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
} |
Partager