课 程 设 计
课程设计名称： 排序综合 专 业 班 级 ： 00 学 生 姓 名 ： 00 学 号 ： 000 指 导 教 师 ： 000 课程设计时间： 2010.6.21-2010.6.25
1 / 1
计算机科学与技术 专业课程设计任务书
学生姓名 题 目 课题性质 指导教师 A．工程设计 专业班级 排序综合 课题来源 同组姓名 D．自拟课题 无 学号 主要内容 综合应用所学知识，设计完成一个排序综合系统。本系统拟实现以下功能： 1.直接插入排序 2.希尔排序 3.快速排序 4.堆排序 5.结果保存 6.计算排序时间 系统要求采用VC6.0工具进行开发实现。 综合运用和融化所学理论知识，提高分析和解决实际问题的能力，使用c语任务要求 言设计一个排序综合系统。 完成课程设计报告，报告中对关键部分给出图表说明。要求格式规范，工作量饱满。 [1] 数据结构. 严蔚敏，吴伟民 编著. 清华大学出版社. 2007年03月 [2] 数据结构、算法与应用：C++语言描术. （美）萨尼（Sahni,S.） 著，汪诗林 等译. 机械工业出版社.2005年03月 指导教师签字： 审查意见 教研室主任签字： 2010 年 6 月24 日 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页
参考文献
1 / 1
信息科学与工程 学院课程设计成绩评价表
课程名称：数据结构课程设计
设计题目：排序 序号 评审项目 分 数 满分标准说明 思路清晰；语言表达准确，概念清楚，论点正确；实验方法科学，分析归纳合理；结论严谨，设计有应用价值。任务饱满，做了大量的工作。 内容新颖，题目能反映新技术，对前人工作有改进或突破，或有独特见解 整体构思合理，理论依据充分，设计完整，实用性强 1 内 容 2 创 新 3 完整性、实用性 4 数据准确、可靠 数据准确，公式推导正确 设计格式、绘图、图纸、实验数据、标准的运用等符合有关标准和规定 能很好的遵守各项纪律，设计过程认真； 准备工作充分，回答问题有理论依据，基本概念清楚。主要问题回答简明准确。在规定的时间内作完报告。 5 规 范 性 6 纪 律 性 7 答 辩 总 分 综 合 意 见 指导教师 年 月 日
1 / 1
1、 需求分析
1.1、直接插入排序
思路:设有一组关键字{K1,K2,…….,Kn},排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列, 让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列.
1.2、希尔排序
思路：先取一个正整数d1(d1
1.3、快速排序:（递归和非递归）
思路:以第一个关键字K1为控制字，将[K1、K2、….Kn]分成两个子区，使左区的有关键字小于等于K1，右区所有关键字大于等于K1，最后控制居两个子区中间的适当位置。在子区内数据尚处于无序状态。
将右区首、尾指针保存入栈，对左区进行与第（1）步相类似的处理，又得到它的左子区和右子区，控制字区中。
重复第（1）、（2）步，直到左区处理完毕。然后退栈对一个个子区进行相类似的处理，直到栈空 分区处理函数hoare
思路：首先用两个指针i、j分别指向首、尾两个关键字，i=1，j=8。如对(46、56、14、43、95、10、19、72)。第一个关键字46作为控制字，该关键字所属的记录另存储在一个x变量中。从文件右端元素r[j].key开始与控制字x.key相比较，当r[j].key大于等于x.key时，r[j]不移动，修改指针j，j--，直到r[j].key 1 / 1 r[i].key与x.key相比较，当r[i].key小于等于x.key时，r[i]不移动，修改指针i，i--，直到r[i].key 1.4、堆排序 思路：把n个记录存于向量r之中，把它看成完全二叉树，此时关键字序列不一定满足堆的关系。堆排序大体分为两步处理： 初建堆，从堆的定义出发，当i=1、2、。。。。、[2/n]时应满足ki<=k2i和ki<=k2i+1.所以先取i=[n/2](它一定是第n个结点的双亲编号),将以i结点为根的子树调整为堆，然后令i=i-1，将以不结点为根的子树调整为堆。此时可能会反复调整某些结点，直到i=1为止，堆初步建成。 堆排序，首先输出堆顶元素（一般是最小值）,让堆中最后一个元素上移到原堆顶位置，然后恢复堆。因为经过第一步输出堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤。 2、 概要设计 2.1、头文件 #include 2.2 、ADT struct element { int key; }list[20]; struct rnode { int key; int point; 1 / 1
排序综合课程设计报告
