HuffmanCode.h
1 #ifndef HUFFMANCODE_H
2 #define HUFFMANCODE_H
3
4 enum LRSTATUS
5 {
6 LEFTCHILD, //左子树
7 RIGHTCHILD //右子树
8 };
9
10 struct HuffmanCode
11 {
12 //哈弗曼编码类
13 int weight; //权值
14 int * pPath; //路径指针
15 int pathLength; //路径长度
16 HuffmanCode() //默认构造函数
17 {
18 weight = 0;
19 pPath = 0;
20 pathLength = 0;
21 }
22 //HuffmanCode(int n) //初始化路径指针成员
23 //{
24 // pPath = new int [n];
25 //}
26 //~HuffmanCode() //销毁并释放路径指针成员
27 //{
28 // if (0!=pPath)
29 // {
30 // delete [] pPath;
31 // pPath = 0;
32 // }
33 //}
34 };
35
36 #endif //HUFFMANCODE_H
HuffmanNode.h
1 #ifndef HUFFMANNODE_H
2 #define HUFFMANNODE_H
3
4 enum NODESTATUS
5 {
6 IN_FOREST, //在森林中
7 OUT_FOREST //不在森林中
8 };
9
10 struct HuffmanNode
11 {
12 //哈弗曼节点结构类
13 int weight; //节点权值
14 NODESTATUS flag; //是否在森林里的标志：IN_FOREST为在森林中；OUT_FOREST为不在森林中
15 HuffmanNode * parent; //双亲指针
16 HuffmanNode * lChild; //左子树指针
17 HuffmanNode * rChild; //右子树指针
18
19 HuffmanNode() //初始化成员数据
20 {
21 weight = 0;
22 flag = OUT_FOREST;
23 parent = 0;
24 lChild = 0;
25 rChild = 0;
26 }
27 };
28
29 #endif //HUFFMANNODE_H
HuffmanTree.h
1 #ifndef HUFFMANTREE_H
2 #define HUFFMANTREE_H
3
4 #include "HuffmanCode.h"
5 #include "HuffmanNode.h"
6
7 class HuffmanTree
8 {
9 //哈夫曼树类
10 private:
11 HuffmanNode * pNode; //哈弗曼节点指针（即哈弗曼树的节点数组）
12 HuffmanCode * pCode; //哈弗曼编码指针（即哈弗曼树的路径数组）
13 int * pWeight; //哈弗曼权值指针（即哈弗曼树的权值数组）
14 int size; //哈弗曼权值数组大小
15 protected:
16 public:
17 HuffmanTree(int * pWeight, int size); //哈夫曼树构造函数
18 ~HuffmanTree(){}; //哈弗曼树析构函数
19
20 void CreateHuffmanTree(HuffmanNode ** ppNode); //创建哈弗曼树，使用ppNode返回哈弗曼节点数组
21 void GetHuffmanCode(HuffmanNode * pNode, HuffmanCode ** ppCode); //获取哈弗曼编码，使用ppCode返回哈弗曼路径数组
22 };
23
24 void FreeHuffmanTree(HuffmanNode ** ppNode); //释放有函数CreateHuffmanTree申请的动态内存
25 void FreeHuffmanTree(HuffmanCode ** ppCode); //释放有函数GetHuffmanCode申请的动态内存
26
27 #endif //HUFFMANTREE_H
HuffmanTree.cpp
1 #include "HuffmanTree.h"
2 #include <iostream>
3 #include <iomanip> //for setw()
4
5 using namespace std;
6
7 #define DEBUG
8
9 #define MAX_VALUE 0x7FFFFFFF
10 #define WIDTH 12
11
12 //************************************
13 // Method: HuffmanTree
14 // FullName: HuffmanTree::HuffmanTree
15 // Access: public
16 // Returns:
17 // Qualifier: HuffmanTree类构造函数，使用HuffmanTree类之前必须进行类对象初始化
18 // Parameter: int * pWeight
19 // Parameter: int size
20 //************************************
21 HuffmanTree::HuffmanTree(int * pWeight, int size)
22 {
23 this->pWeight = pWeight;
24 this->size = size;
25 }
26
27 //************************************
28 // Method: CreateHuffmanTree
29 // FullName: HuffmanTree::CreateHuffmanTree
30 // Access: public
31 // Returns: void
32 // Qualifier: 创建哈弗曼树，返回指向保存哈弗曼树节点数组的指针
33 // Parameter: HuffmanNode * * ppNode
34 //************************************
35 void HuffmanTree::CreateHuffmanTree(HuffmanNode ** ppNode)
36 {
37 _ASSERT(pWeight || ppNode); //判断是否是空指针
38
39 int nodeNum = 2*size-1; //哈弗曼树总节点数
40 if (nodeNum<=0)
41 return ; //出现错误退出函数
42 pNode = new HuffmanNode [nodeNum];
43 _ASSERT(pNode);
44 for (int i=0 ; i<size ; ++i) //赋初值
45 {
46 pNode[i].weight = pWeight[i];
47 pNode[i].flag = IN_FOREST;
48 }
49 int min1 = MAX_VALUE, min2 = MAX_VALUE; //最小值和次小值
50 int pos1 = -1, pos2 = -1; //最小值和次小值位置
51 for (int i=0 ; i<size ; ++i) //遍历所有节点并且赋值
52 {
53 for (int j=0 ; j<nodeNum ; ++j) //查找最小值和次小值
54 {
55 if (pNode[j].flag==IN_FOREST && pNode[j].weight<min1)
56 {
57 min2 = min1;
58 pos2 = pos1;
59 min1 = pNode[j].weight;
60 pos1 = j;
61 }
62 else if (pNode[j].flag==IN_FOREST && pNode[j].weight<min2)
63 {
64 min2 = pNode[j].weight;
65 pos2 = j;
66 }
67 }
68 if (-1!=pos1 && -1!=pos2)
69 {
70 //生成最小值和次小值的二叉树双亲
71 pNode[size+i].weight = (pNode[pos1].weight+pNode[pos2].weight);
72 pNode[size+i].flag = IN_FOREST;
73 pNode[size+i].lChild = &pNode[pos1];
74 pNode[size+i].rChild = &pNode[pos2];
75 pNode[pos1].flag = OUT_FOREST;
76 pNode[pos1].parent = &pNode[size+i];
77 pNode[pos2].flag = OUT_FOREST;
78 pNode[pos2].parent = &pNode[size+i];
79 #ifdef NODEBUG
80 cout << "pNode[" << (size+i) << "].weight = " << pNode[size+i].weight << endl;
81 cout << "pNode[" << (size+i) << "].flag = " << pNode[size+i].flag << endl;
82 cout << "pNode[" << (size+i) << "].parent = " << pNode[size+i].parent << endl;
83 cout << "pNode[" << (size+i) << "].lChild = " << pNode[size+i].lChild << endl;
84 cout << "pNode[" << (size+i) << "].rChild = " << pNode[size+i].rChild << endl;
85 cout << "pNode[" << (pos1) << "].weight = " << pNode[pos1].weight << endl;
86 cout << "pNode[" << (pos1) << "].flag = " << pNode[pos1].flag << endl;
87 cout << "pNode[" << (pos1) << "].parent = " << pNode[pos1].parent << endl;
88 cout << "pNode[" << (pos1) << "].lChild = " << pNode[pos1].lChild << endl;
89 cout << "pNode[" << (pos1) << "].rChild = " << pNode[pos1].rChild << endl;
90 cout << "pNode[" << (pos2) << "].weight = " << pNode[pos2].weight << endl;
91 cout << "pNode[" << (pos2) << "].flag = " << pNode[pos2].flag << endl;
92 cout << "pNode[" << (pos2) << "].parent = " << pNode[pos2].parent << endl;
93 cout << "pNode[" << (pos2) << "].lChild = " << pNode[pos2].lChild << endl;
94 cout << "pNode[" << (pos2) << "].rChild = " << pNode[pos2].rChild << endl;
95 #endif //DEBUG
96 //重置最小值和次小值
97 min1 = min2 = MAX_VALUE;
98 //重置最小值和次小值位置
99 pos1 = pos2 = -1;
100 }
101 if (i==size-1)
102 {
103 pNode[size+i-1].flag = OUT_FOREST;
104 }
105 #ifdef NODEBUG
106 cout << "node [] = {" << setw(WIDTH) << "weight" << setw(WIDTH) << "flag" << endl;
107 for (int k=0 ; k<nodeNum ; ++k)
108 {
109 cout << setw(11) << " ";
110 cout << setw(WIDTH) << (pNode[k].flag==0 ? "IN_FOREST" : "OUT_FOREST") << setw(WIDTH) << pNode[k].weight << endl;
111 }
112 cout << setw(11) << "}" << endl;
113 #endif //DEBUG
114 }
115 #ifdef NODEBUG
116 for (int k=0 ; k<nodeNum ; ++k)
117 {
118 cout << "pNode[" << (k) << "].weight = " << pNode[k].weight << endl;
119 cout << "pNode[" << (k) << "].flag = " << pNode[k].flag << endl;
120 cout << "pNode[" << (k) << "].parent = " << pNode[k].parent << endl;
121 cout << "pNode[" << (k) << "].lChild = " << pNode[k].lChild << endl;
122 cout << "pNode[" << (k) << "].rChild = " << pNode[k].rChild << endl;
123 }
124 #endif //DEBUG
125 *ppNode = pNode;
126 }
127
128 //************************************
129 // Method: GetHuffmanCode
130 // FullName: HuffmanTree::GetHuffmanCode
131 // Access: public
132 // Returns: void
133 // Qualifier: 创建哈夫曼编码，返回指向哈弗曼编码数组的指针（注：调用该函数前一定要先使用函数CreateHuffmanTree）
134 // Parameter: HuffmanNode * pNode
135 // Parameter: HuffmanCode * * ppCode
136 //************************************
137 void HuffmanTree::GetHuffmanCode(HuffmanNode * pNode, HuffmanCode ** ppCode)
138 {
139 _ASSERT(pNode || ppCode);
140 if (size<=0)
141 return ; //终止函数执行
142 #ifdef NODEBUG
143 for (int k=0 ; k<size*2-1 ; ++k)
144 {
145 cout << "pNode[" << (k) << "].weight = " << pNode[k].weight << endl;
146 cout << "pNode[" << (k) << "].flag = " << pNode[k].flag << endl;
147 cout << "pNode[" << (k) << "].parent = " << pNode[k].parent << endl;
148 cout << "pNode[" << (k) << "].lChild = " << pNode[k].lChild << endl;
149 cout << "pNode[" << (k) << "].rChild = " << pNode[k].rChild << endl;
150 }
151 #endif //DEBUG
152
153 pCode = new HuffmanCode [size];
154 _ASSERT(pCode);
155
156 for (int i=0 ; i<size ; ++i) //赋值操作
157 {
158 pCode[i].weight = pWeight[i]; //权值赋值
159 int pCode_Length = 0; //临时变量
160 HuffmanNode * temp = &pNode[i]; //临时变量
161 while (NULL!=temp->parent)
162 {
163 ++pCode_Length;
164 temp = temp->parent;
165 }
166 pCode[i].pathLength = pCode_Length; //路径长度赋值
167 pCode[i].pPath = new int [pCode[i].pathLength]; //路径数组创建
168 temp = &pNode[i]; //重新复制临时变量
169 for (int j=pCode_Length-1 ; j>=0 ; --j) //路径数组赋值
170 {
171 if (NULL!=temp->parent)
172 {
173 HuffmanNode * putValue1 = temp->parent->lChild; //DEBUG
174 HuffmanNode * putValue2 = temp->parent->lChild; //DEBUG
175 if (temp==temp->parent->lChild)
176 pCode[i].pPath[j] = LEFTCHILD;
177 else
178 pCode[i].pPath[j] = RIGHTCHILD;
179 temp = temp->parent;
180 }
181 }
182 #ifdef NODEBUG
183 cout << "code [] = {" << setw(WIDTH) << "weight" << setw(WIDTH) << "pPath" << endl;
184 cout << setw(11) << " ";
185 cout << setw(WIDTH) << pCode[i].weight << ", ";
186 cout << setw(11) << " ";
187 for (int k=0 ; k<pCode_Length ; ++k)
188 cout << pCode[i].pPath[k] << ",";
189 cout << endl;
190 #endif //DEBUG
191 }
192 #ifdef NODEBUG
193 for (int k=0 ; k<size*2-1 ; ++k)
194 {
195 cout << "pNode[" << (k) << "].weight = " << pNode[k].weight << endl;
196 cout << "pNode[" << (k) << "].flag = " << pNode[k].flag << endl;
197 cout << "pNode[" << (k) << "].parent = " << pNode[k].parent << endl;
198 cout << "pNode[" << (k) << "].lChild = " << pNode[k].lChild << endl;
199 cout << "pNode[" << (k) << "].rChild = " << pNode[k].rChild << endl;
200 }
201 #endif //DEBUG
202 *ppCode = pCode;
203 }
204
205 //************************************
206 // Method: FreeHuffmanTree
207 // FullName: FreeHuffmanTree
208 // Access: public
209 // Returns: void
210 // Qualifier: 销毁由函数CreateHuffmanTree申请的对象
211 // Parameter: HuffmanNode * * ppNode
212 //************************************
213 void FreeHuffmanTree(HuffmanNode ** ppNode)
214 {
215 if (NULL!=ppNode && NULL!=*ppNode)
216 {
217 delete [] *ppNode;
218 *ppNode = NULL;
219 }
220 }
221
222 //************************************
223 // Method: FreeHuffmanTree
224 // FullName: FreeHuffmanTree
225 // Access: public
226 // Returns: void
227 // Qualifier: 销毁由函数GetHuffmanCode申请的内存
228 // Parameter: HuffmanCode * * ppCode
229 //************************************
230 void FreeHuffmanTree(HuffmanCode ** ppCode)
231 {
232 if (NULL!=ppCode && NULL!=*ppCode)
233 {
234 int size = _msize(*ppCode)/sizeof(HuffmanCode);
235 for (int i=0 ; i<size ; ++i)
236 {
237 if (NULL!=(*ppCode+i)->pPath)
238 {
239 delete [] (*ppCode+i)->pPath;
240 (*ppCode+i)->pPath = NULL;
241 }
242 }
243 delete [] *ppCode;
244 *ppCode = NULL;
245 }
246 }
Main.cpp
1 #include <iostream>
2 #include "HuffmanTree.h"
3
4 using namespace std;
5
6 #define DEBUG
7
8 #define _CRTDBG_MAP_ALLOC
9 #include <stdlib.h>
10 #include <crtdbg.h>
11
12 #ifndef DBG_NEW
13 #define DBG_NEW new ( _NORMAL_BLOCK , __FILE__ , __LINE__ )
14 #define new DBG_NEW
15 #endif
16
17 int main() //测试代码
18 {
19 ::_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
20 ::_CrtSetReportMode(_CRT_WARN, _CRTDBG_MODE_FILE | _CRTDBG_MODE_DEBUG);
21 ::_CrtSetReportFile(_CRT_WARN, _CRTDBG_FILE_STDOUT);
22
23 int weight[] = {87, 67, 45, 3, 6, 9, 11};
24 int size = sizeof(weight)/sizeof(int);
25 #ifdef DEBUG
26 cout << "weight [] = {" ;
27 for (int i=0 ; i<size ; ++i)
28 cout << weight[i] << ", " ;
29 cout << "}" << endl;
30 #endif //DEBUG
31 HuffmanTree obj(weight, size);
32 HuffmanNode * pNode = NULL;
33 obj.CreateHuffmanTree(&pNode);
34 HuffmanCode * pCode = NULL;
35 obj.GetHuffmanCode(pNode, &pCode);
36
37 FreeHuffmanTree(&pNode);
38 FreeHuffmanTree(&pCode);
39
40 return 0;
41 }
以上程序共5个文件：
1.Main.cpp文件主要实现对哈弗曼树、哈弗曼编码的测试，并且使用VS专用内存泄露检测代码进行内存泄露检测；
2.类HuffmanNode主要实现哈弗曼节点结构构造；
3.类HuffmanCode主要实现对哈弗曼树路径的存储；
4.类HuffmanTree主要实现哈弗曼树，并且实现创建哈弗曼树，创建哈弗曼编码；
5.使用宏#define DEBUG来对哈弗曼类代码中间结果进行验证。
原文链接: https://www.cnblogs.com/superstargg/p/3155709.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/93394
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
