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

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

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

3、行， 我們 可以逐步積累調(diào)試 C 程序的經(jīng)驗(yàn)并逐漸培養(yǎng)我們的編程能力、 用計(jì)算機(jī)解決實(shí)際 問(wèn)題的能力。在課程設(shè)計(jì)過(guò)程中， 我們不但有自己的獨(dú)立思考， 還借助各種參考文獻(xiàn)來(lái)幫 助我們完成系統(tǒng)。 更為重要的是， 我們同學(xué)之間加強(qiáng)了交流， 在對(duì)問(wèn)題的認(rèn)識(shí)方 面可以交換不同的意見(jiàn)。 同時(shí)，師生之間的互動(dòng)也隨之改善， 我們可以通過(guò)具體 的實(shí)例來(lái)從老師那學(xué)到更多的實(shí)用的知識(shí)。數(shù)據(jù)結(jié)構(gòu)課程具有比較強(qiáng)的理論性，同時(shí)也具有較強(qiáng)的可應(yīng)用性和實(shí)踐性。 課程設(shè)計(jì)是一個(gè)重要的教學(xué)環(huán)節(jié)。 我們?cè)谝话闱闆r下都能夠重視實(shí)驗(yàn)環(huán)節(jié)， 但是 容易忽略實(shí)驗(yàn)的總結(jié)， 忽略實(shí)驗(yàn)報(bào)告的撰寫。 通過(guò)這次實(shí)驗(yàn)讓我們明白： 作為一 名大學(xué)生必須

4、嚴(yán)格訓(xùn)練分析總結(jié)能力、 書面表達(dá)能力。 需要逐步培養(yǎng)書寫科學(xué)實(shí) 驗(yàn)報(bào)告以及科技論文的能力。只有這樣，我們的綜合素質(zhì)才會(huì)有好的提高。2 需求分析課 題：哈夫曼編碼譯碼器問(wèn)題描述： 打開一篇英文文章， 統(tǒng)計(jì)該文章中每個(gè)字符出現(xiàn)的次數(shù)， 然后以它們作為權(quán)值，對(duì)每一個(gè)字符進(jìn)行編碼， 編碼完成后再對(duì)其編碼進(jìn)行譯碼。問(wèn)題補(bǔ)充： 1. 從硬盤的一個(gè)文件里讀出一段英語(yǔ)文章；2. 統(tǒng)計(jì)這篇文章中的每個(gè)字符出現(xiàn)的次數(shù)；3. 以字符出現(xiàn)字?jǐn)?shù)作為權(quán)值，構(gòu)建哈夫曼樹，并將哈夫曼樹的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)進(jìn)行輸出；4. 對(duì)每個(gè)字符進(jìn)行編碼并將所編碼寫入文件然后對(duì)所編碼進(jìn)行破譯。具體介紹：在本課題中， 我們?cè)谟脖P中預(yù)先建立一

5、個(gè)文檔， 在里面編輯一篇文章。 然后運(yùn)行程序， 調(diào)用函數(shù)讀出該文章， 顯示在界面； 再調(diào)用函數(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)用函數(shù)構(gòu)建哈夫曼樹； 并調(diào)用函數(shù)將哈夫曼的存 儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)進(jìn)行輸出。 然后調(diào)用函數(shù)對(duì)哈夫曼樹進(jìn)行編碼， 調(diào)用函數(shù)將 編碼寫入文件；再調(diào)用對(duì)編碼進(jìn)行譯碼，再輸出至界面。至此，整個(gè)工作就完成 了3 概要設(shè)計(jì)對(duì)系統(tǒng)進(jìn)行分析，給出系統(tǒng)結(jié)構(gòu)圖；廠哈弗曼樹編碼譯碼器編碼譯碼退出Pare nt;q=q-Pare nt)ode-HCi.start=0;else HCi.code-HCi.s

6、tart=1;p=p-n ext;行程序得到如下界面:*Met1-編碼。*2 -譯確7-M-M*E退出-344(沁請(qǐng)輸入相應(yīng)撼作的序號(hào)沏3 -圖6主界面運(yùn)行截圖2.選擇1,按回車鍵，在輸入對(duì)字符串進(jìn)行編碼，得到如下界面打開存赦字符串的文件-務(wù)輸入要打幵的文件名=txti.txt諫人的字符串為二-le llo eeryboidvt Huf Fman codec debuwinig ppocess Is uery in te ire st io g 豊最終的噲大曼編碼是：1111011O1311100111H1H110H01 si Bin lieiflBi01 lninenmi mi 110611

7、011180in00ini0 ii 00i0ie0iii00iiii0ei0iie0iie0ii008iii0iiiiiiiii80i0ii lieieseiiioei 0110000100100 10001006181001101000001101000018111111110110101160110000010101160000111110100161 10110訶fum flnmi hari ni 洌int hi 1011nt hfh ifurfu11 hihh mftft保存編碼請(qǐng)輸入曼保存的文件各.圖7編碼運(yùn)行截圖3. 輸入按回車鍵保存哈弗曼編碼:保存編碼尸請(qǐng)輸入要保存的文件名:tx

8、t2 -txt保存成功，文件名為:txt2.txto按叵車犍繼續(xù)圖8保存編碼運(yùn)行截圖4. 輸入按回車鍵進(jìn)行譯碼得到如下界面：打開扁碼的文件-請(qǐng)輸入要打尸的文件茗：txts-txt得到的最終字符串為：,Hello euepybodly1* Huffman codec debugrsfing process is uery interesting?保存譯碼.請(qǐng)輸入聲保存的立件名匚圖9譯碼運(yùn)行截圖6總結(jié)通過(guò)一周的課程設(shè)計(jì)使我對(duì)哈夫曼樹以及哈夫曼編碼有了更深的認(rèn)識(shí)和理 解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。首先我談?wù)勎以谠O(shè)計(jì)期間我遇到的難點(diǎn)。開始的時(shí)候，代碼中有許多的錯(cuò)誤,特別是

9、有一個(gè)“無(wú)法找到文件”的錯(cuò)誤讓我束手無(wú)策，最后還是屏蔽了定義的四 個(gè)頭文件然后慢慢地改正錯(cuò)誤才讓我又看到了希望。然后在實(shí)現(xiàn)文章的讀入時(shí)， 由于對(duì)文件不是太熟悉， 只好翻開 C 語(yǔ)言書本仿照其模式編寫。 許多的錯(cuò)誤讓我 明白了一個(gè)道理 - 細(xì)心是非常重要的。同時(shí)，對(duì)于編程者而言，思路清晰是相 當(dāng)重要的。 在適當(dāng)?shù)臅r(shí)候和同學(xué)一起交流探討是一個(gè)十分好的學(xué)習(xí)機(jī)會(huì)。 請(qǐng)教老 師也很重要，因?yàn)楫吘刮覀兪切率郑瑢?duì)于某些問(wèn)題很難弄清楚。而且，某些錯(cuò)誤 對(duì)于我們來(lái)說(shuō)有時(shí)候想半天都弄不來(lái)， 但老師幾下下就搞好了， 這樣就更加有效 地節(jié)約了時(shí)間。這次課程設(shè)計(jì)不但讓我學(xué)得了一些編程知識(shí)， 還學(xué)會(huì)了系統(tǒng)的做一份課程設(shè)

10、計(jì)報(bào)告，學(xué)會(huì)了如何截圖， 學(xué)會(huì)了如何更好的畫流程圖， 明白了做事情只有認(rèn)真， 才能真正做得更好！這段時(shí)間里，可謂是酸甜苦辣都嘗過(guò)。有時(shí)，為了一個(gè)錯(cuò)誤而焦頭爛額；有 時(shí)，連吃飯都是匆匆了事；但一旦程序運(yùn)行成功，總會(huì)讓我興奮不已。通過(guò)這次課程設(shè)計(jì)， 我看清楚了自己的編程功底和動(dòng)手能力還不如人意， 這 主要是平時(shí)實(shí)踐太少的緣故。 我想， 在未來(lái)的暑假中， 我會(huì)努力嘗試編寫一些程 序。雖然我們信息管理專業(yè)的學(xué)生， 但現(xiàn)在編程的能力太差了， 畢竟多精通一門 技術(shù)總是好事。在這個(gè)程序中， 還有許多地方值得完善。 比如，讀出文本只能是大寫的文檔， 空格和小寫不能識(shí)別，更不用說(shuō)是任意的 AS5碼字符了。由于時(shí)

11、間問(wèn)題，暫時(shí) 不能實(shí)現(xiàn)了。我想在暑假里好好研究這個(gè)問(wèn)題7 致謝 在這次設(shè)計(jì)中我要感謝與我同組的兩位同學(xué)喻霞林和董茗桓， 有很多不懂得 地方我們可以互相討論研究，沒(méi)有他們的配合我不可能完成這次課程設(shè)計(jì)！8 附錄 ：#include #include #include #define M 10000#define N 128 typedef struct nodeint weight;struct node *LChild,*RChild,*Parent;struct node *next;HFMNode,*HFMTree;typedef structchar ch;char codeN+1; i

12、nt start;CodeNode;int n;void clearscreen() system(cls);void Open(char s)char name10;FILE *fp;int i=0;printf( 請(qǐng)輸入要打開的文件名： ); 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) char name10; FILE *fp;printf( 請(qǐng)輸入要保存

13、的文件名： ); gets(name);if(fp=fopen(name,wt)=NULL)printf( 存儲(chǔ)失敗！ ); 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)countj+;break;if(j=k)strk=si;c

14、ountk+;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,int count)int i;HFMTree

15、 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=HT2;p-weight=HT1-weight+H

16、T2-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;else HCi.code-HCi.start=1;p=p-next;void TotalCoding(char s,CodeNode HC,char code)int i,j;code0=0;for(i

17、=0;si;i+)for(j=0;jParent;root=root-Parent); for(i=0,p=root;codei;i+)if(codei=0)p=p-LChild;else p=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 打開存放字符串的文件

18、.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,CodeNode HC) clearscreen(); printf(n打開編碼的文件 .nn);Open(code);DeCoding(code,*HT,str,ss);printf(n 得到的最終字符串為 :n); puts(ss);printf(n