数据结构实验报告(7971).doc

南京信息工程大学 数据结构 实验(实习)报告实验(实习)名称 内排序 实验(实习)日期 2012.5.30 得分 指导老师 宣文霞 系 计算机系 专业 网络工程 班级 1 姓名 袁盼 学号 20102300242 1、需求分析（1 ）实现直接插入排序算法编写一个程序实现直接插入排序过程，并输出9，8，7，6，5，4，3，2，1，0的排序过程。输出形式例如：初始关键字 9 8 7 6 5 4 3 2 1 0排序次数i=1 8 9 7 6 5 4 3 2 1 0 i=2 7 8 9 6 5 4 3 2 1 0 最后结果： 0 1 2 3 4 5 6 7 8 9（2） 实现希尔插入排序算法编写一个程序实现希尔插入排序过程，并输出9，8，7，6，5，4，3，2，1，0的排序过程。（3） 实现冒泡排序算法编写一个程序实现冒泡排序过程，并输出9，8，7，6，5，4，3，2，1，0的排序过程。（4） 实现快速排序算法编写一个程序实现快速排序过程，并输出6，8，7，9，0，1，3，2，4，5的排序过程。（5） 实现直接选择排序算法编写一个程序实现直接排序过程，并输出6，8，7，9，0，1，3，2，4，5的排序过程。2.设计一、直接插入排序#include #define MAXE 20typedef 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处插入Ri*/printf( i=%d ,i);/*输出每一趟的排序结果*/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(n);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(nn);二、希尔排序#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/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(n);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);三、冒泡排序#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 ,i);/*输出每一趟的排序结果*/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(n);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(nn);四、实现快速排序法#include #define MAXE 20/*线性表中最多元素个数*/typedef int KeyType;typedef char InfoType10;typedef struct /*记录类型*/KeyType key; /*关键字项*/ InfoType data; /*其他数据项,类型为InfoType*/ RecType;void QuickSort(RecType R,int s,int t) /*对Rs至Rt的元素进行快速排序*/int i=s,j=t,k;RecType temp;if (si & Rj.keytemp.key) j-; /*从右向左扫描,找第个关键字小于temp.key的Rj */ if (ij) /*表示找到这样的Rj,Ri、Rj交换*/Ri=Rj;i+; while (ij & Ri.keytemp.key) i+;/*从左向右扫描,找第个关键字大于temp.key的记录Ri */ if (ij) /*表示找到这样的Ri,Ri、Rj交换*/Rj=Ri;j-; Ri=temp;printf( );/*输出每一趟的排序结果*/for (k=0;k10;k+)if (k=i)printf( %d,Rk.key);elseprintf(%4d,Rk.key);printf(n);QuickSort(R,s,i-1); /*对左区间递归排序*/QuickSort(R,i+1,t); /*对右区间递归排序*/void main()int i,k,n=10;KeyType a=6,8,7,9,0,1,3,2,4,5;RecType RMAXE;for (i=0;in;i+)Ri.key=ai;printf(n);printf( 初始关键字);/*输出初始关键字序列*/for (k=0;kn;k+)printf(%4d,Rk.key);printf(n);QuickSort(R,0,n-1);printf( 最后结果 );/*输出初始关键字序列*/for (k=0;kn;k+)printf(%4d,Rk.key);printf(nn);五、实现直接选择排序法#include #define MAXE 20/*线性表中最多元素个数*/typedef int KeyType;typedef char InfoType10;typedef struct /*记录类型*/KeyType key; /*关键字项*/ InfoType data; /*其他数据项,类型为InfoType*/ RecType;void SelectSort(RecType R,int n)/*直接选择排序算法*/int i,j,k,l;RecType temp;for (i=0;in-1;i+) /*做第i趟排序*/k=i;for (j=i+1;jn;j+) /*在当前无序区Ri.n-1中选key最小的Rk */if (Rj.keyRk.key)k=j; /*k记下目前找到的最小关键字所在的位置*/if (k!=i) /*交换Ri和Rk */temp=Ri;Ri=Rk;Rk=temp; printf( i=%d ,i);/*输出每一趟的排序结果*/for (l=0;ln;l+)printf(%2d,Rl.key);printf(n);void main()int i,k,n=10,m=5;KeyType a=6,8,7,9,0,1,3,2,4,5;RecType RMAXE;for (i=0;in;i+)Ri.key=ai;printf(n);printf( 初始关键字 );/*输出初始关键字序列*