Abstraktní datové struktury

definice, užití a implementace, zásobník, fronta, prioritní fronta, lineární spojové seznamy

Každá hodnota, všechna data zpracovávaná v PC musí být nějakého typu. Typ je dán užitým programovacím jazykem.

Typ proměnné nám určuje 3 věci:

  1. množinu hodnot, které je možné daným typem vyjádřit
  2. vnitřní reprezentaci v PC - jakou zabírá paměť
  3. přípustné operace, jež lze nad danou hodnotou provést

Definice

Datová struktura definuje konkrétní způsob organizace dat v paměti počítače, tak aby ona data mohla být využita efektivně. Datová struktura umožňuje spravovat a uchovat množinu dat stejného typu (případně různých typů, ale logicky souvisejících).

Užití a vlastnosti

Datové struktura umožňuje data:

  • vkládat
  • vyhledávat
  • aktualizovat
  • mazat

DS bývají většinou založeny na na schopnosti PC ukládat/načítat data kamkoli do paměti, určené pointerem.

Kritériem pro návrh datové struktury je:

  1. rychlost čtení dat
  2. rychlost zápisu (vložení, mazání, aktualizace)
  3. náročnost na paměť
  4. náročnost implementace - komplikovaný algoritmus má větší pravděpodobnost chybovosti

Např. DB spoléhají na binární stromy, dle nichž spravují indexy.

Lineární spojový seznam

  • dynamická datová struktura
  • obsahuje více datových položek (stejného typu)
  • položky jsou navzájem provázány pomocí ukazatelů nebo referencí
  • důležité je, že poslední položka odkazuje "nikam", tím poznáme konec seznamu

Lineární seznamy mohou být jednosměrné nebo obousměrné. V jednosměrném odkazuje položka na následující. V obousměrném odkazuje položka do předchozí i následující.

Lineární seznam může být také kruhový -> poslední prvek listu odkazuje na první prvek.

Fronta a prioritní fronta

  • dynamická datová struktura
  • DS typu FIFO
  • v OS se tento typ DS nazývá PIPE (roura)
  • poslední položka odkazuje nikam (tímto poznáme konec fronty)
  • lze je implementovat pomocí pole, nebo spojového seznamu (linkedList)
  • složitost je O(n)
  • implementace pomocí haldy (prioritní fronta) může dosahovat složitosti O(log n)

Princip fronty

  • zajímají nás jen první a poslední položka fronty
  • INSERT (enqueue) a DELETE (dequeue) (push(), take(), pop(), apod.)
  • zleva "naláduju" frontu -> přidávám prvky/bloky zleva, takže poprvé vložený prvek je zcela vpravo:
  1. mějme čísla 3 5 4 6
  2. push(5); push(3); push(6); push(4)
  3. fronta bude vypadat takto: 4 6 3 5
  4. každý příkaz pro dequeue (take()) - bude bez parametru a metoda odebere zleva poslední prvek (který byl "pušnutý" jako první); v tomto případě 5
  5. fronta bude: 4 6 3

Princip prioritní fronty

  • implementace pomocí binární haldy
  • pracuje s tzv. prioritou
    • push() s danou prioritou
    • take() - odstraní z fronty nejstarší prvek s nejvyšší prioritou
  • prvek se de facto vkládá tak, že se projdou priority stávající a na příslušné místo se umístí námi přidávaný prvek (heapsort)
    • přeruší se link/vazba mezi předchozím a následujícím prvkem a vytvoří se 2 nové vazby na vložený prvek

Zásobník - Stack

  • pro dočasné ukládání dat
  • založen na LIFO (Last is First Out)
  • pro manipulaci se používá tzv. ukazatel zásobníku, který ukazuje na poslední vloženou položku zásobníku (vrchol zásobníku)
  • uživatel smí používat pouze několik málo příkazů: push(), pop()
  • zásobník má dno (počáteční adresa zásobníku)
  • vrchol (nejvyšší zabraná paměťová buňka)

Implementace je možná pomocí pole, nebo linkového seznamu.

Stack je část paměti počítače, jež má pevně danou počáteční adresu, ale proměnlivou strukturu.

  • počáteční velikost stacku je 0
  • pointer velikosti zásobníku ukazuje na počáteční adresu
  • dáme-li push() - tak se přidají data na adresu paměti, na kterou pointer ukazuje, ale adresa pointeru se změní (navýší/zmenší se) o velikost paměti zabranou daty
  • pop() nebo pull() vyjme data z adresy paměti, na kterou ukazuje pointer, adresa pointeru se změní o velikost paměti, kterou data zabírala

PŘÍKLAD

Počáteční adresa zásobníku je pevně stanovená, např. na 1000 a expandujeme směrem dolů. Měníme-li velikost zásobníku, tak nám adresa pointeru (znázorňující aktuální velikost stacku) bude dekrementovat až do 0 (v závislosti na velikosti dat). Tedy, do zásobníku přidám float (32 bitů), adresa pointeru vrcholu zásobníku se změní na 968. Dále přidám data adresa pointeru se dekrementuje na třeba 740. Takto mohu postupovat až do nuly. Budu-li data ze zásobníku brát, tak se adresa pointeru bude inkrementovat zpět k 1000.

  1. Underflow - ukazatel vecholu zásobníku nikdy nesmí být inkrementován nad původní hranici - jinak hrozí podtečení
  2. Overflow - pokud budeme volat naopak stále metodu push() tak nám může dojít k přetečení tím, že adresa pointeru se dekrementuje přes hodnotu 0

Zdroje