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.
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':
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).
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, 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).
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.
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 (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;
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)
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).
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;
}
.... 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;
}
.... 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.
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).
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 možemo 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:
- 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).
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.
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. ***
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).
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".
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.
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.
Č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;
}
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).