Новая строка в дереве Хаффмана - PullRequest
Новая
       26

Новая строка в дереве Хаффмана

0 голосов
/ 26 мая 2019

Мое дерево Хаффмана должно печатать

CR для отображения символа '\ n' LF для отображения символа '\ r'

, но оно просто печатает пробел.

Вот мой код: 

#include <cmath>
#include <fstream>
#include <iostream>
#include <map>
#include <vector>
#include <queue>

#define MAX_TREE_HT 2048

using namespace std;

// map characters to value
map<char, string> codes;

// store frequences
map<char, int> freq;

// Create tree.
struct HuffmanTree {
    char data;                 // One of the input characters
    int freq;                  // Frequency of the character
    HuffmanTree *left, *right; // Left and right child

    HuffmanTree(char data, int freq) {
        left = right = NULL;
        this->data = data;
        this->freq = freq;
    }
};

// Compare Function
struct compare {
    bool operator()(HuffmanTree* l, HuffmanTree* r) { return (l->freq > r->freq); }
};

void printCodes(struct HuffmanTree* root, string str) {
    if(!root) return;
    if(root->data != '$') cout << root->data << ": " << str << "\n";
    printCodes(root->left, str + "0");
    printCodes(root->right, str + "1");
}

void storeCodes(struct HuffmanTree* root, string str) {
    if(root == NULL) return;
    if(root->data != '$') codes[root->data] = str;
    storeCodes(root->left, str + "0");
    storeCodes(root->right, str + "1");
}

// Use vector and queue
//
priority_queue<HuffmanTree*, vector<HuffmanTree*>, compare> minHeap;

// build tree and store codes
void HuffmanCodes(int size) {
    struct HuffmanTree *left, *right, *top;
    for(map<char, int>::iterator v = freq.begin(); v != freq.end(); v++)
        minHeap.push(new HuffmanTree(v->first, v->second));
    while(minHeap.size() != 1) {
        left = minHeap.top();
        minHeap.pop();
        right = minHeap.top();
        minHeap.pop();
        top = new HuffmanTree('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        minHeap.push(top);
    }
    storeCodes(minHeap.top(), "");
}

// map frequencies
void calcFreq(string str, int n) {
    for(int i = 0; i < str.size(); i++) freq[str[i]]++;
}

int main() {
    ifstream t("file.txt");
    string str((std::istreambuf_iterator<char>(t)),
               std::istreambuf_iterator<char>());

    string encodedString;
    calcFreq(str, str.length());
    HuffmanCodes(str.length());
    for(auto v = codes.begin(); v != codes.end(); v++)
        cout << "{key: " << v->first << ' ' << v->second << "}" << endl;

    return 0;
}

Вот пример входного файла "file.txt": 

This is a test line. 
This is a test line. 
This is a test line.

Вот вывод: 

{key:
 10100}
{key:   111}
{key: T 10101}
{key: a 01101}
{key: e 001}
{key: f 01100}
{key: h 0100}
{key: i 110}
{key: l 1011}
{key: n 0111}
{key: s 100}
{key: t 000}
{key: w 0101}

Это базовое дерево Хаффмана без каких-либо фантазий.Мне просто нужно отобразить частоты перевода строки и возврата каретки.Я использую компиляцию g ++ в Ubuntu под управлением Windows 10.

...