数据结构实验报告-静态查找表中的查找

数据结构实验实验一 静态查找表中的查找一、实验目的：1、理解静态查找表的概念2、掌握顺序查找和折半查找算法及其实现方法3、理解顺序查找和折半查找的特点，学会分析算法的性能二、实验内容：1、按关键字从小到大顺序输入一组记录构造查找表，并且输出该查找表；2、给定一个关键字值，对所构造的查找表分别进行顺序查找和折半查找，输出查找的结果以及查找过程中“比较”操作的执行次数。三、实验要求：1、查找表的长度、查找表中的记录和待查找的关键字值要从终端输入；2、具体的输入和输出格式不限；3、算法要具有较好的健壮性，对错误操作要做适当处理；4、输出信息中要标明所采用的查找方法类型。实验二 基于二叉排序树的查找一、实验目的：1、理解动态查找表和二叉排序树的概念2、掌握二叉排序树的构造算法及其实现方法3、掌握二叉排序树的查找算法及其实现方法二、实验内容：1、输入一组记录构造一颗二叉排序树，并且输出这棵二叉排序树的中序序列；2、给定一个关键字值，对所构造的二叉排序树进行查找，并输出查找的结果。三、实验要求：1、二叉排序树中的记录和待查找的关键字值要从终端输入；2、输入的记录格式为(整数，序号)，例如(3, 2)表示关键字值为3，输入序号为2的记录；3、算法要具有较好的健壮性，对错误操作要做适当处理。四、程序实现：(1)实现顺序查找表和折半查找表：#include#define MAX_LENGTH 100typedef struct int keyMAX_LENGTH; int length;stable;int seqserch(stable ST,int key,int &count) int i; for(i=ST.length;i0;i-) count+; if(ST.keyi=key) return i; return 0;int binserch(stable ST,int key,int &count) int low=1,high=ST.length,mid; while(low=high) count+; mid=(low+high)/2; if(ST.keymid=key) return mid; else if(keyST.keymid) high=mid-1; else low=mid+1; return 0;main() stable ST1; int a,b,k,x,count1=0,count2=0,temp=0; ST1.length=0; printf(请按从小到大的顺序输入查找表数据：(-1代表结束！)n); for(a=0;aMAX_LENGTH;a+) scanf(%d,&temp); if(temp!=-1) ST1.keya=temp; ST1.length+; else break; printf(输入数据为：n); for(b=0;bST1.length;b+) printf(%d ,ST1.keyb); printf(n请输入要查找的数据：); scanf(%d,&k); a=seqserch(ST1,k,count1)+1; printf(n顺序查找： 该数据的位置在第：%d个n,a); printf(查找次数为：%dnn,count1-1); a=binserch(ST1,k,count2)+1; printf(折半查找： 该数据的位置在第：%d个n,a); printf(查找次数为：%dn,count2-1);（2）二叉排序树的查找：#include#includetypedef struct node int data; int key; struct node *left,*right;bitnode,*bittree;void serchbst(bittree T,bittree *F,bittree *C,int data) while(T!=NULL) if(T-data=data) *C=T; break; else if(datadata) *F=T; T=T-left; else *F=T; T=T-right; return 0;int insertbst(bittree *T,int key,int data) bittree F=NULL,C=NULL,s; serchbst(*T,&F,&C,data); if(C!=NULL) return 0; s=(bittree)malloc(sizeof(bitnode); s-data=data; s-key=key; s-left=s-right=NULL; if(F=NULL) *T=s; else if(datadata) F-left=s; else F-right=s; return 1;void creatbst(bittree *T) int key,data;*T=NULL; printf(请输入数据以构造二叉排序树：(数据格式为:m n (-1000,-1000)代表结束)n); scanf(%d%d,&key,&data); while(key!=-1000 | data!=-1000) insertbst(T,key,data); scanf(%d%d,&key,&data); void midTraverse(bittree T) if(T!=NULL) midTraverse(T-left); printf(%d,%d) ,T-key,T-data); midTraverse(T-right); main() bittree T=NULL,C=NULL,F=NULL; int key,data,temp; creatbst(&T); printf(此二叉树的中序序列为：); midTraverse(T); printf(n请输入要查找的关键字：); scanf(%d,&data); serchbst(T,&F,&C,data); printf(此关键字的数据为：%dn,C-key);五、实现结果：(1)顺序查找和折半查找：(2)二叉树排序树查找：六、实验之心得体会：（1）在这次实验中，我基本上掌握了顺序查找、折半查找和二叉排序树查找的基本思想和实现方法，让我体会到了写程序时，不仅要考虑是否能够调试出结果，还要考虑程序实现的效率，这是一个编程人员必须要具备的一项总要的素质。（2）通过这次实验，让我体会到同样的数据在不同的查询方法下有着不同的查询效率，就拿实验一来说，用顺序查找法在12个数据中查找一个关键字需要的查找的次数为8次，但是，如果折半查找法却只要两次，由此可以看出，我们在查找时不仅要考虑查找的实现，还要考虑查找的效率和查找所用的时间。（3）用二叉排序树查找效率也比较高，只要你输入相应的关键字，就可已找到所需要的数据，就我个人看来，用二叉排序树的效率要比顺序查找和折半查找的效率更高，查询的速度更快。