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 gorenavedenom 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("мама") da bismo dobili ime majke, ili niz["директор"] 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:

<тип елемента> <назив_промјенљиве>[<величина_низа>];

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; /* декларација показивача */
int n = 20; /* декларација дужине низа */
niz = malloc(n * sizeof(double) );
              /* malloc алоцира меморију и враћа адресу почетка заузетог сегмента.
                 ову адресу смјештамо у показивач niz */

/* ... користимо низ ... */

/* обавезни смо овако алоцирани низ да избришемо из меморије по завршетку кориштења */
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]; /* декларишемо један статички низ */
int n; /* декларишемо једну помоћну промјенљиву */
niz[0] = 17; /* додјељујемо број 17 првом елементу низа */
niz[1] = 18;
n = niz[0]; /* додјељујемо промјенљивој n вриједност првог елемента низа */

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

int M[10][3]; /* декларишемо матрицу од 10x3 елемената
int n; /* декларишемо помоћну промјенљиву n */
M[0][2] = 17; /* трећем елементу првог реда додјељујемо број 17 */
n = M[0][2]; /* промјенљивој n додјељујемо трећи елемент првог реда */

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]; // декларација статичке матрице
int * niz; // декларација показивача за низ
niz = new int[20]; // алокација помоћу оператора new
delete [] niz; // брисање низа из меморије се врши уз помоћ кључне ријечи delete и средњих заграда

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; {* код једнодимензионалних низова синтакса је иста као у C-у *}
matrica[3,2] = 4; {* код вишедимензионалних низова синтакса је различита од C-ове *}
matrica[0,1] = 10; {* грешка! matrica је дефинисана да има индексе од 2 до 6 по првој димензији и од 0 до 3 по другој*}

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(); // промјенљива niz постаје низ од нула елемената
$niz2 = array(10, 20, 30 ); // декларишемо низ од 3 елемента, 10, 20 и 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:

// први начин
$porodica = array("мама“ => „Славица“, „тата“ => „Миодраг“, „бата“ => „Срећко“ );
echo „Моји родитељи се зову ";
echo $porodica["мама"];
echo " и ";
echo $porodica["тата"];
// Штампа се текст „Моји родитељи се зову Славица и Миодраг“

// други начин
$porodica = array();
$porodica["мама"] = „Славица";
$porodica["тата"] = „Миодраг";
$porodica["бата"] = „Срећко";

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 Паскала-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(); // креирамо низ
niz[0] = 10; // нови елемент правимо тако што му једноставно додијелимо вриједност на жељеном индексу
niz[100] = 20; // елементи се не морају креирати „редом“, него можемо да додијелимо вриједност
                       // директно n-том елементу, да би низ аутоматски порастао на дужину n+1
alert(niz.length); // атрибут length увијек осликава тренутну дужину низа
delete niz; // бришемо низ из меморије браузера

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.