Problème d'implémentation des listes liées

Question

J'essaie de créer une pile en utilisant une structure de liste liée sous-jacente.

Peut-être que je me trompe, mais j'ai des problèmes avec la fonction remove().

int Stack::remove(){ 
    node* victim = new node; 
    int popped; 
    popped = top->element; 
    victim = top; 
    top = victim->next; 
    delete victim; 
    return popped; 
} 

Je reçois glibc dectecting

à double libre ou la corruption (out);

Puisque j'alloue une nouvelle mémoire à la victime, ne dois-je pas supprimer la victime, ou est-ce quelque chose dont je n'ai pas à me soucier?

Answer 1

Une pile ressemble beaucoup à un groupe de vaisselle qui sont lavées et superposées. C'est le premier en est le dernier (type de données FILO). Cela est si votre pile lu en 2, 7, 8 puis il semblerait que:

C'est d'abord le 2 est placé dans la pile, suivie le 7 puis le 8. Si vous voulez supprimer ou faire apparaître la pile, vous devez déplacer la tête du pointeur. Votre code me semble un peu étrange ...

int Stack::remove() 
{ 
    int datum;  //to store the popped value 
    node* temp=head; //assign pointer to head of list 
    datum = temp->data; //grab the data value stored at the head (or temp since they carry same reference) 
    head = temp->next; //move the head pointer (in our example now it points to 7) 
    delete temp; 
    return datum; 
} 

Answer 2

Il n'y a aucune raison d'allouer de la mémoire de tas dans une méthode remove() comme vous le faites avec victim. Ce que vous voulez est:

int Stack::remove(){ 
    node* new_top = top->next; 
    int popped = top->element; 

    delete top; 
    top = new_top; 

    return popped; 
} 

Answer 3

Vous n'avez pas besoin d'allouer un nœud pour victim. Affectez-lui simplement le haut de la pile et, si ce n'est pas null, définissez top sur son pointeur next, récupérez la valeur de victim, puis libérez le victim.

Il ne s'agit pas réellement d'une corruption, mais d'une fuite de mémoire: vous allouez un nœud, puis remplacez ce pointeur par victim = top;, perdant ainsi la trace de la mémoire allouée.