- 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 ------> entieriè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 ------> listeCes 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 ------> listeCes 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 ------> listeCes 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 du type abstrait 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;