Mercredi 12 septembre 2007 : premiers programmes en C
Mercredi 19 septembre 2007 : tri par sélection
Jeudi 20 septembre 2007 : tri par fusion
Vendredi 21 septembre 2007 : gdb, opérations sur des vecteurs
Mercredi 26 septembre 2007 : vi
Jeudi 27 septembre 2007 : pile et file d'attente avec un tableau
Mercredi 3 octobre 2007 : pile et file d'attente avec une liste chaînée
Mercredi 10 octobre 2007 : insertion triée et longueur d'une liste chaînée, itérativement et récursivement
Mercredi 17 octobre 2007 : représentation des graphes
Mercredi 24 octobre 2007 : parcours de graphe
Mercredi 7 novembre 2007 : retournement d'un graphe, parcours en largeur ou en profondeur d'abord
Mercredi 21 novembre 2007 : recherche de cycle
Mercredi 5 décembre 2007 : recherche des composantes fortement connexes
Mercredi 19 décembre 2007 : tas
Vendredi 21 décembre 2007 : Dijkstra
Vendredi 11 janvier 2008 : Dijkstra

Mercredi 12 septembre 2007 : premiers programmes en C

#include<stdio.h> int main() { int a,b; printf("Donnez deux nombres : "); scanf("%d%d",&a,&b); printf("La somme de %d et %d est %d\n",a,b,a+b); printf("La différence entre %d et %d est %d\n",a,b,a-b); printf("Le produit de %d et %d est %d\n",a,b,a*b); printf("En divsisant %d par %d, on obtient %d comme quotient et %d comme reste.\n",a,b,a/b,a%b); return 0; } #include<stdio.h> #include<math.h> int main() { long double a,b,c,d,x; printf("Donnez les coefficients a, b et c de l'équation ax²+bx+c=0 : "); scanf("%Lf%Lf%Lf",&a,&b,&c); if(a==0) if(b==0) if(c==0) printf("Tout nombre est solution.\n"); else printf("Il n'y a pas de solution.\n"); else printf("La solution est %Le\n",-c/b); else { d=b*b-4*a*c; if(d>0) { d=sqrtl(d); if(b>0) d=-d; x=(d-b)/(2*a); printf("Les deux solutions sont %Le et %Le\n",x,c/a/x); } else if(d==0) printf("La solution double est %Le\n",-b/(2*a)); else printf("Les deux racines complexes sont %Le±i%Le\n",-b/(2*a),sqrtl(-d)/(2*a)); } return 0; } int somt(int t[],int n) { int i, s=0; for(i=0;i<n;i++) s+=t[i]; return s; } int somt(int t[],int n) { return n==0 ? 0 : t[0]+somt(t+1,n-1); } int max2(int a,int b) { return a>b?a:b; } int maxt(int t[],int n) { int i, m=t[0]; for(i=1;i<n;i++) m=max2(m,t[i]); return m; } int maxt(int t[],int n) { return n==1 ? t[0] : max2(t[0],maxt(t+1,n-1)); }

Mercredi 19 septembre 2007 : tri par sélection

#include<stdio.h> int main() { int a,b; printf("Donnez deux nombres : "); scanf("%d%d",&a,&b); printf("La somme de %d et %d est %d\n",a,b,a+b); printf("La différence entre %d et %d est %d\n",a,b,a-b); printf("Le produit de %d et %d est %d\n",a,b,a*b); printf("En divsisant %d par %d, on obtient %d comme quotient et %d comme reste.\n",a,b,a/b,a%b); return 0; } #include<stdio.h> #include<math.h> int main() { double a,b,c,d,x; printf("Donnez les coefficients a, b et c de l'équation ax²+bx+c=0 : "); scanf("%lf%lf%lf",&a,&b,&c); if(a==0) if(b==0) if(c==0) printf("Tout nombre est solution.\n"); else printf("Il n'y a pas de solution.\n"); else printf("La solution est %le\n",-c/b); else { d=b*b-4*a*c; if(d>0) { d=sqrt(d); if(b>0) d=-d; x=(d-b)/(2*a); printf("Les deux solutions sont %le et %le\n",x,c/a/x); } else if(d==0) printf("La solution double est %le\n",-b/(2*a)); else printf("Les deux racines complexes sont %le±i%le\n",-b/(2*a),sqrt(-d)/(2*a)); } return 0; } #include<stdio.h> void afft(int t[],int n) { int i; for(i=0;i<n;i++) printf("%d ",t[i]); } int somite(int t[],int n) { int i, s=0; for(i=0;i<n;i++) s+=t[i]; return s; } int somrec(int t[],int n) { return n==0 ? 0 : t[0]+somrec(t+1,n-1); } int max2(int a,int b) { return a>b?a:b; } int maxite(int t[],int n) { int i, m=t[0]; for(i=1;i<n;i++) m=max2(m,t[i]); return m; } int maxrec(int t[],int n) { return n==1 ? t[0] : max2(t[0],maxrec(t+1,n-1)); } void triselection(int t[],int n) { for(;n>1;n--) { int i, m=t[0], posm=0; for(i=1;i<n;i++) if(t[i]>m) m=t[posm=i]; t[posm]=t[n-1]; t[n-1]=m; } } int main() { int t[]={5,2,6,1,4,8,-1,3}, n=8; afft(t,n); printf("\n"); printf("La somme des éléments est %d=%d\n",somite(t,n),somrec(t,n)); printf("Le plus grand des éléments est %d=%d\n",maxite(t,n),maxrec(t,n)); triselection(t,n); afft(t,n); printf("\n"); return 0; }

Jeudi 20 septembre 2007 : tri par fusion

#include<stdio.h> #include<stdlib.h> void afft(int t[],int n) { int i; for(i=0;i<n;i++) printf("%d ",t[i]); } int*interclasse(int t1[],int n1,int t2[],int n2) { int n3=n1+n2, *t3=malloc(n3*sizeof(*t3)), i=0, j=0, k=0; while(k<n3) t3[k++]= i<n1 && (j>=n2 || t1[i]<t2[j]) ? t1[i++] : t2[j++]; return t3; } void trifusion(int t[],int n) { if(n>1) { int m=n/2, i, *trep; trifusion(t,m); trifusion(t+m,n-m); trep=interclasse(t,m,t+m,n-m); for(i=0;i<n;i++) t[i]=trep[i]; free(trep); } } void trifusion2(int t1[],int n3) { if(n3>1) { int n1=n3/2, n2=n3-n1, *t2=t1+n1, t3[n3], i=0, j=0, k=0; trifusion2(t1,n1); trifusion2(t2,n2); while(k<n3) t3[k++]= i<n1 && (j>=n2 || t1[i]<t2[j]) ? t1[i++] : t2[j++]; for(k=0;k<n3;k++) t1[k]=t3[k]; } } int main() { int t[]={5,2,6,1,4,8,-1,3}, n=8; afft(t,n); printf("\n"); trifusion(t,n); afft(t,n); printf("\n"); return 0; }

Vendredi 21 septembre 2007 : gdb, opérations sur des vecteurs

#include<stdio.h> #include<stdlib.h> #define dim 4 typedef double nombre, vec[dim], mat[dim][dim]; nombre*somvvv(vec a,vec b) { nombre*c=malloc(sizeof(vec)); int i; for(i=0;i<dim;i++) c[i]=a[i]+b[i]; return c; } nombre*difvvv(vec a,vec b) { nombre*c=malloc(sizeof(vec)); int i; for(i=0;i<dim;i++) c[i]=a[i]-b[i]; return c; } nombre*mulrvv(nombre a,vec b) { nombre*c=malloc(sizeof(vec)); int i; for(i=0;i<dim;i++) c[i]=a*b[i]; return c; } vec*sommmm(mat a,mat b) { vec*c=malloc(sizeof(mat)); int i,j; for(i=0;i<dim;i++) for(j=0;j<dim;j++) c[i][j]=a[i][j]+b[i][j]; return c; } nombre*mulmvv(mat a,vec b) { nombre*c=malloc(sizeof(vec)); int i,j; for(i=0;i<dim;i++) c[i]=0; for(i=0;i<dim;i++) for(j=0;j<dim;j++) c[i]+=a[i][j]*b[i]; return c; } vec*mulmmm(mat a,mat b) { vec*c=malloc(sizeof(mat)); int i,j,k; for(i=0;i<dim;i++) for(j=0;j<dim;j++) c[i][j]=0; for(i=0;i<dim;i++) for(j=0;j<dim;j++) for(k=0;k<dim;k++) c[i][k]+=a[i][j]*b[i][k]; return c; } void affvec(vec a) { int i; for(i=0;i<dim;i++) printf("\t%le",a[i]); printf("\n"); } void affmat(mat a) { int i; printf("\n") ;for(i=0;i<dim;i++) affvec(a[i]); } void copdelvec(vec a,vec b) { int i; for(i=0;i<dim;i++) b[i]=a[i]; free(a); } int main() { vec a={3,5,2,6}, b={5,4,1,3}, c; copdelvec(somvvv(a,b),c); affvec(a); affvec(b); affvec(c); return 0; }

Mercredi 26 septembre 2007 : vi

Écrire et exécuter un programme en C : exceed, KDE, Konsole, vim et gcc

Sous windows, il faut d'abord lancer exceed, pour avoir une fenêtre graphique contenant KDE associé à un autre ordinateur tournant sous linux.
Dans KDE le troisième bouton en bas à gauche de la fenêtre, représente un écran d'ordinateur et permet de lancer konsole, qui ouvre un terminal X, c'est-à-dire une fenêtre dans laquelle on peut taper des commandes unix qui sont interprétées par un shell (a priori bash).
Dans Konsole, on peut ouvrir deux terminaux X. Pour ouvrir un deuxième terminal, il suffit de cliquer sur le bouton en bas de la fenêtre de Konsole. Pour passer d'un terminal à l'autre on peut cliquer sur un des deux onglets se trouvant en bas de la fenêtre de Konsole, ou bien appuyer sur <shift>← ou <shift>→ .
Dans un des terminaux, on mettra le programme en cours d'écriture. On y tapera donc :
mkdir algo
cd algo
vi bonjour.c
Dans l'autre terminal, on pouura compiler et on exécuter le programme en y tapant
cd algo
gcc -Wall bonjour.c
./a.out

vi ou vim

Vi est l'éditeur de texte traditionnel d'unix. Il existe depuis plusieurs dizaines d'années. Vim est une version améliorée de vi, que l'on utilise maintenant avec linux. Il reconnaît toutes les commandes de vi, plus beaucoup de nouvelles. Dans beaucoup d'éditeurs de texte, les lettres que l'on tape sont insérées dans le texte et il faut taper <ctrl>+une lettre pour exécuter une commande. C'est différent sous vi : les lettres servent à exécuter des commandes et il faut d'abord passer en mode insertion avant de pouvoir taper du texte.

insertion

Beaucoup de commandes permettent de passer en mode insertion : <ins> permet de passer du mode insertion au mode remplacement et réciproquement.
<échap> permet de sortir du mode insertion ou remplacement et revenir au mode de commande.

déplacement du curseur

Les quatre touches de déplacement du curseur et les quatre touches page vers le haut, page vers le bas, début et fin marchent normalement avec vim, mais certaines de ces commandes peuvent aussi se faire autrement : h=ctrl-H=<backspace>=← , k=↑ , l=<espace;>=→ , j=↓ , ^=<début>=0 , $=<fin> .
on peut aussi utiliser les commandes :

sauvegarder et quitter

divers

remplacement

Pour remplacer toutes les occurences de truc par machin on peut
ou bien d'abord taper /truc puis cwmachin<échap> ou 4clmachin<échap> puis n.n.n.n. autant de fois que nécessaire. n se place sur le prochain truc et . le remplace par machin.
Ou bien on tape une commande comme :%s/truc/machin/g
% est équivalent à 1,$ qui veut dire : sur toutes les lignes. On aurait pu le remplacer par exemple par 21,45 qui veut dire sur lignes 21 à 45.
Le g signifie que l'on fait plusieurs remplacement par ligne

copier (y yank), couper (d delete) et coller (p put)

Il y a plusieurs façons de copier du texte : Il y a autant façons de couper du texte : Dans ce qui précède il faut remplacer y par d. On a donc les commandes dd, 5dd, dl, 2dl, dw, 7dw, d$, d^, v...d, V...d, ctrl-V...d.
La commande p (resp. P) colle le dernier bout de texte copié ou coupé, derrière (resp. devant) le caractère ou la ligne courante.
Exemples :
Pour dupliquer la ligne courante, il suffit de taper yyp .
Pour échanger la ligne courante et la suivante, il suffit de taper ddp .
Pour échanger le caractère sous le curseur et le suivant, il suffit de taper dlp ou xp .
Pour échanger le mot courant et le précédent, il suffit de taper bdwbP .

sélection

Les commandes de sélection (v, V et ctrl-V) sont suivies de déplacements du curseur et se terminent par, au choix : gv resélectionne la même zone.

premier programme

En utilisant vi on va d'abord mettre dans algo/bonjour.c le programme :#include<stdio.h> int main() { printf("Bonjour\n"); return 0; } Puis on va On peut alors compiler le programme par la commande cc -Wall bonjour.c puis l'exécuter par ./a.out
On peut supprimer la ligne #include<stdio.h> du programme, le sauver, par :w le recompiler et l'exécuter, puis le restaurer, par u.
On peut de même supprimer le \n ou la ligne return 0; ou le int devant main ou enfin le point-virgule après le 0.

autre façon plus sûre pour exécuter un programme : !

Au lieu de changer de fenêtre il est plus simple et plus sûr de rester dans la même fenêtre et de taper
:!gcc -Wall -g %
suivi de
:!./a.out
ou de
:!gdb a.out
En effet après :! on peut taper un commande qui sera passée au shell et exécutée dans la même fenêtre que vi. Dans cette commande % est remplacé par le nom du fichier que l'est en train d'éditer. Ainsi on est sûr de bien compiler le fichier que l'on vient d'éditer, et non pas un autre comme cela arrive parfois quand on édite et compile dans des fenêtres différentes. De plus vi prévient si on tape une commande :!...% sans avoir sauvé le fichier courant par :w .

autre programme : 3+4=7

On peut sortir de vi par :q et le relancer par vi somme.c.
On peut aussi rester dans vi et taper la commande :w somme.c et modifier le programme pour qu'il devienne : #include<stdio.h> int main() { int a,b; printf("Donnez deux nombres entiers : "); scanf("%d%d",&a,&b); printf("%d+%d=%d\n",a,b,a+b); return 0; } On peut modifier le programme pour qu'il calcule aussi le produit, le quotient et le reste de la division : #include<stdio.h> int main() { int a,b; printf("Donnez deux nombres entiers : "); scanf("%d%d",&a,&b); printf("%d+%d=%d\n",a,b,a+b); printf("%d*%d=%d\n",a,b,a*b); printf("%d/%d=%d\n",a,b,a/b); printf("%d%%%d=%d\n",a,b,a%b); return 0; } Si on exécute se programme en lui donnant les deux nombres 3 et 0, il se termine par une erreur.
Pour savoir où cette erreur se produit on peut recompiler en n'oubliant pas l'option -g puis lancer le debugger :cc somme.c -Wall -g gdb a.out On peut alors taper :run 3 0 print a print b qt quit

Jeudi 27 septembre 2007 : pile et file d'attente avec un tableau

#include<stdio.h> typedef int nombre; #if 1 #define taillemax 40 typedef struct {nombre t[taillemax]; int debut,fin;} ens; void aff(ens*a) { int i; for(i=a->debut;i!=a->fin;i=(i+1)%taillemax) printf("%d ",a->t[i]); printf("\n"); } void inseretete(nombre x,ens*a) { if(a->debut==0) a->debut=taillemax; a->t[--a->debut]=x; } void inserequeue(nombre x,ens*a) { a->t[a->fin++]=x; if(a->fin==taillemax) a->fin=0; } void inseretrie(nombre x,ens*a) { int i=a->fin++; if(a->fin==taillemax) a->fin=0; while(i!=a->debut) { int j=(i?i:taillemax)-1; if(a->t[j]<=x) break; a->t[i]=a->t[j]; i=j; } a->t[i]=x; } nombre enlevetete(ens*a) { nombre x=a->t[a->debut++]; if(a->debut==taillemax) a->debut=0; return x; } void initens(ens*a) {a->debut=a->fin=0;} void detruitens(ens*a) {} int vide(ens*a) { return a->debut==a->fin; } #endif #if 0 void inseretete(nombre x,ens*a) void inserequeue(nombre x,ens*a) void inseretrie(nombre x,ens*a) nombre enlevetete(ens*a) void initens(ens*a) void detruitens(ens*a) int vide(ens*a) #endif typedef void (*proc)(nombre,ens*); proc p[3]={inseretete,inserequeue,inseretrie}; int main() { ens s; int x, i, j; nombre y; initens(&s); for(i=0;i<3;i++) { for(x=j=0;j<10;j++) p[i](x=(3*x+1)%32,&s),aff(&s); for(;;) { y=enlevetete(&s); if(vide(&s)) break; y-=enlevetete(&s); if(y<0) y=-y; p[i](y,&s),aff(&s); } printf("%d\n",y); } return 0; }

Mercredi 3 octobre 2007 : pile et file d'attente avec une liste chaînée

#include<stdio.h> #include<stdlib.h> typedef int nombre; #if 0 #define taillemax 40 typedef struct {nombre t[taillemax]; int debut,fin;} ens; void aff(ens*a) { int i; for(i=a->debut;i!=a->fin;i=(i+1)%taillemax) printf("%d ",a->t[i]); printf("\n"); } void inseretete(nombre x,ens*a) { if(a->debut==0) a->debut=taillemax; a->t[--a->debut]=x; } void inserequeue(nombre x,ens*a) { a->t[a->fin++]=x; if(a->fin==taillemax) a->fin=0; } void inseretrie(nombre x,ens*a) { int i=a->fin++; if(a->fin==taillemax) a->fin=0; while(i!=a->debut) { int j=(i?i:taillemax)-1; if(a->t[j]<=x) break; a->t[i]=a->t[j]; i=j; } a->t[i]=x; } nombre enlevetete(ens*a) { nombre x=a->t[a->debut++]; if(a->debut==taillemax) a->debut=0; return x; } void initens(ens*a) {a->debut=a->fin=0;} void detruitens(ens*a) {} int vide(ens*a) { return a->debut==a->fin; } #endif #if 1 typedef struct chainon *liste; struct chainon { nombre x; liste suite; }; typedef struct { liste tete, queue; } ens; void initens(ens*a) { a->tete=0; } int vide (ens*a) { return !a->tete; } void aff (ens*a) { liste p; for(p=a->tete;p;p=p->suite) printf("%d ",p->x); printf("\n"); } void inseretete(nombre x,ens*a) { liste c=malloc(sizeof(*c)); c->x=x; c->suite=a->tete; a->tete=c; if(!c->suite) a->queue=c; } void inserequeue(nombre x,ens*a) { liste c=malloc(sizeof(*c)); c->x=x; c->suite=0; if(a->tete) a->queue->suite=c; else a->tete =c; a->queue=c; } void inseretrie(nombre x,ens*a) { if(vide(a) || x<=a->tete ->x) inseretete (x,a); else if( x>=a->queue->x) inserequeue(x,a); else { liste c=malloc(sizeof(*c)), b=a->tete; while(x>b->suite->x) b=b->suite; c->x=x; c->suite=b->suite; b->suite=c; } } nombre enlevetete(ens*a) { liste c=a->tete; nombre x=c->x; a->tete=c->suite; free(c); return x; } void detruitens(ens*a) { while(!vide(a)) enlevetete(a); } #endif typedef void (*proc)(nombre,ens*); proc p[3]={inseretete,inserequeue,inseretrie}; int main() { ens s; int x, i, j; nombre y; initens(&s); for(i=0;i<3;i++) { for(x=j=0;j<10;j++) p[i](x=(3*x+1)%32,&s),aff(&s); for(;;) { y=enlevetete(&s); if(vide(&s)) break; y-=enlevetete(&s); if(y<0) y=-y; p[i](y,&s),aff(&s); } printf("%d\n",y); } return 0; }

Mercredi 10 octobre 2007 : insertion triée et longueur d'une liste chaînée, itérativement et récursivement

#include<stdio.h> #include<stdlib.h> typedef int nombre; #if 0 #define taillemax 40 typedef struct {nombre t[taillemax]; int debut,fin;} ens; void aff(ens*a) { int i; for(i=a->debut;i!=a->fin;i=(i+1)%taillemax) printf("%d ",a->t[i]); printf("\n"); } void inseretete(nombre x,ens*a) { if(a->debut==0) a->debut=taillemax; a->t[--a->debut]=x; } void inserequeue(nombre x,ens*a) { a->t[a->fin++]=x; if(a->fin==taillemax) a->fin=0; } void inseretrie(nombre x,ens*a) { int i=a->fin++; if(a->fin==taillemax) a->fin=0; while(i!=a->debut) { int j=(i?i:taillemax)-1; if(a->t[j]<=x) break; a->t[i]=a->t[j]; i=j; } a->t[i]=x; } nombre enlevetete(ens*a) { nombre x=a->t[a->debut++]; if(a->debut==taillemax) a->debut=0; return x; } void initens(ens*a) {a->debut=a->fin=0;} void detruitens(ens*a) {} int vide(ens*a) { return a->debut==a->fin; } int cardinal(ens *a) { int l=a->fin-a->debut; if(l<0) l+=taillemax; return l; } #endif #if 1 typedef struct chainon *liste; struct chainon { nombre x; liste suite; }; typedef struct { liste tete, queue; } ens; void initens(ens*a) { a->tete=0; } int vide (ens*a) { return !a->tete; } void aff (ens*a) { liste p; for(p=a->tete;p;p=p->suite) printf("%d ",p->x); printf("\n"); } void inseretete(nombre x,ens*a) { liste c=malloc(sizeof(*c)); c->x=x; c->suite=a->tete; a->tete=c; if(!c->suite) a->queue=c; } void inserequeue(nombre x,ens*a) { liste c=malloc(sizeof(*c)); c->x=x; c->suite=0; if(a->tete) a->queue->suite=c; else a->tete =c; a->queue=c; } void inseretrieite(nombre x,ens*a) // version itérative { if(vide(a) || x<=a->tete ->x) inseretete (x,a); else if( x>=a->queue->x) inserequeue(x,a); else { liste c=malloc(sizeof(*c)), b=a->tete; while(x>b->suite->x) b=b->suite; c->x=x; c->suite=b->suite; b->suite=c; } } liste instri(nombre x,liste a) { if(a && a->x<x) {a->suite=instri(x,a->suite); return a;} { liste b=malloc(sizeof(*b)); b->x=x; b->suite=a; return b; } } void inseretrierec(nombre x,ens*a) // version récursive { if(vide(a) || x<=a->tete ->x) inseretete (x,a); else if( x>=a->queue->x) inserequeue(x,a); else instri(x,a->tete); } nombre enlevetete(ens*a) { liste c=a->tete; nombre x=c->x; a->tete=c->suite; free(c); return x; } void detruitens(ens*a) { while(!vide(a)) enlevetete(a); } int longueur(liste a) {return a?1+longueur(a->suite):0; } int cardinalrec(ens *a) {return longueur(a->tete); } int cardinalite(ens *a) { int l=0; liste b; for(b=a->tete;b;b=b->suite) l++; return l; } #if 0 #define inseretrie inseretrierec #define cardinal cardinalrec #else #define inseretrie inseretrieite #define cardinal cardinalite #endif #endif typedef void (*proc)(nombre,ens*); proc p[3]={inseretete,inserequeue,inseretrie}; int main() { ens s; int x, i, j; nombre y; initens(&s); for(i=0;i<3;i++) { for(x=j=0;j<10;j++) p[i](x=(3*x+1)%32,&s),aff(&s); printf("%d\n",cardinal(&s)); for(;;) { y=enlevetete(&s); if(vide(&s)) break; y-=enlevetete(&s); if(y<0) y=-y; p[i](y,&s),aff(&s); } printf("%d\n",y); } return 0; }

Mercredi 17 octobre 2007 : représentation des graphes

#include<stdio.h> #include<stdlib.h> #define n 4 // nombre de sommets du graphe #define a 8 // nombre d'arcs du graphe typedef char bool; typedef short int sommet; typedef bool graphe1[n][n]; typedef struct {sommet ori, ext;} graphe2[a]; typedef int tetesuite[n+a]; typedef struct chainon *liste; struct chainon {sommet s; liste suite;}; typedef liste graphe3[n]; void affg1(graphe1 g) { sommet i,j; for(i=0;i<n;i++) for(j=0;j<n;j++) if(g[i][j]) printf("%d-->%d ", i, j); printf("\n"); } void affg2(graphe2 g) { int k; for(k=0;k<a;k++) printf("%d-->%d ", g[k].ori, g[k].ext); printf("\n"); } void affg3(graphe3 g) { sommet i; liste p; for(i=0;i<n;i++) for(p=g[i];p;p=p->suite) printf("%d-->%d ", i, p->s); printf("\n"); } void g1g2(graphe1 g1, graphe2 g2) { sommet i,j; int k=0; for(i=0;i<n;i++) for(j=0;j<n;j++) if(g1[i][j]) g2[k].ori=i, g2[k++].ext=j; } void g2g1(graphe2 g2, graphe1 g1) { sommet i,j; int k; for(i=0;i<n;i++) for(j=0;j<n;j++) g1[i][j]=0; for(k=0;k<a;k++) g1[g2[k].ori][g2[k].ext]=1; } void g1g3(graphe1 g1, graphe3 g3) { sommet i,j; for(i=0;i<n;i++) g3[i]=0; for(i=0;i<n;i++) for(j=0;j<n;j++) if(g1[i][j]) { liste p=malloc(sizeof(*p)); p->s=j; p->suite=g3[i]; g3[i]=p; } } void g3g1(graphe3 g3, graphe1 g1) { sommet i,j; liste p; for(i=0;i<n;i++) for(j=0;j<n;j++) g1[i][j]=0; for(i=0;i<n;i++) for(p=g3[i];p;p=p->suite) g1[i][p->s]=1; } void g3g2(graphe3 g3, graphe2 g2) { sommet i; int k=0; liste p; for(i=0;i<n;i++) for(p=g3[i];p;p=p->suite) g2[k].ori=i, g2[k++].ext=p->s; } void g2g3(graphe2 g2, graphe3 g3) { int k; sommet i; for(i=0;i<n;i++) g3[i]=0; for(k=0;k<a;k++) { liste p=malloc(sizeof(*p)); p->s=g2[k].ext; p->suite=g3[i=g2[k].ori]; g3[i]=p; } } void g2ts(graphe2 g2, tetesuite tete) { int k, *suite=tete+n; sommet i; for(i=0;i<n;i++) tete[i]=-1; for(k=0;k<a;k++) suite[k]=tete[i=g2[k].ori], tete[i]=k; } int main() { graphe2 g2={{0,1},{1,2},{2,3},{0,3},{1,0},{2,1},{1,3},{2,0}}, h2, k2; graphe1 g1, h1; graphe3 g3, h3; tetesuite ts; affg2(g2); g2g1(g2,g1), printf("g2g1 : "), affg1(g1); g1g2(g1,h2), printf("g1g2 : "), affg2(h2); g2g3(g2,g3), printf("g2g3 : "), affg3(g3); g3g2(g3,k2), printf("g3g2 : "), affg2(k2); g3g1(g3,h1), printf("g3g1 : "), affg1(h1); g1g3(g1,h3), printf("g1g3 : "), affg3(h3); g2ts(g2,ts); return 0; }

Mercredi 24 octobre 2007 : parcours de graphe

void dfs1(sommet s,graphe1 g,bool visite[n]) { if(!visite[s]) // Si le sommet s n'a pas encore été visité { int t; visite[s]=1; // on note que maintenant il a été visité puis for(t=0;t<n;t++) if(g[s][t]) // chaque de successeur t de s dfs1(t,g,visite); // est visité } } void dfs3(sommet s,graphe3 g,bool visite[n]) { if(!visite[s]) // Si le sommet s n'a pas encore été visité { liste p; visite[s]=1; // on note que maintenant il a été visité puis for(p=g[s];p;p=p->suite) // chaque de successeur de s dfs3(p->s,g,visite); // est visité } } void dfs2(sommet s,graphe2 g,tetesuite tete,bool visite[n]) { if(!visite[s]) // Si le sommet s n'a pas encore été visité { int k, *suite=tete+n; visite[s]=1; // on note que maintenant il a été visité puis for(k=tete[s];k>=0;k=suite[k]) // pour chaque arc k partant de s dfs2(g[k].ext,g,tete,visite); // on visite son extrémité } } int main() { int i, ng; graphe2 g2={{0,1},{1,2},{2,3},{0,3},{1,0},{2,1},{1,3},{2,0}}, h2, k2; graphe1 g1, h1; graphe3 g3, h3; tetesuite ts; affg2(g2); g2g1(g2,g1), printf("g2g1 : "), affg1(g1); g1g2(g1,h2), printf("g1g2 : "), affg2(h2); g2g3(g2,g3), printf("g2g3 : "), affg3(g3); g3g2(g3,k2), printf("g3g2 : "), affg2(k2); g3g1(g3,h1), printf("g3g1 : "), affg1(h1); g1g3(g1,h3), printf("g1g3 : "), affg3(h3); g2ts(g2,ts); for(ng=0;ng<3;ng++) { bool visite[n]; for(i=0;i<n;i++) visite[i]=0; switch(ng) { case 0: dfs1(2,g1, visite); break; case 1: dfs2(2,g2,ts,visite); break; case 2: dfs3(2,g3, visite); break; } for(i=0;i<n;i++) if(visite[i]) printf(" %d ",i); printf("\n"); } return 0; }

Mercredi 7 novembre 2007 : retournement d'un graphe, parcours en largeur ou en profondeur d'abord

Contrôle

Dans le programme précédent complétez les procédures retg1, retg2 et retg3 qui doivent retourner tous les arcs du graphe, en échangeant l'origine et l'extrémité de chacun d'eux. Elle ne devront pas faire d'appel à malloc ni à free. Par exemple les chaînons des anciennes listes devront être réutilisés en les répartissant dans des nouvelles listes initialement vides et dont les têtes sont rangées dans un tableau de type graphe3 local à la procédure retg3 et qui sera à la fin recopié dans g. void retg1(graphe1 g) // change le sens du graphe : l'arc i-->j devient l'arc j-->i { int i,j; for(i=0;i<n;i++) // Pour tout couple de sommets (i,j) avec i>j for(j=0;j<i;j++) { bool x=g[i][j]; // on échange les valeurs de g[i][j] et g[j][i] g[i][j]=g[j][i]; g[j][i]=x; // Si on oublie la condition i>j, les deux variables g[1][2] et g[2][1] seront échangées deux fois, } // pour (i,j)=(1,2) et (i,j)=(2,1), et elles reprendront leur valeur initiale. } void retg2(graphe2 g) // change le sens du graphe : l'arc i-->j devient l'arc j-->i { int k; for(k=0;k<a;k++) // Pour chacun des a arcs g[k] { sommet x=g[k].ori; // on échange son origine et son extrémité. g[k].ori=g[k].ext; g[k].ext=x; } } void retg3(graphe3 g) // change le sens du graphe : l'arc i-->j devient l'arc j-->i { graphe3 h; sommet i; liste l; for(i=0;i<n;i++) h[i]=g[i], g[i]=0; // On met tous les arcs de g dans le graphe h, et g n'a plus d'arc. for(i=0;i<n;i++) for(l=h[i];l;) // Pour chaque sommet i et chaque arc l (ou p) partant de i, on l'enlève de h et on l'ajoute retourné dans g. { liste p=l; // Le chaînon à déplacer p sommet j=p->s; // représente un arc de i vers j dans le graphe h. l=p->suite; // On l'enlève de la liste l des successeurs de i dans h. p->s=i; // On l'utilise pour représenter que i est un successeur de j dans g. (la nouvelle extrémité est i) p->suite=g[j], g[j]=p; // On insère le chaînon p en tête de la liste g[j] des arcs partant du sommet j dans le graphe g. } }

parcours en largeur d'abord

void wfs(graphe3 g, sommet depart, int dist[n], sommet pere[n]) { sommet file[n], y; int debf=0, finf=0; // La file d'attente est initialement vide. liste l; for(y=0;y<n;y++) dist[y]=pere[y]=n; // aucun sommet n'a encore été visité pere[depart]=depart; // Le sommet de départ est la racine de l'arbre de parcours, il n'a pas de père. dist[depart]=0; // Il est à une distance 0 de lui-même. file[finf++]=depart; // On le met dans la file d'attente des sommets ouverts. while(debf<finf) // Tant que la file n'est pas vide { sommet x=file[debf++]; // on sort x de la file d'attente for(l=g[x];l;l=l->suite) // pour chacun des arcs partant de x if(pere[y=l->s]==n) // qui mène à un sommet y non encore visité, { pere[y]=x; // On note qu'il est visité en notant son père dist[y]=dist[x]+1; // et sa distance au sommet de départ. file[finf++]=y; // On le met dans la file d'attente } } }

parcours en profondeur d'abord avec pile

void dfspile(graphe3 g, sommet depart, int dist[n], sommet pere[n]) { sommet pile[n], y; graphe3 h; int hauteur=0; // La pile est initialement vide. for(y=0;y<n;y++) dist[y]=pere[y]=n, // Aucun sommet n'a encore été visité h[y]=g[y]; // tous les arcs sont encore utilisables. pere[depart]=depart; // Le sommet de départ est la racine de l'arbre de parcours, il n'a pas de père. dist[depart]=0; // Il est à une distance 0 de lui-même. pile[hauteur++]=depart; // On le met dans la pile des sommets ouverts. while(hauteur) // Tant que la pile n'est pas vide { sommet x=pile[--hauteur]; // on sort x de la pile liste l=h[x]; // l est la liste des arcs partant de x qui n'ont pas encore été utilisés if(l) // Si cette liste n'est pas vide, { h[x]=l->suite; // on va utiliser son premier élément, qu'on enlève donc de la liste pile[hauteur++]=x; // On remet x dans la pile if(pere[y=l->s]==n) // Si l'arc l mène à un sommet y non encore visité, { pere[y]=x; // On note qu'il est visité en notant son père dist[y]=dist[x]+1; // et sa distance au sommet de départ (dans l'arbre de parcours) pile[hauteur++]=y; // et on le met dans la pile } } } }

parcours en profondeur d'abord sans pile

void dfs(graphe3 g, sommet x, int dist[n], sommet pere[n]) { sommet y; graphe3 h; for(y=0;y<n;y++) dist[y]=pere[y]=n, // Aucun sommet n'a encore été visité. h[y]=g[y]; // Tous les arcs sont encore utilisables. pere[x]=x; // Le sommet de départ est la racine de l'arbre de parcours. Il n'a pas de père. dist[x]=0; // Il est à une distance 0 de lui-même. for(;;) // Tant qu'on a pas fini { liste l=h[x]; // l est la liste des arcs partant de x qui n'ont pas encore été utilisés. if(l) // Si cette liste n'est pas vide, { h[x]=l->suite; // on va utiliser son premier élément, qu'on enlève donc de la liste. if(pere[y=l->s]==n) // Si l'arc l mène à un sommet y non encore visité, { pere[y]=x; // On note qu'il est visité en notant son père dist[y]=dist[x]+1; // et sa distance au sommet de départ (dans l'arbre de parcours) x=y; // et on avance sur ce sommet. } } else // Quand on a regardé tous les arcs partant de x, if(pere[x]==x) break; // si de plus x est le sommet de départ, alors on a fini, else x=pere[x]; // sinon on recule. } } int main() { int i, ng; graphe2 g2={{0,1},{1,2},{2,3},{0,3},{1,0},{2,1},{1,3},{2,0}}, h2, k2; graphe1 g1, h1; graphe3 g3, h3; tetesuite ts; void (*tfs[])(graphe3 g,sommet depart, int dist[n], sommet pere[n])={wfs,dfs,dfspile}; affg2(g2); g2g1(g2,g1), printf("g2g1 : "), affg1(g1); g1g2(g1,h2), printf("g1g2 : "), affg2(h2); g2g3(g2,g3), printf("g2g3 : "), affg3(g3); g3g2(g3,k2), printf("g3g2 : "), affg2(k2); g3g1(g3,h1), printf("g3g1 : "), affg1(h1); g1g3(g1,h3), printf("g1g3 : "), affg3(h3); g2ts(g2,ts); for(ng=0;ng<3;ng++) { bool visite[n]; for(i=0;i<n;i++) visite[i]=0; switch(ng) { case 0: dfs1(2,g1, visite); break; case 1: dfs2(2,g2,ts,visite); break; case 2: dfs3(2,g3, visite); break; } for(i=0;i<n;i++) if(visite[i]) printf(" %d ",i); printf("\n"); } for(ng=0;ng<3;ng++) { int dist[n]; sommet pere[n]; tfs[ng](g3,2,dist,pere); for(i=0;i<n;i++) printf(" %d-->%d(%d) ",pere[i],i,dist[i]); printf("\n"); } return 0; }

Mercredi 21 novembre 2007 : recherche de cycle

typedef enum{libre, ouvert, ferme} statut[n]; // Chaque sommet peut être libre, ouvert ou fermé int arr(graphe2 g, sommet pere[n]) // Rend un arc arrière dans la forêt correspondant à pere. { tetesuite tete; statut stat; int arr=n, *suite=tete+n; // Rend n s'il n'y a pas de cycle void parcours(sommet s) // Procédure récursive, s est un sommet libre { sommet t; // t est un des sommets successeurs de s int k; // k est un des arcs partant du sommet s stat[s]=ouvert; // s sera ouvert jusqu'à la fin de l'exécution de cette procédure for(k=tete[s];k>=0;k=suite[k]) // Pour chaque arc k partant du sommet s switch(stat[t=g[k].ext]) // et arrivant sur le sommet t, { case libre : pere[t]=s; parcours(t); break; // si t est libre, on va le visiter ( en mettant l'arc s-->t dans l'arbre de parcours) case ouvert: arr=k; // si t est ouvert, on a trouvé un arc arrière k : s-->t default: ; } stat[s]=ferme; // On a exploré s et tous ses successeurs } sommet s; g2ts(g,tete); // On construit les listes d'adjacence, à partir de la liste de tous les arcs. for(s=0;s<n;s++) stat[s]= libre; // Tous les sommets sont initialement libres for(s=0;s<n;s++) if(stat[s]==libre) pere[s]=s, parcours(s); // On fait un parcours en profondeur à partir de sommets libres return arr; // On rend le dernier arc arrière trouvé ou n s'il n'y en a pas. } void affcycle(graphe2 g, sommet pere[n], int k) // Affiche un cycle, en affichant à l'envers la branche de l'arbre de parcours { sommet x=g[k].ori, t=g[k].ext; // reliant l'extrémité d'un arc arrière à l'origine de cet arc. for(;x!=t;x=pere[x]) printf("%d ",x); printf("%d\n",x); }

Mercredi 5 décembre 2007 : recherche des composantes fortement connexes

int cherchecfc(graphe2 g2,int cfc[n]) { int finvisite[n], nbfin=0, tete[n+a], *suite=tete+n, nbcfc=0; void parcours1(sommet s) { int k; sommet t; cfc[s]=-1; // on note que s a déjà été visité for(k=tete[s];k>=0;k=suite[k]) if(!cfc[t=g2[k].ext]) parcours1(t); finvisite[nbfin++]=s; } void parcours2(sommet s) { int k; sommet t; cfc[s]=nbcfc; // on note que s a déjà été visité for(k=tete[s];k>=0;k=suite[k]) if(cfc[t=g2[k].ext]<0) parcours2(t); } int i; g2ts(g2,tete); // chaînage des arcs sortant de chacun des sommets for(i=0;i<n;i++) cfc[i]=0; // aucun sommet n'a encore été visité for(i=0;i<n;i++) if(!cfc[i]) parcours1(i); retg2(g2); // retournement du graphe g2ts(g2,tete); // chaînage des arcs entrant dans chacun des sommets while(nbfin) if(cfc[i=finvisite[--nbfin]]<0) parcours2(i), nbcfc++; retg2(g2); // retournement du graphe return nbcfc; } Comptage des composantes fortement connexes du graphe ayant pour sommets les nombres entiers de 0 à 1000 et les arcs de la forme : 2i --> i et i --> 3i+1
n=1001
a=501+334 void initg2(graphe2 g2) { int k=0, i,j; for(i=0;j=i+i ,j<=1000;i++) g2[k].ori=j, g2[k++].ext=i; for(i=0;j=3*i+1,j<=1000;i++) g2[k].ori=i, g2[k++].ext=j; printf("k=%d a=%d\n",k,a); if(k!=a) exit(1); } int main() { graphe2 g2; int cfc[n]; initg2(g2); printf("Il y a %d composantes fortement connexes\n",cherchecfc(g2,cfc)); return 0; } programme commenté en C g1g2g3.c

Mercredi 19 décembre 2007 : tas

#include<stdio.h> #include<stdlib.h> typedef int element; // type des éléments rangés dans le tas typedef struct{element *t; int n; const int nmax;} tas; // 0n utilise t[1],t[2],...,t[n] n<=nmax tas nouveautas(int nmax) { tas a={malloc((nmax+1)*sizeof(element)),0,nmax}; // t[0] n'est jamais utilisé return a; } void detruittas(tas a) { free(a.t); } // free libère la place alloouée par le malloc de nouveautas void remonte(tas a, int j) // x=t[j] remonte en t[j/2] puis t[j/4] etc. { element x=a.t[j]; for(;;) { int jj=j/2; // t[jj] est le père de t[j] if(!jj) return; // jj=0 ssi j=1 : Il n'y a pas de père if(x>=a.t[jj]) return; // Le père est bien plus petit. x est à sa place a.t[j]=a.t[jj]; // On échange t[j] et t[jj] a.t[j=jj]=x; } } void descend(tas a,int j) { element x=a.t[j]; // x=t[j] descend en t[2*j ou 2*j+1] puis en ... for(;;) { int jj=j+j; // t[2*j] est le premier fils de t[j] if(jj>a.n) return; // Il n'y a pas de fils. if(jj<a.n && a.t[jj+1]<a.t[jj]) jj++; // Il y a deux fils et le second est le plus petit. if(x<=a.t[jj]) return; // Le plus petit fils est plus grand que x=t[j] qui est donc à sa place définitive. a.t[j]=a.t[jj]; // On échange x avec son plus petit fils. a.t[j=jj]=x; } } void ajoute(tas *aa,element x) // ajoute l'élément x dans le tas a { if(++aa->n>aa->nmax) printf("Le tas déborde\n"),exit(1); aa->t[aa->n]=x; // On met x dans t[++n] remonte(*aa,aa->n); // puis on le remonte à sa place. } element enlevepp(tas *aa) // On enlève t[1] et on le sauvegarde dans x car ce sera la valeur rendue par la fonction { element x=aa->t[1]; if(!aa->n) printf("Le tas est vide\n"),exit(1); aa->t[1]=aa->t[aa->n--]; // On bouche le trou en t[1] avec le dernier élément t[n--] descend(*aa,1); // Puis le fait descendre à sa place return x; } void arrangetas1(tas a) // Permute les n éléments de t pour en faire un tas. Méthode lente en O(n ln(n)) { int i; for(i=2;i<=a.n;i++) remonte(a,i); } void arrangetas2(tas a) // Permute les n éléments de t pour en faire un tas. Méthode rapide en O(n) { int i; for(i=a.n/2;i;i--) descend(a,i); } void tritas1(int n,element t[]) { tas a={t-1,n,n}; // a.t[1] est (t-1)[1] c'est-à-dire t[0] ne marche pas nécessairement selon la norme ansi. arrangetas1(a); // On fait un tas de n éléments while(a.n) {element x=enlevepp(&a); t[a.n]=x;} // Tant que le tas n'est pas vide, on enlève son plus petit élément. On ne peut écrire } // t[a.n]=enlevepp(&a); car on ne sait pas si le compilateur va prendre l'ancienne ou la nouvelle valeur de a.n qui diminue de 1. void tritas2(int n,element t[]) { tas a={t-1,n,n}; arrangetas2(a); while(a.n) {element x=enlevepp(&a); t[a.n]=x;} } int main() { int j,f,n=10; for(f=0;f<2;f++) { element t[n]; for(j=0;j<n;j++) t[j]=j*3%n; (f?tritas1:tritas2)(n,t); for(j=0;j<n;j++) printf(" %d",t[j]); printf("\n"); } return 0; }

Vendredi 21 décembre 2007 : Dijkstra

#include<values.h> typedef struct {int nn, *t, *pos, *dist;} tas; void echange(tas t,int i,int j) { int x=t.t[i], y=t.t[j]; t.t[i]=y, t.pos[y]=i; t.t[j]=x, t.pos[x]=j; } #define le(i,j) (t.dist[t.t[i]]<=t.dist[t.t[j]]) void remonte(tas t,int j) { for(;;) { int jj=j/2; if(!jj) return; if(le(jj,j)) return; echange(t,j,jj); j=jj; } } void descend(tas t,int j) { for(;;) { int jj=j+j; if(jj>t.nn) return; if(jj<t.nn && le(jj+1,jj)) jj++; if(le(j,jj)) return; echange(t,j,jj); j=jj; } } #undef le int otepp(tas *t) { echange(*t,1,t->nn--); descend(*t,1); return t->t[t->nn+1]; } void dijkstra(graphe2 g2, int poids[n], sommet dep, int dist[n]) { int tete[n+a], *suite=tete+n, pos[n], tt[n+1], i, k; tas t={n,tt,pos,dist}; g2ts(g2,tete); for(i=0;i<n;i++) tt[pos[i]=i+1]=i, dist[i]=MAXINT; echange(t,1,dep+1); dist[dep]=0; while(t.nn && dist[i=otepp(&t)]!=MAXINT) for(k=tete[i];k>=0;k=suite[k]) { sommet j=g2[k].ext; int d=dist[i]+poids[k]; if(d<dist[j]) dist[j]=d, remonte(t,pos[j]); } }

Vendredi 11 janvier 2008 : Dijkstra

#define n 100000 #define a 103333 sommet depart=10001, arrivee=10000; { int i, k=0; printf("arcs i --> 3i+1 et i --> 5i+1 et 2i --> i de poids respectifs 2, 11 et 1\n"); for (i=0;3*i+1< n;i++) g2[k].ori=i, g2[k].ext=3*i+1, poids[k++]=2; for (i=0;5*i+1< n;i++) g2[k].ori=i, g2[k].ext=5*i+1, poids[k++]=11; for (i=0;2*i < n;i++) g2[k].ori=2*i, g2[k].ext=i, poids[k++]=1; printf("n=%d k=%d a=%d\n",n,k,a); if(k!=a) exit(1); } retg2(g2); dijkstra(g2,poids,arrivee,dist); retg2(g2); for(i=0;i<n && i<100;i++) printf("%d ",dist[i]); printf("\n"); { int tete[n+a], *suite=tete+n, s,k; g2ts(g2,tete); for(k=tete[s=depart];k>=0;k= dist[g2[k].ext]+poids[k]==dist[s] ? printf(" %d(%d)",s,dist[s]), tete[s=g2[k].ext] : suite[k]) ; printf(" %d(%d)\n",s,dist[s]); }