#include <stdio.h> void main ()

{

  char operation;   int r, a, b;

  printf("Entrez un signe d'opération: "); scanf("%c", &operation);   a=273; b=158; r=0;

  if (operation=='+' || operation=='p')     r = a + b;

  else if (operation=='-' || operation=='m')     r = a - b;

  else if (operation=='*' || operation=='f')     r = a * b;

  else if (operation=='/' || operation=='d')     r = a / b;   else

    printf("Non valable: ");

  printf("%d %c %d = %d\n", a, operation, b, r); }

#include <stdio.h> void main ()

{

char operation;   int r, a, b;

  printf("Entrez un signe d'opération: "); scanf("%c", &operation);   a=273; b=158; r=0;

  switch (operation) {   case '+':   case 'p': r = a + b;     break;       case '-':   case 'm':     r = a - b; break;       case '*':   case 'f':     r = a * b;     break;       case '/':   case 'd':     r = a / b;     break;       default:

  }

  printf("%d %c %d = %d\n", a, operation, b, r); }

#include <stdio.h> void main ()

{ int i, M, N;

do {

printf("Donnez M N: "); scanf("%d %d", &M, &N);

} while (M <= -6 || N >= 6 || M >= N);

i = M; while (i <= N) {

printf("%d ", i); i = i+1;

}

printf("\n");

}

La boucle while simple suivante a un fonctionnement similaire, à la nuance près évoquée plus haut. Avant toute chose, la condition figurant entre parenthèses est évaluée. Si elle est vraie, c'est-à-dire si la valeur courante de la variable i est inférieure à la valeur courante de la variable N, alors les instructions se trouvant entre accolades sont exécutées: la valeur de i est affichée et la valeur courante de i est augmentée de 1. La condition est alors de nouveau évaluée. Si elle est toujours vraie on exécute à nouveau les instructions du bloc. Le programme se poursuit ainsi jusqu'à ce que la condition ne soit plus vérifiée ce qui ne manquera pas d'arriver car la valeur de i est augmentée d'une unité chaque fois que le bloc d'instructions entre accolades est exécuté alors que la valeur de N, elle, n'est pas modifiée. Il est ainsi indispensable que la condition déterminant la fin d'une boucle comporte au moins une variable modifiée à l’intérieur de la boucle sinon la boucle s’exécute indéfiniment ou pas du tout ce qui, la plupart du temps, a des conséquences fâcheuses! Ainsi while(0==0) est une boucle infinie.

Exercice 16.Ecrire un programme qui demande à l’utilisateur de deviner un nombre caché dans le programme. Le programme doit exécuter une boucle qui demande un nombre à l’utilisateur, écrire “trop grand” si le nombre tapé est plus grand que le nombre choisi, “trop petit” si le nombre est plus petit et se terminer en écrivant “vous avez trouvé” lorsque le chiffre correspond exactement à celui qu’on cherche.

6.9  Instruction for

Souvent on souhaite exécuter un bloc d'instructions un certain nombre de fois connu à l'avance en suivant le processus habituel de comptage. Le langage C offre pour cela une instruction pratique: l'instruction for. Dans son utilisation la plus courante, elle se présente comme suit:

for (i=m1; i<=m2; i++) {

}

Ainsi le programme 17 lit deux nombres au clavier et écrit les uns sous les autres une liste de nombres qui va du premier nombre tapé, au deuxième nombre tapé. On note que comme le corps de la boucle for n'est composé que d'une seule instruction alors les accolades peuvent être omises.

Programme 17

Le programme ci-dessous tabule les valeurs des sinus des 10 premiers degrés d’angle.

Programme 18

En fait l'instruction for est plus générale que ce qui a été présenté dans les programmes 17 et 18. En effet, elle est définie plus précisément sous la forme:

for (initialisation; condition; continuation) {

}

qui n'est en fait qu'un raccourci pour la construction suivante:

initialisation; while (condition) { .

continuation; } initialisation, condition et continuation sont trois expressions pouvant être assez quelconques. Comme le montre la construction équivalente utilisant l'instruction while, initialisation est tout d'abord exécutée une seule fois. Ensuite la condition est évaluée à son tour. Si elle est vraie, alors le corps de boucle est exécuté. A la fin de l'exécution du corps de boucle, l'expression continuation est évaluée elle aussi. La

for (i=5; i>0; i--) {

}

La boucle suivante affiche les 5 premières puissances de 2:

for (i=1; i<=32; i=i*2) {

printf(“%d ”, i);

}

Exercice 17.Afficher les 10 premières valeurs d’une liste de nombres. Le premier est 0 et la liste est créée en ajoutant 1, puis 2, puis 3 etc, pour passer d’une valeur à la suivante.

Exercice 18.Lire deux nombres au clavier et afficher tous les nombres depuis le deuxième tapé jusqu’au premier dans l’ordre décroissant.

6.10  Imbrication des instructions

Programme 19

Toutes les instructions de C peuvent s’imbriquer les unes dans les autres. Le programme 19 transforme, dans toutes les phrases de plus de 32 caractères, les majuscules en minuscules et vice versa. Dans ce programme, l’instruction exécutée si la condition (len >= 32) est vérifiée est une boucle for. Les instructions répétées à l’intérieur de cette boucle sont deux tests (caractère minuscule ou caractère majuscule). A l’intérieur de chacun des deux tests se trouve une instruction d’affectation. Chaque rectangle représente l’ensemble des instructions exécutées sous le contrôle d’un test ou d’une boucle. Comme le montre ce programme, les rectangles peuvent être imbriqués. Dans l’instruction if on peut mettre d’autres instructions if, des boucles for, des affectations. A l’intérieur d’une boucle for on peut mettre d’autres boucles for, des tests, des affectations, etc

Pour rendre compte de cette imbrication des structures et améliorer la lisibilité des programmes il est d'usage d'indenter les lignes (c'est-à-dire de les décaler d'un certain nombre d'espaces vers la droite) conformément à leur niveau d'imbrication.

Un tableau se déclare de la façon suivante: float x[200];La variable x représente dans ce cas une suite de 200 variables réelles distinctes. Dans chacun des 200 éléments du tableau x on peut donc déposer une valeur et l’utiliser comme n’importe quelle autre variable: x[20] = 15.0; x[30] = x[5] + 20.0;

La valeur entière figurant entre crochets pour faire référence à un élément particulier du tableau est appelé indice. Le premier élément d'un tableau correspond toujours à l'indice 0. Dans une expression, l'indice peut être donné sous forme d'une constante comme ci-dessus mais peut également être une variable de type int ce qui permet, par exemple, d’imprimer la liste des variables au moyen d’une boucle for:

Si l’on veut les imprimer à 10 par ligne, il faut utiliser une double boucle du type suivant:

Vérifiez que les indices générés valent successivement 0, 1, 2, 3

Le programme suivant présente une autre façon de faire qui évite de calculer l’expression i*10+j à chaque itération et qui permet par la même occasion d’afficher autant de nombres que l’on veut (pas nécessairement un multiple de 10):

Il est possible de créer un tableau d’entiers, de réels, de caractères ou de n'ímporte quel autre type défini qu'il soit de base ou complexe. Il est également possible d'initialiser le contenu d'un tableau au moment de sa déclaration en utilisant une liste de valeurs entre accolades:

int tableau[4] = {2, 3, 12 45};

Pour copier un tableau dans un autre il faut copier les éléments un à un au moyen d'une boucle de type for ou bien utiliser la fonction memcpy.

Exercice 19.Initialiser un vecteur v de 10 réels, et calculer la moyenne des 10 réels. La formule permettant de calculer la moyenne est:

n

vi = 1

Exercice 20.Initialiser un vecteur de 10 éléments, et calculer la variance des 10 éléments. La formule permettant de calculer la variance est:

₁n n ? n ? 2 ?_v = -_n     ?? v i[ ]??

i = 1                                   i = 1                       i = 1

Exercice 21.On demande de trier des nombres déposés dans un vecteur et de les placer dans un ordre croissant dans un autre vecteur. Déposer dans un vecteur les valeurs 3, 6, 1, 9, 2, 5 puis faire un programme qui copie dans un autre vecteur ces mêmes valeurs, mais placées dans l’ordre croissant de 1 à 9.

Pour cela, on va faire un programme de tri simple qui effectue la boucle suivante. Chercher le minimum du vecteur et mémoriser l’indice de l’élément qui contient le minimum. Le déposer dans le vecteur des valeurs triées et remplacer ce minimum par une valeur supérieure à toutes les autres, pour qu’on ne retrouve pas à chaque boucle le même minimum. Recommencer n fois.

Exercice 22.On peut faire le tri en utilisant un seul vecteur. Lorsque vous avez trouvé le minimum du vecteur, échangez-le avec le premier élément, puis cherchez le minimum parmi les éléments 2 à n et placez-le en 2. Puis cherchez de 3 à n, etc

Programme 20

Le programme 21 est un exemple de manipulation de caractères:

Programme 21

Ce programme lit du clavier un caractère introduit par l’utilisateur et l’affecte à la variable carac, de type char. Ensuite on affecte à deux variables distinctes (carac1 et carac2) le décrément et l’incrément de la variable lue. Cette opération est possible puisque dans le langage C les variables caractères de type char sont assimilées à des entiers dont la valeur est celle du code ASCII correspondant au caractère (voir figure 3). On affiche le tout et on lit au clavier un nombre entier. En spécifiant %c dans le printf, nous disons au compilateur de prendre la valeur de la variable de type integer et l’afficher en tant que caractère char.

Notez que tous les caractères ne sont pas des lettres de l’alphabet ou des chiffres. Certains caractères sont appelés caractères de contrôle, et apparaissent à l’écran sous le format ^@, ^A, ^B, ^C. Ils sont utilisés pour contrôler l’affichage du texte (tabulation, retour de ligne, ).

Les variables de type char ne peuvent recevoir qu’un caractère.

char chaine[7];

Dans le programme suivant, on a déclaré une variable appelée votre_nom de type “tableau de 32 caractères maximum” pouvant donc contenir des chaînes de 31 caractères maximum:

Programme 22

Dans le programme 22 on voit comment lire un nom ou une phrase au clavier dans une variable de type tableaux de caractères en utilisant la fonction scanf en utilisant le spécificateur de format %s déjà rencontré dans la fonction printf. Notez également la présence d'une spécification de longueur de champ (voir section 6.3) qui limite à 31 le nombre de caractères lus au clavier par la fonction, ceci afin d'éviter de dépasser la capacité de la variable votre_nom, limitée à 32 caractères (un caractère doit être réservé pour le zéro marquant la fin de chaîne). L'utilisation de la fonction scanf

Il est capital de prendre garde au détail suivant concernant l'utilisation de la fonction scanf. Quand on lit une variable de type numérique simple (par exemple int i;), la syntaxe est:

scanf(“%d”, &i);

Quand on lit une variable tableau de caractères (par exemple char s[12];), la syntaxe est:

scanf(“%11s”, s);

Notez la présence du & accolé à la variable dans le premier cas et son absence dans le deuxième. Ceci est une source d'erreurs graves entraînant le plantage du programme, soyez donc extrêmement vigilants. Les raisons de cette différence seront expliquées au chapitre 8

int s[12]; fgets(s,12,stdin);

Le premier paramètre de cette fonction est la variable désignant le tableau de caractères où la chaîne tapée doit être stockée. Le paramètre suivant est la taille de ce tableau afin que la fonction ne tente pas d'y mettre plus de caractères qu'il n'est possible et le troisième et dernier paramètre sera toujours, pour l'instant stdin qui désigne le clavier.

Le dépassement de la longueur des tableaux de caractères (character buffer overflow) est la cause d'erreurs la plus fréquente dans les programmes en C et conduit le plus souvent à un plantage du programme ou une faille de sécurité. Soyez donc très vigilants à ce sujet: à aucun moment vous ne devez mettre dans un tableau de caractères de chaîne plus grande que la taille maximale pour laquelle vous avez déclaré le tableau.

Par exemple, dans le programme 22, si on avait utilisé un appel scanf sans spécifier la longueur de champ: scanf(“%s”, votre_nom); et que l'utilisateur avait entré un nom de 32 caractères ou plus, la variable votre_nom se serait trouvée en situation de dépassement de capacité et le programme aurait probablement planté.On peut afficher le contenu d'une chaîne contenue dans un tableau de caractères au moyen de la fonction printf.

Il est possible d'initialiser le contenu d'un tableau de caractères avec une chaîne au moment de sa déclaration:

char prenom[32]=”Olivier”;

Dans une telle construction on peut omettre la taille de tableau, le compilateur utilise alors comme taille celle de la chaîne d'initialisation. Ainsi

char prenom[]=”Olivier”;

déclare le tableau prenom comme étant de taille huit caractères (sept caractères pour la chaîne proprement dite plus un pour le zéro final).

Attention: en dehors de l'initialisation, il n'est pas permis d'écrire prenom=”Olivier” (voir section 6.13)

Programme 23

Dans ce programme on a déclaré une variable un_nom de type char [20]et une variable caractere de type char qui permet de mémoriser un seul caractère. Pour désigner la quatrième lettre (qui pourrait se trouver être une espace), on utilise: un_nom[3] (le premier élément se trouve à la position 0!).

La variable caractere, la variable un_nom[3] et la constante ’*’ sont de même type, char. On peut donc copier le contenu de l’une dans l’autre. Cela a été fait pour remplacer la quatrième lettre par une étoile dans le programme ci-dessus. La fonction strlen(un_nom) renvoie la longueur de la chaîne effectivement contenue dans le tableau de caractères (au plus égale à la taille du tableau moins un si aucun dépassement de capacité n'a eu lieu). Notez qu’une chaîne de longueur 1 est différente d’un char.

Exercice 23.Lire une phrase dans une variable et compter combien il y a de mots (compter les espaces). Utiliser une boucle for, de 1 jusqu’à la fin de la phrase (strlen). Si l’on trouve la constante espace, ’ ’, on incrémente la variable qui compte les espaces.

Exercice 24.Lisez deux chaînes de même longueur et comparez-les caractère par caractère. Indiquez dans une variable booléenne si les chaînes sont égales. Conseil, utilisez une boucle for. Essayez les trois cas suivants:

Ecran 5

strcpy. La fonction strcpy(dest,src) permet de copier la chaîne de caractères src dans le tableau de caractères dest.

Le tableau de caractères de dest doit avoir une taille suffisante pour pouvoir contenir la chaîne src sinon il se produit un dépassement de capacité tel qu'il a été décrit au paragraphe 6.12.

Comme indiqué à la fin du paragraphe 6.11 il n'est pas possible de copier un tableau dans un autre au moyen de la simple affectation utilisant le signe '='. Ceci est particulièrement vrai pour les tableaux de caractères. Pour copier une chaîne dans une autre il est donc indispensable d'utiliser la fonction strcpy(dest,src):

2

Programme 24

Ceci vaut également pour les chaînes constantes. Ainsi, l'affectation suivante est incorrecte:

char chaine[7]; chaine = “Coucou”;

Il aurait fallut écrire:

strcpy(chaine,”Coucou”);

strcmp. Des chaînes peuvent être comparées entre elles au moyen de la fonction strcmp. L’ordre correpond à l’ordre lexicographique (celui du dictionnaire), mais les majuscules sont séparées des minuscules. C définit l’ordre suivant: espace 0 < < 9 < A < < Z < a < < z qui correspond à l’ordre donné par les valeurs ASCII des caractères. La fonction strcmp(s1,s2) retourne un entier positif si s1 est alphabétiquement supérieure à s2, 0 si s1 et s2 sont identiques et un entier négatif si s1 est inférieure à s2.

Exercice 26.On peut faire le programme de l’exercice 25 en utilisant seulement deux chaînes de caractères. Pour cela, au fur et à mesure qu’on lit les noms au clavier, on compare le nom qu’on vient de lire (le nom courant) avec le nom précédent. Si le nom courant est plus grand que le nom précédent, le nom courant devient le nom précédent, et l’on lit un nouveau nom au clavier. Sinon le programme s’interrompt.

Exercice 27.Même programme que le précédent, mais avant d’utiliser l’instruction de comparaison, s’assurer que chaque caractère est majuscule. Si l’on découvre une minuscule, c’est-à-dire comprise entre ’a’ et ’z’, on lui soustrait la valeur ’a’ - ’A’. C’est logique, puisqu’elles sont dans l’ordre, la distance entre une minuscule et sa majuscule est toujours la même.

Attention, les caractères peuvent s’additionner. On a par exemple:

Programme 25

strcat. La fonction strcat permet de concaténer deux chaînes de caractères. Ainsi l'appel strcat(dest,src) permet d'ajouter la chaîne src à la fin de la chaîne dest:

Programme 26

Le tableau de caractères de destination doit avoir une taille suffisante pour pouvoir contenir la chaîne de départ plus la chaîne ajoutée sinon il se produit un dépassement de capacité tel qu'il a été décrit au paragraphe 6.12

Exercice 29.Lire une chaîne au clavier (ou déposer une chaîne constante dans une variable) et l’imprimer sans qu’apparaissent les lettres ’a’ qui seraient contenues dans cette chaîne.

Exercice 30.Lire un nom au clavier puis l’afficher en mettant un signe - entre chaque lettre.

Exercice 31.Lire un mot au clavier. Afficher ensuite combien il y a de ’a’ dans le mot.

Exercice 32.Lire une chaîne au clavier (ou déposer une chaîne constante dans une variable), composer une nouvelle chaîne de caractères qui contienne toutes les lettres de chaîne lue, sauf les ‘a’. Imprimer la nouvelle chaîne de caractères.

6.14  Les instructions break et continue

Nous avons déjà rencontré l'instruction break en relation avec l'instruction switch (voir section 6.7). En fait l'instruction break est plus générale et peut être utilisée également dans le corps des boucles while, dowhile et for. Elle a pour effet dans ce cas de sortir immédiatement de la boucle et de poursuivre l'exécution du programme à l'instruction se trouvant immédiatement après l'accolade marquant la fin du corps de boucle.

Par exemple le programme suivant calcule le nombre de lettres du premier mot d'une phrase entrée par l'utilisateur:

Programme 27

La boucle for parcourt normalement tous les indices de 0 à strlen(phrase)-1, toutefois à l'intérieur du corps de boucle on teste si la lettre située à l'indice courant est une espace et si c'est le cas on interrompt immédiatement le déroulement de la boucle grâce à break, ainsi i contient la taille du premier mot.

Programme 28

La boucle se déroule de 0 à strlen(phrase)-1. A l'intérieur du corps de boucle on teste si la lettre courante est une espace, si c'est le cas l'instruction continue passe immédiatement à l'itération suivante en ignorant le reste du corps de boucle sinon on incrémente la variable nblettres et on affiche la lettre courante.

Dans de nombreux cas une utilisation judicieuse des variables booléennes permet d'éviter d'avoir recours à l'instruction break. Dans le programme ci-dessous, on désire déterminer si dans une chaîne de caractères déposée dans une variable, le caractère ’a’ apparaît ou non:

#include <stdio.h> #include <string.h> void main () { char un_mot[32];   int i;   printf("Donnez un mot: ");   scanf(“%31s”, un_mot);   for (i=0; i < strlen(un_mot); i++) { if (un_mot[i]=='a') {       printf("Il y a au moins un 'a'\n");       break;     }   }   if (i == strlen(un_mot) + 1)     printf("Il n'y a pas de 'a'\n"); } Dans le programme précédent, on a dû se fier à la valeur de i pour savoir après la boucle s’il y avait un ’a’ ou non dans le mot. C’est une façon de faire qui n’est pas très explicite, elle rend donc le programme plus difficile à comprendre. Le programme suivant a exactement le même rôle que le programme précédent, mais le fait qu’un ’a’ soit présent ou non est mémorisé dans la variable booléenne present: #include <stdio.h> #include <string.h> void main () { char un_mot[32]; int present, i; printf("Donnez un mot: "); scanf(“%31s”, un_mot); for (i=0; i <= strlen(un_mot); i++) { present = (un_mot[i] == 'a'); if (present) break; } if (present) printf("Il y a au moins un 'a'\n"); else printf("Il n'y a pas de 'a'\n"); } Programme 30 A chaque itération de la boucle, present reçoit la valeur de la condition testant si la lettre examinée dans un_mot est un ’a’ ou pas, c'est-à-dire une valeur non-nulle si cette lettre est un ’a’ ou zéro sinon. Si present devient vrai alors la boucle est interrompue au moyen de l'instruction break. Notez qu'un programmeur C expérimenté abrégerait le corps de boucle comme suit: if (present=(un_mot[i]==’a’)) break; En effet une instruction d'affectation a comme valeur la valeur affectée, donc une expression telle que present=(un_mot[i] == ’a’); a pour valeur la valeur de la variable present après l'affectation et peut donc être utilisée directement comme condition dans un if. Exercice 33.Ajoutez un test dans la condition du for qui teste si present est encore faux (négation present) pour continuer la boucle. Vous pouvez alors supprimer du corps de boucle le test sur present qui arrête la boucle au moyen du break. N’oubliez pas d’initialiser present avant la boucle faute de quoi elle pourrait ne jamais être exécutée. Exercice 35.Modifier l’exercice précédent en remplaçant la boucle do-while par une boucle while. Exercice 36.Créer un programme qui demande à l’utilisateur de deviner un mot. Pour cela il faut définir deux variables: une qui contient le mot à deviner et une autre qui contient une étoile à la place de chaque lettre (remplacer les lettres par des étoiles dans une boucle for). Ensuite effectuer une boucle dans laquelle on demande une lettre à l’utilisateur, puis on recherche où se trouve la lettre dans le premier mot et on remplace l’étoile située à la même position dans le deuxième mot, jusqu’à ce que les deux mots soient égaux (jeu du pendu). 6.15  Tableaux multidimensionnels, matrices Une matrice 2x2 de nombres réels à deux dimensions, M, est représentée sous la forme d'un tableau bidimensionnel que l'on déclare comme ci-dessous: float M[2][2]; L’élément d’une matrice Mij est désigné en C par M[i][j]. Par convention i désigne la ligne et j la colonne. On peut initialiser un tel tableau au moment de sa déclaration grâce à la construction suivante: int m[2][2] = {{3, 4}, {0, 2} }; Une fois initialisé on ne peut changer les valeurs du tableau que case par case (voir section 6.11) Exercice 37.Déclarer deux vecteurs de dimension 2 et une matrice de dimensions 2x2. Déposer dans la matrice des valeurs qui représentent une rotation d’un angle a. Rappel 1: une matrice qui effectue une rotation de a radians est représentée ci-dessous: cos(a) –sin(a) sin(a) cos(a) Déposer dans le premier vecteur V les valeurs (1.0, 0.0) et calculer dans le deuxième W le produit de la matrice M par ce vecteur. Ceci revient à calculer un deuxième vecteur déterminé par une rotation de a du premier vecteur autour du centre des axes. Rappel 2: le produit matriciel est donné ci-dessous: W[0] = M[0][0] ? V[0] + M[0][1] ? V[1] W[1] = M[1][0] ? V[0] + M[1][1] ? V[1] Exercice 38.On ne peut faire le calcul explicite du produit matriciel que si le nombre de termes dans chaque dimension est petit. Pour de plus grandes dimensions, il faut utiliser l’instruction for, ce que nous allons introduire dans cet exercice en deux étapes. Première étape: remarquez qu’on peut calculer chacune des deux coordonnées du vecteur W au moyen d’une boucle: #include <stdio.h> void main () {   float V[2] = {6.0, 5.0};   float W[2] = {0.0, 0.0};   float M[2][2] = {{3.2, 4.5},                    {2.0, 5.3}};   int i;   for (i = 0; i < 2; i++)     W[0] = W[0] + M[0][i] * V[i];   for (i = 0; i < 2; i++)     W[1] = W[1] + M[1][i] * V[i]; } Programme 31 Deuxième étape: on peut faire ce même calcul au moyen de deux boucles for imbriquées dont la boucle extérieure parcourt les éléments de W. Cela permet de faire des produits matrice par vecteur dont la dimension est quelconque, en mettant une variable n à la place de 2. Vous pouvez maintenant généraliser à un tableau de taille N. Exercice 39.On demande d’écrire un programme qui initialise une matrice M avec les valeurs M[i][j] = 3i + j, et affiche la matrice. On demande ensuite de transposer la matrice, c’est-à-dire d’échanger les éléments M[i][j] et M[j][i], pour toutes les valeurs de i et de j. 4     5     6 7     8     9 10 11 12 = 4    7 10 5    8 11 6    9 12 Par exemple, si la matrice M est de taille 3, cela donnera les résultats suivants: T Exercice 40.On demande d’écrire un programme qui initialise une matrice M avec les valeurs M[i][j] = 3i -j, et affiche la matrice. On demande ensuite à l’utilisateur d’indiquer deux lignes de la matrice (par exemple la 1ère et la 3ème) et d’échanger deux lignes de la matrice. Par exemple, échanger la ligne 1 et la ligne 3 donnera les résultats suivants: 2 1 0 5 4 3 8 7 6 13 = 5 4 3 2 1 0 EL 6.16  Constructions abrégées Le C offre un certain nombre de raccourcis d'écriture pour des instructions fréquentes. Le tableau 6 en résume quelques-unes parmi les plus utilisées. Dans ce tableau a, b et c sont des variables numériques entières ou non: Construction abrégée Construction équivalente a++; a = a+1; ++a; a = a+1; a--; a = a-1; --a; a = a-1; a += b; a = a+b; a -= b; a = a-b; a *= b; a = a*b; a /= b; a = a/b; a=(b>0) ? 12 : c; if (b>0) a = 12; else a = c; Tableau 6: Constructions abrégées Les 4 premières lignes présentent des instructions d'incrémentation et de décrémentation. On remarque que deux notations différentes existent: la notation postfixée où le signe ++ ou -- se trouve après le nom de variable et la notation préfixée où ces signes se trouvent avant le nom de la variable. Ces deux notations, préfixée et postfixée, incrémentent (resp. décrémentent) toutes deux la variable considérée mais présentent une différence fondamentale: l'expression ++a incrémente a avant de prendre sa valeur alors que a++ incrémente a après avoir pris sa valeur. Donc si a vaut 5, l’expression b = a++; met la valeur 5 dans b et incrémente ensuite a qui passe à 6 alors que l'expression b = a++; incrémente d'abord a qui passe donc à 6 et met ensuite cette valeur dans b qui vaut alors 6 L'opérateur ternaire (condition) ? val1 : val2 est une expression très concise qui prend la valeur val1 ou val2 selon que condition est vraie ou fausse. Accumulation dans une variable réelle. Beaucoup de calculs arithmétiques se résument à une somme ou un produit de plusieurs variables. Un exemple de somme est le produit scalaire, qui calcule la somme des produits n – 1 des éléments de deux vecteurs a et b (tableau de réels) de dimension n, et qui peut s’écrire x = ? aibi . Faire i = 0 une somme de plusieurs éléments revient en langage de programmation à accumuler les résultats intermédiaires dans une variable: #include <stdio.h> #include <stdlib.h> #define SIZE 4 void main () { float a[SIZE], b[SIZE], x; int i; // initialisation des vecteurs for (i=0; i<SIZE; i++) { a[i] = 100*((float)rand()/RAND_MAX); b[i] = 100*((float)rand()/RAND_MAX); } // affichage des vecteurs printf("A = "); for (i=0; i<SIZE; i++) printf("%f ", a[i]); printf("\nB = "); for (i=0; i<SIZE; i++) printf("%f ", b[i]); // accumulation du produit scalaire x = 0; for (i=0; i<SIZE; i++) x = x + a[i] * b[i]; // affichage du produit scalaire printf("\nProduit scalaire = %f\n", x); } Programme 32 Un autre exemple d’accumulation est l’exercice 17. Dans la même catégorie, on trouve les programme qui calculent:                                                                                                              ?n – 1   ? •    la moyenne arithmétique des éléments d’un vecteur: a = ? ? ai? ? n , cf. exercice 19,                                                                                                                ?i = 0    ? •    la variance des éléments d’un vecteur: ? = ?? ? ai ? ? n? – (a) , cf. exercice 20,                                                                                     ??i = 0    ?    ?                                                                                  ??n – 1       ?    ?        •    la covariance de deux vecteurs a et b µ = ?? ? aibi? ? n? – (ab) ,                                                                                  ??i = 0       ?    ? n – 1 •    la factorielle d’un nombre n! = ? i , i = 0 n – 1 •    le produit matriciel cij = ? aikbkj , k = 0 p               p p           p •    combinaisons Cn = n! ? (n – p)!p! ou Cn = ? (n – p + i) ? ? i i = 1                           i = 1 n i •    calcul de polynôme de degré n y =cix . i = 0 Accumulation dans une chaîne de caractères. Les exercices 28 à 31 demandent simplement d’afficher un à un des caractères à l’écran. Cependant, le but d’un programme n’est pas souvent d’afficher des caractères à l’écran, mais plus souvent d’affecter une variable (c’est-à-dire lui donner une valeur), comme il l’est demandé dans l’exercice suivant. Ceci conduit à une erreur très fréquente qui est illustrée ci-dessus pour l’exercice 28: #include <stdio.h> #include <string.h> void main () { char s1[32], s2[32]; int i,len; printf("Chaine? "); fgets(s1,32,stdin); len = strlen(s1); strcpy(s2, "");     for (i=len-1; i>=0; i--) s2[(len-1)-i] = s1[i];      /* accumulation */ Programme 33 Dans cet exemple on construit la chaîne s2 en ajoutant les caractères un par un dans les cases du tableau de caractères “à la main”, c'est-à dire sans utiliser des fonctions de librairie comme strcat. Dans ce cas l'erreur consiste à oublier de marquer la fin de chaîne en omettant le caractère '\0' final (voir section 6.12). Si tel est le cas, la fonction printf n'est pas en mesure d'afficher correctement la chaîne s2 à la ligne suivante et il peut même se produire un plantage du programme. Logique booléenne. On demande d’écrire un programme qui vérifie qu’une matrice M est antisymétrique (pour tous les i et les j, M(i,j) = -M(j, i)). Cela donne généralement lieu à de nombreuses erreurs de logique: Programme 34 Les deux programmes ci-dessus ne fonctionnent pas. Par exemple, dans le programme de gauche, il suffit qu’il existe un i et un j tel que m[i][j] == -m[j][i] pour que la variable booléenne antisym devienne vraie. Le second programme indique seulement si le terme m[SIZE-1][SIZE-1] de la matrice est nul. La bonne façon de faire est montrée ci-dessous: #include <stdio.h> #include <stdlib.h> #define SIZE 4 void main () { float m[SIZE][SIZE]; int i, j, antisym; // Initialisation de la matrice for(i=0; i<SIZE; i++) { for(j=0; j<SIZE; j++) { m[i][j]=i-j; } } antisym = 1; //Initialisation // Accumulation for(i=0;i<SIZE;i++) { for(j=0;j<SIZE;j++) { if (m[i][j] != -m[j][i]) { antisym=0; } } } printf("Antisym= %d",antisym); } Exercice 41.Ecrire un programme qui vérifie qu’une chaîne de caractère est un palindrome, c’est-à-dire que la première et la dernière lettre sont identiques, la seconde et l’avant-dernière sont identiques, la troisième et l’antépénultième sont identiques, etc. Exercice 42.Ecrire un programme qui vérifie que tous les éléments d’un vecteur sont ordonnés en ordre croissant. Exercice 43.Ecrire un programme qui vérifie qu’une chaîne de caractère contient la lettre e. Exercice 44.Ecrire un programme qui vérifie qu’une chaîne de caractère NE contient PAS la lettre e. Exercice 45.Ecrire un programme qui vérifie qu’une matrice contient au moins un élément nul. Exercice 46.Ecrire un programme qui vérifie qu’une matrice ne contient que des éléments positifs. Exercice 47.Ecrire un programme qui vérifie qu’une matrice contient au moins un élément positif. Exercice 48.Le programme 35 n’est pas des plus efficaces. Considérez une matrice m[0..999,0..999], dont l’élément m[0,0] est non nul. Après avoir observé le premier élément, on sait qu’elle n’est pas antisymétrique. En général, il est inutile de parcourir tous les éléments de la matrice dès que l’on est sûr qu’elle n’est pas antisymétrique. Pouvez-vous modifier le programme 35 de façon à ce que le programme s’interrompe dès que la variable antisym a pris la valeur logique fausse. Il y a deux façons de faire: soit modifier la condition de boucle soit utiliser l'instruction break. Les sections suivantes vous apprendront à utiliser des routines graphiques existantes (sections 7.1 et 7.2), des fonctions de calcul matriciel (section 7.3) et des fonctions mathématiques existantes (section 7.4), puis à écrire vous même des fonctions (section 7.5). Le chapitre 11 contient deux sections avancées sur les fonctions, la première expliquant les modules et la compilation séparée (section 12), et la seconde décrivant des routines d'interaction avec l'écran graphique, permettant notamment de créer des jeux simples (section 13). 7.1  Module graphique Le but de cette section est de vous apprendre deux choses: d'une part l'utilisation d'une bibliothèque de routines (library) d'autre part le contenu d'une bibliothèque d'affichage à l'écran. Considérons le programme 36. Après la directive habituelle #include <stdio.h>, il contient une autre directive #include, suivie d’un nom de fichier entre guillemets, "Graphics.h". Le fait d’utiliser ici des guillemets plutôt que <> indique juste que Graphics.h n'est pas une librairie standard. #include <stdio.h> #include "Graphics.h" void main () { FillRectangle (100, 100, 200, 300) ; printf("Pressez Return pour terminer le programme\n"); getchar () ; } Programme 36 Le fichier Graphics.h est ce qu'on appelle un fichier d'interface (header file). Il contient une liste d'interfaces de fonction précisant le nombre et le type des paramètres ainsi que le type de retour de chaque fonction. L'intérêt des fonctions est qu'elles agissent comme des boîtes noires: il n'est pas nécessaire de savoir comment elles fonctionnent en interne pour pouvoir s'en servir, une simple description de ce qu'elles font ainsi que la connaissance de leur interface suffit. void SetWindowSize (int sizeX, int sizeY) ; void Delay (int millisec) ; Programme 37 Par exemple, l'interface de la fonction FillRectangle (première ligne du programme 37) a quatre paramètres de type entier, int, appelés left, top, right et bottom. Elle dessine dans une fenêtre graphique un rectangle plein dont le coin supérieur gauche a pour coordonnée (left, top), et le coin inférieur droit (right, bottom). Le programme 36 contient un appel à la fonction FillRectangle. Un appel de fonction est un nom de fonction suivi de paramètres effectifs. Il faut que le nombre et le type de paramètres effectifs correspondent au nombre et au type de chacun des paramètres formels. En l'occurrence, il faut spécifier 4 valeurs entières entre parenthèses dans l'appel de la fonction FillRectangle. Une fonction est en fait un emballage pour une série d'instructions (parfois très longue) qui effectue la commande suggérée par le nom de la fonction. La série d'instructions qui correspond au nom de la fonction s'appelle le corps de la fonction. Dans les sections 7.1 à 7.4, nous nous contenterons de lire des interfaces de fonctions et de faire des appels de fonctions. Dans la section 7.5 nous écrirons des interfaces et corps de fonctions et les appellerons. Pour résumer, il y a trois notions importantes liées à l'utilisation des fonctions: l'interface (nom de la fonction et liste de ses paramètres), le corps (la liste des instructions qui effectuent la commande suggérée par le nom de la fonction), et l'appel de fonction (l'utilisateur demande que la fonction soit utilisée avec une valeur spécifique pour chacun des paramètres). Les routines SuspendRefresh et ResumeRefresh sont des routines d’optimisation de la performance. Lorsqu'on a beaucoup de primitives graphiques (rectangles, lignes, cercles) à dessiner, il vaut mieux d'abord interrompre le rafraîchissement d'écran (SuspendRefresh), dessiner toutes les primitives, et relancer le rafraîchissement d'écran qui affichera alors toutes les primitives d'un coup. Le fichier Graphics.h déclare également la routine Delay qui permet de suspendre l'exécution d'un programme pendant un certain nombre de millisecondes. Cela est utile pour simuler le mouvement (afficher un point, attendre 50ms, l'effacer, et afficher le point à un autre endroit). Pour compiler le programme 36, on utilise les commandes suivantes: cosun12% gcc -g -o grp graphics-first.c -l$GLIB Dans la ligne de commande, vous reconnaissez la ligne de commande classique gcc -g -o grp graphics-first.c On doit ajouter l'option -l$GLIB (moins PETIT ell dollar glib majuscules) à la fin de la commande. Le point (0,0) d'une fenêtre graphique se trouve par convention dans le coin supérieur gauche. La coordonnée x croît vers la droite. La coordonnée y croît vers le bas (figure 4). La figure 4 montre aussi la fenêtre graphique résultant de l'exécution du programme 36.                                 fenêtre graphique                                     FIGURE 4: Fenêtre graphique Exercice 49.Faire le dessin d’une maison dont les points sont donnés ci-dessous: (100,10) (150,40) (150,130) Exercice 50.Lire une valeur au clavier et dessiner la maison de sorte que le coin en bas à gauche soit placé au même endroit et que la maison soit dessinée à l’échelle donnée par le nombre lu. Exercice 51.Dans cet exercice, on demande de dessiner un sinus qui fait deux oscillations sur la largeur de l’écran (0 à 400). Exercice 53.Dans cet exercice, on demande d’afficher la fonction sin(x) * sin(x + Pi/3) de façon que le tracé tienne entre les horizontales 20 et 180. Cherchez le maximum et le minimum de la fonction dans une première boucle puis affichez la fonction à l’échelle. Exercice 54.Dessiner des figures de Lissajou sur la fenêtre graphique. Les figures de Lissajou sont des figures créées par le déplacement d’un point dont les coordonnées en x et en y varient selon des fonctions sinus de différentes fréquences. On calcule donc x = sin(t) et y = sin(cste*t) pour des valeurs croissantes de t, et on affiche les points (x;y) proprement décalés pour qu’ils apparaissent dans l’écran.csteest une constante réelle dont la valeur est choisie par l’utilisateur. Exercice 55.Reprendre l’exercice 38, mais afficher dans la fenêtre graphique un cercle de 5 pixels de rayon à la position donnée par les coordonnées x et y. Pourquoi le point descend-il lorsque vous appuyez ‘h’. 7.2  Module d’affichage de fonctions On se rend compte, dans les exercices de la section 7.1, qu’ajuster les fonctions dans la fenêtre graphique présente une certaine difficulté, et surtout que cette difficulté se répète pour chaque nouvelle fonction. La difficulté provient de ce qu’il faut convertir les coordonnées de graphe (réels, par exemple (t, sin(t))) en coordonnées d’écran (entiers, par exemple (50,150)). Le module introduit dans cette section permet de contourner la difficulté. Le fichier Graphs.h contient la liste des fonctions aidant à l’affichage des fonctions mathématiques. Il utilise lui-même le module Graphics.h. (programme 38): void SetScreenSize(int l,int t,int r,int b); void SetGraphSize(float l,float t,float r,float b); void DrawGraphLine(float fromGX, float fromGY, float toGX, float toGY); void DrawGraphPoint(float hereX, float hereY, int radius); FIGURE 5: Fenêtre, écran, graphe (window, screen, graph) La figure 5 montre, dans une fenêtre graphique de taille (400,400), un écran (c’est-à-dire une sous-fenêtre) de taille (200,200) dont le coin supérieur gauche a pour coordonnées (200,100). Dans cet écran, on dessine la fonction sinus dans l’intervalle (0,2?). La taille de la fenêtre graphique est définie à l’aide de la fonction SetWindowSize (module Graphics.h). Les tailles d’écran et de graphe (définis à l’aide des fonctions SetScreenSize et SetGraphSize) servent simplement à définir les rapports entre les coordonnées d’écran et de graphe. Dans le cas de la figure 5, le point (0,1) dans le graphe correspond à la coordonnée (200,100) dans la fenêtre graphique, et le point (2?, -1) dans le graphe correspond à la coordonnée (400,300) dans la fenêtre graphique. Le programme 39 permet d’afficher la fonction sinus entre 0 et 2? en x, et entre -1 et 1 en y, dans la fenêtre 200,100,400,300: #include <stdio.h> #include "Graphics.h" #include "Graphs.h" #include "math.h" #define PI 3.14159 void main () { float x; SetScreenSize(200,100,400,300); SetGraphSize(0,1,2*M_PI,-1); for (x=0; (x + 0.01) <= (2*M_PI); x = x + 0.01) { DrawGraphLine (x,sin(x),x+0.01,sin(x+0.01)); } getchar(); } Programme 39 Comme précédemment, pour compiler ce programme, vous devez utiliser la commande de compilation: cosun12% gcc -g -o drawsinus drawsinus.c -l$GLIB Exercice 56.Dans le programme 39, la fonction sinus est appelée deux fois à chaque itération de la boucle while. Réécrivez ce programme de façon à n’appeler qu’une fois la fonction à chaque itération de la boucle. Exercice 57.Dans cet exercice, on demande d’afficher la fonction sin(x) * sin(x + Pi/3) de façon que le tracé tienne entre les horizontales 20 et 180 (voir exercice 53). Cette fois-ci, utilisez les routines du module Graphs.h 7.3  Module de calcul matriciel Le fichier matrix.h (Prog. 40) contient les déclarations des fonctions de calcul matriciel mises à votre disposition. VectorPT CreateVector(unsigned int size); void DeleteVector(VectorPT mpt); MatrixPT CreateMatrix(unsigned int lines, unsigned int cols); void DeleteMatrix(MatrixPT mpt); double GetVectorElement(VectorPT vpt, unsigned int index) ; void SetVectorElement(VectorPT mpt, unsigned int index, double value); double GetMatrixElement(MatrixPT mpt, unsigned int line, unsigned int col) ; void SetMatrixElement(MatrixPT mpt, unsigned int line, unsigned int col,                       double value); void WriteVector (VectorPT vpt); void WriteMatrix (MatrixPT mpt); double ScalarProduct (VectorPT v1, VectorPT v2); void MatVectMult (MatrixPT mpt, VectorPT vpt, VectorPT rpt ); void MatMatMult (MatrixPT mpt1, MatrixPT mpt2, MatrixPT rpt); void SolveSystem (MatrixPT spt, VectorPT rpt); Programme 40 Cet ensemble de fonctions permet de manipuler des vecteurs et des matrices m × n. Deux nouveaux types sont ainsi définis VectorPT et MatrixPT. Pour se servir d'une matrice ou d'un vecteur il faut d'abord non seulement le déclarer mais aussi le “créer” au moyen des fonctions CreateVector et CreateMatrix. Quand on a fini de s'en servir il faut le détruire au moyen de DeleteMatrix ou DeleteVector. Par exemple, pour utiliser une matrice de 3 lignes et 2 colonnes: MatrixPT myMatrix; myMatrix = CreateMatrix(3,2); DeleteMatrix(myMatrix); Pour utiliser un vecteur à 3 composantes: VectorPT myVector; myVector = CreateVector(3); DeleteVector(myVector); On peut consulter et fixer les valeurs d'une matrice ou d'un vecteur au moyen des fonctions GetVectorElement, SetVectorElement, GetMatrixElement et SetMatrixElement. Le programme 41 montre l’utilisation de quelques routines du module de calcul matriciel. Il s’agit simplement d’un programme qui réalise l’exercice 60 (rotation d’un vecteur à l’aide du calcul matriciel) en utilisant les fonctions déclarées dans le fichier d'en-tête matrix.h. On peut remarquer que l’on s’est débarrassé de toutes les boucles et donc des risques d’erreurs. #include <stdio.h> #include "matrix.h" #include "math.h" void main () {   MatrixPT m;       /* Declaration de la matrice m */ VectorPT v, w;    /* Declaration des vecteurs v et w*/ double a;   a = M_PI / 4;   m = CreateMatrix(2,2); /* Création de la matrice m */   v = CreateVector(2);  /* Création du vecteur v */   w = CreateVector(2);     /* Création du vecteur w */   SetVectorElement(v,0,1); SetVectorElement(v,1,0); SetMatrixElement(m,0,0,cos(a)); SetMatrixElement(m,0,1,-sin(a)); SetMatrixElement(m,1,0,sin(a)); SetMatrixElement(m,1,1,cos(a)); printf("m = \n"); WriteMatrix(m);   printf("v = \n"); WriteVector(v);   MatVectMult (m,v,w);   printf("w = \n"); WriteVector(w); DeleteMatrix(m);   DeleteVector(v);   DeleteVector(w); } Programme 41 On remarque que le programme débute par la déclaration des variables matrice et vecteurs et qu’ensuite ils sont créés par les appels à CreateMatrix et CreateVector. Des valeurs sont ensuite fixées grâce aux fonctions SetVectorElement et SetMatrixElement. Pour pouvoir utiliser le module de calcul matriciel, copiez les fichiers matrix.h dans ~/include et libmatrix.a dans ~/lib s'ils ne s'y trouvent déjà pas. Ces fichiers se trouvent dans ~gennart/include et ~gennart/lib. La ligne de compilation requise pour compiler un programme testmat.c qui utilise le module de calcul matriciel est alors: Exercice 60.On demande de tracer les points générés par la rotation du vecteur défini dans l’exercice 37. Pour cela, créer une fonction qui affiche un point dont les coordonnées sont passées en paramètre (vecteur). Dans le programme principal, initialiser une matrice de rotation M, initialiser un vecteur à (80, 0) et faire une boucle de 1 à 100 appelant la procédure de multiplication de matrice puis la procédure qui dessine le vecteur. A chaque boucle, transférer le résultat dans le vecteur placé en deuxième position dans MatVectMult. Exercice 61.Faire une horloge dont les aiguilles sont représentées par des points de grandeurs différentes. Pour cela utilisez si nécessaire les trois modules introduits jusqu’ici. 7.4  Le module de fonctions mathématiques Le dernier module que nous allons utiliser dans le cadre de ce cours contient des fonctions mathématiques. Certaines des fonctions mathématiques présentées ici ont déjà été introduites dans la section 6.5 #defineM_E2.7182818284590452354 #defineM_LOG2E1.4426950408889634074 #defineM_LOG10E0.43429448190325182765 #defineM_LN20.69314718055994530942 #defineM_LN102.30258509299404568402 #defineM_PI3.14159265358979323846 #defineM_PI_21.57079632679489661923 #defineM_PI_40.78539816339744830962 #defineM_1_PI0.31830988618379067154 #defineM_2_PI0.63661977236758134308 #defineM_2_SQRTPI1.12837916709551257390 #defineM_SQRT21.41421356237309504880 #defineM_SQRT1_20.70710678118654752440 extern double acos (double); extern double asin (double); extern double atan (double); extern double atan2 (double, double); extern double cos (double); extern double sin (double); extern double tan (double); extern double cosh (double); extern double sinh (double); extern double tanh (double); extern double pow (double, double); extern double sqrt (double); extern double ceil (double); extern double fabs (double); extern double floor (double); extern double fmod (double, double); Programme 42 Une fonction peut être utilisée dans une expression quelconque, comme l’illustre le programme 43, qui montre dans un cas particulier que la tan(?) est effectivement égale à sin(?)/cos(?). On remarque qu’en langage C, on peut appeler une fonction à l’intérieur même d’une autre fonction. Ici, il n’est pas nécessaire de faire le calcul puis de le mettre dans une variable avant d’afficher la variable. On peut simplement mettre le calcul à effectuer à l’endroit où on met la valeur à afficher. Ceci est dû au fait que les fonctions mathématiques retournent une valeur (voir section 7.5). #include <stdio.h> #include <math.h> void main () { float theta = 1.0; printf("tan(theta) = %8.3f %8.3f\n", tan(theta), sin(theta)/cos(theta)); } Programme 43 La librairie mathématique du langage C est normalisée, pour l'utiliser il faut simplement rajouter l’option -lm lors de la compilation: cosun12% gcc -g -o program43 program43.c -lm 7.5  Fonctions Jusqu’à présent, nous nous sommes contentés d’utiliser des fonctions existantes. On se rend compte, au fur et à mesure que l'on écrit des programmes plus complexes, que l'on réécrit souvent les mêmes instructions C pour effectuer la même tâche. C’est alors le moment de commencer à écrire ses propres fonctions. Une fonction est un morceau de programme auquel est attribué un nom. On peut appeler cette fonction depuis un point quelconque du programme principal ou d’une autre fonction en mentionnant simplement son nom. On distingue donc d’une part la définition de la fonction et d’autre part son appel. Pour illustrer notre propos, nous allons écrire une fonction qui convertit des degrés fahrenheit en degrés celsius (Prog. 44): Déclaration et définition. Une définition de fonction commence par un mot-clé de type qui correspond au type de la valeur de retour, le type particulier void indiquant que la fonction ne retourne rien. Viennent ensuite le nom de la fonction suivi de paramètres placés entre parenthèses. Ce sont les paramètres formels car ils définissent la forme que va prendre l’appel de la fonction, c’est-à-dire le nombre et le type de ces paramètres. On peut avoir de 0 à n paramètres formels. Chaque paramètre formel est défini par le type de la variable suivi du nom de la variable. Cet ensemble: nom de la fonction, type de retour, nombre et type des paramètres s'appelle l'interface, l'en-tête, le prototype ou la signature de la fonction. La partie suivante de la définition d'une fonction, placée entre une accolade ouvrante et une accolade fermante, constitue le corps de fonction. Sa structure est la même que celle du corps de la fonction main: tout d'abord une suite optionnelle de déclarations de variables propres à la fonction, suivie d'instructions à exécuter. Parmi ces instructions, l'instruction return a un effet particulier: elle interrompt immédiatement le déroulement de la fonction en renvoyant la valeur de l'expression située à sa droite qui se trouve ainsi être la valeur de retour de la fonction. Cette expression doit donner une valeur du type déclaré comme type de retour par l'interface de la fonction. Dans le cas du programme 44, lorsque l'exécution parvient à l’appel FahrToCelsius(tempf), le programme copie les valeurs des paramètres de l’appel, appelés paramètres effectifs dans ceux de la définition, appelés paramètres formels. En l'occurrence, ici, la valeur de la variable tempf est copiée dans la variable fahr pour la durée de l'exécution de la fonction. Donc pendant l'exécution du corps de cette fonction fahr prend la valeur 35. Lors de l'appel FahrToCelsius(12), fahr prend la valeur 12 pendant l'exécution du corps de la fonction. Lors d'un appel tel que FahrToCelsius(tempf), c'est bien la valeur de la variable tempf au moment de l'appel, c'est-à-dire le nombre 32, qui est copiée dans fahr pour être ainsi passée à la fonction et non pas la variable tempf elle-même. Ainsi, si le contenu de la variable fahr était modifié à l'intérieur de la fonction FahrToCelsius cela n'aurait aucune influence sur la valeur de la variable tempf qui continuerait de valoir 32. C'est pourquoi on dit que le C passe les paramètres aux fonctions par valeur. Ainsi il n'est a priori pas possible de modifier la valeur d'une variable extérieure de l'intérieur d'une fonction. En fait cela est possible en passant comme paramètre non pas une variable elle-même mais un pointeur sur elle (voir section 8.5) Dans l’appel de la fonction les paramètres effectifs sont séparés par des virgules et le type n’apparaît pas (car il est déjà défini par la déclaration de la fonction). Les paramètres effectifs peuvent avoir les mêmes noms que les paramètres formels. Mais en principe on appelle la même fonction avec différents jeux de paramètres effectifs, ce qui justifie d’avoir les deux sortes de paramètres. Exercice 62.Ecrire un programme qui définit et appelle plusieurs fois une fonction qui convertit des degrés minutes secondes en radians. La formule est: radians = ------- ?                     60             3600 Exercice 63.Ecrire une fonction qui calcule la valeur y d’un polynôme de degré 3, sachant la valeur des coefficients c0, c1, c2, c3 et l’abscisse x. Pour l’exercice 63, la formule du polynôme est bien entendu y = c0 + c1x + c2x2 + c3x3. Comment calculer la nième puissance de x? On peut bien entendu utiliser des formules sophistiquées basées sur les logarithmes (attention aux nombres négatifs), ou trouver un module qui contient une fonction qui calcule yx, avec y et x réels. Cependant, dans le calcul du polynôme, on sait que l’exposant est entier. Il vaut donc mieux utiliser une boucle qui calcule xi, en initialisant x à 1, et en multipliant i fois par x. On peut cependant faire mieux, en factorisant le polynôme de la façon suivante: y = c0 + x (c1 + x (c2 + c3x)). Ceci réduit le nombre de multiplications à n pour un polynôme de degré n, contre n*(n+1)/2 pour la formule non factorisée. Utilisez si possible la formule factorisée pour calculer le polynôme. Exercice 64.Créer une fonction qui calcule le nombre de combinaisons d’un ensemble de n pièces prises m par m: m – 1                                                                    ?m?                          !                                                                    ? n?             m! ? (n – m)!m          i i = 1 Attention, la fonction factorielle donne des résultats qui dépassent rapidement la capacité des entiers de type int. Il vaut mieux utiliser la formule simplifiée qui calcule le rapport de deux produits. Exercice 65.Ecrire et tester une fonction qui calcule la norme d’un vecteur (x,y). Variables globales et variables locales. On peut déclarer des variables à l’intérieur d’une fonction comme nous l'avons fait jusqu'ici dans la fonction main. De telles variables ne sont visibles que dans la fonction où elles sont déclarées, elles n'ont pas d'existence ailleurs et le compilateur signale une erreur si l'on tente de s'en servir ailleurs. On appelle ces variables, variables de fonction ou variables locales, par opposition aux variables déclarées en dehors de toute fonction (y compris la fonction main) qui, elles, sont visibles dans tout le programme après leur déclaration, c'est-à-dire dans toutes les fonctions. On appelle ces variables, variables de programme ou variables globales. Le programme 45 est pratiquement identique au programme 44. Il montre l’utilisation de d'une variable locale, celsius, dans la fonction FahrToCelsius: #include <stdio.h> #include <math.h> int FahrToCelsius(int fahr); int tempc; void main () {   int tempf = 35;   tempc = FahrToCelsius(tempf); printf("%d F -> %d C\n", tempf, tempc); printf("%d F -> %d C\n", 12, FahrToCelsius(12)); } int FahrToCelsius(int fahr) { int celsius; celsius = 5*(fahr-32)/9; return celsius; } Programme 45 Dans ce programme, la variable celsius ne peut être utilisée que dans la fonction FahrToCelsius. L'utiliser dans la fonction main produirait une erreur de compilation. De même tenter d'utiliser la variable tempf dans la fonction FahrToCelsius provoque également une erreur. Par contre, la variable tempc, déclarée en dehors de toutes les fonctions, est une variable globale et peut être utilisée à la fois dans main et dans FahrToCelsius. Deux variables déclarées dans deux fonctions différentes peuvent avoir le même nom: ce seront cependant deux variables différentes. Une variable de programme peut avoir le même nom qu’une variable locale. Dans la fonction, après la déclaration de la variable locale, seule la variable locale reste visible. Une façon d’éviter toutes ces subtilités est de choisir des noms différents pour toutes les variables de votre programme, quel que soit l’endroit de leur déclaration et de limiter au maximum l'emploi de variables globales. A la rigueur, vous pouvez utiliser la variable i comme indice de boucle à plusieurs endroits, mais n’oubliez pas de la déclarer dans toutes les fonctions où vous l’utilisez et surtout ne la déclarez jamais globale. Ci-dessous vous avez un programme assez simple (programme 46) où le programmeur emploie par inadvertance deux fois la variable x, mais ne la déclare qu’une fois globalement. Pouvez-vous expliquer pourquoi ce programme n’affiche aucun ovale alors qu'on pourrait penser qu'il en affiche 40 ? #include <stdio.h> #include <math.h> #include "Graphics.h" int x, y; int ComputePosition(int abscisse) { int ordonnee = abscisse; for(x=1; x<=1000; x++) ordonnee = ordonnee * 7 % 400; return ordonnee; } void main () { for (x=10; x < 400; x+=10) { y = ComputePosition(x); DrawOval(x-2,y-2,x+2,y+2); }   getchar(); } Programme 46 L’exemple suivant va vous permettre de vérifier si vous avez compris les règles de visibilité précédentes. #include <stdio.h> #include <math.h> float x, fact; float factorielle(float x) {   int i; float z = 1.0; for (i=2; i<=floor(x); i++) { z = z * i; } x = 0; fact = z; return fact; } void main() {   x = 12;   fact = factorielle(x);   printf("Factorielle de %1.0f = %1.0f\n", x, fact);   fact = 4; factorielle(4.0);   printf("Factorielle de 4.0 = %1.0f\n", fact); } On en tire les conclusions suivantes: l’instruction printf("%1.0f %1.0f\n",x,fact) placée dans la fonction affiche la valeur du x global. Cette valeur n'est pas changée par l'appel factorielle(x) car la variable x visible à l'intérieur de la fonction factorielle est locale et masque la variable globale du même nom. L'affectation x=0 n'a donc pas d'incidence sur la variable x globale. La valeur du x affichée par le premier printf du programme principal est donc 12.0. D’autre part comme fact est une variable globale, elle est connue aussi bien à l’intérieur de la fonction factorielle qu'à l'intérieur de la fonction main. Comme il n'y a pas, à l'intérieur de factorielle, de variable de même nom, l'affectation fact=z; modifie la variable fact globale et le deuxième printf affiche donc bien la valeur de la factorielle de 4 et non pas 4.0 comme on pourrait s'y attendre. 8  Adresses et valeurs: pointeurs Un pointeur est une variable qui contient l'adresse d'une autre variable. Cette notion constitue souvent un obstacle majeur pour les débutants en C. Pourtant, si un usage confus peut effectivement rendre incompréhensible un programme utilisant des pointeurs, le concept est en lui-même très simple à comprendre et repose sur le fonctionnement même des mémoires d'ordinateur. En C l'utilisation de pointeurs est incontournable car ils sont étroitement liés à la représentation des tableaux et donc des chaînes de caractères. Ainsi, certaines notions qui ont pu vous sembler obscures dans les sections précédentes, comme le fait que l'affectation au moyen du signe = des variables tableaux de caractères ne copiait en fait pas ces chaînes, vont trouver ici des explications lumineuses! N'hésitez pas à relire ce chapitre plusieurs fois. mémoire FIGURE 6: Structure d’un ordinateur et de la mémoire La mémoire d'un ordinateur est en fait un composant électronique (appelé RAM) au fonctionnement relativement simple. Ce composant stocke une série de bits dont on peut écrire la valeur et venir la relire plus tard. Pour des questions de commodité on ne lit/écrit pas ces bits un par un mais par paquets de huit, ce que l'on appelle un octet (byte). Un unique composant de RAM peut ainsi stocker plusieurs millions d'octets. Quand on veut en lire ou en écrire un il faut naturellement indiquer au composant lequel. Pour cela il suffit de donner son numéro, en effet tous les octets contenus dans la mémoire sont numérotés de 0 jusqu'à n-1 pour une mémoire contenant n octets. Ce numéro permettant d'identifier individuellement chacun des octets de la mémoire est appelé adresse. Graphiquement la mémoire d'un ordinateur peut donc être représentée comme une série de cases numérotées de 0 à n-1 contenant chacune un octet, c'est à dire un nombre entier de 0 à 255 (figure 7). 3 255 17 28 32 47 255 0 0 255 28 0                            0         1         2         3         4         5         6         7         8         9        10       11 En programmation, on devrait donc, pour utiliser des valeurs dans la mémoire procéder à des opérations du genre “ranger la valeur 12 à l'adresse 1036”, “prendre la valeur rangée à l'adresse 1024, l'additionner à la valeur rangée à l'adresse 1036 et ranger le résultat de l'opération à l'adresse 1058”. Naturellement ceci n'est guère pratique car cela demanderait une sacré gymnastique pour se souvenir de toutes ces adresses, tous les numéros finissant par se ressembler à la longue. C'est pourquoi le langage C offre des variables. Les variables ne sont ainsi ni plus ni moins que de simples labels arbitraires que l'on donne à des cases mémoires pour éviter d'avoir à utiliser leur adresse numérique. On peut ainsi utiliser des noms plus faciles à retenir plutôt que des adresses numériques. Lorsque vous déclarez des variables dans un programme C, le compilateur choisit lui-même des emplacements disponibles dans la mémoire et établit une correspondance entre les noms de variables choisis et les adresses de ces emplacements. Considérons le programme suivant: #include <stdio.h> #include <stdlib.h> void main() { int x, i; float r; short int j,k; char str[24]; x = 3; strcpy(str,"Hello"); x = x + 1; } Programme 48 En supposant qu’un float prend 8 octets de place mémoire, un int 4 octets, un short 2 octets, et une chaîne caractères, n octets, le compilateur pourrait organiser les données en mémoire comme suit: x : int ; i : int; r : float; j, k: short int;  str : char[24]; FIGURE 8: Organisation de variables en mémoire Au passage, notez le 0 à l'adresse 1019 qui indique la fin de la chaîne à l'intérieur du tableau de 24 caractères. Ce modèle d’exécution est extrêmement simple, mais très général. C’est ce qui fait la puissance des ordinateurs. La chose importante à retenir donc est que chaque variable que vous déclarez est caractérisée par deux choses: son adresse en mémoire et sa valeur. 8.2  Les pointeurs Comme indiqué précédemment, les adresses des octets en mémoire et par la même, les adresses des variables, sont de simples nombres entiers. Rien n'empêche donc d'affecter ces adresses à une autre variable. Considérons la figure 8, on y remarque que l'adresse de la variable i est 1004, nous pouvons tout à fait stocker cette valeur 1004 dans une autre variable, c'est-à-dire dans un autre emplacement de la mémoire. Une telle variable numérique qui contient une valeur qui n'est pas réellement utile en soi mais se trouve être l'adresse d'une autre variable est ce que l'on appelle un pointeur car elle indique (pointe) l'emplacement d'une autre variable dans la mémoire. Le langage C dispose d'un opérateur pour prendre l'adresse d'une variable, l'opérateur unaire &. Ainsi dans la situation de la figure 8 toujours, l'expression p=&i; met dans la variable p la valeur 1004, adresse de l'emplacement mémoire correspondant à la variable i. On dit alors que p pointe sur i ou que p est un pointeur sur i. Un pointeur est donc une variable contenant une adresse. Comme une adresse est un nombre entier, on pourrait penser que les pointeurs sont des variables de type int tout simplement. En fait pas exactement, le langage C distingue les pointeurs suivant le type de la variable qu'ils pointent. Ainsi p qui contient l'adresse de la variable i doit être de type “pointeur sur int”. Le langage C utilise la notation suivante pour déclarer une variable d'un tel type: int *p; j = *p; met la valeur 2 365 961 dans la variable j. Cette opération consistant à prendre la valeur de la case mémoire pointée par un pointeur constitue un déréférencement ou indirection. Mais la construction *p peut également être utilisée pour ranger une nouvelle valeur dans la case mémoire dont l'adresse est contenue dans p. Ainsi l'instruction: *p=12; range la valeur 12 dans la case mémoire d'adresse 1004, valeur de p. Or la variable i est rangée à cet endroit de la mémoire aussi, donc cette opération a pour effet de changer la valeur de la variable i également qui devient égale à 12. A beaucoup d'égards, comme ils contiennent des adresses qui ne sont en fait que des nombres, les pointeurs se comportent comme de simples variables numériques. Ainsi si l'on définit un autre pointeur sur int: int *q; l'affectation q=p; est légale. Elle a pour effet de fixer la valeur de q à 1004. Donc q se retrouve contenir l'adresse de i, tout comme p. q devient ainsi un autre pointeur sur i et toute utilisation des expressions *q et *p est donc rigoureusement équivalente. Considérons le programme suivant qui résume ces notions: void main() { int v=12; int u=10; int *vP; /*pointeur sur int*/ vP = &v; /*affectation du pointeur */ u = *vP; printf(“u=%d v=%d\n”,u,v); *vP = 25; printf(“u=%d v=%d\n”,u,v); } Adresses: Programme 49 L’organisation des données en mémoire est la suivante: v : int u : int vP : int *                             Après vP=&v                            Après u=*vP                             Après *vP=25 A chaque type prédéfini du langage ou bien défini par le programmeur (voir l'instruction typedef, section 10.1) on associe un type pointeur. On peut ainsi définir des variables de type “pointeur sur float”, des variables de type “pointeur sur char”, etc De tels types de pointeurs sont incompatibles, bien que tous soient en réalité des adresses de variables, donc contiennent en fait une valeur numérique entière. Il n'est pas possible de mettre telle quelle l'adresse d'une variable de type int dans un pointeur sur float. Ceci est dû au fait que lors d'un déréférencement, c'est-à-dire quand on examine le contenu d'un emplacement de mémoire pointé par un pointeur, au moyen de la construction *ptr, l'interprétation faite des nombres contenus dans la mémoire varie suivant le type considéré. Ainsi si ip est un pointeur sur un entier: int *ip, l'instruction i=*ip doit aller examiner le contenu de la mémoire à l'adresse contenue dans ip. Comme ip est un pointeur sur un int et qu'un int occupe 32 bits, on sait que l'on doit considérer 4 octets consécutifs à partir de l'adresse contenue dans ip pour déterminer la valeur de *ip. Maintenant si sp est un pointeur sur un short: short int *sp, l'instruction s=*sp doit de même aller examiner le contenu de la mémoire à l'adresse contenue dans sp. Mais comme sp est un pointeur sur un short et qu'un short n'occupe que deux octets en mémoire, il suffit d'examiner deux octets et non plus quatre pour déterminer la valeur de *sp. On voit ainsi que, bien que ip et sp contiennent tous deux des adresses numériques en mémoire analogues, ils sont en fait de types différents car l'interprétation qui doit être faite de *ip et *sp respectivement est différente. C'est pourquoi le programme suivant provoque un avertissement du compilateur: main() {   int *ip;   short s;   ip = &s; /* Avertissement du compilateur !!! */ } Pointeur générique. Dans certaines situations il est nécessaire de conserver et manipuler une adresse mémoire sans nécessairement savoir ou donner d'indication sur le type des données qui sont stockées à cet endroit. Le C dispose pour de tels cas du type pointeur générique. On déclare un tel pointeur de la façon suivante: void *ptr; Un tel pointeur ne peut pas être déréférencé, c'est-à-dire qu'il est illégal d'utiliser l'expression *ptr, ce qui s'explique simplement par le fait que l'on ne dispose pas d'information sur le type de données contenu en mémoire à l'adresse indiquée par ptr (on ne sait donc pas si on doit considérer un, deux, quatre octets ou plus pour déterminer la valeur de *ptr). Si l'on veut pouvoir déréférencer un pointeur générique, il faut donner une indication sur les données contenues en mémoire à l'adresse indiquée par le pointeur en utilisant une conversion explicite du type du pointeur (cast). Par exemple: (int *)ptr convertit le pointeur générique en pointeur sur int. Nous reviendrons sur les pointeurs génériques dans la section consacrée à l'allocation dynamique de la mémoire (section 8.6). Pointeur NULL. Avant d'être initialisée, une variable locale de type pointeur, comme toute variable locale non initialisée, contient une valeur indéterminée. S'il n'y prend garde, le programmeur peut tenter d'utiliser une telle valeur qui pointe une case mémoire quelconque, cela conduit le plus souvent à un plantage immédiat du programme. Pour éviter ce problème, il est courant d'affecter à une variable de type pointeur la constante NULL qui vaut zéro. Cette valeur particulière indique de façon explicite que le pointeur n'est pas initialisé et ne contient pas d'adresse utilisable. int t[5]; A quoi correspond le nom symbolique t? A quelle adresse en mémoire est-il associé? Le langage C ne reconnaissant que des types de base proches de ceux que manipule le microprocesseur (donc essentiellement des nombres), il n'est pas en mesure d'associer le nom t aux 20 octets qu'occupe effectivement en mémoire un tableau déclaré de cette façon. En fait C associe au nom t simplement l'adresse où commence le tableau en mémoire. Considérons le programme suivant: #include <stdio.h> main() { int t[5] = {31, 14, 21, 12, 24}; int *ip;     printf(“t=%x\n”, t);          /* Affiche la valeur de t en hexa */ printf(“&t[0]=%x\n”, &t[0]); /* Affiche l'adresse du 1er element du tableau */ printf(“*t=%d\n”, *t);   /* Affiche la valeur de *t */ printf(“t[0]=%d\n”,t[0]); /* Affiche la valeur de t[0] */ ip = t; *ip = 17; printf(“t[0]=%d\n”, t[0]); } Programme 51 Les trois premières lignes de la fonction main déclarent trois variables t, ip et i. Voici le contenu de la mémoire juste après l'exécution de ces 3 lignes: t[0] int t[5] t[1] t[2] t[3] t[4] int ip FIGURE 10: Organisation de la mémoire (programme 51, initialisations) La déclaration int t[5] définit un tableau de 5 ints, c'est-à-dire un bloc de 5 entiers consécutifs en mémoire notés t[0], t[1], t[4]. Les deux premiers appels à la fonction printf affichent les valeurs des variables t et &t[0] en hexadécimal. On constate en exécutant ce programme que ces valeurs sont les mêmes. La valeur de t est l'adresse du premier élément du tableau, t[0]. Cette remarque est d'une extrême importance.                           La valeur d'une variable de type tableau est l'adresse du premier élément du tableau Comme la valeur de t est l'adresse, 1000, du premier élément du tableau et que le tableau contient des ints, l'affectation ip=t est légale et place la valeur 1000 à l'adresse 1014 associée à ip, faisant de ce fait pointer ip sur le premier élément du tableau, t[0]. La mémoire est alors dans l'état suivant: t[0] int t[5] t[1] t[2] t[3] t[4] int ip FIGURE 11: Organisation de la mémoire (programme 51, affectation de ip) L'affectation suivante, *ip=17 a pour effet de placer la valeur 17 à l'adresse pointée par ip, en l'occurrence 1000, c'est-à-dire que la valeur de t[0] est changée, ce que confirme le printf suivant. Par de nombreux aspects donc, le nom de tableau, t, se comporte comme un pointeur. Il existe toutefois une différence essentielle: un nom de tableau n'est pas une variable au sens propre et on ne peut donc en changer la valeur. Des instructions telles que t=&i ou t++ sont signalées comme des erreurs par le compilateur. Ceci explique que l'on ne puisse utiliser simplement l'opérateur = pour copier un tableau dans un autre, cela ne ferait pas de sens. Tableaux multi-dimensionnels. Les tableaux multi-dimensionnels sont en tout point semblables aux tableaux mono-dimensionnels évoqués précédemment. Là encore les différents éléments du tableau sont disposés dans des espaces successifs en mémoire et le nom symbolique associé au tableau a en fait pour valeur l'adresse du premier élément du tableau. Prenons le cas du programme suivant: #include <stdio.h> void main() { int i,j; int m[4][4]; for(i=0;i<4;i++) for(j=0;j<4;j++) m[i][j] = i + j; for(i=0;i<4;i++) { for(j=0;j<4;j++) printf("%d ",m[i][j]); printf("\n"); } } 4 4 0 1 2 3 1 2 3 4 2 1000 int i 1004 int j 1008 m[0][0]         m 100c m[0][1] 1010 m[0][2] 1014 m[0][3] 1018 m[1][0] 101c m[1][1] 1020 m[1][2] 1024 m[1][3] 1028 m[2][0] FIGURE 12: Organisation de la mémoire (tableau bidimensionnel) 8.4  Arithmétique des pointeurs Les pointeurs étant des variables contenant des adresses numériques donc en fait des nombres entiers, on peut leur appliquer des opérations arithmétiques, notamment incrémentation et décrémentation. Toutefois il y a quelques subtilités de taille qui distinguent l'arithmétique des pointeurs de celle des simples entiers. Considérons le programme suivant: #include <stdio.h> main() { int t[5] = {31, 14, 21, 12, 24}; int *ip, *ipbis; ip = t; ipbis = t+1; printf(“%d %d\n”,*ip,*ipbis); printf(“ip=%x\nipbis=%x\n”,ip,ipbis); } Programme 53 Après son exécution la mémoire se trouve dans l'état suivant: t[0] int t[5] t[1] t[2] t[3] t[4] int ip int ipbis FIGURE 13: Arithmétique des pointeurs L'affectation ip=t, place la valeur 1000 dans ip, faisant pointer cette variable vers le premier élément du tableau t, t[0]. Par définition, le langage C assure que ip+1 pointe vers le deuxième élément du tableau, ip+2 pointe vers le troisième et ainsi de suite. Ainsi l'instruction ipbis=ip+1 place dans ipbis l'adresse du deuxième élément du tableau, t[1], c'est-à-dire la valeur 1004 et non pas 1000+1=1001 comme on aurait pu le croire à première vue. Cette affirmation est d'ailleurs confirmée par le résultat des deux printfs. Quel que soit le type pointé, si p est un pointeur sur un élément d'un tableau, alors p+1 est un pointeur sur l'élément suivant, p+i est un pointeur sur le ième élément suivant. Une fréquente source d'erreur chez les débutants en C consiste à confondre valeur du pointeur et valeur pointée par le pointeur. Dans la situation de la figure 13, la valeur du pointeur ip est 1000, celle du pointeur ipbis est 1004. La valeur pointée par ip (notée *ip) est 31, celle pointée par ipbis (notée *ipbis) est 14. Il y a de ce fait une différence fondamentale entre les deux expressions ip=ipbis et *ip=*ipbis. La première fait passer la valeur de ip de 1000 à 1004 qui est la valeur de ipbis. ip se retrouve ainsi pointant sur le même emplacement mémoire que ipbis. La deuxième expression, *ip=*ipbis, fait passer la valeur pointée par ip de 31 à 14 qui est la valeur pointée par ipbis. Le configuration résultant de ces deux expressions est illustrée dans la figure suivante: *ip = *ipbis t[0]                                                int t[5]t[0]                                                int t[5] t[1]t[1] t[2]t[2] t[3]t[3] t[4]t[4] int ipint ip int ipbisint ipbis FIGURE 14: Valeur de pointeur et valeur pointée 8.5  Utilisation de pointeurs comme arguments de fonctions Comme il a été signalé dans la section 7.5, lors d'un appel de fonction les valeurs des variables sont copiées pour être passées à la fonction (passage par valeur). Dès lors il ne semble pas possible de modifier une variable depuis l'intérieur d'une fonction. Considérons l'exemple suivant: #include <stdio.h> void incremente(int e) { e = e+1; } main() { int i = 12; incremente(i); printf(“i=%d\n”,i); } La variable i est locale à main et n'est donc pas visible depuis incremente. Il existe néanmoins un moyen pour en modifier le contenu depuis la fonction incremente, il faut pour cela utiliser un pointeur. L'idée consiste à transmettre à la fonction incremente, plutôt qu'une valeur à incrémenter comme nous l'avons fait jusqu'ici, l'adresse en mémoire où se trouve l'entier à incrémenter. En quelque sorte, jusqu'à maintenant le corps de la fonction faisait “ajoute un au nombre entier qui est donné” et ce nombre était perdu. Désormais il faut qu'elle fasse “ajoute un à l'entier se trouvant à tel endroit donné dans la mémoire”. Si cet endroit de la mémoire correspond à une variable alors la valeur de cette variable sera changée, même si elle est extérieure à la fonction! Le programme précédent est modifié comme suit: #include <stdio.h> void incremente(int *e) { *e = *e+1; } main() { int i = 12; incremente(&i); printf(“i=%d\n”,i); } Programme 55 On remarque dans cette nouvelle version que la fonction incremente attend désormais comme paramètre, non plus un simple nombre entier, mais plutôt un pointeur sur un nombre entier (int *e), c'est-à-dire l'adresse d'une case mémoire où se trouve un nombre entier. Ce que fait désormais la fonction c'est d'aller consulter cet emplacement de la mémoire pour relever l'entier qui s'y trouve contenu, y ajouter un et replacer cette nouvelle valeur au même endroit de la mémoire (*e=*e+1). Ainsi programmée, la fonction incremente est à même de changer le contenu d'une variable externe. Ce mécanisme consistant à passer comme argument de fonction non pas la valeur d'une variable mais son adresse est très souvent utilisé pour plusieurs raisons: •    comme les paramètres sont passés par valeur, c'est-à-dire copiés pour être utilisés localement par la fonction, le temps de copie peut devenir non négligeable si le type de l'objet sur lequel la fonction travaille est grand. Dans ce cas il est plus judicieux d'éviter la copie de l'objet et de passer simplement à la fonction un pointeur dessus, c'est-à-dire l'adresse en mémoire où l'objet peut être trouvé •    une fonction ne peut retourner qu'une valeur par la construction return (même si cette valeur peut être complexe). Or, dans certains cas, on peut souhaiter plusieurs valeurs en retour. Ainsi la fonction FahrToCelsius du programme 44 n'a besoin de renvoyer qu'une température et peut donc être codée sous la forme d'une fonction retournant un int. Imaginons par contre une fonction convertissant des coordonnées cartésiennes du plan (x y) en coordonnées polaires (r ?) . Une telle fonction a besoin de retourner deux valeurs. Pour cela on peut lui passer comme paramètre l'adresse de deux variables où la fonction pourra ranger les valeurs calculées de  et r ? #include <stdio.h> #include <math.h> void CartToSpher(float x, float y, float *r, float *theta) { *r = sqrt(x*x + y*y);   *theta = atan(y/x); } void main () {   float x1,y1;   float r1,theta1;   x1 = 1;   y1 = 1; CartToSpher(x1,y1,&r1,&theta1);   printf("r1 = %5.3f theta1 = %5.3f (radians)\n",r1,theta1); } Exercice 66.Ecrire une fonction qui permet d'échanger les valeurs de deux variables passées en paramètre Notons pour terminer que nous avons déjà rencontré une fonction modifiant des variables externes en utilisant pour cela un passage de paramètres par adresse: la fonction scanf. Grâce à ce qui précède on comprend pourquoi tous les arguments de cette fonction doivent être des pointeurs. On comprend également pourquoi dans le cas de variables simples on utilise l'opérateur & pour en obtenir l'adresse alors que cela n'est pas nécessaire dans le cas de tableaux puisque leur nom représente déjà un pointeur. Passage de tableaux en paramètre. Comme expliqué à la section 8.3, les variables de type tableau ont en fait pour valeur l'adresse du premier élément du tableau et, de ce fait, se comportent comme des pointeurs. Donc dire que l'on passe une variable de type tableau à une fonction est en fait un abus de langage, on passe en fait l'adresse de début de ce tableau et non pas une copie du tableau. Cela peut être vu comme une entorse au principe de passage des paramètres par valeur et il faut donc y faire attention. #include <stdio.h> #include <stdlib.h> void Vecteur2DCarre(int vect[]) { vect[0] = vect[0] * vect[0]; vect[1] = vect[1] * vect[1]; } void main() { int vecteur[2] = {3, 5}; Vecteur2DCarre(vecteur); printf("Vecteur[0] : %d\n",vecteur[0]); printf("Vecteur[1] : %d\n",vecteur[1]); } Programme 57 Le programme 57 montre bien que le tableau vecteur, local à main, passé à la fonction Vecteur2DCarre est bien modifié par cette dernière. L'interface de la fonction Vecteur2DCarre aurait également pu s´écrire void Vecteur2DCarre(int *vect) On peut noter au passage qu'aucune information sur la taille du tableau n'est passée à la fonction Vecteur2DCarre. De l'intérieur de la fonction, rien ne garantit que le tableau effectivement passé à la fonction est bien de taille 2 comme la fonction s'y attend et rien ne permet de le vérifier. Seule une bonne discipline du programmeur permet de ne pas faire d'erreur dans ce cas. Autant dire que cette situation est une cause potentielle de nombreuses erreurs. La fonction Vecteur2DCarre a une sémantique qui indique qu'elle travaille sur des tableaux de taille fixe deux. Par contre d'autres fonctions peuvent avoir besoin de travailler sur des tableaux de taille quelconque. Imaginons une fonction SommeVecteur calculant la somme des éléments d'un tableau d'entiers de taille variable. Le premier paramètre d'une telle fonction serait un tableau d'entiers int t[]. A l'intérieur on additionnerait les éléments du tableau t[0], t[1], mais à quel indice s'arrêter? En passant t comme paramètre à la fonction on lui indique juste le début de la zone de mémoire où sont rangées les valeurs des différents entiers du tableau, on ne lui indique pas combien il y en a ou bien où s'arrête le tableau. On peut trouver plusieurs solutions à ce problème. La plus simple consiste à rajouter un paramètre à la fonction permettant d'indiquer le nombre d'éléments du tableau elle est illustrée dans le programme 58. #include <stdio.h> int SommeVecteur(int t[], int taille) { int i, somme=0; for (i=0; i<taille; i++) { somme += t[i]; } return sommae; } main() { int vect[5] = {2,3,5,3,2}; printf(“Somme=%d\n”, SommeVecteur(vect, 5)); } #include <stdio.h> int SommeVecteur(int t[]) { int i, somme=0; for (i=0; t[i]!=0; i++) { somme += t[i]; } return somme; } main() { int vect[6] = {2,3,5,3,2,0}; printf(“Somme=%d\n”, SommeVecteur(vect)); } Programme 59 En pratique on utiliserait plutôt pour cet exemple, la première méthode. La deuxième n'est pas complètement dénuée de sens toutefois puisque c'est celle qui est utilisée pour la manipulation des chaînes de caractères comme le montre le paragraphe suivant. Exercice 67.Ecrivez et testez une fonction qui calcule la moyenne d’un vecteur de taille quelconque. Exercice 68.Ecrivez et testez une fonction qui calcule la moyenne et la variance d’un vecteur de taille quelconque. Exercice 69.Ecrivez une fonction qui trouve l’indice des éléments minimum et maximum dans un vecteur de taille quelconque. Exercice 70.Ecrire un programme qui calcule la valeur d’un polynôme de degré N, connaissant ses N+1 coefficients et l’abscisse x (voir exercice 63). Passage de pointeurs et tableaux de caractères en paramètre. La section 8.3 a montré combien les tableaux et pointeurs sont étroitement liés. En langage C, les chaînes de caractères sont manipulées sous forme de tableaux de caractères et il existe donc là encore une liaison très forte avec la notion de pointeurs. Les pointeurs de caractères sont, de très loin, les plus courants dans les programmes écrits en langage C. Dès lors, appliquons tout ceci à la rédaction d'une fonction permettant de changer les o en a dans une chaîne de caractères passée en paramètre: #include <stdio.h> void ChangeOA(char s[]) { int i=0; while (s[i] != 0) { if (s[i]==’o’) s[i] = ’a’; i++; } } main() { char chaine[]=”Hello world !”; ChangeOA(chaine); printf(“%s\n”, chaine); } Programme 60 Dans cet exemple un tableau de caractères chaine est alloué et initialisé avec la chaîne “Hello world !”. Pour fixer les idées disons que ce tableau est située dans une zone mémoire commençant à l'adresse 1036. Lors de l'appel de la fonction ChangeOA cette valeur, 1036, est affectée au paramètre s qui se trouve ainsi pointant sur le début de la chaîne chaine en mémoire. Cette situation est illustrée par la figure 15. A l'intérieur de la FIGURE 15: Organisation de la mémoire (appel de fonction et chaîne de caractères) fonction ChangeOA, toute expression de la forme s[i] fait donc référence à un caractère de chaine et non pas une quelconque copie. Toute affectation dans s[i] change donc bien chaine comme le confirme le printf. Par contre tout changement de la valeur de s elle même est sans effet sur la chaîne. Tout changement de la valeur de s ne fait que changer la case mémoire pointée mais pas la valeur contenue dans cette case mémoire. Grâce à cette remarque et en utilisant les propriété de l'arithmétique des pointeurs évoquées à la section 8.4, on peut éviter l'utilisation de la variable additionnelle i dans la fonction ChangeOA: il suffit de changer la valeur de s pour lui faire pointer successivement un par un les caractères de la chaîne en s'arrêtant au zéro final, c'est ce que fait la version améliorée suivante: void ChangeOA(char s[]) { while (*s != 0) { if (*s == ’o’) *s = ’a’; s++; } } Exercice 72.Ecrire la fonction strcpy(char dest[], char src[]) qui copie une chaîne src (y compris le '\0' final) dans le tableau de caractères dest que l'on supposera de taille suffisante Exercice 73.Ecrire la fonction strncpy(char dest[], char src[], int n) qui copie n caractères de la chaîne src dans le tableau de caractères dest en tronquant src si elle est trop longue ou en remplissant avec des zéros si elle est trop courte 8.6  Pointeurs et allocation dynamique de variables Une autre situation très courante où les pointeurs sont utilisés concerne ce que l'on appelle l'allocation dynamique d'espace mémoire. Il existe en effet des situations où l'on ne sait pas, au moment où l'on écrit un programme, quelle taille il va falloir donner à un tableau. Imaginons par exemple, un programme qui lise un texte depuis le disque dur pour le mettre dans un tableau de caractères en mémoire afin de pouvoir le manipuler. Au moment où l'on écrit le programme, on ne sait pas quelle va être la taille nécessaire pour ce tableau, il est donc difficile de le déclarer comme nous l'avons fait jusqu'ici. Une solution consiste bien sûr à se donner une taille très grande quitte à n'en utiliser en fait qu'une toute petite partie, mais cette solution n'est pas bonne car elle provoque un gaspillage de mémoire qui est une ressource toujours limitée. Le langage C offre une solution à ce problème au travers des deux fonctions standard malloc() et free() déclarées dans stdlib.h. Le programme suivant montre l'utilisation de ces deux fonctions. Il demande à l'utilisateur combien il souhaite rentrer de nombres. Ensuite on lui demande de rentrer ces nombres un par un. On affiche ensuite la série de nombres entrés par l'utilisateur. #include <stdio.h> #include <stdlib.h> void main() { int i, n; int *ptr; printf(“Combien d'entiers voulez vous rentrer ? ”); scanf(“%d”,&n); ptr = malloc(n*sizeof(int)); if (ptr == NULL) { } for (i=0; i<n; i++) { printf(“Entrez l'entier d'indice %2d: ”, i); scanf(“%d”,&ptr[i]); } printf("\nContenu du tableau: \n", ptr); for (i=0; i<n; i++) { printf(“%d ”, ptr[i]); } free(ptr); } Programme 62 Le nombre de nombres que l'utilisateur souhaite rentrer est conservé dans la variable n. Comme on ne sait pas, au moment où l'on écrit le programme, combien de nombres l'utilisateur va vouloir rentrer, on ne peut allouer de tableau de la bonne taille par une construction du genre int t[5]; Au lieu de cela on a recours à la fonction malloc (memory allocate). L'interface de cette fonction est la suivante: void *malloc(long size); Cette fonction recherche un bloc de mémoire libre de taille égale à size octets, le marque occupé afin qu'aucune autre variable ne vienne l'utiliser et renvoie l'adresse de début de ce bloc sous forme d'un pointeur générique. Dans notre cas nous avons besoin d'un bloc pouvant contenir n ints pour stocker les n nombres que va rentrer l'utilisateur. L'opérateur sizeof(int) retourne le nombre d'octets occupés par une variable de type int. Donc pour stocker n octets il faut n*sizeof(int) octets en mémoire. Si la fonction malloc ne parvient pas à réserver un bloc de mémoire de la taille demandée, elle renvoie NULL (c'est-à-dire la valeur numérique zéro) en lieu et place de l'adresse de début de bloc. On teste donc si ptr vaut NULL, on signale une erreur dans ce cas et on interrompt le programme au moyen de la fonction exit(). Si l'appel à malloc se déroule correctement, l'adresse de début d'un bloc réservé est renvoyée et donc placée dans ptr. Pour fixer les idées supposons que l'utilisateur ait indiqué qu'il souhaitait rentre 5 nombres. A l'issue de l'appel à la fonction malloc la mémoire pourrait se retrouver dans l'état suivant: Grâce à cette figure on s'aperçoit que l'on se trouve dans une situation tout à fait analogue à celle de la figure 13 où le pointeur ip permettait d'accéder aux éléments du tableau t. En fait on peut accéder à la zone de mémoire réservée par malloc comme à n'importe quel tableau d'entiers que nous avons rencontré jusqu'ici. Ainsi l'expression ptr[0] désigne l'entier contenu à l'adresse 1024, ptr[1] celui contenu à l'adresse 1028 et ainsi de suite jusqu'à l'indice n-1. Ainsi, à l'intérieur de la première boucle, l'expression scanf(“%d”,&ptr[i]); permet de stocker les valeurs entrées par l'utilisateur l'une après l'autre dans la zone réservée et l'expression printf(“%d ”, ptr[i]); de la deuxième boucle permet de les afficher. Par équivalence de syntaxe on aurait également pu utiliser l'expression ptr+i au lieu de &ptr[i] et *(ptr+i) au lieu de ptr[i] (section 8.4). La fonction free, quant à elle, libère une zone de mémoire allouée par la fonction malloc. Son interface est: void free(void *ptr); La mémoire utilisable par un programme est limitée, tout bloc alloué par malloc doit donc être libéré dès que possible afin de pouvoir être réutilisé plus tard par un nouvel appel à malloc. Un programme qui alloue répétitivement de la mémoire au moyen de malloc sans jamais la libérer avec free finit vite par épuiser la mémoire disponible. Dans cette situation, malloc ne peut plus faire de réservation et le programme a de fortes chances de planter. On voit que pour appeler free, il faut indiquer le début de la zone de mémoire à libérer au moyen d'un pointeur, il faut prendre garde à ne pas perdre la référence à des zones de mémoire. Dans l’exemple suivant, la zone réservée par le deuxième malloc ne pourra évidemment plus être retrouvée, car l’affectation à #include <stdio.h> #include <stdlib.h> void main() { int *ptr1, *ptr2; ptr1 = malloc(sizeof(int)); ptr2 = malloc(sizeof(int)); *ptr1 = 845; ptr2 = ptr1; printf("%d\n",*ptr2); free(ptr1); free(ptr2); /* !!! ERREUR !!! */ } Programme 63 deux fois la même zone mémoire, ce qui n'est pas autorisé et peut, dans certains cas entraîner un plantage. Les variables “normales” sont appelées statiques alors que celles qui sont pointées et allouées par malloc lors de l'exécution du programme sont appelées dynamiques. Le pointeur lui-même est donc en fait statique. Une variable dynamique est donc représentée par un symbole précédé de *. 9  Lecture ou écriture de fichiers sur le disque Le langage C permet de sauvegarder des données dans un ou plusieurs fichiers sur disque après que l’exécution d’un programme soit terminée. On distingue fichiers texte et fichiers binaires. Les fichiers texte sont les plus courants et leur avantage essentiel est qu’il est possible de les utiliser d’une machine à l’autre, même si les machines ont des microprocesseurs et des systèmes d'exploitation différents. Un autre avantage est qu’ils peuvent être lus et vérifiés par un observateur humain. Les fichiers binaires permettent quant à eux de stocker des valeurs de variables sans devoir les transformer en chaînes de caractères. Toutefois on ne peut généralement pas les utiliser tels quels sur une autre plate-forme que celle sur laquelle ils ont été écrits, on doit pour cela prévoir des traitements tout à fait particuliers. De plus ils sont illisibles pour un observateur humain. 9.1  Fichiers texte Les programmes qu’on a préparés, modifiés et exécutés jusqu’ici se trouvent sur le disque de l’ordinateur. Ce sont des fichiers. Il est évidemment possible de lire le contenu d’un fichier directement d’un programme et d’y déposer des valeurs pour les garder, même lorsqu’on éteint l’ordinateur. Chapitre 9: Lecture ou écriture de fichiers sur le disque Les instructions de lecture et d’écriture pour les fichiers sont nombreuses et seront résumées dans la section suivante. Nous verrons ici, simplement, les deux instructions de base permettant de lire ou d’écrire dans un fichier. Il s’agit de fprintf et de fscanf. Elles sont très semblables à printf et scanf. /* écriture sur l’écran */ printf("Bonjour\n"); /* écriture sur le fichier lié à la variable monFichier */ fprintf(monFichier, "Bonjour\n"); /* lecture depuis le fichier lié à la variable monFichier */ fscanf(monFichier, ”%d”, &i); Programme 64 On voit apparaître dans la ligne d’écriture sur fichier, un paramètre supplémentaire monFichier. Ce paramètre est ce que l'on appelle un descripteur de fichier. Il permet d'indiquer à la commande fprintf dans quel fichier elle doit écrire, en effet un programme peut tout à fait écrire dans plusieurs fichiers différents. La variable monFichier doit au préalable avoir eté déclarée: FILE *monFichier; puis le fichier doit être ouvert grâce à la commande fopen dont la syntaxe est: monFichier = fopen("","mode"); où est le nom du fichier sur le disque et la chaîne mode indique ce qu’on veut faire avec le fichier. Les valeurs autorisées sont: “r” ouvre un fichier texte en lecture (on ne pourra pas écrire dedans) “w” ouvre un fichier texte en écriture. Si le fichier existait, son contenu est écrasé “a” “r+” ouvre un fichier texte en mode mise à jour (lecture et écriture) “w+” ouvre un fichier texte en mode mise à jour. Si le fichier existait, son contenu est écrasé “a+” ouvre un fichier texte en mode mise à jour en se plaçant à la fin du fichier s'il existait déjà La commande fopen renvoie un descripteur de fichier (type FILE *) si le fichier a été correctement ouvert ou bien NULL sinon. Deux autres instructions sont très utilisées en C pour lire et écrire dans les fichiers texte, il s’agit de fgets et de fputs qui servent respectivement à lire une chaîne de caractère depuis un fichier et à écrire une chaîne de caractère dans un fichier. Leurs interfaces sont: char *fgets(char *s, int n, FILE *file); int fputs(char *s, FILE *file); Nous avons déjà rencontré la fonction fgets pour lire des chaînes de caractères au clavier. Pour cela on utilisait stdin comme paramètre file. stdin est en fait un descripteur de fichier standard ouvert automatiquement par le système au début de l'exécution du programme (inutile donc d'utiliser fopen dans ce cas) et qui désigne le clavier. En effet pour Unix, le système d'exploitation sur lequel le langage C a été développé, tout ou à peu près tout est considéré comme un fichier, y compris le clavier et le terminal d'affichage. fgets lit jusqu’au caractère de fin de ligne (inclus) ou au maximum n-1 caractères et les place dans s en ajoutant le zéro final. fgets renvoie un pointeur vers la chaîne lue (donc s) ou bien NULL si aucun caractère n'a pu être lu. fscanf(file,“%s”,s) joue à peu près le même rôle si ce n'est que cette fonction s'arrête au premier espace rencontré s'il en apparaît un avant le caractère de fin de ligne. fputs écrit la chaîne contenue dans le tableau de caractères s dans le fichier désigné par file. Chapitre 9: Lecture ou écriture de fichiers sur le disque Lors d’une lecture, pour savoir si l’on est à la fin du fichier ou s’il y a encore des données à lire, on peut utiliser la fonction feof(monFichier), ce qui signifie end of file. Cette fonction retourne une valeur non nulle (donc vraie d'un point de vue logique) lorsqu’on a lu tout le fichier. Le programme ci-dessous montre comment lire un fichier ligne par ligne, comment afficher chaque ligne sur l’écran, puis comment fermer le fichier: #include <stdio.h> #include <stdlib.h> void main() { FILE *fichier; char nom_fichier[128], chaine[128]; printf("Donnez le nom du fichier ? "); scanf("%127s",nom_fichier); if ((fichier = fopen(nom_fichier,"r")) == NULL) { printf("Erreur : Ouverture du fichier impossible\n"); exit(1); } /* On a pu ouvrir le fichier */ while (!feof(fichier)) { if (fgets(chaine, 128, fichier)!=NULL); printf("%s", chaine); } } Programme 65 Exercice 74.Dans chaque ligne du fichier , on a déposé 4 nombres, correspondant aux coordonnées (x1 y1) et (x2 y2) des extrémités de vecteurs. On demande de lire ces nombres (fscanf(fichier,"%d %d %d %d",&x1,&y1,&x2,&y2)) et d’afficher sur l’écran graphique les vecteurs correspondants, partant de (x1, y1) et aboutissant à (x2, y2). Ces nombres sont compatibles avec l’échelle de l’écran graphique. Exercice 75.Faire un programme qui copie un fichier sur un autre. Ce programme est pratiquement identique au programme 65. Il faut juste ouvrir un deuxième fichier pour y écrire dedans et fermer les deux fichiers à la fin. Faites ce programme avec fgets et fputs. Exercice 76.Réaliser un programme qui compte le nombre de lignes et le nombre de caractères dans un fichier. Conseil: utiliser l’instruction strlen(*char). FILE *entree ; /* fichier d’entrée */ FILE *sortie ; /* fichier de sortie */ x : integer ; char chaine[128]; fichier = fopen("","r"); /* ouvrir en lecture le fichier */ fichier = fopen("","w"); /* ouvrir en écriture le fichier */ fscanf(entree,"%d\n",&x); /* lire dans entree la valeur de la variable x */ fgets(chaine,128,entree); /* lit une ligne de max. 128 caractères */ fgetc(char,entree); /* Lit un carctère dans le fichier entree */ fprintf (sortie, "Hello\n") ; fprintf (sortie, "Bonjour %d\n",x) ; /* écrire dans le fichier sortie la chaîne de caractère "Bonjour" et la valeur de x */ fputs("Bonjour Monsieur",sortie); /*écrire dans sortie "Bonjour Monsieur" */ fputs(chaine,sortie); /* écrire dans sortie la valeur de la chaine chaine */ fputc(char,sortie); /* Met un caractère dans le fichier sortie */ fclose (entree) ; fclose (sortie) ; Programme 66 10  Structurer les données Ce chapitre introduit le dernier concept fondamental du C, les structures ou enregistrements. Les structures permettent de grouper plusieurs variables et de leur donner un nom, au même titre qu’une fonction permet de grouper plusieurs instructions et de leur donner un nom. Les pointeurs permettent de créer des relations privilégiées entre variables et de créer des variables complexes dont la taille varie en cours d’exécution du programme. Par exemple, les pointeurs permettent de rajouter un élément au milieu d’un ensemble sans avoir à en recopier tous les éléments, ou créer une structure d’arbre (généalogique par exemple). typedef unsigned int uint; typedef float VecteurT[4]; La première instruction fait du symbole uint un équivalent de unsigned int, la deuxième définit le symbole VecteurT comme étant un type représentant un tableau de 4 réels. Ces nouveaux types peuvent ensuite être utilisés pour déclarer des variables exactement comme les types primitifs du langage: uint i; VecteurT x, y, z; L'instruction typedef est utilisée tout particulièrement avec les structures présentées dans la section suivante. 10.2  Structures Il arrive très souvent en programmation qu’une variable ne se décrive pas seulement par un entier, un réel ou une autre grandeur simple mais que sa description demande plusieurs informations de type différents. Par exemple, une variable décrivant une personne contient par exemple, son prénom et son nom (chaînes de caractère), sa date de naissance (3 entiers), le nom des parents, le numéro AVS, la taille, la couleur des yeux, etc Dans ce cas il devient nécessaire d'utiliser un mécanisme permettant de regrouper de façon cohérente un certain nombre de variables, c'est ce qu'offre le concept de structure. Dans les lignes suivantes on définit un type qui contient trois numéros et un nom. typedef struct person { char nom[32]; char prenom[32]; int jour, mois, annee; int index } PersonT; Programme 67 Cette structure, définit les champs jour, mois, annee de type int, les champs nom, prenom de type tableau de caractères, et le champ index, de type int. Il est tout à fait possible de définir des champs d’une structure qui soient eux-mêmes des structures et donc de placer des structures à l’intérieur de structures, à l’intérieur de structures, etc. La syntaxe employée ici permet de définir un nouveau type de variable appelé PersonT au moyen de l'instruction typedef. Grâce à cette définition de type on peut déclarer des variables du type structure avec la syntaxe suivante: PersonT luke; struct person luke; La définition du programme 67 peut se lire de la façon suivante: “une personne est caractérisée par son nom, son prénom, sa date de naissance, et un indice (par exemple, le numéro AVS)”. Si l’on a déclaré une variable luke du type PersonT tel qu’il est défini ci-dessus, on peut désigner ses champs de la façon suivante en utilisant l'opérateur . : PersonT luke; = 7; strcpy(,"Skywalker"); strcpy(luke.prenom,"Luke"); Programme 68 Attention, il est impératif de déclarer une variable du nouveau type avant toute utilisation, la définition du type en elle même ne permet pas d’affecter des valeurs. Pour le champ mois, l’affectation est semblable à celle d’une variable normale. Pour le champ nom l’affectation est aussi semblable mais rappelons que pour une chaîne de caractères, on doit utiliser l’instruction strcpy(tableau_char, chaine_a_copier);. Les instructions du programme 68 peuvent se lire: le nom de la personne luke est ‘Skywalker’. Le mois de naissance de luke est le 7ème mois, etc Il est possible également de définir un tableau de personnes, ce qui est fait à la ligne suivante: PersonT famille[4]; Dans ce cas, les champs des personnes se désignent de la façon suivante: strcpy(famille[3].prenom, "Isabelle"); famille[2].annee = 1992; Ces identificateurs sont formés d’une indication d’élément de tableau suivi de l’indication d’un champ: .prenom, .mois, etc Ces lignes peuvent se lire: le prénom de la quatrième personne de la famille est Isabelle, l’année de naissance de la troisième personne de la famille est 1992. #include <stdio.h> #include <stdlib.h> typedef struct person { char nom[32]; char prenom[32]; int jour, mois, annee; int index; } PersonT; void PrintPerson(PersonT p) { printf("%s %s\n",p.nom, p.prenom); printf("jour %d mois %d annee %d\n", p.jour, p.mois, p.annee); } void main() { PersonT jules, jacques; PersonT jean = {"Tour", "Jean", 12, 4, 1958, 1}; PrintPerson(jean); } #include <stdio.h> #include <stdlib.h> typedef char StringT[32]; PrintPerson(char *nom, char *prenom, int jour, int mois, int annee) { printf("%s %s\n",nom,prenom); printf("%d %d %d\n",jour, mois, annee); } void main() { StringT nom_de_jules, prenom_de_jules; int jour_de_jules, mois_de_jules; int annee_de_jules; StringT nom_de_jacques, prenom_de_jacques; int jour_de_jacques, mois_de_jacques; int annee_de_jacques; StringT nom_de_jean = “Tour”, prenom_de_jean = “Jean”; int jour_de_jean=12, mois_de_jean = 4, annee_de_jean = 1958; PrintPerson(nom_de_jean,prenom_de_jean, jour_de_jean, mois_de_jean, annee_de_jean); } Programme 69 Il faut encore noter qu’on peut facilement affecter une structure entière à une autre comme on le fait avec des variables: void main() { PersonT jules, jacques, jean; jules = jean; } Programme 70 Par contre on ne peut pas comparer deux structures (il faut comparer champ par champ): Programme 71 Exercice 77.La liste des personnes d’une famille est contenue dans le fichier. Ecrire un programme avec une variable famille capable de stocker les informations d’au maximum 20 personnes, et copier les données du fichier dans cette variable. #define MAXSIZE 20 typedef struct PersonT { } PersonT; void main() { PersonT famille[MAXSIZE]; . } FIGURE 17: Contenu du fichier Exercice 78.Triez les membres de la famille par ordre alphabétique (voir exercice 21). Exercice 79.On se propose de modéliser un objet se déplaçant dans le plan (la fenêtre graphique) en décrivant sa position en x et en y (PosX, PosY), ainsi que sa vitesse en x et en y (SpeedX, SpeedY). Ces quatre coordonnées sont des nombres réels. La position est donnée en pixel, et la vitesse en pixel par itération du programme. A chaque itération du programme l’on ajoute la vitesse à la position, coordonnée par coordonnée, et l’on calcule la nouvelle vitesse de la façon suivante: Dist = sqrt (PosX2+PosY2), ?SpeedX= -k.PosX/(Dist3), ?SpeedY= -k.PosX/(Dist3). Exécutez 1000 itérations du programme, n utilisant comme valeurs initiales PosX = 150.0, PoxY = 0.0, SpeedX = 0.0, et SpeedY = 1.0. Utilisez les routines graphiques pour afficher l’objet à l’écran dans chacune de ses positions. La valeur à utiliser pour la constante k est 200. Le mouvement de l’objet vous rappelle-t-il quelque chose? Exercice 80.Pour vous faciliter l’exercice suivant, plutôt que de déclarer 4 variables PoxX, PosY, SpeedX, SpeedY, déclarez une structure ObjectT avec 4 champs réels portant les noms PoxX, PosY, SpeedX, SpeedY, et une seule variable de type ObjectT. Ecrivez une procédure qui calcule la nouvelle position à partir de l’ancienne, et une procédure qui affiche la particule. Pensez aussi à recentrer l’origine lors de l’affichage. Le mouvement de l’objet est limité à l’intervalle (-200,200), tant en x qu’en y. Exercice 81.Modifiez l’exercice 79 de façon à ce qu’il y ait trois objets, avec les valeurs initiales suivantes. Obj[1].PosX = 50.0 ; Obj[1].PoxY = 0.0 ; Obj[1].SpeedX = 0.0 ; Obj[1].SpeedY = 1.7 ; Obj[2].PosX = 100.0 ; Obj[2].PoxY = 0.0 ; Obj[2].SpeedX = 0.0 ; Obj[2].SpeedY = 1.2 ; Obj[3].PosX = 150.0 ; Obj[3].PoxY = 0.0 ; Obj[3].SpeedX = 0.0 ; Obj[3].SpeedY = 1.0 ; #define MAXSIZE 200 typedef struct line { int fromX, fromY ; int toX, toY; } LineT; LineT lines[MAXSIZE]; Programme 73 10.3  Structures, pointeurs de structures et fonctions On peut tout à fait utiliser une structure comme argument ou valeur de retour d'une fonction. Dans ce cas, le passage s'effectue comme toujours par valeur, donc en copiant temporairement la structure, champ par champ. Ainsi dans le programme 74, lors de l'appel Translate(p1, delta), les valeurs (3,5) et (1,1) de p1 et delta sont copiées temporairement dans p et deplacement. Une fois le calcul effectué dans la variable tem- #include <stdio.h> typedef struct point { int x; int y; } PointT; PointT Translate(PointT p, PointT deplacement) { PointT temp; temp.x = p.x + deplacement.x; temp.y = p.y + deplacement.y; return temp; } main() { PointT p1 = {3, 5}; PointT delta = {1, 1}; PointT p2; p2 = Translate(p1, delta); printf(“%d %d\n”,p2.x, p2.y); } Programme 74 poraire temp, sa valeur est retournée de la fonction et donc copiée dans p2 grâce à l'affectation p2=Translate( ). Si les structures sont de très grande taille, le passage par valeur et donc la copie qu'il implique peut devenir particulièrement pénalisant. C'est pourquoi le passage de variables de type structure est plutôt rare, on lui préfère généralement le passage par pointeur. Le programme suivant est similaire au précédent mais utilise des pointeurs: #include <stdio.h> typedef struct point { int x; int y; } PointT; void Translate(PointT *p, PointT *deplacement) { (*p).x += (*deplacement).x; (*p).y += (*deplacement).y; } main() { PointT p1 = {3, 5}; PointT delta = {1, 1}; Translate(&p1, &delta); printf(“%d %d\n”,p1.x, p1.y); } Remarquez la notation utilisée pour accéder aux membres de la structure. Pour mémoire, si ip est un pointeur d'entier (int *ip), alors la notation *ip désigne l'entier pointé par ip, c'est-à-dire l'entier se trouvant à l'emplacement mémoire dont l'adresse est la valeur de ip. Il en va de même pour les structures, si ptP est un pointeur sur une structure de type point (PointP *ptP), alors la notation *ptP désigne la structure contenue dans l'emplacement mémoire commençant à l'adresse indiquée par ptP. On peut donc utiliser l'opérateur “.” pour accéder aux différents champs de cette structure, toutefois comme la priorité de cet opérateur est plus forte que celle de “*”, on est obligé d'entourer *ptP de parenthèses: (*ptP).x. Mais les pointeurs de structure sont tellement fréquents que le C dispose d'un opérateur spécifique pour simplifier l'écriture d'une telle expression, l'opérateur “->”. Cet opérateur nécessite un pointeur de structure à sa gauche et un identificateur de champ à sa droite. Ainsi l'expression (*ptP).x est en tout point identique à ptP->x. Un programmeur C exercé écrirait donc la fonction Translate du programme 75, comme suit: void Translate(PointT *p, PointT *deplacement) { p->x += deplacement->x; p->y += deplacement->y; } 10.4  Utilisation des pointeurs pour améliorer les programmes Nous allons reprendre l’exercice 78 (tri de la famille) et l’améliorer de deux façons différentes: limiter la taille mémoire utilisée, et accélérer le tri. 10.5  Réduction de la mémoire occupée par un programme La première difficulté liée à l’exercice 77 est son usage excessif de mémoire. Si l’on considère une valeur MAX_SIZE=10000, et la taille de la structure PersonT = 100 octets, la taille mémoire requise pour stocker la variable famille est 106 octets. Ceci même si le fichier ne contient qu’une seule personne. typedef struct personT { } PersonT; void main() { PersonT *famille[MAXSIZE]; } Programme 76 La taille d’un pointeur est en général 4 octets (pour les machines dites 32 bits, et 8 octets pour les machines dites 64 bits). De nouveau, si MAXSIZE=10000, la taille occupée par le programme en mémoire est 4.104 + 100*NbrePersonneDsFichier. Dans le cas où le fichier contient six personnes, le programme 76 occupe 40600 octets contre 1040000 octets pour le programme 72. C’est un facteur 25 d’économie. Exercice 83.Réécrivez l’exercice 77 (lecture du fichier ) en utilisant les déclarations du programme 76. La figure 18 montre graphiquement l’utilisation de la mémoire dans les deux situations: Johnson Johnson Johnson Johnson Heyden Heyden Albert Catherine Renee Paul Bernard Bruno 7 14 21 5 30 12 6 10 7 2 5 9 1897 1898 1924 1926 1920 1955 Programme 72 FIGURE 18: Deux organisations mémoire pour les programmes 72 et 76 Exercice 84.Réécrivez l’exercice 78 (tri des membres de la famille) en utilisant les déclarations du programme 76. Exercice 85.Réécrivez l’exercice 82 (lire les points dans un fichier) en utilisant les déclarations suivantes (tableau de pointeurs de ligne, plutôt que tableau de lignes): #define MAXSIZE 20 typedef struct lineT { int fromX, fromY; int toX, toY; } LineT; void main() { LineT *Lines[MAXSIZE]; } Programme 77 /* Tri1 */ #define SIZE typedef struct person { } PersonT; void main() { PersonT famille[SIZE]; PersonT tmp; for(i = 0; i < SIZE-1; i++) for (j = i+1; j < SIZE; j++) if (Older(famille[i], famille[j])) { tmp = famille[i]; famille[i] = famille[j]; famille[j] = tmp; } } Programme 78 Grâce aux pointeurs, on peut améliorer sensiblement ce programme. Dans le programme 79, la variable famille est déclarée comme tableau de pointeurs, et dans la routine de tri, on échange non plus des structures, mais des pointeurs. Au bout du compte, le résultat est le même, mais on a copié 25 fois moins de données (une structure PersonT représente 100 octets, tandis qu’un pointeur n’en représente que 4). /* Tri2 */ #define SIZE typedef struct person { } PersonT; void main() { PersonT *famille[SIZE]; PersonT *tmp; for(i = 0; i < SIZE-1; i++) for (j = i+1; j < SIZE; j++) if (Older(famille[i], famille[j])) { tmp = famille[i]; famille[i] = famille[j]; famille[j] = tmp; } } Programme 79 Observez le programme 80. Pouvez-vous dire combien d’octets sont copiés dans le pire des cas de tri d’une famille de 1000 personnes? Ce programme illustre la différence qu’il y a entre la copie de pointeurs (programme 79, famille[i] = famille[j]) et la copie de structures (programme 80, *famille[i] = *famille[j]). /* Tri3 */ #define SIZE typedef struct person { } PersonT; void main() { PersonT *famille[SIZE]; PersonT *tmp; for(i = 0; i < SIZE-1; i++) for (j = i+1; j < SIZE; j++) if (Older(famille[i], famille[j])) { *tmp = *famille[i]; *famille[i] = *famille[j]; *famille[j] = *tmp; } } FIGURE 19: Organisation mémoire après les programmes Tri2 et Tri3 10.7  Utilisation des pointeurs pour faire un ‘arbre généalogique’ Dans les schémas, nous avons souvent représenté jusqu'ici les pointeurs sous forme de flèches. Que ce soit cette représentation ou le nom même de pointeur, tout indique qu'un pointeur permet d'établir une relation entre deux emplacements de la mémoire, c'est-à-dire entre deux variables. Imaginons que l'on souhaite créer une relation de parenté entre les personnes d’une famille (voir exercice 77), c'est-à-dire pouvoir être capable de dire pour chaque personne, quel est son père et quelle est sa mère. Comme toutes les personnes sont caractérisées par un index unique, on pourrait établir cette relation au moyen de deux variables de type int contenues dans la structure et qui contiendraient l'index du père et l'index de la mère. Cette méthode a une limitation toutefois: il n'est facile de retrouver les informations relatives au père et à la mère que tant que l'on peut accéder facilement à un enregistrement à partir de son numéro d'index. C'était le cas dans les exemple précédents puisque l'index d'une personne correspondait à un indice dans le tableau des structures. typedef struct person {   char nom[32];   char prenom[32];   int jour, mois, annee;   int index;   struct person *pere; struct person *mere; } PersonT; Programme 81 Dans le fichier , dont le contenu est montré dans la Figure 20, les relations de parenté sont indiquées: Renee et Paul ont pour parents Albert et Catherine. Bruno a pour parents Bernard et Renee. Johnson Albert 7 6 1897    inconnu inconnu inconnu inconnu Johnson Catherine 14 10 1898    inconnu inconnu inconnu inconnu Johnson Renee 21 7 1924 Johnson Albert Johnson Catherine Johnson Paul 21 10 1926 Johnson Albert Johnson Catherine Heyden Bernard 30 10 1920 inconnu inconnu inconnu inconnu Heyden Bruno 12 9 1955 Heyden Bernard Johnson Renee FIGURE 20: Contenu du fichier Exercice 86.On vous donne un fichier, qui contient pour chacun des membres de la famille le nom du père et de la mère s’ils sont connus, ‘inconnu’ autrement. Modifiez le programme 77 de façon à ce qu’il lise les informations contenues dans le fichieret initialise tous les champs de la structure PersonT. Si le père ou la mère sont inconnus, les champs pere et mere doivent être initialisés à NULL. Utilisez la fonction strcmp(chaîne1, chaîne2) qui renvoie 0 si les deux chaînes sont identiques. Cette fonction est déclarée dans le fichier string.h Exercice 87.Reprenez l’exercice 82 (lire et afficher des lignes), avec la structure suivante. #define MAXSIZE 20 typedef struct line {   int fromX, fromY;   int toX, toY;   int index;   struct line *nextP; } LineT; LineT *lines[MAXSIZE]; Exercice 89.Revenons à l’exercice 86. Plutôt que de “matérialiser” les relations père/mère, on souhaite matérialiser la relation enfants, en ajoutant dans chaque structure un tableau de pointeurs vers des personnes, de la façon suivante: typedef struct person {   char nom[32];   char prenom[32];   int jour, mois, annee;   int index;   struct person *enfants[4]; } PersonT; Programme 83 Ecrivez un programme qui lit le fichier, et initialise tous ses champs de façon à pouvoir retrouver directement tous les enfants de chaque personne. 10.8  Utilisation des pointeurs dans les listes chaînées Il subsiste encore trois difficultés dans la solution proposée à l’exercice 83: •    on reste limité dans la taille de l’arbre généalogique que le programme peut traiter car le tableau stockant les structures de personnes ou les pointeurs vers ces structures est de taille limitée fixée au moment où l'on écrit le programme; •    il est difficile de rajouter une personne au milieu du tableau de personnes (pour faire cela, il faut décaler toutes les personnes qui “suivent”, ce qui occasionne pas mal de copies de structures ou de pointeurs). Les structures se retrouvent ainsi organisées selon ce qu'on appelle une liste chaînée simple (dans le cas où chaque structure n'a qu'un pointeur vers la suivante) ou doublement chaînée (dans le cas où chaque structure pointe vers la précédente et la suivante). Pour illustrer cela, voici un programme (programme 84) qui lit le fichier , et insère chacun des membres dans une telle liste chaînée: #include <stdio.h> #include <stdlib.h> typedef struct person {   char nom[32], prenom[32];   int jour, mois, annee, index;   struct person *next; } PersonT; main() { PersonT *teteDeListe, *person; FILE *fichier; int i; char temp[5]; teteDeListe = NULL; if ((fichier = fopen("","r")) == NULL) { printf("Erreur \n"); exit(1); } i = 1; while (!feof(fichier)) { person = (PersonT *)malloc(sizeof(PersonT)); person->index = i; fgets(person->nom, 32, fichier); fgets(person->prenom, 32, fichier); fscanf(fichier,"%d", &person->jour); fscanf(fichier,"%d", &person->mois); fscanf(fichier,"%d", &person->annee); fgets(temp, 5, fichier); person->next = teteDeListe; teteDeListe = person; i++; }   /* Affichage des données lues */   person = teteDeListe;   while (person != NULL) { printf("%s",person->prenom); printf("%s\n",person->nom); person = person->next; } } Le programme 84 lit dans le fichier les personnes une par une (première boucle while). On alloue au fur et à mesure l’espace mémoire nécessaire pour contenir les informations relatives à chacune des personnes (person = malloc(sizeof(PersonT)), initialise les informations concernant la personne à partir des données du fichiers (les instructions fgets et fscanf dans la boucle), et insère la personne dans la liste chaînée dont l'adresse de début est contenue dans teteDeListe. Etudions les deux instructions d’insertion dans la liste chaînée: person->next = tetedeListe ; teteDeListe = person ; Pour des questions d'efficacité, chaque nouvelle personne est insérée au début de la liste. Pour la nouvelle personne ajoutée, la personne suivante est celle se trouvant actuellement en tête de liste. C'est le sens de la première affectation: person->next = tetedeListe; Afin de mieux comprendre, on peut représenter graphiquement, cette opération: FIGURE 21: Effet de l’affectation person->next = tetedeListe; A ce stade, la personne en cours d'ajout (Renée Johnson) est en quelque sorte déjà insérée dans la liste puisqu'à partir d'elle on peut atteindre la personne suivante (Catherine Johnson) et à partir de là toutes les autres personnes déjà présentes dans la liste. Renée Johnson est de fait devenue la nouvelle tête de liste. La deuxième affectation met alors à jour le pointeur teteDeListe afin qu'il pointe vers cette nouvelle tête de liste: teteDeListe = person; FIGURE 22: Effet de l’affectation teteDeListe = person; Pour résumer, la figure 23 représente l'ajout des trois premières personnes dans la liste chaînée (ainsi que son état final). Pourquoi utiliser des listes, alors que les tableaux fonctionnaient à peu près? Avec les listes chaînées, il n’y a pas moyen d’accéder directement aux personnes de la famille en utilisant les indices du tableau. Par contre, on peut agrandir “sans limite” le nombre de personnes dans la famille. Tout dépend de la situation dans laquelle on se trouve. Il y a beaucoup de situations où l'on ne peut pas se permettre d’allouer un tableau de taille fixe qui soit suffisamment grand pour traiter le pire des cas. A ce moment-là, la seule solution est la liste chaînée. Exercice 90.Modifier le programme 84 (programme ~gennart/exercices-corriges/program84.c) sans ajouter de variables de façon à ce qu’il ajoute les personnes au bout de la liste chaînée. Montrer que ce programme est beaucoup plus lent que le programme 84 (par exemple en insérant 1000, 2000 et 4000 personnes dans la liste). Exercice 91.Modifier l’exercice précédent en ajoutant une variable PersonT *finDeListe qui pointe toujours vers la dernière personne de la liste. Ceci permet d’insérer une nouvelle personne à la fin de la liste chaînée de façon beaucoup plus rapide. FIGURE 24: Suppression d'un élément d'une liste simplement chaînée variables prev et maxPrev. Par contre lorsque l'élément à enlever est en tête de liste, il suffit de changer le pointeur de tête de liste pour le faire pointer vers l'élément suivant. Le programme 86 montre un programme qui traite une liste circulaire doublement chaînée de personnes. Une liste circulaire est une liste où l'élément suivant du dernier est le premier (figure 25). Un algorithme de parcours d'une telle liste qui se contenterait de passer d'un élément au suivant sans autre forme de précaution n'aurait pas de fin. Une astuce pour éviter ce genre de problème ainsi que d'avoir à traiter l'insertion du premier élément et la suppression du dernier comme des cas particuliers, consiste à faire en sorte que la liste contienne toujours un élément initial vide, appelé sentinelle. Nous laissons au lecteur le soin de s’armer d’un crayon, d’un papier et d’un peu de patience afin de faire les schémas nécessaires pour étudier et comprendre ces programmes. #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct person {  char nom[32], prenom[32]; int jour, mois, annee;  struct person *next; } PersonT; PersonT *teteDeListe; void LitAdresses(char *nom_fichier) {  FILE *fichier;  PersonT *person;  char temp[5];     teteDeListe = NULL;     if ((fichier = fopen(nom_fichier,"r")) == NULL) {      printf("Erreur \n");     exit(1);    } while (!feof(fichier)) {      person = malloc(sizeof(PersonT));      fgets(person->nom, 32, fichier);      fgets(person->prenom, 32, fichier); fscanf(fichier,"%d", &person->jour); fscanf(fichier,"%d", &person->mois);    fscanf(fichier,"%d", &person->annee);   /* absorbe le retour chariot sur la ligne courante */ }   fclose(fichier); } void AfficheAdresses() {  PersonT *person; for (person=teteDeListe; person != NULL; person=person->next) {      printf("%s",person->nom); printf("%s",person->prenom); printf("%d\n",person->jour); printf("%d\n",person->mois); printf("%d\n",person->annee);   printf("\n"); } } void TrieAdresses() {  PersonT *nouvelleTete, *person, *prev, *max, *maxPrev;  int i;    nouvelleTete = NULL;     while (teteDeListe) { maxPrev = NULL; prev = max = teteDeListe; printf("Step %d\n", i);      AfficheAdresses();      for (person=teteDeListe->next; person!=NULL; person=person->next) { if ((strcmp(person->nom, max->nom) > 0) ||  (strcmp(person->nom, max->nom)==0 && strcmp(person->prenom, max->prenom) > 0)) { maxPrev = prev;      max = person; }    prev = person;  } /* Si le max n’etait pas en tete de    liste, on l’enleve de la liste en         raccrochant son precendent a son    suivant. Sinon on l’enleve en          faisant avancer la tete de liste d’une personne */ if (maxPrev) maxPrev->next = max->next; else teteDeListe = teteDeListe->next; /* On insere le max en tete de la nouvelle liste */ max->next = nouvelleTete;      nouvelleTete = max; i++; } teteDeListe = nouvelleTete; } void main() {      LitAdresses(""); TrieAdresses();       printf("Resultat\n");      AfficheAdresses(); } Programme 85 #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct person {  char nom[32], prenom[32]; int jour, mois, annee;  struct person *next, *prev; } PersonT; PersonT *teteDeListe; PersonT *CreeListe() { PersonT *nouvelleListe; } void AjoutePersonne(PersonT *listPerson, PersonT *newPerson) { newPerson->next = listPerson; newPerson->prev = listPerson->prev; listPerson->prev->next = newPerson; listPerson->prev = newPerson; } void EnlevePersonne(PersonT *person) { person->prev->next = person->next; person->next->prev = person->prev; } void LitAdresses(char *nom_fichier) {  FILE *fichier;  PersonT *person;  char temp[5];    teteDeListe = CreeListe();     if ((fichier = fopen(nom_fichier,"r")) == NULL) { printf("Erreur \n");      exit(1); }   while (!feof(fichier)) {      person = malloc(sizeof(PersonT));    fgets(person->nom, 32, fichier); fgets(person->prenom, 32, fichier);   fscanf(fichier,"%d", &person->jour);  fscanf(fichier,"%d", &person->mois);  fscanf(fichier,"%d", &person->annee); /* absorbe le retour chariot sur la ligne courante */ fgets(temp,5,fichier); /* absorbe la ligne vide */ fgets(temp,5,fichier); AjoutePersonne(teteDeListe, person); }   fclose(fichier); } ; void AfficheAdresses() {  PersonT *person;  for (person = teteDeListe->next;        person != teteDeListe;        person = person->next) {            printf("%s",person->nom); printf("%s",person->prenom); printf("%d\n",person->jour); printf("%d\n",person->mois);      printf("%d\n",person->annee); printf("\n"); } } void TrieAdresses() {  PersonT *nouvelleTete, *person, *prev, *min, *maxPrev;  int i;    nouvelleTete = CreeListe();     while (teteDeListe->next!=teteDeListe) { printf("Step %d\n", i); AfficheAdresses();      min = teteDeListe->next; for (person=min->next; person!=teteDeListe; person=person->next) { if ((strcmp(person->nom, min->nom) < 0) || (strcmp(person->nom,  min->nom)==0 && strcmp(person->prenom, min->prenom) < 0)) { }    } EnlevePersonne(min); AjoutePersonne(nouvelleTete, min); i++; } free(teteDeListe); teteDeListe = nouvelleTete; } main() {  LitAdresses(""); TrieAdresses();   printf("Resultat\n");  AfficheAdresses();   } Programme 86 FIGURE 25: Liste circulaire doublement chaînée Exercice 92.Modifier le programme 86 pour que la routine qui lise les noms introduise immédiatement les personnes dans l’ordre alphabétique, au fur et à mesure que les noms sont lus dans le fichier. Exercice 93.Arbre. A préparer. Exercice 94.Table associative. A préparer. Exercice 95.Graphe acyclique dirigé. A préparer. 10.9  Discussion de ce chapitre Dans ce chapitre, vous avons envisagé trois façons de résoudre le même problème: tableau de structures, tableau de pointeurs vers des structures, listes. Quelle solution faut-il choisir ? Cela dépend du problème. Les tableaux de structures sont faciles à utiliser, et l’accès à chacun des éléments est immédiat. La taille maximale est fixe ou variable. On ne peut cependant pas rajouter d’éléments au milieu du tableau sans copie de structures, et le mouvement d’objet demande des copies. Les tableaux de pointeurs sont un peu plus délicats à utiliser. L’accès à chacun des éléments reste immédiat. La taille maximale est fixe ou variable. Rajouter un élément au milieu du tableau ou en déplacer un demande seulement des copies de pointeurs. Les listes demandent pas mal de travail en C. On perd l’accès immédiat aux éléments de la liste (il faut suivre la liste pour trouver l’élément que l’on cherche). L’avantage est que la longueur de la liste n’est limitée que par la mémoire de la machine, et qu’on peut ajouter très rapidement un élément au milieu de la liste. Une dernière solution est bien sûr d’utiliser des tableaux de structures dont on va modifier la taille au fur et à mesure des besoins dans le programme mais cette façon de procéder est peu utilisée car elle est plus lourde que l’utilisation des listes chaînées. Chapitre 11: Les constructions avancées en C 11  Les constructions avancées en C 11.1  Les fonctions récursives Une caractéristique très pratique du langage C est que les fonctions peuvent s’appeler elle-mêmes. Cela s’appelle la récursion. Ceci permet d’écrire des programmes très élégants (même s’ils ne sont pas toujours les plus rapides). Considérons par exemple la factorielle qui peut être définie de la façon suivante: 1! = 1, x! = x.(x-1)! (Factorielle de 1 = 1, et factorielle de x égale x fois factorielle de x moins 1). On peut écrire le programme de la façon suivante: #include <stdio.h> int fact (int x) { printf (“Computing fact %d\n”, x) ; if (x == 1) return 1 ; else return x * fact (x-1) ; } main () { printf (“5! = %d\n”, fact (5)) ; } Programme 87 Exercice 96.La suite de Fibonacci commence par les nombres 1, 1. Chaque nombre suivant est la somme des deux précédents. La suite est donc 1, 1, 2, 3, 5, 8, 13, 21, Ecrivez un programme récursif qui calcule le nième nombre de Fibonacci. Exercice 97.Dans le programme de l’exercice 96, vous effectuez très certainement une double récursion (Fib(n) = Fib(n-1)+Fib(n-2), ce qui fait que vous calculez plusieurs fois chaque terme de la suite. Pouvez-vous modifier votre programme pour n’effectuer qu’une simple récursion? 11.2  Le type union Il est quelquefois nécessaire de mémoriser dans une variable des valeurs dont le type varie selon les circonstances. Ceci peut être fait grâce au type union. Un exemple tiré de The C Programming Language: typedef union uT { int ival ; float fval; char *sval; } u; Comme exemple, nous allons utiliser plus subtilement l’union u: union uT u; u.sval = “chaine de char”; printf (“l’addresse est %d“, u.ival); Programme 89 Ici, on mémorise d’abord l’adresse de “chaine de char” dans u, vu comme pointeur vers une chaîne de caractères. Ensuite, on traite u vu comme entier, ce qui imprime la vraie valeur de l’adresse mémoire de “chaine de char”. (Remarque: écrire printf (“%d“, u.sval); a le même effet) Pour l’exemple ci-dessus, on voulait voir la même valeur sous différentes formes. Dans certains cas on veut se rappeler si l’on avait mémorisé un entier ou un réel par exemple pour pouvoir les relire sous la forme dans laquelle ils avaient été mémorisés. Pour cela il faut ajouter une variable de plus qui indique le type effectivement contenu dans l’union. On affecte alors à cette variable des valeurs différentes lorsque l’on dépose différents types de valeurs dans l’union. Par exemple on peut décider qu’elle est mise à 1 lorsque l’on a mémorisé des entiers et à 2 lorsque l’on a mémorisé des réels, 3 si u contient un char *. En pratique, on ne se sert des unions que pour des problèmes extrêmement pointus donc rares. 12  Compilation séparée et programmation modulaire 12.1  Compilation séparée Dès que les programmes dépassent une certaine taille, il devient difficile de les manipuler dans un seul fichier. On va au contraire chercher à regrouper les fonctions en groupes de fonctions ayant des rapports entre elles et on va utiliser un fichier source différent pour chacun de ces groupes, ce qui permet de mieux organiser l'ensemble du code source. Fichiers d'en-tête. Observons le programme suivant: /* premier fichier : princ.c */ long carre (long x) ; main () { long y; y := carre (15); } /* second fichier : calculs.c */ long carre (long x) { return x * x; } Le programme peut alors être compilé en un programme exécutable, essai, au moyen de la commande: Chapitre 12: Compilation séparée et programmation modulaire gcc -g -o essai princ.c calculs.c 12.2  Bibliothèques de fonctions (librairies) Que se passe-t-il si l’on a plusieurs programmes qui utilisent, par exemple, les routines d’initialisation et d’affichage de matrice? On peut bien entendu faire du copier-coller à chaque fois. Cela pose cependant un problème. Que faire lorsque l'on détecte une erreur dans une des routines de calcul matriciel? Effectuer les changements dans tous les programmes où les fonctions ont été copiées serait la source de beaucoup d’autres erreurs. Pour remédier à cela, on préfère extraire les routines suffisamment générales pour être susceptibles d’être utilisées dans plusieurs programmes, et les regrouper dans des fichiers séparés. C'était par exemple, le cas des routines matricielles présentées à la section 7.3. Ces routines ont été écrites originellement dans deux fichiers matrix.c et vector.c dont un extrait est présenté dans le programme 92. /* matrix.c (extrait) */ MatrixPT CreateMatrix (unsigned int lines, unsigned int cols) {     MatrixPT m;     unsigned int i;     if ((m = (MatrixPT)malloc(sizeof(MatrixT)))==NULL) {         printf("\nERROR: Can’t allocate requested matrix (malloc error).\n");         return NULL;     } m->lines = lines;     m->cols  = cols;     if ((m->val = (double *)malloc(lines*cols*sizeof(double))) == NULL) {         printf("\nERROR: Can’t allocate requested matrix (malloc error).\n"); free(m);         return NULL;     }     for (i=0; i<lines*cols; i++)         m->val[i] = 0.0;     return m; } #include “matrix.h” dans les fichiers qui appellent des fonctions qui y sont déclarées. 12.3  Compilation, édition de liens et Makefile Si l’on observe la commande de compilation du programme 91: gcc -g -o essai princ.c calculs.c on constate que l’on recompile à chaque fois les deux fichiers princ.c et calculs.c. Sur le même modèle, la ligne de commande pour compiler un fichier testmat.c utilisant les routines matricielles définies dans vector.c et matrix.c serait: gcc -g -o testmat testmat.c vector.c matrix.c Supposons que les fichiers matrix.c et vector.c soient grands, et ne changent plus beaucoup (ils contiennent beaucoup de routines de calcul matriciel, qui fonctionnent correctement). Supposons que le fichier testmat.c soit relativement court, et qu’il change souvent (c’est le programme que l’on essaie d’écrire et il contient des fautes). Chaque fois qu’on lance la commande de compilation précédente, on recompile les trois fichiers. C’est du temps perdu, vu que les fichiers matrix.c et vector.c ne changent pas d’une fois à l’autre. Compilation et édition de liens. Pour comprendre ce qui suit, il faut savoir que ce que nous avons appelé compilation jusqu’à présent comporte en fait deux étapes: la compilation proprement dite, et l’édition de liens. La compilation proprement dite transforme un programme C en langage machine, sans se soucier des appels de procédure. L’éditeur de liens se charge seulement des appels de procédure, c’est-à-dire, il vérifie que toutes les procédures qui sont appelées ont bien été déclarées, et lie les appels de procédure à leur déclaration.                                          fichiers source                           fichiers objets                                 exécutable testmat.c vector.c matrix.c option de compilation -c qui demande au compilateur de ne pas effectuer l’édition de lien cosun12% cc -c -g vector.c cosun12%      commande de compilation proprement ditecosun12%   du fichier vector.c en un fichier object cosun12% cosun12% cc -c -g matrix.c cosun12%      commande de compilation proprement dite cosun12%    du fichier matrix.c en un fichier object cosun12% cosun12% cc -c -g testmat.c cosun12%     commande de compilation proprement ditecosun12%   du fichier testmat.c en un fichier object cosun12% cosun12% cc -g -o testmat testmat.o matrix.o vector.o cosun12%           commande d’édition de lien entre les fichiers testmat.o, matrix.o et vector.o en un fichier exécutable FIGURE 27: Les commandes de compilation La figure 27 décrit les trois commandes qui permettent de faire la compilation des trois fichiers source testmat.c, matrix.c et vector.c en fichiers objets, et la commande d’édition de lien. La première commande effectue la compilation proprement dite du fichier vector.c en un fichier objet vector.o. Le compilateur n’effectue pas l’édition de liens à cause de l’option de compilation -c. La deuxième commande transforme le fichier source matrix.c en un fichier objet matrix.o. La troisième commande fait de même Chapitre 12: Compilation séparée et programmation modulaire avec le fichier testmat.c. Enfin, la quatrième effectue l’édition de lien sur les fichiers objet matrix.o, vector.o et testmat.o et produit un fichier exécutable appelé testmat. Pour raccourcir cela, on peut utiliser l’une des commandes suivantes: cosun12% cc -c -g matrix.c cosun12% cc -c -g vector.c cosun12% cosun12% cc -g -o testmat testmat.c matrix.o vector.o Bibliothèque de fonctions (librairie). On pourrait en rester là et compiler d'autres programmes se servant des routines de calcul matriciel comme testmat en ajoutant matrix.o et vector.o à la fin de la ligne de compilation. Mais imaginons que les routines matricielles aient été définies non pas en deux fichiers mais en vingt, cela donnerait des lignes de compilation beaucoup trop longues et fastidieuses à taper, sans parler des problèmes d'organisation des fichiers. En fait, les fichiers objets peuvent être regroupés en un seul fichier dans ce que l'on appelle une bibliothèque (ou librairie par mauvaise traduction de l’anglais library), c'est ce que l'on a fait à partir des fichiers objet matrix.c et vector.c pour créer la bibliothèque libmatrix.a présentée à la section 7.3. La commande Unix rassemblant des fichiers objet dans une librairie est ar. Voici un exemple d'appel de cette commande: cosun12% ar cvq libmatrix.a matrix.o vector.o Dès lors, pour compiler testmat.c, plutôt que de mentionner explicitement matrix.o et vector.o à la fin de la ligne de commande de compilation, on peut utiliser l'option -l du compilateur servant à effectuer l'édition de lien avec une librairie: cosun12% cc -g -o testmat testmat.c -lmatrix Notez que l'on doit omettre le préfixe lib ainsi que le suffixe .a du nom de la librairie en argument de l'option -l, c'est pourquoi pour lier testmat avec libmatrix.a on utilise -lmatrix. Makefile.  Lorsqu’un programme contient beaucoup de fichiers, il est parfois assez difficile de se rappeler quel fichier il faut recompiler. Il existe un utilitaire très pratique, appelé make, qui utilise un fichier de dépendances appelé Makefile qui décrit quels fichiers source il faut pour obtenir un exécutable donné. Grâce à cette description make est en mesure de recompiler seulement les fichiers qui ont été modifiés depuis la dernière compilation. Un fichier Makefile se présente comme suit (figure 29): NOM_DE_VARIABLE = valeur. La deuxième ligne du fichier Makefile précédent définit par exemple une variable CFLAGS (option de compilation), qui prend la valeur -g. Dans ce cas, l’intérêt de définir une variable est de pouvoir changer les options de compilation C pour tous les fichiers d’un seul coup. Tant que l’on n’est pas sûr du fonctionnement de son programme, on conserve l’option -g pour pouvoir utiliser le debugger. Une fois que le programme fonctionne, on remplace l’option -g par l’option -O (optimisation), pour améliorer la performance du programme. Après les déclarations de variables viennent les règles de compilation. Les règles de compilation comportent 3 parties: •    le nom du fichier que l’on souhaite créer (appelé fichier cible, target) suivi de ‘:’ •    la liste des fichiers dont le fichier cible dépend (les dépendances, dependencies). Toute modification d'un de ces fichiers entraîne la régénération du fichier cible •    A la ligne suivante: un caractère de tabulation TAB suivi de la commande qui permet de régénérer le fichier cible à partir de ses dépendances. ATTENTION: une ligne de commande dans un fichier Makefile doit impérativement commencer par une tabulation (pas des espaces). Par exemple, la première règle dit que le fichier exécutable testmat dépend des fichiers objets testmat.o, matrix.o et vector.o. Pour reconstituer le fichier exécutable à partir des fichiers testmat.o, matrix.o et vector.o, on utilise la commande cc $(CFLAGS) -o testmat testmat.o matrix.o vector.o. Dans cette commande, la notation $(CFLAGS) veut simplement dire: le contenu de la variable CFLAGS, en l’occurrence “-g”. La deuxième règle dit que le fichier testmat.o dépend des fichiers testmat.c et matrix.h. Pour reconstituer le fichier testmat.o, on utilise la commande cc $(CFLAGS) -c testmat.c. On remarque que les commandes utilisées sont exactement les commandes de la figure 27. cosun12% make cosun12% L’avantage de cette manipulation est qu’en utilisant la commande make, on ne recompilera que les fichiers qui ont été modifié depuis la dernière compilation. Pour obtenir ce résultat, la commande make vérifie la date de création des différents fichiers auxquels il est fait référence dans le fichier Makefile. La commande procède comme suit. Lors de son invocation, si aucune cible n'est précisée, make tente de générer la première cible se trouvant dans le fichier Makefile, en l'occurrence testmat. make considère alors les dépendances de tesmat (testmat.o, matrix.o et vector.o) l'une après l'autre pour vérifier s'il existe des règles pour chacune d'elles. C'est par exemple le cas pour tesmat.o. make tente donc de générer testmat.o d'après sa règle, pour cela make considère d'abord les dépendances de testmat.o (testmat.c et matrix.h) l'une Chapitre 13: Routines graphiques avancées après l'autre pour vérifier s'il existe des règles pour les générer. Or il n'y en a pas, testmat.c et matrix.h sont donc considérés comme des fichiers terminaux qui ne peuvent être générés. Dans ce cas make compare leur date de modification à celle de la dernière génération de testmat.o. Si testmat.o est plus récent que la dernière modification de testmat.c et matrix.h, alors il est à jour et ce n'est pas la peine de le régénérer. Dans le cas contraire la règle de compilation cc $(CFLAGS) -c testmat.c est appliquée. make procède de même pour les autres dépendances matrix.o et vector.o. Si l'une au moins des dépendances est plus récente que sa cible alors la cible est régénérée au moyen de la règle de compilation. Notons qu'il est possible de raccourcir le fichier Makefile en utilisant ce que l’on appelle des règles de compilation génériques, d'effectuer de la compilation de fichiers sous conditions, etc Les possibilités offertes par make sont énormes et dépassent le cadre de ce cours. 13.1  Interaction dans la fenêtre terminal Le fichier Graphics.h contient quatre routines supplémentaires qui permettent d’interagir avec la fenêtre graphique, par l’intermédiaire de la fenêtre terminal dans laquelle vous avez lancé le programme. void StartSingleCharacterMode (void) ; void FinishSingleCharacterMode (void) ; void GetSingleCharacter (char c) ; void CheckForSingleCharacter (char c) ; Programme 93 Le mode d’interaction par la fenêtre terminal permet au programme de réagir à chaque touche de clavier enfoncée. C’est différent de l’interaction habituelle avec l’instruction C scanf ou getchar. Dans ces cas, le programme ne réagit que lorsqu’on enfonce la touche Return. Pour pouvoir utiliser ces fonctions, il faut au début du programme appeler la procédure StartSingleCharacterMode, qui permet au programme de réagir immédiatement, dès qu’une touche est enfoncée. Le programme est fait d’une boucle qui affiche quelque chose dans la fenêtre graphique, attend un petit peu, demande à l’utilisateur ce qu’il faut faire, et recommence la boucle. Pour interroger l’utilisateur, le programmeur dispose de deux routines: GetSingleCharacter et CheckForSingleCharacter. GetSingleCharacter bloque le programme jusqu’à ce que l’utilisateur enfonce une touche. CheckForSingleCharacter retourne ‘?’ si l’utilisateur n’enfonce pas de touche. Si l’utilisateur a enfoncé une touche, la fonction retourne la lettre correspondant à la touche enfoncée. A la fin du programme la routine FinishSingleCharacterMode doit être appelée. Entre les appels StartSingleCharacterMode et FinishSingleCharacterMode, il est interdit d’employer les routines scanf ou getchar. 13.2  Interaction dans la fenêtre graphique Les routines de la section précédente ne permettent pas d’utiliser la souris pour les interactions avec la fenêtre graphique. Pour arriver à ce résultat, il faut changer complètement de modèle de programmation. Dans les programmes g3.c et g4.c de la section précédente, il y avait une boucle infinie qui traitait les interventions de l’utilisateur au clavier. Maintenant, la boucle d’événements est cachée dans la librairie, et le programmeur la lance en invoquant la procédure GraphicsLoop. Cette procédure comporte deux paramètres: le nom de la routine qui est exécutée à chaque itération de la boucle, et le délai entre chaque itération de la boucle. La routine exécutée à chaque itération de la boucle rafraîchit en général l’écran en fonction de l’état du programme. Avant de lancer la procédure GraphicsLoop, il faut indiquer à quels événements la boucle sera sensible. Ces événements peuvent être un mouvement de la souris (SetMouseMotionRoutine), l’enfoncement d’une touche du clavier (SetKeyDownRoutine), le relâchement d’une touche (SetKeyUpRoutine), l’enfoncement d’une touche du clavier en même temps que la touche Control (SetControlKeyDownRoutine), le relâchement d’une touche pendant que la touche Control est encore enfoncée (SetControlKeyUpRoutine), l’enfoncement d’un bouton de la souris (SetButtonDownRoutine) et le relâchement d’un bouton de la souris (SetButtonDownRoutine). enum ButtonT { LeftButton, CenterButton, RightButton }; void SetMouseMotionRoutine (void MouseMotion (int x, int y)) ; void SetKeyDownRoutine (char c, void KeyRoutine ()) ; void SetKeyUpRoutine (char c, void KeyRoutine ()) ; void SetControlKeyDownRoutine (char c, void KeyRoutine ()) ; void SetControlKeyUpRoutine (char c, void KeyRoutine ()) ; void SetButtonDownRoutine (int ButtonT, void ButtonRoutine ()) ; void SetButtonUpRoutine (int ButtonT, void ButtonRoutine ()) ; void DoNothing () ; void GraphicsLoop (void repeatRoutine (), int delay) ; void ToggleDebugMode () ; Programme 94 La routine ToggleDebugMode active ou désactive les messages d’informations de la librairie d’interaction graphique. Les programmes ~gennart/exercice-corriges/g5.c et ~/gennart/exercicecorriges/g6.c illustrent le fonctionnement des procédures du programme 94. 14  Exercices avancés Tous les exercices que nous avons vus jusqu’à présent ont servi à vous faire comprendre les constructions du langage C. Dans cette section, nous essayons de résoudre des problèmes pratiques, en utilisant les constructions du langage. Ces exercices représentent une étape assez importante. Jusqu’à présent, le but était d’écrire des programmes courts. A partir ce cette section, avant d’écrire votre programme, il faut transformer un énoncé en français (expliquant un problème de balistique, la résolution des contraintes dans une structure, ou la rotation en 3-D) en une séquence d’opérations à décrire en C. Les deux étapes: conception du programme, c’est-à-dire, la transformation d’un énoncé en une séquence d’opérations et la réalisation du programme, c’est-à-dire la traduction de ces opérations en C ont autant d’importance l’une que l’autre. Cependant, dans cette section, nous insisterons surtout la partie conception, qui est nouvelle, et laisserons la réalisation des programmes comme exercice. x t( + ?t) ? x t( ) + ?t ? x·( )t = xEU(t + ?t)                                            (EQ 1) Dans cette expression, x t( + ?t) représente la valeur exacte de la fonction x au temps t+?t, et EU x (t + ?t) la valeur approchée de la fonction x au temps t+?t, en utilisant la formule de l’équation (1). Graphiquement, l’équation (1) se représente de la façon suivante: FIGURE 30: Illustration de la formule d’Euler On constate donc que l’on obtient une valeur approchée de la valeur x(t). Comme on fait les calculs de proche en proche, les erreurs s’accumulent. On constate aussi qu’il vaut mieux ne pas choisir une valeur trop grande du pas ?t, sinon l’erreur devient très grande très rapidement. La méthode de Runge-Kutta d’ordre 2 permet de calculer de proche en proche la valeur d’une fonction, de façon beaucoup plus précise que l’approximation de la formule (1). L’idée est de prendre la dérivée au point t+?t/2 et de trouver la valeur approchée x t( + ?t) selon la formule: xRK2(t + ?t) = x t( ) + ?t ? x·(t + ?t ? 2)                                             (EQ 2) ·(t + ?t ? 2) . Pour évaluer la formule (2), trois étapes: Le problème est qu’on ne connaît pas la valeur de x                                      ·( )t   = f t x t( ( )) •    on calcule x •    on évalue d’abord un première approximation de x t( + ?t ? 2) , en utilisant la formule de l’équation (1). EU ceci nous donne l’expression x      (t + ?t ? 2) ·(t + ?t) = f t( + ?t ? 2 xEU(t + ?t ? 2)) , une estimation de la dérivée en • on calcule ensuite x t + ?t . •    On a alors toutes les valeurs nécessaire pour évaluer la formule de l’équation (2). RK4 calculer la nouvelle valeur de x       (t + ?t) est: k1 = ?t ? f t x t( ( )) k2 = ?t ? f t( + ?t ? 2 x t( ) + k1 ? 2) k3 = ?t ? f t( + ?t ? 2 x( )t + k2 ? 2) k4 = ?t ? f t( + ?t x( )t + k3) (EQ 3) RK4                                       k      k      k      k x    (t + ?t) = x t( ) + ---1 + ---2 + ---3 + ---4                                                                                                                              6      3      3      6 Quantité x(t) scalaire: tracé d’une courbe du 3ème degré. On considère f(x(t)) = 3t2-1, et t0= -2, x(t0) = -6. On demande de tracer en fonction de t: •    la courbe t3-t entre -2 et 2, •    la courbe qui résulte de l’évaluation de la formule (1), avec des pas ?t = 0.25, •    la courbe qui résulte de l’évaluation de la formule (2), avec le même pas •    la courbe qui résulte de l’évaluation des formules (3). Le fichier degre3.c sur le serveur CO contient les trois premières parties. Runge-Kutta avec une quantité x(t) vectorielle: balistique. La trajectoire d’un projectile est affectée par la                     gravitation et le frottement de l’air. La force due à la gravitation s’écrit Fg = g m?    . La force due au frotte-                   ment est proportionnelle à la vitesse et s’écrit Ff = k V?  . L’équation du mouvement est donc: ?? 0 ?? ? m – ? ?xy· ? k = ? ?? ?xy·· ? m                                                                                           –g           ? ? Pour avoir une forme canonique, il faut introduire deux variables supplémentaires vx et vy. Le système devient alors: · x    = vx · y    = vy x·· = v·x = 0 – ??vx ? --mk??                                                     (EQ 5) y·· = v·y = – g – ??vy ? --mk?? · Ce système d’équation est de la forme X( )t        = f X t??         ( )??    , avec X = (x, y, vx, vy). On peut donc appliquer la méthode de Runge-Kutta sur chacun des éléments du vecteur, en utilisant par exemple comme valeurs initiales (x, y, vx, vy) = (0,0,2,0.5), ?t = 0.1, k = 0.2, g=0.1, et m=1. Pour afficher le résultat, on affiche les points (x(t),y(t)) pour toutes les valeurs de t calculées. Runge-Kutta avec une quantité x(t) vectorielle: mouvement de la lune autour de la terre. La force d’attraction entre deux corps est inversement proportionnelle à la distance qui les séparent. Si on fait l’hypothèse que la Terre est fixe au centre de l’écran et que (x,y) représente la position de la lune, on a donc:             k m?           1 Fg = –x----------------2 + y2 ? --------------------x2 + y2 ? ? ?? ?xy                         (EQ 6) On a donc un système de la forme:                                                                                               ? ?xm                                                                       (EQ 7) Fg = ma ·· · x    = vx · y    = vy x·· = v·x = –x ? -------------------------2k21.5            (EQ 8) (x + y ) On peut résoudre ce système en utilisant la méthode de Runge-Kutta. Pour afficher le résultat, on affiche les points (x(t), y(t)) pour toutes les valeurs de t calculées. Comme valeurs initiales, on peut prendre x=1.0, y=0.0, vx = 0.0, vy = 1.25. Faites attention à ne pas prendre un ?t trop grand. Une bonne valeur de ?t est par exemple 0.01. Si vous utilisez les routines graphiques pour afficher la position (x,y), utilisez comme taille de graphe (4.0,-8.0,-4.0,2.0). 14.2  Rotation 3-D Routine d’affichage. On considère que l’on a d’une part un graphe, dont les coordonnées sont des nombres réels, et d’autre part un écran dont les coordonnées sont des nombres entiers. Les axes x et y du graphe vont de gauche à droite et de bas en haut respectivement. Les axes xe et ye de l’écran vont de gauche à droite et de HAUT en BAS. La coordonnée (0,0) de l’écran est au coin supérieur gauche. écran                           graphe (0,0) FIGURE 32: Coordonnées de graphe et d'écran Pour dessiner un graphe, l’utilisateur spécifie d’abord la taille de l’écran et la taille du graphe. Il dessine ensuite une série d’objets (points, vecteurs, ) dont les points sont spécifiés en coordonnées de graphe. Les routines de dessin se chargent automatiquement de transformer coordonnées de graphe en coordonnées d’écran. void SetGraphSize(float top,float left,float bottom,float right); void SetScreenSize (int top, int left, int bottom, int right) ; void DrawPoint (float x, float y, float diameter) ; void DrawVector (float fromX, float fromY, float toX, float toY); Chacune des deux routines d’affichage est constituée de deux parties. La première transforme les coordonnées de graphe en coordonnées d’écran (GraphToScreen). La deuxième affiche à l’écran les données nécessaires. La routine GraphToScreen prend en considération la taille du graphe et la taille de l’écran. Routine de projection d’un point 3-D sur un plan.  Les coordonnées 3D sont écrites (X, Y, Z). L’axe X va de l’arrière vers l’avant. L’axe Y va de gauche à droite. L’axe Z va de bas en haut. Les coordonnées 2D sont écrites (x, y). L’axe x va de gauche à droite. L’axe y va de bas en haut. Pour effectuer la projection, on propose la méthode simplifiée suivante: FIGURE 33: Affichage 3-D Pour afficher un point 3D dont la coordonnée en X est 0, on utilise comme coordonnées (x, y) les coordonnées Y et Z du point 3D. Si la coordonnée X du point 3D est non-nulle, on soustrait de Y et de Z la moitié de la coordonnée X. Sur le graphe ci-dessus, l’extrémité du vecteur (1, 2, 3) est affichée en 2D à la coordonnée (2-0.5 =1.5, 3-0.5 = 2.5). En notation matricielle, l’opération de projection est écrite: –0.5 1 0 (EQ 9) –0.5 0 1 L’opération de projection peut donc être écrite simplement sous forme de produit matriciel. Votre routine de projection devrait donc prendre tout au plus quelques lignes. Vérifier en utilisant les routines d’affichage 2D et la routine de projection que vous arrivez à afficher le graphe ci-dessus. La rotation autour d’un axe quelconque consiste à ramener, par deux rotations autour des axes de référence Z et Y, l’axe de rotation sur l’axe de référence X, faire tourner le vecteur autour de l’axe X, et ramener l’axe de rotation à sa position originale par deux rotations autour des axes de référence Y et Z. On écrira d’abord 3 routines d’initialisation de matrice (3,3) de rotation autour des 3 axes de référence (faites attention, les routines sin et cos prennent comme paramètre des radians): void InitXRotationMatrix(MatrixPT m, double theta); void InitYRotationMatrix(MatrixPT m, double theta); void InitZRotationMatrix(MatrixPT m, double theta); Ces trois matrices contiennent les valeurs suivantes:      X axis                                                     Y axis                                         Z axis 1.0    0.0        0.0 0.0 cos? –sin? 0.0 sin? cos? cos? 0.0     0.0     1.0 –sin? 0.0 sin? 0.0 cos? cos? –sin? 0.0 sin? cos? 0.0 0.0        0.0    1.0 Faire tourner un vecteur d’un angle ? autour d’un axe dont les deux angles sont ? et ? consiste à multiplier ce vecteur par cinq matrices de rotation: M0 (rotation d’un angle -? autour de l’axe Z), M1 (rotation d’un angle ? autour de l’axe Y), M2 (rotation d’un angle ? autour de l’axe X), M3 (rotation d’un angle ? autour de l’axe Y), M4 (rotation d’un angle ? autour de l’axe Z: rotatedVector = M4 ? M3 ? M2 ? M1 ? M0 ? vector Il reste à déterminer les angles des rotations à effectuer autour des axes Y et Z. Ceci se fait par une transformation des coordonnées cartésiennes (X,Y,Z) de l’axe de rotation en coordonnées sphériques (r, ?, ?). Graphiquement, les angles sont définis comme suit: Les formules pour effectuer cette transformation s’écrivent: ? = acos? ?? ?zr             ? ? ?----2 ;?----2 ?                         ? = - – ?          ? ? [0;?] 2 y ? 0 ? ??? = acos??--------------rsinx ?????            ? ? [0 2; ?] y ? 0 ? ??? = 2? – acos??r--------------sinx ?????    ? ? [0 2; ?] (EQ 10) Faites attention, car avec les erreurs d’arrondi, l’expression z / r peut être plus grande que 1 (ou plus petite que -1) et prendre l’arccosinus d’une expression plus grande que 1 donne une valeur indéterminée. Pour ce qui est de l’affichage, la meilleure façon pour donner l’impression de mouvement est de successivement dessiner et effacer le vecteur à différentes positions autour de l’axe de rotation. Comme cela efface des points des axes, il est conseillé de redessiner les axes à chaque étape. 14.3 Calcul des contraintes dans un treillis. Par définition, le type de treillis que l’on peut résoudre avec l’algorithme présenté contient n noeuds et 2n -3 barres. La figure suivante présente un treillis contenant (1) 2 noeuds et 1 barre; (2) 3 noeuds et 3 barres; (3) 4 noeuds et 5 barres; (4) 5 noeuds et 7 barres. Les treillis plus compliqués se font en ajoutant à chaque étape 1 noeud et 2 barres. FIGURE 35: Treillis Le treillis (4) représente un pont, avec deux supports. Un des supports est fixé dans les deux dimensions, l’autre support n’est fixé que verticalement. On applique sur le pont une charge ponctuelle P au noeud P3 (P3x,P3y). A partir de cette charge, il est possible de déterminer les réactions aux supports (R1x, R1y, R5y), en considérant d'une part que la somme des forces en direction des axes X et Y est nulle et d'autre part que la somme des couples appliqués au treillis est nulle, ce qui se traduit par: P      + P       = 0                                          1x        3x                                    1y        3y        5y P x + P y + P x + P y + P x + P y = 0 1y 1 1x 1 3y 3 3x 3 5y 5 5x 5 (EQ 11) Ce système de trois équations permet de déterminer les réactions aux supports. Le fichier contenant la représentation du treillis contient à la fois les charges et les forces de réactions. Si vous créez un fichier de représentation du treillis, vous devez vous assurer que la somme des forces extérieures appliquées au pont est bien nulle. Pour déterminer les contraintes dans les barres, on écrit pour chacun des noeuds 2 équations indiquant que la somme des forces selon les 2 axes principaux est nulle. Dans le cas du pont à 5 noeuds, ces équations sont: noeud 1?------------------X2 – X1?? + f2??------------------X3B–13X1?? + P1x = 0 f1? B12 f1??Y-----------------2B–12Y1?? + f2??Y-----------------3B–13Y1?? + P1y = 0 noeud 2f1??------------------X1B–12X2?? + f3??------------------X3B–32X2?? + f4??X------------------4B–42X2?? = 0 f1??Y-----------------1B–12Y2?? + f3??Y-----------------3B–32Y2?? + f4??Y-----------------4B–42Y2?? = 0                                         noeud 3 f2??------------------X1B–13X3?? + f3??------------------X2B–23X3?? + f5??------------------X4B–43X3?? + f7??------------------X5B–53X3?? + P3x = 0 f2??Y-----------------1B– Y3?? + f3??Y-----------------2B–23Y3?? + f5??Y-----------------4B–43Y3??+ f7??Y-----------------5B–53Y3?? + P3y = 0 13f4 noeud 4f4??Y-----------------2B– Y4?? + f5??Y-----------------3B–34Y4?? + f6??Y-----------------5B–54Y4?? = 0 24 f6??------------------X4B–45X5?? + f7??------------------X3B–35X5?? + P5x = 0                                         noeud 5                   f6??Y-----------------4B–45Y5?? + f7??Y-----------------3B–35Y5?? + P5y = 0 fbar??X---------------------------fromBfromto– Xto?? fbar??Y-------------------------fromBfromto– Yto?? (EQ 13) représente la projection de la force fbar sur les axes X et Y. Dans ces expressions, le noeud “from” a pour coordonnées (Xfrom, Yfrom); la longueur d’une barre qui va du noeud “from” au noeud “to” est dénotée |Bfromto|. Une remarque aussi sur les problèmes de force dans une barre est considérée positive si elle est en compression. Pour qu’il n’y ait pas d’erreur de signe dans la matrice, il faut veiller à ce que tous les termes Xto et Ytosur une même ligne aient le même indice. Le même système écrit sous forme matricielle est Les esprits attentifs auront remarqué que le système comporte 10 équations pour 7 inconnues. De par la définition du problème cependant, les trois dernières équations sont des combinaisons linéaires des 7 premières. On peut donc les ignorer, et résoudre un système de 7 équations à 7 inconnues. D’autres considérations permettent de construire la matrice assez facilement: •    chaque colonne contient 4 éléments non nuls, qui correspondent tous à une barre •    chaque ligne contient la projection sur un axe (vertical ou horizontal) de la force interne des barres qui aboutissent à un noeud donné. 14.4  Le labyrinthe On se propose de modéliser un appartement comportant plusieurs chambres en utilisant la structure ChambreT: typedef struct ChambreT { char nom[32] ; int index ; int c1, c2, c3 ; } ChambreT; Programme 95 Le champ nom contient le nom de la chambre, le champ index le numéro de la chambre. Chacune des chambres comporte 3 portes. Les champs c1, c2, c3 indiquent les chambres vers lesquelles chacune des portes mène. Une valeur de -1 pour une des variables c1, c2 ou c3 indique que la porte correspondante est condamnée. écrire le nom des chambres dans lesquelles on peut aller demander un numéro aller dans la chambre correspondant au numéro Programme 96 FIGURE 36: Schéma d'appartement Labyrinthe avec pointeurs. Dans l’exercice précédent, on a défini un tableau contenant 4 chambres. Si l’on ne connaît pas, avant d’exécuter le programme, le nombre de chambres de la maison, on risque comme ci-dessus de perdre beaucoup de place en déclarant des tableaux trop grands. Cette situation est si fréquente qu’on a prévu le concept du pointeur pour utiliser la mémoire de façon optimale. Plutôt que d’avoir un index qui pointe sur un tableau, on utilise un pointeur qui est en fait une espèce d’index pointant directement sur la mémoire de l’ordinateur. Nous allons remplacer les index par des pointeurs. Dans le premier exemple, nous définissons un pointeur pour chaque chambre. La structure avec pointeurs s'écrit comme suit: typedef struct ChambreT { ChambreT *c1, *c2, *c3 ; char nom [32] ; } ChambreT; ChambreT *chambres[4]; chambres[0] = (ChambreT *) malloc(sizeof(ChambreT)); Programme 97 Dans la première structure (Prog. 95), on repère les chambres au moyen d’entiers et dans le deuxième (Prog. 97) au moyen de pointeurs de chambre et plutôt que de mettre les chambres dans un tableau, on met seulement les pointeurs de chambre dans le tableau, et on crée les chambres en utilisant l’instruction malloc. Modifier le programme du labyrinthe en utilisant des pointeurs plutôt que des indices, selon ce qui a été expliqué ci-dessus. . L'assembleur est un langage symbolique permettant de manipuler directement les registres et instructions d'un microprocesseur. L'assembleur a donc une syntaxe spécifique à chaque microprocesseur et qui varie beaucoup d'un microprocesseur à l'autre. .  La séquence // a été introduite par le langage C++ et n'est pas supportée par les compilateurs C stricts. En cas de doute il vaut mieux utiliser les séquence /* */ même pour des commentaires d'une seule ligne .  Un avertissement peut toutefois être généré par certains compilateurs si aucune conversion explicite de type n'est effectuée. .  En fait les opérateurs de division entière et modulo % ne correspondent à la définition mathématique rigoureuse que pour les entiers positifs. Le fait que le résultat de cette expression soit toujours juste est dû au fait que dans le cas où un des deux opérandes est négatif, les erreurs commises sur le modulo et la division entière se compensent! [6] .  En fait si le bloc ne comporte qu'une seule instruction, les accolades peuvent être omises. En pratique il est souvent prudent de les mettre même pour une seule instruction, car cela peut éviter quelques erreurs sournoises. .  Sauf du point de vue de l’instruction continue, voir section 6.14 [8] .  Pour les esprits curieux, GLIB est une variable d'environnement de la fenêtre terminal (à ne pas confondre avec les variables de vos programmes C). On peut en afficher le contenu en utilisant dans la fenêtre terminal la commande echo $GLIB. Cette variable d'environnement permet au compilateur C de trouver comment exécuter chacune des fonctions utilisées, externes au programme. .  Dans les schémas nous utiliserons ces valeurs d'adresse, débutant à la valeur 1000, notez cependant que ce choix est purement arbitraire, généralement les vraies valeurs observées dans les exercices seront beaucoup plus grandes. .  On pourrait aussi utiliser les tableaux dynamiques mais ils amènent ensuite les mêmes problèmes que les tableaux statiques lorsqu’il s’agit de déplacer les données bien qu’ils permettent un gain de place en mémoire. Contactez-nous A propos de nous On recrute Rechercher dans le site Politique de confidentialité Droit d'auteur/Copyright Blog Etudes et métiers Informatique Comptabilité Economie Marketing Management Gestion Statistiques Finance Commerce Electronique Electricité Sci-Tech ABONNEZ-VOUS À LA NEWSLETTER ! Télécharger votre Calendrier 2022 X