Structures de données et langage C

Algorithmique, Structures de données et langage C

Pointeurs generiques
En C, les pointeurs comme les autres variables sont types. Par exemple un pointeur d’entiers: int *p est di erent d’un pointeur de reels float *p m^eme si chacun d’entre eux contient une adresse en memoire. Ceci permet au compilateur de conna^tre le type de la valeur pointee et de la recuperer (c’est l’operation de dereferencement).
C ne permet les a ectations entre pointeurs que si ceux-ci sont de m^eme type. Pour ecrire des fonctions independantes d’un type particulier (par exemple une fonction de permutation) le mecanisme de typage peut ^etre contourne en utilisant des pointeurs generiques. Pour creer un pointeur generique en C, il faut le declarer de type void*.
Copie de zones memoires
L’utilisation de pointeurs generiques ne permet pas d’utiliser l’operateur de dereferencement * et donc d’acceder au contenu d’une variable. Ceci pose un probleme si l’on veut copier des donnees d’une variable designee par un pointeur generique vers une autre.
La librairie string.h fournit une fonction qui permet de resoudre ce probleme: 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.
Exemple
Si l’on n’utilise pas des pointeurs generiques, il faut ecrire autant de versions de la fonction permutation que de types de variables a 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;
}
et pour des reels:
void permut_float(float *p_a, float *p_b)
{
float c;
c=*p_a;
*p_a=*p_b;
*p_b=c;
}
Que l’on utilisera de la maniere suivante:
int i=2,j=3;
float x=3.4,y=6.5;
permut_int(&i,&j);
permut_float(&x, &y);
L3 IUP AISEM/ICM Algorithmique et langage C J.M. ENJALBERT
Pour pouvoir utiliser la m^eme fonction quel que soit le type des donnees a manipuler il est necessaire de passer en parametre la taille des donnees a traiter qui depend de leurs types.
La fonction de permutation generique peut s’ecrire:
void permut(void* p_a, void* p_b, int taille)
{
void* p_c;
p_c=malloc(taille);
memcpy(p_c,p_a,taille); /* *p_c=*p_a n’est pas autorise */
memcpy(p_a,p_b,taille);
memcpy(p_b,p_c,taille);
free(p_c);
}
Que l’on pourra utiliser ainsi:
int i=2,j=3;
float x=3.4,y=6.5;
permut(&i,&j, sizeof(i));
permut(&x, &y, sizeof(x));
On rapelle que la fonction sizeof() renvoie la taille correspondant au type de la variable passee en parametre.
Remarquez que cette fonction reste valable pour des structures complexes. Par exemple:
struct complexe
{
double reel;
double imag;
};
struct complexe cx={1,2}, cy={3,4};
permut(&cx, &cy, sizeof(cx));
Pointeurs de fonctions
Les pointeurs de fonction sont des pointeurs qui, au lieu de pointer vers des donnees, pointent vers du code executable. La declaration d’un pointeur de fonction ressemble a celle d’une fonction sauf que l’identi cateur de la fonction est remplace par l’identi cateur du pointeur precede d’un asterisque (*) le tout mis entre parentheses.
Exemple:
int (* p_fonction) (int x, int y);
declare un pointeur vers une fonction de type entier necessitant deux parametres de type entier.
L’inter^et est, par exemple, de pouvoir passer en parametre d’une fonction, une autre fonction.
Utilisation:
int resultat;
int calcul(int x, int y)
{
…
L3 IUP AISEM/ICM Algorithmique et langage C J.M. ENJALBERT
}
p_fonction=calcul;
resultat=p_fonction(3,5); /* Equivalent a resultat=calcul(3,5) */
1.5.1 Exemple complet
Recherche du minimum d’une fonction monovariable y=f(x) entre 2 bornes (Algorithme plut^ot simpliste!):
#include <stdio.h>
float carre(float x)
{
return x*x;
float parabole(float x)
{
return x*x-4*x+2;;

float min_fct(float a, float b, float (* pF) (float x))
{
int i;
float pas;
float vmin;
float valeur;
pas=(b-a)/100;
vmin=pF(a);
for (i=1; i<101; i++)
{
valeur=pF(a+i*pas);
if (vmin > valeur)
vmin=valeur;
}
return vmin;
}
int main()
{
printf(« %f \n »,min_fct(-3.0,3.0,carre));
printf(« %f \n »,min_fct(-3.0,3.0,parabole));
return 0;
}
Compilation séparée et classes d’allocation de variables
Variables locales et globales
Variables locales ou internes
Les variables dites locales sont celles qui sont declarees dans un bloc (separateurs: f et g ). Elles ne sont visibles (donc utilisables) que dans ce bloc. Leur duree de vie va de l’execution du debut de bloc jusqu’a la n du bloc (variables volatiles).
Variables globales ou externes
Ce sont les variables declarees hors de tout bloc. Elles sont visibles a partir de leur de nition.
Exemple
#include <stdio.h>
double x; /* Variables globales */
int N;
double f1()
{
int N; /* variable locale qui masque la variable globale de m^eme nom */ int i; /* autre variable locale */
…
x=…; /* Utilisation de la variable globale x (deconseille) */
}
int main()
{
/* dans le main, x et N sont accessibles mais pas i */
}
De nition et declaration
La de nition d’une variable e ectue une reservation de memoire.
Ex: int N
La declaration fait reference a une de nition. Elle n’e ectue pas de reservation en memoire, la variable doit avoir ete de nie par ailleurs.
Ex: extern int N
Variables communes
Un programme C, des qu’il devient un peu important, est constitue de plusieurs chiers sources.
Le partage des variables entre les di erents chiers necessite certaines precautions.
Une variable globale commune a plusieurs chiers doit ^etre de nie dans un seul chier et declaree dans tous les chiers qui doivent y avoir acces.
Ex: chier1.c: int N; chier2.c: extern int N;
Classe d’allocations de variables
Une variable est de nie par sa classe d’allocation qui peut ^etre: extern, auto, static, register. Par defaut (sans precision) les variables sont de classe auto. Pour de nir une variable dans une autre classe, il faut le preciser en t^ete de de nition.
Le tableau suivant resume les caracteristiques de ces 4 classes.
Algorithmes
Notion d’algorithme
Un algorithme est une suite de traitements elementaires e ectues sur des donnees en vue d’ob-tenir un resultat en un nombre nis d’operations.
Traitement elementaire: traitement pouvant ^etre e ectue par un ordinateur. Notion relative. Exemple: le calcul de la racine carree d’un nombre peut ^etre considere comme elementaire en C en utilisant la bibliotheque mathematique. Il ne l’est pas pour un microcontroleur programme 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 base sur le principe
que les diviseurs communs de a et b sont les m^emes que ceux de b et r. En remplacant a par b et b par r et en divisant a nouveau, on obtient deux entiers ayant les m^emes 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 de a et de b.
 Representation des algorithmes
Un programme est la realisation d’un algorithme. Pour s’a ranchir d’un langage de program-mation particulier, di erentes techniques de representation sont utilisees.
 Pseudo langage
Permet de representer formellement un algorithme independamment de l’implementation (lan-gage). Base sur les instructions disponibles dans la plupart des langages.
Structures elementaires:
{ Entrees/Sorties: LIRE, ECRIRE
{ a ectation: X Y
{ instruction conditionnelle: SI condition ALORS instructions SINON instructions FIN SI { repetition
{ TANT QUE condition FAIRE instructions FIN TANT QUE { POUR i=0 A n FAIRE instructions FIN POUR
{ FAIRE instructions TANT QUE condition
ECRIRE F Il n’existe pas de formalisme universel. Chaque auteur a sa syntaxe particuliere.
Analyse et complexite d’un algorithme
Il existe souvent plusieurs algorithmes permetant de resoudre un m^eme probleme. Exemple: les algorithmes de tri. Le choix du meilleur algorithme implique une analyse de ses performances. En general, le critere le plus important est celui du temps necessaire a son execution. Celui ci depend le plus souvent de la quantite de donnees a traiter. Par exemple, le temps necessiare pour trier un ensemble d’objets depend du nombre d’objets.
L’etude de la complexite d’un algorithme consiste essentiellement a evaluer la dependance entre le temps d’execution et le volume de donnees 1. Les resultats s’expriment de maniere qualitative: On cherche par exemple a savoir si la complexite croit de maniere lineaire ou polynomiale avec le volume n de donnees.
1. On peut aussi s’interesser a la quantite de memoire necessaire
Par exemple, la recherche d’un element particulier dans un ensemble de n elements non tries consiste a examiner chaque element jusqu’a trouver celui que l’on cherche. Dans le meilleur cas, cela prendra une seule comparaison, dans le pire des cas, il faudra e ectuer n comparaisons. En moyenne on aura n=2 comparaisons a e ectuer.
On s’interesse en general a la complexite d’un algorithme:
{ dans le meilleur cas, { en moyenne,
{ dans le pire des cas.
On exprime la complexite d’un algorithme en ne gardant que le terme variant le plus avec n et en omettant les termes constants. Par exemple, un algorithme necessitant 100n3 + 1000n2 + 5000n + 10000 instructions elementaires sera dit de complexite O(n3 ). Un algorithme ne dependant pas du volume de donnees sera dit de complexite O(1).
En general un algorithme de complexite O(n log n) sera plus e cace qu’un algorithme de com-plexite O(n2 ) mais ceci peut n’^etre vrai que si n est assez grand. En e et la complexite mesure le comportement asymptotique d’un algorithme quand n tend vers l’in ni.