查找、排序的应用 实验报告
实验七查找、排序的应用
一、实验目的
1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。
2、学会比较各种排序与查找算法的优劣。
3、学会针对所给问题选用最适合的算法。
4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。
二、实验内容
[问题描述]
对学生的基本信息进行管理。
[基本要求]
设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1．总成绩要求自动计算；
2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）；
3．排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。
[测试数据]
由学生依据软件工程的测试技术自己确定。
三、实验前的准备工作
1、掌握哈希表的定义，哈希函数的构造方法。
2、掌握一些常用的查找方法。
1、掌握几种常用的排序方法。
2、掌握直接排序方法。
四、实验报告要求
1、实验报告要按照实验报告格式规范书写。
2、实验上要写出多批测试数据的运行结果。
3、结合运行结果，对程序进行分析。
五、算法设计
a、折半查找
设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时，令low=1,high=n,mid=(low+high)/2，让key与mid指向的记录比较，
若key==r[mid].key，查找成功
若key 若key>r[mid].key，则low=mid+1 重复上述操作，直至low>high时，查找失败 b、顺序查找 从表的一端开始逐个进行记录的关键字和给定值的比较。在这里从表尾开始并把下标为0的作为哨兵。 void chaxun(SqList &ST) uehao<[j-1].xuehao) { LI=[j]; [j]=[j-1]; [j-1]=LI; } int a=0; cout<<"输入要查找的学号"< cin>>n; int low,high,mid; low=0;high=; uehao) { cout<<[mid].xuehao<<" "<<[mid].xingming<<" "<<[mid].xingbei<<" "<<[mid].chengji1<<" "<<[mid].chengji2<<" "<<[mid].zong< a=1; break; } else if(n<[mid].xuehao ) high=mid-1; ingming) { cout<<[i].xuehao<<" "<<[i].xingming<<" "<<[i].xingbei<<" "<<[i].chengji1<<" "<<[i].chengji2<<" "<<[i].zong< a=1; } 1、插入排序 每步将一个待排序的记录，按其关键码大小，插入到前面已经排好序的一组记录的适当位置上，直到记录全部插入为止。 uehao<[j-1].xuehao) { LI=[j]; [j]=[j-1]; [j-1]=LI;} 2、选择排序 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换 重复上述操作，共进行n-1趟排序后，排序结束。 hengji1>[j].chengji1) {LI=[j]; [j]=[i]; [i]=LI; 六、运行测试结果输入学生信息 以多种方式进行查找 按总成绩进行排序 六、实验总结 通过本次实验我对查找排序的应用有了一定得了解，知道了各种查找排序的基本知识。同时，通过自己数次的调试、修改也搞懂了许多以前比较模糊的知识点，比如这次的界面是复制过来的，其中很多语句经过同学的讲解都理解了。但这次实验也有很多不尽人意的地方，我将在以后多学习同学优秀的地方．也会在以后的学习过程中要尽量考虑周全，使程序更有实用价值，提高编程能力。 七、源代码 #include using namespace std; #include #define MAXSIZE 100 uehao; cout<<"姓名"< cin>>[i].xingming; cout<<"性别"< cin>>[i].xingbei; cout<<"成绩1"< cin>>[i].chengji1; cout<<"成绩2"< cin>>[i].chengji2; } cout<<"输入完毕"< } void zong(SqList &ST) ong=[i].chengji1+[i].chengji2; } } void shuchu(SqList &ST)uehao<<" "<<[i].xingming<<" "<<[i].xingbei<<" "<<[i].chengji1<<" "<<[i].chengji2<<" " <<[i].zong<<" "< } } void chaxun(SqList &ST) uehao<[j-1].xuehao) { LI=[j]; [j]=[j-1]; [j-1]=LI; } l2: int a=0; cout<<"输入要查找的学号"< cin>>n; int low,high,mid; low=0;high=; uehao) { cout<<[mid].xuehao<<" "<<[mid].xingming<<" "<<[mid].xingbei<<" "<<[mid].chengji1<<" "<<[mid].chengji2<<" "<<[mid].zong< a=1; break; } else if(n<[mid].xuehao ) high=mid-1; ingming) { cout<<[i].xuehao<<" "<<[i].xingming<<" "<<[i].xingbei<<" "<<[i].chengji1<<" "<<[i].chengji2<<" "<<[i].zong< a=1; } } if(!a) { cout<<"所查信息不存在!"< cout<<"请重新输入"< goto l3; } goto l1; } if(m==3) ingbei) { cout<<[i].xuehao<<" "<<[i].xingming<<" "<<[i].xingbei<<" "<<[i].chengji1<<" "<<[i].chengji2<<" "<<[i].zong< a=1; } } if(!a) { cout<<"所查信息不存在!"< cout<<"请重新输入"< goto l4; } goto l1; } if(m==4) { caidan(ST); } } void paixu(SqList &ST) uehao<[j-1].xuehao) { LI=[j]; [j]=[j-1]; [j-1]=LI; } shuchu(ST); cout<<"排序完毕"< goto l1; } if(n==2) hengji1>[j].chengji1) { LI=[j]; [j]=[i]; [i]=LI; } } shuchu(ST); cout<<"排序完毕"< goto l1; } if(n==3) hengji2>[j].chengji2) { LI=[j]; [j]=[i]; [i]=LI; } } shuchu(ST); cout<<"排序完毕"< goto l1; } if(n==4) ong>[j].zong) { LI=[j]; [j]=[i]; [i]=LI; } } shuchu(ST); cout<<"排序完毕"< goto l1; } if(n==5) //退出 { caidan(ST); } } void caidan(SqList &ST)//选择菜单 { cout<<"请选择要进入的模块"< cout<<"(1)查询"< cout<<"(2)排序"< cout<<"(3)退出"< int c; cin>>c; if(c==1) { chaxun(ST); } if(c==2) { paixu(ST); } if(c==3) { exit(0); } } void main() { SqList ST; CreatList(ST); zong(ST); shuchu(ST); caidan(ST); } 陕西科技大学实验报告 班级学号姓名实验组别 实验日期室温报告日期成绩 报告内容：（目的和要求、原理、步骤、数据、计算、小结等） 实验名称：查找与排序算法的实现和应用 实验目的： 1. 掌握顺序表中查找的实现及监视哨的作用。 2. 掌握折半查找所需的条件、折半查找的过程和实现方法。 3. 掌握二叉排序树的创建过程，掌握二叉排序树查找过程的实现。 4. 掌握哈希表的基本概念，熟悉哈希函数的选择方法，掌握使用线性探测法和链地址法进行冲突解决的方 法。 5. 掌握直接插入排序、希尔排序、快速排序算法的实现。 实验环境（硬/软件要求）：Windows 2000,Visual C++ 6.0 实验内容： 通过具体算法程序，进一步加深对各种查找算法的掌握，以及对实际应用中问题解决方 法的掌握。各查找算法的输入序列为：26 5 37 1 61 11 59 15 48 19输出 要求：查找关键字37,给出查找结果。对于给定的某无序序列，分别用直接插入排序、希尔排序、快速排序等方法进行排序，并输出每种排序下的各趟排序结果。 各排序算法输入的无序序列为：26 5 37 1 61 11 59 15 48 19。 实验要求： 一、查找法 1. 顺序查找 首先从键盘输入一个数据序列生成一个顺序表，然后从键盘上任意输入一个值，在顺序 表中进行查找。 2. 折半查找 任意输入一组数据作为个数据元素的键值，首先将此序列进行排序，然后再改有序表上 使用折半查找算法进对给定值key 的查找。 3. 二叉树查找 任意输入一组数据作为二叉排序树中节点的键值，首先创建一颗二叉排序树，然后再次二叉排序树上实现对一 定k的查找过程。 4. 哈希表查找 任意输入一组数值作为个元素的键值，哈希函数为Hash （key ）=key%11, 用线性探测再散列法解决冲突问题。 二、排序算法 编程实现直接插入排序、希尔排序、快速排序各算法函数；并编写主函数对各排序函数进行测试。 实验原理： 1. 顺序查找： 在一个已知无（或有序）序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从最后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以 《数据结构》实验报告排序实验题目： 输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路： 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 次记录移动(赋值)的操作。而实际上， 实验六、七：查找、排序算法的应用 班级 10511 学号 20103051114 姓名高卫娜 一、实验目的 1 掌握查找的不同方法，并能用高级语言实现查找算法。 2 熟练掌握顺序表和有序表的顺序查找和二分查找方法。 3 掌握排序的不同方法，并能用高级语言实现排序算法。 4 熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现。 二、实验内容 1 创建给定的顺序表。表中共包含八条学生信息，信息如下： 学号姓名班级C++ 数据结构 1 王立03511 85 76 2 张秋03511 78 88 3 刘丽03511 90 79 4 王通03511 7 5 86 5 赵阳03511 60 71 6 李艳03511 58 68 7 钱娜03511 95 89 8 孙胜03511 45 60 2 使用顺序查找方法，从查找表中查找姓名为赵阳和王夏的学生。如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。 3 使用二分查找方法，从查找表中查找学号为7和12的学生。如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。（注意：创建静态查找表时必须按学号的从小到大排列！） 4 使用直接插入排序方法，对学生信息中的姓名进行排序。输出排序前和排序后的学生信息表，验证排序结果。 5 使用直接选择排序方法，对学生信息中的C成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。 6 使用冒泡排序方法，对学生信息中的数据结构成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。 7 编写一个主函数，将上面函数连在一起，构成一个完整程序。 8 将实验源程序调试并运行。 三、实验结果 源程序代码为： #include 实验七查找、排序的应用 一、实验目的 1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。 2、学会比较各种排序与查找算法的优劣。 3、学会针对所给问题选用最适合的算法。 4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。 二、实验内容 [问题描述] 对学生的基本信息进行管理。 [基本要求] 设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1．总成绩要求自动计算； 2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）； 3．排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。 [测试数据] 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握哈希表的定义，哈希函数的构造方法。 2、掌握一些常用的查找方法。 1、掌握几种常用的排序方法。 2、掌握直接排序方法。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果，对程序进行分析。 五、算法设计 a、折半查找 设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时，令low=1,high=n,mid=(low+high)/2，让key与mid指向的记录比较， 若key==r[mid].key，查找成功 若key 电子科技大学实验报告 课程名称：数据结构与算法 学生姓名： 学号： 点名序号： 指导教师： 实验地点：基础实验大楼 实验时间： 5月20日 2014-2015-2学期 信息与软件工程学院 实验报告（二） 学生姓名学号：指导教师： 实验地点：基础实验大楼实验时间：5月20日 一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—排序与查找 三、实验学时：4 四、实验原理： 快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 1）设置两个变量I、J，排序开始的时候I：=1，J：=N 2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]； 3）从J开始向前搜索，即（J：=J-1），找到第一个小于X的值，两者交换； 4）从I开始向后搜索，即（I：=I+1），找到第一个大于X的值，两者交换； 5）重复第3、4步，直到I=J。 二分法查找（折半查找）的基本思想： （1）确定该区间的中点位置：mid=（low+high）/2 min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置（2）将待查a值与结点mid的关键字（下面用R[mid].key）比较，若相等，则查找成功，否则确定新的查找区间： A)如果R[mid].key>a，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中,这时high=mid-1; B)如果R[mid].key 动态查找表实验报告 一. 1 、实验概要 实验项目名称: 抽象数据类型的实现 实验项目性质: 设计性实验 所属课程名称: 数据结构 实验计划学时: 6 2、实验目的 对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。 实验要求如下： 1．参加实验的学生应首先了解设计的任务，然后根据自己的基础和能力从中选择一题。一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。若学生对教材以外的相关题目较感兴趣，希望选作实验的题目时，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。 2. 实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。 3. 实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。 4. 实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。 所用软件环境或工具：DEV-C++5可视化编程环境. 3.动态查找表的抽象数据类型 ADT DynamicSearchTable { 数据对象D：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一 标识数据元素。 数据关系R：数据元素同属一个集合。 基本操作P： InitDSTable(&DT); 操作结果：构造一个空的动态查找表DT。 DestroyDSTable(&DT); 初始条件：动态查找表DT存在； 操作结果：销毁动态查找表DT。 SearchDSTable(DT, key); 初始条件：动态查找表DT存在，key为和关键字类型相同的给定值； 操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的 实验四：查找与排序 【实验目的】 1.掌握顺序查找算法的实现。 2.掌握折半查找算法的实现。 【实验内容】 1.编写顺序查找程序，对以下数据查找37所在的位置。 5，13，19，21，37，56，64，75，80，88，92 2.编写折半查找程序，对以下数据查找37所在的位置。 5，13，19，21，37，56，64，75，80，88，92 【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。 至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4．写好代码 5．编译－＞链接－＞调试 #include "stdio.h" #include "malloc.h" #define OVERFLOW -1 #define OK 1 #define MAXNUM 100 typedef int Elemtype; typedef int Status; typedef struct { Elemtype *elem; int length; }SSTable; Status InitList(SSTable &ST ) { int i,n; ST.elem = (Elemtype*) malloc (MAXNUM*sizeof (Elemtype)); if (!ST.elem) return(OVERFLOW); printf("输入元素个数和各元素的值:"); scanf("%d\n",&n); for(i=1;i<=n;i++) { scanf("%d",&ST.elem[i]); } ST.length = n; return OK; } int Seq_Search(SSTable ST,Elemtype key) { int i; ST.elem[0]=key; for(i=ST.length;ST.elem[i]!=key;--i); return i; } int BinarySearch(SSTable ST,Elemtype key) { int low,high,mid; low=1; high=ST.length; 《数据结构》实验报告一 学院：班级： 学号：姓名： 日期：程序名 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输入结点值。 2.从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找 不到，则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 二、源程序及注释： #include 河南工业大学实验报告 课程名称数据结构实验项目实验三查找和排序(二)——排序院系信息学院计科系专业班级计科1203 姓名张伟龙学号 201216010313 指导老师范艳峰日期 2013.6.5 批改日期成绩 一实验目的 掌握希尔排序、快速排序、堆排序的算法实现。 二实验内容及要求 实验内容：1．实现希尔排序。 2．实现快速排序。 3. 实现堆排序。 （三选一） 实验要求：1. 根据所选题目，用C语言编写程序源代码。 2. 源程序必须编译调试成功，独立完成。 三实验过程及运行结果 选择第三题： Source Code： #include int rchild=2*i+1; //i的右孩子节点序号 int max=i; //临时变量 if(i<=size/2) //如果i是叶节点就不用进行调整 { if(lchild<=size&&a[lchild]>a[max]) { max=lchild; } if(rchild<=size&&a[rchild]>a[max]) { max=rchild; } if(max!=i) { swap(a[i],a[max]); HeapAdjust(a,max,size); //避免调整之后以max为父节点的子树不是堆 } } } void BuildHeap(int *a,int size) //建立堆 { int i; for(i=size/2;i>=1;i--) //非叶节点最大序号值为size/2 { HeapAdjust(a,i,size); } } 淮海工学院计算机科学系实验报告书 课程名：《数据结构》 题目：查找、排序的应用实验 班级：软件102 学号：111003215 姓名：鹿迅 排序、查找的应用实验报告要求 1目的与要求: 1）查找、排序是日常数据处理过程中经常要进行的操作和运算，掌握其算法与应用对于提高学生数据处理能力和综合应用能力显得十分重要。 2）本次实验前，要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使用的数据存储结构； 3）利用C或C++语言独立完成本次实验内容或题目，程序具有良好的交互性（以菜单机制实现实验程序的交互运行）和实用性； 4）本次实验属于验收平分性质实验，希望同学们认真对待，并按时完成实验任务； 5）认真书写实验报告（包括程序清单及相关实验数据与完整运行结果），并按时提交。 2 实验内容或题目 题目：对记录序列（查找表）：{55，13，23，72，109，67，2，78,13}分别实现如下操作： 1)顺序查找； 2)分别使用直接插入排序、冒泡排序、快速排序对原纪录序列进行排序（暂时人工排序）； 3)对排好序的纪录序列表进行折半查找； 4)利用原纪录序列建立一颗二叉排序树，并在其上实现特定关键字值结点的查找； 5)按照“除留余数法”哈希构造函数和线性探测再散列的冲突处理方法创建表长为m=11的哈希表 （暂时不做，下次实验做）； 6)实现5）创建哈希表上的查找。 3 实验步骤与源程序 #include 实验四——查找 一、实验目的 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; umber; for(i=1;[i].number!=0;) { cin>>[i].name>>[i].sex>>[i].age; ++; cout< 《编程实训》 实验报告书 专业：计算机科学与技术 班级：151班 学号： 姓名： 指导教师： 日期：2016年6月30日 目录 一、需求分析 (3) 1.任务要求 (3) 2.软件功能分析 (3) 3.数据准备 (3) 二、概要设计 (3) 1.功能模块图 (4) 2.模块间调用关系 (4) 3.主程序模块 (5) 4.抽象数据类型描述 (5) 三、详细设计 (6) 1.存储结构定义 (6) 2.各功能模块的详细设计 (7) 四、实现和调试 (7) 1.主要的算法 (7) 2.主要问题及解决 (8) 3.测试执行及结果 (8) 五、改进 (9) 六、附录 (9) 1.查找源程序 (9) 2.排序源程序 (9) 目录 1 需求分析 1.1 任务要求 对于从键盘随机输入的一个序列的数据，存入计算机内，给出各种查找算法的实现； 以及各种排序算法的实现。 1.2 软件功能分析 任意输入n个正整数，该程序可以实现各类查找及排序的功能并将结果输出。 1.3 数据准备 任意输入了5个正整数如下： 12 23 45 56 78 2 概要设计（如果2，3合并可以省略2.4） 2.1 功能模块图（注：含功能说明） 2.2 模块间调用关系 2.3 主程序模块 2.4 抽象数据类型描述 存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。又称为存储结构。数据类型（data type）是一个“值”的集合和定义在此集合上的一组操作的总称。 3 详细设计 3.1 存储结构定义 查找： typedef int ElemType ; //顺序存储结构 typedef struct { ElemType *elem; //数据元素存储空间基址，建表时按实际长度分配，号单元留空 int length; //表的长度 实验五 查找及排序 实验课程名： 数据结构与算法 一、实验目的及要求 1、掌握查找的不同方法，并能用高级语言实现查找算法。 2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法。 3、掌握常用的排序方法，并能用高级语言实现排序算法。 4、深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。 5、了解各种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度的分析方法。 二、实验内容 任务一：顺序表的顺序查找。 有序表的折半查找。 完成下列程序，该程序实现高考成绩表（如下表所示）的顺序查找，在输出结果中显示查找成功与查找不成功信息。 解答： （1）源代码：#include 【一】需求分析 课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。 为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。 【二】概要设计 1.堆排序 ⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。 ⑵程序实现及核心代码的注释： for(j=2*i+1; j<=m; j=j*2+1) { if(j temp=su[i]; su[i]=su[0]; su[0]=temp; head(0,i-1); } cout<<"排序之后的数组为："< 学院专业班学号 协作者_____________教师评定_________________ 实验题目查询与排序 综合实验评分表 实验报告 一、实验目的与要求 1、掌握散列表的构造及实现散列查找； 2、掌握堆排序的算法； 3、综合比较各类排序算法的性能。 二、实验容 #include"stdio.h" #include"stdlib.h" #include"string.h" #include"windows.h" #define MAX 20 typedef struct{ unsigned long key; int result; char name[30];}RNode; RNode t[MAX],r[MAX]; int h(unsigned long k) /*散列函数*/ { return((k-3109005700)%11); } void insert(RNode t[],RNode x) /*插入函数，以线性探查方法解决冲突*/ { int i,j=0; i=h(x.key); while((j xxx大学实验报告 课程名称数据结构实验项目实验三查找和排序(一)——查找 院系信息学院计类系专业班级计类1501 姓名学号 指导老师日期 批改日期成绩 一实验目的 1．掌握哈希函数——除留余数法的应用； 2. 掌握哈希表的建立； 3. 掌握冲突的解决方法； 4. 掌握哈希查找算法的实现。 二实验内容及要求 实验内容：已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)，哈希 函数定义为：H(key)=key MOD 13, 哈希表长为m=16。实现该哈希表的散列，并 计算平均查找长度（设每个记录的查找概率相等）。 实验要求：1. 哈希表定义为定长的数组结构；2. 使用线性探测再散列或链 地址法解决冲突；3. 散列完成后在屏幕上输出数组内容或链表；4. 输出等概率 查找下的平均查找长度；5. 完成散列后，输入关键字完成查找操作，要分别测 试查找成功与不成功两种情况。 注意：不同解决冲突的方法会使得平均查找长度不同，可尝试使用不同解决 冲突的办法，比较平均查找长度。（根据完成情况自选，但至少能使用一种方法 解决冲突） 三实验过程及运行结果 #include #define q 13 int sign=2; typedef struct Hash { int date; //值域 int sign; //标记 }HashNode; void compare(HashNode H[],int p,int i,int key[]) //线性冲突处理{ p++; if(H[p].sign!=0) { sign++; compare(H,p,i,key); } else { H[p].date=key[i]; H[p].sign=sign; sign=2; } } void Hashlist(HashNode H[],int key[]) { int p; for(int i=0;i<12;i++) { p=key[i]%q; if(H[p].sign==0) { H[p].date=key[i]; H[p].sign=1; } else compare(H,p,i,key); } } int judge(HashNode H[],int num,int n) //查找冲突处理 { 实验七查找和排序算法的实现 一．实验目的及要求 （1）学生在实验中体会各种查找和内部排序算法的基本思想、适用场合，理解开发高效算法的可能性和寻找、构造高效算法的方法。 （2）掌握运用查找和排序解决一些实际应用问题。 二.实验内容： （1）编程实现一种查找算法（如折半查找、二叉排序树的查找、哈希查找等），并计算相应的ASL。 （2）编程实现一种内部排序算法（如插入排序、快速排序等）。 三.实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页） （1）编程实现一种查找算法（如折半查找、二叉排序树的查找、哈希查找等），并计算相应的ASL。 ?程序代码： 折半查找： 头文件： #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define maxlength 20 typedef int ElemType; typedef struct{ ElemType key; ElemType other; }card;//每条记录包含的数据项 typedef struct{ card r[maxlength]; int length; }SSTable;//一张表中包含的记录容量 void Create(SSTable &L); int Search(SSTable L,int elem); 功能函数： #include"1.h" #include"stdio.h" void Create(SSTable &L) { printf("新的线性表已经创建，请确定元素个数（不超过20）\n"); scanf("%d",&L.length); printf("请按递增序列输入具体的相应个数的整数元素（空格隔开）\n"); for(int i=0;i 一、实验目的 1、了解内排序都是在内存中进行的。 2、为了提高数据的查找速度，需要对数据进行排序。 3、掌握内排序的方法。 二、实验内容 1、设计一个程序e xp10—1.cpp实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序 过程。 （1）源程序如下所示： //文件名:exp10-1.cpp #include _________ 学院_________ 专业____________ 班学号_______________ 姓名___________ 协作者______________ 师评定____________________ 实验题目查询与排序 综合实验评分表 实验报告 实验目的与要求 1、掌握散列表的构造及实现散列查找; 2、掌握堆排序的算法； 3、综合比较各类排序算法的性能。 二、实验内容 #include "stdio.h" #include "stdlib.h" #include "string.h" #include "windows.h" #define MAX 20 typedef struct{ unsigned long key; int result; char name[30]; }RNode; RNode t[MAX],r[MAX]; int h( unsigned long k) /* 散列函数*/ { return ((k - 3109005700)%11); } void insert(RNode t[],RNode x) /*插入函数，以线性探查方法解决冲突*/ { int i,j =0; i =h(x. key); while ((j 实验8查找与排序算法的实现和应用
《数据结构》实验报告——排序.docx
实验6 查找和排序 (2)(1)
(完整word版)查找、排序的应用 实验报告
实验报告-排序与查找
动态查找表实验报告材料
查找与排序实验报告
顺序表的查找、插入与删除实验报告
河南工业大学实验报告——查找和排序(排序)——张伟龙
查找、排序综合实验
《数据结构》实验报告查找
查找排序实验报告
实验五查找及排序讲解
各种排序实验报告
查询与排序 实验报告
河南工业大学实验报告_实验三 查找和排序(一)——查找
查找和排序算法的实现(实验七)
数据结构内排序实验报告
查询与排序实验报告