哈夫曼編譯碼器課程設計報告

1、<p><b>　　哈夫曼編碼/譯碼器</b></p><p><b>　　一 目的</b></p><p>　　通過本次課程設計：復習學過的數(shù)據(jù)結構的內(nèi)容；鞏固和加深對線性表、棧、隊列、字符串、樹、圖、查找、排序等理論知識的理解，這里主要用到二叉樹和棧；掌握現(xiàn)實復雜問題的分析建模和解決方法；提高利用計算機分析解決綜合性實際問題的基本

2、能力。</p><p><b>　　二 需求分析</b></p><p>　　目前，進行快速遠距離通信的主要手段是電報，即將需傳送的文字轉化成由二進制的字符組成的字符串。在傳送電文時，希望總長度盡可能地短。如果對每個字符設計長度不等的編碼，且讓電文中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，則傳送電文的總長度便可減少。如果要設計長短不等的編碼，則必須是任一個字符的編碼都

3、不是另外一個字符的編碼的前綴，這種編碼叫前綴編碼。設計電文總長最短的二進制前綴編碼，要以n種字符出現(xiàn)的頻率做權，設計一棵哈夫曼樹，由此得到的二進制前綴編碼就叫做哈夫曼編碼。</p><p>　　編碼時，從待編譯文件ToBeTran.txt中獲得出現(xiàn)的字符及其出現(xiàn)的次數(shù)（出現(xiàn)次數(shù)即為此字符的權值）；或從終端獲取各個字符及其權值據(jù)此建立哈夫曼樹。建好的哈夫曼樹以凹凸表的形式存到文件TreePrint.txt中。利用建

4、好的哈夫曼樹對各個字符進行編碼，編得的哈夫曼碼存到文件HuffmanCodes.txt中。利用已建好的各字符的哈夫曼碼對ToBeTran.txt進行逐字編碼，編好的二進制字符串存到文件CodeFile.txt中。</p><p>　　在編碼期間，用戶可以選擇是否觀看：建好的哈夫曼樹；建好的各字符的哈夫曼碼；ToBeTran.txt中的原文；原文經(jīng)編譯產(chǎn)生的二進制字符串。</p><p>　

5、　譯碼時，從HuffmanCodes.txt中獲取各字符的哈夫曼碼，據(jù)此建好哈夫曼樹，然后利用建好的哈夫曼樹對文件CodeFile.txt中的二進制字符串進行譯碼，將二進制字符串譯成對應字符集，并把它們存到文件TextFile.txt中。</p><p>　　在譯碼期間，用戶可以選擇是否觀看：CodeFile.txt中的哈夫曼碼集；建好的各字符的哈夫曼碼；哈夫曼碼集經(jīng)譯碼產(chǎn)生的字符集。</p>&l

6、t;p><b>　　三 概要設計</b></p><p>　　1、程序抽象數(shù)據(jù)類型的定義</p><p><b>　?。?）</b></p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　c

7、har character;//字符</p><p>　　unsigned int weight;//權值</p><p>　　unsigned int parent;//父母節(jié)點</p><p>　　unsigned int lchild;//左孩子</p><p>　　unsigned int rchild;//右孩子</p>

8、<p>　　}HTNode,*PHTNode,*HuffmanTree; </p><p>　　HuffmanTree：哈夫曼樹；HTNode：哈夫曼樹的節(jié)點；PHTNode：指向哈夫曼樹節(jié)點類型數(shù)據(jù)的指針類型。</p><p><b>　　（2）</b></p><p>　　typedef HTNode StackElement

9、Type;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　StackElementType *base;//棧底指針，在棧構造前和銷毀后，base的值為0 。</p><p>　　StackElementType *top;//棧頂指針。</p>

10、<p>　　int stack_max_capacity;//棧的最大容量。</p><p>　　int stack_length;//棧當前的長度。</p><p><b>　　}SqStack;</b></p><p>　　SqStack：棧（在打印哈夫曼樹前建立凹凸表時用到，程序的核心部分沒有用到棧。）</p>

11、<p><b>　　（3）</b></p><p>　　typedef int Status;</p><p>　　Status：函數(shù)的返回類型，0代表成功，1代表不成功。</p><p><b>　　2、程序含三個模塊</b></p><p><b>　?。?）主程序模塊&l

12、t;/b></p><p><b>　　打印菜單；</b></p><p>　　讓用戶選擇是編碼還是譯碼；</p><p>　　讓用戶決定是否觀看一些信息。</p><p><b>　?。?）編碼模塊</b></p><p>　　Status Initializatio

13、n(HuffmanTree& HT);</p><p>　　初始化哈弗曼樹，統(tǒng)計待編碼文件ToBeTran.txt中各字符出現(xiàn)次數(shù)并記入哈弗曼樹中；</p><p>　　Status CreatHuffman(HuffmanTree& HT);</p><p>　　已知各字符出現(xiàn)次數(shù)，據(jù)此建立哈弗曼樹；</p><p>　　S

14、tatus HuffmanCoding(HuffmanTree& HT,HuffmanCode& HC);</p><p>　　已建好哈弗曼樹，據(jù)此對各字符進行編碼，并將各字符的哈弗曼碼存到HuffmanCodes.txt中；</p><p>　　Status TextCoding(HuffmanTree& HT,HuffmanCode& HC);</

15、p><p>　　對ToBeTran.txt中的文字編碼，結果存入CodeFile.txt中。</p><p><b>　?。?）譯碼模塊</b></p><p>　　Status CreatHuffmanTree2(HuffmanTree& HT);</p><p>　　讀HuffmanCodes.txt，建立哈夫曼

16、樹；</p><p>　　Status TextDecoding(HuffmanTree& HT);</p><p>　　建好哈弗曼樹后，讀CodeFile.txt 把哈弗曼碼譯為字符并存到TextFile.txt中。</p><p>　　3、程序中用到的其它函數(shù)</p><p>　?。?）打印相應東西到屏幕上的3個函數(shù)</p&

17、gt;<p>　　Status ShowText(char *filename);</p><p>　　讀文件，把里面的字符打到屏幕上。</p><p>　　Status ShowTree(HuffmanTree& HT);</p><p>　　哈夫曼樹已建好，把哈夫曼樹以凹凸表形式打印到屏幕上。</p><p>　　S

18、tatus ShowHuffmanCodes();</p><p>　　各個字符的哈夫曼碼已建好并已存于HuffmanCodes.txt中，把各字符的哈夫曼碼打印到屏幕上。</p><p><b>　　（2）棧的6個函數(shù)</b></p><p>　　Status InitStack(SqStack& S);</p><

19、;p>　　Status Push(SqStack& S,StackElementType E);</p><p>　　Status Pop(SqStack& S,StackElementType& E);</p><p>　　Status GetTop(SqStack& S,StackElementType& E);</p>&l

20、t;p>　　Status FindSame(SqStack& S,StackElementType& E);</p><p>　　Status DestoryStack(SqStack& S);</p><p><b>　　4、程序流程圖</b></p><p><b>　?。?）主函數(shù)流程圖</b

21、></p><p>　　（2）編碼模塊流程圖</p><p>　?。?）譯碼模塊流程圖</p><p><b>　　四 詳細設計</b></p><p>　　1、編碼時建立哈夫曼樹</p><p>　　前提：初始化哈弗曼樹， 統(tǒng)計待編碼文件ToBeTran.txt中各字符出現(xiàn)次數(shù)并記入哈弗

22、曼樹中，即已經(jīng)知道了各字符及其權值。</p><p>　　功能：建立哈夫曼樹。</p><p>　　char chars[N]={' ','e','t','a','o','i','n','r','s','h','d'

23、,'c',',','.','l','m','p','u','f','g','w','y','b','v','\'','\n','k','x','j

24、9;,'q','z'};</p><p>　　Status CreatHuffman(HuffmanTree& HT)</p><p><b>　　{</b></p><p>　　int i,smallest1,smallest2,m=2*N-1;</p><p>　　統(tǒng)計權值不為

25、零的字符;</p><p>　　m=權值不為零的字符的個數(shù);</p><p>　　for(i=N+1;i<=m;i++)//建立哈弗曼樹，每循環(huán)一次少一棵子樹</p><p><b>　　{</b></p><p>　　//選擇兩棵權值最小的子樹，smallest1是靠前的那棵</p><p&g

26、t;　　Select(HT,i-1,smallest1,smallest2);</p><p>　　利用儲存哈夫曼樹的數(shù)組的新的一個空間，把此空間的左子樹設為下標為smallest1的節(jié)點，右子樹設為下標為smallest2的節(jié)點；</p><p>　　把下標為smallest1和smallest2的節(jié)點的父母節(jié)點都設為新利用空間；</p><p><b>

27、;　　}</b></p><p>　　return OK;</p><p><b>　　}</b></p><p>　　2、對ToBeTran.txt中的原文進行編碼</p><p>　　前提：HC中儲存著各個字符的哈夫曼碼。</p><p>　　功能：把原文中的各個字符翻譯為這個字符

28、對應的哈夫曼碼存于文件中。</p><p>　　Status TextCoding(HuffmanTree& HT,HuffmanCode& HC)</p><p><b>　　{</b></p><p>　　FILE *fp,*fp2;</p><p>　　fp打開待譯文件ToBeTran.txt；&l

29、t;/p><p>　　fp2打開CodeFile.txt；//將把原文譯得的二進制字符串寫到里面。</p><p>　　//逐個讀ToBeTran.txt中的字符 在HT對應位置找到該字符的碼 把碼打到CodeFile.txt中</p><p>　　while((ch=fgetc(fp))!=EOF)</p><p><b>　　{&l

30、t;/b></p><p><b>　　int p=1;</b></p><p>　　//從待譯文件中讀到一個字符ch，尋找ch在HT中的位置</p><p>　　while(ch!=(*(HT+p)).character)</p><p><b>　　p++;</b></p>

31、<p>　　fputs(HC[p],fp2);//把該字符對應的哈夫曼碼寫到CodeFile.txt中。</p><p><b>　　}</b></p><p>　　return OK;</p><p><b>　　}</b></p><p>　　3、譯碼時建立哈夫曼樹</p>

32、<p>　　前提：CodeFile.txt存在且里面已存有譯好的二進制字符串， HuffmanCodes.txt存在且里面存有編好的各字符的哈夫曼碼，并且這兩個文件里的內(nèi)容是同一個編碼實例產(chǎn)生的。</p><p>　　功能：利用HuffmanCodes.txt建立哈夫曼樹。</p><p>　　Status CreatHuffmanTree2(HuffmanTree&

33、 HT)</p><p><b>　　{</b></p><p>　　for(i=1,p=HT+1;i<=m;i++,p++)//對哈弗曼樹進行初始化</p><p>　　{ (*p).character='#'; (*p).lchild=0; (*p).rchild=0;}</p><p>&l

34、t;b>　　FILE *fp;</b></p><p>　　fp打開HuffmanCodes.txt；//這樣可獲取每個字符的哈夫曼碼。</p><p><b>　　char ch;</b></p><p>　　int s=0;//s代表chars中的位置</p><p>　　int q=1;//q是未

35、入哈弗曼樹的第一個節(jié)點的下標</p><p>　　while((ch=fgetc(fp))!=EOF)</p><p><b>　　{</b></p><p>　　HuffmanCodes.txt中哈夫曼碼為1的字符不做處理，continue；</p><p>　　//其它的做以下處理：</p><p

36、><b>　　int z=1;</b></p><p>　　while(遍歷該字符的哈夫曼碼的每一位)</p><p><b>　　{</b></p><p>　　讀此字符的哈夫曼碼的每一位，為0的則利用儲存哈夫曼樹的數(shù)組的第一個未被利用的空間，把此空間設為已利用的空間的右孩子，為1的設為左孩子;</p>

37、<p>　　非葉子節(jié)點的character都設為‘#’;</p><p><b>　　}</b></p><p>　　葉子節(jié)點的character設為對應字符;</p><p><b>　　}</b></p><p>　　return OK;</p><p>&

38、lt;b>　　}</b></p><p>　　4、對CodeFile.txt中的二進制字符串進行譯碼</p><p>　　前提：哈夫曼樹已建好，CodeFile.txt存在且里面存有滿足一定條件的二進制字符串。</p><p>　　功能：對CodeFile.txt中的二進制字符串進行譯碼，譯得的原文存于TextFile.txt中。</p>

39、;<p>　　Status TextDecoding(HuffmanTree& HT)</p><p><b>　　{</b></p><p>　　FILE *fp,*fp2;</p><p>　　fp打開CodeFile.txt；fp2打開TextFile.txt；</p><p><b&g

40、t;　　char ch;</b></p><p>　　while((ch=fgetc(fp))!=EOF)</p><p><b>　　{</b></p><p>　　int s=1;//從數(shù)組1位置 即根節(jié)點開始往下走 根節(jié)點作為父母節(jié)點</p><p>　　while((ch=fgetc(fp))!=EO

41、F)//又讀了一位 因為每個字符的碼的第一位都是0 故要忽略</p><p><b>　　{</b></p><p>　　if(ch=='0') s=HT[s].rchild;//從節(jié)點HT[s]往下走了一層 付給s新值 s為新的父母節(jié)點的下標。</p><p>　　else s=HT[s].lchild;</p>

42、<p>　　if(HT[s].character=='#') continue;//如果新的這層的節(jié)點內(nèi)存有'#' 則應continue 。</p><p>　　else {fputc(HT[s].character,fp2); break;}//直到讀到非'#'時break 說明此時一段哈碼已被譯為一個字符 則可開始一段新的哈碼。</p>

43、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　return OK;</p><p><b>　　}</b></p><p><b>　　五 調(diào)試分析</b></p><p>

44、;<b>　　1、調(diào)試內(nèi)容一</b></p><p>　　作用：測試編碼模塊建好的哈夫曼樹是否和預期的一致。</p><p>　　路徑：main()--->Initialization(HT)---> CreatHuffman(HT)。</p><p>　　發(fā)現(xiàn)的問題及解決策略：對哈夫曼樹的初賦值應該分成兩部分，前半部分儲存字符，后

45、半部分儲存非葉子節(jié)點；儲存哈夫曼樹的數(shù)組，出現(xiàn)頻率高的字符放在數(shù)組靠前的位置，這樣子在統(tǒng)計ToBeTran.txt中各字符出現(xiàn)次數(shù)時可減少尋找對應字符的時間；CreatHuffman(HT)中，有一個while循環(huán)的循環(huán)次數(shù)，原來設為N+1<=i<=2*N-1，但運行不出正確結果，經(jīng)調(diào)試發(fā)現(xiàn)，while循環(huán)的循環(huán)次數(shù)不是一個固定的值，而是需要編碼幾種字符就循環(huán)幾次，所以后來就設了個計數(shù)器來記錄有幾種字符需編碼，這個問題就解決

46、了。</p><p><b>　　2、調(diào)試內(nèi)容二</b></p><p>　　作用：測試譯碼模塊建的哈夫曼樹是否和預期的一致。</p><p>　　路徑：main()--->CreatHuffmanTree2(HT)。</p><p>　　發(fā)現(xiàn)的問題及解決策略：因為char chars[N]這個數(shù)組不涉及到對它的改

47、變且至少有三個函數(shù)用到它，所以適合設為全局變量；因為各個字符的哈夫曼碼都是以“0”開頭的，所以可以忽略這個“0”，建哈夫曼樹時，可以減少使用一個節(jié)點，且在后來的譯碼中，每一個需翻譯的原文字符都少走了一步（解釋：譯碼時，要從根節(jié)點走到葉子節(jié)點，葉子節(jié)點里儲存的是該路徑下對應的字符，而該路徑就代表一個哈夫曼碼）。</p><p><b>　　3、調(diào)試內(nèi)容三</b></p><

48、p>　　作用：測試以凹凸表打印哈夫曼樹的模塊是否正確。</p><p>　　路徑：main()--->Initialization(HT) CreatHuffman(HT) ShowTree(HT)。</p><p>　　發(fā)現(xiàn)的問題1：不能正確打印出哈夫曼樹。</p><p>　　解決策略：修改路徑為main()--->Initialization

49、(HT) HuffmanCoding(HT,HC)-CreatHuffman(HT) ShowTree(HT)。</p><p>　　結果：可以正確打印哈夫曼樹了。</p><p><b>　　原因：未找到。</b></p><p>　　發(fā)現(xiàn)的問題2：在Status ShowTree(HuffmanTree& HT)這個函數(shù)中，char

50、 *dir開辟的空間在本函數(shù)快結束時只要釋放就會在運行時產(chǎn)生錯誤。</p><p>　　解決策略：把釋放空間的代碼注釋，讓這塊未釋放的空間在程序停止運行后由系統(tǒng)自動收回。</p><p>　　結果：可以正確運行了，但是這個問題只是被隱藏了，并沒有真正解決。</p><p><b>　　原因：未找到。</b></p><p&g

51、t;<b>　　4、調(diào)試用到的環(huán)境</b></p><p><b>　　VC++6.0。</b></p><p><b>　　六 測試結果</b></p><p><b>　　1、編碼</b></p><p>　　測試數(shù)據(jù)（存于ToBeTran.txt中

52、）</p><p>　　經(jīng)編譯后得到的各字符的哈夫曼碼（存于HuffmanCodes.txt中，并可以在屏幕上顯示）</p><p>　　經(jīng)編譯產(chǎn)生的二進制字符串（存于ColdFile.txt中）</p><p><b>　　2、譯碼</b></p><p>　　測試數(shù)據(jù)：見“1，編碼”部分的第四個截圖</p>

53、;<p>　　測試結果（存于TextFile.txt中）</p><p><b>　　七 用戶使用說明</b></p><p><b>　　1、主界面</b></p><p>　　在此界面下有三個選項（1：編碼；2：譯碼；3：退出。），用戶可以輸入對應的數(shù)字再敲回車鍵執(zhí)行相應功能。</p>&

54、lt;p>　　2、編碼（正確運行情況下）</p><p>　　編碼前請確認文件夾內(nèi)已有文件ToBeTran.txt（已存有待譯原文）、HuffmanCodes.txt（將存儲編譯得到的各字符的哈夫曼碼）、CodeFile.txt（將存儲編譯原文得到的哈夫曼碼集）、HuffmanTree.txt（將把哈夫曼樹存入此中）。</p><p>　　獲得字符及其權值有兩種方法：1，讀待譯文件統(tǒng)

55、計出現(xiàn)的字符及其權值；2，從鍵盤輸入各字符及其權值。這里用第1種方法。</p><p>　　在此期間，用戶可選擇查看：建好的哈夫曼樹（以凹凸表的形式）、各字符的哈夫曼碼、ToBeTran.txt中的原文、原文經(jīng)編譯產(chǎn)生的哈夫曼碼集。</p><p>　　3、編碼（錯誤輸入情況下）</p><p>　　在此次實例中，ToBeTran.txt中擁有全部的小寫字母及英文空

56、格、英文逗號、英文句號、英文單引號，但是在從終端輸入字符及其權值時，只輸入了abcdef六種字符，結果，原文經(jīng)編碼得到二進制字符串是不對的。這是因為，程序把原文中除abcdef以外的字符都編碼為1，這樣，就得到了截屏中看到的CodeFile.txt中的二進制字符串。</p><p>　　用戶最好是用“從待編譯文件ToBeTran.txt中獲得出現(xiàn)的字符及其出現(xiàn)的次數(shù)”這種方法來建立哈夫曼樹，這樣可保證建好的電文二

57、進制字符串最短。而若從終端輸入字符及其權值，則有三個弊端：1，需注意輸入的字符正是待譯文件中存在的字符（若待譯文件中沒有的字符卻從終端輸入了該字符，則程序可得到正確運行結果；若待譯文件中有的字符而終端沒有輸入，程序雖然能夠運行，但得到的結果是錯誤的）；2，用戶輸入的字符的權值不一定和待譯文件中對應字符的出現(xiàn)次數(shù)相符合（這樣譯得的二進制字符串就可能不是最短的了）；3，浪費時間。</p><p><b>　

58、　4、譯碼</b></p><p>　　譯碼前請確認文件夾內(nèi)已有文件HuffmanCodes.txt（已存有每個字符的哈夫曼碼）、CodeFile.txt（已存有原文的哈夫曼碼集）和TextFile.txt（將存入譯得的原文）。</p><p>　　在譯碼期間，用戶可以選擇是否觀看：CodeFile.txt中的哈夫曼碼集；建好的各字符的哈夫曼碼；哈夫曼碼集經(jīng)譯碼產(chǎn)生的字符集。&

59、lt;/p><p><b>　　八 課程設計總結</b></p><p>　　做這個課程設計，最開始想向要求的那樣，從終端輸入字符及其權值，但是逐漸考慮到剛剛在用戶手冊中提到的用這種方法的三個弊端，于是就開始想另外一種獲得字符集及其權值的方法，就這樣，“從待編譯文件ToBeTran.txt中獲得出現(xiàn)的字符及其出現(xiàn)的次數(shù)”這樣的方法誕生了。但是隨后還是把“從終端輸入字符及

60、其權值”這種建哈夫曼樹的方法也加到了程序里，供用戶二選一。</p><p>　　用“從待編譯文件ToBeTran.txt中獲得出現(xiàn)的字符及其出現(xiàn)的次數(shù)”這樣的方法去建哈夫曼樹，需事先羅列出待譯文件中所有的可能出現(xiàn)的字符，若待譯文件中恰好有這個字符，就建它的哈夫曼碼，若沒有這個字符，則這個字符的哈夫曼碼設為“1”，因為其它正常的字符的哈夫曼碼開頭的一位都是“0”，這樣子就可以把兩種字符區(qū)分開來。事后證明，在打印各字

61、符的哈夫曼碼時，打印哈夫曼樹時，接收方建哈夫曼樹時（在下一段將詳細提到），這種區(qū)分是很有必要的。</p><p>　　本課程設計要求的是建好哈夫曼樹編譯了待譯文件，然后利用這棵已建好的哈夫曼樹，把二進制字符串翻譯為原文?？紤]到在實際應用中，編譯待譯文件時建好的哈夫曼樹在發(fā)送文件方的電腦內(nèi)存中，而發(fā)送文件方只能把二進制字符串發(fā)送給接受文件方，所以接受文件方的電腦內(nèi)存中肯定沒有現(xiàn)成的哈夫曼樹可以使用，他只能自己另建一

62、棵。這個是本程序的難點，就是接受文件方要依據(jù)些什么東西才能建一棵和發(fā)送文件方一樣的哈夫曼樹。于是我想到，發(fā)送方要把各字符的哈夫曼碼隨同譯好的二進制電文一同發(fā)送給接收方，接收方要和發(fā)送方使用相同的字符順序，這樣接收方就可以知道各個字符的哈夫曼碼，他就依據(jù)這個可以再建一棵哈夫曼樹（接收方的哈夫曼樹形態(tài)上和發(fā)送方的大大不同，但實質(zhì)上一模一樣）。</p><p>　　寫這個程序遇到的另一個難點是怎樣把哈夫曼樹以凹凸表的形

63、式打印到屏幕上。一開始想用遞歸，但是這樣不好確定哈夫曼各個節(jié)點在屏幕上相應的位置。其實我們上學期也寫過以凹凸表形式打印二叉樹的一個程序，但那個程序里的二叉樹是以二叉鏈表的形式儲存的，而本程序的哈夫曼樹（二叉樹的一種）是以數(shù)組形式儲存的，一開始我以為那個程序的方法在本程序中不適用。后來因為想不到其它方法，就考慮能否用那個程序的方法放在本程序中使用。結果發(fā)現(xiàn)，我只改動了少許地方就可以了。從這一點上我認識到，二叉樹是以什么方式儲存的不重要，最

64、重要的是對二叉樹的一些操作對于不同儲存類型的二叉樹是普遍通用的。</p><p>　　另外，因為未學扎實，程序中還有至少兩個未解決的問題。這在“調(diào)試分析”中提到過。這兩個問題通過其它的一些措施可以避免錯誤的運行，但終究是沒有徹底解決，需在課程設計被檢查完以后，再花些時間搞懂?？傊?，通過此次的課程設計，我又復習了一遍二叉樹、棧等數(shù)據(jù)結構里的知識點，加深了對它們的理解，對使用這些數(shù)據(jù)結構更加熟練了；又重新略看了一遍《