哈夫曼編碼譯碼器課程設(shè)計(jì)--- 哈夫曼樹(shù)的建立與實(shí)現(xiàn)

1、<p>　　學(xué) 年 設(shè) 計(jì) 報(bào) 告</p><p>　　設(shè)計(jì)題目 哈夫曼樹(shù)的建立與實(shí)現(xiàn) </p><p>　　作者姓名 </p><p>　　所學(xué)專(zhuān)業(yè) 網(wǎng)絡(luò)工程 </

2、p><p>　　指導(dǎo)教師 </p><p>　　2011年8月23日</p><p><b>　　學(xué)年設(shè)計(jì)任務(wù)書(shū)</b></p><p><b>　　目 錄</b></p><p><b>　　1 引 言

3、4</b></p><p><b>　　2 需求分析4</b></p><p><b>　　3 概要設(shè)計(jì)4</b></p><p>　　3.1 設(shè)計(jì)思路及方案4</p><p>　　3.2 模塊的設(shè)計(jì)及介紹5</p><p><b>

4、;　　4 詳細(xì)設(shè)計(jì)8</b></p><p>　　4.1 主調(diào)函數(shù)8</p><p>　　4.2 建立HuffmanTree9</p><p>　　4.3生成Huffman樹(shù)并寫(xiě)入文件10</p><p>　　5 調(diào)試與操作說(shuō)明11</p><p>　　5.1讀出文本11</p>

5、<p>　　5.2輸出哈夫曼樹(shù)存儲(chǔ)結(jié)構(gòu)的初態(tài)12</p><p>　　5.3輸出哈夫曼樹(shù)存儲(chǔ)結(jié)構(gòu)的終態(tài)12</p><p>　　5.4輸出哈夫曼樹(shù)構(gòu)成后的抽象圖14</p><p>　　6學(xué)年設(shè)計(jì)總結(jié)與體會(huì)14</p><p>　　7 參考文獻(xiàn)15</p><p><b>　　8

6、 致謝15</b></p><p><b>　　9 附錄15</b></p><p><b>　　學(xué)年設(shè)計(jì)的主要內(nèi)容</b></p><p><b>　　1 引 言</b></p><p>　　隨著當(dāng)今信息技術(shù)的發(fā)展，為了方便和節(jié)省信息的存儲(chǔ)和傳遞速度，人們

7、便創(chuàng)建了哈夫曼編碼。哈夫曼編碼是將文件進(jìn)行壓縮的一種壓縮方法。哈夫曼編碼的最大的功能是能夠用更少的內(nèi)存空間來(lái)存儲(chǔ)更多的信息。若要對(duì)文件進(jìn)行編碼則必須對(duì)其建立哈夫曼樹(shù)，其次對(duì)這個(gè)哈夫曼樹(shù)進(jìn)行編碼。本學(xué)年設(shè)計(jì)的主要目標(biāo)就是對(duì)如何建立哈夫曼樹(shù)和如何進(jìn)行編碼的一個(gè)詳細(xì)介紹。</p><p><b>　　2 需求分析</b></p><p>　　問(wèn)題描述：打開(kāi)一篇英文文章，統(tǒng)

8、計(jì)該文章中每個(gè)字符出現(xiàn)的次數(shù)，然后以它作為權(quán)值，對(duì)所有字符進(jìn)行構(gòu)建哈夫曼樹(shù)。</p><p>　　問(wèn)題補(bǔ)充：⑴ 從硬盤(pán)的一個(gè)文件里讀出一段英語(yǔ)文章； </p><p>　?、?統(tǒng)計(jì)這篇文章中的每個(gè)字符出現(xiàn)的次數(shù)；</p><p>　　⑶ 以字符出現(xiàn)字?jǐn)?shù)作為權(quán)值，構(gòu)建哈夫曼樹(shù)，并將哈夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)進(jìn)行輸出。</p><p><

9、;b>　　具體介紹：</b></p><p>　　在E盤(pán)中預(yù)先建立一個(gè)filel.txt文檔，在文檔中編輯一篇文章（大寫(xiě)）。然后運(yùn)行程序，調(diào)用fileopen()函數(shù)讀出該文章，顯示在界面；再調(diào)用jsq()函數(shù)對(duì)該文章的字符種類(lèi)進(jìn)行統(tǒng)計(jì)，并對(duì)每個(gè)字符的出現(xiàn)次數(shù)進(jìn)行統(tǒng)計(jì)，并且在界面上顯示；然后以每個(gè)字符出現(xiàn)次數(shù)作為權(quán)值，調(diào)用ChuffmanTree()函數(shù)構(gòu)建哈夫曼樹(shù)，并調(diào)用print1()和pr

10、int2()函數(shù)將哈夫曼的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)進(jìn)行輸出。</p><p><b>　　3 概要設(shè)計(jì)</b></p><p>　　3.1 設(shè)計(jì)思路及方案</p><p>　　假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為Wi，編碼長(zhǎng)度為L(zhǎng)i，電文中有n種字符，則電文編碼總長(zhǎng)度為（W1*L1）+(W2*L2)+.......(Wi*Li)。若將此對(duì)應(yīng)到二叉

11、樹(shù)上，Wi為葉結(jié)點(diǎn)，Li為根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長(zhǎng)度。那么，（W1*L1）+(W2*L2)+.......(Wi*Li) 恰好為二叉樹(shù)上帶權(quán)路徑長(zhǎng)度。以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵哈夫曼樹(shù)。</p><p>　　該系統(tǒng)將實(shí)現(xiàn)以下幾大功能：從硬盤(pán)讀取字符串，建立哈夫曼樹(shù)，輸出哈夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)。</p><p>　　3.2 模塊的設(shè)計(jì)及介紹</p><p

12、>　　⑴ 從硬盤(pán)讀取字符串</p><p>　　fileopen(參數(shù)){</p><p>　　//利用此函數(shù)進(jìn)行對(duì)將文件打開(kāi)</p><p><b>　　實(shí)現(xiàn)命令；</b></p><p><b>　　打印輸出；</b></p><p><b>　　}&l

13、t;/b></p><p>　　⑵ 建立HuffmanTree</p><p>　　通過(guò)三個(gè)函數(shù)來(lái)實(shí)現(xiàn):</p><p>　　void select(參數(shù)){ //從數(shù)組中選取兩個(gè)最小的字符作為//根節(jié)點(diǎn)的左右結(jié)點(diǎn)</p><p><b>　　初始化；</b

14、></p><p><b>　　for{ </b></p><p><b>　　接受命令；</b></p><p><b>　　處理命令；</b></p><p><b>　　}</b></p><p>　　說(shuō)明：在ht[l.

15、......k]中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法</p><p>　　int jsq（參數(shù)）{ </p><p>　　// 統(tǒng)計(jì)字符的種類(lèi)及其個(gè)數(shù)</p><p><b>　　初始化；</b></p><p><b>　　for{</b></p><p>

16、<b>　　接受命令；</b></p><p><b>　　處理命令；</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　說(shuō)明：統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字符的種類(lèi)</p><

17、;p>　　void ChuffmanTree(){初始化； //利用此函數(shù)構(gòu)造出哈夫曼樹(shù)</p><p><b>　　for{</b></p><p><b>　　接受命令；</b></p><p><b>　　處理命令； </b></p>

18、<p><b>　　}</b></p><p><b>　　輸出字符統(tǒng)計(jì)情況；</b></p><p><b>　　}</b></p><p><b>　　說(shuō)明：構(gòu)造哈夫曼樹(shù)</b></p><p>　?、?輸出哈夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)

19、</p><p>　　分別調(diào)用print1()和print2（）來(lái)實(shí)現(xiàn)</p><p>　　void print1（參數(shù)）{ //輸出哈夫曼樹(shù)的初態(tài)</p><p><b>　　初始化；</b></p><p><b>　　輸出初態(tài)；</b>&

20、lt;/p><p><b>　　}</b></p><p>　　說(shuō)明：輸出哈夫曼樹(shù)的初態(tài)</p><p>　　void print2（參數(shù)）{ //輸出哈夫曼樹(shù)的終態(tài)</p><p><b>　　for{</b></p><p&

21、gt;<b>　　輸出終態(tài)；</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　說(shuō)明：輸出哈夫曼樹(shù)的終態(tài)</p><p>　?、?哈夫曼算法是通過(guò)對(duì)輸入數(shù)據(jù)的統(tǒng)計(jì)，根據(jù)其頻率來(lái)構(gòu)造出權(quán)值，再通過(guò)對(duì)構(gòu)造的權(quán)值進(jìn)行建立哈夫

22、曼樹(shù)。并對(duì)其進(jìn)行0和1的賦值，進(jìn)而可以對(duì)每一個(gè)權(quán)值所對(duì)應(yīng)的位置進(jìn)行編碼。</p><p>　　圖1哈夫曼算法實(shí)現(xiàn)流程圖</p><p>　?、?哈夫曼編碼是通過(guò)對(duì)構(gòu)成最優(yōu)二叉樹(shù)的結(jié)點(diǎn)進(jìn)行有規(guī)律的0和1的編碼，之后從根結(jié)點(diǎn)往下進(jìn)行不斷地延伸，且在延伸的過(guò)程中會(huì)途徑所有的結(jié)點(diǎn)并記住每一個(gè)結(jié)點(diǎn)所對(duì)應(yīng)的數(shù)值是0還是1并進(jìn)行記錄，進(jìn)而可以將每個(gè)途徑的結(jié)點(diǎn)所對(duì)應(yīng)的數(shù)值記錄在數(shù)組中。直到所有的結(jié)點(diǎn)都遍

23、歷了一遍的時(shí)候，整個(gè)編碼的過(guò)程也就完成了，而此時(shí)數(shù)組中所存儲(chǔ)的0，1代碼便是每一個(gè)結(jié)點(diǎn)所對(duì)應(yīng)的編碼</p><p>　　圖2哈夫曼編碼流程圖</p><p>　　(6) 構(gòu)造哈夫曼樹(shù)其實(shí)就是對(duì)以上已經(jīng)建立好的權(quán)值利用哈夫曼算法把它建立成一個(gè)最優(yōu)二叉樹(shù)即哈夫曼樹(shù)。其詳細(xì)的過(guò)程是通過(guò)比較權(quán)值域來(lái)選取最小的兩個(gè)權(quán)值，進(jìn)行一步步的合并和刪除直到權(quán)值域中只剩下唯一的一個(gè)所謂的權(quán)值時(shí)，則整個(gè)哈夫曼樹(shù)

24、的構(gòu)造便順利的完成了，而這唯一的一個(gè)權(quán)值便是整棵二叉樹(shù)的根結(jié)點(diǎn)。</p><p>　　圖3哈夫曼樹(shù)構(gòu)造流程圖</p><p><b>　　4 詳細(xì)設(shè)計(jì)</b></p><p>　　各模塊分別為主調(diào)函數(shù)、建立Huffman Tree、生成Huffman Tree并寫(xiě)入文件。具體過(guò)程如下：</p><p><b>

25、;　　4.1 主調(diào)函數(shù)</b></p><p>　　代碼解釋?zhuān)哼@是main函數(shù)里的各個(gè)函數(shù)調(diào)用情況。</p><p>　　fileopen（string）； //從C盤(pán)內(nèi)中讀取文件</p><p>　　num=jsq(string,cnt,str); //統(tǒng)計(jì)字符種類(lèi)及各類(lèi)字符出現(xiàn)的頻率<

26、;/p><p>　　DhuffmanTree(HT,cnt,str);</p><p>　　printf(“HuffmanTree的初態(tài)：\n”);</p><p>　　print1(HT); //輸出哈夫曼樹(shù)的初態(tài)</p><p>　　ChuffmanTree(HT,HC,cnt,str);

27、 //建立哈夫曼樹(shù)</p><p>　　HuffmanEncoding(HT,HC); //生成哈夫曼樹(shù)</p><p>　　printf(“HuffmanTree的終態(tài)：\n”);</p><p>　　print2(“HuffmanTree的終態(tài)：\n”);</p><p>　　4.2 建立HuffmanTre

28、e</p><p>　　代碼解釋?zhuān)涸摵瘮?shù)為在ht[l......k]中選擇patent為0且權(quán)值最小的根結(jié)點(diǎn)的算法，其序號(hào)為s1和s2.</p><p>　　void select (HuffmanTree T,int k,int &s1,int &s2){ //選取最小的根結(jié)點(diǎn)的函數(shù)</p><p><b>　　int i, j;<

29、;/b></p><p>　　s2=s1 //以s1和s2作為兩個(gè)最小節(jié)點(diǎn)的變量</p><p>　　for(i=1;i<=k;i++)</p><p>　　if(T[i].weight<min1 &&T[i].patent==0){ //利用此循環(huán)將最小結(jié)點(diǎn)

30、s1找到</p><p>　　j=i; min1=T[i].weight;</p><p><b>　　}</b></p><p>　　s1=j; min1=32767;</p><p>　　for(i=1;i<=k;i++) //利用此循環(huán)將另一個(gè)最小結(jié)點(diǎn)s2找到

31、</p><p>　　if(T[i].weight<min1 &&T[i].patent==0 &&i!=s1){</p><p>　　j=i; min1=T[i].weight;</p><p><b>　　}</b></p><p><b>　　s2=j;</b&

32、gt;</p><p><b>　　}</b></p><p>　　//對(duì)所有的字母進(jìn)行統(tǒng)計(jì)種類(lèi)和出現(xiàn)的次數(shù)</p><p>　　int jsp(char *s,int cnt[],char str[]){ //str[]存放所有字符，cnt[]來(lái)存放每種字</p><p>　　int i ,j

33、,k; //母的權(quán)值</p><p>　　char *p; //統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字</p><p>　　int temp[27]; //存每種字母的個(gè)數(shù)</p><p>　　

34、for(i=1;i<=26;i++)</p><p>　　temp[i]=0;</p><p>　　for(p=s;*p!=’\0’;p++){</p><p>　　if(*p>=’A’&&*p<=’Z’)</p><p>　　k=*p-64; //找到該字

35、母的位置</p><p>　　temp[k]++;</p><p>　　} //統(tǒng)計(jì)各種字符的個(gè)數(shù)</p><p>　　for（i=1,j=0;i<=26;++i）</p><p>　　if(temp[i]!=0){</p><p><b&g

36、t;　　j++;</b></p><p>　　str[j]=i+64; //送對(duì)應(yīng)字母到數(shù)組中</p><p>　　cnt[j]=temp[i]; //存入對(duì)應(yīng)字母的權(quán)值</p><p><b>　　}</b></p><p

37、>　　return j； //j是輸入字母總數(shù)</p><p><b>　　}</b></p><p>　　代碼解釋?zhuān)合旅婧瘮?shù)用來(lái)構(gòu)造哈夫曼樹(shù)HT。首先初始化哈夫曼樹(shù)，然后輸入前面統(tǒng)計(jì)的各個(gè)結(jié)點(diǎn)的權(quán)值，用for循環(huán)來(lái)構(gòu)造哈夫曼樹(shù)。</p><p>　　void ChuffmanTre

38、e(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[]){</p><p>　　int i,s1 ,s2;</p><p>　　for(i=1;i<=2*num-1;i++){ //初始化HT，2*num-1是指哈夫曼所有的節(jié)//點(diǎn)數(shù)目</p><p>　　HT[i].lchild

39、=0;HT[i].rchild=0;</p><p>　　HT[i].patent=0;HT[i].weight=0;</p><p><b>　　}</b></p><p>　　for(i=1;i<=num;i++) //輸入num個(gè)葉結(jié)點(diǎn)的權(quán)值</p><p>　　HT[i].w

40、eight=cnt[i];</p><p>　　for(i=num+1;i<=2*num-1;i++) {</p><p>　　select(HT,i-1,s1,s2);</p><p>　　HT[s1].patent=i;HT[s2].patent=i;</p><p>　　HT[i].lchild=s1;HT[i].rchild=s

41、2;</p><p>　　HT[i]weight=HT[s1].weight*HT[s2].weight;</p><p>　　} //在ht[l.....k]中選擇patent為0且權(quán)值最小的兩</p><p>　　//個(gè)根結(jié)點(diǎn)，其序號(hào)為s1和s2，i為雙親</p><p>　　f

42、or（i=0；i<=num；i++）； //輸入字符集中字符</p><p>　　HC[i].ch=str[i]; //字符種類(lèi)</p><p>　　i=1;while(i<=num)</p><p>　　printf(“字符%c次數(shù)：%d”,HC[i].ch,cnt[i++]);</p>

43、<p>　　} //輸出統(tǒng)計(jì)的情況</p><p>　　4.3生成Huffman樹(shù)并寫(xiě)入文件</p><p>　　代碼解釋?zhuān)焊鶕?jù)所輸入的字符構(gòu)建哈夫曼樹(shù)T 。</p><p>　　void HuffmanEncoding (HuffmanT\ree T,HuffmanCode

44、H){</p><p>　　int c,p,i; //c和p分別指示t中孩子和雙親</p><p>　　char cd[n]; //臨時(shí)存放編碼串</p><p>　　int start; //指示碼在cd中的

45、起始位置</p><p>　　cd[num]=’\0’; //最后一位（第num個(gè)）放上串結(jié)束符</p><p>　　for(i=1;i<=num;++i){</p><p>　　start=num; //初始位置</p><p>　　c=i;

46、 //從葉子結(jié)點(diǎn)t[i]開(kāi)始上溯</p><p>　　while((p=T[c].patent)>0){ //直至上溯到t[c]是樹(shù)根為止</p><p>　　Cd[--start]=(T[p].lchild==c) ?’0’:’1’;</p><p><b>　　c=p;<

47、;/b></p><p>　　} //若t[c]是t[p]的左孩子則生成0；否則生成1</p><p>　　Strcpy(H[i].bits,*cde[start]);</p><p>　　H[i].len=num-start;</p><p><b>　　}

48、</b></p><p><b>　　}</b></p><p>　　代碼解釋?zhuān)簩?duì)str所代表的字符串進(jìn)行構(gòu)建哈夫曼樹(shù)并寫(xiě)入文件。將翻譯的二進(jìn)制碼寫(xiě)入文本文件。</p><p>　　void coding(HuffmanCode HC, char *str) //對(duì)str所代表的字符串進(jìn)行編碼并寫(xiě)入文件</p>

49、<p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　FILE *fp; //定義文件的指針</p><p>　　fp=fopen(“codefile.txt”,”w”);

50、 //打開(kāi)文件的函數(shù)</p><p>　　while(*str){ //str為編碼的指針</p><p>　　for(i=1;i<=num;i++)</p><p>　　if(HC[i].ch==*str){</p><p>　　for(j=0;j<=HC[i].le

51、n;j++)</p><p>　　Fputc(HC[I].bits[j],fp);</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　str++;</b></p><p>　　} fc

52、lose(fp); //將文件關(guān)閉</p><p><b>　　}</b></p><p>　　5 調(diào)試與操作說(shuō)明</p><p>　　本次測(cè)試是通過(guò)建立一個(gè)名為file1.txt的文本文檔，其中有一篇英文字母的文章期望程序能將其讀出至界面并實(shí)現(xiàn)其它相關(guān)的功能。運(yùn)行程序后，我們可以見(jiàn)到以下運(yùn)行界

53、面。</p><p><b>　　5.1讀出文本</b></p><p>　　從file1.txt中讀取剛輸入的字符串并將其輸出到顯示屏如圖3所示。</p><p><b>　　圖3讀出文本示意圖</b></p><p>　　5.2輸出哈夫曼樹(shù)存儲(chǔ)結(jié)構(gòu)的初態(tài)</p><p>

54、　　下圖所示的為哈夫曼樹(shù)的初態(tài)。其中的每行數(shù)字分別表示字符的權(quán)值，字符的雙親，字符的左孩子，字符的右孩子，而本圖為哈夫曼樹(shù)的初始化如圖4所示。</p><p>　　圖4哈夫曼樹(shù)的初態(tài)圖</p><p>　　5.3輸出哈夫曼樹(shù)存儲(chǔ)結(jié)構(gòu)的終態(tài)</p><p>　　該圖為哈夫曼樹(shù)的終態(tài)。本圖顯示的是哈夫曼樹(shù)的構(gòu)建以后的其字符的權(quán)值，雙親下標(biāo)，左孩子，右孩子如圖5所示。&l

55、t;/p><p>　　圖5 哈夫曼的終態(tài)圖1</p><p>　　圖6 哈夫曼樹(shù)的終態(tài)圖2</p><p>　　5.4輸出哈夫曼樹(shù)構(gòu)成后的抽象圖</p><p>　　此圖的構(gòu)成首先是從權(quán)值域中選取最小的兩個(gè)權(quán)值，在此例中其分別為4、4. 通過(guò)這兩個(gè)最小的權(quán)值合并成為雙親結(jié)點(diǎn)8.之后在將8插入到權(quán)值域中，同時(shí)將此兩個(gè)最小的結(jié)點(diǎn)刪除。按照此方法一步步

56、的運(yùn)行下去最終使得權(quán)值域中只剩下唯一的一個(gè)權(quán)值，至此最優(yōu)二叉樹(shù)便建立好了。并且這個(gè)最后的結(jié)點(diǎn)便是整棵二叉樹(shù)中的根結(jié)點(diǎn)，在本例子中456便是整棵最優(yōu)二叉樹(shù)的根結(jié)點(diǎn)。</p><p><b>　　圖6哈夫曼樹(shù)示意圖</b></p><p><b>　　學(xué)年設(shè)計(jì)總結(jié)與體會(huì)</b></p><p>　　本學(xué)年設(shè)計(jì)的主要目的是要建立

57、一個(gè)哈夫曼樹(shù)并將其實(shí)現(xiàn)。通過(guò)構(gòu)建哈夫曼編碼結(jié)構(gòu)體來(lái)解決一系列因編碼帶來(lái)的復(fù)雜問(wèn)題。同時(shí)利用幾個(gè)數(shù)組來(lái)存儲(chǔ)字符出現(xiàn)的頻率和種類(lèi)。且在此過(guò)程中也用到了哈夫曼編碼函數(shù)和哈夫曼構(gòu)建函數(shù)等，因而使得整個(gè)程序繁而不亂有條不紊的編輯和運(yùn)行</p><p>　　在此次的學(xué)年設(shè)計(jì)中，對(duì)于構(gòu)建哈夫曼樹(shù)主要的思想是通過(guò)記錄文件中字符的頻率來(lái)作為在哈夫曼樹(shù)構(gòu)造中必不可少的權(quán)值，再根據(jù)權(quán)值來(lái)構(gòu)造哈夫曼樹(shù)，進(jìn)而根據(jù)這棵建好的哈夫曼樹(shù)來(lái)進(jìn)行字

58、符編碼，并將其存儲(chǔ)在所對(duì)應(yīng)的文件中。 </p><p><b>　　7 參考文獻(xiàn) </b></p><p>　　[1] 嚴(yán)蔚敏，胡學(xué)剛.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M]. 清華大學(xué)出版社，2007</p><p>　　[2] 蘇仕華. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)[M].機(jī)械工業(yè)出版社，2007</p><p>　　[3] 譚浩強(qiáng). C

59、語(yǔ)言程序設(shè)計(jì)教程[M].高等教育出版社，2006</p><p><b>　　8 致謝 </b></p><p>　　對(duì)于老師詳細(xì)的指導(dǎo)和同學(xué)們的積極配合予以感謝，同時(shí)對(duì)各個(gè)參考文件的提供出版社以真誠(chéng)的感謝。</p><p><b>　　9 附錄 </b></p><p>　　# includ

60、e<stdio.h></p><p>　　# include<string.h></p><p>　　# include<stdlib.h></p><p>　　# include<fstream.h></p><p>　　//*********************類(lèi)型相關(guān)變量的定義****

61、************************//</p><p>　　# define n 100 //葉子結(jié)點(diǎn)數(shù)</p><p>　　# define m 2*n-1 //哈夫曼樹(shù)中的結(jié)點(diǎn)數(shù)</p><p>　　typedef str

62、uct{</p><p>　　char ch; //相關(guān)的字母</p><p>　　char bits[9]; //存放編碼位串</p><p>　　int len;

63、 //該字母編碼的長(zhǎng)度</p><p>　　}CodeNode; //編碼的類(lèi)型</p><p>　　typedef CodeNode HuffmanCode[n+1]; //所有的葉子結(jié)點(diǎn)的編碼數(shù)組</p><p>　　typedef struct{</p&g

64、t;<p>　　int weight; //權(quán)值</p><p>　　int lchild,rchild,parent; //左右孩子及雙親指針</p><p>　　}HTNode; //

65、哈夫曼樹(shù)結(jié)點(diǎn)的類(lèi)型</p><p>　　typedef HTNode HuffmanTree[m+1]; //0號(hào)單元不用</p><p>　　int num; //統(tǒng)計(jì)每種字母出現(xiàn)的次數(shù)和種類(lèi)數(shù)目</p><p>　　// ******************

66、********建立HuffmanTree/**************************//</p><p>　　void select(HuffmanTree T,int k,int &s1,int &s2){</p><p>　　//在ht[1......k]中選擇parent為0且權(quán)</p><p>　　//值最小的兩個(gè)根結(jié)點(diǎn)的算法&l

67、t;/p><p>　　//其序號(hào)為s1和s2</p><p>　　int i,j;int min1=101; //min1的數(shù)字無(wú)何意義只是初始值之后//用來(lái)記錄權(quán)值，i為循環(huán)</p><p>　　//最小權(quán)值的下標(biāo),k為數(shù)組結(jié)點(diǎn)的總數(shù)</p><p>　　for(i=1;i<=k;i++

68、)</p><p>　　if (T[i].weight<min1 &&T[i].parent==0){</p><p>　　j=i; min1=T[i].weight; //賦權(quán)值</p><p><b>　　}</b></p><p>　　s1=j; min1=

69、32767; //找到權(quán)值最小的其中之一</p><p>　　for (i=1; i<=k; i++)</p><p>　　if(T[i].weight<min1 &&T[i].parent==0 && i!=s1)//不讓s2和s1的數(shù)組下標(biāo)重合</p><p><

70、;b>　　{</b></p><p>　　j=i ; min1=T[i].weight; //找到權(quán)值最小的其中之一</p><p><b>　　}</b></p><p><b>　　s2=j ;</b></p><p><b>　　}

71、</b></p><p>　　int jsq(char *s, int cnt [],char str[]) //str[]存放所有字符，cnt[]來(lái)存放每種字//母的權(quán)值</p><p>　　{ //統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字//符的種類(lèi)，s為數(shù)組&

72、lt;/p><p><b>　　//的首地址指針</b></p><p>　　int i,j,k;</p><p><b>　　char *p;</b></p><p>　　int temp[27]; //存每種字母的個(gè)數(shù)</p>

73、<p>　　for(i=1;i<=26;i++)</p><p>　　temp[i]=0; //初始化為0</p><p>　　for(p=s;*p!='\0';p++)</p><p>　　{

74、 </p><p><b>　　{</b></p><p>　　if(*p>='A' &&*p<='Z' ) </p><p>　　k=*p-64;

75、 //找到字母在數(shù)組中的下標(biāo)</p><p>　　temp[k]++; //字母?jìng)€(gè)數(shù)累加</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=1,j=0;i<=26;++i)

76、 </p><p>　　if( temp[i] !=0)</p><p><b>　　{</b></p><p>　　j++; //j為字母的總數(shù)</p><p>　　str[j]=i+64; //

77、送對(duì)應(yīng)的字母到數(shù)組中</p><p>　　cnt[j]=temp[i]; //存入對(duì)應(yīng)字母的權(quán)值</p><p><b>　　}</b></p><p>　　return j; //j是輸入字母總數(shù)</p>&

78、lt;p><b>　　}</b></p><p>　　void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[], char str[])</p><p>　　{ //構(gòu)造哈夫曼樹(shù)HT</p><p&

79、gt;　　int i,s1,s2;</p><p>　　for(i=1;i<=2*num-1;i++)</p><p>　　{ //初始化HT，2*num-1是指哈夫曼樹(shù)所</p><p><b>　　//有的結(jié)點(diǎn)數(shù)目</b></p>&l

80、t;p>　　HT[i].lchild=0;HT[i].rchild=0; //初始化為根結(jié)點(diǎn)</p><p>　　HT[i].parent=0;HT[i].weight=0; //初始化為根結(jié)點(diǎn)</p><p><b>　　}</b></p><p>　　for(i=1;i<=num

81、;i++) //輸入num個(gè)葉子結(jié)點(diǎn)的權(quán)值</p><p>　　HT[i].weight=cnt[i]; //賦權(quán)值</p><p>　　for(i=num+1;i<=2*num-1;i++)</p><p><b>　　{</b></p>

82、;<p>　　select(HT,i-1,s1,s2); //在ht[1.....k]中選擇parent為0且權(quán)值 </p><p>　　//最小的兩個(gè)根結(jié)點(diǎn) </p><p>　　HT[s1].parent=i;HT[s2].parent=i; //其序

83、號(hào)為s1和s2</p><p>　　HT[i].lchild=s1;HT[i].rchild=s2; //i為雙親</p><p>　　HT[i].weight=HT[s1].weight+HT[s2].weight;</p><p><b>　　}</b></p><p>　　for(i=0;i&

84、lt;=num;i++) //輸入字符集的中字符</p><p>　　HC[i].ch=str[i]; //字符的種類(lèi)</p><p>　　i=1;while(i<=num)</p><p>　　printf("字符%c次數(shù):%d\n",HC[

85、i].ch,cnt[i++]);</p><p><b>　　}</b></p><p>　　//*************************生成Huffman樹(shù)并寫(xiě)入文件*****************//</p><p>　　void HuffmanEncoding(HuffmanTree T,HuffmanCode H)</

86、p><p>　　{ //根據(jù)哈夫曼樹(shù)T求哈夫曼編碼H</p><p>　　int c,p,i; //c和p分別指示t中孩子和雙親</p><p>　　char cd[n];

87、 //臨時(shí)存放編碼串，n為字母總數(shù)</p><p>　　int start; //指示碼在cd中的起始位置</p><p>　　cd[num]='\0'; //num為葉子結(jié)點(diǎn)的總數(shù)

88、 </p><p>　　for(i=1;i<=num;++i) //對(duì)所有的葉子節(jié)點(diǎn)進(jìn)行大循環(huán)的編碼</p><p><b>　　{</b></p><p>　　start=num; //從最后的葉子結(jié)點(diǎn)上

89、溯編碼 </p><p>　　c=i; //從葉子結(jié)點(diǎn)t[i]開(kāi)始上溯</p><p>　　while((p=T[c].parent)>0)</p><p>　　{ //直至上溯到t[c]是樹(shù)根為止</p>

90、<p>　　//若t[c]是t[p]的左孩子，則生成0，否則//生成1</p><p>　　cd[--start]=(T[p].lchild==c)?'0':'1';</p><p>　　c=p; //使得可以進(jìn)行循環(huán)</p><p><b>　　}&

91、lt;/b></p><p>　　strcpy(H[i].bits,&cd[start]);</p><p>　　H[i].len=num-start;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void

92、 coding(HuffmanCode HC,char *str)</p><p>　　{ //對(duì)str所代表的字符串進(jìn)行構(gòu)建哈夫曼</p><p><b>　　//樹(shù)并寫(xiě)入文件</b></p><p>　　int i,j; </p>&

93、lt;p>　　FILE*fp; //定義文件的指針</p><p>　　fp=fopen("codefile.txt","w"); //打開(kāi)文件 的函數(shù)</p><p>　　while (*str) </p><p>&l

94、t;b>　　{</b></p><p>　　for(i=1;i<=num;i++)</p><p>　　if(HC[i].ch==*str){</p><p>　　for(j=0;j<=HC[i].len;j++)</p><p>　　fputc(HC[i].bits[j],fp);</p><

95、;p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　str++;</b></p><p>　　}fclose(fp); //關(guān)閉文件</p><p><

96、;b>　　}</b></p><p>　　//***************輸出HuffmanTree存儲(chǔ)結(jié)構(gòu)*********************//</p><p>　　void print1(HuffmanTree HT)</p><p><b>　　{</b></p><p><b&g

97、t;　　int x;</b></p><p>　　for(x=1;x<=2*num-1;x++)</p><p><b>　　{</b></p><p>　　HT[x].parent=0;</p><p>　　HT[x].lchild=0;</p><p>　　HT[x].rch

98、ild=0;</p><p>　　printf("%11d %d\t%d\n",HT[x].weight,HT[x].parent,HT[x].lchild,HT[x].rchild);</p><p><b>　　}</b></p><p>　　printf("------------------------

99、-----\n");</p><p><b>　　}</b></p><p>　　void print2(HuffmanTree HT)</p><p><b>　　{</b></p><p><b>　　int k;</b></p><p>

100、;　　for(k=1;k<=2*num-1;k++)</p><p><b>　　{</b></p><p>　　printf("%d\t%d\t%d\n",HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);</p><p><b>　　}</b&

101、gt;</p><p>　　printf("--------------------------\n");</p><p><b>　　}</b></p><p>　　void DhuffmanTree(HuffmanTree HT,int cnt[],char str[]){ //構(gòu)造哈夫曼樹(shù) </p>&

102、lt;p><b>　　int i;</b></p><p>　　//char x;</p><p>　　for (i=1;i<=num;i++){ //輸入num個(gè)葉結(jié)點(diǎn)的權(quán)值 </p><p>　　HT[i].weight=cnt[i];</p>&

103、lt;p>　　if(i>=str[i]){</p><p>　　HT[i].weight=(char)'*';</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p>

104、<p>　　//**************************打開(kāi)文本************************//</p><p>　　int fileopen(char string[]){ // string[]為字母的首地址 </p><p>　　FILE *fp;

105、 //文件的指針</p><p>　　if((fp=fopen("file1.txt","r"))==NULL) //判斷該文件是否為空，若是則判空 </p><p>　　printf("不能打開(kāi)文件！\n");</p><p&g

106、t;　　while(fgets(string,100 ,fp)!=NULL)</p><p>　　printf("%s\n",string); //將所有的字母進(jìn)行輸出</p><p>　　fclose(fp); //關(guān)閉文件</p

107、><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void main (){</p><p>　　char string[500]; //用來(lái)存儲(chǔ)所有的字母</p>&

108、lt;p>　　char*s,str[27];</p><p>　　int cnt[27]; //用來(lái)存儲(chǔ)字母的權(quán)值</p><p>　　HuffmanTree HT; //定義哈夫曼樹(shù)</p><p>　　HuffmanCode H

109、C; //定義哈夫曼結(jié)點(diǎn)</p><p>　　printf("讀出文本為：\n");</p><p>　　fileopen(string); //打開(kāi)字符串所在地文件</p><p>　　num=jsq(string,cnt,s

110、tr); //統(tǒng)計(jì)字符的種類(lèi)及各類(lèi)字符出現(xiàn)的//頻率</p><p>　　DhuffmanTree(HT,cnt,str); //構(gòu)造哈夫曼樹(shù) </p><p>　　printf("-------------------\n");</p><p>　　

111、printf("HuffmanTree的初態(tài)：\n"); //輸出哈夫曼的初態(tài)</p><p>　　print1(HT); </p><p>　　ChuffmanTree(HT,HC,cnt,str); //建立哈夫曼樹(shù)</p><p>　　HuffmanEncoding(

112、HT,HC); //生成哈夫曼樹(shù)</p><p>　　coding(HC,string); //建立電文哈夫曼編碼文件</p><p>　　printf("--------------------------------\n");</p><p>

113、　　printf("HuffmanTree的終態(tài)：\n"); //輸出哈夫曼的終態(tài)</p><p>　　print2(HT);</p><p>　　printf("*************************\n");</p><p><b>　　}</b></p