9. Structures récursives non linéaires: les listes

La seule propriété structurelle des chaînes est l'ordonnancement de ses éléments, tous de type identique. On peut généraliser la notion de chaîne en élargissant la restriction d'identité de type des éléments de la manière suivante :

Définition : Une liste est une chaîne non-homogène dont chaque élément contient soit une information (atome), soit une autre liste (sous-liste).

La définition ci-dessus est récursive car le terme à définir (la liste) est utilisée à l'intérieur de la définition. Cela peut sembler être un cercle vicieux, mais c'est en fait une façon très puissante de définir et de décrire toutes les structures de listes possibles.

Exemple

A=()

liste vide (longueur 0).

B=(a, (b, c))

liste de longueur 2, le 1er élément est un atome "a", le 2ème élément est une liste "(b, c)".

C=(B, B, ())

liste de longueur 3 dont les 2 premiers éléments sont identiques et correspondent chacun à la liste B, le 3ème élément est la liste vide.

D=(a, D)

liste récursive de longueur 2. D correspond à la liste infinie (a, (a, (a, (. . . )))). Cette possibilité de déclarer des listes récursives est souvent utilisée pour représenter la grammaire d'un langage de programmation.

Déclaration

     type Contenus = (Entier, Reel, Booleen,
                      Symbole, Liste);
          VersObjet = ^Objet;
          Objet = record
              Suivant: VersObjet;
              case Contenu: Contenus of
                Entier : (ValEnt : integer);
                  Reel : (ValReel : real);
               Booleen : (ValBool : boolean);
               Symbole : (ValSym : string);
                 Liste : (Tete, Fin: VersObjet);
                end; { Objet }

     var Obj: Objet;

Cet exemple est extrait d'un interpréteur LOGO, qui est un langage où les listes sont des structures privilégiées. Un programme LOGO est lui-même une liste. Dans cet exemple de déclaration, nous avons volontairement déclaré une variable "Obj" de type "Objet", au lieu d'une variable "Debut" de type "VersObjet" pour bien montrer la récursivité des déclarations : une liste est un objet qui contient une suite d'objets qui, eux-mêmes, peuvent être des listes . . . Il va de soi que la déclaration d'une liste, comme pour une chaîne, pourrait se limiter à une variable de type pointeur (VersObjet).

On peut envisager une variante qui mette plus en évidence la distinction entre atome et sous-liste :

     type GenreAtomes = (Entier, Reel,
                         Booleen, Symbole);
          Contenus = (Atome, Liste);
          VersObjet = ^Objet;

          Atomes = record
                case Genre: GenreAtomes of
                  Entier: (ValEnt : integer);
                    Reel: (ValReel : real);
                 Booleen: (ValBool: boolean);
                 Symbole: (ValSym : string);
                end; { Atomes }

         Objet = record
              Suivant: VersObjet;
              case Contenu: Contenus of
              Atome: (Valeur: Atomes);
              Liste: (Tete, Fin: VersObjet);
             end; { Objet }

     var Obj: Objet;

Cette variante complique toutefois l'accès à la valeur d'un atome.

Description en terme de type abstrait :

• le rôle d'une liste est de stocker un nombre indéterminé d'éléments de types quelconques dans un certain ordre. Un élément peut être lui-même une liste. L'ordre de placement des éléments dans la liste peut dépendre de la chronologie d'insertion, du contenu des éléments insérés ou d'un quelconque autre critère fixé par l'utilisateur.
  
• primitives de manipulation :

  On peut reprendre quasi in-extenso les primitives énumérées pour les chaînes en rajoutant un prédicat permettant de savoir si un élément est un atome ou une liste.

9.1. Operations sur les listes

Table des matières.

Site Hosting: Bronco