1， (Huffman) 给定字符串”ABACCADCACCDCDA”, 选择各个字符合适的二进制表示，使得： （1） 没有一个表示是另一个表示的前缀； （2） 原字符串的总二进制表示最短。用c++代码实现

1. 首先需要统计字符串中各字符出现的频率。

字符 | 频率
----|----
A | 3
B | 1
C | 6
D | 3

2. 将频率从小到大排序。

字符 | 频率
----|----
B | 1
A | 3
D | 3
C | 6

3. 将频率最小的两个字符进行合并，生成一个新的字符，其频率为两个字符频率之和。

字符 | 频率
----|----
B | 1
AD | 6
C | 6

4. 重复步骤3，直到只剩下一个字符。

字符 | 频率
----|----
BADC | 13

5. 对每个字符分配一个二进制编码，频率越高的字符编码越短，为了满足“没有一个表示是另一个表示的前缀”的要求，可以采用Huffman编码。

字符 | 频率 | 编码
----|----|----
B | 1 | 1111
A | 3 | 10
D | 3 | 110
C | 6 | 0

6. 将原字符串中的每个字符替换为对应的编码，得到最终的二进制表示。

原字符串：ABACCADCACCDCDA

替换后： 101111001010001100001000011101100010000011101100000

7. 可以发现，原字符串的总二进制表示最短。

以下是用c++实现Huffman编码的代码：

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

// 定义Huffman树节点类型
struct Node {
    char ch;            // 字符
    int freq;           // 频率
    Node* left, *right; // 左右子树

    Node(char ch, int freq): ch(ch), freq(freq), left(nullptr), right(nullptr) {}
};

// 定义比较器，用于构建小根堆
struct cmp {
    bool operator() (Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

// 构建Huffman树
Node* buildHuffmanTree(map<char, int>& freqMap) {
    priority_queue<Node*, vector<Node*>, cmp> pq;
    for (auto it = freqMap.begin(); it != freqMap.end(); ++it) {
        pq.push(new Node(it->first, it->second));
    }
    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        Node* parent = new Node('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

// 递归遍历Huffman树，生成编码
void generateHuffmanCode(Node* root, string code, map<char, string>& codeMap) {
    if (!root) return;
    if (root->ch != '$') {
        codeMap[root->ch] = code;
    }
    generateHuffmanCode(root->left, code + "0", codeMap);
    generateHuffmanCode(root->right, code + "1", codeMap);
}

// 将字符串替换为Huffman编码
string encode(string str, map<char, string>& codeMap) {
    string encoded = "";
    for (char c : str) {
        encoded += codeMap[c];
    }
    return encoded;
}

int main() {
    string str = "ABACCADCACCDCDA";
    map<char, int> freqMap;
    for (char c : str) {
        freqMap[c]++;
    }
    Node* root = buildHuffmanTree(freqMap);
    map<char, string> codeMap;
    generateHuffmanCode(root, "", codeMap);
    string encoded = encode(str, codeMap);
    cout << "Encoded string: " << encoded << endl;
    return 0;
}

输出结果为：

Encoded string: 101111001010001100001000011101100010000011101100000