數(shù)據(jù)結(jié)構(gòu)C語言哈夫曼編碼譯碼

1、哈夫曼的編碼與解碼叛據(jù)結(jié)物實訓(xùn)報告題目:哈夫曼樹編碼譯碼院系：信息工程系專業(yè)：計算機科學(xué)與技術(shù)（網(wǎng)絡(luò)方向）姓名：梁展榮學(xué)號：1151220115指導(dǎo)教師：趙瑩瑩劉欣日期：2013年7月3日桂林電子科技大學(xué)信息科技學(xué)院-9 -一、設(shè)計思想錯誤！未定義書簽1.1 建立哈夫曼樹的思想 錯誤！未定義書簽1.2建立哈夫曼編碼表錯誤！未定義書簽1.3對文件進行編碼.1.4對文件進行解碼.二、算法流程圖三、運行結(jié)果四、遇到的問題及解決.五、心得體會223810錯誤！未定義書簽。一、設(shè)計思想要完成哈夫曼的編碼和解碼需要首先建立哈夫曼樹，之后對所有 字符根據(jù)權(quán)重進行編碼，最后再對文件內(nèi)容進行編碼和解碼。1.1建

2、立哈夫曼樹的思想。首先定義適合哈夫曼樹的節(jié)點類型，需要定義的有當(dāng)前節(jié)點的字 符，當(dāng)前節(jié)點的左子、右子和父親指針。在建立哈夫曼樹之前還需要 對出現(xiàn)的字符和權(quán)重進行統(tǒng)計和記錄，并且定義一個可以篩選出最小 權(quán)重的函數(shù)。初始化樹節(jié)點之后開始建立哈夫曼樹。先在所有可能出現(xiàn)的字符 中篩選出當(dāng)前權(quán)重最小的兩個字符，將這兩個字符分別作為新節(jié)點的 左子和右子建立一個小的二叉樹，并將兩個字符的權(quán)重之和賦值給新 節(jié)點，將新二叉樹放入篩選字符中，再將篩選過的兩個字符從篩選列 表中淘汰掉。依次對列表中剩下的字符進行權(quán)重最小的篩選，直到根節(jié)點（如果編碼表共有N個字符，則2*N-1就為最終根節(jié)點）為止， 也就是當(dāng)篩選列表為

3、空的時候，哈夫曼樹即建立完成。對于哈夫曼編碼樹來說，由于哈夫曼編碼是前綴碼，所以所有要 編碼的字符最終都將是這顆樹的葉子節(jié)點， 而其它節(jié)點并沒有真正的 字符意義。即當(dāng)哈夫曼編碼樹建立之后，對樹的所有葉子節(jié)點進行打 印可知道是否有字符遺漏或多余。1.2建立哈夫曼編碼表建立編碼表時要根據(jù)每個出現(xiàn)的字符的權(quán)重對建立的哈夫曼樹 的每個葉子節(jié)點進行編碼。編碼時要從葉子節(jié)點出發(fā)向根節(jié)點進行逆 向編碼。判斷如果當(dāng)前節(jié)點為左子則對其編碼 0'，如果當(dāng)前節(jié)點為 右子則對其編碼 1'。以此類推進行編碼直到根節(jié)點為止。此時的編 碼是逆向的，所以需要將碼值逆向存儲。依次對每一個葉子節(jié)點進行 編碼操作，

4、即可得到當(dāng)前哈夫曼樹的編碼表。對于碼值的逆向存儲可以使用棧結(jié)構(gòu)，先將一個碼的每一步編碼 存入棧，再在一個碼結(jié)束后出棧至空。當(dāng)然也可以定義一個字符型數(shù) 組，將值從后向前存入數(shù)組，再將數(shù)組有值部分粘貼到新的數(shù)組中進 行存儲。本次采用了后者，因為個人認(rèn)為為此一步操作建立棧結(jié)構(gòu)不 劃算，而且前一個設(shè)計也已經(jīng)熟練掌握了棧的方法， 此處進行新的嘗 試會更好。1.3對文件進行編碼。首先需要建立一個原始文件，在文件中輸入需要編碼的內(nèi)容。之 后將文件打開，將其中的內(nèi)容存儲到字符串中以便程序編碼調(diào)用。開始對需要編碼的字符進行編碼，將字符逐一讀取與剛剛建立的編碼表 中的每個葉子節(jié)點代表的字符進行比較， 找出相同的對

5、象，并將當(dāng)前 節(jié)點的編碼打印到屏幕，并將編碼存入到新建的密碼文件當(dāng)中。1.4對文件進行解碼。先打開密碼文件，將之前編碼后得到的密文內(nèi)容存儲到字符串中 以便解碼調(diào)用。開始對密文的字符串進行解碼，樹索引從根節(jié)點開始 走，當(dāng)密文中的當(dāng)前字符是 0'的時候，則索引走向左子節(jié)點；當(dāng)是 1'的時候，則走向右子節(jié)點。以此類推，一直走到葉子節(jié)點為 止，則當(dāng)前葉子節(jié)點所代表的字符即為前一段密文的解碼結(jié)果，。再對下一個字符依次從根節(jié)點開始解碼，如此循環(huán)對每一段密文進行解 碼直到解碼結(jié)束。將解碼打印到屏幕，并將解碼結(jié)果存入到新的解碼 文件當(dāng)中。在解碼之前，還應(yīng)該先確認(rèn)之前是否建立了哈夫曼樹并且是否構(gòu)

6、 建了編碼表。不過由于本次將 a到z'都進行了編碼，所以此步 省略了，因為編碼表是唯一的。需要的時候可以在Encoder函數(shù)中先 進行判定。將編碼和解碼寫在了一起，可以在運行時進行選擇調(diào)用。二、算法流程圖第一步：建立哈夫曼樹。圖1建立哈夫曼樹的算法流程圖第二步：構(gòu)建哈夫曼編碼表圖2構(gòu)建哈夫曼編碼表的算法流程圖第二步：編碼第四步：解碼圖3編碼算法流程圖圖4解碼算法流程圖哈夫曼的編碼與解碼-ii -四、運行結(jié)果原文文件:圖5中綴轉(zhuǎn)后綴運行結(jié)果圖編碼圖:圖6編碼圖密文文件:文件（B窓略式 聶凹幫助凹CODEFILE-iB事忝The Huffman Code is:11110001100000

7、11010100000110101100010000100001111011111011111010110010010101111001001101111110001100000110101000001101011000100001000011110111110111110101100100101011110010011011圖7密文文件圖解碼圖:The Text is:this a huffman tree=Decoder Over' =圖8解碼圖譯文文件:圖9譯文文件圖1. Encoder2. Decoder3. Exit整體運行圖:=;直 C：'.B - -. =71-

8、l'Z: - i?' .1 fL tic r=Encoder Begain= The Original is:this is a huffman treeThe Huffman code is:11110001100000110101000001101011000100001000011110111110111110101100100101011110010011011=e n c ode r Ove r=:De c ode r Bug a 1 nThe Huffman Code is:1111000110000011010100000110101100010000100001

9、1110111110111110101100100101011110 010011011The Text is:this is a huffman tree =D亡tocj亡r over圖10編碼解碼整體運行圖五、遇到的問題及解決這部分我主要遇到了如下兩個問題，其內(nèi)容與解決方法如下所列：第一個問題是權(quán)重的篩選部分出現(xiàn)了錯誤解決辦法：一開始對于篩選最小權(quán)重的代碼編寫如下：void SelectMin(HFMT T,int i,int *p1,int *p2)int j, min=999;for(j=0;j<i;j+)if(Tj.pare nt=-1 &&mi n>Tj

10、.weight)哈夫曼的編碼與解碼min二 Tj.weight;*p1=j；min=999;for(j=0;j<i;j+)if(Tj.pare nt=-1 &&mi n>Tj.weight&&j!=(*p1)min二 Tj.weight;*p2=j;因為權(quán)重中最大的就是字符e的權(quán)重103,所以為初始值min賦 值時覺得999就已經(jīng)是無限大了。但是后來發(fā)現(xiàn)編碼不知確，就開始 思考是什么問題。發(fā)現(xiàn)每次篩選都將會把最小的兩個權(quán)重進行相加， 所以很快就會超過999，編碼自然就出現(xiàn)了問題。所以后來將min定義成了 long型，并賦值999999,問題就解決了。

11、第二個問題是生成編碼表的時候如何將逆向編碼正向存儲解決辦法:對于求編碼的時候，由于是從葉子節(jié)點向根順次而求，所以編碼 結(jié)果將是逆向的。一開始想到的辦法是利用棧的結(jié)構(gòu)， 將編碼依次存 入棧中，再在一個字符編碼結(jié)束時將棧倒空， 這樣就可以將編碼正向 存儲了。但是又在考慮如果不用棧時候也可以做到。后來想到了 strcpy函數(shù)對字符數(shù)組進行鏈接。所以就可以定義一 個數(shù)組，從后向前存儲編碼，再在一個字符編碼結(jié)束時將這個數(shù)組有 值的重新存入新數(shù)組中，即可以成為正向編碼了。最終實現(xiàn)編碼如下：HFCode hfEn( HFMT T)int i,f,c,start;HFCode hc;char *cd;hc=(

12、char *)malloc(N+1)*sizeof(char*);cd=(char)malloc(N*sizeof(char);cdN-1='0：for(i=0;i<N;i+)start=N-1;for(c=i,f=Ti.pare nt;f!=-1;c二f,f=Tf.pare nt)if(Tf.left=c)cd-start='O：elsecd-start='1'hci=(char *)malloc(N-start)*sizeof(char);strcpy(hci,&cdstart);return hc;六、心得體會通過對本次的編寫，使我掌握了哈夫曼編碼的特點、存儲方法和 基本原理，培養(yǎng)了我運用C語言正確編寫程序以及調(diào)試程序的能力。哈夫曼編碼的結(jié)構(gòu)取決于可能出現(xiàn)的字符的個數(shù)和其所對應(yīng)的權(quán)值， 權(quán)值大的編碼短，權(quán)值小的編碼長。這樣的結(jié)構(gòu)會利用比較小的空間 存儲數(shù)據(jù)。而且，利用樹的結(jié)構(gòu)對其編碼和對其解碼，也是比較規(guī)格 話，比較方便的。本次編程還運用了結(jié)構(gòu)體，便捷的對樹節(jié)點和樹以 及編碼表進行定義和調(diào)