《数据结构课程设计—排序综合》由会员分享，可在线阅读，更多相关《数据结构课程设计—排序综合（20页珍藏版）》请在金锄头文库上搜索。
1、攀枝花学院本科学生课程设计任务书题目排序综合1、课程设计的目的1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操 作实现算法，以及它们在程序中的使用方法。2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）问题描述：用程序实现多种排序算法基本要求：利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法 进行排序。要求：1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序
2、、希尔排序、 起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在 不同的文件中。2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出 其中两种较快的方法。如果采用4种或4种以上的方法者，可适当加分。3、主要参考文献1刘大有等，数据结构（C语言版），高等教育出版社2严蔚敏等，数据结构（C语言版），清华大学出版社3William Ford，William ToppData Structure with C+清华大学出版社4苏仕华等，数据结构课程设计，机械工业出版社4、课程设计工作进度计划第1天完成方案设计与程序框图第2、3天编写程序代码第4天程序调试分
3、析和结果第5天课程设计报告和总结指导教师（签字）日期年 月 日教研室意见：年 月 日学生（签字）:接受任务时间：年 月曰注：任务书由指导教师填写。课程设计（论文）指导教师成绩评定表题目名称排序综合评分项目分值得分评价内涵工作表现20%01学习态度6遵守各项纪律，工作刻苦努力，具有良好的科学工 作态度。02科学实践、调研7通过实验、试验、查阅文献、深入生产实践等渠道 获取与课程设计有关的材料。03课题工作量7按期圆满完成规定的任务，工作量饱满。能 力 水 平 35%04综合运用知识的能力10能运用所学知识和技能去发现与解决实际问题，能 正确处理实验数据，能对课题进行理论分析，得出 有价值的结论。
4、05应用文献的能力5能独立查阅相关文献和从事其他调研;能提出并较 好地论述课题的实施方案；有收集、加工各种信息 及获取新知识的能力。06设计（实验）能力，方案的 设计能力5能正确设计实验方案，独立进行装置安装、调试、 操作等实验工作，数据正确、可靠；研究思路清晰、 完整。07计算及计算机应用能力5具有较强的数据运算与处理能力；能运用计算机进 行资料搜集、加工、处理和辅助设计等。08对计算或实验结果的分析 能力（综合分析能力、技术 经济分析能力）10具有较强的数据收集、分析、处理、综合的能力。成果质量45%09插图（或图纸）质量、篇幅、 设计（论文）规范化程度5符合本专业相关规范或规定要求;规范
5、化符合本文 件第五条要求。10设计说明书（论文）质量30综述简练完整，有见解；立论正确，论述充分，结 论严谨合理；实验正确，分析处理科学。11创新10对前人工作有改进或突破，或有独特见解。成绩指导教师评语指导教师签名：年 月曰摘要排序（sorting ）是计算机程序设计的一种重要操作，他的功能 是将一个数据元素（或记录）的任意序列，重新排列一个按关键字有 序的序列。由于待排序的记录数量不同，使得排序过程中涉及的储存 器不同，可将排序方法分为两大类：一类是内部排序，指的是待排序 记录存放在计算机随机储存器中进行的排序过程；另一类是外部排序， 指的是待排序记录的数量很大，以致内存一次不能容纳全部记
6、录，在 排序过程中尚需对外存进行访问的排序过程。内部排序又分为：插入排序、快速排序、选择排序、归并排序 和基数排序。其中插入排序又分为：直接插入排序、其他插入排序和 希尔排序；选择排序分为：简单选择排序、树形选择排序和堆排序； 基数排序又分为：多关键字的排序和链式基数排序。本次课程设计就是内部排序中的几个排序方法。关键字：内部排序 关键字 重新排列一、方案设计(1) 、程序的模块1、输入2、选择3、输出(2) 、模块的功能1、输入模块的功能：利用随机函数产生N个数(超过20000),由于产生的 数较多，不好查看排序后的顺序是否正确，所以在本程序中只随机产生20个数。create(a,b,&n)
7、是一个随机函数，它可以随机产生20个随机数。2、选择模块的功能：选择数字则进行对应的排序；选择字母则进行重新产 生随机数和退出的操作。1 插入排序insertsort(a,n)2 希尔排序xiersort(a,n)3 冒泡排序maopaosort(a,n)4 快速排序quicksort(a,1,n)5 简单排序jiandansort(a,n)6 堆排序duisort(a,n)C(c)重新产生20个随机数create(a,b,&n)N(n)退出程序3、输出模块的功能：把利用各种排序方法排好顺序的数输出到一个文件夹 中。writefile1(a,n)向指定的文件中写入排序前的数writefile2
8、(a,n)向指定的文件中写入用各种排序方法排好序的数二、程序操作过程图开始C(C)退出输入数字，选择排序方法输入字母，选择重 新置数或者是退出把利用排序方法排好序的数输出到指定的文件夹利用随机函数产 生20个随机数N(n)重新产生随机数2希尔排序1插入排序4快速 排序3冒泡 排序5简单排序6堆 排序三、程序流程图四、程序源代码#include#include#include#define M 20/*把排序之前的数输入到指定文件夹中*/Void writefile1(int *a,int n)( FILE *fp;int i;char filename10;printf(-请输入要输出的文件名
9、称(包括后缀名)：n)； gets(filename);if(fp二fopen(filename,w)=NULL)fprintf(不能打开文件！n)；fprintf(排序之前 ：*n)；for(i=1;i=n;i+)fprintf( %3d,ai);/*把用各种排序方法排序后的数输入到指定文件夹中*/void writefile2(int *a,int n)( FILE *fp;int i;char filename10;fprintf(-请输入要输出的文件名称(包括后缀名)：n)； gets(filename);if(fp二fopen(filename,w)=NULL)fprintf(不能打
10、开文件！n)；printf( 排序之后：*n)； for(i=1;i=n;i+)printf( %3d,ai);a0=-1;/*用随机函数产生20个随机数*/ void create(int *a,int *b,int *n)( int i,;srand(unsigned)time(NULL);for(i=0;in;i+)( ai=rand();bi=ai;printf(%8d ,ai); /*1* 插入排序 */void insertsort(int *a,int n)( int i,j;for(i=2;i=n;i+)( a0=ai;for(j=i-1;a0aj;j-) aj+1=aj;aj
11、+1 =a0;/*插入排序*/*2* 希尔排序 */void xiersort(int *a,int n)( int d3 = 5,3,1;int i,j,k=0;while(k3)(for(i=dk+1;i0&aja0;j=j-dk) aj+dk=aj;aj+dk=a0;k+;/* 希尔排序 */*3* 冒泡排序 */void maopaosort(int *a,int n)( int i,j,change,t;for(i=1;in;i+)( change=0;for(j=1;jaj+1)( t=aj; aj=aj+1;aj+1=t; change=1;if(change=0)break;/
12、* *冒泡排序* */*4* 快速排序 */ void quicksort(int *a,int t, int n) ( int i=t,j=n;while(ij)( if(ij)( a0=ai;while(ia0) j-;if(ij)( ai=aj; i+; while(ij&aia0)i+;if(ij)( aj=ai; j-; ai=a0;quicksort(a,1,i-1);quicksort(a,i+1,n);/*快速排序*/*5* 简单排序 */ void jiandansort(int *a,int n) ( int i,j,t;for(i=1;in;i+)( for(j=i+1;jaj) ( t=ai;ai=aj;/* 简单排序 */*6* 堆排序 */void adjust(int *a,int low, int
