INF220 - TP Séance 3
Durée : 2h00
Objectifs
- Comprendre le concept de la liste simplement chaînée d'entiers.
- Implémenter une liste d'entiers à partir d'un tableau d'entiers.
Au menu
- Consignes
- Création des 4 fonctions de base de la liste
- Programmation de fonctions sur les listes
L'objectif de ce TP est de concevoir une structure de liste d'entiers à partir d'un tableau d'entiers.
Lisez attentivement cet énoncé de TP
en suivant les instructions.
En cas d'interrogation,
faites appel à moi,
que ce soit pour en savoir plus sur un des points abordés pendant le TP, ou
pour savoir comment effectuer une des tâches demandées (numérotées pour pouvoir
y faire référence simplement).
Surtout
ne restez pas bloqué(e) sur une des questions.
Entre parenthèses, à côté des titres de sous-sections, est indiqué
le temps que vous avez dû passer à effectuer les étapes précédentes.
question(); ?>Créez un fichier INF220TP3.java
prêt à compiler.
question(); ?>Créez une fonction main, à l'intérieur
de laquelle vous allez créer un tableau d'entiers memoire de 1000 cases.
Nous allons utiliser ce tableau
memoire
comme une mémoire globale, afin de stocker des listes simplement chaînées :
- principe 1 : dans sa première case, le numéro Java de la première case "vide" de ce tableau memoire
- principe 2 : chaque case de memoire dont le numéro Java est impair correspond à la tête d'une liste (c'est-à-dire au contenu d'une case d'une liste)
- principe 3 : chaque case de memoire dont le numéro Java est pair correspond au numéro Java dans le tableau memoire de la case suivante de la liste
- principe 4 : chaque case de memoire dont le numéro Java est pair et qui contient -1 signifie que la case suivante de la liste est la liste vide NULL
- principe 5 : ainsi, pour stocker une liste, il suffira de remplir correctement le tableau memoire
et de stocker simplement un entier : cet entier correspond au numéro Java de la case
(dans le tableau memoire) qui contient
la tête de la liste.
Pour comprendre ce codage, voici un exemple de tableau
memoire :
[5,4,-1,9,1].
question(); ?>Quelle est la liste d'entiers L1
codée par l'entier 3 à l'aide de ce tableau memoire ?.
Dessinez le tableau et la liste et appliquez chacun des 5 principes précédents
sur cet exemple.
A l'inverse, nous allons essayer de partir d'une liste et de voir
comment la coder par un entier, en remplissant correctement le tableau
memoire.
question(); ?>Quel est le contenu
du tableau memoire, et quel est l'entier à stocker,
pour créer une liste L2 qui serait constituée simplement d'une case
contenant la valeur 4 ?
Indication : si vous bloquez bien que vous avez essayé de faire des
petits dessins de liste et de tableau, utilisez la première page
(voire la deuxième page) de
ce document pour comprendre à partir d'un exemple.
question(); ?>Même question avec une liste L3
qui serait constituée simplement d'une première case contenant un 3
pointant vers une deuxième case contenant un 2, pointant vers
une troisième case contenant un 4.
On va généraliser l'exemple précédent pour créer une fonction
creeListe qui va créer une nouvelle liste à partir
d'un tableau.
En utilisant le cours sur
les listes simplement chaînées, et le fait qu'on doit stocker toutes
les informations sur les listes dans le tableau
memoire,
question(); ?>quelles sont les entrées
de la fonction creeListe ?.
La sortie sera le numéro de la case du tableau
memoire
correspondant à la tête de la liste créée.
question(); ?>Que renvoie la fonction
creeListe dans les exemples précédents des listes L1 et L2 ?.
question(); ?>Écrivez le code de la fonction
creeListe.
question(); ?>Écrivez le code de la fonction
tete.
question(); ?>Écrivez le code de la fonction
suivant, qui renvoie naturellement l'entier correspondant
au numéro, dans le tableau
memoire, du contenu de la
deuxième case de la liste donnée en entrée (sous forme du numéro indiquant
la position dans
memoire de la tête de la liste).
question(); ?>Écrivez le code d'une fonction
estVide qui renvoie true si l'entier fourni en entrée
correspond à la liste vide, et false sinon.
question(); ?>Écrivez
une fonction afficheListe permettant d'afficher le contenu de chacune
des cases d'une liste.
question(); ?>Écrivez
les fonctions remplaceTete et valeur vues
en cours.
question(); ?>Écrivez
les fonctions d'insertion d'un élément en tête de liste
et de suppression de l'élément en tête de liste.