nav_dugme codeBlog codeBlog
  • početna Početna stranica
  • Sačuvani članci Sačuvani članci
  • Učionica
  • Saveti
  • Zanimljivosti
  • Kontakt

Strukture podataka

Facebook LinkedIn Twitter Viber WhatsApp E-mail
zoom_plus zoom_minus bookmark

Uvod

Za postizanje optimalnih rezultata u programiranju, nije dovoljno samo da iza algoritama stoje najoptimalnije ideje, već je neophodno i da sami podaci nad kojima algoritmi operišu, budu formatirani na najefikasniji način.

U praktičnom smislu, pojam struktura podataka, označava kolekciju međusobno povezanih podataka koji su u memoriji zapisani na način koji omogućava da se odgovori na prethodno postavljen zahtev - pri čemu posebno važnu ulogu imaju relacije među podacima i operacije koje se tipično vezuju za određenu strukturu (umetanje elemenata u listu, pretraga u stablu, uklanjanje elementa sa steka i sl).

U apstraktnom smislu, pojam 'struktura podataka' označava sam format koji je korišćen za zapis.

Strukture podataka se najčešće implementiraju kao sistemi međusobno povezanih "čvorova" * (eng. node), međutim, svakako su prisutni i drugi vidovi povezivanja.

* Videćemo u nastavku šta navedeni pojam označava, to jest, kako se čvorovi implementiraju.

Neke strukture podataka, kao što su statički nizovi, liste, stekovi, redovi za čekanje i stabla (o kojima govorimo u ovom tekstu i drugim člancima), dobro su poznate i često korišćene, pa je na početku ozbiljnijeg bavljenja programiranjem potrebno prvo se upoznati upravo sa navedenim strukturama.

U međusobnom povezivanju čvorova, važnu ulogu igraju pokazivači, pa ćemo se u članku detaljno upoznati i sa pokazivačima u C-u (implementacija je veoma slična i u drugim jezicima).

Klasifikacija struktura podataka

Za sam početak (zarad boljeg razumevanja), upoznaćemo se sa klasifikacijom struktura podataka, preko nekoliko najvažnijih kriterijuma.

Podela struktura podataka prema topologiji

Prema topologiji (tipu veza između podataka), strukture podataka mogu biti:

  • linearne
  • razgranate
  • umrežene

Linearne strukture podataka

Kod linearnih struktura podataka, podaci ("čvorovi"), poređani su jedan za drugim, bez grananja ili 'povratnih veza':

Linearne strukture podataka
Slika 1. - Linearne strukture podataka - podaci su poređani jedan za drugim.

Primeri linearnih struktura podataka su: nizovi, liste, stek, red za čekanje.

Razgranate strukture podataka

Razgranate strukture podataka ('stabla'), odlikuje hijerarhijski raspored elemenata.

Bilo koji čvor može biti povezan sa proizvoljnim brojem drugih čvorova, * ali - samo pod uslovom da su u pitanju čvorovi sa sledećeg nivoa hijerarhije (ni u slučaju razgranatih struktura, nema 'povratnih veza'). **

Shodno navedenom, na vrhu hijerarhije nalazi se jedan, 'koreni' čvor (od koga počinju pretrage, obilasci i ostale operacije).

Razgranate strukture podataka
Slika 2. - Razgranate strukture podataka - podaci su poređani u obliku stabla (što je istovremeno drugi, mnogo češće korišćen naziv za razgranate strukture) - bez povratnih veza i veza sa susednim podstablima.

* Određeni čvorovi u stablu, (naravno) moraju biti i bez potomaka, a izraz koji se koristi za čvor bez potomaka je - "list" (stablo sa gornje slike sadrži četiri lista).

Izraz za povezani čvor sa prethodnog nivoa strukture je - 'predak' (ili, 'roditelj'), dok je izraz za povezani čvor sa narednog nivoa strukture - 'potomak' (ili, 'dete').

** Ako čvorove stabla (u kontekstu dozvoljenih i nedozvoljenih veza), zamislimo kao temena a veze među čvorovima kao duži, nijedna "duž" ne sme zatvoriti "mnogougao" (takođe, u nastavku ćemo se detaljnije osvrnuti na implementaciju čvorova).

Umrežene strukture podataka

Kod umreženih struktura podataka (grafova), bilo koji čvor može biti povezan sa bilo kojim drugim čvorom (pri čemu povratna veza može postojati, ali i ne mora).

Umrežene strukture podataka
Slika 3. - Umrežene strukture podataka - podaci su povezani jedni sa drugima na proizvoljan način.

Preko grafova se u programima može predstaviti: povezanost ulica u gradu, povezanost gradova preko mreže međugradskih puteva, međusobna povezanost sajtova u računarskim mrežama (preko linkova) i sl.

I naravno, na gornjoj slici vidimo više "mnogouglova" (što je u grafovima dozvoljeno).

Podela struktura podataka prema mogućnosti dodavanja i uklanjanja elemenata

Prema mogućnosti dodavanja i uklanjanja pojedinačnih elemenata, strukture podataka se dele na:

  • statičke strukture podataka
  • dinamičke strukture podataka

Statičke strukture, su strukture kod kojih dodavanje i uklanjanje novih elemenata nije moguće (statički nizovi), dok su dinamičke strukture, one koje dozvoljavaju dodavanje i uklanjanje elemenata (liste, stek, redovi, stabla, grafovi i mnoge druge).

Na pojedinim mestima u literaturi, takođe se može naći dodatna podela dinamičkih struktura, na strukture koje dozvoljavaju proizvoljno umetanje i uklanjanje elemenata (liste), i strukture kod kojih je umetanje i uklanjanje elemenata dozvoljeno samo pod određenim okolnostima, odnosno na određenom mestu (stek, red za čekanje).

Kod statičkih struktura, povezanost elemenata ostvaruje se implicitno (posredno), time što susedni elementi zauzimaju susedne lokacije u memoriji, dok se kod dinamičkih struktura povezivanje vrši preko pokazivača (ili tzv. 'referenci', u zavisnosti od implementacije u konkretnom programskom jeziku).

Pokazivači

U članku o objektno orijentisanom programiranju, mogli ste videti nekoliko primera koji prikazuju kako se više pojedinačnih podataka može 'spakovati' u jednu imenovanu celinu - jedan objekat, pa samo još ostaje pitanje: kako omogućiti objektima da 'vide' jedni druge?

Rešenje je (kao što verovatno pretpostavljate s obzirom na naslov odeljka) - korišćenje pokazivača, promenljivih koje su u stanju da skladište memorijske adrese (adrese opšteg tipa i adrese drugih promenljivih).

Pri definisanju klase (koja predstavlja pojedinačni čvor), potrebno je samo da se među polja uvrsti i pokazivač (koji će pokazivati na druge srodne objekte).

Naravno, pokazivači, koji se koriste kao polja unutar objekta, mogu (u opštem smislu), pokazivati i na druge podatke u memoriji, međutim, u kontekstu diskusije o strukturama podataka, to nije od prevelikog značaja (bar za sada).

Pokazivači su u stanju da pokazuju na bilo koju memorijsku lokaciju (odnosno, da čuvaju bilo koju adresu), ali se najčešće koriste za skladištenje memorijskih adresa drugih promenljivih (bilo da su u pitanju osnovni podaci, slogovi ili objekti), pa su stoga u mnogim jezicima (u nekim jezicima - pored pokazivača, u drugim jezicima - umesto pokazivača), uvedene tzv. reference - specijalizovani pokazivači koji mogu pokazivati samo na adrese drugih promenljivih.

.... što je istovremeno: elegantno i praktično rešenje, kao i svojevrstan sigurnosni mehanizam (koji čini programski kod jednostavnijim i čitljivijim).

U programskim jezicima C i C++, pokazivači se označavaju zvezdicom *, a reference znakom ampersend &.

		
int* p = &a;
int& r = &a;
		
	
Slika 4. - Pokazivači i reference u programskom jeziku C/C++ - Dodela adresa.

Vidimo na slici, da pokazivač p pokazuje na adresu promenljive a (ili jednostavnije - pokazuje na promenljivu a), to isto čini i referenca r - i u oba slučaja se adresa dobija preko operatora adresiranja: &.

Kada je potrebno zadati vrednost (podatku na koji pokazuje pokazivač ili referenca), uz promenljivu koja predstavlja pokazivač, koristi se operator *, dok se uz reference ne navodi dodatni operator.

		
int* p = &a;
int& r = &a;

*p = 12;
r  = 12

// Praktično: kao da smo naveli a = 12;
		
	
Slika 5. - Pokazivači i reference u programskom jeziku C/C++ - zadavanje vrednosti.

Pokazivač koji nije 'angažovan' (ne pokazuje na određenu adresu), ima sistemsku vrednost NULL (NULL == "ne pokazuje ni na šta"), a isto važi i za reference.

U određenim jezicima, vrednost "null" se označava kako smo videli, kao NULL (velikim slovima), u nekim jezicima je označena malim slovima, kao null, u nekima kao None (na primer, u Python-u) i sl.

Predavanje argumenata preko pokazivača (referenci)

Iako tema članka nisu pokazivači, prodiskutovaćemo ukratko o tome kako se funkcije (metode), ponašaju u slučaju da parametre definišemo preko pokazivača/referenci, a kako u slučaju kada parametre definišemo kao podatke koji pripadaju nekom od osnovnih tipova (int, float char i sl).

U praktičnom smislu, implementacija bilo koje strukture podataka, gotovo sigurno, podrazumeva korišćenje pokazivača (koji se pojavljuju kao parametri u metodama, koje pripadaju klasama preko kojih su strukture definisane).

Budući da ćemo ovaj članak završiti prikazom implementacije strukture steka u C++-u, diskusija o pokazivačima - i te kako ima praktičan značaj.

Ukoliko pri definisanju parametara funkcije, ne koristimo pokazivače (ili reference), osnovni tipovi podataka (char, int, float), predaju se po vrednosti, što zapravo znači da u telu funkcije nije moguće menjati vrednost promenljive koja je predata kao argument.

Na primer, pri pokretanju sledećeg programa:

		
#include<isotream>

using namespace std;

void promeni(int a)
{
	a = a + 10;
}

int main()
{
	int a = 5;
	promeni(a);
	cout << a;
}
		
	
Slika 6. - Primer pokretanja funkcije čiji se argumenti ne mogu menjati (budući da parametri nisu definisani kao pokazivači ili reference).

.... ispis će biti "5" (budući da je funkciji promeni, predata samo vrednost promenljive a iz funkcije main).

Ukoliko (za razliku od prethodnog primera), parametar definišemo kao pokazivač/referencu, pri pozivu funkcije dolazi do "predavanja (promenljive) po referenci" .....

		
#include<isotream>

using namespace std;

void promeni_pok(int* a)
{
	*a = *a + 10;
}


void promeni_ref(int& a)
{
	a = a + 10;
}

int main()
{
	int a = 5;
	promeni_pok(&a);
	promeni_ref(&a);
	cout << a;
}
		
	
Slika 7. - Direktan pristup parametrima/argumentima funkcija - preko pokazivača.

.... a ovoga puta, ispis je "25", budući da smo pokrenuli obe funkcije, pri čemu svaka od dve funkcije ima direktan pristup promenljivoj a iz funkcije main (pa se zato vrednost predatog argumenta, dva puta uvećava za 10).

Da rezimiramo pravila ....

Ako se pri definisanju funkcije, kao parametar navede podatak tipa int, odnosno, celobrojna promenljiva (ili, u opštijem smislu, "promenljiva koja nije pokazivač/referenca"), pri pozivu kao što je promeni(a); dešava se sledeće: vrednost promenljive a iz pozivajuće funkcije (u gornjem primeru, iz funkcije main), kopira se i dodeljuje lokalnoj promenljivoj a funkcije promeni (kada kažemo "lokalnoj promenljivoj", mislimo na to da je parametar funkcije - u praktičnom smislu - lokalna promenljiva), ali, pošto je vrednost kopirana - prestaje bilo kakva povezanost između lokalne promenljive a iz funkcije main, i parametra a iz funkcije promeni.

Nadamo se da vas nismo zbunili time što smo koristili isti naziv promenljive (a), u obe funkcije (time smo samo hteli da dodatno potcrtamo, to da lokalne promenljive iz jedne funkcije, nemaju veze sa lokalnim promenljivama iz druge funkcije - čak i kada promenljive imaju iste nazive).

Nasuprot prethodnom slučaju, ako se pri definisanju funkcije, kao parametar navede int* a ili int& a, to jest, pokazivač ili referenca na celobrojnu promenljivu, funkciji se, pri pozivu kao što je promeni_pok(&a); ili promeni_ref(&a); ovoga puta predaje adresa promenljive, što znači da lokalna promenljiva a (iz neke od dve navedene funkcije), "pokazuje" na promenljivu a iz funkcije main(), što nadalje znači, da funkcije promeni_pok i promeni_ref - u praktičnom smislu - direktno operišu nad promenljivom a iz glavne funkcije.

Sad je već red da se vratimo na strukture podataka ....

Čvor (node)

Čvor je kolekcija podataka, tipično implementirana kao slog (struct) ili objekat klase, koja sadrži jedan ili više podataka opšteg tipa (osnovni podaci, nizovi, liste, slogovi ili objekti klasa i sl), i jedan ili više pokazivača na srodne čvorove (pri čemu čvor, naravno, može sadržati i pokazivače/reference koji ne pokazuju na srodne čvorove, već na druge podatke, bilo kog tipa).

Struktura čvora
Slika 8. - Struktura čvora ulančane liste: čvor sadrži podatak i pokazivač na druge čvorove i upravo pokazivači omogućavaju povezivanje čvorova na razne načine.

Na gornjoj slici vidimo čvor (najjednostavniji mogući), kakav se tipično sreće u ulančanim listama, a u donjem odeljku možemo videti i programski kod preko koga se prikazani čvor implementira.

		
struct cvor
{
	// Vrednost
	int v;

	// Pokazivač na sledeći čvor
	cvor* sledeci;                 
};
		
	
Slika 9. - Struktura čvora zapisana u programskom jeziku C/C++: vrednost je zapisana preko celobrojne promenljive, a pokazivač (je u stanju da) pokazuje na sledeći čvor.

Dakle, (jedan) čvor je u stanju da pamti adresu drugog, sličnog čvora, drugi čvor (čija je adresa predata prvom čvoru), u stanju je da pamti adresu trećeg čvora, "treći čvor pamti četvrti" ..... što (u praktičnom smislu) znači da možemo kreirati liste proizvoljne dužine.

Kao što smo već pomenuli, čvor može imati i polja koja predstavljaju više pojedinačnih pokazivača na srodne čvorove (što ćemo videti na primeru binarnih stabala), kao i listu (ili liste) pokazivača i sl.

Čak i najprostiji čvor kakav smo videli, nudi znatne mogućnosti kombinovanja, a za početak ćemo sagledati nekoliko najčešće korišćenih struktura podataka (koje smo naveli u uvodu), koje se mogu implementirati preko jednostavnih čvorova sa podatkom i jednim pokazivačem.

U pitanju su:

  • ulančane liste (linked list)
  • magacin, odnosno stek (stack)
  • redovi za čekanje (queue)

Za binarna stabla ćemo već morati da implementiramo čvorove sa dva pokazivača (što ćemo i prikazati u nastavku), a za stabla opšteg tipa se koriste čvorovi sa listama pokazivača.

U ovom tekstu, na konkretne odlike navedenih struktura ćemo se osvrnuti okvirno, a za starije/iskusnije čitaoce, koje tematika struktura podataka zanima u većoj meri (naravno, ne obeshrabrujemo ni ostale; sami ćete odlučiti koliko duboko ste spremni da 'zagazite' :)), spremili smo i zasebne, detaljne članke o većini struktura o kojima u članku pišemo (linkovi u nastavku).

Pre toga ćemo (kao svojevrstan uvod), napraviti osvrt na razlike između statičkih i dinamičkih nizova (jednostavan primer koji ilustruje upotrebnu vrednost struktura podataka koje nastaju povezivanjem čvorova).

Razlike između statičkih i dinamičkih nizova

Najprostija struktura podataka koju smo do sada često koristili, je statički niz (i do sada smo takvu strukturu jednostavno zvali - "niz").

Statički niz je implementiran kao raspon susednih memorijskih lokacija koje se mogu rezervisati i (u smislu pristupa i drugih operacija), koristiti kao svaka druga promenljiva - s tim da se niz pojavljuje kao jedna imenovana promenljiva (sa više indeksa).

.... kao što već znamo (od ranije).

U pitanju je vrlo korisna struktura za smeštaj podataka koja se koristi u mnogim programima, pri čemu očigledno nije implementirana preko povezanih čvorova.

Struktura statičkog niza
Slika 10. - Statički niz čine susedne memorijske lokacije čiji je broj unapred definisan i ne može se menjati.

Osnovna prednost statičkih nizova u odnosu na liste (sa kojima ćemo se upoznati u narednom odeljku), je vreme pristupa određenom elementu ("bilo kom elementu") - i vreme pristupa elementu ne zavisi od veličine niza (to jest, od broja elemenata), međutim - statički niz kao struktura podataka ima i nekoliko očiglednih nedostatka:

  • maksimalni broj elemenata statičkog niza je (praktično) ograničen na oko 500 hiljada
  • veličina niza se ne može menjati naknadno

Prvi nedostatak uslovljen je načinom na koji operativni sistemi upravlja memorijom (u smislu toga koliko stek memorije se može "rezervisati") i takođe, navedena vrednost odnosi se na jedan niz celobrojnih promenljivih (int promenljive su 32-bitne odnosno, zauzimaju 4 bajta), dok bi u slučaju decimalnih brojeva dvostruke preciznosti (double promenljive zauzimaju 8 bajtova), najveći mogući statički niz bio duplo manji (kao i u slučaju kada bismo kreirali dva celobrojna niza maksimalnog kapaciteta).

Rešenje za problem ograničenog kapaciteta je (pretpostavljate već) - kreiranje i upotreba ulančanih lista.

Ulančana lista ('dinamički niz'), predstavlja sistem međusobno povezanih čvorova, u kome su čvorovi linearno poređani jedan za drugim.

Svaki čvor pokazuje na jedan čvor ("sledeći" čvor), pri čemu je dozvoljeno da se čvorovi, proizvoljno (to jest, "dinamički"), dodaju, umeću i uklanjaju * (ali, kao što smo na početku naglasili, nije dozvoljeno kreirati zatvorene 'petlje' u strukturi liste, niti hijerarhijske strukture koje su svojstvena stablima). **

Iako veličina dinamičkih nizova nije ograničena (makar teoretski), dinamički nizovi (razume se), ne mogu imati doslovno neograničen broj elemenata (ne mogu zauzeti ni celokupan kapacitet RAM memorije, a kamoli zaista biti 'neograničeni'), ali, povezivanjem čvorova možemo kreirati liste znatno veće od statičkih nizova. ***

* Dodavanje i umetanje su naizgled slični pojmovi, ali, da budemo precizni:

  • dodavanje = postavljanje novog elementa na kraj liste (tako da dotadašnji poslednji čvor pokazuje na novi čvor)
  • umetanje = postavljanje novog čvora između dva proizvoljna čvora (tako da su čvorovi čija se veza raskida postavljanjem novog čvora, povezani preko novog čvora)

** Doduše, ukoliko koristimo elementarne čvorove sa jednim pokazivačem (kakve i koristimo), kreiranje hijerarhijske strukture - u praktičnom smislu - nije ni moguće.

*** Praktično: pre nego što deklarišemo statički niz od 100 hiljada elemenata, potrebno je da dobro razmislimo o tome da li je takav niz neophodan.

Kreiranje ulančanih lista, od više stotina hiljada elemenata (čak i preko milion) - pod uslovom da imamo na raspolaganju dovoljno RAM memorije - ne predstavlja problem.

Naravno, kreiranje jako velikih lista (osim upotrebne vrednosti), ima i "cenu".

Pristup elementu statičkog niza je algoritam složenosti O(1), dok pristup elementu liste, ima složenost O(n).

U statičkom nizu je svejedno da li pristupamo: prvom, trećem ili hiljaditom elementu; u listama (dinamičkim nizovima) - nije.

Jedini način da pronađemo 131. element u dinamičkom nizu, je da krenemo od prvog elementa i preko pokazivača prelazimo na naredne elemente dok ne stignemo do stotridesetprvog (prvi element "zna" samo gde je drugi, drugi gde je treći, treći je povezan samo sa četvrtim .... 129. sa 130. i na kraju, preko 130. elementa pronalazimo 131. element).

Pored toga, tu je i nezanemarljivo dodatno memorijsko zauzeće koje povlači upotreba pokazivača.

Ali, nije sve 'tako crno' (ni iz daleka) i problematici treba pristupiti konstruktivno.

Umesto da se opterećujemo nedostacima, koristićemo strukture podataka shodno njihovim dobrim stranama:

  • statičke nizove koristićemo za manje kolekcije podataka čija se veličina ne menja
  • liste ćemo koristiti za veće kolekcije podataka u kojima prioritet nije brza pretraga
  • za pretragu (ionako) nećemo koristiti liste, već specijalizovana stabla ili hash mape

Svakako bi bilo lepo da "nekako" možemo kreirati strukturu niza koja ispoljava sve (ranije navedene) prednosti i odbacuje sve nedostatke, ali, dok se to ne desi - postupaćemo u okvirima poznatog i postojećeg. :)

Ulančane liste (Linked List)

Kao što smo već naveli, ulančana lista je zvaničan naziv za implementaciju osnovnog dinamičkog niza, čiji je princip funkcionisanja opisan u prethodnom odeljku.

Još jedna lepa osobina dinamičkih nizova, na koju se do sada nismo osvrnuli, je to što - za razliku od statičkih nizova (gde je takav pristup obavezan) - susedni čvorovi dinamičkih nizova, ne moraju zauzimati susedne lokacije u memoriji, već se raspoređuju proizvoljno po slobodnim delovima memorije (jednostavno, pokazivač nekog čvora "zna" gde je sledeći element, bez obzira na to da li je sledeći element: "odmah pored", "negde u blizini", ili je "daleko").

Dakle, elementi ulančane liste su - u idejnom smislu - poređani "jedan-za-drugim", međutim, kada se podaci zapišu u memoriji, ne postoji 'geometrijski poredak' (koji odgovara idejnom rasporedu elemenata).

Verujemo da ste to i sami pretpostavili, ali, da ipak pomenemo, "za svaki slučaj" (i naravno, isto važi i za druge strukture, o kojima ćemo tek pisati, koje su takođe definisane preko čvorova).

Struktura čvorova ulančane liste
Slika 11. - Struktura čvorova ulančane liste: svaki čvor sastoji se iz podatka i pokazivača (na sledeći čvor). Pronalaženje elementa počinje od prvog čvora (pri čemu svaki čvor "zna" samo za susedni čvor); umetanje i uklanjanje čvorova su mogući na svim pozicijama.

Ulančane liste (kao što smo naveli u prethodnim odeljcima), moguće je proširivati dodavanjem čvorova na kraj, kao i proizvoljnim umetanjem elemenata na "međupozicijama" (a moguće je naravno i uklanjati elemente), pa, ako vas ulančane liste zanimaju u većoj meri, možete ispratiti link prema članku u kome je detaljno opisana implementacija jednostruko ulančane liste (u programskom jeziku C++).

Stek (magacin, stack)

Stek je (gotovo sigurno), najkorisnija jednostavna struktura podataka (mada ne i najzastupljenija; rekli bismo da ta "titula" pripada ulančanim listama).

Za razliku od ulančanih lista, kod kojih je moguće pristupiti proizvoljnom elementu, kod steka se može pristupiti samo poslednjem dodatom čvoru (u cilju dodavanja novog čvora, zarad očitavanja vrednosti poslednjeg čvora ili zarad uklanjanja poslednjeg čvora).

Princip uklanjanja elemenata sa steka poznat je pod skraćenicom LIFO: "Last In - First Out".

Struktura čvorova steka
Slika 12. - Struktura steka: moguće je čitati samo poslednji ubačeni element, ili dodati novi element tako da "prekrije" element koji je do tada bio na vrhu steka.

Stekovi se koriste u algoritmima za prevođenje programskih jezika (recimo Shunting Yard, sa kojim smo se ranije upoznali), za praćenje pozicije u rekurzivnim pozivima, kao i u brojnim drugim okolnostima.

Jednostavnu implementaciju steka za celobrojne vrednosti (u programskom jeziku C++), možete videti u poslednjem odeljku ovog članka.

Redovi za čekanje (Queue)

Redovi za čekanje su, baš kao i stek, struktura podataka od velike važnosti koja se u programiranju koristi veoma često.

Za razliku od steka, u redovima za čekanje je - zarad očitavanja vrednosti čvora ili zarad uklanjanja čvora - moguće pristupiti samo prvom ubačenom elementu (princip uklanjanja elementa iz reda za čekanje poznat je pod skraćenicom FIFO - "First In - First Out").

Dodavanje elemenata se obavlja na suprotnom kraju - preko zasebnog pokazivača.

Struktura čvorova reda za čekanje
Slika 13. - Struktura reda za čekanje (queue): dva zasebna pokazivača, jedan za čitanje (na kraju niza čvorova) i drugi za upis (na početku), omogućavaju upis novih elemenata i čitanje prvog ubačenog elementa. Svi ostali elementi su nedostupni.

U smislu principa po kome funkcionišu, redovi za čekanje u računarskim algoritmima, nalikuju redovima za čekanje koje srećemo u svakodnevnom životu (redovi na kasi u supermarketu, na naplatnim rampama i sl).

Redovi za čekanje se (kao i stekovi), takođe koriste u brojnim algoritmima, a verovatno najpoznatiji primer upotrebe strukture reda za čekanje, je algoritam BFS, u kome se redovi koriste za pamćenje polja koja je potrebno obići nakon polja koje se trenutno obrađuje.

Stabla

Stablo je razgranata struktura podataka, kod koje postoji koreni čvor koji sadrži dva (u slučaju binarnih stabala), ili više pokazivača (u slučaju ostalih), pri čemu nadalje čvorovi potomci (na koje pokazuje koreni čvor), takođe imaju dva ili više pokazivača i pokazuju na svoje potomke.

Da bismo to ilustrovali, za primer ćemo uzeti binarna stabla, čiji su čvorovi sastavljeni iz podatka (podataka) i dva pokazivača: pokazivača koji pokazuje na levo podstablo i pokazivača koji pokazuje na desno podstablo.

Struktura čvorova binarnog stabla
Slika 14. - Struktura binarnog stabla: svaki čvor ima tačno dva pokazivača - jedan koji pokazuje na levi element (koji u stablima pretrage, po pripisanoj celobrojnoj vrednosti, mora biti manji) i jedan koji pokazuje na desni element (kome je u stablima pretrage pripisana veća celobrojna vrednost). Ukoliko je dati čvor "list" (čvor koji ne pokazuje na druge čvorove), pokazivači će imati vrednost NULL.

Čvorovi stabla ne mogu pokazivati na svoje pretke (ili proizvoljne čvorove iz drugih podstabala), već samo na svoje direktne potomke (čvorove koji su za jedan 'sprat' udaljeniji od korena u odnosu na dati čvor).

Stabla imaju ogromnu primenu u brzinskim pretragama velikih struktura podataka i prevođenju programskih jezika, a ako vas stabla više zanimaju, Visinski balansiranim (AVL) stablima za pretragu i Binarnim stablima za predstavljanje algebarskih izraza, posvetili smo zasebne članke.

Praktičan primer - Implementacija steka u C++ - u

Za kraj, pogledajmo kompletnu implementaciju strukture steka, koja omogućava očitavanje vrednosti čvora, kao i umetanje i uklanjanje čvorova.

Programski jezik koji ćemo koristiti, biće C++ (budući da 'običan C' ne dozvoljava upotrebu klasa).

		
#include<iostream>
#include<stdlib.h>

using namespace std;

struct Cvor
{
	int          Vrednost;
	struct Cvor* Sledeci;  
};

class Stek
{
	public:
		
	struct Cvor* Gornji;
	int Brojac;
	
	Stek()
	{
		Gornji = NULL;
		Brojac = 0;
	}
	
	Stek(int v)
	{
		Brojac = 0;
		Push(v);
	}
	
	void Push(int v)
	{
		// Prvo moramo kreirati novi čvor:
		// (konkretan objekat koji nije samo referenca)

		struct Cvor* Novi;
		Novi = (struct Cvor*) malloc(sizeof(struct Cvor));
		
		// Novom čvoru zadajemo unetu vrednost:

		Novi->Vrednost    = v;
		
		// Novi čvor pokazivaće (u praktičnom smislu) na
		// dosadašnji "gornji element":
		
		Novi->Sledeci = Gornji;
		
		// Pokazivač "Gornji" od sada
		// referencira novi čvor:
		
		Gornji = Novi;
		
		// Ažuriramo brojač čvorova:
		Brojac++;
	}
	
	bool Pop(int v)
	{
		// Ne smemo skidati čvor sa praznog steka!

		if (Gornji == NULL) {
			return false;
		}
		else {
			// Bez pomoćnog čvora, dešava se sledeće:
			// -ako prvo uklonimo gornji čvor, izgubićemo
			// pokazivač na sledeći element ("donji",
			// "pretposlednji" element);
			// -ako prvo premestimo pokazivač "Gornji",
			// sa gornjeg čvora na pretposlednji,
			// izgubićemo pokazivač na gornji čvor -
			// koji je potrebno ukloniti
			// preko komande free
			// Stoga - potrebno je koristiti
			// pomoćni pokazivač
			Cvor C = Gornji;
			Gornji = Gornji->Sledeci;
			free(C);
		}
	}
	
	int CitanjeVrha()
	{
		return Gornji->Vrednost;
	}
};

int main()
{
	struct Stek stek_1(10);
	
	cout << "Broj elemenata: ";
	cout << stek_1.Brojac;
	cout << " Vrh steka: ";
	cout << stek_1.CitanjeVrha() << endl;

	stek_1.Push(12);
		
	cout << "Broj elemenata: ";
	cout << stek_1.Brojac;
	cout << " Vrh steka: ";
	cout << stek_1.CitanjeVrha() << endl;
}
		
	
Slika 15. - Implementacija steka preko klasa, u programskom jeziku C++.

Vidimo da se, 'sve što treba', postiže:

  • prostim dodelama vrednosti pokazivačima
  • dereferenciranjem - upućivanjem pokazivača na drugu vrednost (koja može biti NULL, ili adresa drugog čvora)
  • oslobađanjem memorije pri uklanjanju čvora. *

* U određenim programskim jezicima, nije potrebno "ručno" pozivati funkcije/metode za oslobađanje memorije (rekli bismo da je "najočigledni" takvog pristupa Java). U drugim jezicima, kao što su C i C++, programeri moraju samostalno voditi računa o oslobađanju memorije pri uklanjanju objekata (i naravno, o alokaciji memorije, pri kreiranju objekata).

Takođe, stariji i iskusniji čitaoci mogu primetiti da, ako pažljivije analiziramo prethodni programski kod, lako uviđamo da je za implementaciju steka dovoljan samo slog Cvor (struct Cvor) i da je klasa koju smo koristili (makar u teoriji) 'nepotrebna'.

Međutim - iako je takav pristup zanimljiv sam po sebi (i može biti zanimljiva vežba za studente I ili II godine fakulteta na kojima se izučava programiranje) - u praksi - preglednost koda, ima prioritet u odnosu na "lepe" i "akrobatske" kodove (a programiranje zahteva strateški pristup i vođenje računa o održivosti koda u daljoj eksploataciji).

.... i najprostije rečeno, nećemo stekove i stabla implementirati preko samo jednog pokazivača. :)

Ako vam je potrebna dodatna ideja za vežbu - probajte da implementirate stek u programskom jeziku C (bez klasa).

Autor članka Nikola Vukićević Za web portal www.codeblog.rs
Napomena: Tekstovi, slike, web aplikacije i svi ostali sadržaji na sajtu www.codeblog.rs (osim u slučajevima gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta www.codeblog.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo drugo korišćenje u komercijalne svrhe, bez eksplicitnog pismenog odobrenja autora.
© 2020-2023. Sva prava zadržana.
Facebook LinkedIn Twitter Viber WhatsApp E-mail
početna Početna > Članci > Strukture podataka

Info & povezani članci Info o članku - dugme

Info

trejler_sat Datum objave: 20.03.2020.

trejler_dokument Jezici: C++

trejler_teg_narandzasti Težina: 8/10

Povezani članci

Povezani članci

Svi članci
Dont't think you are .... Know you are!
Filmski citat
codeBlog codeBlog
Sajt posvećen popularizaciji kulture i veštine programiranja.
Napomena: Tekstovi i slike na sajtu www.codeblog.rs (osim u slučajevima, gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta www.codeblog.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo drugo korišćenje u komercijalne svrhe, bez eksplicitnog odobrenja autora.
© 2020-2023. Sva prava zadržana.
Facebook - logo
Instagram - logo
LinkedIn - logo
Twitter - logo
E-mail
Naslovna
   •
Uslovi korišćenja
   •
Obaveštenja
   •
FAQ
   •
Kontakt