實(shí)驗(yàn)二：用Huffman樹(shù)進(jìn)行編碼與解碼算法.doc

《實(shí)驗(yàn)二：用Huffman樹(shù)進(jìn)行編碼與解碼算法.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、（規(guī)格為A4紙或A3紙折疊）（用五號(hào)宋體和TimesNewRoman,A4紙雙面打?。┮?、實(shí)驗(yàn)?zāi)康模?、通過(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á)到最小，稱這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，又稱為哈夫曼樹(shù)（Huffmantree）。Huffman樹(shù)是一種特殊的二叉樹(shù)，其葉結(jié)點(diǎn)的編碼是一種前綴碼，同時(shí)，

2、通過(guò)統(tǒng)計(jì)字符的頻度，能夠達(dá)到編碼電文的最小化。假設(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.調(diào)試下列程序“二叉樹(shù)程序一”，掌握鏈?zhǔn)蕉鏄?shù)構(gòu)造

3、的算法和實(shí)現(xiàn)方式。2.根據(jù)二叉樹(shù)程序的學(xué)習(xí)，完成Huffman樹(shù)的構(gòu)造、編碼和解碼的實(shí)現(xiàn)。（1）統(tǒng)計(jì)電文中字符的出現(xiàn)頻率。（2）用統(tǒng)計(jì)頻率建立Huffman樹(shù)，并生成前綴碼；（3）建立Huffman樹(shù)的解碼算法。（4）用隨機(jī)輸入的電文完成編碼與解碼過(guò)程。五、程序源代碼及注釋#include#include#includetypedefstruct{charch;intweight;intparent,lchild,rchild;}HTnode,*Huffmantree;//動(dòng)態(tài)分配數(shù)組

4、存儲(chǔ)赫夫曼樹(shù)typedefchar**Huffmancode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表intmain(){//------------構(gòu)造赫夫曼樹(shù)及赫夫曼編碼-------------------HuffmantreeHT;HuffmancodeHC;char*cd,s[100],g[100];intn,mm,m,i,j=0,f,start,c,s1=0,s2=0,temp1,temp2;intw[26];inta[26]={0};printf("請(qǐng)輸入字符：");gets(s);n=strlen(s);HT=(Huffmantree

5、)malloc((m+1)*sizeof(HTnode));//0號(hào)單元未用for(i=0;i

6、parent=HT[i].lchild=HT[i].rchild=0;}for(;i<=m;++i)HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0;//除葉子外的節(jié)點(diǎn)賦初值for(i=n+1;i<=m;i++){//建赫夫曼樹(shù)//在HT[1..i-1]選擇parent為0且weight最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為別為s1,s2.temp1=temp2=100;for(j=1;j<=i-1;j++)if(HT[j].parent==0)if(HT[j].weight

7、1=HT[j].weight;s1=j;}for(j=1;j<=i-1;j++)if(HT[j].parent==0&&j!=s1)if(HT[j].weight

8、");for(i=1;i<=m;i++)printf("%-4d%4d%8d%8d%8d%6c",i,HT[i].weight,HT[i].lchild,H