Pile

File

La file (en anglais queue) permet également de stocker des éléments. A l'inverse de la pile elle permet de lire et d'ôter l'élément le plus anciennement stocké dans la file. Les opération que l'on doit pouvoir appliquer à une file sont file-vide(f), un prédicat, enfiler(x, f) et defiler(f) qui sont tous deux des modificateurs de file, enfiler permet d'ajouter un élément à la file, défiler ôte et retourne un élément de la file.

Exemple d’utilisation de pile : retourner un tableau

Réalisation d’une pile à l’aide d’un tableau

Une pile peut être constituée de deux éléments un tableau de longueur l (on dira que la pile à une profondeur de l) et d'un élément qui indexe le sommet de la pile, que l'on appellera sommet. Lorsque la pile est vide cet élément à pour valeur -1. Ajouter un élément à la pile consiste donc à incrémenter le sommet et à stocker l'élément dans le tableau à cet indice. Attention il peut y avoir débordement de la pile ! dépiler consiste à décrémenter le sommet et à rendre l'élément qui est au dessus. Ici encore il peut y avoir débordement de la pile.

Réalisation d’une file avec des listes

Une file sera représentée par une paire dont le car sera la liste des éléments entrés dans la file, le plus ancien est en tête de cette liste, le cdr de la paire représentant la liste pointera sur le plus récent élément entré dans la file. La file est vide lorsque le car de la paire la représentant est la liste vide. Le programme ci-dessous est inspiré du livre de Jacques Chazarain Programmer avec Scheme — De la pratique à la théorie (Vuibert)

Réalisation d’une file avec des tableaux

L'idée, empruntée à l'excellent ouvrage de Max Hailperin, Barbara Kaiser, et Karl Knight Concrete Abstractions – An Introduction to Computer Science Using Scheme, disponible en texte intégral ici :
http://www.gustavus.edu/+max/concrete-abstractions.html),
est de représenter la file par un tableau alveoles où seront emmagasinés les éléments à placer dans la file. Pour ne pas avoir à décaler le contenu de toutes les alvéoles vers la gauche à chaque fois que l'on retire un élément de la tête de la file, le tableau d'alvéoles est rempli de façon circulaire : même si l'on a retiré l'élément de tête par un (defiler F), on continue à ajouter en queue par (enfiler x F) les éléments qui viennent dans la file. Lorsque l'on arrive ainsi à la dernière case d'alveoles, mais que les premières cases correspondent à des éléments qui ont été retirés, donc à des alvéoles inutilisées, on continue le remplissage à partir de la case 0. Lorsqu'un ajout ferait déborder réellement la file, c'est-à-dire écraser un élément « vivant », la file est allongée par une opération (allonger-file! F), qui remplace le vecteur alveoles par un nouveau, de longueur double.

Le vecteur alveoles qui contient la file proprement dite est contrôlé au moyen d'un vecteur préfixe de trois cases : la première case contient la longueur de la file, la seconde case contient la position dans alveoles qui correspond à la tête de la file, la troisième case pointe vers alveoles.

Implanter un type de données

• créer une file : (creer-file) ;
• vérifier l'appartenance d'un objet au type : (file? o) ;
• la file est-elle vide : (file-vide? F) ;
• obtenir la valeur de l'élément tête de file : (tete-file F) ;
• placer un élément dans la file : (enfiler! x F) ;
• retirer un élément de la file : (defiler! F).

• 0 ≤ (longueur-file F) ≤ longueur-alveoles ;
• 0 ≤ (pos-tete-file F) ≤ longueur-alveoles ;
• il y a (longueur-file F) éléments dans la file F ; pour tout i dans l'intervalle 0 ≤ i ≤ (longueur-file F) on vérifie que l'élément qui est dans la file i places après la tête de file est rangé dans l'alvéole :
  alveoles[(pos-tete-file + i) mod(longueur-alveoles)]

Arbre binaire

Un arbre binaire est soit une valeur particulière qu'on appelle l'arbre vide et qu'on note arbre-vide soit un triplet (valeur, fils-gauche, fils-droit) dans lesquels fils-droit et fils-gauche sont eux-même des arbres binaires. On distingue deux sortes d'éléments dans un arbres ceux qui n'ont pas de fils qu'on appellera feuilles et ceux qui en ont qu'on apellera noeuds. Dans un arbre il existe un triplet qui n'est ni le fils droit ni le fils gauche d'un autre arbre : on appelle cet arbre la racine. Pour chaque sous-arbre on peut construire une séquence d'arbres dont le premier est la racine et dont chacun des autres est soit le fils droit soit le fils gauche du précédent dans la séquence. Le nombre d'arbres autres que la racine présent dans un telle chaine est la profondeur à laquelle se trouve le sous-arbre. La racine est ainsi à profondeur 0, son fils droit à profondeur 1, le fils gauche de son fils droit à profondeur 2...

Tas

Un tas est un objet qui peut être vu comme un arbre binaire complet : à part peut-être un seul de ses sous arbres tous ont soit un ou deux fils qui sont des arbres-vides soit deux fils qui ne sont pas des arbres vides. Tous les sous-arbres non vides se présentent sur deux niveaux au plus. Enfin lorsqu'on examine deux sous arbres vides dont l'un est à gauche de l'aure, le sous arbre de gauche est toujours à une profondeur supérieure ou égale à celui de droite. La valeur d'un sous arbre est toujours plus élevée que les valeurs contenues dans ses sous arbres droit et gauche.

Représentation d'un tas : on peut le représenter par un tableau (de longueur l) et par une valeur qui représente le nombre de sous-arbres non vides du tas. Les valeurs du tas seront stockées dans les cellules 1 à taille du tas (attention à la taille maximum du tas qui doit etre plus petite d'un que la taille du tableau). De la sorte la valeur du fils gauche de l'arbre dont la valeur sera en position i du tableau sera stockée en 2i et le fils droit en 2i+1, de la même manière le père d'un noeud en position i sera en Entier(i/2).


On trouvera la suite de l’histoire des tas, et une application intéressante, à l’article sur les algorithmes de tri.

This document was translated from L^AT_EX by H^EV^EA.