C++實現:霍夫曼編碼

C++實現:霍夫曼編碼：

1. #ifndef CHUFFMANTREE_H_   
2. #define CHUFFMANTREE_H_   
3. #include <assert.h>   
4. #include <iostream>   
5. #include <string>   
6. #include <deque>   
7. using namespace std;  
8. /***************************************************************************/  
9. /*先談談霍夫曼編碼的基本思想： 
10. /*對於一個給定的概率數組，所有元素之和為1，為了便於算法實現，我們擴大100倍 
11. /*選出序列中最小的兩個元素，刪除原序列中的這兩個數，相加得到一個新的元素 
12. /*再把新得到的數放入序列中，重復上述過程，直到序列中只有一個元素(100) 
13. /*規定：1、左孩子必須不大於右孩子節點的值；2、左邊編碼為0，右邊為1 
14. /***************************************************************************/  
15. typedef struct _ITEM  
16. {  
17.     int index;//元素在原來的數組中的索引值   
18.     int data;//數據   
19. }ITEM,*PITEM;  
20. typedef struct _TREE  
21. {  
22.     _TREE* lChild;//指向左孩子   
23.     _TREE* rChild;//指向右孩子   
24.     _TREE* pParent;//指向父節點   
25.     ITEM item;//當前節點的數據域   
26. }TREE,*PTREE;  
27. class CHuffmanTree  
28. {  
29. public:  
30.     CHuffmanTree(int s[],const int len);  
31.     virtual~ CHuffmanTree();  
32.     //初始化樹   
33.     void InitTree()const;  
34.     //打印輸入的數據   
35.     void ShowBuffer()const;  
36.     //打印樹   
37.     void ShowTree()const;  
38.     void ShowHuffmanCode();  
39. protected:  
40.     //對隊列元素進行兩次冒泡排序，以便選出最小的兩個數   
41.     void SortDeque();  
42.     //選出隊列中最小的兩個元素構造新的樹節點   
43.     void Select(int& m,int& n);  
44.     //構造哈弗曼樹   
45.     void CreateHuffmanTree();  
46. private:  
47.     int* pBuffer;//把元素復制到自己的內存裡，指向首地址   
48.     int m_iLength;//數組元素個數   
49.     PTREE pTree;  
50.     deque<ITEM> que;//雙向隊列，在這裡面進行篩選最小的兩個   
51. };  
52. #endif;  

#ifndef CHUFFMANTREE_H_ #define CHUFFMANTREE_H_ #include <assert.h> #include <iostream> #include <string> #include <deque> using namespace std; /***************************************************************************/ /*先談談霍夫曼編碼的基本思想： /*對於一個給定的概率數組，所有元素之和為1，為了便於算法實現，我們擴大100倍 /*選出序列中最小的兩個元素，刪除原序列中的這兩個數，相加得到一個新的元素 /*再把新得到的數放入序列中，重復上述過程，直到序列中只有一個元素(100) /*規定：1、左孩子必須不大於右孩子節點的值；2、左邊編碼為0，右邊為1 /***************************************************************************/ typedef struct _ITEM { int index;//元素在原來的數組中的索引值 int data;//數據 }ITEM,*PITEM; typedef struct _TREE { _TREE* lChild;//指向左孩子 _TREE* rChild;//指向右孩子 _TREE* pParent;//指向父節點 ITEM item;//當前節點的數據域 }TREE,*PTREE; class CHuffmanTree { public: CHuffmanTree(int s[],const int len); virtual~ CHuffmanTree(); //初始化樹 void InitTree()const; //打印輸入的數據 void ShowBuffer()const; //打印樹 void ShowTree()const; void ShowHuffmanCode(); protected: //對隊列元素進行兩次冒泡排序，以便選出最小的兩個數 void SortDeque(); //選出隊列中最小的兩個元素構造新的樹節點 void Select(int& m,int& n); //構造哈弗曼樹 void CreateHuffmanTree(); private: int* pBuffer;//把元素復制到自己的內存裡，指向首地址 int m_iLength;//數組元素個數 PTREE pTree; deque<ITEM> que;//雙向隊列，在這裡面進行篩選最小的兩個 }; #endif;

1. #include "stdafx.h"   
2. #include "HuffmanTree.h"   
3. CHuffmanTree::CHuffmanTree(int s[], const int len)  
4. :pBuffer(NULL)  
5. ,pTree(NULL)  
6. ,m_iLength(0)  
7. {  
8.     assert(len>0);  
9.     pBuffer=new int[len];  
10.     int* p=pBuffer;  
11.     for(int i=0;i<len;++i)  
12.     {  
13.         ITEM it;  
14.         it.index=i;  
15.         it.data=s[i];  
16.         que.push_back(it);  
17.         *(p+i)=s[i];  
18.     }  
19.     m_iLength=len;  
20.     pTree=new TREE[2*len-1];  
21.     InitTree();  
22. }  
23. CHuffmanTree::~CHuffmanTree()  
24. {//回收內存   
25.     if(pTree)  
26.     {  
27.         delete[] pTree;  
28.         pTree=NULL;  
29.     }  
30.     if(pBuffer)  
31.     {  
32.         delete[] pBuffer;  
33.         pBuffer=NULL;  
34.     }  
35. }  
36. void CHuffmanTree::InitTree() const  
37. {  
38.     int* p=pBuffer;  
39.     int i=0;  
40.     for(;i<2*m_iLength-1;++i)  
41.     {  
42.         (pTree+i)->lChild=NULL;  
43.         (pTree+i)->rChild=NULL;  
44.         (pTree+i)->pParent=NULL;  
45.         (pTree+i)->item.index=i;  
46.     }  
47.     for(i=0;i<m_iLength;++i)  
48.         (pTree+i)->item.data=*(p+i);  
49.     for(;i<2*m_iLength-1;++i)  
50.         (pTree+i)->item.data=0;  
51. }  
52. void CHuffmanTree::ShowBuffer() const  
53. {  
54.     for(int i=0;i<m_iLength;++i)  
55.         cout<<*(pBuffer+i)<<"   ";  
56.     cout<<endl;  
57. }  
58. void CHuffmanTree::ShowTree() const  
59. {  
60.     cout<<"index         lChild        rChild        pParent       data"<<endl;  
61.     for(int i=0;i<2*m_iLength-1;++i)  
62.     {  
63.         cout<<(pTree+i)->item.index<<"              ";  
64.         if((pTree+i)->lChild)  
65.             cout<<(pTree+i)->lChild->item.data<<"             ";  
66.         else  
67.             cout<<"0             ";  
68.         if((pTree+i)->rChild)  
69.             cout<<(pTree+i)->rChild->item.data<<"             ";  
70.         else  
71.             cout<<"0             ";  
72.         if((pTree+i)->pParent)  
73.             cout<<(pTree+i)->pParent->item.data<<"             ";  
74.         else  
75.             cout<<"0             ";    
76.         cout<<(pTree+i)->item.data<<endl;  
77.     }  
78.           
79. }  
80. void CHuffmanTree::Select(int& m,int& n)  
81. {  
82.     if(que.size()<2)  
83.         return;  
84.     SortDeque();  
85.     //經過兩次冒泡排序，最小的兩個元素的索引當然是0和1了   
86.     m=que.at(0).index;  
87.     n=que.at(1).index;  
88.     //出隊列   
89.     que.pop_front();  
90.     que.pop_front();  
91. }  
92. void CHuffmanTree::SortDeque()  
93. {  
94.     if(que.empty())  
95.         return;  
96.     //兩次冒泡排序就可以篩選出最小的兩個了   
97.     for(int i=0;i<2;++i)  
98.     {  
99.         for(int j=que.size()-1;j>i;--j)  
100.         {  
101.             if(que.at(j).data<que.at(j-1).data)  
102.             {  
103.                 ITEM temp=que.at(j);  
104.                 que.at(j)=que.at(j-1);  
105.                 que.at(j-1)=temp;  
106.             }  
107.         }  
108.     }  
109. }  
110. void CHuffmanTree::CreateHuffmanTree()  
111. {  
112.     for(int i=m_iLength;i<2*m_iLength-1;++i)  
113.     {  
114.         int m=0,n=0;  
115.         Select(m,n);  
116.         (pTree+m)->pParent=(pTree+i);  
117.         (pTree+n)->pParent=(pTree+i);  
118.         (pTree+i)->lChild=(pTree+m);  
119.         (pTree+i)->rChild=(pTree+n);  
120.         (pTree+i)->item.index=i;  
121.         (pTree+i)->item.data=(pTree+m)->item.data+(pTree+n)->item.data;  
122.         que.push_back((pTree+i)->item);//關鍵！產生的新節點一定要放入隊列中   
123.     }  
124. }  
125. void CHuffmanTree::ShowHuffmanCode()  
126. {  
127.     CreateHuffmanTree();//生成霍夫曼樹   
128.     for(int i=0;i<m_iLength;++i)  
129.     {  
130.         TREE* p=(pTree+i);  
131.         string s="";  
132.         while(p->pParent)  
133.         {//我們約定左0，右1   
134.             if(p->pParent->lChild->item.index==p->item.index)  
135.                 s+="0";  
136.             else  
137.                 s+="1";  
138.             p=p->pParent;  
139.         }  
140.         s=string(s.rbegin(),s.rend());//逆置   
141.         cout<<(pTree+i)->item.data<<"的編碼為:"<<s<<endl;//打印每個元素的霍夫曼編碼   
142.     }  
143. }  

代碼有注釋，在此不再啰嗦.

測試:

1. #include "stdafx.h"   
2. #include <iostream>   
3. #include "huffmantree.h"   
4. using std::cout;  
5. using std::endl;  
6.   
7. int _tmain(int argc, _TCHAR* argv[])  
8. {  
9.     int s[]={5,29,7,8,14,23,3,11};  
10.     CHuffmanTree tree(s,8);  
11.     tree.ShowBuffer();  
12.     tree.ShowTree();  
13.     tree.ShowHuffmanCode();  
14.     tree.ShowTree();  
15.     return 0;  
16. }