题目3 - 排序综合 - 报告课件
更新时间:2024-06-28 20:52:01 阅读量: 综合文库 文档下载
理学院 课程设计说明书
课 程 名 称: 数据结构与算法A设计实践 课 程 代 码: 6015059 题 目 三: 排序综合 开 始 时 间: 2015 年 12 月 28 日 完 成 时 间: 2016 年 01 月 10 日 课程设计成绩:
学习态度及平技术水平与实际时成绩(30) 能力(20) 创新(5) 说明书撰写质量(45) 总 分(100) 指导教师签名: 年 月 日
西华大学理学院课程设计说明书
数据结构与算法A设计实践任务书
学院名称: 理学院 课程代码:_6015059________ 专业: 信科 年级: 2012
一、 设计题目
排序综合(限最多1人完成)
二、主要内容
利用随机函数产生N个随机整数(20000以上),对这些数进行多种方法进行排序。
三、具体要求及提交的材料
1) 至少采用4种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。并把排序后的结果保存在不同的文件中。
2) 统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比),找出其中两种较快的方法。
如果采用4种或4种以上的方法者,可适当加分。
测试数据及测试结果请在上交的资料中写明;必须上机调试通过 按《数据结构课程设计大纲》中的要求完成课程设计报告格式。 设计结束后,每个学生必须上交的材料有:
1 《课程设计报告》打印稿一份 2.课程设计的源代码电子文档一份
四、主要技术路线提示
无。
五、进度安排
共计两周时间,建议进度安排如下:
1. 选题,应该在上机实验之前完成 2. 需求分析、概要设计可分配4学时完成 2. 详细设计可分配4学时 4. 调试和分析可分配10学时。 2学时的机动,可提前安排部分提前结束任务的学生答辩
六、 推荐参考资料
1. 2. 3. 4.
冯博琴 等编著,《软件技术基础》(修改版),西安交通大学出版社,1997 严蔚敏 等著,《数据结构》,清华大学出版社,2003 李芸芳 等著,《软件技术基础》(第二版),清华大学出版社,2000 徐孝凯 等著,《数据结构(C语言描述)》,清华大学出版社,2004
指导教师 签名日期 年 月 日 系 主 任 审核日期 年 月 日
西华大学理学院课程设计说明书
目 录
摘 要 ................................................................... 1 1 引 言 .................................................................. 2 2 系统分析 ................................................................ 3 2.1 功能需求 ............................................................ 3 2.1.1总体要求 ......................................................... 3 2.1.2 本人所做模块 .................................................... 3 2.2数据需求 ............................................................ 3 3 详细设计与分析 .......................................................... 4 3.1设计思路 ........................................................... 4 3.2整体设计方案 ........................................................ 5 3.3各种操作函数 ........................................................ 6 3.4主函数 .............................................................. 6 3.5编码 ................................................................ 9 4 测试系统 ............................................................... 13 4.1设计测试数据 ....................................................... 13 4.2测试结果与分析 ..................................................... 14 结 论 ................................................................... 16 致 谢 ................................................................... 17 参考文献 ................................................................. 18 附录 ..................................................................... 19
排序综合
摘 要
排序(sorting是计箅机程序设计的一种重要操作,它的功能是将一组任意顺序数据元素(记录),根据某一个(或几个)关键字按一定的顺序里新排列成为有序的序列。由于待排序的记录数量不同,使得排序过程中涉及的存储器的不同,可将排序方法分为两大类:一类是内部排序,指的是待排序的记录存放在计算机随机存储器中进行的排序过程;另一类是外部排序,指的是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需要对外存进行访问的排序过程。本次课程设计主要是关于内部排序的。
内部排序的方法很多,但就其全面性能而言,很难提出一种被认为是最好的方法,每一种方法都有各自的优缺点,适合在不同的环境(如记录的初始排列状态等)下使用。
本次课程设计就是内部排序中的几个常用排序方法。分析了排序的实质,排序的应用,排序的分类,利用C语言采用数组存储结构编程实现了本排序综合系统,该系统包含了几种常见的排序方法,有直接插入排序、希尔排序、冒泡排序、快速排序、简单排序。
关键词:内部排序,外部排序,重新排列,关键字
1
西华大学理学院课程设计说明书
1 引 言
1. 1问题的提出
排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
排序算法是数据结构学科经典的内容,其中内部排序现有的算法有很多种,其中包含冒泡排序,直接插入排序,简单选择排序,希尔排序,快速排序,堆排序等,各有其特点。
对排序算法比较的分析可以遵循若干种不同的准则,通常以排序过程所需要的算法步数作为度量,有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间,例如,当键是较长的字符串时,常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录,且记录都很大时,还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑所用时间作为复杂性的度量。
1.2 C语言
C语言既有高级语言的特点,又具有汇编语言的特点;既是一个成功的系统设计语言,有时一个使用的程序设计语言;既能用来编写不依赖计算机硬件的应用程序,又能用来编写各种系统程序;是一种受欢迎、应用广泛的程序设计语言。
1.3 C语言发展过程
1973年,美国贝尔实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言,他取了BCPL的第二个字母作为这种语言的名字,这就是C语言。
1977年Dennis M.Ritchie 发表了不依赖于具体机器系统的C语言编译文本《可移植的C语言编译程序》。
1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著《The C Programming Language》,从而使C语言成为目前世界上流行最广泛的高级程序设计语言。
1.4任务与分析
2
排序综合
前面分析了排序的种类以及过程,因此,本系统实现了几种常用的排序方法, 包括:直接插入排序、希尔排序、冒泡排序、非递归的快速排序、简单排序。
2 系统分析
2.1 功能需求 2.1.1总体要求
任务:
机函数产生N个随机整数(20000以上),对这作数进行多种方法进行排序。 要求:
1) 至少采用4种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。并把排序后的结果保存在不同的文件中。
2) 统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比),找出其中两种较快的方法。
如果采用4种或4种以上的方法者,可适当加分。
2.1.2 本人所做模块
通过对任务的要求分析,我将任务分成了几个模块,从而实现了任务的总体要求。
包括了输入模块、选择排序方法模块、输出模块。其中: 1、输入模块
利用随机函数产生N个数(20000以上),产生的数据个数由用户自己输入。 2、选择排序方法模块
在菜单中通过输入相应的选项编号来选择采用何种算法排序,包括的排序算法有:直接插入排序、希尔排序、冒泡排序、快速排序、简单排序。 3、输出模块
输出排序前的,或者排序后的数据元素到屏幕上显示,并且输出以某种算法排序后的数据元素到文件中保存。
最后让主函数对这几个模块进行调用,从而实现全部功能。
2.2数据需求
利用随机函数产生的随机数。
3
西华大学理学院课程设计说明书
3 详细设计与分析
3.1设计思路
1、直接插入排序
思路:设有一组关键字{K1,K2,……,Kn},排序开始便认为K1是一个有序的序列,让 K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列,让K3插入到表长为 2的有序序列,使之成为个表长为3的有序序列,依次类推,最后让Kn插入上述表长为 n-1的有序序列,得到一个表长为n的冇序序列。 2、希尔排序
思路:先取一个正整数dl(dl 思路:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第n个和第n-1个数,将小数放前,大数放后,然后比较第n-1个数和第n-2个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最小的数放到了最前。在第二趟:仍从第n个数开始比较,将小数放前,大数放后,一直比较到第二个数(第一的位置上已经是最小的),第二趟结束,在数第二的位置上得到一个新的最小数(其实在整个数列中是第二小的数)。如此下去,重复以上过程,直至最终完成排序。用二循环实现,外循环变量设i,内循环变量设为j。每次进行比较的两个元素都是与内循环j有关的,它们可以分别用a[j]和a[j+1]标识。 4、快速排序 思路:以第一个关键字K1为控制字,将[K1,K2..Kn]分成两个子区,使左区的所有关键字小于等于K1,右区所有关键字大于等于K1,在子区内数据尚处于无序状态。 将右区首、尾指针保存入栈,对左区进行与第(1)步相类似的处理,又得到它的左子区和右子区。 重复第(1)、(2)步,直到左区处理完毕。然后退栈对一个个子区进行相类似的处理,直到栈空。 4 排序综合 5、简单排序 思路:在n个记录中,用两重循环,外层循环i从第一个元素a[0]开始至最后一个 元素a[n-l],内层循环j从外层循环所值元素a[i]的下—个元素a[jl=a[i+l]开始至最后一个元素a[n-l]搜索,只要找到比a[i]小的元素,便与a[i]交换,如此重复执行操作,当外层循环完毕后,全部记录就排序完成了。 3.2整体设计方案 此课题是研究的是排序问题,为了直观和方便,画出流程图如下图1: 开始 调用欢迎界面 函数startface 选择操作项 产直希冒快简退 生接尔泡速单出 随插排排排选该 机入序序序择系 数 排函函函排统 序数 数 数 序 函 数 保存排序后文件 结束 图1 程序总流程图 通过流程图可以从中看出操作过程以及函数间的调用关系。 5 西华大学理学院课程设计说明书 3.3各种操作函数 根据模块的划分,将函数对模块进行实现,主要函数如下: (1) 创建一个数组函数:int creat() (2) 输出数组函数:void print(struct element a[],int n) (3) 保存函数:void save(struct element a[],int n,char filename[]) (4) 直接插入排序函数:void insertsort(struct element a[],int n) (5) 希尔排序函数:void shellsort(struct element a[],int n) (6) 冒泡排序函数:void bublesort(struct element a[],int n) (7) 快速排序分区处理:int partition(struct element a[],int low,int high) (8) 快速排序函数:void quicksort(struct element a[],int low,int high) (9) 简单排序函数:void selesort(struct element a[],int n) 3.4主函数 //==========通过该函数对其他函数的调用,实现系统功能 int _tmain(int argc, _TCHAR* argv[]) { 6 int num,c; bool flag=0; clock_t start,end; char file1[300]=\直接插入排序.txt\; char file2[300]=\希尔排序.txt\; char file3[300]=\冒泡排序.txt\; char file4[300]=\快速排序.txt\; char file5[300]=\选择排序.txt\; while(1) { menu(); printf(\请输入操作选项:\); scanf(\,&c); 排序综合 if(c!=1&&flag==0) printf(\处理错误,请先产生随机数...\\n\); else { switch(c) { case 1:num=creat(); print(list,num); printf(\); flag=1; break; case 2:start=clock(); insertsort(list,num); end=clock(); printf(\直接插入排序后的结果:\\n\); print(list,num); save(list,num,file1); printf(\,end-start); printf(\); break; case 3:start=clock(); shellsort(list,num); end=clock(); printf(\希尔排序后的结果:\\n\); print(list,num); save(list,num,file2); printf(\,end-start); printf(\); break; case 4:start=clock(); 7 西华大学理学院课程设计说明书 8 bublesort(list,num); end=clock(); printf(\冒泡排序后的结果:\\n\); print(list,num); save(list,num,file3); printf(\,end-start); printf(\); break; case 5:start=clock(); quicksort(list,0,num-1); end=clock(); printf(\快速排序完成!\\n\); printf(\快速排序后的结果:\\n\); print(list,num); save(list,num,file4); printf(\,end-start); printf(\); break; case 6:start=clock(); selesort(list,num); end=clock(); printf(\选择排序后的结果:\\n\); print(list,num); save(list,num,file5); printf(\,end-start); printf(\); break; case 0:exit(1); default:printf(\输入错误,请重新输入...\\n\); } 排序综合 } } system(\); return 0; } 3.5编码 //=========数据类型定义 #define size 1000000 struct element { int key; }list[size]; //==========直接插入排序模块 void insertsort(struct element a[],int n) { int i,j; struct element x; for(i=1;i a[j+1]=a[j]; a[j+1]=x; } printf(\直接插入排序完成!\\n\); } 9 西华大学理学院课程设计说明书 //=========希尔排序模块 void shellsort(struct element a[],int n) { } //=========冒泡排序模块 void bublesort(struct element a[],int n) { 10 int i,j,dk; struct element x; dk=n/2; while(dk>0) { } printf(\希尔排序完成!\\n\); for(i=dk;i if(a[i].key x=a[i]; for(j=i-dk;j>0&&x.key a[j+dk]=a[j]; a[j+dk]=x; dk=dk/2; int i,j; struct element temp; for(i=0;i for(j=n;j>=i;j--) if(a[j+1].key 排序综合 { temp=a[j+1]; a[j+1]=a[j]; a[j]=temp; } } printf(\冒泡排序完成!\\n\); } //==========快速排序模块 int partition(struct element a[],int low,int high) { int i,j; struct element x; i=low; j=high; x=a[i]; while(i j--; if(i } while((i i++; if(i { 11
正在阅读:
题目3 - 排序综合 - 报告课件06-28
通货膨胀对国民经济与生活的影响08-31
猪戊型肝炎08-16
小学语文三年级下册3-8教学建议10-20
最新人教版四年级数学下册教学教案03-12
竹木加工项目可行性研究报告05-10
资本成本答案11-13
爆款打造的思路方法 - 图文03-18
妈妈,我想对您说作文300字07-08
精神科护理考试试题11-02
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 课件
- 排序
- 题目
- 报告
- 综合
- (通用版)19版高考化学微一轮复习第15讲氮及其重要的化合物微课
- 七下期中模拟卷1
- 计算机应用基础教程2011版习题
- 财务会计舞弊、防范与监管
- 镇坪县牛头店镇建立初信初访快速处理机制的几点做法
- 公务员计算机专业课考试必备资料
- 2012台湾省高考历年语文试卷精选必过技巧
- 论林黛玉的人生悲剧
- 第四章ControlLogix 控制器指令介绍和编程应用
- alphacam使用教程
- 运动生理学复习资料选择题的练习及答案
- 初三数学导学案(2018修改)
- 3500个常用汉字(拼音版)
- SQL习题(附答案)
- 2011年村级工作目标管理考核方案
- 机器人运动学(精品教程)(1)
- 2017年中国井矿盐发展现状与市场前景分析(目录)
- 写牛的作文500字-word范文模板(4页)
- 八年级历史 第11课 北伐战争
- 水利基础知识试题集