liste chainée Fermé

Question

Bonjour,
j'ai rencontré un problème en manipulant les listes chainées avec l'utilisation de la récursivité :
voici un exemple qui consiste à l'ajout des éléments à la fin de liste:    
liste creation(liste l,int valeur) 
{
    noeud *p;
    p=(noeud*)malloc(sizeof(noeud));
    p->val=valeur;
    p->suiv=l;
    return(p);
}

liste ajout_fin(liste l,int valeur)
{   liste tmp=l;
    if (tmp==NULL)
     return(creation(NULL,valeur));

    tmp->suiv=ajout_fin(tmp,valeur);
    return(l);
}

// c'est quoi le problème ??

Marco la baraque · Answer

Bonsoir Maroo,
Euh, moi je vois plusieurs problèmes, certains plus graves que d'autres...

Le premier c'est quand tu fais : tmp->suiv=ajout_fin(tmp,valeur); 
Ici à mon avis, tu as une boucle infinie. En effet, si tu arrives à cet endroit, c'est que tmp n'est pas nul, et tu le passes en paramètre à ta fonction, donc tu vas appeler infiniment cette fonction (donc stack overflow à un moment).

Le second c'est ceci : return(l); . Ici tu dois retourner tmp et non pas l. En effet, tu fais liste tmp=l; , c'est donc une recopie de ta liste l dans une nouvelle liste tmp (et donc non pas juste une copie de l'adresse mémoire de l'objet : c'est un nouvel objet). Autrement dit, si après tu modifies tmp, l n'est pas modifié.

Le troisième, c'est justement d'éviter de faire une recopie à chaque appel de fonction (surtout en récursivité !). Utilise des pointeurs pour passer tes listes et modifie tes listes directement.
Ici, imagine que tu passes une liste contenant plein d'entiers (elle fait 10Mo disons, ce qui est très gros). Dès que tu fais appel à ta fonction, c'est stocké dans la pile (10Mo). Ensuite tu fais une copie de ta liste (tmp), ta pile fait 20Mo.
Tu appelles récursivement ta fonction : tu copies tmp dans la pile pour le passer en paramètres à ta fonction (30Mo). Ensuite tu crées une copie de ta liste (ta pile fait 40Mo), et tu appelles récursivement...

Bref, pour éviter d'augmenter inutilement ta taille de ta pile à chaque appel récursif, utilise des pointeurs.

Cordialement,

Liste chainée

1 réponse

Discussions similaires