1、哈夫曼編碼12007-6定義2哈夫曼編碼是一種一致性編碼法（又稱“熵編碼法”），用于數據的無損耗壓縮。根據每一個源字符出現的估算概率而建立起來的（出現概率高的字符使用較短的編碼，反之出現概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達到無損壓縮數據的目的）。原理3首先統計信源中各符號出現的概率，按符號出現的概率從大到小排序；把最小的兩個概率相加合并成新的概率，與剩余的概率組成新的概率集合；對新的概率集合重新排序，再次把其中最小的兩個概率相加，組成新的概率集合。如此重復進行，直到最后兩個概率的和為l；原理4分配碼字：碼字分配從最后一步開始反向進行，對于每次相加的兩個概率

2、，給大的賦O，小的賦1(也可以全部相反，如果兩個概率相等，則從中任選一個賦O，另一個賦l即可)，讀出時由該符號開始一直走到最后的概率和1，將路線上所遇到的O和l按最低位到最高位的順序排好，就是該符號的哈大曼編碼。編碼步驟5對給定的n個權值W1,W2.Wn構成n棵二叉樹的初始集合F= T1,T2,T3,.,Ti,.,Tn，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。（為方便在計算機上實現算法，一般還要求以Ti的權值Wi的升序排列。）編碼步驟6在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。從F中刪除這兩棵

3、樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。重復二和三兩步，直到集合F中只有一棵二叉樹為止。示例7假如有A,B,C,D,E五個字符，出現的頻率（即權值）分別為5,4,3,2,1,那么我們第一步先取兩個最小權值作為左右子樹構造一個新樹，即取1，2構成新樹，其結點為1+2=3，如圖：p虛線為新生成的結點，第二步再把新生成的權值為3的結點放到剩下的集合中，所以集合變成5,4,3,3，再根據第二步，取最小的兩個權值構成新樹，如圖：示例8再依次建立哈夫曼樹，如下圖：p各字符對應的編碼為：A-11,B-10,C-00,D-011,E-010五、程序部分代碼及其分析9實現過程：首先通過 Huffma

4、nTree() 函數構造哈夫曼樹，然后在主函數 main()中自底向上開始(也就是從數組序號為零的結點開始)向上層層判斷，若在父結點左側，則置碼為 0,若在右側,則置碼為 1。最后輸出生成的編碼。typedef struct int bitMAXBIT; int start; HCodeType; /* 編碼結構體 */五、程序部分代碼及其分析10typedef struct int weight; int parent; int lchild; int rchild; int value; HNodeType; /* 結點結構體 */ 五、程序部分代碼及其分析11* 初始化存放哈夫曼樹數組

5、HuffNode 中的結點 */ for (i=0; i2*n-1; i+) HuffNodei.weight = 0;/權值 HuffNodei.parent =-1; HuffNodei.lchild =-1; HuffNodei.rchild =-1; HuffNodei.value=i; /實際值，可根據情況替換為字母 /* end for */五、程序部分代碼及其分析12/* 循環構造 Huffman 樹 */ for (i=0; in-1; i+) m1=m2=MAXVALUE; /* m1、m2中存放兩個無父結點且結點權值最小的兩個結點 */ x1=x2=0; /* 找出所有結點

6、中權值最小、無父結點的兩個結點，并合并之為一顆二叉樹 */ for (j=0; jn+i; j+) if (HuffNodej.weight m1 & HuffNodej.parent=-1) m2=m1; x2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNodej.weight m2 & HuffNodej.parent=-1) m2=HuffNodej.weight; x2=j; /* end for */五、程序部分代碼及其分析13 /* 設置找到的兩個子結點 x1、x2 的父結點信息 */ HuffNodex1.parent = n+i; HuffNodex2.parent = n+i; HuffNoden+i.