欢迎来到天天文库
浏览记录
ID:49546263
大小:167.00 KB
页数:20页
时间:2020-03-02
《查找实验报告.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(x4、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;elementtype5、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==NULL7、8、t->key=x)returnT;//子树为空或已经找到时均可结束elseif(xkey)returnbst_search(T->lchild,x);//左子树中查找的结果就是函数的结果elsereturnbst_search(T->rchild,x9、);//右子树中查找的结果就是函数的结果}一、上机实验1.实验内容。1)建立一个顺序表,用顺序查找的方法对其实施查找;2)建立一个有序表,用折半查找的方法对其实施查找;3)建立一个二叉排序树,根据给定值对其实施查找;4)对同一组数据,试用三种方法查找某一相同数据,并尝试进行性能分析。2.实验源程序。(1)#include#include#definemax100范文..intx;typedefstruct{intdata[max];intlistlen;}seqlist;voidiniti
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
此文档下载收益归作者所有