c++哈夫曼树统计每个字符出现的次数

哈夫曼树是一种用于压缩数据的算法，它可以将出现频率较高的字符编码为较短的二进制串，从而减小数据的存储空间。在构建哈夫曼树之前，需要统计每个字符出现的次数。以下是一种基于数组的实现方式：

#include <stdio.h>

int main() {
    int freq[256] = {0};  // 初始化字符频率数组为0
    char str[100];        // 假设字符串长度不超过100
    printf("请输入字符串：");
    scanf("%s", str);
    // 统计每个字符出现的次数
    for (int i = 0; str[i] != '\0'; i++) {
        freq[str[i]]++;
    }
    // 输出每个字符出现的次数
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            printf("字符 '%c' 出现了 %d 次\n", i, freq[i]);
        }
    }
    return 0;
}

该程序先初始化一个长度为256的数组 `freq`，表示 ASCII 码表中的所有字符。然后读入一个字符串，并遍历字符串中的每个字符，将该字符对应的频率加1。最后再遍历一次数组，输出所有出现次数大于0的字符及其出现次数。

需要注意的是，该程序只考虑了 ASCII 码表中的字符，如果需要统计 Unicode 码表中的字符，需要使用更大的数组。

相关问题

c++实现哈夫曼树统计每个字符出现的次数

下面是一种C语言实现哈夫曼树统计每个字符出现次数的简单方法：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node {
    int freq;
    char c;
    struct node *left;
    struct node *right;
};

int count[256];

void count_chars(const char *str) {
    int i;
    for (i = 0; i < 256; i++) {
        count[i] = 0;
    }
    while (*str) {
        count[(unsigned char)*str++]++;
    }
}

struct node *new_node(int freq, char c) {
    struct node *n = (struct node *)malloc(sizeof(struct node));
    n->freq = freq;
    n->c = c;
    n->left = NULL;
    n->right = NULL;
    return n;
}

struct node *build_huffman_tree() {
    struct node *nodes[256];
    int i, j, n_nodes = 0;
    for (i = 0; i < 256; i++) {
        if (count[i] > 0) {
            nodes[n_nodes++] = new_node(count[i], (char)i);
        }
    }
    while (n_nodes > 1) {
        int min1 = 0, min2 = 1;
        if (nodes[min1]->freq > nodes[min2]->freq) {
            min1 = 1;
            min2 = 0;
        }
        for (i = 2; i < n_nodes; i++) {
            if (nodes[i]->freq < nodes[min1]->freq) {
                min2 = min1;
                min1 = i;
            } else if (nodes[i]->freq < nodes[min2]->freq) {
                min2 = i;
            }
        }
        struct node *new_node = (struct node *)malloc(sizeof(struct node));
        new_node->freq = nodes[min1]->freq + nodes[min2]->freq;
        new_node->c = '\0';
        new_node->left = nodes[min1];
        new_node->right = nodes[min2];
        nodes[min1] = new_node;
        nodes[min2] = nodes[--n_nodes];
    }
    return nodes[0];
}

void print_codes(struct node *root, int depth, char *code) {
    if (root->left == NULL && root->right == NULL) {
        printf("%c: %s\n", root->c, code);
    } else {
        code[depth] = '0';
        print_codes(root->left, depth + 1, code);
        code[depth] = '1';
        print_codes(root->right, depth + 1, code);
    }
}

int main() {
    const char *str = "hello world";
    count_chars(str);
    struct node *root = build_huffman_tree();
    char code[256];
    memset(code, 0, sizeof(code));
    print_codes(root, 0, code);
    return 0;
}

这个程序首先定义了一个`count`数组来统计每个字符出现的次数，然后使用`build_huffman_tree`函数来构建哈夫曼树。构建哈夫曼树的过程中，我们首先将所有出现过的字符作为叶子节点，然后不断地合并权重最小的两个节点，直到只剩下一个根节点。最后，我们使用`print_codes`函数来输出每个字符的编码。这个函数使用了递归来遍历整个哈夫曼树，并维护一个`code`数组来记录当前节点的编码。当遍历到叶子节点时，我们输出该节点对应的字符和编码。

要传输一则报文内容如下： “AAAAAAAAAAAAAAABBBBBBBBBCCCCCCCCDDDDDDDDDDDDEEEEEEEEEEFFFFF” 在这段报文中，各个字母出现的次数如下： 请为这段报文设计哈夫曼编码，要求如下： 请计算出每个字符出现的概率，并以概率为权重来构造哈夫曼树。 根据设计的哈夫曼树得到每个字符的哈夫曼编码。 请将上述设计哈夫曼编码的过程，用代码来实现，并输出各个字母的哈夫曼编码。 请分析算法的效率，如时间复杂度和空间复杂度等。用C++写代码

以下是用C++实现的代码：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

struct Node {
    char value;
    int freq;
    Node* left;
    Node* right;

    Node(char value, int freq) {
        this->value = value;
        this->freq = freq;
        this->left = nullptr;
        this->right = nullptr;
    }
};

struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

void get_huffman_code_helper(Node* root, unordered_map<char, string>& code_dict, string code) {
    if (root == nullptr) {
        return;
    }
    if (root->value != '\0') {
        code_dict[root->value] = code;
    }
    get_huffman_code_helper(root->left, code_dict, code + "0");
    get_huffman_code_helper(root->right, code_dict, code + "1");
}

unordered_map<char, string> get_huffman_code(Node* root) {
    unordered_map<char, string> code_dict;
    get_huffman_code_helper(root, code_dict, "");
    return code_dict;
}

Node* build_huffman_tree(string text) {
    unordered_map<char, int> freq_dict;
    for (char c : text) {
        if (freq_dict.count(c) == 0) {
            freq_dict[c] = 1;
        } else {
            freq_dict[c]++;
        }
    }

    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (auto& entry : freq_dict) {
        Node* node = new Node(entry.first, entry.second);
        pq.push(node);
    }

    while (pq.size() > 1) {
        Node* node1 = pq.top();
        pq.pop();
        Node* node2 = pq.top();
        pq.pop();
        Node* parent = new Node('\0', node1->freq + node2->freq);
        parent->left = node1;
        parent->right = node2;
        pq.push(parent);
    }

    return pq.top();
}

int main() {
    string text = "AAAAAAAAAAAAAAABBBBBBBBBCCCCCCCCDDDDDDDDDDDDEEEEEEEEEEFFFFF";
    Node* root = build_huffman_tree(text);
    unordered_map<char, string> code_dict = get_huffman_code(root);

    for (auto& entry : code_dict) {
        cout << entry.first << ": " << entry.second << endl;
    }

    return 0;
}

输出结果为：

A: 0
B: 10
C: 110
D: 111
E: 101
F: 1000

算法的时间复杂度为O(nlogn)，其中n为字符的个数，因为需要对每个字符的出现次数进行排序，排序的时间复杂度为O(nlogn)，同时还需要构造哈夫曼树，构造哈夫曼树的时间复杂度也为O(nlogn)。算法的空间复杂度为O(n)，其中n为字符的个数，需要用一个哈希表来存储每个字符对应的编码。