Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/07242.jsonl.gz/326

tp04_ex1tmplt.java. (Pour télécharger le fichier, cliquer ici.) On utilise la classe
Listedé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.
static void afficheListe(Liste li)qui affiche une liste.
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
litelle que
li.contenu=23 li.suivant.contenu=8 li.suivant.suivant.contenu=43 li.suivant.suivant.suivant=null
static int longueur(Liste li)qui retourne le nombre déléments d'une liste. (Faire une méthode itérative ou récursive.)
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é]
x.contenu<x.suivant.contenupour tout élément
xde la liste. Avec les méthodes et classes de l'exercice 1, définir des méthodes
static Liste insere(int a,Liste li)
static Liste trieListe(Liste li)
insere(a,li)retourne une liste triée obtenue à partir d'une liste triée
lipar insersion d'un nouvel élément de contenu
a. La méthode
trieListe(li)utilise
inserepour 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.
static Liste intersection(Liste a,Liste b)
static Liste reunion(Liste a,Liste b)
static Liste complementaire(Liste a,Liste e)
static boolean estEgal(Liste a,Liste b)
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
0obtenues par découpage de la liste a.