C et C++ partie H
Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.
C++ : Chaînages
Les activités #.dec (dec pour Découverte) consistent à étudier des présentations explicatives et à traiter tous les exercices de découverte proposés. Si vous ne répondez pas correctement à un exercice de découverte, revenez en arrière pour relire les explications et identifier la cause de votre erreur.
Les activités #.ent (ent pour Entrainement) consistent à traiter des exercices d’entraînement. Vous devez d’abord tenter de traiter ces exercices sans dévoiler d’indice ni regarder la solution. Vous pouvez remonter dans le document pour relire certaines explications ou consulter les solutions des exercices de découverte ou d’entraînement précédemment traités.
Activité de découverte H.dec
Dans cette partie, nous explorons la manière d’implémenter des structures de données, telles que des listes et des arbres, constituées de différentes instances de classes reliées par des pointeurs.
H.dec1 : La revanche des pointeurs
Prérequis
| Partie G |
|---|
Objectif
| Réaliser des structures de données extensibles qui consomment exactement la quantité de mémoire dont elles ont besoins. |
|---|
La classe standard vector permet de créer des listes extensibles, mais au prix d’une réservation de mémoire souvent supérieure aux besoins réels. Les données contenues dans une instance de vector sont physiquement stockées dans un tableau. Nous allons étudier une représentation différente.
Moyen
| Décomposer une liste en un élément de tête et une liste des autres éléments |
|---|
Une liste peut être définie par induction de la manière suivante :
Une liste est :
- soit vide,
- soit constituée d’un élément de tête et d’une liste, appelée reste ou queue, contenant les autres éléments.
Par exemple :
- La liste [1, 2, 3] a pour tête 1 et pour reste la liste [2, 3].
- La liste [2, 3] a pour tête 2 et pour reste la liste [3].
- La liste [3] a pour tête 3 et pour reste la liste vide [].
La classe suivante permet de représenter une liste de chaines de cette manière.
class Liste
{
private:
Liste* reste;
string tete;
Liste(const string& tete, Liste* reste);
public:
Liste();
const string& getTete() const;
const Liste& getReste() const;
bool estVide() const;
void add(const string& tete);
void affiche() const;
void afficheDebug() const;
int longueur() const;
};
Examinons les attributs.
- Si la liste est vide, alors
tetecontient la liste vide""etrestecontient la valeurnull_ptr, qui est une autre notation pourNULL. - Si la liste n’est pas vide, alors
tetecontient l’élément de tête etrestepointe le reste de la liste.
Voici un exemple de représentation en mémoire d’une liste de deux éléments, "bbb" et "aaa" :

La liste se présente comme une succession de maillons représentés par des instances de Liste. Le dernier maillon représente une liste vide et sert aussi à terminer le chaînage.
Il sera tout à fait possible que le premier maillon, qui contient la tête de la liste si celle-ci n’est pas vide (ou qui représente la liste vide dans le cas contraire) soit placé dans la pile, mais tous les autres devront impérativement être dans le tas pour éviter des problèmes d’accident mémoire lors de la destruction d’une liste.
Le constructeur par défaut crée une liste vide. L’attribut tête est initialisé implicitement par le constructeur par défaut de la classe string.
Liste::Liste()
{
reste = nullptr;
}
Le constructeur à deux paramètres étend une liste par ajout d’un élément en tête. Ce constructeur est privé. C’est un choix de conception. Pour sécuriser l’extension d’une liste existante par ajout d’un élément en tête de liste, les personnes utilisatrices de la classe devront utiliser la méthode publique add.
Liste::Liste(const string& tete, Liste* reste) :
tete(tete), reste(reste)
{
}
Voici les deux méthodes d’accès :
const string& Liste::getTete() const
{
return tete;
}
const Liste& Liste::getReste() const
{
return *reste;
}
Il y a plusieurs const qui apparaissent ici. Les const en début de ligne indiquent que les références retournées ne permettent pas la modification des attributs désignés par ces références. Le retour de références plutôt que de copies a pour seul but d’améliorer l’efficacité.
Les const qui apparaissent en fin de ligne indique que ces méthodes ne modifient pas les attributs de l’instance courante (l’instance avec laquelle elles sont appelées).
La méthode add sera utilisée pour l’ajout d’un élément (une instance de string) en tête de la liste courante. Cette méthode est conçue de manière à ne pas changer l’adresse d’implantation en mémoire de la tête de la liste à modifier. La motivation de ce choix est d’éviter certaines situations propices à de futurs accidents mémoire et effets de bords, telle que cette situation…

…ou même des situations encore pires où plusieurs maillons seraient dans la pile.
La définition de la méthode add n’est pas triviale et doit être regardée de près.
void Liste::add(const string& nouvTete)
{
Liste* m = new Liste(this->tete, this->reste);
this->tete = nouvTete;
this->reste = m;
}
Pour comprendre le principe de l’ajout d’un nouvel élément de tête nouvTete, partons de la situation suivante :

La variable t désigne la liste ["aaa", "bbb"]. L’instance de Liste qui contient la tête de la liste est dans la pile, mais elle pourrait être dans le tas. Les maillons suivants sont dans le tas et ne pourraient pas être dans la pile.
On veut ajouter un nouvel élément "ccc" en tête de liste, sans changer l’adresse mémoire du premier maillon de la liste :

L’implantation en mémoire du premier maillon n’a pas changé, mais son contenu, c’est à dire les valeurs de ses attributs, ont changés. Les attributs initiaux du maillon de tête ont été copiés dans un nouveau maillon créé dans le tas, qui fait office de deuxième maillon de la nouvelle liste.
Exercice de découverte H.dec.x1
Donnez les lignes de code permettant de créer la liste dont la représentation en mémoire est illustrée ci-dessus.
Liste w;
w.add("aaa");
w.add("bbb");
w.add("ccc");
Donnez les lignes de code permettant de créer une liste identique, mais complètement dans le tas.
Liste* t = new Liste();
t->add("aaa");
t->add("bbb");
t->add("ccc");
Examinons maintenant le code de la méthode affiche (et celui de la méthode estVide qu’elle utilise).
bool Liste::estVide() const
{
return (reste == nullptr);
}
void Liste::affiche() const
{
if(estVide())
{
cout << "." << endl;
}
else
{
cout << getTete() << " ";
reste->affiche();
}
}
La représentation d’une liste comme étant soit vide, soit constituée d’un élément de tête et d’une liste, se prête à une implémentation récursive. On peut expliciter le code en français de la façon suivante :
Pour afficher une liste vide, on écrit un point
.à l’écran.Pour afficher une liste non vide, on écrit à l’écran son élément de tête, puis on affiche la liste constituée du reste de ses éléments.
Exercice de découverte H.dec.x2
Définissez une méthode récursive int Liste::longueur() qui retourne la longueur de la liste courante.
int Liste::longueur() const
{
if(estVide()) return 0;
else return 1 + getReste().longueur();
}
H.dec2 : Libérer la mémoire
Prérequis
| Parties G, H.dec1 |
|---|
Objectif
| Libérer la mémoire occupée par une liste chaînée. |
|---|
La classe présentée dans la section précédente comportait un destructeur implicite qui détruit l’instance courante, mais pas sa ramification.
Si on exécute le code suivant…
Liste* w = Liste::vide();
w = w->add("aaa");
w = w->add("bbb");
w->affiche();
delete w;
…tout semble bien se passer. Mais en réalité il y a une fuite mémoire.

Le destructeur implicite a libéré uniquement la mémoire occupée par l’instance de Liste pointée par w, mais pas les instances suivantes dans le chaînage.
Il nous faut implémenter un destructeur explicite.
Moyen
| Implémenter un destructeur récursif |
|---|
Voici la définition d’un destructeur correct de la classe Liste présentée dans la section précédente.
Liste::~Liste()
{
if(reste != nullptr)
{
delete reste;
}
}
La destruction de l’instance courante, celle à laquelle l’instruction delete a été appliquée, est automatiquement réalisée. Le code du destructeur sert uniquement à détruire la ramification.
Pour bien visualiser ce qui se passe, nous allons utiliser une version de la méthode d’affichage qui affiche les adresses des instances de Liste :
void Liste::afficheDebug()
{
cout << "@" << this << "-> ";
if(reste == nullptr)
{
cout << "." << endl;
}
else
{
cout << tete << endl;
reste->afficheDebug();
}
}
La première ligne affiche this, c’est à dire l’adresse de l’instance courante.
Nous allons également ajouter un affichage au destructeur :
Liste::~Liste()
{
cout << "Exécution destructeur de @" << this
if(reste != nullptr)
{
cout << "Appel destructeur de @" << reste;
delete reste;
}
cout << "Destruction de @" << this << endl;
}
Maintenant, exécutons la fonction suivante :
void test_Liste1()
{
Liste w;
w.add("aaa");
w.add("bbb");
w.afficheDebug();
}
Voici l’affichage obtenu (l’indentation a été ajoutée pour faciliter la lecture) :
@0x16fdff300-> bbb
@0x100727250-> aaa
@0x100727230-> .
Exécution destructeur de @0x16fdff300 :
Appel destructeur de @0x100727250
Exécution destructeur de @0x100727250 :
Appel destructeur de @0x100727230
Exécution destructeur de @0x100727230 :
Destruction de @0x100727230
Fin d'exécution du destructeur
Destruction de @0x100727250
Fin d'exécution du destructeur
Destruction de @0x16fdff300
Fin d'exécution du destructeur
L’appel du destructeur avec l’instance @0x16fdff300 (située dans la pile) :
- appelle le destructeur avec l’instance
@0x100727250(située dans le tas), - puis détruit effectivement l’instance
@0x16fdff300.
L’appel récursif du destructeur avec l’instance @0x100727250 :
- appelle le destructeur avec l’instance
@0x100727230, - puis détruit effectivement l’instance
@0x100727250
L’appel du destructeur avec l’instance @0x100727230 :
- n’appelle pas de destructeur car l’instance à détruire n’a pas de ramification (c’est le dernier maillon du chainage).
- détruit l’instance
@0x100727230.
Exercice de découverte H.dec.x3
On exécute la fonction suivante :
void test_Liste2()
{
Liste* w = new Liste();
w->add("aaa");
w->add("bbb");
w->affiche();
}
La liste désignée par w sera-t-elle complètement détruite, partiellement détruite ou pas du tout détruite. Est-il nécessaire d’ajouter quelque chose pour qu’elle soit complètement détruite ?
Elle n’est pas détruite du tout, car les instances de classe situées dans le tas (créées par new) ne sont jamais détruite automatiquement. Il faut les détruire avec delete.
Pour assurer la libération complète de la mémoire, il faut écrire :
void test_Liste2()
{
Liste* w = new Liste();
w->add("aaa");
w->add("bbb");
w->affiche();
delete w;
}
H.dec3 : Copie en profondeur
Prérequis
| Parties G, H.dec1, H.dec2 |
|---|
Objectif
| Créer une copie d’une liste complètement indépendante en mémoire. |
|---|
La classe Liste de la section précédente n’est pas encore suffisamment sécurisée. Pour s’en convaincre, examinons et exécutons le code suivant :
void test_Liste3()
{
Liste w;
w.add("aaa");
w.add("bbb");
Liste u = w;
w.affiche();
u.affiche();
}
Après l’affichage des listes désignées par w et par u, le programme plante ! Que s’est-il passé ? Pour le comprendre, il faut examiner la situation en mémoire juste avant la fin de l’exécution de la fonction.

La ligne…
Liste u = w;
…a invoqué le constructeur en copie implicite de la classe Liste. Cette ligne est équivalente à celle-ci :
Liste u(w);
Or ce constructeur en copie implicite réalise une copie superficielle. Les valeurs des attributs de l’instance contenue dans la variable w sont copiés dans les attributs de l’instance contenue dans la variable u. Il en résulte que les listes désignées par w et u partagent la même ramification, ce qui peut être source d’effets de bord, mais aussi d’accidents mémoire.
En l’occurrence, à l’issue de l’exécution de la fonction test_liste3, les variables u et w sont automatiquement détruites par invocation du destructeur de la classe Liste. La destruction d’une des variables entraîne la destruction de l’instance qu’elle contient et de toute sa ramification. Ensuite, la destruction de l’autre variable appelle une deuxième fois le destructeur, qui tente de détruire à nouveau l’instance contenant la chaine "aaa". Comme cette instance a déjà été détruite, il y a accident mémoire.
Pour éviter ce problème, il faut définir un constructeur en copie explicite.
Moyen
| Un constructeur en copie réalisant une copie en profondeur |
|---|
Voici la définition d’un constructeur en copie de la classe Liste qui réalise une copie en profondeur de la liste utilisée comme modèle pour créer une nouvelle liste :
Liste::Liste(const Liste& modele) :
tete(modele.tete)
{
if(modele.reste==nullptr)
{
reste = nullptr; // Ligne A
}
else
{
reste = new Liste(*(modele.reste)); // Ligne B
}
}
La clé de la copie en profondeur est l’utilisation de la récursivité : ce constructeur en copie s’appelle lui-même autant de fois que nécessaire pour reproduire toute la ramification de la liste modèle.
Si le modèle est une liste vide, alors la ligne A est exécutée, ce qui a pour effet d’assigner la valeur nullptr à l’attribut reste de l’instance de Liste en cours de construction. Le résultat est la construction d’une instance de Liste sans ramification qui représente une liste vide.
Si le modèle n’est pas une liste vide, alors la ligne B est exécutée, ce qui a pour effet d’appeler le constructeur en copie pour créer une copie en profondeur (dans le tas) de la ramification et la rattacher à l’instance de Liste en cours de création.
Il faut bien comprendre l’utilisation de l’opérateur de dépointage * lors de l’appel récursif du constructeur en copie. Ce constructeur a pour paramètre la référence de l’instance de Liste à copier. Or model.reste est un pointeur sur la liste à copier. Pour passer la référence d’une donnée pointée, il faut utiliser l’opérateur de dépointage.
Exercice de découverte H.dec.x4
Donnez les lignes de code permettant de :
- créer une liste vide dans la pile,
- puis de lui ajouter les mots
"xxx"et"yyy", - puis de créer une copie de cette liste située entièrement dans le tas, en utilisant le constructeur en copie de la classe
Liste, - puis d’afficher la liste initiale et sa copie,
- puis de libérer la mémoire occupée par la copie.
Liste w;
w.add("xxx");
w.add("yyy");
Liste* t = new Liste(w);
w.affiche();
t->affiche();
delete t;
Donnez les lignes de code permettant de :
- créer une liste vide dans le tas,
- puis de lui ajouter les mots
"xxx"et"yyy", - puis de créer une copie de cette liste dans une variable de type
Listesituée dans la pile (qui aura une ramification dans le tas), en utilisant le constructeur en copie de la classeListe, - puis d’afficher la liste initiale et sa copie,
- puis de faire ce qui est nécessaire et suffisant pour éviter toute fuite mémoire.
Liste* w = new Liste();
w->add("xxx");
w->add("yyy");
Liste t(*w);
w->affiche();
t.affiche();
delete w;
H.dec4 : Redéfinition de l’opérateur d’assignation
Prérequis
| Parties G, H.dec1, H.dec2, H.dec3 |
|---|
Objectif
| Sécuriser les copies de listes |
|---|
La classe Liste de la section précédente n’est pas encore suffisamment sécurisée ! Pour s’en convaincre, examinons et exécutons le code suivant :
void test_Liste4()
{
Liste w;
w.add("aaa");
w.add("bbb");
Liste u;
u.add("zzz");
w = u; // Ligne A
w.affiche();
u.affiche();
}
À l’exécution, on constate l’affichage…
zzz .
zzz .
…puis le programme se plante ! Pour comprendre ce qui s’est passé, il faut bien voir que le symbole = utilisé en ligne A n’a pas le même sens que le symbole = de l’exemple introductif de la section précédente. Dans la section précédente, ce symbole était utilisé pour initialiser une variable de type Liste par appel du constructeur en copie. Ici, ce même symbole représente l’assignation d’une variable qui a déjà été préalablement déclarée et initialisée.
L’opérateur d’assignation utilisé en ligne A réalise une copie superficielle de l’instance de Liste désignée par la variable u dans l’instance de Liste désignée par la variable w.

Comme le montre l’illustration ci-dessus, la situation en mémoire à l’issue de l’exécution de la ligne A n’est pas reluisante. Non seulement les deux listes w et u partagent la même ramification dans le tas, ce qui est à l’origine de l’accident mémoire ayant pour effet le plantage constaté, mais en plus il y a une fuite mémoire.
Pour éviter cela, nous allons redéfinir l’opérateur d’assignation.
Moyen
| Redéfinition de l’opérateur d’assignation. |
|---|
S’il n’est pas redéfini, l’opérateur d’assignation = réalise une copie superficielle. Voici comment redéfinir l’opérateur d’assignation de la classe Liste pour qu’il réalise une copie en profondeur.
Liste& Liste::operator=(const Liste& modele)
{// Début bloc A
if(reste!=nullptr)
{
delete reste;
}
// Fin bloc A
tete = modele.tete; // Ligne B
// Début bloc C
if(modele.reste==nullptr)
{
reste = nullptr;
}
else
{
reste = new Liste(*(modele.reste));
}
// Fin bloc C
return *this; // Ligne D
}
Dans le code de cette méthode, qui est appelée lorsque l’opérateur d’assignation est utilisé, l’instance courante de Liste est la destination de l’assignation et le paramètre modele désigne la source, c’est à dire la liste à copier dans la destination.
Le bloc A libère, si applicable, la ramification de la liste de destination de l’assignation. Le but est d’éviter une fuite mémoire.
La ligne B remplace la tête de la liste de destination par la tête de la liste modèle.
Le bloc C est identique au code du constructeur en copie. Il permet de recréer une copie complète, complètement indépendante en mémoire, de la liste source.
La ligne D retourne la référence de l’instance courante. Cette valeur de retour n’est utilisée que lors d’assignations en chaine de la forme f = g = h, qui est autorisée en langage C et C++. En C++, toute assignation d’une donnée de type primitif retourne la valeur assignée et toute assignation d’une instance de classe retourne la référence de l’instance assignée.
Voici la situation en mémoire après l’exécution de la ligne A de la fonction test_ligne4 après redéfinition de l’opérateur d’assignation.

Exercice de découverte H.dec.x5
Donnez les lignes de code permettant de :
- créer une liste vide dans la pile, désignée par une variable
w, - puis de lui ajouter les mots
"xxx"et"yyy", - puis de créer une liste vide dans le tas, pointée par une variable
t, - puis d’assigner à
wla liste pointée part.
Liste w;
w.add("xxx");
w.add("yyy");
Liste* t = new Liste();
*t = w;
En résumé, pour sécuriser la gestion mémoire lors de l’utilisation d’une classe avec ramification dans le tas, il y a trois choses à faire :
- Définir une destructeur qui libère toute la mémoire occupée par la ramification de l’instance courante.
- Définir un constructeur en copie explicite qui permettant de créer une nouvelle instance (et sa ramification), identique à une instance existante (et sa ramification), mais complètement indépendante en mémoire.
- Redéfinir l’opérateur d’assignation
=(méthodeoperator=) pour qu’il permette de remplacer l’instance courante (et sa ramification) par la copie d’une autre instance (et sa ramification), sans créer de fuite mémoire.
Activité d’entraînement H.ent
Cette activité est essentielle. C’est grâce à elle que vous apprendrez vraiment à comprendre et utiliser les notions vues précédemment.
Vous devez réaliser au moins une itération et évaluer votre niveau de réussite par une valeur entre 1 et 4 selon les critères habituels.
Si le résultat est 1, vous devrez traiter à nouveau l’activité de découverte précédente, en laissant passer au moins une nuit, avant de revenir à cette activité d’entraînement en réalisant à nouveau l’itération courante. Vous devez aussi essayer d’identifier les points de blocage et demander à votre enseignant de vous aider à les surmonter.
Si le résultat est 2, vous devrez d’abord comprendre ce qui vous a conduit à des erreurs et / ou ce qui vous a bloqué. Si vous avez des doutes, des difficultés, essayez de trouver les réponses dans les présentations et explication de l’activité de découverte précédente et demandez toute l’aide nécessaire à votre enseignant. Ensuite, vous devrez refaire l’activité d’entraînement après un délai d’au moins deux jours et d’au plus une semaine.
Si le résultat est 3, vous devrez revenir traiter certains exercices d’entraînement après un délai de plusieurs semaines pour éviter de perdre vos acquis.
En traitant les exercices, vous devrez considérer que les paramètres des fonctions ont des valeurs correctes. Il ne vous est pas demandé de vérifier si certaines valeurs sont aberrantes au regard de ce que demande l’énoncé. Par exemple, si un paramètre doit être positif pour que le traitement demandé soit possible, vous considérerez que la fonction sera appelée avec une valeur positive de ce paramètre.
Vous pouvez utiliser un ordinateur pour tester vos solutions et les corriger en cas de comportement inattendu. C’est même recommandé, à condition de commencer par réfléchir avant de vous jeter sur le clavier. Si vous pensez avoir une solution différente de celle proposée, ce qui peut arriver souvent, vous ne devez en aucun cas rester dans le doute. Vous devez vérifier si votre solution est correcte ou non, soit en testant votre solution avec un ordinateur, soit en demandant à une personne enseignante.
Itération H.ent1
Exercice d’entrainement H.ent1.1
Nous allons travailler avec la classe Liste définie dans l’activité de découverte.
class Liste
{
private:
Liste* reste;
string tete;
Liste(const string& tete, Liste* reste);
public:
~Liste();
Liste();
Liste(const Liste& modele);
Liste& operator=(const Liste& modele);
const string& getTete() const;
const Liste& getReste() const;
bool estVide() const;
int longueur() const;
void add(const string& tete);
void affiche() const;
void afficheDebug() const;
};
Question 1
Vous devez définir une méthode récursive…
void Liste::addFin(string& s);
…qui ajoute la chaîne désignée par s à la fin de la liste courante.
void Liste::addFin(const string& s)
{
if(estVide())
{
add(s);
}
else
{
reste->addFin(s);
}
}
Question 2
Définissez la méthode récursive…
string Liste::getElem(int pos);
…qui retourne la chaine située en position pos dans la liste courante. La tête de la liste correspond à la position 0. Si pos est au delà de la fin de la liste, la valeur de retour doit être la chaine vide "".
string Liste::getElem(int pos)
{
if(pos==0)
{
return getTete();
}
else if(estVide())
{
return "";
}
else
{
return reste->getElem(pos-1);
}
}
La seule difficulté est de raisonner récursivement. L’élément en position 0 est par définition la tête de la liste. L’élément en position $i$ dans une liste est en position $i-1$ dans le reste de cette liste.
Question 3
Définissez une fonction essai qui réalise les actions suivantes :
- Déclaration d’une variable
wde typeListeinitialisée avec le constructeur par défaut de la classeListe. - Ajout de
"aaa", puis de"bbb"au début de la liste désignée parw. - Ajout de
"ccc"à la fin de de la liste désignée parw. - Affichage de la liste désignée par
w. - Création dans le tas d’une liste vide, pointée par une variable
usituée dans la pile. - Ajout au début de la liste désignée par
ude l’élément situé en position 1 dans la liste désignée parw. La méthodeaddElemdoit être utilisée. - Ajout à la fin de la liste désignée par
ude l’élément situé en position 0 dans la liste désignée parw. La méthodeaddElemdoit être utilisée. - Affichage de la liste désignée par
w. - Ce qui est nécessaire et suffisant pour éviter toute fuite mémoire.
void essai()
{
Liste w;
w.add("aaa");
w.add("bbb");
w.addFin("ccc");
w.affiche();
Liste* u = new Liste();
u->add(w.getElem(1));
u->addFin(w.getElem(0));
u->affiche();
delete u;
}
Exercice d’entrainement H.ent1.2
Le but de cet exercice est de représenter des arbres binaires étiqueté par des entiers à l’aide d’une classe Arbre.
Voici les attributs privés de cette classe :
class Arbre
{
private:
int val;
Arbre* gauche;
Arbre* droit;
public :
// ...
};
Un arbre est :
- soit vide,
- soit constitué d’une étiquette de type
int, d’un fils gauche et d’un fils droit, qui sont des arbres.
Un arbre vide est représenté par une instance de la classe Arbre dont l’attribut val a pour valeur 0 et les attributs gauche et droit ont pour valeur nullptr.
Un arbre $\alpha$ non vide est représenté par une instance de la classe Arbre dont l’attribut val contient l’étiquette racine et dont les attributs gauche et droit pointent vers des instances de la classe Arbre représentant le fils gauche et le fils droit de $\alpha$.
Voici un exemple d’arbre et sa représentation en mémoire. Les traits inclinés représentent la valeur nullptr.

On dote la classe Arbre d’un constructeur par défaut et d’un constructeur superficiel :
Arbre::Arbre()
{
cout << "[D]";
val = 0;
droit = nullptr;
gauche = nullptr;
}
Arbre::Arbre(int val, Arbre* g, Arbre* d)
{
cout << "[S]";
this->val = val;
gauche = g;
droit = d;
}
Le constructeur par défaut crée un arbre vide. Le constructeur superficiel crée un arbre non vide dont les adresse des fils sont données en paramètre. Il est appelé ainsi car les fils de l’arbre créé ne sont pas des copies des arbres désignés par les paramètre, avec les risques que cela comporte en termes d’accident mémoire et de fuite mémoire. (Plusieurs arbres peuvent avoir des sous-arbres communs.)
Les affichages ajoutés vont permettre de comptabiliser le nombre d’instances créées par chacun des constructeurs dans un but pédagogique et de mise au point.
Question 1.
Donnez les lignes de code permettant de construire l’arbre donné en exemple ci-dessus, situé complètement dans le tas.
Arbre* a = new Arbre(9, new Arbre(), new Arbre());
Arbre* r = new Arbre(5, new Arbre(), a);
L’arbre complet construit est pointé par la variable r.
On ajoute une méthode permettant de déterminer si l’arbre courant est vide :
bool Arbre::vide() const
{
return gauche == nullptr;
}
Le test est réalisé avec l’attribut gauche, sachant que si l’arbre est vide, alors les deux attributs gauche et droit contiennent la valeur nullptr, et que dans le cas contraire, aucun des deux attributs ne contient cette valeur.
Question 2
Définissez le destructeur de la classe Arbre.
Arbre::~Arbre()
{
if(!vide())
{
delete gauche;
delete droit;
}
cout << "[X]";
}
Un affichage a été ajouté pour permettre de visualiser les destructions à des fins pédagogiques et de mise au point.
Question 3
Définissez la méthode…
void Arbre::affiche();
…qui affiche l’arbre courant dans le format illustré par l’exemple suivant :
5(.,9(.,.))
Les points . représentent des arbres vides.
void Arbre::affiche() const
{
if(vide())
{
cout << ".";
}
else
{
cout << val << "(";
gauche->affiche();
cout << ",";
droit->affiche();
cout << ")";
}
}
Question 4
Reprenez la solution de la question 1, qui crée un arbre dans le tas, et complétez là en ajoutant les lignes de code permettant d’afficher l’arbre créé, puis de libérer la mémoire qu’il occupe.
Arbre* a = new Arbre(9, new Arbre(), new Arbre());
Arbre* r = new Arbre(5, new Arbre(), a);
cout << endl;
r->affiche();
cout << endl;
delete r;
Il ne faut surtout pas ajouter la ligne delete a, car l’arbre pointé par a est le fils droit de l’arbre pointé par r et sera détruit par delete r.
Question 5
Le constructeur par défaut affiche [D] lors de son exécution. Le constructeur superficiel affiche [S], et le destructeur affiche [X].
Donnez l’affichage exact produit par l’exécution de la solution de la question 4.
[D][D][S][D][S]
5(.,9(.,.))
[X][X][X][X][X]
Les deux premiers [D] correspondent aux deux new Arbre() de la première ligne. Le [S] suivant correspond à l’appel du constructeur superficiel de la première ligne. Le [D] et le [S] suivants sont affichés par l’appel du constructeur par défaut et du constructeur superficiel de la deuxième ligne.
Tout ces appels ont créé au total 5 instance de Arbre dans le tas. Chacune d’elles est détruite lors de l’exécution du destructeur de l’arbre pointé par r. Il y a donc 5 affichages de [X].
Exercice d’entrainement H.ent1.3
On reprend la classe Arbre de l’exercice précédent avec ses constructeurs, destructeurs et méthodes apparaissant dans la déclaration suivante, et qui sont supposés être correctement implémentés.
class Arbre
{
private:
int val;
Arbre* gauche;
Arbre* droit;
public:
Arbre();
Arbre(int val, Arbre* g, Arbre* d);
Arbre(int val, const Arbre& g, const Arbre& d);
~Arbre();
bool vide() const;
void affiche() const;
};
Un nouveau constructeur, appelé constructeur en profondeur, apparait. Voici sa définition :
Arbre::Arbre(int val, const Arbre& g, const Arbre& d)
{
cout << "[P]";
this->val = val;
gauche = new Arbre(g);
droit = new Arbre(d);
}
Ce constructeur fait appel aux constructeur en copie pour créer les fils gauche et droit de l’arbre en cours de construction à partir de copies des arbres dont les références sont passées en paramètres.
Lors de son exécution, ce constructeur affiche [P] dans un but pédagogique et de mise au point. Pour mémoire, le constructeur superficiel affiche [S], le constructeur par défaut affiche [D] et le destrcuteur affiche [X].
Question 1
Définissez le constructeur en copie de la classe Arbre. Ce constructeur doit permettre de créer un nouvel arbre identique à un arbre existant. La copie et l’original doivent être complètement indépendants en mémoire. L’exécution de ce constructeur doit afficher [C].
Arbre::Arbre(const Arbre& m)
{
// À compléter
}
Arbre::Arbre(const Arbre& m)
{
cout << "[C]";
val = m.val;
if(vide())
{
gauche = nullptr; droit = nullptr;
}
else
{
// À compléter
}
}
Dans tous les cas, l’attribut val du modèle est recopié dans l’attribut val de l’instance créée. Si le modèle est un arbre vide, alors l’instance créée représente aussi un arbre vide.
Il reste à traiter la cas où le modèle n’est pas vide, donc a un fils gauche et un fils droit. Les attributs gauche et droit de l’instance créée doivent pointer sur des copies des fils du modèle.
Arbre::Arbre(const Arbre& m)
{
cout << "[C]";
val = m.val;
if(m.vide())
{
gauche = nullptr; droit = nullptr;
}
else
{
gauche = new Arbre(*(m.gauche));
droit = new Arbre(*(m.droit));
}
}
Question 2
On exécute la fonction suivante…
void test_Arbre1()
{
Arbre a(12, Arbre(), Arbre());
cout << endl;
a.affiche();
cout << endl;
}
…et on obtient l’affichage :
[D][D][P][C][C][X][X]
12(.,.)
[X][X][X]
Ce qui signifie que :
- le constructeur par défaut est invoqué 2 fois,
- le constructeur en profondeur est invoqué 1 fois,
- le constructeur en copie est invoqué 2 fois,
- et que le destructeur est invoqué 5 fois.
Détaillez toutes les étapes et tentez de comprendre et d’expliquer pourquoi il y a eu 5 appels de constructeur pour créer un arbre constitué de seulement 3 instances de la classe Arbre.
Tous les appels de constructeur sont réalisés par la première ligne. On peut identifier trois étapes de l’exécution de la première ligne.

- À l’étape 1, un arbre vide anonyme est créé dans la pile. Cet arbre n’est pas stocké dans une variable et sera détruit automatiquement.
- À l’étape 2, un autre arbre anonyme est créé dans la pile.
Ceci nous donne l’explication des deux premiers [D], c’est à dire des deux invocations du constructeur par défaut.
Mais pourquoi y a t’il à l’étape 3 une invocation du constructeur en profondeur et deux invocations du constructeur en copie ? À vous de continuer l’enquête. Regardez le code du constructeur en profondeur.
Comme les étapes 1 et 2 ne produisent pas des pointeurs mais de instances de la classe Arbre, c’est le constructeur en profondeur qui est invoqué à l’étape 3 pour initialiser la variable a.
En examinant le code de ce constructeur, on constate qu’il crée deux instances de Liste en appelant avec new le constructeur en copie de la classe Liste. C’est la raison pour laquelle on a deux fois l’affichage [C].
À quoi correspondent les deux premiers [X] affichés ? Et les trois derniers ?
Les deux premiers [X] correspondent à le destruction automatique des deux instances anonymes de la classe Arbre créées aux étapes 1 et 2.
Les trois derniers [X] correspondent à la destruction automatique de l’arbre désigné par la variable a, incluant les deux arbres vides de sa ramification.
Question 3
Donnez la définition de la méthode…
Arbre& Arbre::operator=(const Arbre& m);
…qui implémente l’opérateur = de manière à ce que si les variables a et b désignent deux arbres existants, appelés respectivement l’arbre cible et l’arbre source, l’assignation a = b ait les effets suivants :
- Destruction de toute la ramification de l’arbre désigné par
a. - Remplacement de cet arbre par une copie en profondeur de l’arbre désigné par
b.
Arbre& Arbre::operator=(const Arbre& m)
{
val = m.val; // Ligne A
if(!vide())
{
delete gauche; delete droit; // ligne B
}
// À compléter
return *this;
}
La ligne A copie la chaine associée à la racine de l’arbre source dans l’instance courante qui représente la racine de l’arbre cible.
La ligne B détruit la ramification de l’arbre cible, si applicable, c’est à dire si l’arbre cible n’est pas une feuille.
La partie à compléter doit réaliser la copie en profondeur des fils gauche et droit de l’arbre source dans l’arbre cible. Il faut utiliser le constructeur en copie de la classe Arbre.
Arbre& Arbre::operator=(const Arbre& m)
{
val = m.val;
if(!vide())
{
delete gauche; delete droit;
}
if(m.vide())
{
gauche = nullptr; droit = nullptr;
}
else
{
gauche = new Arbre(*(m.gauche));
droit = new Arbre(*(m.droit));
}
return *this;
}
Question 4
On considère le fonction suivante :
void testArbre(void)
{
Arbre f; // Ligne A
Arbre a(12, f, f); // Ligne B
Arbre b(9, f, f); // Ligne C
Arbre c(3, a, b); // Ligne D
c.affiche(); cout << endl;
a = c; // Ligne E
a.affiche(); cout << endl;
}
Combien de fois le constructeur par défaut est-il appelé, et (si applicable) lors de l’exécution de quelles lignes ?
Une seule fois, lors de l’exécution de la ligne A.
Combien de fois le constructeur en copie est il appelé au cours de l’exécution de la ligne B ?
Deux fois, par le constructeur en profondeur qui crée deux copies de l’arbre désigné par f (les fils gauche et droit de l’arbre désigné par a).
On adopte la représentation simplifiée suivante pour représenter l’arbre désigné par a à l’issue de l’exécution de la ligne B. Le triangle noir en haut à gauche d’une instance signifie qu’elle est située dans la pile.

Dessinez la situation complète en mémoire à l’issue de l’exécution des lignes A, B, C et D.

Combien de fois le constructeur en copie est il appelé au cours de l’exécution de la ligne D ?
Six fois. Trois fois pour créer le fils gauche de l’arbre construit dans c, et trois fois pour créer son fils droit. On le voit facilement sur le dessin en comptant les instances de la ramification de l’arbre désigné par c.
Quels sont les constructeurs appelés lors de l’exécution de la ligne E, et combien de fois ? Le destructeur est-il appelé lors de l’exécution de cette ligne, et si oui combien de fois ?
Les destructeur est appelé deux fois pour détruire la ramification de l’arbre désigné par a. Les constructeur en copie est appelé 6 fois pour remplacer les fils gauche et droit de l’arbre désigné par a par des copies des fils gauche et droit de l’arbre désigné par c.