Föreläsning 2: Abstrakta datatyper
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. Det finns flera fördelar med abstraktion:
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 (belopp i ören), temperaturer av flyttal (grader Celsius) och datum av textsträngar ("03-11-04"), alltså av konkreta datatyper, men det är inte så bra. En datorn 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
Så här skulle exemplen se ut med abstrakta datatyper. saldo=kronor() # Ett objekt av den abstrakta datatypen kronor saldo.set(1999) # 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(27.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(2003,11,4) # Sätter ett värde if d.helgdag(): # Användbara anrop finnsSpecifikationen 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 stack
En stack fungerar som en trave tallrikar - det man lägger överst på stacken
är det som kommer att tas bort först.
Skriv programmet ladiesfirst.py som läser filen person.reg av typen 120203-1114 Albus Dumbledore 330401-6402 Minerva McGonagall 920731-3131 Harry Potter - - - - - - - - -och först skriver alla kvinnor och sedan alla män i filen. dator>python ladiesfirst.py Kvinna: Minerva McGonagall Man: Harry Potter Man: Albus Dumbledore Männen måste tillfälligt läggas i ett förvaringsutrymme medan filen läses igenom, till exempel en abstrakt stack. Man lägger en textrad på stacken med anropet push("En textrad") och man hämtar en textrad från
stacken med rad=pop() . Så här blir huvudprogrammet.
- - - register = file("person.reg") for rad in register.readlines(): # Raderna läses in i en vektor if rad[9] in "13579": push(rad) # Män pushas på stacken else: print "Kvinna:",rad, # Kvinnor skrivs ut while not isempty(): # Så länge stacken inte är tom... rad=pop() # ...poppar vi man efter man... print "Man:",rad, # ...och skriver utHär har vi programmerat abstrakt, som om push och pop vore fungerande metoder. Stackimplementationen kommer lite senare! 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.
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. Nedan följer klassen class Node: value=None # Refererar till värde av valfri typ next=None # Pekar på nästa nodNär en nod skapas med n = Node() har både n.value
och n.next värdet None , dvs pekar inte på någonting, men
satsen n.value=17 lägger in ett värde. 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.Man kan mödosamt skapa en stack av orden EN SJYST STACK på följande sätt. class Node: # Nodklassen definieras value = None next = None top = None # Stacken är tom från början n = Node() # En ny nod skapas... n.value = "STACK" # ...får ett värde... top = n # ...och läggs i stacken n = Node() # En ny nod skapas... n.value = "SJYST" # ...får ett värde... n.next = top # ...pekar på tidigare nod... top = n # ...och blir ny toppnod n = Node() n.value = "EN" n.next = top top = n p = top # Hjälppekaren p sätts överst i stacken while p: # Så länge den pekar på något... print p.value # ...skrivs dess värde ut... p = p.next # ...och pekaren flyttas till nästaHär har stacken hanterats konkret, men om vi programmerar push, pop och isempty kan den behandlas abstrakt. push("STACK") push("SJYST") push("EN") while not isempty(): print pop() För att detta ska fungera och för att ladiesfirst.py ska
fungera måste vi definiera push och pop, dvs implementera den
abstrakta stacken. Så här kan det se ut.
class Node: value = None next = None top=None def push(x): global top # Annars får push inte ändra globala top ny = Node() ny.value = x ny.next = top top = ny def pop(): global top # Annars får pop inte ändra globala top x = top.value top = top.next return x def isempty(): return top==NoneOm den här koden ligger före huvudprogrammet i ladiesfirst.py kommer det att fungera. Men två brister finns med det användningssättet. Vi vill lägga stackdefinitionerna i en egen fil som vi kan importera i många program. Och vi vill kunna ha flera stackar i samma program. Varje stack måste ha sin egen top -pekare, så det är
bäst att göra en stackklass. Både stackklass och nodklass kan
ligga i filen stack.py
"En abstrakt stack" class Stack: top = None def push(self,x): # Förklaring till self ges efteråt ny = Node() ny.value = x ny.next = self.top self.top = ny def pop(self): x = self.top.value self.top = self.top.next return x def isempty(self): return self.top==None class Node: value = None next = NoneDet nya som händer är att man inte längre kan skriva top ,
man måste ange vilken top man menar, nämligen self.top .
Första parametern i en objektmetod ska alltid vara self .
När den anropas med s.push(17) översätts nämligen anropet till
push(s,17) och alla blir glada.
Huvudprogrammet behöver bara importera stack-klassen, inte nod-klassen. "Ett huvudprogram som använder stack-klassen" from stack import Stack herrar = Stack() register = file("person.reg") for rad in register.readlines(): if rad[9] in "13579": herrar.push(rad) else: print rad, while not herrar.isempty(): print herrar.pop(), En kö kan implementeras likadant som länkad lista, 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 first = None last = None def put(self,x): ny=Node() ny.value=x if self.first is 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 get(self): - - - def isempty(self): - - - |