Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Structures de données élémentaires
Article mis en ligne le 5 avril 2006
dernière modification le 1er mai 2007

par Laurent Bloch

"http://www.w3.org/TR/REC-html40/loose.dtd">



Auteurs : William Saurin, Laurent Bloch

Pile

Une pile est une structure de données qui permet de stocker des éléments. La caractéristique des pile est que l'élément le plus récemment stocké sera le premier qui pourra être retrouvé et ôté de la pile. On trouve dans la littérature anglophone le nom de LIFO (Last in First out) pour les piles. Les opérations élémentaires qui doivent s'appliquer sur les piles sont un prédicat: pile-vide(p), et deux modificateur de piles: empiler(x,p) qui permet d'ajouter un élément à une pile, et depiler(p) qui ôte et retourne le plus récent élément de la pile. Si une pile est vide, depiler doit traiter le cas par exemple en appliquant une routine d'erreur.

(define *STACK* (make-vector 1000)) (define *STACK-INDEX* 0) (define (stack:push v) (vector-set! *STACK* *STACK-INDEX* v) (set! *STACK-INDEX* (+ *STACK-INDEX* 1)) ) (define (stack:pop) (set! *STACK-INDEX* (- *STACK-INDEX* 1)) (vector-ref *STACK* *STACK-INDEX*) )


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

Nom de l'algo : retourner-tableau Entrée : E; un tableau Sortie : E; un tableau dans lequel les éléments apparaissent en ordre inverse de leur ordre initial. Variables: P une pile pour i allant de 0 à (longueur de E) -1 faire empiler(E[i], P); fait pour i allant de 0 à (longueur de E) - 1 faire E[i] <- depiler(P); fait retourner E


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)



(define (creer-file) (vector "*FILE*" (cons '() '()))) (define (file? F) (and (vector? F) (pair? (vector-ref F 1)) (list? (car (vector-ref F 1))) (list? (cdr (vector-ref F 1))))) (define (file-vide? F) (and (file? F) (null? (car (vector-ref F 1))))) (define (tete-file F) (and (file? F) (if (file-vide? F) (error "tete-file" F "vide") (caar (vector-ref F 1))))) (define (enfiler! v F) (and (file? F) (let ((doublet (cons v '()))) (if (null? (car (vector-ref F 1))) (set-car! (vector-ref F 1) doublet) (set-cdr! (cdr (vector-ref F 1)) doublet)) (set-cdr! (vector-ref F 1) doublet)))) (define (defiler! F) (and (file? F) (if (file-vide? F) (error "defiler!" F "vide") (begin (set-car! (vector-ref F 1) (cdar (vector-ref F 1))) F))))


Utilisation :

1:=> (define Q (creer-file)) Q 1:=> (enfiler! Q 0) #unspecified 1:=> (enfiler! Q 1) #unspecified 1:=> (enfiler! Q 2) #unspecified 1:=> (enfiler! Q 3) #unspecified 1:=> Q (file (0 1 2 . #0=(3)) . #0#) 1:=> (defiler Q) 0 1:=> Q (file (1 2 . #0=(3)) . #0#) 1:=> (defiler Q) 1 1:=> Q (file (2 . #0=(3)) . #0#) 1:=> (defiler Q) 2 1:=> (defiler Q) 3 1:=> (defiler Q) *** ERROR:defiler: (file () 3) -- debordement


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


Pour implanter ce type de données abstrait (ADT, comme Abstract Data TYpe) file, nous définissons d'une part une interface de programmation (API, comme Application programming interface), c'est-à-dire une collection de procédures destinées à l'usage du programmeur qui aurait besoin d'une structure de données de type file, d'autre part des procédures internes au type, privées, qui en constituent l'implémentation mais qui doivent rester cachées pour le monde extérieur, et n'être utilisées que par les auteurs du type.

Les opérations que nous souhaitons proposer dans l'API sont les suivantes :
  • 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).
Nous pouvons (devons) définir les invariants du type, c'est-à-dire un certain nombre de propriétés caractéristiques qui doivent être vérifiées après toute opération, et dont la non vérification signalerait une erreur :

Soit F une file représentée par un vecteur de trois cases :

longueur-file = (vector-ref F 0)                     (1)
pos-tete-file = (vector-ref F 1)                     (2)
file-alveoles = (vector-ref F 2)                     (3)
longueur-alveoles = (vector-length (file-alveoles F))                     (4)


les invariants sont :
  • 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)]
Les procédures privées du type file, en quelque sorte la boîte à outils nécessaire à sa réalisation, sont ici :

;; La longueur 8 est arbitraire (define *LONGUEUR-MAX* 8) ;; La file est implantée comme un vecteur de trois cases ;; La case de rang 0 contient la longueur de la file (define (fixe-longueur-file! F la-longueur) (vector-set! F 0 la-longueur)) ;; La case de rang 1 contient le rang de la tête de file ;; dans la tableau d'alvéoles (define (pos-tete-file F) (vector-ref F 1)) ;; On peut déplacer le curseur sur la tête de file (define (fixe-tete-file! F la-tete) (vector-set! F 1 la-tete)) ;; La case de rang 2 contient le tableau des alvéoles ;; qui contiennent les éléments de la file (define (file-alveoles F) (vector-ref F 2)) (define (fixe-file-alveoles! F les-alveoles) (vector-set! F 2 les-alveoles)) ;; La procédure from-to-do définit une itérative ;; simple qui peut être utile à d'autres usages (define (from-to-do start stop body) (if (> start stop) 'done (begin (body start) (from-to-do (+ 1 start) stop body))))


Autre procédure privée :

(define (allonger-file! F) (let ((longueur (longueur-file F)) (tete (pos-tete-file F)) (alveoles (file-alveoles F))) (let ((longueur-alveoles (vector-length alveoles))) (let ((alveoles-fraiches (make-vector (* 2 longueur-alveoles)))) (from-to-do 0 (- longueur 1) (lambda (i) (vector-set! alveoles-fraiches i (vector-ref alveoles (remainder (+ tete i) longueur-alveoles))))) (fixe-tete-file! F 0) (fixe-file-alveoles! F alveoles-fraiches) F))))


Les procédures publiées, de l'API, commencent ici :

(define (creer-file) (let ((entete (make-vector 3)) (alveoles (make-vector *LONGUEUR-MAX*))) (fixe-longueur-file! entete 0) (fixe-tete-file! entete 0) (fixe-file-alveoles! entete alveoles) entete)) (define (file? o) (and (vector? o) (number? (vector-ref o 0)) (number? (vector-ref o 1)) (vector? (vector-ref o 2)))) (define (file-vide? F) (zero? (longueur-file F))) (define (longueur-file F) (vector-ref F 0)) (define (tete-file F) (if (file-vide? F) (error "tete-file" F "vide") (vector-ref (file-alveoles F) (pos-tete-file F))))


Autre procédure publiée :

(define (enfiler! x F) (let ((longueur (longueur-file F)) (tete (pos-tete-file F)) (alveoles (file-alveoles F))) (if (= longueur (vector-length alveoles)) (begin (allonger-file! F) (enfiler! x F)) (begin (vector-set! alveoles (remainder (+ tete longueur) (vector-length alveoles)) x) (fixe-longueur-file! F (+ longueur 1)) F)))) (define (defiler! F) (and (not (file-vide? F)) (let ((longueur (longueur-file F)) (tete (pos-tete-file F)) (alveoles (file-alveoles F))) (fixe-longueur-file! F (- longueur 1)) (fixe-tete-file! F (remainder (+ 1 tete) (vector-length alveoles))) F)))


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 LATEX by HEVEA.