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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
|
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <time.h>
/* I. DECLARATIONS */
/* I.1. DECLARATION DES CONSTANTES RELATIVES AUX TAILLES DE TABLEAUX UTILISES */
#define MAX_LETTRES 30
#define MAX_MOTS 23000
/* I.2. DECLARATION DES STRUCTURES DE DONNEES IMBRIQUEES*/
struct mot {
char motdebase[MAX_LETTRES], mottrie[MAX_LETTRES];
int taille;
};
struct tableau
{
struct mot fiche [MAX_MOTS];
};
struct tab
{
struct tableau n[2];
};
/* I.3. DECLARATION DES FONCTIONS DE TRIS ET DE COMPARAISONS*/
void tri_extraction_lettres(char tab[MAX_LETTRES]);
void tri_shell_lettres(char tab[MAX_LETTRES]);
void tri_extraction_mots(struct tab *T, int nombre_mots, int id_fichier);
void tri_shell_mots(struct tab *T, int nombre_mots, int id_fichier);
int comparaisonoptimise(char mottrie1[], char mottrie2[],int taille1, int taille2);
/* Remarque : la fonction de comparaison basique est directement integree a la fonction analyse_du_fichier*/
/* I.4. DECLARATION DE NOS VARIABLES GLOBALES*/
int n1=0;
/* I.4.1. Les tableaux temps_tri et la variable temps_comparaison servent a stocker la valeur du clock(), avant et apres l'execution de la fonction associee*/
clock_t
temps_tri_lettres[2][2],
temps_tri_mots[2][2],
temps_comparaison[2];
/* I.4.2. Les tableaux duree_tri stockent la difference des tableaux temps_tri associes. Le type double permet la prise en charge des ms*/
double
duree_tri_lettres[2]={0},
duree_tri_mots[2]={0},
duree_comparaison=0;
/* II. FONCTION QUI ANALYSE LE FICHIER ET APPELLE LES FONCTIONS CITEES CI-DESSUS */
struct tab analyse_du_fichier (struct tab T,char nom_du_fichier[], int i)/**/
{
/* II.1. OUVERTURE, LECTURE, ANALYSE DU FICHIER, ET REMPLISSAGE DES TABLEAUX DE MOTS */
FILE *f ;
f=fopen(nom_du_fichier,"r");/*ouverture du fichier en lecture*/
if (f!=NULL)
{
int j=0,n=0,k=0,i2=0,m=0,n2=0,t=0,p=0,q=0,z=0;
char c='\0';/*variable qui sert a stocker les caracteres lus par le fgetc*/
char mm[MAX_LETTRES]="0",zz[MAX_LETTRES]="0"; /* variable qui servent pour faire mes fgets*/
/* Lecture du fichier et preparation du tableau*/
while ((c=fgetc(f))!=EOF) /* on lit le fichier tant qu'on a pas atteint la fin du fichier*/
{
if (isalpha(c)) /* isalpha(c) permet de savoir si le caractere considere est une lettre ou autre chose et si elle renvoie vrai c'est que le caractere est une lettre*/
{
c = tolower(c); /*tolower transforme chaque lettre en miniscule si necessaire*/
T.n[i-1].fiche[n].motdebase[k]=c; /*stockage de la lettre dans le premier case disponible*/
}
else
{
if (k > 1) /*k est superieure 1 seulement si le mot stocke contient au moins 2 caracteres*/
{
T.n[i-1].fiche[n].motdebase[k]='\0'; /*mise a la fin de chaque mot stocke un caractere de fin de liste*/
n++; /*incrementation du nombre de ligne du tableau*/
}
k=-1;/* on remet k a -1 pour remettre k a 0 car k est incremente juste apres en debut de boucle*/
}
k++;/*incrementation de la place de la letttre*/
}
if (k > 0) {
T.n[i-1].fiche[n].motdebase[k]='\0'; /*mise d'un caractere de fin de ligne lors de l'enregistrement du dernier mot*/
n++;/*incrementation du nombre de ligne*/
}
if (i==1)
{
n1=n;/* n1 correspond au nombre de mots stockes venant du fichier 1*/
for (p=0;p<n1;p++)
{
T.n[0].fiche[p].taille = strlen (T.n[0].fiche[p].motdebase); /* taille de chaque mot*/
/* appel de la fonction qui transforme les majuscules en miniscules*/
strcpy( T.n[0].fiche[p].mottrie , T.n[0].fiche[p].motdebase ); /* FONCTION DE DUPLICATION DE motdebase vers mottrie */
}
}
else if (i==2){
n2=n;/* n2 correspond au nombre de mots stockes venant du fichier 2*/
for (p=0;p<n2;p++)
{
T.n[1].fiche[p].taille = strlen (T.n[1].fiche[p].motdebase); /* taille de chaque mot*/
strcpy( T.n[1].fiche[p].mottrie , T.n[1].fiche[p].motdebase ); /* FONCTION DE DUPLICATION DE motdebase vers mottrie */
}
}
/* II.2. APPEL ET CHOIX DE LA FONCTION DE TRI DES MOTS */
temps_tri_mots[i-1][0]=clock();
puts(" [CHOIX DU TYPE DE TRI DES MOTS] Entrez :\n - 0 pour extraction \n - 1 pour shell");
fgets(mm,MAX_LETTRES,stdin);
m=atoi(mm);/* transformation de la chaine de caractere en un nombre*/
/*choix du tri pour le tri des mots*/
switch (m)
{
case(0): tri_extraction_mots(&T,n,(i-1));break;
case (1) : tri_shell_mots(&T,n,(i-1));break;
}
/* II.2.1. SUPRESSION DES DOUBLONS */
if (i==1)
{
for (j=(n1-1);j>0 ;j--)
{
if (strcmp(T.n[0].fiche[j].motdebase,T.n[0].fiche[j-1].motdebase)==0)
{
T.n[0].fiche[j].taille=0;
}
}
}
else {
for (j=(n2-1);j>0;j--)
{
if (strcmp(T.n[1].fiche[j].motdebase,T.n[1].fiche[j-1].motdebase)==0){
T.n[1].fiche[j].taille=0;
}
}
}
temps_tri_mots[i-1][1]=clock();
duree_tri_mots[i-1] = (double)(temps_tri_mots[i-1][1]-temps_tri_mots[i-1][0]) / CLOCKS_PER_SEC;
/* II.3. APPEL ET CHOIX DE LA FONCTION DE TRI DES LETTRES */
temps_tri_lettres[i-1][0]=clock();
puts(" [CHOIX DU TYPE DE TRI DES LETTRES] Entrez :\n - 0 pour extraction \n - 1 pour shell");
fgets(mm,MAX_LETTRES,stdin);/*saisie du choix*/
m=atoi(mm);/* transformation de la chaine de caractere en un nombre*/
printf("La liste contient %d mots\n\n", n);
/*choix du tri pour le tri des lettres*/
switch (m)
{
case (0): for (i2=0; i2<n; i2++){
tri_extraction_lettres(T.n[i-1].fiche[i2].mottrie); /* appel de la fonction de tri des lettres grace au tri shell*/
}; break;
case (1): for (i2=0; i2<n; i2++){
tri_shell_lettres(T.n[i-1].fiche[i2].mottrie); /* appel de la fonction de tri des lettres grace au tri par extraction*/
};break;
}
temps_tri_lettres[i-1][1]=clock();
duree_tri_lettres[i-1] = (double)(temps_tri_lettres[i-1][1]-temps_tri_lettres[i-1][0])/CLOCKS_PER_SEC;
/* II.4. APPEL ET CHOIX DE LA FONCTION DE COMPARAISON DES ANAGRAMMES + AFFICHAGE DES ANAGRAMMES*/
if (i==2)
/*on fait appel a la fonction de comparaison des anagrammes que si on a lu le deuxieme fichier*/
{
puts("\n [CHOIX DU TYPE DE COMPARAISON] Entrez :\n - 0 pour une comparaison bete \n - 1 pour une comparaison optimisee");
fgets(zz,MAX_LETTRES,stdin);
z=atoi(zz);
t=0;
printf("\n-----------");
printf("\n[ANAGRAMMES]\n");
temps_comparaison[0]=clock();
for (q=0;q<n1;q++)
{ if(T.n[0].fiche[q].taille!=0)
for (j=0;j<n2;j++) /*on compare tous les mots tries en eux*/
{
switch (z){
case (0) : if ( (T.n[0].fiche[q].taille!=0)
&& (T.n[1].fiche[j].taille!=0)
&& (strcmp(T.n[0].fiche[q].mottrie,T.n[1].fiche[j].mottrie)==0)
&& (strcmp(T.n[0].fiche[q].motdebase,T.n[1].fiche[j].motdebase)!=0)
/*on ecrit les anagrammes que si la taille des mots est differente de zero , que les mots tries sont les memes et que ce ne sont pas les memes mots de base*/
) {
printf("[%s <=> %s] ",
T.n[0].fiche[q].motdebase,
T.n[1].fiche[j].motdebase
);/* on affiche au fur et à mesure les anagrammes */
t++;/* on incremente t pour compter le nombre d'anagrammes*/
}; break;
case (1) : if ((comparaisonoptimise (T.n[0].fiche[q].mottrie,T.n[1].fiche[j].mottrie,T.n[0].fiche[q].taille,T.n[1].fiche[j].taille))==0
&& (T.n[0].fiche[q].taille!=0)
&& (T.n[1].fiche[j].taille!=0)
&& (strcmp(T.n[0].fiche[q].motdebase,T.n[1].fiche[j].motdebase)!=0)
/*on ecrit les anagrammes que si la tailles des mots est differente , que les mots tries sont les memes et que ceux ne sont pas les memes mots de base*/
)
{
printf("[%s <=> %s] ",
T.n[0].fiche[q].motdebase,
T.n[1].fiche[j].motdebase
);
/* on affiche au fur et à mesure les anagrammes */
t++;/* on incremente t pour compter le nombre d'anagrammes*/
};break;
}
}
}
temps_comparaison[1]=clock();
duree_comparaison = (double)(temps_comparaison[1]-temps_comparaison[0])/CLOCKS_PER_SEC;
/*II.4.1. AFFICHAGE DES INFORMATIONS */
printf("\n--------------");
printf("\n[STATISTIQUES]");
printf("\nNombre d'anagrammes : %d",t);/*affichage du nombre d'anagrammes*/
printf("\n\nTemps pour le fichier 1");
printf("\n- Temps de tri des mots : %.3lfs",duree_tri_mots[0]);
printf("\n- Temps de tri des lettres : %.3lfs",duree_tri_lettres[1]);
printf("\nTemps pour le fichier 2");
printf("\n- Temps de tri des mots : %.3lfs",duree_tri_mots[1]);
printf("\n- Temps de tri des lettres : %.3lfs",duree_tri_lettres[1]);
printf("\n\nTemps totaux");
printf("\n- Temps de tri des mots : %.3lfs",duree_tri_mots[0]+duree_tri_mots[1]);
printf("\n- Temps de tri des lettres : %.3lfs",duree_tri_lettres[0]+duree_tri_lettres[1]);
printf("\n- Temps de comparaisons : %.3lfs",duree_comparaison);
printf("\n- Temps total d'execution du programme : %.3lfs",duree_tri_mots[0]+duree_tri_mots[1]+duree_tri_lettres[0]+duree_tri_lettres[1]+duree_comparaison);
printf("\n");
}
}
fclose(f);
return T;
}
/* III. DEFINITIONS DES FONCTIONS DE TRIS ET DE COMPARAISONS */
/* III.1. TRIS PAR EXTRACTION */
void tri_extraction_lettres(char tab[]) {
int i=0;
int i2=0;
char aux;
int count=1;
int taille=strlen(tab);
for(i=0; i<taille; i++) {
for(i2=count; i2<taille; i2++) {
if(tab[i2]<tab[i]) {
aux=tab[i];
tab[i]=tab[i2];
tab[i2]=aux;
}
}
count++;
}
}
void tri_extraction_mots(struct tab *T, int nombre_mots, int id_fichier) {
int i=0;
int i2=1;
/*On definit un tableau de buffer pour les mots tries, et un pour les mots basiques*/
char aux[MAX_LETTRES];
char aux2[MAX_LETTRES];
/* Cette variable auxiliaire sert a stocker la longeur de la chaine de caractere de chaque mot */
int aux3;
int taille=nombre_mots;
for(i=0; i<taille; i++) {
for(i2=i+1; i2<taille; i2++) {
if( strcmp((*T).n[id_fichier].fiche[i2].mottrie,(*T).n[id_fichier].fiche[i].mottrie)<(0) ) {
strcpy( aux,(*T).n[id_fichier].fiche[i].mottrie );
strcpy( aux2,(*T).n[id_fichier].fiche[i].motdebase );/*On realise la meme operation avec les mots de bases pour garder une correspondance*/
aux3=(*T).n[id_fichier].fiche[i].taille;
strcpy( (*T).n[id_fichier].fiche[i].mottrie,(*T).n[id_fichier].fiche[i2].mottrie );
strcpy( (*T).n[id_fichier].fiche[i].motdebase,(*T).n[id_fichier].fiche[i2].motdebase );/*Meme commentaire que le precedent*/
(*T).n[id_fichier].fiche[i].taille=(*T).n[id_fichier].fiche[i2].taille;
strcpy( (*T).n[id_fichier].fiche[i2].mottrie,aux );
strcpy( (*T).n[id_fichier].fiche[i2].motdebase,aux2 );
(*T).n[id_fichier].fiche[i2].taille=aux3;
}
}
}
}
/* III.2. TRIS DE SHELL */
void tri_shell_lettres(char tab[MAX_LETTRES]) {
int h=1;
int aux=0;
int i=0;
int j=0;
do {
h=3*h+1;
} while (h<=strlen(tab));
do {
h=h/3;
for (i=h;i<strlen(tab);i++) {
aux = tab [i];
j=i;
while (j>=h && tab[j-h]>= aux) {
tab [j] = tab[j-h];
j=j-h;
}
tab[j]=aux;
}
} while (h!=1);
}
void tri_shell_mots(struct tab *T, int nombre_mots, int id_fichier) {
int h, i,j;
h = 0;
/*On definit un tableau de buffer pour les mots tries, et un pour les mots basiques*/
char aux[MAX_LETTRES];
char aux2[MAX_LETTRES];
int aux3;
/* Calcul du pas */
while(h<nombre_mots)
{
h = 3*h+1;
}
while(h!=0) /* tant que le pas est > 0 */
{
h = h/3;
for(i=h; i<nombre_mots; i++)
{
strcpy(aux,(*T).n[id_fichier].fiche[i].mottrie);
strcpy(aux2,(*T).n[id_fichier].fiche[i].motdebase);/*On realise la meme operation avec les mots de bases pour garder une correspondance*/
aux3=(*T).n[id_fichier].fiche[i].taille; /* Cette variable auxiliaire sert a stocker la longeur de la chaine de caractere de chaque mot */
j = i;
while( (j>(h-1)) && (strcmp((*T).n[id_fichier].fiche[j-h].mottrie,aux)>0) )
{ /* echange des valeurs */
strcpy( (*T).n[id_fichier].fiche[j].mottrie , (*T).n[id_fichier].fiche[j-h].mottrie );
strcpy( (*T).n[id_fichier].fiche[j].motdebase , (*T).n[id_fichier].fiche[j-h].motdebase );/*On realise la meme operation avec les mots de bases pour garder une correspondance*/
(*T).n[id_fichier].fiche[j].taille=(*T).n[id_fichier].fiche[j-h].taille;
j = j-h;
}
strcpy( (*T).n[id_fichier].fiche[j].mottrie , aux );
strcpy( (*T).n[id_fichier].fiche[j].motdebase , aux2 );
(*T).n[id_fichier].fiche[j].taille=aux3;
}
}
}
/* III.3. FONCTION DE COMPARAISON OPTIMISEE */
int comparaisonoptimise(char mottrie1[40], char mottrie2[40],int taille1, int taille2)
{
int i;
if (taille1==taille2) /*ce sont des anagrammes que si ils ont le même nombre de lettre*/
{
for (i=taille1-1;i>=0;i--) /*je commence par la derniere lettre parce que statistiquement les dernieres de l'alphabet sont les plus rares donc on a plus de chances de tomber sur des lettres differentes*/
{
if (mottrie1[i]==mottrie2[i])/* je compare chaque lettre une a une*/
{
}
else{
return 42;/*je retourne 42 si ce ne sont pas des anagrammes*/
}
}
return 0;/*je retourne 0 c'est-a-dire que les anagrammes sont identiques si toutes les lettres sont identiques et qu'il y a le même nombre de lettres*/
}
else {return 42;}/*je retourne 42 si ce ne sont pas des anagrammes*/
}
/* IV. FONCTION MAIN, TRANSMET LES PARAMETRES PASSES EN ARGUMENTS PAR L'UTILISATEUR A LA FONCTION analyse_du_fichier*/
int main (int argc, char **argv)
{
int i;
struct tab T;
if (argc!=3) /* verifie que le nombre d'arguments est egale a 3, pour savoir si ce qui est rentre en ligne de commande correspond a ce que l'on souhaite*/
{
printf("Erreur de syntaxe. Veuillez fournir vos deux fichiers en parametres : %s fichier1 fichier2\n",argv[0]); /* donne le prototype du lancement de la fonction*/
return -1; /* retourne -1 si le prototype n'est pas bon */
}
else
{
for (i=1;i<=2;i++)
{
printf("\nNom du fichier en cours : ");
puts(argv[i]);
printf("\n");
T = analyse_du_fichier(T,argv[i],i); /* je lance l'analyse des deux fichiers */
}
return 0;/*retourne 0 pour montrer que tout c'est bien passe dans le programme*/
}
} |
Problème compilation code
Répondre avec citation
Partager