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

XVII. c_strspn

XVII-A. Prototype

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

XVII-B. Description et comportement

La fonction c_strspn calcule la longueur du segment initial de la chaine s1 ne contenant que des caractères de l'ensemble s2. Son comportement est semblable à la fonction c_strpbrk sauf qu'elle retourne la taille du segment initial et non un pointeur !

Le caractère de fin de chaine ne participe pas à la recherche.

La fonction renvoie la taille du segment initial ou 0 si aucun caractère du début de la chaine s1 ne figure dans l'ensemble s2.

XVII-C. Algorithme

Voici un algorithme possible pour la fonction c_strspn :

 
Sélectionnez
algorithme
   fonction c_strspn (s1:chaîne, s2:chaîne):entier
      début
         i <- 0
         j <- 0
         len_s1 <- longueur (s1)
         len_s2 <- longueur (s2)
         size <- 0
         quit <- 0
 
         pour i de 0 à len_s1 et tant que quit égal à 0 faire
            quit <- 1
            pour j de 0 à len_s2 et tant que quit égal à 1 faire
               si s2[j] égal à s1[i]
                  alors
                     quit <- 0
                     size <- size + 1
               fsi
            fpour
         fpour
 
         retourne size
      fin
 
lexique
   s1     : chaine : Chaine de caractères de recherche.
   s2     : chaine : Ensemble de caractères devant se trouver dans le segment initial de 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_s1 : entier : Longueur de la chaine s1.
   len_s2 : entier : Longueur de l'ensemble s2.
   size   : entier : Taille du segment initial.
   quit   : entier : Drapeau de sortie de la fonction.

Nous commençons comme d'habitude par initialiser des variables, on initialise de même à la valeur 0 la variable size qui est celle utilisée pour stocker la taille du segment initial ainsi que la variable quit qui est le drapeau de sortie de la fonction.

Notre première boucle dispose de deux conditions de sortie et se termine lorsqu'une des deux devient vraie à savoir dans l'ordre :

  1. Si la variable quit vaut ;
  2. Si la fin de la chaine s1 a été atteinte.

La première instruction met la variable quit à la valeur 1. Ceci nous permet de sortir de la fonction si aucun caractère valide n'a été trouvé.

Nous attaquons ensuite le parcours de l'ensemble s2 (un parcours complet de l'ensemble est effectué à chaque tour de la première boucle). Nous possédons ici également deux conditions d'arrêt de la boucle à savoir :

  1. Si la fin de l'ensemble s2 a été atteinte ;
  2. Si la variable quit vaut 0.

Si au cours de cette boucle un caractère de l'ensemble s2 est présent dans le segment initial de la chaine s1, nous mettons la variable quit à la valeur 0 ce qui nous permet de continuer à la sortie de la seconde boucle le parcours de la chaine s1 et nous incrémentons également le compteur size !

Complexité temporelle dans le pire des cas :

Dans le pire des cas s2[j] == s1[i] seulement lorsque j = len_s2-1: complexité en O(taille(s1)*taille(s2)+C(c_strlen(s1))+C(c_strlen(s2)))

XVII-D. Implémentation

 
Sélectionnez
c_size_t c_strspn (const char * s1, const char * s2)
{
   c_size_t j = 0;
   c_size_t i = 0;
   c_size_t len_s1 = c_strlen (s1);
   c_size_t len_s2 = c_strlen (s2);
   c_size_t size = 0;
   int quit = 0;
 
   for (i = 0; !quit && i < len_s1; i++)
   {
      quit = 1;
      for (j = 0; quit && j < len_s2; j++)
      {
         if (s2[j] == s1[i])
         {
            quit = 0;
            size++;
         }
      }
   }
 
   return size;
}

L'implémentation présentée ci-dessus reflète avec exactitude l'algorithme décrit plus haut. Il faut juste noter que les variables i et j sont déclarées en type c_size_t pour satisfaire des futurs avertissements du compilateur, car nous faisons dans le cas contraire des comparaisons entre type int et unsigned int !

Il n'est jamais conseillé de mettre plusieurs conditions dans des boucles for contrairement à ce qui a été fait ici. Cela n'arrange pas toujours la bonne lisibilité et compréhension du code, mais cela nous a permis dans l'implémentation ci-dessus d'écrire un code plus court et plus simple.

XVII-E. Tests

 
Sélectionnez
#include "c_string.h"
#include <stdio.h>
 
 
int main (void)
{
   printf ("%d\n", c_strspn ("OOoo Bonjour ! ooOO", "Oo"));
   return 0;
}

Dans ce simple programme de test, nous recherchons la longueur du segment initial « OOoo » de la chaine passée en premier argument à la fonction c_strspn. Le résultat est le suivant :

 
Sélectionnez
4
 
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.