Listes

  • Cours sur les listes :
    • Définition du type abstrait liste
      Ce type de structure de données est utile pour les données qui doivent être traitées séquentiellement, chaque élément est relié à un autre élément et un seul.
      Elle permet de simuler des situations de la vie courante : liste d’articles pour les magasins, liste de personnes, liste d’objets divers....
      Cas particuliers de listes :
    • Les files (FIFO : First In , First Out):Les éléments sont ajoutés à la queue et supprimés à la tête
    • Les piles (LIFO : Last In, Last Out) :

      On n'y accède que par le sommet qui est le dernier élément rentré. Les éléments sont
      ajoutés et supprimés au sommet.

    •  définition itérative d'une liste
      Soit élément : type T;Une liste est un ensemble fini d'éléments. Il existe une relation d'ordre entre les places (ou les rangs) des éléments d'une liste.Les opérateurs minimaux sont :

      liste vide :                              ------> liste

      Cet opérateur est dit constante car il est défini à partir de rien.
      longueur :                           liste     ------> entier

      ième       :                            liste      ------> élément

      Ces 2 opérateurs sont dits observateurs car à partir d’au moins un type défini, ils
      renvoient un type prédéfini.

      insérer :       liste, entier, élément  ------> liste
      supprimer :   liste, entier                ------> liste

      Ces 2 opérateurs sont dits opérateurs internes  car à partir d’au moins un type défini,
      ils renvoient un type défini.
      On peut enrichir cette spécification en ajoutant les opérateurs suivants qui s’appellent des extensions de type :

      estmembrede :  liste, élément                ------> booléen

      rechercher :      liste, élément                ------> entier

      inverser :           liste                              ------> liste

      concaténer :      liste, liste                      ------> liste

      Une liste linéaire est une structure de données qui a la définition inductive suivante :
      - ou bien elle est vide, on l’appelle alors la liste vide notée nil (en Pascal) ou [] (en Caml)

      - ou bien elle est formée de 2 parties :
      - un premier élément appelé  tête T

      - un deuxième élément appelé reste ou queue Q qui est une liste
      Voici une  définition théorique sous plusieurs formes :

      type élément : …………….. ;
      liste = ( liste vide | liste non vide) où liste non vide = ( élément ; liste)

      type élément : …………….. ;
      liste = nil ou ( élément ; liste)

       

      type élément : …………….. ;
      liste = nil + élément  liste ;

      En Caml  [ 1 ; 2 ; 3 ] est une liste qu’on peut aussi créer par 1 : : ( 2 : : ( 3 : : [] )
      Le compilateur de Caml reconnaît automatiquement une liste dès que l’on utilise soit la
      notation d’ajout ( : : ) soit les crochets [ ] et les points-virgules ; de séparation des
      éléments.

      Les opérateurs minimaux sont :

      liste vide :                                    ------> liste

      estvide :                            liste    ------> booléen

      tête      :                            liste   ------> élément

      ajouterdébut  :    liste, élément  ------> liste
      queue :                               liste  ------> liste

      Ces 2 opérateurs sont dits opérateurs internes  car à partir d’au moins un type défini,
      ils renvoient un type défini.
      On peut enrichir cette spécification en ajoutant les opérateurs suivants qui s’appellent des extensions de type :

      estmembrede :  liste, élément                ------> booléen

      rechercher :      liste, élément                ------> entier

      inverser :           liste                              ------> liste

      concaténer :      liste, liste                      ------> liste

    •  définition récursive d'une liste :
      Une liste linéaire est une structure de données qui a la définition inductive suivante :
      - ou bien elle est vide, on l’appelle alors la liste vide notée nil (en Pascal) ou [] (en Caml)
      - ou bien elle est formée de 2 parties :
      - un premier élément appelé  tête T
      - un deuxième élément appelé reste ou queue Q qui est une liste
      Voici une  définition théorique sous plusieurs formes :
      type élément : …………….. ;
      liste = ( liste vide | liste non vide) où liste non vide = ( élément ; liste)type élément : …………….. ;
      liste = nil ou ( élément ; liste)type élément : …………….. ;
      liste = nil + élément  liste ;

      En Caml  [ 1 ; 2 ; 3 ] est une liste qu’on peut aussi créer par 1 : : ( 2 : : ( 3 : : [] )
      Le compilateur de Caml reconnaît automatiquement une liste dès que l’on utilise soit la
      notation d’ajout ( : : ) soit les crochets [ ] et les points-virgules ; de séparation des
      éléments.

      Les opérateurs minimaux sont :

      liste vide :                                    ------> liste

      estvide :                            liste    ------> booléen

      tête      :                            liste   ------> élément

      ajouterdébut  :    liste, élément  ------> liste
      queue :                               liste  ------> liste

      Ces 2 opérateurs sont dits opérateurs internes  car à partir d’au moins un type défini,
      ils renvoient un type défini.
      On peut enrichir cette spécification en ajoutant les opérateurs suivants qui s’appellent des extensions de type :

      estmembrede :  liste, élément                ------> booléen

      rechercher :      liste, élément                ------> entier

      inverser :           liste                              ------> liste

      concaténer :      liste, liste                      ------> liste


  • Exercices :
    • Sujet : Exercice 3 de E3A :  e3aO3
    • Corrigé :
      type element : integer;
      liste = ^.cellule ;
      cellule = record
      valeur : element;
      suivant :liste;
      end;
      function IndiceTripletMaximal(lst : liste):entier;
      function longueur(L : liste): integer;
      begin
        if L = nil then longueur := 0
      else longueur := 1 + longueur(L^.suivant);
      end;
      begin (* on suppose que la liste au au moins 3 éléments *)
      sommemaximale :=0;
      I := 1;
      repeat
      somme3termesconsecutifs:=lst^.valeur+lst^.suivant.valeur + lst^.suivant.suivant.valeur;
      if somme3termesconsecutifs > somme maximale
      then
      begin
      sommemaximale := somme3termesconsecutifs;
      indicepointe:=I;
      end;
      I:= I +1 ;
      lst:=lst^.suivant;
      until I = longueur(lst) - 1;
      IndiceTripletMaximal := indicepointe;
      end;