suppression d'un élément de liste liée provoque une boucle infinie

Question

Je prépare un programme qui prend une liste de nombres entiers dans l'entrée, et sur la base du nombre entier, il effectue les opérations suivantes:

1. supprimer la valeur absolue si la valeur en entrée est négative

2. Si le nombre est positif et même, puis ajouter sur le haut de la liste

3. Si le nombre est positif et impair, ajoutez-le sur la queue de la liste

4. Si le nombre est égal à zéro, terminez le programme et imprimez la liste.

Mon problème est avec la fonction pop_el, ce qui provoque une boucle infinie sur la liste, donc quand j'imprimer la liste du programme va dans une boucle infinie. Voici mon code:

#include <stdio.h> 
#include <stdlib.h> 

typedef struct ll_node_S * ll_node_ptr; 
struct ll_node_S 
{ 
    int v; 
    ll_node_ptr next; 
}; 
typedef struct ll_node_S ll_node; 

ll_node_ptr push_tail(ll_node_ptr head, int v) 
{ 
    ll_node_ptr backup = head; 
    ll_node_ptr current = head; 

    while(current->next != NULL) 
    { 
     current = current->next; 
    } 
    current->next = (ll_node_ptr) malloc(sizeof(ll_node)); 
    current->v = v; 
    return backup; 
} 

ll_node_ptr push_head(ll_node_ptr head, int v) 
{ 
    ll_node_ptr new_head = (ll_node_ptr)malloc(sizeof(ll_node)); 
    new_head->v = v; 
    new_head->next = head; 
    return new_head; 
} 

ll_node_ptr pop_el(ll_node_ptr head, int el) 
{ 
    ll_node_ptr backup = head; 
    ll_node_ptr current = head; 
    ll_node_ptr previous = NULL; 
    int found = 0; 

    while(current != NULL && !found) 
    { 
     if(current->v == el) 
     { 
      if(previous == NULL) 
      { 
       backup = current->next; 
       free(current); 
       current = backup; 
       previous = current; 
      } 
      else 
      { 
       previous->next = current ->next; 
       free(current); 
       current = current->next; 
      } 

      found = 1; 
     } 
     else 
     { 
      previous = current; 
      current = current->next; 
     } 
    } 
    return backup; 
} 

void print(ll_node_ptr head) 
{ 
    ll_node_ptr current = head; 
    printf("%d\n", head->v); 
    while(current->next != NULL) 
    { 
     current = current->next; 
     printf("%d\n", current->v); 
    } 
} 

int isPair(int n) 
{ 
    return ((n % 2) == 0); 
} 

int main(int argc, char** argv) 
{ 
    int n = 1; 
    ll_node_ptr list = NULL; 
    while(n != 0) 
    { 
     scanf("%d", &n); 

     if(n < 0) 
     { 
      list = pop_el(list, -n); 
     } 
     else 
     { 
      if(isPair(n)) 
      { 
       list = push_head(list, n); 
      } 
      else 
      { 
       list = push_tail(list, n); 
      } 

     } 


    } 

    print(list); 
    //should free the list 
    return 0; 
} 

ce qui est le cas de test (passé en entrée) je teste le code contre:

4 
5 
2 
-4 
-5 
-3 
9 
2 
0 

qui devrait produire la sortie suivante:

2 
2 
9 

des indices?

Answer 1

Tout d'abord, je suggère d'utiliser des fonctions récursives lorsque vous travaillez avec des listes. C'est beaucoup plus facile à déboguer et à comprendre.

Je pense que je l'ai trouvé un problème avec votre fonction push_tail:

current->next = (ll_node_ptr) malloc(sizeof(ll_node)); 
current->v = v; 

Vous allouez de la mémoire pour current-> suivante mais attribuez la valeur au noeud courant. Cela devrait être

current->next = (ll_node_ptr) malloc(sizeof(ll_node)); 
current->next->v = v; 
current->next->next = NULL; 

Peut-être que cela a quelque chose à voir avec votre problème.

Answer 2

Votre problème immédiat peut être résolu en fixant la fonction push_tail(), comme indiqué par @Vitek. Le code d'origine non seulement stocké la valeur dans le mauvais nœud, mais a également échoué à définir le champ next du nœud de queue nouvellement attribué à NULL. Il existe un autre problème dans cette fonction: les fonctions push_head() et push_tail() doivent créer et renvoyer un pointeur de nœud lorsqu'il est appelé avec un pointeur NULLhead. La fonction push_head() d'origine le fait, mais la fonction push_tail() ne le fait pas. Si le premier numéro entré par l'utilisateur est impair, le premier noeud est ajouté à la liste via la fonction push_tail(), ce qui conduit à un comportement indéfini (probablement un défaut de segmentation).

Plus important encore, vous devriez travailler sur la simplification de votre code. Cela rendra l'écriture plus facile, et plus facile à déboguer.Par exemple, votre fonction print() peut être réduite à trois lignes:

void print(ll_node_ptr current) 
{ 
    while(current) { 
     printf("%d\n", current->v); 
     current = current->next; 
    } 
} 

Il y a plusieurs choses qui peuvent être faites pour améliorer la fonction push_tail(). Voici une nouvelle version:

ll_node_ptr push_tail(ll_node_ptr head, int v) 
{ 
    ll_node_ptr current = head; 
    ll_node_ptr prev = NULL; 
    ll_node_ptr tail = malloc(sizeof(ll_node)); 

    if (tail == NULL) { 
     fprintf(stderr, "Tail node allocation error\n"); 
     exit(EXIT_FAILURE); 
    } 

    tail->v = v; 
    tail->next = NULL; 

    while (current) { 
     prev = current; 
     current = current->next; 
    } 

    if (head) { 
     prev->next = tail; 
    } else { 
     head = tail; 
    } 

    return head; 
} 

Vous n'avez pas besoin de jeter le résultat de malloc(). Opinions differ on whether or not you should do so, mais l'écriture sans la distribution simplifie le code. En outre, vous devez vérifier que malloc() a correctement alloué la mémoire demandée. Ceci est particulièrement important si vous utilisez plutôt realloc(), car ne pas le faire peut entraîner des fuites de mémoire. Après la création du nouveau noeud final, les champs v et next sont immédiatement définis.

Il semble généralement plus simple d'itérer sur une liste chaînée en examinant le nœud current plutôt qu'en regardant le nœud current->next. L'utilisation du pointeur de nœud prev facilite cela. La nouvelle fonction itère sur la liste jusqu'à current == NULL, point prev pointant vers le dernier nœud de la liste. Dans le cas où head a été passé en tant que pointeur NULL (c'est-à-dire, la liste était vide, ce qui peut arriver si le premier nombre entré par l'utilisateur est impair) la boucle d'itération est ignorée, puisque current est initialisée à head. Le code après la boucle définit le champ next du dernier nœud pour pointer vers le nœud de queue nouvellement créé si une liste non vide a été donnée à la fonction, sinon head devient le nouveau nœud de queue. Finalement, head est renvoyé à la fonction appelante.

Il y a beaucoup de simplification qui pourrait être appliquée à la fonction pop_el(), et beaucoup de code superflu. Cette fonction devrait vraiment être complètement repensée. Où avez-vous:

previous->next = current ->next; 
free(current); 
current = current->next; 

Vous avez free d la mémoire référencée par current, alors vous essayez de déréférencer le pointeur vers cette mémoire. Après l'appel à free(), vous ne possédez plus cette mémoire, et c'est undefined behavior. Au lieu de cela que vous voulez:

current = previous->next; 

Mais cela ne compte pas vraiment, parce que found est prochaine série à 1, la boucle se termine, et la fonction return s backup, sans plus d'utilisations de current. Vous devez simplement supprimer l'affectation ci-dessus à current car elle n'est pas nécessaire.

Vous devriez pouvoir utiliser cette information pour améliorer le reste du code dans votre programme. Il y a d'autres problèmes que vous pourriez vouloir examiner. C'est généralement une mauvaise pratique pour les pointeurs - cela ne sert qu'à obscurcir le code et augmente la probabilité d'erreurs de programmation. La spécification que vous avez fournie ne précise pas ce qui doit se produire s'il existe plusieurs nœuds contenant la même valeur, c'est-à-dire, doit-on supprimer un ou tous les nœuds? Et, que faire si le premier numéro entré par l'utilisateur est 0?

Answer 3

Plusieurs choses,

En pop_el,

1.Si previous est NULL, il vous suffit de déplacer votre head ptr vers le nœud suivant. Pour qu'il devienne nouveau head.

if(previous == NULL) 
{ 
    backup = current->next; 
    free(current);  
    //current = backup; ---> Not needed. 
    //previous = current; ---> Not needed. 
    break; //   ---> No need of setting found flag. You can remove it 
} 

2.Dans précédente n'est pas NULL alors vous devez pointer simplement le nœud suivant previous ptr au prochain noeud du noeud current.

else 
{ 
    previous->next = current ->next; 
    free(current);   
    //current = current->next; ---> Not needed. 
    break; //   ---> No need of setting found flag. You can remove it 
} 

3.In push_tail vous allouent la mémoire pour le noeud current->next et dans la ligne suivante vous ajoutez v au noeud courant de v. C'est faux. Vérifiez les points suivants,

ll_node_ptr push_tail(ll_node_ptr head, int v) 
{ 
    ll_node_ptr backup = head; 
    ll_node_ptr current = head; 
    ll_node_ptr new = NULL; // Created new pointer 
    while(current->next != NULL) 
    { 
     current = current->next; 
    } 
    //current->next = (ll_node_ptr) malloc(sizeof(ll_node)); 
    new = (ll_node_ptr) malloc(sizeof(ll_node)); 
    //current->v = v; ----> incorrect. new Value is actually replacing the old value. 
    new->v = v;  // New value is added in the newly created node. 
    new->next = NULL; 
    current->next = new; 
    return backup; 
} 

4.You peut améliorer votre logique print

void print(ll_node_ptr head) 
{ 
    ll_node_ptr current = head; 
    //printf("%d\n", head->v); 
    while(current != NULL) 
    { 
     printf("%d\n", current->v); 
     current = current->next; 
    } 
}