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

《数据结构内排序实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构内排序实验报告.docx（5页珍藏版）》请在三一办公上搜索。

1、数据结构内排序实验报告一、 实验目的 1、 了解内排序都是在内存中进行的。 2、 为了提高数据的查找速度，需要对数据进行排序。 3、 掌握内排序的方法。 二、 实验内容 1、 设计一个程序exp101.cpp实现直接插入排序算法，并输出9,8,7,6,5,4,3,2,1,0的排序过程。 源程序如下所示： /文件名:exp10-1.cpp #include #define MAXE 20 /线性表中最多元素个数 typedef int KeyType; typedef char InfoType10; typedef struct /记录类型 KeyType key; /关键字项 InfoTyp

2、e 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处插入Ri printf(i=%d,i); /输出每一趟的排序结果 printf(插入%d,结果为: ,temp); for (k=0;kn;k+) printf(%3d,Rk.key); printf(n);

3、 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、 设计一个程序exp102.cpp实现希尔插

4、入排序算法，并输出9,8,7,6,5,4,3,2,1,0的排序过程。 源程序如下所示： /文件名: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;

5、 /d取初值n/2 while (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; /递减增量d 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(初始关键字:

6、 ); /输出初始关键字序列 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); 结果如下图所示： 3、 设计一个程序exp103.cpp实现冒泡排序算法，并输出9,8,7,6,5,4,3,2,1,0的排序过程。 源程序如下所示： /文件名:exp10-3.cpp #include #define MAXE 20 /线性表中最多元素个数 typedef int KeyTyp

7、e; 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,冒出的最小

8、关键字:%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(%2d,Rk.key); printf(n); BubbleSort(R,n); printf(最后结果: ); /输出初始关键字序列 for (k=0;kn;k+) printf(%2d,Rk.key); printf(n); 结果如下图所示：