IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

 C Discussion :

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


Sujet :

C

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre émérite Avatar de ypcman
    Homme Profil pro
    Retraité codeur !
    Inscrit en
    Janvier 2011
    Messages
    601
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations professionnelles :
    Activité : Retraité codeur !
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Janvier 2011
    Messages : 601
    Par défaut Fct récursive sur une liste chaînée
    Bonjour.
    j'ai une liste chaînée tradi :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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

  2. #2
    Expert confirmé
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    Décembre 2015
    Messages
    1 599
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 62
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Décembre 2015
    Messages : 1 599
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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

  3. #3
    Membre émérite Avatar de ypcman
    Homme Profil pro
    Retraité codeur !
    Inscrit en
    Janvier 2011
    Messages
    601
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations professionnelles :
    Activité : Retraité codeur !
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Janvier 2011
    Messages : 601
    Par défaut
    Brillant !
    merci

  4. #4
    Membre Expert
    Femme Profil pro
    ..
    Inscrit en
    Décembre 2019
    Messages
    667
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 95
    Localisation : Autre

    Informations professionnelles :
    Activité : ..

    Informations forums :
    Inscription : Décembre 2019
    Messages : 667
    Par défaut
    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.

  5. #5
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 835
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 835
    Billets dans le blog
    1
    Par défaut
    Bonjour
    Citation Envoyé par ypcman Voir le message
    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
    Ok, demandé si gentiment...

    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 c : Sélectionner tout - Visualiser dans une fenêtre à part
    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 c : Sélectionner tout - Visualiser dans une fenêtre à part
    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...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  6. #6
    Membre émérite Avatar de ypcman
    Homme Profil pro
    Retraité codeur !
    Inscrit en
    Janvier 2011
    Messages
    601
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations professionnelles :
    Activité : Retraité codeur !
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Janvier 2011
    Messages : 601
    Par défaut
    Merci Sve@r pour toutes ces explications et les potentialités que tu m'ouvres. Bien coder est un art.

  7. #7
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 835
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 835
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par ypcman Voir le message
    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.
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 5
    Dernier message: 31/05/2019, 18h53
  2. Tri rapide sur une liste chaînée
    Par Mckinl3y dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 28/08/2016, 21h24
  3. Réponses: 3
    Dernier message: 15/06/2007, 12h06
  4. select sur une liste chaînée
    Par wtfu dans le forum Langage SQL
    Réponses: 1
    Dernier message: 01/06/2006, 15h30
  5. Réponses: 16
    Dernier message: 19/11/2005, 16h47

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo