（封面）
学生实验报告
学 院：国际经贸学院
课程名称：数据结构
专业班级：09电子商务
姓 名：
学 号：
学生实验报告
（经管类专业用）
一、实验目的及要求：
1、目的
掌握内排序的方法。
2、内容及要求
实验题10.1 编写一个程序实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程
实验题10.2 编写一个程序实现希尔插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程
实验题10.3 编写一个程序实现冒泡排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程
实验题10.4 编写一个程序实现快速排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程
实验题10.5 编写一个程序实现直接选择排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程
二、仪器用具：
三、实验方法与步骤:
10.1
#include
#define MAXE 20
typedef int KeyType;
typedef char InfoType[10];
typedef struct
{
KeyType key;
InfoType data;
} RecType;
void InsertSort(RecType R[],int n)
{
int i,j,k;
RecType temp;
for (i=1;i { temp=R[i]; j=i-1; while (j>=0 && temp.key { R[j+1]=R[j]; j--; } R[j+1]=temp; printf(" i=%d ",i); for (k=0;k printf("%3d",R[k].key); printf("\n"); } } void main() { int i,k,n=10; KeyType a[]={9,8,7,6,5,4,3,2,1,0}; RecType R[MAXE]; for (i=0;i R[i].key=a[i]; printf("\n"); printf(" first main word "); for (k=0;k printf("%3d",R[k].key); printf("\n"); InsertSort(R,n); printf(" result "); for (k=0;k printf("%3d",R[k].key); printf("\n\n"); getch(); } 10.2 #include #define MAXE 20 typedef int KeyType; typedef char InfoType[10]; typedef struct { KeyType key; InfoType data; } RecType; void ShellSort(RecType R[],int n) { int i,j,d,k; RecType temp; d=n/2; while (d>0) { for (i=d;i { j=i-d; while (j>=0 && R[j].key>R[j+d].key) { temp=R[j]; R[j]=R[j+d]; R[j+d]=temp; j=j-d; } } printf(" d=%d: ",d); for (k=0;k printf("%3d",R[k].key); printf("\n"); d=d/2; } } void main() { int i,k,n=10; KeyType a[]={9,8,7,6,5,4,3,2,1,0}; RecType R[MAXE]; for (i=0;i R[i].key=a[i]; printf("\n"); printf("first main word "); for (k=0;k printf("%3d",R[k].key); printf("\n"); ShellSort(R,n); printf(" result "); for (k=0;k printf("%3d",R[k].key); printf("\n\n"); getch(); } 10.3 #include #define MAXE 20 typedef int KeyType; typedef char InfoType[10]; typedef struct { KeyType key; InfoType data; } RecType; void BubbleSort(RecType R[],int n) { int i,j,k; RecType temp; for (i=0;i { for (j=n-1;j>i;j--) if (R[j].key { temp=R[j]; R[j]=R[j-1]; R[j-1]=temp; } printf(" i=%d ",i); for (k=0;k printf("%2d",R[k].key); printf("\n"); } } void main() { int i,k,n=10; KeyType a[]={9,8,7,6,5,4,3,2,1,0}; RecType R[MAXE]; for (i=0;i R[i].key=a[i]; printf("\n"); printf(" first main word "); for (k=0;k printf("%2d",R[k].key); printf("\n"); BubbleSort(R,n); printf(" result "); for (k=0;k printf("%2d",R[k].key); printf("\n\n"); getch(); } 10.4 #include #define MAXE 20 typedef int KeyType; typedef char InfoType[10]; typedef struct { KeyType key; InfoType data; } RecType; void QuickSort(RecType R[],int s,int t) { int i=s,j=t,k; RecType temp; if (s { temp=R[s]; while (i!=j) { while (j>i && R[j].key>temp.key) j--; if (i { R[i]=R[j]; i++; } while (i i++; if (i { R[j]=R[i]; j--; } } R[i]=temp; printf(" "); for (k=0;k<10;k++) if (k==i) printf(" [%d]",R[k].key); else printf("%4d",R[k].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 R[MAXE]; for (i=0;i R[i].key=a[i]; printf("\n"); printf(" first main word "); for (k=0;k printf("%4d",R[k].key); printf("\n"); QuickSort(R,0,n-1); printf(" result "); for (k=0;k printf("%4d",R[k].key); printf("\n\n"); getch(); } 10.5 #include #define MAXE 20 typedef int KeyType; typedef char InfoType[10]; typedef struct { KeyType key; InfoType data; } RecType; void SelectSort(RecType R[],int n) { int i,j,k,l; RecType temp; for (i=0;i { k=i; for (j=i+1;j if (R[j].key k=j; if (k!=i) { temp=R[i];R[i]=R[k];R[k]=temp; } printf(" i=%d ",i); for (l=0;l printf("%2d",R[l].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 R[MAXE]; for (i=0;i R[i].key=a[i]; printf("\n"); printf(" first main word "); for (k=0;k printf("%2d",R[k].key); printf("\n"); SelectSort(R,n); printf(" result "); for (k=0;k printf("%2d",R[k].key); printf("\n\n"); getch(); } 四、实验结果与数据处理： 10.1 10.2 10.3 10.4 10.5 五、讨论与结论 要掌握每种算法，并能运行，整个过程要认真，细心。
六、指导教师评语及成绩： 评语： 成绩： 指导教师签名： 批阅日期： 一、实验目的 1、了解内排序都是在内存中进行的。 2、为了提高数据的查找速度，需要对数据进行排序。 3、掌握内排序的方法。 二、实验内容 1、设计一个程序exp10—1.cpp实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。 （1） 源程序如下所示： //文件名:exp10-1.cpp #include #define MAXE 20 //线性表中最多元素个数 typedef int KeyType; typedef char InfoType[10]; typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType; void InsertSort(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序 { int i,j,k; RecType temp; for (i=1;i { temp=R[i]; j=i-1; //从右向左在有序区R[0..i-1]中找R[i]的插入位置 while (j>=0 && temp.key { R[j+1]=R[j]; //将关键字大于R[i].key的记录后移 j--; } R[j+1]=temp; //在j+1处插入R[i] printf("i=%d,",i); //输出每一趟的排序结果 printf("插入%d,结果为: ",temp); for (k=0;k printf("%3d",R[k].key); printf("\n"); } } void main() { int i,k,n=10; KeyType a[]={9,8,7,6,5,4,3,2,1,0}; RecType R[MAXE]; for (i=0;i R[i].key=a[i]; printf("初始关键字: "); //输出初始关键字序列 for (k=0;k printf("%3d",R[k].key); printf("\n"); InsertSort(R,n); printf("最后结果: "); //输出初始关键字序列 for (k=0;k printf("%3d",R[k].key); printf("\n"); } （2） 运行的结果如下图所示： 2、设计一个程序exp10—2.cpp实现希尔插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。 （1） 源程序如下所示： //文件名:exp10-2.cpp #include #define MAXE 20 //线性表中最多元素个数 typedef int KeyType; typedef char InfoType[10]; 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 (d>0) { for (i=d;i { j=i-d; while (j>=0 && R[j].key>R[j+d].key) { temp=R[j]; //R[j]与R[j+d]交换 R[j]=R[j+d]; R[j+d]=temp; j=j-d; } } printf("d=%d: ",d); //输出每一趟的排序结果 for (k=0;k printf("%3d",R[k].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 R[MAXE]; for (i=0;i R[i].key=a[i]; printf("初始关键字: "); //输出初始关键字序列 for (k=0;k printf("%3d",R[k].key); printf("\n"); ShellSort(R,n); printf("最后结果: "); //输出初始关键字序列 for (k=0;k printf("%3d",R[k].key); printf("\n\n"); } （2） 结果如下图所示： 3、设计一个程序exp10—3.cpp实现冒泡排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。 （1） 源程序如下所示： //文件名:exp10-3.cpp #include #define MAXE 20 //线性表中最多元素个数 typedef int KeyType; typedef char InfoType[10]; typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType; void BubbleSort(RecType R[],int n) //冒泡排序算法 { int i,j,k; RecType temp; for (i=0;i { for (j=n-1;j>i;j--) //比较,找出本趟最小关键字的记录 if (R[j].key { temp=R[j]; //R[j]与R[j-1]进行交换,将最小关键字记录前移 R[j]=R[j-1]; R[j-1]=temp; } printf("i=%d,冒出的最小关键字:%d,结果为: ",i,R[i].key); //输出每一趟的排序结果 for (k=0;k printf("%2d",R[k].key); printf("\n"); } } void main() { int i,k,n=10; KeyType a[]={9,8,7,6,5,4,3,2,1,0}; RecType R[MAXE]; for (i=0;i R[i].key=a[i]; printf("初始关键字: "); //输出初始关键字序列 for (k=0;k printf("%2d",R[k].key); printf("\n"); BubbleSort(R,n); printf("最后结果: "); //输出初始关键字序列 for (k=0;k printf("%2d",R[k].key); printf("\n"); } （2） 结果如下图所示：
第二篇：数据结构内排序实验报告
