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 :

Listes chainées : dérouler le code pour arriver à comprendre


Sujet :

Langage Pascal

  1. #1
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2013
    Messages
    31
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2013
    Messages : 31
    Points : 14
    Points
    14
    Par défaut Listes chainées : dérouler le code pour arriver à comprendre
    Salut,
    J'ai un souci avec le chapitre que je viens d'attaquer, qui est les listes chaînées.

    J'arrive à saisir le principe du cours (d'ailleurs je trouve assez bien celui-ci), mais pour ce qui est de le traduire en code ou de dérouler le code & faire un schéma qui m’aiderait a comprendre, je n'y arrive pas.

    En fait j'aimerais dérouler ce code :
    Code : 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
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    PROGRAM liste (input,output);
    TYPE
      tpoint = ^tval;
      tval = record
               valeur : integer;
               suivant : tpoint
             end;
    VAR
      prem, precedent, point : tpoint;
      i, n : integer;
    BEGIN
      write('Combien d''éléments comporte votre liste ?');
      readln(n);
      new(prem);
         { le 1er est particulier : si on le perd, on perd la liste }
      write('1ère valeur ? ');
      readln(prem^.valeur);
         { lecture de l'enregistrement VALEUR de la variable d'adresse (pointée par) PREM }
      precedent := prem;
      for i := 2 to n do begin
        new(point);
           { création d'une nouvelle variable }
        write(i,'ième valeur ? ');
        readln(point^.valeur);
        precedent^.suivant := point;
           { mise à jour du chaînage }
        precedent := point
           { se préparer pour la prochaine boucle }
      end;
      precedent^.suivant := NIL;
      { NIL signifie "rien" car 0 est un entier, non une adresse }
      point := prem;
         { heureusement, on se souvient du premier }
      for i := 1 to n do begin
        writeln(point^.valeur);
        point := point^.suivant
           { pour la prochaine boucle }
      end
    END.
    Pour arriver à un schéma comme celui-ci :

    Je pense que ça m’aidera beaucoup à comprendre si j'arrive à le dérouler.

  2. #2
    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,

    En dessinant chaque étape, on voit apparaître l'algorithme.
    Voici un exemple pour n = 3 :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
      i = ?
      
      n = 3
      
      prem ---------------
                         |     
      precedent          -->| ??? | ??? |
      
      point
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
      write('1ère valeur ? ');
      readln(prem^.valeur);
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
      
      i = ?
      
      n = 3
      
      prem ---------------
                         |     
      precedent          -->| val | ??? |
      
      point
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
      
      i = ?
      
      n = 3
      
      prem ---------------
                         |     
      precedent ----------->| val | ??? |
      
      point
    1ère itération de la boucle :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
      for i := 2 to n do begin
      { i = 2 }
        new(point);
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
      
      i = 2
      
      n = 3
      
      prem ---------------
                         |     
      precedent ----------->| val | ??? |      ---->| ??? | ??? |
                                               |
      point ------------------------------------
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
        write(i,'ième valeur ? ');
        readln(point^.valeur);
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
      
      i = 2
      
      n = 3
      
      prem ---------------
                         |     
      precedent ----------->| val | ??? |      ---->| val | ??? |
                                               |
      point ------------------------------------
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
        precedent^.suivant := point;
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
      
      i = 2
      
      n = 3
      
      prem ---------------         
                         |          
      precedent ----------->| val | pt--|---------->| val | ??? |
                                               |
      point ------------------------------------
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
      
      i = 2
      
      n = 3
      
      prem ---------------         
                         |          
      precedent ----     -->| val | pt--|---------->| val | ??? |
                   |                           |
      point ------------------------------------
    2e itération de la boucle :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
      for i := 2 to n do begin
      { i = 3 }
        new(point);
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
      i = 3
      
      n = 3
      
      prem ---------------         
                         |          
      precedent ----     -->| val | pt--|---------->| val | ??? |     ---->| ??? | ??? |
                   |                          |                       |
      point ---    ----------------------------                       |
              |                                                       |
              ---------------------------------------------------------
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
        write(i,'ième valeur ? ');
        readln(point^.valeur);
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
      
      i = 3
      
      n = 3
      
      prem ---------------         
                         |          
      precedent ----     -->| val | pt--|---------->| val | ??? |     ---->| val | ??? |
                   |                          |                       |
      point ---    ----------------------------                       |
              |                                                       |
              ---------------------------------------------------------
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
        precedent^.suivant := point;
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
      
      i = 3
      
      n = 3
      
      prem ---------------         
                         |          
      precedent ----     -->| val | pt--|---------->| val | pt--|--------->| val | ??? |
                   |                          |                       |
      point ---    ----------------------------                       |
              |                                                       |
              ---------------------------------------------------------
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
      
      i = 3
      
      n = 3
      
      prem ---------------         
                         |          
      precedent ----     -->| val | pt--|---------->| val | pt--|--------->| val | ??? |
                   |                                                  |
      point ---    |                                                  |
              |    |                                                  |
              ---------------------------------------------------------
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
      end;
      precedent^.suivant := NIL;
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
      
      i = 3
      
      n = 3
      
      prem ---------------         
                         |          
      precedent ----     -->| val | pt--|---------->| val | pt--|--------->| val | NIL |
                   |                                                  |
      point ---    |                                                  |
              |    |                                                  |
              ---------------------------------------------------------
    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]

  3. #3
    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
    Boe,

    Eh oui, la bonne vieille méthode : crayon + papier.
    Si les cons volaient, il ferait nuit à midi.

  4. #4
    Membre expert
    Avatar de e-ric
    Homme Profil pro
    Apprenti chat, bienfaiteur de tritons et autres bestioles
    Inscrit en
    Mars 2002
    Messages
    1 550
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Apprenti chat, bienfaiteur de tritons et autres bestioles

    Informations forums :
    Inscription : Mars 2002
    Messages : 1 550
    Points : 3 916
    Points
    3 916
    Par défaut
    Eh oui, la bonne vieille méthode : crayon + papier.
    Ca c'est ben vrai...

    @AmineDrX: Plusieurs observations :

    - Il doit y avoir un épidémie de listes chaînées dans les écoles. Ca fait déjà 2 fois ces derniers temps que je répond à ce genre d'exercice. Merci de consulter les archives (récentes).

    - les listes chaînées sont un exercice classiques (passionnant...) mais elles ne servent pas souvent dans la pratique, c'est surtout une marotte des profs de fac qui y trouvent de sujets facilement. En gros, si c'est pas ton prof qui te le demande, ne t'acharne pas là-dessus.

    - Pense à créer des fonctions et des procédures pour manipuler ce genre de structure de données, le code est ainsi plus facile à lire, à comprendre, à tester et à relire 6 mois après.

    @+

    M E N S . A G I T A T . M O L E M
    Debian 64bit, Lazarus + FPC -> n'oubliez pas de consulter les FAQ Delphi et Pascal ainsi que les cours et tutoriels Delphi et Pascal

    "La théorie, c'est quand on sait tout, mais que rien ne marche. La pratique, c'est quand tout marche, mais qu'on ne sait pas pourquoi. En informatique, la théorie et la pratique sont réunies: rien ne marche et on ne sait pas pourquoi!".
    Mais Emmanuel Kant disait aussi : "La théorie sans la pratique est inutile, la pratique sans la théorie est aveugle."

  5. #5
    Expert éminent sénior
    Avatar de Paul TOTH
    Homme Profil pro
    Freelance
    Inscrit en
    Novembre 2002
    Messages
    8 964
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Freelance
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Novembre 2002
    Messages : 8 964
    Points : 28 430
    Points
    28 430
    Par défaut
    Citation Envoyé par e-ric Voir le message
    Ca c'est ben vrai...

    @AmineDrX: Plusieurs observations :

    - Il doit y avoir un épidémie de listes chaînées dans les écoles. Ca fait déjà 2 fois ces derniers temps que je répond à ce genre d'exercice. Merci de consulter les archives (récentes).

    - les listes chaînées sont un exercice classiques (passionnant...) mais elles ne servent pas souvent dans la pratique, c'est surtout une marotte des profs de fac qui y trouvent de sujets facilement. En gros, si c'est pas ton prof qui te le demande, ne t'acharne pas là-dessus.

    - Pense à créer des fonctions et des procédures pour manipuler ce genre de structure de données, le code est ainsi plus facile à lire, à comprendre, à tester et à relire 6 mois après.

    @+
    oh moi je m'en sert de temps à autre, c'est tout de même une structure très intéressante.

    La SiblingList est pas mal aussi, la subtile nuance avec la liste chaînée est qu'elle est circulaire, qu'elle conserve l'ordre d'insertion et qu'elle pointe sur le dernier élément.

    pour parcourir une telle liste on boucle jusqu'à revenir au premier (qui est le dernier)
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
      Item := List; // dernier élément
      repeat
         Item := Item.Next; // premier, deuxième, troisième...
         ...utiliser Item...
      until Item = List; // dernier élement
    Developpez.com: Mes articles, forum FlashPascal
    Entreprise: Execute SARL
    Le Store Excute Store

  6. #6
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2013
    Messages
    31
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2013
    Messages : 31
    Points : 14
    Points
    14
    Par défaut
    Merci beaucoup Vos réponses m'ont beaucoup aidé.

    En faite, avant de poster j'avais fait plusieurs recherches, & je tombais souvent sur des explications qui me semblaient pas très clairs. Mais j’admets ne pas avoir consulter les archives.

    Je ne m'acharne pas dessus, c'est juste qu'en Algorithme on fait les listes, piles & les files, & j'avais pas bien saisis ce qu'expliquait le prof.

    Merci des conseils, & bonne continuation

  7. #7
    Membre expert
    Avatar de e-ric
    Homme Profil pro
    Apprenti chat, bienfaiteur de tritons et autres bestioles
    Inscrit en
    Mars 2002
    Messages
    1 550
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Apprenti chat, bienfaiteur de tritons et autres bestioles

    Informations forums :
    Inscription : Mars 2002
    Messages : 1 550
    Points : 3 916
    Points
    3 916
    Par défaut
    Salut,

    Les piles, listes et les files sont des structures de données fondamentales et une source inépuisable d'exercices, c'est une bonne façon de faire travailler ses méninges.

    Je discutais sur la représentation d'une liste simplement chainée car pour accéder à un élément de la liste, tu dois parcourir tous les éléments qui le précèdent. C'est lourd... et d'autre formes de listes existent.

    Dans Delphi par exemple, le conteneur de base est la classe TList qui est une liste indexée, plus souple qu'une liste chaînée (on peut la simuler avec une TList) et qui ne mélange pas les infos de structures (liens) avec les données contenues dans la liste comme c'est le cas dans ton exemple.

    @+

    M E N S . A G I T A T . M O L E M
    Debian 64bit, Lazarus + FPC -> n'oubliez pas de consulter les FAQ Delphi et Pascal ainsi que les cours et tutoriels Delphi et Pascal

    "La théorie, c'est quand on sait tout, mais que rien ne marche. La pratique, c'est quand tout marche, mais qu'on ne sait pas pourquoi. En informatique, la théorie et la pratique sont réunies: rien ne marche et on ne sait pas pourquoi!".
    Mais Emmanuel Kant disait aussi : "La théorie sans la pratique est inutile, la pratique sans la théorie est aveugle."

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 3
    Dernier message: 30/01/2010, 12h56
  2. Réponses: 7
    Dernier message: 11/05/2007, 11h14
  3. Réponses: 8
    Dernier message: 03/12/2006, 18h46
  4. Réponses: 28
    Dernier message: 24/05/2006, 19h20
  5. Réponses: 12
    Dernier message: 09/02/2005, 00h42

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