Articles

Abstraktní datové struktury

by admin

Abstraktní datové typy

V počítači věda, abstraktní typ dat (ADT) je matematický model pro datové typy, kde typ dat je definován jeho chování (sémantika) z pohledu uživatele údajů, zejména z hlediska možných hodnot, možných operací na data tohoto typu, a chování těchto operací. To kontrastuje s datovými strukturami, které jsou konkrétními reprezentacemi dat a jsou z pohledu implementátora, nikoli uživatele.

formálně může být ADT definována jako „třída objektů, jejichž logické chování je definováno sadou hodnot a sadou operací“; to je analogické algebraické struktuře v matematice. Co se rozumí „chováním“, se liší podle autora, přičemž dva hlavní typy formálních specifikací pro chování jsou axiomatická (algebraická) specifikace a abstraktní model; ty odpovídají axiomatické sémantice a operační sémantice abstraktního stroje. Někteří autoři také zahrnují výpočetní složitost („náklady“), a to jak z hlediska času (pro výpočetní operace), tak prostoru(pro reprezentaci hodnot).

důvod, proč používáme abstraktní struktury, je ten, že efektivně využívají paměť na základě návrhu dat v nich uložených. S velmi velkým množstvím dat nebo velmi často se měnícími daty může struktura dat znamenat obrovský rozdíl v efektivitě (době běhu) vašeho počítačového programu.

V další společnou řeč, abstraktní datová struktura je jen nějaké uspořádání dat, které jsme postavili do řádné uspořádání.

dokonale krásný přehled

Některé typy abstraktní datové struktury

Posoudit IB

  1. statické a dynamické datové struktury
  1. pole
  2. dvou-dimenzionální pole
  3. stack
  4. queue
  5. spojový seznam
  6. strom
  7. binární strom
  8. kolekce
  9. rekurze

nebyly Hodnoceny podle IB, ale měli byste vědět, je

  1. seznamy
  2. slovníky
  3. nastaví
  4. tuple

Základní operace datových struktur

našel jsem tento vynikající snímek od Simona Allardice.

základní operace polí.png

Srovnání různých datových struktur

Datová Struktura Silné stránky Nedostatků
pole Vkládání a mazání prvků, iterace přes kolekci Třídění a vyhledávání, Vkládání a mazání – zvláště pokud jste vkládání a mazání na začátku nebo na konci pole
spojový seznam přímé indexování, Snadné vytvoření a použití přímý přístup, vyhledávání a třídění
stack a fronty určeno pro LIFO / FIFO přímý přístup, vyhledávání a třídění
binární strom rychlost vkládání a mazání, rychlost přístupu, udržování seřazeném pořadí některé režijní

  • Pevná konstrukce jsou rychlejší / menší
  • Když uvažujete, jestli byste měli použít abstraktní datové struktury, byste se měli zeptat sami sebe: to, co drží nejvíce dat a co drží nejčastěji změněná data?

porovnání statických a dynamických datových struktur

toto srovnání je použito v naší učebnici informatiky.

Statické datové struktury Dynamické datové struktury
Neefektivní, protože paměť je alokována, že nemusí být zapotřebí. efektivní, protože množství paměti se mění podle potřeby.
rychlý přístup ke každému prvku dat jako umístění paměti je pevná, když je program zapsán. pomalejší přístup ke každému prvku, protože umístění paměti je přiděleno za běhu.
přidělené paměťové adresy budou přilehlé, takže přístup bude rychlejší. přidělené paměťové adresy mohou být roztříštěné, takže přístup je pomalejší.
struktury mají pevnou velikost, což je činí předvídatelnějšími pro práci. Mohou například obsahovat záhlaví. struktury se liší velikostí, takže musí existovat mechanismus pro poznání velikosti současné struktury.
vztah mezi různými prvky dat se nemění. vztah mezi různými prvky dat se změní při spuštění programu.

Výběru, které datové struktury použití

Tento obrázek je použit s obrovskou vděčností z Dartford Grammar School Computer Science Department.

výběr vývojového diagramu datového typu.png

standardy

  • identifikují situaci, která vyžaduje použití rekurzivního myšlení.
  • Identifikujte rekurzivní myšlení v zadaném řešení problému.
  • trasování rekurzivního algoritmu pro vyjádření řešení problému.
  • popište vlastnosti dvojrozměrného pole.
  • Konstruujte algoritmy pomocí dvourozměrných polí.
  • popište vlastnosti a aplikace zásobníku.
  • Konstruujte algoritmy pomocí přístupových metod zásobníku.
  • popište vlastnosti a aplikace fronty.
  • Konstruujte algoritmy pomocí přístupových metod fronty.
  • vysvětlete použití polí jako statických zásobníků a front.
  • popište vlastnosti a vlastnosti dynamické datové struktury.
  • popište, jak propojené seznamy fungují logicky.
  • skica propojené seznamy (jednoduché, dvojité a kruhové).
  • popište vlastnosti a aplikace kolekce.
  • Konstruujte algoritmy pomocí přístupových metod kolekce.
  • diskutujte o potřebě podprogramů a sbírek v rámci programovaných řešení.
  • Konstruujte algoritmy pomocí předdefinovaných podprogramů, jednorozměrných polí a / nebo kolekcí.
  • popište, jak stromy fungují logicky (binární i nebinární).
  • Definujte termíny: rodič, levé dítě, pravé dítě, podstrom, kořen a list.
  • uveďte výsledek průchodu stromu inorder, postorder a preorder.
  • načrtněte binární stromy.
  • Definujte termín dynamická datová struktura.
  • Porovnejte použití statických a dynamických datových struktur.
  • Navrhněte vhodnou strukturu pro danou situaci.