檢查NULL節點時發生分段錯誤

Question

我正在使用合併，插入和提取功能創建優先隊列。測試程序通過提供數據和優先級來插入節點，我創建節點並嘗試將其放置在左側樹堆優先級隊列中。

這是類節點代碼：

template <class DATA> 
class Node { 
    public : 
    DATA data ; 
    double priority ; 
    unsigned distance ; 
    Node<DATA> * left , * right ; 

    Node (DATA & d , double prio) : data (d) , priority(prio) , 
    distance(0) , left(NULL) , right(NULL) {} ; 
} ; 

這是我的代碼使用合併和交換插入節點：

template<class DATA> 
Node<DATA> * 
PQueue<DATA> :: merge (Node<DATA> * p , Node<DATA> * q) 
{ 
    unsigned d1, d2; 

    if (p == NULL) return q ; 
    if (q == NULL) return p ; 

    if ((p->priority) < (q->priority)) // p is final root. 
     swap(p,q) ; 

    p->right = merge (p->right , q); 

    d1 = p->left->distance; 
    d2 = p->right->distance; 

    if (d1 < d2) 
     swap(p->left,p->right) ; // leftist tree. 

    p->distance = 1 + p->right->distance ; 

    return p ; 
} 

template<class DATA> 
void 
PQueue<DATA> :: swap (Node<DATA> * p, Node<DATA> * q) 
{ 
    Node<DATA> * temp; 
    temp = p; 
    p = q; 
    q = temp; 
    delete temp; 
} 

template < class DATA > 
bool 
PQueue<DATA> :: insertPQ (DATA & data , double priority) 
{ 
    root = merge(root, new Node<DATA>(data, priority)); 
    return true; 
} 

用於插入測試代碼是這樣的：

pq.insertPQ(data[i] , data[i]) 

第一次插入工作正常。第二次插入到合併函數，進入第一個遞歸循環p->right = merge (p->right , q);，並給出了一個seg錯誤if if (p == NULL) return q ;做了一些檢查p does = NULL在這一點上，但當我檢查p == NULL時，我得到錯誤。任何幫助表示讚賞。

Answer 1

我懷疑它並沒有真正崩潰在你認爲的地方。

雖然你有幾個錯誤。 首先，請注意您的交換函數將交換給定的指針，但這對樹中沒有任何影響。我想你的意思是使這些參數引用：swap (Node<DATA> *&p, Node<DATA> *&q)

其次，請注意，您刪除了一個節點，但您還沒有分配一個。你正在釋放p節點。這可能會導致段錯誤。