Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/07112.jsonl.gz/860

Série 3 : structures de données, récursion et algorithmes
2 mai 2001
Introduction
Après avoir introduit les comptes avec découvert et les comptes
avec journal nous allons améliorer encore notre programme de gestion
de comptes en banque.
Une faiblesse du programme de la semaine dernière était que le nombre de
comptes pouvant être ouvert dans la banque était limité par la taille
du tableau dans lequel on avait choisi de les stocker. Le
problème est qu'un tableau n'est pas extensible.
En stockant les comptes dans une liste telle que celles utilisées avec
QC++, plutôt que dans un tableau, on pourrait ajouter autant de
comptes que l'on désire. C'est ce que nous allons faire dans cette série.
Cela nous donnera également l'occasion d'utiliser la récursion pour
écrire de manière élégante la fonction de suppression d'un élément de
la liste.
1 Point de départ
A faire [2 min]:
Avant toute chose il faut recopier le répertoire de la série sur votre
compte en tapant cp -R /home/cremet/serie3 . (attention, le
point fait partie de la commande), et vous placer dans ce répertoire
en tapant cd serie3. Vous travaillerez ensuite directement
sur les fichiers présents dans ce répertoire, mais vous pouvez à tout
moment consulter leur version original ici.
2 Listes et itérateurs
Une liste est une structure de données standard pour manipuler des
collections d'objets. Tout ce qu'on peut faire avec une liste, c'est :
lui ajouter un élément, supprimer un de ses éléments, obtenir un
itérateur sur cette liste.
Un itérateur sur une liste permet de parcourir cette liste de façon
élégante. Il possède une méthode suivant() qui a le comportement
suivant : au premier appel, elle renvoie le premier élément de la
liste, au deuxième le second, etc. Pour tester si on arrive en bout de
liste il possède aussi une méthode aUnSuivant() qui renvoie false
s'il ne reste plus d'élément à considérer.
Dans le fichier ListeCompte.H se trouvent
l'interfaces des classes ListeCompte et IterateurCompte qui
représentent ces deux structures de données quand les éléments sont
des comptes.
2.1 Utilisation des listes et itérateurs
L'intérêt des structures de données abtraites, comme les listes et les
itérateurs, est que l'utilisateur n'a pas besoin de savoir comment
elles sont faites, mais seulement comment les utiliser.
Le concept de classe, avec ses notions de membres privés et publics,
permet de bien séparer ces deux points de vue.
En pratique voici les seules choses qu'on peut faire avec une liste ou
un itérateur :
Voici un exemple d'utilisation de cette structure de données :
exempleAvecListe.C.
A faire [10 min] :
Se familiariser avec l'exemple.
2.2 Implantation des listes et des itérateurs
L'implantation d'une liste est faite dans le fichier
ListeCompte.C, exclusivement au moyen de
pointeurs, et reprend grosso modo les idées des exercices de QC++ sur
les pointeurs. Nous ne vous demanderons donc pas de tout réécrire.
La seule méthode que vous devrez écrire est la méthode
supprimer(..) de la classe ListeCompte. L'idée est de vous faire
utiliser la récursion (une fonction qui s'appelle elle-même) pour
l'écrire de manière élégante.
Comme souvent quand on veut utiliser la récursion, on doit utiliser
une fonction auxiliaire. La
fonction auxiliaire s'appelera ici supprimerEnPartantDe, voici :
Pour supprimer un compte c de la liste, il suffit alors d'appeler la
méthode ci-dessus, en partant du premier élément.
-
sa signature : void supprimerEnPartantDe(Compte*
c,ConteneurCompte* &courant);
- sa spécification : supprimer le compte c du morceau de la
liste situé à partir de courant
- son algorithme : si le morceau de liste qui commence avec
courant est vide, ne rien faire.
Sinon ce morceau contient un élément e suivi d'un autre morceau de
liste qui commence avec courant->suivant.
Si l'élément e contient le compte à supprimer, supprimer e, sinon
appeler à nouveau la méthode supprimerEnPartantDe avec toujours le
même compte c, mais en partant cette fois de courant->suivant.
A faire [environ 10 lignes, 30 min]:
Compléter les méthode
supprimerEnPartantDe et supprimer dans le fichier
ListeCompte.C.
3 Modification de la classe Banque
On aimerait que la classe Banque puisse gérer un nombre illimité de
comptes. Pour cela, on va modifier la classe pour qu'elle utilise une
liste plutôt qu'un tableau de comptes.
On aimerait également pouvoir supprimer un compte donné et lister
l'ensemble des comptes gérés par la banque. Pour cela on va rajouter
deux nouvelles méthodes à la classe Banque et modifier sa méthode
demarrer afin qu'elle offre ces deux nouvelles possibilités à
l'utilisateur.
A faire [environ 25 lignes, 60 min]:
Supprimer les champs capacite et nombre_comptes de la classe
Banque et modifier le type du champ comptes en remplaçant le
tableau de comptes (Compte**) par une liste de comptes
(ListeCompte*). Pour que cela compile correctement, il faut
également rajouter un #include "ListeCompte.H" au fichier
(Banque.H),
Modifier la déclaration du constructeur de la classe Banque. Il n'y
a maintenant plus besoin d'indiquer de capacité. Le constructeur ne
prend donc plus aucun paramètre. Cette modification implique qu'il
faut aussi modifier l'appel à ce constructeur dans le fichier
main.C.
Modifier l'implantation du constructeur et du destructeur de la classe
Banque afin qu'ils créent et détruisent la liste de comptes.
Modifier l'implantation de la méthode ajouterCompte. Ici, il suffit
de faire un appel à la méthode ajouter de la classe ListeCompte.
Modifier l'implantation de la méthode rechercherCompte. Ici, il faut
remplacer la boucle for qui travaille sur le tableau de comptes par
une boucle while qui travaille sur un itérateur sur la liste de
comptes.
Ajouter à la classe Banque et implanter les deux nouvelles méthodes
suivantes:
La méthode supprimerCompte doit d'abord rechercher le compte à
supprimer en utilisant la méthode rechercherCompte puis, s'il
existe, le supprimer avec la méthode supprimer de la classe
ListeCompte. La méthode listerComptes utilise simplement un
itérateur sur la liste de comptes afin d'imprimer le nom de chacun des
comptes.
-
void supprimerCompte(char* login);
- void listerComptes();
Modifier l'implantation de la méthode demarrer afin que
l'utilisateur puisse supprimer un compte et lister l'ensemble des
comptes gérés par la banque. Ici, il faut bien évidemment utiliser les
deux nouvelles méthodes qui viennent d'être rajoutées à la classe.
4 Compilation séparée
Voici les commandes à taper pour compiler ce micro-projet :
g++ -c Compte.C
g++ -c CompteAvecDecouvert.C
g++ -c CompteAvecJournal.C
g++ -c ListeCompte.C
g++ -c Banque.C
g++ -c main.C
g++ Compte.o CompteAvecDecouvert.o CompteAvecJournal.o ListeCompte.o Banque.o main.o -o banque
Explications :
L'idée est de compiler le programme en plusieurs morceaux.
On commence par compiler chaque fichier .C séparément en utilisant
l'option -c (6 permières commandes). A chaque fois est généré
un fichier de code machine avec l'extension .o.
Puis on recolle tous les morceaux ensemble avec la dernière ligne pour
obtenir l'exécutable banque.
Cette manière de compiler en plusieurs morceaux permet de ne pas avoir
toutes les erreurs d'un coup. De plus une fois qu'un morceau est
compilé on n'a pas à le recompiler, ce qui fait gagner du temps pour les
gros projets.
A faire [10 min]:
Compiler le programme (vous pouvez faire un
copier-coller avec le bouton gauche de la souris pour sélectionner,
suivi du bouton du milieu pour coller)
This document was translated from LATEX by
HEVEA.