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
| #include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
typedef struct sommet
{
char * mot;
struct sommet * fg;
struct sommet * fd;
} Sommet, * Abr;
typedef struct maillon
{
int lg;
Abr arbre;
struct maillon* suiv;
}Maillon, * Foret;
//declaration des fonctions
Abr nouveausmt(const char * s)
{
Abr p; //équivaut à Sommet*p
p=(Abr)malloc(sizeof(Sommet));
//on reserve une autre espace mémoire pour mot puisqu'elle pointe vers une costante donc sa valeur pointée sera non modifiable
p->mot=(char *)malloc(strlen(s)*sizeof(char));
strcpy(p->mot,s);
p->fg=p->fd=NULL;
return p;
}
Foret nouveaumaillon(int x,Abr r)
{
Foret p; // équivaut à Maillon *p
p=(Foret)malloc(sizeof(Maillon));
p->lg = x;
p->arbre=r;
p->suiv=NULL;
return p;
}
int cherche(const char * s,Abr r) //cette fonction ne sert à rien
{
Abr p;//en C on n'a pas le type booléen,c'est pour ça on utilise le type int,0 pour faux (n'éxiste pas),et autrement pour vrai (existe)
if(r==NULL) //arbre vide
return 0;
else
if(strlen(p->mot)!=strlen(s))//cela va diminuer le temps d'éxécution si la taille de l'arbre est grande
return 0;
else
{
p=r;
while(p!=NULL)
if(strcmp(p->mot,s)==0)
return 1;
else
if((strcmp(p->mot,s))>0)
p=p->fg;
else
p=p->fd;
if(p==NULL)
return 0;
}
}
void insere(const char * s,Abr * r) //r est passé par adresse
{
if (r==NULL)
*r=nouveausmt(s);
else
if(strcmp((*r)->mot,s)==0)
printf("le sommet existe deja\n");
else
if(strcmp((*r)->mot,s)>0)
insere(s,&(*r)->fg);
else
insere(s,&(*r)->fd);
}
void insereforet(const char * s,Foret * f) //f est passé par adresse
{
Foret p,ptr,pred;
int n=strlen(s);
if(*f==NULL) //foret vide
*f=nouveaumaillon(n,nouveausmt(s));
else
{
p=*f;
while(p->lg<strlen(s)&& p!=NULL)
{
pred=p;
p=p->suiv;
}
if(p!=NULL)
if(p->lg==n)
insere(s,&p->arbre);
else //(p->lg)>(strlen(s))
{
ptr=nouveaumaillon(n,nouveausmt(s));
if(p==*f) //insertion d'un nouveau maillon au début
{
ptr->suiv=*f;
*f=ptr;
}
else //insertion d'un nouveau maillon au milieu
{
pred->suiv=ptr;
ptr->suiv=p;
}
}
else //p==NULL ça veut dire insertion à la fin
pred->suiv=nouveaumaillon(n,nouveausmt(s));
}
}
void imprimeabr(Abr r)
{
if(r!=NULL)
{
printf("%s ",r->mot); //retour chariot,on laisse 3 distance entre les mots
imprimeabr(r->fg);
imprimeabr(r->fg);
}
}
void imprimeforet(Foret f)
{
Foret p=f;
while(p!=NULL)
{
printf("mots de longeur %d: \n",p->lg); //retour chariot,on laisse 3 distance entre les mots
imprimeabr(p->arbre);
p=p->suiv;
}
}
//programme principale
main()
{
int i;
char s[7];
Foret tete=NULL;
for (i=0;i<10;i++) {
printf("entre le %d eme mot :\n ",i);
scanf("%s",s);
insereforet(s,&tete);
}
imprimeforet(tete);
printf("\n");
getch(); //arreter l'éxécution
} |
