IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage Pascal Discussion :

Liste chaînée sans pointeur


Sujet :

Langage Pascal

  1. #1
    Membre à l'essai
    Profil pro
    Inscrit en
    Décembre 2006
    Messages
    15
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2006
    Messages : 15
    Points : 11
    Points
    11
    Par défaut Liste chaînée sans pointeur
    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.

  2. #2
    Expert confirmé

    Inscrit en
    Août 2006
    Messages
    3 939
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 3 939
    Points : 5 648
    Points
    5 648
    Par défaut
    Koe,

    Par principe même, on passe d'un chaînon à l'autre avec un pointeur.
    Si les cons volaient, il ferait nuit à midi.

  3. #3
    Membre à l'essai
    Profil pro
    Inscrit en
    Décembre 2006
    Messages
    15
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2006
    Messages : 15
    Points : 11
    Points
    11
    Par défaut
    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 !

  4. #4
    Membre averti Avatar de Tux++
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    281
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 281
    Points : 379
    Points
    379
    Par défaut
    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
    Certified Oracle Advanced PL/SQL Professional
    Certified Oracle APEX Expert
    Certified Oracle SQL Expert

  5. #5
    Membre à l'essai
    Profil pro
    Inscrit en
    Décembre 2006
    Messages
    15
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2006
    Messages : 15
    Points : 11
    Points
    11
    Par défaut
    merci pour ta réponse.

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

  6. #6
    Membre averti Avatar de Tux++
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    281
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 281
    Points : 379
    Points
    379
    Par défaut
    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

  7. #7
    Expert confirmé

    Inscrit en
    Août 2006
    Messages
    3 939
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 3 939
    Points : 5 648
    Points
    5 648
    Par défaut
    Hei,
    Citation Envoyé par Tux++ Voir le message
    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.

    Citation Envoyé par Tux++ Voir le message
    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)
    Si les cons volaient, il ferait nuit à midi.

  8. #8
    Membre averti Avatar de Tux++
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    281
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 281
    Points : 379
    Points
    379
    Par défaut
    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

  9. #9
    Expert confirmé

    Inscrit en
    Août 2006
    Messages
    3 939
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 3 939
    Points : 5 648
    Points
    5 648
    Par défaut
    Gao,
    Citation Envoyé par Tux++ Voir le message
    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
    Mais une liste n'est qu'un des usages des listes chaînées, et n'a pas à supporter ce que fait une liste chaînée normale (insertion, suppression, entre autres).

    La question concernait les listes chaînées, pas les files.
    Si les cons volaient, il ferait nuit à midi.

  10. #10
    Membre averti Avatar de Tux++
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    281
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 281
    Points : 379
    Points
    379
    Par défaut
    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)
    le calcul d'indice est un temps constant O(1), ca ne change strictement rien.

    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

  11. #11
    Expert confirmé

    Inscrit en
    Août 2006
    Messages
    3 939
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 3 939
    Points : 5 648
    Points
    5 648
    Par défaut
    Fai,
    Citation Envoyé par Tux++ Voir le message
    le calcul d'indice est un temps constant O(1), ca ne change strictement rien.
    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.

    Citation Envoyé par Tux++ Voir le message
    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.
    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.

    Citation Envoyé par Tux++ Voir le message
    La file est une implémentation des listes (une possible, il y en a plusieurs), pas l'inverse à mon sens
    Aurais-je prétendu le contraire ?
    Si les cons volaient, il ferait nuit à midi.

  12. #12
    Membre averti Avatar de Tux++
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    281
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 281
    Points : 379
    Points
    379
    Par défaut
    La question concernait les listes chaînées, pas les files.
    j'ai compris ça comme ça...

    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

  13. #13
    Expert confirmé

    Inscrit en
    Août 2006
    Messages
    3 939
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 3 939
    Points : 5 648
    Points
    5 648
    Par défaut
    Jai,

    Citation Envoyé par Tux++ Voir le message
    en fait, mieux que mes mots, voilà mon point de vue : http://fr.wikipedia.org/wiki/Liste_(...Types_de_liste
    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"

    Citation Envoyé par Tux++ Voir le message
    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)
    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.

  14. #14
    Membre à l'essai
    Profil pro
    Inscrit en
    Juin 2008
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2008
    Messages : 5
    Points : 11
    Points
    11
    Par défaut
    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 :
    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;
    Je sais pas si je suis très clair.

  15. #15
    Membre averti Avatar de Tux++
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    281
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 281
    Points : 379
    Points
    379
    Par défaut
    @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

  16. #16
    Responsable Pascal, Lazarus et Assembleur


    Avatar de Alcatîz
    Homme Profil pro
    Ressources humaines
    Inscrit en
    Mars 2003
    Messages
    7 929
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 57
    Localisation : Belgique

    Informations professionnelles :
    Activité : Ressources humaines
    Secteur : Service public

    Informations forums :
    Inscription : Mars 2003
    Messages : 7 929
    Points : 59 395
    Points
    59 395
    Billets dans le blog
    2
    Par défaut
    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) :
    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 |
    Voilà, je viens de créer une liste chaînée sans aucun pointeur.
    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]

  17. #17
    Expert confirmé

    Inscrit en
    Août 2006
    Messages
    3 939
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 3 939
    Points : 5 648
    Points
    5 648
    Par défaut
    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.

  18. #18
    Rédacteur/Modérateur
    Avatar de M.Dlb
    Inscrit en
    Avril 2002
    Messages
    2 463
    Détails du profil
    Informations personnelles :
    Âge : 39

    Informations forums :
    Inscription : Avril 2002
    Messages : 2 463
    Points : 4 305
    Points
    4 305
    Par défaut
    Citation Envoyé par droggo Voir le message
    Pour Alcatîz : c'est là encore un abus de langage.
    Ou pas.

    Un tableau est bien une liste, et le chaînage est effectué correctement. C'est donc bien une liste chaînée
    M.Dlb - Modérateur z/OS - Rédacteur et Modérateur Pascal

  19. #19
    Membre averti Avatar de Tux++
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    281
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 281
    Points : 379
    Points
    379
    Par défaut
    c'est tout de même superflu
    Certified Oracle Advanced PL/SQL Professional
    Certified Oracle APEX Expert
    Certified Oracle SQL Expert

  20. #20
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 203
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 203
    Points : 36 631
    Points
    36 631
    Par défaut
    Citation Envoyé par droggo Voir le message
    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.
    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
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

Discussions similaires

  1. Réponses: 5
    Dernier message: 15/03/2012, 01h26
  2. Pointeurs et listes chaînées
    Par womannosky dans le forum C++
    Réponses: 8
    Dernier message: 11/11/2007, 05h41
  3. Pointeur générique et liste chaînée
    Par jro-daemon dans le forum C
    Réponses: 9
    Dernier message: 23/02/2007, 15h06
  4. conserver ma liste d'objets sans Pointeur Null ...
    Par comme de bien entendu dans le forum Général Java
    Réponses: 8
    Dernier message: 24/03/2006, 12h55
  5. [LG]Listes chainées avec pointeur
    Par PaowZ dans le forum Langage
    Réponses: 2
    Dernier message: 17/02/2004, 20h49

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo