Untitled
unknown
plain_text
a year ago
5.0 kB
3
Indexable
#include<iostream> #include<vector> #include<string> #include<algorithm> #include<queue> #include<fstream> using namespace std; typedef struct HF { char c; //the word in character int t = 0; //the times that this word appear in the file HF *r = nullptr; //initial set it to null to prevent wrong HF *l = nullptr; //initial set it to null to prevent wrong }HF, *hfptr; //type define struct select //use to implement selecting { bool operator()(struct HF *k0, struct HF *k1) { return ((*k0).t) > ((*k1).t); } }; int num; //the number of different words int load_information(vector<char> &, vector<int> &); //load information void sorting(vector<char> &, vector<int> &); //sorting void telluser(void); //tell user to input filename void encode(vector<char> &, vector<int> &); //en void outputfile(string, HF *); void del(HF *); priority_queue<hfptr, vector<hfptr>, select> P; ofstream fileout("霍夫曼編碼結果", ios::out); int main() { vector<char> word; vector<int> times; telluser(); num = load_information(word, times); sorting(word, times); for(int i = 0; i < word.size(); i++) { if(word[i] == '\n') { cout << "換行" << " " << times[i] << endl; } else if(word[i] == ' ') { cout << "空格" << " " << times[i] << endl; } else { cout << word[i] << " " << times[i] << endl; } } encode(word, times); } void encode(vector<char> &word, vector<int> ×) { string str; for(int i = 0; i < num; i++) { HF *point = new HF; (*point).c = word[i]; (*point).t = times[i]; P.push(point); } while(true) { if(P.size() == 1) break; HF *father = new HF; hfptr right, left; left = P.top(); P.pop(); right = P.top(); P.pop(); (*father).t = ((*right).t) + ((*left).t); (*father).l = left; (*father).r = right; P.push(father); } outputfile(str, P.top()); del(P.top()); } void sorting(vector<char> &word, vector<int> ×) { int maxi; for(int i = 0; i < times.size()-1; i++) { maxi = i; for(int index = i+1; index < times.size(); index++) { if(times[index] > times[maxi]) { maxi = index; } } char c = word[i]; int t = times[i]; word[i] = word[maxi]; times[i] = times[maxi]; word[maxi] = c; times[maxi] = t; } } void telluser(void) { cout << "Hello~" << endl; cout << "This is a program to encode Huffman code." << endl; cout << "Please input the file name which is the base you want to encode." << endl; cout << "This program will output a .txt file named 霍夫曼編碼結果 to give the information of your Huffman code"; cout << endl; } void del(HF *father) { if(father == nullptr) { return; } else { del((*father).l); del((*father).r); delete father; } } int load_information(vector<char> &word, vector<int> ×) { char c; string filename; string s; ifstream file; cout << "Enter the file name: "; cin >> filename; file.open(filename); while(file.fail()) { cout << "File could not be opened." << endl; cout << "Please enter the input file name: "; cin >> filename; file.open(filename); } while(file.get(c)) { int i; int appear = 0; for(i = 0; i < word.size(); i++) { if(c == word[i]) { appear = 1; break; } } if(appear == 1 && i != word.size()) { times[i]++; } else { word.push_back(c); times.push_back(1); } } return word.size(); } void outputfile(string str, HF *father) { if(father == nullptr) { return; } else { if((*father).l) { str = str + "0"; } else { } outputfile(str, (*father).l); if((*father).l == nullptr && (*father).r == nullptr) { fileout << (*father).c << ": "; for (int i = 0; i < str.size(); i++) { fileout << str[i]; } fileout << endl; }` else { } str.pop_back(); if(father -> r) { str = str + "1"; } else { } outputfile(str, (*father).r); } }
Editor is loading...
Leave a Comment