Till KTH:s startsida Till KTH:s startsida

Laboration 2

Laboration 2 - Kortkonst

Mål: läsa Pythons dokumentation, använda moduler, implementera en datatyp, hantera länkade listor.

"Trollkarlen tar ut de tretton spaderna ur leken, håller dem som en
kortlek med baksidan upp och lägger ut dem på följande sätt: Översta
kortet stoppas underst, nästa kort läggs ut med framsidan upp, nästa
kort stoppas underst, nästa kort läggs ut osv.  Till publikens
häpnad kommer korten upp i ordning ess, tvåa, trea...

Utförande: Man ordnar i hemlighet korten enligt följande."

Ja, här bryter vi citatet ur Liberg: Trolleri för alla.
I labbuppgiften ingår nämligen att ta reda på kortkonstens hemlighet! Du ska därför göra ett program där man kan simulera korttricket så här:

     Vilken ordning ligger korten i? 3   1   4   2   5 
     De kommer ut i denna ordning: 1 2 3 5 4

I denna labb ska du implementera en kö på två olika sätt. Med den abstrakta datastrukturen kö kan man göra tre saker:

  • enqueue(x)            # stoppa in något sist
  • x = dequeue()        #plocka ut det som står först
  • isEmpty()               #kolla om kön är tom

Uppgifter

  1. ArrayQ - en kö med Pythons array


    I första uppgiften ska du skriva en egen klass ArrayQ där du implementerar en kö med hjälp av pythons array.

    • Börja med att importera modulen array med from array import array
    • Bestäm vilken typ av data du vill lagra.
    • Skapa en array och experimentera med array-metoderna append, insert, remove och pop. Rita bilder som illustrerar vad metoderna gör. Vilka vill du använda i din enqueue respektive dequeue? 
    • Nu är du redo att skriva din egen klass ArrayQ.
    • Attribut: En array (och ev andra attribut som du vill ha med). Alla attribut ska vara privata.
    • Metoder:  __init__, enqueue, dequeue och isEmpty (men inga andra metoder).

  2. Testa ArrayQ

    Prova din kö med följande testprogram: 
       q = ArrayQ()
   q.enqueue(1)
   q.enqueue(2)
   x = q.dequeue()
   y = q.dequeue()
   print(x,y)   # 1 2 ska komma ut

  3. Skriv Trollkarlsprogrammet

    Skriv ett program som simulerar korttricket (se exemplet överst i labben). 

    Inmatningstips är att använda input() för att läsa in hela raden, split() för att dela upp den och int() för att konvertera till heltal. Experimentera sedan med olika inmatade ordningar och se om du kan lista ut i vilken ordning korten ska ligga innan man börjar trolla för att man ska få ut alla tretton i rätt ordning

  4. Skapa en ArrayQ-modul

    Gör nu så här: klipp ut klassen från ditt program och klistra in i en ny fil arrayQFile.py
    Importera klassen till huvudprogrammet med raden
            from arrayQFile import ArrayQ
    Nu går det att använda klassen utan att den syns i programmet.

  5. LinkedQ - en kö av noder (länkad lista)

    Nu ska du istället implementera kön som en länkad lista. Då behövs två nya klasser: Node och LinkedQ.  Skriv in bägge klasserna i samma fil: linkedQFile.py. Noderna i listan är objekt som vardera innehåller två  attribut: ett värde (value) och en referens till nästa objekt (next).

    Själva LinkedQ-klassen ska ha två (privata) attribut: first som håller reda på den första noden i kön och last som pekar ut den sista. Använd samma gränssnitt som i uppgift 1:

    • enqueue(x)
    • x = dequeue()
    • isEmpty()

    Det är extra knepigt att programmera enqueue(x) eftersom det blir två fall, beroende på om kön är tom eller inte. Rita upp bägge fallen (lådor med pilar) innan du skriver koden!

  6. Trollkarlsprogrammet med LinkedQ

    Ändra import-satsen i trollkarlsprogrammet så att du importerar klassen LinkedQ istället för ArrayQ. Provkör. Fungerade det? Då har du lyckats implementera den abstrakta datastrukturen kö på två olika sätt.

    Programmet konverserar också intelligent. Mata till exempel in meningen                                                                         JAG GILLAR NÄR DU KRAMAR MEJ.

När allt fungerar som det ska bör du ta en extra titt på koden. Är den kommenterad och begriplig? 
Vid redovisningen ska du kunna 

  • Berätta vad array-metoderna append, insert, remove och pop gör, vilka du valt att använda, och varför.
  • Förklara varför attributen ska vara privata.
  • Rita upp hur dina metoder fungerar för bägge implementationerna av kön.
  • Fungerar de två implementationerna likadant? Förklara eventuella skillnader.

Betyg

Denna labb kan endast ge betyg E. Du måste lämna in den och redovisa den i tid för att få göra labbarna för högre betyg i nästa period.

Redovisning

Labben lämnas in via git och redovisas muntligt av bägge gruppmedlemmarna.