中南大学数据结构实验报告(七)

中南大学数据结构试验报告题目实验七学生姓名王云鹏学号8213180228指导老师郑瑾学院计算机学院专业班级物联网1802完成时间2020.6指导老师评定签名实验七1.需求分析本实验目的是使读者，掌握常用排序方法的基本思想，通过实验加深理解各种排序算法，通过实验掌握各种排序方法的时间复杂度分析，了解各种排序方法的优缺点及适用范围。1．排序算法的实现（设计性实验）问题描述排序是计算机领域的一项重要技术，是程序设计中的一种重要运算。它的功能是将一个数据元素的任意序列重新排列成一个按键有序的序列。学习和研究各种排序方法是计算机工作者的一项重要工作课题。基本要求随机产生n个整数（依次为n赋值100、200、300、1000和2000），将其存于数组A[1..n]中。对主要算法（顺序查找、插入排序、归并排序、堆排序和快速排序）进行实验比较，计算出平均比较次数cn、平均移动次数mn及执行时间tn。cn和mn由程序自动计算，tn由系统时间计算。对实验结果数据进行对比分析。测试数据由随机数生成器决定。实现提示(1)设计一个驱动程序，其任务是，随机输入一组原始数据A[1..n]，对于查找还需准备一个键码值（可以随机产生，也可在A[1..n]中按索引号挑选若干有代表性的数据）。对每组原始数据，分别调用查找或排序算法过程。(2)为了自动计算cn和mn需要在每个算法过程中的适当位置插入计数操作。手工计算每个算法的执行时间tn时，为了减少计时误差，删除所插入的计数操作，并按n的大小确定一个K，对每个查找或排序算法过程反复调用K次，在调用开始前设置一个计时起点t0，在K次调用执行后可打印信息。设计时的终点为t1，则(t1t0)/K便是算法的大致执行时间。选作内容对不同的输入表长做试验，观察含义相同的变量相对于表长的变化关系，还可以对稳定性做验证。2．统计成绩（综合性实验）问题描述给出n个学生的m门考试的成绩表，每个学生的信息由学号、姓名及各科成绩组成。对学生的考试成绩进行有关统计，并打印统计表。基本要求(1)按总数高低次序，打印出名次表，分数相同的为同一名次。(2)按名次打印出每个学生的学号、姓名、总分以及各科成绩。测试数据由读者依据软件工程的测试技术自己确定。注意测试边界数据。选作内容对各科成绩设置不同的权值2.概要设计设计性实验函数：综合性实验函数：3.详细设计设计性实验#includeiostream#includefstream#includectimeusingnamespacestd;templatetypenametvoidprint_array(tarray[],intarray_size){//模板，打印数组for(inti=0;iarray_size;i++){coutarray[i];if((i+1)%50==0)coutendl;}coutendl;}templatetypenametvoidmy_swap(t&a,t&b){//模板，交换数据a、bttemp=a;a=b;b=temp;}classancestor{public:longcn=0;//平均比较次数longmn=0;//平均移动次数longtn=0;//平均执行时间,单位：CPU时钟数intarray_size;int*array;ancestor(intn)//初始化array,存放待用数字序列{array_size=n;//array=newint[array_size];array=(int*)malloc(array_size*sizeof(int));//位array分配空间//intx[array_size];//array=x;srand((unsigned)time(NULL));//随机数种子for(inti=0;iarray_size;i++){array[i]=rand()%array_size;//用随机数序列初始化array}}};classseq_search:publicancestor//顺序查找{public:seq_search(intn,intdest):ancestor(n){clock_tstart_time,end_time;start_time=clock();//计时程序intflag=0;//是否查找到的标志位for(inti=0;in;i++){//遍历查找cn++;if(array[i]==dest){//找到flag=1;//coutdest位于序列的第i+1位endl;}}end_time=clock();//停止计时//tn=(double)(end_time-start_time)/CLOCKS_PER_SEC;tn=end_time-start_time;if(flag==0){//没找到//cout数字序列中没有destendl;}}};classinsert_sort:publicancestor//插入排序{public:insert_sort(intn):ancestor(n){clock_tstart_time,end_time;start_time=clock();//计时for(inti=1;in;i++){//遍历所有数据，看能否往前插入cn++;if(array[i]array[i-1]){//若前一个比当前的大，就接着往前寻找，否则说明当前数据有序，不需要移动inttemp=array[i];intj;for(j=i-1;temparray[j]&&j=0;j--){//移动比当前所有数据大的数，向后移动一位，覆盖array[j+1]=array[j];cn++;//计数mn++;//coutjendl;}array[j+1]=temp;//最后，插入当前数据到比他略小的数据之后}}end_time=clock();tn=end_time-start_time;}};classmerge_sort:publicancestor//归并排序{public:merge_sort(intn):ancestor(n){clock_tstart_time,end_time;start_time=clock();//计时my_sort(array,array_size,0,array_size-1);//排序end_time=clock();tn=end_time-start_time;}voidmy_sort(intarray[],intarray_size,intleft,intright){//array为待排序数组，left为拆开的下界，right为上界if(leftright){intmid=(int)((left+right)/2);my_sort(array,array_size,left,mid);//拆开上半部分my_sort(array,array_size,mid+1,right);//拆开下半部分merge(array,array_size,left,mid,right);//归并拆开的部分}}voidmerge(intarray[],intarray_size,intleft,intmid,intright){//归并inti,j,k;inttemp[right-left+1];//存放需要参加比较的数据for(inti=left;i=right;i++){//从array赋值，初始化temptemp[i-left]=array[i];}for(i=left,j=mid+1,k=left;i=mid&&j=right;k++){//两条数据合并，挨个比较并在一起if(temp[i-left]=temp[j-left]){//i小，将i所在数据存入arrayarray[k]=temp[i-left];i++;}else{//j小，将j所在数据存入arrayarray[k]=temp[j-left];j++;}cn++;mn++;}while(i=mid){//某条数据放完，将剩下的数据直接放入arrayarray[k++]=temp[i-left];i++;mn++;}while(j=right){array[k++]=temp[j-left];j++;mn++;}}};classheap_sort:publicancestor//堆排序{public:heap_sort(intn):ancestor(n){clock_tstart_time,end_time;start_time=clock();//计时for(inti=array_size/2;i=0;i--){heap_adjust(i,array_size-1);//建立一个大顶堆}swap(array[0],array[array_size-1]);//将堆顶与堆底互换mn=mn+3;for(inti=array_size-2;i0;i--){//不断将堆顶与堆底互换，画完调整堆，使之保持大顶堆。而有序的数据都挨个沉到堆底，最终从小到大排序heap_adjust(0,i);swap(array[0],array[i]);mn=mn+3;}end_time=clock();tn=end_time-start_time;}voidheap_adjust(ints,intm){//大顶堆，调整堆，从array[s...m]使保持大顶堆（假设：除了以s的位置不对，其他都是对的）inttemp=array[s];mn++;for(intj=2*s+1;j=m;j=j*2+1){//调整以s为顶的堆if(jm&&array[j]array[j+1]){//找到更大的儿子，j为儿子的下标j++;}if(temp=array[j]){//若s所在已经是最大的位置，则是大顶堆，推出循环break;}array[s]=array[j];//更大的向上浮动s=j;//使s记录已经向上浮动数据的位置mn++;}array[s]=temp;//s所在数据放回堆中mn++;}};classquick_sort:publicancestor//快速排序{public:quick_sort(intn):ancestor(n){clock_tstart_time,end_time;start_time=clock();//计时q_sort(0,array_size-1);//排序end_time=clock();tn=end_time-start_time;}intpartition(intlow,inthigh){//分段，并且使一次排序inttemp=array[low];//分界数，根据分界数将待排序列分成大小的两段mn++;while(lowhigh){//遍历，分别从左右向中间靠近，左右互换，完成一次排序while(lowhigh&&array[high]=temp){//从右边，挨个寻找比分界数小的数high--;cn++;}if(lowhigh){//判断是处理特殊情况array[low++]=array[high];//找到比分界数小的数，放大左边去mn++;}while(lowhigh&&array[low]=temp){//从左边，挨个寻找比分界数大的数low++;cn++;}if(lowhigh){array[high--]=array[low];//找到比分界数大的数，放到右边去（此时，右边该位置的数，已经放到左边）mn++;}}array[low]=temp;//将分界数放回mn++;returnlow;}voidq_sort(intlow,inthigh){//快排if(lowhigh){intmid=partition(low,high);//分段，排一次，此时，左边都是比分界数小的数，右边都是比分界数大的数q_sort(low,mid-1);//排列左半边的数