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. }
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;
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. }