mardi 17 avril 2018

Can't locate Segmentation error in a C++ program implementing the Huffman table

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <map>

using namespace std;


class HuffmanNode{
 public:
 char data;
 int count;
 HuffmanNode *left;
 HuffmanNode *right;
};


//Compare function for priority queue
class compare_function{
public:
bool operator()(const  HuffmanNode* one, const  HuffmanNode* two){
return one->count> two->count;
}

};

/*
Struct used for the final map which uses
ascii value as keys and contains 
*/
struct information{
int freq;
string code;

};


int main(){

//Helps build the huffman table
priority_queue<HuffmanNode*, vector<HuffmanNode*>,compare_function> 
huffman_table;

/*Use manual input
replace with file input later
Helps get the frequency count
*/
map<char, int> frequency;

string text = "What is your name";

for(char c: text)
    frequency[c]++;

/*Put the informaton from the map to the 
 priority queue */

 for(auto var: frequency){
    HuffmanNode* node= new HuffmanNode;
    node->data=var.first;
    node->count=var.second;
    node->left=nullptr;
    node->right= nullptr;

 }

//Building a tree
 HuffmanNode* combined= nullptr; // Declared outside as it can be used to combine with the last node in the priority queue
 while(huffman_table.size() >= 2){
    HuffmanNode * one = huffman_table.top(); // First minimum node
    huffman_table.pop(); // Popped out of the queue
    HuffmanNode*two = huffman_table.top(); //Second minimum node
    huffman_table.pop(); //Popped out of the queue

    //Combining the two nodes and re inserting to the table
    combined= new HuffmanNode();
    combined->data= '\0';
    combined->count= one->count+two->count;
    combined->left = one;
    combined->right = two;
    //Re-inset back to the table
    huffman_table.push(combined);

 }



/*The root of the table is the combination of the compared node and 
   the last node in the priority queue*/
 HuffmanNode* last = huffman_table.top();
 HuffmanNode* root= new HuffmanNode;
 root->data ='\0';
 root->count=combined->count+ last->count;
 root->left= combined;
 root->right = last;



//Map containing final solution
 map<char, information> solution;
 information i;


 //traverse the tree in search of the node and compute code
HuffmanNode* x = root;
string temp;
for(auto var: frequency){

   while(x->data != var.first)
   {
    if(x==nullptr)
        x=root;
    else if (x->count < var.second){
        temp=temp+"0";
        x=x->left;
    }
    else if(x->count > var.second){
        temp= temp+"1";
        x=x->right;
    }
   }
   i.code=temp;
   i.freq=var.second;
   solution[var.first]=i;
   x=root;
   temp="";

}
//Prints answer here
for(auto var: solution){
    cout<<var.first<<" "<<var.second.freq<<" "<<var.second.code;
}

}

I've tried to implement a Huffman table here. I understand how it works and I don't really see anything wrong with the approach I used and there aren't any syntax errors. However, I seem to be getting a segmentation fault 11 error and I'm not sure where exactly. I've added comments to every section to indicate what happens where. Any form of assistance, as to which portion of the code I need to overlook would be really appreciated.

Aucun commentaire:

Enregistrer un commentaire