Suppression liste chainee

[deyni]

Bonjour,

j'essaye de supprimer tous élements qui sont supérieur à une valeur dans une liste chainee. Mais je n'y parviens pas, j'ai essayé ceci:

typedef struct liste {
      int nombre;
      liste *suivant
}LISTE


LISTE supprimer(LISTE *l, int n) {
       LISTE *temp = l; 
       LISTE *t = l; 

       if (l == NULL) return NULL;

        while (temp->suivant) {

                  if ( t->nombre > n) {
			t->suivant = t->suivant->suivant;
			free(temp->suivant);
			free(temp);
			temp = t;   
		  }
	  t = t->suivant;
	  temp = temp->suivant;
	}
	
	afficher_liste(l);
	supprimer_liste(l);

  }

  return l;

Merci bien.
-----

[Jack]

Ce n'est pourtant pas ton premier exercice sur les listes. Il suffit de prendre un crayon une gomme et du papier et le problème saute aux yeux:

if ( t->nombre > n)

Tu pointes le maiilon à faire sauter avec t ...

t->suivant = t->suivant->suivant;

... et tu fais sauter le suivant au lieu du maillon courant !

[Dlzlogic]

Bonjour,
A mon avis vous ne comprenez pas bien ce qu'est une liste chainée parce que votre structure ne comporte qu'un nombre entier, et c'est tout. Il ne me parait pas évident que ce contexte justifie une liste chainée.
Mettez donc beaucoup de choses dans votre structure, faites un dessin qui représente le lieu de stockage de ce que vous y avez mis, et surtout, la liaison logique entre les pointeurs de la liste et les "suiv".

D'autre part, avez-vous essayé la syntaxe en utilisant "for" au lieu de "while", elle me parait plus claire et surtout plus facile à comprendre.

[Jack]

A mon avis vous ne comprenez pas bien ce qu'est une liste chainée parce que votre structure ne comporte qu'un nombre entier, et c'est tout. Il ne me parait pas évident que ce contexte justifie une liste chainée.

A mon avis c'est un exercice sur les listes chainées.

D'autre part, avez-vous essayé la syntaxe en utilisant "for" au lieu de "while", elle me parait plus claire et surtout plus facile à comprendre.

Algorithmiquement parlant, "Tant qu'on n'est pas en fin de liste" me semble idéal.


A+

[A voir en vidéo sur Futura]

[Dlzlogic]

A mon avis c'est un exercice sur les listes chainées.
Algorithmiquement parlant, "Tant qu'on n'est pas en fin de liste" me semble idéal.
A+

Oui, c'est un exercice, mais ça n'interdit pas d'essayer de comprendre.
Concernant la logique algorithmique, "Tant qu'on n'est pas en fin de liste" me convient parfaitement lorsqu'on veut supprimer tous les éléments de la liste. Mais ici "Pour chaque élément de la liste", me semblerait plus clair pour notre ami.
Un autre conseil que je pourrais lui donner : mettre du commentaire, soit avant un bloc de traitement, soit en bout de ligne. Cela ne présente que des avantages.

[Jack]

Oui, c'est un exercice, mais ça n'interdit pas d'essayer de comprendre.

Qu'il y a-t-il à comprendre? Une liste chainée peut contenir un peu ce que l'on veut. Son problème n'est pas de traiter le contenu, mas de réussir à gérer le contenant. Alors des entiers ou autre chose ...
Rien n'empêche ensuite à l'étape suivante d'utiliser ce type de lise à bon escient.

"Tant qu'on n'est pas en fin de liste" me convient parfaitement lorsqu'on veut supprimer tous les éléments de la liste. Mais ici "Pour chaque élément de la liste", me semblerait plus clair pour notre ami.

C'est une interprétation personnelle que tu fais. Tant qu'on n'est pas en fin de liste veut dire que l'on va traiter tous les éléments de la liste. Le reste n'est que supputations. Je ne vois pas en quoi ça implique que l'on veuille supprimer tous les éléments. C'est du ressort du contenu de la boucle tout ça.

A+

[whoami]

Bonjour,

+1 sur Jack.

Les différentes boucles ont été créées pour gérer diverses situations :

- for : on connaît le nombre de tours à faire
- while : on ne le connaît pas, ni si on doit faire au moins un tour
- do..while : on ne connaît pas le nombre de tours, mais on veut entrer dans la boucle au moins une fois.

Et de manière générale, parcourir une liste chaîne relève du while, puisqu'on ignore si on doit effectivement entrer dans la boucle d'une part, et le nombre de tours à faire d'autre part.

Il est inutile de me préciser qu'on n'est pas tenu à utiliser telle ou telle boucle, et qu'on peut contourner tout ça,je le sais parfaitement. Mais il reste qu'utiliser le type normalement dédié au cas traité rend le code plus logique quant à sa construction, et donc à sa maintenance.

[leon1789]

Dlzillogic, tes commentaires sont assez étranges en effet.
D'une part, deyni a bien défini une liste chaînée, et d'autre part il n'y a rien à ajouter à la structure. Je ne remets pas une couche sur le while ou le for.
Cela dit, ok pour ton conseil sur les commentaires concernant des lignes ou des blocs.

Il faut avant tout comprendre l'objectif pédagogique de l'exercice sans vouloir entraîner deyni sur un autre terrain...
Et pour cela, je crois que Jack pointe très bien le souci de deyni (qui effectivement retire le mauvais élément de la liste en "visant juste un coup trop loin").

[Dlzlogic]

Pour mémoire, en C, le définition d'une boucle for est la suivante
- initialisation
- test
- incrémentation

Il n'y est nulle part question de nombre de tours.

[Jack]

Il n'y est nulle part question de nombre de tours.

Bien sûr.
On peut tout faire avec un for. On peut même voir des choses du genre en C:
for (; ; );
Il parait même qu'on peut faire tout le programme avec un for.
Maintenant, d'un point de vue algorithmique, c'est ce qui s'apparente le plus à un POUR qui est une boucle dont on connait le nombre d'itération.

Il m'arrive également d'utiliser for au lieu de while ou do while car un for ne fait pas que contrôler un compteur en effet. Mais dans le cas du programme ci-dessus, le while me semble cohérent avec le traitement.

Un autre conseil que je pourrais lui donner : mettre du commentaire, soit avant un bloc de traitement, soit en bout de ligne. Cela ne présente que des avantages.

Entièrement d'accord

[Chanur]

Bonjour,

Et de manière générale, parcourir une liste chaîne relève du while, puisqu'on ignore si on doit effectivement entrer dans la boucle d'une part, et le nombre de tours à faire d'autre part.

Il est inutile de me préciser qu'on n'est pas tenu à utiliser telle ou telle boucle, et qu'on peut contourner tout ça,je le sais parfaitement. Mais il reste qu'utiliser le type normalement dédié au cas traité rend le code plus logique quant à sa construction, et donc à sa maintenance.

Mouais ...
Personnellement, pour balayer une boucle chaînée, j'utilise :

for (element=debut; element != NULL; element=element->suivant)

et je n'ai jamais eu l'impression que ça contournait quoi que ce soit, ni que mon code était illogique, ni que ça le rendait plus difficile à maintenir.

Je crois que c'est plus une question d'habitudes de programmation que de logique du langage.

A+

[Dlzlogic]

Bonjour Chanur,
Au moins on est deux à faire comme ça.
Et pour un débutant, je pense que c'est plus clair.

[whoami]

Bonjour,

Ce n'est pas un problème "de logique du langage", mais de logique algorithmique : les différents types de boucles ont été créés pour répondre à des situations claires et précises, autant utiliser la bonne forme pour le cas traité.

[Dlzlogic]

Bonjour,

Ce n'est pas un problème "de logique du langage", mais de logique algorithmique : les différents types de boucles ont été créés pour répondre à des situations claires et précises, autant utiliser la bonne forme pour le cas traité.

En tout cas, c'est pas ce qu'ont écrit BWK&DMR.
Et en matière d'utilisation d'un langage, résultat vaut preuve.

[deyni]

Bonjour,

j'utilise le while, car je le comprends mieux.
Tant que l'element suivant ne pointe pas sur NULL, faire.....
Je ne suis que débutant, je me planterai surêment avec un for.
Une fois, j'ai aussi fait un parcours de liste de manière récursive, ce qui etait difficile et inutile....


Ce n'est pas mon premier exercice sur les listes.^^
Je ne comprends pas votre remarque Jack.

Je crois que j'ai compris mon erreur:

if ( t->nombre > n) {
			t->suivant = t->suivant->suivant;
			free(t->suivant);
			free(t);
			temp = t;   
		  }

par l'instruction t->suivant = t->suivant->suivant, je pense faire:
"élment courant pointe sur l'element suivant du prochain élement".

Merci.

[Jack]

Je ne comprends pas votre remarque Jack.

Quelle remarque, car la discussion est relativement longue?.

Fais-voir ton nouveau code complet pour voir si tu as rectifié le problème.

A+

[deyni]

Bonjour,

je faisais allususion à votre 1ere remarque en réponse à mon message.

[deyni]

Pardon, j'ai oublié le code.

LISTE supprimer(LISTE *l, int n) {
       LISTE *temp = l; 
       LISTE *t = l; 

       if (l == NULL) return NULL;

        while (temp->suivant) {

                  if ( t->nombre > n) {
			t->suivant = t->suivant->suivant;
			free(temp->suivant);
			free(temp);
			temp = t;   
		  }
	  t = t->suivant;
	  temp = temp->suivant;
	}
	
	afficher_liste(l);
	supprimer_liste(l);

  }

  return l;
}

[Jack]

pour moi l'erreur est toujours présente:
quand tu fais t->nombre > n, t pointe un maillon.
Ensuite tu fais t->suivant = t->suivant->suivant; , donc tu fais sauter le maillon suivant, pas celui pointé pat t. Fais un petit dessin avec l'évolution des liens du chainage et tu verras.

A+

[deyni]

Bonjour, j'ai déjà fais un dessin, me je me plante encore!!!

si je faisais:
t = t->suivant->suivant?

[Jack]

je verrai ça plus tard si personne n'intervient car je dois partir.

A+

[deyni]

D'accord merci bien Jack.

[Dlzlogic]

Moi je propose que Chanur fasse un exemple de ce qui devrait normalement se faire, et qui sera certainement plus clair avec un for qu'avec un while, puisque la difficulté de gestion d'une liste chainée est de savoir sur quel élément on travaille, en cas de suppression ou de rajout.

[deyni]

Bonjour,

mais je ne comprends toujours pas où ça bloque pour moi!!
Le code que j'ai donné ne fonctionne pas. Même en mettant les free en commentaire.

Je l'ai fais une fois avec un for, je crois qu'il faut faire:

for (; liste->suivant != NULL; liste = liste->suivant)

mais ça à l'air compliqué. Et je suis sûr que je me suis planté dans le parcours.


Comment faire pour supprimer les élements.

[Dlzlogic]

Si je peux me permettre un conseil, cette opération, ainsi que l'opération d'insertion, est une opération fondamentale.
Ecrivez l'algorithme, indépendamment de tout langage.
Puis écrivez un code en n'utilisant que "if" et "goto".
Puis réécrivez le même code avec "while", puis avec "for", ceci pour la suppression et pour l'insertion.
Tous ces codes doivent tourner.

[Jack]

mais je ne comprends toujours pas où ça bloque pour moi!!
Le code que j'ai donné ne fonctionne pas. Même en mettant les free en commentaire.

En prenant un crayon et du papier c'est pourtant simple. Il faut que tu chaine le champ suivant du PREDECESSEUR de t avec le maillon suivant celui pinté par t.

A+

[Chanur]

Bonjor,

Moi je propose que Chanur fasse un exemple de ce qui devrait normalement se faire, et qui sera certainement plus clair avec un for qu'avec un while, puisque la difficulté de gestion d'une liste chaînée est de savoir sur quel élément on travaille, en cas de suppression ou de rajout.

Au risque de me contredire , dans le cas présent, j'utiliserait un while, de façon à ne faire l'incrémentation que quand on en a besoin. J'utilise plutôt la boucle for quand l'instruction d'incrémentation est fixe.

En effet le cas de la suppression est spécial : on modifie la liste chaînée qu'on est en train de balayer.
Si on supprime l'élément t->suivant en écrivant t->suivant=t->suivant->suivant, il faut rester sur l'element t pour l'itération suivante, pour savoir si on doit supprimer son suivant, puisqu'on ne l'a pas encore testé (il a changé).

Par ailleurs, si on supprime t->suivant, on ne peut pas supprimer le premier élément.

Ça m'embête de publier une solution toute faite, alors que deyni va forcément réussir et que c'est justement le fait de résoudre ce genre de problèmes qui nous fait progresser.

Mais en gros je ferais comme ça :
d'abord une boucle qui supprime le premier element, tant qu'il répond à la condition t->nombre > n
ensuite une boucle dans laquelle soit on supprime t->suivant en affectant t->suivant=t->suivant->suivant, soit on avance en affectant t=t->suivant

Une autre possibilité serait de faire une fonction qui ne supprime qu'un seul élément et sort de la boucle. Dans des cas concrets, ce sera souvent suffisant, quitte à lancer plusieurs fois cette fonction (laquelle devrait évidemment indiquer si elle a effectivement trouvé quelque chose à supprimer). L'intérêt est qu'on est sûr de ne pas réutiliser l’élément qu'on vient de désallouer et qu'on ne se soucie de l'incrémentation que si on n'a rien supprimé.

Attention à bien mémoriser ce dont on se servira avant de faire un free. Par exemple la séquence (message 18) :

free(t);
temp = t;

est mauvaise : temp pointera vers une zone désallouée ...

[Jack]

Je pense égalment qu'une bonne idée d’algorithme est de traiter le ca général dans la boucle et les cas particuliers (liste vide, un seul élément, etc. avant la boucle.

A+

[Dlzlogic]

Petit souvenir personnel, quand j'ai fait mes premières listes chainées, j'ai pris un papier et un crayon, j'ai écrit une colonne de chiffres, disons 1 à 10 et j'ai écrit (toujours papier-crayon) comment supprimer un élément.
Même technique pour l'insertion.

[Chanur]

Petit souvenir personnel, quand j'ai fait mes premières listes chainées, j'ai pris un papier et un crayon, j'ai écrit une colonne de chiffres, disons 1 à 10 et j'ai écrit (toujours papier-crayon) comment supprimer un élément.
Même technique pour l'insertion.

Tiens, moi aussi ... Et d'ailleurs je le fais toujours.