哈夫曼編碼譯碼器---課程設(shè)計(jì)報告

1、目錄目錄.21課程設(shè)計(jì)的目的和意義32需求分析43概要設(shè)計(jì)44詳細(xì)設(shè)計(jì).85調(diào)試分析和測試結(jié)果.116總結(jié)127致謝138附錄13參考文獻(xiàn).201 課程設(shè)計(jì)目的與意義在當(dāng)今信息爆炸時代，如何采用有效的數(shù)據(jù)壓縮技術(shù)來節(jié)省數(shù)據(jù)文件的存儲空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視。哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個對應(yīng)的字符的編碼，這就是哈夫曼

2、編碼。通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進(jìn)制碼形式的字符串。但在信息傳遞時，總希望總長度盡可能最短，即采用最短碼。作為計(jì)算機(jī)專業(yè)的學(xué)生，我們應(yīng)該很好的掌握這門技術(shù)。在課堂上，我們能過學(xué)到許多的理論知識，但我們很少有過自己動手實(shí)踐的機(jī)會！課程設(shè)計(jì)就是為解決這個問題提供了一個平臺。在課程設(shè)計(jì)過程中，我們每個人選擇一個課題，認(rèn)真研究，根據(jù)課堂講授內(nèi)容，借助書本，自己動手實(shí)踐。這樣不但有助于我們消化課堂所講解的內(nèi)容，還可以增強(qiáng)我們的獨(dú)立思考能力和動手能力；通過編寫實(shí)驗(yàn)代碼和調(diào)試運(yùn)行，我們可以逐步積累調(diào)試C程序的經(jīng)驗(yàn)并逐漸培養(yǎng)我們的編程能力、用計(jì)算機(jī)解決實(shí)際問

3、題的能力。在課程設(shè)計(jì)過程中，我們不但有自己的獨(dú)立思考，還借助各種參考文獻(xiàn)來幫助我們完成系統(tǒng)。更為重要的是，我們同學(xué)之間加強(qiáng)了交流，在對問題的認(rèn)識方面可以交換不同的意見。同時，師生之間的互動也隨之改善，我們可以通過具體的實(shí)例來從老師那學(xué)到更多的實(shí)用的知識。數(shù)據(jù)結(jié)構(gòu)課程具有比較強(qiáng)的理論性，同時也具有較強(qiáng)的可應(yīng)用性和實(shí)踐性。課程設(shè)計(jì)是一個重要的教學(xué)環(huán)節(jié)。我們在一般情況下都能夠重視實(shí)驗(yàn)環(huán)節(jié)，但是容易忽略實(shí)驗(yàn)的總結(jié)，忽略實(shí)驗(yàn)報告的撰寫。通過這次實(shí)驗(yàn)讓我們明白：作為一名大學(xué)生必須嚴(yán)格訓(xùn)練分析總結(jié)能力、書面表達(dá)能力。需要逐步培養(yǎng)書寫科學(xué)實(shí)驗(yàn)報告以及科技論文的能力。只有這樣，我們的綜合素質(zhì)才會有好的提高。2

4、需求分析課 題：哈夫曼編碼譯碼器問題描述：打開一篇英文文章，統(tǒng)計(jì)該文章中每個字符出現(xiàn)的次數(shù)，然后以它們作為權(quán)值，對每一個字符進(jìn)行編碼，編碼完成后再對其編碼進(jìn)行譯碼。問題補(bǔ)充：1. 從硬盤的一個文件里讀出一段英語文章；2. 統(tǒng)計(jì)這篇文章中的每個字符出現(xiàn)的次數(shù)；3. 以字符出現(xiàn)字?jǐn)?shù)作為權(quán)值，構(gòu)建哈夫曼樹，并將哈夫曼樹的存儲結(jié)構(gòu)的初態(tài)和終態(tài)進(jìn)行輸出；4. 對每個字符進(jìn)行編碼并將所編碼寫入文件然后對所編碼進(jìn)行破譯。具體介紹：在本課題中，我們在硬盤中預(yù)先建立一個文檔，在里面編輯一篇文章。然后運(yùn)行程序，調(diào)用函數(shù)讀出該文章，顯示在界面；再調(diào)用函數(shù)對該文章的字符種類進(jìn)行統(tǒng)計(jì)，并對每個字符的出現(xiàn)次數(shù)進(jìn)行統(tǒng)計(jì)，并

5、且在界面上顯示；然后以每個字符出現(xiàn)次數(shù)作為權(quán)值，調(diào)用函數(shù)構(gòu)建哈夫曼樹；并調(diào)用函數(shù)將哈夫曼的存儲結(jié)構(gòu)的初態(tài)和終態(tài)進(jìn)行輸出。然后調(diào)用函數(shù)對哈夫曼樹進(jìn)行編碼，調(diào)用函數(shù)將編碼寫入文件；再調(diào)用對編碼進(jìn)行譯碼，再輸出至界面。至此，整個工作就完成了3 概要設(shè)計(jì)。對系統(tǒng)進(jìn)行分析，給出系統(tǒng)結(jié)構(gòu)圖；哈弗曼樹編碼譯碼器編碼譯碼退出圖1 系統(tǒng)結(jié)構(gòu)圖（1）.編碼：提示要編碼的文件文件名讀取文件以字母出現(xiàn)次數(shù)為權(quán)值建立哈弗曼樹對文本進(jìn)行哈弗曼編碼并輸出編碼提示將編碼保存的文件名保存編碼文件；（2）.譯碼：提示輸入要譯碼的文件名利用建立好的哈弗曼樹進(jìn)行譯碼將譯碼輸出提示保存譯碼文件的文件名保存譯碼文件；（3）.退出：退出系

6、統(tǒng)，程序運(yùn)行結(jié)束。1打開文件函數(shù)：Open(char s)輸入要打開的文件名if(fp=fopen(name,rt)=NULL)打開失敗si+=fgetc(fp)fclose(fp)開始圖2 打開文件函數(shù)流程圖2.保存文件函數(shù)Save(char s)開 始輸入要保存的文件名if(fp=fopen(name,wt)=NULL)存儲失敗fputs(s,fp)fclose(fp)是圖3 保存文件函數(shù)流程圖3.哈弗曼編碼函數(shù)：HFMCode(HFMTree HT,CodeNode HC,char str)開始將字符存入哈夫曼編碼結(jié)構(gòu)體數(shù)組的字符單元中if(q=q-Parent-LChild)HCi.c

7、ode-HCi.start=0HCi.code-HCi.start=1p=p-nextI=n 時結(jié)束圖4 哈弗曼編碼函數(shù)流程圖4.譯碼函數(shù)：DeCoding(char code,HFMTree HT,char str,char s)開始Root指向根節(jié)點(diǎn)P!=rootcodei=0p=p-LChildp=p-RChildp-LChild=NULL&p-RChild=NULLsk+=strjp=root結(jié)束 圖5 譯碼函數(shù)流程圖4 詳細(xì)設(shè)計(jì)本課題是用最優(yōu)二叉樹即哈夫曼樹來實(shí)現(xiàn)哈夫曼編碼譯碼器的功能。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為Wi，編碼長度為Li，電文中有n種字符，則電文編碼總長度為(W1*

8、L1)+(W2*L2)+(Wi*Li)。若將此對應(yīng)到二叉樹上，Wi為葉結(jié)點(diǎn)，Li為根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長度。那么，(W1*L1)+(W2*L2)+(Wi*Li)恰好為二叉樹上帶權(quán)路徑長度。因此，設(shè)計(jì)電文總長最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵哈夫曼樹，此構(gòu)造過程稱為哈夫曼編碼該系統(tǒng)將實(shí)現(xiàn)以下幾大功能：從硬盤讀取字符串，建立哈夫曼樹，哈弗曼編碼以及哈夫曼譯碼等。1.從硬盤讀出字符串的函數(shù)：void Open(char s) /打開存放字符或編碼的文件，將其存入字符串?dāng)?shù)組中char name10;FILE *fp;int i=0;printf(請輸入要打開的文件名：);ge

9、ts(name); /要打開的文件名if(fp=fopen(name,rt)=NULL)printf(打開失??！n); /若打開失敗，則直接退出exit(1);si+=fgetc(fp);while(si-1!=EOF)si+=fgetc(fp);si=0; /存取字符串結(jié)束fclose(fp);2.建立哈夫曼樹函數(shù)void CreatHFMTree(HFMTree *HT,int count)/創(chuàng)建哈夫曼樹int i;HFMTree p,HT1,HT2; /HT1，HT2分別存放權(quán)值最小和次小的節(jié)點(diǎn)的位置p=*HT=(HFMTree)malloc(sizeof(HFMNode);p-next

10、=p-LChild=p-RChild=p-Parent=NULL; /初始化哈夫曼鏈表且有2n-1個節(jié)點(diǎn)for(i=1;inext=(HFMTree)malloc(sizeof(HFMNode);p=p-next;p-next=p-LChild=p-RChild=p-Parent=NULL;for(i=0,p=*HT;iweight=counti;p=p-next;for(i=n;iParent=HT2-Parent=p; p-LChild=HT1;p-RChild=HT2;p-weight=HT1-weight+HT2-weight; /將兩個節(jié)點(diǎn)的權(quán)值相加存入最后一個節(jié)點(diǎn)中p=p-next

11、; /p指向下一個沒有存儲權(quán)值的節(jié)點(diǎn)3哈弗曼編碼函數(shù)：void HFMCode(HFMTree HT,CodeNode HC,char str)/從每個葉子節(jié)點(diǎn)開始，利用哈夫曼樹對每個字符進(jìn)行編碼，最終建立一個哈夫曼表int i;HFMTree q,p=HT;for(i=0;in;i+) /將字符存入哈夫曼編碼結(jié)構(gòu)體數(shù)組的字符單元中HCi.ch=stri;HCi.coden-1=0; /初始化編碼的最后一位for(i=0;iParent;q=q-Parent) /判斷q所指向的節(jié)點(diǎn)，左孩子置0，右孩子置1if(q=q-Parent-LChild)HCi.code-HCi.start=0;els

12、eHCi.code-HCi.start=1;p=p-next; /判斷下一個葉子節(jié)點(diǎn)5哈弗曼譯碼函數(shù)void DeCoding(char code,HFMTree HT,char str,char s)/對哈夫曼編碼進(jìn)行譯碼，放入字符串s中int i,j,k=0;HFMTree root,p,q;for(root=HT;root-Parent;root=root-Parent); /用root指向哈夫曼樹的根結(jié)點(diǎn)for(i=0,p=root;codei;i+) /從根結(jié)點(diǎn)開始按編碼順序訪問樹 if(codei=0)p=p-LChild;elsep=p-RChild;if(p-LChild=NU

13、LL&p-RChild=NULL) /到根節(jié)點(diǎn)時將該節(jié)點(diǎn)對應(yīng)的字符輸出for(j=0,q=HT;q!=p;q=q-next,j+);sk+=strj;p=root; /回溯到根結(jié)點(diǎn)sk=0; /解碼完畢，在字符串最后一個單元存入05 調(diào)試分析和測試結(jié)果1.運(yùn)行程序得到如下界面：圖6 主界面運(yùn)行截圖2.選擇1，按回車鍵，在輸入txt1.txt對字符串進(jìn)行編碼，得到如下界面： 圖7 編碼運(yùn)行截圖3.輸入txt2.txt按回車鍵保存哈弗曼編碼：圖8 保存編碼運(yùn)行截圖4.輸入txt2.txt按回車鍵進(jìn)行譯碼得到如下界面：圖9 譯碼運(yùn)行截圖6總結(jié)通過一周的課程設(shè)計(jì)使我對哈夫曼樹以及哈夫曼編碼有了更深的認(rèn)

14、識和理解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。首先我談?wù)勎以谠O(shè)計(jì)期間我遇到的難點(diǎn)。開始的時候，代碼中有許多的錯誤，特別是有一個“無法找到文件”的錯誤讓我束手無策，最后還是屏蔽了定義的四個頭文件然后慢慢地改正錯誤才讓我又看到了希望。然后在實(shí)現(xiàn)文章的讀入時，由于對文件不是太熟悉，只好翻開C語言書本仿照其模式編寫。許多的錯誤讓我明白了一個道理-細(xì)心是非常重要的。同時，對于編程者而言，思路清晰是相當(dāng)重要的。在適當(dāng)?shù)臅r候和同學(xué)一起交流探討是一個十分好的學(xué)習(xí)機(jī)會。請教老師也很重要，因?yàn)楫吘刮覀兪切率?，對于某些問題很難弄清楚。而且，某些錯誤對于我們來說有時候想半天都弄不來，但老師幾下下就

15、搞好了，這樣就更加有效地節(jié)約了時間。這次課程設(shè)計(jì)不但讓我學(xué)得了一些編程知識，還學(xué)會了系統(tǒng)的做一份課程設(shè)計(jì)報告，學(xué)會了如何截圖，學(xué)會了如何更好的畫流程圖，明白了做事情只有認(rèn)真，才能真正做得更好！這段時間里，可謂是酸甜苦辣都嘗過。有時，為了一個錯誤而焦頭爛額；有時，連吃飯都是匆匆了事；但一旦程序運(yùn)行成功，總會讓我興奮不已。通過這次課程設(shè)計(jì)，我看清楚了自己的編程功底和動手能力還不如人意，這主要是平時實(shí)踐太少的緣故。我想，在未來的暑假中，我會努力嘗試編寫一些程序。雖然我們信息管理專業(yè)的學(xué)生，但現(xiàn)在編程的能力太差了，畢竟多精通一門技術(shù)總是好事。在這個程序中，還有許多地方值得完善。比如，讀出文本只能是大寫

16、的文檔，空格和小寫不能識別，更不用說是任意的ASC碼字符了。由于時間問題，暫時不能實(shí)現(xiàn)了。我想在暑假里好好研究這個問題7 致謝在這次設(shè)計(jì)中我要感謝與我同組的兩位同學(xué)喻霞林和董茗桓，有很多不懂得地方我們可以互相討論研究，沒有他們的配合我不可能完成這次課程設(shè)計(jì)！8 附錄：#include #include #include #define M 10000 #define N 128 typedef struct node int weight;struct node *LChild,*RChild,*Parent; struct node *next; HFMNode,*HFMTree;typed

17、ef struct char ch; char codeN+1; int start; CodeNode;int n; void clearscreen()system(cls);void Open(char s) char name10;FILE *fp;int i=0;printf(請輸入要打開的文件名：);gets(name); if(fp=fopen(name,rt)=NULL)printf(打開失??！n); exit(1);si+=fgetc(fp);while(si-1!=EOF)si+=fgetc(fp);si=0; fclose(fp);void Save(char s) ch

18、ar name10;FILE *fp;printf(請輸入要保存的文件名：);gets(name);if(fp=fopen(name,wt)=NULL)printf(存儲失?。?;exit(1);fputs(s,fp);printf(n保存成功，文件名為:%s。n,name);printf(n按回車鍵繼續(xù).);getchar();fclose(fp);void SearchStr(char s,char str,int count) int i,j,k=0;for(i=0;iN;i+) counti=0;for(i=0;si;i+)for(j=0;jk;j+) if(strj=si)count

19、j+;break;if(j=k) strk=si;countk+;strk=0; n=k; void SelectMin(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2)int i,min;HFMTree p;min=32767;for(i=0,p=HT;inext)if(p-weightParent=0)min=p-weight;*HT1=p;min=32767;for(i=0,p=HT;inext)if(p-weightParent=0&p!=*HT1) min=p-weight;*HT2=p;void CreatHFMTree(HFMTree *HT

20、,int count)int i;HFMTree p,HT1,HT2; p=*HT=(HFMTree)malloc(sizeof(HFMNode);p-next=p-LChild=p-RChild=p-Parent=NULL; for(i=1;inext=(HFMTree)malloc(sizeof(HFMNode);p=p-next;p-next=p-LChild=p-RChild=p-Parent=NULL;for(i=0,p=*HT;iweight=counti;p=p-next;for(i=n;iParent=HT2-Parent=p; p-LChild=HT1;p-RChild=HT

21、2;p-weight=HT1-weight+HT2-weight; p=p-next; void HFMCode(HFMTree HT,CodeNode HC,char str)int i;HFMTree q,p=HT;for(i=0;in;i+) HCi.ch=stri;HCi.coden-1=0; for(i=0;iParent;q=q-Parent) if(q=q-Parent-LChild)HCi.code-HCi.start=0;elseHCi.code-HCi.start=1;p=p-next; void TotalCoding(char s,CodeNode HC,char co

22、de)int i,j;code0=0; for(i=0;si;i+) for(j=0;jParent;root=root-Parent); for(i=0,p=root;codei;i+) if(codei=0)p=p-LChild;elsep=p-RChild;if(p-LChild=NULL&p-RChild=NULL) for(j=0,q=HT;q!=p;q=q-next,j+);sk+=strj;p=root; iksk=0; void Coding(char s,char str,char code,int count,HFMTree *HT,CodeNode HC)clearscreen();printf(n打開存放字符串的文件.nn);Open(s); SearchStr(s,str,count); CreatHFMTree(HT,count);HFMCode(*HT,HC,str); TotalCoding(s,HC,code); printf(n讀入的字符串為:n);puts(s);printf(n最終的哈夫曼編碼是:n);puts(code);printf(n保存編碼,);Save(code); void TransCode(char code,char str,char ss,HFMTree *HT,Cod