Del A
A) Uppgiften går ut på att implementera en datasamling för att hålla reda på en mängd objekt. Datasamlingen skall vara en länkad lista som du implementerar från grunden och skall vara specifik för objektet X. Vilken datatyp står för X kommer att beskrivas senare.
Listan skall vara en enkellänkad med två referenser, en till första noden och en till sista.
Följande metoder skall implementeras för datasamlingen:
-Lägga in objektet X i datasamlingen. Objekten skall läggas i slutet av listan med bästa tänkbaratidskomplexiteten.
-Lägga in objekt X i datasamlingen. Objekten skall läggas i början av listan med bästa tänkbara tidskomplexitet.
-Ta bort objekt på plats index i datasamlingen. Metoder skall kasta undantag (exception) om index är för stor eller för liten.
-Ta bort sista noden i listan
-Söka efter objekt i datasamlingen med bästa tänkbara tidskomplexiteten -Returnera ett träd med alla unika objekt från Datasamlingen. Använd java.util.TreeSet klassen
Programmet: För att bevisa att klassen Datasamling fungerar skall du implementera ett program med en enkel meny (textuell interface) där användaren kan göra följande val:
-Lägg till objekt i samlingen. Data till objektet skall läsas in från användare med Scanner. Objektet skall kunna läggas först eller sist i listan utifrån användaren önskemål.
-Sortera samlingen. Sorterings kriteriet skall läsas in från användaren med Scanner-objekt. Sortera datasamlingen utifrån två av objektens egenskaper. Vi antar att klassen Datasamling är en subtyp av java.util.List, det vill säga att du kan sortera samlingen med Collections.sort() algoritmen. På vilket sätt samlingen skall sorteras skall vara argument till metoden.
OBS! Om du vill att din kod skall kompileras måste klassen Datasamling implementera interfacen List. Detta kan du göra om du vill men låt metoderna från interfacen vara ”tomma” med enbart return av rätt datatyp.
-Skriv ut alla unika objekt i samlingen genom att använda trädets iterator
Objektet X som du skall använda är Konto med egenskaperna (namn och saldo).Utöver konstruktor, kan du lägga i klassen metoder om du tycker du behöver det.
För objektet X skall du överskriva metoderna toString() och equals(), hashCode().
Arbetsgång och poängsättning:
1.Implementera först klassen som beskriver objektet X som skall ingå i din Datasamling enligt beskrivningen
2.Implementera två Comparator-objekt som kan göra det möjligt att objekten du implementerar kan jämföras utifrån två av sina egenskaper.
3.Implementera klassen som beskriver en nod i datasamlingen. Detta skall vara specifik för ditt objekt (det får inte vara Object eller AnyType)
4.Implementera klassen Datasamling som är en länkad lista med metoderna som jag tidigare har beskrivit
5.Implementera programmet
B) För alla metoder i klassen Datasamling förklara vad är tidskomplexiteten. Motivera
C) För att bevisa att alla objekt från Datasamlingen finns i trädet som returneras av metoden som du har implementerad tidigare skall du skriva en testmetod med hjälp av jUnit test. Du behöver inte skapa en riktig DatasamligTest fil skriv bara koden som skulle testa det beskrivna scenariot. Beskriv också med ord vad du skall testa och varför.
D) Förklara kort skillnaden mellan dessa två datastrukturer samt ge exempel på situationer/applikationer där du kan använda båda datastrukturerna nedan. Förklara hur du resonerar i val av datastruktur och vilka är fördelarna respektive nackdelarna med var och en. Hashtabell, Binär sökträd.
E) Vilken av följande operationer har lägre tidskomplexitet för en sorterad länkad lista än för ett balanserat binärt sökträd? Motivera svaret!
1) Utskrift av elementen i storleksordning
2) Lagring av ett genomsnittligt värde
3) Misslyckad sökning
4) Beräkning av summan av elementen
5) Sökning efter minsta värdet
Del B
A)En snabb sökstruktur innehåller uppgifter om faktorer till alla heltal mellan 1 och 10000. T ex innehåller strukturen heltalet 60 och dess faktorer 2, 2, 3 och 5 (60 = 2 * 2 * 3 * 5). Ett program skapar en sådan sökstruktur, och använder den för att förkorta olika bråk. Programmets användare kan t ex ange bråket 60 / 72, och få den i förkortad form 5 / 6. Bråkets nämnare och täljare ska inte överstiga 10000. Skapa först den här datastrukturen som du finner lämpligast. Använd sedan datastrukturen i ett program där som först fyller datastrukturen med alla värden och sedan låter användaren mata in bråktal. Resultatet skall skrivas ut på skärmen. Utöver skall programmet bevisa att resultatet är korrekt.
B)Motivera för dit val av datastruktur samt tidskomplexiteten för alla metoder i datastukturen.
C)Förklara i vilka situationer väljer du att implementera algoritmer och datastrukturer som generiska.
