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.
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, 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) - što će biti razlog da se u članku detaljno upoznamo i sa pokazivačima u programskom jeziku C (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':
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 čvor ('koreni čvor'), od koga počinju pretrage, obilasci i ostale operacije, koreni čvor pokazuje na svoje direktne potomke, direktni potomci korenog čvora pokazuju na svoje direkne potomke i sl.
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 (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 podataka, 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 podataka, povezanost elemenata ostvaruje se implicitno (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 - 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).
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;
int& r = &a;
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 (promenljivoj na koju 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;
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.
Predavanje argumenata preko pokazivača (referenci)
Prodiskutovaćemo ukratko i o tome kako se funkcije/metode ponašaju u slučaju kada se parametri definišu preko pokazivača/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č/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;
}
.... a 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 (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 iz funkcije promeni, * ali, pošto je vrednost kopirana - prestaje bilo kakva povezanost između lokalne promenljive a iz funkcije main, i parametra a iz funkcije promeni.
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 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 (naravno) mogu sadržati i pokazivače ili reference koji ne pokazuju na srodne čvorove, već 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, sagledaćemo 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 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 (sa više indeksa).
U pitanju je vrlo korisna struktura za smeštaj podataka koja se koristi 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), 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
Rešenje za problem ograničenosti kapaciteta je (kao što verovatno pretpostavljate) - 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 (bez "grananja" i "petlji").
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 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 - 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 (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), i problematici treba pristupiti konstruktivno.
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.
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).
Ulančane liste (kao što smo naveli u prethodnim odeljcima), 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 (gotovo sigurno), najkorisnija jednostavna struktura podataka (mada ne i najzastupljenija; reklo bi se da ta "titula" pripada ulančanim listama).
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 (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.
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, a verovatno najpoznatiji primer upotrebe strukture reda za čekanje je, 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.
Da bismo to ilustrovali, 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 svoje 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 velikih 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 moramo kreirati novi čvor
// (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ćemo i
// 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 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 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).
Ako vam je potrebna dodatna ideja za vežbu - probajte da implementirate stek u programskom jeziku C (bez klasa).