Föreläsning 2: Abstrakta datatyper
Mål | Läs |
Abstrakta datatyper. Stack Kö Dequeue |
Kapitel 4.1-4.5, 4.10-4.14, 4.19-4.25 i kursboken |
Abstrakta datatyper
- Abstraktion
- Gränssnitt (Interface)
- Abstrakta datatyper
- Stack
- Kö (Queue)
- Deque
Abstraktion
Abstraktion innebär att dölja detaljer. En användare behöver inte känna till detaljer för att kunna utnyttja en datastruktur eller algoritm och en konstruktör behöver inte veta var informationen kommer ifrån eller vad resultaten ska utnyttjas till.
Exempel:
pyspotify Album Links to an external site.
Google Maps API Links to an external site.
Man behöver inte veta exakt hur data lagras för att använda operationerna.
Likadant i Python - vi vet inte hur strängar, listor och uppslagslistor är definierade, ändå kan vi använda dom. Det här är ett exempel på abstraktion. Om implementationen av listans metoder ändras (i en ny Python-version) behöver vi inte bekymra oss, alla våra program som använder listor fungerar ändå. Vi använder listan som en abstrakt datastruktur.
Några fördelar med abstraktion:
- Användaren och konstruktören kommer överens om vad som ska kunna göras och vilka data som ska utnyttjas (d v s ett gränssnitt).
- Sedan kan konstruktören ägna sig åt detta problem och användaren fortsätta som om det var löst (och utnyttja gränssnittet i sin del av programmet).
- Användaren kan inte missbruka detaljinformation (utan måste hålla sig till gränssnittet).
- Konstruktören kan förbättra konstruktionen utan att användarens kod behöver ändras.
Dessutom:
- Det är lättare att överblicka program om delproblem är lösta separat.
- Konstruktören kan anpassa den abstrakta datatypen/algoritmen till olika användare utan att förstöra en bra konstruktion.
Gränssnitt (Interface)
Begreppet gränssnitt används i många sammanhang, men det handlar alltid om någon form av "kontakt" eller "kommunikation". Man talar tex om gränssnittet mellan olja och vatten som skiktat sig i en behållare och om grafiska användargränssnitt som underlättar kommunikationen mellan användare och datorprogram.
Här gäller det gränssnitt inuti program; hur en viss del av koden kommunicerar med resten av programmet.
Abstrakta datatyper
Heltal, flyttal, textsträngar och vektorer är datorns datatyper. Verklighetens datatyper är många fler, till exempel pengar, temperaturer och datum. Det är frestande att låta pengar representeras av heltal, temperaturer av flyttal (grader Celsius) och datum av textsträngar ("2016-08-31"), alltså av konkreta datatyper, men det är inte så bra. Programspråket kanske kan inte lagra hur stora heltal som helst, så när man kommer upp i stora belopp beter sig inte programmet som man tänkt sig. Temperatur anges i Fahrenheit i USA, så där räknar programmet fel. Och misstaget att ha datum som konkret datatyp kostade hundratals miljarder i omprogrammering vid tusenårsskiftet.
En abstrakt datatyp:
- Anger inte lagringssättet
- Specificerar operationer för åtkomst och ändring
Så här skulle exemplen se ut med abstrakta datatyper.
saldo = Kronor() # Ett objekt av den abstrakta datatypen kronor saldo.set(2000) # Sätter nytt värde saldo.plus(1500) # Ändrar värdet print(saldo.get()) # Åtkomst av värdet
T = temperatur() # Ett objekt av den abstrakta datatypen temperatur T.setC(11.5) # Sätter nytt värde i grader Celsius print(T.getF()) # Åtkomst i grader Fahrenheit
d = datum() # Ett objekt av den abstrakta datatypen datum d.set(2016,09,03) # Sätter ett värde if d.helgdag(): # Användbara anrop finns
Specifikationen av vilka anrop som finns kallas datatypens gränssnitt och är det enda användaren behöver känna till. Hur data representeras konkret och hur metoderna implementerats behöver användaren inte veta. Om implementationen ändras påverkar det inte gränssnittet, så ingen användarkod behöver ändras.
Abstrakt kö
En kö fungerar som man förväntar sig, dvs det man stoppar in först är det som tas ut först.
För en abstrakt kö finns följande operationer:
- enqueue(x): Stoppa in x sist i kön.
- x = dequeue(): Plocka ut och returnera det som står först i kön.
- isEmpty(): Undersök om kön är tom.
I labb 2 ska ni använda en kö för att förbereda en kortkonst.
En kö kan också användas för att hantera skrivarköer (se avsnitt 4.14. Simulation: Printing Tasks Links to an external site. Links to an external site.i Miller-Ranum). Den som först begärde utskrift ska också få ut sin utskrift först.
Abstrakt stack
En stack fungerar som en trave tallrikar - det man lägger överst på stacken är det som kommer att tas bort först.
För en abstrakt stack finns följande operationer:
- push(x): Lägg x överst på stacken.
- x = pop(): Plocka ut och returnera det som ligger överst.
- isEmpty(): Undersök om stacken är tom.
Prova följande animation: stack Links to an external site.
Abstrakt deque
Deque (double-ended queue)
För en abstrakt deque finns följande operationer:- addFront(x): Lägg in x först.
- addRear(x): Lägg in x sist.
- x = removeFront(): Plocka ut och returnera det som ligger först.
- x = removeRear(): Plocka ut och returnera det som ligger sist.
- isEmpty(): Undersök om dequen är tom.
Exempel
När vaccinet anländer till vårdcentralen bildas en lång kö utanför av folk som vill bli vaccinerade.
Syster Maud inser att vaccinet inte kommer att räcka till alla och ser att många i början av kön är unga och friska. Hon tror att dom som är i minst behov av vaccination hamnat först (dom sprang snabbast).
Hon vill se till att personer som är 65 eller äldre vaccineras först. Hur ska hon göra?
Skriv programmet MaudVaccinerar.py som läser filen patienter.txt av typen
Usain 29 Annegret 65 Stanislawa 104 Frankie 47 Inge 74
och skriver ut alla under 65 först.
Yngre måste tillfälligt läggas i ett förvaringsutrymme medan filen läses igenom, till exempel i en stack. Man lägger ett objekt på stacken med anropet push(p) och man hämtar ett objekt från stacken med p = pop().
Algoritm
- Skapa en tom stack
- Öppna filen
- För varje patient i filen:
- Om patienten är yngre än 65:
- Pusha hen på stacken
- annars:
- Vaccinera
- Om patienten är yngre än 65:
- Nu är filen genomläst. Så länge stacken inte är tom:
- Poppa ett element ur stacken
- Vaccinera
from stack import Stack class Patient: def __init__(self, namn, ålder): self.namn = namn self.ålder = int(ålder) def __str__(self): return self.namn + " " + str(self.ålder) + " år" def main(): korridor = Stack() with open("patienter.txt", encoding = "utf8") as register: for rad in register: lista = rad.split() namn = lista[0] ålder = lista[1] p = Patient(namn, ålder) if p.ålder < 65: korridor.push(p) else: print("Vaccinerar:", p) |
Här har vi programmerat abstrakt, som om push och pop vore fungerande metoder. Stackimplementationen kommer lite senare!
I vilken ordning kommer personerna ut?
Länkade listor
En länkad lista består av ett antal objekt, noder som är sammanlänkade genom att varje nod refererar till nästa nod. Dessa referenser kallas ofta next-pekare.
Prova först denna animation av Y. Daniel Liang
Noderna som listan består av kan definieras så här:
class Node: def __init__(self, x, next = None): self.data = x # Kan referera till värde av valfri typ self.next = next
När en nod skapas med n = Node(rad) har n.next värdet None, dvs pekar inte på någonting.
Vad innebär följande?
* p.data
* p.next
* p = None
* p = p.next
Vi skapar en Stack-klass. Både Stack-klass och Nod-klass kan ligga i filen stack.py
För en stack behövs bara en referens top till den översta noden, sedan kommer man åt övriga noder genom att följa next-pekarna.
class Stack: def __init__(self): self.top = None def push(self,x): """Lägger x överst på stacken """ ny = Node(x) ny.next = self.top self.top = ny def pop(self): """Plockar ut och returnerar det översta elementet """ x = self.top.data self.top = self.top.next return x def isEmpty(self): """Returnerar True om stacken är tom, False annars""" if self.top == None: return True else: return False class Node: def __init__(self, x, next = None): self.data = x self.next = next
En kö kan implementeras likadant som en stack. Nu vill man ha en pekare i var ände på kön.
Den som hette top i stacken kallar vi first och så har vi last som pekar på sista noden. Där ska nämligen nya noder stoppas in.
class Queue: def __init__(self): self.first = None self.last = None def enqueue(self,x): """Stoppar in x sist i kön """ ny = Node(x) if self.first == None: # Om kön är tom blir det på ett sätt... - - - # ...som du får tänka ut själv. else: # Annars blir det på ett annat sätt.. - - - # ...som du också får lura ut själv. def dequeue(self): """Plockar ut och returnerar det som står först i kön """ - - - def isEmpty(self): """Returnerar True om kön är tom, False annars """ - - -
Bilder från Föreläsningen