习题5-堆排序.c

数据结构各章实验源代码； 数据结构实验源代码

#include  "datastru.h"
#include  <stdio.h>

void sift(RECNODE *r, int i, int m)
{/*i是根结点编号,m是以i结点为根的子树中最后一个结点的编号*/
	int j;
	RECNODE temp;

	temp = r[i];
	j = 2 * i;       /*j为i根结点的左孩子*/
	while(j <= m)
	  {if(j < m && (r[j].key < r[j + 1].key))
	    j++;                                  /*当i结点有左右孩子时,j取关键字大的孩子结点编号*/
	   if(temp.key < r[j].key)
	     { r[i] = r[j];   i = j;   j = 2 * i;}/*按堆定义调整,并向下一层筛选调整*/
	   else   break;                          /*筛选调整完成,跳出循环*/ 
	  }
	r[i] = temp;
}

void heapsort(RECNODE *r, int n)
{/*堆排序: n为r表中记录数,从r[1]开始放起*/
	int i;
	RECNODE temp;

	for(i = n/2; i >= 1; i--)
	  sift(r, i, n);             /*将无序序列建成大堆*/
	for(i = n; i >= 2; i--)
	  {temp = r[1];              /*堆顶及堆尾元素交换*/
	   r[1] = r[i];
	   r[i] = temp;
	   sift(r,1,i - 1);          /*交换后,从第一个元素开始调整为大堆,每次记录个数少一个*/
	  }         
}

main( )
{ RECNODE  a[MAXSIZE];
  int  i, j, k, len;

 printf("\n\n输入待排序数据(整数，以空格隔开，0 结束) : "); k = 0; scanf("%d",&j);
 while(j != 0) { k++; a[k].key = j; scanf("%d",&j); }
 len = k;
 printf("\n排序前 : ");
 for (i = 0; i < len; i++)   printf("  %d",a[i+1].key);
 printf("\n");
 heapsort (a,len);
 printf("\n\n排序后 : ");
 for (i = 0; i < len; i++)   printf("  %d",a[i+1].key);
 printf("\n\n");
}