How does this code work? Please explain the calls and logic behind the statement

Question

How does this code work?

Please explain the calls and logic behind the statements of the code

#include<iostream>

#include<vector>

#include<string>

using namespace std;

struct node

{

node * leftChild;

node * rightChild;

double frequency;

    string content;

string code;

};

vector<node> nodeArray;// Use nodeArray to record all the nodes that may be created in the whole process

node extractMin()

{

double temp = (double) INT_MAX;

    vector<node>::iterator i1,pos;

    for(i1 = nodeArray.begin();i1!=nodeArray.end();i1++)

{

if(temp>(*i1).frequency)

{

     pos = i1;

     temp = (*i1).frequency;

}

}

node tempNode = (*pos);

nodeArray.erase(pos);

return tempNode;

}

node getHuffmanTree()

{

while(!nodeArray.empty())

{

   node * tempNode = new node;  

      node * tempNode1 = new node;

   node * tempNode2 = new node;

      *tempNode1 = extractMin();

   *tempNode2 = extractMin();

   tempNode->leftChild = tempNode1;

   tempNode->rightChild = tempNode2;

   tempNode->frequency = tempNode1->frequency+tempNode2->frequency;

   nodeArray.push_back(*tempNode);

   if(nodeArray.size() == 1)//only the root node exsits

   {

    break;

   }

}

    return nodeArray[0];

}

void BFS(node * temproot,string s)

{

   node * root1 = new node;

   root1 = temproot;

   root1->code = s;

   if(root1 == NULL)

   {

   }

   else if(root1->leftChild == NULL && root1->rightChild == NULL)

   {

    cout<<"the content is "<<root1->content<<endl;

    cout<<"and its corresponding code is "<<root1->code<<endl;

   }

   else

   {

      root1->leftChild->code = s.append("0");

   s.erase(s.end()-1);

   root1->rightChild->code = s.append("1");

   s.erase(s.end()-1);

      BFS(root1->leftChild,s.append("0"));

   s.erase(s.end()-1);

      BFS(root1->rightChild,s.append("1"));

   s.erase(s.end()-1);

}

}

void getHuffmanCode()

{

int size,i;

double tempDouble;

string tempString = "";

cout<<"please input the number of things you want to encode!"<<endl;

cin>>size;

for(i = 0;i<size;i++)

{

cout<<"please input the things you want to encoded and their frequencies!"<<endl;

node tempNode;

cin>>tempString;

cin>>tempDouble;

tempNode.frequency = tempDouble;

tempNode.content = tempString;

tempNode.leftChild = NULL;

tempNode.rightChild = NULL;

nodeArray.push_back(tempNode);

}

node root = getHuffmanTree();

BFS(&root,"");

}

int main()

{

vector<int> test;

test.push_back(1);

test.push_back(2);

test.push_back(3);

test.push_back(4);

vector<int>::iterator i1 = test.begin();

test.erase(i1);

getHuffmanCode();

system("pause");

return 0;

}

Explanation / Answer

First this code is declaring a structure of type node.

Then it has a vector node array in which we are pushing all the values later in main.

Extractmin() is node type of function that is extracting minimum value out of node then gethuffmantree() is creating a huffman tree taking these nodes and putting them to left and right sides to the root element.

iterator i1, pos is searching the pos for i1 value, in extractmin().

    for(i1 = nodeArray.begin();i1!=nodeArray.end();i1++) is browsing the nodeArray from beginning to end taking i1 increment each time. Finding the elements in order and placing them in form of huffman tree.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.