C - OHJELMOINTI

Dynaamisille tietorakenteille on ominaista seuraavat seikat:
• tietorakenteelle ei tehdä staattista eikä automaattista tilanvarausta joko ennen ohjelman käynnistymistä tai ohjelman suorituksen aikana kuten tavallisille yksinkertaisille muuttujille ja taulukoille
• tietorakenteelle allokoidaan tarvittaessa tilaa vapaasta muistista
• tietorakenne elää; syntyy, kasvaa, supistuu ja kuolee
• tietorakenteen synnyttää ja pitää koossa muistinhallinta
• osoittimet ovat avainasemassa
• pino, lista ja puu ovat dynaamisia tietorakenteita

PINO

Esimerkissä tarkastellaan pinoa, joka toimii LIFO-periaatteella (Last In First Out). Tämä tarkoittaa sitä, että viimeksi pinoon työnnetty olio on ensimmäinen, joka sieltä tulee ulos.
Pinon käsittelyrutiineja kutsutaan push ja pop -operaatioiksi. Pinon käsittelyssä tarvitaan kahta osoitinta; toinen osoittaa pinon alkukohtaa, pohjaa ja toinen pinon huippua. Ohjelmassa käytetään kolmea staattista osoitinta top, bottom ja max_stack. Osoittimista ensimmäinen osoittaa pinon huippua, toinen pinon pohjaa ja kolmas paikkaa, jonka yli pino ei saa kasvaa. Lisäksi ohjelmassa on määritelty kaksi vakiota OUTSTACK ja STACKSIZE. Vakiota OUTSTACK käytetään osoittamaan, että on tapahtunut pinon yli- tai alivuoto, ja STACKSIZE, jolla määritellään pinon maksimikoko.

Funktio push palauttaa arvonaan pinoon pistetyn kokonaisluvun tai arvon OUTSTACK, jos on tapahtunut pinon ylivuoto.

Funktio pop palauttaa arvonaan alkion pinosta tai pinon alivuototilanteessa vakion OUTSTACK.

Pääohjelmassa varataan tila pinolle standardifunktiolla malloc. Paluuosoitin muunnetaan osoittimeksi kokonaislukuun muunnoksella (int*). Pääohjelmassa luetaan kokonaislukuja, jotka pinotaan pinoon ja tulostetaan pinon kokonaisluvut huipulta pohjaan.

Esim.

 
#include <stdio.h>
#include <stdlib.h>
#define OUTSTACK 2147483647
#define STACKSIZE 100

int *top, *bottom, *max_stack;

int push( int item )
{
  if (top < max_stac)
    return *top++ = item;
  else
  {
    printf(”Pinon ylivuoto\n”);
    return OUSTACK;
  }
}

int pop( void )
{
  if (top > bottom)
    return *--top;
  else
  {
    printf(”Pinon alivuoto\n”);
    return OUTSTACK;
  }
}

int main(void)
{
  int luku, ok;

  bottom = top = (int *) malloc(STACKSIZE*sizeof(int));
  max_stack = bottom + STACKSIZE;

  while ( scanf(”%d”,&luku)==1 )
  {
    ok = push(luku);
    if ( ok==OUTSTACK ) break;
  }

  while (top > bottom)
  printf(”%d \n”, pop());

  return 0;
}

 

(kokeiltaessa...varaudu syöttämään 101 lukua ohjelmaan)

LISTAT

Listoja on olemassa monenlaisia, mutta yhteistä niille kaikille on, että ne koostuvat tietueista, joissa on yksi tai useampi osoitin (linkkikenttä) listan muihin alkioihin. Esimerkissä on käytetty yhteen suuntaan ketjutettua listaa. Lista koostuu alkioista, joista kukin on ketjutettu seuraajaansa. Listan viimeisen tietueen linkkikenttä sisältää NULL -osoittimen, joka tarkoittaa listan loppumista. Listan tallettamiseen tarvitaan osoitin, joka osoittaa listan alkuun. Lisäksi tarvitaan yksi tai useampi osoitin, joiden avulla suoritetaan listaan kohdistuvia operaatioita, kuten listan läpikäynti, lisäys tai poisto.

Esimerkkiohjelmassa käytetään tietuetta:

 
struct lista_alkio
{
  int arvo;
  struct lista_alkio *seuraava;
};

 

Tietue koostuu kahdesta kentästä: arvo ja seuraava. Arvo-kenttä sisältää tietueen varsinaisen tiedon ja seuraava on osoitin seuraavaan listan alkioon.

Esimerkkiohjelma lukee päätteeltä kokonaislukuja, järjestää ne yhteen suuntaan ketjutettuun listaan suuruusjärjestykseen ja lopuksi tulostaa tämän listan kaikki alkiot.Ohjelmassa on lisäksi kaksi funktiota ja yksi makro:
• tulosta_lista() -funktio tulostaa listan alusta loppuun
• vie_listaan() -funktio vie uuden kokonaisluvun paikalleen listassa
• makro a_alloc perustuu malloc() -funktion kutsuun ja tuloksen tyypin muunnokseen

Esim

 
#include <stdio.h>
#include <stdlib.h>
#define a_alloc                        \
      (struct lista_alkio *)           \
   malloc(sizeof(struct lista_alkio))

struct lista_alkio
{
  int arvo;
  struct lista_alkio *seuraava;
};

void tulosta_lista( struct lista_alkio *p )
{
  while ( p != NULL )
  {
    printf( ”%d\n”, p->arvo );
    p = p->seuraava;
  }
}

void vie_listaan(struct lista_alkio **p, int n)
{
  struct lista_alkio *t = *p;

  if (*p == NULL || n < (*p)->arvo)
  {
    *p = a_alloc;
    (*p)->arvo = n;
    (*p)->seuraava = t;
  }
  else
  {
    struct lista_alkio *edellinen;

    do
    {
      if (t -> arvo == n)
        return;
      edellinen = t;
      t = t -> seuraava;
    } while(t != NULL && t -> arvo < n);

    if ((t == NULL) || (t->arvo != n))
    {
      edellinen ->seuraava = a_alloc;
      edellinen->seuraava->arvo = n;
      edellinen->seuraava->seuraava = t;
    }
  }
}

int main(void)
{
  struct lista_alkio *ap;
  int uusi;
  ap = NULL;
  while (scanf(”%d”, &uusi) == 1)
    vie_listaan(&ap, uusi);
  tulosta_lista(ap);

  return 0;
}

 

Pääohjelman muuttuja ap on osoitin listan alkuun, jolle annetaan alkuarvoksi nollaosoitin. Funktio vie_listaan saa ensimmäisenä argumenttina ap:n osoitteen ja toisena argumenttina syöttötietona olleen luvun. Funktio toimii seuraavasti:
• jos lista on tyhjä tai luku on pienempi kuin listan ensimmäisen alkion sisältämä, niin funktio luo uuden lista-alkion ja sijoittaa luvun siihen sekä asettaa argumenttinsa osoittaman osoittimen osoittamaan uuteen alkioon.
• muussa tapauksessa funktio hakee listasta sopivan paikan uudelle alkiolle eli määrittää työmuuttujille edellinen ja t arvot siten, että ne osoittavat peräkkäisiä alkioita, joiden väliin uusi alkio tulee lisätä; paikan määritettyään funktio luo uuden alkion ja sijoittaa sen listaan asettamalla seuraava-kentät sopivasti.

PUU

Puu on tietorakenne, jossa kukin alkio sisältää osoittimet kahteen muuhun alkioon siten, että osoitinketjut eivät muodosta renkaita. Puussa on aina täsmälleen yksi alkio, johon ei ole osoitinta mistään alkiosta. Tätä kutsutaan puun juureksi. Puun kukin alkio (solmu) voidaan tulkita puun yhden alipuun juureksi. Puun lehti-solmuksi kutsutaan solmua, jonka molemmat osoittimen 'jälkeläisiin* ovat NULL -arvoisia.

Seuraavassa esimerkki puurakenteen määrittelystä C-kielessä:

 
struct solmu 
{
  datatyyppi data;
  struct solmu *vasen, *oikea;
}
 

Datatyyppi on puun solmuihin talletettavan varsinaisen tiedon tyyppi, yleensä jokin tietue- tai yhdistetyyppi. Osoittimet vasen ja oikea voidaan tulkita osoittimiksi solmua vastaavan alipuun vasempaan ja oikeaan alipuuhun.

Esimerkkinä puun läpikäynnistä on ohjelma, joka lukee lausekkeen ja tallentaa sen sisäiseen tietorakenteeseen. Tämän jälkeen ohjelma laskee lausekkeen arvon annetuilla muuttujan arvoilla.

Esim.

 
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

typedef long luku;
typedef enum {vakio,muuttuja,unaarinen,binaarinen} laji;
typedef struct 
        { char operaattori;
          struct solmu *vasen_operandi, *oikea_operandi;
        } bin_lauseke;

typedef union 
        { luku vakioarvo;
          struct solmu *operandi;
          bin_lauseke bin;
        } data;

typedef struct solmu 
        { laji luokka;
          data solmundata;
        } *lauseke;

#define allokoi() (lauseke)malloc(sizeof(struct solmu))

extern lauseke lue_lauseke(void);
int merkki = 0;

#define lue_merkki() do merkki=getchar(); 
                                 while(isspace(merkki))

lauseke lue_tekija(void)
{ lauseke e;
  switch(merkki)
  { case ‘x’: e = allokoi();
              e->luokka = muuttuja;
              lue_merkki();
              return e;
    case ‘(‘: lue_merkki();
              e = lue_lauseke();
              if (merkki == ‘)’)
              { lue_merkki();
                return e;
              } else return NULL;
    default:  if (isdigit(merkki))
              { int n = 0;
                do
                { n = 10 * n + merkki - ‘0’;
                  lue_merkki();
                } while ( isdigit (merkki) );

                e = allokoi(9);
                e->luokka = vakio;
                e->solmundata.vakioarvo = n;
                return e;
              } else return NULL;
} }
lauseke luo_binaarinen(char op,lauseke vasen,
                                       lauseke oikea)
{ 
  lauseke uusi = allokoi();
  uusi -> luokka = binaarinen;
  uusi->solmundata.bin.operaattori = op;
  uusi->solmundata.bin.vasen_operandi = vasen;
  if ( (uusi->solmundata.bin.oikea_operandi = oikea)
                                            == NULL )
    return NULL;
  else
	return uusi;
}

lauseke lue_termi(void)
{
  char op;
  lauseke e = lue_tekija();
  while (merkki == ‘*’ || merkki == ‘/’)
    if (e == NULL)
      return NULL;
    else
    { op = merkki;
      lue_merkki();
      e = luo_binaarinen(op, e, lue_tekija());
    }
  return e;
}

lauseke lue_lauseke(void)
{
  char op;
  int miinus = 0;
  lauseke e;

  if (merkki == ‘-’)
  { miinus = 1;
    lue_merkki();
  }

  e = lue_termi();
  if (miinus && e != NULL)
  { lauseke uusi = allokoi();
    uusi ->luokka = unaarinen;
    uusi ->solmundata.operandi = e;
    e = uusi;
  }

  while (merkki == ‘+’ || merkki == ‘-’)
    if (e == NULL)
      return NULL;
    else
    { op = merkki;
      lue_merkki();
      e = luo_binaarinen(op, e, lue_termi());
    }
    return e;
}

luku arvo(lauseke e, luku arg)
{
  switch(e->luokka)
  { 
    case muuttuja:  return arg;
    case vakio:     return e->solmundata.vakioarvo;
    case unaarinen: return -arvo(e->solmundata.operandi,
                                                	arg);
    case binaarinen:
    {
       luku op1 = arvo(e->solmundata.bin.vasen_operandi,
                                                    arg);
       luku op2 = arvo(e->solmundata.bin.oikea_operandi,
                                                    arg);
       switch(e->solmundata.bin.operaattori)
       { 
         case ‘+’: return op1 + op2;
         case ‘-’ : return op1 - op2;
         case ‘*’ : return op1 * op2;
         case ‘/’ : return op1 / op2;
       }
    }
} }

int main(void)
{
  luku arg;
  lauseke e;
  lue_merkki();
  e = lue_lauseke();
  if (e == NULL)
  {
    printf(”Virhe lausekkeessa.\n”);
    return 1;
  }
  while (scanf(”%ld”, &arg)== 1)
    printf(”Lausekkeen arvo argumentin arvolla %ld on
                           %ld.\n”, arg, arvo(e, arg));

  return 0;
}