数据结构内排序实验报告.doc

一、 实验目的1、 了解内排序都是在内存中进行的。2、 为了提高数据的查找速度，需要对数据进行排序。3、 掌握内排序的方法。二、 实验内容1、 设计一个程序exp101.cpp实现直接插入排序算法，并输出9,8,7,6,5,4,3,2,1,0的排序过程。（1） 源程序如下所示：/文件名:exp10-1.cpp#include #define MAXE 20/线性表中最多元素个数typedef int KeyType;typedef char InfoType10;typedef struct /记录类型KeyType key; /关键字项InfoType data; /其他数据项,类型为InfoType RecType;void InsertSort(RecType R,int n) /对R0.n-1按递增有序进行直接插入排序int i,j,k;RecType temp;for (i=1;i=0 & temp.keyRj.key) Rj+1=Rj;/将关键字大于Ri.key的记录后移j-; Rj+1=temp;/在j+1处插入Riprintf(i=%d,i);/输出每一趟的排序结果printf(插入%d,结果为: ,temp);for (k=0;kn;k+)printf(%3d,Rk.key);printf(n);void main()int i,k,n=10;KeyType a=9,8,7,6,5,4,3,2,1,0;RecType RMAXE;for (i=0;in;i+)Ri.key=ai;printf(初始关键字: );/输出初始关键字序列for (k=0;kn;k+)printf(%3d,Rk.key);printf(n);InsertSort(R,n);printf(最后结果: );/输出初始关键字序列for (k=0;kn;k+)printf(%3d,Rk.key);printf(n);（2） 运行的结果如下图所示：2、 设计一个程序exp102.cpp实现希尔插入排序算法，并输出9,8,7,6,5,4,3,2,1,0的排序过程。（1） 源程序如下所示：/文件名:exp10-2.cpp#include #define MAXE 20/线性表中最多元素个数typedef int KeyType;typedef char InfoType10;typedef struct /记录类型KeyType key;/关键字项InfoType data;/其他数据项,类型为InfoType RecType;void ShellSort(RecType R,int n)/希尔排序算法int i,j,d,k;RecType temp;d=n/2;/d取初值n/2while (d0) for (i=d;i=0 & Rj.keyRj+d.key) temp=Rj; /Rj与Rj+d交换Rj=Rj+d;Rj+d=temp;j=j-d;printf(d=%d: ,d);/输出每一趟的排序结果for (k=0;kn;k+)printf(%3d,Rk.key);printf(n); d=d/2; /递减增量dvoid main()int i,k,n=10;KeyType a=9,8,7,6,5,4,3,2,1,0;RecType RMAXE;for (i=0;in;i+)Ri.key=ai;printf(初始关键字: );/输出初始关键字序列for (k=0;kn;k+)printf(%3d,Rk.key);printf(n);ShellSort(R,n);printf(最后结果: );/输出初始关键字序列for (k=0;kn;k+)printf(%3d,Rk.key);printf(nn);（2） 结果如下图所示：3、 设计一个程序exp103.cpp实现冒泡排序算法，并输出9,8,7,6,5,4,3,2,1,0的排序过程。（1） 源程序如下所示：/文件名:exp10-3.cpp#include #define MAXE 20/线性表中最多元素个数typedef int KeyType;typedef char InfoType10;typedef struct /记录类型KeyType key; /关键字项 InfoType data; /其他数据项,类型为InfoType RecType;void BubbleSort(RecType R,int n)/冒泡排序算法int i,j,k;RecType temp;for (i=0;ii;j-)/比较,找出本趟最小关键字的记录if (Rj.keyRj-1.key) temp=Rj; /Rj与Rj-1进行交换,将最小关键字记录前移Rj=Rj-1;Rj-1=temp;printf(i=%d,冒出的最小关键字:%d,结果为: ,i,Ri.key);/输出每一趟的排序结果for (k=0;kn;k+)printf(%2d,Rk.key);printf(n); void main()int i,k,n=10;KeyType a=9,8,7,6,5,4,3,2,1,0;RecType RMAXE;for (i=0;in;i+)Ri.key=ai;printf(初始关键字: );/输出初始关键字序列for (k=0;kn;k+)printf(%2