

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、<p> 計(jì)算機(jī)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)</p><p><b> 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p> 題 目: 哈夫曼樹(shù)的應(yīng)用</p><p> 班 級(jí): 計(jì)科10102班 </p><p> 完成日期:2012年1月1日</p>
2、<p> 《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)</p><p><b> 目 錄</b></p><p><b> 前言</b></p><p><b> 摘要</b></p><p> 《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)任務(wù)書</p><p&g
3、t;<b> 二、實(shí)驗(yàn)?zāi)康?lt;/b></p><p> 三、題目--赫夫曼樹(shù)的應(yīng)用</p><p><b> 問(wèn)題描述</b></p><p><b> 基本要求</b></p><p><b> 測(cè)試要求</b></p><p
4、><b> 實(shí)現(xiàn)提示</b></p><p> 需求分析--具體要求</p><p><b> 概要設(shè)計(jì)</b></p><p><b> 程序說(shuō)明</b></p><p><b> 調(diào)試分析</b></p><p>
5、;<b> 實(shí)驗(yàn)心得與體會(huì)</b></p><p><b> 九. 參考文獻(xiàn)</b></p><p><b> 前言</b></p><p><b> 摘要</b></p><p> 隨著計(jì)算機(jī)的普遍應(yīng)用與日益發(fā)展,其應(yīng)用早已不局限于簡(jiǎn)單的數(shù)值
6、運(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)。</p><p> 數(shù)據(jù)結(jié)構(gòu)是在整個(gè)計(jì)算機(jī)科
7、學(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é)構(gòu),闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系,討論其在計(jì)算機(jī)中的存儲(chǔ)表示
8、,以及在其上進(jìn)行各種運(yùn)算時(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)用能力
9、和專業(yè)素質(zhì)的提高。</p><p> 《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)任務(wù)書</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í)間和空間限制的有效算法。<
10、;/p><p> 本課程設(shè)計(jì)要求同學(xué)獨(dú)立完成一個(gè)較為完整的應(yīng)用需求分析。并在設(shè)計(jì)和編寫具有一定規(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&g
11、t; 數(shù)據(jù)結(jié)構(gòu)作為一門學(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)
12、今信息時(shí)代,信息技術(shù)己成為當(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ī)軟件和
13、計(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ì)的提高。通過(guò)此次課程設(shè)計(jì)主要達(dá)到以下目的:</p><p> 了解并掌
14、握數(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)題的能力;</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>
15、;<p> 三、題目--赫夫曼樹(shù)的應(yīng)用</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ā)站編寫一個(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>&
17、lt;p> (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>
18、 以下為選做:</b></p><p> (4) P:印代碼文件(Print)。將文件CodeFile以緊湊格式顯示在終端上,每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin中。</p><p> (5) T:印赫夫曼樹(shù)(Tree printing)。將已在內(nèi)存中的赫夫曼樹(shù)以直觀的方式(比如樹(shù))顯示在終端上,同時(shí)將此字符形式的赫夫曼樹(shù)寫入文件TreePr
19、int 中。</p><p><b> 測(cè)試要求</b></p><p> 用下表給出的字符集和權(quán)值的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立赫夫曼樹(shù),并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼: </p><p> “how are you ni shi na li de ren ”。</p><p><b> 實(shí)現(xiàn)提示</b>
20、;</p><p> (1) 編碼結(jié)果以文本方式存儲(chǔ)在文件Codefile中。</p><p> (2) 用戶界面可以設(shè)計(jì)為“菜單”方式:顯示上述功能符號(hào),再加上“Q”,表示退出運(yùn)行Quit。請(qǐng)用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單,直至某次用戶選擇了“Q”為止。</p><p> (3) 在程序的一次執(zhí)行過(guò)程中,第一次執(zhí)行I,D或C命令之后,赫
21、夫曼樹(shù)已經(jīng)在內(nèi)存了,不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令,因?yàn)槲募fmTree可能早已建好。</p><p><b> 四、具體要求:</b></p><p> 課程設(shè)計(jì)成果的內(nèi)容必須由以下四個(gè)部分組成,缺一不可。</p><p> (1) 上交源程序:學(xué)生按照實(shí)驗(yàn)題目的具體要求所開(kāi)發(fā)的所有源程序(應(yīng)該放到一個(gè)文件夾中);</p
22、><p> (2) 上交程序的說(shuō)明文件:(保存在.txt中)在說(shuō)明文檔中應(yīng)該寫明上交程序所在的目錄,上交程序的主程序文件名,如果需要安裝,要有程序的安裝使用說(shuō)明;</p><p> (3) 設(shè)計(jì)報(bào)告:(保存在word 文檔中,文件名要求: 按照“姓名_學(xué)號(hào)_設(shè)計(jì)題目”起名,如文件名為“ 張三_XXX_赫夫曼編碼 ”.doc。打印稿用A4紙)。</p><p><
23、;b> 其中包括:</b></p><p><b> 題目;</b></p><p><b> 實(shí)驗(yàn)?zāi)康模?lt;/b></p><p> 需求分析:在該部分中敘述實(shí)現(xiàn)的功能要求;</p><p><b> 概要設(shè)計(jì):</b></p><
24、;p> 在此說(shuō)明每個(gè)部分的算法設(shè)計(jì)說(shuō)明(可以是描述算法的流程圖),每個(gè)程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說(shuō)明(如果指定存儲(chǔ)結(jié)構(gòu)請(qǐng)寫出該存儲(chǔ)結(jié)構(gòu)的定義);</p><p><b> 詳細(xì)設(shè)計(jì)</b></p><p> 各個(gè)算法實(shí)現(xiàn)的源程序,對(duì)每個(gè)題目要有相應(yīng)的源程序(可以是一組源程序,每個(gè)功能模塊采用不同的函數(shù)實(shí)現(xiàn))。源程序要按照寫程序的規(guī)則來(lái)編寫。要結(jié)構(gòu)清晰,重點(diǎn)函
25、數(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)題如何解決?),算法的改進(jìn)設(shè)想;</p><p><b> 總結(jié): </b></p><p&
26、gt; 總結(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à)由三部分組成,包括程序演示(50%),課程設(shè)計(jì)報(bào)告(30%),回答教師提問(wèn)(20%)。</p><p><b>
27、; 1.程序演示:</b></p><p> 優(yōu)功能完善,全部測(cè)試正確,并且能夠?qū)植窟M(jìn)行完善。</p><p> 良功能完善,但測(cè)試欠缺。</p><p> 中功能基本完善,但程序尚有部分錯(cuò)誤。</p><p> 及格 完成內(nèi)存中赫夫曼編碼/譯碼,但不涉及文件操作。</p><
28、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ì)思路清晰、書寫 條理清楚,源程序結(jié)構(gòu)合理、清晰,注釋說(shuō)明完整,有對(duì)本次課程設(shè)計(jì)的心得體會(huì)。</p><p> 良包括設(shè)計(jì)內(nèi)容,設(shè)計(jì)思想
29、,已經(jīng)完成的任務(wù)及達(dá)到的目標(biāo),設(shè)計(jì)思路基本清晰、書寫條理基本清楚,源程序結(jié)構(gòu)合理、清晰,注釋說(shuō)明基本完整,有對(duì)本次課程設(shè)計(jì)的心得體會(huì)。</p><p> 中課程設(shè)計(jì)報(bào)告內(nèi)容基本完整,思路較清晰,書寫基本清楚,源程序結(jié)構(gòu)尚可,有注釋說(shuō)明但不完整。</p><p> 及格課程設(shè)計(jì)報(bào)告內(nèi)容基本完整,思路較差,書寫尚清楚。</p><p> 不及格課程設(shè)計(jì)報(bào)告
30、內(nèi)容不完整,書寫沒(méi)有條理。</p><p><b> 3.回答教師提問(wèn):</b></p><p> 優(yōu)能回答教師提出的所有問(wèn)題,并完全正確,思路清晰</p><p> 良基本能回答教師提出的所有問(wèn)題,有些小錯(cuò)誤</p><p> 中基本能回答教師提出的問(wèn)題,少數(shù)問(wèn)題回答錯(cuò)誤或不清楚</p>
31、<p> 及格 能回答教師提出的問(wèn)題,但較多問(wèn)題回答錯(cuò)誤或不能回答</p><p> 不及格基本不能回答教師提出的問(wèn)題</p><p><b> 五、概要設(shè)計(jì)</b></p><p><b> 1 .設(shè)計(jì)思想</b></p><p> 赫夫曼樹(shù)用鄰接矩陣作為存儲(chǔ)結(jié)
32、構(gòu),借助靜態(tài)鏈表來(lái)實(shí)現(xiàn)遍歷。</p><p><b> 2. 函數(shù)間的關(guān)系</b></p><p> 函數(shù)間的關(guān)系如圖3.1所示:</p><p> 圖3.1 函數(shù)間的關(guān)系</p><p> 3 .數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)</p><p> 赫夫曼編\譯碼器的主要功能是先建立赫夫曼樹(shù),然后利用
33、建好的赫夫曼樹(shù)生成赫夫曼編碼后進(jìn)行譯碼 。</p><p> 在數(shù)據(jù)通信中,經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0、1組成的二進(jìn)制串,稱之為編碼。構(gòu)造一棵赫夫曼樹(shù),規(guī)定赫夫曼樹(shù)中的左分之代表0,右分支代表1,則從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)所經(jīng)過(guò)的路徑分支組成的0和1的序列便為該節(jié)點(diǎn)對(duì)應(yīng)字符的編碼,稱之為赫夫曼編碼。</p><p> 最簡(jiǎn)單的二進(jìn)制編碼方式是等長(zhǎng)編碼。若采用不等長(zhǎng)編碼,讓出
34、現(xiàn)頻率高的字符具有較短的編碼,讓出現(xiàn)頻率低的字符具有較長(zhǎng)的編碼,這樣可能縮短傳送電文的總長(zhǎng)度。赫夫曼樹(shù)課用于構(gòu)造使電文的編碼總長(zhǎng)最短的編碼方案。</p><p> 其主要流程圖如圖3.2所示。</p><p> 圖3.2 赫夫曼樹(shù)編\譯碼器流程圖</p><p> 5.問(wèn)題分析哈夫曼樹(shù)的定義</p><p> 1.哈夫曼樹(shù)節(jié)點(diǎn)的數(shù)據(jù)類
35、型定義為:</p><p> typedef struct{ //赫夫曼樹(shù)的結(jié)構(gòu)體</p><p><b> char ch;</b></p><p> int weight; //權(quán)值</p><p> int parent,lchild,rchild;</p
36、><p> }htnode,*hfmtree;</p><p> 6.所實(shí)現(xiàn)的功能函數(shù)如下</p><p> 1.void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼樹(shù),處理InputHuffman(Huffman Hfm)函數(shù)得到的數(shù)據(jù),按照哈夫曼規(guī)則建立2叉樹(shù)。此函數(shù)塊調(diào)用了Select()函數(shù)
37、。</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> 3.int main()</p><p> 主函數(shù): 利用已建好的哈夫曼樹(shù)(如不在內(nèi)存,則從文件hfmtree.txt
38、中讀入)</p><p> 對(duì)文件中的正文進(jìn)行編碼,然后將結(jié)果存入文件codefile.txt中。如果正文中沒(méi)有要編碼的字符,則鍵盤讀入并存儲(chǔ)到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容,將編碼好的哈夫曼編碼存儲(chǔ)到CodeFile中。</p><p> 4.Encoding </p><p> 編碼功能:對(duì)輸入字符進(jìn)行編碼</p>
39、<p> 5.Decoding</p><p> 譯碼功能: 利用已建好的哈夫曼樹(shù)將文件codefile.txt中的代碼進(jìn)行譯碼,結(jié)果存入文件textfile.dat 中。</p><p> Print() 打印功能函數(shù):輸出哈夫曼樹(shù),字符,權(quán)值,以及它對(duì)應(yīng)的編碼。</p><p> 6.主函數(shù)的簡(jiǎn)要說(shuō)明,主函數(shù)主要設(shè)計(jì)的是一個(gè)分支語(yǔ)句,讓用戶
40、挑選所實(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><b> 7. </b></p><p> 1)哈夫曼系統(tǒng),函數(shù)間的關(guān)系如圖所示:</p><p> 2)系統(tǒng)結(jié)構(gòu)圖(功能模塊圖)</p><
41、p><b> 六、程序說(shuō)明</b></p><p> .哈夫曼編碼/譯碼器源代碼</p><p> #include<iostream.h></p><p> #include<stdio.h></p><p> #include<stdlib.h></p>
42、<p> #include<string.h></p><p> #include<fstream.h></p><p> typedef struct{ //赫夫曼樹(shù)的結(jié)構(gòu)體</p><p><b> char ch;</b></p><p> int w
43、eight; //權(quán)值</p><p> int parent,lchild,rchild;</p><p> }htnode,*hfmtree;</p><p> typedef char **hfmcode;</p><p> void Select(hfmtree &HT,int a,int *
44、p1,int *p2) //Select函數(shù),選出HT樹(shù)到a為止,權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn)</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){<
45、/p><p><b> x=j;</b></p><p><b> break;</b></p><p><b> }</b></p><p><b> }</b></p><p> for(i=j+1;i<=a;++i
46、){</p><p> if(HT[i].weight<HT[x].weight&&HT[i].parent==0){</p><p> x=i; //選出最小的節(jié)點(diǎn)</p><p><b> }</b></p><p><b> }</b&
47、gt;</p><p> for(j=1;j<=a;++j){</p><p> if(HT[j].parent==0&&x!=j)</p><p><b> {</b></p><p><b> y=j;</b></p><p><b&
48、gt; break;</b></p><p><b> }</b></p><p><b> }</b></p><p> for(i=j+1;i<=a;++i)</p><p><b> {</b></p><p> if
49、(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i)</p><p><b> {</b></p><p> y=i; //選出次小的節(jié)點(diǎn)</p><p><b> }</b></p>
50、<p><b> }</b></p><p><b> if(x>y){</b></p><p><b> *p1=y;</b></p><p><b> *p2=x;</b></p><p><b> }</b
51、></p><p><b> else</b></p><p><b> {</b></p><p><b> *p1=x;</b></p><p><b> *p2=y;</b></p><p><b>
52、 }</b></p><p><b> }</b></p><p> void hfmcoding(hfmtree &HT,hfmcode &HC,int n) //構(gòu)建赫夫曼樹(shù)HT,并求出n個(gè)字符的赫夫曼編碼HC</p><p><b> {</b></p><p&g
53、t; int i,start,c,f,m,w;</p><p> int p1,p2;</p><p> char *cd,z;</p><p><b> if(n<=1){</b></p><p><b> return;</b></p><p><b
54、> }</b></p><p><b> m=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>&l
55、t;b> {</b></p><p> printf("請(qǐng)輸入第%d字符信息和權(quán)值:",i);</p><p> scanf("%c%d",&z,&w);</p><p> while(getchar()!='\n')</p><p><b
56、> {</b></p><p><b> continue;</b></p><p><b> }</b></p><p> HT[i].ch=z;</p><p> HT[i].weight=w;</p><p> HT[i].parent=0
57、;</p><p> HT[i].lchild=0;</p><p> HT[i].rchild=0;</p><p><b> }</b></p><p> for(;i<=m;++i) //初始化其余的結(jié)點(diǎn)</p><p><b> {</b>
58、;</p><p> HT[i].ch='0';</p><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>&l
59、t;b> }</b></p><p> for(i=n+1;i<=m;++i) //建立赫夫曼樹(shù)</p><p><b> {</b></p><p> Select(HT,i-1,&p1,&p2);</p><p> HT[p1].parent=i;HT[
60、p2].parent=i;</p><p> HT[i].lchild=p1;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+
61、1)*sizeof(char *));</p><p> cd=(char *)malloc(n*sizeof(char));</p><p> cd[n-1]='\0';</p><p> for(i=1;i<=n;++i) //給n個(gè)字符編碼</p><p><b> {&
62、lt;/b></p><p> start=n-1;</p><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>&l
63、t;b> {</b></p><p> cd[--start]='0';</p><p><b> }</b></p><p><b> else</b></p><p><b> {</b></p><p>
64、 cd[--start]='1';</p><p><b> }</b></p><p><b> }</b></p><p> HC[i]=(char*)malloc((n-start)*sizeof(char));</p><p> strcpy(HC[i],&
65、cd[start]);</p><p><b> }</b></p><p><b> free(cd);</b></p><p><b> }</b></p><p> int main()</p><p><b> {</b
66、></p><p> char code[100],h[100],hl[100];</p><p> int n,i,j,k,l;</p><p> ifstream input_file; //文件輸入輸出流</p><p> ofstream output_file;</p><p> cha
67、r choice,str[100];</p><p> hfmtree HT;</p><p> hfmcode HC;</p><p> cout<<"===============================================================================\n";</
68、p><p> cout<<"\t數(shù)據(jù)結(jié)構(gòu)\t課程設(shè)計(jì)\t計(jì)科10102班 李偉 29號(hào) 朱林 27號(hào)\n";</p><p> cout<<"-------------------------------------------------------------------------------\n";</p&g
69、t;<p> while(1) </p><p><b> { </b></p><p> cout<<"\n\t\t";</p><p> cout<<"┏━━━━━━━━━━━━━━━━━━━━┓\n\t\t";</p>
70、;<p> cout<<"┃ 歡迎使用赫夫曼編碼解碼系統(tǒng) ┃\n\t\t";</p><p> cout<<"┡━━━━━━━━━━━━━━━━━━━━┩\n\t\t";</p><p> cout<<"│ i.初始化赫夫曼鏈表 │\n
71、\t\t";</p><p> cout<<"│ e.編 碼 │\n\t\t";</p><p> cout<<"│ d.譯 碼 │\n\t\t";</p><p> cout<&l
72、t;"│ q.退 出 │\n\t\t";</p><p> cout<<"└────────────────────┘\n\n";</p><p> cout<<"==================================================
73、=============================\n";</p><p> cout<<"請(qǐng)輸入您要操作的步驟:";</p><p> cin>>choice;</p><p> switch (choice)</p><p><b> {</b>&
74、lt;/p><p> case 'i': //初始化赫夫曼樹(shù)</p><p><b> {</b></p><p> cout<<"請(qǐng)輸入字符個(gè)數(shù):";</p><p><b> cin>>n;</b></p>&l
75、t;p> hfmcoding(HT,HC,n);</p><p> for(i=1;i<=n;++i)</p><p><b> {</b></p><p> cout<<HT[i].ch<<":"<<HC[i]<<endl;</p><
76、p><b> }</b></p><p> output_file.open("hfmTree.txt");</p><p> if(!output_file){</p><p> cout<<"can't oen file!"<<endl;</p>
77、;<p><b> return 1;</b></p><p><b> }</b></p><p> for(i=1;i<=n;i++)</p><p><b> {</b></p><p> output_file<<"(
78、"<<HT[i].ch<<HC[i]<<")";</p><p><b> }</b></p><p> output_file.close();</p><p> cout<<"赫夫曼樹(shù)已經(jīng)創(chuàng)建完畢,并且已經(jīng)放入hfmTree.txt文件中!&quo
79、t;<<endl;</p><p><b> break;</b></p><p><b> }</b></p><p> case 'e': //進(jìn)行編碼,并將字符放入ToBeTran.txt,碼值放入CodeFile.txt中</p><p>&l
80、t;b> {</b></p><p> printf("請(qǐng)輸入字符:");</p><p> gets(str);</p><p> output_file.open("ToBeTran.txt");</p><p> if(!output_file)</p>
81、<p><b> {</b></p><p> cout<<"can't oen file!"<<endl;</p><p><b> return 1;</b></p><p><b> }</b></p><
82、p> output_file<<str<<endl;</p><p> output_file.close();</p><p> output_file.open("CodeFile.txt");</p><p> if(!output_file){</p><p> cout&l
83、t;<"can't oen file!"<<endl;</p><p><b> return 1;</b></p><p><b> }</b></p><p> for(i=0;i<strlen(str);i++){</p><p>
84、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[j];</p><p>&l
85、t;b> break;</b></p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p> output_file.close();</p><p>
86、cout<<"\n";</p><p> cout<<"編碼完畢,并且已經(jīng)存入CodeFile.txt文件!\n";</p><p> input_file.open("CodeFile.txt"); //從CodeFile.txt中讀入編碼,輸出在終端</p><p
87、> if(!input_file)</p><p><b> {</b></p><p> cout<<"can't oen file!"<<endl;</p><p><b> return 1;</b></p><p><b
88、> }</b></p><p> input_file>>code;</p><p> cout<<"編碼碼值為:"<<code<<endl;</p><p> input_file.close();</p><p><b> break
89、;</b></p><p><b> }</b></p><p> case 'd': //讀入CodeFile.txt中的編碼進(jìn)行譯碼,將譯出來(lái)的字符放入Textfile.txt中</p><p><b> {</b></p><p> input_file
90、.open("CodeFile.txt");</p><p> if(!input_file){</p><p> cout<<"can't oen file!"<<endl;</p><p><b> return 1;</b></p><p&g
91、t;<b> }</b></p><p> input_file>>h;</p><p> input_file.close();</p><p> output_file.open("Textfile.txt");</p><p> if(!output_file)</p
92、><p><b> {</b></p><p> cout<<"can't oen file!"<<endl;</p><p><b> return 1;</b></p><p><b> }</b></p>
93、<p><b> k=0;</b></p><p> while(h[k]!='\0') //先用編碼中的前幾個(gè)和字符的編碼相比較,然后往后移</p><p><b> {</b></p><p> for(i=1;i<=n;i++){</p>
94、<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';</p&g
95、t;<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> break;</b>
96、;</p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p> output_file.close();</p><p> input_file.open("Te
97、xtfile.txt");</p><p> if(!input_file){</p><p> cout<<"can't oen file!"<<endl;</p><p><b> return 1;</b></p><p><b> }
98、</b></p><p> input_file>>h; </p><p> cout<<h<<endl;</p><p> input_file.close();</p><p> cout<<"譯碼結(jié)束,字符已經(jīng)存入Textfile.txt文件中!"&
99、lt;<endl;</p><p><b> break;</b></p><p><b> }</b></p><p><b> case 'q':</b></p><p><b> exit(0);</b></p&g
100、t;<p><b> default:</b></p><p> cout<<"您沒(méi)有輸入正確的步驟,請(qǐng)重新輸入!"<<endl;</p><p><b> }</b></p><p><b> }</b></p><
101、;p><b> return 0;</b></p><p><b> }</b></p><p><b> 七、調(diào)試分析</b></p><p> 1.進(jìn)入界面如下,根據(jù)需要輸入i,e,d,q執(zhí)行操作步驟。</p><p> 2.初始化赫夫曼鏈表,根據(jù)需要輸入各
102、字符信息及其權(quán)值,然后經(jīng)過(guò)程序?qū)⑵滢D(zhuǎn)化為赫夫曼編碼,結(jié)果如下。</p><p> 3.編碼操作:輸入所要編碼的字符,如”how are you ni shi na li de ren”,按回車之后,程序?qū)?zhí)行編碼操作并將編碼保存到CodeFile.txt文件中,然后將編碼碼值輸出在屏幕中。</p><p> 譯碼操作:輸入字母d,程序?qū)⒆x取CodeFile.txt中的編碼,然后進(jìn)行譯碼
103、操作,結(jié)果如下,并將譯碼后的字符保存在Textfile.txt文件中。</p><p> 6.退出:輸入字符q , 程序?qū)⑼顺?,結(jié)果如下。</p><p><b> 八、實(shí)驗(yàn)心得與體會(huì)</b></p><p> 在我自己課程設(shè)計(jì)中,就在編寫好源代碼后的調(diào)試中出現(xiàn)了不少的錯(cuò)誤,遇到了很多麻煩及困難,我的調(diào)試及其中的錯(cuò)誤和我最終找出錯(cuò)誤,修改
104、為正確的能夠執(zhí)行的程序中,通過(guò)分析,我學(xué)到了:</p><p> 在定義頭文件時(shí)可多不可少,即我們可多寫些頭文件,肯定不會(huì)出錯(cuò),但是若沒(méi)有定義所引用的相關(guān)頭文件,必定調(diào)試不通過(guò);</p><p> 在執(zhí)行譯碼操作時(shí),不知什么原因,總是不能把要編譯的二進(jìn)制數(shù)與編譯成的字符用連接號(hào)連接起來(lái),而是按順序直接放在一起,視覺(jué)效果不是很好。還有就是,很遺憾的是,我們的哈夫曼編碼/譯碼器沒(méi)有像老師要
105、求的那樣完成編一個(gè)文件的功能,這是我們?cè)O(shè)計(jì)的失敗之處。</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)題就不加思索地做,而是首先要先對(duì)它有個(gè)大概的了解,接著再詳細(xì)地分析每一步怎么做,無(wú)論自己以前是否有處理過(guò)相似的問(wèn)題,只要按照以上的步驟
106、,必定會(huì)順利地做出來(lái)。</p><p> 這次課程設(shè)計(jì),我在編輯中犯了不應(yīng)有的錯(cuò)誤,設(shè)計(jì)統(tǒng)計(jì)字符和合并時(shí)忘記應(yīng)該怎樣保存數(shù)據(jù),對(duì)文件的操作也很生疏。在不斷分析后明確并改正了錯(cuò)誤和疏漏,我的程序有了更高的質(zhì)量。</p><p><b> 九.參考文獻(xiàn)</b></p><p> [1]嚴(yán)蔚敏,吳偉民.《數(shù)據(jù)結(jié)構(gòu):C語(yǔ)言版》.北京:清華大學(xué)出版
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---哈夫曼樹(shù)的應(yīng)用
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--哈夫曼樹(shù)的應(yīng)用
- 哈夫曼樹(shù)_數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 哈夫曼樹(shù)_數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--- 哈夫曼樹(shù)的應(yīng)用
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---哈夫曼編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告----哈夫曼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----哈夫曼編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)哈夫曼編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--哈夫曼編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---哈夫曼編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)哈夫曼編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----赫夫曼樹(shù)
- 數(shù)據(jù)結(jié)構(gòu)-赫夫曼樹(shù)-課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)之哈夫曼編碼
- 哈夫曼編碼譯碼數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(赫夫曼樹(shù)的建立)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---哈夫曼編碼器
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---哈夫曼編碼器
- 哈夫曼編碼譯碼數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
評(píng)論
0/150
提交評(píng)論