Strukture podataka I algoritmi Prvo predavanje gradivni elementi strukture podataka liste

Strukture podataka i algoritmi

• Prvo predavanje gradivni elementi strukture podataka LISTE

Tekstualni editor

Heksa-decimalni editor

Strukture podataka i algoritmi

• Strukture podataka:

• “statički aspekt programa”

• Algoritmi:

• “dinamički aspekt programa”

Rješavanje problema metodom postepenog profinjavanja

Definicije pojmova (podaci)

• Tip podataka:

• skup vrijednosti koje neki podatak može poprimiti (integer, real)

• Apstraktni tip podataka

• zadan jedan ili više tipova podataka, te jedna ili više operacija (procedura; funkcija) primjer kompleksni brojevi

• Struktura podataka

• Skupina varijabli u nekom programu i veza među tim varijablama

Algoritam

• Konkretna realizacija apstraktnog tipa podataka u nekom programu.

• Konačni niz instrukcija od kojih svaka ima jasno značenje i može biti izvršena u konačnom vremenu

• Iste instrukcije mogu se izvršiti više puta pod pretpostavkom da same instrukcije ukazuju na ponavljanje

Elementi od kojih se grade strukture podataka

• Klijetka (engl. cell)

• Polje

• Zapis

• Pokazivač (engl. pointer)

• Kursor

Klijetka (engl. cell)

• Varijabla koju promatramo kao zasebnu cjelinu

• Relativan pojam jer možemo analizirati i njenu unutarnju građu u određenim okolnostima

• Svaka klijetka ima tip i adresa

• Sadržaj klijetke odgovarajućeg tipa

• Gradivni element polja

Polje

• Mehanizam udruživanja manjih dijelova strukture u veće

• Više klijetki istog tipa pohranjeni na uzastopnim adresama

• Broj klijetki je unaprijed zadan i nepromjenljiv

• Indeksi cjelobrojne konstante

Zapis

• Još jedan način udruživanja manjih cjelina u veće strukture

• Zapis čini više klijetki koje ne moraju biti istog tipa ali su pohranjene na uzastopnim adresama

• Pojedina klijetka zove se komponenta zapisa

• Zapise možemo kombinirati u polja

Pokazivač ( engl. Pointer)

• Klijetka koja pokazuje na neku drugu klijetku

• Služi za uspostavljanje veze između dijelova strukture

• Sadržaj pokazivača je adresa klijetke koju treba pokazati

Kursor

• Također povezuje dijelove strukture

• Klijetka tipa integer koja pokazuje na element u polju

• Sadržaj kursora je indeks tog elementa polja

Primjer strukture podataka

Lista (općenito)

• Lista je konačan niz ( od nule ili više podataka istog tipa. Podaci koji čine listu nazivaju se elementima liste

• [a1,a2,a3,…an ]

• n - duljina liste

• Ako je n=0 prazna lista

• Definiran prethodnik i sljedbenik

• Broj elemenata nije fiksan

• Identitet elementa liste određen njegovim pozicijom

Primjer liste

• Polinom

• P(x)=anxen+ anxen+… anxen

• Gdje je 0

• Zapravo se radi o listi

• [(a1 ,e1),(a2 ,e2), … ,(an ,en)]

Operacije nad listama

• END(L) – funkcija koja vraća poziciju na kraj liste

• MAKE_NULL(L) – pretvara listu u praznu listu i vraća poziciju END(L)

• INSERT(x,p,L) – ubacuje podatak x na poziciju p u listi L

• DELETE(p,L) – izbacuje element p iz liste L

• FIRST(L) – funkcija vraća prvu poziciju u listi, za praznu listi vraća END(L)

• NEXT(p,L), PREVIOUS(p,L) vraća poziciju ispred odnosno iza u listi

• RETRIVE(p,L)

Implementacija listi

• Pomoću polja