Различные выходные данные при установке разных точек останова

Question

Я только что написал код для построения дерева Хаффмана с помощью MinHeap. При тестировании я хочу вывести результат обхода.

Алгоритм прост, но мой код не может получить правильный ответ. Странно, что результат был другим, когда я устанавливал разные точки останова. Например, это зависит от того, устанавливаю ли я точку прерывания в цикле, такую ​​как строка 165 input_list.insert(*parent);.

Входной тест был

4 //number of nodes. 
1 1 3 5 //weight of each node. 

и выход при отладке его с точки останова в петле

5 
10 
1 
2 
1 
5 
3 

, что является правильным. Но когда я просто запускаю его без отладки, у него даже не было выхода. Кто-нибудь знает, как это объяснить?

#include <iostream> 
#include <vector> 

using namespace std; 

#define max_size 100 

int sum=0; 

class huffman_node 
{ 
public: 
    int weight; 
    huffman_node* left_child; 
    huffman_node* right_child; 

    huffman_node(){} 

    huffman_node(int w, huffman_node* l, huffman_node* r): 
     weight(w),left_child(l),right_child(r) {} 

}; 

vector <huffman_node> node_list; 

class minheap 
{ 
public: 
    minheap() 
    { 
     heap=new huffman_node [max_size]; 
     current_size=0; 
    } 

    ~minheap() 
    { 
     delete []heap; 
    } 

    void siftdown(int start, int m) 
    { 
     int i=start; 
     int j=2*i+1; 
     huffman_node temp=heap[i]; 

     while(j<=m) 
     { 
      if(j<m && heap[j+1].weight<heap[j].weight) 
      { 
       ++j; 
      } 
      if(temp.weight<=heap[j].weight) 
      { 
       break; 
      } 
      else 
      { 
       heap[i]=heap[j]; 
       i=j; 
       j=2*i+1; 
      } 
     } 
     heap[i]=temp; 
    } 

    void siftup(int start) 
    { 
     int j=start; 
     int i=(j-1)/2; 
     huffman_node temp=heap[j]; 

     while(j>0) 
     { 
      if(heap[i].weight<=temp.weight) 
      { 
       break; 
      } 
      else 
      { 
       heap[j]=heap[i]; 
       j=i; 
       i=(j-1)/2; 
      } 
      heap[j]=temp; 
     } 
    } 

    bool insert(const huffman_node& input) 
    { 
     if(current_size==max_size) 
     { 
      cout<<"minheap full"<<endl; 
      return false; 
     } 
     heap[current_size]=input; 
     siftup(current_size); 
     ++current_size; 
     return true; 
    } 

    bool remove_min(huffman_node& output) 
    { 
     if(!current_size) 
     { 
      cout<<"minheap empty"<<endl; 
      return false; 
     } 
     output=heap[0]; 
     heap[0]=heap[current_size-1]; 
     --current_size; 
     siftdown(0,current_size-1); 
     return true; 
    } 

private: 
    huffman_node* heap; 
    int current_size; 
}; 

void route_length(huffman_node* &root,int depth) 
{ 
    if(root!=NULL) 
    { 
//  if(root->left_child==NULL&&root->right_child==NULL) 
//  { 
//   sum+=depth*root->weight; 

//  } 
     route_length(root->left_child,depth+1); 
     cout<<root->weight<<endl; 
     route_length(root->right_child,depth+1); 
    } 
    else 
    { 
     return; 
    } 
} 

int main() 
{ 
    minheap input_list; 
    int n; 
    cin>>n; 
    for(int i=0;i<n;++i) 
    { 
     int key; 
     cin>>key; 
     huffman_node input(key,NULL,NULL); 
     input_list.insert(input); 
     cin.get(); 
    } 

    huffman_node* root; 

    for(int i=0;i<n-1;++i) 
    { 
     huffman_node* parent; 
     huffman_node out1; 
     huffman_node out2; 
     input_list.remove_min(out1); 
     input_list.remove_min(out2); 
     node_list.push_back(out1); 
     node_list.push_back(out2); 
     parent=new huffman_node(out1.weight+out2.weight,&node_list[node_list.size()-2],&node_list[node_list.size()-1]); 
     input_list.insert(*parent); 
     root=parent; 
    } 
    route_length(root,0); 
// cout<<sum<<endl; 
    return 0; 

} 

Answer 1

Проблема заключается в том, что вы используете указатели на элементы vector<huffman_node> и хранить их в вашей структуре данных (то есть левый и правый члены huffman_node объекта).

Вещь, которая случайно убивает вашу программу, состоит в том, что std::vector перемещает значения в памяти, когда вы добавляете к ней. Содержимое элементов векторов сохраняется, но места нет. Как только он перемещает элементы, память, в которой использовался вектор, может быть перезаписана любым (то есть gdb также требует кучную память), и теперь указатели указывают на мусор.

Как быстро проверить вменяемость, вы можете сделать ваш код не врезаться путем резервирования места в вашем node_list по телефону

node_list.reserve(max_size*2); 

в начале main. Это не правильный способ дальнейшего развития этого фрагмента кода, но он должен проиллюстрировать проблему.

Лучше, если бы ваш node_list был vector<huffman_node*>. Или если вы изменили элементы слева/справа на векторные индексы вместо указателей.