哈夫曼編碼課程設計報告

1、 湖南科技學院 數據結構 課程設計報告課 題: 霍夫曼編碼 專業(yè)班級： 信計1202 學 號： 201205001239 姓 名： 黃思琪 指導教師: 牛志毅 1 課程設計的目的和意義在當今信息爆炸時代，如何采用有效的數據壓縮技術來節(jié)省數據文件的存儲空間和計算機網絡的傳送時間已越來越引起人們的重視。哈夫曼編碼正是一種應用廣泛且非常有效的數據壓縮技術。哈夫曼編碼的應用很廣泛，利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個對應的字符的

2、編碼，這就是哈夫曼編碼。通常我們把數據壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進制碼形式的字符串。但在信息傳遞時，總希望總長度盡可能最短，即采用最短碼。 2需求分析 課 題：哈夫曼編碼譯碼器系統(tǒng)問題描述：打開一篇英文文章，統(tǒng)計該文章中每個字符出現的次數，然后以它們作為權值，對每一個字符進行編碼，編碼完成后再對其編碼進行譯碼。問題補充：1. 從硬盤的一個文件里讀出一段英語文章；2. 統(tǒng)計這篇文章中的每個字符出現的次數；3. 以字符出現字數作為權值，構建哈夫曼樹4. 對每個字符進行編碼并將所編碼寫入文件然后對所編碼進行破譯。具體介紹：在本課題中，我們在硬盤D盤中預先建立一個

3、xuzhimo.txt文檔，在里面編輯一篇文章(大寫)。然后運行程序，調用fileopen()函數讀出該文章，顯示在界面；再調用tongji()函數對該文章的字符種類進行統(tǒng)計，并對每個字符的出現次數進行統(tǒng)計，并且在界面上顯示；然后以每個字符出現次數作為權值，調用Create_huffmanTree()函數構建哈夫曼樹。然后調用Huffman_bianma()函數對哈夫曼樹進行編碼，調用coding()函數將編碼寫入文件。 3 系統(tǒng)（項目）設計 (1)設計思路及方案本課題是用最優(yōu)二叉樹即哈夫曼樹來實現哈夫曼編碼譯碼器的功能。假設每種字符在電文中出現的次數為Wi，編碼長度為Li，電文中有n種字符，

4、則電文編碼總長度為(W1*L1)+(W2*L2)+(Wi*Li)。若將此對應到二叉樹上，Wi為葉結點，Li為根結點到葉結點的路徑長度。那么，(W1*L1)+(W2*L2)+(Wi*Li)恰好為二叉樹上帶權路徑長度。因此，設計電文總長最短的二進制前綴編碼，就是以n種字符出現的頻率作權，構造一棵哈夫曼樹，此構造過程稱為哈夫曼編碼。該系統(tǒng)將實現以下幾大功能：從硬盤讀取字符串，建立哈夫曼樹，輸出哈夫曼樹的存儲結構的初態(tài)和終態(tài)，輸出各種字符出現的次數以及哈夫曼編碼的譯碼等。 (2)模塊的設計及介紹1從硬盤讀取字符串fileopen(參數) 實現命令； 打印輸出；2建立HuffmanTree通過三個函數來

5、實現：void select_min(參數) 初始化； for 接受命令； 處理命令；說明：在ht1.k中選擇parent為0且權值最小的兩個根結點的算法int tongji(參數) 初始化； for 接受命令； 處理命令； 說明：統(tǒng)計字符串中各種字母的個數以及字符的種類void Create_huffmanTree() 初始化； for 接受命令； 處理命令； 輸出字符統(tǒng)計情況；說明：構造哈夫曼樹3哈夫曼編碼void Huffman_bianma(參數) 定義變量； 處理命令；說明：哈夫曼編碼 (3)主要模塊程序流程圖下面介紹三個主要的程序模塊流程圖： 主函數流程圖：結束統(tǒng)計字符種類及頻率字

6、符總數num建立哈夫曼樹哈夫曼編碼打開文件？開始否是 圖3.1流程圖注釋：該圖比較簡單，主要是調用各個函數模塊，首先代開已經存在的文件，然后統(tǒng)計總的字符數以及出現的各個字符和頻率。然后才開始建立哈夫曼樹，接著在哈夫曼樹的基礎上對其進行編碼。最后輸出結束。構造哈夫曼樹：開始結束第i個結點權值i=num?創(chuàng)建哈夫曼樹輸出字符統(tǒng)計情況第i個根結點i=2*num-1?i=num?否是否是否是 圖3.2流程圖注釋：該圖是表示構造哈夫曼樹的過程。首先輸入num個葉結點的權值，當i=num是循環(huán)結束。然后進行哈夫曼樹的構建，當i=2*num-1是循環(huán)結束。最后輸出所得到的字符統(tǒng)計情況。哈夫曼編碼：結束開始T

7、p.left=c?i=num?Cd-start=0,start=numCd-start=0Cd-start=1否否是是 圖3.3流程圖解釋：該流程圖表四哈夫曼編碼情況。首先初始化，Cd-start=0,start=num。然后進行編碼，當cd-start=Tp.lchild= =c時，cd-start=0；當cd-start=Tp.left！= =c時，cd-start=1。這個編碼循環(huán)一直到i=num時結束。4 系統(tǒng)實現各模塊關鍵代碼及算法的解釋： 主調函數 代碼解釋：這是main函數里的各個函數調用情況。fileopen(string); /從硬盤中讀取文件num=tongji(strin

8、g,cishu,str); /統(tǒng)計字符種類及各類字符出現的頻率Create_huffmanTree(HT,HC,cishu,str);/建立哈夫曼樹 Huffman_bianma(HT,HC); /生成哈夫曼編碼 建立HuffmanTree代碼解釋：該函數為在ht1.k中選擇parent為0且權值最小的兩個根結點的算法，其序號為s1和s2。void select_min(HuffmanTree T,int k,int &x1,int &x2) int i,j;int min1=1000; for(i=1;i=k;i+) if(Ti.weightmin1 &Ti.parent=0) j=i;mi

9、n1=Ti.weight;x1=j;min1=1000;for (i=1;i=k;i+) if(Ti.weightmin1 & Ti.parent=0 & i!=x1)j=i;min1=Ti.weight;x2=j;代碼解釋：下面函數用來統(tǒng)計字符串中各種字母的個數以及字符的種類。當字符在A和Z之間時即被計數，并用strj保存字母到數組中，用cntj統(tǒng)計每種字符個數。j返回總共讀取的字符數目。int tongji(char *s,int cishu,char str) int i,j,k; char *p;int t27; for(i=1;i=A&*p=Z)k=*p-64;tk+; for(i=

10、1,j=0;i=26;+i)if(ti!=0 ) j+;strj=i+64; cishuj=ti; return j; 代碼解釋：下面函數用來構造哈夫曼樹HT。首先初始化哈夫曼樹，然后輸入前面統(tǒng)計的各結點的權值，用for循環(huán)來構造哈夫曼樹。void Create_huffmanTree(HuffmanTree ht,HuffmanCode hc,int cishu,char str) /生成哈夫曼樹HTint i,s1,s2;for(i=0;i2*num-1;i+) hti.left=0;hti.right=0;hti.parent=0;hti.weight=0;for(i=1;i=num;i

11、+) /輸入num個葉結點的權值hti.weight=cishui;for(i=num+1;i=2*num-1;i+) /選擇parent為0且權值最小的兩個根結點，其序號為s1和s2,i為雙親select_min(ht,i-1,s1,s2);hts1.parent=i;hts2.parent=i;hti.left=s1; hti.right=s2;hti.weight=hts1.weight+hts2.weight;for(i=0;i=num;i+) hci.ch=stri; /字符的種類i=1;while(i=num)printf(字符%c次數:%8dn,hci.ch,cishui+);

12、生成Huffman編碼并寫入文件代碼解釋：根據哈夫曼樹T求哈夫曼編碼H。void Huffman_bianma(HuffmanTree T,HuffmanCode H) /根據哈夫曼樹T求哈夫曼編碼H int child,parent,i; /child和parent分別指示t中孩子和雙親char coden; /存放編碼int start; /指示碼在code中的起始位置codenum=0; /最后一位（第num個）放上串結束符for(i=1;i0) /直至tchild是樹根為止 /若tchild是tparent的左孩子,則生成0;否則生成1if(Tparent.left=child)cod

13、e-start=0;elsecode-start=1;child=parent;strcpy(Hi.co,&codestart);Hi.len=num-start;代碼解釋：對str所代表的字符串進行編碼并寫入文件。將翻譯的二進制碼寫入文本文件。void coding(HuffmanCode hc ,char *str) /對str所代表的字符串進行編碼 并寫入文件int i,j;FILE *fp;fp=fopen(codefile.txt,w);while(*str)for(i=1;i=num;i+)if(hci. ch=*str)for(j=0;j=hci.len;j+)fputc(hci

14、.coj,fp);break;str+;fclose(fp);5 系統(tǒng)調試本次測試是在我的電腦的D盤中建立一個名為file.txt的文本文檔，其中有大寫字母IAMASTUDENT，期望程序能將其讀出至界面并實現其他相關的功能。運行程序后，我們可以見到一下的運行界面。從硬盤中讀出已有的文本文件 輸出所讀字符的種類和每種字符的個數 輸出編碼 小 結通過一周的課程設計使我對哈夫曼樹以及哈夫曼編碼有了更深的認識和理解，也使我更加明白哈夫曼編碼譯碼在信息技術中的重要性和地位。首先我談談我在設計期間我遇到的難點。開始的時候，代碼中有許多的錯誤，特別是有一個“無法找到文件”的錯誤讓我束手無策，最后還是屏蔽了

15、定義的四個頭文件然后慢慢地改正錯誤才讓我又看到了希望。然后在實現文章的讀入時，由于對文件不是太熟悉，只好翻開C語言書本仿照其模式編寫，但后來進入了死循環(huán)，最后的解決方式是把main函數里的一個dowhile循環(huán)去掉。許多的錯誤讓我明白了一個道理-細心是非常重要的。同時，對于編程者而言，思路清晰是相當重要的。在適當的時候和同學一起交流探討是一個十分好的學習機會。這次課程設計不但讓我學得了一些編程知識，還學會了系統(tǒng)的做一份課程設計報告，學會了如何截圖，學會了如何更好的畫流程圖，明白了做事情只有認真，才能真正做得更好！通過這次課程設計，我看清楚了自己的編程功底和動手能力還很不足，這主要是平時實踐太少

16、的緣故。我想，在未來的暑假中，我會努力嘗試編寫一些程序。在這個程序中，還有許多地方值得完善。比如，讀出文本只能是大寫的文檔，空格和小寫不能識別。由于時間問題，暫時不能實現了，我想在暑假里好好研究這個問題。未完成：哈夫曼譯碼附錄 源程序#include #include #include #include/類型相關變量的定義#define n 100 #define m 2*n-1 typedef structchar ch;char co9; /存放編碼int len; CodeNode;typedef CodeNode HuffmanCoden+1;typedef struct int we

17、ight; int left,right,parent; HTNode;typedef HTNode HuffmanTreem+1; int num;void select_min(HuffmanTree T,int k,int &x1,int &x2) /選擇權值最小的兩個根結點,其序號為x1和x2int i,j;int min1=1000; for(i=1;i=k;i+) /找最小值if(Ti.weightmin1 &Ti.parent=0) j=i;min1=Ti.weight;x1=j;min1=1000;for (i=1;i=k;i+) /找次小值if(Ti.weightmin1 &

18、 Ti.parent=0 & i!=x1)j=i;min1=Ti.weight;x2=j;int tongji(char *s,int cishu,char str) /統(tǒng)計字符串中各種字母的個數以及字符的種類int i,j,k; char *p;int t27; for(i=1;i=A&*p=Z)k=*p-64;tk+; for(i=1,j=0;i=26;+i)if(ti!=0 ) j+;strj=i+64; /送對應的字母到數組中cishuj=ti; /存入對應字母的權值return j; /j是輸入字母種數void Create_huffmanTree(HuffmanTree ht,Hu

19、ffmanCode hc,int cishu,char str) /生成哈夫曼樹HTint i,s1,s2;for(i=0;i2*num-1;i+) hti.left=0;hti.right=0;hti.parent=0;hti.weight=0;for(i=1;i=num;i+) /輸入num個葉結點的權值hti.weight=cishui;for(i=num+1;i=2*num-1;i+) /選擇parent為0且權值最小的兩個根結點，其序號為s1和s2,i為雙親select_min(ht,i-1,s1,s2);hts1.parent=i;hts2.parent=i;hti.left=s1

20、; hti.right=s2;hti.weight=hts1.weight+hts2.weight;for(i=0;i=num;i+) hci.ch=stri; /字符的種類i=1;while(i=num)printf(字符%c次數:%8dn,hci.ch,cishui+);void Huffman_bianma(HuffmanTree T,HuffmanCode H) /根據哈夫曼樹T求哈夫曼編碼H int child,parent,i; /child和parent分別指示t中孩子和雙親char coden; /存放編碼int start; /指示碼在code中的起始位置codenum=0;

21、 /最后一位（第num個）放上串結束符for(i=1;i0) /直至tchild是樹根為止 /若tchild是tparent的左孩子,則生成0;否則生成1if(Tparent.left=child)code-start=0;elsecode-start=1;child=parent;strcpy(Hi.co,&codestart);Hi.len=num-start;void coding(HuffmanCode hc ,char *str) /對str所代表的字符串進行編碼 并寫入文件int i,j;FILE *fp;fp=fopen(codefile.txt,w);while(*str)for(i=1;i=num;i+)if(hci. ch=*str)for(j=0;j=hci.len;j+)fputc(hci.coj,fp);break;str+;fclose(fp);void output() /輸出編碼FILE *fp;char ch;if(fp=fopen(codefile.txt,r+)=NULL)printf(errorn);exit(0);printf(編碼為:n);ch=fgetc(fp);while(!feof(fp)putchar(ch);ch=fgetc(fp); printf(n);int fileopen(char string) /讀