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