从一个字符串中用2个键填充Map,字符和频率c++

mjqavswn  于 2022-12-05  发布在  其他
关注(0)|答案(3)|浏览(105)

我是新的Map,所以有点不确定最好的方法来做这件事。这个任务是关于压缩与霍夫曼编码。这里我有什么。

#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();

我从一个文本文件读入一个填充字符串的fileline。

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

这里是我尝试的第二种方法来填充Map,字符值不正确,符号和笑脸..

getFreq(fileline,huffmanMap);

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

这就是我如何打印Map

system("pause");
    return 0;
}

当我运行我的getFreq方法时,程序崩溃了。我没有得到任何错误。使用第二个方法时,char值是无意义的。注意,我没有同时运行这两个方法,我只是将它们都包括进来以显示我所尝试的。
任何见解都将不胜感激。谢谢。)

qoefvg9y

qoefvg9y1#

你的代码到处都是,它不是很连贯,所以很难理解流程。
以下是一些低亮度:

这是错误的myfile.open("text.txt",ios::out);-为什么要用out标志打开一个输入流?它应该简单地为:

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

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

在while循环中,您要做的是遍历内容并将其添加到Map中?因此,现在的代码如下所示:

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方法签名是错误的,您是通过值(即复制)而不是引用传递Map,因此您在函数中的修改是复制而不是原始的!

错误:void getFreq(string file, map<char, int> map)
正确:void getFreq(string file, huffmanMap_Type& map)

**Next:**为什么在上面的方法中使用clear()?如果有多行呢?肯定不需要这样做吧?

这就足够了,清理你的代码,如果有更多的问题,更新你的问题。

qaxu7uf2

qaxu7uf22#

一次修复和一次改进。
修复方法是:在getFreq引用中创建第二个参数:

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

改进之处在于:只是写

huffmanMap[i]++;

代替

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

毕竟,通过写huffmanMap[i]?,你要检查它是否为0,如果为0,你就把它变成1,这和huffmanMap[i]++是一样的。

sf6xfgos

sf6xfgos3#

(An使用 C++ 的功能回答C20。
但首先,你问的是如何获得文本中字母的数量(频率)。
几乎有一个通用的解决方法。我们可以使用std::unordered_map。它在C
参考here中描述。
它是std::unordered_map非常方便的索引operator[],它使得计数非常简单。这个运算符返回一个对Map到键的值的引用。因此,它搜索键,然后返回值。如果键不存在,它插入一个新的键/值对,并返回对值的引用。
因此,无论如何,都会返回一个对该值的引用。并且它可以递增。例如:
如果一个字符串中包含一个“std::unordered_map〈char,int〉mymap{};“和文本“阿坝”,则可以用索引运算符完成以下操作:

  • mymap ['a']将在Map中搜索'a'。未找到,因此将为'a'创建一个新条目,其对应值为0:返回值的a引用。如果我们现在递增它,我们将递增计数器值。因此,mymap['a']++,将插入一个新的gey/value对'a'/0,然后递增它,得到'a'/1
  • 对于“B”,将发生与上述相同的情况。
  • 对于下一个“a”,将在Map中找到一个条目,因此返回对值(1)的引用。该值递增,然后将为2

等等等等。
通过使用一些现代语言元素,可以读取整个文件并计算其字符数,只需一个简单的for-循环:

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

其他信息:
我们可以使用最小堆来构建哈夫曼树,它可以很容易地用现有的std::priority_queue来实现。请阅读here
通过4行代码,可以构建完整的Huffmann树。
最后,我们把结果放在一个代码本里,同样是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来分配内存,但是我们之后并没有使用delete
我们现在可以在适当的位置添加delete语句,但我将向您展示一个使用智能指针的修改后的解决方案。
请看这里:

#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";
}

相关问题