數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告哈夫曼編碼譯碼器系統(tǒng)

1、 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)報(bào)告課 題: 專業(yè)班級： 信 息 061班 學(xué) 號： 200616020208 姓 名： 指導(dǎo)教師: 評閱意見：評定成績： 指導(dǎo)老師簽名： 年 月 日目 錄目 錄 目錄11 課程設(shè)計(jì)的目的和意義22 需求分析33 系統(tǒng)（項(xiàng)目）設(shè)計(jì)5 設(shè)計(jì)思路及方案5 模塊的設(shè)計(jì)及介紹5 主要模塊程序流程圖84 系統(tǒng)實(shí)現(xiàn)11 主調(diào)函數(shù).12 建立huffmantree12 生成huffman編碼并寫入文件.15 電文譯碼.165 系統(tǒng)調(diào)試17參考文獻(xiàn)20附錄 源程序211課程設(shè)計(jì)的目的和意義在當(dāng)今信息爆炸時(shí)代，如何采用有效的數(shù)據(jù)壓縮技術(shù)來節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間已越來越引

2、起人們的重視。哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。樹中從根到每個(gè)葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個(gè)對應(yīng)的字符的編碼，這就是哈夫曼編碼。通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報(bào)通信是傳遞文字的二進(jìn)制碼形式的字符串。但在信息傳遞時(shí)，總希望總長度盡可能最短，即采用最短碼。作為信息管理專實(shí)踐的機(jī)會(huì)！課程設(shè)計(jì)就是為解決這個(gè)問題提供了一個(gè)平臺。在課程設(shè)計(jì)過程中，我們每個(gè)人選擇一個(gè)課題，

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

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

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

6、de()對編碼進(jìn)行譯碼，再輸出至界面。至此，整個(gè)工作就完成了。測試數(shù)據(jù)：例如從文本中讀到文章為：iamastudent。則效果如下：iamastudent-huffmantree的初態(tài): 2 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 2 0 0 0 1 0 0 0 - 0 0 0 - 0 0 0 - 0 0 0 - 0 0 0 - 0 0 0 - 0 0 0 - 0 0 0 - 0 0 0-字符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-huf

7、fmantree的終態(tài): 2 13 0 0 1 10 0 0 1 10 0 0 1 11 0 0 1 11 0 0 1 12 0 0 1 12 0 0 2 14 0 0 1 13 0 0 2 14 2 3 2 15 4 5 2 15 6 7 3 16 9 1 4 16 8 10 4 17 11 12 7 17 13 14 11 0 15 16-譯碼后的字符串: iamastudent*press any key to continue3 系統(tǒng)（項(xiàng)目）設(shè)計(jì)(1)設(shè)計(jì)思路及方案本課題是用最優(yōu)二叉樹即哈夫曼樹來實(shí)現(xiàn)哈夫曼編碼譯碼器的功能。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為wi，編碼長度為li，電文中有

8、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)恰好為二叉樹上帶權(quán)路徑長度。因此，設(shè)計(jì)電文總長最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵哈夫曼樹，此構(gòu)造過程稱為哈夫曼編碼。該系統(tǒng)將實(shí)現(xiàn)以下幾大功能：從硬盤讀取字符串，建立哈夫曼樹，輸出哈夫曼樹的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)，輸出各種字符出現(xiàn)的次數(shù)以及哈夫曼編碼的譯碼等。 (2)模塊的設(shè)計(jì)及介紹從硬盤讀取字符串fileopen(參數(shù)) 實(shí)現(xiàn)命令； 打印輸出；建立huffmantree通過三個(gè)

9、函數(shù)來實(shí)現(xiàn)：void select(參數(shù)) 初始化； for 接受命令； 處理命令；說明：在ht1.k中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法int jsq(參數(shù)) 初始化； for 接受命令； 處理命令； 說明：統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字符的種類void chuffmantree() 初始化； for 接受命令； 處理命令； 輸出字符統(tǒng)計(jì)情況；說明：構(gòu)造哈夫曼樹輸出哈夫曼樹的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)分別調(diào)用print1()和print2()來實(shí)現(xiàn)void print1(參數(shù)) 初始化； 輸出初態(tài)；說明：輸出哈夫曼樹的初態(tài)void print2(參數(shù)) for 輸出終態(tài)；說明：輸出

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

11、開始結(jié)束第i個(gè)結(jié)點(diǎn)權(quán)值i=num?創(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.lchlid=c?i=num?cd-start=0,start=numcd-start=0cd-start=1否否是是 圖3.3流程圖解釋：該流程圖表四哈夫曼編碼情況。首先初始化，cd-start=0,start=num。然后進(jìn)行編碼，使用了一個(gè)三目運(yùn)算符。cd-

12、start=(tp.lchild=c) ? 0 : 1，即當(dāng)cd-start=tp.lchild= =c時(shí)，cd-start=0；當(dāng)cd-start=tp.lchild！= =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=jsq(string,cnt,str); /統(tǒng)計(jì)字符種類及各類字符出現(xiàn)的頻率dhuffmantree(ht,cnt,str); printf(huffmantree的初態(tài):n);print1(ht)

13、; /輸出哈夫曼樹的初態(tài)chuffmantree(ht,hc,cnt,str);/建立哈夫曼樹 huffmanencoding(ht,hc); /生成哈夫曼編碼printf(huffmantree的終態(tài):n);print2(ht); /輸出哈夫曼樹的終態(tài)s=decode(hc); /讀編碼文件譯碼printf(譯碼后的字符串:n);printf(%sn,s); /輸出譯碼后的字符串 建立huffmantree 代碼解釋：該函數(shù)為在ht1.k中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法，其序號為s1和s2。void select(huffmantree t,int k,int &s1,in

14、t &s2) int i,j;int min1=101; for(i=1;i=k;i+)if(ti.weightmin1 &ti.parent=0) j=i;min1=ti.weight;s1=j;min1=32767;for (i=1;i=k;i+)if(ti.weightmin1 & ti.parent=0 & i!=s1)j=i;min1=ti.weight;s2=j;代碼解釋：下面函數(shù)用來統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字符的種類。當(dāng)字符在a和z之間時(shí)即被計(jì)數(shù)，并用strj保存字母到數(shù)組中，用cntj統(tǒng)計(jì)每種字符個(gè)數(shù)。j返回總共讀取的字符數(shù)目。int jsq(char *s,int cn

15、t,char str) int i,j,k; char *p;int temp27; for(i=1;i=a&*p=z)k=*p-64;tempk+; /統(tǒng)計(jì)各種字符的個(gè)數(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是輸入字母總數(shù)代碼解釋：下面函數(shù)用來構(gòu)造哈夫曼樹ht。首先初始化哈夫曼樹，然后輸入前面統(tǒng)計(jì)的各結(jié)點(diǎn)的權(quán)值，用for循環(huán)來構(gòu)造哈夫曼樹。void chuffmantree(huffmantree ht,huffmancode hc,int c

16、nt,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.parent=0;hti.weight=0;for(i=1;i=num;i+) /輸入num個(gè)葉結(jié)點(diǎn)的權(quán)值hti.weight=cnti;for(i=num+1;i=2*num-1;i+)select(ht,i-1,s1,s2);hts1.parent=i;hts2.parent=i;hti.lchild=s1; hti.rchild=s2;hti.weight=hts1.weight+hts

17、2.weight;/在ht1.k中選擇parent為0且權(quán)值最小/的兩個(gè)根結(jié)點(diǎn),其序號為s1和s2,i為雙親for(i=0;i=num;i+) /輸入字符集的中字符hci.ch=stri; /字符的種類i=1;while(i=num)printf(字符%c次數(shù):%dn,hci.ch,cnti+); /輸出統(tǒng)計(jì)的情況 生成huffman編碼并寫入文件 代碼解釋：根據(jù)哈夫曼樹t求哈夫曼編碼h。 void huffmanencoding(huffmantree t,huffmancode h)int c,p,i; /c和p分別指示t中孩子和雙親char cdn; /臨時(shí)存放編碼串int start;

18、 /指示碼在cd中的起始位置cdnum=0; /最后一位（第num個(gè)）放上串結(jié)束符for(i=1;i0) /直至上溯到tc是樹根為止cd-start=(tp.lchild=c) ? 0 : 1;c=p; /若tc是tp的左孩子/則生成0;否則生成底碼strcpy(hi.bits,&cdstart);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)

19、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); 電文譯碼代碼解釋：代碼文件codefile.txt的譯碼，將翻譯的二進(jìn)制碼譯成原來的字符。char*decode(huffmancode hc)file *fp;char str254; /假設(shè)遠(yuǎn)文本文件不超過254個(gè)字符char *p;static char cdn+1;int i,j,k=0,cjs;fp=fopen(codefile.txt,r);/一只讀的方式打開文本文檔/codefile.tx

20、twhile(!feof(fp) /feof(fp)判斷文件是否真正結(jié)束， /feof(fp)=1時(shí)文件結(jié)束cjs=0;for(i=0;inum & cjs=0 & !feof(fp);i+)cdi= ;cdi+1=0;cdi=fgetc(fp); /數(shù)組接受從fp指針?biāo)赶蛭募凶x /入的一個(gè)字符 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盤中建立一個(gè)名為file1.txt的文

21、本文檔，其中有大寫字母iamastudent，期望程序能將其讀出至界面并實(shí)現(xiàn)其他相關(guān)的功能。運(yùn)行程序后，我們可以見到一下的運(yùn)行界面。 從硬盤中讀出已有的文本文件(見圖5.1)： 圖5.1 輸出哈夫曼樹存儲(chǔ)結(jié)構(gòu)的初態(tài)(見圖5.2)： 圖5.2 輸出所讀字符的種類和每種字符的個(gè)數(shù)(見圖5.3)： 圖5.3 輸出哈夫曼樹存儲(chǔ)結(jié)構(gòu)的終態(tài)(見圖5.4)： 圖5.4 輸出譯碼后的字符(見圖5.5) 圖5.5由此可見，此次測試很成功。我們能夠?qū)⑽谋疚臋nfile1.txt中的文段讀出，并將其統(tǒng)計(jì)并輸出字符種類和每種字符出現(xiàn)的頻率。同時(shí)輸出哈夫曼樹存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)。然后輸出譯碼后的字符。小 結(jié)通過兩周的課程

22、設(shè)計(jì)使我對哈夫曼樹以及哈夫曼編碼有了更深的認(rèn)識和理解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。首先我談?wù)勎以谠O(shè)計(jì)期間我遇到的難點(diǎn)。開始的時(shí)候，代碼中有許多的錯(cuò)誤，特別是有一個(gè)“無法找到文件”的錯(cuò)誤讓我束手無策，最后還是屏蔽了定義的四個(gè)頭文件然后慢慢地改正錯(cuò)誤才讓我又看到了希望。然后在實(shí)現(xiàn)文章的讀入時(shí)，由于對文件不是太熟悉，只好翻開c語言書本仿照其模式編寫，但后來進(jìn)入了死循環(huán)，最后的解決方式是把main函數(shù)里的一個(gè)dowhile循環(huán)去掉。在程序中，我還另外加了一個(gè)功能-輸出哈夫曼樹的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)。這使得我更加的明白了哈夫曼到底是怎么存儲(chǔ)信息的。許多的錯(cuò)誤讓我明白了一個(gè)道理

23、-細(xì)心是非常重要的。同時(shí)，對于編程者而言，思路清晰是相當(dāng)重要的。在適當(dāng)?shù)臅r(shí)候和同學(xué)一起交流探討是一個(gè)十分好的學(xué)習(xí)機(jī)會(huì)。請教老師也很重要，因?yàn)楫吘刮覀兪切率?，對于某些問題很難弄清楚。而且，某些錯(cuò)誤對于我們來說有時(shí)候想半天都弄不來，但老師幾下下就搞好了，這樣就更加有效地節(jié)約了時(shí)間。這次課程設(shè)計(jì)不但讓我學(xué)得了一些編程知識，還學(xué)會(huì)了系統(tǒng)的做一份課程設(shè)計(jì)報(bào)告，學(xué)會(huì)了如何截圖，學(xué)會(huì)了如何更好的畫流程圖，明白了做事情只有認(rèn)真，才能真正做得更好！這段時(shí)間里，可謂是酸甜苦辣都嘗過。有時(shí)，為了一個(gè)錯(cuò)誤而焦頭爛額；有時(shí)，編程熬夜到凌晨兩點(diǎn)；有時(shí)，連吃飯都是匆匆了事；但一旦程序運(yùn)行成功，總會(huì)讓我興奮不已。通過這次課程

24、設(shè)計(jì)，我看清楚了自己的編程功底和動(dòng)手能力還不如人意，這主要是平時(shí)實(shí)踐太少的緣故。我想，在未來的暑假中，我會(huì)努力嘗試編寫一些程序。雖然我們信息管理專業(yè)的學(xué)生，但現(xiàn)在編程的能力太差了，畢竟多精通一門技術(shù)總是好事。在這個(gè)程序中，還有許多地方值得完善。比如，讀出文本只能是大寫的文檔，空格和小寫不能識別，更不用說是任意的asc碼字符了。由于時(shí)間問題，暫時(shí)不能實(shí)現(xiàn)了。我想在暑假里好好研究這個(gè)問題。參考文獻(xiàn)1 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)(c語言版).清華大學(xué)出版社，20072 蘇仕華.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).機(jī)械工業(yè)出版社，20073 譚浩強(qiáng).c語言程序設(shè)計(jì)教程.高等教育出版社，2006附錄 源程序#include #in

25、clude #include #include/*類型相關(guān)變量的定義*#define n 100 /葉子結(jié)點(diǎn)數(shù)#define m 2*n-1 /哈夫曼樹中的結(jié)點(diǎn)樹typedef structchar ch;char bits9; /存放編碼位串int len; codenode;typedef codenode huffmancoden+1;typedef struct int weight; /權(quán)值int lchild,rchild,parent; /左右孩子幾雙親指針 htnode;typedef htnode huffmantreem+1; /0號單元不用int num;/*建立huff

26、mantree*void select(huffmantree t,int k,int &s1,int &s2) /在ht1.k中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法/其序號為s1和s2int i,j;int min1=101; for(i=1;i=k;i+)if(ti.weightmin1 &ti.parent=0) j=i;min1=ti.weight;s1=j;min1=32767;for (i=1;i=k;i+)if(ti.weightmin1 & ti.parent=0 & i!=s1)j=i;min1=ti.weight;s2=j;int jsq(char *s,int

27、 cnt,char str) /統(tǒng)計(jì)字符串中各種字母的個(gè)數(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!=0 ) j+;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)造哈夫曼樹htint i,s1,s2;for(i=1;i=2*nu

28、m-1;i+)/初始化ht，2*num-1是指哈夫曼樹所有的結(jié)點(diǎn)數(shù)目hti.lchild=0;hti.rchild=0;hti.parent=0;hti.weight=0;for(i=1;i=num;i+) /輸入num個(gè)葉結(jié)點(diǎn)的權(quán)值hti.weight=cnti;for(i=num+1;i=2*num-1;i+) /在ht1.k中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)/其序號為s1和s2/i為雙親select(ht,i-1,s1,s2);hts1.parent=i;hts2.parent=i;hti.lchild=s1; hti.rchild=s2;hti.weight=hts1.wei

29、ght+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求哈夫曼編碼hint c,p,i; /c和p分別指示t中孩子和雙親char cdn; /臨時(shí)存放編碼串int start; /指示碼在cd中的起始位置cdnum=0; /最后一位（第num個(gè)）放上串結(jié)束符for(i=1;i0

30、) /直至上溯到tc是樹根為止 /若tc是tp的左孩子,則生成0;否則生成底碼cd-start=(tp.lchild=c) ? 0 : 1;c=p;strcpy(hi.bits,&cdstart);hi.len=num-start;void coding(huffmancode hc ,char *str) /對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.bitsj,

31、fp);break;str+;fclose(fp);/*電文譯碼*char*decode(huffmancode hc) /代碼文件codefile.txt的譯碼file *fp;char str254; /假設(shè)遠(yuǎn)文本文件不超過254個(gè)字符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時(shí)文件結(jié)束cjs=0;for(i=0;inum & cjs=0 & !feof(fp);i+)cdi= ;cdi+1=0;cdi=fgetc(fp);/數(shù)組接受從fp指針?biāo)赶蛭募凶x入的一個(gè)字符 for(j=1;j=num;j+)if(strcmp(hcj.bits,cd)=0)/haffman編碼和密碼譯碼相比較strk=hcj.ch;k+;cjs=1;break; strk=0;p=str;return p;/*輸出huffmantree存儲(chǔ)結(jié)構(gòu)*void prin