C algorithmique, premier semestre, deuxième année, MMIA 2006--2006

vendredi 7 octobre : comparaison du pascal et du C
vendredi 14 octobre 2005 : ++ += virgule ? : for
vendredi 21 octobre 2005 : priorité des opérateurs
vendredi 28 octobre 2005 : pointeurs et passage d'arguments
vendredi 4 novembre 2005 : pointeurs et tableaux
vendredi 18 novembre 2005 : structures, pointeurs, malloc et listes chaînées
vendredi 25 novembre 2005 : liste chaînée : création et parcours
vendredi 2 décembre 2005 : manipulations élémentaires de listes chaînées
vendredi 9 décembre 2005 : insertion triée, fusion et trifusion
vendredi 16 décembre 2005 : pointeur sur un pointeur
vendredi 13 janvier 2006 : contrôle
vendredi 20 janvier 2006 : corrigé du contrôle

suivant sommaire

vendredi 7 octobre : comparaison du pascal et du C

Le langage C a été inventé en s'inspirant du pascal. Il lui ressemble donc beaucoup. Nous allons donc voir toutes les différences entre ces deux langages.

compacité: BEGIN END IF THEN ELSE WHILE et DO

Les inventeurs du C ont voulu rendre les programmes les plus courts possible. C'est pourquoi, ils ont essayé de mettre le moins possible de mots réservés. Par exemple BEGIN et END sont devenus { et } tandis que THEN et DO ont été remplacés par ).

 
begin           {
  a:=3;           a=3;
  c:=5            c=5;
end             }

if a=3 then b:=4        if(a==3) b=4;
       else c:=5        else     c=5;

while i>0 do i=i-2      while(i>0) i-=2;

Dans un IF en pascal la condition se trouve entre IF et THEN, et elle n'est donc pas nécessairement entourée de parenthèse. C'est le THEN qui indique la fin de la condition. En C, il n'y a pas de then, mais la condition doit obligatoirement être mise entre parenthèse. Tout ce passe donc comme si le IF et le THEN du pascal étaient remplacés par if( et ) en C.
De même, on peut considérer que le WHILE et le DO du pascal sont remplacés par while( et ) en C.

point-virgule et instruction vide

Le point-virgule a un statut très différent en pascal et en C. En pascal une instruction ne se termine jamais par un point-virgule, les points-virgules se trouvent entre les instructions qui sont mises les unes derrière les autres dans un bloc BEGIN ... END (ou un REPEAT ... UNTIL). Il n'y a donc pas besoin de point-virgule avant le END, et il n'y a jamais de point-virgule avant un ELSE. (Ce point-virgule séparerait le IF qui précède de l'instruction suivante qui commencerait par ELSE, or aucune instruction ne commence par ELSE).
En C ce n'est pas du tout la même chose. Toutes les instructions se terminent par un point-virgule (ou une accolade fermante). On met un point-virgule derrière une expression pour en faire une instruction. A l'intérieur d'un bloc {...} toutes les instructions sont mises bout à bout sans rajouter de séparateur. Par exemple begin a:=3;c:=5 end contient deux instructions «a:=3» et «c:=5» séparées par un «;» tandis que {a=3;c=5;} contient deux instructions «a=3;» et «c=5;» sans rien entre elles. Ces deux instructions composées se ressemblent donc beaucoup.
On peut confondre facilement ces deux syntaxes, d'autant plus qu'en pascal on a le droit d'écrire begin a:=3;c:=5;end qui contient trois instructions «a:=3» et «c:=5» et «»(l'instruction vide) séparées par deux «;».
L'instruction vide existe aussi en C et se note «;». Par exemple begin;;a:=3;;;c:=5;;;end contient neuf instructions : 2 vides, «a:=3», 2 vides, «c:=5» et 3 vides séparées par huit «;» tandis que {;;a=3;;c=5;;;} contient huit instructions : 2 vides, «a=3;», 2 vides, «c=5;» et 2 vides sans rien entre elles.
Tout cela peut paraître un peu bizarre, et l'instruction vide semble inutile. En fait elle sert dans le cas d'un if contenant un else mais sans rien à faire dans le cas du then :


if a=3 then             if(a==3) ;   
       else c:=5        else     c=5;

En pascal il n'y a rien entre THEN et ELSE, tandis qu'en C il y a un point-virgule entre ) et else.
On peut aussi mettre une instruction vide comme corps d'une boucle while :


while readkey=' ' do;       while(getchar()==' ') ;
a:=a+1                      a++;

En pascal le point-virgule sépare le while de l'affectation qui suit. Il ne fait pas partie du while. L'instruction répétée est l'instruction vide entre do et «;».
En C le point-virgule est l'instruction vide qui est répétée. Il fait donc partie du while.

déclarations de variables

En pascal le type est mis après la variable à déclarer. En C le type est mis avant.

var i:integer;                 int i;
    ii:word;                   unsigned int ii;
    j,k:longint;               long int j,k;
    x,y:single;                float x,y;
    z:double;                  double z;
    u:extended;                long double u;

En pascal les déclarations sont mises avant le corps de la procédure. En C elles sont mises au début de n'importe quel bloc.

opérateurs +, *, /, etc.


  2+3                      2+3         5
  4-1                      4-1         3
  4*5                      4*5        20 
  23 div 5                 23/5        4
  21 mod 8                 21%8        5
  7.0/2.0                  7.0/2.0     3.0
  6 and 5                  6&5         4
  6 or 5                   6|5         7
  6 xor 5                  6^5         3
  false or true = true     0||32       1
  false and true = false   0&&32       0
  -(2+3)                   -(2+3)      -5
  not true    = false      !4          0
  not false   = true       !0          1
  not 5                    ~5          -6
  21 shr 2                 21>>2       5
  7 shl 3                  7<<3        56
  4=3                      4==3        0
  4<>3                     4!=3        1
  4<3                      4<3         0
  4>3                      4>3         1
  4<=3                     4<=3        0
  4>=3                     4>=3        1

En pascal il existe un type booléen (BOOLEAN), différent des types numériques.
En C il n'en existe pas. Les opérateurs logiques && (et logique), || (ou logique) et ! (non logique) ont un résultat entier qui peut être 0 (pour faux) ou 1 (pour vrai). Par contre leurs opérandes peuvent être des nombres quelconques, entiers ou réels. Un nombre nul est considéré comme faux. Un nombre non nul est considéré comme vrai. Par exemple (-3.0 && 0) se comprend comme (vrai et faux) qui est égal à faux qui est représenté par 0.
suivant précédent sommaire

vendredi 14 octobre 2005 : ++ += virgule ? : for

opérateurs ++ et --

Les instructions i++; et ++i; sont équivalentes à i=i+1;
Par contre les expressions i++ et ++i ont le même effet, d'augmenter i de 1, mais elles ont des valeurs différentes : la valeur de i++ est l'ancienne valeur de i, tandis que la valeur de ++i est la nouvelle valeur de i. Par exemple
{i=3; a=i++;} est équivalent à {i=4; a=3;}, mais
{i=3; a=++i;} est équivalent à {i=4; a=4;}.

opérateurs d'affectation

a+=3 est équivalent à a=a+3.
b/=2 est équivalent à b=b/2. etc.
Les opérateurs d'affectation sont = += -= *= /= %= <<= >>= |= &= ^=.
En pascal a:=3 est une instruction. En C l'instruction équivalente est a=3; (avec un point-virgule). Par contre a=3 (sans point-virgule) n'est pas une instruction, c'est une expression qui a pour valeur 3 (et dont l'évaluation a pour effet de mettre 3 dans a).
Par exemple

c=(a=3)+(b=4);

est équivalent à

a=3;
b=4;
c=a+b;

Les opérateurs binaires sont en général «associatifs à gauche» par exemple 4-5-6 est égal à (4-5)-6 et vaut -7, alors que 4-(5-6) vaut 5.
Les opérateurs d'affectation sont eux «associatifs à droite». Par exemple a=b=c=3; est équivalent à a=(b=(c=3)); c'est-à-dire à {c=3; b=c; a=b;} ou encore à {c=3; b=3; a=3;}.
De même s+=t*=x/++i; est équivalent à {i=i+1; t=t*(x/i); s=s+t;}

ordre d'évaluation des opérandes

Quand on exécute a=f(i,3)+g(i); on ne sait pas si la fonction f(i,3) est évaluée avant ou après la fonction g(i). Selon la norme ansi, ce choix est laissé à la discrétion du compilateur. Tous les opérateurs binaires ont ce même comportement, sauf && || et ,(virgule).
Les opérateurs ou et et logiques évaluent d'abord leur opérande gauche. Après cela ils n'évaluent leur opérande droit que si sa valeur est nécessaire pour déterminer le résultat de l'opération. Par exemple
{i=0; j=3; k=i++||j++;} est équivalent à {i=1; j=4; k=1;} mais
{i=0; j=3; k=++i||j++;} est équivalent à {i=1; j=3; k=1;}. Puisque ++i est non nul, j++ n'est pas évalué, et donc j garde la valeur 3.

opérateur virgule

L'opérateur virgule évalue d'abord son opérande gauche, puis son opérande droit. Le résultat de l'opération est l'opérande droit.
Par exemple 23,45 vaut 45.
a=(expr1,expr2); est équivalent à {expr1; a=expr2;}
expr1,expr2; est équivalent à {expr1; expr2;}

opérateur conditionnel ternaire ? :

a=expr1 ? expr2 : expr3; est équivalent à

if(expr1) a=expr2;
else      a=expr3;

Pour évaluer l'expression (expr1 ? expr2 : expr3) on évalue d'abord expr1. Puis on évalue une seule des deux expressions expr2 ou expr3.
Par exemple 2?3:4 vaut 3.
0?3:5 vaut 5.
i=3, j=6, k=2?i++:j++; est équivalent à i=4, j=6, k=3;

instruction do...while


repeat                 do
  a:=a-10;             { a-=10;
  i:=i+1                 i++;
until a<0              } while(a>=0);

instruction for

for(expr1;expr2;expr3) instr
est totalement équivalent à

{ expr1;
  while(expr2)
  { instr
    expr3;
  }
}

Par exemple l'instruction du pascal for i:=1 to 10 do j:=j+i
peut se traduire en C par for(i=1;i<=10;i++) j+=i;
Les trois expressions expr1, expr2 et expr3 peuvent bien sûr contenir des virgules mais pas de point-virgule. Donc il doit y avoir exactement deux points-virgules entre les parenthèses du for. Chacune des trois expressions expr1, expr2 et expr3 peut être vide. Si expr2 est vide, sa valeur est considérée comme toujours vraie, et la boucle se fait donc indéfiniment. Par exemple for(;;) printf("coucou\n"); écrit une infinité de lignes contenant toutes coucou.

TD

bonjour

Lancer le programme : démarrer / programme / dev c++
Ecrire le programme


int main()
{ printf("bonjour\n");
  getchar();
}

Le sauver sous le nom c:\dev-cpp\dupont\bonjour.c.
Le compiler puis l'exécuter.
Dans le menu : outils / options du compilateur / commande
remplacer «gcc.exe» par «gcc.exe -Wall»
Recompiler et corriger le programme pour supprimer les avertissements (warnings) :
Ajouter #include<stdio.h> en première ligne.
Ajouter return 0; en avant dernière ligne.

3+4=7

Ecrire le programme a3b4.c


#include<stdio.h>
int main()
{ int a,b;
  a=3;
  b=4;
  printf("a=%d b=%d\n",a,b);
  getchar();
  return 0;
}

Le compiler puis l'exécuter.
Le modifier pour qu'il écrive

3+4=7
3*4=12

Remplacer a=3 par printf("Tapez un nombre "); scanf("%d",&a);
Idem pour b.
Mettre deux appels à getchar();

1 4 9 ... 81 100

Ecrire un programme qui affiche les carrés des entiers de 1 à 10 (avec une boucle for).

équation du second degré

Compléter le programme :


#include<stdio.h>
#include<math.h>
int main()
{ double a,b,c,d,x1,x2;
  printf("Coefficient de X*X : ");
  scanf("%lf",&a);

suivant précédent sommaire

vendredi 21 octobre 2005 : priorité des opérateurs

L'opérateur de multiplication * est prioritaire sur l'opérateur d'addition + : L'expression 1*3+2 est équivalente à (1*3)+2, elle vaut 5. L'expression 1+3*2 est équivalente à 1+(3*2), elle vaut 7.
D'une manière générale, les expressions qui contiennent plus de trois niveaux de parenthèses, sont assez difficiles à lire quand les parenthèses ne se ferment pas toutes au même endroit. C'est pourquoi il faut connaître la priorité des opérateurs, cela permet d'éviter de mettre des parenthèses inutiles. Bien sûr si on a des doutes sur la priorité des opérateurs, il vaut mieux mettre des parenthèses inutiles que de prendre le risque d'écrire une expression fausse. Mais dès que possible, il vaut mieux essayer d'enlever ces parenthèses inutiles. Un programme qui contient trop de parenthèses, montre la prudence de celui qui l'a écrit, mais aussi son ignorance de la syntaxe du langage.

associativité à droite ou à gauche

La plupart des opérateurs binaires sont associatifs à gauche, cela signifie que lorsque deux opérateurs binaires de même priorité se suivent, celui de gauche est prioritaire. Par exemple 4-5-6 est équivalent à (4-5)-6 qui vaut -7 et non pas à 4-(5-6) qui vaut 5.
En C tous les opérateurs binaires sont associatifs à gauche, sauf les opérateurs d'affectation qui sont associatifs à droite. Par exemple
a=b=3 est équivalent à a=(b=3) c'est-à-dire à b=3,a=b ou encore à b=3,a=3
a=b=c=2 est équivalent à a=(b=(c=2)) c'est-à-dire à c=2,b=c,a=b ou encore à c=2,b=2,a=2
a+=b*=x+=1 est équivalent à a+=(b*=(x+=1)) c'est-à-dire à x+=1,b*=x,a+=b

opérateur ? :

? et : jouent le rôle de parenthèses. On peut donc mettre n'importe quelle expression entre eux. Le ?expr: se comporte syntaxiquement comme un opérateur binaire qui est associatif à droite (comme les opérateurs d'affectation).
Autrement dit expr1?expr2:expr3?expr4:expr5 est équivalent à expr1?(expr2):(expr3?(expr4):expr5).
Par exemple 1?2:3?4:5 vaut 2 alors que (1?2:3)?4:5 vaut 4.

Associativité de la virgule

L'opérateur virgule est associatif : En effet les deux expressions (expr1,expr2),expr3 et expr1,(expr2,expr3) sont équivalentes car elles ont toutes deux pour effet d'évaluer dans l'ordre expr1 puis expr2 puis expr3 et ont pour valeur la valeur de expr3. On peut donc considérer que la virgule est un opérateur associatif à droite ou à gauche.

priorité des opérateurs en pascal

1) opérateurs unaires postfixes : [indice] (liste_d_arguments) .nom_de_champ ^
2) opérateurs unaires préfixes : @ - not
3) opérateurs multiplicatifs : * mod / div and shl shr
4) opérateurs additifs : + - or xor
9,5) opérateurs de comparaison : < > <= >= = <>

priorité des opérateurs en C

En C on retrouve plus ou moins ces cinq niveaux de priorité dans le même ordre, mais il y en plein d'autres.
1) opérateurs unaires postfixes : [indice] (liste_d_arguments) .nom_de_champ ->nom_de_champ ++ --
2) opérateurs unaires préfixes : & - ~ ! + * (type)
3) opérateurs multiplicatifs : * % /
4) opérateurs additifs : + -
5) opérateurs de décalage : >> <<
6) opérateur et bit à bit : &
7) opérateur ou exclusif bit à bit : ^
8) opérateur ou bit à bit : |
9) opérateurs de relation : < > <= >=
10) opérateurs de comparaison : == !=
11) opérateur et logique : &&
12) opérateur ou logique : ||
13) opérateur conditionnel : ?...:
14) opérateurs d'affectation : = += -= *= /= %= &= ^= |= >>= <<=
15) opérateur virgule : ,
Puisque ? et : jouent le rôle de parenthèses, on peut donc mettre entre eux une affectation ou une virgule.

exemple

a=5,b=a<3?b=5,c=6:j=7,k=8; est équivalent à
(a=5) , (b=((a<3)?((b=5),(c=6)):(j=7))) , (k=8);
ou encore à


a=5;
if(a<3) b=(b=5,c=6);
  else  b=(j=7);
k=8;

ou encore à


a=5;
if(a<3) {b=5;c=6;b=c;}
  else  {j=7;b=j;}
k=8;

Puisque a vaut 5, la condition a<3 est fausse. Donc en fait l'instruction précédente est équivalente à {a=5; b=j=7; k=8;}
De même en mettant 2 dans a au lieu de 5 on voit que l'instruction a=2,b=a<3?b=5,c=6:j=7,k=8; est équivalente à {a=2; b=c=6; k=8;}

TD : tableaux et fonctions

tableaux

Traduire en C le crible d'Erathostène :

pour j=2,3, ... n faire
  t[j]:=1
fait
pour j=2,3, ... √n faire
  si t[j]=1 alors // si j est premier
     pour k=j*j, j*j+j, j*j+2j, ... faire
       t[k]:=0
     fait
  finsi
fait
pour j=2,3, ... n faire
  si t[j]=1 alors
     afficher j
  finsi
fait

Si k est composé, il est le produit de son plus petit diviseur premier j, par un facteur supérieur ou égal à j. Donc si pour chacun des nombres premiers déjà trouvés, on élimine les nombres produits de ce nombre premier par un entier plus grand, on est sûr d'éliminer tous les nombres composés, et il ne reste que les nombres premiers.


#include<stdio.h>
int main()
{ int n=100000, t[n+1], j,k;
  for(j=2;j  <=n;j++)    t[j]=1;
  for(j=2;j*j<=n;j++) if(t[j]) for(k=j*j;k<=n;k+=j) t[k]=0;
  for(j=2;j  <=n;j++) if(t[j]) printf("%d ",j);
  getchar();
  getchar();
  return 0;
}

fonctions

Compléter le programme :


#include<stdio.h>
void aff(int n,int t[n])
{...}
int somme(int n,int t[n])
{...
  return s;
}
int main()
{ int n=5, t[]={3,6,9,2,1};
  aff(n,t);
  printf("La somme vaut %d\n",somme(n,t));
  getchar();
  getchar();
  return 0;
}

suivant précédent sommaire

vendredi 28 octobre 2005 : pointeurs et passage d'arguments

cours : pointeurs

adresse d'une variable

On peut considéder la mémoire de l'ordinateur comme un très grand tableau, dans lequel on réserve des petits morceaux pour y mettre les variables utilisées par un programme. L'indice dans ce grand tableau est l'«adresse» de la variable qui s'y trouve. Par exemple si on déclare

int a,b,c[3];
float d,e[3];
struct {int x,double y[2];} f,g[3];

Les variables a, b, c, d, e, f et g peuvent être rangées consécutivement à partir de l'adresse 1000 :

!_,_,_,_!_,_,_,_!_,_,_,_!_,_,_,_!_,_,_,_!_,_,_,_!_,_,_,_!_,_,_,_!_,_,_,_!_,_,_,_!_,_,_,_,_,_,_,_!_,_,_,_,_,_,_,_!
1000     1004   1008     1012   1016     1020   1024     1028   1032    1036    1040            1048           
a        b      c[0]     c[1]   c[2]     d      e[0]     e[1]   e[2]    f.x     f.y[0]          f.y[1]     
                c                               e                       f.x     f.y
                                                                        f     

!_,_,_,_!_,_,_,_,_,_,_,_!_,_,_,_,_,_,_,_!_,_,_,_!_,_,_,_,_,_,_,_!_,_,_,_,_,_,_,_!_,_,_,_!_,_,_,_,_,_,_,_!_,_,_,_,_,_,_,_!
1056    1060            1068            1076    1080            1088            1096    1100            1108           
g[0].x  g[0].y[0]       g[0].y[1]       g[1].x  g[1].y[0]       g[1].y[1]       g[2].x  g[2].y[0]       g[2].y[1]     
g[0].x  g[0].y                          g[1].x  g[1].y                          g[2].x  g[2].y
g[0]                                    g[1]                                    g[2]     
g

L'expression &a ,l'adresse de a vaut 1000.
De même &c = &c[0] = 1008.
&g=&g[0]=&g[0].x=1056.

pointeur

Un pointeur est une variable qui prend pour valeur l'adresse d'une autre variable.

int *p;
p=&a;    // p=1000
*p=3;    // *1000=3  i.e. a=3
p=&b;    // p=1004
*p=4;    // *1004=4  i.e. b=4
p=a;     // p=3 est interdit car 3 est un entier ce n'est pas l'adresse d'un entier
*p=&a    // *1004=1000 i.e. b=1000 est interdit car *p (c'est-à-dire b) est un entier et &a n'est pas un entier, c'est l'adresse d'un entier

Les opérateurs unaires préfixes * (indirection) et & (adresse) sont l'inverse l'un de l'autre. & transforme une variable en son adresse, * appliqué à l'adresse d'une variable donne cette variable. Par exemple &a vaut 1000 et *1000 est a. Autrement dit *&a est la variable a tandis que &*p est la valeur de p.
Dans les lignes précédentes il y a une différence entre «est» et «vaut» :
&a est une expression qui a pour valeur l'adresse de a. On ne peut pas changer l'adresse de a. Cette expression peut être le membre droit d'une affectation, mais pas le membre gauche. J'appelle cela une valeur (On appelle cela aussi une rvalue).
*p est la variable pointée par p, c'est la variable dont l'adresse est rangée dans p. C'est bien une variable, on peut la mettre comme membre gauche d'une affectation (On appelle cela aussi une lvalue).
*&a et a sont deux expressions qui représentent la même variable. p et &*p sont deux expressions qui ont la même valeur, mais p est une variable alors que &*p n'est pas une variable.

syntaxe des déclarations de pointeur

La déclaration int *p,a,*q; signifie que les trois expressions *p, a et *q représentent des entiers. Donc a est un entier et p et q sont des pointeurs sur des entiers.

TD : passage d'argments

Ecrire des procédures qui :
échange deux entiers
échange deux entiers s'ils ne sont pas dans l'ordre croissant
permute trois entiers pour les mettre dans l'ordre croissant
calcule la surface et le périmètre d'un cercle, à partir du rayon

#include<stdio.h>
#include<math.h>
void ech(int *aa,int *bb)
{ int c;
  c=*aa, *aa=*bb, *bb=c;
}
void tri2(int *aa,int *bb)
{ if(*aa>*bb) ech(aa,bb);
}
void tri3(int *aa,int *bb,int *cc)
{ tri2(aa,bb);
  tri2(bb,cc);
  tri2(aa,bb);
}
void cercle(double rayon,double *perimetre,double *surface)
{ *perimetre=2*rayon*M_PI;
  *surface=rayon*rayon*M_PI;
}
int main()
{ double r,c,s;
  int i,j,k;
  printf("Donnez trois nombres : ");
  scanf("%d%d%d",&i,&j,&k);
  printf("%d %d %d\n",i,j,k);
  tri3(&i,&j,&k);
  printf("%d %d %d\n",i,j,k);
  printf("Quel est le rayon du cercle ? ");
  scanf("%lf",&r);
  cercle(r,&c,&s);
  printf("La circonférence est %20.15lf\n",c);
  printf("La surface est %20.15lf\n",s);
  getchar();
  getchar();
  return 0;
}

suivant précédent sommaire

vendredi 4 novembre 2005 : pointeurs et tableaux

cours

passage d'arguments

Avec les procédures du programme précédent, on éxécute instruction par instruction le bout de programme :

a=4, b=3;
tri2(&a,&b);

!_,_,_,4!_,_,_,3!
2000     2004    
a        b

On exécute tri2(2000,2004);

!_,_,_,4!_,_,_,3!       !_,_2000!_,_2004!
2000     2004           2020     2024    
a        b              aa       bb
                        tri2(&a,&b)

*aa>*bb donne *2000>*2004 c'est-à-dire 4>3 qui est vrai. Donc on exécute ech(aa,bb);

!_,_,_,4!_,_,_,3!       !_,_2000!_,_2004!       !_,_2000!_,_2004!_,_,_,_!
2000     2004           2020     2024           2040     2044    2048  
a        b              aa       bb             aa       bb      c
                        tri2(&a,&b)             ech(aa,bb)

c=*aa; donne c=*2000 c'est-à-dire c=a donc c=4
*aa=*bb; donne *2000=*2004 c'est-à-dire a=b donc a=3
*bb=c; donne *2004=c c'est-à-dire b=4

!_,_,_,3!_,_,_,4!       !_,_2000!_,_2004!       !_,_2000!_,_2004!_,_,_,4!
2000     2004           2020     2024           2040     2044    2048  
a        b              aa       bb             aa       bb      c
                        tri2(&a,&b)             ech(aa,bb)

tableaux et pointeurs

En C l'opérateur [] s'applique à un tableau ou à un pointeur, mais une référence à un tableau à une dimension se comporte comme un pointeur sur son premier élément : Si t est un tableau à une dimension, les deux expressions t et &t[0] sont équivalentes. Donc de même *t et t[0] sont équivalents.

tableau passé en argument

Dans une liste d'arguments de fonction, les trois déclarations int *t, int t[] et int t[4] sont donc équivalentes.
De plus les tableaux sont toujours passés par référence en C, ils ne sont jamais recopiés lors d'un appel de fonction.

opérations sur les pointeurs

t+3 est équivalent à &t[3].
Donc de même *(t+3) est équivalent à t[3]
On peut soustraire deux pointeurs pour obtenir un entier. (t+5)-(t+3) vaut 2

TD

Compléter les procédures :

int maxt(int n,int t[n])
int posmax(int n,int t[n])
void tri(int n,int t[n])
void fusion(int n,int m,int t[n],int u[m], int v[n+m])

maxt cherche le plus grand des éléments d'un tableau et posmax cherche sa position. tri permute les éléments d'un tableau en les mettant dans l'ordre croissant, en échangeant le plus grand élément avec le dernier et en recommençant en considérant qu'il y a un élément de moins dans le tableau. fusion fusionne les deux tableaux triés t et u en un tableau trié v, en prenant le plus petit des deux premiers éléments de t et u, en l'enlevant de ce tableau pour le mettre dans v et en recommençant.

#include<stdio.h>

int maxt(int n,int t[n])
{ int m=t[0], i;
  for(i=1;i<n;i++) if(t[i]>m) m=t[i];
  return m;
}

int posmax(int n,int t[n])
{ int i,j=0;
  for(i=1;i<n;i++) if(t[i]>t[j]) j=i;
  return j;
}

void tri(int n,int t[n])
{ for(;n;n--)
  { int j=posmax(n,t), x=t[j];
    t[j]=t[n-1];
    t[n-1]=x;
  }
}   
  
void fusion(int n,int m,int t[n],int u[m], int v[n+m])
{ int i=0,j=0;
  while(i<n && j<m) if(t[i]<u[j]) v[i+j]=t[i], i++;
                    else          v[i+j]=u[j], j++;
  while(i<n) v[i+j]=t[i], i++;
  while(j<m) v[i+j]=u[j], j++;
}

void trifusion(int n,int t[n])
{ if(n>1)
  { int m=n/2, *u=t+m, v[n];
    trifusion(m  ,t);
    trifusion(n-m,u);
    fusion(m,n-m,t,u,v);
    for(m=0;m<n;m++) t[m]=v[m];
  }
}

void aff(int n,int t[n])
{ int i;
  for(i=0;i<n;i++) printf(" %d",t[i]);
  printf("\n");
}

int main()
{ int n=7, t[]={5,6,2,7,1,4,3};
  aff(n,t);
  printf("Le plus grand élément est %d\n",maxt(n,t));
  trifusion(n,t);
  aff(n,t);
  return 0;
}

suivant précédent sommaire

vendredi 18 novembre 2005 : structures, pointeurs, malloc et listes chaînées

déclaration de structure

pascal vs C, première version sans déclaration de type

var a,b:record x,y:integer end;               struct {int x,y;} a,b;

déclare deux structures identiques a et b qui ont chacune deux champs de type entier appelés x et y. On a donc quatre variables entières a.x, a.y, b.x, b.y.

pascal vs C, deuxième version avec déclaration de type

   pascal                                 C de Kernighan et Ritchie             C ansi
type xy=record x,y:integer end;           struct xy {int x,y;};           typedef struct {int x,y;} xy;
var a,b:xy;                               struct xy a,b;                  xy a,b;

En pascal le type est "xy" en C de K&R c'est "struct xy". Le typedef du C ansi permet de se rapprocher du pascal.

syntaxe de la déclaration struct

Une déclaration de structure en C comporte dans l'ordre :
le mot "struct"
un nom de structure
une liste de déclarations de champs entre accolade
une liste de variables séparées par des virgules
un point-virgule.
Par exemple

struct xy{int x,y;} a,b;

Chacune des trois zones en couleur est facultative. Par exemple la ligne précédente est équivalente à

struct xy{int x,y;};
struct xy a,b;

Elle aurait pu aussi s'écrire

struct {int x,y;} a,b;

si on n'avait pas voulu définir le type "struct xy".
On peut même écrire :

struct truc;

qui signifie que truc est le nom d'une structure, dont on précisera plus tard le contenu.

pointeurs sur des structures

En C comme en pascal, on a le droit de déclarer des pointeurs sur une structure dont on ne connaît pas encore la composition. Cela ne pose pas de problème au compilateur, puisque les pointeurs ont tous quatre octets. Leur taille ne dépend pas de la taille de la structure pointée. Par exemple :

type ptruc=^truc;                                         typedef struct truc *ptruc;
     truc=record a:integer; b:double; c:ptruc end;        struct truc{int a;double b;ptruc c;};
var p,q:ptruc;                                            ptruc p,q;

En C K&R (donc sans typedef) on aurait écrit :

struct truc{int a;double b;struct truc *c;};
struct truc *p,*q;

allocation de mémoire

malloc et free vs allocation automatique dans un bloc

{ int t[n];               { int *t; t=malloc(n*sizeof(*t));
  ...                       ...
                            free(t);
}                         }

sont équivalents.

rappel : différence entre déclaration et passage en argument de pointeurs et de tableaux

Dans les déclarations en début de bloc, int t[n]; n'est pas équivalent à int *t; . La première déclaration réserve la place pour n entiers à chaque fois que l'on rentre dans ce bloc et libère cette place quand on sort de ce bloc. La deuxième réserve la place pour un pointeur (4 octets) dans lequel on devra mettre l'adresse d'un tableau (par exemple un tableau créé par malloc, qu'il faudra détruire par free quand on n'en aura plus besoin).
Par contre dans une liste d'argument de fonction, ,int t[n], est équivalent à ,int t[], ou a ,int *t, . Aucun tableau n'est créé. L'adresse du tableau passé en argument est rangée dans le pointeur t.

listes chaînées

Une liste chaînée est une suite de chaînons contenant chacun un élément de la liste et un pointeur sur le chaînon suivant. Le dernier chaînon contient le pointeur nul. Autrement dit, une liste chaînée est représentée par un pointeur sur un chaînon, qui est
soit le pointeur nul, si la liste est vide,
soit un pointeur sur le premier chaînon qui contient le premier élément de la liste et un pointeur représentant le reste de la liste.
Le programme suivant crée la liste (4,5,2) et appelle une procédure qui affiche cette liste.


typedef struct chainon *liste;  // liste= pointeur sur (struct chainon)
struct chainon {int val; liste suite;};

void aff(liste a)       // version récursive        
{ if(a) printf(" %d",a->val), aff(a->suite);  // Pour afficher une liste non vide, on affiche son premier élément, puis le reste.
  else  printf("\n");                         // Pour afficher une liste vide, on passe simplement à la ligne
}

void aff2(liste a)     // version iérative
{ for(;a;a=a->suite;) printf(" %d",a->val);  // Tant que la liste est non vide, on affiche son premier élément, et on passe à la suite.
  printf("\n");                              // A la fin de la liste on passe à la ligne
}

int main()
{ liste p,q,r;
  p=malloc(sizeof(*p)); 
  q=malloc(sizeof(*q)); 
  r=malloc(sizeof(*r)); 
  p->val=4;   p->suite=q;
  q->val=5;   q->suite=r;
  r->val=2;   r->suite=0;
  aff(p);
  aff2(p);
  return 0;
}

Dans le programme précédent on aurait pu ne pas mettre la définition du type liste typedef struct chainon *liste; et remplacer partout liste par struct chainon *. Par exemple, au lieu de void aff(liste a) on peut écrire void aff(struct chainon *a). Au lieu de liste p,q,r; on peut écrire struct chainon *p,*q,*r;.
suivant précédent sommaire

vendredi 25 novembre 2005 : liste chaînée : création et parcours

Dans le programme principal précédent, on fait des choses assez similiaires avec p, q et r : p=malloc(sizeof(*p)); p->val=4; p->suite=q; peut être remplacé par l'appel de fonction p=nouv(4,q);. Si on ajoute la fonction


liste nouv(int val,liste suite)
{ liste a;
  a=malloc(sizeof(*a));
  a->val=val;
  a->suite=suite;
  return a;
}

le programme principal devient


int main()
{ liste p,q,r;
  r=nouv(2,0);
  q=nouv(5,r);
  p=nouv(4,q);
  aff(p);
  aff2(p);
  return 0;
}

On peut éliminer les variables q et r de ce programme de deux manières :


int main()
{ liste p;
  p=nouv(4,nouv(5,nouv(2,0))));
  aff(p);
  aff2(p);
  return 0;
}
int main()
{ liste p=0;
  p=nouv(2,p);
  p=nouv(5,p);
  p=nouv(4,p);
  aff(p);
  aff2(p);
  return 0;
}

La première manière est plus compacte est montre clairement qu'on fabrique la liste (4 5 2). La deuxième suggère de mettre p=nouv(...,p); dans une boucle :


int main()
{ liste p=0;
  int t[]={2,5,4}, i;
  for(i=0;i<3;i++) p=nouv(t[i],p);
  aff(p);
  aff2(p);
  return 0;
}

TD

Dans la version récursive de l'affichage d'une liste chaînée mettre l'affichage du premier élément après l'appel récursif qui affiche le reste de la liste. On obtient ainsi une procédure qui affiche la liste à l'envers.
Ecrire une fonction itérative qui calcule la somme des éléments d'une liste chaînée. Elle ressemblera à la procédure itérative d'affichage, dans laquelle on remplace l'écriture de a->val par s+=a->val;.
Ecrire une fonction récursive qui calcule la somme des éléments d'une liste chaînée. Cette somme est nulle si la liste est vide. Sinon c'est la somme du premier élément et de la somme du reste de la liste.
Ecrire une fonction récursive qui fabrique une copie d'une liste chaînée avec de nouveaux chaînons. La copie d'une liste vide est la liste vide. La copie d'une liste non vide est un nouveau chaînon qui contient la même valeur que le premier chaînon de l'originale et la copie de la suite de ce premier chaînon.
Ecrire une fonction itérative qui fait une copie à l'envers d'une liste chaînée. Elle ressemblera à la procédure itérative d'affichage, dans laquelle on remplace l'écriture de a->val par p=nouv(a->val,p);.

#include<stdio.h>
#include<stdlib.h>
typedef struct chainon *liste;  // liste= pointeur sur (struct chainon)
struct chainon {int val; liste suite;};

void aff(liste a)       // version récursive
{ if(a) printf(" %d",a->val), aff(a->suite);  // Pour afficher une liste non vide, on affiche son premier élément, puis le reste.
  else  printf("\n");                         // Pour afficher une liste vide, on passe simplement à la ligne
}

void aff2(liste a)     // version iérative
{ for(;a;a=a->suite) printf(" %d",a->val);  // Tant que la liste est non vide, on affiche son premier élément, et on passe à la suite.
  printf("\n");                              // A la fin de la liste on passe à la ligne
}

liste nouv(int val,liste suite)
{ liste a;
  a=malloc(sizeof(*a));
  a->val=val;
  a->suite=suite;
  return a;
}

void ffa(liste a)
{ if(a) ffa(a->suite), printf(" %d",a->val);
}

int sommeit(liste a)
{ int s=0;
  for(;a;a=a->suite) s+=a->val;
  return s;
}
int sommere(liste a)
{ if(a) return a->val+sommere(a->suite);
  else  return 0;
}

liste copie(liste a)
{ if(a) return nouv(a->val,copie(a->suite));
  else  return 0;
}

liste eipoc(liste a)
{ liste p=0;
  for(;a;a=a->suite) p=nouv(a->val,p);
  return p;
}

int main()
{ liste p=0,q,r;
  int t[]={2,5,4}, i;
  for(i=0;i<3;i++) p=nouv(t[i],p);
  aff(p);
  aff2(p);
  ffa(p);
  printf("\n somme : %d = %d\n",sommeit(p),sommere(p));
  q=copie(p);
  r=eipoc(p);
  aff(q);
  aff(r);
  return 0;
}

suivant précédent sommaire

vendredi 2 décembre 2007 : manipulations élémentaires de listes chaînées

parcours

for(p=l;p;p=p->suite) ...p->val...
L'opération faite sur chaque élément de la liste peut être par exemple un affichage à l'écran : printf(" %d",a->val);
ou le calcul de la somme : s+=a->val;
ou le comptage des chaînons nb++;
ou une modification de la valeur rangée dans la liste comme a->val++;

ajout d'un élément en tête de liste

p=nouv(23,p); ajoute un chaînon contenant 23 en tête de la liste p.

suppression d'un élément en tête de liste

q=p; p=q->suite; free(q);
enlève le premier chaînon de la liste p, mais q pointe sur ce chaînon, ce qui permet de libérer la place qu'il utilisait. free(q); ne marche que si ce chaînon avait été créé par un appel à malloc, éventuellement fait par un appel à nouv.

combinaisons de ces manipulations élémentaires

parcours et insertion en tête de liste : copie à l'envers


  l2=0;
  for(p=l1;p;p=p->suite) l2=nouv(p->val,l2);

Si par exemple la liste l1 contient (3 5 4), alors la boucle sera faite trois fois et p->val vaudra 3 puis 5 puis 4. La liste l2 contiendra successivement () puis (3) puis (5 3) et enfin (4 5 3). La liste l1 n'est pas modifiée, elle contient toujours (3 5 4). La liste l2 est une copie de l1 à l'envers avec de nouveau chaînons.

détachement en tête de liste et insertion en tête de liste : retournement d'une liste avec les mêmes chaînons


  l2=0;
  for(;l1;l1=l1->suite) p=l1, l1=p->suite, // on détache le premier chaînon p de l1
                        p->suite=l2, l2=p; // on l'ajoute en tête de l2

Les valeurs successives de l1 et l2 sont par exemple :

   (4 7 8 2)   ()
   (7 8 2)     (4)
   (8 2)       (7 4)
   (2)         (8 7 4)
   ()          (2 8 7 4)

On détache un par un les chaînons en tête de l1, pour les mettre en tête de l2. A la fin l2 contient les chaînons de l1, chaînés à l'envers.

copie d'une liste chaînée

Il y a deux façons de fabriquer une copie d'une liste chaînée : De manière itérative avec deux boucles : on fabrique une liste à l'envers, que l'on retourne ensuite. De manière récursive : La copie d'une liste non vide est un nouveau chaînon contenant la même valeur que le premier chaînon de liste originale et un pointeur représentant la copie de la suite du premier chaînon.

TD

Ecrire une fonction pour chacune des opérations vues en cours.


void ajoute(int v,liste *p) { *p=nouv(v,*p); }

int enleve(liste *l)
{ liste p=*l;    // adresse du premier chaînon
  int v=p->val;  // valeur du premier chainon
  *l=p->suite;   // la liste commence maintenant au deuxième chainon
  free(p);       // on libère la place du premier chaînon
  return v;      // valeur qui était rangée dans le premier chaînon
}

liste eipoc(liste a)
{ liste p=0;
  for(;a;a=a->suite) p=nouv(a->val,p);
  return p;
}

liste retourne(liste l1)
{ liste l2=0, p;
  for(;l1;l1=l1->suite) p=l1, l1=p->suite, // on détache le premier chaînon p de l1
                        p->suite=l2, l2=p; // on l'ajoute en tête de l2
  return l2;
}

liste copieit(liste l) { return retourne(eipoc(l)); }

liste copie(liste a)
{ return a ? nouv(a->val,copie(a->suite)) : 0;
}

suivant précédent sommaire

vendredi 9 décembre 2005 : insertion triée, fusion et trifusion

copie d'une liste avec une seule boucle qui insère en fin de liste

liste copie2(liste a) { if(!a) return a; // liste vide { liste p=nouv(a->val,0), d=p; // premier et dernier chainons de la copie for(;a=a->suite,a;) d=d->suite=nouv(a->val,0); // insertion d'un nouveau chaînon au bout return p; } } On peut aussi partir de la fonction récursive : liste copie(liste a) { liste b; if(a) b=malloc(sizeof(*b)), *b=*a, b->suite=copie(b->suite); return b; } la transformer en une procédure récursive : void copier(liste *aa) { liste b; if(*aa) b=malloc(sizeof(*b)), *b=**aa, *aa=b, copier(&b->suite); } puis la dérécursiver : void copier(liste *aa) { liste b; while(*aa) b=malloc(sizeof(*b)), *b=**aa, *aa=b, aa=&b->suite; } et enfin la transformer en une fonction itérative : liste copie(liste a) { liste b,*aa; for(aa=&a;*aa;aa=&b->suite) b=malloc(sizeof(*b)), *b=**aa, *aa=b; return a; }

insertion dans une liste triée

On pourra tester la procédure d'insertion dans une liste triée avec les instructions suivantes l=0; for(j=0;j<10;j++) l=instri(j*3%10,l),aff(l); qui insèrent dans une liste initialement vide les nombres 0 3 6 9 2 5 8 1 4 7. A la fin liste doit être (0 1 2 3 4 5 6 7 8 9).

fonction récursive

Si la liste est vide ou que l'élément à insérer est plus petit que le premier élément, alors on insère l'élément en tête de liste, sinon on l'insère dans la suite; liste instrirec(int v,liste a) { if(a && a->val<v) a->suite=instrirec(v,a->suite); else a=nouv(v,a); return a; }

procédure récursive

On passe maintenant l'adresse de la variable de type liste : void instrirecp(int v,liste *aa) { if(*aa && (*aa)->val<v) instrirecp(v,&(*aa)->suite); else *aa=nouv(v,*aa); }

procédure itérative

On peut dérécursiver la procédure précédente : void instriitep(int v,liste *aa) { while(*aa && (*aa)->val<v) aa=&(*aa)->suite; *aa=nouv(v,*aa); }

fonction itérative

On peut tranformer la procédure précédente en une fonction : liste instriite(int v,liste a) { instriitep(v,&a); return a; } liste instriite(int v,liste a) { liste *aa=&a; while(*aa && (*aa)->val<v) aa=&(*aa)->suite; *aa=nouv(v,*aa); return a; }

fusion de deux listes triées

On veut écrire une procédure qui part de deux listes chaînées triées dans l'ordre croissant et les fusionne en une liste triée, en gardant les mêmes chainons. Il ne faut donc pas appeler malloc ni nouv. Si une des deux listes est vide on rend l'autre. Sinon on peut comparer le premier élément de chacune des deux listes. Si par exemple le premier élément de a est plus petit que celui de b, alors ce sera le premier élément du résultat de la fusion, et il sera suivi du résultat de la fusion de b et de la suite des éléments de a.
version récursive : liste fusion(liste a,liste b) { if(!a) return b; if(!b) return a; if(b->val>a->val) { a->suite=fusion(a->suite,b); return a; } else { b->suite=fusion(b->suite,a); return b; } } version itérative : liste fusion(liste a,liste b) { liste c, *cc=&c; while(a && b) if(b->val>a->val) *cc=a, cc=&a->suite, a=*cc; else *cc=b, cc=&b->suite, b=*cc; *cc= a ? a : b; return c; }

tri fusion

Pour trier une liste chaînée, on la sépare en deux parties de mêmes longueurs. Si ces deux parties sont non vides, on les trie (récursivement) et on les fusionne. p=(); q=() tant que a n'est pas vide faire on enlève le premier chaînon de a et on l'ajoute en tête de q. on échange p et q fait si q est vide alors // p a au plus un élément et est donc trié on rend p sinon on trie p on trie q on fusionne ces deux listes triées on rend le résultat de la fusion finsi liste trifusion(liste a) { liste p=0, q=0, r; while(a) r=a, a=r->suite, r->suite=q, q=p, p=r; return q ? fusion(trifusion(p),trifusion(q)) : p; } q p a () () (7 4 8 3) () (7) (4 8 3) (7) (4) (8 3) (4) (8 7) (3) (8 7) (3 4) () suivant précédent sommaire

vendredi 16 décembre 2005 : pointeur sur un pointeur

cours

Exécution pas à pas de la procédure de fusion itérative précédente : liste fusion(liste a,liste b) { liste c, *p=&c; while(a && b) if(b->val>a->val) *p=a, p=&a->suite, a=*p; else *p=b, p=&b->suite, b=*p; *p= a ? a : b; return c; } appliquée au deux listes a=(4 6) et b=(5 7). La boucle while est faite trois fois. !_,_,_,_! !_&M4_,_! !_,_,_,4!_&M6_,_! !_,_,_,6!_,_,_,0! // a=(4 6) c=*p c a M4 M6 !_&c,_,_! !_&M5_,_! !_,_,_,5!_&M7_,_! !_,_,_,7!_,_,_,0! // b=(5 7) p b M5 M7 Première itération*p=a, p=&a->suite, a=*p; c=&M4, p=&M4.suite, a=&M6; !_,&M4,_! !_&M6_,_! !_,_,_,4!_&M6_,_! !_,_,_,6!_,_,_,0! // a=(6) c=(4 ...) p=&M4 c a M4 M6 !&M4.sui! !_&M5_,_! !_,_,_,5!_&M7_,_! !_,_,_,7!_,_,_,0! // b=(5 7) p b M5 M7 Deuxième itération *p=b, p=&b->suite, b=*p; M4.suite=&M5, p=&M5.suite, b=&M7; !_,&M4,_! !_&M6_,_! !_,_,_,4!_&M5_,_! !_,_,_,6!_,_,_,0! // a=(6) c=(4 5 ...) p=&M5 c a M4 M6 !&M5.sui! !_&M7_,_! !_,_,_,5!_&M7_,_! !_,_,_,7!_,_,_,0! // b=(7) p b M5 M7 Troisième itération *p=a, p=&a->suite, a=*p; M5.suite=&M6, p=&M6.suite, a=0; !_,&M4,_! !_,_,_,0! !_,_,_,4!_&M5_,_! !_,_,_,6!_,_,_,0! // a=() c=(4 5 6 ...) p=&M6 c a M4 M6 !&M6.sui! !_&M7_,_! !_,_,_,5!_&M6_,_! !_,_,_,7!_,_,_,0! // b=(7) p b M5 M7 *p= a ? a : b; M6.suite= &M7; !_,&M4,_! !_,_,_,0! !_,_,_,4!_&M5_,_! !_,_,_,6!_&M7_,_! // c=(4 5 6 7) c a M4 M6 !&M6.sui! !_&M7_,_! !_,_,_,5!_&M6_,_! !_,_,_,7!_,_,_,0! p b M5 M7 return c; return &M4; // (4 5 6 7)

TD

Compléter les fonctions suivantes :void separe(liste a,int seuil,liste *p,liste *q) // *p={x dans A | x< seuil} // *q={x dans A | x>=seuil} void separen(liste a,int n liste t[n]) // t[j]={x&in; | x mod n=j} liste raboute(int n,liste t[n]) On peut faire deux versions de ces fonctions. Dans la première on construit les listes itérativement dans le même sens en utilisant des pointeurs sur des listes. void separe1(liste a,int seuil,liste *p,liste *q) // *p={x dans A | x< seuil} // *q={x dans A | x>=seuil} { for(;a;a=a->suite) if(a->val<seuil) *p=a, p=&a->suite; else *q=b, q=&b->suite; *p=*q=0; } void separen1(liste a,int n liste t[n]) // t[j]={x&in; | x mod n=j} { liste *p[n]; int j; for(j=0;j<n;j++) p[i]=t+i; for(:a;a=a->suite) j=a->val%n, *p[j]=a, p[j]=&a->suite; for(j=0;j<n;j++) *p[i]=0; } liste raboute1(int n,liste t[n]) { liste c, *p=&c; int i; for(i=0;i<n;i++) for(*p=t[i];*p;p=&(*p)->suite) ; *p=0; return c; } On peut aussi fabriquer des listes retournées en détachant les chaînons en tête d'une liste pour les insérer en tête d'une autre liste. Dans cette version on n'a pas vraiment besoin de pointeur sur des listes. void separe2(liste a,int seuil,liste *p,liste *q) // *p={x dans A | x< seuil} // *q={x dans A | x>=seuil} { *p=*q=0; for(;a;a=a->suite) { liste r=a; a=r->suite; if(r->val<seuil) r->suite=*p, *p=r; else r->suite=*q, *q=r; } } void separen2(liste a,int n liste t[n]) // t[j]={x&in; | x mod n=j} { int j; for(j=0;j<n;j++) p[i]=0; for(:a;a=a->suite) {liste r=a; a=r->suite, r->suite=t[j=r->val%n], t[j]=r;} } liste raboute2(int n,liste t[n]) { liste c=0,p,r; int i; for(i=0;i<n;i++) for(p=t[i];p;) r=p, p=r->suite, r->suite=c, c=r; return c; } suivant précédent sommaire

vendredi 13 janvier 2006 : contrôle

Qu'écrit le programme suivant quand on l'exécute ? #include<stdio.h> void pr(int a,int b) { if(b>0) pr(a+3,b-1),pr(a+2,b-2),pr(a+4,b-1); else printf("%4d",a); } void pr2(int a,int b) { printf("%4d",a); while(b) pr2(a++,--b); } #define a 5 #define b 6 int main() { int i,j,k,l,*p=&i,*q=&j,*r; printf("%4d %4d %4d %4d\n",a&b,a|b,a^b,(a,b)); printf("%4d %4d %4d %4d\n",-a,~a,!a,!!a); printf("%4d %4d %4d %4d\n",i=a,j=b,k=a+b,l=a-b); printf("%4d %4d %4d %4d\n",++i*j--,k+=l--,a<<2,a>>2); printf("%4d %4d %4d %4d\n",++i*j--,k+=l--,a<<2,a>>2); r=p,p=q,q=r; i=a,j=b; printf("%4d %4d %4d %4d\n",i,j,*p,*q); j+=i+=*q, j+=i+=*q; printf("%4d %4d %4d %4d\n",i,j,*p,*q); pr (a,3); printf("\n"); pr2(a,3); printf("\n"); return 0; } Compléter les deux procéduresliste select(liste a,int masque); liste tri(liste a); qui permutent les chaînons d'une liste chaînée. select(a,masque) met en tête tous les chaînons dont la clé v vérifie v\&masque==0. Tous les autres chaînons suivent. Les chaînons gardent l'ordre de la liste initiale s'il le peuvent. tri() trie son argument dans l'ordre croissant des clés en utilisant select. précédent sommaire

vendredi 20 janvier 2006 : corrigé du contrôle

4 7 3 6 -5 -6 0 1 5 6 11 -1 36 10 20 1 35 8 20 1 5 6 6 5 20 36 36 20 14 13 15 10 15 14 16 10 9 11 15 14 16 11 16 15 17 5 5 5 5 6 6 6 7 a=5 101 b=6 110 a&b=4 100 a|b=7 111 a^b=3 011 a<<2=20 10100 a>>2=1 1 (a,b)=(5,6)=6, -a=-5, ~a=~5=-5-1=-6, !a=!5=0, !!a=!0=1.
i=a, j=b, k=a+b, l=a-b valent 5, 6, 11 et -1 et rangent ces quatre valeurs dans i, j, k et l.
++i fait passer i de 5 à 6 et vaut la nouvelle valeur de i : 6. j-- fait passer j de 6 à 5 et vaut l'ancienne valeur de j : 6. ++i*j-- vaut donc 6*6=36.
l-- fait passer l de -1 à -2 et vaut l'ancienne valeur de j : -1. k+=-1 fait passer k de 11 à 10 et vaut 10.
++i fait passer i de 6 à 7 et vaut la nouvelle valeur de i : 7. j-- fait passer j de 5 à 4 et vaut l'ancienne valeur de j : 5. ++i*j-- vaut donc 7*5=35.
l-- fait passer l de -2 à -3 et vaut l'ancienne valeur de j : -2. k+=-2 fait passer k de 10 à 8 et vaut 8.
Avant r=p,p=q,q=r; les variables valent i( 5 ), j( 6 ), p( &i ), q( &j ).
r=p,p=q,q=r; échange les valeurs de p et q. Les variables valent i( 5 ), j( 6 ), p( &j ), q( &i ).
j+=i+=*q est équivalent à j+=i+=i c'est-à-dire à i=i+i, j=j+i. La première exécution change i en 5+5=10 et j en 6+10=16. La deuxième exécution change i en 10+10=20 et j en 16+20=36.
L'appel de procédure pr (a,3); écrit 17 nombres.
L'appel de procédure pr2(a,3); écrit 8 nombres. #include<stdio.h> #include<stdlib.h> typedef struct chainon *liste; struct chainon{int val; liste suite;}; void aff(liste a) { for(;a;a=a->suite) printf("%d ",a->val); printf("\n"); } liste selectm(liste a,int masque) { liste p=0, q=0, r; while(a) if(a->val&masque) r=a, a=r->suite, r->suite=p, p=r; else r=a, a=r->suite, r->suite=q, q=r; while(p) r=p, p=r->suite, r->suite=a, a=r; while(q) r=q, q=r->suite, r->suite=a, a=r; return a; } liste tri(liste a) { int masque; for(masque=1;masque;masque<<=1) a=selectm(a,masque); return a; } liste nouv(int val,liste suite) { liste a=malloc(sizeof(*a)); a->val=val; a->suite=suite; return a; } int main() { liste a=0; int i; for(i=0;i<10;i++) a=nouv(i*3%10,a); aff(a); a=tri(a); aff(a); return 0; }