#include??
#include??
#include?
#include?
?
typedef?int?TElemType;?
using?namespace?std;
typedef?struct?
{?
	int?weight;?
????int?parentlchildrchild;?
}HTNode*?HuffmanTree;?

typedef?char?**HuffmanCode;//定義Huffman編碼表?

//-----------全局變量-----------------------?
HuffmanTree?HT;?
HuffmanCode?HC;?
int?w[50]ijn;?
char?z[50];??//字符數組?
int?flag=0;?
int?numb=0;?
//-----------------select函數---------------------------
void?select（HuffmanTree?tint?iint?&s1int?&s2）?
{?//?t[1..i]中權值最小的倆結點的序號為s1，s2?
??????int?j=1max=1000;
	??for（j=1;j<=i;j++）//尋找parent為0的節點，并將器parent賦為1
	??{
		??if（t[j].parent==0&&t[j].weight		??{
			??s1=j;
			??max=t[j].weight;
		??}
	??}?
	??t[s1].parent=1;
	??max=1000;
	??for（j=1;j<=i;j++）
	??{
		??if（t[j].parent==0&&t[j].weight??????????{
			??s2=j;
??????????????max=t[j].weight;
		??}
	??}
}
//?--------------算法6.12--------------------------?
void?HuffmanCoding（HuffmanTree?&HTHuffmanCode?&HCint?*wint?n）?
{?//?w存放n個字符的權值（均>0）構造赫夫曼樹HT并求出n個字符的赫夫曼編碼HC?
	int?mis1s2start;?int?cf;?
????HuffmanTree?p;??char?*cd;

????if（n<=1）??return;//檢測結點數是否可以構成樹?
????m=2*n-1;?
????HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;?//?0號單元未用?
????for（p=HT+1i=1;i<=n;++i++p++w）?//HT[1..n]結點有權值
????{?
		p->weight=*w;??p->parent=0;?
		p->lchild=0;???p->rchild=0;?
	}?
????for（;i<=m;++i++p）?//HT[n+1...m]結點權值為0
	{?
		p->weight=0;??p->parent=0;?
		p->lchild=0;???p->rchild=0;?
	}?
	for（i=n+1;i<=m;++i）?//?建赫夫曼樹?
	{?//?在HT[1~i-1]中選擇parent為0且weight最小的兩個結點其序號分別為s1和s2?
		select（HTi-1s1s2）;?
????????HT[s1].parent=HT[s2].parent=i;?
????????HT[i].lchild=s1;?
????????HT[i].rchild=s2;?
????????HT[i].weight=HT[s1].weight+HT[s2].weight;?
????}?
????//?-------------從葉子到根逆向求每個字符的赫夫曼編碼?--------------
????HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））;?//?分配n個字符編碼的頭指針向量（[0]不用）?
????cd=（char*）malloc（n*sizeof（char））;?//?分配求編碼的工作空間?
????cd[n-1]=‘e‘;?//?編碼結束符?
????for（i=1;i<=n;i++）?
????{?//?逐個字符求赫夫曼編碼?
		start=n;//-1;?//?編碼結束符位置?
		for（c=if=HT[i].parent;f!=0;c=ff=HT[f].parent）?
		{	//?從葉子到根逆向求編碼?
			if（HT[f].lchild==c）?
				cd[--start]=‘0‘;?
			else?
				cd[--start]=‘1‘;?
		}
?????HC[i]=（char*）malloc（（n-start）*sizeof（char））;?//?為第i個字符編碼分配空間?
?????strcpy（HC[i]&cd[start]）;?//?從cd復制編碼（串）到HC?
?????}?
?????free（cd）;?//?釋放工作空間?
}?
//--------------初始化赫夫曼鏈表---------------------------------?
void?Initialization（）?
{?
	char?s[10];
	cout<<“請輸入字符集字符個數“;
	cin>>n;
	cout<<“請輸入字符集及其權值:“;
	cin.getline（s1）;
	cin.getline（z30）;
	for（i=0;i	{
	???cin>>*（w+i）;	???
	}
????HuffmanCoding（HTHCwn）;
	
????//------------------------打印編碼-------------------------------------------?
????cout<<“字符對應的編碼為:“<????for（i=1;i<=n;i++）?
????{?
????????cout<<*（z+i-1）<<‘?‘;?
		puts（HC[i]）;?//把p指向的字符串輸出到終端?
????}?
????//--------------------------將赫夫曼編碼寫入文件------------------------?
????cout<<“下面將赫夫曼編碼寫入文件“<