Langage C et structures de données licence MASS 2004--2005

lundi 4 octobre et mardi 5 octobre 2004 : premiers programmes en C

bonjour

#include<stdio.h>
int main()
{ printf("Bonjour");
  getchar();
  return 0;
}

21+7=28

#include<stdio.h>
int mini(int a,int b) {return a<b ? a : b;}
int maxi(int a,int b) {return a>b ? a : b;}
int pgcd(int a,int b) {return b ? pgcd(b,a%b) : a;}
int Pgcd(int a,int b) {while(b) {int c=a%b; a=b; b=c;} return a;}
int main()
{ int a,b;
  printf("Donnez deux nombres : ");
  scanf("%d%d",&a,&b);
  printf("%d*%d=%d\n",a,b,a*b);   // produit
  printf("%d/%d=%d\n",a,b,a/b);   // quotient
  printf("%d%%%d=%d\n",a,b,a%b);  // reste
  printf("%d+%d=%d\n",a,b,a+b);   // somme
  printf("%d-%d=%d\n",a,b,a-b);   // différence
  printf("%d>>%d=%d\n",a,b,a>>b); // décalage à droite
  printf("%d<<%d=%d\n",a,b,a<<b); // décalage à gauche
  printf("%d&%d=%d\n",a,b,a&b);   // et bit à bit
  printf("%d^%d=%d\n",a,b,a^b);   // ou exclusif bit à bit
  printf("%d|%d=%d\n",a,b,a|b);   // ou bit à bit
  printf("Le plus petit des deux est %d\n",mini(a,b));
  printf("Le plus grand des deux est %d\n",maxi(a,b));
  printf("Leur pgcd est %d\n",pgcd(a,b));
  printf("Leur pgcd est %d\n",Pgcd(a,b));
  printf("~%d=%d\n",a,~a);
  getchar();
  getchar();
  return 0;
}

réels : float, double et long double

#include<stdio.h>
#include<math.h>
int main()
{ double r;
  printf("Quel est le rayon du cercle ? ");
  scanf("%lf",&r);
  printf("Le diamètre est %20.15lf\n",2*r);
  printf("La circonférence est %20.15lf\n",2*r*M_PI);
  printf("La surface est %20.15lf\n",r*r*M_PI);
  getchar();
  getchar();
  return 0;
}

#include<stdio.h>
#include<math.h>
int main()
{ long double r;
  const long double pi=acosl(-1); // M_PI est un double
  printf("Quel est le rayon du cercle ? ");
  scanf("%Lf",&r);
  printf("Le diamètre est %30.19Lf\n",2*r);
  printf("La circonférence est %30.19Lf\n",2*r*pi);
  printf("La surface est %30.19Lf\n",r*r*pi);
  getchar();
  getchar();
  return 0;
}
                                          float    double     long double
  format                                   %f       %lf         %Lf
taille (en octets)                         4         8          10
précision (nombre de chiffres décimaux)    6        15          19
fonction sinus                            sinf      sin        sinl

entiers signés ou entiers non signés ? (signed int or unsigned int ?)

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{ printf("%d %d %u %u\n",-1,-1u,-1,-1u);
  cout<<-1<<' '<<-1u<<'\n';
  getchar();
  return 0;
}

-1 -1 4294967295 4294967295
-1 4294967295

expressions et instructions

valeur                 effet
5                       5                    aucun
5+2                     7                    aucun
a                     valeur de a            aucun 
a+3                   (valeur de a)+3        aucun
a=4                    4                     la valeur de a devient 4 
i++                    ancienne valeur de i  la valeur de i augmente de 1
++i                    nouvelle valeur de i  la valeur de i augmente de 1
(a=4)+3                7                     la valeur de a devient 4 
a=i++                  ancienne valeur de i  la valeur de i augmente de 1 et a prend l'ancienne valeur de i

5;
5+2;
a;
a+3;

lundi 11 et mardi 12 octobre 2004

a=2,b=i==3?*t++[4+a++]->x1.x2,4:5,a+b;
                  ---
                4+ 2
                 6
           ------------------,4
      ----?                  4 :5   
 2 ,b=      (4 ou 5)             , 7 
 2 ,        (4 ou 5)             , 7 

for=while

mardi 12 octobre : boucles for et tableaux

#include<stdio.h>
int main()
{ int n,i,j;
  printf("Combien de nombres ? ");
  scanf("%d",&n);
  for(i=1;i<=n;++i) printf("%d ",i);
  printf("\n");
  for(i=n;i;--i) printf("%d ",i);
  printf("\n");
  for(i=1;i<=n;++i,printf("\n")) for(j=1;j<=n;++j) printf("%4d",i*j);
  for(i=1;i<=n;++i,printf("\n")) for(j=1;j<=i;++j) printf("%4d",1  );
  int t[n][n];
  for(i=0;i<n;++i,printf("\n")) for(j=0;j<=i;++j)
   printf("%4d",t[i][j]= !j || j==i ? 1 : t[i-1][j]+t[i-1][j-1]);
  int u[n];
  for(i=0;i<n;++i,printf("\n")) for(j=i;j>=0;--j)
   printf("%4d",u[j]= !j || j==i ? 1 : u[j]+u[j-1]);
  return 0;
}
Combien de nombres ? 5
1 2 3 4 5 
5 4 3 2 1 
   1   2   3   4   5
   2   4   6   8  10
   3   6   9  12  15
   4   8  12  16  20
   5  10  15  20  25
   1
   1   1
   1   1   1
   1   1   1   1
   1   1   1   1   1
   1
   1   1
   1   2   1
   1   3   3   1
   1   4   6   4   1
   1
   1   1
   1   2   1
   1   3   3   1
   1   4   6   4   1

lundi 18 et mardi 19 octobre 2004

passage de fonction en argument à une procédure

#include<stdio.h>
typedef int typef1(int);
void testf1(typef1 f)
{ int i;
  for(i=1;i<=10;++i) printf("%2d %d\n",i,f(i));
}
int add2(int x){return x+2;}
int mul2(int x){return x*2;}
int main()
{ testf1(add2);
  testf1(mul2);
  return 0;
}

 1 3
 2 4
 3 5
 4 6
 5 7
 6 8
 7 9
 8 10
 9 11
10 12
 1 2
 2 4
 3 6
 4 8
 5 10
 6 12
 7 14
 8 16
 9 18
10 20

copie de chaînes de caractères

#include<stdio.h>
#include<string.h>
int main()
{ char t[]="Il fait beau.", s[strlen(t)+1];
  int i,j;
  for(i=0;(s[i]=t[i]);++i) ;
  printf("%s\n%s\n",t,s);
  for(i=0;(s[i]=t[i]==' '?',':t[i]);++i) ;
  printf("%s\n",s);
  for(i=j=0;t[i]==' ' || (s[j++]=t[i]);++i) ;
  printf("%s\n",s);
  return 0;
}

Il fait beau.
Il fait beau.
Il,fait,beau.
Ilfaitbeau.

comparaison de chaînes de caractères

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{ char *t[]={"Jules","Antoine","Paul","Simon","Adrien","Paul","Vincent",0};
  int i,j;
  for(i=0;t[i];++i) for(j=i+1;t[j];j++) if(!strcmp(t[i],t[j]))
  printf("%s apparaît deux fois en positions %d et %d.\n",t[i],i,j), exit(0);
  printf("Tous les noms sont différents.\n");
  return 0;
}

Paul apparaît deux fois en positions 2 et 5.

lundi 25 octobre 2004 : tableau de chaînes de caractères

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{ char *t[]={"Jules","Antoine","Paul","Simon","Adrien","Paul","Vincent",0},*x,c;
  int i,j,l;
  for(i=0  ;t[i];++i)
  for(j=i+1;t[j];++j)
  if(!strcmp(t[i],t[j]))
  { printf("%s apparaît deux fois en positions %d et %d.\n",t[i],i,j);
    goto suite;
  }
  printf("Tous les noms sont différents.\n");
  suite:
  
  for(i=0;t[i];++i) printf("%s ",t[i]);
  printf("\n");
  
  for(i=0  ;t[i];++i)
  for(j=i+1;t[j];++j)
  if(strcmp(t[i],t[j])>0) x=t[i],t[i]=t[j],t[j]=x;
  
  for(i=0;t[i];++i) printf("%s ",t[i]);
  printf("\n");

  for(i=0;t[i];++i) t[i]=strcpy(malloc(strlen(t[i])+1),t[i]);
  
  for(i=0;t[i]   ;++i)
  for(j=0;t[i][j];++j)
  if(t[i][j]=='e') t[i][j]='E'; 
  
  for(i=0;t[i];++i) printf("%s ",t[i]);
  printf("\n");

  for(i=0;t[i];++i)
  for(j=0,l=strlen(t[i])-1;j<l;++j,--l)
  c=t[i][j], t[i][j]=t[i][l], t[i][l]=c; 

  for(i=0;t[i];++i) printf("%s ",t[i]);
  printf("\n");
  
  return 0;
}

Paul apparaît deux fois en positions 2 et 5.
Jules Antoine Paul Simon Adrien Paul Vincent
Adrien Antoine Jules Paul Paul Simon Vincent
AdriEn AntoinE JulEs Paul Paul Simon VincEnt
nEirdA EniotnA sEluJ luaP luaP nomiS tnEcniV

mardi 26 octobre 2004 : pointeurs

pointeurs et chaînes de caractères : abracadabra

#include<stdio.h>
#include<string.h>
#define abra "abracadabra"
int main()
{ char s[]=abra, t[]=abra, *x,*y,c;
  for(x=s,y=s+strlen(s)-1;x<y;x++,y--) c=*x,*x=*y,*y=c;
  printf("%s\n",s);
  for(x=t;*x;x++) printf("%s\n",x);
  for(x=t+strlen(t);*t;*--x=0) printf("%s\n",t);
  for(x=s;*x;++x)
  for(y=x;*y;++y) if(*x>*y) c=*x,*x=*y,*y=c;
  printf("%s\n",s);
  return 0;
}

arbadacarba
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
a
abracadabra
abracadabr
abracadab
abracada
abracad
abraca
abrac
abra
abr
ab
a
aaaaabbcdrr

pointeurs et tableaux d'entiers

#include<stdio.h>
int som(int *t,int n) {int s=0; for(;n;--n) s+=*t++; return s;} 
void aff(int *t,int n) {for(;n;--n) printf("%d ",*t++); } 
#define ex(a) printf(#a" : "),a,printf("\n")
#define ev(a) printf(#a" : %d\n",a)
int main()
{ const int n=10;
  int t[n], i;
  for(i=0;i<n;++i) t[i]=i*3%n;
  ex(aff(t,n));
  ex(aff(t+3,4));
  ev(som(t,n));
  ev(som(t+3,4));
  return 0;
}

aff(t,n) : 0 3 6 9 2 5 8 1 4 7
aff(t+3,4) : 9 2 5 8
som(t,n) : 45
som(t+3,4) : 24

mardi 2 novembre 2004 : passage d'arguments

#include<stdio.h>
#include<math.h>
void cercle(double rayon,double *diametre,double *circonference,double *surface)
{ *diametre=2*rayon;
  *circonference=*diametre*M_PI;
  *surface=rayon*rayon*M_PI;
}
int main()
{ double r,d,c,s;
  printf("Rayon ? ");
  scanf("%lf",&r);
  cercle(r,&d,&c,&s);
  printf("Diamètre : %lf\nCirconférence : %lf\nSurface : %lf\n",d,c,s);
  return 0;
}

Rayon ? 5
Diamètre : 10.000000
Circonférence : 31.415927
Surface : 78.539816

#include<stdio.h>
#include<math.h>
void cercle(double rayon,double &diametre,double &circonference,double &surface)
{ diametre=2*rayon;
  circonference=diametre*M_PI;
  surface=rayon*rayon*M_PI;
}
int main()
{ double r,d,c,s;
  printf("Rayon ? ");
  scanf("%lf",&r);
  cercle(r,d,c,s);
  printf("Diamètre : %lf\nCirconférence : %lf\nSurface : %lf\n",d,c,s);
  return 0;
}

#include<stdio.h>
#include<math.h>

double arith(double a,double b) {return (a+b)/2;}
double geom (double a,double b) {return sqrt(a*b);}
double harm (double a,double b) {return 2*a*b/(a+b);}

double arithgeom(double a,double b)
{ double c=arith(a,b), d=geom(a,b);
  return a==c || b==d ? a : arithgeom(c,d);
}

typedef double moy(double,double);

double moymm(double a,double b,moy m1,moy m2)
{ double c=m1(a,b), d=m2(a,b);
  return a==c || b==d ? a : moymm(c,d,m1,m2);
}

void testmoy(double a,double b)
{ printf("moyennes de %lf et %lf\n",a,b);
  printf("arithmétique : %lf\n",arith(a,b));
  printf("harmonique : %lf\n",harm(a,b));
  printf("géométrique : %lf = %lf\n",geom(a,b),moymm(a,b,arith,harm));
  printf("arithméticogéométrique : %lf = %lf =%lf\n",arithgeom(a,b),moymm(a,b,arith,geom),
   1/moymm(1/a,1/b,geom,harm));
}

int main()
{ testmoy(1,2);
  testmoy(2,4);
  testmoy(1,4);
  return 0;
}

moyennes de 1.000000 et 2.000000
arithmétique : 1.500000
harmonique : 1.333333
géométrique : 1.414214 = 1.414214
arithméticogéométrique : 1.456791 = 1.456791 =1.456791
moyennes de 2.000000 et 4.000000
arithmétique : 3.000000
harmonique : 2.666667
géométrique : 2.828427 = 2.828427
arithméticogéométrique : 2.913582 = 2.913582 =2.913582
moyennes de 1.000000 et 4.000000
arithmétique : 2.500000
harmonique : 1.600000
géométrique : 2.000000 = 2.000000
arithméticogéométrique : 2.243029 = 2.243029 =2.243029

lundi 8 et mardi 9 novembre 2004 : passage de tableaux, tris

#include<stdio.h>
/*
void afft(int n,int t[n])
{ int i;
  for(i=0;i<n;i++) printf("%d ",t[i]);
  printf("\n");
}
int somm(int n,int t[n])
{ int i,s=0;
  for(i=0;i<n;i++) s+=t[i];
  return s;
}
int prod(int n,int t[n])
{ int i,p=1;
  for(i=0;i<n;i++) p*=t[i];
  return p;
}
int maxt(int n,int t[n])
{ int i,m=*t;
  for(i=0;i<n;i++) if(m<t[i]) m=t[i];
  return m;
}
void retourne(int n,int t[n])
{ int i,j,x;
  for(i=0,j=n-1;i<j;i++,j--) x=t[i],t[i]=t[j],t[j]=x;
}
/*/
void afft(int n,int t[n])
{ for(;n;n--,t++) printf("%d ",*t);
  printf("\n");
}
int somm(int n,int t[n])
{ int s=0;
  for(;n;n--,t++) s+=*t;
  return s;
}
int prod(int n,int t[n])
{ int p=1;
  for(;n;n--,t++) p*=*t;
  return p;
}
int maxt(int n,int t[n])
{ int m=*t;
  for(;n;n--,t++) if(m<*t) m=*t;
  return m;
}
void retourne(int n,int t[n])
{ int *s,x;
  for(s=t+n-1;t<s;t++,s--) x=*t,*t=*s,*s=x;
}
//*/
int posmax(int n,int t[n])
{ int i,j=0;
  for(i=0;i<n;i++) if(t[j]<t[i]) j=i;
  return j;
}
int *ppmax(int n,int t[n])
{ int *s=t;
  for(;n;n--,t++) if(*s<*t) s=t;
  return s;
}
void triselection1(int n,int t[n])
{ for(;n;n--)
  { int i=posmax(n,t), x;
    x=t[i],t[i]=t[n-1],t[n-1]=x;
  }
}
void triselection2(int n,int t[n])
{ for(;n;n--)
  { int *p=ppmax(n,t), x;
    x=*p,*p=t[n-1],t[n-1]=x;
  }
}
void fusion(int n1,int t1[n1],int n2,int t2[n2],int t3[n1+n2])
{ // int n3=n1+n2;
  // printf("fusion %d %d %d\n",n1,n2,n3);
  // afft(n1,t1);
  // afft(n2,t2);
  while(n1 || n2) if (!n2 || (n1 && *t1<*t2)) *t3++=*t1++, n1--;
                  else                        *t3++=*t2++, n2--;
  // afft(n3,t3-n3);
}
void trifusion(const int n, int t[n])
{ if(n<=1) return;      // Si le tableau n'a qu'un seul élèment, il est déjà trié.
  const int m=n/2;
  trifusion(m,t);       // tri de la première moitié
  trifusion(n-m,t+m);   // tri de la deuxième moitié
  int tt[m], i;
  for(i=0;i<m;i++) tt[i]=t[i];  // copie de la première moitié
  fusion(m,tt,n-m,t+m,t);       // fusion des deux moitiés déjà triées
}
void trirapide(const int n, int t[n])
{ if(n<=1) return;      // Si le tableau n'a qu'un seul élèment, il est déjà trié.
  int *d=t, *f=t+n-1, p=*t, x;
  for(;;d++,f--)
  { while(*d<p) d++;
    while(*f>p) f--;
    if(d>=f) break;
    x=*d,*d=*f,*f=x;
  }
  trirapide(d-t,t);
  trirapide(t+n-f-1,f+1);
}
void testtri(void tri(int,int[]))
{ int t[20], i ,x=1;
  for(i=0;i<20;i++) t[i]=x=3*x%100;
  afft(20,t);
  tri (20,t);
  afft(20,t);
}
#define aff0(a) printf(#a" : "),a
#define affd(a) printf(#a" : %d\n",(a))
int main()
{ int t[20], i ,x=1;
  for(i=0;i<20;i++) t[i]=x=3*x%100;
  aff0(afft(20,t));
  aff0(afft(4,t+3));
  aff0(retourne(7,t+5));
  aff0(afft(20,t));
  affd(prod(5,t));
  affd(somm(3,t+3));
  affd(maxt(10,t+6));
  testtri(triselection1);
  testtri(triselection2);
  testtri(trifusion);
  testtri(trirapide);
  return 0;
}

afft(20,t) : 3 9 27 81 43 29 87 61 83 49 47 41 23 69 7 21 63 89 67 1
afft(4,t+3) : 81 43 29 87
retourne(7,t+5) : afft(20,t) : 3 9 27 81 43 41 47 49 83 61 87 29 23 69 7 21 63 89 67 1
prod(5,t) : 2539107
somm(3,t+3) : 165
maxt(10,t+6) : 87
3 9 27 81 43 29 87 61 83 49 47 41 23 69 7 21 63 89 67 1
1 3 7 9 21 23 27 29 41 43 47 49 61 63 67 69 81 83 87 89
3 9 27 81 43 29 87 61 83 49 47 41 23 69 7 21 63 89 67 1
1 3 7 9 21 23 27 29 41 43 47 49 61 63 67 69 81 83 87 89
3 9 27 81 43 29 87 61 83 49 47 41 23 69 7 21 63 89 67 1
1 3 7 9 21 23 27 29 41 43 47 49 61 63 67 69 81 83 87 89
3 9 27 81 43 29 87 61 83 49 47 41 23 69 7 21 63 89 67 1
1 3 7 9 21 23 27 29 41 43 47 49 61 63 67 69 81 83 87 89

lundi 15 et mardi 16 novembre 2004 : structures

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct personne personne, *pp;
struct personne{char *prenom, sexe; pp pere,mere;};
pp t[9];
void init()
{ int i;                                            //  antoine       jean+julie
  for(i=0;i<9;i++) t[i]=malloc(sizeof(personne));   //     |      +-------+------+      
  const pp antoine=t[0], jeanne =t[1], henri  =t[2],//   jeanne+hubert  hector aurelie
           hubert =t[3], hector =t[4], aurelie=t[5],//         |                  |
           claire =t[6], jean   =t[7], julie  =t[8];//       henri              claire
  antoine->prenom="antoine";  antoine->pere=0;         antoine->mere=0;
  jeanne ->prenom="jeanne" ;  jeanne ->pere=antoine;   jeanne ->mere=0;
  henri  ->prenom="henri"  ;  henri  ->pere=hubert;    henri  ->mere=jeanne;
  hubert ->prenom="hubert" ;  hubert ->pere=jean;      hubert ->mere=julie;
  hector ->prenom="hector" ;  hector ->pere=jean;      hector ->mere=julie;
  aurelie->prenom="aurelie";  aurelie->pere=jean;      aurelie->mere=julie;
  claire ->prenom="claire" ;  claire ->pere=0;         claire ->mere=aurelie;
  jean   ->prenom="jean"   ;  jean   ->pere=0;         jean   ->mere=0;
  julie  ->prenom="julie"  ;  julie  ->pere=0;         julie  ->mere=0;
}
void sexualisation()
{ int i;
  for(i=0;i<9;i++) t[i]->sexe='i';
  for(i=0;i<9;i++)
  { if(t[i]->pere) t[i]->pere->sexe='m';
    if(t[i]->mere) t[i]->mere->sexe='f';
  }
}
void affpp(pp a)
{ printf("%s(%c)",a->prenom,a->sexe);
  if(a->mere) printf(" Sa mere est %s." ,a->mere->prenom);
  if(a->pere) printf(" Son pere est %s.",a->pere->prenom);
  printf("\n");
}
void afft() {int i; printf("\n"); for(i=0;i<9;i++) affpp(t[i]);}
void trichrono()
{ int i,j;
  pp x;
  for(i=0;i<9;i++)
  for(j=i;++j<9;)
  if(t[i]->pere==t[j] || t[i]->mere==t[j]) x=t[i],t[i]=t[j],t[j]=x,j=i;
}
void trialpha()
{ int i,j;
  pp x;
  for(i=0;i<9;i++)
  for(j=i;++j<9;)
  if(strcmp(t[i]->prenom,t[j]->prenom)>0) x=t[i],t[i]=t[j],t[j]=x;
}
int main()
{ init(); sexualisation();
  afft();
  trichrono();
  afft();
  trialpha();
  afft();
  trichrono();
  afft();
  return 0;
}

antoine(m)
jeanne(f) Son pere est antoine.
henri(i) Sa mere est jeanne. Son pere est hubert.
hubert(m) Sa mere est julie. Son pere est jean.
hector(i) Sa mere est julie. Son pere est jean.
aurelie(f) Sa mere est julie. Son pere est jean.
claire(i) Sa mere est aurelie.
jean(m)
julie(f)

antoine(m)
jeanne(f) Son pere est antoine.
jean(m)
julie(f)
hector(i) Sa mere est julie. Son pere est jean.
aurelie(f) Sa mere est julie. Son pere est jean.
claire(i) Sa mere est aurelie.
hubert(m) Sa mere est julie. Son pere est jean.
henri(i) Sa mere est jeanne. Son pere est hubert.

antoine(m)
aurelie(f) Sa mere est julie. Son pere est jean.
claire(i) Sa mere est aurelie.
hector(i) Sa mere est julie. Son pere est jean.
henri(i) Sa mere est jeanne. Son pere est hubert.
hubert(m) Sa mere est julie. Son pere est jean.
jean(m)
jeanne(f) Son pere est antoine.
julie(f)

antoine(m)
jean(m)
julie(f)
hector(i) Sa mere est julie. Son pere est jean.
hubert(m) Sa mere est julie. Son pere est jean.
jeanne(f) Son pere est antoine.
aurelie(f) Sa mere est julie. Son pere est jean.
henri(i) Sa mere est jeanne. Son pere est hubert.
claire(i) Sa mere est aurelie.

lundi 22 novembre 2004 : serètcarac ed senîahc

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char*concat(char*s,char*t)
{ char *p=malloc(strlen(s)+strlen(t)+1), *q=p;
  while(*s) *q++=*s++;
  while(*t) *q++=*t++;
  *q=0;
  return p;
}
char*retourne(char*s)
{ int l=strlen(s);
  char *p=malloc(l+1), *q=p;
  for(s+=l;l;l--) *q++=*--s;
  *q=0;
  return p;
}
char*retourne2(char*s)
{ int l=strlen(s);
  char *p=malloc(l+1)+l;
  *p=0;
  while(*s) *--p=*s++;
  return p;
}
char*maj(char*s)
{ char *p=malloc(strlen(s)+1), *q;
  for(q=p;*s;s++,q++) *q=*s>='a' && *s<='z' ? *s+'A'-'a' : *s;
  return p;
}
int main()
{ char *s="Esope reste ici et se repose.", *t="Tu l'as trop écrasé, César, ce port-salut.";
  printf("%s%s\n","bon","jour"); 
  printf("%s\n",concat("bon","jour"));
  printf("%s<-->%s\n",s,retourne(s));
  printf("%s<-->%s\n",t,retourne2(t));
  printf("%s %s\n",maj(s),maj(t));
  return 0;
}

bonjour
bonjour
Esope reste ici et se repose.<-->.esoper es te ici etser eposE
Tu l'as trop écrasé, César, ce port-salut.<-->.tulas-trop ec ,raséC ,ésarcé port sa'l uT
ESOPE RESTE ICI ET SE REPOSE. TU L'AS TROP éCRASé, CéSAR, CE PORT-SALUT.

mardi 23 novembre 2004 : listes chaînées

lundi 29 novembre 2004 : insertion en fin de liste chaînée

mardi 30 novembre 2004 : tri fusion de liste chaînée

#include<stdio.h>
#include<stdlib.h>
typedef struct chainon chainon, *liste;
struct chainon{int val; liste suite;};
void aff(liste l)
{ for(;l;l=l->suite) printf("%d ",l->val);
  printf("\n");
}
liste nouv(int val, liste suite)
{ liste a=malloc(sizeof(*a));
  a->val=val;
  a->suite=suite;
  return a;
}
liste copie(liste l) {return l ? nouv(l->val,copie(l->suite)) : 0;}
int   somre(liste l) {return l ?      l->val+somre(l->suite)  : 0;}
int   somit(liste l)
{ int s=0;
  for(;l;l=l->suite) s+=l->val;
  return s;
}
void add1(liste l) {for(;l;l=l->suite) l->val++;}
liste eipoc(liste l)
{ liste p=0;
  for(;l;l=l->suite) p=nouv(l->val,p);
  return p;
}
liste retourne(liste l)
{ liste p=0;
  while(l)
  { liste q=l; l=l->suite, // on enleve un chainon q en tete de l
    q->suite=p, p=q;       // on le met en tete de p
  }
  return p;
}
void retour(liste *l) {*l=retourne(*l);}
void affrec(liste l) {if(l) printf("%d ",l->val), affrec(l->suite);}
void ffa   (liste l) {if(l) ffa   (l->suite), printf("%d ",l->val);}
typedef struct {liste tete,fin;} lliste;
// tete pointe sur le premier chainon et fin sur le dernier.
// La liste est vide ssi tete==0, et dans ce cas fin n'est pas défini.
void ajoutetete(lliste *a,int x)
{ a->tete=nouv(x,a->tete);
  if(!a->tete->suite) a->fin=a->tete;  // la liste etait vide
}
void ajoutefin(lliste *a,int x)
{ if(!a->tete) return ajoutetete(a,x); // la liste est vide
  a->fin->suite=nouv(x,0);
  a->fin=a->fin->suite;
}
int enlevetete(lliste *a,int *x)
{ if(!a->tete) return 0;
  liste l=a->tete;
  *x     =l->val;
  a->tete=l->suite;
  free(l);
  return 1;
}
liste fusionrec(liste a,liste b)
{ return !a ? b :
         !b ? a :
         b->val>a->val ? a->suite=fusionrec(a->suite,b), a :
                       ( b->suite=fusionrec(b->suite,a), b );
}
liste fusionit(liste a,liste b)
{ liste c,r;
  if(!a) return b;
  if(!b) return a;
  if(b->val>a->val) c=r=a, a=a->suite;
  else              c=r=b, b=b->suite;
  while(a && b)
  if(b->val>a->val) c->suite=a, a=a->suite, c=c->suite;
  else              c->suite=b, b=b->suite, c=c->suite;
  c->suite=a ? a : b;
  return r;
}
liste fusionit2(liste a,liste b)
{ liste c, *l=&c;
  while(a && b) if(b->val>a->val) *l=a, l=&a->suite, a=*l;
                else              *l=b, l=&b->suite, b=*l;
  *l=a ? a : b;
  return c;
}
#define fusion fusionit2
liste trifusion(liste l)
{ liste p=0,r=0;
  while(l)
  { liste q=l; l=q->suite, // on enleve un chainon q en tete de l
    q->suite=p, p=r, r=q;  // on le met en tete de p, puis on echange p et r
  }
  return !p ? r : fusion(trifusion(p),trifusion(r));
}
int main(){ liste l=nouv(3,nouv(7,nouv(5,nouv(1,0)))), k=copie(l), m=l;
  affrec(l), ffa(l), printf("\n");
  aff(l), aff(k), aff(m);
  printf("%d=%d\n",somre(l),somit(l));
  add1(l);
  aff(l), aff(k), aff(m=eipoc(m));
  lliste ll={0,0};
  int x,y;
  for(x=0;x<10;x++) (x&1 ? ajoutetete : ajoutefin)(&ll,x), aff(ll.tete);
  while(enlevetete(&ll,&x) && enlevetete(&ll,&y)) ajoutefin(&ll,x+y-3), aff(ll.tete);
  for(x=1;x;x=(x*2+1)%11) l=nouv(x,l);
  aff(l);
  retour(&l);
  aff(l);
  aff(l=trifusion(l));
  return 0;
}

3 7 5 1 1 5 7 3
3 7 5 1
3 7 5 1
3 7 5 1
16=16
4 8 6 2
3 7 5 1
2 6 8 4
0
1 0
1 0 2
3 1 0 2
3 1 0 2 4
5 3 1 0 2 4
5 3 1 0 2 4 6
7 5 3 1 0 2 4 6
7 5 3 1 0 2 4 6 8
9 7 5 3 1 0 2 4 6 8
5 3 1 0 2 4 6 8 13
1 0 2 4 6 8 13 5
2 4 6 8 13 5 -2
6 8 13 5 -2 3
13 5 -2 3 11
-2 3 11 15
11 15 -2
-2 23
18
5 2 6 8 9 4 7 3 1 4 8 6 2
2 6 8 4 1 3 7 4 9 8 6 2 5
1 2 2 3 4 4 5 6 6 7 8 8 9

lundi 6 et mardi 7 décembre 2004 : listes doublement chaînées

lundi 6 décembre 2004 : anneaux

#include<stdio.h>
#include<stdlib.h>
typedef struct chainon *anneau;
struct chainon{int val; anneau suite,prec;};
anneau nouv(int val)
{ anneau a=malloc(sizeof(*a));
  a->val=val;
  return a->suite=a->prec=a;
}
void croise(anneau a,anneau b)
{ anneau c;
  c=a->suite, a->suite=b->suite, b->suite=c;
  a->suite->prec=a;
  b->suite->prec=b;
}
void aff(anneau a)
{ anneau b=a;
  do printf(" %d",a->val), a=a->suite; while(a!=b);
  printf("\n");
}
anneau copie(anneau a)
{ anneau b=a, x=nouv(a->val);
  for(;a=a->prec,a!=b;) croise(x,nouv(a->val));
  return x;
}
int longueur(anneau a)
{ int j=0;
  anneau b=a;
  do j++, a=a->suite; while(a!=b);
  return j;
}
int somme(anneau a)
{ int j=0;
  anneau b=a;
  do j+=a->val, a=a->suite; while(a!=b);
  return j;
}
void retourne1(anneau a)
{ anneau b=a->suite, c;
  while(c=b->suite,c!=a) croise(b,c), croise(a,c);  // a x ... b c y ... -> a c x ... b y ...
}
void retourne2(anneau a)
{ anneau b=a, c;
  do c=a->suite, a->suite=a->prec, a->prec=c, a=c; while(a!=b);
}
void add1(anneau a)
{ anneau b=a;
  do a->val++, a=a->suite; while(a!=b);
}
int memeanneau(anneau a,anneau b)
{ anneau c=a;
  for(;;) if(a==b) return 1; else if(a=a->suite, a==c) return 0;
}
int main()
{ int j;
  anneau a=nouv(3);
  for(j=4;j<10;j++) croise(a,nouv(j));
  aff(a);
  anneau b=copie(a);
  aff(b);
  retourne1(a);
  aff(a);
  retourne2(a);
  aff(a);
  printf("longueur : %d  somme : %d\n",longueur(a),somme(a));
  add1(a);
  aff(a);
  printf("%d %d\n",memeanneau(a,a->prec), memeanneau(a,b));
  return 0;
}

 3 9 8 7 6 5 4
 3 9 8 7 6 5 4
 3 4 5 6 7 8 9
 3 9 8 7 6 5 4
longueur : 7  somme : 42
 4 10 9 8 7 6 5
 1 0

mardi 7 décembre 2004 : listes triées terminées par des pointeurs nuls

#include<stdio.h>
#include<stdlib.h>
typedef struct chainon *liste;
struct chainon{int val; liste suite,prec;};
void aff(liste p)
{ for(;p;p=p->suite) printf("%d ",p->val);
  printf("\n");
}
liste inseretrie(liste l,int val)
{ liste p=0, s=l, x=malloc(sizeof(*x));
  while(s && val>s->val) p=s, s=s->suite;
  x->val=val;
  x->suite=s;
  x->prec =p;
  if(p) p->suite=x; else l=x;
  if(s) s->prec =x;
  return l;
}
liste otetrie(liste l,int val)
{ liste s=l;
  while(s && val>s->val) s=s->suite;
  if(!s || s->val!=val) return l;
  if(s->prec ) s->prec->suite=s->suite; else l=s->suite;
  if(s->suite) s->suite->prec=s->prec;
  free(s);
  return l;
}
int main()
{ int j, t[]={3,6,1,4,10,5};
  liste x=0;
  for(j=0;j<6;j++) x=inseretrie(x,t[j]), aff(x);
  for(j=0;j<6;j++) x=   otetrie(x,t[j]), aff(x);
  return 0;
}

3
3 6
1 3 6
1 3 4 6
1 3 4 6 10
1 3 4 5 6 10
1 4 5 6 10
1 4 5 10
4 5 10
5 10
5

lundi 13 décembre 2004 : listes doublement chaînées attachées aux deux bouts

#include<stdio.h>
#include<stdlib.h>
typedef struct chainon *liste;
struct chainon{int val; liste suite,prec;};
liste nouv()
{ liste a=malloc(sizeof(*a));
  return a->suite=a->prec=a;
}
void aff(liste a)
{ liste p;
  for(p=a->suite;p!=a;p=p->suite) printf("%d ",p->val);
  printf("\n");
}
void inseretrie(liste l,int val)
{ liste s=l->suite, x=malloc(sizeof(*x));
  while(s!=l && val>s->val) s=s->suite;
  x->val=val;
  x->suite=s;
  x->prec =s->prec;
  x->prec->suite=x;
  s->prec =x;
}
void otetrie(liste l,int val)
{ liste s=l->suite;
  while(s!=l && val>s->val) s=s->suite;
  if(s==l || s->val!=val) return;
  s->prec->suite=s->suite;
  s->suite->prec=s->prec;
  free(s);
}
liste copie1(liste a)
{ liste b=nouv(), p;
  for(p=a->prec;p!=a;p=p->prec) inseretrie(b,p->val);
  return b;
}
liste copie2(liste a)
{ liste b=malloc(sizeof(*b)), p, q, r=b;
  for(p=a->suite;p!=a;p=p->suite)
  q=malloc(sizeof(*q)), q->val=p->val, q->prec=r, r->suite=q, r=q;
  b->prec=r, r->suite=b;
  return b;
}
#define copie copie2
liste fusion(liste a,liste b)
{ liste c=nouv(), p=a->prec, q=b->prec;
  while(p!=a && q!=b) if(p->val>q->val) inseretrie(c,p->val), p=p->prec;
                      else              inseretrie(c,q->val), q=q->prec;
  while(p!=a        )                   inseretrie(c,p->val), p=p->prec;
  while(        q!=b)                   inseretrie(c,q->val), q=q->prec;
  return c;
}
int main()
{ int j, t[]={3,6,1,4,10,5};
  liste x=nouv(), y, z=nouv(), u;
  for(j=0;j<6;j++) inseretrie(x,t[j]), aff(x);
  y=copie(x); aff(y);
  for(j=0;j<6;j++)    otetrie(x,t[j]), aff(x), inseretrie(z,t[j]^3);
  aff(z);
  u=fusion(y,z); aff(u);
  return 0;
}

3
3 6
1 3 6
1 3 4 6
1 3 4 6 10
1 3 4 5 6 10
1 3 4 5 6 10
1 4 5 6 10
1 4 5 10
4 5 10
5 10
5

0 2 5 6 7 9
0 1 2 3 4 5 5 6 6 7 9 10

mardi 14 décembre 2004 : arbres binaires de recherche

#include<stdio.h>
#include<stdlib.h>
typedef struct noeud *abr;
struct noeud{int val,eq;abr fg,fd;};
void aff(abr a)
{ if(a) aff(a->fg), printf("%d ",a->val), aff(a->fd);}
void affln(abr a) {aff(a), printf("\n");}
abr nouv(abr fg,int val,abr fd)
{ abr a=malloc(sizeof(*a));
  a->val=val;
  a->fg =fg;
  a->fd =fd;
  a->eq =0;
  return a;
}
abr f(int val) {return nouv(0,val,0);}
abr recherche(abr a,int val)
{ if(!a || a->val==val) return a;
  return recherche(val>a->val?a->fd:a->fg,val);
}
abr ajoute(abr a,int val)
{ if(!a) return f(val);
  if(val>a->val) a->fd=ajoute(a->fd,val);
  if(val<a->val) a->fg=ajoute(a->fg,val);
  return a;
}
void add1(abr a)
{ if(a) add1(a->fg),a->val++,add1(a->fd); }
abr copie(abr a)
{ return a?nouv(copie(a->fg),a->val,copie(a->fd)):0; }
abr oppose(abr a)
{ return a?nouv(oppose(a->fd),-a->val,oppose(a->fg)):0; }
int somme(abr a)
{ return a?somme(a->fg)+a->val+somme(a->fd):0; }
abr ote(abr a,int val)
{ if(!a) return 0;
  if(val>a->val) return a->fd=ote(a->fd,val), a;
  if(val<a->val) return a->fg=ote(a->fg,val), a;
  abr b;
  if(!a->fg) return b=a->fd, free(a), b;
  if(!a->fd) return b=a->fg, free(a), b;
  for(b=a->fd;b->fg;b=b->fg) ;
  return a->fd=ote(a->fd,a->val=b->val), a;
}
abr tourneg(abr a)   /*      a           b      */
{ abr b=a->fd;       /*     / \         / \     */
  a->fd=b->fg;       /*    x   b  -->  a   z    */
  b->fg=a;           /*       / \     / \       */
  return b;          /*      y   z   x   y      */
}
abr tourned(abr a)   /*        a  -->  b        */
{ abr b=a->fg;       /*       / \     / \       */
  a->fg=b->fd;       /*      b   z   x   a      */
  b->fd=a;           /*     / \         / \     */
  return b;          /*    x   y       y   z    */
}
abr linearise1(abr a)
{ if(!a) return a;
  while(a->fd) a=tourneg(a);
  a->fg=linearise1(a->fg);
  return a;
}
void linearise2(abr*a)
{ if(!*a) return;
  while((*a)->fd) *a=tourneg(*a);
  linearise2(&(*a)->fg);
}
void linearise3(abr*a)
{ for(;*a;a=&(*a)->fg) while((*a)->fd) *a=tourneg(*a);
}
void affarb(abr a,int n)
{ if(a) affarb(a->fd,n+1), printf("%*s%d\n",3*n,"",a->val), affarb(a->fg,n+1);
}
void affaln(abr a) {printf("\n"), affarb(a,0);}
abr raccourci(abr a,int x) // réduit la longueur de la branche menant à x
{ if(!a || x==a->val) return a;  // on est au bout de la branche
  if(      x> a->val)                                                 /*  a  -->   b    */
  { abr b=a->fd;                                                      /*   \      / \   */
    if(!b || x==b->val) return a;                                     /*    b    a      */
    if(      x> b->val) return b->fd=raccourci(b->fd,x), tourneg(a);  /*     \          */
    { abr c=b->fg;
      if(!c || x==c->val) return a;                          /*  a  -->  b                */
      if(      x> c->val) return raccourci(tourneg(a),x);    /*   \     /                 */
                          return a->fd=raccourci(a->fd,x), a;/*    b   a  ->  a  -->  c   */
    }                                                        /*   /     \      \     / \  */
  }                                                          /*  c       c      c   a     */
  { abr b=a->fg;                                             /*   \       \      \        */
    if(!b || x==b->val) return a;
    if(      x< b->val) return b->fg=raccourci(b->fg,x), tourned(a);
    { abr c=b->fd;
      if(!c || x==c->val) return a;
      if(      x< c->val) return raccourci(tourned(a),x);
                          return a->fg=raccourci(a->fg,x), a;
    }
  }
}
abr reequilibre(abr a)
{ if(a->eq>0) if(a->fd->eq>=0) return a->eq=-(--a->fd->eq), tourneg(a);
              else             a->fd=tourned(a->fd), a=tourneg(a);
  else        if(a->fg->eq<=0) return a->eq=-(++a->fg->eq), tourned(a);
              else             a->fg=tourneg(a->fg), a=tourned(a);
  a->fg->eq=a->fd->eq=0;
  if(a->eq<0) a->fd->eq= 1;
  if(a->eq>0) a->fg->eq=-1;
  a->eq=0;
  return a;
}
int haug; // booléen qui indique si la hauteur de l'arbre a varié lors de la dernière insertion
          // ou suppresion dans un avl.
abr ajouteavl(abr a,int x)
{ if(!a) return haug=1, f(x);  // L'arbre vide est remplacé par un nouveau noeud. Sa hauteur augmente donc
  if(x==a->val) return haug=0, a; // x est déjà dans l'arbre (dans sa racine). On ne le modifie pas.
  if(x<a->val) a->fg=ajouteavl(a->fg,x), haug*=-1; // On ajoute x dans le sous-arbre gauche.
  else         a->fd=ajouteavl(a->fd,x)          ; // On ajoute x dans le sous-arbre droit.
  if(!haug) return a;                              // La hauteur des fils n'a pas changé.
  if(haug!=a->eq) a->eq+=haug;     // La hauteur d'un des fils a augmenté de 1. Donc a->eq varie de 1.
  else            a=reequilibre(a);// S'il passe à 2 ou -2, on fait des rotations.   
  return haug=!!a->eq, a; // Qu'il y ait eu ou non des rotations, la hauteur de l'arbre a augmenté
}                         // si et seulement s'il n'est pas bien tassé (a->eq non nul)

abr detacheavl(abr a,int x) // Fait la même chose que oteavl(a,x) sans appel à free
{ abr b;
  if(!a) return haug=0, a;  // L'arbre est vide, donc x n'est pas dedans, on ne le modifie pas
  if(x>a->val) a->fd=detacheavl(a->fd,x), haug*=-1; else  // x est dans le sous-arbre droit
  if(x<a->val) a->fg=detacheavl(a->fg,x)          ; else  // x est dans le sous-arbre gauche
  { if(!a->fg) return haug=1, a->fd;  // x est dans la racine, qui n'a pas de fils gauche (droit) 
    if(!a->fd) return haug=1, a->fg;  // On remplace donc l'arbre par l'autre fils. 
    for(b=a->fg;b->fd;b=b->fd) ;      // b est l'élément le plus à droite du sous-arbre gauche
    b->fg=detacheavl(a->fg,b->val);   // On le détache du sous-arbre gauche, puis on le met
    b->fd=a->fd;                      // à la place de a à la racine.
    b->eq=a->eq;                      // Tout se passe alors, comme si on avait enlevé
    a=b;                              // un élément du sous-arbre gauche.   
  }
  if(!haug) return a;                 // La hauteur des fils n'a pas changé.
  if(haug!=a->eq) a->eq+=haug;     // La hauteur d'un des fils a diminué de 1. Donc a->eq varie de 1.
  else            a=reequilibre(a);// S'il passe à 2 ou -2, on fait des rotations.   
  return haug=!a->eq, a; // Qu'il y ait eu ou non des rotations, la hauteur de l'arbre a diminué          
}                        // si et seulement s'il est bien tassé (a->eq nul)
abr oteavl(abr a,int x)
{ abr b=a;
  while(b && b->val!=x) b=x>b->val?b->fd:b->fg;
  if(b) a=detacheavl(a,x), free(b);
  return a;
}
void verifavl(abr a)
{ abr x=0;
  int hauteur(abr a)
  { if(!a) return 0;
    int hg=hauteur(a->fg);
    if(x && x->val>=a->val) printf(" Clefs non croissantes"),getchar(),exit(1);
    x=a;
    int hd=hauteur(a->fd);
    if(hd-hg!=a->eq || a->eq<-1 || a->eq>1) printf(" erreur %d-%d=%d",hd,hg,a->eq),getchar(),exit(1);
    return 1+(hg<hd?hd:hg);
  }
  hauteur(a);
}
void affar(abr a,abr r)
{ for(;a;a=a->fg)
  { abr p=a->fg; a->fg=0, affar(a->fd,r), a->fg=p;//On cache le fils gauche pendant l'affichage du droit
    int g=2;
    for(p=r;p!=a;p=p->fg?:p->fd) printf(g!=!p->fg?"   ":"|  "), g=!!p->fg;
    printf("%c--+(%2d) %d\n","/\\-"[g],a->eq,a->val);
  }
}
void affarln(abr a) {printf("\n"),affar(a,a);}
int main()
{ abr a=nouv(f(1),4,nouv(f(7),8,0));
  int j;
  affln(a);
  a=ajoute(a,6);
  affln(a);
  for(j=0;j<20;j+=2) if(recherche(a,j)) printf("%d ",j);
  printf("\n");
  abr b=copie(a);
  add1(b);
  printf("%d : ",somme(a)), affln(a);
  printf("%d : ",somme(b)), affln(b);
  abr c=oppose(b);
  printf("%d : ",somme(c)), affln(c);
  while(a) a=ote(a,a->val), affln(a);
  affaln(b);
  b=tourneg(b);
  affaln(b);
  b=tourned(b);
  affaln(b);
  //b=linearise1(b);
  //linearise2(&b);
  linearise3(&b);
  affaln(b);
  for(j=0;j<50000;++j) b=ajoute(b,j), b=raccourci(b,j);
  //affln(b);
  for(j=0;j<50000;++j) b=raccourci(b,j), b=ote(b,j);
  affln(b);
  for(j=0;j<50000;j++) b=ajouteavl(b,j^23521);
  verifavl(b);
  for(j=0;j<50000;j++) b=oteavl(b,j^23521);
  verifavl(b);
  affln(b);
  return 0;
}

1 4 7 8 
1 4 6 7 8 
4 6 8 
26 : 1 4 6 7 8 
31 : 2 5 7 8 9 
-31 : -9 -8 -7 -5 -2 
1 6 7 8 
1 7 8 
1 8 
1 


   9
      8
         7
5
   2

9
      8
         7
   5
      2

   9
      8
         7
5
   2

9
   8
      7
         5
            2

lundi 3 et mardi 4 janvier 2005 : rotations dans les arbres binaires de recherche

lundi 10 et mardi 11 janvier 2005 : AVL

lundi 10 janvier : rééquilibrage dans les AVL

   h+3                h+3           h+3                h+2
    A      devient     B             A      devient     B
  / 2 \h+2        h+2/-1 \         / 2 \h+2        h+1/ 0 \
 h      B          A     h+1      h      B          A     h+1
      / 0 \      / 1 \                 / 1 \      / 0 \
    h+1   h+1   h    h+1              h    h+1   h     h   

   h+3                h+2          h+3                h+2          h+3                h+2       
    A      devient     C            A      devient     C            A      devient     C        
  / 2 \h+2        h+1/ 0 \h+1     / 2 \h+2        h+1/ 0 \h+1     / 2 \h+2        h+1/ 0 \h+1   
 h      B          A       B     h      B          A       B     h      B          A       B    
      /-1 \      / 0 \   / 0 \        /-1 \      /-1 \   / 0 \        /-1 \      / 0 \   / 1 \  
    h+1    h    h     h h     h     h+1    h    h   h-1 h     h     h+1    h    h     h h-1   h 
     C                               C                               C
   / 0 \                           / 1 \                           /-1 \
  h     h                        h-1    h                         h    h-1   

mardi 11 janvier : insertion dans un AVL

    h+1               h+1
     A    devient      A
   /-1 \             / 0 \
  h    h-1          h     h

    h+1               h+2
     A    devient      A
   / 0 \             / 1 \
  h     h           h    h+1

    h+1               h+2                  h+2     h+1
     A    devient      A     qui devient    B   ou  B
   / 1 \             / 2 \                 -1       0
 h-1    h          h-1   h+1