查找实验报告

1、实验报告姓课程名称：院（系专业/年级：实验四查找一、实验目的1.掌握顺序表的查找方法，尤其是折半查找方法；2.掌握二叉排序树的查找算法。二、实验预习内容请在上机前认真阅读教材及实验指导书，并在以下空白处填写相应的内容。1.请写出简单顺序查找算法。intseq_search(elementtypeA,intn,keytypex)i=n;A0.key=x;while(Ai.key=x)i-；returni;2.请写出有序表二分（折半）查找算法。(1)非递归算法intbin_search(elementtypeA,intn,keytypex)intmid,low=0,high=n-1;/初始化查找区

2、域while(low=high)mid=(low+high)/2;if(x=Amid.keyreturnmid;elseif(xhigh)return-1;/查找失败elsemid=(low+high)/2;/求解中间元素的下标if(x=Amid.key)returnmid;/查找成功elseif(xkeykey)insert(T-lchild,S);/插入到T的左子树中elseinsert(T-rchild,S);/插入到T的右子树中3）请写出二叉排序树构造的算法。voidcreate_bst(Bnode*&T);/通过插入结点构造二叉排序树的算法Bnode*u;elementtypex;T

3、=NULL;cinx;/初始化根指针并读入第一个元素值While(x!=end_of_num)/x不是结束符时u=newBnode;u-data=x;/产生新结点并装入数据u-lchild=NILL;u-rchild=NULL;/设置左、右孩子指针为空insert(T,u);/插入结点到二叉排序树T中cinx;/读入下一个元素的值）请写出二叉排序树查找的算法。非递归算法：Bnode*bst_search(Bnode*T,keytypex)Bnode*P=T;/P指向根while(p!=NULL)if(x=p-key)returnp;/查找成功elseif(xkey=p-lchild);/到左子

4、树中继续查找elsep=p-rchild;/到右子树中继续查找returnp;/返回结果可能为空，也可能非空递归算法：Bnode*bst_search(Bnode*T,keytypex)if(T=NULL|t-key=x)returnT;/子树为空或已经找到时均可结束elseif(xkey)returnbst_search(T-lchild,x);/左子树中查找的结果就是函数的结果elsereturnbst_search(T-rchild,x);/右子树中查找的结果就是函数的结果三、上机实验1.实验内容。1）建立一个顺序表，用顺序查找的方法对其实施查找；2）建立一个有序表，用折半查找的方法对其

5、实施查找；3）建立一个二叉排序树，根据给定值对其实施查找；4）对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。2.实验源程序。(1)#include#include#definemax100intx;typedefstructintdatamax;intlistlen;seqlist;voidinitial_list(seqlist*L)L-listlen=0;voidlist_creat(seqlist*L)inti;L-listlen+;i=L-listlen;L-datai=x;intlast_search(seqlist*L)inti;i=L-listlen;L-dat

6、a0=x;while(L-datai!=x)i-;returni;intfirst_search(seqlist*L)inti,n;n=L-listlen;for(i=1;idatai=x)returni;return-1;intbin_search(seqlist*L)intmid,low=1,high=L-listlen;while(lowdatamid)returnmid;elseif(xdatamid)high=mid-1;elselow=mid+1;return-1;intmain(void)seqlist*L;L=(seqlist*)malloc(sizeof(seqlist);i

7、nta,b,c;initial_list(L);printf(你想创建有序的查找表(以-1结束):);scanf(%d,&x);while(x!=-1)list_creat(L);scanf(%d,&x);printf(请输入你想查找的数:);scanf(%d,&x);printf(顺序查找-你所要找数的下标号:);a=first_search(L);if(a=-1)printf(没有你所要查的数!);elseprintf(%d,a);printf(n);printf(倒序查找-你所要找数的下标号:);b=last_search(L);if(b=0)printf(没有你所要查的数!);else

8、printf(%d,b);printf(n);printf(折半查找-你所要找数的下标号:);c=bin_search(L);if(c=-1)printf(没有你所要查的数!);elseprintf(%d,c);printf(n);return0;(2)#include#include#includetypedefstructBTnodeintdata;structBTnode*lchild,*rchild;BTnode,*Bnode;voidinsert(Bnode&T,BnodeS)if(T=NULL)T=S;elseif(S-datadata)insert(T-lchild,S);els

9、einsert(T-rchild,S);voidcreate_bat(Bnode&T)Bnodeu;intx;T=NULL;printf(putanumber:);scanf(%d,&x);while(x!=-1)u=(BTnode*)malloc(sizeof(BTnode);u-data=x;u-lchild=NULL;u-rchild=NULL;insert(T,u);printf(putanumber:);scanf(%d,&x);Bnodebst_search(BnodeT,intx)if(T=NULL|T-data=x)returnT;elseif(T-data)x)returnbst_search(T-lchild,x);elsereturnbst_search(T-rchild,x);intmain()intx;BnodeT,p;printf(请先建立一棵二叉排序树:);printf(n);create_bat(T);printf(请输入你要查找的数字:);scanf(%d,&x);p=bst_search(T,x);if(p!=NULL)printf(已找到你