数据结构实验报告编辑精选.docx

数据结构实验报告

第一篇：数据结构实验报告实验报告4排序一、实验目的1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。二、实验要求及内容要求编写的程序所能实现的功能包括：1、从键盘输入要排序的一组元素的总个数2、从键盘依次输入要排序的元素值3、对输入的元素进行快速排序4、对输入的元素进行折半插入排序三、实验代码及相关注释#includeusingnamespacestd;#include“malloc.h”typedefstruct{intkey;}RedType;typedefstruct{RedTyper[100];intlength;}SqList;//1快速排序的结构体typedefstruct{intdata[100];intlast;}Sequenlist;//2折半插入排序的结构体intPartition(SqList&L,intlow,inthigh)//1寻找基准{L.r[0]=L.r[low];//子表的第一个记录作基准对象intpivotkey=L.r[low].key;//基准对象关键字while(lowwhile(low=pivotkey)--high;L.r[low]=L.r[high];//小于基准对象的移到区间的左侧while(lowL.r[high]=L.r[low];//大于基准对象的移到区间的右侧}L.r[low]=L.r[0];returnlow;}voidQuickSort(SqList&L,intlow,inthigh)//1快速排序{//在序列low-high中递归地进行快速排序if(low{intpivotloc=Partition(L,low,high);//寻找基准QuickSort(L,low,pivotloc-1);//对左序列同样递归处理QuickSort(L,pivotloc+1,high);//对右序列同样递归处理}}Sequenlist*Sqlset()//2输入要折半插入排序的一组元素{Sequenlist*L;inti;L=(Sequenlist*)malloc(sizeof(Sequenlist));L->last=0;coutcin>>i;coutcoutif(i>0){for(L->last=1;L->lastlast++)cin>>L->data[L->last];L->last--;}return(L);}middlesort(Sequenlist*L)//2折半插入排序{inti,j,low,high,mid;for(i=1;ilast;i++){L->data[0]=L->data[i];low=1;high=i-1;while(low{mid=(low+high)/2;if(L->data[0]data[mid])high=mid-1;//插入点在前半区elselow=mid+1;//插入点在后半区}for(j=i;j>high+1;j--){L->data[j]=L->data[j-1];}//后移L->data[high+1]=L->data[0];//插入}return0;}intmain(){gg:cout>m;coutif(m==1){SqListL;intn;cout>n;coutcin>>L.r[i].key;}coutQuickSort(L,1,L.length);for(intj=1;j{cout}coutcout}if(m==2){Sequenlist*L;inti;L=Sqlset();coutmiddlesort(L);coutfor(i=1;ilast;i++){coutdata[i]}coutcoutgotogg;}if(m==3){exit(0);cout四、重要函数功能说明1、Sequenlist*Sqlset()输入要折半插入排序的一组元素2、intPartition(SqList&L,intlow,inthigh)寻找快速排序的基准3、voidQuickSort(SqList&L,intlow,inthigh)快速排序4、middlesort(Sequenlist*L)折半插入排序五、程序运行结果下图仅为分别排序一次，可多次排序，后面有相关截图：六、实验中遇到的问题、解决及体会1、起初编写快速排序的程序时，我是完全按照老师PPT上的算法敲上去的，然后建立了一个SqList的结构体，调试运行时出现错误，仔细查看才意识到Partition函数中L中应该包含元素key，而我建立结构体时没有注意，然后我将key这个元素补充进去，继续调试，又出现错误，提示我Par