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

1、精選文檔一、設(shè)計思想（一） 哈夫曼樹的設(shè)計思想對于一組具有確定權(quán)值的葉子結(jié)點(diǎn)可以構(gòu)造出多個具有不同帶權(quán)路徑長度的二叉樹， 其中具有最小帶權(quán)路徑長度的二叉樹稱作哈夫曼樹或最優(yōu)二叉樹。首先給定 n 個權(quán)值制造 n 個只含根結(jié)點(diǎn)的二叉樹，得到一個二叉樹林；再在這二叉樹林里面找根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵樹作成新的二叉樹， 其中新的二叉樹的根結(jié)點(diǎn)的權(quán)值為左右子根結(jié)點(diǎn)權(quán)值之和； 最后在二叉樹林中把組合過的二叉樹刪除， 再重復(fù)第二步， 直到最后就剩一顆二叉樹的時候得到的這棵二叉樹就是哈夫曼樹。（二）哈夫曼編碼與解碼的設(shè)計思想在數(shù)據(jù)通訊中，經(jīng)常要將傳送的文字轉(zhuǎn)換為二進(jìn)制字符0 和 1 組成的二進(jìn)制串，稱這個

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

3、步解碼就行了?？删庉嬕陨暇褪峭ㄟ^用哈夫曼樹進(jìn)行哈夫曼編碼與解碼如何實(shí)現(xiàn)的主要設(shè)計思想。二、算法流程圖（一）哈夫曼樹的流程圖不 是圖1哈夫曼樹的流程圖（二）編碼的流程圖（三）解碼的流程圖三、源代碼找到樹的根結(jié)點(diǎn) 輸入二進(jìn)制串否卜面給出的是用中綴轉(zhuǎn)后綴算法實(shí)現(xiàn)的程序的源代碼:/* 構(gòu)造哈夫曼樹*/#include stdio.h#include string.h#define max 100 struct haffnode int weight;int parent;char ch;int lchild;int rchild;*myhafftree;/* 定義常量*/* 權(quán)值 */* 雙親結(jié)點(diǎn)下標(biāo)

4、 */* 定義數(shù)組*/* 字符的權(quán)值*/* 定義結(jié)構(gòu)體*/struct codingchar bitmax;char ch;int weight;*myhaffcode;void haffman(int n)/* 定義哈夫曼函數(shù) */int i,j,x1,x2,s1,s2;for (i=n+1;i=2*n-1;i+)/* 樹的初始化 */s1=s2=10000;x1=x2=0;for (j=1;j=i-1;j+)/* 構(gòu)造哈夫曼樹的非葉子結(jié)點(diǎn) */* 分配左右結(jié)點(diǎn) */if(myhafftreej.parent=0&myhafftreej.weights1)s2=s1;x2=x1;s1=myh

5、afftreej.weight;x1=j;else if(myhafftreej.parent=0&myhafftreej.weights2)s2=myhafftreej.weight;x2=j;myhafftreex1.parent=i;myhafftreex2.parent=i;myhafftreei.weight=s1+s2;/* 左右子組合為新樹*/myhafftreei.lchild=x1;myhafftreei.rchild=x2;void haffmancode(int n)/* 構(gòu)造 n 個結(jié)點(diǎn)哈夫曼編碼*/int start,c,f,i,j,k; char *cd;cd=(c

6、har *)malloc(n*sizeof(char);myhaffcode=(struct coding *)malloc(n+1)*sizeof(struct coding); cdn-1=0;for(i=1;i=n;+i)/*n 個葉子結(jié)點(diǎn)的哈夫曼編碼*/ start=n-1;for(c=i,f=myhafftreei.parent;f!=0;c=f,f=myhafftreef.parent)if(myhafftreef.lchild=c) cd-start=0;else cd-start=1;for(j=start,k=0;jn;j+) myhaffcodei.bitk=cdj; k+

7、;myhaffcodei.ch=myhafftreei.ch;/* 取編碼對應(yīng)的權(quán)值 */myhaffcodei.weight=myhafftreei.weight; free(cd); init()/* 定義有返回值的函數(shù) */int i,n,m;printf(please input the number of words:); scanf(%d,&n);m=2*n-1;myhafftree=(struct haffnode *)malloc(sizeof(struct haffnode)*(m+1); for(i=1;i=n;i+) printf(please input the wor

8、d and the equal:);scanf(%s%d,&myhafftreei.ch,&myhafftreei.weight);myhafftreei.parent=0;myhafftreei.lchild=0;myhafftreei.rchild=0; for(i=n+1;i=m;i+) myhafftreei.ch =#;myhafftreei.lchild=0;myhafftreei.parent=0;myhafftreei.rchild=0;myhafftreei.weight=0;haffman(n);haffmancode(n);for(i=1;i=n;i+)printf(%c

9、 %d,myhaffcodei.ch,myhaffcodei.weight);printf(n);printf(init success!n);return n;void caozuo_c(int m)int n,i,j;char string50,*p;printf(please input the words ： );scanf(%s,string);n=strlen(string);for(i=1,p=string;i=n;i+,p+)for(j=1;j=m;j+)if(myhaffcodej.ch=*p)printf(%sn,myhaffcodej.bit);/* 編碼函數(shù) */* 計

10、算字符串長度*/* 進(jìn)行編碼 */void caozuo_d(int n)/* 解碼函數(shù) */int i,c;char code1000,*p;printf(please input the coding scanf(%s,code);for(p=code,c=2*n-1;*p!=0;p+)if(*p=0)c=myhafftreec.lchild;if(myhafftreec.lchild=0)printf(%c,myhafftreec.ch);c=2*n-1;);/* 輸入二進(jìn)制編碼*/* 進(jìn)行解碼*/* 結(jié)束條件*/* 賦值 */* 掃描 */continue;else if(*p=1)c

11、=myhafftreec.rchild;if(myhafftreec.lchild=0)printf(%c,myhafftreec.ch);c=2*n-1;/* 賦值 */continue; printf(n);void main()int n;char char1;n=init();printf(a.coding b.codeprintingwhile(1)scanf(%c,&char1);if(char1=c)break;switch(char1)casea:caozuo_c(n);break;caseb:caozuo_d(n);break; casec:;break;/* 結(jié)束 */*

12、定義字符 */* 函數(shù)的調(diào)用 */c.exitnplease input the process:n);/* 判斷字符 */* 執(zhí)行編碼操作*/* 執(zhí)行解碼操作*/四、運(yùn)行結(jié)果（一）中綴轉(zhuǎn)后綴算法的運(yùn)行結(jié)果:&em 語牛;huffmat生please input the nuitber of words:1 please input the ward and the equal:a 1please input the word and the equal:b 2im髭。input th電 的rd and th equal ：c 3please input the word and the。川d

13、l:dinit success!a.coding b.codeprinting c.exitblease input the process:aplease input the vrordsuhbcd110111100bplease input th。 codingul110111199 abed五、遇到的問題及解決這部分我主要遇到了如下三個問題，其內(nèi)容與解決方法如下所列:問題1：剛開始不知道如何建一個好樹， 因?yàn)槲议_始試著建了幾個二叉樹， 不知道什么原因運(yùn)行的時候那編碼總是不對， 跟在草稿紙上自己畫的那個二叉樹總是不相符， 就找原因。解決方法 :開始時總是編碼出錯， 就試著找錯， 樹的初始化

14、不可能出錯， 所以首先看那葉子結(jié)點(diǎn)的 for 函數(shù)，沒什么錯誤，接著看非葉子結(jié)點(diǎn)的 for 函數(shù)，非葉子結(jié)點(diǎn)不好弄，找起來麻煩一些， 就是費(fèi)時間， 盤查到最后也沒什么錯， 最后就是左右子結(jié)點(diǎn)重生結(jié)點(diǎn)的一塊了， 這也比較好查， 可是結(jié)果卻是錯處在這兒了， 沒想到最放心的一塊出了錯，得好好反省反省了，以后絕不能在這些問題上出錯了，還好不是很嚴(yán)重，還可以補(bǔ)回來。問題 2:由于前一個問題的解決， 后面小心意義的寫， 盡量放慢寫的速度， 省的再花時間找錯， 可是最后能運(yùn)行， 運(yùn)行的結(jié)果卻是錯的不容樂觀啊， 還出現(xiàn)一些不認(rèn)識的亂碼，這樣的問題最難了，也是最不想遇到的問題，邏輯問題和一些代碼輸入有誤。解決方

15、法:剛開始改的時候不知哪兒錯， 就是亂改一通， 結(jié)果還是找不到哪兒出錯了， 只能請高手了，不過還是問了兩個人才解決這個問題的。最后還是不是怎么懂， 馬馬虎虎吧。問題 3 ：這個問題是寫到前面才想起來的，就是哈夫曼編碼與解碼這個作業(yè)的原理不是很懂，剛開始在課上聽的就不是很懂很透，結(jié)果過了兩天忘了。解決方法：這個問題跟別人討論了一下， 然后給我講了一下就懂了， 也沒什么難的， 就這么輕松的解決了。六、心得體會通過這次的作業(yè)我充分的認(rèn)識到了自己的不足， 特別是對寫程序代碼這方面， 一個程序從算法到用程序把它實(shí)現(xiàn)出來， 這一整個過程是很不容易的， 你懂得它的算法， 不一定就能寫的出來， 通過這次我也深深的了這一點(diǎn)。對于一個新手來說，小的錯誤出現(xiàn)的太多， 而且一個小的錯誤就能讓我束手無策， 因?yàn)橄氩煌ㄥe在哪， 所以就一直在亂改， 邏輯錯誤就更難了， 有時候程序運(yùn)行語法沒有錯誤， 但只要輸入表達(dá)式計算結(jié)果時， 出來的結(jié)果要不是錯的