哈夫曼編碼譯碼數據結構課程設計

1、數據結構課程設計題目：哈夫曼編碼譯碼姓名：專業(yè)：通信工程學號：指導教師：吳澤暉目錄目錄1一、需求分析2二、設計要求2三、概要設計21、流程圖22、設計包含的幾個部分4四、詳細設計2五、顯示結果9.六、心得體會10七、參考文獻11哈夫曼編碼譯碼一、 需求分析在當今信息爆炸時代，如何采用有效的數據壓縮技術節(jié)省數據文件的存儲空間和計算機網絡的傳送時間已越來越引起人們的重視，赫夫曼編碼正是一種應用廣泛且非常有效的數據壓縮技術。哈夫曼編碼是一種編碼方式，以哈夫曼樹即最優(yōu)二叉樹，帶權路徑長度最小的二叉樹，經常應用于數據壓縮。哈弗曼編碼使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個符號）進行編碼。這張編碼

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

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

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

5、）其主要流程圖如圖1-1所示。開始結點數是否大于1將data和權值賦給ht輸出根結點和權值調用SELECT函數計算根結點函數父結點為兩子結點之和輸出兩子結點和已構造的結點是否為根結點？左子是否為空？此時編碼為0I<2*N?I+編碼為1結束否否否右子是否為空是是否否是是是（2）設計包含的幾個方面： 赫夫曼樹的建立赫夫曼樹的建立由赫夫曼算法的定義可知，初始森林中共有n棵只含有根結點的二叉樹。算法的第二步是：將當前森林中的兩棵根結點權值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就減少一棵樹，產生一個新結點。顯然要進行n1次合并，所以共產生n1個新結點，它們都是具有兩個孩子的分支結點

6、。由此可知，最終求得的赫夫曼樹中一共有2n1個結點，其中n個結點是初始森林的n個孤立結點。并且赫夫曼樹中沒有度數為1的分支結點。我們可以利用一個大小為2n-1的一維數組來存儲赫夫曼樹中的結點。 赫夫曼編碼 要求電文的赫夫曼編碼，必須先定義赫夫曼編碼類型，根據設計要求和實際需要定義的類型如下： typedet struct char ch; / 存放編碼的字符 char bitsN1; / 存放編碼位串 int len; / 編碼的長度 CodeNode; / 編碼結構體類型 代碼文件的譯碼 譯碼的基本思想是：讀文件中編碼，并與原先生成的赫夫曼編碼表比較，遇到相等時，即取出其對應的字符存入一個新

7、串中。 四、 詳細設計（1）赫夫曼樹的存儲結構描述為： #define N 50 / 葉子結點數 #define M 2*N-1 / 赫夫曼樹中結點總數 typedef struct int weight; / 葉子結點的權值 int lchild, rchild, parent; / 左右孩子及雙親指針 HTNode; / 樹中結點類型 typedef HTNode HuffmanTreeM+1; 哈弗曼樹的算法void CreateHT(HTNode ht,int n) /調用輸入的數組ht,和節(jié)點數n int i,k,lnode,rnode; int min1,min2; for (i=

8、0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有結點的相關域置初值-1 for (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) /若權值小于最小的左節(jié)點的權值 min2=min1;rnode=lnode

9、; min1=htk.weight;lnode=k; else if (htk.weight<min2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /兩個最小節(jié)點的父節(jié)點是i hti.weight=htlnode.weight+htrnode.weight; /兩個最小節(jié)點的父節(jié)點權值為兩個最小節(jié)點權值之和 hti.lchild=lnode;hti.rchild=rnode; /父節(jié)點的左節(jié)點和右節(jié)點（2）哈弗曼編碼void CreateHCode(HTNode ht,HCode hcd,int n) int

10、i,f,c; HCode hc; for (i=0;i<n;i+) /根據哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結點結束循環(huán) 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 hc

11、d,int n) /輸出哈夫曼編碼的列表 int i,k; printf(" 輸出哈夫曼編碼:n"); for (i=0;i<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 stringMAX

12、SIZE; int i,j,k;scanf("%s",string); /把要進行編碼的字符串存入string數組中printf("n輸出編碼結果:n");for (i=0;stringi!='#'i+) /#為終止標志for (j=0;j<n;j+)if(stringi=htj.data) /循環(huán)查找與輸入字符相同的編號，相同的就輸出這個字符的編碼for (k=hcdj.start;k<=n;k+) printf("%c",hcdj.cdk);break; /輸出完成后跳出當前for循環(huán)（3）哈弗曼譯碼v

13、oid deHCode(HTNode ht,HCode hcd,int n) /譯碼函數char codeMAXSIZE;int i,j,l,k,m,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) /當輸入的字符串與所存儲的編碼字

14、符串個數相等時則輸出這個的data數據printf("%c",hti.data);for(x=0;codex-1!='#'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',&

15、#39;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; /建

16、立結構體 HCode hcdN; /建立結構體 for (i=0;i<n;i+) /把初始化的數據存入ht結構體中 hti.data=stri; hti.weight=fnumi; while (flag) /菜單函數，當flag為0時跳出循環(huán) （5）顯示部分源程序： printf("n"); printf(" *"); printf("n * 1-顯示編碼 *"); printf("n * 2-進行編碼 *"); printf("n * 3-進行譯碼 *"); printf("

17、n * 4-退出 *n"); printf(" * *"); printf("n"); printf(" 請輸入選擇的編號:"); scanf("%c",&orz); switch(orz) case 'a': case 'A': system("cls"); /清屏函數 CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf("n按任意鍵返回.")

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

19、ispHCode(ht,hcd,n); printf("請輸入編碼(以#結束):n"); deHCode(ht,hcd,n); printf("n按任意鍵返回."); getch(); system("cls"); break; case 'd': case 'D': flag=0; break; default: system("cls"); 五、調試結果進入主菜單選A時的顯示結果選擇B時的顯示結果選C時的顯示結果六、心得體會通過這次課程設計，讓我對一個程序的數據結構有更全面更進一

20、步的認識，根據不同的需求，采用不同的數據存儲方式，不一定要用棧，二叉樹等高級類型，有時用基本的一維數組，只要運用得當，也能達到相同的效果，甚至更佳，就如這次的課程設計，通過用for的多重循環(huán)，舍棄多余的循環(huán)，提高了程序的運行效率。在編寫這個程序的過程中，我復習了之前學的基本語法，哈弗曼樹最小路徑的求取，哈弗曼編碼及譯碼的應用范圍，程序結構算法等一系列的問題它使我對數據結構改變了看法。在這次設計過程中，體現出自己單獨設計模具的能力以及綜合運用知識的能力，體會了學以致用、突出自己勞動成果的喜悅心情，也從中發(fā)現自己平時學習的不足和薄弱環(huán)節(jié)，從而加以彌補。七、參考文獻1 徐孝凱編著，數據結構課程實驗，

21、清華大學出版 2002年第一版2 張乃笑編著，數據結構與算法，電子工業(yè)出版社 2004年10月3 嚴蔚敏 數據結構（C語言版） 清華大學出版社附錄：源程序如下：#include <stdio.h>#include <stdlib.h> /要用system函數要調用的頭文件#include<conio.h> /用getch()要調用的頭文件#include <string.h>#define N 50 /義用N表示50葉節(jié)點數#define M 2*N-1 /用M表示節(jié)點總數 當葉節(jié)點數位n時總節(jié)點數為2n-1#define MAXSIZE 100

22、typedef struct char data; /結點值 int weight; /權值 int parent; /雙親結點 int lchild; /左孩子結點 int rchild; /右孩子結點HTNode; typedef struct char cdN; /存放哈夫曼碼 int start; /從start開始讀cd中的哈夫曼碼HCode;void CreateHT(HTNode ht,int n) /調用輸入的數組ht,和節(jié)點數n int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti

23、.lchild=hti.rchild=-1; /所有結點的相關域置初值-1 for (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) /若權值小于最小的左節(jié)點的權值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else

24、 if (htk.weight<min2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /兩個最小節(jié)點的父節(jié)點是i hti.weight=htlnode.weight+htrnode.weight; /兩個最小節(jié)點的父節(jié)點權值為兩個最小節(jié)點權值之和 hti.lchild=lnode;hti.rchild=rnode; /父節(jié)點的左節(jié)點和右節(jié)點void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;i<n;i+) /根

25、據哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結點結束循環(huán) 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(&q

26、uot; 輸出哈夫曼編碼:n"); for (i=0;i<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",st

27、ring); /把要進行編碼的字符串存入string數組中printf("n輸出編碼結果:n");for (i=0;stringi!='#'i+) /#為終止標志for (j=0;j<n;j+)if(stringi=htj.data) /循環(huán)查找與輸入字符相同的編號，相同的就輸出這個字符的編碼for (k=hcdj.start;k<=n;k+) printf("%c",hcdj.cdk);break; /輸出完成后跳出當前for循環(huán)void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數cha

28、r codeMAXSIZE;int i,j,l,k,m,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.da

29、ta);for(x=0;codex-1!='#'x+) /把已經使用過的code數組里的字符串刪除codex=codex+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

30、','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結構體中 hti.data=stri; hti.weight=fnumi; while (flag) /菜單函數