1、實 驗 報 告課程名稱 _數(shù)據(jù)結構上機實驗_實驗項目 _二叉樹的應用 _實驗儀器 _PC機_系 別_專 業(yè)_ 班級/學號_學生姓名 _ 實驗日期 _成 績 _ 指導教師 _實驗三.二叉樹的應用1. 實驗目的：掌握二叉樹的鏈式存儲結構和常用算法。利用哈夫曼樹設計最優(yōu)壓縮編碼。 2. 實驗內(nèi)容：1) 編寫函數(shù)，實現(xiàn)建立哈夫曼樹和顯示哈夫曼樹的功能。2) 編寫函數(shù)，實現(xiàn)生成哈夫曼編碼的功能。3) 編寫主函數(shù)，從終端輸入一段英文文本；統(tǒng)計各個字符出現(xiàn)的頻率，然后構建哈夫曼樹并求出對應的哈夫曼編碼；顯示哈夫曼樹和哈夫曼編碼。選做內(nèi)容：修改程序，選擇實現(xiàn)以下功能：4) 編碼：用哈夫曼編碼對一段英文文本進行

2、壓縮編碼，顯示編碼后的文本編碼序列；5) 統(tǒng)計：計算并顯示文本的壓縮比例；6) 解碼：將采用哈夫曼編碼壓縮的文本還原為英文文本。3. 算法說明：1) 二叉樹和哈夫曼樹的相關算法見講義。2) 編碼的方法是：從頭開始逐個讀取文本字符串中的每個字符，查編碼表得到它的編碼并輸出。重復處理直至文本結束。3) 解碼的方法是：將指針指向哈夫曼樹的樹根，從頭開始逐個讀取編碼序列中的每位，若該位為1則向右子樹走，為0則向左子樹走。當走到葉子節(jié)點時，取出節(jié)點中的字符并輸出。重新將指針放到樹根，繼續(xù)以上過程直至編碼序列處理完畢。4) 壓縮比例的計算：編碼后的文本長度為編碼序列中的0和1,的個數(shù)，原文本長度為字符數(shù)*

3、8。兩者之比即為壓縮比。4. 實驗步驟：實現(xiàn)哈夫曼樹的編碼序列操作： int i=0,j=0;huffnode p;p=tree2*n-2;/序號2*n-2節(jié)點就是樹根節(jié)點while(hfmstri!=0)/從頭開始掃描每個字符,直到結束while(p.lchild!=-1&p.rchild!=-1)if(hfmstri=0)/為0則向左子樹走p=treep.lchild;/取出葉子節(jié)點中的字符else if(hfmstri=1)/為1則向右子樹走p=treep.rchild;/取出葉子節(jié)點中的字符i+;decodestrj=p.data;j+;/對字符進行譯碼,結果放在decodestr字符

4、串中p=tree2*n-2;/返回根節(jié)點程序修改后完整源代碼如下： #include #include #include #include /專門用于檢測整型數(shù)據(jù)數(shù)據(jù)類型的表達值范圍#define N 96 /ASCII字符集包含至多N個可見字符typedef struct /Huffman樹節(jié)點定義 char data; /字符值int weight; /權重int lchild; /左子結點int rchild; /右子結點 huffnode; /huffman節(jié)點類型struct charcode int count; /字符出現(xiàn)的次數(shù)(頻率)char codeN; /字符的Huffma

5、n編碼 codesetN; /編碼表,長為N,每項對應一個ascii碼字符,下標i的項對應ascii編碼為i+32的字符huffnode * CreateHufftree(char data, int weight, int n) /建立Huffman樹的算法int i,k;int min1,min2,min_i1,min_i2;huffnode *tree;tree=(huffnode *)malloc(2*n-1)*sizeof(huffnode); /為Huffman樹分配2n-1個節(jié)點空間for (i=0;i2*n-1;i+) /初始化,將各字符和其頻率填入Huffman樹,作為葉子結

6、點 treei.lchild=treei.rchild=-1;if (in) treei.data=datai;treei.weight=weighti;else treei.data= ; for (i=n;i2*n-1;i+) /合并兩棵樹,作n-1遍min1=min2=INT_MAX; /INT_MAX為最大值min_i1=min_i2=-1;for (k=0;k=0) /僅在根節(jié)點中找if (treek.weightmin1)min2=min1;min_i2=min_i1;min1=treek.weight;min_i1=k;else if (treek.weight=0;i-) pr

7、intf(%dt,i); printf(%ct,treei.data); printf(%dt,treei.lchild); printf(%dt,treei.rchild); printf(%dt,treei.weight); printf(n); void EnCoding(char str, char hfmstr)/根據(jù)codeset編碼表,逐個將str字符串中的字符轉化為它的huffman編碼,結果編碼串放在hfmstr字符串中int i, j;hfmstr0=0;/把hfmstr串賦空i=0;while(stri!=0)/從第頭開始掃描str的每個字符,一直到該字符的結束 j=st

8、ri-32;/執(zhí)行字符到huffman的轉換strcat(hfmstr, codesetj.code);/把codest編碼串添加到hfmstr結尾處i+;/每次循環(huán)完i的值加1void DeCoding(huffnode tree, int n, char hfmstr, char decodestr)/根據(jù)tree數(shù)組中的huffman樹,逐個對hfmstr字符串中的字符進行譯碼,結果放在decodestr字符串中int i=0,j=0;huffnode p;p=tree2*n-2;/序號2*n-2節(jié)點就是樹根節(jié)點while(hfmstri!=0)/從頭開始掃描每個字符,直到結束while

9、(p.lchild!=-1&p.rchild!=-1)/指針為空，兒子的值取完了if(hfmstri=0)/為0則向左子樹走p=treep.lchild;/取出葉子節(jié)點中的字符else if(hfmstri=1)/為1則向右子樹走p=treep.rchild;/取出葉子節(jié)點中的字符i+;decodestrj=p.data;j+;/對字符進行譯碼,結果放在decodestr字符串中p=tree2*n-2;/返回根節(jié)點void main() int i,j;huffnode * ht; /Huffman樹char dataN; /要編碼的字符集合int weightN; /字符集合中各字符的權重(

10、頻率)int n=0; /字符集合中字符的個數(shù)char str1000; /需輸入的原始字符串 char hfm_str1000=; /編碼后的字符串char decode_str1000=;/解碼后的字符串printf(請輸入要轉換的字符串n);gets(str);for(i=0;iN;i+) /初始化編碼表,頻率為0,編碼串為空串codeseti.count=0;codeseti.code0=0;i=0; while(stri!=0) /統(tǒng)計原始字符串中各字符出現(xiàn)的頻率,存入編碼表j=stri-32;codesetj.count+; /codeset095對應ascii碼32127的字符i

11、+;for(i=0;iN;i+) /統(tǒng)計原始字符串中出現(xiàn)的字符個數(shù)if(codeseti.count!=0) n+;printf(字符頻率統(tǒng)計:n); /顯示統(tǒng)計結果for(i=0;iN;i+) if(codeseti.count!=0) printf(%c:%d, , i+32, codeseti.count);printf(n);j=0;for(i=0;iN;i+) /生成要編碼的字符集合,以及權重if (codeseti.count!=0) dataj=i+32;weightj=codeseti.count; j+;ht=CreateHufftree(data,weight,n); /建立Huffman樹,根節(jié)點是ht2*n-2 PrintHufftree(ht,n); /顯示Huffman樹的存儲結果CreateHuffcode(ht, 2*n-2, ); /以ht2*n-2為根,以空字符串為起始編碼字符串,求出各葉子節(jié)點的編碼字符串/顯示codeset中的Huffman編碼,參見顯示頻率統(tǒng)計結果的代碼. printf(haffman編碼為:n); for(i=0;iN;i+)if(codeseti.count!=0) printf(%c:%sn,i+32,codeseti.code );EnCoding(str, hfm_str);