Kategorija:Podatkovna struktura

Iz MaFiRaWiki

(Preusmerjeno iz Podatkovna struktura)
Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Podatkovna struktura je način organizacije podatkov ali kakih drugih entitet. V vsakdanjem življenju srečamo podatkovne strukture kot so seznam, sklad, vrsta, imenik ali slovar, razpredelnica ipd. V računalništvu poznamo še mnoge druge podatkovne strukture, kot so drevesa, grafi, množice, multimnožice ipd.

Vsaka podatkovna struktura ima dva vidika, matematičnega in računalniškega. Ko gledamo na podatkovno strukture iz matematičnega vidika, nas zanimajo predvsem njene matematične lastnosti. V računalništvu pa se ukvarjamo z vprašanjem, kako podatkovno strukturo predstavimo v računalniku in kako učinkovito opravljamo osnovne operacije na podatkovni strukturi.

V nadaljevanju se posvetimo računalniškim vidikom podatkovnih struktur. V grobem ločimo dve vrsti podatkovnih struktur, konkretne in abstraktne

Konkretna podatkovna struktura

Konkretna podatkovna struktura sestoji iz podatkovnega tipa in osnovnih operacij na njem. Na primer, seznam je konkretna podatkovna struktura, ki jo poznamo v večini programskih jezikov. Osnovne operacije na seznamu so:

  • prazen seznam
  • glava seznama
  • rep seznama
  • dodajanje elementa na začetek seznama

Abstraktna podatkovna struktura

Pri abstraktni podatkovni strukturi ločimo med njeno specifikacijo in implementacijo.

Specifikacija nam pove, kakšne lastnosti ima abstraktna podatkovna struktura, ne pa tudi, kako jo dejansko predstavimo v računalniku. Običajno je specifikacija podana s signaturo, ki je seznam osnovnih tipov in operacij na podatkovni strukturi, skupaj z njihovimi tipi, ter z aksiomi, ki povedo, kakšne lastnosti naj bi imele osnovne operacije.

Implementacija abstraktne podatkovne strukture je konkretna podatkovna struktura, ki zadošča specifikaciji. V implementaciji so osnovni tipi in operacije predstavljene s podatkovnimi tipi in algoritmi, ki ustrezajo aksiomom. Dani specifikaciji lahko ustreza vec različnih implementacij.

Osebna orodja