通用排序程序

1、课 程 设 计 报 告 设计题目：通用排序程序学生姓名：专业班级：学 号：指导教师：完成日期：合肥工业大学计算机与信息学院目录（一）需求和规格说明3（二）设计31.设计思想32.设计表示43.详细设计表示5（三）用户手册7（四）测试及调试71.总结及反思72.附录10（一） 需求和规格说明题目：编一通用排序程序，程序可以对任意类型的数值常数或字符串构成的行进行排序，通过人机对话选择程序是按数值进行排序还是按字符顺序进行排序。排序是针对数据文件的。例如：初识数据为：12，24，9，128，3，76，345按数值大小排序应为：3，9，12，24，76，128，345按字符串大小排序应为：12，12

2、8，24，3，345，76，9（二） 设计1设计思想题目中要求利用人机对话实现选择程序是按数值进行排序还是按字符顺序进行排序，在这，可以利用if-else选择语句对程序进行编写，从而达到人机对话实现选择程序是按数值进行排序还是按字符顺序进行排序。在存储结构方面，以单链表为存储结构，因此，首先需要创建一个单链表，将待排序数据存储在单链表中，然后用指针实现关键字的从小到大的排序。而程序排序的基本思想是：数值排序与字符排序均采用链表的冒泡排序方式，外循环共循环n-1次，内循环实现数值的两两交换，在第i次外循环中，需要比较n-i+1次。在第一次外循环中将数值最大的数置于最后，以此类推，直至最后完成排序

3、。函数流程图函数流程图选择排序方式输入数字1，2若是1若是2选择数值排序方式选择字符排序方式输出排序结果选择退出继续若选择0若选择1结束2设计表示结构体类型成员成员digitalint digstruct digital *nextstringchar str20struct string *next两种结构体类型中int/char型成员用于存储用户输入的数或字符，next指针指向自身的结构体类型，当用户输入数或字符时，便生成一新节点，连接到单链表中，完成输入。节点中一部分用于存储数据，一部分用于存储下一节点的地址next。3.详细设计表示l 利用if-else语句根据输入的代表不同功能的数字

4、来用不同的方法处理数据。输入数字1时用数值排序方式处理数据；输入数字2时用字符方式排序法处理数据。输入数字0时退出程序，输入数字1时继续程序。l 虽然排序有不同的方法，但是，其基本操作不外乎两种： （1） 关键字大小的比较。 （2） 改变记录的位置。具体处理方式依赖于记录的存储形式，对于顺序型记录，一般移动记录本身，而链式存储的记录则通过改变指向记录的指针实现重定位。l 本程序的主函数通过定义一个链表结构体指针head，用以指向链表头结点；设计一个循环输入变量，控制相关方法的调用来实现链表的建立及对数据的排序。l 本程序通过if-else.选择语句对程序进行编写，从而达到人机对话实现选择程序是

5、按数值进行排序还是按字符顺序进行排序。l 在控制流程过程中，选择for语句和while语句达到对程序流程的循环控制。l 流程控制语句：for语句，switch，while语句等。这里用到了while语句和for语句。For语句的形式如下：for语句形式： for (表达式1； 表达式2； 表达式3) 语句； 执行过程： 首先计算“表达式1”（循环初值），且仅计算一次。每一次循环之前计算“表达 式2”（循环条件），如果其结果为真，则执行“语句”（循环体），并计算“表达式3”（循环增量）。否则，循环终止。While语句形式：while (表达式) 语句； 它的执行过程：首先计算“表达式” 的值，如

6、果为真，则执行“语句” 。再次判断，直至“表达式”的值为假结束循环。l 本程序的主函数通过定义一个链表结构体指针head，用以指向链表头结点；设计一个循环输入变量，控制相关方法的调用来实现链表的建立及对数据的排序。（三） 用户手册l 程序运行时，自动输出“通用排序”；l 首先提示“请选择排序类型:1.按数值大小2.按字符串大小”，用户输入1/2选择排序类型；l 程序提示“共有多少个数据:”用户输入数据个数；l 对于类型1的数值排序，程序提示输入n个数据，用户输入完成后，输出“数据输入完成. 开始排序.”然后输出排序结果；l 对于类型2的字符串排序，程序提示输入n个数据，用户输入完成后，输出“数

7、据输入完成. 开始排序.”然后输出排序结果；l 程序最后提示“请选择:0.退出 1.继续”用户根据提示选择0/1选择退出或继续。（四） 调试及测试 总结及反思在第三学期第一次做课程设计，一开始有些期待和紧张。在确定的课程设计的选题以后，刚开始准备入手选题时，确实是有些盲目和无助，也许这就是所谓的“万事开头难”吧，一开始忙碌了一上午也是一无所获，后来觉得自己应该先把总体框架设计出来，再去关注小细节，于是我开始静下心来构思整个程序的流程，后来经过一番思考，我确定整体框架大概是这样：主函数里的最外层采用while语句的形势，一开始设表达式的值为1，到程序尾再让用户选择1/0从而选择是继续还是退出，接

8、着对于内层，程序中要求利用人机对话实现选择程序是按数值进行排序还是按字符顺序进行排序，在这，可以利用if-else选择语句对程序进行编写，用户选择1/2选择是按数值进行排序还是按字符顺序进行排序，对于数值和字符的排序，都用链表存储用户输入的信息，每一次输入的信息都作为节点的data部分，然后均对链表进行冒泡排序，然后对链表进行输出，显示最终的排序结果。在程序的算法部分，主要就是链表的冒泡排序，它是最基本的排序方法之一，比之于其他的排序方法而言思路更清晰操作更简单。一开始进行排序时，面对众多的排序方法，不知道选择哪一种方法进行实例操作，一开始我选择的是直接选择排序，该算法的基本思想是控制选择n-

9、1次最小元素，用一个变量指示当前子表中最小元素，然后用后面的各元素与最小元素来比较，找出比当前最小数更小的元素，然后将最小数放到最终的位置上。但是我后来查阅资料发现直接选择查找的算法是不稳定排序，因为关键字相同的元素在排序过程中可能会交换次序，而且通过模拟执行可发现：排序过程中可能存在许多次的重复比较，因而造成时间复杂度的增大，基于这两点考虑，我选择了冒泡排序，冒泡排序也是整个程序中的核心算法。一开始编写冒泡排序时，之前学的算法有些遗忘，后来我又查阅资料，套用冒泡排序的算法模板，最终成功完成了对于数值与字符串部分的排序。在基于交换思想的排序算法中，冒泡排序是较为简单的一种，而且冒泡排序显然是稳

10、定的排序算法，而冒泡排序的基本思想是：从一端开始，逐个比较相邻的元素，发现倒序即交换，每一次将最大的元素交换到其最终位置上，然后重复n-1次冒泡操作。在完成这次设计的过程中，我意识到自己在很多方面都有漏洞，但是在完成这次程序设计的过程中，也让我学习到了不少知识，同时也巩固了以前所学的知识，这次程序设计也培养了我自己独立思考的能力，同时也锻炼了我的逻辑思维，同时我也认识到，仅仅有书本上的理论知识，是远远不够的，要学会将理论运用于实践，在反复的实践中将理论运用到恰当好处，这次的编程也让我认识到，编程要在反复的实践中积累经验，这中间需要自己的不断思考，查阅资料，不断改进等等，总之这次实践让我认识到自

11、己编程的很多方面的欠缺，同时也让我收获颇丰。附录源程序清单：#include<iostream.h>#include <string.h>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)cout<<"请选择排序类型:1.按数值大小2.按字符串大小 "cin>

12、>type;cout<<"共有多少个数据:"cin>>n;if(type=1) /数值排序struct digital *head,*tail,*newnode;int tp; /输入数据head = new digital;tail = head;for(i=0;i<n;i+) newnode = new digital;cout<<"已输入n个数据.请继续 "cin>>tp;newnode->dig=tp;tail->next=newnode;tail=newnode;tail-

13、>next=NULL;cout<<"数据输入完成. 开始排序.n" /排序struct digital *p;for(i=0;i<n-1;i+)p=head;for(j=0;j<n-i-1;j+) p=p->next;if(p->dig > p->next->dig) tp=p->dig;p->dig=p->next->dig;p->next->dig=tp;/输出cout<<"排序结果如下:n"p=head->next;while(p!=N

14、ULL) cout<<" "<<p->dig;p=p->next;else/字符串排序struct string *head,*tail,*newnode;char str20; /输入数据head = new string;tail = head;for(i=0;i<n;i+) newnode = new string;cout<<"已输入n个数据.请继续 "cin>>str;strcpy(newnode->str,str);tail->next=newnode;tail=n

15、ewnode;tail->next=NULL;cout<<"数据输入完成. 开始排序.n" /排序struct string *p;char temp20;for(int i=0;i<n-1;i+)p=head;for(int j=0;j<n-i-1;j+) p=p->next;if(strcmp(p->str,p->next->str)=1) strcpy(temp,p->str);strcpy(p->str,p->next->str);strcpy(p->next->str,temp);/输出cout<<"排序结果如下:n"p=head->next;while(p!=NULL) cout<<" "<<p->str;p=p->next;cout<<"n请选择:0.退出 1.继续 "cin>>flag;测试数据： 12，24，9，128，3，76，345运行结果：1