1.cpp

建堆及堆排序

#define MAXSIZE 20
#include"stdio.h"

typedef struct{
	int r[MAXSIZE+1];
	int     length;
}SqList;

typedef SqList HeapType;

void HeapAdjust(HeapType &H,int s,int m){
	int rc=H.r[s];
	for (int j=2*s;j<=m;j*=2){
		if ((j<m) && (H.r[j]>H.r[j+1])) ++j;
		if (!(rc>H.r[j])) break;
		H.r[s]=H.r[j];  s=j;
	}
	H.r[s]=rc;
}

void HeapSort(HeapType &H){
	int temp;
	for (int i=H.length/2; i>0; --i)
		HeapAdjust(H,i,H.length);
	for (i=H.length; i>0; --i){
		//printf("%d ",H.r[1] );
		temp=H.r[1] ;
		H.r[1] =H.r[i] ;
		H.r[i] =temp;
		HeapAdjust(H,1,i-1);
	}
}

void HeapSort(HeapType &H,int){
	int temp;
	for (int i=H.length/2; i>0; --i)
		HeapAdjust(H,i,H.length);
	printf("初始堆：\n");
	for( i=1;i<=H.length ;i++)
	    printf("%d ",H.r[i] );
	for (i=H.length; i>0; --i){
		printf("\n\n执行第%d次：\n",H.length-i+1);
		printf("输出的堆顶元素和堆为：\n%d \n",H.r[1] );
		temp=H.r[1] ;
		H.r[1] =H.r[i] ;
		H.r[i] =temp;
		HeapAdjust(H,1,i-1);
	
		for( int j=1;j<=i-1 ;j++)
		{
	     printf("%d ",H.r[j] );
		}
	}
}
main()
{
	HeapType H;
	char ch='y';
	while( ch=='y'||ch=='Y'){

	  printf("请输入数据规模：\n");
	  scanf("%d",&H.length);
	  printf("请输入%d个数据：\n",H.length );
	  for(int i=1;i<=H.length;i++)
		scanf("%d",&H.r[i]);
	
	  printf("是否要显示堆顶元素和堆[y/n]\n");
	  getchar();
	  char c=getchar();
	  getchar();
	  if(c=='y'||c=='Y')
		  HeapSort(H,1);
	  else
	      HeapSort(H);
      printf("\n排序的结果为:\n");
	  for( i=H.length ;i>=1;i--)
	      printf("%d ",H.r[i] );
	  printf("\n\n是否重来[y/n]\n");
	  
	  ch=getchar();
	}

}