实验四——查找
一、实验目的
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 80
typedef 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认定为终止输入):"< 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; } } //输出学生信息 void print(seqlist L) { int i; cout<<"学生基本信息为:"< for(i=1;i<=L.num;i++) cout<<"\t"< } //顺序查找 int find(seqlist L,int number) { int i; for(i=L.num;i>=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 high=mid-1; else low=mid+1; } return 0; } void main() { int i,number; seqlist L; 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 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.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默认为结束输入):"< cout<<"学号"<<"\t姓名"<<"\t性别"<<"\t年龄"< cin>>number; while(number) { u=new bnode; u->inf.number=number; cin>>u->https://www.wendangku.net/doc/5518933574.html,>>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默认为结束输入):"< cout<<"学号"<<"\t姓名"<<"\t性别"<<"\t年龄"< cin>>number; while(number) { u=new bnode; u->inf.number=number; cin>>u->https://www.wendangku.net/doc/5518933574.html,>>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.查找学生信息"< cout<<"选择:"; cin>>choice; switch(choice) { case 1:{create(T);cout<<"成功建立!"< case 2:{insert1(T);cout<<"插入成功!"< case 3:{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来保存每次比较完之后的数组的下标。 在实验二中:二叉排序树中的创建树,输出一个要插入的学生信息,学号为主要关键字进行插入,首先进行比较在决定是插在左子树还是右子树。主要问题是如何一次保存学生的四个信息?这就要求在输入学生信息时候,要定义学号为关键字输入。在输入学生信息时候仍要调用插入函数对学生信息进行保存。 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程,是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法,介绍了常用的多种查找和排序技术,并做了性能分析和比较,内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: (1)内容丰富,学习量大,给学习带来困难; (2)贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点; (3)所用到的技术多,而在此之前的各门课程中所介绍的专业性知识又不多,因而加大了学习难度; (4)隐含在各部分的技术和方法丰富,也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性,设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练,突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时,觉得无从下手,做起来特别费劲。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程,理解和掌握算法设计所需的技术,为整个专业学习打好基础,要求运用所学知识,上机解决一些典型问题,通过分析、设计、编码、调试等各环节的训练,使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法,如算法设计的构思方法,动态链表,算法的编码,递归技术,与特定问题相关的技术等,要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上,掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时,要求完成以下六个题目: 实习一约瑟夫环问题(2学时) 物理实验报告格式范文 一、实验目的 二、实验仪器和器材(要求标明各仪器的规格型号) 三、实验原理:简明扼要地阐述实验的理论依据、计算公式、画出电路图或光路图 四、实验步骤或内容:要求步骤或内容简单明了 五、数据记录:实验中测得的原始数据和一些简单的结果尽可能用表格形式列出,并要求正确表示有效数字和单位 六、数据处理:根据实验目的对测量结果进行计算或作图表示,并对测量结果进行评定,计算误差或不确定度. 七、实验结果:扼要地写出实验结论 八、误差分析:当实验数据的误差达到一定程度后,要求对误差进行分析,找出产生误差的原因. 九、问题讨论:讨论实验中观察到的异常现象及可能的解释,分析实验误差的主要来源,对实验仪器的选择和实验方法的改进提出建议,简述自己做实验的心得体会,回答实验思考题. 物理探究实验:影响摩擦力大小的因素 技能准备:弹簧测力计,长木板,棉布,毛巾,带钩长方体木块,砝码,刻度尺,秒表。 知识准备: 1. 二力平衡的条件:作用在同一个物体上的两个力,如果大小相等,方向相反,并且在同一直线上,这两个力就平衡。 2. 在平衡力的作用下,静止的物体保持静止状态,运动的物体保持匀速直线运动状态。 3. 两个相互接触的物体,当它们做相对运动时或有相对运动的趋势时,在接触面上会产生一种阻碍相对运动的力,这种力就叫摩擦力。 4. 弹簧测力计拉着木块在水平面上做匀速直线运动时,拉力的大小就等于摩擦力的大小,拉力的数值可从弹簧测力计上读出,这样就测出了木块与水平面之间的摩擦力。 探究导引 探究指导: 关闭发动机的列车会停下来,自由摆动的秋千会停下来,踢出去的足球会停下来,运动的物体之所以会停下来,是因为受到了摩擦力。 运动物体产生摩擦力必须具备以下三个条件:1.物体间要相互接触,且挤压;2.接触面要粗糙;3.两物体间要发生相对运动或有相对运动的趋势。三个条件缺一不可。 摩擦力的作用点在接触面上,方向与物体相对运动的方向相反。由力的三要素可知:摩擦力除了有作用点、方向外,还有大小。 提出问题:摩擦力大小与什么因素有关? 猜想1:摩擦力的大小可能与接触面所受的压力有关。 猜想2:摩擦力的大小可能与接触面的粗糙程度有关。 猜想3:摩擦力的大小可能与产生摩擦力的两种物体间接触面积的大小有关。 探究方案: 用弹簧测力计匀速拉动木块,使它沿长木板滑动,从而测出木块与长木板之间的摩擦力;改变放在木块上的砝码,从而改变木块与长木板之间的压力;把棉布铺在长木板上,从而改变接触面的粗糙程度;改变木块与长木板的接触面,从而改变接触面积。 物理实验报告 .化学实验报告 .生物实验报告 .实验报告格式 .实验报告模板 探究过程: 1. 用弹簧测力计匀速拉动木块,测出此时木块与长木板之间的摩擦力:0.7N 2. 在木块上加50g的砝码,测出此时木块与长木板之间的摩擦力:0.8N 3. 在木块上加200g的砝码,测出此时木块与长木板之间的摩擦力:1.2N 4. 在木板上铺上棉布,测出此时木块与长木板之间的摩擦力:1.1N 5. 加快匀速拉动木块的速度,测出此时木块与长木板之间的摩擦力:0.7N 6. 将木块翻转,使另一个面积更小的面与长木板接触,测出此时木块与长木板之间的摩擦力:0.7N 探究结论: 《数据结构》实验报告排序实验题目: 输入十个数,从插入排序,快速排序,选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路: 1. 插入排序:直接插入排序的基本操作是,将一个记录到已排好序的有序表中,从而得到一个新的,记录增一得有序表。 一般情况下,第i 趟直接插入排序的操作为:在含有i-1 个记录的有序子序列r[1..i-1 ]中插入一个记录r[i ]后,变成含有i 个记录的有序子序列r[1..i ];并且,和顺序查找类似,为了在查找插入位置的过程中避免数组下标出界,在r [0]处设置哨兵。在自i-1 起往前搜索的过程中,可以同时后移记录。整个排序过程为进行n-1 趟插入,即:先将序列中的第一个记录看成是一个有序的子序列,然后从第2 个记录起逐个进行插入,直至整个序列变成按关键字非递减有序序列为止。 2. 快速排序:基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 假设待排序的序列为{L.r[s] ,L.r[s+1],…L.r[t]}, 首先任意选取一个记录 (通常可选第一个记录L.r[s])作为枢轴(或支点)(PiVOt ),然后按下述原则重新排列其余记录:将所有关键字较它小的记录都安置在它的位置之前,将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置i 作为界线,将序列{L.r[s] ,… ,L.r[t]} 分割成两个子序列{L.r[i+1],L.[i+2], …,L.r[t]}。这个过程称为一趟快速排序,或一次划分。 一趟快速排序的具体做法是:附设两个指针lOw 和high ,他们的初值分别为lOw 和high ,设枢轴记录的关键字为PiVOtkey ,则首先从high 所指位置起向前搜索找到第一个关键字小于PiVOtkey 的记录和枢轴记录互相交换,然后从lOw 所指位置起向后搜索,找到第一个关键字大于PiVOtkey 的记录和枢轴记录互相 交换,重复这两不直至low=high 为止。 具体实现上述算法是,每交换一对记录需进行3 次记录移动(赋值)的操作。而实际上, 数据结构实验报告 一.题目要求 1)编程实现二叉排序树,包括生成、插入,删除; 2)对二叉排序树进行先根、中根、和后根非递归遍历; 3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么? 二.解决方案 对于前三个题目要求,我们用一个程序实现代码如下 #include 云南大学软件学院数据结构实验报告 (本实验项目方案受“教育部人才培养模式创新实验区(X3108005)”项目资助)实验难度: A □ B □ C □ 学期:2010秋季学期 任课教师: 实验题目: 查找算法设计与实现 姓名: 王辉 学号: 20091120154 电子邮件: 完成提交时间: 2010 年 12 月 27 日 云南大学软件学院2010学年秋季学期 《数据结构实验》成绩考核表 学号:姓名:本人承担角色: 综合得分:(满分100分) 指导教师:年月日(注:此表在难度为C时使用,每个成员一份。) (下面的内容由学生填写,格式统一为,字体: 楷体, 行距: 固定行距18,字号: 小四,个人报告按下面每一项的百分比打分。难度A满分70分,难度B满分90分)一、【实验构思(Conceive)】(10%) 1 哈希表查找。根据全年级学生的姓名,构造一个哈希表,选择适当的哈希函数和解决冲突的方法,设计并实现插入、删除和查找算法。 熟悉各种查找算法的思想。 2、掌握查找的实现过程。 3、学会在不同情况下运用不同结构和算法求解问题。 4 把每个学生的信息放在结构体中: typedef struct //记录 { NA name; NA tel; NA add; }Record; 5 void getin(Record* a)函数依次输入学生信息 6 人名折叠处理,先将用户名进行折叠处理折叠处理后的数,用除留余数法构造哈希函数,并返回模值。并采用二次探测再散列法解决冲突。 7姓名以汉语拼音形式,待填入哈希表的人名约30个,自行设计哈希函数,用线性探测再散列法或链地址法处理冲突;在查找的过程中给出比较的次数。完成按姓名查询的操作。将初始班级的通讯录信息存入文件。 二、【实验设计(Design)】(20%) (本部分应包括:抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明,主程序模块与各子程序模块间的调用关系) 1抽象数据类型的功能规格说明和结构体: #include 实验报告格式范文 实验一撰写可行性研究报告 一、实验目的 1、掌握可行性研究步骤; 2、学习编制可行性研究报告。 二、实验要求 硬件:Intel Pentium 120 或以上级别的CPU,大于16MB的内存。 软件:Win dows 95/98/2000 操作系统,Office 97/2000 软件 学时:2学时 写岀此项实验报告 三、实验内容 1、可行性研究(结构化分析)方法; 2、绘制数据流图,使用Word写实验报告。 四、实验步骤 1 ?引言 1.1 编写目的 可行性研究的目的是为了对问题进行研究,以最小的代价在最短的时间内确定问题是否可解。 经过对此项目进行详细调查研究,初拟系统实现报告,对软件开发中将要面临的问题及其解决方案进行初步设计及合理安排。明确开发风险及其所带来的经济效益。本报告经审核后,交软件经理审查。 1 . 2 项目背景 (1 )待开发的软件产品名称:旅行社机票预定系统。 (2)本项目的提岀者:冯剑。开发者:李翀。用户:旅行社 (3)本软件产品将用于旅行社的机票预定和费用的记录。 1 . 3术语说明 DFD (数据流图):一种描述书记变换的图形工具,是结构化分析方法最普遍采用的表示手段,但数据流图并不是结构化分析模型的全部,数据字典和小说明为数据流图提供了补充,并用以验证图形表示的正确性、一致性和完整性,三者共同构成了被建系统的模型。 1 . 4.系统参考文献 参考文献见附录 2?可行性研究的前提 2.1基本要求 ⑴功能 本软件实现的功能有:为游客提供机票预定服务,提高旅游局的服务质量和服务效率。 对航班数据库的查询和修改,对机票费用记帐数据库的查询和修改,记录旅客信息(姓名、性别、年龄、身份证号、单位、旅行时间、目的地)、航班时间和班次,打印机票和帐单。 (2) 性能 时间:提供的信息必须及时的反映在工作平台上。售票系统的定单必须无差错的存 储在机场的主服务器上。对服务器上的数据必须进行及时正确的刷新。一笔业务在一分钟内完成。空间:运行空间 2M。 (3) 系统的输入和输岀 输入:旅行社定票单。数据完整,详实。 输岀:机票、帐单。简捷,快速,实时。 (4) 处理流程 旅行社将定票信息输入定票系统,系统输岀机票和帐单给旅客。 5 )安全保密要求 电子科技大学实验报告 课程名称:数据结构与算法 学生姓名: 学号: 点名序号: 指导教师: 实验地点:基础实验大楼 实验时间: 5月20日 2014-2015-2学期 信息与软件工程学院数据结构实验报告格式
物理实验报告格式范文
《数据结构》实验报告——排序.docx
数据结构实验报告
数据结构实验报告七查找、
实验报告格式范文
实验报告-排序与查找