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 :

Pour créer une liste de comptes vide on écrit : ListeCompte* liste = new ListeCompte();
Pour ajouter un compte, accessible par le pointeur c, on écrit : liste->ajouter(c);
Pour supprimer un compte, accessible par le pointeur c, on écrit : liste->supprimer(c);
Pour parcourir une liste de comptes on commence par obtenir un itérateur sur cette liste :
IterateurCompte* it = liste->iterateur();
Puis on utilise les deux méthodes aUnSuivant() et suivant() dans un while :
```
 
Compte* c = NULL; 
while (it->aUnSuivant()) {
   c = it->suivant();
   ...
   ...
}
```

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 :

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.

Pour supprimer un compte c de la liste, il suffit alors d'appeler la méthode ci-dessus, en partant du premier élément.

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:

void supprimerCompte(char* login);
void listerComptes();

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.

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 L^AT_EX by H^EV^EA.