DD1320 Tillämpad Datalogi

Föreläsning 2: Abstrakta datatyper

En klass i Python 
class Student:

   def __init__(self, namn, kthid, program):
      self.namn = namn
      self.kthid = kthid
      self.program = program

   def bytProgram(self, nytt):
      self.program = nytt

   def __str__(self):
      strang = self.namn + " " + self.program
      return strang


s = Student("Emma Khama", "i56ef2g", "COPEN")
print s
s.bytProgram("CDATE")
print s
Vi kan lägga in tre objekt i en lista, och skriva ut dom, så här: 
studiegrupp = []
studiegrupp.append(Student("Emma Khama", "i56ef2g", "CDATE"))
studiegrupp.append(Student("Kim Robinson", "i56ag3g", "CMETE"))
studiegrupp.append(Student("Nour Simson", "i56tr3c", "CLGYM"))

for p in studiegrupp:
    print p

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.

Här är en interaktiv listanimation av Y. Daniel Liang.

I Student-klassen ovan kan vi lägga till ett attribut next: 

class Student:

   def __init__(self, namn, kthid, program, next = None):
      self.namn = namn
      self.kthid = kthid
      self.program = program
      self.next = next    # Ska peka på nästa Student
Då kan vi skapa länkade listor av Student-objekt så här: 

studiegrupp = None
studiegrupp = Student("Emma Khama", "i56ef2g", "CDATE", None)
studiegrupp.next = Student("Kim Robinson", "i56ag3g", "CMETE", None)
studiegrupp.next.next = Student("Nour Simson", "i56tr3c", "CLGYM", None)

p = studiegrupp
while p != None:
    print p
    p = p.next

Men enklare vore ju om vi kunde skilja på tankarna om den länkade listan och studentens data. Vi generaliserar och kallar innehållet i noden för data. Här är klassen Node: 

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.

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. Några fördelar med abstraktion:

Dessutom:

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 ("12-08-29"), alltså av konkreta datatyper, men det är inte så bra. 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(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(2012,10,31)  # 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: put(x)         Stoppa in x sist i kön.
x = get()       Plocka ut och returnera det som står först i kön.
isEmpty()       Undersök om kön är tom.
En kö kan t ex användas för att hantera skrivarköer (se exempel i boken). Den som först begärde utskrift ska också få ut sin utskrift först.

I labb 2 ska ni använda en kö för att förbereda en kortkonst!

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.

Skriv programmet ladiesfirst.py som läser filen person.txt 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. 
from stack import Stack

herrar = Stack()
register = open("person.txt","r")     # Öppnar filen person.txt för läsning

for rad in register:                  # Raderna i filen läses in 
   if rad[9] in "13579":
      herrar.push(rad)                # Män pushas på stacken
   else: 
      print "Kvinna:",rad,            # Kvinnor skrivs ut

while not herrar.isEmpty():           # Så länge stacken inte är tom...
   rad = herrar.pop()                 # ...poppar vi man efter man...
   print "Man:",rad,                  # ...och skriver ut
Här har vi programmerat abstrakt, som om push och pop vore fungerande metoder. Stackimplementationen kommer lite senare!

I vilken ordning kommer männen ut?

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 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:

    def __init__(self): 
       self.first = None
       self.last = None

    def put(self,x):
        """Stoppar in x sist i kön """
        ny = Node(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):
        """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 """
        - - -