数据结构实验六

《数据结构实验六》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验六排序一、实验目的1、掌握内部排序的基本算法；2、分析比较内部排序算法的效率。二、实验预习说明以下概念1、简单排序：将一组记录按某关键字递增或递减的顺序排序。2、希尔排序：又称“缩小增量排序”属于插入排序类的方法。3、快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。4、堆排序：只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。三、实验内容和要求1、编程实现直接插入排序算法。程序代码

2、：#include#include#defineERROR0#defineOK1#defineLT(a,b)((a)<(b))#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTyper[MAXSIZE+1];intlength;}Sqlist;intInitList_Sq(Sqlist&L){inti=1;//printf("请输入待排序的记录的个数：");//scanf("%d",&L.length);printf(

3、"请输入待排序的记录的关键字（整型数）：");while(scanf("%d",&L.r[i])){i++;}L.length=i-1;returnOK;}/*InitList*/voidPrint_Sq(Sqlist&L)/*输出顺序表*/{inti;for(i=1;i<=L.length;i++)printf("%d",L.r[i]);}voidInsertSort(Sqlist&L){inti,j;for(i=2;i<=L.length;++i)if(LT(L.r[i],L.r[i-1]))//“<”，

4、需将L.r[i]插入有序子表{L.r[0]=L.r[i];//复制为哨兵L.r[i]=L.r[i-1];for(j=i-2;LT(L.r[0],L.r[j]);--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置}}voidmain(){SqlistS;InitList_Sq(S);Print_Sq(S);printf("1.简单插入排序");InsertSort(S);Print_Sq(S);/*printf("3.快速排序");QuickSor

5、t(S);Print_Sq(S);printf("5.堆排序");HeapSort(S);Print_Sq(S);*/}2、输入待排序序列：49386597132749（以输入一个字符作为结束）1）直接插入排序运行结果（写出每一趟的状态）：384965971327491338496597274913273849659749132738494965972）堆排序运行结果（写出每一趟的状态）：3、编程实现快速排序算法。程序代码：#include#include#defin

6、eERROR0#defineOK1#defineLT(a,b)((a)<(b))#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTyper[MAXSIZE+1];intlength;}Sqlist;intInitList_Sq(Sqlist&L){inti=1;//printf("请输入待排序的记录的个数：");//scanf("%d",&L.length);printf("请输入待排序的记录的关键字（整型数）：");while(scanf("%d",&L

7、.r[i])){i++;}L.length=i-1;returnOK;}/*InitList*/voidPrint_Sq(Sqlist&L)/*输出顺序表*/{inti;for(i=1;i<=L.length;i++)printf("%d",L.r[i]);}voidInsertSort(Sqlist&L){inti,j;for(i=2;i<=L.length;++i)if(LT(L.r[i],L.r[i-1]))//“<”，需将L.r[i]插入有序子表{L.r[0]=L.r[i];//复制为哨兵L.r[i]

8、=L.r[i-1];for(j=i-2;LT(L.r[0],L.r[j]);--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置}}intPartition(Sqlist&L,intlow,inthigh){//交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置，此时//在它之前（后）的记录均不大（小）于它。KeyTyp