Exercice n°1
- Créez la classe Cell.java conformément au code ci-dessous (= celle donnée en TD).
public class Cell {
public int value;
public Cell next;
public Cell(int value) {
this.value = value;
next = null;
}
}
- Complétez les méthodes de la classe ListSimple.java donnée ci-dessous, en prenant comme base les méthodes données en TD.
public class ListSimple {
public Cell head;
public int size;
public ListSimple() {
head = null;
size = 0;
}
public Cell find(int value) {
}
public Cell get(int index) {
}
public Cell append(int value) {
}
public Cell insert(int value, int index) {
}
public Cell replace(int value, int index) {
}
public Cell removeAt(int index) {
}
public Cell remove(int value) {
}
public void print() {
}
}- Un programme de test : si vous constatez que votre résultat est différent des commentaires, c'est que votre classe ListSimple est fausse.
class TestSimple {
public static void main(String[] args) {
ListSimple liste = new ListSimple();
liste.append(20); // liste vide -> insertion en tête
liste.insert(10,-5); // insertion en tête
liste.insert(30,7); // insertion en fin
liste.append(50); // ajout en fin
liste.insert(40,3); // insertion en 3
liste.print(); // affiche 10 20 30 40 50
liste.remove(12); // ne fait rien
liste.remove(10); // enlève la valeur 10 (la tête)
liste.removeAt(-2); // ne fait rien
liste.removeAt(22); // ne fait rien
liste.removeAt(2); // enleve la valeur en 2 (i.e. 40)
liste.print(); // affiche 20 30 50
Cell c = liste.get(-1); // accès en dehors -> renvoie null
if (c != null) {
System.out.println("pb with get()");
}
c = liste.get(99); // accès en dehors -> renvoie null
if (c != null) {
System.out.println("pb with get()");
}
c = liste.find(99); // value inexsitante -> renvoie null
if (c != null) {
System.out.println("pb with find()");
}
c = liste.find(20);
if (c.value != 20) {
System.out.println("pb with find()");
}
c = liste.find(50);
if (c.value != 50) {
System.out.println("pb with find()");
}
}
}
- Utiliser le canevas de code C à disposition sur cours-info pour faire la même chose que l'exercice 1, mais en C.
Exercice n°3
- On définit maintenant la classe CellDouble.java pour permettre de créer une liste doublement chaînée. Pour cela, on doit ajouter un attribut de type Cell appelé prev, qui référence la cellule précédente
public class CellDouble {
public int value;
public CellDouble prev;
public CellDouble next;
public CellDouble(int value) {
this.value = value;
prev = null;
next = null;
}
}- On définit maintenant une classe ListDoubleCir.java qui permet de gérer une liste doublement chaînée ET circulaire.
- Cela implique qu'une cellule référence celle qui la précède et celle qui la suite mais aussi que la cellule de tête référence la dernière et inversement.
- En terme d'implémentation, cela veut dire que les attribut prev et next de toutes les cellules ne sont JAMAIS égaux à null. Par exemple, lors de l'insertion de la première cellule, ses attributs prev et next doivent référencer la cellule elle-même (donc this).
- Pour vous aider dans l'implémentation quelques remarques sont données en commentaires.
public class ListDoubleCirc {
public CellDouble head;
public int size;
public ListDoubleCirc() {
head = null;
size = 0;
}
public CellDouble find(int value) {
// quasi identique à l'exo 1, excepté le test d'arrêt
}
public CellDouble get(int index) {
// pour éviter de tout parcourir, on peut tester si l'indice
// est avant ou après la moitié de la liste. S'il est avant,
// on explore la liste grâce à next, et sinon grâce à prev
}
public CellDouble append(int value) {
// pas besoin de trouver la dernière cellule : on y a accès
// grâce à prev de la tête. Seul cas particulier, la liste est vide
}
public CellDouble prepend(int value) {
// pas compliqué : insertion en tête = insertion en fin
// puis déplacement de la tête
}
public CellDouble insert(int value, int index) {
// on a get() pour trouver la cellule du point d'insertion
// Seul cas particulier, la liste est vide
}
public CellDouble replace(int value, int index) {
// utiliser get()
}
public CellDouble removeAt(int index) {
// utiliser get()
}
public CellDouble remove(int value) {
// utiliser find
}
}- Le programme de test :
class TestDouble {
public static void main(String[] args) {
ListDoubleCirc liste = new ListDoubleCirc();
liste.append(20); // liste vide -> insertion en tête
liste.insert(10,-5); // insertion en tête
liste.insert(30,7); // insertion en fin
liste.append(50); // ajout en fin
liste.insert(40,3); // insertion en 3
liste.print(); // affiche 10 20 30 40 50
liste.remove(12); // ne fait rien
liste.remove(10); // enlève la valeur 10 (la tête)
liste.removeAt(-2); // ne fait rien
liste.removeAt(22); // ne fait rien
liste.removeAt(2); // enleve la valeur en 2 (i.e. 40)
liste.print(); // affiche 20 30 50
CellDouble c = liste.get(-1); // accès en dehors -> renvoie null
if (c != null) {
System.out.println("pb with get()");
}
c = liste.get(99); // accès en dehors -> renvoie null
if (c != null) {
System.out.println("pb with get()");
}
c = liste.get(1); // accès indice 1 (i.e 30)
if (c.value != 30) {
System.out.println("pb with get()");
}
c = liste.find(99); // value inexsitante -> renvoie null
if (c != null) {
System.out.println("pb with find()");
}
c = liste.find(20);
if (c.value != 20) {
System.out.println("pb with find()");
}
c = liste.find(50);
if (c.value != 50) {
System.out.println("pb with find()");
}
}
}
- La séparation stricte des deux types de liste ne respecte pas les concepts de programmation objet.
- Normalement, il faudrait faire une super-classe (ou une classe interface) ListChained permettant de déclarer/définir les opérations basiques et des sous-classe implémentant ces opérations en fonction du type de liste.
- Bien entendu, cela suppose également que les classe de cellule soient également remaniée. On pourrait par exemple créer une classe générique de cellule qui ne contienne qu'une attribut valeur, puis faire des sous-classes représentant les cellules utilisées dans les différents types de liste.
Exercice n°4
- L'objectif est d'écrire les même fonctionnalités que l'exercice n°3 mais en C.
- Pour cela vous pouvez utiliser le fichier entête suivant : listdouble.h
typedef struct cell {
int value;
struct cell* next;
struct cell* prev;
} Cell;
typedef struct list {
Cell* head;
int size;
} List;
List* listCreate();
Cell* listFind(List* l, int value);
Cell* listGet(List* l, int index);
Cell* listPrepend(List* l, int value);
Cell* listAppend(List* l, int value);
Cell* listInsert(List* l, int value, int index);
Cell* listReplace(List* l, int value, int index);
Cell* listRemoveAt(List* l, int index);
Cell* listRemove(List* l, int value);
void listPrint(List* l);
- Et du canevas de code suivant pour l'implémentation des fonction : listdouble.c
#include <stdio.h>
#include <stdlib.h>
#include "listdouble.h"
List* listCreate() {
}
Cell* listFind(List* l, int value) {
}
Cell* listGet(List* l, int index) {
}
Cell* listPrepend(List* l, int value) {
}
Cell* listAppend(List* l, int value) {
}
Cell* listInsert(List* l, int value, int index) {
}
Cell* listReplace(List* l, int value, int index) {
}
Cell* listRemoveAt(List* l, int index) {
}
Cell* listRemove(List* l, int value) {
}
void listPrint(List* l) {
}
- Pour le programme de test, il suffit de prendre le même que testsimple.c fourni en TD, mais de remplacer #include "listsimple.h" par #include "listdouble.h"
- Création exécutable (compilation + édition de liens) : gcc listdouble.c testdouble.c -o testdouble