哈夫曼編碼譯碼器1

1、滁州學(xué)院課程設(shè)計報告課程名稱： 數(shù)據(jù)結(jié)構(gòu)設(shè)計題目：哈夫曼編碼譯碼器 系 別：計算機(jī)科學(xué)與技術(shù)專 業(yè)：網(wǎng)絡(luò)工程組 別： 第十組起止日期: 2011年4月28日 2011年5月23日 指導(dǎo)教師: 計算機(jī)科學(xué)與技術(shù)系2010年制課程設(shè)計題目哈夫曼編碼譯碼器組長學(xué)號班級系別計算機(jī)科學(xué)與技術(shù)專業(yè)網(wǎng)絡(luò)工程組員指導(dǎo)教師課程設(shè)計目的掌握哈夫曼編碼譯碼器的構(gòu)造以及懂得設(shè)計思想課程設(shè)計所需環(huán)境VC+環(huán)境課程設(shè)計任務(wù)要求基本了解哈夫曼編碼譯碼器的構(gòu)造原理課程設(shè)計工作進(jìn)度計劃序號起止日期工 作 內(nèi) 容分工情況郭金華 4月28日5月23日收集資料及構(gòu)建哈夫曼樹和打開文件函數(shù)構(gòu)建哈夫曼樹和打開文件函數(shù)朱錕4月28日5月2

2、3日收集資料及構(gòu)建哈夫曼樹和打開文件函數(shù)構(gòu)建哈夫曼樹和打開文件函數(shù)劉強(qiáng)4月28日5月23日編輯小結(jié)和構(gòu)建生成哈夫曼編碼的函數(shù)構(gòu)建能夠統(tǒng)計文件中字符的函數(shù)及其意義朱開發(fā)4月28日5月23日編輯小結(jié)和構(gòu)建生成哈夫曼編碼的函數(shù)構(gòu)建能夠統(tǒng)計文件中字符的函數(shù)及其意義高鵬飛4月28日5月23日編輯哈夫曼譯碼器中的譯碼器函數(shù)編輯哈夫曼譯碼器中的的譯碼器函數(shù)曹探4月28日5月23日編輯哈夫曼譯碼器中的譯碼器函數(shù)等其他的相關(guān)事宜編輯哈夫曼譯碼器中的譯碼器函數(shù)等其他的相關(guān)事宜教研室審核意見：教研室主任簽字： 年 月 日課程設(shè)計任務(wù)書目錄 1 課程設(shè)計的目的和意義。3 2 需求分析。4 3 系統(tǒng)（項目）設(shè)計。4 設(shè)

3、計思路及方案。4 模塊的設(shè)計及介紹。5 主要模塊程序流程圖。7 4 系統(tǒng)實現(xiàn)。7 主調(diào)函數(shù)。7 建立Huffman Tree。8 生成Huffman Tree。，。9 電文譯碼。10 5 小結(jié)。13 6系統(tǒng)調(diào)試。13 參考文獻(xiàn)。13 附錄 源程序。13。 1.課程設(shè)計的目的和意義隨著人民生活水平的提高，科學(xué)的進(jìn)步和通信技術(shù)的發(fā)展。人們在進(jìn)行通信的同時要求做到信息交流的保密性和快速準(zhǔn)確性，尤其是在軍事和高端科技方面。為了解決上面所提出的問題、實現(xiàn)該目的，設(shè)計出了一種快速可靠的編碼方式，即哈夫曼編碼。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。樹中從根到每個葉子都

4、有一條路徑，對路徑的各分支約定：指制定左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，去每條路徑的“0”或“1”的序列作為和各個對應(yīng)的字符編碼，這就是哈夫曼樹編碼。利用哈夫曼樹編碼進(jìn)行通信可以大大的提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。通常我們把數(shù)據(jù)壓縮的過程叫做編碼，解壓縮的過程叫做解碼。電報通信是傳遞文字的二進(jìn)制碼形式的字符串。但在信息傳遞時，總希望總長度盡可能最短，即采用最短碼。作為計算機(jī)系學(xué)生，我們應(yīng)該很好的掌握這門技術(shù)。在課堂上，我們能夠?qū)W到許多的理論知識，但我們很少有過自己動

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

6、環(huán)節(jié)。我們在一般情況下都能夠重視實驗環(huán)節(jié)，但是容易忽略實驗的總結(jié)，忽略實驗報告的撰寫。通過這次試驗我們明白：作為一名大學(xué)生必須嚴(yán)格訓(xùn)練分析總結(jié)能力、書面表達(dá)能力，需要逐步培養(yǎng)書寫實驗報告以及科技論文的能力。只有這樣，我們的綜合素質(zhì)會有好的提高。 2 需求分析課 題：哈夫曼編碼譯碼器系統(tǒng)問題描述：打開一篇英文文章，統(tǒng)計該文章中每個字符出現(xiàn)的次數(shù)，然后以它作為權(quán)值，對每一個字符進(jìn)行編碼，編碼完成再對其編碼進(jìn)行譯碼。問題補(bǔ)充：1. 從硬盤的一個文件里讀出一段英語文章； 2. 統(tǒng)計這篇文章中的每個字符出現(xiàn)的次數(shù)； 3.以字符出現(xiàn)字?jǐn)?shù)作為權(quán)值，構(gòu)建哈夫曼樹，并將哈夫曼樹的存儲結(jié)構(gòu)的初態(tài)和終態(tài)進(jìn)行輸出；

7、4.對每個字符進(jìn)行編碼并將所編碼寫入文件然后對所編碼進(jìn)行破譯。具體介紹：在本課題中，我們在硬盤E盤中預(yù)先建立一個filel.txt文檔，在里面編輯一篇文章（大寫）。然后運(yùn)行程序，調(diào)用fileopen()函數(shù)讀出該文章，顯示在界面；再調(diào)用jsq()函數(shù)對該文章的字符種類進(jìn)行統(tǒng)計，并對每個字符的出現(xiàn)次數(shù)進(jìn)行統(tǒng)計，并且在界面上顯示；然后以每個字符出現(xiàn)次數(shù)作為權(quán)值，調(diào)用ChuffmanTree()函數(shù)構(gòu)建哈夫曼樹；并調(diào)用print1()和print2()函數(shù)將哈夫曼的存儲結(jié)構(gòu)的初態(tài)和終態(tài)進(jìn)行輸出。然后調(diào)用HuffmanEncoding（）函數(shù)對哈夫曼樹進(jìn)行編碼，調(diào)用coding（）函數(shù)將編碼寫入文件；

8、再調(diào)用decode（）對編碼進(jìn)行譯碼，再輸出到界面。至此，整個工作就完成了。測試數(shù)據(jù)：例如從文本中讀到文章為：IAMASTUDENT。 譯碼后的字符串：IAMASTUDENTPress any key to continue3 系統(tǒng)（項目）設(shè)計（1）設(shè)計思路及方案本課題是用最優(yōu)二叉樹即哈夫曼樹來實現(xiàn)哈夫曼編碼譯碼器的功能。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為Wi，編碼長度為Li，電文中有n種字符，則電文編碼總長度為（W1*L1）+(W2*L2)+.(Wi*Li)。若將此對應(yīng)到二叉樹上，Wi為葉結(jié)點(diǎn)，Li為根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長度。那么，（W1*L1）+(W2*L2)+.(Wi*Li) 恰好為二叉樹

9、上帶權(quán)路徑長度。因此，設(shè)計電文總長最短的二進(jìn)制前綴編碼，就是以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 接受命令； 處理命令； 說明：在htl.k中選擇parent為0且權(quán)值最小的兩個根結(jié)點(diǎn)的算法int jsq（參數(shù)） 初始化； for 接受命令； 處理命

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

11、夫曼譯碼 哈夫曼編碼： 流程圖解釋：該流程圖表示哈夫曼編碼情況。首先初始化，Cd-start=0,start=num.然后進(jìn)行編碼，使用了一個三目運(yùn)算符。Cd-start=(Tp.lchild=c)?0:1,即當(dāng)cd-start=Tp.lchild=c時，cd-start=0;當(dāng)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)鍵代碼及算法的解釋： 主調(diào)函數(shù) 代碼解釋：這是main函數(shù)里的各個函數(shù)調(diào)用情況。 fileopen（string）； /從C盤內(nèi)中讀取文件 num=jsq(string,

12、cnt,str); /統(tǒng)計字符種類及各類字符出現(xiàn)的頻率 DhuffmanTree(HT,cnt,str); printf(“HuffmanTree的初態(tài)：n”); print1(HT); /輸出哈夫曼樹的初態(tài) ChuffmanTree(HT,HC,cnt,str); /建立哈夫曼樹 HuffmanEncoding(HT,HC); /生成哈夫曼編碼 printf(“HuffmanTree的終態(tài)：n”); print2(“HuffmanTree的終態(tài)：n”); printf(“%sn”); /輸出譯碼后的字符串 建立HuffmanTree 代碼解釋：該函數(shù)為在htl.k中選擇patent為0且權(quán)值

13、最小的根結(jié)點(diǎn)的算法，其序號為s1和s2.void select (HuffmanTree T,int k,int &s1,int &s2) int i, j; s2=s1 for(i=1;i<=k;i+) if(Ti.weight<min1 &&Ti.patent=0) j=i; min1=Ti.weight;s1=j; min1=32767;for(i=1;i<=k;i+) if(Ti.weight<min1 &&Ti.patent=0 &&i!=s1) j=i; min1=Ti.weight;s2=j;

14、對所有的字母進(jìn)行統(tǒng)計種類和出現(xiàn)的次數(shù)int jsp(char *s,int cnt,char str) int i ,j,k; char *p; int temp27;for(i=1;i<=26;i+) tempi=0;for(p=s;*p!=0;p+) if(*p>=A&&*p<=Z) k=*p-64;/找到該字母的位置 tempk+;/統(tǒng)計各種字符的個數(shù)for（i=1,j=0;i<=26;+i） if(tempi!=0) j+; strj=i+64; /送對應(yīng)字母到數(shù)組中 cntj=tempi; /存入對應(yīng)字母的權(quán)值return j； /j是輸入字母

15、總數(shù)代碼解釋：下面函數(shù)用來構(gòu)造哈夫曼樹HT。首先初始化哈夫曼樹，然后輸入前面統(tǒng)計的各個結(jié)點(diǎn)的權(quán)值，用for循環(huán)來構(gòu)造哈夫曼樹。void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt,char str) int i,s1 ,s2; for(i=1;i<=2*num-1;i+) /初始化HT，2*num-1是指哈夫曼所有的節(jié)點(diǎn)數(shù)目 HTi.lchild=0;HTi.rchild=0; HTi.patent=0;HTi.weight=0;for(i=1;i<=num;i+) /輸入num個葉結(jié)點(diǎn)的權(quán)值 HTi.weight=cnti

16、;for(i=num+1;i<=2*num-1;i+) select(HT,i-1,s1,s2); HTs1.patent=i;HTs2.patent=i; HTi.lchild=s1;HTi.rchild=s2; HTiweight=HTs1.weight*HTs2.weight; /在htl.k中選擇patent為0且權(quán)值最小的兩個根結(jié)點(diǎn)，其序號為s1和s2，i為雙親for（i=0；i<=num；i+）； /輸入字符集中字符HCi.ch=stri; /字符種類i=1;while(i<=num) printf(“字符%c次數(shù)：%d”,HCi.ch,cnti+); /輸出統(tǒng)計

17、的情況 生成Huffman編碼并寫入文件 代碼解釋：根據(jù)哈夫曼樹T求哈夫曼編碼H。 void HuffmanEncoding (HuffmanTree T,HuffmanCode H) int c,p,i; /c和p分別指示t中孩子和雙親 char cdn; /臨時存放編碼串 int start; /指示碼在cd中的起始位置 cdnum=0; /最后一位（第num個）放上串結(jié)束符 for(i=1;i<=num;+i) start=num; /初始位置 c=i; /從葉子結(jié)點(diǎn)ti開始上溯 while(p=Tc.patent)>0) /直至上溯到tc是樹根為止 Cd-start=(Tp

18、.lchild=c) ?0:1; c=p; /若tc是tp的左孩子則生成0；否則生成1Strcpy(Hi.bits,*cdestart);Hi.len=num-start;代碼解釋：對str所代表的字符串進(jìn)行編碼并寫入文件。將翻譯的二進(jìn)制碼寫入文本文件。void coding(HuffmanCode HC, char *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.bit

19、sj,fp); break;str+; fclose(fp);電文譯碼 代碼解釋：代碼文件codefile。Txt的譯碼，將翻譯的二進(jìn)制碼譯成原來的字符。char *decode(HuffmanCode HC)FILE *fp;char str254; /假設(shè)原文本文件不超過254個字符char *p;static char cdn+1;int i,j,k=0,cjs;Fp=fopen(“codefile.txt”,”r”); /一只讀的方式打開文本文檔codefile。Txtwhile(!feof(fp) /feof（fp）判斷文件是否真正結(jié)束，feof(fp)=1時文件結(jié)束 cjs=0;

20、For(i=0;i<num&&cjs=0&&!feof(fp);i+) Cdi= Cdi+1=0; Cdi=fgetc(fp); /數(shù)組接收從fp指針?biāo)赶蛭募凶x入的一個字符 for（j=1;j<=num;j+） if(strcmp(HCj.bits,cd)=0) strk=HCj.ch; k+; cjs=1;break; /haffman編碼和密碼譯碼相比較strk=0;p=str;return p;5 系統(tǒng)調(diào)試本次測試是在我的電腦的E盤中建立一個名為file1.txt的文本文檔，其中有大寫字母IAMASTUDENT,期望程序能將其讀出至界面并實

21、現(xiàn)其它相關(guān)的功能。 運(yùn)行程序后，我們可以見到以下運(yùn)行界面。輸出哈夫曼樹存儲結(jié)構(gòu)的初態(tài) 輸出哈夫曼樹存儲結(jié)構(gòu)的終態(tài) 輸出譯碼后的字符 由此可見，此次測試很成功。我們能夠?qū)⑽谋疚臋nfile1.txt中的文段讀出，并將其統(tǒng)計輸出字符種類和每種字符出現(xiàn)的頻率。同時輸出哈夫曼樹存儲結(jié)構(gòu)的初態(tài)和終態(tài)。然后輸出譯碼后的字符。 小結(jié) -通過兩周的課程設(shè)計是我對哈夫曼樹以及哈夫曼編碼有了更深的認(rèn)識和理解，也使我更加明白了哈夫曼編碼譯碼在信息技術(shù)中的重要性地位。 首先我談?wù)勎以谠O(shè)計期間我遇到的難點(diǎn)。開始的時候，代碼中有許多的錯誤，特別是有一個“無法找到文件”的錯誤讓我束手無策，最后還是屏蔽了定義的四個頭文件然后慢

22、慢的改正錯誤才讓我又看到了希望。然后在實現(xiàn)文章的讀入時，由于對文件不是太熟悉，只好翻開C語言書本仿照其模式編寫，但后來進(jìn)入了死循環(huán)，最后的解決方式是把main函數(shù)里的一個do while循環(huán)去掉，在程序中，我還另外加了一個功能-輸出哈夫曼樹的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。這使得我更加的明白了哈夫曼到底是怎么存儲信息的。許多的錯誤讓我明白了一個道理-細(xì)心是非常重要的。同時，對于編程者而言，思路清晰是相當(dāng)重要的。在適當(dāng)?shù)臅r候和同學(xué)一起交流探討是一個十分好的學(xué)習(xí)機(jī)會。請教老師也很重要，因為畢竟我們是新手，對于某些問題很難弄清楚。而且，某些錯誤對于我們來說有時候想半天都弄不來，但老師幾下就搞好了，這樣就更加有

23、效的節(jié)約了時間。這段時間里，可謂是酸甜苦辣都嘗過。有時，為了一個錯誤而焦頭爛額；有時，變成熬夜到凌晨兩點(diǎn)；有時，連吃飯都是草草了事；但一旦程序運(yùn)行成功，總會讓我興奮不已。通過這次課程設(shè)計，我看清楚了自己的編程功底和動手能力還不如人意，這主要是平時是實踐太少的緣故。我想，在未來的暑假中，首先任務(wù)是編寫一些程序。雖然我們網(wǎng)絡(luò)工程專業(yè)的學(xué)生，但現(xiàn)在變成的能力太差了，畢竟多精通一門技術(shù)總是好事。在這個程序中，還有許多地方值得完善。比如，讀出文本只能是大寫的文檔，空格和小寫不能識別，更不用說是任意的ASCII碼字符了。由于時間問題，暫時不能實現(xiàn)了。 參考文獻(xiàn)【1】 嚴(yán)蔚敏，數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)

24、出版社，2007【2】 蘇仕華，數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，機(jī)械工業(yè)出版社，2007【3】 譚浩強(qiáng)，C語言程序設(shè)計教程，高等教育出版社，2006附錄：源程序# include< stdio.h># include<string.h># include<stdlib.h># include<fstream.h>/*類型相關(guān)變量的定義*# define n 100 /葉子結(jié)點(diǎn)數(shù)# define m 2*n-1 /哈夫曼樹中的結(jié)點(diǎn)數(shù)typedef struct char ch; /相關(guān)的字母 char bits9; /存放編碼位串 int len; /該字母編碼

25、的長度CodeNode; /編碼的類型typedef CodeNode HuffmanCoden+1; /所有的葉子結(jié)點(diǎn)的編碼數(shù)組typedef struct int weight; /權(quán)值 int lchild,rchild,parent; /左右孩子及雙親指針HTNode; /哈夫曼樹結(jié)點(diǎn)的類型typedef HTNode HuffmanTreem+1; /0號單元不用int num; /統(tǒng)計每種字母出現(xiàn)的次數(shù)和種類數(shù)目/建立HuffmanTree/ void select(HuffmanTree T,int k,int &s1,int &s2) /在ht1.k中選擇par

26、ent為0且權(quán)值最小的兩個根結(jié)點(diǎn)的算法 /其序號為s1和s2 int i,j;int min1=101; /min1的數(shù)字無何意義只是初始值之后用來記錄權(quán)值，i為循/環(huán) /最小權(quán)值的下標(biāo),k為數(shù)組結(jié)點(diǎn)的總數(shù) for(i=1;i<=k;i+) if (Ti.weight<min1 &&Ti.parent=0) j=i; min1=Ti.weight;/賦權(quán)值 s1=j; min1=32767;/找到權(quán)值最小的其中之一 for (i=1; i<=k; i+) if(Ti.weight<min1 &&Ti.parent=0 &&

27、 i!=s1)/不讓s2和s1的數(shù)組下標(biāo)重合 j=i ; min1=Ti.weight;/找到權(quán)值最小的其中之一 s2=j ;int jsq(char *s, int cnt ,char str)/str存放所有字符，cnt來存放每種字母的權(quán)值 /統(tǒng)計字符串中各種字母的個數(shù)以及字符的種類，s為數(shù)組/的首地址指針 int i,j,k; char *p; int temp27; /存每種字母的個數(shù) for(i=1;i<=26;i+) tempi=0; /初始化為0 for(p=s;*p!='0'p+) if(*p>='A' &&*p<

28、;='Z' ) k=*p-64; /找到字母在數(shù)組中的下標(biāo) tempk+; /字母個數(shù)累加 for(i=1,j=0;i<=26;+i) if( tempi !=0) j+; /j為字母的總數(shù) strj=i+64; /送對應(yīng)的字母到數(shù)組中 cntj=tempi; /存入對應(yīng)字母的權(quán)值 return j; /j是輸入字母總數(shù)void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt, char str) /構(gòu)造哈夫曼樹HT int i,s1,s2; for(i=1;i<=2*num-1;i+) /初始化HT，2*num

29、-1是指哈夫曼樹所有的結(jié)點(diǎn)數(shù)目 HTi.lchild=0;HTi.rchild=0; /初始化為根結(jié)點(diǎn) HTi.parent=0;HTi.weight=0; /初始化為根結(jié)點(diǎn) for(i=1;i<=num;i+) /輸入num個葉子結(jié)點(diǎn)的權(quán)值 HTi.weight=cnti; /賦權(quán)值 for(i=num+1;i<=2*num-1;i+) select(HT,i-1,s1,s2); /在ht1.k中選擇parent為0且權(quán)值最小的兩個根結(jié)點(diǎn) HTs1.parent=i;HTs2.parent=i; /其序號為s1和s2 HTi.lchild=s1;HTi.rchild=s2; /i

30、為雙親 HTi.weight=HTs1.weight+HTs2.weight; for(i=0;i<=num;i+) /輸入字符集的中字符 HCi.ch=stri; /字符的種類 i=1;while(i<=num) printf("字符%c次數(shù):%dn",HCi.ch,cnti+);/*生成Huffman編碼并寫入文件*void HuffmanEncoding(HuffmanTree T,HuffmanCode H) /根據(jù)哈夫曼樹T求哈夫曼編碼H int c,p,i; /c和p分別指示t中孩子和雙親 char cdn; /臨時存放編碼串，n為字母總數(shù) int

31、start; /指示碼在cd中的起始位置 cdnum='0' /num為葉子結(jié)點(diǎn)的總數(shù) for(i=1;i<=num;+i) /對所有的葉子節(jié)點(diǎn)進(jìn)行大循環(huán)的編碼 start=num; /重最后的葉子結(jié)點(diǎn)上溯編碼 c=i; /從葉子結(jié)點(diǎn)ti開始上溯 while(p=Tc.parent)>0) /直至上溯到tc是樹根為止 /若tc是tp的左孩子，則生成0，否則生成1 cd-start=(Tp.lchild=c)?'0':'1' c=p; /使得可以進(jìn)行循環(huán) strcpy(Hi.bits,&cdstart); Hi.len=num-

32、start; void coding(HuffmanCode HC,char *str) /對str所代表的字符串進(jìn)行編碼并寫入文件 int i,j; FILE*fp; /定義文件的指針 fp=fopen("codefile.txt","w"); /打開文件的函數(shù) while (*str) for(i=1;i<=num;i+) if(HCi.ch=*str) for(j=0;j<=HCi.len;j+) fputc(HCi.bitsj,fp); break; str+; fclose(fp); /關(guān)閉文件/*電文譯碼*char *decode

33、(HuffmanCode HC) /讀出編碼文件的譯碼/代碼文件codefile.txt的譯碼 FILE*fp; /定義文件指針 char str254; /假設(shè)原文本文件不超過254個字符 char *p; /定義字符串的指針 static char cdn+1; int i,j,k=0,cjs; fp=fopen("codefile.txt","r"); / 打開文件 while(!feof(fp) /feof（fp）判斷文件是否真正結(jié)束，feof（fp）=1時文件結(jié)束 cjs=0;/作為返回值 for(i=0;i<=num&&

34、cjs=0 && !feof(fp);i+) cdi=' 'cdi+1='n' cdi=fgetc(fp); /數(shù)組接收從fp指針?biāo)赶蛭募凶x入的一個字符 for(j=1;j<=num;j+) if(strcmp(HCj.bits,cd)=0) /haffman編碼和密碼譯碼相比較 strk=HCj.ch; k+; cjs=1;break; strk='0' /令最后的字符串的字符為0 p=str; /將str的頭指針賦給了p return p; /*輸出HuffmanTree存儲結(jié)構(gòu)*void print1(Huffma

35、nTree HT) int x; for(x=1;x<=2*num-1;x+) HTx.parent=0; HTx.lchild=0; HTx.rchild=0; printf("%11d %dt%dn",HTx.weight,HTx.parent,HTx.lchild,HTx.rchild); printf("-n");void print2(HuffmanTree HT) int k; for(k=1;k<=2*num-1;k+) printf("%dt%dt%dn",HTk.weight,HTk.parent,HTk.lchild,HTk.r