数据结构实验排序.docx
《数据结构实验排序.docx》由会员分享，可在线阅读，更多相关《数据结构实验排序.docx（15页珍藏版）》请在冰点文库上搜索。
数据结构实验排序
数据结构实验报告
课程名称数据结构成绩
实验项目排序指导教师
学生姓名学号班级专业
实验地点实验日期2012年12月29日
排序
一、实习目的
熟悉几种典型的排序方法，并对各种算法的特点、使用范围和效率有进一步的
了解。
二、实例
排序是计算机科学中非常基本且使用频繁的运算，在计算机系统软件和应用软件中都有广泛的应用。
下面给出的是冒泡排序、快速排序的实现与比较。
/*源程序的头文件sort.h*/
voidgetrandat（Dataary[],intcount）/*产生一批随机数，准备排序*/
{longinta=100001;
inti;
for（i=0;iary[i].key=（int）a;
}
}/*getrandat*/
voidprdata（Dataary[],intcount）/*输出数据的函数*/
{inti;charch;
printf（“\n”）;
for（i=0;iprintf（“\n”）;
printf（“\n\n打回车键，结束显示。
“）;ch=getch（）;
}/*prdata*/
[两种排序方法的比较源程序]
/*sortcmp.c*/
#include
#include
#defineMAX1000/*数组最大界限*/
typedefintElemType;/*关键字的类型*/
typedefstruct
{ElemTypekey;
intshu;/*其它属性域*/
}Data;/*一个纪录的结构体类型*/
Dataar[MAX],br[MAX];
typedefstruct
{intlo,hi;
}Selem;/*栈的元素结构体类型*/
typedefstruct
{Selemelem[MAX];/*一维数组子域*/
inttop;/*栈顶指针子域*/
}SqStack;/*栈的顺序结构体类型*/
SqStacks1;
/*函数声明*/
voidbubble（Dataary[],intn）;
voidgetrandat（Dataary[],intcount）;/*产生一批随机数，准备排序*/
voidqksort（Dataary[],intn）;
voidhoare（Dataary[],intl,inth）;
voidinit_s（SqStack*s）;
voidpush（SqStack*s,Seleme）;/*进栈一个元素*/
Selempop（SqStack*s）;
voidprdata（Dataary[],intcount）;/*输出数据的函数*/
intempty（SqStacks）;
/*主函数*/
voidmain（）
{intk,n,j;j;charch;
do{printf（"\n\n\n"）;
printf（"\n\n1.产生一批随机数准备排序"）;
printf（"\n\n2.一般情况的起泡排序"）;
printf（"\n\n3.有序情况的起泡排序"）;
printf（"\n\n4.一般情况的快速排序"）;
printf（"\n\n5.有序情况的快速排序"）;
printf（"\n\n6.结束程序运行"）;
printf（"\n======================================"）;
printf（"\n请输入您的选择（1,2,3，4，5，6）"）;
scanf（"%d",&k）;
switch（k）
{case1:
{printf（"thenumberofdatas:
"）;/*输入数据个数*/
scanf（"%d",&n）;
getrandat（ar,n）;/*产生n个随机数*/
for（j=0;jprdata（ar,n）;
}break;
case2:
{for（j=0;jbubble（ar,n）;/*对n个数据起泡排序*/
prdata（ar,n）;/*排序后输出*/
}break;
case3:
{bubble（ar,n）;/*有序情况的起泡排序*/
prdata（ar,n）;
}break;
case4:
{for（j=0;jqksort（ar,n）;/*对n个数据快速排序*/
prdata（ar,n）;/*排序后输出*/
}break;
case5:
{qksort（ar,n）;/*有序情况的快速排序*/
prdata（ar,n）;
}break;
case6:
exit（0）;
}/*switch*/
printf（"\n----------------"）;
}while（k>=1&&k<6）;
printf（"\n再见！
"）;
printf（"\n打回车键，返回。
"）;ch=getchar（）;
}
/*main*/
/*起泡排序*/
voidbubble（Dataary[],intn）
{inti,j,tag;Datax;
i=0;
do{tag=0;
for（j=0;jif（ary[j].key>ary[j+1].key）
{x=ary[j];ary[j]=ary[j+1];
ary[j+1]=x;tag=1;
}
i++;
}while（i}/*bubble*/
/*快速排序非递归算法*/
voidqksort（Dataary[],intn）
{intlow,high,i,tag;
Selemx,y;
init_s（&s1）;/*初始化一个空栈*/
low=0;high=n-1;tag=1;
do{while（low{i=hoare（ary,low,high）;/*调用一趟快速排序*/
x.lo=i+1;x.hi=high;
push（&s1,x）;
high=i-1;
}
if（empty（）==0）tag=0;
else{y=pop（s1）;
low==y.lo;high=y.hi;
}
}while（tag==1）;
}/*qksort*/
/*一趟快速排序*/
inthoare（intary[],intl,inth）
{inti,j;Datax;
i=l;j=h;x=ary[l];
do{
while（（i=x）
j--;
if（i{
ary[i]=ary[j];
i++;}
while（（ii++;
if（i{
ary[j]=ary[i];
j--;}
}while（iary[i]=x;/*枢轴记录定位*/
return（i）;/*返回左、右区分界处*/
}/*hoar*/
/*关于栈的操作*/
voidinit_s（SqStack*s）/*初始化一个空栈*/
{s->top=0;
}/*init_s*/;
/*进栈一个元素*/
voidpush（SqStack*s,Seleme）
{if（s->top==MAX-1）printf（"\nstackOverflow!
\n"）;
else{s->top++;
s->elem[s->top]=e;
}
}/*push*/
/*出栈一个元素*/
Selempop（SqStack*s）init_s（&s1）;
{Seleme;
if（s->top==0）{printf（"\nsatckEmpty!
\n"）;
e.lo=-1;e.hi=-1;
}
else{e=s->elem[s->top];
s->top--;
}
return（e）;
}/*pop*/
voidgetrandat（Dataary[],intcount）/*产生一批随机数，准备排序*/
{longinta=100001;
inti;
for（i=0;iary[i].key=（int）a;
}
}/*getrandat*/
voidprdata（Dataary[],intcount）/*输出数据的函数*/
{inti;charch;
printf（"\n"）;
for（i=0;iprintf（"\n"）;
printf（"\n\n打回车键，结束显示。
"）;ch=getchar（）;
}/*prdata*/
本程序中，qksort用非递归实现快速排序，在这个函数里，调用了hoare函数，函数,hoare对ary[l…h]进行一趟快速排序，执行该函数后，将ary[]从下标i处分成左右两个分区，其中左分区中的数据均小于等于ary[i].key，而右分区中的数据均大于等于ary[i].key（l≤i≤h）。
将右区尾指针（记录下标）保存入栈，对左区再调用hoare进行快速排序。
另外，此处用到的栈与以前的栈结构稍有不同，（因为栈中同时要放进两个值），故操作也稍有不同。
例：
入栈时，要两个参数即右区首、尾指针组成的结构体变量入栈。
快速排序的最坏情况亦即各元素已有序时，再进行快速排序，这种情况下，其实并不快，这种情况下的冒泡排序反而很快。
可见算法的优劣并不是绝对的。
快速排序适合于记录关键字无序的b情况。
排序因其应用广泛，所以人们在排序找方面的研究经久不衰。
三、实习题
1.编写程序实现简单选择排序、堆排序（或归并排序），进行比较分析。
算法设计如下：
1单选择排序法：
#include
#defineMAX50
/*输入数据操作*/
voidInputData（intlist[],intn）
{
printf（"请输入数据:
"）;
for（inti=0;iscanf（"%d",&list[i]）;
}
/*输出数据操作*/
voidOutputData（intlist[],intn）{
printf（"排序后的顺序：
\n"）;
for（intk=0;kprintf（"%5d",list[k]）;
printf（"\n\n"）;
}
/*简单选择排序操作*/
voidSelectSort（intlist[],intn）{
inti,j,k,temp;
for（i=0;ik=i;
for（j=i+1;jif（list[j]k=j;
if（i!
=k）{
temp=list[i];
list[i]=list[k];
list[k]=temp;
}
}
OutputData（list,n）;
}
/*主函数*/
voidmain（）{
intnum;
intlist[MAX];
printf（"请输入系列表的长度：
"）;
scanf（"%d",&num）;
InputData（list,num）;
SelectSort（list,num）;
}
程序运行输出界面如下：
2排序法
#include
/*交换函数*/
voidswap（int*x,int*y）
{intt;
t=*x;*x=*y;*y=t;
}
voidHeapAdjust（int*a,inti,intsize）//调整堆
{intlchild=2*i;//i的左孩子节点序号
intrchild=2*i+1;//i的右孩子节点序号
intmax=i;//临时变量
if（i<=size/2）//如果i不是叶节点就不用进行调整
{if（lchild<=size&&a[lchild]>a[max]）
{max=lchild;}
if（rchild<=size&&a[rchild]>a[max]）
{max=rchild;}
if（max!
=i）
{swap（&a[i],&a[max]）;
HeapAdjust（a,max,size）;//避免调整之后以max为父节点的子树不是堆
}
}
}
voidBuildHeap（int*a,intsize）//建立堆
{inti;
for（i=size/2;i>=1;i--）//非叶节点最大序号值为size/2
{HeapAdjust（a,i,size）;}
}
voidHeapSort（int*a,intsize）//堆排序
{inti;
BuildHeap（a,size）;
for（i=size;i>=1;i--）
{
swap（&a[1],&a[i]）;//交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面
HeapAdjust（a,1,i-1）;//重新调整堆顶节点成为大顶堆
}
for（i=1;i<=size;i++）
printf（"%5d",a[i]）;
}
voidmain（）
{
intsize;inti;inta[100];a[0]=0;
printf（"请输入需排数字个数"）;
scanf（"%d",&size）;
printf（"请输入对应的数字：
"）;
for（i=1;i<=size;i++）
scanf（"%d",&a[i]）;
printf（"堆排序后为"）;
HeapSort（a,size）;
printf（"\n"）;
}
程序输出运行界面如下：
2.编写程序实现简单插入排序、希尔排序（或基数排序），进行比较分析。
算法设计如下：
一：
简单插入排序法
#include
#include
#defineN256
voidINSERTION_SORT（inta[N],intm）
{inti,j,key,k;
for（j=1;j{key=a[j];i=j-1;
while（i>=0&&a[i]>key）
{a[i+1]=a[i];
i=i-1;
}
a[i+1]=key;
}
printf（"\n使用（插入排序法）得到的新序列为:
\n"）;
for（k=0;kprintf（"%5d",a[k]）;
}
voidmain（）
{inti,j,a[N],k;
printf（"\n请输入需要排的个数：
"）;
scanf（"%d",&j）;
printf（"\n请输入对应的数：
"）;
for（i=0;iscanf（"%d",&a[i]）;
INSERTION_SORT（a,j）;//调用插入排序法
printf（"\n"）;
}
程序运行输出界面如下：
四、实验结论
排序时计算机程序设计中的一种重要操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。
根据排序过程中涉及的存储器的不同，排序分为内部排序和外部排序两类。
所谓内部排序，是指待排序列完全存放在内存中进行的排序过程，适合不太大的元素序列。
所谓外部排序，是指排序过程中还需要访问外存的排序过程，适合于待排序列记录数量较大，而不能完全放入内存的元素序列，排序过程中数据在内存和外村之间需要多次移动。
五、实验总结
通过此次实验，我了解了各种排序的基本方法，明白了各种排序方法的基本思想，
并且排序算法的实现方法中包含了丰富的程序设计技巧，比较经典的排序算法有插入排序、交换排序、选择排序、归并排序、堆排序和基数排序，这对于初学者而言提高软件设计能力帮助很大。
升级会员 