Код Хаффмана C ++ выдает фатальную ошибку - PullRequest
Новая
       18

Код Хаффмана C ++ выдает фатальную ошибку

0 голосов
/ 21 января 2020

Я пишу код для известного алгоритма кодирования Хаффмана. Я получаю фатальную ошибку, которая превращает систему в синий экран, а затем перезагружается. Эта ошибка возникает в display_Codes, которые имеют рекурсивные вызовы. Ошибка возникает в следующих строках: 

display_Codes(root->l, s + "0"); 
display_Codes(root->r, s + "1" );

Ниже приведен полный код. 

#include <iostream>

#include <bits/stdc++.h> 

using namespace std;




class HeapNode_Min {




public:


char d; 

unsigned f; 

HeapNode_Min *l, *r;
HeapNode_Min(char d, unsigned f) 
{ 

      this->d = d;
      this->f = f;
}




~HeapNode_Min()
 {
   delete l;
   delete r;
 } 
}; 



class Analyze {  

  public:
    bool operator()(HeapNode_Min* l, HeapNode_Min* r) 
    { 
        return (l->f > r->f);
    } 
}; 



void display_Codes(HeapNode_Min* root, string s) 
{   
    if(!root) 
        return; 

    if (root->d != '$') 
        cout << root->d << " : " << s << "\n";

    display_Codes(root->l, s + "0"); 
    display_Codes(root->r, s + "1" ); 

} 

void HCodes(char data[], int freq[], int s) 
{ 
    HeapNode_Min  *t,*r, *l ;  


    priority_queue<HeapNode_Min*, vector<HeapNode_Min*>, Analyze> H_min; 

    int a=0;
    while (a<s){H_min.push(new HeapNode_Min(data[a], freq[a])); ++a;}


    while (H_min.size() != 1) { 

        l = H_min.top(); H_min.pop(); 
        r = H_min.top(); H_min.pop(); 

        t = new HeapNode_Min('$',  r->f + l->f); 

        t->r = r; t->l = l; 


        H_min.push(t); 
    } 
    display_Codes(H_min.top(), ""); 
} 



int main() 
{ 
    try
    {

        int frequency[] = { 3, 6, 11, 14, 18, 25 };  char alphabet[] = { 'A', 'L', 'O', 'R', 'T', 'Y' };  
        int size_of = sizeof(alphabet) / sizeof(alphabet[0]); 

      cout<<"Alphabet"<<":"<<"Huffman Code\n";
      cout<<"--------------------------------\n";

      HCodes(alphabet, frequency, size_of);
    }
    catch(...)
    {
    }
    return 0; 
}

1 Ответ

5 голосов
/ 21 января 2020

Вы никогда не устанавливаете l или r на nullptr, но ваш код полагается, что указатели либо действительны, либо nullptr: 

void display_Codes(HeapNode_Min* root, string s) 
{   
    if(!root) 
        return; 

    if (root->d != '$') 
        cout << root->d << " : " << s << "\n";

    display_Codes(root->l, s + "0"); 
    display_Codes(root->r, s + "1" ); 

}

Передайте a root без левого и правого узла, тогда ни root->l, ни root->r не имеют значения, которое вы можете использовать для чего угодно. Передача их в следующую рекурсию позволяет разыменовать их, что вызывает неопределенное поведение.

Чтобы исправить это, вам нужно инициализировать указатели, например, в конструкторе: 

HeapNode_Min(char d, unsigned f) : d(d),f(f),l(nullptr),r(nullptr) { }

Также ваш класс не делает этого следуйте правилу 3/5/0 .

...