Joukko

Sisältö:

Joukon määritelmä:

Joukko on kokoelma mielivaltaisen tyyppisiä alkioita eli se voi olla esimerkiksi kokonaislukujen joukko tai kokonaislukujen joukon joukko. Joukon kaikki alkiot ovat keskenään erilaisia eli sama alkio ei voi esiintyä joukossa samanaikaisesti kahtena ilmentymänä. Mikäli joukon alkiot ovat joukkoja, voi alkiojoukoissa toki esiintyä samoja alkioita, mutta kaksi eri alkiojoukkoa ei voi olla keskenään täysin samat. Joukon alkiot ovat yleensä keskenään samaa tyyppiä. Atomeille oletetaan usein lineaarinen järjestys, joka täyttää seuraavat ehdot:

1) Jos a ja b ovat Joukon S alkioita, vain yksi väittämistä a < b, a = b, tai b <  a on tosi.
2) Jos a, b ja c ovat joukon S alkioita siten, että a < b ja b < c , niin a < c.

Käytettävissä olevat tyypit:

Yleinen joukko:

Yleisen joukon funktioita tarvitaan silloin, kun pitää käsitellä joukkoa, jonka tyyppiä ei vielä ohjelmaa kirjoitettaessa tiedetä. Yleistä joukkoa luotaessa määritellään joukon tyyppi kuvaajan DESCRIPTOR avulla.

Kokonaislukujoukko:

Joukkoon voidaan tallettaa kokonaislukuja (integer). Funktioiden eteen pitää lisätä INT_ tai lyhenne IDS_ (INT_DSET).

Liukulukujoukko / reaalilukujoukko:

Joukkoon voidaan tallettaa liukulukuja / reaalilukuja (float). Funktioiden eteen pitää lisätä FLOAT_ tai lyhenne FDS_ (FLOAT_DSET).

Merkkijonojoukko:

Joukkoon voidaan tallettaa merkkijonoja (char). Funktioiden eteen pitää lisätä CHARP_ tai lyhenne CDS_ (CHARP_DSET).

Osoitinjoukko:

Joukkoon voidaan tallettaa osoittimia. Funktioiden eteem pitää lisätä VOIDPTR_ tai lyhenne PDS_ (VOIDPTR_DSET).


Funktiot:

Uuden joukon luominen:
DSET_CREATE(DS, D)

Yleinen DSET_CREATE(DS, D) muodostaa tyhjän joukon DS, ja asettaa joukon kuvaajaksi kuvaajan D . 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)

void DSET_CREATE(DSET DS, DESCRIPTOR D)
void INT_DSET_CREATE(DSET DS)
void FLOAT_DSET_CREATE(DSET DS)
void CHARP_DSET_CREATE(DSET DS)
void VOIDPTR_DSET_CREATE(DSET DS)

Joukkoon lisääminen:
DSET_INSERT (DS, x)

Lisää joukkoon DS elementin x. Jos elementti on jo joukossa, ei tee mitään. Tyypitetyt operaatiot vievät joukkoon omaa tyyppiään olevan alkion.
Aikavaativuus: O(log n)

void DSET_INSERT(DSET DS, ELEMENT x)
void INT_DSET_INSERT(DSET DS, INT_TYPE x)
void FLOAT_DSET_INSERT(DSET DS, FLOAT_TYPE x)
void CHARP_DSET_INSERT(DSET DS, char* x)
void VOIDPTR_DSET_INSERT(DSET DS, void* x)

Joukosta poistaminen:
DSET_DELETE(DS, x)

Poistaa joukosta DS elementin x. Jos elementtiä ei ole joukossa, ei tee mitään.
Aikavaativuus: O(log n)

void DSET_DELETE(DSET DS, ELEMENT x)
void INT_DSET_DELETE(DSET DS, INT_TYPE x)
void FLOAT_DSET_DELETE(DSET DS, FLOAT_TYPE x)
void CHARP_DSET_DELETE(DSET DS, char* x)
void VOIDPTR_DSET_DELETE(DSET DS, void* x)

Onko alkio joukossa:
DSET_MEMBER(DS, x)

Palauttaa tiedon siitä löytyykö joukosta DS elementti x. Jos elementti löytyy, palauttaa arvon !=0, muuten arvon 0.
Aikavaativuus: O(log n)

int DSET_MEMBER(DSET DS, ELEMENT x)
int INT_DSET_MEMBER(DSET DS, INT_TYPE x)
int FLOAT_DSET_MEMBER(DSET DS, FLOAT_TYPE x)
int CHARP_DSET_MEMBER(DSET DS, char* x)
int VOIDPTR_DSET_MEMBER(DSET DS, void* x)

Joukon minimi:
DSET_MIN(DS)

Palauttaa joukon DS pienimmän alkion. Yleinen funktio DSET_MIN(DS) palauttaa ELEMENT-tyyppiä olevan alkion ja tyypitetyt funktiot omaa tyyppiään olevan alkion.
Aikavaativuus: O(log n)

ELEMENT DSET_MIN(DSET DS)
INT_TYPE INT_DSET_MIN(DSET DS)
FLOAT_TYPE FLOAT_DSET_MIN(DSET DS) 
char* CHARP_DSET_MIN(DSET DS) 
void* VOIDPTR_DSET_MIN(DSET DS)

Joukon maksimi:
DSET_MAX(DS)

Palauttaa joukon DS suurimman alkion. Yleinen funktio DSET_MAX(DS) palauttaa ELEMENT-tyyppiä olevan alkion ja tyypitetyt funktiot omaa tyyppiään olevan alkion.
Aikavaativuus: O(log n)

ELEMENT DSET_MAX(DSET DS)
INT_TYPE INT_DSET_MAX(DSET DS) 
FLOAT_TYPE FLOAT_DSET_MAX(DSET DS) 
char* CHARP_DSET_MAX(DSET DS) 
void* VOIDPTR_DSET_MAX(DSET DS)

Joukon kopiointi:
DSET_ASSIGN(DS1,DS2)

Kopioi joukkoon DS1 kaikki joukon DS2 alkiot. Joukon DS1 tyypiksi tulee joukon DS2 tyyppi. Jos joukko DS1 ei ole tyhjä, entiset tiedot tuhoutuvat!
Aikavaativuus: O(n)

void DSET_ASSIGN(DSET DS1, DSET DS2)
void INT_DSET_ASSIGN(DSET DS1, DSET DS2)
void FLOAT_DSET_ASSIGN(DSET DS1, DSET DS2)
void CHARP_DSET_ASSIGN(DSET DS1, DSET DS2)
void VOIDPTR_DSET_ASSIGN(DSET DS1, DSET DS2)

Joukon yhdiste:
DSET_UNION(DS1,DS2)

Palauttaa joukkojen DS1 ja DS2 yhdisteen muuttamatta kuitenkaan alkuperäisiä joukkoja. Palautettava joukko on joukon DS1 tyyppiä.
Aikavaativuus: O(n)

DSET DSET_UNION(DSET DS1, DSET DS2)
DSET INT_DSET_UNION(DSET DS1, DSET DS2)
DSET FLOAT_DSET_UNION(DSET DS1, DSET DS2)
DSET CHARP_DSET_UNION(DSET DS1, DSET DS2)
DSET VOIDPTR_DSET_UNION(DSET DS1, DSET DS2)

Joukon erotus:
DSET_DIFFERENCE(DS1,DS2)

Palauttaa joukkojen DS1 ja DS2 erotuksen muuttamatta kuitenkaan alkuperäisiä joukkoja, ts. DS1 pois DS2. Palautettava joukko on  joukon DS1 tyyppiä.
Aikavaativuus: O(n)

DSET DSET_DIFFERENCE(DSET DS1, DSET DS2);
DSET INT_DSET_DIFFERENCE(DSET DS1, DSET DS2);
DSET FLOAT_DSET_DIFFERENCE(DSET DS1, DSET DS2);
DSET CHARP_DSET_DIFFERENCE(DSET DS1, DSET DS2);
DSET VOIDPTR_DSET_DIFFERENCE(DSET DS1, DSET DS2);

Joukon leikkaus:
DSET_INTERSECTION(DS1,DS2)

Palauttaa joukkojen DS1 ja DS2 leikkauksen muuttamatta kuitenkaan alkuperäisiä joukkoja. Palautettava joukko on joukon DS1 tyyppiä.
Aikavaativuus: O(n)

DSET DSET_INTERSECTION(DSET DS1, DSET DS2)
DSET INT_DSET_INTERSECTION(DSET DS1, DSET DS2)
DSET FLOAT_DSET_INTERSECTION(DSET DS1, DSET DS2)
DSET CHARP_DSET_INTERSECTION(DSET DS1, DSET DS2)
DSET VOIDPTR_DSET_INTERSECTION(DSET DS1, DSET DS2)

Onko joukkojen alkiot samat:
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 (!=0), mutta jos joukot eroavat toisistaan ollenkaan, (0).
Aikavaativuus: O(n)

int DSET_EQUAL(DSET DS1, DSET DS2)
int INT_DSET_EQUAL(DSET DS1, DSET DS2)
int FLOAT_DSET_EQUAL(DSET DS1, DSET DS2)
int CHARP_DSET_EQUAL(DSET DS1, DSET DS2)
int VOIDPTR_DSET_EQUAL(DSET DS1, DSET DS2)

Joukon tulostus:
DSET_PRINT (DS)

Tulostaa ruudulle joukon alkiot välilyönneillä erotettuina.
Aikavaativuus: O(1)

void DSET_PRINT(DSET DS)

Joukon vapautus:
DSET_FREE (DS)

Vapauttaa kaiken joukon DS varaaman tilan ja asettaa joukon DS määrittelemättömäksi joukoksi. On hyvä ohjelmointitapa vapauttaa ohjelman lopussa ohjelman varaama tila.
Aikavaativuus: O(1)

void DSET_FREE(DSET DS)
void INT_DSET_FREE(DSET DS)
void FLOAT_DSET_FREE(DSET DS)
void CHARP_DSET_FREE(DSET DS)
void VOIDPTR_DSET_FREE(DSET DS)

Joukon tyypin palautus:
DSET_TYPE (DS)

Palauttaa joukon DS kuvaajan. Käytetään lähinnä tilanteessa, jossa ei ohjelmoitaessa tiedetä minkätyyppinen joukko joudutaan luomaan.
Aikavaativuus: O(1)

DESCRIPTOR DSET_TYPE(DSET DS)

Onko joukko tyhjä:
DSET_EMPTY (DS)

Palauttaa tiedon siitä onko joukko DS tyhjä joukko. Palautusarvo on siis !=0, jos joukko on tyhjä, ja 0 mikäli joukko ei ole tyhjä.
Aikavaativuus: O(1)

int DSET_EMPTY(DSET DS)
int INT_DSET_EMPTY(DSET DS)
int FLOAT_DSET_EMPTY(DSET DS)
int CHARP_DSET_EMPTY(DSET DS)
int VOIDPTR_DSET_EMPTY(DSET DS)

Alkioiden vertailu:
DSET_LESS(DS, x, y)
DSET_SAME(DS, x, y)

Palauttavat tiedon siitä ovatko joukon DS kuvaajan 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 joukon DS alkiot (muttei niiden ole pakko olla joukon DS alkioita). Jos x=y, niin DSET_SAME palauttaa siis (!=0), ja jos x<y niin DSET_LESS palauttaa (0). Merkkijonojoukossa vertaillaan merkkijonojen välistä aakkosjärjestystä.
Aikavaativuus: O(1)

int DSET_LESS(DSET DS, ELEMENT x, ELEMENT y)
int DSET_SAME(DSET DS, ELEMENT x, ELEMENT y)

Satunnaisen alkion palauttaminen:
DSET_ANY(DS, i)

Alustaa joukon DS läpikäynnin i . Jos joukko on tyhjä, palauttaa tyhjän alkion.

ELEMENT DSET_ANY(DSET DS, DSET_ITERATOR i)
ELEMENT INT_DSET_ANY(DSET DS, DSET_ITERATOR i)
ELEMENT FLOAT_DSET_ANY(DSET DS, DSET_ITERATOR i)
ELEMENT CHARP_DSET_ANY(DSET DS, DSET_ITERATOR i)
ELEMENT VOIDPTR_DSET_ANY(DSET DS, DSET_ITERATOR i)

Seuraavan alkion palauttaminen:
DSET_ANOTHER(DS, i)

Palauttaa joukon S jonkin läpikäynnissä i vielä käsittelemättömän alkion. Jos joukon kaikki alkiot on jo käsitelty läpikäynnissä i , palauttaa tyhjän alkion. Jollei läpikäyntiä i ole aloitettu, on tulos määrittelemätön.

ELEMENT DSET_ANOTHER(DSET DS, DSET_ITERATOR i)
ELEMENT INT_DSET_ANOTHER(DSET DS, DSET_ITERATOR i)
ELEMENT FLOAT_DSET_ANOTHER(DSET DS, DSET_ITERATOR i)
ELEMENT CHARP_DSET_ANOTHER(DSET DS, DSET_ITERATOR i)
ELEMENT VOIDPTR_DSET_ANOTHER(DSET DS, DSET_ITERATOR i)

Onko läpikäynti vielä meneillään:
DSET_ITERATING(DS, i)

Palauttaa arvon true (!=0), jos joukon S läpikäynti i on vielä kesken, muuten palauttaa arvon false (0). Jollei läpikäyntiä i ole aloitettu, on operaation tulos määrittelemätön.

int DSET_ITERATING(DSET DS, DSET_ITERATOR i)
int INT_DSET_ITERATING(DSET DS, DSET_ITERATOR i)
int FLOAT_DSET_ITERATING(DSET DS, DSET_ITERATOR i)
int CHARP_DSET_ITERATING(DSET DS, DSET_ITERATOR i)
int VOIDPTR_DSET_ITERATING(DSET DS, DSET_ITERATOR i)