Nada

Grudat 2004-11-01

Föreläsning 2: Abstrakta datatyper: stack och kö.

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. Ett heltal i datorn kan inte vara större än cirka två miljarder, så när man kommer upp i stora belopp ballar programmet ur. 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 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 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()
Hämta det som ligger överst på stacken.
isempty()
Undersök om stacken är tom.
Skriv programmet ladiesfirst.py som läser filen person.reg av typen 
420119-0818 Henrik
410423-1206 Gerd
971229-6772 Elon
och först skriver alla kvinnor och sedan alla män i filen. 
dator>python ladiesfirst.py 
Kvinna: 410423-1206 Gerd
Man: 971229-6772 Elon
Man: 420119-0818 Henrik


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 = open("person.reg")       
for rad in register:                # Varje rad slutar med "\n"
  if rad[9] in "13579": 
    push(rad)                       # Män pushas på stacken
  else: 
    print "Kvinna:",rad.strip()     # Kvinnor skrivs ut
while not isempty():                # Så länge stacken inte är tom...
   rad=pop()                        # ...poppar vi man efter man...
   print "Man:",rad.strip()         # ...och skriver ut
Här har vi programmerat abstrakt, som om push och pop vore fungerande metoder. Stackimplementationen kommer lite senare!
Exempel: HP-räknare

Denna klassiska räknedosa har ingen =tangent och inga parenteser. Beräkningen 2*(3+4) knappas in som 2 3 4 + *. Tydligen behövs en stack att lagra talen i och när en operationsknapp trycks poppar den de båda översta talen på stacken, räknar och pushar tillbaka resultatet på stacken. Programmet blir så här. 

"Emulerar en HP-räknare"

    - - -                      #def av push och pop
while True:
    rad=raw_input("in:")
    if rad=="": break
    tkn=rad[0]
    if tkn=="+":
        x = pop()+pop()
    elif tkn=="-":   
        x = -pop()+pop()
    elif tkn=="*":   
        x = pop()*pop()
    else:      
        x = int(rad)
    push(x)
    print "---->",x
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. Annat namn: enqueue(x).
x=get()
Hämta det som står först i kön. Annat namn: x=dequeue().
isempty()
Undersök om kön är tom.
En kö kan t ex användas för att hantera skrivarköer. 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!

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 node som skulle kunna användas för att skapa en länkad lista. 

class Node:
    value=None          # Refererar till värde av valfri typ
    next=None           # Pekar på nästa nod
Nä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ästa
Hä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==None
Om 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 = None
Det 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):
        - - -
Vetenskapliga teorier

Universitetskanslern Sigbrit Franke skrev i DN att teknologer sysslar med fakta medan lärarhögskolans studenter håller på med teorier. Kristdemokratledaren Alf Svensson föreslog nyligen att bibelns skapelseberättelse borde ges samma status i skolorna som den vetenskapliga beskrivningen av utvecklingen, eftersom det bara rör sej om två olika teorier. Det här visar två missuppfattningar av vad en vetenskaplig teori är för något.

Vetenskapen vill beskriva verkligheten och grunden för all vetenskap är data från observationer och experiment. 

 ______________  Observationer ______       __________       _______
| Verkligheten |----->--------| Data |-->--|Systematik|-->--|Modell|
|______________| Experiment   |______|     |Databas   |     |Teori |
       ^                                   |__________|     |______|
       |                                                        |
        ------------------------------------------------<-------
                            Förutsägelser som kan testas
En modell är ett matematiskt samband som gäller för observationerna. En teori är vetenskapens slutprodukt, en allmängiltig modell. Kännetecknet på en bra vetenskaplig teori är den gör förutsägelser som kan testas i verkligheten. Linjär algebra är en matematisk teori, differentialkalkyl en annan. Vardagsbetydelsen av teori som något obevisat och tvivelaktigt är alltså helt motsatt den vetenskapliga betydelsen.
Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 10 november 2009
Tekniskt stöd: <webmaster@nada.kth.se>