Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
2746 connectés 

  FORUM HardWare.fr
  Programmation
  C

  liste simplement chainée , supprimer un element

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

liste simplement chainée , supprimer un element

n°1658683
verazano
Posté le 15-12-2007 à 14:56:09  profilanswer
 

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;
  7. if(motavant == NULL)
  8.  return NULL;
  9. First=motavant;
  10. while(strcmp(motavant->mot,mot) != 0 )
  11. {
  12.   tmp=motavant;
  13.   motavant=motavant->nxt;
  14.   ok=1;
  15. }
  16. if(ok == 0)
  17. {
  18.  if(motavant != NULL)
  19.  {
  20.   tetedelist=motavant->nxt;
  21.   free(motavant);
  22.   return tetedelist;
  23.  }
  24.  else return NULL;
  25. }
  26. else
  27.  {
  28.   if(motavant->nxt == NULL)
  29.   {
  30.    tmp->nxt=NULL;
  31.    free(motavant);
  32.    return First;
  33.   }
  34.   else
  35.   {
  36.    cell *motasuppr=NULL;
  37.    motasuppr=tmp->nxt;
  38.    tmp->nxt=motasuppr->nxt; 
  39.                                 /*valgrind me signale une erreur ici sur le free */
  40.    free(motasuppr);
  41.    motasuppr=NULL;
  42.    return First;
  43.   }
  44.  }
  45. }


 
Merci d'avance de votre aide  :jap:

mood
Publicité
Posté le 15-12-2007 à 14:56:09  profilanswer
 

n°1658822
Sve@r
Posté le 16-12-2007 à 00:20:35  profilanswer
 

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.
n°1658882
gilou
Modérateur
Modzilla
Posté le 16-12-2007 à 12:16:21  profilanswer
 

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) ;
  14.       if (current && current->mot)
  15.         {
  16.           if (previous)
  17.             previous->next=current->next;
  18.           else
  19.             liste = current->next;
  20.           free(current);
  21.           return 1;
  22.         }
  23.     }
  24.   return 0;
  25. }


 
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é!  --
n°1658907
verazano
Posté le 16-12-2007 à 13:03:12  profilanswer
 

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 ?

n°1658914
gilou
Modérateur
Modzilla
Posté le 16-12-2007 à 13:35:27  profilanswer
 

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;
  5.           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é!  --
n°1658927
verazano
Posté le 16-12-2007 à 13:58:47  profilanswer
 

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


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C

  liste simplement chainée , supprimer un element

 

Sujets relatifs
liste déroulante sur une page web en html pointant vers des fichiers pSupprimer un vector proprement
[Resolu] Probleme liste dynamiquesupprimer un element avec removechild() selon la valeur dans un select
Supprimer un .htaccess[JS] supprimer des valeurs dans un select multiple
Pointeur en argument -> obtention de la taille de l'élément pointé?Initalisation d'une liste déroulante
Centrer une liste de largeur inconnue 
Plus de sujets relatifs à : liste simplement chainée , supprimer un element


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR