Tablouri

Obiectivele laboratorului sunt urmatoarele:

prezentarea tablourilor (unidimensionale si multidimensionale) si a constantelor de tip tablou;

prezentarea pointer-ilor;

alocarea dinamica de memorie, operatorul sizeof;

prezentarea relatiei dintre tablouri si pointeri, aritmetica pointerilor;

Tablouri

Un tablou de elemente reprezinta o structura de date alcatuita din mai multe variabile din acelasi tip de date

Tablouri unidimensionale

Tablourile unidimensionale sunt alcatuite dintr-un grup de elemente de acelasi tip (numit tip de baza) si sunt referite printr-un nume comun. Tablourile sunt stocate in memorie la locatii consecutive, un tablou ocupand o zona contigua de memorie, cu primul element al tabloului aflat la adresa cea mai mica.

Variabilele de tip tablou se definesc astfel:

nume_tip nume_var[dimensiune];

Exemplu de declaratie de tablou:

int v[4]; // declararea tabloului v, care are 4 elemente

Initializarea elementelor unui tablou se poate face in urmatoarele moduri:

v[0] = 21;

v[1] = 23;

v[2] = 27;

v[3] = 12;

sau:

int v[4] = ;

In limbajul C, un tablou se poate initializa si fara dimensiune:

int d[] = ; // tabloul va avea dimensiunea 4

Daca nu se specifica dimensiunea unui tablou atunci cand se declara, compilatorul va aloca suficienta memorie pentru a pastra elementele matricei respective.

Atentie! in limbajul C numerotarea elementelor unui tablou incepe cu pozitia 0. Astfel, daca avem definitia:

int tablou[10];

atunci primul element al tabloului este tablou[0], iar ultimul element al tabloului este tablou[9].

Accesarea unui element al unui tabloului se face folosind ca index pozitia elementului. Astfel, tablou[3] va referi al 4-lea element al tabloului tablou.

Cantitatea de memorie necesara pentru memorarea unui tablou este determinata de tipul si numarul elementelor tabloului. Pentru un tablou unidimensional, cantitatea de memorie ocupata se calculeaza astfel: mem_ocupata = dimensiune_octeti * marime_tablou.

Atentie! o problema legata de tablouri este ca in C nu se face nici o verificare legata de "marginile" tabloului, astfel incat se pot accesa gresit elemente din afara tabloului. De exemplu, pentru definitia:

int tablou[10];

daca se incearca accesarea elementului tablou[15] nu se va semnala nici o eroare, returnandu-se valoarea de la o locatie de memorie aflata la o distanta de 5 locatii fata de sfarsitul tabloului, fapt ce poate duce la comportari "bizare" ale programului.

Aceeasi situatie, dar fata de inceputul tabloului, se intampla la incercarea de a accesa elementul tablou[-5].

Tablouri multidimensionale

Limbajul C ofera posibilitatea folosirii tablourilor multidimensionale. Din punct de vedere semantic, tablourile multidimensionale sunt "tablouri de tablouri".

Un tablou multidimensional se declara in modul urmator:

nume_tip nume_tablou[dim_1][dim_2].[dim_n]

Exemplu de declarare de tablou multidimensional (bidimnesional, in cazul de fata)

int matrice[3][3] // declararea unui tablou 3 x 3

Valorile elementelor unui tablou multidimensional se pot declara atunci cand se declara tabloul respectiv:

int matrice[3][3] = , , };

Se poate folosi si urmatoarea reprezentare/declarare, pentru usurarea vizualizarii continutului tabloului:

int matrice[3][3] = ,

,

}

Constante de tip tablou

Constantele de tip tablou sunt constante in care se memoreaza valorile dintr-un tablou de elemente. Forma generala a declaratiei unui tablou de constante este:

const [nume_tip] nume_tablou[dim_1][dim_n] = ;

Exemplu de constanta de tip tablou unidimensional:

const int c[3] = ;

Exemplu de constanta de tip tablou multidimensional:

const int d[2][3] = , };

Exemplu: Urmatorul program citeste de la tastatura elementele unui tablou de numere intregi si determina maximul dintre ele:

#include <stdio.h>

#define MAX 100

void main (void)

max = tab [0];

for (i = 1; i < N; i++)

printf ('Maximul este: %d n', max);

Pointeri

Dupa cum s-a vazut, limbajul C este un limbaj de nivel mediu - contine atat elemente de nivel inalt (functii, instructiuni decizionale si repetitive samd), cat si elemente de nivel scazut, apropiat de nivelul hardware. Una dintre aceste caracteristici de nivel scazut o reprezinta posibilitatea de a accesa orice adresa din memorie, prin intermediul pointerilor.

Pointerii sunt o caracteristica foarte puternica a limbajului C, dar folosirea lor poate fi si riscanta - in cazul in care se incearca accesarea unei adrese din memorie care este rezervata altei variabile, altui program, sau chiar sistemului de operare.

Ei sunt foarte mult utilizati in limbajul C datorita faptului ca, uneori, sunt singura cale de rezolvare a unor anumite probleme, dar si pentru ca folosirea lor duce la alcatuirea unui cod mai compact si mai eficient decat altul obtinut in alt mod.

Un pointer este o variabila care contine (memoreaza) o adresa din memorie, de obicei adresa unei alte variabile.

Daca o variabila contine adresa alteia, se spune ca prima este "un pointer la cea de-a doua" (sau ca indica spre cea de-a doua).

Declararea unei variabile de tip pointer are forma generala:

tip *nume;

Tipul de baza defineste tipul de variabila catre care indica pointer-ul.

Exemplu de declaratie de pointer:

int *a;

float *pf;

Prima declaratie de mai sus se citeste "a este un pointer catre o valoare de tip intreg".

Operatorii folositi in lucrul cu pointeri

Operatorii folositi in lucrul cu pointeri sunt & si *.

Operatorul & este folosit pentru returnarea adresei operandului sau. De exemplu, prin instructiunile:

int a, *b;

a = 23;

b = &a;

variabila a va avea valoarea "adresa variabilei b". Aceasta adresa NU are nici o legatura cu valoarea variabilei a. Instructiunea anterioara de atribuire se citeste "b primeste adresa lui a".

Atentie! Operatorul & poate fi aplicat doar variabilelor sau elementelor unui tablou, constructii ca &(x+1) si &3 fiind interzise.

Operatorul * este complementarul operatorului &. Acest operator este folosit pentru a returna continutul adresei de memorie catre care indica pointerul care ii urmeaza. De exemplu, prin instructiunea:

int a, *c;

a = *c;

variabilei a i se atribuie valoarea de la adresa de memorie catre care indica c. Aceasta instructiune se citeste 'a primeste valoarea din locatia de memorie catre care indica c'.

Atentie! uneori se poate face confuzie intre operatorul * si operatorul pentru inmultire (tot *), precum si intre operatorul & si operatorul la nivel de bit AND (notat tot &). Acesti operatori nu au nici o legatura intre ei, atat & cat si * avand prioritate fata de toti operatorii aritmetici.

Pentru a intelege mai bine complementarea celor doi operatori, consideram secventa:

int a, b, *p;

p = &b;

a = *p;

Aceasta secventa este echivalenta cu atribuirea:

a = b;

Atentie! Este sarcina programatorului sa se asigure ca la adresa indicata de un pointer se afla o variabila de tipul dorit, atunci cand se acceseaza valoarea respectivei locatii. De exemplu, atunci cand se declara un pointer ca fiind de tip int, compilatorul se asteapta ca la adresa pe care o contine pointer-ul respectiv se afla o variabila de tip intreg, chiar daca acest lucru nu este adevarat.

Exemplu de program:

void main (void)

Afisarea adresei unei variabile se poate face folosind sirul de formatare %p:

void main (void)

Erori intalnite frecvent in folosirea pointer-ilor

Exista cateva erori frecvent intalnite in folosirea pointer-ilor, care pot duce la comportari nedorite a programelor.

Principala problema intalnita in folosirea pointer-ilor este folosirea pointerilor neinitializati. Consideram urmatorul exemplu:

void main (void)

In exemplul de mai sus se atribuie valoarea 23 unei locatii de memorie necunoscute.

Presupunerea incorecta asupra amplasarii variabilelor in memorie este o alta eroare destul de intalnita in lucrul cu pointeri. In general nu se poate cunoaste cu exactitate amplasarea datelor in memoria calculatorului sau daca vor fi amplasate in aceeasi ordine sau locatie dupa fiecare executare a unui program.

Exemplu:

#include <stdio.h>

void main (void)

Alocarea dinamica de memorie

In practica pot exista multe situatii in care nu se poate determina cantitatea de memorie necesara unui program in momentul compilarii acestuia, ci doar in momentul executiei (ex. numarul de elemente ale unui tablou care reprezinta o baza de date). In aceste situatii, se poate apela la mecanismele alocarii dinamice de memorie, in timpul executiei programelor, doar atunci cand este necesar si cand se cunoaste dimensiunea zonei de memorie dorita.

Operator sizeof ()

Functiile pentru alocarea dinamica de memorie necesita specificarea dimensii in octeti a zonei care se doreste alocata,. Pentru a simplifica utilizarea acestora, limbajul C pune la dispozitia programatorilor operatorul sizeof, care determina dimensiunea in octeti a unei variabile sau tip de date.

Exemplu de folosire al operatorului sizeof ():

int dim;

float x;

dim = sizeof (x);

/* echivalent cu */

dim = sizeof (float);

Dimensiunile in octeti ale principalelor tipuri de date sunt:

Spre exemplu, declaratia:

double a;

determina alocarea unei zone de memorie de 8 octeti, pentru memorarea valorii variabilei a.

Functii folosite in alocarea dinamica de memorie

Cele mai importante functii folosite pentru alocarea dinamica de memorie sunt malloc () si free (). Pentru folosirea acestor functii e nevoie de includerea fisierului header stdlib.h

Functia malloc () este folosita pentru alocarea dinamica a memoriei. Prototipul functiei este:

void *malloc (size_t nr_oct)

size_t este un tip de date folosit pentru exprimarea dimensiunilor zonelor de memorie, echivalent cu un unsigned int.

Functia malloc () returneaza un pointer (de tip void) catre primul octet al regiunii de memorie alocate. Daca nu exista suficienta memorie disponibila pentru a putea fi alocata, functia malloc () va returna valoarea 0 (sau NULL - macrodefinitie echivalenta cu un pointer care indica spre adresa zero, rezervata de obicei sistemului de operare).

Exemplu de alocare de memorie:

int *ex;

ex = malloc (1024); /* aloca 1024 de octeti */

Functia free () este complementara functiei malloc (), rolul ei fiind de a elibera memoria care a fost alocata (prin folosirea functiei malloc ()).

Prototipul functiei free () este:

void free (void *p);

Pointerul p indica spre o zona de memorie care a fost alocata anterior folosind functia malloc (). Functia free () nu trebuie apelata cu un argument care nu a fost returnat de functia malloc (), deoarece aceasta operatie poate duce la distrugerea listei de memorie disponibila.

Exemplu de folosire a functiilor malloc () si free ():

void main (void)

Relatia dintre tablouri si pointeri. Aritmetica pointerilor

In limbajul C exista o legatura foarte stransa intre tablouri si pointeri. Datorita acestei relatii se pot scrie programe mult mai eficiente si se pot accesa si folosi mult mai eficient tablourile.

Numele unei variabile de tip tablou reprezinta un pointer catre primul element al tabloului:

int a

int *p;

*a = 123; /* echivalent cu: a [0] = 123; */

p = a;    /* atribuirea este corecta si permisa */

2) Orice zona de memorie adresata printr-un pointer permite utilizarea indexarii pentru accesarea elementelor:

int *b;

b = malloc (10 * sizeof (int));

/* accesarea celui de-al treilea element */

b [3] = 23;

Aritmetica pointerilor

In limbajul C exista doua operatii aritmetice care se pot efectua cu pointeri: adunare si scadere.

Prin incrementarea unui pointer, se avanseaza pointerul spre o adresa superioara in memorie, avansandu-se cu dimensiunea in octeti a tipului de baza al pointerului respectiv. Pentru decrementare se procedeaza in mod analog.

int *p;

int tab [10];

p = tab;

printf ('Primul element este la adresa %p n', p);

p = p + 1; /* SAU p++ */

printf ('Urmatorul element este la adresa %p n ', p);   

Se observa ca cele doua adrese afisate difera prin doi octeti, dimensiunea tipului int.

Exemplu: Aritmetica pointerilor se poate utiliza pentru a creste viteza de executie a unui program:

int tab [10], i;

for (i = 0; i < 10; i++)

tab[i] = 0;

La fiecare accesare    a unui element din tablou, procesorul face urmatoarele operatii:

*(tab + i * sizeof (int)) = 0;

Inmultirea care apare in paranteze este o operatie costisitoare ca timp de executie, astfel incat daca se acceseaza succesiv elementele unui tablou, e mai rapida metoda:

int tab [10], *p, *sfarsit;

sfarsit = &tab[9];

for (p = tab; p < sfarsit; p++)

*p = 0;

Castigul de viteza provine din faptul ca incrementarea unei valori (adresa indicata de p) este mult mai rapida decat o adunare si o inmultire.

Compararea pointerilor

Folosind o expresie relationala se pot compara doi pointeri, pentru a se verifica adresa de memorie indicata de cei doi pointeri:

Exemplu:

int *a;

int *b;

if (a < b)

printf ('a indica spre o adresa mai mica decat b

Exemplu: Programul urmator utilizeaza alocarea dinamica de memorie si aritmetica pointerilor pentru a determina suma unui sir de numere dat de la tastatura:

#include <stdio.h>

#include <stdlib.h>

void main (void)

Exemplu: Programul urmator citeste un sir de numere de la tastatura si le afiseaza ordonate crescator, utilizand algoritmul bubblesort:

#include <stdio.h>

#include <stdlib.h>

#define MAX 100

void main (void)

}

while (!ordonat);

printf ('Sirul ordonat crescator este: n');

for (k = 0; k < N; k++)

printf ('%d n', tab[k]);

Probleme propuse:

1. Sa se scrie un program in C care, folosind un meniu, sa citeasca de la tastatura doua matrici patratice de numere intregi, de dimensiune specificata de utilizator si sa afiseze suma celor doua matrici.
2. Sa se scrie un program care sa implementeze o structura de tip stiva utilizand un tablou. Programul trebuie sa aiba un meniu cu 3 optiuni:

1) Depunere in stiva,

2) Extragere din stiva,

3) Iesire;

3. Sa se scrie un program in C care sa citeasca de la tastatura doua matrici patratice de numere intregi, de dimensiune specificata de utilizator si sa afiseze produsul celor doua matrici.