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

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

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

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

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

5、有較長(zhǎng)的編 碼,這樣可能縮短傳送電文的總長(zhǎng)度。 哈夫曼樹(shù)課用于構(gòu)造使電文的 編碼總長(zhǎng)最短的編碼方案。設(shè)計(jì)包含的幾個(gè)方面： 哈夫曼樹(shù)的建立赫夫曼樹(shù)的建立由赫夫曼算法的定義可知， 初始森林中共有 n 棵只含 有根結(jié)點(diǎn)的二叉樹(shù)。 算法的第二步是： 將當(dāng)前森林中的兩棵根結(jié)點(diǎn)權(quán) 值最小的二叉樹(shù)，合并成一棵新的二叉樹(shù)；每合并一次，森林中就減 少一棵樹(shù)，產(chǎn)生一個(gè)新結(jié)點(diǎn)。顯然要進(jìn)行 n 1 次合并，所以共產(chǎn)生 n 1 個(gè)新結(jié)點(diǎn)，它們都是具有兩個(gè)孩子的分支結(jié)點(diǎn)。由此可知，最 終求得的哈夫曼樹(shù)中一共有 2n1 個(gè)結(jié)點(diǎn)，其中 n 個(gè)結(jié)點(diǎn)是初始森林 的 n 個(gè)孤立結(jié)點(diǎn)。 并且哈夫曼樹(shù)中沒(méi)有度數(shù)為 1 的分支結(jié)點(diǎn)。 我

6、們可 以利用一個(gè)大小為 2n-1 的一維數(shù)組來(lái)存儲(chǔ)赫夫曼樹(shù)中的結(jié)點(diǎn)。定義 的結(jié)構(gòu)體類型如下： typedef structchar data;/ 結(jié)點(diǎn)字符int weight; int parent; int lchild; int rchild;/權(quán)值/雙親結(jié)點(diǎn) /左孩子結(jié)點(diǎn) /右孩子結(jié)點(diǎn)HTNode; 哈夫曼編碼要求電文的哈夫曼編碼， 必須先定義哈夫曼編碼類型， 根據(jù)設(shè)計(jì)要求 和實(shí)際需要定義的類型如下：typedet struct char cdN; / 存放編碼的數(shù)組int start; / 從 start 開(kāi)始讀 cd 中的哈夫曼編碼 Hcode; / 編碼結(jié)構(gòu)體類型 代碼文件的譯碼譯

7、碼的基本思想是： 讀文件中編碼， 并與原先生成的哈夫曼編碼表比 較，遇到相等時(shí)，即取出其對(duì)應(yīng)的字符存入一個(gè)新串中。四、詳細(xì)設(shè)計(jì)字符統(tǒng)計(jì)int jsq(char *s,int cnt,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;哈夫曼樹(shù)的算法void CreateHT(HTNode ht,int n,char str,int cn) for(int

8、input=1;input<=256;input+) strinput=input;int l=0;for(int output=1;output<=256;output+) if(cnoutput !=0)htl.data=stroutput;的字母依次存入數(shù)組 hthtl.weight=cnoutput;l+;/創(chuàng)建哈夫曼樹(shù)函數(shù)/按字母順序?qū)⒊霈F(xiàn)int i,k,lnode,rnode;int min1,min2;for (i=0;i<2*n-1;i+)hti.parent=hti.lchild=hti.rchild=0;for (i=n;i<2*n-1;i+)/ 所

9、有結(jié)點(diǎn)的相關(guān)域置初值 0 /構(gòu)造哈夫曼樹(shù)min1=min2=MAX;lnode=rnode=0;for (k=0;k<=i-1;k+)/int 的范圍是 -32768-32767if (htk.parent=0)if (htk.weight<min1)min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if (htk.weight<min2)min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i;/只在尚未構(gòu)造二叉樹(shù)的結(jié)點(diǎn)中查找/ 比 min1 小時(shí)/比 min1 大

10、，比 min2 小/ 兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)是 ihti.weight=htlnode.weight+htrnode.weight; 為兩個(gè)最小節(jié)點(diǎn)權(quán)值之和/兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)權(quán)值hti.lchild=lnode;hti.rchild=rnode;哈夫曼編碼/父節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)void CreateHCode(HTNode ht,HCode hcd,int n) hc.start=n; c=i;/初始位置/從葉子結(jié)點(diǎn) hti 開(kāi)始上溯int i,p,c;HCode hc;for (i=0;i<n;i+)/根據(jù)哈夫曼樹(shù)求哈夫曼編碼p=hti.parent;while (p!=0) /

11、循序直到樹(shù)根結(jié)點(diǎn)結(jié)束循環(huán)hc.cdhc.start-=(htp.lchild)=c?'0':'1'/ 左孩子記為 0，右孩子記為 1c=p;p=htp.parent; hc.start+; hcdi=hc;/與上句 c=i;p=hti.parent 同義，促進(jìn)循環(huán)/start 指向哈夫曼編碼 hc.cd 中最開(kāi)始字符/lnode 和 rnode 記錄最小權(quán)值的兩個(gè)結(jié)點(diǎn)位置 /選出每次外層循環(huán)最小權(quán)值的兩個(gè)結(jié)點(diǎn) 哈夫曼譯碼void deHCode(HTNode ht,HCode hcd,int n,char str)/ 譯碼函數(shù)printf(" 輸出譯碼

12、結(jié)果為 :n");int i,j,k,x,m=0;char codeMAX;for (i=0;i<MAX;i+)for (j=0;j<n;j+)if(stri=htj.data) / 循環(huán)查找與輸入字符相同的編號(hào)，相同的就 輸出這個(gè)字符的編碼for (k=hcdj.start;k<=n;k+)codem=hcdj.cdk;/ 將輸出的編碼賦值到數(shù)組中m+;break;/ 輸出完成后跳出當(dāng)前 for 循環(huán)codem='#'/把要進(jìn)行譯碼的字符串存入 code 數(shù)組中while(code0!='#')for (i=0;i<n;i+)

13、m=0;for (k=hcdi.start,j=0;k<=n;k+,j+)if(codej=hcdi.cdk) m+;if(m=j) 串個(gè)數(shù)相等時(shí)則輸出這個(gè)的 data 數(shù)據(jù)printf("%c",hti.data); for(x=0;codex-j!='#'x+) 刪除codex=codex+j;/m 為想同編碼個(gè)數(shù)的計(jì)數(shù)器/j 為記錄所存儲(chǔ)這個(gè)字符的編碼個(gè)數(shù)/當(dāng)有相同編碼時(shí) m 值加 1/當(dāng)輸入的字符串與所存儲(chǔ)的編碼字符/ 把已經(jīng)使用過(guò)的 code 數(shù)組里的字符串刪除j個(gè)數(shù)，往前移動(dòng)j位printf("n"); 主函數(shù)void

14、main()char stMAX,sstMAX;int cn257;int n,i;printf(" 請(qǐng)輸入字符串 (任意字符 ):n"); gets(st);n=jsq(st,cn,sst);/99for(i=0;i<99;i+)ssti=sti;/HTNode htM;HCode hcdN;CreateHT(ht,n,st,cn);CreateHCode(ht,hcd,n); outputHCode(ht,hcd,n); editHCode(ht,hcd,n,sst); deHCode(ht,hcd,n,sst);五、調(diào)試輸出哈夫曼編碼輸入字符串（任意字符興Not

15、hingis inpocsible t輸岀哈夫曼編碼二11r11100hl11101b11110emuSTh63011110I6010n6011n610001011P0101s100t1010輸出編碼結(jié)果輸出譯碼結(jié)果THIS PROGRAM I£ MV FRAUORITE輸岀編碼結(jié)果為：1011010100100101011110901101110010110010111110001011100101011111190001101110111 01100910001110001111011100001113110101 0110110110111101111*111100011300

16、1111106091 110011110001B101101111010輸出編譯結(jié)果為：THIS PROGRAM IS ttV FflAUOEITEPress： any key to cont inueM附錄源程序#i nclude <stdio.h> #in elude <stri ng.h> #defi ne N 256 #define M 2*N-1 #defi ne MAX 32767/gets ()函數(shù)需要/義用N表示50葉節(jié)點(diǎn)數(shù)/用M表示節(jié)點(diǎn)總數(shù)當(dāng)葉節(jié)點(diǎn)數(shù)位n時(shí)總節(jié)點(diǎn)數(shù)為2n-1typedef structchar data; int weight; int

17、 pare nt; int lchild; int rchild;HTNode;/結(jié)點(diǎn)字符/權(quán)值/雙親結(jié)點(diǎn)左孩子結(jié)點(diǎn)/右孩子結(jié)點(diǎn)typedef structchar cdN;/存放哈夫曼碼int start;/從 start 開(kāi)始讀 cd 中的哈夫曼碼HCode;/int jsq(char *s,int cnt,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

18、;/void CreateHT(HTNode ht,int n,char str,int cn)/ 創(chuàng)建哈夫曼樹(shù)函數(shù)for(int input=1;input<=256;input+)strinput=input;int l=0;for(int output=1;output<=256;output+)if(cnoutput !=0)htl.data=stroutput;/按字母順序?qū)⒊霈F(xiàn)的字母依次存入數(shù)組 hthtl.weight=cnoutput;l+;int i,k,lnode,rnode;int min1,min2;for (i=0;i<2*n-1;i+)hti.pa

19、rent=hti.lchild=hti.rchild=0;/ 所有結(jié)點(diǎn)的相關(guān)域置初值 0for (i=n;i<2*n-1;i+)min1=min2=MAX;/構(gòu)造哈夫曼樹(shù)/int 的范圍是 -32768-32767lnode=rnode=0;for (k=0;k<=i-1;k+)/lnode 和 rnode 記錄最小權(quán)值的兩個(gè)結(jié)點(diǎn)位置/選出每次外層循環(huán)最小權(quán)值的兩個(gè)結(jié)點(diǎn)if (htk.parent=0)if (htk.weight<min1)min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if (htk.weight<

20、;min2)min2=htk.weight;rnode=k;/只在尚未構(gòu)造二叉樹(shù)的結(jié)點(diǎn)中查找/ 比 min1 小時(shí)/比 min1 大，比 min2 小htlnode.parent=i;htrnode.parent=i;hti.weight=htlnode.weight+htrnode.weight;為兩個(gè)最小節(jié)點(diǎn)權(quán)值之和/ 兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)是 i/兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)權(quán)值hti.lchild=lnode;hti.rchild=rnode;/父節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)void CreateHCode(HTNode ht,HCode hcd,int n)int i,p,c;HCode hc;for

21、 (i=0;i<n;i+) hc.start=n; c=i; p=hti.parent; while (p!=0) /根據(jù)哈夫曼樹(shù)求哈夫曼編碼/初始位置/從葉子結(jié)點(diǎn) hti 開(kāi)始上溯/ 循序直到樹(shù)根結(jié)點(diǎn)結(jié)束循環(huán)hc.cdhc.start-=(htp.lchild)=c?'0':'1' 子記為 1/ 左孩子記為 0，右孩c=p; p=htp.parent;hc.start+;hcdi=hc;/與上句 c=i;p=hti.parent 同義，促進(jìn)循環(huán)/start 指向哈夫曼編碼 hc.cd 中最開(kāi)始字符/void outputHCode(HTNode ht,H

22、Code hcd,int n) int i,k;printf(" 輸出哈夫曼編碼 :n");for (i=0;i<n;i+)printf(" %c:t",hti.data);for (k=hcdi.start;k<=n;k+)printf("%c",hcdi.cdk);printf("n");/void editHCode(HTNode ht,HCode hcd,int n,char str) int i,j,k;printf("n 輸出編碼結(jié)果 :n"); for (i=0;i&l

23、t;MAX;i+) for (j=0;j<n;j+) if(stri=htj.data) 輸出這個(gè)字符的編碼/輸出哈夫曼編碼的列表/輸出 data 中的所有數(shù)據(jù)，/輸出所有 data 中數(shù)據(jù)的編碼/從初最開(kāi)始的字符起輸出/編碼函數(shù)/循環(huán)查找與輸入字符相同的編號(hào)，相同的就for (k=hcdj.start;k<=n;k+)printf("%c",hcdj.cdk);/ 輸出完成后跳出當(dāng)前 for 循環(huán) break;printf("n");/譯碼函數(shù)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;i<MAX;i+)for (j=0;j<n;j+)if(stri=htj.data