排序程序设计

《排序程序设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计报告（2013-2014第2学期）课程设计类型：软硬件设计题目：通用排序程序学号：121001260809姓名：胡柳专业：自动化，中美互认指导教师：李建敦课程设计日期：2014.06.16—2014.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.课题分析

2、1.1背景介绍排序是数据处理中经常使用的一种重要运算。设文件由n个记录{R1,R2,,,,Rn}组成，如n个学生记录，每个学生记录包括学号、姓名、班级等。n个记录对应的关键字集合为{K1,K2,,,,,Kn}，如学生的学号。所谓排序就是将这n个记录按关键字大小递增或递减重新排列。当待排序记录的关键字均不相同时，排序结果是唯一的，否则排序结果不唯一。如果文件中关键字相同的记录经过某种排序方法进行排序后，仍能保持它们在排序之前的相对次序，则称这种排序方法是稳定的；否则，这种排序方法是不稳定的。由于文件

3、大小不同使排序过程中涉及的储存器不同，可将排序分成内部排序和外部排序两类。整个排序过程都在内存进行的排序，称为内部排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。内排序适用于记录个数不是很多的小文件，而外排序则适用于记录个数太多，不能一次性放入内存的大文件。按策略划分，内部排序方法可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。几乎所有的排序都有两个基本的操作：（1）关键字大小的比较。（2）改变记录的位置。具体处理方式依赖于记录的存储形式，对于顺序型记录，一般移

4、动记录本身，而链式存储的记录则通过改变指向记录的指针实现重定位。排序算法很多，不同的算法有不同的优缺点，没有哪种算法在任何情况下都是最好的。评价一种排序算法好坏的标准主要有两条：（1）执行时间和所需的辅助空间，即时间复杂度和空间复杂度；（2）算法本身的复杂程度，比如算法是否易读、是否易于实现。在本次实验设计程序中，编一通用排序程序，程序可以对任意类型的数值常数或字符串构成的行进行排序，通过人机对话选择程序是按数值进行排序还是按字符顺序进行排序。排序是针对数据文件的。例如初识数据为：12，24，9，

5、128，3，76，345按数值大小排序应为：3，9，12，24，76，128，345按字符串大小排序应为：12，128，24，3，345，76，9需要将数据文件按数值大小进行排序，以及按字符大小进行排序。21.2需求分析利用if-else语句根据输入的代表不同功能的数字来用不同的方法处理数据。输入数字1时用数值排序方式处理数据；输入数字2时用字符方式排序法处理数据。输入数字0时退出程序，输入数字1时继续程序。虽然排序有不同的方法，但是，其基本操作不外乎两种：（1）关键字大小的比较。2（2）改变记录

6、的位置。具体处理方式依赖于记录的存储形式，对于顺序型记录，一般移动记录本身，而链式存储的记录则通过改变指向记录的指针实现重定位。由本次课程设计的课题内容分析可得，解决问题的实际就是要建立一个单链表，将待排序的整型数据以结点的形式存储在建立的单链表中。然后，依次对单链表中的结点数据进行简单选择排序，其中排序为从大到小排序用这种方法实现所要求的排序方式得到结果。162.总体设计2.1总体思路程序中要求利用人机对话实现选择程序是按数值进行排序还是按字符顺序进行排序，在这，可以利用if-else选择语句对

7、程序进行编写，从而达到人机对话实现选择程序是按数值进行排序还是按字符顺序进行排序。本程序设计关于排序的基本思想是：链式简单选择排序的是每一趟在n-i+1（i=1,2,...,n-1)个记录中选取关键字最大或最小的记录作为有序序列中第i个记录。本课程设计中以单链表为存储结构，待排序的数据由伪随机函数产生。因此，首先需要创建一个单链表，将待排序数据存储在单链表中，然后用指针实现关键字的从大到小的排序。2.2相关技术流程控制语句：for语句，switch，while语句等。这里用到了while语句和fo

8、r语句。For语句的形式如下：for语句形式：for(表达式1；表达式2；表达式3)语句；执行过程：首先计算“表达式1”（循环初值），且仅计算一次。每一次循环之前计算“表达式2”（循环条件），如果其结果为真，则执行“语句”（循环体），并计算“表达式3”（循环增量）。否则，循环终止。While语句形式：while(表达式)语句；它的执行过程：首先计算“表达式”的值，如果为真，则执行“语句”。再次判断，直至“表达式”的值为假结束循环。本程序的主函数通过定义一个链表结构体指针head，用