| Algo - C++ | Année 2004/2005 |
Le texte ci-dessous fait partie d'un corrigé du mini projet 4. Il présente la conception des classes utilisées (Abonne et Annuaire) et leur déclaration en C++. Quelques remarques sur la programmation utilisant ces classes, et les essais effectués figurent ensuite.
Les attributs des classes Abonne et Annuaire définis
précisément par l'énoncé sont utilisés. Nous ajoutons un attribut de la
classe Annuaire pour indiquer si le tableau d'abonnés est trié sur le
champ nom; cela permet d'effectuer la recherche adéquate (séquentielle
ou dichotomique).
Pour les méthodes de ces classes, l'énoncé est plus vague, laissant de
la marge à la réflexion.
De sa lecture attentive se dégage la nécessité de lire ou
d'écrire les informations sur un abonné; il faut aussi pouvoir
rechercher un abonné dans un annuaire. Observons enfin que
pour la recherche séquentielle on utilise une relation d'égalité
entre attributs ou entre abonnés, alors que pour la recherche
dichotomique (et le tri), c'est une relation d'ordre entre
abonnés qui est utilisée.
♦ classe Abonne ♦
De façon standard nous avons des constructeurs, deux méthodes d'écriture
d'un abonné (une n'est utilisée que pour la mise au point), une méthode
de lecture. Nous avons une méthode fournissant le nom d'un abonné
et une méthode permettant de comparer deux abonnés(c'est à dire tous les
attributs), afin de ne pas avoir de doublons dans un annuaire.
Remarque il n'y a pas besoin, pour les traitements effectués
ici, d'autres fonctions d'accès.
♦ classe Annuaire ♦
En plus des attributs département, tableau et nombre d'abonnés, on
ajoute un attribut précisant
si l'annuaire est trié sur le champ nom.
Outre des constructeurs d'annuaire, nous avons la méthode
d'ajout d'un abonné, une méthode de tri et des méthodes de
recherche d'un abonné d'un abonné sur le nom de l'abonné:
→
deux méthodes, notées rechercheS effectuant une recherche séquentielle: la première pour
détecter la présence d'un abonné (le premier rencontré) et la deuxième
qui fournira un tableau de tous les abonnés de l'annuaire ayant
un nom donné;
→
une méthode notée rechercheD de recherche dichotomique classique, utilisable uniquement
si les abonnés sont ordonnés sur le nom, qui fournit un (seul) indice;
→
et deux méthodes, qui utiliseront, suivant l'état trié ou non
du tableau, la recherche la plus adaptée (la plus rapide en fait).
Si on veut avoir tous les abonnés d'un annuaire ayant un nom donné,
l'annuaire étant trié, un appel à rechercheD fournira (si le nom
est présent) le plus petit indice dans le tableau d'abonnés, et un
parcours séquentiel à partir de cet indice permet d'avoir les autres abonnés
ayant le même nom.
|
Comme on pourra utiliser des fichiers il est nécessaire d'avoir
une forme externe pour un abonné et pour un annuaire, avec des
possibilités de lecture et d'écriture.
|
Toto l'Accro
18 rue sans soucis
91400 Orsay
0123456789
| ||
|
| |||
|
On ajoute cependant, des informations propres à l'annuaire, à savoir le
numéro de département, le nombre d'abonnés et une information précisant
si l'annuaire est trié sur le champ nom.
Les méthodes d'écriture ou de lecture d'un Annuaire n'accèdent à aucun champ de la classe Abonné; elles utilisent plutôt les méthodes d'écriture ou de lecture d'un abonné.
|
-annuaire- département nb.abonnés trié
91 7 0
Toto
0 Le grand Pin
91400 Orsay
0123456789
Gaston Lagaffe
1 rue des petites perles
91234 Courcouronnes
06 0606 0606
| ||
|
|
Pour cela on fait précéder la forme externe d'un abonné
par le numéro du département dans lequel il réside, comme
ci-contre.
| 91 Gaston Lagaffe
1 rue des petites perles
91234 Courcouronnes
06 0606 0606
| |
♦ En dehors de toute classe ♦
nous écrirons les fonctions demandées par
l'énoncé et celles qui manipulent des fichiers, en respectant les
principes suivants:
♦ Recherches multicritères ♦
Comme le permet l'énoncé la recherche d'un abonné sur plusieurs critères,
nom et ville par exemple, est une extension. Nous envisagerons dans une
deuxième version cette recherche.
Pour une utilisation plus en phase avec la réalité, nous programmerons
dans cette nouvelle version, une relation
d'égalité qui permette d'affirmer que, par exemple, 'DUPONT' et
'Dupont' sont le même nom.
Deux conventions d'écriture des identificateurs sont observées.
Tout d'abord les noms de constantes sont en majuscules;
exemple: MAXABONNES
De plus, les noms privés commencent par le caractère soulignement (_);
exemple: _nbAbonnes
Pour utiliser la valeur d'un attribut, en dehors de sa classe, on définit
des fonctions ayant presque le même nom (en enlevant le caractère _).
string nbAbonnes(); ←
pour récupérer la valeur du champ
void d_nbAbonnes(int n); ←
pour définir une nouvelle valeur du nombre d'abonnés
Il est IMPORTANT que la même écriture soit utilisée
pour ces différents usages d'un attribut afin d'éviter les erreurs
d'orthographe, ou des efforts de mémorisation, qui font perdre du temps
inutilement.
En fait avec une bonne conception ces fonctions ne sont pas utilisées.
En particulier il faut limiter au maximum la modification de
champs privés d'une classe par de telles fonctions.
Pour les traitements de ce TP on n'a besoin que de connaître
l'attribut _nom pour des comparaisons.
|
Les méthodes ecr et lec correspondent respectivement
à l'écriture d'un abonné dans un flot
et à la lecture depuis un flot, de façon symétrique; le format
d'écriture est rappelé ci contre: une information par ligne, avec un
retrait de deux espaces pour l'adresse (sur un seule ligne), la
ville et le téléphone.
Actuellement aucune vérification n'est effectuée à la lecture quant au respect de ce format. |
Toto l'Accro
18 rue sans soucis
91400 Orsay
0123456789
|
La méthode aff ne sert qu'à la mise au point; elle affiche précisément les chaînes mémorisées (en particulier la présence d'espaces) car chaque valeur de chaîne est encadrée par des apostrophes.
On définit un abonné spécial appelé VIDE dont l'utilisation dans les algorithmes de recherche d'un abonné (classe Annuaire) est pratique.
// abonne.h #include#include using namespace std; class Abonne { public: Abonne(string nom="", string adr="", string vil="", string tel="") : _nom(nom), _adresse(adr), _ville(vil), _telephone(tel){;} // Pour initialiser un tableau d'abonnés Abonne(const char nom[]) : _nom(nom), _adresse(""), _ville(""), _telephone(""){;} // Fonctions de récupération d'un champ string nom() const { return(_nom);} // Pour test identité bool operator==(const Abonne &a) const; // Ecriture dans un flot void ecr(ostream & flot) const; void lec(istream & flot); // Affichage pour mise au point void aff() const; private: string _nom,_adresse,_ville,_telephone; }; // Opérateurs d'écriture et de lecture d'un abonné ostream & operator<< (ostream &flot, const Abonne & a); istream & operator>> (istream &flot, Abonne & a); // Valeur spéciale utilisée dans la classe Annuaire const Abonne VIDE("ABONNE_ABSENT");
La classe est déclarée ci-dessous. On peut remarquer le constructeur
privé qui, à partir d'un tableau d'abonnés, définit un annuaire; ce
constructeur est utilisé lors de la mise au point.
Remarquer la ligne
'friend void miseAuPointAnnuaire();' qui permet à cette
fonction l'accès à tous les attributs de la classe. Cela évite d'avoir
à modifier une déclaration entre la phase de mise au point et celle de
l'exploitation.
Nous avons l'attribut booléen _estTrie qui reflète l'état du tableau d'abonnés. Il est défini à FAUX dans les constructeurs; il bascule à VRAI dans la méthode tri et à FAUX dans la méthode ajout.
Les méthodes de recherches séquentielles ou dichotomique sont privées; noua avons aussi des méthodes publiques qui n'utilisent la recherche dichotomique, que si le tableau d'abonnés est trié sur le nom. Ainsi un utilisateur de la classe ne pourra pas utiliser la recherche dichotomique dans un cas où elle est invalide.
On peut remarquer que l'accès aux champs privés, nécessaires aux opérateurs '<<' et '>>' est traité d'une autre façon que dans la classe Abonne. Ici la classe autorise ces fonctions externes à la classe (voir déclarations friend) à accéder à tous ses champs.
Remarquer l'attribut "INDICATEUR" qui marque le début d'un annuaire dans un flot: comme c'est un attribut unique pour tous les annuaires il est déclaré static et sa valeur est attribuée en dehors de la classe.
// annuaire.h #ifndef ANNUAIRE_H #define ANNUAIRE_H #include#include using namespace std; const int MAXABONNES = 7; class Annuaire { public: static const char INDICATEUR[]; Annuaire(int dep=91) : _nbAbonnes(0), _departement(dep), _estTrie(0) {} int nbAbonnes() { return _nbAbonnes; } int departement() { return _departement; } void d_departement(int dep); // définir le département bool estTrie() { return _estTrie; } // Ajoute un abonné (peut modifier estTrie) // Renvoie l'indice où il est placé dans le tableau, ou: // MAXABONNES si l'annuaire est déjà plein // -1 si l'abonné est déjà présent int ajout(const Abonne &a); // Recherche d'un abonné sur le nom (première occurrence) // Renvoie l'abonné s'il existe ou VIDE sinon Abonne recherche(const string &nom) const; // Recherche des abonnés sur le nom (toutes les occurrences) // Remplit le tableau t avec les abonnés trouvés // Renvoie le nombre d'abonnés trouvés int recherche(const string &nom, Abonne t[]) const; // Tri le tableau d'abonnés // Utilise une définition de : Abonne < Abonne void tri(); private: Abonne _abonnes[MAXABONNES]; int _nbAbonnes; int _departement; bool _estTrie; // VRAI ou 1 si tableau trié; FAUX ou 0 sinon // Constructeur utilisé pour la mise au point Annuaire(Abonne ta[], int na, int dep=91, int trie=0); // Recherche un abonné (pour détecter les doublons) // Renvoie l'indice dans _abonnes s'il existe ou -1 sinon int recherche(const Abonne &a) const; // Recherche séquentielle d'un abonné sur le nom (première occurrence) // Renvoie l'abonné s'il existe ou VIDE sinon Abonne rechercheS(const string &nom) const; // Recherche séquenteille des abonnés sur le nom (toutes les occurrences) // Remplit le tableau t avec les abonnés trouvés // Renvoie le nombre d'abonnés trouvés int rechercheS(const string &nom, Abonne t[]) const; // Recherche dichotomique d'un abonné sur le nom (première occurrence) // Renvoie l'indice dans _abonnes s'il existe ou -1 sinon // CONDITION: _abonnes est trié sur le nom d'abonné int rechercheD(const string &nom) const; friend void miseAuPointAnnuaire(); friend ostream & operator<< (ostream &flot, const Annuaire & a); friend istream & operator>> (istream &flot, Annuaire & a); }; const char Annuaire::INDICATEUR[] = "-annuaire- num.département nb.abonnés estTrié"; // Opérateurs d'écriture et de lecture d'un annuaire ostream & operator<< (ostream &flot, const Annuaire & a); istream & operator>> (istream &flot, Annuaire & a); #endif
Nous utilisons un tableau d'annuaires pour travailler avec les numéros de département de 1 à 95; la constante symbolique MAXDEPARTEMENT est utilisée. Les abonnés du département de numéro i sont mémorisés dans l'annuaire d'indice i de ce tableau.
Figurent ci-dessous les déclarations de initAnnuaires, des méthodes de recherche et d'une méthode de sauvegarde sur fichier.
const int MAXDEPARTEMENT = 95; Annuaire tabAnn[1+MAXDEPARTEMENT]; // Remplit un tableau d'annuaires à partir d'un fichier contenant des // abonnés avec leur département // Aucune vérification n'est effectuée // Paramètres: // + (R) ta est un tableau d'annuaire; ta[i] est l'annuaire du // département i; si ta est de dimension 96, il pourra contenir // les annuaires des départements 1, 2 .. 95 (voir maxDep) // + (D) maxDep est le numéro de département le plus grand pouvant être // enregistré dans ta // + (D) nomFic est le nom du fichier à parcourir // Renvoie le nombre d'abonnés lus ou // -1 si fichier non trouvé int initAnnuaires( Annuaire ta[], int maxDep, string nomFic); // Recherche d'un abonné sur le département et le nom (une occurrence) // Renvoie l'abonné s'il existe ou VIDE sinon Abonne recherche(Annuaire ta[], int maxDep, int dep, string nom); // Recherche des abonnés sur département et nom (toutes les occurrences) // Remplit le tableau t avec les abonnés trouvés // si t est de taille MAXABONNES aucun débordement n'a lieu // Renvoie le nombre d'abonnés trouvés int recherche(Annuaire ta[], int maxDep, int dep, string nom, Abonne t[]); // Sauvegarde du tableau ta, de na abonnés, du département dep, dans // le fichier de nom nomFic. // Renvoie: -1 si le fichier ne peut pas être créé // le nombre d'abonnés écrits sur fichier sinon int surFichier(Abonne ta[], int na, string nomFic, int dep=-1);
Voici la liste des fichiers concernés par la programmation:
♦ abonne.h
♦ abonne.cpp
♦ annuaire.h
♦ annuaire.cpp
♦ desAnnuaires.h
♦ desAnnuaires.cpp
♦ dependancesPAbonne: dépendances
♦ annuairesInit.txt : données d'initialisation tableau d'annuaires
On ne présente dans ce paragraphe qu'une partie de la programmation, pour illustrer l'utilisation de quelques méthodes des classes Abonne et Annuaire. Sux extraits suivent.
♦ 1.
Voici l'ajout d'un abonné, méthode de la classe Annuaire; cet ajout
n'est pas systématique: un abonné qui est déjà présent n'est pas ajouté;
enfin il n'y a pas d'ajout si l'annuaire est plein.
Ces éventualités sont communiquées au programme appelant.
// Ajoute un abonné
// Renvoie: l'indice où il est placé dans le tableau
// MAXABONNES si l'annuaire est déjà plein
// -1 si l'abonné est déjà présent
int Annuaire::ajout(const Abonne &a) {
if(_nbAbonnes==MAXABONNES) return MAXABONNES;
int ind = recherche(a);
// Pas d'ajout si l'abonné y est déjà
if(ind != -1) return -1;
// Ajout effectif
_abonnes[_nbAbonnes]=a;
_nbAbonnes++;
return _nbAbonnes-1;
}
♦ 2.
Et voici l'initialisation d'un annuaire à partir d'un fichier;
cette méthode utilise la lecture d'un Abonné depuis un flux
(opérateur>>) puis la méthode, de la classe Annuaire permettant
d'ajouter un abonné dans un annuaire. On réalise qu'il n'y a aucune
utilisation explicite des attributs d'un abonné.
// Remplit un tableau d'annuaires à partir d'un fichier contenant des
// abonnés avec leur département, d'après le format ci-dessous, où
// chaque abonné est précédé par le numéro de son département et
// un espace; exemple avec 1 abonné de l'Essonne et 1 de la Seine:
// 91 Toto
// 0 Le grand Pin
// 91400 Orsay
// 0123456789
// 75 Gaston Lagaffe
// 1 rue des petites perles
// Agathe
// 3110
// Aucune vérification n'est effectuée
// Paramètres:
// + (R) ta est un tableau d'annuaire; ta[i] est l'annuaire du
// département i; si ta est de dimension 96, il pourra contenir
// les annuaires des départements 1, 2 .. 95 (voir maxDep)
// + (D) maxDep est le numéro de département le plus grand pouvant être
// enregistré dans ta
// + (D) nomFic est le nom du fichier à parcourir, fermé à la fin
// Renvoie: le nombre d'abonnés lus ou
// -1 si fichier non trouvé
int initAnnuaires( Annuaire ta[], int maxDep, string nomFic) {
ifstream flot(nomFic.c_str());
if(! flot) return -1;
int dep, na=0; char c; Abonne a;
flot>>dep;
while(! flot.eof()) {
na++;
flot.get(c); flot>>a;
// cout<<na<<" "<<dep <<a;
if(dep>=1 && dep<=maxDep) {
ta[dep].d_departement(dep);
ta[dep].ajout(a);
}
flot>>dep;
}
flot.close();
return na;
}
♦ 3.
Nous trouvons ci-dessous la programmation, très courte, pour
trier un tableau d'Abonne, après avoir défini l'opérateur
< entre deux Abonne. Il faut aussi ajouter la déclaration de
la fonction 'sort' par l'inclusion du fichier <algorithm>
// Comparaison de deux abonnés
bool operator<(const Abonne &a1, const Abonne &a2) {
return a1.nom() < a2.nom();
}
// Tri le tableau _abonnes si nécessaire et met à jour _estTrie
// Utilise une définition de : Abonne < Abonne
#include <algorithm>
void Annuaire::tri() {
if(! _estTrie) sort(_abonnes,_abonnes+_nbAbonnes);
_estTrie=1;
}
♦ 4.
Nous ajoutons la fonction de recherche d'un abonné dans un tableau
d'annuaires, à partir du numéro de département et du nom de l'abonné.
La programmation est courte car on fait appel à une méthode de la classe
Annuaire. On constate à nouveau que les attributs d'un
Abonne n'interviennent pas ici.
// Recherche d'un abonné sur le département et le nom (une occurrence)
// Renvoie l'abonné s'il existe ou VIDE sinon
Abonne recherche(Annuaire ta[], int maxDep, int dep, string nom) {
if(dep<1 || dep>maxDep) return VIDE;
else return ta[dep].recherche(nom);
}
♦ 5. Voici la définition d'un tableau d'abonnés et celle d'un annuaire qui vont servir aux tests de programmation des fonctions d'ajout et de recherche séquentielle.
On recherchera dans ann1 son premier abonné, son dernier abonné, ainsi que l'abonné abs qui est absent.
En donnant à MAXABONNES la valeur 6, on ajoutera à l'annuaire ann3 chacun des éléments du tableau ta, pour vérifier en particulier la détection d'un doublon et l'impossibilités d'ajouter un septième abonné.
Abonne ta[]= {
Abonne("J'ai peur","2 dans le noir","91300 Massy","0123456789")
,Abonne("Toto","0 Le grand Pin","91400 Orsay","0123456789")
,Abonne("Gaston Lagaffe","1 rue des petites perles","Agathe","3110")
,Abonne("Toto","3 rue sans soucis","91400 Orsay","0123456789")
,Abonne("Titi","4 la cage","91400 Orsay","0123456789")
,Abonne("Toto","5 a la gare","91400 Orsay","0123456789")
,Abonne("Toto","5 a la gare","91400 Orsay","0123456789")
,Abonne("Jojo La Terreur","ici","91400 Orsay","0123456789")
};
const int na = sizeof(ta)/sizeof(ta[0]);
Annuaire ann1(ta,na), ann2(ta,na-1);
Abonne abs("Zorro");
Annuaire ann3;
♦ 6.
Voici enfin les essais effectués pour tester la fonction de recherche
du premier abonné de nom donné, dans un département donné.
Pour chacun des 6 essais, l'objectif de l'essai est en commentaire;
puis on programme ses conditions, les affichages du résultat
attendu et
du résultat obtenu par le sous programme testé.
// Initialisation d'un tableau d'annuaires (fichier annuairesInit.txt)
Annuaire tAnn[MAXDEPARTEMENT+1]; int nAnn=MAXDEPARTEMENT;
string nf("annuairesInit.txt");
initAnnuaires(tAnn,nAnn,"annuairesInit.txt");
// Recherche une seule occurrence d'un nom
int nd; string nomAbo;
cout<<"Recherche département,nom: une seule occurrence"<<endl;
// a. département correct, recherche premier abonné
nd=91; nomAbo="Toto";
cout<<" attendu: présent, dép:"<<nd<<"--> "
<<nomAbo<<": "<<recherche(tAnn,nd,nd,nomAbo);
// b. département correct, recherche dernier abonné
nd=91; nomAbo="Gaston Lagaffe";
cout<<" attendu: présent, dép:"<<nd<<"--> "
<<nomAbo<<": "<<recherche(tAnn,nd,nd,nomAbo);
// c. département correct, abonné absent
nd=88; nomAbo="Gaston Lagaffe";
cout<<" attendu: absent, dép:"<<nd<<"--> "
<<nomAbo<<": "<<recherche(tAnn,nd,nd,nomAbo);
// d. département trop grand
nd=91; nomAbo="Gaston Lagaffe";
cout<<" attendu: absent, dép:"<<nd<<"--> "
<<nomAbo<<": "<<recherche(tAnn,nd-1,nd,nomAbo);
// e. numéro département trop petit
nd=00; nomAbo="J'ai peur";
cout<<" attendu: absent, dép:"<<nd<<"--> "
<<nomAbo<<": "<<recherche(tAnn,nAnn,nd,nomAbo);
// f. premier département, abonné présent
nd=01; nomAbo="J'ai peur";
cout<<" attendu: présent, dép:"<<nd<<"--> "
<<nomAbo<<": "<<recherche(tAnn,nAnn,nd,nomAbo);
//
Les essais effectués pour tester la programmation figurent tous dans le
programme principal. On y trouve les instructions pour tester les méthodes ou
fonctions, ainsi que l'objectif de l'essai effectué. Après test, ces
instructions sont mises en commentaire pour ne pas alourdir l'affichage.
Dans l'ensemble, pour ces essais, on a limité les saisies, car elles sont
fastidieuses à reproduire.
A titre indicatif signalons que le nombre de lignes programmées pour
les essais est du même ordre que le nombre de lignes définissant les
classes et les divers traitements.
A titre d'exemple, les essais effectués pour tester la recherche d'un abonné unique, par son nom, dans un tableau d'annuaires sont indiqués dans le paragraphe précédent 'Programmation', sous paragraphe 6.
Pour tester les algorithmes de recherche dans un tableau, 4 essais au
moins sont effectués:
→
recherche d'un élément, présent dans le tableau
→
recherche du premier élément du tableau
→
recherche du dernier élément du tableau
→
recherche d'un élément absent du tableau.
De façon générale on teste un cas standard et chaque cas limite, comme
par exemple fichier inexistant, tableau saturé lors d'un ajout, et
tableau autorisant un seul ajout ...