数据结构排序.docx
《数据结构排序.docx》由会员分享，可在线阅读，更多相关《数据结构排序.docx（21页珍藏版）》请在冰点文库上搜索。
数据结构排序
江南大学物联网工程学院上机报告
课程名称数据结构上机名称排序上机日期2013-５-２２
班级计科1203姓名汪俊学号1030412314
上机报告要求1．上机名称2．上机要求3．上机环境4．程序清单（写明运行结果）5．上机体会
1.上机名称
排序，实验5
2.上机要求
调试实验一，补充实验2主函数，完成实验3
3.上机环境
VisualC++6.0
4.程序清单（写明运行结果）
一、
#include
#defineN10
#defineFALSE0
#defineTRUE1
typedefintKeyType;
typedefcharInfoType;
typedefstruct
{
KeyTypekey;
InfoTypeotherinfo;
}RecType;
typedefRecTypeSeqlist[N+1];
intm,num;//全局变量m存储输出的是第几趟结果，num存储递归调用的次数
SeqlistR;
voidInsertsort（）;
voidBubblesort（）;
voidSelectsort（）;
voidmain（）
{
SeqlistS;
inti;
charch1,ch2;
printf（"请输入10个待排序的数据：
（每两个数据间用空格隔开）\n"）;
for（i=1;i<=N;i++）
scanf（"%d",&S[i].key）;
ch1='y';
while（ch1=='y'||ch1=='Y'）
{
printf（"**********菜单**********\n"）;
printf（"请选择下列操作:
\n"）;
printf（"1-------更新待排序数据--------\n"）;
printf（"2-------直接插入排序----------\n"）;
printf（"3-------冒泡排序--------------\n"）;
printf（"4-------直接选择排序----------\n"）;
printf（"5-------退出------------------\n"）;
printf（"请选择操作类别:
\n"）;
scanf（"\n%c",&ch2）;
switch（ch2）
{
case'1':
printf（"请输入更新待排序数据:
\n"）;
for（i=1;i<=N;i++）
scanf（"%d",&S[i].key）;
break;
case'2':
printf（"请输入要输出第几趟排序结果:
\n"）;
scanf（"%d",&m）;
for（i=1;i<=N;i++）
R[i].key=S[i].key;
Insertsort（）;
break;
case'3':
printf（"请输入要输出第几趟排序结果:
\n"）;
scanf（"%d",&m）;
for（i=1;i<=N;i++）
R[i].key=S[i].key;
Bubblesort（）;
break;
case'4':
printf（"请输入要输出第几趟排序结果:
\n"）;
scanf（"%d",&m）;
for（i=1;i<=N;i++）
R[i].key=S[i].key;
Selectsort（）;
break;
case'5':
ch1='n';
break;
default:
ch1='n';
}
}
}
voidInsertsort（）
{
inti,j,k;
for（i=2;i<=N;i++）
{
if（R[i].key{
R[0]=R[i];
j=i-1;
while（R[0].key{/*从右向左在有序区R[1....i-1]中查找R[i]的插入位置*/
R[j+1]=R[j];
j--;
}
R[j+1]=R[0];
}
if（i-1==m）
{
printf（"第%d趟的结果是:
\n",m）;
for（k=1;k<=N;k++）
printf（"%5d",R[k].key）;
printf（"\n"）;
printf（"请输入还想输出第几趟结果,不想输出时请输入0:
\n"）;
scanf（"%d",&m）;
}
}
if（m!
=0）
{
printf（"最终排序结果是:
\n"）;
for（k=1;k<=N;k++）
printf（"%5d",R[k].key）;
printf（"\n"）;
}
}
voidBubblesort（）
{
//自下向上
inti,j,k;
intexchange;
for（i=1;i<=N;i++）
{//最多做N-1趟排序
exchange=FALSE;
for（j=N-1;j>=i;j--）
{
if（R[j+1].key{
R[0]=R[j+1];
R[j+1]=R[j];
R[j]=R[0];
exchange=TRUE;
}
}
if（i==m）
{
printf（"第%d趟的结果是:
\n",m）;
for（k=1;k<=N;k++）
printf（"%5d",R[k].key）;
printf（"\n"）;
printf（"请输入还想输出第几趟结果,不想输出时请输入0:
\n"）;
scanf（"%d",&m）;
}
if（（!
exchange）||（m==0））
break;
}
if（m!
=0）
{
printf（"最终排序结果是:
\n"）;
for（k=1;k<=N;k++）
printf（"%5d",R[k].key）;
printf（"\n"）;
}
}
voidSelectsort（）
{
inti,j,k,h;
for（i=1;i{
h=i;
for（j=i+1;j<=N;j++）
{
if（R[j].keyh=j;
}
if（h!
=i）
{
R[0]=R[i];
R[i]=R[h];
R[h]=R[0];
}
if（i==m）
{
printf（"第%d趟的结果是:
\n",m）;
for（k=1;k<=N;k++）
printf（"%5d",R[k].key）;
printf（"\n"）;
printf（"请输入还想输出第几趟结果,不想输出时请输入0:
\n"）;
scanf（"%d",&m）;
}
}
if（m!
=0）
{
printf（"最终排序结果是:
\n"）;
for（k=1;k<=N;k++）
printf（"%5d",R[k].key）;
printf（"\n"）;
}
}
二、
#include
#defineN4
#definefalse0
#defineture1
typedefintkeytype;
typedefcharinfotype;
typedefstruct
{
keytypekey;
infotypeotherinfo;
}rectype;
typedefrectypeseqlist[N+1];
intm,num;
seqlistR;
voidquicksort（seqlist&R,ints,intt）
{
inti=s,j=t;
if（i{
R[0]=R[i];
do
{
while（i=R[0].key）
j--;
if（i{
R[i]=R[j];
i++;
}
while（ii++;
if（i{
R[j]=R[i];
j--;
}
}while（iR[i]=R[0];
quicksort（R,s,j-1）;
quicksort（R,j+1,t）;
}
}
voidshellsort（seqlist&R,intn）
{
inti,j,gap;
gap=n/2;
while（gap>0）
{
for（i=gap;i<=n;i++）
{
R[0]=R[i];
j=i-gap;
while（j>=1&&R[0].key{
R[j+gap]=R[j];
j=j-gap;
}
R[j+gap]=R[0];
j=j-gap;
}
gap=gap/2;
}
}
voidsift（seqlist&R,intv,intn）
{
inti,j;
i=v;
j=2*i;
R[0]=R[i];
while（j<=n）
{
if（jj++;
if（R[0].key{
R[i]=R[j];
i=j;
j=2*i;
}
else
j=n+1;
}
R[i]=R[0];
}
voidheapsort（seqlist&R,intn）
{
inti;
for（i=n/2;i>=1;i--）
sift（R,i,n）;
for（i=n;i>=2;i--）
{
R[0]=R[i];
R[i]=R[1];
R[1]=R[0];
sift（R,1,i-1）;
}
}
voidshow（seqlist&R,intn）
{
inti;
for（i=1;i<=n;i++）
printf（"%d",R[i].key）;
}
voidmain（）
{
seqlistS;
inti;
charch1,ch2;
printf（"请输入4个待排元素：
（每两个数据间用空格隔开）\n"）;
for（i=1;i<=N;i++）
scanf（"%d",&S[i].key）;
ch1='y';
while（ch1=='y'||ch1=='Y'）
{
printf（"***************菜单****************\n"）;
printf（"请选择下列操作：
\n"）;
printf（"1----------------更新待排数据----------------------\n"）;
printf（"2----------------快速排序----------------------\n"）;
printf（"3-----------------希尔排序---------------------\n"）;
printf（"4-----------------堆排序----------------\n"）;
printf（"5--------------------退出----------------------------\n"）;
printf（"请选择操作类型：
\n"）;
scanf（"\n%c",&ch2）;
switch（ch2）
{
case'1':
printf（"请输出更新待排数据：
\n"）;
for（i=1;i<=N;i++）
scanf（"%d",&S[i].key）;
break;
case'2':
quicksort（S,1,4）;
show（S,4）;
break;
case'3':
shellsort（S,4）;
show（S,4）;
break;
case'4':
heapsort（S,4）;
show（S,4）;
break;
case'5':
ch1='n';
break;
default:
ch1='n';
}
}
}
三、#include
#include
#include
usingnamespacestd;
#defineN6
#definefalse0
#defineture1
typedefintkeytype;
typedefstringinfotype;
typedefstruct
{
keytypepaim;
keytypekey;
infotypeotherinfo;
}rectype;
typedefrectypeseqlist[N+1];
intm,num;
seqlistR;
voidquicksort（seqlist&R,ints,intt）
{
inti=s,j=t;
if（i{
R[0]=R[i];
do
{
while（i=R[0].key）
j--;
if（i{
R[i]=R[j];
i++;
}
while（ii++;
if（i{
R[j]=R[i];
j--;
}
}while（iR[i]=R[0];
quicksort（R,s,j-1）;
quicksort（R,j+1,t）;
}
}
voidshellsort（seqlist&R,intn）
{
inti,j,gap;
gap=n/2;
while（gap>0）
{
for（i=gap;i<=n;i++）
{
R[0]=R[i];
j=i-gap;
while（j>=1&&R[0].key{
R[j+gap]=R[j];
j=j-gap;
}
R[j+gap]=R[0];
j=j-gap;
}
gap=gap/2;
}
}
voidsift（seqlist&R,intv,intn）
{
inti,j;
i=v;
j=2*i;
R[0]=R[i];
while（j<=n）
{
if（jj++;
if（R[0].key{
R[i]=R[j];
i=j;
j=2*i;
}
else
j=n+1;
}
R[i]=R[0];
}
voidheapsort（seqlist&R,intn）
{
inti;
for（i=n/2;i>=1;i--）
sift（R,i,n）;
for（i=n;i>=2;i--）
{
R[0]=R[i];
R[i]=R[1];
R[1]=R[0];
sift（R,1,i-1）;
}
}
voidshow（seqlist&R,intn）
{
inti,j,m;
for（i=6;i>=1;i--）
{
R[i].paim=7-i;
if（R[i].key==R[i+1].key）
R[i].paim=R[i+1].paim;
cout<<"姓名为：
"<cout<<"成绩为：
"<cout<<"名次为：
"<}
}
voidmain（）
{
seqlistS;
inti;
charch1,ch2;
printf（"请输入6个成绩：
\n"）;
for（i=1;i<=N;i++）
scanf（"%d",&S[i].key）;
printf（"请输入6个学生姓名：
\n"）;
for（i=1;i<=N;i++）
cin>>S[i].otherinfo;
ch1='y';
while（ch1=='y'||ch1=='Y'）
{
printf（"***************菜单****************\n"）;
printf（"请选择下列操作：
\n"）;
printf（"1----------------更新成绩----------------------\n"）;
printf（"2----------------快速排序----------------------\n"）;
printf（"3-----------------希尔排序---------------------\n"）;
printf（"4-----------------堆排序----------------\n"）;
printf（"5--------------------退出----------------------------\n"）;
printf（"请选择操作类型：
\n"）;
scanf（"\n%c",&ch2）;
switch（ch2）
{
case'1':
printf（"请输出更新的成绩：
\n"）;
for（i=1;i<=N;i++）
scanf（"%d",&S[i].key）;
break;
case'2':
quicksort（S,1,N）;
show（S,N）;
break;
case'3':
shellsort（S,N）;
show（S,N）;
break;
case'4':
heapsort（S,N）;
show（S,N）;
break;
case'5':
ch1='n';
break;
default:
ch1='n';
}
}
}
5.上机体会
纯手打，排序还不是小kiss。
。
。
考试复习的时间都用来编程了，伤不起。
。
。
不过还是学到了不少的东西。
。
。
加油。
。
。
教师评价
优
良
中
及格
不及格
教师签名
日期
升级会员 