用Huffman樹(shù)進(jìn)行編碼與解碼算法

1、佛山科學(xué)技術(shù)學(xué)院實(shí) 驗(yàn) 報(bào) 告課程名稱(chēng) 數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)項(xiàng)目 用Huffman樹(shù)進(jìn)行編碼與解碼算法 專(zhuān)業(yè)班級(jí) 網(wǎng)絡(luò)工程2 姓 名 陳浩明 學(xué) 號(hào) 2010394223 指導(dǎo)教師 成 績(jī) 日 期 1、 實(shí)驗(yàn)?zāi)康?1、通過(guò)本實(shí)驗(yàn)，熟悉二叉樹(shù)、Huffman樹(shù)的基本概念，掌握二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及各種算法2、熟悉用Huffman樹(shù)進(jìn)行電文的加密與解密算法二、實(shí)驗(yàn)內(nèi)容1、Huffman樹(shù)的存儲(chǔ)方式2、加密與解密算法在電文編碼中的應(yīng)用三、實(shí)驗(yàn)原理 給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱(chēng)這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱(chēng)為哈夫曼樹(shù)(Huffman tree)。 Huffman樹(shù)是一

2、種特殊的二叉樹(shù)，其葉結(jié)點(diǎn)的編碼是一種前綴碼，同時(shí)，通過(guò)統(tǒng)計(jì)字符的頻度，能夠達(dá)到編碼電文的最小化。 哈夫曼樹(shù)的構(gòu)造 假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹(shù)有n個(gè)葉子結(jié)點(diǎn)。 n個(gè)權(quán)值分別設(shè)為 w1、w2、wn，則哈夫曼樹(shù)的構(gòu)造規(guī)則為： (1) 將w1、w2、，wn看成是有n 棵樹(shù)的森林(每棵樹(shù)僅有一個(gè)結(jié)點(diǎn))； (2) 在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和； (3)從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林； (4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹(shù)為止，該樹(shù)即為所求得的哈夫曼樹(shù)。四、實(shí)驗(yàn)步驟 1、統(tǒng)計(jì)電文中字符的出現(xiàn)

3、頻率。 2. 用統(tǒng)計(jì)頻率建立Hffman樹(shù)。 3生成前綴碼； 4建立huffman樹(shù)的解碼算法 5用隨機(jī)輸入的電文完成編碼與解碼過(guò)程。5、 程序源代碼及注釋#include #include const int MAX=20; struct huffnodeint weight;int lchild,rchild,parent;struct huffinit /輸入的權(quán)值信息的結(jié)構(gòu) char data; int weight;struct huffcode /哈夫曼樹(shù)編碼的結(jié)構(gòu) char data; char codeMAX+1;class HuffTree /哈夫曼樹(shù)類(lèi)的聲明 public:

4、 HuffTree(huffinit w,int n); HuffTree() void Select(int &min1,int &min2,int m); void Output(); /輸出哈夫曼樹(shù)最終狀態(tài)（tree數(shù)組） void Encode(); /編碼 void Decode(char code); /解碼 private: huffnode tree2*MAX-1; /存儲(chǔ)哈夫曼樹(shù) huffcode cdMAX; /存儲(chǔ)各個(gè)哈夫曼編碼 int size; /哈夫曼樹(shù)的葉子結(jié)點(diǎn)數(shù) ;HuffTree:HuffTree(huffinit w,int n) size=n;for(in

5、t i=0;i2*n-1;i+)treei.parent=-1;treei.lchild=-1;treei.rchild=-1;for(i=0;in;i+) treei.weight=wi.weight; cdi.data=wi.data; int min1=-1; int min2=-1;int m=size;for(int k=n;k2*n-1;k+) Select(min1,min2, m);treemin1.parent=k;treemin2.parent=k;treek.weight=treemin1.weight+treemin2.weight;treek.lchild=min1;

6、treek.rchild=min2;m+;void HuffTree:Select(int &min1,int &min2,int m)/選擇兩個(gè)權(quán)值最小的結(jié)點(diǎn) int a=100; int b=100; for(int i=0;im;i+) if(treei.weighta&treei.parent=-1) a=treei.weight; min1=i; for(i=0;im;i+) if(treei.weightb&treei.parent=-1&i!=min1) b=treei.weight; min2=i; void HuffTree:Output()for(int i=0;i2*si

7、ze-1;i+)couttreei.weight treei.parent treei.lchild treei.rchildendl;void HuffTree:Encode() /編碼 int m;int a;int j; char b100; int k; for(int i=0;i=0;j-) cdi.codek+=bj; cdi.codek=0; coutcdi.datacdi.codeendl; void HuffTree:Decode(char code) /解碼 int n=strlen(code); int a=2*size-2;/根節(jié)點(diǎn)的下標(biāo) for(int i=0;in;

8、i+)if(codei=0) a=treea.lchild; if(codei=1) a=treea.rchild; if(treea.lchild=-1&treea.rchild=-1) coutcda.data; a=2*size-2; elseif(codei+1=0)couterror; coutendl; void main() huffinit w20;int n;char s100;coutn;for(int i=0;in;i+) cout請(qǐng)輸入第i+1wi.data;cinwi.weight; HuffTree H(w,n); cout已經(jīng)建好的節(jié)點(diǎn)信息為endl;H.Output(); cout已經(jīng)建好的節(jié)點(diǎn)編碼信息為endl;H.Encode();char q; do couts;H.Decode(s);coutendl;coutq;while(q=Y);結(jié)果截圖: 六、實(shí)驗(yàn)結(jié)果分析及實(shí)驗(yàn)體會(huì) 通過(guò)用Huffman樹(shù)進(jìn)行編碼與解碼算法的實(shí)驗(yàn)后，對(duì)于huffman樹(shù)的理解和應(yīng)用都有了進(jìn)一步的了解，但對(duì)于快速構(gòu)建huffman樹(shù)還有些有欠純熟，還要多加煉金，并且要對(duì)基礎(chǔ)的二叉樹(shù)等知識(shí)要多加練習(xí)。注：