Seminar 2 – Alocare dinamicaSubprograme. Pointer spre functii

I. Pointeri – aspecte teoretice

- lucrul cu pointeri, unul dintre atuurile limbajului C/C++- folositi de obicei in lucrul cu:

- talouri - transfer al parametrilor functiilor- acces direct la memorie - si alocare dinamica a memoriei.

- pointeri de date – pointeri care contin adresa zonei de memorie a unei variabile.

-Declarare pointer: tip * variabila_pointer;

tip – tipul de baza al pointerului si care indica tipul datelor memorate la adresa continuta in variabila_pointer

Ex: int * p;char * s;p - pointer cu tipul de baza int => contine adresa unei zone de memorie la care este memorat un numar intreg (de tip int).s – pointer cu tipul de baza char => contine adresa unei zone de memorie la care este memorat un caracter.

-pointer generic - un pointer cu tipul de baza “void” (void *).

-Atentie: -> precizarea tipului de baza al pointerului este necesara. -> adresa unei zone de memorie este de fapt adresa de baza primului octet din zona respective (o valoare

numerica). Indicand tipul de baza la pointerului, se poate determina, in primul rand, dimensiunea zonei de memorie a carei adresa este memorata in pointer( de exp. 2 octeti pentru int*, 1 octet pentru char*, 4 octeti pentru long int*).

-NULL – constanta pointer speciala, reprezinta faptul ca “pointerul nu contine adresa nici unei zone de memorie”. Valoarea acestei constante este 0.

-Operatii cu pointeri

a) operatia de referentiere – operatia prin care putem obtine adresa de memorie a unei variabile. - rezultatul operatiei este un pointer care are ca valoare adresa primului octet al

zonei de memorie in care este stocata variabila - referentierea unei variabile se realizeaza utilizand operatorul unar & (numit

operatorul de referentiere sau operatorul adresa) -exp: &variabila

b) operatia de dereferentiere – operatie prin care putem accesa valoarea memorata intr-o zona de memorie a carei adresa de inceput este memorata intr-un pointer.

1

- dereferentierea unui pointer se realizeaza utilizand operatorul unar * (operator de dereferentiere)

- exp: *variabila_pointer (expresia are ca valoare continutul zonei de memorie a carei adresa este memorata in variabila_pointer).

Exmeplu:int i,*p; i=20; p=&i; //referentiere - atribuim pointerului p adresa variabilei iprintf("%d", *p); //dereferentiere - afisez continului zonei de memorie a carei adresa este memorata in p (valoarea 20), fara * langa p, se va afisa ceva de genul 2686788

c) incrementare si decrementare pointeri – operatori folositi: --, ++ - micsoreaza/maresc adresa memorata in pointer cu numarul de octeti

necesari pentru a memora o data de tipul de baza al pointerului (sizeof (tip)). - exp:

int * p; p++; //adresa memorata in p se mareste cu 2 octeti=sizeof (int)

char *p; p--; //adresa memorata se micsoreaza cu 1 (sizeof(char));

d) adunarea/scaderea dintre un pointer si un numar intreg – ex. p-n, p+n - adresa memorata in pointer se micsoreaza sau

mareste cu n*sizeof(tip).p+n => indica al n-lea element de tipul de baza al pointerului care urmeaza dupa adresa p;p-n => indica al n-lea element de tipul de baza al pointerului care precede elementul de la adresa p.

Legatura dintre pointeri si tablouri

Numele unui tablou este un pointer constant care are ca valoare adresa primului element din tablou.

a) Vectori – pentru “tip v[LungMax];”, avem expresiile care sunt echivalente:

Forma 1 Forma 2 Comentariuv &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 vectorv++ v[1] Elementul de pe pozitia 1

b) Matrice – o matrice este un vector de vectori, - numele sau este un pointer la prima linie din matrice- pentru “tip mat[LungMax][Lungmax];”, avem expresiile care sunt echivalente:

Forma 1 Forma 2 Forma 3 Comentariumat &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

2

II. Probleme pointeri cu vectori si matrice

1. Scrieţi un program C care să înmulţească o valoare cu un vector şi apoi cu o matrice. Se vor realiza subprograme pentru:

- alocare memorie vector- alocare memorie matrice- dezalocare memorie pentru matrice- citire vector- citire matrice- afisare vector- afisare matrice- inmultire scalar cu vector- inmultire scalar cu matrice

Exemplu:

3

Dati scalarul:2

Dati dimens vector:3p[0]=1p[1]=2p[2]=3

Rezultat:p[0]=2p[1]=4p[2]=6

Dati dimens linii:2Dati dimens col:2p[0][0]=1p[0][1]=1p[1][0]=1p[1][1]=1

Rezultat:p[0][0]=2 p[0][1]=2p[1][0]=2 p[1][1]=2

4

Indicatii:1. biblioteci: stdio.h, conio.h, malloc.h.2. functie pentru alocare memorie vector: int *alocareV (int m) { . . . }3. functie pentru alocare memorie matrice: int **alocareM (int m, int n) { . . . }4. functie pentru dezalocare memorie matrice: void dezalocMDinamic(int **m1, int m) {. . .}5. functie pentru citire vector: void citireV (int *p, int m) { . . . }6. functie pentru citire matrice: void citireMDinamic (int **m1, int m, int n) { . . . } 7. functie pentru afisare vector: void afisareV (int *p, int m) { . . . }8. functie pentru afisare matrice: void afisareMDinamic (int **m1, int m, int n) { . . . }9. functie pentru inmultire scalar cu vector:

void inmCuVectDinamic (int *p, int m, int val, int *q){ int i; for (i=0;i<m; i++) *(q+i)= val * *(p+i); }

10. functie pentru inmultire scalar cu matrice:

void inmCuMatrDinamic (int **m1, int m, int n, int val, int **m2){ int i,j; for (i=0;i<m; i++) for (j=0;j<n; j++) *(*(m2+i)+j)= val * *(*(m1+i)+j); }

11. in functia main:- se declara de tip intreg: *p1, **matr1, l, m,n, *p1_rez, **matr1_rez, scal;- se citeste scal – scalarul folosit la inmultirea cu vectorul si matricea - se citeste l – dimensiunea vectorului- se aloca memorie pentru vectorul care se va citi de la tastatura si pentru vectorul rezultat: p1=alocareV(l); p1_rez=alocareV(l);

- se citeste vecorul de la tastatura:

citireV(p1,l);

- se calculeaza produsul intre scalar si vector:

inmCuVectDinamic (p1, l, scal, p1_rez);

- se afiseaza rezultatul:

printf("Rezultat:\n"); afisareV (p1_rez, l);

- se elibereaza memoria pentru vectori:

free(p1); free(p1_rez);

5

- se citesc dimensiunile m si n ale matricei;- se aloca memorie pentru matricea citita de la tastatura si matricea rezultat:

matr1=alocareM(m,n); matr1_rez=alocareM(m,n);

- se citeste matricea de la tastatura:

citireMDinamic(matr1,m,n);

- se inmulteste scalarul cu matricea:

inmCuMatrDinamic (matr1, m, n, scal, matr1_rez); - afisare rezultat inmultire matrice cu scalar:

printf("Rezultat:\n"); afisareMDinamic (matr1_rez,m,n);

- dezalocare memorie matrice:

dezalocMDinamic (matr1,m); dezalocMDinamic (matr1_rez,m);

2. Scrieti programul C care elimina o coloana dintr-o matrice alocata dinamic (numarul coloanei este citit de la tastatura). Programul va contine subprograme pentru:- alocare memorie pentru matrice- dezalocare memorie pentru matrice- citire matrice- afisare matrice- stergere coloana din matrice

Exemplu:

6

Dati dimens linii:3Dati dimens col:3Dati numarul coloanei de sters:1matrice alocata dinamicp[0][0]=1p[0][1]=2p[0][2]=3p[1][0]=4p[1][1]=5p[1][2]=6p[2][0]=7

p[2][1]=8p[2][2]=9

p[0][0]=1 p[0][1]=2 p[0][2]=3p[1][0]=4 p[1][1]=5 p[1][2]=6p[2][0]=7 p[2][1]=8 p[2][2]=9

Rezultat p[0][0]=1 p[0][1]=3p[1][0]=4 p[1][1]=6p[2][0]=7 p[2][1]=9

Indicatii:1.biblioteci2.functie de alocare memorie pentru matrice: int **alocareM (int m, int n) { . . . }3.functie pentru dezalocare memorie: void dezalocM (int **mat, int m) { . . . }4.functie pentru citire matrice: void citireM (int **m1, int m, int n) { . . . }5.functie pentru afisare matrice : void afisareM (int **m1, int m, int n) { . . . }6.functie pentru stergere coloana din matrice:

//IN: matricea m1, dimensiunile m si n, nr coloanei de sters nrCDeSters//OUT: - void stergColoanaMatriceDinamic (int **m1, int m, int *n, int nrCDeSters) { int i,j; for (i=0;i<m;i++) for (j=nrCDeSters;j<(*n)-1;j++) *(*(m1+i)+j)= *(*(m1+i)+j+1); (*n)--; }

6.in functia main :- declarari de tip intreg: **matr1, m, n, nrC;- se citesc dimensiunile matricei - m si n;- se citeste numarul de coloana care se va sterge - nrC- se aloca memorie pentru matrice:

matr1=alocareM(m,n);

- se citeste matricea: citireM(matr1,m,n); - se afiseaza matricea (pentru cotrol):

afisareM (matr1,m,n); - se sterge coloana dorita: stergColoanaMatriceDinamic(matr1, m, &n, nrC) ; - se afiseaza matricea modificata:

afisareM (matr1,m,n);- se dezaloca memoria pentru matrice dezalocM (matr1,m);3. Scrieti programul C care sa identifice care dintre liniile unui masiv bidimensional alocat dinamic sunt egale cu un vector dat. Se vor folosi subprograme pentru:- alocare memorie vector si matrice- dezalocare memorie matrice- citire vector si matrice- afisare vector si matrice- indentificare linii egale cu un vector

Exemplu:Dati dimens linii:3 Dati dimens col:3

7

p[0][0]= 1p[0][1]= 2p[0][2]= 3p[1][0]= 4p[1][1]= 5p[1][2]= 6p[2][0]= 1p[2][1]= 2p[2][2]= 3

Citire vectorp[0]= 1p[1]= 2p[2]= 3

Rezultat:p[0]= 0p[1]= 2

8

Indicatii:1. biblioteci2. functie pentru alocare vector: int *alocareV (int m) { . . . }3. functie pentru alocare matrice: int **alocareM (int m, int n) { . . . }4.functie pentru citire vector: void citireV (int *p, int m ) { . . . }5.functie pentru citire matrice: void citireM (int **m1, int m, int n) { . . .}6.functie pentru afisare vector: void afisareV (int *p, int m) { . . . }7. functie pentru afisare matrice : void afisareM (int **m1, int m, int n) { . . . }8. functie pentru verificare daca doi vectori sunt egali. Intoarce 1 daca cei doi vectori sunt egali, sau 0 daca nu sunt egali.

//IN: vectorii p1 si p2, dimensiunea m//OUT: b = 1 daca cei doi vectori sunt egali si 0 daca nu sunt egaliint VerifVectoriEgali (int *p1, int *p2, int m) //intoarce 1 daca cei doi vectori sunt egali, 0 daca nu{ int i, b=1; for (i=0;i<m;i++) if (*(p1+i)!=*(p2+i)) {b=0; break; }return b;}

9. functia care verifica daca liniile unei matrice sunt egale cu un vector:

//IN: matricea (m1) si dimensiunile sale (m si n), vectorul v;//OUT: vectorul rez si dimensiunea sa dim_rez. In acest vector se vor pastra valorile acelor linii //egale cu vectorul dat. void VerifLiniiMatriceEgalVector (int **m1, int m, int n, int *v, int **rez, int *dim_rez)//rez e un vector cu numarul liniilor gasite egale cu vectorul dat { int i,j; *dim_rez=0; *rez = alocareV(m); for (i=0;i<m; i++) if (VerifVectoriEgali(*(m1+i),v,m)==1) { *((*rez)+*dim_rez)= i; (*dim_rez)++; } }

10. in functia main :

- declarari de tip intreg : *rez1, **matr1, m, n, dim_rez1, *vect;- se citesc dimensiunile matricei – m si n;- se aloca memorie pentru matrice:

matr1=alocareM(m,n);

- se citeste matrice: citireM(matr1,m,n);

- se aloca memoria pentru vector:

vect=alocareV(m);

- se citeste vectorul:printf("Citire vector \n");

citireV (vect,m);

- se verifica ce linii sunt identice cu vectorul citit:

VerifLiniiMatriceEgalVector (matr1, m, n, vect, &rez1, &dim_rez1);

- se afiseaza rezultatul:printf("Rezultat: \n");

afisareV(rez1, dim_rez1);

III. Pointeri spre functii

1.Teorie despre pointeri la functiiIn C, numele unei functii este un pointer care indica adresa de memorie unde incepe codul executabil

al functiei. Aceasta permite transmiterea functiilor ca parametri in subprograme precum si lucrul cu tabele de functii. Pentru acest scop, se parcurg etapele:

a) declararea unei variabile de tip procedural (pointer spre functie)tip_rezultat (*nume_var)(lista_parametri_formali);

unde:nume_var este o variabila de tip procedural si are tipul “pointer spre functie cu parametrii lista_parametri_formali si care returneaza o valoare de tipul tip_rezultat”. Lui nume_var i se poate atribui ca valoare doar numele unei functii de prototip corespunzator acestui tip:

tip_rezultat nume_f(lista_parametri_formali);

b) descrierea functiei care utilizeaza parametrul procedural:

void f(…, tip_rezultat (*nume)(lista_parametrilor_formali), …){ tip_rezultat x;

…x=(*nume)(lista_parametrilor_actuali);…

}unde nume este parametrul formal de tip procedural.

c) apelul functiei cu parametri procedurali:

tip_rezultat nume_functie(lista_parametri_formali){ …}

void main (){…

f(…, nume_functie, …);}

Atentie: a nu se confunda:- un pointer la o functie: tip_returnat (*pointer_f) ([parametri] ) - cu o functie care are ca rezultat un pointer: tip_returnat *pointer_f ([parametri])

2. Exemple

a) Exemplu cu vectori

Enunt - Fie o functie care efectueaza o prelucrare asupra unui vector. Nu se cunoaste apriori tipul prelucrarii, aceasta fiind descrisa de o alta functie primita ca parametru. Pot exista mai multe functii care descriu prelucrari diferite asupra unui vector si oricare din ele poate fi transmisa ca paramteru.Tipul prelucrarii va consta in: - suma elementelor unui vector- media elementelor vectorului

Exemplu numericNumarul de elemente(<10):5a[0]=1a[1]=2a[2]=3a[3]=4a[4]=5

Suma elementelor:Rezultatul prelucrarii este: 15.00

Media elementelor:Rezultatul prelucrarii este: 3.00

Indicatii1. Se includ bibliotecile: stdio.h, conio.h2. Se scriu functiile de prelucrare:

- Suma elementelor unui vector:float suma(float *v, int n) {int i; float s=0;… return (s);}

- Media elementelor vectoruluifloat media (float *v, int n) {int i; float m=0;…return (m);}

3. Functia “functie” foloseste parametrul procedural //pct. b - descriere functiei ce fol parametrul procedural

float functie (float vec[], int dim, float (*prelucrare)(float*, int)) { float x; x= (*prelucrare)(vec,dim); return x;

//sau return (*prelucrare)(vec,dim);}

4.In functia main:- se declara de tip intreg: i,m- se declara de tip float: vector[10]- se citeste “m” de la tastatura, numarul de elemente pentru vector (maxim 10)- se citesc de la tastatura elementele vectorului “vector”, elemente de tip float

- se apeleaza functia “functie” (afisand totodata si rezultatul pentru suma): printf("Rezultatul prelucrarii este: %5.2f\n", functie(vector,m,suma));

- se apeleaza functia “functie” (afisand totodata si rezultatul pentru medie): printf("Rezultatul prelucrarii este: %5.2f\n", functie (vector,m,media));

b. Exemplu metoda bisectiei Pentru calculul rădăcinilor reale ale unei ecuaţii algebrice se utilizează mai multe metode numerice dintre

care amintim: metoda bisecţiei (bipartiţiei), metoda aproximaţiilor succesive, metoda lui Newton - Raphson, metoda lui Lobacevski.

- enunt:

- descriere metoda (I. Rusu – Metode numerice, 2006)

- exemplu numeric pentru functia f(x)= x*x*x-3*x+14. Pentru solutia gasita mai jos f(-2.822266) este aprox. -0.013072Introduceti limitele intervalului:-10 10

Eroarea admisa: 0.01 Numarul de iteratii: 1000 Solutia aproximativa este: -2.822266

Indicatii program1. Biblioteci - stdio.h, conio.h, math.h2. Prototipuri functii (bisectie si functie pentru care se aplica metoda bisectiei)

//prototipul functiei bisectievoid bisectie (float, float, float (*f)(float), float, long, int*, float *);

/*prototipul functiei pentru care se aplica metoda bisectiei*/float fct (float);

3. In functia main:- Se declara: float a,b,eps,x; int cod; long n; float (*functie)(float);- Se citesc de la tastatura: limitele intervalului (a si b), eroarea admisa (eps), numarul de iteratii (n,

ex: scanf ("%li", &n);)- Variabila “functie” primeste valoare functiei “fct” de analizat.

functie=fct; - Se apeleaza functia bisectie:

bisectie (a, b, functie, eps, n, &cod, &x); - Se testeaza valoarea variabilei cod:

if(!cod) printf ("\n Nu se poate calcula solutia aproximativa"); else printf("\n Solutia aproximativa este: %f", x);

4. descriere functie pentru care se aplica met. bisectiei*/

float fct(float x){ return x*x*x-3*x+14;}

5. functia care implementeaza metoda bisectiei:

void bisectie(float a, float b, float (*f)(float), float eps, long n, int *cod, float *x){int gata=0;long c;

for (c=0;(c<n)&&!gata; c++){ *x=(a+b)/2; gata= fabs(*x-a)<eps; //fabs(z)= modul de z (|z|), if((*f)(*x)*(*f)(a)<0) b=*x; else a=*x;}*cod=gata;}

Exercitii pentru acasa1. Să se scrie funcţia pentru aproximarea valorii soluţiei unei ecuaţii algebrice transcendente

prin metoda tangentei.

Indicatii:Una dintre cele mai cunoscute si mai folosite tehnici de rezolvare a ecuatiilor neliniare este metoda

Newton, denumita uneori si metoda Newton-Raphson sau metoda tangentelor. Ea se deosebeste de alte metode de aproximatii succesive prin faptul ca pentru fiecare punct din sirul aproximatiilor este necesara atat evaluarea functiei f(x) ce defineste ecuatia, cat si a derivatei acesteia f '(x).

Valoarea aproximativa a radacinii exacte  se calculeaza folosind un sir de aproximatii succesive {x_0, x_1, x_2, ... } construit dupa urmatorul model. Pornind de la aproximatia x_0, curba y=f(x) este aproximata in punctul de coordonate (x_0, f(x_0)) prin tangenta la ea. Noua aproximatie x_1 se obtine la intersectia acestei tangente cu axa absciselor. Folosind pe x_1 ca aproximatie initiala, se reia procedeul, determinandu-se o noua aproximatie x_2 s.a.m.d. pana cand abaterea intre doua iteratii succesive scade sub o valoare prag

impusa: |x_(n+1) - x_n| < . Alegerea aproximatiei initiale influenteaza in buna masura procesul iterativ. (a) Daca aproximatia initiala este prea departe de solutia exacta, este posibil ca, datorita unei forme aparte a curbei y = f(x), noile aproximatii sa fie aruncate spre infinit. (b) Intr-o situatie mai fericita, procesul ramane convergent, dar sirul aproximatiilor succesive se indreapta catre o alta radacina decat cea cautata.

Conditiile de convergenta ale metodei Newton sunt relativ complexe ca forma si se refera nu numai la functia f(x), ci si la primele sale doua derivate, f '(x) si f ''(x).

METODA NEWTON-RAPHSON

Condiţia de convergenţă a şirului, spre soluţia ecuaţiei, este dată de relaţia

Pentru convergenţa metodei Newton - Raphson este necesar ca .

Formula Newton - Raphson poate fi scrisă şi pentru ecuaţia implicită astfel :

Formula mai poartă numele şi de metoda tangentei. În acest caz:

iar condiţiile de convergenţă se transcriu:1. Soluţia de start să fie cât mai aproape de soluţia ecuaţiei, f(x)să fie cât mai mic;2. f''(x) să fie cât mai mic;3. f' (x) să fie cât mai depărtat de zero.

Funcţia are ca parametri de intrare soluţia iniţială (x0), numărul maxim de iteraţii (n), precizia cerută (eps), valoarea minimă a tangentei (eps2), funcţia asociată ecuaţiei (f), derivata funcţiei asociate ecuaţiei (fd), derivata funcţiei de iteraţie (gd) şi adresa unde se va înscrie soluţia. Funcţia returnează prin numele său un cod cu următoarea semnificaţie: 0 – nu s-a găsit soluţie datorită numărului prea mic de iteraţii; 1 – nu s-a găsit soluţie datorită anulării derivatei funcţiei asociate ecuaţiei; 2 – nu s-a găsit soluţie deoarece metoda nu este convergentă pentru datele primite; 3 – s-a găsit soluţie aproximativă.

int tangenta(float x0, int n, float eps, float eps2, float (*f)(float), float (*fd)(float), float(*gd)(float), float *x){ int cod=0;while((n) && (!cod)){if(fabs((*fd)(x0))<eps2) cod=1; else if(fabs((*gd)(x0))>1) cod=2; else {*x=x0-(*f)(x0)/(*fd)(x0);if(fabs(*x-x0)<eps1) cod=3; else {x0=*x; n--;}}}return cod;}

2. Scrieti un program care aproximeaza valoarea integralei prin metoda trapezului.

Indicatie: Pentru rezolvare se determina o diviziune a intervalului [a,b]. Considerand punctele determinate de punctele diviziunii si valorile functiei f in acestea, se obtine o serie de trapeze dreptunghiulare alaturate. Suma ariilor acestor trapeze aproximeaza suprafata dintre graficul functiei si axa reala, deci valoarea integralei. Aria unui trapez dreptunghic este jumatate din produsul dintre inaltinmea trapezului si suma bazelor.

O posibila forma a a functiei este urmatoarea:

double integrala_aprox (double a. double b, double (*f)(double), int n){ double rez, s; int i; double st, dr, l; l=(b-a)/n; rez=0; for (i=0;i<n;i++)

rez= rez+(*f)(a+i*l); rez= rez+(*f)(a)/2+(*f)(b)/2; rez*=l; return rez;}

Apel:…double int_a_b; int n;double a,b; ……Int_a_b = integrala_aprox(a,b,f,n);