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:

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].