實驗四--哈夫曼樹與哈夫曼編碼(共10頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實驗四 哈夫曼樹與哈夫曼編碼一、實驗目的1、使學生熟練掌握哈夫曼樹的生成算法。2、熟練掌握哈夫曼編碼的方法。二、實驗內(nèi)容問題描述已知n個字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼。基本要求1. 初始化：從鍵盤讀入n個字符，以及它們的權值，建立Huffman樹。（具體算法可參見教材P147的算法6.12）2. 編碼：根據(jù)建立的Huffman樹，求每個字符的Huffman編碼。對給定的待編碼字符序列進行編碼。選作內(nèi)容. 譯碼：利用已經(jīng)建立好的Huffman樹，對上面的編碼結(jié)果譯碼。譯碼的過程是分解電文中的字符串，從根結(jié)點出發(fā)，按字符0和1確定找左孩子或右孩子，直至葉結(jié)點，

2、便求得該子串相應的字符。4. 打印 Huffman樹。測試數(shù)據(jù)利用教材P.148 例62中的數(shù)據(jù)調(diào)試程序?？稍O8種符號分別為A,B,C,D,E,F,G,H。編/譯碼序列為 “CFBABBFHGH”(也可自己設定數(shù)據(jù)進行測試)。3、 算法設計 1、主要思想：*赫夫曼樹的構(gòu)造*(1) 由給定的 n 個權值 w1, w2, , wn，構(gòu)造具有 n 棵二叉樹的森林 F =T1, T2, , Tn ，其中每棵二叉樹 Ti 只有一 個帶權為 wi 的根結(jié)點, 其左、右子樹均為空。(2) 在 F 中選取兩棵根結(jié)點的權值最小的二叉樹, 作為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點的權值為其

3、左、右子樹上根結(jié)點的權值之和。 (3)在 F 中刪去這兩棵二叉樹, 把新的二叉樹加入F。 (4)重復(2)和(3), 直到 F 中僅剩下一棵樹為止。 *霍夫曼編碼*主要用途是實現(xiàn)數(shù)據(jù)壓縮。由于赫夫曼樹中沒有度為1的節(jié)點，則一棵有n個葉子結(jié)點的赫夫曼樹共有2n-1個結(jié)點，可以存儲在一個大小為2n-1的一維數(shù)組中。由于在構(gòu)成赫夫曼樹之后，為求編碼需從葉子結(jié)點出發(fā)走一條從葉子到根的路徑；而為譯碼需從根出發(fā)走一條從根到葉子的路徑。則對每個結(jié)點而言，既須知雙親的信息，又需知孩子結(jié)點的信息。2、 本程序包含三個模塊1）主函數(shù)Int main() 先輸入結(jié)點總數(shù)； 分別輸入各個結(jié)點；調(diào)用建立哈夫曼樹函數(shù)；

4、調(diào)用編碼函數(shù)讀入建立的哈夫曼樹進行編碼3、 元素類型、結(jié)點類型和指針類型typedef struct /定義新數(shù)據(jù)類型即結(jié)點結(jié)構(gòu)int weight; /權重域 int parent,lchild,rchild; /指針域htnode; /結(jié)點類型標識符/typedef htnode * huffmanstree; /定義哈弗曼數(shù)類型htnode htmaxnodenumber;/定義三叉鏈表存儲數(shù)組typedef struct /定義保存一個葉子節(jié)點哈弗曼編碼的結(jié)構(gòu) int bitmaxbit; /定義一維數(shù)組為編碼域 int start; /定義位置域hcnodetype; /定義編碼類型

5、4、 主函數(shù)和其他函數(shù)清單1）Int main() 先輸入結(jié)點總數(shù)； 分別輸入各個結(jié)點；調(diào)用建立哈夫曼樹函數(shù)； 調(diào)用編碼函數(shù)讀入建立的哈夫曼樹進行編碼2）htnode * creatstree(int n) 建立哈夫曼樹算法實現(xiàn)函數(shù)3）void getstree(htnode * ht,int n) 哈夫曼編碼算法及打印函數(shù)的實現(xiàn)四、調(diào)試分析 輸入結(jié)點總數(shù) 分別輸入各個結(jié)點 赫夫曼的編碼5、 總結(jié)本次實驗電子報告中我原來打算加上各 函數(shù)的簡單流程圖，但是由于我處理圖形方面還比較不熟練，畫了三四個小時也不太滿意，所以索 性將幾個小時的努力通過del鍵結(jié)束了，所以這次報告不太令

6、人滿意，我將在以后的報告中加上示意 圖，多學習同學優(yōu)秀的地方也會在以后的學習過程中要盡量考慮周全，使程序更有實用價值，提高 編程能力。 我更加認識到自己動手的重要性，因為問題看起來很簡單，但是等到親自去實踐時，你會發(fā)現(xiàn)出現(xiàn)很多問題。正是通過不斷的發(fā)現(xiàn)問題、解決問題，我們才更加深刻的領悟到為核心，進而更好的掌握所學的知識；其次，我認識到了自己不明白的地方一定要向老師請教，老師的點撥，讓人豁然開朗，有助于我們更好的理解和掌握。最后，我理解棧的順序結(jié)構(gòu)，實現(xiàn)了一些基本操作，掌握了棧的先進后出的特點，并且能運用這一點解決實際問題。六、源代碼#include<stdio.h&g

7、t;#include<iostream.h>#include<malloc.h>#define maxvalue 10000 /定義最大權值常量#define maxnodenumber 100 /定義節(jié)點最大數(shù)#define maxbit 10 /定義哈弗曼編碼最大長度 typedef struct /定義新數(shù)據(jù)類型即節(jié)點結(jié)構(gòu)int weight; /權重域? int parent,lchild,rchild; /指針域htnode; /節(jié)點類型標識符/typedef htnode * huffmanstree; /定義哈弗曼數(shù)類型htnode htmaxnodenu

8、mber;/定義三叉鏈表存儲數(shù)組typedef struct /定義保存一個葉子節(jié)點哈弗曼編碼的結(jié)構(gòu) int bitmaxbit; /定義一維數(shù)組為編碼域 int start; /定義位置域hcnodetype; /定義編碼類型 htnode * creatstree(int n) /huffmanstree creatstree(int n) /建立哈夫曼樹算法實現(xiàn)函數(shù) int i,j,m1,m2,k1,k2; /局部變量for(i=0;i<2*n-1;i+)/初始化各節(jié)點 hti.weight=0; /權重初始化為0 hti.parent=-1; /根節(jié)點和給左右孩子初始化為-1 h

9、ti.lchild=-1; hti.rchild=-1;for(i=0;i<n;i+)/權重賦初值，由用戶輸入 scanf("%d",&hti.weight); for(i=0;i<n-1;i+) /生成新節(jié)點構(gòu)造哈夫曼樹 m1=maxvalue; /預置最小權值變量為最大權值m2=maxvalue; /預置次小權值變量為最大權值k1=0;/預置最小權值節(jié)點位置為下標為0處k2=0;/預置次小權值節(jié)點位置為下標為0處for(j=0;j<n+i;j+)/循環(huán)找出每趟最下權值和所在位置?if(htj.parent=-1&&htj.wei

10、ght<m1)m2=m1; k2=k1;m1=htj.weight;k1=j;else /當小于當前次小m2則更新m2及其位置if(htj.parent=-1&&htj.weight<m2)m2=htj.weight;k2=j;htk1.parent=n+i;/修改最小權值節(jié)點的雙親為剛生成的新節(jié)點htk2.parent=n+i;/修改次小權值節(jié)點的雙親為剛生成的新節(jié)點htn+i.weight=htk1.weight+htk2.weight; /將新生成的權重值填入新的根節(jié)點htn+i.lchild=k1; /新生節(jié)點左孩子指向k1htn+i.rchild=k2;

11、/新生節(jié)點右孩子指向k2return ht; /返回哈夫曼樹指針?void getstree(htnode * ht,int n) /哈夫曼編碼算法及打印函數(shù)的實現(xiàn)? int i,j,c,p; /局部變量的定義 hcnodetype cdmaxnodenumber; /定義存儲哈夫曼編碼的數(shù)組for(i=0;i<n;i+) /循環(huán)控制對每一個節(jié)點進行編碼 c=i; /為編碼各節(jié)點初始化c和jj=maxbit;do j-;/j指向bit中存放編碼為的正確位置p=htc.parent; /p指向c的雙親節(jié)點if(htp.lchild=c)/如果c是p的左孩子cdi.bitj=0;/編碼為賦值

12、0 else/否則即c是p的右孩子 cdi.bitj=1;/編碼賦值1 c=p;/更新當前指針，為下一節(jié)點編碼做準備while(htp.parent!=-1);/判斷是否編碼結(jié)束即循環(huán)至最終根節(jié)點cdi.start=j;/編碼完成,記下編碼開始位置for(i=0;i<n;i+) /循環(huán)打印各節(jié)點哈夫曼編碼 for(j=cdi.start;j<maxbit;j+)/循環(huán)逐一輸出 printf("%d",cdi.bitj); printf("n");/每輸出一編碼后換行 int main() /主函數(shù) int n; printf("*歡迎欣賞哈夫曼樹*:");cout<<endl; printf("請輸入節(jié)點數(shù):"); /用戶輸入節(jié)點數(shù) scanf("%d",&n); cout<<endl; cout<<"分別輸入哈夫曼樹的各個節(jié)點:"<<endl; htnode * p; /huffmanstree p /定義哈夫曼樹類型p p=(htnode * )malloc(siz