Tietorakenteet, kevät 2003
2. kurssikoe 9.4.

Tehtävä 3 (max 4 + 2 + 2 pistettä)

a) (seuraava on melkein suoraan luentojen luvusta 7)

   Vierusmatriisi on verkon esitys siten, että solmut numeroidaan ja
   särmät esitetään matriisin alkiona. Painottamattoman verkon
   tapauksessa matriisin alkioina voitaisiin käyttää totuusarvoja.

   Jos särmiin liittyy paino, matriisin alkioina voidaan käyttää
   kokonaislukuja tai liukulukuja. Tässä tapauksessa puuttuva särmä
   voidaan esittää mahdottomana painona.

   Vieruslista on verkon esitys siten, että solmut pannaan taulukkoon
   ja solmusta lähtevät särmät esitetään linkittettynä listana.

   Verkon solmuihin liittyvää tietoa voidaan tallettaa taulukon
   alkioina oleviin solmuihin.  Särmiin liittyviä tietoja, esimerkiksi
   painoja, voidaan puolestaan tallettaa särmälistojen alkioihin.

   (Kuvat ja esimerkit tietysti helpottavat selittämistä.)

b) (metodi luentojen StringVerkkoVM-luokassa)

    public void asteet() {
        for(int i=0; i<solmuLkm; ++i) {
            int tulo = 0, lähtö = 0;

            for (int j=0; j<solmuLkm; ++j) {
                // solmun i lähtöaste on rivin i särmien määrä
                // ja tuloaste sarakkeen i särmien määrä
                if (särmät[i][j] > 0) ++lähtö;
                if (särmät[j][i] > 0) ++tulo;
            }

            System.out.println(solmut[i] +
                               " tulo: " + tulo + " lähtö " + lähtö);
        }
    }

c) (metodi luentojen StringVerkkoVL-luokassa)

    public void asteet() {
        int[] tulo  = new int[ekaEiKäytössä];
        int[] lähtö = new int[ekaEiKäytössä];

        for(int i=0; i<ekaEiKäytössä; ++i) {
            for(solmut[i].vieruslista.setIterToStart();
                !solmut[i].vieruslista.iterAtEnd();
                solmut[i].vieruslista.advanceIter()) {
                ++tulo[((SärmänToteutus)
                        solmut[i].vieruslista.getValueAtIter()).kohde];
                // solmun i lähtöaste saataisiin myös kutsumalla
                // solmut[i].vieruslista.getN(), mutta ListaK-luokan
                // getN-metodi käy kuitenkin koko listan läpi
                ++lähtö[i];
            }
        }

        for(int i=0; i<ekaEiKäytössä; ++i) {
            System.out.println(solmut[i].solmu + " tulo: " + tulo[i] +
                               " lähtö: " + lähtö[i]);
        }
    }