XIII. c_strrchr▲
XIII-A. Prototype▲
char
*
c_strrchr (
const
char
*
s, int
c);
XIII-B. Description et comportement▲
La fonction c_strrchr permet de rechercher la dernière occurrence du
caractère c (par conversion du type entier en caractère) dans la chaîne
s passée en argument. Le zéro de fin participe à la recherche ainsi,
lorsque vous passez le caractère nul comme caractère à rechercher,
la fonction renvoie un pointeur sur la fin de la chaîne !
Si le caractère passé en argument ne figure pas dans la chaîne, la fonction
renvoie la valeur NULL.
La chaîne de caractère doit posséder un caractère de code nul sinon il y'a risque
de dépassement de la zone mémoire passée en argument ce qui a pour effet une possibilité
d'un comportement indéterminé de votre programme !
XIII-C. Algorithme▲
Voici un algorithme possible pour la fonction c_strrchr:
algorithme
fonction c_strrchr (s:chaîne, c:entier):chaîne
debut
i <- longueur (s)
faire
si s[i] égal à c
alors retourne s[i]
fsi
i <- i - 1
tant que i supérieur ou égal à 0
retourne NULL
fin
lexique
s : chaîne : Chaîne dans laquelle il faut trouver la dernière occurrence du caractère c.
c : entier : Caractère dont il faut trouver la première occurrence dans la chaîne s.
i : entier : Variable d'incrémentation pour se déplacer dans la chaîne s.
Nous avons ici l'algorithme inverse de la fonction c_strchr.
On commence par récupérer la taille de la chaîne que nous stockons dans la variable
i. Dans la boucle, on débute par le test du dernier caractère de la chaîne ;
s'il correspond au caractère à rechercher, on quitte la fonction en retournant
l'adresse de ce caractère dans la chaîne.
A chaque tour de boucle, nous effectuons cette vérification et si la condition
n'est pas remplie, nous décrémentons i. La boucle tourne jusqu'à atteindre
le premier caractère de la chaîne.
Si aucune occurrence du caractère n'est trouvée, la fonction se termine en
retournant la valeur NULL.
Complexité temporelle dans le pire des cas: |
---|
Dans le pire des cas où le caractère souhaité n'est pas trouvé: complexité en O(taille(s)+C(c_strlen(s))) |
XIII-D. Implémentation▲
char
*
c_strrchr (
const
char
*
s, int
c)
{
const
char
*
p =
s +
c_strlen (
s);
do
{
if
(*
p ==
(
char
) c)
{
return
(
char
*
) p;
}
}
while
(--
p >=
s);
return
NULL
;
}
Les modifications apportées à l'implémentation ci-dessus sont mineures.
On commence par retrouver l'adresse de fin de la chaîne donc son dernier
caractère, que l'on assigne au pointeur p. La condition de la
boucle change également un peu car nous mettons l'instruction
de décrémentation à l'intérieur de celle-ci. On décrémente en fait le
pointeur p puis on teste son adresse avec celle de la chaîne s
qui correspond donc au début de la chaîne. La boucle s'arrête lorsque
le début de la chaîne à été atteint si bien sûr, aucune occurrence du
caractère demandé n'a été trouvée !
XIII-E. Tests▲
#include "c_string.h"
#include <stdio.h>
int
main (
void
)
{
const
char
*
str =
"
Ma chaine de caracteres !
"
;
char
*
p =
NULL
;
p =
c_strrchr (
str, '
c
'
);
if
(
p !=
NULL
)
{
printf (
"
%s
\n
"
, p);
}
return
0
;
}
Le test est identique à celui de la fonction précédente c_strchr sauf que nous recherchons la dernière occurrence du caractère passé en second argument à la fonction c_strrchr. Voici la sortie du test qui recherche la dernière occurrence du caractère c:
cteres !
Process returned 0 (0x0) execution time : 0.015 s
Press any key to continue.