Abstract Data Type (ADT)

 

 

Hvad er ADT: En overfladisk/Abstrakt beskrivelse af en komponent/klasse. Fokus er på hvad den gøre og ikke hvordan. Hvis du kender til Interfaces i programmering, så vil en abstrakt data type være et interface. En komponent/klasse som implimenterer dette inderface vil så implimentere de metoder som interfacet beskriver, men interfacet selv indeholder ingen implimentering.

Fiktivt ADT eksempel

ADT BingoCage: Lad os definere en ny ADT som kaldes BingoCage. Den skal opføre sig således. Man kan indsætte alle de kugler med tal man ønsker og så skal man kunne få tilfældige kugler med tal ud.

ADT BingoCage Interface: Her ser du interfacet for BingoCage. Læg mærke til at den har 2 metoder med beskrivende navne og ind og ud variabler. Det er godt at lade interfacet beskrive så meget som muligt.

Læg også mærke til at metoderne i interfacet IKKE beskriver hvordan metoderne skal lave det som vi forventer at de skal. Det er op til implementeringen at bestemme. Dette betyder at samme ADT implementeret i f.eks Java, og i C# helst ikke er implementeret ens, og muligvis opfører de sig også lidt forskelligt, set udefra. Dog bør de opføre sig rimelig ens, det er hele fidusen. Så kan du bruge en ADT i c# så burde du også kunne bruge denne i andre programmeringssprog/udgaver.

    interface BingoCage
    {
        void addKugler(int fra, int til);
        int getKugle();
    }

ADT BingoCage mulig implementering:

Det er vigtigt at forstå et ADT ikke beskriver hvordan man implementerer data typen. Her ser du én mulig implementering og ikke "den rigtige", fordi der findes ingen rigtig. Det eneste rigtige er interfacet.

using System;
using System.Collections.Generic;
namespace AbstrakteDataTyper
{
    class Program
    {
        static void Main(string[] args)
        {
            Bingo bingo = new Bingo();
            bingo.addKugler(3, 6);
            Console.WriteLine(bingo.getKugle());
            Console.WriteLine(bingo.getKugle());
            Console.WriteLine(bingo.getKugle());
            Console.WriteLine(bingo.getKugle());
        }
    }
    class Bingo : BingoCage
    {
        List<int> bingoListe = new List<int>();
        public void addKugler(int fra, int til)
        {
            while (fra <= til)
            {
                bingoListe.Add(fra);
                fra = fra + 1;
            }
        }
        Random rand = new Random();
        public int getKugle()
        {
            int svar = -1;
            int getPos = rand.Next(0, bingoListe.Count);
            svar = bingoListe[getPos];
            bingoListe.RemoveAt(getPos);
            return svar;
        }
    }
    interface BingoCage
    {
        void addKugler(int fra, int til);
        int getKugle();
    }
}

ADT BingoCage mulig implementering udskrift eksempler

Her ser du én udskrift eksempler, når koden kører. Udskriften vil være forskellig for hver gang der udskrives.




Rigtige ADT eksempler
(Wikipedia)

Nogle almindelige ADT'er, der har vist sig nyttigt i en bred vifte af applikationer, er


Hver af disse ADT'er kan defineres på mange måder og varianter, ikke nødvendigvis tilsvarende. For eksempel kan en stak ADT måske eller måske ikke have en tæller operation, der fortæller, hvor mange elementer er blevet skubbet og endnu ikke poppet. Dette valg gør en forskel, ikke kun for sine kunder, men også for implementeringen.






ADT List

ADT List: List er lige som en almindelig indkøbs liste, hvor du kan skrive på den og læse fra den. Du kan skrive og slette hvor du vil.

Add metoden, remove og getEntry er nok de vigtigste metoder for en Liste, de andre er mere for at gøre det nemmer når man arbejder med en liste.

isFull metoden er lidt mærkelig, og C# har ikke sådan en, fordi man kan fylde uendelig meget i en C# liste. Men man kan selv implimenter en List, og det kan være at du syns det giver mening med en isFull.

ADT List Interface: De mest vigtige metoder som en liste bør have er at finde i interfacet her til højre.

 

Læg mærke til at jeg har kaldt interfacet Liste og ikke List, dette skyldes at om du indsætter dette i c# så kører det, men hvis du ændrer Liste til List, får du problemer, fordi der allerede findes sådan en.

    interface Liste<T>
    {
        void Add(T item);
        void Add(int pos, T item);
        void Remove(int fra);
        void Clear();
        void Replace(int pos, T item);
        T getEntry(int pos);
        bool isEmpty();
        bool isFull();
        void display();
    }

Brug af List i C# :

Som du ser her, så har C# indbygget en List som vi kan bruger ved at importere System.Collections.Generic

using System;
using System.Collections.Generic; 
namespace ADT_List
{
    class Program
    {
        static void Main(string[] args)
        {
            List<String> minList = new List<string>();
            minList.Add("Audi");
            minList.Add("Ferrari");
            minList.Add("Ford");
            minList.Add("Mazda");
            minList.Add("Nissan");
            minList.Insert(1, "Honda");
            minList.Remove("Ford");
            minList.RemoveAt(0);
            Console.WriteLine("[Contains BMW: " + minList.Contains("BMW") + "]");
            Console.WriteLine("[Count: " + minList.Count + "]");
            Console.WriteLine("[index of Mazda: " + minList.IndexOf("Mazda") + "]");
            foreach (String bil in minList)
            {
                Console.WriteLine(bil);
            }
            minList.Clear();
            Console.WriteLine("[Count: " + minList.Count + "]");
        }
    }
}

C# List udskrift.

Her ser du udskriften af koden lige ovenover.




ADT Queue

ADT Queue: Denne ADT er ret nem at forstå, og ret praktisk i mange sammenhænge.

Man kan indsætte og tage ud, men nu er der restriktioner på i forhold til List, fordi nu kan man KUN tage ud fra enden og ikke midt i.

 

Vi siger den følger "først ind først ud" princippet

ADT Queue Interface: De mest vigtige metoder som en kø bør have er at finde i interfacet her til højre.

 

Læg mærke til at jeg har kaldt interfacet Queuen og ikke Queue, dette skyldes at vi kan få problemer hvis vi  indsætter dette i c#, fordi den allerede eksisterer.

    interface Queuen<T>
    {
        void Enqueu(T item);       
        T Dequeue();
        bool isEmpty();       
    }

 

Brug af Queue i Brug af Queue i C# :

Som du ser her, så har C# indbygget en Queue (KØ) som vi kan bruge med det samme.

De 2 vigtige metoder Enqueu og Dequeue er implimenteret i denne udgave, men C# har ingen isEmpty, men i stedet for har de en Count, som tilbyder samme funktionalitet.

using System;
using System.Collections.Generic;
namespace ADT_Queue
{
    class Program
    {
        static void Main(string[] args)
        {
            Queue<String> minKø = new Queue<string>();
            minKø.Enqueue("Der");
            minKø.Enqueue("var");
            minKø.Enqueue("engang");
            minKø.Enqueue("en");
            minKø.Enqueue("princesse");
            while (minKø.Count > 0)
            {
                Console.WriteLine(minKø.Dequeue());
            }
        }
    }
} 

C# Queue udskriftor-bidi">C# Queue udskrift.

Her ser du udskriften af koden lige ovenover.

Læg mærke til rækkefølgen, den passer perfekt med den rækkefølge de kommer ind.



ADT Stack

ADT Stack: Denne ADT er ret nem at forstå, og ret praktisk i mange sammenhænge.

Man kan indsætte og tage ud, men nu er der restriktioner på i forhold til List, fordi nu kan man KUN tage ud fra toppen og ikke midt i.

 

Vi siger den følger "Sidst ind først ud" princippet

ADT Stack Interface: De mest vigtige metoder som en kø bør have er at finde i interfacet her til højre.

 

Læg mærke til at jeg har kaldt interfacet Stacken og ikke Stack, dette skyldes at vi kan få problemer hvis vi  indsætter dette i c#, fordi den allerede eksisterer.

    interface Stacken<T>
    {
        void Push(T item);       
        T Pop();
        bool isEmpty();       
    }

 

Brug af Stack i C# :

Som du ser her, så har C# indbygget en Queue (KØ) som vi kan bruge med det samme.Ø) som vi kan bruge med det samme.

De 2 vigtige metoder Enqueu og Dequeue er implimenteret i denne udgave, men C# har ingen isEmpty, men i stedet for har de en Count, som tilbyder samme funktionalitet.

using System;
using System.Collections.Generic;
namespace ADT_Stack
{
    class Program
    {
        static void Main(string[] args)
        {
            Stack<String> minStack = new Stack<string>();
            minStack.Push("Der");
            minStack.Push("var");
            minStack.Push("engang");
            minStack.Push("en");
            minStack.Push("princesse");
            while (minStack.Count > 0)
            {
                Console.WriteLine(minStack.Pop());
            }
        }
    }
}

C# Stack udskrift.strong>C# Queue udskrift.

udskriften af koden lige ovenover.

Læg mærke til rækkefølgen. Nu kommer de i modsat rækkefølge i forhold til hvordan de kommer ind. Den som kom først ind, kommer nu sidst ud. Og det passer perfekt med en stack.