Types de données et représentation

Types de données et représentation

Langage C

B. Rouzeyre, Polytech'ERII

1. Action de base

2. Séquencement

3. Bloc et niveau de détail

Représentation des algorithmes

Organigramme : façon graphique de représenter le déroulement d'un calcul

Action 1

Action 1

Action 2

Action 12

Action 11Action 1

Action 2

4. Sélection

Organigramme

Non structuré

Action 23

Action 22

Action 21Action 1

Action 3

Action 23Action 22Action 21

Action 1

Action 3

Critère ?

Ev.1

Ev.3

Ev.2

Ev.1 Ev.2 Ev.3

Σ Evi = 1 et Evi.Evj = 0

Structuré

Se lit de haut en bas et de droite à gauche Se lit en suivant les fils

4. Cas particulier : alternative

Organigramme

Non structuré

Action 22

Action 21Action 1

Action 3

Action 22Action 21

Action 1

Action 3

Critère ?

Vrai

FauxVrai Faux

Structuré

4. Cas particulier : alternative sans action

Organigramme

Non structuré

Action 21Action 1

Action 3

Action 21

Action 1

Action 3

Critère ?

Vrai

FauxVrai Faux

Structuré

5. Itérations : exprime le fait que l'on répète une action

Organigramme

Action 2

Action 1

Action 3

Action 3Action 2

Action 1

Critère

5.1 "Tant que"

Vrai Faux

1 – On évalue le critère2 – s'il est vrai on effectue l'action 2, retour en 12 bis – s'il est faux on passe à la suite

Remarque : éventuellement l'action 2 n'est pas exécutée

5. Itérations :

Organigramme

Action 2

Action 1

Action 3Action 3

Action 2

Action 1

Critère

5.2 "Jusqu'à ce que"

VraiFaux

1 – On exécute l'action 22 – s'il est faux, retour en 12 bis – s'il est vrai, on passe à la suite

Remarque : l'action 2 est exécutée au moins une fois

5. Itérations :

Organigramme

Action 2

Action 1

Action 3

5.3 "Pour tout e ε E"

l'action 2 est exécutée autant de fois qu'il y a d'éléments dans E.

Remarque : si E est vide, Action 2 n'est pas exécutée.

Action 3Action 2

Action 1

e ε E ?Vrai Faux

e <- valeur suivante de E

- utiliser que les primitives précédentes- intérêt : traduction (presque) directe en C- ne pas faire de spaghetti :

- traduction difficile- debug impossible- résultat incompréhensible - => 0 à l'examen

Organigramme : conseil

Action 3Action 2

Action 1

e ε E ?Vrai Faux

e <- valeur suivante de E

Organigramme : exemple

Imprimer S

S=0

x pair ?

x= suivant(x)

x = premier

x dernier ?

S=0

x = premier

Imprimer S

S = S+ x

Vrai

Faux

fin = v

x= suivant(x)

fin = fauxS = S+ x

OKKO

• Les actions ou "instructions" en langage C ne sont en fait que des opérations élémentaires (+,-, * etc…) sur des données unitaires.

• Chaque instruction est suivie d'un ;• Le début d'un bloc est signalé par un { , la fin d'un bloc par }. Un bloc

devient l'équivalent syntaxique d'une instruction.• Ex :

Codage d'un algorithme en C

Calcul

x = 1

y = 2

imprimer z

z = x+y

{x=1;y=2;z=x+y;printf("%d",z);} ;

optionnel

Alternative

if (expression) action1 ;else action2 ;


"problème"

calcul

Imprimer z

Vrai

Faux

"calcul juste"

z = z+10

…if (z == 3) {

printf("calcul juste");z=z+10;

}else printf ("problème");printf ("%d",z);…

fin de l'instruction if

Cas particuliers de alternative


…if (z == 3) ;else printf("problème);printf ("%d",z);…

"problème"

calcul

Imprimer z

Vrai

Faux

Cas particuliers de alternative


calcul

Imprimer z

Vrai

Faux

"calcul juste"

z = z+10

…if (z == 3) {


}else;printf ("%d",z);…

ou bien

…if (z == 3) {


};printf ("%d",z);…

Sélection multiple : en C, la sélection ne peut être qu'une comparaison à des valeurs de constante entière ou caractère (si besoin passer à plusieurs if imbriqués)


…switch (z) {

case 3 : printf("ok"); break;case 4 : printf("PB1"); break;default : "printf ("PB2");

};…

"PB2"

"PB1"

"ok"Action 1

Action 3

z=3

autres

z=4

Structures itératives. Exemple, on veut imprimer tous les nombres de 1 à 10

TANT QUE : while (condition) action;


x=1;while (x <=10) {

printf("%d\n",x);x=x+1;

};…

x=1

imprimer x

x=x+1

x=1

imprimer x

x=x+1

x=1;do {


}while (x <= 11);…

JUSQU'À CE QUE : do action while (condition);

POUR


for(x=1; x≤10; x=x+1)printf("%d\n",x);imprimer x

équivalent TANT QUE

x=1;while (x <=10) {


};…

x=1

imprimer x

x=x+1

Compilateurs

• Sur le web

– ideone.com (pour le début)

• En TP

– Visual C++

Types de données

• 3 types de base

caractères ex : 'a', '1', '\n'

entier relatifsex : 0 , -12, 328

réel3.14, 2.3 e+4

• Remarques :Pas de booléen (vrai, faux)Pas de type chaînes de caractères prédéfini

Type caractère

• Caractère : Symboles alphanumériques (a,z,!,1,9) + caractères spéciaux (retour à la ligne, beep, etc..)

• Un caractère est représenté sur un octet (8 bits) suivant la table ASCII (American Standard Code for Information Interchange)

• ex : 'a' = 9710 = 6116 = 0110 00012

• Table ASCIIex : code ASCII du 'A' = 65'A'<'B'<……..< 'Z''0'<'1'<'2'<…..<'9''a'<'b'<……….<'z'

• Déclaration de variable de type caractèrechar c;c = 'a';

• Constante de type caractère#define caractère_a 'a'

Table ASCII

• Remarques :

les chiffres sont codés suivant un ordre croissant (48 à 57)

idem pour les lettres (65 à 90, 97 à 122)

code des majuscules est inférieur au code des majuscules (différence

constante = 32)

les codes supérieurs à 128 dépendent de la langue :

é, ö , ä, æ, œ etc…

• Déclaration d'une variable caractère :

char c;

c='a';…..

Type caractère

• Caractères spéciaux (retour à la ligne, tabulation etc..)• Exemple :

retour à la ligne = CR = code ASCII 13char retour;retour = 13; ou bien retour = '\n';

• Conventions\n : retour à la ligne\t : tabulation\f : nouvelle page\' : apostrophe\0 : caractère nul (indique la fin d'une chaîne de caractères)

Les entiers : entiers naturels

• Codage sur 2 ou 4 octets suivant le calculateur

• Sur deux octets on peut coder les nombres de 0 à 216-1 (0 à 65535)

• Nombre représenté en base 2, les bits sont rangés dans des cellules correspondant à leur poids, on complète à gauche par des 0

• Exemple :13 = 8 + 4 +1 = 1*23+1*22+0*21+1*20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1

• Déclaration d'une variable entier naturel xunsigned int x;short unsigned int x; (on force sur 16 bits)long unsigned int x; (on force sur 32 bits)

32ou 16n,1,0,21

0

i

in

ii xxx

Type entier relatif

• Implantation sur 2 ou 4 octets suivant le compilateur• Représentation sur n bits : codage complément à 2

• Déclarationsint a,b;….a = 1;….b= 3;

1,0,222

0

11

i

in

ii

nn xxxx

Type entier relatif

• Codage complément à 2

• Si xn-1 = 0 : nombre positif, xn-1 = 1 : nombre négatif• Exemple sur 16 bits

+5 = 1 * 22 + 0 * 21 + 1 * 20 = 0000 0000 0000 0101

-3 = -32768 + 32765= -215+ 214 + 213 + 212 + 211 + 210 + 29 + 28 + 27 + 26 + 25 + 24 + 23 + 1.22 + 0. 21 + 1.20

= 1111 1111 1111 1101• Sur 16 bits (2 octets)

-32768 x 32767• Sur 32 bits

-2147483648 x 2147483647

1,0,222

0

11

i

in

ii

nn xxxx

Complément à 2

• Représentation non symétrique : le plus petit nombre n'a pas d'opposé : sur n bits

• le plus grand entier positif est 2n-1-1• le plus petit entier négatif est -2n-1

• exemple sur 3 bits :000

100

010110

001

011101

111 01

2

3-4

-3

-2

-1

Codage complément à 2

• Remarques1/ Complément à 2 de x = Complément à 1 de x + 1représentation de –3 ?3 = 0000 0000 0000 0011c1(3) = 1111 1111 1111 1100 +1 = 0000 0000 0000 0001c1(3) +1= 1111 1111 1111 1101

2/ Représentation 16 bits = > 32 bitsx >0 = 0000 0000 0000 0011 => x = 0000 0000 0000 0000 0000 0000 0000 0011x <0 = 1111 1111 1111 1101 => x = 1111 1111 1111 1111 1111 1111 1111 1101

• Extensionsint 2 ou 4 octets ? problème de portabilitéshort int x; 2 octetslong int x ; 4 octetsunsigned int x ; bit de signe utilisé pour la valeurunsigned short int x ;unsigned long int x ;

Type réel

• Déclarationfloat x,y;x = 3.14;y = 2.0 e+3;

• Implantation sur 4 octets• Représentation suivant le compilateur

en général mantisse exposant (norme IEEE)

• 10-38 < x < 1038

• Extension :double x; x est codé sur 8 octets

Nombre réels

• Codage des réels : virgule flottante, Norme IEEE• flottant stocké sous la forme M * BE

M : Mantisse ; B : Base ; E : Exposant

• exemple : 123 . 103 = 123 000• Représentation IEEE 754 (signe 1 bit, mantisse et

exposant sur 32 ou 64 bits pour simple et double précision)

• SM : signe de la mantisse : 1 bit• Eb : exposant biaisé : 8 ou 11 bits • M : Mantisse : 23 ou 52 bits

SM Eb M

Mantisse et exposant

• Signe : bit de poids fort (0 = + ; 1 = -)• Exposant

placé avant la mantisse pour simplifier les comparaisons (pour ceci il ne doit pas être représenté en complément à deux : -1 > 2)

sur 8 bits : 0..256 sans signe mais biaisé de 127 (simple précision) : Eb = 1 E = 1 – 127 = -126⇒ Eb = 254 E = 254 – 127 = 127⇒ les exposants 255 (erreur) et 0 (nb dénormalisé) sont interdits

• Mantisse normalisée : bit de poids fort n’est pas 0 et un seul chiffre avant la

virgule• ex : 3,2510 = 11,012 = 1,101 * 21

Virgule Flottante

• Comme le bit de poids fort de la mantisse est nécessairement 1 : on ne l’indique pas (gaspillage de place), il est implicite

• Mantisse partie fractionnaire = f1f2 …fn m = 1,f1f2…fn⇒ nombre x = (-1)SM * 1,M * 2Eb-127

• Exemple x = (-2,5)10 = -1,01*21

2

SM = 1 ; E= 1 => Eb= 128 = 1000 0000 ; m=1,01 => M =010…….0

• Déclaration de variables réelles :float x;double y;

SM

Eb M f1,f2,……fn

Variables

• Variable : élément de mémorisation élémentaire• Toutes les variables doivent être déclarées suivant un type

int a, b; ou bien int a;int b;

float x;char caractere;

• Identificateur de variables (noms)Le premier caractères doit être une lettreLes autres caractères sont les lettres (majuscules et minuscules), les chiffres

et le caractère _Majuscule / minuscule significatifs

• Exemples :Pi, pi3_14, a2B3 : corrects2x, i-E : incorrectsA1 a1

Variables

• Exemple :char a;int un;a = 'a';un =1;a = '1';

• Initialisation des variablesà l'exécution :int i;….i = 0;

à la compilation int i = 0;

Conversion de type

• Conversion explicite : ( type ) expressionExemple :int a; float x; char c;a= 2;x= (float) a;x= 2.3; a= (int) (x+1);a = 98;c = (char) a; -> c='b'

• Conversion impliciteExemple :int a; float x; char c;a= 2;x= a;x= 2.3; a= x+1;a = 98;c = a; -> c='b'

Conversion de types

• Exemples :char c; int i; float f;// conversion entier vers char.c= 98; // implicite : c prend le code ASCII 98 c-à-d ’b'c = (char) 98; // explicite plus propre// char vers entieri= 'a' ; // i prend la valeur 97i= (int) 'a' ; //plus propre// entier vers réelf= 3; // f prend la valeur 3.0;f=(float) 3; //+ propre//réel vers entier, attention : troncaturei = 3.4; // i prend la valeur 3i= -3.7; // i prend la valeur -3i = (int) 3.4; // + propre

Conversion de types : application• Passer au caractère suivant

char c;c ='a';c = c+1; // calcul fait en entier puis résultat converti en charc = (char) ((int) c+1) ; //+ propre

• Conversions majuscule<-> minusculechar c;c='t';// conversion en Majusculec=c-32; // c contient 'T'ou mieuxc=c-('a'-'A'); c=c+1; // c contient 'U' // conversion en minusculec=c+32; ou c=c+('a'-'A')

// conversion en Majusculeif ((c >= 'a') && (c <= 'z')) c = c-('a'-'A');

Tableaux

• Lorsque on veut mémoriser plusieurs données de même type, on peut utiliser un tableau c-à-d on regroupe sous un même nom plusieurs informations

• Exemple de déclaration d'un tableau d'entiersint tab[100]; int : type des éléments du tableautab : identificateur (nom du tableau)100 : nombre d'éléments du tableau (dimension)

tab peut recevoir 100 entiers indicés de 0 à 99 (attention !)le premier est tab[0]le second tab[1]..le dernier tab [99]

Tableaux

• Utilisationchaque élément du tableau est accessible par un indice qui doit être

de type entier, quelque soit le type des éléments du tableau exemples :

int i ;tab[2] 3eme élément du tableautab[2+3] 6eme élément du tableautab[i] i+1eme élément du tableau

• Exemples :stocker les 100 premiers nombres pairs : 0,2,4,...,196,198

int i, t[100];for (i=0; i < 100; i=i+1)

t[i]= 2*i;

Tableaux• Remarques:

1/ chaque élément du tableau s'utilise comme une variable tab[3] = 2;

2/ le nombre maximum d'éléments du tableau (dimension)1/ doit être fixé à la compilation2/ ne peut être modifié pendant l'exécution

3/ Pas d'opérations sur les tableaux en tant que tels

Parcours des éléments d’un tableau

Parcours du premier au dernierint i; /* l’indice de balayage doit être un entier */float t[100]; /* le type du tableau est quelconque, ici réel */for (i=0; i < 100; i=i+1) // ou bien for (i=0; i <= 99; i=i+1)

t[i]= …….;

Parcours du dernier au premierint i; float t[100]; for (i=99; i >= 0; i=i-1)

t[i]= …….;

La dimension

Bonne pratique de programmationint i; int t[100];for (i=0; i < 100; i=i+1)

t[i]= 100;Pb : modification du pgm, changement de la taille du tableau malaisée

#define TAILLE 100int i; int t[TAILLE];for (i=0; i < TAILLE; i=i+1)

t[i]= 100;

Il suffit de changer TAILLE

Exemples

Point de l'espace1ere solution :float x,y,z;2eme solutionfloat pt[3];pt[0] pour x, pt[1] pour y, pt[2] pour z

Mémorisation des 100 premiers nombres pairs et impairs:int pairs[100], impairs[100];int i;for (i=0; i<100;i=i+1) {

pairs[i]=2*i;impairs[i]=2*i+1;}

• En c, pas de type prédéfini chaîne de caractères. En pratique on utilise des tableaux de caractères.

• Convention : le dernier caractère utile est suivi du caractère \0 (de code ascii 0)

• Exemples :char t[10]; (9 caractères max, puisque une case réservée pour \0;strcpy(t,"abcdefghi")chaque lettre est accessible par l'indicechar t[12]; strcpy(t,"abcdefghi");

• Initialisation char t[12]= "abcdefghi"; ou char t[]= "abcdefghi";

• Constante chaîne de caractères#define ceciestuntexte "azssddqsdqsd"

Chaînes de caractères

'a' 'b' 'c' 'd' 'e' 'f' 'g' 'h' 'i' 0

'a' 'b' 'c' 'd' 'e' 'f' 'g' 'h' 'i' 0 ? ?

Définitions de type utilisateur

typedef int entier; (entier est maintenant un type)entier i;

typedef int tableaude20[20];tableaude20 t; int t[20];

Les expressions en langage C

Expressions : introduction

• Remarque : expression instruction• une instruction indique à l'ordinateur de mener une action• expression = élément syntaxique

• Expressions :variable ou constante, ex : x, 3constituées à l'aide d'opérateurs : x+ y

conversion de type, opérateurs arithmétiques, de taille, relationnels et logiques, affectation, bit-à-bit, conditionnels, adresse

Expressions

• Une expression représente une donnée élémentaire : constante, variable, un élément de tableau, la référence à une fonction ou à une valeur, le résultat d'un calcul etc ….

• Exemples3a+bx=yc = a+bx <= yx == yi++ sin(3.14)

• Toute expression a une valeur

Opérateurs arithmétiques

• Opérateurs bi-opérandes+ , -* , / , % (modulo)Les opérandes doivent être des valeurs numériques. entier opérateur entier -> résultat entierréel opérateur réel -> résultat réelentier opérateur réel -> résultat réel

• Exemplesint a,b;a=10; b= 3a+b 13a-b 7a*b 30a/b 3 (division euclidienne)a%b 1

float a,b;a=12.6; b= 3.0a+b 13.6a-b 9.6a*b 37.8a/b 4.2 (division réelle)a%b erreur de syntaxe


• Opérateur % : - int a; flloat x;(a+x) % 4 incorrect. ((int) (a+x))%4 correct- si l'un des opérandes est négatif, le résultat est négatif.

• Si l'un des opérandes est de type caractère, c'est la valeur du code ASCII qui est prise (conversion implicite char vers int ou float)

• Conversion majuscule minuscule

Exemple :char c = 'a';c = c+1; => c = 'b'mécanisme :

c+1 = 98 + 1 =99 c = code ascii 99 = 'c'

Exemple :char c ;if (c >= 'a' && c <='z') c = c-32 (ou bien c = c + 'A' –'a')if (c >= 'A' && c <='Z') c = c+32 (ou bien c = c - 'A' +'a')


• Opérateurs unaires (un opérande)a/ signe : + , -exemple : a = -a;

b/ incrémentation, décrémentation : ++ (+1) , -- (-1)exemple :int i =1;++i;printf("%d",i) ; -> 2;Syntaxes : ++i ou i++++i : la valeur de i est d'abord incrémenté, la valeur résultat est

utilisée dans l'expression courantei++ : la valeur courante de i est utilisée dans l'expression courante,

puis i est incrémenté

++ et --

• Exemplesi=1; i=1;printf("i= %d\n",i); -> i=1 printf("i= %d\n",i); -> i=1printf("i= %d\n",++i); -> i=2 printf("i= %d\n",i++); ->

i=1printf("i= %d\n",i); -> i=2 printf("i= %d\n",i); -> i=2

• Conclusions :1/ appendre la règle (pour comprendre des programmes)2/ à n'utiliser que lorsque il n'y a pas d'ambiguïté :

x=y+z++; // à éviterx++; // pas de risque

Opérateurs d'affectation

• Affectation simplesyntaxe : variable = expressionla valeur de l'expression est stockée dans la mémoire à l'endroit

réservé pour la variableExemples :a = 2; b=1; c=0;a = b+c;a = b && c;la valeur de l'expression vaut la valeur affectée

Attention : affectation et test d'égalitéif (a =1) instruction1; else instruction2;L'instruction1 est toujours déclenchée.

a = b = 3; (évaluation de droite à gauche)

Opérateurs d'affectation

• Affectation et opération : +=, -=, *=, /=, %=,<<= , >>=, &=, |=, ^=

Syntaxe : variable opérateur expressionéquivalent à : variable = variable opérateur expression

Exemple :int i;i= 3;i+=2; // même chose que i=i+2;printf("%d\n",i); -> 5

Opérateurs relationnels et logiques • Valeur logique :

0 : faux 0 : vraiexemple : if (3) traitement1 ; else traitement 2; équivalent à : traitement1;

• Relationnels : >= , > , == , <, <= , !=• La valeur de l'expression est 1 si l'expression est vraie , 0 si elle est fausse

Exemple : 2 < 3 vaut 1 , 2 > 3 vaut 0

• Attention à la confusion : test d'égalité == et l'affectation =ex : if (x=0) traitement 1; // au lieu de x==0 else traitement 2;

Conséquence: En cas d'erreur, non seulement le traitement 1 ne sera jamais exécuté mais en plus x vaudra 0 quelle que soit sa valeur initiale

• Logiques : && "et" logique , || "ou" logique, ! "non" logiqueDans l'évaluation de l'expression, 0 est considéré comme la valeur logique "faux", toute valeur 0

comme la valeur logique "vraie"La valeur de l'expression est 1 ou 0Exemples:

2 && 0 vaut 0 et donc est faux2 || 0 vaut 1 et donc est vrai !0 vaut 1 !4 vaut 0

Opérateurs bit à bit

• Opèrent sur les représentations des valeurs• & et , | ou, ^ ou-exclusif, ~ complément à 1 ,• << décalage à gauche, >> décalage à droite, • Attention : & &&• Exemples

5 0000 0000 0000 010120 0000 0000 0001 01005 & 20 0000 0000 0000 0100 => 5 & 20 => 45 | 20 0000 0000 0001 0101 => 5 | 20 => 215 ^ 20 0000 0000 0001 0001 => 5 ^ 20 => 17~5 1111 1111 1111 1010 => -6

• Affectation/bit-à-bit : &=, |=, ^=, ~=

Décalages

• Décalages• à gauche a << b : a est décalé à gauche de b bits (les bits ajoutés

valent 0) 5 << 2 0000 0000 0001 0100 20un décalage d'une position à gauche correspond à une multiplication

par 2

• à droite a >>b : a est décalé à droite de b bits (les bits insérés valent le bit de poids fort)

14 0000 0000 0000 1110 14 >> 2 0000 0000 0000 0011 3-6 1111 1111 1111 1010-6 >> 1 1111 1111 1111 1101 -3un décalage d'une position à droite correspond à une division par 2

(en respectant le signe)

Opérateur conditionnel

• Syntaxe expression1 ? expression2 : expression3

à peu près équivalent à :if (expression1) expression2; else expression3;

• Exemple :maximum = (x>y) ? x : y;

if (x>y) maximum =x ; else maximum = y;

• Conseil : ne pas utiliser (peu clair)

Opérateurs d'adressage

• Adresse de : &Syntaxe : &variable , donne l'adresse mémoire de la variableExemple :int i,adr;adr = &i;

ne pas confondre avec le "et" bit à bit

• Dont l'adresse est : *Syntaxe *expression : donne le mot mémoire dont l'adresse est

donnée par l'expressionExemple :int i,adr;i=1;adr = &i;printf("%d", *adr); -> 1

Opérateur de taille : sizeof

• Donne la taille de l'implantation• 2 syntaxes

1/ sizeof expression exemple :int i,j ;j= sizeof i; -> 2 ou 4 (octets)

2/ sizeof (type)exmples :typedef char tab[100];tab t;int n;n = sizeof(int), -> 2 ou 4 (octets)n = sizeof(tab) -> 100 (char)

Opérateurs divers

• ( ) : force l'ordre des calculsex : 1 + 2 * 3 -> 7

(1+2) * 3 -> 9

• [ ] pour les tableauxt[2] équivalent à *(t+2)

• -> et . (opérateurs sur structures, + tard)

Priorité des opérateursPriorité Opérateurs Description Associativité15 () [ ] -> . opérateurs d'adressage ->

14

++ -- incrément/décrément

<-

~ complément à un (bit à bit)! non unaire& * adresse et valeur (pointeurs)(type) conversion de type (cast)+- plus/moins unaire (signe)

13 * / % opérations arithmétiques ->12 + - "" ->11 << >> décalage bit à bit ->10 < <= > >= opérateur relationnels ->9 == != "" ->8 & et bit à bit ->7 ^ ou exclusif bit à bit ->6 | ou bit à bit ->5 && et logique ->4 || ou logique ->3 ?: conditionnel <-

2 = += -= *= /= %= >>= <<= &= ^= |= assignations <-

1 , séparateur ->

Priorité des opérateurs

a – b /c *d

(a-b) / (c-d)

i = j = k = 0;

a=1; b=4;! --a == ++ !b!0 == ++01 == 11

Priorité des opérateurs (exercices)main(){int x, y , z;x = 2;x += 3 + 2; printf("%d\n",x);x -= y = z = 4; printf("%d%d%d\n",x,y,z);x = y == z; printf("%d%d%d\n",x,y,z); x == (y = z); printf("%d%d%d\n",x,y,z);

x = 3; y =2 ; z = 1;x = x && y || z ; printf("%d\n", x);printf ("%d\n", x || ! y && z);x = y = 0;z = x ++ -1; printf ("%d, %d\n", x, z);z += -x ++ + ++ y; printf ("%d, %d\n", x, z);

x =1 ; y =1;printf("%d\n", ! x | x);printf("%d\n", ~ x | x);printf("%d\n", x ^ x);x <<= 3 ; printf("%d\n", x);y <<= 3 ; printf("%d\n", y);y >>= 3 ; printf("%d\n", y);

Priorité des opérateurs (exercices)x =0 ; y =0; z=0;x+=y+=z;printf("%d\n", x < y ? y : x) ;printf("%d\n", x < y ? x++ : y++) ;printf("%d, %d\n", x , y);printf("%d\n", z += x < y ? x++ : y++) ;printf("%d, %d\n", y , z);

x = 3; y = z = 4;printf("%d\n",( z >= y >= x) ? 1 : 0) ;printf("%d\n", z >= y && y >= x ) ;x = y = z = 0;}

ENTREES / SORTIES

Les entrées/sorties (lecture/écriture)

• Lecture clavier2 fonctions de base : getchar () et scanf()Elles peuvent être appelées soit indépendamment soit au sein

d'expressionsExemples getchar();while (c==getchar()) {…..};

getchar()

• getchar() : sert à la lecture de caractères isolés• la valeur de getchar() est le code ascii du caractère lu• utilisation

char c;c = getchar();

• Exemple : on veut lire et mémoriser 2 caractères donnés sur 2 lignes différenteschar c1,c2;c1 = getchar() // acquiert le 1er caractèregetchar (); // filtre le <cr>, on ne mémorise pas la valeur luec2 = getchar () // acquiert le 2ème caractère

scanf ()

• Sert à la lecture de données et convertit la succession de caractères donnés en entiers, flottants, caractères, chaîne de caractères

• Syntaxe : scanf (format,arg1,arg2,……,argn) le nombre d'arguments est quelconque arg1, arg2,……, argn sont les adresses des variables dans

lesquelles on stocke les valeurs lues variable simple (entier, caractère, flottant) : &v chaîne de caractères = tableau : v

le format est une chaîne de caractères précisant le type des arguments afin de convertir la suite de caractères lus dans les arguments

Scanf : format

• Format chaîne de caractères composée de caractères % suivis d'une lettre

et éventuellement séparés par des blancsla lettre indique le type de conversion à effectuerexemple :

int i; float x;scanf("%d %f", &i,&x);

le %d indique que le premier argument est un entierle %f indique que le second est un réel

réponse : 23☐12.623 est converti en entier et stocké dans i12.6 est stocké en flottant et stocké dans x

Scanf : format• caractères de conversion

c : donnée de type caractère simpled : donnée de type entier relatiff : donnée de type flottante : donnée de type flottant en notation exponentiellex : donnée de type entier hexadécimals : donnée de type chaîne de caractères (tabl. de char terminé par \0)

• Exemple char t[20];int i ; float x;scanf ("%s %d %f", t,&i,&x);

réponses : 1/ abcde 123 0.052/ abcde 123

0.053/ abcde

123 0.05

Scanf : rôle des caractères ☐, , tabulation, dans les réponses

• Dans les réponses☐, , tabulation servent de délimiteurs pour les valeurs numériques et les

chaînes de caractères (pas pour les caractères)• Exemples

scanf ("%d%f",&i,&x);rep1 : 123 ☐☐☐☐456 i = 123 , x = 456.0rep2 : 123456 i = 123456 , x : pas encore lu (en attente)

scanf("%s%d",ch,&i);rep : abc 12 ch = "abc" , i=12

scanf ("%c%c",&c1,&c2);rep1 : ab c1= 'a' , c2 = 'b'rep2 : a☐b c1= 'a' , c2 = ☐

scanf ("%c%c%c",&c1,&c2,&c3);rep1 : ab c1= 'a' , c2 = 'b', c3= rep2 : ab c1= 'a' , c2 = 'b'

c c3 =

Scanf : rôle des caractères ☐ et tabulation, dans la chaîne de format

• Lecture de valeurs numériques : aucun rôlescanf ("%d%f",&i,&x) scanf ("%d☐%f",&i,&x)

• Lecture de caractères : indique de sauter les ☐, tab et • Exemples

scanf ("%c%c%c",&c1,&c2,&c3);rep1 : abc c1= 'a' , c2 = 'b', c3= 'c'rep2 : a☐b☐c c1= 'a' , c2 = '☐', c3= 'b'

scanf ("%c☐%c☐%c",&c1,&c2,&c3);rep1 : abc c1= 'a' , c2 = 'b', c3= 'c'rep2 : a☐b☐c c1= 'a' , c2 = 'b', c3= 'c'rep2 : a☐b c c1= 'a' , c2 = 'b', c3= 'c'

Scanf : compléments

• Nombre de caractères lusfaire précéder le caractère de format du nombre de caractères (max)

désiréExemples

int i,j,k;scanf("%3d %3d %3d",&i,&j,&k);rep1 : 1☐2☐3 i=1 j=2 k=3rep2 : 123☐456☐789 i=123 j=456 k=789rep3 : 123456789 i=123 j=456 k=789rep4 :1234☐5678☐9 i=123 j=4 k=567

int i; float x;char c;scanf("%3d☐%5f☐%c,&i,&x,&c);rep : 10☐234.567☐t i=10 x=234.5 c='6'

Scanf : compléments

• Lecture d'une chaîne de caractèreschar ch[50];scanf("%s",ch) // pas de &rep : abcdefghi

Le caractère 0 de fin de chaîne est ajouté automatiquement Exercice : faire l'équivalent de scanf("%s",ch) à l'aide de getchar()

• Saut conditionnel de caractères : %*d, %*fpermet de sauter des données correspondantes dans la réponseexemple :

int i,j; char c;scanf("%d ☐ %*d ☐ %c",&i,&c);rep1 : 12☐34x i=12 c='x'rep2 : 12☐x i=12 c='x'

'a' 'b' 'c' 'd' 'e' 'f' 'g' 'h' 'i' 0 ? ?

scanf : compléments

• Filtre sur chaînes de caractères[ caractères admissibles] ou [^caractères non admissibles]

exempleschar ch[100];scanf("%[0123456789]",ch);rep : 32ab48 ch="32"

scanf("%[^0123456789]",ch);rep : 32ab48 ch="ab"

raccourcis : [0123456789] ou [0-9][abcdefg] ou [a-g]

Ecriture

• 2 fonctions de base : putchar() et printf()

• putchar(caractère)

• Exemplechar c;c='a';putchar ( c );putchar ('\n');putchar('b');

Affichage :ab

Printf()

• Formatprintf(format,arg1,arg2,…..,argn);

les arguments sont des valeurs d'expression à imprimerle format donne le texte mort et le mode de décodage des argumentsle format est une chaîne de caractères

• Exemples :printf("bon"); printf("jour");printf("\n") bonjouri=j=1;printf("i=%d\n",i) i=1printf("%d%d%d\n",i,j,i+j); 112printf("%d☐%d☐%d☐%d\n",i,j,i+j,sqrt(i)); 1☐1☐2☐1x=3.0;printf("%f☐%d\n",x,i); 3.000000☐1printf("%d\n%d\n",i,i+j); 1

2

Printf

• Caractères spéciaux de format%d : imprime les entiers sur le nombre de caractères nécessaires%f : imprime les réels avec 6 chiffres de partie décimale%e : imprime les réels en notation exponentielle%c : imprime un caractère%s : imprime une chaîne de caractères jusqu'à rencontrer le

caractère de fin de chaine 0 (erreur si absent)…..\n : saut à la ligne\t : tabulation\p : saut à la page….

Printf : mises en forme

• Forçage du nombre de caractèresentiers :

%5d l'entier est imprimé sur 5 caractères au moins (blancs) avec cadrage à droite

%-5d l'entier est imprimé sur 5 caractères au moins (blancs) avec cadrage à gauche

réels :%10f le réel est imprimé sur 10 caractères (en tout) avec 6 chiffres en partie décimale (cadrage à droite)%-10f idem + cadrage à gauche

limitation de la partie décimale%20.3f le réel est imprimé sur 20 caractères (en tout) avec 3 chiffres en partie décimale

Printf : format variable

• ("%*d",n,i) n donne le nombre de caractères pour i

• ("%*.3f,n,x) n donne le nombre total de caractères pour x

• ("%*.*f,n,m,x) n donne le nombre de total caractèresm donne le nombre de caractères pour la partie décimale

• Exemples

Printf

• La valeur de retour du printf est le nombre de caractères écrits et une valeur négative si il y a eu un pb.

• Exemple :int a,x;a=32;x = printf ("%d\n",a);printf ("%d\n",x); -> 3

Autres fonctions d'E/S

• Beaucoup d'autre fonctions d'E/Svoir "stdio.h"

gets, puts permettent de lire et d'écrire des chaînes de caractères contenant des espaces (rappel : scanf ("%s",….) les espaces sont des délimiteurs)

exemple :#include "stdioh"main()

{char ligne[80];gets(ligne);puts(ligne);}

Lecture/Ecriture dans fichiers

• Principe : identique aux lecture/écriture sur clavier/écranEn fait, le clavier et l'écran sont des fichiers particuliers

• Il faut simplement en plus "ouvrir" le fichier c-à-d- l'associer à un fichier physique (sur disque)- l'associer à un variable interne du pgm

• Un fichier peut être- soit lu (read)- soit (ré-)écrit (write) bande magnétique- soit écrit à la fin (append)

• Déclaration :FILE * variable-interneex : FILE * f; // f est une variable spéciale de type "fichier"

Ouverture de fichier : fopen

• variable = fopen("nom du fichier sur disque",mode d'ouverture)mode d'ouverture :

syntaxe : chaîne de caractères1er caractère :

'r' = read = lecture'w' = write = écriture'a' = append = écriture à la fin

fopen renvoie la valeur NULL (=0) si le pb sur le fichier physique

• ExempleFILE * f;f = fopen ("c:\texte.txt","r1234");if (f==NULL) printf ("le fichier est absent\n");else printf ("ok\n");

variable interne

fichier physique

Fermeture du fichier : fclose

• Supprime l'association fichier physique-variable interne• La variable interne peut être associée à un autre fichier

physique

• Syntaxefclose (variable interne)

• Exemple :FILE * f;f= fopen (fichier1, "r");….fclose (f);…f= fopen (fichier2,"w");…

Lecture dans fichier

• Lecture : fgetc() et getc() ↔ getchar()exemple

c=fgetc(f);

fscanf() ↔ scanf() exemplefscanf(f,"%d",i) le 1er argument est le variable interne fichier

• Le caractère EOF indique la fin de fichier• Ecriture

fputc () ↔ putchar() // c= fgetc (f)fprintf() ↔ printf() // fprintf(f,"……",…..);

Exercice

• Afficher à l'écran le contenu d'un fichier (idem commande unix ou MSDOS type)

main() {FILE * monfichier;char sur_disque[100]; char c;/* acquisition du nom */scanf("%s",sur_disque);/*ouverture*/monfichier=fopen(sur_disque,"r");if (monfichier==NULL) printf("erreur\n");else { // lecture affichage

while ((c=getc(monfichier))!=EOF) printf("%c",c);fclose (monfichier);}

}

Lecture/ecriture dans chaines de caractères

• sprintf (char * s, format, paramètres) = écriture dans la chaine s

• sscanf (char * s, format, paramètres) = lecture dans la chaine sexemplechar tokenstring[] = "15 12 14... " ;char s[81]; char c; int i; float fp; /*lecture de différentes valeurs: */ sscanf( tokenstring, "%s", s ); sscanf( tokenstring, "%c", &c ); sscanf( tokenstring, "%d", &i ); sscanf( tokenstring, "%f", &fp ); /* Sortie*/printf( "String = %s\n", s ); printf( "Character = %c\n", c ); printf( "Integer: = %d\n", i ); printf( "Real: = %f\n", fp ); }

• Sortie : String = 15 Character = 1 Integer: = 15 Real: = 15.000000

Lecture/écriture dans chaines de caractères

• Exercice : Convertir un entier en une chaîne de caractères :

exemple :int i = 135,;char s[1000];/* à faire */

……..printf("%s",s); 135;

Compléments sur les instructions de contrôle

• Instruction if : imbrication

ex1 : if(e1) if(e2) s1;else s2;

else if (e3) s3;else s4;

e1

s1s1

s2

s3

s4

e2

e3

ex2 : if(e1) s1; else if (e2) s2;

ex3 : if(e1) s1; else if (e2) s2;

else s3;

ex4 : if(e1) if(e2) s1;else s2;

e1

s1

s2e2

e1

s1

s2

s3e2

e1

s1s1

s2e2

e1

s1s1

s2

e2

Compléments sur les instructions de contrôle

• Règle : le else se rapporte au if le + imbriqué

e1

s1s1

s2

e2

if(e1) {if(e2) s1;} else s2;

if(e1) if(e2) s1;else ;

else s2;

Compléments sur les instructions de contrôle : continue

• Dans une structure itérative : l'instruction continue permet d'arrêter l'itération courante sans sortie de la boucle

• Exemple: Calculer la moyenne des valeurs positives d'un tableau d'entiers relatifs.

nb_valeurs=0;somme = 0;for (i=0;i<dim;i++) {

if (T[i]<0) continue;somme = somme + T[i];nb_valeurs ++;}

moyenne = somme / nb_valeurs

Instruction break

L'instruction break fait sortir de la structure de contrôle dans laquelle elle est imbriquée

Utilisation dans les boucles : permet de faire une boucle avec une condition de type "et" logique

ex: while (c1 && c2) {traitement;}while (c1)

if (!c2) break;else {traitement;}

Application typique : gestion d'exception

différence entre continue et break

for (i = 0 ; i < 10 ; i++) { if (i == 5) break ; printf("%d,",i) ; }0,1,2,3,4,

for (i = 0 ; i < 10 ; i++) { if (i == 5) continue ; printf("%d,",i) ; }0,1,2,3,4,6,7,8,9

breakOn veut afficher tous les éléments d'un tableau d'entiers jusqu'à rencontrer un nombre <0 (si il y en a un)

for (i=0;t[i]>=0 && i<dim;i++) ou bien i=0;printf("%d", t[i]); while(t[i]>=0 && i<dim)

{printf("%d", t[i]);i++};

Pb : lorsque i=dim, il y a évaluation de t[dim] qui n'existe pas => erreur

Solution 1 : avec un "drapeau »positif=1; // positif indique que l’on a eu que des valeurs positives jusqu'à maintenant for (i=0; (positif==1) && (i<dim) ; i++) {

if(t[i]<0) positif=0;else printf("%d", t[i]);}

Solution 2 : for (i=0; i<dim;i++) {

if(t[i]<0) break;else printf("%d", t[i]);}

Instruction switch

• syntaxe : switch (expression) instructions où expression a une valeur entière ou caractère

• L'instruction est une expression composée d'alternatives. Chaque alternative commence par une énumération de cas

• switch (expression) {case valeur 1 : instruction1; instruction 2; ….;case valeur 2 : instruction1; instruction 2; ….;…case valeur n : instruction1; instruction 2; ….;default : instruction1; instruction 2; ….; // optionnel};

switch

Exemple :char c;printf("donner un e couleur\n");c=getchar();if (c>='a' && c<='z') c=c+'A'-'a' switch (c) {

case 'R' : printf("Rouge \n");case 'V' : printf("Vert\n");case 'B' : printf("Bleu\n");default : printf ("Autre");}

R

Rouge

BleuVert

Autre

V

BleuVert

Autre

B

Bleu

Autre

Autre

switch + break

Exemple :char c;printf("donner un e couleur\n");c=getchar();if (c>='a' && c<='z') c=c+'A'-'a' switch (c) {

case 'R' : printf("Rouge \n");break;case 'V' : printf("Vert\n");break;case 'B' : printf("Bleu\n");break;default : printf ("Autre");}

R

Rouge

V

Vert

BBleu

Autre

b ou B

switch + break

Exemple :char c;printf("donner une couleur\n");c=getchar();switch (c) {

case 'r','R' : printf("rouge \n");break;case 'v', 'V' : printf("Vert\n");break;case 'b','B' : printf("Bleu\n");break;default : printf ("Autre");}

r ou R

Rouge

v ou V

Vert

Bleu

Autre

Les tableaux

Rappel : tableau =regroupement de données de même type sous un même nom, accessibles par un indice (0,..,dim-1)

Déclaration et implantation mémoire :

int t[50]; => réservation dans la mémoire de 50 cases contiguës d'entiers.

L'adresse de la première case est t

&t[0] t

*t t[0]

t[0]t[1]t[2]

t[48]t[49]

t

• Initialisation à la compilation int t[10] = {1,2,3,4,5,6,7,8,9,10};float x[4] = {0.,0.25,3.14,2.57};char couleur[4]= {'r','v','b','j'};char texte[10]="abcd"; int t1[10] = {1,2,3};

• Dimension par défaut:int t[ ]={0,0,0} => dimension =3char t [ ]={'r','v','b','j'}; => dimension=4char t[ ]="abcd" => dimension=5

par contre int t[ ] sans initialisation est incorrect

a b

Tableaux

1 2 3 4 5 6 7 8 9 10

c d \0 ? ? ? ? ?

1 2 3 ? ? ? ? ? ? ?

0. 0.25 3.14 2.57

r v b j

Tableaux

• Accès aux éléments d'un tableau

int t[50];

syntaxe 1// accès à la (i+1)ème case avec i compris entre 0 et 49t[i];

syntaxe 2puisque t est l'adresse de la première case :t[0] *t // mot d'adresse t, * : opérateur mot dont l'adresse est)t[1] *(t+1) // rem : priorité des opérateurs)…t[i] *(t+i) // *t+i t[0]+i

Tableaux à plusieurs dimensions• Tableau dont chaque case est elle-même un tableau

ex : typedef int t[100] // t est un typet matrice [20];

matrice est un tableau de 20 cases, chacune est un tableau de 100 entiers => matrice est un tableau de 20*100 entiers

autre déclaration : int matrice [20][100]; // tableau de 20 "lignes" et 100 "colonnes"

• Accès aux élémentspar un 1er indice allant de 0 à 19 et par un 2eme indice allant de 0 à 99matrice[3] est la 4eme case de tableau. C'est un tableau de 100 cases

(entiers)matrice[3][48] est un entier.

matrice [i][j] avec i de 0 à 19 et j de 0 à 99

matrice est un tableau à 2 dimensions

• Pas de limitations sur le nombre de dimensionsEx à 3 dimensions : tableau de coord. de pts de l'espacetypedef float point[3] ; // x: indice 0, y : indice 1, z : indice 2point tab[100][100]; // tab = matrice de 100 pointsou bientab[100][100][3];

tab[2][5][1] représente le "y" du point rangé en ligne 2 et colonne 5

• Implantation mémoireint t[3][2];

Tableaux à plusieurs dimensions

t[0][0]t[0][1]t[1][0]

t[2][0]t[1][1]

t[2][1]

t[0]

t[1]

t[2]


• Initialisation (à la compilation)int t[3][2] = {1,2,3,4,5,6};ou bien (+ clair)int t[3][2] = {{1,2},{3,4},{5,6}};

int t[3][2] = {{1,2},4,{5,6}}; => t[1][1] non initialisé

• Initialisation grâce à des boucles for (i=0;i<3;i++)

for (j=0;j<2;j++)t[i][j]=0;

t[0][0] = 1t[0][1] = 2t[1][0] = 3

t[2][0] = 5t[1][1] = 4

t[2][1] = 6

t[0]

t[1]

t[2]


• Accés aux éléments

int t[dim1][dim2] ;t[i][j] * (t+i*dim2+j)

int t[dim1][dim2][dim3];t[i][j][k] * (t+i*dim2*dim3+j*dim3+k)

int t[dim1][dim2]….[dimn] ;t[i1][i2]….[in] * (t

+i1*dim2*dim3*dim4….. *dimn

+i2* dim3*dim4….. *dimn

+…..+in-1 *dimn

+in) )

=> la première dimension n'est pas utilisée dans le calcul

Les fonctions• Une fonction permet de :

– Remplacer une partie qui se répète– Découper un programme en parties isolées -> débogage, lisibilité, etc..

• Exemples : fonctions d'E/S (scanf, printf, …), mathématiques (sin, cos, …)• Organisation d'un programme :

Déclarations de variables et de types globauxtype fonction1 (arguments) {Déclarations de variables et de types locaux à la fonctionInstructions}type fonction2 (arguments) {Déclarations de variables et de types locaux à la fonctionInstructions}...void main (arguments) {Déclarations de variables et de types locaux à la fonctionInstructions}

Exemple

char minus_majus (char c1) {char c2; /* déclarations locales */if (c1 >= 'a' && c1 <= 'z') c2 = c1+'A'-'a';else c2=c1;return (c2);

}void main() {

char c,majuscule;printf("Donner un caractere\n");c = getchar(); getchar();majuscule = minus_majus(c);

printf ("La majuscule de %c est %c\n",c,majuscule);}

Type de la valeur de retour

Argument

Instructions

Appel de la fonction

Valeur renvoyée

Définition de fonction : syntaxe

type_fonction nom_fonction (type_arg1 arg1, …, type_argn argn) {…return (valeur retournée);}

Dans l'exemple précédent : char minus_majus (char c1) type_fonction : char, c'est le type de la valeur renvoyée par returnnom_fonction : minus_majustype_arg1 : chararg1 : c1

Le nombre d'arguments est quelconque, éventuellement aucun, les parenthèses doivent toujours figurer (ex: main () )

Type de la fonction

• Une fonction peut ne pas renvoyer de valeur.• Exemple void print_majus (char c1) {

char c2;if (c1 >= 'a' && c1 <= 'z') c2 = c1+'A'-'a';else c2=c1;printf("la majuscule de % est %c, c1, c2);return; /* ou bien return (); ou bien ;*/

}

• Dans ce cas, le type de la fonction est : void • Le type de la fonction ne peut être que :

• int, float, char void, ou adresse_de • ni tableau, ni autre type complexe

Instruction return

1/ Indique la valeur de retour de la fonction.2/ Arrête l'exécution de la fonctionchar minus_majus (char c1) {

if (c1 >= 'a' && c1 <= 'z') return (c1+'A'-'a');else return (c1);printf("%c",c1); // jamais executée

}Pour les fonction de type void, return est optionnelvoid print_majus (char c1) {

char c2;if (c1 >= 'a' && c1 <= 'z') c2 = c1+'A'-'a';else c2=c1;printf("la majuscule de % est %c, c1, c2);

}

Appel des fonctions

• L'appel d'une fonction se fait en donnant son nom, suivi de la liste des paramètres entre parenthèses. L'ordre des paramètres correspond à celui des arguments.

• Exemplefloat puiss (float x, int n) {float y=1.0;if (n>0) for (i=1;i<=n;i++) y = y*x;else for (i=1;i<=n;i++) y = y/x;return (y);}

void main () {float z,t;z = puiss(10.7,2);t = puiss (z,-6);...}

Appel des fonctions• Un appel de fonction peut se faire comme opérande d'une expression, soit comme

paramètre d'un autre appel de fonction.• Exemple

int maximum (int x, int y) {return((x>y)?x,y));}void main () {int v1,v2,v3,m1;scanf("%d %d %d , &v1,&v2,&v3);m1 = maximum(v1,v2);m1 = maximum(m1,v3);printf("valeur maximale %d\n", m1);}

ou bienm1 =maximum(v1,v2);printf("valeur maximale %d\n", maximum(m1,v3));

ou bienprintf("valeur maximale %d\n", maximum(maximum(v1,v2),v3));

Règles de déclaration et d'appel• Toute fonction ne peut appeler que des fonctions déclarées avant elle ou elle-même

( exception : la fonction main ne peut pas s'appeler).... f1 (..) {...}... f2 (...) {...}... f3 (...) {...}void main (...) {...}la fonction main peut appeler f1,f2,f3la fonction f3 peut appeler f1,f2,f3la fonction f2 peut appeler f1, f2la fonction f1 peut appeler f1

• Lorsqu'une fonction s'appelle elle-même, on dit qu'elle est "récursive".

Déclarations en "avance"

• Règle précédente contraignante• Solution : Prototype

En début de programme on donne le type de chaque fonction , son nom, le nombre et les types des arguments : prototype

• Information suffisante pour le compilateur.

float puiss (float,int);void main(){puiss (10.2, 5);...}float puiss (float x, int n){ float y=1.0;if (n>0) for (i=1;i<=n;i++) y = y*x;else for (i=1;i<=n;i++) y = y/x;return (y);}

/*Prototype de la fonction puiss*/

/*Appel avant déclaration*//*Déclaration de la fonction */

Fichier "header"

• Conseil de programmation :Dans un fichier ".h" déclarer les prototypes de toutes les fonctions,

par exemple malib.hDans le ou les fichiers ".c", insérer la directive

#include "malib.h"

Passage des paramètres

• Rappel : les paramètres sont associés aux arguments suivant l'ordre de déclaration.

• En c, cette association se fait par COPIE de la valeur du paramètre dans l'argument. Chaque argument est en fait une variable locale de la fonction. La fonction travaille sur l'argument.

• Conséquence : Une fonction ne modifie pas les paramètres d'appelsvoid f (int a){a=a+1;}void main(){int b;b=0;f(b);printf("%d\n",b); ->0}

Détailvoid f (int a){a=a+1; /*t3*/}void main(){int b;b=0; /*t1*/f(b); /*t2*/printf("%d\n",b); /*4*/}

b 0

/*t1*/

b 0

a 0

b 0

a 1

b 0

/*t2*/ /*t3*/ /*t4*/

CopieInchangé

Modification des paramètres

• Si l'on veut qu'une fonction modifie un paramètre, on ne passe pas la variable mais l'adresse de la variable. Il y a copie de l'adresse de la variable. Dans la fonction on va chercher la variable par son adresse.

• Rappels : opérateur & : &variable -> adresse de la variableopérateur * : *adresse -> valeur qui se trouve à cette adresse

int i; int * adresse_i; /* déclaration d'une adresse d'entier */ i=0; adresse_i=&i; printf("%d\n",i); -> 0; printf("%d\n",*adresse_i); -> 0; ...

void f2 (int * a){ // a est l'adresse, *a est l'entier *a=*a+1; /*t3 on incrémente le mot d'adresse a*/}void main(){int b;b=0; /*t1*/f2(&b); /*t2 &b est l'adresse de b */printf("%d\n",b); /*t4*/ -> 1}

Modification des paramètres

b 0

/*t1*/

b 1 b 1

/*t2*/ /*t3*/ /*t4*/

a

728 b 0

&b 728

aCopie

728

&b 728

728

*a

Exemple : scanf ("%d",&v);

Passage d'un tableau à une dimension en paramètre

• Rappels:– Lorsqu'on déclare un tableau, par ex int t[10], t est l'adresse du 1er élément

du tableau– Chaque élément du tableau peut être accédé par t[i] ou *(t+i)– La première dimension d'un tableau n'est pas utilisée dans le calcul de

l'adresse d'une case• Exemple

void printtab (int t1[50]) {int i;for (i=0;i<50;i++)printf("%d",t1[i]);}void main () {int t[50];.....printtab(t);}


• Puisque la dimension n'est pas utilisée, on peut ne pas la donner void printtab (int t1[50]){int i;for (i=0;i<50;i++)

printf("%d",t1[i]);}

ou bienvoid printtab (int t1[]) {int i;for (i=0;i<50;i++)


Syntaxes équivalentes


Conséquence : on peut donc appeler cette fonction avec tout tableau d'entiers quelle que soit sa dimension. C’est au programmeur à gérer les débordements de tableau => donner le nombre de cases sur lequel travaille la fonction

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

void main () {int t[50],t2[100];...printtab(t,50); /*affiche toutes les cases de t de 0 à 49*/printtab(t2,100); /*affiche toutes les cases de t2 de 0 à 99*/printtab(t+20,30);/*affiche toutes les cases de t de 20 à 49*/printtab(t+20,10);/*affiche toutes les cases de t de 20 à 30*/}


Puisqu'en fait t1 est une adresse, on peut le déclarer comme tel

void printtab (int * t1,int n) {int i;for (i=0;i<n;i++)



Conséquence :Si un argument est de type tableau (càd une adresse), la fonction

peut modifier les cases du tableau

void misea0 (int t1[], int n){int i;for (i=0;i<n;i++)t1[i]=0;}

void main () {int t[10]={1,2,3,4,5,6,7,8,9,10};printtab(t,10); -> 1 2 3 4 5 6 7 8 9 10misea0(t,10); printtab(t,10); -> 0 0 0 0 0 0 0 0 0 0 }

Fonctions de manipulations de chaînes de caractères

• Rappel : une chaîne de caractères est un tableau de caractères. Le caractère \0 marque la fin de la chaine.

#include "string.h"....char S1[]="abcd";char S2[20];S2 = S1 ; incorrectstrcpy(S2,S1);

void strcpy( char * dest, char * source){int i;i=0;while(source[i]!=\0) {

dest[i]=source[i]i++;}

dest[i]=\0}

Fonctions de manipulations de chaînes de caractères

• Toutes les fonctions de manipulation de chaines de caractères suivent ce gabarit.

• strlen(char * s) : donne la longueur de s, le 0 final non compris• strcat (char * s1, char * s2): ajoute s2 à la fin de s1• strcmp(char * s1, char * s2): compare les chaines suivant l'ordre

lexicographique. Valeur de retour : >0 si s1 > s2=0 si s1 = s2<0 si s1 < s2

"abc" < "abcd""aa"< "ab""aa" < "b"

et bien d'autres fonctions (voir string.h)

Fonctions et tableaux à plusieurs dimensions

Rappel: Pour des tableaux à plusieurs dimensions, la première dimension n'est pas utilisée pour le calcul d'adresse, mais la seconde , la troisième etc.. sont nécessaires .

int t[dim1][dim2]….[dimn] ;t[i1][i2]….[in] * (t

+i1*dim2*dim3*dim4….. *dimn

+i2* dim3*dim4….. *dimn

+…..+in-1 *dimn

+in)

ConséquenceLorsqu'un argument est un tableau à plusieurs dimensions il faut donner explicitement sa deuxième, troisième etc...


Exemple void zero_mat (float t[30][40]) {int i, j;for (i=0;i<30;i++)

for (j=0;j<40;j++)t[i][j]=0;

}

void main() {float t1[30][40];zero_mat(t1);}

Remarques :Dans void zero_mat (float t[30][40]),

1/le 30 est inutile2/le 30 n'a pas de rapport avec le 30 de la boucle for

Fonctions et tableaux à plusieurs dimensionsAutre déclarationvoid zero_mat (float t[][40]) {int i, j;for (i=0;i<30;i++)

for (j=0;j<40;j++)t[i][j]=0;

}

void main() {float t1[30][40];zero_mat(t1);}

Mais void main() {float t1[30][40];float t2[40][40];// zero_mat peut être utilisée pour t2, mais seules les 30 premières "lignes" seront mises à zero}


Autre déclaration (mieux)void zero_mat (float t[][40], int lignes) {int i, j;for (i=0;i<lignes;i++)

for (j=0;j<40;j++)t[i][j]=0; // pas de pb dans les calculs d'adresse

}

void main() {float t1[30][40];float t2[40][40];zero_mat(t1,30);zero_mat(t2,40);}

Fonctions et tableau à plusieurs dimensions

Cette fonction n'est utilisable qu'avec des tableaux dont la deuxième dimension est 40

float t1[30][40];float t2[30][50]; /* on ne peut pas utiliser la fonction sur t2 */

Ennuyeux ! si l'on manipule des matrices avec une deuxième dimension différente.

Comment contourner la difficulté ?

Faire soit-même l'adressage des cases dans la fonction en gérant les dimensions


void zero_mat (float * t, int l, int c) {int i,j;

/* rappel t[i][j] = *(t+i*dim2+j) */for (i=0;i<l;i++)

for (j=0;j<c;j++)*(t+i*c+j) = 0.0;

} void main(){float t1[20][40],t2[30][10];

zero_mat (t1,20,40);zero_mat (t2,30,10);zero_mat (t1,20,5); /* correct ou incorrect ? effet ? */zero_mat (t1,10,40); /* correct ou incorrect ? effet ?*/}


Pour que le calcul soit correct il faut que c soit égal à la deuxième dimension vraie du tableau

void zero_mat (float * t, int l , int c) {int i,j;

/* rappel t[i][j] = *(t+i*dim2+j) */for (i=0;i<l;i++)for (j=0;j<c;j++)*(t+i*c+j) = 0.0;

} void main(){float t1[20][40],t2[30][10];zero_mat (t1,20,40); /* correct */zero_mat (t2,30,10); /* correct */zero_mat (t1,20,5); /* incorrect */zero_mat (t1,10,40); /* correct */}


Solution : passer la deuxième dimension en paramètrevoid mat0 (float * t, int l , int c, int dim2) {

int i,j;/* rappel t[i][j] = *(t+i*dim2+j) */

for (i=0;i<l;i++)for (j=0;j<c;j++)

*(t+i*dim2+j) = 0.0;} void main(){float t1[20][40],t2[30][10];zero_mat (t1,20,40,40); // correct mieux: mat0 (&t1[0][0],…)zero_mat (t2,30,10,10); // correctzero_mat (t1,20,5,40); // correctzero_mat (t1,10,20,40); // correct}

Visibilité des variables

• On appelle visibilité ou portée des variables les règles qui régissent l'utilisation des variables. Les mêmes règles régissent les types définis par l'utilisateur.

• Règle 1 : variables globalesLes variables déclarées avant la 1ere fonction peuvent être utilisées dans toutes les

fonctions. Ces variables sont dites globales.#include "stdio.h"int i; void f1 () {

i = i+1;}

void main(){i=0;f1();printf("%d\n",i) -> 1}


• Règle 2 : variables localesLes variables déclarées dans une fonction ne peuvent être utilisées

que dans cette fonction. Ces variables sont dites locales.

void f1 () {int i; i = i+1;

}void main(){i=0; -> ERREUR : i n'existe pas pour main...}


• Règle 3 : arguments = variables localesLes arguments d'une fonction sont aussi des variables locales de la fonction.

void f1 (int i) {i = i+1; /* i est une variable locale de la fonction */

}void main(){int j=1; f1(j);printf("%d\n",j)}• Règle 4 : Au sein d'une fonction, toutes les variables doivent avoir des noms

distincts void f1 () {

int i;char i; -> ERREUR : i existe déjài = i+1;

}


• Règle 5 : Des variables déclarées dans des fonctions différentes peuvent porter le même nom sans ambiguïté.

void f1 () {int i; sous-entendu i_f1...

}void f2 () {

char i; sous-entendu i_f2...

} void main(){

int i; sous-entendu i_main....

}Ces 3 variables n'ont rien de commun


• Règle 6 : Si une variable globale et une variable locale ont le même nom, on accède à la variable locale dans la fonction où elle est déclarée.. Si il n'y a pas de déclaration locale, on accède à la variable globale.

int i;void f1 () {

int i;i=2; /* i de f1 */

}void main(){

i=0; /* i global */f1();printf (%"d\n",i); -> 0

}

Conseils

• Evitez autant que possible l'usage des variables globales => limitation des effets de bord indésirables

int i;void f1 () {

...i=i+1;

}void main(){

i=0; f1();printf (%"d\n",i); -> 1

}• Dans f1, on travaille sur i global :

– Est-ce bien ce que l'on désirait (oubli de déclaration d'une nouvelle variable locale ?)

– Débogage difficile : il faut inspecter le code en détail pour voir où sont modifiées les variables.

Conseils

• Si l'on ne peut éviter les variables globales, respecter un code pour différencier les variables globales des variables locales.

• Par exemple :si l'initiale de la variable est une majuscule -> globale : Vglob minuscule -> locale : vlocou bien le nom de chaque variable globale commence par G_ : G_variable

etc...

• Pas de confusion entre variables locales et globales.• Mêmes règles pour les déclarations de type que pour les variabes

Compléments : static

• Static : une telle variable maintient sa valeur à travers les appels de la fonction

void inc( ){

int i=0;i++;printf ("%d", i);

}

void inc( ){

static int i=0;i++;printf ("%d", i);

}

1, 1, 1, 1, … 1, 2, 3, 4, …

Compléments : register

• Une déclaration "registre" indique au compilateur qu'une variable sera utilisée fréquemment.

• Si c'est possible, le compilateur utilisera un registre pour implanter la variable plutot qu'un emplacement mémoire (vitesse d'exécution)

• register int i;

Structures

• Une structure permet de rassembler sous un même nom des données de types différents

• Une structure peut contenir des donnés entières, flottantes, tableaux , caractères, pointeurs, etc... Ces données sont appelés les membres de la structure.

• Exemple : fiche d'indentification d'un personne– nom, prénom, âge, liste des diplômes, etc...

Définition d'une structure

• Déclaration d'une structure : syntaxe

• Exemple : compte bancaire

struct nomdelastructure {typemembre1 nommembre1 ;typemembre2 nommembre2 ;…typemembren nommembren ;}

struct compte {int no_compte ;char etat ;char nom[80];float solde;};

struct compte a,b,c; /*déclaration de 3 variables de ce type*/

Déclarations de variables

• Autres façons de déclarer des variables structurestruct compte {

int no_compte ;char etat ;char nom[80];float solde;} a, b; /*déclaration de 2 variables de ce type*/

struct compte c; /*déclaration de 1 variable de ce type*/

struct { /* le nom de la structure est facultatif */int no_compte ;char etat ;char nom[80];float solde;} a,b,c; /*déclaration de variables de ce type ici */

/* mais plus de possibilité de déclarer d'autres variables de ce type*/

Déconseillé

Déclarations de variables• Autres façons de déclarer des variables structure

• Dans ce cas puisque on ne se sert plus de "struct compte" par la suite

typedef struct compte {int no_compte ;char etat ;char nom[80];float solde;} cpt ;

/* cpt est alors un type équivalent à struct compte*/

cpt a,b,c; /*déclaration de variables de ce type*/

Recommandé

typedef struct {int no_compte ;char etat ;char nom[80];float solde;} cpt ;

Structures imbriquées

• Une structure peut être membre d'une autre structure

• Remarque : ordre de déclaration des structures

struct date {int jour; int mois;int annee;};

struct compte {int no_compte ;char etat ;char nom[80];float solde;struct date dernier_versement;};

Structures

• Tableaux de structures

• La portée du nom d'un membre est limité à la structure dans laquelle il est défini. On peut avoir des membres homonymes dans des structures distinctes.

struct compte client[100];

struct s1 {float x;int y ;};

struct s2{char x;float y;};

Pas de confusion

Manipulation des structures

• Initialisation à la compilation

• Accés aux membres : opérateur . Syntaxe : variable.membre

struct compte {int no_compte ;char etat ;char nom[80];float solde;struct date dernier_versement;};

struct compte c1 = {12345,'i',"Dupond",2000.45,01,11,2009};

1/ c1.solde = 3834.56;

2/ struct compte c[100]; y=c[33].solde;

3/ c1.dernier_versement.jour = 15; c[12].dernier_versement.mois = 11;

Manipulation des structures

• Sur les structures elles-mêmes– Affectation :

– Pas de comparaison , il faut comparer tous les membres

c[4] = c1

Structures et pointeurs

• L'adresse de début d'une structure s'obtient à l'aide de l'opérateur &

• c1 est de type cpt, pc est un pointeur sur une variable de type cpt

• Accés au membres à partir du pointeur

• Opérateur ->

typedef struct {int no_compte ;char etat ;char nom[80];float solde;struct date dernier_versement;} cpt ;

cpt c1 , * pc;

pc = &c1;

*pc.no-compte = ...

(*pc).no-compte = ...

pc->no-compte = ...

Incorrect . est plus prioritaire que *

Structures et fonctions

• Les membres d'une structure peuvent être passés comme paramètres à des fonctions avec ou sans modification

• Ex1 (sans modification)

float ajoute_au_compte(float solde1, float somme1) {solde1 = solde1+somme1;return (solde1);

}void main () {......cpt c1;c1.solde = 0.;ajoute_au_compte(c1.solde,1000.0);printf("%f\n",c1.solde); -> 0.000000c1.solde=ajoute_au_compte(c1.solde,1000.0);printf("%f\n",c1.solde); -> 1000.000000


• Ex2 (avec modification)

void ajoute_au_compte(float * solde1, float somme1) {*solde1 = *solde1+somme1;

}

void main () {......cpt c1;c1.solde = 0.;ajoute_au_compte(&(c1.solde),1000.0); /* ou &c1.solde */printf("%f\n",c1.solde); -> 1000.000000

Structures et fonctions• Un argument de fonction peut-être de type structure

• Ou pointeur sur structure

float ajoute_au_compte(cpt c, float somme1) {return(c.solde+somme1);

}

void main () {cpt c1;c1.solde = ajoute_au_compte(c1,1000.0); printf("%f\n",c1.solde); -> 1000.000000

void ajoute_au_compte (cpt * c, float somme1) {c->solde = c->solde + somme1;

}

void main () {cpt c1;ajoute_au_compte(&c1 ,1000.0); printf("%f\n",c1.solde); -> 1000.000000


• La valeur de retour d'une fonction peut être une structure

cpt ajoute_au_compte(cpt c, float somme1) {cpt c2;c2=c;c2.solde=c.solde+somme1;return(c2);

}

void main () {......cpt c1;c1.solde = 0.;c1=ajoute_au_compte(c1,1000.0); printf("%f\n",c1.solde); -> 1000.000000

Récursion

• Définitions :• Une notion est dite récursive quand elle fait référence à elle-même

soit directement soit indirectement. • Récursion directe : A -> A -> A• Récursion indirecte : A-> B ->.... -> A

• Exemples :• arbre : racine et des branches vers des sous-arbres• n! = n*(n-1)! • Un problème peut être représenté par un algorithme récursif quand il

peut être décomposé en un ou plusieurs sous-problèmes de même type mais de taille inférieure.

Récursion

• Méthode générale :1) Le paramétrage consiste à mettre en évidence les éléments dont dépend la solution, en particulier la taille du problème.2) La recherche et la résolution d'au moins un cas trivial : consiste à résoudre le problème directement, c-à-d sans appel récursif, dans un cas particulier.3) La décomposition du cas général consiste à passer d'un problème de taille N à un ou des problèmes de taille < N.

• Exemple 1 : calcul de factorielle.1) paramétrage : n2) cas triviaux : 1! = 0! = 13) décomposition : n! = n* (n-1)!

Récursion

int facto (int n) { int p;if (n==0) return (1);else {p = n * facto(n-1); /* appel récursif à la fonction facto */return (p);}

• Lors du calcul de facto(n) il y a n appels à la fonction facto.

La pile contient n "assiettes" correspondant à cette fonction.

Récursion

Exemple 2 : Suite récurrente : Suite de Fibonacci (récursion double);Un = Un-1 + Un-2U1 = U0 =1

1) paramétrage : n2) cas triviaux : U1 = U0 =1;3) décomposition : Un = Un-1 + Un-2 • Implantation en langage C int fibo (int n) {

if ((n==0) || (n==1)) return (1);else return ( fibo(n-1) + fibo (n-2) ); /* appel récursif à la fonction fibo */}

• Lors du calcul de fibo (n) il y a 2n appels à la fonction fibo. La pile contient n

"assiettes" correspondant à cette fonction.

Récursion

Exemple 3 : Combinaisons Cnp (méthode du triangle de Pascal);

1) paramétrage : n et p2) cas triviaux : Cn

0 = 1 Cnn = 1

3) décomposition : Cnp = Cn-1

p-1 + Cn-1p

Implantation en langage Cint combinaisons (int n, int p) {

if ((n==p) || (p==0)) return (1);else return(combinaisons(n-1,p-1)+combinaisons(n-1,p))

/* appel récursif à la fonction combinaisons */}

RécursionExemple 4 : Tri par partition d'un tableau T sur l'intervalle [a , b]1) paramétrage : a et b2) cas triviaux : a >= b-1 , rien à faire3) décomposition : Trier T sur [a,b] : - Faire la partition de T sur [a, b] et soit adpivot l'adresse du

pivot après partition - Trier T sur [a , adpivot - 1] - Trier T sur [adpivot + 1, b]

void tri (tab T , int a , int b){ int adpivot; if (b > a+1) { /* sinon ne rien faire */

partition (T,a,b,&adpivot);tri(T,a,adpivot-1);tri(T,adpivot+1,b);}

}

Récursion

Exemple 5 : Recherche du zéro d'une fonction continue sur [a , b]Pb : Trouver un zéro x0 d'une fonction continue sur [a , b] avec une précision > 0

donnée si il en existe, sinon détecter qu'il n'y a pas de zéros.On cherche x et y / x < y ≤ x + et tels que f(x).f(y) < 0.Principe de dichotomie :

- si a et b sont tels que f(a). f(b) <0 alors il existe un zéro dans [a,b].- sinon, on divise l'intervalle en 2 moitiés et on recherche dans le premier intervalle. Si l'on n'a pas trouvé de zéro on cherche dans le second.

1) paramétrage : a , b et 2) cas triviaux : a < b ≤ a + et f(a). f(b) <0 alors il existe un zéro dans [a,b] et x0 = a

a < b ≤ a + et f(a). f(b) > 0 alors il n'existe pas de zéro dans [a,b]3) décomposition : principe de dichotomie

Récursion

int zero (float a, float b, float epsilon, float * x) { / * retourne 0 si il n'existe pas de zero dans l'intervalle

a , b; 1 sinon */int trouve;if ( b-a <= epsilon)

if (f(a) * f(b) < 0 ) { *x = a; return (1); };else return (0);

else {trouve = zero (a,(a+b)/2,epsilon,x);if (trouve) return(1);else return(zero ((a+b)/2,b,epsilon,x));}

}

Récursion

Exemple 6 : Les tours de Hanoi : Soient 3 socles A, B et C. Sur le socle A sont posées n disques de taille décroissante. Le problème consiste à transférer tous les disques du socle A au socle B en respectant les contrainte suivantes :

- on ne déplace qu'un disque à la fois- on ne peut déplacer que les disques se trouvant en haut de

chaque socle - on ne peut déplacer un disque que si on le pose sur un

disque plus grand ou sur un socle vide. Exemple avec 5 disques :

Socle A Socle B Socle C

Récursion

1) paramétrage : N : nombre de disques, socle de départ, socle relais, socle final

2) cas triviaux : N = 0 ne rien faire ; N= 1, et socle final vide : déplacer de départ à final

3) décomposition :Transférer N disques de A vers B en passant par C :

- Transférer N-1 disques de A vers C en passant par B - Déplacer 1 disque de A vers B - Transférer N-1 disques de C vers B en passant par A

void hanoi (int n, char depart, char final, char relais) {if (N>0) {

hanoi(n-1, depart, relais, final);printf("deplacement de %c à %c\n", depart, final);hanoi(n-1, relais, final, depart) ;} ;

}

Récursion

remarques :- la seule véritable action est faite par le printf- pour n disques il y a 2n appels à la fonction hanoi

appels successifs Actionshanoi(3,'A','B','C')

hanoi(2,'A','C','B')hanoi(1,'A','B','C')hanoi(0,'A','C','B') rienA vers B A vers B (1)hanoi(0,'C','B','A') rienA vers C A vers C (2)hanoi(1,'B','C','A')hanoi(0,'B,'A,'C') rienB vers C B vers C (3)hanoi(0,'A','C','B') rienA vers B A vers B (4)hanoi(2,'C','B','A')hanoi(1,'C','A','B')hanoi(0,'C','B','A') rienC vers A C vers A (5)hanoi(0,'B','A','C') rienC vers B C vers B (6)hanoi(1,'A','B','C')hanoi(0,'A,'C,'B') rienA vers B A vers B (7)hanoi(0,'C','B','A') rien








1

3

6

4

2

7


5

Exercices

1- Que fait la fonction suivante ?

int f (int n) {if (n<0) return(f(-n));if (n==0) return (0);return(1+f(n/10);

}

2- Ecrire une fonction récursive qui teste l'existence d'une lettre donnée dans une chaine de caractères. Son prototype est : int existe_lettre(char lettre, char * chaine)

Adresses et pointeurs

• Adresse = Pointeur

• Rappels : opérateur & : & variable -> adresse de la variableopérateur * : * adresse -> valeur qui se trouve à cette adresse

int i; int * adresse_i; /* déclaration d'une adresse d'entier */ i=0; adresse_i=&i; printf("%d\n",i); -> 0; printf("%d\n",*adresse_i); -> 0;


• Déclaration de pointeurs• Syntaxe

type * variable /* type : char, float, int, structure */ex : int * pi; /* pi est un pointeur d'entier */float * px; /* px est un pointeur de réel */char * pc ; /* pc est un pointeur de caractère */

• Interprétations int * pi ;

int * pi ;

Le mot d'adresse pi est un entier => pi est un pointeur

pi donne une adresse

• Types de pointeurs type_simple * variabletype_simple : int, float, char, pointeur

int i; int * pi;int * * ppi ;/* adresse d'adresse d'entiers */pi= &i;ppi = π

• Pas de pointeurs de tableau (le nom du tableau est déjà un pointeur)int t[10]; int * * ppi ; ppi = &t;


i

pi

ppi

...11509

728

23712

11509

...23712

38124

Pointeurs et opérations

• Sur variable pointée : toute opération valide sur le typefloat x,y,* px; ...px= &x;y = sinus (*px);

• Sur pointeursRemarque : La valeur d'un pointeur n'a pas d'intérêt en elle-même, d'autant qu'elle

change à chaque exécution. 1/ affectation int * pi, * pj;float * px;...pi= pj;px = (float *) pi; /*conversion de type de pointeur */

Pointeurs et opérations

2/ comparaison d'égalité, d'inégalité

int * pi, * pj;...if (pi==pj) ......;

3/ comparaison : >, < , .... mais aucun intérêt.

Etats d'un pointeur, NULL

Un pointeur doit donner l'adresse d'une zone mémoire allouéeint * pi, * pj;int i1,i2;i1=0;pi=&i1;i2 = *pi; /* correct */i2 = *pj -> erreur

PB : comment différencier une adresse valide d'une adresse invalide ?

NULL est une valeur spéciale indiquant qu'un pointeur ne pointe vers rienint * pi, i;pi = NULL;if ( ....) pi = &i;if (pi != NULL) printf ("%d",*pi);

Etats d'un pointeur, NULL

3 états d'un pointeur :1/ NULL2/ ≠ NULL

2.1 adresse valide2.2 adresse invalide

PB : comment différencier une adresse valide d'une adresse invalide ?ne jamais avoir de pointeur dans l'état 2.2 => initialiser tous les pointeurs à NULL

Allocation dynamique de mémoire

Jusqu’à maintenant, on a vu que tous les objets (variables) ainsi que leur taille devaient être déclarés au moment de la compilation, càd explicitement dans le code C.

En particulier, la dimension des tableaux doit être connue au moment de l’écriture du pgm et ne peut être modifiée au moment de l’exécution.

Les fonctions de gestion "dynamique" de mémoire permettent de remédier à cette limitation.

2 fonctions de base :

malloc() : allocation d'une zone de mémoire

free() : libération d'une zone mémoire précédemment alloué grâce à malloc

La fonction malloc

la fonction malloc permet de réserver n octets contigus (un tableau) dans la mémoire.

La valeur de retour est l'adresse du premier octet réservé.

Exemple :int * t; //t est un pointeur d'entierint n;printf("combien d entiers voulez-vous réserver ? \n");scanf("%d",&n);t = (int*) malloc (n*sizeof(int));

Calcul du nombre d'octets

conversion de type

La fonction malloc

Exemple :int * t; //t est un pointeur d'entierint n;….t = (int*) malloc (n*sizeof(int));..// accès aux éléments*t = … // 1ere case ou bien t[0]*(t+1)=…//2eme case ou bien t[1]*(t+2)=…//3eme caseou bien t[2]…*(t+i)=…//ieme case ou bien t[i]

En fait, on a "réservé" un tableau de n cases

La fonction malloc

Prototype

void * malloc (int n) ;

nombre d'octetstype de pointeur

La fonction free

La fonction free permet de libérer l'espace mémoire alloué par un malloc précédent.

Ex :int * pt;int n;… /*t1*/…pt = (int*) malloc(n*sizeof(int)); /*t2*/…free (pt); /*t3*/…

/*t1*/

npt

/*t2*/

npt

/*t3*/

npt

La fonction freeRemarque :Après free, pt ne vaut pas NULL et il indique pourtant une adresse inaccessible.

Faire toujours suivre un free par une mise à NULL du pointeurfree (pt); /*t3*/pt=NULL;

/*t3*/

npt

malloc et free

l'adresse donnée comme paramètre à la fonction free doit correspondre à une adresse renvoyée par un malloc précédent

int * pt;int n;pt = (int*) malloc(n*sizeof(int)); pt = pt+1free (pt); => ERREUR…

Il ne faut jamais "oublier" l'adresse renvoyée par un malloc, seul moyen d'atteindre les cases réservées => risque de saturation de la mémoire

int * pt;…pt = (int*) malloc(sizeof(int)); /*t1*/pt = (int*) malloc(sizeof(int)); /*t2*/pt = (int*) malloc(sizeof(int)); /*t3*/…

malloc et free

/*t1*/

pt

/*t2*/

pt

/*t3*/

pt

Libre

Occupé

Occupé inaccessible

Autres fonctions

• calloc : idem malloc + initialisation des cases réservées à 0

• realloc : permet d'agrandir une zone mémoire déjà réservée

– Ex : scanf ("%d", &taille);t = (int *) malloc (taille*sizeof(int));……..……..nouvelle_taille = taille+100;t =(int *) realloc(t, nouvelle_taille*sizeof(int));

Tabelau à une dimension (inconnue à la compil)

int * t; int n;

printf("taille du tableau ? ");scanf ("%d", &n);

t = (int *) malloc (n* sizeof(int));

t[0]= …;…t[n-1]= …;

Tableaux à plusieurs dimensions variables

Rappelst[dim1][dim2] ~ dim1 tableaux de dim2

int t[3][2] : tableau de 3 cases, chaque case est un tableau de 2 entiers

rappel : la première dimension n'est pas utilisée dans le calcul d'adresset[i][j] <-> *(t+i*dim2+j)

t[0][0]t[0][1]t[1][0]

t[2][0]t[1][1]

t[2][1]

t[0]

t[1]

t[2]

Première dimension inconnue à la compilation ~ t[n] [2]

Même principe que pour les tableaux à une dimensiontypedef int t2[2]; // t2 est un typet2 * t; // t est un pointeur sur un objet de type t2scanf("%d",&n);t = (t2 *) malloc(n*sizeof(t2));

L'accès aux éléments par la notation t[i][j] est utilisable puisque : t[i][j] <-> *(t+i*2+j) // 2 est la taille d'un objet de type t2, c'est la 2eme dimension

Première dimension "variable"

t[0][0]t[0][1]t[1][0]

t[2][0]t[1][1]

t[2][1]

t[0]

t[1]

t[2]

t[n-1][0]t[n-1][1] t[n-1]

Deuxième dimension "variable"Deuxième dimension inconnue ~ t[4] [n]

Principe : on utilise un tableau de pointeurs

int * t[4]; // t est tableau de 4 pointeurs// Création du tableau :scanf("%d",&n);for (i=0;i<4;i++)t[i] = (int *) malloc(n*sizeof(int));

t[1]

t[0]

t[2]

t[3]

Deuxième dimension "variable"

Accès aux éléménts :t[i][j] est traduit en *(t[i]+j) : donc notation utilisable

Intérêt : tableau de chaines de caractèresDe plus pour les chaines de caractères, l'initialisation est possible :char * semaine[7]= {"lundi","mardi,..,"dimanche"};


Deux dimensions inconnues ~ t[n] [m] ~ matrice

La deuxième dimension est inconnue à la compilation mais sera constante

int ** t; // t est un pointeur sur un tableau de pointeurs

ex:scanf("%d %d",&n,&m);// allocation des lignest = (int * *) malloc(n*sizeof(int*));

// allocations des colonnesfor (i<0;i<m;i++)

t[i]=(int *) malloc (m*sizeof(int));


Accès aux éléménts :t[i][j] est traduit en *(*(t+i)+j) : donc notation utilisable

t[1]

t[0]

t[2]

t[3]

….

…

t[n-2]

t[n-1]

Tableaux à plusieurs dimensionsDeux dimensions inconnues, la deuxième peut varier

Exemple : stocker un nombre inconnu de chaines de caractèreschar ** dic; int cpt = 0;char tmp[100]; //tableau intermédiaire pour la lectureint nb = 10; // nombre de chaines prévues par défautdic = (char **) malloc(nb * sizeof(char *));for(i=0;i<nb;i++) dic[i]=NULL;printf("donner un nom"\n);scanf("%s",tmp);while (strlen(temp)!=0) {

dic[cpt] = (char *) malloc(strlen(tmp)*sizeof(char));strcpy(dic[cpt],tmp); nb++;

if (cpt> nb-1) { // on augmente la première dimensionnb=nb+10;dic = (char **) realloc(dic,nb*sizeof(char*));

for(i=nb-1;i>nb-11;i--) dic[i]=NULL; }Exercice : trier les noms par ordre alphabétique

Structures et allocation dynamique de mémoire : listes, files, piles, etc..

Pas plus de variables que de pointeurs déclarés

Lorsque on veut créer dynamiquement des variables, on :- déclare un pointeur sur structure- dans la structure on définit un membre qui est lui-même un pointeur (à l'aide

duquel on pourra créer dynamiquement une autre structure qui elle-même contient un pointeur, etc …)


Exemple

struct ent {int valeur;struct ent * suivant;};

struct ent * p1;p1=NULL;p1 = (struct ent *) malloc(sizeof(struct ent));p1->valeur=1; p1->suivant= (struct ent *) malloc(sizeof(struct ent));p1->suivant->valeur=2;p1->suivant->suivant= (struct ent *) malloc(sizeof(struct ent));…..


p1=NULL; /*1*/p1 = (struct ent *) malloc(sizeof(struct ent)); /*2*/p1->valeur=1; /*3*/p1->suivant= (struct ent *) malloc(sizeof(struct ent)); /*4*/p1->suivant->valeur=2; /*5*/p1->suivant->suivant= (struct ent *) malloc(sizeof(struct ent)); /*6*/…..

p1 p1 p1 1

p1 1 p1 1

2

p1 1

2

valeur suivant


p1 1

2

Les valeurs sont accessibles par :p1->valeurp1->suivant->valeurp1->suivant->suivant->valeur

Pb1 : on doit connaitre le nombre de (->suivant) au moment de l'écriture du pgm !!

Pb2 : quand doit on s'arrêter ?rep : le dernier membre suivant doit être NULL.


struct ent {int valeur;struct ent * suivant;};

struct ent * p1;p1 = (struct ent *) malloc(sizeof(struct ent));

Syntaxe équivalente plus commodetypedef struct ent element, *pt ; //element et pt sont des typesstruct ent {

int valeur;pt suivant;};

pt p1;p1 = (pt) malloc(sizeof(element);

ListesCréation d'une liste contenant les n premiers entierspt deb =NULL; pt paux;for(i=1;i<=n;i++) {

paux= (pt) malloc (sizeof(element));paux->valeur = i;paux->suiv=deb;deb=paux;

}

Parcours des éléments de la listepaux=deb; // on prend un pointeur auxiliaire pour ne pas perdre l'adresse de début de la liste

while(paux!=NULL) {printf("%d",paux->valeur);paux=paux->suiv;

}Attention: ne jamais perdre l'adresse du début de la liste

Listes : exemples de fonction

Fonction ajoutant une donnée en début de liste

void ajoutdeb (pt * d; int data) { // doit être appelée avec le pointeur de début de la liste ex : ajout(&deb,56)pt paux;paux =(pt) malloc(sizeof(element));paux->valeur=data;paux->suiv=*d;*d=paux;}


Fonction ajoutant une donnée en fin de listevoid ajoutfin (pt * d; int data) {// appelée avec le pointeur de début de la liste Ex : ajoutfin(&L,42);pt paux,paux2;paux=(pt) malloc(sizeof(element));paux->valeur=data; `//attention priorité des opérateurspaux->suiv=NULL;if(*d==NULL) *d=paux; // cas d'une liste initialement videelse { // autres cas

paux2=*d;while(paux2->suiv!=NULL) paux2=paux2->suiv;paux2->suiv=paux;}

}


Fonction retournant l'adresse d'une donnée présente dans la listept adresse1(pt d; int data) { // doit être appelée avec le pointeur de début de la liste p=adresse2 (L,42);while(d->valeur!=data) d=d->suiv;return(d);}

Fonction retournant l'adresse d'une donnée dont on ne sait si elle est présente ou pas dans la liste (dans ce cas, la fonction renvoie NULL)

pt adresse2(pt d; int data) { // doit être appelée avec le pointeur de début de la liste ex: p=adresse2 (L,42);while(d!=NULL)

if(d->valeur==data) return(d);else d=d->suiv;

return(NULL);}


Fonction supprimant la listept detruit (pt * d) { // doit être appelée avec le pointeur de début de la listewhile (*d!=NULL) {

paux=*d;*d=(*d)->suiv;free(paux);}

}

Fonction supprimant une donnée dans la listevoid detruit (pt * d, int data) { // doit être appelée avec le pointeur de début de la liste ex: detruit (&L,42);pt p,prec;prec=NULLp=*d;while (p!=NULL) {

if (p->valeur!=data) { //on avance dans la listeprec=p;p=p->suiv;}else { //on a trouvé l'élément à supprimer if(prec!=NULL) prec->suiv=p->suiv;else *d =(*d)->suiv;free(p);return;}}}


*d

datap

prec

Traitement récursif des listes chaînées :

• Le traitement itératif des listes est peu commode. Par exemple pour insérer un élément dans une liste il faut repérer l'adresse de l'élément précédent dans la liste. Même problème lorsque on veut retirer un élément de la liste

• Idée : considérer une liste L comme L = x + L' ou x est le premier élément de la liste et L' est la liste L privée du premier élément.

• L'adresse de x est connue c'est celle du début de la liste, celle de L' également.

• Pour le traitement récursif :• 1) cas triviaux : lorsque la liste est vide• 2) décomposition : L = x + L' . Appliquer une traitement à L revient à

l'appliquer soit sur l'élément à x , soit à L'

Traitement récursif des listes chaînées :

• On suppose dans la suite que les listes sont déclarées de la façon suivante :

typedef struct {int data;pt suiv;} elementliste, *pt;

• chaque liste est déclarée par un pointeur sur son premier

élémentpt L=NULL;

Affichage d'un liste L dans l'ordre de ses éléments :

• cas trivial : si L est vide, ne rien faire• décomposition : Afficher un liste L = 1/ imprimer x

2/ Afficher la liste L'

• Implantation en langage Cvoid affiche (pt L) { if (L) { printf(("%d"\n",L->data);

affiche (L->suiv);}

}

Affichage d'un liste L dans l'ordre inverse de ses éléments :

• cas trivial : si L est vide, ne rien faire• décomposition :

Afficher un liste L = Afficher la liste L'imprimer x

• Implantation en langage Cvoid affiche (pt L) {

if (L) {affiche (L->suiv);printf(("%d"\n",L->data);}

}

Retrait d'une donnée d d'une liste

• Cas trivial : si L est vide ne rien faire. • Décomposition : Retirer de L = si x = d remplacer L par L'

sinon Retirer d de L' -> L".faire L = x + L"

• Implantation en langage Cvoid retrait (pt * L, int d) {pt p;if (L) {

if (d == (*L)->data) { /* element à retirer en début de liste */ p = *L;*L = (*L) ->suiv; free(p); };else /* element à retirer dans L' */retrait ( &((*L)->suiv), d);

}• remarque : l'appel récursif se faisant avec l'adresse du champ suivant qui est

modifié, il y reconstruction de la liste L c-à-d L = x + L"

Ajout d'une donnée dans une liste de façon que les éléments soient rangés en ordre

croissant • Cas trivial : Si L est vide ajouter d en début de liste• Décomposition :Ajouter d à sa bonne place dans la liste L

Si d < x , ajouter d en tête de liste LSinon Ajouter d à sa bonne place dans la liste L' -> L"L = x + L"

void ajout2 (pt * L) {pt p;if (!(*L)) {p = (pt) malloc (sizeof(elementliste)); // cas liste vide

p->data=d;p->suiv= (*L);*L = p;};

else {if (x < (*L)->data ) { /* ajout en début */p = (pt) malloc (sizeof(elementliste));p->data=d;p->suiv= (*L);*L = p;};else ajout2 (&((*L)->suiv), d);}

}

Documents

Types de données et représentation