ENPC - Objets et Patterns - Corrigés des exercices de la séance 8

Exercice 1: longeur d'une liste vide

Ce qui nous empêche d'appliquer la méthode length() à une liste vide, c'est que cette dernière est représentée par la référence null, qui ne représente pas un objet et sur laquelle on ne peut appeler aucune méthode ni aucun champ sous peine de lever une exception de la classe NullPointerException. Aussi, il nous faut représenter la liste vide par un véritable objet. Pour cela, nous pouvons définir un constructeur sans argument qui initialise les champs head et tail à null. En revanche, pour éviter que chaque liste vide soit un nouvel objet de ce genre, on peut interdire à l'utilisateur d'appeler ce constructeur en le qualifiant de privé. Pour disposer de la liste vide, l'utilisateur aura accès à un champ constant (final static), déclaré dans la classe, qui lui sera initialisé par un appel au constructeur privé; ce dernier sera donc appelé une seule fois en tout et pour tout.

/**
 * Une classe implantant le type récursif des listes.
 */
public class Liste {
  public final static Liste VIDE = new Liste();
  Object head;
  Liste tail;
  /**
   * Constructeur (seule façon de créer une liste non vide).
   */ 
  public Liste(Object head, Liste tail) {
    this.head = head;
    this.tail = tail;
  }
  /**
   * Constructeur privé de la liste vide.
   */
  private Liste() {
    this.head = null;
    this.tail = null;
  }
  /**
   * Longueur de la liste.
   */ 
  public int length() {
    if (this == VIDE)
      return 0;
    return 1 + tail.length();
  }
  /**
   * Représentation d'une liste.
   */  
  public String toString() {
    if (this == VIDE)
      return "[]";
    return "[" + head + ":" + tail.toString() + "]"; 
  }
  /**
   * Teste si la liste contient un élément donné.
   */
  public boolean contains(Object o) {
    if (this == VIDE)
      return false;
    if (head.equals(o))
      return true;
    return tail.contains(o);
  }
  
  public static void main(String[] args) {
    Liste l = new Liste("a",
                        new Liste("b",
                                  new Liste("c",
                                            new Liste("d",VIDE))));
    System.out.println(l);
    System.out.println("longueur: " + l.length());
    System.out.println("Contient c? " + l.contains("c"));
    Liste listeVide = VIDE;
    System.out.println(listeVide);
    System.out.println("longueur: " + listeVide.length());
  }
}

DU coup, on peut remarquer que le test permettant de savoir si une liste est vide peut se résumer à tester l'égalité de référence avec VIDE puisqu'aucune autre instance de liste vide ne peut être créé.

Exercice 2: interface IList et classes Cons et Nil

public interface IList {
  /**
   * Retourne la longueur de la liste.
   */ 
  int length();
  /**
   * Teste si la liste contient l'objet o parmi ses éléments.
   */
  boolean contains(Object o);
}

La première classe que nous définissons ici est la classe Nil, qui ne stocke rien (elle n'a pas de champ). La définition des méthodes est ultra simple puisqu'on sait que lorsque ces méthodes sont appellées, on est nécessairement sur une liste vide.

public class Nil implements IList {
    public int length() {
	return 0;
    }
    public boolean contains(Object o) {
	return false;
    }
    public String toString() {
	return "[]";
    }
}

Le code de la classe Cons est un peu plus riche, mais le fait de savoir qu'on est sûr de ne pas être dans le cas d'une liste vide simplifie les précautions et les tests.

public class Cons implements IList {
    Object head;
    IList tail;
    public Cons(Object head, IList tail) {
	this.head = head;
	this.tail = tail;
    }
    public int length() {
	return 1 + tail.length();
    }
    public boolean contains(Object o) {
	if (head.equals(o)) 
	    return true;
	return tail.contains(o);
    }
    public String toString() {
	return "[" + head + "," + tail + "]";
    }
}

Exercice 3: méthode append

Dans l'interface IList, il suffit pour la méthode de concaténation de définir la méthode suivante:

  // Dans l'interface IList
  /**
   * Concatène de manière applicative (sans effets de bords)
   * la liste courante avec l2 et retourne le résultat.
   */
  IList append(IList l);

L'implémentation de cette méthode dans la classe Nil est très simple: que faire lorsqu'on veut concaténer une liste l à une liste vide? Il suffit de retourner la liste l:

  // Dans la classe Nil
  public IList append(IList l) {
    return l;
  }

Dans la classe Cons, il est important de rappeler que nous voulions une méthode "applicative", c'est à dire sans effet de bord. Autrement dit, on souhaite que les deux listes utilisées pour faire la concaténation reste inchangées à l'issue de l'opération. Pour ce faire, une technique courrament employée dans ce genre de situation est le partage de structure. Plutôt que de modifier la structure d'une liste ou de l'autre, on reconstruit la "charpente" de la première liste, en partageant ses éléments, et on partage, en guise de fin de liste, la liste complète avec laquelle on devait être concaténé. Le fait que notre algorithme est récursif et qu'il s'applique sur une structure récursive rend le code particulièrement élégant.

  // Dans la classe Cons
  public IList append(IList l) {
    return new Cons(head, tail.append(l));
  }

Exercice 4: interface Tree

public interface Tree {
    /**
     * Retourne le nombre de valeurs stockées dans l'arbre.
     */ 
    int size();
    /**
     * Retourne la profondeur de l'arbre. 
     * L'arbre vide est de profondeur -1. 
     * L'arbre à un élément est de profondeur 0. 
     */
    int depth();
    /**
     * Teste si l'arbre contient l'objet o parmi ses éléments.
     */
    boolean contains(Object o);
}

Exercice 5: classe Node et Empty

public class Empty implements Tree {
    public final static Tree E = new Empty();
    private Empty(){}
    public int size() {
	return 0;
    }
    public int depth() {
	return 0;
    }
    public boolean contains(Object o) {
	return false;
    }
}
public class Node implements Tree {
    Object value;
    Tree left;
    Tree right;
    public Node(Object value, Tree left, Tree right) {
	this.value = value;
	this.left = left;
	this.right = right;
    }
    public int size() {
	return 1 + left.size() + right.size();
    }
    private int max(int a, int b) {
	return (a>b)?a:b;
    }
    public int depth() {
	int countLeft = left.depth();
	int countRight = right.depth();
	return 1 + max(countLeft,countRight);
    }
    public boolean contains(Object o) {
	if (value.equals(o))
	    return true;
	return left.contains(o) || right.contains(o);
    }
    public static void main(String[] args) {
	Tree t = new Node("a",
			  new Node("b",
				   new Node("c",Empty.E,Empty.E),
				   new Node("d",Empty.E,Empty.E)),
			  new Node("e",
				   Empty.E,
				   new Node("f",
					    new Node("g",Empty.E,Empty.E),
					    Empty.E)));
	System.out.println("Nombre de feuilles: " + t.size());
	System.out.println("Profondeur: " + t.depth());
	System.out.println("Contient g: " + t.contains("g"));
	System.out.println("Contient d: " + t.contains("d"));
	System.out.println("Contient h: " + t.contains("h"));
    }
}

Exercice 6: affichage d'arbre

    // Dans la classe Empty
    public String toString() {
	return toString(0);
    }
    public String toString(int decal) {
	return "\n";
    }
    // Dans la classe Node
    public String toString() {
	return toString(0);
    }
    public String toString(int decal) {
	StringBuffer sb = new StringBuffer();
	sb.append(right.toString(decal+3));
	for(int i=0; i<decal; i++)
	    sb.append("-");
	sb.append(value);
	sb.append(left.toString(decal+3));
	return sb.toString();
    }


Etienne.Duris[at]univ-mlv.fr - © École Nationale des Ponts et Chaussées - Décembre 2000 - http://www-igm.univ-mlv.fr/~duris/ENPC/index2000.html