Discussion :

[lyes312]

bonjour,
j'aimerais savoir si on peut faire des listes chainées sans faire intervenir des pointeur juste avec les classes.

merci d'avance pour vos réponses éventuelles.

[droggo]

Koe,

Par principe même, on passe d'un chaînon à l'autre avec un pointeur.

[lyes312]

oki.
Je demande ça parce que j'ai un examen demain ou les listes sont au programme mais pas les pointeurs.
C'est un truc bizaroïde ça !

[Tux++]

Bonjour,

oui les listes chainées sans pointeurs existent mais ce ne sont plus des listes "chainées" en tant que telles.

Elles sont utilisées pour la création d'OS par exemple dans les files de processus, quand le moins octet de mémoire est important

voici la déclaration courante:

Code :

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

1
2
3
4
type liste = record
                     tab: array[1..MAX] of integer;
                     p : 0..MAX;
                end;

p est la longueur de la liste et les éléments sont en ordre inverse

note que ce type d’implémentation convient mieux si le type abstrait emploie des procédures qui modifient la liste, car alors il n’est pas nécessaire de recopier les tableaux

c'est en fait l'implémentation des listes qu'utilsent les piles

[lyes312]

merci pour ta réponse.

sinon je voit pas trop pourquoi tu parle d'ordre inversé !

[Tux++]

parce que tu dois commencer à remplir à MAX et pas à 1

Comme ça, ca respecte le principe des listes chainées, le dernier élement ajouté est devant le reste de la liste sans devoir bouger tous les autres élements

[droggo]

Hei,

Bonjour,

oui les listes chainées sans pointeurs existent mais ce ne sont plus des listes "chainées" en tant que telles.

Elles sont utilisées pour la création d'OS par exemple dans les files de processus, quand le moins octet de mémoire est important

voici la déclaration courante:

Code :

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

1
2
3
4
type liste = record
                     tab: array[1..MAX] of integer;
                     p : 0..MAX;
                end;

p est la longueur de la liste et les éléments sont en ordre inverse

note que ce type d’implémentation convient mieux si le type abstrait emploie des procédures qui modifient la liste, car alors il n’est pas nécessaire de recopier les tableaux

c'est en fait l'implémentation des listes qu'utilsent les piles

Je me refuse qu'on appelle ça une liste chaînée, alors que c'est un vulgaire tableau qu'on utilise un tableau de manière un peu particulière, comme une file, c'est tout.
Et on y retrouve les inconvénients des tableaux (insertion, suppression longues) sans les avantages des listes chaînées (insertion, suppression rapides), mais qui ne sont pas sans inconvénients non plus, certes.

parce que tu dois commencer à remplir à MAX et pas à 1

Comme ça, ca respecte le principe des listes chainées, le dernier élement ajouté est devant le reste de la liste sans devoir bouger tous les autres élements

Dans une liste chaînée, on ajoute aussi rapidement en tête qu'en queue de liste.
D'ailleurs, une liste chaînée est généralement implémentée avec les 2 possibilités.

De toute manière, commencer par MAX pour aller à 1, au lieu de 1 à MAX, ne change pas l'utilisation de ta file, sauf que ça la complique, dans le cas ou tu veux accéder au nième élément (un petit calcul d'indice à faire)

[Tux++]

c'est pourtant la deuxième solution d'implémentation des listes

Prenons la représentation des listes chainées...qu'est ce qu'elle dit?

p != nil => (p^.e = head(l) et p^.r = tail(l))
p = nil ssi l = nil


En quoi la représentation en tableau contredit cette représentation? ton head(l) est a[1] et la queue est a[2..MAX], donc comme ceci:

p = long(l) et ∀i ∈ 1..p : a[p − i + 1] = nth(l, i)

où nth(l,i) est le ieme élement de l.


Chaque méthode à ses avantages et ses inconvénients, la plus utilisée est évidemment celle avec les pointeurs mais celle avec les tableaux est indispensable dans un OS par exemple