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

《数据结构课程设计排序算法的实现.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计排序算法的实现.doc（14页珍藏版）》请在三一办公上搜索。

1、课 程 设 计（论文） 课程名称 数据结构 题目名称 排序算法的实现 学生学部（系） 艺术设计与计算机 专业班级 10计算机1班 2011 年12月05日广东工业大学华立学院课程设计（论文）任务书题目名称排序算法的实现学生学部（系）艺术设计与计算机学部专业班级10计算机1班姓 名蔡晶晶学 号21011010102一、课程设计（论文）的内容 排序算法的实现二、课程设计（论文）的要求与数据（1）需求分析（2）概要设计（3）详细设计（4）编程实现（5）测试: 提供数个测试用例（6）符合撰写规范设计的必要说明文档三、课程设计（论文）应完成的工作（1）根据要求完成课题；（2）程序书写符合规范，程序设计完

2、善；（3）对程序进行初步的测试；（4）程序运行结果和过程的界面截图；（5）根据设计规范撰写报告并按时提交；（6）设计内容用A4纸打印并按要求装订。四、课程设计（论文）进程安排序号设计（论文）各阶段内容地点起止日期1搜集资料图书馆12.05-12.102需求分析图书馆12.10-12.143概要设计图书馆12.14-5.174详细设计图书馆12.17-12.205程序实现图书馆12.20-12.296系统测试、运行机房12.19-12.307提交报告12.30五、应收集的资料及主要参考文献1 朱战立.数据结构.北京:电子工业出版社，2010 2 吴伟民，严蔚敏. 数据结构(C语言版) .北京:

3、清华大学出版社，2009发出任务书日期： 2011 年 12 月 12日 指导教师签名：计划完成日期： 2011 年 12 月 30 日 教学单位责任人签章：目录 1序言11.1内容11.2目的12 需求分析12.1需求分析12.2 功能分析23概要设计24详细设计35 程序实现4总结8参考文献91序言1.1内容排序是对数据元素序列建立某种有序序列的过程。排序的方法有许多种，不同的排序方法特点不同。学习排序，主要有两点，一个是每种排序的算法思想，另一个是每种排序方法的性能特点。1.2目的 通过学习排序算法，我们可以掌握各种排序的基本思想、掌握各种排序方法的算法实现、掌握各种排序方法的优劣分析及

4、花费的时间计算、掌握各种排序方法所适应的不同场合等等。 2 需求分析2.1需求分析排序是对数据元素序列建立某种有序排列的过程。准确的说，排序是把一个数据元素序列整理成按关键字递增（或递减）排列的过程。所以说，排序在生活中随处可见，并且非常重要。2.2 功能分析开始需要排序的数据元素主方法：直接插入排序方法直接选择排序方法冒泡排序方法结束3概要设计【直接插入排序的基本思想】顺序的把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。子集合的数据元素个数从只有一个数据元素开始，逐次增大，当子集合大小最终和集合大小相同时排序完毕。【直接选择排序的基本思想】从待排序的数据元素集合中

5、选取关键字最小的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置上数据元素的集合中选取关键字最小的数据元素，并将它与数据元素集合中的第二个数据元素交换位置；重复如此，直到数据元素集合中只剩一个数据元素为止。【冒泡排序的基本思想】设数组a中存放了n个数据元素，循环进行n-1趟如下的排序过程：第一趟时，依次比较相邻两个数据元素ai.key和ai+1.key（i=0,1,2，n-2），若为逆序，即ai.keyi+1.key，则交换两个数据元素，否则不交换，这样数值最大的数据元素将被放置在an-1中；第二趟时，数据元素个数减1，即数据元素个数为n-1，操作方法和第一趟

6、的类似，这样整个n个数据元素集合中数值次大的数据元素将被放置在an-2中；当第n-1趟结束时，整个n个数据元素集合中次小的数据元素将被放置在a1中，a0中放置了最小的数据元素。4详细设计 直接排序算法，在已经排好序的序列中查找待插入的元素的插入位置，并将待插入元素插入到有序列表的过程。 直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。值得注

7、意的是，我们必需用一个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位 插入排序类似玩牌时整理手中纸牌的过程。插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。 直接插入排序的作法是：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序属于稳定的排序

8、，时间复杂性为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个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，

9、大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。 由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，.，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用aj和a

10、j+1标识，i的值依次为1,2,.,9，对于每一个i, j的值依次为1,2,.10-i。5 程序实现直接插入排序算法#include typedef int KeyType;typedef structKeyType key; DataType;void InsertSort(DataType a,int n)int i,j; DataType temp; for(i=0;i-1 & temp.keyaj.key) aj+1=aj; j-; aj+1=temp;void main(void)DataType test6=1,4,6,3,9,10; int i,n=6; InsertSort(t

11、est,n); for(i=0;in;i+) printf(%d ,testi.key);直接选择排序算法#include typedef int KeyType;typedef structKeyType key;DataType;void SelectSort (DataType a,int n)int i,j,small; DataType temp; for(i=0;in-1;i+)small=i; for(j=i+1;jn;j+) if(aj.keyasmall.key) small=j; if(small!=i)temp=ai; ai=asmall; asmall=temp;voi

12、d main(void)DataType test6=1,6,0,9,4,6; int i,n=6; SelectSort(test,n); for(i=0;in;i+) printf(%d ,testi.key);冒泡排序算法#include typedef int KeyType;typedef structKeyType key;DataType;void BubbleSort (DataType a,int n)int i,j,flag=1; DataType temp; for(i=0;in&flag=1;i+)flag=0; for(j=0;jaj+1.key)flag=1;tem

13、p=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); 总结课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对我们的实际工作能力的具体训练和考察过程。随着科学技术发展的日新月异，当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握程序开发技术是十分重要的，因此做好课程设计是十分必要的。 回顾起此次课程设计，至今我

14、仍感慨颇多，的确，自从拿到题目到完成整个编程，从理论到实践，在整整一个月的日子里，可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。 从这次的课程设计中，我发现我理解和解决问题的能力以及实践能力都有了很大的提高，自学能力也获得了提升。做了这次课程设计，我觉得课程设计这种形式才是我们需要的，可以让我们学到很多，包括书本内的，以及课外的。在学习排序算法的时候，读了书上的算法描述，觉得自己都会了，但到真正到编译去实现他的时候，却不是那么简单就能成功的，总会有这样那样的差错，只能一次一次改，等到程序终于正确运行的时候，才算真正会了这些算法。理论和实际

15、总是有差别的，不去做是体会不出来的。坐在电脑前才真正知道自己会不会，眼高手低是要不得的。通过这次课程设计，使说我明白到，要做好一个课程设计，首先那要有一个完整的思路，才能做出一个好的程序。并且一个好的程序不是一次就能完成的，这需要修改许多次才能完成的。而我这次的程序实现则是排序，排序是对数据元素序列建立某种有序序列的过程。准确的说，排序是把一个数据元素序列整理成按关键字递增（或递减）排列的过程。所以说，排序在生活中随处可见，并且非常重要。学习排序，主要有两点，一个是每种排序的算法思想，另一个是每种排序方法的性能特点。 回想起此次的程序设计，我仍感慨颇多。从老师给程序设计题目到完成整个编程，从理

16、论到实践，在整整一个月的日子里，我学到很多很多的东西。通过此次的程序设计，我不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。经过这次程序设计，使我明白到理论与实际相结合非常重要，平时我们只是学到理论知识，回到宿舍也没有去练习，导致我们动手能力普遍偏弱。只有自己亲自去做。才能提高自己的实际动手能力和独立思考问题的能力。 通过实践的学习，我认识到学好计算机要重视实践操作，不仅仅是学习数据结构，还是其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。参考文献1 朱战立.数据结构.北京:电子工业出版社，2010 2 吴伟民，严蔚敏

17、. 数据结构(C语言版) .北京: 清华大学出版社，20093 朱战立.数据机构使用C语言典型题解与上机实验指导.西安：西安交通大学出版社，20044 Sartaj Sahni.数据结构算法与应用C+语言描述（英文版）.北京：机械工业出版社，19975 朱战立.数据结构（Java语言描述）.北京：清华大学出版社，2005心得体会这次的课程设计，看着简单，做着难，一直都是自己眼高手低，不过，通过这次的课程设计，知道，努力付出总是有收获的，再苦再累也是值了。做了这次课程设计，我觉得课程设计这种形式才是我们需要的，可以让我们学到很多，包括书本内的，以及课外的。在学习排序算法的时候，读了书上的算法描述

18、，觉得自己都会了，但到真正到编译去实现他的时候，却不是那么简单就能成功的，总会有这样那样的差错，只能一次一次改，等到程序终于正确运行的时候，才算真正会了这些算法。理论和实际总是有差别的，不去做是体会不出来的。坐在电脑前才真正知道自己会不会，眼高手低是要不得的。 通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。经过这次课程设计，我好好的看了一遍书，对书中的算法思想有了更深的了解，虽然在应用中显得不是很自如，可这次的课程设计却给我带来了不可替代的乐趣。也给我以后编程莫大的鼓励，通过老师的传授，我们可能只是学的，并不能深刻的理解，只有通过自己的努力，才能真正学的知识。数据结构是任何程序的基础，没有数据结构的支持，就没有程序的存在，至少说不会存在有价值的程序。有了数据结构的知识，再加上程序设计，这对我们以后的深入学习有了更大的帮助。总的来说，这次课程设计确实学到很多，不仅锻炼了我遇到问题解决问题的勇气和能力，还练就了遇到挫折不达目的不罢休的韧性，这在以后的工作与学习中将会非常重要。 2011年12月29日教师评语 2012年01月05日成绩及签名 2012年01月05日