Discussion :

[devstud]

Bonsoir, j'ai du mal à faire la différence ou à me représenter la différence entre liste récursive et liste itérative.

Sur le cours que j'ai, il est simplement dit que dans une liste itérative, chaque élément permet d'accéder à l'élément suivant, alors que dans une liste récursive, chaque élément permet d'accéder à la liste d'éléments suivants. (Pour moi c'est pareil..).

Il est également dit que dans une LI, on accède plus facilement au i ème élément, tandisque dans une LR il faut tout parcourir, par contre l'avantage des LR, c'est que si on supprime un élément, on ne fait pas de décalages contrairement aux LI.

LI c'est quoi? un tableau?

l'implémentation d'une liste qu'elle soit LI ou LR pour moi c'est ça ;

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
struct Maillon       
{
      Element valeur;
      struct Maillon *suivant;
}Maillon;
 
typedef struct Maillon *Liste_chainee;

Pouvez vous me dire quelle est la différence entre les 2 ça m'échappe vraiment.?

Merci.

[hegros]

LI c'est quoi? un tableau?

Liste itérative ?


Je ne suis pas sûr que c'est la structure qui change mais plutot les fonctions permettant de travailler dessus.

Cela ne doit pas trop t'aider mais bon on fait comme on peut hein

[devstud]

Liste itérative ?


Je ne suis pas sûr que c'est la structure qui change mais plutot les fonctions permettant de travailler dessus.

Cela ne doit pas trop t'aider mais bon on fait comme on peut hein

oui LI pour liste itérative, LC pour récursive, (je suis devenu fainéant même sur l'ordi..)

non ça m'aide ce que tu dis, car sur le cours, les fonctions ne sont pas les mêmes pour les LI et les LC, donc tu as sans doute raison.

Je crois (sans certitude) que pour les LI, on déclare dans la liste, un tableau et une constante pour définir la taille du tableau non ?

merci pour ta réponse.

[Thierry Chappuis]

Pour effectuer des traitements sur une liste chaînée, on peut utiliser des algorithmes itératifs ou des algorithmes récursifs. Mais cela n'influence en rien la liste en tant que structure de donnée.

Thierry

[Trap D]

Si j'ai compris ce qui est dit, la liste itérative est modélisée avec un tableau qui permet un acces direct au donnée (tab[10] qui donne le onzième élément du tableau considéré comme une liste).
la liste récursive est une liste où on accède au premier élément et au reste de la liste, c'est une liste à accès séquentiel, pour arriver au dixième élément, il faut visiter les 9 premiers, attention, et c'est là qu'il y a ambiguité, ce parcours peut se faire de manière itérative ou récursive.

Le vocabulaire (liste itérative ou liste récursive) me parait mal choisi.

[devstud]

Je devrais dire implémentation récursive ou itérative.

Je pense que c'est désormais clair pour moi, j'ai retrouvé mon explication qui me fuyait un peu. Et vos réponses vont dans le même sens.

Voici l'implémentation itérative (ou contigüe) d'une liste ;

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
#define MAX 10
 
struct Maillon       
{
      int tab[MAX];
      int taille;
}Maillon;

Et l'implémentation récursive est la même que celle que j'ai mise là haut.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
struct Maillon       
{
      Element valeur;
      struct Maillon *suivant;
}Maillon;
 
typedef struct Maillon *Liste_chainee;

En fait, en cours, on a manipulé que les listes chaînées et pas l'implémentation contigüe. Mais je fais la différence maintenant, et je pense que c'est ça.

Merci de vos réponses.

[Thierry Chappuis]

Si j'ai compris ce qui est dit, la liste itérative est modélisée avec un tableau qui permet un acces direct au donnée (tab[10] qui donne le onzième élément du tableau considéré comme une liste).
la liste récursive est une liste où on accède au premier élément et au reste de la liste, c'est une liste à accès séquentiel, pour arriver au dixième élément, il faut visiter les 9 premiers, attention, et c'est là qu'il y a ambiguité, ce parcours peut se faire de manière itérative ou récursive.

Le vocabulaire (liste itérative ou liste récursive) me parait mal choisi.

Donc, selon cette terminologie, une liste itérative, c'est un tableau, et une liste récursive, c'est une liste chaînée. C'est ça?

Thierry