搜索
《数据结构》实验班级：学号：姓名：1实验四——查找一、实验目的1.掌握顺序表的查找方法，尤其是折半查找方法；2.掌握二叉排序树的查找算法。二、实验内容1.建立一个顺序表，用顺序查找的方法对其实施查找；2.建立一个有序表，用折半查找的方法对其实施查找；3.建立一个二叉排序树，根据给定值对其实施查找；4.对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。三、实验预习内容实验一包括的函数有：typedefstruct，创建函数voidcreate(seqlist&L)，输出函数voidprint(seqlistL)，顺序查找intfind(seqlistL,intnumber)，折半查找inthalffind(seqlistL,intnumber)主函数main().实验二包括的函数有：结构体typedefstruct，插入函数voidinsert(bnode*&T,bnode*S)，voidinsert1(bnode*&T)，创建函数voidcreate(bnode*&T)，查找函数bnode*search(bnode*T,intnumber)，主函数main().四、上机实验实验一：1.实验源程序。#includeiostream.h#defineN80typedefstruct{intnumber;//关键字charname[5];charsex[2];intage;}record;typedefstruct{recordstu[N];intnum;//记录人数}seqlist;//建顺序表voidcreate(seqlist&L){inti;《数据结构》实验班级：学号：姓名：2L.num=0;cout请依次输入(输入学号为0认定为终止输入):endl;cout学号\t姓名\t性别\t年龄endl;cinL.stu[1].number;for(i=1;L.stu[i].number!=0;){cinL.stu[i].nameL.stu[i].sexL.stu[i].age;L.num++;coutendl;cinL.stu[++i].number;}}//输出学生信息voidprint(seqlistL){inti;cout学生基本信息为:endl;for(i=1;i=L.num;i++)cout\tL.stu[i].number\tL.stu[i].name\tL.stu[i].sex\tL.stu[i].ageendl;}//顺序查找intfind(seqlistL,intnumber){inti;for(i=L.num;i=0;i--)if(L.stu[i].number==number)returni;}//折半查找inthalffind(seqlistL,intnumber){inthigh=L.num,low=1,mid;for(;low=high;){mid=(high+low)/2;if(number==L.stu[mid].number)returnmid;elseif(numberL.stu[mid].number)《数据结构》实验班级：学号：姓名：3high=mid-1;elselow=mid+1;}return0;}voidmain(){inti,number;seqlistL;create(L);print(L);cout折半查找:endl;cout输入学生学号:;cinnumber;if((i=halffind(L,number))!=0)cout\tL.stu[i].number\tL.stu[i].name\tL.stu[i].sex\tL.stu[i].ageendl;elsecout失败!endl;cout顺序查找:endl;cout输入学生学号:;cinnumber;if((i=find(L,number))!=0)cout\tL.stu[i].number\tL.stu[i].name\tL.stu[i].sex\tL.stu[i].ageendl;elsecout失败!endl;}实验二：#includeiostream.htypedefstruct{intnumber;//关键字charname[5];charsex[2];intage;}record;《数据结构》实验班级：学号：姓名：4typedefstructnode{recordinf;structnode*lchild,*rchild;}bnode;voidinsert(bnode*&T,bnode*S){if(!T)T=S;elseif(S-inf.numberT-inf.number)insert(T-lchild,S);elseinsert(T-rchild,S);}voidinsert1(bnode*&T){intflag=1;intnumber;bnode*u;charctinue;for(;flag==1;){cout依次输入(学号为0默认为结束输入):endl;cout学号\t姓名\t性别\t年龄endl;cinnumber;while(number){u=newbnode;u-inf.number=number;cinu-inf.nameu-inf.sexu-inf.age;u-lchild=u-rchild=NULL;insert(T,u);cinnumber;}cout继续插入(Y/N):;cinctinue;if(ctinue=='y'||ctinue=='y')flag=1;elseflag=0;}}voidcreate(bnode*&T)《数据结构》实验班级：学号：姓名：5{bnode*u;intnumber;T=NULL;cout依次输入(学号为0默认为结束输入):endl;cout学号\t姓名\t性别\t年龄endl;cinnumber;while(number){u=newbnode;u-inf.number=number;cinu-inf.nameu-inf.sexu-inf.age;u-lchild=u-rchild=NULL;insert(T,u);cinnumber;}}bnode*search(bnode*T,intnumber){if(T==NULL||T-inf.number==number)returnT;elseif(T-inf.numbernumber)returnsearch(T-lchild,number);elsereturnsearch(T-rchild,number);}voidmain(){intnumber,flag=1,choice;charctinue;bnode*T,*p;for(;flag==1;){cout\t1.建立二叉排序树\n\t2.插入学生信息\n\t3.查找学生信息endl;cout选择:;cinchoice;switch(choice){case1:{create(T);cout成功建立!endl;};break;case2:{insert1(T);cout插入成功!endl;};break;case3:{cout输入待查学生的学号:;cinnumber;p=search(T,number);if(p)《数据结构》实验班级：学号：姓名：6coutp-inf.number\tp-inf.name\tp-inf.sex\tp-inf.ageendl;elsecout查找失败!endl;};break;}coutContinue(Y/N):;cinctinue;if(ctinue=='y'||ctinue=='y')flag=1;elseflag=0;}}2.实验结果（截图）。实验一：开始界面：插入数据界面：《数据结构》实验班级：学号：姓名：7查找信息的界面;实验二：开始界面：建立二叉树：《数据结构》实验班级：学号：姓名：8插入学生的信息：查找学生信息：再次插入学生信息：《数据结构》实验班级：学号：姓名：9五、实验总结（实验过程中出现的问题、解决方法、结果或其它）在实验一中：创建的学生信息包含四个方面：学号，姓名，性别，年龄。要分别定义四个数组来保存它们。其中要将学生的学号定义为查找的关键字。顺序查找按学号就可以，在折半查找中，我们需要定义high和low来保存每次比较完之后的数组的下标。在实验二中：二叉排序树中的创建树，输出一个要插入的学生信息，学号为主要关键字进行插入，首先进行比较在决定是插在左子树还是右子树。主要问题是如何一次保存学生的四个信息？这就要求在输入学生信息时候，要定义学号为关键字输入。在输入学生信息时候仍要调用插入函数对学生信息进行保存。