查找实验报告.doc

实验报告 姓 课程名称： 院（系 专业/年级： 实验四 ——查找 实验目的 掌握顺序表的查找方法，尤其是折半查找方法； 掌握二叉排序树的查找算法。 实验预习内容 请在上机前认真阅读教材及实验指导书，并在以下空白处填写相应的内容。 请写出简单顺序查找算法。 int seq_search(elementtype A[],int n, keytype x) { i=n;A[0].key=x; while(A[i].key=x) i--； return i; } 请写出有序表二分（折半）查找算法。 非递归算法 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==A[mid].key return mid; else if(xA[mid.key])high=mid-1; else low=mid+1; } return -1; //返回查找失败的标志 } 递归算法 int bin_search(elementtype A[],int low,int high,keytype x) { int mid; if( lowhigh) return -1;//查找失败 else { mid=(low+high)/2;//求解中间元素的下标 if( x==A[mid].key ) return mid;//查找成功 else if( xA[mid].key ) return bin_search(A,low,mid-1,x);//将在左边区域查找的结果作为在整个区域的查找结果返回 else return bin_search(A,mid+1,high,x); //将在右边区域查找的结果作为在整个区域的查找结果返回 } } 二叉排序树查找算法： 请写出二叉排序树结点的结构体定义语句。 typedef char datatype; typedef struct node { keytype key; datatype data; struct node * lchild, *rchild; }BSTnode; 2）请写出二叉排序树中插入结点的算法。 void insert (Bnode *T,Bnode *S) //将指针S所指结点插入到二叉排序树T中 { if (T==NULL) T=S; //插入到空树时，插入结点成为根结点 else if (S-keyT-key) 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; //读入下一个元素的值 } } 请写出二叉排序树查找的算法。 非递归算法： Bnode * bst_search(Bnode * T,keytype x) { Bnode * P=T; //P指向根 while (p!=NULL)