排序程序设计.doc

课 程 设 计 报 告（2013 -2014第2学期）课程设计类型： 软硬件设计 题 目： 通用排序程序 学 号： 121001260809 姓 名： 胡柳 专 业： 自动化，中美互认 指 导 教 师： 李建敦 课程设计日期： 2014.06.162014.06.20 目录1. 课题分析11.1 背景介绍11.2 需求分析12. 总体设计32.1 总体思路32.2 相关技术33. 详细设计43.1 设计原则43.2 模块设计44. 实现与测试54.1 实现环境54.2 模块实现54.3测试65. 总结与展望75.1 总结75.2 展望7参考文献9附录10答辩记录131. 课题分析1.1 背景介绍排序是数据处理中经常使用的一种重要运算。设文件由n个记录R1,R2,Rn组成，如n个学生记录，每个学生记录包括学号、姓名、班级等。n个记录对应的关键字集合为K1,K2,Kn，如学生的学号。所谓排序就是将这n个记录按关键字大小递增或递减重新排列。 当待排序记录的关键字均不相同时，排序结果是唯一的，否则排序结果不唯一。如果文件中关键字相同的记录经过某种排序方法进行排序后，仍能保持它们在排序之前的相对次序，则称这种排序方法是稳定的；否则，这种排序方法是不稳定的。 由于文件大小不同使排序过程中涉及的储存器不同，可将排序分成内部排序和外部排序两类。整个排序过程都在内存进行的排序，称为内部排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。内排序适用于记录个数不是很多的小文件，而外排序则适用于记录个数太多，不能一次性放入内存的大文件。 按策略划分，内部排序方法可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。几乎所有的排序都有两个基本的操作： （1）关键字大小的比较。 （2）改变记录的位置。具体处理方式依赖于记录的存储形式，对于顺序型记录，一般移动记录本身，而链式存储的记录则通过改变指向记录的指针实现重定位。 排序算法很多，不同的算法有不同的优缺点，没有哪种算法在任何情况下都是最好的。评价一种排序算法好坏的标准主要有两条： （1）执行时间和所需的辅助空间，即时间复杂度和空间复杂度； （2）算法本身的复杂程度，比如算法是否易读、是否易于实现。在本次实验设计程序中，编一通用排序程序，程序可以对任意类型的数值常数或字符串构成的行进行排序，通过人机对话选择程序是按数值进行排序还是按字符顺序进行排序。排序是针对数据文件的。例如初识数据为：12，24，9，128，3，76，345按数值大小排序应为：3，9，12，24，76，128，345按字符串大小排序应为：12，128，24，3，345，76，9需要将数据文件按数值大小进行排序，以及按字符大小进行排序。1.2 需求分析利用if-else语句根据输入的代表不同功能的数字来用不同的方法处理数据。输入数字1时用数值排序方式处理数据；输入数字2时用字符方式排序法处理数据。输入数字0时退出程序，输入数字1时继续程序。虽然排序有不同的方法，但是，其基本操作不外乎两种： （1）关键字大小的比较。 2（2）改变记录的位置。具体处理方式依赖于记录的存储形式，对于顺序型记录，一般移动记录本身，而链式存储的记录则通过改变指向记录的指针实现重定位。由本次课程设计的课题内容分析可得，解决问题的实际就是要建立一个单链表，将待排序的整型数据以结点的形式存储在建立的单链表中。然后，依次对单链表中的结点数据进行简单选择排序，其中排序为从大到小排序用这种方法实现所要求的排序方式得到结果。162. 总体设计2.1 总体思路程序中要求利用人机对话实现选择程序是按数值进行排序还是按字符顺序进行排序，在这，可以利用if-else选择语句对程序进行编写，从而达到人机对话实现选择程序是按数值进行排序还是按字符顺序进行排序。本程序设计关于排序的基本思想是：链式简单选择排序的是每一趟在n-i+1（i=1,2,.,n-1)个记录中选取关键字最大或最小的记录作为有序序列中第i个记录。本课程设计中以单链表为存储结构，待排序的数据由伪随机函数产生。因此，首先需要创建一个单链表，将待排序数据存储在单链表中，然后用指针实现关键字的从大到小的排序。2.2 相关技术流程控制语句：for语句，switch，while语句等。这里用到了while语句和for语句。For语句的形式如下：for语句形式： for (表达式1； 表达式2； 表达式3) 语句； 执行过程： 首先计算“表达式1”（循环初值），且仅计算一次。每一次循环之前计算“表达 式2”（循环条件），如果其结果为真，则执行“语句”（循环体），并计算“表达式3”（循环增量）。否则，循环终止。While语句形式：while (表达式) 语句； 它的执行过程：首先计算“表达式” 的值，如果为真，则执行“语句” 。再次判断，直至“表达式”的值为假结束循环。本程序的主函数通过定义一个链表结构体指针head，用以指向链表头结点；设计一个循环输入变量，控制相关方法的调用来实现链表的建立及对数据的排序。3. 详细设计3.1 设计原则本程序的主函数通过定义一个链表结构体指针head，用以指向链表头结点；设计一个循环输入变量，控制相关方法的调用来实现链表的建立及对数据的排序。本程序通过if-else.选择语句对程序进行编写，从而达到人机对话实现选择程序是按数值进行排序还是按字符顺序进行排序。在控制流程过程中，选择for语句和while语句达到对程序流程的循环控制。3.2 模块设计可以用流程图来展示函数流程图选择排序方式输入数字1，2若是1若是2选择数值排序方式选择字符排序方式输出排序结果选择退出继续若选择0若选择1结束4. 实现与测试4.1 实现环境本课程设计需要采用支持标准C/C+的Visual C+编译器（6.0或更高版本），并采用最基础的Windows xp控制台程序。4.2 模块实现1. 用户可根据系统提示和用户需要输入12的操作数字。图4.1 程序主界面2. 当用户输入1时，系统执行数值排序方式。图4.2 输出数值排序方式界面3. 当用户输入2时，系统执行字符顺序排序。图4.3 输出字符排序方式界面4.3测试程序最后的测试结果输出为：图4.4 由上图可得，当输入的数据为12，24，9，128，3，76，345，选择按数值大小排序是，输出的排序结果为：3，9，12，24，76，128，345，与题目中所要求得到的结果一致，当输入数据后选择按字符大小排序得到的结果为：12，128，24，3，345，76，9，也题目所要求所得到的数据一致。说明程序编写是正确的。5. 总结与展望5.1 总结本程序实现了对数据文件的排序功能，分别实现了按数值进行排序和按字符进行排序的功能，程序最后的运行结果，达到了题目所要求的通过人机对话实现选择程序是按数值进行排序还是按字符顺序进行排序。达到了课题的预期效果。此次课程设计中，我学习了简单选择排序。它是最基本的排序方法之一，比之于其他的排序方法而言思路更清晰操作更简单。对于用线性顺序表结构实现简单选择排序的算法描述，数据结构书本算法10.4已经给出了，而用链式存储结构来实现的区别是循环方式的差别：顺序表用一个for循环实现从下标1到n的排序，链式表的实现是一个while循环从头结点开始直到最后一个结点。5.2 展望第一次做课程设计，因此感到期待而又非常紧张，一个星期，短暂而忙碌，但却又充实、兴奋。当我把程序写出来，并运行正确后，我有种说不出的喜悦，虽然还有许多不足，但我对未来一片憧憬。 这次选课题，我选到的是“数据排序“，开始的我是无从下手，从网上搜了一气后一无所获，一味地依赖网上现成地答案使我毫无进展。后来，在同组同学地影响下，我开始静下心来回忆学过的知识 。终于，经过反复调试后，我终于找到了思路，经过同组同学的帮助与网上资料，我逐渐将程序设计成型，虽然还有许多缺陷，比如，设计后还是不能人性化地满足要求。虽然与想象中的还有很大差距，但我看到了希望，并决心一直努力下去。 一个星期的程序设计虽然马上就要结束的，但是它带给我的将会影响我今后的学习。在这次程序设计中，我不仅提高了编程的能力，也增加了我对这门课程的兴趣，虽然一周的程序设计很忙，但过得的很充实、很有意义。但也有许多不足的地方，如界面设计的还不够完美、还有一些最基本的知识没有完全掌握等等。这为我以后的学习提出了要求。通过此次课程设计，使我更加扎实的掌握了有关C+方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和对知识运用的不熟。在课程设计过程中，我不断发现错误，不断改正，不断领悟，不断获取，最后终于调试成功。这次课程设计终于顺利完成了，在设计中遇到了很多问题，通过查资料，终于游逆而解。课程设计诚然是一门专业课，给我很多专业知识以及专业技能上的提升，同时又是一门讲道课，一门辩思课，给了我许多道，给了我很多思，给了我莫大的空间。同时，设计让我感触很深。通过这次课程设计，我掌握了if和for的循环语句。我认为，在这学期的学习中，不仅培养了独立思考的能力，而且体现了合作的重要性。更重要的是，在课上，我们学会了很多学习的方法。而这是日后最实用的，真的是受益匪浅。要面对社会的挑战，只有不断的学习、实践，再学习、再实践。这对于我们的将来也有很大的帮助。回顾起此课程设计，至今我仍感慨颇多，从理论到实践，在这段日子里，可以说得是苦多于甜，但是可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，然后运用到生活中，最后才能真正为社会服务。在设计的过中遇到问题，可以说得是困难重重，但可喜的是最终都得到了解决。此次设计也让我明白了思路即出路，有什么不懂不明白的地方要及时请教或上网查询，只要认真钻研，动脑思考，动手实践，就没有弄不懂的知识，收获颇丰。参考文献1 殷人昆. 数据结构用面向对象方法与C+语言描述. 2版, 北京: 清华大学出版社, 2009.2 严蔚敏, 吴伟民. 数据结构. C语言版, 北京: 清华大学出版社, 1997.3 苏成, 姜薇, 苏仁科. C+程序设计教程. 1版, 北京: 清华大学出版社, 2013.4 谭浩强. C+程序设计(第二版). 北京: 清华大学出版社, 2012.5 谭浩强. C+程序设计题解与上机指导(第二版). 北京: 清华大学出版社, 2012.附录源程序为：#include#include struct string char str20;struct string *next;struct digital int dig;struct digital *next;void main() cout通用排序 n;int type,n,i,j,flag=1;while(flag)couttype;coutn;if(type=1) /数值排序struct digital *head,*tail,*newnode;int tp; /输入数据head = new digital;tail = head;for(i=0;in;i+) newnode = new digital;couttp;newnode-dig=tp;tail-next=newnode;tail=newnode;tail-next=NULL;cout数据输入完成. 开始排序.n; /排序struct digital *p;for(i=0;in-1;i+)p=head;for(j=0;jnext;if(p-dig p-next-dig) tp=p-dig;p-dig=p-next-dig;p-next-dig=tp;/输出coutnext;while(p!=NULL) cout dig;p=p-next;else/字符串排序struct string *head,*tail,*newnode;char str20; /输入数据head = new string;tail = head;for(i=0;in;i+) newnode = new string;coutstr;strcpy(newnode-str,str);tail-next=newnode;tail=newnode;tail-next=NULL;cout数据输入完成. 开始排序.n; /排序struct string *p;char temp20;for(int i=0;in-1;i+)p=head;for(int j=0;jnext;if(strcmp(p-str,p-next-str)=1) strcpy(temp,p-str);strcpy(p-str,p-next-str);strcpy(p-next-str,temp);/输出coutnext;while(p!=NULL) cout str;p=p-next;coutflag;另外一种程序编写#include #include #include using namespace std;const int LEN=1000;const int NUMLEN=10;struct Ele int n; char numNUMLEN;eleLEN; /结构体里面两个成员，n是整型，num是将n转化成的字符串void deal(int m) /deal函数用来将int型转化成字符串 int i; int tmpNUMLEN; int n=elem.n; int cou=0; while(n!=0) tmpcou=n%10; n=n/10; cou+; for(i=0;i0?1:-1;int cmpnum(const void *a,const void *b) return strcmp(*(struct Ele *)a).num,(*(struct Ele *)b).num)0?1:-1; /这两个函数是qsort调用的，你可以百度下qsort的意思，我就不多加阐述了int main()