77.cpp

来自「数据结构168个实验程序,很全面」· C++ 代码 · 共 67 行

// 77.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"

typedef struct{
	int key;
}Redtype;

typedef struct{
	Redtype r[50];
	int length;
}Heap;

void Heap_Adjust(Heap &H,int s,int m)//顺序表H中,H.r[s+1]到H.r[m]已经是堆,把H.r[s]插入并调整成堆
{
  Redtype  rc;
  int j;
  rc=H.r[s];
  for(j=3*s-1;j<=m;j=3*j-1)
  {
    if(j<m && H.r[j].key<H.r[j+1].key) ++j;
	if(!(H.r[j].key<H.r[j+1].key))break;
    H.r[s]=H.r[j];
    s=j;
  }
  H.r[s]=rc;
}//Heap_Adjust


void TriHeap_Sort(Heap &H)//利用三叉树形式的堆进行排序的算法
{
	int i;
	Redtype m;
	for(i=H.length/3;i>0;i--)
    Heap_Adjust(H,i,H.length);
	for(i=H.length;i>1;i--)
	{
		m=H.r[1];
		H.r[1]=H.r[i];
		H.r[i]=m;
		Heap_Adjust(H,1,i-1);
	}
}//TriHeap_Sort 
int main(int argc, char* argv[])
{
	int n,i;
	Heap H;
	printf("请输入数据个数: ");
	scanf("%d",&n);
	H.length=n;
	for(i=0;i<n;i++)
	{
		printf("请输入第%d个数据 ",i+1);
		scanf("%d",&H.r[i].key);
	}
	TriHeap_Sort(H);
	printf("排序后为   ");
	for(i=0;i<n;i++)
	{
		printf("%d",H.r[i].key);
	}
	printf("\n\n");

	return 0;
}