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

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

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

3、2011 年 8 月 29 日 2011 年 8 月 29 日 構(gòu)建哈夫曼樹(shù)和收集相關(guān)資料6 2011 年 8 月 29 日 2011 年 8 月 31 日 編輯代碼分配任務(wù)等其他相關(guān)事宜 指導(dǎo)教師簽字： 年 月 日教研室審核意見(jiàn)：教研室主任簽字： 年 月 日滁州學(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樹(shù)并寫(xiě)入文件.105 調(diào)調(diào)試試與與操操作作說(shuō)說(shuō)明明.115.1 讀出文本.1

4、15.2 輸出哈夫曼樹(shù)存儲(chǔ)結(jié)構(gòu)的初態(tài).125.3 輸出哈夫曼樹(shù)存儲(chǔ)結(jié)構(gòu)的終態(tài).125.4 輸出哈夫曼樹(shù)構(gòu)成后的抽象圖.146學(xué)學(xué)年年設(shè)設(shè)計(jì)計(jì)總總結(jié)結(jié)與與體體會(huì)會(huì).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é)省信息的存儲(chǔ)和傳遞速度，人們便創(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ù)

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

6、符出現(xiàn)次數(shù)作為權(quán)值，調(diào)用 ChuffmanTree()函數(shù)構(gòu)建哈夫曼樹(shù)，并調(diào)用 print1()和 print2()函數(shù)將哈夫曼的存儲(chǔ)結(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，編碼長(zhǎng)度為 Li，電文中有 n 種字符，則電文編碼總長(zhǎng)度為（W1*L1）+(W2*L2)+.(Wi*Li)。若將此對(duì)應(yīng)到二叉樹(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ù)。該系統(tǒng)將實(shí)現(xiàn)以下幾大功能：從硬

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

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

9、編碼。 圖 1 哈夫曼算法實(shí)現(xiàn)流程圖 哈夫曼編碼是通過(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)的開(kāi)開(kāi)始始讀讀取取輸輸入入的的數(shù)數(shù)據(jù)據(jù)統(tǒng)統(tǒng)計(jì)計(jì)字字符符的的頻頻率率輸輸入入字字符符排排序序建建立立哈哈夫夫曼曼樹(shù)樹(shù)輸輸入入字字符符編編碼碼結(jié)結(jié)束束滁州學(xué)院本科學(xué)年設(shè)計(jì)7數(shù)值是 0 還是 1 并進(jìn)行記錄，進(jìn)而可以將每個(gè)途徑的結(jié)點(diǎn)所對(duì)應(yīng)的數(shù)值記錄在數(shù)組中。直到所有的結(jié)點(diǎn)都遍歷了一遍的時(shí)候，整個(gè)編碼的過(guò)程也就完成了，而此時(shí)數(shù)組中所存儲(chǔ)的0，1 代碼便是每一個(gè)結(jié)點(diǎn)所對(duì)應(yīng)的編碼圖 2 哈夫曼編碼流程圖(6) 構(gòu)

10、造哈夫曼樹(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ù)的構(gòu)造便順利的完成了，而這唯一的一個(gè)權(quán)值便是整棵二叉樹(shù)的根結(jié)點(diǎn)。開(kāi)開(kāi)始始數(shù)數(shù)組組初初始始化化當(dāng)當(dāng)前前位位置置編編碼碼當(dāng)當(dāng)前前位位置置進(jìn)進(jìn)數(shù)數(shù)組組換換下下一一個(gè)個(gè)位位置置切切換換下下一一個(gè)個(gè)位位置置繼繼續(xù)續(xù)是是否否為為終終點(diǎn)點(diǎn)結(jié)結(jié)果果查查找找，輸輸出出數(shù)數(shù)組組空空結(jié)結(jié)束束是是是是滁州學(xué)院本科學(xué)年設(shè)計(jì)8圖 3 哈夫曼樹(shù)構(gòu)造流程圖4 詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)各模塊分別為主調(diào)函數(shù)、建立 Huff

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

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

13、s2.void select (HuffmanTree T,int k,int &s1,int &s2) /選取最小的根結(jié)點(diǎn)的函數(shù)int i, j;s2=s1 /以 s1 和 s2 作為兩個(gè)最小節(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)將另一個(gè)最小結(jié)點(diǎn) s2 找到if(Ti.weightmin1 &Ti.patent=0 &i!=s1) j=

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

15、權(quán)值return j； /j 是輸入字母總數(shù)滁州學(xué)院本科學(xué)年設(shè)計(jì)10代碼解釋：下面函數(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ù)。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 個(gè)葉結(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)值最小的兩/個(gè)根結(jié)點(diǎn)，其序號(hào)為 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 樹(shù)并寫(xiě)入文件樹(shù)并寫(xiě)入文件代碼解釋：根據(jù)所輸入的字符構(gòu)建哈夫曼樹(shù) T 。void HuffmanEncoding (HuffmanTree T,HuffmanCode H) int c,p,i; /c 和 p 分別指示 t 中孩子和雙親 char cdn; /臨時(shí)存放編碼串 int start; /指示碼在 cd 中的起始位置 cdnum=0; /最后一位（第 num 個(gè)）放上串結(jié)束符 for(i=1;i0) /直至上溯到 tc是樹(shù)根為止 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;代碼解釋：對(duì) str 所代表的字符串進(jìn)行構(gòu)建哈夫曼樹(shù)并寫(xiě)入文件。將翻譯的二進(jìn)制碼寫(xiě)入文本文件。void coding(HuffmanCode HC, char *str) /對(duì) str 所代表的字符串進(jìn)行編碼并寫(xiě)入文件int i,j;FILE *fp; /定義文件的指針fp=fopen(“codefile.txt”,”w”); /打開(kāi)文件的函數(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)試與操作說(shuō)明調(diào)試與操作說(shuō)明本次測(cè)試是通過(guò)建立一個(gè)名為 file1.txt 的文本文檔，其中有一篇英文字母的文章期望程序能將其讀出至界面并實(shí)現(xiàn)其它相關(guān)的功能。運(yùn)行程序后，我們可以見(jiàn)到以下運(yùn)行界面。5.1 讀出文本讀出文本從 file1.txt 中讀取剛輸入的字符串并將其輸出到顯示屏如圖 3 所示。滁州學(xué)院本科學(xué)年設(shè)計(jì)12 圖 3 讀出文本示意圖5.2 輸出哈夫曼樹(shù)存儲(chǔ)結(jié)構(gòu)的初態(tài)輸出哈夫曼樹(shù)存儲(chǔ)結(jié)構(gòu)的初態(tài)下圖所示

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

21、 8.之后在將 8 插入到權(quán)值域中，同時(shí)將此兩個(gè)最小的結(jié)點(diǎn)刪除。按照此方法一步步的運(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)。圖 6 哈夫曼樹(shù)示意圖6 學(xué)年設(shè)計(jì)學(xué)年設(shè)計(jì)總結(jié)與體會(huì)總結(jié)與體會(huì)本學(xué)年設(shè)計(jì)的主要目的是要建立一個(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)的頻率和種類。且在此過(guò)程中也用到了哈夫曼編碼函數(shù)和哈夫曼構(gòu)建函數(shù)等，因而使得整個(gè)程序繁而不亂有條不紊的編輯和運(yùn)行在此次的學(xué)年設(shè)計(jì)中，對(duì)于構(gòu)建哈夫曼樹(shù)主要

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

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

24、em+1; /0 號(hào)單元不用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)/值最小的兩個(gè)根結(jié)點(diǎn)的算法滁州學(xué)院本科學(xué)年設(shè)計(jì)16 /其序號(hào)為 s1 和 s2 int i,j;int min1=101; /min1 的數(shù)字無(wú)何意義只是初始值之后/用來(lái)記錄權(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來(lái)存放每種字/母的權(quán)值 /統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字/符的種類，s 為數(shù)組/的首地址指針 int i,j,k;

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

27、 int i,s1,s2; for(i=1;i=2*num-1;i+) /初始化 HT，2*num-1 是指哈夫曼樹(shù)所/有的結(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 個(gè)葉子結(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)值 /最小的兩個(gè)根結(jié)點(diǎn) HTs1.parent=i;HTs2.

28、parent=i; /其序號(hào)為 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 樹(shù)并寫(xiě)入文件*/void HuffmanEncoding(HuffmanTree T,HuffmanCode H)滁州學(xué)院本科學(xué)年設(shè)計(jì)18 /根據(jù)哈夫曼樹(shù) T 求哈夫曼編碼 H int

29、 c,p,i; /c 和 p 分別指示 t 中孩子和雙親 char cdn; /臨時(shí)存放編碼串，n 為字母總數(shù) int start; /指示碼在 cd 中的起始位置 cdnum=0; /num 為葉子結(jié)點(diǎn)的總數(shù) for(i=1;i0) /直至上溯到 tc是樹(shù)根為止 /若 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) /對(duì) str 所代表

30、的字符串進(jìn)行構(gòu)建哈夫曼/樹(shù)并寫(xiě)入文件 int i,j; FILE*fp; /定義文件的指針 fp=fopen(codefile.txt,w); /打開(kāi)文件 的函數(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 存儲(chǔ)結(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