数据结构内排序实验报告_数据结构排序程序实例
数据结构内排序实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构排序程序实例”。
一、实验目的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(“nn”);}（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）结果如下图所示：
