Remarques préliminaires :

• Un cours complet sur les structures de données appelées "Listes chaînées" est à votre disposition. Les paragraphes "Introduction" à "Généralisation" inclus concernent ce TP. Ils seront donc supposés connus lors des tests correspondants.
• Tous les exercices de ce TP doivent être effectués dans le répertoire dirlstsimple qui sera considéré comme répertoire courant.
• Recopier les fichiers dirptr/config.h, dirptr/CDuree.h, dirptr/CDuree.hxx, dirptr/CDuree.cxx et dirptr/Makefile dans le répertoire courant.
• Rappel : Chemins d'accès aux sources des corrigés.

Sommaire

Structures de données : liste simplement chaînée

exo_01

• Liste des fichiers créés ou modifiés : CElement.h, CElement.hxx, exo_01.cxx, Makefile_01

    Dans l'espace de noms nsSdD (namespace Structures de Données), créer une classe CElement (fichiers CElement.h et CElement.hxx) possédant les deux données membres privées et les fonctions membres publiques (en inline) suivantes (figure 1) :

• une valeur entière m_Info,
• un pointeur vers l'élément suivant m_Suivant.
• un constructeur permettant d'initialiser les deux données membres,
• les accesseurs GetInfo() et GetSuivant().

figure 1 : élément d'une liste simplement chaînée

     A cause de la présence d'un pointeur comme donnée membre, interdire le constructeur par copie et l'affectation.

     Dans le fichier exo_01.cxx, écrire la fonction Exo_01() qui effectue les opérations suivantes :

• crée successivement 10 éléments contenant les valeurs entières 0..9, chaque nouvel élément étant chaîné à l'élément précédemment créé,

figure 2 : liste simplement chaînée
• affiche toutes les valeurs stockées dans l'ordre dans lequel elles se présentent,
• détruit successivement tous les éléments de la liste.

1. Pour rendre l'utilisation de la classe CElement plus générale, il faudrait ajouter les modifieurs SetInfo() et SetSuivant().
2. Les deux paramètres du constructeur peuvent avoir des valeurs par défaut, n'importe laquelle pour m_Info et 0 pour le pointeur vers le suivant.
3. On constate que tous les éléments sont affichés dans l'ordre inverse de leur création. Cette structure peut donc servir de point de départ pour créer une pile d'entiers.
4. Si les éléments doivent toujours être détruits tous ensemble comme ci-dessus, et jamais individuellement, il est beaucoup plus efficace d'ajouter un destructeur approprié. L'ajouter à la classe CElement.
5. L'ensemble des éléments chaînés entre eux ainsi que la tête (appelée Premier sur la figure 2) constituent une liste dynamique simplement chaînée. C'est une structure de données, construction qui organise physiquement les données entre elles, en leur conférant certaines propriétés :
• un ordre, qui est leur rang,
• tout élément a un successeur, sauf le dernier,
• le premier élément, appelé la tête de liste, permet, par récurrence, d'accéder à tous les éléments de la liste. Si la tête n'est pas connue, la liste est inaccessible. La tête est de type différent (CElement *) des éléments qui composent cette liste (CElement).

    Nous verrons ultérieurement qu'il est possible de donner d'autres implémentations d'une liste simplement chaînée.

Corrigés : exo_01.cxx      -      CElement.h      -      CElement.hxx      -      Makefile_01

Sommaire

Transformation en liste générique

exo_02

• Liste des fichiers créés ou modifiés : CElemGen.h, CElemGen.hxx, exo_02.cxx, Makefile_02

    Recopier les fichiers CElement.h, CElement.hxx, Makefile_01 et exo_01.cxx dans les fichiers CElemGen.h, CElemGen.hxx, Makefile_02 et exo_02.cxx. Transformer la fonction Exo_01() en Exo_02() et la classe CElement en classe générique CElemGen de paramètre de généricité T (figure 3). Ajouter à la fonction Exo_02() une instruction typedef permettant, en instanciant la classe générique CElemGen par le type int, d'utiliser le reste de la fonction sans aucune autre modification.

figure 3 : élément générique d'une liste simplement chaînée

    Modifier le destructeur de CElemGen pour qu'il ne détruise plus la totalité de la liste (cela revient à avoir un destructeur vide).

    Mettre à jour le fichier Makefile_02 (ajout des variables de dépendance CELEMGEN_H et CELEMGEN_HXX). Afin de pouvoir utiliser le dernier fichier Makefile??? pour compiler aussi les exercices précédents, on ne supprimera pas les éléments qui ne sont plus utiles pour l'exercice courant.

    Compiler et tester.

   Remarques :

1. la liste est dite non intrusive car chaque élément de la liste contient  un lien (une donnée membre et éventuellement des fonctions membres pour le manipuler). L'information existe indépendamment du chaînage, elle est dupliquée par le constructeur qui la recopie.
2. lorsqu'un élément contient une information et un chaînage, la relation est dite HasA.

Corrigés : exo_02.cxx      -      CElemGen.h      -      CElemGen.hxx      -      Makefile_02

Sommaire

Donnée membre m_Info non élémentaire

exo_03

• Liste des fichiers créés ou modifiés : exo_03.cxx, Makefile_03

    Dans cet exercice, l'Info est une donnée de la classe CDuree. Recopier les fichiers exo_02.cxx et Makefile_02 dans exo_03.cxx et Makefile_03. Modifier la fonction Exo_02() en Exo_03() pour créer une liste de 10 durées, les afficher successivement au moyen de l'injecteur et détruire la liste.

figure 4 : élément générique d'une liste simplement chaînée instancié par la classe CDuree.

    Mettre à jour le fichier Makefile_03 (ajout des variables de dépendance CDUREE_H et CDUREE_HXX, et compilation de CDuree.cxx). Compiler et tester.

Corrigés : exo_03.cxx      -      Makefile_03

Sommaire

Dérivation d'une classe "lien"

exo_04

• Liste des fichiers créés ou modifiés : exo_04.cxx, CLinkSimple.h, CLinkSimple.hxx, CDureeLink.h, CDureeLink.hxx, CDureeLink.cxx, Makefile_04

    La classe CElement développée dans le premier paragraphe présente deux parties très distinctes : les données et fonctions membres portant sur la partie chaînage (m_Suivant et GetSuivant()) et celles portant sur l'information (m_Info et GetInfo()). Par ailleurs, l'accès aux fonctions membres de la partie générique Info de chaque élément nécessite deux appels, ce qui alourdit l'écriture, comme le montre l'exemple ci-dessous :
 

typedef CElemGen <CDuree> CElement; CElement * Ptr; // .. Ptr->GetInfo().GetDuree();

    Une solution fait disparaître cet inconvénient (figure 5) : développer une classe CLinkSimple possédant toutes les fonctionnalités nécessaires à la gestion du chaînage (m_Suivant et GetSuivant()), puis lui ajouter par dérivation celles portant sur l'information (une durée par exemple).

figure 5 : classe CDureeLink possédant toutes les caractéristiques d'un lien et d'une durée

    Dans les fichiers CLinkSimple.h et CLinkSimple.hxx, écrire la classe CLinkSimple correspondante. La classe CLinkSimple doit logiquement faire partie de l'espace de noms nsSdD puisqu'elle est faite pour créer des listes chaînées.

    Puis recopier les fichiers CDuree.h, CDuree.hxx et CDuree.cxx dans les fichiers CDureeLink.h, CDureeLink et CDureeLink.cxx. Plusieurs modifications doivent être effectuées :

• l'identificateur CDuree doit être partout remplacé par CDureeLink,
• la classe CDureeLink doit être dérivée de CLinkSimple (penser à inclure le fichier correspondant),
• le constructeur par copie et l'opérateur = doivent être interdits, car la duplication du chaînage n'aurait aucun sens,
• le constructeur restant de CDureeLink doit être légèrement modifié, car il doit construire lui-même l'objet CLinkSimple dont il est dérivé (ajouter un paramètre pour initialiser la donnée membre m_Suivant),
• La classe CDureeLink ne peut faire partie de l'espace de noms nsSdD, car elle n'a aucun intérêt général pour les sutructures de données et est au contraire très spécifique. Nous la placerons donc de nouveau dans nsWorking.

    Recopier le fichier exo_03.cxx dans exo_04.cxx. Transformer la fonction Exo_03() en Exo_04() en utilisant la nouvelle classe CDureeLink.

Remarque :

Un pointeur sur un objet d'une classe fille pointe toujours implicitement sur un objet de la classe mère (un objet de la classe fille est un objet de la classe mère, éventuellement complété  : un chat est un mammifère). L'inverse n'est pas vrai (un mammifère n'est pas forcément un chat). La fonction GetSuivant() renvoyant un pointeur vers un CLinkSimple, la conversion en un pointeur vers la classe fille doit être explicitement demandée. Il s'agit d'un transtypage (cast) vers le bas, ou down-cast :

CDureeLink * Ptr = ... // .. Ptr = static_cast <CDureeLink *> (Ptr->GetSuivant());

Cette conversion est effectuée au moment de la compilation, contrairement à la conversion dynamic_cast, qui ne peut être effectué qu'à l'exécution (ligature dynamique).

    Recopier le fichier Makefile_03 dans le fichier Makefile_04 (ajout des variables de dépendance CLINKSIMPLE_H, CLINKSIMPLE_HXX, CDUREELINK_H et CDUREELINK_HXX, et compilation de CDureeLink.cxx). Compiler et tester.

    Pour éviter ce transtypage, il faut surcharger, dans la classe fille, toutes les fonctions membres publiques de la classe mère dont la valeur de retour nécessiterait un transtypage. Ici, il s'agit seulement de la fonction GetSuivant(). Nous adopterons cette solution chaque fois que cela sera nécessaire.

    Dans la classe CDureeLink, sucharger la fonction GetSuivant(). Dans la fonction Exo_03(), ajouter une boucle d'affichage sans transtypage. Compiler et tester.

Remarque :

• La liste est dite intrusive car un objet de la classe CDuree n'existe pas en dehors du chaînage : le constructeur ne recopie pas dans l'objet une durée préexistante, mais construit la durée en même temps que l'élément de la liste.

Corrigés : exo_04.cxx      -      CLinkSimple.h      -      CLinkSimple.hxx      -      CDureeLink.h      -      CDureeLink.hxx      -      CDureeLink.cxx      -      Makefile_04

Sommaire

Dérivation double d'une classe "lien"

exo_05

• Liste des fichiers créés ou modifiés : exo_05.cxx, CDureeAndLink_05.h, CDureeAndLink_05.hxx, Makefile_05

    Il n'est pas toujours possible de dériver la classe CLinkSimple en une autre classe, comme nous l'avons fait avec la classe CDureeLink, par exemple si le corps de la classe CDuree est livré sous forme compilée. De plus, un important travail de réécriture et d'adaptation, source potentielle d'erreurs, est nécessaire.

    Conceptuellement, la solution proposée n'est pas non plus satisfaisante : même si, techniquement, on peut faire dériver une durée d'un lien, il n'y a aucune raison de considérer qu'une durée est d'abord et avant tout un lien, enrichi d'informations complémentaires.

    Enfin, l'impossibilité de créer des durées en dehors d'une liste rend la solution inefficace.

    La double dérivation que le C++ est le seul à autoriser, offre une alternative intéressante (figure 6).

figure 6 : classe CDureeAndLink héritant de toutes les caractéristiques d'un lien et d'une durée

    Dans les fichiers CDureeAndLink_05.h et CDureeAndLink_05.hxx, dériver la classe CDureeAndLink (espace de noms nsWorking), des classes CLinkSimple et CDuree par double dérivation publique. Comme précédemment, le constructeur par copie et l'opérateur d'affectation = doivent être interdits, et le constructeur restant doit être modifié. Ne pas oublier la surcharge de GetSuivant().

    Attention : les données membres des classes mères sont par défaut private, ce qui pourrait poser certains problèmes ...

    Recopier le fichier exo_04.cxx dans exo_05.cxx. Transformer la fonction Exo_04() en Exo_05() en utilisant la nouvelle classe CDureeAndLink.

    Recopier le fichier Makefile_04 dans le fichier Makefile_05, ajouter les variables de dépendance CDUREEANDLINK_05_H, CDUREEANDLINK_05_HXX, la compilation de CDuree.cxx et ajout de CDuree.o à l'édition de liens).

    Compiler et tester.

Remarque : cette technique est inapplicable si l'information est d'un type prédéfini : il est par exemple impossible de faire une liste d'entiers int.

Corrigés : exo_05.cxx      -      CDureeAndLink_05.h      -      CDureeAndLink_05.hxx      -      Makefile_05

Sommaire

Introduction de la tête dans la liste

exo_06

• Liste des fichiers créés ou modifiés : exo_06.cxx, CTeteLinkSimple.h, CTeteLinkSimple.hxx, CTeteLinkSimple.cxx, CDureeAndLink.h, CDureeAndLink.hxx, Makefile_05

    Nous avons vu au cours des exercices précédents que la liste était constituée de deux "objets", un pointeur vers le premier élément de la liste et l'ensemble des éléments chaînés entre eux. Il est en général maladroit et source potentielle d'erreurs de séparer ces deux informations. Une solution consiste à créer une classe CListeSimple qui contient la tête de la liste, et de la doter de fonctions membres permettant d'accéder indirectement aux éléments chaînés. Elle sera mise en œuvre dans les TDs suivants. Une autre solution, très simple, consiste à ajouter dans la classe CLinkSimple, une donnée membre statique m_Tete, initialisée par le constructeur, et mise à jour à chaque ajout ou chaque suppression. C'est cette dernière solution que nous adopterons ici.

    Deux possibilités de mise en oeuvre peuvent être envisagées :

• la dérivation permettrait d'enrichir une classe (CLinkSimple) en une classe CTeteLink par exemple, en lui ajoutant des données et des fonctions membres. L'expérience rapportée dans la littérature montre que certains développeurs abusent de cette technique, parfois seulement pour compenser une conception insuffisante, et cela conduit à une prolifération de classes très peu différentes les unes des autres, qui finissent par être ingérables. Nous ne retiendrons pas cette technique ici, qui pourrait cependant être justifiée si on considère que la nouvelle classe, bien que peu enrichie, est cependant par nature très différente de sa classe de base.
• la modification du code de la classe CLinkSimple en y ajoutant directement les nouvelles données et fonctions membres. Elle traduit elle aussi un défaut d'analyse, et est de ce fait peu recommandable. Cependant, elle est une pratique courante, permettant l'évolution et l'amélioration du code, et reste acceptable tans que le code reste compatible avec les versions précédentes, ce qui est le cas de la modification proposée ici. C'est la solution que nous retiendrons, mais c'est seulement pour conserver les différentes versions que nous travaillerons sur une copie de CLinkSimple.

    Recopier les fichiers CLinkSimple.h et CLinkSimple.hxx dans CTeteLinkSimple.h et CTeteLinkSimple.hxx. Ajouter à la classe :

• la donnée membre statique m_Tete,
• la fonction membre GetTete().

    Recopier les fichiers CDureeAndLink_05.h et CDureeAndLink_05.hxx dans les fichiers CDureeAndLink.h et CDureeAndLink.hxx. Faire les modifications nécessaires concernant la tête de la liste.

    Recopier le fichier exo_05.cxx dans le fichier exo_06.cxx, et faire les modifications nécessaires.

    Recopier le fichier Makefile_05 dans le fichier Makefile_06, le mettre à jour.

    Compiler et tester.

Remarque : cette solution est inapplicable s'il doit y avoir plusieurs instanciations de la classe CTeteLinkSimple (il ne peut y avoir qu'une seule tête pour plusieurs listes).

Corrigés : exo_06.cxx      -      CTeteLinkSimple.h      -      CTeteLinkSimple.hxx      -      CTeteLinkSimple.cxx      -      CDureeAndLink.h      -      CDureeAndLink.hxx      -      Makefile_06

Sommaire

Liste non propriétaire

exo_07

• Liste des fichiers créés ou modifiés : exo_07.cxx

    Toutes les listes construites précédemment sont appelées listes propriétaires. Cela signifie que l'information est dupliquée (valeur recopiée par le constructeur) dans la donnée membre m_Info lorsqu'elle est insérée dans la liste, et que cette copie est détruite, et donc perdue, lorsqu'est détruit l'élément de la chaîne qui la contient.

    Ce type de structure (c'est généralisable à tout autre type : arbre, graphe, etc...) ou de conteneur (dictionnaire, pile, etc...) présente trois inconvénients :

• il nécessite l'existence d'un constructeur par recopie de l'information, ce qui n'est pas le cas de toutes les classes,
• il peut conduire à une importante perte de temps et d'espace pour des informations de grande taille (par exemple des chaînes de caractères, images, etc...),
• il interdit l'appartenance d'une même information à plusieurs structures.

figure 7 : élément d'une liste non propriétaire

    La liste est dite non propriétaire. Elle est illustrée par la figure 8 :

figure 8 : liste non propriétaire d'éléments de type CDuree

    En réutilisant la classe générique template <class T> class CElemGen écrite dans l'exercice 2, deux solutions sont possibles :

• modifier le type de la donnée membre m_Info (et de la valeur de retour de la fonction GetInfo()) en T*,
• instancier la classe par un type pointeur.

    N'importe quel fichier Makefile peut être utilisé. Compiler et tester.

Corrigés : exo_07.cxx

Sommaire

Téléchargement des corrigés :

Chemins d'accès aux sources des corrigés :

© D. Mathieu     mathieu@romarin.univ-aix.fr
I.U.T.d'Aix en Provence - Département Informatique