Listan funktioiden esittelyt


Listaa voidaan käsitellä yleisen listan avulla tietämättä listan oikeaa tyyppiä. Kuitenkin usein tarvitaan listoja jotka sisältävät jotakin määrätyntyyppistä tietoa. Mahdollisimman erityyppisten tilanteiden kattavuuden vuoksi tietorakennekirjastoa varten on toteutettu neljä erilaista tyypitettyä listatyyppiä : kokonaislukulista, joka sisältää int / integer - arvoja, liukulukulista (sisältää float / real - tyyppistä tietoa), merkkijonolista (char* / string[ ]) ja osoitinlista (void* / pointer - tyyppistä tietoa).

Tässä osassa on esitelty yleisen-, kokonaisluku-, liukuluku- ja merkkijonolistan funktiot. Osoitinlistasta enemmän osuudessa "Kirjaston laajentaminen". Funktioista / proseduureista esitellään aina ensiksi C-kieliset, sitten Pascal-kieliset versiot. Kaikkien funktioiden käytössä oletetaan että lista on määritelty. Mikäli parametrina annettava lista L on määrittelemätön, on aliohjelmien toiminta määrittelemätöntä, lukuunottamatta tietenkin LIST_CREATE:a joka määrittelee listan.

Yleisen listan käsittely

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. Kuvaajasta ja yleisen listan alkioiden tyypistä ELEMENT enemmän luvussa "Tietorakenteiden kuvaukset".

Int / integer - listan käsittely

Kokonaislukulistan esittelyissä käytetään kokonaislukutyyppinä tyypinmäärittelyä INT_TYPE, joka on toteutuskohtaisesti määritelty. Tämä siksi, että esimerkiksi joissakin MS/DOS-ympäristössä toimivissa kääntäjissä int on 16-bittinen luku (max. 2^16), mutta esim. cs:n gpc:ssä 32-bittinen (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.

Funktioiden esittelyt

LIST_CREATE (L, D)

void LIST_CREATE (LIST L, DESCRIPTOR D);

void INT_LIST_CREATE(LIST L);

void FLOAT_LIST_CREATE(LIST L);

void CHARP_LIST_CREATE(LIST L);

void VOIDPTR_LIST_CREATE(LIST L);

procedure LIST_CREATE (var L:LIST; D:DESCRIPTOR);

procedure INT_LIST_CREATE (var L:LIST);

procedure FLOAT_LIST_CREATE (var L:LIST);

procedure CHARP_LIST_CREATE (var L:LIST);

procedure VOIDPTR_LIST_CREATE (var L:LIST);

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. Esimerkki 1 : Pascal / C  

Aikavaativuus : O(1)

LIST_INSERT (L, p, x)

void LIST_INSERT (LIST L, LIST_POSITION p, ELEMENT x);

void INT_LIST_INSERT(LIST L, LIST_POSITION p, INT_TYPE x);

void FLOAT_LIST_INSERT(LIST L, LIST_POSITION p, FLOAT_TYPE x);

void CHARP_LIST_INSERT(LIST L, LIST_POSITION p, CHARP_TYPE x);

void VOIDPTR_LIST_INSERT(LIST L, LIST_POSITION p, *void x);

procedure LIST_INSERT (L:LIST; p:LIST_POSITION; x:ELEMENT);

procedure INT_LIST_INSERT (L:LIST; p:LIST_POSITION; x:INT_TYPE);

procedure FLOAT_LIST_INSERT (L:LIST; p:LIST_POSITION; x:FLOAT_TYPE);

procedure CHARP_LIST_INSERT (L:LIST; p:LIST_POSITION; x:CHARP_TYPE);

procedure VOIDPTR_LIST_INSERT (L:LIST; p:LIST_POSITION; x:pointer);

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. Esimerkki 1 : Pascal / C

Aikavaativuus : O(1)

LIST_RETRIEVE (L, p)

ELEMENT LIST_RETRIEVE (LIST L, LIST_POSITION p);

INT_TYPE INT_LIST_RETRIEVE (LIST L, LIST_POSITION p);

FLOAT_TYPE FLOAT_LIST_RETRIEVE (LIST L, LIST_POSITION p);

CHARP_TYPE CHARP_LIST_RETRIEVE (LIST L, LIST_POSITION p);

*void VOIDPTR_LIST_RETRIEVE (LIST L, LIST_POSITION p);

function LIST_RETRIEVE (L:LIST; p:LIST_POSITION) : ELEMENT;

function INT_LIST_RETRIEVE(L:LIST; p:LIST_POSITION) : INT_TYPE;

function FLOAT_LIST_RETRIEVE(L:LIST; p:LIST_POSITION) : FLOAT_TYPE;

function CHARP_LIST_RETRIEVE(L:LIST; p:LIST_POSITION) : CHARP_TYPE;

function VOIDPTR_LIST_RETRIEVE(L:LIST; p:LIST_POSITION) : pointer;

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)

LIST_POSITION LIST_LOCATE (LIST L, ELEMENT x);

LIST_POSITION INT_LIST_LOCATE(LIST L, INT_TYPE x);

LIST_POSITION FLOAT_LIST_LOCATE(LIST L, FLOAT_TYPE x);

LIST_POSITION CHARP_LIST_LOCATE(LIST L, CHARP_TYPE x);

LIST_POSITION VOIDPTR_LIST_LOCATE(LIST L, *void x);

function LIST_LOCATE (L:LIST; x:ELEMENT) : LIST_POSITION;

function INT_LIST_LOCATE (L:LIST; x:INT_TYPE) : LIST_POSITION;

function FLOAT_LIST_LOCATE (L:LIST; x:FLOAT_TYPE) : LIST_POSITION;

function CHARP_LIST_LOCATE (L:LIST; x:CHARP_TYPE) : LIST_POSITION;

function VOIDPTR_LIST_LOCATE (L:LIST; x:pointer) : LIST_POSITION;

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. Esimerkki 2 : Pascal / C

Aikavaativuus : O(1)

LIST_DELETE (L, p)

void LIST_DELETE (LIST L, LIST_POSITION p);

void INT_LIST_DELETE (LIST L, LIST_POSITION p);

void FLOAT_LIST_DELETE (LIST L, LIST_POSITION p);

void CHARP_LIST_DELETE (LIST L, LIST_POSITION p);

void VOIDPTR_LIST_DELETE (LIST L, LIST_POSITION p);

procedure LIST_DELETE (L:LIST; p:LIST_POSITION);

procedure INT_LIST_DELETE (L:LIST; p:LIST_POSITION);

procedure FLOAT_LIST_DELETE (L:LIST; p:LIST_POSITION);

procedure CHARP_LIST_DELETE (L:LIST; p:LIST_POSITION);

procedure VOIDPTR_LIST_DELETE (L:LIST; p:LIST_POSITION);

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. Esimerkki 2 : Pascal / C

Aikavaativuus : O(1)

LIST_NEXT (L, p)

LIST_POSITION LIST_NEXT (LIST L, LIST_POSITION p);

LIST_POSITION INT_LIST_NEXT (LIST L, LIST_POSITION p);

LIST_POSITION FLOAT_LIST_NEXT (LIST L, LIST_POSITION p);

LIST_POSITION CHARP_LIST_NEXT (LIST L, LIST_POSITION p);

LIST_POSITION VOIDPTR_LIST_NEXT (LIST L, LIST_POSITION p);

function LIST_NEXT (L:LIST; p:LIST_POSITION) : LIST_POSITION;

function INT_LIST_NEXT (L:LIST; p:LIST_POSITION) : LIST_POSITION;

function FLOAT_LIST_NEXT (L:LIST; p:LIST_POSITION) : LIST_POSITION;

function CHARP_LIST_NEXT (L:LIST; p:LIST_POSITION) : LIST_POSITION;

function VOIDPTR_LIST_NEXT (L:LIST; p:LIST_POSITION) : LIST_POSITION;

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 operaatioen 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)

LIST_POSITION LIST_PREVIOUS (LIST L, LIST_POSITION p);

LIST_POSITION INT_LIST_PREVIOUS (LIST L, LIST_POSITION p);

LIST_POSITION FLOAT_LIST_PREVIOUS (LIST L, LIST_POSITION p);

LIST_POSITION CHARP_LIST_PREVIOUS (LIST L, LIST_POSITION p);

LIST_POSITION VOIDPTR_LIST_PREVIOUS (LIST L, LIST_POSITION p);

function LIST_PREVIOUS (L:LIST; p:LIST_POSITION) : LIST_POSITION;

function INT_LIST_PREVIOUS (L:LIST; p:LIST_POSITION) : LIST_POSITION;

function FLOAT_LIST_PREVIOUS (L:LIST; p:LIST_POSITION) : LIST_POSITION;

function CHARP_LIST_PREVIOUS (L:LIST; p:LIST_POSITION) : LIST_POSITION;

function VOIDPTR_LIST_PREVIOUS (L:LIST; p:LIST_POSITION) : LIST_POSITION;

Palauttaa asemaa p edellisen aseman listassa L. Mikäli L ei ole tyhjä lista, PREVIOUS(L, p) listan viimeisen alkion asema. 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)

LIST_POSITION LIST_FIRST (LIST L);

LIST_POSITION INT_LIST_FIRST (LIST L);

LIST_POSITION FLOAT_LIST_FIRST (LIST L);

LIST_POSITION CHARP_LIST_FIRST (LIST L);

LIST_POSITION VOIDPTR_LIST_FIRST (LIST L);

function LIST_FIRST (L:LIST) : LIST_POSITION;

function INT_LIST_FIRST (L:LIST) : LIST_POSITION;

function FLOAT_LIST_FIRST (L:LIST) : LIST_POSITION;

function CHARP_LIST_FIRST (L:LIST) : LIST_POSITION;

function VOIDPTR_LIST_FIRST (L:LIST) : LIST_POSITION;

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).  Esimerkki 1 : Pascal / C  

Aikavaativuus : O(1)

LIST_LAST (L)

LIST_POSITION LIST_LAST (LIST L);

LIST_POSITION INT_LIST_LAST (LIST L);

LIST_POSITION FLOAT_LIST_LAST (LIST L);

LIST_POSITION CHARP_LIST_LAST (LIST L);

LIST_POSITION VOIDPTR_LIST_LAST (LIST L);

function LIST_LAST (L:LIST) : LIST_POSITION;

function INT_LIST_LAST (L:LIST) : LIST_POSITION;

function FLOAT_LIST_LAST (L:LIST) : LIST_POSITION;

function CHARP_LIST_LAST (L:LIST) : LIST_POSITION;

function VOIDPTR_LIST_LAST (L:LIST) : LIST_POSITION;

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).  Esimerkki 1 : Pascal / C 

Aikavaativuus : O(1)

LIST_EOL (L)

LIST_POSITION LIST_EOL (LIST L);

LIST_POSITION INT_LIST_EOL (LIST L);

LIST_POSITION FLOAT_LIST_EOL (LIST L);

LIST_POSITION CHARP_LIST_EOL (LIST L);

LIST_POSITION VOIDPTR_LIST_EOL (LIST L);

function LIST_EOL (L : LIST) : LIST_POSITION;

function INT_LIST_EOL (L : LIST) : LIST_POSITION;

function FLOAT_LIST_EOL (L : LIST) : LIST_POSITION;

function CHARP_LIST_EOL (L : LIST) : LIST_POSITION;

function VOIDPTR_LIST_EOL (L : LIST) : LIST_POSITION;

Palauttaa listan L EOL-aseman. Tyypitettyjen funktioiden toiminnassa ei ole eroa tähän. Esimerkki 1 : Pascal / C

Aikavaativuus : O(1)

LIST_PRINT (L)

void LIST_PRINT (LIST L);

void INT_LIST_PRINT (LIST L);

void FLOAT_LIST_PRINT (LIST L);

void CHARP_LIST_PRINT (LIST L);

void VOIDPTR_LIST_PRINT (LIST L);

procedure LIST_PRINT (L:LIST);

procedure INT_LIST_PRINT (L:LIST);

procedure FLOAT_LIST_PRINT (L:LIST);

procedure CHARP_LIST_PRINT (L:LIST);

procedure VOIDPTR_LIST_PRINT (L:LIST);

Tulostaa listan L kuvaajassa määritellyllä tavalla. Tyypitetyillä funktioilla ei ole eroa tämän toiminnan kanssa. Esimerkki 1 : Pascal / C  

Aikavaativuus : O(1)

Seuraavat aliohjelmat eivät ole välttämättömiä listan käytön kannalta, mutta helpottavat yleisten aliohjelmien tekemistä ja testaamista:

LIST_FREE (L)

void LIST_FREE (LIST L);

void INT_LIST_FREE (LIST L);

void FLOAT_LIST_FREE (LIST L);

void CHARP_LIST_FREE (LIST L);

void VOIDPTR_LIST_FREE (LIST L);

procedure LIST_FREE (var L:LIST);

procedure INT_LIST_FREE (var L:LIST);

procedure FLOAT_LIST_FREE (var L:LIST);

procedure CHARP_LIST_FREE (var L:LIST);

procedure VOIDPTR_LIST_FREE (var L:LIST);

Vapauttaa kaiken listan L varaaman tilan ja asettaa listan L määrittelemättömäksi listaksi. Esimerkki 1 : Pascal / C  

Aikavaativuus : O(n)

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 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'. Esimerkki 2 : Pascal / C

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 ohjelmoitaessa 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)

int LIST_LESS (LIST L, ELEMENT x, ELEMENT y);

int LIST_SAME (LIST L, ELEMENT x, ELEMENT y);

function LIST_LESS (L:LIST; x,y:ELEMENT) : boolean;

function LIST_SAME (L:LIST; x,y:ELEMENT) : boolean;

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 x<y niin LIST_LESS palauttaa TRUE (!=0). Merkkijonolistassa vertaillaan merkkijonojen välistä aakkosjärjestystä.

Aikavaativuus : yksinkertaisille tyypeille O(1)

LIST_EMPTY (L)

int LIST_EMPTY (LIST L);

int INT_LIST_EMPTY (LIST L);

int FLOAT_LIST_EMPTY (LIST L);

int CHARP_LIST_EMPTY (LIST L);

int VOIDPTR_LIST_EMPTY (LIST L);

function LIST_EMPTY (L:LIST) : boolean;

function INT_LIST_EMPTY (L:LIST) : boolean;

function FLOAT_LIST_EMPTY (L:LIST) : boolean;

function CHARP_LIST_EMPTY (L:LIST) : boolean;

function VOIDPTR_LIST_EMPTY (L:LIST) : boolean;

Palauttaa tiedon siitä onko lista L tyhjä lista. C-kielessä palautusarvo on siis !=0, jos lista on tyhjä, ja 0 mikäli lista ei ole tyhjä. Pascalissa funktio palauttaa TRUE jos lista on tyhjä ja FALSE, jos lista ei ole tyhjä.

Aikavaativuus : O(1)