Tableaux, pointeurs, allocation dynamique 11 février 2013 Struct Tableaux et Matrices Pointeurs Rappels Vision abstraite : > Un pointeur est une variable
Previous PDF | Next PDF |
[PDF] Rappels : Tableaux et Matrices - IGM
Tableaux, pointeurs, allocation dynamique 11 février 2013 Struct Tableaux et Matrices Pointeurs Rappels Vision abstraite : > Un pointeur est une variable
[PDF] Rappels de calcul matriciel
LES MATRICES PREMIERES DEFINITIONS 1 1 Définition Une matrice A(n, p) est un tableau rectangulaire de nombres comprenant n lignes et p colonnes
[PDF] Rappels de calcul matriciel - Ousmane THIARE
16 avr 2020 · Définition et notation Matrices Définition Une matrice de format (m, n) à coefficients dans K est un tableau de m × n éléments de K organisés
[PDF] Chapitre I: Rappel sur le calcul matriciel 1 Définitions 2 Matrice
- Matrice : une matrice est un tableau de chiffres rangés en lignes et en colonnes Exemple : │ ⌋ ⌉ │ ⌊ ⌈ 23
[PDF] Algorithmique (suite) - LaBRI
T est une variable de type tableau d'entiers à deux dimensions T peut être vue comme une matrice à 3 lignes Rappel : T2 est la matrice inverse de
Tableaux et tris - I3 - Algorithmique et programmation - Moodle INSA
Rappels Tableaux `a n dimensions Initiation aux tris Tableaux et tris ainsi de représenter par exemple des matrices `a deux dimensions) On déclare une
[PDF] Rappel: les fonctions
Un tableau est une variable structurée • L'objet mathématique qui y ressemble est la matrice (à X dimensions) ou le vecteur a 1D Indice ou éléments dimension
[PDF] Matrices - Maths-francefr
2 1 Définition de la matrice d'une famille de vecteurs dans une base (rappel) K est un tableau à n lignes et p colonnes et donc à np cases, chaque case
[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] Exercices d 'algorithmique en seconde Probabilités #8211 statistiques
[PDF] simulations, algorithmes en probabilités et statistique(s) au - Apmep
[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] Algorithmique en classe de première avec AlgoBox - Xm1 Math
[PDF] Algorithme U prend la valeur [expression de la suite - Maths en ligne
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 coursCe 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 MatricesPointeursRappels :
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´eclarationtypenomTab[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; i20; i++)
tab2[i]="a"+i; Struct6/32Tableaux et MatricesPointeursParcourir un tableauEn 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;iStruct8/32
Tableaux et MatricesPointeursExemple
void afficheTab(int tab[], int lgTab){ int i; for(i=0;iT 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 41 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 MatricesPointeursPointeurs
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 - suite2 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 ypiz1. 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/32Tableaux 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
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 *)malloc1000*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
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;iTableaux et MatricesPointeursLe cas des chaˆınes de caract`eres#include
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
Struct31/32Tableaux et MatricesPointeursChaˆınes de caract`eres - suite#include
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 positionde la 1ere occurrence ou de la derni`ere occurrence (strrchr).Variantes avec la longueur :strncpy,strncat,strncmp, ...Struct32/32
quotesdbs_dbs22.pdfusesText_28