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

哈夫曼編碼與解碼的實現(xiàn)

一、設(shè)計思想

(一)哈夫曼樹的設(shè)計思想

對于一組具有確定權(quán)值的葉子結(jié)點可以構(gòu)造出多個具有不同帶權(quán)路徑長度的二叉樹，其中具有最小帶權(quán)路徑長度的二叉樹稱作哈夫曼樹或最優(yōu)二叉樹。

首先給定n個權(quán)值制造n個只含根結(jié)點的二叉樹，得到一個二叉樹林；再在這二叉樹林里面找根結(jié)點的權(quán)值最小和次小的兩棵樹作成新的二叉樹，其中新的二叉樹的根結(jié)點的權(quán)值為左右子根結(jié)點權(quán)值之和；最后在二叉樹林中把組合過的二叉樹刪除，再重復(fù)第二步，直到最后就剩一顆二叉樹的時候得到的這棵二叉樹就是哈夫曼樹。

（二）哈夫曼編碼與解碼的設(shè)計思想

在數(shù)據(jù)通訊中，經(jīng)常要將傳送的文字轉(zhuǎn)換為二進制字符0和1組成的二進制串，稱這個過程為編碼。與子相對的是解碼或是譯碼，就是用與編碼相同的方式將二進制串轉(zhuǎn)換稱編碼前的文字的過程稱作解碼。在這里是通過哈夫曼樹實現(xiàn)編碼與解碼的，所以稱作是哈夫曼編碼與解碼。

首先輸入一個字符串，還有相應(yīng)的在哈夫曼樹里的權(quán)值，這樣用哈夫曼樹把字符串用二進制串代替它，這個過程要注意樹和編碼問題，其中樹的問題在上面已經(jīng)解決，主要看編碼的問題，就是根據(jù)我們輸入的字符串和權(quán)值建立相應(yīng)的樹模型，這一步完成那編碼就已經(jīng)完成了，最后打印就行了；然后就是解碼，完成編碼相應(yīng)的解碼就相對簡單了，就是先找到在編碼的時候建的那個模型樹，將編碼中的二進制串再根據(jù)權(quán)值轉(zhuǎn)換為相應(yīng)的字符串，這樣一步步解碼就行了。

以上就是通過用哈夫曼樹進行哈夫曼編碼與解碼如何實現(xiàn)的主要設(shè)計思想。

哈夫曼編碼與解碼的實現(xiàn)

for(i=n+1;i<=2*n-1;i++)

{

s1=s2=10000;

x1=x2=0;

for(j=1;j<=i-1;j++)

{

if(myHaffTree[j].parent==0&&myHaffTree[j].weight

{

s2=s1;x2=x1;

s1=myHaffTree[j].weight;x1=j;

}

else if(myHaffTree[j].parent==0&&myHaffTree[j].weight

{

s2=myHaffTree[j].weight;x2=j;

}

}

myHaffTree[x1].parent=i;

myHaffTree[x2].parent=i;

myHaffTree[i].weight=s1+s2;

myHaffTree[i].lchild=x1;

myHaffTree[i].rchild=x2;

} } void HaffmanCode(int n){ int start,c,f,i,j,k;char *cd;cd=(char *)malloc(n*sizeof(char));myHaffCode=(struct Coding *)malloc((n+1)*sizeof(struct Coding));cd[n-1]='