数据结构实验报告排序.docx
《数据结构实验报告排序.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告排序.docx（18页珍藏版）》请在冰点文库上搜索。
数据结构实验报告排序
本章共8道实验题目。
一、直接插入排序
1.定义顺序表的存储结构
2.初始化顺序表为空表
3.输入10个元素创建含有10个元素的顺序表
4.输出顺序表
5.对顺序表进行直接插入排序（InsertSort）
6.输出排序后的顺序表
例如：
11938669507117261708343300602
11938669507117261708343300602
11117261300343507602669708938
程序:
#include
#include
usingnamespacestd;
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintStatus;
#defineMAXSIZE100
typedefintKeyType;
typedefcharInfoType[256];
typedefstruct
{
KeyTypekey;
InfoTypeotherinfo;
}RedType;
typedefstruct
{
RedTyper[MAXSIZE+1];
intlength;
}SqList;
//此处定义直接插入排序函数
inta[20];
intmain（）
{
intInsertSort;
for（inti=0;i<10;++i）
{
cin>>a[i];
cout<}
cout<sort（a,a+10）;
for（inti=0;i<10;++i）
cout<return0;
}
二、折半插入排序
1.定义顺序表的存储结构
2.初始化顺序表为空表
3.输入10个元素创建含有10个元素的顺序表
4.输出顺序表
5.对顺序表进行折半插入排序（BInsertSort）
6.输出排序后的顺序表
例如：
11938669507117261708343300602
11938669507117261708343300602
11117261300343507602669708938
程序：
#include
#include
usingnamespacestd;
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintStatus;
#defineMAXSIZE100
typedefintKeyType;
typedefcharInfoType[256];
typedefstruct
{
KeyTypekey;
InfoTypeotherinfo;
}RedType;
typedefstruct
{
RedTyper[MAXSIZE+1];
intlength;
}SqList;
//此处定义折半插入排序函数
inta[20];
intmain（）
{
intBInsertSort;
for（inti=0;i<10;++i）
{
cin>>a[i];
cout<}
cout<sort（a,a+10）;
for（inti=0;i<10;++i）
cout<return0;
}
三、希尔排序
1.定义顺序表的存储结构
2.初始化顺序表为空表
3.输入10个元素创建含有10个元素的顺序表
4.输出顺序表
5.对顺序表进行希尔排序（ShellSort）
6.输出排序后的顺序表
例如：
11938669507117261708343300602
11938669507117261708343300602
11117261300343507602669708938
程序：
#include
#include
usingnamespacestd;
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintStatus;
#defineMAXSIZE100
typedefintKeyType;
typedefcharInfoType[256];
typedefstruct
{
KeyTypekey;
InfoTypeotherinfo;
}RedType;
typedefstruct
{
RedTyper[MAXSIZE+1];
intlength;
}SqList;
inta[20];
intmain（）
{
intShellSort;
for（inti=0;i<10;++i）
{
cin>>a[i];
cout<}
cout<sort（a,a+10）;
for（inti=0;i<10;++i）
cout<return0;
}
四、冒泡排序
1.定义顺序表的存储结构
2.初始化顺序表为空表
3.输入10个元素创建含有10个元素的顺序表
4.输出顺序表
5.对顺序表进行冒泡排序（BubbleSort）
6.输出排序后的顺序表
例如：
11938669507117261708343300602
11938669507117261708343300602
11117261300343507602669708938
程序：
#include
#include
usingnamespacestd;
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintStatus;
#defineMAXSIZE100
typedefintKeyType;
typedefcharInfoType[256];
typedefstruct
{
KeyTypekey;
InfoTypeotherinfo;
}RedType;
typedefstruct
{
RedTyper[MAXSIZE+1];
intlength;
}SqList;
inta[20];
intmain（）
{
intBubbleSort;
for（inti=0;i<10;++i）
{
cin>>a[i];
cout<}
cout<sort（a,a+10）;
for（inti=0;i<10;++i）
cout<return0;
}
五、快速排序
1.定义顺序表的存储结构
2.初始化顺序表为空表
3.输入10个元素创建含有10个元素的顺序表
4.输出顺序表
5.对顺序表进行快速排序（QuickSort）
6.输出排序后的顺序表
例如：
11938669507117261708343300602
11938669507117261708343300602
11117261300343507602669708938
程序：
#include
#include
usingnamespacestd;
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintStatus;
#defineMAXSIZE100
typedefintKeyType;
typedefcharInfoType[256];
typedefstruct
{
KeyTypekey;
InfoTypeotherinfo;
}RedType;
typedefstruct
{
RedTyper[MAXSIZE+1];
intlength;
}SqList;
inta[20];
intmain（）
{
intQuickSort;
for（inti=0;i<10;++i）
{
cin>>a[i];
cout<}
cout<sort（a,a+10）;
for（inti=0;i<10;++i）
cout<return0;
}
六、简单选择排序
1.定义顺序表的存储结构
2.初始化顺序表为空表
3.输入10个元素创建含有10个元素的顺序表
4.输出顺序表
5.对顺序表进行简单选择排序（SelectSort）
6.输出排序后的顺序表
例如：
11938669507117261708343300602
11938669507117261708343300602
11117261300343507602669708938
程序：
#include
#include
usingnamespacestd;
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintStatus;
#defineMAXSIZE100
typedefintKeyType;
typedefcharInfoType[256];
typedefstruct
{
KeyTypekey;
InfoTypeotherinfo;
}RedType;
typedefstruct
{
RedTyper[MAXSIZE+1];
intlength;
}SqList;
inta[20];
intmain（）
{
intSelectSort;
for（inti=0;i<10;++i）
{
cin>>a[i];
cout<}
cout<sort（a,a+10）;
for（inti=0;i<10;++i）
cout<return0;
}
七、堆排序
1.定义顺序表的存储结构
2.初始化顺序表为空表
3.输入10个元素创建含有10个元素的顺序表
4.输出顺序表
5.对顺序表进行堆排序（HeapSort）
6.输出排序后的顺序表
例如：
11938669507117261708343300602
11938669507117261708343300602
11117261300343507602669708938
程序：
#include
usingnamespacestd;
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintStatus;
#defineMAXSIZE100
typedefintKeyType;
typedefcharInfoType[256];
typedefstruct
{
KeyTypekey;
InfoTypeotherinfo;
}RedType;
typedefstruct
{
RedTyper[MAXSIZE+1];
intlength;
}SqList;
StatusInitList（SqList&L）
{
L.length=0;
return0;
}
StatusCreateList（SqList&L,intn）
{
if（!
L.r||n<1||n>MAXSIZE）returnERROR;
//cout<<"\n请输入"<";
for（inti=1;i<=n;i++）
cin>>L.r[i].key;
L.length=n;
returnOK;
}
voidListTraverse（SqListL）
{
//cout<<"L=（";
for（inti=1;i<=L.length;i++）
cout<//if（L.length）cout<<'\b';
//cout<<"）";
cout<}
voidHeapSort（SqList&L）{
intvalue=0;
for（inti=0;ifor（intj=0;j{
if（L.r[j].key>L.r[j+1].key）
{
value=L.r[j].key;
L.r[j].key=L.r[j+1].key;
L.r[j+1].key=value;
}
}
}
intmain（）
{
SqListL;
InitList（L）;
CreateList（L,10）;
ListTraverse（L）;
HeapSort（L）;
ListTraverse（L）;
return0;
}
八、归并排序
1.定义顺序表的存储结构
2.初始化顺序表为空表
3.输入10个元素创建含有10个元素的顺序表
4.输出顺序表
5.对顺序表进行二路归并排序（MergeSort）
6.输出排序后的顺序表
例如：
11938669507117261708343300602
11938669507117261708343300602
11117261300343507602669708938
程序：
#include
usingnamespacestd;
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintStatus;
#defineMAXSIZE100
typedefintKeyType;
typedefcharInfoType[256];
typedefstruct
{
KeyTypekey;
InfoTypeotherinfo;
}RedType;
typedefstruct
{
RedTyper[MAXSIZE+1];
intlength;
}SqList;
StatusInitList（SqList&L）
{
L.length=0;
return0;
}
StatusCreateList（SqList&L,intn）
{
if（!
L.r||n<1||n>MAXSIZE）returnERROR;
//cout<<"\n请输入"<";
for（inti=1;i<=n;i++）
cin>>L.r[i].key;
L.length=n;
returnOK;
}
voidListTraverse（SqListL）
{
//cout<<"L=（";
for（inti=1;i<=L.length;i++）
cout<//if（L.length）cout<<'\b';
//cout<<"）";
cout<}
voidMSort（）{}
voidMerge（）{}
voidMergeSort（SqList&L）{
intvalue=0;
for（inti=0;ifor（intj=0;j{
if（L.r[j].key>L.r[j+1].key）
{
value=L.r[j].key;
L.r[j].key=L.r[j+1].key;
L.r[j+1].key=value;
}
}
}
intmain（）
{
SqListL;
InitList（L）;
CreateList（L,10）;
ListTraverse（L）;
MergeSort（L）;
ListTraverse（L）;
return0;
}
升级会员 