Tietorakenne

tietty tapa tallettaa ja jäsentää tieto tietokoneessa

Tietorakenne on tietojenkäsittelyssä esiintyvä termi, joka tarkoittaa tapaa säilöä ja käsitellä dataa tietokoneella tyypillisesti tietokoneen muistissa tietokoneohjelman suorituksen aikana. Tiedostoihin tallennetun tiedon järjestämisestä (siirtäminen, pysyvä säilytys) käytetään termiä tiedostomuoto. Säilömistä tai toiselle koneelle siirtämistä varten tietorakenteet on serialisoitava tarkoitukseen sopivassa muodossa.[1][2]

Taustaa muokkaa

 
Esimerkki hajautustauluna tunnetusta tietorakenteesta.

Algoritmit riippuvat tietorakenteiden suunnittelusta.[3] Tietorakenteen vaihtaminen ei vaikuta algoritmin oikeellisuuteen, mutta se voi tarjota vaihtoehtoja ja vaikuttaa operaatioiden tehokkuuteen, jolloin suorituskyky voi parantua dramaattisesti.[4]

Matematiikassa muuttujat luokitellaan tiettyjen tärkeiden piirteiden mukaan, josta esimerkkinä jakaminen reaali- ja kompleksilukuihin tai joukkoihin arvoja.[5] Luokittelu on vähintään yhtä tärkeää tietojen käsittelyssä ja muuttujilla, vakioilla, lausekkeilla ja aliohjelmilla on tietty tyyppi.[5] Tyyppien lisäksi yleiskäyttöisen ohjelmointikielen on tarjottava menetelmä koostaa tietoa rakenteisiin.[5] Rakenteet voivat vaihdella yksinkertaisista monimutkaisiin ja ne voivat olla kiinteitä tai dynaamisesti muodostettuja.[5]

Taulukko on yksi tunnetuimmista tietorakenteista koska monissa kielissä kuten Fortran ja ALGOL se on ainoa eksplisiittisesti saatavilla oleva tietorakenne.[5] Taulukko on homogeeninen tietorakenne, joka koostuu komponenteista, jotka ovat kaikki samaa tyyppiä (perustyyppi).[5] Taulukkoa voi käyttää hajasaantina ja jokaiseen elementtiin voi lukea ja kirjoittaa missä tahansa järjestyksessä.[5] Taulukossa yksittäiseen elementtiin viitataan indeksillä, joka voi olla eri tyyppiä kuin taulukon perustyyppi.[5]

Monissa tapauksissa tarvitaan tietojen yhdistelmää esimerkiksi koordinaattijärjestelmä voi vaatia pisteelle kahta numeroa ilmaistuna tai luonnolliseen henkilöön voidaan liittää etu- ja sukunimi, syntymäpäivä ja niin edelleen.[5] Yhdistelmätyypistä käytetään tietojenkäsittelyssä termiä tietue.[5] Eri yhdistelmätyyppejä voi muodostaa kielestä riippuen muun muassa struct tai tuple -tyyppeinä, joissa ensimmäisessä jäsenkentät ovat nimettyjä kun taas jälkimmäisessä ne eivät ole: tämä vaikuttaa tietojen käsittelyn helppouteen.[6][7]

Joukko on taulukon ja tietueen ohella perustava käsite, joka voi sisältää x kappaletta muun tyyppistä elementtiä.[5]

 
Tyyppihierarkia Python 3:ssa.

Tietorakenteita muokkaa

Spatiaaliset tietorakenteet muokkaa

Spatiaalinen tietorakenne on sellainen tietorakenne, jossa määrätyn etäisyysmitan perusteella lähimmän alkion hakeminen on tehokasta. Spatiaalisia tietorakenteita euklidiseen avaruuteen ovat 3D-grafiikassa paljon käytetyt bsp-puu ja kd-puu.

Katso myös muokkaa

Lähteet muokkaa

  1. Serialization and Unserialization isocpp.org. Viitattu 9.9.2022. (englanniksi)
  2. Serialization (C#) docs.microsoft.com. 15.9.2021. Viitattu 9.9.2022. (englanniksi)
  3. John Bullinaria: Lecture Notes for Data Structures and Algorithms (PDF) (sivu 5) cs.bham.ac.uk. 27.3.2019. Viitattu 8.9.2022. (englanniksi)
  4. Skiena, Steven S.: The Algorithm Design Manual, s. 3–4,65,273. Second edition. Springer, 2008. ISBN 978-1-84800-070-4. doi:10.1007/978-1-84800-070-4. (englanniksi)
  5. a b c d e f g h i j k Wirth, Niklaus: Algorithms + Data structures = Programs, s. 1–6,11,16,23–33. Prentice-Hall, 1976. ISBN 0-13-022418-9. (englanniksi)
  6. Defining and Instantiating Structs doc.rust-lang.org. Viitattu 9.9.2022. (englanniksi)
  7. Data Types doc.rust-lang.org. Viitattu 9.9.2022. (englanniksi)

Kirjallisuutta muokkaa

  • Mehta, Dinesh P. & Sahni, Sartaj: Handbook of Data Structures And Applications. Chapman & Hall/CRC, 2005. ISBN 1-58488-435-5. (englanniksi)
  • A. V. Aho, J. E. Hopcroft, J. D. Ullman: Data Structures and Algorithms. Addison-Wesley, 1983. ISBN 0-201-00023-7. (englanniksi)

Aiheesta muualla muokkaa