Untitled
unknown
plain_text
a year ago
3.3 kB
5
Indexable
#include <iostream> #include <fstream> #include <vector> #include <queue> #include <unordered_map> using namespace std; typedef struct Tree { int freq; // 頻率 char key; Tree *left; Tree *right; Tree(int fr = 0, char k = '\0', Tree *l = nullptr, Tree *r = nullptr): freq(fr), key(k), left(l), right(r) {}; } Tree, *pTree; struct compare { bool operator() (Tree *a, Tree *b) { return a->freq > b->freq; // 升冪 } }; priority_queue<pTree, vector<pTree>, compare> pque; // Min-heap // In-order traversal to print Huffman codes void printCode(Tree *proot, string st) { if (proot == nullptr) { return; } if (proot->left) { st += '0'; } printCode(proot->left, st); if (!proot->left && !proot->right) { // Leaf node string paddedCode = st; while (paddedCode.size() < 12) { paddedCode = 'x' + paddedCode; } cout << proot->key << "'s code: " << paddedCode << endl; } st.pop_back(); // Backtrack one character if (proot->right) { st += '1'; } printCode(proot->right, st); } // Free allocated memory on the heap void del(Tree *proot) { if (proot == nullptr) { return; } del(proot->left); del(proot->right); delete proot; } // Huffman coding void huffman(const unordered_map<char, int>& charFrequency) { for (const auto& entry : charFrequency) { Tree *pt = new Tree; pt->key = entry.first; pt->freq = entry.second; pque.push(pt); } // Combine the two smallest frequencies into a tree until only one tree remains while (pque.size() > 1) { Tree *proot = new Tree; pTree pl, pr; pl = pque.top(); pque.pop(); pr = pque.top(); pque.pop(); proot->freq = pl->freq + pr->freq; proot->left = pl; proot->right = pr; pque.push(proot); } string s = ""; printCode(pque.top(), s); del(pque.top()); } // Function to count character occurrences in a text unordered_map<char, int> countCharacterfrequency(const string& text) { unordered_map<char, int> charCount; for (char c : text) { charCount[c]++; } return charCount; } int main() { // Read file ifstream inputFile("HUFFMANtree.txt"); if (!inputFile.is_open()) { cerr << "Error opening the file 'HUFFMANtree.txt'" << endl; return 1; } // Read content from the file string fileContent; char ch; while (inputFile.get(ch)) { fileContent += ch; } //關檔 inputFile.close(); //出現頻率 unordered_map<char, int> charOccurrences = countCharacterfrequency(fileContent); // Print character counts for (const auto& entry : charOccurrences) { if (entry.first == '\n') { cout << "Character '" << "\\n" << "' appears " << entry.second << " times." << endl; } else { cout << "Character '" << entry.first << "' appears " << entry.second << " times." << endl; } } //霍夫曼編碼 huffman(charOccurrences); return 0; }
Editor is loading...
Leave a Comment