《數(shù)據(jù)結(jié)構(gòu) 哈夫曼編碼的報(bào)告》

1、一、設(shè)計(jì)思想首先規(guī)定構(gòu)建哈夫曼樹，再去進(jìn)行哈夫曼的譯碼，接著設(shè)計(jì)函數(shù)進(jìn)行字符 串的編碼過(guò)程，最后進(jìn)行哈夫曼編碼的譯碼。定義一個(gè)結(jié)構(gòu)體，用于存放構(gòu)建哈夫曼樹所需要的所有變量，開(kāi)辟一塊地 址空間，用于存放數(shù)組，數(shù)組中每個(gè)元素為之前定義的結(jié)構(gòu)體。輸入n個(gè)字符 及其權(quán)值。構(gòu)建哈夫曼樹：在上述存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的哈夫曼算法可大致描述為：1、初始化。將ht0. m-1中2n-1個(gè)結(jié)點(diǎn)里的三個(gè)指針均置為空，權(quán)值 置為0。2、輸入。讀入n個(gè)葉子的權(quán)值存于向量的前n個(gè)分量中。它們是初始森 林中n個(gè)孤立的根結(jié)點(diǎn)上的權(quán)值。3、合并。對(duì)森林中的樹共進(jìn)行n-1次合并，所產(chǎn)生的新結(jié)點(diǎn)依次放入向量 ht的第i個(gè)分量中。每次合并

2、分兩步：在當(dāng)前森林ht0. i-1的所有結(jié)點(diǎn)中，選取權(quán)最小和次小的兩個(gè)根結(jié)點(diǎn) s1和s2作為合并對(duì)象，這里0Ms1，s2i-10將根為hts1和hts2的兩棵樹作為左右子樹合并為一棵新的樹，新樹的 根是新結(jié)點(diǎn)hti具體操作：將 hts1和 hts2的 parent 置為 i，將hti的Ichild和rchild分別置為s1和s2新結(jié)點(diǎn)hti的權(quán)值置為hts1和hts2的權(quán)值之和。哈夫曼的編碼：約定左子為0，右子為1，則可以從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路 徑上的字符組成的字符串作為該葉子結(jié)點(diǎn)的編碼。當(dāng)用戶輸入字母時(shí)。就在已經(jīng)找好編碼的編碼結(jié)構(gòu)體中去查找該字母。查 到該字母就打印所存的哈夫曼編碼。接著就是

3、完成用戶輸入0、1代碼時(shí)把代碼 轉(zhuǎn)成字母的功能。這是從樹的頭結(jié)點(diǎn)向下查找，如果當(dāng)前用戶輸入的0、1串中 是0則就走向該結(jié)點(diǎn)的左子。如果是1這就走向該結(jié)點(diǎn)的右結(jié)點(diǎn)，重復(fù)上面步 驟。直到發(fā)現(xiàn)該結(jié)點(diǎn)屬于輸入了字母的結(jié)構(gòu)體則打印該結(jié)構(gòu)體的字母。重復(fù)上 面步驟。直到找完用戶輸入0、1串為止。則就完成了程序所有的譯碼過(guò)程。二、算法流程圖建立哈夫曼樹的算法：定義各結(jié)點(diǎn)類型其中應(yīng)包含兩類數(shù)據(jù)一是權(quán)重域weight； 一是應(yīng)該包括指 向左右孩子和指向雙親的指針這里分別用lchild、rchild和parent來(lái)表示，因此 可用靜態(tài)三叉鏈表來(lái)實(shí)現(xiàn)。在實(shí)際構(gòu)造中由于是葉子結(jié)點(diǎn)來(lái)構(gòu)造新的根結(jié)點(diǎn)其 構(gòu)造過(guò)程中僅與葉子結(jié)

4、點(diǎn)的權(quán)重有關(guān)而與其數(shù)據(jù)域無(wú)關(guān)，所以構(gòu)造過(guò)程中不用 考慮其數(shù)值域，并且在鏈表中從葉子開(kāi)始存放，然后不斷的將兩個(gè)最小權(quán)值的 子樹合并為一個(gè)權(quán)值為其和的較大的子樹，逐步生成各自內(nèi)部結(jié)點(diǎn)直到樹根。圖1構(gòu)建哈夫曼樹圖編碼的算法將建立的哈夫曼樹從每個(gè)葉子結(jié)點(diǎn)開(kāi)始沿著雙親回到根結(jié)點(diǎn)，每走一步進(jìn) 行編碼得到的一個(gè)編碼值，由于每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng) 的葉子的路徑的各個(gè)分支的代碼組成的0和1序列，所以先得到了低位編碼后 得到高位編碼因此可用一維數(shù)組從后向前來(lái)存放各位編碼值，并用start來(lái)記 錄編碼的起始位置。圖2哈夫曼編碼圖哈夫曼編碼。當(dāng)我們輸入一些字符串，進(jìn)行哈夫曼編碼，然后輸出0、1代碼。

5、輸入字符以回車結(jié)束c=nStingi=htc.datj=n圖3哈夫曼編碼NYj=dcc.startI結(jié)束i=0開(kāi)始C=0C+輸出代碼j+輸出字符串。四、哈夫曼譯碼當(dāng)我們輸入哈夫曼01代碼時(shí)進(jìn)行譯碼過(guò)程，三、源代碼#include #include 數(shù)組頭文件#include#define MAX 999/宏定義typedef struct/定義哈夫曼編碼的結(jié)構(gòu)數(shù)組char data;int weight;/定義權(quán)值int parent;int lchild;int rchild;huffmannode;typedef struct/定義保存哈夫曼結(jié)構(gòu)體char bits50;int start

6、;huffmancode ;void main()huffmannode ht100;/定義儲(chǔ)存權(quán)值的空間huffmancode cd100;char string100;定義數(shù)組存儲(chǔ)空間char hcd100;int i,j,x,y,s1,s2,m1,m2,n,c,f,k;printf(please input the n=);輸入字符的個(gè)數(shù)scanf(%d”,&n);printf(n=n);for(i=0;in;i+)getchar();/獲得輸入的字符printf(please input the value :);scanf(%c”,&hti.data);/輸入字符函數(shù)printf(p

7、lease input the weight:);scanf(%d”,&hti.weight);printf(n=n);for(i=0;i2*n-1;i+)hti.parent=hti.lchild=hti.rchild=-1; /初始化父結(jié)點(diǎn)，左右子結(jié)點(diǎn)for (i=n;i2*n-1;i+)s1=s2=0;初始化變量m1=m2=MAX;for (j=0;ji;j+) if (htj.weightm1 &htj.parent=-1) /尋找無(wú)父結(jié)點(diǎn)的最小值m2=m1;s2=s1;m1=htj.weight;s1=j;尋找當(dāng)前最小值else if(htj.weightm2 &htj.parent

8、=-1) /尋找無(wú)父結(jié)點(diǎn)的次小值m2=htj.weight;s2=j;尋找次小值/s1的父結(jié)點(diǎn)為i/最小值的權(quán)值相加為i的權(quán)值/i的左子為si/i的右子為s2hts1.parent=i;hts2.parent=i;hti.weight=m1+m2;hti.lchild=s1;hti.rchild=s2;for(i=0;in;i+)cdi.start=n;x=i;y=htx.parent;記錄父結(jié)點(diǎn)while (y!=-1) if (hty.lchild=x)cdi.bitscdi.start=0;給字符賦 0 值elsecdi.bitscdi.start=1;/給字符賦 1 值cdi.star

9、t-; x=y;y=hty.parent;printf(nout the huffmancode:n);for (i=0;in;i+)printf(%c:,hti.data);輸出字符for(j=cdi.start;j=n;j+)printf(%c”,cdi.bitsj);輸出字符的 01 代碼printf(n);printf(n=n);printf(nPlease input the message:n);scanf(%s”,string);輸入字符串for(i=0;stringi!=0;i+)for(c=0;c=n;c+)if(stringi=htc.data) /尋找與輸入字符相匹配的字

10、母for(j=cdc.start;j=n;j+)printf(%c”,cdc.bitsj); /輸出字母代碼 break;printf(n=n);printf(Please input the HuffmanCode:n);scanf(%s”,hcd);輸入 0、1 代碼f=2*n-2;for(i=0;hcdi!=0;i+)if(hcdi=0)判斷輸入為0，尋找左子f=htf.lchild;else if(hcdi=1)f=htf.rchild;/判斷輸入為1，尋找右子if(fn) printf(%c”,htf.data);輸出字符串f=2*n-2;printf(n);getch();四、運(yùn)行

11、結(jié)果第一步，運(yùn)行程序，首先規(guī)定結(jié)點(diǎn)個(gè)數(shù)n=8回車，其次我們輸入每個(gè)結(jié)點(diǎn) 的字符及每個(gè)結(jié)點(diǎn)對(duì)應(yīng)的權(quán)值，得如圖2。蜃 C:U5ersXDe5ktopluanbi3n.exeplease input the n=8please please please please please please please please please please please please please please pleaseinput input input input input input input input input input input input input input inputual

12、ue weight value weight value weight ualue weight ualue weight value weight value weight第二thethethethethethethethethethethethethethe y圖5字符與權(quán)值的輸入運(yùn)行結(jié)果圖步，單擊回車得到每個(gè)葉子結(jié)點(diǎn)的編碼，如圖3。s12d33 f58z8799c120昴 C:Use rsXD esktopl dd n bia n .exepleasepleasepleasepleasepleasepleasepleaseinput input input input input inp

13、ut inputthe weight:87 the value ;x the weight；:99 the value ic the weight:120 the value :q the weight:4560 0 01_0 0 _0 _0 0 -1 1111001 00000001 tu oasdfzxcQthe huffmancode:圖6葉子結(jié)點(diǎn)編碼圖第三步，得到huffmancode后我們輸入字符進(jìn)行哈夫曼編碼，如圖4。圖7字符的編碼圖第五步，的到哈夫曼編碼后輸入哈夫曼編碼進(jìn)行譯碼過(guò)程。Please input the message:010000 010001 010001 010

14、01 000 001 011 011 011 011 01001 010001 010000 010000 0 10001 1111 010000 000 001 010000 010001 01001 0101 0101 0101 0101 010001 0100 1 010000 000 001 1 0101Please input the HuffmanCode:010000010001000000000011011011001001001111111110101010101010101010001010001010000010000aszzzcccxxxqqqqqqqqffffssaa

15、圖8哈夫曼編碼的譯碼圖五、遇到的問(wèn)題及解決這部分我主要遇到了如下問(wèn)題，其內(nèi)容與解決方法如下所列：怎樣去構(gòu)建哈夫曼樹？解決方案：經(jīng)過(guò)查詢資料，請(qǐng)教別人得到如下幾條結(jié)論Q構(gòu)成初始集合。 對(duì)給定的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)，它的左右子樹均為空。（為方便在計(jì)算機(jī)上實(shí)現(xiàn)算法，一般還要 求以Ti的權(quán)值Wi的升序排列。）Q選取左右子樹。在F中選取兩棵根結(jié)點(diǎn)權(quán) 值最小的樹作為新構(gòu)造的二叉樹的左右子樹，新二叉樹的根結(jié)點(diǎn)的權(quán)值為 其左右子樹的根結(jié)點(diǎn)的權(quán)值之和。3刪除左右子樹。從F中

16、刪除這兩棵樹， 并把這棵新的二叉樹同樣以升序排列加入到集合F中。Q重復(fù)二和三兩步。重復(fù)二和三兩步，直到集合F中只有一棵二叉樹為止。在進(jìn)行哈夫曼樹的構(gòu)建，以及字符的編碼與譯碼過(guò)程中c程序的調(diào)試。解決方案：在此次c的編程中遇到了很多語(yǔ)句賦值的錯(cuò)誤，還有 for語(yǔ) 句使用的不熟練，以及自己的粗心而造成的標(biāo)點(diǎn)符號(hào)使用錯(cuò)誤，宏語(yǔ)句的 定義等等，主要的解決方案是，看一些關(guān)于c語(yǔ)言編程的書籍，請(qǐng)教其他同 學(xué)，使得編譯成功自己的程序。六、心得體會(huì)通過(guò)本次數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，我學(xué)習(xí)了很多在上課沒(méi)懂的知識(shí)，并對(duì)求哈夫 曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān) 于哈夫曼編碼的知識(shí)，真正學(xué)會(huì)一種算法了。當(dāng)求解一個(gè)算法時(shí)，不是拿到問(wèn)題 就不加思索地做，而是首先要先對(duì)它有個(gè)大概的了解，接著再詳細(xì)地分析每一 步怎么做，無(wú)論自己以前是否有處理過(guò)相似的問(wèn)題，只要按照以上的步驟，必 定會(huì)順利地做出來(lái)。通過(guò)編程，應(yīng)使我掌握哈夫曼編碼的特點(diǎn)、存儲(chǔ)方法和基本原理，培養(yǎng)學(xué) 生運(yùn)用C語(yǔ)言正確編程及調(diào)試的能力，運(yùn)用數(shù)據(jù)結(jié)構(gòu)解