logo

TechCodeview

Abstraktné dátové typy

V tomto článku sa dozvieme o ADT, ale predtým, ako pochopíme, čo je ADT, zvážme rôzne vstavané typy údajov, ktoré sú nám poskytované. Dátové typy ako int, float, double, long atď. sa považujú za vstavané dátové typy a môžeme s nimi vykonávať základné operácie ako sčítanie, odčítanie, delenie, násobenie atď. Teraz môže nastať situácia, keď potrebujeme operácie pre náš užívateľsky definovaný dátový typ, ktorý je potrebné definovať. Tieto operácie je možné definovať len vtedy a vtedy, keď ich požadujeme. Takže, aby sme zjednodušili proces riešenia problémov, môžeme vytvárať dátové štruktúry spolu s ich operáciami a také dátové štruktúry, ktoré nie sú zabudované, sú známe ako abstraktný dátový typ (ADT).

koľko miest v Spojených štátoch amerických

Abstraktný dátový typ (ADT) je typ (alebo trieda) pre objekty, ktorých správanie je definované množinou hodnôt a množinou operácií. Definícia ADT uvádza iba to, aké operácie sa majú vykonať, ale nie to, ako sa tieto operácie budú vykonávať. Nešpecifikuje, ako budú dáta usporiadané v pamäti a aké algoritmy budú použité na implementáciu operácií. Nazýva sa abstraktné, pretože poskytuje pohľad nezávislý od implementácie.

Proces poskytovania len toho najnutnejšieho a skrývania detailov je známy ako abstrakcia.



Používateľ Používateľ teda potrebuje vedieť len to, čo môže dátový typ robiť, ale nie ako bude implementovaný. Predstavte si ADT ako čiernu skrinku, ktorá skrýva vnútornú štruktúru a dizajn dátového typu. Teraz definujeme konkrétne tri ADT Zoznam ADT, Fronta ADT.

1. Uveďte zoznam ADT

ako previesť znak na reťazec

Súboje zo zoznamu

  • Údaje sú vo všeobecnosti uložené v poradí kľúčov v zozname, ktorý má štruktúru hlavy pozostávajúcu z počítať , ukazovatele a adresa porovnávacej funkcie potrebné na porovnanie údajov v zozname.
  • Dátový uzol obsahuje ukazovateľ na dátovú štruktúru a a sebareferenčný ukazovateľ ktorý ukazuje na nasledujúci uzol v zozname.
  • The Zoznam funkcií ADT je uvedené nižšie:
  • get() – Vráti prvok zo zoznamu na ľubovoľnej danej pozícii.
  • insert() – Vloží prvok na ľubovoľnú pozíciu v zozname.
  • remove() – odstráni prvý výskyt akéhokoľvek prvku z neprázdneho zoznamu.
  • removeAt() – Odstráňte prvok na určenom mieste z neprázdneho zoznamu.
  • nahradiť() – Nahradenie prvku na ľubovoľnej pozícii iným prvkom.
  • size() – Vráti počet prvkov v zozname.
  • isEmpty() – Vráti hodnotu true, ak je zoznam prázdny, inak vráti hodnotu false.
  • isFull() – Vráti hodnotu true, ak je zoznam plný, inak vráti hodnotu false.

2. Stack ADT

Pohľad na stoh

java triedenie zoznamu
  • V implementácii Stack ADT namiesto uloženia údajov v každom uzle sa ukladá ukazovateľ na údaje.
  • Program prideľuje pamäť pre údajov a adresu sa odovzdá do zásobníka ADT.
  • Hlavný uzol a dátové uzly sú zapuzdrené v ADT. Volajúca funkcia vidí iba ukazovateľ na zásobník.
  • Štruktúra hlavy zásobníka obsahuje aj ukazovateľ na top a počítať počtu záznamov aktuálne v zásobníku.
  • push() – Vložte prvok na jeden koniec zásobníka s názvom top.
  • pop() – Odstráňte a vráťte prvok v hornej časti zásobníka, ak nie je prázdny.
  • peek() – Vráťte prvok v hornej časti zásobníka bez jeho odstránenia, ak zásobník nie je prázdny.
  • size() – Vráti počet prvkov v zásobníku.
  • isEmpty() – Vráti hodnotu true, ak je zásobník prázdny, inak vráti hodnotu false.
  • isFull() – Vráti hodnotu true, ak je zásobník plný, inak vráti hodnotu false.

3. Front ADT

Pohľad na front

  • Typ abstraktných údajov vo fronte (ADT) sleduje základný návrh abstraktného typu údajov zásobníka.
  • Každý uzol obsahuje prázdny ukazovateľ na údajov a ukazovateľ odkazu na ďalší prvok v poradí. Zodpovednosťou programu je prideliť pamäť na ukladanie údajov.
  • enqueue() – Vložte prvok na koniec frontu.
  • dequeue() – Odstráňte a vráťte prvý prvok frontu, ak front nie je prázdny.
  • peek() – Vráti prvok frontu bez jeho odstránenia, ak front nie je prázdny.
  • size() – Vráti počet prvkov vo fronte.
  • isEmpty() – Vráti hodnotu true, ak je front prázdny, inak vráti hodnotu false.
  • isFull() – Vráti hodnotu true, ak je front plný, inak vráti hodnotu false.

Vlastnosti ADT:

Abstraktné dátové typy (ADT) predstavujú spôsob zapuzdrenia údajov a operácií s týmito údajmi do jednej jednotky. Niektoré z kľúčových funkcií ADT zahŕňajú:

  • Abstrakcia: Užívateľ nemusí poznať implementáciu dátovej štruktúry, poskytuje len to najnutnejšie.
  • Lepšia koncepcia: ADT nám poskytuje lepšiu konceptualizáciu skutočného sveta.
  • Robustný: Program je robustný a má schopnosť zachytiť chyby.
  • Zapuzdrenie : ADT skrývajú interné podrobnosti údajov a poskytujú používateľom verejné rozhranie na interakciu s údajmi. To umožňuje jednoduchšiu údržbu a úpravu dátovej štruktúry.
  • Abstrakcia údajov : ADT poskytujú úroveň abstrakcie od podrobností implementácie údajov. Používatelia potrebujú poznať iba operácie, ktoré možno vykonať s údajmi, nie to, ako sú tieto operácie implementované.
  • Nezávislosť štruktúry údajov : ADT môžu byť implementované pomocou rôznych dátových štruktúr, ako sú polia alebo prepojené zoznamy, bez ovplyvnenia funkčnosti ADT.
  • Skrytie informácií: ADT môžu chrániť integritu údajov tým, že povolia prístup iba oprávneným používateľom a operáciám. To pomáha predchádzať chybám a zneužitiu údajov.
  • Modularita : ADT je ​​možné kombinovať s inými ADT na vytvorenie väčších a komplexnejších dátových štruktúr. To umožňuje väčšiu flexibilitu a modularitu v programovaní.

Celkovo ADT poskytujú výkonný nástroj na organizáciu a manipuláciu s údajmi štruktúrovaným a efektívnym spôsobom.

Abstraktné dátové typy (ADT) majú niekoľko výhod a nevýhod, ktoré je potrebné zvážiť pri rozhodovaní o ich použití pri vývoji softvéru. Tu sú niektoré z hlavných výhod a nevýhod používania ADT:

Výhody:

  • Zapuzdrenie : ADT poskytujú spôsob na zapuzdrenie údajov a operácií do jednej jednotky, čo uľahčuje správu a úpravu štruktúry údajov.
  • Abstrakcia : ADT umožňujú používateľom pracovať s dátovými štruktúrami bez toho, aby museli poznať detaily implementácie, čo môže zjednodušiť programovanie a znížiť chyby.
  • Nezávislosť štruktúry údajov : ADT môžu byť implementované pomocou rôznych dátových štruktúr, čo môže uľahčiť prispôsobenie sa meniacim sa potrebám a požiadavkám.
  • Skrytie informácií : ADT môžu chrániť integritu údajov riadením prístupu a zabránením neoprávneným úpravám.
  • Modularita : ADT je ​​možné kombinovať s inými ADT na vytvorenie zložitejších dátových štruktúr, čo môže zvýšiť flexibilitu a modularitu v programovaní.

Nevýhody:

  • Nad hlavou : Implementácia ADT môže zvýšiť réžiu z hľadiska pamäte a spracovania, čo môže ovplyvniť výkon.
  • Zložitosť : Implementácia ADT môže byť zložitá, najmä pre veľké a zložité dátové štruktúry.
  • Učenie Krivka: Používanie ADT si vyžaduje znalosť ich implementácie a používania, čo si môže vyžadovať čas a námahu na učenie.
  • Obmedzená flexibilita: Niektoré ADT môžu byť obmedzené vo svojej funkčnosti alebo nemusia byť vhodné pre všetky typy dátových štruktúr.
  • náklady : Implementácia ADT môže vyžadovať dodatočné zdroje a investície, čo môže zvýšiť náklady na vývoj.

Celkovo možno povedať, že výhody ADT často prevažujú nad nevýhodami a sú široko používané pri vývoji softvéru na správu a manipuláciu s údajmi štruktúrovaným a efektívnym spôsobom. Pri rozhodovaní o použití ADT je ​​však dôležité zvážiť špecifické potreby a požiadavky projektu.

chrome adresný riadok

Z týchto definícií môžeme jasne vidieť, že definície nešpecifikujú, ako budú tieto ADT reprezentované a ako sa budú vykonávať operácie. Môžu existovať rôzne spôsoby implementácie ADT, napríklad zoznam ADT môže byť implementovaný pomocou polí alebo jednoducho prepojeného zoznamu alebo dvojito prepojeného zoznamu. Podobne je možné implementovať zásobník ADT a frontu ADT pomocou polí alebo prepojených zoznamov.