bild
Skolan för
datavetenskap
och kommunikation
KTH / CSC / Kurser / DD1339 / inda12 / Vårens uppgifter / Uppgift 2

Uppgift 2 våren 2013

Uppgiften ska lämnas till din övningsledare på övningen den 25/1.

För godkänt måste du ha gjort samtliga deluppgifter. Det är tillåtet att göra enstaka fel och misstag men det är viktigt att du försöker lösa samtliga uppgifter. Om du kör fast med någon uppgift så finns det som vanligt hjälp att få på labbarna.

Hemuppgift

Studera kapitel 9 i programmeringsboken.

Skriftlig uppgift

Arv i Java

Lämna in lösningar till uppgift 9.11-9.16 i programmeringsboken (uppl 4: 9.12-9.17).

Länkade listor

En lista, ett antal element ordnade i en linjär struktur, är den kanske enklaste och mest grundläggande datastrukturen. Java erbjuder flera implementationer av listor:

  • den vanliga vektorn (t.ex. int[]) som har direkt stöd i hårdvara och är enkel men något begränsad,
  • ArrayList som är implementerad med hjälp av en vektor men har ytterligare funktionalitet,
  • och LinkedList som har i stort sett samma funktionalitet som ArrayList men annorlunda prestanda.

En länkad lista är en sekvens av listelement förbundna av pekare. En länkad lista med tre heltal [2, 2, 1] ser ut så här.

     ----------        ----------        ----------
    |     |    |      |     |    |      |     |    |
--->|  2  |  -------->|  2  |  -------->|  1  |null|
    |     |    |      |     |    |      |     |    |
     ----------        ----------        ----------

Listelementen kan implementeras som objekt med två instansvariabler, en variabel som innehåller nodens värde och en variabel som pekar på nästa element i listan:

class ListElement {
    int data;
    ListElement next;
}

Du ska göra följande uppgifter.

  1. Implementera en enkellänkad lista. Ett kodskelettet finns i filen LinkedList.java Du får inte ändra klassens gränssnitt, dvs du får inte ändra signaturerna på de publika metoderna i klassen LinkedList eller lägga till några andra publika metoder.
  2. Beräkna den asymptotiska värstafallstiden för samtliga publika metoder i din implementation. Uttryck tiden som en funktion av antalet element n i listan.
  3. Skriv utförlig testkod. Alla publika metoder ska testas. Glöm inte att kontrollera att din kod fungerar även för den tomma listan. Jag rekommenderar att du skriver testkoden först.

Som vanligt ska du lämna in en utskrift av all kod – dvs även testkoden.

Det kan vara svårt att testa datastrukturer; en metod kan returnera rätt svar men ändå göra fel. Det händer till exempel om den lämnar efter sig instansvariabler med felaktiga värden. En bra sätt att upptäcka den typen av fel är att använda en testmetod som undersöker om listan befinner sig i ett korrekt tillstånd:

  • size är lika med antalet ListElement.
  • Om listan är tom så är first och last båda nollpekare, annars pekar de på listelement.
  • Om ett element ligger sist i listan så är next nollpekaren.

Du ska implementera en metod isHealthy() som kollar detta. På lämpliga ställen (troligen ganska många) i din testkod ska du sedan anropa isHealthy() för att kontrollera att listan inte har gått sönder.

Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
Uppdaterad 2013-01-20