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:

M(1,1)	M(1,2)	M(1,3)
M(2,1)	M(2,2)	M(2,3)
M(3,1)	M(3,2)	M(3,3)
M(4,1)	M(4,2)	M(4,3)

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:

int x[10];

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

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:

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:

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:

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:

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:

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:

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:

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.

$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:

// 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:

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.

Spoljašnje veze

Niz (struktura podataka) na Wikimedijinoj ostavi