Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
5.0 kB
0
Indexable
Never
#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> &times)
{
    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> &times)
{
    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> &times)
{
    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);
    }
}
Leave a Comment