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

《用Huffman樹進(jìn)行編碼與解碼算法.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

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

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

3、3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。四、實驗步驟1、統(tǒng)計電文中字符的出現(xiàn)頻率。2.用統(tǒng)計頻率建立Hffman樹。3．生成前綴碼；4．建立huffman樹的解碼算法．5．用隨機(jī)輸入的電文完成編碼與解碼過程。五、程序源代碼及注釋#include#includeconstintMAX=20;structhuffnode{intweight;intlchild,rchild,parent;};structhuffinit//輸入的權(quán)值信息的結(jié)構(gòu){char

4、data;intweight;};structhuffcode//哈夫曼樹編碼的結(jié)構(gòu){chardata;charcode[MAX+1];};classHuffTree//哈夫曼樹類的聲明{public:HuffTree(huffinitw[],intn);~HuffTree(){}voidSelect(int&min1,int&min2,intm);voidOutput();//輸出哈夫曼樹最終狀態(tài)（tree數(shù)組）voidEncode();//編碼voidDecode(charcode[]);//解碼privat

5、e:huffnodetree[2*MAX-1];//存儲哈夫曼樹huffcodecd[MAX];//存儲各個哈夫曼編碼intsize;//哈夫曼樹的葉子結(jié)點數(shù)};HuffTree::HuffTree(huffinitw[],intn){size=n;for(inti=0;i<2*n-1;i++){tree[i].parent=-1;tree[i].lchild=-1;tree[i].rchild=-1;}for(i=0;i

6、w[i].data;}intmin1=-1;intmin2=-1;intm=size;for(intk=n;k<2*n-1;k++){Select(min1,min2,m);tree[min1].parent=k;tree[min2].parent=k;tree[k].weight=tree[min1].weight+tree[min2].weight;tree[k].lchild=min1;tree[k].rchild=min2;m++;}}voidHuffTree::Select(int&min1,int&m

7、in2,intm)//選擇兩個權(quán)值最小的結(jié)點{inta=100;intb=100;for(inti=0;i

8、*size-1;i++){cout<