Tietorakenteet, kokoelmaluokat

Ohjelmoinnissa taulukko on aika yksinkertainen ja helppokäyttöinen, mutta useasti se ei vaan yksinkertaisesti riitä. Kuvittele esimerkiksi tilannetta, jossa pitäisi pystyä kysymään käyttäjältä lukuja ja tehdä niille jotain toimenpiteitä. Ohjelmassa ei saisi rajoittaa syötettyjen lukujen määrää, vaan käyttäjä voisi syöttää niin monta lukua kun vaan jaksaisi näpytellä. Tällöin ohjelmaa koodatessa ei olisi tiedossa, kuinka suuri taulukosta tulisi määritellä. Toisaalta voisimme alustaa ohjelmointikoodissa niin valtavan taulukon, että todennäköisesti kaikki syötetyt luvut sinne mahtuisivat, mutta tällöin varaisimme turhaan todella paljon muistia (ja käyttäjä voisi silti syöttää juuri yhden luvun enemmän kun taulukkoon mahtuisi).

Tällaisia suurempia tietomääriä varten ohjelmointikielissä on käytössä dynaamisia tietorakenteita eli kokoelmia. Niiden koko kasvaa sitä mukaa, kun niihin lisätään alkioita. C#:ssa on valmiiksi aika paljon erityyppisiä tietorakenteita, niihin kannattaa ehdottomasti tutustua ennen kuin aloittaa toteuttamaan jotain omaa rakennetta. Täällä yleisesittely .NET:in erilaisista kokoelmista ja tietorakenteista.

Kurssilla otetaan käsittelyyn vain geneerisiä eli yleiskäyttöisiä kokoelmia, jotka on esitelty system.Collections.Generic-nimiavaruudesta. Geneerisille tietorakenteille tulee aina esitellä sen sisältämä tietotyyppi <>-merkkien sisälle.

.NET ja Kokoelmat (Collections)

.NET Framework tarjoaa hyvän valikoiman tyyppejä ja luokkia oliokokoelmien tallentamiseen ja käsittelyyn --> katso Collections and Data Structures. Näihin kuuluvat: uudelleenmääriteltävät listat (resizable lists), linkitetyt listat (linked lists), lajitellut ja lajittelemattomat hakemistot (dictionaries) kuin myös taulukot (arrays). Näistä ainoastaan Array kuuluu C#-kieleen, muut ovat instantoivia .NETin luokkia.

Lista (List)

Listaa (List<T>) voidaan ajatella automaattisesti kokoaan muuttavana taulukkona. Lista on dynaaminen, eli sinne voi lisätä alkioita, ja sieltä voi poistaa alkioita; tällöin listan koko muuttuu dynaamisesti. Lista on vahvasti tyypitetty. Uudet alkiot lisätään aina listan loppuum ja alkioihin voidaan viitata indekseille tai viittauksilla. Sille on tarjolla paljon käteviä toimintoja tiedon lisäämiseen, poistamiseen, etsimiseen, järjestämiseen jne. Lisätietoa: List<T> Class.

Kokonaisluvut listaan

Alla olevassa esimerkissä luodaan lista, johon talletetaan käyttäjän syöttämät kokonaisluvut.

Tulosteena voisi olla seuraava (riippuu siitä mitä arvoja käyttäjä syöttää):

    Give a number > 2
    Give a number > 4
    Give a number > 6
    Give a number > 8
    Give a number > 1
    Give a number > 3
    Give a number > 5
    Give a number > 7
    Give a number >
    Average : 4,5
    Min : 1
    Max : 8
    Numbers count : 8
    2,4,6,8,1,3,5,7
    1,2,3,4,5,6,7,8    
    

Listan geneeriset metodit (List<T> Methods)

List<T> sisältää monia käyttökelpoisia toimintoja listan jäsenten käsittelyyn. Alla olevassa esimerkissä on käytetty ForEach-toimintoa ja sille on annettu delegaattina funktio mitä kullekin listan jäsenelle tehdään.

Delegaattina voi käyttää myös omia metodeja, kuten alla olevassa esimerkissä on tehty.

Oliot listaan

Edellisessä esimerkissä listaan talletettiin arvotyyppejä. Lista ottaa vastaan myös viittaustyyppejä eli oliota.

Tehdään ensin Person-luokka, joka käsittelee muutamia henkilölle kuuluvia ominaisuuksia, jotka voidaan palauttaa ToString()-metodilla yhtenä merkkojonona.

Luokkaa voidaan käyttää seuraavasti:

Kokoelman järjestäminen

Kokoelman sisältämiä alkioita voidaan järjestellä monella eri tavalla. Yksi helpoimmista on käyttää Comparison<T> delegaattia, jolla voidaan vertailla kahta samantyyppistä objektia.

Järjestellään persons-lista sukunimen mukaan järjestykseen ja tulostetaan uudelleen. Sort-metodissa määritellään objektit, joita vertaillaan eli tässä tapauksessa listan kaksi alkiota. Objektien vertailussa käytetään compareTo()-metodia, joka vertailee kahta merkkijonoa keskenään (Lastnames). CompareTo()-metodi palauttaa vertailussa < 0 arvon, jos sukunimi on aakkosissa aikaisemmin verrattuun nähden, jolloin objekti siirretään listassa vertailtavaa ennen. Vastaavasti metodi palauttaa vertailussa > 0 arvon, jos objektin sukunimi on akkosissa myöhemmin vertailtavaan nähden. Metodi palauttaa arvon 0, jos sukunimet ovat samoja.

Huomaa tulosteiden ero kahdessa edellä esitetyssä esimerkissä. Ensimmäisessä oliot ovat persons-kokoelmassa siinä järjestyksessä kuin ne on sinne lisätty. Jälkimmäisessä järjestys on järjestelty objektien sukunimien mukaisesti aakkosjärjestykseen.

Toinen vaihtoehto on määritellä luokka toteuttamaan IComparable-rajapinta. Tuolloin luokan on toteutettava CompareTo-metodi. Person-luokka voitaisiin muuttaa seuraavasti. Toteutuksessa CompareTo-metodi vertailee ensisijaisesti sukunimiä, ja jos ovat samoja, niin sitten etunimiä.

Nyt kokoelmaa käyttämässä ohjelmassa riittää käyttää vain Sort()-metodia, joka käy automaattisesti läpi kokoelman alkiot ja niiden CompareTo()-metodit.

persons.Sort();

Pino (Stack)

Pino (Stack<T>) voi sisältää arvotyyppejä ja olioita kuten edellä esitetty lista seuraavin poikkeuksin: alkiot lisätään aina pinon päälle ja poisto tapahtuu myös aina pinon päältä, käsitteen LIFO (Last in First out) mukaan.

Stack - tyypilliset metodit
Push Lisää uuden alkion pinon päällimmäiseksi.
Pop Poistaa alkion pinon päältä.
Peek Palauttaa pinon päällimmäisen alkion ilman että sitä poistetaan.
Contains Tutkii onko tutkittava pinossa.
Lisätietoa: Stack<T> Class.

Seuraavassa esimerkissä on talletettu merkkijonoja pinoon ja esitetty muutamia perustoimintoja.

Jono (Queue)

Jono (Queue<T>) on tietorakenne, joka toteuttaa käsitteen FIFO, First in first out. Jono käsittelee sekä arvotyyppejä että oliota kuten aikaisemmin esitetyt rakenteet. Eli voit tallentaa sinne vaikka omia olioitasi.

Queue - tyypilliset metodit
Enqueue Lisää uuden alkion jonon viimeiseksi.
Dequeue Poistaa jonon ensimmäisen alkion.
Peek Palauttaa jonon ensimmäisen alkion ilman että sitä poistetaan.
Contains Tutkii onko tutkittava jonossa.
Ominaisuus Count palauttaa montako alkiota/elementtiä jonossa on.
Lisätietoa: Queue<T> Class.

Alla olevassa esimerkissä lisätään muutamia lukuja jonoon ja otetaan jonosta alkioita.

Kokoelma eli "Sanakirja" (Dictionary)

Dictionary<TKey,TValue>
Tietorakenne Dictionary sisältää sekä avaimia (key) ja arvoja (value). Tietorakenteessa olevat avaimet ovat aina uniikkeja ja viittaavat johonkin arvoon/tietoon. Tietorakenteen määrittelyn yhteydessä annetaan aina tyyppi sekä avaimelle että arvolle. Lisätietoa: Dictionary<TKey,TValue> Class.

Alla olevassa esimerkissä kokoelmaan on talletettu Person-luokan (esitetty aikaisemmin) olioita siten, että avaimena toimii henkilön sotu ja itse arvona henkilö olio.

Alla olevassa esimerkissä käydään läpi kaikki kokoelman avaimet ja arvot:

Voidaan käydä läpi myös koko kokoelma eli avaimet ja arvot samanaikaisesti:

Ja avain-arvopareja voidaan poistaa Remove()-metodilla:

Hashtable

Hashtable on hieman samantyyppinen kuin edellä mainittu Dictionary. Hashatablessa on avaimia (key) ja arvoja (value), haut ovat nopeita. Hashtable on kuitenkin vanhempaa kamaa, ja on suositeltavaa käyttää Dictionary sen sijasta. Jos kuitenkin haluat tutustua Hashtableen, löydät DotNetPerls-sivustolta kelpo dokumentaation sen käytöstä.

Yhteenveto

Lisätietoa:

Collections (C#)
Commonly Used Collection Types