3. harjoitukset 16.-20.11.2009

Lisää harjoitusta vieläkin Ohjelmoinnin perusteiden hengessä...

6. & 7.
   [Tämä tehtävä liittyy Ohjelmoinnin perusteet -kurssin oppimateriaalin lukuihin 2.7 String-olioita ja char-arvoja ja 2.8 Taulukko-olioista]
   Kun jokin ohjelmointikielen väline vaikuttaa helppokäyttöiseltä ja joustavalta, kyseessä on se, että joku jossakin on toteuttanut, ohjelmoinut, tuon helppouden! Eikä se välttämättä ole ollut helppoa...

   Luokassa String on monenlaisia välineitä merkkijonojen käsittelyyn. Kerran luotu String-olio tunnetusti ei kuitenkaan voi koskaan muuttua, ne ovat kerran synnyttyään muuttumattomia, "immutaabeleita". Ohjelmoi ja testaa oma merkkijonoluokka OmaString muutettavien merkkijononojen toteutukseksi. Tehtävän ratkaisemisessa on pyrittävä välttämään roskienkerääjän ylensyöttämistä. Itse asiassa Java-APIssa on olemassa luokat StringBuilder ja StringBuffer muutettavien merkkijonojen käsittelyyn, mutta asioiden tekeminen omin käsin on opettavaista!

   Luokan OmaString määrittely alkaa:

    public class OmaString {
   
      public static final int MAKSIMIPITUUS = 100; // pisin mahdollinen merkkijono 
                                                   // ("final" tarkoittaa vakiota);
                                                   // tätä voi kysyä luokan ulkopuolelta
                                                   // OmaString.MAKSIMIPITUUS
   
      private char[] mjono; // merkkijononon esitys char-taulukkona
      private int pituus;   // montako alkioita mjono:n alusta on käytössä
      ...
   

   Luokassa on konstruktorit:
   • public OmaString() luo tyhjää merkkijonoa esittävän OmaString-olion.
     (Vihje: tilanne esitetään siten, että kenttä pituus == 0.)
   • public OmaString(String s) luo OmaString-olion annetusta String-oliosta. Jos s on pidempi kuin OmaString.MAKSIMIPITUUS, luotavaan OmaString-olioon otetaan parametrin alkuosa.
     (Vihje: Jos siis parametri on vaikkapa "Helppoa ja hauskaa!", merkit viedään mjono-taulukon alkuun ja pituus-kentän arvoksi tulee 19.)
   • public OmaString(OmaString m) luo aidon kopion parametrina annetusta OmaString-oliosta.
     (Vihje: myös taulukko-olio on syytä kopioida! Miksi?)

   Lisävihje ja -ohje (19.11.): Huomaa että aina luodaan taulukko, jonka koko on MAKSIMIPITUUS! Taulukko-oliota ei tässä tehtävässä koskaan vaihdeta esimerkiksi suuremmaksi!

   Luokka tarjoaa aksessorit:

   • public int length() palauttaa arvonaan OmaString-merkkijonon pituuden.
     (Vihje: Palautetaan siis pituus-kentän arvo.)
   • public void replace(char vanha, char uusi) korvaa this-olion kaikki vanha-merkit uusi-merkeillä.
   • public boolean insert(int ind, char merkki) asettaa OmaString-merkkijonon sisään parametrina annetun merkin; ind kertoo, mihin kohtaan merkki lisätään. Jos ind on liian suuri tai liian pieni, lisäystä ei tehdä. Samoin käy jos muutetun merkkijonon pituus tavoittaisi ylittäisi maksimipituuden. Metodi palauttaa arvon true, jos lisäys onnistui, muuten false.
     (Vihje: Merkkijonon loppua joudutaan siis siirtämään eteenpäin taulukossa.)
   • public boolean delete(int ind) poistaa OmaString-merkkijonosta merkin kohdasta ind. [lisäys 19.11.:] Metodi myös siirtää poistettua merkkiä seuranneet merkit taulukon alkua kohden. Jos ind on liian suuri tai liian pieni, mikään ei muutu. Metodi palauttaa arvon true, jos poisto onnistui, muuten false.
   • public String toString() palauttaa arvonaan OmaString-merkkijonoa vastaavan String-olion.

   Kirjoita pääohjelma, joka esittelee monipuolisesti OmaString-olioiden käyttöä.

8. Täydennä edellisen tehtävän luokkaa String-luokasta tutuin aksessorein compareTo, equals, charAt, indexOf(char), indexOf(OmaString). String-luokan API-kuvauksesta saa hyviä vinkkejä. Menettele kuitenkin String-luokasta poiketen virheiden käsittelyssä: Kuten edellisessä tehtävässä, älä tässäkään anna ohjelman kaatua virhetilanteisiin. Määrittele sen sijaan "järkevä" suhtautuminen virheisiin.

   Huom: Poiketen String luokan metodista riittää, että tämä compareTo-metodi palauttaa arvon -1, 0 tai 1.
   Huom: Jälkimmäinen indexOf-metodi etsii this-OmaString-oliosta parametrina annettua OmaString-oliota.

   Kirjoita pääohjelma, joka esittelee monipuolisesti näiden laajennettujen OmaString-olioiden käyttöä.

9. Unix/Linux-ympäristössä ja Windowsin DOS-ikkunassa ohjelman syöttötiedot voidaan lukea näppäimistön sijaan tiedostosta, kun käytetään ns. standardisyöttövirran uudelleenohjausta:

        java Ohjelma < tiedosto
   

   Samoin ohjelman tulosteet voidaan ohjata tiedostoon kuvaruudun sijasta:

        java Ohjelma > tiedosto
   

   Myös molemmat voidaan tehdä:

        java Ohjelma < tiedosto1 > tiedosto2
   
   

   Laadi ohjelma Humanisoi, joka tekee syöttötiedostosta sellaisen kopion, jossa jokainen numeromerkki on korvattu merkillä '*'. Ohjelma suoritetaan komennolla:

        java Humanisoi < teksti.txt > humanoitu.txt
   

   Vihjeitä

   • Voit käyttää - jos haluat - tässä tehtävässä hyväksesi tehtävässä 6 & 7 toteutettua luokkaa OmaString!
   • Tiedoston rivit voi lukea ja käsitellä seuraavalla "idiomilla", "ohjelmahahmolla":

           while (lukija.hasNextLine()) {
             String rivi = lukija.nextLine();
             // ... käsittele yksi rivi
           }
     
     

10. Kokeile, tutki ja mittaa pikajärjestämisen algoritmia (kirjan 4. painoksessa s. 139, vanhemmissa painoksissa s. 128, www-sivulla 3.5 kohta "Rekursiosta") omalla koneellasi tai jollakin laitoksen mikrolla. Varaudu esittelemään mittaustuloksiasi harjoituksissa. Yritä arvella tai päätellä, miksi tuo algoritmi on niin paljon nopeampi kuin muut kursseilla opitut järjestämisalgoritmit. Voit halutessasi tutustua myös menetelmää esittelevään Wikipedia-artikkeliin.

Takaisin harjoitussivulle.