Tietorakennekirjaston operaatioiden avulla voidaan käsitellä neljää erilaista tyypitettyä tyyppiä. Nämä tyypit ovat kokonaislukutyyppi, joka sisältää int / integer - arvoja, liukulukutyyppi (sisältää float / real - tyyppistä tietoa), merkkijonotyyppi (char* / string[ ] -tyyppistä tietoa) ja osoitintyyppi (void* / pointer - tyyppistä tietoa). Tämä voi kuulostaa monimutkaiselta, mutta yksinkertaisesti lisäämällä kulloinkin käytetyn operaation eteen halutun tyypin "tunnuksen" saadaan operaatio käsittelemään kyseisen tyyppisiä arvoja.
Esimerkki 1: Halutaan luoda ja käyttää listaa, joka sisältää osoittimia. Lista luodaan komennolla VOIDPTR_LIST_CREATE(L); (L = luotava lista) Listaan lisätään komennolla VOIDPTR_LIST_INSERT(L, p, x); (L = Luotava lista, p = kohta johon lisätään ja x = lisättävä osoitin) jne... Esimerkki 2: Vastaavasti jos halutaan tallettaa listaan kokonaislukuja luodaan lista komennolla INT_LIST_CREATE(L); jne... Eli ensimmäinen "liiteosa" vain muuttuu. Tietorakenne kirjasto liitetään ohjelmaan lisäämällä ohjelman alkuun; import tra. Esim. program har8_t1; import tra; type ...Käännettäessä ohjelmaa käytetään käskyä "trap" (ei siis esim. gpc) että saadaan tietorakennekirjasto mukaan käännökseen.
Esim. trap harj8_t1.p
Onnistunut käännös tekee siihen hakemistoon jossa käsky suoritetaan a.out nimisen tiedoston, joka on suorituskelpoinen ohjelma eli kirjoittamalla a.out ja painamalla enter saadaan ohjelma ajettua. Mikäli taas kääntäjä huomaa virheitä ne tulostuvat heti komennon perään. Ja niistä ohjelmoija voi katsoa missä päin koodia virheitä sijaitsee.
Lista on dynaaminen rakenne,joka koostuu alkioista, jotka ovat järjestetty peräkkäin siten, että jokaisella alkiolla, paitsi viimeisellä, on yksikäsitteinen seuraaja ja jokaisella alkiolla, paitsi ensimmäisellä on yksikäsitteinen edeltäjä.
Lista on tyhjä, kun se ei sisällä yhtään alkiota. Epätyhjä lista puolestaan sisältää mielivaltaisen määrän alkioita. Listan pituus on listan sisältämien alkioiden lukumäärä. Listan pituus voi listan elinkaaren aikana vaihdella huomattavasti, koska listaan voidaan lisätä ja siitä voidaan poistaa alkioita kulloisenkin käyttötarpeen edellyttämällä tavalla.
Yleisen listan funktioita tarvitaan silloin, kun pitää käsitellä listaa, jonka tyyppiä ei vielä ohjelmaa kirjoitettaessa tiedetä. Yleistä listaa luotaessa määritellään listan tyyppi kuvaajan DESCRIPTOR avulla. Funktio LIST_TYPE(L) palauttaa listan L kuvaajan jota voidaan käyttää listaa luotaessa. Kuvaaja sisältää kaiken tiedon siitä miten listan alkioita vertaillaan, käsitellään ja tulostetaan.
Int / integer - listan käsittely
Kokonaislukulistan esittelyissä käytetään kokonaislukutyyppinä
tyypinmäärittelyä INT_TYPE, joka on määritelty toteutuskohtaisesti. Tämä
siksi, että esimerkiksi joissakin MS/DOS-ympäristössä toimivissa
kääntäjissä int on 16-bittinen luku (enintään 2^16), mutta esim. cs:n
gpc:ssä 32-bittinen (enintään 2^32). Kaikki INT_LIST_XXX - aliohjelmat
voidaan lyhentää IL_XXX; INT_LIST_CREATE(L) voidaan siis kutsua myös
IL_CREATE(L).
Float / real - listan käsittely
Liukulukulistan esittelyissä käytetään liukulukutyyppiä FLOAT_TYPE,
samoista syistä kuin kokonaislukulistan kohdalla. FLOAT_LIST_XXX voidaan
lyhentää koodissa FL_XXX. Char* / string[ ] - listan käsittely
Merkkijonolistan tyyppinä on C:ssä char*, osoitin merkkijonoon. Pascalissa tyyppinä on string, jonka maksimipituus on vakio RANDOM_STR_MAX, cs:llä 16 merkkiä. Kaikki CHARP_LIST_XXX - aliohjelmat voidaan lyhentää koodissa CL_XXX.
LIST_CREATE (L, D)
Yleinen LIST_CREATE(L, D) muodostaa tyhjän listan L, ja asettaa listan
kuvaajaksi kuvaajan D = {INT_DESC| FLOAT_DESC| CHARP_DESC| VOIDP_DESC}.
Mikäli lista L ei ole tyhjä lista, kaikki listassa ollut tieto menetetään,
ja se jää varamaan muistia turhaan. Tyypitetyt operaatiot muodostavat omaa
tyyppiään olevan listan L
LIST_INSERT (L, p, x)
Lisää alkion x listaan L asemaan p. Aiemmin asemassa p ollut alkio siirtyy
seuraavaan asemaan. Jos p=LIST_EOL(L), lisätään alkio x listan loppuun,
p=LIST_FIRST(L) lisää alkion listan ensimmäiseksi. Jos asemaa p ei ole
listassa, vaikutus on määrittelemätön. Tyypitetyt operaatiot vievät
listaan omaa tyyppiään olevan alkion. Aikavaativuus : O(1)
LIST_RETRIEVE (L, p)
Palauttaa listan L asemassa p olevan arvon. Yleinen lista palauttaa
ELEMENT-tyypin, tyypitettyjen listojen funktiota palauttavat listan omaa
tyyppiä olevan arvon. Jos p=LIST_EOL(L) tai asemaa p ei ole listassa,
tulos on määrittelemätön. Aikavaativuus : O(1)
LIST_LOCATE (L, x)
Palauttaa alkion x aseman listassa L. Jos x esiintyy listassa monta
kertaa, funktio palauttaa sen x:n esiintymän aseman, jonka etäisyys listan
alusta on lyhin. Jos x ei sisälly listaan L, palauttaa aseman LIST_EOL(L).
Yleinen lista saa parametrina x elementtityyppiä olevan alkion, tyypitetyt
listat omaa tyyppiään. Aikavaativuus : O(1)
LIST_DELETE (L, p)
Poistaa listasta L asemassa p olevan alkion. Alkion poistamisen jälkeen
listassa asemaa p ja sitä seuraavien asemien tiedot vanhentuvat. Jos
p=LIST_EOL(L) tai asemaa p ei listassa L ole ollenkaan, on vaikutus
määrittelemätön. Aikavaativuus : O(1)
LIST_NEXT (L, p)
Palauttaa asemaa p seuraavan aseman listassa L. Jos p on listan viimeisen
alkion asema, palauttaa LIST_NEXT(L, p) aseman LIST_EOL(L). Jos taas
p=LIST_EOL(L), on NEXT(L, p) määrittelemätön. Jos listassa ei ole asemaa
p, on operaation tulos määrittelemätön. Kaikki tyypitetyt funktiot
toimivat samalla tavalla (INT_LIST_NEXT(L ,p), CHARP_LIST_NEXT(L, p),
jne...). Näiden käytössä ei ole siis eroa eri listoilla, joten
Int-tyyppisessä listassa L voidaan hyvin soveltaa esim. p=LIST_NEXT(L, p).
Aikavaativuus : O(1)
LIST_PREVIOUS (L, p)
Palauttaa asemaa p edellisen aseman listassa L. Mikäli L ei ole tyhjä
lista, palauttaa LIST_PREVIOUS(L, LIST_EOL(L, p) ) listan viimeisen alkion
aseman. Jos p on listan ensimmäisen alkion asema, on PREVIOUS(L, p)
määrittelemätön. Jos listassa ei ole asemaa p, on operaation tulos
määrittelemätön. Kaikki tyypitetyt funktiot toimivat samalla tavalla
(INT_LIST_PREVIOUS(L ,p), CHARP_LIST_PREVIOUS(L, p), jne...). Näiden
käytössä ei ole siis eroa eri listoilla, joten Int-tyyppisessä listassa L
voidaan hyvin soveltaa esim. p=LIST_PREVIOUS(L, p). Aikavaativuus : O(1)
LIST_FIRST (L)
Jos L on tyhjä lista, funktio palauttaa LIST_EOL(L), muutoin LIST_FIRST(L)
palauttaa listan ensimmäisen alkion aseman. Kaikki tyypitetyt funktiot
toimivat samalla tavalla, joten näiden käytössä ei ole eroa sillä
käyttääkö INT_LIST_FIRST(L) vai LIST_FIRST(L)
LIST_LAST (L)
Jos L on tyhjä lista, funktio palauttaa LIST_EOL(L), muutoin LIST_LAST(L)
palauttaa listan viimeisen alkion aseman. Kaikki tyypitetyt funktiot
toimivat samalla tavalla, joten näiden käytössä ei ole eroa sillä
käyttääkö INT_LIST_LAST(L) vai LIST_LAST(L). Aikavaativuus : O(1)
LIST_EOL (L)
Palauttaa listan L EOL-aseman. Tyypitettyjen funktioiden toiminnassa ei
ole eroa LIST_EOL(L):n kanssa. Aikavaativuus : O(1)
LIST_PRINT (L)
Tulostaa listan L kuvaajassa määritellyllä tavalla. Tyypitetyillä
funktioilla ei ole eroa LIST_PRINT(L):n toiminnan kanssa. Aikavaativuus :
O(1)
LIST_FREE (L)
Vapauttaa kaiken listan L varaaman tilan ja asettaa listan L
määrittelemättömäksi listaksi. Aikavaativuus : O(n)
Seuraavat aliohjelmat eivät ole välttämättömiä listan käytössä:
LIST_CONSTRUCT_RANDOM (L, count, min, max);
void LIST_CONSTRUCT_RANDOM (LIST L, int count, INT_TYPE min, INT_TYPE max);
procedure LIST_CONSTRUCT_RANDOM (L:LIST; count:integer;min,max:INT_TYPE);
Muodostaa listan L, jossa on count-määrä alkioita. Lista täytyy olla alustettu jonkin tyyppiseksi listaksi (XXX_LIST_CREATE(L)). Mikäli lista on kokonaislukulista, min on listan alkioiden minimiarvo ja max maksimi, liukulukulistalla samoin. Merkkijonolistalla LIST_CONSTRUCT_RANDOM (L, count, min, max) vie listaan count kappaletta merkkijonoja, jotka sisältävät min..max merkkiä. C:ssä merkkijonon pituus LIST_CONSTRUCT_RANDOM (L, count, min, max) vie listaan count kappaletta merkkijonoja, jotka sisältävät min..max merkkiä. C:ssä merkkijonon pituus on kuitenkin vähintään 1 ('\0'-merkki), Pascalissa pituus voi olla 0 merkkiä. Merkkijonot koostuvat pelkästään pienistä kirjaimista väliltä 'a'..'z'. Merkkijonon maksimipituus on rajoitettu vakion RANDOM_STR_MAX suuruiseksi, ainakin cs:n toteutuksessa 16 merkkiä. LIST_CONSTRUCT_RANDOM (L, 10, 2, 4) arpoo siis kokonaislukulistalle 10 kappaletta kokonaislukuja, jotka saavat arvoja 2..4, liukulukulistalle 10 kpl. liukulukuja välillä 2.00 - 4.00, merkkijonolistalle 10 merkkijonoa välillä 'aa'..'zzzz'. Aikavaativuus : O(count)
LIST_TYPE (L) DESCRIPTOR LIST_TYPE (LIST L);
function LIST_TYPE (L:LIST) :
DESCRIPTOR;
Palauttaa listan L kuvaajan. Käytetään lähinnä tilanteessa, jossa ei ohjelmaa kirjoitettaessa vielä tiedetä minkätyyppinen lista joudutaan luomaan. Uusi lista M, joka on samaa tyyppiä kuin lista L, luodaan komennolla LIST_CREATE(M, LIST_TYPE(L));. Aikavaativuus : O(1)
LIST_LESS (L, x, y)
LIST_SAME (L, x, y)
Palauttavat tiedon siitä ovatko listan L määräämää tyyppiä olevat
elementit x ja y samoja (SAME), tai onko x järjestyksessä ennen y:tä
(LESS). Elementtien x ja y pitää olla samaa tyyppiä kuin listan L alkiot
(muttei niiden ole pakko olla listan L alkioita). Jos x=y, niin LIST_SAME
palauttaa siis TRUE (!=0), ja jos xLESS palauttaa TRUE (!=0).
Merkkijonolistassa vertaillaan merkkijonojen välistä aakkosjärjestystä
Aikavaativuus : yksinkertaisille tyypeille O(1)
LIST_EMPTY (L)
Palauttaa tiedon siitä onko lista L tyhjä lista, Funktio
palauttaa TRUE jos lista on tyhjä ja FALSE, jos lista ei ole tyhjä
Aikavaativuus : O(1)
Jono on lista, jolle on määritelty vain operaatiot alkion lisäämiseksi ja poistamiseksi jonosta sekä jonon tyhjyyden testaus.
Käyttö/käsittely: Jono voi olla tyhjä tai sisältää mielivaltaisen määrän alkioita. Alkion lisäys tapahtuu aina listan toiseenpäähän ja poisto toisesta päästä. Alkiot poistetaan siis samassa järjestyksessä, jossa ne on lisätty. Jonorakenne noudattaa ns.FIFO-periaattetta (First In First Out).
Yleisen jonon funktioita tarvitaan silloin, kun pitää käsitellä jonoa, jonka tyyppiä ei vielä ohjelmaa kirjoitettaessa tiedetä. Yleistä jonoa luotaessa määritellään jonon tyyppi kuvaajan DESCRIPTOR avulla. Funktio QUEUE_TYPE(Q) palauttaa jonon Q kuvaajan jota voidaan käyttää jonoa luotaessa. Kuvaaja sisältää kaiken tiedon siitä miten jonon alkioita vertaillaan, käsitellään ja tulostetaan. Kuvaajasta ja yleisen jonon alkioiden tyypistä ELEMENT enemmän luvussa "Tietorakenteiden kuvaukset".
Int / integer - jonon käsittely
Kokonaislukujonon esittelyissä käytetään kokonaislukutyyppinä
tyypinmäärittelyä INT_TYPE, joka on määritelty toteutuskohtaisesti. Tämä
siksi, että esimerkiksi joissakin MS/DOS-ympäristössä toimivissa
kääntäjissä int on 16-bittinen luku (enintään 2^16), mutta esim. cs:n
gpc:ssä 32-bittinen (enintään 2^32). Kaikki INT_QUEUE_XXX - aliohjelmat
voidaan lyhentää IQ_XXX; INT_QUEUE_CREATE(Q) voidaan siis kutsua myös
IQ_CREATE(Q).
Float / real - jonon käsittely
Liukulukujonon esittelyissä käytetään liukulukutyyppiä FLOAT_TYPE,
samoista syistä kuin kokonaislukujonon kohdalla. FLOAT_QUEUE_XXX voidaan
lyhentää koodissa FQ_XXX.
Char* / string[ ] - jonon käsittely
Merkkijonojonontyyppinä on string, jonka maksimipituus on vakio
RANDOM_STR_MAX,$
merkkiä. Kaikki CHARP_QUEUE_XXX - aliohjelmat voidaan lyhentää koodissa
CQ_XXX.
Jonoa voidaan käsitellä yleisen jonon operaatioiden avulla tietämättä jonon oikeaa tyyppiä, aivan kuten esimerkiksi listan tapauksessa. Tietorakennekirjastoon on toteutettu neljä erilaista tyypitettyä jonotyyppiä : kokonaislukujono, joka sisältää int / integer - arvoja, liukulukujono (sisältää float / real - tyyppistä tietoa), merkkijonojono (char* / string[ ]) ja osoitinjono (void* / pointer - tyyppistä tietoa).
Tässä osassa on esitelty yleisen-, kokonaisluku-, liukuluku- ja merkkijonojonon funktiot. Kaikkien funktioiden käytössä oletetaan että jono on määritelty. Mikäli parametrina annettava jono Q on määrittelemätön, on aliohjelmien toiminta määrittelemätöntä, lukuunottamatta tietenkin QUEUE_CREATE:a joka määrittelee jonon.
Jono on tietorakenteena kuin lista jonka lisäysoperaatiot kohdistuvat aina listan loppuun ja poisto- sekä retrieve-operaatiot listan alkuun.
QUEUE_CREATE (Q, D)
Yleinen QUEUE_CREATE(Q, D) muodostaa tyhjän jonon Q, ja asettaa jonon
kuvaajaksi kuvaajan D = {INT_DESC| FLOAT_DESC| CHARP_DESC| VOIDP_DESC}.
Mikäli jono Q ei ole tyhjä jono, kaikki jonossa ollut tieto menetetään, ja
se jää varamaan muistia turhaan. Tyypitetyt operaatiot muodostavat omaa
tyyppiään olevan jonon Q. Aikavaativuus : O(1)
QUEUE_ENQUEUE (Q, x)
Lisää alkion x jonon Q loppuun. Tyypitetyt operaatiot vievät jonoon omaa
tyyppiään olevan alkion. Aikavaativuus : O(1)
QUEUE_ FRONT (Q)
Palauttaa jonon Q ensimmäisen alkion arvon. Yleinen jono palauttaa
ELEMENT-tyypin, tyypitettyjen listojen funktiota palauttavat jonon omaa
tyyppiä olevan arvon. Aikavaativuus : O(1)
QUEUE_DEQUEUE (Q)
Poistaa jonon Q ensimmäisen alkion. Aikavaativuus : O(1)
QUEUE_PRINT (Q)
Tulostaa jonon Q kuvaajassa määritellyllä tavalla. Aikavaativuus : O(n)
QUEUE_FREE (Q)
Vapauttaa kaiken jonon Q varaaman tilan ja asettaa jonon Q
määrittelemättömäksi jonoksi. On hyvä ohjelmointitapa vapauttaa ohjelman
lopussa ohjelman varaama tila.Jos void*- tai char*-jonossa on talletettuna
tietoa jolle on varattu muistia eikä siihen enää päästä käsiksi jonon
tuhoamisen jälkeen, täytyy ennen QUEUE_FREE:n kutsumista huolehtia varatun
muistitilan vapauttamisesta. Aikavaativuus : O(n)
Seuraavat aliohjelmat eivät ole välttämättömiä jonon käytön kannalta, mutta helpottavat ohjelmien tekemistä ja testaamista:
QUEUE_CONSTRUCT_RANDOM (Q, count, min, max)
Muodostaa jonon Q, jossa on count-määrä alkioita. Jono täytyy olla
alustettu jonkin tyyppiseksi jonoksi (XXX_QUEUE_CREATE(Q)). Mikäli jono on
kokonaislukujono, min on jonon alkioiden minimiarvo ja max maksimi,
liukulukujonolla samoin. Merkkijonojonolla QUEUE_CONSTRUCT_RANDOM (Q,
count, min, max) vie jonoon count kappaletta merkkijonoja, jotka kukin
sisältävät min..max merkkiä. Pituus voi olla 0 merkkiä. Merkkijonot
koostuvat
pelkästään pienistä kirjaimista väliltä 'a'..'z'. Merkkijonon
maksimipituus on rajoitettu vakion RANDOM_STR_MAX suuruiseksi,
ainakin cs:n toteutuksessa 16 merkkiä. QUEUE_CONSTRUCT_RANDOM (Q, 10, 2,
4) arpoo siis kokonaislukujonolle 10 kappaletta kokonaislukuja, jotka
saavat arvoja 2..4, liukulukujonolle 10 kpl. liukulukuja välillä 2.00 -
4.00, merkkijonojonolle 10 merkkijonoa välillä 'aa'..'zzzz'.Aikavaativuus
: O(count)
QUEUE_TYPE (Q)
Palauttaa jonon Q kuvaajan. Käytetään lähinnä tilanteessa, jossa ei
ohjelmoitaessa tiedetä minkätyyppinen jono joudutaan luomaan. Uusi jono M,
joka on samaa tyyppiä kuin jono Q, luodaan komennolla QUEUE_CREATE(M,
QUEUE_TYPE(Q));. Aikavaativuus : O(1)
QUEUE_LESS (Q, x, y)
QUEUE_SAME (Q, x, y)
Palauttavat tiedon siitä ovatko jonon Q määräämää tyyppiä olevat elementit
x ja y samoja (SAME), tai onko x järjestyksessä ennen y:tä (LESS).
Elementtien x ja y pitää olla samaa tyyppiä kuin jonon Q alkiot (muttei
niiden ole pakko olla jonon Q alkioita). Jos x=y, niin QUEUE_SAME
palauttaa siis TRUE (!=0), ja jos x<y niin QUEUE_LESS palauttaa TRUE
(!=0). Merkkijonojonossa vertaillaan merkkijonojen välistä
aakkosjärjestystä. Aikavaativuus : yksinkertaisille tyypeille O(1)
QUEUE_EMPTY (Q)
Palauttaa tiedon siitä onko jono Q tyhjä jono. Funktio palauttaa TRUE jos
jono on tyhjä ja FALSE, jos jono ei ole tyhjä. Aikavaativuus : O(1)
Pino syntyy kun kohdistetaan listatyypin lisäys, poisto sekä haku operaatiot listan yhteen päähän. Tästä toimii Esimerkkinä, pöydällä oleva korttipakka, voit kohdistaa lisäyksen tai poiston vain päällimmäiseen korttiin.
Pino on tietorakenteena ikään kuin lista jonka operaatiot kohdistuvat aina listan ensimmäiseen alkioon eli pinon pinnalle. Tästä seuraa se ,että vain päällimmäinen alkio on käsiteltävissä. Useimmilla pino-operaatioilla onkin vain yksi parametri, nimittäin se pino, johon operaatio kohdistetaan.
STACK_CREATE (S, D)
Muodostaa tyhjän pinon. Aikavaativuus 0(1).
STACK_PUSH (S, x)
Vie pinoon S päällimmäiseksi alkion x. Aikavaativuus 0(1).
STACK_TOP (S)
Palauttaa pinon S päällimmäisen alkion arvon, jos pino on tyhjä, jää tulos
määrittelemättömäksi. Aikavaativuus 0(1).
STACK_POP (S)
Poistaa pinosta S päällimmäisen alkion arvon. Tyhjään pinoon
kohdistettaessa operaation vaikutus on määrittelemätön. Aikavaativuus
0(1).
STACK_PRINT (S)
Tulostaa pinon S alkiot päällimmäisestä alimmaiseen. Aikavaativuus 0(1).
STACK_FREE (S)
Aikavaativuus 0(1).
STACK_CONSTRUCT_RANDOM (S, count, min, max)
Aikavaativuus 0(1).
STACK_TYPE (S)
Aikavaativuus 0(1).
STACK_LESS (S, x, y)
Aikavaativuus 0(1).
STACK_SAME (S, x, y)
Aikavaativuus 0(1).
STACK_EMPTY (S)
Palauttaa boolen arvon true, mikäli pino S on tyhjä, muuten palauttaa
arvon false. Aikavaativuus 0(1).
Pino ja jono saadaan listasta rajoittamalla lisäys-, poisto- ja hakuoperaatiot kohdistuviksi aina vain listan jompaankumpaan päähän. Kohdistamalla nämä kolme operaatiota listan molempiin päihin, muttei muualle, saadaan listasta abstrakti tietotyyppi pakka. Luonnollisena ilmentymä pakasta toimii esimerkiksi kädessä pidettävä korttipakka.
Pakka on tietorakenteena kuin lista jonka operaatiot kohdistuvat aina listan jompaankumpaan päähän. Pakassa on kaksi paikkaa joihin operaatiot voidaan kohdistaa, joten operaatioissa täytyy ilmaista haluttu käsittelykohta.
DEQUE_CREATE (D, desc)
Muodostaa tyhjän pakan D. Aikavaativuus 0(1).
DEQUE_ENQUEUE (D ,e, x)
Vie pakan D alkuun (e = top) tai loppuun (e = bottom) alkion x.
Aikavaativuus 0(1).
DEQUE_FRONT (D)
Palauttaa pakan D ensimmäisen alkion arvon. Jos pakka on tyhjä, jää tulos
määrittelemättömäksi. Aikavaativuus 0(1).
DEQUE_REAR (D)
Palautta pakan D viimeisen alkion arvon, Jos pakka on tyhjä, jää tulos
määrittelemättömäksi. Aikavaativuus 0(1).
DEQUE_DEQUEUE (D, dir)
Poistaa pakasta D ensimmäisen ( e= top) tai viimeisen (e = bottom)
alkion. Tyhjään pakkaan kohdistettaessa operaation vaikutus on
määrittelemätön. Aikavaativuus 0(1).
DEQUE_PRINT (D)
Tulostaa pakan D. Aikavaativuus 0(1).
DEQUE_FREE (D)
DEQUE_CONSTRUCT_RANDOM (D, count, min, max)
Aikavaativuus 0(1).
DEQUE_TYPE (D)
Aikavaativuus 0(1).
DEQUE_LESS (D, x, y)
Aikavaativuus 0(1).
DEQUE_SAME (D, x, y)
Aikavaativuus 0(1).
DEQUE_EMPTY (D)
Palauttaa boolen arvon true, mikäli pakka D on tyhjä, muuten palauttaa
arvon false. Aikavaativuus 0(1).
Puu on kokoelma solmuja, jotka muodostavat hierarkkisen rakenteen. Solmu on puuhun kuuluva alkio, johon voidaan tallettaa dataa. Puu voi olla tyhjä. Juuri on puun ylin solmu. Sillä ei ole isää. Kullakin solmulla on vain yksi isä. Puun muut solmut muodostavat nolla tai useampia alipuita. Alipuilla ei ole yhteisiä solmuja. Solmun r alipuiden juuret ovat r:n jälkeläisiä (poikia) ja r on kunkin alipuun juuren isä, vanhempi. Yleisessä puussa kullakin solmulla voi olla mikä tahansa määrä jälkeläisiä. Jos solmulla ei ole jälkeläisiä, se on lehtisolmu. Muutoin solmu on haarautumasolmu. Saman vanhemman jälkeläisiä sanotaan sisarussolmuiksi.
Solmun syvyys puussa on polun pituus juuresta kyseiseen solmuun. Juuri on tasolla 0. Puun korkeus on pisimmän puussa esiintyvän polun pituus. Puu voi olla järjestetty - tällöin jälkeläisten järjestyksellä on merkitystä puussa. Järjestämättömässä puussa kaikki jälkeläisten järjestykset ovat samanvertaisia (järjestyksellä ei merkitystä).
Puulla on useita läpikäyntijärjestyksiä, niistä yleisimmät ovat: esi-, sisä-, jälki- ja tasoittainen järjestys.
Esijärjestyksessä käydään ensiksi juurisolmussa, jonka jälkeen käydään vasemmassa ja oikeassa lapsessa.
Sisäjärjestyksessä puu käydään läpi niin, että ensiksi käydään vasemmassa lapsessa, sitten juuressa ja lopuksi oikeassa lapsessa.
Jälkijärjestyksessä käydään ensiksi vasemmassa lapsessa, sitten oikeassa lapsessa ja lopuksi juuressa.
Tasoittainen läpikäynti etenee seuraavasti:
1. juuri 2. syvyydellä 1 olevat solmut vasemmalta oikealle 3. syvyydellä 2 olevat solmut vasemmalta oikealle 4. ... 5. puussa syvimmällä olevat solmut vasemmalta oikealle
TREE_CREATE (T, D)
muodostaa tyhjän puun
TREE_RETRIEVE (T, N)
Palauttaa puun T solmun N arvon.
TREE_PRINT_NODE (T, N)
Tulostaa solmun N puun T kuvaajassa määritellyllä tavalla. Solmun
N ei tarvitse olla kuitenkaan puussa T.
TREE_ROOT(T)
Palauttaa puun T juurisolmun. Jos puu on tyhjä puu, palauttaa NULL.
TREE_PARENT(T,N)
Palauttaa solmun N vanhemman (isän).
TREE_LEFTMOST_CHILD(T,N)
Palauttaa solmun N vanhimman lapsen.
TREE_RIGHT_SIBLING(T,N)
Palauttaa solmun N seuraavaksi vanhimman sisaruksen, tai NULL jos
N:llä ei ole nuorempia sisaruksia.
TREE_ASSIGN_ROOT(T,N)
Asettaa puun T juurisolmuksi N:n. N:n tyypiksi tulee puun T
tyyppi.
TREE_ASSIGN_LEFTMOST_CHILD(T,N,M)
Asettaa solmun N vanhimmaksi lapseksi solmun M. Solmu M muutetaan
samantyyppiseksi kuin solmu N.
TREE_ASSIGN_RIGHT_SIBLING(T,N,M)
Asettaa solmun N seuraavaksi (nuoremmaksi) sisarukseksi solmun
M. M:n tyypiksi tulee solmun N tyyppi.
TREE_CREATE_NODE(x)
Luo uuden solmun, asettaa sen dataksi x ja palauttaa luodun
solmun.
TREE_DESTROY_NODE (T,N)
Poistaa puusta T solmun N. Solmun poistamisen jälkeen solmun N,
kaikkien sen sisarusten ja kaikkien sen jälkeläisten tiedot
vanhentuvat.
TREE_FREE (T)
Vapauttaa kaiken puun T varaaman tilan ja asettaa puun T
määrittelemättömäksi puuksi.
Binääripuu on järjestetty puu, jossa jokaisella solmulla on täsmälleen kaksi lasta: vasen ja oikea. Solmut voivat olla myös tyhjiä. Binääripuu on täysi, jos kaikki puussa olevat tasot ovat täynnä, lukuunottamatta alinta tasoa. Binääripuuta käydään läpi kulkemalla solmusta solmuun. Jokaisen solmun kohdalla voidaan käsitellä vasenta alipuuta, oikeaa alipuuta tai solmua itseään. Solmun pojat erotetaan toisistaan kutsumalla toista vasemmaksi pojaksi ja toista oikeaksi pojaksi.
Binääripuiden operaatiot eivät juurikaan eroa yleisten puiden operaatioista. Operaatioiden TREE_LEFTMOST_CHILD ja TREE_RIGHT_SIBLING asemasta käytetään kätevämpiä operaatioita BTREE_LEFTCHILD ja BTREE_RIGHTCHILD. Näin ei tarvitse erikseen enää selvittää onko vanhin poika vasen vai oikea.
Näiden lisäksi binääripuilla on vielä muutama muu operaatio, jotka ovat:
Empty
Maketree(Vasen, Oikea, Arvo)
RightSubtree
LeftSubtree
Root
IsEmpty
Joukko on kokoelma mielivaltaisen tyyppisiä alkioita. Alkiotyyppi voi olla yksinkertainen (kokonaisluku), tai esimerkiksi joukko (kokonaisuus on siis joukkojen joukko). Joukon kaikki alkiot ovat keskenään erilaisia, ts. sama alkio ei voi esiintyä joukossa samanaikaisesti kahtena eri ilmentymänä. Mikäli joukon alkiot ovat joukkoja, voi alijoukkoihin sisältyä keskenään samoja alkioita, mutta saman joukon kaksi alijoukkoa eivät voi olla keskenään täysin samat.
Joukon alkiot ovat yleensä keskenään samaa tyyppiä. Atomeille oletetaan usein lineaarinen järjestys < (lue: "pienempi kuin" tai "edeltää"), joka täyttää seuraavat ehdot:
1) Jos a ja b ovat joukon S alkioita, vain yksi väittämistä a<b, a=b, b<a on tosi. 2) Jos a, b ja c ovat joukon S alkioita siten, että a<b ja b<c, niin a<c.
Joukossa alkioiden järjestys ei yleensä ole käyttäjälle näkyvä. Jos käyttäjä ei tarvitse järjestystä, toteutus voi määritellä sen sisäisesti sillä monet joukkojen toteutustavoista vaativat yksikäsitteisen järjestyksen.
Esittelyissä käytetyt parametrit:
DS on tyyppiä DSET.
x ja y ovat tyyppiä ELEMENT.
i on tyyppiä DSET_ITERATOR.
DSET_CREATE (DS, DESC)
Yleinen DSET_CREATE(DS, DESC) muodostaa tyhjän joukon DS, ja asettaa
joukon kuvaajaksi kuvaajan DESC = {INT_DESC| FLOAT_DESC| CHARP_DESC|
VOIDPTR_DESC}. Mikäli joukko DS ei ole tyhjä joukko, kaikki
joukossa ollut tieto menetetään, ja se jää varamaan muistia turhaan.
Tyypitetyt operaatiot muodostavat omaa tyyppiään olevan joukon DS.
Aikavaativuus : O(1)
DSET_FREE (DS)
Vapauttaa kaiken joukon DS varaaman tilan ja asettaa joukon DS
määrittelemättömäksi joukoksi. On hyvän ohjelmointitavan mukaista
vapauttaa ohjelman lopussa ohjelman varaama tila. Aikavaativuus : O(1)
DSET_TYPE (DS)
Palauttaa joukon DS kuvaajan. Käytetään lähinnä tilanteessa,
jossa ei ohjelmoitaessa tiedetä minkätyyppinen joukko joudutaan
luomaan. Uusi joukko M, joka on samaa tyyppiä kuin joukko DS,
luodaan komennolla DSET_CREATE(M, DSET_TYPE(DS));. Aikavaativuus : O(1)
DSET_LESS (DS, x, y)
Palauttaa tiedon siitä onko joukon DS kuvaajan määräämää tyyppiä
olevista elementeistä x järjestyksessä ennen y:tä. Elementtien x ja y pitää olla
samaa tyyppiä kuin joukon DS alkiot (muttei niiden ole pakko olla
joukon DS alkioita). Jos x<y niin DSET_LESS palauttaa FALSE.
Merkkijonojoukossa vertaillaan merkkijonojen välistä aakkosjärjestystä.
Aikavaativuus : O(1)
DSET_SAME (DS, x, y)
Palauttaa tiedon siitä ovatko joukon DS kuvaajan määräämää tyyppiä
olevat elementit x ja y samoja. Elementtien x ja y pitää olla samaa
tyyppiä kuin joukon DS alkiot (muttei niiden ole pakko olla joukon
DS alkioita). Jos x=y, niin DSET_SAME palauttaa siis
TRUE. Merkkijonojoukossa vertaillaan merkkijonojen välistä
aakkosjärjestystä. Aikavaativuus : O(1)
DSET_EMPTY (DS)
Palauttaa tiedon siitä onko joukko DS tyhjä joukko. Funktio
palauttaa TRUE jos joukko on tyhjä ja FALSE, jos joukko ei ole tyhjä.
Aikavaativuus : O(1)
DSET_INSERT (DS,x)
Lisää joukkoon DS elementin x säilyttäen joukon DS muilta osin
ennallaan. Jos elementti on jo joukossa, ei tee mitään.
Tyypitetyt operaatiot vievät joukkoon omaa tyyppiään olevan alkion.
Aikavaativuus : O(log n)
DSET_DELETE (DS,x)
Poistaa joukosta DS elementin x säilyttäen joukon DS muilta osin
ennallaan. Jos elementtiä ei ole joukossa, ei tee mitään.
Aikavaativuus : O(log n)
DSET_ASSIGN (DS1, DS2)
Asettaa joukon DS1 sisällön samaksi kuin joukon DS2 sisältö.
Joukon DS1 tyypiksi tulee joukon DS2 tyyppi. Jos joukko DS1
ei ole tyhjä, entiset tiedot tuhoutuvat! Aikavaativuus : O(n)
DSET_UNION (DS1, DS2)
Palauttaa (luo uuden) joukkojen DS1 ja DS2 yhdisteen muuttamatta
kuitenkaan alkuperäisiä joukkoja. Palautettava joukko on
joukon DS1 tyyppiä. Aikavaativuus : O(n)
DSET_INTERSECTION (DS1, DS2)
Palauttaa (luo uuden) joukkojen DS1 ja DS2 leikkauksen muuttamatta
kuitenkaan alkuperäisiä joukkoja. Palautettava joukko on
joukon DS1 tyyppiä. Aikavaativuus : O(n)
DSET_DIFFERENCE (DS1, DS2)
Palauttaa (luo uuden) joukkojen DS1 ja DS2 erotuksen muuttamatta
kuitenkaan alkuperäisiä joukkoja, ts. DS1 alioista pois kaikki
DS2: alkiot. Palautettava joukko on joukon DS1 tyyppiä.
Aikavaativuus : O(n)
DSET_MEMBER (DS, x)
Palauttaa tiedon siitä löytyykö joukosta DS elementti x.
Jos elementti löytyy, palauttaa arvon TRUE, muuten arvon FALSE.
Aikavaativuus : O(log n)
DSET_MIN (DS)
Palauttaa joukon DS pienimmän alkion. Operaation tulos on määrittelemätön
jos DS on tyhjä. Yleinen funktio DSET_MIN(DS) palauttaa ELEMENT-tyyppiä
olevan alkion ja tyypitetyt funktiot omaa tyyppiään olevan alkion.
Aikavaativuus : O(log n)
DSET_MAX (DS)
Palauttaa joukon DS suurimman alkion. Operaation tulos on määrittelemätön
jos DS on tyhjä. Yleinen funktio DSET_MAX(DS) palauttaa ELEMENT-tyyppiä
olevan alkion ja tyypitetyt funktiot omaa tyyppiään olevan alkion.
Aikavaativuus : O(log n)
DSET_EQUAL (DS1, DS2)
Palauttaa tiedon siitä, ovatko joukot DS1 ja DS2 samat, siis sisältävätkö
ne samat alkiot. Mikäli joukoissa on täsmälleen samat alkiot,
palauttaa TRUE, mutta jos joukot eroavat toisistaan ollenkaan, FALSE.
Aikavaativuus : O(n)
DSET_PRINT (DS)
Tulostaa näytölle joukon alkiot välilyönneillä erotettuina.
Aikavaativuus : O(n)
DSET_ANY(DS, i)
Alustaa joukon läpikäynnin i. Palauttaa joukon DS jonkin alkion, jos
joukko DS on tyhjä palauttaa tyhjän alkion. Muuttuja i tulee esitellä
seuraavasti i: DSET_ITERATOR;. Aikavaativuus : O(n)
DSET_ANOTHER(DS, i)
Palauttaa joukon DS läpikäynnissä i vielä käsittelemättömän alkion.
Jos joukon DS kaikki alkiot on jo käsitelty läpikäynnissä i palauttaa
tyhjän alkion. Jollei läpikäyntiä i ole aloitettu (operaatio
DSET_ANY(DS, i)), on operaatio määrittelemätön. Aikavaativuus : O(n)
DSET_ITERATING(DS, i)
Paluattaa arvon TRUE, jos joukon DS läpikäynti i on vielä kesken,
muuten palauttaa arvon FALSE. Jollei läpikäyntiä i ole aloitettu
(operaatio DSET_ANY(DS, i)), on operaatio määrittelemätön.
Aikavaativuus : O(n)
Prioriteettijonon (Priority Queue) nimitys perustuu siihen, että alkioille määritellään tärkeysjärjestys eli prioriteetti. Prioriteetti määrää alkioiden poistamisjärjestyksen prioriteettijonosta. Kyseessä ei siis ole tavallinen jono, josta alkiot poistetaan saapumisjärjestyksessä, vaan prioriteettijonoon vietävä alkio sijoittuu jonossa jo ennestään oleviin alkioihin nähden prioriteettinsa mukaisesti.
Paremman prioriteetin omaava poistetaan ennen huonomman prioriteetin omaavaa alkiota. Prioriteettijonosta voidaan ottaan käsittelyyn vain parhaan prioriteetin omaava alkio. Alkioiden prioriteettijonoon viemistä ei mitenkään rajoiteta. (TRA-kirjastossa pieni prioritteetti on parempi, huom. vain positiivisia arvoja käsitellään).
Esittelyissä käytetyt parametrit:
P on tyyppiä PRIQUEUE.
x ja y ovat tyyppiä ELEMENT.
pri on tyyppiä real.
PRIQUEUE_CREATE (P, DESC)
Yleinen PRIQUEUE_CREATE(P, DESC) muodostaa tyhjän prioriteettijonon P,
ja asettaa sen kuvaajaksi kuvaajan DESC = {INT_DESC | FLOAT_DESC |
CHARP_DESC | VOIDPTR_DESC}. Mikäli prioriteettijono P ei ole
tyhjä prioriteettijono, kaikki prioriteettijonossa ollut tieto
menetetään, ja se jää varamaan muistia turhaan. Tyypitetyt
operaatiot muodostavat omaa tyyppiään olevan prioriteettijonon P.
Aikavaativuus : O(1)
PRIQUEUE_FREE (P)
Vapauttaa kaiken prioriteettijonon P varaaman tilan ja asettaa
prioriteettijonon P määrittelemättömäksi prioriteettijonoksi.
On hyvän ohjelmointitavan mukaista vapauttaa ohjelman lopussa
ohjelman varaama tila. Jos void*- tai char*-prioriteettijonossa
on talletettuna tietoa jolle on varattu muistia eikä siihen enää
päästä käsiksi jonon tuhoamisen jälkeen, täytyy ennen PRIQUEUE_FREE:n
kutsumista huolehtia varatun muistitilan vapauttamisesta.
Aikavaativuus : O(n)
PRIQUEUE_TYPE (P)
Palauttaa prioriteettijonon P kuvaajan. Käytetään lähinnä tilanteessa,
jossa ei ohjelmoitaessa tiedetä minkätyyppinen prioriteettijono
joudutaan luomaan. Uusi prioriteettijono Q, joka on samaa tyyppiä
kuin prioriteettijono P luodaan komennolla
PRIQUEUE_CREATE(Q, PRIQUEUE_TYPE(P));. Aikavaativuus : O(1)
PRIQUEUE_LESS (P, x, y)
Palauttavat tiedon siitä onko prioriteettijonon P määräämää tyyppiä
olevista elementeistä x järjestyksessä ennen y:tä. Elementtien x ja y
pitää olla samaa tyyppiä kuin prioriteettijonon P alkiot
(muttei niiden ole pakko olla jonon P alkioita). Jos x<y niin
PRIQUEUE_LESS palauttaa TRUE. Merkkijonojonossa
vertaillaan merkkijonojen välistä aakkosjärjestystä.
Aikavaativuus : yksinkertaisille tyypeille O(1)
PRIQUEUE_SAME (P, x, y)
Palauttavat tiedon siitä ovatko prioriteettijonon P määräämää tyyppiä
olevat elementit x ja y samoja. Elementtien x ja y pitää olla samaa
tyyppiä kuin prioriteettijonon P alkiot (muttei niiden ole
pakko olla jonon P alkioita). Jos x=y, niin PRIQUEUE_SAME
palauttaa siis TRUE. Merkkijonojonossa vertaillaan merkkijonojen
välistä aakkosjärjestystä. Aikavaativuus : yksinkertaisille tyypeille O(1)
PRIQUEUE_EMPTY (P)
Palauttaa tiedon siitä onko prioriteettijono P tyhjä prioriteettijono.
Funktio palauttaa TRUE jos prioriteettijono on tyhjä ja FALSE,
jos prioriteettijono ei ole tyhjä. Aikavaativuus : O(1)
PRIQUEUE_INSERT (P, x, pri)
Lisää alkion x prioriteettijonoon P asettaen sille prioriteetin pri.
Tyypitetyt operaatiot vievät prioriteettijonoon omaa tyyppiään olevan alkion.
Aikavaativuus : O(n)
PRIQUEUE_DELETEMIN (P)
Poistaa prioriteettijonosta P pieniprioriteettisimman alkion.
Aikavaativuus : O(n)
PRIQUEUE_MIN (P)
Palauttaa prioriteettijonon P prioriteetiltään pienimmän alkion arvon. Aikavaativuus : O(n)
Suunnattu verkko (Divertex Graph) on tietorakenne, joka muodostuu kahdesta joukosta eli solmujen ja kaarten joukoista. G=(V, E), jossa V on solmujen joukko ja E on kaarien joukko. Suunnatun verkon alkioita ovat solmut, joita yhdistää kaari, jos solmuilla on suhde. Jollei solmujen välillä ole kaarta, ei tällöin kyseisillä solmuilla ole suhdetta. Suunnatussa verkossa suhdetta kuvaavilla kaarilla on suunta eli kaarella yhdistetyistä solmuista voidaan erottaa lähtö- ja päätesolmu.
Solmu A on solmun B naapuri, jos A:n ja B:n välillä on kaari siten, että B on lähtösolmu ja A on päätesolmu. Näin ollen A ja B ovat samanaikaisesti naapureita toisilleen vain siinä tapauksessa, että niiden välillä on kaksi toisistaan poikkeavaan suuntaan olevaa kaarta. Suunnatussa verkossa solmu voi olla itsensä naapuri ja kahden solmun välillä voip olla useitakin kaaria. Solmun naapureiden lukumäärää ei ole rajattu ja solmu voi olla mielivaltaisen monen solmun naapuri. Verkko on äärellinen, koska solmujen ja kaarten joukot ovat aina äärellisiä. Solmu ja kaari voidaan varustaa nimiöllä.
Verkon luontiin tarvittavat operaatiot:
DIGRAPH_CREATE(DG) DIGRAPH_INSERT_VERTEX(DG,lbl,cst,col) DIGRAPH_INSERT_EDGE(DG,from,to,lbl,cst,col) DIGRAPH_DELETE_EDGE(DG,E) DIGRAPH_RETRIEVE_EDGE(DG,V1,V2,) DIGRAPH_DELETE_VERTEX(DG,V) DIGRAPH_FREE(DG)
Verkon solmujen ja kaarten värittämiseen tarvittavat operaatiot:
DIGRAPH_VERTEX_COLOR(DG,V) DIGRAPH_VERTEX_COST(DG,V) DIGRAPH_VERTEX_LABEL(DG,V) DIGRAPH_EDGE_COLOR(DG,E) DIGRAPH_EDGE_COST(DG,E) DIGRAPH_EDGE_LABEL(DG,E) DIGRAPH_ASSIGN_VERTEX_COLOR(DG,V,color) DIGRAPH_ASSIGN_VERTEX_COST(DG,V,cost) DIGRAPH_ASSIGN_VERTEX_LABEL(DG,V,lbl) DIGRAPH_ASSIGN_EDGE_COLOR(DG,E,col) DIGRAPH_ASSIGN_EDGE_COST(DG,E,cst) DIGRAPH_ASSIGN_EDGE_LABEL(DG,E,lbl)
Verkon läpikäyntiin tatvittavat operaatiot:
DIGRAPH_IS_ADJACENT(DG,V1,V2) DIGRAPH_VERTEX_ANY(DG,i) DIGRAPH_VERTEX_ANOTHER(DG,i) DIGRAPH_VERTEX_ITERATING(DG,i) DIGRAPH_EDGE_ANY(DG,i) DIGRAPH_EDGE_ANOTHER(DG,i) DIGRAPH_EDGE_ITERATING(DG,i) DIGRAPH_VERTEX_ANY_ADJ(DG,V,i) DIGRAPH_VERTEX_ANOTHER_ADJ(DG,V,i) DIGRAPH_VERTEX_ITERATING_ADJ(DG,V,i) DIGRAPH_EDGE_ANY_ADJ(DG,E,i) DIGRAPH_EDGE_ANOTHER_ADJ(DG,E,i) DIGRAPH_EDGE_ITERATING_ADJ(DG,E,i)
Operaatioiden esittelyt:
Verkon luontiin tarvittavat operaatiot:
DIGRAPH_CREATE(DG)
Operaatio luo uuden tyhjän verkon DG. Aikavaativuus: O(1)
DIGRAPH_INSERT_VERTEX(DG, lbl, cst, col)
Asettaa uuden solmun nimiöltään lbl, väriltään col ja painoltaan
cst verkkoon DG, ja palauttaa luodun solmun. Aikavaativuus: O(1)
DIGRAPH_INSERT_EDGE(DG, from, to, lbl, cst, col)
Asettaa uuden kaaren nimiöltään lbl, väriltään col ja painoltaan
cst verkkoon DG solmujen from ja to välille, ja palauttaa luodun
kaaren. Aikavaativuus: O(1)
DIGRAPH_DELETE_EDGE(DG, E)
Operaatio poistaa kaaren E verkosta DG. Aikavaativuus: O(|E|)
DIGRAPH_RETRIEVE_EDGE(DG, V1, V2)
Palauttaa solmujen V1 ja V2 välillä verkossa DG olevan kaaren,
jos se on olemassa. Solmu V1 on oltava lähtösolmu ja V2 päätesolmu. Jollei
solmuja tai kaarta ole, operaatio palauttaa NIL. Aikavaativuus: O(|E|)
DIGRAPH_DELETE_VERTEX(DG, V)
Poistaa solmun V verkosta DG. Samoin poistuu myös solmuun V
liittyvät kaaret. Aikavaativuus: O(|E|+|V|)
DIGRAPH_FREE(DG)
Vapauttaa verkon DG varaaman tilan. Kaikki solmut ja kaaret
tuhotaan. Aikavaativuus: O(|E|+|V|)
Verkon solmujen ja kaarten värittämiseen tarvittavat operaatiot:
DIGRAPH_VERTEX_COLOR(DG, V)
Funktio palauttaa verkon DG solmun V värin. Aikavaativuus: O(1)
DIGRAPH_VERTEX_COST(DG, V)
Funktio palauttaa verkon DG solmun V painon. Aikavaativuus: O(1)
DIGRAPH_VERTEX_LABEL(DG, V)
Funktio palauttaa verkon DG solmun V nimiön. Aikavaativuus: O(1)
DIGRAPH_EDGE_COLOR(DG, E)
Funktio palauttaa verkon DG kaaren E värin. Aikavaativuus: O(1)
DIGRAPH_EDGE_COST(DG, E)
Funktio palauttaa verkon DG kaaren E painon. Aikavaativuus: O(1)
DIGRAPH_EDGE_LABEL(DG, E)
Funktio palauttaa verkon DG kaaren E nimiön. Aikavaativuus: O(1)
DIGRAPH_ASSIGN_VERTEX_COLOR(DG, V, col)
Asettaa solmun V väriksi col verkossa DG. Aikavaativuus: O(1)
DIGRAPH_ASSIGN_VERTEX_COST(DG, V, cost)
Asettaa solmun V painoksi cost verkossa DG. Aikavaativuus: O(1)
DIGRAPH_ASSIGN_VERTEX_LABEL(DG, V, lbl)
Asettaa solmun V nimiöksi lbl verkossa DG. Aikavaativuus: O(1)
DIGRAPH_ASSIGN_EDGE_COLOR(DG, E, col)
Asettaa kaaren E väriksi col verkossa DG. Aikavaativuus: O(1)
DIGRAPH_ASSIGN_EDGE_COST(DG, E, cst)
Asettaa kaaren E painoksi cst verkossa DG. Aikavaativuus: O(1)
DIGRAPH_ASSIGN_EDGE_LABEL(DG, E, lbl)
Asettaa kaaren E nimiöksi lbl verkossa DG. Aikavaativuus: O(1)
Verkon läpikäyntiin tarvittavat operaatiot:
DIGRAPH_IS_ADJACENT(DG, V1, V2)
Palauttaa arvon TRUE, jos verkon DG solmusta V1 johtaa kaari
solmuun V2, muutoin palauttaa arvon FALSE. Aikavaativuus: O(1)
DIGRAPH_VERTEX_ANY(DG, i)
Funktio alustaa verkon DG läpikäyntimuuttujan i ja palauttaa
verkon DG jonkin solmun. Jollei verkossa ole solmuja, funktio palauttaa
arvon NIL. Aikavaativuus: O(1)
DIGRAPH_VERTEX_ANOTHER(DG, i)
Palauttaa jonkin vielä käsittelemättömän solmun läpikäynnin i
mukaan verkossa DG. Jos verkon DG kaikki solmut on käyty läpi, funktio on
määrittelemätön. Aikavaativuus: O(1)
DIGRAPH_VERTEX_ITERATING(DG, i)
Palauttaa arvon TRUE, jos verkon
DG solmujen läpikäynti i on
vielä kesken, muuten FALSE. Aikavaativuus: O(1)
DIGRAPH_EDGE_ANY(DG, i)
Funktio alustaa verkon DG läpikäyntimuuttujan i ja palauttaa
verkon DG jonkin kaaren. Jollei verkossa ole kaaria, funktio palauttaa
arvon NIL. Aikavaativuus: O(|V|)
DIGRAPH_EDGE_ANOTHER(DG, i)
Palauttaa jonkin vielä käsittelemättömän kaaren läpikäynnin i
mukaan verkossa DG. Jos verkon DG kaikki kaaret on käyty läpi, funktio on
määrittelemätön. Aikavaativuus: O(|V|)
DIGRAPH_EDGE_ITERATING(DG, i)
Palauttaa arvon TRUE, jos verkon DG kaarien läpikäynti i on vielä
kesken, muuten FALSE. Aikavaativuus: O(1)
DIGRAPH_VERTEX_ANY_ADJ(DG, V, i)
Funktio alustaa verkon DG läpikäyntimuuttujan i ja palauttaa
verkon DG solmun V jonkin naapurisolmuista. Jollei solmulla V ole
naapurisolmuja, funktio palauttaa arvon NIL. Aikavaativuus: O(1)
DIGRAPH_VERTEX_ANOTHER_ADJ(DG, V, i)
Palauttaa solmun V jonkin vielä käsittelemättömistä
naapurisolmuista läpikäynnin i mukaan verkossa DG. Jos solmun V kaikki
naapurisolmut on käyty läpi, funktio on
määrittelemätön. Aikavaativuus: O(1)
DIGRAPH_VERTEX_ITERATING_ADJ(DG, V, i)
Palauttaa arvon TRUE, jos verkon DG solmun V naapurisolmujen
läpikäynti i on vielä kesken, muuten FALSE. Aikavaativuus: O(1)
DIGRAPH_EDGE_ANY_ADJ(DG, E, i)
Funktio alustaa verkon DG läpikäyntimuuttujan i ja palauttaa
verkon DG kaaren E jonkin naapurikaarista eli kaarista, jotka lähtevät
samasta solmusta. Jollei kaarella E ole naapurikaaria, funktio palauttaa
arvon NIL. Aikavaativuus: O(1)
DIGRAPH_EDGE_ANOTHER_ADJ(DG, E, i)
Palauttaa kaaren E jonkin vielä käsittelemättömistä
naapurikaarista läpikäynnin i mukaan verkossa DG. Jos kaaren E kaikki
naapurikaaret on käyty läpi, funktio on
määrittelemätön. Aikavaativuus: O(1)
DIGRAPH_EDGE_ITERATING_ADJ(DG, E, i)
Palauttaa arvon TRUE, jos verkon DG kaaren E naapurikaarien
läpikäynti i on vielä kesken, muuten FALSE. Aikavaativuus: O(1)
Suuntaamaton verkko (Graph) on tietorakenne, jonka muodostaa solmujen ja kaarten joukot kuten suunnatunkin verkon. (G=(V, E), jossa V on solmujen joukko ja E on kaarien joukko.) Suuntaamattomassa verkossa kaarilla ei kuitenkaan ole suuntaa kuten suunnatun verkon kaarilla. Näin ollen kaaren yhdistämiä solmuja voidaan kumpaakin kutsua päätesolmuksi. Suuntaamattomassa verkossa solmu on toisen naapuri, jos solmujen välillä on kaari. Solmu ei voi olla itsensä naapuri kuten suunnatussa verkossa ja solmujen välillä ei voi olla useampaa kuin yksi kaari. Kaari ja solmu voidaan varustaa nimiöllä.
Verkon luontiin tarvittavat operaatiot:
GRAPH_CREATE(G) GRAPH_FREE(G) GRAPH_INSERT_VERTEX(G,lbl,cst,col) GRAPH_DELETE_VERTEX(G,V) GRAPH_INSERT_EDGE(G,V1,V2,lbl,cst,col) GRAPH_DELETE_EDGE(G,E) GRAPH_RETRIEVE_EDGE(G,V1,V2)
Verkon solmujen ja kaarten värittämiseen tarvittavat operaatiot:
GRAPH_VERTEX_COLOR(G,V) GRAPH_VERTEX_COST(G,V) GRAPH_VERTEX_LABEL(G,V) GRAPH_ASSIGN_VERTEX_COLOR(G,V,col) GRAPH_ASSIGN_VERTEX_COST(G,V,cst) GRAPH_ASSIGN_VERTEX_LABEL(G,V,lbl) GRAPH_EDGE_COLOR(G,E) GRAPH_EDGE_COST(G,E) GRAPH_EDGE_LABEL(G,E) GRAPH_ASSIGN_EDGE_COLOR(G,E,col) GRAPH_ASSIGN_EDGE_COST(G,E,cst) GRAPH_ASSIGN_EDGE_LABEL(G,E,lbl)
Verkon läpikäyntiin tarvittavat operaatiot:
GRAPH_IS_ADJACENT(G,V1,V2) GRAPH_VERTEX_ANY(G,i) GRAPH_VERTEX_ANOTHER(G,i) GRAPH_VERTEX_ITERATING(G,i) GRAPH_EDGE_ANY(G,i) GRAPH_EDGE_ANOTHER(G,i) GRAPH_EDGE_ITERATING(G,i) GRAPH_VERTEX_ANY_ADJ(G,V,i) GRAPH_VERTEX_ANOTHER_ADJ(G,V,i) GRAPH_VERTEX_ITERATING_ADJ(G,V,i) GRAPH_EDGE_ANY_ADJ(G,E,i) GRAPH_EDGE_ANOTHER_ADJ(G,E,i) GRAPH_EDGE_ITERATING_ADJ(G,E,i)
Operaatioiden esittelyt:
Verkon luontiin tarvittavat operaatiot:
GRAPH_CREATE(G)
Operaatio luo uuden tyhjän verkon G. Aikavaativuus: O(1)
GRAPH_FREE(G)
Vapauttaa verkon G varaaman tilan. Kaikki solmut ja kaaret
tuhotaan. Aikavaativuus: O(|E|+|V|)
GRAPH_INSERT_VERTEX(G, lbl, cst, col)
Asettaa uuden solmun nimiöltään lbl, väriltään col ja painoltaan
cst verkkoon G, ja palauttaa luodun solmun. Aikavaativuus: O(1)
GRAPH_DELETE_VERTEX(G, V)
Poistaa solmun V verkosta G. Samoin poistuu myös solmuun V
liittyvät kaaret. Aikavaativuus: O(|E|+|V|)
GRAPH_INSERT_EDGE(G, V1, V2, lbl, cst, col)
Asettaa uuden kaaren nimiöltään lbl, väriltään col ja painoltaan
cst verkkoon G solmujen V1 ja V2 välille, ja palauttaa luodun
kaaren. Aikavaativuus: O(1)
GRAPH_DELETE_EDGE(G, E)
Operaatio poistaa kaaren E verkosta G. Aikavaativuus: O(|E|)
GRAPH_RETRIEVE_EDGE(G, V1, V2)
Palauttaa solmujen V1 ja V2 välillä verkossa G olevan kaaren, jos
se on olemassa. Jollei solmuja tai kaarta ole, operaatio palauttaa
NIL. Aikavaativuus: O(|E|)
Verkon solmujen ja kaarten värittämiseen tarvittavat operaatiot:
GRAPH_VERTEX_COLOR(G, V)
Funktio palauttaa verkon G solmun V värin. Aikavaativuus: O(1)
GRAPH_VERTEX_COST(G, V)
Funktio palauttaa verkon G solmun V painon. Aikavaativuus: O(1)
GRAPH_VERTEX_LABEL(G, V)
Funktio palauttaa verkon G solmun V nimiön. Aikavaativuus: O(1)
GRAPH_ASSIGN_VERTEX_COLOR(G, V, col)
Asettaa solmun V väriksi col verkossa G. Aikavaativuus: O(1)
GRAPH_ASSIGN_VERTEX_COST(G, V, cst)
Asettaa solmun V painoksi cost verkossa G. Aikavaativuus: O(1)
GRAPH_ASSIGN_VERTEX_LABEL(G, V, lbl)
Asettaa solmun V nimiöksi lbl verkossa G. Aikavaativuus: O(1)
GRAPH_EDGE_COLOR(G, E)
Funktio palauttaa verkon G kaaren E värin. Aikavaativuus: O(1)
GRAPH_EDGE_COST(G, E)
Funktio palauttaa verkon G kaaren E painon. Aikavaativuus: O(1)
GRAPH_EDGE_LABEL(G, E)
Funktio palauttaa verkon G kaaren E nimiön. Aikavaativuus: O(1)
GRAPH_ASSIGN_EDGE_COLOR(G, E, col)
Asettaa kaaren E väriksi col verkossa G. Aikavaativuus: O(1)
GRAPH_ASSIGN_EDGE_COST(G, E, cst)
Asettaa kaaren E painoksi cst verkossa G. Aikavaativuus: O(1)
GRAPH_ASSIGN_EDGE_LABEL(G, E, lbl)
Asettaa kaaren E nimiöksi lbl verkossa G. Aikavaativuus: O(1)
Verkon läpikäynteihin tarvittavat operaatiot:
GRAPH_IS_ADJACENT(G, V1, V2)
Palauttaa arvon TRUE, jos verkon G solmujen V1 ja V2 välillä on
kaari, muutoin palauttaa arvon FALSE. Aikavaativuus: O(1)
GRAPH_VERTEX_ANY(G, i)
Funktio alustaa verkon G läpikäyntimuuttujan i ja palauttaa
verkon G jonkin solmun. Jollei verkossa ole solmuja, funktio palauttaa
arvon NIL. Aikavaativuus: O(1)
GRAPH_VERTEX_ANOTHER(G, i)
Palauttaa jonkin vielä käsittelemättömän solmun läpikäynnin i
mukaan verkossa G. Jos verkon G kaikki solmut on käyty läpi, funktio on
määrittelemätön. Aikavaativuus: O(1)
GRAPH_VERTEX_ITERATING(G, i)
Palauttaa arvon TRUE, jos verkon G solmujen läpikäynti i on vielä
kesken, muuten FALSE. Aikavaativuus: O(1)
GRAPH_EDGE_ANY(G, i)
Funktio alustaa verkon G läpikäyntimuuttujan i ja palauttaa
verkon G jonkin kaaren. Jollei verkossa ole kaaria, funktio palauttaa
arvon NIL. Aikavaativuus: O(|V|)
GRAPH_EDGE_ANOTHER(G, i)
Palauttaa jonkin vielä käsittelemättömän kaaren läpikäynnin i
mukaan verkossa G. Jos verkon G kaikki kaaret on käyty läpi, funktio on
määrittelemätön. Aikavaativuus: O(|V|)
GRAPH_EDGE_ITERATING(G, i)
Palauttaa arvon TRUE, jos verkon G kaarien läpikäynti i on vielä
kesken, muuten FALSE. Aikavaativuus: O(1)
GRAPH_VERTEX_ANY_ADJ(G, V, i)
Funktio alustaa verkon G läpikäyntimuuttujan i ja palauttaa
verkon G solmun V jonkin naapurisolmuista. Jollei solmulla V ole
naapurisolmuja, funktio palauttaa arvon NIL. Aikavaativuus: O(1)
GRAPH_VERTEX_ANOTHER_ADJ(G, V, i)
Palauttaa solmun V jonkin vielä käsittelemättömistä
naapurisolmuista läpikäynnin i mukaan verkossa G. Jos solmun V kaikki
naapurisolmut on käyty läpi, funktio on
määrittelemätön. Aikavaativuus: O(1)
GRAPH_VERTEX_ITERATING_ADJ(G, V, i)
Palauttaa arvon TRUE, jos verkon G solmun V naapurisolmujen
läpikäynti i on vielä kesken, muuten FALSE. Aikavaativuus: O(1)
GRAPH_EDGE_ANY_ADJ(G, E, i)
Funktio alustaa verkon G läpikäyntimuuttujan i ja palauttaa
verkon G kaaren E jonkin naapurikaarista eli kaarista, jotka lähtevät
samasta solmusta. Jollei kaarella E ole naapurikaaria, funktio palauttaa
arvon NIL. Aikavaativuus: O(1)
GRAPH_EDGE_ANOTHER_ADJ(G, E, i)
Palauttaa kaaren E jonkin vielä käsittelemättömistä
naapurikaarista läpikäynnin i mukaan verkossa G. Jos kaaren E kaikki
naapurikaaret on käyty läpi, funktio on
määrittelemätön. Aikavaativuus: O(1)
GRAPH_EDGE_ITERATING_ADJ(G, E, i)
Palauttaa arvon TRUE, jos verkon G kaaren E naapurikaarien
läpikäynti i on vielä kesken, muuten FALSE. Aikavaativuus: O(1)