Forum |  HardWare.fr | News | Articles | PC | Prix | S'identifier | S'inscrire | Aide Recherche
1952 connectés 

  FORUM HardWare.fr
  Programmation
  C

  Suppression d'un maillon d'une liste chainée

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Suppression d'un maillon d'une liste chainée

n°1915201
Duc_onlajo​y
Posté le 14-08-2009 à 16:40:46  profilanswer
 

Bonjour

 

Je viens une fois de plus vers vous car je n'arrive pas à faire une fonction qui supprime un maillon d'une liste chainée.
J'ai essayé de regarder les autre sujets du forum mais malheureusement je n'ai pas très bien compris. D'où ce nouveau sujet.

 

Voici la fonction que j'ai faite :

Code :
  1. s_ListeDePoint *sSupprimerUnMaillonDeLaListe(s_ListeDePoint *psTeteDeListe, double dValeur){
  2.     struct s_ListeDePoint *p = psTeteDeListe;
  3.     while (p->sMaillonSuivant!= NULL){
  4.         /*Si le maillon suivant correspond à celui que l'on veut enlever*/
  5.         if((fabs(p->sMaillonSuivant->dX-dValeur))<DBL_EPSILON){
  6.                 /*on change le pointeur de l'element suivant pour sauter le maillon que l'on veut enlever*/
  7.                 p = p->sMaillonSuivant->sMaillonSuivant;
  8.                 /*on libere l'espace du maillon car il a ete alloue avec un malloc*/
  9.                 free(p->sMaillonSuivant);
  10.                 return psTeteDeListe;
  11.             }
  12.         /*on test le maillon suivant*/
  13.         p = p->sMaillonSuivant;
  14.     }
  15.     return psTeteDeListe;
  16. }
 

Merci beaucoup de vos explications.

Message cité 1 fois
Message édité par Duc_onlajoy le 14-08-2009 à 16:41:16
mood
Publicité
Posté le 14-08-2009 à 16:40:46  profilanswer
 

n°1915209
pataluc
Posté le 14-08-2009 à 16:57:41  profilanswer
 

tu ne peux pas faire un free comme ca, tu pète ta liste... il faut que tu stocke le noeud à supprimer dans une autre variable, et que tu la free ensuite...  
 
ca doit donner qqchose comme ca:

Code :
  1. s_ListeDePoint *sSupprimerUnMaillonDeLaListe(s_ListeDePoint *psTeteDeListe, double dValeur){
  2.    struct s_ListeDePoint *p = psTeteDeListe;
  3.    while (p->sMaillonSuivant!= NULL){
  4.        /*Si le maillon suivant correspond à celui que l'on veut enlever*/
  5.        if((fabs(p->sMaillonSuivant->dX-dValeur))<DBL_EPSILON){
  6.                /*on change le pointeur de l'element suivant pour sauter le maillon que l'on veut enlever*/
  7.                struct s_ListeDePoint *p_del = p->sMaillonSuivant;
  8.                p = p->sMaillonSuivant->sMaillonSuivant;
  9.                /*on libere l'espace du maillon car il a ete alloue avec un malloc*/
  10.                free(p_del);
  11.                return psTeteDeListe;
  12.            }
  13.        /*on test le maillon suivant*/
  14.        p = p->sMaillonSuivant;
  15.    }
  16.    return psTeteDeListe;
  17. }


n°1915286
Sve@r
Posté le 14-08-2009 à 19:23:21  profilanswer
 

Duc_onlajoy a écrit :

Bonjour
 
Je viens une fois de plus vers vous car je n'arrive pas à faire une fonction qui supprime un maillon d'une liste chainée.
J'ai essayé de regarder les autre sujets du forum mais malheureusement je n'ai pas très bien compris. D'où ce nouveau sujet.


Te faut faire un dessin. Une liste chainée, c'est une suite de carrés reliés par un fil (généralement on fait partir le fil du bas du carré pour le faire arriver en haut du carré suivant).
 
Supprimer un maillon, c'est barrer un carré. Mais faut pas perdre le fil. Donc le fil du carré précédent tu le fais pointer sur le carré suivant (sauf si le carré à supprimer est le dernier de la liste) puis une fois que le lien est sauvegardé, tu peux supprimer le carré => voir soluce de Pataloc
 
Toutefois, généralement la fonction qui supprime un maillon on lui fait recevoir le maillon à supprimer et la recherche se fait en amont (plutôt que de faire chercher dans la fonction). c'est plus souple d'emploi. Et comme il peut arriver que le premier élément change (si justement on supprime le premier élément, c'est le second qui prend sa place) on passe aussi la liste elle-même à la fonction.
Ce qui donnerait un truc de ce style

Code :
  1. void supprimeMaillon(s_maillon *principal, s_liste *liste)
  2. {
  3.     // Si on est sur le premier maillon (cas particulier à la con)
  4.     if (principal == liste->premier)
  5.     {
  6.            // on modifie le premier élément
  7.           liste->premier=principal->suivant;
  8.     }
  9.     else
  10.     {
  11.           s_maillon *prec;
  12.          // il faut rechercher le maillon précédent
  13.          for (prec=liste->premier; prec->suivant != principal; prec=prec->suivant);
  14.  
  15.          // on modifie le précédent
  16.           prec->suivant=principal->suivant;
  17.     }
  18.     // Le lien est sauvegardé, on peut libérer le maillon
  19.     free(principal);
  20.    /* Attention, si ton maillon contient des tableaux d'éléments alloués par malloc, faut d'abord libérer les  
  21.        éléments avant de nettoyer le maillon => d'où l'utilité de créer des fonctions de nettoyage associées
  22.         à chaque type => c'est le premier pas vers la programmation objet                                               */
  23. }


Message édité par Sve@r le 14-08-2009 à 19:26:53

---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
n°1915349
Trap D
Posté le 15-08-2009 à 10:07:49  profilanswer
 

Sve@r >> attention quand même, ton code suppose que le maillon soit présent dans la liste, c'est sous-entendu ("la recherche se fait en amont" ) mais pour quelqu'un qui lit les posts en diagonale comme moi, c'est un peu surprenant.
De toute façon, je testerais quand même prec != NULL dans la boucle for et j'en tiendrais compte ensuite dans la modification de prec.
D'autre part, si j'ai bien lu ton code, l'argument liste n'est pas toujours utilisé ainsi : quelquefois/souvent on passe l'adresse du premier élément de la liste alors que toi tu passes l'adresse d'une structure dont un champs passe vers le premier élément de la liste à modifier ce qui est sensiblement différent et il me paraît nécessire de le préciser.

n°1916203
Sve@r
Posté le 18-08-2009 à 14:33:37  profilanswer
 

Trap D a écrit :

Sve@r >> attention quand même, ton code suppose que le maillon soit présent dans la liste, c'est sous-entendu ("la recherche se fait en amont" ) mais pour quelqu'un qui lit les posts en diagonale comme moi, c'est un peu surprenant.


Arf. En effet, je suppose que l'appel de cette fonction ne se fera qu'avec un maillon valide. Mais bon, beaucoup d'autres fonctions présupposent leurs paramètres corrects (strlen, fprintf, etc...)
 

Trap D a écrit :

quelquefois/souvent on passe l'adresse du premier élément de la liste alors que toi tu passes l'adresse d'une structure dont un champs passe vers le premier élément de la liste à modifier ce qui est sensiblement différent et il me paraît nécessire de le préciser.


En fait, ce post a été écrit dans l'esprit d'une autre conversation qu'on a eue Duc_onlajoy et moi où je lui expliquais que je préconisais toujours la création d'une structure permettant de manipuler la liste http://forum.hardware.fr/hfr/Progr [...] 4799_1.htm.
 
Ainsi, cette fonction de suppression suppose effectivement l'existence de ladite structure que Duc_onlajoy connait déjà (mais bien entendu que les autres ne connaissent pas forcément et donc évidemment j'aurais pu/du en reparler...)


Message édité par Sve@r le 18-08-2009 à 14:37:39

---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
n°1916526
Duc_onlajo​y
Posté le 19-08-2009 à 11:32:21  profilanswer
 

Je vous remercie sincèrement de toutes ces explications. J'ai adapté tout ceci (de même que les autres structures des sujets précédents) et tout semble fonctionner.
 
J'aurai néanmoins une autre petite question : comment faire pour être sur qu'il n'y a pas de mémoire que l'on a oublié de libérer. Je pense avoir effectué tout les free nécessaires mais je n'en suis pas certain à 100%. Y a-t-il un moyen sûr de savoir si oute la mémoire a été libérée?
 
Merci beaucoup à vous.

n°1916547
ptitchep
Posté le 19-08-2009 à 11:41:57  profilanswer
 

Valgrind doit pouvoir t'aider. Le meilleur outil reste la rigueur.


---------------
deluser --remove-home ptitchep
n°1916818
Sve@r
Posté le 19-08-2009 à 19:21:14  profilanswer
 

ptitchep a écrit :

Valgrind doit pouvoir t'aider.


Ne fonctionne malheureusement que sous environnement de type unixoide http://doc.ubuntu-fr.org/valgrind (et Duc... n'a pas précisé son environnement)

ptitchep a écrit :

Le meilleur outil reste la rigueur.


Yes  :bounce:  
 


---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
n°1916828
ptitchep
Posté le 19-08-2009 à 20:28:15  profilanswer
 

Sve@r a écrit :


Ne fonctionne malheureusement que sous environnement de type unixoide http://doc.ubuntu-fr.org/valgrind (et Duc... n'a pas précisé son environnement)

Attention Troll

Spoiler :

Quand je parle de rigueur, c'est aussi valable pour le choix de l'OS


Message édité par ptitchep le 19-08-2009 à 20:51:21

---------------
deluser --remove-home ptitchep
n°1916871
ITM
Avatar peint à la main
Posté le 19-08-2009 à 23:32:32  profilanswer
 

Qu'il utilise mpatrol sinon :o


---------------
iteme.free.fr | Mon feedback
mood
Publicité
Posté le 19-08-2009 à 23:32:32  profilanswer
 

n°1916971
Duc_onlajo​y
Posté le 20-08-2009 à 10:37:39  profilanswer
 

Merci bien pour tout ces outils. Même si je pense que la façon dont j'ai conçu le programme est suffisamment rigoureuse et que tout est bien libérée, j'utiliserais ces outil afin de vérifier que je ne me suis pas trompé. On est pas à l'abri d'une erreur de conception :s
 
PS, l'OS change en fonction de la machine que j'utilise Windau.. ou Fedora ou Ubuntu le tout avec un serveur svn pour centraliser tout ça..... j'ai donc le choix


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

  Suppression d'un maillon d'une liste chainée

 

Sujets relatifs
[VBS] Comparaison de dates (résolu)Un tableau de liste chaînée
[ACCESS] Accèder à une liste déroulanteObtenir la liste des appels entre deux break points
[EXCEL] Liste clients -> recherche géographique[Shell] Suppression retours à la ligne/retours chariot
[Suppression]Problème pour récuperer une IPSuppression de doublon Mysql5 (resolu)
PL/SQL : utilisation de variable pour liste de valeur dans requête 
Plus de sujets relatifs à : Suppression d'un maillon d'une liste chainée



Copyright © 1997-2014 Hardware.fr SARL (Signaler un contenu illicite) / Groupe LDLC