哈夫曼編碼譯碼器課程設(shè)計(jì)

1、滁州學(xué)院本科學(xué)年設(shè)計(jì)1 學(xué)學(xué) 年年 設(shè)設(shè) 計(jì)計(jì) 報報 告告設(shè)計(jì)題設(shè)計(jì)題目目 哈夫曼樹的建立與實(shí)現(xiàn) 作者姓名作者姓名 所學(xué)所學(xué)專業(yè)專業(yè) 網(wǎng)絡(luò)工程 指指導(dǎo)導(dǎo)教教師師 2011 年年 8 月月 23 日日滁州學(xué)院本科學(xué)年設(shè)計(jì)2學(xué)年設(shè)計(jì)任務(wù)書學(xué)年設(shè)計(jì)任務(wù)書課程設(shè)計(jì)題目 哈夫曼樹的建立與實(shí)現(xiàn)組長學(xué)號班級組別第 組專業(yè)網(wǎng)絡(luò)工程組員指 導(dǎo) 教 師學(xué) 年 設(shè) 計(jì) 目 的 通過構(gòu)建哈夫曼樹對數(shù)據(jù)進(jìn)行壓縮，以節(jié)省存儲空間。從而可以用更少的內(nèi)存空間來存儲更多的信息，縮短信息的傳遞時間。學(xué)年設(shè)計(jì)所需環(huán)境Windows XP VC+ 6.0 學(xué)年設(shè)計(jì)任務(wù)要求 收集有關(guān)的資料，對如何構(gòu)建哈夫曼樹有了更加清晰的認(rèn)識，為哈夫

2、曼樹的編寫提供了基本的框架。 將所輸入的數(shù)據(jù)信息進(jìn)行編碼構(gòu)造成哈夫曼樹。 代碼的編寫和對每段的編碼的解釋使得源代碼更具可讀性。 學(xué)年設(shè)計(jì)工作進(jìn)度計(jì)劃序號起止日期工 作 內(nèi) 容分工情況1 2011 年 8 月 23 日2011 年 8 月 25 日編輯打開文件的函數(shù)和哈夫曼樹的輸出初態(tài)和終態(tài) 2 2011 年 8 月 26 日 2011 年 8 月 27 日 查找資料對哈夫曼樹相關(guān)的類型變量的定義 3 2011 年 8 月 27 日 2011 年 8 月 28 日 收集圖片和生成哈夫曼樹并寫入文件 42011 年 8 月 28 日2011 年 8 月 29 日 編寫主函數(shù)以及修改文件的編輯 5

3、2011 年 8 月 29 日 2011 年 8 月 29 日 構(gòu)建哈夫曼樹和收集相關(guān)資料6 2011 年 8 月 29 日 2011 年 8 月 31 日 編輯代碼分配任務(wù)等其他相關(guān)事宜 指導(dǎo)教師簽字： 年 月 日教研室審核意見：教研室主任簽字： 年 月 日滁州學(xué)院本科學(xué)年設(shè)計(jì)3目目 錄錄1 引引 言言.42 需需求求分分析析.43 概概要要設(shè)設(shè)計(jì)計(jì).43.1 設(shè)計(jì)思路及方案.43.2 模塊的設(shè)計(jì)及介紹.54 詳詳細(xì)細(xì)設(shè)設(shè)計(jì)計(jì).84.1 主調(diào)函數(shù).84.2 建立 HUFFMANTREE.94.3 生成 HUFFMAN樹并寫入文件.105 調(diào)調(diào)試試與與操操作作說說明明.115.1 讀出文本.1

4、15.2 輸出哈夫曼樹存儲結(jié)構(gòu)的初態(tài).125.3 輸出哈夫曼樹存儲結(jié)構(gòu)的終態(tài).125.4 輸出哈夫曼樹構(gòu)成后的抽象圖.146學(xué)學(xué)年年設(shè)設(shè)計(jì)計(jì)總總結(jié)結(jié)與與體體會會.147 參參考考文文獻(xiàn)獻(xiàn).158 致致謝謝.159 附附錄錄.15滁州學(xué)院本科學(xué)年設(shè)計(jì)4學(xué)年設(shè)計(jì)的主要內(nèi)容學(xué)年設(shè)計(jì)的主要內(nèi)容1 引引 言言隨著當(dāng)今信息技術(shù)的發(fā)展，為了方便和節(jié)省信息的存儲和傳遞速度，人們便創(chuàng)建了哈夫曼編碼。哈夫曼編碼是將文件進(jìn)行壓縮的一種壓縮方法。哈夫曼編碼的最大的功能是能夠用更少的內(nèi)存空間來存儲更多的信息。若要對文件進(jìn)行編碼則必須對其建立哈夫曼樹，其次對這個哈夫曼樹進(jìn)行編碼。本學(xué)年設(shè)計(jì)的主要目標(biāo)就是對如何建立哈夫曼樹

5、和如何進(jìn)行編碼的一個詳細(xì)介紹。2 需求分析需求分析問題描述：打開一篇英文文章，統(tǒng)計(jì)該文章中每個字符出現(xiàn)的次數(shù)，然后以它作為權(quán)值，對所有字符進(jìn)行構(gòu)建哈夫曼樹。問題補(bǔ)充： 從硬盤的一個文件里讀出一段英語文章； 統(tǒng)計(jì)這篇文章中的每個字符出現(xiàn)的次數(shù)； 以字符出現(xiàn)字?jǐn)?shù)作為權(quán)值，構(gòu)建哈夫曼樹，并將哈夫曼樹的存儲結(jié)構(gòu)的初態(tài)和終態(tài)進(jìn)行輸出。具體介紹：在 E 盤中預(yù)先建立一個 filel.txt 文檔，在文檔中編輯一篇文章（大寫） 。然后運(yùn)行程序，調(diào)用 fileopen()函數(shù)讀出該文章，顯示在界面；再調(diào)用 jsq()函數(shù)對該文章的字符種類進(jìn)行統(tǒng)計(jì)，并對每個字符的出現(xiàn)次數(shù)進(jìn)行統(tǒng)計(jì)，并且在界面上顯示；然后以每個字

6、符出現(xiàn)次數(shù)作為權(quán)值，調(diào)用 ChuffmanTree()函數(shù)構(gòu)建哈夫曼樹，并調(diào)用 print1()和 print2()函數(shù)將哈夫曼的存儲結(jié)構(gòu)的初態(tài)和終態(tài)進(jìn)行輸出。3 概要設(shè)計(jì)概要設(shè)計(jì)3.1 設(shè)計(jì)思路及方案設(shè)計(jì)思路及方案假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為 Wi，編碼長度為 Li，電文中有 n 種字符，則電文編碼總長度為（W1*L1）+(W2*L2)+.(Wi*Li)。若將此對應(yīng)到二叉樹上，Wi 為葉結(jié)點(diǎn)，Li 為根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長度。那么， （W1*L1）+(W2*L2)+.(Wi*Li) 恰好為二叉樹上帶權(quán)路徑長度。以 n 種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵哈夫曼樹。該系統(tǒng)將實(shí)現(xiàn)以下幾大功能：從硬

7、盤讀取字符串，建立哈夫曼樹，輸出哈夫曼樹的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。3.2 模塊的設(shè)計(jì)及介紹模塊的設(shè)計(jì)及介紹 從硬盤讀取字符串滁州學(xué)院本科學(xué)年設(shè)計(jì)5fileopen(參數(shù)) /利用此函數(shù)進(jìn)行對將文件打開 實(shí)現(xiàn)命令； 打印輸出； 建立 HuffmanTree通過三個函數(shù)來實(shí)現(xiàn):void select(參數(shù)) /從數(shù)組中選取兩個最小的字符作為/根節(jié)點(diǎn)的左右結(jié)點(diǎn)初始化；for 接受命令；處理命令；說明：在 htl.k中選擇 parent 為 0 且權(quán)值最小的兩個根結(jié)點(diǎn)的算法int jsq（參數(shù)） / 統(tǒng)計(jì)字符的種類及其個數(shù)初始化；for接受命令；處理命令；說明：統(tǒng)計(jì)字符串中各種字母的個數(shù)以及字符的種類v

8、oid ChuffmanTree()初始化； /利用此函數(shù)構(gòu)造出哈夫曼樹 for接受命令；處理命令； 輸出字符統(tǒng)計(jì)情況；說明：構(gòu)造哈夫曼樹 輸出哈夫曼樹的存儲結(jié)構(gòu)的初態(tài)和終態(tài)分別調(diào)用 print1()和 print2（）來實(shí)現(xiàn)void print1（參數(shù)） /輸出哈夫曼樹的初態(tài)滁州學(xué)院本科學(xué)年設(shè)計(jì)6 初始化；輸出初態(tài)；說明：輸出哈夫曼樹的初態(tài)void print2（參數(shù)） /輸出哈夫曼樹的終態(tài)for輸出終態(tài)；說明：輸出哈夫曼樹的終態(tài) 哈夫曼算法是通過對輸入數(shù)據(jù)的統(tǒng)計(jì)，根據(jù)其頻率來構(gòu)造出權(quán)值，再通過對構(gòu)造的權(quán)值進(jìn)行建立哈夫曼樹。并對其進(jìn)行 0 和 1 的賦值，進(jìn)而可以對每一個權(quán)值所對應(yīng)的位置進(jìn)行

9、編碼。 圖 1 哈夫曼算法實(shí)現(xiàn)流程圖 哈夫曼編碼是通過對構(gòu)成最優(yōu)二叉樹的結(jié)點(diǎn)進(jìn)行有規(guī)律的 0 和 1 的編碼，之后從根結(jié)點(diǎn)往下進(jìn)行不斷地延伸，且在延伸的過程中會途徑所有的結(jié)點(diǎn)并記住每一個結(jié)點(diǎn)所對應(yīng)的開開始始讀讀取取輸輸入入的的數(shù)數(shù)據(jù)據(jù)統(tǒng)統(tǒng)計(jì)計(jì)字字符符的的頻頻率率輸輸入入字字符符排排序序建建立立哈哈夫夫曼曼樹樹輸輸入入字字符符編編碼碼結(jié)結(jié)束束滁州學(xué)院本科學(xué)年設(shè)計(jì)7數(shù)值是 0 還是 1 并進(jìn)行記錄，進(jìn)而可以將每個途徑的結(jié)點(diǎn)所對應(yīng)的數(shù)值記錄在數(shù)組中。直到所有的結(jié)點(diǎn)都遍歷了一遍的時候，整個編碼的過程也就完成了，而此時數(shù)組中所存儲的0，1 代碼便是每一個結(jié)點(diǎn)所對應(yīng)的編碼圖 2 哈夫曼編碼流程圖(6) 構(gòu)

10、造哈夫曼樹其實(shí)就是對以上已經(jīng)建立好的權(quán)值利用哈夫曼算法把它建立成一個最優(yōu)二叉樹即哈夫曼樹。其詳細(xì)的過程是通過比較權(quán)值域來選取最小的兩個權(quán)值，進(jìn)行一步步的合并和刪除直到權(quán)值域中只剩下唯一的一個所謂的權(quán)值時，則整個哈夫曼樹的構(gòu)造便順利的完成了，而這唯一的一個權(quán)值便是整棵二叉樹的根結(jié)點(diǎn)。開開始始數(shù)數(shù)組組初初始始化化當(dāng)當(dāng)前前位位置置編編碼碼當(dāng)當(dāng)前前位位置置進(jìn)進(jìn)數(shù)數(shù)組組換換下下一一個個位位置置切切換換下下一一個個位位置置繼繼續(xù)續(xù)是是否否為為終終點(diǎn)點(diǎn)結(jié)結(jié)果果查查找找，輸輸出出數(shù)數(shù)組組空空結(jié)結(jié)束束是是是是滁州學(xué)院本科學(xué)年設(shè)計(jì)8圖 3 哈夫曼樹構(gòu)造流程圖4 詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)各模塊分別為主調(diào)函數(shù)、建立 Huff

11、man Tree、生成 Huffman Tree 并寫入文件。具體過程如下：4.1 主調(diào)函數(shù)主調(diào)函數(shù)代碼解釋：這是 main 函數(shù)里的各個函數(shù)調(diào)用情況。 fileopen（string） ； /從 C 盤內(nèi)中讀取文件 num=jsq(string,cnt,str); /統(tǒng)計(jì)字符種類及各類字符出現(xiàn)的頻率 DhuffmanTree(HT,cnt,str); printf(“HuffmanTree 的初態(tài)：n”); print1(HT); /輸出哈夫曼樹的初態(tài) ChuffmanTree(HT,HC,cnt,str); /建立哈夫曼樹 HuffmanEncoding(HT,HC); /生成哈夫曼樹 p

12、rintf(“HuffmanTree 的終態(tài)：n”); print2(“HuffmanTree 的終態(tài)：n”);輸輸入入所所有有權(quán)權(quán)值值比比較較求求出出兩兩個個最最小小的的權(quán)權(quán)值值以以此此兩兩個個權(quán)權(quán)值值作作為為左左右右孩孩子子合合并并成成一一棵棵樹樹，并并將將這這棵棵樹樹放放入入到到權(quán)權(quán)值值域域中中，且且將將這這兩兩個個最最小小權(quán)權(quán)值值刪刪去去。權(quán)權(quán)值值域域的的個個數(shù)數(shù)為為1？是是哈哈夫夫曼曼樹樹構(gòu)構(gòu)造造成成功功否否結(jié)結(jié)束束滁州學(xué)院本科學(xué)年設(shè)計(jì)9 4.2 建立建立 HuffmanTree代碼解釋：該函數(shù)為在 htl.k中選擇 patent 為 0 且權(quán)值最小的根結(jié)點(diǎn)的算法，其序號為s1 和

13、s2.void select (HuffmanTree T,int k,int &s1,int &s2) /選取最小的根結(jié)點(diǎn)的函數(shù)int i, j;s2=s1 /以 s1 和 s2 作為兩個最小節(jié)點(diǎn)的變量for(i=1;i=k;i+) if(Ti.weightmin1 &Ti.patent=0) /利用此循環(huán)將最小結(jié)點(diǎn) s1 找到 j=i; min1=Ti.weight;s1=j; min1=32767;for(i=1;i=k;i+) /利用此循環(huán)將另一個最小結(jié)點(diǎn) s2 找到if(Ti.weightmin1 &Ti.patent=0 &i!=s1) j=

14、i; min1=Ti.weight; s2=j;/對所有的字母進(jìn)行統(tǒng)計(jì)種類和出現(xiàn)的次數(shù)int jsp(char *s,int cnt,char str) /str存放所有字符，cnt來存放每種字int i ,j,k; /母的權(quán)值char *p; /統(tǒng)計(jì)字符串中各種字母的個數(shù)以及字int temp27; /存每種字母的個數(shù)for(i=1;i=A&*p=Z) k=*p-64; /找到該字母的位置 tempk+; /統(tǒng)計(jì)各種字符的個數(shù)for（i=1,j=0;i=26;+i） if(tempi!=0) j+; strj=i+64; /送對應(yīng)字母到數(shù)組中 cntj=tempi; /存入對應(yīng)字母的

15、權(quán)值return j； /j 是輸入字母總數(shù)滁州學(xué)院本科學(xué)年設(shè)計(jì)10代碼解釋：下面函數(shù)用來構(gòu)造哈夫曼樹 HT。首先初始化哈夫曼樹，然后輸入前面統(tǒng)計(jì)的各個結(jié)點(diǎn)的權(quán)值，用 for 循環(huán)來構(gòu)造哈夫曼樹。void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt,char str) int i,s1 ,s2; for(i=1;i=2*num-1;i+) /初始化 HT，2*num-1 是指哈夫曼所有的節(jié)/點(diǎn)數(shù)目HTi.lchild=0;HTi.rchild=0; HTi.patent=0;HTi.weight=0;for(i=1;i=num;i+)

16、/輸入 num 個葉結(jié)點(diǎn)的權(quán)值 HTi.weight=cnti;for(i=num+1;i=2*num-1;i+) select(HT,i-1,s1,s2); HTs1.patent=i;HTs2.patent=i; HTi.lchild=s1;HTi.rchild=s2; HTiweight=HTs1.weight*HTs2.weight; /在 htl.k中選擇 patent 為 0 且權(quán)值最小的兩/個根結(jié)點(diǎn)，其序號為 s1 和 s2，i 為雙親for（i=0；i=num；i+） ； /輸入字符集中字符HCi.ch=stri; /字符種類i=1;while(i=num) printf(“字

17、符%c 次數(shù)：%d”,HCi.ch,cnti+); /輸出統(tǒng)計(jì)的情況 4.3 生成生成 Huffman 樹并寫入文件樹并寫入文件代碼解釋：根據(jù)所輸入的字符構(gòu)建哈夫曼樹 T 。void HuffmanEncoding (HuffmanTree T,HuffmanCode H) int c,p,i; /c 和 p 分別指示 t 中孩子和雙親 char cdn; /臨時存放編碼串 int start; /指示碼在 cd 中的起始位置 cdnum=0; /最后一位（第 num 個）放上串結(jié)束符 for(i=1;i0) /直至上溯到 tc是樹根為止 Cd-start=(Tp.lchild=c) ?0:1

18、;滁州學(xué)院本科學(xué)年設(shè)計(jì)11 c=p; /若 tc是 tp的左孩子則生成 0；否則生成1Strcpy(Hi.bits,*cdestart);Hi.len=num-start;代碼解釋：對 str 所代表的字符串進(jìn)行構(gòu)建哈夫曼樹并寫入文件。將翻譯的二進(jìn)制碼寫入文本文件。void coding(HuffmanCode HC, char *str) /對 str 所代表的字符串進(jìn)行編碼并寫入文件int i,j;FILE *fp; /定義文件的指針fp=fopen(“codefile.txt”,”w”); /打開文件的函數(shù)while(*str) /str 為編碼的指針 for(i=1;i=num;i+)

19、 if(HCi.ch=*str) for(j=0;j=HCi.len;j+) Fputc(HCI.bitsj,fp); break;str+; fclose(fp); /將文件關(guān)閉 5 調(diào)試與操作說明調(diào)試與操作說明本次測試是通過建立一個名為 file1.txt 的文本文檔，其中有一篇英文字母的文章期望程序能將其讀出至界面并實(shí)現(xiàn)其它相關(guān)的功能。運(yùn)行程序后，我們可以見到以下運(yùn)行界面。5.1 讀出文本讀出文本從 file1.txt 中讀取剛輸入的字符串并將其輸出到顯示屏如圖 3 所示。滁州學(xué)院本科學(xué)年設(shè)計(jì)12 圖 3 讀出文本示意圖5.2 輸出哈夫曼樹存儲結(jié)構(gòu)的初態(tài)輸出哈夫曼樹存儲結(jié)構(gòu)的初態(tài)下圖所示

20、的為哈夫曼樹的初態(tài)。其中的每行數(shù)字分別表示字符的權(quán)值，字符的雙親，字符的左孩子，字符的右孩子，而本圖為哈夫曼樹的初始化如圖 4 所示。圖 4 哈夫曼樹的初態(tài)圖5.3 輸出哈夫曼樹存儲結(jié)構(gòu)的終態(tài)輸出哈夫曼樹存儲結(jié)構(gòu)的終態(tài)該圖為哈夫曼樹的終態(tài)。本圖顯示的是哈夫曼樹的構(gòu)建以后的其字符的權(quán)值，雙親下標(biāo)，左孩子，右孩子如圖 5 所示。滁州學(xué)院本科學(xué)年設(shè)計(jì)13圖 5 哈夫曼的終態(tài)圖 1圖 6 哈夫曼樹的終態(tài)圖 2滁州學(xué)院本科學(xué)年設(shè)計(jì)145.4 輸出哈夫曼樹構(gòu)成后的抽象圖輸出哈夫曼樹構(gòu)成后的抽象圖 此圖的構(gòu)成首先是從權(quán)值域中選取最小的兩個權(quán)值，在此例中其分別為 4、4. 通過這兩個最小的權(quán)值合并成為雙親結(jié)點(diǎn)

21、 8.之后在將 8 插入到權(quán)值域中，同時將此兩個最小的結(jié)點(diǎn)刪除。按照此方法一步步的運(yùn)行下去最終使得權(quán)值域中只剩下唯一的一個權(quán)值，至此最優(yōu)二叉樹便建立好了。并且這個最后的結(jié)點(diǎn)便是整棵二叉樹中的根結(jié)點(diǎn)，在本例子中 456 便是整棵最優(yōu)二叉樹的根結(jié)點(diǎn)。圖 6 哈夫曼樹示意圖6 學(xué)年設(shè)計(jì)學(xué)年設(shè)計(jì)總結(jié)與體會總結(jié)與體會本學(xué)年設(shè)計(jì)的主要目的是要建立一個哈夫曼樹并將其實(shí)現(xiàn)。通過構(gòu)建哈夫曼編碼結(jié)構(gòu)體來解決一系列因編碼帶來的復(fù)雜問題。同時利用幾個數(shù)組來存儲字符出現(xiàn)的頻率和種類。且在此過程中也用到了哈夫曼編碼函數(shù)和哈夫曼構(gòu)建函數(shù)等，因而使得整個程序繁而不亂有條不紊的編輯和運(yùn)行在此次的學(xué)年設(shè)計(jì)中，對于構(gòu)建哈夫曼樹主要

22、的思想是通過記錄文件中字符的頻率來作為在哈夫曼樹構(gòu)造中必不可少的權(quán)值，再根據(jù)權(quán)值來構(gòu)造哈夫曼樹，進(jìn)而根據(jù)這棵建好的哈夫曼樹來進(jìn)行字符編碼，并將其存儲在所對應(yīng)的文件中。 滁州學(xué)院本科學(xué)年設(shè)計(jì)157 參考文獻(xiàn)參考文獻(xiàn) 1 嚴(yán)蔚敏，胡學(xué)剛.數(shù)據(jù)結(jié)構(gòu)（C 語言版）M. 清華大學(xué)出版社，20072 蘇仕華. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)M.機(jī)械工業(yè)出版社，20073 譚浩強(qiáng). C 語言程序設(shè)計(jì)教程M.高等教育出版社，20068 致謝致謝 對于老師詳細(xì)的指導(dǎo)和同學(xué)們的積極配合予以感謝，同時對各個參考文件的提供出版社以真誠的感謝。9 附錄附錄 # include# include# include# include/*

23、類型相關(guān)變量的定義*/# define n 100 /葉子結(jié)點(diǎn)數(shù)# define m 2*n-1 /哈夫曼樹中的結(jié)點(diǎn)數(shù)typedef struct char ch; /相關(guān)的字母 char bits9; /存放編碼位串 int len; /該字母編碼的長度CodeNode; /編碼的類型typedef CodeNode HuffmanCoden+1; /所有的葉子結(jié)點(diǎn)的編碼數(shù)組typedef struct int weight; /權(quán)值 int lchild,rchild,parent; /左右孩子及雙親指針HTNode; /哈夫曼樹結(jié)點(diǎn)的類型typedef HTNode HuffmanTre

24、em+1; /0 號單元不用int num; /統(tǒng)計(jì)每種字母出現(xiàn)的次數(shù)和種類數(shù)目/ *建立 HuffmanTree/*/void select(HuffmanTree T,int k,int &s1,int &s2) /在 ht1.k中選擇 parent 為 0 且權(quán)/值最小的兩個根結(jié)點(diǎn)的算法滁州學(xué)院本科學(xué)年設(shè)計(jì)16 /其序號為 s1 和 s2 int i,j;int min1=101; /min1 的數(shù)字無何意義只是初始值之后/用來記錄權(quán)值，i 為循環(huán)/最小權(quán)值的下標(biāo),k 為數(shù)組結(jié)點(diǎn)的總數(shù) for(i=1;i=k;i+) if (Ti.weightmin1 &Ti.p

25、arent=0) j=i; min1=Ti.weight; /賦權(quán)值 s1=j; min1=32767; /找到權(quán)值最小的其中之一 for (i=1; i=k; i+) if(Ti.weightmin1 &Ti.parent=0 & i!=s1)/不讓 s2 和 s1 的數(shù)組下標(biāo)重合 j=i ; min1=Ti.weight; /找到權(quán)值最小的其中之一 s2=j ;int jsq(char *s, int cnt ,char str) /str存放所有字符，cnt來存放每種字/母的權(quán)值 /統(tǒng)計(jì)字符串中各種字母的個數(shù)以及字/符的種類，s 為數(shù)組/的首地址指針 int i,j,k;

26、 char *p; int temp27; /存每種字母的個數(shù) for(i=1;i=A &*p=Z ) k=*p-64; /找到字母在數(shù)組中的下標(biāo) tempk+; /字母個數(shù)累加 for(i=1,j=0;i=26;+i) 滁州學(xué)院本科學(xué)年設(shè)計(jì)17 if( tempi !=0) j+; /j 為字母的總數(shù) strj=i+64; /送對應(yīng)的字母到數(shù)組中 cntj=tempi; /存入對應(yīng)字母的權(quán)值 return j; /j 是輸入字母總數(shù)void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt, char str) /構(gòu)造哈夫曼樹 HT

27、 int i,s1,s2; for(i=1;i=2*num-1;i+) /初始化 HT，2*num-1 是指哈夫曼樹所/有的結(jié)點(diǎn)數(shù)目 HTi.lchild=0;HTi.rchild=0; /初始化為根結(jié)點(diǎn) HTi.parent=0;HTi.weight=0; /初始化為根結(jié)點(diǎn) for(i=1;i=num;i+) /輸入 num 個葉子結(jié)點(diǎn)的權(quán)值 HTi.weight=cnti; /賦權(quán)值 for(i=num+1;i=2*num-1;i+) select(HT,i-1,s1,s2); /在 ht1.k中選擇 parent 為 0 且權(quán)值 /最小的兩個根結(jié)點(diǎn) HTs1.parent=i;HTs2.

28、parent=i; /其序號為 s1 和 s2 HTi.lchild=s1;HTi.rchild=s2; /i 為雙親 HTi.weight=HTs1.weight+HTs2.weight; for(i=0;i=num;i+) /輸入字符集的中字符 HCi.ch=stri; /字符的種類 i=1;while(i=num) printf(字符%c 次數(shù):%dn,HCi.ch,cnti+);/*生成 Huffman 樹并寫入文件*/void HuffmanEncoding(HuffmanTree T,HuffmanCode H)滁州學(xué)院本科學(xué)年設(shè)計(jì)18 /根據(jù)哈夫曼樹 T 求哈夫曼編碼 H int

29、 c,p,i; /c 和 p 分別指示 t 中孩子和雙親 char cdn; /臨時存放編碼串，n 為字母總數(shù) int start; /指示碼在 cd 中的起始位置 cdnum=0; /num 為葉子結(jié)點(diǎn)的總數(shù) for(i=1;i0) /直至上溯到 tc是樹根為止 /若 tc是 tp的左孩子，則生成 0，否則/生成 1 cd-start=(Tp.lchild=c)?0:1; c=p; /使得可以進(jìn)行循環(huán) strcpy(Hi.bits,&cdstart); Hi.len=num-start; void coding(HuffmanCode HC,char *str) /對 str 所代表

30、的字符串進(jìn)行構(gòu)建哈夫曼/樹并寫入文件 int i,j; FILE*fp; /定義文件的指針 fp=fopen(codefile.txt,w); /打開文件 的函數(shù) while (*str) for(i=1;i=num;i+) if(HCi.ch=*str) for(j=0;j=HCi.len;j+) fputc(HCi.bitsj,fp); break; str+; fclose(fp); /關(guān)閉文件 滁州學(xué)院本科學(xué)年設(shè)計(jì)19/*輸出 HuffmanTree 存儲結(jié)構(gòu)*/void print1(HuffmanTree HT) int x; for(x=1;x=2*num-1;x+) HTx.parent=0; HTx.lchild=0; HTx.rchild=0; printf(%11d %dt%dn,HTx.weight,HTx.parent,HTx.lchild,HTx.rchild