Contraintes

Nous allons définr une classe (récursive) Liste de la façon suivante:

class Liste {
    public int tete;
    public Liste queue;

    static final Liste VIDE = null;

    public Liste(int tete, Liste queue) {
        this.tete = tete;
        this.queue = queue;
    }

    public Liste cons(int tete, Liste queue) {
        return new Liste(tete, queue);
    }

    public String toString() {// suppose la liste non vide !
        if (queue == null) {
            return tete + "::[]";
        } else {
            return tete + "::" + queue.toString();
        }
    }
}

Les seules choses que nous aurons le droit de faire sont :

// Créer une liste vide
Liste l = Liste.VIDE;

// Construire une liste à partir
// d'une tête (un élément)
// et d'une queue (une liste)
int tete = 17;
Liste queue = Liste.VIDE;
Liste nouvelle = cons(tete, queue);
Liste l = cons(16, nouvelle);

// Accéder au premier élément (tête)
System.out.println(l.tete)

// Accéder à la queue de la liste (liste privée de son premier élément)
System.out.println(l.queue)

// Tester si la liste est vide
if (l == null) {
    System.out.println("Liste vide")
} else {
    System.out.println("Liste pas vide")
}

Exercices

Dans une autre classe (Main), écrire et tester les fonctions suivantes :

1. taille ou longueur d’une liste

   static int longueur(Liste l):
       if (l == null) {
           return 0;
       } else {
           return 1 + longueur(l.queue);
       }

2. estDans teste si un élément donné appartient à la liste.

3. concatene met deux listes bout à bout.

4. renverse renvoie la liste à l’envers.

5. Calculer la complexité des fonctions concatene et renverse.

6. maximum renvoie le plus grand élément d’une liste d’entiers.

7. minimum renvoie le plus grand élément d’une liste d’entiers.

8. repeat(n, m) renvoie la liste composée de n fois l’élément m.

   >>> repeat(5, "ah")
   ["ah", "ah", "ah", "ah", "ah"]

9. cycle(n, l) renvoie la liste composée de n fois la liste l.

   >>> cycle(4, ["a","b"])
   ["a", "b", "a", "b", "a", "b", "a", "b"]

10. pairs(n) renvoie la liste des n premiers nombres pairs.

    >>> lp = pairs(10)
    >>> lp
    [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

11. take(n, l) renvoie la liste des n premiers éléments de l.

    >>> take(4, lp)
    [2, 4, 6, 8]

12. drop(n, l) renvoie la liste des éléments de l privée des n premiers.

    >>> drop(5, lp)
    [12, 14, 16, 18, 20]

13. last renvoie le dernier élément d’une liste.

    >>> last(lp)
    20

14. init renvoie la liste privée de son dernier élément.

    >>> init(lp)
    [2, 4, 6, 8, 10, 12, 14, 16, 18]