GDPU 数据结构 天码行空9

实验九 哈夫曼编码

一、【实验目的】

1、理解哈夫曼树的基本概念
2、掌握哈夫曼树的构造及数据结构设计
3、掌握哈夫曼编码问题设计和实现

二、【实验内容】

1、假设用于通信的电文仅由8个字母 {a, b, c, d, e, f, g, h} 构成，它们在电文中出现的概率分别为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 }，试为这8个字母设计哈夫曼编码。

提示:包含两个过程:
（1）构建哈夫曼树
（2）输出编码。

三、【实验源代码】

🍑 优先队列版

#include 
#include 
#include 
using namespace std;

// 定义结点结构体
struct Node
{
	Node *l;  // 左孩子结点
	Node *r;  // 右孩子结点
	int w;    // 结点权值
	char letter;  // 字符

	// 结点构造函数
	Node(Node* _l, Node* _r, int _w, char _letter)
	{
		l = _l;
		r = _r;
		w = _w;
		letter = _letter;
	}

	// 重载小于运算符
	bool operator < (const Node& cmp) const {
		return w > cmp.w;
	}
};

priority_queue<Node> heap;  // 定义优先队列用于构建哈夫曼树的堆
map<char, string> hafCode;  // 存储哈夫曼编码的映射表

// 构建哈夫曼树
Node* build()
{
	while (heap.size() > 1)
	{
		// 从堆中取出两个权值最小的结点，合并为一个新的父结点
		Node* x = new Node(heap.top().l, heap.top().r, heap.top().w, heap.top().letter);
		heap.pop();
		Node* y = new Node(heap.top().l, heap.top().r, heap.top().w, heap.top().letter);
		heap.pop();
		Node* node = new Node(x, y, x->w + y->w, '!');  // 父结点的字符设为'!'
		heap.push(*node);  // 将新父结点加入堆中
	}
	return new Node(heap.top().l, heap.top().r, heap.top().w, heap.top().letter);  // 返回哈夫曼树的根结点
}

// 递归遍历哈夫曼树，生成哈夫曼编码
void dfs(Node* n, string m)
{
	if (n->letter != '!')
	{
		hafCode.insert(make_pair(n->letter, m));  // 将字符和其对应的哈夫曼编码插入映射表
	}
	if (n->l != NULL)
		dfs(n->l, m + "0");  // 左孩子结点编码为m + "0"
	if (n->r != NULL)
		dfs(n->r, m + "1");  // 右孩子结点编码为m + "1"
}

// 输出字符的哈夫曼编码
void printHafCode()
{
	for (char i = 'a'; i <= 'h'; i++)
		cout << "字母 " << i << " 的哈夫曼码值是: " << hafCode[i] << endl;
}

int main()
{
	// 将初始字符权值放入优先队列中
	heap.push(Node(NULL, NULL, 7, 'a'));
	heap.push(Node(NULL, NULL, 19,'b'));
	heap.push(Node(NULL, NULL, 2, 'c'));
	heap.push(Node(NULL, NULL, 6, 'd'));
	heap.push(Node(NULL, NULL, 32,'e'));
	heap.push(Node(NULL, NULL, 3, 'f'));
	heap.push(Node(NULL, NULL, 21,'g'));
	heap.push(Node(NULL, NULL, 10,'h'));

	Node *root = build();  // 构建哈夫曼树
	dfs(root, "");  // 生成哈夫曼编码
	printHafCode();  // 输出哈夫曼编码
	return 0;
}
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

🍑 能跑就行

#include 
using namespace std;
#include 
#include 
typedef struct node {   //哈夫曼树中单个节点的信息
    int parent;   //父节点
    char letter;   //字母
    int lchild;
    int rchild;
    double weight;   //权值
}*HuffmanTree;
void Select(HuffmanTree& tree, int n, int& s1, int& s2) {   //找到权值最小的两个值的下标，其中s1的权值小于s2的权值
    int min = 0;
    for (int i = 1; i <= n; i++) {
        if (tree[i].parent == 0) {
            min = i;
            break;
        }
    }
    for (int i = min + 1; i <= n; i++) {
        if (tree[i].parent == 0 && tree[i].weight < tree[min].weight)
            min = i;
    }
    s1 = min;   //找到第一个最小值，并赋给s1
    for (int i = 1; i <= n; i++) {
        if (tree[i].parent == 0 && i != s1) {
            min = i;
            break;
        }
    }
    for (int i = min + 1; i <= n; i++) {
        if (tree[i].parent == 0 && i != s1 && tree[i].weight < tree[min].weight)
            min = i;
    }
    s2 = min;  //找到第二个最小值，并赋给s2
}
void CreateHuff(HuffmanTree& tree, char* letters, double* weights, int n) {
    int m = 2 * n - 1;   //若给定n个数要求构建哈夫曼树，则构建出来的哈夫曼树的结点总数为2n-1
    tree = (HuffmanTree)calloc(m + 1, sizeof(node));   //开辟空间顺序储存Huffman树，用calloc开辟的空间初始化的值为0（NULL），符合Huffman树初始化条件（parent、weight、lchild、rchild等初始化应为0），由于tree[0]不存数据（因为任何节点的父节点若为0，会与节点初始化0值相混淆，故不存数据），则要开辟（2n-1）+1个空间（额外开辟一个空间）
    for (int i = 1; i <= n; i++) {   //给节点赋字母及其对应的权值
        tree[i].weight = weights[i - 1];
        tree[i].letter = letters[i];
    }
    for (int i = n + 1; i <= m; i++) {
        int s1 = 0, s2 = 0;
        Select(tree, i - 1, s1, s2);   //每次循环选择权值最小的s1和s2,生成它们的父结点
        tree[i].weight = tree[s1].weight + tree[s2].weight;   //新创建的节点i 的权重是s1和s2的权重之和
        tree[i].lchild = s1;   //新创建的节点i 的左孩子是s1
        tree[i].rchild = s2;   //新创建的节点i 的右孩子是s2
        tree[s1].parent = i;   //s1的父亲是新创建的节点i
        tree[s2].parent = i;   //s2的父亲是新创建的节点i
    }   
}
void HuffmanCoding(HuffmanTree& tree, char**& HuffCode, int n) {
    HuffCode = (char**)malloc(sizeof(char*) * (n + 1));   //运用char型二级指针，可理解成包含多个char*地址的数组，开n+1个空间，因为下标为0的空间不用
    char* tempcode = (char*)malloc(sizeof(char) * n);
    tempcode[n - 1] = '\0';
    for (int i = 1; i <= n; i++) {
        int start = n - 1;
        int doing = i;   //doing为正在编码的数据节点
        int parent = tree[doing].parent;   //找到该节点的父结点
        while (parent) {   //直到父结点为0(NULL)，即父结点为根结点时停止
            if (tree[parent].lchild == doing)   //如果该结点是其父结点的左孩子，则编码为0，否则为1
                tempcode[--start] = '0';
            else
                tempcode[--start] = '1';
            doing = parent;   //继续往上进行编码
            parent = tree[parent].parent;
        }
        HuffCode[i] = (char*)malloc(sizeof(char) * (n - start));   //开辟用于存储编码的内存空间
        strcpy(HuffCode[i], &tempcode[start]);   //将编码拷贝到字符指针数组中的相应位置
    }
    free(tempcode); //释放辅助空间
}
int main() {
    int n = 8;
    char letters[9] = {' ','a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
    double weights[9] = {0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10};
    HuffmanTree tree;
    CreateHuff(tree, letters, weights, n);   //构建哈夫曼树
    char** HuffCode;
    HuffmanCoding(tree, HuffCode, n);
    for (int i = 1; i <= n; i++)
        printf("字母 %c 的哈夫曼编码值是: %s\n", tree[i].letter, HuffCode[i]);
    return 0;
}
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

👨‍🏫 参考资料