数据结构实训哈夫曼编码c++

哈夫曼编码是一种常用的数据压缩算法，它可以根据字符出现的频率构建一棵二叉树，并将出现频率较高的字符赋予较短的编码，从而减少数据的存储空间。

在C语言中实现哈夫曼编码，首先需要定义一个结构体来表示哈夫曼树的节点，包括字符、字符出现的频率以及左右子节点。

接下来，可以通过读取文件的方式统计字符出现的频率，并将每个字符及其出现的频率保存在一个数组中。

然后，需要根据字符频率构建哈夫曼树。可以通过构建最小堆来实现，首先将所有字符的频率作为权值存放在堆中。然后，从堆中选取两个频率最小的节点，将它们合并成一个新的节点，并将新节点的频率设为两个子节点频率之和。将新节点插入堆中，并重复上述步骤，直到堆中只有一个节点，即为根节点。

接着，可以通过遍历哈夫曼树，给每个字符赋予对应的编码。对于根节点的左子树，编码为0，右子树编码为1。遍历过程中，将编码保存在一个编码表中。

最后，可以根据编码表将原始数据进行编码。将原始数据拆分为单个字符，根据编码表找到对应的编码，将编码字符串连起来。最终得到的编码就是哈夫曼编码。

总结来说，实现哈夫曼编码主要包括：统计字符频率、构建哈夫曼树、遍历哈夫曼树生成编码表和进行编码。通过这些步骤，可以实现对数据进行压缩，并减少存储空间的占用。

相关问题

数据结构构造哈夫曼树c++

哈夫曼树是一种特殊的二叉树，它的叶子节点对应着要编码的字符，而非叶子节点则对应着编码。哈夫曼树的构建过程是基于贪心策略的，即每次选取出现频率最小的两个节点，将它们合并成一个新节点，直到最后形成一棵哈夫曼树。以下是一个 C++ 的实现：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 定义哈夫曼树节点结构体
struct TreeNode {
    char data; // 节点存储的字符
    int freq; // 节点对应字符出现的频率
    TreeNode* left; // 左子节点
    TreeNode* right; // 右子节点
    TreeNode(char data, int freq) : data(data), freq(freq), left(nullptr), right(nullptr) {}
};

// 定义比较函数，用于优先队列的排序
struct cmp {
    bool operator()(TreeNode* a, TreeNode* b) {
        return a->freq > b->freq; // 频率小的节点优先级高
    }
};

// 构建哈夫曼树的函数
TreeNode* buildHuffmanTree(vector<char>& chars, vector<int>& freqs) {
    priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq; // 定义优先队列
    for (int i = 0; i < chars.size(); i++) {
        TreeNode* node = new TreeNode(chars[i], freqs[i]); // 创建节点，存储字符和频率
        pq.push(node); // 将节点加入到优先队列中
    }
    while (pq.size() > 1) { // 只要队列中还有两个及以上的节点
        TreeNode* left = pq.top(); // 取出频率最小的节点
        pq.pop();
        TreeNode* right = pq.top(); // 取出频率次小的节点
        pq.pop();
        TreeNode* parent = new TreeNode('$', left->freq + right->freq); // 新建一个父节点
        parent->left = left; // 将左子节点挂到父节点下面
        parent->right = right; // 将右子节点挂到父节点下面
        pq.push(parent); // 将新建的父节点加入到队列中
    }
    return pq.top(); // 队列中最后剩下的节点即为根节点
}

// 递归打印哈夫曼树的编码
void printHuffmanCode(TreeNode* root, string code) {
    if (!root) return; // 递归结束条件
    if (root->data != '$') { // 如果是叶子节点，输出对应字符和编码
        cout << root->data << " " << code << endl;
    }
    printHuffmanCode(root->left, code + "0"); // 递归处理左子树
    printHuffmanCode(root->right, code + "1"); // 递归处理右子树
}

int main() {
    vector<char> chars = {'a', 'b', 'c', 'd', 'e', 'f'};
    vector<int> freqs = {5, 9, 12, 13, 16, 45};
    TreeNode* root = buildHuffmanTree(chars, freqs);
    printHuffmanCode(root, "");
    return 0;
}

输出结果：

f 0
c 100
d 101
a 1100
b 1101
e 111

以上代码中，`buildHuffmanTree` 函数用于构建哈夫曼树，它使用了优先队列（堆）来维护频率最小的两个节点，不断合并成为新的节点，直到最后形成一棵哈夫曼树。`printHuffmanCode` 函数用于递归打印哈夫曼树的编码，其中传入的 `code` 参数表示当前节点的编码。

哈夫曼树与哈夫曼编码C++

哈夫曼树是一种带权路径长度最短的树，常用于数据压缩中的编码和解码。哈夫曼编码是一种前缀编码，即任何一个字符的编码都不是另一个字符编码的前缀。下面是C++实现哈夫曼树和哈夫曼编码的示例代码：

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

// 哈夫曼树结点类
class HuffmanNode {
public:
    char ch; // 字符
    int freq; // 频率
    HuffmanNode* left; // 左子树
    HuffmanNode* right; // 右子树
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
    ~HuffmanNode() {
        delete left;
        delete right;
    }
};

// 哈夫曼编码类
class HuffmanCoding {
public:
    // 构造函数
    HuffmanCoding(string s) : str(s) {
        for (char c : s) {
            freq[c]++;
        }
        buildHuffmanTree();
        buildHuffmanTable();
    }
    // 编码函数
    string encode() {
        string res = "";
        for (char c : str) {
            res += table[c];
        }
        return res;
    }
    // 解码函数
    string decode(string code) {
        string res = "";
        HuffmanNode* cur = root;
        for (char c : code) {
            if (c == '0') {
                cur = cur->left;
            } else {
                cur = cur->right;
            }
            if (cur->left == nullptr && cur->right == nullptr) {
                res += cur->ch;
                cur = root;
            }
        }
        return res;
    }
private:
    string str; // 待编码的字符串
    unordered_map<char, int> freq; // 字符频率
    unordered_map<char, string> table; // 哈夫曼编码表
    HuffmanNode* root; // 哈夫曼树根节点
    // 建立哈夫曼树
    void buildHuffmanTree() {
        priority_queue<HuffmanNode*, vector<HuffmanNode*>, [](HuffmanNode* a, HuffmanNode* b) { return a->freq > b->freq; }> pq;
        for (auto p : freq) {
            pq.push(new HuffmanNode(p.first, p.second));
        }
        while (pq.size() > 1) {
            HuffmanNode* left = pq.top(); pq.pop();
            HuffmanNode* right = pq.top(); pq.pop();
            HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
            parent->left = left;
            parent->right = right;
            pq.push(parent);
        }
        root = pq.top();
    }
    // 建立哈夫曼编码表
    void buildHuffmanTable() {
        dfs(root, "");
    }
    void dfs(HuffmanNode* node, string code) {
        if (node->left == nullptr && node->right == nullptr) {
            table[node->ch] = code;
            return;
        }
        dfs(node->left, code + "0");
        dfs(node->right, code + "1");
    }
};

// 测试
int main() {
    string s = "hello world";
    HuffmanCoding hc(s);
    string code = hc.encode();
    cout << "编码结果：" << code << endl;
    string decode = hc.decode(code);
    cout << "解码结果：" << decode << endl;
    return 0;
}