实验报告 姓 课程名称： 院（系 专业/年级：实验四 查找一、 实验目的1. 掌握顺序表的查找方法，尤其是折半查找方法；2. 掌握二叉排序树的查找算法。二、 实验预习内容请在上机前认真阅读教材及实验指导书，并在以下空白处填写相应的内容。1. 请写出简单顺序查找算法。int seq_search(elementtype A,int n, keytype x) i=n;A0.key=x; while(Ai.key=x) i-； return i;2. 请写出有序表二分（折半）查找算法。(1) 非递归算法int bin_search(elementtype A,int n,keytype x) int mid,low=0,high=n-1; /初始化查找区域 while(low=high) mid=(low+high)/2; if(x=Amid.key return mid; else if(xhigh) return -1;/查找失败 else mid=(low+high)/2;/求解中间元素的下标 if( x=Amid.key ) return mid;/查找成功 else if( xkeykey) insert (T-lchild,S); /插入到T的左子树中 else insert(T-rchild,S); /插入到T的右子树中 3）请写出二叉排序树构造的算法。void create_bst(Bnode *&T); /通过插入结点构造二叉排序树的算法 Bnode * u;elementtype x; T=NULL;cinx; /初始化根指针并读入第一个元素值 While (x!=end_of_num) /x不是结束符时 u=new Bnode; u-data=x; /产生新结点并装入数据 u-lchild=NILL;u-rchild=NULL; /设置左、右孩子指针为空 insert (T,u); /插入结点到二叉排序树T中 cinx; /读入下一个元素的值 4） 请写出二叉排序树查找的算法。 非递归算法：Bnode * bst_search(Bnode * T,keytype x) Bnode * P=T; /P指向根 while (p!=NULL) if( x=p-key) return p; /查找成功 else if( xkey=p-lchild); /到左子树中继续查找 else p=p-rchild; /到右子树中继续查找 return p; /返回结果可能为空，也可能非空递归算法：Bnode * bst_search(Bnode * T,keytype x) if (T=NULL | t-key=x) return T; /子树为空或已经找到时均可结束 else if(xkey) return bst_search(T-lchild, x); /左子树中查找的结果就是函数的结果 else return bst_search(T-rchild, x); /右子树中查找的结果就是函数的结果三、 上机实验1. 实验内容。1）建立一个顺序表，用顺序查找的方法对其实施查找；2）建立一个有序表，用折半查找的方法对其实施查找；3）建立一个二叉排序树，根据给定值对其实施查找；4） 对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。2. 实验源程序。(1)#include #include #define max 100int x;typedef structint datamax;int listlen;seqlist;void initial_list(seqlist *L)L-listlen=0;void list_creat(seqlist *L)int i;L-listlen+;i=L-listlen;L-datai=x;int last_search(seqlist *L)int i;i=L-listlen;L-data0=x;while(L-datai!=x)i-;return i;int first_search(seqlist *L)int i,n;n=L-listlen;for(i=1;idatai=x)return i;return -1;int bin_search(seqlist *L)int mid,low=1,high=L-listlen;while(lowdatamid)return mid;else if(xdatamid)high=mid-1;elselow=mid+1;return -1;int main(void)seqlist *L;L=(seqlist*)malloc(sizeof(seqlist);int a,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(没有你所要查的数!);elseprintf(%d,b); printf(n); printf(折半查找-你所要找数的下标号:); c=bin_search(L); if(c=-1)printf(没有你所要查的数!);elseprintf(%d,c); printf(n);return 0;(2)#include#include#includetypedef struct BTnodeint data;struct BTnode *lchild,*rchild; BTnode,*Bnode;void insert(Bnode &T,Bnode S)if(T=NULL)T=S;else if(S-datadata)insert(T-lchild,S); else insert(T-rchild,S);void create_bat(Bnode &T)Bnode u;int x;T=NULL;printf(put a number:);scanf(%d,&x);while(x!=-1)u=(BTnode*)malloc(sizeof(BTnode);u-data=x;u-lchild=NULL;u-rchild=NULL;insert(T,u); printf(put a number:); scanf(%d,&x);Bnode bst_search(Bnode T,int x)if(T=NULL|T-data=x)return T;else if(T-data)x) return bst_search(T-lc