数据结构课程设计(排序)

《数据结构课程设计(排序)》由会员分享，可在线阅读，更多相关《数据结构课程设计(排序)（13页珍藏版）》请在金锄头文库上搜索。

1、数据结构课程设计排序综合学生姓名：学生学号：院係）：计算机科学与信息技术学院年级专业：指导教师：付丹丹二O年十二月题目排序综合1、课程设计的目的1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操 作实现算法，以及它们在程序中的使用方法。2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）问题描述:用程序实现多种排序算法基本要求：利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法

2、进行排序。要求：至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。如果采用4种或4种以上的方法者，可适当加分。3、主要参考文献1刘大有等，数据结构（C语言版），高等教育出版社2严蔚敏等，数据结构（C语言版），清华大学出版社3William Ford， William Topp,Data Structure with C+清华大学出版社4苏仕华等，数据结构课程设计，机械工业出版社4、课程设计工作进度计划第1天完成方案设计与程序框图第2、3天编写程序代码第4天程序调试分析和结果第5天课程设计报告和总结学生（签字）:接受任务时

3、间：年 月 日课程设计成绩评定表题目名称排序综合评分项目分值得分评价内涵工 作 表 现 20%01学习态度6遵守各项纪律，工作刻苦努力，具有良好的科学 工作态度。02科学实践、调研7通过实验、试验、查阅文献、深入生产实践等渠 道获取与课程设计有关的材料。03课题工作量7按期圆满完成规定的任务，工作量饱满。能35%04综合运用知识的能力10能运用所学知识和技能去发现与解决实际问题， 能正确处理实验数据，能对课题进行理论分析， 得出有价值的结论。05应用文献的能力5能独立查阅相关文献和从事其他调研；能提出并 较好地论述课题的实施方案；有收集、加工各种 信息及获取新知识的能力。06设计（实验）能力，

4、方案 的设计能力5能正确设计实验方案，独立进行装置安装、调试、 操作等实验工作，数据正确、可靠；研究思路清 晰、完整。07计算及计算机应用能力5具有较强的数据运算与处理能力；能运用计算机 进行资料搜集、加工、处理和辅助设计等。08对计算或实验结果的分析 能力（综合分析能力、技 术经济分析能力）10具有较强的数据收集、分析、处理、综合的能力。45%09插图（或图纸）质量、篇 幅、设计（论文）规范化 程度5符合本专业相关规范或规定要求；规范化符合本 文件第五条要求。10设计说明书（论文）质量30综述简练完整，有见解；立论正确，论述充分， 结论严谨合理；实验正确，分析处理科学。11创新10对前人工作

5、有改进或突破，或有独特见解。成绩摘要数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关 系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数 据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨 论在该类数据上执行的运算才有意义。在许多类型的程序的设计中，数据结构的 选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困 难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时 候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根 据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构

6、都是 非常重要的。排序算法是数据结构学科经典的内容，其中内部排序现有的算法有 很多种，其中包含冒泡排序，直接插入排序，简单选择排序，希尔排序，快速排 序，堆排序等，各有其特点。对排序算法比较的分析可以遵循若干种不同的准则， 通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较 次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符 串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动 记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比 较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复 杂性的度量。1

7、概要1.1 设计目的数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计 算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机 软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数 据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系 统工程等各种领域。学习数据结构与算法是为了将实际问题中涉及的对象在计算 机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进 学生的综合应用能力和专业素质的提高。1）本演示程序对以下 6种常用的内部排序算法进行实测比较：冒泡排序， 直接插入排序，简单选择排序，快速排序，希尔排序，

8、堆排序；2）待排序表的元素的关键字为整数。比较的指标为有关键字参加的比较次 数和关键字的移动次数（关键字交换记为 3 次移动）；3）演示程序以以用户和计算机的对话方式执行，在计算机终端上显示提示 信息，对随机数组进行排序，并输出比较指标值；4）最后对结果作出简单分析。1.2 预期目标按要求输入不同的操作。输入后，根据不同的输入进行不同的操作，最终达 到对各算法进行比较的目的。通过此次课程设计主要达到以下目的了解并掌握数 据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发 过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用 所学的理论知识和方法独立分析和解

9、决问题的能力；训练用系统的观点和软件开 发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2排序算法2.1 各排序算法的特点1）冒泡排序冒泡排序的基本概念是：依次比较相邻的两个数，将大数放在前面，小数放在 后面。即首先比较第 1 个和第 2 个数，将大数放前，小数放后。然后比较第 2 个数和 第 3 个数，将大数放前，小数放后，如此继续，直至比较最后两个数，将大数放前， 小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。重复以上过程，仍 从第一对数开始比较 （因为可能由于第 2 个数和第 3 个数的交换， 使得第 1 个数不再 大于第 2 个数），将大数放前，小数放

10、后，一直比较到最小数前的一对相邻数，将大 数放前，小数放后，第二趟结束， 在倒数第二个数中得到一个新的最小数。 如此下去， 直至最终完成排序。由于在排序过程中总是大数往前放，小数往后放，相当于气泡往 上升，所以称作冒泡排序。2）直接插入排序每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍 然有序。第一趟比较前两个数 ,然后把第二个数按大小插入到有序表中 ; 第二趟把第三 个数据与前两个数从后向前扫描， 把第三个数按大小插入到有序表中； 依次进行下去， 进行了（n-1）趟扫描以后就完成了整个排序过程。3）简单选择排序（1）在一组元素ViVn-1中选择具有最小排序码的元素（2）

11、若它不是这 组元素中的第个元素，则将它与这一组元素中的第一个元素对调；（3）在这组元 素中剔除这个具有最小排序码的元素，在剩下的元素Vi+1Vn-1中重复执行 第（1）（2）步，直到剩余元素只有一个为止。4）快速排序首先检查数据列表中的数据数，如果小于两个，则直接退出程序。如果有超 过两个以上的数据，就选择一个分割点将数据分成两个部分，小于分割点的数据 放在一组，其余的放在另一组，然后分别对两组数据排序；5）希尔排序先取一个正整数d1n，把所有序号相隔dl的数组元素放一组，组内进行直 接插入排序；然后取d2vd1，重复上述分组和排序操作；直至di=1，即所有记录 放进一个组中排序为止；6）堆排

12、序堆排序是一树形选择排序，在排序过程中，将R1.N看成是一颗完全二叉 树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选 择最小的元素；堆的定义:N个元素的序列K1，K2, K3,，Kn.称为堆，当且 仅当该序列满足特性：KiK2i Ki K2i+l(l I；N/2)2.2 各算法的比较方法1. 稳定性比较插入排序、冒泡排序、简单选择排序及其他线形排序是稳定的 希尔排序、快速排序、堆排序是不稳定的2. 时间复杂性比较插入排序、冒泡排序、选择排序的时间复杂性为O(n2)其它非线形排序的时间复杂性为 O(nlog2n)线形排序的时间复杂性为O(n);3. 辅助空间的比较线形排序

13、的辅助空间为O(n),其它排序的辅助空间为O(1);4. 其它比较 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。当 n 较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插 入或冒泡排序。若待排序的记录的关键字在一个明显有限范围内时 ,且空间允许是用桶排 序。当 n 较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。当 n 较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间 允许的情况下，宜用归并排序。当 n 较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用 堆排序一、需求分

14、析利用随机函数产生N个随机整数（N = 500, 1000, 1500, 2000, 2500,30000）,利用直接插入排序、折半插入排序，起泡排序、 快速排序、选择排序、堆排序,基数排序七种排序方法（可添加其它 排序方法）进行排序（结果为由小到大的顺序）,并统计每一种排序 所耗费的时间（统计为图表坐标形式）。二、程序的主要功能1. 用户输入任意个数,产生相应的随机数2. 用户可以自己选择排序方式（直接插入排序、折半插入排序、 起泡排序、快速排序、选择排序、堆排序、基数排序）的一种3. 程序给出原始数据、排序后从小到大的数据,并给出排序所用 的时间。三、程序运行平台Visual C+ 6.0

15、 版本四、数据结构本程序的数据结构为线形表，线性顺序表、线性链表。1 、结构体：typedef structint *r; r指向线形表的第一个结点。r0闲置，不同的算法有不同的用处,如用作哨兵等。intlength; /顺序表的总长度Sqlist;2、空线性表Status InitSqlist(Sqlist &L)L.r=(int *)malloc(MAXSIZE*sizeof(int);/分配存储空间if(!L.r)printf(存储分配失败!);exit(0); /存储分配失败L.length=0;初始长度为0return OK;五、算法及时间复杂度(一)各个排序是算法思想：(1) 直接插入排序：将一个记录插入到已排好的有序表中，从而得 到一个新的，记录数增加 1 的有序表。(2) 折半插入排序：插入排序的