Chapitre 3    Structures de données élémentaires

• tester si l'ensemble E est vide.
• ajouter l'élément x à l'ensemble E.
• vérifier si l'élément x appartient à l'ensemble E.
• supprimer l'élément x de l'ensemble E.

3.1  Listes chaînées

class Liste {

  int contenu;
  Liste suivant;

  Liste (int x, Liste a) {
      contenu = x;
      suivant = a;
  }
}

---

Figure 3.1 : Ajout d'un élément dans une liste

---

static boolean estVide (Liste a) {  

  return a == null;
}

static Liste ajouter (int x, Liste a) {

  return new Liste (x, a);   // L'ancienne tête se retrouve après x
}

static boolean recherche (int x, Liste a) {

  while (a != null) {
      if (a.contenu == x)
          return true;
      a = a.suivant;
  }
  return false;
}

---

Figure 3.2 : Suppression d'un élément dans une liste

---

static boolean recherche (int x, Liste a) {

  if (a == null) 
      return false;
  else if (a.contenu == x) 
      return true;       
  else 
      return recherche (x, a.suivant);
}

static boolean recherche (int x, Liste a) {

  if (a == null) 
      return false;
  else 
      return (a.contenu == x) || recherche (x, a.suivant);
}

static boolean recherche (int x, Liste a) {

  return a != null && (a.contenu == x || recherche (x, a.suivant));
}

Liste = {Liste_vide}  È   Element × Liste

static int longueur(Liste a) {

  if (a == null)
      return 0;
  else
      return 1 + longueur (a.suivant);
}

static int longueurI(Liste a) {

  int   longueur = 0;
  while (a != null) {
      ++longueur;
      a = a.suivant;
  }
  return longueur;
} 

static Liste supprimer (int x, Liste a) {

  if (a != null)
      if (a.contenu == x)
          a = a.suivant;
      else 
          a.suivant = supprimer (x, a.suivant);
  return a;      
}

static Liste supprimer (int x, Liste a) { 

  if (a != null)
      if (a.contenu == x)
          a = a.suivant;
      else {
          Liste b = a ;
          while (b.suivant != null && b.suivant.contenu != x) 
              b = b.suivant;
          if (b.suivant != null) 
              b.suivant = b.suivant.suivant;
      } 
  return a;       
}

static Liste supprimer (int x, Liste a) { 

  if (a != null)
      return null;
  else if (a.contenu == x)
      return a.suivant;
  else
      return new Liste (a.contenu, supprimer (x, a.suivant));
}

Remarque

Exemple

static Liste listePremier (int n) {

  Liste  a = null;
  int    k;

  for (int i = n; i >= 2; --i) {
       a = ajouter (i, a);
  } 
  k = a.contenu; 
  for (Liste b = a; k * k <= n ; b = b.suivant){ 
      k = b.contenu;   
      for (int j = k; j <= n/k; ++j) 
          a = supprimer (j * k, a);
      }
  return(a); 
}

Remarque

Exemple

Liste al[] = new Liste[N-1];

static void insertion (String x, int val) {

    int i = h(x);
    al[i] = ajouter (x, al[i]);
}

static int recherche (String x) {

  for (int a = al[h(x)]; a != null; a = a.suivant) {
      if (x.equals(nom[a.contenu]))
          return tel[a.contenu];
  }
  return -1;
}

3.2  Files

• estVide est une application de Fil(E) dans (vrai, faux), estVide(F) est égal à vrai si et seulement si la file F est vide.
• ajouter est une application de E × Fil(E) dans Fil(E), ajouter(x,F) est la file obtenue à partir de la file F en insérant l'élément x à la fin de celle-ci.
  
  
• valeur est une application de Fil(E) \ F₀ dans E qui à une file F non vide associe l'élément se trouvant en tête.
• supprimer est une application de Fil(E) \ F₀ dans Fil(E) qui associe à une file F non vide la file obtenue à partir de F en supprimant son premier élément.

---

Figure 3.3 : File gérée par un tableau circulaire

---

• la file d'attente est vide si et seulement si début = fin,
  
  
• lorsqu'un nouveau client arrive on incrémente fin et on donne ce numéro au client,
  
  
• lorsque le serveur est libre et peut servir un autre client, si la file n'est pas vide, il incrémente début et appelle le possesseur de ce numéro.

class File {

  final static int MaxF = 100;

  int         debut;
  int         fin;
  boolean     pleine, vide;
  int         contenu[];    

  File () {
    debut = 0; fin = 0;
    pleine = false; vide = true;
    contenu = new int[MaxF];
  } 

  static File vide () {
    return new File();
  }

  static void faireVide (File f) {
    f.debut = 0; f.fin = 0;
    f.pleine = false; f.vide = true;
  }

  static boolean estVide(File f) {
    return  f.vide;
  }

  static boolean estPleine(File f) {
    return  f.pleine;
  }

  static int valeur (File f) {
    if (f.vide)
        erreur ("File Vide.");
    return  f.contenu[f.debut];
  }

  private static int Successeur(int i) {
    return  (i+1) % MaxF;
  }

  static void ajouter (int x, File f) {
    if (f.pleine)
        erreur ("File Pleine.");
    f.contenu[f.fin] = x;
    f.fin = Successeur(f.fin);
    f.vide = false;
    f.pleine = f.fin == f.debut;
  }

  static void supprimer (File f) {
    if (f.vide)
        erreur ("File Vide.");
    f.debut =  Successeur(f.debut);
    f.vide = f.fin == f.debut;
    f.pleine = false;
  }
}

class File {
        
    Liste debut;
    Liste fin;

  File (Liste a, Liste b)  {
    debut = a;
    fin = b;
  }
  
  static File vide () {
    Liste garde = new Liste();   
    return new File (garde, garde);
  }

  static void faireVide (File f) {
    Liste garde = new Liste();   
    f.debut = f.fin = garde;
  }

  static boolean estVide (File f) { 
    return f.debut == f.fin;
  }

  static int valeur (File f) {
    Liste b = f.debut.suivant;
    return b.contenu;
  }

  static void ajouter (int x, File f) {
    Liste a = new Liste (x, null);
    f.fin.suivant = a;
    f.fin = a;
  }

  static void supprimer (File f) {   
    if (estVide (f))
        erreur ("File Vide.");
    f.debut = f.debut.suivant;
  }
}

---

Figure 3.4 : File d'attente implémentée par une liste

---

3.3  Piles

class Pile {

  final static int maxP = 100;

  int          hauteur ;
  Element      contenu[];

  Pile ()  {
     hauteur = 0;
     contenu = new Element[maxP];
  }

  static File vide () {
    return new Pile();
  }

  static void faireVide (Pile p) {
    p.hauteur = 0;
  }

  static boolean estVide (Pile p) {
    return p.hauteur == 0;
  }

  static boolean estPleine (Pile p) {
    return p.hauteur == maxP;
  }

  static void ajouter (Element x, Pile p) 
      throws ExceptionPile
  {
    if (estPleine (p))
         throw new ExceptionPile("pleine");
    p.contenu[p.hauteur] = x;
    ++ p.hauteur;
  }

  static Element valeur (Pile p) 
      throws ExceptionPile
  {
    if (estVide (p)) 
        throw new ExceptionPile("vide");
    return p.contenu [p.hauteur - 1];
   }

  static void supprimer (Pile p) 
      throws ExceptionPile
  {
    if (estVide (p)) 
        throw new ExceptionPile ("vide");
    -- p.hauteur;
  }
}

class ExceptionPile extends Exception {
  String nom;

  public ExceptionPile (String x) {
      nom = x;
  }
}

Remarques

3.4  Evaluation des expressions arithmétiques préfixées

• des symboles parmi les 4 suivants: + * ( )
  
  
• des entiers naturels

(+ e1 e2)          (* e1 e2)

47
(* 2 3)
(+ 12 8)
(+ (* 2 3) (+ 12 8))
(+ (*  (+ 35 36) (+ 5 6)) (* (+ 7 8) (* 9 9)))

class Element {
  boolean       estOperateur; 
  int           valeur;
  char          valsymb;
}

static int calculer (char a, int x, int y) {

  switch (a) {
      case '+': return x + y;
      case '*': return x * y;
  }
  return -1;
}

---

+

*     +

+     *     +

35     +     *     +

71     *     +

+     71     *     +

5     +     71     *     +

781     +

*     781     +

+     *     781     +

7     +     *     781     +

*     15     *     781     +

9     *     15     *     781     +

Figure 3.5 : Pile d'évaluation de l'expression dont le résultat est 1996

---

static void inserer (Element x, Pile p) 
    throws ExceptionPile
{
  Element    y, op;

  while (!(Pile.estVide(p)  || x.estOperateur ||
                          Pile.valeur(p).estOperateur))  {
      y = Pile.valeur(p);
      Pile.supprimer(p);
      op = Pile.valeur(p);
      Pile.supprimer(p);
      x.valeur = calculer (op.valsymb, x.valeur, y.valeur);
  }
  Pile.ajouter(x,p);
}

static int evaluer (Element u[])
    throws ExceptionPile
{
  Pile p = new Pile();

  for (int i = 0; i < u.length ; ++i) {
      inserer (u[i], p);
  }
  return Pile.valeur(p).valeur;
}

public static void main (String args[]) {

  Element exp[] = new Element [args.length];

  for (int i = 0; i < args.length; ++i) {
     String s = args[i];
     if (s.equals ("+") || s.equals ("*"))
         exp[i] = new Element (true, 0, s.charAt(0));
     else
         exp[i] = new Element (false, Integer.parseInt(s), ' ');
  }    
  try {
      System.out.println (evaluer (exp));
  } catch (ExceptionPile x) {
      System.err.println ("Pile " + x.nom);
  }
}

3.5  Opérations courantes sur les listes

---

Figure 3.6 : Queue d'une liste

---

class Liste {

  Object contenu;
  Liste suivant;

  Liste (Object x, Liste a) {
      contenu = x;
      suivant = a;
  }

  static Liste cons (Object x, Liste a) {
    return new Liste (x, a);
  }

  static Object head (Liste a) {
    if (a == null)
        erreur ("Head d'une liste vide.");
    return a.contenu;
  }

  static Liste tail (Liste a) {
    if (a == null) 
        erreur ("Tail d'une liste vide.");
    return a.suivant;
  }

---

Figure 3.7 : Concaténation de deux listes par Append

---

static Liste append (Liste a, Liste b) {
  if (a == null)
      return b;
  else
      return ajouter (a.contenu, append (a.suivant, b)) ;
}

static Liste nConc (Liste a, Liste b) {
  if (a == null) 
      return b;
  else {
      Liste c = a;
      while (c.suivant != null) 
           c = c.suivant; 
      c.suivant = b;
      return a;
  }
}

static Liste nConc (Liste a, Liste b) {
  if (a == null) 
      return b;
  else {
      a.suivant = nConc (a.suivant, c);
      return a;
  }
}

---

Figure 3.8 : Concaténation de deux listes par Nconc

---

---

Figure 3.9 : Transformation d'une liste au cours de nReverse

---

static Liste nReverse (Liste a) {
  Liste b = null;
  while (a != null) {
      Liste c = a.suivant;
      a.suivant = b;
      b = a;
      a = c;
  }
 return b;
}

static Liste reverse (Liste a) {
  if (a == null)
      return  a;
  else
      return  append (reverse (a.suivant), 
                      ajouter (a.contenu, null));
} 

static Liste nReverse (Liste a) {
  return nReverse1 (null, a);
}

static Liste nReverse1 (Liste b, Liste a) {
  if (a == null)
      return b;
  else
      return nReverse1 (ajouter (a.contenu, b), a.suivant);
}

---

Figure 3.10 : Liste circulaire gardée

---

static Liste inserer (int v, Liste a) {

  Liste b = a;
  while (b.suivant != a && v > head(b.suivant))
      b = b.suivant;
  b.suivant = ajouter (v, b.suivant);        
  a.contenu = head(a) + 1;
  return a;
}   

3.6  Programmes en Caml

/* Déclaration des listes, voir page X */

type element == int;;

type liste = Nil | Cons of cellule

and cellule =
  { mutable contenu : element;
    mutable suivant : liste };;

(* Liste vide, voir page X *)
let estVide a =
  a = Nil;;

(* Ajouter, voir page X *)
let ajouter x a =
  Cons {contenu = x; suivant = a};;

(* Recherche, voir page X *)
let recherche x a =
 let l = ref a in
 let result = ref false in
 while !l <> Nil do
  match !l with
  | Cons {contenu = y; suivant = s} ->
     if x = y then result := true
     else l := s
  | _ -> ()
 done;
 !result;;

(* Recherche récursive, voir page X *)
let recherche x a =
  match a with
    Nil -> false
  | Cons {contenu = y; suivant = s} ->
     if x = y then true
     else recherche x s;;

let recherche x a =
  match a with
    Nil -> false
  | Cons {contenu = y; suivant = s} ->
     x = y || recherche x s;;

(* Longueur d'une liste, voir page X *)
let rec longueur = function
    Nil -> 0
  | Cons {suivant = reste; _} ->
      1 + longueur reste;;

(* Longueur d'une liste, voir page X *)
let longueur a =
  let r = ref 0
  and accu = ref a in
  while !accu <> Nil do
    incr r;
    match !l with
    | Cons {suivant = reste; _} ->
        accu := reste
    | _ -> ()
  done;
  !r;;

(* Supprimer, voir page X *)
let rec supprimer x a =
   match a with
   Nil -> a
 | Cons ({contenu = c; suivant = s} as cellule) ->
    if c = x then s
    else begin 
      cellule.suivant <- supprimer x s;
      a
    end;;

let rec supprimer x a =
   match a with
   Nil -> Nil
 | Cons {contenu = c; suivant = s} ->
    if c = x then s
    else Cons {contenu = c; suivant = s};;

(* Liste des nombres premiers, voir page X *)
let liste_premier n =
  let a = ref Nil in
  for i = n downto 2 do ajouter i a done;
  let k = ref 2 in
  let b = ref !a in
  while !k * !k <= n do
    match !b with
      Nil -> failwith "liste_premier"
    | Cons {contenu = c; suivant = s} ->
       k := c;
       for j = c to n / c do
         supprimer (j * !k) a done;
       b := s
  done;
  a;;

(* Les files avec des vecteurs, voir page X *)
let maxF = 100;;

type 'a file =
  { mutable debut: int;
    mutable fin: int;
    mutable pleine: bool;
    mutable vide: bool;
    contenu: 'a vect };;

let vide () = {debut = 0; fin = 0;
  pleine = false; vide = true; 
  contenu = make_vect maxF 0};;

let faireVide f = begin
  f.debut = 0; f.fin = 0;
  f.pleine = false; f.vide = true; 
  end;;

let estVide f = f.vide;;

let estPleine f = f.pleine;;

let valeur f = begin
  if f.vide then failwith "Pile vide.";
  f.contenu.(f.debut)
  end;;

let successeur x = (x + 1) mod maxF ;;

let ajouter x f = begin
  if f.pleine then failwith "Pile pleine.";
  f.contenu.(f.fin) <- x;
  f.fin <- successeur (f.fin);
  f.vide <- false;
  f.pleine <- f.fin = f.debut;
  end;;

let supprimer f = begin
  if f.vide then failwith "File vide.";
  f.debut <- successeur (f.debut);
  f.vide <-  f.fin = f.debut;
  f.pleine <- false;
  end;;

(* Les files avec des listes, voir page X *)

type 'a liste = Nil | Cons of 'a cellule
and 'a cellule =
  {contenu: 'a; mutable suivant: 'a liste};;

type 'a file =
  {mutable debut: 'a cellule;
   mutable fin: 'a cellule };;

let vide () = 
  let b = {contenu = 0; suivant = Nil} in
  {debut = b; fin = b};;

let faireVide f =
  let b = {contenu = 0; suivant = Nil} in
  f.debut <- b; f.fin <- b;;

let estVide f = f.fin == f.debut;;

let valeur f =
  match f.debut.suivant with
    Nil -> failwith "Pile vide"
  | Cons cell -> cell.contenu;;

let ajouter x f =
  let b = {contenu = x; suivant = Nil} in
  f.fin.suivant <- Cons b;
  f.fin <- b;;

let supprimer f =
  match f.debut.suivant with
    Nil -> ()
  | Cons cell -> f.debut <- cell;;

(* Déclarations et opérations sur les piles,
 voir page X *)

exception ExceptionPile of string;;

let maxP = 100;;

type 'a pile =
  {mutable hauteur: int;
   mutable contenu: 'a vect};;

let vide () = 
  {hauteur = 0; contenu = make_vect maxP 0};;

let faireVide p = p.hauteur <- 0;;

let estVide p = p.hauteur = 0;;

let estPleine p = p.hauteur = maxP;;

let ajouter x p =
  if estPleine p then
    raise (ExceptionPile "pleine");
  p.contenu.(p.hauteur) <- x;
  p.hauteur <- p.hauteur + 1;;

let pvaleur p =
  if estVide p then
    raise (ExceptionPile "vide");
  p.contenu.(p.hauteur - 1);;

let psupprimer p =
  if estVide p then
    raise (ExceptionPile "vide");
  p.hauteur <- p.hauteur - 1;;

(* Opérations sur les piles, version plus traditionelle *)

type 'a pile == 'a list ref;;

let vide () = ref [];;

let faireVide (p) = p := [];;

let estVide p = (!p = []);;

let ajouter x p = p := x :: !p;;

let valeur p = match !p with
    [] -> failwith "Pile Vide."
  | x :: p' -> x;;

let supprimer p =  p := match !p with
    [] -> failwith "Pile Vide."
  | x :: p' -> p';;

(* Evaluation des expressions préfixées,
   voir page X *)
type expression == element vect
and element =
    Symbole of char
  | Nombre of int;;

let calculer a x y =
  match a with
    `+` -> x + y
  | `*` -> x * y
  | _ -> failwith "unknown operator";;

let rec inserer x p =
  match x with
    Symbole c -> ajouter x p
  | Nombre n ->
     if pvide p then ajouter x p else
     match valeur p with
       Symbole c as y -> ajouter x p
     | Nombre m ->
        supprimer p;
        match valeur p with
          Symbole c ->
          supprimer p;
          let res = Nombre (calculer c n m) in
          inserer res p
        | _ -> failwith "pile mal construite";;

let evaluer u =
  let p =
    {hauteur = 0;
     contenu = make_vect 100 (Nombre 0)} in
  for i = 0 to vect_length u - 1 do
    inserer u.(i) p
  done;
  match valeur p with
    Symbole c -> failwith "pile mal construite"
  | Nombre n -> n;;

let pile_of_string s =
  let u = make_vect (string_length s) (Symbole ` `) in
  let l = ref 0 in
  for i = 0 to string_length s - 1 do
    let element =
      match s.[i] with
        `0` .. `9` as c ->
         let n =
          int_of_char c - int_of_char `0` in
         begin match u.(!l) with
           Symbole c -> Nombre n
         | Nombre m ->
            decr l; Nombre (10 * m + n)
         end
      | c -> Symbole c in
    incr l;
    u.(!l) <- element
  done;
  sub_vect u 0 !l;;

evaluer
 (pile_of_string
   "(* (+ 10 (* 2 3)) (+ (* 10 10) (* 9 9)))");;
- : int = 1996

(* Tail et cons, voir page X *)
let tail a = 
  match a with
    Nil -> failwith "tail"
  | Cons cell -> cell.contenu;;

let cons x l =
  Cons {contenu = x; suivant = l};;

(* Append et nconc, voir page X *)
let rec append a b =
  match a with
    Nil -> b
  | Cons cell ->
     cons (cell.contenu)
          (append cell.suivant b);;

let nconc ap b =
  match !ap with
    Nil -> ap := b
  | _ ->
     let c = ref !ap in
     while
      match !c with
        Cons {suivant = (Cons cell as l); _} ->
          c := l; true
      | _ -> false
     do () done;
     match  !c with
        Cons cell -> cell.suivant <- b
      | _ -> ();;

(* Version plus conforme au style Caml:
 avec une fonction récursive locale,
 on fait l'opération physique sur la liste *)
let rec nconc a b =
  let rec nconc1 c =
   match c with
     Nil -> b
   | Cons ({suivant = Nil; _} as cell) ->
       cell.suivant <- b; a
   | Cons {suivant = l; _} -> nconc1 l in
 nconc_aux a;;

(* Nreverse et reverse,
 voir page X *)
let nreverse ap =
 let a = ref !ap in
 let b = ref Nil in
 let c = ref Nil in
 while
   match !a with
   | Nil -> false
   | Cons ({suivant = s; _} as cell) ->
      c := s;
      cell.suivant <- !b;
      b := !a;
      a := !c;
      true
 do () done;
 ap := !b;;

(* Version plus conforme à Caml:
 on renverse la liste en place
 et l'on rend la nouvelle tête de liste *)
let nreverse l =
 let rec nreverse1 a b =
  match a with
  | Nil -> b
  | Cons ({suivant = s; _} as cell) ->
     cell.suivant <- b;
     nreverse1 s a in
  nreverse_aux l Nil;;

let rec reverse a =
   match a with
   | Nil -> a
   | Cons cell ->
      append (reverse cell.suivant)
             (cons (cell.contenu) Nil);;

(* Insert, voir page X *)
let insert v l =
  match l with
    Nil -> failwith "insert"
  | Cons c ->
     let rec insert_aux a =
      match a with
      | Nil -> failwith "insert"
      | Cons cell ->
         if v > cell.contenu && cell != c
         then insert_aux cell.suivant
         else cell.suivant <-
                cons v cell.suivant in
     insert_aux c.suivant;
     c.contenu <- l.contenu + 1;;