查找实验报告.doc

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

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){int

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

3、(x==A[mid].key)returnmid;//查找成功elseif(x

4、ild,*rchild;}BSTnode;2）请写出二叉排序树中插入结点的算法。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;elementtype

5、x;T=NULL;cin>>x;//初始化根指针并读入第一个元素值范文..While(x!=end_of_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)

6、returnp;//查找成功elseif(xkey=p->lchild);//到左子树中继续查找elsep=p->rchild;//到右子树中继续查找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

9、);//右子树中查找的结果就是函数的结果}一、上机实验1.实验内容。1）建立一个顺序表，用顺序查找的方法对其实施查找；2）建立一个有序表，用折半查找的方法对其实施查找；3）建立一个二叉排序树，根据给定值对其实施查找；4）对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。2.实验源程序。(1)#include#include#definemax100范文..intx;typedefstruct{intdata[max];intlistlen;}seqlist;voidiniti