通用排序程序

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

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

3、后，以此类推，直至最后完成排序。函数流程图2.设计表示结构体类型成员成员digitalint digstruct digital *n extstri ngchar str20struct stri ng *n ext两种结构体类型中in t/char型成员用于存储用户输入的数或字符，next指针指向自身的结构体类型，当用户输入数或字符时,便生成一新节点，连接到单链表中，完成输入。节点中一部分用于存储数据，一部分用于存储下一节点的地址next 。3. 详细设计表示利用 if-else 语句根据输入的代表不同功能的数字来用不同的方法处理数据。 输入数字 1 时用数值排序方式处理数据； 输入数字

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

5、 语句和 while 语句达到对程序流程的循环控制。流程控制语句： for 语句，switch， while 语句等。这里用到了while 语句和 for 语句。For 语句的形式如下：for 语句形式：for （ 表达式 1；表达式 2； 表达式 3）执行过程：语句；首先计算“表达式1”（循环初值），且仅计算一次。每一次循环之前计算“表达 式 2”循环条件），如果其结果为真，则执行“语句”（循环体），并计算表达式 3”（循环增量）。否则，循环终止。While 语句形式：while （表达式 ）语句；它的执行过程：首先计算“表达式” 的值，如果为真，则执行语句” 。再次判断，直至“表达式”的值

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

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

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

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

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

11、程要在反复 的实践中积累经验，这中间需要自己的不断思考，查阅资料，不断改 进等等， 总之这次实践让我认识到自己编程的很多方面的欠缺， 同时 也让我收获颇丰。附录源程序清单：#include #include struct stringchar str20;struct string *next;struct digitalint dig;struct digital *next;void main()coutvv通用排序n;int type,n,i,j,flag=1;while(flag)coutvv请选择排序类型:1.按数值大小 2.按字符串大小H.cintype;coutn;if(type

12、=1) /数值排序struct digital *head,*tail,*newnode;int tp;/输入数据head = new digital;tail = head;for(i=0;itp;newnode-dig=tp;tail-next=newnode;tail=newnode;tail-next=NULL;coutvv数据输入完成.开始排序.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;/

13、输出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;istr;strcpy(newnode-str,str);tail-next=newnode;tail=newnode;tail-next=NULL;coutvv数据输入完成.开始排序.n;/排序struct string *p;char temp20;13for(int i=0;in-1;i+)p=head;fo

14、r(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;17coutvvn请选择:0.退出1.继续H.cin flag;测试数据：12，24，9，128, 3, 76,345运行结果:1.用户可根据系统提示和用户需要输入1 2的操作数字。3S藍霧序粪型d按数值知按林串犬小-2.当用户输入1时，系统执行数值排序方式。型据凳个：岀 .靛诈寧浪

15、 耕擇贾入一匸結1择 用.远自输辰9选 通U児ga竝排3诸按数値犬丿按字符串大小1 ：7 请堆续12 24 3 912B 76ISe 3451 继续-3.当用户输入2时，系统执行字符顺序排序。嚣劈楹:彈da按字符串大小2程序最后的测试结果输出为:C:PMjgram FilesXMicrosoft Visual StudioMvProjects 1 Debugl-eKe个数据请个数据请aw?据入 数输 个据M数i1 已继 小兀暫嗚 / 7 空-1 - 4 惓居 / 8 串址壤 奸日数入 我9个输 d 3已 力 4 / 大21 值肯噬 制卖卖请孑 J 孑-I - 惓惓居a汐请炷 蠶鱸卩逼1?岀序棘犧範公时熾个个義別己结诅己结炮择 9选选2选 3斶話共已已懸排i诂M枣数 必按8 -2 - 111:1 已继7 营-1 - 爭一舌8S4S n3数入9个输3已213己继 卖卖