[++C] TD : Liste chaînée

Le menu est disponible grâce au bouton droit

Date de première publication : 2012/11/07

On veut vous faire coder une classe représentant une liste chaînée simple, tout d'abord sur un type de données particulier : un entier puis en faire une version générique (template)

Mise en place des classes List et Cell

Nous avons besoin d'une classe List qui nous permettra de faire toutes les opérations que l'on veut faire. Une liste chaînée étant constituée de cellules, nous avons également besoin d'une classe Cell.

Pour ce TP, nous avons besoin d'au moins 4 fichiers :

• List.hpp : contient les déclarations des classes List, Cell (et plus tard ItList). Les classes ne sont pas imbriquées.
• List.cpp : contient la définition des classes
• main.cpp, le programme principal qui va nous permettre de tester note développement
• makefile

1. Déclarer la classe Cell avec un champ de donnée et un champ sur la cellule suivante. Si vous voulez coder une liste que l'on peut parcourir dans les deux sens, je vous laisse ajouter un champ sur la cellule précédente.
2. Déclarer la classe List et écrire le constructeur par défaut qui crée une liste vide.
3. Ajouter un méthode empty() qui revoie vrai si la liste est vide
4. Écrire le destructeur de la liste (libérer toutes les cellules)
5. Écrire une méthode push_back() qui permet d'ajouter un élément en fin de liste.
6. Écrire une méthode display() qui affiche sur la liste sur le flux passé en paramètre. Surcharger l'opérateur operator<<().
7. Écrire une méthode push_front() qui permet d'insérer un élément en tête de liste.
8. Écrire les méthodes front() et back() qui renvoient respectivement le premier et le dernier élément de la liste.

9. Écrire les méthodes pop_front() et pop_back() qui enlèvent respectivement l'élément en tête et en fin de liste
10. Écrire la méthode size() qui permet de connaître le nombre d'éléments de la liste
11. Si vous pensez que vous avez fini, vous pouvez passze à la section suivante, sinon vous prendrez un peu de temps pour compléter l'interface de la liste et lui offrir une vraie forme normale de Coplien avec un constructeur de copie et un opérateur d'affectation.

Si vous voulez qu'un objet de classe A (respectivement fonction f) puisse accéder aux attributs privés d'une classe B, il est nécessaire que la classe A (respectivement f) soit déclarée amie de la classe B dans la classe B. Si l'amitié peut être fort pratique, usez-en avec Parcy et Monie car cela brise l'encapsulation de la classe B. C'est pour cela que l'on a a créé une methode display() à utiliser dans l'opérateur operator<< ().

L'itérateur de liste

Un itérateur est un objet qui permet de parcourir un conteneur (ici la liste) et qui permet d'obtenir l'objet courant quand on le déréférence (à l'instar du pointeur sur un tableau).

Voici le code que l'on veut écrire pour manipuler un itérateur de liste :

ItList it = l1.begin();
while (it!=l1.end()) {
  std::cout << *it;
  ++it;
}

1. Doter la classe ItList d'un constructeur par défaut public qui initialise le champ cell au pointeur nul.
2. Doter la classe List d'une méthode begin(). Cette méthode crée un itérateur sur la première cellule de la liste
3. Doter la classe ItList d'un constructeur qui prend en paramètre un pointeur sur une cellule pour réaliser l'opération ci-dessus.

4. Doter la classe List d'une méthode end(). Je rappelle que cet itérateur ne désigne pas le dernier élément mais vraiment la fin de la liste (éventuellement, un élément fictif après le dernier élément). On peut donc se contenter dans le cas de la liste chaînée, d'un "pointeur nul". Cette méthode end() peut donc simplement renvoyer un itérateur créé par défaut (qui est "nul").
5. Doter la classe ItList d'un constructeur qui prend en paramètre un pointeur sur une cellule pour réaliser l'opération ci-dessus.

Qu'en est-il du constructeur de copie ? de l'opérateur d'affectation ? du destructeur ? Il n'y a pas d'attribut compliqué. Les versions binaires fournies par le compilateur sont suffisantes. Il manque cependant des éléments comme l'opérateur de comparaison operator!=(), l'opérateur de déréférencement operator*() et l'incrément d'itérateur.

6. Doter la classe ItList d'une méthode bool equals(const ItList&) qui renvoie vrai si les itérateurs pointent sur le même élément
7. Écrire l'operator!=().

8. Écrire l'operator*() qui renvoie l'élément pointé.

int&        operator*()       throw (NullIteratorException);
const int&  operator*() const throw (NullIteratorException);

9. Pourquoi ne pas ajouter une exception si l'utilisateur essaie de déréférencer un itérateur nul ?
10. Passons maintenant à l'incrément d'itérateur, c'est-à-dire passer à l'élément suivant de la collection. Il y a deux formes pour l'opérateur ++ : une forme pour la version préfixée et une autre pour la version postfixée. Pour les différentier, la version postfixée , la plus compliquée (on doit renvoyer une copie de l'itérateur), a un paramètre entier muet.

ItList& operator++();    // version préfixée
ItList operator++(int);  // version postfixée

Version template ...

Si vous avez réalisé tout ce que l'on vous a demandé, vous pouvez passer à la version paramétrée de la classe. Il s'agit simplement

1. Copier les fichiers fonctionnels précédents (au cas où) et mettre à jour les gardiens
2. Paramétrer les classes List, Cell et ItList par un type générique et remplacer tout (ou presque) ce qui était int par ce type
3. Prendre en compte qu'un fichier qui contient du code template ne se compile pas

template<typename T>
class List{
  Cell<T> * first;
  // ...
};
  
template<typename T>
void List<T>::insert(const ItList<T>& it, const T& elem) {

}

Le code non générique précédent doit fonctionner avec la structure de données paramétrée.

List<int>    li;
List<double> ld;
List<Point>  lp;

Pour faire une liste de points, il faudra que la classe Point redéfinisse/surcharge tous les opérateurs et méthodes nécessaires : forme de Coplien, opérateurs de comparaison, ...

Bonus

On a tous les éléments pour compléter l'interface de la classe List lorsque l'on a un itérateur opérationnel (même si la bibliothèque standard propose encore bon nombre d'autres méthodes soit parce que la liste de la bibliothèque standard peut être parcourue dans les deux sens, soit parce que on peut avoir des itérateurs "constants".

• Ajouter une méthode find() qui permet de trouver un élément dans la liste et renvoie un itérateur sur celui-ci.
• Écrire une méthode remove() qui permet d'effacer l'élément repéré par un itérateur.
• Écrire une méthode insert() qui permet d'insérer un élément donné après la position (itérateur) donnée

Complément

Voici une liste de déclarations... une n'est pas valide, pouvez-vous la reconnaître ? Que font les autres ?

Classe c1;
Classe c2();
Classe c3(12);

Classe * p1 = new Classe;
Classe * p2 = new Classe();

Exception e;
throw e;

throw Exception;
throw Exception();

• c1 est un objet de la classe Classe construit avec le constructeur par défaut.
• c2 est un prototype de fonction sans paramètre et qui renvoie un objet de la classe Classe. Ce n'est pas une création d'objet.
• c3 est un objet de la classe Classe construit avec un constructeur avec paramètre.
• p1 et p2 sont des pointeurs sur des objets créés dynamiquement par le constructeur par défaut.
• thow permet de lancer tout objet donc la ligne 9 est acceptée
• L'erreur se trouve ligne 11 : Exception est un type donc le compilateur ne comprend pas que l'on veut créer un objet, la ligne correcte est celle du dessous.

Les formes utilisées ne semblent pas toujours cohérentes mais elles visent à lever les ambiguités que peut rencontrer le compilateur.