INF220 - TP Séance 3

Durée : 2h00




Objectifs




Au menu

  1. Consignes
  2. Création des 4 fonctions de base de la liste
  3. 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.

Créez un fichier INF220TP3.java prêt à compiler.

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 : Pour comprendre ce codage, voici un exemple de tableau memoire : [5,4,-1,9,1]. 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. 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.

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, 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. Que renvoie la fonction creeListe dans les exemples précédents des listes L1 et L2 ?.
Écrivez le code de la fonction creeListe.

Écrivez le code de la fonction tete.

É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).

Écrivez le code d'une fonction estVide qui renvoie true si l'entier fourni en entrée correspond à la liste vide, et false sinon. Écrivez une fonction afficheListe permettant d'afficher le contenu de chacune des cases d'une liste.

Écrivez les fonctions remplaceTete et valeur vues en cours.

É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.