數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(哈夫曼編碼)

1、目 錄 1丨 1課程設(shè)計的目的和意義 22需求分析 33系統(tǒng)設(shè)計 4|(1)設(shè)計思路及方案 4裝(2)模塊的設(shè)計及介紹 4；(3)主要模塊程序流程圖 64系統(tǒng)實現(xiàn) 10訂(1) 主調(diào)函數(shù) 10(2) 建立 HuffmanTree 10(3) 生成Huffman編碼并寫入文件 13線(4) 電文譯碼 145系統(tǒng)調(diào)試 16小 結(jié) 18參考文獻 19i 附錄源程序 201課程設(shè)計的目的和意義在當(dāng)今信息爆炸時代，如何采用有效的數(shù)據(jù)壓縮技術(shù)來節(jié)省數(shù)據(jù)文件的存儲空間 和計算機網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視。哈夫曼編碼正是一種應(yīng)用廣泛且 非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得

2、的用于通信的二進制編碼稱為哈夫 曼編碼。樹中從根到每個葉子都有一條路徑， 對路徑上的各分支約定：指向左子樹的 分支表示“0”碼，指向右子樹的分支表示“ 1”碼，取每條路徑上的“ 0”或“ T的 序列作為和各個對應(yīng)的字符的編碼，這就是哈夫曼編碼。通常我們把數(shù)據(jù)壓縮的過程稱為編碼， 解壓縮的過程稱為解碼。電報通信是傳遞 文字的二進制碼形式的字符串。但在信息傳遞時，總希望總長度盡可能最短，即采用 最短碼。作為軟件工程專業(yè)的學(xué)生，我們應(yīng)該很好的掌握這門技術(shù)。 在課堂上，我們能過 學(xué)到許多的理論知識，但我們很少有過自己動手實踐的機會！ 課程設(shè)計就是為解決這 個問題提供了一個平臺。在課程設(shè)計過程中，我們每

3、個人選擇一個課題，認真研究，根據(jù)課堂講授內(nèi)容， 借助書本，自己動手實踐。這樣不但有助于我們消化課堂所講解的內(nèi)容，還可以增強 我們的獨立思考能力和動手能力；通過編寫實驗代碼和調(diào)試運行，我們可以逐步積累 調(diào)試C程序的經(jīng)驗并逐漸培養(yǎng)我們的編程能力、用計算機解決實際問題的能力。在課程設(shè)計過程中，我們不但有自己的獨立思考，還借助各種參考文獻來幫助我 們完成系統(tǒng)。更為重要的是，我們同學(xué)之間加強了交流，在對問題的認識方面可以交 換不同的意見。同時，師生之間的互動也隨之改善，我們可以通過具體的實例來從老 師那學(xué)到更多的實用的知識。數(shù)據(jù)結(jié)構(gòu)課程具有比較強的理論性， 同時也具有較強的可應(yīng)用性和實踐性。 課程 設(shè)計

4、是一個重要的教學(xué)環(huán)節(jié)。我們在一般情況下都能夠重視實驗環(huán)節(jié)，但是容易忽略 實驗的總結(jié)，忽略實驗報告的撰寫。通過這次實驗讓我們明白：作為一名大學(xué)生必須 嚴格訓(xùn)練分析總結(jié)能力、書面表達能力。需要逐步培養(yǎng)書寫科學(xué)實驗報告以及科技論 文的能力。只有這樣，我們的綜合素質(zhì)才會有好的提高。2需求分析題目：哈夫曼編碼/譯碼器問題描述：利用哈夫曼編碼進行信息通信可以大大提高信道利用率，縮短信息傳輸時 間，降低傳輸成本。但是這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù) 先編碼；在接收端將傳來的數(shù)據(jù)進行譯碼(復(fù)原)。對于雙工信道(即可 以雙向傳輸信息的信道)，每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣 的信息收發(fā)站寫一

5、個哈夫曼碼的編譯碼系統(tǒng)。具體要求：1) 初始化：鍵盤輸入字符集大小n及n個字符和m個權(quán)值，建立哈夫 曼樹，并將它存于文件 hfmtree中。2) 編碼：利用建好的哈夫曼樹，對文件tobetrans中的正文進行編碼， 然后將結(jié)果存入文件codefile中。3) 解碼：利用建好的哈夫曼樹將文件codefile中的代碼進行譯碼，結(jié)果存入文件textfile中。4) 打印代碼文件：將文件 codefile 以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件codepri nt中。5) 打印哈夫曼樹：將已在內(nèi)存中的哈夫曼樹以直觀的方式(樹或凹入表形式)顯示在終端上，同時將此字符形

6、式的哈夫曼樹寫入文件treepri nt 中。6) 設(shè)字符集及頻度如下表:字符空 格ABCDEFGHIJKLM頻度1866423223210321154757153220字符NOPQRSTUVWXYZ頻度205619250515530101122123系統(tǒng)設(shè)計(1) 設(shè)計思路及方案本課題是用最優(yōu)二叉樹即哈夫曼樹來實現(xiàn)哈夫曼編碼譯碼器的功能。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為 W，編碼長度為Li，電文中有n種字符，則電文編碼總長 度為(W1*L1)+(W2*L2)+(Wi*Li)。若將此對應(yīng)到二叉樹上，Wi為葉結(jié)點，Li為根結(jié)點到葉結(jié)點的路徑長度。那么，(W1*L1)+(W2*L2)+(Wi*Li

7、)恰好為二叉樹上帶權(quán) 路徑長度。因此，設(shè)計電文總長最短的二進制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵哈夫曼樹，此構(gòu)造過程稱為哈夫曼編碼。該系統(tǒng)將實現(xiàn)以下幾大功能：從硬盤讀取字符串，建立哈夫曼樹，輸出哈夫曼樹 的存儲結(jié)構(gòu)的初態(tài)和終態(tài)，輸出各種字符出現(xiàn)的次數(shù)以及哈夫曼編碼的譯碼等。(2) 模塊的設(shè)計及介紹 從硬盤讀取字符串fileopen(參數(shù))實現(xiàn)命令；打印輸出； 建立 HuffmanTree通過三個函數(shù)來實現(xiàn)：void select(參數(shù))初始化；for接受命令；處理命令；說明：在ht1.k 中選擇pare nt為0且權(quán)值最小的兩個根結(jié)點的算法int jsq(參數(shù)):初始化；for:

8、接受命令；丨處理命令；裝丨說明：統(tǒng)計字符串中各種字母的個數(shù)以及字符的種類void Chuffma nTree()訂:初始化；for線:接受命令；處理命令；:輸出字符統(tǒng)計情況；丨說明：構(gòu)造哈夫曼樹輸出哈夫曼樹的存儲結(jié)構(gòu)的初態(tài)和終態(tài)分別調(diào)用print1()和print2()來實現(xiàn)void prin t1( 參數(shù))初始化；輸出初態(tài)；說明：輸出哈夫曼樹的初態(tài)void prin t2（參數(shù)）for丨輸出終態(tài)；1說明：輸出哈夫曼樹的終態(tài)裝哈夫曼編碼和譯碼void HuffmanEncoding（參數(shù)）丨定義變量；訂:處理命令；線1說明：哈夫曼編碼char*decode（參數(shù)）1定義變量；while1接受命

9、令；1處理命令；說明：哈夫曼譯碼（3）主要模塊程序流程圖下面介紹三個主要的程序模塊流程圖: 主函數(shù)流程圖:圖3.1流程圖注釋：該圖比較簡單，主要是調(diào)用各個函數(shù)模塊，首先代開已經(jīng)存在的文件，然后統(tǒng)計總的 字符數(shù)以及出現(xiàn)的各個字符和頻率。然后才開始建立哈夫曼樹，接著在哈夫曼樹的基 礎(chǔ)上對其進行編碼，編碼之后才是譯碼。最后輸出結(jié)束。 構(gòu)造哈夫曼樹:圖3.2流程圖注釋：該圖是表示構(gòu)造哈夫曼樹的過程。首先輸入num個葉結(jié)點的權(quán)值，當(dāng)i=num是循環(huán)結(jié) 束。然后進行哈夫曼樹的構(gòu)建，當(dāng)i= 2*num-1是循環(huán)結(jié)束。最后輸出所得到的字符統(tǒng) 計情況。 哈夫曼編碼:圖3.3流程圖解釋：該流程圖表四哈夫曼編碼情況

10、。首先初始化， Cd-start=O,start=num。然后進行編碼，使用了一個三目運算符。cd-start=(Tp.lchild=c) ? O : 1，即當(dāng) cd-start=Tp.lchild= =c 時，cd-start=0 ;當(dāng) cd-start=Tp.lchild ！ = =c 時， cd-start=1。這個編碼循環(huán)一直到i=num時結(jié)束。4系統(tǒng)實現(xiàn)丨各模塊關(guān)鍵代碼及算法的解釋：main函數(shù)里的各個函數(shù)調(diào)用情況。從硬盤中讀取文件統(tǒng)計字符種類及各類字符出現(xiàn)的頻率丨 (1)主調(diào)函數(shù) 丨代碼解釋：這是fileope n( stri ng);/num =jsq(stri ng,c nt,

11、str); /Dhuffma nTree(HT,c nt,str); printf(HuffmanTree 的初態(tài):n);輸出哈夫曼樹的初態(tài)建立哈夫曼樹生成哈夫曼編碼輸出哈夫曼樹的終態(tài)讀編碼文件譯碼輸出譯碼后的字符串中選擇pare nt為0且權(quán)值最小的兩個根裝prin t1(HT);/Chuffma nTree(HT,HC,c nt,str);Huffma nEn codi ng(HT,HC); /訂printf(HuffmanTree 的終態(tài):nprin t2(HT);/s=decode(HC);/丨printf(譯碼后的字符串:n);線prin tf(%sn,s);/(2)建立 Huffm

12、anTreeI代碼解釋：該函數(shù)為在ht1.k|結(jié)點的算法，其序號為s1和s2。void select(HuffmanTree T,int k,int &s1,int &s2)int i,j;in t min 1=101;for(i=1;i=k;i+)if(Ti.weightmi n1 &Ti.pare nt=0)j=i;m in 1=Ti.weight;s1=j;mi n仁32767;for (i=1;i=k;i+)if(Ti.weight=A&*p=Z)k=*p-64; tempk+;丨/統(tǒng)計各種字符的個數(shù)for(i=1,j=0;i=26;+i)if(tempi!=0 )j+;送對應(yīng)的字母到

13、數(shù)組中存入對應(yīng)字母的權(quán)值strj=i+64;/cn tj=tempi; /丨return j; /j是輸入字母總數(shù):代碼解釋：下面函數(shù)用來構(gòu)造哈夫曼樹HT。首先初始化哈夫曼樹，然后輸丨入前面統(tǒng)計的各結(jié)點的權(quán)值，用for循環(huán)來構(gòu)造哈夫曼樹。void Chuffma nTree(Huffma nTree HT,Huffma nCode HC,i nt cnt,char str)int i,s1,s2;裝for(i=1;i=2*num-1;i+)初始化 HT, 2*num-1 是指哈夫曼I/所有的結(jié)點數(shù)目HTi.lchild=O;HTi.rchild=O;訂HTi.pare nt=0;HTi.wei

14、ght=0;for(i=1;i=num;i+) / 輸入num個葉結(jié)點的權(quán)值線HTi.weight=cnti;for(i 二nu m+1;i=2* nu m-1;i+)select(HT,i-1,s1,s2);HTs1.pare nt=i;HTs2.pare nt=i;HTi.lchild=s1; HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;1/在ht1.k 中選擇pare nt為0且權(quán)值最小/的兩個根結(jié)點,其序號為s1和s2,i為雙親for(i=0;i=nu m;i+) / 輸入字符集的中字符HCi.ch=stri; /字符的種類i=1;

15、while(i=num)printf( 字符 %c次數(shù) :%dn,HCi.ch,c nti+);/輸出統(tǒng)計的情況生成Huffman編碼并寫入文件代碼解釋：根據(jù)哈夫曼樹 T求哈夫曼編碼H。void Huffma nEn codi ng(Huffma nTree T,Huffma nCode H) int c,p,i;/c和p分別扌曰示t中孩子和雙親char cd n;/臨時存放編碼串int start;/指示碼在cd中的起始位置cd num=0;/最后一位(第num個)放上串結(jié)束符for(i=1;i0) /直至上溯到tc是樹根為止cd-start=(Tp.lchild=c) ? O : 1;c=

16、p；/若tc是tp的左孩子/則生成0;否則生成底碼1strcpy(Hi.bits,&cdstart);Hi.le n=nu m-start;代碼解釋：對str所代表的字符串進行編碼并寫入文件。將翻譯的二進制碼寫入 文本文件。void codi ng(Huffma nCode HC ,char *str)int i,j;FILE *fp;fp=fope n(codefile.txt,w);while(*str)for(i=1;i=nu m;i+)if(HCi. ch=*str)for(j=0;jv=HCi.le n;j+)fputc(HCi.bitsj,fp); break;sM+;fclose

17、(fp);電文譯碼代碼解釋：代碼文件codefile.txt char*decode(Huffma nCode HC) FILE *fp;char str254;/char *p;static char cd n+1;int i,j,k=0,cjs;fp=fope n(codefile.txt,r);while(!feof(fp)/feof(fp)feof(fp)=1的譯碼，將翻譯的二進制碼譯成原來的字符假設(shè)遠文本文件不超過254個字符一只讀的方式打開文本文檔/codefile.txt判斷文件是否真正結(jié)束，時文件結(jié)束cjs=0;for(i=0;iee2 18的纟冬態(tài)：Q011500115001

18、160B116&0321003220a216G011700322eR423002190011?002190a22023220452219134231842412144241G1652S1?662571082611188261920112721221&272324270252&圖5.4輸出譯碼后的字符（見圖5.5）譯碼后的字符串：IMIS FPOGRAM IS n? FfiUORlTE鬥 耳 ：M 斃 JC 屛 K X XXXXJOCJCXMIJtMiXlCKlCXKKXlCXJCltXlOCJtMrJCJCJCXJtKXPress 凰ny hey to continue圖5.5由此可見，此次測

19、試很成功。我們能夠?qū)⑽谋疚臋n中的文段讀出，并將其統(tǒng)計 并輸出字符種類和每種字符出現(xiàn)的頻率。同時輸出哈夫曼樹存儲結(jié)構(gòu)的初態(tài)和終態(tài)。 然后輸出譯碼后的字符。通過一周的課程設(shè)計使我對哈夫曼樹以及哈夫曼編碼有了更深的認識和理解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。首先我談?wù)勎以谠O(shè)計期間我遇到的難點。開始的時候，代碼中有許多的錯誤，特別是有一個“無法找到文件”的錯誤讓我束手無策，最后還是屏蔽了定義的四個頭文 件然后慢慢地改正錯誤才讓我又看到了希望。 然后在實現(xiàn)文章的讀入時，由于對文件 不是太熟悉，只好翻開C語言書本仿照其模式編寫，但后來進入了死循環(huán)，最后的解 決方式是把main函數(shù)里

20、的一個dowhile循環(huán)去掉。在程序中，我還另外加了一個 功能-輸出哈夫曼樹的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。 這使得我更加的明白了哈夫曼到底 是怎么存儲信息的。許多的錯誤讓我明白了一個道理-細心是非常重要的。同時，對于編程者而言， 思路清晰是相當(dāng)重要的。在適當(dāng)?shù)臅r候和同學(xué)一起交流探討是一個十分好的學(xué)習(xí)機 會。請教老師也很重要，因為畢竟我們是新手，對于某些問題很難弄清楚。而且，某 些錯誤對于我們來說有時候想半天都弄不來，但老師幾下下就搞好了，這樣就更加有 效地節(jié)約了時間。這次課程設(shè)計不但讓我學(xué)得了一些編程知識，還學(xué)會了系統(tǒng)的做一份課程設(shè)計報 告，學(xué)會了如何截圖，學(xué)會了如何更好的畫流程圖，明白了做事情只有

21、認真，才能真 正做得更好！200720072006參考文獻1 嚴蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社,2 蘇仕華.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.機械工業(yè)出版社，3 譚浩強.C語言程序設(shè)計教程.高等教育出版社,附錄源程序#in elude #in elude #in elude #in elude/*類型相關(guān)變量的定義*#defi ne n 100/#defi ne m 2*n-1/typedef structchar ch;char bits9;/int len;CodeNode;typedef CodeNode Huffma nCode n+1; typedef struct int weight

22、;/int lchild,rchild,pare nt;/HTNode;typedef HTNode Huffma nTreem+1; int num;*葉子結(jié)點數(shù)哈夫曼樹中的結(jié)點樹存放編碼位串權(quán)值左右孩子幾雙親指針0號單元不用建立Huffma nTree*void select(HuffmanTree T,int k,int &s1,int &s2) / 在ht1.k 中選擇pare nt為0且權(quán)值最小的兩個根結(jié)點的算法 其序號為s1和s2int i,j;i nt min 1=101;for(i=1;i=k;i+)if(Ti.weightmi n1 &Ti.pare nt=0)j=i;m i

23、n 1=Ti.weight;s1=j;mi n1=32767;for (i=1;i=k;i+)if(Ti.weightmin1 & Ti.parent=0 & i!=s1)j=i;m in 1=Ti.weight;s2=j;int jsq(char *s,i nt cn t,char str) /統(tǒng)計字符串中各種字母的個數(shù)以及字符的種類int i,j,k;char *p;int temp27;for(i=1;i=A&*p=Z) k=*p-64;tempk+;for(i=1,j=0;i=26;+i) if(tempi!=O) 送對應(yīng)的字母到數(shù)組中 存入對應(yīng)字母的權(quán)值是輸入字母總數(shù)j+;strj=

24、i+64;/cntj=tempi;/return j;/j裝void Chuffma nTree(Huffma nTree HT,Huffma nCode HC,i nt cnt,char str)丨 II構(gòu)造哈夫曼樹 HTint i,s1,s2;丨for(i=1;i=2*num-1;i+) 初始化 HT, 2*num-1是指哈夫曼樹所有的結(jié)點數(shù)目HTichild=O;HTi.rchild=O;訂HTi.pare nt=0;HTi.weight=0;丨for(i=1;i=num;i+)II輸入num個葉結(jié)點的權(quán)值HTi.weight=c nti;for(i=n um+1;i=2* num_1;

25、i+)丨 II 在ht1.k 中選擇pare nt為0且權(quán)值最小的兩個根結(jié)點線II其序號為si和s2IIi為雙親 select(HT,i-1,s1,s2);HTs1.pare nt=i;HTs2.pare nt=i;HTi.lchild=s1; HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;for(i=0;i=nu m;i+)II輸入字符集的中字符HCi.ch=stri;II字符的種類i=1;while(i=num)printf(字符 %c次數(shù):%dn,HCi.ch,cnti+);II*生成Huffman編碼并寫入文件*void Huffma

26、 nEn codi ng(Huffma nTree T,Huffma nCode H)IIint c,p,i;IIcchar cd n;IIint start;IIcd num=0;IIfor(i=1;i0) II II根據(jù)哈夫曼樹T求哈夫曼編碼H和p分別指示t中孩子和雙親臨時存放編碼串指示碼在cd中的起始位置最后一位（第num個）放上串結(jié)束符初始位置從葉子結(jié)點ti開始上溯直至上溯到tc是樹根為止若tc是tp的左孩子，則生成0;否則生成底碼1cd-start=(Tpchild=c) ? O : 1：c=p;strcpy(Hi.bits,&cdstart);Hi.le n=nu m-start;

27、void cod in g(Huffma nCode HC ,char *str)/對str所代表的字符串進行編碼并寫入文件int i,j;FILE *fp;fp=fope n( codefile.txt,w);while(*str)for(i=1;i=nu m;i+)if(HCi. ch=*str)for(j=O;j=HCi.le n;j+)fputc(HCi.bitsj,fp);break;str+;fclose(fp);1 譯碼 *代碼文件codefile.txt 的譯碼假設(shè)遠文本文件不超過254個字符一只讀的方式打開文本文檔codefile.txt判斷文件是否真正結(jié)束，feof(fp)

28、=1時文件結(jié)束/*char*decode(Huffma nCode HC) /FILE *fp;char str254;/char *p;static char cdn+1;int i,j,k=O,cjs;fp=fope n(codefile.txt,r);/while(!feof(fp)/feof(fp)cjs=O;for(i=O;i num & cjs=O & !feof(fp);i+)cdi= ;cdi+1=O;cdi=fgetc(fp);數(shù)組接受從fp指針所指向文件中讀入的一個字符for(j=1;j=nu m;j+)if(strcmp(HCj.bits,cd)=O)/haffma n編碼和密碼譯碼相比較strk=HCj.ch;k+; cjs=1;break;strk=O;p=str;return p;*void prin t1(Huffma nTree HT)int x; for(x=1;x=2* num_1;x+)HTx.pare nt=O; HTx.lchild=O; HTx.rchild=O;輸出HuffmanTree存儲結(jié)構(gòu)*prin tf(%11d %dt %dt %dn,HT x .weight,HTx.