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

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

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

3、步解碼就行了?？删庉嬕陨暇褪峭ㄟ^(guò)用哈夫曼樹(shù)進(jìn)行哈夫曼編碼與解碼如何實(shí)現(xiàn)的主要設(shè)計(jì)思想。二、算法流程圖（一）哈夫曼樹(shù)的流程圖不 是圖1哈夫曼樹(shù)的流程圖（二）編碼的流程圖（三）解碼的流程圖三、源代碼找到樹(shù)的根結(jié)點(diǎn) 輸入二進(jìn)制串否卜面給出的是用中綴轉(zhuǎn)后綴算法實(shí)現(xiàn)的程序的源代碼:/* 構(gòu)造哈夫曼樹(shù)*/#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+)/* 樹(shù)的初始化 */s1=s2=10000;x1=x2=0;for (j=1;j=i-1;j+)/* 構(gòu)造哈夫曼樹(shù)的非葉子結(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;/* 左右子組合為新樹(shù)*/myhafftreei.lchild=x1;myhafftreei.rchild=x2;void haffmancode(int n)/* 構(gòu)造 n 個(gè)結(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 個(gè)葉子結(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;/* 取編碼對(duì)應(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ù) */* 計(jì)

10、算字符串長(zhǎng)度*/* 進(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 語(yǔ)牛;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五、遇到的問(wèn)題及解決這部分我主要遇到了如下三個(gè)問(wèn)題，其內(nèi)容與解決方法如下所列:問(wèn)題1：剛開(kāi)始不知道如何建一個(gè)好樹(shù)， 因?yàn)槲议_(kāi)始試著建了幾個(gè)二叉樹(shù)， 不知道什么原因運(yùn)行的時(shí)候那編碼總是不對(duì)， 跟在草稿紙上自己畫(huà)的那個(gè)二叉樹(shù)總是不相符， 就找原因。解決方法 :開(kāi)始時(shí)總是編碼出錯(cuò)， 就試著找錯(cuò)， 樹(shù)的初始化

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

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