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++霍夫曼樹和指針

回答

相關問題