Cours C 4 Types structures et allocation dynamique

Cours C 4 Types structures et allocation dynamique

…

Les structures

• objets regroupant plusieurs données appelées "champs"
• à définir hors d'une fonction
• définition:

struct nom {

type_champ1 nom_champ1;

type_champ2 nom_champ2;

...

};

Les structures

• déclaration d'une variable:

struct nom_type nom_var;

struct complex { double real; double imaginary;

};

int main(int argc,char* argv[]) {

struct complex c;

c.real=1.2;

c.imaginary=6.3;

printf("%f+%f*i\n",c.real,c.imaginary);

return 0;

}

Choix des champs

• on peut mettre tout ce dont le compilateur connaît la taille
• on ne peut donc pas mettre la structure elle-même:

struct list { int value;

struct list next;

};

$>gcc -Wall -ansi struct.c

struct.c:7: champ « next » a un type incomplet

Structures récursives

• mais on peut mettre un pointeur sur la structure, car la taille des pointeurs est

connue:

struct list { int value;

struct list* next;

};

Imbrication de structures

• un champ peut être une structure:

pas d'ambiguïté car le type ne s'appelle pas id mais struct id

Imbrication de structures

• 2 structures peuvent s'appeler l'une l'autre, à condition d'utiliser des pointeurs:

struct state {

struct transition* t; char final;

};

struct transition { char letter;

struct state* dest;

struct transition* next;

};

Contraintes sur les structures

• champs organisés dans l'ordre de leur

déclarations:  struct foo { int a; char b; float c;

};

int main(int argc,char* argv[]) { struct foo f;

printf("%p < %p < %p\n", &(f.a),&(f.b),&(f.c)); return 0;

}

$>./a.out

0022FF58 < 0022FF5C < 0022FF60

  Alignement

• adresse d'une structure = adresse de son premier champ
• pour les autres champs, le compilateur fait de l'alignement pour avoir, selon l'implémentation:

– des adresses multiples de la taille des données

– des adresses multiples de la taille des pointeurs

–

000

Alignement

• taille variable suivant l'ordre des champs:

   struct ta { int a; char b; char c; char d;

}; 

struct to { char a; int b; char c; char d;

};   sizeof(to)=12    sizeof(ta)=8    

• ne jamais essayer de deviner l'adresse d'un champ ou la taille d'une structure:

– noms des champs

– sizeof

Alignement

   struct ta { int a; char b; char c; char d;

}; 

struct to { char a; int b; char c; char d;

};   sizeof(to)=12    sizeof(ta)=8

@+0

@+4

@+5

@+6

Initialisation

• struct to t={val0,val1,...,valn-1};

struct to t={'a',145,'y','u'};

• seulement lors de la déclaration

  int main(int argc,char* argv[]) {

struct to t;

t={'a',145,'y','u'};

printf("%c %d %c %c\n",t.a,t.b,t.c,t.d);

return 0;

 }

$>gcc -Wall -ansi struct.c

struct.c: Dans la fonction « main »:

struct.c:33: erreur d'analyse syntaxique avant le jeton « { »

Opérations

• l'affectation fonctionne

int main(int argc,char* argv[]) {

struct to z={'a',145,'y','u'};

struct to t=z;

printf("%c %d %c %c\n",t.a,t.b,t.c,t.d);

return 0;

}

• attention: si un champ est un pointeur, on ne copie que l'adresse
• pas d'opérateur de comparaison

b à écrire soi-même

Structures en paramètres

• les structures sont passées par valeur!

– non modifiables

– peuvent occuper beaucoup de place sur la

pile (tableaux)

– temps de recopie

• toujours les passer par adresse

Structures en paramètres

struct array { int t[100000]; int size;

};

void f(struct array* a) { int i;

for (i=0;i<(*a).size;i++) { printf("%d\n",(*a).t[i]);

}

}

attention au parenthésage: (*a).t[i] ≠ *a.t[i]

Structures en paramètres

• passage d'adresse =

– gain de temps

– gain d'espace sur la pile

– on peut modifier la structure

• notation simplifiée: (*a).size = a->size

void f(struct array* a) { int i;

for (i=0;i<(*a).size;i++) { printf("%d\n",(*a).t[i]);   void f(struct array* a) { int i;

for (i=0;isize;i++) { printf("%d\n",a->t[i]);

}   }

}   }

Retourner une structure

• on peut, mais c'est une opération de copie sur la pile
• mêmes problèmes que pour le passage par valeur
• à éviter absolument
• il faudra utiliser de l'allocation dynamique

Les unions

typeN nomN;

};

• s'utilisent comme les structures

 union toto { char a; float b;

 };

void foo(union toto* t) { t->a='z';

}

Les unions

• taille = taille du plus grand champ
• au programmeur de savoir quel champ doit être utilisé

 union toto { char a;

char s[16];   

};    $>./a.out

$oucou

int main(int argc,char* argv[]) {

union toto t;

strcpy(t.s,"coucou");

t.a='$';

printf("%s\n",t.s);

return 0;

}   

Les unions

• utiles quand on doit manipuler des informations exclusives les unes des autres
• peuvent être utilisées anonymement dans une structure

struct student {

char name[256];

union {

char login[16];

int id;

};

};

Unions complexes

• on peut mettre des structures (anonymes) dans les unions

union color {

/* RGB representation */

struct {

unsigned char red,blue,green;

};

/* 2 colors: 0=black 1=white */

char BandW;

};

on peut utiliser soit red, blue et green, soit BandW

Quel(s) champ(s) utiliser ?

• encapsulation dans une structure avec un champ d'information

struct color {

/* 0=RGB 1=black & white */

char type;

union {

/* RGB representation */

struct {

unsigned char red,blue,green;

};

/* 2 colors: 0=black 1=white */

char BandW;

};

};

Les énumérations

• enum nom {id0,id1,000,idn-1};
• si on a une variable de type enum nom,

elle pourra prendre les valeurs idi

enum gender {male,female};

void init(enum gender *g,char c) { *g=(c=='m')?male:female; }

Les énumérations

• valeurs de type int
• par défaut, commencent à 0 et vont de 1 en 1
• on peut les modifier

Les énumérations

• on peut avoir plusieurs fois la même

valeur

enum color {

blue=45, BLUE=blue, Blue=blue,

green/* =46 */, GREEN=green, Green=green

};

int main(int argc,char* argv[]) { printf("%d %d %d %d %d %d\n",

blue,BLUE,Blue,green,GREEN,Green); return 0;

}

$>./a.out

45 45 45 46 46 46

Contrôles des valeurs

• contrairement aux espoirs du programmeur, pas de contrôle!

enum gender {male='m',female='f'}; enum color {blue,red,green};

int main(int argc,char* argv[]) {

enum gender g='z';

enum color c=g;

/* ... */

return 0;

}

Contrôles des valeurs

• seul contrôle: avec -Wall, gcc indique s'il manque des cas dans un switch (quand il n'y a pas de default)

$>gcc -Wall -ansi enum.c

enum.c: Dans la fonction « foo »:

enum.c:24: AVERTISSEMENT: valeur d'énumération « green » n'est pas traitée dans le switch

enum.c:24: AVERTISSEMENT: valeur d'énumération « yellow » n'est pas traitée dans le switch

 Déclaration de constantes

• si on veut juste déclarer des constantes, on peut utiliser une énumération anonyme

enum {Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday};

char* names[]={"Monday","Tuesday","Wednesday","Thursday","Friday", "Saturday","Sunday"};

void print_day(int day) {

printf("gis\n",names[day]);

}

int main(int argc,char* argv[]) { print_day(Saturday);

return 0;

}

Combinaison union/enum

• quand on utilise une union, c'est plus propre de décrire les alternatives avec une énumération:

 enum cell_type {EMPTY,BONUS,MALUS,PLAYER,MONSTER};

 struct cell {

enum cell type type;

_

union {

Bonus bonus; Malus malus; Player player; Monster monster;

};

};

typedef

• typedef type nom;
• permet de donner un nom à un type, simple ou composé
• pratique pour éviter de recopier les mots-clés struct, union et enum

typedef signed char sbyte; typedef unsigned char ubyte;

typedef struct cell Cell; typedef enum color Color;

typedef

• pas de nouveaux types
• seulement des synonymes

interchangeables

struct array { int t[N]; int size; };

typedef struct array Array;

int main(int argc,char* argv[]) {

Array a;

struct array b=a;

/* ... */

return 0;

}

typedef

• pour les types structurés, deux modes de

définition:

 enum cell_type {EMPTY,BONUS,MALUS,

PLAYER,MONSTER};

typedef enum cell_type CellType;

struct cell {

CellType type; union {

Bonus bonus; Malus malus; Player player; Monster monster;

};

};

typedef struct cell Cell;

typedef enum {EMPTY,BONUS,MALUS, PLAYER,MONSTER} CellType;

typedef struct { CellType type; union {

Bonus bonus; Malus malus; Player player; Monster monster;

};

} Cell;

Les pointeurs

• pointeur=adresse mémoire+type
• type* nom; ~ nom pointe sur une zone mémoire correspondant au type donné
• le type peut être quelconque
• valeur spéciale rTULL équivalente à 0
• pointeur générique: vois* nom;

Arithmétique des pointeurs

• int* t -=> on peut voir t comme un tableau d'int

*t a t[0]

• l'addition et la soustraction se font en fonction de la taille des éléments du tableau

t+3 = t+3*sizeof(type des éléments)

*(t+i) <* t[i]

Arithmétique des pointeurs

• si le pointeur t pointe sur la case x du tableau, on peut le décaler sur la case

x+1 en faisant t++

int copy(char* src,char* dst) {

if (src==NULL || dst==NULL) {

return 0;

}

while ((*dst=*src)!='\0') {

src++;

dst++;

}

return 1;

}

Transtypage

• pas de problème de conversion pour:

void*

void*

• problème pour truc* ~ biniou*
• on peut chercher à voir la mémoire de façon différente, mais il faut une conversion explicite: biniou* b=...;

truc* t=(truc*)b;

Exemple

• ordre de rangement des octets en mémoire

=> voir un int comme un tableau de 4 octets

Exemple 2

• voir les octets qui composent un double

void show_bytes(double d) {

unsigned char* t=(unsigned char*)(&d);

int i;

for (i=0;i<sizeof(double);i++) {

printf("%X ",t[i]);

}

printf("\n");

}

$>./a.out 375.57898541

FA 8C 34 86 43 79 77 40

Allocation dynamique

• principe: demander une zone mémoire au système
• zone représentée par son adresse
• zone prise sur le tas
• zone persistante jusqu'à ce qu'elle soit libérée (≠ variables locales)
• void* malloc(size_t size);

(dans stdlib.h)

• size = taille en octets de la zone réclamée
• retourne la valeur spéciale rTVLL en cas d'échec ou l'adresse d'une zone au contenu indéfini sinon b penser à initialiser la zone
• toujours tester le retour de malloc
• toujours multiplier le nombre d'éléments

par la taille

• toujours mettre un cast pour indiquer le

type (facultatif, mais plus lisible)

• usage prototypique:

Cell* c=(Cell*)malloc(sizeof(Cell)); if (c==HULL) {

/* ... */

}

Allocation de tableaux

• il suffit de multiplier par le nombre

d'éléments:

int* create_array(int size) {

int* array;

array=(int*)malloc(size*sizeof(int));

if (array==HULL) {

fprintf(stderr,"Not enough memory!\n");

exit(1);

}

return array;

}

• void* calloc(size_t nmemb,size_t size);
• alloue et remplit la zone de zéros:

int* create_array(int size) {

int* array;

array=(int*)calloc(size,sizeof(int));

if (array==HULL) {

fprintf(stderr,"Not enough memory!\n");

exit(1);

}

return array;

}

• void* realloc (void* ptr,size_t size);
• réalloue la zone pointée par ptr à la nouvelle taille size

– anciennes données conservées

– ou tronquées si la taille a diminuée

• possible copie de données sous-jacente
• ptr doit pointer sur une zone valide!

Exemple de réallocation

struct array { int* data; int capacity; int current;

};

/* Adds the given value to the given array,

* enlarging it if needed */

void add_int(struct array* a,int value) {

if (a->current==a->capacity) {

a->capacity=a->capacity*2;

a->data=(int*)realloc(a->data,a->capacity*sizeof(int));

if (a->data==HULL) {

fprintf(stderr,"Not enough memory!\n");

exit(1);

}

}

a->data[a->current]=value;

(a->current)++;

}

Libération de la mémoire

• void free(void* ptr);
• libère la zone pointée par ptr
• ptr peut être à rTULL (pas d'effet)
• ptr doit pointer sur une zone valide obtenue avec malloc, calloc ou realloc
• la zone ne doit pas déjà avoir été libérée

Libération de la mémoire

• ne JAMAIS lire un pointeur sur une zone libérée
• attention aux allocations cachées: char* strdup(const char* s); (string.h)

 Libération de la mémoire

• 1 malloc = 1 free
• celui qui alloue est celui qui libère:

Allocation de structures

Utilisation de malloc

• l'allocation est coûteuse en temps et en espace
• à utiliser avec discernement (pas quand la taille d'un tableau est connue par exemple)

int main(int argc,char* argv[]) {

Complex a={2,3};

Complex b={7,4};

Complex* c=mult_Complex(&a,&b);

/* ... */

free_Complex(c);

return 0;

}

Tableaux à 2 dimensions

• = tableau de tableaux:

– allouer le tableau principal

– allouer chacun des sous-tableaux

int** init_array(int X,int Y) {

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

if (t==HULL) { /* ... */ }

int i;

for (i=0;i<X;i++) {

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

if (t[i]==HULL) { /* ... */ }

}

return t;

}

• on peut étendre à n dimensions

 Tableaux à 2 dimensions

• les éléments ne sont pas tous contigus!

≠ tableaux statiques

• les sous-tableaux ne sont pas forcément dans l'ordre

int** t de 2x3 contenant la valeur 7

43B2 44F8 4532

4532 44F8 ... 7 7 7 ... 7 7 7

• on pourrait ne faire qu'un seul malloc

 Tableaux à 2 dimensions

• libération:

– d'abord les sous-tableaux

– puis le tableau principal

• on peut étendre à n dimensions

 Listes chaînées

• chaque cellule pointe sur la suivante
• grâce à l'allocation dynamique, on peut avoir des listes arbitrairement longues double définition pour pouvoir:

1) avoir un type récursif

2) avoir un nom de type sans struct

Listes chaînées

• représentation en mémoire de la liste:

3 7 15

FB07 FB42 FBAE

• liste=adresse de son premier élément (ici FB07)

 Complexités

• attention aux complexités cachées de malloc et free (et de toutes les autres fonctions)
• si on a une fonction linéaire sur des listes mais que les malloc sont en n2, on n'aura pas un temps d'exécution linéaire