数据结构实验报告:内部排序算法比较.doc
文本预览下载声明
实报 告
实验名称:任课教师:: 计网类 班 级: 2007级1班 学号:
姓 名:完成日期: 二、主要实验内容及要求:
(1)使用VC++语言编写程序,分别实现以下算法:插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序及基数排序。
(2)编译运行以上算法程序,在运行过程中观察它们的执行过程和结果,给出比较结果。
三、程序说明:(算法设计思路)
四、实验结果与结论:(经调试正确的源程序和程序的运行结果)
编程员:lghgxu
程序源代码:
一、插入排序
#include stdio.h
# include stdlib.h
# define OVERFLOW -2
typedef struct
{ int * elem;
int length;
}SqList;
SqList create(int n)//建立一个顺序表
{ SqList L;
L.elem = (int *)malloc( n*sizeof(int));
if(!L.elem) exit(OVERFLOW);
L.length=n;
for(int j=1;jn;j++)
{ printf(请输入第%d个整数:\n,j );
scanf(%d,L.elem[j]);
}
return L;
}
void InsertSort(SqList L) // 对顺序表L作直接插入排序。
{ int i,j;int count=0;
for (i=2; iL.length; ++i)
if (L.elem[i]L.elem[i-1]) // 时,需将L.elem[i]插入有序子表
{ count++;
L.elem[0] = L.elem[i]; // 复制为哨兵
for (j=i-1; L.elem[0]L.elem[j]; --j)
L.elem[j+1] = L.elem[j]; // 记录后移
L.elem[j+1] = L.elem[0];// 插入到正确位置
printf(第%d轮排序顺序如下:\n,count);
for (int k=1; kL.length; ++k)
printf(%6d,L.elem[k]);
printf(\n);
}
} // InsertSort
void main()
{ SqList T;
int n=0,flag=0;
char yes_no;
do
{ do
{ printf(请输入顺序表的长度(大于0)(第一个存储单元不存数据):\n);
scanf(%d,n);
}while(n=0);
T=create(n);
InsertSort(T);
printf(数据排序后如下:\n);
for(int i=1;iT.length;i++)
{printf(%5d,T.elem[i]);}
printf(\n);
do
{ printf(如果想继续验证请输入Y或y,否则输入N或n:\n\n);
scanf(%s,yes_no);
}while(yes_no!=Yyes_no!=yyes_no!=Nyes_no!=n);
}while(yes_no==Y||yes_no==y);
}
运行结果:
请输入顺序表的长度(大于0)(第一个存储单元不存数据):
8
请输入第1个整数:
12
请输入第2个整数:
23
请输入第3个整数:
34
请输入第4个整数:
45
请输入第5个整数:
45
请输入第6个整数:
56
请输入第7个整数:
67
数据排序后如下:
12 23 34 45 45 56 67
如果想继续验证请输入Y或y,否则输入N或n:
二、冒泡排序
#include stdio.h
# include stdlib.h
# define OVERFLOW -2
typedef struct
{ int * elem;
int length;
}SqList;
SqList create(int n)//建立一个顺序表
{ SqList L;
L.elem = (int *)malloc( n*siz
显示全部