Taulukko (tietorakenne) — ohjelmoinnin array: alkiot, koko ja indeksit
Tutustu taulukkoihin (array): alkiot, koko ja indeksit eri kielissä, indeksointi (0/1), koon rajoitukset ja käytännön esimerkit ohjelmoinnissa.
Ohjelmointikielissä taulukko (array) on tietorakenne, jonka avulla tallennetaan useita samanlaisia alkioita (esim. kokonaislukuja tai merkkijonoja). Taulukon jokaisella alkiolla on paikka järjestyksessä, ja paikkaa merkitään indeksillä. Indeksointi alkaa joissakin kielissä nollasta (0, 1, 2, ...), toisissa kielissä yhdestä (1, 2, 3, ...).
Peruskäsitteet
- Alkio: taulukon yksittäinen arvo (esimerkiksi luku tai merkkijono).
- Koko (length): alkioiden lukumäärä, jonka taulukko voi sisältää.
- Indeksi: alkion sijainti taulukossa; käytetään alkion hakemiseen.
Tyypilliset ominaisuudet
- Useissa staattisesti tyypitetyissä kielissä (esim. C, Java) taulukon kaikki alkiot ovat samaa tietotyyppiä. Joissakin dynaamisissa kielissä (esim. Python) vastaava rakenne (lista) voi sisältää eri tyyppisiä arvoja.
- Taulukot ovat yleensä peräkkäisessä muistiosoitteessa (contiguous memory), mikä mahdollistaa satunnaisen pääsyn alkioihin vakioajassa O(1).
- Monissa kielissä perinteisen taulukon koko on kiinteä: kun sen koko on määritelty, sitä ei voi muuttaa ilman uuden taulukon luomista ja kopiointia.
- Joissain kirjastoissa on dynaamisia taulukkorakenteita (esim. C++:n std::vector, Java:n ArrayList), jotka laajentuvat automaattisesti ja tarjoavat helppokäyttöisyyttä staattisten taulukoiden sijaan.
Indeksit ja sijoittuminen
Indeksit antavat tavan viitata yksittäiseen alkioon. Usein ensimmäisen alkion indeksi on 0, jolloin viimeisen alkion indeksi on koko − 1. Indeksin ulkopuolelle viittaaminen johtaa joko virheilmoitukseen (esim. Java, Python) tai määrittelemättömään käyttäytymiseen (esim. C).
Koko, muistin hallinta ja uudelleenasettaminen
Kun ohjelmoija luo perinteisen taulukon, hänen yleensä täytyy ilmoittaa sen koko. Jos tallennettavia alkioita tarvitaan enemmän kuin alkuperäinen koko sallii, tavallinen tapa on luoda uusi suurempi taulukko ja kopioida vanhan taulukon sisältö siihen. Tämä selittää, miksi staattisen taulukon koon muuttaminen on hankalampaa kuin dynaamisen taulukon (vektorin) käyttäminen.
C:n taulukot ovat esimerkki kiinteän kokoisista taulukoista: ne ovat suorassa muistissa ja niiden koko on yleensä määritettävä etukäteen. Dynaamisia ratkaisuja C:ssä voi toteuttaa malloc/realloc -kutsuin, mutta niissä on itse huolehdittava muistinhallinnasta.
Yleiset operaatiot ja niiden tehokkuus
- Alkion lukeminen kirjoittaminen indeksillä: O(1).
- Lisääminen taulukon loppuun dynaamisessa taulukossa: amortisoitu O(1); staattisessa taulukossa vaatii usein uudelleenallokoinnin O(n).
- Lisääminen tai poisto keskeltä: O(n) (vaatii alkioiden siirtämistä).
- Haku (tuntematon sijainti): lineaarinen haku O(n); jos taulukko on järjestetty, binäärihaku O(log n).
Moniulotteiset taulukot
Taulukko voi olla myös moniulotteinen (esim. kaksiulotteinen matriisi). Kaksitasoisessa taulukossa alkiot järjestetään riveihin ja sarakkeisiin. Huomioitavaa on järjestysmuisti (row-major vs column-major), joka vaikuttaa suorituskykyyn, kun käydään läpi alkioita.
Kieleen liittyviä eroja
- C: staattiset taulukot ovat kiinteän kokoisia ja sijaitsevat peräkkäisessä muistissa; indeksien ulkopuolelle meneminen on undefined behavior.
- Java: taulukot ovat olioita, niiden koko on kiinteä, mutta indeksiä valvotaan (IndexOutOfBoundsException).
- Python: lista (list) toimii käytännössä dynaamisena taulukkona ja sallii heterogeenisiä arvoja; myös Pythonissa indeksi tarkistetaan ja virhe aiheuttaa poikkeuksen.
- C++: tarjoaa sekä perinteiset taulukot että dynaamiset kontit kuten std::vector, joka yhdistää taulukon O(1)-pääsyn ja dynaamisen koonhallinnan.
Hyviä käytäntöjä
- Käytä taulukkoa, kun tiedät tai voit tehokkaasti arvioida alkioiden määrän ja tarvitset nopean satunnaishaun.
- Jos tarvitset usein lisäyksiä/poistoja keskeltä, harkitse linkitettyä listaa tai muuta data-rakennetta.
- Muista tarkistaa indeksien rajat tai käyttää kielikohtaisia turvallisia rakenteita virheiden välttämiseksi.
- Valitse dynaaminen taulukko (esim. vector/ArrayList) kun haluat joustavuutta ilman käsin tehtävää muistikopiointia.
Taulukko on yksinkertainen mutta tehokas tietorakenne, joka on perustana monille algoritmeille ja rakenteille. Sen ymmärtäminen — erityisesti indeksointi, koko ja muistin hallinta — on keskeistä ohjelmoinnissa.
Asettelut C:ssä
Ohjelmointikielessä C voidaan luoda matriiseja seuraavasti:
Tämä luo kokonaislukumassan, johon voidaan tallentaa 5 kokonaislukua. Ohjelmoija voi nyt tallentaa kokonaislukuja joukkoon tekemällä:
Ohjelmoija voi käyttää joukkoon sisältyvää arvoa näin:
Asettelut Javassa
Ohjelmointikielessä Java voidaan luoda matriiseja seuraavasti:
Tämä luo kokonaislukumassan, johon voidaan tallentaa 5 kokonaislukua. Ohjelmoija voi nyt tallentaa kokonaislukuja joukkoon tekemällä:
Ohjelmoija voi käyttää joukkoon sisältyvää arvoa näin:
Kysymyksiä ja vastauksia
K: Mikä on array ohjelmointikielissä?
V: Joukko on ohjelmointikielissä tapa tallentaa useita samantyyppisiä kohteita.
K: Minkä tyyppisiä kohteita voidaan tallentaa arrayyn?
V: Joukkoon voidaan tallentaa vain samantyyppisiä kohteita, kuten kokonaislukuja tai merkkijonoja.
Kysymys: Mikä on indeksi joukossa?
V: Indeksi on luku, joka on annettu jokaiselle joukon kohteelle, jotta ohjelmoija voi käyttää kyseistä kohdetta kyseisen luvun avulla.
Kysymys: Miten määritetään joukon ensimmäisen kohteen indeksi?
V: Joissakin ohjelmointikielissä ensimmäisen kohteen indeksi on 0, kun taas toisissa se on 1.
K: Mitä ohjelmoijan on annettava, kun hän luo arraya?
V: Ohjelmoijan on annettava array-koko, joka on arrayyn tallennettavien kohteiden määrä.
K: Miksi arrayn kokoa ei voi muuttaa?
V: Joukon kokoa ei voi muuttaa, koska se asetetaan, kun joukko luodaan.
K: Mitä ohjelmoijan on tehtävä, jos hän haluaa tallentaa enemmän kohteita kuin array-koko sallii?
V: Jos ohjelmoija haluaa tallentaa enemmän kohteita kuin array-koko sallii, hänen on luotava uusi array, jonka koko on suurempi.
Etsiä