Se dorește citirea unui șir de numere naturale de la tastatură terminat cu un -1, care nu face parte din șir (există mereu cel puțin un element pozitiv în șir). Se cere să se aloce dinamic memoria folosită. Să se gestioneze într-un mod eficient memoria alocată.

• Indicații de implementare:

  • Avem nevoie de 3 variabile:

    • int *v - array-ul care urmează să fie alocat/realocat dinamic

    • int capacity - acesta va conține în orice moment numărul de elemente alocate către care pointează v.

      • Prin urmare mereu vor exista v[0], v[1], …, v[capacity - 1]

    • int size - acesta conține în orice moment numărul de elemente folosite din vector.

      • Presupunem că pe măsură ce citim elemente, adăugăm mereu la finalul vectorului.

      • Elementele ocupate sunt mereu v[0], v[1], …, v[size - 1] (evident dacă size > 0)

    • Observăm că întotdeauna trebuie să avem size <= capacity (folosim cel mult câte elemente am alocat).

  • Algoritm:

    • Inițial: size = 0, capacity = 1, v = malloc(capacity * sizeof(int));

    • Cât timp NU am ajuns la -1

      • Citesc x (următorul element).

      • Dacă x este -1, mă opresc.

      • Altfel

        • Dacă size == capacity (vectorul e plin)

          • resize: ++capacity;

        • Adaugă elementul in vector și reactualizează size.

    • La final dacă size < capacity, aplic operația de resize si capacity = size (dacă am alocat prea multă memorie, eliberez surplusul).

    • Afișez size si capacity pe ecran.

    • Afișez elementele vectorului pe ecran.

Exemplu

Input:

0 1 2 5 9 -1

Output:

5 5
0 1 2 5 9

Follow-up: In loc sa incrementati, dublati capacitatea vectorului pentru realocarea memoriei. Discutati cu asistentul care sunt avantajele/dezavantajele unei astfel de abordari.

Dorim să implementăm un API minimal ce aloca o matrice de numere întregi de n x m elemente sub forma unui vector, pentru a stoca elementele contiguu în memorie.

• Creati functia alloc_matrix(int n, int m) ce intoarce un int* (pointer catre începutul matricei). Afisati matricea si demonstrați că aceasta este stocată contiguu.

Creati functia int access_elem(int *mat, int n, int i, int j) ce returneaza un pointer la elementul de pe linia i și coloana j din matrice.

Creați funcția free_matrix(int *mat) care eiberează resursele folosite.

Input: Pe prima linie se află n și m, dimensiunile matricei. Pe următoarele n linii se află câte m elemente, care reprezintă elementele matricei.

Pe ultima linie se află doi indici i și j pentru care dorim să aflăm elementul din matrice. (indexare de la 0).

Output: elementele matricei, element din matrice cu indecsii i si j

Exemplu

Input:

3 3
1 2 3
4 5 6
7 8 9
1 1

Output:

1 2 3
4 5 6
7 8 9
5

Explicatii:

Se primesc de la tastatura n = 3, m = 3, elementele matricei și poziția (1, 1). Se aloca memoria si se afiseaza matricea, dupa care se afiseaza elementul de pe poziția (1, 1) din matrice returnat de functia access_elem().

• Follow-up: modificați implementarea voastră astfel încât să nu folosiți operatorul [].

• Follow-up: faceți implementarea generică. Alocarea trebuie să țină pentru un element de orice tip, nu doar de tipul int.

  Hint: Pentru funcțiile de alloc_matrix și access_elem trebuie să mai adaugați un parametru ce reprezintă numărul de bytes pentru fiecare element al matricei.