演算法作業三 - huffman decoder

huffman.cpp

#include<iostream>
#include<vector>
#include<string>

using namespace std;

struct node
{
    node * left;
    node * right;
    float prob;

    char digit;

    string code;
};

vector<node> nodeArray;

node popMin()
{
    float tmp = 1;
    node *target;
    int mark;

    for(unsigned int i = 0; i != nodeArray.size(); i++)
    {
        if(tmp > nodeArray[i].prob)
        {
            mark = i;
            target = &nodeArray[i];
            tmp = nodeArray[i].prob;
        }
    }

    node tmpNode = *target;

    nodeArray.erase(nodeArray.begin() + mark);

    return tmpNode;
}

node getTree()
{
    while(nodeArray.size() != 1)
    {
        node *tmpNode = new node;
        node *tmpNode1 = new node;
        node *tmpNode2 = new node;

        // get mins from nodeArray and move them to tmpNode
        *tmpNode1 = popMin();
        *tmpNode2 = popMin();

        // link nodes, and give node probability
        tmpNode->left = tmpNode1;
        tmpNode->right = tmpNode2;
        tmpNode->prob = tmpNode1->prob + tmpNode2->prob;

        // push node back to nodeArray
        nodeArray.push_back(*tmpNode);
    }

    // return root
    return nodeArray[0];
}

vector<node> dict;

void writeDict(node* tmpRoot,string s)
{
    node *root1 = tmpRoot;

    root1->code = s;

    if(root1 == NULL){} // make sure that there is a tree
    else if(root1->left == NULL && root1->right == NULL) // leaf
    {
        dict.push_back(*root1);
    }
    else
    {
        // "s.erase(s.end()-1);" is for deleting '/0' after string

        string tmp = s + '1';

        root1->left->code = tmp;
        writeDict( root1->left, tmp );

        tmp = s + '0';

        root1->right->code = tmp;
        writeDict( root1->right, tmp );
    }
}

int main()
{

    // get probability of digits
    for(int i = 0; i<10; i++)
    {
        node tmpNode;

        cin>> tmpNode.prob;
        tmpNode.digit = i+'0';
        tmpNode.left = NULL;
        tmpNode.right = NULL;

        nodeArray.push_back(tmpNode);
    }

    node root = getTree();

    writeDict(&root,"");

    string s="";

    // get code
    cin >> s;

    unsigned int next = 0;

    // compare substring of code with code in dict
    while( next != s.size() )
    {
        for(int j=0 ; j<10 ; j++)
        {
            if( s.compare(next, dict[j].code.size(), dict[j].code) == 0 )
            {
                cout << dict[j].digit ;

                next += dict[j].code.size();
            }
        }
    }

    return 0;
}