數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---哈夫曼樹(shù)的應(yīng)用

1、<p><b>　　課 程 設(shè) 計(jì)</b></p><p><b>　　課程設(shè)計(jì)任務(wù)書(shū)</b></p><p>　　2011～2012學(xué)年第 2學(xué)期</p><p>　　學(xué)生姓名： **** 專業(yè)班級(jí)：**********</p><p>　　指導(dǎo)教師： ***

2、 工作部門(mén)： 計(jì)算機(jī)學(xué)院 </p><p>　　一、課程設(shè)計(jì)題目：哈夫曼樹(shù)的應(yīng)用</p><p>　　二、課程設(shè)計(jì)內(nèi)容（含技術(shù)指標(biāo)）</p><p>　　1.從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)并將它存于文件hfmTree中.將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式（比如樹(shù)）顯示在終端上；</p><p>

3、;　　2.利用已經(jīng)建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件htmTree中讀入），對(duì)文件Text.txt中的正文進(jìn)行編碼，然后將結(jié)果存入文件Code.txt中。</p><p>　　3.利用已建好的哈夫曼樹(shù)將文件Code.txt中的代碼進(jìn)行譯碼，結(jié)果存入文件Text.txt中，并輸出結(jié)果。</p><p><b>　　三、進(jìn)度安排</b></p><p

4、>　　2012年6月11日 設(shè)計(jì)動(dòng)員，布置任務(wù)</p><p>　　2012年6月12日~2012年6月13日，查閱資料，分析、討論與設(shè)計(jì)</p><p>　　2012年6月14日~2011年6月19日，編寫(xiě)程序，進(jìn)行調(diào)試</p><p>　　2012年6月20日~2011年6月21日，完成模塊聯(lián)調(diào)，進(jìn)行測(cè)試</p><p>　　201

5、2年6月22日，成果驗(yàn)收，完成設(shè)計(jì)報(bào)告、答辯</p><p><b>　　四、基本要求</b></p><p>　　1．分析問(wèn)題，給出數(shù)學(xué)模型，選擇數(shù)據(jù)結(jié)構(gòu)。</p><p>　　2．設(shè)計(jì)算法，給出算法描述，給出源程序清單。</p><p>　　3．編輯、編譯、調(diào)試源程序，撰寫(xiě)課程設(shè)計(jì)報(bào)告。</p><

6、;p>　　4．界面友好，函數(shù)功能要?jiǎng)澐趾?lt;/p><p>　　5．總體設(shè)計(jì)應(yīng)畫(huà)一流程圖</p><p>　　6．程序要加必要的注釋</p><p>　　7．要提供程序測(cè)試方案</p><p>　　8．程序一定要經(jīng)得起測(cè)試，寧可功能少一些，也要能運(yùn)行起來(lái)，不能運(yùn)行的程序是沒(méi)有價(jià)值的。 </p><p>

7、;<b>　　目 錄</b></p><p><b>　　摘要1</b></p><p><b>　　一 概述2</b></p><p>　　1.課程設(shè)計(jì)的目的2</p><p>　　2.課程設(shè)計(jì)的要求2</p><p>　　3.哈夫曼算法的實(shí)

8、現(xiàn)2</p><p>　　二 總體方案設(shè)計(jì)3</p><p>　　1.整體的設(shè)計(jì)思路3</p><p>　　2.算法的整體思路3</p><p><b>　　3.工作內(nèi)容3</b></p><p><b>　　4.關(guān)鍵問(wèn)題4</b></p><

9、p><b>　　三 詳細(xì)設(shè)計(jì)5</b></p><p>　　1.總體設(shè)計(jì)流程圖5</p><p>　　2.建立哈夫曼樹(shù)5</p><p><b>　　3.編碼功能6</b></p><p><b>　　4.譯碼功能6</b></p><p&g

10、t;　　四 程序的調(diào)試與運(yùn)行結(jié)果說(shuō)明7</p><p>　　五 課程設(shè)計(jì)總結(jié)10</p><p><b>　　程序部分代碼11</b></p><p><b>　　參考文獻(xiàn)14</b></p><p><b>　　摘要</b></p><p>　

11、　隨著計(jì)算機(jī)的普遍應(yīng)用與日益發(fā)展，其應(yīng)用早已不局限于簡(jiǎn)單的數(shù)值運(yùn)算，而涉及到問(wèn)題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計(jì)以及設(shè)計(jì)最短路線等復(fù)雜的非數(shù)值處理和操作。算法與數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)就是為以后利用計(jì)算機(jī)資源高效地開(kāi)發(fā)非數(shù)值處理的計(jì)算機(jī)程序打下堅(jiān)實(shí)的理論、方法和技術(shù)基礎(chǔ)。</p><p>　　算法與數(shù)據(jù)結(jié)構(gòu)旨在分析研究計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象的特性，以便選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，從而使建立在其上的解決問(wèn)題的算法達(dá)到最優(yōu)。<

12、/p><p>　　數(shù)據(jù)結(jié)構(gòu)是在整個(gè)計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語(yǔ)。它用來(lái)反映一個(gè)數(shù)據(jù)的內(nèi)部構(gòu)成，即一個(gè)數(shù)據(jù)由那些成分?jǐn)?shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。</p><p>　　《數(shù)據(jù)結(jié)構(gòu)》主要介紹一些最常用的數(shù)據(jù)結(jié)

13、構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計(jì)算機(jī)中的存儲(chǔ)表示，以及在其上進(jìn)行各種運(yùn)算時(shí)的實(shí)現(xiàn)算法，并對(duì)算法的效率進(jìn)行簡(jiǎn)單的分析和討論。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件之間的一門(mén)計(jì)算機(jī)專業(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)行處

14、理。通過(guò)課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。</p><p><b>　　一 概述</b></p><p><b>　　1.課程設(shè)計(jì)的目的</b></p><p>　　1．理解和掌握該課程中的有關(guān)基本概念，程序設(shè)計(jì)思想和方法。</p><p>　　2．培養(yǎng)綜合運(yùn)用

15、所學(xué)知識(shí)獨(dú)立完成課題的能力。</p><p>　　3．培養(yǎng)勇于探索、嚴(yán)謹(jǐn)推理、實(shí)事求是、有錯(cuò)必改，用實(shí)踐來(lái)檢驗(yàn)理論，全方位考慮問(wèn)題等科學(xué)技術(shù)人員應(yīng)具有的素質(zhì)。</p><p>　　4．掌握從資料文獻(xiàn)、科學(xué)實(shí)驗(yàn)中獲得知識(shí)的能力，提高學(xué)生從別人經(jīng)驗(yàn)中找到解決問(wèn)題的新途徑的悟性，初步培養(yǎng)工程意識(shí)和創(chuàng)新能力。</p><p><b>　　2.課程設(shè)計(jì)的要求<

16、/b></p><p>　　一個(gè)完整的系統(tǒng)至少具有以下功能：</p><p>　　(1) I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立赫夫曼樹(shù)，并將它存于文件hfmTree中。</p><p>　　(2) E：編碼（Encoding）。利用已建好的赫夫曼樹(shù)（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件T

17、oBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。</p><p>　　(3) D：譯碼（Decoding）。利用已建好的赫夫曼樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件Textfile中。</p><p>　　3.哈夫曼算法的實(shí)現(xiàn)</p><p>　　由哈夫曼樹(shù)的構(gòu)造過(guò)程可知，初始森林中共有n棵二叉樹(shù)，每棵樹(shù)中都僅有一個(gè)孤立的結(jié)點(diǎn)，

18、它們既是根，又是葉子。然后將當(dāng)前森林中的兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹(shù)，合并成一棵新二叉樹(shù)。每合并一次，森林中就減少一棵樹(shù)。顯然，要進(jìn)行n-l次合并，才能使森林中的二叉樹(shù)的數(shù)目，由n棵減少到剩下一棵最終的哈夫曼樹(shù)。并且每次合并，都要產(chǎn)生一個(gè)新結(jié)點(diǎn)，合并n-l次共產(chǎn)生n-1個(gè)新結(jié)點(diǎn)，顯然它們都是具有兩個(gè)孩子的分支結(jié)點(diǎn)。由此可知，最終求得的哈夫曼樹(shù)中共有2n-1個(gè)結(jié)點(diǎn)，其中n個(gè)葉結(jié)點(diǎn)是初始森林中的n個(gè)孤立結(jié)點(diǎn)，并且哈夫曼樹(shù)中沒(méi)有度為1的分支結(jié)點(diǎn)

19、。因此，在構(gòu)造哈夫曼樹(shù)時(shí)，可以設(shè)置一個(gè)大小為2n-1的數(shù)組ht保存哈夫曼樹(shù)中各結(jié)點(diǎn)的信息。</p><p><b>　　二 總體方案設(shè)計(jì)</b></p><p><b>　　1.整體的設(shè)計(jì)思路</b></p><p>　　利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。這要求在發(fā)送端通過(guò)一個(gè)編

20、碼系統(tǒng)對(duì)待傳輸預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼。對(duì)于雙工通道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。本課程設(shè)計(jì)實(shí)現(xiàn)這樣的信息收發(fā)站，編寫(xiě)一個(gè)哈夫曼碼的編/譯碼系統(tǒng)。</p><p>　　系統(tǒng)共分為四個(gè)子系統(tǒng)：初始化哈夫曼樹(shù)；編碼；譯碼；打印哈夫曼樹(shù)。</p><p>　　輸入相應(yīng)的數(shù)字后按回車鍵即可進(jìn)入相應(yīng)的系統(tǒng)。在相應(yīng)的系統(tǒng)內(nèi)可完成相應(yīng)的功能。各模塊相對(duì)獨(dú)立

21、，每個(gè)模塊用一個(gè)大型的函數(shù)來(lái)處理數(shù)據(jù)。</p><p><b>　　2.算法的整體思路</b></p><p>　　本系統(tǒng)能根據(jù)輸入的字符數(shù)生成哈夫曼樹(shù)，并自動(dòng)輸出各字符的哈夫曼編碼。通過(guò)對(duì)單鏈表的結(jié)點(diǎn)查找，結(jié)點(diǎn)插入等一些算法建立一個(gè)根據(jù)頭結(jié)點(diǎn)來(lái)插入數(shù)據(jù)的函數(shù)，通過(guò)對(duì)此函數(shù)的調(diào)用建立一個(gè)根據(jù)輸入的數(shù)據(jù)來(lái)輸入信息的函數(shù)。修改信息，排序，查找信息等模塊的函數(shù)均用同樣的方法

22、處理。</p><p><b>　　3.工作內(nèi)容</b></p><p>　　工作進(jìn)程安排：系統(tǒng)設(shè)計(jì)，詳細(xì)設(shè)計(jì)，編寫(xiě)代碼，結(jié)果測(cè)試與分析。</p><p>　　本人負(fù)責(zé)模塊：譯碼功能。</p><p>　　功能分析：譯碼（Decoding）。將codefile.txt文檔中的編碼以字符形式輸出。</p>&

23、lt;p>　　譯碼原則：在完成Huffman編碼后，我們利用其構(gòu)建的哈夫曼編碼樹(shù)來(lái)進(jìn)行譯碼。與編碼過(guò)程不同，譯碼過(guò)程中，我們將用戶輸入的二進(jìn)制代碼串依次與字符集中的每個(gè)字符的編碼進(jìn)行比較，從根結(jié)點(diǎn)出發(fā)，逐個(gè)讀入電文中的二進(jìn)制碼；若代碼為“0”，則走左子樹(shù)的根結(jié)點(diǎn)，否則走向右子樹(shù)的根結(jié)點(diǎn)；一旦到達(dá)葉子結(jié)點(diǎn)，便譯出代碼所對(duì)應(yīng)的字符。然后又重新從根結(jié)點(diǎn)開(kāi)始繼續(xù)譯碼，直到二進(jìn)制電文結(jié)束。</p><p><b

24、>　　實(shí)現(xiàn)代碼：</b></p><p>　　void Decoding()</p><p>　　{ cout << "下面對(duì)根目錄下文件codefile.txt中的字符進(jìn)行譯碼" << endl;</p><p>　　FILE *codef, *txtfile;</p><p&g

25、t;　　if ((txtfile = fopen("Textfile.txt", "w")) == NULL)// w 只寫(xiě)</p><p>　　{ cout << "不能打開(kāi)文件" << endl; }</p><p>　　if ((codef = fopen("codefile.tx

26、t", "r")) == NULL)// r 只讀</p><p>　　{ cout << "不能打開(kāi)文件" << endl; }</p><p>　　char *work, *work2, i2;</p><p>　　int i4 = 0, i, i3;</p>&

27、lt;p>　　unsigned long length = 10000;</p><p>　　work = (char*)malloc(length *sizeof(char));</p><p>　　fgets(work, length, codef);</p><p>　　work2 = (char*)malloc(length *sizeof(char)

28、);</p><p>　　i3 = 2 * n - 1;</p><p>　　for (i = 0; *(work + i - 1) != '\0'; i++)</p><p>　　{ i2 = *(work + i);</p><p>　　if (HT[i3].lchild == 0)</p><p

29、>　　{ *(work2 + i4) = *(z + i3 - 1);</p><p>　　i4++; i3 = 2 * n - 1; i--;</p><p><b>　　}</b></p><p>　　else if (i2 == '0')</p><p>　　i3

30、 = HT[i3].lchild;</p><p>　　else if (i2 == '1')</p><p>　　i3 = HT[i3].rchild;</p><p><b>　　}</b></p><p>　　*(work2 + i4) = '\0';</p><

31、p>　　fputs(work2, txtfile);</p><p>　　cout << "譯碼完成" << endl << "內(nèi)容寫(xiě)入根目錄下的文件txtfile.txt中" << endl<< endl;</p><p>　　cout << work2<<e

32、ndl;</p><p>　　free(work); free(work2);</p><p>　　fclose(txtfile); fclose(codef);</p><p><b>　　}</b></p><p><b>　　4.關(guān)鍵問(wèn)題</b></p>&

33、lt;p>　　（1）哈夫曼樹(shù)的構(gòu)建，輸入字符與權(quán)值后哈夫曼編碼的生成。</p><p>　?。?）編碼（Encoding）。輸入要編碼的字符，存入text.txt文檔中，通過(guò)編碼程序，將字符以哈夫曼編碼形式存在codefile.txt文檔中。</p><p>　?。?）將哈夫曼樹(shù)以樹(shù)型打印出來(lái)。</p><p><b>　　三 詳細(xì)設(shè)計(jì)</b&

34、gt;</p><p><b>　　1.總體設(shè)計(jì)流程圖</b></p><p>　　圖3-1 主要功能流程圖</p><p><b>　　2.建立哈夫曼樹(shù)</b></p><p>　　功能：1.進(jìn)入輸入系統(tǒng)后選擇需要進(jìn)行的操作步驟。輸入待編碼的字符數(shù)，并且隨即輸入編碼字符的權(quán)值。 </p&g

35、t;<p><b>　　3.編碼功能</b></p><p>　　功能：輸入需要編碼的字符，編碼后存入文檔。再輸出編碼。</p><p><b>　　4.譯碼功能</b></p><p>　　功能：選擇譯碼步驟，將Codefile.txt中的編碼進(jìn)行譯碼。</p><p>　　四 程序

36、的調(diào)試與運(yùn)行結(jié)果說(shuō)明</p><p><b>　　1.初始化哈夫曼樹(shù)</b></p><p><b>　　2.編碼功能</b></p><p><b>　　3.譯碼功能</b></p><p><b>　　4.打印哈夫曼樹(shù)</b></p>&

37、lt;p><b>　　5.調(diào)試分析</b></p><p>　　5.1 調(diào)試過(guò)程中遇到的問(wèn)題</p><p>　?。?）文件的調(diào)用與寫(xiě)入。</p><p>　　由于文件的內(nèi)容學(xué)習(xí)得不夠扎實(shí)，在從tobetran.txt文檔中讀取已經(jīng)輸入的字符進(jìn)行編碼時(shí)出現(xiàn)了問(wèn)題。程序首先能成功讀取字符，并進(jìn)行編碼存入Codefile.txt文檔中，但無(wú)法

38、再?gòu)腃odefile.txt文檔中讀出已經(jīng)編碼的值。</p><p>　　解決方法：設(shè)置一個(gè)全局結(jié)構(gòu)體變量來(lái)存放已經(jīng)在文件中存放的哈夫曼樹(shù)。</p><p>　?。?）Huffman樹(shù)的打印。</p><p>　　由于在學(xué)習(xí)中并未留意數(shù)據(jù)如何類似圖形輸出，算法思想也不了解。因此這一模塊無(wú)法成功完成。</p><p>　　解決方案：由其他組員完

39、成，但未完善解決，只是將內(nèi)存中的哈夫曼樹(shù)中各節(jié)點(diǎn)的值及其孩子輸出。</p><p>　　5.2 算法的時(shí)空分析</p><p><b>　　算法的時(shí)間復(fù)雜度：</b></p><p>　　Select(HuffmanTree HT,int end,int *s1,int *s2) O(n)</p><p>　　Hu

40、ffmanCoding(Huffman Hfm) O(n2)</p><p>　　InitHuffman(Huffman Hfm) O(n)</p><p>　　Encoding(Huffman Hfm) O(n)</p><p>　　Decoding(Huff

41、man Hfm) O(n)</p><p>　　Print(Huffman Hfm) O(n)</p><p><b>　　五 課程設(shè)計(jì)總結(jié)</b></p><p>　　通過(guò)為期半個(gè)月的課程設(shè)計(jì)，我們對(duì)《數(shù)據(jù)結(jié)構(gòu)》這門(mén)課程有了更深一步的了解。它是計(jì)算機(jī)程序設(shè)

42、計(jì)的重要理論技術(shù)基礎(chǔ)，在我們計(jì)算機(jī)專業(yè)的學(xué)習(xí)中占據(jù)著十分重要的地位。同時(shí)也使我們知道，要學(xué)好這門(mén)課程，僅學(xué)習(xí)書(shū)本上的知識(shí)是不夠的，還要有較強(qiáng)的實(shí)踐能力。因?yàn)槲覀儗W(xué)習(xí)知識(shí)就是為了實(shí)踐。而只有多實(shí)踐，多編寫(xiě)程序，才能更好的理解與掌握書(shū)本上的東西。</p><p>　　我從實(shí)踐中明白了C語(yǔ)言的模塊化設(shè)計(jì)的理論。將一個(gè)大任務(wù)分成若干個(gè)較小的任務(wù)，較小的任務(wù)又細(xì)分為更小的任務(wù)，直到更小的任務(wù)功能較為單一，便于實(shí)現(xiàn)為止，每個(gè)

43、小任務(wù)為一個(gè)模塊。各個(gè)模塊功能單一，獨(dú)立編程，獨(dú)立存放，單獨(dú)調(diào)試，可以為多個(gè)程序所調(diào)用，并可以由不同的人實(shí)現(xiàn)。</p><p>　　在以后的編程過(guò)程中，我會(huì)按照軟件開(kāi)發(fā)的方法，步驟，原則認(rèn)真的完成軟件開(kāi)發(fā)。不斷尋求最優(yōu)的解決問(wèn)題的辦法，使自己開(kāi)發(fā)出來(lái)的軟件運(yùn)行效率更高，功能更加完善。</p><p>　　對(duì)于自己解決不了的問(wèn)題可以在網(wǎng)上查找，找同學(xué)幫忙，復(fù)習(xí)教材相應(yīng)的內(nèi)容，并且不斷地學(xué)習(xí)新

44、知識(shí)，以使自己在軟件開(kāi)發(fā)方面跟上時(shí)代的發(fā)展。</p><p><b>　　程序部分代碼</b></p><p>　　// -----------------求赫夫曼編碼-----------------------</p><p>　　int min(HuffmanTree t, int i)</p><p>　　{

45、int j, flag;</p><p>　　int k = UINT_MAX; //k存最小權(quán)值，初值取整型最大值</p><p>　　for (j = 1; j <= i; j++)//對(duì)于前i個(gè)結(jié)點(diǎn),尋找第一最小值</p><p>　　if (t[j].weight < k && t[j].parent == 0) </p&g

46、t;<p>　　k = t[j].weight, flag = j; </p><p>　　t[flag].parent = 1;</p><p>　　return flag;</p><p><b>　　}</b></p><p>　　//--------------------slect函數(shù)------

47、----------------</p><p>　　void select(HuffmanTree t, int i, int &s1, int &s2)</p><p>　　{ int j;</p><p>　　s1 = min(t, i);//尋找第一個(gè)最小值</p><p>　　s2 = min(t, i);//尋

48、找第二最小值</p><p>　　if (s1 > s2)</p><p>　　{ j = s1;</p><p><b>　　s1 = s2;</b></p><p><b>　　s2 = j;</b></p><p><b>　　}</b>

49、;</p><p><b>　　}</b></p><p>　　// --------------構(gòu)造赫夫曼樹(shù)--------------------</p><p>　　void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)</p>

50、<p>　　{ int m, i, s1, s2, start;//*m表示結(jié)點(diǎn)個(gè)數(shù)*//</p><p><b>　　int c, f;</b></p><p>　　HuffmanTree p;</p><p><b>　　char *cd;</b></p><p>　　if (n &

51、lt;= 1)//葉子結(jié)點(diǎn)數(shù)不大于n</p><p><b>　　return ;</b></p><p>　　m = 2 * n - 1; //n個(gè)葉子結(jié)點(diǎn)的哈弗曼樹(shù)共有m個(gè)結(jié)點(diǎn)</p><p>　　HT = (HuffmanTree)malloc((m + 1) *sizeof(HTNode)); // 0號(hào)單元未用</p>

52、<p>　　for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++w)</p><p>　　{ p->weight = *w;//*賦權(quán)值*//</p><p>　　p->parent = 0;//*雙親域?yàn)榭眨ㄊ歉Y(jié)點(diǎn)）*//</p><p>　　p->lchild = 0;//*左右孩子

53、為空（是葉子結(jié)點(diǎn)）*//</p><p>　　p->rchild = 0;</p><p><b>　　}</b></p><p>　　for (; i <= m; ++i, ++p) //*i從n+1到m*///</p><p>　　p->parent=0; //*雙親域?yàn)榭眨ㄊ歉Y(jié)點(diǎn)）*//<

54、;/p><p>　　p->lchild=0; //*左右孩子為空（是葉子結(jié)點(diǎn)）*//</p><p>　　p->rchild=0;*/</p><p>　　p->parent = 0;</p><p>　　for (i = n + 1; i <= m; ++i)</p><p>　　{ se

55、lect(HT, i - 1, s1, s2);</p><p>　　HT[s1].parent = HT[s2].parent = i;//*i號(hào)單元是s1和s2的雙親*//</p><p>　　HT[i].lchild = s1;//*i號(hào)單元的左右孩子分別是s1和s2*//</p><p>　　HT[i].rchild = s2;</p><

56、;p>　　HT[i].weight = HT[s1].weight + HT[s2].weight; }</p><p>　　HC = (HuffmanCode)malloc((n + 1) *sizeof(char*));</p><p>　　cd = (char*)malloc(n *sizeof(char)); // 分配求編碼的工作空間</p><p&g

57、t;　　cd[n - 1] = '\0'; // 編碼結(jié)束符</p><p>　　for (i = 1; i <= n; i++)</p><p>　　{ start = n - 1; // 編碼結(jié)束符位置</p><p>　　for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f

58、].parent)</p><p>　　if (HT[f].lchild == c) //*c是其雙親的左孩子*//</p><p>　　cd[--start] = '0';</p><p><b>　　else</b></p><p>　　cd[--start] = '1'; </

59、p><p>　　HC[i] = (char*)malloc((n - start) *sizeof(char));</p><p>　　strcpy(HC[i], &cd[start]); // 從cd復(fù)制編碼(串)到HC</p><p><b>　　}</b></p><p>　　free(cd); // 釋放工作

60、空間</p><p><b>　　}</b></p><p>　　//------------------------打印赫夫曼樹(shù)的函數(shù)-----------------------</p><p>　　void coprint(HuffmanTree start, HuffmanTree HT)</p><p>　　{

61、 if (start != HT)</p><p>　　{ FILE *TreePrint;</p><p>　　if ((TreePrint = fopen("TreePrint.txt", "a")) == NULL)</p><p>　　{ cout << "創(chuàng)建文件失敗"

62、; << endl;</p><p><b>　　return ;</b></p><p><b>　　}</b></p><p>　　numb++; //該變量為已被聲明為全局變量</p><p>　　coprint(HT + start->rchild, HT);</p&

63、gt;<p>　　cout << setw(5 *numb) << start->weight << endl;</p><p>　　fprintf(TreePrint, "%d\n", start->weight);</p><p>　　coprint(HT + start->lchild, HT);

64、</p><p><b>　　numb--;</b></p><p>　　fclose(TreePrint);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void Tree_printing(Hu

65、ffmanTree HT, int w)</p><p>　　{ HuffmanTree p;</p><p>　　p = HT + w;</p><p>　　cout << "下面打印赫夫曼樹(shù)" << endl;</p><p>　　coprint(p, HT);</p><

66、p>　　cout << "打印工作結(jié)束" << endl;</p><p><b>　　}</b></p><p>　　//------------------------主函數(shù)------------------------------------</p><p>　　void main()&

67、lt;/p><p>　　{ char choice;</p><p>　　while (choice != 'q')</p><p>　　{ cout << " "<<" 哈夫曼編碼解碼系統(tǒng)" << endl;</p><p>　

68、　cout << "1.初始化哈夫曼樹(shù)" << " 2.編 碼 功 能" << endl;</p><p>　　cout << "3.譯 碼 功 能 " << " 4.打印哈夫曼樹(shù)" << endl;</p><p>　　

69、cout << "5.退 出 系 統(tǒng)" << endl;</p><p>　　cout<<"請(qǐng)輸入您要進(jìn)行的操作：";</p><p>　　cin >> choice;</p><p>　　switch (choice)</p><p>　　{ cas

70、e '1':</p><p>　　Initialization();</p><p><b>　　break;</b></p><p><b>　　case '2':</b></p><p>　　InputCode();</p><p>　　E

71、ncoding();</p><p><b>　　break;</b></p><p><b>　　case '3':</b></p><p>　　Decoding();</p><p><b>　　break;</b></p><p>

72、<b>　　case '4':</b></p><p>　　Tree_printing(HT, 2 *n - 1);</p><p><b>　　break;</b></p><p><b>　　case '5':</b></p><p><

73、;b>　　default:</b></p><p>　　cout << "input error" << endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　f

74、ree(z);</b></p><p><b>　　free(w);</b></p><p><b>　　free(HT);</b></p><p><b>　　}</b></p><p><b>　　參考文獻(xiàn)</b></p>&

75、lt;p>　　[1]鄧又明，數(shù)據(jù)結(jié)構(gòu)（第一版），北京，地質(zhì)出版社，2007年8月。</p><p>　　[2]劉天印，C語(yǔ)言程序設(shè)計(jì)（第一版），北京，科學(xué)出版社，2007年3月。</p><p>　　[3]嚴(yán)蔚敏，吳偉民編著，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），北京；清華大學(xué)出版社，2005</p><p>　　[4]嚴(yán)蔚敏，陳文博編著，數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程，北京；清華大