liste simplement chainée , supprimer un element

liste simplement chainée , supprimer un element - C - Programmation

Marsh Posté le 15-12-2007 à 14:56:09    

Bonjour,
 
Je viens vous demander de l'aide sur un petit problème qui me bloque depuis quelques heures  :D  
 
Valgrind me signale une erreur de lecture sur un de mes free de ma fonction et je n'arrive pas à trouver pourquoi.
Cette fonction desalloue la cellule qui contient le mot que je lui envois en paramètre.
 

Code :
  1. cell *desallocmot(char *mot,cell *motavant)
  2. {
  3. cell *tmp=NULL;
  4. cell *tetedelist=NULL;
  5. cell *First=NULL;
  6. int ok=0;
  9. if(motavant == NULL)
  10.  return NULL;
  11. First=motavant;
  12. while(strcmp(motavant->mot,mot) != 0 )
  13. {
  14.   tmp=motavant;
  15.   motavant=motavant->nxt;
  16.   ok=1;
  17. }
  19. if(ok == 0)
  20. {
  21.  if(motavant != NULL)
  22.  {
  24.   tetedelist=motavant->nxt;
  25.   free(motavant);
  26.   return tetedelist;
  27.  }
  28.  else return NULL;
  29. }
  30. else
  31.  {
  32.   if(motavant->nxt == NULL)
  33.   {
  34.    tmp->nxt=NULL;
  35.    free(motavant);
  36.    return First;
  37.   }
  38.   else
  39.   {
  40.    cell *motasuppr=NULL;
  41.    motasuppr=tmp->nxt;
  42.    tmp->nxt=motasuppr->nxt; 
  43.                                 /*valgrind me signale une erreur ici sur le free */
  44.    free(motasuppr);
  45.    motasuppr=NULL;
  46.    return First;
  47.   }
  48.  }
  49. }


 
Merci d'avance de votre aide  :jap:

Reply

Marsh Posté le 15-12-2007 à 14:56:09   

Reply

Marsh Posté le 16-12-2007 à 00:20:35    

Boaf moi je vois déjà 2 problèmes
1) quand tu cherches ton mot, si le mot n'y est pas tu ne t'arrêtes jamais
2) quand tu libères ton élément contenant le mot, tu ne mets pas à jour le next de l'élément précédent
 
Pour le reste je pige rien à ton algo mais c'est peut-être parce qu'il a trop de commentaires...

int desallocmot(char *mot,cell *motavant)
{
    cell *current;
    cell *previous;
 
    // On se positionne sur la cellule qui contient le mot
    for (previous=NULL, current=motavant; current != NULL && strcmp(mot, current->mot) != 0; previous=current, current=current->next);
 
     // Si on n'a pas trouvé on s'arrête ici
     if (current == NULL)
         return 0;
 
     // S'il y a un précédent (plus d'un élément)
     if (previous != NULL)
          // On met à jour le précédent
          previous->next=current->next;
 
    // On libère l'élément qui contient le mot
    free(current);
 
     // Fonction réussie
     return 1;
}

Message cité 1 fois
Message édité par Sve@r le 16-12-2007 à 00:20:52

---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 16-12-2007 à 12:16:21    

Sve@r a écrit :

Boaf moi je vois déjà 2 problèmes
1) quand tu cherches ton mot, si le mot n'y est pas tu ne t'arrêtes jamais
2) quand tu libères ton élément contenant le mot, tu ne mets pas à jour le next de l'élément précédent
 
Pour le reste je pige rien à ton algo mais c'est peut-être parce qu'il a trop de commentaires...

Pour le 2, en principe si, car il faisait d'une part lors de la recherche: tmp=motavant
et plus tard, avant le free tmp->nxt=motasuppr->nxt.
 
Mais je suis d'accord avec toi, son algo est suffisament boursouflé pour qu'on ne voie pas bien les problemes qu'il peut poser.
 

Code :
  1. int desallocmot(char *mot, cell *liste)
  2. {
  3.   if (mot && liste)
  4.     {
  5.       cell *previous, *current;
  6.    
  7.       /* test avec pour condition d'arret:  
  8.          - fin de liste   
  9.          - cellule ne contenant pas de mot  
  10.          - cellule contenant le mot cherche */
  11.       for (current=liste, previous=NULL;
  12.            current && current->mot && !strcmp(mot, current->mot);
  13.            previous=current, current=current->next) ;
  15.       if (current && current->mot)
  16.         {
  17.           if (previous)
  18.             previous->next=current->next;
  19.           else
  20.             liste = current->next;
  22.           free(current);
  23.           return 1;
  24.         }
  25.     }
  26.   return 0;
  27. }


 
Algo modifiable selon que  
1- on est certain que l'on aura jamais current->mot  a nil (par exemple si c'est un tableau de chars dans la structure cell). On pourrait aussi modifier l'algo pour sauter les cellules qui ont current->mot à nil. Tout dépend du problème concret.
2- on est certain que l'on aura jamais mot et  liste a nil avant l'appel de la fonction
 
Noter que desallocmot ne retire qu'une seule fois le mot de la liste.
S'il peut apparaitre plusieurs fois, et que toutes les occurences doivent en être retirées, il y a la solution bourine d'appeller recursivement desallocmot, et la solution intelligente d'adapter l'algo, et de n'appeller qu'une seule fois la fonction.
 
A+,


Message édité par gilou le 16-12-2007 à 16:49:09

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 16-12-2007 à 13:03:12    

Pour mon algo qui est trop boursouflé je suis d'accord c'est d'ailleurs en partie la raison pour laquelle je me tournais vers vous  ;)  
 
Mais donc on a pas à géré si le mot est en début de liste ou pas ?

Reply

Marsh Posté le 16-12-2007 à 13:35:27    

C'est géré ainsi:
for (current=liste, previous=NULL;
           current && current->mot && !strcmp(mot, current->mot);
Si ton mot est en tete de liste, tu va t'arreter tout de suite, car strcmp(mot, current->mot) renvoie 0.
 
A ce stade, tu as donc current=liste et  previous=NULL
Cas qu'on considere ici:
if (current && current->mot)
        {
          if (previous)
            previous->next=current->next;
mais tu as raison, dans l'algo, il faut remettre liste a l'élément qui suit la tete de liste (et s'il n'y en a pas, la liste vas être mise a nil, qui est ce que l'on veut).
 
et il faudrait donc mieux réécrire le bout correspondant de l'algo comme:

Code :
  1. if (previous)
  2.             previous->next=current->next;
  3.           else
  4.             liste = current->next;
  6.           free(current);


J'ai été mettre a jour mon post précédent à ce sujet.
A+,


Message édité par gilou le 16-12-2007 à 16:59:26

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 16-12-2007 à 13:58:47    

merci beaucoup gilou c'est plus clair dans ma tête maintenant  :jap:

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed