2.8 Taulukko-olioista

Luku esittelee taulukoiden käytön perusideoita: määrittely, taulukosta etsiminen, taulukon järjestäminen. Taulukoiden alkioina käytetään alkeistyyppejä, eräitä olioita, mm. taulukoita.

• Taulukon idea
• Taulukko on olio
• Ohjelmointitekniikkaa: etsiminen taulukosta
• Ohjelmointitekniikkaa: taulukon järjestäminen
• String-olioita taulukossa
• String-oliot ja char-taulukot
• Omia olioita taulukossa
• Taulukko-olioita taulukossa
• Taulukko luokan kenttänä

Taulukon idea

Olkoonpa ohjelmointitehtävänä tulostaa 100 syöttölukua käänteisessä järjestyksessä. Ainoa mahdollisuus ratkaista ongelma jo opitulla kalustolla on:

   int luku1, luku2, 
       .......           // nuo pisteet eivät ole Javaa!
       luku99, luku100;

   // luetaan 100 lukua:

   System.out.println("Anna luku 1");
   luku1 = Lue.kluku();
   System.out.println("Anna luku 2");
   luku2 = Lue.kluku();
       .......           // nuo pisteet eivät ole Javaa!

   System.out.println("Anna luku 100");
   luku100 = Lue.kluku();

   // tulostetaan luvut käänteisessä järjestyksessä:

   System.out.println("Luvut lopusta alkuun:");
   System.out.println(luku100); 
   System.out.println(luku99);
        .......           // nuo pisteet eivät ole Javaa!
   System.out.println(luku2); 
   System.out.println(luku1); 

Taulukon idea on, että yksi muuttujan nimi voi tarkoittaa kokonaista jonoa keskenään samantyyppisiä muuttujia. Kutakin tuollaista "alimuuttujaa" kutsutaan taulukon alkioksi eli komponentiksi. Yksittäisiin "alimuuttujiin" viitatataan indeksoimalla taulukkomuuttujaa:

Jos vaikkapa luku on tuollainen taulukkomuuttuja, ilmaus

   luku[7] 

   luku[7] = 56;
   luku[7] += 3;
   luku[7] = luku[7]*luku[7];
   ++luku[7];
   luku[7] = Lue.kluku();
   System.out.println(luku[7]);
   
   jne, jne ....   

Äskeinen esimerkki voidaan ohjelmoida:

    int[] luku = new int[101]; // Tämä selviää pian!

    // luetaan 100 lukua:

    for (int i=1; i<=100; ++i) {
      System.out.println("Anna luku "+i);
      luku[i] = Lue.kluku();
    }

    // tulostetaan luvut käänteisessä järjestyksessä:

    System.out.println("Luvut lopusta alkuun:");
    for (int i=100; i>=1; --i)
      System.out.println(luku[i]);

    luku[i]

    luku[1], luku[2], ... luku[99], luku[100].

    luku[7+j] = luku[i-3] * luku[i*i];

Taulukko on olio

  int[] luku = new int[101];

• int[] tarkoittaa int-tyyppisistä alkioista muodostuvan taulukon tyyppiä.
• int[] luku määrittelee muuttujan luku ja kertoo, että sen arvoksi voidaan asettaa milloin mikäkin int[]-tyyppinen taulukko-olio (eikä koskaan mitään muuta!).
• new int[101] on taulukko-olion konstruktorin kutsu. Se palauttaa arvonaan 101-alkioisen int-taulukon.

  int luku[] = new int[101];

Taulukot ovat siis Javassa olioita: Ne luodaan konstruktorilla, niitä käsitellään viitteinä, ..., parametrina välitettyä taulukkoa voi muuttaa, metodi voi palauttaa arvonaan viitteen taulukkoon, ...

Sääntöjä:

1. Taulukon indeksit ovat aina int-tyyppisiä.
2. Taulukon ensimmäinen indeksi on aina 0.
3. Taulukon koko on aina konstruktorin kutsussa annettu kokonaislukuarvo ja siis suurin käytössä oleva indeksi on koko-1 (koska ensimmäinen on aina 0).
4. Taulukon käyttäjä on vastuussa siitä, että indeksinä ei käytetä koskaan arvoa joka ei ole välillä [0,koko-1]. Jos käytetään, ohjelman suoritus keskeytetään.
5. Taulukon alkioilla on oletusalkuarvot (esim. 0, 0.0, false, null), koska alkiot ovat oikeastaan taulukko-olion kenttiä, ks. luku 4.2.
6. Taulukko-olion koko ei voi koskaan muuttua. (Mutta taulukkomuuttuja voi tietenkin saada arvokseen uuden - vaikkapa erikokoisen - taulukon.)
7. Taulukon koon saa selville ilmauksella .length Jos muuttujan luku arvona on 101-alkionen taulukko-olio, luku.length on 101. (Taulukko-olioilla on julkinen kenttä length.)

public class KaannaLuvut {
  public static void main(String[] args) {

    int[] luku = new int[100];

    // luetaan 100 lukua:

    for (int i=0; i < luku.length; ++i) {
      System.out.println("Anna luku "+(i+1));
      luku[i] = Lue.kluku();
    }

    // tulostetaan luvut käänteisessä järjestyksessä:

    System.out.println("Luvut lopusta alkuun:");
    for (int i=luku.length-1; i >= 0; --i)
      System.out.println(luku[i]);
  }
}

    for (int i=0; i < luku.length; ++i)
      ...

public class KaannaLuvut2 {
  public static void main(String[] args) {

    int lukumäärä;

    do {
      System.out.println("Montako lukua käännetään? (Vähintään yksi!)");
      lukumäärä = Lue.kluku();
    } while (lukumäärä < 1);

    int[] luku = new int[lukumäärä]; // Huom: muuttuja!

    // Loppuosa ohjelmasta säilyy aivan ennallaan!

    for (int i=0; i < luku.length; ++i) {
      System.out.println("Anna luku "+(i+1));
      luku[i] = Lue.kluku();
    }

    // tulostetaan luvut käänteisessä järjestyksessä:

    System.out.println("Luvut lopusta alkuun:");
    for (int i=luku.length-1; i >= 0; --i)
      System.out.println(luku[i]);
  }
}

Esimerkkejä taulukkomuuttujien määrittelyistä, taulukko-olioiden konstruoinnista ja taulukoiden käytöstä:

public class TauluKokeita  {
  public static void main(String[] args) {

    // Määrittelyitä:

    int[] klukuA;               // taulukkomuuttuja, EI vielä taulukkoa!
    int[] klukuB = new int[10];

    int[] klukuC = {5, -23, 12, 31, 7}; 
                           // tämä ilmaus konstruoi taulukon int[5]
                           // ja asettaa alkioille alkuarvot!!
                           // Näitä voi käyttää VAIN muuttujia
                           // määriteltäessä!

    double[] dlukuA = new double[5];
    double[] dlukuB = {3.14, 7.21, 0.0, 9.1}; // double[4]!

    boolean[] totuusA = new boolean[8];
    boolean[] totuusB = {true, true, false};  // boolean[3]!

    String[] jonoA = new String[3];
    String[] jonoB = {"kissa", "hiiri"};      // String[2]!

    char[] merkkiA = new char[10];
    char[] merkkiB = {'q', 'w', 'e'};         // char[3]!

    // Käyttöä:

    for (int i=0; i<klukuB.length; ++i) // 7:n kertotaulu
       klukuB[i] = 7*(i+1);

    for (int i=0; i<klukuB.length; ++i)
       System.out.println(klukuB[i]);


    klukuA = klukuC;         // KOPIOIDAAN VIITE
    klukuA[1] = 123456;      // MYÖS klukuC[1] MUUTTUU!
    System.out.println(klukuA[1]+" "+klukuC[1]);

    klukuC = new int[5];  // luodaan uusi taulukko klukuC:n arvoksi
    klukuC[1] = -98;
    System.out.println(klukuA[1]+" "+klukuC[1]);
  }
}

7
14
21
28
35
42
49
56
63
70
123456 123456
123456 -98

Ohjelmointitekniikkaa: etsiminen taulukosta

Laaditaan metodi, joka saa parametrinaan int[]-tyyppisen arvon eli kokonaislukutaulukon ja selvittää, löytyykö taulukosta toisena parametrina annettua kokonaislukua. Jos kysytty arvo löytyy, metodi palauttaa haettavan luvun indeksin arvonaan (jos haettavia on taulukossa monia, palautetaan niistä ensimmäisen indeksi). Jos kysyttyä ei löydy, metodin arvo on -1 (Hae.java):

public class Hae {  // Peräkkäishaku int-taulukosta

  private static int hae(int[] taulu, int haettava) {

    for (int i=0; i<taulu.length; ++i) 
      if (taulu[i] == haettava)
        return i; // tärppäsi, lopetetaan

    return -1; // päästiin loppuun eikä löytynyt
  }

  public static void main(String[] args) { // testipääohjelma

    int[] a = {40, 20, 50, 10, 30};

    System.out.println(hae(a, 10));
    System.out.println(hae(a, 20));
    System.out.println(hae(a, 30));
    System.out.println(hae(a, 40));
    System.out.println(hae(a, 50));
    System.out.println(hae(a, 60));

    int[] b = new int[100];
    for (int i=0; i<b.length; ++i)
      b[i] = (int)(300*Math.random()); // arvotaan testisisältö
    System.out.println(hae(b, 123));
  }
}

  3
  1
  4
  0
  2
  -1
  26 

  private static int hae(int[] taulu, int haettava) {
    int indeksi=0;
    boolean loytyi=false;
    int palautusindeksi = -1; // Pessimistinen oletus!

    while (!loytyi && indeksi < taulu.length) {
      if (taulu[indeksi] == haettava) {
        palautusindeksi = indeksi;
        loytyi = true;
      }
      ++indeksi;
    }
    return palautusindeksi;
  }

Jos taulukko on järjestyksessä, ns. binäärihaku on erittäin tehokas väline arvon hakemiseen taulukosta (BinHae.java):

public class BinHae {  // Binäärihaku järjestetystä 
                       // int-taulukosta

  private static int binHae(int[] taulu, int haettava) {

    int vasen = 0;
    int oikea = taulu.length-1;
    int keski;

    while (vasen <= oikea) {
      keski = (vasen+oikea)/2;

      if (haettava == taulu[keski])
        return keski;     // löytyi ja lopetetaan!

      if (haettava < taulu[keski])
        oikea = keski-1;
      else
        vasen = keski+1;
    }
    return -1;  // hakualue tuli tyhjäksi eikä löytynyt
  }

  public static void main(String[] args) { // testipääohjelma

    int[] a = {10, 20, 30, 40, 50};

    System.out.println(binHae(a, 5));
    System.out.println(binHae(a, 10));
    System.out.println(binHae(a, 20));
    System.out.println(binHae(a, 30));
    System.out.println(binHae(a, 35));
    System.out.println(binHae(a, 40));
    System.out.println(binHae(a, 50));
    System.out.println(binHae(a, 60));

  }
}

-1
0
1
2
-1
3
4
-1

Ohjelmointitekniikkaa: taulukon järjestäminen

Yksi tehoton, mutta helposti ymmärrettävä järjestämisalgoritmi on ns. yksinkertainen vaihtojärjestäminen (nousevaan järjestykseen) (VaihtoJarj.java):

public class VaihtoJarj { // Yksinkertainen vaihtojärjestäminen

   private static void vaihtoJarjesta(int[] taulu) {
     for (int i=0; i < taulu.length-1; ++i) 
       for (int j=i+1; j < taulu.length; ++j)
         if (taulu[i] > taulu[j]) { // onko järjestys väärä?
            int apu = taulu[i];
            taulu[i] = taulu[j];
            taulu[j] = apu;
         }
   }

  public static void main(String[] args) { // testipääohjelma

    int[] a = {40, 20, 50, 10, 30};

    for (int i=0; i<a.length; ++i)
       System.out.print(a[i]+" ");
    System.out.println();

    vaihtoJarjesta(a);

    for (int i=0; i<a.length; ++i)
       System.out.print(a[i]+" ");
    System.out.println();

    int[] b = new int[18];
    for (int i=0; i<b.length; ++i)
      b[i] = (int)(300*Math.random()); // vrt. harj. 15

    for (int i=0; i<b.length; ++i)
       System.out.print(b[i]+" ");
    System.out.println();

    vaihtoJarjesta(b);

    for (int i=0; i<b.length; ++i)
       System.out.print(b[i]+" ");
    System.out.println();
  }
}

40 20 50 10 30
10 20 30 40 50
66 250 88 15 124 97 165 119 233 147 220 161 137 185 219 2 5 295
2 5 15 66 88 97 119 124 137 147 161 165 185 219 220 233 250 295

• Vertaillaan ensin ensimmäistä alkiota kaikkiin muihin alkioihin ja vaihdetaan alkiot, jos ne ovat väärässä järjestyksessä.
• Nyt ensimmäisenä on alkioista kaikkein pienin (oikeastaan "alkio, jota pienempiä ei ole"). Sitä ei enää tarvitse käsitellä.
• Otetaan käsittelyyn toinen alkio ja verrataan sitä jäljellä oleviin ja vaihdetaan tarvittaessa. Nyt toiseksi alkioksi on saatu koko taulukon toiseksi pienin alkio.
• Jatketaan menettelyä kolmannelle alkiolle ...
• ...
• Kun toiseksi viimeinen on saatu käsiteltyä, koko taulukko on järjestyksessä.

• Vertaile ensimmäistä ja toista alkiota. Jos ne ovat väärässä järjestyksessä, vaihda ne.
• Vertaile toista ja kolmatta alkiota. Jos ne ovat väärässä järjestyksessä, vaihda ne.
• Vertaile kolmatta ja neljättä ..., jne. Kun olet päässyt loppuun, taulukon viimeiseksi alkioksi on tullut, "kuplinut", alkioista suurin (oikeastaan "alkio, jota suurempaa ei löydy"). Sitä ei enää tarvitse käsitellä.
• Aloita sama menettly uudelleen alusta, mutta etene vain toiseksi viimeiseen alkioon. ...
• ...
• Kun on edetty enää toiseen alkioon saakka, taulukko on järjestyksessä.

   private static void kuplaJarjesta(int[] taulu) {
     for (int i=taulu.length; i > 0; --i) 
       for (int j=0; j < i-1; ++j)
         if (taulu[j] > taulu[j+1]) { // onko järjestys väärä?
            int apu = taulu[j];
            taulu[j] = taulu[j+1];
            taulu[j+1] = apu;
         }
   }

  private static void lisaysJarjesta(int[] taulu) {
    for (int i=1; i<taulu.length; ++i) {
      int apu = taulu[i];
      int j = i;
      while (j > 0 && taulu[j-1] > apu) {
        taulu[j] = taulu[j-1]; 
        --j;
      }
      taulu[j] = apu;
    }
  }

Järjestämisalgoritmien (kuten muidenkin algoritmien!) tehokkuutta voidaan analysoida matemaattisesti: kaikki edelläesitetyt järjestämisalgoritmit kuuluvat ns. luokkaan O(n²). Se tarkoittaa suurinpiirtein, että "jos järjestettävän taulukon koko kaksinkertaistetaan, algoritmin suoritusaika nelinkertaistuu". Parhaat järjestämisalgoritmit "toimivat ajassa O(n*log n)" ns. "yleisessä tapauksessa".

Toisaalta suoritusaikoja voidaan myös kokeellisesti mitata. Pieni vertailu antaa seuraavia suoritusaikoja kun järjestetään 50000-alkoinen int-taulukko (ohjelma VertaileJarj.java) ("testiohjelmasta" on uusi versio 20.10.2003 VertaileJarj2.java) (ajat riippuvat tietysti käytettävästä tietokoneesta, mutta suhteet säilynevät, tässä on kyse sekunneista ja koneen prosessorina on Pentium 4 1.6 GHz):

                arvottu          valmiiksi      käänteisessä
                alkujärjestys    järjestetty    järj. oleva
                                 taulukko       taulukko
              
  vaihtojärj.       10             10              20

  kuplajärj.        20              8              16

  lisäysjärj.        5            << 1             10

String-olioita taulukossa

Myös taulukon komponentit voivat olla olioita eli tarkemmin sanottuna viitteitä olioihin!

String-olioita sisältävä taulukkomuuttuja voidaan määritellä:

   String[] taulu;

  String[] taulu = new String[5]; 

Lause

  String[] taulu = {"kissa", "hiiri", "koira"};

Huom: Pääohjelmametodin pakollinen parametri

  String[] args

  java Ohjelma apina ja gorilla

Esimerkkejä String-taulukoista (STauluKoe.java):

public class STauluKoe {

  private static void tulostaSTaulu(String[] taulu) {
    System.out.println("\n ---- taulukon koko: "+taulu.length+":");
    for (int i=0; i<taulu.length; ++i)
      System.out.println(taulu[i]);
  }

  public static void main(String[] args) {

    String[] ekaTaulu,
             tokaTaulu = new String[5],
             kolmasTaulu = {"kissa", "hiiri", "koira"};

    tulostaSTaulu(kolmasTaulu);

    tulostaSTaulu(tokaTaulu);  // null-alkuarvot

    for (int i=0; i<tokaTaulu.length; ++i)
      tokaTaulu[i] = "(" + i + ")";

    tulostaSTaulu(tokaTaulu);

    //  tulostaSTaulu(ekaTaulu); OLISI TÄSSÄ VIRHEELLINEN!

    ekaTaulu = kolmasTaulu;    // kopioidaan viite!
    tulostaSTaulu(ekaTaulu);

    ekaTaulu = tokaTaulu;
    tulostaSTaulu(ekaTaulu);

    tulostaSTaulu(args);       // komentoriviparametrit    
  }
}

   java STauluKoe apina ja gorilla

 ---- taulukon koko: 3:
kissa
hiiri
koira

 ---- taulukon koko: 5:
null
null
null
null
null

 ---- taulukon koko: 5:
(0)
(1)
(2)
(3)
(4)

 ---- taulukon koko: 3:
kissa
hiiri
koira

 ---- taulukon koko: 5:
(0)
(1)
(2)
(3)
(4)

 ---- taulukon koko: 3:
apina
ja
gorilla

String-oliot ja char-taulukot

Luokka StringBuffer tarjoaa joukon kehittyneitä välineitä merkkijonoarvojen muutteluun (StringBuffer-luokan virallinen määrittely, suuri tiedosto!).

Koska on kuitenkin hyödyllistä oppia tekemään asiat "omin käsin", tässä tutustutaan merkkitaulukon käyttämiseen merkkijonojen käsittelyssä:

Määrittelyt

    char[] jono1 = new char[10];
    char[] jono2  = {'k','i','s','s','a'};

Nyt voidaan ohjelmoida vaikkapa:

     for (int i=0; i<jono2.length; ++i)
        System.out.print(jono2[i]);
     System.out.println(); 

     for (int i=0; i<jono1.length; ++i)
        jono1[i] = '*';

     for (int i=0; i<jono2.length; ++i)
       jono1[9-i] = jono2[i];

     for (int i=0; i<jono1.length; ++i)
       System.out.print(jono1[i]);
     System.out.println(); 

kissa
*****assik

public char[] toCharArray()

public String(char[] value)

public class Aeta { 
  public static void main(String[] args) {

    System.out.println("Anna merkkijono");
    String jono = Lue.rivi();

    char[] mtaulu = jono.toCharArray();

    for (int i=0; i<mtaulu.length; ++i)
      if (mtaulu[i] == 'a')
        mtaulu[i] = 'ä';

    jono = new String(mtaulu);

    System.out.println("Merkkijono muunnettuna:");
    System.out.println(jono);
  }
}

    System.out.println(mtaulu);

Omia olioita taulukossa

   PikkuVarasto[] varastot = new PikkuVarasto[4];

   varastot[0] = new PikkuVarasto(10, "Mehu");
   varastot[1] = new PikkuVarasto(123.4, "Olut");
   ...

   varastot[0].vieVarastoon(30.0);
   System.out.println(varastot[0].paljonkoOn());
   varastot[0].otaVarastosta(7.0);
   System.out.println(varastot[0]);

   varastot[2] = varastot[0];
   System.out.println(varastot[2].mikaNimi());

Taulukko-olioita taulukossa

Huom: Oikeastaan Javassa on vain yksiulotteisia taulukoita, mutta koska taulukon komponentit (ja niiden komponentit!) voivat olla taulukoita, ohjelmoija voi ajatella käytävänsä useampiulotteisia taulukoita.

Määrittely

    int[][] matriisiA;

Määrittely

    int[][] matriisiA = new int[2][2];

Määrittely

    int[][] matriisiB = { {1, 2}, {3,4} };

Myös kaksiulotteisen taulukon alkioihin viitataan indeksoiden:

    matriisiB[0]

    {1, 2}

    matriisiB[0][1]

Kaksiulotteisen taulukon alkiot voidaan läpikäydä vaikkapa lauseella:

    for (int rivi=0; rivi<matriisi.length; ++rivi)
      for (int sarake=0; sarake<matriisi[rivi].length; ++sarake) 
        // alialgoritmi yhden alkion käsittelyyn

Laaditaan esimerkkisovellus, joka lukee 2*2-matriisin ja tulostaa sen 7:llä kerrottuna (so. jokainen alkio kerrotaan 7:llä) (Matriisi7.java):

public class Matriisi7 {
  public static void main(String[] args) {

    int[][] matriisi = new int[2][2];

    // luetaan arvot:

    for (int rivi=0; rivi<matriisi.length; ++rivi)
      for (int sarake=0; sarake<matriisi[rivi].length; ++sarake) {
        System.out.println("Anna alkio "+rivi+", "+sarake);
        matriisi[rivi][sarake] = Lue.kluku();
      }

    // kerrotaan alkiot 7:llä:

    for (int rivi=0; rivi<matriisi.length; ++rivi)
      for (int sarake=0; sarake<matriisi[rivi].length; ++sarake)
        matriisi[rivi][sarake] *= 7;  // operaatio '*='kertoo!

    // tulostetaan matriisi:

    System.out.println("Seitsemällä kerrottuna:");
    for (int rivi=0; rivi<matriisi.length; ++rivi) {
      for (int sarake=0; sarake<matriisi[rivi].length; ++sarake)
        System.out.print(matriisi[rivi][sarake]+"\t");
      System.out.println();
    }

  }
}

Taulukko luokan kenttänä

Toteutetaan luokka AlaspainLaskureita, sadasta alaspäin laskevien laskureiden toteutukseksi:

• Konstruktori public AlaspainLaskureita(int kpl) luo AlaspainLaskureita-olion, jolla on kpl kappaletta laskureita. Jos kpl on ykköstä pienempi, luodaan yksilaskurinen olio.
• Metodi public int seuraava(int n) paluttaa arvonaan n:nnen laskurin arvon ja vähentää sitä yhdellä. Kun laskuri saavuttaa nollan, sen arvo ei enää vähene. Jos n on virheellinen, metodi palauttaa arvon -1.

public class AlaspainLaskureita {

  // tietorakenne:

  private int[] laskurit;

  // konstruktori:

  public AlaspainLaskureita(int kpl) {
    if (kpl<=1) 
      laskurit = new int[1];
    else
      laskurit = new int[kpl];
    for (int i=0; i<laskurit.length; ++i)
      laskurit[i] = 100;  
  }

  public int seuraava(int n) {
    if (n<0 || n>=laskurit.length)
      return -1;
    int arvo = laskurit[n];
    if (laskurit[n]>0) 
      --laskurit[n];
    return arvo;
  }

  // testipääohjelma:

  public static void main(String[] args) {
    
    AlaspainLaskureita a = new AlaspainLaskureita(10);
    AlaspainLaskureita b = new AlaspainLaskureita(-10);

    // vähentyminen:
    System.out.println(a.seuraava(3));
    System.out.println(a.seuraava(3));
    System.out.println(a.seuraava(3));

    // virheellinen alkio:
    System.out.println(a.seuraava(12));

    // loppuuko väheneminen:
    for (int i=0; i<98; ++i) {
       int apu = a.seuraava(7);
    }
    System.out.println(a.seuraava(7));
    System.out.println(a.seuraava(7));
    System.out.println(a.seuraava(7));
    System.out.println(a.seuraava(7));

    // tuliko yhden mittaiseksi väärästä konstruoinnista:
    System.out.println(b.seuraava(0));
    System.out.println(b.seuraava(0));
    System.out.println(b.seuraava(1));
  }
}

100
99
98
-1
2
1
0
0
100
99
-1

Takaisin luvun 2 sisällysluetteloon.