哈夫曼編碼試驗報告

本文格式為Word版，下載可任意編輯——哈夫曼編碼試驗報告北京郵電大學(xué)信息與通信工程學(xué)院

數(shù)據(jù)結(jié)構(gòu)試驗報告

試驗名稱：試驗三——哈夫曼編碼學(xué)生姓名：牛佳寧班級：2023211107班內(nèi)序號：27學(xué)號：10210213

日期：2023年12月10日

1．試驗要求

利用二叉樹結(jié)構(gòu)實現(xiàn)赫夫曼編/解碼器。

1、讀入一串字符，統(tǒng)計字符個數(shù)及權(quán)值。2、建立哈夫曼樹。

3、根據(jù)哈夫曼樹建立哈夫曼表。4、將字符串進行編碼。

5、輸入一串01數(shù)，進行解碼。

2.程序分析

2.1存儲結(jié)構(gòu)

哈夫曼樹為正則二叉樹，有n個葉子的哈夫曼樹共有2n-1個結(jié)點，可以用一個大小為2n-1的數(shù)組來儲存哈夫曼樹的各個結(jié)點，如圖weight2369dataZCBLchild-1-1-1-1code10010111RChild-1-1-1-1parent-1-1-1-1對應(yīng)的編碼表可用如下圖結(jié)構(gòu)

2.2關(guān)鍵算法分析

第1頁

北京郵電大學(xué)信息與通信工程學(xué)院

一、創(chuàng)立哈夫曼樹

1、根據(jù)權(quán)值初始化哈夫曼樹for(inti=0;iilist;for(intj=0;j::iteratorit=ilist.begin();x=*it;y=*++it;returnx,y;}

六、建立數(shù)組不重復(fù)的儲存字符并且統(tǒng)計出現(xiàn)次數(shù)即權(quán)值：利用循環(huán)鏈表來實現(xiàn)，每插入一個結(jié)點之前先定義節(jié)點指針指向第一個結(jié)點，邊向后移動邊比較儲存的字符是否一致，若一致則使該節(jié)點權(quán)值加一，不同則將該節(jié)點參與到循環(huán)鏈表中，直到遍歷整個字符串，代碼如下

voidLinklist::Construct(chars[])//建立循環(huán)鏈表存放字符串{rear=newNode;rear->next=rear;for(unsignedinti=0;inext==rear)//放入第一個字符{Node*p=newNode;p->data=s[0];p->weight=1;p->next=rear->next;rear->next=p;rear=p;}else{

第4頁

北京郵電大學(xué)信息與通信工程學(xué)院

法插入}}

}

Node*q=rear->next->next;//q指向第一個字符

while(q!=rear->next)//遍歷鏈表看q存儲的字符是否有與要插入的字符一致的{if(q->data==s[i]){q->weight++;//若有則權(quán)值加一break;}elseq=q->next;}

if(q==rear->next)//若鏈表中無與要插入字符一致的字符，則將該字符使用頭插{}

Node*r=newNode;r->data=s[i];r->weight=1;

r->next=rear->next;rear->next=r;rear=r;

q

時間繁雜度計算：select函數(shù)的時間繁雜度為O(n),則建立哈夫曼樹的時間按繁雜度為Ｏ（ｎ

第5頁

北京郵電大學(xué)信息與通信工程學(xué)院

＾２）建立哈夫曼編碼表的時間繁雜度為O（n）。編碼的函數(shù)時間繁雜度為O（n）。解碼函數(shù)的時間繁雜度為O（n^2）。

3.程序運行結(jié)果運行環(huán)境為vc6.0

編碼前的長度為32編碼后的長度為22，壓縮比為22/32=68.75%

4.總結(jié)

在調(diào)試過程中遇到過好多困難，譬如在寫選擇權(quán)重最小的兩個節(jié)點的編碼時，就出現(xiàn)了選擇出最大的輸出兩遍等問題你，規(guī)律上有些麻煩，但是使用STL后，程序變得簡單多了，而且不用考慮那些過于細(xì)致的問題。

吸取上次八皇后問題編碼時使用遞歸函數(shù)簡單出現(xiàn)中止遞歸的條件不明顯等問題，這次選擇了用循環(huán)來實現(xiàn)遞歸，雖然代碼變長，但是思維變得明了起來，也不太簡單出現(xiàn)錯誤通過這次編程是我對哈夫曼編碼有了更深刻的理解，并且學(xué)會了將之前學(xué)過的循環(huán)鏈表等數(shù)據(jù)存儲結(jié)構(gòu)運用到程序中來，并且有了解了STL的排序功能，又一次見識到了STL的便利快捷。但本試驗仍有好多不足：

1、在解碼時仍缺少過錯能力，使解碼有誤

2、在統(tǒng)計字符權(quán)重時使用循環(huán)鏈表雖然有比較與統(tǒng)計長度便利等優(yōu)點，但仍不夠簡單，應(yīng)

該還存在著更為簡單的方法3、未能實現(xiàn)菜單的交互

第6頁

北京郵電大學(xué)信息與通信工程學(xué)院

＾２）建立哈夫曼編碼表的時間繁雜度為O（n）。編碼的函數(shù)時間繁雜度為O（n）。解碼函數(shù)的時間繁雜度為O（n^2）。

3.程序運行結(jié)果運行環(huán)境為vc6.0

編碼前的長度為32編碼后的長度為22，壓縮比為22/32=68.75%

4.總結(jié)

在調(diào)試過程中遇到過好多困難，譬如在寫選擇權(quán)重最小的兩個節(jié)點的編碼時，就出現(xiàn)了選擇出最大的輸出兩遍等問題你，規(guī)律上有些麻煩，但是使用STL后，程序變得簡單多了，而且不用考慮那些過于細(xì)致的問題。

吸取上次八皇后問題編碼時使用遞歸函數(shù)簡單出現(xiàn)中止遞歸的條件不明顯等問題，這次選擇了用循環(huán)來實現(xiàn)遞歸，雖然代碼變長，但是思維變得明了起來，也不太簡單出現(xiàn)錯誤通過這次編程是我對哈夫曼編碼有了更深刻的理解，并且學(xué)會了將之前學(xué)過的循環(huán)鏈表等數(shù)據(jù)存儲結(jié)構(gòu)運用到程序中來，并且有了解了STL的排序功能，又一次見識到了STL的便利快捷。但本