Tietorakenteet / 2. kurssikoe 10.4.2002

Tehtävä 2.

Ratkaisuehdotuksia ja selostusta arvostelusta.

Lista-luokassa tarvitaan operaatiot listan luomiseen sekä alkion
lisäämiseen, poistamiseen ja etsimiseen listasta. Tehtävässä voi
lakaista kaiken varsinaisen työn maton eli Listan alle: kopioidaan
hajautustaulun operaatioiden määritelmät ja vaihdetaan hajautustaulun
tilalle lista.

Listan operaatiot (puuttuessaan -2 pisteen arvoiset):

public Lista()
  luo tyhjän listan

public void insert(Hashable arvo)
  lisää "arvon" listaan; jos jo löytyi, ei tee mitään

public void remove(Hashable arvo)
  poistaa "arvon" listasta; jos ei löydy, mikään ei muutu

public Hashable find(Hashable arvo)
  palauttaa viitteen olioon, joka on equals-sama "arvon" kanssa; jos
  ei löydy, palautetaan null.

(Käyttämällä Hashable-olioita listassa välttää muunnoksen hajatustaulun
find-metodissa.)

Nyt AvoinHajautus-luokan toteutuksessa ei ole enää oikeastaan mitään
tekemistä. (AvoinHajautus piti siis toteuttaa Javalla, suomeksi
toteutettuna tehtävästä sai max 4 pistettä.)

public class AvoinHajautus {
    private Lista[] taulu;

    public AvoinHajautus(int koko) {
        taulu = new Lista[koko > 0 ? koko : 13]; // tarkistetaan koko

        // luodaan listat valmiiksi, säästää kirjoitusvaivaa metodeissa
        for (int i = 0; i < taulu.length; ++i) {
            taulu[i] = new Lista();
        }
    }

    public void insert(Hashable arvo) {
        if (arvo != null) { // tämäkin pitää muistaa tarkistaa
            taulu[arvo.hash(taulu.length)].insert(arvo);
        }
    }

    public void remove(Hashable arvo) {
        if (arvo != null) {
            taulu[arvo.hash(taulu.length)].remove(arvo);
        }
    }

    public Hashable find(Hashable arvo) {
        if (arvo != null) {
            return taulu[arvo.hash(taulu.length)].find(arvo);
        } else {
            return null;
        }
    }
}

Koon ja arvon tarkistamisen unohtaminen olivat yleisimmät virheet;
niistä menetti yhden pisteen, samoin kuin muista pikkuvirheistä.
Puuttuva tai jotakin aivan kummallista tekevä metodi aiheutti 2
pisteen menetyksen.