Problème chaîne sans pointeur

**VitelAdam** · 18/01/2021, 19h03

Bonjour

Je me suis mis à la programmation sous C depuis quelques semaines seulement, et suis bloqué sur un exercice :

Sans utiliser de pointeur, Ecrire la fonction partie_presente qui retourne 1 si une chaîne de caractère est présente dans une autre chaine de caractères et 0 sinon. Les deux chaînes seront passées en paramètre de la fonction.

J'ai beau tourné le problème dans tous les sens, je n'arrive pas, je suis un novice, et c'est ma première de mande sur le forum, espérant ne pas l'avoir déposé dans le mauvais endroit, et espérant une aide de votre part.

D'avance merci.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
#include<stdio.h>
#include<string.h>
/* c'est du langage C */
int partie_presente(char ch1 [], char ch2[])
{
    int i=0, j=0, k=0;
    int h=0, ps=0;
    printf("Entrez une chaîne de caractères: ");
    fgets(ch1,1000,stdin);
    printf("Entrez la séquence recherchée: ");
    fgets(ch2,1000,stdin);
    char tmp[strlen(ch2)];
 
    for(i=0; i<strlen(ch1); i++)
    {
        for(j=i; j<strlen(ch2) ; j++)
        {
            strncpy(tmp, ch1,strlen(ch2));
             h=strcmp(tmp,ch2);          
        }
        if(h==0)
            {
                ps=1;
            }
    }
 
    if(ps==1)
        printf("La séquence est présente\n");
    else
        printf("La séquence n'est pas présente\n");
 
    return ps;
}
 
int main()
{
     char ch1[1000], ch2[1000];
     partie_presente(ch1, ch2);
     return 0;
}

**Sve@r** · 18/01/2021, 20h47

Bonjour

Je ne vois pas trop ce que le "sans utiliser de pointeur" apportera à l'exercice. Peut-être pour te forcer à utiliser la notation indicée mais bon, quand on en arrive au point où on remplace les indices par des pointeurs on a alors atteint un niveau où les indices c'est peanut. Je suis d'ailleurs étonné qu'on t'interdise les pointeurs mais qu'on t'autorise strlen() ou strcmp() (accessoirement moi j'aurais plutôt vu ici strncmp() !!!) car d'une part on ne sait plus si cet exo est là pour t'apprendre l'algo et la manipulation des strings ; et d'autre part, les arguments que tu passes à ces fonctions ce sont des pointeurs.

Sinon question algo c'est pas super compliqué. Une première boucle avec un indice "i" qui balaye ch1. Une seconde boucle avec un second indice "j" qui balaye ch2. Là, si ch2[j] est différent de ch1[i+j] alors tant pis, on passe au "i" suivant et si on atteint la fin de ch1 c'est définitivement perdu (on peut aussi, pour optimiser, s'arrêter avant quand on sait que ch2 ne rentrera plus dans ce qui reste). Et si on arrive à un moment donné à amener "j" au bout de ch2 alors gagné, ch2 est bien dans ch1.
Bien entendu, si (comme je le pense) pas de strlen() alors il faut se repérer au '\0' terminant toute chaine pour savoir quand terminer la première ou seconde boucle.

Quelques détails annexes: une fonction qui doit chercher un truc n'a pas à se préoccuper de la saisie du truc (qu'est-ce qui te dit que le truc ne proviendra pas demain d'un fichier ou d'une bdd ?). Comme Paris face à Priam (ne te préoccupe que de ton épée et de son épée), une fonction qui traite des chaines qu'elle reçoit ne se préoccupe que de les recevoir.
Et introduire strlen() comme condition de fin de boucle est super lourd (le calcul de la taille est effectué à chaque tour de boucle). Comme je l'ai dit, tu as le '\0' qui te permet de savoir quand terminer ta boucle.

**VitelAdam** · 19/01/2021, 21h30

Envoyé par Sve@r

Bonjour

Sinon question algo c'est pas super compliqué. Une première boucle avec un indice "i" qui balaye ch1. Une seconde boucle avec un second indice "j" qui balaye ch2. Là, si ch2[j] est différent de ch1[i+j] alors tant pis, on passe au "i" suivant et si on atteint la fin de ch1 c'est définitivement perdu (on peut aussi, pour optimiser, s'arrêter avant quand on sait que ch2 ne rentrera plus dans ce qui reste). Et si on arrive à un moment donné à amener "j" au bout de ch2 alors gagné, ch2 est bien dans ch1.
Bien entendu, si (comme je le pense) pas de strlen() alors il faut se repérer au '\0' terminant toute chaine pour savoir quand terminer la première ou seconde boucle.

Merci beaucoup pour ce retour, j'ai repris le tout à zéro (et pour être honnête : avec de l'aide ) , et ça marche maintenant. Il faut dire que je me suis compliqué la vie tout seul.
Pour ce qui est des pointeurs, c'était la consigne.
Merci encore.
Problème résolu.

**dalfab** · 20/01/2021, 09h16

C'était la consigne, pourtant c'est impossible d'écrire cette fonction sans pointeur. Il y en a partout. Par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
bool  partie_presente( const char  ch1[], const char  ch2[] ) {
    const size_t  lg1 = strlen( ch1 );
    const size_t  lg2 = strlen( ch2 );
    if ( lg1 < lg2 )
        return  false;
    for ( size_t  i = 0u ;  i <= lg1 - lg2 ;  ++i )
        if ( strncmp( &ch1[i], ch2 , lg2 ) == 0 )
            return  true; 
    return false;
}

C'est mal, j'ai utilisé strlen() et strncmp() qui sont des fonctions qui reçoivent des pointeurs.
Mais la fonction partie_presente() elle aussi est une fonction qui reçoit 2 pointeurs en paramètres. La notation char ch1[] est en fait juste un alias pour dire char* ch1. Et oui ch1 et ch2 et &ch1[i] sont bien 3 pointeurs.

**Sve@r** · 20/01/2021, 13h28

Envoyé par VitelAdam

Merci beaucoup pour ce retour, j'ai repris le tout à zéro (et pour être honnête : avec de l'aide ) , et ça marche maintenant. Il faut dire que je me suis compliqué la vie tout seul.

Problème résolu.

Reprendre à zéro ça peut être une bonne solution qu'il ne faut en effet pas négliger. Des études ont montré qu'il est parfois plus rentable de tout reprendre à zéro que de s'entêter dnas l'erreur. Unix par exemple a été d'abord un échec pendant 5 ans. Au bout de 5 ans d'efforts, les chercheurs ont tout foutu au panier, ont repris à zéro et ont sorti Unix en 2 ans.
De l'aide oui tu en as le droit il n'y a pas de mal à ça. Mais maintenant tu ne voudrais pas nous mettre ton code qu'on voit si on peut optimiser certains détails ? Surtout je suis curieux de voir comment est traduit la contrainte "sans pointeur"...

Envoyé par dalfab

C'était la consigne, pourtant c'est impossible d'écrire cette fonction sans pointeur. Il y en a partout.

Ce que je pense (et si l'exo est posté je pourrai en avoir confirmation) c'est qu'il ne faut pas utiliser de pointeur dans l'algo. Exemple un for (char *pt=ch; *pt != '\0'; pt++) trt(*pt) sera interdit au profit de for (size_t i=0; ch[i] != '\0'; i++) trt(ch[i]). Je pense aussi que le prof ne veut pas qu'on écrive une sous-fonction qui (par exemple) ferait le boulot de strncmp() (ça a été ma première idée quand j'ai répondu à ce post et ensuite je me suis dit "oui mais on ne pourra pas appeler cette fonction sans lui passer un pointeur") et veut qu'on fasse l'algo dans la fonction principale qui, elle, reçoit fatalement un pointeur mais on ne peut pas faire autrement.

**VitelAdam** · 20/01/2021, 21h40

Envoyé par Sve@r

Mais maintenant tu ne voudrais pas nous mettre ton code qu'on voit si on peut optimiser certains détails ? Surtout je suis curieux de voir comment est traduit la contrainte "sans pointeur"...

Sans aucun problème, le code est joint .
Quand j'ai parlé de pointeur c'est *char

Merci encore.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
#include <stdio.h>
#include <string.h>
 
int partie_presente(char ch[], char seq[])
{
    int i=0, p=0;
    while(ch[i]!='\0')
    {
        int j=0;
        int k=i;
        while(ch[k]==seq[j])
        {
            k++;
            j++;
 
            if(seq[j+1]=='\0') 
                p=1;
        }
        i++;
    }
    return p;
}
 
 
int main()
{
    char ch[1000], seq[1000];
    int r=0;
 
    printf("Entrez une chaîne de caractères: ");
    fgets(ch,1000,stdin);
    printf("Entrez la séquence recherchée: ");
    fgets(seq,1000,stdin);
 
    partie_presente(ch, seq);
    r=partie_presente(ch, seq);
 
    if (r==1)
        printf("La séquence est présente\n");
    else if(r==0)
            printf("La séquence n'est pas présente\n");
    return 0;
}

**Sve@r** · 21/01/2021, 17h46

Envoyé par VitelAdam

Quand j'ai parlé de pointeur c'est *char

Bon ben ça c'est clairement inutile. Ecrire char ch[] ou char *ch pour ton paramètre, c'est exactement pareil, quand on passe un tableau à une fonction on ne lui passe que l'adresse de son premier élément, adresse qui sera alors stockée dans une variable apte à stocker une adresse donc un pointeur. Et la syntaxe n'y fera rien. J'aurais pu admettre toute autre raison telles que celles que j'ai évoquées dans mon post précédent mais refuser l'écriture pointeur juste pour la cacher est probablement une des pires (et des plus inutiles) raison qui soient.

Sinon ton code il est pas mal du tout. Juste le while () début peut être remplacé par un for () et "p" peut être supprimée si au lieu d'écrire p=1 tu écris directement return 1 (on a trouvé, plus la peine de continuer). Mais certains profs n'aiment pas cette façon de faire que de quitter une fonction en plein milieu car ils disent que cela nuit à la lisibilité du code.

Accessoirement dans le main() tu appelles 2 fois la fonction. Et bon, t'es sûr que le if (r == 0) dans le "else" est utile ???

**Xelland** · 18/01/2021, 20h53

Bonjour

Beaucoup de choses à dire sur ton code !

Envoyé par VitelAdam

Les deux chaînes seront passées en paramètre de la fonction.

ce n'est pas fait

Tu fais ensuite 2 boucles for (on verra dans un deuxième temps pour les optimisations)
mais tu n'utilises ni i, ni j, donc à quoi servent ces 2 boucles ?

à quoi sert ici l'appel à strncpy ?
pourquoi tu utilises strcmp ? (ça sert à comparer 2 chaines, alors que tu cherches à savoir si A est présent dans B, d'ailleurs avec ou sans la casse ?)

ton code doit être :
1. saisie des chaines
2. contrôle sur les chaines
3. affichage du résultat

**VitelAdam** · 18/01/2021, 21h25

bonjour

@Xelland
Merci pour ce retour. Ce que j'ai mis est une partie d'un long exercice, j'ai demandé et saisi les deux chaine pour plus de clarté.

@Sve@r
Merci pour vos tuyaux, je viens de tester mais il retourne toujours vrai (çàd chaine 2 présente dans chaine 1) dès qu'il trouve un seul caractère.
Voici ce que j'ai fait , et espérant plus d'éclaircissement, je commence à désespérer ...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
 
#include<stdio.h>
#include<string.h>
 
int partie_presente(char ch1 [], char ch2[])
{
    int i=0, j=0;
	printf("Entrez une chaîne de caractères: ");
	fgets(ch1,1000,stdin);
	printf("Entrez la séquence recherchée: ");
	fgets(ch2,1000,stdin);
 
    for(i = 0; ch1[i] != '\0'; ++i)
	{
        for(j=0;j<=strlen(ch2);++j)
            while (ch2[j] != ch1[i+j])
			{
	            i=i+1;
	            return 1;
			}
	}
}
 
int main()
{
	 char ch1[1000], ch2[1000];
	 partie_presente(ch1, ch2);
	 if (partie_presente)
	 printf("La séquence est présente\n");
	 return 0;
}

**Sve@r** · 18/01/2021, 22h17

Envoyé par VitelAdam

Voici ce que j'ai fait , et espérant plus d'éclaircissement, je commence à désespérer ...

Ta seconde boucle (sur j) utilise encore strlen(). Ok ça le fait mais si la première utilise le '\0', on se demande pourquoi tu n'appliques pas le même procédé sur toutes les chaines.
Maintenant à quoi sert la 3° boucle ? Je n'ai jamais parlé d'une 3° boucle. J'ai dit "si ch2[j] est différent de ch1[i+j]" et un "si" n'a jamais été traduit par une boucle (boucle inutile puisque tu quittes la fonction à la première itération).
La base d'un algo c'est le papier et le crayon. Comment tu ferais avec un papier et un crayon si tu ne pouvais voir qu'une lettre à la fois ?

Problème chaîne sans pointeur

C

Vue hybride

Discussions similaires

Partager

Partager