Labb 2: Datastrukturer - kö
- Inlämningsdatum 8 sep 2023 av 18:00
- Poäng 10
- Lämnar in en filuppladdning
- Filtyper py
Mål | Läs i kursboken |
kunna läsa Pythons dokumentation, använda moduler, implementera en datatyp, hantera länkade listor | Kapitel 4.1-4.5, 4.10-4.14, 4.19-4.25 Links to an external site. |
"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... |
Ja, här bryter vi citatet ur Liberg: Trolleri för alla.
Du ska skriva 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 dessa saker:
- Queue() # skapa en tom kö
- enqueue(x) # stoppa in något sist i kön
- x = dequeue() # plocka ut det som står först i kön
- isEmpty() # kolla om kön är tom
- n = size() # antalet element i kön
Uppgifter
-
-
-
ArrayQ - en kö med Pythons array
I första uppgiften ska du skriva en egen klass ArrayQ där du implementerar en kö. Du måste använda pythons array Links to an external site.. Datastrukturen array är inte samma sak som pythons list, men den fungerar på liknande sätt.
- Börja med att importera Links to an external site. 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 Links to an external site., insert Links to an external site., remove Links to an external site. och pop Links to an external site.. 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 Links to an external site. (och ev andra attribut som du vill ha med). Alla attribut ska vara privata Links to an external site. (inledas med understrykningstecken _).
-
Testa ArrayQ
Prova din kö med följande testprogram:
q = ArrayQ() q.enqueue(1) q.enqueue(2) x = q.dequeue() y = q.dequeue() if (x == 1 and y == 2): print("OK") else: print("FAILED")
-
Skriv Trollkarlsprogrammet
Skriv ett program som simulerar korttricket (se videon och exemplet överst i labben).Inmatningstips är att använda input() för att läsa in hela raden, använda split() Links to an external site. för att dela upp den och int() för att konvertera till heltal. ( I denna del med ArrayQ behöver du inte hantera korten Kn, D, K). 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
-
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 ArrayQNu går det att använda klassen utan att den syns i programmet.
Tips: Använd if-satsenif __name__ == "__main__":
i din modul för att inte köra eventuell kod, t.ex. testkod i ArrayQ
-
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). Dessa två attribut behöver inte vara privata.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, med enqueue, dequeue osv.
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!
-
Testa LinkedQ
Prova din kö med följande testprogram (som använder Pythons unittest Links to an external site.):import unittest from linkedQFile import LinkedQ class TestQueue(unittest.TestCase): def test_isEmpty(self): #isEmpty ska returnera True för tom kö, False annars q = LinkedQ() self.assertTrue(q.isEmpty(), "isEmpty på tom kö") q.enqueue(17) self.assertFalse(q.isEmpty(), "isEmpty på icke-tom kö") def test_order(self): #Kontrollerar att kö-ordningen blir rätt q = LinkedQ() q.enqueue(1) q.enqueue(2) q.enqueue(3) self.assertEqual(q.dequeue(), 1) self.assertEqual(q.dequeue(), 2) self.assertEqual(q.dequeue(), 3) if __name__ == "__main__": unittest.main()
-
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. -
Skicka in programmet till Kattis
Logga in på Kattis och skicka in ditt trollkarlsprogram tillsammans med linkedQFile.py Istället för att använda input ska du läsa in från sys.stdin, t ex så härimport sys
Titta också på exemplet "Solving a problem" i Kattis hjälptexter Links to an external site.. Det går bra att skicka in flera filer till Kattis. Välj Click and choose file och markera flera filer (Shift-click).
indata = sys.stdin.readline()
Tips: I andra testfallet är det strängar som ska läggas in i kön istället för heltal. Kan din LinkedQ hantera det?
-
-
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
- I implementationen av ArrayQ: Berätta vad array-metoderna append Links to an external site., insert Links to an external site., remove Links to an external site. och pop Links to an external site. gör, vilka du valt att använda, och varför.
- Varför ska attributen ska vara privata i dina klasser? Förklara.
- Rita upp hur metoderna enqueue och dequeue fungerar för bägge implementationerna av kön.
- Fungerar de två implementationerna likadant? Förklara eventuella skillnader.
Glöm inte att lämna in i Canvas! Det räcker att du lämnar in LinkedQ.
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 period 2.
Redovisning
Labben lämnas in indivuellt med "Lämna in uppgift"-knappen högst upp på sidan, och ska redovisas muntligt av bägge gruppmedlemmarna. Skriv gruppmedlemmarnas namn i kommentarsfältet!