- Ohj2, luennot 19-21, 22.4.-23.4.2005
- Javan tietorakenteet-täydennystä
- Linkitetty lista
- Dynaaminen rakenne: lisääminen ja poisto vakioaikaista (jos tiedetään lisäys/poistopaikka), haun kompleksisuus lineaarinen
- Indeksointi tehotonta (lineaarinen kompleksisuus, vrt. taulukko)
- Perusmalli: alkio sisältää viitteen seuraavaan
- Erillisenä tietorakenteena oma "osoitinolio", joka sisältää linkin sisältöön ja seuraavaan
- esim. LISP-ohjelmointikieli perustuu tällaiseen listarakenteeseen
- Kehittyneempi variaatio: kahteen suuntaan linkitetty lista, jota voidaan kulkea myös "taaksepäin"
- näin toteutettu javan linkitetty lista
- Joukko (set)
- Ei salli alkioiden (avainten) moninkertaisia esiintymiä
- Voidaan toteuttaa hajautustauluna (HashSet) tai tasapainotettuna binääripuuna (TreeSet)
- Hajautustaulussa avaimet ovat "taulukossa" (lokeroissa), lokeron indeksi lasketaan hajautuskoodista hajaustusfunktiolla (esim. jakojäännöksen variaatio)
- hajautustaulua käytettäessä hashCoden pitäisi olla yksilöllinen - muuten avaimet menevät samaan "lokeroon" ja käsittely hidastuu hieman vakioaikaisesta
- jos hajautufunktio on tehokas ja erottelee avaimet, saavutetaan lähes vakioaikainen lisäys, poisto ja haku
- kun taulu täyttyy, rakennetta täytyy laajentaa kuten dynaamisen taulukon kopioinnissa
- TreeSetin käsittelyaika on logaritminen - avaimet ovat binääripuussa. Lisäksi alkiot noudattavat luonnollista tai annettua järjestystä
- Assosiaatiokartta (hakemisto) - Map
- (avain,arvo)-pareja, avain on yksilöllinen
- Avaimet varastoidaan joukkoon, kustakin avaimesta linkki arvoon
- Avainjoukon toteutustavasta riippuen toteutusluokkia mm. HashMap ja TreeMap
- sisältää omat iteraattorit avaimille, arvoille ja avain/arvo-pareille
- HashSet/Map-olion alkioiden iterointijärjestys saattaa muuttua (esim. uudelleenhajautuksen myötä) eikä sillä yleensä ole mitään tekemistä alkioiden syöttöjärjestyksen kanssa. LinkedHashMap/Set sisältää listan, jonka avulla käsittelyjärjestys pysyy vakiona
- Huom. HashTable ja Vector ovat javan vanhemman version luokkia, jotka vastaavat HashMap- ja ArrayList-luokkia ja ovat säieturvallisuuden ansiosta hieman uudempia luokkia hitaampia
- Esimerkit
- dyna/LinLista
- "käsin tehty" linkitetty lista, heikkoutena lähinnä se, että sisältöalkio on sidottu listan rakenteeseen ("seuraava"-attribuutti) - LinListaGen korjaa tämän, mutta vain java 5:ssa
- sanatsortedset, sanatmap, sanatsortedmap, sanatmapgen...
- Esimerkkejä Javan omista tietorakenteista
- XML ja jäsennys
- Materiaalia
- Vesterholm & Kyppö: java-ohjelmointi, luku 25
- Jäsentämisestä
- Vaikka harvat toteuttavat omia ohjelmointikieliä ja kääntäjiä, merkkijonojen käsittely on ehkä tärkein yleinen ohjelmointitehtävä
- Esim: käyttäjän syötteen lukeminen, merkkipohjaiset tiedostoformaatit, SQL-lauseen koostaminen, hakukielet, säännölliset lausekkeet...
- Ohjelmointiympäristöt tarjoavat usein valmiita oikoteitä tiettyihin merkkijonojen käsittelyn osa-alueisiin, mutta lähes aina jotain joutuu tekemään itse
- Esim. lähes jokaiselle kielelle on valmiina XML-jäsennin, mutta on olemassa runsaasti muutakin rakenteista tietoa!
- Jäsennettävän kielen monimutkaisuudesta riippuen jäsennystä voidaan automatisoida: esim. säännölliset lausekkeet tai jäsenninkoodin kieliopin pohjalta generoivat ohjelmat (lex, yacc ym)
- Syvällisemmin: Automaatit ja kieliopit-kurssi
- XML:stä
- XML-standardi esitystapa (puoli)rakenteiselle tiedolle
- Java tarjoaa standardit rajapinnat XML:n käsittelyyn
- ks. JAXP tutorial
- [ http://java.sun.com/xml/jaxp/dist/1.1/docs/tutorial/ ]
- DOM - XML:n käsittelyä puurakenteessa
- Perusrajapinnat: Node ja Nodelist
- Operaatioita esim. solmun haku ID:n mukaan, tietynnimisten solmujen haku, lapsisolmujen haku, tämänhetkisen solmun vanhemman/edellisen/seuraavan solmun haku ym...
- Erittäin helppokäyttöinen rajapinta, mutta ei sovellu suurille dokumenteille, koska dokumentti joudutaan pitämään kerralla keskusmuistissa
- Sisällön erottelu sekaisin tekstiä ja alisolmuja sisältävästä tekstistä saattaa olla työlästä
- Perusteellinen sivusto mm. DOM:n käytöstä JavaScriptillä - quirksmode.org
- [ http://quirksmode.org/ ]
- SAX - Tapahtumapohjaista käsittelyä
- Dokumenttia ei pidetä muistissa, vaan sen lukemisen aikana lähetetään tapahtumia kutsuvalle ohjelmalle
- Tapahtumia esim. elementin alkaminen ja päättyminen
- Tapahtumankäsittely muistuttaa graafisten käyttöliittymien tapahtumankäsittelyä (esim. kun käyttäjä painaa nappia, sovelluksen tapahtumankäsittelijämetodi saa tästä tiedon, jos se on rekisteröitynyt kuuntelemaan tapahtumaa)
- Harjoittelua pääteohjauksissa...
- Esim. itse tehty minimaalinen XML-jäsennysesimerkki
- Harrastusten käsittelyn lisääminen
- Kertaus: vaihe 5
- Esimerkki: kerho/yhteis51
- jasenet - lisätty iteraattori
- standardi rajapinta helpottaa käyttöliittymän erottamista logiikasta - esim. hakutulosten listaus
- harrastukset - 2 iteraattoria
- tavallinen läpikäynti sekä läpikäynti, joka huomioi kun ollaan tietyn jäsenen harrastuksissa (parametrina jäsenid)
- uusi harrastus-luokka
- Huom. tietojen kysely näyttö-luokassa (jäsenen id:n pitää olla tiedossa)
- Harrastuksen tietojen tulostus jäsenen tietojen mukana
- jonoksi-funktion toteutus?
- Tietojen tallennus, olioiden välinen kommunikointi
- ks. CPP-moniste, luku 19
- [ http://www.mit.jyu.fi/vesal/kurssit/cpp/moniste/html/m.htm ]
- Miksi tiedostonkäsittely ennen päätesyöttöä?
- Testaus helpottuu
- Päätesyötön vaatima koodi liittyy myös hakuun ja muokkaukseen, jotka joka tapauksessa tehdään vasta lopuksi (erityisesti hakujärjestelmän tekemisessä ei ole juuri mieltä, ennen kuin olioiden yhteistyö toimii)
- Talletuksen / latauksen tehtävien jako eri luokille
- Testaa datatiedostojen muuttamista ja tulostuksen toimintaa
- Monesta-Moneen suhteiden toteutus???
- Hakutoiminnot - alkua
- HT-vaihe 6 - vaatimukset
- Esimerkki: kerho/talletus6
- naytto - lisätty kutsut tiedostonkäsittelyä varten
- jäsen&harrastus: lisätty tostring ja parse
- huom. myös ohjeet
- kerho - välittäjäluokka