数据结构 实验报告-3

1. 哈夫曼编码

1.1 实验内容

给定一段文字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出一套编码，使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼编码并不是唯一的。

例如对字符串 “aaaxuaxz”，容易得到字母 ‘a’、’x’、’u’、’z’ 的出现频率对应为 4、2、1、1。我们可以设计编码 {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}，也可以用另一套 {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}，还可以用 {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}，三套编码都可以把原文压缩到 14 个字节。

但是 {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} 就不是哈夫曼编码，因为用这套编码压缩得到 00001011001001 后，解码的结果不唯一，”aaaxuaxz” 和 “aazuaxax” 都可以对应解码的结果。本题就请你判断任一套编码是否哈夫曼编码。

1.2 实验目的

掌握哈夫曼算法。

1.3 程序清单

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int     heap[999];
int heap_size = 0;

/**
 * @brief 向最小堆中插入元素
 * 
 * @param val 元素值
 */
void insert_heap(int val)
{
    heap[++heap_size] = val;

    int i = heap_size;
    while (i > 1 && heap[i / 2] > heap[i]) {
        int temp = heap[i];
        heap[i] = heap[i / 2];
        heap[i / 2] = temp;
        i /= 2;
    }
}

/**
 * @brief 从最小堆中提取最小元素
 * 
 * @return int 元素值
 */
int extract_min()
{
    int min_val = heap[1];
    heap[1] = heap[heap_size--];

    int i = 1;
    while (i * 2 <= heap_size) {
        int child = i * 2;
        if (child + 1 <= heap_size && heap[child + 1] < heap[child]) {
            child++;
        }

        if (heap[i] <= heap[child]) {
            break;
        }

        int temp = heap[i];
        heap[i] = heap[child];
        heap[child] = temp;
        i = child;
    }

    return min_val;
}

/* 字典树节点结构 */
typedef struct trie_node_s {
    struct trie_node_s  *left;  // 对应字符 '0'
    struct trie_node_s *right;  // 对应字符 '1'
    int                is_end;  // 标记是否为某个字符编码的结尾
} trie_node_t;

/**
 * @brief 创建字典树节点
 * 
 * @return trie_node_t* 节点指针
 */
trie_node_t* create_node()
{
    trie_node_t *node = (trie_node_t *)calloc(1, sizeof(trie_node_t));
    node->left = node->right = NULL;
    node->is_end = 0;
    return node;
}

/**
 * @brief 插入编码到字典树中并检查前缀
 * 
 * @param root 根节点指针
 * @param str  字符
 * @return int 0->Failed | 1->OK
 */
int insert_trie(trie_node_t *root, const char* str)
{
    trie_node_t *curr = root;

    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        if (curr->is_end) {
            // 已经有编码是当前编码的前缀
            return 0;
        }

        if (str[i] == '0') {
            if (!curr->left) {
                curr->left = create_node();
            }
            curr = curr->left;
        } else {
            if (!curr->right) {
                curr->right = create_node();
            }
            curr = curr->right;
        }
    }

    // 当前编码是其他已存在编码的前缀, 或是重复编码
    if (curr->left || curr->right || curr->is_end) {
        return 0;
    }
    curr->is_end = 1;
    return 1;
}

/**
 * @brief 释放字典树内存
 * 
 * @param root 根节点指针
 */
void free_trie(trie_node_t *root)
{
    if (root == NULL) {
        return;
    }

    free_trie(root->right);
    free_trie(root->left);
    free(root);
}

int main()
{
    // 读取字符总数
    int n;
    if (scanf("%d", &n) != 1) {
        return 0;
    }

    // 保存每个字符出现的频率
    int freq[256] = { 0 };
    for (int i = 0; i < n; i++) {
        int      f;
        char ch[5];

        // 用字符串读取可以自动跳过空格和换行
        scanf("%s %d", ch, &f);
        freq[(unsigned char)ch[0]] = f;
        insert_heap(f);
    }

    // 通过最小堆模拟构建哈夫曼树的过程，计算最优带权路径长度 (WPL)
    int optimal_wpl = 0;
    if (n > 1) {
        while (heap_size > 1) {
            int a = extract_min();
            int b = extract_min();
            int sum = a + b;

            // 每合并一次，累加到 WPL 中
            optimal_wpl += sum;
            insert_heap(sum);
        }
    } else {
        optimal_wpl = heap[1];
    }

    // 读取霍夫曼编码总数
    int m;
    scanf("%d", &m);

    // 依次验证 M 套编码方案
    while (m--) {
        int    is_valid = 1;
        int current_wpl = 0;

        trie_node_t *root = create_node();

        for (int i = 0; i < n; i++) {
            char ch[5];
            char code[100];
            scanf("%s %s", ch, code);

            if (is_valid) {
                // 累加当前方案的 WPL：频率 * 编码长度
                current_wpl += freq[(unsigned char)ch[0]] * strlen(code);

                // 将编码插入字典树，如果不是有效的前缀码，标记为无效
                if (!insert_trie(root, code)) {
                    is_valid = 0;
                }
            }
        }

        // 只有当符合前缀码规范，并且 WPL 严格等于最优 WPL 时，才是哈夫曼编码
        if (is_valid && current_wpl == optimal_wpl) {
            printf("Yes\r\n");
        } else {
            printf("No\r\n");
        }

        free_trie(root);
    }

    return 0;
}

1.4 调试步骤

  1. 输入测试数据
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
7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11
  1. 程序输出
1
2
3
4
Yes
Yes
No
No

1.5 分析与思考

设字符集大小为 n，需判断 m 套编码，每套 n 个编码的总长度为 L(即所有编码串的长度之和)。

  • 空间复杂度：$O(n \log n + m \cdot L)$

  • 时间复杂度：$O(n + L)$

2. 线索二叉树的建立和遍历

2.1 实验内容

本题要求实现建立中序线索二叉树和中序遍历中序线索二叉树。

2.2 实验目的

掌握二叉树的建立以及遍历。

2.3 程序清单

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <stdio.h>
#include <stdlib.h>

/* 线索二叉树节点 */
typedef struct thread_node_s {
    char data;
    int  ltag;
    int  rtag;

    struct thread_node_s *lchild;
    struct thread_node_s *rchild;
} thread_node_t;

/**
 * @brief 创建一个新节点
 * 
 * @param data 数据
 * @return thread_node_t* 节点指针
 */
thread_node_t* create_node(int data)
{
    thread_node_t *node = (thread_node_t *)malloc(sizeof(thread_node_t));
    node->data   = data;
    node->ltag   =    0;
    node->rtag   =    0;
    node->lchild = NULL;
    node->rchild = NULL;
    return node;
}

/**
 * @brief 通过先序遍历序列构建二叉树, 输入 -1 表示空节点
 * 
 * @return thread_node_t* 根节点指针
 */
thread_node_t* create_tree()
{
    char val;
    scanf(" %c", &val);

    if (val == '@') {
        // 空节点返回 NULL
        return NULL;
    } else {
        thread_node_t* node = create_node(val);
        node->lchild = create_tree();
        node->rchild = create_tree();
        return node;
    }
}

/**
 * @brief 线索化二叉树
 * 
 * @param node 根节点指针
 * @param pre    前驱指针
 */
void in_thread(thread_node_t *node, thread_node_t **pre)
{
    if (node != NULL) {
        // 递归线索化左子树
        in_thread(node->lchild, pre);

        // 处理当前节点的前驱
        if (node->lchild == NULL) {
            node->lchild = *pre;
            node->ltag = 1;
        }

        // 处理前驱节点的后继
        if (*pre != NULL && (*pre)->rchild == NULL) {
            (*pre)->rchild = node;
            (*pre)->rtag = 1;
        }

        // 更新 pre 为当前节点
        *pre = node;

        // 递归线索化右子树
        in_thread(node->rchild, pre);
    }
}

/**
 * @brief 建立中序线索二叉树
 * 
 * @param tree 二叉树根节点指针
 */
void create_in_thread(thread_node_t *tree)
{
    thread_node_t *pre = NULL;

    if (tree != NULL) {
        in_thread(tree, &pre);

        // 处理最后一个节点
        if (pre != NULL && pre->rchild == NULL) {
            pre->rtag = 1;
        }
    }
}

thread_node_t* first_node(thread_node_t *p)
{
    while (p->ltag == 0) {
        p = p->lchild;
    }
    return p;
}

thread_node_t* next_node(thread_node_t *p)
{
    if (p->rtag == 1) {
        return p->rchild;
    } else {
        return first_node(p->rchild);
    }
}

/**
 * @brief 遍历中序线索二叉树
 * 
 * @param tree 根节点指针
 */
void in_order(thread_node_t *tree)
{
    for (thread_node_t *p = first_node(tree); p != NULL; p = next_node(p)) {
        printf("%c  %d  %d\r\n", p->data, p->ltag, p->rtag);
    }
}

int main()
{
    // 动态构建二叉树
    thread_node_t *root = create_tree();
    if (root == NULL) {
        return -1;
    }

    create_in_thread(root);

    in_order(root);
    return 0;
}

2.4 调试步骤

  1. 输入测试数据
1
AB@D@@CE@@@
  1. 程序输出
1
2
3
4
5
B  1  0
D  1  1
A  0  0
E  1  1
C  0  1

2.5 分析与思考

设二叉树节点数为 n。

  • 空间复杂度：$O(n)$

  • 时间复杂度：$O(n)$

课程报告
#河北工业大学 #数据结构
数据结构 实验报告-3
https://flowerdown.org/posts/20220519-192412
作者
Unrealfeathers
发布于
2022年5月19日
许可协议