数据结构 实验报告 内排序 比较.docx
- 文档编号:6890341
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:14
- 大小:512.89KB
数据结构 实验报告 内排序 比较.docx
《数据结构 实验报告 内排序 比较.docx》由会员分享,可在线阅读,更多相关《数据结构 实验报告 内排序 比较.docx(14页珍藏版)》请在冰点文库上搜索。
数据结构实验报告内排序比较
实验项目名称
综合算法设计
同组者
无
实验日期
第一部分:
实验预习报告
1、实验目的、意义
1)掌握查找的含义
2)掌握基本查找操作的算法和实现
3)掌握动态查找算法的实现、应用场合与优缺点
4)能够针对具体问题,灵活选用适宜的查找算法
5)掌握排序的基本概念,对排序的稳定性及排序的时间复杂度有深刻的认识
6)对比折半插入排序和Shell排序的异同
7)掌握选择排序中堆排序的基本思想和算法实现
8)掌握快速排序的基本思想和算法实现
9)了解归并排序算法的基本思想和程序实现
10)了解基数排序算法的基本思想和程序实现
11)掌握Hash排序算法的基本思想和程序实现
12)在上述内容的基础上,将所有查找及排序算法整合在一个程序中
2、实验基本原理与方法
本实验涉及各类查找和排序算法。
静态查找,折半查找的思想为:
设查找表中的元素存放在数组r中,数据元素的下标范围为[low,high],要查找的关键字值为key,中间元素的下标为mid=|_(low+high)/2_|(向下取整),令key与r[mid]的关键字比较:
1若key=r[mid].key,查找成功,下标为m的记录即为所求,返回mid。
2若key 3若key>r[mid].key,所要找的记录只能在右半部分记录中,再对右半部分使用折半查找法继续进行查找,搜索区间缩小了一半。 重复上述过程,直到找到查找表中某一个数据元素的关键字的值等于给定的值key,说明查找成功;或者出现low的值大于high的情况,说明查找不成功。 动态查找,编程实现一个开放式的高校本科招生最低录取分数线的查询系统,供师生和家长等查询,高校自愿放入该校的信息,可能随时有高校加入。 要求实现的查询功能有: ①查询等于用户给定分数的高校; ②查询大于(或小于)用户给定分数的高校③查询最低录取分数线在用户给定的分数段中的高校。 直接插入排序: 将当前无序区的第一个记录插入到有序区中适当位置。 折半查找法: 在有序表中进行,先确定表的中点位置,再通过比较确定下一步查找哪个半区。 Shell排序: 先取定一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组,所有距离为d1倍数的记录放在同一个组中,在各组内进行直接插入排序;然后取第二个增量重复上述分组和排序,直至所取的增量dt=1(dt 堆排序是利用大顶堆(或小顶堆)来选取当前无序区中关键字最大(或最小)的记录实现排序 快速排序是对冒泡法的改进,其基本思想是: 通过一趟排序将待排文件分割成独立的两部分,其中一部分记录的关键字值均比另一部分记录的关键字小,然后分别对这两部分进行排序,以达到整个序列有序。 归并的思想: 将两个或两个以上的有序表合并成一个有序表。 利用归并的思想实现排序,假设初始的序列含有n个记录,可以看成n个有序的子序列,每个子序列的长度为m,然后把i(≥2)个子序列归并,得到n/i个长度为i的子序列;再继续归并,如此重复直到得到一个长度为n的有序序列为止。 通常使用的是i=2的二路归并法。 基数排序的基本思想是采用多关键字的排序。 设记录关键字R[i]由d个分量ki1,ki2,…,kid组成,设每个分量的取值范围为{ti|i=1,2,…,m,且t1 准备m个箱子,先按低位分箱再按序号一次将各个非空箱子里的记录收集起来,再对新收集起来的元素依次按较高的位分箱,直到最高位。 分箱即将第s个关键字等于ti的全部记录装入第i个箱子里。 按最高位分箱后,按序号一次将各个非空箱子里的记录收集起来,得到的元素序列就是有序的。 Hash排序是在Hash查找的基础上演变而来。 对待排序列采用单调的Hash函数,并用链地址法处理冲突,最后用一定规则收集存储好的数据从而得到有序序列。 3、主要仪器设备及耗材 安装有TurboC++3.0运行环境的电脑,无耗材要求。 4、实验方案或技术路线 本实验含有五部分内容——静态查找、动态查找、插入排序与选择排序、快速排序与归并排序、查找及排序算法集成。 A.静态查找部分 查找表的存储结构为有序表,即表中记录按关键字大小排序存放。 输入待查数据元素的关键字进行查找。 为了简化算法,记录只含一个整型量关键字字段,记录的其余数据部分忽略不考虑。 此程序中要求对整型量关键字数据的输入按从小到大排序输入。 B.动态查找部分 主要的功能是查找,查找表为高校最低录取分数信息的集合。 根据题意可知,该查找表中的元素个数可能随时增减,所以它是一个动态查找表,可采用树状结构保存。 为了提高查询速度,可建立二叉排序树并在二叉排序树中实现查找。 C.排序部分 考虑对20个整数的随机输入进行排序,各排序功能基本上都可以成为独立调用的模块,因此可以先写出排序算法,然后用主函数调用。 D.查找及排序算法集成部分 此部分需要学生自行设计,本指导书不给出具体算法。 第二部分: 实验过程记录 实验原始记录(包括实验数据记录,实验现象记录,实验过程发现的问题等) 1.概要设计 (说明本程序中用到的所有抽象数据类型的定义,主程序的流程以及各程序模块之间的层次或调用关系) 1)抽象数据类型和数据结构的定义 i.在基数排序中,用到10个队列分别存放数字的位数,所以: ADTQueueNode{ 数据对象: D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系: R1={ 约定a1为队列头,an为队列尾。 基本操作: InitQueue_Sq(&Q) 操作结果: 构造一个空队列Q。 GetHead_Sq(Q,&e) 初始条件: 队列Q已存在且非空。 操作结果: 用e返回Q的队头元素。 EnQueue_Sq(&Q,e) 初始条件: 队列Q已存在。 操作结果: 插入元素e为Q的新的队尾元素。 DeQueue_Sq(&Q,&e) 初始条件: 队列Q已存在且非空。 操作结果: 删除Q的队头元素,并用e返回其值。 } ii.ADTSORT{ 数据对象: D=随机函数产生的100000个数据元素; 基本操作: intRandomNum();-----------------------产生随机数 voidInsertSort(structelementa[],intn);--直接插入排序 voidShellSort(structelementa[],intn);----希尔排序 voidInsertSort1(structelementa[],intn);---折半排序 intHashSort(structelementa[],intl,inth);----哈希排序 voidQuickSort(structelementa[],intn);----快排 voidMergeSort(structelementa[],intl,inth);---二路归并 voidradixSort(structelementa[],intn);----基数排序 voidHeapSort(structelementa[],inti,intm);----堆排序 }ADTSORT 2)主程序流程 3)程序模块(函数)之间的层次调用关系图 2.详细设计(实现程序模块的具体算法) 1)用到的数据类型定义如下: typedefstructhnode {intdata; structhnode*next; }HNODE; typedefstructpoint {structhnode*pt; }POINT; //基数排序的结点 structNode {charkey[D]; RadixNode*next; }; structNodeRandArrayR[MAXSIZE+1]; //基数排序用到的Node型的队列 typedefstructQueueNode {RadixNode*f;/*队列的头指针*/ RadixNode*e;/*队列的尾指针*/ }Queue; Queuequeue[R]; //定义链表LinkList,存放关键字 typedefstructLinkList{ intkey; }LinkList; 2)基数排序算法的流程图 3.调试分析 内容包括: a)调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析;b)算法的时空分析——包括基本操作和相关算法的时间复杂度和空间复杂度的分析以及改进设想;c)经验和体会等) a)调试部分问题解决 1.在哈希排序的某一次测试中,MAXSEZE排序规模为100000时没有错误,但规模为100或10000时如下位置出现下示错误: 中断后调试发现,L[I].key=6671,j的值为3335,过多的大于了100,导致(p+j)->pt超过了一般哈希表的长度。 为了解决这个问题,可以做一个简单分析。 在上面/2的情况下当规模小于等于16383时都不能够正常运行。 当排序数据规模较大时,j可以取得较大的数值,而产生的随机数最大为32767,为了能够在小规模数据排序时不出错,可取j=L[i].key/999,此时能够处理规模为1000的情况(j的值在0-998之间),但此时冲突的次数会增加,所以会花费较多的运行时间。 2.在基数排序中,同过atoi()函数将字符转换成数字时竟然出现k=70两位数的结果(k应在0-9之间),导致程序产生完随机数并处理完后,无法接着顺利运行排序这一过程。 解决办法是为p->key[j]另赋值给一个一维数组,并强制ss[1]=’\0’,这样就确保了k中转换后的值就是刚刚j位置对应的值,而不会无意连接到上次的结果上。 B)部分排序算法时空分析 直接插入排序算法分析: 该算法的时间复杂度为O(n*n).直接插入排序是稳定的排序方法。 当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。 Shell排序算法分析: Shell排序算法的时间复杂度分析比较复杂,实际所需的时间取决于各次排序时增量的个数和增量的取值。 当n较大时,比较和移动的次数约在nl.25到1.6n1.25之间。 由于Shell排序算法是按增量分组进行的排序,所以Shell排序算法是一种不稳定的排序算法。 Quick排序算法分析: 快速排序主体算法时间运算约为O(log2n),划分子区函数运算量约为O(n),所总时复杂度为O(nlog2n).因为快速排序的记录移动次数不大于比较的次数,所以快速排序的最坏时间复杂度应为0(n2),最好时间复杂度为O(nlgn)。 HeapSort排序算法分析: 堆排序中heap算法的时间复杂度与堆所对应的完全二叉树的深度[log2n]+1相关,而heapsort中对heap的调用数量级为n,所以整个堆排序的时间复杂度为O(nlog2n)。 堆排序是不稳定的。 3.经验体会 做这次综合实验让我感受很深,也才明白掌握知识、运用知识不是在课堂上,而是在课下。 课下没有人逼着我们去看书,全凭自觉,遇到问题,自己想办法解决,在这样一个反复发现问题、分析问题和解决问题的过程中掌握知识,也是在这样一个过程中知道以前学习的知识是来干什么用的,也正因为这样的过程才觉得有意思,有继续学习的动力。 总的来说在本次实验中我走的路是很弯曲的,因为没有按照合适的步骤来进行,忽略了前期概要设计和详细设计的关键性步骤,差不多一开始就陷进了代码里面,导致后期调试小问题小漏洞花了巨多时间。 当我回头去写需求分析、概要设计和详细设计部分的内容时,感受最深的就是,如果前期花了一天来做这些事,那么后期在代码的编写过程中就不会“捉襟见肘”,这一段调好了那一段代码又有问题,而且都有花不少时间去修复,慢慢的去提高它的健壮性。 “磨刀不误砍柴工”,真是这个道理。 此外,代码编写过程中难免会出问题,懂得去调试程序也是很重要的。 在学数据结构以前,只知道去读运行时报的错,然后根据错误提示一行一行的去看代码,由于都是些小程序,没觉得有什么大麻烦。 这次,我发现这种方式已经很难行的通了。 有的时候,编译能通过,但出现死循环,或者程序无故死掉,我也才发现,原来加断点,F10,F11配合起来调试,基本上什么问题都能够解决,用的还挺爽。 以前都是听老师讲调试调试,现在才知道调试,观察变量、指针的情况是何其重要。 我在整个过程中还是比较注重代码的注释和缩进,这样无论实在调试还是请其他人帮我们看程序时都带来了很大好处。 请其他人看自己程序中的错误是一个好习惯,因为很多错误,我们冥思苦想几个小时,心中甚至抱着一团怒火,但也去旁边人一看,竟然是一个很小很小的错误,然后一起发感叹。 在学习中互相帮助,占用不了多少时间,却可以解决很多问题。 4.用户使用说明 (如何使用你编写的程序,详细列出每一步的操作步骤) 运行时直接在vs按F5或ctrl+F5键运行即可看到程序的运行结果。 为了便于查看排序前后及各种排序算法之间排序结果,程序将会在原目录下建立一下9个文本文件Random.txt(产生的随机数排序前的结果)、InsertSort.txt(直接插入排序之后的结果)、InsertSort1.txt(折半排序的结果)。 点击调试图标开始调试运行程序。 不出意外,出现下示控制台,由于第一、二排序都是插入排序,所以速度比较慢,请耐心等待。 下图为成功执行后的界面,现在可以去到文件夹下查看生成的9个文件。 下图分别为排序的100000个随机数的部分结果截图,Random.txt,HashSort.txt,RadixSort.txt,HeapSort.txt,InsertSort.txt,MergeSort.txt。 第三部分结果与讨论 实验结果分析(包括数据处理、实验现象分析、影响因素讨论、综合分析和结论等) 程序设计类实验: 包括原程序、输入数据、运行结果、实验过程发现的问题及解决方法等; 分析与设计、软件工程类实验: 编制分析与设计报告,要求用标准的绘图工具绘制文档中的图表。 系统实施部分要求记录核心处理的方法、技巧或程序段; 其它实验: 记录实验输入数据、处理模型、输出数据及结果分析 测试结果(列出测试结果,包括输入和输出。 这里的测试数据应该完整而严格,最好多于需求分析中所列) 本实验不需要人工输入任何数据,由系统产生的100000个随机数作为需要排序的数据来源。 下图为程序某一次运行结果: (都已排好序) 其他测试结果,由于都是随机数,没有必要再贴图了。 总之,这次关于各种排序的综合实验不仅仅让我牢牢掌握了这几种内排序算法,通过走完这一个流程,让我懂得如何去组织、去描述、去调试一个程序。 ----------------------------------------------------------------------- 实验报告评语及成绩(请按优,良,中,及格,不及格五级评定) 教师签字:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验报告 内排序 比较 实验 报告 排序