Niz kao struktura podataka
Niz je osnovna struktura podataka u programiranju, koja služi za čuvanje većeg broja vrednosti, kojima se onda pristupa preko zadatog indeksa. U ovom tekstu ćemo opisati praktičan problem obrade većeg broja podataka koji najjednostavnije rešavamo upotrebom nizova. Takođe ćemo se upoznati i sa pojmom matrice (dvodimenzionalnog niza).
Vidite, čim počnemo da pravimo malo ozbiljnije programe, ukazaće nam se potreba da radimo sa malo većom količinom podataka. Zamislite da je potrebno napraviti animaciju desetak sprajtova na ekranu, izvršiti pomeranje geometrijskog oblika koji ima 15-tak temena i slično.
Ako "vladamo" samo promenljivama, morali bismo da koristimo novu promenljivu za svaku vrednost koju želimo da obradimo. Glavna ideja je da ovakav posao nekako automatizujemo, da ne bismo morali da radimo "ručno" sa svakom promenljivom pojedinačno.
Manipulacija velikim brojem podataka
Animacija objekata
Hajde da vidimo kako bi sve ovo izgledalo na primeru "igre" gde imamo npr. 10 objekata na različitim pozicijama na ekranu i svaki želimo da pomerimo.
Svaki sprajt na ekranu ima x i y koordinatu. Pošto imamo 10 sprajtova, za svaki od njih moramo beležiti obe koordinate, odnosno moramo negde smestiti po dva broja za svaki sprajt. Recimo da se svi sprajtovi moraju pomeriti udesno za po 20 tačkica. To znači da X koordinatu svakog sprajta povećavamo za 20. To bi moglo izgledati ovako:
ax = ax + 20; bx = bx + 20; cx = cx + 20; dx = dx + 20; ...
Ovaj deo programa izgleda užasno. Ne samo što je program ogroman, nego je i nepregledan, lako se greši, a teško ispravlja. Zamislite kako bi bilo da treba da animiramo 150, a ne samo 10 sprajtova! A tek kako bi izgledala provera da li je neki od sprajtova stigao do kraja ekrana, ili da li su se neka dva sprajta sudarila...
Još jedan veliki problem je ako želimo da napravimo program koji funkcioniše čak iako ne znamo unapred koliko ćemo imati sprajtova, već želimo da to zavisi od dešavanja u programu ili je u pitanju broj koji treba da unese sam korisnik.
Ideja!
Prvo što nam pada na pamet je da bi ovo jako jednostavno moglo da se odradi pomoću ciklusa. Kada bismo promenljivama koje sadrže koordinate dali nazive:
x1, x2, x3...
y1, y2, y3...
I onda umesto:
x1 = x1 + 20; x2 = x2 + 20; x3 = x3 + 20; ...
Uradimo nešto kao...
for (i = 1..10) { xi = xi + 20; }
Evo kakva je ideja - napravimo ciklus sa brojačkom promenljivom (npr. i), koji ide od 1 do 10 (ili koliko treba), a onda menjamo naziv promenljive tako što na "x" dodamo to i, pa u prvom prolasku kroz ciklus radimo sa promenljivom x1, u drugom sa x2, u trećem sa x3... Kad bi tako moglo - bilo bi idealno. Bukvalno smo u par linija programa rešili nešto što bismo radili u 10 ili 150 programskih linija. Na žalost, ovakva manipulacija nazivom promenljive je nemoguća.
Međutim, ideja je odlična, jedino što mora da se ostvari na drugačiji način.
Rešenje našeg problema je jedna struktura podataka (način beleženja veće količine podataka u memoriji), koja se zove niz (eng. array). Videćemo da je niz u stvari nešto što zaista liči na numerisane promenljive, kakve smo opisali kada smo pokušavali da smislimo rešenje problema.
Inače, niz je najpoznatija i najkorišćenija struktura podataka - isto tako i najjednostavnija za učenje. Dakle, niz je struktura podataka u kojoj se pod jednim nazivom (jednom promenljivom) može zabeležiti više vrednosti, kojima se pristupa preko indeksa (odnosno rednog broja).
Svaka pojedina vrednost u nizu se naziva elemenat ili član niza. Tako bi niz sa 5 elemenata (od kojih svaki sadrži recimo neki string) u memoriji izgledao npr. ovako:
| Indeks | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Vrednost | "Milan" | "Jovan" | "Petar" | "Lazar" | "Zoran" |
Svakom elementu niza pristupamo preko njegovog indeksa koji (najčešće) navodimo u uglastoj zagradi. To bi značilo, da ako niz a ima N elemenata, onda bi sve to izgledalo ovako:
| Indeks | 1 | 2 | 3 | ... | N |
|---|---|---|---|---|---|
| Element | a[1] | a[2] | a[3] | ... | a[N] |
| Vrednost | "Milan" | "Jovan" | "Petar" | ... | "Zoran" |
Obavezno pravite razliku između sledeće dve stvari:
| a1 | Obična promenljiva koja se zove a1. |
| a[1] | Element niza a sa indeksom 1. |
Ok, zašto su nam nizovi toliko važni? Jednostavno, kad malo razmislimo - indeksi su celobrojne vrednosti. To znači da kao indeks ne moramo da zadamo samo bukvalan broj, npr. a[5], već to može biti i promenljiva (koja sadrži celobrojnu vrednost) kao npr. a[i] ili čitav izraz (čiji je rezultat celobrojna vrednost), kao npr. a[x+2]. Ovo nam otvara ogromne mogućnosti za automatizaciju rada sa velikom količinom podataka.
Primer korišćenja nizova
Animacija više objekata uz pomoć nizova
Dakle, sada ćemo predstaviti primer u kome animiramo veći broj krugova sa jedne strane grafičkog okvira na drugu. Cela animacija se svodi na uzastopno menjanje X koordinate (pomeranje je po horizontali - s desna nalevo) i iscrtavanje oblika na novoj poziciji.
Pogledajmo prvo suštinski deo algoritma - ono što je poenta cele ove lekcije.
x = array(100);
...
for (i = 1..N) {
x[i] = x[i] - 20;
crtanje(x[i],y[i]);
}
Naravno, ovo je samo ono najvažnije. Sada ćemo predstaviti kompletan algoritam u pseudo-kodu kojim pomeramo 30 kružića, i to neke od njih sporije, a neke brže (tako postižemo i efekat dubine). Nemojte se plašiti ako vam algoritam izgleda komplikovano - da bi animacija bila kompletna, moramo razmišljati i o raznim stvarima koje služe kao "podrška" osnovnom algoritmu:
- Koje su početne pozicije kružića? Moramo ih prvo postaviti na osnovu slučajnih brojeva.
- Koji kružići će se pomerati brže, a koji sporije? Trebalo bi da se razlikuju i po boji i veličini.
- Kada brišemo grafički okvir, a kada zadajemo prikaz onoga što smo zadali da se nacrta?
- Šta se dešava kada kružić "ispadne" iz grafičkog okvira? Moramo da ga "premotamo" na desnu stranu i izračunamo mu novu Y poziciju
Sve ovo čini da naš osnovni algoritam bude malo "ugušen" svim tim dodatnim naredbama, ali one su neophodne kako bi sve radilo kako treba. Pošto se animacija odvija beskonačno, zahvaljujući while ciklusu, kliknite na dugmence za zatvaranje (X) (iza grafičkog okvira) kako bi se izvršavanje prekinulo.
x = array(50); y = array(50); n=30; m=n div 2;
for (i=1..n) { x[i] = trunc(rand()*(_WIDTH-50)); y[i] = trunc(rand()*(_HEIGHT-40))+20; }
color("#000");
while (true) {
cls("#000");
for (i = 1..n) {
if (i<m) { off=4; boja="#da8"; s=5; } else { off=8; boja="#ffc"; s=10; }
fill(boja);
ellipse(x[i],y[i], s,s);
x[i] -= off;
if (x[i]<-30) { x[i] += _WIDTH+30; y[i] = trunc(rand()*(_HEIGHT-40))+20; }
}
graphic();
}
Dakle deluje malo komplikovano, ali ne brinite, ovo i nije baš početnički primer. Više smo hteli da pokažemo jednu praktičnu primenu nizova, koja bi svima delovala zanimljivo. Poenta cele priče je da ovakav program ne bi mogao da se uradi bez korišćenja nizova u kojima čuvamo koordinate kružića.
Da biste pokrenuli algortitam, kliknite na dugmence Start.
Priprema niza
U klasičnim programskim jezicima, nizove moramo da deklarišemo na određen broj elemenata, odnosno da obavestimo računar koliko će niz maksimalno biti velik. Ovo je zato što je niz generalno "primitivna" struktura - praktično samo komad memorije koju računar unapred odvoji za podatke.
Međutim, u modernim programskim jezicima često ne moramo da "dimenzionišemo" niz (tj. da unapred ograničimo broj elemenata), ali isto tako obično moramo da ga "najavimo", tačnije da nekako obeležimo da je nešto niz, a ne obična promenljiva. Niz se tada kreira dinamički, tokom izvršavanja programa.
U našem pseudokodu koristimo funkciju array() da odvojimo memoriju za niz. Bitno je da ovo uradimo pre nego što počnemo da koristimo niz.
Prednosti i nedostaci nizova
Zavisno od jezika, nizove obično moramo unapred deklarisati, i to tako što navedemo koliko će niz imati elemenata. U takvim programskim jezicima (C, Java, Pascal/Delphi...), moramo navesti i kog su tipa članovi niza. To znači da se još pri prevođenju programa na mašinski jezik, odvaja memorija za niz. Pošto su svi elementi istog tipa, svaki zauzima istu količinu memorije, tako da se pozicija svakog člana lako računa na osnovu indeksa. Samim tim nizovi su veoma efikasni i brzi.
Međutim, očigledno je da nizovi nisu fleksibilni i mogu biti memorijski zahtevni. Pošto moramo unapred da odredimo broj članova niza, unapred nam je postavljeno ograničenje - nizovi mogu tokom izvršavanja programa imati manje, ali ne i više elemenata nego što je navedeno pri deklaraciji. Da bi bili spremni na svaku eventualnost, programeri često moraju zahtevati dosta više elemenata nego što je zaista potrebno. Samim tim se često zauzima previše memorije.
Kao što smo malopre pomenuli, moderni programski jezici uvode tzv. dinamičke nizove (JavaScript, PHP, Delphi...) za koje nije neophodno unapred odrediti broj elemenata i u koje se tokom izvršavanja programa mogu dodavati elementi po potrebi. Neki programski jezici čak i potpuno napuštaju koncept klasičnih nizova i uvode surogate poput listi (Python). Rad sa ovakvim strukturama podataka je memorijski efikasan, ali može biti sporiji u odnosu na klasične nizove (zavisno od implementacije liste).
Matrice
E, sada se možda pitate - da li elementi niza moraju biti samo nekog prostog tipa (brojevi, stringovi...)? Odgovor je ne! Nizovi mogu sadržati i elemente kompleksnih tipova, kao što su strukture podataka, pa samim tim - elementi niza mogu biti drugi nizovi.
Takvu strukturu, u kojoj su elementi niza podnizovi, nazivamo matrica. Pogledajmo kako izgleda jedna dvodimenzionalna matrica, dimenzija 3x4:
| a | j | ||||
| 1 | 2 | 3 | 4 | ||
| i | 1 | ||||
| 2 | |||||
| 3 | |||||
Zašto je ovo "2D niz", odnosno "dvodimenzionalna" matrica? Zato što imamo "glavni niz" od 3 elementa, od kojih je svaki podniz sa 4 elementa, kome su vrednosti "obični" podaci. Svakom elementu niza pristupamo pomoću dva indeksa. Tako je "drugi elemenat trećeg podniza" označen indeksima [3,2] (dakle, treći red - druga kolona).
Dakle, j-tom elemetu i-tog podniza pristupamo kao:
a[i][j]
ili
a[i,j]
Način kako se navode indeksi zavisi od programskog jezika - u pseudo-kodu koristimo drugi način, odnosno navodimo listu indeksa odvojenih zarezima. Elementima matrice pristupamo kroz ciklus unutar ciklusa, a primer možete videti već u sledećem tekstu o programiranju sa nizovima.
Naravno, čak ni ovde nije kraj - možemo imati i 3D nizove, gde je svaki elemenat matrice takođe podniz. Suštinski, kompjuter neće imati problem sa višedimenzionalnim nizovima, ali ako uhvatimo sebe da pravimo takvu strukturu podataka, moramo da se zapitamo da li je sve u redu sa našim algoritmom. Pravilo je - koliko imamo "dimenzija" niza, toliko nam indeksa treba za pristup pojedinom elementu.