《数据结构》实验报告查找.doc
- 文档编号:2790808
- 上传时间:2023-05-04
- 格式:DOC
- 页数:9
- 大小:213KB
《数据结构》实验报告查找.doc
《《数据结构》实验报告查找.doc》由会员分享,可在线阅读,更多相关《《数据结构》实验报告查找.doc(9页珍藏版)》请在冰点文库上搜索。
《数据结构》实验班级:
学号:
姓名:
实验四——查找
一、实验目的
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.实验源程序。
#include
#defineN80
typedefstruct
{
intnumber;//关键字
charname[5];
charsex[2];
intage;
}record;
typedefstruct
{
recordstu[N];
intnum;//记录人数
}seqlist;
//建顺序表
voidcreate(seqlist&L)
{
inti;
L.num=0;
cout<<"请依次输入(输入学号为0认定为终止输入):
"< cout<<"学号"<<"\t姓名"<<"\t性别"<<"\t年龄"< cin>>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< cin>>L.stu[++i].number; } } //输出学生信息 voidprint(seqlistL) { inti; cout<<"学生基本信息为: "< for(i=1;i<=L.num;i++) cout<<"\t"< } //顺序查找 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; else if(number high=mid-1; else low=mid+1; } return0; } voidmain() { inti,number; seqlistL; create(L); print(L); cout<<"折半查找: "< cout<<"输入学生学号: "; cin>>number; if((i=halffind(L,number))! =0) cout<<"\t"< else cout<<"失败! "< cout<<"顺序查找: "< cout<<"输入学生学号: "; cin>>number; if((i=find(L,number))! =0) cout<<"\t"< else cout<<"失败! "< } 实验二: #include typedefstruct { intnumber;//关键字 charname[5]; charsex[2]; intage; }record; typedefstructnode { recordinf; structnode*lchild,*rchild; }bnode; voidinsert(bnode*&T,bnode*S) { if(! T) T=S; else if(S->inf.number insert(T->lchild,S); else insert(T->rchild,S); } voidinsert1(bnode*&T) { intflag=1;intnumber;bnode*u;charctinue; for(;flag==1;) { cout<<"依次输入(学号为0默认为结束输入): "< cout<<"学号"<<"\t姓名"<<"\t性别"<<"\t年龄"< cin>>number; while(number) { u=newbnode; 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; } } voidcreate(bnode*&T) { bnode*u; intnumber; T=NULL; cout<<"依次输入(学号为0默认为结束输入): "< cout<<"学号"<<"\t姓名"<<"\t性别"<<"\t年龄"< cin>>number; while(number) { u=newbnode; 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,intnumber) { if(T==NULL||T->inf.number==number) returnT; else if(T->inf.number>number) returnsearch(T->lchild,number); else returnsearch(T->rchild,number); } voidmain() { intnumber,flag=1,choice;charctinue; bnode*T,*p; for(;flag==1;) { cout<<"\t1.建立二叉排序树"<<"\n\t2.插入学生信息"<<"\n\t3.查找学生信息"< cout<<"选择: "; cin>>choice; switch(choice) { case1: {create(T);cout<<"成功建立! "< case2: {insert1(T);cout<<"插入成功! "< case3: {cout<<"输入待查学生的学号: ";cin>>number;p=search(T,number); if(p) cout< else cout<<"查找失败! "< } cout<<"Continue(Y/N): "; cin>>ctinue; if(ctinue=='y'||ctinue=='y') flag=1; else flag=0; } } 2.实验结果(截图)。 实验一: 开始界面: 插入数据界面: 查找信息的界面; 实验二: 开始界面: 建立二叉树: 插入学生的信息: 查找学生信息: 再次插入学生信息: 五、实验总结(实验过程中出现的问题、解决方法、结果或其它) 在实验一中: 创建的学生信息包含四个方面: 学号,姓名,性别,年龄。 要分别定义四个数组来保存它们。 其中要将学生的学号定义为查找的关键字。 顺序查找按学号就可以,在折半查找中,我们需要定义high和low来保存每次比较完之后的数组的下标。 在实验二中: 二叉排序树中的创建树,输出一个要插入的学生信息,学号为主要关键字进行插入,首先进行比较在决定是插在左子树还是右子树。 主要问题是如何一次保存学生的四个信息? 这就要求在输入学生信息时候,要定义学号为关键字输入。 在输入学生信息时候仍要调用插入函数对学生信息进行保存。 8
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告 查找