INDA - Övning 4 våren 2005


Uppgiften ska lämnas till din övningsledare på övningen i vecka 6. Glöm inte försättsbladet (pdf) och att alla papper ska häftas samman eller lämnas in i en plastficka.

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 10 i programmeringsboken och se till att du förstår hur abstrakta klasser och gränssnitt (interface) fungerar i Java. Studera avsnittet om hashing (7.3) i algoritmboken.


Skriftlig uppgift
Lös uppgift 10.58 i programmeringsboken.

Lös uppgift 7.3.1 och 7.3.7 i algoritmboken.

Beräkna tidskomplexiteten i medelfall för sökning, insättning och borttagning i en

  • osorterad vektor,
  • sorterad vektor,
  • osorterad enkellänkad lista,
  • sorterad enkellänkad lista,
  • hashtabell (du kan anta att antalet element är lika med hashtabellens storlek).
Presentera lösningen i en tabell med tre rader och fem kolumner. Som vanligt ska du också motivera dina svar.

Implementera följande gränssnitt med hjälp av öppen hashning (open hashing) så som det beskrivs i avsnitt 7.3 i algoritmboken.
/**
 * An interface describing the ADT (abstract data type)
 * dictionary. The dictionary cannot contain duplicate
 * strings.
 * 
 * @author Stefan Nilsson
 * @version 2005-01-24
 */
public interface StringDictionary
{ 
    /**
     * Adds the given string to this dictionary.
     * Returns <code>true</code> if the dictionary
     * did not already contain the given string.
     */
    public boolean add(String s);

    /**
     * Removes the given string from this dictionary
     * if it is present. Returns <code>true</code> if
     * the dictionay contained the specified element.
     */
    public boolean remove(String s);

    /**
     * Returns <code>true</code> if the string is
     * in this dictionary.
     */
    public boolean contains(String s);
 }
Hashtabellens storlek (antalet element i vektorn) ska anges när man skapar en ny tabell. Använd gärna din implementation av länkade listor från föregående uppgift. Som vanligt ska du skriva lämplig testkod.


Stefan Nilsson
2005-01-24