AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【C++数据结构——树】哈夫曼树（头歌实践教学平台习题） 【合集】

2025-01-08 347
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构——树】哈夫曼树（头歌实践教学平台习题）【合集】目录任务描述相关知识测试说明我的通关代码：测试结果：任务描述本关任务：编写一个程序构建哈夫曼树和生成哈夫曼编码。相关知识为了完成本关任务，你需要掌握：1.如何构建哈夫曼树，2.如何生成哈夫曼编码。测试说明平台会对你编写的代码进行测试：测试输入：1192677541518462450242195190181174157138124123(用户分别输入所列单词的频度）预

 

目录😋

任务描述

相关知识

如何构建哈夫曼树

  1. 定义节点结构体

  2. 实现比较函数（用于优先队列）

  3. 构建哈夫曼树

生成哈夫曼编码

整体结构说明：

各函数详细解释：

测试说明

通关代码：

测试结果：

任务描述

本关任务：编写一个程序构建哈夫曼树和生成哈夫曼编码。

相关知识

为了完成本关任务，你需要掌握：

  1. 如何构建哈夫曼树，
  2. 如何生成哈夫曼编码。

如何构建哈夫曼树

  1. 定义节点结构体

       首先，需要定义哈夫曼树节点的结构体。一个哈夫曼节点包含以下几个部分：

  • 左子节点指针。
  • 右子节点指针。
  • 节点的权重（通常是字符出现的频率）。
  • 可能还包含节点表示的数据（例如字符）。
struct HuffmanNode {
    int weight;
    char data;
    HuffmanNode* left;
    HuffmanNode* right;
    HuffmanNode(int w, char d) : weight(w), data(d), left(nullptr), right(nullptr) {}
};
image.gif

  2. 实现比较函数（用于优先队列）

       为了能够在构建哈夫曼树时方便地找到权重最小的节点，通常使用优先队列（priority_queue）。需要定义一个比较函数，使得优先队列可以根据节点权重进行排序。

struct CompareNodes {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};
image.gif

  3. 构建哈夫曼树

       构建哈夫曼树的主要步骤如下：

  1. 将所有节点放入优先队列。
  2. 每次从优先队列中取出两个权重最小的节点，创建一个新的父节点，其权重为这两个节点权重之和，并将这两个节点作为新父节点的左右子节点，然后将新父节点放入优先队列。
  3. 重复步骤 2，直到优先队列中只剩下一个节点，这个节点就是哈夫曼树的根节点。

以下是构建哈夫曼树的函数：

#include <iostream>
#include <queue>
#include <vector>
// 1. 定义节点结构体
// 哈夫曼树节点的结构体定义。一个哈夫曼节点包含以下几个部分：
// - 左子节点指针，用于指向该节点的左子树节点。
// - 右子节点指针，用于指向该节点的右子树节点。
// - 节点的权重（通常是字符出现的频率），代表该节点在构建树过程中的重要程度等相关属性。
// - 可能还包含节点表示的数据（例如字符），在某些应用场景下用于标识该节点对应的具体内容。
struct HuffmanNode {
    int weight;
    char data;
    HuffmanNode* left;
    HuffmanNode* right;
    // 构造函数，用于方便地初始化哈夫曼节点的权重和数据成员，同时将左右子节点指针初始化为nullptr。
    HuffmanNode(int w, char d) : weight(w), data(d), left(nullptr), right(nullptr) {}
};
// 2. 实现比较函数（用于优先队列）
// 为了能够在构建哈夫曼树时方便地找到权重最小的节点，通常使用优先队列（priority_queue）。
// 需要定义一个比较函数，使得优先队列可以根据节点权重进行排序。
// 这里定义的比较函数是一个函数对象（仿函数），重载了括号运算符，使得它可以像函数一样被调用。
// 它的作用是比较两个哈夫曼节点指针所指向节点的权重大小，返回 true 表示第一个节点的权重大于第二个节点的权重，
// 这样在优先队列中就会按照权重从小到大的顺序来排列节点（因为优先队列默认是大顶堆，通过这样的比较函数实现小顶堆效果）。
struct CompareNodes {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};
// 3. 构建哈夫曼树
// 构建哈夫曼树的主要步骤如下：
// 该函数接受一个包含所有初始节点（通常是代表字符及其频率的节点）的向量作为参数，返回构建好的哈夫曼树的根节点指针。
HuffmanNode* buildHuffmanTree(const std::vector<HuffmanNode*>& nodes) {
    // 创建一个优先队列，用于存放哈夫曼节点指针，使用自定义的比较函数 CompareNodes 来确定节点的优先级顺序，即按照权重从小到大排列。
    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, CompareNodes> pq;
    // 将所有节点放入优先队列
    for (HuffmanNode* node : nodes) {
        pq.push(node);
    }
    // 循环执行以下操作，直到优先队列中只剩下一个节点，这个节点就是哈夫曼树的根节点。
    while (pq.size() > 1) {
        // 每次从优先队列中取出两个权重最小的节点
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();
        // 创建一个新的父节点，其权重为这两个节点权重之和
        HuffmanNode* parent = new HuffmanNode(left->weight + right->weight, '\0');
        // 将取出的两个节点作为新父节点的左右子节点
        parent->left = left;
        parent->right = right;
        // 将新父节点放入优先队列，以便后续继续参与构建树的合并操作。
        pq.push(parent);
    }
    // 最后返回构建好的哈夫曼树的根节点指针，如果输入的节点向量为空，则返回 nullptr（这里暂未做额外的错误处理，可根据实际需求完善）。
    return pq.empty()? nullptr : pq.top();
}
// 辅助函数，用于释放哈夫曼树的内存空间（采用后序遍历的方式递归释放节点）。
// 这是一个很重要的函数，避免内存泄漏，因为在构建哈夫曼树过程中使用了动态分配内存（new 操作符）来创建节点。
void freeHuffmanTree(HuffmanNode* root) {
    if (root == nullptr) {
        return;
    }
    freeHuffmanTree(root->left);
    freeHuffmanTree(root->right);
    delete root;
}
// 以下是一个简单的测试示例，用于展示如何使用构建哈夫曼树的函数。
int main() {
    // 模拟创建一些初始节点，这里简单地手动构造了几个节点，实际应用中可能根据字符频率统计等方式来生成这些节点。
    std::vector<HuffmanNode*> nodes;
    nodes.push_back(new HuffmanNode(5, 'a'));
    nodes.push_back(new HuffmanNode(9, 'b'));
    nodes.push_back(new HuffmanNode(12, 'c'));
    nodes.push_back(new HuffmanNode(13, 'd'));
    nodes.push_back(new HuffmanNode(16, 'e'));
    // 调用构建哈夫曼树的函数，得到哈夫曼树的根节点指针。
    HuffmanNode* root = buildHuffmanTree(nodes);
    // 这里可以进行后续对哈夫曼树的操作，比如编码、解码等，暂时省略这些操作的具体实现代码。
    // 释放哈夫曼树的内存空间，避免内存泄漏。
    freeHuffmanTree(root);
    return 0;
}
image.gif

节点结构体部分:

  HuffmanNode 结构体清晰地定义了哈夫曼树节点的构成要素。其中 weight 成员变量用于记录节点的权重，在文本压缩等应用场景下通常对应字符出现的频率，权重越小，表示该字符相对出现的次数越少；data 成员变量用于存放节点所代表的数据内容，比如在基于字符构建哈夫曼树时，这里可以存放具体的字符；left 和 right 指针分别指向该节点的左子节点和右子节点，用于构建树的层次结构，初始化为 nullptr 表示新建节点时默认没有子节点。

比较函数部分：

  CompareNodes 结构体通过重载 operator() 函数实现了一个比较函数对象（仿函数）。在 std::priority_queue（优先队列）的使用中，这个比较函数决定了队列中元素的排列顺序。因为默认情况下，std::priority_queue 是大顶堆（即队头元素是最大的元素），但我们希望按照节点权重从小到大来管理节点，所以通过这个比较函数返回 a->weight > b->weight 的结果，使得优先队列实际上变成了小顶堆，这样每次调用 pq.top() 就能获取到权重最小的节点。

 

构建哈夫曼树函数部分:

  • 节点入队：首先创建了一个 std::priority_queue 类型的优先队列 pq，并将输入的所有节点指针通过循环依次放入队列中。这些输入节点可以看作是最初的、独立的叶子节点，代表了构建哈夫曼树的基础元素，每个节点都有其特定的权重和可能的数据标识。
  • 循环构建树：在 while 循环中，只要优先队列中节点数量大于 1，就不断进行以下操作。每次先取出两个权重最小的节点（通过两次调用 pq.top() 并接着 pq.pop() 实现），这两个节点将作为新生成节点的左右子节点。然后创建一个新的父节点，其权重设置为取出的两个子节点权重之和，并且将刚才取出的两个节点分别赋值给新父节点的左右子节点指针。最后把这个新创建的父节点再放入优先队列中，参与后续的合并操作。这样不断合并节点，树的层次结构逐渐形成，直到队列中只剩下一个节点，这个节点就是整个哈夫曼树的根节点，代表了所有节点合并后的最终结果，通过它可以访问到整棵哈夫曼树的各个部分。
  • 内存释放：由于在构建哈夫曼树过程中使用了 new 操作符动态分配内存来创建节点，所以需要编写 freeHuffmanTree 函数来释放这些内存，避免内存泄漏。该函数采用后序遍历的方式，先递归释放左子树节点内存，再释放右子树节点内存，最后释放根节点内存，确保整个哈夫曼树所占用的内存都能正确回收。

测试示例部分:

       在 main 函数中，模拟创建了一个包含几个节点的向量，这些节点的权重和对应的数据（字符）是手动设定的，仅用于简单展示构建哈夫曼树的流程。实际应用中，这些节点通常是根据文本中字符出现的频率统计等操作来生成的。然后调用 buildHuffmanTree 函数构建哈夫曼树，得到根节点指针后，虽然这里省略了后续对哈夫曼树进行编码、解码等实际操作的代码，但展示了基本的使用流程，最后调用 freeHuffmanTree 函数来释放哈夫曼树所占用的内存空间，保证程序的内存管理正确

生成哈夫曼编码

       构建哈夫曼树后，可以通过遍历哈夫曼树来生成每个字符的哈夫曼编码。通常使用递归函数来实现。

以下是一个简单的生成哈夫曼编码的函数示例：

void generateHuffmanCodes(HuffmanNode* root, string code, unordered_map<char, string>& huffmanCodes) {
    if (root == nullptr) return;
    if (root->data!= '\0') {
        huffmanCodes[root->data] = code;
    }
    generateHuffmanCodes(root->left, code + "0", huffmanCodes);
    generateHuffmanCodes(root->right, code + "1", huffmanCodes);
}
image.gif

以下是一个使用上述函数构建哈夫曼树和生成哈夫曼编码的完整示例：

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cstring>
using namespace std;
// 1. 定义哈夫曼树节点结构体
// 该结构体用于表示哈夫曼树中的节点，包含以下几个重要成员：
// - weight：节点的权重，通常代表字符在文本中出现的频率，权重值越大，表示对应字符出现的相对次数越多。
// - data：节点所代表的数据，这里一般是字符本身，如果是其他应用场景也可以是其他类型的数据标识。
// - left 和 right：分别指向该节点的左子节点和右子节点的指针，用于构建哈夫曼树的树形结构，初始化为 nullptr 表示新建节点时无子节点。
struct HuffmanNode {
    int weight;
    char data;
    HuffmanNode* left;
    HuffmanNode* right;
    // 构造函数，用于方便地初始化节点的权重和数据成员，同时将左右子节点指针初始化为 nullptr。
    HuffmanNode(int w, char d) : weight(w), data(d), left(nullptr), right(nullptr) {}
};
// 2. 定义比较函数结构体（用于优先队列）
// 这个结构体实现了一个函数对象（仿函数），通过重载括号运算符来定义比较规则。
// 在优先队列（priority_queue）中使用，目的是按照节点的权重从小到大对节点进行排序。
// 这样优先队列的顶部元素始终是权重最小的节点，方便在构建哈夫曼树时取出权重最小的节点进行合并操作。
struct CompareNodes {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};
// 3. 构建哈夫曼树的函数
// 该函数接受一个包含所有初始节点（通常是代表字符及其频率的节点）的向量作为参数，返回构建好的哈夫曼树的根节点指针。
HuffmanNode* buildHuffmanTree(vector<HuffmanNode*>& nodes) {
    // 创建一个优先队列，用于存放哈夫曼节点指针，使用自定义的比较函数 CompareNodes 来确定节点的优先级顺序，即按照权重从小到大排列。
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareNodes> pq;
    // 将所有节点放入优先队列，如果输入的节点向量为空，这里可以添加错误处理逻辑，暂时简单打印提示信息并返回 nullptr。
    if (nodes.empty()) {
        cout << "输入的节点向量为空，无法构建哈夫曼树！" << endl;
        return nullptr;
    }
    for (HuffmanNode* node : nodes) {
        pq.push(node);
    }
    // 循环执行以下操作，直到优先队列中只剩下一个节点，这个节点就是哈夫曼树的根节点。
    while (pq.size() > 1) {
        // 每次从优先队列中取出两个权重最小的节点
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();
        // 创建一个新的父节点，其权重为这两个节点权重之和
        HuffmanNode* parent = new HuffmanNode(left->weight + right->weight, '\0');
        // 将取出的两个节点作为新父节点的左右子节点
        parent->left = left;
        parent->right = right;
        // 将新父节点放入优先队列，以便后续继续参与构建树的合并操作。
        pq.push(parent);
    }
    // 返回构建好的哈夫曼树的根节点指针，如果输入的节点向量为空，这里返回的是之前已经处理的 nullptr。
    return pq.top();
}
// 4. 生成哈夫曼编码的函数
// 该函数通过递归遍历哈夫曼树来生成每个字符对应的哈夫曼编码，将其存储在一个无序映射（unordered_map）中。
// 参数说明：
// - root：哈夫曼树的根节点指针，从根节点开始递归遍历整棵树。
// - code：当前路径的编码字符串，随着递归遍历不断累加，向左子树走添加 '0'，向右子树走添加 '1'。
// - huffmanCodes：无序映射，用于存储字符及其对应的哈夫曼编码，键为字符，值为编码字符串。
void generateHuffmanCodes(HuffmanNode* root, string code, unordered_map<char, string>& huffmanCodes) {
    // 如果当前节点为空，直接返回，这是递归的边界条件，用于结束递归调用。
    if (root == nullptr) return;
    // 如果当前节点的数据不为空字符（'\0'），说明该节点代表一个实际的字符（非中间合并节点），
    // 将当前的编码字符串赋值给该字符对应的映射项，即记录下该字符的哈夫曼编码。
    if (root->data!= '\0') {
        huffmanCodes[root->data] = code;
    }
    // 递归遍历左子树，将当前编码字符串添加 '0' 后继续递归，用于生成左子树中各字符的哈夫曼编码。
    generateHuffmanCodes(root->left, code + "0", huffmanCodes);
    // 递归遍历右子树，将当前编码字符串添加 '1' 后继续递归，用于生成右子树中各字符的哈夫曼编码。
    generateHuffmanCodes(root->right, code + "1", huffmanCodes);
}
// 5. 辅助函数，用于释放哈夫曼树的内存空间（采用后序遍历的方式递归释放节点）。
// 这是一个很重要的函数，避免内存泄漏，因为在构建哈夫曼树过程中使用了动态分配内存（new 操作符）来创建节点。
void freeHuffmanTree(HuffmanNode* root) {
    if (root == nullptr) {
        return;
    }
    freeHuffmanTree(root->left);
    freeHuffmanTree(root->right);
    delete root;
}
// 6. 主函数，用于测试哈夫曼树构建及编码生成的功能。
int main() {
    // 示例：假设字符和频率
    vector<HuffmanNode*> nodes;
    nodes.push_back(new HuffmanNode(5, 'a'));
    nodes.push_back(new HuffmanNode(9, 'b'));
    nodes.push_back(new HuffmanNode(12, 'c'));
    nodes.push_back(new HuffmanNode(13, 'd'));
    nodes.push_back(new HuffmanNode(16, 'e'));
    // 构建哈夫曼树，获取根节点指针，如果构建失败（返回 nullptr），则直接结束程序。
    HuffmanNode* root = buildHuffmanTree(nodes);
    if (root == nullptr) {
        return 0;
    }
    // 用于存储生成的哈夫曼编码，键为字符，值为对应的哈夫曼编码字符串。
    unordered_map<char, string> huffmanCodes;
    // 调用函数生成哈夫曼编码，从根节点开始，初始编码字符串为空。
    generateHuffmanCodes(root, "", huffmanCodes);
    // 输出哈夫曼编码
    for (auto& code : huffmanCodes) {
        cout << code.first << " : " << code.second << endl;
    }
    // 释放哈夫曼树占用的内存空间，避免内存泄漏，调用辅助函数进行后序遍历释放。
    freeHuffmanTree(root);
    return 0;
}
image.gif

整体结构说明：

       整个代码主要实现了构建哈夫曼树以及基于构建好的哈夫曼树生成相应字符的哈夫曼编码的功能。代码分为几个主要部分，包括定义哈夫曼树节点结构体、实现用于优先队列的比较函数、构建哈夫曼树的函数、生成哈夫曼编码的函数以及主函数进行测试和内存释放操作等。

 

各函数详细解释：

  1. buildHuffmanTree 函数：
  • 输入节点入队：首先创建了一个 std::priority_queue 类型的优先队列 pq，并将输入的所有节点指针通过循环依次放入队列中。添加了对输入节点向量为空情况的简单错误处理，如果为空则打印提示信息并返回 nullptr，避免后续出现错误操作。
  • 循环构建树：在 while 循环中，只要优先队列中节点数量大于 1，就不断进行以下操作。每次先取出两个权重最小的节点（通过两次调用 pq.top() 并接着 pq.pop() 实现），这两个节点将作为新生成节点的左右子节点。然后创建一个新的父节点，其权重设置为取出的两个子节点权重之和，并且将刚才取出的两个节点分别赋值给新父节点的左右子节点指针。最后把这个新创建的父节点再放入优先队列中，参与后续的合并操作。这样不断合并节点，树的层次结构逐渐形成，直到队列中只剩下一个节点，这个节点就是整个哈夫曼树的根节点，代表了所有节点合并后的最终结果，通过它可以访问到整棵哈夫曼树的各个部分。
  • 返回根节点：最后返回构建好的哈夫曼树的根节点指针，如果输入的节点向量为空，这里返回的是之前已经处理的 nullptr。
  1. generateHuffmanCodes 函数：
  • 递归边界处理：首先判断当前传入的节点指针是否为 nullptr，如果是则直接返回，这是递归调用的边界条件，用于终止递归过程，避免无限递归。
  • 记录字符编码：当节点的数据成员不为空字符（'\0'）时，说明该节点代表一个实际的字符（非中间合并节点），此时将当前已经生成的编码字符串（通过递归过程中不断累加 0 或 1 形成）赋值给该字符对应的映射项，也就是记录下这个字符的哈夫曼编码到 huffmanCodes 无序映射中。
  • 递归遍历子树：接着分别递归遍历当前节点的左子树和右子树，在遍历左子树时，将当前编码字符串添加 0 后继续递归调用该函数；遍历右子树时，将当前编码字符串添加 1 后继续递归调用。通过这样的递归方式，能够遍历整棵哈夫曼树，为每个叶子节点（代表字符的节点）生成对应的哈夫曼编码。
  1. freeHuffmanTree 函数：
  • 这是一个用于释放哈夫曼树内存空间的辅助函数，采用后序遍历的方式进行递归释放。先判断根节点指针是否为 nullptr，如果是则直接返回，不需要进行释放操作。然后递归调用自身先释放左子树的内存，再释放右子树的内存，最后释放根节点的内存（通过 delete 操作符），确保整个哈夫曼树所占用的内存都能正确回收，避免内存泄漏问题，因为在构建哈夫曼树过程中使用了动态分配内存（new 操作符）来创建节点。
  1. main 函数：
  • 构建测试数据：在主函数中，首先模拟创建了一个包含几个节点的向量，这些节点的权重和对应的数据（字符）是手动设定的，仅用于简单展示构建哈夫曼树和生成编码的流程。实际应用中，这些节点通常是根据文本中字符出现的频率统计等操作来生成的。
  • 构建哈夫曼树并处理错误：调用 buildHuffmanTree 函数构建哈夫曼树，获取根节点指针后，对返回的指针进行判断，如果为 nullptr，说明构建树过程出现问题（比如输入节点为空等情况），则直接结束程序。
  • 生成并输出编码：创建一个 unordered_map 用于存储生成的哈夫曼编码，然后调用 generateHuffmanCodes 函数从根节点开始，初始编码字符串为空的情况下生成哈夫曼编码，并通过循环遍历 huffmanCodes 无序映射来输出每个字符及其对应的哈夫曼编码。
  • 释放内存：最后调用 freeHuffmanTree 函数来释放哈夫曼树所占用的内存空间，保证程序的内存管理正确，避免出现内存泄漏等问题。

测试说明

平台会对你编写的代码进行测试：

测试输入：(用户分别输入所列单词的频度）

1192 677 541 518 462 450 242 195 190 181 174 157 138 124 123
image.gif

预期输出：

哈夫曼编码:
The:01
of:101
a:001
to:000
and:1110
in:1101
that:11110
he:11001
is:11000
at:10011
on:10010
for:10001
His:10000
are:111111
be:111110
image.gif

开始你的任务吧，祝你成功！

通关代码：

#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
struct HuffmanNode{
    int weight;
    string word;
    HuffmanNode *left,*right;
    HuffmanNode(int weight,string word):weight(weight),word(word),left(nullptr),right(nullptr){}
};
struct Compare{
    bool operator()(HuffmanNode *l,HuffmanNode *r){
        if(l->weight == r->weight){
            return l->word < r->word;
        }
        return l->weight > r->weight;
    }
};
void generateHuffmanCode(HuffmanNode *root,string str,unordered_map<string,string> & huffmanCodes){
    if(!root)
    return;
    if(!root->word.empty()){
        huffmanCodes[root->word] = str;
    }
    generateHuffmanCode(root->left,str + "0",huffmanCodes);
    generateHuffmanCode(root->right,str + "1",huffmanCodes);
}
double calculateAverageSearchLength(HuffmanNode *root,int depth = 0){
    if(!root)
    return 0;
    if(!root->word.empty())
    return depth * root->weight;
    return calculateAverageSearchLength(root->left,depth + 1) + calculateAverageSearchLength(root ->right,depth + 1);
}
int main(){
    vector<string>words = {"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"};
    vector<int> weights(words.size());
    priority_queue<HuffmanNode *,vector<HuffmanNode *>,Compare> minHeap;
    for(int i = 0;i < words.size();++i){
        cin >> weights[i];
        minHeap.push(new HuffmanNode(weights[i],words[i]));
    }
    while (minHeap.size() > 1){
        HuffmanNode *left = minHeap.top();
        minHeap.pop();
        HuffmanNode *right =minHeap.top();
        minHeap.pop();
        HuffmanNode *top = new
HuffmanNode(left->weight + right -> weight,"");
        top->left =left;
        top->right = right;
        minHeap.push(top);
    }
    HuffmanNode *root = minHeap.top();
    unordered_map<string,string> huffmanCodes;
    generateHuffmanCode(root,"",huffmanCodes);
    cout <<"哈夫曼编码:\n";
    for(const string &word : words){
        cout <<word <<":"<<huffmanCodes[word]<<endl;
    }
    while(!minHeap.empty()){
        delete minHeap.top();
        minHeap.pop();
    }
    delete root;
    return 0;
}

image.gif

测试结果：

image.gif

image.gif

文章标签：
C++
存储
关键词：
数据结构实践
C++实践
C++树实践
数据结构树
C++实践教学习题
RossyYan
目录
相关文章
陌陌谣
|
6月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用，通过C++实现其构建与查询功能，显著提升多维数据处理效率。KD树作为一种二叉空间划分结构，适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法，基于KD树的方案检索效率提升2-3个数量级，但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
陌陌谣
181 17
RossyYan
|
10月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
500 77
RossyYan
|
10月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类（头歌实践教学平台习题）【合集】
声明一个简单的Computer类，含有数据成员芯片（cpu）、内存（ram）、光驱（cdrom）等等，以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制，用于保护类的数据不被外部随意修改。根据提示，在右侧编辑器补充代码，平台会对你编写的代码进行测试。成员可以在派生类（继承该类的子类）中访问。成员，在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务，你需要掌握。
RossyYan
220 19
平凡程序猿~
|
9月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象（下）
在上一篇博客中，我们学习了C++的基础类与对象概念，包括类的定义、对象的使用和构造函数的作用。在这一篇，我们将深入探讨C++类的一些重要特性，如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象，以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念，提升代码的健壮性、灵活性和可维护性。
平凡程序猿~
231 0
hahaha无
|
5月前
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果：注意：类模板中的成员函数若是放在类外定义时，需要加模板参数列表。return 0;
hahaha无
156 0
hahaha无
|
5月前
|
存储 编译器 程序员
c++的类（附含explicit关键字，友元，内部类）
本文介绍了C++中类的核心概念与用法，涵盖封装、继承、多态三大特性。重点讲解了类的定义（`class`与`struct`）、访问限定符（`private`、`public`、`protected`）、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数（构造函数、析构函数、拷贝构造、赋值重载）以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员（变量与函数）、友元（友元函数与友元类）的概念及其使用场景，并简要介绍了内部类的特性。
hahaha无
248 0
ephemerals__
|
7月前
|
编译器 C++ 容器
【c++11】c++11新特性（上）（列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式）
C++11为C++带来了革命性变化，引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式，initializer_list简化了容器多元素初始化；右值引用和移动语义优化了资源管理，减少拷贝开销；类新增移动构造和移动赋值函数提升性能；lambda表达式提供匿名函数对象，增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展，提升了开发效率与程序性能。
ephemerals__
283 12
蓝易云
|
8月前
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨，我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性，而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧，对于提升C++编程水平至关重要。
蓝易云
173 16
羑悻的小杀马特
|
9月前
|
编译器 C语言 C++
类和对象的简述（c++篇）
类和对象的简述（c++篇）
羑悻的小杀马特
226 28
预备女程序员a
|
8月前
|
编译器 C++
类和对象（中 ）C++
本文详细讲解了C++中的默认成员函数，包括构造函数、析构函数、拷贝构造函数、赋值运算符重载和取地址运算符重载等内容。重点分析了各函数的特点、使用场景及相互关系，如构造函数的主要任务是初始化对象，而非创建空间；析构函数用于清理资源；拷贝构造与赋值运算符的区别在于前者用于创建新对象，后者用于已存在的对象赋值。同时，文章还探讨了运算符重载的规则及其应用场景，并通过实例加深理解。最后强调，若类中存在资源管理，需显式定义拷贝构造和赋值运算符以避免浅拷贝问题。
预备女程序员a
121 1

热门文章

最新文章

  • 1
    Visual C++运行库、.NET Framework和DirectX运行库的作用及常见问题解决方案，涵盖MSVCP140.dll丢失、0xc000007b错误等典型故障的修复方法
  • 2
    给我介绍一些C++中引用的使用注意事项
  • 3
    （Python基础）新时代语言！一起学习Python吧！（一）：认识Python、Py解释器作用；编写第一个Python程序；Python中的基本数据结构
  • 4
    （Pandas）Python做数据处理必选框架之一！（一）：介绍Pandas中的两个数据结构；刨析Series：如何访问数据；数据去重、取众数、总和、标准差、方差、平均值等；判断缺失值、获取索引...
  • 5
    【C/C++】数据在内存中的存储（完整篇非常详细）
  • 6
    C++STL中set的使用策略(详解)
  • 7
    myeclipse开发安装C++
  • 8
    c++windows内核编程笔记day12 硬盘逻辑分区管理、文件管理、内存管理
  • 9
    C++第11周项目1——函数体验
  • 10
    C++第3周项目3——时间类
  • 1
    （Pandas）Python做数据处理必选框架之一！（一）：介绍Pandas中的两个数据结构；刨析Series：如何访问数据；数据去重、取众数、总和、标准差、方差、平均值等；判断缺失值、获取索引...
    350
  • 2
    （Python基础）新时代语言！一起学习Python吧！（一）：认识Python、Py解释器作用；编写第一个Python程序；Python中的基本数据结构
    389
  • 3
    Redis数据结构：别小看这5把“瑞士军刀”，用好了性能飙升！
    339
  • 4
    软考中级软件设计师专项-数据结构与算法上篇
    461
  • 5
    【Redis】常用数据结构之List篇：从常用命令到典型使用场景
    415
  • 6
    Redis基础命令与数据结构概览
    114
  • 7
    Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
    273
  • 8
    【Redis】 常用数据结构之String篇：从SET/GET到INCR的超全教程
    308
  • 9
    【📕分布式锁通关指南 12】源码剖析redisson如何利用Redis数据结构实现Semaphore和CountDownLatch
    252
  • 10
    Redis核心数据结构与分布式锁实现详解
    320

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • C++ 入门教程开发文档

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    oss云网关配置