哈夫曼樹(shù)課程設(shè)計(jì) (2)

1、<p>　　計(jì)算機(jī)學(xué)院信息管理與信息系統(tǒng)專(zhuān)業(yè)</p><p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p>　　題 目： 哈夫曼樹(shù)的應(yīng)用 </p><p>　　班 級(jí)： 信管09101班 </p><p>　　姓 名：

2、 趙林芬 </p><p>　　學(xué) 號(hào)： 200917020114 </p><p>　　同組人姓名： 陳立芳 王紅 </p><p>　　起 迄 日 期： 2011.03.01-03.04 </p><p>　　課

3、程設(shè)計(jì)地點(diǎn): 系辦公樓E3-A513 </p><p>　　指導(dǎo)教師： 孫葉楓 </p><p>　　完成日期：2011年3月4日</p><p><b>　　目錄</b></p><p><b>　　1、設(shè)計(jì)目的3</b><

4、/p><p><b>　　2、需求分析4</b></p><p>　　2.1選題的意義及背景4</p><p>　　2.2 輸入/輸出形式和輸出值的范圍4</p><p><b>　　3、概要設(shè)計(jì)4</b></p><p><b>　　3.1設(shè)計(jì)思想4<

5、/b></p><p>　　3.2函數(shù)間的關(guān)系4</p><p><b>　　4、詳細(xì)設(shè)計(jì)5</b></p><p>　　4.1哈夫曼的主要結(jié)構(gòu)5</p><p>　　4.1.1結(jié)構(gòu)定義5</p><p>　　4.1.2主要函數(shù)聲明及功能描述6</p><p&g

6、t;<b>　　4.2源程序7</b></p><p>　　4.2.1頭文件7</p><p>　　4.2.2源文件8</p><p>　　5、程序測(cè)試結(jié)果及問(wèn)題分析17</p><p><b>　　6、總結(jié)18</b></p><p><b>　　7、參

7、考文獻(xiàn)18</b></p><p><b>　　1.設(shè)計(jì)目的</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)作為一門(mén)學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及對(duì)數(shù)據(jù)的各種操作。因此，主要有三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)；對(duì)數(shù)據(jù)的操作（或算法）。通常，算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)取決于數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是信息的一種組織

8、方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對(duì)應(yīng)，通過(guò)這組算法集合可以對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。</p><p>　　在當(dāng)今信息時(shí)代，信息技術(shù)己成為當(dāng)代知識(shí)經(jīng)濟(jì)的核心技術(shù)。我們時(shí)刻都在和數(shù)據(jù)打交道。比如人們?cè)谕獬龉ぷ鲿r(shí)找最短路徑，在銀行查詢(xún)存款、通過(guò)互聯(lián)網(wǎng)查新聞、以及遠(yuǎn)程教育報(bào)名等，所有這些都在與數(shù)據(jù)發(fā)生關(guān)系。實(shí)際上，現(xiàn)實(shí)世界中的實(shí)體經(jīng)過(guò)抽象以后，就可以成為計(jì)算機(jī)上所處理的數(shù)據(jù)。</p&

9、gt;<p>　　數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中所出現(xiàn)的計(jì)算機(jī)操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件之間的一門(mén)計(jì)算機(jī)專(zhuān)業(yè)的核心課程，它是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫(kù)、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。</p><p>　　學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問(wèn)題中所涉及的對(duì)象在計(jì)算機(jī)中表示出來(lái)并對(duì)它們進(jìn)行處理

10、。通過(guò)課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專(zhuān)業(yè)素質(zhì)的提高。通過(guò)此次課程設(shè)計(jì)主要達(dá)到以下目的：</p><p>　　了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；</p><p>　　初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；</p><p>　　提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題

11、的能力；</p><p>　　訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。</p><p><b>　　2．需求分析</b></p><p>　　2.1選題的意義及背景</p><p>　　鍛煉我們的編碼能力，真正理解數(shù)據(jù)結(jié)構(gòu)的編碼思想,并且鍛煉我們的動(dòng)手能力和成員間的配

12、合，提高程序編寫(xiě)能力。</p><p>　　在信息傳遞時(shí)，希望長(zhǎng)度能盡可能短，即采用最短碼。赫夫曼編碼的應(yīng)用，就是采用這種有效的數(shù)據(jù)壓縮技術(shù)可以節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間。</p><p>　　2.2 輸入/輸出形式和輸出值的范圍</p><p>　　輸入信息以加載存檔的reading.txt文件為方式，加載不成功，提示出錯(cuò)信息，加載成功后，系統(tǒng)對(duì)

13、其編碼，并按照選擇對(duì)各種相關(guān)信息存檔</p><p><b>　　3．概要設(shè)計(jì)</b></p><p><b>　　3.1設(shè)計(jì)思想</b></p><p>　　哈夫曼樹(shù)用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)，借助靜態(tài)鏈表來(lái)實(shí)現(xiàn)遍歷。 </p><p>　　利用多重結(jié)構(gòu)體的形式設(shè)計(jì)出所需的變量類(lèi)型，還有基本的文件讀寫(xiě)

14、知識(shí)，同時(shí)借助九大子函數(shù)結(jié)合一個(gè)主函數(shù)設(shè)計(jì)了此課程內(nèi)容，第一部分為信息的讀寫(xiě)及統(tǒng)計(jì)；第二部分為哈夫曼樹(shù)及其編碼的建立，再將編碼信息寫(xiě)進(jìn)文件；第三部分為給信息加密在寫(xiě)進(jìn)文件，再在對(duì)其翻譯。最后的主函數(shù)是整個(gè)程序的組織者，利用switch選擇循環(huán)將九大子函數(shù)聯(lián)系起來(lái)，畫(huà)龍點(diǎn)睛。這樣整個(gè)程序的基本流出就出來(lái)了，再根據(jù)此流出設(shè)計(jì)出源程序。 </p><p><b>　　3.2函數(shù)間的關(guān)系</b>&l

15、t;/p><p>　　哈夫曼系統(tǒng)，函數(shù)間的關(guān)系如圖所示：</p><p><b>　　界面運(yùn)行圖如下：</b></p><p><b>　　4、詳細(xì)設(shè)計(jì)</b></p><p>　　4.1哈夫曼的主要結(jié)構(gòu) </p><p>　　4.1.1結(jié)構(gòu)定義：</p><

16、;p>　　#define MAXVALUE 1000//定義最大權(quán)值</p><p>　　#define MAXBIT 100//定義哈夫曼樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)</p><p>　　typedef struct</p><p><b>　　{ </b></p><p>　　char data;//字符值<

17、/p><p>　　int num;//某個(gè)值的字符出現(xiàn)的次數(shù)</p><p>　　}TotalNode; //統(tǒng)計(jì)結(jié)點(diǎn)，包括字符種類(lèi)和出現(xiàn)次數(shù)</p><p>　　typedef struct</p><p><b>　　{ </b></p><p>　　TotalNode tot[300];/

18、/統(tǒng)計(jì)結(jié)點(diǎn)數(shù)組</p><p>　　int num;//統(tǒng)計(jì)數(shù)組中含有的字符個(gè)數(shù)</p><p>　　}Total; //統(tǒng)計(jì)結(jié)構(gòu)體，包括統(tǒng)計(jì)數(shù)組和字符種類(lèi)數(shù)</p><p>　　typedef struct</p><p><b>　　{ </b></p><p>　　char mes[

19、300];//字符數(shù)組</p><p>　　int num;//總字符數(shù)</p><p>　　}Message; //信息結(jié)構(gòu)體，包括字符數(shù)組和總字符數(shù)</p><p>　　typedef struct{</p><p>　　int locked[500];//密碼數(shù)組</p><p>　　int num;//密碼總數(shù)

20、</p><p>　　}Locking; //哈夫曼編碼后的密文信息</p><p>　　typedef struct</p><p><b>　　{ </b></p><p>　　char data;//字符</p><p>　　int weight;//權(quán)值</p>&l

21、t;p>　　int parent;//雙親結(jié)點(diǎn)在數(shù)組HuffNode[]中的序號(hào)</p><p>　　int lchild;//左孩子結(jié)點(diǎn)在數(shù)組HuffNode[]中的序號(hào)</p><p>　　int rchild;//右孩子結(jié)點(diǎn)在數(shù)組HuffNode[]中的序號(hào)</p><p>　　}HNodetype; //哈夫曼樹(shù)結(jié)點(diǎn)類(lèi)型，包括左右孩子，權(quán)值和信息<

22、;/p><p>　　typedef struct</p><p><b>　　{ </b></p><p>　　int bit[MAXBIT];</p><p>　　int start;</p><p>　　}HCodetype; //哈夫曼編碼結(jié)構(gòu)體，包括編碼數(shù)組和起始位</p>&l

23、t;p>　　4.1.2主要函數(shù)聲明及功能描述如下：</p><p>　　void reading_file(Message *message);</p><p><b>　　從文件中讀取信息</b></p><p>　　void writing_file(Message *message);</p><p><

24、;b>　　將信息寫(xiě)進(jìn)文件</b></p><p>　　void total_message(Message *message,Total *total);</p><p>　　統(tǒng)計(jì)信息中各字符的出現(xiàn)次數(shù)</p><p>　　void HaffmanTree(Total *total,HNodetype HuffNode[]);</p>

25、<p><b>　　構(gòu)建哈夫曼樹(shù)</b></p><p>　　void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);</p><p><b>　　建立哈夫曼編碼</b></p><p>　　void writing_HC

26、ode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);</p><p><b>　　將編碼規(guī)則寫(xiě)進(jìn)文件</b></p><p>　　void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Lock

27、ing *locking);</p><p><b>　　給文件信息加密編碼</b></p><p>　　void writing_lock(Locking *locking);</p><p>　　將已編碼信息寫(xiě)進(jìn)文件</p><p>　　void writing_translate(Locking *locking,

28、HCodetype HuffCode[],HNodetype HuffNode[],Total *total);</p><p>　　將已編碼信息翻譯過(guò)來(lái)并寫(xiě)進(jìn)文件</p><p><b>　　4.2源程序 </b></p><p>　　4.2.1頭文件head.h</p><p>　　#define MAXVALUE

29、1000//定義最大權(quán)值</p><p>　　#define MAXBIT 100//定義哈夫曼樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)</p><p>　　typedef struct</p><p><b>　　{ </b></p><p>　　char data;//字符值</p><p>　　int nu

30、m;//某個(gè)值的字符出現(xiàn)的次數(shù)</p><p>　　}TotalNode; //統(tǒng)計(jì)結(jié)點(diǎn)，包括字符種類(lèi)和出現(xiàn)次數(shù)</p><p>　　typedef struct</p><p><b>　　{ </b></p><p>　　TotalNode tot[300];//統(tǒng)計(jì)結(jié)點(diǎn)數(shù)組</p><p&

31、gt;　　int num;//統(tǒng)計(jì)數(shù)組中含有的字符個(gè)數(shù)</p><p>　　}Total; //統(tǒng)計(jì)結(jié)構(gòu)體，包括統(tǒng)計(jì)數(shù)組和字符種類(lèi)數(shù)</p><p>　　typedef struct</p><p><b>　　{ </b></p><p>　　char mes[300];//字符數(shù)組</p>&l

32、t;p>　　int num;//總字符數(shù)</p><p>　　}Message; //信息結(jié)構(gòu)體，包括字符數(shù)組和總字符數(shù)</p><p>　　typedef struct{</p><p>　　int locked[500];//密碼數(shù)組</p><p>　　int num;//密碼總數(shù)</p><p>　　}L

33、ocking; //哈夫曼編碼后的密文信息</p><p>　　typedef struct</p><p><b>　　{ </b></p><p>　　char data;//字符</p><p>　　int weight;//權(quán)值</p><p>　　int parent;//雙親結(jié)

34、點(diǎn)在數(shù)組HuffNode[]中的序號(hào)</p><p>　　int lchild;//左孩子結(jié)點(diǎn)在數(shù)組HuffNode[]中的序號(hào)</p><p>　　int rchild;//右孩子結(jié)點(diǎn)在數(shù)組HuffNode[]中的序號(hào)</p><p>　　}HNodetype; //哈夫曼樹(shù)結(jié)點(diǎn)類(lèi)型，包括左右孩子，權(quán)值和信息</p><p>　　typed

35、ef struct</p><p><b>　　{ </b></p><p>　　int bit[MAXBIT];</p><p>　　int start;</p><p>　　}HCodetype; //哈夫曼編碼結(jié)構(gòu)體，包括編碼數(shù)組和起始位</p><p>　　void reading_fil

36、e(Message *message);//從文件中讀取信息</p><p>　　void writing_file(Message *message);//將信息寫(xiě)進(jìn)文件</p><p>　　void total_message(Message *message,Total *total);//統(tǒng)計(jì)信息中各字符的次數(shù)</p><p>　　void HaffmanT

37、ree(Total *total,HNodetype HuffNode[]);//構(gòu)建哈夫曼樹(shù)</p><p>　　void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//建立哈夫曼編碼</p><p>　　void writing_HCode(HNodetype HuffNode[],HCode

38、type HuffCode[],Total *total);//將編碼規(guī)則寫(xiě)進(jìn)文件</p><p>　　void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking);//給文件信息加密編碼</p><p>　　void writing_lock(Lock

39、ing *locking);//將已編碼信息寫(xiě)進(jìn)文件</p><p>　　void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total);//將已編碼信息翻譯過(guò)來(lái)并寫(xiě)進(jìn)文件</p><p>　　4.2.2源文件source.cpp</p><p

40、>　　#include<iostream></p><p>　　#include<fstream></p><p>　　#include"head.h"</p><p>　　using namespace std;</p><p>　　int main()</p><p&g

41、t;<b>　　{</b></p><p>　　int i,j,choice,mark=0;//mark標(biāo)記文件信息是否讀入到內(nèi)存中</p><p>　　HNodetype HuffNode[500];//保存哈夫曼樹(shù)中各結(jié)點(diǎn)信息</p><p>　　HCodetype HuffCode[300];</p><p>　　

42、Locking *locking;</p><p>　　Total *total;</p><p>　　Message *message;</p><p>　　locking=new Locking;</p><p>　　locking->num=0;</p><p>　　total=new Total;<

43、/p><p>　　total->num=0;</p><p>　　message=new Message;</p><p>　　message->num=0; //初始化變量</p><p><b>　　while(1)</b></p><p><b>　　{</b>

44、</p><p>　　cout<<"********************************************************************************";</p><p>　　cout<<"*1:從文件讀取信息 2:顯示編碼規(guī)則 3:將原文件信息寫(xiě)進(jìn)文件

45、 *";</p><p>　　cout<<"*4:將編碼規(guī)則寫(xiě)進(jìn)文件 5:將編碼后的信息寫(xiě)進(jìn)文件 6:將譯碼后的信息寫(xiě)進(jìn)文件 7:退出 *";</p><p>　　cout<<"***********************************************************************

46、*********";</p><p>　　cout<<endl;</p><p>　　cout<<"請(qǐng)輸入操作代碼：";</p><p>　　cin>>choice;</p><p>　　switch(choice)</p><p><b>

47、　　{</b></p><p><b>　　case 1:</b></p><p>　　reading_file(message);//從文件中讀取信息</p><p><b>　　mark=1;</b></p><p><b>　　break;</b></p

48、><p>　　case 2://顯示編碼規(guī)則</p><p>　　if(mark==0)cout<<"請(qǐng)先從文件中讀取信息!"<<endl;</p><p><b>　　else</b></p><p><b>　　{</b></p><p

49、>　　total_message(message,total); HaffmanTree(total,HuffNode); HaffmanCode(HuffNode,HuffCode,total); </p><p>　　for(i=0;i<total->num;i++)//顯示編碼規(guī)則</p&

50、gt;<p><b>　　{ </b></p><p>　　cout<<total->tot[i].data<<" ";</p><p>　　for(j=HuffCode[i].start+1;j<total->num;j++)</p><p>　　co

51、ut<<HuffCode[i].bit[j];</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　break; </p><p>　　case 3

52、://將原文件信息寫(xiě)進(jìn)文件</p><p>　　if(mark==0)cout<<"請(qǐng)先從文件中讀取信息!"<<endl;</p><p><b>　　else</b></p><p>　　writing_file(message);//將信息寫(xiě)進(jìn)文件</p><p><

53、b>　　break;</b></p><p>　　case 4://將編碼規(guī)則寫(xiě)進(jìn)文件</p><p>　　if(mark==0)cout<<"請(qǐng)先從文件中讀取信息!"<<endl;</p><p><b>　　else</b></p><p><b&g

54、t;　　{</b></p><p>　　total_message(message,total); </p><p>　　HaffmanTree(total,HuffNode); </p><p>　　HaffmanCode(HuffNode,HuffCode,total); writing_HCode(HuffNode,HuffCode,to

55、tal); </p><p><b>　　}</b></p><p><b>　　break;</b></p><p>　　case 5://將編碼后的信息寫(xiě)進(jìn)文件</p><p>　　if(mark==0)cout<<"請(qǐng)先從文件中讀取信息!"<<end

56、l;</p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　total_message(message,total); </p><p>　　HaffmanTree(total,HuffNode); </p><p>　　H

57、affmanCode(HuffNode,HuffCode,total); </p><p>　　lock(message,HuffNode,HuffCode,total,locking); </p><p>　　writing_lock(locking);</p><p><b>　　}</b></p><p><

58、b>　　break;</b></p><p>　　case 6://將譯碼后的信息寫(xiě)進(jìn)文件</p><p>　　if(mark==0)cout<<"請(qǐng)先從文件中讀取信息!"<<endl;</p><p><b>　　else</b></p><p><b

59、>　　{</b></p><p>　　total_message(message,total); </p><p>　　HaffmanTree(total,HuffNode); </p><p>　　HaffmanCode(HuffNode,HuffCode,total); writing_transl

60、ate(locking,HuffCode,HuffNode,total);</p><p><b>　　}</b></p><p><b>　　break;</b></p><p><b>　　case 7:</b></p><p><b>　　exit(1);<

61、;/b></p><p><b>　　default:</b></p><p>　　cout<<"輸入錯(cuò)誤，請(qǐng)重新選擇"<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p&

62、gt;<p>　　for(i=0;i<locking->num;i++)</p><p>　　if(locking->locked[i]==-1)cout<<" ";</p><p><b>　　else</b></p><p>　　cout<<locking->

63、locked[i]; </p><p>　　cout<<endl;</p><p>　　for(i=0;i<total->num;i++)</p><p>　　cout<<total->tot[i].data<<" "<<total->tot[i].num<<en

64、dl;</p><p>　　for(i=0;i<2*(total->num)-1;i++)</p><p>　　cout<<HuffNode[i].parent<<" ";</p><p>　　cout<<endl; </p><p><b>　　ret

65、urn 0;</b></p><p><b>　　}</b></p><p>　　void reading_file(Message *message)</p><p><b>　　{ </b></p><p><b>　　int i=0;</b></p>

66、;<p><b>　　char ch;</b></p><p>　　ifstream infile("c:\\reading.txt",ios::in|ios::out);</p><p>　　if(!infile)//打開(kāi)失敗則結(jié)束</p><p><b>　　{</b></p&g

67、t;<p>　　cout<<"打開(kāi)c:\\reading.txt文件失敗"<<endl;</p><p><b>　　exit(1);</b></p><p><b>　　}</b></p><p><b>　　else</b></p&g

68、t;<p>　　cout<<"讀取文件成功"<<endl;</p><p>　　while(infile.get(ch) && ch!='#')//讀取字符直到遇到#</p><p><b>　　{</b></p><p>　　message->me

69、s[i]=ch; </p><p><b>　　i++;</b></p><p><b>　　}</b></p><p>　　message->num=i;//記錄總字符數(shù)</p><p>　　infile.close();//關(guān)閉文件</p><p>　　}//從

70、文件中讀取信息</p><p>　　void writing_file(Message *message)//將信息寫(xiě)進(jìn)文件</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　ofstream outfile("c:\\writi

71、ng.txt",ios::in|ios::out);//打開(kāi)文件</p><p>　　if(!outfile)//打開(kāi)失敗則結(jié)束</p><p><b>　　{</b></p><p>　　cout<<"打開(kāi)c:\\writing.txt文件失敗"<<endl;</p><

72、;p><b>　　exit(1);</b></p><p><b>　　}</b></p><p>　　for(i=0;i<message->num;i++)//寫(xiě)文件</p><p>　　outfile.put(message->mes[i]); </p><p>　　co

73、ut<<"信息寫(xiě)進(jìn)文件成功"<<endl;</p><p>　　outfile.close();//關(guān)閉文件</p><p>　　}//將原信息寫(xiě)入文件</p><p>　　void total_message(Message *message,Total *total)</p><p><b

74、>　　{</b></p><p>　　int i,j,mark;</p><p>　　for(i=0;i<message->num;i++)//遍歷message中的所有字符信息</p><p><b>　　{</b></p><p>　　if(message->mes[i]!=

75、9; ')//字符不為空格時(shí)</p><p><b>　　{</b></p><p><b>　　mark=0;</b></p><p>　　for(j=0;j<total->num;j++)//在total中搜索當(dāng)前字符</p><p>　　if(total->tot[j

76、].data==message->mes[i])</p><p>　　//搜索到，則此字符次數(shù)加1，mark標(biāo)志為1</p><p><b>　　{</b></p><p>　　total->tot[j].num++;</p><p><b>　　mark=1;</b></p>

77、;<p><b>　　break;</b></p><p><b>　　}</b></p><p>　　if(mark==0)</p><p>　　//未搜索到，新建字符種類(lèi)，保存進(jìn)total中，字符類(lèi)加1</p><p><b>　　{</b></p>

78、;<p>　　total->tot[total->num].data=message->mes[i];</p><p>　　total->tot[total->num].num=1;</p><p>　　total->num++;</p><p><b>　　}</b></p>&

79、lt;p><b>　　}</b></p><p><b>　　}</b></p><p>　　}//統(tǒng)計(jì)信息中各字符的出現(xiàn)次數(shù)</p><p>　　通過(guò)各權(quán)值的一一比較選取最小和次小兩權(quán)值建立二叉樹(shù)，記錄節(jié)點(diǎn)的左右孩子及雙親的位置關(guān)系最終構(gòu)建成哈夫曼樹(shù)，且記錄的左孩子權(quán)值比右孩子小</p><p&

80、gt;　　void HaffmanTree(Total *total,HNodetype HuffNode[])</p><p><b>　　{</b></p><p>　　int i,j,min1,min2,x1,x2;</p><p>　　首先初始化哈夫曼樹(shù)并存入葉子結(jié)點(diǎn)權(quán)值和信息</p><p>　　for(i=0

81、;i<2*(total->num)-1;i++)</p><p><b>　　{</b></p><p>　　if(i<=total->num-1)HuffNode[i].data=total->tot[i].data;</p><p>　　HuffNode[i].weight=total->tot[i].n

82、um;</p><p>　　HuffNode[i].parent=-1;</p><p>　　HuffNode[i].lchild=-1;</p><p>　　HuffNode[i].rchild=-1;</p><p><b>　　} </b></p><p>　　for(i=0;i

83、<total->num-1;i++)</p><p><b>　　{</b></p><p>　　min1=min2=MAXVALUE;</p><p><b>　　x1=x2=0;</b></p><p>　　接著選取最小x1和次小x2的兩權(quán)值</p><p>

84、　　for(j=0;j<total->num+i;j++) </p><p><b>　　{</b></p><p>　　if(HuffNode[j].parent==-1&&HuffNode[j].weight<min1)</p><p><b>　　{</b></p>&

85、lt;p>　　min2=min1;</p><p><b>　　x2=x1;</b></p><p>　　min1=HuffNode[j].weight;</p><p><b>　　x1=j;</b></p><p><b>　　}</b></p><

86、;p><b>　　else</b></p><p>　　if(HuffNode[j].parent==-1&&HuffNode[j].weight<min2) </p><p>　　min2=HuffNode[j].wei

87、ght;</p><p><b>　　x2=j;</b></p><p><b>　　}</b></p><p>　　HuffNode[x1].parent=total->num+i;//修改親人結(jié)點(diǎn)位置</p><p>　　HuffNode[x2].parent=total->num+

88、i;</p><p>　　HuffNode[total->num+i].weight=HuffNode[x1].weight+HuffNode[x2].weight; 最后選出的左孩子比右孩子權(quán)值小</p><p>　　HuffNode[total->num+i].lchild=x1; </p><p>　　HuffNode[total->num+

89、i].rchild=x2;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　哈夫曼樹(shù)構(gòu)建成功</b></p><p>　　在建立的哈夫曼樹(shù)基礎(chǔ)上，利用數(shù)組使左分支為0，右分支為1，從葉結(jié)點(diǎn)向上直到根結(jié)點(diǎn)建立哈夫曼編碼，

90、并保存每個(gè)葉結(jié)點(diǎn)起始位。該函數(shù)利用了while的循環(huán)并多次利用for循環(huán)以完成目標(biāo)</p><p>　　void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)</p><p><b>　　{</b></p><p>　　int i,j,c,p;</p

91、><p>　　HCodetype cd;</p><p>　　for(i=0;i<total->num;i++)//建立葉子結(jié)點(diǎn)個(gè)數(shù)的編碼</p><p><b>　　{</b></p><p>　　cd.start=total->num-1;//起始位的初始化</p><p>　　

92、p=HuffNode[i].parent;</p><p><b>　　c=i;</b></p><p>　　while(p!=-1)//從葉結(jié)點(diǎn)向上爬直到到達(dá)根結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　if(HuffNode[p].lchild==c)//左分支都為0<

93、;/p><p>　　cd.bit[cd.start]=0;</p><p><b>　　else</b></p><p>　　cd.bit[cd.start]=1;//右分支都為1</p><p>　　cd.start--;//起始位向前移動(dòng)</p><p><b>　　c=p;</b

94、></p><p>　　p=HuffNode[p].parent;</p><p><b>　　}</b></p><p>　　for(j=cd.start+1;j<total->num;j++)</p><p>　　//保存求出的每個(gè)葉結(jié)點(diǎn)編碼和起始位</p><p>　　Hu

95、ffCode[i].bit[j]=cd.bit[j];</p><p>　　HuffCode[i].start=cd.start;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　哈夫曼編碼的建立成功</p><p>　　利

96、用文件的輸入輸出規(guī)則打開(kāi)HCode文件，打開(kāi)失敗則結(jié)束操作，否則將信息利用數(shù)組及for循環(huán)寫(xiě)進(jìn)文件</p><p>　　void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)</p><p><b>　　{</b></p><p><b>　

97、　int i,j;</b></p><p>　　ofstream outfile("c:\\HCode.txt",ios::in|ios::out);</p><p>　　if(!outfile)//打開(kāi)失敗則結(jié)束并輸出</p><p><b>　　{</b></p><p>　　cout

98、<<"打開(kāi)c:\\HCode.txt文件失敗"<<endl;</p><p><b>　　exit(1);</b></p><p><b>　　}</b></p><p>　　for(i=0;i<total->num;i++)//寫(xiě)文件</p><

99、p><b>　　{</b></p><p>　　outfile.put(HuffNode[i].data);</p><p>　　outfile<<" ";</p><p>　　for(j=HuffCode[i].start+1;j<total->num;j++)</p><

100、;p>　　outfile<<HuffCode[i].bit[j];</p><p>　　outfile<<endl;</p><p><b>　　} </b></p><p>　　cout<<"編碼規(guī)則寫(xiě)進(jìn)文件成功"<<endl;</p><p>

101、;　　outfile.close();//關(guān)閉文件</p><p><b>　　}</b></p><p>　　void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking)</p><p><b>

102、　　{</b></p><p>　　int i,j,m;</p><p>　　for(i=0;i<message->num;i++)//遍歷信息</p><p><b>　　{</b></p><p>　　if(message->mes[i]==' ')</p>

103、<p>　　//碰到空格則以-1形式保存進(jìn)locked數(shù)組中</p><p><b>　　{</b></p><p>　　locking->locked[locking->num]=-1;</p><p>　　locking->num++;</p><p><b>　　}</

104、b></p><p><b>　　else</b></p><p>　　for(j=0;j<total->num;j++)//搜索信息對(duì)應(yīng)的編碼</p><p><b>　　{</b></p><p>　　if(HuffNode[j].data==message->mes[i

105、])</p><p>　　for(m=HuffCode[j].start+1;m<total->num;m++)</p><p><b>　　{</b></p><p>　　locking->locked[locking->num]=HuffCode[j].bit[m];</p><p>　　lo

106、cking->num++;//locked數(shù)組總數(shù)加1</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　}//給文件信息加密編碼</p><p>　　voi

107、d writing_lock(Locking *locking)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　ofstream outfile("c:\\locking.txt",ios::in|ios::out);</p>

108、<p>　　if(!outfile)//打開(kāi)失敗則結(jié)束</p><p><b>　　{</b></p><p>　　cout<<"打開(kāi)c:\\locking.txt文件失敗"<<endl;</p><p><b>　　exit(1);</b></p>&

109、lt;p><b>　　}</b></p><p>　　for(i=0;i<locking->num;i++)//寫(xiě)文件</p><p>　　if(locking->locked[i]==-1)</p><p>　　outfile.put(' ');</p><p><b>

110、;　　else</b></p><p>　　outfile<<locking->locked[i];</p><p>　　cout<<"已編碼信息寫(xiě)進(jìn)文件成功"<<endl;</p><p>　　outfile.close();//關(guān)閉文件</p><p>　　}//將

111、哈夫曼編碼后的密文信息寫(xiě)進(jìn)文件</p><p>　　void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total)</p><p><b>　　{</b></p><p>　　int i,j,mark[100],sta

112、rt[100],min,max;</p><p>　　ofstream outfile("c:\\translate.txt",ios::in|ios::out);//打開(kāi)文件</p><p>　　if(!outfile)//打開(kāi)失敗則結(jié)束</p><p><b>　　{</b></p><p>　　

113、cout<<"打開(kāi)c:\\translate.txt文件失敗"<<endl;</p><p><b>　　exit(1);</b></p><p><b>　　}</b></p><p>　　for(i=0;i<total->num;i++)//start數(shù)組初始化&

114、lt;/p><p>　　start[i]=HuffCode[i].start+1;</p><p>　　for(i=0;i<total->num;i++)//mark數(shù)組初始化</p><p>　　mark[i]=1;</p><p><b>　　min=0;</b></p><p>　　

115、for(max=0;max<locking->num;max++)//寫(xiě)文件</p><p><b>　　{</b></p><p>　　if(locking->locked[max]==-1)//碰到空格信息則直接輸出空格</p><p><b>　　{</b></p><p>

116、　　outfile.put(' ');</p><p><b>　　min++;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p>&

117、lt;p>　　for(i=min;i<=max;i++)//查找從min開(kāi)始到max的編碼對(duì)應(yīng)的信息</p><p><b>　　{</b></p><p>　　for(j=0;j<total->num;j++) </p><p><b>　　{

118、</b></p><p>　　if(start[j]==total->num+1)</p><p>　　mark[j]=0;//對(duì)應(yīng)編碼比所給編碼短則不在比較</p><p>　　if(mark[j]==1&&locking->locked[i]==HuffCode[j].bit[start[j]])</p>&

119、lt;p>　　start[j]++;</p><p><b>　　else</b></p><p>　　mark[j]=0;</p><p>　　} </p><p><b>　　}</b></p><p>　　for(

120、i=0;i<total->num;i++)//找到對(duì)應(yīng)信息，則寫(xiě)進(jìn)文件</p><p><b>　　{</b></p><p>　　if(mark[i]==1&&start[i]==total->num)</p><p><b>　　{</b></p><p>　　

121、outfile.put(HuffNode[i].data);</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(i!=total->num)</p>&

122、lt;p>　　min=max+1;</p><p>　　for(i=0;i<total->num;i++)//start數(shù)組初始化 </p><p>　　start[i]=HuffCode[i].start+1; </p><p>　　for(i=0;i<total->num;i++)

123、//mark數(shù)組初始化</p><p>　　mark[i]=1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　cout<<"翻譯信息寫(xiě)進(jìn)文件成功"<<endl;</p><p>

124、;　　outfile.close();//關(guān)閉文件</p><p><b>　?。?lt;/b></p><p>　　5.程序測(cè)試結(jié)果及問(wèn)題分析</p><p>　　5.1 程序測(cè)試結(jié)果</p><p>　　在C盤(pán)中輸入一個(gè)reading的文本文檔</p><p>　　運(yùn)行后有如下界面再選擇操作代碼1：

125、</p><p>　　再選擇2，即出現(xiàn)如下哈夫曼編碼界面：</p><p>　　選擇代碼3，使程序運(yùn)行，信息寫(xiě)進(jìn)文件：</p><p><b>　　5.2 問(wèn)題分析</b></p><p>　　程序的設(shè)計(jì)過(guò)程中，我們遇到不少問(wèn)題，比如對(duì)文件的讀寫(xiě)不能精確的掌握，所以這部分的設(shè)計(jì)過(guò)程中總免不了要翻書(shū)，有的時(shí)侯會(huì)打開(kāi)文件之后

126、忘記outfile.close();在哈夫曼編碼的時(shí)候，在reading的文件中的拼寫(xiě)錯(cuò)誤使我們運(yùn)行過(guò)多次，但最終還是發(fā)現(xiàn)了，語(yǔ)法的錯(cuò)誤導(dǎo)致浪費(fèi)了很多時(shí)間，針對(duì)不同的電腦程序運(yùn)行有的會(huì)出現(xiàn)不同的結(jié)果，比如：有的電腦只需要輸入一個(gè)reading文件就可以，但有的電腦運(yùn)行就需要把writing等的都寫(xiě)出來(lái)，才能運(yùn)行，這可能是電腦的系統(tǒng)問(wèn)題，但最終還是克服了。最主要的是編寫(xiě)程序是的細(xì)節(jié)錯(cuò)誤，但那是對(duì)算法的一種真正的考察，如果哈夫曼的算法不能熟

127、悉的寫(xiě)出，說(shuō)明其思想沒(méi)有滲透這才是問(wèn)題的關(guān)鍵，但是我們還是齊心協(xié)力把它給寫(xiě)出來(lái)了。</p><p><b>　　6.總結(jié)</b></p><p>　　通過(guò)本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，我學(xué)習(xí)了很多在上課沒(méi)懂的知識(shí)，并對(duì)求哈夫曼樹(shù)及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識(shí)，真正學(xué)會(huì)一種算法了。當(dāng)求解一個(gè)算法時(shí),不是拿到問(wèn)題就不加思索地

128、做，而是首先要先對(duì)它有個(gè)大概的了解，接著再詳細(xì)地分析每一步怎么做，無(wú)論自己以前是否有處理過(guò)相似的問(wèn)題，只要按照以上的步驟，必定會(huì)順利地做出來(lái)。</p><p>　　這次課程設(shè)計(jì)，我在編輯中犯了不應(yīng)有的錯(cuò)誤，設(shè)計(jì)統(tǒng)計(jì)字符和合并時(shí)忘記應(yīng)該怎樣保存保存數(shù)據(jù)，在不斷分析后明確并改正了錯(cuò)誤和疏漏，使我的程序有了更高的質(zhì)量。這不僅是程序設(shè)計(jì),更是鍛煉我們處理問(wèn)題的能力,同時(shí)也使我們了解到團(tuán)隊(duì)合作的可貴.編寫(xiě)程序是件細(xì)心活,稍

129、不留神就會(huì)出錯(cuò),這就必須要求我們對(duì)待事情要認(rèn)真!在編寫(xiě)程序的過(guò)程中,錯(cuò)誤不斷出現(xiàn),不同的類(lèi)型(如少寫(xiě)了一個(gè)符號(hào),寫(xiě)錯(cuò)了字母,用錯(cuò)了函數(shù)等等)層出不窮,這考驗(yàn)我們待事細(xì)心,耐心,能不能堅(jiān)持到底,不能半途而廢。</p><p>　　三人行必有我?guī)?遇到問(wèn)題我們一起討論,研究,錯(cuò)了再寫(xiě),寫(xiě)了在改.經(jīng)過(guò)多次的修改,調(diào)試,運(yùn)行,添加,終于最后在大家的歡呼聲中,完成了我們的任務(wù).雖說(shuō)是累了點(diǎn)，但我們也從中找到了自己的快樂(lè)，每

130、當(dāng)完成一個(gè)新的函數(shù)時(shí)，那心情是激動(dòng)啊,這畢竟是自己弄出來(lái)的,同時(shí)也使我感受到了學(xué)習(xí)的快樂(lè)！</p><p><b>　　7.參考文獻(xiàn)</b></p><p>　　[1]嚴(yán)蔚敏，吳偉民．《數(shù)據(jù)結(jié)構(gòu)：C語(yǔ)言版》．北京：清華大學(xué)出版社．</p><p>　　[2]陳維興，林小茶.《C++面向?qū)ο蟪绦蛟O(shè)計(jì)教程（第三版）》北京：清華大學(xué)出版社． &l