BAZA ZNANJA

Kurs: Strukture podataka i algoritamsko modelovanje

Modul: Tipovi i strukture podataka

Autor:

Naziv jedinice: Složeni tipovi podataka 1

Složeni tipovi

U opštem smislu, tip podatka definiše skup vrednosti i operacije dozvoljene nad tim tipom. Skoro svaki programski jezik eksplicitno sadrži pojam tipa podatka mada, možda koristi drugačiju terminologiju. Takođe, i većina programskih jezika dozvoljava programeru da definiše dodatne tipove, obično kombinujući osnovne tipove kao i ostale složene tipove pod uslovom da kreira i odgovarajuće operacije koje bi se izvodile nad njima. Pod složene tipove možemo svrstati nizove, liste, stek, N-arna i B-stabla.

Nizovi

U programiranju nizovi su strukture podataka koje se sastoje od podataka kojima se pristupa indeksiranjem. U većini programskih jezika članovi niza su istog tipa i smešteni su u memoriju računara, u neprekidnom nizu. Većina programskih jezika sadrži ugrađen nizovni tip. U novijim jezicima nizovi se mogu nazivati vektorima, listama ili tabelama. Takve strukture mogu da olakšaju rešavanje problema u poređenju sa korišćenjem klasičnih nizova.

Pogodnost korišćenja nizova sa unapred određenom dužinom je efikasnost pristupa podacima preko indeksa. Kompaktne su strukture i zahtev za količinom memorije se ne menja u zavisnosti od trenutne količine članova u njemu.

Slika 1. Niz kod kojeg indeksiranje počinje sa 0

Nizovi su posebno korisni zbog njihovih sposobnosti da se koriste za pravljenje drugih struktura podataka kao što su redovi, stekovi, strigovi i slično.

Indeks

Indeks prvog člana niza koji se naziva i početkom niza varira od jezika do jezika. Generalno ih delimo na one koji počinju sa 0, 1 ili n. Na slici 1. je dat primer niza kod kojeg indeksiranje počinje od 0, a na 9. i 10. mestu nema podataka. U jeziku C niz počinje sa 0 i u njemu je niz koji bi počinjao sa n jednostavno niz koji počinje sa 0, ali pomeran za n mesta. Nizovi koji počinju sa 1 imaju izuzetnu primenu u matematičkim izračunavanjima, budući da u realnom svetu počinje da se broji od 1. Nizovi koji počinju sa n su naročito primenljivi u modelovanju problema na koje može da naiđe programer, dozvoljavajući mu da čak postavi i negativne vrednosti i tako omogući efektivno rešenje problema. Zagovornici nizova koji počinju 0 kritikuju ostale nizove kao sporije, mada se to da ispraviti korišćenjem modifikovane logike pretraživanja. U višedimenzionalnim nizovima se to ipak potrvđuje kao tačno, iz razloga računanja odstupanja indeksa po principu mreže u memoriji računara. Prosto rečeno, nizovi koji počinju s nulom su prirodniji, jednostavniji i brži u datim višedimenzionalnim nizovima.

Problem početka niza nije samo otvorena debata u programerskom svetu. Na primer, prizemlje u evropskim liftovima je označeno sa 0, dok je u Americi označeno sa 1.
Indeksiranje se vrši jednostavnim dodeljivanem sledećeg većeg broja sledećem elementu u nizu, bez obzira na njegovu stvarnu vrednost. Takvo linearno indeksiranje nije uvek najbolja ideja. Ovo je zato što bi i brisanje nekog elementa trebalo da je jednostavna operacija. U slučaju niza sa n elemenata potrebno bi bilo doći do poslednjeg elementa u n koraka. Tako da bi u dužim nizovima bilo jednostavnije da se pribegne na primer binarnom stablu ili nekoj drugoj strukturi.

 slika 2. Višedimenzioni niz je niz čiji su članovi nizovi

Liste

Nedostatak nizova je to da se unapred mora znati dužina niza, a to nije baš uvek moguće. Primer toga bi bio kada bismo ušli u restoran i tražili da nam serviraju odmah ono što će da naruči prvi gost koji dođe sutra.

Kod takvih slučajeva gde nam nije unapred poznato koliko članova ćemo morati da smestimo u niz, liste su se pokazale veoma korisne. Svaki  član liste ima dva dela od kojih se sastoji, a to su deo gde sadrži potrebnu informaciju i deo koji pokazuje na sledeći član liste ili pokazivač (pointer). Na taj način je obezbeđeno da bez obzira na to koliko članova nam je potrebno, poslednji član ili rep će pokazivati na član koji se upravo dodaje.

slika 3. L pokazuje na prvi član liste

Možemo se sresti i sa dvostruko povezanim listama, kod kojih svaki član u sebi ima pointer i na sledeći i na prethodni član. Na taj način nam je omogućeno da listu pretražujemo i od početka i od kraja. Na sledećoj slici imamo primer umetanja člana u listu.

slika 4. Umetanje u listu elementa B i izbacivanje elementa C iz liste

Vidimo da je, kod dodavanja, pokazivač koji je pokazivao iz A u C preusmeren tako da pokazuje iz A u B. Kod izbacivanja imamo da se pokazivač preusmerava na sledeći član posle onog kojeg izbacujemo.

Postoje generalno dva načina na koji se brišu podaci iz lista. To su FILO (LIFO) First In Last Out (Last In First Out) i FIFO (LILO) First In First Out (Last In Last Out). Prvi princip je vezan za klasične liste, dok je dvostruko povezanim listama omogućen i drugi princip.

Prvi princip možemo da uporedimo sa ređanjem tanjira na policu. Jednom kada naređamo nekoliko tanjira ne možemo lako da sklonimo prvi koji smo stavili, a da ne podignemo i sve ostale tanjire. A primer za drugi princip bi bio niz ljudi koji čekaju u redu u pošti.