实验四 ——查找一、 实验目的1. 掌握顺序表的查找方法，尤其是折半查找方法；2. 掌握二叉排序树的查找算法二、 实验内容1. 建立一个顺序表，用顺序查找的方法对其实施查找；2. 建立一个有序表，用折半查找的方法对其实施查找；3. 建立一个二叉排序树，根据给定值对其实施查找；4. 对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析三、 实验预习内容实验一包括的函数有：typedef struct ，创建函数void create(seqlist & L)，输出函数void print(seqlist L)，顺序查找int find(seqlist L,int number)，折半查找int halffind(seqlist L,int number)主函数main().实验二包括的函数有：结构体typedef struct， 插入函数void insert(bnode * & T,bnode * S)，void insert1(bnode * & T)，创建函数void create(bnode * & T)，查找函数bnode * search(bnode * T,int number)，主函数main().四、 上机实验实验一：1. 实验源程序。
include#define N 80typedef struct { int number; //关键字 char name[5]; char sex[2]; int age;}record;typedef struct{ record stu[N]; int num;//记录人数}seqlist;//建顺序表void create(seqlist & L){ int i; L.num=0; cout<<"请依次输入(输入学号为0认定为终止输入):"<>L.stu[1].number; for(i=1;L.stu[i].number!=0;) { cin>>L.stu[i].name>>L.stu[i].sex>>L.stu[i].age; L.num++; cout<>L.stu[++i].number; }}//输出学生信息void print(seqlist L){ int i; cout<<"学生基本信息为:"<=0;i--) if(L.stu[i].number==number) return i;}//折半查找int halffind(seqlist L,int number){ int high=L.num,low=1,mid; for(;low<=high;) { mid=(high+low)/2; if(number==L.stu[mid].number) return mid; else if(number>number; if((i=halffind(L,number))!=0) cout<<"\t"<>number; if((i=find(L,number))!=0) cout<<"\t"<typedef struct { int number; //关键字 char name[5]; char sex[2]; int age;}record;typedef struct node{ record inf; struct node *lchild,*rchild;}bnode;void insert(bnode * & T,bnode * S){ if(!T) T=S; else if(S->inf.numberinf.number) insert(T->lchild,S); else insert(T->rchild,S);}void insert1(bnode * & T){ int flag=1; int number; bnode * u; char ctinue; for(;flag==1;) { cout<<"依次输入(学号为0默认为结束输入):"<>number; while(number) { u=new bnode; u->inf.number=number; cin>>u->inf.name>>u->inf.sex>>u->inf.age; u->lchild=u->rchild=NULL; insert(T,u); cin>>number; } cout<<"继续插入(Y/N):"; cin>>ctinue; if(ctinue=='y'||ctinue=='y') flag=1; else flag=0; }}void create(bnode * & T){ bnode * u; int number; T=NULL; cout<<"依次输入(学号为0默认为结束输入):"<>number; while(number) { u=new bnode; u->inf.number=number; cin>>u->inf.name>>u->inf.sex>>u->inf.age; u->lchild=u->rchild=NULL; insert(T,u); cin>>number; }}bnode * search(bnode * T,int number){ if(T==NULL||T->inf.number==number) return T; else if(T->inf.number>number) return search(T->lchild,number); else return search(T->rchild,number);}void main(){ int number,flag=1,choice; char ctinue; bnode * T,*p; for(;flag==1;) { cout<<"\t1.建立二叉排序树"<<"\n\t2.插入学生信息"<<"\n\t3.查找学生信息"<>choice; switch(choice) { case 1:{create(T);cout<<"成功建立!"<>number;p=search(T,number); if(p) cout<inf.number<<"\t"<inf.name<<"\t"<inf.sex<<"\t"<inf.age<>ctinue; if(ctinue=='y'||ctinue=='y') flag=1; else flag=0; } }2. 实验结果（截图）。
实验一：开始界面：插入数据界面：查找信息的界面;实验二：开始界面：建立二叉树：插入学生的信息：查找学生信息：再次插入学生信息：五、 实验总结（实验过程中出现的问题、解决方法、结果或其它） 在实验一中：创建的学生信息包含四个方面：学号，姓名，性别，年龄要分别定义四个数组来保存它们其中要将学生的学号定义为查找的关键字顺序查找按学号就可以，在折半查找中，我们需要定义high和low来保存每次比较完之后的数组的下标 在实验二中：二叉排序树中的创建树，输出一个要插入的学生信息，学号为主要关键字进行插入，首先进行比较在决定是插在左子树还是右子树主要问题是如何一次保存学生的四个信息？这就要求在输入学生信息时候，要定义学号为关键字输入在输入学生信息时候仍要调用插入函数对学生信息进行保存。