Strukture podataka

Uvod

Za postizanje optimalnih rezultata u programiranju, nije dovoljno samo da iza algoritama stoje optimalne 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 postavljeni 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.

Određene 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, i stoga je na početku ozbiljnijeg bavljenja programiranjem potrebno prvo se upoznati upravo sa navedenim strukturama. **

U dizajnu struktura podataka, važnu ulogu igraju pokazivači (promenljive koje omogućavaju međusobno povezivanje podataka), i stoga je takođe neophodno da se u članku detaljno upoznamo i sa pokazivačima u programskom jeziku C (s tim da vredi napomenuti da je implementacija 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, odnosno, prema tipu veza između podataka, strukture podataka mogu biti:

• linearne
• razgranate
• umrežene

Linearne strukture podataka

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

Primeri linearnih struktura podataka su: niz, lista, stek, red za čekanje.

Razgranate strukture podataka

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

Bilo koji čvor (osim "korenog" čvora, koji se nalazi na vrhu hijerarhije i od koga počinju pretrage, obilasci i sl), povezan je sa:

• tačno jednim čvorom sa prethodnog nivoa hijerarhije (čvor "predak")
• proizvoljnim brojem čvorova sa sledećeg nivoa hijerarhije (čvorovi "potomci"/"deca")

U stablu obavezno postoje i čvorovi koji nemaju potomke (izraz za takav čvor je "list") * i, takođe, nijedan čvor iz stabla ne sme pokazivati na čvorove iz susednih "podstabala" * (što je već implicirano kada je navedeno da bilo koji čvor može imati najviše jednog pretka). **

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).

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 (npr. statički nizovi), dok su dinamičke strukture, one koje dozvoljavaju dodavanje i uklanjanje elemenata (npr. lista, stek, red, stablo, graf i mnoge druge).

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

Kod statičkih struktura podataka, povezanost elemenata ostvaruje se implicitno (tj. posredno), time što susedni elementi zauzimaju susedne lokacije u memoriji, dok se kod dinamičkih struktura podataka, 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 (tj. jedan objekat), pa samo još ostaje pitanje: kako omogućiti objektima da 'vide' jedni druge?

Kao što verovatno pretpostavljate (s obzirom na naslov odeljka), rešenje je - 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).

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

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

		
int* p = &a; // pokazivač p
int& r = &a; // referenca r
		
	

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 - adresa se dobija preko operatora adresiranja: &.

Kada je potrebno zadati vrednost promenljivoj na koju pokazuje pokazivač ili referenca, važe sledeća pravila: uz promenljivu koja predstavlja pokazivač, koristi se operator *, dok se uz reference ne navodi dodatni operator.

Na primer:

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

*p = 12;
r  = 12

// Praktično: kao da smo naveli a = 12;
		
	

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

Predavanje argumenata preko pokazivača ili referenci

Prodiskutovaćemo ukratko i o tome kako se ponašaju funkcije (tj. metode), u slučaju kada se parametri definišu preko pokazivača ili referenci, a kako u slučaju kada se parametri definišu kao podaci koji pripadaju nekom od osnovnih tipova (int, float char i sl).

Ukoliko se pri definisanju parametara funkcije ne koriste pokazivači (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<iostream>

using namespace std;

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

int main()
{
	int a = 5;
	promeni(a);
	cout << a;
}
		
	

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

Ukoliko je (za razliku od prethodnog primera), parametar definisan kao pokazivač (ili referenca), 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;
}
		
	

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

Da rezimiramo pravila ....

Ako se pri definisanju (radne) funkcije, kao parametar navede promenljiva koja pripada nekom od osnovnih tipova podataka, * pri pozivu funkcije (u primeru: promeni(a);), dešava se sledeće: vrednost promenljive iz pozivajuće funkcije (u gornjem primeru, vrednost promenljive a iz funkcije main), kopira se i dodeljuje lokalnoj promenljivoj (parametar a iz funkcije promeni), ** ali - pošto je vrednost kopirana - prestaje bilo kakva povezanost između parametra, tj. lokalne promenljive iz radne funkcije, i promenljive iz pozivajuće funkcije.

Nasuprot prethodnom slučaju, ako se pri definisanju funkcije, kao parametar navede pokazivač ili referenca (u primerima koje smo prikazali: int* a i int& a), pri pozivu funkcije, ovoga puta se predaje adresa promenljive iz pozivajuće funkcije, što znači da parametar radne funkcije (lokalna promenljiva), "pokazuje" na promenljivu iz pozivajuće funkcije, ili (malo drugačije), parametar radne funkcije povezuje se sa promenljivom iz pozivajuće funkcije (parametri int* a i int& a iz funkcija promeni_pok i promeni_ref, povezuju se sa promenljivom a iz funkcije main).

Ili, još jednostavnije: u najpraktičnijem smislu, radna funkcija direktno operiše nad promenljivom iz pozivajuće funkcije.

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

Čvor (node)

Čvor je kolekcija podataka 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.

Čvorovi se tipično implementiraju: ili preko slogova (struct), ili kao objekti klasa, a bitno je navesti i to da čvorovi mogu (naravno) sadržati i pokazivače ili reference koji ne pokazuju na srodne čvorove, već pokazuju na druge podatke (bilo kog tipa).

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;                 
};
		
	

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 je moguće kreirati liste proizvoljne dužine.

Č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 sledeće strukture podataka:

• ulančana lista (linked list)
• magacin, odnosno stek (stack)
• red za čekanje (queue)

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

U ovom tekstu, na konkretne odlike navedenih struktura osvrnućemo se okvirno, a zarad starijih/iskusnijih čitalaca * koje tematika struktura podataka zanima u većoj meri, spremili smo i zasebne, detaljne članke o većini struktura o kojima u članku pišemo (linkovi u nastavku).

Kao svojevrstan uvod u glavnu temu članka, napravićemo 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

Statički niz je najprostija struktura podataka koju smo do sada često koristili, i do sada smo takvu strukturu jednostavno zvali - "niz".

Struktura statičkog niza je implementirana 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 (ali, sa više indeksa).

U pitanju je vrlo korisna struktura za smeštaj podataka (koja ima primenu u mnogim programima), pri čemu implementacija očigledno nije izvedena preko povezanih čvorova.

Osnovna prednost statičkih nizova u odnosu na liste (sa kojima ćemo se upoznati u narednom odeljku), tiče se vremena pristupa određenom elementu ("bilo kom elementu") - pri čemu 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, praktično je ograničen na oko 500 hiljada *
• veličina niza se ne može menjati naknadno

Rešenje za problem ograničenosti kapaciteta, je (kao što verovatno pretpostavljate) - kreiranje i upotreba ulančanih lista.

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

Svaki čvor pokazuje na jedan čvor (odnosno, na "sledeći" čvor), pri čemu je dozvoljeno proizvoljno (tj. "dinamičko"), dodavanje, umetanje i uklanjanje čvorova * (ali, kao što smo već naglasili, nije dozvoljeno kreirati zatvorene 'petlje' u strukturi liste, niti hijerarhijske strukture koje su svojstvene stablima). **

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

Naravno, kreiranje velikih lista - osim upotrebne vrednosti - ima i "cenu".

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

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

Pored svega navedenog, u obzir treba uzeti i nezanemarljivo dodatno memorijsko zauzeće koje povlači upotreba pokazivača.

Međutim, 'nije sve tako crno' (ni iz daleka), to jest, problematici treba pristupiti na konstruktivan način.

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

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

Svakako bi bilo lepo da se "nekako" može kreirati struktura 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čni naziv za implementaciju osnovnog dinamičkog niza, čiji je princip funkcionisanja opisan u prethodnom odeljku (a opštu šemu možemo videti na donjoj slici).

Postoji još jedna lepa osobina dinamičkih nizova (na koju smo se osvrnuli samo okvirno): * 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).

Kao što smo naveli u prethodnim odeljcima, ulančane liste mogu se proširivati, dodavanjem čvorova na kraj, kao i proizvoljnim umetanjem elemenata na "međupozicijama" (a moguće je naravno i uklanjati elemente).

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 struktura podataka kod koje su pokazivači iskorišćeni tako da se može pristupati samo poslednjem ubačenom elementu, i u pitanju je (gotovo sigurno), najkorisnija linearna struktura podataka (mada ne i najzastupljenija; reklo bi se da ta "titula" pripada ulančanim listama).

Da dodatno "potcrtamo poentu": za razliku od ulančanih lista, kod kojih je moguće pristupiti proizvoljnom elementu, na steku 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".

Stekovi se koriste u algoritmima za prevođenje programskih jezika, * za praćenje pozicije u rekurzivnim pozivima, kao i u brojnim drugim okolnostima.

Jednostavnu implementaciju steka za celobrojne vrednosti ** možete videti u poslednjem odeljku ovog članka.

Redovi za čekanje (Queue)

Red za čekanje je struktura podataka kod koje su pokazivači iskorišćeni tako da se može pristupati samo prvom ubačenom elementu, i (baš kao i stek), red predstavlja linearnu strukturu podataka od velike važnosti (koja se u programiranju koristi veoma često).

Da pojasnimo dodatno: za razliku od steka, u redovima za čekanje je moguće pristupiti samo prvom ubačenom elementu (zarad očitavanja vrednosti čvora ili zarad uklanjanja čvora), a dodavanje elemenata se obavlja na suprotnom kraju - preko zasebnog pokazivača.

Princip uklanjanja elementa iz reda za čekanje, poznat je pod skraćenicom FIFO ("First In - First Out").

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

Redovi za čekanje (kao i stekovi), takođe se koriste u brojnim algoritmima, pri čemu ćemo pomenuti verovatno najpoznatiji primer upotrebe strukture reda za čekanje - algoritam BFS (u kome se red koristi 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 ....

Jednostavnije rečeno (kao što smo već pokazali na početku): stabla su strukture podataka koje odlikuje hijerarhijski raspored elemenata.

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

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

Stabla imaju primenu u brzinskim pretragama različitih struktura podataka i prevođenju programskih jezika, a ako vas stabla zanimaju u većoj meri, 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 jednostavnu (ali, prilično kompletnu), implementaciju strukture steka, koja omogućava očitavanje vrednosti čvora, kao i umetanje i uklanjanje čvorova.

		
#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 je potrebno kreirati novi čvor
		// (tj. potrebno je kreirati konkretan objekat
		// 'koji nije samo referenca'):

		struct Cvor* Novi;
		Novi = (struct Cvor*) malloc(sizeof(struct Cvor));
		
		// Novom čvoru zadaje se uneta 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;
		
		// Na kraju, ažurira se i
		// brojač čvorova:
		Brojac++;
	}
	
	bool Pop(int v)
	{
		// Ne smemo pokušavati da skinemo
		// čvor sa praznog steka!
		if (Gornji == NULL) {
			return false;
		}
		else {
			// Bez pomoćnog čvora, dešava se sledeće:
			// -ako se prvo ukloni gornji čvor, izgubićemo
			// pokazivač na sledeći element ("donji",
			// "pretposlednji" element);
			// -ako se prvo premesti pokazivač "Gornji",
			// sa gornjeg čvora na pretposlednji,
			// izgubićemo pokazivač na gornji čvor -
			// koji je potrebno ukloniti preko
			// komande free (i stoga je jasno da je
			// pomoćni pokazivač - i te kako potreban).
			Cvor C = Gornji;
			Gornji = Gornji->Sledeci;
			free(C);
		}

		return true;
	}
	
	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;
}
		
	

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. *

Takođe, stariji i iskusniji čitaoci mogu primetiti i sledeće: ako se pažljivije analizira prethodni programski kod, može delovati da je za implementaciju steka dovoljan samo slog Cvor (struct Cvor), odnosno, može delovati da se sve može izvesti bez upotrebe klase?!

Međutim - iako je navedeni 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 i poštovanje opštih principa, 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).

Ako vam je potrebna dodatna ideja za vežbu - probajte da implementirate stek u programskom jeziku C (bez klasa, ali, uz uvažavanje opštih principa koje smo izneli u prethodnih nekoliko pasusa).