Discussion :

[yonna]

Bonjour ;
je dois ecrire un programme en c qui permet de implementer une automate fini non deterministe mais avec les structures de données !!!
mercii d'avance

[Bayard]

Bon courage.

Où est votre code ?

[yonna]

Bon courage.

Où est votre code ?

salut;
le probleme c'est on doit utilisé les structures de données voici la structure donnée par le prof :

Code :

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

1
2
3
4
5
struct etat{
                                          int e;//e est le numero de etat enter 
                                          etat*next;//pointeur vers l'etat suivante
                                          };
                                      etat*tr[][];//un tableau de pointeur sur la structure

par exemple tr[0][0].e = 1
tr[0][0].e = 2

voici ce que j'ai fais

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
liste construire()
{
        char condition1 [4],condition2 [4];
        etat* T=NULL;
		int l=0;
		int netats, nfinales,nsymboles;
     int f[10];
     int i,j;
     printf("enter le nombre des etats \n");
     scanf("%d",&netats);
     printf("enter le nombre des symboles \n");
     scanf("%d",&nsymboles);
     printf("\nenter les symbols\t");
 
     for(i=0; i<nsymboles; i++) 
     {
           printf("\n\n %d \t", i+1);
           printf("%c",c[i]=getch());
     }
 
     printf("\n\nenter le number des etats finaux\t");
     scanf("%d",&nfinales);
 
     for(i=0;i<nfinales;i++)
     {
          printf("\n\netat final %d : ",i+1);
          scanf("%d",&f[i]);
     }
 
     printf("-----------------------------------------------------------------------");
     printf("\n\ndefine transition rule as (initial state, input symbol ) = final state\n");
     tr=(int **) malloc(nsymboles*sizeof(int*)); 
     for (i=0; i<nsymboles; i++) 
      tr[i]=(int *) malloc(netats*sizeof(int)); 
   do{
     for(i=0; i<nsymboles; i++)
    {
          for(j=0; j<netats; j++){
                    while(l=0);
               {printf("\n donner un etat");
               scanf("%d",(tr[i][j])->e));
                 if(tr[i][j]->e==-1) return 0;
               tr[i][j]->next=*T;
               *T=tr[i][j];
               printf("Voulez vous ajouter d'autres etats pour cette transition ? (oui/non)\n");
			   scanf("%s",condition1);
		    	l=strcmp(condition1,"non");
		    }
    }}
          while(l=0);      
    for(i=0; i<nsymboles; i++)
          for(j=0; j<netats; j++)
                  tr[i][j]=T;
           do
			{
      for(i=0; i<nsymboles; i++)
       {
          for(j=0; j<netats; j++)
               {printf("\n(%d , %c ) = ",j,c[i]);
               scanf("%d",tr[i][j]->e);
			   tr[i][j]=tr[i][j]->next;
				if ((next==NULL)||(tr[i][j] !=next->T)) l=1;
				else l=0;
			    }}}
			while ((tr[i][j]!= 0) &&  l!=0);
			return (liste)T;}}}
int main()
{
    char rep[3];
			int finale[1],i,nb;
			//liste k=construire();
			do
			{
                  liste k=construire();
 
	         }
		while(strcmp(rep,"non")!=0);
			return 0;
}

[Bayard]

1) J'ai vu des malloc mais je n'ai pas vu de free. Il faut prévoir cela même si c'est dans une fonction à part.

2) Si le prof demande d'utiliser cette structure, il ne demande pas forcément de l'utiliser avec une gestion dynamique de mémoire (malloc).
Pourquoi ne pas avoir un tableau en dur (const) qui contienne les états ?
Cela s'appelle de la gestion statique de mémoire.
Ce serait beaucoup plus simple. Ensuite faire des fonctions qui utilisent ce tableau de structure

Code :

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

struct etat

est assez facile...

[yonna]

Salut, premièrement merci de votre réponse
bon j'ai essayé de changer un peu algorithme mais toujours il y a des problèmes dans cette partie

Code :

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

1
2
3
4
5
{printf("\n donner un etat");
               scanf("%d",&((tr[i][j])->e));
                // if(tr[i][j]->e==-1) return 0;
                 ((tr[i][j]))->next=*T;
                 *T=tr[i][j]

voici tout le programme

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
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
94
95
96
97
98
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<stddef.h>
#include<string.h>
#include<stdlib.h>
char c[10];
struct etat
{
   int e;
   struct etat* next;
};
typedef struct etat etat;
 
typedef etat* liste;   
 
  void  construire(liste *T)
{
        char condition1 [4],condition2 [4];
        //etat* T=NULL;
		int l=0;
		int netats, nfinales,nsymboles;
		etat*tr[10][10];
     int f[10];
     int i,j;
    // int tr[10][10];
     printf("enter le nombre des etats \n");
     scanf("%d",&netats);
     printf("enter le nombre des symboles \n");
     scanf("%d",&nsymboles);
     printf("\nenter les symbols\t");
 
     for(i=0; i<nsymboles; i++) 
     {
           printf("\n\n %d \t", i+1);
           printf("%c",c[i]=getch());
     }
 
     printf("\n\nenter le number des etats finaux\t");
     scanf("%d",&nfinales);
 
     for(i=0;i<nfinales;i++)
     {
          printf("\n\netat final %d : ",i+1);
          scanf("%d",&f[i]);
     }
 
     printf("-----------------------------------------------------------------------");
     printf("\n\ndefine transition rule as (initial state, input symbol ) = final state\n");
 
     for(i=0; i<nsymboles; i++)
    {
          for(j=0; j<netats; j++){
                  { printf("donner les etats:");
                   scanf("%d",&tr[i][j]);}}
     for(i=0; i<nsymboles; i++)
    {
          for(j=0; j<netats; j++){  
                    while(l=0);
               {printf("\n donner un etat");
               scanf("%d",&((tr[i][j])->e));
                // if(tr[i][j]->e==-1) return 0;
                 ((tr[i][j]))->next=*T;
                 *T=tr[i][j];
               printf("Voulez vous ajouter d'autres etats pour cette transition ? (oui/non)\n");
			   scanf("%s",condition1);
		    	l=strcmp(condition1,"non");
		    }
    }}
          while(l=0);  }    }
   /* for(i=0; i<nsymboles; i++)
          for(j=0; j<netats; j++)
                  tr[i][j]=T;
           do
			{
      for(i=0; i<nsymboles; i++)
       {
          for(j=0; j<netats; j++)
               {printf("\n(%d , %c ) = ",j,c[i]);
               scanf("%d",tr[i][j]->e);
			   tr[i][j]=tr[i][j]->next;
			    }}}
			while ((tr[i][j]!= 0) &&  l!=0);
			return (liste)T;}}*/
int main()
{
    char rep[3];
			int finale[1],i,nb;
			//liste k=construire();
			liste T=NULL;
			do
			{
                  construire(&T);
 
	         }
		while(strcmp(rep,"non")!=0);
			return 0;
}

[Bayard]

1) Ma remarque 2 n'est pas prise en compte, il n'y a pas de tableaux de structure en dur (const).

2)La variable

Code :

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

etat*tr[10][10]

est une variable locale. Elle sera donc perdue en sortant de la fonction.
Donc tout pointeur qui y réfère sera cassé.

3) S'il y a un tableaux structure déjà construit "en dur" (const), il n'y a pas besoin de fonction qui s'appelle construire.

[Médinoc]

Ça me paraît bizarre de gérer les états par une liste chaînée, surtout avec un tableau 2D de pointeurs pour les transitions.

Pour moi, dans un AFN, on gérerait plutôt un tableau fixe d'états, et un tableau de Booléens pour chaque transition (et donc, un tableau 2D de Booléens pour la liste de transitions un tableau 3D de Booléens pour chaque transition vu qu'il y a NB_ETATS*NB_SYMBOLES transitions).

[yonna]

Salut,
merci pour les remarques ,mais je vais essayer les listes chainées multiple voici les structure:

Code :

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

1
2
3
4
5
6
7
8
9
10
struct etat{
                  int e;
                  char s;
                  etat*next;
                  EA*suivant;
                  };
struct EA{
             int ea;
             EA * suivant;
             };

si vous avez des remarques n'hésitez pas pour m'aider à résoudre ce problème
cordialement .

[Médinoc]

Que signifie "EA" ?

[yonna]

Que signifie "EA" ?

EA est une structure des états arrivés pour que structure etat qui contient etat et le symbole pointe sur une liste des etats arrive par exemple :
[1|a|.]-->[1|.]->[2|.]->null et ainsi de suite

[Médinoc]

Si ta structure contient un état et un symbole, elle devrait s'appeler transition, pas etat.

[Sve@r]

merci pour les remarques ,mais je vais essayer les listes chainées multiple

Bonjour

Je sens que c'est pas super maitrisé...

voici la structure donnée par le prof :

Code c :

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

1
2
3
4
5
struct etat{
                                          int e;//e est le numero de etat enter 
                                          etat*next;//pointeur vers l'etat suivante
                                          };
                                      etat*tr[][];//un tableau de pointeur sur la structure

Ca m'étonnerait qu'un prof ait pu pondre ça. Ou alors c'était un prof de chimie, physique, français, maths, histoire, sport, biologie, bref tout sauf de C. Déjà d'une part parce que "etat" ce n'est pas un nom de type donc "etat*next" ça ne compilera pas (faudrait écrire struct etat *next) et un tableau de pointeurs n'a pas besoin d'être en deux dimensions (et cette ligne non plus ne compilera pas). Et je vois mal un prof conseiller une variable globale... et en plus avec un nom aussi peu représentatif !!!

voici les structure:

Code :

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

1
2
3
4
5
6
7
8
9
10
struct etat{
                  int e;
                  char s;
                  etat*next;
                  EA*suivant;
                  };
struct EA{
             int ea;
             EA * suivant;
             };

si vous avez des remarques n'hésitez pas pour m'aider à résoudre ce problème

Ben déjà, en dehors du problème de syntaxe, le compilo ne peut pas connaitre "EA*suivant" si la structure EA n'a pas été déclarée .
Ensuite si tu veux être à l'aise il te faut commencer par être méthodique et rigoureux et poser les bases avec des noms appropriés et ne pas mettre des noms comme "ea" d'un coté et "EA" de l'autre ou "next" d'un coté et "suivant" de l'autre (super la relecture !!!).
Donc déjà les noms tout en majuscules sont réservés aux macros. Ensuite, une structure se préfixe par un "s_" et un type par un "t_". Et certains vont même jusqu'à préfixer leurs pointeur par autant de "p" qu'il y a d'étoile (char ***pppTruc) mais bon perso je ne le fais pas donc je ne peux pas te dire de le faire...

Ainsi, tes structures pourraient être

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
typedef struct s_etatFini {
    int valeur;
    struct s_etatFini *next;
} t_etatFini;
 
typedef struct s_transition {
    int valeur;
    char symbole;
    struct s_transition *next;
    t_etatFini *etat;
} t_transition;

Maintenant tu as maintenant deux beaux types "t_etatFini" et "t_transition" disponibles pour tes variables "etatFini" et "transition" si tu as envie de les nommer ainsi. Ensuite donc poser tes algos, faire des dessins de tes listes sur papier, schématiser l'insertion et la suppression puis une fois tout ça bien carré, le découpage de ton code en fonctions te viendra bien plus facilement...