第八次数据结构上机实验报告.docx
《第八次数据结构上机实验报告.docx》由会员分享，可在线阅读，更多相关《第八次数据结构上机实验报告.docx（9页珍藏版）》请在冰点文库上搜索。
第八次数据结构上机实验报告
一、调试成功程序及说明
1、
题目：
2．实现快速排序算法
算法思想：
1.设置两个变量i、j，排序开始的时候：
i=0，j=N-1；
2.以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3.从j开始向前搜索，即由后开始向前搜索（j--），找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4.从i开始向后搜索，即由前开始向后搜索（i++），找到第一个大于key的A[i]，将A[i]和A[j]互换；
5.重复第3、4步，直到i=j；（3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。
找到符合条件的值，进行交换的时候i，j指针位置不变。
另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
源程序：
#include
#include
voidswap（int*x,int*y）
{
inttemp;
temp=*x;
*x=*y;
*y=temp;
}
intchoose_pivot（inti,intj）
{
return（（i+j）/2）;
}
voidquicksort（intlist[],intm,intn）
{
intkey,i,j,k;
if（m{
k=choose_pivot（m,n）;
swap（&list[m],&list[k]）;
key=list[m];
i=m+1;
j=n;
while（i<=j）
{
while（（i<=n）&&（list[i]<=key））
i++;
while（（j>=m）&&（list[j]>key））
j--;
if（iswap（&list[i],&list[j]）;
}
//交换两个元素的位置
swap（&list[m],&list[j]）;
//递归地对较小的数据序列进行排序
quicksort（list,m,j-1）;
quicksort（list,j+1,n）;
}
}
voidprintlist（intlist[],intn）
{
inti;
for（i=0;iprintf（"%d\t",list[i]）;
}
voidmain（）
{
constintMAX_ELEMENTS=10;
intlist[MAX_ELEMENTS];
inti=0;
printf（"请输入十位排序的数字，按enter终止输入：
"）;
for（i=0;i{
scanf（"%d",&list[i]）;
}
printf（"排序前的序列:
\n"）;
printlist（list,MAX_ELEMENTS）;
//sortthelistusingquicksort
quicksort（list,0,MAX_ELEMENTS-1）;
//printtheresult
printf（"使用快速排序算法进行排序之后的序列:
\n"）;
printlist（list,MAX_ELEMENTS）;
}
运行结果：
2、
题目：
3．实现堆排序算法；
算法思想：
1.先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
2.再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
3.由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。
然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
源程序：
#include
#defineSUCCESS0
#defineERROR-1
/**
*调整堆
*index是数组下标，从0开始
*/
intHeapSort_adjust（int*piBuffer,constunsignedintuiSize,constunsignedintuiIndex）
{
int*piTmp=piBuffer;
unsignedinti=uiIndex;
unsignedintuiChild=i;
intiTmpValue=0;
if（（NULL==piTmp）||（uiSize<2）||（uiIndex>=uiSize））/**入参判断*/
{
returnERROR;
}
for（i=uiIndex;i{
uiChild=2*i+1;
/**找到子结点中较大的*/
if（（uiChildpiBuffer[uiChild]））
{
uiChild++;
}
/**判断较大的子结点是否比父结点大*/
if（（uiChild<=uiSize-1）&&（piBuffer[uiChild]>piBuffer[i]））
{
iTmpValue=piBuffer[i];
piBuffer[i]=piBuffer[uiChild];
piBuffer[uiChild]=iTmpValue;
}
else/**如果左右子结点都比父结点小，那么可以肯定这是一个大根堆了，可以结束循环了*/
{
break;
}
}
returnSUCCESS;
}
/**
*堆排序，这里使用大根堆，按照从小到大排序
*uiSize是数组大小，从1开始
*/
intHeapSort（int*piBuffer,constunsignedintuiSize）
{
int*piTmp=piBuffer;
inti=（uiSize-2）/2;
intiTmpValue=0;
if（（NULL==piTmp）||（uiSize<2））/**入参判断*/
{
returnERROR;
}
/**首先进行堆的初始化，调整成一个大根堆*/
for（i=（uiSize-2）/2;i>=0;i--）/**数组下标从0开始，所以i的初始值为（uiSize-2）/2*/
{
HeapSort_adjust（piBuffer,uiSize,i）;
}
/**把第0个元素与最后一个元素对调，重新调整堆*/
for（i=uiSize-1;i>0;i--）
{
iTmpValue=piBuffer[i];
piBuffer[i]=piBuffer[0];
piBuffer[0]=iTmpValue;
HeapSort_adjust（piBuffer,i,0）;/**每次只需要调整前i个元素即可*/
}
returnSUCCESS;
}
/**
*打印数组内容
*/
intHeapSort_print（int*piBuffer,constunsignedintuiSize）
{
int*piTmp=piBuffer;
inti=0;
if（NULL==piTmp）/**入参判断*/
{
returnERROR;
}
/**打印数组内容，中间以逗号隔开*/
for（i=0;i{
if（0==i）
{
printf（"%d",piTmp[i]）;
}
else
{
printf（"%d",piTmp[i]）;
}
}
printf（"\n"）;
returnSUCCESS;
}
intmain（intargc,char*argv[]）
{
inti,array[10];
printf（"输入用于堆排序的十个数:
\n"）;
for（i=0;i<10;i++）
{
scanf（"%d",&array[i]）;
}
printf（"排序后为:
\n"）;
HeapSort（array,sizeof（array）/sizeof（array[0]））;/**堆排序*/
HeapSort_print（array,sizeof（array）/sizeof（array[0]））;/**第二个参数是数组中元素个数，所以不能简单的用sizeof*/
returnSUCCESS;
}
运行结果：
升级会员 