Tietorakenteiden kuvaukset

Lista:

 List:
Lista abstraktina tietotyyppinä on keskenään samantyyppisten alkioiden kokoelma, jonka alkiot ovat toisiinsa nähden peräkkäissuhteessa. Lista voi olla tyhjä, jolloin 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.

Listatyyppiin ei sisältynyt operaatiota listassa jo olevan alkion muuttamista varten. Muutosoperaation puuttuminen ei estä alkion muuttamista, mutta muutoksen tekeminen on hieman vaivalloista: Aluksi selvitetään muutettavan alkion asema ja haetaan kyseisessä asemassa oleva arvo esiin. Tällä tavoin saadaan muodostetuksi listan alkion kopio, johon halutut muutokset tehdään. Lopuksi alkuperäinen alkio poistetaan listasta ja viedään muutettu kopio samaan asemaan, mistä alkio poistettiin. Yhden alkion muuttaminen toisin sanoen muuttaakin koko listan. Pinossa ja pakassa saatavilla oleva alkio muutetaan aivan vastaavalla tavalla

  

wpe1.jpg (7701 bytes)

Pino:

 Stack:
Kun listatyypin lisäys-, poisto- ja hakuoperaatioiden sallitaan kohdistua vain listan yhteen päähän - joko vain listan alkuun tai vain listan loppuun - johdutaan abstraktiin tietotyyppiin pino. Listan päistä käytetään tällöin nimityksiä pinon pinta ja pinon pohja. Kaikki pino-operaatiot kohdistuvat aina pinon pinnalle. Tämä merkitsee, että kaikista pinon alkioista vain päällimmäisin eli pinon pinnalla oleva alkio on käsiteltävissä. Pinon toiseksi päällimmäisimpään alkioon päästään käsiksi vain poistamalla pinosta ensin päällimmäisin alkio. Tyhjässä pinossa päällimmäistä alkiota ei ole lainkaan. Epätyhjään pinoon taas voi päällimmäisen alkion lisäksi sisältyä mielivaltainen määrä muita alkiota, joiden lukumärää tosin ei tunneta. Pinon ominaisuuksiin ei näet kuulu tietää, kuinka monta alkiota pino kullakin hetkellä sisältää. Pinoa kutsutaan toisinaan myös LIFO-listaksi, jolloin viitataan pinon alkioille tyypilliseen ominaisuuteen "last-in-first-out".

Koska kaikkien pino-operaatioiden toiminta kohdistuu aina pinon pinnalle, ei operaatioita käytettäessä tarvitse yksilöidä käsittelykohtaa. Tästä syystä aseman käsite menettää pinojen tapauksessa merkityksensä. Vastaavasti ei puhuta myöskään pinon alkioiden etäisyydestä pinon huipulta (tai pohjalta): ainoan mahdollisen käsiteltävissä olevan alkion etäisyys pinon pinnalta on joka tapauksessa nolla. Useimmilla pino-operaatioilla onkin vain yksi parametri, nimittäin se pino, johon operaatio kohdistetaan.

 wpe2.jpg (7512 bytes)

Jono:

 Queue:
Rajoittamalla listan käyttöä siten, että sallitaan alkioiden lisääminen vain listan loppuun ja alkioiden poistaminen ja hakeminen vain listan alusta, päädytään abstraktiin jonojen tietotyyppiin. Jono voi olla tyhjä tai sisältää mielivaltaisen määrän alkioita. Epätyhjään jonoon sisältyvien alkioiden lukumäärää ei tunneta. Jonoa kutsutaan joskus FIFO-listaksi, koska jonon alkioilla on ominaisuus "first-in-first-out". Uusi alkio asettuu aina jonon loppuun ja alkioita käsitellään saapumisjärjestyksessä. Jonosta ei voi poistaa keskeltä. Jono-operaatioissa ei käsittelykohtaa tarvitse yksilöidä, koska käsittelykohta on aina ilmeinen. wpe3.jpg (5992 bytes)
Prioriteettijono: Priority Queue:
Nimitys prioriteettijono perustuu siihen, että alkioille määritellään tärkeysjärjestys eli prioriteetti, joka määrää alkioiden joukostapoistamisjärjestyksen: paremman prioriteetin omaava alkio poistetaan joukosta ennen huonomman prioriteetin omaavaa alkiota. Kyseessä ei toisin sanoen ole puhdas jono, josta alkiot poistetaan saapumisjärjestyksessä, vaan prioriteettijonoon vietävä alkio sijoittuu jonossa jo ennestään oleviin alkioihin nähden oman prioriteettinsa mukaisesti. Prioriteettijonosta saadaan tavallinen jono kiinnittämällä prioriteetti samaksi kuin saapumisjärjestys eli kun sallitaan alkioiden poistaminen ainoastaan tietyssä järjestyksessä, päädytään prioriteettijonoon. Alkioiden prioriteettijonoon viemistä ei mitenkään rajoiteta. wpe4.jpg (5646 bytes)

Pakka:

 Deque:
Pino ja jono saadaan listasta rajoittamalla lisäys-, poisto- ja hakuoperaatiot kohdistuviksi aina vain listan jompaankumpaan päähän. Sallimalla nämä kolme operaatiota listan molemmissa päissä, muttei muualla, saadaan listasta abstrakti tietotyyppi pakka. wpe5.jpg (6443 bytes)
Taulukko: Array:
Silloin, kun kokoelman alkioihin on tärkeää päästä käsiksi mielivaltaisessa järjestyksessä, mutta alkioita halutaan silti käsitellä tehokkaasti myös peräkkäin, tarvitaan abstraktia taulukkotyyppiä. Taulukon alkioiden välillä vallitsee peräkkäisyyssuhde, mutta alkiot ovat saatavilla toisistaan riippumattakin, koska alkioiden asemat saadaan selville indeksoimalla eli ilmaisemalla alkioiden suhteelliset etäisyydet taulukon alusta lukien.

Alkiot sijaitsevat listassa peräkkäin ja useimmiten alkiot myös käsitellään peräkkäisjärjestyksessä. Käsittelysuunta tosin voi muuttua etenevästä takenevaksi, mutta kumpaankin suuntaan siirrytään alkio alkiolta. Muista listoista poiketen taulukot tukevat myös hajakäsittelyä, vaikka ovatkin sinänsä ilmiselvästi peräkkäisrakenteita.

 wpe6.jpg (7766 bytes)
Puu: Tree:
Puu määrää alkiokokoelmalle hierarkkisen rakenteen. Määritellään puu kokoelmaksi solmuja, jotka muodostavat hierarkkisen rakenteen. Solmujen hierarkia eli solmujen keskinäinen sijainti rakenteessa määräytyy solmujen välisen isä-relaation perusteella. Puun solmuista yksi, niin sanottu juuri (juurisolmu), on erityisasemassa: juurisolmulla ei ole isää. Puun kaikilla muilla solmuilla sen sijaan on yksiymmärteinen isäsolmu. Puun kukin solmu sisältää hallittavan alkiokokoelman yhden alkion, joka luonnollisesti voi olla minkä tahansa tyyppinen. wpe5.gif (2117 bytes)
Binääripuu: Binary tree:
Rajoittamalla solmun alipuiden lukumäärää saadaan joitakin tärkeitä puiden erikoistapauksia. €ärimmillään voidaan alipuiden määrä rajoittaa enintään yhteen, mutta tällainen puu on itse asiassa lista. Enintään kahden alipuun salliminen puolestaan johtaa binääripuun käsitteeseen, joka on yksi tietojenkäsittelytieteen keskeisimmistä peruspilareista.

Binääripuu on joko tyhjä puu tai puu, jonka kullakin solmulla on yksi, kaksi tai ei yhtään poikaa. Solmun pojat erotetaan toisistaan kutsumalla toista vasemmaksi pojaksi ja toista oikeaksi pojaksi. Näistä kahdesta pojasta kumpi tahansa voi puuttua. Olennainen ero binääripuun ja sellaisen yleisen puun, jonka jokaisella solmulla on enintään kaksi poikaa, välillä on seuraava: Jos yleisen puun solmulla on vain yksi poika, on se ilman muuta isänsä vanhin eli vasemmanpuoleisin poika. Sen sijaan binääripuun yksipoikaisen solmun ainoa poika on joko vasen tai oikea poika sen mukaan, kumpi pojista puuttuu. Binääripuun solmun ainoa poika ei toisin sanoen ilman muuta ole vasemmanpuoleinen poika.

 wpe3.gif (2153 bytes)
Joukko: Set:
Joukko on kokoelma mielivaltaisen tyyppisiä alkioita. Alkiotyyppi voi siis olla yksinkertainen (kuten kokonaisluku tai merkkijono), tai esimerkiksi joukko (kokonaisuus on siis joukkojen joukko). Joukon kaikki alkiot ovat keskenään erilaisia, toisin sanoen sama alkio ei voi esiintyä joukossa samanaikaisesti kahtena eri ilmentymänä. Mikäli joukon alkiot ovat joukkoja, voi alkiojoukkoihin toki sisältyä keskenään samojakin alkioita, mutta saman joukon kaksi eri alkiojoukkoa 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.

Alkioiden järjestyksen ei tarvitse olla 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.

wpe7.jpg (10451 bytes)
Suunnattu verkko: Divertex graph:
Suunnattu verkko G=(V, E) muodostuu solmujen (vertex, node) joukosta V ja suunnattujen kaarten (edge) joukosta E, jota kutsutaan joskus myös nuolten joukoksi. Solmut kuvaavat verkon perusalkioita ja solmujen väliset suhteet esitetään suunnattujen kaarten avulla. Suunnattu kaari on kahden solmun u ja v järjestetty pari (u, v), jota merkitään myös u ® v. Parin ensimmäinen solmu on suunnatun kaaren lähtösolmu ja jälkimmäinen solmu päätesolmu. Suunnattu kaari Ñ lyhyesti kaari, jos on selvää, että on kyse suunnatusta verkosta Ñ johtaa lähtösolmusta päätesolmuun. Kaari kuvaa parin jäsenten välistä naapuruussuhdetta: päätesolmu on lähtösolmun naapuri. Suhde on yksisuuntainen; päinvastainen naapuruussuhde vallitsee vain, jos verkossa on myös päinvastaiseen suuntaan suunnattu kaari. Solmulla voi olla mielivaltainen määrä naapureita ja vastaavasti solmu voi olla mielivaltaisen monen solmun naapuri. Solmu voi olla itsensä naapuri, ja naapuruus voi olla jopa moninkertaista, toisin sanoen lähtösolmusta päätesolmuun voi johtaa useita kaaria. Solmujen ja kaarten joukot ovat aina äärellisiä, joten verkkokin on äärellinen.Sekä verkon solmu että verkon kaari voidaan varustaa nimiöllä. wpe9.jpg (9853 bytes)
Suuntaamaton verkko: Graph:
Suuntaamaton verkko G=(V, E) koostuu solmuista ja kaarista kuten suunnattu verkkokin, mutta suuntaamattoman verkon kaaria ei varusteta suunnalla. Tämä merkitsee, että kaari (u, v) on järjestämätön pari ja se voidaan yhtä hyvin esittää muodossa (v, u). Koska kaarella ei ole suuntaa, voidaan molempia kaareen liittyviä solmuja kutsua kaaren päätesolmuiksi. Kaaren päätesolmut ovat toistensa naapureita, toisin sanoen naapuruussuhde on symmetrinen. Suunatusta verkosta poiketen, suuntaamattoman verkon kaaren ei sallita johtavan solmusta itseensä ja kahden eri solmun välillä saa olla vain yksi kaari. Abstraktin tietotyypin suuntamaton verkko operaatiot ovat samat kuin suunnatun verkon operaatiot. wpeA.jpg (9039 bytes)