Dans le fichier node.hpp, créer la classe générique CNode :

template 
class CNode
{
private:
    T m_Data;
    CNode* m_Next;
public:
    //constructor
    CNode ();
    //destructor
    ~CNode ();

    //getter / setter
    TODO
};

1. Faites en sorte d’avoir un constructeur par défaut;
2. Ecrivez le profil des getter et des setter;
3. Pour cet exercice, faites en sorte que le destructeur affiche la contenu de la case supprimée (ce dernier est supposé être injectable dans le flux écran);
4. Ecrivez le corps de toutes les fonctions.

Tester votre classe avec le code suivant :

void ListeSimple (void)
{
    std::cout << "ListeSimple : \n\n";

    CNode* Tete = nullptr;

    // Le dernier element cree est toujours le premier de la liste


    for (unsigned i (0); i < 5; ) {
        Tete = new CNode (i++, Tete);
        std::cout << Tete << endl;
    }

    for (CNode* Ptr (Tete); Ptr; Ptr = Ptr->GetNextNode ())
        std::cout << Ptr->GetData() << "; ";

    std::cout << '\n';

    // Dans cette version, le destructeur de C1Link detruit son
    //   suivant donc la destruction de la liste est recursive

    delete Tete;

}// ListeSimple ()

Dans le fichier list.hpp, créer la classe générique CList de signature suivante :

template 
class CList
{
private:
    CNode* m_Head;
public:
    CList ();
    ~CList ();
   //ajout en tête de liste
    void push_front (const T & val);
   //affichage
    void Show () const;
    //recherche d'un élément dans la liste, renvoie le pointeur du maillon si l'élément est présent, nullptr sinon
    CNode* Find (const T & val) const;
    //ajout d'une valeur après un maillon de la liste
    void Add (const T & val, CNode*);
    //détache un maillon de la liste et le supprime
    void Delete (CNode*);
};

Ecrivez le corps de toutes les fonctions de cette classe.

Tester votre classe avec le code suivant :

void ListeSimpleV2 ()
{
    cout << "ListeSimpleV2 : \n\n";

    CList AList;

    // Le dernier element cree est toujours le premier de la liste

    for (unsigned i (0); i < 5; ) 
    {
        AList.push_front (i++);
    }

    AList.Show ();

    int i;
    cin >>i;
    CNode* ptr = AList.Find (i);
    AList.Add (3*i, ptr);
    AList.Show ();

    cout << ((ptr != NULL)?  " " : "non ") << "trouve" << endl;

}

Ajouter à la classe CList une donnée membre qui indique l’adresse de la queue (dernier élément) de la liste.

Modifier la fonction Add en mettant à jour cette variable lorsque cela est nécessaire.

Ajouter à la classe la fonction push_back () de signature :

void push_back (const T & val);

Tester votre fonction.

La donnée membre m_Head change de sémantique : elle ne pointe plus vers la tête réelle mais vers une tête fictive nommée m_fictionaHead.

Modifier toutes les fonctions de la classe CList pour appliquer cette modification.

Reprenez la classe CNode de l’exercice précédent, renommez les données membres m_Prec et m_Next en respectivement m_LC (left child) et m_RC (right child).
Mettez à jour les accesseurs et modifieurs correspondants.

En vous inspirant de la classe CList, créez la classe CRDTree (arbre aléatoire – Random Tree), elle aussi générique.

Les modifications sont les suivantes :

1. le constructeur contient un paramètre (la donnée), crée un smart pointer contenant cette donnée et initialise la racine à cette adresse (ie, on n’a plus de tête fictive);
2. la fonction show () parcours toutes les branches de l’arbre;
3. la fonction add (), qui ne contient qu’un paramètre (la valeur à insérer dans l’arbre), doit avoir le comportement suivant :
   1. s’il n’y a pas de fils gauche, alors on insère dans ce dernier;
   2. s’il n’y a pas de fils droit, alors on insère dans ce dernier;
   3. sinon on explore aléatoirement (rand () % 2) le sous arbre de gauche, ou de droite.

Random Tree

Modifier l’exercice précédent de façon à obtenir un arbre binaire de recherche.

Seule la fonction add () doit être modifiée.

Ecrire ensuite le prédicat find() qui renvoie vrai si le paramètre passé en argument est présent dans l’arbre, faux sinon.

Arbre binaire de recherche

Récupérer l’archive suivante : List.zip.

Cette liste contient une tête fictive en début de liste ainsi qu’un pointeur vers le dernier élément réel de la liste (utile notamment pour faire l’instruction push_back ()).

Transformer tous les pointeurs du c en pointeur intelligent (voir amphi2 et amphi4)

Dans un premier temps, transformer la classe CNode, puis modifier le corps de ListeSimple ().
Dans un second temps, transformer la classe CList, l’unique modification de la fonction ListeSimpleV2 () ne doit être que sur la nature du pointeur de recherche (NB: auto est autorisé exceptionnellement car, normalement, on ne devrait pas connaitre la structure interne de la liste en dehors de la classe CList).