数据结构排序实验报告.pdf
数据结构课程设计报告数据结构课程设计报告实验五实验五 排序排序一、需求分析：一、需求分析：本演示程序用本演示程序用 C+6.0C+6.0 编写，完成各种排序的实现，对输入的一组数字实现不同的排序编写，完成各种排序的实现，对输入的一组数字实现不同的排序方法，对其由小到大顺序输出。方法，对其由小到大顺序输出。1 1分别对直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序算法分别对直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序算法进行编写。进行编写。2 2、对存储的函数即输入的数字进行遍历。、对存储的函数即输入的数字进行遍历。3 3、初始化函数对输入的数字进行保存。、初始化函数对输入的数字进行保存。4 4、主函数实现使用者操作界面的编写，对输入、选择、保存、输出的各种实现。、主函数实现使用者操作界面的编写，对输入、选择、保存、输出的各种实现。这当中还包括了各个函数的调用的实现。这当中还包括了各个函数的调用的实现。5 5、程序所能到达的功能：完成对输入的数字的生成，并通过对各排序的选择实现、程序所能到达的功能：完成对输入的数字的生成，并通过对各排序的选择实现1数字从小到大的输出。数字从小到大的输出。二、程序主要功能以及基本要求：二、程序主要功能以及基本要求：1 1、设计一个菜单，格式如下：、设计一个菜单，格式如下：1 1、直接插入排序、直接插入排序2 2、希尔排序、希尔排序3 3、冒泡排序、冒泡排序4 4、快速排序、快速排序5 5、选择排序、选择排序6 6、堆排序、堆排序7 7、退出、退出2 2、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。三、系统框架图：三、系统框架图：本程序包含了本程序包含了 9 9 个函数，它们分别是：个函数，它们分别是：1 1、直接插入排序的算法函数、直接插入排序的算法函数 InsertSortInsertSort。2 2、希尔排序的算法函数、希尔排序的算法函数 ShellSortShellSort。3 3、冒泡排序算法函数、冒泡排序算法函数 BubbleSortBubbleSort。4 4、快速排序的算法函数、快速排序的算法函数 PartitionPartition。5 5、选择排序算法函数、选择排序算法函数 SelectSortSelectSort。6 6、堆排序算法函数、堆排序算法函数 HeapAdjustHeapAdjust。7 7、对存储数字的遍历函数、对存储数字的遍历函数 VisitVisit。8 8、初始化函数、初始化函数 InitSqListInitSqList。9 9、主函数、主函数 mainmain。主函数主函数各各个个排排序序算算法法函函数数对对入入数数进进遍遍初初化化输输的的组组行行历历始始操操作作界界面面的的设设计，计，函函数数的的调用。调用。四、详细设计四、详细设计实现各个算法的主要内容，下面是各个函数的主要信息：实现各个算法的主要内容，下面是各个函数的主要信息：1 1各个排序函数的算法：各个排序函数的算法：2一、直接插入排序一、直接插入排序void InsertSort(SqList&L)void InsertSort(SqList&L)int i,j;int i,j;for(i=2;i=L.length;i+)for(i=2;i=L.length;i+)if(L.ri.key L.ri-1.key)if(L.ri.key L.ri-1.key)L.r0=L.ri;L.r0=L.ri;L.ri=L.ri-1;L.ri=L.ri-1;for(j=i-2;(L.r0.key L.rj.key);j-)for(j=i-2;(L.r0.key L.rj.key);j-)L.rj+1=L.rj;L.rj+1=L.rj;L.rj+1=L.r0;L.rj+1=L.r0;二、希尔排序二、希尔排序void ShellSort(SqList&L)void ShellSort(SqList&L)int i,j;int i,j;int dk=1;/int dk=1;/增量增量while(dk=L.length/3)while(dk 0)while(dk0)dk/=3;/dk/=3;/减小增量减小增量for(i=dk;i=L.length;i+)for(i=dk;i=dk)&(L.rj-dk.key L.r0.key)while(j=dk)&(L.rj-dk.key L.r0.key)L.rj.key=L.rj-dk.key;L.rj.key=L.rj-dk.key;j-=dk;j-=dk;L.rj.key=L.r0.key;L.rj.key=L.r0.key;三、冒泡排序三、冒泡排序void BubbleSort(SqList&L)void BubbleSort(SqList&L)int i,j;int i,j;for(i=0;iL.length-2;i+)for(i=0;iL.length-2;i+)int flag=1;int flag=1;for(j=0;jL.length-i-2;j+)for(j=0;j L.rj+1.key)if(L.rj.key L.rj+1.key)flag=0;flag=0;int temp;int temp;temp=L.rj.key;temp=L.rj.key;L.rj.key=L.rj+1.key;L.rj.key=L.rj+1.key;L.rj+1.key=temp;L.rj+1.key=temp;/假设无交换说明已经有序假设无交换说明已经有序if(flag=1)if(flag=1)break;break;4 四、快速排序四、快速排序int Partition(SqList&L,int low,int high)int Partition(SqList&L,int low,int high)/分割区域函数分割区域函数L.r0=L.rlow;L.r0=L.rlow;int pivotkey=L.rlow.key;/int pivotkey=L.rlow.key;/一般将顺序表第一个元素作为支点一般将顺序表第一个元素作为支点while(low high)while(low high)while(low=pivotkey)while(low=pivotkey)high-;high-;L.rlow=L.rhigh;L.rlow=L.rhigh;while(lowhigh&L.rlow.key=pivotkey)while(lowhigh&L.rlow.key=pivotkey)low+;low+;L.rhigh=L.rlow;L.rhigh=L.rlow;L.rlow=L.r0;/L.rlow=L.r0;/返回枢轴位置返回枢轴位置return low;return low;void QSort(SqList&L,int low,int high)void QSort(SqList&L,int low,int high)/每张子表的快速排序每张子表的快速排序if(lowhigh)if(lowhigh)int pivotloc=Partition(L,low,high);int pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);QSort(L,pivotloc+1,high);void QuickSort(SqList&L)void QuickSort(SqList&L)5 QSort(L,1,L.length);QSort(L,1,L.length);五、简单项选择择排序五、简单项选择择排序void SelectSort(SqList&L)void SelectSort(SqList&L)int min;int min;int j;int j;for(int i=0;i L.length;i+)for(int i=0;i L.length;i+)/选择第选择第 i i 小的记录，并交换小的记录，并交换j=i;j=i;min=L.ri.key;min=L.ri.key;for(int k=i;k L.length;k+)for(int k=i;k L.length;k+)/在在 Ri.n-1Ri.n-1中选择最小的记录中选择最小的记录if(L.rk.key min)if(L.rk.key min)min=L.rk.key;min=L.rk.key;j=k;j=k;if(i!=j)if(i!=j)/与第与第 i i 个记录交换个记录交换int temp=L.ri.key;int temp=L.ri.key;L.ri.key=L.rj.key;L.ri.key=L.rj.key;L.rj.key=temp;L.rj.key=temp;六、堆排序六、堆排序void HeapAdjust(HeapType&H,int s,int m)void HeapAdjust(HeapType&H,int s,int m)6/堆调整，将记录调整为小顶堆堆调整，将记录调整为小顶堆int j;int j;RedType rc=H.rs;/RedType rc=H.rs;/暂时存储根结点暂时存储根结点for(j=2*s;j=m;j*=2)for(j=2*s;j=m;j*=2)/沿着结点记录较小的向下筛选沿着结点记录较小的向下筛选if(jm&H.rj.keyH.rj+1.key)if(jm&H.rj.key=H.rj.key)if(rc.key=H.rj.key)break;break;H.rs=H.rj;H.rs=H.rj;s=j;s=j;H.rs=rc;H.rs=rc;void HeapSort(HeapType&H)void HeapSort(HeapType&H)int i;int i;RedType temp;RedType temp;for(i=H.length;i0;-i)for(i=H.length;i0;-i)HeapAdjust(H,i,H.length);HeapAdjust(H,i,H.length);for(i=H.length;i1;-i)for(i=H.length;i1;-i)temp=H.r1;temp=H.r1;H.r1=H.ri;H.r1=H.ri;H.ri=temp;H.ri=temp;HeapAdjust(H,1,i-1);HeapAdjust(H,1,i-1);7 2 2遍历函数与初始化遍历函数与初始化void Visit(SqList L)void Visit(SqList L)for(int i=1;i=L.length;i+)for(int i=1;i=L.length;i+)coutL.ri.key;coutL.ri.key;coutendl;coutendl;void InitSqList(SqList&L,int a)void InitSqList(SqList&L,int a)for(int i=1;i=L.length;i+)for(int i=1;i=L.length;i+)L.ri.key=ai;L.ri.key=ai;五、测试结果五、测试结果以下是各种界面的测试结果：以下是各种界面的测试结果：1 1输入的界面输入的界面:2 2排排序序操操作作界界面面：83 3各种排序的结果：各种排序的结果：六、设计不足以及存在问题六、设计不足以及存在问题本程序是基于本程序是基于 C+6.0C+6.0 的实现，其实在设计上的改良可以利用类进行操作，这种类的改的实现，其实在设计上的改良可以利用类进行操作，这种类的改9良了存储上的不足还可以实现了，对各种的函数基于类的实现，这就是对本程序的改良，良了存储上的不足还可以实现了，对各种的函数基于类的实现，这就是对本程序的改良，这是十分重要的与是改良的基础。这是十分重要的与是改良的基础。本程序出现过的问题是主函数对个函数的调用以及对存储数组的调用上出现了问题，本程序出现过的问题是主函数对个函数的调用以及对存储数组的调用上出现了问题，导致排序的结果以及排序的界面出现了问题，的不到实现。后来对算法进行改良，最终把导致排序的结果以及排序的界面出现了问题，的不到实现。后来对算法进行改良，最终把问题得以解决。问题得以解决。10
