#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//Huffman樹的存儲結(jié)構(gòu)
#define n 4					//葉子數(shù)目
#define m 2*n-1					//樹中結(jié)點(diǎn)總數(shù)
typedef struct					//結(jié)點(diǎn)類型
{	float weight;				//權(quán)值，不妨設(shè)權(quán)值均大于零
	int lchild,rchild,parent;	//左右孩子及雙親指針
}HTNode;
typedef HTNode HuffmanTree[m];	//HuffmanTree是向量類型

typedef struct
{	char ch;					//存儲字符
	char bits[n+1];				//存放編碼位串
}CodeNode;
typedef CodeNode HuffmanCode[n];

void InitHuffmanTree(HuffmanTree T);	//初始化Huffman樹
void InputWeight(HuffmanTree T);		//輸入權(quán)值
void SelectMin(HuffmanTree T,int i,int *p1,int *p2);

void main()
{
	
	void CreateHuffmanTree(HuffmanTree T);	//構(gòu)造Huffman樹
	void CharSetHuffmanEncoding(HuffmanTree T,HuffmanCode H);
	HuffmanTree T;
	HuffmanCode H;
	CreateHuffmanTree(T);
	CharSetHuffmanEncoding(T,H);
}

void CreateHuffmanTree(HuffmanTree T)
{ 	//構(gòu)造Huffman樹，T[m-1]為其根結(jié)點(diǎn)
	int i,p1,p2;
	InitHuffmanTree(T);		//將T初始化
	InputWeight(T);			//輸入葉子權(quán)值至T[0..n-1]的weight域
	for(i=n;i<m;i++)		//共進(jìn)行n-1次合并，新結(jié)點(diǎn)依次存于T[i]中
	{	SelectMin(T,i-1,&p1,&p2);
		//在T[0..i-1]中選擇兩個權(quán)最小的根結(jié)點(diǎn)，其序號分別為p1和p2
		T[p1].parent=T[p2].parent=i;
		T[i].lchild=p1;		//最小權(quán)的根結(jié)點(diǎn)是新結(jié)點(diǎn)的左孩子
		T[i].rchild=p2;		//次小權(quán)的根結(jié)點(diǎn)是新結(jié)點(diǎn)的右孩子
		T[i].weight=T[p1].weight+T[p2].weight;
	}
}

void InitHuffmanTree(HuffmanTree T)
{	//初始化Huffman樹
	int i;
	for (i=0;i<m;i++)
	{
		T[i].weight=0;
		T[i].lchild=T[i].rchild=T[i].parent=NULL;
	}
}

void InputWeight(HuffmanTree T)
{	//輸入權(quán)值
	int i;
	for (i=0;i<n;i++)
	{
		printf("請輸入第%d個權(quán)值：",i+1);
		scanf("%f",&T[i].weight);
	}
}

void SelectMin(HuffmanTree T,int i,int *p1,int *p2)
{	//在T中選擇兩個權(quán)最小的根結(jié)點(diǎn)
	int j;
	float min1,min2;
	min1=min2=-1;
	for(j=0;j<=i;j++)
		if(T[j].parent==NULL)
		{
			if(T[j].weight<min1||min1==-1)
			{
				if(min1!=-1)
				{
					min2=min1;
					*p2=*p1;
				}
				min1=T[j].weight;
				*p1=j;
			}
			else
				if(T[j].weight<min2||min2==-1)
				{
					min2=T[j].weight;
					*p2=j;
				}
		}
}

void CharSetHuffmanEncoding(HuffmanTree T,HuffmanCode H)
{	//根據(jù)Huffman樹T求Huffman編碼表H
	int c,p,i;				//c和p分別指示T中孩子和雙親的位置
	char cd[n+1];			//臨時存放編碼
	int start;				//指示編碼在cd中的起始位置
	cd[n]='\0';				//編碼結(jié)束符
	printf("請輸入字符:");
	for(i=0;i<n;i++)
	{H[i].ch=getchar();
	}
	for(i=0;i<n;i++)		//依次求葉子T[i]的編碼
	{
			//讀入葉子T[i]對應(yīng)的字符
		start=n;			//編碼起始位置的初值
		c=i;				//從葉子T[i]開始上溯
		while((p=T[c].parent)!=NULL)//直至上溯到T[c]是樹根為止
		{	//若T[c]是T[p]的左孩子，則生成代碼0；否則生成代碼1
			cd[--start]=(T[p].lchild==c)?'0':'1';
			c=p;			//繼續(xù)上溯
		}
		strcpy(H[i].bits,&cd[start]);		//復(fù)制編碼位串
	}
	for(i=0;i<n;i++)
		printf("第%d個字符%c的編碼為%s\n",i+1,H[i].ch,H[i].bits);
}