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
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 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
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 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 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)]
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) RETRIVE(p,L)
Implementacija listi
Dostları ilə paylaş: |