[Langage C] Liste chainée suppression

[invite88c51880]

Bonjour,
Je travaille actuellement sur les listes chainées en C, cependant je n'arrive pas à supprimer un élément en milieu de liste. Lorsque j'appelle ma fonction, seul un champ de la structure à l'air de disparaitre.
Voici mon code :

t_compte* supprimerElement(t_compte *liste, int val)
{

    if(liste == NULL)
        return NULL;


    if(liste->numeroCompte == val)
    {
        t_compte *tmp = liste->suivant;
        free(liste);
        tmp = supprimerElement(tmp, val);
        return tmp;
    }
    else
    {
        liste->suivant = supprimerElement(liste->suivant, val);
        return liste;
    }
}

Quelqu'un pourrait-il me guider ?
Merci d'avance
-----

[gienas]

Bonjour lilili92 et tout le groupe

Bienvenue sur le forum.

... je n'arrive pas à supprimer un élément en milieu de liste. Lorsque j'appelle ma fonction, seul un champ de la structure à l'air de disparaitre ...

Hum. Pourrais-tu préciser ton véritable problème?

D'après toi, quel est le rôle de la fonction décrite?

Peux-tu aussi compléter/préciser quelles sont les conditions de l'appel de la fonction?

[invite88c51880]

J'ai donc une structure t_compte contenant plusieurs champs. La fonction de suppression est appelée dans un menu proposant plusieurs actions sur la liste chainée.
Pour moi ma fonction devrait au moins supprimer quelque chose or elle ne supprime rien...

[pm42]

Tu ne remets pas les pointeurs là où il faut. Si tu supprimes un élément, le suivant du précédent doit pointer sur le suivant du supprimé.
Et il faut gérer les différents cas notamment celui où on est le 1er de la liste.

Cela peut s'écrire avec une boucle ou récursivement mais ce dernier cas n'apporte pas grand chose en terme de lisibilité et de concision de code.

Typiquement, on garde un pointeur sur l'élément précédent pour pouvoir faire le "raccord" une fois qu'on a supprimé.

[A voir en vidéo sur Futura]

[PA5CAL]

Bonjour

Pour supprimer un élément E_n d'une liste chaînée, il faut :
- parcourir la liste pour trouver l'élément E_n (ici identifié d'après la valeur de numeroCompte),
- indiquer dans l'élément précédent E_n-1 que son élément suivant devient E_n+1 (le suivant de E_n) ou NULL s'il n'y en a pas,
- le cas échéant, si la liste présente également un chaînage arrière, indiquer dans l'élément suivant E_n+1 que son élément précédent devient E_n-1 (le précédent de E_n) ou NULL s'il n'y en a pas,
- si nécessaire, détruire l'élément E_n. Selon la manière dont l'élément a été créé, cela peut consister à libérer la mémoire allouée par sa structure (en incluant les champs alloués séparément sur le tas), ou juste à indiquer qu'il n'existe plus si sa structure fait partie d'un tableau.

D'une part, ton code se contente de libérer la mémoire de l'élément à supprimer sans rien changer au chaînage de la liste. Cela conduit à continuer de pointer sur l'élément censément disparu, lequel reste (au moins partiellement) accessible tant que sa zone de mémoire n'a pas été réutilisée et écrasée par une autre structure.

D'autre part, ton code parcours la liste en utilisant une fonction récursive. Ce n'est pas à proprement parler une erreur, mais j'ai récemment expliqué (c.f. ce commentaire et les suivants) que cette façon de procéder était dangereuse. Il serait grandement préférable de réaliser la récurrence à l'aide d'une boucle de répétition (for ou while).

[invite88c51880]

Bon je pense que je vais aller revoir mon cours sur les listes chainées car je ne comprend pas comment accéder au "précédent"

[pm42]

Ce n'est pas à proprement parler une erreur, mais j'ai récemment expliqué (c.f. ce commentaire et les suivants) que cette façon de procéder était dangereuse.

C'était du nawak à l'époque et ça le reste... Ce n'est pas parce que tu ne maitrises pas une technique que c'est dangereux.
Par exemple, il y a des fonctions récursives dans le noyau Linux qui est connu pour tourner avec une certaine fiabilité.

P.S : et l'algorithme que tu as donné est faux... Il référence un indice négatif dans un cas donné par ex. Tu devrais essayer la récursivité pour ne pas avoir ce genre de problème.

[invite88c51880]

Bon j'ai changé quelques truc, et ça à l'air de fonctionner !

t_compte* supprimerElement(t_compte *liste, int numCompte)
{

    t_compte *courant, *precent;
    courant=liste;
    if(liste == NULL)
        return NULL;


    if(courant->numeroCompte == numCompte)
    {


        precent = courant->suivant;
        free(courant);

        return precent;
    }
    else
    {
        liste->suivant = supprimerElement(liste->suivant, numCompte);
        return liste;
    }
}

Quand j'affiche ma liste chainée après avoir appelée la fonction supprimer, le maillon n'apparait plus !

[invite88c51880]

Ah ça fonctionne que pour certain maillon apparement

[pm42]

Quand j'affiche ma liste chainée après avoir appelée la fonction supprimer, le maillon n'apparait plus !

Ca a l'air pas trop mal en effet. J'ai un peu la flemme de lire en détail vu l'absence de balise CODE et encore plus de tester ceci dit.
Mais l'approche récursive marche bien finalement : si c'est le 1er qu'il faut virer, on renvoie le suivant. Sinon, on remplace le suivant par la liste filtrée moins le 1er...

[invite88c51880]

Voila en fait je peux tout supprimer sauf la tête de liste

t_compte* supprimerElement(t_compte *liste, int numCompte)
{

    t_compte *courant, *precent;
    courant=liste;
    if(liste == NULL)
        return NULL;

    while(courant!=NULL)
    {
        if(courant->numeroCompte == numCompte)
        {
            precent = courant->suivant;
            free(courant);

            return precent;
        }
        else
        {
            liste->suivant = supprimerElement(liste->suivant, numCompte);
            return liste;
        }
    }
}

[pm42]

Voila en fait je peux tout supprimer sauf la tête de liste

Cela dépend de la façon dont tu l'appelles. Tu ne peux pas virer la tête de liste "sur place".
Mais normalement vu vas écrire :

liste = supprimerElement(liste, 12)

Par contre, ton 2nd code me semble faux : le mélange de la boucle et de la récursivité est une mauvaise idée.

[invite88c51880]

Le premier élément de ma liste ne part toujours pas même avec cet appel

[pm42]

Le premier élément de ma liste ne part toujours pas même avec cet appel

Si je prends ton code correct, pas le mélange boucle/récursif, tu vois que si c'est le 1er élément, tu renvoies son suivant. Donc l'erreur doit être ailleurs.

[PA5CAL]

C'était du nawak à l'époque et ça le reste... Ce n'est pas parce que tu ne maitrises pas une technique que c'est dangereux.

C'est plutôt toi qui n'a très clairement pas compris les preuves que j'ai apportées au travers d'exemples parfaitement corrects dans différents langages (Python, C/C++, Javascript). Tu as d'ailleurs été dans l'incapacité d'y apporter le moindre démenti, et j'attends toujours que tu le fasses (on peut toujours rêver) ! Après on pourra en discuter sérieusement.

Apporte des preuves de ce que tu avances. Se contenter de dénigrer les contributeurs n'est pas un argument techniquement recevable.

Par exemple, il y a des fonctions récursives dans le noyau Linux qui est connu pour tourner avec une certaine fiabilité.

Là, tu pars du principe que si quelques exemples réalisés dans des situations très particulières ont pu fonctionner, alors il n'y a pas de problème.

Tu devrais pourtant te rendre compte que ton raisonnement est aberrant : si tu remplis un seau avec de l'eau de mer et que tu n'y trouves pas de poisson, tu ne peux pas en déduire qu'il n'y a pas de poisson dans la mer.

Pour que la fonction récursive ne pose pas de problème, il faut pouvoir garantir :
- soit que le compilateur ou l'interpréteur linéarise la fonction récursive,
- soit que le code limite la profondeur des appels à la quantité de mémoire effectivement disponible sur la pile.
Or, dans les cas de figure discutés, absolument rien n'a été apporté sur la façon de garantir l'une ou l'autre de ces conditions. Bien au contraire, j'ai démontré qu'il est toujours possible d'atteindre un niveau de complexité où l'outils de développement n'est plus capable de linéariser la fonction récursive, et qu'on atteignait toujours un volume de données traitées qui faisait déborder la pile.

P.S : et l'algorithme que tu as donné est faux... Il référence un indice négatif dans un cas donné par ex. Tu devrais essayer la récursivité pour ne pas avoir ce genre de problème.

Ne te fais pas plus bête que tu ne l'es. Ici on ne traite pas un tableau et si je fais référence à un indice c'est juste par soucis de vulgarisation. Un élément inexistant ne doit simplement pas traité.


Exemple de code dans le cas d'un simple chaînage avant :

// Efface tous les éléments de la liste tels que numeroCompte==val
// Retourne le nouveau pointeur sur le début de la liste
t_compte* supprimeElements(t_compte* liste, int val)
{
  t_compte* premier = liste;
  t_compte* precedent = NULL;
  t_compte* element = liste;

  while( element != NULL ) {
    if( element->numeroCompte == val) {
      if( precedent == NULL )
        premier = element->suivant;
      else
        precedent->suivant = element->suivant;
      t_compte* suivant = element->suivant;
      free(element);
      element = suivant;
    } else {
      precedent = element;
      element = element->suivant;
    }
  }
  return premier;
}

(non testé)

L'appel doit être du type :

liste = supprimeElements(liste, val);

[invite88c51880]

si j'enleve le mélange boucle/récursif, plus rien ne se supprime par contre

[invite88c51880]

Le code fonctionne bien PA5CAL, sauf si le compte que je souhaite supprimer est le premier de la liste

[pm42]

C'est plutôt toi qui n'a très clairement pas compris les preuves que j'ai apportées au travers d'exemples parfaitement corrects dans différents langages (Python, C/C++, Javascript). Tu as d'ailleurs été dans l'incapacité d'y apporter le moindre démenti, et j'attends toujours que tu le fasses (on peut toujours rêver) ! Après on pourra en discuter sérieusement.

J'ai donné des arguments, démonté ton exemple hilarant où gcc se plantait alors qu'il optimisait la boucle, cité plusieurs exemples dont Erlang dans les télécoms, le noyau Linux.
Je pourrais également citer les cours de programmation du MIT qui sont basés sur le récursivité ou te demander de nous parcourir un arbre sans utiliser cette technique.
Mince, je l'ai déjà fait et je n'ai pas eu de réponse.

Je n'y peux rien si ton niveau en programmation est "juste moyen" et que tu refuses d'accepter qu'il y a des choses que tu ne connais pas et que tu te contentes de pondre des tartines sans aucune référence.

Le truc typique est le

"Bien au contraire, j'ai démontré"

Mais oui, tu as démontré des trucs avec 3 phrases sur le forum que les concepteurs de Lisp, Linux, le compilo Java, Scala, Erlang ne savent pas.
Dunning-Kruger... en dessous de la moyenne et venant frimer quand il est confronté au niveau au dessus.

[PA5CAL]

Le code fonctionne bien PA5CAL, sauf si le compte que je souhaite supprimer est le premier de la liste

Ce n'est pas ce que ton premier code suggérait...

Dans ce cas, il suffit de quitter la fonction après la première suppression :

// Efface le premier élément de la liste tels que numeroCompte==val
// Retourne le nouveau pointeur sur le début de la liste
t_compte* supprimeElements(t_compte* liste, int val)
{
  t_compte* premier = liste;
  t_compte* precedent = NULL;
  t_compte* element = liste;

  while( element != NULL ) {
    if( element->numeroCompte == val) {
      if( precedent == NULL )
        premier = element->suivant;
      else
        precedent->suivant = element->suivant;
      free(element);
      return premier;
    }
    precedent = element;
    element = element->suivant;
  }
  return premier;
}

(non testé)

[invite88c51880]

Oui désolé quand je disais en milieu de chaîne j'entendais partout dans la chaîne, j'aurais du mieux m'exprimer

[PA5CAL]

J'ai donné des arguments, démonté ton exemple hilarant où gcc se plantait alors qu'il optimisait la boucle, cité plusieurs exemples dont Erlang dans les télécoms, le noyau Linux.

Tu n'as rien démonté du tout.

Je t'ai montré que quelle que soit le niveau d'optimisation choisi, on pouvait trouver un exemple correct généré par GCC qui plantait le programme. Si tu es capable, j'attends toujours que tu nous montres ta « méthode que je ne maîtrise pas » qui empêcherait que cela arrive.

Je pourrais également citer les cours de programmation du MIT qui sont basés sur le récursivité ou te demander de nous parcourir un arbre sans utiliser cette technique. Mince, je l'ai déjà fait et je n'ai pas eu de réponse.

Et moi je peux citer des cas de fonctions récurrentes que j'ai codées et pour lesquelles je peux garantir qu'elles de feront pas déborder la pile.

Il n'est reste pas moins que rien ne garantit que les exemples rapportés par les demandeurs sur ce forum puissent être sûrs.

Comme je l'ai dit, rapporter un cas qui marche n'empêche pas le problème d'exister.

Je n'y peux rien si ton niveau en programmation est "juste moyen" et que tu refuses d'accepter qu'il y a des choses que tu ne connais pas et que tu te contentes de pondre des tartines sans aucune référence.

Tu es fort pour citer des références sans utilité et pour prétendre savoir ce que les autres ignorent sans les connaître. Tu ne te rends même pas compte que c'est toi qui refuses d'accepter qu'il y a des choses que tu ne connais pas.

Le truc typique est le
"Bien au contraire, j'ai démontré"
Mais oui, tu as démontré des trucs avec 3 phrases sur le forum que les concepteurs de Lisp, Linux, le compilo Java, Scala, Erlang ne savent pas.
Dunning-Kruger... en dessous de la moyenne et venant frimer quand il est confronté au niveau au dessus.

Tu délires. En quoi ce que j'ai démontré aurait un quelconque rapport avec les concepteurs de Lisp, Linux, le compilo Java, Scala, Erlang ... ?

Tu ne sais plus quoi inventer.

Puisque tu prétends avoir quelques compétences en la manière, contente-toi de donner à lilili92 une fonction récursive qui ne puisse jamais planter (ce qui, selon moi, n'est pas impossible dans l'absolu, mais qui compliquerait assez les choses).

[invite88c51880]

En tout cas merci à vous, ça marche niquel maintenant, je vais essayer de voir comment trier la liste selon plusieurs critères maintenant

[pm42]

Tu délires. En quoi ce que j'ai démontré aurait un quelconque rapport avec les concepteurs de Lisp, Linux, le compilo Java, Scala, Erlang ... ?

Ils utilisent tous massivement la récursivité. Je peux te donner les coordonnées de certains pour que tu leur expliques ce que tu as compris et qu'eux ignorent.
Je peux aussi te mettre en contact avec Stallman qui l'utilise aussi massivement.

Je t'ai montré que quelle que soit le niveau d'optimisation choisi, on pouvait trouver un exemple correct généré par GCC qui plantait le programme.

C'est vrai avec toutes les techniques de programmation...

Je remarque aussi que tu ne réponds jamais aux questions : programme moi un parcours d'arbre sans récursivité...
Bon, je te laisse à ton ignorance.

[PA5CAL]

Ils utilisent tous massivement la récursivité.

Mais moi aussi j'utilise la récursivité, à l'occasion, dans des contextes de développement strictement contrôlés.

Cela n'empêche pas, comme je l'affirme, que l'emploi des fonctions récursives soit dangereux, d'une manière générale mais plus particulièrement dans les cas des demandes que nous traitons sur ce forum, qui nous sont soumises par des débutants.

C'est vrai avec toutes les techniques de programmation...

C'est l'une des principales raisons pour lesquelles il est dangereux d'employer des fonctions récursives : pour un code donné, on ne peut pas garantir que le code sera généré de façon assez intelligente pour éviter le débordement de pile.

Je remarque aussi que tu ne réponds jamais aux questions : programme moi un parcours d'arbre sans récursivité...
Bon, je te laisse à ton ignorance.

Et moi je remarque que tu réponds aux questions par d'autres questions ayant peu de rapport avec le sujet. Tu ignores ce que j'ignores, et tu n'as visiblement pas d'autre argument que l'invective.

[PA5CAL]

Et pour répondre à ta question hors sujet, je sais faire, depuis le début des années 80, à une époque où l'on ne pouvait justement pas se permettre d'utiliser de simples fonctions récursives par manque de mémoire et d'absence de dispositif matériel de protection de la pile. On utilisait un tableau (éventuellement extensible) stockant les indices des branches à chaque niveau de l'arbre, et un pointeur parcourant ce tableau. Ainsi, on pouvait par exemple parcourir, sans fonction récursive, un arbre binaire contenant jusqu'à 1024 niveaux avec seulement 130 octets de mémoire.

Mieux vaut avoir de l'expérience qu'être prétentieux.

[pm42]

Et pour répondre à ta question hors sujet, je sais faire, depuis le début des années 80, à une époque où l'on ne pouvait justement pas se permettre d'utiliser de simples fonctions récursives par manque de mémoire et d'absence de dispositif matériel de protection de la pile. On utilisait un tableau (éventuellement extensible) stockant les indices des branches à chaque niveau de l'arbre, et un pointeur parcourant ce tableau. Ainsi, on pouvait par exemple parcourir, sans fonction récursive, un arbre binaire contenant jusqu'à 1024 niveaux avec seulement 130 octets de mémoire.

C'est une technique de derécursification, pas la seule, pas forcément la meilleure.
Ecris nous un parcours d'arbre XML par avec ça et ensuite récursivement qu'on regarde le code.

Sinon on pouvait parfaitement faire du récursif bien avant les années 80. L'informatique ne se limite pas au PC sous DOS avec 64ko de pile. Ce qui d'ailleurs est suffisant pour traiter 1024 niveaux de profondeur récursivement. Mais on avait déjà des machines largement plus puissantes notamment des stations de travail. Et des machines Lisp très utilisées par le MIT et le DoD.

Mais comme je le disais, ton expérience est très, très limitée et tu crois que tu "démontres" des choses contraires aux pratiques des gens les plus reconnus de la profession. Donc coté prétention, tu devrais éviter de donner des leçons.

Et ce coup ci, c'est la dernière réponse. Je te laisse avoir le dernier mot parce que c'est la seule façon pour toi de croire avoir raison.

[PA5CAL]

C'est une technique de derécursification, pas la seule, pas forcément la meilleure.

C'était la meilleure dans le contexte, que tu ne connais pas. Encore une fois, tu parles sans savoir.

Ecris nous un parcours d'arbre XML par avec ça et ensuite récursivement qu'on regarde le code.

Commence donc par nous écrire le code en rapport avec les sujets posés par les demandeurs, ici et dans l'autre fil. Ça serait un début, parce que pour le moment, on n'a pas vu grand chose venant de ta part concernant des fonctions récursives qui ne seraient pas susceptibles de planter le programme.

Sinon on pouvait parfaitement faire du récursif bien avant les années 80. L'informatique ne se limite pas au PC sous DOS avec 64ko de pile. Ce qui d'ailleurs est suffisant pour traiter 1024 niveaux de profondeur récursivement. Mais on avait déjà des machines largement plus puissantes notamment des stations de travail. Et des machines Lisp très utilisées par le MIT et le DoD.

En l'occurrence il s'agissait de programmes sous Apple //. Encore une fois tu parles sans savoir.

Le fait qu'il y ait eu à l'époque de bien plus grosses machines (dont j'ai eu l'occasion de programmer certaines en Lisp) n'empêche pas qu'on devait également programmer les petites. Maintenant, si tu dois acheter un ordinateur à $100000 pour faire un travail réalisable sur une petite machine à $1000 parce que tu penses qu'il faut absolument utiliser des fonctions récursives...

Mais comme je le disais, ton expérience est très, très limitée et tu crois que tu "démontres" des choses contraires aux pratiques des gens les plus reconnus de la profession. Donc coté prétention, tu devrais éviter de donner des leçons.

Tu ne connais pas mon expérience, et tu continues de parler sans savoir, tout en cherchant systématiquement à me discréditer en me rabaissant de façon insultante. Pour en rester à ce niveau de discussion, il est évident que tu manques cruellement d'arguments.

Quant aux leçons, le manque de consistance de tes réponses me laissent penser que j'ai largement les moyens de t'en donner.

Et ce coup ci, c'est la dernière réponse. Je te laisse avoir le dernier mot parce que c'est la seule façon pour toi de croire avoir raison.

Encore une fois, tu quittes la discussion sans avoir apporté (contrairement à moi) un seul élément de réponse concret au sujet posé qui serait conforme à ton point de vue sur cette question des fonctions récurrentes. Mais j'imagine que ce n'est pas près d'arriver.

[Jack]

La réponse ayant été apportée, je ferme vu la tournure prise par la discussion