佛山科学技术学院
实验报告
课程名称数据结构
实验项目实现典型的排序算法
专业班级 09计算机（1）班姓名梁志恒学号________2009314138________
指导教师黄营成绩____________ 日期________ _______
题目：请编程实现堆排序算法。

#include<stdio.h>
#define maxsize 100
typedef struct
{
int key[maxsize];
int length;
}SqList;
//堆排序大根堆
void HeapAdjust(SqList *L,int s,int m)
{
int j;
L->key[0]=L->key[s];
for(j=2*s;j<=m;j=2*j)
{
if(j<m && L->key[j]>L->key[j+1])
j++;
if(!(L->key[0]>L->key[j]))
break;
L->key[s]=L->key[j];
s=j;
}
L->key[s]=L->key[0];
}
void HeapSort(SqList *L)
{
//对顺序表key进行堆排序
int i;
for(i=L->length/2;i>0;i--)
HeapAdjust(L,i,L->length);
for(i=L->length;i>1;i--)
{
L->key[0]=L->key[1];
L->key[1]=L->key[i];
L->key[i]=L->key[0];
HeapAdjust(L,1,i-1);
}
}
void main()
{
SqList L;
int i,s=1;
printf("元素的个数length=");
scanf("%d",&(L.length));
for(i=1;i<=L.length;i++)
{
scanf("%d",&(L.key[i]));
}
HeapSort(&L,s,L.length);
printf("排序后：\n");
for(i=1;i<=L.length;i++)
printf("%d ",L.key[i]);
printf("\n");
}
1．请为所建立的堆选择适合的数据结构。

链式存储结构
typedef struct BiTNode
{
int data;
struct BiTNode *lchild,* rchild;
}BiTNode , *BiTree;
顺序存储结构
#define maxsize 100
typedef struct
{
int key[maxsize];
int length;
}SqList;
2．给出如下12个数字，请画出建立小根堆的过程。

36，47，58，12，17，22，97，10，21，28，72，80
36，47，58，12，17，22，97，10，21，28，72，80
3．请画出从小根堆输出升序序列的过程。

输出 10
58
7297 80
58
7297
80
58
7297
80
58
7297
80
输出10 12 17 21 22 28 36 47 58
80
7297
80
7297
72
8097
72
8097输出10 12 17 21 22 28 36 47 58 72
97 80
80
97
80
97
输出10 12 17 21 22 28 36 47 58 72 80
97
输出10 12 17 21 22 28 36 47 58 72 80 97。