Dinamičke strukture podataka

Dinamičke strukture podataka predstavljaju takve vrste struktura podataka koje mogu da nastaju, mijenjaju kapacitet i nestaju i u toku samog izvršenja programa. Dinamičke strukture podataka su u vrlo širokoj upotrebi u modernom programiranju.

Dinamičke strukture se najčešće koriste u situacijama kada nije unaprijed zadata gornja granica količine potrebnog prostora za skladištenje podataka. Ostvaruju se koristeći alociranje memorije u toku rada programa i pokazivače kao vezivno tkivo između osnovnih jedinica dinamičke strukture. Dinamičke strukture se najčešće realizuju u obliku steka, liste i drveta, ali su često korišćeni i redovi, obični nizovi i grafovi.

Realizacija

Dinamička struktura se realizuje kao konačan skup jedinica dinamičke strukture, koje su najčešće slogovi (u programskom jeziku C struct, u Paskalu record itd.) zbog njihove mogućnosti da sadrže više elemenata različitih tipova, ali se može realizovati i kao obični niz, čija se veličina mijenja u toku rada programa.

Realizacija putem slogova

Slogovi po svojoj prirodi mogu sadržati više elemenata različitih tipova, te se u njih može smjestiti određeni broj pokazivača koji po svojoj deklaraciji mogu pokazivati na slogove istog ili srodnog tipa kao i onaj kojem pripadaju, a preostali elementi da predstavljaju relevantne podatke koje struktura nosi. Na ovaj način, organizuje se određeni skup slogova, svaki od njih posjedujući pokazivače ka drugim slogovima.

Slijedi niz primjera struktura podataka realizovanih putem slogova:

• Stablo se može realizovati kao dinamička struktura čiji svaki slog posjeduje po dva ili više pokazivača (binarno ili višestruko stablo), čiji slogovi sa pokazivačima jednakim nuli predstavljaju listove stabla, a slog na koji nijedan pokazivač iz preostalih slogova ne pokazuje a koji pokazuje na bar jedan slog iz preostalog skupa predstavlja vrh odnosno korijen stabla.
• Lista se može realizovati kao dinamička struktura čiji svaki slog posjeduje po tačno jedan pokazivač koji pokazuje na sljedeći slog, a tačno jedan slog posjeduje pokazivač jednak nuli, što predstavlja kraj liste.
• Stek se realizuje na isti način kao i lista, samo što se upotreba steka razlikuje od upotrebe liste.
• Graf se može realizovati kao dinamička struktura čiji svaki slog posjeduje neodređen broj pokazivača (npr. niz pokazivača) koji pokazuju na druge elemente liste.

Realizacija putem običnog niza

Ako imamo niz n1 dužine N, i želimo da ga proširimo na dužinu N+K, proširivanje se vrši na sljedeći način:

• alociramo novi niz n2 dužine N+K (koristeći dinamičko alociranje)
• prepišemo sav sadržaj niza n1 na početak niza n2
• obrišemo niz n1 (koristeći dinamičko oslobađanje memorije)
• nizu n2 promijenimo ime u n1 (izjednačavajući vrijednost pokazivača n1 sa vrijednošću n2

Dinamička struktura realizovana preko običnog niza se najčešće naziva vektor.

Vidi još

• Struktura podataka
• Stek
• Lista
• Red
• Drvo
• Niz
• Graf (struktura podataka)