数据结构c语言设计.docx

设计名称： 程序设计语言强化课程设计题 目：比较各种排序方法的效率学生姓名：专业：网络工程班级：学号：指导教师：日期：201年 月曰课程设计任务书一、设计题目比较各种排序方法的效率二、主要内容选择四种以上的排序方法，采用随机生成的数据，登记并比较各 个排序方法的比较次数和交换次数，验证各个排序方法效率的理论分 析的结果。三、具体要求围绕课程设计的目的和意义，基本要求如下：每次随机生成的数据不小于100个采用顺序存储结构，登记多次结果经过大量的统计计算，给出各种排序方法的平均效率的比较。把统计结果与理论分析结论进行对照。四、进度安排1、资料查找、系统分析，概要设计；时间安排2天2、系统详细设计、功能设计；时间安排2天3、算法实现、编程调试；时间安排5-7天4、资料整理、课程设计说明书编写。时间安排1天五、完成后应上交的材料1、课程设计说明书（所使用的数据结构说明、程序流程图、功能模块 图、核心算法等）2、相关源程序文件六、总评成绩指导教师 签名日期 年月日系主任 审核日期年月日目录一、 设计任务的主要算法分析11.1主要算法具体分析2二、程序的流程图3各种排序算法的N-S图31. 总流程图模块 32. 直接插入排序模块43. 冒泡排序模块 54. 简单选择模块55. 快速排序模块 66. 堆排序模块 6三、 各个模块的源代码 73. 1各种排序算法71. 直接插入排序函数 72. 冒泡排序函数 83. 简单选择排序函数 94. 快速排序函数105. 堆排序函数116. 输出函数137. 随机生成函数138. 主函数16四、程序运行效果图 204.1登陆画面 20 4.2各种排序结果显示画面（100个数据随机生成5次）214.3总的、平均的比较次数和交换次数显示画面（100个数据随机23生成5次）4.4总的、平均的比较次数和交换次数显示画面（1000个数据随机生成100次） 24五、 使用说明24六、 设计心得246.1课程设计中遇到的主要问题和解决方法 246.2本程序的创新和得意之处256.3设计中存在的不足及改进的设想 256.4本次课程设计的感想和心得体会25一.算法分析直接插入排序：将记录插入到己排好序的有序表中，得到一个新的， 记录数增加的有序表。冒泡排序：是基于交换排序的一种算法。它是依次两两比较待排序元 素；若为逆序(递增或递减)则进行交换，将待排序元素 从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排序 列中的最大(小)关键字交换到最后位置，直到全部元素 有序为止。简单选择排序：令i从1至n-1，进行n-1趟选择操作。快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部 分记录的关键字均比另一部分记录的关键字小，则可分别 对这两部分记录继续进行排序，已达到整个序列有序。堆排序：使记录序列按关键字非递减有序排列，则在堆排序的算法中 先建一个“大顶堆”，即先选得一个关键字为最大的记录并与 序列中最后一个记录交换，然后对序列中前n-1记录进行筛 选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。随机生成函数：用srand(unsigned)time(NULL)随机生成数据并使用 不同排序方法排序。定义结构体数组typedef int keytype; 定义关键字类型为整型typedef structkeytype key;datatype; 记录类型datatype RMAXSIZE; /定义结构体数组1.1主要算法具体分析：这个排序算法设计个以静态结构体应用为基础加上C的基础语法一起 的一个综合系统程序。1主程序是goto语句和for循环的应用2直接插入函数是一个将记录插入到已排好序的静态数组的应用3冒泡排序函数是一个将数据不断交换排序的应用4简单选择函数是一个从n-i+1个记录中选出最小关键字并和第i个记 录交换的应用5快速排序函数是一个将每趟记录分成独立两部分并比较交换的应用6堆排序函数是一个将记录建成堆并交换的排序的应用7随机生成函数是用srand(unsigned)time(NULL)随机生成数据的应 用8输出函数是一个对排好序的组数输出的应用二.程序的流程图2.1总流程图说明：利用判断语句判断，若n<100则执行goto语句；利用for循环 语句执行随机生成函数并输出结果。for(i=2;i<=n;+i)a0+''''''''>->fRikey<Ri-1.key)_'R0=Ri;Ri=Ri-1;b0+=2;for(j=i-2;R0.key<Rj.key;-j)Rj+1=Rj; b0+; a0+;J0a0+;Rj+1=R0; b0+;说明：利用外循环for语句，内嵌判断语句if(Ri.key<Ri-1.key)和内 循环for语句。说明：利用内外循环for语句，并判断if(Rj.key>Rj+1.key)进行排序。说明：for外循环，内嵌for循环和判断语句来进行选择交换排序。2.5快速排序函数int i;_Jfl°w<high_i=Partition(R,low,high);递归调用 QSort(R,low,i-1);递归调用 QSort(R,i+1,high);说明:判断 if(low<high)，并递归调用 QSort(R,low,i-1); QSort(R,i+1,high);2.6堆排序函数int i；for(i=n/2;i>0;-i)HeapAdjust(R,i,n);for(i=n;i>1;-i)R1<=>Ri b4+=3;HeapAdjust(R,1,i-1);说明：执行第一个for循环，不断调用HeapAdjust(R,i,n)函数；执行第 二个for循环，不断交换数据和HeapAdjust(R,1,i-1)函数。三.原代码程序3.1各种排序算法#include<stdio.h>#include<stdlib.h>#include<time.h>#include<windows.h>#define MAXSIZE 50000typedef int keytype; /定义关键字类型为整型typedef struct(keytype 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.key<Ri-1.key)R0=Ri; 复制为哨兵Ri=Ri-1;b0+=2;for(j=i-2;R0.key<Rj.key;-j)Rj+1=Rj； 记录后移b0+;a0+;if(j!=0) a0+;Rj+1=R0; /插入到正确位置b0+;/<二 >冒泡排序void Bubble_Sort(datatype R,int n)/ 冒泡排序(int i,j;for(i=1;i<=n-1;i+)for(j=1;j<=n-i;j+)(a1+;if(Rj.key>Rj+1.key)(R0=Rj;Rj=Rj+1; /将 Rj与 Rj+1交换Rj+1=R0;b1+=3;/<三简单选择排序void Select_Sort(datatype R,int n)/简单选择排序(int i,j,k;for(i=1;i<n;i+)(k=i;for(j=i+1;j<=n;j+)(a2+;if(Rj.key<Rk.key) /选择第 i 小的记录k=j;if(i!=k)R0=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(low<high)(while(low<high&&Rhigh.key>=pivotkey)a3+; -high;if(low<high)(Rlow=Rhigh; 将比枢轴记录小的记录移到低端a3+;b3+;while(low<high&&Rlow.key<R0.key)a3+; +low;if(low<high)Rhigh=Rlow; 将比枢轴记录大的记录移到高端a3+;b3+;Rlow=R0;b3+;return low; /返回枢轴位置/Partitionvoid QSort(datatype R,int low,int high)/快速排序(int i;if(low<high)(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)(datatype rc;int j;rc=Rs;for(j=2*s;j<=m;j*=2) /沿key较大的孩子节点向下筛选(if(j<m && Rj.key<Rj+1.key)a4+;+j; /j为key较大记录的下标if(j<m) a4+;a4+;if(rc.key>Rj.key) break;Rs=Rj; b4+;s=j;Rs=rc; /插入/HeapAdjustvoid HeapSort(datatype R,int n)/堆排序(int i;for(i=n/2;i>0;-i)HeapAdjust(R,i,n); /将 R1.n建成大顶堆for(i=n;i>1;-i)(R0=R1;R1=Ri; 将 R1与 Ri交换Ri=R0;b4+=3;HeapAdjust(R,1,i-1); /将 R1.i-1重新调整为大顶堆/HeapSort/六输出函数 void Pri(datatype R,int n)/输出函数 (int i;for(i=1;i=n;i+)printf("%d ,Ri.key);printf(n)； /七随机生成函数void rand_select(int n)/随机生成函数 (int i;LARGE_INTEGERm_liPerfFreq=0;LARGE_INTEGERm_liPerfStart=0;LARGE_INTEGER liPerfNow=0;datatype R1MAXSIZE,R2MAXSIZE,R3MAXSIZE,R4MAXSIZE;for (i=1; i<=n; i+)(printf("%d ", Ri.key=rand()%n);printf("n");for(i=1;i<=n;i+)R1i.key=Ri.key;for(i=1;i<=n;i+)R2i.key=Ri.key;for(i=1;i<=n;i+)R3i.key=Ri.key;for(i=1;i<=n;i+)R4i.key=Ri.key;QueryPerformanceFrequency(&m_liPerfFreq);QueryPerformanceCounter(&m_liPerfStart); /计时开始 Insert_Sort(R, n); /直接插入排序QueryPerformanceCounter(&liPerfNow); /计时结束Ttime=(liPerfNow.QuadPart)-(m_liPerfStart.QuadPart) *1000.0/m_liPerfFreq.QuadPart;c0+=Ttime;printf("插入排序后数据的顺序：n");Pri(R,n);QueryPerformanceFrequency(&m_liPerfFreq);QueryPerformanceCounter(&m_liPerfStart); /计时开始Bubble_Sort(R1, n); /冒泡排序QueryPerformanceCounter(&liPerfNow); /计时结束Ttime=(liPerfNow.QuadPart)-(m_liPerfStart.QuadPart)*1000.0/m_liPerfFreq.QuadPart;c1+=Ttime;printf("冒泡排序后数据的顺序：n");Pri(R1,n);QueryPerformanceFrequency(&m_liPerfFreq);QueryPerformanceCounter(&m_liPerfStart); /计时开始Select_Sort(R2, n); /简单选择排序QueryPerformanceCounter(&liPerfNow); /计时结束Ttime=(liPerfNow.QuadPart)-(m_liPerfStart.QuadPart)*1000.0/m_liPerfFreq.QuadPart;c2+=Ttime;printf("简单排序数据的顺序：n");Pri(R2,n);QueryPerformanceFrequency(&m_liPerfFreq);QueryPerformanceCounter(&m_liPerfStart); /计时开始QSort(R3,1,n); 快速排序QueryPerformanceCounter(&liPerfNow); /计时结束Ttime=(liPerfNow.QuadPart)-(m_liPerfStart.QuadPart)*1000.0/m_liPerfFreq.QuadPart;c3+=Ttime;printf("快速排序后数据的顺序：n");Pri(R3,n);QueryPerformanceFrequency(&m_liPerfFreq);QueryPerformanceCounter(&m_liPerfStart); /计时开始HeapSort(R4,n); /堆排序QueryPerformanceCounter(&liPerfNow); /计时结束Ttime=(liPerfNow.QuadPart)-(m_liPerfStart.QuadPart)*1000.0/m_liPerfFreq.QuadPart;c4+=Ttime;printf("堆排序后数据的顺序：n");Pri(R4,n);/八 主函数void main()(int i,n,t; srand(unsigned)time(NULL);/使用系统定时/计数 器的值做为随机种子每次运行，显示的随机数会是伪随机数，结果 都不同printf(n)；printf(n)；printf(n)；printf("*n)；m:printf("|请输入随机生成数据的个数|n");printf("*n");scanf(%d,&n);if(n<10)(printf("取数个数不能小于10,请重新输入！n");goto m;printf(n)；printf(n)；*n");printf("printf("|请输入随机生成的次数|n);*n");printf("scanf("%d",&t);printf(n)；for(i=0;i<t;i+)(printf("电脑第%d次随机生成数据为：n”,i+1);rand_select(n);printf("统计第%d次随机数据的比较次数和交换次数为n”,i+1);prinr+f (、*rr)-prirrtf (、*i*uH买薄亨簪«灌亨簪 能耳n、)-prinr+f (、n、)-prinr+f (、*w®Ksd<-+K10d<-+K12f n、 aoL bo-co)；prinr+f (、n、)-prinr+f (、*M sKsd<-+K10d<-+K12f n、 aIL b11 c1)；prinr+f (、n、)-prinr+f (、*3* Ksd<-+K10d<-+K12f n、 a2b2-c2)； prinr+f (、n、)-prinR (、*»s Ksd<-+K10d<-+K12frA a3L b31 c3)： prinr+f (、n、)-prinr+f (、*® Ksd<-+K10d<-+K12f n、 a4L b4-c4)； prinr+f (、* *rr)：prinr+f (、n、)-18-TTT-TTTprintf(-求得平均比较次数和平均移动次数为n)；printf(*n)；printf("*排序方式 平均比较次数 平均交换次数 平均耗时n)；printf(n)；printf(*直接T0dt%T0dt%T2fn，a0/t,b0/t,c0/t);printf(n)；printf(*冒泡T0dt%T0dt%T2fn，a1/t,b1/t,c1/t)；printf(n)；printf(*简单选择 -10dt%-10dt%-12fn，a2/t,b2/t,c2/t)；printf(n)；printf(*快速排序 -10dt%-10dt%-12fn，a3/t,b3/t,c3/t)；printf(n)；printf(*堆排序 -10dt%-10dt%-12fn，a4/t,b4/t,c4/t)；printf(*n)；4程序运行效果4.1登陆界面（100个数据随机生成5次）4.2各种排序结果显示画面（100个数据随机生成5次） 第1次生成画面：（100个数据随机生成5次） 第5次生成画面：4.3总的和平均的比较次数和交换次数显示（100个数据随机生成5次）4.4总的和平均的比较次数和交换次数显示(1000个数据随机生成100次)五.使用说明本设计比较各种排序算法的效率能在家用或公用计算机上的VC软件上 使用.六.设计心得(1) 课程设计中遇到的主要问题和解决方法：上学期刚学完数据结构这本书，毕竟都很少实践操作，做这个比较 排序算法的效率都有些挑战，在这个课程设计中，主要是对于一些基 本的知识，熟悉程度不够，特别是对于比较次数和交换次数的统计， 刚开始是跟理论值相差甚大，然后自己看了好几遍的书和上网看了一 些例题，根据输入两个随机生成数据，比较次数为1的依据才把问题 解决。在编译时有时会出现较多的出错提示，这时要理解提示信息的含 义，并据此改正错误。当编译提示的出错信息不止一条时，只须先注 重其中第一条，每次改完一个错误后先编译一次，因为从第二个错误 开始的若干错误很可能是随带错误，只要更正了第一个错误可能就没 有错误出现了，而且我们可以用printf语句来测试某条有返回值的语 句是否执行。(2) 我的创新和得意之处：这个比较排序算法的效率，使用系统定时/计数器的值 srand(unsigned)time(NULL);做为随机种子每次运行，显示的随机数会 是伪随机数，结果都不同，是可以随意输入随机生成数据的个数，程序 执行时可以输入大量数据，有利于精确求取比较次数和交换次数。(3) 设计中存在的不足及改进的设想：设计过程中，程序不够简练，另外计时语句显得比较冗长，因为 是高精度时间，因此统计比较次数和交换次数的工作应该是短期内能 完成的工作，时间太长，误差会特别大，因为线程有占用时间片的因 素存在。不过总的来说这个设计功能还是比较完善，它很好记录了排 序过程中的时间差。(4) 本次课程设计的感想和心得体会：此次课程设计，自拿到题目到完成整个编程，从理论到实践，在 短短的天数，发现很多以前没有注意到的知识点，学到很多东西，巩 固了以前所学过的知识。通过这次课程设计使我懂得了理论与实际相 结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知 识与实践相结合起来，才能提高自己的实际动手能力和独立思考的能 力。在设计的过程中遇到问题，很多问题自己都可以解决，有时利用 printf语句来测试某条语句是否执行，或用/* */暂且分隔出某部分 来执行其他语句，能够很快的找到问题所在。在设计的过程中发现了 自己的不足之处，对一些前面学过的知识理解得不够深刻，掌握得不 够牢固，通过这次课程设计之后，我加深所学过的知识的理解与运用。 在学习的过程中，独立完成，很好的提升了自己的能力，也锻炼了自 己的耐力。