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

XIX. c_strstr

XIX-A. Prototype

 
Sélectionnez
char * c_strstr (const char * s1, const char * s2);

XIX-B. Description et comportement

La fonction c_strstr recherche la première occurrence de la sous-chaine s2 dans la chaine s1. Le zéro de fin ne participe pas à la recherche !

La fonction retourne un pointeur sur la position du premier caractère de la sous-chaine retrouvée ou NULL si aucune occurrence n'a été trouvée.

Si la sous-chaine s2 est vide (""), alors la fonction renvoie la chaine s1.

XIX-C. Algorithme

Voici un algorithme possible pour la fonction c_strstr:

 
Sélectionnez
algorithme
   fonction c_strstr (s1:chaîne, s2:chaîne):chaîne
      début
         i <- 0
         len <- longueur (s2)
 
         tant que s1[i] différent de '\0' faire
            si c_memcmp (s1[i], s2, len) égal à 0
               alors retourne s1[i]
            fsi
 
            i <- i + 1
         ftant
 
         retourne NULL
      fin
 
lexique
   s1  : chaine : Chaine de caractères de recherche.
   s2  : chaine : Sous-chaine à retrouver dans la chaine s1.
   i   : entier : Variable d'incrémentation pour le parcours de la chaine s1.
   len : entier : Longueur de l'ensemble s2.

Nous commençons par initialiser les variables dont la variable len qui contiendra la longueur de la sous-chaine s2. Nous pourrions en effet éviter la déclaration d'une variable, mais cela coûterait un appel de fonction supplémentaire à chaque itération de notre boucle donc baisse des performances !

Nous parcourons la chaine s1 tant que nous n'arrivons pas à la fin de la chaine ou jusqu'à ce que la fonction trouve une première occurrence de la sous-chaine s2, ce que nous testons dans la condition à l'intérieur de la boucle.

Si la fonction c_memcmp renvoie la valeur 0 alors, cela signifie que nous avons trouvé une première sous-chaine et on retourne dans ce cas la position du premier caractère de celle-ci !

Complexité temporelle dans le pire des cas :

Dans le pire des cas s2 n'apparaît pas dans s1 : complexité en O(taille(s1)*C(c_memcmp))

XIX-D. Implémentation

 
Sélectionnez
char * c_strstr (const char * s1, const char * s2)
{
   const char * p_s1 = s1;
   c_size_t len = c_strlen (s2);
 
   while (*p_s1)
   {
      if (c_memcmp (p_s1, s2, len) == 0)
      {
         return (char *)p_s1;
      }
 
      p_s1++;
   }
 
   return NULL;
}

L'implémentation ci-dessus est identique à l'algorithme présenté plus haut sauf que nous utilisons des pointeurs ! On peut juste remarquer que le retour de la fonction dans la condition if se fait par cast car effectivement, notre pointeur p_s1 tout comme les arguments de la fonction sont du type const char * alors que nous devons retourner le type char * !

XIX-E. Tests

 
Sélectionnez
#include "c_string.h"
#include <stdio.h>
 
 
int main (void)
{
   printf ("%s\n", c_strstr ("Bonjour, le monde !", "le "));
   return 0;
}

Dans ce simple programme d'exemple, on recherche la sous-chaine « le » ce qui nous fait afficher le résultat :

 
Sélectionnez
le monde !
 
Process returned 0 (0x0)   execution time : 0.031 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.