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

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

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

3、夫曼編碼是前綴碼，所以所有要編碼的字符最終都將是這顆樹的葉子節(jié)點(diǎn)，而其它節(jié)點(diǎn)并沒有真正的字符意義。即當(dāng)哈夫曼編碼樹建立之后，對樹的所有葉子節(jié)點(diǎn)進(jìn)行打印可知道是否有字符遺漏或多余。1.2建立哈夫曼編碼表。建立編碼表時(shí)要根據(jù)每個(gè)出現(xiàn)的字符的權(quán)重對建立的哈夫曼樹的每個(gè)葉子節(jié)點(diǎn)進(jìn)行編碼。編碼時(shí)要從葉子節(jié)點(diǎn)出發(fā)向根節(jié)點(diǎn)進(jìn)行逆向編碼。判斷如果當(dāng)前節(jié)點(diǎn)為左子則對其編碼0，如果當(dāng)前節(jié)點(diǎn)為右子則對其編碼1。以此類推進(jìn)行編碼直到根節(jié)點(diǎn)為止。此時(shí)的編碼是逆向的，所以需要將碼值逆向存儲(chǔ)。依次對每一個(gè)葉子節(jié)點(diǎn)進(jìn)行編碼操作，即可得到當(dāng)前哈夫曼樹的編碼表。對于碼值的逆向存儲(chǔ)可以使用棧結(jié)構(gòu)，先將一個(gè)碼的每一步編碼存入棧，再在

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

5、后得到的密文內(nèi)容存儲(chǔ)到字符串中以便解碼調(diào)用。開始對密文的字符串進(jìn)行解碼，樹索引從根節(jié)點(diǎn)開始走，當(dāng)密文中的當(dāng)前字符是0的時(shí)候，則索引走向左子節(jié)點(diǎn)；當(dāng)是1的時(shí)候，則走向右子節(jié)點(diǎn)。以此類推，一直走到葉子節(jié)點(diǎn)為止，則當(dāng)前葉子節(jié)點(diǎn)所代表的字符即為前一段密文的解碼結(jié)果，。再對下一個(gè)字符依次從根節(jié)點(diǎn)開始解碼，如此循環(huán)對每一段密文進(jìn)行解碼直到解碼結(jié)束。將解碼打印到屏幕，并將解碼結(jié)果存入到新的解碼文件當(dāng)中。在解碼之前，還應(yīng)該先確認(rèn)之前是否建立了哈夫曼樹并且是否構(gòu)建了編碼表。不過由于本次將a到z都進(jìn)行了編碼，所以此步省略了，因?yàn)榫幋a表是唯一的。需要的時(shí)候可以在Encoder 函數(shù)中先進(jìn)行判定。將編碼和解碼寫在了一

6、起，可以在運(yùn)行時(shí)進(jìn)行選擇調(diào)用。二、算法流程圖第一步：建立哈夫曼樹。圖1建立哈夫曼樹的算法流程圖第二步：構(gòu)建哈夫曼編碼表。圖2構(gòu)建哈夫曼編碼表的算法流程圖第三步：編碼。圖3 編碼算法流程圖第四步：解碼。圖4 解碼算法流程圖四、運(yùn)行結(jié)果原文文件：圖5 中綴轉(zhuǎn)后綴運(yùn)行結(jié)果圖編碼圖：圖6 編碼圖密文文件：圖7 密文文件圖解碼圖：圖8 解碼圖譯文文件：圖9 譯文文件圖整體運(yùn)行圖：圖10 編碼解碼整體運(yùn)行圖五、遇到的問題及解決這部分我主要遇到了如下兩個(gè)問題，其內(nèi)容與解決方法如下所列： 第一個(gè)問題是權(quán)重的篩選部分出現(xiàn)了錯(cuò)誤解決辦法：一開始對于篩選最小權(quán)重的代碼編寫如下：void SelectMin(HFMT

7、 T,int i,int *p1,int *p2 int j, min=999;for(j=0;j if(Tj.parent=-1&&min>Tj.weightmin=Tj.weight; *p1=j; min=999; for(j=0;j if(Tj.parent=-1&&min>Tj.weight&&j!=(*p1min=Tj.weight; *p2=j; 因?yàn)闄?quán)重中最大的就是字符e的權(quán)重103，所以為初始值min賦值時(shí)覺得999就已經(jīng)是無限大了。但是后來發(fā)現(xiàn)編碼不知確，就開始思考是什么問題。發(fā)現(xiàn)每次篩選都將會(huì)把最小的兩個(gè)權(quán)重進(jìn)行

8、相加，所以很快就會(huì)超過999，編碼自然就出現(xiàn)了問題。所以后來將min定義成了long型，并賦值999999，問題就解決了。 第二個(gè)問題是生成編碼表的時(shí)候如何將逆向編碼正向存儲(chǔ)解決辦法：對于求編碼的時(shí)候，由于是從葉子節(jié)點(diǎn)向根順次而求，所以編碼結(jié)果將是逆向的。一開始想到的辦法是利用棧的結(jié)構(gòu)，將編碼依次存入棧中，再在一個(gè)字符編碼結(jié)束時(shí)將棧倒空，這樣就可以將編碼正向存儲(chǔ)了。但是又在考慮如果不用棧時(shí)候也可以做到。后來想到了strcpy函數(shù)對字符數(shù)組進(jìn)行鏈接。所以就可以定義一個(gè)數(shù)組，從后向前存儲(chǔ)編碼，再在一個(gè)字符編碼結(jié)束時(shí)將這個(gè)數(shù)組有值的重新存入新數(shù)組中，即可以成為正向編碼了。最終實(shí)現(xiàn)編碼如下：HFCod

9、e hfEn(HFMT T int i,f,c,start;HFCode hc;char *cd;hc=(char *malloc(N+1*sizeof(char*; cd=(charmalloc(N*sizeof(char; cdN-1='0' for(i=0;i start=N-1;for(c=i,f=Ti.parent;f!=-1;c=f,f=Tf.parentif(Tf.left=c cd-start='0'else cd-start='1'hci=(char *malloc(N-start*sizeof(char; strcpy(hci,&cdstart; return hc;六、心得體會(huì)通過對本次的編寫，使我掌握了哈夫曼編碼的特點(diǎn)、存儲(chǔ)方法和基本原理，培養(yǎng)了我運(yùn)用C語言正確編寫程序以及調(diào)試程序的能力。哈夫曼編碼的結(jié)構(gòu)取決于可能出現(xiàn)的字符的個(gè)數(shù)和其所對應(yīng)的權(quán)值，權(quán)值大的編碼短，權(quán)值小的編碼長。這樣的結(jié)構(gòu)會(huì)利用比較小的空間存儲(chǔ)數(shù)據(jù)。而且，利用樹的結(jié)構(gòu)對其編碼和對其解碼，也是比較規(guī)格話，比較方便的。本次編程還運(yùn)用了結(jié)構(gòu)體，便捷的對樹節(jié)點(diǎn)和樹以及編碼表進(jìn)行定義和調(diào)用。并且了解到當(dāng)求解一個(gè)算法時(shí)，不是拿到問題就不假思索去做，而