C++实现哈夫曼树编码解码

时间:2022-09-26 09:43:09

本文实例为大家分享了C++实现哈夫曼树的编码解码,供大家参考,具体内容如下

代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#pragma once
#include<iostream>
#include<stack>
using namespace std;
#define m 20
stack<int> s;
/*哈夫曼树结点类HuffmanNode声明*/
template<class T>
class HuffmanNode {
private:
 HuffmanNode<T> * left;
 HuffmanNode<T> * right;
 T data;
 int weight;
public:
 HuffmanNode(){}
 HuffmanNode(const T& item, HuffmanNode<T> * l, HuffmanNode<T> * r):data(item),left(l),right(r){}
 HuffmanNode<T> * getLeft() { return left; }
 void setLeft(HuffmanNode<T> * left) { this->left = left; }
 HuffmanNode<T> * getRight() { return right; }
 void setRight(HuffmanNode<T> * right) { this->right=right; }
 T& getData() { return data; }
 void setData(const T& item) { data = item; }
 int getWeight() { return weight; }
 void setWeight(int weight) { this->weight = weight; }
};
 
/*哈夫曼树类HuffmanTree声明*/
template<class T>
class HuffmanTree {
private:
 HuffmanNode<T> * root;
 T data[m];
 int weight[m];
 int count;
public:
 HuffmanTree(HuffmanNode<T> * t=NULL):root(t){}
 void CreateHuffmanTree();//创建哈夫曼树
 HuffmanNode<T> * getRoot() { return root; }
 void setRoot(HuffmanNode<T> * t) { root = t; }
 void inputNodes();//输入各个结点的data和weight值
 HuffmanNode<T> * deCode(HuffmanNode<T>*t,T item);
 void showCode();
};
 
template<class T>
inline void HuffmanTree<T>::CreateHuffmanTree()
{
 inputNodes();
 HuffmanNode<T> ** H = new HuffmanNode<T>*[count];
 HuffmanNode<T> * p1 = NULL, *p2 = NULL, * p,* t;
 for (int i = 0; i < count; i++) {
 H[i] = new HuffmanNode<T>();
 H[i]->setData(data[i]);
 H[i]->setWeight(weight[i]);
 H[i]->setLeft(NULL);
 H[i]->setRight(NULL);
 }
 
 for (int i = 0; i < count - 1; i++) {
 p = new HuffmanNode<T>();
 p1 = H[i];
 p2 = H[i + 1];
 p->setLeft(p1);
 p->setRight(p2);
 p->setWeight(p1->getWeight() + p2->getWeight());
 //将新的结点插入结点数组中的合适位置,并将被合并的两个结点删除
 t = p;
 int j = i + 2;
 while ( j < count &&H[j]->getWeight() < t->getWeight()) {
  H[j - 1] = H[j];
  j++;
 }
 H[j - 1] = t;
 }
 root = H[count - 1];
}
 
template<class T>
inline void HuffmanTree<T>::inputNodes()
{
 int i = 0;
 for (int j = 0; j < m; j++) {
 data[j] = NULL;
 weight[j] = 0;
 }
 while (cin >> data[i] >> weight[i]) {
 i++;
 }
 count = i;
}
 
template<class T>
inline HuffmanNode<T>* HuffmanTree<T>::deCode( HuffmanNode<T> * t,T item)
{
 HuffmanNode<T> * p, * q;
 if(t==NULL)
 return NULL;
 if (t->getData() == item)
 return t;
 if ((p = deCode(t->getLeft(), item))!=NULL) {
 s.push(0);
 return p;
 }
 else if((q = deCode(t->getRight(), item))!=NULL){
 s.push(1);
 return q ;
 }
}
 
template<class T>
inline void HuffmanTree<T>::showCode()
{
 cout << root->getWeight() << endl;
 cout << (root->getLeft())->getRight()->getData() << endl;
 for (int i = 0; i < count; i++) {
 cout << data[i] << "——";
 deCode(root, data[i]);
 while (!s.empty()) {
  cout << s.top();
  s.pop();
 }
 cout << endl;
 }
}

测试程序:

?
1
2
3
4
5
6
7
8
9
10
11
#include<iostream>
#include"HuffmanTree.h"
using namespace std;
 
int main() {
 HuffmanTree<char> * tree = new HuffmanTree<char>();
 tree->CreateHuffmanTree();
 tree->showCode();
 system("pause");
 return 0;
}

测试数据:

n 1
s 3
t 4
a 10
i 12
p 13
e 15
Ctrl+Z 回车结束输入
输入时权值由小到大排序…也可以在程序里加一个排序

结果:

C++实现哈夫曼树编码解码

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:https://blog.csdn.net/qq_36795903/article/details/89916203