排序问题实验报告
2010级数据结构实验报告
实验名称：排序
姓名：袁彬
班级： 2009211120
班内序号： 09
学号： 09210552
日期： 2010 年12 月19 日
1．实验要求
试验目的：
通过选择试验内容中的两个题目之一，学习、实现、对比各种排序的算法，掌握各种排序算法的优缺点，以及各种算法使用的情况。
试验内容：
题目一：
使用简单数组实现下面各种排序算法，并进行比较。
排序算法如下：
①插入排序；
②希尔排序
③冒泡排序；
④快速排序；
⑤简单选择排序；
⑥堆排序
⑦归并排序
⑧基数排序
⑨其他。
具体要求如下：
①测试数据分为三类：正序，逆序，随机数据。
②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。
③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。
④对②和③的结果进行分析，验证上述各种算法的时间复杂度。
⑤编写main()函数测试各种排序算法的正确性。
题目二：
使用链表实现下面各种排序算法，并进行比较。
排序算法如下：
①插入排序；
②冒泡排序；
③快速排序；
④简单选择排序；
⑤其他。
具体要求如下：
①测试数据分为三类：正序，逆序，随机数据。
②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。
③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙（选作）
④对②和③的结果进行分析，验证上述各种算法的时间复杂度。
⑤编写main()函数测试各种排序算法的正确性。
2. 程序分析
2.1 存储结构
程序中每一个算法均是用一个类来表示的，类中有自己的构造函数、排序函数。
程序的储存结构采用数组。数组的第一个位置不存储数据。数据从第二个位置开始。数组中的相对位置为数组的下标。
2.2 关键算法分析
㈠、关键算法：
1、插入排序函数：Insert s ort(int n)
①、从2开始做循环，依次和前面的数进行比较：for(int i=2;i<=n;i++)
②、如果后面的比前面的小，则进行前移：if(number[i] ③、设置哨兵：number[0]=number[i]; ④、如果后面的比前面的小，前面的进行后移：for(j=i-1;number[0] ⑤、前面的进行后移：number[j+1]=number[j]; ⑥、将比较的数据放置到正确位置：number[j+1]=number[0]; 2、希尔排序函数：Shell i nsert(int n) ①、以长度的一半为间隔进行循环：for(int d=n/2;d>=1;d=d/2) ②、在自己的间隔中进行简单插入排序，进行循环：for(int i=d+1;i<=n;i++) ③、如果后面的数据比前面的小，进行前移：if(number[i] ④、设置哨兵：number[0]=number[i]; ⑤、在自己的间隔中进行简单插入排序：for(j=i-d;number[0] ⑥、大的数据后移：number[j+d]=number[j]; ⑦、哨兵归位：number[j+d]=number[0]; 3、冒泡排序函数：Bubble s ort(int n) ①、设置有序无序的边界点：int pos=n; ②、当边界点不为空进行循环：while(pos!=0) ③、边界点传递给bound：int bound=pos; ④、从开始到边界点进行循环：for(int i=1;i ⑤、如果前面的数据比后面的大，进行交换：if(number[i]>number[i+1]) ⑥、交换：number[0]=number[i];number[i]=number[i+1];number[i+1]=number[0]; ⑦、从小设置边界点：pos=i; 4、一趟快速排序函数：partion(int first,int end) ①、传递设置整个数据的起点和终点：int i=first;int j=end; ②、设置中轴：number[0]=number[i]; ③、当end大于first进行循环：while(i ④、当后面的数据大于中轴，后面的游标前移：while((i ⑤、中轴和比它大的数据进行交换：number[i]=number[j]; ⑥、当前面的数据小于中轴，前面的游标后移：while((i i++; ⑦、中轴和比它小的数据进行交换：number[j]=number[i]; ⑧、将中轴进行归位：number[i]=number[0]; 5、递归快速排序函数：Qsort(int i,int j) ①、如果数组不为空，进行排序：if(i ②、一趟冒泡排序：int pivotloc=partion(i,j); ③、递归将左右半面进行排序：Qsort(i,pivotloc-1);Qsort(pivotloc+1,j); 6、简单选择排序函数：Select s ort(int n) ①、从数组开始到结尾进行遍历：for(int i=1;i ②、设置最小数据标记：int index=i; ③、在无序区进行循环：for(int j=i+1;j<=n;j++) ④、当出现比标记还小的数据，就进行交换：if(number[j] ⑤、如果最小的不是末尾的数，就进行交换：if(index!=i) ⑥、进行交换： number[0]=number[i];number[i]=number[index];number[index]=number[0]; 7、一趟堆排序函数：sift(int k,int m) ①、设置根节点和孩子的位置：int i=k,j=2*k; ②、从左右孩子中选择出最小的孩子：if(j ③、判断根节点是不是最小的，不是就进行交换：if(number[i] ④、进行交换：number[0]=number[i];number[i]=number[j];number[j]=number[0]; ⑤、将根节点和孩子位置后移，继续排序：i=j;j=2*i; 8、递归堆排序函数：Heap s ort(int n) ①、从最大非叶子节点，进行一趟堆排序：for(i=n/2;i>=1;i--) ②、进行数组长度值的循环：for(i=1;i ③、将根节点和尾节点进行交换： number[0]=number[1];number[1]=number[n-i+1];number[n-i+1]=number[0]; ④、在进行一趟堆排序：sift(1,n-i); 9、一趟归并排序函数：Merge(int *r, int *r1, int s, int m, int t) ①、传递设置两个数组的起点和终点：int i=s;int j=m+1;int k=s; ②、当任意一个数组没有达到终点时，进行循环：while(i<=m&&j<=t) ③、进行循环，将较小的值传给r1数组：if(r[i] ④、将较小的值传给r1数组：r1[k++]=r[i++];else r1[k++]=r[j++]; ⑤、当一个数字已经比较完，做循环将其续借到r1数组中：if(i<=m)while(i<=m) r1[k++]=r[i++]; ⑤、当另一个数字已经比较完，做循环将其续借到r1数组中：if(j<=t)while(j<=t) r1[k++]=r[j++]; 10、递归归并排序函数：MergeSort(int *r, int *r1, int s, int t) ①、创建新数字指针存储排序序列：int *r2=new int[t]; ②、当序列中只有一个数据时，令其相等：if(s==t)r1[s]=r[s]; ③、否则，进行递归：else ④、将原数组折半：int m=(s+t)/2; ⑤、将前半数组进行递归调用：MergeSort(r,r2,s,m); ⑥、将后半数组进行递归调用：MergeSort(r,r2,m+1,t); ⑦、将数组进行递归调用：Merge(r2,r1,s,m,t); ㈡、关键算法的时间、空间复杂度 ①、直接插入排序函数：时间复杂度O（n2） ②、希尔排序函数：时间复杂度O(n㏒2 n) ③、起泡排序：时间复杂度O（n2） ④、快速排序：时间复杂度O(n㏒2 n) ⑤、简单选择排序：时间复杂度O（n2） ⑥、堆排序：时间复杂度O(n㏒2 n) ⑦、归并排序：时间复杂度O(n㏒2 n) 3. 程序运行结果 测试主函数流程： 程序流程图如下： 4. 总结 （1）、出现的问题及调试的方法 这次试验总的来说是比较简单的，因为这七种排序算法的代码书上都有，在理解的基础上参考书上的代码输入基本上不会有太大的问题，但问题还是有的。例如：一组待排序的整数存在一个数组中，当采用一种排序算法对这个数组进行排序后，数组就被修改了，变为有序的序列，这是一个问题，于是我动态申请了七个数组，每次排序对不同的数组进行，这个问题就解决了 （2）、心得体会 这次试验是我对排序运算有了深刻的理解，对我们课堂上的知识进行回顾。 在程序编译和链接时还报了一些错，最后我对排序运算有了深刻的理解，对我们课堂上的知识进行回顾。 在程序编译和链接时还报了一些错，最后通过一步一步的测试，也很快解决了问题。 通过这次程序我感觉我对C++调试有个很深的理解，对程序的调试有了很多心得，也对我的程序调试和编写有了进一步的提高。同时对C++编程进一步熟悉，同时对数据结构有了一个整体的认识，对各种排序中函数成员实现的原理、代码进一步了解。同时对各种排序的优缺点有了进一步的认识和了解。 在这个程序中，我觉得下一步程序可以进一步对时间复杂度进行优化，通过将程序的冗长的代码删除，优化算法等，让程序得到结果所需要的时间更短、更快，删除一些代码，让程序的空间复杂度和时间复杂度都减小。 （3）、下一步的改进 程序中代码有一部分不是太简洁，例如七个数组、统计比较了移动次数这些代码显得比较乱。 算法设计与分析基础 实验报告 应用数学学院 二零一六年六月 实验一插入排序算法 一、实验性质设计 二、实验学时14学时 三、实验目的 1、掌握插入排序的方法和原理。 2、掌握java语言实现该算法的一般流程。 四、实验内容 1、数组的输入。 2、输入、输出的异常处理。 3、插入排序的算法流程。 4、运行结果的输出。 五、实验报告 Ⅰ、算法原理 从左到右扫描有序的子数组，直到遇到一个大于（或小于）等于A[n-1]的元素，然后就把A[n-1]插在该元素的前面（或后面）。 插入排序基于递归思想。 Ⅱ、书中源代码 算法InsertionSort（A[0..n-1]） //用插入排序对给定数组A[0..n-1]排序 //输入：n个可排序元素构成的一个数组A[0..n-1] //输出：非降序排列的数组A[0..n-1] for i ←1 to n-1 do v ← A[i] j ← i-1 while j ≥0and A[j] > v do A[j+1] ← A[j] j ← j-1 A[j+1] ← v Ⅲ、Java算法代码： import java.util.*; public class Charu { public static void main(String[] args) { int n = 5; int a[] = new int[n]; int s = a.length; int i = 0, j = 0, v = 0; System.out.println("请输入若干个数字："); Scanner sc = new Scanner(System.in); try { while (i < s) { a[i] = sc.nextInt(); i++; } for (i = 1; i 《数据结构》实验报告排序实验题目： 输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路： 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、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。 二、实验内容 [问题描述] 对学生的基本信息进行管理。 [基本要求] 设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩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 《排序问题求解》实验报告 一、算法的基本思想 1、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中，从而得到一个新的， 记录数增1 的有序序列。 直接插入排序算法的伪代码称为InsertionSort，它的参数是一个数组A[1..n]，包含了n 个待排序的数。用伪代码表示直接插入排序算法如下： InsertionSort (A) for i←2 to n do key←A[i] //key 表示待插入数 //Insert A[i] into the sorted sequence A[1..i-1] j←i-1 while j>0 and A[j]>key do A[j+1]←A[j] j←j-1 A[j+1]←key 2、快速排序算法思想 快速排序算法的基本思想是，通过一趟排序将待排序序列分割成独立的两部分，其中一 部分记录的关键字均比另一部分记录的关键字小，则可对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序序列为数组A[1..n]，首先选取第一个数A[0]，作为枢轴（pivot），然后按照下述原则重新排列其余数：将所有比A[0]大的数都排在它的位置之前，将所有比A[0]小的数都排在它的位置之后，由此以A[0]最后所在的位置i 作为分界线，将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序，对子数组A[1..i-1]和A[i+1..n]排序。 一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey，则首先从high 所指位置起向前搜索，找到第一个小于pivotkey 的数，并将其移到低端，然后从low 所指位置起向后搜索，找到第一个大于pivotkey 的数，并将其移到高端，重复这两步直至low=high。最后，将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下： Partition ( A, low, high) A[0]←A[low] //用数组的第一个记录做枢轴记录 privotkey←A[low] //枢轴记录关键字 while low 电子科技大学实验报告 课程名称：数据结构与算法 学生姓名： 学号： 点名序号： 指导教师： 实验地点：基础实验大楼 实验时间： 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 数据结构 排序算法综合实验报告 姓名： xx x x 班级： 10电信1 学号： xxx 指导老师：胡圣荣 日期： 2012.12.15～2013.1.5 华南农业大学工程学院 算法基本思想： 1、插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已经排序好的序列中的适当位置，直到全部记录插入完毕为止。 （1）直接插入排序：在排序过程中，每次都讲无序区中第一条记录插入到有序区中适当位置，使其仍保持有序。初始时，取第一条记录为有序区，其他记录为无序区。显然，随着排序过程的进行，有序区不断扩大，无序区不断缩小。最终无序区变为空，有序区中包含了所有的记录，排序结束。 （2）希尔排序：将排序表分成若干组，所有相隔为某个“增量”的记录为一组，在各组进行直接插入排序；初始时增量d1较大，分组较多（每组的记录数少），以后增量逐渐减少，分组减少（每组的记录数增多），直到最后增量为1（d1>d2>...>dt=1）,所有记录放为一组，再整体进行一次直接插入排序。 2、交换排序：每次比较两个待排序的记录，如果发现他们关键字的次序与排序要求相反时就交换两者的位置，直到没有反序的记录为止。 （1）冒泡排序：设想排序表R[1]到R[n]垂直放置，将每个记录R[i]看作是重量为R[i].key 的气泡；根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。 （2）快速排序：在待排序的n个记录中任取一个作为“基准”，将其与记录分为两组，第一组中个记录的键值均小于或等于基准的键值，第二组中个记录的键值均大于或等于基准的键值，而基准就排在这两组中间（这也是该记录的最终位置），这称为一趟快速排序（或一次划分）。对所分成的两组重复上述方法，直到所有记录都排在适当位置为止。 3、选择排序：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已排好序的子序列的后面（或最前），直到全部记录排序完毕。 （1）直接选择排序：首先，所有记录组成初始无序区R[1]到R[n]，从中选出键值最小的记录，与无序区第一个记录R[1]交换；新的无序区为R[2]到R[n]，从中再选出键值最小的记录，与无序区第一个记录R[2]交换；类似，第i趟排序时R[1]到R[i-1]是有序区，无序区为R[i]到R[n]，从中选出键值最小的记录，将它与无序区第一个记录R[i]交换，R[1]到R[i]变为新的有序区。因为每趟排序都使有序区中增加一个记录，所以，进行n-1趟排序后，整个排序表就全部有序了。 （2）堆排序：利用小根堆（或大根堆）来选取当前无序区中关键字最小（或最大）的记录来实现排序的。下面介绍利用大根堆来排序。首先，将初始无序区调整为一个大根堆，输出关键字最大的堆顶记录后，将剩下的n-1个记录在重建为堆，于是便得到次小值。如此反复执行，知道全部元素输出完，从而得到一个有序序列。 4、并归排序：指将若干个已排序的子表合成一个有序表。 （1）二路并归排序：开始时，将排序表R[1]到R[n]看成n个长度为1的有序子表，把这些子表两两并归，便得到n/2个有序的子表（当n为奇数时，并归后仍是有一个长度为1的子表）；然后，再把这n/2个有序的子表两两并归，如此反复，直到最后得到一个程度为n的 实验四：查找与排序 【实验目的】 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; 数据结构与算法设计 实验报告 （2016 — 2017 学年第1 学期） 实验名称： 年级： 专业： 班级： 学号： 姓名： 指导教师： 成都信息工程大学通信工程学院 一、实验目的 验证各种简单的排序算法。在调试中体会排序过程。 二、实验要求 （1）从键盘读入一组无序数据，按输入顺序先创建一个线性表。 （2）用带菜单的主函数任意选择一种排序算法将该表进行递增排序，并显示出每一趟排序过程。 三、实验步骤 1、创建工程（附带截图说明） 2、根据算法编写程序（参见第六部分源代码） 3、编译 4、调试 四、实验结果图 图1-直接输入排序 图2-冒泡排序 图3-直接选择排序 五、心得体会 与哈希表的操作实验相比，本次实验遇到的问题较大。由于此次实验中设计了三种排序方法导致我在设计算法时混淆了一些概念，设计思路特别混乱。虽然在理清思路后成功解决了直接输入和直接选择两种算法，但冒泡 排序的算法仍未设计成功。虽然在老师和同学的帮助下完成了冒泡排序的算法，但还需要多练习这方面的习题，平时也应多思考这方面的问题。而且，在直接输入和直接选择的算法设计上也有较为复杂的地方，对照书本做了精简纠正。 本次实验让我发现自己在算法设计上存在一些思虑不周的地方，思考问题过于片面，逻辑思维能力太过单薄，还需要继续练习。 六、源代码 要求：粘贴个人代码，以便检查。 #include 《数据结构》实验报告一 学院：班级： 学号：姓名： 日期：程序名 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输入结点值。 2.从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找 不到，则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 二、源程序及注释： #include 本章共8道实验题目。 一、直接插入排序 1. 定义顺序表的存储结构 2. 初始化顺序表为空表 3. 输入10个元素创建含有10个元素的顺序表 4. 输出顺序表 5. 对顺序表进行直接插入排序（InsertSort） 6. 输出排序后的顺序表 例如： 11 938 669 507 117 261 708 343 300 602 11 938 669 507 117 261 708 343 300 602 11 117 261 300 343 507 602 669 708 938 程序: #include { int InsertSort; for (int i = 0; i < 10; ++i) { cin >> a[i]; cout << a[i] << " "; } cout << endl; sort(a, a+10); for (int i = 0; i < 10; ++i) cout << a[i] << " "; return 0; } 二、折半插入排序 1. 定义顺序表的存储结构 2. 初始化顺序表为空表 3. 输入10个元素创建含有10个元素的顺序表 4. 输出顺序表 5. 对顺序表进行折半插入排序（BInsertSort） 6. 输出排序后的顺序表 例如： 11 938 669 507 117 261 708 343 300 602 11 938 669 507 117 261 708 343 300 602 11 117 261 300 343 507 602 669 708 938 程序： #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); } } 2010级数据结构实验报告 实验名称：排序 姓名：袁彬 班级： 2009211120 班内序号： 09 学号： 09210552 日期： 2010 年12 月19 日 1．实验要求 试验目的： 通过选择试验内容中的两个题目之一，学习、实现、对比各种排序的算法，掌握各种排序算法的优缺点，以及各种算法使用的情况。 试验内容： 题目一： 使用简单数组实现下面各种排序算法，并进行比较。 排序算法如下： ①插入排序； ②希尔排序 ③冒泡排序； ④快速排序； ⑤简单选择排序； ⑥堆排序 ⑦归并排序 ⑧基数排序 ⑨其他。 具体要求如下： ①测试数据分为三类：正序，逆序，随机数据。 ②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。 ③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。 ④对②和③的结果进行分析，验证上述各种算法的时间复杂度。 ⑤编写main()函数测试各种排序算法的正确性。 题目二： 使用链表实现下面各种排序算法，并进行比较。 排序算法如下： ①插入排序； ②冒泡排序； ③快速排序； ④简单选择排序； ⑤其他。 具体要求如下： ①测试数据分为三类：正序，逆序，随机数据。 ②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。 ③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙（选作） ④对②和③的结果进行分析，验证上述各种算法的时间复杂度。 ⑤编写main()函数测试各种排序算法的正确性。 2. 程序分析 2.1 存储结构 程序中每一个算法均是用一个类来表示的，类中有自己的构造函数、排序函数。 程序的储存结构采用数组。数组的第一个位置不存储数据。数据从第二个位置开始。数组中的相对位置为数组的下标。 2.2 关键算法分析 ㈠、关键算法： 1、插入排序函数：Insert s ort(int n) ①、从2开始做循环，依次和前面的数进行比较：for(int i=2;i<=n;i++) ②、如果后面的比前面的小，则进行前移：if(number[i] 实验四——查找 一、实验目的 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为快速排序，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、掌握内排序的方法。 二、实验内容 1、设计一个程序e xp10—1.cpp实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序 过程。 （1）源程序如下所示： //文件名:exp10-1.cpp #include 二叉排序树的实现 实验内容与要求 1) 实现二叉排序树，包括生成、插入，删除； 2) 对二叉排序树进行先根、中根、和后根非递归遍历； 3) 每次对树的修改操作和遍历操作的显示结果都需要在屏 幕上用树的形状表示出来。 实验方案 1. 选择链表的方式来构造节点，存储二叉排序树的节点。// 树的结构struct BSTNode { // 定义左右孩子指针 struct BSTNode *lchild,*rchild; // 节点的关键字 TElemType key; }; int depth=0; // 定义一个struct BSTNode 类型的指针typedef BSTNode *Tree; 2. 对树的操作有如下方法： // 创建二叉排序树 Tree CreatTree(Tree T) ； // 二叉树的深度，返回一个int 值为该树的深度 int TreeDepth(Tree T) // 树状输出二叉树，竖向输出 void PrintTree(Tree T , int layer) ； // 查找关键字，如果关键字存在则返回所在节点的父节点，如果关键字不存在则返回叶子所在的节点 Status SearchBST(Tree T , TElemType key , Tree f,Tree &p) ； // 向树中插入节点 Status InsertBST(Tree &T , TElemType e) ； // 删除节点 Status Delete(Tree &T) ； // 删除指定节点，调用Delete(Tree &T) 方法 Status DeleteData(Tree &T , TElemType key) ； // 非递归先序遍历void x_print(Tree T); // 非递归中序遍历 Void z_print(Tree T ); // 非递归后序遍历 void h_print(Tree T); 3. 对二叉排序树非递归先根、中根、后根遍历，采用栈来存储一次遍历过的节点的形式来辅助实现 // 自定义类型以SElemType 作为栈中指针返回的值的类型 // 也就是要返回一个节点的指针 typedef Tree SElemType; // 栈的结构 struct Stack { // 栈底指针SElemType *base; // 栈顶指针SElemType *top; // 栈的容量 int stacksize; }; 4. 栈的操作方法： // 创建一个空栈 Status InitStack(Stack &S) // 获取栈顶元素并删除栈中该位置的元素SElemType Pop(Stack &S,SElemType &elem) // 获取栈顶元素返回栈顶元素不对栈做任何修改SElemType getTop(Stack S,SElemType &elem) // 删除栈顶元素 Status DeleteTop(Stack &S) // 往栈中压入数据 Status Push(Stack &S,SElemType elem) // 判断栈是否为空 Status IsEmpty(Stack S) 三、代码实现 #include 插入排序算法实验报告
《数据结构》实验报告——排序.docx
(完整word版)查找、排序的应用 实验报告
算法排序问题实验报告
实验报告-排序与查找
排序综合实验报告
查找与排序实验报告
排序操作实验报告
顺序表的查找、插入与删除实验报告
数据结构实验报告-排序
河南工业大学实验报告——查找和排序(排序)——张伟龙
排序问题实验报告
《数据结构》实验报告查找
查找排序实验报告
各种排序实验报告
数据结构内排序实验报告
二叉排序树实验报告