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.
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.
Koe,
Par principe même, on passe d'un chaînon à l'autre avec un pointeur.
Si les cons volaient, il ferait nuit à midi.
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 !
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:
p est la longueur de la liste et les éléments sont en ordre inverse
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;
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
Certified Oracle Advanced PL/SQL Professional
Certified Oracle APEX Expert
Certified Oracle SQL Expert
merci pour ta réponse.
sinon je voit pas trop pourquoi tu parle d'ordre inversé !
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
Certified Oracle Advanced PL/SQL Professional
Certified Oracle APEX Expert
Certified Oracle SQL Expert
Hei,
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.
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)
Si les cons volaient, il ferait nuit à midi.
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
Certified Oracle Advanced PL/SQL Professional
Certified Oracle APEX Expert
Certified Oracle SQL Expert
le calcul d'indice est un temps constant O(1), ca ne change strictement rien.
Code : Sélectionner tout - Visualiser dans une fenêtre à part 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)
Et le fait de commencer à MAX est une convention pour ajouter un élément en tête de liste selon le principe des listes chainées.
La file est une implémentation des listes (une possible, il y en a plusieurs), pas l'inverse à mon sens
d'ailleurs en général les files sont implémentées par des B-Arbres ou par des heap
Certified Oracle Advanced PL/SQL Professional
Certified Oracle APEX Expert
Certified Oracle SQL Expert
Fai,
Mais combien de bugs dus à ce genre de petit calcul (genre un + ou - 1 qui manque) ?
Et ça ajoute O(1) au reste.
Mais bon, sur ce plan là, une file implémentée avec un tableau gagne largement.
Que dis-je ? Pour une file, le problème ne se pose pas, on n'est pas censé accéder aléatoirement aux données.
Comme déjà dit, une liste chaînée bien conçue permet d'ajouter/supprimer en tête, en queue, et généralement en n'importe quel point de la liste, pour maintenir un classement, par exemple.
Aurais-je prétendu le contraire ?
Si les cons volaient, il ferait nuit à midi.
j'ai compris ça comme ça...La question concernait les listes chaînées, pas les files.
Le code que j'ai fournit est une implémentation des listes avec réprésentation par tableau qui peut être utilisée pour implémenter une file
En tout les cas, si tu vois une autre implémentation des listes que celle-ci, hormis par pointeurs, je dormirai moins ignorant
Par contre j'aimerai savoir en quoi cette réprésentation te choque pour appeler cela une liste (hors complexité plus ou moins efficaces pour certaines fonctions)
en fait, mieux que mes mots, voilà mon point de vue : http://fr.wikipedia.org/wiki/Liste_(...Types_de_liste
Certified Oracle Advanced PL/SQL Professional
Certified Oracle APEX Expert
Certified Oracle SQL Expert
Jai,
Ce qui confirme mon point de vue pour "liste chaînée" : ça ne s'implémente pas avec un tableau, mais avec des pointeurs. et la question porte bien sur "j'aimerais savoir si on peut faire des listes chainées"
Je ne suis pas choqué de l'appeler une liste, mais de l'appeler une liste chaînée.
PS : tout au long des messages, j'ai parlé de file pour ton implémentation, alors que je pensais pile, et LIFO, pour être plus précis.
Si les cons volaient, il ferait nuit à midi.
Salut Lyes
Et on peux pas faire avec la POO un objet qu'on appelle CObjet par exemple avec un attribut CObjet pour aller vers le suivant ?
Et après on fait une procédure de type :
Je sais pas si je suis très clair.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10 Courant : Cobjet; begin Courant := PremierObjet; while ( i < Max ) begin { Ce qu'on veut faire avec } Courant := Courant.getsuivant; end;
@droggo: et moi j'ai parlé de listes chainées au lieu de lsites dans certains message, conversation de sourd, on est en fait d'accord fin d'examens quand tu me tiens
Il n'existe en effet pas de listes chainées autre que liste avec pointeurs, l'implémentation que j'ai donné est une liste LIFO comme le dit droggo souvent utilisée pour les piles, et parler de liste chainée est un abus de langage
Certified Oracle Advanced PL/SQL Professional
Certified Oracle APEX Expert
Certified Oracle SQL Expert
Bonjour !
Dans un tableau statique donné, rien n'empêche de créer une liste chaînée avec les indices des éléments (comme dans une FAT) :
Voilà, je viens de créer une liste chaînée sans aucun pointeur.
Code X : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 +----- Indice dans le tableau | +-------- Indice de l'élément suivant | | 01 | Elément 01 | 03 02 | Elément 02 | 15 03 | Elément 03 | 06 04 | Elément 04 | 05 | Elément 05 | 06 | Elément 06 | 13 07 | Elément 07 | 08 | Elément 08 | 09 | Elément 09 | 10 | Elément 10 | 11 | Elément 11 | 12 | Elément 12 | 13 | Elément 13 | 02 14 | Elément 14 | 15 | Elément 15 | 00 <---- Fin de liste 16 | Elément 16 |
Règles du forum
Cours et tutoriels Pascal, Delphi, Lazarus et Assembleur
Avant de poser une question, consultez les FAQ Pascal, Delphi, Lazarus et Assembleur
Mes tutoriels et sources Pascal
Le problème en ce bas monde est que les imbéciles sont sûrs d'eux et fiers comme des coqs de basse cour, alors que les gens intelligents sont emplis de doute. [Bertrand Russell]
La tolérance atteindra un tel niveau que les personnes intelligentes seront interdites de toute réflexion afin de ne pas offenser les imbéciles. [Fiodor Mikhaïlovitch Dostoïevski]
Hia,
Pour Alcatîz : c'est là encore un abus de langage.
Tu utilises un tableau pour simuler (et encore) une liste chaînée, mais ton implémentation n'est pas une liste chaînée, qui, par définition classique, utilise une chaîne de pointeurs.
Si les cons volaient, il ferait nuit à midi.
c'est tout de même superflu
Certified Oracle Advanced PL/SQL Professional
Certified Oracle APEX Expert
Certified Oracle SQL Expert
Une liste chainée, c'est d'abord des méthodes pour insérer/retirer les éléments de la liste. Pour implémenter ces méthodes, il va bien valoir stocker "quelque part" l'information pour savoir qui est le suivant, le prédécesseur et le contenu.
Comme les méthodes vont masquer ce qu'est le triplet { précedent, suivant, contenu }, ils pourront être réalisé comme:
1 - la ligne d'un tableau à N entrée avec précédent et suivant dans 0..N. Dans ce cas contenu pourra être l'adresse de l'élément. Si c'est le contenu, le tableau sera plus gros.
2 - une liste de... pointeurs vers des éléments,
3 - des éléments commençant par l'adresse de précédent, suivant suivi des attributs de 'cet' élément.
Si on est limité en place (comme c'est parfois le cas pour les modules d'un noyau) on préférera implanter un tableau... Dans tous les autres cas, on utilisera des pointeurs.
Mais à priori les méthodes ne changent pas.
- W
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager