Huffman coding c++

Question

So I am working on Huffman coding for a project. However, my code just doesn't work. When i ran it on visual studio, it didn't give me an error. What I was trying to do is to read a file and put all of them into a string. And get the frequency for each character in that string. But I think when the file got a little bit large, it seems like my code is running in a infinite loop. Can anyone explain anything to me? By the way, I had a sorted function that I used to sort a vector of node* by their frequency.

ifstream infile;
infile.open(filename);
string q;
string line;
while (getline(infile, line))
{
 q += line;
}
char y;
int count = 0;
int check = 0;
for (int i = 0; i < q.size(); i++) //if the string gets big, it seems to become an infinite loop in here
{
 y = q[i];
 for (int x = i - 1; x > 0; x--) //make sure not counting the same char
 {
 if (y == q[x])
 {
 check++;
 }
 }
 if (check == 0)
 {
 for (int i = 0; i < q.size(); i++)
 {
 if (q[i] == y)
 {
 count++;
 }
 }
 node*x = new node;
 x->char1 = y; //my node have char 
 x->freq = count; //my node has frequency
 list1.push_back(x);
 }
 count = 0;
 check = 0;
}
sort(list1.begin(), list1.end(), sorter); //sort them from small to big
while (list1.size() > 1)
{
 node*left = list1[0];
 node*right = list1[1];
 list1.erase(list1.begin(), list1.begin() + 2);
 double sum = left->freq + right->freq;
 node* x = new node;
 x->freq = sum;
 x->left = left;
 x->right = right;
 list1.push_back(x);
 sort(list1.begin(), list1.end(), sorter);
}
list1.clear();
return true;

The following is my sort function

static struct {
bool operator()(NodeInterface* a, NodeInterface* b) {
 if (a->getFrequency() == b->getFrequency()) {//if the frequencies are even,
 if (b->getCharacter() == '0円') return false;
 if (a->getCharacter() != '0円') {
 return (int)a->getCharacter() < (int)b->getCharacter();
 }
 return false;
 }
 return a->getFrequency() < b->getFrequency();
}

} sorter;

• Ken Y-N: The sorter looks wrong; if a->getFrequency() and b->getFrequency() are equal and both a->getCharacter() and b->getCharacter() are 0円, both a < b and b < a are false. This will confuse the sort, and return (int)a->getCharacter() < (int)b->getCharacter(); should be sufficient without the guards.
• aschepler: @KenY-N If a and b are equivalent, then both a<b and b<a should return false.
• Felipe Lopez: Something is overflowing, try changing the variables so they can store more data, ex. int64_t
• Felipe Lopez: The infinite loop problem would be easy to figure out, just use F10 to step through your code line by line! and check the variables values!
• Ken Y-N: @aschepler Ah... Not enough coffee, or some excuse like that!

Answer 1

I see two major problems.

You have a for loop inside a for loop both initializing and using int i

Change the variable name of the inner loop.

for (int i = 0; i < q.size(); i++) //if the string gets big, it seems to become an infinite loop in here
.
.
 if (check == 0)
 {
 for (int i = 0; i < q.size(); i++) //Change this to int j for example
 {
 .
 .

And the Sorter struct. I would rewrite it as this.

static struct {
 bool operator()(NodeInterface* a, NodeInterface* b) {
 if (a->getFrequency() == b->getFrequency()) {//if the frequencies are even,
 if (b->getCharacter() == '0円') return false;
 if (a->getCharacter() == '0円') return true;
 return (int)a->getCharacter() < (int)b->getCharacter();
 }
 return a->getFrequency() < b->getFrequency();
 }
} sorter;

A few suggestions for your for loop:

for (int i = 0; i < q.size(); i++) //if the string gets big, it seems to become an infinite loop in here
{
 y = q[i];
 //You can avoid this entire loop by using a structure like map
 for (int x = i - 1; x > 0; x--) //make sure not counting the same char
 {
 if (y == q[x])
 {
 check++;
 //break; //if you use a loop, break it once you find the character.
 }
 }
 if (check == 0)
 {
 for (int j = 0; j < q.size(); j++)//Renamed variable + you can start this loop from j = i as you know there is no occurrence of y before that.
 {
 if (q[i] == y)
 {
 count++;
 }
 }
 node*x = new node;
 x->char1 = y; //my node have char 
 x->freq = count; //my node has frequency
 list1.push_back(x);
 }
 count = 0;
 check = 0;
}