[PDF] [PDF] Rappels : Tableaux et Matrices - IGM

View - Download [PDF] Rappels : Tableaux et Matrices - IGM

Previous PDF

Next PDF

Tableaux et MatricesPointeursConception de structures de donn´ees

Cours 1

Tableaux, pointeurs, allocation dynamique

11 f´evrier 2013

Struct1/32Tableaux et MatricesPointeursAvant de commencer page web du cours : http://monge.univ-mlv.fr/ ~pivoteau/STRUCT/index.html ?planning, dates d"Exam ?transparents de cours, sujets de TD ?sujets de TP, programmes, quelques corrections ?bibliographie et lien utiles7 s´eances de cours ?lundi, 10h30 - 12h30environ 14 s´eances de TD/TP ?TD en demi-groupes ?TP en quarts de groupe, `a rendre.contrˆole des connaissances : ?contrˆole continu : TPs, partiel (mi-semestre) ?exam fin de semestre ?projet (avril - juin)Struct2/32Tableaux et MatricesPointeursBut du cours

Ce n"est pas un cours de programmation!

... mˆeme si il y aura de la programmation quand mˆeme.L"objectif est d"apprendre `aCONCEV OIRdes structu res

de donn´ees et les algorithmes qui les manipulent. ... autrement dit : il faut apprendre ` ar ´efl´echir .Chaque COURS sera en partie :

de l"algorithmique(des structures de donn´ees);de l"implantationdans un langage de programmation (C);En TD : lesbases et les e xemplesfondamen taux.

En TP :

implan tationdes structures vues en cours et en TD et utilisation p ourr ´esoudrediff ´erentsprobl `emes. ?Tout ce qui est vu en TD (fini ou non) doit ˆetre su. ?Tous les TPs sont `a finir et `a rendre.Struct3/32Tableaux et MatricesPointeurs

Rappels :

Tableaux et Matrices

Struct4/32

Tableaux et MatricesPointeursTableaux statiques

?Un "objet"statiqueest un objet dont l"emplacement en m´emoire est r ´eserv´elors de la compilation (et pas ` al"ex ´ecution). ?Lataille d"un tableau statique doit donc ˆ etreconn uelors de la compilation (C Ansi) ;c"est : soit uneconstan teen ti`ere: 4, 18, 150, ... soit une constan tesym bolique : #define N 1000 ?en C 99 :variable length arrays. la taille n"a plus besoin d"ˆetre connue `a la compilation! Mais on ne peut toujours pas d´eclarer :inttab[]; ?Let ypedes ´ el´ementsdu tableau doit ˆ etresp ´ecifi´elors de la d´eclaration

typenomTab[taille];Struct5/32Tableaux et MatricesPointeursD´eclarer et initialiser un tableau (statique)

#define TAILLE 100 int i; int n=10; int tab0[n]; /* !! n n"est pas constant (ok en C 99)*/ int tab1[TAILLE]; char tab2[20]; short tab3[]={0,1,2,3,4,5,6,7,8,9};/* taille = 10 */ double tab4[]={12.2,3.0,8.1,4.777};/* taille = 4 */ char mot[]="Toto"; /* {"T","o","t","o","\0"}*/ for(i=0; i <=TAILLE-1 ; i++) tab1[i]=i*n; for(i=0; i

20; i++)

tab2[i]="a"+i; Struct6/32Tableaux et MatricesPointeursParcourir un tableau

En C, tous

les tableaux commencen t` al"ind ice0 Dans un tableau de longueurn, on peut acc´eder aux cases d"indice 0 `an-1.Une tentative d"acc`es `a une case d"indice≥nprovoquera un r´esultat al´eatoire et risque en particulier de pro voquerune segmentation fault.for(i=0;i=0;i--) printf("%d ", tab1[i]);Dans le cas d"une chaˆıne de caract`eres : soit on connaˆıt sa taille et on peut proc´eder de mˆeme; soit on utilise la sentinelle"\0"pour stopper le parcours. for(i=0; mot[i]!=" \0"; i++) putchar(mot[i]); Struct7/32Tableaux et MatricesPointeursTableaux et fonctions Attention :TABLEAU = POINTEUR!!la variablenomtableaucontient l"adresse de la premi`ere case du tableau. ?Cons´equence : un tableau pass´e en param`etre d"une fonction peut ˆetre modifi´e!! MAIS : une fonction ne peut pas renvoyer un tableau statiquecr´e´e dans cette fonction. Pourquoi? Parce que l"espace r´eserv´e (allou´e) au tableau dans la fonction est d´etruit `a la sortie de la fonction. Par contre, on peut passer en param`etre de la fonction un tableau d´ej`a d´eclar´e et le modifier.

Struct8/32

Tableaux et MatricesPointeursExemple

void afficheTab(int tab[], int lgTab){ int i; for(i=0;iMatrice =

T ableau` a2 dimensions

Matrice = Tableau dont

les cases son tdes tableaux ?comme pour un tableau classique, onindique sa taille lors de la d´eclaration(taille constante) : int matrice[2][3]; ?comme pour un tableau classique, on peut l"initialiser lors de la d´eclaration... int matrice[2][3] ={ {1 , 2 , 3},{4 , 5 , 6} }; ?... ou apr`es matrice[0][0] = 1; matrice[0][1] = 2; matrice[0][2] = 3; matrice[1][0] = 4; Struct10/32Tableaux et MatricesPointeursParcourir une matrice int i,j; int matrice[3][5]; for(i=0;i<3;i++) for(j=0;j<5;j++) matrice[i][j]=i+j;0 1 2 3 4

1 2 3 4 5

2 3 4 5 6

0 1 2 1 2 3 2 3 4 3 4 5 4 5 6 ou??Convention : typenomMatrice[nb lignes][nb colonnes]; ?matrice[i][j]→case sur la ieligne, dans la jecolonne .Struct11/32Tableaux et MatricesPointeurs

Pointeurs

Struct12/32

Tableaux et MatricesPointeursRappels

Vision abstraite :

?Un pointeur est une variable"p ointant" vers un emplacement en m´emoire.En pratique : ?Un pointeur est une variable qui contient l"adresse m´emoire d"une variable.

?Donc : pointeur = adresse m´emoire (entier).L"espace m´emoire point´e peut ˆetre allou´e :

de fa¸constatique(d´ej`a vu) : int i = 3;et pourquoi pas :int *p; int *p = &i; *p = 3;??oudynamiquement. int *q = (int *) malloc( sizeof(int) ); *q = 4; Struct13/32Tableaux et MatricesPointeursRappels - suite

2 op´erateurs sp´ecifiques :

R´ef´erencement :&donne l"adresse d"une variable, (un pointeur sur cette variable) : char c = "a";

char *p = &c; /* p est de type (char *) */D´er´ef´erencement, indirection :*donne la valeur point´ee par un

pointeur (la valeur `a l"adresse correspondante) : printf("%c", *p); /* affiche a */Exemples (Kernighan et Ritchie) : int x = 1, y = 2, z[10]; int *pi; pi = &x; y = *pi; /* y=*(&x) */ *pi = 0; pi = &z[0]; /* pi=z */

Struct14/32Tableaux et MatricesPointeurs1

x 2 ypiz 1 x 1 ypiz 0 x 1 ypiz 0 x 1 ypiz

1. pi = &x;2. y = *pi;3. *pi = 0;4. pi = &z[0];Struct15/32Tableaux et MatricesPointeursD"autres exemples

D´eclarations :

int i=6, b, *p, *pi, t[10]={0}; struct{int x, y;}*q;/* pointeur sur struct. anonyme */ int *t1[10];/* tableau de pointeurs sur entier */ int (*t2)[10];/* pointeur sur tableau d"entiers */ void *g;/* pointeur g´en´erique */Affectations et arithm´etique : pi = &i; p = t;t=p;/* NON! pas d"affectation de tableau. */*p=6;/* m´emoire non allou´ee! */ p = i; p = &t[3]; *pi += 1;/* incr´emente*pide la taille du type point´e*/ b = *t+1;/*b=t[0]+1*/ b = *(t+1);/*b=t[1]... attention aux priorit´es!*/Struct16/32 Tableaux et MatricesPointeursRappel? Priorit´es des op´erateurs Cat´egorie d"op´erateursOp´erateursAssoc.

( ) [ ] .->G→Dunaires-++--! ˜?&sizeof (type)D→Gmult., div., mod.* /%G→Daddition, soustraction+-G→Dbinaires de d´ecalage<< >>G→Drelationnels< <=> >=G→Dde comparaison== ! =G→Det binaire&G→Dou exclusif binaireˆG→Dou binaire|G→Det logique&&G→Dou logique||G→Dconditionnel?:D→Gaffectation= + =-=?= etc...D→Gvirgule,G→DStruct17/32Tableaux et MatricesPointeursvoid * et NULL

Il est possible de d´efinir un pointeur survoid, c"est-`a-dire sur quelque chose qui n"a pas de type pr´ed´efini. Un pointeur de typevoid *est un pointeur :universel, g´en´erique, polymorphe. On utilisevoid *quand on ne connait pas (`a priori) le type point´e.

?Par exemple, le type de retour demallocestvoid *.! Pas d"indirection (*), ni d"arithm´etique sur unvoid *.Un pointeur doit de pr´ef´erence ˆetre typ´e!

Il existe un pointeur qui ne pointe sur rien :

NULL int *p = NULL; Struct18/32Tableaux et MatricesPointeursPassage de param`etres par r´ef´erence En C, les param`etres des fonctions sont pass´es parvaleur. C"est uneCOPIEde la valeur de l"argument qui est manipul´ee dans la fonction : donc on ne peut pas modifier une variable pass´ee en param`etre d"une fonction. Solution :Utiliser des pointeurs sur les variables `a modifier, c-`a-d passe rles param `etrespar r ´ef´erence par exemple : void swap(int a, int b){ int tmp = a; a=b; => b=tmp; int a=1,b=2; swap(a,b); /* NON: a=1, b=2 */ swap2(&a,&b); /* OUI: a=2, b=1 */void swap2(int *a, int *b){ int tmp = *a; *a=*b; *b=tmp; Struct19/32Tableaux et MatricesPointeursPointeurs et tableaux ... mais lorsque l"on passe un tableau en param`etre d"une fonction on peut le modifier! Pourquoi? Parce que le nom du tableau est en fait un pointeur vers la premi`ere case du tableau (l"adresse de d´epart du tableau).Si on d´eclare un tableau statique et un pointeur ainsi : int tab[10]; int *p; alors l"affectation :p=&tab[0]est ´equivalente `ap=tab et*pd´esignetab[0].les crochets sont une simplification d"´ecriture : tab[i]?*(tab+i)Il existe tout de mˆeme une diff´erence entre pointeur et tableau : un nom de tableau n"est pas une variable, on ne peut donc rien affecter `a un nom de tableau, contrairement `a un pointeur :tab=palors quep = tab.Struct20/32

Tableaux et MatricesPointeursL"op´erateursizeof()L"op´erateursizeof(): Renvoie la taille en octets de l"argument

(soit un type, soit une variable ou une expression) short A; char B[5][10]; sizeof A→2sizeof B→50sizeof 4.25→8 sizeof "abcd"→5sizeof(float)→4sizeof(double)→8void fnc (int tab[]){ printf("%ld, %ld \n", sizeof(tab), sizeof(tab[0])); } int main (int argc, char *argv[]){ int t1[]={1,2,3,4,5}; int *t2= (int *)malloc(20*sizeof(int)); printf("%ld, %ld \n", sizeof(t1), sizeof(t1[0])); printf("%ld, %ld \n", sizeof(t2), sizeof(t2[0])); fnc(t1);

Struct21/32Tableaux et MatricesPointeursAllocation dynamique#include On a vu qu"allouer de la m´emoirestatiqueavait un int´erˆet limit´e.

Comment faire pour r´eserver de l"espace au moment de l"ex´ecution? ?Il faut allouer la m´emoiredynamiquement.void *malloc (sizet size); •Allouesizeoctets; •Renvoie un pointeur sur la m´emoire allou´ee; •La zone de m´emoire n"est pas initialis´ee. long *a = (long *) malloc( sizeof(long) ); int n = 100; long *tab = (long *) malloc(n * sizeof(long)); struct z{int f,g;}; struct z *p;

p=(struct z *)malloc(sizeof(struct z));/* ptr surstruct z*/Struct22/32Tableaux et MatricesPointeursAllocation dynamique - suite

void *calloc (sizet nb, sizet size); Alloue et remplit de 0 la m´emoire n´ecessaire pournb´el´ements desizeoctets; renvoie un pointeur sur la zone allou´ee. Attention, ce n"est pas la mˆeme signature quemalloc! int n = 100; long *tab = (long *) calloc(n, sizeof(long));/*nfois 0 */void *realloc (void *p, sizet size); R´eduit (ou augmente) la taille du bloc de m´emoire point´e parp `a une taille desizeoctets; conserve lessizepremiers octets `a l"adressep. Le reste de la nouvelle zone n"est pas initialis´e. int * tab; tab = (int *) calloc ( 2, sizeof(int) ); tab[0] = 33; tab[1] = 55; tab = (int *)realloc(tab, 3 * sizeof(int) ); tab[2] = 77; Struct23/32Tableaux et MatricesPointeursAllocation dynamique - suite ! Attention, il peut toujours se produire des errors lors de l"allocation dynamique de m´emoire : il faut TOUJOURS v´erifier que le pointeur retourn´e lors de l"allocation n"est pas NULL! int *tab1, *tab2; tab1 = (int *) malloc( 1000*sizeof(int) ); if( tab1 == NULL ){ fprintf(stderr,"allocation rat´ee !"); exit(EXIT_FAILURE); if( tab2 = (int *)malloc

1000*sizeof(int)

== NULL ) { fprintf(stderr,"allocation rat´ee !"); exit(EXIT_FAILURE);

Struct24/32

Tableaux et MatricesPointeursFonction pour l"allocation dynamique void alloue(int *p, int nb){ if( (p=(int *)malloc(nb*sizeof(int))) == NULL ) error("L"allocation a ´echou´e !"); void alloue2(int **p, int nb){ if( (*p=(int *)malloc(nb*sizeof(int))) == NULL ) error("L"allocation a ´echou´e !"); int *alloue3(int nb){ int *p; if((p=(int *)malloc(nb*sizeof(int)))==NULL) error("alloc. rat´ee !"); return p; int main(void){ int *tab=NULL, *tab2=NULL, *tab3=NULL; alloue(tab,1000); alloue2(&tab2,1000); tab3=alloue3(1000); Struct25/32Tableaux et MatricesPointeursLib´eration de la m´emoire La m´emoire n"´etant pas infinie, lorsqu"un emplacement m´emoire n"est plus utilis´e, il est important de lib´erer cet espace.

La fonctionvoid free( void *p ):

•lib`ere l"espace m´emoirepoint´e parp •qui a ´et´e obtenu lors d"un appel `amalloc,callocourealloc •Sinon, ou si il a d´ej`a ´et´e lib´er´e avecfree(), le comportement est ind´etermin´e. •Attention,freene met pas le pointeurp`a NULL. int i, int *tab=(int *)calloc(1000, sizeof(int)); free(tab); int *tab2; alloue2(&tab2,1000); for (i=0;i<1000;i++) *(tab2+i)=i;

afficheTab(tab,1000);/* affiche (parfois) 0 1 2 3 ... 999 */Struct27/32Tableaux et MatricesPointeursCopie de m´emoire, de tableaux#include void *memcpy (void *dest, const void *src, sizet n)

Copienoctets depuis la zone m´emoiresrcvers la zone m´emoire dest. Les deux zones ne doivent pas se chevaucher. Si c"est le cas, utiliser plutˆotmemmove.

Ces deux fonctions renvoient un pointeur surdest.

int lg=20; int t1[]={1,2,3,4,5}; int *t2=(int *)malloc(lg*sizeof(int)); if (t2==NULL) error("..."); int *t3=(int *)malloc(lg*sizeof(int)); if (t3==NULL) error("..."); for(i=0;iStruct29/32

Tableaux et MatricesPointeursLe cas des chaˆınes de caract`eres#include On a vu que les chaˆınes de caract`eres sont des tableaux, donc

des pointeurs... avec quelques subtilit´es.Attention, les chaˆınes de typechar *initialis´ees avec des" "

sont statiqu eset constantes: on ne peut pas les modifier.char s1[] = "toto"; char *s2 = "titi"; s1[0] = "x"; /* OK */s2[0] = "y"; /* NON! */ Elles peuvent ´egalement ˆetre d´eclar´ees comme deschar *et allou´ees dynamiquement (malloc(), ...). char *s3 = (char *)malloc( 5*sizeof(char) ); if (s3==NULL) error("..."); s3[0] = "t"; /* OK */printf(s3) /* NON! */

Struct30/32Tableaux et MatricesPointeursChaˆınes de caract`eres - suite#include printf,scanf:sizet strlen(const char *s);

Renvoie longueur de la chaˆıne de caract`eress, sans compter le caract`ere nul"\0"final.char *strcpy(char *dest, const char *src) Copie la chaˆıne point´ee parsrc(y compris le"\0"final) dans la chaˆıne point´ee pardest. Les 2 chaˆınes ne doivent pas se chevaucher etdestdoit ˆetre assez grande pour la copie. Renvoie un pointeur sur la chaˆınedest.char *strdup(const char *s) Renvoie un pointeur sur une nouvelle chaˆıne de caract`eres qui est dupliqu´ee depuiss. La m´emoire est obtenue parmalloc(), et peut (doit) donc ˆetre lib´er´ee. Renvoie un pointeur sur la chaˆıne dupliqu´ee, ou NULL s"il n"y avait pas assez de m´emoire.

Struct31/32Tableaux et MatricesPointeursChaˆınes de caract`eres - suite#include char *strcat(char *dest, const char *src)

Ajoute la chaˆınesrc`a la fin de la chaˆınedesten ´ecrasant le "\0"`a la fin dedest, puis en ajoutant un nouveau"\0"final. Les chaˆınes ne doivent pas se chevaucher, etdestdoit ˆetre assez

grande pour le r´esultat. Renvoie un pointeur surdest.int strcasecmp(const char *s1, const char *s2);

Compare les chaˆınes chaines1et chaines2et renvoie un entier : - n´egatif, si chaines1est inf´erieure `a chaines2; - nul, si chaines1est ´egale `a chaines2; - positif, si chaines1est sup´erieur `a chaines2.char * strchr(const char *s, int c) Recherche le caract`erecdans la chaineset renvoie la position

de la 1ere occurrence ou de la derni`ere occurrence (strrchr).Variantes avec la longueur :strncpy,strncat,strncmp, ...Struct32/32

quotesdbs_dbs22.pdfusesText_28

[PDF] N°96 - spécial mouvement intra 2016pub - Snes

[PDF] Algorithmique et programmation : les bases (Algo) Corrigé

[PDF] TP7 : le théor`eme du point fixe en action sous MATLAB

[PDF] Séance de travaux pratiques n° 1

[PDF] simulations, algorithmes en probabilités et statistique(s) au - Apmep

[PDF] Loi de Bernoulli et loi binomiale, cours, première S - MathsFG - Free

[PDF] Probabilités, simulation et algorithmique (pour TI)

[PDF] Algorithmes et programmation en Pascal TD corrigés - Limuniv-mrsfr

[PDF] Notes de cours / Algo et Python

[PDF] Algorithmique et Programmation Projet : algorithme de - DI ENS

[PDF] Score ASIA

[PDF] Un algorithme de simulation pour résoudre un problème de probabilité

[PDF] Algorithme PanaMaths

[PDF] Algorithmique en classe de première avec AlgoBox - Xm1 Math

[PDF] Algorithme U prend la valeur [expression de la suite - Maths en ligne