一、实验目的
- 掌握哈夫曼树的构造算法。
- 掌握哈夫曼编码的构造算法。
二、实验内容（题目）
输入一串字符串，根据给定的字符串中字符出现的频率建立相应哈夫曼树，构造哈夫曼编码表，在此基础上可以对待压缩文件进行压缩（即编码），同时可以对压缩后的二进制编码文件进行解压（即译码）。
三、实验环境
（1）软件系统
操作系统：Windows 10
编程环境：Embarcadero Dev-C++ 6.3，包含GNU GCC编译器和GDB调试器
（2）硬件系统
CPU：Intel® Core™ i7-10875H CPU @ 2.30GHz
内存：16GB
硬盘：500GB SSD
四、程序代码
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
// 声明全局变量
int num; // 不同字符的数量
int alpha[26]; // 字符频率数组
int num2 = 0;
int k = 0; // 实际使用的数组长度
char list[26]; // 存储字符本身
// 哈夫曼树的节点结构
typedef struct {
int weight; // 节点的权重
int parent, lchild, rchild; // 双亲和孩子节点的索引
} HTNode, *HuffmanTree; // 定义哈夫曼树
typedef char** HuffmanCode; // 定义哈夫曼编码类型
// 从哈夫曼树中选择两个权重最小且未被选择的节点
void Select(HuffmanTree HT, int sum, int &s1, int &s2)
{
int i, min1 = INT_MAX, min2 = INT_MAX;
for (i = 1; i <= sum; i++)
{
if (HT[i].parent == 0 && HT[i].weight < min1)
{
min2 = min1;
min1 = HT[i].weight;
s2 = s1;
s1 = i;
}
else if (HT[i].parent == 0 && HT[i].weight < min2)
{
min2 = HT[i].weight;
s2 = i;
}
}
}
// 创建哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT, int n)
{
if (n <= 1) return;
int m = 2 * n - 1;
HT = new HTNode[m + 1];
for (int i = 1; i <= m; i++) {
HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0;
}
for (int i = 1; i <= n; i++) // 初始化叶子节点的权重
HT[i].weight = alpha[i - 1];
int s1, s2;
for (int i = n + 1; i <= m; i++) // 构建哈夫曼树
{
Select(HT, i - 1, s1, s2);
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
// 生成哈夫曼编码
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
HC = new char*[n + 1];
char *cd = new char[n];
cd[n - 1] = '\0';
for (int i = 1; i <= n; i++)
{
int start = n - 1;
for (int c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
{
cd[--start] = (HT[f].lchild == c) ? '0' : '1';
}
HC[i] = new char[n - start];
strcpy(HC[i], &cd[start]);
}
delete[] cd;
}
// 输出哈夫曼树和编码
void Output(HuffmanTree HT, HuffmanCode HC)
{
for (int i = 1; i <= 2 * k - 1; i++)
cout << i << " " << HT[i].weight << " " << HT[i].parent << " " << HT[i].lchild << " " << HT[i].rchild << endl;
for (int i = 1; i <= k; i++)
{
cout << list[i - 1] << ":" << HC[i];
if (i != k) cout << " ";
}
cout << endl;
}
// 初始化字符频率表
void Initalpha(int a[], string s)
{
memset(a, 0, sizeof(int) * 26);
for (char c : s) {
if (islower(c)) a[c - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (a[i] != 0) {
cout << char(i + 'a') << ":" << a[i] << " ";
alpha[k] = a[i];
list[k++] = char(i + 'a');
}
}
cout << endl;
}
// 重置数据，为新的输入做准备
void InitData(int fre[])
{
memset(fre, 0, sizeof(int) * 26);
memset(list, 0, sizeof(list));
k = num2 = num = 0;
}
// 将字符串翻译成哈夫曼编码
void Translate(HuffmanCode HC, string s)
{
for (char c : s) {
if (islower(c)) cout << HC[c - 'a' + 1];
}
cout << endl;
}
int main()
{
string s;
while (cin >> s && s != "0")
{
InitData(alpha);
Initalpha(alpha, s);
HuffmanTree HT;
HuffmanCode HC;
CreateHuffmanTree(HT, k);
CreatHuffmanCode(HT, HC, k);
Output(HT, HC);
Translate(HC, s);
}
return 0;
}
五、实验分析
从以下方面分析：
1、正确性（输入的测试数据和测试结果，附测算截屏）
在提供的代码中，主要流程包括统计字符频率、构建哈夫曼树、生成哈夫曼编码、以及最后的编码输出和字符串翻译。函数正确统计输入中每个小写字母的出现次数。这是哈夫曼编码的基础，确保每个字符根据其出现频率被适当处理。通过连续选择两个最小权重的未选择节点，程序正确地构建了哈夫曼树。这保证了树的最优性，即常见字符有较短的路径。程序从叶节点到根节点反向追踪生成编码，确保了每个字符的哈夫曼编码是正确和唯一的。
测算截屏：
2、可读性（主要在源代码中体现）
• 程序结构清晰，各函数功能明确，对主要的功能块有基本的注释。
• 使用了结构体和指针来管理哈夫曼树，增强了代码的模块化。
3、健壮性（容错性，主要在源代码中体现，在此简要说明）
• 优点：
• 程序能够持续处理多组输入直到遇到"0"。
• 缺点：
• 缺少对非预期输入（如大写字母、特殊字符等）的处理。
• 使用全局变量可能导致数据处理上的错误。
4、时间和空间复杂度（针对核心算法函数分析）
• 时间复杂度：整个程序的时间复杂度主要受哈夫曼树构建阶段的影响，大致为O(n2)。
• 空间复杂度：程序主要空间消耗来自于哈夫曼树和编码表的存储，总体空间复杂度为O(n)，其中n是不同字符的数量。
实验结束
关注点赞收藏，获取更多干货内容~
本篇收录于数据结构专栏下，可前往首页查看更多