使用字符串中的 2 个键填充地图。字符和频率 c++

Question

我是地图新手，所以有点不确定执行此操作的最佳方法。该任务与霍夫曼编码压缩有关。这是我所拥有的。

#include <map>
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

typedef map<char,int> huffmanMap;

void getFreq(string file, map<char, int> map) 
{ 
    map.clear();    
    for (string::iterator i = file.begin(); i != file.end(); ++i) {
        ++map[*i];   
    }
}

上面是我在网上找到的一种方法，但无法打印

int main()
{
    map<char, int> huffmanMap;
    string fileline;

    ifstream myfile;
    myfile.open("text.txt",ios::out); 

    while(!myfile.eof())  {
    getline(myfile, fileline); //get the line and put it in the fileline string
    }
    myfile.close();

我从文本文件中读取的任何内容以填充字符串文件行。

    for (int i=0; i<fileline.length(); i++) {
        char t = fileline[i];
        huffmanMap[i]? huffmanMap[i]++ : huffmanMap[i]=1;
    }

这是我尝试填充地图的第二种方法，字符值不正确，符号和笑脸。

    getFreq(fileline,huffmanMap);

    huffmanMap::iterator position;
    for (position = huffmanMap.begin(); position != huffmanMap.end(); position++)  {
        cout << "key: \"" << position->first << endl;
        cout << "value: " << position->second << endl;
    }

这就是我尝试打印地图的方法

    system("pause");
    return 0;
}

当我运行 getFreq 方法时，程序崩溃了。我没有收到任何错误。使用第二种方法时， char 值是无意义的。注意，我没有同时运行这两种方法，我只是将它们都包含在内以显示我所尝试的内容。

任何见解将不胜感激。谢谢。对初学者要宽容一点；）

Answer 1

您的代码到处都是，不是很连贯，因此很难理解流程。

以下是一些不足之处：

这是错误的： myfile.open("text.txt",ios::out); - 为什么要使用以下命令打开输入流out 标志？它应该简单地是：

string fileline;
ifstream myfile("text.txt"); 

while(getline(myfile, fileline))  {
   // now use fileline.
}

在 while 循环中，您想要做的是迭代内容并将其添加到您的地图中？所以现在代码看起来像：

string fileline;
ifstream myfile("text.txt"); 

while(getline(myfile, fileline))  {
   getFreq(fileline, huffmanMap);
}

下一步修复，这是错误的：你有一个 typedef 和一个同名的变量！

typedef map<char,int> huffmanMap;

map<char, int> huffmanMap;

使用合理的命名

typedef map<char,int> huffmanMap_Type;

huffmanMap_Type huffmanMap;

下一步修复，您的getFreq方法签名是错误的，您通过值（即复制）而不是引用传递地图，因此您在函数中的修改是复制品不是原件！

错误：void getFreq(string file, mapmap)

正确：void getFreq(string file, huffmanMap_Type& map)

下一步： 为什么在上面的方法中使用clear()？如果有多于一根线怎么办？肯定不需要这个吧？

现在就足够了，如果有更多问题，请清理您的代码并更新您的问题。

Answer 2

一项修复，一项改进。

修复是：在 getFreq 参考中创建第二个参数：

void getFreq(string file, map<char, int> & map); //notice `&`

改进是：只需写入

huffmanMap[i]++;

而不是

huffmanMap[i]? huffmanMap[i]++ : huffmanMap[i]=1;

毕竟，通过写入 huffmanMap[i]? 你正在检查它是否为零。如果为零，则将其设为 1，这与 huffmanMap[i]++ 相同。

Answer 3

（使用 C++20 的 C++ 语言功能的答案。

但首先，您询问如何获取文本中字母的计数（频率）。

对此几乎有一种通用的解决方案。我们可以使用 std::unordered_map 中的 C++ 参考此处

这是std::unordered_map非常方便的索引运算符 [] 这使得计数变得非常简单。该运算符返回对映射到键的值的引用。因此，它搜索键，然后返回值。如果键不存在，它会插入一个新的键/值对并返回对该值的引用，

因此，无论如何，都会返回对该值的引用，例如：

使用“std：”。 :unordered_mapmymap{};" 和文本“aba”，可以使用索引运算符完成以下操作：

• mymap['a'] 将在地图中搜索“a”。未找到该值，因此创建了一个对应值为 0 的“a”新条目：返回对该值的 a 引用。并且，如果我们现在增加该值，我们将增加计数器值。因此，mymap['a']++，将插入一个新的gey/值对'a'/0，然后递增它，导致'a'/1
• 对于'b'相同就会发生以上情况。
• 对于下一个“a”，将在映射中找到一个条目，因此返回对值 (1) 的引用。此值会递增，然后为 2

等等。

通过使用一些现代语言元素，可以使用一个简单的 for 循环来读取整个文件并计算其字符数：

for (const char c : rng::istream_view<char>(ifs)) counter[c]++;

附加信息：

为了构建一棵霍夫曼树，我们可以使用最小堆，它可以使用现有的 std::priority_queue 轻松实现。请阅读此处了解相关内容。

只需4行代码，就可以构建完整的霍夫曼树。

最后，我们将结果放入密码本中。再次使用 std::unordered_map 并将结果显示给用户。

例如，这可以像下面这样实现：

#include <iostream>
#include <fstream>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <ranges>
#include <vector>
#include <utility>

namespace rng = std::ranges;            // Abbreviation for the rnages namespace
using namespace std::string_literals;   // And we want to use stding literals

// The Node of the Huffmann tree
struct Node {                           
    char letter{ '\0' };                // The letter that we want to encode
    std::size_t frequency{};            // The letters frequency in the source text
    Node* left{}, *right{};             // The pointers to the children of this node
};

// Some abbreviations to reduce typing work and make code more readable
using Counter = std::unordered_map<char, std::size_t>;
struct Comp { bool operator ()(const Node* n1, const Node* n2) { return n1->frequency > n2->frequency; } }; 
using MinHeap = std::priority_queue<Node*, std::vector<Node*>, Comp>;
using CodeBook = std::unordered_map<char, std::string>;

// Traverse the Huffmann Tree and build the code book
void buildCodeBook(Node* root, std::string code, CodeBook& cb) {
    if (root == nullptr) return;
    if (root->letter != '\0') cb[root->letter] = code;
    buildCodeBook(root->left, code + "0"s, cb);
    buildCodeBook(root->right, code + "1"s, cb);
}
// Get the top most two Elements from the Min-Heap
std::pair<Node*, Node*> getFrom(MinHeap& mh) {
    Node* left{ mh.top() }; mh.pop();
    Node* right{ mh.top() }; mh.pop();
    return { left, right };
}

// Demo function
int main() {
    if (std::ifstream ifs{ "r:\\lorem.txt" }; ifs) {

        // Define moste important resulting work products
        Counter counter{};
        MinHeap minHeap{};
        CodeBook codeBook{};

        // Read complete text from source file and count all characters ---------
        for (const char c : rng::istream_view<char>(ifs)) counter[c]++;

        // Build the Huffmann tree ----------------------------------------------
        // First, create a min heap, based and the letters frequency
        for (const auto& p : counter) minHeap.push(new Node{p.first, p.second});

        // Compress the nodes
        while (minHeap.size() > 1u) {
            auto [left, right] = getFrom(minHeap);
            minHeap.push(new Node{ '\0', left->frequency + right->frequency, left, right });
        }
        // And last but not least, generate the code book -----------------------
        buildCodeBook(minHeap.top(), {}, codeBook);

        // And, as debug output, show the code book -----------------------------
        for (const auto& [letter, code] : codeBook) std::cout << '\'' << letter << "': " << code << '\n';
    }
    else std::cerr << "\n\n***Error: Could not open source text file\n\n";
}

您我注意到我们使用 new 来分配内存。但事后我们不会删除它。

我们现在可以在适当的位置添加删除语句，但我将向您展示使用智能指针的修改后的解决方案。

请看这里：

#include <iostream>
#include <fstream>
#include <string>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <queue>
#include <ranges>
#include <vector>
#include <utility>
#include <memory>

namespace rng = std::ranges;                // Abbreviation for the rnages namespace
using namespace std::string_literals;       // And we want to use stding literals
struct Node;                                // Forward declaration
using UPtrNode = std::unique_ptr<Node>;     // Using smart pointer for memory management

// The Node of the Huffmann tree
struct Node {
    char letter{ '\0' };                    // The letter that we want to encode
    std::size_t frequency{};                // The letters frequency in the source text
    UPtrNode left{}, right{};               // The pointers to the children of this node
};

// Some abbreviations to reduce typing work and make code more readable
using Counter = std::unordered_map<char, std::size_t>;
struct CompareNode { bool operator ()(const UPtrNode& n1, const UPtrNode& n2) { return n1->frequency > n2->frequency; } };
using MinHeap = std::priority_queue<UPtrNode, std::vector<UPtrNode>, CompareNode>;
using CodeBook = std::map<Counter::key_type, std::string>;

// Traverse the Huffmann Tree and build the code book
void buildCodeBook(UPtrNode&& root, std::string code, CodeBook& cb) {
    if (root == nullptr) return;
    if (root->letter != '\0') cb[root->letter] = code;
    buildCodeBook(std::move(root->left), code + "0"s, cb);
    buildCodeBook(std::move(root->right), code + "1"s, cb);
}
// Get the top most to Elements from the Min-Heap
std::pair<UPtrNode, UPtrNode> getFrom(MinHeap& mh) {

    UPtrNode left = std::move(const_cast<UPtrNode&>(mh.top()));mh.pop();
    UPtrNode right = std::move(const_cast<UPtrNode&>(mh.top()));mh.pop();
    return { std::move(left), std::move(right) };
}

// Demo function
int main() {
    if (std::ifstream ifs{ "r:\\lorem.txt" }; ifs) {

        // Define moste important resulting work products
        Counter counter{};
        MinHeap minHeap{};
        CodeBook codeBook{};

        // Read complete text from source file and count all characters ---------
        for (const char c : rng::istream_view<char>(ifs)) counter[c]++;

        // Build the Huffmann tree ----------------------------------------------
        // First, create a min heap, based and the letters frequency
        for (const auto& p : counter) minHeap.push(std::make_unique<Node>(Node{ p.first, p.second }));

        // Compress the nodes
        while (minHeap.size() > 1u) {
            auto [left, right] = getFrom(minHeap);
            minHeap.push(std::make_unique<Node>(Node{ '\0', left->frequency + right->frequency, std::move(left), std::move(right) }));
        }
        // And last but not least, generate the code book -----------------------
        buildCodeBook(std::move(const_cast<UPtrNode&>(minHeap.top())), {}, codeBook);

        // And, as debug output, show the code book -----------------------------
        for (std::size_t k{}; const auto & [letter, code] : codeBook) std::cout << ++k << "\t'" << letter << "': " << code << '\n';
    }
    else std::cerr << "\n\n***Error: Could not open source text file\n\n";
}