generer les mots d'un alphabet (probleme avec strcat)

**abdelhamidem** · 18/10/2007, 16h13

Bonjour,

Je cherche à faire un programme qui à partir d'un alphabet {a, b}, genere tous les mots possibles de taille inferieure ou egale à un entier "n".
Par exemple pour n=2 :

a; b; aa; ab; ba; bb.

Pour cela, j'ai procédé de la maniere suivante:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void generer(char* mot, int n)
{
    char* mot_a;
    char* mot_b;
 
    // J'ai essayé de mettre des malloc, mais ca ne ne donne rien :o).
    mot_a = (char*) malloc(n*sizeof(char));
    mot_b = (char*) malloc(n*sizeof(char));
 
    //on copie mot dans deux variables chaine de caractere. L'une pour
    //la concatener avec "a", l'autre avec "b".
    mot_a = mot;
    mot_b = mot;
 
    //condition d'arret du programme.
    if (n==0)
        exit(0);
 
//debugage amateur
printf("avant probleme\n");
 
    // On concatene la lettre "a" à mot_a, puis on l'affiche
    strcat(mot_a, "a");
 
//debugage amateur
printf("apres probleme\n");
 
    puts(mot_a);
 
    // on fait de meme avec mot_b et "b"
    strcat(mot_b, "b");
    puts(mot_b);
 
    //Appels recursifs pour generer les autres mots
    //On decremente n pour que le programme s'arrete quand n = 0
    generer(mot_a, n-1);
    generer(mot_b, n-1);
}
 
int main()
{
    int n;
 
    printf("programme de generation de mots a partir de l'alphabet {a, b}\n");
    printf("Entrez N\n");
    scanf("%d", &n);
 
    // on donne un mot "vide" au depart.
    generer("", n);
 
    return 0;
}

Comme vous pourrez le constater dans le code (ou en executant le programme), ca plante juste apres le 1er strcat. En lancant le debuggeur (que je ne maitrise pas du tout) j'ai cru comprendre qu'il s'agissait d'une "segmentation fault".

Voila voila. Alors si vous pouviez m'aider... Merci d'avance.

**Médinoc** · 18/10/2007, 16h40

Hum...

C'est un beau bordel.

Premièrement, on ne "copie" pas une chaîne avec = : = ne copie que le pointeur. Il faut utiliser strcpy() pour copier la chaîne.
Ensuite, pense à mettre des const pour les pointeurs pointant vers quelque chose qui ne doit pas être modifié.
Tu dois absolument définir ce que tu cherches à faire avant de l'implémenter en C. Écris l'algorithme de ce que tu veux faire et poste-le ici.
Et supprime les casts du retour de malloc() : Ils sont inutiles et déconseillés en C.

**Sve@r** · 18/10/2007, 17h43

Envoyé par abdelhamidem

Bonjour,

Je cherche à faire un programme qui à partir d'un alphabet {a, b}, genere tous les mots possibles de taille inferieure ou egale à un entier "n".
Par exemple pour n=2 :

a; b; aa; ab; ba; bb.

Pour cela, j'ai procédé de la maniere suivante:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void generer(char* mot, int n)
{
    char* mot_a;
    char* mot_b;
 
    // J'ai essayé de mettre des malloc, mais ca ne ne donne rien :o).
    mot_a = (char*) malloc(n*sizeof(char));
    mot_b = (char*) malloc(n*sizeof(char));
 
    //on copie mot dans deux variables chaine de caractere. L'une pour
    //la concatener avec "a", l'autre avec "b".
    mot_a = mot;
    mot_b = mot;
 
    //condition d'arret du programme.
    if (n==0)
        exit(0);
 
//debugage amateur
printf("avant probleme\n");
 
    // On concatene la lettre "a" à mot_a, puis on l'affiche
    strcat(mot_a, "a");
 
//debugage amateur
printf("apres probleme\n");
 
    puts(mot_a);
 
    // on fait de meme avec mot_b et "b"
    strcat(mot_b, "b");
    puts(mot_b);
 
    //Appels recursifs pour generer les autres mots
    //On decremente n pour que le programme s'arrete quand n = 0
    generer(mot_a, n-1);
    generer(mot_b, n-1);
}
 
int main()
{
    int n;
 
    printf("programme de generation de mots a partir de l'alphabet {a, b}\n");
    printf("Entrez N\n");
    scanf("%d", &n);
 
    // on donne un mot "vide" au depart.
    generer("", n);
 
    return 0;
}

Comme vous pourrez le constater dans le code (ou en executant le programme), ca plante juste apres le 1er strcat. En lancant le debuggeur (que je ne maitrise pas du tout) j'ai cru comprendre qu'il s'agissait d'une "segmentation fault".

Ouahou... ça part en torche là. Déjà premier truc => jamais de "exit" dans une fonction. On part du main pour aller dans la fonction => on quitte la fonction pour revenir au main (comme les poupées russes)

Sinon j'ai pas trop le temps de suite mais plus tard dans la soirée je regarderai mieux l'algo...

Envoyé par Médinoc

[*]Et supprime les casts du retour de malloc() : Ils sont inutiles et déconseillés en C.

Inutiles certainement. Mais pourquoi "déconseillés" ???

**Médinoc** · 18/10/2007, 17h59

Envoyé par Sve@r

Inutiles certainement. Mais pourquoi "déconseillés" ???

Dangereux en cas d'oubli d'inclusion de stdlib.h, qu'ils masquent (le cast masque le warning de conversion d'entier en pointeur) :

Sur une architecture M68k, pointeurs et entiers ne sont pas retournés dans le même registre : Si le compilo croit que malloc() retourne un int parce qu'on n'a pas inclut stdlib.h, on aura n'importe quoi.
Sous Windows 64 bits, un int et un pointeur n'ont pas la même taille : On perdra donc les 32 bits supérieurs du pointeur.

**Sve@r** · 18/10/2007, 21h41

Envoyé par Médinoc

Dangereux en cas d'oubli d'inclusion de stdlib.h, qu'ils masquent (le cast masque le warning de conversion d'entier en pointeur) :

Sur une architecture M68k, pointeurs et entiers ne sont pas retournés dans le même registre : Si le compilo croit que malloc() retourne un int parce qu'on n'a pas inclut stdlib.h, on aura n'importe quoi.
Sous Windows 64 bits, un int et un pointeur n'ont pas la même taille : On perdra donc les 32 bits supérieurs du pointeur.

Jolie réponse très bien explicitée !!!

**abdelhamidem** · 19/10/2007, 00h15

Envoyé par Médinoc

Hum...

C'est un beau bordel.

Premièrement, on ne "copie" pas une chaîne avec = : = ne copie que le pointeur. Il faut utiliser strcpy() pour copier la chaîne.
Ensuite, pense à mettre des const pour les pointeurs pointant vers quelque chose qui ne doit pas être modifié.
Tu dois absolument définir ce que tu cherches à faire avant de l'implémenter en C. Écris l'algorithme de ce que tu veux faire et poste-le ici.
Et supprime les casts du retour de malloc() : Ils sont inutiles et déconseillés en C.

Merci pour ton aide.

Alors en fait l'algorithme tourne à peu pres comme ca pour generer des mots de taille <= 3 , toujours sur l'alphabet {a, b}
le premier appel de generer se fait avec un mot vide, et n=3.

Code :

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

1
2
3
4
5
6
7
 
 
                                generer("", 3)
                              /              \
                generer("a", 2)               generer("b", 2)
               /           \                      /        \
generer("aa", 1)  generer("ab", 1)    generer("ba", 1)   generer("bb", 1)

etc...

Ce qui se passe dans generer("b", 2) c'est d'abord l'impression à l'ecran des deux mots "ba" puis "bb"...
et ensuite il y a deux appels de generer(,):
_ L'un pour afficher les mots qui viennent apres "ba", c'est à dire : "baa" puis "bab" ... puis faire les 2 appels de generer(,) qui font la suite de l'abrbre.
_ L'autre pour afficher les mots qui viennent apres "ba", c'est à dire : "bba" puis "bbb"... puis faire les 2 appels de generer(,) qui font la suite de l'abrbre.

J'utilise la concatenation car quand on appelle generer("b", 2) je concatene le mot "b" à la lettre "a", puis le mot "b" à la lettre "b", et je les affiche tous les 2. (ca donne "ba" puis "bb")

J'espere que c'est plus clair maintenant.