課程設(shè)計(jì)報(bào)告哈夫曼編碼譯碼系統(tǒng)

1、北京化工大學(xué)北方學(xué)院課程設(shè)計(jì)報(bào)告課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 設(shè)計(jì)題目 哈夫曼編碼/譯碼系統(tǒng) 專業(yè)、班級 軟件工程0901 學(xué) 號 090203014 姓 名 李澤 指導(dǎo)教師 周建敏 設(shè)計(jì)時(shí)間 2012年9月10日2012年9月23日 2012年 10 月 12 日一、 引言（簡要說明設(shè)計(jì)題目的目的、意義、內(nèi)容、主要任務(wù)等） 隨著計(jì)算機(jī)的普遍應(yīng)用與日益發(fā)展，其應(yīng)用早已不局限于簡單的數(shù)值運(yùn)算，而涉及到問題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計(jì)以及設(shè)計(jì)最短路線等復(fù)雜的非數(shù)值處理和操作。算法與數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)就是為以后利用計(jì)算機(jī)資源高效地開發(fā)非數(shù)值處理的計(jì)算機(jī)程序打下堅(jiān)實(shí)的理論、方法和技術(shù)基礎(chǔ)。 算法與數(shù)據(jù)結(jié)構(gòu)旨在

2、分析研究計(jì)算機(jī)加工的數(shù)據(jù)對象的特性，以便選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)，從而使建立在其上的解決問題的算法達(dá)到最優(yōu)。 數(shù)據(jù)結(jié)構(gòu)是在整個(gè)計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個(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)部的存儲安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。數(shù)據(jù)結(jié)構(gòu)主要介紹一些最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計(jì)算機(jī)中的存儲表示，以及在其上進(jìn)行各種運(yùn)算時(shí)的實(shí)現(xiàn)算法，并對算法的效率進(jìn)行簡單的分析和討論

3、。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件之間的一門計(jì)算機(jī)專業(yè)的核心課程，它是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問題中所涉及的對象在計(jì)算機(jī)中表示出來并對它們進(jìn)行處理。通過課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問題中所涉及的對象在計(jì)算機(jī)中表示出來并對它們進(jìn)行處理。通過課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計(jì)主要達(dá)到以下目的：u 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；u

4、 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；u 提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；u 訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。二、 正文（課程設(shè)計(jì)的主要內(nèi)容，包括實(shí)驗(yàn)與觀測方法和結(jié)果、儀器設(shè)備、計(jì)算方法、編程原理、數(shù)據(jù)處理、設(shè)計(jì)說明與依據(jù)、加工整理和圖表、形成的論點(diǎn)和導(dǎo)出的結(jié)論等。正文內(nèi)容必須實(shí)事求是、客觀真切、準(zhǔn)確完備、合乎邏輯、層次分明、語言流暢、結(jié)構(gòu)嚴(yán)謹(jǐn)，符合各學(xué)科、專業(yè)的有關(guān)要求。）問題分析： 設(shè)計(jì)一個(gè)哈夫曼編碼、譯碼系統(tǒng)。對一個(gè)ASCII編碼的文本文件中的字符進(jìn)行哈夫曼編碼，

5、生成編碼文件；反過來，可將編碼文件譯碼還原為一個(gè)文本文件。（1） 從文件中讀入任意一篇英文短文（文件為ASCII編碼，擴(kuò)展名為txt）；（2） 統(tǒng)計(jì)并輸出不同字符在文章中出現(xiàn)的頻率（空格、換行、標(biāo)點(diǎn)等也按字符處理）；（3） 根據(jù)字符頻率構(gòu)造哈夫曼樹，并給出每個(gè)字符的哈夫曼編碼；（4） 將文本文件利用哈夫曼樹進(jìn)行編碼，存儲成壓縮文件（編碼文件后綴名.huf）（5） 用哈夫曼編碼來存儲文件，并和輸入文本文件大小進(jìn)行比較，計(jì)算文件壓縮率；（6） 進(jìn)行譯碼，將huf文件譯碼為ASCII編碼的txt文件，與原txt文件進(jìn)行比較。根據(jù)上述過程可以知道該編碼譯碼器的關(guān)鍵在于字符統(tǒng)計(jì)和哈夫曼樹的創(chuàng)建以及解碼。

6、哈夫曼樹的理論創(chuàng)建過程如下：一、構(gòu)成初始集合對給定的n個(gè)權(quán)值W1,W2,W3,.,Wi,.,Wn構(gòu)成n棵二叉樹的初始集合F=T1,T2,T3,.,Ti,.,Tn，其中每棵二叉樹Ti中只有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn)，它的左右子樹均為空。 二、選取左右子樹在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為新構(gòu)造的二叉樹的左右子樹，新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹的根結(jié)點(diǎn)的權(quán)值之和。 三、刪除左右子樹從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。 四、重復(fù)二和三兩步，重復(fù)二和三兩步，直到集合F中只有一棵二叉樹為止。 因此，有如下分析：1. 我們需要一個(gè)功能函數(shù)對ASCII碼的初始化并需要一個(gè)數(shù)

7、組來保存它們；2. 定義代表森林的數(shù)組，在創(chuàng)建哈夫曼樹的過程當(dāng)中保存被選中的字符，即給定報(bào)文中出現(xiàn)的字符,模擬哈夫曼樹選取和刪除左右子樹的過程；3. 自底而上地創(chuàng)建哈夫曼樹，保存根的地址和每個(gè)葉節(jié)點(diǎn)的地址，即字符的地址，然后自底而上檢索，首尾對換調(diào)整為哈夫曼樹實(shí)現(xiàn)哈弗曼編碼；4. 從哈弗曼編碼文件當(dāng)中讀入字符，根據(jù)當(dāng)前字符為0或者1的狀況訪問左子樹或者右孩子，實(shí)現(xiàn)解碼；5. 使用文件讀寫操作哈夫曼編碼和解碼結(jié)果的寫入； 解題方法： 結(jié)構(gòu)體、數(shù)組、類的定義：1. 定義結(jié)構(gòu)體類型的signode 作為哈夫曼樹的節(jié)點(diǎn)，定義結(jié)構(gòu)體類型的hufnode 作為哈夫曼編碼對照表的節(jié)點(diǎn)，定義HFM類實(shí)現(xiàn)對哈夫

8、曼樹的創(chuàng)建，利用其成員函數(shù)完成哈夫曼編碼譯碼的工作。2. 定義signode 類型的全局?jǐn)?shù)組SN256（為方便調(diào)用，之后的forest256，hufNode256均為全局?jǐn)?shù)組）, 保存ASCII編碼的字符，是否在文章中出現(xiàn)（bool類型）以及出現(xiàn)次數(shù)（int類型，權(quán)重），左右孩子節(jié)點(diǎn)位置，父節(jié)點(diǎn)位置信息；3. 為節(jié)省存儲空間，定義signode * 類型的全局?jǐn)?shù)組forest256, 模擬森林，在創(chuàng)建哈夫曼樹的過程中保存出現(xiàn)字符的指針，模擬哈夫曼樹選取和刪除左右子樹的過程；4. 定義hufnode 類型的全局?jǐn)?shù)組hufNode256，在編碼時(shí)最為哈夫曼編碼對照表的節(jié)點(diǎn)，char 型c保存字符,

9、int code100保存其哈夫曼編碼；5. 定義HFM類，主要保存哈夫曼樹的根節(jié)點(diǎn)指針，但其豐富的功能函數(shù)將實(shí)現(xiàn)哈夫曼編碼譯碼的工作及其他功能；函數(shù)介紹：1. void init(signode * sig) 初始化數(shù)組SN；2. void compress()輸出壓縮對比情況的信息;3. void exchange()用兩層for循環(huán)實(shí)現(xiàn)hufNodei節(jié)點(diǎn)的成員哈夫曼編碼數(shù)組code前后元素的對換，因?yàn)樵谥暗木幋a過程中由于是從葉節(jié)點(diǎn)追溯至根節(jié)點(diǎn)，存入code數(shù)組的哈夫曼編碼與哈夫曼編碼的概念反向，故而要調(diào)整；4. signode * getroot()返回哈夫曼樹的根節(jié)點(diǎn)指針；5. s

10、ignode * HFM:creat()創(chuàng)建哈夫曼樹，首先用三個(gè)for循環(huán)查看forest數(shù)組，找到權(quán)值最小的兩個(gè)字符，以int型的min1,min2記錄其下標(biāo)，定義signode * 類型指針pp指向新生成signode節(jié)點(diǎn)，用指針操作使pp指向的節(jié)點(diǎn)的權(quán)值為min1,min2權(quán)值之和，pp做孩子指向forestmin1,右孩子指向forestmin2，min1,min2的父指針指向pp，然后將pp存入min1的位置，min2之后的每一個(gè)節(jié)點(diǎn)依次往前移一個(gè)位置，實(shí)現(xiàn)從forest數(shù)組中清除min1,min2并加入pp的操作；6. void HFM:hufcode()哈夫曼編碼，用for循環(huán)控

11、制查看hufNode 數(shù)組，其初始化已在creat（）的開始完成，對每一個(gè)字符實(shí)現(xiàn)編碼，用while循環(huán)從葉節(jié)點(diǎn)開始，如果該節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子就將codehufNodei.size+賦值0，否則賦為1，直至當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)為空，while循環(huán)結(jié)束；7. void HFM:savewithhufcode(FILE * inf,FILE * outf)將讀入的文章以哈夫曼編碼的形式存儲，其中inf為讀入文件的指針，outf為寫入文件的指針,首先調(diào)用rewind(inf)函數(shù)將光標(biāo)放置在文章開頭，防止文件未關(guān)閉導(dǎo)致的錯(cuò)誤，每讀一個(gè)字符就用for循環(huán)在hufNode 數(shù)組中查找，因?yàn)閔ufNode

12、 數(shù)組就是保存出現(xiàn)的字符的，故一定可以找到，然后再用fputc函數(shù)將code數(shù)組的內(nèi)容寫入文件，直至讀入文件結(jié)束；8. void HFM:inorder(signode * sig)迭代法遍歷樹，遍歷到葉節(jié)點(diǎn)時(shí)執(zhí)行hufNodecount+.sig=sig語句實(shí)現(xiàn)hufNode 數(shù)組指向文章中出現(xiàn)的字符；9. int HFM:maxc() 計(jì)數(shù)變量，記錄哈夫曼編碼最大位數(shù)；10. void HFM:hufdecode(FILE* ipf,FILE* opf)解碼，從哈夫曼編碼到字符，輸出到屏幕和指定的文件中；11. void input(FILE * f)初始讀入文章，保存出現(xiàn)的字符記錄修改其

13、權(quán)重；數(shù)據(jù)結(jié)構(gòu)選擇與算法設(shè)計(jì) 數(shù)據(jù)結(jié)構(gòu)選擇：signode： struct signode /signode節(jié)點(diǎn)，哈夫曼樹節(jié)點(diǎn)/ char c; /字符/ int weight; /權(quán)重/ bool b; /文章中是否出現(xiàn)/ signode * parent; signode * left; signode * right; signode() /初始化/ c=NULL; b=false; weight=0; parent=left=right=NULL; ; Cweightbparentleftright hufnode: struct hufnode /哈夫曼編碼對照表節(jié)點(diǎn)/ signod

14、e * sig; int code100; /保存哈夫曼編碼/ int size;bool b; hufnode()sig=NULL;size=0;b=true;Sig code100 size;HFM:class HFM /哈夫曼類/ private: signode * root; /哈夫曼樹根/ signode * pt; /編碼時(shí)做哨兵指針/ int alleaf; public: HFM(int all)root=pt=NULL;alleaf=all; /all是森林中樹的個(gè)數(shù)/ HFM() signode * getroot()return root; signode * crea

15、t(); /創(chuàng)建哈夫曼樹/ void hufcode(); /編碼/ void savewithhufcode(FILE * inf,FILE * outf); /用哈弗曼編碼存儲文件/ void hufdecode(FILE* ipf,FILE* opf); /解碼/ void inorder(signode * sig); int maxc(); /求取哈弗曼編碼最大長度/;Root pt alleafcreat() hufcode() savewithhufcode(inf,outf) inorder(sig) getroot()hufdecode(ipf,opf) maxc()算法設(shè)計(jì)

16、：init(SN)初始化SN數(shù)組input（f1）從f1讀入字符 輸出字符信息及權(quán)重 huffman.creat（）創(chuàng)建哈夫曼樹 huffman.hufcode(); exchange(); huffman.savewithhufcode(f1,f2);哈夫曼編碼并用該編碼保存 文件輸入數(shù)字選擇compress（）1. 查看哈夫曼編碼3.查看壓縮率2.哈夫曼解碼huffman.hufdecode(f2,f3)輸入數(shù)字選擇測試結(jié)果Doc窗口： 文件讀寫（部分）： 三、 結(jié)論（應(yīng)當(dāng)準(zhǔn)確、完整、明確精練；也可以在結(jié)論或討論中提出建議、設(shè)想、尚待解決問題等。） 初始的創(chuàng)建是哈夫曼編碼譯碼系統(tǒng)成功的關(guān)鍵

17、，我在創(chuàng)建的過程當(dāng)中多次使用樹的先根，配合中根遍歷操作，輸出接點(diǎn)字符或者權(quán)重信息，作為檢驗(yàn)，對驗(yàn)證和糾錯(cuò)起到了非常大的作用。在適當(dāng)?shù)牡胤秸{(diào)用它們，運(yùn)行時(shí)可以看到驗(yàn)證編寫程序的正確性； 通過本次實(shí)驗(yàn)，提高了自已調(diào)試程序的能力。充分體會到了在程序執(zhí)行時(shí)的提示性輸出的重要性。編寫大一點(diǎn)的程序，應(yīng)先寫出算法，再寫程序，一段一段調(diào)試；對于沒有實(shí)現(xiàn)的操作用空操作代替，這樣容易找出錯(cuò)誤所在。最忌諱將所有代碼寫完后再調(diào)試，這樣若程序有錯(cuò)誤，太難找 。感覺文件操作自己并不是很熟練，盡管在向顯示器輸出的時(shí)候并沒有什么錯(cuò)誤但是讀寫文件的時(shí)候就沒那么順利了，比如說當(dāng)編寫savewithhufcode函數(shù)時(shí)讀文件，卻總不執(zhí)行，后來通過斷點(diǎn)測試發(fā)現(xiàn)每次fgetc()返回值總為-1，于是我考慮是否是文件沒有打開或者文件結(jié)束的緣故，后來想通了是之前打開的文件光標(biāo)讀操作結(jié)束后仍在結(jié)尾故每次總返回-1，故調(diào)用rewind函數(shù)將光標(biāo)位置移動到文章開始。 用哈夫曼編碼存儲文件的時(shí)候還應(yīng)注意數(shù)字0,1與字符0,1的不同，不應(yīng)直接在fputc()函數(shù)中直接寫入0,1那么將會是寫入的