数据结构c语言设计,比较各种排序方法的效率.pdf
《数据结构c语言设计,比较各种排序方法的效率.pdf》由会员分享,可在线阅读,更多相关《数据结构c语言设计,比较各种排序方法的效率.pdf(31页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、课程设计说明书设计名称:程序设计语言强化课程设计题目:比较各种排序方法的效率学生姓名:梁汉荣专业:网络工程班级:10 网络工程 2学号:2010394236指导教师:顾艳春日期:2012年 3 月 8 日课程设计任务书一、一、设计题目设计题目比较各种排序方法的效率二、二、主要内容主要内容选择四种以上的排序方法,采用随机生成的数据,登记并比较各个排序方法的比较次数和交换次数,验证各个排序方法效率的理论分析的结果。三、三、具体要求具体要求围绕课程设计的目的和意义,基本要求如下:每次随机生成的数据不小于 100 个采用顺序存储结构,登记多次结果经过大量的统计计算,给出各种排序方法的平均效率的比较。把
2、统计结果与理论分析结论进行对照。四、四、进度安排进度安排1、资料查找、系统分析,概要设计;时间安排 2 天2、系统详细设计、功能设计;时间安排 2 天3、算法实现、编程调试;时间安排 5-7 天4、资料整理、课程设计说明书编写。时间安排 1 天五、五、完成后应上交的材料完成后应上交的材料1、课程设计说明书(所使用的数据结构说明、程序流程图、功能模块图、核心算法等)2、相关源程序文件六、六、指导教师指导教师签名日期签名日期年年月月日日系系 主主 任任审核日期审核日期年年月月日日总评成绩总评成绩目目录录一、设计任务的主要算法分析11.1 主要算法具体分析 2二、程序的流程图3各种排序算法的 N-S
3、 图 31.总流程图模块 32.直接插入排序模块43.冒泡排序模块54.简单选择模块55.快速 排序 模块 66.堆排 序 模 块 6三、各个模块的源代码 731 各种排序算法71.直接插入排序函数72.冒泡排序函数 8 3.简单选择排序函数94.快速排序函数 105.堆排序函数 116.输出函数 137.随机生成函数 138.主函数 16四、程序运行效果图 204.1登陆画面204.2 各种排序结果显示画面(100 个数据随机生成 5 次)214.3 总的、平均的比较次数和交换次数显示画面(100 个数据随机生成 5 次)234.4 总的、平均的比较次数和交换次数显示画面(1000 个数据随
4、机生成 100 次)24五、使用说明24六、设计心得 246.1 课程设计中遇到的主要问题和解决方法246.2 本程序的创新和得意之处 256.3 设计中存在的不足及改进的设想 256.4 本次课程设计的感想和心得体会25佛山科学技术学院课程设计用纸一一.算算法分析法分析主程序直接插入冒泡排序简单选择快速排序堆排序随机生成直接插入排序:将记录插入到已排好序的有序表中,得到一个新的,记录数增加的有序表。冒泡排序:是基于交换排序的一种算法。它是依次两两比较待排序元素;若为逆序(递增或递减)则进行交换,将待排序元素从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排序列中的最大(小)关键字交换到最后位
5、置,直到全部元素有序为止。简单选择排序:令 i 从 1 至 n-1,进行 n-1 趟选择操作。快速排序:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,已达到整个序列有序。堆排序:使记录序列按关键字非递减有序排列,则在堆排序的算法中先建一个“大顶堆”,即先选得一个关键字为最大的记录并与序列中最后一个记录交换,然后对序列中前 n-1 记录进行筛选,重新将它调整为一个“大顶堆”,如此反复直至排序结束。随机生成函数:用 srand(unsigned)time(NULL)随机生成数据并使用1佛山科学技术学院课程设计用纸不同
6、排序方法排序。定义结构体数组typedef int keytype;/定义关键字类型为整型typedef structkeytype key;datatype;/记录类型datatype RMAXSIZE;/定义结构体数组1.1 主要算法具体分析:这个排序算法设计个以静态结构体应用为基础加上 C 的基础语法一起的一个综合系统程序。1 主程序是 goto 语句和 for 循环的应用2 直接插入函数是一个将记录插入到已排好序的静态数组的应用3 冒泡排序函数是一个将数据不断交换排序的应用4简单选择函数是一个从 n-i+1个记录中选出最小关键字并和第i 个记录交换的应用5 快速排序函数是一个将每趟记录
7、分成独立两部分并比较交换的应用6 堆排序函数是一个将记录建成堆并交换的排序的应用7 随机生成函数是用 srand(unsigned)time(NULL)随机生成数据的应用8 输出函数是一个对排好序的组数输出的应用2佛山科学技术学院课程设计用纸二二程序的流程图程序的流程图2.12.1 总流程图总流程图输入随机生成数据的个数n100Tgoto m;输入随机生成的次数for(i=0;it;i+)rand_select(n);统计第%d 次随机数据的比较次数和交换次数平均比较次数和平均移动次数说明:利用判断语句判断,若 n100 则执行 goto 语句;利用 for 循环语句执行随机生成函数并输出结果
8、。3F佛山科学技术学院课程设计用纸2.22.2 直接插入排序函数直接插入排序函数for(i=2;i=n;+i)a0+Tif(Ri.keyRi-1.key)FR0=Ri;Ri=Ri-1;b0+=2;for(j=i-2;R0.keyRj.key;-j)Rj+1=Rj;b0+;a0+;Ta0+;Rj+1=R0;b0+;if(j!=0)F说明:利用外循环 for 语句,内嵌判断语句 if(Ri.keyRi-1.key)和内循环 for 语句。4佛山科学技术学院课程设计用纸2.32.3 冒泡排序函数冒泡排序函数for(i=1;i=n-1;i+)for(j=1;jRj+1.key)FRj Rj+1b1+=
9、3;说明:利用内外循环 for 语句,并判断 if(Rj.keyRj+1.key)进行排序。2.42.4 简单选择函数简单选择函数for(i=1;in;i+)k=i;for(j=i+1;j=n;j+)a2+;Tk=j;TRkRi;b2+=3;5if(Rj.keyRk.key)Fif(i!=k)F佛山科学技术学院课程设计用纸说明:for 外循环,内嵌 for 循环和判断语句来进行选择交换排序。2.52.5 快速排序函数快速排序函数int i;Tif(lowhigh)Fi=Partition(R,low,high);递归调用 QSort(R,low,i-1);递归调用 QSort(R,i+1,hi
10、gh);说明:判断 if(low0;-i)HeapAdjust(R,i,n);for(i=n;i1;-i)R1Rib4+=3;HeapAdjust(R,1,i-1);说明:执行第一个 for 循环,不断调用 HeapAdjust(R,i,n)函数;执行第二个 for 循环,不断交换数据和 HeapAdjust(R,1,i-1)函数。6佛山科学技术学院课程设计用纸三原代码程序三原代码程序3.1 各种排序算法各种排序算法#include#include#include#include#define MAXSIZE 50000typedef int keytype;/定义关键字类型为整型typede
11、f structkeytype key;datatype;/记录类型datatype RMAXSIZE;/定义结构体数组int a5=0,b5=0;/分别定义比较次数和交换次数double c5,Ttime;/直接插入排序void Insert_Sort(datatype R,int n)/直接插入排序 int i,j;for(i=2;i=n;+i)a0+;if(Ri.keyRi-1.key)7佛山科学技术学院课程设计用纸R0=Ri;/复制为哨兵Ri=Ri-1;b0+=2;for(j=i-2;R0.keyRj.key;-j)Rj+1=Rj;/记录后移 b0+;a0+;if(j!=0)a0+;R
12、j+1=R0;/插入到正确位置b0+;/冒泡排序void Bubble_Sort(datatype R,int n)/冒泡排序int i,j;for(i=1;i=n-1;i+)for(j=1;jRj+1.key)R0=Rj;/简单选择排序void Select_Sort(datatype R,int n)/简单选择排序int i,j,k;Rj=Rj+1;/将 Rj与 Rj+1交换Rj+1=R0;b1+=3;for(i=1;in;i+)k=i;for(j=i+1;j=n;j+)a2+;if(Rj.keyRk.key)/选择第 i 小的记录k=j;if(i!=k)9佛山科学技术学院课程设计用纸R0
13、=Rk;Rk=Ri;/将 Rk与 Ri交换Ri=R0;b2+=3;/快速排序int Partition(datatype R,int low,int high)int pivotkey;R0=Rlow;b3+;pivotkey=Rlow.key;/枢轴记录关键字while(lowhigh)while(low=pivotkey)a3+;-high;if(lowhigh)Rlow=Rhigh;/将比枢轴记录小的记录移到低端a3+;b3+;while(lowhigh&Rlow.keyR0.key)10佛山科学技术学院课程设计用纸a3+;+low;if(lowhigh)Rhigh=Rlow;/将比枢轴
14、记录大的记录移到高端a3+;b3+;Rlow=R0;b3+;return low;/返回枢轴位置/Partitionvoid QSort(datatype R,int low,int high)/快速排序int i;if(lowhigh)i=Partition(R,low,high);/将 Rlow.high一分为二QSort(R,low,i-1);/对低子表递归排序,i 是枢轴位置QSort(R,i+1,high);/对高子表递归排序/QSort/堆排序void HeapAdjust(datatype R,int s,int m)11佛山科学技术学院课程设计用纸datatype rc;int
15、 j;rc=Rs;for(j=2*s;j=m;j*=2)/沿 key 较大的孩子节点向下筛选Rs=rc;/插入if(jm&Rj.keyRj+1.key)a4+;+j;/j 为 key 较大记录的下标if(jRj.key)break;Rs=Rj;b4+;s=j;/HeapAdjustvoid HeapSort(datatype R,int n)/堆排序int i;for(i=n/2;i0;-i)HeapAdjust(R,i,n);/将 R1.n建成大顶堆for(i=n;i1;-i)R0=R1;R1=Ri;/将 R1与 Ri交换12佛山科学技术学院课程设计用纸Ri=R0;b4+=3;HeapAdj
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 语言 设计 比较 各种 排序 方法 效率
限制150内