Post on 05-Jul-2018
transcript
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
1/33
Algoritmi si tehnici
de programare-curs 1-
1
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
2/33
Informatii generale
As. dr. Radu Mogosmogos.radu@gmail.com
Punctaj:5p examen (C)3p lucrare la seminar ( S)1p activitate seminar (S)
1p din oficiu
2
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
3/33
Tipuri dinamice de date. Pointeri 1. Introducere2. Operatori specifici3. Declarare şi iniţializare 4. Opera ţii cu pointeri5. Legătura dintre pointeri şi masive 6. Alocarea dinamică a memoriei 7. Modificatorul const8. Alocarea dinamic ă a masivelor
3
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
4/33
1. Introducere
4
Lucrul cu pointeri - unul dintre atuurile limbajului C/C++
Folositi de obicei in lucrul cu:talouri
transfer al parametrilor functiiloracces direct la memoriealocare dinamica a memoriei.
Pointeri de date – pointeri care contin adresa zonei dememorie a unei variabile.
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
5/33
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
6/33
3. Declarare şi iniţializare
6
Declarare pointer : tip * variabila_pointer;
tip – tipul de baza al pointerului si care indica tipul datelor memorate la adresacontinuta in variabila_pointer
Ex:int * p; char * s;
p - pointer cu tipul de baza int => contine adresa unei zone de memorie la care estememorat un numar intreg (de tip int).s – pointer cu tipul de baza char => contine adresa unei zone de memorie la care estememorat un caracter.
pointer generic - un pointer cu tipul de baza “void” (void *).
NULL – constanta pointer speciala, reprezinta faptul ca “pointerul nu contine adresanici unei zone de memorie”. Valoarea acestei constante este 0.
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
7/33
7
Atentie:precizarea tipului de baza al pointerului este necesara.adresa unei zone de memorie este de fapt adresa de baza aprimului octet din zona respectiva (o valoare numerica).
Indicand tipul de baza al pointerului, se poate determina,in primul rand, dimensiunea zonei de memorie a careiadresa este memorata in pointer.
De exp. :2 octeti pentru int*1 octet pentru char*4 octeti pentru long int*
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
8/33
short int *p, a, *q; short int *p; short int a; short int *q;
p = &a;
q = p;
*q = 7;
struct punct {float x,y;}* x; //sizeof (x) =4; sizeof(punct)=8
void* p;
p a q
7
8
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
9/33
Pointeri - exempleint* nume; int a; float b;
nume=&a;nume=&b; //eroare, De ce?
void *nume; int a; float b;nume=&a; nume=&b;
int a, b, c; int *nume1; void *nume2;b=5; nume1=&a; *nume1=b; c=*nume1+b; nume2=&b;
*nume2=10; //eroare - *(int *)nume2=10; //corect c=*nume2; //eroare - c=*(int *)nume2; //corect
9
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
10/33
Atribuire
Operatorul de atribuire =int *p, *q; float *r, *s;p = q;r = s;p = r; s = q; //eroareint *q; void *r;r=q;
q=(int*)r;
10
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
11/33
4. Opera ţii cu pointeri
float v[20]; float *p; p=v;Incrementare/decrementarep++; p--;
Adunarea/s căderea unui întreg p=v+5; p=p-2;
Compararea a doi vectorip?v (==, !=, >, =,
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
12/33
5. Legătura dintre pointeri şi masive
12
Numele unui tablou este un pointer constant care are ca valoare adresaprimului element din tablou.
Vectori – pentru “tip v[LungMax];”, avem expresiile care sunt echivalente:
Matrice – o matrice este un vector de vectori, numele sau este un pointer laprima linie din matrice pentru “tip mat[LungMax][Lungmax];”, avem expresiilecare sunt echivalente:
Forma 1 Forma 2 Comentariu v &v[0] Adresa primului element din vector
v+i &v[i] Adresa elementului de pe pozitia i din vector *v v[0] Primul element din vector
*(v+i) v[i] Elementul de pe pozitia i din vector *(v+1) v[1] Elementul de pe prima pozitie
Forma 1 Forma 2 Forma 3 Comentariu
mat &mat[0] Adresa primei linii din matrice
mat+i & mat [i] Adresa liniei i din matrice
* mat mat [0] &mat[0][0] Adresa primului element de pe linia 0
*(mat+i) mat [i] &mat[i][0] Adresa primului element de pe linia i
*(*(mat+i)+j) mat[i][j] Elementul de pe pozitia i si coloana j
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
13/33
5. Legătura dintre pointeri şi masive
vectoriint a[10]; int *p;p = a; p=a+6;a = p; //??
matriceint a[5][5]; int **p;p = a; //??
13
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
14/33
6. Alocarea dinamică a memoriei
Se includemalloc.h (Visual C)
Funcţii importante void* malloc(unsigned n);
void free(void* p);
Alte funcţii void* calloc(unsigned nr_elem, unsigned dim_elem);void* farmalloc(unsigned long n);
void farfree(void* p);
14
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
15/33
7. Modificatorul const
Pointer constanttip *const nume;Exemplu: char *const p=“Limbajul C”; p++; --p; //???
Poi nter la o zonă de memorie constantă tip const *nume;Exemplu: char const *p=“Limbajul C”;
*p=„J ; //???
15
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
16/33
Exemple:
1. Interpretaţi următoarele expresii: a) *++p;b) *p++;c) (*p)++;d) --*p;e) ++*--p;
16
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
17/33
Răspuns :a) *++p; //preincrementeaza pointerul si apoi extrage continutulb) *p++; extrage continutul , apoi postincrementare de pointerc) (*p)++; extrage continutul , apoi postincrementare continutd) --*p; predecrementare continute) ++*--p; predecrementare de adresa si incrementarea continutului
de la noua adresa
Not ă: *, ++, -- au aceea şi prioritate şi se asociază de ladreapta spre stânga
17
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
18/33
8 . Alocarea dinamică a masivelor (1)
Exemple: alocare vector, matrice, comp. static-dinamic1. Produs vectorial a doi vectori (fara functii)2. Suma a doua matrice (fara functii)
18
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
19/33
8 . Alocarea dinamică a masivelor (2)ExempluS ă se scrie programul care determină minimul elementelor
de pe fiecare linie dintr-o matrice. Masivele se voraloca dinamic.
#include
#include
void main(){ float **a, *min; int m,n,i,j;
printf ("m="); scanf("%d", &m);
printf ("n="); scanf("%d", &n);
//alocare matrice
a=(float**)malloc(m*sizeof(float*));for(i=0;i
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
20/33
for(i=0;i
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
21/33
Transferul masivelor
Masiv
/E
I/
static în apelator
dinamic
static
în subprogram
în apelator
în apelator
în apelator
dinamic
21
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
22/33
Transferul vectorilorI/ : v[10], n
/E: -
void sortare( int a[10], int n )
{ …
… a[i] …
}
22
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
23/33
Exemplu 1Să se calculeze produsul scalar dintre doi vectori
Rezultatul se întoarce prin numele funcţiei
float ps( float x[], float y[] , int n)
{ int i;
float prod=0;
for(i=0;i
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
24/33
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
25/33
Exemplu 2
Produs vectorial între doi vectoriToate masivele alocate staticToate masivele alocate dinamic în apelatorToate masivele alocate dinamic, rezultatul alocat în subprogram -Tema
25
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
26/33
Exemplu 2 - cont.
26
Toate masivele alocate static
void ProdusVect ( int p[10], int q[10] , int n, int pv[10] ){ int i;
for (i=0;i
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
27/33
Exemplu 2 - cont.
27
Toate masivelealocate dinamic înapelator
int *alocareV (int n){ int *p,i;
p=(int*)malloc(n*sizeof(int));return p; }
void prodVect( int *p1 , int *p2 , int m, int*pRez ){ int i;
for(i=0;i
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
28/33
Transferul matricelorI/ : a[10][10], m, n/E: -
void min( int a[][10] , int m, int n )
{ …
… a[i][j] … }
void min( int **a , int m, int n )
{ … … a[i][j] …
}
Matrice alocat ă dinamic
Matrice alocat ă static
28
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
29/33
Exemple
Produsul dintre 2 matriceToate masivele alocate staticToate masivele alocate dinamic în apelatorToate masivele alocate dinamic, rezultatul alocat în subprogramsi intors prin parametruToate masivele alocate dinamic, rezultatul alocat în subprogramsi intors prin numele func ţiei
29
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
30/33
Exemplu – alocare static ă #include
#include
void produs( float a[][10], float b[][7] , int m, int n, int p, float c[][7] ){ int i,j,k;
for (i=0;i
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
31/33
Exemplu – alocare dinamică în apelator #include
#includevoid produs( float **a, float **b, int m, int n, int p, float **c){ int i,j,k;
for (i=0;i
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
32/33
Exemplu – rez. alocat dinamic în subpr.#include#includevoid produs( float **a, float **b, int m, int n, int p, float ***c){ int i,j,k;
*c=(float**)malloc(m*sizeof(float*));for(i=0;i
8/15/2019 ATP - Curs 1-Pointeri Si Alocare Dinamica
33/33
Exemplu – rez. returnat prin numele fct.#include#includefloat** produs( float **a, float **b, int m, int n, int p){ int i,j,k; float **c;
**c=(float**)malloc(m*sizeof(float*));for(i=0;i