Coder la fonction strstr

Version imprimable

Bonjour,

Je suis entrain de recoder moi même certaine fonction de string.h, afin de verifier mes connaissance et ma compression de leurs effets.

Néanmoins je bloque sur la fonction strstr, qui chercher une chaîne de caractères dans une chaîne de caractères.

Voici mon code:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
 
int main(int argc, char *argv [])
 {
     char *Next_String;
 
     Next_String = String_In_String ("Petit texte de test", "test");
 
     if (Next_String != NULL)
      {
          printf("L'occurrence est : %s.\n", Next_String);
      }
 
 
    return 0;
 }
 
int Size_String (char *String)
 {
     char Character = 0;
     int Number_Of_Character = 0;
 
     do
      {
          Character = String [Number_Of_Character];
          Number_Of_Character ++;
      } while(Character != '\0');
 
    return Number_Of_Character;
 }
int Comp_String (const char *String_1, const char *String_2)
 {
     int Size = 0, Size_1 = 0, Size_2 = 0, Comp = 0, i;
 
     Size_1 = Size_String (String_1);
     Size_2 = Size_String (String_2);
 
     Size = Size_1 - Size_2;
 
     if (Size == 0)
      {
          for(i=0; i<Size; i++)
           {
               if (String_1 [i] == String_2 [i])
                {
                    Comp = 0;
                    //printf("Les chaines sont identiques.\n\n");
                    return Comp;
                }
           }
      }
 
     else
      {
          if (Size > 0)
           {
               Comp = 1;
               printf("Les chaines sont differentes, la premiere etant plus grande que la seconde.\n\n");
               return Comp;
           }
 
          if (Size < 0)
           {
               Comp = -1;
               printf("Les chaines sont differentes, la premiere etant plus petite que la seconde.\n\n");
               return Comp;
           }
      }
 }
 
char *String_In_String (const char *String_1, const char *String_2)
 {
     int Size = 0, Size_1 = 0, Size_2 = 0, Comp = 0, i, k;
     char *Occurrence = 0;
 
     Size_1 = Size_String (String_1);
     Size_2 = Size_String (String_2);
 
     Comp = Comp_String (String_1, String_2);
 
     for(i=0; i<Size_1; i++)
      {
          for(k=0; k<Size_2; k++)
           {
               if ( (String_1 [i] == String_2 [k]))
                {
                    return String_1 - Size_2;
                }
           }
      }
 
    return NULL;
 }

De plus si quelqu'un connais des exo (corrigés de preference) sur les pointeurs ca m'aiderait pas mal je pense =), merci.

17/07/2009, 12h47
gl

Citation:

Envoyé par Ququbs

Je suis entrain de recoder moi même certaine fonction de string.h, afin de verifier mes connaissance et ma compression de leurs effets.

Néanmoins je bloque sur la fonction strstr, qui chercher une chaîne de caractères dans une chaîne de caractères.

Je t'invite à jeter un œil à Etude détaillée du module String de la libc qui pourrait te donner des pistes.
17/07/2009, 13h47
Ququbs

Sinon tu trouve que ma fonction Comp_String est fausse, car on me signale que oui mais je vois pas l'erreur même avec la doc détaillée.

Mais sinon une truc que je comprend pas pourquoi dans la fonction il:

char * c_strstr (const char * s1, const char * s2)
{
const char * p_s1 = s1;

Alors que S1 est déjà un pointeur? :x
17/07/2009, 15h26
gl
Citation:

Envoyé par Ququbs

Sinon tu trouve que ma fonction Comp_String est fausse, car on me signale que oui mais je vois pas l'erreur même avec la doc détaillée.

Oui, au moins trois problèmes :
- Si la taille des deux chaînes, tu retournes une valeur dépendant de l'ordre relative des tailles et non de l'ordre lexicographique, contrairement à strcmp().
- Si les tailles sont égales, Size vaut 0, donc la boucle for(i=0; i<Size; i++) est équivalente à for(i=0; i<0; i++) et donc aucune itération n'a lieu et la comparaison n'a pas lieu.
- Même en supposant que la boucle est bonne (itération sur la taille des chaînes et non sur Size qui vaut 0), tu retournes 0 dès qu'un caractère est identique et donc avec cette boucle, "maison" est égale à "meuble" ainsi qu'à "tables".
Citation:

Envoyé par Ququbs

Mais sinon une truc que je comprend pas pourquoi dans la fonction il:

char * c_strstr (const char * s1, const char * s2)
{
const char * p_s1 = s1;

Alors que S1 est déjà un pointeur? :x

C'est un choix d'implémentation et je ne connais pas les raisons de ce choix.
Ce code aurait fonctionné en utilisant directement le pointeur s1, modification qui aurait été purement locale à la fonction vu que le pointeur est passé par valeur.
Ceci dit, à titre personnel, je n'aime pas trop utiliser les paramètres d'une fonction (même lorsqu'ils sont passé par valeur) en guise de compteur ou autre mécanisme du même style, trop de risque de modifier quelque chose qu'il ne faut pas et plus complexe en général à faire évoluer.
17/07/2009, 15h54
Ququbs

Bon je vais refaire toutes mes fonctions alors, tu voudras bien jeter un coup d'oeil aprés? x)

Et si j'ai bien compris:

// Tant que String != '\0' <=> // Tant que *String ?
17/07/2009, 16h35
gl

Citation:

Envoyé par Ququbs

Et si j'ai bien compris:

// Tant que String != '\0' <=> // Tant que *String ?

Si String est un pointeur sur un caractère alors, dans une condition *String != '\0' est équivalent à *String.
Je te conseille la première notation qui est plus facile à lire.
18/07/2009, 17h30
Ququbs

Je comprend pas trop:

Citation:

si s1[i] == 0
alors retourne 0

Dans strcmp :s
18/07/2009, 18h12
gl

Citation:

Envoyé par Ququbs

Je comprend pas trop:

Citation:

si s1[i] == 0
alors retourne 0

Dans strcmp :s

Ça signifie tout simplement que si la fin de la chaîne est atteinte on retourne 0 (la condition d'égalité entre le caractère d'index i des deux chaînes est déjà vérifiés dans la condition précédente).

Le caractère '\0' dont la valeur est 0 (ce qui signifie que si[i] == 0 est équivalent ) s1[i] == '\0') marque en C la fin d'une chaîne de caractère.
18/07/2009, 18h38
Ququbs

Je savais pas que c'était équivalent merci.
18/07/2009, 20h28
Ququbs

Si les chaînes sont de même taille mais différentes on doit renvoyer quelle nombre?xD
18/07/2009, 21h12
coyotte507

Renseigne-toi un peu sur la doc de strcmp, tu connaîtras le comportement désiré de la fonction :roll:
18/07/2009, 23h00
gl
Citation:

Envoyé par Ququbs

Si les chaînes sont de même taille mais différentes on doit renvoyer quelle nombre?xD

Si tu cherches bien à implémenter l'équivalent de strcmp(), le code retour doit être (extrait de l'article dont j'ai précédemment donnée le lien) :
Citation:
Valeur négative si la chaîne d'adresse s1 est inférieure à la chaîne d'adresse s2.
Zéro si les deux chaînes de caractères sont identiques.
Valeur positive si la chaîne d'adresse s1 est supérieure à la chaîne d'adresse s2.

Voila ca a l'air mieux.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
int c_strcmp (const char *s1, const char *s2)
{
    int i=0;
 
    while (s1 [i] == s2 [i])
     {
         i++;
 
         if (s1 [i] == '\0')
          {
              return 0;
          }
     }
 
    return (s1 [i] > s2 [i])  ? 1 : -1;
}

Là tu auras un risque de segfault si tu passes deux chaines "" en paramètre à ta fonction.
En plus tu peux retourner 0 même si les deux chaînes sont différentes (ex: teste avec "abc", "abcdef")

Je verrais plutôt le code comme ça:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 int c_strcmp (const char *s1, const char *s2) { while (*s1 == *s2) { if (*s1 == 0) /* ce qui veut dire *s1 == *s2 == 0 */ return 0; ++s1, ++s2; /* on déplace les pointeurs */ } return (*s1> *s2) ? 1 : -1; }

21/07/2009, 20h48
Ququbs

En gardant mon code et en mettant l'incrémentation après le test ca marche mieux =o
21/07/2009, 21h15
coyotte507

Ah oui :aie:

Là je vois pas de problèmes :ccool:
21/07/2009, 22h31
Ququbs

Par contre j'ai encore du mal avec strstr, même avec l'algo, y'aurais pas un moyen de la faire en utilisant c_strcmp qu'on a fait?

J'arrive pas a faire un truc qui aboutis :s

En cresant j'ai fait ca mais je trouva ca très bourrin au niveau du return...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
char *c_strstr (const char *s1, const char *s2)
 {
     int size =0;
     size = c_strlen(s2);
     int count =0;
 
     while(*s1++)
      {
          while(*s1==*s2)
           {
               count ++;
               if(count==size)
                {
                    return s2;
                }
 
               else
                {
                    *s1++;
                    *s2++;
                }
           }
      }
return NULL;
 }

22/07/2009, 13h56
coyotte507

Salut,

ta fonction est fausse, déjà la définition est de trouver la première occurence de str2 dans str1.

Donc je ne vois pas pourquoi tu fais des s2++, en fait il suffit juste de parcourir tous les caractères de s1 et de faire strcmp(s1, s2) == 0 pour voir (en augmentant s1 jusqu'à ce que *s1 == 0).
22/07/2009, 15h06
Ququbs

T'es sûre que ca marche?

Parceque strcmp compare *s1 a s2, mais s2 ne sera jamais totalement identique a *s1 non?
22/07/2009, 15h52
coyotte507

Ah oui tu as raison :aie:

Ca serait strncmp(s1, s2, strlen(s2)), mais il faudrait stocker strlen(s2) pour éviter de le réappeler à chaque fois.

Sinon pour optimiser tu peux implémenter la comparaison dans la méthode mais dans ce cas-là au lieu de faire varier s1 et s2 pour faire une comparaison caractère à caractère il faut copier s1 et s2 dans deux pointeurs temporaires et faire varier ceux-ci.

Enfin dans un premier temps fais la première version!

Tu peux essayer de coder l'algo suivant :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1- si s2 est vide, retourner s1 (C'est la norme!)

  Pour l'analyse de la chaine, on va simultanément parcourir les deux chaines
  à partir de s1 et s2 :
2- Tant que s1 n'est pas à la fin de la chaine :
  2-1- initialiser un pointeur sp1 avec s1 
  2-2- initialiser un pointeur sp2 avec s2
  2-3- Tant que le caractère pointé par sp1 est égal au caractère pointé par sp2
       et que l'on est pas arrivé à la fin de l'une des deux chaines : 
       incrémenter sp1 et sp2
  2-4- Si le caractère pointé par sp2 est alors le caractère de fin de chaine,
       la sous-chaine a été trouvée : retourner s1
  2-5- Sinon, analyser la chaine à partir du caractère suivant : incrémenter s1

3- La sous chaine n'a pas été trouvée : retourner NULL

Pour l'algo de diogene je tombe sur cela:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
char *c_strstr (const char *s1, const char *s2)
 {
     const char *ps1=s1;
     const char *ps2=s2;
 
     if(*ps2==NULL)
      {
          return ps1;
      }
 
     while(*ps1++)
      {
          for(*ps1; *ps1!=0; *ps1++)
           {
               for(*ps2; *ps2!=0; *ps2++)
                {
                    /**
                    while( (*ps1==*ps2) && (*ps1!=0 || *ps2!=0) )
                    
                    {**/
 
 
               if(*ps2==0)
                {
                    return ps1;
                }
 
               else
                {
                    *ps1 ++;
                }
 
               //                *ps1++;
               //*ps2++;
           }
     } }
 
    return NULL;
 }

Où sont les erreurs?

22/07/2009, 19h57
coyotte507

L'initialisation est dans la boucle, pas en dehors.

Les pointeurs ps1 et ps2 ne devraient pas exister en dehors de la boucle.

Pourquoi ca, ne marche pas?
Code:

1 2 3 4 5 6 //Initialisation... int comp = strncmp(s1,s2,size); // Code.. if(comp==0) // Code...
Et que cela marche:
Code:

1 2 3 if(strncmp(s1,s2,size) //Code...

22/07/2009, 22h27
coyotte507

Ca ne serait pas:

Code:

if(strncmp(s1,s2,size)==0)

Sinon poste un code complet qui ne marche pas..........
23/07/2009, 13h08
Ququbs

Tout est bon, merci !

Ps les doc sur comme celle de string.h y'en a sur tout? =p
23/07/2009, 14h32
coyotte507

Il y a une doc ici:

http://www.cppreference.com/wiki/c/start

Il y en a plein d'autres (linux man pages, ...)

Citation:

Envoyé par Ququbs

Pour l'algo de diogene je tombe sur cela:...

Où sont les erreurs?

Tu ne respectes pas l'algo :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
char *c_strstr (const char *s1, const char *s2)
{
   const char *ps1;
   const char *ps2;
   //1- si s2 est vide, retourner s1 (C'est la norme!)
   if(*s2 == 0) return s1;
   //  Pour l'analyse de la chaine, on va simultanément parcourir les deux chaines
   //  à partir de s1 et s2 :
   //2- Tant que s1 n'est pas à la fin de la chaine :
   while(*s1 !=0)
   {
       //  2-1- initialiser un pointeur sp1 avec s1
       ps1 = s1;
       //  2-2- initialiser un pointeur sp2 avec s2
       ps2 = s2;
       //  2-3- Tant que le caractère pointé par sp1 est égal au caractère pointé par sp2
       //       et que l'on est pas arrivé à la fin de l'une des deux chaines :
       //       incrémenter sp1 et sp2
       while(*ps1== *ps2 && *ps1 !=0 && *ps2 != 0)
       {
         ps1++;
         ps2++;
       }
       //  2-4- Si le caractère pointé par sp2 est alors le caractère de fin de chaine,
       //       la sous-chaine a été trouvée : retourner s1
       if(*ps2==0) return s1;
       //  2-5- Sinon, analyser la chaine à partir du caractère suivant : incrémenter s1
       s1++;
    }
    // 3- La sous chaine n'a pas été trouvée : retourner NULL
    return NULL;
}

23/07/2009, 16h20
Ququbs

C'est bon tout fonctionne merci =)