设置不同断点输出不同

Question

我刚刚写了一段代码来使用 MinHeap 构建哈夫曼树。测试的时候想输出它的遍历结果。

算法很简单，但我的代码无法得到正确答案。奇怪的是，我设置不同的断点，输出却不同。例如，这取决于我是否在循环中设置断点，例如第 165 行 input_list.insert(*parent);。

测试输入是

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

在循环中使用断点调试时的输出是

没错。但是当我只是运行它而没有调试时，它甚至没有任何输出。有谁知道怎么解释吗？

#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 中保留 space 来避免代码崩溃

node_list.reserve(max_size*2);

在 main 的开头。这不是进一步开发这段代码的正确方法，但应该可以说明问题。

如果您的 node_list 是 vector<huffman_node*> 会更好。或者，如果您将 left/right 成员更改为矢量索引而不是指针。

设置不同断点输出不同

Different output when set different breakpoints

c++

heap