#include
#include
//创建最小堆
typedef struct HeapStruct *MinHeap;
struct HeapStruct
{
struct TreeNode *a;//存储堆元素的数组
int size;//堆的当前元素的个数
int capacity;//堆的最大容量
} ;
//========================================
typedef struct TreeNode *HuffmanTree;
struct TreeNode
{
int Weight;
HuffmanTree Left,Right;
};
//======================================
MinHeap Creat(int MinSize)//创建一个堆的过程
{
//创建容量为Maxsize的空的最大堆
MinHeap H= (MinHeap)malloc(sizeof(struct HeapStruct));
H->a =(HuffmanTree)malloc((MinSize+1)*sizeof(struct TreeNode));
H->size =0;
H->capacity =MinSize;
H->a[0].Weight =1000; //赋一个最大值当作哨兵，不论怎么调整堆节点
//这个哨兵总是比他大
return H;
}
void Insert(MinHeap H,int item)
{
//将元素item插入到最大堆H，其中H->Elements[0]已经定义为哨兵
int i;
if(H->size ==H->capacity )
{
printf("最小堆已经满了");
return ;
}
i=++H->size ;//i指向插入后堆中的第一个元素的位置
for(;H->a[i/2].Weight >item;i/2)
{
H->a[i].Weight =H->a[i/2].Weight ;
}
H->a[i].Weight =item;
}
HuffmanTree DeleteMin(MinHeap H)//删除堆定元素
{
int parent,child;
int temp;HuffmanTree MinItem;
if(H->size ==0)//判断堆是否为空
{
printf("最小堆已经为空");
HuffmanTree error;
return error;
}
MinItem=&(H->a[1]);//最大元素为堆顶元素
temp=H->a[H->size--].Weight;
for(parent=1;parent*2>=H->size ;parent=child)
{
child=parent*2;
if((child!=H->size )&&(H->a[child].Weight >H->a[child+1].Weight ))
child++;//右孩子比左孩子大，child指向右孩子
if(temp>=H->a[child].Weight )
break;
else
H->a[parent].Weight =H->a[child].Weight ;
}
H->a[parent].Weight =temp;
return MinItem;
}
void BuildMinHeap(MinHeap H)
{
printf("请输入5个元素\n");
int num[5];
for(int i=0;i<5;i++)
{
printf("请输入第%d个元素\n",i+1);
scanf("%d",&num[i]);
Insert(H,num[i]);
}
}
//==================================
HuffmanTree Huffman(MinHeap H)
{
int i; HuffmanTree T;
BuildMinHeap(H);
for(i=1;isize ;i++)
{
T=(HuffmanTree)malloc(sizeof(struct TreeNode));
T->Left =DeleteMin(H);
T->Right =DeleteMin(H);
}
}
//===================================
int main()
{
MinHeap H;
BuildMinHeap(H);
return 0;
}
