数据结构课程设计-排序算法演示系统
更新时间:2024-03-10 17:45:01 阅读量: 综合文库 文档下载
- 数据结构与算法课程设计推荐度:
- 相关推荐
各专业全套优秀毕业设计图纸
计算机学院
数据结构课程设计
题 目:数据结构排序算法演示系统 班 级: 姓 名: 学 号: 同组人姓名:
起 迄 日 期: 课程设计地点: 指导教师:
评阅意见: 成绩评定: 评阅人: 日期: 完成日期:2014年12月
目录
一、课程设计的目的 ................................... 1 二、设计内容和要求 ................................... 1 三、数据采取的结构 ................................... 1 四、功能模块详细设计 ................................. 1 4.1 详细设计思想 .................................. 2 4.1.1 冒泡排序 ................................. 5 4.1.2 快速排序 ................................. 7 4.1.3 直接插入排序 ............................. 9 4.1.4 希尔排序 ................................ 10 4.1.5 直接选择排序 ............................ 12 4.1.6 堆排序 .................................. 14 4.1.7归并排序 ................................ 17 五、总结或心得体会 .................................. 19
六、参考文献 ........................................ 20 七、附录 ............................................ 20
一. 设计目的
随着计算机技术的发展,各种排序算法不断的被提出。排序算法在计算机科学中有非常重要的意义,且应用很广泛。在以后的发展中排序对我们的学习和生活的影响会逐渐增大,很有必要学习排序知识。此次课程设计一方面使自己掌握排序的知识,另一方面锻炼一下团队合作开发系统的能力。
二. 设计内容和要求
功能要求:
(1)界面友好,易与操作。可采用菜单或其它人机对话方式进行选择。 (2)实现各种内部排序。包括直接插入排序,冒泡排序,直接选择排序,希尔排序,快速排序,堆排序,归并排序。
(3)待排序的元素的关键字为整数或(字符)。可用随机数据和用户输入数据作测试比较。比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。
(1) 演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标值的列
表,以便比较各种排序的优劣。
三. 本设计所采用的数据结构
typedef struct {
int key; }RecType;
四.功能模块详细设计
排序算法演示系统 冒泡排序快速排序直接插入排序希尔排序直接选择排序堆排序归并排序 - 1 -
4.1 详细设计思想
主函数:
#include
#define L 8 //排序元素个数 #define FALSE 0 #define TRUE 1 typedef struct {
int key; }RecType; RecType R[L]; int num; int sum;
int sun; //定义排序趟数的全局变量 //系统主界面 //主函数 int main() {
RecType S[100]; int i,k;
char ch1,ch2,q;
printf(\排序算法演示系统************\\n\\n\\t\\t请输入%d个待排序的数据:\\n\
for(i=1;i<=L;i++) { printf(\请输入第%dth数据:\ scanf(\ getchar(); }
ch1='y';
while(ch1=='y') { printf(\ 菜 单 \\n\
printf(\
printf(\更新排序数据* 2--------直接插入排序 \\n\ printf(\希 尔 排 序* 4--------冒 泡 排 序 \\n\ printf(\快 速 排 序* 6--------直接选择排序 \\n\ printf(\堆 排 序 * 8--------归 并 排 序 \\n\ printf(\退 出************ \\n\ printf(\
- 2 -
printf(\请选择:\scanf(\getchar();
for(i=1;i<=L;i++) { R[i].key=S[i].key; }
switch(ch2) {
case '1': printf(\请输入%d个待排序数据\\n\\t\\t\ for(i=1;i<=L;i++) { scanf(\ getchar(); printf(\ } printf(\数据输入完毕!\ break; case '2': Insertsort(); break; case '3': Shellsort(); break; case '4': Bubblesort(); break; case '5': printf(\原始数据为(按回车键开始排序):\\n\\t\\t\ for(k=1;k<=L;k++) { printf(\ } getchar(); printf(\ num=0;sun=0;sum=0; Quicksort(1,L); printf(\排序最终结果是:\\n\\t\\t\ for(k=1;k<=L;k++) { printf(\ } printf(\比较次数是:%d\\n\\t\\t\
- 3 -
}
printf(\交换次数是:%d\\n\\t\\t\ break; case '6': Selectsort(); break; case '7': Heap(); break; case '8': Mergesort(); break; case '0': ch1='n'; break; default: system(\清屏 printf(\对不起,您输入有误,请重新输入!\\n\ break; } if(ch2!='0') { if(ch2=='2'||ch2=='3'||ch2=='4'||ch2=='5'||ch2=='6'||ch2=='7'||ch2=='8') { printf(\排序完毕!\ printf(\按回车键继续!\ q=getchar(); if(q!='\\n') { getchar(); ch1='n'; } } } }
return 1;
- 4 -
图一 主界面
4.1.1 冒泡排序 核心思想
依次比较相邻的两个数,将小数放在前面,大数放在后面,第一轮比较后,最大的数便被放到了最后;第二轮操作前n-1个数据(假设有n个数据),依然是依次比较相邻的两个数,将小数放在前面,大数放在后面,倒数第二个数便是第二大的数;同理第i轮操作前n-i+1的数据(假设i取值是从1开始的),则n-i+i位置上的数据为第i大的数据。一共有n-1轮,第i轮比较中共比较n-i次比较。 核心代码
void Bubblesort() {
int i,j,k,x=0,y=0,m=0;
int exchange=TRUE;//标志位exchange初始化为TRUE 1 printf(\原始数据为(按回车键开始排序):\\n\\t\\t\ for(k=1;k<=L;k++) {
- 5 -
}
printf(\}
getchar(); printf(\
for(i=1;i printf(\比较次数是:\\t\\t\printf(\ printf(\移动次数是:\\t\\t\printf(\ printf(\排序最终结果是:\\n\\t\\t\for(i=1;i<=L;i++) { printf(\} - 6 - 图二 直接插入排序 4.1.2 快速排序 核心思想 首先检查数据列表中的数据数,如果小于两个,则直接退出程序。如果有超过两个以上的数据,就选择一个分割点将数据分成两个部分,小于分割点的数据放在一组,其余的放在另一组,然后分别对两组数据排序。 通常分割点的数据是随机选取的。这样无论你的数据是否已被排列过,你所分割成的两个字列表的大小是差不多的。而只要两个子列表的大小差不多 核心代码 //递归算法实现 void Quicksort(int low,int high) { int i=low,j=high,k; R[0].key=R[low].key; while(i - 7 - if(i R[i].key=R[0].key; num++; //输出语句包括排序的结果及次数 printf(\第%d趟快速排序的结果为:\\n\\t\\t\ for(k=1;k<=L;k++) { printf(\ } getchar(); printf(\ if(low 图三 快速排序 - 8 - 4.1.3 直接插入排序 核心思想 经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置,使得L[1..i]又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。首先比较L[i]和L[i-1],如果L[i-1]≤ L[i],则L[1..i]已排好序,第i遍处理就结束了;否则交换L[i]与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),使得L[j] ≤L[j+1]时为止 核心代码 void Insertsort() { int i,j,k,m=0,x=0; //初始化比较次数变量m,移动次数变量x printf(\原始数据为:(按回车键开始排序)\\n\\t\\t\ for(k=1;k<=L;k++) { printf(\ } getchar(); printf(\ //主要运行部分 for(i=2;i<=L;i++) { if(R[i].key - 9 - } printf(\第%d趟直接插入排序的结果为:\\n\\t\\t\ for(k=1;k<=L;k++) { printf(\ } getchar(); printf(\} printf(\ printf(\比较次数是:\\t\\t\printf(\ printf(\移动次数是:\\t\\t\printf(\ printf(\排序最终结果是:\\n\\t\\t\for(i=1;i<=L;i++) { printf(\} 图四 直接插入排序 4.1.4 希尔排序 核心思想 先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进 - 10 - 行直接插入排序;然后,取第二个增量d2 void Shellsort() { int i,j,gap,x,k,y=0,m=0; //初始化比较次数变量m,移动次数变量y printf(\原始数据为:(按回车键开始排序)\\n\\t\\t\ for(k=1;k<=L;k++) { printf(\ } getchar(); printf(\ //函数主要部分 gap=L/2; while(gap>0) { for(i=gap+1;i<=L;i++) { j=i-gap; while(j>0) { if(R[j].key>R[j+gap].key) { x=R[j].key;//交换语句 R[j].key=R[j+gap].key; R[j+gap].key=x; j=j-gap; y++;//移动次数++ } else { j=0; } } } gap=gap/2; m++;//比较次数++ //输出语句包括排序的结果及次数 printf(\第%d趟希尔排序的结果为:\\n\\t\\t\ for(k=1;k<=L;k++) - 11 - } { printf(\ } getchar(); printf(\} printf(\比较次数是:\\t\\t\printf(\ printf(\移动次数是:\\t\\t\printf(\ printf(\排序最终结果是:\\n\\t\\t\for(i=1;i<=L;i++) { printf(\} printf(\ 图五 希尔排序 4.1.5 直接选择排序 核心思想 第一次从R[0]~R[n-1]中选取最小值,与R[0]交换,第二次从R{1}~R[n-1]中选取最小值,与R[2]交换,...., 第i次从R[i-1]~R[n-1]中选取最小值,与R[i-1]交换,.....,第n-1次从R[n-2]~R[n-1]中选取 - 12 -
正在阅读:
数据结构课程设计-排序算法演示系统03-10
幼儿五言古诗11-24
小学数学第十一册复习计划07-01
创业协会新会员见面会策划书04-16
国际结算复习思考题01-13
王勇毕业论文毕业设计(论文)-基于单片机的热水控制器设计05-10
平安智慧星终身寿险(万能型)等投保规则07-30
计算机组装及调试题库(1)12-02
第十章大学药剂学文本课件01-08
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 数据结构
- 算法
- 演示
- 排序
- 课程
- 设计
- 系统
- CG插画设计与衍生品市场调研报告册
- 江苏省扬州市2015届第一学期检测高三语文试题
- 鸡西市疾病预防控制中心布鲁氏菌病控制应急预案
- 党风廉政建设责任制责任考核实施办法
- 临时用电施工组织设计方案范本
- XX煤矿企业成本、费用核算办法
- 国税(相关说明)
- 急诊科护士
- 毕业论文-钻孔灌注桩
- 语文教学中如何培养学生的创新能力
- 山东省济南市第一中学2011届高三10月阶段考试-语文
- 少年宫音乐室工作总结一
- 广东省河源市中英文实验学校七年级英语上册《Unit 2 Topic 3 Sec
- 计算机基础第四套答案(满分100)
- 用于银行贷款2013年智能浮子液位计项目可行性研究报告(甲级资质
- 第三届“龙建杯”路桥知识竞赛组题 - 图文
- 2020年新编平面设计师考试试题大全(1)名师精品资料
- BSS与AHR接口说明书1119(1)
- 保险代理人模拟试题第三套
- 男人肾病缠身有11个信号