实验六：排序算法的设计.doc

《实验六：排序算法的设计.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.学校代码：10128学号：201220905048《数据结构》实验报告（题目：排序算法的设计学生姓名：孙跃学院：理学院系别：数学系专业：信息与计算科学班级：信计12-2班任课教师：杜雅娟二〇一四年十一月..一、实验目的1.掌握排序算法；2.提高学生的分析问题和解决问题的实际能力。二、实验内容1、实现直接插入排序的算法；2、实现希尔排序的算法；3、实现起泡排序的算法；4、实现快速排序的算法；5、实现堆排序的算法。三、实验程序1、首先建立三个公用文件c1.h#include#include

2、pe.h>#include#include#include#include#include#include#include#include//状态代码#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1typedefintStatus;..typedefintBoolean;c9.h#

3、defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))c10-1.h#defineMAXSIZE20typedefintKeyType;structRedType{KeyTypekey;InfoTypeotherinfo;};structSqList{RedTyper[MAXSIZE+1];intlength;};2、插入排序在同一文件夹中建立如下5个文件：c1.h,c9.h,c10-1.h,bo10-1.cpp,algo10-1

4、.cpp.对algo10-1.cpp进行编译、构建和运行。bo10-1.cppvoidInsertSort(SqList&L){inti,j;for(i=2;i<=L.length;++i)..ifLT(L.r[i].key,L.r[i-1].key){L.r[0]=L.r[i];for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}}voidBInsertSort(SqList&L){inti,j,m,low,high;f

5、or(i=2;i<=L.length;i++){L.r[0]=L.r[i];low=1;high=i-1;while(low<=high){m=(low+high)/2;ifLT(L.r[0].key,L.r[m].key)high=m-1;elselow=m+1;}for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];L.r[high+1]=L.r[0];}..}algo10-1.cpp#include"c1.h"typedefintInfoType;#include"c9.h"#inc

6、lude"c10-1.h"#include"bo10-1.cpp"voidprint(SqListL){inti;for(i=1;i<=L.length;i++)printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);printf("");}#defineN8voidmain(){RedTyped[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};SqListl1,l2;inti;for(i=0;i

7、i++)l1.r[i+1]=d[i];l1.length=N;..l2=l1;printf("排序前:");print(l1);InsertSort(l1);printf("直接插入排序后:");print(l1);BInsertSort(l2);printf("折半插入排序后:");print(l2);}3、希尔排序在同一文件夹中建立如下4个文件：c1.h,c9.h,c10-1.h,algo10-3.cpp.对algo10-3.cpp进行编译、构建和运行。algo10-3.cpp//algo10-3.

8、cpp希尔排序#includetypedefintInfoType;#include"c9.h"#include"c10-1.h"voidShellInsert(SqList&L,intdk){inti,j;for(i=dk+1;i<=L.length;++i)ifLT(L.r[i].key,L.r[i-dk].key){..L.r[0]=