北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)—Huffman編碼解碼器

1、.數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： _Huffman編碼 / 解碼器 _學(xué)生姓名： _班級： _班內(nèi)序號： _學(xué)號： _.日期： _.1實(shí)驗(yàn)要求利用二叉樹結(jié)構(gòu)實(shí)現(xiàn)哈夫曼編/ 解碼器?；疽螅?.初始化 (Init) ：能夠?qū)斎氲娜我忾L度的字符串s 進(jìn)行統(tǒng)計(jì)， 統(tǒng)計(jì)每個(gè)字符的頻度， 并建立哈夫曼樹2.建立編碼表 (CreateTable) ：利用已經(jīng)建好的哈夫曼樹進(jìn)行編碼，并將每個(gè)字符的編碼輸出。3.編碼 (Encoding) ：根據(jù)編碼表對輸入的字符串進(jìn)行編碼，并將編碼后的字符串輸出。4.譯碼 (Decoding) ：利用已經(jīng)建好的哈夫曼樹對編碼后的字符串進(jìn)行譯碼，并輸出譯碼結(jié)果。5.計(jì)算輸入的

2、字符串編碼前和編碼后的長度，并進(jìn)行分析，討論赫夫曼編碼的壓縮效果。2. 程序分析2.1 存儲結(jié)構(gòu)靜態(tài)三叉鏈表WeightLchildRchildparent2.2 程序流程(或程序結(jié)構(gòu)、或類關(guān)系圖等表明程序構(gòu)成的內(nèi)容，一般為流程圖等 )流程圖開始輸入進(jìn)行編碼的字符串統(tǒng)計(jì)各個(gè)字符的頻度，并對各葉子節(jié)點(diǎn)的權(quán)重賦值.初始化各節(jié)點(diǎn)的Lchild ， Rchild 和 parent進(jìn)行哈弗曼編碼是否是否最后一個(gè)字符該節(jié)點(diǎn)是否為根節(jié)點(diǎn)否是判斷雙親輸出各字符編碼節(jié)點(diǎn)若為左孩子若為右孩子編碼前插入 0編碼前插入 1對字符串進(jìn)行編碼找到當(dāng)前字符編碼，復(fù)制到總編碼中否是否最后一個(gè)字符是輸出各字符串編碼對哈弗曼碼進(jìn)

3、行譯碼輸出譯碼結(jié)果.計(jì)算分析內(nèi)存占用情況輸出占用情況結(jié)束偽代碼1.輸入進(jìn)行編碼的字符串2.遍歷字符串，并為葉子節(jié)點(diǎn)權(quán)重賦值3.依次對各字符進(jìn)行哈弗曼編碼，自下往上，若是雙親節(jié)點(diǎn)左孩子則編碼前插入 0 ，若是雙親節(jié)點(diǎn)右孩子則編碼錢插入 1。4.顯示各字符的哈弗曼編碼。5.對字符串進(jìn)行編碼，挨個(gè)遍歷字符，找到相應(yīng)的編碼，復(fù)制到總的編碼里，最后輸出字符串的編碼。6.對字符串的哈弗曼碼進(jìn)行譯碼。自上往下，若是0，則遞歸到左孩子，若是1，則遞歸到右孩子，知道葉子節(jié)點(diǎn)，輸出該葉子節(jié)點(diǎn)代表字符，再繼續(xù)遍歷。7.分析內(nèi)存占用情況。若用ASCII 編碼，每個(gè)字符占1 個(gè)字節(jié)，即8bit ，該情況下占用內(nèi)存就是（

4、字符長度）*8 。若用哈弗曼編碼，占用內(nèi)存是各（字符頻度）*（每個(gè)字符占用位數(shù)）之和。2.3 關(guān)鍵算法分析該程序關(guān)鍵算法即哈弗曼編碼，語句如下：void CHTree:huffmancode()int i;if(n<=1)return;m=2*n-1;for(i=1;i<=n;i+)/葉子節(jié)點(diǎn)的初始化 hti.parent=0; hti.lchild=0; hti.rchild=0;for(;i<=m;i+) /非葉子節(jié)點(diǎn)的初始化.hti.weight=0;hti.parent=0;hti.lchild=0;hti.rchild=0;for(i=n+1;i<=m;+i)

5、/構(gòu)造哈夫曼樹s1=select(i-1);/ 函數(shù)在 ht1 到 hti-1 中選擇 parent 為 0 且 weight 最小的結(jié)點(diǎn)， 并將結(jié)點(diǎn)序號返 s，并將 hts1.parent 設(shè)為 -1s2=select(i-1);hts1.parent=i;hts2.parent=i;hti.lchild=s1;hti.rchild=s2;hti.weight=hts1.weight+hts2.weight;int c,f;for(i=1;i<=n;+i) for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)/逆向求葉子結(jié)點(diǎn)的哈夫曼編碼if(htf.l

6、child=c)stri.insert(0,"0",0,1); /在字符串 stri 的第 0 位置插入字符“0”elsestri.insert(0,"1",0,1); /在字符串 stri 的第 0 位置插入字符“ 1”分析：這段語句實(shí)現(xiàn)的功能是根據(jù)統(tǒng)計(jì)出來的各字符的頻度，建立哈弗曼。 建立哈弗曼樹的過程如程序所展示，每次選取權(quán)重最小且無雙親節(jié)點(diǎn)的節(jié)點(diǎn)組合，并將其權(quán)重之和賦給其雙親節(jié)點(diǎn)， 加入到總結(jié)中進(jìn)行下次判斷。哈弗曼樹建立完全以后，開始對各字符進(jìn)行編碼，從下往上，以葉子節(jié)點(diǎn)為起始點(diǎn)，若它是雙親節(jié)點(diǎn)的左孩子，其編碼前插入0 ，若是右孩子則插入1 。再

7、判斷雙親節(jié)點(diǎn)使其雙親節(jié)點(diǎn)的左孩子還是右孩子，以此類推直到根節(jié)點(diǎn)。依次對每個(gè)字符進(jìn)行上述過程編碼。算法復(fù)雜度：最好情況為只有根結(jié)點(diǎn)和葉子節(jié)點(diǎn)：O（ n）最壞情況為滿二叉樹情況：O（ n*logn/2 ）.3.程序運(yùn)行結(jié)果分析首先，要求用戶輸入進(jìn)行編碼的字符串，遍歷字符串，并為葉子節(jié)點(diǎn)權(quán)重賦值。然后，依次對各字符進(jìn)行哈弗曼編碼， 自下往上， 若是雙親節(jié)點(diǎn)左孩子則編碼前插入 0，若是雙親節(jié)點(diǎn)右孩子則編碼錢插入 1。屏幕上顯示各字符的哈弗曼編碼。 接下來對字符串進(jìn)行編碼， 挨個(gè)遍歷字符，找到相應(yīng)的編碼，復(fù)制到總的編碼里，最后輸出字符串的編碼。對字符串的哈弗曼碼進(jìn)行譯碼。自上往下，若是0，則遞歸到左孩子

8、，若是1，則遞歸到右孩子，知道葉子節(jié)點(diǎn)，輸出該葉子節(jié)點(diǎn)代表字符，再繼續(xù)遍歷。最后分析內(nèi)存占用情況。若用ASCII 編碼，每個(gè)字符占1 個(gè)字節(jié)，即8bit ，該情況下占用內(nèi)存就是（字符長度）*8 。若用哈弗曼編碼，占用內(nèi)存是各（字符頻度）*（每個(gè)字符占用位數(shù)）之和。3. 總結(jié)4.1 實(shí)驗(yàn)的難點(diǎn)和關(guān)鍵點(diǎn)本實(shí)驗(yàn)的難點(diǎn)和關(guān)鍵點(diǎn)是進(jìn)行哈弗曼的編碼與譯碼。編碼之前先要遍歷字符串，并統(tǒng)計(jì)各字符出現(xiàn)的頻度。這里就要區(qū)分目前的字符是否出現(xiàn)過，若出現(xiàn)過則字符權(quán)重加一，若沒.有出現(xiàn)則在結(jié)構(gòu)體數(shù)組的當(dāng)前末尾添加該元素。統(tǒng)計(jì)完頻度以后開始編碼。根據(jù)哈弗曼樹的特點(diǎn)， 每次選取結(jié)點(diǎn)里權(quán)重最小，且雙親不為0 的節(jié)點(diǎn)結(jié)合， 依

9、次添加直至根節(jié)點(diǎn)。編碼過程是從下往上。 對于某字符所在葉子節(jié)點(diǎn)， 若是雙親節(jié)點(diǎn)左孩子則編碼前插入 0 ，若是雙親節(jié)點(diǎn)右孩子則編碼錢插入 1直。到雙親節(jié)點(diǎn)移動(dòng)到根節(jié)點(diǎn)， 所得到的編碼即為該字符的編碼。譯碼過程是編碼的逆過程。依次讀取哈弗曼碼，自上往下，若是 0 ，則遞歸到左孩子，若是1，則遞歸到右孩子，知道葉子節(jié)點(diǎn)，輸出該葉子節(jié)點(diǎn)代表字符，再繼續(xù)遍歷。4.2 心得體會(huì)通過哈弗曼樹的程序編寫， 更加深入了解了樹這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)， 并且熟悉了這種數(shù)據(jù)結(jié)構(gòu)的應(yīng)用。同時(shí)，也對哈弗曼編碼的優(yōu)越性能有了根本的解釋。附：程序代碼#include<iostream>#include<stri

10、ng>using namespace std;#define max 1000/哈夫曼數(shù)存儲的最大葉子節(jié)點(diǎn)數(shù)int judge;/初始化過程中用于判斷字符是否出現(xiàn)過struct HTNodechar c;int weight;int lchild,rchild,parent;class CHTreepublic:CHTree()ht=NULL; ;void Init();void huffmancode();intselect(int i);void Display();void canculate();void encoding();void decoding();private:HT

11、Node* ht;int m;int n;/ 葉子結(jié)點(diǎn)數(shù)int s1;int s2;.string a;/ 存儲輸入的字符串string code;/存儲對字符串的編碼string strmax;/存儲葉子結(jié)點(diǎn)的哈夫曼編碼;void CHTree:Init()int i=1;/ 用于記錄葉子節(jié)點(diǎn)個(gè)數(shù)int j=0;int x=0,ru;cout<<" 請輸入進(jìn)行編碼的字符串："<<endl;cin>>a;int l=a.length();ht=(HTNode*)malloc(max)*sizeof(HTNode);/ 分配 MAXSIZE

12、 個(gè)葉子結(jié)點(diǎn)的存儲空間 while(x<l) / 統(tǒng)計(jì)字符出現(xiàn)的次數(shù)judge=1;for(j=0;j<i;j+)if(htj.c=ax)/ 如果字符 ax 已經(jīng)出現(xiàn)過，則記錄，權(quán)值加 1 htj.weight+;judge=0;break;if(judge)/ 若字符沒有出現(xiàn)過，字符入列，且權(quán)值設(shè)為 1 n=i;/ 記錄葉子節(jié)點(diǎn)數(shù)hti.weight=1;hti.c=ax;i+; x+;int CHTree:select(inti)/ 函數(shù)在 ht1 到 hti 中選擇 parent 為 0 且 weight 最小的結(jié)點(diǎn)，并將結(jié)點(diǎn)序號返回int j=1;int k=1;int s

13、;while(htj.parent!=0)j+;s=j;k=j+1;while(k<=i)while(htk.parent!=0) k+;.if(k>i)return s;if(htj.weight>htk.weight)htj.parent=0;/如果第二次和第二次以后循環(huán)中發(fā)現(xiàn)有比htj 權(quán)值還小的，將htj.parent重新設(shè)為0j=k;/ 始終令“htj ”為二者中權(quán)值小的那一個(gè)s=j;htj.parent=-1;/如果 htj 是權(quán)值較小的，將htj 的 parent 記為 -1 ，elses=j;htj.parent=-1;k+;return s; void CH

14、Tree:huffmancode()int i;if(n<=1)return;m=2*n-1;for(i=1;i<=n;i+)/葉子節(jié)點(diǎn)的初始化 hti.parent=0; hti.lchild=0; hti.rchild=0;for(;i<=m;i+) /非葉子節(jié)點(diǎn)的初始化hti.weight=0;hti.parent=0;hti.lchild=0;hti.rchild=0;for(i=n+1;i<=m;+i)/構(gòu)造哈夫曼樹s1=select(i-1);/ 函數(shù)在 ht1 到 hti-1 中選擇 parent 為 0 且 weight 最小的結(jié)點(diǎn)， 并將結(jié)點(diǎn)序號返 s

15、，并將 hts1.parent 設(shè)為 -1s2=select(i-1);hts1.parent=i;hts2.parent=i;hti.lchild=s1;hti.rchild=s2;hti.weight=hts1.weight+hts2.weight;int c,f;for(i=1;i<=n;+i) for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)/ 逆向求葉子結(jié)點(diǎn)的哈夫曼編碼 if(htf.lchild=c)stri.insert(0,"0",0,1); /在字符串 stri 的第 0 位置插入字符“0”.elsestri.i

16、nsert(0,"1",0,1); /在字符串 stri 的第 0 位置插入字符“ 1”void CHTree:Display()cout<<"huffman編碼如下： n"cout<<" 字符 "<<'t'<<" 權(quán)值 "<<'t'<<" 哈夫曼編碼 "<<endl; for(int i=1;i<=n;i+)cout<<hti.c<<'t&#

17、39;<<hti.weight<<'t'<<stri<<endl;void CHTree:canculate()int m=0;for(int i=1;i<=n;i+)m+=(hti.weight)*(stri.length();/該字符所占位數(shù)為頻度和每個(gè)字符huffman碼長度乘積cout<<"nn內(nèi)存分析：n"<<"原始編碼所占內(nèi)存數(shù)為"<<8*sizeof(char)*(a.length()<<"bit"<

18、;<endl;cout<<"huffman編碼所占內(nèi)存數(shù)為"<<m<<"bit"<<endl;void CHTree:encoding()for(int i=0;i<a.length();i+)/循環(huán)變量 i 用于遍歷輸入字符串的字符for(int j=1;j<=n;j+)/循環(huán)變量j 用于尋找 huffman 編碼中與該字符的相匹配的字符編碼if(ai=htj.c)code+=strj;cout<<"nn字符編碼為 "<<code<<endl;void CHTree:decoding()int i=0;int m=code.length();cout<<"nn對編碼譯碼后所得字符："while(i<m)int parent=2*n-1;/根結(jié)點(diǎn)在HTree 中的下表while(htparent.rchild!=0|htparent.lchild!=0)/自根結(jié)點(diǎn)向葉子節(jié)點(diǎn)匹配編碼，葉子節(jié)點(diǎn)左右孩子均為0，此時(shí)輸出字符if(codei='0')parent