# Tietorakenteet ja algoritmit FAQ

#### K: Kuinka otan kirjaston käyttöön omassa ohjelmassani? (ANSI C)

V: Käyttöönotto tapahtuu kahdessa vaiheessa:
1. Kirjaston funktioiden kuvaukset pitää ilmoittaa esikääntäjälle #include - lauseella, ohjelman alussa. Lauseen tulee olla:
#include TRA/TRA.h>
2. Kääntäjälle pitää ilmoittaa että kirjasto TRA.a otetaan käyttöön. Komentoriviltä tapahtuva kääntäminen tapahtuu siis:
%gcc -oRun -lTRA.a Foo.c
mikä tuottaa c-kooditiedostosta Foo.c ajokelpoisen ohjelman nimeltä Run, ja liittää kirjaston TRA.a mukaan käännökseen.
2 (cs:llä): Käännetään komennolla trac ohjelma.c tai trac -o ohjelma ohjelma.c

#### K: Kuinka otan kirjaston käyttöön omassa ohjelmassani? (GNU-Pascal)

V: Käyttöönotto tapahtuu kahdessa vaiheessa:
1. Kirjaston funktioiden kuvaukset pitää ilmoittaa esikääntäjälle import - lauseella, ohjelman alussa. Lauseen tulee olla:
import TRA;
2. Komentoriviltä tapahtuva kääntäminen tapahtuu siis:
gpc Foo.p ohjelma
mikä tuottaa p-kooditiedostosta Foo.p ajokelpoisen ohjelman nimeltä ohjelma, ja liittää kirjaston TRA mukaan käännökseen.

#### K: Miksi joistain funktioista on useita eri versioita?

V: Joistakin funktioista on kaikille perustyypeille oma versionsa. Yleensä sen takia, että kääntäjän pitää tietää minkä tyyppiset syötteet funktio saa. Esimerkiksi QUEUE_ENQUEUE(Q,x):lle ei voida antaa syötteenä x:n paikalla liukulukua:
QUEUE_ENQUEUE(Q, 5.7);
koska QUEUE_ENQUEUE saa parametrinaan tyyppiä ELEMENT olevan muuttujan. Niinpä meidän pitää käyttää versiota joka saa parametrinaan liukuluvun :
FLOAT_QUEUE_ENQUEUE(Q, 5.7);
Tämän koodin kääntäjä hyväksyy. Käytön helpottamiseksi suurimmasta osasta funktioita on sekä tyyppiversiot että yleiset versiot.

#### K: Kuinka luon uuden pinon/listan/jonon/...?

V: Koodilohkon alussa pitää käytettävä tietorakenne esitellä kuin mikä tahansa muuttuja, ja ennen käyttöä tietorakenne pitää alustaa. Esimerkiksi uusi pino jonka nimeksi halutaan OmaPino ja joka sisältää kokonaislukuja otetaan käyttöön seuraavasti:

C | Pascal
{ STACK OmaPino; /* Esitellään OmaPino */ /* Alustetaan OmaPino kokonaislukupinoksi */ INT_STACK_CREATE(OmaPino); /* Käytetään tietorakennetta ... */ STACK_FREE(OmaPino); } | var OmaPino:STACK ; (* Esitellään OmaPino *) begin (* Alustetaan OmaPino kokonaislukupinoksi *) INT_STACK_CREATE(OmaPino); (* Käytetään tietorakennetta ... *) STACK_FREE(OmaPino);

#### K: Olen tehnyt aliohjelman joka saa parametrinaan pinon joka voi sisältää mitä tahansa perustyyppiä. Kuinka luon aputietorakenteita jotka ovat samaa tyyppiä kuin parametrina saamani pino?

V: Käytät tietorakenteen tyypin palauttavaa funktiota STACK_TYPE(S). Jokaisen tietorakenteen tyypin saa selville XXX_TYPE(X) - funktiolla. STACK_TYPE(S) palauttaa tyyppiä DESCRIPTOR olevan muuttujan, joka voidaan uutta tietorakennetta alustettaessa antaa parametrina XXX_CREATE(X,D):lle.

Esimerkki 1: Luodaan parametrina S saadun pinon tyyppiä oleva jono:

C | Pascal
void MyFunction (STACK S) { QUEUE Q; QUEUE_CREATE(Q, STACK_TYPE(S)); /* Q on nyt samaa tyyppiä kuin S. */ } | procedure MyFunction (S:STACK); var Q:QUEUE; begin QUEUE_CREATE(Q, STACK_TYPE(S)); (* Q on nyt samaa tyyppiä kuin S. *) end;

Esimerkki 2: Otetaan talteen tieto listan tyypistä ja käytetään sitä kahdessa paikassa:

C | Pascal
void MyFunction (LIST L) { QUEUE Q1, Q2; DESCRIPTOR D; D=LIST_TYPE(L); QUEUE_CREATE(Q1, D); /* Q1 on nyt samaa tyyppiä kuin L. */ /* ... */ QUEUE_CREATE(Q2, D); /* Q2 on myös samaa tyyppiä kuin L. */ /* ... */ } | procedure MyFunction (L:LIST); var Q1,Q2:QUEUE; D:DESCRIPTOR; begin D:=LIST_TYPE(L); QUEUE_CREATE(Q1, D); (* Q1 on nyt samaa tyyppiä kuin L. *) (* ... *) QUEUE_CREATE(Q2, D); (* Q2 on myös samaa tyyppiä kuin L. *) (* ... *) end;

#### K: Kuinka toteutan pinon joka sisältää listoja?

V: Jos halutaan tallettaa tietorakenteeseen muita (tai samantyyppisiä) tietorakenteita, käytetään osoitintyyppistä rakennetta, luodaan siis VOIDPTR-tyyppinen rakenne:
STACK S;
VOIDPTR_STACK_CREATE(S);
Tähän pinoon voidaan nyt viedä esimerkiksi listoja, mutta on huomioitava, että koko tietorakenteen sisältöä ei kopioida, vaan ainoastaan tieto rakenteen sijainnista muistiavaruudessa. Esimerkkilistaus:

C | Pascal
void main() { STACK S; LIST L[5]; int i; for(i=1;i<5;i++) IL_CREATE(L[i]); VOIDPTR_STACK_CREATE(S); LIST_CONSTRUCT_RANDOM(L[1], 3, 1, 10); LIST_CONSTRUCT_RANDOM(L[4], 1, 1, 10); for(i=4;i>0;i--) PS_PUSH(S, L[i]); while (!STACK_EMPTY(S)) { printf("L:"); LIST_PRINT(PS_TOP(S)); PS_POP(S); printf("\n"); } | program LIST_IN_STACK; var S:STACK; L1,L2,L3,L4,L5:LIST; i:integer; begin INT_LIST_CREATE(L1); INT_LIST_CREATE(L2); INT_LIST_CREATE(L3); INT_LIST_CREATE(L4); VOIDPTR_STACK_CREATE(S); LIST_CONSTRUCT_RANDOM(L1, 3, 1, 10); LIST_CONSTRUCT_RANDOM(L4, 1, 1, 10); VOIDPTR_STACK_PUSH(S, L1); VOIDPTR_STACK_PUSH(S, L2); VOIDPTR_STACK_PUSH(S, L3); VOIDPTR_STACK_PUSH(S, L4); while (not STACK_EMPTY(S)) do begin writeln('L:'); LIST_PRINT(PS_TOP(S)); VOIDPTR_STACK_POP(S); writeln; end;

Edellinen ohjelma luo aluksi seuraavanlaiset listat:

LIST_CONSTRUCT_RANDOM:ien jälkeen viedään listat 1-4 pinoon (PS_PUSH() on lyhenne VOIDPTR_STACK_PUSH():sta). Lyhenneluettelo täältä.
Pinossa on siis neljä listaa joista kaksi on tyhjiä:

Lopuksi tulostetaan pinosta listoja ja poistetaan niitä niin kauan että pino on tyhjä. Listat ovat kuitenkin tallessa vielä listoina, L[1..5].

Söulissa, 4.9.1999 Matti Meriläinen

© 1999 Tapani Katainen - Tietojenkäsittelytieteen laitos, Joensuun Yliopisto