2022年数据结构实验七查找定义 .pdf

《2022年数据结构实验七查找定义 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验七查找定义 .pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、inorder ( t ) if (t!=Null) inorder(tlchild); printf(“%4d ”, tkey); inorder(trchild); bstnode *insertbst(t, s) bstnode *s, *t; bstnode *f, *p; p=t; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 13 页 - - - - - - - - - while(p!=Null) f=p; if (skey= =p key) return

3、 t; if (skeypkey) p=plchild; else p=prchild; if(t= =Null) return s; if (skeyfkey) flchild=s; else frchild=s; return t; bstnode *creatord( ) bstnode *t, * s; int key; t=Null; scanf( “%d ”,&key); while (key!=0) s=malloc(sizeof (bitree); skey=key; slchild=Null; srchild=Null; scanf( “%d ”, &data); sothe

4、r=data; t=insertbst(t, s); scanf( “%d ”,&key); return t; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 13 页 - - - - - - - - - 五、思考与提高1. 用其它的查找方法完成该算法。2.比较各种算法的时间及空间复杂度。六、完整参考程序1.折半查找#include #include #define MAX 30 /定义有序查找表的最大长度typedef struct char elemMAX; /有序

5、查找表int length; /length 指示当前有序查找表的长度SSTable; void initial(SSTable &); /初始化有序查找表int search(SSTable,int); /在有序查找表中查找元素void print(SSTable); /显示有序查找表中所有元素void main() SSTable ST; /ST 为一有序查找表int ch,loc,flag=1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 13 页 - - -

6、- - - - - - char j; initial(ST); /初始化有序查找表while(flag) printf( 请选择： n); printf(1.显示所有元素 n); printf(2.查找一个元素 n); printf(3.退出n); scanf( %c,&j); switch(j) case 1:print(ST); break; /显示所有元素case 2:printf(请输入要查找的元素： ); scanf(%d,&ch); /输入要查找的元素的关键字loc=search(ST,ch); /查找if(loc!=0) printf( 该元素所在位置是： %dn,loc);

7、/显示该元素位置else printf(%d 不存在 !n,ch);/当前元素不存在break; default:flag=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 13 页 - - - - - - - - - printf( 程序运行结束 !按任意键退出 !n); void initial(SSTable &v) /初始化有序查找表int i; printf( 请输入静态表的元素个数：); /输入有序查找表初始化时的长度scanf(%d,&v.length)

8、; printf( 请从小到大输入 %d 个元素（整形数）：n,v.length); getchar(); for(i=1;i=v.length;i+) scanf(%d,&v.elemi); / 从小到大输入有序查找表的各元素 int search(SSTable v,int ch) /在有序查找表中查找ch 的位置，成功返回其位置，失败返回0 int low,high,mid; low=1;high=v.length; /置区间初值名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第

9、5 页，共 13 页 - - - - - - - - - while(lowch) high=mid-1; / 继续在前半区间进行查找else low=mid+1; /继续在后半区间进行查找 return 0; /找不到时， i 为 0 void print(SSTable v) /显示当前有序查找表所有元素int i; for(i=1;i=v.length;i+) printf(%d ,v.elemi); printf(n); 2.二叉排序树的建立与查找#include #include #include #include 名师资料总结 - - -精品资料欢迎下载 - - - - - - -

10、 - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 13 页 - - - - - - - - - enum BOOLFalse,True; typedef struct BiTNode /定义二叉树节点结构char data; /为了方便，数据域只有关键字一项struct BiTNode *lchild,*rchild; / 左右孩子指针域BiTNode,*BiTree; BOOL SearchBST(BiTree,char,BiTree,BiTree&); /在二叉排序树中查找元素BOOL InsertBST(BiTree &,char);

11、 /在二叉排序树中插入元素BOOL DeleteBST(BiTree &,char); /在二叉排序树中删除元素void Delete(BiTree &); /删除二叉排序树的根结点void InorderBST(BiTree); /中序遍历二叉排序树， 即从小到大显示各元素void main() BiTree T,p; char ch,keyword,j=y; BOOL temp; T=NULL; while(j!=n) printf(1.displayn); printf(2.searchn); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -

12、- - - - - 名师精心整理 - - - - - - - 第 7 页，共 13 页 - - - - - - - - - printf(3.insertn); printf(4.deleten); printf(5.exitn); scanf( %c,&ch); / 输入操作选项switch(ch) case 1:if(!T) printf(The BST has no elem.n); else InorderBST(T);printf(n); break; case 2:printf(Input the keyword of elem to be searched(a char):);

13、scanf( %c,&keyword); / 输入要查找元素的关键字temp=SearchBST(T,keyword,NULL,p); if(!temp) printf(%c isnt existed!n,keyword); / 没有找到else printf(%c has been found!n,keyword); /成功找到break; case 3:printf(Input the keyword of elem to be inserted(a char):); scanf( %c,&keyword); / 输入要插入元素的关键字temp=InsertBST(T,keyword);

14、if(!temp) printf(%c has been existed!n,keyword); /该元素已经存在else printf(Sucess to inert %c!n,keyword); /成功插入名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 13 页 - - - - - - - - - break; case 4:printf(Input the keyword of elem to be deleted(a char):); scanf( %c,&key

15、word); / 输入要删除元素的关键字temp=DeleteBST(T,keyword); if(!temp) printf(%c isnt existed!n,keyword); / 该元素不存在else printf(Sucess to delete %cn,keyword); / 成功删除break; default: j=n; printf(The program is over!nPress any key to shut off the window!n); getchar();getchar(); void InorderBST(BiTree T) /以中序方式遍历二叉排序树T

16、，即从小到大显示二叉排序树的所有元素if(T-lchild) InorderBST(T-lchild); printf(%2c,T-data); if(T-rchild) InorderBST(T-rchild); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 13 页 - - - - - - - - - BOOL SearchBST(BiTree T,char key,BiTree f,BiTree &p) /在根指针 T 所指二叉排序树中递归的查找其关键字等于key

17、 的元素，若查找成功/则指针 p 指向该数据元素，并返回True,否则指针指向查找路径上访问的最后一/个结点并返回 False,指针 f 指向 T 的双亲，其初始调用值为NULL BOOL tmp1,tmp2; tmp1=tmp2=False; if(!T) p=f;return False; /查找不成功else if(key=T-data) p=T;return True; /查找成功else if(keydata) tmp1=SearchBST(T-lchild,key,T,p); / 在左子树中继续查找else tmp2=SearchBST(T-rchild,key,T,p); / 在

18、右子树中继续查找if(tmp1|tmp2) return True; /若在子树中查找成功，向上级返回True else return False; /否则返回 False BOOL InsertBST(BiTree &T,char e) /当二叉排序树 T 中不存在元素 e时，插入 e并返回 True,否则返回 False 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 13 页 - - - - - - - - - BiTree p,s; if(!SearchBST(

19、T,e,NULL,p) / 查找不成功s=(BiTree)malloc(sizeof(BiTNode); s-data=e; s-lchild=s-rchild=NULL; if(!p) T=s; /被插结点 *s 为新的根结点else if(edata) p-lchild=s; /被插结点 *s 为左孩子else p-rchild=s; /被插结点 *s 为右孩子return True; /成功插入 else return False; / 树中已存在关键字为e的数据元素 BOOL DeleteBST(BiTree &T,char key) /若二叉排序树 T 中存在关键字等于key 的数据

20、元素时，则删除该数据元素结点/并返回 True,否则返回 False BOOL tmp1,tmp2; tmp1=tmp2=False; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 13 页 - - - - - - - - - if(!T) return False; /不存在关键字等于key 的数据元素else if(key=T-data) Delete(T); return True; /找到关键字等于 key 的数据元素并删除它else if(keydata)

21、tmp1=DeleteBST(T-lchild,key); /继续在左子树中删除else tmp2=DeleteBST(T-rchild,key); /继续在右子树中删除if(tmp1|tmp2) return True; /在子树中删除成功，返回True else return False; /不存在该元素 void Delete(BiTree &p) /在二叉排序树中删除结点p,并重接它的左或右子树BiTree s,q; if(!p-rchild) /右子树空，只需重接它的左子树q=p; p=p-lchild; free(q); 名师资料总结 - - -精品资料欢迎下载 - - - - -

22、 - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 13 页 - - - - - - - - - else if(!p-lchild) / 左子树空，只需重接它的右子树q=p; p=p-rchild; free(q); else /左右子树均不空q=p; s=p-lchild; while(s-rchild) q=s;s=s-rchild; / 转左，然后向右走到尽头p-data=s-data; /s 指向被删结点的“前驱”if(q!=p) q-rchild=s-rchild; / 重接*q 的右子树else q-lchild=s-lchild; /重接*q 的左子树free(s); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 13 页 - - - - - - - - -