數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告電文編碼譯碼哈夫曼編碼

1、福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)：哈夫曼編譯碼器姓名：韋邦權(quán)專業(yè)：2013級計(jì)算機(jī)科學(xué)與技術(shù)學(xué)號：13224624班級：13052316完成日期：2013.12.28哈夫曼編譯碼器一、需求分析在當(dāng)今信息爆炸時代，如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文 件的存儲空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視，哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼 是一種編碼方式，以哈夫曼樹一即最優(yōu)二叉樹，帶權(quán)路徑長度最小的 二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。哈夫曼編碼使用一張?zhí)厥獾木幋a表將 源字符（例如某文件中的一個符號）進(jìn)行編碼。這張編碼表的特殊之 處在于，它是根據(jù)每一個源字

2、符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編 碼，這便使編碼之后的字符串的平均期望長度降低，從而達(dá)到無損壓縮數(shù)據(jù)的目的）。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用 于通信的二進(jìn)制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條 路徑，對路徑上的各分支約定：指向左子樹的分支表示“ 0”碼，指 向右子樹的分支表示“ 1”碼，取每條路徑上的“ 0”或“ T的序列 作為和各個葉子對應(yīng)的字符的編碼， 這就是哈夫曼編碼。哈夫曼譯碼 輸入字符串可以把它編譯成二進(jìn)制代碼， 輸入二進(jìn)制代碼時可以編譯 成字符串。二、設(shè)計(jì)要求對輸入的一串電文字符實(shí)現(xiàn)哈夫曼編碼， 再

3、對哈夫曼編碼生成的代碼串進(jìn)行譯碼，輸出電文字符串。通常我們把數(shù)據(jù)壓縮的過程稱為 編碼，解壓縮的過程稱為解碼。電報(bào)通信是傳遞文字的二進(jìn)制碼形式 的字符串。但在信息傳遞時，總希望總長度能盡可能短，即采用最短 碼。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為 Wi,編碼長度為Li，電文 中有n種字符，則電文編碼總長度為刀 WiLi。若將此對應(yīng)到二叉樹上， Wi為葉結(jié)點(diǎn)的權(quán)，Li為根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長度。那么，刀 WiLi 恰好為二叉樹上帶權(quán)路徑長度。因此，設(shè)計(jì)電文總長最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵哈夫曼樹，此 構(gòu)造過程稱為哈夫曼編碼。設(shè)計(jì)實(shí)現(xiàn)的功能：（1）哈夫曼樹的建立； （2）

4、哈夫曼編碼的生成；（3）編碼文件的譯碼。三、概要設(shè)計(jì)哈夫曼編 譯碼器的主要功能是先建立哈夫曼樹，然后利用建好 的哈夫曼樹生成哈夫曼編碼后進(jìn)行譯碼。在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0、1組成的二進(jìn)制串，稱之為編碼。構(gòu)造一棵哈夫曼樹，規(guī)定哈夫曼樹 中的左分之代表0,右分支代表1,則從根節(jié)點(diǎn)到每個葉子節(jié)點(diǎn)所經(jīng) 過的路徑分支組成的0和1的序列便為該節(jié)點(diǎn)對應(yīng)字符的編碼，稱之 為哈夫曼編碼。最簡單的二進(jìn)制編碼方式是等長編碼。若米用不等長編碼，讓出 現(xiàn)頻率高的字符具有較短的編碼，讓出現(xiàn)頻率低的字符具有較長的編 碼，這樣可能縮短傳送電文的總長度。 哈夫曼樹課用于構(gòu)造使電文的 編碼總長最短的

5、編碼方案。設(shè)計(jì)包含的幾個方面: 哈夫曼樹的建立赫夫曼樹的建立由赫夫曼算法的定義可知， 初始森林中共有n棵只含 有根結(jié)點(diǎn)的二叉樹。算法的第二步是：將當(dāng)前森林中的兩棵根結(jié)點(diǎn)權(quán) 值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就減 少一棵樹，產(chǎn)生一個新結(jié)點(diǎn)。顯然要進(jìn)行 n-1次合并，所以共產(chǎn)生 n- 1個新結(jié)點(diǎn)，它們都是具有兩個孩子的分支結(jié)點(diǎn)。由此可知，最 終求得的哈夫曼樹中一共有2n-1個結(jié)點(diǎn)，其中n個結(jié)點(diǎn)是初始森林 的n個孤立結(jié)點(diǎn)。并且哈夫曼樹中沒有度數(shù)為1的分支結(jié)點(diǎn)。我們可 以利用一個大小為2n-1的一維數(shù)組來存儲赫夫曼樹中的結(jié)點(diǎn)。 定義 的結(jié)構(gòu)體類型如下：typedef struct

6、char data;/結(jié)點(diǎn)字符int weight;/權(quán)值int pare nt;/雙親結(jié)點(diǎn)int lchild;/左孩子結(jié)點(diǎn)int rchild;/右孩子結(jié)點(diǎn)HTNode;哈夫曼編碼要求電文的哈夫曼編碼，必須先定義哈夫曼編碼類型，根據(jù)設(shè)計(jì)要求 和實(shí)際需要定義的類型如下：typedet struct char cdN; / 存放編碼的數(shù)組int start; / 從start 開始讀cd中的哈夫曼編碼Hcode; /編碼結(jié)構(gòu)體類型代碼文件的譯碼譯碼的基本思想是：讀文件中編碼，并與原先生成的哈夫曼編碼表比 較，遇到相等時，即取出其對應(yīng)的字符存入一個新串中。四、詳細(xì)設(shè)計(jì)字符統(tǒng)計(jì)int jsq(ch

7、ar *s,i nt cn t,char str) char *p;int i,j,k;for(i=1;i=256;i+)cnti=0;for(p=s;*p!=0;p+)k=*p;cntk+; j=0;for(i=1,j=0;i=256;i+)if(cnti!=0)j+;return j; 哈夫曼樹的算法void CreateHT(HTNode ht,i nt n,char str,i nt cn )/創(chuàng)建哈夫曼樹函數(shù)for(i nt in put=1;i nput=256;i nput+)stri nput=in put;in t l=0;for(i nt output=1;output=2

8、56;output+)if(cn output !=0)htl.data=stroutput;/按字母順序?qū)⒊霈F(xiàn)的字母依次存入數(shù)組hthtl.weight=c no utput;l+;int i,k,l no de,r no de;int min 1,mi n2;所有結(jié)點(diǎn)的相關(guān)域置初值0構(gòu)造哈夫曼樹for (i=0;i2* n-1;i+)hti.pare nt=hti.lchild=h ti .rchild=0; /for (i=n; i2* n-1;i+)/初始位置初始位置從葉子結(jié)點(diǎn)hti開始上溯/根據(jù)哈夫曼樹求哈夫曼編碼min仁min 2=MAX;intIno de=r no de=0;/

9、Inode置for (k=O;k=i-1;k+)/if (htk.pare nt=O)/if (htk.weightmi n1)/mi n2=mi n1;rnode=l no de;min 1=htk.weight; Ino de=k;else if (htk.weightmi n2) /min 2=htk.weight;r no de=k;ht Ino de.pare nt=i;htr no de.pare nt=i;/父節(jié)點(diǎn)是ihti.weight=ht Ino de.weight+htr no de.weight;父節(jié)點(diǎn)權(quán)值為兩個最小節(jié)點(diǎn)權(quán)值之和hti.lchild=l no de;ht

10、i.rchild=rnode;/和右節(jié)點(diǎn) 哈夫曼編碼void CreateHCode(HTNode ht,HCode hcd,i nt n)int i,p,c;HCode hc;for (i=0;i n;i+)hc.start=n;/c=i;/p=hti.pare nt;while (p!=0)hc.cdhc.start-=(htp.lchild)=c?O:1; 子記為0，右孩子記為1c=p;p=htp.pare nt;/進(jìn)循環(huán)的范圍是-32768-32767和rnode記錄最小權(quán)值的兩個結(jié)點(diǎn)位選出每次外層循環(huán)最小權(quán)值的兩個結(jié)點(diǎn) 只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找比min1小時比min1大，比mi

11、n2小兩個最小節(jié)點(diǎn)的/兩個最小節(jié)點(diǎn)的父節(jié)點(diǎn)的左節(jié)點(diǎn)循序直到樹根結(jié)點(diǎn)結(jié)束循環(huán)/左孩與上句 c=i;p=hti.parent 同義，促hc.start+;/start始字符hcdi=hc;哈夫曼譯碼void deHCode(HTNode ht,HCode hcd,int n,char str) printf(輸出譯碼結(jié)果為:n);int i,j,k,x,m=0;char codeMAX;for (i=0;iMAX;i+)for (j=0;j n;j+)if(stri=htj.data) /同的就輸出這個字符的編碼for (k=hcdj.start;k=n ;k+)codem=hcdj.cdk; /

12、m+;break;/ codem=#;/while(code0!=#)for (i=0;i n ;i+)m=0;mfor (k=hcdi.start,j=0;k=n; k+,j+)/j個數(shù)if(codej=hcdi.cdk) /m+;if(m=j)/符串個數(shù)相等時則輸出這個的data數(shù)據(jù)指向哈夫曼編碼hc.cd中最開/譯碼函數(shù)循環(huán)查找與輸入字符相同的編號， 相將輸出的編碼賦值到數(shù)組中輸出完成后跳出當(dāng)前for循環(huán)把要進(jìn)行譯碼的字符串存入code數(shù)組中為想同編碼個數(shù)的計(jì)數(shù)器為記錄所存儲這個字符的編碼當(dāng)有相同編碼時m值加1當(dāng)輸入的字符串與所存儲的編碼字prin tf(%c,hti.data);for

13、(x=0;codex-j!=#;x+)/把已經(jīng)使用過的 code數(shù)組里的字符串刪除codex=codex+j;II刪除j個數(shù)，往前移動j位prin tf(n);主函數(shù)void mai n()char stMAX,sstMAX;int cn257;int n,i;printf(請輸入字符串(任意字符):n);gets(st);n =jsq(st,c n, sst);IIIIIIIIIIIIIIIIIIIIIIIIIII99for(i=0;i99;i+)ssti=sti;IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIHTNode htM;HCode hcdN;CreateHT

14、(ht ,n, st,c n);CreateHCode(ht,hcd, n);outputHCode(ht,hcd, n); editHCode(ht,hcd, n, sst); deHCode(ht,hcd ,n, sst);五、調(diào)試輸出哈夫曼編碼輸入字符串（任意字符”Nothingis inpocsible t輸岀哈夫曼編碼二11r11100hl11101b11110emuSTh0301111016010n6011n610001011P0101s100t1010輸出編碼結(jié)果輸出譯碼結(jié)果附錄源程序#in elude 函數(shù)需要義用N表示50葉節(jié)點(diǎn)數(shù)用M表示節(jié)點(diǎn)總數(shù)當(dāng)葉節(jié)點(diǎn)數(shù)位n時總節(jié)點(diǎn)數(shù)為2n

15、-1#in elude gets()#defi ne N 256/#defi ne M 2*N-1/#defi ne MAX 32767 typedef structchar data;/結(jié)點(diǎn)字符int weight;/權(quán)值int pare nt;/雙親結(jié)點(diǎn)int lchild;/左孩子結(jié)點(diǎn)int rchild;/右孩子結(jié)點(diǎn)HTNode;/typedef structchar cdN;/存放哈夫曼碼int start;II從start 開始讀 cd中的哈夫曼碼HCode;/Iint jsq(char *s,i nt cn t,char str)char *p;int i,j,k;for(i=1

16、;i=256;i+)cnti=0;for(p=s;*p!=0;p+)k=*p;cntk+;j=0;for(i=1,j=0;i=256;i+)if(cnti!=0)j+;return j;/void CreateHT(HTNode ht,i nt n,char str,i nt cn )/創(chuàng)建哈夫曼樹函數(shù)for(i nt in put=1;i nput=256;i nput+)stri nput=in put;in t l=0;for(i nt output=1;output=256;output+)if(cn output !=0)htl.data=stroutput;/按字母順序?qū)⒊霈F(xiàn)的字母

17、依次存入數(shù)組hthtl.weight=c no utput;l+;int i,k,l no de,r no de;int min 1,mi n2;for (i=0;i2* n-1;i+)/初始位置初始位置從葉子結(jié)點(diǎn)hti開始上溯/根據(jù)哈夫曼樹求哈夫曼編碼循序直到樹根結(jié)點(diǎn)結(jié)束循環(huán)/左孩hti.pare nt=hti.lchild=h ti .rchild=O; / for (i=n; i2* n-1;i+)/min仁min 2=MAX;intIno de=r no de=0;/Inode置for (k=0;k=i-1;k+)/if (htk.pare nt=O)/if (htk.weightmi

18、 n1)/mi n2=mi n1;rnode=l no de;min 1=htk.weight; Ino de=k;else if (htk.weightmi n2)/min 2=htk.weight;r no de=k;ht Ino de.pare nt=i;htr no de.pare nt=i;/父節(jié)點(diǎn)是ihti.weight=ht Ino de.weight+htr no de.weight;父節(jié)點(diǎn)權(quán)值為兩個最小節(jié)點(diǎn)權(quán)值之和hti.lchild=l no de;hti.rchild=rnode;/和右節(jié)點(diǎn)/void CreateHCode(HTNode ht,HCode hcd,i n

19、t n) int i,p,c;HCode hc;for (i=0;i n;i+)hc.start=n;/c=i;/p=hti.pare nt;while (p!=0)hc.cdhc.start-=(htp.lchild)=c?0:1;子記為0，右孩子記為1所有結(jié)點(diǎn)的相關(guān)域置初值0構(gòu)造哈夫曼樹的范圍是-32768-32767和rnode記錄最小權(quán)值的兩個結(jié)點(diǎn)位 選出每次外層循環(huán)最小權(quán)值的兩個結(jié)點(diǎn) 只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找比min1小時比min1大，比min2小兩個最小節(jié)點(diǎn)的/兩個最小節(jié)點(diǎn)的父節(jié)點(diǎn)的左節(jié)點(diǎn)c=p;p=htp.pare nt;進(jìn)循環(huán)hc.start+;始字符hcdi=hc;/v

20、oid outputHCode(HTNode ht,HCode hcd,i nt n) /int i,k;prin tf(輸出哈夫曼編碼for (i=0;i n;i+)prin tf(%c:t,hti.data);for (k=hcdi.start;k=n ;k+)prin tf(%c,hcdi.cdk);prin tf(n);/void editHCode(HTNode ht,HCode hcd,int n,char str) int i,j,k;printf(n輸出編碼結(jié)果:n);for (i=0;iMAX;i+)for (j=0;j n;j+)if(stri=htj.data)同的就輸出

21、這個字符的編碼for (k=hcdj.start;k=n ;k+)prin tf(%c,hcdj.cdk);/start:n);/prin tf(n);與上句 c=i;p=hti.parent/同義，促指向哈夫曼編碼hc.cd中最開輸出哈夫曼編碼的列表輸出data中的所有數(shù)據(jù),輸出所有data中數(shù)據(jù)的編碼從初最開始的字符起輸出編碼函數(shù)循環(huán)查找與輸入字符相同的編號,break;/輸出完成后跳出當(dāng)前for循環(huán)/void deHCode(HTNode ht,HCode hcd,int n,char str) / printf(輸出譯碼結(jié)果為:n);int i,j,k,x,m=0;char codeMAX;for (i=0;iMAX;i+)for (j=0;j n;j+)譯碼函數(shù)if(stri=htj.data) /同的就輸出這個字符的編碼for (k=hcdj.start;k=n ;k+)codem=hcdj.cdk; /m+; break;/code