北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)—Huffman編碼解碼器_第1頁(yè)
北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)—Huffman編碼解碼器_第2頁(yè)
北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)—Huffman編碼解碼器_第3頁(yè)
北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)—Huffman編碼解碼器_第4頁(yè)
已閱讀5頁(yè),還剩9頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

2、字符串編碼前和編碼后的長(zhǎng)度,并進(jìn)行分析,討論赫夫曼編碼的壓縮效果。2. 程序分析2.1 存儲(chǔ)結(jié)構(gòu)靜態(tài)三叉鏈表WeightLchildRchildparent2.2 程序流程(或程序結(jié)構(gòu)、或類關(guān)系圖等表明程序構(gòu)成的內(nèi)容,一般為流程圖等 )流程圖開始輸入進(jìn)行編碼的字符串統(tǒng)計(jì)各個(gè)字符的頻度,并對(duì)各葉子節(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對(duì)字符串進(jìn)行編碼找到當(dāng)前字符編碼,復(fù)制到總編碼中否是否最后一個(gè)字符是輸出各字符串編碼對(duì)哈弗曼碼進(jìn)

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

4、字符長(zhǎng)度)*8 。若用哈弗曼編碼,占用內(nèi)存是各(字符頻度)*(每個(gè)字符占用位數(shù))之和。2.3 關(guān)鍵算法分析該程序關(guān)鍵算法即哈弗曼編碼,語(yǔ)句如下: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)序號(hào)返 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”分析:這段語(yǔ)句實(shí)現(xiàn)的功能是根據(jù)統(tǒng)計(jì)出來(lái)的各字符的頻度,建立哈弗曼。 建立哈弗曼樹的過(guò)程如程序所展示,每次選取權(quán)重最小且無(wú)雙親節(jié)點(diǎn)的節(jié)點(diǎn)組合,并將其權(quán)重之和賦給其雙親節(jié)點(diǎn), 加入到總結(jié)中進(jìn)行下次判斷。哈弗曼樹建立完全以后,開始對(duì)各字符進(jìn)行編碼,從下往上,以葉子節(jié)點(diǎn)為起始點(diǎn),若它是雙親節(jié)點(diǎn)的左孩子,其編碼前插入0 ,若是右孩子則插入1 。再

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

8、,若是1,則遞歸到右孩子,知道葉子節(jié)點(diǎn),輸出該葉子節(jié)點(diǎn)代表字符,再繼續(xù)遍歷。最后分析內(nèi)存占用情況。若用ASCII 編碼,每個(gè)字符占1 個(gè)字節(jié),即8bit ,該情況下占用內(nèi)存就是(字符長(zhǎng)度)*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)過(guò),若出現(xiàn)過(guò)則字符權(quán)重加一,若沒(méi).有出現(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)。編碼過(guò)程是從下往上。 對(duì)于某字符所在葉子節(jié)點(diǎn), 若是雙親節(jié)點(diǎn)左孩子則編碼前插入 0 ,若是雙親節(jié)點(diǎn)右孩子則編碼錢插入 1直。到雙親節(jié)點(diǎn)移動(dòng)到根節(jié)點(diǎn), 所得到的編碼即為該字符的編碼。譯碼過(guò)程是編碼的逆過(guò)程。依次讀取哈弗曼碼,自上往下,若是 0 ,則遞歸到左孩子,若是1,則遞歸到右孩子,知道葉子節(jié)點(diǎn),輸出該葉子節(jié)點(diǎn)代表字符,再繼續(xù)遍歷。4.2 心得體會(huì)通過(guò)哈弗曼樹的程序編寫, 更加深入了解了樹這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn), 并且熟悉了這種數(shù)據(jù)結(jié)構(gòu)的應(yīng)用。同時(shí),也對(duì)哈弗曼編碼的優(yōu)越性能有了根本的解釋。附:程序代碼#include<iostream>#include<stri

10、ng>using namespace std;#define max 1000/哈夫曼數(shù)存儲(chǔ)的最大葉子節(jié)點(diǎn)數(shù)int judge;/初始化過(guò)程中用于判斷字符是否出現(xiàn)過(guò)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;/ 存儲(chǔ)輸入的字符串string code;/存儲(chǔ)對(duì)字符串的編碼string strmax;/存儲(chǔ)葉子結(jié)點(diǎn)的哈夫曼編碼;void CHTree:Init()int i=1;/ 用于記錄葉子節(jié)點(diǎn)個(gè)數(shù)int j=0;int x=0,ru;cout<<" 請(qǐng)輸入進(jìn)行編碼的字符串:"<<endl;cin>>a;int l=a.length();ht=(HTNode*)malloc(max)*sizeof(HTNode);/ 分配 MAXSIZE

12、 個(gè)葉子結(jié)點(diǎn)的存儲(chǔ)空間 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)過(guò),則記錄,權(quán)值加 1 htj.weight+;judge=0;break;if(judge)/ 若字符沒(méi)有出現(xiàn)過(guò),字符入列,且權(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)序號(hào)返回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)序號(hào)返 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碼長(zhǎng)度乘積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對(duì)編碼譯碼后所得字符:"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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論