vendredi 12 octobre 2007 : pointeurs et passage d'arguments entiers
vendredi 19 octobre 2007 : grève des transports
vendredi 26 octobre 2007 : pointeurs et tableaux
vendredi 2 novembre 2007 : tri fusion
vendredi 9 novembre 2007 : pointeurs et structures : généalogie
vendredi 16 novembre 2007 : grève des transports
vendredi 23 novembre 2007 : généalogie suite, cousins germains
vendredi 30 novembre 2007 : listes chaînées
vendredi 7 décembre 2007 : listes chaînées
vendredi 14 décembre 2007 : tri fusion d'une liste chaînée
vendredi 21 décembre 2007 : arbre binaire de recherche
vendredi 11 janvier 2008 : arbre binaire de recherche équilibré
vendredi 18 janvier 2008 :
suivant sommairevendredi 12 octobre 2007 : pointeurs et passage d'arguments entiers
cours
Compiler et exécuter un programme C
Voici comment sur un ordinateur avec Windows et gcc vous pouvez compiler
et exécuter des programmes en C que vous écrivez avec le bloc-note :
Ouvrez d'abord une fenêtre «invite de commandes».
Pour cela vous avez le choix entre deux menus :
- Démarrer/Programmes/accessoires/Invite de commandes
- Démarrer/Exécuter en tapant cmd
Dans la fenêtre qui apparaît vous pouvez alors taper les commandes suivantes
<![CDATA[>cd \Dev-C++
>md dupont
>cd dupont
>notepad minmax.c
>\Dev-C++\bin\gcc -Wall -g minmax.c
>a
>\Dev-C++\bin\gdb a.exe
>dir]]>
Les trois premières commandes créent le dossier C:\Dev-Cpp\dupont et vous
placent dedans.
La commande suivante demande au bloc-note de créer ou de modifier le fichier
C:\Dev-C++\dupont\minmax.c
dans le quel vous allez taper un programme en C.
La commande \Dev-C++\bin\gcc -Wall -g minmax.c
demande à gcc (Gnu C Compiler c'est-à-dire le Compilateur C Gnu)
de compiler le programme minmax.c c'est-à-dire de le traduire en un programme,
appelé a.exe, écrit en langage machine et donc directement exécutable par l'ordinateur.
La commande a demande d'exécuter le programme a.exe que le compilateur vient de fabriquer.
La commande \Dev-C++\bin\gdb a.exe
demande à gdb (Gnu DeBugger c'est-à-dire le débogueur gnu) de vous aider à trouver les
erreurs dans le programme a.exe
Pour qu'il vous aide efficacement il faut absolument avoir exécuté gcc avec l'option -g
sinon le débogueur ne connaîtra pas les noms des variables de votre programme.
La commande dir permet de voir les différents fichiers présents dans votre répertoire.
Normalement il doit y avoir minmax.c qui fait environ 3 à 5 ko et a.exe qui fait environ
15 ko.
Il est plus simple de ne jamais fermer la fenêtre du bloc-note.
A chaque fois que vous voulez tester les modifications que vous avez apportées à minmax.c
vous devez le sauver, par ^S puis repasser dans l'invite de commandes et relancer
gcc puis a. Pour ce faire vous n'avez pas besoin de retaper toute la commande.
Vous pouvez la rappeler grâce à la touche «flèche vers le haut».
Si votre programme boucle indéfiniment vous pouvez l'arrêter en tapant ^C.
calcul de la surface d'un rectangle par une fonction
<![CDATA[#include<stdio.h>
int surface(int largeur,int longueur)
{ return largeur*longueur;}
int main()
{ printf("%d\n",surface(6,7));
return 0;
}]]>
calcul de la surface d'un rectangle par une procédure
<![CDATA[#include<stdio.h>
void calculsurface(int largeur,int longueur,int *surface)
{ *surface=largeur*longueur;}
int main()
{ int lar=6, lon=7, sur;
calculsurface(lar,lon,&sur);
printf("Le rectangle de largeur %d et de longueur %d a pour surface %d\n",lar,lon,sur);
return 0;
}]]>
TD
Compléter le programme :<![CDATA[#include<stdio.h>
int max2(int a, int b);
int max3(int a, int b, int c);
int max4(int a, int b, int c, int d);
int min2(int a, int b);
int min3(int a, int b, int c);
int min4(int a, int b, int c, int d);
int med3(int a, int b, int c);
void tri2(int *a, int *b);
void tri3(int *a, int *b, int *c);
void tri4(int *a, int *b, int *c, int *d);
void tri5(int *a, int *b, int *c, int *d, int *e);
]]>solution :<![CDATA[#include<stdio.h>
int max2(int a, int b)
{ if(a<b) return b;
else return a;
}
int max3(int a, int b, int c)
{ return max2(a,max2(b,c));
}
int max4(int a, int b, int c, int d)
{ return max2(max2(a,b),max2(c,d));
}
int min2(int a, int b)
{ if(a>b) return b;
else return a;
}
int min3(int a, int b, int c)
{ return min2(a,min2(b,c));
}
int min4(int a, int b, int c, int d)
{ return min2(min2(a,b),min2(c,d));
}
int med3(int a, int b, int c)
{ return a+b+c-max3(a,b,c)-min3(a,b,c);
}
void ech2(int *a, int *b)
{ int c=*a;
*a=*b;
*b=c;
}
void tri2(int *a, int *b)
{ if(*a>*b) ech2(a,b);
}
void tri3(int *a, int *b, int *c)
{ tri2(a,b); // *b=max(*a,*b)
tri2(b,c); // *c=max(*a,*b,*c)
tri2(a,b); // *a<*b<*c
}
void tri4(int *a, int *b, int *c, int *d)
{ tri2(a,b); tri2(c,d); // *a=min(*a,*b) *c=min(*c,*d) *b=max(*a,*b) *d=max(*c,*d)
tri2(a,c); tri2(b,d); // *a=min(*a,*b, *c,*d) *d=max(*a,*b, *c,*d)
tri2(b,c); // *a<*b<*c<*d
}
void ins4(int *a, int *b, int *c, int *d) // en entrée *a<*b<*d en sortie *a<*b<*c<*d
{ if(*c>*b) tri2(c,d); // avant l'appel de tri2 : *a<*b<min(*c,*d)
else ech2(b,c),tri2(a,b); // avant l'appel de tri2 : max(*a,*b)<*c<*d
}
void tri4bis(int *a, int *b, int *c, int *d)
{ tri3(a,b,d); // *a<*b<*d
ins4(a,b,c,d); // *a<*b<*c<*d
}
void tri5(int *a, int *b, int *c, int *d, int *e)
{ tri2(a,b); // *a<*b
tri2(c,e); // *c<*e
if(*b>*e) ech2(a,c), ech2(b,e); // *a<*b<*e et *c<*e
ins4(a,b,d,e); // *a<*b<*d<*e et *c<ancien(*e)<*e
ins4(a,b,c,d); // *a<*b<*c<*d<*e
}
int x;
int aleat() { x=5*x+1; return (x/11)&63; }
int main()
{ int a,b,c,d,e;
printf("Donnez un nombre : ");
scanf("%d",&x);
a=aleat();
b=aleat();
c=aleat();
d=aleat();
e=aleat();
printf("%d %d %d %d %d\n",a,b,c,d,e);
printf("%d %d %d\n",max2(a,b),max3(c,d,e),max4(a,b,c,d));
printf("%d %d %d\n",min2(a,b),min3(c,d,e),min4(a,b,c,d));
printf("%d\n", med3(c,d,e));
tri5(&a,&b,&c,&d,&e);
printf("%d %d %d %d %d\n",a,b,c,d,e);
return 0;
}]]>
suivant précédent sommairevendredi 19 octobre 2007 : grève des transports
suivant précédent sommairevendredi 26 octobre 2007 : pointeurs et tableaux
<![CDATA[#include<stdio.h>
int main()
{ int a, b, *x, *y;
a=3; // 3
b=4; // 3 4
x=&a; // 3 4 &a
y=x; // 3 4 &a &a
*x=5; // 5 4 &a &a *x=*&a=a =5
(*y)++; // 6 4 &a &a (*&a)++ a++ a=a+1=5+1=6
printf("%d %d %d %d\n",a,b,*x,*y); // a=6 b=4 *x=*&a=a=6 *y=*&a=a=6
return 0;
}]]>
<![CDATA[#include<stdio.h>
int main()
{ int a=1, b=2, c=3, *x=&b, *y=x, *z=&c;
a++; // 2 2 3 &b &b &c
*z+=*x; // 2 2 5 &b &b &c c+=b c=b+c=2+3=5
*x+=a; // 2 4 5 &b &b &c b+=a b=a+b=2+2=4
a+=a+b+c; // 15 4 5 &b &b &c a+=2+4+5=13 a=2+13=15
printf("%d %d %d %d %d %d\n",a,b,c,*x,*y,*z); // a=15 b=4 c=5 *x=*&b=b=4 *y=*&b=b=4 *z=*&c=c=5
return 0;
}]]>
<![CDATA[#include<stdio.h>
int main()
{ int t[3],*x; // t[0] t[1] t[2] x
x=t; // t
*x=3; // 3 t
x++; // 3 t+1
*x=2; // 3 2 t+1
t[2]=4; // 3 2 4 t+1
x[1]+=2; // 3 2 6 t+1 x[1]=*(x+1)=*(t+1+1)=*(t+2)=t[2]+=2 t[2]=4+2=6
printf("%d %d %d\n",t[0],t[1],t[2]);
return 0;
}]]>
TD
<![CDATA[#include<stdio.h>
void afft(int n,int t[])
{ int i;
for(i=0;i<n;i++) printf("%d ",t[i]);
printf("\n");
}
int somt(int n,int t[])
{ int i, s=0;
for(i=0;i<n;i++) s+=t[i];
return s;
}
int maxt(int n,int t[])
{ int i, m=t[0];
for(i=1;i<n;i++) if(m<t[i]) m=t[i];
return m;
}
void tri(int n,int t[])
{ int i,j, x;
for(i=0;i<n;i++) for(j=i+1;j<n;j++) if(t[i]>t[j]) x=t[i], t[i]=t[j], t[j]=x;
}
int main()
{ int i,t[10];
for(i=0;i<10;i++) t[i]=/*3*i+1*/ i*(10-i);
afft(10,t);
printf("La somme vaut %d\n",somt(10,t));
printf("Le plus grand élément est %d\n",maxt(10,t));
tri(10,t);
afft(10,t);
return 0;
}]]>
<![CDATA[0 9 16 21 24 25 24 21 16 9
La somme vaut 165
Le plus grand élément est 25
0 9 9 16 16 21 21 24 24 25}]]>
suivant précédent sommairevendredi 2 novembre 2007 : tri fusion
<![CDATA[
void fusion(int n, int m, int t[], int u[], int v[])
{ while(n && m) if(t[n-1]<u[m-1]) n--, v[n+m]=t[n];
else m--, v[n+m]=u[m];
while(n) n--, v[n]=t[n];
while(m) m--, v[m]=u[m];
}
void trifusion(int n, int t[n])
{ if(n>1)
{ int i, m=n/2, u[n];
trifusion(m ,t );
trifusion(n-m,t+m);
fusion(m,n-m,t,t+m,u);
for(i=0;i<n;i++) t[i]=u[i];
}
}]]>
suivant précédent sommairevendredi 9 novembre 2007 : pointeurs et structures : généalogie
<![CDATA[#include<stdio.h>
typedef struct personne personne;
struct personne {char nom[21], prenom[21], sexe;
int age;
personne *pere, *mere, *conjoint, *enfant, *frere;};
void affnom(const personne *p)
{ printf("%s %s\n",p->prenom,p->nom);
}
void affpersonne(const personne *p)
{ personne *f;
printf("nom : %s\n",p->nom);
printf("prenom : %s\n",p->prenom);
printf("ne en : %d\n",p->age);
printf("sexe : %c\n",p->sexe);
if(p->pere ) printf("pere : "), affnom(p->pere);
if(p->mere ) printf("mere : "), affnom(p->mere);
if(p->conjoint) printf("conjoint : "), affnom(p->conjoint);
for(f=p->enfant;f;f=f->frere) printf("enfant : "), affnom(f);
}
void affgrandsparents(const personne *p)
{ printf("Voici les grands parents de "), affnom(p);
if(p->pere && p->pere->pere) printf("grand-pere paternel : "), affnom(p->pere->pere);
if(p->pere && p->pere->mere) printf("grand-mere paternelle : "), affnom(p->pere->mere);
if(p->mere && p->mere->pere) printf("grand-pere maternel : "), affnom(p->mere->pere);
if(p->mere && p->mere->mere) printf("grand-mere maternelle : "), affnom(p->mere->mere);
}
void affpetitsenfants(const personne *p)
{ personne *f, *g;
printf("Voici les petits enfants de "), affnom(p);
for(f=p->enfant;f;f=f->frere) // f décrit l'ensemble de tous les enfants de p
for(g=f->enfant;g;g=g->frere) affnom(g); // g décrit l'ensemble de tous les enfants de f
}
void affcousinsgermains(const personne *p)
{ personne *m, *g, *t, *c;
int im;
printf("Voici les cousins germains de "), affnom(p);
for(im=0;im<2;im++) if(m=im?p->mere:p->pere,m) // m est le père (im=0) ou la mère (im=1) de p
if(g=m->mere?m->mere:m->pere,g) // g est un des parents de m
for(t=g->enfant;t;t=t->frere) if(t!=m) // t décrit l'ensemble des enfants de g. On ne garde que les frères et soeur de m (t!=m)
for(c=t->enfant;c;c=c->frere) // c décrit l'ensemble des enfants de t.
affnom(c);
}
void affdescendance(const personne *p,int m)
{ printf("%*s",m,""); affnom(p);
for(p=p->enfant;p;p=p->frere) affdescendance(p,m+4);
}
int main()
{ personne
alphonse ={"Pierre" ,"Alphonse" ,'P',1900,0 ,0 ,0 ,0,0 },
juliette ={"Picart" ,"Juliette" ,'F',1900,0 ,0 ,&alphonse ,0,0 },
georges ={"Cailliez" ,"Georges" ,'M',1900,0 ,0 ,0 ,0,0 },
jeanne ={"Villeval" ,"Jeanne" ,'F',1900,0 ,0 ,&georges ,0,0 },
andre ={"Pierre" ,"Andre" ,'M',1927,0 ,0 ,0 ,0,0 },
jean_marie={"Cailliez" ,"Jean-Marie",'M',1930,&georges ,&jeanne ,0 ,0,0 },
georgette ={"Cailliez" ,"Georgette" ,'F',1928,&georges ,&jeanne ,&andre ,0,&jean_marie},
annie ={"Chapiteau","Annie" ,'F',1940,0 ,0 ,0 ,0,0 },
jean ={"Colin" ,"Jean" ,'M',1940,0 ,0 ,&annie ,0,0 },
frederique={"Colin" ,"Frederique",'F',1961,&jean ,&annie ,0 ,0,0 },
laurent ={"Pierre" ,"Laurent" ,'M',1958,&andre ,&georgette ,0 ,0,0 },
bruno ={"Pierre" ,"Bruno" ,'M',1956,&andre ,&georgette ,&frederique,0,&laurent },
marion ={"Pierre" ,"Marion" ,'F',1991,&bruno ,&frederique,0 ,0,0 },
maurice ={"Bouvet" ,"Maurice" ,'M',1957,&jean_marie,0 ,0 ,0,0 },
francoise ={"Bouvet" ,"Francoise" ,'F',1955,&jean_marie,0 ,0 ,0,&maurice };
alphonse .conjoint=&juliette;
georges .conjoint=&jeanne;
andre .conjoint=&georgette;
frederique.conjoint=&bruno;
juliette .enfant=alphonse.enfant=&andre;
jeanne .enfant=georges .enfant=&georgette;
georgette .enfant=andre .enfant=&bruno;
annie .enfant=jean .enfant=&frederique;
frederique.enfant=bruno .enfant=&marion;
jean_marie.enfant=&francoise;
affpersonne(&bruno);
affgrandsparents(&marion);
affpetitsenfants(&juliette);
affcousinsgermains(&bruno);
affdescendance(&jeanne,0);
return 0;
}]]>
suivant précédent sommairevendredi 16 novembre 2007 : grève des transports
suivant précédent sommairevendredi 23 novembre 2007 : généalogie suite, cousins germains
suivant précédent sommairevendredi 30 novembre 2007 : listes chaînées
suivant précédent sommairevendredi 7 décembre 2007 : listes chaînées
déclaration et affichage d'une liste chaînée
<![CDATA[#include<stdio.h>
#include<stdlib.h>
typedef struct chainon *liste;
struct chainon {int v; liste suite;};
void aff(liste a)
{ for(;a;a=a->suite) printf("%d ",a->v);
printf("\n");
}]]>
Insertion en tête de liste
<![CDATA[liste inseretete(int x,liste l)
{ liste a=malloc(sizeof(*a));
a->v=x;
a->suite=l;
return a;
}
void inserete(int x,liste *ll)
{ liste a=malloc(sizeof(*a));
a->v=x;
a->suite=*ll;
*ll=a
}]]>
Insertion en queue de liste chaînée
<![CDATA[liste inserequeuerec(liste l,int x)
{ if(!l) return inseretete(l,x);
l->suite=inserequeue(l->suite,x);
return l;
}
void inserequerec(liste *ll,int x)
{ if(!*ll) inserete(ll,x);
else inserequerec(&(*ll)->suite,x);
}
void inserequeite(liste *ll,int x)
{ while(*ll) ll=&(*ll)->suite;
inserete(ll,x);
}]]>
Insertion dans une liste triée
<![CDATA[liste inseretrie(liste l,int x)
{ if(!l || x<l->v) return inseretete(l,x);
l->suite=inseretrie(l->suite,x);
return l;
}
int main()
{ liste l=inseretete(4,inseretete(7,inseretete(5,0)));
int i;
aff(l);
l=inseretete(2,l); aff(l);
inserete(8,&l); aff(l);
l=inserequeuerec(l,6); aff(l);
inserequerec(&l,3); aff(l);
inserequeite(&l,9); aff(l);
l=0;
for(i=0;i<10;i++) l=inseretrie(l,3*i%10), aff(l);
return 0;
}]]>
suivant précédent sommairevendredi 14 décembre 2007 : tri fusion d'une liste chaînée
<![CDATA[#include<stdio.h>
#include<stdlib.h>
typedef struct chainon *liste;
struct chainon {int v; liste suite;};
void aff(liste a)
{ for(;a;a=a->suite) printf("%d ",a->v);
printf("\n");
}
liste nouveauchainon(int v, liste suite)
{ liste a=malloc(sizeof(*a));
a->v=v;
a->suite=suite;
return a;
}
liste fusion(liste a,liste b)
{ return !a ? b :
!b ? a :
a->v<b->v ? a->suite=fusion(a->suite,b),a :
(b->suite=fusion(b->suite,a),b);
}
liste trifusion(liste l)
{ liste l1=0, l2=0;
while(l)
{ liste p=l; l=p->suite;
p->suite=l1, l1=l2, l2=p;
}
return l1 ? fusion(trifusion(l1),trifusion(l2)) : l2;
}
int main()
{ liste l=0;
int i;
for(i=0;i<10;i++) l=nouveauchainon(i*3%10,l);
aff(l);
l=trifusion(l);
aff(l);
return 0;
}]]>
suivant précédent sommairevendredi 21 décembre 2007 : arbre binaire de recherche
<![CDATA[#include<stdio.h>
#include<stdlib.h>
typedef int element;
typedef struct noeud *abr;
struct noeud {element cle;abr fg,fd;};
abr nouveaunoeud(abr fg,element cle,abr fd)
{ abr a=malloc(sizeof(*a));
a->fg=fg;
a->fd=fd;
a->cle=cle;
return a;
}
int c;
abr insere(element x,abr a)
{ c++;
if(!a) return nouveaunoeud(0,x,0);
if(x==a->cle) return a;
if(x<a->cle) a->fg=insere(x,a->fg);
else a->fd=insere(x,a->fd);
return a;
}
void insere2(element x,abr *aa)
{ if(!*aa) *aa=nouveaunoeud(0,x,0); else
if(x==(*aa)->cle) ; else
insere2(x,x<(*aa)->cle?&(*aa)->fg:&(*aa)->fd);
}
void insere3(element x,abr *aa)
{ for(;*aa;aa=x<(*aa)->cle?&(*aa)->fg:&(*aa)->fd) if(x==(*aa)->cle) return;
*aa=nouveaunoeud(0,x,0);
}
abr enleve(element x,abr a)
{ if(!a) return a;
if(x<a->cle) return a->fg=enleve(x,a->fg),a;
if(x>a->cle) return a->fd=enleve(x,a->fd),a;
if(!a->fd) {abr b=a->fg; free(a); return b;}
{ abr b=a->fd;
while(b->fg) b=b->fg;
a->fd=enleve(a->cle=b->cle,a->fd);
return a;
}
}
void aff(abr a) {for(;a;a=a->fd) aff(a->fg), printf("%d ",a->cle);}
void affln(abr a) {aff(a), printf("\n");}
int main()
{ int i,j,x;
abr a=0;
for(i=0;i<10;i++) a=insere(i*3%10,a), affln(a);
for(i=0;i<10;i++) a=enleve(i*3%10,a), affln(a);
for(i=0;i<10;i++) insere2(i*3%10,&a), affln(a);
for(i=0;i<10;i++) a=enleve(i*3%10,a), affln(a);
for(i=0;i<10;i++) insere3(i*3%10,&a), affln(a);
for(i=0;i<10;i++) a=enleve(i*3%10,a), affln(a);
i=x=c=0;
for(j=10;j<=10000;j*=10)
{ for(;i<j;i++) x=x*37+1, a=insere(x%100001,a);
printf("%6d appels à insere pour un arbre de taille %d\n",c,i);
}
return 0;
}]]>
Ldernières lignes affichées par le programme précédent sont :
<![CDATA[ 32 appels à insere pour un arbre de taille 10
760 appels à insere pour un arbre de taille 100
11999 appels à insere pour un arbre de taille 1000
165728 appels à insere pour un arbre de taille 10000]]>
suivant précédent sommairevendredi 11 janvier 2008 : arbre binaire de recherche équilibré
Dans le programme suivant,
un arbre binaire de recherche est «équilibré» si la taille d'un sous-arbre n'est jamais plus grande que la taille de son oncle.
La taille d'un arbre est le nombre sous-arbres vides (feuilles) qu'il contient. C'est un de plus que son nombre de noeuds (ou de clés).
L'arbre vide (la feuille) n'est pas représenté par un pointeur nul, mais par vide qui est un pointeur sur un noeud particulier
qui a pour taille 1 et pour fils lui-même. De cette façon on ne craint plus de traverser un pointeur nul et on peut écrire
a->fd->fd->taille au lieu de a && a->fd && a->fd->fd ? a->fd->fd->taille : 1.
Cela évite donc beaucoup de tests.
<![CDATA[#include<stdio.h>
#include<stdlib.h>
typedef int element;
typedef struct noeud *abr;
struct noeud {element cle;int taille;abr fg,fd;} vide[1]={{0,1,vide,vide}};
abr reequi(abr a); // prototype nécessaire pour la récursivité croisée : reequi() appelle droite() et gauche() qui appellent reequi().
abr droite(abr a) // rotation simple à droite
{ abr b=a->fg; // a b a et b sont des noeuds.
a->fg=b->fd; // b Z --> X a X, Y et Z sont des arbres éventuellement vides. a
b->fd=reequi(a); // X Y Y Z On appelle reequi() sur le nouveau sous arbre Y Z
return b; // On a fait une permutation circulaire de 3 pointeurs : fils gauche de a, fils droit de b, arbre complet.
}
abr gauche(abr a) // rotation simple à gauche
{ abr b=a->fd; // a b a et b sont des noeuds.
a->fd=b->fg; // Z b --> a X X, Y et Z sont des arbres éventuellement vides. a
b->fg=reequi(a); // Y X Z Y On appelle reequi() sur le nouveau sous arbre Y Z
return b; // On a fait une permutation circulaire de 3 pointeurs : fils droit de a, fils gauche de b, arbre complet.
}
abr reequi(abr a) // Arrange un arbre non équilibré et dont la taille de la racine n'est pas à jour, mais dont les deux fils sont équilibrés.
{ if(a==vide) return a; // Il ne faut pas recalculer la taille de l'arbre vide (1!=1+1)
if(a->fg->fg->taille>a->fd->taille) return reequi(droite(a)); // Si un des 4 petits fils est plus grand que son oncle, on
if(a->fg->fd->taille>a->fd->taille) return a->fg=gauche(a->fg), reequi(droite(a)); // fait une rotation simple (pour un petit fils externe) ou
if(a->fd->fd->taille>a->fg->taille) return reequi(gauche(a)); // double (pour un petit fils interne). Les appels à droite()
if(a->fd->fg->taille>a->fg->taille) return a->fd=droite(a->fd), reequi(gauche(a)); // et gauche() rééquilibrent tout nouveau sous-arbre.
a->taille=a->fg->taille+a->fd->taille; // la taille de la racine est mise à jour,
return a; // les deux fils sont équilibrés et aucun petit fils n'est plus grand que son oncle. Donc a est équilibré.
}
abr insere(element x,abr a)
{ if(a==vide) a=malloc(sizeof(*a)), a->cle=x, a->fg=a->fd=vide; else // nouveau noeud. reequi(a) fera a->taille=2 (=vide->taille+vide->taille)
if(x==a->cle) return a; else // x est déjà dans l'arbre, puisqu'il est dans la racine.
if(x<a->cle) a->fg=insere(x,a->fg); // On insère à gauche de la racine tout nombre plus petit.
else a->fd=insere(x,a->fd); // On insère à droite de la racine tout nombre plus grand.
return reequi(a); // les tailles des fils et petits fils ont peut-être changé, il faut donc recalculer la taille de a et le rééarranger éventuellement.
}
abr enleve(element x,abr a)
{ if(a==vide) return a; // x n'est pas dans l'arbre puiqu'il est vide.
if(x<a->cle) a->fg=enleve(x,a->fg); else // si x est dans l'arbre, il est à gauche.
if(x>a->cle) a->fd=enleve(x,a->fd); else // si x est dans l'arbre, il est à droite.
if(a->fd==vide) {abr b=a->fg; free(a); a=b;} else // Pour supprimer un noeud qui n'a pas de fils droit, on le remplace par son fils gauche.
{ abr b=a->fd; // b, le fils droit de a est non vide
while(b->fg!=vide) b=b->fg; // b est le noeud le plus à gauche dans le sous-arbre droit de a. Il a la plus petite clé plus grande que a.
a->fd=enleve(a->cle=b->cle,a->fd); // On recopie la clé de b dans a, puis on supprime le noeud b.
}
return reequi(a);
}
void aff(abr a) {for(;a!=vide;a=a->fd) aff(a->fg), printf("%d ",a->cle);}
void affln(abr a) {aff(a), printf("\n");}
int main()
{ int i;
abr a=vide;
for(i=0;i<20;i++) a=insere(i*3%20,a), affln(a);
for(i=0;i<20;i++) a=enleve(i*3%20,a), affln(a);
return 0;
}]]>
précédent sommairevendredi 18 janvier 2008 :