Epita:Algo:Cours:Info-Sup:Structures séquentielles

De EPITACoursAlgo.

Sommaire

Les listes linéaires

La liste linéaire est la forme la plus simple d'organisation de données que l'on puisse rencontrer. Celles-ci sont stockées les unes à la suite des autres dans des places et permettent divers traitements séquentiels. L'ordre des éléments dans une liste ne dépend pas des éléments eux-mêmes, mais de la place de ceux-ci dans la liste. Il y a plusieurs façons de décrire une liste, soit itérativement, soit récursivement. Nous allons envisager les deux et voir sur quels types de fonctionnement elles sont respectivement basées et quelle représentation mémoire est la mieux adaptée suivant le type de liste. En effet, il nous faut pouvoir créer des éléments, en modifier et en supprimer. De plus (et pour le même prix), nous y ajouterons des fonctionnalités propres aux listes comme la concaténation, la recherche d'élément etc.

Le type liste récursive

types
liste, place
utilise
élément
opérations
listevide : \rightarrow liste cons : liste x élément \rightarrow liste fin : liste \rightarrow liste tête : liste \rightarrow place contenu : place \rightarrow élément premier : liste \rightarrow élément succ : place \rightarrow place
préconditions
fin(l) est-défini-ssi l ≠ listevide tête(l) est-défini-ssi l ≠ listevide premier(l) est-défini-ssi l ≠ listevide
axiomes
premier(l) = contenu(tête(l)) fin(cons(e,l)) = l premier(cons(e,l)) = e succ(tête(l)) = tête(fin(l))
avec
liste l élément e

Nous ne redonnerons plus par la suite la terminologie des éléments utilisés dans les définitions de type (Oui, c'est vrai, ça ira bien comme ça !).

Alors dans le type abstrait qui précède, nous avons :


  • Liste et Place comme types définis
  • élément comme type prédéfini
  • tête et succ comme opérations internes de place
  • contenu comme observateur de place
  • listevide, fin et cons comme opérations internes de liste
  • premier comme observateur de liste


Ces opérations n'étant pas définies partout, il y bien sur des préconditions. La définition algébrique affecte aux diverses fonctions les rôles suivants :


  • liste-Vide crée une liste sans éléments (une sorte de "constructeur")
  • tête permet de récupérer la première place (celle de tête)
  • contenu permet d'obtenir l'élément d'une place
  • premier permet d'obtenir le premier élément d'une liste (sans place intermédiaire)
  • fin permet de détruire l'élément de tête et de récupérer la liste restante
  • cons permet d'ajouter un élément en première place (en l'insérant devant la liste existante)
  • succ permet de passer à la place suivante


Le type Liste itérative

types
liste, place
utilise
entier, élément
opérations
listevide : \rightarrow liste accès : liste x entier \rightarrow place contenu : place \rightarrow élément ième : liste x entier \rightarrow élément longueur : liste \rightarrow entier supprimer : liste x entier \rightarrow liste insérer : liste x entier x élément \rightarrow liste succ : place \rightarrow place
préconditions
accès(l,k) est-défini-ssi l ≠ listevide & 1k ≤ longueur(l) supprimer(l,k) est-défini-ssi l ≠ listevide & 1k ≤ longueur(l) insérer(l,k,e) est-défini-ssi 1k ≤ longueur(l)+1
axiomes
longueur(listevide) = 0 longueur(supprimer(l,k)) = longueur(l)-1 longueur(insérer(l,k,e)) = longueur(l)+1
1 ≤ i < k \Rightarrow ième(supprimer(l,k),i) = ième(l,i) k ≤ i ≤ longueur(l)-1 \Rightarrow ième(supprimer(l,k),i) = ième(l,i+1)
1 ≤ i < k \Rightarrow ième(insérer(l,k,e),i) = ième(l,i) k = i \Rightarrow ième(insérer(l,k,e),i) = e k < i ≤ longueur(l)+1 \Rightarrow ième(insérer(l,k,e),i) = ième(l,i-1)
contenu(accès(l,k)) = ième(l,k) succ(accès(l,k)) = accès(l,k+1)
avec liste l entier i,k élément e

Cette présentation correspond à une autre forme d'implémentation des listes linéaires. En fait l'opération de base n'est plus l'accès à la première place d'une liste, mais l'opération accès qui renvoie la Kième place de cette liste. Les autres opérations découlant de ce fonctionnement.


Le type abstrait liste itérative bien que plus adapté à d'autres fonctionnements, permet aussi de décrire des traitements récursifs.


Ce qui est important, c'est de comprendre qu'en fait nous décrivons la même donnée, seule la manière de s'en servir diffère. Une façon simple de le montrer est de décrire les opération d'un type en terme de celles de l'autre et inversement.


Prenons par exemple, les opérations du type récursif en terme des opérations du type itératif:


récursive itérative
tête (l) accès (l,1)
premier (l) ième (l,1)
fin (l) supprimer (l,1)
cons (e,l) insérer (l,1,e)


Et inversement:


itérative récursive
insérer (l,i,e) l2 \leftarrow liste-vide
(i-1) fois \Bigg\{ l2 \leftarrow cons (premier (l),l2)
l \leftarrow fin (l)
l \leftarrow cons (e,l)
(i-1) fois \Bigg\{ l \leftarrow cons (premier (l2),l)
l2 \leftarrow fin (l2)


Comme on peut le constater, dans ce cas la correspondance ne se résume pas une simple opération, mais l'opération insérer à bien été retranscrite en terme des opérations de la liste récursive.

Remarque : La traduction des autres opérations est laissée en exercices.


Extensions du type liste

Bien entendu, nous avons souvent besoin d'opérations complémentaires sur les listes comme la concaténation de deux listes, la recherche d'un élément dans une liste. Dans ce cas, et ceci est valable pour n'importe quel type défini, on déclare ce que l'on appelle des extensions au type. Il est alors inutile de représenter le type abstrait qui est supposé connu (En tous cas, on l'espère!). Pour ces deux opérations supplémentaires, nous présenterons le profil (Le bon, hein Tintin !) les éventuelles préconditions et les axiomes pour une liste itérative et pour une liste récursive.

Concaténation

La concaténation de deux listes est l'opération qui permet de les rassembler en les mettant bout à bout. Les éléments de chacune conservent leur place d'origine au sein de leur propre liste, la deuxième liste étant accrochée à la suite de la première.

opérations
concaténer : liste x liste \rightarrow liste
axiomes (Liste récursive)
concaténer(listevide,l) = l concaténer(cons(e,l),l2) = cons(e,concaténer(l,l2))
axiomes (Liste itérative)
longueur(concaténer(l,l2)) = longueur(l)+longueur(l2) 1 < i < longueur(l) \Rightarrow ième(concaténer(l,l2),i) = ième(l,i) longueur(l)+1 < i < longueur(l)+longueur(l2) \Rightarrow ième(concaténer(l,l2),i) = ième(l2,i-longueur(l))
avec
liste l,l2 entier i élément e

Recherche d'un élément

La recherche consiste à trouver un élément dans une liste et à retourner sa place si celui-ci existe dans la liste. Dans ce cas (j'aime bien cette locution. Et de plus, je fais ce que je veux ! C'est clair Junior !?), le problème est que la recherche n'est pas définie pour un élément non présent. Il faut donc une précondition sur la recherche que l'on décrira à l'aide d'une opération auxiliaire existe.


opérations
rechercher : élément x liste \rightarrow place existe : élément x liste \rightarrow booléen
préconditions
rechercher(e,l) est-défini-ssi existe(e,l) = vrai
axiomes (Liste récursive)
existe(e,listevide) = faux e = e2 \Rightarrow existe(e2,cons(e,l)) = vrai ee2 \Rightarrow existe(e2,cons(e,l)) = existe(e2,l) existe(e,l) = vrai \Rightarrow contenu(rechercher(e,l)) = e
axiomes (Liste itérative)
existe(e,listevide) = faux e = e2 \Rightarrow existe(e2,insérer(l,i,e)) = vrai ee2 \Rightarrow existe(e2,insérer(l,i,e)) = existe(e2,l) existe(e,l) = vrai \Rightarrow contenu(rechercher(e,l)) = e
avec
liste l entier i élément e,e2

Représentation des Listes

Les listes comme tous les autres types de données sont implémentables de différentes manières. Les deux formes basiques sont la représentation statique (à l'aide de tableaux) et la représentation dynamique (à l'aide de pointeurs et d'enregistrements).

Bien sûr, pour des types de données plus élaborés, il sera possible de représenter ceux-ci par des hybrides des deux (statique et dynamique). De plus, il sera éventuellement possible d'avoir plusieurs représentations statiques et plusieurs dynamiques (C'est chouette ! Non ?).

Représentation statique

Exemple de déclaration algorithmique :

Constantes
Nbmax = 20
Types
t_element = ... /* Définition du type des éléments */ t_vectNbmaxelts = Nbmax t_element /* Définition du tableau des éléments */ t_liste = enregistrement /* Définition du type t_liste */ t_vectNbmaxelts elts entier longueur fin enregistrement t_liste
Variable
t_liste liste

Ce qui correspondrait à la structure suivante :


Représentation statique des listes


Le problème posé par les tableaux est la nécessité d'un surdimensionnement. En effet, ils sont statiques. Donc pour être sûr que votre liste de données puisse y être représentée, vous êtes tenus de donner au tableau une taille supérieure à celle de la liste (pour d'éventuels ajouts). Dès lors, vous devez savoir où s'arrêtent vos données dans ce tableau. C'est l'utilité de la variable longueur qui contiendra toujours la taille de votre liste. Pour accèder à une donnée il suffit alors de préciser le nom du tableau et le rang de celle-ci. C'est très simple (un enfant de 5 ans comprendrait. Enfin, je crois...).


Remarque 1 : Pour insérer ou supprimer une donnée, vous devrez décaler dans un sens où dans l'autre tous les éléments se trouvant entre celle-ci et la fin de votre liste, ce qui ne rend pas cette représentation très performante en cas de modifications fréquentes des éléments.


Remarque 2 : Contrairement à ce que l'on pourrait croire, cette représentation est parfaitement adaptée aux listes récursives, où la longueur fait office de place de tête et où il n'a aucun transfert de valeur a effectuer au milieu du tableau.

Représentation dynamique

Exemple de déclaration algorithmique :

Types
t_element = ... /* Définition du type des éléments */ t_pliste = \uparrowt_liste /* Définition du type pointeur t_pliste */ t_liste = enregistrement /* Définition du type t_liste */ t_element elt t_pliste lien fin enregistrement t_liste
Variables
t_pliste liste

Ce qui correspondrait à la structure suivante :


Représentation dynamique des listes


Le pointeur NUL représente la fin de liste (listevide). Cette représentation utilise à priori plus de place que la précédente dans la mesure où l'on doit stocker la valeur des pointeurs. Mais en fait, le nombre d'éléments est toujours celui de la liste, ni plus ni moins. Contrairement à l'implémentation statique pour laquelle il faut surdimensionner le tableau, celle-ci ne nécessite pas de compteur du nombre d'éléments (Longueur).


Remarque : L'inconvénient majeur est de ne pas pouvoir accèder au Kième élément directement. Par contre, il est facile de concaténer deux chaînes, d'ajouter ou de supprimer un élément sans avoir à tout décaler. Elle est de plus très bien adaptée aux traitements récursifs.

Variantes de représentation

Utilisation d'une sentinelle en tête

Une possibilité est de ne pas utiliser un pointeur sur l'enregistrement, mais directement un enregistrement pour générer la tête de liste. L'avantage est de ne pas avoir besoin de traitement particulier en insertion devant le premier élément. Dans ce cas, l'élément de l'enregistrement de tête n'est pas utilisé et la déclaration de variables est :

Variable
t_liste liste

Ce qui correspondrait à la structure suivante :


Représentation dynamique des listes (avec sentinelle de tête)


Liste circulaire

On peut aussi utiliser des listes circulaires. Dans ce cas, le dernier pointeur n'est pas nul, mais il pointe sur le premier élément de la liste. Pour cela, le pointeur principal de liste référence le dernier élément et non pas le premier. Dans ce cas, pour obtenir l'élément de tête, il suffit d'avancer d'un lien.

Notons que si la liste n'est composée que d'un élément, celui-ci pointe sur lui-même (Ah Ouais! C'est Géniaaallll !). La déclaration est alors la même que pour la représentation dynamique de base.

Ce qui correspondrait à la structure suivante :


Représentation circulaire des listes


Note : On pourrait là aussi utiliser une sentinelle (un enregistrement) à la place d'un pointeur


Liste doublement chaînée

Le problème des représentations précédentes est de ne pouvoir aller que dans un sens. En effet, les listes étant généralement ordonnées, il peut être intéressant de revenir sur l'élément précédent, or cette possibilité n'existe pas. Pour y arriver, il suffit de rajouter un lien en sens inverse. Dans ce cas, il faut posséder non seulement un pointeur de tête, mais aussi un pointeur de queue. La déclaration devient :


Types
t_element = ... /* Définition du type des éléments */ t_penreg = \uparrowt_enreg /* Définition du type pointeur t_penreg */ t_enreg = enregistrement /* Définition du type t_enreg */ t_element elt t_penreg suivant,precedent fin enregistrement t_enreg t_liste = enregistrement /* Définition du type t_liste */ t_penreg premier,dernier fin enregistrement t_liste
Variable
t_liste liste

Ce qui correspondrait à la structure suivante :


Représentation des listes doublement chaînées


Bien sûr, il est toujours possible de construire d'autres structures comme par exemple; une liste circulaire doublement chaînée. Enfin pour terminer sur les variantes possibles des listes, citons la simulation de pointeurs dans un tableau. Dans ce cas, les éléments du tableau sont des enregistrements contenant deux champs; l'élément et un entier contenant l'indice de l'élément suivant. Tout est possible ou presque, mais utiliser ce genre de structure n'a aucun intérêt dans la mesure où elle présente tous les inconvénients du statique et du dynamique réunis (un peu comme le Side-Car).

Les piles et les files

Les piles

Les piles sont des structures LIFO (Last In First Out). C'est à dire que les entrées et les sorties s'effectuent du même coté. L'image la plus simple que l'on puisse donner est la pile d'assiette où, si l'on est totalement "terminé" (ce qui pour certains étudiants n'est pas gagné), les entrées et les sorties se font au même endroit. On appelle ce dernier le sommet de la pile.

Le type abstrait d'une pile est le suivant :

types
pile
utilise
booléen, élément
opérations
pilevide : \rightarrow pile empiler : pile x élément \rightarrow pile dépiler : pile \rightarrow pile sommet : pile \rightarrow élément estvide : pile \rightarrow booléen
préconditions
dépiler(p) est-défini-ssi estvide(p) = Faux sommet(p) est-défini-ssi estvide(p) = Faux
axiomes
dépiler(empiler(p,e)) = p sommet(empiler(p,e)) = e estvide(pilevide) = Vrai estvide(empiler(p,e)) = Faux
avec
pile p élément e

Représentation statique des piles

Nous avons besoin d'un tableau pour ranger les éléments et d'un entier Sommet qui nous permette de savoir en permanence où se situe celui-ci. Pour avoir quelque chose de systémique, nous allons déclarer une pile statique comme la composée d'un ensemble de valeurs empilées (un vecteur d'éléments) et d'un indicateur de sommet (entier), ce qui donne:

Exemple de déclaration algorithmique :

Constantes
Nbmax = 20 /* Nombre maximum d'éléments dans la pile */
Types
t_element = ... /* Définition du type des éléments */ t_elements = Nbmax t_element /* Définition du vecteur d'éléments */ t_pile = enregistrement /* Définition du type pile */ t_elements elts entier sommet fin enregistrement t_pile
Variable
t_pile pile

Ce qui correspondrait à la structure suivante :


Représentation statique des piles


Représentation dynamique des piles

Dans ce cas, les éléments de la pile sont chaînés entre eux, et le pointeur représente le sommet de celle-ci. On peut noter que le lien sur les éléments est un lien de précédence qui permet lorsque l'on dépile de savoir quel élément avait été précédemment empilé.

Exemple de déclaration algorithmique :

Types
t_element = ... /* Définition du type des éléments */ t_ppile = \uparrowt_pile /* Définition du type pointeur t_ppile */ t_pile = enregistrement /* Définition du type t_pile */ t_element elt t_ppile precedent fin enregistrement t_pile
Variables
t_ppile pile

Ce qui correspondrait à la structure suivante :


Représentation dynamique des listes


Les files

Les files sont des structures FIFO (First In First Out). C'est à dire que les entrées et les sorties s'effectuent à chaque extrémité de la liste. L'image la plus simple que l'on puisse donner est la file d'attente où (en l'absence de tout resquilleur) la première personne arrivée dans la file sera la première à en sortir. Nous avons donc besoin dans ce cas là de maitriser la position de l'entrée et celle de la sortie. On référence alors la Tête et la Queue de la file.

Le type abstrait d'une pile est le suivant :

types
file
utilise
booléen, élément
opérations
filevide : \rightarrow file enfiler : file x élément \rightarrow file défiler : file \rightarrow file premier : file \rightarrow élément estvide : file \rightarrow booléen
préconditions
défiler(f) est-défini-ssi estvide(f) = Faux premier(f) est-défini-ssi estvide(f) = Faux
axiomes
estvide(f) = Vrai \Rightarrow premier(enfiler(f,e)) = e estvide(f) = Faux \Rightarrow premier(enfiler(f,e)) = premier(f) estvide(f) = Vrai \Rightarrow défiler(enfiler(f,e)) = filevide estvide(f) = Faux \Rightarrow défiler(enfiler(f,e)) = enfiler(défiler(f),e) estvide(filevide) = Vrai estvide(enfiler(f,e)) = Faux
avec
file f élément e

Représentation statique des files

Nous avons besoin d'un tableau pour ranger les éléments et de deux entiers Tete et Queue qui nous permettent de savoir en permanence où se situe le début et la fin de la file.

Exemple de déclaration algorithmique :

Constantes
Nbmax = 8 /* Nombre maximum d'éléments dans la file */
Types
t_element = ... /* Définition du type des éléments */ t_elements = Nbmax t_element /* Définition du vecteur d'éléments */ t_file = enregistrement /* Définition du type file */ t_elements elts entier tete,queue fin enregistrement t_file
Variable
t_file file

Ce qui correspondrait à la structure suivante :


Représentation statique des files


Nous pourrions pour visualiser l'implémentation d'une file statique utiliser cette figure, mais en fait pour illustrer les débordements, il vaut mieux représenter celle-ci de façon circulaire, ce qui donnerait pour deux cas différents:


Représentation circulaire d'une file statique


Pour ces deux exemples, nous avons fixé Nbmax à 8. En fait les valeurs de tete et de queue avancent d'un rang à chaque fois, exception faite de la bascule de 8 à 1. En effet, lorsque nous atteignons la limite Nbmax que ce soit avec la tete ou la queue, nous passons à 1 alors que dans les autres cas, nous passons à la valeur augmentée de 1. Ce dépassement est géré de façon extrêmement simple, il suffit d'utiliser un modulo Nbmax, soit 8 dans le cas présent.

Représentation dynamique des files

Dans ce cas, les éléments de la file sont chaînés entre eux, et les pointeurs Tête et Queue représentent les deux extrémités de celle-ci.

Exemple de déclaration algorithmique :

Types
t_element = ... /* Définition du type des éléments */ t_penr = \uparrowt_enr /* Définition du type pointeur t_penr */ t_enr = enregistrement /* Définition du type t_file */ t_element elt t_penr suivant fin enregistrement t_enr
t_file = enregistrement /* Définition du type file */ t_penr tete,queue fin enregistrement t_file
Variables
t_file file

Ce qui correspondrait à la structure suivante (a) :


Représentation dynamique des files


On peut remarquer que dans le cas d'une représentation circulaire (b), le pointeur de Tête n'a plus aucune utilité. Il suffit de suivre le lien Suivant à partir du dernier pour déterminer le premier élément. Il est, d'autre part, possible d'utiliser le système de sentinelle utilisée avec les listes, à savoir prendre un élément complet pour les deux pointeurs (Tête et Queue).


(Christophe "krisboul" Boullay)

Outils personnels
Cours d'algo EPITA :
Accès aux algorithmes :