Tout document autorisé

Sommaire

Tri par insertion : utilisation de sentinelle

    Dans la fonction Exo_01c() du fichier exo_01.cxx (TP 4 de C++), nous avons montré que la boucle de décalage à droite des éléments du vecteur s'arrête soit lorsqu'est trouvé un élément inférieur ou égal à l'élément à insérer, soit lorsque le premier élément du vecteur est atteint. Dans ce cas, il faut encore vérifier si ce premier élément doit lui-même être décalé.

    Si N désigne le nombre d'éléments du vecteur et si les éléments à insérer se présentent dans un ordre aléatoire, la probabilité d'insérer en tête est de 1/N, et pourtant le test de début de vecteur doit toujours être effectué. Pour supprimer ce test, il faut être sûr que l'autre test sera toujours satisfait, donc que sera toujours trouvé un élément inférieur ou égal à l'élément à insérer. Une telle certitude peut être obtenue en plaçant la nouvelle valeur en première position du vecteur avant de commencer le décalage. Cette position est appelée la sentinelle.

    Un vecteur de N valeurs "utiles" contient donc N+1 éléments, l'élément de rang 0 étant réservé à une utilisation interne du tri.

•     En s'inspirant de la fonction Exo_01c() du fichier exo_01.cxx, écrire la fonction TriInsertSent() qui met en oeuvre l'amélioration décrite ci-dessus.
•     Quelle(s) modification(s) faut-il apporter à la fonction EditVString() ?

Sommaire

Chaînes

• Dans l'espace de noms nsUtil, écrire une fonction StrToUpper1() qui met en majuscules toutes les lettres minuscules d'une chaîne (string) qui lui est passée en paramètre. La fonction n'a pas de valeur de retour. Elle devrait pouvoir être utilisée ainsi :

 

string S1 = "CouCou c'est Moi"; StrToUpper1 (S1); cout << "S1 = " << S1 << endl;

• Donner une seconde version StrToUpper2() de cette fonction pour que, sans nécessiter la création d'une chaîne intermédiaire, elle puisse aussi être utilisée ainsi :

 

string S1 = "CouCou c'est Moi"; string S2 = StrToUpper2 (S1);

• Que pensez-vous de cette utilisation :

 

string S2 = StrToUpper2 ("CouCou c'est Moi");

Sommaire

Flux, chaînes et vecteurs

1. - Ecrire la fonction AfficherBalises() qui affiche à l'écran, sans les stocker, toutes les balises d'un fichier html qui lui est passé en paramètre, à raison d'une balise par ligne. Les <> doivent aussi être affichés. On supposera que :
   • le fichier est valide,
   • les balises ne sont pas à cheval sur des lignes différentes,
   • le fichier est déjà ouvert et positionné en début avant l'entrée de la fonction,
   • la fonction n'a pas à remettre le fichier en état (fermeture, rembobinage éventuel, etc.).
       Pour la lecture dans le fichier, utiliser la fonction get(char & C) membre de la classe istream.

   Corrigé : Balises_01.cxx

   ---

2. - On considèrera ici que le changement de ligne dans un fichier texte est marqué par la suite des deux caractères suivants :
   • "Retour chariot" ("Carriage Return" ou CR), de code ASCII 13, ou de valeur '\r',
   • "Nouvelle ligne" ("Line Feed" ou LF), de code ASCII 10, ou de valeur '\n'.
       Indiquer précisément la ou les modifications à apporter à la fonction AfficherBalises() pour que chaque balise soit affichée sur une ligne, même si elle est sur plusieurs lignes différentes du fichier.

   Corrigé :     Balises_02.cxx

   ---

3. - Ecrire la fonction StockerBalises() qui range dans un vecteur (vector) de chaînes (string) toutes les balises d'un fichier html. Le vecteur et le fichier sont passés en paramètres de la fonction. Une balise peut être sur des lignes différentes dans le fichier, mais doit être stockée dans une seule chaîne. Pour cet exercice, il est impérativement demandé de :
   • lire le fichier ligne par ligne et non caractère par caractère,
   • travailler au maximum avec des chaînes (string) et leurs méthodes.
   Corrigé :     Balises_03.cxx

Sommaire

© D. Mathieu    mathieu@romarin.univ-aix.fr
I.U.T.d'Aix en Provence - Département Informatique