《数据结构c语言设计》由会员分享，可在线阅读，更多相关《数据结构c语言设计（30页珍藏版）》请在金锄头文库上搜索。
1、课程设计任务书一、一、设计题目设计题目比较各种排序方法的效率二、二、主要内容主要内容 选择四种以上的排序方法，采用随机生成的数据，登记并比较各个排序方法的比较次数和交换次数，验证各个排序方法效率的理论分析的结果。三、三、具体要求具体要求围绕课程设计的目的和意义，基本要求如下：每次随机生成的数据不小于 100 个采用顺序存储结构，登记多次结果经过大量的统计计算，给出各种排序方法的平均效率的比较。把统计结果与理论分析结论进行对照。四、四、进度安排进度安排1、资料查找、系统分析，概要设计；时间安排 2 天2、系统详细设计、功能设计；时间安排 2 天3、算法实现、编程调试；时间安排 5-7 天4、资料
2、整理、课程设计说明书编写。时间安排 1 天五、五、完成后应上交的材料完成后应上交的材料1、课程设计说明书（所使用的数据结构说明、程序流程图、功能模 块图、核心算法等）2、相关源程序文件六、六、总评成绩总评成绩指导教师指导教师 签名日期签名日期 年年 月月 日日系系 主主 任任 审核日期审核日期 年年 月月 日日目目 录录一、设计任务的主要算法分析11.1 主要算法具体分析 2二、程序的流程图3各种排序算法的 N-S 图31.总流程图模块 32.直接插入排序模块43.冒泡排序模块 54.简单选择模块55.快速排序模块 66.堆排序模块 6三、各个模块的源代码 731 各种排序算法71.直接插入排
3、序函数72.冒泡排序函数 83.简单选择排序函数94.快速排序函数 105.堆排序函数 116. 输出函数 137.随机生成函数 138.主函数 16四、程序运行效果图 204.1 登陆画面 204.2 各种排序结果显示画面（100 个数据随机生成 5 次）214.3 总的、平均的比较次数和交换次数显示画面（100 个数据随机 生成 5 次）234.4 总的、平均的比较次数和交换次数显示画面（1000 个数据随机生成 100 次）24五、使用说明24六、设计心得 246.1 课程设计中遇到的主要问题和解决方法 246.2 本程序的创新和得意之处 25 6.3 设计中存在的不足及改进的设想 25
4、6.4 本次课程设计的感想和心得体会25佛山科学技术学院课程设计用纸1一一. .算法分析算法分析 主程序直 接 插 入冒 泡 排 序简 单 选 择快 速 排 序堆 排 序随 机 生 成直接插入排序：将记录插入到已排好序的有序表中，得到一个新的， 记录数增加的有序表。冒泡排序：是基于交换排序的一种算法。它是依次两两比较待排序元素；若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”。 每趟冒泡都将待排序列中的最大（小）关键字交换到最后位置，直到全部元素有序为止。简单选择排序：令 i 从 1 至 n-1，进行 n-1 趟选择操作。快速排序：通过一趟排序将待排记录分割成独立
5、的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。堆排序：使记录序列按关键字非递减有序排列，则在堆排序的算法中先建一个“大顶堆” ，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前 n-1 记录进行筛选，重新将它调整为一个“大顶堆” ，如此反复直至排序结束。佛山科学技术学院课程设计用纸2随机生成函数：用 srand(unsigned)time(NULL)随机生成数据并使用不同排序方法排序。定义结构体数组typedef int keytype; /定义关键字类型为整型typedef structkeytyp
6、e key;datatype; /记录类型datatype RMAXSIZE; /定义结构体数组1.1 主要算法具体分析：这个排序算法设计个以静态结构体应用为基础加上 C 的基础语法一起的一个综合系统程序。1 主程序是 goto 语句和 for 循环的应用2 直接插入函数是一个将记录插入到已排好序的静态数组的应用3 冒泡排序函数是一个将数据不断交换排序的应用4 简单选择函数是一个从 n-i+1 个记录中选出最小关键字并和第 i 个记录交换的应用5 快速排序函数是一个将每趟记录分成独立两部分并比较交换的应用6 堆排序函数是一个将记录建成堆并交换的排序的应用7 随机生成函数是用 srand(uns
7、igned)time(NULL)随机生成数据的应用8 输出函数是一个对排好序的组数输出的应用佛山科学技术学院课程设计用纸3二二程序的流程图程序的流程图 2.12.1 总流程图总流程图输入随机生成数据的个数nRj+1.key) Fa1+;Rj Rj+1 b1+=3;说明：利用内外循环 for 语句，并判断 if(Rj.keyRj+1.key)进行排 序。2.42.4 简单选择函数简单选择函数佛山科学技术学院课程设计用纸6for(i=1;iRi ;b2+=3;k=i;k=j;if(i!=k)TF说明：for 外循环，内嵌 for 循环和判断语句来进行选择交换排序。2.52.5 快速排序函数快速排序
8、函数Tif(low0;-i)for(i=n;i1;-i)R1Ri b4+=3;HeapAdjust(R,i,n);HeapAdjust(R,1,i-1);int i；说明：执行第一个 for 循环，不断调用 HeapAdjust(R,i,n)函数；执行 第二个 for 循环，不断交换数据和 HeapAdjust(R,1,i-1)函数。三原代码程序三原代码程序3.1 各种排序算法各种排序算法#include#include#include#include #define MAXSIZE 50000typedef int keytype; /定义关键字类型为整型typedef structkeyt
9、ype key;datatype; /记录类型datatype RMAXSIZE; /定义结构体数组佛山科学技术学院课程设计用纸8int a5=0,b5=0; /分别定义比较次数和交换次数double c5,Ttime; /直接插入排序void Insert_Sort(datatype R,int n)/直接插入排序int i,j;for(i=2;i冒泡排序void Bubble_Sort(datatype R,int n)/冒泡排序int i,j;for(i=1;iRj+1.key)R0=Rj;Rj=Rj+1; /将 Rj与 Rj+1交换Rj+1=R0;b1+=3; 佛山科学技术学院课程设计
10、用纸10/简单选择排序void Select_Sort(datatype R,int n)/简单选择排序int i,j,k;for(i=1;i快速排序int Partition(datatype R,int low,int high)佛山科学技术学院课程设计用纸11int pivotkey;R0=Rlow;b3+; pivotkey=Rlow.key; /枢轴记录关键字while(low=pivotkey)a3+; -high; if(low堆排序void HeapAdjust(datatype R,int s,int m)datatype rc;int j;rc=Rs;for(j=2*s;j
11、Rj.key) break;Rs=Rj; b4+; s=j;佛山科学技术学院课程设计用纸13Rs=rc; /插入/HeapAdjustvoid HeapSort(datatype R,int n)/堆排序int i;for(i=n/2;i0;-i)HeapAdjust(R,i,n); /将 R1n建成大顶堆for(i=n;i1;-i)R0=R1;R1=Ri; /将 R1与 Ri交换Ri=R0;b4+=3; HeapAdjust(R,1,i-1); /将 R1i-1重新调整为大顶堆/HeapSort/输出函数void Pri(datatype R,int n)/输出函数 int i;for(i=
12、1;i随机生成函数void rand_select(int n)/随机生成函数int i;LARGE_INTEGER m_liPerfFreq=0;LARGE_INTEGER m_liPerfStart=0; LARGE_INTEGER liPerfNow=0;datatype R1MAXSIZE,R2MAXSIZE,R3MAXSIZE,R4MAXSIZE;for (i=1; i主函数void main() int i,n,t; srand(unsigned)time(NULL);/使用系统定时/计数器的值 /做为随机种子每次运行，显示的随机数会是伪随机数,结果都不同 printf(“n“);
13、printf(“n“);printf(“n“);printf(“ *-*n“);m:printf(“ |请输入随机生成数据的个数|n“);printf(“ *-*n“);scanf(“%d“,if(n100)printf(“取数个数不能小于 100,请重新输入!n“);goto m;佛山科学技术学院课程设计用纸18printf(“n“);printf(“n“);printf(“ *-*n“);printf(“ |请输入随机生成的次数|n“);printf(“ *-*n“);scanf(“%d“,printf(“n“);for(i=0;it;i+)printf(“电脑第%d 次随机生成数据为:n“,i+1);rand_select(n);printf(“统计第%d 次随机数据的比较次数和交换次数为n“,i+1);printf(“*-
