XVI. c_strpbrk▲
XVI-A. Prototype▲
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 chaîne s2 dans la chaîne s1
et retourne un pointeur sur le caractère trouvé.
Le zéro de fin de chaîne ne participe pas à la recherche.
La fonction renvoie la valeur NULL si aucun caractère de
l'ensemble s2 n'appartient à la chaîne s1 !
XVI-C. Algorithme▲
Voici un algorithme possible pour la fonction c_strpbrk:
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 : chaîne : Chaîne de caractères de recherche.
s2 : chaîne : Ensemble de caractères dont il faut trouver une occurrence dans la chaîne s1.
i : entier : Variable d'incrémentation pour le parcours de la chaîne 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 chaîne s1 caractère
par caractère. A chaque itération, on parcours la chaîne s2
à la recherche du caractère courant dans la chaîne s1.
Si le caractère courant de la chaîne s1 correspond à un
des caractères de la chaîne 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 chaîne 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▲
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é 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▲
#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 chaîne 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é:
jour !
Process returned 0 (0x0) execution time : 0.046 s
Press any key to continue.