数据结构课程设计---排序算法的实现.doc

课课 程程 设设 计（论文）计（论文） 课程名称 数据结构 题目名称 排序算法的实现 学生学部（系） 艺术设计与计算机 专业班级 10 计算机 1 班 2011 年 12 月 05 日 广东工业大学华立学院广东工业大学华立学院 课程设计（论文）任务书课程设计（论文）任务书 一、课程设计（论文）的内容一、课程设计（论文）的内容 排序算法的实现 二、课程设计（论文）的要求与数据二、课程设计（论文）的要求与数据 （1）需求分析 （2）概要设计 （3）详细设计 （4）编程实现 （5）测试: 提供数个测试用例 （6）符合撰写规范设计的必要说明文档 三、课程设计（论文）应完成的工作三、课程设计（论文）应完成的工作 （1）根据要求完成课题； （2）程序书写符合规范，程序设计完善； （3）对程序进行初步的测试； （4）程序运行结果和过程的界面截图； （5）根据设计规范撰写报告并按时提交； （6）设计内容用a4纸打印并按要求装订。 题目名称排序算法的实现 学生学部（系）艺术设计与计算机学部 专业班级10 计算机 1 班 姓 名蔡晶晶 学 号 21011010102 1 四、课程设计（论文）进程安排四、课程设计（论文）进程安排 序号设计（论文）各阶段内容地点起止日期 1 搜集资料图书馆 12.05-12.10 2 需求分析图书馆 12.10-12.14 3 概要设计图书馆 12.14-5.17 4 详细设计图书馆 12.17-12.20 5 程序实现图书馆 12.20-12.29 6 系统测试、运行机房 12.19-12.30 7 提交报告 12.30 五、应收集的资料及主要参考文献五、应收集的资料及主要参考文献 1 朱战立.数据结构.北京:电子工业出版社，2010 2 吴伟民，严蔚敏. 数据结构(c 语言版) .北京: 清华大学出版社，2009 发出任务书日期：发出任务书日期： 20112011 年年 1212 月月 1212 日日 指导教师签名：指导教师签名： 计划完成日期：计划完成日期： 20112011 年年 1212 月月 3030 日日 教学单位责任人签章：教学单位责任人签章： 目录目录 1 1 序言序言 1 1 1.1 内容 .1 1.2 目的 .1 2 2 需求分析需求分析1 1 2.1 需求分析 .1 2.2 功能分析.2 3 3 概要设计概要设计 2 2 4 4 详细设计详细设计 3 3 5 5 程序实现程序实现4 4 总结总结8 8 参考文献参考文献9 9 1 1 1 序言序言 1.11.1 内容内容 排序是对数据元素序列建立某种有序序列的过程。排序的方法有许多种，不同的排序方 法特点不同。学习排序，主要有两点，一个是每种排序的算法思想，另一个是每种排序方法 的性能特点。 1.21.2 目的目的 通过学习排序算法，我们可以掌握各种排序的基本思想、掌握各种排序方法的算法实现、 掌握各种排序方法的优劣分析及花费的时间计算、掌握各种排序方法所适应的不同场合等等。 2 2 需求分析需求分析 2.12.1 需求分析需求分析 排序是对数据元素序列建立某种有序排列的过程。准确的说，排序是把一个数据元素序 列整理成按关键字递增（或递减）排列的过程。所以说，排序在生活中随处可见，并且非常 重要。 2 2.22.2 功能分析功能分析 3 3 概要设计概要设计 【直接插入排序的基本思想】顺序的把待排序的数据元素按其关键字值的大小插入到已排序 数据元素子集合的适当位置。子集合的数据元素个数从只有一个数据元素开始，逐次增大， 当子集合大小最终和集合大小相同时排序完毕。 【直接选择排序的基本思想】从待排序的数据元素集合中选取关键字最小的数据元素并将它 与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置上数据元素的 集合中选取关键字最小的数据元素，并将它与数据元素集合中的第二个数据元素交换位置； 重复如此，直到数据元素集合中只剩一个数据元素为止。 【冒泡排序的基本思想】设数组 a 中存放了 n 个数据元素，循环进行 n-1 趟如下的排序过程： 第一趟时，依次比较相邻两个数据元素 ai.key 和 ai+1.key（i=0,1,2，n-2） ， 若为逆序，即 ai.keyi+1.key，则交换两个数据元素，否则不交换，这样数值最大的 数据元素将被放置在 an-1中；第二趟时，数据元素个数减 1，即数据元素个数为 n-1，操 作方法和第一趟的类似，这样整个 n 个数据元素集合中数值次大的数据元素将被放置在 an-2中；当第 n-1 趟结束时，整个 n 个数据元素集合中次小的数据元素将被放置在 a1 开始 需要排序的数据元素 主方法： 直接插入排序方法 直接选择排序方法 冒泡排序方法 结束 3 中，a0中放置了最小的数据元素。 4 4 详细设计详细设计 直接排序算法，在已经排好序的序列中查找待插入的元素的插入位置，并将待插入元素 插入到有序列表的过程。 直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环 为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较， 所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较， 直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。值得注意的是， 我们必需用一个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比 较数值置入比它小的数值的后一位 插入排序类似玩牌时整理手中纸牌的过程。插入排序的 基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当 位置，直到全部记录插入完毕为止。 直接插入排序的作法是：每次从无序表中取出第一个元素，把它插入到有序表的合适位 置，使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第 二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行 下去，进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序属于稳定的排序，时 间复杂性为 o(n2)，空间复杂度为 o(1)。 直接选择排序也是一种简单的排序方法，它的基本思想是：第一次从 r0rn-1中选 取最小值，与 r0交换，第二次从 r1rn-1中选取最小值，与 r1交换，第 i 次从 ri-1rn-1中选取最小值，与 ri-1交换，.，第 n-1 次从 rn-2rn-1中 选取最小值，与 rn-2交换,总共通过 n-1 次,得到一个按排序码从小到大排列的有序序列。 冒泡排序的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。 即在第一趟：首先比较第 1 个和第 2 个数，将小数放前，大数放后。然后比较第 2 个数和第 3 个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。 至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由 于第 2 个数和第 3 个数的交换，使得第 1 个数不再小于第 2 个数） ，将小数放前，大数放后， 一直比较到倒数第二个数（倒数第一的位置上已经是最大的） ，第二趟结束，在倒数第二的 位置上得到一个新的最大数（其实在整个数列中是第二大的数） 。如此下去，重复以上过程， 直至最终完成排序。 由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升， 所以称作冒泡排序。用二重循环实现，外循环变量设为 i，内循环变量设为 j。外循环重复 9 次，内循环依次重复 9，8，.，1 次。每次进行比较的两个元素都是与内循环 j 有关的， 它们可以分别用 aj和 aj+1标识，i 的值依次为 1,2,.,9，对于每一个 i, j 的值依次 为 1,2,.10-i。 4 5 5 程序实现程序实现 直接插入排序算法 #include typedef int keytype; typedef struct keytype key; datatype; void insertsort(datatype a,int n) int i,j; datatype temp; for(i=0;i-1 typedef struct keytype key; datatype; void selectsort (datatype a,int n) int i,j,small; datatype temp; for(i=0;i typedef int keytype; typedef struct keytype key; datatype; 7 void bubblesort (datatype a,int n) int i,j,flag=1; datatype temp; for(i=0;iaj+1.key) flag=1; temp=aj; aj=aj+1; aj+1=temp; void main(void) datatype test6=1,6,0,9,4,6; int i,n=6; bubblesort(test,n); for(i=0;in;i+) printf(“%d “,testi.key); 8 总结总结 课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力 的重要环节,是对我们的实际工作能力的具体训练和考察过程。随着科学技术发展的日新月 异，当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握程 序开发技术是十分重要的，因此做好课程设计是十分必要的。 回顾起此次课程设计，至今 我仍感慨颇多，的确，自从拿到题目到完成整个编程，从理论到实践，在整整一个月的日子 里，可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在 书本上所没有学到过的知识。 从这次的课程设计中，我发现我理解和解决问题的能力以及实践能力都有了很大的提高， 自学能力也获得了提升。做了这次课程设计，我觉得课程设计这种形式才是我们需要的，可 以让我们学到很多，包括书本内的，以及课外的。在学习排序算法的时候，读了书上的算法 描述，觉得自己都会了，但到真正到编译去实现他的时候，却不是那么简单就能成功的，总 会有这样那样的差错，只能一次一次改，等到程序终于正确运行的时候，才算真正会了这些 算法。理论和实际总是有差别的，不去做是体会不出来的。坐在电脑前才真正知道自己会不 会，眼高手低是要不得的。 通过这次课程设计，使说我明白到，要做好一个课程设计，首先那要有一个完整的思路， 才能做出一个好的程序。并且一个好的程序不是一次就能完成的，这需要修改许多次才能完 成的。而我这次的程序实现则是排序，排序是对数据元素序列建立某种有序序列的过程。准 确的说，排序是把一个数据元素序列整理成按关键字递增（或递减）排列的过程。所以说， 排序在生活中随处可见，并且非常重要。学习排序，主要有两点，一个是每种排序的算法思 想，另一个是每种排序方法的性能特点。 回想起此次的程序设计，我仍感慨颇多。从老师给程序设计题目到完成整个编程，从理 论到实践，在整整一个月的日子里，我学到很多很多的东西。通过此次的程序设计，我不仅 巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。经过这次程序设 计，使我明白到理论与实际相结合非常重要，平时我们只是学到理论知识，回到宿舍也没有 去练习，导致我们动手能力普遍偏弱。只有自己亲自去做。才能提高自己的实际动手能力和 独立思考问题的能力。 通过实践的学习，我认识到学好计算机要重视实践操作，不仅仅是学习数据结构，还是 其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注视实践操作，使 自己便好地学好计算机。 9 参考文献参考文献 1 朱战立.数据结构.北京:电子工业出版社，2010 2 吴伟民，严蔚敏. 数据结构(c 语言版) .北京: 清华大学出版社，2009 3 朱战立.数据机构使用 c 语言典型题解与上机实验指导.西安：西安交通大学出版社， 2004 4 sartaj sahni.数据结构算法与应用c+语言描述（英文版）.北京：机械工业出版社， 1997 5 朱战立.数据结构（java 语言描述）.北京：清华大学出版社，2005 心 得 体 会 这次的课程设计，看着简单，做着难，一直都是自己眼高手低，不过，通过 这次的课程设计，知道，努力付出总是有收获的，再苦再累也是值了。做了这次 课程设计，我觉得课程设计这种形式才是我们需要的，可以让我们学到很多，包 括书本内的，以及课外的。在学习排序算法的时候，读了书上的算法描述，觉得 自己都会了，但到真正到编译去实现他的时候，却不是那么简单就能成功的，总 会有这样那样的差错，只能一次一次改，等到程序终于正确运行的时候，才算真 正会了这些算法。理论和实际总是有差别的，不去做是体会不出来的。坐在电脑 前才真正知道自己会不会，眼高手低是要不得的。 通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识 是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论， 才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。 经过这次课程设计，我好好的看了一遍书，对书中的算法思想有了更深的了 解，虽然在应用中显得不是很自如，可这次的课程设计却给我带来了不可替代的 乐趣。也给我以