霍夫曼编码C++

Question

所以我正在为一个项目的霍夫曼编码工作。但是，我的代码不起作用。当我在Visual Studio上运行它时，它并没有给我一个错误。我想要做的是读取一个文件并将它们全部放入一个字符串中。并获取该字符串中每个字符的频率。但是我认为当文件有点大时，看起来好像我的代码在无限循环中运行。任何人都可以向我解释什么？顺便说一下，我有一个排序函数，我用它来按照频率排序节点*的向量。

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; 

以下是我的排序功能

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(); 
} 

}分拣;

Answer 1

我看到两个主要问题。

您有一个用于内部循环的循环都初始化和使用int i

更改内部循环的变量名。

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 
     { 
     . 
     . 

和分拣机结构。我会重写它。

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; 

您的for循环几点建议：

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; 
}