9.1. Opérations sur les listes

• insertion : en début, en fin.
• extraction : du premier élément (car), de tout sauf le premier élément (cdr).
• construction : combinaison d'un élément et d'une liste.
• comparaison : = ou <>.
• prédicat de liste vide : revient à comparer à la liste vide.                 

L'insertion est similaire à ce que l'on a vu pour les chaînes. A noter que le pointeur "Fin" est là pour accélérer les insertions en fin de liste. Comme pour les chaînes, il est possible de construire des variantes à la structure de liste, en rendant la liste circulaire et/ou bidirectionnelle. Ceci apportera les mêmes avantages que pour les chaînes, c'est-à-dire une plus grande facilité pour effectuer certaines opérations telles que insertion avant un élément donné, suppression du dernier élément, . . .

"car" et "cdr" sont, par des raisons historiques, les abrégés, respectivement, de "Content of A Register" et "Content of D Register". "car" fournit un atome si le premier élément est un atome, et une liste si le premier élément est une sous-liste. "cdr" fournit toujours une liste correspondant à la liste de départ moins le premier élément. "car" ou "cdr" d'une liste vide donnent un résultat indéterminé (en LISP cela donne à nouveau la liste vide).

La combinaison de "car" et "cdr" permet d'isoler n'importe quel élément d'une liste. Pour abréger, on ne note souvent que les lettres du milieu (a ou d), le tout entouré de c et r.

Exemple

car(cdr(cdr(L))) peut s'abréger caddr(L)

L'opération de construction consiste à créer une nouvelle liste à partir d'un élément et d'une liste de façon à avoir la relation suivante :

L = cons( car(L), cdr(L) )

La comparaison de deux listes tient compte des niveaux d'imbrication des sous-listes ainsi que du nombre d'éléments. Ainsi, (a) est différent de (a ()) et de ((a)) , de même (()) est différent de ().

Exemple d'algorithme de comparaison (cet algorithme utilise la première variante de déclaration vue au début de ce chapitre) :

     function Egale(Obj1,Obj2:Objet): boolean;
        
        function ListesEgales(Tete1,
                              Tete2:VersObjet)
                              : boolean;
        begin { ListesEgales }
          if (Tete1=nil) and (Tete2=nil) then
            ListesEgales := true
          else if (Tete1=nil) or
                  (Tete2=nil) then
                 ListesEgales := false
          else ListesEgales:=
                 Egale(Tete1^, Tete2^) and
                 ListesEgales(Tete1^.Suivant,
                              Tete2^.Suivant);
        end; { ListesEgales }

        begin { Egale }
          if Obj1.Contenu<>Obj2.Contenu then
            Egale := false
          else case Obj1.Contenu of
                  Entier: Egale:= (Obj1.ValEnt =
                                   Obj2.ValEnt);
                    Reel: Egale:= (Obj1.ValReel =
                                   Obj2.ValReel);
                 Booleen: Egale:= (Obj1.ValBool =
                                   Obj2.ValBool);
                 Symbole: Egale:= (Obj1.ValSym =
                                   Obj2.ValSym);
                   Liste: Egale:= ListesEgales
                           (Obj1.Tete,Obj2.Tete);
                end; { case }
         end; { Egale }

Il est clair que le parcours des éléments de listes dans la fonction "ListesEgales" pourrait se faire sans utiliser la récursivité.

9.2. Détermination de l'appartenance à une liste

Table des matières.

Site Hosting: Bronco