Test d'égalité de listes chainées en C / récursif

Bonjour,

Je devais créer une fonction qui renvoie 1 si deux listes chainées sont égales et 0 si différentes.

J’avais fait un premier code qui marchait pas et j’ai réussi à le changer un peu mais je ne comprends pas pourquoi il ne marchait pas.

voilà le code initial (qui ne fonctionne pas) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int egal(Liste l1, Liste l2)
{
     if((l1==NULL)&&(l2==NULL))
        return 1;
    if((l1==NULL)||(l2==NULL))
        return 0;
    if(l1->contenu!=l2->contenu)
        egal(l1->suivant,l2->suivant);
    return 0;
}

voilà le code qui fonctionne:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int egal(Liste l1, Liste l2)
{
     if((l1==NULL)&&(l2==NULL))
        return 1;
    if((l1==NULL)||(l2==NULL))
        return 0;
    if(l1->contenu!=l2->contenu)
        return 0;
    egal(l1->suivant,l2->suivant);
}

Le premier code me renvoient des 0 lorsqu’ils ne devrait pas : J’ai deux listes chainées qui contiennent toutes les deux 1, 2, 3, 4, 5 et NULL pour la fin de la chaîne.

Merci d’avance !

Il manque un return là… non ?

Ton premier code retourne toujours 0 tant que tu lui passe pas 2 arguments NULL. Et est logiquement faux ^^" Si deux éléments sont différents alors pas besoin de regarder les suivants ^^*

Ton deuxième code fonctionne par chance. Il manque le return devant l’appel de la fonction egale.

1
2
3
4
5
6
7

int egal(Liste l1, Liste l2) {
  if( l1 == NULL || l2 == NULL)
     return l1 == l2;
  if( l1->contenu == l2->contenu )
     return egal(l1->suivant, l2->suivant);
  return 0;
}

Salut,

Outre le return manquant (pour propager la valeur de l’appel récursif), c’est ta condition qui était fausse dans ta première version.

En effet, tu ne cherches normalement à t’attaquer à la suite des listes que si leurs premiers maillons sont égaux, pas s’ils sont différents. S’ils sont différents, tu sais que les listes le sont aussi, et tu renvoies 0.

Ce serait peut-être plus élégant avec des else, même s’ils sont fonctionnellement inutile.

Bonjour,

Merci pour vos réponses, pour le premier code, je me suis trompé lorsque j’ai c/c mes codes, la condition était if( l1->contenu == l2->contenu )

par contre je n’ai pas compris ce que faisait le :

1

return l1==l2;

Salut,

Le l1==l2 retourne true si les deux sont égaux. Or dans ce if, on test si au moins l’un est NULL. Donc cela retourne true si les deux listes sont nulles : elles sont « egales »…  »

D’accord merci beaucoup,

J’ai retesté mon premier code :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int egal(Liste l1, Liste l2)
{
     if((l1==NULL)&&(l2==NULL))
        return 1;
    if((l1==NULL)||(l2==NULL))
        return 0;
    if(l1->contenu==l2->contenu)
        egal(l1->suivant,l2->suivant);
    return 0;
}

et effectivement il marche avec le return devant le égal mais je ne comprends pas encore bien ce que fait

1

return egal(l1->suivant,l2->suivant);

ça return quoi avec mon code du coup ? ça return le résultat de mon prochain appel ?

Oui.

Mais vu ton code, c’est pas super simple à expliquer …

Si les deux listes sont NULL alors, oui elles sont égales. Si seulement 1 des deux est NULL alors elles ne sont pas égales.

Si leur contenu est égal, alors pour savoir si elles sont égales, il faut continuer à l’élément suivant. Donc on retourne le résultat de l’étape suivante.

Sinon, leur contenu diffère et donc, elles ne peuvent pas être égale.

D’accord merci beaucoup et pour le récursivité en général c’est obligatoire le return devant l’appel de la fonction ?

En général, non mais si tu veux faire une fonction qui retourne quelque chose de manière recursif alors oui, c’est obligatoire ^^"

Le principe n’est pas de savoir si c’est obligatoire ou pas.

Le principe c’est de comprendre pourquoi tu dois le faire !

En gros, si une fonction à un type de retour, c’est que ton type de retour doit servir. Soit tu récupères la valeur pour un traitement, soit tu retourne la valeur. Et ce, indépendamment du fait que ta fonction soit récursive ou non.

Ajouté à ça, que si ta fonction doit retourner quelque chose, il faut que dans tous les cas tu retourne une valeur; dans ton cas, ta méthode ne comportait pas de return si tous les if étaient évalués à false.

Mais typiquement si tu as une fonction récursive qui ne retourne rien, void, évidemment aucun return à faire.

Dans ton premier code , tu avais une instruction :

1

egal(l1->suivant,l2->suivant);

en ligne 8.

tu dis : dis moi si les éléments l1->suivant et l2-> suivant sont identiques, mais de toutes façons, je n’écouterai pas la réponse. (pas d’écouteur pour recevoir la réponse de la fonction)

Quand tu appelles une fonction, en principe, c’est parce que tu es intéressé par le code retour de cette fonction, et donc, ça passe par :

1

i = fonct()

ou bien :

1

if fonct() then ...

ou encore

1

return fonct()  

Merci beaucoup !