哈夫曼編譯碼器課程設(shè)計報告

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計哈夫曼編碼/譯碼器一 目的通過本次課程設(shè)計：復(fù)習(xí)學(xué)過的數(shù)據(jù)結(jié)構(gòu)的內(nèi)容；鞏固和加深對線性表、棧、隊列、字符串、樹、圖、查找、排序等理論知識的理解，這里主要用到二叉樹和棧；掌握現(xiàn)實復(fù)雜問題的分析建模和解決方法；提高利用計算機(jī)分析解決綜合性實際問題的基本能力。二 需求分析目前，進(jìn)行快速遠(yuǎn)距離通信的主要手段是電報，即將需傳送的文字轉(zhuǎn)化成由二進(jìn)制的字符組成的字符串。在傳送電文時，希望總長度盡可能地短。如果對每個字符設(shè)計長度不等的編碼，且讓電文中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，則傳送電文的總長度便可減少。如果要設(shè)計長短不等的編碼，則必須是任一個字符的編碼都不是另外一個字符的編碼的前綴

2、，這種編碼叫前綴編碼。設(shè)計電文總長最短的二進(jìn)制前綴編碼，要以n種字符出現(xiàn)的頻率做權(quán)，設(shè)計一棵哈夫曼樹，由此得到的二進(jìn)制前綴編碼就叫做哈夫曼編碼。編碼時，從待編譯文件tobetran.txt中獲得出現(xiàn)的字符及其出現(xiàn)的次數(shù)（出現(xiàn)次數(shù)即為此字符的權(quán)值）；或從終端獲取各個字符及其權(quán)值據(jù)此建立哈夫曼樹。建好的哈夫曼樹以凹凸表的形式存到文件treeprint.txt中。利用建好的哈夫曼樹對各個字符進(jìn)行編碼，編得的哈夫曼碼存到文件huffmancodes.txt中。利用已建好的各字符的哈夫曼碼對tobetran.txt進(jìn)行逐字編碼，編好的二進(jìn)制字符串存到文件codefile.txt中。在編碼期間，用戶可以選

3、擇是否觀看：建好的哈夫曼樹；建好的各字符的哈夫曼碼；tobetran.txt中的原文；原文經(jīng)編譯產(chǎn)生的二進(jìn)制字符串。譯碼時，從huffmancodes.txt中獲取各字符的哈夫曼碼，據(jù)此建好哈夫曼樹，然后利用建好的哈夫曼樹對文件codefile.txt中的二進(jìn)制字符串進(jìn)行譯碼，將二進(jìn)制字符串譯成對應(yīng)字符集，并把它們存到文件textfile.txt中。 在譯碼期間，用戶可以選擇是否觀看：codefile.txt中的哈夫曼碼集；建好的各字符的哈夫曼碼；哈夫曼碼集經(jīng)譯碼產(chǎn)生的字符集。三 概要設(shè)計1、程序抽象數(shù)據(jù)類型的定義（1）typedef structchar character;/字符unsig

4、ned int weight;/權(quán)值unsigned int parent;/父母節(jié)點unsigned int lchild;/左孩子unsigned int rchild;/右孩子htnode,*phtnode,*huffmantree; huffmantree：哈夫曼樹；htnode：哈夫曼樹的節(jié)點；phtnode：指向哈夫曼樹節(jié)點類型數(shù)據(jù)的指針類型。（2）typedef htnode stackelementtype;typedef structstackelementtype *base;/棧底指針，在棧構(gòu)造前和銷毀后，base的值為0 。stackelementtype *top;/

5、棧頂指針。int stack_max_capacity;/棧的最大容量。int stack_length;/棧當(dāng)前的長度。sqstack;sqstack：棧（在打印哈夫曼樹前建立凹凸表時用到，程序的核心部分沒有用到棧。）（3）typedef int status;status：函數(shù)的返回類型，0代表成功，1代表不成功。2、程序含三個模塊（1）主程序模塊打印菜單；讓用戶選擇是編碼還是譯碼；讓用戶決定是否觀看一些信息。（2）編碼模塊status initialization(huffmantree& ht);初始化哈弗曼樹，統(tǒng)計待編碼文件tobetran.txt中各字符出現(xiàn)次數(shù)并記入哈弗曼樹中；s

6、tatus creathuffman(huffmantree& ht);已知各字符出現(xiàn)次數(shù)，據(jù)此建立哈弗曼樹；status huffmancoding(huffmantree& ht,huffmancode& hc);已建好哈弗曼樹，據(jù)此對各字符進(jìn)行編碼，并將各字符的哈弗曼碼存到huffmancodes.txt中；status textcoding(huffmantree& ht,huffmancode& hc);對tobetran.txt中的文字編碼，結(jié)果存入codefile.txt中。（3）譯碼模塊status creathuffmantree2(huffmantree& ht);讀huf

7、fmancodes.txt，建立哈夫曼樹；status textdecoding(huffmantree& ht);建好哈弗曼樹后，讀codefile.txt 把哈弗曼碼譯為字符并存到textfile.txt中。3、程序中用到的其它函數(shù)（1）打印相應(yīng)東西到屏幕上的3個函數(shù)status showtext(char *filename);讀文件，把里面的字符打到屏幕上。status showtree(huffmantree& ht);哈夫曼樹已建好，把哈夫曼樹以凹凸表形式打印到屏幕上。status showhuffmancodes();各個字符的哈夫曼碼已建好并已存于huffmancodes.tx

8、t中，把各字符的哈夫曼碼打印到屏幕上。（2）棧的6個函數(shù)status initstack(sqstack& s);status push(sqstack& s,stackelementtype e);status pop(sqstack& s,stackelementtype& e);status gettop(sqstack& s,stackelementtype& e);status findsame(sqstack& s,stackelementtype& e);status destorystack(sqstack& s);4、程序流程圖（1）主函數(shù)流程圖（2）編碼模塊流程圖（3）譯碼

9、模塊流程圖四 詳細(xì)設(shè)計1、編碼時建立哈夫曼樹前提：初始化哈弗曼樹， 統(tǒng)計待編碼文件tobetran.txt中各字符出現(xiàn)次數(shù)并記入哈弗曼樹中，即已經(jīng)知道了各字符及其權(quán)值。功能：建立哈夫曼樹。char charsn= ,e,t,a,o,i,n,r,s,h,d,c,.,l,m,p,u,f,g,w,y,b,v,n,k,x,j,q,z;status creathuffman(huffmantree& ht)int i,smallest1,smallest2,m=2*n-1;統(tǒng)計權(quán)值不為零的字符;m=權(quán)值不為零的字符的個數(shù);for(i=n+1;i=m;i+)/建立哈弗曼樹，每循環(huán)一次少一棵子樹/選擇兩棵權(quán)

10、值最小的子樹，smallest1是靠前的那棵select(ht,i-1,smallest1,smallest2);利用儲存哈夫曼樹的數(shù)組的新的一個空間，把此空間的左子樹設(shè)為下標(biāo)為smallest1的節(jié)點，右子樹設(shè)為下標(biāo)為smallest2的節(jié)點；把下標(biāo)為smallest1和smallest2的節(jié)點的父母節(jié)點都設(shè)為新利用空間；return ok;2、對tobetran.txt中的原文進(jìn)行編碼前提：hc中儲存著各個字符的哈夫曼碼。功能：把原文中的各個字符翻譯為這個字符對應(yīng)的哈夫曼碼存于文件中。status textcoding(huffmantree& ht,huffmancode& hc)fil

11、e *fp,*fp2;fp打開待譯文件tobetran.txt；fp2打開codefile.txt；/將把原文譯得的二進(jìn)制字符串寫到里面。/逐個讀tobetran.txt中的字符 在ht對應(yīng)位置找到該字符的碼 把碼打到codefile.txt中while(ch=fgetc(fp)!=eof)int p=1;/從待譯文件中讀到一個字符ch，尋找ch在ht中的位置while(ch!=(*(ht+p).character)p+;fputs(hcp,fp2);/把該字符對應(yīng)的哈夫曼碼寫到codefile.txt中。return ok;3、譯碼時建立哈夫曼樹前提：codefile.txt存在且里面已存有

12、譯好的二進(jìn)制字符串， huffmancodes.txt存在且里面存有編好的各字符的哈夫曼碼，并且這兩個文件里的內(nèi)容是同一個編碼實例產(chǎn)生的。功能：利用huffmancodes.txt建立哈夫曼樹。status creathuffmantree2(huffmantree& ht)for(i=1,p=ht+1;iinitialization(ht)- creathuffman(ht)。發(fā)現(xiàn)的問題及解決策略：對哈夫曼樹的初賦值應(yīng)該分成兩部分，前半部分儲存字符，后半部分儲存非葉子節(jié)點；儲存哈夫曼樹的數(shù)組，出現(xiàn)頻率高的字符放在數(shù)組靠前的位置，這樣子在統(tǒng)計tobetran.txt中各字符出現(xiàn)次數(shù)時可減少尋找

13、對應(yīng)字符的時間；creathuffman(ht)中，有一個while循環(huán)的循環(huán)次數(shù)，原來設(shè)為n+1=icreathuffmantree2(ht)。發(fā)現(xiàn)的問題及解決策略：因為char charsn這個數(shù)組不涉及到對它的改變且至少有三個函數(shù)用到它，所以適合設(shè)為全局變量；因為各個字符的哈夫曼碼都是以“0”開頭的，所以可以忽略這個“0”，建哈夫曼樹時，可以減少使用一個節(jié)點，且在后來的譯碼中，每一個需翻譯的原文字符都少走了一步（解釋：譯碼時，要從根節(jié)點走到葉子節(jié)點，葉子節(jié)點里儲存的是該路徑下對應(yīng)的字符，而該路徑就代表一個哈夫曼碼）。3、調(diào)試內(nèi)容三作用：測試以凹凸表打印哈夫曼樹的模塊是否正確。路徑：mai

14、n()-initialization(ht) creathuffman(ht) showtree(ht)。發(fā)現(xiàn)的問題1：不能正確打印出哈夫曼樹。解決策略：修改路徑為main()-initialization(ht) huffmancoding(ht,hc)-creathuffman(ht) showtree(ht)。結(jié)果：可以正確打印哈夫曼樹了。原因：未找到。發(fā)現(xiàn)的問題2：在status showtree(huffmantree& ht)這個函數(shù)中，char *dir開辟的空間在本函數(shù)快結(jié)束時只要釋放就會在運(yùn)行時產(chǎn)生錯誤。解決策略：把釋放空間的代碼注釋，讓這塊未釋放的空間在程序停止運(yùn)行后由系統(tǒng)

15、自動收回。結(jié)果：可以正確運(yùn)行了，但是這個問題只是被隱藏了，并沒有真正解決。原因：未找到。4、調(diào)試用到的環(huán)境vc+6.0。六 測試結(jié)果1、編碼測試數(shù)據(jù)（存于tobetran.txt中）經(jīng)編譯后得到的各字符的哈夫曼碼（存于huffmancodes.txt中，并可以在屏幕上顯示）經(jīng)編譯產(chǎn)生的二進(jìn)制字符串（存于coldfile.txt中）2、譯碼測試數(shù)據(jù)：見“1，編碼”部分的第四個截圖測試結(jié)果（存于textfile.txt中）七 用戶使用說明1、主界面在此界面下有三個選項（1：編碼；2：譯碼；3：退出。），用戶可以輸入對應(yīng)的數(shù)字再敲回車鍵執(zhí)行相應(yīng)功能。2、編碼（正確運(yùn)行情況下）編碼前請確認(rèn)文件夾內(nèi)已有

16、文件tobetran.txt（已存有待譯原文）、huffmancodes.txt（將存儲編譯得到的各字符的哈夫曼碼）、codefile.txt（將存儲編譯原文得到的哈夫曼碼集）、huffmantree.txt（將把哈夫曼樹存入此中）。獲得字符及其權(quán)值有兩種方法：1，讀待譯文件統(tǒng)計出現(xiàn)的字符及其權(quán)值；2，從鍵盤輸入各字符及其權(quán)值。這里用第1種方法。在此期間，用戶可選擇查看：建好的哈夫曼樹（以凹凸表的形式）、各字符的哈夫曼碼、tobetran.txt中的原文、原文經(jīng)編譯產(chǎn)生的哈夫曼碼集。3、編碼（錯誤輸入情況下）在此次實例中，tobetran.txt中擁有全部的小寫字母及英文空格、英文逗號、英文句

17、號、英文單引號，但是在從終端輸入字符及其權(quán)值時，只輸入了abcdef六種字符，結(jié)果，原文經(jīng)編碼得到二進(jìn)制字符串是不對的。這是因為，程序把原文中除abcdef以外的字符都編碼為1，這樣，就得到了截屏中看到的codefile.txt中的二進(jìn)制字符串。用戶最好是用“從待編譯文件tobetran.txt中獲得出現(xiàn)的字符及其出現(xiàn)的次數(shù)”這種方法來建立哈夫曼樹，這樣可保證建好的電文二進(jìn)制字符串最短。而若從終端輸入字符及其權(quán)值，則有三個弊端：1，需注意輸入的字符正是待譯文件中存在的字符（若待譯文件中沒有的字符卻從終端輸入了該字符，則程序可得到正確運(yùn)行結(jié)果；若待譯文件中有的字符而終端沒有輸入，程序雖然能夠運(yùn)行

18、，但得到的結(jié)果是錯誤的）；2，用戶輸入的字符的權(quán)值不一定和待譯文件中對應(yīng)字符的出現(xiàn)次數(shù)相符合（這樣譯得的二進(jìn)制字符串就可能不是最短的了）；3，浪費時間。4、譯碼譯碼前請確認(rèn)文件夾內(nèi)已有文件huffmancodes.txt（已存有每個字符的哈夫曼碼）、codefile.txt（已存有原文的哈夫曼碼集）和textfile.txt（將存入譯得的原文）。在譯碼期間，用戶可以選擇是否觀看：codefile.txt中的哈夫曼碼集；建好的各字符的哈夫曼碼；哈夫曼碼集經(jīng)譯碼產(chǎn)生的字符集。八 課程設(shè)計總結(jié)做這個課程設(shè)計，最開始想向要求的那樣，從終端輸入字符及其權(quán)值，但是逐漸考慮到剛剛在用戶手冊中提到的用這種方法

19、的三個弊端，于是就開始想另外一種獲得字符集及其權(quán)值的方法，就這樣，“從待編譯文件tobetran.txt中獲得出現(xiàn)的字符及其出現(xiàn)的次數(shù)”這樣的方法誕生了。但是隨后還是把“從終端輸入字符及其權(quán)值”這種建哈夫曼樹的方法也加到了程序里，供用戶二選一。用“從待編譯文件tobetran.txt中獲得出現(xiàn)的字符及其出現(xiàn)的次數(shù)”這樣的方法去建哈夫曼樹，需事先羅列出待譯文件中所有的可能出現(xiàn)的字符，若待譯文件中恰好有這個字符，就建它的哈夫曼碼，若沒有這個字符，則這個字符的哈夫曼碼設(shè)為“1”，因為其它正常的字符的哈夫曼碼開頭的一位都是“0”，這樣子就可以把兩種字符區(qū)分開來。事后證明，在打印各字符的哈夫曼碼時，打印哈夫曼樹時，接收方建哈夫曼樹時（在下一段將詳細(xì)提到），這種區(qū)分是很有必要的。本課程設(shè)計要求的是建好哈夫曼樹編譯了待譯文件，然后利用這棵已建好的哈夫曼樹，把二進(jìn)制字符串翻譯為原文?？紤]到在實際應(yīng)用中，編譯待譯文件時建好的哈夫曼樹在發(fā)送文件方的電腦內(nèi)存中，而發(fā)送文件方只能把二進(jìn)制字符串發(fā)送給接受文件方，所以接受文件方的電腦內(nèi)存中肯定沒有現(xiàn)成的哈夫曼樹可以使用，他只能自己另建一棵。這個是本程序的難點，就是接受文