《数据结构产生随机数并排序》由会员分享，可在线阅读，更多相关《数据结构产生随机数并排序（9页珍藏版）》请在金锄头文库上搜索。
1、1数据结构课程设计学部：信息科学与技术学部 专业：计算机科学与技术 目录一、 实验题目 .1二、实验目的和要求 .1三、实验内容和原理 .1四、实验环境 .1五、自定义函数 .21.生成随机数的函数 .22.快速排序函数 .23.堆排序函数 .34.显示函数 .35.主函数 .4六、运行截图 .4七、代码清单 .51一、 实验题目排序综合 利用随机函数产生 N 个随机整数，对这些数采用三种方法（快速排序，基数排序，堆排序） 。二、实验目的和要求a) 掌握快速排序的基本概念和使用方法；b) 掌握堆排序的基本概念和使用方法；独立设计和完成快速，堆排序的程序设计，能够说明他们各自的排序的原理和优缺点
2、。能够应用这两种排序到今后的大型程序设计之中并能够区分什么时候用哪种排序更为简便和快捷。分析两种排序方法的时间复杂度。三、实验内容和原理 实验内容：设计快速、堆排序算法快速排序：在待排序的 N 个记录中，任取一个记录作为基准，经过一趟排序后以基准记录的关键字把全部记录分为两部分，所有关键字值比基准记录关键字值大的记录都排列在基准记录之后；然后堆基准记录前后的这两部分分别重复这样的过程们的到本趟排序的两个新到位的基准和 4 个部分如此重复上述过程，直到每一个部分只剩下一个记录。堆排序：对待排序的文件中的 N 个记录，依它们的关键字值大小按堆的定义排成一个序列，从而输出堆顶的最小关键字的记录，然后
3、堆剩余的关键子再次建堆，便得到次小关键字的记录，如此反复惊醒输出和建堆，直到全部记录按关键字排成有序序列时为止。四、实验环境硬件：（1）学生用微机（2）多媒体实验教室软件：（1）Windows XP 中文操作系统 （2）VC+6.02五、自定义函数1.生成随机数的函数/*-产生随机数-*/void creat(sqlist *l) int i;printf(请输入要产生的随机数个数:);scanf(%d,&l-length);srand(unsigned)time(NULL); /给 srand()提供一个种子，它是一个 unsigned int 类型，for(i=1;ilength;i+)l
4、-ri.key = rand() %900+100; /调用 rand()，返回一个随机数( 在 0 到 32767 之间)printf(%d ,l-ri.key);printf(n);2.快速排序函数/*交换顺序表中子表 rlow.high的记录，使枢轴记录到位，并返回其所在的位置*/int partion(sqlist *l,int low,int high) int pivotkey;l-r0=l-rlow; /用子表的第一个记录作枢轴记录pivotkey=l-rlow.key; /枢轴记录关键字while(lowrhigh.key=pivotkey) -high;l-rlow=l-rh
5、igh; /将比枢轴记录小的记录移到低端while(lowrlow.keyrhigh=l-rlow; /将比枢轴记录大的记录移到低端l-rlow=l-r0; /枢轴记录到位return low; /返回枢轴位置/*-快速排序-*/void Qsort(sqlist *l,int low,int high) int pivotloc;if(lowrs的关键字，使 h-rs成为一个大顶堆*/void heapadjust(sqlist *h,int s,int m) keytype rc;int j;rc=h-rs;for(j=2*s;jrj.keyrj+1.key)+j;if(rc.key=h-
6、rj.key) break;h-rs=h-rj;s=j;h-rs=rc;/*对顺序表 h 进行堆排序*/void heapsort(sqlist *h) keytype rc;int i;for(i=h-length/2;i0;-i)heapadjust(h,i,h-length);for(i=h-length;i1;-i) rc=h-r1;h-r1=h-ri;h-ri=rc;heapadjust(h,1,i-1);4.显示函数/*显示顺序表*/void display(sqlist *l) int i;for(i=1;ilength;i+) /输出顺序printf(%-4.2d,i);pri
7、ntf(n);for(i=1;ilength;i+) /输出分隔符printf(-);printf(n); for(i=1;ilength;i+) /输出排列好的数 4printf(%-4.2d,l-ri.key); 5.主函数/*主函数*/void main() sqlist t; creat(&t);Qsort(&t,1,t.length);printf(nn);printf(快速排序:n);display(&t);heapsort(&t);printf(n);printf(堆排序:n);display(&t);六、运行截图1. 输入要生成的随机数2. 生成随机数并进行排序5七、代码清单#
8、include #include #include typedef structint key;keytype;typedef struct keytype r1000;int length;sqlist;/*产生随机数*/void creat(sqlist *l) int i;printf(请输入要产生的随机数个数:);scanf(%d,&l-length);srand(unsigned)time(NULL); /给 srand()提供一个种子，它是一个 unsigned int 类型，for(i=1;ilength;i+)l-ri.key = rand() %900+100; /调用 ra
9、nd()，返回一个随机数( 在 0 到 32767 之间)printf(%d ,l-ri.key);printf(n);/*交换顺序表中子表 rlow.high的记录，使枢轴记录到位，并返回其所在的位置*/6int partion(sqlist *l,int low,int high) int pivotkey;l-r0=l-rlow; /用子表的第一个记录作枢轴记录pivotkey=l-rlow.key; /枢轴记录关键字while(lowrhigh.key=pivotkey) -high;l-rlow=l-rhigh; /将比枢轴记录小的记录移到低端while(lowrlow.keyrhi
10、gh=l-rlow; /将比枢轴记录大的记录移到低端l-rlow=l-r0; /枢轴记录到位return low; /返回枢轴位置/*快速排序*/void Qsort(sqlist *l,int low,int high) int pivotloc;if(lowlength;i+) /输出顺序printf(%-4.2d,i);printf(n);for(i=1;ilength;i+) /输出分隔符printf(-);printf(n); for(i=1;ilength;i+) /输出排列好的数 printf(%-4.2d,l-ri.key); /*调整 h-rs的关键字，使 h-rs成为一个大顶堆*/void heapadjust(sqlist *h,int s,int m) keytype rc;int j;rc=h-rs;for(j=2*s;jrj
