Suppression élément dans liste

Version imprimable

06/12/2005, 15h49
bugmenot

Suppression élément dans liste
Salut à tous,

Voilà je voudrais supprimer un élément dans une liste chainée.

J'ai la structure suivante :
Code:

1 2 3 4 5 6 7 8 typedef struct objet { char * s; /* nom de l'objet */ int x; /* numéro de l'objet pointé */ struct objet * suiv; /* objet suivant */ } Objet; typedef Objet * listeObjet;
J'ai une liste de type listeObjet à laquelle je voudrais supprimer un élément . Par exemple je veux supprimer l'objet ayant pour numéro 5.

Voilà merci de m'aider, car là je galère depuis 2 jours :s[/code]
06/12/2005, 15h52
fearyourself

Citation:

Voilà merci de m'aider, car là je galère depuis 2 jours

Donne ton code qui ne marche pas et on verra pourquoi ça plante...

Jc

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
void supprimer_dans_liste(listeObjet * lO, int x)
/* specif : supprime l'objet x dans la liste lO                             */
{
   listeObjet tmp = *lO;
 
   if((*lO)->som == x)
   {
      (*lO) = (*lO)->suiv;
      free(tmp);
      return;
   }
 
   while(tmp != NULL)
   {
      if(tmp->som == x)
      {
         free(tmp);
         tmp = tmp->suiv;
         return;
      }
      tmp = tmp->suiv;
   }
   return;
}
 
void total_destroy_liste(listeObjet * lO)
/* specif : suppression totale d'une liste                                    */
{
   while((*lO) != NULL)
   {
      free(*lO);
      *lO = (*lO)->suiv;
   }
}

Voilà le total_destroy_liste marche ( je pense ), par contre le supprimer_dans_liste ne marche pas :/

06/12/2005, 16h14
Emmanuel Delahaye

Citation:

Envoyé par bugmenot

Voilà le total_destroy_liste marche ( je pense ), par contre le supprimer_dans_liste ne marche pas :/

Ce sujet a été abordé récemment.

http://www.developpez.net/forums/vie...397113#2397113
06/12/2005, 16h40
fearyourself
Citation:

Ce sujet a été abordé récemment.

http://www.developpez.net/forums/vie...397113#2397113

Pour ne pas relancer la discussion, je ne vais pas reprendre ton code mais juste quelques remarques sur ton code:
- Il ne faut pas faire un free si on utilise après l'élément:
  Code:
  
  1 2 3 4 5 6 7 free(tmp); tmp = tmp->suiv; return; ... free(*lO); *lO = (*lO)->suiv;
  Lorsqu'on veut modifier une liste chaînée (et plus particulièrement le chaînage), il faut soit retourner la liste modifiée, soit passer une double indirection pour modifier (dans le cas nécessaire) le premier élément.
  Lorsque je code une liste chaînée j'ai une préférence avec la première solution (je crois que c'est une question d'habitude), mais elle est trompeuse. On a une tendance à croire que la fonction rend une nouvelle liste chaînée différente, ce qui est faux...
  
  Je te conseille donc la deuxième puisqu'elle est plus claire: on risque de modifier la liste!
Pour tout le reste, regarde le lien d'Emmanuel
Jc

Code:

1
2
3
4
5
6
7
8
 
typedef struct objet {
   char * s; /* nom de l'objet */
   int x; /* numéro de l'objet pointé */
   struct objet * suiv; /* objet suivant */
   } Objet;
 
typedef Objet * listeObjet;

J'ai réussi un total_destroy_liste qui marche :D

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
void total_destroy_liste(listeObjet * lO)
/* specif : suppression totale d'une liste                                    */
{
   listeObjet tmp;
 
   while(*lO != NULL)
   {
      tmp = (*lO)->suiv;
      free(*lO);
      *lO = tmp;
   }
}

Par contre pour supprimer un élément, y'a rien à faire :/[/code]

06/12/2005, 17h19
bugmenot

Meme avec le post précédent et le lien d'emmanuel, je n'y arrive pas :(
06/12/2005, 17h25
fearyourself

L'algorithme serait:

Si c'est le premier élément
Efface le premier élément
Retourne le reste de la liste
Sinon
Chercher l'élément qu'il faut supprimer
Le retirer
Retourner la liste modifiée

Ex:
Liste de départ: A -> B -> C -> D
Suppression de A: On remarque que c'est le premier élément donc on sauvegarde l'adresse de B, on fait un free sur A et on retourne B...

Suppression de C:
On parcourt la liste chaînée jusqu'à B,
on remarque que le prochain est C donc on stocke l'adresse de C dans une variable temporaire, on change le chaînage de B pour qu'il pointe vers D et on fait un free sur C,
on retourne l'adresse A qui est le début de la liste...

Essaie avec toutes ces infos...

Code:

1
2
3
4
5
6
7
typedef struct objet {
   char * s; /* nom de l'objet */
   int x; /* numéro de l'objet pointé */
   struct objet * suiv; /* objet suivant */
   } Objet;
 
typedef Objet * listeObjet;

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
listeObjet supprimer_dans_liste(listeObjet lO, int x)
/* specif : supprime le sommet x dans la liste lO                             */
{
   listeObjet tmp = lO, tmp2, deb = lO;
 
   if(lO->som == x)
   {
      tmp = lO->suiv;
      free(lO);
      return tmp;
   }
 
   while(tmp->suiv != NULL && tmp->suiv->som != x)
   {
      tmp = tmp->suiv;
   }
   if(tmp->suiv->som == x)
   {
      tmp2 = tmp->suiv;
      tmp = tmp->suiv->suiv;
      free(tmp2);
   }
   return deb;
}

Qui ne marche toujours pas :cry:

Lorsqu'on travaille avec des pointeurs il ne faut pas oublier les tests de base...

Voici ton code commente:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
listeObjet supprimer_dans_liste(listeObjet lO, int x)
/* specif : supprime le sommet x dans la liste lO                             */
{
   //fy: pas besoin de deb, tu as toujours l0...
   listeObjet tmp = lO, tmp2, deb = lO;
 
    //fearyourself: il faut commencer par tester si l0 == NULL
    //si c'est le cas, on retourne NULL...
 
   //fy: Cette partie est juste sauf que tu ne desalloue pas s (nom de l'objet)
   //fy: Comment est-ce que tu alloue ces chaines de caracteres?
   //fy: Pourquoi som? t'avais x dans ta structure, t'as change ta structure?
   if(lO->som == x)
   {
      tmp = lO->suiv;
      free(lO);
      return tmp;
   }
 
   //fy: Je suis d'accord sur cette boucle
   while(tmp->suiv != NULL && tmp->suiv->som != x)
   {
      tmp = tmp->suiv;
   }
 
   //fy: Il faut tester tmp->suiv!=NULL D'ABORD!!!
   if(tmp->suiv->som == x)
   {
      tmp2 = tmp->suiv;
 
      //fy: mauvaise affectation des liens, c'est tmp->suiv que tu veux changer...
      tmp = tmp->suiv->suiv;
 
      //fy: meme remarque pour tmp2->s...
      free(tmp2);
   }
 
   //retourne juste l0....
   return deb;
}

Oui j'ai changé la structure, j'ai un char au lieu d'un char * :

Code:

1
2
3
4
5
6
7
8
 
typedef struct objet {
   char c; /* nom de l'objet */
   int x; /* numéro de l'objet pointé */
   struct objet * suiv; /* objet suivant */
   } Objet;
 
typedef Objet * listeObjet;

Par contre MERCI pour ton aide, j'ai enfin compris, et CA MARCHE, voilà :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
listeObjet supprimer_dans_liste(listeObjet lO, int x)
/* specif : supprime le sommet x dans la liste lO                             */
{
   listeObjet tmp = lO, tmp2;
 
   if(lO == NULL) return NULL;   
 
   if(lO->x == x)
   {
      tmp = lO->suiv;
      free(lO);
      return tmp;
   }
 
   while(tmp->suiv != NULL && tmp->suiv->x != x)
   {
      tmp = tmp->suiv;
   }
   if(tmp->suiv != NULL && tmp->suiv->x == x)
   {
      tmp2 = tmp->suiv;
      tmp->suiv = tmp->suiv->suiv;
      free(tmp2);
   }
   return lO;
}

ENCORE UN GRAND MERCI fearyourself !

Pour mon total_destroy_liste, ca peut aller tu crois ?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
void total_destroy_liste(listeObjet * lO)
/* specif : suppression totale d'une liste                                    */
{
   listeObjet tmp;
 
   while(*lO != NULL)
   {
      tmp = (*lO)->suiv;
      free(*lO);
      *lO = tmp;
   }
}

06/12/2005, 19h32
fearyourself
Citation:

CA MARCHE

Je suis d'accord mais tu peux simplifier ce test:
Code:

1 2 if(tmp->suiv != NULL && tmp->suiv->x == x)
en
Code:

1 2 if(tmp->suiv != NULL)
parce que: si tu sors de ta boucle, soit tmp->suiv==NULL et donc on est a la fin de la liste, soit tmp->suiv->x == x...

Si tmp->suiv!=NULL alors forcement tmp->suiv->x==x!

Sinon rajoute quelques commentaires pour que tu te souviennes de tout ca la prochaine fois et ca me semble bien...

Citation:

Pour mon total_destroy_liste, ca peut aller tu crois ?

Oui c'est bien

Citation:

ENCORE UN GRAND MERCI fearyourself !

De rien mais de toute facon c'est toi qui a fait le boulot, felicitations! ;-)
06/12/2005, 19h52
bugmenot

Et en plus t'es modeste :wink:

Allé bonne soirée, merci encore :p