Datové struktury: Porovnání verzí

(Založena nová stránka: =Datové struktury= Datové struktury jsou programové konstrukce sloužící k efektivní správě dat v počítačovém softwaru. Data jsou v počítači reprezentová…)
 
Řádek 1: Řádek 1:
=Datové struktury=
 
 
Datové struktury jsou programové konstrukce sloužící k efektivní správě dat v počítačovém softwaru. Data jsou v počítači reprezentována různými [[datový typ|datovými typy]]. Ty lze dále skládat do struktur, které umožňují s daty snadněji a rychleji pracovat.
 
Datové struktury jsou programové konstrukce sloužící k efektivní správě dat v počítačovém softwaru. Data jsou v počítači reprezentována různými [[datový typ|datovými typy]]. Ty lze dále skládat do struktur, které umožňují s daty snadněji a rychleji pracovat.
  
Řádek 6: Řádek 5:
 
V dnešní době známe desítky základních i pokročilých datových struktur. Každá je vhodná k plnění jiných funkcí. Existují obecné datové struktury používané v širokém spektru programů, ale i úzce specializované vhodné k použití ve velmi specifických případech. Pro datovou strukturu a její využití je rozhodující především jejich paměťová náročnost a škála základních operací s jejich [[asymptotická složitost|asymptotickou složitostí]].
 
V dnešní době známe desítky základních i pokročilých datových struktur. Každá je vhodná k plnění jiných funkcí. Existují obecné datové struktury používané v širokém spektru programů, ale i úzce specializované vhodné k použití ve velmi specifických případech. Pro datovou strukturu a její využití je rozhodující především jejich paměťová náročnost a škála základních operací s jejich [[asymptotická složitost|asymptotickou složitostí]].
  
===Operace===
+
==Operace==
  
 
Operace jsou úkony, které lze v rámci dané datové struktury nad daty provádět. Většina operací souvisí s efektivním ukládáním, vyhledáváním, řazením, tříděním nebo mazáním dat ve struktuře. Pro každou operaci lze vypočítat [[asymptotická složitost|asymptotickou složitost]] udávající rychlost s kterou se daná operace provede.
 
Operace jsou úkony, které lze v rámci dané datové struktury nad daty provádět. Většina operací souvisí s efektivním ukládáním, vyhledáváním, řazením, tříděním nebo mazáním dat ve struktuře. Pro každou operaci lze vypočítat [[asymptotická složitost|asymptotickou složitost]] udávající rychlost s kterou se daná operace provede.
  
==Základní datové struktury==
+
=Základní datové struktury=
===Pole (Array)===
+
==Pole (Array)==
 
Pole  si můžeme představit jako uspořádanou matici prvků určitého datového typu. Prvky dat jsou  v poli ukládány do paměti v navazujících blocích za sebe a jsou identifikovány pomocí indexu. Pozici prvku v paměti počítače pak lze dopočítat pomocí jednoduché rovnice:  
 
Pole  si můžeme představit jako uspořádanou matici prvků určitého datového typu. Prvky dat jsou  v poli ukládány do paměti v navazujících blocích za sebe a jsou identifikovány pomocí indexu. Pozici prvku v paměti počítače pak lze dopočítat pomocí jednoduché rovnice:  
 
adresa prvku v paměti = adresa počátku pole + index * velikost prvku
 
adresa prvku v paměti = adresa počátku pole + index * velikost prvku
Řádek 20: Řádek 19:
 
*dynamická pole - jsou pole s proměnlivým počtem prvků
 
*dynamická pole - jsou pole s proměnlivým počtem prvků
  
===Fronta (Queue)===
+
==Fronta (Queue)==
 
Jednoduchá datová struktura s proměnným počtem zařazených prvků fungující na principu FIFO (First-In-First-Out). Prvek uložený ve frontě jako první, je jako první na řadě pro výběr.  Fronta aktivně pracuje pouze s prvním a posledním zařazeným prvkem.  K tomuto účelu používá sadu tří základních operací:  *Zařazení prvku (Equeue)
 
Jednoduchá datová struktura s proměnným počtem zařazených prvků fungující na principu FIFO (First-In-First-Out). Prvek uložený ve frontě jako první, je jako první na řadě pro výběr.  Fronta aktivně pracuje pouze s prvním a posledním zařazeným prvkem.  K tomuto účelu používá sadu tří základních operací:  *Zařazení prvku (Equeue)
 
*Vyřazení prvku (Dequeue)
 
*Vyřazení prvku (Dequeue)
Řádek 27: Řádek 26:
 
Speciálním případem front jsou prioritní fronty. V nich jsou prvky řazeny na základě priority. Zařazený prvek s vyšší prioritou předbíhá méně prioritní prvky. Z prioritní fronty je vybírán vždy prvek s nejvyšší prioritou.
 
Speciálním případem front jsou prioritní fronty. V nich jsou prvky řazeny na základě priority. Zařazený prvek s vyšší prioritou předbíhá méně prioritní prvky. Z prioritní fronty je vybírán vždy prvek s nejvyšší prioritou.
  
===Zásobník (Stack)===
+
==Zásobník (Stack)==
 
Jednoduchá datová struktura s proměnným počtem zařazených prvků  fungující na principu LIFO (Last-In-First-Out). Na rozdíl od fronty se ze zásobníku prvky vybírají v opačném pořadí než v jakém byly vloženy. Zásobník tak aktivně pracuje pouze s posledním vloženým prvkem. Díky své rychlosti se zásobníky využívají především pro uchovávání výsledků mezivýpočtů a rekurzivních stavů. Základní sada operací zásobníku obsahuje instrukce:
 
Jednoduchá datová struktura s proměnným počtem zařazených prvků  fungující na principu LIFO (Last-In-First-Out). Na rozdíl od fronty se ze zásobníku prvky vybírají v opačném pořadí než v jakém byly vloženy. Zásobník tak aktivně pracuje pouze s posledním vloženým prvkem. Díky své rychlosti se zásobníky využívají především pro uchovávání výsledků mezivýpočtů a rekurzivních stavů. Základní sada operací zásobníku obsahuje instrukce:
  
Řádek 34: Řádek 33:
 
*Test prázdnoty (Empty)
 
*Test prázdnoty (Empty)
  
===Spojový seznam (Linked list)===
+
==Spojový seznam (Linked list)==
 
Je datová struktura určená k ukládání dat předem neznámé délky. Spojové seznamy jsou tvořeny vzájemně propojenými uzly. Každý uzel obsahuje jeden datový prvek a jeden nebo více ukazatelů na další uzly. Na základě použitých ukazatelů rozlišujeme několik druhů spojových seznamů:
 
Je datová struktura určená k ukládání dat předem neznámé délky. Spojové seznamy jsou tvořeny vzájemně propojenými uzly. Každý uzel obsahuje jeden datový prvek a jeden nebo více ukazatelů na další uzly. Na základě použitých ukazatelů rozlišujeme několik druhů spojových seznamů:
  
====Jednosměrně zřetězený spojový seznam====
+
===Jednosměrně zřetězený spojový seznam===
 
Nejjednodušší varianta spojového seznamu. Jeho prvky obsahují pouze ukazatel na další prvek v seznamu. Jednosměrný spojový seznam lze prohledávat pouze jedním směrem od počátečního prvku struktury dál. Jednosměrné prohledávání je v mnoha případech neefektivní, proto vznikly další varianty spojových seznamů.
 
Nejjednodušší varianta spojového seznamu. Jeho prvky obsahují pouze ukazatel na další prvek v seznamu. Jednosměrný spojový seznam lze prohledávat pouze jedním směrem od počátečního prvku struktury dál. Jednosměrné prohledávání je v mnoha případech neefektivní, proto vznikly další varianty spojových seznamů.
  
====Obousměrně zřetězený spojový seznam====
+
===Obousměrně zřetězený spojový seznam===
 
Uzly obousměrně zřetězeného seznamu obsahují  dva ukazatele na následující a předchozí uzel. Díky zpětnému zřetězení se jde při prohledávání obousměrně zřetězeného seznamu i vracet.
 
Uzly obousměrně zřetězeného seznamu obsahují  dva ukazatele na následující a předchozí uzel. Díky zpětnému zřetězení se jde při prohledávání obousměrně zřetězeného seznamu i vracet.
  
====Kruhový spojový seznam====
+
===Kruhový spojový seznam===
 
Kruhový seznam je speciálním typem seznamu zřetězeným do kruhu.  Poslední uzel seznamu obsahuje místo prázdného odkazu ukazatel na první prvek listu. Kruhový seznam lze vytvořit v obou variantách zřetězení. Obousměrné zřetězení umožňuje tento typ spojového seznamu procházet libovolně v obou směrech od počátku i od konce.
 
Kruhový seznam je speciálním typem seznamu zřetězeným do kruhu.  Poslední uzel seznamu obsahuje místo prázdného odkazu ukazatel na první prvek listu. Kruhový seznam lze vytvořit v obou variantách zřetězení. Obousměrné zřetězení umožňuje tento typ spojového seznamu procházet libovolně v obou směrech od počátku i od konce.
  
==Pokročilé datové struktury==
+
=Pokročilé datové struktury=
 
Mezi pokročilé datové struktury řadíme především stromy, hashe a nejrůznější grafové struktury. Konstrukčně složitější datové struktury mají význam především při efektivním třídění a vyhledávání dat.
 
Mezi pokročilé datové struktury řadíme především stromy, hashe a nejrůznější grafové struktury. Konstrukčně složitější datové struktury mají význam především při efektivním třídění a vyhledávání dat.
  
===Stromové struktury (Tree)===
+
==Stromové struktury (Tree)==
  
 
Slouží k uchovávání hierarchicky uspořádaných dat jako jsou abecední seznamy, organizační struktury, nebo hierarchie souborů. Ve stromových strukturách jsou data řazeny od tzv. kořene (root) pomocí větvení až k nejnižším prvkům struktury – listům (leaf). Stromy jsou efektivní především při prohledávání setříděných dat s logaritmickou složitostí.  
 
Slouží k uchovávání hierarchicky uspořádaných dat jako jsou abecední seznamy, organizační struktury, nebo hierarchie souborů. Ve stromových strukturách jsou data řazeny od tzv. kořene (root) pomocí větvení až k nejnižším prvkům struktury – listům (leaf). Stromy jsou efektivní především při prohledávání setříděných dat s logaritmickou složitostí.  
Řádek 55: Řádek 54:
 
Z hlediska implementace existuje mnoho různých stromových struktur. Mezi nejznámější patří binární stromy, R-stromy, nebo AVL stromy. Vlastnostmi stromů se podrobně zabývá [[teorie grafů]].
 
Z hlediska implementace existuje mnoho různých stromových struktur. Mezi nejznámější patří binární stromy, R-stromy, nebo AVL stromy. Vlastnostmi stromů se podrobně zabývá [[teorie grafů]].
  
===Grafy (Graph)===
+
==Grafy (Graph)==
  
 
Grafy jsou datové struktury složené z uzlů (nodes) a hran (edges) a jejich vzájemných incidencí. Uzly grafu uchovávají data. Hrany jsou spojnice uzlů označující vazby, nebo vztahy mezi nimi. Z hlediska vnitřní struktury rozlišujeme dva základní typy grafů:
 
Grafy jsou datové struktury složené z uzlů (nodes) a hran (edges) a jejich vzájemných incidencí. Uzly grafu uchovávají data. Hrany jsou spojnice uzlů označující vazby, nebo vztahy mezi nimi. Z hlediska vnitřní struktury rozlišujeme dva základní typy grafů:
Řádek 64: Řádek 63:
 
Problematikou grafů se v počítačové vědě podrobně zabývá teorie grafů.
 
Problematikou grafů se v počítačové vědě podrobně zabývá teorie grafů.
  
===Hashe (Hash)===
+
==Hashe (Hash)==
 
Hash je struktura používaná k sestavování asociativních polí, které za pomoci klíče (key) a správné hashovací funkce (hash function) umožňují indexování. Indexování je hojně používáno například v [[databáze|databázích]], kde urychluje vyhledávání.
 
Hash je struktura používaná k sestavování asociativních polí, které za pomoci klíče (key) a správné hashovací funkce (hash function) umožňují indexování. Indexování je hojně používáno například v [[databáze|databázích]], kde urychluje vyhledávání.

Verze z 7. 6. 2014, 22:06

Datové struktury jsou programové konstrukce sloužící k efektivní správě dat v počítačovém softwaru. Data jsou v počítači reprezentována různými datovými typy. Ty lze dále skládat do struktur, které umožňují s daty snadněji a rychleji pracovat.

Datové struktury patří mezi abstraktní datové typy (ADT). Jde o programové abstrakce nezávislé na konkrétním způsobu implementace, programovacím jazyku, nebo typu ukládaných dat. Jednotlivé datové struktury definují jak svou vnitřní strukturu, tak i operace, které je možné nad daty provádět.

V dnešní době známe desítky základních i pokročilých datových struktur. Každá je vhodná k plnění jiných funkcí. Existují obecné datové struktury používané v širokém spektru programů, ale i úzce specializované vhodné k použití ve velmi specifických případech. Pro datovou strukturu a její využití je rozhodující především jejich paměťová náročnost a škála základních operací s jejich asymptotickou složitostí.

Operace

Operace jsou úkony, které lze v rámci dané datové struktury nad daty provádět. Většina operací souvisí s efektivním ukládáním, vyhledáváním, řazením, tříděním nebo mazáním dat ve struktuře. Pro každou operaci lze vypočítat asymptotickou složitost udávající rychlost s kterou se daná operace provede.

Základní datové struktury

Pole (Array)

Pole si můžeme představit jako uspořádanou matici prvků určitého datového typu. Prvky dat jsou v poli ukládány do paměti v navazujících blocích za sebe a jsou identifikovány pomocí indexu. Pozici prvku v paměti počítače pak lze dopočítat pomocí jednoduché rovnice: adresa prvku v paměti = adresa počátku pole + index * velikost prvku

Pole mohou mít libovolný počet rozměrů. Nejjednodušším typem jsou jednorozměrná neboli lineární pole. Dvourozměrná pole někdy nazýváme tabulka. Přístup k prvkům vícerozměrného pole se řeší použitím více indexů podobně jako při práci s maticemi.

  • statická pole - jsou pole s pevně daným počtem prvků
  • dynamická pole - jsou pole s proměnlivým počtem prvků

Fronta (Queue)

Jednoduchá datová struktura s proměnným počtem zařazených prvků fungující na principu FIFO (First-In-First-Out). Prvek uložený ve frontě jako první, je jako první na řadě pro výběr. Fronta aktivně pracuje pouze s prvním a posledním zařazeným prvkem. K tomuto účelu používá sadu tří základních operací: *Zařazení prvku (Equeue)

  • Vyřazení prvku (Dequeue)
  • Test prázdnoty (Empty)

Speciálním případem front jsou prioritní fronty. V nich jsou prvky řazeny na základě priority. Zařazený prvek s vyšší prioritou předbíhá méně prioritní prvky. Z prioritní fronty je vybírán vždy prvek s nejvyšší prioritou.

Zásobník (Stack)

Jednoduchá datová struktura s proměnným počtem zařazených prvků fungující na principu LIFO (Last-In-First-Out). Na rozdíl od fronty se ze zásobníku prvky vybírají v opačném pořadí než v jakém byly vloženy. Zásobník tak aktivně pracuje pouze s posledním vloženým prvkem. Díky své rychlosti se zásobníky využívají především pro uchovávání výsledků mezivýpočtů a rekurzivních stavů. Základní sada operací zásobníku obsahuje instrukce:

  • Vložit (Push)
  • Vybrat (Pop)
  • Test prázdnoty (Empty)

Spojový seznam (Linked list)

Je datová struktura určená k ukládání dat předem neznámé délky. Spojové seznamy jsou tvořeny vzájemně propojenými uzly. Každý uzel obsahuje jeden datový prvek a jeden nebo více ukazatelů na další uzly. Na základě použitých ukazatelů rozlišujeme několik druhů spojových seznamů:

Jednosměrně zřetězený spojový seznam

Nejjednodušší varianta spojového seznamu. Jeho prvky obsahují pouze ukazatel na další prvek v seznamu. Jednosměrný spojový seznam lze prohledávat pouze jedním směrem od počátečního prvku struktury dál. Jednosměrné prohledávání je v mnoha případech neefektivní, proto vznikly další varianty spojových seznamů.

Obousměrně zřetězený spojový seznam

Uzly obousměrně zřetězeného seznamu obsahují dva ukazatele na následující a předchozí uzel. Díky zpětnému zřetězení se jde při prohledávání obousměrně zřetězeného seznamu i vracet.

Kruhový spojový seznam

Kruhový seznam je speciálním typem seznamu zřetězeným do kruhu. Poslední uzel seznamu obsahuje místo prázdného odkazu ukazatel na první prvek listu. Kruhový seznam lze vytvořit v obou variantách zřetězení. Obousměrné zřetězení umožňuje tento typ spojového seznamu procházet libovolně v obou směrech od počátku i od konce.

Pokročilé datové struktury

Mezi pokročilé datové struktury řadíme především stromy, hashe a nejrůznější grafové struktury. Konstrukčně složitější datové struktury mají význam především při efektivním třídění a vyhledávání dat.

Stromové struktury (Tree)

Slouží k uchovávání hierarchicky uspořádaných dat jako jsou abecední seznamy, organizační struktury, nebo hierarchie souborů. Ve stromových strukturách jsou data řazeny od tzv. kořene (root) pomocí větvení až k nejnižším prvkům struktury – listům (leaf). Stromy jsou efektivní především při prohledávání setříděných dat s logaritmickou složitostí.

Z hlediska implementace existuje mnoho různých stromových struktur. Mezi nejznámější patří binární stromy, R-stromy, nebo AVL stromy. Vlastnostmi stromů se podrobně zabývá teorie grafů.

Grafy (Graph)

Grafy jsou datové struktury složené z uzlů (nodes) a hran (edges) a jejich vzájemných incidencí. Uzly grafu uchovávají data. Hrany jsou spojnice uzlů označující vazby, nebo vztahy mezi nimi. Z hlediska vnitřní struktury rozlišujeme dva základní typy grafů:

  • Neorientovaný graf - hrany nerozlišují směr
  • Orientovaný graf - hrany mají určen směr od počátečního do koncového uzlu

Problematikou grafů se v počítačové vědě podrobně zabývá teorie grafů.

Hashe (Hash)

Hash je struktura používaná k sestavování asociativních polí, které za pomoci klíče (key) a správné hashovací funkce (hash function) umožňují indexování. Indexování je hojně používáno například v databázích, kde urychluje vyhledávání.