Un tablou este o colecție de date de același tip, plasate într-o zonă contiguă de memorie. Prin folosirea unui singur nume și a unui indice se pot stoca și prelucra oricâte valori - limita este dată doar de memoria disponibilă.
1Obiectivele lucrării
- Declararea tablourilor cu una sau mai multe dimensiuni
- Calculul adresei unui element și al dimensiunii totale ocupate
- Înțelegerea consecințelor accesului în afara limitelor
- Utilizarea șirurilor de caractere și a terminatorului nul
- Implementarea algoritmilor de căutare și sortare
2Declararea tablourilor
sintaxă
tip_element nume_tablou [dim_1][dim_2]...[dim_N]; float vect1[5]; // 5 elemente float -> 5 * sizeof(float) octeti int dimensiuni[4][12]; // 4 * 12 = 48 elemente int
Dimensiunile trebuie să fie constante întregi cunoscute la compilare. Zona de memorie rezervată
conține dim_1 × dim_2 × ... × dim_N elemente de tipul specificat.
| Formă de inițializare | Efect |
|---|---|
int v[5] = {1, 2, 3, 4, 5}; | toate elementele primesc valori explicite |
int v[5] = {1, 2}; | primele două primesc valori, restul devin 0 |
int v[5] = {0}; | tot tabloul este pus pe zero |
int v[] = {1, 2, 3}; | dimensiunea este dedusă automat: 3 |
int v[5]; | valori nedefinite - conține „gunoi" din memorie |
Indicii încep de la zeroUn tablou declarat cu
int v[5] are elementele
v[0], v[1], v[2], v[3], v[4].
Elementul v[5] nu există, deși compilatorul acceptă scrierea lui.3Organizarea în memorie
Elementele sunt plasate la adrese succesive. Adresa unui element se calculează astfel:
Formula de adresare
&v[i] = adresa_de_bază + i · sizeof(tip_element)
Numele tabloului, folosit singur, reprezintă chiar adresa primului element:
v este echivalent cu &v[0].| Expresie | Semnificație | Exemplu pentru int v[4] |
|---|---|---|
sizeof(v) | dimensiunea totală a tabloului | 16 octeți |
sizeof(v[0]) | dimensiunea unui element | 4 octeți |
sizeof(v)/sizeof(v[0]) | numărul de elemente | 4 |
v | adresa primului element | &v[0] |
4Simulator de indexare
Schimbați indicele și urmăriți ce element este accesat și la ce adresă se află. Încercați indici negativi sau mai mari decât dimensiunea, ca să vedeți ce înseamnă ieșirea din limite.
Depășirea limitelor nu este verificatăÎn C/C++ nu există nicio verificare
automată a indicilor, nici la compilare, nici la execuție. Scrierea în
v[10] pentru un tablou
de 6 elemente suprascrie memoria altor variabile, producând erori care se manifestă mult mai târziu,
în cu totul altă parte a programului. Este cea mai frecventă cauză a defectelor grave de securitate.5Tablouri bidimensionale
O matrice se declară cu două dimensiuni și se memorează pe linii (row-major): toate elementele primei linii, apoi ale celei de-a doua ș.a.m.d.
organizarea unei matrice 3×4 în memorie
int m[3][4]; linia 0: m[0][0] m[0][1] m[0][2] m[0][3] linia 1: m[1][0] m[1][1] m[1][2] m[1][3] linia 2: m[2][0] m[2][1] m[2][2] m[2][3] in memorie, consecutiv: [0][0] [0][1] [0][2] [0][3] [1][0] [1][1] ... [2][3] adresa: &m[i][j] = baza + (i * 4 + j) * sizeof(int)
Ordinea parcurgerii contează pentru vitezăParcurgerea pe linii
(
for i { for j }) accesează adrese consecutive și folosește eficient memoria cache.
Parcurgerea pe coloane sare din 4 în 4 elemente și poate fi sensibil mai lentă pentru matrice mari.6Șiruri de caractere
În C nu există un tip dedicat pentru șiruri: acestea sunt tablouri de char, terminate
obligatoriu cu caracterul nul '\0'.
reprezentarea șirului "abc"
char s[] = "abc";
indice: 0 1 2 3
valoare: 'a' 'b' 'c' '\0'
^ ^
primul caracter terminator adaugat automat
sizeof(s) = 4 (include terminatorul)
strlen(s) = 3 (numara pana la terminator)
Funcție (string.h) | Rol | Atenție |
|---|---|---|
strlen(s) | lungimea, fără terminator | parcurge tot șirul de fiecare dată |
strcpy(d, s) | copiază s în d | nu verifică dimensiunea lui d |
strncpy(d, s, n) | copiază cel mult n caractere | poate să nu adauge terminatorul |
strcat(d, s) | concatenează s la sfârșitul lui d | d trebuie să aibă spațiu suficient |
strcmp(a, b) | compară lexicografic | returnează 0 la egalitate, nu 1 |
Compararea șirurilor
if (s1 == s2) compară adresele, nu conținutul.
Pentru conținut se folosește if (strcmp(s1, s2) == 0).7Algoritmi uzuali
| Algoritm | Cerință | Complexitate |
|---|---|---|
| Căutare secvențială | niciuna | O(n) |
| Căutare binară | tabloul trebuie sortat | O(log n) |
| Sortare prin interschimbare (bubble) | niciuna | O(n²) |
| Sortare prin selecție | niciuna | O(n²) |
De ce contează complexitateaPentru 1000 de elemente, căutarea secvențială
face în medie 500 de comparații, iar cea binară doar 10. Diferența devine decisivă la volume mari de date.
8Cod sursă
statistici.c - prelucrarea unui vector
#include <stdio.h>
#define DIM_MAX 100
int main(void)
{
int v[DIM_MAX], n;
int suma = 0, minim, maxim;
printf("Numarul de elemente (max %d): ", DIM_MAX);
scanf("%d", &n);
if (n <= 0 || n > DIM_MAX) {
printf("Dimensiune invalida\n");
return 1;
}
for (int i = 0; i < n; i++) {
printf("v[%d] = ", i);
scanf("%d", &v[i]);
}
minim = maxim = v[0]; // pornim de la primul element
for (int i = 0; i < n; i++) {
suma += v[i];
if (v[i] < minim) minim = v[i];
if (v[i] > maxim) maxim = v[i];
}
printf("\nSuma = %d\n", suma);
printf("Media = %.3f\n", (double)suma / n);
printf("Minim = %d\n", minim);
printf("Maxim = %d\n", maxim);
return 0;
}
sortare.c - bubble sort cu optimizare
#include <stdio.h>
void afiseaza(int v[], int n)
{
for (int i = 0; i < n; i++) printf("%d ", v[i]);
printf("\n");
}
int main(void)
{
int v[] = {29, 10, 14, 37, 13, 5};
int n = sizeof(v) / sizeof(v[0]); // numarul de elemente, calculat automat
printf("Initial: "); afiseaza(v, n);
for (int i = 0; i < n - 1; i++) {
int schimbat = 0; // optimizare: detecteaza vectorul deja sortat
for (int j = 0; j < n - 1 - i; j++) {
if (v[j] > v[j + 1]) {
int aux = v[j];
v[j] = v[j + 1];
v[j + 1] = aux;
schimbat = 1;
}
}
if (!schimbat) break; // nicio interschimbare -> gata
}
printf("Sortat: "); afiseaza(v, n);
return 0;
}
matrice.c - operații cu matrice
#include <stdio.h>
#define N 3
int main(void)
{
int m[N][N] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int sumaDiag = 0;
printf("Matricea:\n");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf("%4d", m[i][j]);
printf("\n");
}
// suma diagonalei principale: elementele cu i == j
for (int i = 0; i < N; i++)
sumaDiag += m[i][i];
printf("\nSuma diagonalei principale = %d\n", sumaDiag);
// transpusa: se schimba liniile cu coloanele
printf("\nTranspusa:\n");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf("%4d", m[j][i]);
printf("\n");
}
return 0;
}
siruri.c - prelucrarea șirurilor
#include <stdio.h>
#include <string.h>
int main(void)
{
char text[100];
printf("Introduceti un cuvant: ");
fgets(text, sizeof(text), stdin);
text[strcspn(text, "\n")] = '\0'; // elimina linia noua
printf("Lungime (strlen) = %zu\n", strlen(text));
printf("Spatiu ocupat = %zu octeti\n", sizeof(text));
// inversarea sirului, pe loc
int n = strlen(text);
for (int i = 0; i < n / 2; i++) {
char aux = text[i];
text[i] = text[n - 1 - i];
text[n - 1 - i] = aux;
}
printf("Inversat = %s\n", text);
// verificare palindrom
int palindrom = 1;
for (int i = 0; i < n / 2; i++)
if (text[i] != text[n - 1 - i]) { palindrom = 0; break; }
printf("Este palindrom? %s\n", palindrom ? "DA" : "NU");
return 0;
}
9Atelier de cod
Tabloul este o zonă continuă de memorie. În modul Pas cu pas, panoul din dreapta arată tot conținutul tabloului după fiecare instrucțiune - inclusiv dacă scrieți în afara lui.
De încercatÎncercați să schimbați
i < n în i <= n și rulați: motorul vă avertizează că ați ieșit din tablou. Un compilator obișnuit nu v-ar spune nimic, iar programul ar folosi o valoare întâmplătoare din memorie.10Sarcini de lucru
- Citiți N valori într-un vector și determinați suma, media, minimul și maximul.
- Afișați adresa fiecărui element și verificați că diferența dintre adrese este
sizeof(tip). - Calculați numărul de elemente cu
sizeof(v)/sizeof(v[0])și verificați rezultatul. - Implementați sortarea prin interschimbare, cu optimizarea de oprire anticipată.
- Scrieți căutarea binară într-un vector sortat și comparați numărul de pași cu cea secvențială.
- Construiți transpusa unei matrice pătratice și calculați suma ambelor diagonale.
- Verificați dacă un cuvânt citit este palindrom.
- Scrieți intenționat în afara limitelor unui tablou mic și observați ce se întâmplă cu variabilele vecine.
11Aplicație de aprofundare
ExtindereImplementați „Ciurul lui Eratostene" pentru determinarea numerelor prime
până la N: folosiți un tablou de indicatori, marcați multiplii fiecărui număr prim găsit și afișați
la final doar pozițiile rămase nemarcate. Comparați timpul de execuție cu metoda verificării fiecărui
număr prin împărțiri succesive, pentru N = 100 000, folosind funcția
clock() din
<time.h>.