[C++] Dictionnaire

Le menu est disponible grâce au bouton droit

Date de première publication : 2013/11/21

Exercice : un dictionnaire

Nous voulons coder un programme permettant de gérer un dictionnaire : une liste de lettres avec la liste de mots commençant par cette lettre. Nous vous proposons le diagramme UML suivant :

Manipulation d'une liste chaînée

Nous voulons fournir une classe ListeMotsTries qui contient des listes de mots (std::string) triés. C'est une simple encapsulation de std::list<std::string>. Les méthodes seront donc très rapides à écrire et on essaiera d'utiliser le plus possible la bibliothèque standard.

• Écrire la déclaration de la classe avec son attribut.
• Ajouter une méthode ajouterMot(const string&) qui ajoute un mot à cette liste. La liste sera triée après chaque ajout.
• Ajouter une méthode getNbMots() qui retourne le nombre de mots de la liste. Vérifier que l'ajout de mots incrémente bien cette valeur.
• Écrire une méthode afficher(ostream & = cout) qui permet d'afficher sur le flux spécifié le contenu de la liste. Vous pouvez :
• Parcourir cette liste avec un itérateur et afficher dans le flux
• Utiliser l'algorithme copy() et ostream_iterator
• Surcharger l'opérateur de redirection <<
• Ajouter une méthode debut() qui retournera un itérateur constant sur le premier élément de la liste. Le type const_iterator sera défini comme un typedef ou un using du type correspondant de la chaîne de caractères et dans la classe ListeMotsTries.
• Ajouter une méthode fin() qui retournera un itérateur constant de fin de liste
• Ajouter une méthode inserer() qui permet d'insérer une liste de mots triés dans une autre liste de mots triés en prenant des itérateurs constants sur la liste à insérer.

Voici un extrait de fichier de tests :

TEST_CASE ( "ListeMT1" ) {
  ListeMotsTries liste;

  REQUIRE( 0 == liste.getNbMots() );
  liste.ajouterMot("inserer");
  REQUIRE( 1 == liste.getNbMots() );
  liste.ajouterMot("effacer");
  REQUIRE( 2 == liste.getNbMots() );
  liste.ajouterMot("ajout");
  REQUIRE( 3 == liste.getNbMots() );


  ListeMotsTries::const_iterator it = liste.debut();

  REQUIRE( *it == "ajout" ); 
  ++it;
  REQUIRE( *it == "effacer" );
  ++it;
  REQUIRE( *it ==  "inserer" );
  ++it;
  REQUIRE( it == liste.fin() );

  liste.enleverMot("effacer");
  REQUIRE( 2 == liste.getNbMots() );
  liste.enleverMot("inserer");
  REQUIRE( 1 == liste.getNbMots() );
  liste.enleverMot("ajout");
  REQUIRE( 0 == liste.getNbMots() );

  REQUIRE( liste.debut() == liste.fin() );
}

TEST_CASE ( "ListeMT2" ) {
  ListeMotsTries liste1, liste2;

  liste1.ajouterMot("essai 1 a");
  liste1.ajouterMot("essai 1 b");
  liste2.inserer(liste1.debut(), liste1.fin());

  ListeMotsTries liste3;
  liste3.ajouterMot("essai 1 b");
  liste3.ajouterMot("essai 2 a");
  liste3.ajouterMot("essai 2 c");
  liste2.inserer(liste3.debut(), liste3.fin());
}

TEST ( TestListeMT, LMT1 ) {
  ListeMotsTries liste;

  EXPECT_EQ( liste.getNbMots(), 0 );
  liste.ajouterMot("inserer");
  EXPECT_EQ( liste.getNbMots(), 1);
  liste.ajouterMot("effacer");
  EXPECT_EQ( liste.getNbMots(), 2 );
  liste.ajouterMot("ajout");
  EXPECT_EQ( liste.getNbMots(), 3 );


  ListeMotsTries::const_iterator it = liste.debut();

  EXPECT_STREQ(it->c_str(), "ajout");
  ++it;
  EXPECT_STREQ(it->c_str(), "effacer");
  ++it;
  EXPECT_STREQ(it->c_str(), "inserer");
  ++it;
  EXPECT_EQ(it, liste.fin());

  liste.enleverMot("effacer");
  EXPECT_EQ(liste.getNbMots(), 2);
  liste.enleverMot("inserer");
  EXPECT_EQ(liste.getNbMots(), 1);
  liste.enleverMot("ajout");
  EXPECT_EQ(liste.getNbMots(), 0);

  EXPECT_EQ(liste.debut(), liste.fin());
}

TEST ( TestListeMT, LMT2 ) {
  ListeMotsTries liste1, liste2;

  liste1.ajouterMot("essai 1 a");
  liste1.ajouterMot("essai 1 b");
  liste2.inserer(liste1.debut(), liste1.fin());

  ListeMotsTries liste3;
  liste3.ajouterMot("essai 1 b");
  liste3.ajouterMot("essai 2 a");
  liste3.ajouterMot("essai 2 c");
  liste2.inserer(liste3.debut(), liste3.fin());
}

Manipulation d'un tableau associatif

La classe Dictionnaire est composée d’une instance de std::map<char,ListeMotsTries>. Le premier champ est la clé, il s’agit de la première lettre d’un mot. La valeur qui lui est associée est une liste de mots (instance de ListeMotsTries) qui stocke par ordre alphabétique tous les mots commençant par la dite lettre.

• Implémentez les méthodes de base telles que ajouterMot ou supprimerMot.
• La méthode rechercherMots() renvoie la liste de tous les mots commençant par le motif qu’on lui passe en paramètre. L’une des méthodes compare de la classe std::string vous aidera à fournir cette fonctionnalité.

Vérifiez à présent le bon fonctionnement de votre dictionnaire :

• Testez la recherche d’un mot qui n’existe pas.
• Vérifiez que vous avez compris la gestion d’une map en proposant les fonctions nécessaires pour utiliser cette surcharge : std::ostream & operator<<( std ::ostream & inO, const Dictionnaire& inD );