Tietorakenteet ja algoritmit 1				4.5.2009

Harjoitus 8

Nämä harjoitukset molemmilla ryhmillä ma 4.5. 12-14 T2/D106.
Ohjaus ke 29.4. 10-12.

Kurssin loppukoe ke 6.5. 12.00 - 14.00 T2/D106.

Toteutetaan sanakirja (operaatiot insert, contains, remove, sekä
läpikäynti) suljetulla hajautuksella. Alkiotyyppinä on geneerinen tyyppi
ja hajautukseen käytetään ko. tyypin hashCode() metodia. Varsinaisena
hajautustauluna toimii taulukko (ei Vector tms.). Luokan runko on
www-sivulla.

Seuraava X4 tehtävä on pakollinen kaikille opiskelijoille. X-tehtävien
ratkaisujen pitää olla kunkin opiskelijan itse tekemiä. Saman ratkaisun
kopioita ei hyväksytä (versioitunakaan). Vastaukset pitää lähettää
edeltävänä päivänä (su) klo 20.00 mennessä sähköpostitse allaolevaa
ohjetta käyttäen. Saat automaattisen vastauksen pian onnistuneen
lähetyksen jälkeen. Vastauksen on sisällettävä lyhyt itsearviointi jossa
arvioit ratkaisun toimivuutta, aikavaativuutta ja mahdollisia
parannusmahdollisuuksia. Oikea itsearvointi (jonkinlaiseen ratkaisuun)
on yhden pisteen arvoinen.

Lähetä ratkaisusi cs:n käyttäjälle sjuva käyttäen viestin otsikkona
merkkijonoa TRA1_X4_tunnus missä tunnus on sinun cs-käyttäjätunnuksesi
(tai tunnus@cc). Helpointa lähettäminen on cs:ltä käyttäen komentoa:

    /usr/ucb/mail -s TRA1_X4_tunnus sjuva < tunnus.java

missä tunnus on cs-käyttäjätunnuksesi ja tunnus.java on ohjelmatiedosto
joka sisältää vastauksesi. Jotta tehtävä kääntyisi, on pääohjelman
luokan nimen oltava täsmälleen sama kuin käyttäjätunnuksesi (kuitenkin
ilman @cc tms. osuutta). Ohjelman on siis oltava sähköpostin runkona
sellaisenaan (ilman MIME/HTML -koodauksia, allekirjoituksia, uusia
rivityksiä tms.).

X4) Täydennä operaatiot insert(E x) ja contains(E x). insert() lisää
    alkion sanakirjaan jollei sitä siellä jo ennestään ole.
    Talletusaluetta ei tarvitse täyttyessä laajentaa, poikkeus riittää.
    contains() palauttaa totuusarvon onko alkio kokoelmassa vai ei.
    Näidenkin operaatioiden on huomioitava mahdollisuus, että
    sanakirjasta on poistettu alkioita (tehtävä 45).

45) Täydennä operaatio remove(E x) joka poistaa annetun alkion
    sanakirjasta. Poistossa alkio korvataan erikoisarvolla removed jotta
    myöhemmät haut onnistuisivat.

46) Toteuta uudelleenhajautus (enlarge()) hajautustaulun lähestyessä
    täyttä (2/3 alueesta täynnä). Metodi varaa uuden kaksinkertaisen
    talletusalueen ja siirtää alkiot sinne.

47-48) Toteuta sanakirjan läpikäynti (lisää luokkaan rajapinnan Iterable
    toteutus). Katso esimerkkiä www-sivun JLaukku luokasta.