Сортировка без priorty_queue - PullRequest
Новая
       7

Сортировка без priorty_queue

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

Может кто-нибудь помочь мне разобрать это по частоте, а не по коду? Я теперь, что priority_queue сортирует по ключу, так что это моя первая проблема. Мне нужно изменить это на вектор, но когда я сопоставил его с вектором, программа потерпела крах.

Мне удалось исправить часть непечатных символов, но, к сожалению, я не получаю особой помощи от учебных пособий, доступных для деревьев Хаффмана.

Вот мой код: 

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

using namespace std;

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


calcFreq(str, str.length());
HuffmanCodes(str.length());
for(auto v = codes.begin(); v != codes.end(); v++)

    {
    if (v->first == '\n')
    { cout << "Key:  Newline " <<  "  " << v->second  << endl; }
    else if (v->first == ' ')
    { cout << "Key:  Space" << " " << v->second << endl; }
    else if (v->first == '\r')
    { cout << "Key:  Carriage Return " << " " << v->second << endl; }
    else { cout << "Key:  " << v->first << "  " << v->second << endl; }
    }
return 0;
}
...