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

XVI. c_strpbrk

XVI-A. Prototype

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

XVI-B. Description et comportement

La fonction c_strpbrk recherche la première occurrence d'un caractère de la chaine s2 dans la chaine s1 et retourne un pointeur sur le caractère trouvé.

Le zéro de fin de chaine ne participe pas à la recherche.

La fonction renvoie la valeur NULL si aucun caractère de l'ensemble s2 n'appartient à la chaine s1 !

XVI-C. Algorithme

Voici un algorithme possible pour la fonction c_strpbrk :

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

L'algorithme ci-dessus parcourt la chaine s1 caractère par caractère. À chaque itération, on parcourt la chaine s2 à la recherche du caractère courant dans la chaine s1.

Si le caractère courant de la chaine s1 correspond à un des caractères de la chaine s2, on retourne l'adresse mémoire (un pointeur en C) du caractère.

Si la première boucle se termine, on retourne NULL qui dans ce cas, indique que la chaine s1 ne contient pas de caractère figurant dans l'ensemble s2 !

Complexité temporelle dans le pire des cas :

Dans le pire des cas où il n'y a aucune lettre de s1 dans s2 : complexité en O(taille(s1)*taille(s2)+C(c_strlen(s2))

XVI-D. Implémentation

 
Sélectionnez
char * c_strpbrk (const char * s1, const char * s2)
{
   const char * p_s1 = s1;
   int i = 0;
   int len = c_strlen (s2);
 
   while (*p_s1++)
   {
      for (i = 0; i < len; i++)
      {
         if (s2[i] == *p_s1)
         {
            return (char *)p_s1;
         }
      }
   }
 
   return NULL;
}

L'implémentation ici correspond à l'algorithme présenté ci-dessus, mais est simplement adaptée au C et donc à l'utilisation des pointeurs. On peut juste noter que le retour du pointeur sur le caractère trouvé (dans la condition à l'intérieur de la seconde boucle) est caster en type char *, car effectivement, le pointeur de parcours est du type const char * tout comme le sont les paramètres !

XVI-E. Tests

 
Sélectionnez
#include "c_string.h"
#include <stdio.h>
 
 
int main (void)
{
   const char * s1 = "Bonjour !";
   const char * s2 = "rj";
   char * p = NULL;
 
   p = c_strpbrk (s1, s2);
 
   if (p != NULL)
   {
      printf ("%s\n", p);
   }
 
   return 0;
}

Nous pouvons observer le comportement de la fonction avec ce simple programme. Notre ensemble de caractères s2 contient deux caractères figurant dans la chaine s1. On peut noter que seule la première occurrence de l'un d'eux valide la condition de la fonction et y met fin donc ici dans notre test, c'est l'adresse du caractère j qui est retourné :

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