Capitolul 9

Siruri si pointeri

Un sir (se mai spune si vector) este o secventa de date ce contine articole de acelasi tip, indexate si memorate contiguu. De obicei, sirurile se folosesc pentru reprezentarea unui numar mare de valori omogene (in capitolul urmator vom studia sirurile de caractere). O declaratie obisnuita de sir aloca memorie incepand de la adresa de baza. Numele sirului este un pointer constant la aceasta adresa de baza.
O alta notiune pe care o vom explica este transmiterea sirurilor ca argumente in functii.

9.1 Siruri uni-dimensionale

Exemplu:

Presupunem ca vrem sa lucram cu trei intregi:
int a1, a2, a3;
Totusi, daca avem mai multe numere este anevoios sa declaram numerele in acest fel. Solutia consta in utilizarea unui sir (de lungime trei) de intregi.
int a[3];
Elementele acestui sir vor fi accesate astfel: a[0] a[1] a[2]
Deci numarul 3 reprezinta lungimea sirului, elementele sale fiind indexate incepand cu numarul 0. Aceasta este o trasatura a limbajului C.
O declaratie de sir uni-dimensional este un tip urmat de un identificator urmat la randul lui de paranteze patrate ce cuprind o expresie integrala constanta. Valoarea expresiei constante, care trebuie sa fie pozitiva, se numeste lungimea sirului si ea specifica numarul de elemente ale sirului. Pentru memorarea elementelor intr-un sir, compilatorul rezerva un spatiu de memorie corespunzator, pornind de la adresa de baza. Dimensiunea spatiului de memorie este egala cu numarul de elemente ale sirului inmultit cu numarul de octeti necesari memorarii unui element al sirului.

Exemplu:

Vom scrie un mic program care initializeaza un sir, tipareste valorile sale si insumeaza elementele sirului.

#include
#define N 5

void main()
{
int a[N]; /* aloca spatiu de memorie pentru a[0], a[1], a[2], a[3] si a[4] */
int i, suma = 0;

for (i = 0; i < N; ++i) /* initializeaza sirul */
a[i] = 7 + i * i;
for (i = 0; i < N; ++i) /* tipareste sirul */
printf("a[%d] = %d ", i, a[i]);
for (i = 0; i < N; ++i) /* insumeaza elementele sirului */
suma += a[i];
printf("\nsuma = %d\n", suma); /* tipareste suma lor */
}
Sa vedem ce se intampla in memorie ?

Deci vectorul (sirul) "a" se va memora incepand de la adresa 3A38:0FF6. Deci "a = &a[0]".
Se recomanda definirea lungimii unui sir ca o constanta simbolica (folosind directiva "#define").

9.2 Initializarea sirurilor

Sirurile pot apartine claselor de memorare "auto", "extern", "static" sau "constant", dar nu pot fi "register". Ca si variabilele simple, sirurile pot fi initializate in timpul declararii lor. Initializarea sirurilor se face folosind acolade si virgule.

Exemplu:

float x[7] = {-1.1, 0.2, 33.0, 4.4, 5.05, 0.0, 7.7};
Asta inseamna, echivalent:
x[0] = -1.1;
x[1] = 0.2;
. . . . .
x[6] = 7.7;
Daca lista de valori de initializare este mai mica decat numarul de elemente ale sirului, atunci elementele ramase se initializeaza cu 0. Daca un sir declarat "extern" sau "static" nu este initializat, atunci sistemul initializeaza toate elementele cu 0. Vectorii declarati constanti sau automatic (cei impliciti) sunt initializati cu valori "garbage" (adica cu valorile existente in momentul executiei in memorie la acele adrese). C traditional permite doar initializarea vectorilor declarati "extern" sau "static", pe cand ANSI C permite initializarea sirurilor automate si constante.
Daca un sir este declarat fara precizarea lungimii si initializat cu o serie de valori, atunci lungimea sa se considera implicit numarul de valori initiale.

Exemplu:

Declaratiile
int a[] = {3, 4, 5, 6}; si int a[4] = {3, 4, 5, 6};
sunt echivalente.

9.3 Indexul unui sir

Presupunem ca avem declaratia
int i, a[lungime];
Pentru accesarea unui element din sir, vom scrie "a[i]", sau mai general "a[expresie]", unde "expresie" este o expresie integrala. "i" de mai sus se numeste index al sirului "a" si poate avea valori intre 0 si "lungime-1". Daca indexul depaseste acest domeniu, compilatorul va da eroare in timpul executiei programului.

Exemplu:

#include
#include

void main()
{
int c, i, litera[26];

for (i = 0; i < 26; ++i) /* initializarea vectorului cu 0 */
litera[i] = 0;
while ((c = getchar()) != EOF) /* numararea literelor */
if (isupper(c))
++litera[c - 'A'];
for (i = 0; i < 26; ++i) /* tiparirea rezultatelor */
{
if (i % 6 == 0)
printf("\n");
printf("%5c:%4d", 'A' + i, litera[i]);
}
printf("\n\n");
}
Acest program citeste de la tastatura sau dintr-un fisier (folosind indirectarea) un sir de caractere si numara in vectorul "litera" fiecare aparitie (in parte) a literelor.

9.4 Relatia dintre vectori si pointeri

Am vazut ca numele unui sir (de exemplu "a") este o adresa, deci poate fi privit ca valoare a unui pointer. Deci sirurile si pointerii pot fi priviti oarecum la fel in ceea ce priveste modul cum sunt folositi pentru accesarea memoriei. Cu toate acestea, sunt cateva diferente (subtile si importante). Cum numele unui sir este o adresa fixa (particulara), atunci aceasta o putem gandi ca un pointer constant. Cand este declarat un sir, compilatorul trebuie sa aloce o adresa de baza si un spatiu suficient de memorie care trebuie sa contina toate elementele sirului. Adresa de baza a unui sir este locatia initiala din memorie unde sirul este memorat; aceasta coincide cu adresa primului element (de index 0) al sirului.

Exemplu: Presupunem ca avem declaratiile:

#define N 100
int a[N], *p;
Atunci sistemul va rezerva octetii (sa zicem) numerotati 300, 302, ..., 498 ca fiind adresele elementelor a[0], a[1], ..., a[99]
Instructiunile
p = a; si p = &a[0];
sunt echivalente si vor asigna lui "p" valoarea 300 (ca adresa de memorie). Aritmetica pointerilor pune la dispozitie o alternativa pentru indexarea sirurilor.
Instructiunile p = a + 1; si p = &a[1]; sunt echivalente si va asigna lui "p" valoarea 302 (adresa, bineinteles).

Exemplu: Presupunem ca avem un sir ale carui elemente au deja valori. Pentru a face suma elementelor, putem folosi pointeri.

suma = 0;
for (p = a; p < &a[N]; ++p)
suma += *p;

9.5 Pointeri aritmetici si lungimea elementelor

Pointerii aritmetici reprezinta una din trasaturile puternice ale limbajului C. Daca variabila "p" este pointer catre un tip particular, atunci expresia "p + 1" reprezinta adresa masina pentru memorarea sau accesarea urmatoarei variabile de acest tip. In mod similar, expresiile p + i ++p p += i au sens. Daca "p" si "q" sunt pointeri catre elemente de tip vector, atunci "p - q" intoarce valoarea "int" si reprezinta numarul de elemente dintre "p" si "q". Chiar daca expresiile pointer si expresiile aritmetice seamana, exista diferente mari intre cele doua tipuri de expresii.

Exemplu:

void main()
{
double a[2], *p, *q;
p = &a[0]; /* pointeaza catre baza sirului */
q = p + 1; /* echivalent cu q = &a[1]; */
printf("%d\n", q - p); /* se va tipari 1 */
printf("%d\n", (int) q - (int) p)); /* se va tipari 8 */
}

9.6 Trimiterea sirurilor ca argumente pentru functii

Intr-o definitie de functie, un parametru formal care este declarat ca un sir este de fapt un pointer. Cand este trimis un sir, atunci se trimite de fapt adresa de baza (evident prin "call-by-value"). Elementele vectorului nu sunt copiate. Ca o conventie de notatie, compilatorul permite folosirea parantezelor patrate ([,]) in declararea pointerilor ca parametri.

Exemplu:

Suma elementelor unui sir de tip vector

int suma(int a[], int n) /* n dimensiunea sirului */
{
int i, s = 0;
for (i = 0; i < n; ++i)
s += a[i];
return s;
}
In antetul functiei precedente, declaratia:
int a[]; este echivalenta cu int *a;
Pe de alta parte, declaratiile de mai sus nu sunt echivalente daca se utilizeaza in alta parte:
- prima se refera la creearea unui pointer constant (fara spatiu de memorie);
- a doua va crea o variabila pointer.
Presupunem ca "v" este declarat ca fiind un sir de 100 de elemente de tip "int". Dupa ce am atribuit valori elementelor sale, putem utiliza functia "suma()" pentru a aduna anumite valori ale lui "v".

Exemplu:

Sortare cu bule - "Bubble sort"

Algoritmii eficienti de sortare au, de obicei, O(n*log n) operatii. Metoda sortarii cu bule este ineficienta din acest punct de vedere deoarece are O(n^2) operatii. Totusi, pentru siruri de lungime mica, numarul de operatii este acceptabil. Un cod "elegant" ar fi:
void interschimba(int *, int *);

void bubble(int a[], int n) /* n este lungimea lui a[] */
{
int i, j;

for (i = 0; i < n - 1; ++i)
for (j = n - 1; i < j; --j)
if (a[j - 1] > a[j])
interschimba(&a[j - 1], &a[j]);
}

9.7 Siruri multidimensionale

Limbajul C permite siruri de orice tip, inclusiv siruri de siruri. Putem obtine siruri de dimensiune 2, 3, ... .

Exemple:

int a[100]; <- sir de dimensiune 1
int b[2][7]; <- sir de dimensiune 2
int c[5][3][2]; <- sir de dimensiune 3
Pornind de la adresa de baza, toate elementele sirului sunt memorate contiguu in memorie. Prin definitie un tablou bidimensional este de fapt un tablou unidimensional ale carei elemente sunt fiecare in parte cite un tablou. Prin urmare, indicii se scriu astfel a[i][j] in loc de a[i, j] ca in majoritatea limbajelor. In plus un tablou bidimensional poate fi tratat in mai multe moduri decat in alte limbaje. Elementele sunt memorate pe linii, ceea ce inseamna ca indicele din dreapta variaza primul in asa fel incit elementele sunt accesate in ordinea memoriei.

9.8 Vectori 2-dimensionali

Presupunem ca avem un vector 2-dimensional cu elemente intregi.
int a[3][5];
Incepand cu adresa de baza, compilatorul va aloca spatiu contiguu pentru 15 intregi. Atunci putem gandi acest vector ca o matrice, astfel:

Pentru a[i][j] avem expresiile, de exemplu, echivalente:
*(a[i] + j)
(*(a + i))[j]
*((*(a + i)) + j)
*(&a[0][0] + 5*i + j)
Putem gandi "a[i]" ca a "i"-a coloana a lui "a" (numarand de la 0), si "a[i][j]" ca elementul din linia "i", coloana "j" a sirului (numarand de la 0). Numele sirului ("a") este tot una cu "&a[0]"; acesta este un pointer catre un sir de 5 intregi. Adresa de baza este "&a[0][0]", si nu "a". Ultimul exemplu de mai sus reflecta functia de corespondenta in memorie dintre valoarea pointerului si indicele sirului.
Cand un vector multidimensional este un parametru formal in definitia unei functii, toate dimensiunile, exceptand prima trebuie specificate.

Exemplu:

Presupunem ca sunt date elementele vectorului "a". Functia de mai jos se poate folosi pentru suma elementelor unui sir. Atentie ! Trebuie specificat numarul de coloane.
int suma(int a[][5])
{
int i, j, suma = 0;

for (i = 0; i < 3; ++i)
for (j = 0; j < 5; ++j)
suma += a[i][j];
return suma;
}
In antetul functiei, urmatoarele declaratii sunt echivalente:
int a[][5] int (*a)[5] int a[3][5]
Constanta 3 actioneaza ca o reminiscenta a omului, dar compilatorul nu tine cont de ea.
Nou venitii in C sunt uneori confuzi in legatura cu deosebirea dintre un tablou bidimensional si un tablou de pointeri cum ar fi "a" din exemplul de mai sus. Fiind date declaratiile
int a[10][10];
int *b[10];
utilizarile lui "a" si "b" pot fi similare, in sensul ca a[5][5] si b[5][5] sunt ambele referinte legale ale aceluiasi "int".
Avantaje pentru utilizarea vectorilor (dezavantaje pentru pointeri):
- "a" este un tablou in toata regula: toate cele 100 celule de memorie trebuie alocate, iar pentru gasirea fiecarui element
se face calculul obisnuit al indicelui;
- pentru "b", oricum prin declararea sa se aloca 10 pointeri; fiecare trebuie facut sa pointeze un tablou de intregi.
Presupunind ca fiecare pointeaza cate 10 elemente din tablou, atunci vom obtine 100 celule de memorie rezervate, plus cele 10 celule pentru pointeri. Astfel tabloul de pointeri utilizeaza sensibil mai mult spatiu si poate cere un procedeu explicit de
initializare.
Avantaje pentru utilizarea pointerilor (dezavantaje pentru vectori):
- accesarea unui element se face indirect prin intermediul unui pointer, in loc sa se faca prin inmultire si adunare;
- liniile tabloului pot fi de lungimi diferite. Aceasta inseamna ca nu orice element al lui b este constrins sa pointeze pe un vector de 10 elemente, unii pot pointa pe cate 2 elemente, altii pe cate 20 si altii pe niciunul.

9.9 Vectori 3-dimensionali

Vectorii de dimensiune mai mare decat 3 lucreaza intr-un mod similar. Daca avem declaratia int a[7][9][2];
atunci compilatorul va aloca spatiu pentru 7*9*2 intregi. Adresa de baza a sirului este "&a[0][0][0]", iar functia de corespondenta in memorie este specificata de a[i][j][k] care este echivalent cu *(&a[0][0][0] + 9*2*i + 2*j + k)

9.10 Initializarea vectorilor

Exista mai multe moduri de a initializa un vector multidimensional.

Exemplu: Urmatoarele declaratii sunt echivalente:

int a[2][3] = {1, 2, 3, 4, 5, 6};
int a[2][3] = {{1, 2, 3}, {4, 5, 6}};
int a[][3] = {{1, 2, 3}, {4, 5, 6}};
Indexarea se face dupa linii. Daca nu sunt suficiente elemente care sa initializeze vectorul, atunci restul elementelor sunt initializate cu 0. Daca prima componenta lipseste, atunci compilatorul extrage lungimea din numarul de perechi de acolade interioare.

Exemplu: Consideram initializarea:

int a[2][2][3] = {
{{1, 1, 0}, {2, 0, 0}},
{{3, 0, 0}, {4, 4, 0}}
};
O initializare echivalenta poate fi data si astfel:
int a[][2][3] = {{{1, 1}, {2}}, {{3}, {4, 4}}};
De obicei, daca un sir declarat "auto" nu este explicit initializat, atunci elementele sirului vor contine valori "garbage".
Sirurile "static" si "external" sunt initializate implicit cu 0. Iata un mod simplu de a initializa toate valorile unui vector cu 0:
int a[2][2][3] = {0};

9.11 Alocarea dinamica a memoriei

C pune la dispozitie pentru alocarea memoriei functiile "calloc()" si "malloc()" din biblioteca standard. Aceste functii au prototipul declarat in . Acest lucru va permite rezervarea memoriei pentru un vector (de exemplu) in care ii aflam dimensiunea abia la rularea in executie (pana acum declararam dimensiunea unui vector cu #define). Un apel de tipul calloc(n, dimensiune_tip) va returna un pointer catre un spatiu din memorie necesar pentru memorarea a "n" obiecte, fiecare pe "dimensiune_tip" octeti. Daca sistemul nu poate aloca spatiul cerut, atunci acesta va returna valoarea NULL.
In ANSI C, tipul "size_t" este dat ca "typedef" in . De obicei, tipul este "unsigned". Definitia tipului este folosita in prototipurile functiilor "calloc()" si "malloc()":
void *calloc(size_t, size_t);
void *malloc(size_t);
Deoarece pointerul returnat de aceste functii are tipul "void", acesta poate fi asignat altor pointeri fara conversie explicita (cast). Totusi unele sisteme nu accepta aceasta conversie, deci ea trebuie facuta explicit. Octetii rezervati de "calloc()" sunt automat initializati cu 0, pe cand cei rezervati cu "malloc()" nu sunt initializati (deci vor avea valori "garbage"). Numele "calloc", respectiv "malloc", provine de la "contiguous allocation", respectiv "memory allocation".

Exemplu: Program care citeste dimensiunea unui sir interactiv

#include
#include

void main()
{
int *a, i, n, suma = 0;

printf("\n%s", "Citirea dimensiunii unui sir interactiv.\n\nDati numarul de elemente a sirului: ");
scanf("%d", &n);
a = calloc(n, sizeof(int)); /* aloca spatiu pentru n intregi */
/* daca da eroare de conversie de tip, atunci adaugati dupa semnul =, conversia (int *) */
for (i = 0; i < n; ++i)
scanf("%d", &a[i]);
for (i = 0; i < n; ++i)
suma += a[i];
free(a); /* eliberarea spatiului */
printf("\n%s%7d\n%s%7d\n\n", "Numarul de elemente: ", n, "Suma elementelor : ", suma);
}
Prototipul functiei "free()" se gaseste in si este void free(void *ptr);
Spatiul alocat de "calloc()" si "malloc()" ramane ocupat pana cand este eliberat de catre programator. Acesta nu se elibereaza cand se iese dintr-o functie (in care s-a facut rezervarea de memorie).
In programul de mai sus, instructiunea
a = calloc(n, sizeof(int));
este echivalenta cu
a = malloc(n * sizeof(int));
Singura diferenta este deci initializarea cu 0 in cazul functiei "calloc()".

Exemplu: Exemplu de citire interactiva a dimensiunii si a elementelor unei matrice de intregi
void main()
{
int N;
int ** a, *ptr;

printf("Introduceti dimensiunea matricii:");
scanf("%d", &N);
a = (int **) calloc(N * N, sizeof(int));

ptr=&a[0][0];
printf("\n\nIntroduceti elementele matricii:\n");

for (i = 0;i < N; ++i)
for (j = 0;j < N; ++j)
{
printf("a[%d][%d]=", i, j);
scanf("%d", ptr++);
}
}