C++霍夫曼树和指针

我正在创建霍夫曼树，为此我开始制作一个Min Heap。堆已建立并按文档中的频率对值进行排序，但在尝试开始创建树时出现问题。C++霍夫曼树和指针

我弹出堆中的前两项，并将一个节点放在它们上面并重新插入堆中。堆是基于数组的，所以它不会触及节点的* left和* right指针。当堆下降到只有一个节点，但它的左和右节点指针都为空，所以我认为这可能是我的指针问题...？我是新来的Java的c + +给我愚蠢的错误。

while(theHeap.getheapSize() > 1) 
    { 
     Node top; 
     Node *min1=new Node(theHeap.topandPop()); 
     Node *min2=new Node(theHeap.topandPop()); 
     top.left=min1; 
     top.right=min2; 
     top.freq=min1->freq+min2->freq; 
     theHeap.insert(top); 
    } 
    Node r=theHeap.topAndPop(); //null pointers for left and right children 

-------------------------------------- 
    //code for heap. arr is in the header file is Node *arr; 

void Heap::insert(Node c) 
{ 
    if (heapSize != arrSize) 
    { 
     heapSize=heapSize+1; 
     arr[heapSize - 1] = c; //does this call copy constructor??? 
     percolateUp(heapSize - 1); 
    } 
} 
void Heap::percolateUp(int nodeIndex) { 

    int parentIndex; 
    Node tmp; 
    if (nodeIndex != 0) 
    { 
     parentIndex = getParentPos(nodeIndex); 
     if (arr[parentIndex].freq > arr[nodeIndex].freq) 
     { 
      tmp = arr[parentIndex]; 
      arr[parentIndex] = arr[nodeIndex]; 
      arr[nodeIndex] = tmp; 
      percolateUp(parentIndex); 

     } 
    } 
}

来源

2010-09-23 Westin

你有没有考虑过使用'std :: priority_queue'作为堆？ – 2010-09-23 04:28:39

这是一项家庭作业，我们不允许使用标准库。 – Westin 2010-09-23 04:31:10

只是为了确保：'top'超出了范围，所以希望'insert（）'调用一个拷贝构造函数而不仅仅是一个地址？ – Reinderien 2010-09-23 04:57:24

首先，我会建议不要混合实例和指针，如果你选择一个，你的任务将会简单得多。在这种情况下，我认为在堆中存储一个指向Node的指针是合适的，而不是一个实例，额外的好处是指针的行为更像Java中习惯的那样，不需要担心复制构造和分配。你只需要记住删除它们（与Java不同），这可以在Heap的Dtor中完成。

其次，要回答您的代码注释中的问题：否在Heap :: insert（）中不调用copy ctor，而是调用赋值运算符。这是否是一个问题取决于您的Node类的外观。

来源

2010-09-23 07:33:37

C++霍夫曼树和指针

回答

相关问题