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.

[Faiche]

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;

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;

Il y a un problème la.

La deuxieme implémentation est juste, Liste_chainee representant le 1er maillon de la chaine.

La premiere par contre, n'a rien a voir.

Il faudrait, pour avoir la meme liste chainée représentée dans un tableau faire comme ça :

Code :

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

1
2
3
4
5
6
 
struct liste_chainee_it
{
  Element[MAX] valeurs;
  int nb_elt;
}

Et après tu déplaces les valeurs dans le tableau.

[Médinoc]

typedef struct Maillon *Liste_chainee;

Mauvais, ça.
Il faut éviter de dissimuler les pointeurs ainsi, c'est la porte ouverte aux erreurs.

Soit tu renommes ton typedef en PMaillon, soit tu le vires complètement.

[Faiche]

Mauvais, ça.
Il faut éviter de dissimuler les pointeurs ainsi, c'est la porte ouverte aux erreurs.

Soit tu renommes ton typedef en PMaillon, soit tu le vires complètement.

ou alors tu le renomme a la windows, genre

Code :

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

1
2
 
typedef struct Maillon* __PHDLREC;

pour pointeur sur la tete de la liste recursive :p

[koala01]

Salut,

Mauvais, ça.
Il faut éviter de dissimuler les pointeurs ainsi, c'est la porte ouverte aux erreurs.

Soit tu renommes ton typedef en PMaillon, soit tu le vires complètement.

je plussote...

A ceci pres qu'à titre personnel, je le virerai carrément... (sans forcer personne à etre de mon avis)

Si je précise souvent un P ou un ptr devant le nom d'une variable de type pointeur, je ne suis pas du tout persuadé que le seul fait de rajouter un P devant un nom de type représentant un pointeur soit réelement de nature à éviter les problèmes.

Des deux solutions

Code :

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

1
2
3
4
 
typedef Maillon *PListeChainee;
void mafonct(PListeChainee truc);/* en utilisant le pointeur simple*/
void mafonct2(PListeChainee *brol); /* fonction qui prend un pointeur de pointeur */

ou

Code :

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

1
2
3
4
 
/* pas de typedef en tant que pointeur */
void mafonct(Maillon* truc);/* 1ere fonction mais sans utiliser le typedef */
void mafonct2(Maillon** brol);/* deuxieme fonction sans utiliser le typedef */

Je trouve qu'il n'est pas plus facile d'écrire la première que la deuxième, et que la deuxième a, au moins, l'avantage de réciser clairement qu'il s'agit de pointeur (de pointeur), alors que la première, malgré tout, "cache" le fait qu'il s'agit d'un pointeur derrière un nom qui, hormis le P initial ressemble à s'y méprendre à un type personnalisé, et dont le fait de commencer par un P peut très bien passer inaperçu et, finalement, dépend d'une seule ligne, qui, en plus, ne se trouve pas forcément dans le meme fichier...

Bref, cette pratique, meme si je l'accepte (sans l'utiliser à titre personnel), présente l'énorme inconvéniant de donner une chance supplémentaire à la distraction du programmeur de s'exercer...

Et comme le programmeur est avant tout "un humain" et que "l'erreur est humaine"...

Comme d'hab, je présente ici les arguments, le raisonnement qui me font éviter cette pratique... Ils se tiennent selon moi, et il s'agit de mon avis perso... Mais je le partage ...

Si je le présente, c'est, justement, pour permettre une confrontation argumentée et constructive des points de vue .

[Médinoc]

ou alors tu le renomme a la windows, genre

Code :

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

typedef struct Maillon* __PHDLREC;

pour pointeur sur la tete de la liste recursive :p

Ben non, Windows ne renomme pas comme ça.

Par contre, il aiment bien les pointeurs absolument opaques vers des structures qui n'existent pas (et qui en fait, ne sont même pas toujours de vrais pointeurs).

Code :

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

typedef struct HLINKEDLIST__ * HLINKEDLIST;

Ou bien, les vrais pointeurs sur de vraies structures:

Code :

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

1
2
3
4
typedef struct tagMAILLON
{
...
} MAILLON, *PMAILLON;

[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