Fct récursive sur une liste chaînée

Bonjour.
j'ai une liste chaînée tradi :

Code:

---

1 2 3 4

typedef struct liste { int valeur; struct liste *next; } liste;

---

et une fonction récursive qui cherche à supprimer le 1° maillon contenant une valeur donnée et, et c'est la le pb ..., qui doit renvoyer l'adresse de la liste modifiée

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

liste* efface_premiere_occ_rec(liste *l, int e) { if (l == NULL) { return NULL; } else if (l->valeur == e) { liste *l_tmp = l; l = l->next; free(l_tmp); return l; } else { return efface_premiere_occ_rec(l->next, e); } }

---

Or, la fct étant récursive, le pointeur en paramètre se décale d'un maillon jusqu'à trouver le maillon ayant la bonne valeur. Donc je ne vois pas comment récupérer l’adresse du début de la liste....
Merci d'avance à Sve@r et autres dieux de la prog pour leurs éclaircissements :hola:

Bonjour,

Ici, ou bien c'est le premier élément qui disparaît et la fonction retourne une autre liste, ou bien elle retourne la valeur inchangée de liste.
Il faut utiliser cela en replaçant la ligne 10 par:

Code:

---

1 2	l->next = efface_premiere_occ_rec(l->next, e); // reconnecte le suivant qui a pu être modifié return l; // retourner le début de la liste

---

Brillant !
merci

Salut,

C'est à creuser mais la récursion n'étant plus terminale (cf. tail recursion) dans la proposition de @dalfab, il y a maintenant un risque de débordement de la pile.

Bonjour

Citation:

---

Envoyé par ypcman

Or, la fct étant récursive, le pointeur en paramètre se décale d'un maillon jusqu'à trouver le maillon ayant la bonne valeur. Donc je ne vois pas comment récupérer l’adresse du début de la liste....
Merci d'avance à Sve@r et autres dieux de la prog pour leurs éclaircissements :hola:

---

Ok, demandé si gentiment...:lahola:

Donc mes remarques: tout d'abord ta liste chainée n'est pas une liste tradi. Parce que ta structure ce n'est pas une structure de liste mais une structure de maillon (ou de noeud). Et la liste c'est la structure qui tient le premier maillon. Ca peut paraître idiot d'avoir une structure pour un seul élément mais on se rend compte à l'usage que ça simplifie pas mal de soucis (surtout ceux liés à tout changement éventuel de premier élément comme c'est le cas ici). Et ensuite elle peut ensuite avoir d'autres infos si besoin (ex nb d'éléments etc).

Ce qui donne alors

Code:

---

1 2 3 4 5 6 7 8 9

typedef struct s_noeud { int valeur; struct s_noeud* next; } t_noeud;   typedef struct { t_noeud* first; size_t nb; } t_liste;

---

Accessoirement tu remarqueras que les types sont préfixés par un "t_" ce qui permet de les repérer facilement.

De là, non seulement tu ne perdras plus ton début de liste (puisque dans ton main tu auras un t_liste liste qui restera toujours disponible), mais en plus ta fonction qui supprime le premier élément n'a même plus besoin d'être récursive. Car la récursivité, qui a un coût important et qui, comme le dit kaitlyn, est limitée en profondeur de récursion ; n'existe que pour répondre à une nécessité qui rend impossible un algo itératif (ce qui est en général assez rare).

Ainsi ta fonction pourrait devenir

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

t_noeud* efface_premiere_occ_rec(t_liste* l, int e) { if (l == NULL) return NULL; t_noeud* prev; t_noeud* current; for (prev=NULL, current=l->first; current != NULL; prev=current, current=current->next) { // Si on trouve pas on passe au suivant if (current->valeur != e) continue; // Et comme ça on gagne un niveau d'indentation.   // On a trouvé !!! // Si pas premier élément (cas le plus probable donc que je mets toujours en premier) if (prev != NULL) { // Alors le next du précédent récupère le next du courant prev->next=current->next; } else { // On est sur le premier élément l->first=current->next; } free(current); // On libère le noeud l->nb--; // On a un élément de moins return current; // Il faut retourner un truc non NULL } return NULL; }

---

Et voilà comment une structure qu'on n'imaginait pas nécessaire montre soudain son utilité...

Ici un exemple complet de liste chainée classique...

Merci Sve@r pour toutes ces explications et les potentialités que tu m'ouvres. Bien coder est un art.

Citation:

---

Envoyé par ypcman

Bien coder est un art.

---

Il faut essayer de penser "atomicité". Chaque concept encapsulé dans sa structure et possédant des fonctions dédiées.
Par exemple ton noeud contient un int (la data). Perso j'aurais créé une structure "t_data" contenant toutes les datas (donc l'int). Ainsi si demain tu veux rajouter un float, ben tu le rajoutes dans la structure, et dans les fonctions qui manipulent la data et c'est tout, tout le reste s'adapte.

Plus des fonctions elles-aussi atomiques, qui ne font qu'une chose. Ainsi plus elles seront simples plus tu pourras les réutiliser dans différentes situations. C'est un peu comme les légos: des centaines d'objets avec seulement une dizaine de légos aux formes simples.