>> Inapoi <<
==================
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.
-------------------------------
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 3) 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 ?
Nume Tip Valoare Adresa
------------------------------------
| a[4] | int | 23 | 3A38:0FFE |
------------------------------------
------------------------------------
| a[3] | int | 16 | 3A38:0FFC |
------------------------------------
------------------------------------
| a[2] | int | 11 | 3A38:0FFA |
------------------------------------
------------------------------------
| a[1] | int | 8 | 3A38:0FF8 |
------------------------------------
------------------------------------
| a[0] | int | 7 | 3A38:0FF6 |
------------------------------------
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").
---------------------------
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.
---------------------
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.
-----------------------------------------
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;
-------------------------------------------------------
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 */
}
--------------------------------------------------------------
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".
--------------------------------------------------------------
| Apel | Ce se calculeaza si se returneaza ? |
--------------------------------------------------------------
suma(v, 100) v[0] + v[1] + ... + v[99]
suma(v, 88) v[0] + v[1] + ... + v[87]
suma(&v[7], k-7) v[7] + v[8] + ... + v[k - 1]
suma(v + 7, 2 * k) v[7] + v[8] + ... + v[2 * k + 6]
--------------------------------------------------------------
-----------
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]);
}
--------------------------------
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.
------------------------------
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:
col1 col2 col3 col4 col5
lin1 a[0][0] a[0][1] a[0][2] a[0][3] a[0][4]
lin2 a[1][0] a[1][1] a[1][2] a[1][3] a[1][4]
lin3 a[2][0] a[2][1] a[2][2] a[2][3] a[2][4]
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.
-----------------------------
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)
-----------------------------
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};
---------------------------------------
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, i;
int ** a, *ptr;
printf("Introduceti dimensiunea matricii:");
scanf("%d", &N);
a = (int **) malloc(N * sizeof(int *));
for (i = 0; i < N; i++)
a[i] = (int *) malloc(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++);
}
}
-----------------------------------------------
Exercitii propuse spre implementare
-----------------------------------------------
1. Scrieti o functie care insumeaza elementele de rang (index) impar, respectiv
par, ale unui vector cu elemente de tip "double".
Sugestie: functia poate incepe cam asa
void suma(double a[],
int n, /* n - lungimea sirului a */
double *impar,
double *par)
{
. . . . .
2. Modificati programul de sortare cu bule astfel incat terminarea iteratiilor
sa aiba loc cand nu se mai fac interschimbari de
elemente.
3. Calculati valoarea unui determinant asociat unei matrice patratice. In cazul
in care determinantul este nenul, calculati
inversa matricei.
4. Calculati inversa unei permutari cu un numar constant de variabile
suplimentare.