[畢業(yè)設(shè)計(jì)精品]哈夫曼編碼譯碼器系統(tǒng)

1、 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)報(bào)告課 題: 專業(yè)班級(jí)： 學(xué) 號(hào)： 姓 名： 指導(dǎo)教師: 1 課程設(shè)計(jì)的目的和意義在當(dāng)今信息爆炸時(shí)代，如何采用有效的數(shù)據(jù)壓縮技術(shù)來節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間已越來越引起人們的重視。哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。樹中從根到每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個(gè)對(duì)應(yīng)的字符的編碼，這就是哈夫曼編碼。通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電

2、報(bào)通信是傳遞文字的二進(jìn)制碼形式的字符串。但在信息傳遞時(shí)，總希望總長(zhǎng)度盡可能最短，即采用最短碼。 2需求分析 課 題：哈夫曼編碼譯碼器系統(tǒng)問題描述：打開一篇英文文章，統(tǒng)計(jì)該文章中每個(gè)字符出現(xiàn)的次數(shù)，然后以它們作為權(quán)值，對(duì)每一個(gè)字符進(jìn)行編碼，編碼完成后再對(duì)其編碼進(jìn)行譯碼。問題補(bǔ)充：1. 從硬盤的一個(gè)文件里讀出一段英語文章；2. 統(tǒng)計(jì)這篇文章中的每個(gè)字符出現(xiàn)的次數(shù)；3. 以字符出現(xiàn)字?jǐn)?shù)作為權(quán)值，構(gòu)建哈夫曼樹4. 對(duì)每個(gè)字符進(jìn)行編碼并將所編碼寫入文件然后對(duì)所編碼進(jìn)行破譯。具體介紹：在本課題中，我們?cè)谟脖Pd盤中預(yù)先建立一個(gè)file.txt文檔，在里面編輯一篇文章(大寫)。然后運(yùn)行程序，調(diào)用fileope

3、n()函數(shù)讀出該文章，顯示在界面；再調(diào)用tongji()函數(shù)對(duì)該文章的字符種類進(jìn)行統(tǒng)計(jì)，并對(duì)每個(gè)字符的出現(xiàn)次數(shù)進(jìn)行統(tǒng)計(jì)，并且在界面上顯示；然后以每個(gè)字符出現(xiàn)次數(shù)作為權(quán)值，調(diào)用create_huffmantree()函數(shù)構(gòu)建哈夫曼樹。然后調(diào)用huffman_bianma()函數(shù)對(duì)哈夫曼樹進(jìn)行編碼，調(diào)用coding()函數(shù)將編碼寫入文件。測(cè)試數(shù)據(jù)：例如從文本中讀到文章為：iamastudent。則效果如下：讀出文本為：iamastudent 字符a次數(shù):2字符d次數(shù):1字符e次數(shù):1字符i 次數(shù):1字符m次數(shù):1字符n 次數(shù):1字符s 次數(shù):1字符t次數(shù):2字符u次數(shù):1輸出編碼：000 101

4、001 101 011 110 100 1110 1111 010 110press any key to continue 3 系統(tǒng)（項(xiàng)目）設(shè)計(jì) (1)設(shè)計(jì)思路及方案本課題是用最優(yōu)二叉樹即哈夫曼樹來實(shí)現(xiàn)哈夫曼編碼譯碼器的功能。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為wi，編碼長(zhǎng)度為li，電文中有n種字符，則電文編碼總長(zhǎng)度為(w1*l1)+(w2*l2)+(wi*li)。若將此對(duì)應(yīng)到二叉樹上，wi為葉結(jié)點(diǎn)，li為根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長(zhǎng)度。那么，(w1*l1)+(w2*l2)+(wi*li)恰好為二叉樹上帶權(quán)路徑長(zhǎng)度。因此，設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵哈夫曼樹

5、，此構(gòu)造過程稱為哈夫曼編碼。該系統(tǒng)將實(shí)現(xiàn)以下幾大功能：從硬盤讀取字符串，建立哈夫曼樹，輸出哈夫曼樹的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)，輸出各種字符出現(xiàn)的次數(shù)以及哈夫曼編碼的譯碼等。 (2)模塊的設(shè)計(jì)及介紹1從硬盤讀取字符串fileopen(參數(shù)) 實(shí)現(xiàn)命令； 打印輸出；2建立huffmantree通過三個(gè)函數(shù)來實(shí)現(xiàn)：void select_min(參數(shù)) 初始化； for 接受命令； 處理命令；說明：在ht1.k中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法int tongji(參數(shù)) 初始化； for 接受命令； 處理命令； 說明：統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字符的種類void create_hu

6、ffmantree() 初始化； for 接受命令； 處理命令； 輸出字符統(tǒng)計(jì)情況；說明：構(gòu)造哈夫曼樹3哈夫曼編碼void huffman_bianma(參數(shù)) 定義變量； 處理命令；說明：哈夫曼編碼 (3)主要模塊程序流程圖下面介紹三個(gè)主要的程序模塊流程圖： 主函數(shù)流程圖：結(jié)束統(tǒng)計(jì)字符種類及頻率字符總數(shù)num建立哈夫曼樹哈夫曼編碼打開文件？開始否是 圖3.1流程圖注釋：該圖比較簡(jiǎn)單，主要是調(diào)用各個(gè)函數(shù)模塊，首先代開已經(jīng)存在的文件，然后統(tǒng)計(jì)總的字符數(shù)以及出現(xiàn)的各個(gè)字符和頻率。然后才開始建立哈夫曼樹，接著在哈夫曼樹的基礎(chǔ)上對(duì)其進(jìn)行編碼。最后輸出結(jié)束。構(gòu)造哈夫曼樹：開始結(jié)束第i個(gè)結(jié)點(diǎn)權(quán)值i=num

7、?創(chuàng)建哈夫曼樹輸出字符統(tǒng)計(jì)情況第i個(gè)根結(jié)點(diǎn)i=2*num-1?i=num?否是否是否是 圖3.2流程圖注釋：該圖是表示構(gòu)造哈夫曼樹的過程。首先輸入num個(gè)葉結(jié)點(diǎn)的權(quán)值，當(dāng)i=num是循環(huán)結(jié)束。然后進(jìn)行哈夫曼樹的構(gòu)建，當(dāng)i=2*num-1是循環(huán)結(jié)束。最后輸出所得到的字符統(tǒng)計(jì)情況。哈夫曼編碼：結(jié)束開始tp.left=c?i=num?cd-start=0,start=numcd-start=0cd-start=1否否是是 圖3.3流程圖解釋：該流程圖表四哈夫曼編碼情況。首先初始化，cd-start=0,start=num。然后進(jìn)行編碼，當(dāng)cd-start=tp.lchild= =c時(shí)，cd-star

8、t=0；當(dāng)cd-start=tp.left！= =c時(shí)，cd-start=1。這個(gè)編碼循環(huán)一直到i=num時(shí)結(jié)束。4 系統(tǒng)實(shí)現(xiàn)各模塊關(guān)鍵代碼及算法的解釋： 主調(diào)函數(shù) 代碼解釋：這是main函數(shù)里的各個(gè)函數(shù)調(diào)用情況。fileopen(string); /從硬盤中讀取文件num=tongji(string,cishu,str); /統(tǒng)計(jì)字符種類及各類字符出現(xiàn)的頻率create_huffmantree(ht,hc,cishu,str);/建立哈夫曼樹 huffman_bianma(ht,hc); /生成哈夫曼編碼 建立huffmantree代碼解釋：該函數(shù)為在ht1.k中選擇parent為0且權(quán)值最

9、小的兩個(gè)根結(jié)點(diǎn)的算法，其序號(hào)為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;min1=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;代碼解釋：下面函數(shù)用來統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字符的種類。當(dāng)字符在a和z之間時(shí)

10、即被計(jì)數(shù)，并用strj保存字母到數(shù)組中，用cntj統(tǒng)計(jì)每種字符個(gè)數(shù)。j返回總共讀取的字符數(shù)目。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=1,j=0;i=26;+i)if(ti!=0 ) j+;strj=i+64; cishuj=ti; return j; 代碼解釋：下面函數(shù)用來構(gòu)造哈夫曼樹ht。首先初始化哈夫曼樹，然后輸入前面統(tǒng)計(jì)的各結(jié)點(diǎn)的權(quán)值，用for循環(huán)來構(gòu)造哈夫曼樹。void create_huffmantree(huffma

11、ntree 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+) /輸入num個(gè)葉結(jié)點(diǎn)的權(quán)值hti.weight=cishui;for(i=num+1;i=2*num-1;i+) /選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)，其序號(hào)為s1和s2,i為雙親select_min(ht,i-1,s1,s2);hts1.parent=i;hts2.parent=i;

12、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次數(shù):%8dn,hci.ch,cishui+); 生成huffman編碼并寫入文件代碼解釋：根據(jù)哈夫曼樹t求哈夫曼編碼h。void huffman_bianma(huffmantree t,huffmancode h) /根據(jù)哈夫曼樹t求哈夫曼編碼h int child,parent,i; /child和parent分別指示t中孩子和雙親char

13、coden; /存放編碼int start; /指示碼在code中的起始位置codenum=0; /最后一位（第num個(gè)）放上串結(jié)束符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;代碼解釋：對(duì)str所代表的字符串進(jìn)行編碼并寫入文件。將翻譯的二進(jìn)制碼寫入文本文件。void coding(huffmancode hc

14、,char *str) /對(duì)str所代表的字符串進(jìn)行編碼 并寫入文件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);5 系統(tǒng)調(diào)試本次測(cè)試是在我的電腦的d盤中建立一個(gè)名為file.txt的文本文檔，其中有大寫字母iamastudent，期望程序能將其讀出至界面并實(shí)現(xiàn)其他相關(guān)的功能。運(yùn)行程序后，我們可以見到一下的運(yùn)行界面。從硬盤中讀出已有的文本文件 輸出所

15、讀字符的種類和每種字符的個(gè)數(shù) 輸出編碼 小 結(jié)通過一周的課程設(shè)計(jì)使我對(duì)哈夫曼樹以及哈夫曼編碼有了更深的認(rèn)識(shí)和理解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。首先我談?wù)勎以谠O(shè)計(jì)期間我遇到的難點(diǎn)。開始的時(shí)候，代碼中有許多的錯(cuò)誤，特別是有一個(gè)“無法找到文件”的錯(cuò)誤讓我束手無策，最后還是屏蔽了定義的四個(gè)頭文件然后慢慢地改正錯(cuò)誤才讓我又看到了希望。然后在實(shí)現(xiàn)文章的讀入時(shí)，由于對(duì)文件不是太熟悉，只好翻開c語言書本仿照其模式編寫，但后來進(jìn)入了死循環(huán)，最后的解決方式是把main函數(shù)里的一個(gè)dowhile循環(huán)去掉。許多的錯(cuò)誤讓我明白了一個(gè)道理-細(xì)心是非常重要的。同時(shí)，對(duì)于編程者而言，思路清晰是相當(dāng)

16、重要的。在適當(dāng)?shù)臅r(shí)候和同學(xué)一起交流探討是一個(gè)十分好的學(xué)習(xí)機(jī)會(huì)。這次課程設(shè)計(jì)不但讓我學(xué)得了一些編程知識(shí)，還學(xué)會(huì)了系統(tǒng)的做一份課程設(shè)計(jì)報(bào)告，學(xué)會(huì)了如何截圖，學(xué)會(huì)了如何更好的畫流程圖，明白了做事情只有認(rèn)真，才能真正做得更好！通過這次課程設(shè)計(jì)，我看清楚了自己的編程功底和動(dòng)手能力還很不足，這主要是平時(shí)實(shí)踐太少的緣故。我想，在未來的暑假中，我會(huì)努力嘗試編寫一些程序。在這個(gè)程序中，還有許多地方值得完善。比如，讀出文本只能是大寫的文檔，空格和小寫不能識(shí)別。由于時(shí)間問題，暫時(shí)不能實(shí)現(xiàn)了，我想在暑假里好好研究這個(gè)問題。未完成：哈夫曼譯碼附錄 源程序#include #include #include #inclu

17、de/類型相關(guān)變量的定義#define n 100 #define m 2*n-1 typedef structchar ch;char co9; /存放編碼int len; codenode;typedef codenode huffmancoden+1;typedef struct int weight; int left,right,parent; htnode;typedef htnode huffmantreem+1; int num;void select_min(huffmantree t,int k,int &x1,int &x2) /選擇權(quán)值最小的兩個(gè)根結(jié)點(diǎn),其序號(hào)為x1和x

18、2int 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 & ti.parent=0 & i!=x1)j=i;min1=ti.weight;x2=j;int tongji(char *s,int cishu,char str) /統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字符的種類int i,j,k; char *p;int t27; for(i=1;i=a&*p=z)

19、k=*p-64;tk+; for(i=1,j=0;i=26;+i)if(ti!=0 ) j+;strj=i+64; /送對(duì)應(yīng)的字母到數(shù)組中cishuj=ti; /存入對(duì)應(yīng)字母的權(quán)值return j; /j是輸入字母種數(shù)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+) /輸入num個(gè)葉

20、結(jié)點(diǎn)的權(quán)值hti.weight=cishui;for(i=num+1;i=2*num-1;i+) /選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)，其序號(hào)為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次數(shù):%8dn,hci.ch,cishui+);void huffman

21、_bianma(huffmantree t,huffmancode h) /根據(jù)哈夫曼樹t求哈夫曼編碼h int child,parent,i; /child和parent分別指示t中孩子和雙親char coden; /存放編碼int start; /指示碼在code中的起始位置codenum=0; /最后一位（第num個(gè)）放上串結(jié)束符for(i=1;i0) /直至tchild是樹根為止 /若tchild是tparent的左孩子,則生成0;否則生成1if(tparent.left=child)code-start=0;elsecode-start=1;child=parent;strcpy(h

22、i.co,&codestart);hi.len=num-start;void coding(huffmancode hc ,char *str) /對(duì)str所代表的字符串進(jìn)行編碼 并寫入文件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(