Tietorakenteet ja algoritmit		25.11.2004

Harjoitus 10

Demoryhmä 2 (ke 16-18) on yhdistetty torstain ryhmiin (08-10 ja 10-12).

Toinen välikoe ti 7.12. 08.00 - 10.00 M1.

1/3 (= 20) demorasteista vaaditaan 2. välikokeeseen. Demobonukset
lasketaan vain 1/3 ylittävältä osalta siten, että 1 demopiste vastaa
0,225 koepistettä. Pyöristyksiä ei käytetä.

Täytä opintojakson arviointilomake http://cs.joensuu.fi/~arvio/

Seuraavissa tehtävissä toteutetaan reaalilukujoukko suljetulla
hajautuksella.

55) Tee hajautusfunktio

    function real_hash(x : real; m : integer) : integer;

    joka laskee mistä tahansa reaaliluvusta kokonaisluvun väliltä
    0..m-1. Huomioi myös desimaalit ja hyvin suuret luvut. Arvioi
    hajautusfunktiosi hyvyyttä erilaisilla reaalilukujoukoilla (hyvin
    suuria, pieniä, 0..1, negatiivisia, jne).

56) Esittele reaalilukujen joukon ("sanakirjan") toteutus. Käytä
    suljettua hajautusta ja edellisen tehtävän hajatusfunktiota. Toteuta
    reaalilukujoukon operaatiot REAL_SET_CREATE ja REAL_SET_INSERT.

57) Jatka edellistä tehtävää toteuttamalla operaatio REAL_SET_MEMBER ja
    tee esimerkkiohjelma, joka testaa joukon operaatioiden toimintaa
    edustavasti, myös törmäysten tapahtumista.

Seuraavissa kahdessa tehtävässä toteutetaan vakioaputilaista
merkkijonojen kasalajittelua käyttäen syötetaulukon alkupäätä
talletusrakenteena prioriteettijonolle (binääripuulle). Www-sivun pohja
sisältää aliohjelmien otsitkot ja varsinaisen lajittelun.

58) Toteuta puuoperaatiot LEFT_CHILD, RIGHT_CHILD, PARENT, ROOT ja SWAP.
    SWAP vaihtaa kahden parametrinsa solmujen sisällöt keskenään.

59) Toteuta operaatiot jarjestaalas ja jarjestaylos. Testaa operaatioita
    pohjan kasalajittelualgoritmilla.

60) Simuloi käsin AVL-puun toimintaa. Lisää (aluksi tyhjään) AVL-puuhun
    alkiot 18, 7, 4, 10, 12, 20, 15, 1, 2, 5, 6, 3. Piirrä puu uudestaan
    kunkin sellaisen lisäyksen jälkeen, jossa tarvittiin kiertoa tai
    kaksoiskiertoa. Merkitse kunkin solmun tasapaino (- -, -, 0, +, + +)
    kussakin tilanteessa. Korjaa tasapainoja lisäyksen jälkeen alhaalta
    ylös aina sen mukaan kummalle puolelle lisäys kohdistui. Tasapainon
    muutos pysähtyy tasapainon muuttumiseen 0:ksi tai kiertoon.
    Itsetarkastukseen: toiseksi viimeisen alkion (6) lisäyksen jälkeen
    tehdään kaksoiskierto oikealle ja juuri vaihtuu.