//?HuffmanTree.cpp:?
#include?“HuffmanTree.h“
#include“iostream.h“
/*
?*?前置條件：哈弗曼樹不存在
?*?輸????入：無
?*?功????能：初始化哈弗曼樹
?*?輸????出：無
?*?后置條件：創建一個空哈弗曼樹
?*/

HuffmanTree::HuffmanTree（）
{
????for（int?i=0;i	{
	????w[i].weight=0;
		w[i].a=NULL;
		s[i]=NULL;
	}
	for（?i=0;i	{
		code[i]=-1;
	}
	Count（）;
	i=0;
	while（（w[i].a!=NULL））
	{
	????i++;?????
	}
	m=i;
	InitHuffmanTree（）;
}
/*
?*?前置條件：哈弗曼樹已存在
?*?輸????入：無
?*?功????能：銷毀哈弗曼樹
?*?輸????出：無
?*?后置條件：釋放哈弗曼樹所占用的存儲空間
?*/

HuffmanTree::~HuffmanTree（）
{

}

/*
?*?前置條件：存在一個空哈弗曼樹
?*?輸????入：字符串數組
?*?功????能：初始化哈弗曼樹
?*?輸????出：無
?*?后置條件：哈弗曼樹被初始化
?*/
void?HuffmanTree::InitHuffmanTree（）
{
???????for?（int?i=0;?i<2*m-1;?i++）?????????????//初始化
	???{
??????????huffmantree?[i].parent=?-1;
??????????huffmantree?[i].lchild=?-1;
??????????huffmantree?[i].rchild=?-1;
		??huffmantree[i].data.weight=100;
	???}
	???for?（i=0;?i	???{
??????????huffmantree[i].data.weight=w[i].weight;
		??huffmantree[i].data.a=w[i].a;
	???}
???????for?（int?k=m;?k<2*m-1;?k++）????????????//n-1次合并
	???{??????
???????????SelectCombine（km）;????//在哈弗曼樹中找權值最小的兩個結點并合并??????????
	???}
}


void?HuffmanTree::ReInit（）
{

????for（int?i=0;i	{
	????w[i].weight=0;
		w[i].a=NULL;
		s[i]=NULL;
	}
	for（?i=0;i	{
		code[i]=-1;
	}
	Count（）;
	i=0;
	while（（w[i].a!=NULL））
	{
	????i++;?????
	}
	m=i;
	InitHuffmanTree（）;
}
/*
?*?前置條件：存在一個非空哈弗曼樹
?*?輸????入：無
?*?功????能：建立編碼表利用已經建好的赫夫曼樹進行編碼，并將每個字符的編碼輸出
?*?輸????出：每個字符的編碼
?*?后置條件：編碼表完成
?*/	
void?HuffmanTree::CreateTableHuffmanTree（）??
{
?????Code?cd;
	?int?cpj;
	?for（int?i=0;i	?{?
		?cd.start=m-1;
?????????c=i;
?????????p=huffmantree[c].parent;
?????????while（p!=-1）
		?{?
			?if（huffmantree[p].lchild==c）
?????????????????cd.code[cd.start]=0;
?????????????else
?????????????????cd.code[cd.start]=1;
?????????????cd.start--;
?????????????c=p;
?????????????p=huffmantree[c].parent;
		?}
?????????for（j=cd.start+1;j?????????????Huffcode[i].code[j]=cd.code[j];
?????????Huffcode[i].start=cd.start;
	?}
	?cout<<“編碼成功!“<	?cout<<“編碼結果如下:“<?????for（i=0;i	?{?
?????????cout<?????????for（j=Huffcode[i].start+1;j?????????cout<	?}
}





?/*
?*?前置條件：編碼表完成
?*?輸????入：無
?*?功????能：編碼，根據編碼表對輸入的字符串進行編碼，并將編碼后的字符串輸出
?*?輸????出：編碼后的字符串
?*?后置條件：編碼完成
?*/	??
?void?HuffmanTree::Encoding（）???????????????
?{
?????
	?cout<<“對輸入字符串的編碼如下：“<	?int?k=0ij=0p;
	?while（s[k]!=NULL）
	?{
	????for（i=0;i		{
		????if（huffmantree[i].data.a==s[k]）??
			{
				for（p=Huffcode[i].start+1;p				{
				????cout<					code[j++]=Huffcode[i].code[p];
				}
			}
		}
		k++;
	?}
	?cout<?}
/*
?*?前置條件：編碼完成
?*?輸????入：無
?*?功????能：譯碼，利用已經建好的赫夫曼樹對編碼后的字

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

????.CA....????196724??2003-02-27?02:26??08212291_王碧珺_實驗三_哈夫曼樹\Debug\experiment03_2.exe

????.CA....????317728??2003-02-27?02:26??08212291_王碧珺_實驗三_哈夫曼樹\Debug\experiment03_2.ilk

????.CA....?????43520??2009-11-22?18:13??08212291_王碧珺_實驗三_哈夫曼樹\Debug\experiment03_2.opt

????.CA....????248812??2003-02-27?02:24??08212291_王碧珺_實驗三_哈夫曼樹\Debug\experiment03_2.pch

????.CA....????533504??2003-02-27?02:24??08212291_王碧珺_實驗三_哈夫曼樹\Debug\experiment03_2.pdb

????.CA....?????20040??2003-02-27?02:24??08212291_王碧珺_實驗三_哈夫曼樹\Debug\HuffmanTree.obj

????.CA....??????7645??2003-02-27?02:26??08212291_王碧珺_實驗三_哈夫曼樹\Debug\main.obj

????.CA....?????58368??2003-02-27?02:26??08212291_王碧珺_實驗三_哈夫曼樹\Debug\vc60.idb

????.CA....?????69632??2003-02-27?02:24??08212291_王碧珺_實驗三_哈夫曼樹\Debug\vc60.pdb

????.CA....??????4498??2009-11-22?01:10??08212291_王碧珺_實驗三_哈夫曼樹\experiment03_2.dsp

????.CA....???????536??2009-11-20?21:52??08212291_王碧珺_實驗三_哈夫曼樹\experiment03_2.dsw

????.CA....?????50176??2003-02-27?02:38??08212291_王碧珺_實驗三_哈夫曼樹\experiment03_2.ncb

????.CA....?????53760??2003-02-27?02:38??08212291_王碧珺_實驗三_哈夫曼樹\experiment03_2.opt

????.CA....???????944??2003-02-27?02:26??08212291_王碧珺_實驗三_哈夫曼樹\experiment03_2.plg

????.CA....??????6778??2003-02-27?02:24??08212291_王碧珺_實驗三_哈夫曼樹\HuffmanTree.cpp

????.CA....??????1724??2003-02-27?02:24??08212291_王碧珺_實驗三_哈夫曼樹\HuffmanTree.h

????.CA....??????1132??2003-02-27?02:16??08212291_王碧珺_實驗三_哈夫曼樹\main.cpp

????.C.D...?????????0??2003-02-27?00:09??08212291_王碧珺_實驗三_哈夫曼樹\Debug

????.C.D...?????????0??2003-02-27?00:09??08212291_王碧珺_實驗三_哈夫曼樹

-----------?---------??----------?-----??----

??????????????1615521????????????????????19