Tietorakenteet ja algoritmit		20.11.2003

Harjoitus 10

Toinen välikoe ti 25.11. 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 merkkijonojen joukko suljetulla
hajautuksella. 

	const MJONOPIT = 40;			#define MJONOPIT 40
	type MJONO = string[MJONOPIT];		typedef char *MJONO;

55) Tee hajautusfunktio

	function MJONO_HASH(x : MJONO; m : integer) : integer;
	int MJONO_HASH(MJONO x, int m);

    joka laskee mistä tahansa merkkijonosta kokonaisluvun väliltä
    0..m-1. Ota huomioon koko merkkijono ja varmista että funktiosi
    antaa kaikkia arvoja väliltä 0..m-1. Arvioi hajautusfunktiosi
    hyvyyttä erilaisilla merkkijonojoukoilla. www-sivulla on yksi
    esimerkkiaineisto.

56) Esittele merkkijonojen joukon ("sanakirjan") toteutus. Käytä
    suljettua hajautusta ja edellisen tehtävän hajatusfunktiota. Toteuta
    merkkijonojoukon operaatiot MJONO_SET_CREATE, MJONO_SET_EMPTY ja
    MJONO_SET_INSERT.

57) Jatka edellistä tehtävää toteuttamalla operaatiot
    MJONO_SET_MEMBER ja MJONO_SET_FREE. ja tee esimerkkiohjelma, joka
    testaa joukon operaatioiden toimintaa edustavasti, myös törmäysten
    tapahtumista ja talletusalueen täyttymistä.

Seuraavissa kahdessa tehtävässä toteutetaan vakioaputilaista
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 6, 8, 2, 3, 4, 5, 1, 11, 12, 7, 10, 9. 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: viimeisen alkion (9) lisäyksen
    jälkeen tehdään kierto vasemmalle ja juuri vaihtuu.