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

XX. c_strtok

XX-A. Prototype

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

XX-B. Description et comportement

La fonction c_strtok permet d'éclater la chaine de caractères s1 en plusieurs éléments lexicaux d'après la liste des délimiteurs contenus dans l'ensemble s2.

Le premier appel doit fournir l'adresse d'une chaine s1 et les appels suivants, s'ils se font sur la même chaine, doivent se faire en passant NULL au premier argument ! L'ensemble de délimiteurs peut par contre changer à chaque appel.

La fonction renvoie un pointeur sur le début de la sous-chaine découpée ou NULL si plus aucun délimiteur n'est trouvé.

La fonction modifie son argument s1 en y plaçant un zéro de fin de chaine après la fin de chaque élément lexical, il convient donc de travailler sur une copie de la chaine !

XX-C. Algorithme

Voici un algorithme possible pour la fonction c_strtok :

L'algorithme ci-dessous est tiré de la fonction strtok_r trouvée sur le site Koders à l'adresse : strtok_r.cstrtok_r.c

 
Sélectionnez
algorithme
   fonction c_strtok (s1:chaîne, s2:chaîne):chaîne
      début
         i <- 0
         ptr <- NULL
         ret <- NULL
 
         /* 1. */
         si s1 égal à NULL
            alors s1 = ptr
         fsi
 
         /* 2. */
         tant que s1[i] différent de '\0' et c_strchr (s2, s1[i]) égal vrai faire
            i <- i + 1
         ftant
 
         si s1[i] égal à '\0'
            alors
               /* 3. */
               ret = NULL
            sinon
               /* 4. */
               ret = s1[i]
 
               /* 5. */
               tant que s1[i] différent de '\0' et c_strchr (s2, s1[i]) égal faux faire
                  i <- i + 1
               ftant
 
               /* 6. */
               si s1[i] différent de '\0'
                  alors s1[i] = '\0'
               fsi
 
               /* 7. */
               ptr = s1[i]
         fsi
 
         retourne ret
      fin
 
lexique
   s1  : chaine : Chaine de caractères à découper.
   s2  : chaîne : Ensemble de délimiteurs à considérer pour la découpe.
   i   : entier : Variable d'incrémentation pour le parcours de la chaine s1.
   ptr : chaine : Variable statique permettant de stocker le dernier emplacement de la découpe.
   ret : chaine : Partie courante de la chaine découpée. Variable retournée par la fonction.

L'algorithme ci-dessus est sans doute le plus long et compliqué de cet article, les explications seront donc scindées en 7 groupes par rapport à la numérotation qui est en place dans l'algorithme !

On commence comme d'habitude par déclarer et initialiser nos variables locales. Ici, la variable ptr nous permet de stocker le début de la prochaine découpe lors d'un nouvel appel de la fonction si bien sûr, le premier argument est mis sur la valeur NULL !

  1. On commence par déterminer si le premier argument vaut NULL. Cela a une incidence sur le bon déroulement de l'éclatement de la chaine de caractères. Si vous devez appeler cette fonction plusieurs fois sur la même chaine, il vous faut passer cet argument avec la valeur NULL ! Ici si l'argument s1 vaut NULL, on passe alors l'adresse contenue dans ptr à s1.
  2. Cette première boucle permet de repérer le premier caractère de la partie de la chaine à découper donc en recherchant tout simplement le premier caractère qui ne se trouve pas dans l'ensemble des délimiteurs s2.
  3. Si après notre première recherche le caractère courant n'est autre que le zéro de fin de chaine, on attribue la valeur NULL à la variable ret et on quitte la fonction.
  4. Si on se trouve après notre première recherche sur le début de la sous-chaine à renvoyer, on attribue à la variable ret l'adresse du début de cette dernière.
  5. Cette seconde boucle permet de calculer la longueur de la sous-chaine à renvoyer. Ceci permet à la fonction de savoir où placer le nouveau zéro de fin de chaine. C'est en effet le cas où la fonction c_strtok, tout comme la version offcielle, modifie la chaine source en y plaçant des zéros de fin de chaine après chaque découpage, il convient donc de travailler sur des copies des chaines sous peine de ne plus pouvoir les utiliser !
  6. Si l'on ne se trouve pas sur un zéro de fin de chaine, on en place un et on se déplace d'une case mémoire donc au début de la future découpe lors d'un prochain appel.
  7. On transmet l'adresse du début de la prochaine découpe à la variable ptr qui est je le rappelle une variable statique, elle garde donc sa valeur même lors de la fin de la fonction !

Complexité temporelle dans le pire des cas :

Dans le pire des cas, on parcourt UNE seule fois la chaine s1 : complexité en O(taille(s1)*C(c_strchr))

XX-D. Implémentation

 
Sélectionnez
char * c_strtok (char * s1, const char * s2)
{
   static char * ptr = NULL;
   char * ret = NULL;
 
   if (s1 == NULL)
   {
      s1 = ptr;
   }
 
   while (*s1 && c_strchr (s2, *s1))
   {
      ++s1;
   }
 
   if (*s1 == '\0')
   {
      ret = NULL;
   }
   else
   {
      ret = s1;
 
      while (*s1 && !c_strchr (s2, *s1))
      {
         ++s1;
      }
 
      if (*s1)
      {
         *s1++ = '\0';
      }
 
      ptr = s1;
   }
 
   return ret;
}

Cette implémentation est la copie conforme de l'algorithme présenté plus haut, mais adapté au C.

XX-E. Tests

 
Sélectionnez
#include "c_string.h"
#include <stdio.h>
 
 
int main (void)
{
   char str [] = "Ma chaine de caracteres !";
   char * p_str = str;
   char * p = NULL;
 
   while ((p = c_strtok (p_str, " ")) != NULL)
   {
      printf ("%s\n", p);
      p_str = NULL;
   }
 
   return 0;
}

Dans ce programme de test, on veut faire découper la chaine pointée par str, avec comme délimiteur un simple espace :

 
Sélectionnez
Ma
chaine
de
caracteres
!
 
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.