数据结构上机基本习题.ppt

《数据结构上机基本习题.ppt》由会员分享，可在线阅读，更多相关《数据结构上机基本习题.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、单元实验二 排序算法排序算法 排序的分类排序的分类内部排序内部排序外部排序外部排序 插入排序（插入排序（直插排序、二分插入排序直插排序、二分插入排序、希尔排序希尔排序）交换排序（冒泡排序、快速排序）交换排序（冒泡排序、快速排序）选择排序（选择排序（简单选择排序、树型排序、堆排序简单选择排序、树型排序、堆排序）归并排序（二路归并排序、多路归并排序）归并排序（二路归并排序、多路归并排序）分配排序（多关键字排序、基数排序）分配排序（多关键字排序、基数排序）多路平衡归并排序多路平衡归并排序 置换选择排序置换选择排序 最佳归并树最佳归并树排序排序直接插入排序直接插入排序n直接插入排序直接插入排序(Str

2、aight Insertion Sorting)(Straight Insertion Sorting)的基本思的基本思想是：想是：n n个待排序的元素由一个有序表和一个无序表组成，个待排序的元素由一个有序表和一个无序表组成，开始时有序表中只包含一个元素。排序过程中，每次从开始时有序表中只包含一个元素。排序过程中，每次从无序表中取出第一个元素，将其插入到有序表中的适当无序表中取出第一个元素，将其插入到有序表中的适当位置，使有序表的长度不断加长，完成排序过程。位置，使有序表的长度不断加长，完成排序过程。有序序列有序序列R1.i-1Ri无序序列无序序列 Ri.n有序序列有序序列R1.i无序序列无序

3、序列 Ri+1.n冒泡排序冒泡排序n冒泡排序冒泡排序(Bubble Sorting)(Bubble Sorting)的基本思想是：将相邻位置的基本思想是：将相邻位置的关键字进行比较，若为逆序则交换之。的关键字进行比较，若为逆序则交换之。无序序列无序序列R1.n-i+1有序序列有序序列 Rn-i+2.nn-i+1无序序列无序序列R1.n-i有序序列有序序列 Rn-i+1.n比较相邻记录，将关键字最大的记比较相邻记录，将关键字最大的记录录交换到交换到 n-i+1 的位置上的位置上第第 i 趟起泡排序趟起泡排序若在一趟排序过程中没有进行过交换记录的操作，则若在一趟排序过程中没有进行过交换记录的操作，

4、则整个排序过程终止。整个排序过程终止。简单选择排序简单选择排序n简单选择排序的基本思想是：第一趟在简单选择排序的基本思想是：第一趟在n n个记录中选取最个记录中选取最小记录作为有序序列的第一个记录，第二趟在小记录作为有序序列的第一个记录，第二趟在n-1n-1个记录个记录中选取最小记录作为有序序列的第二个记录，第中选取最小记录作为有序序列的第二个记录，第i i趟在趟在n-n-i+1i+1个记录中选取最小的记录作为有序序列多中的第个记录中选取最小的记录作为有序序列多中的第i i个个记录。记录。有序序列有序序列R1.i-1无序序列无序序列 Ri.n 第 i 趟简单选择排序从中选出关键字最小的记录从中

5、选出关键字最小的记录有序序列有序序列R1.i无序序列无序序列 Ri+1.n基本要求基本要求1用随机函数产生1000个（或更多）整数（或浮点数），保存在文件（intfile.dat/realfile.dat）中，然后将文件中的所有整数（或浮点数）读入一个数组A。（1）用冒泡法对数组A排序；（2）用简单选择排序方法对数组A排序；（3）用直接插入排序法对数组A排序；将上述排序算法分别用函数实现，输出每种排序过程中元素的比较次数、交换（或移动）次数，以及排序过程所消耗的时间（以s或ms为单位）；基本要求基本要求 2将问题1中所有1000个（或更多）整数读入数组A，用快速排序算法对数组A中的元素排序，输

6、出排序结果、排序过程中元素的比较和交换（移动）次数、排序算法消耗的时间;3.利用上面实现的任意一种排序算法，对实验题目一所产生的学生信息文件studinfo.dat，读取其中的所有学生信息：（1）按学号排序输出学生信息；（2）按姓名排序输出学生信息；（3）按三门课程的平均分从高到低排序输出学生信息（除了学生基本信息外，还要输出每个学生的平均成绩），最后再加一行输出信息：每门课程的平均成绩。快速排序快速排序n快速排序快速排序(Quick Sorting)(Quick Sorting)是迄今为止所有内排序算法中是迄今为止所有内排序算法中速度最快的一种。其基本思想是：取待排序序列中的某速度最快的一种

7、。其基本思想是：取待排序序列中的某个元素作为基准（也成为枢轴元素，一般取第一个元素）个元素作为基准（也成为枢轴元素，一般取第一个元素），通过一趟排序，将待排序列划分为左右两个子序列，通过一趟排序，将待排序列划分为左右两个子序列，左子序列元素的关键字均小于或等于基准元素的关键字，左子序列元素的关键字均小于或等于基准元素的关键字，右子序列的关键字则大于或等于基准元素的关键字，然右子序列的关键字则大于或等于基准元素的关键字，然后分别对两个子序列继续进行排序，直至整个序列有序。后分别对两个子序列继续进行排序，直至整个序列有序。无无 序序 的的 记记 录录 序序 列列无序的左子序列无序的左子序列无序的右

8、子序列无序的右子序列枢轴枢轴一次划分一次划分分别进行快速排序分别进行快速排序38 65 97 13 27 49 551234567849049pivotij快速排序中的一趟划分快速排序中的一趟划分38 65 97 13 27 49 551234567804949pivotijaj与与pivot比较，比较，aj小则小则ajai38 65 97 13 27 49 551234567804949pivotij快速排序中的一趟划分快速排序中的一趟划分i38 65 97 13 27 49 551234567804949pivotjai与与pivot比较，比较，ai大则大则ai aj；否则；否则i增增13

9、8 65 97 13 27 49 551234567804949pivotij快速排序中的一趟划分快速排序中的一趟划分i386597 13 27 49 551234567804949pivotjai与与pivot比较，比较，ai大则大则ai aj；否则；否则i增增1快速排序中的一趟划分快速排序中的一趟划分i386597 13 27 49 551234567804949pivotjaj与与pivot比较，比较，aj小则小则aj ai；否则；否则j减减1123456789i386597 13 27 49 550449pivotj快速排序中的一趟划分快速排序中的一趟划分i386597 132749

10、551234567804949pivotjai与与pivot比较，比较，ai大则大则ai aj；否则；否则i加加1123456789i386597 1349 550449pivotj27快速排序中的一趟划分快速排序中的一趟划分i386597132749 551234567804949pivotjaj与与pivot比较，比较，aj小则小则ai aj；否则；否则j减减1i386597132749 551234567804949pivotj快速排序中的一趟划分快速排序中的一趟划分i386597132749 551234567804949pivotji与与j相等时，完成一次划分，相等时，完成一次划分，

11、枢轴元素归位枢轴元素归位i386597132749 551234567804499j快速排序中的一趟划分快速排序中的一趟划分 38 27 13 49 97 49 551234567804659int Partition(SqList&L,int low,int high)L.r0=L.rlow;pivotkey=L.r0.key;/元素移动元素移动 i=low;j=high;while(ij)while(i=pivotkey)j-;L.ri=L.rj;/元素移动元素移动 while(ij&L.ri.key=pivotkey)i+;L.rj=L.ri;/元素移动元素移动 L.ri=L.r0;/元

12、素移动元素移动 return i;/返回枢轴元素最后确定的位置返回枢轴元素最后确定的位置 /Partition38 65 97 13 27 49 554904840 30 20 15925123456781059pivotij快快速速排排序序中中的的一一趟趟划划分分840 30 20 1592555ij10840 30 20 15925ij540830 20 15925 40ij598930 20 1525 40ij5308930 20 15 30 25 40i j512345678910快速排序快速排序int Partition(SqList&L,int low,int high).retu

13、rn i;/返回枢轴元素的位置返回枢轴元素的位置/Partitionvoid QSort(SqList&L,int low,int high)/对对L.rlowL.rhigh中的元素序列进行快速排序中的元素序列进行快速排序 if(low 0;-i)/把把H建成大顶堆建成大顶堆 HeapAdjust(H,i,H.length);for(i=H.length;i 1;-i)H.r1 H.ri;/堆顶记录和当前未排子序列中最后一个记录相交换堆顶记录和当前未排子序列中最后一个记录相交换 HeapAdjust(H,1,i-1);/将将H.rl.i-1 重新调整为大顶堆重新调整为大顶堆 /HeapSort

14、 for(i=H.length;i 1;-i)H.r1H.ri;/堆顶记录和当前未排子序列中最后一个记录相交换堆顶记录和当前未排子序列中最后一个记录相交换 /三次移动元素三次移动元素 HeapAdjust(H,1,i-1);/将将H.rl.i-1 重新调整为大重新调整为大/小顶堆小顶堆 示例示例 将将H建成大建成大/小顶堆小顶堆 for(i=H.length/2;i 0;-i)/把把H建成大建成大/小顶堆小顶堆 HeapAdjust(H,i,H.length);123685472430539191368547243053124736911253302485 堆排序算法堆排序算法(筛选算法筛选算

15、法)vtypedef SqList HeapType;/堆采用顺序存储结构堆采用顺序存储结构void HeapAdjust(HeapType&H,int s,int m)/HeapAdjust rc=H.rs;/元素移动元素移动 for(j=2*s;j=m;j*=2)/沿沿key较小的孩子结点向下筛选较小的孩子结点向下筛选 if(j H.rj+l.key)+j;/j为为key较小的记录的下标较小的记录的下标 if(rc.Key 1)MergeSort(待排序列的前半区间待排序列的前半区间)；MergeSort(待排序列的后半区间待排序列的后半区间)；已排好序的前半区间、后半区间合并成一个有序序

16、列；已排好序的前半区间、后半区间合并成一个有序序列；/if/MergeSortv采用顺序存储结构，对于由下标采用顺序存储结构，对于由下标st界定的一个序列，前界定的一个序列，前半区间为半区间为s (s+t)/2，后半区间为，后半区间为(s+t)/2+1 tvoid MergeSort(SqList&L,int s,int t)/归并排序归并排序 if(s t)m=(s+t)/2;MergeSort(L,s,m)；MergeSort(L,m+1,t)；Merge(L,s,m,t);/合并合并L.rsL.rm与与L.rm+1L.rt /if/MergeSort 两路归并算法两路归并算法v以顺序表作

17、为存储结构以顺序表作为存储结构void Merge(SqList&L,int i,int m,int n)/两路归并两路归并 /引入辅助数组空间引入辅助数组空间temp，有序序列为，有序序列为ri.m和和rm+1.n/Merge b=i;for(j=m+1,k=1;i=m&j=n;+k)/for/ifi if(L.ri.key L.rj.key)temp.rk=L.ri+;else temp.rk=L.rj+;for(;i=m;)temp.rk+=L.ri+;for(;j=n;)temp.rk+=L.rj+;for(i=b,k=1;i=n;)L.ri+=temp.rk+;随机数随机数n随机函数

18、rand()n#include RAND_MAX在stdlib.h中定义，不大于双字节整数的最大值32767n产生0,RAND_MAX 之间的随机数magic=rand();n产生0,b-1 之间的随机数magic=rand()%b;n产生a,a+b-1 之间的随机数magic=rand()%b+a;随机数随机数n随机函数srand为函数rand()设置随机数种子来实现对函数rand所产生的伪随机数的“随机化”n通过键入随机数种子，产生0,100之间的随机数scanf(%u,&seed);srand(seed);magic=rand()%100+1;n使用计算机读取其时钟值并把该值自动设置为随

19、机数种子，产生0,100之间的随机数n函数time()返回以秒计算的当前时间值，该值被转换为无符号整数并用作随机数发生器的种子#include srand(unsigned)time(NULL);magic=rand()%100+1;计算代码段运行时间示例计算代码段运行时间示例#include clock_t CLK_1,CLK_2;/typedeflongclock_t;CLK_1=clock();/此处为需要测试运行时间的代码段此处为需要测试运行时间的代码段CLK_2=clock();printf(duration_time:%d,CLK_2 CLK_1);#include time_t start_time,end_time;start_time =time(0);/此处为需要测试运行时间的代码段此处为需要测试运行时间的代码段end_time=time(0);printf(duration_time:%lf,difftime(end_time,start_time);