試驗(yàn)四二叉樹的應(yīng)用-哈夫曼編碼--大山

1、網(wǎng)絡(luò)092李雨山200900824225實(shí)驗(yàn)四哈夫曼樹及其的應(yīng)用一、實(shí)驗(yàn)?zāi)康?. 在二叉樹基本操作的基礎(chǔ)上，掌握對(duì)二叉樹的一些其它操作的 具體實(shí)現(xiàn)方法。2. 掌握構(gòu)造哈夫曼樹以及哈夫曼編碼的方法。3. 熟練掌握哈夫曼樹(最優(yōu)二叉樹)特征及其應(yīng)用二、實(shí)驗(yàn)內(nèi)容題目一、哈夫曼樹和哈夫曼編碼：從終端輸入若干個(gè)字符，統(tǒng)計(jì)(或指定)字符出現(xiàn)的頻率，將 字符出現(xiàn)的頻率作為結(jié)點(diǎn)的權(quán)值，建立哈夫曼樹，然后對(duì)各字符進(jìn) 行哈夫曼編碼。最后打印哈夫曼樹和對(duì)應(yīng)的哈夫曼編碼。設(shè)計(jì)要求： 哈夫曼殊和哈夫曼編碼的存儲(chǔ)表示參考教材事例 在程序中構(gòu)造四個(gè)子程序?yàn)?int freqchar(char *st);/*統(tǒng)計(jì)字符出現(xiàn)的頻

2、率*/ void CreateHuffmanTree(HuffmanTree &,int*,int); /生成哈夫曼樹 void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); / 對(duì)哈夫曼樹進(jìn)行編碼 void PrintHuffmanCode(HuffmanCode,int*,int,char*);/顯示哈夫曼編碼 void Select(HuffmanTree,int,int&,int&); /在數(shù)組中尋找權(quán)值最小的兩個(gè)結(jié)點(diǎn)三、實(shí)驗(yàn)步驟、數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計(jì)描述1.重點(diǎn)：統(tǒng)計(jì)字符出現(xiàn)的頻率并作為權(quán)值int f

3、reqchar(char *st)/*統(tǒng)計(jì)字符出現(xiàn)的頻率 */i nt n=0;/統(tǒng)計(jì)字符的種類memset (num ,0,sizeof( nu m);f or(int i=0;i<M;i+)int t=sti-'a：nu mt+;f or(i nt j=0;j<27;j+)if(n umj!=0)n+;return n;2.將構(gòu)造一棵哈夫曼樹HTvoid CreateHuffma nTree(Huffma nTree &H T,i nt *w,i nt n)/w存放n個(gè)結(jié)點(diǎn)的權(quán)值，將構(gòu)造一棵哈夫曼樹HTi nt i,m;i nt s1,s2;Huffma nTr

4、ee p;i f(n<=1) return;m=2* n-1; n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，有2* n-1個(gè)結(jié)點(diǎn)HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/ 開辟 2*n 各結(jié)點(diǎn)空間f or(p=HT+1,i=1;i<=n;+i,+p,+w) / 進(jìn)行初始化p->weight=*w;p->pare nt=0;p->lchild=0;p->rchild=0;f or(;i<=m;+i,+p)p->weight=0;p->pare nt=0;p->lchild=0;p->rchild=0;f

5、or(i=n+1;i<=m;+i) /建哈夫曼樹Select(HT,i-1,s1,s2);/從HT1.i-1 中選擇pare nt為0且weight最小的兩個(gè)結(jié)點(diǎn)，其 序號(hào)分別為s1和s2HTs1.parent=i;HTs2.parent=i; / 修改 s1 和 s2 結(jié)點(diǎn)的父指針pare ntHTichild=s1; HTi.rchild=s2; /修改i結(jié)點(diǎn)的左右孩子指針HTi.weight=HTs1.weight+HTs2.weight; /修改權(quán)值3. 哈夫曼編碼void Huffma nCodi ng(Huffma nTree HT,Huffma nCode & HC

6、,i nt n)/將有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹HT進(jìn)行編碼，所編的碼存放在 HC中/方法是從葉子到根逆向求每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼i nt i,c,f,start;char *cd;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/ 分配 n 個(gè)編碼的頭指針向量cd=(char *)malloc( n*sizeof(char); /開辟一個(gè)求編碼的工作空間cd n-1='0： /編碼結(jié)束符f or(i=1;i<=n;+i) /逐個(gè)地求哈夫曼編碼/從葉子到start =n-1; /編碼結(jié)束位置for(c=i,f=HTi.pare nt;f!=O;c

7、=f,f=HTf.pare nt)根逆向求編碼if(HTf.lchild=c)cd-start='0' /若是左孩子編為'0'elsecd-start='1' /若是右孩子編為'1'HCi=(char *)malloc(n-start)*sizeof(char);/ 為第 i 個(gè)編碼分配空間strcpy(HCi,&cdstart); /將編碼從 cd 復(fù)制到 HC中 f ree(cd); / 釋放工作空間 4. 顯示有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹的編碼表void Prin tHuffma nCode(Huffma nCode H

8、C,i nt *w,i nt n,char *c1)/顯示有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹的編碼表i nt i;printf("HuffmanCode is :n");cout<<"字符"<<"-"<<"權(quán)值"<<"-"<<"哈弗曼編碼"<<endl; f or(i=1;i<=n ;i+)cout<<c1i-1<<"-"<<wi-1<<&q

9、uot;-"<<HCi<<e ndl;5. 找最小權(quán)值的兩個(gè)結(jié)點(diǎn)void Select(HuffmanTree HT,int t,int&s1,int&s2)/在HT1.t 中選擇pare nt不為0且權(quán)值最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分 別為si和s2i nt i,m,n;m=n=10000;f or(i=1;i<=t;i+)if(HTi.pare nt=0&&( HTi.weight<m|HTi.weight <n)if(m<n)n=HTi.weight;s2=i;elsem=HTi.weight;s1=i;

10、i f(s1>s2) /s1 放較小的序號(hào)i=s1;s1=s2;s2=i;、函數(shù)調(diào)用及主函數(shù)設(shè)計(jì)void mai n()HUffmanTree HT; /哈夫曼樹 HTHUffma nCode HC; /哈夫曼編碼表 HCi nt n; /n是哈夫曼樹葉子結(jié)點(diǎn)數(shù)(字符種類的個(gè)數(shù))i nt *w; /w存放葉子結(jié)點(diǎn)權(quán)值char *c1;/c1存放字符串中字符的種類char aM;/用于儲(chǔ)存輸入的字符串cout<<"請(qǐng)輸入字符串："while(c in> >a)n=freqchar(a);/得到字符種類的個(gè)數(shù)w=(i nt*)malloc( n*s

11、izeof(i nt); /開辟空間存放權(quán)值c1=(char*)malloc( n*sizeof(char); /開辟空間存放權(quán)值int j;for(i nt i=0;i <n ;i+)for(j=i；j<27；j+)if(n umj!=0)wi=nu mj;得到權(quán)值c1i=j+'a'得到字符種類break;/字符與權(quán)值相對(duì)應(yīng)CreateHuffma nTree(HT,w ,n); /生成哈夫曼樹Huffma nCodi ng(HT,HC, n); /進(jìn)行哈夫曼編碼Prin tHuffma nCode(HC,w, n,c1); /顯示哈夫曼編碼printf(”請(qǐng)輸入

12、字符串：");、程序調(diào)試及運(yùn)行結(jié)果分析輸入：abbcccdddd結(jié)果、實(shí)驗(yàn)總結(jié)通過這次實(shí)驗(yàn)，我對(duì)二叉樹和哈希曼 樹有了更好的 認(rèn)識(shí)。在實(shí)驗(yàn)過 程中，我掌 握了哈希曼 樹的構(gòu)造方法，哈希曼編碼的方法，學(xué)會(huì)了如何將理論知識(shí)傳換成實(shí)際 應(yīng)用。同時(shí)，在解決程序中遇到的一些 問題的同時(shí)，我也對(duì)調(diào)試技巧有了更好的掌 握，分析問題的能力也略有提高。在實(shí)驗(yàn)中，我遇到了許多難點(diǎn)，比如：統(tǒng)計(jì)字符的權(quán)值，就需要我們有扎實(shí)的 基礎(chǔ)，需要有靈活的頭腦，只有不斷的練習(xí)，不斷的訓(xùn)練，我們才能處理各種問題。在以后的學(xué)習(xí)中，我要不斷的努力，多聯(lián)系，多思考，我相信我能有所進(jìn)步的。四、主要算法流程圖及程序清單1、程序清單

13、#in clude <stdio.h>#in elude <stdlib.h>#in elude <stri ng.h>#i nclude <iostream.h>#define M 1000typedef structint weight; /結(jié)點(diǎn)權(quán)值in t pare nt,lchild,rchild; /結(jié)點(diǎn)的父指針，左右孩子指針HTNode,*Huffma nTree; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹typedef char *Huffma nCode; II動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表int num27;統(tǒng)計(jì)字符出現(xiàn)的次數(shù)并作為權(quán)值int

14、freqchar(char *st);I*統(tǒng)計(jì)字符出現(xiàn)的頻率 */void CreateHuffma nTree(Huffma nTree & ,i nt*,i nt ); II生成哈夫曼樹void Huffma nCodi ng(Huffma nTree,Huffma nCode &int ); II對(duì)哈夫曼樹進(jìn)行編碼void Prin tHuffma nCode(Huffma nCode,i nt*,i nt,char*); II顯示哈夫曼編碼void Select(Huffma nTree,i nt,i nt&,int&); /在數(shù)組中尋找權(quán)值最小的兩個(gè)結(jié)

15、點(diǎn)void mai n()HuffmanTree HT; II哈夫曼樹 HTHuffma nCode HC; II哈夫曼編碼表 HCint n; IIn是哈夫曼樹葉子結(jié)點(diǎn)數(shù)(字符種類的個(gè)數(shù))int *w; IIw存放葉子結(jié)點(diǎn)權(quán)值char *c1;IIc1存放字符串中字符的種類char aM;II用于儲(chǔ)存輸入的字符串cout<<"請(qǐng)輸入字符串："while(ci n> >a)n=freqchar(a);II得到字符種類的個(gè)數(shù)w=(i nt*)malloc( n*sizeof(i nt); II開辟空間存放權(quán)值c1=(char*)malloc( n*si

16、zeof(char); II開辟空間存放權(quán)值int j;for(i nt i=0;i <n ;i+)for(j=i;j<27;j+)if(n umj!=0)wi=nu mj;得到權(quán)值c1i=j+'a'得到字符種類break;/字符與權(quán)值相對(duì)應(yīng)CreateHuffma nTree(HT,w ,n); /生成哈夫曼樹Huffma nCodi ng(HT,HC, n); /進(jìn)行哈夫曼編碼Prin tHuffma nCode(HC,w, n,c1); /顯示哈夫曼編碼printf(”請(qǐng)輸入字符串：");int freqchar(char *st)/*統(tǒng)計(jì)字符出現(xiàn)的

17、頻率 */int n=0;/ 統(tǒng)計(jì)字符的種類memset( nu m,0,sizeof( nu m);for(int i=0;i<M;i+)int t=sti-'a'nu mt+;for(i nt j=0;j<27;j+)if(n umj!=0)n+;return n;void CreateHuffma nTree(Huffma nTree & HT,i nt *w,i nt n)/w存放n個(gè)結(jié)點(diǎn)的權(quán)值，將構(gòu)造一棵哈夫曼樹HTint i,m;int s1,s2;Huffma nTree p;if(n<=1) return;m=2* n-1; n個(gè)葉子結(jié)

18、點(diǎn)的哈夫曼樹，有2* n-1個(gè)結(jié)點(diǎn)HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/ 開辟 2*n 各結(jié)點(diǎn)空間for(p=HT+1,i=1;i<=n;+i,+p,+w) /進(jìn)行初始化p->weight=*w;p->pare nt=0; p->lchild=0; p->rchild=0; for(;i<=m;+i,+p) p_>weight=0; p->pare nt=0; p->lchild=0; p->rchild=0;建哈夫曼樹for(i=n+1;i<=m;+i) /Select(HT,

19、i-1,s1,s2);/從HT1.i-1 中選擇pare nt為0且weight最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為s1和s2HTs1.parent=i;HTs2.parent=i;/ 修改 s1 和 s2 結(jié)點(diǎn)的父指針pare ntHTi.lchild=s1;HTi.rchild=s2;/ 修改 i 結(jié)點(diǎn)的左右孩子指針HTi.weight=HTs1.weight+HTs2.weight; /修改權(quán)值void Huffma nCodi ng(Huffma nTree HT,Huffma nCode & HC,i nt n)將有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹 HT進(jìn)行編碼，所編的碼存放在HC中 /方法是

20、從葉子到根逆向求每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼 int i,c,f,start;char *cd;HC=(HuffmanCode)malloc(n+1)*sizeof(char*); / 分配 n 個(gè)編碼的頭指針向量cd=(char *)malloc( n*sizeof(char); /開辟一個(gè)求編碼的工作空間cd n-1='0' /編碼結(jié)束符for(i=1;i<=n ;+i) /逐個(gè)地求哈夫曼編碼start =n-1; /編碼結(jié)束位置for(c=i,f=HTi.parent;f!=O;c=f,f=HTf.parent)/ 從葉子到根逆向求編碼if(HTf.lchild=c) cd-start='0' /若是左孩子編為'0'elsecd-start='1' /若是右孩子編為'1'HCi=(char *)malloc(n-start)*sizeof(char);/ 為第 i 個(gè)編碼分配空間strcpy(HCi,&cdstart); /將編碼從 cd