Podatkovna struktura

Iz Wikipedije, proste enciklopedije

Podatkòvna struktúra je v računalništvu način shranjevanja podatkov v računalniku, da ga lahko učinkovito uporabimo. Velikokrat bo skrbno izbrana podatkovna struktura omogočila uporabo učinkovitejšega algoritma.

V izdelavi veliko vrst programov bo izbira odgovarjajoče podatkovne strukture osnovni izdelavni premislek, saj so izkušnje pri gradnji velikih sistemov pokazale, da je težavnost izvedbe in kakovost končnega rezultata močno odvisna od izbire najboljše podatkovne strukture. Ko se izberejo podatkovne strukture, postanejo uporabljeni algoritmi sorazmerno očitni. Včasih stvari delujejo v obratni smeri - izberejo podatkovne strukture, ker določene pomembne naloge potrebujejo algoritme, ki najbolje delujejo z določenimi podatkovnimi strukturami, vendar je v obeh primerih izbira primernih podatkovnih struktur odločilna.

Ta vpogled je vodil do veliko določenih izdelavnih postopkov in programskih jezikov v katerih so podatkovne strukture bolj kot algoritmi ključni ureditveni činitelj. Objektno usmerjeni programski jeziki kot sta C++ in Java sta ena skupina jezikov, ki kažeta ta pristop.

Osnovni gradniki večine podatkovnih struktur so polja, zapisi in reference.

[uredi] Nepopolni seznam podatkovnih struktur

linearne podatkovne strukture
- seznam
  - tabela (polje, vektor)
    - bitne slike
      - slike
      - višinske slike (Heightfields)
  - povezani seznam
    - preskakovalni seznam
- razpršena tabela
- sklad (oziroma LIFO zadnji noter, prvi ven)
- vrsta (oziroma FIFO prvi noter, prvi ven)
  - prednostna vrsta
- dvojna vrsta (Deque)
- izravnalna vrzel
grafovske podatkovne strukture
- seznam sosednosti
- prizorski graf
- drevesne podatkovne strukture
  - B-drevo
  - dvojiško iskalno drevo
    - samoutežno dvojiško iskalno drevo
      - AVL drevo
      - rdečečrno drevo
      - plosko drevo (Splay tree)
  - kopica
  - drevo izpeljav
  - priponsko drevo
  - (trie)
    - (Patricia trie)
odmišljene podatkovne strukture
- združevalno polje
druge podatkovne strukture
- etiketirana unija (Tagged union)