数据结构实验七查找

《数据结构实验七查找》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验七查找一、实验目的1.掌握查找的不同方法，并能用高级语言实现查找算法；2.熟练掌握二叉排序树的构造和查找方法。3.熟练掌握静态查找表及哈希表查找方法。二、实验内容设计一个读入一串整数，然后构造二叉排序树，进行查找。三、实验步骤1.从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中。2.在二叉排序树中查找某一结点。3.用其它查找算法进行排序(课后自己做)。四、实现提示1.定义结构typedefstructnode{intkey;intother;structnode*lchild,*rchild;}b

2、stnode;voidinorder(t){if(t!=Null){inorder(tflchild);printf("%4d〃,tTkey);inorder(t-*rchild);}}bstnode*insertbst(t,s)bstnode*s,*t;{bstnode*f,*p;P=t；while(p!=Null){f=p;讦(stkey==ptkey)returnt;if(s—key

3、;elseffrchild二s;returnt;}bstnode*creatord(){bstnode*t,*s;intkey;t=Null;scanf("%d〃,&key);while(key!=0){s=malloc(sizeof(bitree));sfkey二key;Ichild二Null;sfrchild二Null;scanf("%cT,&data);s—other二data;t二insertbst(t,s);scanf("%d〃,&key);returnt;五、思考与提高1.用其它的查找方法完成该算法。2.比较各种算法的时间及

4、空间复杂度。六、完整参考程序1•折半查找#include#include#defineMAX30〃定义有序查找表的最大长度typedefstruct{charelem[MAX];〃有序查找表intlength;//length指示当前有序查找表的长度JSSTable;voidinitial(SSTable&);〃初始化有序查找表intsearch(SSTable,int);〃在有序查找表中查找元素voidprint(SSTable);〃显示有序查找表中所有元素voidmain(){SSTableST;

5、//ST为一有序查找表intch,loc,flag=l;charj;initial(ST);〃初始化有序查找表while(flag){printf(”请选择：");printf(Hl.显示所有元素”);printf("2.查找一个元素”);printf(M3.退出”)；scanfC%c”,&j);switch(j){caseT:print(ST);break;//显示所有元素case2:{printf(”请输入要查找的元素：”)；scanf(n%dH,&ch);〃输入要查找的元素的关键字loc=search(ST,ch)

6、;〃查找if(loc!=0)printf("该元素所在位置是：%d",loc);〃显示该元素位置elseprintf("%d不存在!",ch);〃当前元素不存在break;}default:flag=O;printf(n程序运行结束!按任意键退出!H);voidinitial(SSTable&v)｛〃初始化有序查找表inti;print”请输入静态表的元素个数：”);〃输入有序查找表初始化时的长度scanf(**%d"，&v.length);printf(”请从小到大输入％d个元素(整形数):",v.length);ge

7、tchar();for(i=l;i<=v.length;i++)scanf(n%du,&v.elem

8、i]);〃从小到大输入有序查找表的各元素｝intsearch(SSTablev,intch)｛〃在有序查找表中查找ch的位置，成功返回其位置，失败返回0intlow,high,mid;low=1;high=v.length;//置区间初值while(low<=high){mid=(low+high)/2;if(v.elem[mid]==ch)returnmid;〃找到待查元素elseif(v.elem[mid]>ch)high=mid-

9、l;〃继续在前半区间进行查找elselow二mid+1;〃继续在后半区间进行查找}return0;〃找不到时，i为0}voidprint(SSTablev)〃显示当前有序查找表所有元素{inti;for(i