4. Nizovi

Podeli svoje utiske o poglavlju na anketi OVDE.

Preduslovi za rad:

Potrebno je osnovno znanje iz naredbi selekcije i ciklusa.

Do sad je bio uveden koncept promenljive, koja ima jedinstveno ime, sadrži jednu vrednost i određene je veličine. Veličina i vrednost zavise od tipa promenljive. Nizovi predstavljaju više uzastopnih lokacija u memoriji, gde svaka poput promenljive ima svoju vrednost i sve su iste veličine. Ukoliko se upotrebi analogija gde promenljiva predstavlja jednu "kućicu" u memoriji, niz je čitava ulica tipskih kuća (sve liče jedna na drugu). To je zato što nizovi, kao i promenljive, imaju svoj tip i svi članovi niza su tog tipa. Članovi se nazivaju i elementima niza.

Primer deklaracije niza:

int niz[10];

Ova deklaracija napraviće niz od 10 celobrojnih elemenata.

Njima nije moguće pristupiti odjednom, već pojedinačnim elementima:

niz[0] = 5;
int a = niz[2];

Napomena:

Indeksiranje nizova u programskom jeziku C kreće od 0! Za niz od 10 elemenata, validni indeksi su od 0 do 9!

4.1. Osnovni primeri rada sa nizovima

Tokom rada sa nizovima moguće je raditi isključivo sa njegovim pojedinačnim elementima, ne sa celim nizom odjednom. Da bi se obradio svaki element niza, potrebno je koristiti for petlju.

Pretpostavimo da imamo deklaraciju promenljive i i niza celobojnih vrednosti niz na sledeći način:

    int i, niz[5];

Primer upisa vrednosti u niz sa standardnog ulaza:

    for(i = 0;i < 5;i++)
    {
        printf("niz[%d]: ", i);
        scanf("%d", &niz[i]);
    }

Primer ispisa vrednosti iz niza na standardni izlaz:

    for(i = 0;i < 5;i++)
    {
        printf("%d ", niz[i]);
    }

Na primerima se može videti da se promenljiva i koristi u for petlji, njena početna vrednost je 0, a krajnja veličina niza minus 1. Za primer iznad to će biti vrednost 4. U jednoj iteraciji for petlje, određeni element niza biće učitan, odnosno ispisan.

4.2. Korišćenje određenog dela niza

Kod deklaracije niza je njegova veličina navedena unapred, pre kompajliranja. Često se u praksi dešava situacija da postoje slučajevi korišćenja kad je potrebno popuniti samo deo niza. Sa druge strane, dimenzija niza mora podržati slučaj koji traži najviše iskorišćenih elemenata.

Ovakva fleksibilnost postiže se uvođenjem nove promenljive n, koja će označavati broj upotrebljenih elemenata:

#include <stdio.h>

#define MAX_SIZE 30

int main()
{
    int i, n, niz[MAX_SIZE];

    do
    {
        printf("Unesite broj elemenata niza: ");
        scanf("%d", &n);
    } while(n <= 0 || n > MAX_SIZE);
    

    for(i = 0;i < n;i++)
    {
        printf("niz[%d]: ", i);
        scanf("%d", &niz[i]);
    }

    for(i = 0;i < n;i++)
    {
        printf("%d ", niz[i]);
    }

    return 0;
}

Na početku programa unosi se vrednost n. Obavezno je da bude u granicama od 1 do MAX_SIZE, kako bi broj korišćenih elemenata bio unutar granica niza.

Primer rada programa:

Unesite broj elemenata niza: 31
Unesite broj elemenata niza: -5
Unesite broj elemenata niza: 5
niz[0]: 1
niz[1]: 2
niz[2]: 3
niz[3]: 4
niz[4]: 5
1 2 3 4 5 

Prve dve vrednosti koje su unete su izvan dimenzija niza, tako da će one biti odbijene. Od korisnika će se tražiti da unosi vrednosti sve dok ne zada neku koja se nalazi u granicama niza (ovo obezbeđuje do-while petlja u programu).

Napomena:

MAX_SIZE je definisano putem #define pretprocesorske direktive.
Ona će pre samog kompajliranja zameniti svuda gde se nalazi MAX_SIZE sa vrednošću koja joj je pridružena.
Funkcionalnost je slična kao kad se kod tekst editora izabere opcija "Find and replace".
Moguće je videti kod nakon pretprocesiranja pomoću sledeće komande: gcc -E kod.c

Primer koji traži srednju vrednost unetih elemenata niza:

#include <stdio.h>

#define MAX_SIZE 30

int main()
{
    int i, n, niz[MAX_SIZE];

    do
    {
        printf("Unesite broj elemenata niza: ");
        scanf("%d", &n);
    } while(n <= 0 || n > MAX_SIZE);
    

    for(i = 0;i < n;i++)
    {
        printf("niz[%d]: ", i);
        scanf("%d", &niz[i]);
    }

    int suma = 0;
    for(i = 0;i < n;i++)
    {
        suma += niz[i];    // isto sto i "suma = suma + niz[i];"
    }

    printf("Srednja vrednost vrednosti iz niza je: %.2lf\n", (double)suma / n);

    return 0;
}

Ispis programa:

Unesite broj elemenata niza: 5
niz[0]: 3
niz[1]: 6
niz[2]: 4
niz[3]: 7
niz[4]: 2
Srednja vrednost vrednosti iz niza je: 4.40

4.3. Traženje minimalnog/maksimalnog elementa u nizu

Često je neophodno pronaći vrednost najmanjeg, odnosno, najvećeg člana u nizu. Kako je prethodno navedeno, u programskom jeziku C nije moguće odjednom pristupiti svim članovima i pronaći među njima najveći/najmanji element.

Algoritam je sledeći:

1. Pretpostaviti da je neki od članova niza njegov najveći/najmanji element, tako što se njegova vrednost sačuva u posebnu promenljivu (uglavnom se bira vrednost prvog člana niza)

2. Izabrati naredni član niza (uglavnom se ide redom, drugi, treći, četvrti itd.)

3. Uporediti ga sa vrednošću promenljive koja trenutno glasi kao najveća/najmanja

4. Ukoliko je trenutni član niza veći/manji od vrednosti iz prethodnog koraka, postaviti vrednost člana niza kao novu najveću/najmanju vrednost

5. Vratiti se na korak 2. i ponoviti postupak dokle god ima neobrađenih članova niza

Izvršavanje navedenih koraka garantuje da će se nakon prolaska kroz čitav niz, odnosno, obradu svih njegovih članova u promenljivoj koja je namenjena za to naći vrednost najvećeg/najmanjeg elementa. Ovaj algoritam primenljiv je na nizove čiji elementi nisu prethodno uređeni po vrednosti (u rastućem ili opadajućem redosledu).

Primer koji traži maksimalnu vrednost u nizu:

#include <stdio.h>

#define MAX_SIZE 30

int main()
{
    int i, n, niz[MAX_SIZE];

    do
    {
        printf("Unesite broj elemenata niza: ");
        scanf("%d", &n);
    } while(n <= 0 || n > MAX_SIZE);
    

    for(i = 0;i < n;i++)
    {
        printf("niz[%d]: ", i);
        scanf("%d", &niz[i]);
    }

    int maks = niz[0];

    for(i = 1;i < n;i++)
    {
        if(niz[i] > maks)
        {
            maks = niz[i];
        }
    }

    printf("Maksimalna vrednost niza je: %d\n", maks);

    return 0;
}

Ispis programa:

Unesite broj elemenata niza: 5
niz[0]: 4
niz[1]: 2
niz[2]: 7
niz[3]: 1
niz[4]: 3
Maksimalna vrednost niza je: 7

Za traženje minimalne vrednosti u nizu potrebno je obrnuti samo smer relacionog operatora u if naredbi.

4.4. Sortiranje nizova

Sortiranje niza predstavlja uređenje njegovih elemenata tako da oni budu u rastućem ili opadajućem redosledu. Postoji mnoštvo algoritama za sortiranje niza. Ovde će biti prikazana dva, Bubble Sort i Selection Sort. Kod za učitavanje elemenata niza i njihov ispis je izostavljen radi akcenta na samim algoritmima.

Bubble Sort algoritam:

    int i, n, niz[MAX_SIZE];
    int nema_promena, j, tmp;

    for(i = 0;i < n - 1;i++)
    {
        nema_promena = 1;   // pretpostavimo da nece biti promena
        for(j = 0;j < n - i - 1;j++)
        {
            if(niz[j] > niz[j + 1])
            {
                tmp = niz[j];
                niz[j] = niz[j + 1];
                niz[j + 1] = tmp;
                nema_promena = 0;   // desila se promena, nema_promena postaje netacno
            }
        }

        if(nema_promena)
        {
            break;
        }
    }

Kod ovog algoritma najveći/najmanji element "isplivava" na kraj niza nakon jednog prolaska kroz ceo niz (for petlja po j). To se dešava tako što se susedni elementi porede i ako se ispostavi da je prvi veći/manji od drugog, izvršiće se njihova zamena. Čitav postupak ponavlja se n - 1 puta i svaki put je for petlja po j sve kraća, zbog toga što se sa rastom i desilo "isplivavanje" elemenata na njihove pozicije. Bubble Sort je vrlo neefikasan algoritam za sortiranje niza i koristi se isključivo u svrhe učenja zbog svoje jednostavnosti.

Selection Sort algoritam:

    int i, n, niz[MAX_SIZE];
    int indeks_najmanjeg, j, tmp;

    for(i = 0;i < n - 1;i++)
    {
        indeks_najmanjeg = i;

        for(j = i + 1;j < n;j++)
        {
            if(niz[indeks_najmanjeg] > niz[j])
            {
                indeks_najmanjeg = j;
            }
        }

        if(indeks_najmanjeg != i)
        {
            tmp = niz[i];
            niz[i] = niz[indeks_najmanjeg];
            niz[indeks_najmanjeg] = tmp;
        }
    }

Za razliku od Bubble Sort algoritma, Selection Sort traži odgovarajući element desno od i-tog člana. Ukoliko nađe najveći/najmanji, pristupa se zameni i-tog i najvećeg/najmanjeg. Ako se, pak, ispostavi da ne postoji veći/manji od i-tog, zamena elemenata se neće dogoditi.

Napomena:

U prethodnim primerima algoritama za sortiranje koristi se "petlja u petlji".
Ovaj koncept naziva se "ugneždena petlja" i funkcioniše na način da će se za jednu iteraciju spoljne petlje 
(u primerima po brojačkoj promenljivoj i), unutrašnja petlja izvršiti do n puta (u primerima po brojačkoj promenljivoj j).
Primer korišćenja ugneždene petlje je, recimo, za traženje duplikata u nizovima.

Ukratko rečeno, unutrašnja petlja će izvršiti sve svoje iteracije za jednu iteraciju spoljašnje.

Napomena:

Da bi dva elementa niza zamenili mesta, potrebno je uvesti treću, pomoćnu promenljivu.
Analogija ovome je da, recimo, imate tečnost u dve čaše i želite da prebacite tečnost iz jedne u drugu.
Ovo nije moguće bez korišćenja treće, prazne čaše, u koju ćete, recimo, usuti tečnost iz prve,
zatim prebaciti tečnost iz druge u prvu, koja je pre toga bila prazna, a tečnost iz treće čaše presućete u drugu.

Promenljiva tmp u primerima izigrava treću čašu.