1

Seminar 2 Alocare dinamica Subprograme. 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.

2

- 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 i

printf("%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 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++ 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 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

3

II. Probleme pointeri cu vectori si matrice

1. Scriei un program C care s nmuleasc 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:

Dati scalarul:2

Dati dimens vector:3

p[0]=1

p[1]=2

p[2]=3

Rezultat:

p[0]=2

p[1]=4

p[2]=6

Dati dimens linii:2

Dati dimens col:2

p[0][0]=1

p[0][1]=1

p[1][0]=1

p[1][1]=1

Rezultat:

p[0][0]=2 p[0][1]=2

p[1][0]=2 p[1][1]=2

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

4

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);

- 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);

5

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:

Dati dimens linii:3

Dati dimens col:3

Dati numarul coloanei de sters:1

matrice alocata dinamic

p[0][0]=1

p[0][1]=2

p[0][2]=3

p[1][0]=4

p[1][1]=5

p[1][2]=6

p[2][0]=7

p[2][1]=8

p[2][2]=9

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

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

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

Rezultat

p[0][0]=1 p[0][1]=3

p[1][0]=4 p[1][1]=6

p[2][0]=7 p[2][1]=9

Indicatii: 1.biblioteci 2.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

6

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

p[0][0]= 1

p[0][1]= 2

p[0][2]= 3

p[1][0]= 4

p[1][1]= 5

p[1][2]= 6

p[2][0]= 1

p[2][1]= 2

p[2][2]= 3

Citire vector

p[0]= 1

p[1]= 2

p[2]= 3

Rezultat:

p[0]= 0

p[1]= 2

Indicatii:

1. biblioteci

2. 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 egali int 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

(*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 functii

In 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 numeric

Numarul de elemente(

float suma(float *v, int n) {int i; float s=0; return (s);}

- Media elementelor vectorului

float 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 rdcinilor reale ale unei ecuaii algebrice se utilizeaz mai multe metode numerice dintre care amintim: metoda biseciei (bipartiiei), metoda aproximaiilor 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.013072

Introduceti limitele intervalului:

-10

10

Eroarea admisa: 0.01

Numarul de iteratii: 1000

Solutia aproximativa este: -2.822266

Indicatii program

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

//prototipul functiei bisectie

void 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

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

Condiia de convergen a irului, spre soluia ecuaiei, este dat de relaia

Pentru convergena metodei Newton - Raphson este necesar ca .

Formula Newton - Raphson poate fi scris i pentru ecuaia implicit astfel :

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

iar condiiile de convergen se transcriu: 1. Soluia de start s fie ct mai aproape de soluia ecuaiei, f(x)s fie ct mai mic; 2. f''(x) s fie ct mai mic; 3. f' (x) s fie ct mai deprtat de zero.

Funcia are ca parametri de intrare soluia iniial (x0), numrul maxim de iteraii (n), precizia cerut (eps), valoarea minim a tangentei (eps2), funcia asociat ecuaiei (f), derivata funciei asociate ecuaiei (fd), derivata funciei de iteraie (gd) i adresa unde se va nscrie soluia. Funcia returneaz prin numele su un cod cu urmtoarea semnificaie: 0 nu s-a gsit soluie datorit numrului prea mic de iteraii; 1 nu s-a gsit soluie datorit anulrii derivatei funciei asociate ecuaiei; 2 nu s-a gsit soluie deoarece metoda nu este convergent pentru datele primite; 3 s-a gsit soluie 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))1) cod=2;

else {*x=x0-(*f)(x0)/(*fd)(x0);

if(fabs(*x-x0)

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