Domů » Informatika » Datová struktura

Datová struktura

Datová struktura je konkrétní způsob uložení dat v paměti počítače. Kvůli různým technickým omezením není možné vytvořit jednu univerzální a za všech okolností efektivní datovou strukturu. Proto bylo navrženo mnoho rozličných datových struktur, které jsou používány tam, kde se zdají být nejvhodnější.

Požadavky na datové struktury jsou často protichůdné. Někdy je prioritou rychlost přístupu k datům, jindy je přednější maximální úspora paměti. Volba té či oné datové struktury by měla být vždy učiněna s přihlédnutím k účelu, k němuž má být struktura nejčastěji použita.

Datový typ

Datový typ je soubor syntaktických a sémantických pravidel. Každá skupina spolu souvisejících pravidel specifikuje jednu funkci daného datového typu – pravidla syntaktická určují signaturu funkce, tedy její definiční obor funkce a obor hodnot. Pravidla sémantická tuto funkci dále formálně specifikují.

Zavedením datových typů do programu na sebe programátor klade jistá dobrovolná omezení, která však za cenu nižší flexibility zvýší srozumitelnost programu a sníží riziko lidských chyb – překladač s kontrolou typové bezpečnosti nahlásí místa, kde dochází k nesprávnému zacházení s datovými typy.

Existuje velmi úzká souvislost mezi datovým typem a datovou strukturou. Každá datová struktura má datový typ, ale ne každý datový typ je strukturou. Například číslo v paměti může vykazovat určitou strukturu, ale nemusí. Do důsledků vzato je každá netriviální entita v paměti počítače datovou strukturou, přičemž základním a nedělitelným atomem je jeden bit.

Příklad – syntaktická pravidla pro zásobník

Jednoduchý zásobník obsahuje pět funkcí, jejichž signatura (syntaxe) je popsána následujícími pěti pravidly.

€€ \begin{align} \text{init}: &\rightarrow \text{Stack} \\ \text{push}: N \times \text{Stack} &\rightarrow \text{Stack} \\ \text{top}: \text{Stack} &\rightarrow (N \; \cup \; \text{ERROR}) \\ \text{remove}: \text{Stack} &\rightarrow \text{Stack} \\ \text{isempty}: \text{Stack} &\rightarrow \text{Boolean} \\ \end{align} €€

Příklad – sémantická pravidla pro zásobník

Formální popis jednotlivých funkcí není vždy tak přímočarý a některé složitější funkce vyžadují i několik různých pravidel pro specifikaci všech možných případů. Některé typy formálních popisů se vzdáleně podobají lambda kalkulu.

kód v jazyce (žádný) - Zobrazit

  1. top(init()) = ERROR
  2. top(push(i, stack)) = i
  3. remove(init()) = init()
  4. remove(push(i, stack)) = stack
  5. isempty(init()) = true
  6. isempty(push(i, stack)) = false

Hierarchie

hierarchie uvedených pojmů

Vybrané datové struktury

Reference