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

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

3、電文字符串。通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報(bào)通信是傳遞文字的二進(jìn)制碼形式的字符串。但在信息傳遞時(shí)，總希望總長度能盡可能短，即采用最短碼。假設(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) 哈夫曼編碼的生成； (3) 編碼文件的譯碼。 三、概要

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

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

6、雙親結(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)體類型 代碼文件的譯碼 譯碼的基本思想是：讀文件中編碼，并與原先生成的哈夫曼編碼表比較，遇到相等時(shí)，即取出其對應(yīng)的字符存入一個(gè)新串中。四、詳細(xì)設(shè)計(jì)字符統(tǒng)計(jì)int jsq(char *s,int cnt,char str)char *p;int

7、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,int n,char str,int cn) /創(chuàng)建哈夫曼樹函數(shù)for(int input=1;input<=256;input+)strinput=input;int l=0;for(int output=1;output<=256;output+)if(cnoutput

8、 !=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.parent=hti.lchild=hti.rchild=0; /所有結(jié)點(diǎn)的相關(guān)域置初值0 for (i=n;i<2*n-1;i+) /構(gòu)造哈夫曼樹 min1=min2=MAX; /int的范圍是-32768-32767 lnode=rnode=0; /lnode和rnode記錄最小權(quán)值的兩個(gè)結(jié)點(diǎn)位置 for (k=0;k&l

9、t;=i-1;k+) /選出每次外層循環(huán)最小權(quán)值的兩個(gè)結(jié)點(diǎn) if (htk.parent=0) /只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找 if (htk.weight<min1) /比min1小時(shí) min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weight<min2) /比min1大，比min2小 min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)是i hti.weight=htlnode.weight+htrnode.we

10、ight; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)權(quán)值為兩個(gè)最小節(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 (i=0;i<n;i+) /根據(jù)哈夫曼樹求哈夫曼編碼 hc.start=n; /初始位置 c=i; /從葉子結(jié)點(diǎn)hti開始上溯 p=hti.parent; while (p!=0) /循序直到樹根結(jié)點(diǎn)結(jié)束循環(huán) hc.cdhc.start-=(htp.lchild)=c?'0'

11、;:'1' /左孩子記為0，右孩子記為1 c=p; p=htp.parent; /與上句c=i;p=hti.parent同義，促進(jìn)循環(huán) hc.start+; /start指向哈夫曼編碼hc.cd中最開始字符 hcdi=hc; 哈夫曼譯碼void deHCode(HTNode ht,HCode hcd,int n,char str) /譯碼函數(shù)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) /循

12、環(huán)查找與輸入字符相同的編號，相同的就輸出這個(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+)m=0; /m為想同編碼個(gè)數(shù)的計(jì)數(shù)器 for (k=hcdi.start,j=0;k<=n;k+,j+) /j為記錄所存儲這個(gè)字符的編碼個(gè)數(shù)if(codej=hcdi.cdk) /當(dāng)有相同編碼時(shí)m值加1m

13、+;if(m=j) /當(dāng)輸入的字符串與所存儲的編碼字符串個(gè)數(shù)相等時(shí)則輸出這個(gè)的data數(shù)據(jù)printf("%c",hti.data);for(x=0;codex-j!='#'x+) /把已經(jīng)使用過的code數(shù)組里的字符串刪除codex=codex+j; /刪除j個(gè)數(shù)，往前移動j位printf("n");主函數(shù)void main()char stMAX,sstMAX;int cn257;int n,i;printf("請輸入字符串(任意字符):n");gets(st);n=jsq(st,cn,sst);/99for(i=

14、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)試輸出哈夫曼編碼輸出編碼結(jié)果輸出譯碼結(jié)果附錄源程序#include <stdio.h>#include <string.h> /gets()函數(shù)需要#define N 256 /義用N表示50葉節(jié)點(diǎn)數(shù)#define M 2*N-1 /用M表示節(jié)點(diǎn)總數(shù) 當(dāng)

15、葉節(jié)點(diǎn)數(shù)位n時(shí)總節(jié)點(diǎn)數(shù)為2n-1#define MAX 32767typedef struct char data; /結(jié)點(diǎn)字符 int weight; /權(quán)值 int parent; /雙親結(jié)點(diǎn) int lchild; /左孩子結(jié)點(diǎn) int rchild; /右孩子結(jié)點(diǎn)HTNode;/ typedef struct char cdN; /存放哈夫曼碼 int start; /從start開始讀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

16、;*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,int n,char str,int cn) /創(chuàng)建哈夫曼樹函數(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ù)組htht

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

18、 /只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找 if (htk.weight<min1) /比min1小時(shí) min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weight<min2) /比min1大，比min2小 min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)是i hti.weight=htlnode.weight+htrnode.weight; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)權(quán)值為兩個(gè)最小節(jié)點(diǎn)權(quán)值之和 hti.lchild=lnode

19、;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 (i=0;i<n;i+) /根據(jù)哈夫曼樹求哈夫曼編碼 hc.start=n; /初始位置 c=i; /從葉子結(jié)點(diǎn)hti開始上溯 p=hti.parent; while (p!=0) /循序直到樹根結(jié)點(diǎn)結(jié)束循環(huán) hc.cdhc.start-=(htp.lchild)=c?'0':'1' /左孩子記為0，右孩子記為1 c=p; p=htp.parent; /與上

20、句c=i;p=hti.parent同義，促進(jìn)循環(huán) hc.start+; /start指向哈夫曼編碼hc.cd中最開始字符 hcdi=hc; /void outputHCode(HTNode ht,HCode hcd,int n) /輸出哈夫曼編碼的列表 int i,k; printf(" 輸出哈夫曼編碼:n"); for (i=0;i<n;i+) /輸出data中的所有數(shù)據(jù)， printf(" %c:t",hti.data); for (k=hcdi.start;k<=n;k+) /輸出所有data中數(shù)據(jù)的編碼 printf("%c

21、",hcdi.cdk); /從初最開始的字符起輸出 printf("n"); /void editHCode(HTNode ht,HCode hcd,int n,char str) /編碼函數(shù)int i,j,k;printf("n輸出編碼結(jié)果:n");for (i=0;i<MAX;i+) for (j=0;j<n;j+)if(stri=htj.data) /循環(huán)查找與輸入字符相同的編號，相同的就輸出這個(gè)字符的編碼for (k=hcdj.start;k<=n;k+) printf("%c",hcdj.cdk); break; /輸出完成后跳出當(dāng)前for循環(huán)printf("n");/void deHCode(HTNode ht,HCode hcd,int n,char str) /譯碼函數(shù)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) /循環(huán)查找與輸入字符相同的編號，相同的就輸出這個(gè)字符的編碼for