logo

TechCodeview

Abstrakte datatyper

I denne artikkelen vil vi lære om ADT, men før vi forstår hva ADT er, la oss vurdere forskjellige innebygde datatyper som er gitt til oss. Datatyper som int, float, double, long osv. anses å være innebygde datatyper og vi kan utføre grunnleggende operasjoner med dem som addisjon, subtraksjon, divisjon, multiplikasjon osv. Nå kan det oppstå en situasjon når vi trenger operasjoner for vår brukerdefinerte datatype som må defineres. Disse operasjonene kan bare defineres når og når vi trenger dem. Så, for å forenkle prosessen med å løse problemer, kan vi lage datastrukturer sammen med deres operasjoner, og slike datastrukturer som ikke er innebygd er kjent som Abstrakt Data Type (ADT).

zip-kommando i linux

Abstrakt datatype (ADT) er en type (eller klasse) for objekter hvis oppførsel er definert av et sett med verdier og et sett med operasjoner. Definisjonen av ADT nevner bare hvilke operasjoner som skal utføres, men ikke hvordan disse operasjonene skal implementeres. Den spesifiserer ikke hvordan data vil bli organisert i minnet og hvilke algoritmer som skal brukes for å implementere operasjonene. Det kalles abstrakt fordi det gir et implementeringsuavhengig syn.

Prosessen med å gi bare det essensielle og skjule detaljene er kjent som abstraksjon.



Brukeren av Så en bruker trenger bare å vite hva en datatype kan gjøre, men ikke hvordan den skal implementeres. Tenk på ADT som en svart boks som skjuler den indre strukturen og designen til datatypen. Nå skal vi definere tre ADT-er, nemlig Liste ADT, Kø ADT.

1. List ADT

java omvendt streng

Vies av listen

  • Dataene er vanligvis lagret i nøkkelsekvens i en liste som har en hodestruktur bestående av telle , pekere og adresse til sammenligningsfunksjonen nødvendig for å sammenligne dataene i listen.
  • Datanoden inneholder pekeren til en datastruktur og en selvrefererende peker som peker til neste node i listen.
  • De List ADT-funksjoner er gitt nedenfor:
  • get() – Returner et element fra listen på en gitt posisjon.
  • insert() – Sett inn et element på en hvilken som helst plassering av listen.
  • remove() – Fjern den første forekomsten av et element fra en ikke-tom liste.
  • removeAt() – Fjern elementet på et spesifisert sted fra en ikke-tom liste.
  • replace() – Erstatt et element i en hvilken som helst posisjon med et annet element.
  • size() – Returner antall elementer i listen.
  • isEmpty() – Returner true hvis listen er tom, ellers returner false.
  • isFull() – Returner true hvis listen er full, ellers returner false.

2. Stable ADT

Utsikt over stabelen

java snu en streng
  • I Stack ADT-implementering i stedet for at data lagres i hver node, lagres pekeren til data.
  • Programmet tildeler minne for data og adresse sendes til stabel ADT.
  • Hovednoden og datanodene er innkapslet i ADT. Ringefunksjonen kan bare se pekeren til stabelen.
  • Stabelhodestrukturen inneholder også en peker til topp og telle av antall oppføringer i stabelen.
  • push() – Sett inn et element i den ene enden av stabelen kalt top.
  • pop() – Fjern og returner elementet øverst i stabelen, hvis det ikke er tomt.
  • peek() – Returner elementet på toppen av stabelen uten å fjerne det, hvis stabelen ikke er tom.
  • size() – Returner antall elementer i stabelen.
  • isEmpty() – Returner true hvis stabelen er tom, ellers returner false.
  • isFull() – Returner true hvis stabelen er full, ellers returner false.

3. Kø ADT

Utsikt over køen

  • Køabstraktdatatypen (ADT) følger den grunnleggende utformingen av stabelabstraktdatatypen.
  • Hver node inneholder en void-peker til data og lenkepeker til neste element i køen. Programmets ansvar er å tildele minne for lagring av data.
  • enqueue() – Sett inn et element på slutten av køen.
  • dequeue() – Fjern og returner det første elementet i køen, hvis køen ikke er tom.
  • peek() – Returner elementet i køen uten å fjerne det, hvis køen ikke er tom.
  • size() – Returner antall elementer i køen.
  • isEmpty() – Returner true hvis køen er tom, ellers returner false.
  • isFull() – Returner true hvis køen er full, ellers returner false.

Funksjoner av ADT:

Abstrakte datatyper (ADT) er en måte å kapsle inn data og operasjoner på disse dataene i en enkelt enhet. Noen av nøkkelfunksjonene til ADT-er inkluderer:

  • Abstraksjon: Brukeren trenger ikke å kjenne til implementeringen av datastrukturen, bare det vesentlige er gitt.
  • Bedre konseptualisering: ADT gir oss en bedre konseptualisering av den virkelige verden.
  • Robust: Programmet er robust og har evnen til å fange opp feil.
  • Innkapsling : ADT-er skjuler de interne detaljene til dataene og gir et offentlig grensesnitt for brukere å samhandle med dataene. Dette muliggjør enklere vedlikehold og modifikasjon av datastrukturen.
  • Dataabstraksjon : ADT-er gir et abstraksjonsnivå fra implementeringsdetaljene til dataene. Brukere trenger bare å vite operasjonene som kan utføres på dataene, ikke hvordan disse operasjonene implementeres.
  • Datastrukturuavhengighet : ADT-er kan implementeres ved hjelp av forskjellige datastrukturer, for eksempel arrays eller koblede lister, uten å påvirke funksjonaliteten til ADT.
  • Skjuler informasjon: ADT-er kan beskytte integriteten til dataene ved kun å tillate tilgang til autoriserte brukere og operasjoner. Dette bidrar til å forhindre feil og misbruk av dataene.
  • Modularitet : ADT-er kan kombineres med andre ADT-er for å danne større, mer komplekse datastrukturer. Dette gir større fleksibilitet og modularitet i programmeringen.

Totalt sett gir ADT et kraftig verktøy for å organisere og manipulere data på en strukturert og effektiv måte.

Abstrakte datatyper (ADT) har flere fordeler og ulemper som bør vurderes når du bestemmer deg for å bruke dem i programvareutvikling. Her er noen av de viktigste fordelene og ulempene ved å bruke ADT:

Fordeler:

  • Innkapsling : ADT-er gir en måte å innkapsle data og operasjoner i en enkelt enhet, noe som gjør det enklere å administrere og endre datastrukturen.
  • Abstraksjon : ADT-er lar brukere jobbe med datastrukturer uten å måtte kjenne til implementeringsdetaljene, noe som kan forenkle programmering og redusere feil.
  • Datastrukturuavhengighet : ADT-er kan implementeres ved hjelp av ulike datastrukturer, noe som kan gjøre det lettere å tilpasse seg endrede behov og krav.
  • Skjuler informasjon : ADT-er kan beskytte integriteten til data ved å kontrollere tilgang og forhindre uautoriserte modifikasjoner.
  • Modularitet : ADT-er kan kombineres med andre ADT-er for å danne mer komplekse datastrukturer, noe som kan øke fleksibiliteten og modulariteten i programmering.

Ulemper:

  • Overhead : Implementering av ADT-er kan legge til overhead når det gjelder minne og prosessering, noe som kan påvirke ytelsen.
  • Kompleksitet : ADT-er kan være komplekse å implementere, spesielt for store og komplekse datastrukturer.
  • Læring Kurve: Å bruke ADT-er krever kunnskap om implementering og bruk, noe som kan ta tid og krefter å lære.
  • Begrenset fleksibilitet: Noen ADT-er kan være begrenset i funksjonalitet eller kanskje ikke være egnet for alle typer datastrukturer.
  • Koste : Implementering av ADT-er kan kreve ekstra ressurser og investeringer, noe som kan øke utviklingskostnadene.

Samlet sett oppveier fordelene med ADT-er ofte ulempene, og de er mye brukt i programvareutvikling for å administrere og manipulere data på en strukturert og effektiv måte. Det er imidlertid viktig å vurdere de spesifikke behovene og kravene til et prosjekt når du bestemmer deg for å bruke ADT.

streng av lengde

Fra disse definisjonene kan vi tydelig se at definisjonene ikke spesifiserer hvordan disse ADTene vil bli representert og hvordan operasjonene skal utføres. Det kan være forskjellige måter å implementere en ADT på, for eksempel kan List ADT implementeres ved hjelp av arrays, eller enkeltlenket liste eller dobbeltlenket liste. På samme måte kan stack ADT og Queue ADT implementeres ved hjelp av arrays eller koblede lister.