#include
#include?
typedef?struct?{
????int?weight;
????int?parentlchildrchild;
	char?elem;
}HTNode*HuffmanTree;//動態(tài)分配數(shù)組存儲赫夫曼樹
typedef?char?**HuffmanCode;//動態(tài)分配數(shù)組存儲赫夫曼編碼表
////////////////////////求赫夫曼編碼
void?Select（HuffmanTree?&HTint?nint?*s1int?*s2）
{
???int?i?min;
???for（i=1;i<=n;i++）
???{
	if（HT[i].parent==0）
	{
		min=i;
		i=n+1;
	}
???}
???for（i=1;i<=n;i++）
???{
	if（HT[i].parent==0）
	{??if（HT[i].weight	????min=i;
	}
???}
	*s1=min;
???for（i=1;?i<=n;?i++）
???{
????if（HT[i].parent?==?0?&&?i!=*s1）
	{
?????min?=?i;
?????i?=?n+1;
	}
???}
????for（i=1;i<=n;i++）
???{
	if（HT[i].parent==0&&i!=*s1）
	{???if（HT[i].weight	??min=i;
	}
	}
???*s2=min;
}
////////////////////
void?Huffmantree（HuffmanTree?&HTint*wint?nchar?*e）
{?//w存放n個字符的權(quán)值，構(gòu)造赫夫曼樹HT，并求出n個字符的赫夫曼編碼HC
	int?mis1s2;
	if（n<=1）?return;
	m=2*n-1;//總的結(jié)點
	HT=new?HTNode[m+1];
	for（i=1;i<=n;++i）
	{/*1-n號放葉子結(jié)點，初始化*/
		HT[i].weight=w[i];
		HT[i].lchild=0;
		HT[i].rchild=0;
		HT[i].parent=0;
		HT[i].elem=e[i];
	}
	for（i=n+1;i<=m;++i）?
	{/*非葉子結(jié)點初始化*/
????????HT[i].weight=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
		HT[i].parent=0;
		HT[i].elem=0;
	}
	????cout<<“HT的初態(tài)為：“<		cout<<“weight“<<“??“<<“parent“<<“??“<<“l(fā)child“<<“??“<<“rchild“<	for（i=1;i<=m;i++）//打印空赫夫曼樹
	{?????
		cout<	}

	for（i=n+1;i<=m;++i）
	{//在HT[1……i]選擇parent為0且weight最小的兩個
????????Select（HTi-1&s1&s2）;
		HT[s1].parent=i;
		HT[s2].parent=i;
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	?cout<<“HT的終態(tài)為：“<	?	cout<<“weight“<<“??“<<“parent“<<“??“<<“l(fā)child“<<“??“<<“rchild“<	for（i=1;i<=m;i++）//打印赫夫曼樹
	{?
		cout<	}
}
////////////////////////////////////////////////////////
void?CHuffmancode（HuffmanTree?&HTHuffmanCode?&HCint?n）
{???

	char?*cd;
????int?cfstar;
	HC=new?char*[n+1];
	cd=new?char[n];
	cd[n-1]=‘\0‘;//編碼結(jié)束符

		for（int?i=1;i<=n;++i）
		{
			star=n-1;?//從右向左逐位存放編碼，首先存放編碼結(jié)束符
	for（c=if=HT[i].parent;f!=0;c=ff=HT[f].parent）//從葉子到根結(jié)點求編碼
				if（HT[f].lchild==c）
					cd[--star]=‘0‘;?//左分支標(biāo)0
				else?
					cd[--star]=‘1‘;//右分支標(biāo)1
				HC[i]=new?char[n-star];?//為第i個編碼分配空間
				strcpy（HC[i]&cd[star]）;//從cd復(fù)制編碼串到HC
		}
		delete?cd;//釋放工作空間
??for（i=1;i<=n;i++）
	???cout<}
////////////////////////////
void?main（）
{
????HuffmanTree?HT;?
????HuffmanCode?HC;?
	int?*w;//表示權(quán)值
	char?*e;
	char?c;
	int?inmwei;
	cout<<“請輸入赫夫曼樹的葉子節(jié)點數(shù)目n：“;
	cin>>n;
	w=new?int[n+1];//開辟n+1個數(shù)組空間
	e=new?char[n+1];
	for（i=1;i<=n;i++）
	{
		cout<<“請輸入第“<		cin>>c;
		e[i]=c;
		cout<<“請輸入第“<		cin>>wei;
		w[i]=wei;

	}
???Huffmantree（HTwne）;

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2012-05-07?16:32??實驗四-hfm編碼\
?????文件????????3367??2012-05-04?12:39??實驗四-hfm編碼\1.cpp
?????目錄???????????0??2012-05-07?16:27??實驗四-hfm編碼\Debug\
?????文件???????14133??2012-05-07?16:25??實驗四-hfm編碼\Debug\1.obj
?????文件??????213043??2012-05-07?16:25??實驗四-hfm編碼\Debug\hfm_5_4.exe
?????文件??????284328??2012-05-07?16:25??實驗四-hfm編碼\Debug\hfm_5_4.ilk
?????文件??????250296??2012-05-04?00:11??實驗四-hfm編碼\Debug\hfm_5_4.pch
?????文件??????533504??2012-05-04?12:39??實驗四-hfm編碼\Debug\hfm_5_4.pdb
?????文件???????41984??2012-05-07?16:25??實驗四-hfm編碼\Debug\vc60.idb
?????文件???????61440??2012-05-04?12:39??實驗四-hfm編碼\Debug\vc60.pdb
?????文件????????4290??2012-05-04?00:14??實驗四-hfm編碼\hfm_5_4.dsp
?????文件?????????520??2012-05-04?00:11??實驗四-hfm編碼\hfm_5_4.dsw
?????文件???????41984??2012-05-07?16:26??實驗四-hfm編碼\hfm_5_4.ncb
?????文件???????48640??2012-05-07?16:26??實驗四-hfm編碼\hfm_5_4.opt
?????文件?????????880??2012-05-07?16:25??實驗四-hfm編碼\hfm_5_4.plg
?????文件??????292864??2012-05-04?16:17??實驗四-hfm編碼\王寧實驗四__哈夫曼樹與哈夫曼編碼.doc