logo

TechCodeview

Abstraktní datové typy

V tomto článku se dozvíme o ADT, ale než pochopíme, co je ADT, zvažme různé vestavěné datové typy, které jsou nám poskytovány. Datové typy jako int, float, double, long atd. jsou považovány za vestavěné datové typy a můžeme s nimi provádět základní operace jako sčítání, odčítání, dělení, násobení atd. Nyní může nastat situace, kdy potřebujeme operace pro náš uživatelsky definovaný datový typ, který je třeba definovat. Tyto operace lze definovat pouze tehdy, když je požadujeme. Abychom zjednodušili proces řešení problémů, můžeme vytvářet datové struktury spolu s jejich operacemi a takové datové struktury, které nejsou vestavěné, jsou známé jako abstraktní datový typ (ADT).

seznam.seřadit java

Abstraktní datový typ (ADT) je typ (nebo třída) pro objekty, jejichž chování je definováno sadou hodnot a sadou operací. Definice ADT pouze zmiňuje, jaké operace se mají provádět, ale ne, jak budou tyto operace implementovány. Nespecifikuje, jak budou data organizována v paměti a jaké algoritmy budou použity pro provádění operací. Nazývá se abstraktní, protože poskytuje pohled nezávislý na implementaci.

Proces poskytování pouze toho nejnutnějšího a skrývání detailů je známý jako abstrakce.



Uživatel Uživatel tedy potřebuje pouze vědět, co datový typ umí, ale ne, jak bude implementován. Představte si ADT jako černou skříňku, která skrývá vnitřní strukturu a design datového typu. Nyní definujeme konkrétně tři ADT Seznam ADT, Fronta ADT.

1. Seznam ADT

Souboje seznamu

pythonská n-tice seřazena
  • Data jsou obecně uložena v posloupnosti klíčů v seznamu, který má strukturu hlavy sestávající z počet , ukazatele a adresa funkce porovnání potřebné k porovnání údajů v seznamu.
  • Datový uzel obsahuje ukazatel do datové struktury a sebereferenční ukazatel který ukazuje na další uzel v seznamu.
  • The Seznam funkcí ADT je uveden níže:
  • get() – Vrátí prvek ze seznamu na libovolné dané pozici.
  • insert() – Vloží prvek na libovolné místo v seznamu.
  • remove() – Odebere první výskyt jakéhokoli prvku z neprázdného seznamu.
  • removeAt() – Odebere prvek na určeném místě z neprázdného seznamu.
  • nahradit() – Nahradí prvek na libovolné pozici jiným prvkem.
  • size() – Vrátí počet prvků v seznamu.
  • isEmpty() – Vrátí hodnotu true, pokud je seznam prázdný, v opačném případě vrátí hodnotu false.
  • isFull() – Vrátí hodnotu true, pokud je seznam plný, jinak vrátí hodnotu false.

2. Stack ADT

Pohled na zásobník

  • V implementaci Stack ADT se místo ukládání dat v každém uzlu ukládá ukazatel na data.
  • Program přiděluje paměť pro data a adresa je předán do zásobníku ADT.
  • Hlavní uzel a datové uzly jsou zapouzdřeny v ADT. Volající funkce vidí pouze ukazatel na zásobník.
  • Struktura hlavy zásobníku také obsahuje ukazatel na horní a počet počtu záznamů aktuálně v zásobníku.
  • push() – Vloží prvek na jeden konec zásobníku s názvem top.
  • pop() – Odstraňte a vraťte prvek v horní části zásobníku, pokud není prázdný.
  • peek() – Vraťte prvek v horní části zásobníku bez jeho odstranění, pokud není zásobník prázdný.
  • size() – Vrátí počet prvků v zásobníku.
  • isEmpty() – Vrátí hodnotu true, pokud je zásobník prázdný, v opačném případě vrátí hodnotu false.
  • isFull() – Vrátí hodnotu true, pokud je zásobník plný, jinak vrátí hodnotu false.

3. Fronta ADT

vkládací python

Pohled na frontu

  • Abstraktní datový typ fronty (ADT) se řídí základním návrhem abstraktního datového typu zásobníku.
  • Každý uzel obsahuje prázdný ukazatel na data a ukazatel odkazu na další prvek ve frontě. Zodpovědností programu je přidělit paměť pro ukládání dat.
  • enqueue() – Vloží prvek na konec fronty.
  • dequeue() – Odstraňte a vraťte první prvek fronty, pokud fronta není prázdná.
  • peek() – Vrátí prvek fronty bez jeho odstranění, pokud fronta není prázdná.
  • size() – Vrátí počet prvků ve frontě.
  • isEmpty() – vrátí hodnotu true, pokud je fronta prázdná, jinak vrátí hodnotu false.
  • isFull() – Vrátí hodnotu true, pokud je fronta plná, jinak vrátí hodnotu false.

Vlastnosti ADT:

Abstraktní datové typy (ADT) představují způsob, jak zapouzdřit data a operace s těmito daty do jediné jednotky. Některé z klíčových funkcí ADT zahrnují:

  • Abstrakce: Uživatel nemusí znát implementaci datové struktury, poskytuje pouze to nejnutnější.
  • Lepší konceptualizace: ADT nám poskytuje lepší konceptualizaci skutečného světa.
  • Robustní: Program je robustní a má schopnost zachytit chyby.
  • Zapouzdření : ADT skrývají interní podrobnosti dat a poskytují uživatelům veřejné rozhraní pro interakci s daty. To umožňuje snadnější údržbu a úpravu datové struktury.
  • Abstrakce dat : ADT poskytují úroveň abstrakce od podrobností implementace dat. Uživatelé potřebují znát pouze operace, které lze s daty provádět, nikoli to, jak jsou tyto operace implementovány.
  • Nezávislost datové struktury : ADT lze implementovat pomocí různých datových struktur, jako jsou pole nebo propojené seznamy, aniž by to ovlivnilo funkčnost ADT.
  • Skrytí informací: ADT mohou chránit integritu dat tím, že umožňují přístup pouze oprávněným uživatelům a operacím. To pomáhá předcházet chybám a zneužití dat.
  • Modularita : ADT lze kombinovat s jinými ADT za účelem vytvoření větších a složitějších datových struktur. To umožňuje větší flexibilitu a modularitu v programování.

Celkově ADT poskytují výkonný nástroj pro organizaci a manipulaci s daty strukturovaným a efektivním způsobem.

Abstraktní datové typy (ADT) mají několik výhod a nevýhod, které je třeba vzít v úvahu při rozhodování o jejich použití při vývoji softwaru. Zde jsou některé z hlavních výhod a nevýhod používání ADT:

výhody:

  • Zapouzdření : ADT poskytují způsob, jak zapouzdřit data a operace do jediné jednotky, což usnadňuje správu a úpravu datové struktury.
  • Abstrakce : ADT umožňují uživatelům pracovat s datovými strukturami, aniž by museli znát detaily implementace, což může zjednodušit programování a snížit chyby.
  • Nezávislost datové struktury : ADT lze implementovat pomocí různých datových struktur, což může usnadnit přizpůsobení měnícím se potřebám a požadavkům.
  • Skrytí informací : ADT mohou chránit integritu dat řízením přístupu a zabráněním neoprávněným úpravám.
  • Modularita : ADT lze kombinovat s jinými ADT za účelem vytvoření složitějších datových struktur, což může zvýšit flexibilitu a modularitu v programování.

Nevýhody:

  • Nad hlavou : Implementace ADT může zvýšit režii z hlediska paměti a zpracování, což může ovlivnit výkon.
  • Složitost : Implementace ADT může být složitá, zejména pro velké a složité datové struktury.
  • Učení se Křivka: Používání ADT vyžaduje znalost jejich implementace a použití, což může vyžadovat čas a úsilí, než se naučit.
  • Omezená flexibilita: Některé ADT mohou mít omezenou funkčnost nebo nemusí být vhodné pro všechny typy datových struktur.
  • Náklady : Implementace ADT může vyžadovat dodatečné zdroje a investice, což může zvýšit náklady na vývoj.

Celkově lze říci, že výhody ADT často převažují nad nevýhodami a jsou široce používány při vývoji softwaru pro strukturovanou a efektivní správu dat a manipulaci s nimi. Při rozhodování o použití ADT je ​​však důležité vzít v úvahu specifické potřeby a požadavky projektu.

chromový adresní řádek

Z těchto definic jasně vidíme, že definice nespecifikují, jak budou tyto ADT reprezentovány a jak budou operace prováděny. Mohou existovat různé způsoby, jak implementovat ADT, například seznam ADT lze implementovat pomocí polí nebo jednoduše propojeného seznamu nebo dvojitě propojeného seznamu. Podobně lze zásobník ADT a frontu ADT implementovat pomocí polí nebo propojených seznamů.