数据结构与数据库实验报告查找

1、实验数学系 2012 级日期 2013.05.18 No. PB12001117 评分实验题目：查找实验目的：掌握静态查找的算法，学习二叉排序树构造、结点的与删除操作，并学习使用二叉排序树查找，掌握哈希函数的构造、用开放定址法处理。实验分析：实验主要分三部分：静态查找、二叉排序树的操作以及哈希查找。首先要根据三种查找方法的明确操作对象，构造对应的结构体。静态查找只对数据元素进行查询和检索，只需构造数组 r。二叉排序树结构上和二叉树一样，需构造二叉树的结点：typedefstructlocate; key ;NodestructNode*Lchild , *Rchild ;BSTNode, *B

2、STree;哈希查找中的拉链法需构造哈希链表。主函数中只需依次输入找方法进行查找。并用不同的查算法分析：1、 折半查找。用 Low、High 和Mid 表示待查找区间的下界、上界和中间位置指针，初值为 Low=1，High=n。取中间位置 Mid=(Low+High)/2；比较中间位置的关键字与给定的 K 值：若相等则查找成功；若大于 k 则待查在区间的前半段，修改上界指针 High=Mid-1，若小于 k 则待查在区间的后半段，修改下界指针 Low=Mid+1；重复操作直到越界(LowHigh)，查找失败。实现算法如下：binarysearch(r,n,key)low,mid,high;lo

3、w=0; high=n-1;while(lowrmid)low=mid+1;else if(key=rmid) return(mid);else high=mid-1;return -1;2、 二叉排序树。(1) BST 树的查找：首先将给定的 K 值与二叉排序树的根结点的关键字进行比较：若相等则查找成功；若给定的 K 值小于BST 的根结点的关键字，则继续在该结点的树上进行查找；若给定的 K 值大于BST 的根结点的关键字，则继续在该结点的右上进行查找。用递归算法很容易实现：BST_Serach(BSTree T,key)if (T=NULL)return(0);elseif(T-key=k

4、ey )return(T-locate); else if ( keykey )return(BST_Serach(T-Lchild, key) ;elsereturn(BST_Serach(T-Rchild, key) ;(2) BST 树的点x 为：在 BST 树中一个新结点x 时，若BST 树为空则令新结后BST 树的根结点；否则，将结点 x 的关键字与根结点T 的关键字进行比较： 若相等则不需要；若 x.keykey，结点 x到 T的树中；若x.keyT-key，结点 x到T 的右中。递归算法：voidInsert_BST(BSTree &T,BSTNode *s;key,locate

5、)s=(BSTNode *)malloc(sizeof(BSTNode);s-key=key;s-locaocate;s-Lchild=s-Rchild=NULL;if (T=NULL)T=s;elseif (T-key=s-key ) return;/*已有结点 */ else if (s-keykey)Insert_BST(T-Lchild, key,locate);elseInsert_BST(T-Rchild, key,locate) ;(3)BST 树的删除：设被删除结点为 p，其父结点为 f 。若 p 是叶子结点，直接删除 p；若 p 只有一棵，直接用 p 的取代 p 的位置而成为

6、 f 的一棵；若 p 既有树又有右，处理方法有以下两种，可以任选其中一种：1 用 p 的直接前驱结点代替 p。即从 p 的树中选择值最大的结点 s 放在p 的位置(用结点 s 的内容替换结点 p 内容)，然后删除结点 s。s 是 p 的树中的最右边的结点且没有右。2 用 p 的直接后继结点代替 p。即从 p的右中选择值最小的结点s 放在p 的位置(用结点s 的内容替换结点p 内容)，然后删除结点 s。s 是 p 的右中的最左边的结点且没有法如下：树。算void Delete_BST (BSTree &BST ,key)BSTNode *p=BST , *f=NULL , *q , *s ;wh

7、ile ( p!=NULL&p-key!=key) f=p ;/f 指向 p 的父结点if (keykey) p=p-Lchild ;/搜索 else p=p-Rchild ;/ 搜索右树/ 没有要删除的结点if(p=NULL)return;/ 找到了要删除的结点为 ps=p ;if (p-Lchild!=NULL& p-Rchild!=NULL)f=p ;/ 从树开始找s=p-Lchild ;while (s-Rchild!=NULL)f=s ;/ 左、右都不空，找树中最右边的结点s=s-Rchild ;p-key=s-key ;p-locate=s-locate;/用结点s 的内容替换结点

8、p 内容/将第 3 种情况转换为第 2 种情况if(s-Lchild!=NULL)/ 若s 有q=s-Lchild ; else q=s-Rchild ;树，右为空if(f=NULL)BST=q ;else if (f-Lchild=s)f-Lchild=q ;else f-Rchild=q; free(s);(4)BST 树的创建：利用 BST 树的操作，可以从空树开始逐个每个结点，从而建立一棵BST 树，算法如下：BSTreecreate_BST(i;rs,n )BSTree T=(BSTNode *)malloc(sizeof(BSTNode);T=NULL;for(i=1;i=n;i+

9、) Insert_BST(T,rsi,i);return(T);(5)BST 树的输出：由于二叉排序树的中序遍历正好使采用中序遍历输出。3、哈希查找。从小到大排列，故(1) 线性探测发：将散列表 T0 m-1看成循环向量。当发生时，从初次发生的位置依次向后探测其他的地址。增量序列为 di=1, 2, 3, , m-1,设初次发生的地址是 d，则依次探测 Td+1，Td+2，直到 Tm-1时又循环到表头，再次探测 T0，T1，直到 Td-1。探测过程终止的情况是：探测到的地址为空则表中没有，若是查找则失败，若是则将写则入到该地址；探测到的地址有给定的关键字，若是查找则成功，若是失败。Hash_s

10、earch1(HT,k,m)/ 用线性探查法解决d, temp ; d=h(k) ;temp=d; /作为哨兵while (HTd!=-858993460)，m 为表长if (HTd=k)return(d) ;/查找成功 else d=h(d+1);if(d=temp)return -1; /查找失败return d ; /遇到空单元Hash_Insert1(HT ,s,m)/在 HT 表中一个新结点是sd=Hash_search1(HT,s, m);/表满，不能if(d=-1) return -1;elseif(HTd=s)return 0; elseHTd=s;return 1;/表中已有

11、该结点/新结点/成功void Hash_create1( i,s;HT,n)prf(输入序列：); for(i=0;ikey!=k)p=p-next; return p;/*用链地址法解决*/Hash_Insert2(HTlist T , HTNoded;*s,n)HTNode *p=Hash_search2(T,s-key,n);if(p!=NULL)return 0;/表中已有该结点 elsed=(s-key)%n;s-next=Td;Td=s;/成功return 1;void Hash_create2(HTlist T , i,temp;HTlist s30;prf(请输入序列:); f

12、or(i=1;ikey=temp;Hash_Insert2(T, si, n);源程序：#include#include#define LT(a,b) (a)(b)#define LQ(a,b) (a)=(b)#define EQ(a,b) (a)=(b)typedefstructlocate; key ;NodestructNode*Lchild , *Rchild ;BSTNode, *BSTree;typedef struct nodekey;struct node *next;HTNode;r100;binarysearch(r,n,key)low,mid,high;low=0; hi

13、gh=n-1;while(lowrmid)low=mid+1;else if(key=rmid) return(mid);else high=mid-1;return -1;voidInsert_BST(BSTree &T,BSTNode *s;key,locate)s=(BSTNode *)malloc(sizeof(BSTNode);s-key=key;s-locaocate;s-Lchild=s-Rchild=NULL;if (T=NULL)T=s;elseif (T-key=s-key ) return;/*已有结点*/ else if (s-keykey)Insert_BST(T-L

14、child, key,locate);elseInsert_BST(T-Rchild, key,locate) ;BSTreecreate_BST(i;rs,n )BSTree T=(BSTNode *)malloc(sizeof(BSTNode);T=NULL;for(i=1;ikey=key )return(T-locate); else if ( keykey )return(BST_Serach(T-Lchild, key) ;elsereturn(BST_Serach(T-Rchild, key) ;void Delete_BST (BSTree &BST ,key)/ 在以 T 为

15、根结点的 BST 树中删除关键字为key 的结点BSTNode *p=BST , *f=NULL , *q , *s ; while ( p!=NULL&p-key!=key)f=p ;/f 指向 p 的父结点if (keykey) p=p-Lchild ;/搜索 else p=p-Rchild ;/ 搜索右树if(p=NULL)return;/ 没有要删除的结点/ 找到了要删除的结点为 ps=p ;if (p-Lchild!=NULL& p-Rchild!=NULL)f=p ;/ 从树开始找s=p-Lchild ;while (s-Rchild!=NULL)f=s ;/ 左、右都不空，找树中

16、最右边的结点s=s-Rchild ;p-key=s-key ;p-locate=s-locate;/用结点s 的内容替换结点p 内容/将第 3 种情况转换为第 2 种情况if(s-Lchild!=NULL)/ 若s 有q=s-Lchild ; else q=s-Rchild ;树，右为空if(f=NULL)BST=q ;else if (f-Lchild=s)f-Lchild=q ;else f-Rchild=q; free(s);voidInorderTraverse(BSTreeif(T!=NULL)T)InorderTraverse(T-Lchild) ;/根结点prf(%d ,T-ke

17、y);InorderTraverse(T-Rchild) ;h(key)d=key % 11; return d;Hash_search1(HT,k,m)/ 用线性探查法解决d, temp ; d=h(k) ;temp=d; /作为哨兵while (HTd!=-858993460)，m 为表长if (HTd=k)return(d) ;/查找成功 else d=h(d+1);if(d=temp)return -1; /查找失败return d ; /遇到空单元Hash_Insert1(/在 HT 表中HT ,s,m)一个新结点是sd=Hash_search1(HT,s, m);/表满，不能if(

18、d=-1) return -1;elseif(HTd=s)return 0; elseHTd=s;return 1;/表中已有该结点/新结点/成功void Hash_create1( i,s;HT,n)prf(输入序列：); for(i=0;ikey!=k) p=p-next;return p;/用链地址法解决Hash_Insert2(HTlist T , HTNode d;*s,n)HTNode *p=Hash_search2(T,s-key,n);if(p!=NULL)return 0;/表中已有该结点 elsed=(s-key)%n;s-next=Td;Td=s;/成功return 1;

19、void Hash_create2(HTlist T , i,temp;HTlist s30;prf(请输入序列:); for(i=1;ikey=temp; Hash_Insert2(T, si, n);void main()rs100,rh11;i,n,key,x,k; BSTree T;prf(折半查找n);prf(请输入序列个数：);scanf(%d,&n);prf(请输入序列：); for(i=0;in;i+)scanf(%d,&ri);prf(请输入需要查找的数：); scanf(%d,&key);i=binarysearch(r,n,key); if(i!=-1)prf(查找成功！所查找的数的位置：%d,i+1);prf(n);elsepr prf(not found);f(n);prf(nBST 树查找n);prf(请输入序列个数：);scanf(%d,&n);prf(请输入序列：); for(i=1;i=n;i+)scanf(%d,&rsi); T=create_BST(rs,n);prf(请输入要查找的数:);scanf(%d,&key); x=BST_Serach(T, key);if(x=0) prf(查找失败！);else prf(查