Tipuri de date structurate

În C++

Declararea unui vector are forma:

tip nume[nr_elemente];

int a[20];          // 20 de elemente de tip int
float b[10];        // 10 elemente de tip float
const int DIM = 100;
int v[DIM];         // lungimea data de o constanta simbolica

Constanta simbolică DIM se poate folosi apoi în program, de exemplu la verificarea lungimii logice.

Elementele pot primi valori chiar la declarare, printr-o listă scrisă între acolade:

int a[5] = {10, 20, 30, 40, 50};
int b[] = {10, 20, 30};       // 3 elemente, cate valori are lista
int c[5] = {10, 20};          // c[2], c[3], c[4] primesc 0
int f[10] = {0};              // toate elementele primesc 0

Dacă se inițializează toate elementele, numărul lor poate lipsi: compilatorul îl socotește din listă. Dacă lista are mai puține valori decât elemente, celelalte elemente primesc valoarea 0.

Accesul la un element se face prin nume[indice]. Indicii pornesc de la 0, deci pentru un vector cu n elemente indicele ia valori de la 0 la n − 1. Pentru vectorul a de mai sus, a[3] este al patrulea element și are valoarea 40.

În C++

void citire(int a[], int &n) {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
}

void afisare(int a[], int n) {
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << '\n';
}

void afisareInversa(int a[], int n) {
    for (int i = n - 1; i >= 0; i--)
        cout << a[i] << " ";
    cout << '\n';
}

Un tablou transmis ca parametru nu se copiază: subprogramul primește adresa lui și lucrează pe tabloul din programul principal. De aceea citire umple vectorul a din main. Lungimea n se transmite prin referință, int &n, numai la subprogramele care o schimbă.

În C++

void copiere(int a[], int n, int b[]) {
    for (int i = 0; i < n; i++)
        b[i] = a[i];
}

void divizare(int a[], int n, int m, int b[], int c[]) {
    for (int i = 0; i < m; i++)
        b[i] = a[i];
    for (int i = m; i < n; i++)
        c[i - m] = a[i];
}

void concatenare(int a[], int n, int b[], int m, int c[]) {
    for (int i = 0; i < n; i++)
        c[i] = a[i];
    for (int i = 0; i < m; i++)
        c[n + i] = b[i];
}

void inversareInAltVector(int a[], int n, int b[]) {
    for (int i = 0; i < n; i++)
        b[i] = a[n - 1 - i];
}

void inversare(int a[], int n) {
    for (int i = 0; i < n / 2; i++) {
        int aux = a[i];
        a[i] = a[n - 1 - i];
        a[n - 1 - i] = aux;
    }
}

void stergere(int a[], int &n, int k) {
    for (int i = k; i < n - 1; i++)
        a[i] = a[i + 1];
    n--;
}

void inserare(int a[], int &n, int k, int x) {
    for (int i = n; i > k; i--)
        a[i] = a[i - 1];
    a[k] = x;
    n++;
}

void permutareStanga(int a[], int n) {
    int x = a[0];
    for (int i = 1; i < n; i++)
        a[i - 1] = a[i];
    a[n - 1] = x;
}

void permutareDreapta(int a[], int n) {
    int x = a[n - 1];
    for (int i = n - 1; i > 0; i--)
        a[i] = a[i - 1];
    a[0] = x;
}

Atribuirea b = a nu copiază un vector în altul: pentru tablouri, compilatorul o semnalează ca eroare.

În C++

void frecventaCifrelor(long long n) {
    int f[10] = {0};
    do {
        f[n % 10]++;
        n = n / 10;
    } while (n != 0);
    for (int c = 0; c <= 9; c++)
        if (f[c] != 0)
            cout << c << " apare de " << f[c] << " ori\n";
}

În C++

#include <iostream>
#include <fstream>
using namespace std;

ifstream f("numere.txt");

int main() {
    int x, fr[100] = {0};
    while (f >> x)
        if (x >= 10 && x <= 99)
            fr[x]++;

    int maxim = 0, nr = 0;
    for (int i = 10; i <= 99; i++)
        if (fr[i] > maxim) {
            maxim = fr[i];
            nr = i;
        }
    cout << nr;
    return 0;
}

În C++

int a[101][101];    // indicii 0..100; numerotate de la 1, cel mult 100 de linii si 100 de coloane

Elementul de pe linia i și coloana j se scrie a[i][j]. Matricea se parcurge cu două structuri for imbricate: cea exterioară trece prin linii, cea interioară prin coloanele liniei curente. În problemele de examen, liniile și coloanele se numerotează de obicei de la 1.

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        cin >> a[i][j];

În C++

Un tablou bidimensional transmis ca parametru se scrie cu a doua dimensiune precizată, int a[][DIM]: compilatorul are nevoie de ea ca să afle unde începe fiecare linie.

#include <iostream>
using namespace std;

const int DIM = 102;

void bordeaza(int a[][DIM], int n, int m, int v) {
    for (int j = 0; j <= m + 1; j++)
        a[0][j] = a[n + 1][j] = v;
    for (int i = 1; i <= n; i++)
        a[i][0] = a[i][m + 1] = v;
}

void bordeazaSume(int a[][DIM], int n, int m) {
    for (int j = 1; j <= m + 1; j++)
        a[n + 1][j] = 0;
    for (int i = 1; i <= n; i++) {
        a[i][m + 1] = 0;
        for (int j = 1; j <= m; j++) {
            a[i][m + 1] += a[i][j];
            a[n + 1][j] += a[i][j];
        }
        a[n + 1][m + 1] += a[i][m + 1];
    }
}

void bordeazaMaxMin(int a[][DIM], int n, int m) {
    for (int i = 1; i <= n; i++) {
        a[i][0] = a[i][1];
        for (int j = 2; j <= m; j++)
            if (a[i][j] > a[i][0])
                a[i][0] = a[i][j];
    }
    for (int j = 1; j <= m; j++) {
        a[0][j] = a[1][j];
        for (int i = 2; i <= n; i++)
            if (a[i][j] < a[0][j])
                a[0][j] = a[i][j];
    }
}

int varfuri(int a[][DIM], int n, int m) {
    int nr = 0;
    bordeaza(a, n, m, -1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i][j] > a[i - 1][j] && a[i][j] > a[i + 1][j] &&
                a[i][j] > a[i][j - 1] && a[i][j] > a[i][j + 1])
                nr++;
    return nr;
}

void afisare(int a[][DIM], int i1, int i2, int j1, int j2) {
    for (int i = i1; i <= i2; i++) {
        for (int j = j1; j <= j2; j++)
            cout << a[i][j] << " ";
        cout << '\n';
    }
    cout << '\n';
}

int main() {
    int a[DIM][DIM], n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    bordeaza(a, n, m, 0);
    afisare(a, 0, n + 1, 0, m + 1);

    bordeazaSume(a, n, m);
    afisare(a, 1, n + 1, 1, m + 1);

    bordeazaMaxMin(a, n, m);
    afisare(a, 0, n, 0, m);

    cout << varfuri(a, n, m) << " varfuri";
    return 0;
}

Subprogramul afisare primește limitele liniilor și ale coloanelor, deci aceeași matrice se poate afișa cu bordura întreagă sau numai cu laturile completate.

În C++

Un șir de caractere este o succesiune de caractere încheiată cu caracterul NULL, adică cel cu codul ASCII 0, scris '\0'.

Limbajul nu are un tip aparte pentru șiruri: ele se păstrează în vectori de caractere. De aici decurge tot ce urmează: un șir este un vector, iar sfârșitul lui nu e dat de o lungime memorată undeva, ci de primul caracter NULL întâlnit.

Cum se păstrează în memorie:

• fiecare caracter ocupă un octet;
• în octet se păstrează codul ASCII al caracterului;
• caracterele sunt memorate unul după altul, în ordinea din șir: primul pe indicele 0, al doilea pe indicele 1 și așa mai departe;
• după ultimul caracter urmează caracterul NULL.

Cuvântul informatica are 11 litere, deci ocupă 12 octeți:

char a[] = "informatica";
cout << sizeof(a);     // 12: octetii ocupati, cu tot cu caracterul NULL
cout << strlen(a);     // 11: caracterele sirului, fara caracterul NULL
cout << (int) a[0];    // 105: codul ASCII al literei i

Vectorul poate avea mai multe poziții decât îi trebuie șirului. Octeții de după caracterul NULL sunt rezervați, dar nu fac parte din șir, iar conținutul lor nu contează:

Numele vectorului este o adresă

Numele unui vector de caractere este adresa primului lui octet. De aici urmează:

• a + k este adresa octetului de pe indicele k; folosit ca șir, a + k este partea din a care începe pe poziția k și se termină la caracterul NULL;
• *(a + k) și a[k] sunt același caracter;
• o adresă se poate păstra într-o variabilă de tip char *: atribuirea p = a este corectă, iar a = p nu este, fiindcă numele vectorului este o adresă constantă;
• diferența dintre două adrese din același vector este un număr întreg: p - a este indicele octetului spre care arată p.

char a[] = "informatica";
cout << a + 2;              // formatica
char *p = strchr(a, 'm');   // adresa literei m
cout << p;                  // matica
cout << p - a;              // 5, indicele literei m

Pe aceeași regulă lucrează funcțiile din <cstring> care primesc sau întorc o adresă: strcpy(t, a + 2) copiază în t șirul formatica, iar poziția găsită de strchr se află cu strchr(a, c) - a.

Pointerul la caracter

Variabila care păstrează adresa unui caracter se numește pointer la caracter. Se declară cu steluță în fața numelui:

char *p;

Declarația se citește: p păstrează adresa unei variabile de tip char. Steluța se aplică variabilei, nu tipului: în char *x, y; numai x este pointer, iar y este un caracter.

Ce se face cu un pointer la caracter:

• primește o adresă: p = a; îi dă adresa lui a[0], iar p = &a[2]; adresa lui a[2]; operatorul & dă adresa unei variabile;
• *p este caracterul de la adresa păstrată în p; operatorul * scris în fața pointerului dă valoarea de la adresă, care se poate și schimba: *p = 'l' schimbă caracterul spre care arată p;
• cout << p afișează șirul care începe la acea adresă, până la caracterul NULL, iar cout << *p afișează un singur caracter;
• p++ trece la caracterul următor, iar p + k este adresa caracterului aflat cu k poziții mai departe;
• funcțiile care caută, ca strchr, strstr și strtok, întorc un pointer la caracter, iar când nu găsesc nimic întorc NULL; de aceea rezultatul lor se verifică înainte de folosire.

char a[] = "mere";
char *p;
p = a;
cout << *p;     // m
cout << p;      // mere
p = &a[2];
cout << *p;     // r
cout << p;      // re
*p = 'l';
cout << a;      // mele

Un șir se poate parcurge și cu un pointer, în locul indicelui:

int n = 0;
for (p = a; *p != '\0'; p++)
    n++;        // la sfarsit, n este lungimea sirului

Un caracter NULL pus în mijlocul șirului

Afișarea, strlen și celelalte funcții se opresc la primul caracter NULL întâlnit. Dacă unei poziții din mijloc i se atribuie '\0', șirul se scurtează, deși caracterele de după ea rămân în memorie:

char a[] = "informatica";
a[6] = '\0';
cout << a;            // inform
cout << strlen(a);    // 6
cout << a + 7;        // tica

Tot așa lucrează strtok: scrie caracterul NULL în locul separatorului de după fiecare cuvânt.

Vector de caractere și adresă de șir

char t[] = "Salut C!";         // vector: o copie a textului, 9 octeti
const char *b = "Salut C!";    // adresa unei constante sir

Deosebirile:

• t are octeții lui, iar caracterele se pot schimba: t[0] = 's' este corectă;
• b păstrează numai o adresă; constanta spre care arată nu se poate modifica, de aceea se declară const char *;
• sizeof(t) este 9, iar sizeof(b) este mărimea unei adrese, 4 sau 8 octeți, după compilator.

Vectorul de cuvinte

Mai multe cuvinte se păstrează într-o matrice de caractere, câte un cuvânt pe linie:

char c[3][8];
strcpy(c[0], "ana");
strcpy(c[1], "are");
strcpy(c[2], "mere");
cout << c[2];        // mere
cout << c[2][1];     // e

c[i] este adresa liniei i, deci se folosește oriunde se cere un șir: în cout, în strcpy, în strcmp. O linie cu 8 coloane păstrează un cuvânt de cel mult 7 caractere, fiindcă o poziție rămâne caracterului NULL.