霍夫曼樹與霍夫曼編碼

1、實驗五 霍夫曼樹與霍夫曼編碼1、 實驗目的 掌握霍夫曼樹的概念 掌握霍夫曼樹的構造過程； 掌握霍夫曼樹編碼； 掌握霍夫曼樹譯碼。2、 實驗內(nèi)容與要求本實驗要求對輸入的一串電文字符實現(xiàn)霍夫曼編碼，再對霍夫曼編碼生成的代碼串進行譯碼，輸出電文字符串。具體要求：1） 建立霍夫曼樹；2） 霍夫曼編碼的生成；3） 霍夫曼譯碼。3、 實驗編程指導 1）霍夫曼樹的建立由霍夫曼樹的定義可知，含有n個葉子結(jié)點的霍夫曼樹中共有2n-1個結(jié)點，而且霍夫曼中沒有度為1的分支結(jié)點。我們可以用一個大小為2n-1的一維數(shù)組來存儲霍夫曼樹中的結(jié)點。霍夫曼樹的參考存儲結(jié)構描述如下：#define n 100#define m

2、2*n-1typedef struct int weight;char ch;int parent,lchild,rchild;HTNode；typedef HTNode HuffmanTreem;要實現(xiàn)霍夫曼樹，首先要實現(xiàn)HT1n中選擇parent為-1且權值最小的兩個根結(jié)點的選擇算法；另外，還要有一個實現(xiàn)統(tǒng)計輸入電文字符串中各種字符出現(xiàn)的頻率以及字符的種類的算法，假設電文中僅含有大寫字母?；舴蚵鼧涞慕⒅饕ㄒ韵氯齻€部分：1 選擇parent為-1且權值最小的兩個根結(jié)點的算法；2 統(tǒng)計字符串中字符的種類以及各種字符的個數(shù)的算法；3 構造霍夫曼樹。2）霍夫曼編碼要求電文的霍夫曼編碼，必須先

3、定義霍夫曼編碼的類型。參考的定義如下：typedef structchar ch; /存放編碼的字符char bitsn+1; / 存放編碼位串int start; /編碼起始位置 CodeNode;該部分主要包括如下內(nèi)容：1 霍夫曼編碼：根據(jù)霍夫曼樹求霍夫曼編碼表；2 建立正文的編碼文件：將要編碼的字符串中的字符逐一與預先生成的霍夫曼樹保存的字符編碼對照表進行比較，找到之后，將該字符的編碼寫入代碼文件，直至所有的字符處理完畢為止。功能：輸入任意一個字符串（要求其中的字符在原始字符串中出現(xiàn)過），能夠進行霍夫曼編碼。3 霍夫曼譯碼讀取編碼，并與原生成的霍夫曼編碼表比較，遇到相等時，即取出其對應的

4、字符存入一個新串中。注意：具體編解碼算法可以參考講義。以上為參考實驗方案，不局限于此方案。4、 實驗報告要求 分組方式：按小組方式進行，2個人為1組，選1名為組長，負責計劃整個題目的進展，要求分工明確，任務詳實。實驗報告要求以word文件形式發(fā)到老師郵箱。內(nèi)容包括：（1）報告封面包括實驗名稱、班級、姓名、學號以及實驗完成日期。（2）各程序模塊名稱及功能說明。并繪制出主要功能函數(shù)的程序流程圖。（3）個人小結(jié)。包括實驗難點分析、進一步的工作、個人希望等。（4）完整的程序清單。完成日期：2012430各模塊名稱以及功能說明：int Init( HTNode ht函數(shù)：初始化函數(shù)，通過讀取輸入的信息，

5、統(tǒng)計哪一些字符出現(xiàn)過，并且統(tǒng)計出現(xiàn)次數(shù)來確定權值，最后存入ht中。void select(HTNode ht,int q,int *p1,int *p2函數(shù)：選出包含新增結(jié)點在內(nèi)的權值最小的兩個結(jié)點，p1為最小的結(jié)點的下標，p2為次小的結(jié)點的下標。void huffman_setup(HTNode ht,int s函數(shù)：霍夫曼樹的建立函數(shù)，在所有的葉子結(jié)點數(shù)組之后依次增加新增結(jié)點，其權值依次增加，每一個新的結(jié)點的權值為當前結(jié)點中權值最小的兩個結(jié)點權值之和，并建立相應的雙親關系。void huffman_show(CodeNode hc,HTNode ht,int s函數(shù)：給每個輸入的信息元素按

6、照權值編01碼，其基本原理是按照已經(jīng)建立的霍夫曼樹從最后一個元素（跟結(jié)點）開始，根據(jù)子樹是否滿足左右子樹的條件來判斷0還是1編碼。void huffman_code(CodeNode hc函數(shù)：根據(jù)人為輸入的字母信息進行比對編碼，得到相應的01碼。void huffman_read(HTNode ht,int s函數(shù)：根據(jù)人為輸入的01碼，從跟結(jié)點開始往下查找得到并輸出對應的字母信息。主要功能函數(shù)的程序流程圖：int Init( HTNode ht函數(shù)進入函數(shù)初始化各個元素信息讀取元素N統(tǒng)計各個元素的出現(xiàn)次數(shù)為！Y把統(tǒng)計的結(jié)果給ht賦值返回元素的個數(shù)void select(HTNode ht,

7、int q,int *p1,int *p2函數(shù)進入函數(shù)N樹中繼續(xù)查找雙親非零Y后項后移權值>后項YN取最小賦值為P1N樹中繼續(xù)查找雙親非零Y后項后移權值>后項，且！=P1NY取最小賦值為P2void huffman_setup(HTNode ht,int s函數(shù)函數(shù)開始所有的結(jié)點都賦0i+i NY調(diào)用select函數(shù)取權值最小的2個結(jié)點，建立一個新增結(jié)點void huffman_show(CodeNode hc,HTNode ht,int s函數(shù)：進入函數(shù)NI p=s-1Y左孩子為自己N以i為下標的結(jié)點親為0Y賦值為0NY數(shù)組賦值為1賦值給hc退出函數(shù)輸入字母信息void huff

8、man_code(CodeNode hc 函數(shù) i+與hci中相等NY輸出對應霍夫曼碼void huffman_read(HTNode ht,int s函數(shù)：得到相應霍夫曼碼根結(jié)點開始該碼為0NY賦右子樹下標賦左子樹的下標N左子樹為0NY滿足結(jié)束標志輸出該字母Y退出源代碼：（編譯環(huán)境 VS2008）#include #include #include #define n 100#define m 2*n-1typedef structint weight;char ch;int parent,lchild,rchild;HTNode;typedef structchar ch; char bi

9、tsn+1; CodeNode;typedef structchar cha;int number;COUNTER;int Init( HTNode ht/初始化函數(shù)，為每一個字母信息賦權值int i,s=1;COUNTER counter27;char ch;printf("請輸入一段字符來確定權值：(限大寫字母,以'!'號為結(jié)束標志n"scanf("%c",&ch;counter1.cha='A'counter2.cha='B'counter3.cha='C'counter4.c

10、ha='D'counter5.cha='E'counter6.cha='F'counter7.cha='G'counter8.cha='H'counter9.cha='I' counter10.cha='J'counter11.cha='K'counter12.cha='L'counter13.cha='M'counter14.cha='N'counter15.cha='O'counter16.cha=&

11、#39;P'counter17.cha='Q'counter18.cha='R'counter19.cha='S'counter20.cha='T'counter21.cha='U'counter22.cha='V'counter23.cha='W'counter24.cha='X'counter25.cha='Y'counter26.cha='Z'for(i=1;i<=26;i+counteri.number=0;whi

12、le(ch!='!'switch(chcase 'A':counter1.number+;break;case 'B':counter2.number+;break;case 'C':counter3.number+;break;case 'D':counter4.number+;break;case 'E':counter5.number+;break;case 'F':counter6.number+;break;case 'G':counter7.number+

13、;break;case 'H':counter8.number+;break;case 'I':counter9.number+;break;case 'J':counter10.number+;break;case 'K':counter11.number+;break;case 'L':counter12.number+;break;case 'M':counter13.number+;break;case 'N':counter14.number+;break;case 

14、9;O':counter15.number+;break;case 'P':counter16.number+;break;case 'Q':counter17.number+;break;case 'R':counter18.number+;break;case 'S':counter19.number+;break;case 'T':counter20.number+;break;case 'U':counter21.number+;break;case 'V':coun

15、ter22.number+;break;case 'W':counter23.number+;break;case 'X':counter24.number+;break;case 'Y':counter25.number+;break;case 'Z':counter26.number+;break;scanf("%c",&ch;for(i=1;i<=26;i+if(counteri.number!=0hts.weight=counteri.number;hts.ch=counteri.cha;

16、s+; s=s-1;return s;void select(HTNode ht,int q,int *p1,int *p2 /select函數(shù)int i,j,x=0,y=0;for(j=1;j<=q;+jif(htj.parent=0x=j;break;for(i=j+1;i<=q;+iif(hti.weight x=i; /選出最小結(jié)點for(j=1;j<=q;+j if(htj.parent=0&&x!=jy=j;break;for(i=j+1;i<=q;+iif(hti.weight y=i; /選出第二小結(jié)點if(x>y*p1=y;*p2

17、=x;else*p1=x;*p2=y;void huffman_setup(HTNode ht,int s int i,a;int p1,p2;a=2*s-1;for(i=1;i<=a;i+if(i<=shti.weight=hti.weight;elsehti.weight=0;hti.parent=hti.lchild=hti.rchild=0;for(i=s+1;i<=a;+i /建立赫夫曼樹select(ht,i-1,&p1,&p2;htp1.parent=i;htp2.parent=i;hti.lchild=p1;hti.rchild=p2;hti.

18、weight=htp1.weight+htp2.weight;void huffman_show(CodeNode hc,HTNode ht,int s/給字符編碼char qn;int i,p,c,f;qs-1='0'for(i=1;i<=s;i+ p=s-1;for(c=i,f=hti.parent;f;c=f,f=htf.parentif(htf.lchild=cq-p='0'elseq-p='1'strcpy(hci.bits,&qp;hci.ch=hti.ch;void huffman_code(CodeNode hc/根

19、據(jù)字母信息來給出編碼int i=1;char ch,ah;fflush(stdin;/清除流printf("請輸入您想要進行霍夫曼編碼的信息(以'!'為結(jié)束標志，必須包含霍夫曼樹中原有的元素：n"scanf("%c",&ch;printf("霍夫曼編碼是：n"while(ch!='!'ah=hci.ch;while(ch!=ahi+;ah=hci.ch;printf("%s",hci.bits;scanf("%c",&ch;i=1;void huffman_read(HTNode ht,int s/根據(jù)編碼來返回字母信息int i,j,t;char b;t=2*s-1;i=t;printf("請輸入霍夫曼代碼,為您進行編譯!（以'!'為結(jié)束標志，必須包含霍夫曼樹中原有的元素n"fflush(stdin;/清除流scanf("%c",&b;printf("解碼后的信息是：n"while(b!='!'if(b='