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

Listes et Piles I

  1. Dans cet exercice, on cherche à créer des méthodes utiles dans la suite pour manipuler des listes. Il consiste à compléter le fichier tp04_ex1tmplt.java. (Pour télécharger le fichier, cliquer ici.) On utilise la classe Liste définie en cours. 
      class Liste {
  int contenu;
  Liste suivant;
  public Liste(int val,Liste li) {
    contenu=val;
    suivant=li;
  }
}
    Cette classe permet de construire une liste dont la première valeur et le reste de la liste sont donnés.
    1. Définir la méthode 
        static void afficheListe(Liste li)
      qui affiche une liste.
    2. Définir la méthode 
        static Liste stringTabVersListe(String[] str)
      qui convertie un tableau de chaînes du type 
        tab[0]="23"
tab[1]="8"
tab[2]="43"
      en une liste li telle que 
        li.contenu=23
li.suivant.contenu=8
li.suivant.suivant.contenu=43
li.suivant.suivant.suivant=null
    3. Définir la méthode 
        static int longueur(Liste li)
      qui retourne le nombre déléments d'une liste. (Faire une méthode itérative ou récursive.)
    Tester les méthodes.
    [corrigé]

  2. Avec les méthodes et classes de l'exercice 1, définir une méthode itérative 
      static Liste renverse(Liste li)
    qui renverse l'ordre des éléments d'une liste en créant une nouvelle liste.

    Plus difficile: proposer une méthode récursive renverseEnPlace qui effectue un renversement "en place", c'est-à-dire sans créer de nouvelle liste ni modifier un champs contenu d'une cellule d'une liste. Cet algorithme est particulièrement utile lorsque le champs contenu contient un objet plus volumineux d'un simple nombre entier.
    [corrigé]

  3. Dans cet exercice, on manipule des listes triées, c'est-à-dire telle que x.contenu<x.suivant.contenu pour tout élément x de la liste. Avec les méthodes et classes de l'exercice 1, 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.
    [corrigé]

  4. On cherche à effectuer des opérations sur des ensembles de nombres entiers avec les méthodes et classes de l'exercice 1. Pour cela, un ensemble est représenté par une liste ordonnée (voir l'exercice 3). 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 listes sans 0 obtenues par découpage de la liste a.
    [corrigé]