Erreur de segmentation lors de la vérification du noeud NULL

Question

Je crée une file d'attente prioritaire avec des fonctions de fusion, d'insertion et de récupération. Un programme de test insère des nœuds en fournissant les données et la priorité, je crée le nœud et tente de le placer dans une file d'attente de priorité de tas d'arbre de gauche.

Voici le code pour le nœud de classe:

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) {} ; 
} ; 

Ceci est mon code pour insérer un nœud à l'aide d'une fusion et d'échange:

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; 
} 

Le code de test pour l'insert est la suivante:

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

La première insertion fonctionne correctement. La deuxième insertion obtient à la fonction de fusion, entre la première boucle récursive à p->right = merge (p->right , q); et donne une erreur seg sur le si (p == NULL) return q ; Après avoir fait une vérification p fait = NULL à ce stade encore j'obtiens l'erreur en vérifiant si p == NULL. Toute aide est appréciée.

Answer 1

Je suppose que ça ne plante pas vraiment là où vous pensez que c'est.

Vous avez cependant quelques bugs. Tout d'abord, notez que votre fonction de permutation échange les pointeurs donnés, mais cela n'a aucun effet sur l'arborescence. Je pense que vous vouliez faire référence à ces arguments: swap (Node<DATA> *&p, Node<DATA> *&q)

Ensuite, notez que vous supprimez un noeud là, mais vous n'en avez pas affecté un. Vous libérez le noeud p. Cela peut provoquer une erreur de segmentation.