1. Jäsenrekisterin runko

Taulukkoko pienen pieni

vaiko lista suuren suuri

joku muuko miettimäksi

rakenne kerhoon katsomaksi.

 

Kuva tuosta piirtämäksi

tästä temput tutkimaksi

siitä selväksi sävelet

kohtapa jo koodamaksi.

 

Mitä tässä luvussa käsitellään?

·      tietorakenteen valinta

1.1 Runko ilman kommentteja

Emme vielä täysin osaa tehdä edes runkoa jäsenrekisteriohjelmaamme, mutta esitämme tästä huolimatta jonkinlaisen toimivan rungon ohjelmalistauksen.    Koodissa tulee lukuisia vielä käsittelemättömiä osia, joita käsittelemme tarkemmin myöhemmin.  Samoin etsimme myöhemmin sopivan tavan kommentoida aliohjelmia.

Rungon tarkoituksena on tarjota näkyväksi ne toiminnot, jotka ohjelman suunnitelmassa päätettiin tehdä.  Samoin tavoitteena on testata valitun tietorakenteen toimivuus.  Jatkossa toimintoja lisätään tähän runkoon.

Tämä runko ei tietenkään ole syntynyt kerralla, vaan ensin on testattu tietorakenteet yksittäin ja sitten lisätty näiden käyttö valmiiseen menu-runkoon (vrt. menut_3\Naytto.java)

1.2 Valittava tietorakenne

Minkälaisen tietotyypin voisimme valita?  Vaihtoehtoja tulee ehkä lähes yhtä paljon kuin ohjelmoijiakin on.  Voimme kuitenkin vertailla eräiden rakenteiden etuja ja haittoja.  Jos mahdollista, tietorakenteiden tulisi olla yhtenäinen tehdyn oliosuunnitelman kanssa.  Seuraavista ehdotuksista mikään ei ole ristiriidassa edellisessä luvussa tehdyn oliosuunnitelman kanssa.  Vasta kun valitaan harrastusten talletustapaa, joudumme valinnan eteen.

Lähdemme siitä ajatuksesta, että koko käsiteltävä aineisto on kerralla keskusmuistissa.  Voisimme tietenkin operoida myös suoraan levylle, mutta oppimisen tässä vaiheessa voi seuraava ratkaisu olla helpompi:

lue tiedosto muistiin

käsittele aineistoa muistissa

talleta aineisto takaisin levylle

 

1.2.1 Taulukko

Taulukko on kiinteä tietorakenne, jota luotaessa täytyy jo tietää monelleko ihmiselle varaamme tilaa.  Tässä tulee äkkiä varattua tilaa joko liikaa, jolloin tila ei riitä muille toiminnoille, tai liian vähän, jolloin kaikki henkilöt eivät mahdu rekisteriin.  Esimerkissämme olemme varanneet n. 300 tavua/henkilö.  Tilan varaaminen sadalle henkilölle veisi jo 30000 tavua.  Usein sata ei edes riitä!

Kuva 12.1  Taulukko

Javassa asia ei tietysti ole ihan näin suoraviivaista.  Javassahan oliot ovat vaan viitteitä, jolloin oliotaulukko onkin vain taulukollinen viitteitä.  Näin "liian tilan varaaminen" ei ole kovin kohtalokasta, jos jokainen viite vie esim. 4 tavua, niin 100 hengen viitteet vievät 400 tavua.  Edes tuhannen hengen viitteet eivät vie mitenkään katastrofaalisesti tilaa:

 

Kuva 12.2  Javan taulukko

 

Kuitenkin ohjelmoijan omalle vastuulle jää taulukon maksimikoon ja taulukon "käytettyjen" alkioiden lukumäärän ylläpitäminen.  Maksimikokohan saadaan aina taulukon koosta, joten tämä ei ole Javassa kovin suuri vaiva.  Käytettyjen alkioiden määrän ylläpitoon täytyy kuitenkin rakentaa jokin mekanismi.

Javassa on tarjota valmiitakin tietorakenteita, mutta niiden pienenä puutteena on se, että ne tallentavat Object-tyyppisiä olioita.  Tällöin aina kun alkio otetaan tietorakenteesta, pitää sen tyyppi muuttaa vastaamaan todellista tyyppiä.  Taulukossa aliota taas voivat suoraan olla omaa tyyppiään (eli oman tyypin viitteitä).

1.2.2 Linkitetty lista

Linkitetty lista on rakenne, jossa meillä on tieto vain listan 1. alkiosta.  Tämän jälkeen kukin alkio tietää itseään seuraavan alkion, kunnes listan viimeinen alkio ei enää osoita minnekään.

Kuva 12.3  Linkitetty lista

Listan hyvänä puolena on se, ettei etukäteen tarvita mitään tietoa alkioiden lukumäärästä.  Alkioita voidaan lisätä listaan joko alkuun, keskelle tai loppuun niin kauan kuin muistia riittää.

Oppimisen tässä vaiheessa kuitenkin linkitetyn listan käsittelyalgoritmit (lisäys, poisto, lajittelu jne..) saattavat olla liian työläitä. 

Mikäli rakennamme ohjelman huolella, ei tietorakenteen vaihtaminen jälkeen päinkään ole mahdoton tehtävä.  Tätä auttaa vielä aikaisemmin tekemämme valinta käyttää  abstraktia rajapintaa (lisää, poista, etsi) tietorakenneluokan (Kerho tai Jasenet) ja käyttöliittymän (Naytto) välillä.

1.2.3 Sekarakenne

Valitsemme tähän toteutukseen tietorakenteeksi sekarakenteen:

Siis perusrakenteena meillä on Kerho–tyyppi, joka pitää sisällään kerhon perustiedot.  Kerhosta on osoitin taulukkoon, jossa on osoittimet varsinaisiin henkilöiden tietoihin (Jasen). 

Henkilöiden tiedoille varattua tilaa ei ole olemassa ennen kuin sitä tarvitaan.  Siis varataan kullekin kerhoon lisättävälle henkilölle hänen tiedoilleen tarvittava uusi n. 300 tavun "möykky" lisäyksen yhteydessä.

Osoitintaulukkoon sijoitetaan sitten vastaavaan paikkaan sen muistiosoitteen arvo, josta henkilölle tarvittava tila saatiin varattua.

Tässäkin rakenteessa on se huono puoli, että osoitintaulukon koko pitää päättää ennen kuin sinne voidaan sijoittaa osoitteita.  Yksi osoite vie kuitenkin enimmilläänkin tilaa 4 tavua, joten kiinteää tilan varausta esim. 1000 henkilön taulukossa tulee vain 4000 tavua.

Hyvinä puolina rakenteessa on sen suhteellisen helppo käsittely sekä lisäyksen, poiston että lajittelun tapauksessa.

Kuva 12.4  Tietorakenne kun kerho tallettaa jäsenet

 

Tehtävä 12.1  Lisäys

Kirjoita algoritmi henkilön lisäämiseksi rakenteeseen.

Tehtävä 12.2  Etsiminen

Kirjoita algoritmi tietyn henkilön etsimiseksi (vaikkapa nimellä).

Tehtävä 12.3  Poisto

Kirjoita algoritmi löydetyn henkilön (miten löytö kannattaa säilyttää?) poistamiseksi rakenteesta.

Tehtävä 12.4  Lajittelu

Kirjoita algoritmi rakenteen lajittelemiseksi aakkosjärjestykseen.  Mitä lajittelussa kannattaa vaihdella?

1.2.4 Ohjelman runko

Ohjelmalistaus löytyy listausmonisteesta tiedostosta

1.    runko_5\Naytto.java

1.3 Harrastukset mukaan

Jos halutaan tallettaa myös kullekin jäsenelle vaihteleva määrä harrastuksia, on jälleen mahdollisuuksia useita.  Tietorakennetta valittaessa voidaan käyttää samaa kriteeriä kuin tiedostoakin valittaessa. Välttämätöntä tämä ei kuitenkaan ole, vaan voidaan sisäisesti tietysti käyttää myös erilaista rakennetta kuin ulkoisesti.

1.3.1 Tiedot jäsenen yhteyteen

Jos tiedoston muoto on sellainen että harrastukset on lueteltu jäsenen tietojen yhteydessä, kannattaa tietorakennekin valita vastaavasti.

Ankka Aku          |010245-123U|Ankkakuja 6 |12345      |ANKKALINNA |12-12324   |          |

- kalastus                 | 1955 | 20

- laiskottelu              | 1950 | 20

- työn pakoilu             | 1952 | 40

Susi Sepe          |020347-123T|            |12555      |Takametsä  |           |          |

- possujen jahtaaminen     | 1954 | 20

- kelmien kerho            | 1962 |  2

Ponteva Veli       |030455-3333|            |12555      |Takametsä  |           |          |

- susiansojen rakentaminen | 1956 | 15

 

Nyt tietorakenne voisi olla tilanteesta riippuen mikä tahansa edellä esitetyistä siten, että kerhosta alkava rakenne toistuu jäsenen kohdalla.

Esimerkiksi linkitetty lista:

Kuva 12.5  Harrastukset linkitettynä listana

1.3.2 Relaatiomalli

Jos tiedot on talletettu relaatiomallin mukaan, voi olla kannattavaa tehdä myös sisäinen tietorakenne vastaavaksi.  Vaikka jatkossa emme toteutakaan kerhoon vielä harrastuksia, teemme tietorakenteen ja oliot sellaisiksi, että harrastusten käsittely jälkeenpäin olisi mahdollisimman helppoa. 

Toteutettavaa ohjelmaa ajatellen tästä valinnasta seuraa yksi byrokratiaporras (Kerho <-> Jasenet) lisää, joka aluksi saattaa tuntua turhalta.  Valinta maksaa itseään takaisin vasta ongelman monimutkaistuessa.  Tähän samaan monimutkaistumisongelmaan tulemme törmäämään jatkossakin.   Yksinkertaisin mahdollisuus, jolla vaadittu toimenpide juuri ja juuri voidaan suorittaa, johtaa usein jatkoa ajatellen umpikujaan.

Tehtävä 12.5  Lisää harrastus

Kirjoita algoritmi uuden harrastuksen lisäämiseksi. (Ks. alla oleva kuva)

Tehtävä 12.6  Mitä harrastaa

Kirjoita algoritmi, joka vastaa kysymykseen "Mitä henkilö N harrastaa?"

Tehtävä 12.7  Kuka harrastaa

Kirjoita algoritmi, joka vastaa kysymykseen: "Ketkä harrastavat  harrastusta H?".

Tehtävä 12.8  Poista harrastus

Kirjoita algoritmi harrastuksen poistamiseksi.

Tehtävä 12.9  Jäsenen poistaminen

Kirjoita algoritmi, joka poistaa jäsenen jonkin nimi on N.

Tehtävä 12.10                    "Roskaharrastukset"

Kirjoita algoritmi, joka poistaa "roskaharrastukset", eli ne harrastukset, joille ei löydy "omistajaa".  Tällaiseen tilanteeseen hyvässä ohjelmassa ei tietenkään koskaan päädytä.

Tehtävä 12.11                    Monta saman lajin harrastajaa

Jos harrastusten nimet ovat kovin pitkiä ja harrastuksista talletetaan vielä kuhunkin harrastukseen liittyvää lisätietoa, niin edellä mainittu rakenne käy tehottomaksi heti kun löytyy useita saman lajin harrastajia.  Esitä ratkaisu, jossa hukkatilaa (mm. saman harrastuksen nimen toistamista) ei esiinny, mutta jolla voidaan tehdä kaikki samat tehtävät, kuin esitetyllä ratkaisulla.

 

Kuva 12.6  Harrastukset relaation avulla


 

1.3.3 Ohjelman runko harrastusten kanssa

Ohjelmalistaus, jossa harrastuksetkin ovat mukana, löytyy tiedostosta

1.  runko_5\Nayttohar.java

2.