IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Étude détaillée du module String de la libc


précédentsommairesuivant

XIII. c_strrchr

XIII-A. Prototype

 
Sélectionnez
char * c_strrchr (const char * s, int c);

XIII-B. Description et comportement

La fonction c_strrchr permet de rechercher la dernière occurrence du caractère c (par conversion du type entier en caractère) dans la chaine s passée en argument. Le zéro de fin participe à la recherche ainsi, lorsque vous passez le caractère nul comme caractère à rechercher, la fonction renvoie un pointeur sur la fin de la chaine !

Si le caractère passé en argument ne figure pas dans la chaine, la fonction renvoie la valeur NULL.

La chaine de caractère doit posséder un caractère de code nul sinon il y'a risque de dépassement de la zone mémoire passée en argument ce qui a pour effet une possibilité d'un comportement indéterminé de votre programme !

XIII-C. Algorithme

Voici un algorithme possible pour la fonction c_strrchr :

 
Sélectionnez
algorithme
   fonction c_strrchr (s:chaîne, c:entier):chaîne
      debut
         i <- longueur (s)
 
         faire
            si s[i] égal à c
               alors retourne s[i]
            fsi
 
            i <- i - 1
         tant que i supérieur ou égal à 0
 
         retourne NULL
      fin
 
lexique
   s : chaine : Chaine dans laquelle il faut trouver la dernière occurrence du caractère c.
   c : entier : Caractère dont il faut trouver la première occurrence dans la chaine s.
   i : entier : Variable d'incrémentation pour se déplacer dans la chaine s.

Nous avons ici l'algorithme inverse de la fonction c_strchr.

On commence par récupérer la taille de la chaine que nous stockons dans la variable i. Dans la boucle, on débute par le test du dernier caractère de la chaine ; s'il correspond au caractère à rechercher, on quitte la fonction en retournant l'adresse de ce caractère dans la chaine.

À chaque tour de boucle, nous effectuons cette vérification et si la condition n'est pas remplie, nous décrémentons i. La boucle tourne jusqu'à atteindre le premier caractère de la chaine.

Si aucune occurrence du caractère n'est trouvée, la fonction se termine en retournant la valeur NULL.

Complexité temporelle dans le pire des cas :

Dans le pire des cas où le caractère souhaité n'est pas trouvé : complexité en O(taille(s)+C(c_strlen(s)))

XIII-D. Implémentation

 
Sélectionnez
char * c_strrchr (const char * s, int c)
{
   const char * p = s + c_strlen (s);
 
   do
   {
      if (*p == (char) c)
      {
         return (char *) p;
      }
   }
   while (--p >= s);
 
   return NULL;
}

Les modifications apportées à l'implémentation ci-dessus sont mineures.

On commence par retrouver l'adresse de fin de la chaine donc son dernier caractère, que l'on assigne au pointeur p. La condition de la boucle change également un peu, car nous mettons l'instruction de décrémentation à l'intérieur de celle-ci. On décrémente en fait le pointeur p puis on teste son adresse avec celle de la chaine s qui correspond donc au début de la chaine. La boucle s'arrête lorsque le début de la chaine a été atteint si bien sûr, aucune occurrence du caractère demandé n'a été trouvée !

XIII-E. Tests

 
Sélectionnez
#include "c_string.h"
#include <stdio.h>
 
 
int main (void)
{
   const char * str = "Ma chaine de caracteres !";
   char * p = NULL;
 
   p = c_strrchr (str, 'c');
 
   if (p != NULL)
   {
      printf ("%s\n", p);
   }
 
   return 0;
}

Le test est identique à celui de la fonction précédente c_strchr sauf que nous recherchons la dernière occurrence du caractère passé en second argument à la fonction c_strrchr. Voici la sortie du test qui recherche la dernière occurrence du caractère c :

 
Sélectionnez
cteres !
 
Process returned 0 (0x0)   execution time : 0.015 s
Press any key to continue.

précédentsommairesuivant

Copyright © 2007 Franck Hecht. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.