應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--huffman編／譯碼器

1、<p><b>　　課 程 設(shè) 計(jì)</b></p><p><b>　　課程設(shè)計(jì)任務(wù)書(shū)</b></p><p>　　題 目： Huffman編／譯碼器</p><p><b>　　初始條件：</b></p><p>　　利用Huffman編碼進(jìn)行通信可以大大提高信

2、道利用率．縮短信息傳輸時(shí)間，降低傳輸成本，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編／譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫(xiě)一個(gè)Huffman碼的編／譯碼系統(tǒng)。</p><p>　　要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求、說(shuō)明書(shū)撰寫(xiě)等具體要求）</p><p>　　一個(gè)完

3、整的系統(tǒng)應(yīng)具有以下功能：</p><p>　　（l）I：初始化。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件hfmTree中。</p><p>　?。?）E：編碼。利用已建好的Huffman樹(shù)（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。</p><p>　

4、　（3）D：譯碼。利用已建好的Huffman樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。</p><p>　?。?）P：印代碼文件。將文件CodeFile以緊湊格式顯示在終端上，每行50 個(gè)代碼。</p><p>　?。?）T：印哈夫曼樹(shù)。將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式（樹(shù)或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件TreePrint中。

5、</p><p><b>　　時(shí)間安排：</b></p><p><b>　　需求分析</b></p><p><b>　　程序的任務(wù)：</b></p><p>　　利用Huffman編碼進(jìn)行通信可以大大提高信道利用率．縮短信息傳輸時(shí)間，降低傳輸成本，這要求在發(fā)送端通過(guò)一個(gè)編碼

6、系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編／譯碼系統(tǒng)。此程序就是為這樣的信息收發(fā)站寫(xiě)一個(gè)Huffman碼的編／譯碼系統(tǒng)。</p><p><b>　　程序的輸入和輸出：</b></p><p>　　從終端讀入字符集大小n，以及n個(gè)字符及各個(gè)字符的權(quán)值，建立赫夫曼樹(shù)，并將它存儲(chǔ)到文件hf

7、mTree中；利用已建好的赫夫曼樹(shù)將文件中的字符編碼，如果赫夫曼樹(shù)不在內(nèi)存中，則從文件hfmTree中讀取到內(nèi)存；將譯得的代碼存到文件CodeFile中；利用已建好的赫夫曼樹(shù)對(duì)CodeFile中的代碼進(jìn)行譯碼，將結(jié)果存入文件TextFile中；最后將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式（樹(shù)或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件TreePrint中。</p><p><b>　　程序要

8、達(dá)到的功能：</b></p><p>　　用戶可以利用菜單根據(jù)自己的需要來(lái)選擇要進(jìn)行編碼或是譯碼,并將轉(zhuǎn)換好的字符或編碼以文件的形式存到相應(yīng)的文件里面。</p><p><b>　　測(cè)試數(shù)據(jù)如下表：</b></p><p>　?。╨）利用教材中的數(shù)據(jù)調(diào)試程序。</p><p>　　（2）用下表給出的字符集和頻

9、度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹(shù)，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼："THIS PROGRAM IS MY FAVORITE"。</p><p>　　選擇E，輸入THIS PROGRAM IS MY FAVORITE，屏幕上顯示11010001011000111111000100010100110000100101010110010111011000111111100101000111111100111

10、01011000001001001001101101010</p><p>　　同時(shí)文件codefile里面也出現(xiàn)相應(yīng)的代碼</p><p>　　選擇D，從codefile中調(diào)入代碼，終端顯示THIS PROGRAM IS MY FAVORITE，并且文件textfile中也相應(yīng)的存入了這段話。</p><p>　　選擇P，文件CodeFile以緊湊格式顯示在終端上

11、。</p><p>　　選擇T，將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式（樹(shù)或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件TreePrint中。</p><p>　　選擇其他的字母，將出現(xiàn)出錯(cuò)提示，并重新回到選擇菜單。</p><p><b>　　概要設(shè)計(jì)</b></p><p>　　ADT BinaryTre

12、e{</p><p>　　數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素集合。</p><p><b>　　數(shù)據(jù)關(guān)系R：</b></p><p>　　若D為空，則R為空，稱Huffmantree為空霍夫曼樹(shù)；</p><p>　　若D不為空，則R={H}，H是如下的二元關(guān)系：</p><p>　　1、 H

13、滿足二叉樹(shù)的所有要求；</p><p>　　2、 H中所有數(shù)乘以該數(shù)所在節(jié)點(diǎn)的深度值之后和最小。</p><p><b>　　基本操作P：</b></p><p>　　InputHuffman(Huffman Hfm) </p><p>　　操作結(jié)果：輸入并存儲(chǔ)字符和相應(yīng)權(quán)值。</p><p>　

14、　Select(HuffmanTree HT,int end,int *s1,int *s2)</p><p>　　初始條件：頻率數(shù)組已經(jīng)建立。</p><p>　　操作結(jié)果：選擇HT[1....i-1]中無(wú)雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為s1，s2。</p><p>　　HuffmanCoding(Huffman Hfm)</p><p>

15、;　　初始條件：頻率數(shù)組已經(jīng)建立。</p><p>　　操作結(jié)果：w存放n個(gè)字符的權(quán)值（均>0），構(gòu)造赫夫曼樹(shù)HT，并求出n個(gè)字符的構(gòu)造赫夫曼編碼HC。</p><p>　　InitHuffman(Huffman Hfm)</p><p>　　初始條件：頻率數(shù)組已經(jīng)建立。</p><p>　　操作結(jié)果：要求用戶輸入字符和相應(yīng)權(quán)值，初

16、始化赫夫曼數(shù)</p><p>　　Encoding(Huffman Hfm)</p><p>　　初始條件：霍夫曼樹(shù)HuffmanTree已經(jīng)存在。</p><p>　　操作結(jié)果：利用已建好的Huffman樹(shù)（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。</p><p&

17、gt;　　Decoding(Huffman Hfm)</p><p>　　初始條件：霍夫曼樹(shù)HuffmanTree已經(jīng)存在。</p><p>　　操作結(jié)果：利用已建好的Huffman樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。</p><p>　　Print(Huffman Hfm)</p><p>　　初始條件

18、：霍夫曼樹(shù)HoffmanTree已經(jīng)存在。</p><p>　　操作結(jié)果：將文件CodeFile以緊湊格式顯示在終端上，每行50 個(gè)代碼。</p><p>　　Treeprint(Huffman Hfm)</p><p>　　初始條件：霍夫曼樹(shù)HuffmanTree已經(jīng)存在。</p><p>　　操作結(jié)果：將已在內(nèi)存中的哈夫曼樹(shù)以凹入表的形式

19、顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件TreePrint中。</p><p>　　}ADT HuffmanTree</p><p><b>　　2 主程序流程</b></p><p>　　Void main()</p><p><b>　　{</b></p><p&g

20、t;<b>　　顯示菜單；</b></p><p><b>　　Switch(k)</b></p><p><b>　　{ </b></p><p><b>　　I：初始化</b></p><p><b>　　E：編碼</b><

21、/p><p><b>　　D：譯碼</b></p><p><b>　　P：印代碼文件</b></p><p><b>　　T：印哈夫曼樹(shù)</b></p><p><b>　　Q：退出運(yùn)行</b></p><p><b>　　

22、} </b></p><p><b>　　}</b></p><p><b>　　程序調(diào)用模塊</b></p><p><b>　　詳細(xì)設(shè)計(jì)</b></p><p>　　3.1數(shù)據(jù)類型： </p><p>　　typedef char

23、**HuffmanCode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)霍夫曼表碼表</p><p>　　typedef struct{</p><p>　　unsigned int weight;</p><p>　　unsigned int parent,lchild,rchild;</p><p>　　}HTNode,*HuffmanTree;//動(dòng)態(tài)

24、分配數(shù)組存儲(chǔ)霍夫曼樹(shù)</p><p>　　typedef struct{</p><p>　　HuffmanTree HT;</p><p>　　char *c;</p><p>　　int length;</p><p>　　HuffmanCode HC;</p><

25、p>　　}Huffman;//分配數(shù)組存儲(chǔ)字符串及其對(duì)應(yīng)的霍夫曼樹(shù)</p><p>　　Huffman Hfm;</p><p>　　char k; /*控制循環(huán)的標(biāo)志*/</p><p><b>　　3.2 偽碼算法：</b></p><p><b>　　主程序</b></p>

26、<p><b>　　main()</b></p><p><b>　　{</b></p><p>　　InitHuffman(Huffman Hfm)；</p><p>　　Encoding(Huffman Hfm)；</p><p>　　Decoding(Huffman Hfm)；&l

27、t;/p><p>　　Print(Huffman Hfm)；</p><p>　　Treeprint(Huffman Hfm)；</p><p><b>　　}</b></p><p><b>　　其他模塊：</b></p><p>　　void Select(HuffmanTr

28、ee HT,int end,int *s1,int *s2)//選擇HT[1....i-1]中無(wú)雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為s1，s2</p><p>　　FOR (i=1;i<=end;i++)</p><p><b>　　{</b></p><p>　　IF(HT[i].parent是最小的)</p><p&

29、gt;　　THEN HT[i].parent——>*s1</p><p>　　IF(HT[i].parent是次最小的)</p><p>　　THEN HT[i].parent——>*s2</p><p><b>　　}</b></p><p>　　Huffman HuffmanCoding(Huffma

30、n Hfm) //w存放n個(gè)字符的權(quán)值（均〉0），構(gòu)造赫夫曼樹(shù)HT，并求出n個(gè)字符的構(gòu)造赫夫曼編碼HC</p><p><b>　　{</b></p><p>　　FOR(i=n+1;i<=2*n-1;++i) //選擇HT[1....i-1]中無(wú)雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為s1，s2</p><p><b>　　{<

31、;/b></p><p>　　Select(Hfm.HT,i-1,&s1,&s2);</p><p>　　修改父親位置； </p><p><b>　　修改孩子位置；</b></p><p>　　父親結(jié)點(diǎn)權(quán)值為左右孩子權(quán)值之和；</p><p><b>　　}&

32、lt;/b></p><p>　　//從葉子結(jié)點(diǎn)到根逆向求每個(gè)字符的赫夫曼編碼</p><p>　　FOR(i=1;i<=n;++i)</p><p>　　//逐個(gè)字符求赫夫曼編碼</p><p>　　{ start=n-1;//編碼結(jié)束符位置</p><p>　　for(c=i,f=Hfm.HT[i].p

33、arent;f!=0;c=f,f=Hfm.HT[f].parent)</p><p>　　//從葉子到根逆向求編碼</p><p><b>　　{</b></p><p>　　IF(c==Hfm.HT[f].lchild) cd[--start]='0';</p><p>　　ELSE cd[--sta

34、rt]='1';</p><p><b>　　}</b></p><p>　　再?gòu)腸d復(fù)制編碼到Hfm.HC</p><p><b>　　}</b></p><p>　　RETURN Hfm;</p><p><b>　　}</b><

35、;/p><p>　　Huffman InitHuffman(Huffman Hfm)//初始化赫夫曼數(shù)，要求用戶輸入字符和相應(yīng)權(quán)值</p><p><b>　　{</b></p><p>　　對(duì)文件hfmTree以讀文本的形式打開(kāi)</p><p>　　IF(fp==NULL)</p><p>　　調(diào)用

36、InputHuffman函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入赫夫曼數(shù)中</p><p><b>　　ELSE</b></p><p>　　輸出"The Huffmantree has already existed!\nPlease choose again!\n\n");</p><p>　　讀入hfmTree中文本 &l

37、t;/p><p>　　FOR(i=1;i<=n;i++)</p><p>　　作為獨(dú)立結(jié)點(diǎn)對(duì)結(jié)點(diǎn)的parent，lchild，rchild分別賦值0</p><p>　　FOR(;i<=2*n-1;++i)</p><p>　　作為獨(dú)立結(jié)點(diǎn)對(duì)結(jié)點(diǎn)的weight，parent，lchild，rchild分別賦值0 </p&g

38、t;<p>　　Hfm=HuffmanCoding(Hfm);</p><p>　　RETURN Hfm;</p><p><b>　　}</b></p><p>　　void Encoding(Huffman Hfm)//利用已建好的Huffman樹(shù)（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行

39、編碼，然后將結(jié)果存入文件CodeFile中。</p><p><b>　　{</b></p><p>　　輸出"\n\n*******************Encoding**************************\n\n"</p><p>　　IF((ffp=fopen("ToBeTran"

40、,"rt"))==NULL)</p><p>　　提示輸入"Please input the sentence: "</p><p>　　scanf("%s",ch);</p><p>　　printf("\n");</p><p>　　以寫(xiě)文本的形式打開(kāi)Code

41、File</p><p><b>　　ELSE</b></p><p>　　讀入ToBeTran文件中的字符;</p><p>　　WHILE(ch[j])</p><p>　　FOR(i=1;i<=n;i++)</p><p>　　IF(ch[j]==Hfm.c[i])</p>

42、<p>　　分別在終端和文件CodeFile輸入Hfm.HC[i]</p><p>　　void Decoding(Huffman Hfm)//利用已建好的Huffman樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。</p><p>　　{ 定義char d[500]</p><p>　　輸出"\n\n******

43、************Decoding************************\n\n"</p><p>　　IF((fp=fopen("CodeFile","rt"))==NULL)</p><p>　　輸出Please input the code:;</p><p><b>　　ELSE

44、 </b></p><p>　　將文件Codefile中的內(nèi)容讀到d數(shù)組中</p><p>　　輸出The file is :</p><p>　　以寫(xiě)文本的方式打開(kāi)TextFile</p><p>　　WHILE(d[j])</p><p>　　根到葉子結(jié)點(diǎn)遍歷，并按照l(shuí)child——>0，rch

45、ild——>1來(lái)輸出</p><p>　　入到文件TextFile中</p><p><b>　　關(guān)閉文件</b></p><p><b>　　}</b></p><p>　　void Print(Huffman Hfm)//將文件CodeFile以緊湊格式，示在終端上，每行50 個(gè)代碼。&l

46、t;/p><p><b>　　{</b></p><p>　　FOR(i=1;i<=n;i++)</p><p>　　輸出Hfm.c[i]</p><p>　　輸出Hfm.HT[i].weight</p><p>　　以只讀二進(jìn)制的方式打開(kāi)CodeFile文件</p><p&

47、gt;　　while ( feof(fprint)==0 )</p><p><b>　　逐個(gè)輸出</b></p><p>　　IF (m%50==0)</p><p><b>　　輸出"\n"</b></p><p><b>　　關(guān)閉文件</b></

48、p><p><b>　　}</b></p><p>　　void Treeprint(Huffman Hfm)//將已在內(nèi)存中的哈夫曼樹(shù)以凹入表的形式顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件TreePrint中。</p><p><b>　　{</b></p><p>　　打開(kāi)hfmTree文件

49、</p><p>　　將字符及其對(duì)應(yīng)的代碼賦給變量Hfm.c[i]和Hfm.c[i][j]</p><p>　　輸出Hfm.c[i]，對(duì)Hfm.c[i][j]進(jìn)行判斷，不是\n則輸出*，否則停止輸出</p><p><b>　　}</b></p><p>　　3.3函數(shù)調(diào)用關(guān)系圖</p><p>

50、<b>　　調(diào)試分析</b></p><p>　　4.1 調(diào)試過(guò)程中遇到的問(wèn)題：</p><p>　　第一個(gè)問(wèn)題是一直比較棘手的問(wèn)題就是文件的調(diào)用與寫(xiě)入，因?yàn)槲募矫娴闹R(shí)一直就掌握的不是很好，在寫(xiě)代碼時(shí)產(chǎn)生很大困難，所以在解決這個(gè)問(wèn)題的時(shí)候我把文件部分系統(tǒng)的看了一下，這才從自身角度解決了這個(gè)問(wèn)題。而實(shí)際中遇到的問(wèn)題就是如何判斷已經(jīng)有了hfmtree這個(gè)文件，并且怎么

51、調(diào)用到內(nèi)存中來(lái)。</p><p>　　解決方案：設(shè)置一個(gè)全局結(jié)構(gòu)體變量來(lái)存放已經(jīng)在文件中存放的霍夫曼樹(shù)。</p><p>　　第二個(gè)問(wèn)題是關(guān)于界面的美觀設(shè)計(jì)方面，因?yàn)楹芏啻a在文本中編輯時(shí)是比較整齊美觀的，但是在程序運(yùn)行中卻出現(xiàn)很多問(wèn)題，不對(duì)齊等等。還有就是換行符的使用，一不小心就會(huì)產(chǎn)生偏差。</p><p>　　解決方案：進(jìn)入程序進(jìn)行調(diào)試，檢查每段輸出代碼的顯示。

52、</p><p>　　第三個(gè)問(wèn)題是Huffman樹(shù)的打印，方式為凹入式打印，由于在當(dāng)時(shí)學(xué)習(xí)的時(shí)候這部分內(nèi)容沒(méi)有留意，根本沒(méi)有概念，所以在編寫(xiě)程序過(guò)程中出現(xiàn)了嚴(yán)重的問(wèn)題。導(dǎo)致該項(xiàng)功能無(wú)法完成。</p><p>　　解決方案：尚未完善解決，只是將內(nèi)存中的哈夫曼樹(shù)中各節(jié)點(diǎn)的值及其孩子輸出。</p><p>　　4.2 算法的時(shí)空分析：</p><p&g

53、t;<b>　　算法的時(shí)間復(fù)雜度：</b></p><p>　　Select(HuffmanTree HT,int end,int *s1,int *s2) O(n)</p><p>　　HuffmanCoding(Huffman Hfm) O(n2)</p><p>　　InputHuffman(Huffm

54、an Hfm) O(n)</p><p>　　InitHuffman(Huffman Hfm) O(n)</p><p>　　Encoding(Huffman Hfm) O(n)</p><p>　　Decoding(Huffman Hfm)

55、 O(n)</p><p>　　Print(Huffman Hfm) O(n)</p><p>　　4.3 經(jīng)驗(yàn)與體會(huì)：</p><p>　　整個(gè)程序在編的時(shí)候思路是很明朗的，包括菜單的設(shè)置都是很清晰的，但是如何通過(guò)一個(gè)菜單將所有涉及到的文件與終端聯(lián)系起來(lái)還有打印哈夫曼樹(shù)都是比較困難的問(wèn)題，由于

56、文件這一章節(jié)我們以前學(xué)習(xí)的時(shí)候并沒(méi)有很重視，所以在運(yùn)用的時(shí)候遇到了很大的困難，同時(shí)通過(guò)這次的設(shè)計(jì)我也看到其實(shí)文件這一章是很重要的，我們做了一個(gè)程序，必須要把有些必要的數(shù)據(jù)進(jìn)行保存，如果只是停留在內(nèi)存中那就很難在以后被重復(fù)利用，會(huì)很大程度上提高我們調(diào)試的效率；另外凹入式打印哈夫曼樹(shù)更是讓我頭疼了一整天的問(wèn)題，由于根本不知道其概念是什么，更不用說(shuō)去編寫(xiě)代碼了。同時(shí)我也覺(jué)得有些細(xì)節(jié)問(wèn)題是很重要的，不管是一個(gè)整型變量還是一個(gè)結(jié)構(gòu)體變量，有時(shí)候?qū)?/p>

57、整個(gè)程序起著至關(guān)重要的作用。</p><p><b>　　用戶使用說(shuō)明</b></p><p>　　1．本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：hfmtree.exe。</p><p>　　2. 運(yùn)行程序后出現(xiàn)選擇菜單。</p><p>　　3．根據(jù)提示選擇相應(yīng)的操作，初始化，編碼，譯碼，印代碼文件，印哈夫曼樹(shù)&l

58、t;/p><p>　　退出，每次選擇完，都會(huì)再次彈出選擇菜單供用戶選擇。結(jié)束符為回車鍵。</p><p><b>　　測(cè)試結(jié)果</b></p><p>　　在進(jìn)入系統(tǒng)以后，選擇第一個(gè)初始化，按要求鍵入要求的字符及其頻度</p><p><b>　　截圖如下所示：</b></p><p

59、><b>　　圖1</b></p><p>　　進(jìn)入程序，顯示的菜單界面</p><p><b>　　圖2</b></p><p>　　輸入I，選擇進(jìn)行初始化</p><p><b>　　圖3</b></p><p>　　初始化時(shí)對(duì)字符的個(gè)數(shù)進(jìn)行限

60、制，不得少于2個(gè)。</p><p><b>　　圖4、5</b></p><p>　　在字符個(gè)數(shù)處輸入“27”，之后依次輸入各字符及其權(quán)值。</p><p><b>　　圖6</b></p><p>　　在菜單界面選擇E，出現(xiàn)提示語(yǔ)句，要求輸入句子。</p><p><

61、b>　　圖7</b></p><p>　　輸入“THIS_PROGRAM_IS_MY_FAVORITE”，回車之后，顯示出該句的哈夫曼編碼。</p><p>　　（此處為求簡(jiǎn)捷，將空格用下劃線“_”作為代替）</p><p><b>　　圖8</b></p><p>　　在菜單界面選擇D，則對(duì)文件中已有

62、的哈夫曼編碼進(jìn)行反譯，將譯出的字符顯示出來(lái)。</p><p><b>　　圖9</b></p><p>　　在菜單界面選擇P，將文件中的哈夫曼編碼緊湊輸出，每行50個(gè)。結(jié)果如下圖：</p><p><b>　　圖10、11</b></p><p>　　該程序中，我加入了將初始化的各字符的編碼輸出的語(yǔ)

63、句，可以看到各個(gè)字符的哈弗曼編碼。</p><p><b>　　圖12</b></p><p>　　這3行數(shù)字便是緊湊輸出哈夫曼編碼的結(jié)果。</p><p><b>　　圖13</b></p><p>　　同時(shí)，不同的人使用本程序進(jìn)行不同的哈夫曼編碼時(shí)，由于前一位使用者初始化的數(shù)據(jù)后一位不一定同樣適

64、用，為了避免這種情況，因此當(dāng)已經(jīng)初始化后再進(jìn)行初始化時(shí)會(huì)出現(xiàn)提示是否重新初始化的信息提示，如上圖所示。</p><p><b>　　圖14</b></p><p>　　在菜單界面選擇T，打印處內(nèi)存中的哈夫曼樹(shù)各節(jié)點(diǎn)的值及其雙親節(jié)點(diǎn)和子節(jié)點(diǎn)。</p><p><b>　　圖15</b></p><p>

65、;　　TEXTFILE.TXT文本文件，記錄用戶輸入的需要進(jìn)行編碼的句子。</p><p><b>　　圖16</b></p><p>　　CODEFILE.TXT文本文件，記錄TEXTFILE.TXT文本文件中字符的哈弗曼編碼。</p><p><b>　　圖17</b></p><p>　　HF

66、MTREE.TXT文本文件，記錄輸入的各字符及其權(quán)值</p><p><b>　　附錄</b></p><p><b>　　源程序文件名清單：</b></p><p>　　TEXTFILE.TXT 記錄待編碼的句子</p><p>　　CODEFILE.TXT 記錄哈

67、夫曼編碼</p><p>　　HFMTREE.TXT 記錄字符個(gè)數(shù)、名稱及權(quán)值</p><p><b>　　源代碼：</b></p><p>　　#include <stdio.h></p><p>　　#include <string.h></p><p&g

68、t;　　#include <malloc.h></p><p>　　#include<stdlib.h></p><p>　　#include<ctype.h></p><p>　　#define NULL 0</p><p>　　#define OK 1</p><p>　　#de

69、fine ERROR 0</p><p>　　#define OVERFLOW -2</p><p>　　#define MAX_NUM 32767</p><p>　　#define MAX 60</p><p>　　typedef char **HuffmanCode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼表碼表</p><p&g

70、t;　　typedef struct{</p><p>　　unsigned int weight;</p><p>　　unsigned int parent,lchild,rchild;</p><p>　　}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹(shù)</p><p>　　typedef struct{&

71、lt;/p><p>　　HuffmanTree HT;</p><p>　　char *c;</p><p>　　int length;</p><p>　　HuffmanCode HC;</p><p>　　}Huffman;//全局結(jié)構(gòu)體變量，來(lái)存儲(chǔ)字符與代碼</p><

72、;p>　　void Select(HuffmanTree HT,int end,int *s1,int *s2)//選擇HT[1....i-1]中無(wú)雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為s1，s2</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　int min

73、1=MAX_NUM;</p><p><b>　　int min2;</b></p><p>　　for (i=1;i<=end;i++)//遍歷查找權(quán)值最小的結(jié)點(diǎn)S1</p><p><b>　　{</b></p><p>　　if (HT[i].parent==0&&HT[

74、i].weight<min1)</p><p><b>　　{</b></p><p><b>　　*s1=i;</b></p><p>　　min1=HT[i].weight;</p><p><b>　　}</b></p><p><b&

75、gt;　　}</b></p><p>　　min2=MAX_NUM;</p><p>　　for(i=1;i<=end;i++)//遍歷查找除S1外權(quán)值最小的結(jié)點(diǎn)S2</p><p><b>　　{</b></p><p>　　if(HT[i].parent==0&&(*s1!=i)&a

76、mp;&min2>HT[i].weight)</p><p><b>　　{</b></p><p><b>　　*s2=i;</b></p><p>　　min2=HT[i].weight;</p><p><b>　　}</b></p><

77、p><b>　　}</b></p><p><b>　　}</b></p><p>　　Huffman HuffmanCoding(Huffman Hfm) //存放n個(gè)字符的權(quán)值（均〉0），構(gòu)造哈夫曼樹(shù)HT，并求出n個(gè)字符的構(gòu)造哈夫曼編碼HC</p><p><b>　　{</b></p

78、><p>　　int i,n,m,s1,s2,start;</p><p><b>　　int c,f;</b></p><p><b>　　char *cd;</b></p><p>　　n=Hfm.length;</p><p>　　if(n<=1) return H

79、fm;</p><p><b>　　m=2*n-1;</b></p><p>　　for(i=n+1;i<=m;++i) //選擇HT[1....i-1]中無(wú)雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為s1，s2</p><p><b>　　{</b></p><p>　　Select(Hfm.HT,i

80、-1,&s1,&s2);</p><p>　　Hfm.HT[s1].parent=i;//修改父親位置</p><p>　　Hfm.HT[s2].parent=i;</p><p>　　Hfm.HT[i].lchild=s1;//修改孩子位置</p><p>　　Hfm.HT[i].rchild=s2;</p>

81、<p>　　Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight;//父親結(jié)點(diǎn)權(quán)值為左右孩子權(quán)值之和</p><p><b>　　}</b></p><p>　　//從葉子結(jié)點(diǎn)到根逆向求每個(gè)字符的哈夫曼編碼</p><p>　　Hfm.HC=(HuffmanCode)malloc((

82、n+1)*sizeof(char *));//分配n個(gè)字符編碼的頭指針向量</p><p>　　cd=(char *)malloc(n*sizeof(char));//分配求編碼的工作空間</p><p>　　cd[n-1]='\0';//編碼結(jié)束符</p><p>　　for(i=1;i<=n;++i)//逐個(gè)字符求哈夫曼編碼</p&g

83、t;<p><b>　　{</b></p><p>　　start=n-1;//編碼結(jié)束符位置</p><p>　　for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)//從葉子到根逆向求編碼</p><p><b>　　{</b></p>

84、<p>　　if(c==Hfm.HT[f].lchild) cd[--start]='0';</p><p>　　else cd[--start]='1';</p><p><b>　　}</b></p><p>　　Hfm.HC[i]=(char *)malloc((n-start)*sizeo

85、f(char));</p><p>　　strcpy(Hfm.HC[i],&cd[start]);//從cd復(fù)制編碼到Hfm.HC</p><p><b>　　}</b></p><p>　　free(cd);//釋放工作空間</p><p>　　return Hfm;</p><p>&

86、lt;b>　　}</b></p><p>　　Huffman InputHuffman(Huffman Hfm)//輸入函數(shù)，控制用戶輸入字符和相應(yīng)權(quán)值</p><p><b>　　{</b></p><p><b>　　int i,n;</b></p><p>　　printf(

87、"\n\n********************Initialization*********************\n");</p><p>　　printf("The chars and weights will be saved in the file :\hfmTree\ \n");</p><p>　　printf("Plea

88、se input the number of the chars: ");</p><p>　　scanf("%d",&n);</p><p>　　if(n<=1) </p><p>　　{printf("Only One Char!There Is No Need For Coding!");

89、//若只有一個(gè)數(shù)值則無(wú)需編碼</p><p>　　printf("\n");</p><p>　　printf("Please input the number of the chars: ");</p><p>　　scanf("%d",&n);}</p><p>　　Hf

90、m.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));</p><p>　　Hfm.c=(char *)malloc((n+1)*sizeof(char));</p><p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></p><p>　　

91、printf("Please input the char: ");</p><p>　　scanf("%s",&Hfm.c[i]);</p><p>　　printf("Please input the weight of the char: ");</p><p>　　scanf("%

92、d",&Hfm.HT[i].weight);</p><p>　　Hfm.HT[i].parent=0;</p><p>　　Hfm.HT[i].lchild=0;</p><p>　　Hfm.HT[i].rchild=0;</p><p><b>　　}</b></p><p>

93、;　　for(;i<=2*n-1;++i)</p><p><b>　　{</b></p><p>　　Hfm.HT[i].weight=0;</p><p>　　Hfm.HT[i].parent=0;</p><p>　　Hfm.HT[i].lchild=0;</p><p>　　Hfm.

94、HT[i].rchild=0;</p><p><b>　　}</b></p><p>　　Hfm.length=n;</p><p>　　return Hfm;</p><p><b>　　} </b></p><p>　　Huffman InitHuffman(Huffm

95、an Hfm)//初始化哈夫曼數(shù)，要求用戶輸入字符和相應(yīng)權(quán)值</p><p><b>　　{</b></p><p>　　int n,i,x;</p><p><b>　　FILE *fp;</b></p><p>　　fp=fopen("hfmTree","rt&qu

96、ot;);//對(duì)文件hfmTree以讀文本的形式打開(kāi)</p><p>　　if(fp==NULL)</p><p><b>　　{</b></p><p>　　Hfm=InputHuffman(Hfm);//調(diào)用InputHuffman函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入哈夫曼數(shù)中</p><p>　　fp=fopen(&q

97、uot;hfmTree","wt");</p><p>　　fprintf(fp,"%d\n",Hfm.length);</p><p>　　for(i=1;i<=Hfm.length;i++)</p><p>　　fprintf(fp,"%c %d ",Hfm.c[i],Hfm.HT[i

98、].weight);</p><p>　　rewind(fp);</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　{printf("The Huffmantree has already existed!\nDo You Want

99、To Make A New One?('Y'or'N')\n\n");//詢問(wèn)是否重新初始化</p><p>　　scanf("%s",&x);</p><p>　　if(x=='Y')</p><p>　　{ Hfm=InputHuffman(Hfm);//調(diào)用InputHuff

100、man函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入哈弗曼數(shù)中</p><p>　　fp=fopen("hfmTree","w+");</p><p>　　fprintf(fp,"%d\n",Hfm.length);</p><p>　　for(i=1;i<=Hfm.length;i++)</p>&

101、lt;p>　　fprintf(fp,"%c %d ",Hfm.c[i],Hfm.HT[i].weight);</p><p>　　rewind(fp);</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　{fscan

102、f(fp,"%d\n",&n);</p><p>　　Hfm.c=(char *)malloc((n+1)*sizeof(char));</p><p>　　Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));</p><p>　　for(i=1;i<=n;i++)</p>

103、<p>　　fscanf(fp,"%s %d ",&Hfm.c[i],&Hfm.HT[i].weight);//將已經(jīng)在文件中的字符和其對(duì)應(yīng)的權(quán)重輸入到Hfm.c[i]和&Hfm.HT[i].weight中</p><p>　　for(i=1;i<=n;i++)//對(duì)每個(gè)節(jié)點(diǎn)初始化</p><p><b>　　{

104、 </b></p><p>　　Hfm.HT[i].parent=0;</p><p>　　Hfm.HT[i].lchild=0;</p><p>　　Hfm.HT[i].rchild=0;</p><p><b>　　}</b></p><p>　　for(;i<=2*

105、n-1;++i)</p><p><b>　　{</b></p><p>　　Hfm.HT[i].weight=0;</p><p>　　Hfm.HT[i].parent=0;</p><p>　　Hfm.HT[i].lchild=0;</p><p>　　Hfm.HT[i].rchild=0;&

106、lt;/p><p><b>　　}</b></p><p>　　Hfm.length=n;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　fclose(fp);</p><p>　

107、　Hfm=HuffmanCoding(Hfm);</p><p>　　return Hfm;</p><p><b>　　}</b></p><p>　　void Encoding(Huffman Hfm)//利用已建好的Huffman樹(shù)（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件Co

108、deFile中。</p><p><b>　　{</b></p><p>　　int i=0,j=0,n;</p><p>　　char ch[MAX];</p><p>　　FILE *fp,*fw;</p><p>　　n=Hfm.length;</p><p>　　p

109、rintf("\n\n*******************Encoding**************************\n\n");</p><p>　　if((fw=fopen("ToBeTran","r+"))==NULL)//嘗試打開(kāi)ToBeTran</p><p><b>　　{</b>&l

110、t;/p><p>　　printf("\nPlease input the sentence: ");</p><p>　　scanf("%s",ch);</p><p>　　printf("\n");</p><p>　　fp=fopen("CodeFile",&q

111、uot;wt+");</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　fscanf(fw,"%s",ch);</p><p>

112、　　fclose(fw);</p><p><b>　　}</b></p><p>　　while(ch[j])</p><p><b>　　{</b></p><p>　　for(i=1;i<=n;i++)</p><p>　　if(ch[j]==Hfm.c[i])&

113、lt;/p><p><b>　　{</b></p><p>　　printf("%s",Hfm.HC[i]);</p><p>　　fprintf(fp,"%s",Hfm.HC[i]);</p><p><b>　　break;</b></p>&l

114、t;p><b>　　}</b></p><p><b>　　j++;</b></p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　rewind(fp);</p><p>　

115、　fclose(fp);</p><p><b>　　}</b></p><p>　　void Decoding(Huffman Hfm)//利用已建好的Huffman樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。</p><p><b>　　{</b></p><p>

116、　　HuffmanTree p;</p><p><b>　　int i,n;</b></p><p><b>　　int j=0;</b></p><p>　　char d[500];</p><p><b>　　FILE *fp;</b></p><p&

117、gt;　　n=Hfm.length;</p><p>　　printf("\n\n******************Decoding************************\n\n");</p><p>　　if((fp=fopen("CodeFile","r+"))==NULL)</p><p>

118、;<b>　　{</b></p><p>　　printf("Please input the code:");</p><p>　　scanf("%s",d);</p><p><b>　　}</b></p><p><b>　　else</

119、b></p><p><b>　　{</b></p><p>　　fscanf(fp,"%s",d);//將文件中的字符輸入到數(shù)組d中</p><p>　　fclose(fp);</p><p><b>　　}</b></p><p>　　print

120、f("\nThe file is : ");</p><p>　　fp=fopen("TextFile","wt+");//以寫(xiě)入文件的形式打開(kāi)TextFile</p><p>　　while(d[j])</p><p><b>　　{</b></p><p>

121、　　p=&Hfm.HT[2*n-1];</p><p>　　while(p->lchild||p->rchild)</p><p><b>　　{</b></p><p>　　if(d[j]=='0')</p><p>　　{ i=p->lchild; p=&Hfm.H

122、T[i]; }</p><p><b>　　else</b></p><p>　　{ i=p->rchild; p=&Hfm.HT[i]; }</p><p><b>　　j++;</b></p><p><b>　　}</b></p><p

123、>　　printf("%c",Hfm.c[i]);</p><p>　　fprintf(fp,"%c",Hfm.c[i]);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　fclose(fp);

124、</p><p><b>　　}</b></p><p>　　void Print(Huffman Hfm)//將文件CodeFile以緊湊格式顯示在終端上，每行50 個(gè)代碼。</p><p><b>　　{</b></p><p><b>　　int i,n;</b><

125、/p><p>　　int m=1;//計(jì)數(shù)器</p><p><b>　　char ch;</b></p><p>　　FILE* fprint;</p><p>　　n=Hfm.length;</p><p>　　printf("\n\n******************Output t

126、he code of the chars****************\n\n");</p><p>　　for(i=1;i<=n;i++)//顯示每一個(gè)字符對(duì)應(yīng)的哈夫曼編碼</p><p><b>　　{</b></p><p>　　printf("\n");</p><p>　　

127、printf("Char: %c\t",Hfm.c[i]);</p><p>　　printf("Weight: %d\t",Hfm.HT[i].weight);</p><p>　　printf("Code: ");</p><p>　　puts(Hfm.HC[i]);</p><p&

128、gt;<b>　　}</b></p><p>　　fprint=fopen("CodeFile","rb");</p><p>　　while ( feof(fprint)==0 )</p><p><b>　　{</b></p><p>　　ch=fgetc

129、(fprint);</p><p>　　printf("%c",ch);</p><p><b>　　m++;</b></p><p>　　if (m%50==0)//保證每一行輸出50個(gè)字符</p><p>　　printf("\n");</p><p>

130、<b>　　}</b></p><p>　　printf("\n");</p><p>　　fclose(fprint);</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{ &l

131、t;/b></p><p>　　Huffman Hfm;</p><p>　　char k; /*控制循環(huán)的標(biāo)志*/</p><p><b>　　while(1)</b></p><p>　　{ printf(" --------------------------------------\n"

132、;);</p><p>　　printf(" |Thank You To Use MY Huffman Program |\n");</p><p>　　printf(" | |\n");</p><p>　　printf(" |

133、 I.Initialization |\n");</p><p>　　printf(" | E.Encoding |\n");</p><p>　　printf(" | D.Decoding |\n");</p&

134、gt;<p>　　printf(" | P.Printing |\n");</p><p>　　printf(" | T.TreePrint |\n");</p><p>　　printf(" | Q.Ex

135、it |\n");</p><p>　　printf(" --------------------------------------\n");</p><p>　　printf(" Please Input Your Option\n");</p><p>　　scanf(&q

136、uot;%c",&k);</p><p>　　k=toupper(k);</p><p><b>　　switch(k)</b></p><p>　　{ case 'I': Hfm=InitHuffman(Hfm); getchar();break;</p><p>　　case 

137、9;E': Encoding(Hfm); getchar();break;</p><p>　　case 'D': Decoding(Hfm); getchar();break;</p><p>　　case 'P': Print(Hfm); getchar();break;</p>&l