查找实验报告

《查找实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、igh=n-1;//初始化查找区域while(low<=high){mid=(low+high)/2;if(x==A[mid].keyreturnmid;elseif(xhigh)return-1;//查找失败else{mid=(low+high)/2;//求解中间元素的下标if(x==A[mid].key)returnmid;

3、//查找成功elseif(x

4、。voidinsert(Bnode*&T,Bnode*S)//将指针S所指结点插入到二叉排序树T中{if(T==NULL)T=S;//插入到空树时，插入结点成为根结点elseif(S->keykey)insert(T->lchild,S);//插入到T的左子树中elseinsert(T->rchild,S);//插入到T的右子树中}3）请写出二叉排序树构造的算法。voidcreate_bst(Bnode*&T);//通过插入结点构造二叉排序树的算法{Bnode*u;elementtypex;T=NULL;cin>>x;//初始化根指针并读入第一个元素值While(x!=end_of_

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

6、hild;//到右子树中继续查找returnp;//返回结果可能为空，也可能非空}递归算法：Bnode*bst_search(Bnode*T,keytypex){if(T==NULL

7、

8、t->key=x)returnT;//子树为空或已经找到时均可结束elseif(xkey)returnbst_search(T->lchild,x);//左子树中查找的结果就是函数的结果elsereturnbst_search(T->rchild,x);//右子树中查找的结果就是函数的结果}一、上机实验1.实验内容。1）建立一个顺序表，用顺序查找的方法对其实施查找；2）建立一个有序表，用折半查找的方法

9、对其实施查找；3）建立一个二叉排序树，根据给定值对其实施查找；4）对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。2.实验源程序。(1)#include#include#definemax100intx;typedefstruct{intdata[max];intlistlen;}seqlist;voidinitial_list(seqlist*L){L-