Chapitre 11 : structures de données
MPSI - Option informatique - 2017/2018

Une structure de données est l'association :

  • d'un ou de plusieurs types servant à contenir des données
  • de fonctions, appelées primitives d'accès, servant à manipuler ces données.

On distingue la structure abstraite de la structure concrète. La structure abstraite, également appelée interface ou spécification, décrit la structure du point de vue du programmeur qui l'utilise. C'est le mode d'emploi de la structure. La structure concrète est la façon dont est implémentée la structure. Les types abstraits deviennent des types Caml parfaitement définis et les primitives des fonctions Caml codées selon des algorithmes précis.

La structure de piles

La caractéristique fondamentale d'une pile est que la valeur que l'on extrait est toujours la dernière valeur à avoir été placée dans la pile. On parle de structure LIFO (Last In Fast Out).

Structure abstraite de pile

La structure abstraite de pile peut être décrite par l'embryon de code Caml ci-dessous :

type 'a stack

exception Stack_empty

(** Retourne une nouvelle pile vide *)
let create () : 'a stack = ???

(** Indique si la pile s est vide *)
let is_empty (s : 'a stack) : bool = ???

(** Retourne la valeur du sommet de la pile s *)
let peek (s : 'a stack) : 'a = ???

(** Ajoute la valeur x sur le sommet de la pile s *)
let push (s : 'a stack) (x : 'a) : unit = ???

(** Supprime et retourne la valeur du sommet de la pile s *)
let pop (s : 'a stack) : 'a = ???

Le dernier élément placé dans la pile est appelé le sommet de la pile. Les primitives push et pop permettent respectivement d'ajouter ou de retirer un élément. Cette propriété ressemble à celle des listes chaînées Caml, le sommet correspondant à la tête de la liste. La différence réside dans le fait que, contrairement aux listes, les piles sont des structures impératives. La fonction create permet de créer une valeur de type 'a stack destinée à mémoriser les éléments de la pile. Il s'agit d'un type mutable et l'effet des fonctions push et pop est précisément de modifier cette valeur.

Une implémentation de pile

Une façon simple d'implémenter une pile en Caml est de définir le type 'a stack par une référence sur une liste.

In [ ]:
type 'a stack = 'a list ref ;;

exception Stack_empty ;;

(** Retourne une nouvelle pile vide *)
let create () : 'a stack = ref []

(** Indique si la pile s est vide *)
let is_empty (s : 'a stack) : bool =
  !s = []
;;

(** Retourne la valeur du sommet de la pile s *)
let peek (s : 'a stack) : 'a =
  match !s with
  | [] -> raise Stack_empty
  | x :: xq -> x
;;

(** Ajoute la valeur x sur le sommet de la pile s *)
let push (s : 'a stack) (x : 'a) : unit =
  s := x :: !s
;;

(** Supprime et retourne la valeur du sommet de la pile s *)
let pop (s : 'a stack) : 'a =
  match !s with
  | [] -> raise Stack_empty
  | x :: xq -> s := xq ; x
;;
Out[ ]:
type 'a stack = 'a list ref
Out[ ]:
exception Stack_empty
Out[ ]:
val create : unit -> 'a stack = <fun>
Out[ ]:
val is_empty : 'a stack -> bool = <fun>
Out[ ]:
val peek : 'a stack -> 'a = <fun>
Out[ ]:
val push : 'a stack -> 'a -> unit = <fun>
Out[ ]:
val pop : 'a stack -> 'a = <fun>
In [ ]:
let my_stack = create () ;;

for i = 0 to 5 do
  push my_stack (i * i)
done ;;

while not (is_empty my_stack) do
  print_int (pop my_stack) ;
  print_newline ()
done ;;
25
16
9
4
1
0
Out[ ]:
val my_stack : '_a stack = {contents = []}
Out[ ]:
- : unit = ()
Out[ ]:
- : unit = ()

Rien n'interdit malheureusement le programmeur d'accéder directement à la valeur my_stack :

In [ ]:
my_stack := [7; 8] ;;
pop my_stack ;;
my_stack ;;
Out[ ]:
- : unit = ()
Out[ ]:
- : int = 7
Out[ ]:
- : int stack = {contents = [8]}

L'encapsulation d'une structure

Le postulat de base de la programmation structurée est que le programmeur ne manipule jamais directement la valeur de type 'a stack. Il utilise systématiquement les primitives d'accès décrites dans la structure abstraite. Ceci contribue ainsi à produire du code modulaire où il devient possible de modifier certaines parties sans en perturber d'autres. On peut ainsi imaginer de modifier l'implémentation de la pile en remplaçant la référence de liste par un tableau. Si le programmeur qui utilise la structure a respecté l'interface, alors son code fonctionnera tout aussi bien.

Le langage Caml comporte une syntaxe pour encapsuler proprement les structures de données. Il n'est pas nécessaire que vous connaissiez cette syntaxe, mais elle peut contribuer à vous faire bien comprendre cette notion essentielle de structures de données.

Ci-dessous, on a simplement encadré le code Caml de la structure de pile entre un

module Stack = struct

et un

end.

Nous avons également suivi la convention habituelle qui consiste à nommer 'a t plutôt que 'a stack le type principal de la structure.

In [ ]:
module Stack = struct
  type 'a t = 'a list ref

  exception Stack_empty

  (** Retourne une nouvelle pile vide *)
  let create () : 'a t = ref []

  (** Indique si la pile s est vide *)
  let is_empty (s : 'a t) : bool =
    !s = []

  (** Retourne la valeur du sommet de la pile s *)
  let peek (s : 'a t) : 'a =
    match !s with
    | [] -> raise Stack_empty
    | x :: xq -> x

  (** Ajoute la valeur x sur le sommet de la pile s *)
  let push (s : 'a t) (x : 'a) : unit =
    s := x :: !s

  (** Supprime et retourne la valeur du sommet de la pile s *)
  let pop (s : 'a t) : 'a =
    match !s with
    | [] -> raise Stack_empty
    | x :: xq -> s := xq ; x
end
Out[ ]:
module Stack :
  sig
    type 'a t = 'a list ref
    exception Stack_empty
    val create : unit -> 'a t
    val is_empty : 'a t -> bool
    val peek : 'a t -> 'a
    val push : 'a t -> 'a -> unit
    val pop : 'a t -> 'a
  end

La structure s'utilise alors de cette façon :

In [ ]:
let my_stack = Stack.create () ;;

for i = 0 to 5 do
  Stack.push my_stack (i * i)
done ;;

while not (Stack.is_empty my_stack) do
  print_int (Stack.pop my_stack) ;
  print_newline ()
done ;;
25
16
9
4
1
0
Out[ ]:
val my_stack : '_a Stack.t = {contents = []}
Out[ ]:
- : unit = ()
Out[ ]:
- : unit = ()

Caml dispose également d'une syntaxe pour définir les structures abstraites :

In [ ]:
module type STACK = sig
  type 'a t
  exception Stack_empty
  val create : unit -> 'a t
  val is_empty : 'a t -> bool
  val peek : 'a t -> 'a
  val push : 'a t -> 'a -> unit
  val pop : 'a t -> 'a
end
Out[ ]:
module type STACK =
  sig
    type 'a t
    exception Stack_empty
    val create : unit -> 'a t
    val is_empty : 'a t -> bool
    val peek : 'a t -> 'a
    val push : 'a t -> 'a -> unit
    val pop : 'a t -> 'a
  end

La création d'une structure concrète qui implémente la structure abstraite STACK peut alors s'écrire de cette façon :

In [ ]:
module Stack : STACK = struct
  type 'a t = 'a list ref

  exception Stack_empty

  (** Retourne une nouvelle pile vide *)
  let create () : 'a t = ref []

  (** Indique si la pile s est vide *)
  let is_empty (s : 'a t) : bool =
    !s = []

  (** Retourne la valeur du sommet de la pile s *)
  let peek (s : 'a t) : 'a =
    match !s with
    | [] -> raise Stack_empty
    | x :: xq -> x

  (** Ajoute la valeur x sur le sommet de la pile s *)
  let push (s : 'a t) (x : 'a) : unit =
    s := x :: !s

  (** Supprime et retourne la valeur du sommet de la pile s *)
  let pop (s : 'a t) : 'a =
    match !s with
    | [] -> raise Stack_empty
    | x :: xq -> s := xq ; x
end
Out[ ]:
module Stack : STACK
In [ ]:
let my_stack = Stack.create () ;;

for i = 0 to 5 do
  Stack.push my_stack (i * i)
done ;;
Out[ ]:
val my_stack : '_a Stack.t = <abstr>
Out[ ]:
- : unit = ()

Le programmeur n'a maintenant plus aucun moyen d'accéder directement à la valeur my_stack :

In [ ]:
my_stack
Out[ ]:
- : int Stack.t = <abstr>
In [ ]:
my_stack := [7; 8]
Out[ ]:
File "[10]", line 1, characters 0-8:
Error: This expression has type int Stack.t
       but an expression was expected of type 'a ref
Characters 0-8:
  my_stack := [7; 8]
  ^^^^^^^^

Évaluation d'une expression arithmétique

Les expressions arithmétiques sont habituellement écrites en notation infixe, c'est-à-dire en plaçant les opérateurs binaires entre leurs deux arguments. Ceci nécessite des parenthèses pour préciser la hiérarchie des calculs. La formule $\frac{1+2\sqrt{3}}{4}$ s'écrit ainsi :

(1 + ( 2 * ( sqrt 3 ) ) ) / 4.

Une autre écriture possible est la notation postfixée, où les deux arguments sont placés avant l'opérateur. Cette même formule s'écrit alors :

1 2 3 sqrt * + 4 /

Nous allons voir comment, à l'aide d'une pile, évaluer une expression postfixée. La première étape consiste à découper la chaîne de caractères en ses éléments de base appelés tokens. On définit pour cela le type token :

In [ ]:
type token  = 
  | Num of float
  | Binary_op of string
  | Unary_op of string
;;
Out[ ]:
type token = Num of float | Binary_op of string | Unary_op of string

Il faut ensuite associer à chaque token de type opération, la fonction Caml qui lui correspond. Ceci est fait à l'aide d'une liste de couples :

In [ ]:
let unary_ops = [
  ("sqrt", sqrt)
] ;;

let binary_ops = [
  ("+", ( +. ) ) ;
  ("-", ( -. ) ) ;
  ("*", ( *. ) ) ;
  ("/", ( /. ) )
] ;;
Out[ ]:
val unary_ops : (string * (float -> float)) list = [("sqrt", <fun>)]
Out[ ]:
val binary_ops : (string * (float -> float -> float)) list =
  [("+", <fun>); ("-", <fun>); ("*", <fun>); ("/", <fun>)]

L'analyse lexicale de l'expression consiste à produire la liste des tokens à partir du texte de l'expression. Ceci est réalisé par la fonction lexer ci-dessous. Il n'est pas nécessaire pour la suite de comprendre ce code.

In [ ]:
exception Syntax_error ;;

#load "str.cma";;
let lexer (expr : string) : token list =
  List.map
    (fun t ->
      try Num (float_of_string t)
      with Failure _ ->
        if List.mem_assoc t unary_ops then Unary_op t
        else if List.mem_assoc t binary_ops then Binary_op t
        else raise Syntax_error
    )
    @@ Str.split (Str.regexp "[ ]+") expr
;;
Out[ ]:
exception Syntax_error
Out[ ]:
val lexer : string -> token list = <fun>
In [ ]:
lexer "1 2 3 sqrt * + 4 /"
Out[ ]:
- : token list =
[Num 1.; Num 2.; Num 3.; Unary_op "sqrt"; Binary_op "*"; Binary_op "+";
 Num 4.; Binary_op "/"]

Fonction d'évaluation de l'expression

Voici le principe de l'algorithme :

Lire un token
Si le token est un nombre, ajouter le nombre dans la pile
sinon si le token est une opération unaire
  Retirer un nombre de la pile
  Effectuer l'opération sur ce nombre
  Ajouter le résultat dans la pile
sinon si le token est une opération binaire
  Retirer deux nombres de la pile
  Effectuer l'opération sur ces deux nombres
  Ajouter le résultat dans la pile
S'il reste des tokens à lire, recommencer au début
sinon la valeur de l'expression est l'unique nombre
présent dans la pile.
In [ ]:
let eval (expr : string) : float =
  let s = Stack.create () in
  let rec eval_rec ts =
    match ts with
    | [] -> 
      let value = Stack.pop s in
      if Stack.is_empty s then value
      else raise Syntax_error
    | t :: tq ->
      begin match t with
      | Num x -> Stack.push s x
      | Unary_op op ->
        let x = Stack.pop s in
        let f = List.assoc op unary_ops in
        Stack.push s (f x)
      | Binary_op op ->
        let x2 = Stack.pop s in
        let x1 = Stack.pop s in
        let f = List.assoc op binary_ops in
        Stack.push s (f x1 x2)
      end ;
      eval_rec tq
  in
  try eval_rec (lexer expr)
  with Stack.Stack_empty -> raise Syntax_error
;;
      
eval "1 2 3 sqrt * + 4 /"
Out[ ]:
val eval : string -> float = <fun>
Out[ ]:
- : float = 1.1160254037844386

Structure de file

Une structure de file est une structure FIFO (First In Firts Out). Le modèle est celui de la file d'attente. L'élément que l'on retire de la file est toujours premier à y être entré.

Structure abstraite de file

La structure abstraite d'une file est donnée par le code Caml suivant :

In [ ]:
module type QUEUE = sig

  type 'a t
  exception Queue_empty   (* Action invalide sur une file vide *)
  exception Queue_overflow (* Dépassement de capacité de file *)
  
  val create : unit -> 'a t
  (** Retourne une nouvelle file vide *)
  
  val is_empty : 'a t -> bool
  (** Indique si la file est vide *)
  
  val peek : 'a t -> 'a
  (** Retourne le plus ancien élément de la file 
      Lève l'exception Queue_empty si la file est vide *)
      
  val enqueue : 'a t -> 'a -> unit
  (** Ajoute un nouvel élément dans la file
      Lève l'exception Queue_overflow si la file est pleine *)
  
  val dequeue : 'a t -> 'a
  (** Supprime et retourne le plus ancien élément de la file 
      Lève l'exception Queue_empty si la file est vide *)

end
Out[ ]:
module type QUEUE =
  sig
    type 'a t
    exception Queue_empty
    exception Queue_overflow
    val create : unit -> 'a t
    val is_empty : 'a t -> bool
    val peek : 'a t -> 'a
    val enqueue : 'a t -> 'a -> unit
    val dequeue : 'a t -> 'a
  end

Une implémentation de structure de file

On verra comment implémenter la structure de file à l'aide d'un tableau

Structure persistante de file

Les structures de données que nous avons construites jusqu'ici sont toutes des structures impératives. Le type de base est un type mutable qui est modifié par effet de bord par les primitives d'accès à la structure. Pour écrire du code fonctionnel pur il faut pouvoir disposer de structures de données persistantes, c'est-à-dire immuables. Le rôle des primitives d'accès est alors de calculer une nouvelle structure à partir de la structure passée en argument. Cette dernière n'est pas modifiée par la fonction. Illustrons ceci en construisant une structure persistante de file. Sa définition abstraite est donnée par le code Caml ci-dessous :

In [ ]:
module type QUEUE = sig

  type 'a t
  exception Queue_empty
  
  val empty : 'a t
  (** File vide *)
  
  val is_empty : 'a t -> bool
  (** Indique si la file est vide *)
  
  val enqueue : 'a -> 'a t -> 'a t
  (** Ajoute un nouvel élément dans la liste *)
  
  val dequeue : 'a t -> 'a * 'a t
  (** Retire le plus ancien élément de la liste *)
  
end
Out[ ]:
module type QUEUE =
  sig
    type 'a t
    exception Queue_empty
    val empty : 'a t
    val is_empty : 'a t -> bool
    val enqueue : 'a -> 'a t -> 'a t
    val dequeue : 'a t -> 'a * 'a t
  end

Insistons bien, les fonctions enqueue et dequeue retournent une nouvelle file qui diffère de celle passée en argument par l'ajout, respectivement le retrait, d'un élément. La file passée en argument n'est pas modifiée.

Une file persistante peut être implémentée à l'aide de deux listes rear et front. La primitive enqueue ajoute les éléments dans la liste rear. Pour retirer un élément de la file, la primitive dequeue les prend dans la liste front. Si la liste front est vide, elle renverse au préalable la liste rear dans la liste front.

In [ ]:
module Queue : QUEUE = struct

  type 'a t = {
    rear : 'a list ; 
    front  : 'a list
  }

  exception Queue_empty

  let empty : 'a t = {rear = [] ; front = []}

  let is_empty (q : 'a t) : bool =
    q = {rear = [] ; front = []}
    
  let enqueue (x : 'a) (q : 'a t) : 'a t =
    {rear = x :: q.rear ; front = q.front}

  let dequeue (q : 'a t) : 'a * 'a t =
    match q with
    | {rear = [] ; front = []} -> raise Queue_empty
    | {rear = xs ; front = []} ->
      let xr = List.rev xs in List.hd xr, {rear = [] ; front = List.tl xr}
    | {rear = xs ; front = x :: xq} -> 
      x, {rear = xs ; front = xq}
end
Out[ ]:
module Queue : QUEUE
In [ ]:
let rec fill (q : int Queue.t) (n : int) =
  if n = 0 then q
  else fill (Queue.enqueue n q) (n - 1)
;;

fill Queue.empty 5 ;;
Out[ ]:
val fill : int Queue.t -> int -> int Queue.t = <fun>
Out[ ]:
- : int Queue.t = <abstr>
In [ ]:
let rec fill (q : int Queue.t) (n : int) =
  if n = 0 then q
  else fill (Queue.enqueue n q) (n - 1)
;;


let rec deq (q : int Queue.t) =
  if not (Queue.is_empty q) then
    let x, qq = Queue.dequeue q in
    print_int x ;
    print_newline () ;
    deq qq
in
deq (fill Queue.empty 5)
5
4
3
2
1
Out[ ]:
val fill : int Queue.t -> int -> int Queue.t = <fun>
Out[ ]:
- : unit = ()

Parcours en largeur d'un arbre binaire

Lorsque nous avons étudié les arbres binaires nous avons écrit des fonctions pour parcourir les noeuds et les feuilles d'un arbre. Nous avons ainsi présenté les parcours préfixe, infixe et postfixe. Ces trois types de parcours étaient tous des parcours en profondeur. Les fonctions parcourent récursivement tous les noeuds de la branche de gauche avant de s'intéresser à la branche de droite. Nous présentons maintenant un type très différent de parcours, appelé parcours en largeur. L'idée est de parcourir tous les noeuds de profondeur $n$ avant de passer aux noeuds de profondeur $n+1$. Ainsi par exemple, les noeuds de l'arbre ci-dessous seront parcourus dans l'ordre croissant de leurs étiquettes.

In [ ]:
type tree =
  | Nil
  | Node of int * tree * tree
;;

let t1 =
  Node (
    1,
    Node (
      2,
      Node (
        4,
        Node (7, Nil, Nil),
        Node (8, Nil, Nil)
      ),
      Node (5, Nil, Nil)
    ),
    Node (
      3,
      Nil,
      Node (
        6,
        Node (9, Nil, Nil),
        Node (10, Nil, Nil)
      )
    )
  )
;;
Out[ ]:
type tree = Nil | Node of int * tree * tree
Out[ ]:
val t1 : tree =
  Node (1,
   Node (2, Node (4, Node (7, Nil, Nil), Node (8, Nil, Nil)),
    Node (5, Nil, Nil)),
   Node (3, Nil, Node (6, Node (9, Nil, Nil), Node (10, Nil, Nil))))

Pour rappel, voici une fonction de parcours en profondeur selon l'ordre préfixe :

In [ ]:
let rec parcours_en_profondeur (t : tree) : unit =
  match t with
  | Nil -> ()
  | Node (x, tg, td) ->
    print_int x ;
    print_char ' ' ;
    parcours_en_profondeur tg ;
    parcours_en_profondeur td
;;

parcours_en_profondeur t1 ;;
1 2 4 7 8 5 3 6 9 10 
Out[ ]:
val parcours_en_profondeur : tree -> unit = <fun>
Out[ ]:
- : unit = ()

Le parcours en largeur utilise une file. On place dans la file la racine de l'arbre puis, tant qu'il reste des éléments dans la file, on effectue les actions suivantes :

Retirer un noeud de la file
Imprimer ce noeud
Ajouter le fils gauche dans la file
Ajouter le fils droit dans la file
In [ ]:
open Queue

let parcours_en_largeur (t : tree) : unit =
  let rec parcours q =
    if not (is_empty q) then
      let t, qq = dequeue q in
      match t with
      | Nil                   -> parcours qq
      | Node (x, left, right) ->
        print_int x ;
        print_char ' ' ;
        qq |> enqueue left 
           |> enqueue right
           |> parcours
  in
  parcours (enqueue t empty)
;;

parcours_en_largeur t1 ;;
1 2 3 4 5 6 7 8 9 10 
Out[ ]:
val parcours_en_largeur : tree -> unit = <fun>
Out[ ]:
- : unit = ()
In [ ]:
open Queue

let parcours_en_largeur (t : tree) : unit =
  let rec parcours q =
    if not (is_empty q) then begin
      let t, qq = dequeue q in
      match t with
      | Nil                   -> parcours qq
      | Node (x, left, right) ->
        print_int x ;
        print_char ' ' ;
        parcours (enqueue right (enqueue left qq))
    end
  in
  parcours (enqueue t empty)
;;

parcours_en_largeur t1 ;;
1 2 3 4 5 6 7 8 9 10 
Out[ ]:
val parcours_en_largeur : tree -> unit = <fun>
Out[ ]:
- : unit = ()

L'instruction open Queue permet de désigner les valeurs du module Queue sans avoir à les faire précéder du préfixe Queue. C'est l'équivalent du from module import * de Python.

Pour les plus avancés uniquement, voici une seconde version qui utilise le mécanisme d'exception au lieu de tester si la file est vide à chaque appel récursif et qui utilise l'opérateur infixe d'application inverse de fonction.

In [ ]:
open Queue

let parcours_en_largeur (t : tree) : unit =
  let rec parcours q =
    try
      let t, qq = dequeue q in
      match t with
      | Nil                   -> parcours qq
      | Node (x, left, right) ->
        print_int x ;
        print_char ' ' ;
        qq |> enqueue left 
           |> enqueue right
           |> parcours
    with Queue_empty -> ()
  in
  parcours (enqueue t empty)
;;

parcours_en_largeur t1 ;;
1 2 3 4 5 6 7 8 9 10 
Out[ ]:
val parcours_en_largeur : tree -> unit = <fun>
Out[ ]:
- : unit = ()