Ohjelmointi (Pascal)

Harjoitus 12, 2.-5.12       (koko moniste)
                            (Oh! Pascal! sivut  2 - 548,
                             ei lukuja 5-2, 9-2, 11-3, 12-3, 15-2, 15-3,
                             10 vain kursorisesti,
                             ei sivuja 237-239, 244-245,
                             ei get- ja put-operaatioita,
                             16 vain kursorisesti)

Huom: 6.12. ryhmäläiset saavat vierailla haluamassaan ryhmässä!

Yleensä Pascal-toteutuksissa tyyppi set of integer ei ole mahdollinen. 
Kokonaislukujen osajoukkoja voidaan kuitenkin  esittää esimerkiksi 
linkitettyinä listoina:

                    
        [4, 7] :          4         7



        [67, -96, 101] :        -96         67           101



        [-24891, 89, 15673] :     -24891         89        15673



        [] :
              


Sovitaan, että
        type joukko = ^arvo;
             arvo = record
                      luku : integer;
                      next : joukko
                    end;
        var A, B, C, D : joukko;


Joukko siis esitetään linkitettynä listana, johon osoittaa joukko-
tyyppinen osoitinmuuttuja. Joukkoon kuuluva alkio esitetään arvo-
tyyppisenä listan tietueena. Tietorakenteen toteuttamisessa on useita 
vaihtoehtoja. Lista voi olla järjestetty - nousevasti tai laskevasti - 
tai järjestämätön. Luvun esiintyminen yhdessä listassa moneen kertaan 
voidaan kieltää tai sallia. Valinnat vaikuttavat eri operaatioiden 
ohjelmoinnin helppouteen ja toisaalta operaatioiden suoritustehokkuu-
teen. Operaatiot toteutetaan funktioina, joiden otsakkeet ovat
seuraavanlaiset:

  
      function Yhdiste(X, Y : joukko) : joukko;
      function Leikkaus(X, Y : joukko) : joukko;
      function Erotus(X, Y : joukko) : joukko;
      function Kuuluu(e: integer; X : joukko) : Boolean;


Operaatiot eivät saa muuttaa parametrien arvoja! Miksei arvoparametri-
välitys suojaa todellisten parametrien arvoja?


12.1 Joukko esitetään järjestämättömänä listana, jossa luku voi
      esiintyä moneen kertaan. Toteuta operaatiot Yhdiste ja Kuuluu.


12.2 Joukko esitetään nousevasti järjestettynä listana, jossa luku voi
     esiintyä vain kerran. Toteuta operaatiot Leikkaus ja Kuuluu.

                                                             
12.3 Pohdi ja selitä piirroksin, millaisia operaatiot ovat eri tieto-
     rakenneratkaisuissa: lista on järjestetty tai järjestämätön, luku 
     voi esiintyä vain kerran tai monta kertaa, Miten asiaan vaikuttaa, 
     jos todelliset parametrit saavat muuttua?        




Standardinmukaisella Pascalilla voisi toteuttaa vaihtelevanmittaisen 
merkkijonon vaikka seuraavasti:


   type string  = ^merkki;
        merkki  = record
                   cha: char;
                   nex: string
                 end;


Esimerkkejä operaatioista:

   function length(s: string):integer;
     var kpl: integer;
   begin
     kpl := 0;
     while s <> nil do
       begin
         kpl := kpl + 1;
         s := s^.nex;
       end:
     length := kpl;
    end;

    procedure empty(var s: string); {s := ''}
      begin
        s:= nil;
      end;

    procedure writestring(s: string);  
      begin
        while s <> nil do
          begin
            write(s^.cha);
            s := s^.nex;
          end;
      end; 


12.4 Toteuta operaatio readstring(var s: string), joka ohittaa
     välilyönnit ja rivinvaihdot ja sitten lukee s:lle arvon 
     välilyöntiin tai rivinvaihtoon asti.
 

12.5 Tee proseduuri catenate(var a: string; b: string), joka 
     suorittaa merkkijono-operaation a := a + b. 


12.6 Suunnittele operaatiot trim(var s: string) ja 
     pos(e, s: string):integer. Piirrä kuvia ja selitä.


12.7 VASTAA KURSSIKYSELYYN WWW-SIVULLA 
     http://www.cs.Helsinki.fi/local/kurssit/kyselyt/syksy_1996/