Dinamički niz
Da se podsetimo: Niz je osnovna struktura podataka u programiranju, koja služi za čuvanje većeg broja vrednosti, kojima se onda pristupa preko zadatog indeksa.
Opcioni materijal - za slabije učenike koji ne znaju ništa o nizovima ili za bolje koji žele da se podsete:
Ovde nećemo definisati šta je to niz, i kako se radi sa nizom, pošto smo to radili u prethodnim razredima. Ako niste sigurni i želite da se podsetite osnova o nizovima, možete da pročitate kako je to ukratko objasnio na svom blogu profesor M.Radovanović: LINK: Nizovi u C# programskom jeziku ili da pogledate video na Youtube:
Pojam: Deklaracija niza
U klasičnim programskim jezicima, kao što je C, na početku moramo da deklarišemo niz sa određenim brojem elemenata, tj da obavestimo računar kolika će biti maksimalna veličina niza, da bi računar mogao da odvoji komad memorije za te podatke. Kažemo da "dimenzionišemo" niz - unapred ograničimo broj elemenata.
U novijim programskim jezicima se dešava da ne moramo da dimenzionišemo niz. Međutim, obično moramo da "najavimo" niz: da nekako obeležimo da je nešto niz, a ne neka obična promenljiva. Tada se niz kreira dinamički, i to tokom izvršavanja programa.
Pojam: Alokacija memorije
U prvom slučaju vrši se statička dodela memorijskog prostora. To znači da se u vreme prevođenja programa zna tačan broj podataka koji će biti korišćeni. Kada su nizovi u pitanju, potrebno je znati tačan broj elemenata i veličinu svakog elementa. Podsetite se da je u jeziku C deklarisan niz sa najvećim očekivanim brojem elemenata, što može da dovede do nepotrebnog utroška memorije.
Deo memorije u koji se smeštaju statički definisani podaci naziva se statička zona memorije.
Deo memorije u kojem se vrši dinamička dodela prostora u vreme izvršavanja programa, naziva se dinamička zona memorije, a podaci u njoj su dinamički podaci.
Dinamički podaci nemaju imena, već im se pristupa preko njihovih adresa koje se čuvaju u pokazivačima. Za te podatke koji se dinamički stvaraju u toku izvršavanja programa, treba da postoje statički definisani pokazivači. Dinamički pokazivači se stvaraju na zahtev programera i postoje dok ih on ne uništi ili dok se program ne završi. Pri uništavanju dinamičkog podatka, oslobađa se memorijski prostor.
Dodatni materijal koji bi svi trebalo da pročitate:
Za bolje razumevanje pojmova - alokacija memorije, statička alokacija memorije, dinamička alokacija memorije, curenje memorije pročitajte PRVE DVE STRANE sledeće SKRIPTE (LINK)
Dinamički nizovi
Nizovi se u statičkoj memoriji
definišu najvećim brojem elemenata koji se očekuje, a često je taj broj
prevelik čime je nepotrebno zauzeta memorija. Korišćenjem dinamičke
memorije nizu se dodeljuje memorija koja odgovara trenutnim potrebama
programa. Promena dužine niza je moguća jer pokazivač na niz može da
pokazuje na memoriju proizvoljne veličine.
Kod statičkih nizova veličinu niza zadajemo u toku pisanja programa, a
kod dinamičkih za vreme izvršavanja programa. Nakon dodele memorije rad
sa dinamičkim nizovima je isti kao sa dosadašnjim statičkim nizovima.
U različiti programskim jezicima, ovo se izvodi na različite načine.
U slučaju programskog jezika C:
Dinamička dodela memorije zavisi od potreba programa, i to kontroliše programer, korišćenjem naredbi malloc, calloc, realloc. Kako to funkcioniše u programskom jeziku C i kako se pravi dinamički niz, detaljnije je objašnjeno na jednom blogu iz nastave informatike: Динамичка додела меморије- Динамички низови (LINK).
U slučaju programskog jezika C++ : Uvodi se operator new kojime se vrši dinamička alokacija memorije. Iza operatore new obično ide ime nekog tipa. On će tada potražiti u memoriji slobodno mesto u koje bi se mogao smestiti podatak navedenog tipa. Ako se takvo mesto pronađe, operator new će kao rezultat vratiti pokazivač na određeno mesto u memoriji, a u suprotnom će da se javi izuzetak. Na primer: Pokazivac = new int[5] - naredba će potražiti prostor u memoriji koji je dovoljan da prihvati 5 celobrojnih promenljivih i u slučaju da pronađe takav prostor, dodeliće njegovu vrednost pokazivaču "Pokazivac". Znači "Pokazivac" pokazuje na prvo mesto niza! Ovako kreiranom "dinamičkom" nizu možemo pristupiti samo preko pokazivača.
Za one koji žele da znaju više: Za detaljno objašnjenje o dinamičkoj alokaciji memorije i dinamičkim nizovma, sa primerima, u programskom jeyiku C++, možete pročitati predavanje sa elektrotehničkog fakulteta u Sarajevu: Predavanje 5.
U slučaju programskog jezika C#:
Prostor za elemente niza u jeziku C# može da se dodeljuje isključivo dinamički u vreme izvršavanja programa. Takvi podaci se nazivaju dinamički podaci, a deo memorije gde se oni uskladištavaju, dinamička zona memorije.
Znači: Svaki niz u programskom jeziku C# se realizuje kao dinamički niz.
Da se podsetimo od prethodne godine:
Neki primeri definisanja nizova:
int [] a = new int [5];
float [,] b = new float [3,4];
char [,,,] c = new char [4,5,6];
Tip rezultata operatora new je pokazivač (upućivač) na niz koji ima onoliko dimenzija koliko je zareza unutar zagrada i +1. Vrednost rezultata može da se dodeli ranije definisanoj nizovnoj promenljivoj ili kao inicijalizator pri definisanju nove promenljive (što je slučaj u prethodnom primeru).
Kao rezultat dodele memorije zauzima se blok u memoriji. Npr u trećem primeru se zauzima 4 x 5 x 6 x koliko zauzima jedan podatak tipa char. Elementi se unutar bloka smeštaju tako da se najbrže menja poslednji indeks, mada to za programera nije važno.
Ako dodela memorije ne uspe, baca se izuzetak tipa OutOfMemoryException. Ako se taj izuzetak ne obrađuje od strane programa, program se prekida (izuzetke smo radili prošle godine).
Ono što je karakteristično za C#, je da se svaki bajt memorijskog prostora koji se zauzme operatorom new popunjava nulama. (To nije bio slučaj kod C++, gde se na početku u memoriji nalazi ono što je zatečeno na tim lokacijama prilikom zauzimanja memorija - čitaj: "đubre".)
Dalji rad sa nizom u programskom jeziku C# može da ide kao što smo radili prethodnih godina, isto kao u C ili C++: pristupanje pojednim elementima sa ImeNiza[indeks], korišćenje adresne aritmetike, ...
Ako se kao naziv niza ne navede adresa u memoriji, ako je null, javiće se izuzetak tipa NullReferenceException. Ako je vrednost indeksa van dozvoljenog opsega, javlja se izuzetak tipa IndexOutOfRangeException.
Ukupan broj elemenata niza (proizvod dužina po svim dimenzijama) može da se dobije izrazom koji vraća int:
ImeNiza . Length
Broj dimenzija (rang) niza može da se dobije izrazom koji vraća int:
ImeNiza . Rank
Dužina koju ima neka konkretna dimenzija niza d (d = 0, 1, ..., ImeNiza.Rank-1), moće da se dobije izrazom koji vraća int:
ImeNiza . GetLength ( d )
Nizovne promenljive mogu da se međusobno dodeljuju operatorom =. Pošto su promenljive u stvari pokazivači (ime svakog niza pokazuje na prvi element u nizu), ako se jedna nizovna promenljiva dodeli drugoj dobiće se da više promenjivih pokazuje na isti niz u dinamičkoj zoni memorije. Tada kažemo da se jedan niz dodeljuje drugom. Znači, tom se prilikom ne pravi kopija samog niza, već svi pokazuju na isti niz.
Pazite: nizovnoj promenljivoj može da se dodeli i konstanta null, posle čega ona ne upućuje ni na šta. Dok joj se ne dodeli novi niz (tačnije - pokazivač na neki niz), nije dozvoljen ni pristup elementima niza, ni dohvatanje broja elemenata nizam ranga niza, ni dužine u bilo kojoj dimenziji. Ako pokušate, javiće se izuzetak !
Dodatno: Upoređivanje dve nizovne promenljive jeste moguće, operatorima == i !=. Ta se u stvari poredi da li dva pokazivača na početak niza pokazuju na istu lokaciju u memoriji, sa istim tipom podataka, ili da li su oba null.
Kako se prolazi svaki element niza?
Može isto kao u C ili C++, pomoću for petlje, ali je elegantnije koristiti petlju foreach:
foreach (tipElementa in ImeNiza) naredba
Sakupljač otpadaka:
Potrebno je osloboditi memoriju koja je dodeljena podacima koji više nisu potrebni, da bi se napravilo mesta za podatke koji će biti potrebni kasnije.
Kod programskog jezika C se to radilo ručno, od strane programera, dok u C# o tome automatski vodi računa komponenta garbage collector (sakupljač otpadaka).
Memorija koja je bila dodeljena promenljivima prilikom njihovog definisanja oslobađa se u trenutku napuštanja dosega njihovih identifikatora. U slučaju pokazivačkih tipova, kao što su nizovi, time se oslobađa samo memorija za pokazivač na niz, ali ne i memorija u dinamičkoj zoni memorije koja je dodeljena operatorom new. Za to postoji sakupljač otpadaka (engl garbage collector), koji u pozadini i nevidljivo za programera aplikacije, automatski oslobađa zauzete delove memorije koji više nisu u upotrebi.
Od dinamičkih struktura podataka, na sledećim časovima dolaze na red: lista, stek , red, i možda sentinel lista.