Niz (struktura podataka)

**Niz** u programiranju predstavlja složeni tip podataka, sačinjen od nekolicine drugih podataka istog ili različitih tipova. Svaki podatak u nizu se naziva njegovim *elementom*, a svaki element ima svoj *indeks*, odnosno objekat preko kojeg prilazimo tom elementu u nizu.

## Dimenzija
Niz može biti jednodimenzionalan (kada ga zovemo jednostavno *niz*), dvodimenzionalan (kada ga nazivamo *matricom* zbog analogije sa istoimenim matematičkim pojmom), i višedimenzionalan (kocka, četvorodimenzionalna kocka itd.).

Kod jednodimenzionalnog niza, dimenzija se poistovjećuje sa dužinom niza. Npr. kažemo da je niz dimenzije `n`. Kod više dimenzionalnih nizova, međutim, ne postoji pojam dužine, nego se uvijek kaže da je niz dimenzija m x n x ... x z ili (m,n,...,z).

Za niz je bitno poznavati njegove dimenzije da bismo mogli ispravno indeksirati odnosno *dohvatati* njegove elemente.

## Indeksiranje elemenata
Svaki element niza ima onoliko indeksa koliko sam niz ima dimenzija. Tako, element jednodimenzionalnog niza ima jedan indeks, a n-dimenzionalni niz ima n indeksa. Sam indeks je obično cio broj, ali može biti bilo koji objekat.

### Primjer
Ako imamo matricu M dimenzija 4 x 3, onda su njegovi indeksi organizovani kao u donjoj tabeli:

Dakle, indeksiranje se vrši tako što se prvo navede indeks reda koji nam treba a zatim indeks elementa u tom redu. Isto važi i za nizove drugih dimenzija.

U različitim programskim jezicima, a naročito onim koji su preuzeli sintaksu programskog jezika C, nizovi se indeksiraju koristeći operator srednje zagrade ([] ). Tako, umjesto da pišemo M(1,3) kao u gore navedenom primjeru, u C-u i srodnim jezicima ćemo pisati `M[1][3]` a u Paskalu `M[1,3]`.

## Vrste nizova
Po vrsti indeksa niza, nizove obično dijelimo na proste i asocijativne nizove. Prosti nizovi imaju cijele brojeve za indekse koji predstavljaju redne brojeve elemenata u nizu ili podnizovima. Asocijativni nizovi koriste objekte raznih tipova za indekse, ali najčešće riječi (niske). Tako, da bismo indeksirali neki element asocijativnog niza, možemo reći `niz("mama")` da bismo dobili ime majke, ili `niz["direktor"]` da bismo dobili ime ili podatke direktora itd.

Svi programski jezici koji podržavaju nizove podržavaju proste nizove. Ali ne podržavaju svi i asocijativne nizove. Od onih koji ih podržavaju, neki ih imaju ugrađene u sam jezik (npr. PHP) a neki u posebne biblioteke (npr. C++). Čest naziv za asocijativne nizove je *mapa*.

## Nizovi u različitim programskim jezicima
### C
U programskom jeziku C nizovi se implementiraju preko pokazivača. Otuda i posebna sintaksa koju C koristi za nizove, za razliku od ostalih programskih jezika.

C ne podržava asocijativne nizove. Podržava samo obične nizove, i u njima indeks prvog elementa je 0. Posljedično, ako je dimenzija niza `n`, indeks posljednjeg elementa biće `n-1`. Isto tako, kod matrica gornji lijevi element imaće indeks (0,0), a donji desni imaće indeks (m-1,n-1).

Niz se u C-u može formirati na statički i dinamički način.

Pod statičkim podrazumijevamo deklaraciju niza sa fiksnim dimenzijama koje ne možemo mijenjati do kraja postojanja promjenljive. Program će sam brinuti o alociranju odgovarajućeg memorijskog prostora kao i o oslobađanju istog na kraju postojanja promjenljive. Deklaracija izgleda na sljedeći način:

`
<tip elementa> <naziv_promjenljive>[<veličina_niza>];
`

Na primjer, da bismo deklarisali niz `x` od 10 cjelobrojnih elemenata, pisali bismo sljedeći kod:


```c
int x[10];
```


Da bismo deklarisali matricu `M` od 6x4 realnih brojeva, pisali bismo sljedeće:


```c
double M[6][4];
```


Pri deklaraciji statičkog niza imamo mogućnost da ga inicijalizujemo, tj. da dodijelimo
početne vrijednosti njegovim elementima, koristeći vitičaste zagrade:


```c
double y[5] = {1, 2, 4, 5, 7};
```


Pod dinamičkim nizom podrazumijevamo deklaraciju pokazivača odgovarajućeg tipa a zatim ručno alociranje memorije koristeći neku od sistemskih funkcija (`malloc`, `calloc` i drugih). Slijede primjeri:


```c
double * niz; /* deklaracija pokazivača */
int n = 20; /* deklaracija dužine niza */
niz = malloc(n * sizeof(double) );
              /* malloc alocira memoriju i vraća adresu početka zauzetog segmenta.
                 ovu adresu smještamo u pokazivač niz */

/* ... koristimo niz ... */

/* obavezni smo ovako alocirani niz da izbrišemo iz memorije po završetku korištenja */
free(niz );
```


Dinamički alocirani nizovi se mogu za vrijeme rada programa obrisati da bi se alocirao niz većih
ili manjih dimenzija. Takođe, pošto je u C-u obavezno deklarisati promjenljive na početku bloka,
tako i statički nizovi moraju imati dužinu koja je unaprijed poznata. Dinamički alocirani,
međutim, ne moraju; samo pokazivač se mora deklarisati na početku bloka, a funkcija za
alociranje se može pozvati u bilo kom trenutku kasnije, kada saznamo koliki nam niz treba.

Elementima niza prilazimo koristeći sličnu sintaksu kao i kod deklaracije statičkog niza, koristeći
operator srednje zagrade:


```c
int niz[20]; /* deklarišemo jedan statički niz */
int n; /* deklarišemo jednu pomoćnu promjenljivu */
niz[0] = 17; /* dodjeljujemo broj 17 prvom elementu niza */
niz[1] = 18;
n = niz[0]; /* dodjeljujemo promjenljivoj n vrijednost prvog elementa niza */
```


Na isti način se prilazi i elementima višedimenzionalnog niza:


```c
int M[10][3]; /* deklarišemo matricu od 10x3 elemenata */
int n; /* deklarišemo pomoćnu promjenljivu n */
M[0][2] = 17; /* trećem elementu prvog reda dodjeljujemo broj 17 */
n = M[0][2]; /* promjenljivoj n dodjeljujemo treći element prvog reda */
```


### C++
C++ koristi istu sintaksu za deklarisanje statičkih nizova kao i C. Za dinamičko alociranje, međutim, C++ uvodi
novu ključnu riječ `new` koja se koristi i za nizove, opet uz upotrebu srednjih zagrada:


```c
int M[7][8]; // deklaracija statičke matrice
int * niz; // deklaracija pokazivača za niz
niz = new int[20]; // alokacija pomoću operatora new
delete [] niz; // brisanje niza iz memorije se vrši uz pomoć ključne riječi delete i srednjih zagrada
```


Pored podrške za obične nizove, standardna biblioteka C++-a uvodi i biblioteku za rad sa mapama, koje predstavljaju vrstu asocijativnih nizova.

### Paskal
U Paskalu, nizovi su ugrađeni tip promjenljive koji se deklarišu koristeći specijalne ključne riječi i sintaksu
i fizički nemaju nikakvu vezu sa pokazivačima.

Podrazumijevani Indeks prvog elementa niza u Paskalu je 1, ali može biti i bilo koji drugi broj, što
se definiše pri deklaraciji, skupa sa dimenzijom niza.

Paskal koristi ključne riječi `array` i `of` za deklaraciju niza. Slijedi primjer:


```pascal
niz: array[1..10] of integer;
matrica: array[2..6,0..3] of real;
```


Naravno, kao i ostale promjenljive i nizovi moraju biti deklarisani u bloku za deklaraciju, `var`.

Indeksiranje elementa postojećeg niza se vrši koristeći operator srednje zagrade, ali nešto drugačije nego u C-u
kad govorimo o višedimenzionalnim nizovima. Slijedi primjer:


```pascal
niz[1] = 10; {* kod jednodimenzionalnih nizova sintaksa je ista kao u C-u *}
matrica[3,2] = 4; {* kod višedimenzionalnih nizova sintaksa je različita od C-ove *}
matrica[0,1] = 10; {* greška! matrica je definisana da ima indekse od 2 do 6 po prvoj dimenziji i od 0 do 3 po drugoj*}
```


### PHP
PHP ima izuzetno razvijenu podršku za nizove, kako asocijativne tako i obične. Oni takođe predstavljaju dio samog jezika, kao i u Paskalu. Za razliku od C++-ovih mapa, PHP ne podržava objekte klasa da budu indeksi elemenata niza, nego samo cijeli brojevi ili riječi (niske).

Kao i svi ostali tipovi promjenljivih u PHP-u, ni nizovi se ne moraju unaprijed deklarisati, ali se moraju inicijalizovati, koristeći ključnu riječ `array`.


```php
$niz = array(); // promjenljiva niz postaje niz od nula elemenata
$niz2 = array(10, 20, 30 ); // deklarišemo niz od 3 elementa, 10, 20 i 30
```


PHP zapravo obične nizove ne razlikuje od asocijativnih, i koristi istu ključnu riječ `array` i za njih. Asocijativni nizovi se kreiraju na dva načina:
* Koristeći specijalnu sintaksu u inicijalizaciji niza. Ova sintaksa podrazumijeva korištenje operatora `=>`, tako što se za svaki element u inicijalizaciji stavi njegov indeks, zatim već spomenuti operator, zatim vrijednost elementa.
* Indeksirajući nepostojeći član niza, kao da već postoji, i dodjeljujući vrijednost tom novom elementu. Za indeks se koristi riječ, čime niz automatski postaje asocijativan.

Pogledajmo primjere za oba načina:


```php
// prvi način
$porodica = array("mama“ => „Slavica“, „tata“ => „Miodrag“, „bata“ => „Srećko“ );
echo „Moji roditelji se zovu ";
echo $porodica["mama"];
echo " i ";
echo $porodica["tata"];
// Štampa se tekst „Moji roditelji se zovu Slavica i Miodrag“

// drugi način
$porodica = array();
$porodica["mama"] = „Slavica";
$porodica["tata"] = „Miodrag";
$porodica["bata"] = „Srećko";
```


PHP ima i kontrolnu strukturu `foreach` koja služi isključivo za nizove. Ona prolazi kroz svaki element niza i obavlja određenu radnju.

U PHP-u elementi niza mogu biti različitog tipa, što nije karakteristika C-a, C++-a i Paskala-a kod kojih elementi niza moraju imati svi isti tip, što je određeno i samom sintaksom deklaracije tipa. Ovo, međutim, liči na ponašanje većine drugih skriptnih jezika, kao što je Javaskript, Perl i drugi.

### Javaskript
Javaskript nizove posmatra kao objekte ugrađene klase `Array`. Kao takvi, nizovi imaju svoje metode, atribute, podliježu operatoru `delete` a kreiraju se pozivanjem konstruktora klase `Array` operatorom `new`. Slijede primjeri:


```javascript
var niz = new Array(); // kreiramo niz
niz[0] = 10; // novi element pravimo tako što mu jednostavno dodijelimo vrijednost na željenom indeksu
niz[100] = 20; // elementi se ne moraju kreirati „redom“, nego možemo da dodijelimo vrijednost
                       // direktno n-tom elementu, da bi niz automatski porastao na dužinu n+1
alert(niz.length); // atribut length uvijek oslikava trenutnu dužinu niza
delete niz; // brišemo niz iz memorije brauzera
```


Javaskript ne podržava asocijativne nizove, ali se operatori srednjih zagrada ponekad koriste na način da liči da podržava. Naime, u Javaskriptu je sintaksa `Objekat.atribut` ekvivalentan sa `Objekat["atribut"]`. Ova sintaksa se ponekad koristi za generisanje imena atributa objekta neke klase, ali ne predstavlja asocijativne nizove.

## Primjena
Nizovi se koriste u mnogim situacijama kada je potrebno najprije u memoriji sačuvati čitavu grupu podataka da bi se nad njom mogla obaviti određena operacija. Tipičan primjer je sortiranje elemenata nekog skupa - da bismo provjerili da li postoji veći element od nekog elementa, moramo ih sve imati na raspolaganju. A da bismo ih sve imali na raspolaganju, moramo imati neku strukturu podataka zgodnu za to. To može biti binarno stablo, dinamička lista, ali može i niz, ako je broj podataka relativno mali.

Druge primjene nizova su:
* rad sa matematičkim matricama (višedimenzionalni nizovi)
* rad sa tabelama za pretraživanje
* bilo koja situacija kada imamo skup srodnih podataka za čuvanje u memoriji radi kasnije upotrebe

## Srodne strukture podataka
Najsrodnija struktura podataka nizu je dinamička lista. U različitim programskim jezicima ona se implementira na različite načine, ali je osnovna sličnost sa nizovima njena linearnost. Štaviše, u nekim skriptnim jezicima se obični nizovi implementiraju preko dinamičke liste, da ne bi bili ograničenog kapaciteta.

Asocijativni nizovi se u većini jezika implementiraju preko binarnog stabla jer ono ima brz algoritam pretrage, što je neophodno za brz pronalazak elementa sa određenim indeksom.

## Vanjske veze