Pripremna nastava iz Programiranja (za maturski)

...

Pripremna nastava iz Programiranja, 8.čas from V. P. Filko on Vimeo.

Radi boljeg objašnjenja poslednjeg pitanja, pročitajte sledeće:

Implementacija nizova

Skica uređenja niza u memoriji

U programskom jeziku C ne postoje nizovi kao ugrađeni tipovi. Naprotiv, oni se implementiraju preko ostalih ugrađenih tipova i pokazivača. Ovo važi i za jednodimenzionalne i višedimenzionalne nizove (matrice, kocke itd.). Svaki niz u C-u se sastoji od dva fizička dela - elemenata koji sačinjavaju niz i jednog pokazivača koji pokazuje na početak tog niza, tj. njegov prvi element. Dakle, kada predstavimo niz na sledeći način:

int a[10];

tada nastaje 10 elemenata niza (koji nijedan nema svoje pravo ime), i jedna pokazivačka promjenljiva a preko koje se pristupa svim elementima niza koristeći sintaksu a[0] (prvi element, jer u C-u indeksiranje kreće od nule, a ne od jedinice), a[1], a[2], itd.

Nizovi se u C-u implementiraju preko pokazivača zahvaljujući specifičnoj pokazivačkoj aritmetici. Ako je a pokazivač na prvi element niza, onda *a predstavlja sam element. Dalje, pošto pokazivačka aritmetika diktira da a+1 bude pokazivač na sledeći element niza, onda će *(a+1) predstavljati sam drugi element niza. Idući dalje, primećujemo da je a[n] ekvivalentno sa *(a+n). To je upravo ono što kompajler vidi kada putem operatora indeksa referenciramo određeni element niza.

Ako idemo dalje, i predstavimo matricu realnih brojeva M dimenzija m x n, tada je stanje u memoriji sledeće:

• M predstavlja pokazivač na prvi element niza od m pokazivača.

• svaki od m pokazivača pokazuje na po prvi element niza od n realnih brojeva

Skica uređenja višedimenzionalnog niza (matrice) u memoriji

Kada koristimo statičke deklaracije nizova, ovakva stanja memorije se formiraju automatski, ali je takođe moguće formirati ih ručno, koristeći običnu deklaraciju pokazivača i neku od ugrađenih C-ovih funkcija za alociranje memorije. Sledi primer:

char ** alocirajMatricu(int m, int n )
{
    char ** M;
    int i;
    M = malloc(m * sizeof(char *) );        /* alociramo memoriju za niz pokazivača */
    for (i = 0; i < m; i++ )                /* za svaki pokazivač u tom nizu alociramo po još jedan niz */
         M[i] = malloc(n * sizeof(char) );  /* karaktera da bismo formirali matricu. */
    return M;                                /* vraćamo pokazivač „na matricu“. */
}

int main()
{
    char ** M;
    int m, n;
    int i, j;
    scanf("%d %d", &m, &n );         /* pitamo korisnika kolika matrica je potrebna */
    M = alocirajMatricu(m, n );      /* pozivamo funkciju da nam alocira prostor te veličine */
    for (i = 0; i < m; i++ )         /* nadalje se ponašamo kao prema običnoj matrici */
         for (j = 0; j < n; j++ )
               M[i][j] = 'x';

    // ovako alociranu matricu moramo obrisati ručno
    for (i = 0; i < m; i++ )
         free(M[i] );
    free(M );
    return 0;
}

Izvor: Wikipedia

...

Nizovi i pokazivači

Niz se deklariše tako što se navodi tip niza, identifikator i broj elemenata.

Na primer int A[10]; čime se rezerviše 10 susednih mesta u memoriji za elemente ovog niza.

Možemo prilikom same deklaracije niza, da dodelimo vrednosti elementima niza (inicijalizacija niza).

int   A[10] = {2,1,3,5,4,6,8,7,9,10}; 
ili
int   A[] = {2,1,3,5,4,6,8,7,9,10}; 

Na ovaj način smo, samom dodelom elemenata niza, odredili njegovu dužinu.

Matrica (dvodimenzionalni niz) se deklariše navođenjem dve dimenzije int A[2][3];

Prilikom deklaracije, mogu se dodeliti vrednosti elementima matrice (inicijalizacija matrice), ali sme da se izostavi samo prva dimenzijaint A[][3] = { { 1, 2, 3 }, { 0, 1, 2 } };

Prilikom deklaracije niza, u memoriji se rezerviše onoliko lokacija, koliko niz ima elemenata i još jedna lokacija plus, pokazivačkog tipa, koja čuva adresu prvog elementa niza. Prilikom deklaracije

int   A[10];

promenljiva A bez indeksa je pokazivač na prvi element niza A[0], tj. A ≡&A[0]. Adresu i-tog elementa niza dobijamo kao A+i≡&A[i].

Prilikom učitavnja i-tog elementa niza, umesto komande scanf_s("%d", &A[i]);možemo koristiti scanf_s("%d", A+i);

Za pristup i-tom elementu niza preko adrese koristi se operator dereferenciranja *(A + i) ≡A[i] .

Prilikom deklaracije matrice, pored memorijskog prostora za elemente matrice, rezerviše se jedno mesto za pokazivač na niz pokazivača.

Svaki pokazivač iz niza pokazuje na početak jednog reda matrice.

Deklaracijom int A[2][3]; sam identifikator matrice A, je pokazivač na element pokazivačkog tipa, pa je A tipa (int*)*A; A[2] je pokazivač na prvi element trećeg reda matrice, i A[2] je po tipu niz (niz elemenata trećeg reda matrice A).