數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)之哈夫曼編碼

1、哈夫曼編碼與解碼的實(shí)現(xiàn)1一、設(shè)計(jì)思想一、設(shè)計(jì)思想(一)哈夫曼樹的設(shè)計(jì)思想對(duì)于一組具有確定權(quán)值的葉子結(jié)點(diǎn)可以構(gòu)造出多個(gè)具有不同帶權(quán)路徑長度的二叉樹，其中具有最小帶權(quán)路徑長度的二叉樹稱作哈夫曼樹或最優(yōu)二叉樹。首先給定n個(gè)權(quán)值制造n個(gè)只含根結(jié)點(diǎn)的二叉樹，得到一個(gè)二叉樹林；再在這二叉樹林里面找根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵樹作成新的二叉樹，其中新的二叉樹的根結(jié)點(diǎn)的權(quán)值為左右子根結(jié)點(diǎn)權(quán)值之和；最后在二叉樹林中把組合過的二叉樹刪除，再重復(fù)第二步，直到

2、最后就剩一顆二叉樹的時(shí)候得到的這棵二叉樹就是哈夫曼樹。（二）哈夫曼編碼與解碼的設(shè)計(jì)思想在數(shù)據(jù)通訊中，經(jīng)常要將傳送的文字轉(zhuǎn)換為二進(jìn)制字符0和1組成的二進(jìn)制串，稱這個(gè)過程為編碼。與子相對(duì)的是解碼或是譯碼，就是用與編碼相同的方式將二進(jìn)制串轉(zhuǎn)換稱編碼前的文字的過程稱作解碼。在這里是通過哈夫曼樹實(shí)現(xiàn)編碼與解碼的，所以稱作是哈夫曼編碼與解碼。首先輸入一個(gè)字符串，還有相應(yīng)的在哈夫曼樹里的權(quán)值，這樣用哈夫曼樹把字符串用二進(jìn)制串代替它，這個(gè)過程要注意樹和

3、編碼問題，其中樹的問題在上面已經(jīng)解決，主要看編碼的問題，就是根據(jù)我們輸入的字符串和權(quán)值建立相應(yīng)的樹模型，這一步完成那編碼就已經(jīng)完成了，最后打印就行了；然后就是解碼，完成編碼相應(yīng)的解碼就相對(duì)簡單了，就是先找到在編碼的時(shí)候建的那個(gè)模型樹，將編碼中的二進(jìn)制串再根據(jù)權(quán)值轉(zhuǎn)換為相應(yīng)的字符串，這樣一步步解碼就行了。以上就是通過用哈夫曼樹進(jìn)行哈夫曼編碼與解碼如何實(shí)現(xiàn)的主要設(shè)計(jì)思想。哈夫曼編碼與解碼的實(shí)現(xiàn)3三、源代碼三、源代碼下面給出的是用中綴轉(zhuǎn)后綴算

4、法實(shí)現(xiàn)的程序的源代碼：#include“stdio.h“#include“string.h“#defineMAX100定義常量structHaffNodeintweight權(quán)值intparent雙親結(jié)點(diǎn)下標(biāo)chintlchildintrchildmyHaffTree構(gòu)造哈夫曼樹structCodingbit[MAX]定義數(shù)組chintweight字符的權(quán)值myHaffCode定義結(jié)構(gòu)體voidHaffman(intn)定義哈夫曼函數(shù)in

5、tijx1x2s1s2f(i=n1i=2n1i)樹的初始化s1=s2=10000x1=x2=0f(j=1j=i1j)構(gòu)造哈夫曼樹的非葉子結(jié)點(diǎn)if(myHaffTree[j].parent==0x2=x1s1=myHaffTree[j].weightx1=jelseif(myHaffTree[j].parent==0x2=jmyHaffTree[x1].parent=imyHaffTree[x2].parent=imyHaffTree[i