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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 題目：哈夫曼編碼譯碼 專業(yè)：通信工程 學號： 指導教師：吳澤暉 目錄 目錄 1 一、需求分析 2 二、設(shè)計要求 2 三、概要設(shè)計 2 1、 流程圖 2 2、 設(shè)計包含的幾個部分 4 四、詳細設(shè)計 2 五、顯示結(jié)果 9. 六、心得體會 10 七、參考文獻 11 哈夫曼編碼譯碼 一、 需求分析 在當今信息爆炸時代， 如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲空 間和計算機網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視， 赫夫曼編碼正是一種應用 廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。 哈夫曼編碼是一種編碼方式， 以哈夫曼樹即 最優(yōu)二叉樹， 帶權(quán)路徑長度最小的二叉樹， 經(jīng)常應用于數(shù)據(jù)壓縮。 哈弗曼編

2、碼使 用一特殊的編碼表將源字符 (例如某文件中的一個符號) 進行編碼。 這編碼表的 特殊之處在于， 它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的 (出現(xiàn)概率 高的字符使用較短的編碼， 反之出現(xiàn)概率低的則使用較長的編碼， 這便使編碼之 后的字符串的平均期望長度降低，從而達到無損壓縮數(shù)據(jù)的目的) 。赫夫曼編碼 的應用很廣泛， 利用赫夫曼樹求得的用于通信的二進制編碼稱為赫夫曼編碼。 樹 中從根到每個葉子都有一條路徑， 對路徑上的各分支約定： 指向左子樹的分支表 示“ 0”碼，指向右子樹的分支表示“ 1”碼，取每條路徑上的“ 0”或“ 1”的序 列作為和各個葉子對應的字符的編碼， 這就是赫夫曼編碼。

3、 哈弗曼譯碼輸入字符 串可以把它編譯成二進制代碼，輸入二進制代碼時可以編譯成字符串。 二、 設(shè)計要求 對輸入的一串電文字符實現(xiàn)赫夫曼編碼， 再對赫夫曼編碼生成的代碼串進行 譯碼，輸出電文字符串。 通常我們把數(shù)據(jù)壓縮的過程稱為編碼， 解壓縮的過程稱 為解碼。電報通信是傳遞文字的二進制碼形式的字符串。 但在信息傳遞時， 總希 望總長度能盡可能短，即采用最短碼。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為Wi， 編碼長度為Li，電文中有n種字符，則電文編碼總長度為刀 WiLi。若將此對應 到二叉樹上，Wi為葉結(jié)點的權(quán)，Li為根結(jié)點到葉結(jié)點的路徑長度。那么，刀WiLi 恰好為二叉樹上帶權(quán)路徑長度。因此 ，設(shè)計電文

4、總長最短的二進制前綴編碼， 就是以 n 種字符出現(xiàn)的頻率作權(quán)， 構(gòu)造一棵赫夫曼樹， 此構(gòu)造過程稱為赫夫曼編 碼。設(shè)計實現(xiàn)的功能： (1) 赫夫曼樹的建立； (2) 赫夫曼編碼的生成； (3) 編 碼文件的譯碼。 三、 概要設(shè)計 哈夫曼編 譯碼器的主要功能是先建立哈夫曼樹，然后利用建好的哈夫曼樹 生成哈夫曼編碼后進行譯碼 。 在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進制字符 0、1 組成的二 進制串，稱之為編碼。構(gòu)造一棵哈夫曼樹，規(guī)定哈夫曼樹中的左分之代表 0，右 分支代表 1，則從根節(jié)點到每個葉子節(jié)點所經(jīng)過的路徑分支組成的 0和 1的序列 便為該節(jié)點對應字符的編碼，稱之為哈夫曼編碼。 最簡

5、單的二進制編碼方式是等長編碼。 若采用不等長編碼， 讓出現(xiàn)頻率高的 字符具有較短的編碼， 讓出現(xiàn)頻率低的字符具有較長的編碼， 這樣可能縮短傳送 電文的總長度。哈夫曼樹課用于構(gòu)造使電文的編碼總長最短的編碼方案。 (1)其主要流程圖如圖 1-1 所示。 開始 是 結(jié)點數(shù)是否大于1 l2*N? 是 輸出根結(jié)點和權(quán)值 將data和權(quán)值賦給ht 調(diào)用SELECT函數(shù) 計算根結(jié)點函數(shù) 父結(jié)點為兩子結(jié)點之和 是否為根結(jié)點? 是 左子是否為空? 否 否 是否為空 輸出兩子結(jié)點和已構(gòu)造的結(jié)點 此時編碼為0 編碼為1 結(jié)束 (2)設(shè)計包含的幾個方面： 赫夫曼樹的建立 赫夫曼樹的建立由赫夫曼算法的定義可知， 初始森

6、林中共有 n 棵只含有根結(jié)點的 二叉樹。算法的第二步是： 將當前森林中的兩棵根結(jié)點權(quán)值最小的二叉樹， 合并 成一棵新的二叉樹；每合并一次，森林中就減少一棵樹，產(chǎn)生一個新結(jié)點。顯然 要進行 n1 次合并，所以共產(chǎn)生 n1 個新結(jié)點，它們都是具有兩個孩子的分支 結(jié)點。由此可知，最終求得的赫夫曼樹中一共有2n1個結(jié)點，其中n個結(jié)點是 初始森林的 n 個孤立結(jié)點。 并且赫夫曼樹中沒有度數(shù)為 1 的分支結(jié)點。 我們可以 利用一個大小為 2n-1 的一維數(shù)組來存儲赫夫曼樹中的結(jié)點。 赫夫曼編碼 要求電文的赫夫曼編碼， 必須先定義赫夫曼編碼類型， 根據(jù)設(shè)計要求和實際需要 定義的類型如下： typedet s

7、truct char ch; / 存放編碼的字符 char bitsN 1; /存放編碼位串 int len; / 編碼的長度 CodeNode; / 編碼結(jié)構(gòu)體類型 代碼文件的譯碼 譯碼的基本思想是： 讀文件中編碼， 并與原先生成的赫夫曼編碼表比較， 遇到相 等時，即取出其對應的字符存入一個新串中。 四、詳細設(shè)計 (1)赫夫曼樹的存儲結(jié)構(gòu)描述為: #define N 50 /葉子結(jié)點數(shù) #define M 2*N-1 /赫夫曼樹中結(jié)點總數(shù) typedef struct int weight; / 葉子結(jié)點的權(quán)值 int lchild, rchild, parent; / 左右孩子及雙親指針

8、HTNode; / 樹中結(jié)點類型 typedef HTNode HuffmanTreeM+1; 哈弗曼樹的算法 void CreateHT(HTNode ht,int n) / int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; / -1 for (i=n;i2*n-1;i+)/ min1=min2=32767; /int lnode=rnode=-1;/lnode 調(diào)用輸入的數(shù)組 ht, 和節(jié)點數(shù) n 所有結(jié)點的相關(guān)域置初值 構(gòu)造哈夫曼樹 的圍是 -32768

9、 32767 和 rnode 記錄最小權(quán)值的兩個結(jié)點 位置 for (k=0;k=i-1;k+) 只在尚未構(gòu)造二叉樹的結(jié)點中查 若權(quán)值小于最小的左節(jié)點的權(quán)值 if (htk.parent=-1) / 找 if (htk.weightmin1)/ min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin2) min2=htk.weight;rnode=k; 兩個最小節(jié)點的 / 兩個最小節(jié)點的 父節(jié)點的左節(jié)點 htlnode.parent=i;htrnode.parent=i; / 父節(jié)點是 i hti.weigh

10、t=htlnode.weight+htrnode.weight; 父節(jié)點權(quán)值為兩個最小節(jié)點權(quán)值之和 hti.lchild=lnode;hti.rchild=rnode; / 和右節(jié)點 (2)哈弗曼編碼 void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;in;i+) / hc.start=n;c=i; f=hti.parent; while (f!=-1) / if (htf.lchild=c) / hc.cdhc.start-=0; else / hc.cdhc.start-=1; c=f;f=h

11、tf.parent; hc.start+; /start 根據(jù)哈夫曼樹求哈夫曼編碼 循序直到樹根結(jié)點結(jié)束循環(huán) 處理左孩子結(jié)點 處理右孩子結(jié)點 指向哈夫曼編碼 hc.cd 中最開 始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) / int i,k; printf( 輸出哈夫曼編碼 :n); for (i=0;in;i+) / printf( %c:t,hti.data); for (k=hcdi.start;k=n;k+)/ printf(%c,hcdi.cdk); printf(n); void editHCode(HTNode h

12、t,HCode hcd,int n) / char stringMAXSIZE; int i,j,k; scanf(%s,string); / 數(shù)組中 printf(n 輸出編碼結(jié)果 :n); for (i=0;stringi!=#;i+) /# for (j=0;jn;j+) if(stringi=htj.data) / 號，相同的就輸出這個字符的編碼 for (k=hcdj.start;k=n;k+) 輸出哈夫曼編碼的列表 輸出 data 中的所有數(shù)據(jù)，即 A-Z 輸出所有 data 中數(shù)據(jù)的編碼 編碼函數(shù) 把要進行編碼的字符串存入 string 為終止標志 循環(huán)查找與輸入字符相同的編 p

13、rintf(%c,hcdj.cdk); break; / 輸出完成后跳出當前 for 循環(huán) (3)哈弗曼譯碼 void deHCode(HTNode ht,HCode hcd,int n) / char codeMAXSIZE; int i,j,l,k,m,x; scanf(%s,code); / 組中 while(code0!=#) for (i=0;in;i+) m=0; /m for (k=hcdi.start,j=0;k=n;k+,j+) /j 個數(shù) if(codej=hcdi.cdk) / m+; if(m=j) / 符串個數(shù)相等時則輸出這個的 data 數(shù)據(jù) printf(%c,h

14、ti.data); for(x=0;codex-1!=#;x+) / 字符串刪除 codex=codex+j; (4)主函數(shù) 譯碼函數(shù) 把要進行譯碼的字符串存入 code 數(shù) 為想同編碼個數(shù)的計數(shù)器 為記錄所存儲這個字符的編碼 當有相同編碼時m值加1 當輸入的字符串與所存儲的編碼字 把已經(jīng)使用過的 code 數(shù)組里的 void main() int n=26,i; char orz,back,flag=1; char str=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R, S,T,U,V,W,X,Y,Z; / 初始化 int fnum=,64,13,22,32,103

15、,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16 ; / 初始化 HTNode htM; / 建立結(jié)構(gòu)體 HCode hcdN; / 建立結(jié)構(gòu)體 for (i=0;in;i+) / 把初始化的數(shù)據(jù)存入 ht 結(jié)構(gòu)體中 hti.data=stri; hti.weight=fnumi; while (flag) / 菜單函數(shù)，當 flag 為 0 時跳出循環(huán) ( 5)顯示部分源程序： printf(n); printf( * ); 顯示編碼 *) 進行編碼 *) 進行譯碼 *) 退出 *n); printf(n* 1 printf(n*

16、 2 printf(n* 3 printf(n* 4 printf( * * ); printf(n); printf( 請輸入選擇的編號 :); scanf(%c, switch(orz) case a: 清屏函數(shù) case A: system(cls); / CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf(n 按任意鍵返回 .); getch(); system(cls); break; case b: case B: system(cls); printf( 請輸入要進行編碼的字符串 ( 以#結(jié)束 ):

17、n); editHCode(ht,hcd,n); printf(n 按任意鍵返回 .); getch(); system(cls); break; case c: case C: system(cls); DispHCode(ht,hcd,n); printf( 請輸入編碼 (以#結(jié)束 ):n); deHCode(ht,hcd,n); printf(n按任意鍵返回”); getch(); system(cls); break; case d: case D: flag=0; break; default: system(cls); 五、調(diào)試結(jié)果 進入主菜單 I 小 F； C+CTnTaii1b

18、3LnTwi:exa BSD1 耳車耳*上卓承*冀# -*-+ J*-4 Jlj|l 4lj|l 4uj|l 4lj|l 4沖事齊卓齊車齊卓#木克 A =+ H 顯示編碼+ -p exe I 7：0110010103 2： 110000 請輸入編碼（以牡結(jié)朿）：- klooooooii# 7T 按任胃鍵亟回 搜狗拼音半: 六、心得體會 通過這次課程設(shè)計，讓我對一個程序的數(shù)據(jù)結(jié)構(gòu)有更全面更進一步的認識，根據(jù) 不同的需求，采用不同的數(shù)據(jù)存儲方式，不一定要用棧，二叉樹等高級類型，有時用基本的一維數(shù)組，只要運用得當，也能達到相同的效果，甚至更佳，就如這 次的課程設(shè)計， 通過用 for 的多重循環(huán)， 舍

19、棄多余的循環(huán)， 提高了程序的運行效 率。在編寫這個程序的過程中， 我復習了之前學的基本語法， 哈弗曼樹最小路徑 的求取，哈弗曼編碼及譯碼的應用圍， 程序結(jié)構(gòu)算法等一系列的問題它使我對數(shù) 據(jù)結(jié)構(gòu)改變了看法。 在這次設(shè)計過程中， 體現(xiàn)出自己單獨設(shè)計模具的能力以及綜 合運用知識的能力， 體會了學以致用、 突出自己勞動成果的喜悅心情， 也從中發(fā) 現(xiàn)自己平時學習的不足和薄弱環(huán)節(jié)，從而加以彌補。 七、參考文獻 1 徐孝凱編著，數(shù)據(jù)結(jié)構(gòu)課程實驗 ，清華大學出版 2002 年第一版 2 乃笑編著，數(shù)據(jù)結(jié)構(gòu)與算法，電子工業(yè) 2004 年 10 月 3 嚴蔚敏 數(shù)據(jù)結(jié)構(gòu) (C語言版)清華大學 附錄： 源程序如下：

20、 #include #include / 要用 system 函數(shù)要調(diào)用的頭文件 #include / 用 getch() 要調(diào)用的頭文件 #include #define N 50 / 義用 N 表示 50 葉節(jié)點數(shù) #define M 2*N-1 / 用 M 表示節(jié)點總數(shù) 當葉節(jié)點數(shù)位 n 時總節(jié)點數(shù)為 2n-1 #define MAXSIZE 100 typedef struct 結(jié)點值 權(quán)值 雙親結(jié)點 左孩子結(jié)點 右孩子結(jié)點 存放哈夫曼碼 從 start 開始讀 cd 中的哈夫曼碼 char data;/ int weight;/ int parent;/ int lchild;/ i

21、nt rchild;/ HTNode; typedef struct char cdN; / int start; / HCode; void CreateHT(HTNode ht,int n) int i,k,lnode,rnode; / 調(diào)用輸入的數(shù)組 ht, 和節(jié)點數(shù) n int min1,min2; 所有結(jié)點的相關(guān)域置初值 for (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; / void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;

22、in;i+) hc.start=n;c=i; f=hti.parent; / 根據(jù)哈夫曼樹求哈夫曼編碼 while (f!=-1) if (htf.lchild=c) / 循序直到樹根結(jié)點結(jié)束循環(huán) / 處理左孩子結(jié)點 hc.cdhc.start-=0; else / 處理右孩子結(jié)點 hc.cdhc.start-=1; for (i=n;i2*n-1;i+) min1=min2=32767; lnode=rnode=-1; / /int /lnode for (k=0;k=i-1;k+) if (htk.parent=-1) / 找 if (htk.weightmin1)/ min2=min1;

23、rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; 父節(jié)點是 i / 構(gòu)造哈夫曼樹 的圍是 -32768 32767 和 rnode 記錄最小權(quán)值的兩個結(jié)點 只在尚未構(gòu)造二叉樹的結(jié)點中查 若權(quán)值小于最小的左節(jié)點的權(quán)值 hti.weight=htlnode.weight+htrnode.weight; / 兩個最小節(jié)點的 父節(jié)點權(quán)值為兩個最小節(jié)點權(quán)值之和 hti.lchild=lnode;hti.rchi

24、ld=rnode; / 父節(jié)點的左節(jié)點 和右節(jié)點 兩個最小節(jié)點的 c=f;f=htf.parent; 指向哈夫曼編碼 hc.cd 中最開 hc.start+; /start 始字符 hcdi=hc; 輸出哈夫曼編碼的列表 void DispHCode(HTNode ht,HCode hcd,int n) / int i,k; printf( 輸出哈夫曼編碼 :n); 輸出 data 中的所有數(shù)據(jù)，即 A-Z 輸出所有 data 中數(shù)據(jù)的編碼 for (i=0;in;i+) / printf( %c:t,hti.data); for (k=hcdi.start;k=n;k+)/ printf(%

25、c,hcdi.cdk); printf(n); 編碼函數(shù) void editHCode(HTNode ht,HCode hcd,int n) / char stringMAXSIZE; int i,j,k; 把要進行編碼的字符串存入 string 為終止標志 scanf(%s,string); / 數(shù)組中 printf(n 輸出編碼結(jié)果 :n); for (i=0;stringi!=#;i+) /# for (j=0;jn;j+) 循環(huán)查找與輸入字符相同的編 if(stringi=htj.data) / 號，相同的就輸出這個字符的編碼 for (k=hcdj.start;k=n;k+) pri

26、ntf(%c,hcdj.cdk); 輸出完成后跳出當前 for 循環(huán) break; / void deHCode(HTNode ht,HCode hcd,int n) / char codeMAXSIZE; int i,j,l,k,m,x; scanf(%s,code); / 組中 while(code0!=#) for (i=0;in;i+) m=0; /m for (k=hcdi.start,j=0;k=n;k+,j+) /j 個數(shù) if(codej=hcdi.cdk) / m+; if(m=j) / 符串個數(shù)相等時則輸出這個的 data 數(shù)據(jù) printf(%c,hti.data); for(x=0;codex-1!=#;x+) / 字符串刪除 codex=codex+j; 譯碼函數(shù) 把要進行譯碼的字符串存入 code 數(shù) 為想同編碼個數(shù)的計數(shù)器 為記錄所存儲這個字符的編碼 當有相同編碼時m值加1 當輸入的字符串與所存儲的編碼字 把已經(jīng)使用過的 code 數(shù)組里的 void main() int n=26,i; char orz,back,flag=1; char str=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R, S,T,U,V,W