Övningspaket 3: Associativa datastrukturer
Under den här övningen ska vi titta lite på vad som krävs för att kunna använda egna objekt som nycklar i associativa datastrukturer. Vi kommer att använda oss av taggade ord som nyckel.
Taggade ord
Den struktur som ska läsas in är en enkel klass som innhåller två strängattribut: ett löpord och en ordklasstag.
Det är den här klassen vi ska bygga ut så att den går att använda som nyckel.
Eftersom det är en del av inlämningsuppgiften på PST1 att läsa in taggade ord tänker jag inte ge er källkoden för en klass som gör detta. Istället kommer ni att få en förkompilerad klass som ni kan använda. Det går naturligtvis bra att implemnetera en egen!
Jag kommer genomgående att använda denna testtext:
Klassen TokenTag. [java]
Inläsningsklass för TokenTag. [class]
Dokumentation av klasserna TokenTag och TokenTagScanner. [html]
Testtexten som används här. [txt]
Uppgift 1
Skriv en testklass som skriver ut taggade ord. Den ska läsa in från System.in,
och skriva ut varje ord på en egen rad. Använd TokenTagScanner för att läsa
från System.in.
Du borde få ett resultat som liknar det här:
Skriv en String toString()-metod för klassen TokenTag.
Den låter oss styra vad som skrivs ut när vi försöker skriva ut objekt av klassen.
Börja med att skriva en metod som gör att de taggade orden ser ut som de gjorde när de lästes in:
För resten av den här övningen kommer det att vara bra att hålla koll på att de faktiskt
är olika objekt, så bygg ut metoden så att den också anropar sin förälders
toString-metod, så att vi får något som liknar det här:
Uppgift 2
Bygg ut testklassen så att de taggade orden inte bara skrivs ut, utan även lagras i en
HashMap. Associera varje ord med en Integer, så har vi möjligheten
att räkna frekvenser på dem! När du lagrar ett taggat ord i hashtabellen behöver du först
kontrollera ifall den redan finns, gör den det ska den läggas till med sitt gamla värde
plus 1, finns den inte ska den läggas till med värdet 1.
Efter att du lagrat alla taggade ord i din hashtabell ska du löpa igenom nycklarna (använd
keySet()), och skriva ut alla lagrade nycklar och deras associerade värde.
Du borde se något som liknar det här:
Det här är inte riktigt vad vi hade tänkt oss... det verkar som om unika objekt blir unika nycklar, men vi kan ju ha flera objekt som representerar samma taggade ord...
Uppgift 3
Implementera metoderna int hashCode() och boolean equals(Object o)
i klassen TokenTag. Du vet att du har lyckats när unika taggade ord blir unika nycklar!
Uppgift 4
Skriv om testklassen så att den inte längre använder en HashMap, utan en TreeMap.
När du kör den direkt efter omvandlingen kommer du att få ett felmeddelande:
Det är Javas sätt att berätta för dig att bara jämförbara nycklar går att lagra i en TreeMap.
Lösningen är att låta TokenTag implementera gränssnittet Comparable<TokenTag>.
Du gör detta genom att deklarera att klassen implementerar gränssnittet, samt implementera metoden
int compareTo(TokenTag tt). En lämplig implementation av den metoden är att i första hand
jämföra attributet token, och i andra hand attributet tag.
Återigen märks det att du lyckats genom att programmet beter sig som förut, fast med skilnaden att nycklarna är sorterade:
Uppgift 5
Skriv om metoden compareTo, så att den i första hand jämför taggarna, och i andra hand orden.
Teoretisera kring vad du tror kommer att skilja körningen från den ovan innan du testar själv.