14251102202陳曉俊哈夫曼樹編碼解碼

1、 課程設計課程名稱數(shù) 據(jù) 結 構班級與班級代碼14計算機2班，142511022專 業(yè)計 算 機 科 學 與 技 術指導教師羅 勇學 名陳曉俊電子郵箱827381654提交日期2016年6月29日廣東財經大學教務處 制哈夫曼樹編碼解碼1任務和要求哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權路徑長度最短的二叉樹。利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。既然要設計哈夫曼樹編碼來進行通訊傳輸,那么就必須有一套哈夫曼樹解碼。通過對哈夫曼樹編碼解碼的分析，此實驗應該包含如下要求：（1）設計一組字符和字符出現(xiàn)的頻率，即字符的權重，生成哈夫

2、曼樹；（2）利用哈夫曼樹求出所對應的哈夫曼樹編碼；（3）打印所有字符以及所對應的哈夫曼編碼，并顯示平均編碼長度；（4）利用哈夫曼樹解碼原理編寫解碼函數(shù)，由哈夫曼編碼求解出所對應的字符；（5）顯示所有哈夫曼編碼及其所對應的字符；（6）對比分析編碼解碼的正確性；2總體設計2.1系統(tǒng)功能模塊圖：圖一初始化哈夫曼樹構造哈夫曼編碼構造哈夫曼樹打印哈夫曼編碼哈夫曼樹譯碼打印哈夫曼樹打印哈夫曼譯碼主函數(shù)2.2哈夫曼樹的特點：哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權路徑長度最短的二叉樹，權值較大的結點離根較近。2.3哈夫曼樹的構造過程：步驟1：根據(jù)給定的n個權值w1,w2,wn，構造n棵只有根節(jié)點的二叉樹，這n棵二

3、叉樹構成一個森林f。步驟2：在森林f中選擇兩棵根節(jié)點權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的權值為其左右子樹上的根節(jié)點的權值之和。步驟3：在森林f中刪除這兩棵樹，同時將新得到的二叉樹放入到f中。步驟4：重復步驟2和步驟3，知道f中只有一棵二叉樹為止。2.4哈夫曼樹的編碼相關性質：性質1：哈夫曼編碼是前綴編碼性質2：哈夫曼編碼是最優(yōu)前綴編碼2.5哈夫曼樹的編碼過程：依次以葉子為出發(fā)點，向上回溯至根節(jié)點為止。回溯時走作分支則生成代碼0，走右分支則生成代碼1。3.詳細設計3.1詳細的涉及思路（1） 采用的節(jié)點類型：哈夫曼樹的節(jié)點又四個類型，包括節(jié)點的權值weight、雙親節(jié)點pa

4、rent、左孩子節(jié)點lchild、右孩子節(jié)點rchild。采用的邏輯結構：哈夫曼樹為最優(yōu)二叉樹，其采用的邏輯結構為樹狀結構。采用的存儲結構：由于哈夫曼樹中沒有度為1的節(jié)點，則一棵有n個節(jié)點的哈夫曼樹共有2n-1個節(jié)點，可以存儲在一個大小為2n-1的一維數(shù)組中。樹中沒個節(jié)點還要包含其雙親信息和孩子節(jié)點的信息，因此，每個節(jié)點的存儲結構如下表一所示，哈夫曼樹的結構體如下面所示的結構體。表一weightparentlchildrchild/-哈夫曼樹的存儲表示-typedef structchar data5;/定義節(jié)點值double weight;/節(jié)點的權重int parent,lchild,rc

5、hild; /定義哈夫曼樹的雙親節(jié)點、左右孩子節(jié)點htnode，*huffmantree;/動態(tài)分配數(shù)組存儲哈夫曼樹采用的算法：本系統(tǒng)采用的算法為哈夫曼算法。3.2哈夫曼樹編碼解碼詳細的構造過程（1）設計如下字符權重表（即26字權重表） 表二字符abcdefghij權重121323156724369010019字符klmnopqrst權重391392343578895714589029字符uvwxyz權重701234561189111（2）根據(jù)字符權重表，利用哈夫曼算法構造哈夫曼數(shù)。下面取圖三表格中的前面10個字符權重進行構造哈夫曼樹的思路說明。注：全部字符的構造與實現(xiàn)將在程序中體現(xiàn)！步驟1：

6、根據(jù)給定的10個字符權值，構造10棵只有根節(jié)點的二叉樹，這10棵二叉樹構成一個森林f。1213231567森林f19100903624步驟2：在森林f中選擇兩棵根節(jié)點權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的權值為其左右子樹上的根節(jié)點的權值之和。如下圖a251213圖a步驟3：在森林f中刪除這兩棵樹，同時將新得到的二叉樹放入到f中。如下圖b36246715232519100901312圖b步驟4：重復步驟2和步驟3，知道f中只有一棵二叉樹為止。最后得到如圖四的哈夫曼樹。圖四1733992268390100126364759672324253412131519（3）哈夫曼樹編碼

7、原理及其算法： 哈夫曼編碼是指利用哈夫曼樹求得的用于通信的二進制編碼。樹中從根到每個葉子節(jié)點都有一條路徑，對路徑上的各分支約定指向左子樹的分支表示”0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為各個葉子節(jié)點對應的字符編碼，這就是哈夫曼編碼原理。例如上圖四的哈夫曼樹的編碼如下頁圖五所示，圖五即為哈夫曼樹的編碼原理，編碼是從葉子節(jié)點開始編起，往根節(jié)點回溯的過程。圖五1733992268390100126364759672324253412131519000101011010110011abdjcfgehi 所以，圖五中字符的二進制哈夫曼編碼如下表三：字符abcdefg

8、hij哈夫曼編碼00011100110100010111111100000100111011表三表四為26個字母經過哈夫曼樹的構造、編碼得到的二進制編碼：字符abcdefghij權重1100000100010000101111000100100011110000100111101110011110101110字符klmnopqrst權重010110001011010011100101001100110001010010000101字符uvwxyz權重001100000111110000000110111001表四（4） 哈夫曼樹解碼原理：首先得知道編碼用的哈夫曼樹以及字符對應的二進制編碼如圖五

9、。然后從哈夫曼樹的根結點出發(fā)，逐個讀入文件中的二進制碼；若代碼為“0”，則走左子樹的根結點，否則走向右子樹的根結點；一旦到達葉子結點，便譯出代碼所對應的字符。然后又重新從根結點開始繼續(xù)譯碼，直到二進制文件結束。例如我想要對如下表五語句進行編碼解碼：表五canyougivemeakiss那么，得到的語句的二進制編碼為下表六：表六canyougivemeakiss0101111110000010011100110101010001100011110111100000001111010001100011010110011111010解碼只需發(fā)送上面表六的二進制編碼進行解析即可得到:can you g

10、ive me a kiss 這一語句。4 編碼4.1 數(shù)據(jù)結構定義本實驗所用的數(shù)據(jù)結構定義如下：typedef struct char ch; int weight; /權值，這個字符出現(xiàn)的頻率 int parent; /父節(jié)點 int left; /左孩子 int right; / 右孩子huffnode; typedef struct char codemaxnum; int start; huffcode; huffnode htmaxnum*2; /存放哈夫曼樹 huffcode hcdmaxnum; /存放ht數(shù)組中對應的字符的編碼4.2 項目結構圖4.3 功能函數(shù)的設計void c

11、hushihuaht(); /初始化哈夫曼樹htvoid gouzaoht(); /構造哈夫曼樹,看成有n棵樹，選擇權值最小的兩棵樹合并void gouzaohtcode(); /哈夫曼編碼，通過父節(jié)點從下往上找，輸出哈夫曼編碼平均長度int jiemaht(char *str,char* code); /哈夫曼解碼，每次都從根節(jié)點開始搜索void fanzhuan(char *str); /將一個字符串反轉(將編碼從葉子節(jié)點開始編)void shurubainmacode(); /用戶輸入編碼字符,并將編碼字符及其編碼打印到文件當中void shurujiemacode(); /用戶輸入解碼

12、字串void main(); /主函數(shù)4.4 函數(shù)調用關系圖main.cppchushihuaht.cppfanzhuan.cppgouzaoht.cppshurubianmacode.cppgouzaohtcode.cppshurujiemacode.cppjiemaht.cppgouzaohtcode.cppshurujiemacode.cpp圖八4.5 程序實現(xiàn)/*全部代碼實現(xiàn)如下：*/#include #include #include #include/*定義最大長度為字符常量*/#define maxnum 60/*定義哈夫曼樹編碼解碼結構體*/typedef struct cha

13、r ch; int weight; /權值，這個字符出現(xiàn)的頻率 int parent; /父節(jié)點 int left; /左孩子 int right; /右孩子huffnode; typedef struct char codemaxnum; int start; huffcode;/*定義存放哈夫曼樹、哈夫曼編碼的全局變量*/extern huffnode htmaxnum*2; /存放哈夫曼樹 extern huffcode hcdmaxnum; /存放ht數(shù)組中對應的字符的編碼 extern int n; /字符的個數(shù)/*聲明函數(shù)*/void main();void chushihuaht

14、(); void gouzaoht();void fanzhuan(char *str);void gouzaohtcode();int jiemaht(char *str,char* code);void shurubainmacode();void shurujiemacode();/*下列為哈夫曼編碼解碼的主函數(shù)，該函數(shù)調用了chushihuaht()、gouzaoht()、gouzaohtcode()函數(shù)，其功能是讀入文件zifuht.txt中的字符及其權重，生成對應的哈夫曼樹編碼并將其打印在dayincode.txt文件中；同時顯示系統(tǒng)選擇菜單，提供輸入選項，選項1、2、3分別調用了

15、函數(shù)shurubainmacode()、shurujiemacode()、gouzaohtcode()。*/void main() int choice=1;/設置while循環(huán)的標志 chushihuaht();/初始化哈夫曼樹 gouzaoht(); /構造哈夫曼樹 gouzaohtcode(); /構造哈夫曼編碼并將字符及其哈夫曼編碼打印出來 while(choice) system(cls); printf(/*哈曼編碼與解碼*/n); printf( 在zifuht.txt 文件中存放著各個英文字母的權值n); printf( 程序從中讀出各個字母的權值構造哈夫曼樹并進行編碼n);

16、printf( 各個字符的編碼存在dayincode.txt文件中n); printf(/*/n); printf(n請輸入你的選擇：n); printf(n 1: 編碼n); printf(n 2: 解碼n); printf(n 3:平均編碼長度n); printf(n 4:退出n); scanf(%d,&choice); switch(choice) case 1: shurubainmacode();/輸入需要編碼是字符，并將其打印出來 break; case 2: shurujiemacode();/輸入需要解碼的字符串，并將其打印出來 break; case 3: gouzaohtc

17、ode();/輸出哈夫曼樹平均編碼長度 case 4: printf(謝謝使用！n);/推出系統(tǒng) exit(0); break; default: choice=1; printf(你的輸入錯誤！按任意鍵后重新輸入！n); getch(); break; /*下列函數(shù)初始化哈夫曼樹，定義文件指針file *fp,將含有字符及其權重的zifuht.txt文件讀入到fp中進行初始化。*/void chushihuaht() file * fp; char ch; int i=0; /從文件“zifuht.txt”中讀出要編碼的字符和權值 if(fp=fopen(zifuht.txt,r)=null

18、) printf(不能打開文件 zifuht.txt); exit(0); /將父節(jié)點、左孩子、右孩子置為-1 hti.left=hti.right=hti.parent=-1; while(ch=fgetc(fp)!=eof) /當文件沒有讀完，執(zhí)行while循環(huán) if(ch=n)/字符為空 i+; /父節(jié)點，左右孩子節(jié)點置-1 hti.left=hti.right=hti.parent=-1; else if(ch=a & ch=a & ch=0&ch=9)/字符為數(shù)字 hti.weight=hti.weight*10+ch-0;/讀入權重 n=i+1; if(fclose(fp) pri

19、ntf(不能打開文件 zifuht.txt); exit(0); /*下列函數(shù)構造哈夫曼樹，利用哈夫曼算法，將所有節(jié)點看成有n棵樹，選擇權值最小的兩棵樹合并，最終構成一棵完整的哈夫曼樹。*/void gouzaoht() int i=0,k; int mini,minj; /表示存放權值最小的兩個節(jié)點的數(shù)組下標 int f=0; mini=minj=-1; /miniminj for(k=n;k2*n-1;k+) /尋找ht中權值最小且無父結點的兩個結點 i=0; f=0; while(hti.ch!=0) if(hti.parent=-1)/沒有父節(jié)點，則執(zhí)行下面語句 if(f=0) min

20、i=i; f+; else if(f=1) if(hti.weighthtmini.weight) minj=mini; mini=i; else minj=i; f+; else/如果有父節(jié)點則比較權值的大小 if(hti.weighthtmini.weight)/如果父節(jié)點的權值比較小，則把父節(jié)點的下標賦值給mini minj=mini; mini=i; else if(hti.weighthtminj.weight)/如果父節(jié)點的權值比較大，則把父節(jié)點的下標賦值給minj minj=i; i+; /合并兩個結點 htk.ch=#; htk.left=mini; htk.right=min

21、j; htk.weight=htmini.weight+htminj.weight; htk.parent=-1; htmini.parent=htminj.parent=k;printf(aaaaa); /*下列函數(shù)構造哈夫曼編碼，通過根節(jié)點從下往上找，輸出哈夫曼編碼平均長度；調用函數(shù)fanzhuan()將所得編碼反轉，然后將所得到的26個字母及其編碼存放在文件dayincode.txt中。*/void gouzaohtcode() int i,j,length;int sum=0,m=0; file * fp; for(i=0;in;i+) /從父節(jié)點開始尋找 length=0; j=i;

22、 /給每個字符進行編碼 while(htj.parent!=-1)/當存在父節(jié)點時執(zhí)行 if(hthtj.parent.left=j) /第一個字符為父節(jié)點的左孩子 hcdi.codelength+=0+0; /置0 else /第一個字符為父節(jié)點的右孩子 hcdi.codelength+=1+0; /置1 j=htj.parent; /將此父節(jié)點的值賦給j /將字符編碼從上往下存在hcdi.starthcdi.start=hcdi.codelength-1-0; hcdi.codelength=0; fanzhuan(hcdi.code); /將字符編碼翻轉 m+=hti.weight;/將

23、所有的字符權值相加 sum+=hti.weight*j;/計算字符編碼的平均長度 if(fp=fopen(dayincode.txt,w)=null)/把hcd字符編碼寫入文件dayincode.txt中 printf(不能打開文件 dayincode.txt); exit(0); for(i=0;in;i+)/往文件里寫入字符和編碼 fputc(hti.ch,fp); fputs( ,fp); fputs(hcdi.code,fp); fputc(n,fp); if(fclose(fp) printf(不能打開文件 dayincode.txt); exit(0); printf(平均編碼長度

24、=%gn,1.0*sum/m);/*下列函數(shù)為反轉函數(shù)，將gouzaohtcode()函數(shù)從根節(jié)點編碼的字符串反轉變成從葉子節(jié)點開始編碼。*/void fanzhuan(char *str) int i,j; char ch; for(i=0,j=strlen(str)-1;i=a&stri=a&stri=z)/字符為26字母 for(j=0;jn;j+) if(stri=htj.ch)/比較輸入字符和文件coadht.txt中（即哈夫曼樹中的字符） strcat(code,hcdj.code);/將編碼存放在數(shù)組code中strcat(code1,&htj.ch);/將字符存放在數(shù)組code

25、1中fputc(stri,fp);/將字符寫入code.txt文件中 break; i+; else if(stri=#)/讀到#符號puts(code1);/顯示字符單詞printf( );puts(code);/顯示單詞編碼fputs( ,fp); fputs(code,fp); /將單詞編碼寫入到文件code.txt中 fputc(n,fp);memset(code, 0, sizeof(code);/將code清空memset(code1, 0, sizeof(code1);/將code1清空i+;elsef=0;break; if(fclose(fp) printf(不能打開 cod

26、e.txt 文件); exit(0); if(f) printf(你輸入的每個單詞所對應的二進制編碼最終存放在 code.txt 文件中！n);printf(n); else printf(你輸入的字符串錯誤！n); printf(n); printf(按任意鍵后重新選擇！n); getch(); /*下列函數(shù)的功能為當用戶在選擇菜單上選擇解碼時，輸入需要解碼的字符串，調用函數(shù)jiemaht(str,code)進行解碼，然后在運行界面會顯示相應的字符。*/void shurujiemacode() char str50; char code500=0; printf(n請輸入要解碼的字串(用0

27、和1表示)n); scanf(%s,code);printf(n各進制碼所對應的單詞如下：n); if(jiemaht(str,code)/所輸入編碼字符串與26字符的編碼相等printf(n);puts(code);/顯示編碼 puts(str);/顯示該編碼所對應的字符 else printf(你輸入的字串錯誤！n); printf(按任意鍵后重新選擇！n); getch(); /*下列函數(shù)為解碼函數(shù)，是對函數(shù)shurujiemacode()輸入的字符串進行解碼,輸出相應的字符單詞。*/int jiemaht(char *str,char* code) int root=2*n-2; in

28、t length=0,i=0; while(codei) /當編碼不為空 if(codei=0+0) /為0 root=htroot.left; /向左搜索 else if(codei=0+1)/為1 root=htroot.right; /向右搜索 else return 0; /否則報錯 if(htroot.left=-1 & htroot.right=-1)/如果左右節(jié)點都不存在 strlength+=htroot.ch; root=2*n-2; /重新搜索 i+; strlength=0; if(root=2*n-2) return 1; return 0; 5 測試5.1程序測試用例

29、 主菜單界面功能測試用例如下表5.1表5.1字段名稱描述內容測試項程序主菜單功能測試測試目的查看主菜單是否按照預想的那樣出現(xiàn)運行界面，測試程序是否按照選擇成功運行輸入標準1. 輸入1，然后按enter2. 輸入2，然后按enter3. 輸入3，然后按enter4. 輸入4，然后按enter5. 輸入其他輸出標準1. 進入編寫英文單詞界面，通過英文單詞從而得到哈夫曼編碼2. 進入哈夫曼解碼界面，通過0、1編碼得到英文單詞3. 進入輸出哈夫曼編碼平均長度界面4. 退出系統(tǒng)5. 提示輸入非法錯誤原因可能由于代碼編寫錯誤、邏輯錯誤、運行錯誤而導致界面沒有達到所需要的效果當前狀態(tài)顯示當前測試結果的狀態(tài)哈

30、夫曼編碼測試用例如下表5.2所示表5.2字段名稱描述內容輸入測試的字符can you give me a kiss測試目的查看函數(shù)chushihuaht()、gouzaoht()、gouzaohtcode()是否邏輯正確以及是否進行正確的哈夫曼樹編碼，同時測試函數(shù)shurubainmacode()是否能正確輸出想要的結果預測輸出can 010111111000001001110you 011010101000110give 00111101111000000011me 110100011a 11000001kiss 010110011111010實際輸出測試實際輸出的結果，比較實際輸出和預測輸

31、出的結果是否相同錯誤原因如果實際輸出和預測輸出的結果不一致，則分析產生錯誤的原因當前狀態(tài)顯示當前測試結果的狀態(tài)表5.2哈夫曼解碼測試用例如表5.2字段名稱描述內容輸入測試的字符串01111 001001010000000011 011010101000110測試目的查看函數(shù)shurujiemacode()、jiemaht(char *str,char* code)是否邏輯正確以及是否進行正確的哈夫曼解碼預測輸出01111 i001001010000000011 love011010101000110 you實際輸出測試實際輸出的結果，比較實際輸出和預測輸出的結果是否相同錯誤原因如果實際輸出和預

32、測輸出的結果不一致，則分析產生錯誤的原因當前狀態(tài)顯示當前測試結果的狀態(tài)5.2程序運行結果（1） 上述源程序在vc+6.0中編譯運行后，得到如下頁實驗截圖5.4所示。界面中首先給出運行代碼函數(shù)chushihuaht()、gouzaoht()、gouzaohtcode()后的說明和結果，運行結果為系統(tǒng)將存有權重的英文字母的文件zifuht.txt讀入到系統(tǒng)中，對其進行哈夫曼編碼，并將字符和相應的編碼寫入文件dayincode.txt中；主菜單中共有1-4共4個選項，1為輸入相應的英文單詞從而對其進行編碼，2為輸入相應的哈夫曼編碼從而對其進行解碼，3為輸出哈夫曼樹編碼解碼的平均長度，4為退出該系統(tǒng)。

33、實驗截圖5.4(2）選擇選項1，添加一組英文單詞，按照提示輸入can#you#give#me#a#kiss#,操作成功后會輸出每個單詞以及其哈夫曼編碼，并且將結果寫入到文件code.txt中保存方便使用，如實驗截圖5.5；如果操作失敗就提示錯誤，按任意鍵重新選擇，如下頁的實驗截圖5.6。實驗截圖5.5實驗截圖5.6（2）按任意健，系統(tǒng)回到主菜單界面。選擇選項2，添加一組哈夫曼編碼，按照提示輸入01111001001010000000011011010101000110，操作成功后會輸出所對應的單詞i love you，如實驗截圖5.7所示；如果操作不成功，則提示錯誤，按任意鍵重新選擇，如實驗截

34、圖5.8所示。實驗截圖5.7實驗截圖5.8（3）按任意健，系統(tǒng)回到主菜單界面。選擇選項3，輸出系統(tǒng)的哈夫曼編碼平均編碼長度，如實驗截圖5.9。實驗截圖5.9（4）按任意健，系統(tǒng)回到主菜單界面。選擇選項4，系統(tǒng)自動退出程序，如實驗截圖5.10。實驗截圖5.106 總結6.1 不足與設想不足：這個程序只是實現(xiàn)哈夫曼樹編碼解碼系統(tǒng)中最基本的幾個功能，如基本編碼功能、基本解碼功能、計算哈夫曼樹平均編碼長度，沒有更深層次地設計其他功能，如通過讀入一篇英文文章，從而計算各個字母出現(xiàn)的頻率，進行哈夫曼編碼等等！除此之外，本程序出現(xiàn)程序冗余情況，如函數(shù)fanzhuan(char *str)，如果按照先讀葉子節(jié)點的方法實現(xiàn)編碼，這個函數(shù)的存在就不必要了。設想：本程序可以向更高級的功能實現(xiàn)，就如