《数据结构试验指导书08.docx》由会员分享，可在线阅读，更多相关《数据结构试验指导书08.docx（11页珍藏版）》请在三一文库上搜索。
1、实验八查找8.1实验目的：(1) 熟悉掌握各种查找方法，深刻理解各种查找算法及其执行的过程;(2) 学会分析各种查找算法的性能。8.2实验要求：(1) 复习课本中有关查找的知识；(2) 用C语言完成算法和程序设计并上机调试通过；(3) 撰写实验报告，给出算法思路或流程图和具体实现(源程序)、算法分析结果(包括 时间复杂度、空间复杂度以及算法优化设想)、输入数据及程序运行结果(必要时给 出多种可能的输入数据和运行结果)。8.3基础实验实验1顺序查找的设计与实现实验内容与要求：编写一个程序实现在顺序表7,8, 34, 5, 9, 12, 10, 2, 4中查找 9 的过程。分析：算法思想参照课本。
2、参考程序：#include <stdio.h>#define MAXL 100/*定义表中最多记录个数*/typedef int KeyType;typedef char InfoType10;typedef structKeyType key;InfoType data; NodeType;typedef NodeType SeqListMAXL;/*KeyType为关键字的数据类型*/*其他数据*/*顺序表类型*/int SeqSearch(SeqList R,int n,KeyType k) /* 顺序查找算法 */int i=0;while (i<n &&am
3、p; Ri.key!=k)printf("%d ”,Ri.key);i+;/*从表头往后找*/if (i>=n)11return -1;else(printf("%d”,Ri.key);return i;void main()(SeqList R;int n=10;KeyType k=9;int a=7,8,34,5,9,12,10,2,4,i;for (i=0;i<n;i+)/*建立顺序表 */Ri.key=ai;printf("n");if (i=SeqSearch(R,n,k)!=-1)printf("n 元素 %d 的位置是
4、 %dn",k,i);elseprintf("n 元素 %d 不在表中 n",k);printf("n");实验2折半查找的设计与实现 实验内容与要求：2, 4, 6, 8, 10, 12, 14, 16进行折半查找关键字14编写一个程序，实现对顺序表 的过程。分析：算法思想参照课本。参考程序：#include <stdio.h>#define MAXL 100typedef int KeyType;typedef char InfoType10;typedef structKeyType key;InfoType data;/ N
5、odeType;typedef NodeType SeqListMAXL;int BinSearch(SeqList R,int n,KeyType k)/*定义表中最多记录个数*/*KeyType为关键字的数据类型*/*其他数据*/*顺序表类型*/*二分查找算法*/int low=0,high=n-1,mid,count=0;while (low<=high) (mid=(low+high)/2;printf("第d次查找：在%d,%d中查找到元素 R%d:%dn”,if (Rmid.key=k) return mid;if (Rmid.key>k) high=mid-
6、1;elselow=mid+1;return -1;+count,low,high,mid,Rmid.key);/*查找成功返回*/*继续在Rlow.mid-1中查找*/*继续在 Rmid+1.high中查找*/void main()(SeqList R;KeyType k=14;int a=2,4,6,8,10,12,14,16,i,n=10;for (i=0;i<n;i+)/*建立顺序表 */Ri.key=ai;printf("n");if (i=BinSearch(R,n,k)!=-1)printf("元素 %d 的位置是 %dn",k,i)
7、;elseprintf("元素%d不在表中n",k);printf("n");8.4提高实验实验1二叉排序树的设计与实现。实验内容与要求：编写一个程序实现二叉排序树的基本运算，并在此基础上完成如下功能：(1) 由4, 9, 0, 1, 8, 6, 3, 5, 2, 7创建一棵bt并以括号表示法输出;(2) 判断bt是否为一棵二叉排序树；(3) 采用递归和非递归两种方法查找关键字为6的结点，并输出其查找路径；(4) 分别删除bt中的关键字为4和5的结点，并输出删除后的二叉排序树。分析：二叉排序树的查找过程如下：即当二叉排序树不为空的时候，首先将给定值和根结
8、点的关键字比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树和右子树上继续进行查找。参考程序：#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef int KeyType;typedef char InfoType;typedef struct nodeKeyType key;InfoType data;struct node *lchild,*rchild; BSTNode;int pathMaxSize;void DispBST(BSTNode *b);in
9、t InsertBST(BSTNode *p,KeyType k)点*/if (p=NULL)/*定义关键字类型*/*记录类型*/*关键字项*/*其他数据域*/*左右孩子指针*/*全局变量，用于存放路径*/*函数说明*/*在以*p为根结点的BST中插入一个关键字为/*原树为空，新插入的记录为根结点*/k的结p=(BSTNode *)malloc(sizeof(BSTNode);p->key=k;p->lchild=p->rchild=NULL;return 1;else if (k=p->key)return 0;else if (k<p->key)retu
10、rn InsertBST(p->lchild,k);/*插入到 *p 的左子树中 */elsereturn InsertBST(p->rchild,k); /*插入到 *p 的右子树中 */BSTNode *CreatBST(KeyType A,int n)/*由数组A中的关键字建立一棵二叉排序树*/BSTNode *bt=NULL;/* 初始时 bt 为空树*/int i=0;while (i<n)if (InsertBST(bt,Ai)=1)/* 将 Ai插入二叉排序树T 中 */printf("第%d 步，插入 d:",i+1,Ai);DispBST
11、(bt);printf("n");i+;return bt;/*返回建立的二叉排序树的根指针 */void Delete1(BSTNode *p,BSTNode *r)/*当被删*p结点有左右子树时的删除过程*/BSTNode *q;if (r->rchild!=NULL) Delete1(p,r->rchild); /* 递归找最右下结点 */ else/*找到了最右下结点*r*/ p->key=r->key;/*将*r的关键字值赋给*p*/q=r; r=r->lchild;/*将*r的双亲结点的右孩子结点改为*r的左孩子结点*/free(q
12、);/*释放原*r的空间*/void Delete(BSTNode *p)/*从二叉排序树中删除*p结点*/BSTNode *q; if (p->rchild=NULL)/*p结点没有右子树的情况 */ q=p;p=p->lchild;free(q); else if (p->lchild=NULL) /*p结点没有左子树的情况 */ q=p;p=p->rchild;free(q); else Delete1(p,p->lchild); /*p结点既有左子树又有右子树的情况*/ int DeleteBST(BSTNode *bt,KeyType k) /*在bt中
13、删除关键字为k的结点*/ if (bt=NULL) return 0;/* 空树删除失败 */else if (k<bt->key) return DeleteBST(bt->lchild,k);/*递归在左子树中删除关键字为k的结点*/else if (k>bt->key)return DeleteBST(bt->rchild,k);/*递归在右子树中删除关键字为k的结点*/else/*k=bt->key 的情况 */Delete(bt);/* 调用 Delete(bt)函数删除 *bt 结点 */return 1;void SearchBST1(B
14、STNode *bt,KeyType k,KeyType path,int i)/*以非递归方式输出从根结点到查找到的结点的路径*/int j;if (bt=NULL) return;else if (k=bt->key)/* 找到了结点 */pathi+1=bt->key; /* 输出其路径 */for (j=0;j<=i+1;j+)printf("%3d”,pathj);printf("n");elsepathi+1=bt->key;if (k<bt->key)SearchBST1(bt->lchild,k,path,
15、i+1);/* 在左子树中递归查找 */elseSearchBST1(bt->rchild,k,path,i+1);/* 在右子树中递归查找 */int SearchBST2(BSTNode *bt,KeyType k)/*以递归方式输出从根结点到查找到的结点的路径*/if (bt=NULL)return 0;else if (k=bt->key)printf("%3d",bt->key);return 1;else if (k<bt->key)SearchBST2(bt->lchild,k);/* 在左子树中递归查找*/elseSear
16、chBST2(bt->rchild,k);/* 在右子树中递归查找 */printf("%3d",bt->key);void DispBST(BSTNode *bt)/*以括号表示法输出二叉排序树bt*/if (bt!=NULL)(printf("%d”,bt->key);if (bt->lchild!=NULL | bt->rchild!=NULL)(printf("(");DispBST(bt->lchild);if (bt->rchild!=NULL) printf(",");
17、DispBST(bt->rchild);printf(")");KeyType predt=-32767; /*predt为全局变量，保存当前结点中序前趋的值，初值为-m */int JudgeBST(BSTNode *bt) /* 判断 bt 是否为 BST*/ (int b1,b2;if (bt=NULL)return 1;else(b1=JudgeBST(bt->lchild);if (b1=0 | predt>=bt->key)return 0;predt=bt->key;b2=JudgeBST(bt->rchild);retur
18、n b2;void main()(BSTNode *bt;KeyType k=6;int a=4,9,0,1,8,6,3,5,2,7,n=10;printf("创建一棵 BST 树:")；printf("n");bt=CreatBST(a,n);printf(" BST:");DispBST(bt);printf("n");printf(" bt%sn",(JudgeBST(bt)?"是一棵 BST":"不是一棵 BST");printf("n&
19、quot;);printf("查找 %d 关键字(递归):",k);SearchBST1(bt,k,path,-1);printf("查找 %d 关键字(非递归):",k);SearchBST2(bt,k);printf("n 删除操作:n");printf("原 BST:");DispBST(bt);printf("n");printf("删除结点 4:");DeleteBST(bt,4);DispBST(bt);printf("n");printf(&
20、quot;删除结点 5:");DeleteBST(bt,5);DispBST(bt);printf("nn");实验2哈希查找的设计与实现实验内容与要求：编写一个程序实现哈希表的相关运算，并在此基础上完成如下功能：(1) 建立 16, 74, 60, 43, 54, 90。46, 31, 29, 88, 77哈希表 A0.12,哈希函 数为H (k) =key%p,并用线性探查法解决冲突；(2) 在上述哈希表中查找关键字为29的记录；(3) 在上述哈希表中删除关键字为77的记录，再将其插入。分析:哈希表查找的过程为根据给定 key值，按照造表时设定的哈希函数求得哈
21、希地址， 若表中 此位置上为空，没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功； 否则根据造表时设定的处理冲突的方法找“下一地址” ，直至哈希表中某个位置为空或者表 中所填记录的关键字等于给定值时为止。 参考程序：/*定义最大哈希表长度*/*定义空关键字值*/*定义被删关键字值*/*关键字类型*/#include <stdio.h> #define MaxSize 100#define NULLKEY -1 #define DELKEY -2 typedef int KeyType;typedef char * InfoType; /* 其他数据类型 */ ty
22、pedef struct KeyType key;InfoType data; int count;/*关键字域*/*其他数据域*/*探查次数域*/ HashTableMaxSize;/* 哈希表类型 */void InsertHT(HashTable ha,int *n,KeyType k,int p)/*将关键字 k 插入到哈希表中 */int i,adr;adr=k % p;if (haadr.key=NULLKEY | haadr.key=DELKEY) /*xj可以直接放在哈希表中*/haadr.key=k; haadr.count=1;else/*发生冲突时采用线性探查法解决冲突*
23、/(i=1;/*i记录xj发生冲突的次数*/do(adr=(adr+1) % p;i+; while (haadr.key!=NULLKEY && haadr.key!=DELKEY);haadr.key=k;haadr.count=i;n+; void CreateHT(HashTable ha,KeyType x,int n,int m,int p) /* 创建哈希表 */ (int i,n1=0;for (i=0;i<m;i+)/* 哈希表置初值 */( hai.key=NULLKEY; hai.count=0;for (i=0;i<n;i+) InsertH
24、T(ha,n1,xi,p);int SearchHT(HashTable ha,int p,KeyType k)/* 在哈希表中查找关键字k*/(int i=0,adr;adr=k % p;while (haadr.key!=NULLKEY && haadr.key!=k) (i+;/*采用线性探查法找下一个地址*/adr=(adr+1) % p;if (haadr.key=k)/* 查找成功 */return adr;else/*查找失败*/return -1; int DeleteHT(HashTable ha,int p,int k,int *n)/* 删除哈希表中关键字
25、k*/(int adr;adr=SearchHT(ha,p,k);if (adr!=-1)/*在哈希表中找到该关键字*/( haadr.key=DELKEY; n-;/*哈希表长度减1*/return 1; else/*在哈希表中未找到该关键字*/return 0; void DispHT(HashTable ha,int n,int m) /* 输出哈希表 */ ( float avg=0; int i; printf("哈希表地址：t"); for (i=0;i<m;i+) printf(" %3d",i); printf(" n&q
26、uot;); printf("哈希表关键字:t"); for (i=0;i<m;i+)if (hai.key=NULLKEY | hai.key=DELKEY) printf(" ");/* 输出 3 个空格 */elseprintf(" %3d",hai.key); printf(" n"); printf("搜索次数:t"); for (i=0;i<m;i+) if (hai.key=NULLKEY | hai.key=DELKEY) printf(" ");
27、/* 输出 3 个空格 */elseprintf(" %3d",hai.count); printf(" n"); for (i=0;i<m;i+) if (hai.key!=NULLKEY && hai.key!=DELKEY) avg=avg+hai.count; avg=avg/n; printf("平均搜索长度 ASL(%d)=%gn”,n,avg); void main() (int x=16,74,60,43,54,90,46,31,29,88,77;int n=11,m=13,p=13,i,k=29;Hash
28、Table ha;CreateHT(ha,x,n,m,p);printf("n");DispHT(ha,n,m);i=SearchHT(ha,p,k);if (i!=-1)printf(" ha%d.key=%dn”,i,k);elseprintf("未找到 %dn",k);k=77;printf("删除关键字 %dn",k);DeleteHT(ha,p,k,n);DispHT(ha,n,m);i=SearchHT(ha,p,k);if (i!=-1)printf(" ha%d.key=%dn”,i,k);elseprintf("未找到 %dn",k);printf("插入关键字 %dn",k);InsertHT(ha,n,k,p);DispHT(ha,n,m);printf("n");8.5思考题：(1) 将折半查找算法改成递归算法。(2) 试写一个判定给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结 构。且树中结点的关键字均不相同。(3) 假设哈希表长为m,哈希函数为 H (x),用链地址法处理冲突。试编写输入一组关键 字并建造哈希表的算法。