Structures de donnees langage c l'essentiel des concepts et pratiques pour reviser et s'entrainer
Structures de données langage c l'essentiel des concepts et pratiques pour réviser et s'entraîner
…
1.1 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ès à 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;
1.2 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.
1.3 Pointeurs typés
1.3.1 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. Cela 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.
1.3.2 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.
1.3.3 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ès 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 prope
ment dites à l’intérieur de la fonction grâce à 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âce à l’opérateur d’adressage &: permutation(&x,&y);
1.3.4 Allocation dynamique
La déclaration de variables dans la fonction main ou globalement réserve de l’espace en mémoire pour ces variables pour toute la durée de vie du programme. Elle impose par ailleurs de connaître avant le début de l’exécution l’espace nécessaire aux stockage de ces variables et en particulier la dimension des tableaux. Or dans de nombreuses applications le nombre d’éléments d’un tableau peut varier d’une exécution du programme à l’autre.
La bibliothèque stdlib fournit des fonctions qui permettent de réserver et de libérer de manière dynamique (à l’exécution) la mémoire.
La fonction qui permet de réserver de la mémoire est malloc 1 Sa syntaxe est:
void* malloc(unsigned int taille)
La fonction malloc réserve une zone de taille octets en mémoire et renvoie l’adresse du début de la zone sous forme d’un pointeur non-typé(ou NULL si l’opération n’est pas possible).
En pratique, on a besoin du type d’un pointeur pour pouvoir l’utiliser. On souhaite d’autre part ne pas avoir à préciser la taille de la mémoire en octets surtout s’il s’agit de structures. L’usage consiste donc pour réserver de la mémoire pour une variable d’un type donné à:
– Déclarer un pointeur du type voulu.
– Utiliser la fonction sizeof(type) qui renvoie la taille en octets du type passé en paramètre. – forcer malloc à renvoyer un pointeur du type désiré.
Par exemple, pour réserver de la mémoire pour un entier, on écrira:
int* entier;
entier=(int*) malloc(sizeof(int));
Ceci est surtout utilisépour des tableaux, par exemple pour un tableau de N “complexe” (cf. le paragraphe sur les structures) on écrirai:
struct complexe * tabcomp;
tabcomp=(struct complexe*) malloc(N*sizeof(struct complexe));
La fonction free() permet de libérer la mémoire précédemment réservée. Sa syntaxe est: void free(void* p)
1.4 Pointeurs génériques
En C, les pointeurs comme les autres variables sont typés. Par exemple un pointeur d’entiers: int *p est différent d’un pointeur de réels float *p même si chacun d’entre eux contient une adresse en mémoire. Ceci permet au compilateur de connaître le type de la valeur pointée et de la récupérer (c’est l’opération de dér´eférencement).
C ne permet les affectations entre pointeurs que si ceux-ci sont de même type. Pour écrire des fonctions indépendantes d’un type particulier (par exemple une fonction de permutation) le mécanisme de typage peut être contournéen utilisant des pointeurs génériques.
Pour créer un pointeur générique en C, il faut le déclarer de type void*.
1.4.1 Copie de zones mémoires
L’utilisation de pointeurs génériques ne permet pas d’utiliser l’opérateur de déréférencement * et donc d’accéder au contenu d’une variable. Ceci pose un problème si l’on veut copier des données d’une variable désignée par un pointeur générique vers une autre.
La librairie string.h fournit une fonction qui permet de résoudre ce problème: memcpy(): Syntaxe: void *memcpy(void *pa, void *pb, unsigned int N)
Copie N octets de l’adresse pb vers l’adresse pa et retourne pa. L’exemple qui suit illustre l’utilisation de cette fonction.
1.4.2 Exemple
Si l’on n’utilise pas des pointeurs génériques, il faut écrire autant de versions de la fonction permutation que de types de variables à permutter:
Pour des entiers:
void permut_int(int *p_a, int *p_b)
{
int c;
c=*p_a; *p_a=*p_b;
*p_b=c;
1
et pour des réels:
void permut_float(float *p_a, float *p_b) {
float c;
c=*p_a; *p_a=*p_b; *p_b=c;
1
Que l’on utilisera de la manière suivante:
int i=2,j=3;
float x=3.4,y=6.5;
permut_int(&i,&j); permut_float(&x, &y);
...
Chapitre 2
Algorithmes
2.1 Notion d’algorithme
Un algorithme est une suite de traitements élémentaires effectués sur des données en vue d’obtenir un résultat en un nombre finis d’opérations.
Traitement élémentaire: traitement pouvant être effectué par un ordinateur. Notion relative. Exemple: le calcul de la racine carrée d’un nombre peut être considéré comme élémentaire en C en utilisant la bibliothèque mathématique. Il ne l’est pas pour un micro contrôleurs programmé en assembleur.
Exemple: l’algorithme d’Euclide calculant le PGCD de deux entiers:
Soit la division euclidienne de a par b, a = bq+r. L’algorithme d’Euclide est basésur le principe que les diviseurs communs de a et b sont les mêmes que ceux de b et r. En remplaçant a par b et b par r et en divisant à nouveau, on obtient deux entiers ayant les mêmes diviseurs que les entiers a et b d’origine.
Finalement, on obtient deux entiers divisibles entre eux (r = 0) dont le plus petit est le PGCD deaetdeb.
2.2 Représentation des algorithmes
Un programme est la réalisation d’un algorithme. Pour s’affranchir d’un langage de programmation particulier, différentes techniques de représentation sont utilisées.
2.2.1 Pseudo langage
Permet de représenter formellement un algorithme indépendamment de l’implémentation (langage). Basé sur les instructions disponibles dans la plupart des langages.
Structures élémentaires:
– Entrées/Sorties: LIRE, ECRIRE – affectation: X ~-- Y
– instruction conditionnelle: SI condition ALORS instructions SINON instructions FIN SI – répétition
– TANT QUE condition FAIRE instructions FIN TANT QUE
– POUR i=0 A n FAIRE instructions FIN POUR – FAIRE instructions TANT QUE condition
Exemple: calculer la factorielle de N (version itérative):
LIRE N
F~--1
POUR I=1 A N FAIRE
F~--F*I
FIN POUR
ECRIRE F Il n’existe pas de formalisme universel. Chaque auteur à sa syntaxe particulière.
2.2.2 Organigramme
Un organigramme permet de représenter graphiquement un algorithme. Exemple pour le calcul de la factorielle:
Lire N
F <− 1
I <− 1
Ecrire F
FIG. 2.1 – Exemple d’organigramme
En pratique cette représentation devient vite illisible pour des problèmes complexes.
2.3 Analyse et complexité d’un algorithme
Il existe souvent plusieurs algorithmes permetant de résoudre un même problème. Exemple: les algorithmes de tri. Le choix du meilleur algorithme implique une analyse de ses performances. En général, le critère le plus important est celui du temps nécessaire à son exécution. Celui ci dépend le plus souvent de la quantité de données à traiter. Par exemple, le temps nécessaire pour trier un ensemble d’objets dépend du nombre d’objets.
L’étude de la complexité d’un algorithme consiste essentiellement à évaluer la dépendance entre le temps d’exécution et le volume de données'. Les résultats s’expriment de manière qualitative: On cherche par exemple à savoir si la complexité croit de manière linéaire ou polynomiale avec le volume n de données.
- On peut aussi s’intéresser à la quantité de mémoire nécessaire
Par exemple, la recherche d’un élément particulier dans un ensemble de n éléments non triés consiste à examiner chaque élément jusqu’àtrouver celui que l’on cherche. Dans le meilleur cas, cela prendra une seule comparaison, dans le pire des cas, il faudra effectuer n comparaisons. En moyenne on aura n/2 comparaisons à effectuer.
On s’intéresse en général a la complexité d’un algorithme:
– dans le meilleur cas, – en moyenne,
– dans le pire des cas.
On exprime la complexité d’un algorithme en ne gardant que le terme variant le plus avec n et en omettant les termes constants. Par exemple, un algorithme nécessitant 100n3 +1000n2+5000n+ 10000 instructions élémentaires sera dit de complexité O(n3). Un algorithme ne dépendant pas du volume de données sera dit de complexité O(1).
En général un algorithme de complexité O(n log n) sera plus efficace qu’un algorithme de complexité O(n2) mais ceci peut n’être vrai que si n est assez grand. En effet la complexité mesure le comportement asymptotique d’un algorithme quand n tend vers l’infini.
Le tableau suivant donne quelques exemples de complexité que l’on retrouve couramment. Soit E un ensemble de n données:
...
2.4 Récursivité
Une fonction récursive est une fonction qui s’appelle elle-même. Exemple: calcul de la factorielle d’un nombre.
Définition itérative: n! = F(n) = n(n − 1)(n − 2)...2 • 1
Ce qui donne en C:
long int fact(int N) {
long int F=1; int i;
for (i=1; i<=N; i++)
F=F*i;
return F;
}
Définition récursive: F(n) = nF(n − 1), F(0) = 1. Soit en C:
long int factr(int N)
{
if (N==0)
return 1;
else
return N*factr(N-1);
}
Si, en général, la version récursive d’un algorithme est plus élégante à écrire que sa version itérative 2, elle est cependant plus difficile à mettre au point et moins efficace en temps calcul.
Pour qu’un algorithme récursif fonctionne:
– il doit exister un cas terminal que l’on est sur de rencontrer.
– Un mécanisme de pile est par ailleurs nécessaire. Il est naturel en C dans le passage de paramètres à une fonction.
2.5 Algorithmes de tri
Il s’agit d’un problème classique (et utile) de l’algorithmique. On considère un ensemble d’éléments possédant une relation d’ordre total (Exemple: entiers, réels, caractères).
On cherche à ordonner cet ensemble dans l’ordre croissant (ou décroissant).
2.5.1 Tri par sélection Principe
Soit un ensemble de n éléments indicés de 0 à n-1. On suppose que les m premiers éléments (0 a m-1) sont triés.
On cherche la position k du plus petit élément parmi les éléments m à n-1. On le permutte avec l’élément m. L’ensemble se trouve donc trié de l’indice 0 à l’indice m.
On parcourt ainsi l’ensemble de l’élément m=0 à l’élément n-2.
Illustration
En gras, les éléments déjà triés, en italique, les éléments à permutter.
...
Algorithme
Soit à trier un tableau de N éléments (entiers), t[0] à t[N-1]
POUR m=0 a N-2 FAIRE
k ~-- p (indice du plus petit élément entre t[m] et t[N-1]) SI k différent de m ALORS permutter t[k] et t[m] FIN SI FIN POUR
Programmation en C
Le programme peut se décomposer en trois fonctions:
– une fonction de calcul de l’indice du plus petit élément entre t[m] et t[N-1], – une fonction de permutation,
– La fonction de tri proprement dite.
/* indice du plus grand élément entre m et n-1 */
int indice_min(int t[], int m, int n) {
int i;
int imin;
imin=m;
for (i=m+1; i<n; i++) if (t[i]<t[imin]) imin=i;
return imin;
}
/* permutation de 2 entiers */
void permutte(int *a, int *b)
{
int c;
c=*a; *a=*b; *b=c;
}
/* tri par selection */
void tri_selection(int t[], int n)
{
int m;
int p;
for (m=0; m<N-1; m++)
{
p=indice_min(t,m,N);
if (p!=m)
permutte(.fit[p],.fit[m]);
}
}
Analyse
Cet algorithme nécessite n2/2 comparaisons et n permutations. Pour un nombre d’éléments donné, il effectue le même nombre d’opérations que les éléments soient pratiquements déjà triés ou totalement en désordre. Sa complexité est en O(n2).
2.5.2 Tri à bulle Principe
Le principe consiste à parcourir les éléments de l’ensemble de i=0 à n-1 en permuttant les éléments consécutifs non ordonnés.
L’élément le plus grand se trouve alors en bonne position. On recommence la procédure pour l’ensemble de i=0 à n-2 sauf si aucune permutation n’a été nécessaire à l’étape précédente. Les éléments les plus grands se déplacent ainsi comme des bulles vers la droite du tableau.
2.5.3 Illustration
En italique, les deux éléments à comparer, en gras les éléments en bonne place.
...
Algorithme
k ~-- N − 1
FAIRE
POUR i=0 a J-1 FAIRE
SI t[i] > t[i+1] ALORS
permutter t[i] et t[i+1]
permutation=VRAI
FIN SI
FIN POUR
TANT QUE permutation=VRAI
Analyse
Dans le pire des cas, le nombre de comparaisons et le nombre de permutations à effectuer sont de n2/2. Dans le meilleur des cas (ensemble déjà trié), le nombre de comparaisons est de n − 1 et l’algorithme est donc de complexité linéaire.
2.5.4 Tri par insertion Principe
On prend 2 éléments et on les met dans l’ordre. On prend un troisième élément qu’on insère dans les 2 éléments déjà triés, etc..
Un élément m va être inséré dans l’ensemble déjà trié des éléments 0 à m-1. Ce qui donnera m+1 éléments triés (0 à m).
L’insertion consiste a chercher l’élément de valeur immédiatement supérieure ou égale à celle de l’élément à insérer. Soit k l’indice de cet élément, on décale les éléments k à m-1 vers k+1 à m et l’on place l’élément à insérer en position k.
Illustration
En gras, l’élément à insérer dans la partie triée du tableau.
...
3.3 Files
Dans une file, les éléments sont ajoutés en queue et supprimés en tête (First Input First Ouput).
Ils sont donc traités dans l’ordre d’arrivée. On retrouve les opérations suivantes comme pour les piles:
– ajouter: rajoute un élément en queue de file.
– supprimer: renvoie la valeur de l’élément en tête de la file et le supprime.
– vide: renvoie VRAI si et seulement si la file est vide
Les files sont utilisées, par exemple, dans les applications pilotées par évènements. Les évènements (clavier, souris, ...) sont stockés dans une file par ordre d’arrivée avant d’être traités.
On les utilise aussi pour simuler des files d’attente.
3.4 Listes
3.4.1 Généralités
Une liste est un ensemble fini d’éléments notée L = e1, e2, ..., e',, oùe1 est le premier élément, e2 le deuxième, etc... Lorsque n=0 on dit que la liste est vide.
Les listes servent à gérer un ensemble de données, un peu comme les tableaux. Elles sont cependant plus efficaces pour réaliser des opérations comme l’insertion et la suppression d’éléments. Elles utilisent par ailleurs l’allocation dynamique de mémoire et peuvent avoir une taille qui varie pendant l’éxécution. L’allocation (ou la libération) se fait élément par élément1.
Les opérations sur une liste peuvent être:
– Créer une liste
– Supprimer une liste
– Rechercher un élément particulier
– Insérer un élément (en début, en fin ou au milieu)
– Supprimer un élément particulier
– Permuter deux éléments
– Concaténer deux listes
– ...
Les listes peuvent par ailleurs être: – simplement chaînées
– doublement chaînées
– circulaires (chaînage simple ou double)
3.4.2 Listes simplement chaînées
Une liste simplement chaînée est composée d’éléments distincts liés par un simple pointeur. Chaque élément d’une liste simplement chaînée est formée de deux parties:
– un champ contenant la donnée (ou un pointeur vers celle-ci)
– un pointeur vers l’élément suivant de la liste.
Le premier élément d’une liste est sa tête, le dernier sa queue. Le pointeur du dernier élément est initialiséà une valeur sentinelle, par exemple la valeur NULL en C.
Pour accéder à un élément d’une liste simplement chaînée, on part de la tête et on passe d’un élément à l’autre à l’aide du pointeur suivant associéà chaque élément.
En pratique, les éléments étant crées par allocation dynamique, ne sont pas contigus en mémoire contrairement à un tableau. La suppression d’un élément sans précaution ne permet plus d’accéder aux éléments suivants. D’autre part, une liste simplement chainée ne peut être parcourue que dans un sens (de la tête vers la queue).
Exemple d’implémentation sous forme d’une structure en C:
struct s_element
{
int donnee;
struct s_element* suivant;
};
typedef struct s_element t_element;
3.4.3 Listes doublement chaînées
Les listes doublement chaînées sont constituées d’éléments comportant trois champs:
– un champ contenant la donnée (ou un pointeur vers celle-ci)
– un pointeur vers l’élément suivant de la liste.
– un pointeur vers l’élément précédent de la liste.
...
3.4.5 Opérations sur une liste
On ne décrira dans ce paragraphe que quelques opérations sur les listes simplement chaînées. Insertion d’un élément
L’insertion d’un élément dans une liste peut se faire:
– en tête de liste
– en queue de liste
– n’importe ou (àune position fixépar un pointeur dit courant)
L’exemple choisi est celui de l’insertion n’importe où(après l’élément référencépar le pointeur courant):
FIG. 3.4 – Insertion
Les opérations à effectuer sont (dans l’ordre!):
– allouer de la mémoire pour le nouvel élément – copier les données
– faire pointer le nouvel élément vers l’élément suivant de celui pointépar courant (vers NULL s’il n’y a pas de suivant)
– faire pointer l’élément pointépar courant vers le nouvel élément
Le cas ou la liste est vide (tete égal à NULL) doit être traitéà part. Exemple d’implémentation de la fonction d’insertion:
void insertion(t_element** tete, t_element* courant, int data) {
t_element* nouveau;
nouveau=(t_element*) malloc(sizeof(t_element)); nouveau->donnee=data;
if (courant!=NULL)
{
nouveau->suivant=courant->suivant; courant->suivant=nouveau;