Tietorakenteet, syksy 2009

Harjoitustyö 2

Jätettävä tarkastettavaksi viimeistään 6.11.2009

a.Listaoperaatiot

Käytä mallina List-luokkaa ja tee luokka DList, jossa lista on ketjutettu kahteen suuntaan rengaslistaksi. Lista on järjestetty, joten se voisi olla sorted-listin aliluokka (voit tehdä sen myös aivan omaksi luokakseen ja kopioida pohjaksi List-luokan)

Toteuta DListille seuraavat operaatiot. Listaan siis sijoitetaan kokonaislukuja, jotka ovat listassa järjestyksessä.

Insert( int x)  - lisää luvun x listaan
Find(int x) - etsii luvun x listasta
Delete(int x) - poistaa luvun x listasta.
Print() tulostaa listan.

Metodisi voivat olla tietysti muunkin nimisiä.

b.Binääripuu lajittelumenetelmänä

Luennoilla on esitelty BST- binaarinen hakupuu luokka ja sen metodit. Muunna luokkaa siten, että voit sijoittaa puuhun olioita, joissa on kaksi komponenttia

avain - arvo, jonka mukaan oliot asettuvat järjestykseen puuhun
tieto - valitse haluamasi tieto tietokentäksi (esim. nimi, numero, tai mikä tahansa)

Puuhun sijoitetaan siis olioita joiden sisältö on (avain, arvo) siten, että ne järjestyvät puussa avainarvonsa mukaisesti - siis vasemmassa alipuussa ovat oliot, joiden avain-tieto on pienempi kuin juuren ja oikeassa alipuussa oliot, joiden avaintieto on suurempi kuin juuren avain.

Käyttöliittymän on sellainen, että kun käyttäjä haluaa lisätä olion puuhun, hänen on annettava näppäimistöltä sekä avain, että tieto.

Vihje: Kun puuhun sijoitettaessa joudutaan vertailemaan onko avain suurempi tai pienempi kuin juuri, kannattaa tehdä tälle sisältöluokalle metodi (gt (greater than), tai lt (less than)). Siis kun bst - luokassa on solmuluokka (treenode), niin nyt treedoden sisältönä ei ole kokonaisluku vaan olio luokasta (esim. solmuluokka)

class solmuluokka;
int avain;
mytype tieto;

public boolean gt(solmuluokka s) { vertaa onko this:in avain pienempi kuin s:n }

Kun olet sijoittanut puuhun alkioita, saat tulostettua koko puun avainten mukaan suuruusjärjestyksessä toteuttamalla rekursiivisen sisäjärjestyksessä läpikäynnin (ks. luennot).

Ei ole tarpeen toteuttaa poisto-metodia puullesi, vaan siis

- olion (avain, tieto) lisäys binääriseen hakupuuhun
- puun tulostaminen järjestyksessä.

Näin voidaan bst:tä käyttää tehokkaana lajittelumenetelmänä.