数据结构课程设计报告

1数据结构课程设计报告题目：5班级:计算机1102学号：4111110030姓名：陈越指导老师：王新胜2一：需求分析1.运行环境TC2.程序所需实现的功能几种排序算法的演示，要求给出从初始开始时的每一趟的变化情况，并对各种排序算法性能作分析和比较：（1）直接插入排序；（2）折半插入排序；（3）冒泡排序；（4）简单选择排序；（5）快速排序；（6）堆排序；（7）归并排序.二：设计说明1.算法设计的思想1）、直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。2)、折半插入排序排序过程：用折半查找方法确定插入位置的排序叫折半插入排序。3)、冒泡排序3排序过程：将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].keyr[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上。对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置。重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止4)、简单选择排序排序过程：首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换。再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换。重复上述操作，共进行n-1趟排序后，排序结束。5)、快速排序基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=r[s]，x=rp.key。初始时令i=s,j=t。首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换。再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换。重复上述两步，直至i==j为止。再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止。6)、堆排序排序过程：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输4出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序。7)、归并排序归并——将两个或两个以上的有序表组合成一个新的有序表，叫归并。2-路归并排序排序过程：设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。两两合并，得到n/2个长度为2或1的有序子序列。再两两合并，……如此重复，直至得到一个长度为n的有序序列为止。2、程序的主要流程图53⑴直接插入排序；typedefstruct开始主菜单（排序选择）结束输入输入输入输入直接折半冒泡选择输出输出输出输出输入输入输入归并堆快速输出输出输出6{intkey;floatinfo;}JD;voidstraisort(JDr[],intn)//直接插入排序{inti,j;for(i=2;i=n;i++){r[0]=r[i];//复制为哨兵j=i-1;while(r[0].keyr[j].key){r[j+1]=r[j];//记录后移j--;}r[j+1]=r[0];//插入到正确位置}}⑵折半插入排序；voidbinsort(JDr[],intn)//折半插入排序{inti,j,x,s,m,k;for(i=2;i=n;i++){r[0]=r[i];//将r[i]暂存到r[0]x=r[i].key;s=1;j=i-1;while(s=j)//在r[s..j]中折半查找有序插入的位置{m=(s+j)/2;//折半if(xr[m].key)j=m-1;//插入点在低半区elses=m+1;//插入点在高半区}for(k=i-1;k=s;k--)r[k+1]=r[k];//记录后移r[s]=r[0];//插入}}⑶冒泡排序；voidbubble_sort(JDr[],intn)//冒泡排序{intm,i,j,flag=1;JDx;m=n-1;while((m0)&&(flag==1)){flag=0;for(j=1;j=m;j++)if(r[j].keyr[j+1].key){flag=1;x=r[j];7r[j]=r[j+1];r[j+1]=x;}m--;}}⑷简单选择排序；voidsmp_selesort(JDr[],intn)//简单选择排序{inti,j,k;JDx;for(i=1;in;i++){k=i;for(j=i+1;j=n;j++)if(r[j].keyr[k].key)k=j;//在r[i..n]中选择j最小的记录if(i!=k){x=r[i];//与第i个记录交换r[i]=r[k];r[k]=x;}}}⑸快速排序；voidqksort(JDr[],intt,intw)//快速排序{inti,j,k;JDx;if(t=w)return;i=t;j=w;x=r[i];//用字表的第一个记录作枢轴记录while(ij)//从表的两端交替地想中间扫描{while((ij)&&(r[j].key=x.key))j--;if(ij){r[i]=r[j];i++;}//将比枢轴记录小的记录交换到低端while((ij)&&(r[i].key=x.key))i++;if(ij){r[j]=r[i];j--;}//将比枢轴记录大的记录交换到高端}r[i]=x;//枢轴记录到位qksort(r,t,j-1);qksort(r,j+1,w);//返回枢轴所在位置}⑹堆排序；intsift(JDr[],intk,intm)//堆排序{inti,j;JDx;i=k;x=r[i];j=2*i;while(j=m)//沿key较大的孩子结点向下筛选{if((jm)&&{r[j].keyr[j+1].key))j++;//j为key较大的记录的下标8if(x.keyr[j].key)//rc应插入在位置i上{r[i]=r[j];i=j;j*=2;}elsej=m+1;}r[i]=x;//插入}⑺归并排序。voidmergesort(JDr[],intn)//归并排序{inti,s=1;JDt[M];while(sn){tgb(s,n,r,t);s*=2;if(sn){tgb(s,n,t,r);s*=2;}else{i=1;while(i=n)r[i]=t[i++];}}}voidtgb(ints,intn,JDr[],JDt[]){inti=1;while(i=(n-2*s+1)){merge(r,i,i+s-1,i+2*s-1,t);i=i+2*s;}if(i(n-s+1))merge(r,i,i+s-1,n,t);elsewhile(i=n)t[i]=r[i++];}voidmerge(JDr[],inth,intm,intw,JDt[]){inti,j,k;i=h;j=m+1;k=h-1;while((i=m)&&(j=w)){k++;if(r[i].key=r[j].key)t[k]=r[i++];elset[k]=r[j++];}if(im)9while(j=w)t[++k]=r[j++];elsewhile(i=m)t[++k]=r[i++];}三：上机结果及体会1.实际完成的情况说明（完成的功能，支持的数据类型等）类型int,输入10个数据，能够以直接插入排序，折半插入排序，冒泡排序，简单选择排序，快速排序，堆排序，归并排序。2.程序的性能分析，包括时空分析A.直接插入排序在整个排序过程（进行n-1趟插入排序）中，若待排序记录按关键字从小到大排列(正序)，所需进行关键字间比较的次数达最小值n-1,数据移动次数为2(n-1);若待排序记录按关键字从大到小排列(逆序),关键字间的比较次数达最大值（n+2）(n-1)/2,记录的移动次数也达最大值（n+4）(n-1)/2;若待排序记录是随机的，即待排序列中的记录可能出现的各种排列的概率相同，则我们可取上述最小值和最大值的平均值，作为直接插入时所需进行关键字间的比较次数和移动记录的次数，约为n2/4。由此，直接插入排序的时间复杂度为O(n2)、空间复杂度为S（n）=O(1)。所以直接插入排序算法简便，且容易实现。当待排序记录的数量n很小时，只是一种很好的排序方法。但是，通常待排序序列中的记录数量n很大，则不宜采用直接插入排序。B．折半插入排序10它所需要的关键字比较次数与关键字排列次序无关，仅依赖于数据元素个数。在插入第i个数据元素时，需要经过「log2i「+1次关键字比较，才能确定它的插入位置。因此将n个数据元素（为推导方便，设为n=2k）用折半插入排序所进行的关键字比较次数为：n*log2n。当n较大时，总的关键字比较次数比直接插入排序的最坏情况要少得多，但比其最好情况要多。折半插入排序所需要附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，折半插入排序的时间复杂度仍为O(n2)，空间复杂度为S(n)=O(1)。折半插入排序是一种稳定的排序。C．冒泡排序分析冒泡排序的效率，若初始序列为“正序”序列，则只需要进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动记录；反之，若初始序列为“逆序”序列，则需要进行n-1趟排序，需要进行n(n-1)/2次比较，且移动的次数为3n(n-1)/2。因此，总的时间复杂度为O(n2)、空间复杂度为S(n)=O(1)。冒泡排序需要一个附加存储空间以实现数据元素的交换。冒泡排序是一种稳定的排序方法。D．简单选择排序简单选择排序过程中，所需进行记录移动的操作次数较少，其最小值为“0”，最大值为3(n-1)。然而，无论记录的初始排序如何，所需进行的关键字间的比较次数相同，均为n(n-1)/2。直接选择排序中，关键字的比较次数与初始队列无关，假定整个排序表有n个数据元素，总共需要n-1趟排序，第i趟选择具有最小关键字数据元素所需的比较次数总是n-i-1次，11因此，总的关键字比较次数为n(n-1)/2,数据元素的移动次数与初始排列有关，当初始排列从小到大有序时，每一趟选择后都不需要交换，数据元素的移动次数为零，为最小值。最坏情况是每次都要移动，每趟三次，所以总共移动3(n-1)次。可见时间复杂度为O(n2)。由于直接选择排序过程中，交换数据元素一般不是在相邻位置的数据元素之间，因此，它不是一种稳定的排序。E．快速排序快速排序的平均时间为T(n)=knlnn,其中n为待排序序列中记录的个数，k为某个常数，经验证明，在所有同数量级的此类（先进的）排序方法中，快速排序的常数因子k最小。因此，就平均时间而言，快速排序时目前被认为最好的一种内部排序方法。快速排序的趟数取决于递归树的深度。如果每次划分对一个数据元素定位后，该数据元素的左侧子表与右侧子表的长度相等，则下一步将是对两个长度减半的子表进行排序，这是最理想的情况。在n个元素的序列中，堆一个元素定位所需时间为O(n)。若设T(n)是对n个元素的序列进行排序所需的时间，而且每次对一个数据元素正确定位后，正好把排序表划分为长度相等的两个子表，此时，总的计算时间为：T(n)=cnlog2n+nT(1)=O(nlog2n)。最后可证明，时间复杂度为O(nlog2n)。理想情况，需要的存储空间为O(log2n),最坏情况下将达到O(n)。快速排序是一种不稳定的排序方法，对于关键字相同的数据元素，排序后可能会颠倒次序。F．堆排序12堆排序算法的时间复杂度可用关键字的比较次数来测度。设堆中有n个节点，且2k-1≤n≤2k，则对应的完全二叉树有k层。在第i层上的节点数至多2i-1。在第一个形成初始堆的for循环中对每一个非叶结点调用了一次堆调整算法si