數(shù)據(jù)結(jié)構(gòu)課程設計 赫夫曼編碼系統(tǒng)

1、 東華理工大學課程設計報告課程設計題目 ： 赫夫曼編碼系統(tǒng) 學生姓名 ： 安國棟專 業(yè) ： 計算機科學與技術(shù) 班 級 ： 1320701學 號 ： 201320070105指導教師 ： 劉志峰 2014年 06 月 19 日目 錄1、 設計要求-2二、存儲結(jié)構(gòu)-2三、設計思想-21、設計包含的幾個部分-22、流程圖-3四、詳細設計-4五、算法復雜度分析-8六、顯示結(jié)果-9七、心得體會-11八、附錄：源程序代碼-11一、設計要求赫夫曼樹任務 ：建立建立最優(yōu)二叉樹函數(shù) 要求：可以建立函數(shù)輸入二叉樹，實現(xiàn)赫夫曼樹的編碼和譯碼系統(tǒng)，重復地顯示并處理編碼/解碼功能，直到選擇退出為止。二、存儲結(jié)構(gòu)：在本次

2、課程設計中，每一個字符的信息用一個結(jié)構(gòu)體存儲，包含結(jié)點值、權(quán)值、雙親結(jié)點、左孩子結(jié)點、右孩子結(jié)點等數(shù)據(jù)。赫夫曼碼和所有字符都是用一個一維數(shù)組建立存儲的，所以本次課程設計的存儲結(jié)構(gòu)是順序存儲。三、設計思想哈夫曼編譯碼系統(tǒng)的主要功能是先建立哈夫曼樹，然后利用建好的哈夫曼樹生成哈夫曼編碼后進行譯碼 。在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進制字符0、1組成的二進制串，稱之為編碼。構(gòu)造一棵哈夫曼樹，規(guī)定哈夫曼樹中的左分之代表0，右分支代表1，則從根節(jié)點到每個葉子節(jié)點所經(jīng)過的路徑分支組成的0和1的序列便為該節(jié)點對應字符的編碼，稱之為哈夫曼編碼。最簡單的二進制編碼方式是等長編碼。若采用不等長編碼，讓

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

4、可以利用一個大小為2n-1的一維數(shù)組來存儲赫夫曼樹中的結(jié)點。 赫夫曼編碼 要求電文的赫夫曼編碼，必須先定義赫夫曼編碼類型，根據(jù)設計要求和實際需要定義的類型如下： typedet struct char ch; / 存放編碼的字符 char bitsN1; / 存放編碼位串 int len; / 編碼的長度 CodeNode; / 編碼結(jié)構(gòu)體類型 代碼文件的譯碼 譯碼的基本思想是：讀文件中編碼，并與原先生成的赫夫曼編碼表比較，遇到相等時，即取出其對應的字符存入一個新串中。（2）其主要流程圖如圖所示。開始結(jié)點數(shù)是否大于1將data和權(quán)值賦給ht輸出根結(jié)點和權(quán)值調(diào)用SELECT函數(shù)計算根結(jié)點函數(shù)父結(jié)

5、點為兩子結(jié)點之和輸出兩子結(jié)點和已構(gòu)造的結(jié)點是否為根結(jié)點？左子是否為空？此時編碼為0I<2*N?I+編碼為1結(jié)束否否否右子是否為空是是否否是是是四、詳細設計（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; / 左右孩子及雙親指針 HTNode; / 樹中結(jié)點類型 typedef HTNode HuffmanTreeM+1; 哈弗曼樹的算法void CreateHT(HTNode h

6、t,int n) /調(diào)用輸入的數(shù)組ht,和節(jié)點數(shù)n int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有結(jié)點的相關(guān)域置初值-1 for (i=n;i<2*n-1;i+) /構(gòu)造哈夫曼樹 min1=min2=32767; /int的范圍是-3276832767 lnode=rnode=-1; /lnode和rnode記錄最小權(quán)值的兩個結(jié)點位置 for (k=0;k<=i-1;k+) if (htk.parent=-1) /只在尚未構(gòu)造二叉

7、樹的結(jié)點中查找 if (htk.weight<min1) /若權(quán)值小于最小的左節(jié)點的權(quán)值 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; /兩個最小節(jié)點的父節(jié)點是i hti.weight=htlnode.weight+htrnode.weight; /兩個最小節(jié)點的父節(jié)點權(quán)值為兩個最小節(jié)點權(quán)值之和 hti.lchild=lnode;hti.rchild=rnode;

8、 /父節(jié)點的左節(jié)點和右節(jié)點（2）哈弗曼編碼void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;i<n;i+) /根據(jù)哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結(jié)點結(jié)束循環(huán) if (htf.lchild=c) /處理左孩子結(jié)點 hc.cdhc.start-='0' else /處理右孩子結(jié)點 hc.cdhc.start-='1' c=f;f=htf.parent; hc.start+

9、; /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中的所有數(shù)據(jù)，即A-Z printf(" %c:t",hti.data); for (k=hcdi.start;k<=n;k+) /輸出所有data中數(shù)據(jù)的編碼 printf("%c",hcdi.cdk); printf("n&

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

11、n;k+) printf("%c",hcdj.cdk);break; /輸出完成后跳出當前for循環(huán)（3）哈弗曼譯碼void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數(shù)char codeMAXSIZE;int i,j,l,k,m,x;scanf("%s",code); /把要進行譯碼的字符串存入code數(shù)組中while(code0!='#')for (i=0;i<n;i+)m=0; /m為想同編碼個數(shù)的計數(shù)器 for (k=hcdi.start,j=0;k<=n;k+,j+) /j為記錄所

12、存儲這個字符的編碼個數(shù)if(codej=hcdi.cdk) /當有相同編碼時m值加1m+;if(m=j) /當輸入的字符串與所存儲的編碼字符串個數(shù)相等時則輸出這個的data數(shù)據(jù)printf("%c",hti.data);for(x=0;codex-1!='#'x+) /把已經(jīng)使用過的code數(shù)組里的字符串刪除codex=codex+j;（4）主函數(shù)void main() int n=26,i; char orz,back,flag=1; char str='a','b','c','d','

13、;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,

14、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;i<n;i+) /把初始化的數(shù)據(jù)存入ht結(jié)構(gòu)體中 hti.data=stri; hti.weight=fnumi; while (flag) /菜單函數(shù)，當flag為0時跳出循環(huán) （5）顯示部分源程序： printf(" 歡迎使用赫夫曼編譯系統(tǒng) n"); printf(" *n"); printf(" 1：顯示編碼n "); p

15、rintf(" 2：進行編碼n"); printf(" 3：進行譯碼n"); printf(" 0：退出n"); printf(" *n"); printf(" 請輸入選擇的編號:"); scanf("%c",&orz); switch(orz) case '1': system("cls"); /清屏函數(shù) CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); pri

16、ntf("n按任意鍵返回."); getch(); system("cls"); break; case '2': system("cls"); printf("請輸入要進行編碼的字符串(以#結(jié)束,字符為小寫英文字母):n"); editHCode(ht,hcd,n); printf("n按任意鍵返回."); getch(); system("cls"); break; case '3': system("cls"); Di

17、spHCode(ht,hcd,n); printf("請輸入編碼(以#結(jié)束):n"); deHCode(ht,hcd,n); printf("n按任意鍵返回."); getch(); system("cls"); break; case '0': flag=0; printf(" 感謝您的使用！ n"); break; default: system("cls"); 五、算法復雜度分析：void editHCode(HTNode ht,HCode hcd,int n) /編碼函數(shù)

18、void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數(shù)這兩個被調(diào)函數(shù)里面都用了三重循環(huán)，其他的調(diào)用函數(shù)或者主函數(shù)都是一重或二重循環(huán)，所以算法復雜度為o(n3)?？梢钥闯龃怂惴ㄐ适潜容^低的，希望能夠找出更好的算法來減小復雜度。六、調(diào)試結(jié)果進入主菜單選1時的顯示結(jié)果選擇2時的顯示結(jié)果選3時的顯示結(jié)果七、心得體會通過這次課程設計，讓我對一個程序的數(shù)據(jù)結(jié)構(gòu)有更全面更進一步的認識，根據(jù)不同的需求，采用不同的數(shù)據(jù)存儲方式，不一定要用棧，二叉樹等高級類型，有時用基本的一維數(shù)組，只要運用得當，也能達到相同的效果，甚至更佳，就如這次的課程設計，通過用for的多重循環(huán)，舍棄多

19、余的循環(huán)，提高了程序的運行效率。在編寫這個程序的過程中，我復習了之前學的基本語法，哈弗曼樹最小路徑的求取，哈弗曼編碼及譯碼的應用范圍，程序結(jié)構(gòu)算法等一系列的問題它使我對數(shù)據(jù)結(jié)構(gòu)改變了看法。在這次設計過程中，體現(xiàn)出自己單獨設計模具的能力以及綜合運用知識的能力，體會了學以致用、突出自己勞動成果的喜悅心情，也從中發(fā)現(xiàn)自己平時學習的不足和薄弱環(huán)節(jié)，從而加以彌補。八、附錄：源程序代碼源程序如下：#include <stdio.h>#include <stdlib.h> /要用system函數(shù)要調(diào)用的頭文件#include<conio.h> /用getch()要調(diào)用的頭

20、文件#include <string.h>#define N 50 /義用N表示50葉節(jié)點數(shù)#define M 2*N-1 /用M表示節(jié)點總數(shù) 當葉節(jié)點數(shù)位n時總節(jié)點數(shù)為2n-1#define MAXSIZE 100typedef struct char data; /結(jié)點值 int weight; /權(quán)值 int parent; /雙親結(jié)點 int lchild; /左孩子結(jié)點 int rchild; /右孩子結(jié)點HTNode; typedef struct char cdN; /存放哈夫曼碼 int start; /從start開始讀cd中的哈夫曼碼HCode;void Cre

21、ateHT(HTNode ht,int n) /調(diào)用輸入的數(shù)組ht,和節(jié)點數(shù)n int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有結(jié)點的相關(guān)域置初值-1 for (i=n;i<2*n-1;i+) /構(gòu)造哈夫曼樹 min1=min2=32767; /int的范圍是-32768-32767 lnode=rnode=-1; /lnode和rnode記錄最小權(quán)值的兩個結(jié)點位置 for (k=0;k<=i-1;k+) if (htk.paren

22、t=-1) /只在尚未構(gòu)造二叉樹的結(jié)點中查找 if (htk.weight<min1) /若權(quán)值小于最小的左節(jié)點的權(quán)值 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; /兩個最小節(jié)點的父節(jié)點是i hti.weight=htlnode.weight+htrnode.weight; /兩個最小節(jié)點的父節(jié)點權(quán)值為兩個最小節(jié)點權(quán)值之和 hti.lchild=lnode;ht

23、i.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+) /根據(jù)哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結(jié)點結(jié)束循環(huán) if (htf.lchild=c) /處理左孩子結(jié)點 hc.cdhc.start-='0' else /處理右孩子結(jié)點 hc.cdhc.start-='1' c=f;f=htf.parent; hc

24、.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中的所有數(shù)據(jù)，即A-Z printf(" %c:t",hti.data); for (k=hcdi.start;k<=n;k+) /輸出所有data中數(shù)據(jù)的編碼 printf("%c",hcdi.cdk); printf(&

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

26、;k<=n;k+) printf("%c",hcdj.cdk);break; /輸出完成后跳出當前for循環(huán)void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數(shù)char codeMAXSIZE;int i,j,l,k,m,x;scanf("%s",code); /把要進行譯碼的字符串存入code數(shù)組中while(code0!='#')for (i=0;i<n;i+)m=0; /m為想同編碼個數(shù)的計數(shù)器 for (k=hcdi.start,j=0;k<=n;k+,j+) /j為記錄所存

27、儲這個字符的編碼個數(shù)if(codej=hcdi.cdk) /當有相同編碼時m值加1m+;if(m=j) /當輸入的字符串與所存儲的編碼字符串個數(shù)相等時則輸出這個的data數(shù)據(jù)printf("%c",hti.data);for(x=0;codex-1!='#'x+) /把已經(jīng)使用過的code數(shù)組里的字符串刪除codex=codex+j;void main() int n=26,i; char orz,back,flag=1; char str='a','b','c','d','e'

28、,'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; /建立結(jié)構(gòu)體 HCode hcdN; /建立結(jié)構(gòu)體 for (i=0;i<n;i+) /把初始化的數(shù)據(jù)存入ht結(jié)構(gòu)體中 hti.data=stri; hti.weight=fnumi; while (flag) /菜單函數(shù)，當flag為0時跳出循環(huán) printf(" 歡迎使用赫夫曼編譯系統(tǒng) n"); printf(" *n&quo