查找实验报告

1、实验报告姓院（系课程名称：专业 /年级：实验四查找一、实验目的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

2、=0,high=n-1;/初始化查找区域while(low<=high) mid=(low+high)/2;精品文库if(x=Amid.key return mid;else if(x<Amid.key)high=mid-1;else low=mid+1;return -1;/返回查找失败的标志(2) 递归算法int bin_search(elementtype A,int low,int high,keytype x) int mid;if( low>high) return -1;/查找失败else mid=(low+high)/2;/求解中间元素的下标if( x=Ami

3、d.key ) return mid;/查找成功else if( x<Amid.key )return bin_search(A,low,mid-1,x);/将在左边区域查找的结果作为在整个区域的查找结果返回else return bin_search(A,mid+1,high,x);/将在右边区域查找的结果作为在整个区域的查找结果返回欢迎下载2精品文库3. 二叉排序树查找算法：1）请写出二叉排序树结点的结构体定义语句。typedef char datatype;typedef struct node keytype key; datatype data;struct node * lc

4、hild, *rchild;BSTnode;2）请写出二叉排序树中插入结点的算法。void insert (Bnode *&T,Bnode *S)/将指针 S 所指结点插入到二叉排序树T 中if (T=NULL)T=S;/插入到空树时，插入结点成为根结点else if (S->key<T->key)insert (T->lchild,S);/插入到 T 的左子树中else insert(T->rchild,S);/插入到 T 的右子树中3）请写出二叉排序树构造的算法。void create_bst(Bnode *&T);/通过插入结点构造二叉排序树

5、的算法Bnode * u;elementtype x;T=NULL;cin>>x;/ 初始化根指针并读入第一个元素值欢迎下载3精品文库While (x!=end_of_num)/x 不是结束符时u=new Bnode; u->data=x;/产生新结点并装入数据u->lchild=NILL;u->rchild=NULL;/设置左、右孩子指针为空insert (T,u);/插入结点到二叉排序树T 中cin>>x;/ 读入下一个元素的值4）请写出二叉排序树查找的算法。非递归算法：Bnode * bst_search(Bnode * T,keytype x)

6、Bnode * P=T;/P 指向根while (p!=NULL)if( x=p->key) return p;/查找成功else if( x<p->key=p->lchild);/到左子树中继续查找elsep=p->rchild;/ 到右子树中继续查找return p;/ 返回结果可能为空，也可能非空欢迎下载4精品文库递归算法：Bnode * bst_search(Bnode * T,keytype x)if (T=NULL | t->key=x)return T;/ 子树为空或已经找到时均可结束elseif(x<T->key)return b

7、st_search(T->lchild, x);/左子树中查找的结果就是函数的结果elsereturn bst_search(T->rchild, x);/右子树中查找的结果就是函数的结果三、上机实验1. 实验内容。1）建立一个顺序表，用顺序查找的方法对其实施查找；2）建立一个有序表，用折半查找的方法对其实施查找；3）建立一个二叉排序树，根据给定值对其实施查找；4）对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。2. 实验源程序。(1)#include <stdio.h>#include <stdlib.h>#define max 100欢迎

8、下载5精品文库int 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;欢迎下载6精品文库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_sea

9、rch(seqlist *L)int i,n;n=L->listlen;for(i=1;i<=n;i+)欢迎下载7精品文库if(L->datai=x)return i;return -1;int bin_search(seqlist *L)int mid,low=1,high=L->listlen;while(low<=high)mid=(low+high)/2;if(x=L->datamid)return mid;else if(x<=L->datamid)high=mid-1;else欢迎下载8精品文库low=mid+1;return -1;

10、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);欢迎下载9精品文库printf(" 请输入你想查找的数 :");scanf("%d",&x);printf(" 顺序

11、查找 -你所要找数的下标号 :");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(" 折半查找 -你所

12、要找数的下标号 :");c=bin_search(L);欢迎下载10精品文库if(c=-1)printf(" 没有你所要查的数 !");elseprintf("%d",c);printf("n");return 0;(2)#include<stdio.h>#include<string.h>#include<stdlib.h>typedef struct BTnodeint data;struct BTnode *lchild,*rchild; BTnode,*Bnode;欢迎下载11精品

13、文库void insert(Bnode &T,BnodeS)if(T=NULL)T=S;else if(S->data<T->data)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)欢迎下载12精品文库u=(BTnode*)malloc(sizeof(BTnode);

14、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->lchild,x);elsereturn bst_search(T->rchild,x);欢迎下载13精品文库int main()int x;Bnode T,p;printf(" 请先建立一棵二叉排序树:");printf("n");create_bat(T);printf(" 请输入你要查找的数字 :");scanf("%d",&x);p=bst_search(T,x);if(p!=NULL)printf(" 已找到你要查找的数 !")