-
Notifications
You must be signed in to change notification settings - Fork 0
/
HuffmanEncode.cpp
66 lines (61 loc) · 1.72 KB
/
HuffmanEncode.cpp
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
#include "HuffmanEncode.h"
#include <algorithm>
#include <cmath>
#include <fstream>
#include <map>
#include <queue>
using namespace std;
void getHuffmanTree(priority_queue<Hnode *, vector<Hnode *>, cmp> &pq, int n)
{ //节点优先队列和节点名
for (int i = 0; i < n; i++)
{ //n次编码
if (pq.size() == 1)
{
break; //只剩下一个节点
}
Hnode *new_Pnode = new Hnode(); //新节点
Hnode *new_Lnode = pq.top(); //当前概率最小的
pq.pop(); //出队列
Hnode *new_Rnode = pq.top(); //第二小的
pq.pop(); //出队列
new_Pnode->weight = new_Lnode->weight + new_Rnode->weight; //节点为两个的和
new_Pnode->lchild = new_Lnode;
new_Pnode->rchild = new_Rnode;
new_Lnode->parent = new_Rnode->parent = new_Pnode;
pq.push(new_Pnode);
}
}
void getHuffmanCode(priority_queue<Hnode *, vector<Hnode *>, cmp> &pq, ChCode *code, Hnode *node, int n)
{
getHuffmanTree(pq, n); //获取哈夫曼树
for (int i = 0; i < n; i++)
{
Hnode *now_node = &node[i];
while (now_node->parent != NULL)
{
if (now_node == now_node->parent->lchild)
{
code[i].hoffmanCode.push_front(0);
}
else
{
code[i].hoffmanCode.push_front(1);
}
now_node = now_node->parent;
}
}
}
void getHuffmanTable(ChCode *code, int n)
{
ofstream fout("HuffmanCodeTable.txt", ios::out);
fout << n << endl;
for (int i = 0; i < n; i++)
{
fout << code[i].ch << " ";
deque<int>::iterator iter;
for (iter = code[i].hoffmanCode.begin(); iter != code[i].hoffmanCode.end(); iter++)
fout << *iter;
fout << endl;
}
fout.close();
}