Algoritmi Array-uri unidimensionale

1. Parcurgere

int n = 5;
int v[100]; // declaram array-ul cu o valoarea mai mare decat n, in caz ca avem nevoie de spatiu in plus pe viitor.

for (int i = 0; i < n; i++) {
    printf("%d ", v[i]); // aici putem sa operam pe elementele array-ului, in cazul asta doar afisam
}

---

2. Parcurgere in sens invers

int n = 5;
int v[100];

// Vom parcurge de la coada spre cap
for (int i = n-1; i >= 0; i--) {
    printf("%d ", v[i]);
}

---

3. Adaugare in array, la coada acestuia

int n = 5;
int v[100] = {1, 2, 3, 4, 5};

v[n] = 6;
n++;

De asemenea putem scrie:

v[n++] = 6;

Pentru a incremente valoarea lui n odata cu accesarea elementului.

Aici, ca o paranteza, o sa vorbesc despre pre-incrementare si post-incrementare.

v[n++] = 6;

Codul de mai sus o sa faca v[n] = 6 si apoi va mari valoarea lui n. In cazul asta n++ este post-incrementare.

v[++n] = 6;

Codul de mai sus o sa mareasca valoarea lui n mai intai, si abia apoi o sa faca valoarea lui v[n] = 6, in cazul asta ++n este pre-incrementare.

Daca n = 5, prima varianta o sa faca ca v[5] = 6 iar a doua o sa faca ca v[6] = 6.

---

4. Eliminarea din array, din coada acestuia

In cazul in care vrem sa scurtam array-ul este suficient doar sa scadem valoarea lui n. Atunci cand vom parcurge nu vom mai ajunge pana la ea, si ea va fi oricum suprascrisa atunci cand vom adauga pe viitor.

Exemplu:

int n = 5;
int v[100] = {1, 2, 3, 4, 5};

// eliminam ultima valoare
n--;

// adaugam 6 in coada
v[n] = 6;
n++;

Rezultatul este: [1, 2, 3, 4, 6]

---

5. Eliminarea din array a unui element de pe orice pozitie

Strategie noastra este urmatoarea: Avem array-ul: [1, 2, 3, 100, 4, 5, 6] Si vrem sa eliminam valoarea 100 care se afla pe pozitia 3.

Pentru a face asta noi va trebui sa luam fiecare valoarea din dreapta lui 100 si sa o "mutam" in spate cu o pozitie, astfel scriind peste valoarea 100. Adica:

1. 4 care se afla pe pozitia 4 va fi scris peste 100, care e pe pozitia 3. Valoarea lui '4' ramane in continuare scrisa unde era initial

2. 5 care se afla pe pozitia 5 va fi scris peste 4, care e pe pozitia 4. Valoarea lui '5' ramane in continuare scrisa unde era initial

3. 6 care se afla pe pozitia 6 va fi mutat peste 5, care e pe pozitia 5. Valoarea lui '6' ramane in continuare scrisa unde era initial

4. Acum ca am "mutat" toate elementele cu un pas in spate, vom micsora vectorul micsorand valoarea lui n.

Pasii in memorie ar arata asa:

Array initial: [1, 2, 3, 100, 4, 5, 6]

1. [1, 2, 3, 4, 4, 5, 6], n = 7

2. [1, 2, 3, 4, 5, 5, 6], n = 7

3. [1, 2, 3, 4, 5, 6, 6], n = 7

4. [1, 2, 3, 4, 5, 6, 6], n = 6

Codul pentru asta aratand asa:

int n = 7;
int v[100] = {1, 2, 3, 100, 4, 5, 6};

int toRemove = 3; // tinem intr-o variabila pozitia pe care vrem sa o eliminam

for (int i = toRemove; i < n-1; i++) {
    v[i] = v[i+1]; // scriem peste elementul curent valoarea elementului urmator
}
n--; // micsoram valoarea lui n

Observatie: n-1 in codul de mai sus nu este greseala, nu vrem sa mergem pana la ultimul element al sirului pentru ca am ajunge sa incercam sa accesam o valoare care nu exista!

---

6. Introducerea in array a unui element nou pe o pozitie anume

Strategia este similara ca la eliminare. Avem array-ul [1, 2, 3, 4, 5, 6] Si vrem sa punem valoarea 100 inapoi pe pozitia 3. Ca sa facem asta vom "muta" toate elementele de la pozitia 3 in colo cu o pas in fata, iar apoi vom scrie numarul 100 pe pozitia 3.

Array initial: [1, 2, 3, 4, 5, 6], care tine minte ca are de fapt dimensiunea 100! De fapt in memorie array-ul complet este [1, 2, 3, 4, 5, 6, 0, 0, 0, 0, ..., 0]!

1. [1, 2, 3, 4, 5, 6, 0], n = 6 array initial

2. [1, 2, 3, 4, 5, 6, 6], n = 6 mutam fiecare element un pas la dreapta

3. [1, 2, 3, 4, 5, 5, 6], n = 6

4. [1, 2, 3, 4, 4, 5, 6], n = 6

5. [1, 2, 3, 100, 4, 5, 6], n = 6

6. [1, 2, 3, 100, 4, 5, 6], n = 7 marim valoarea lui n

Codul arata asa:

int n = 6;
int v[100] = {1, 2, 3, 4, 5, 6};

int insertIdx = 3; // tinem intr-o variabila pozitia la care vrem sa inseram
int insertVal = 100; // valoarea pe care dorim sa o inseram

for (int i = n; i > insertIdx; i--) {
    v[i] = v[i-1]; // "mutam" fiecare element cu un pas in fata
}
v[insertIdx] = insertVal;
n++; // marim valoarea lui n

---

7. Inversarea a doua variabile (swapping).

De multe ori o sa vrem sa schimbam doua variabile intre ele. Spre exemplu:

Avem x = 1 si y = 100 si vrem ca x = 100 si y = 1. Algoritmul low-level pentru a efectua schimbarea necesita o variabila intermediara. Imagineaza-ti ca vrei sa interschimbi lichidul din doua pahare. Ca sa poti face asta ai nevoie de un al treilea pahar:

1. lichidul din paharul 1 merge in paharul intermediar

2. lichidul din paharul 2 merge in paharul 1

3. lichidul din paharul intermediar merge in paharul 2

la fel, in cod:

int x = 1;
int y = 100;

int temp;

temp = x;
x = y;
y = temp;

In majoritatea limbajelor exista functie de interschimbare, cum ar fi in C++ functia swap(x, y), dar in C suntem ultimii rupti in cur. Facem tot de la 0.

---

8. Cautarea unui element

Avem un array cu n elemente nesortate, dorim sa cautam valoarea 100 si sa ii aflam pozitia.

int findElement(int e, int v[], int n) {
    for (int i = 0; i < n; i++) {
        if (v[i] == e) {
            return i;
        }
    }
    return -1;
}

int main() {
    int n = 10;
    int v[100] = {11, 56, 22, 128, 909, 100, 112, 81, 111, 2};

    int toFind = 100;

    int idx = findElement(toFind, &v, n);
    printf("Element %d found at index %d\n", toFind, idx);

    return 0;
}