LABORATORUL 07

Tablouri de date

Durată: 2 ore Limbaj: C / C++ Precedent: Laboratorul 6 PDF îndrumar EN English version

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

int v[5]; fiecare element ocupa 4 octetiv[0]0x1000v[1]0x1004v[2]0x1008v[3]0x100Cv[4]0x1010v (adresa primului element)&v[i] = v + i * sizeof(int)indicele nu este verificat: v[5] citeste memorie din afara tabloului
Fig. - Asezarea unui tablou in memorie. Elementele sunt contigue, iar numele tabloului este adresa primului element - de aici formula de calcul a adresei si absenta oricarei verificari de limite.
  • 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țializareEfect
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].
ExpresieSemnificațieExemplu pentru int v[4]
sizeof(v)dimensiunea totală a tabloului16 octeți
sizeof(v[0])dimensiunea unui element4 octeți
sizeof(v)/sizeof(v[0])numărul de elemente4
vadresa 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.

Acces la elementele unui tablou de întregi
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)RolAtenție
strlen(s)lungimea, fără terminatorparcurge tot șirul de fiecare dată
strcpy(d, s)copiază s în dnu verifică dimensiunea lui d
strncpy(d, s, n)copiază cel mult n caracterepoate să nu adauge terminatorul
strcat(d, s)concatenează s la sfârșitul lui dd trebuie să aibă spațiu suficient
strcmp(a, b)compară lexicograficreturnează 0 la egalitate, nu 1
Compararea șirurilorif (s1 == s2) compară adresele, nu conținutul. Pentru conținut se folosește if (strcmp(s1, s2) == 0).

7Algoritmi uzuali

AlgoritmCerințăComplexitate
Căutare secvențialăniciunaO(n)
Căutare binarătabloul trebuie sortatO(log n)
Sortare prin interschimbare (bubble)niciunaO(n²)
Sortare prin selecțieniciunaO(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>

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:  ");
    for (int i = 0; i < n; i++) printf("%d ", v[i]);
    printf("\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:   ");
    for (int i = 0; i < n; i++) printf("%d ", v[i]);
    printf("\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)  = %d\n", (int)strlen(text));
    printf("Spatiu ocupat     = %d octeti\n", (int)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.

Statistici pe un vector
#include <stdio.h>

int main(void)
{
    int v[8] = {23, 7, 41, 15, 8, 39, 12, 30};
    int n = 8, i;
    int minim = v[0], maxim = v[0], suma = 0;

    for (i = 0; i < n; i++) {
        suma += v[i];
        if (v[i] < minim) minim = v[i];
        if (v[i] > maxim) maxim = v[i];
    }

    printf("Elemente : ");
    for (i = 0; i < n; i++) printf("%d ", v[i]);

    printf("\nSuma     : %d\n", suma);
    printf("Media    : %.2f\n", (double)suma / n);
    printf("Minim    : %d\n", minim);
    printf("Maxim    : %d\n", maxim);
    return 0;
}
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.
Exercițiu - inversarea unui vector
#include <stdio.h>

int main(void)
{
    int v[6] = {1, 2, 3, 4, 5, 6};
    int n = 6, i, temp;

    /* Inversati vectorul pe loc, fara vector auxiliar:
       schimbati intre ele v[0] cu v[n-1], v[1] cu v[n-2] etc.
       Cate schimbari sunt necesare? */

    for (i = 0; i < n; i++) printf("%d ", v[i]);
    printf("\n");
    return 0;
}

10Exerciții cu verificare automată

Aici scrieți voi codul. Butonul ✓ Verifică rulează programul pe mai multe seturi de date și vă arată imediat unde diferă rezultatul. La final trimiteți traseul ales, iar profesorul îl notează automat.

Fiecare exercițiu are programul deja început, iar comentariile vă spun ce mai trebuie adăugat. Scrieți codul, apăsați ✓ Verifică și citiți ce spune fiecare test picat. Dacă v-ați blocat, deschideți câte un indiciu. Puteți afișa și mesaje pentru utilizator (de tipul Introduceti n:), testul se uită la ce afișați la final.

P1

Suma și maximul

Pe primul rând este n (1 ≤ n ≤ 100), apoi n numere întregi. Afișați suma lor și cel mai mare dintre ele.

intrare5 3 9 -2 7 1
ieșire18 9
#include <stdio.h>

int main(void)
{
    int v[100], n, i;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &v[i]);

    /* Vectorul v este deja citit. Parcurgeți-l încă o dată:
         - adunați fiecare v[i] la o variabilă suma (pornită de la 0);
         - pentru maxim, porniți de la max = v[0] și actualizați-l.
       Afișați: printf("%d %d\n", suma, max); */

    return 0;
}
P2

În ordine inversă

Citiți n și apoi n numere întregi. Afișați-le în ordine inversă, pe un rând.

intrare4 1 2 3 4
ieșire4 3 2 1
#include <stdio.h>

int main(void)
{
    int v[100], n, i;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &v[i]);

    /* Parcurgeți vectorul de la ultimul element (indicele n - 1)
       până la primul (indicele 0): for (i = n - 1; i >= 0; i--) */

    return 0;
}
P3

Câte numere sunt pare

Citiți n și apoi n numere întregi. Afișați câte dintre ele sunt pare.

intrare5 1 2 3 4 6
ieșire3
#include <stdio.h>

int main(void)
{
    int v[100], n, i;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &v[i]);

    /* Folosiți un contor pornit de la 0 și creșteți-l pentru fiecare
       element cu v[i] % 2 == 0. */

    return 0;
}
P4

Căutarea unei valori

Citiți n, apoi n numere întregi, apoi o valoare x. Afișați poziția (indicele, de la 0) primei apariții a lui x, sau -1 dacă x nu apare.

intrare5 4 8 15 16 23 15
ieșire2
#include <stdio.h>

int main(void)
{
    int v[100], n, i, x, poz = -1;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &v[i]);
    scanf("%d", &x);

    /* Parcurgeți vectorul; la prima egalitate v[i] == x
       rețineți poz = i și opriți căutarea cu break. */

    printf("%d\n", poz);
    return 0;
}
P5

Palindrom

Citiți un cuvânt (fără spații, cel mult 100 de litere mici). Afișați da dacă se citește la fel de la stânga la dreapta și invers, altfel nu.

intrarecojoc
ieșireda
#include <stdio.h>
#include <string.h>

int main(void)
{
    char s[101];
    int i, n, ok = 1;
    scanf("%100s", s);
    n = strlen(s);

    /* Comparați s[i] cu s[n - 1 - i] pentru i de la 0 până la jumătate.
       La prima diferență, ok = 0. La final afișați "da" sau "nu". */

    return 0;
}

Problemele pornesc de la un main gol. Formatul ieșirii trebuie respectat exact (spațiile și rândurile noi nu contează, dacă enunțul nu spune altfel), deci nu afișați mesaje pentru utilizator. Testele vizibile acoperă doar cazurile simple; la notare se rulează și teste ascunse, alese să prindă cazurile limită.

A1

Sortarea unui vector

Citiți n (1 ≤ n ≤ 1000) și n numere întregi. Afișați-le în ordine crescătoare, pe un rând. Implementați voi sortarea (fără qsort).

intrare5 5 3 9 1 3
ieșire1 3 3 5 9
#include <stdio.h>

int main(void)
{
    /* scrieți aici rezolvarea */

    return 0;
}
A2

Eliminarea duplicatelor

Citiți n (1 ≤ n ≤ 1000) și n numere întregi. Afișați valorile distincte, în ordinea primei apariții, și apoi, pe rândul următor, câte valori distincte sunt.

intrare7 3 1 3 2 1 5 3
ieșire3 1 2 5 4
#include <stdio.h>

int main(void)
{
    /* scrieți aici rezolvarea */

    return 0;
}
A3

Diagonalele și transpusa

Citiți n (1 ≤ n ≤ 20) și o matrice pătratică n × n de întregi. Afișați pe primul rând suma diagonalei principale și suma diagonalei secundare, apoi matricea transpusă, câte un rând pe linie.

intrare2 1 2 3 4
ieșire5 5 1 3 2 4
#include <stdio.h>

int main(void)
{
    /* scrieți aici rezolvarea */

    return 0;
}
A4

Frecvența literelor

Citiți un rând de text. Ignorând diferența dintre litere mari și mici, afișați fiecare literă care apare, în ordine alfabetică, împreună cu numărul de apariții, câte o pereche pe rând (literele se afișează mici). Celelalte caractere se ignoră.

intrareAna are mere
ieșirea 3 e 3 m 1 n 1 r 2
#include <stdio.h>

int main(void)
{
    /* scrieți aici rezolvarea */

    return 0;
}

11Sarcini 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.

12Aplicaț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>.

13Întrebări de verificare

14Resurse