1、精選文檔數 據 結 構 課 程 設 計設計題目： 哈夫曼樹編碼譯碼 課題名稱哈夫曼樹編碼譯碼院 系班級專業學 號姓 名成 績課題設計目的與設計意義1、課題設計目的：在當今信息爆炸時代，如何接受有效的數據壓縮技術節省數據文件的存儲空間和計算機網絡的傳送時間已越來越引起人們的重視，哈夫曼編碼正是一種應用廣泛且格外有效的數據壓縮技術。哈夫曼編碼是一種編碼方式，以哈夫曼樹即最優二叉樹，帶權路徑長度最小的二叉樹，經常應用于數據壓縮。哈弗曼編碼使用一張特殊的編碼表將源字符（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處在于，它是依據每一個源字符消滅的估算概率而建立起來的。2、課題設計意義：哈夫曼編

2、碼的應用很廣泛，利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支商定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個葉子對應的字符的編碼，這就是哈夫曼編碼。哈弗曼譯碼輸入字符串可以把它編譯成二進制代碼，輸入二進制代碼時可以編譯成字符串。指導老師：年 月 日目錄第一章 需求分析1其次章 設計要求1第三章 概要設計2（1）其主要流程圖如圖1-1所示。3（2）設計包含的幾個方面4第四章 具體設計4（1）哈夫曼樹的存儲結構描述為：4（2）哈弗曼編碼5（3）哈弗曼譯碼7（4）主函數8（5）顯示

3、部分源程序：8第五章 調試結果10第六章 心得體會12第七章 參考文獻12附錄：12第一章 需求分析在當今信息爆炸時代，如何接受有效的數據壓縮技術節省數據文件的存儲空間和計算機網絡的傳送時間已越來越引起人們的重視，哈夫曼編碼正是一種應用廣泛且格外有效的數據壓縮技術。哈夫曼編碼是一種編碼方式，以哈夫曼樹即最優二叉樹，帶權路徑長度最小的二叉樹，經常應用于數據壓縮。哈弗曼編碼使用一張特殊的編碼表將源字符（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處在于，它是依據每一個源字符消滅的估算概率而建立起來的（消滅概率高的字符使用較短的編碼，反之消滅概率低的則使用較長的編碼，這便使編碼之后的字符串的

4、平均期望長度降低，從而達到無損壓縮數據的目的）。哈夫曼編碼的應用很廣泛，利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支商定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個葉子對應的字符的編碼，這就是哈夫曼編碼。哈弗曼譯碼輸入字符串可以把它編譯成二進制代碼，輸入二進制代碼時可以編譯成字符串。其次章 設計要求對輸入的一串電文字符實現哈夫曼編碼，再對哈夫曼編碼生成的代碼串進行譯碼，輸出電文字符串。通常我們把數據壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進制碼形式的字

5、符串。但在信息傳遞時，總期望總長度能盡可能短，即接受最短碼。假設每種字符在電文中消滅的次數為Wi，編碼長度為Li，電文中有n種字符，則電文編碼總長度為WiLi。若將此對應到二叉樹上，Wi為葉結點的權，Li為根結點到葉結點的路徑長度。那么，WiLi恰好為二叉樹上帶權路徑長度。因此 ，設計電文總長最短的二進制前綴編碼，就是以n種字符消滅的頻率作權，構造一棵哈夫曼樹，此構造過程稱為哈夫曼編碼。設計實現的功能： (1) 哈夫曼樹的建立； (2) 哈夫曼編碼的生成； (3) 編碼文件的譯碼。第三章 概要設計哈夫曼編譯碼器的主要功能是先建立哈夫曼樹，然后利用建好的哈夫曼樹生成哈夫曼編碼后進行譯碼 。在數據

6、通信中，經常需要將傳送的文字轉換成由二進制字符0、1組成的二進制串，稱之為編碼。構造一棵哈夫曼樹，規定哈夫曼樹中的左分之代表0，右分支代表1，則從根節點到每個葉子節點所經過的路徑分支組成的0和1的序列便為該節點對應字符的編碼，稱之為哈夫曼編碼。最簡潔的二進制編碼方式是等長編碼。若接受不等長編碼，讓消滅頻率高的字符具有較短的編碼，讓消滅頻率低的字符具有較長的編碼，這樣可能縮短傳送電文的總長度。哈夫曼樹課用于構造使電文的編碼總長最短的編碼方案。（1）其主要流程圖如圖1-1所示。開頭結束結點數是否大于1將data和權值賦給ht輸出根結點和權值調用SELECT函數計算根結點函數雙親結點為兩子結點之和輸

7、出兩子結點和已構造的結點是否為根結點？左子是否為空？此時編碼為0I<2*N?I+編碼為1否否否右子是否為空是是否否是是是（2）設計包含的幾個方面： 哈夫曼樹的建立哈夫曼樹的建立由哈夫曼算法的定義可知，初始森林中共有n棵只含有根結點的二叉樹。算法的其次步是：將當前森林中的兩棵根結點權值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就削減一棵樹，產生一個新結點。明顯要進行n1次合并，所以共產生n1個新結點，它們都是具有兩個孩子的分支結點。由此可知，最終求得的哈夫曼樹中一共有2n1個結點，其中n個結點是初始森林的n個孤立結點。并且哈夫曼樹中沒有度數為1的分支結點。我們可以利用一個大小為

8、2n-1的一維數組來存儲哈夫曼樹中的結點。 哈夫曼編碼 要求電文的哈夫曼編碼，必需先定義哈夫曼編碼類型，依據設計要求和實際需要定義的類型如下： typedet struct char ch; / 存放編碼的字符 char bitsN1; / 存放編碼位串 int len; / 編碼的長度 CodeNode; / 編碼結構體類型 代碼文件的譯碼 譯碼的基本思想是：讀文件中編碼，并與原先生成的哈夫曼編碼表比較，遇到相等時，即取出其對應的字符存入一個新串中。 第四章 具體設計（1）哈夫曼樹的存儲結構描述為： #define N 50 / 葉子結點數 #define M 2*N-1 / 哈夫曼樹中結點

9、總數 typedef struct int weight; / 葉子結點的權值 int lchild, rchild, parent; / 左右孩子及雙親指針 HTNode; / 樹中結點類型 typedef HTNode HuffmanTreeM+1; 哈弗曼樹的算法void CreateHT(HTNode ht,int n) /調用輸入的數組ht,和節點數n int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /全部結點的相關域置初值-1 for (

10、i=n;i<2*n-1;i+) /構造哈夫曼樹 min1=min2=32767; /int的范圍是-3276832767 lnode=rnode=-1; /lnode和rnode記錄最小權值的兩個結點位置 for (k=0;k<=i-1;k+) if (htk.parent=-1) /只在尚未構造二叉樹的結點中查找 if (htk.weight<min1) /若權值小于最小的左節點的權值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weight<min2) min2=htk.weight;rn

11、ode=k; htlnode.parent=i;htrnode.parent=i; /兩個最小節點的父節點是i hti.weight=htlnode.weight+htrnode.weight; /兩個最小節點的父節點權值為兩個最小節點權值之和 hti.lchild=lnode;hti.rchild=rnode; /父節點的左節點和右節點（2）哈弗曼編碼void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;i<n;i+) /依據哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.p

12、arent; while (f!=-1) /循序直到樹根結點結束循環 if (htf.lchild=c) /處理左孩子結點 hc.cdhc.start-='0' else /處理右孩子結點 hc.cdhc.start-='1' c=f;f=htf.parent; hc.start+; /start指向哈夫曼編碼hc.cd中最開頭字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /輸出哈夫曼編碼的列表 int i,k; printf(" 輸出哈夫曼編碼:n"); for (i=0;i&l

13、t;n;i+) /輸出data中的全部數據，即A-Z printf(" %c:t",hti.data); for (k=hcdi.start;k<=n;k+) /輸出全部data中數據的編碼 printf("%c",hcdi.cdk); printf("n"); void editHCode(HTNode ht,HCode hcd,int n) /編碼函數char stringMAXSIZE; int i,j,k;scanf("%s",string); /把要進行編碼的字符串存入string數組中printf

14、("n輸出編碼結果:n");for (i=0;stringi!='#'i+) /#為終止標志for (j=0;j<n;j+)if(stringi=htj.data) /循環查找與輸入字符相同的編號，相同的就輸出這個字符的編碼for (k=hcdj.start;k<=n;k+) printf("%c",hcdj.cdk);break; /輸出完成后跳出當前for循環（3）哈弗曼譯碼void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數char codeMAXSIZE;int i,j,l,k,m

15、,x;scanf("%s",code); /把要進行譯碼的字符串存入code數組中while(code0!='#')for (i=0;i<n;i+)m=0; /m為想同編碼個數的計數器 for (k=hcdi.start,j=0;k<=n;k+,j+) /j為記錄所存儲這個字符的編碼個數if(codej=hcdi.cdk) /當有相同編碼時m值加1m+;if(m=j) /當輸入的字符串與所存儲的編碼字符串個數相等時則輸出這個的data數據printf("%c",hti.data);for(x=0;codex-1!='#

16、'x+) /把已經使用過的code數組里的字符串刪除codex=codex+j;（4）主函數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',

17、9;Q','R','S','T','U','V','W','X','Y','Z' /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立結構體 HCode hcdN; /建立結構體 for (i=0;i<n;i+) /把初始化的數據存入ht結構體中 hti.data=stri

18、; hti.weight=fnumi; while (flag) /菜單函數，當flag為0時跳出循環 （5）顯示部分源程序： printf("n"); printf(" *"); printf("n * 1-顯示編碼 *"); printf("n * 2-進行編碼 *"); printf("n * 3-進行譯碼 *"); printf("n * 4-退出 *n"); printf(" * *"); printf("n"); print

19、f(" 請輸入選擇的編號:"); scanf("%c",&orz); switch(orz) case 'a': 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&#

20、39;: system("cls"); printf("請輸入要進行編碼的字符串(以#結束):n"); editHCode(ht,hcd,n); printf("n按任意鍵返回."); getch(); system("cls"); break; case 'c': case 'C': system("cls"); DispHCode(ht,hcd,n); printf("請輸入編碼(以#結束):n"); deHCode(ht,hcd,n);

21、printf("n按任意鍵返回."); getch(); system("cls"); break; case 'd': case 'D': flag=0; break; default: system("cls"); 第五章 調試結果進入主菜單選A時的顯示結果選擇B時的顯示結果選C時的顯示結果第六章 心得體會通過這次課程設計，讓我對一個程序的數據結構有更全面更進一步的生疏，依據不同的需求，接受不同的數據存儲方式，不肯定要用棧，二叉樹等高級類型，有時用基本的一維數組，只要運用得當，也能達到相同的效果，甚

22、至更佳，就如這次的課程設計，通過用for的多重循環，舍棄多余的循環，提高了程序的運行效率。在編寫這個程序的過程中，我復習了之前學的基本語法，哈弗曼樹最小路徑的求取，哈弗曼編碼及譯碼的應用范圍，程序結構算法等一系列的問題它使我對數據結構轉變了看法。在這次設計過程中，體現出自己單獨設計模具的力量以及綜合運用學問的力量，體會了學以致用、突出自己勞動成果的喜悅心情，也從中發覺自己平常學習的不足和薄弱環節，從而加以彌補。第七章 參考文獻1 徐孝凱編著，數據結構課程試驗，清華高校出版 2002年第一版2 張乃笑編著，數據結構與算法，電子工業出版社 2004年10月3 嚴蔚敏 數據結構（C語言版） 清華高校

23、出版社附錄：源程序如下：#include <stdio.h>#include <stdlib.h> /要用system函數要調用的頭文件#include<conio.h> /用getch()要調用的頭文件#include <string.h>#define N 50 /義用N表示50葉節點數#define M 2*N-1 /用M表示節點總數 當葉節點數位n時總節點數為2n-1#define MAXSIZE 100typedef struct char data; /結點值 int weight; /權值 int parent; /雙親結點 int

24、 lchild; /左孩子結點 int rchild; /右孩子結點HTNode; typedef struct char cdN; /存放哈夫曼碼 int start; /從start開頭讀cd中的哈夫曼碼HCode;void CreateHT(HTNode ht,int n) /調用輸入的數組ht,和節點數n int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /全部結點的相關域置初值-1 for (i=n;i<2*n-1;i+) /構造哈夫曼

25、樹 min1=min2=32767; /int的范圍是-3276832767 lnode=rnode=-1; /lnode和rnode記錄最小權值的兩個結點位置 for (k=0;k<=i-1;k+) if (htk.parent=-1) /只在尚未構造二叉樹的結點中查找 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;h

26、trnode.parent=i; /兩個最小節點的父節點是i hti.weight=htlnode.weight+htrnode.weight; /兩個最小節點的父節點權值為兩個最小節點權值之和 hti.lchild=lnode;hti.rchild=rnode; /父節點的左節點和右節點void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;i<n;i+) /依據哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結點結束循

27、環 if (htf.lchild=c) /處理左孩子結點 hc.cdhc.start-='0' else /處理右孩子結點 hc.cdhc.start-='1' c=f;f=htf.parent; hc.start+; /start指向哈夫曼編碼hc.cd中最開頭字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /輸出哈夫曼編碼的列表 int i,k; printf(" 輸出哈夫曼編碼:n"); for (i=0;i<n;i+) /輸出data中的全部數據，即A-Z printf

28、(" %c:t",hti.data); for (k=hcdi.start;k<=n;k+) /輸出全部data中數據的編碼 printf("%c",hcdi.cdk); printf("n"); void editHCode(HTNode ht,HCode hcd,int n) /編碼函數char stringMAXSIZE; int i,j,k;scanf("%s",string); /把要進行編碼的字符串存入string數組中printf("n輸出編碼結果:n");for (i=0;

29、stringi!='#'i+) /#為終止標志for (j=0;j<n;j+)if(stringi=htj.data) /循環查找與輸入字符相同的編號，相同的就輸出這個字符的編碼for (k=hcdj.start;k<=n;k+) printf("%c",hcdj.cdk);break; /輸出完成后跳出當前for循環void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數char codeMAXSIZE;int i,j,l,k,m,x;scanf("%s",code); /把要進行譯碼的字符

30、串存入code數組中while(code0!='#')for (i=0;i<n;i+)m=0; /m為想同編碼個數的計數器 for (k=hcdi.start,j=0;k<=n;k+,j+) /j為記錄所存儲這個字符的編碼個數if(codej=hcdi.cdk) /當有相同編碼時m值加1m+;if(m=j) /當輸入的字符串與所存儲的編碼字符串個數相等時則輸出這個的data數據printf("%c",hti.data);for(x=0;codex-1!='#'x+) /把已經使用過的code數組里的字符串刪除codex=codex

31、+j;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=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立結構體 HCode hcdN; /建立結構體 for (i=0;i<n;i+) /把初始化的數據存入ht結