哈弗曼編碼譯碼課程設(shè)計(jì).docVIP

武漢工程大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院綜合設(shè)計(jì)報(bào)告設(shè)計(jì)名稱(chēng)： 應(yīng)用軟件綜合設(shè)計(jì) 設(shè)計(jì)題目： 哈夫曼編碼/譯碼器 學(xué)生學(xué)號(hào)： 0805060119 專(zhuān)業(yè)班級(jí)： 軟件工程 學(xué)生姓名： 學(xué)生成績(jī)： 指導(dǎo)教師（職稱(chēng)）： 劉黎志（講師） 課題工作時(shí)間： 2010-6-21 至 2010-7-2 說(shuō)明：1、報(bào)告中的第一、二、三項(xiàng)由指導(dǎo)教師在綜合設(shè)計(jì)開(kāi)始前填寫(xiě)并發(fā)給每個(gè)學(xué)生；四、五兩項(xiàng)（中英文摘要）由學(xué)生在完成綜合設(shè)計(jì)后填寫(xiě)。2、學(xué)生成績(jī)由指導(dǎo)教師根據(jù)學(xué)生的設(shè)計(jì)情況給出各項(xiàng)分值及總評(píng)成績(jī)。3、指導(dǎo)教師評(píng)語(yǔ)一欄由指導(dǎo)教師就學(xué)生在整個(gè)設(shè)計(jì)期間的平時(shí)表現(xiàn)、設(shè)計(jì)完成情況、報(bào)告的質(zhì)量及答辯情況，給出客觀、全面的評(píng)價(jià)。4、所有學(xué)生必須參加綜合設(shè)計(jì)的答辯環(huán)節(jié)，凡不參加答辯者，其成績(jī)一律按不及格處理。答辯小組成員應(yīng)由2人及以上教師組成。5、報(bào)告正文字?jǐn)?shù)一般應(yīng)不少于5000字，也可由指導(dǎo)教師根據(jù)本門(mén)綜合設(shè)計(jì)的情況另行規(guī)定。6、平時(shí)表現(xiàn)成績(jī)低于6分的學(xué)生，其綜合設(shè)計(jì)成績(jī)按不及格處理。7、此表格式為武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院提供的基本格式（適用于學(xué)院各類(lèi)綜合設(shè)計(jì)），各教研室可根據(jù)本門(mén)綜合設(shè)計(jì)的特點(diǎn)及內(nèi)容做適當(dāng)?shù)恼{(diào)整，并上報(bào)學(xué)院批準(zhǔn)。成績(jī)?cè)u(píng)定表學(xué)生姓名： 學(xué)號(hào)： 班級(jí)： 類(lèi)別合計(jì)分值各項(xiàng)分值評(píng)分標(biāo)準(zhǔn)實(shí)際得分合計(jì)得分備注平時(shí)表現(xiàn)1010按時(shí)參加綜合設(shè)計(jì)，無(wú)曠課、遲到、早退、違反實(shí)驗(yàn)室紀(jì)律等情況。完成情況3020按設(shè)計(jì)任務(wù)書(shū)的要求完成了全部任務(wù)，能完整演示其設(shè)計(jì)內(nèi)容，符合要求。10能對(duì)其設(shè)計(jì)內(nèi)容進(jìn)行詳細(xì)、完整的介紹，并能就指導(dǎo)教師提出的問(wèn)題進(jìn)行正確的回答。報(bào)告質(zhì)量3510報(bào)告文字通順，內(nèi)容翔實(shí)，論述充分、完整，立論正確，結(jié)構(gòu)嚴(yán)謹(jǐn)合理；報(bào)告字?jǐn)?shù)符合相關(guān)要求，工整規(guī)范，整齊劃一。5課題背景介紹清楚，綜述分析充分。5設(shè)計(jì)方案合理、可行，論證嚴(yán)謹(jǐn)，邏輯性強(qiáng)，具有說(shuō)服力。5符號(hào)統(tǒng)一；圖表完備、符合規(guī)范要求。5能對(duì)整個(gè)設(shè)計(jì)過(guò)程進(jìn)行全面的總結(jié)，得出有價(jià)值的結(jié)論或結(jié)果。5參考文獻(xiàn)數(shù)量在3篇以上，格式符合要求，在正文中正確引用。答辯情況2510在規(guī)定時(shí)間內(nèi)能就所設(shè)計(jì)的內(nèi)容進(jìn)行闡述，言簡(jiǎn)意明，重點(diǎn)突出，論點(diǎn)正確，條理清晰。15在規(guī)定時(shí)間內(nèi)能準(zhǔn)確、完整、流利地回答教師所提出的問(wèn)題?？傇u(píng)成績(jī)： 分 補(bǔ)充說(shuō)明： 指導(dǎo)教師： （簽字）日 期： 年 月 日答辯記錄表學(xué)生姓名： 學(xué)號(hào)： 班級(jí)： 答辯地點(diǎn)： 答辯內(nèi)容記錄：答辯成績(jī)合計(jì)分值各項(xiàng)分值評(píng)分標(biāo)準(zhǔn)實(shí)際得分合計(jì)得分備注2510在規(guī)定時(shí)間內(nèi)能就所設(shè)計(jì)的內(nèi)容進(jìn)行闡述，言簡(jiǎn)意明，重點(diǎn)突出，論點(diǎn)正確，條理清晰。15在規(guī)定時(shí)間內(nèi)能準(zhǔn)確、完整、流利地回答教師所提出的問(wèn)題。答辯小組成員（簽字）： 年 月 日指導(dǎo)教師評(píng)語(yǔ)指導(dǎo)教師： （簽字）日 期： 年 月 日一、綜合設(shè)計(jì)目的、條件、任務(wù)和內(nèi)容要求：利用哈夫曼編碼進(jìn)行信息通訊可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫(xiě)一個(gè)哈夫曼碼的編譯碼系統(tǒng)。一個(gè)完整的哈夫曼碼的編譯碼系統(tǒng)系統(tǒng)應(yīng)具有以下功能：I: 初始化(Initialization)。從終端讀入字符集大小n，幾個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件hfmtree中。C: 編碼(Coding)。利用已建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件hfmtree中讀入），對(duì)文件tobetrans中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile中。D: 譯碼(Decoding)。利用已建好的哈夫曼樹(shù)將文件codefile中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile中。P: 打印代碼文件(Print)。將文件codefile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫(xiě)入文件codeprint中。T: 打印哈夫曼樹(shù)(Tree printing)。將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式（數(shù)或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件treeprint中。測(cè)試數(shù)據(jù)用下表中給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼數(shù)，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。字符-ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161通過(guò)本設(shè)計(jì)可以鞏固已經(jīng)學(xué)過(guò)的基礎(chǔ)課及專(zhuān)業(yè)課知識(shí)，開(kāi)闊學(xué)生的視野，鍛煉學(xué)生的自學(xué)能力及獨(dú)立動(dòng)手能力。 指導(dǎo)教師簽字： 劉黎志 2009 年 9 月 11 日二、進(jìn)度安排：2010-6-21：明確所選課題的具體要求，按要求閱讀相關(guān)的參考文獻(xiàn)及資料2009-6-22至2010-7-1：課題代碼實(shí)現(xiàn)、課程設(shè)計(jì)報(bào)告書(shū)寫(xiě)2010-7-2：課程設(shè)計(jì)答辯三、應(yīng)收集資料及主要參考文獻(xiàn)：1 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu) M.北京：清華大學(xué)出版,1999 2 陳一華.數(shù)據(jù)結(jié)構(gòu) M.西安：電子科技大學(xué)出版社,1998 3 譚浩強(qiáng).C語(yǔ)言程序設(shè)計(jì) M.北京：高等教育出版社,20024 曲建民,劉元紅 鄭陶然數(shù)據(jù)結(jié)構(gòu) M北京：清華大學(xué)出版社,20055 李春葆.數(shù)據(jù)結(jié)構(gòu)教程 M北京：清華大學(xué)出版社,20056 蔣立翔C+程序設(shè)計(jì)技能百練 M西安：中國(guó)鐵道出版社,2004四、綜合設(shè)計(jì)（課程設(shè)計(jì)）摘要（中文）：在計(jì)算機(jī)信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱(chēng)熵編碼法），用于數(shù)據(jù)的無(wú)損耗壓縮。它在很多領(lǐng)域有著廣泛的應(yīng)用，是一種帶權(quán)路徑長(zhǎng)度最短的樹(shù)，該文在哈夫曼提出的構(gòu)造最優(yōu)二叉樹(shù)的基礎(chǔ)上進(jìn)行一些改進(jìn)，并得出一種最簡(jiǎn)計(jì)算最短帶權(quán)路徑長(zhǎng)度的方法。你會(huì)發(fā)現(xiàn)一些數(shù)據(jù)經(jīng)常出現(xiàn)的頻率高，有些出現(xiàn)的頻率低。利用哈夫曼算法建立一棵哈夫曼樹(shù)(最優(yōu)二叉樹(shù))，同時(shí)將數(shù)據(jù)出現(xiàn)的頻率作為權(quán)值賦給哈夫曼樹(shù)中的結(jié)點(diǎn)。根據(jù)建立好的哈夫曼樹(shù)我們進(jìn)行編碼，從根結(jié)點(diǎn)出發(fā)在左子樹(shù)則標(biāo)為0，右則標(biāo)為1。直到到指定的葉子結(jié)點(diǎn)，然后將遍歷過(guò)程中標(biāo)記的0，1代碼存在一個(gè)數(shù)組中。以此實(shí)現(xiàn)將使用頻率高的字符的編碼盡可能的少，也就使得總的長(zhǎng)度減少。在哈夫曼編碼的基礎(chǔ)上進(jìn)行解碼，就可以還原壓縮的數(shù)據(jù)。哈夫曼樹(shù)是一種應(yīng)用廣泛的數(shù)據(jù)結(jié)構(gòu)。在文件壓縮中,根據(jù)各字符在文件中出現(xiàn)的頻率不同(有的字符根本沒(méi)出現(xiàn)),依照頻率高,則編碼長(zhǎng),頻率低則編碼短的原則對(duì)各字符重新進(jìn)行編碼,從而在總體上使文件長(zhǎng)度縮短,達(dá)到壓縮文件的目的。該設(shè)計(jì)是對(duì)輸入的一串電文字符實(shí)現(xiàn)哈夫曼編碼，再對(duì)哈夫曼編碼生成的代碼串進(jìn)行譯碼，輸出電文字符串。在該設(shè)計(jì)中把數(shù)據(jù)壓縮過(guò)程稱(chēng)為編碼，解壓縮的過(guò)程稱(chēng)為譯碼。此程序中建立了哈夫曼樹(shù)，并利用建好的哈夫曼樹(shù)對(duì)文件中的正文進(jìn)行編碼，對(duì)文件中的代碼進(jìn)行譯碼，顯示輸出等功能。五、綜合設(shè)計(jì)（課程設(shè)計(jì)）Abstract（英文）：In the computer information processing, Huffman coding is a consistent coding method (also known as entropy coding method) for lossless data compression. It has wide application in many fields, is a weighted length of the shortest path tree, this paper put forward in the Huffman binary tree structure based on the optimal number of improvements, and draw one of the most simple calculation of the shortest weighted path length method. You will find some of the data often high frequency, the frequency of some of the low. Huffman algorithm is used to establish a Huffman tree (the optimal binary tree), while data on the frequency as the weights assigned to nodes in Huffman tree. Huffman tree according to well-established that we encode, starting from the root node in the left subtree is marked as 0, the right is labeled 1. Up to the specified leaf node, then iterate the process of marking the existence of a 0,1 code array. In order to achieve high frequency of characters to use as less code, thus making the total length of the reduction. In the Huffman coding on the basis of decoding, you can restore the compressed data. Huffman tree is a widely used data structure. In the file compression, according to the characters in the file of the occurrence frequencies in different (some fundamental Mei Zi Fu there), high the encoder Zhang low frequency short while the principles of coding each Zifuzhongxin encoded in the aggregate to document length in the compressed document is intended to achieve. The design is a message character string input Huffman coding to achieve and then build on Huffman decoding code strings, the output message string. In the design of the data compression process is called encoding, unzip the process is called decoding. This procedure established a Huffman tree, and built the Huffman tree using the text file encoded in the code on the file decoding, display output function.武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 綜合設(shè)計(jì)報(bào)告目 錄摘 要 IIAbstract . II第一章 課題背景（或緒論、概述）. 11.1 哈夫曼背景介紹.11.2 哈夫曼設(shè)計(jì)目的. 21.3 哈夫曼樹(shù)的應(yīng)用.2第二章設(shè)計(jì)簡(jiǎn)介及設(shè)計(jì)方案論述 . 32.1 需求分析.32.2 概要設(shè)計(jì).32.3 相關(guān)函數(shù)介紹.4第三章詳細(xì)設(shè)計(jì). 53.1 哈夫曼樹(shù)核心算法. .53.2 程序流程圖.7第四章設(shè)計(jì)結(jié)果及分析.104.1 調(diào)試分析.104.2 結(jié)果展示.114.3 實(shí)驗(yàn)體會(huì).16總 結(jié) .17致 謝 .18參考文獻(xiàn) .19附錄 主要程序代碼 .20摘 要在計(jì)算機(jī)信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱(chēng)熵編碼法），用于數(shù)據(jù)的無(wú)損耗壓縮。它在很多領(lǐng)域有著廣泛的應(yīng)用，是一種帶權(quán)路徑長(zhǎng)度最短的樹(shù)，該文在哈夫曼提出的構(gòu)造最優(yōu)二叉樹(shù)的基礎(chǔ)上進(jìn)行一些改進(jìn)，并得出一種最簡(jiǎn)計(jì)算最短帶權(quán)路徑長(zhǎng)度的方法。你會(huì)發(fā)現(xiàn)一些數(shù)據(jù)經(jīng)常出現(xiàn)的頻率高，有些出現(xiàn)的頻率低。利用哈夫曼算法建立一棵哈夫曼樹(shù)(最優(yōu)二叉樹(shù))，同時(shí)將數(shù)據(jù)出現(xiàn)的頻率作為權(quán)值賦給哈夫曼樹(shù)中的結(jié)點(diǎn)。根據(jù)建立好的哈夫曼樹(shù)我們進(jìn)行編碼，從根結(jié)點(diǎn)出發(fā)在左子樹(shù)則標(biāo)為0，右則標(biāo)為1。直到到指定的葉子結(jié)點(diǎn)，然后將遍歷過(guò)程中標(biāo)記的0，1代碼存在一個(gè)數(shù)組中。以此實(shí)現(xiàn)將使用頻率高的字符的編碼盡可能的少，也就使得總的長(zhǎng)度減少。在哈夫曼編碼的基礎(chǔ)上進(jìn)行解碼，就可以還原壓縮的數(shù)據(jù)。哈夫曼樹(shù)是一種應(yīng)用廣泛的數(shù)據(jù)結(jié)構(gòu)。在文件壓縮中,根據(jù)各字符在文件中出現(xiàn)的頻率不同(有的字符根本沒(méi)出現(xiàn)),依照頻率高,則編碼長(zhǎng),頻率低則編碼短的原則對(duì)各字符重新進(jìn)行編碼,從而在總體上使文件長(zhǎng)度縮短,達(dá)到壓縮文件的目的。該設(shè)計(jì)是對(duì)輸入的一串電文字符實(shí)現(xiàn)哈夫曼編碼，再對(duì)哈夫曼編碼生成的代碼串進(jìn)行譯碼，輸出電文字符串。在該設(shè)計(jì)中把數(shù)據(jù)壓縮過(guò)程稱(chēng)為編碼，解壓縮的過(guò)程稱(chēng)為譯碼。此程序中建立了哈夫曼樹(shù)，并利用建好的哈夫曼樹(shù)對(duì)文件中的正文進(jìn)行編碼，對(duì)文件中的代碼進(jìn)行譯碼，顯示輸出等功能。關(guān)鍵詞：哈夫曼樹(shù)；哈夫曼編碼AbstractIn the computer information processing, Huffman coding is a consistent coding method (also known as entropy coding method) for lossless data compression. It has wide application in many fields, is a weighted length of the shortest path tree, this paper put forward in the Huffman binary tree structure based on the optimal number of improvements, and draw one of the most simple calculation of the shortest weighted path length method. You will find some of the data often high frequency, the frequency of some of the low. Huffman algorithm is used to establish a Huffman tree (the optimal binary tree), while data on the frequency as the weights assigned to nodes in Huffman tree. Huffman tree according to well-established that we encode, starting from the root node in the left subtree is marked as 0, the right is labeled 1. Up to the specified leaf node, then iterate the process of marking the existence of a 0,1 code array. In order to achieve high frequency of characters to use as less code, thus making the total length of the reduction. In the Huffman coding on the basis of decoding, you can restore the compressed data. Huffman tree is a widely used data structure. In the file compression, according to the characters in the file of the occurrence frequencies in different (some fundamental Mei Zi Fu there), high the encoder Zhang low frequency short while the principles of coding each Zifuzhongxin encoded in the aggregate to document length in the compressed document is intended to achieve. The design is a message character string input Huffman coding to achieve and then build on Huffman decoding code strings, the output message string. In the design of the data compression process is called encoding, unzip the process is called decoding. This procedure established a Huffman tree, and built the Huffman tree using the text file encoded in the code on the file decoding, display output function.Keywords: Huffman tree; Huffman coding- 34 -第一章 課題背景1.1哈夫曼背景介紹哈夫曼樹(shù)又稱(chēng)最優(yōu)二叉樹(shù)，是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)。所謂樹(shù)的帶權(quán)路徑長(zhǎng)度，就是樹(shù)中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長(zhǎng)度。樹(shù)的帶權(quán)路徑長(zhǎng)度記為WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N個(gè)權(quán)值Wi(i=1,2,.n)構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，相應(yīng)的葉結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)i(i=1,2,.n)?？梢宰C明哈夫曼樹(shù)的WPL是最小的。從哈夫曼樹(shù)根結(jié)點(diǎn)開(kāi)始，對(duì)左子樹(shù)分配代碼“0”，右子樹(shù)分配代碼“1”，一直到達(dá)葉子結(jié)點(diǎn)為止，然后將從樹(shù)根沿每條路徑到達(dá)葉子結(jié)點(diǎn)的代碼排列起來(lái)，便得到了哈夫曼編碼。因此，在文件中出現(xiàn)頻率高的符號(hào)，使用短的位序列，而那些很少出現(xiàn)的符號(hào)，則用較長(zhǎng)的位序列。1.1.1 基本術(shù)語(yǔ)路徑和路徑長(zhǎng)度:在一棵樹(shù)中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路，稱(chēng)為路徑。通路中分支的數(shù)目稱(chēng)為路徑長(zhǎng)度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)-1。 結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長(zhǎng)度:若將樹(shù)中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱(chēng)為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。 樹(shù)的帶權(quán)路徑長(zhǎng)度:樹(shù)的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記為WPL。1.2哈夫曼設(shè)計(jì)目的數(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)是信息的一種組織方式，其目的是為了提高算法的效率， 它通常與一組算法的集合相對(duì)應(yīng)，通過(guò)這組算法集合可以對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。通過(guò)課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專(zhuān)業(yè)素質(zhì)的提高。通過(guò)此次課程設(shè)計(jì)主要達(dá)到以下目的：了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法， 具備初步的獨(dú)立分析和設(shè)計(jì)能力；初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)置、程序編碼、測(cè)試等基本方法和技能；提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力；培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。1.3哈夫曼樹(shù)的應(yīng)用1.3.1哈夫曼樹(shù)的構(gòu)造如圖1-1哈夫曼樹(shù)的構(gòu)造假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹(shù)有n個(gè)葉子結(jié)點(diǎn)。 n個(gè)權(quán)值分別設(shè)為 w1、w2、wn，則哈夫曼樹(shù)的構(gòu)造規(guī)則為：(1) 將w1、w2、，wn看成是有n 棵樹(shù)的森林。(2) 在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和。(3)從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林(4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹(shù)為止，該樹(shù)哈夫曼樹(shù)構(gòu)造圖1-1即為所求得的哈夫曼。1.3.2哈夫曼編碼哈夫曼編碼是一種編碼方式，編碼需從葉子結(jié)點(diǎn)出發(fā)走一條從葉子到根的路徑。在數(shù)據(jù)通信中，需要將傳送的文字轉(zhuǎn)換成二進(jìn)制的字符串，用0，1碼的不同排列來(lái)表示字符。為使不等長(zhǎng)編碼為前綴編碼，可用字符集中的每個(gè)字符作為葉子結(jié)點(diǎn)生成一棵編碼二叉樹(shù)，為了獲得傳送報(bào)文的最短長(zhǎng)度，可將每個(gè)字符的出現(xiàn)頻率作為字符結(jié)點(diǎn)的權(quán)值賦予該結(jié)點(diǎn)上，求出此樹(shù)的最小帶權(quán)路徑長(zhǎng)度就等于求出了傳送報(bào)文的最短長(zhǎng)度。因此，求傳送報(bào)文的最短長(zhǎng)度問(wèn)題轉(zhuǎn)化為求由字符集中的所有字符作為葉子結(jié)點(diǎn)，由字符出現(xiàn)頻率作為其權(quán)值所產(chǎn)生的哈夫曼樹(shù)的問(wèn)題。1.3.3哈夫曼譯碼編碼需從葉子結(jié)點(diǎn)出發(fā)走一條從根到葉子的路徑。在通信中，若將字符用哈夫曼編碼形式發(fā)送出去，對(duì)方接收到編碼后，將編碼還原成字符的過(guò)程，稱(chēng)為哈夫曼譯碼。第二章 設(shè)計(jì)簡(jiǎn)介及設(shè)計(jì)方案論述2.1需求分析2.1.1程序的基本功能本程序可以對(duì)任何大小的字符型文件進(jìn)行Huffman編碼，生成一個(gè)編碼文件。并可以在程序運(yùn)行結(jié)束后的任意時(shí)間對(duì)它解碼還原生成字符文件。即：先對(duì)一條電文進(jìn)行輸入，并實(shí)現(xiàn)Huffman編碼，然后對(duì)Huffman編碼生成的代碼串進(jìn)行譯碼，最后輸出電文數(shù)字。2.1.2輸入/輸出形式當(dāng)進(jìn)行編碼時(shí)輸入為原字符文件文件名，當(dāng)程序運(yùn)行編碼完成之后輸入編碼文件名（默認(rèn)名為code.dll）。當(dāng)進(jìn)行譯碼時(shí)輸入為編碼文件名（默認(rèn)名為code.dll），從文件中讀取Huffman編碼樹(shù)后輸入字符文件的文件名。2.1.3測(cè)試數(shù)據(jù)要求本程序中測(cè)試數(shù)據(jù)主要為字符型文件。2.2概要設(shè)計(jì)2.2.1.系統(tǒng)結(jié)構(gòu)圖（功能模塊圖）哈弗曼樹(shù)編碼譯碼器編碼譯碼退出2.2.2功能模塊說(shuō)明(1)編碼：提示要編碼的文件文件名讀取文件以字母出現(xiàn)次數(shù)為權(quán)值建立哈弗曼樹(shù)對(duì)文本進(jìn)行哈弗曼編碼并輸出編碼提示將編碼保存的文件名保存編碼文件。(2)譯碼:提示輸入要譯碼的文件名利用建立好的哈弗曼樹(shù)進(jìn)行譯碼將譯碼輸出提示保存譯碼文件的文件名保存譯碼文件。(3)退出:退出系統(tǒng)，程序運(yùn)行結(jié)束。2.3 相關(guān)函數(shù)介紹哈夫曼樹(shù)節(jié)點(diǎn)的數(shù)據(jù)類(lèi)型定義為：typedef structHuffmanTree HT; /引用上一個(gè)數(shù)據(jù)類(lèi)型char *c; /存放將要建立哈夫曼樹(shù)的字符int longth; /字符的大小，即開(kāi)始第一步輸入的一個(gè)整數(shù)HuffmanCode HC; /存放對(duì)應(yīng)的哈夫編碼即對(duì)應(yīng)的01代碼Huffman（1）int min(HuffmanTree t,int i)建立哈夫曼樹(shù)，存于文件hfmtree.dat中，供InitHuffman（）函數(shù)調(diào)用。（2）void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)初始化哈夫曼樹(shù)，處理InputHuffman(Huffman Hfm )函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建立2叉樹(shù)，此函數(shù)塊調(diào)用了Select（）函數(shù)。（3）void Select(HuffmanTree HT,int end,int *s1,int *s2)把輸入的字符按權(quán)值從小到大排序，挑出最小權(quán)值供HuffmanCoding()調(diào)用并且根節(jié)點(diǎn)的權(quán)值等于他的左右孩子的權(quán)值和。（4）void Decoding()對(duì)文件中的正文進(jìn)行編碼，將結(jié)果存入文件codefile.dat中。如果正文中沒(méi)有要編碼的字符，則鍵盤(pán)讀入并存儲(chǔ)到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲(chǔ)到CodeFile中。（5）void Decoding(Huffman Hfm)利用已建好的哈夫曼樹(shù)將文件codefile.dat中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat 中。（6）void Code_printing()輸出哈夫曼樹(shù)，字符，權(quán)值，以及它對(duì)應(yīng)的編碼。第三章 詳細(xì)設(shè)計(jì)3.1哈夫曼樹(shù)核心算法Huffman編碼是一種可變長(zhǎng)編碼方式，是二叉樹(shù)的一種特殊轉(zhuǎn)化形式。編碼的原理是：將使用次數(shù)多的代碼轉(zhuǎn)換成長(zhǎng)度較短的代碼，而使用次數(shù)少的可以使用較長(zhǎng)的編碼，并且保持編碼的唯一可解性。Huffman算法的最根本的原則是：累計(jì)的(字符的統(tǒng)計(jì)數(shù)字*字符的編碼長(zhǎng)度)為最小，也就是權(quán)值(字符的統(tǒng)計(jì)數(shù)字*字符的編碼長(zhǎng)度)的和最小。3.1.1哈夫曼樹(shù)構(gòu)造算法已知(186) A(64) B(13) C(22) D(32) E(103) F(21) G(15) H(47) I(57) J(1) K(5) L(32) M(20) N(57) O(63) P (15) Q(1) R(48) S(51) T(80) U(23) V(8) W(18) X(1) Y(16) Z(1) 注：括號(hào)里面的是頻度。生成Huffman樹(shù)：每次取最小的那兩個(gè)節(jié)點(diǎn)(node)合并成一個(gè)節(jié)點(diǎn)(node)，并且將累計(jì)數(shù)值相加作為新的接點(diǎn)的累計(jì)數(shù)值，最頂層的是根節(jié)點(diǎn)。Huffman樹(shù)構(gòu)造如下： Huffman樹(shù) 層數(shù) Root(權(quán)值和1000) 1 MFREINCKUS（權(quán)值和402） JQXZKVWHTBGDOPYLA（權(quán)值和598） 2 MFRE INCUS JQXZKVWHT BGDOPYLA 3 MFR E IN CUS JQXZKVWHT BGDO PYLA 4 MF R I N CU S T JQXZKVWH O BGD A PYL 5 M F C U H JQXZKVW D BG L PY 6 JQXZKV W B G P Y 7 JQXZK V 8 JQXZ K 9 JQ XZ 10 J Q X Z 11注：層數(shù)就是位數(shù)或者說(shuō)是代碼長(zhǎng)度，權(quán)值=代碼長(zhǎng)度*該字的統(tǒng)計(jì)次數(shù)。Huffman樹(shù)對(duì)應(yīng)信息：(取左面是0，右面是1)代碼位數(shù)權(quán)值空格 = 1103186A = 1010464B = 100100613C = 00010522D = 10110532E = 0103103F = 111110621G = 100101615H = 0000447I = 0110457 J = 1111011100101 K = 1111011085L = 10111532M = 111111620N = 0111457O = 1000463P = 100110615Q = 1111011101101R = 0010448S = 0011451T = 1110580U = 00011523V = 111101078W = 111100618X = 1111011110101Y = 100111616Z = 1111011111101哈夫曼編碼算法：將“THIS PROGRAM IS MY FAVORITE”用Huffman樹(shù)產(chǎn)生的編碼對(duì)應(yīng)著寫(xiě)到文件中，并且保留原始的Huffman樹(shù)，主要是編碼段的信息。每個(gè)Huffman樹(shù)都必須有以下的結(jié)構(gòu)：code,char,left,right,probability(出現(xiàn)次數(shù))，通常情況是利用一個(gè)數(shù)組結(jié)構(gòu)。因?yàn)樵诮獯a的時(shí)候只需要用到code，所以只需要記錄每個(gè)元素的編碼就可以了。哈夫曼編碼解碼：利用文件中保存的Huffman編碼，一一對(duì)應(yīng)，解讀編碼，把可變長(zhǎng)編碼轉(zhuǎn)換為定長(zhǎng)編碼。3.2程序流程圖開(kāi)始初始化哈夫曼鏈表且有2n-1個(gè)節(jié)點(diǎn)i=1Iweight=countip=p-nextfor(i=n;iParent=HT2-Parent=pp-LChild=HT1p-RChild=HT2p-weight=HT1-weight+HT2-weight結(jié)束圖3-1創(chuàng)建哈夫曼樹(shù)if(q=q-Parent-LChild)開(kāi)始將字符存入哈夫曼編碼結(jié)構(gòu)體數(shù)組的字符單元中HCi.code-HCi.start=0HCi.code-HCi.start=1p=p-nextI=n 時(shí)結(jié)束圖3-2哈夫曼編碼開(kāi)始Root指向根節(jié)點(diǎn)P!=rootcodei=0p=p-LChildp=p-Rchildp-LChild=NULL&p-RChild=NULLsk+=strjp=root結(jié)束圖3-3哈夫曼譯碼第四章 設(shè)計(jì)結(jié)果及分析4.1調(diào)試分析從葉子節(jié)點(diǎn)開(kāi)始向上遍歷二叉樹(shù),獲得哈夫曼編碼；根據(jù)哈夫曼編碼遍歷哈夫曼樹(shù)直到葉子節(jié)點(diǎn),獲得譯碼；算法的時(shí)間復(fù)雜度分析程序部分用雙循環(huán)嵌套結(jié)構(gòu)；算法的空間復(fù)雜度分析：算法的空間復(fù)雜度為O（n）。4.2 結(jié)果展示4.2.1初始化(Initialization)圖4-1 初始化哈夫曼樹(shù)圖4-2 將建立哈夫曼樹(shù)存于文件hfmtree中4.2.2編碼(Coding)圖4-3 編碼界面圖4-4 對(duì)文件tobetrans中的正文進(jìn)行編碼圖4-5 對(duì)文件tobetrans編碼界面圖4-6 將結(jié)果存入文件codefile4.2.3譯碼(Decoding)圖4-7譯碼界面圖4-8文件codefile譯碼前的界面圖4-9文件codefile譯碼后的界面4.2.4打印代碼文件(Print)圖4-10打印代碼文件界面圖4-11 將編碼文件寫(xiě)入文件codeprint4.2.5打印哈夫曼樹(shù)(Tree printing)圖4-12將哈夫曼樹(shù)寫(xiě)入文件treeprint4.3實(shí)驗(yàn)體會(huì)在運(yùn)行哈夫曼編碼過(guò)程中，構(gòu)造好哈夫曼樹(shù)后，就可根據(jù)哈夫曼樹(shù)進(jìn)行編碼。經(jīng)哈夫曼編碼得到的對(duì)應(yīng)的碼值。只要使用同一棵哈夫曼樹(shù)，就可把編碼還原成原來(lái)那組字符。即譯碼功能的實(shí)現(xiàn)。在調(diào)試過(guò)程中，主要是，在生成哈夫曼樹(shù)時(shí)，須花費(fèi)一定的時(shí)間輸入字符以及權(quán)值的大小。本程序有些代碼重復(fù)出現(xiàn)，從而減少了空間的利用率和增加了程序代碼的雜亂性，特別是文件操作方面，如果可能的話(huà)，可以把文件讀入、讀出分別寫(xiě)成一個(gè)函數(shù)（就是把文件名作為參數(shù)），然后就可以直接調(diào)用了。 此處我將編碼結(jié)果存入了一個(gè)文件，譯碼時(shí)直接從文件讀取逐一譯碼。 本設(shè)計(jì)，功能簡(jiǎn)單明了，且程序代碼可運(yùn)行好，其中用到了數(shù)組，字符串，二叉樹(shù)等知識(shí)以實(shí)現(xiàn)程序。 時(shí)間復(fù)雜度與空間復(fù)雜度。在程序開(kāi)頭部分，就定義了一個(gè)長(zhǎng)度為99的字符數(shù)組，用來(lái)存放用戶(hù)輸入的字符，空間上造成了一定的浪費(fèi)，若能實(shí)現(xiàn)動(dòng)態(tài)的存儲(chǔ)空間，就可以有效的利用好空間。與之相同的還有解碼的時(shí)候，同樣申請(qǐng)了一個(gè)長(zhǎng)度為9999的字符數(shù)組。所以有效的利用好空間時(shí)很好的。在運(yùn)行第一步，也就時(shí)構(gòu)造哈夫曼樹(shù)時(shí)，字符與權(quán)值大小的輸入可能會(huì)造成時(shí)間上的浪費(fèi)，另外就是在譯碼時(shí)沒(méi)能實(shí)用二進(jìn)制流文件對(duì)相關(guān)知識(shí)沒(méi)能融會(huì)貫通，所以需耐心完成。 總 結(jié)課程設(shè)計(jì)是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí),發(fā)現(xiàn),提出,分析和解決實(shí)際問(wèn)題,鍛煉實(shí)踐能力的重要環(huán)節(jié),是對(duì)學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過(guò)程.隨著科學(xué)技術(shù)發(fā)展的日新日異，當(dāng)今計(jì)算機(jī)應(yīng)用在生活中可以說(shuō)得是無(wú)處不在。通過(guò)這次課題實(shí)驗(yàn)的程序?qū)嵺`，我實(shí)在獲益匪淺！數(shù)據(jù)結(jié)構(gòu)是上個(gè)學(xué)期開(kāi)展的一門(mén)學(xué)科，學(xué)習(xí)好這門(mén)學(xué)科是非常重要的，在以后的程序設(shè)計(jì)方面這門(mén)學(xué)科能給我們很大的幫助。同時(shí)，學(xué)習(xí)這門(mén)學(xué)科也是艱辛的，因?yàn)樗容^難懂，這不僅需要我們要發(fā)揮我們的聰明才志，還需要我們?cè)诓粩嗟膶?shí)踐中領(lǐng)悟。這次的程序設(shè)計(jì)對(duì)我來(lái)說(shuō)無(wú)疑是一個(gè)具大的考驗(yàn)，從接起課題后，我就一直為實(shí)現(xiàn)程序而努力，翻閱相關(guān)書(shū)籍、在網(wǎng)上查找資料。因?yàn)殚_(kāi)始時(shí)基礎(chǔ)不是很好，過(guò)程中遇到了不少的阻礙，編寫(xiě)程序的進(jìn)度也比較慢。雖然如此，但是通過(guò)自己的努力與老師的指導(dǎo)，我對(duì)這次實(shí)驗(yàn)的原理有了一定的理解，通過(guò)參照從網(wǎng)上找到的源程序，終于在其它源程序的基礎(chǔ)下寫(xiě)出了本次實(shí)驗(yàn)的核心算法，并使其能夠正常的運(yùn)行。這兩周的課程設(shè)計(jì)工作，讓我體會(huì)到了作為一個(gè)編程人員的艱難，一個(gè)算法到具體實(shí)現(xiàn)，再到應(yīng)用層面的開(kāi)發(fā)是需要有一段較長(zhǎng)的路要走的，不是一朝一夕就可以實(shí)現(xiàn)的，而且在編好程序后，編程人員還要花很多的時(shí)間去完善它，其中包含的心酸，外人是不會(huì)明白的。還有這次的課程設(shè)計(jì)引導(dǎo)了我們盡可能多