二叉樹(shù)的應(yīng)用實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)報(bào)告課程名稱 數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn) 實(shí)驗(yàn)項(xiàng)目二叉樹(shù)白應(yīng)用 實(shí)驗(yàn)儀器PC機(jī)系 另I專業(yè)班級(jí)/學(xué)號(hào)學(xué)生姓名實(shí)驗(yàn)日期成績(jī)指導(dǎo)教師實(shí)驗(yàn)三 . 二叉樹(shù)的應(yīng)用1. 實(shí)驗(yàn)?zāi)康模?掌握二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和常用算法。利用哈夫曼樹(shù)設(shè)計(jì)最優(yōu)壓縮編碼。2. 實(shí)驗(yàn)內(nèi)容：1) 編寫(xiě)函數(shù)，實(shí)現(xiàn)建立哈夫曼樹(shù)和顯示哈夫曼樹(shù)的功能。2) 編寫(xiě)函數(shù)，實(shí)現(xiàn)生成哈夫曼編碼的功能。3) 編寫(xiě)主函數(shù)，從終端輸入一段英文文本；統(tǒng)計(jì)各個(gè)字符出現(xiàn)的頻率，然后構(gòu)建哈夫曼樹(shù)并求出對(duì)應(yīng)的哈夫曼編碼；顯示哈夫曼樹(shù)和哈夫曼編碼。選做內(nèi)容：修改程序，選擇實(shí)現(xiàn)以下功能：4) 編碼：用哈夫曼編碼對(duì)一段英文文本進(jìn)行壓縮編碼，顯示編碼后的文本編碼序列；5) 統(tǒng)計(jì)

2、：計(jì)算并顯示文本的壓縮比例；6) 解碼：將采用哈夫曼編碼壓縮的文本還原為英文文本。3. 算法說(shuō)明：1) 二叉樹(shù)和哈夫曼樹(shù)的相關(guān)算法見(jiàn)講義。2) 編碼的方法是：從頭開(kāi)始逐個(gè)讀取文本字符串中的每個(gè)字符，查編碼表得到它的編碼并輸出。重復(fù)處理直至文本結(jié)束。3) 解碼的方法是：將指針指向哈夫曼樹(shù)的樹(shù)根，從頭開(kāi)始逐個(gè)讀取編碼序列中的每位，若該位為 1 則向右子樹(shù)走，為0 則向左子樹(shù)走。當(dāng)走到葉子節(jié)點(diǎn)時(shí)，取出節(jié)點(diǎn)中的字符并輸出。重新將指針?lè)诺綐?shù)根，繼續(xù)以上過(guò)程直至編碼序列處理完畢。4) 壓縮比例的計(jì)算：編碼后的文本長(zhǎng)度為編碼序列中的 0 和1, 的個(gè)數(shù)， 原文本長(zhǎng)度為字符數(shù)*8 。 兩者之比即為壓縮比。4.

3、 實(shí)驗(yàn)步驟：實(shí)現(xiàn)哈夫曼樹(shù)的編碼序列操作：int i=0,j=0;huffnode p;p=tree2*n-2;/ 序號(hào) 2*n-2 節(jié)點(diǎn)就是樹(shù)根節(jié)點(diǎn)while(hfmstri!='0')/ 從頭開(kāi)始掃描每個(gè)字符 ,直到結(jié)束while(p.lchild!=-1&&p.rchild!=-1)if(hfmstri='0')/ 為 0 則向左子樹(shù)走p=treep.lchild;/ 取出葉子節(jié)點(diǎn)中的字符else if(hfmstri='1')/ 為 1 則向右子樹(shù)走p=treep.rchild;/ 取出葉子節(jié)點(diǎn)中的字符i+;decodest

4、rj=p.data;j+;/ 對(duì)字符進(jìn)行譯碼 ,結(jié)果放在 decodestr字符串中p=tree2*n-2;/ 返回根節(jié)點(diǎn)程序修改后完整源代碼如下：#include <stdio.h>#include <stdlib.h>#include <string.h>#include <limits.h>/ 專門(mén)用于檢測(cè)整型數(shù)據(jù)數(shù)據(jù)類型的表達(dá)值范圍#define N 96 /ASCII 字符集包含至多 N 個(gè)可見(jiàn)字符typedef struct /Huffman 樹(shù)節(jié)點(diǎn)定義 char data; / 字符值int weight; / 權(quán)重int lchi

5、ld; / 左子結(jié)點(diǎn)int rchild; / 右子結(jié)點(diǎn) huffnode; /huffman 節(jié)點(diǎn)類型struct charcode int count; / 字符出現(xiàn)的次數(shù)（頻率）char codeN; / 字符的 Huffman 編碼 codesetN; /編碼表，長(zhǎng)為N,每項(xiàng)對(duì)應(yīng)一個(gè)ascii碼字符，下標(biāo)/i 的項(xiàng)對(duì)應(yīng) ascii 編碼為 i+32 的字符huffnode * CreateHufftree(char data, int weight, int n)建立 Huffman 樹(shù)的算法int i,k;int min1,min2,min_i1,min_i2;huffnode *t

6、ree;tree=(huffnode *)malloc(2*n-1)*sizeof(huffnode); / 為Huffman 樹(shù)分配 2n-1 個(gè)節(jié)點(diǎn)空間for (i=0;i<2*n-1;i+)/初 始化 ,將各字 符和其頻 率填入Huffman 樹(shù) ,作為葉子結(jié)點(diǎn)treei.lchild=treei.rchild=-1;if (i<n) treei.data=datai;treei.weight=weighti;else treei.data=' 'for (i=n;i<2*n-1;i+)/合并兩棵樹(shù),作 n-1 遍min1=min2=INT_MAX; /

7、INT_MAX 為最大值min_i1=min_i2=-1;for (k=0;k<i;k+)/查找定位兩個(gè)最小權(quán)重節(jié)點(diǎn)if (treek.weight>=0)/僅在根節(jié)點(diǎn)中找if (treek.weight<min1)min2=min1;min_i2=min_i1;min1=treek.weight;min_i1=k;elseif (treek.weight<min2) min2=treek.weight;min_i2=k;treei.weight=min1+min2; / 合并treemin_i1.weight *= -1;treemin_i2.weight *= -1

8、;treei.lchild=min_i1;treei.rchild=min_i2;return tree;void CreateHuffcode(huffnode tree, int i, char s)/ 已知 treei 節(jié)點(diǎn)的編碼序列為s,求該節(jié)點(diǎn)下所有葉子節(jié)點(diǎn)的編碼序列。 char s1N,c;if(i!=-1)if (treei.lchild=-1 && treei.rchild=-1) c=treei.data;strcpy(codesetc-32.code, s);else strcpy(s1, s); strcat(s1, "0");Crea

9、teHuffcode(tree, treei.lchild, s1);strcpy(s1, s); strcat(s1, "1");CreateHuffcode(tree, treei.rchild, s1);return;void PrintHufftree(huffnode tree, int n)/輸出 tree 中的Huffman 樹(shù)int i;printf("Huffman tree :n");printf("itValuetLchildtRchildtWeightn");for(i=2*n-2;i>=0;i-)pri

10、ntf("%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編碼表，逐個(gè)將str字符串中的字符轉(zhuǎn)化為它的huffman 編碼,結(jié)果編碼串放在hfmstr 字符串中int i, j;hfms

11、tr0='0'/ 把 hfmstr 串賦空i=0;while(stri!='0')/ 從第頭開(kāi)始掃描str 的每個(gè)字符,一直到該字符的結(jié)束j=stri-32;/ 執(zhí)行字符到 huffman 的轉(zhuǎn)換strcat(hfmstr, codesetj.code);把 codest編碼串添加到hfmstr 結(jié)尾處i+;/ 每次循環(huán)完 i 的值加 1void DeCoding(huffnode tree, int n, char hfmstr, char decodestr)/根據(jù) tree 數(shù)組中的 huffman 樹(shù) ,逐個(gè)對(duì) hfmstr 字符串中的字符進(jìn)行譯碼，結(jié)果

12、放在decodestr字符串中int i=0,j=0;huffnode p;p=tree2*n-2;/ 序號(hào) 2*n-2 節(jié)點(diǎn)就是樹(shù)根節(jié)點(diǎn)while(hfmstri!='0')/ 從頭開(kāi)始掃描每個(gè)字符,直到結(jié)束while(p.lchild!=-1&&p.rchild!=-1)/ 指針為空，兒子的值取完了if(hfmstri='0')/ 為 0 則向左子樹(shù)走p=treep.lchild;/ 取出葉子節(jié)點(diǎn)中的字符else if(hfmstri='1')/ 為 1 則向右子樹(shù)走p=treep.rchild;/ 取出葉子節(jié)點(diǎn)中的字符i+;

13、decodestrj=p.data;j+;/ 對(duì)字符進(jìn)行譯碼,結(jié)果放在decodestr字符串中p=tree2*n-2;/ 返回根節(jié)點(diǎn)void main()int i,j;huffnode * ht; /Huffman 樹(shù)char dataN; / 要編碼的字符集合int weightN; / 字符集合中各字符的權(quán)重 (頻率 )int n=0; /字符集合中字符的個(gè)數(shù)char str1000;/需輸入的原始字符串char hfm_str1000="" / 編碼后的字符串char decode_str1000=""/ 解碼后的字符串printf("

14、; 請(qǐng)輸入要轉(zhuǎn)換的字符串 n");gets(str);for(i=0;i<N;i+) / 初始化編碼表,頻率為0,編碼串為空串codeseti.count=0; codeseti.code0='0' i=0;while(stri!='0') /統(tǒng)計(jì)原始字符串中各字符出現(xiàn)的頻率,存入編碼表 j=stri-32; codesetj.count+; /codeset095 對(duì)應(yīng) ascii 碼 32127 的字 符 i+; for(i=0;i<N;i+) / 統(tǒng)計(jì)原始字符串中出現(xiàn)的字符個(gè)數(shù) if(codeseti.count!=0) n+; pr

15、intf(" 字符頻率統(tǒng)計(jì):n"); / 顯示統(tǒng)計(jì)結(jié)果for(i=0;i<N;i+) if(codeseti.count!=0) printf("%c:%d, ",i+32,codeseti.count); printf("n"); j=0; for(i=0;i<N;i+) / 生成要編碼的字符集合,以及權(quán)重if (codeseti.count!=0) dataj=i+32;weightj=codeseti.count;j+;ht=CreateHufftree(data,weight,n);/建立Huffman 樹(shù) ,根節(jié)點(diǎn)是 ht2*n-2PrintHufftree(ht,n); / 顯示 Huffman 樹(shù)的存儲(chǔ)結(jié)果CreateHuffcode(ht, 2*n-2, "");/ 以 ht2*n-2 為根 ,以空字符串為起始編碼字符串,求出各葉子節(jié)點(diǎn)的編碼字符串/顯示 codeset 中的 Huffman 編碼 ,參見(jiàn) " 顯示頻率統(tǒng)計(jì)結(jié)果"的代碼 .printf("haffman 編碼為 :n");for(i=0;i<N;i+)if(codeseti.count!=0)printf("%c:%sn",i+32,co