數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)哈夫曼編碼

1、<p>　　《 數(shù)據(jù)結(jié)構(gòu)與算法 》課程設(shè)計(jì)</p><p>　?。?009/2010學(xué)年第二學(xué)期第20周）</p><p><b>　　指導(dǎo)教師： </b></p><p>　　班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)（3）班</p><p><b>　　學(xué)號(hào)：</b></p><p&

2、gt;<b>　　姓名：</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)</p><p><b>　　目 錄</b></p><p><b>　　前言</b></p><p><b>　　摘要</b></p><p>

3、　　《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)任務(wù)書(shū)</p><p><b>　　二、實(shí)驗(yàn)?zāi)康?lt;/b></p><p>　　三、題目--赫夫曼編碼/譯碼器</p><p><b>　　問(wèn)題描述</b></p><p><b>　　基本要求</b></p><p><

4、;b>　　測(cè)試要求</b></p><p><b>　　實(shí)現(xiàn)提示</b></p><p>　　需求分析--具體要求</p><p><b>　　概要設(shè)計(jì)</b></p><p><b>　　程序說(shuō)明</b></p><p><b&

5、gt;　　詳細(xì)設(shè)計(jì)</b></p><p><b>　　實(shí)驗(yàn)心得與體會(huì)</b></p><p><b>　　前言</b></p><p><b>　　摘要</b></p><p>　　隨著計(jì)算機(jī)的普遍應(yīng)用與日益發(fā)展，其應(yīng)用早已不局限于簡(jiǎn)單的數(shù)值運(yùn)算，而涉及到問(wèn)題的分

6、析、數(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)。</p><p>　　數(shù)據(jù)結(jié)構(gòu)是在整個(gè)計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使

7、用的術(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é)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計(jì)算機(jī)中的存儲(chǔ)表示，以及在其上進(jìn)行各種運(yùn)

8、算時(shí)的實(shí)現(xiàn)算法，并對(duì)算法的效率進(jìn)行簡(jiǎn)單的分析和討論。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件之間的一門計(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)行處理。通過(guò)課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。&l

9、t;/p><p>　　《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)任務(wù)書(shū)</p><p>　　《數(shù)據(jù)結(jié)構(gòu)與算法》是計(jì)算機(jī)專業(yè)重要的核心課程之一，在計(jì)算機(jī)專業(yè)的學(xué)習(xí)過(guò)程中占有非常重要的地位?！稊?shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)》就是要運(yùn)用本課程以及到目前為止的有關(guān)課程中的知識(shí)和技術(shù)來(lái)解決實(shí)際問(wèn)題。特別是面臨非數(shù)值計(jì)算類型的應(yīng)用問(wèn)題時(shí)，需要選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)出滿足一定時(shí)間和空間限制的有效算法。</p>&l

10、t;p>　　本課程設(shè)計(jì)要求同學(xué)獨(dú)立完成一個(gè)較為完整的應(yīng)用需求分析。并在設(shè)計(jì)和編寫(xiě)具有一定規(guī)模程序的過(guò)程中，深化對(duì)《數(shù)據(jù)結(jié)構(gòu)與算法》課程中基本概念、理論和方法的理解；訓(xùn)練綜合運(yùn)用所學(xué)知識(shí)處理實(shí)際問(wèn)題的能力，強(qiáng)化面向?qū)ο蟮某绦蛟O(shè)計(jì)理念；使自己的程序設(shè)計(jì)與調(diào)試水平有一個(gè)明顯的提高。 </p><p><b>　　二、實(shí)驗(yàn)?zāi)康?lt;/b></p><p>　　數(shù)據(jù)結(jié)構(gòu)作為一

11、門學(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)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對(duì)應(yīng)，通過(guò)這組算法集合可以對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。</p><p>　　在當(dāng)今信息時(shí)代，信息技術(shù)己

12、成為當(dāng)代知識(shí)經(jīng)濟(jì)的核心技術(shù)。我們時(shí)刻都在和數(shù)據(jù)打交道。比如人們?cè)谕獬龉ぷ鲿r(shí)找最短路徑，在銀行查詢存款、通過(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><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ī)硬件之間的一門計(jì)

13、算機(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)行處理。通過(guò)課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過(guò)此次課程設(shè)計(jì)主要達(dá)到以下目的：</p><p>　　了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)

14、方法，具備初步的獨(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)題的能力；</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>

15、;　　三、題目--赫夫曼編碼/譯碼器</p><p><b>　　1. 問(wèn)題描述</b></p><p>　　利用赫夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收

16、發(fā)站編寫(xiě)一個(gè)赫夫曼碼的編/譯碼系統(tǒng)。</p><p><b>　　基本要求</b></p><p>　　一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：</p><p>　　(1) I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立赫夫曼樹(shù)，并將它存于文件hfmTree中。</p><p>　

17、　(2) E：編碼（Encoding）。利用已建好的赫夫曼樹(shù)（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。</p><p>　　(3) D：譯碼（Decoding）。利用已建好的赫夫曼樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件Textfile中。</p><p><b>　　以下為選做：&l

18、t;/b></p><p>　　(4) P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫(xiě)入文件CodePrin中。</p><p>　　(5) T：印赫夫曼樹(shù)（Tree printing）。將已在內(nèi)存中的赫夫曼樹(shù)以直觀的方式（比如樹(shù)）顯示在終端上，同時(shí)將此字符形式的赫夫曼樹(shù)寫(xiě)入文件TreePrint 中。<

19、;/p><p><b>　　測(cè)試要求</b></p><p>　　(1) 已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其頻率分別為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，試設(shè)計(jì)赫夫曼編碼。</p><p>　　(2) 用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立赫夫曼樹(shù)，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS P

20、ROGRAME IS MY FAVORITE”。</p><p><b>　　實(shí)現(xiàn)提示</b></p><p>　　(1) 編碼結(jié)果以文本方式存儲(chǔ)在文件Codefile中。</p><p>　　(2) 用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“Q”，表示退出運(yùn)行Quit。請(qǐng)用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜

21、單，直至某次用戶選擇了“Q”為止。</p><p>　　(3) 在程序的一次執(zhí)行過(guò)程中，第一次執(zhí)行I，D或C命令之后，赫夫曼樹(shù)已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。</p><p><b>　　四、具體要求：</b></p><p>　　課程設(shè)計(jì)成果的內(nèi)容必須由以下四個(gè)部分組成，缺一不可。&l

22、t;/p><p>　　(1) 上交源程序：學(xué)生按照實(shí)驗(yàn)題目的具體要求所開(kāi)發(fā)的所有源程序（應(yīng)該放到一個(gè)文件夾中）；</p><p>　　(2) 上交程序的說(shuō)明文件：（保存在.txt中）在說(shuō)明文檔中應(yīng)該寫(xiě)明上交程序所在的目錄，上交程序的主程序文件名，如果需要安裝，要有程序的安裝使用說(shuō)明；</p><p>　　(3) 設(shè)計(jì)報(bào)告：（保存在word 文檔中，文件名要求： 按照“姓

23、名_學(xué)號(hào)_設(shè)計(jì)題目”起名，如文件名為“ 張三_XXX_赫夫曼編碼 ”.doc。打印稿用A4紙）。</p><p><b>　　其中包括:</b></p><p><b>　　題目；</b></p><p><b>　　實(shí)驗(yàn)?zāi)康模?lt;/b></p><p>　　需求分析：在該部分中

24、敘述實(shí)現(xiàn)的功能要求；</p><p><b>　　概要設(shè)計(jì)：</b></p><p>　　在此說(shuō)明每個(gè)部分的算法設(shè)計(jì)說(shuō)明（可以是描述算法的流程圖），每個(gè)程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說(shuō)明（如果指定存儲(chǔ)結(jié)構(gòu)請(qǐng)寫(xiě)出該存儲(chǔ)結(jié)構(gòu)的定義）；</p><p><b>　　詳細(xì)設(shè)計(jì)</b></p><p>　　各個(gè)算法

25、實(shí)現(xiàn)的源程序，對(duì)每個(gè)題目要有相應(yīng)的源程序（可以是一組源程序，每個(gè)功能模塊采用不同的函數(shù)實(shí)現(xiàn)）。源程序要按照寫(xiě)程序的規(guī)則來(lái)編寫(xiě)。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量、重點(diǎn)功能部分要加上清晰的程序注釋；</p><p><b>　　調(diào)試分析</b></p><p>　　測(cè)試數(shù)據(jù)，測(cè)試輸出的結(jié)果，時(shí)間復(fù)雜度分析，和每個(gè)模塊設(shè)計(jì)和調(diào)試時(shí)存在問(wèn)題的思考（問(wèn)題是哪些？問(wèn)題如何解決？），

26、算法的改進(jìn)設(shè)想；</p><p><b>　　總結(jié)： </b></p><p>　　總結(jié)可以包括 : 設(shè)計(jì)過(guò)程的收獲、遇到問(wèn)題及解決問(wèn)題過(guò)程的思考、程序調(diào)試能力的思考、對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程的思考、在設(shè)計(jì)過(guò)程中對(duì)《數(shù)據(jù)結(jié)構(gòu)》課程的認(rèn)識(shí)等內(nèi)容。</p><p>　?。?）考核成績(jī)?cè)u(píng)定標(biāo)準(zhǔn)：</p><p>　　本課程設(shè)計(jì)的評(píng)價(jià)

27、由三部分組成，包括程序演示（50%），課程設(shè)計(jì)報(bào)告（30%），回答教師提問(wèn)（20%）。</p><p><b>　　1．程序演示：</b></p><p>　　優(yōu)功能完善，全部測(cè)試正確，并且能夠?qū)植窟M(jìn)行完善。</p><p>　　良功能完善，但測(cè)試欠缺。</p><p>　　中功能基本完善，但程序尚有部分錯(cuò)

28、誤。</p><p>　　及格完成內(nèi)存中赫夫曼編碼/譯碼，但不涉及文件操作。</p><p>　　不及格功能不完善，且程序錯(cuò)誤較多，無(wú)法運(yùn)行。</p><p><b>　　2．課程設(shè)計(jì)報(bào)告：</b></p><p>　　優(yōu)包括設(shè)計(jì)內(nèi)容，設(shè)計(jì)思想，已經(jīng)完成的任務(wù)及達(dá)到的目標(biāo)，設(shè)計(jì)思路清晰、書(shū)寫(xiě)條理清楚，源程序結(jié)構(gòu)合

29、理、清晰，注釋說(shuō)明完整，有對(duì)本次課程設(shè)計(jì)的心得體會(huì)。</p><p>　　良包括設(shè)計(jì)內(nèi)容，設(shè)計(jì)思想，已經(jīng)完成的任務(wù)及達(dá)到的目標(biāo)，設(shè)計(jì)思路基本清晰、書(shū)寫(xiě)條理基本清楚，源程序結(jié)構(gòu)合理、清晰，注釋說(shuō)明基本完整，有對(duì)本次課程設(shè)計(jì)的心得體會(huì)。</p><p>　　中課程設(shè)計(jì)報(bào)告內(nèi)容基本完整，思路較清晰，書(shū)寫(xiě)基本清楚，源程序結(jié)構(gòu)尚可，有注釋說(shuō)明但不完整。</p><p>

30、;　　及格課程設(shè)計(jì)報(bào)告內(nèi)容基本完整，思路較差，書(shū)寫(xiě)尚清楚。</p><p>　　不及格課程設(shè)計(jì)報(bào)告內(nèi)容不完整，書(shū)寫(xiě)沒(méi)有條理。</p><p><b>　　3．回答教師提問(wèn)：</b></p><p>　　優(yōu)能回答教師提出的所有問(wèn)題，并完全正確，思路清晰</p><p>　　良基本能回答教師提出的所有問(wèn)題，有些小

31、錯(cuò)誤</p><p>　　中基本能回答教師提出的問(wèn)題，少數(shù)問(wèn)題回答錯(cuò)誤或不清楚</p><p>　　及格能回答教師提出的問(wèn)題，但較多問(wèn)題回答錯(cuò)誤或不能回答</p><p>　　不及格基本不能回答教師提出的問(wèn)題</p><p><b>　　概要設(shè)計(jì)</b></p><p>　　問(wèn)題分析哈夫曼

32、樹(shù)的定義</p><p>　　1.哈夫曼樹(shù)節(jié)點(diǎn)的數(shù)據(jù)類型定義為：</p><p>　　typedef struct{ //赫夫曼樹(shù)的結(jié)構(gòu)體</p><p><b>　　char ch;</b></p><p>　　int weight; //權(quán)值</p><

33、;p>　　int parent,lchild,rchild;</p><p>　　}htnode,*hfmtree;</p><p>　　2）所實(shí)現(xiàn)的功能函數(shù)如下</p><p>　　1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼樹(shù)，處理InputHuffman(Huffman Hfm

34、)函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建立2叉樹(shù)。此函數(shù)塊調(diào)用了Select（）函數(shù)。</p><p>　　2、void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函數(shù)，選出HT樹(shù)到a為止，權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn)</p><p>　　2、 int main()</p><p>

35、;　　主函數(shù)： 利用已建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件hfmtree.txt中讀入）</p><p>　　對(duì)文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.txt中。如果正文中沒(méi)有要編碼的字符，則鍵盤(pán)讀入并存儲(chǔ)到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲(chǔ)到CodeFile中。</p><p>　　3、Encoding </p&

36、gt;<p>　　編碼功能：對(duì)輸入字符進(jìn)行編碼</p><p>　　4、Decoding</p><p>　　譯碼功能： 利用已建好的哈夫曼樹(shù)將文件codefile.txt中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat 中。</p><p>　　Print() 打印功能函數(shù)：輸出哈夫曼樹(shù)，字符，權(quán)值，以及它對(duì)應(yīng)的編碼。</p>&

37、lt;p>　　5.主函數(shù)的簡(jiǎn)要說(shuō)明，主函數(shù)主要設(shè)計(jì)的是一個(gè)分支語(yǔ)句，讓用戶挑選所實(shí)現(xiàn)的功能。</p><p>　　使用鏈樹(shù)存儲(chǔ)，然后分別調(diào)用統(tǒng)計(jì)頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來(lái)實(shí)現(xiàn)功能。</p><p>　　系統(tǒng)結(jié)構(gòu)圖（功能模塊圖）</p><p><b>　　程序說(shuō)明</b></p><p&g

38、t;　　.哈夫曼編碼/譯碼器源代碼</p><p>　　#include<iostream.h></p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#include<string.h></p>&l

39、t;p>　　#include<fstream.h></p><p>　　typedef struct{ //赫夫曼樹(shù)的結(jié)構(gòu)體</p><p><b>　　char ch;</b></p><p>　　int weight; //權(quán)值</p><p>　　int

40、parent,lchild,rchild;</p><p>　　}htnode,*hfmtree;</p><p>　　typedef char **hfmcode;</p><p>　　void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函數(shù)，選出HT樹(shù)到a為止，權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn)

41、</p><p><b>　　{</b></p><p>　　int i,j,x,y;</p><p>　　for(j=1;j<=a;++j){</p><p>　　if(HT[j].parent==0){</p><p><b>　　x=j;</b></p>

42、;<p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=j+1;i<=a;++i){</p><p>　　if(HT[i].weight<HT[x].w

43、eight&&HT[i].parent==0){</p><p>　　x=i; //選出最小的節(jié)點(diǎn)</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(j=1;j<=a;++j){<

44、;/p><p>　　if(HT[j].parent==0&&x!=j)</p><p><b>　　{</b></p><p><b>　　y=j;</b></p><p><b>　　break;</b></p><p><b>

45、　　}</b></p><p><b>　　}</b></p><p>　　for(i=j+1;i<=a;++i)</p><p><b>　　{</b></p><p>　　if(HT[i].weight<HT[y].weight&&HT[i].parent

46、==0&&x!=i)</p><p><b>　　{</b></p><p>　　y=i; //選出次小的節(jié)點(diǎn)</p><p><b>　　}</b></p><p><b>　　}</b></p><p&g

47、t;<b>　　if(x>y){</b></p><p><b>　　*p1=y;</b></p><p><b>　　*p2=x;</b></p><p><b>　　}</b></p><p><b>　　else</b>&

48、lt;/p><p><b>　　{</b></p><p><b>　　*p1=x;</b></p><p><b>　　*p2=y;</b></p><p><b>　　}</b></p><p><b>　　}</b

49、></p><p>　　void hfmcoding(hfmtree &HT,hfmcode &HC,int n) //構(gòu)建赫夫曼樹(shù)HT，并求出n個(gè)字符的赫夫曼編碼HC</p><p><b>　　{</b></p><p>　　int i,start,c,f,m,w;</p><p>　　int

50、p1,p2;</p><p>　　char *cd,z;</p><p><b>　　if(n<=1){</b></p><p><b>　　return;</b></p><p><b>　　}</b></p><p><b>　　m=

51、2*n-1;</b></p><p>　　HT=(hfmtree)malloc((m+1)*sizeof(htnode));</p><p>　　for(i=1;i<=n;++i) //初始化n個(gè)葉子結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　printf(&

52、quot;請(qǐng)輸入第%d字符信息和權(quán)值：",i);</p><p>　　scanf("%c%d",&z,&w);</p><p>　　while(getchar()!='\n')</p><p><b>　　{</b></p><p><b>　　co

53、ntinue;</b></p><p><b>　　}</b></p><p>　　HT[i].ch=z;</p><p>　　HT[i].weight=w;</p><p>　　HT[i].parent=0;</p><p>　　HT[i].lchild=0;</p>

54、<p>　　HT[i].rchild=0;</p><p><b>　　}</b></p><p>　　for(;i<=m;++i) //初始化其余的結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　HT[i].ch='0';</p

55、><p>　　HT[i].weight=0;</p><p>　　HT[i].parent=0;</p><p>　　HT[i].lchild=0;</p><p>　　HT[i].rchild=0;</p><p><b>　　}</b></p><p>　　for(i=n+

56、1;i<=m;++i) //建立赫夫曼樹(shù)</p><p><b>　　{</b></p><p>　　Select(HT,i-1,&p1,&p2);</p><p>　　HT[p1].parent=i;HT[p2].parent=i;</p><p>　　HT[i].lchild=p1

57、;HT[i].rchild=p2;</p><p>　　HT[i].weight=HT[p1].weight+HT[p2].weight;</p><p><b>　　}</b></p><p>　　HC=(hfmcode)malloc((n+1)*sizeof(char *));</p><p>　　cd=(char

58、*)malloc(n*sizeof(char));</p><p>　　cd[n-1]='\0';</p><p>　　for(i=1;i<=n;++i) //給n個(gè)字符編碼</p><p><b>　　{</b></p><p>　　start=n-1;</p>

59、;<p>　　for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)</p><p><b>　　{</b></p><p>　　if(HT[f].lchild==c)</p><p><b>　　{</b></p><p>　　cd[--sta

60、rt]='0';</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　cd[--start]='1';</p><p><

61、b>　　}</b></p><p><b>　　}</b></p><p>　　HC[i]=(char*)malloc((n-start)*sizeof(char));</p><p>　　strcpy(HC[i],&cd[start]);</p><p><b>　　}</b&

62、gt;</p><p><b>　　free(cd);</b></p><p><b>　　}</b></p><p>　　int main(){</p><p>　　char code[100],h[100],hl[100];</p><p>　　int n,i,j,k,l

63、;</p><p>　　ifstream input_file; //文件輸入輸出流</p><p>　　ofstream output_file;</p><p>　　char choice,str[100];</p><p>　　hfmtree HT;</p><p>　　hfmcode HC;</p&

64、gt;<p>　　cout<<"\n";</p><p>　　cout<<" "<<"計(jì)算機(jī)（3）班"<<" "<<"Q07620307"<<" "<<"XX

65、X\n";</p><p>　　while(choice!='Q'&&choice!='q') //當(dāng)choice的值不為q且不為Q時(shí)循環(huán)</p><p><b>　　{</b></p><p>　　cout<<" &quo

66、t;<<"*************************赫夫曼編碼/譯碼器*************************\n";</p><p>　　cout<<" "<<"I.Init"<<" "<<"E.Encodin

67、g"<<" "<<"D.Decoding"<<" "<<"Q.Exit\n";</p><p>　　cout<<"請(qǐng)輸入您要操作的步驟：";</p><p>　　cin>>choic

68、e;</p><p>　　if(choice=='I'||choice=='i') //初始化赫夫曼樹(shù)</p><p><b>　　{</b></p><p>　　cout<<"請(qǐng)輸入字符個(gè)數(shù)：";</p><p><b>

69、;　　cin>>n;</b></p><p>　　hfmcoding(HT,HC,n);</p><p>　　for(i=1;i<=n;++i)</p><p><b>　　{</b></p><p>　　cout<<HT[i].ch<<":"&l

70、t;<HC[i]<<endl;</p><p><b>　　}</b></p><p>　　output_file.open("hfmTree.txt");</p><p>　　if(!output_file){</p><p>　　cout<<"can'

71、;t oen file!"<<endl;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></p>

72、;<p>　　output_file<<"("<<HT[i].ch<<HC[i]<<")";</p><p><b>　　}</b></p><p>　　output_file.close();</p><p>　　cout<<&q

73、uot;赫夫曼樹(shù)已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree.txt文件中!"<<endl;</p><p><b>　　}</b></p><p>　　else if(choice=='E'||choice=='e') //進(jìn)行編碼，并將字符放入ToBeTran.txt，碼值放入CodeFile.

74、txt中</p><p><b>　　{</b></p><p>　　printf("請(qǐng)輸入字符：");</p><p>　　gets(str);</p><p>　　output_file.open("ToBeTran.txt");</p><p>　　i

75、f(!output_file)</p><p><b>　　{</b></p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p><p><b>　　

76、}</b></p><p>　　output_file<<str<<endl;</p><p>　　output_file.close();</p><p>　　output_file.open("CodeFile.txt");</p><p>　　if(!output_file){&l

77、t;/p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　for(i=0;i<strlen(str);i

78、++){</p><p>　　for(j=0;j<=n;++j)</p><p><b>　　{</b></p><p>　　if(HT[j].ch==str[i])</p><p><b>　　{</b></p><p>　　output_file<<HC

79、[j];</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　output_file.clos

80、e();</p><p>　　cout<<"\n";</p><p>　　cout<<"編碼完畢，并且已經(jīng)存入CodeFile.txt文件！\n";</p><p>　　input_file.open("CodeFile.txt"); //從CodeFile.txt中

81、讀入編碼，輸出在終端</p><p>　　if(!input_file)</p><p><b>　　{</b></p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b>

82、;</p><p><b>　　}</b></p><p>　　input_file>>code;</p><p>　　cout<<"編碼碼值為："<<code<<endl;</p><p>　　input_file.close();</p>

83、<p><b>　　}</b></p><p>　　else if(choice=='D'||choice=='d') //讀入CodeFile.txt中的編碼進(jìn)行譯碼，將譯出來(lái)的字符放入Textfile.txt中</p><p><b>　　{</b></p><p>

84、;　　input_file.open("CodeFile.txt");</p><p>　　if(!input_file){</p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p

85、><p><b>　　}</b></p><p>　　input_file>>h;</p><p>　　input_file.close();</p><p>　　output_file.open("Textfile.txt");</p><p>　　if(!outpu

86、t_file)</p><p><b>　　{</b></p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p><p><b>　　}</b&

87、gt;</p><p><b>　　k=0;</b></p><p>　　while(h[k]!='\0') //先用編碼中的前幾個(gè)和字符的編碼相比較，然后往后移</p><p><b>　　{</b></p><p>　　for(i=1;i<=n;i++)

88、{</p><p><b>　　l=k;</b></p><p>　　for(j=0;j<strlen(HC[i]);j++,l++){</p><p>　　hl[j]=h[l];</p><p><b>　　}</b></p><p>　　hl[j]='\0&

89、#39;;</p><p>　　if(strcmp(HC[i],hl)==0)</p><p><b>　　{</b></p><p>　　output_file<<HT[i].ch;</p><p>　　k=k+strlen(HC[i]);</p><p><b>　　br

90、eak;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　output_file.close();</p><p>　　input_file.

91、open("Textfile.txt");</p><p>　　if(!input_file){</p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p><p>

92、;<b>　　}</b></p><p>　　input_file>>h; </p><p>　　cout<<h<<endl;</p><p>　　input_file.close();</p><p>　　cout<<"譯碼結(jié)束，字符已經(jīng)存入Textfile.t

93、xt文件中！"<<endl;</p><p><b>　　}</b></p><p>　　else if(choice=='Q'||choice=='q') //退出程序</p><p><b>　　{ </b></p><p&

94、gt;<b>　　exit(0);</b></p><p><b>　　}</b></p><p>　　else //如果選了選項(xiàng)之外的就讓用戶重新選擇</p><p><b>　　{</b></p><p>　　cout<<"

95、您沒(méi)有輸入正確的步驟，請(qǐng)重新輸入！"<<endl;</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　return 0;</b></p&

96、gt;<p><b>　　}</b></p><p><b>　　調(diào)試分析</b></p><p><b>　　編碼</b></p><p><b>　　、譯碼</b></p><p><b>　　、退出</b><

97、/p><p><b>　　實(shí)驗(yàn)心得與體會(huì)</b></p><p>　　在我自己課程設(shè)計(jì)中，就在編寫(xiě)好源代碼后的調(diào)試中出現(xiàn)了不少的錯(cuò)誤，遇到了很多麻煩及困難，我的調(diào)試及其中的錯(cuò)誤和我最終找出錯(cuò)誤，修改為正確的能夠執(zhí)行的程序中，通過(guò)分析，我學(xué)到了：</p><p>　　在定義頭文件時(shí)可多不可少，即我們可多寫(xiě)些頭文件，肯定不會(huì)出錯(cuò)，但是若沒(méi)有定義所引用的

98、相關(guān)頭文件，必定調(diào)試不通過(guò)；</p><p>　　在執(zhí)行譯碼操作時(shí)，不知什么原因，總是不能把要編譯的二進(jìn)制數(shù)與編譯成的字符用連接號(hào)連接起來(lái)，而是按順序直接放在一起，視覺(jué)效果不是很好。還有就是，很遺憾的是，我們的哈夫曼編碼/譯碼器沒(méi)有像老師要求的那樣完成編一個(gè)文件的功能，這是我們?cè)O(shè)計(jì)的失敗之處。</p><p>　　通過(guò)本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，我學(xué)習(xí)了很多在上課沒(méi)懂的知識(shí)，并對(duì)求哈夫曼樹(shù)及哈

99、夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識(shí)，真正學(xué)會(huì)一種算法了。當(dāng)求解一個(gè)算法時(shí),不是拿到問(wèn)題就不加思索地做，而是首先要先對(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ù)，對(duì)文件的操作也很生疏。在