Copy of https://perso.isima.fr/loic/cpp/td_list.php
tete du loic

 Loïc YON [KIUX]

  • Enseignant-chercheur
  • Référent Formation Continue
  • Responsable des contrats pros ingénieur
  • Référent entrepreneuriat
  • Responsable de la filière F2 ingénieur
  • Secouriste Sauveteur du Travail
mail
loic.yon@isima.fr
phone
(+33 / 0) 4 73 40 50 42
location_on
Institut d'informatique ISIMA
  • twitter
  • linkedin
  • viadeo

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

 Cette page commence à dater. Son contenu n'est peut-être plus à jour. Contactez-moi si c'est le cas!

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 :

  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.
  1. Écrire les méthodes pop_front() et pop_back() qui enlèvent respectivement l'élément en tête et en fin de liste
  2. Écrire la méthode size() qui permet de connaître le nombre d'éléments de la liste
  3. 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).

L'itérateur va donc encapsuler un pointeur de cellule.

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.

Nous vous conseillons de garder ce dernier constructeur privé : en effet, il est très dangereux de laisser tout à chacun créer un itérateur de cette manière, sauf une liste. La liste sera donc déclarée amie de la classe itérateur.

  1. 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").
  2. 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.

  1. 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
  2. Écrire l'operator!=().

C'est une fonction qui renvoie vrai si les deux itérateurs pointent sur des éléments différents.

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

Il y a bien deux versions de l'operator*() : une constante et l'autre pas !

int&        operator*()       throw (NullIteratorException);
const int&  operator*() const throw (NullIteratorException);
  1. Pourquoi ne pas ajouter une exception si l'utilisateur essaie de déréférencer un itérateur nul ?
  2. 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".

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();

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