Suppression de nœuds dans une liste doublement chaînée (C++)

Question

Je n'arrive pas à comprendre pourquoi lorsque je crée deux nœuds ou plus (comme indiqué ci-dessous), la fonction void del_end() ne supprime que le char name[20] et non le nœud entier. Comment puis-je résoudre ce problème sans fuite de mémoire?

#include <iostream> 
using namespace std; 

struct node 
{ 
    char name[20]; 
    char profession[20]; 
    int age; 
    node *nxt; 
    node *prv; 
}; 

node *start_ptr = NULL; 

void del_end() 
{ 
    node *temp, *temp2; 
    temp = start_ptr; 
    if (start_ptr == NULL) 
     cout << "Can't delete: there are no nodes" << endl; 
    else if (start_ptr != NULL && start_ptr->nxt == NULL) 
    {start_ptr=NULL;} 
    else 
    { 
    while (temp->nxt != NULL) 
    { 
     temp = temp->nxt; 
    } 
    temp2=temp->prv; 
    delete temp; 
    temp->nxt= NULL; 
    } 
} 

Answer 1

Votre code a quelques problèmes, le pire étant ici:

temp2=temp->prv; 
delete temp2; 
temp->nxt= NULL; 

vous supprimez le prochain avant-dernier noeud, laissant des pointeurs vers elle ballants, et perdre le dernier nœud.

Mais si vous publiez plus de code réel, nous pouvons vous en dire plus.

EDIT:
Voici une version légèrement nettoyé de del_end (et il y a encore beaucoup de place à l'amélioration).

void del_end() 
{ 
    if (start_ptr == NULL) 
    { 
    cout << "Can't delete: there are no nodes" << endl; 
    return; 
    } 

    if (start_ptr->nxt == NULL) 
    { 
    delete start_ptr; 
    start_ptr = NULL; 
    return; 
    } 

    node *nextToLast = start_ptr; 
    node *last = start_ptr->nxt; 

    while(last->nxt != NULL) 
    { 
    nextToLast = last; 
    last = last->nxt; 
    } 

    delete last; 
    nextToLast->nxt = NULL; 

    return; 
} 

Notez que cela ne pas supposer que les prev liens sont corrects, ce qui semble prudent ici.

Answer 2

delete temp2; 

supprimerons nœud entier.

Answer 3

Si vous êtes préoccupé par la mémoire, je recommande fortement d'apprendre à travailler avec Valgrind http://valgrind.org/. C'est un excellent outil. Valgrind divise les fuites de mémoire en 3 catégories:

• « définitivement perdu » - pointeur vers dynamiquement la mémoire allouée est perdue et il n'y a pas moyen de le récupérer
• « peut-être perdu » - pointeur vers la mémoire allouée dynamiquement pointe à l'intérieur d'un bloc et peut être sans rapport avec
• « encore accessible » - pointeur vers la mémoire allouée dynamiquement existe toujours, mais la mémoire n'a jamais été libéré à la fin des programmes d'exécution

Courir Valgrind est également très simple. Voici un lien vers le manuel d'utilisation http://valgrind.org/docs/manual/manual.html. Certains drapeaux utiles lors de l'exécution valgrind:

• --leak-check=<no|summary|yes|full>
• --show-reachable=<no|yes>

Maintenant, la façon dont je supprimer un nœud dans une liste doublement liée est:

// if the node to be removed is the head node 
if (nodeToRemove->prev == NULL) { 
    // reassign the head node pointer 
    start_ptr = nodeToRemove->next; 
} else { 
    // correct previous node pointer 
    nodeToRemove->prev->next = nodeToRemove->next; 
} 

// if the node to be removed node is the tail node 
if (nodeToRemove->next == NULL) { 
    // reassign the tail node pointer 
    end_ptr = nodeToRemove->prev; 
} else { 
    // correct next node pointer 
    nodeToRemove->next->prev = nodeToRemove->prev; 
} 

// deallocate memory 
delete(nodeToRemove); 
nodeToRemove = NULL; 

simplement déclarer node *end_ptr = NULL; après avoir déclaré start_ptr et lorsque vous ajoutez un nœud à la liste, assurez-vous que le paramètre end_ptr pointe toujours vers la fin de la liste ... et si vous ajoutez à la fin de la liste, c'est facile ... pointez simplement le end_ptr vers le noeud ajouté.

Vous pourriez aussi bien garder un pointeur de queue, si vous devez toujours supprimer le dernier noeud. Donc, une fois que vous avez le nœud que vous voulez supprimer, je vérifie simplement s'il s'agit du nœud tête/queue, réaffecte les pointeurs suivant/préc, et libère la mémoire.

Btw ... J'ai pris cela de mon implémentation C, donc si la syntaxe est désactivée je m'excuse ... mais la logique est là.

Espérons que ça aide.

Answer 4

Le problème est que vous semblez essayer de supprimer le dernier nœud, mais vous supprimez en fait celui juste avant.

while (temp->nxt != NULL) 
{ 
    temp = temp->nxt; 
} 
temp2=temp->prv; 
delete temp2; 
temp->nxt= NULL; 

Ceci est votre problème. Changez-le en:

while (temp->nxt != NULL) 
{ 
    temp = temp->nxt; 
} 
temp2=temp->prv; 
delete temp; 
temp2->nxt= NULL; 

Et je crois que cela fonctionnera comme prévu. Cela sauvegarde l'avant-dernier nœud, supprime la fin, puis définit le pointeur nxt suivant sur le dernier nœud à null, ce qui en fait le dernier.