Algorithmique structures de données et langage C

Rappels et compléments de C

Structures
Une structure rassemble des variables, qui peuvent être de types différents, sous un seul nom ce qui permet de les manipuler facilement. Elle permet de simplifier l’écriture d’un programme en regroupant des données liées entre elles. Un exemple type d’utilisation d’une structure est la gestion d’un répertoire. Chaque fiche d’un répertoire contient (par exemple) le nom d’une personne, son prénom, son adresse, ses numéros de téléphone, etc… Le regroupement de toutes ces informations dans une structure permet de manipuler facilement ces fiches. Autre exemple: On peut représenter un nombre complexe à l’aide d’une structure. On définit une structure à l’aide du mot-clé: struct suivi d’un identificateur (nom de la structure) et de la liste des variables qu’elle doit contenir (type et identificateur de chaque variable). Cette liste est délimitée par des accolades. Chaque variable contenue dans la structure est appelée un champ ou un membre. Définir une structure consiste en fait à définir un nouveau type. On ne manipulera pas directement la structure de la même manière que l’on ne manipule pas un type. On pourra par contre définir des variables ayant pour type cette structure. Exemple: struct complexe { double reel; double imag; };struct complexe x,y; Dans cet exemple, on définit une structure contenant deux réels puis on déclare deux variables ayant pour type struct complexe. Les opérations permises sur une structure sont l’affectation (en considérant la structure comme un tout), la récupération de son adresse (opérateur &) et l’acc` es à ses membres. On accède a la valeur d’un membre d’une structure en faisant suivre l’identificateur de la variable de type structure par un point suivi du nom du membre auquel on souhaite accéder. Par exemple x.reel permet d’accéder au membre ’reel’ de la variable x. On peut initialiser une structure au moment de sa déclaration, par exemple: struct complexe x={10,5}; On peut définir des fonctions qui renvoie un objet de type structure. Par exemple, la fonction suivante renvoie le complexe conjugué de x: struct complexe conjugue(struct complexe x); { struct complexe y;
y.reel=x.reel; y.imag=-x.imag;
return y;
}
L’utilisation de cette fonction pourra ressembler à: struct complexe x,z;
z=conjugue(x); L’affectation revient à affecter chaque membre de la structure, par exemple: struct complexe x,z;
x=z; est équivalent à:
struct complexe x,z;
x.reel=z.reel; x.imag=z.imag;

Types synonymes

Le langage C permet de créer de nouveaux noms de types de données grace à la fonction typedef. Par exemple: typedef int longueur fait du nom longueur un synonyme de int. La déclaration: longueur l est alors équivalente à int l. Autre exemple, la déclaration typedef struct complexe comp,*p comp permet de créer deux nouveaux mot-clés: comp équivalent à struct complexe et p comp équivalent à struct complexe* (pointeur de struct complexe). Attention, un typedef ne crée pas de nouveaux types mais simplement de nouveaux noms pour des types existants.

Pointeurs typés

Présentation
A une variable correspond un emplacement mémoire caractérisé par une adresse et une longueur (par exemple 4 octets consécutifs pour un long int). C’est, bien sur, le compilateur qui assure la gestion de la mémoire et affecte à chaque variable un emplacement déterminé. On peut accéder a la valeur de cette adresse grace à l’opérateur unaire & dit opérateur d’adressage. Un pointeur est une variable d’un type spécial qui pourra contenir l’adresse d’une autre variable. On dit qu’il pointe vers cette variable. Celui-ci devra aussi connaˆıtre le type de la variable vers laquelle il pointe puisque la taille d’une variable (en octets) dépend de son type. La déclaration d’un pointeur devra donc indiquer le type d’objet vers lequel il pointe (on dit d’un pointeur qu’il est typé). La syntaxe est la suivante: type *identificateur; Par exemple, pour déclarer un pointeur vers un entier on écrira: int* p_entier; ou encore: int *p_entier;
On peut réaliser des opérations sur des pointeurs de même type. On peut en particulier affecter
à un pointeur un autre pointeur du même type ou l’adresse d’une variable de même type que celle du pointeur. On accède a la valeur stockée à l’adresse contenue dans un pointeur grace à l’opérateur unaire dit de référencement ou d’indirection: * Dans l’exemple suivant: int a; int* p_a;
p_a=&a; *p a et a font référence au même emplacement mémoire (et ont donc la même valeur). Un pointeur peut par ailleurs pointer vers un autre pointeur. On peut aussi incrémenter un pointeur. Celà revient à augmenter sa valeur de la taille de l’objet pointé et donc à pointer sur l’objet suivant du même type (s’il en existe un!). La déclaration d’un pointeur alloue un espace mémoire pour le pointeur mais pas pour l’objet pointé. Le pointeur pointe sur n’importe quoi au moment de sa déclaration. Il est conseillé d’initialiser tout pointeur avant son utilisation effective avec la valeur NULL (constante prédéfinie qui vaut 0) ce qui, par convention, indique que le pointeur ne pointe sur rien.

Pointeurs et tableaux
La déclaration d’un tableau réserve de la place en mémoire pour les éléments du tableau et fournit une constante de type pointeur qui contient l’adresse du premier élément du tableau. Cette constante est identifiée par l’identificateur donné au tableau (sans crochets). C’est cette constante de type pointeur qui va permettre de manipuler facilement un tableau en particulier pour le passer en paramètre d’une fonction puisqu’on ne passera à la fonction que l’adresse du tableau et non tous ses éléments. L’exemple suivant: int tab[10]; déclare un tableau de 10éléments. tab contient l’adresse du premier élément et donc l’expression: tab == &tab[0] est VRAIE. On a donc de même: *tab == tab[0] tab[1] == *(tab+1) tab[k] == *(tab+k) Les deux écritures sont autorisées. La différence entre un tableau et un pointeur est qu’un tableau est une constante non modifiable alors qu’un pointeur est une variable.

Passage de paramètres à une fonction
On a vu que les paramètres passés à une fonction le sont par valeur et ne peuvent pas être modifiés par l’exécution de la fonction. Ceci est tr` es contraignant si l’on souhaite qu’une fonction renvoie plusieurs résultats. Par exemple, si l’on souhaite écrire une fonction permuttant deux entiers, le code suivant qui parait correct ne fonctionnera pas:
void permutation(int a, int b) { int c;
c=a; a=b; b=c;
}
L’appel de la fonction: permutation(x,y); n’aura ainsi aucun effet sur x et sur y. La solution consiste à passer, pour les paramêtres que l’on souhaite voir modifier par la fonction, non plus les valeurs de ces paramètres mais les valeurs des adresses de ces paramètres. Les paramètres de la fonction devront donc être des pointeurs. On accèdera aux valeurs propement dites à l’intérieur de la fonction gr`ace à l’opérateur d’indirection *. Si l’on reprend l’exemple précédent, cela donne: void permutation(int* p_a, int* p_b) { int c;
c=*p_a; *p_a=b; *p_b=c;
}
Remarque: on aurait pu garder les identificateurs initiaux a et b! Et l’appel devra se faire en passant en paramètres les adresses des variables à modifier gr`ace à l’opérateur d’adressage &: permutation(&x,&y);