TD numéro 5 du tronc commun en informatique 1998-99 dirigé par Serge Vaudenay et David Pointcheval.

Listes et Piles II

  1. * Dans cet exercice, on manipule des listes ordonnées, c'est-à-dire telles que x.contenu<x.suivant.contenu pour tout élément x de la liste. Définir des méthodes
    1. static Liste insere(int a,Liste li)
    2. static Liste trieListe(Liste li)
    La méthode récursive insere(a,li) retourne une liste triée obtenue à partir d'une liste triée li par insersion d'un nouvel élément de contenu a. La méthode trieListe(li) utilise insere pour fabriquer une liste triée qui contient les mêmes valeurs que la liste non triée li. (On ne fait par de tri "en place" ici.) Le tri s'effectue par insersion avec pour complexité O(n2) où n est la longueur de la liste.
    On pourra utiliser les méthodes et classes de     l'exercice 1 du TP4 (voir son corrigé) pour saisir et visualiser des listes.
    [Même exercice que l'exercice 3 du TP4, voir son corrigé]

  2. *** L'objectif de cet exercice est d'implémenter l'algorithme de tri par fusion "en place" d'une liste doublement chaînée gardée. On utilise pour cela la structure de données définie par la classe DBListe suivante. 
      class DBListe {
  int contenu;
  DBListe suivant,precedent;
  boolean garde;
  public DBListe() {
    garde=true;
    suivant=this;
    precedent=this;
  }
  public DBListe(int val,DBListe li1,DBListe li2) {
    garde=false;
    contenu=val;
    suivant=li1;
    precedent=li2;
    li1.precedent=this;
    li2.suivant=this;
  }
}
    Avec une telle structure, jamais la valeur null ne doit être rencontrée. Une liste gardée est composée d'une garde et de cellules. Les gardes et les cellules sont des objets qui implémentent la classe DBListe. On les distingue par la valeur booléenne li.garde (si li est le pointeur vers l'objet correspondant). On dit qu'une structure est consistente si pour toute cellule, ainsi que pour la garde, on a la propriété
      ( li.precedent.suivant==li ) && ( li.suivant.precedent==li ).
    On utilise le constructeur new DBListe() pour créer une nouvelle liste gardée (vide), et new DBListe(val,prec,suiv) pour créer une nouvelle cellule en indiquant la précédente et la suivante. (Ce constructeur met à jour les pointeurs des cellules voisines pour maintenir consistente la structure.) On utilise les méthodes suivantes
    1. static boolean estVide(DBListe li)
      qui indique si une liste gardée est vide,
    2. static boolean estConsistente(DBListe li)
      qui vérifie la consistence d'une structure,
    3. static void afficheDBListe(DBListe li)
      qui visualise une liste gardée et prévient si la structure de donnée n'est pas consistente (utile pour détecter les erreurs de programmation!),
    4. static DBListe stringTabVersDBListe(String[] str)
      qui transforme un tableau de String en une liste.
    Ces méthodes sont définies dans le fichier tp05_ex2tmplt.java. (Pour télécharger le fichier,     cliquer ici.)

    On cherche à ordonner une liste d'entiers "en place", c'est-à-dire sans modifier une quelconque valeur li.contenu. Définir des méthodes suivantes.

    1. static void supprimeInsereIci(DBListe x,DBListe li)
      Lorsque x et li sont des cellules de deux listes différentes, cette méthode supprime x de sa propre liste et l'insère dans l'autre juste avant l'emplacement de li.
    2. static DBListe milieu(DBListe li)
      Cette méthode retourne un pointeur vers une cellule du milieu de la liste dont la garde est li.
    3. static DBListe coupeIci(DBListe ici,DBListe li)
      Si ici est une cellule de la liste li, cette méthode supprime tout ce qui se trouve à partir de cette cellule et en fait une nouvelle liste gardée séparée.
    4. static void colle(DBListe li1,DBListe li2)
      Cette méthode colle le contenu de la liste li2 à la fin de la liste li1.
    5. static void fusionne(DBListe li1,DBListe li2)
      Si li1 et li2 sont deux listes ordonnées, cette méthode les fusionne (dans li1) en respectant l'ordre.
    6. static void triFusion(DBListe li)
      Cette méthode effectue un tri en place d'une liste li par l'algorithme de tri par fusion en O(n.log n).

    [corrigé]

  3. ** On cherche à effectuer des opérations sur des ensembles de nombres entiers avec la classe Liste de l'exercice 1 du TP4 (voir son corrigé). Pour cela, un ensemble est représenté par une liste ordonnée (voir l'exercice 1). Définir les méthodes suivantes.
    1. static Liste intersection(Liste a,Liste b)
    2. static Liste reunion(Liste a,Liste b)
    3. static Liste complementaire(Liste a,Liste e)
    4. static boolean estEgal(Liste a,Liste b)
    qui effectuent respectivement l'intersection de deux ensembles, la réunion de deux ensembles, le complémentaire d'un ensemble a dan sun ensemble e, et qui teste l'égalité du contenu de deux ensembles.

    Afin de saisir les données pour tester le programme, on pourra décider que l'entier 0 sert de délimiteur entre deux listes saisies et définir une méthode 

      static Liste[] separe(Liste a)
    qui retourne un tableau de deux listes obtenues par découpage de la liste a.
    [Même exercice que l'exercice 4 du TP4, voir son corrigé]

  4. * On utilise pour cela la structure de données définie par la classe Pile suivante. 
      class Pile {
  int contenu;
  Pile suivant;
  public Pile(int val,Pile st) {
    contenu=val;
    suivant=st;
  }
}
    Dans cet exercice, on cherche à simuler l'emploi d'une calculatrice à notation polonaise inversée. Pour cela, on commence à empiler les arguments numériques, et l'on invoque les opérations ensuite. On cherche donc à définir une application qui traite une série d'arguments itérativement. La commande
      java tp05_ex4 arg1 arg2 ... argn
    traite successivement les arguments arg1, arg2, ... Si l'argument argi est numérique, on empile le nombre argi dans un objet de type Pile. Dans le cas contraire, l'argument doit être l'une des chaîne suivante.
    1. "ADD" Dans ce cas, on dépile deux nombres et l'on empile leur somme.
    2. "SUB" Idem en faisant la soustraction.
    3. "MUL" Idem en faisant la multiplication.
    4. "DIV" Idem en faisant la division.
    5. "DSP" Dans ce cas, on affiche le contenu de la pile.

    On pourra compléter le fichier tp05_ex4tmplt.java. (Pour télécharger le fichier,     cliquer ici.)
    [corrigé]

  5. *** On utilise une structure de pile dans laquelle on peut empiler des entiers ou des identificateurs de fonction définie par la classe Pile. Cette classe admet trois variables d'instance:
    1. type qui indique si l'on a un entier ou un identificateur de fonction dans cette cellule de la pile.
    2. contenu qui est, soit l'entier, soit l'identificateur de fonction.
    3. suivant qui indique la cellule suivante.
    Comme dans l'    exercice 4, les fonctions sont ADD, SUB, MUL et DIV.

    Définir une application qui empile une série d'arguments (des entiers ou des fonctions) qui représentent une expression en notation préfixe, et qui affiche l'expression algébrique correspondante, puis l'évalue. Par exemple

      java tp05_ex5 ADD 5 MUL SUB 4 1 3
    devra afficher
      (5 + ((4 - 1) * 3)) = 14.
    Indication: on pourra utiliser une pile gardée.
    [corrigé]