哈夫曼樹解壓與壓縮

《哈夫曼樹解壓與壓縮》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。

1、實用標準文案哈夫曼樹的壓縮與解壓1.算法簡要描述1.哈夫曼算法1.哈弗曼算法是根據給定的n個權值{w1，w2，w3.......wn}，構造由n棵二叉樹構成的深林F={T1,T2,。。。。Tn}，其中每個二叉樹Ti分別都是只含有一個權值wi的根結點，其左右子樹為空（i=1，，，，，,2）。2.在深林F中選取其根結點的權值最小的兩棵二叉樹，分別作其左右子樹構造一顆新的二叉樹，并置這棵新的二叉樹根結點的權值為其左右子樹的根結點之和。3.從F中刪去這兩棵二叉樹，同時剛新生成的二叉樹加入到深林F中。4.重復2,3,步驟，直至深林F中只含有一顆二叉樹為止

2、。2.哈夫曼樹的實現(xiàn)函數(shù)StringEnCode(CharTypech)：表示哈夫曼樹已存在，返回字符ch的編碼。函數(shù)LinkListUnCode(StringstrCode)：表示對哈夫曼樹進行譯碼，返回編碼前的字符序列。根據算法可以看出，在具有n個結點權值的哈夫曼樹的構造過程中，每次都是從F中刪去兩棵樹，增加一棵樹，即每次結束后減少一棵樹，經過n-1次處理后，F(xiàn)中就只剩下一棵樹了。另外，每次合并都要產生一個新的結點，合并n-1次后共產生了n-1個新結點，并且這n-1個新節(jié)點都是具有左右子樹的分支結點。則最終得到的哈夫曼樹

3、中共有2n-1個結點，并且其中沒有度為1的分支結點，最后一次產生的新結點就是哈夫曼樹的根結點。源代碼中創(chuàng)建了一個哈夫曼樹結點類，其中有數(shù)據成員weight，parent，leftChild，rightChild分別代表了權值，雙親，左孩子，右孩子。在哈夫曼樹類中有數(shù)據成員*nodes，*LeafChars，*LeafCharCodes，curPos，num，分別用來存儲結點信息，葉結點字符信息，葉結點字符編碼信息，譯碼時從根結點到葉結點路徑的當前結點，葉結點個數(shù)。哈夫曼樹類中含有多個函數(shù)，有構造函數(shù)，析構函數(shù)等。由函數(shù)HuffmanTree(C

4、harTypech[],WeightTypew[],intn)來構造由字符，權值，和字符個數(shù)構造哈夫曼樹，在根據哈夫曼算法很容易實現(xiàn)哈夫曼類的函數(shù)以及構造函數(shù)。在在算法中，求葉結點字符的編碼時，需要從葉結點出發(fā)走一條從高葉結點到根結點的路徑，而編碼卻是從根結點出發(fā)到葉結點的路徑，由左分支為編碼0，右分支為編碼1，得到的編碼，因此從葉結點出發(fā)到根結點的路徑得到的編碼是實際編碼的逆序，并且編碼長度不確定，又由于可以再線性鏈表中構造串，因此將編碼的信息儲存在一個線性立案標準，每得到一位編碼都將其插入在線性鏈表的最前面。在求某個字符的編碼是由函數(shù)EnC

5、ode(CharTypech)來求，返回字符編碼。在進行譯碼時，用一個線性鏈表存儲字符序列，由函數(shù)Decode(StringstrCode)來求，對編碼串strCode進行譯碼，返回編碼前的字符序列。函數(shù)Compress()用哈夫曼編碼壓縮文件。函數(shù)Decompress()解壓縮用哈夫曼編碼壓縮的文件。精彩文檔實用標準文案在主函數(shù)中有兩個選項，一個是選擇編碼壓縮，一個是解壓。在函數(shù)中使用了文件輸入輸出流，我們可以選擇要壓縮的文件名輸入，在選出壓縮文件保存的地方和文件類型，將壓縮所得到的文件存儲在另一個文件中，解壓也是如此。1.源代碼#ifnde

6、f__HUFFMAN_TREE_NODE_H__#define__HUFFMAN_TREE_NODE_H__//哈夫曼樹結點類模板templatestructHuffmanTreeNode{WeightTypeweight;//權數(shù)據域unsignedintparent,leftChild,rightChild;//雙親,左右孩子域HuffmanTreeNode();//無參數(shù)的構造函數(shù)模板HuffmanTreeNode(WeightTypew,intp=0,intlChild=0,intrChild=0);/

7、/已知權,雙親及左右孩子構造結構};//哈夫曼樹結點類模板的實現(xiàn)部分templateHuffmanTreeNode::HuffmanTreeNode()//操作結果：構造空結點{parent=leftChild=rightChild=0;}templateHuffmanTreeNode::HuffmanTreeNode(WeightTypew,intp,intlChild,intrChild)//操作結果：構造一個權為w,雙親為p

8、,左孩子為lChild,右孩子為rChild的結點{weight=w;//權parent=p;//雙親leftChild=lChild;//左孩子ri