# Tietorakenteet ja algoritmit FAQ (ANSI C)

Kirjaston peruskäyttöön liittyviä kysymyksiä, C-versio. Pascal-versio täältä.

#### K: Kuinka otan kirjaston käyttöön omassa ohjelmassani?

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ä9. Käännetään komennolla trac ohjelma.c tai trac -o ohjelma ohjelma.c

#### 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:
`{
STACK OmaPino; /* Esitellään OmaPino */
INT_STACK_CREATE(OmaPino); /* Alustetaan OmaPino kokonaislukupinoksi */
/* 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:

`void MyFunction (STACK S) {
QUEUE Q;
QUEUE_CREATE(Q, STACK_TYPE(S));
/* Q on nyt samaa tyyppiä kuin S. */
}`

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

`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. */
/* ... */
}`

#### 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:

    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");
    	}
    }

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