實驗四哈夫曼樹與哈夫曼編碼

1、實驗四 哈夫曼樹與哈夫曼編碼一、實驗內容問題描述已知n個字符在原文中出現的頻率，求它們的哈夫曼編碼?；疽?. 初始化：從鍵盤讀入n個字符，以及它們的權值，建立Huffman樹。（具體算法可參見教材P147的算法6.12）2. 編碼：根據建立的Huffman樹，求每個字符的Huffman編碼。對給定的待編碼字符序列進行編碼。二、概要設計算法設計： 要是實現哈夫曼樹的操作，首先創(chuàng)建一個哈夫曼樹，在創(chuàng)建哈夫曼樹的時候，對哈夫曼樹的葉子和非葉子結點進行初始化，而在建立哈夫曼樹時，最難的該是選擇權值最小的兩個頂點，然后兩個結點的權值和作為新的權值，再選擇兩個權值最小的作為新的兩個結點創(chuàng)建一個小的二叉

2、樹的子樹；創(chuàng)建哈夫曼樹后，進行編碼，在編碼過程中，先找到根，然后遍歷，左孩子用0標記，右孩子用1標記，最后將編碼好的哈夫曼樹進行輸出，就可以知道哈夫曼樹的編碼了。流程圖：開始輸入哈弗曼樹的帶權結點數目 n輸入相應的權值和對應的字符建立哈夫曼樹Huffmantree(HT,w,n,e)顯示哈夫曼樹outputHuffman(HT,m)哈夫曼樹的編碼CHuffmancode(HT,HC,n)結束算法：主函數Huffmantree(HuffmanTree &HT,int*w,int n,char *e)*hc, int n)CHuffmancode(HuffmanTree &HT,HuffmanCo

3、de &HC,int n)outputHuffman(HuffmanTree HT, int m)select(HuffmanTree *ht,int n, int *s1, int *s2)模塊： 在分析了實驗要求和算法分析之后，將程序分為四個功能函數，分別如下：首先建立一個哈夫曼樹和哈夫曼編碼的存儲表示：typedef struct int weight; int parent,lchild,rchild;char elem;HTNode,*HuffmanTree;/動態(tài)分配數組存儲赫夫曼樹typedef char *HuffmanCode;/動態(tài)分配數組存儲赫夫曼編碼表CrtHuffma

4、nTree(HuffmanTree *ht , int *w, int n)：w存放n個字符的權值，構造哈夫曼樹HT。先將葉子初始化，再將非葉子結點初始化，然后構造哈夫曼樹。 構造哈夫曼樹：開始葉子初始化非葉子初始化調用select函數選擇權值最小的兩個這兩個權值最小的兩個字符非別作為同一個結點的左右孩子，其父母的權值為兩個字符的權值之和結束 for(i=n+1;i=m;+i)/在HT1i選擇parent為0且weight最小的兩個 Select(HT,i-1,&s1,&s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HT

5、i.weight=HTs1.weig ht+HTSelect(HuffmanTree &HT,int n,int *s1,int *s2)：在所給的權值中，選擇出權值最小的兩個值。int i, min; for(i=1;i=n;i+) if(HTi.parent=0)min=i;i=n+1; for(i=1;i=n;i+) if(HTi.parent=0) if(HTi.weightHTmin.weight) min=i; *s1=min;在選擇s2的時候和s1相似，只有在判斷是否為最小的時候就，要加上一個條件：if(HTi.parent=0&i!=*s1)，就可以了，否則，選出來的最小權值和

6、s1 就相等了，失去了選擇的意義了。CHuffmancode(HuffmanTree &HT,HuffmanCode &HC,int n)：從葉子到根逆向求編碼：左孩子為0，右孩子為1，這樣一直循環(huán)下去，而最重要的是：for(int i=1;i=n;+i)star=n-1; /從右向左逐位存放編碼，首先存放編碼結束符for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/從葉子到根結點求編碼if(HTf.lchild=c)cd-star=0; /左分支標0else cd-star=1;/右分支標1HCi=new charn-star; /為第i個編碼分配空間st

7、rcpy(HCi,&cdstar);/從cd復制編碼串到HC否是是開始從葉子到根結點求編碼 c=i f=HTi.parentf!=0 c=將0輸入到cd數組HTf.lchild=c中將1輸入到cd數組HTf.lchild=c從cd復制編碼串到HCc=f,f=HTf.parent否輸出字符權值相應的編碼結束outputHuffman(HuffmanTree HT, int m)：顯示出哈夫曼樹的編碼和字符以及權重，與二叉樹的遍歷相似：if(m!=0) coutHTm.elem HTm.weightendl; outputHuffman(HT,HTm.lchild); outputHuffman(

8、HT,HTm.rchild);三 、測試數據測試一：字符為：A B C 權重：10 12 8 測試數據二：字符為：ABCDEFG權重為：7 8 8 12 15 9 6四、結果調試調試一： 調試二： 五總結 在進行這個程序的編寫的時候，其實有點毫無頭緒，只是知道在書上的算法就可以編寫成功。但是在一次又一次的過程，還是一次又一次的錯誤，最后在進行理解才稍微理解了哈夫曼樹的編碼過程，但是選擇權值最小的過程還是不太理解，進行了調試才明白也一些，但是還是沒有明白透徹。在這次的實驗過程中，我明白了調試的重要性，不要在自己遇到問題的時候就去問同學，因為那樣會養(yǎng)成自己的依賴性，在自己不會的時候，不會進行深層次

9、的了解就去問，那樣對自己沒有太大的提高，只有自己理解和同學的講解相結合，才能有所提高。六、附錄：#include#include typedef struct int weight; int parent,lchild,rchild;char elem;HTNode,*HuffmanTree;/動態(tài)分配數組存儲赫夫曼樹typedef char *HuffmanCode;/動態(tài)分配數組存儲赫夫曼編碼表/求赫夫曼編碼void Select(HuffmanTree &HT,int n,int *s1,int *s2) int i, min; for(i=1;i=n;i+) if(HTi.parent

10、=0)min=i;i=n+1; for(i=1;i=n;i+) if(HTi.parent=0) if(HTi.weightHTmin.weight) min=i; *s1=min; for(i=1; i=n; i+) if(HTi.parent = 0 & i!=*s1) min = i; i = n+1; for(i=1;i=n;i+) if(HTi.parent=0&i!=*s1) if(HTi.weightHTmin.weight) min=i; *s2=min;/void Huffmantree(HuffmanTree &HT,int*w,int n,char *e) /w存放n個字

11、符的權值，構造赫夫曼樹HT，并求出n個字符的赫夫曼編碼HCint m,i,s1,s2;if(n=1) return;m=2*n-1;/總的結點HT=new HTNodem+1;for(i=1;i=n;+i)/*1-n號放葉子結點，初始化*/HTi.weight=wi;HTi.lchild=0;HTi.rchild=0;HTi.parent=0;HTi.elem=ei;for(i=n+1;i=m;+i) /*非葉子結點初始化*/ HTi.weight=0;HTi.lchild=0;HTi.rchild=0;HTi.parent=0;HTi.elem=0;for(i=n+1;i=m;+i)/在HT

12、1i選擇parent為0且weight最小的兩個 Select(HT,i-1,&s1,&s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/void CHuffmancode(HuffmanTree &HT,HuffmanCode &HC,int n) char *cd; int c,f,star;HC=new char*n+1;cd=new charn;cdn-1=0;/編碼結束符for(int i=1;i=n;+i)star=n-1; /從右向左逐位存

13、放編碼，首先存放編碼結束符for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/從葉子到根結點求編碼if(HTf.lchild=c)cd-star=0; /左分支標0else cd-star=1;/右分支標1HCi=new charn-star; /為第i個編碼分配空間strcpy(HCi,&cdstar);/從cd復制編碼串到HCdelete cd;/釋放工作空間 for(i=1;i=n;i+) coutHTi.elem HTi.weight:HCiendl;/void outputHuffman(HuffmanTree HT, int m)if(m!=0) coutHTm.elem HTm.weightendl; outputHuffman(HT,HTm.lchild); outputHuffman(HT,HTm.rchild);void main() HuffmanTree HT; H