Taulukko (tietotyyppi)

Taulukko on tietorakenne , joka tallentaa joukon arvoja (taulukon elementtejä), jotka on tunnistettu indeksillä, tai joukko indeksejä, jotka ottavat kokonaislukuja (tai muunnettavia) arvoja joltakin tietyltä jatkuvalta alueelta. Yksiulotteinen taulukko voidaan ajatella abstraktin tietotyypin, vektorin, toteutuksena. Joissakin ohjelmointikielissä taulukkoa voidaan kutsua myös taulukoksi, riviksi, vektoriksi tai matriisiksi.

Taulukon dimensio on indeksien lukumäärä, joka tarvitaan taulukon elementin yksilölliseen osoittamiseen [1] . Käytettyjen indeksien lukumäärän mukaan taulukot jaetaan yksiulotteisiin, kaksiulotteisiin, kolmiulotteisiin jne.

Matriisin muoto tai rakenne - tiedot mittojen lukumäärästä ja taulukon koosta (pituudesta) kullekin ulottuvuudelle [2] ; voidaan esittää yksiulotteisella taulukolla [3] .

Matriisin ominaisuus tietorakenteena (toisin kuin esimerkiksi linkitetyssä listassa ) on jatkuva laskennallinen monimutkaisuus taulukon elementtiin indeksin avulla pääsemisessä [4] . Array viittaa hajasaantitietorakenteisiin .

Yksinkertaisimmassa tapauksessa taulukon pituus on vakio kaikissa ulottuvuuksissa ja se voi tallentaa vain yhden kuvauksessa määritellyn tyypin tietoja. Useat kielet tukevat myös dynaamisia taulukoita , joiden pituus voi muuttua ohjelman suorituksen aikana, ja heterogeenisia taulukoita , jotka voivat tallentaa erityyppisiä tietoja eri elementteihin. Joitakin tiettyjä eri kielissä ja toteutuksissa käytettyjä matriisityyppejä ovat assosiatiivinen taulukko , segmenttipuu , V-lista , rinnakkaistaulukko , harvat taulukot .

Taulukon käytön tärkeimmät edut ovat elementin osoitteen laskemisen helppous sen indeksin perusteella (koska taulukon elementit sijaitsevat peräkkäin), sama pääsyaika kaikille elementeille, elementtien pieni koko (ne koostuvat vain tietokentästä). Haittoja ovat kyvyttömyys poistaa tai lisätä elementtiä siirtämättä muita staattisia taulukoita käytettäessä, ja käytettäessä dynaamisia ja heterogeenisia taulukoita, hitaampi suorituskyky johtuen dynamiikan ja heterogeenisyyden ylläpitämisestä. Kun työskentelet taulukoiden kanssa, joissa on C-toteutus (osoittimilla) ja ilman lisäohjaimia, tyypillinen ajonaikainen virhe on taulukon ylityksen ja tietojen vioittumisen uhka.

Toteutusvaihtoehdot

Taulukko on järjestetty joukko elementtejä, joista jokainen tallentaa yhden arvon, joka tunnistetaan yhdellä tai useammalla indeksillä. Yksinkertaisimmassa tapauksessa taulukon pituus on vakio ja se tallentaa samantyyppisiä tietoyksiköitä ja kokonaisluvut toimivat indekseinä.

Käytettävien taulukkoindeksien määrä voi olla erilainen: yhden indeksin taulukoita kutsutaan yksiulotteisiksi, kahdella taulukoilla kaksiulotteisiksi ja niin edelleen. Yksiulotteinen taulukko - vastaa löyhästi matematiikan vektoria ; kaksiulotteinen ("rivi", "sarake") - matriisi . Yleisimmin käytetään taulukoita, joissa on yksi tai kaksi indeksiä; harvemmin - kolmella; vielä suurempi määrä indeksejä on erittäin harvinaista.

Taulukon ensimmäisellä elementillä voi ohjelmointikielestä riippuen olla eri indeksi. Tauluja on kolme päätyyppiä: nollapohjaiset ( nolla-pohjaiset ), yksipohjaiset ( yksipohjaiset ) ja ohjelmoijan antamaan tiettyyn arvoon perustuvat ( n-pohjaiset ). Nollasta laskeminen on tyypillisempi matalan tason ohjelmointikielille , vaikka sitä löytyy myös korkean tason kielistä, esimerkiksi sitä käytetään melkein kaikilla C-perheen kielillä. Useilla kielillä ( Pascal , Ada , Modula-2 ) indeksien alue voidaan määritellä minkä tahansa tietotyypin mielivaltaiseksi arvoalueeksi, joka voidaan lähettää kokonaisluvuksi, eli kokonaislukuja, symboleja, luetteloita, jopa booleans (jälkimmäisessä tapauksessa taulukossa on kaksi elementtiä, jotka on indeksoitu arvoilla "True" ja "False").

Esimerkki kiinteästä taulukosta Pascalissa {Yksiulotteinen kokonaislukutaulukko. Numerointielementit 1 - 15 } a : kokonaisluku [ 1 .. 15 ] ; {Kaksiulotteinen merkkijono. Sarakkeiden numerointi tavutyypin mukaan (0 - 255) riveillä 1 - 5} multiArray : array [ Byte , 1 .. 5 ] of Char ; {Yksiulotteinen merkkijonojoukko. Sanojen numerointi (0 - 65536)} rangeArray : jono [ Word ] of String ; Esimerkki kiinteästä taulukosta C:ssä int Array [ 10 ]; // Yksiulotteinen taulukko: kokonaislukuja, koko 10; // Elementtien numerointi - 0 - 9. double Array [ 12 ][ 15 ]; // Kaksiulotteinen taulukko: // kaksinkertaiset reaaliluvut, // koko 12 x 15; // Numerointi: rivien mukaan - 0 - 11, // sarakkeiden mukaan - 0 - 14.

Joissakin ohjelmointikielissä moniulotteiset taulukot luodaan yksiulotteisten taulukoiden pohjalta, joissa elementit ovat taulukoita [5] .

Esimerkki JavaScript 2D-taulukosta //Luo kaksiulotteinen numerotaulukko: var array = [ [ 11 , 12 , 13 , 14 , 15 , 16 ], // Ensimmäinen rivi on taulukko [ 21 , 22 , 23 , 24 , 25 , 26 ] , // Toinen [ 31 , 32 , 33 , 34 , 35 , 36 ] // Kolmas ]; // Tulostustaulukko konsoliin: array . forEach (( subArray ) => { // Jokaiselle alitaulukolle subArray . forEach (( item ) => { // jokaiselle sen elementille konsoli . log ( item ); // tulosta tämä elementti konsoliin. } ); });

Tuki indeksitaulukoille (oma ilmoitussyntaksi, elementtien kanssa työskentelyyn liittyvät toiminnot ja niin edelleen) löytyy useimmista korkean tason ohjelmointikielistä . Suurin sallittu taulukkoulottuvuus, indeksiarvojen tyypit ja alueet, elementtityyppien rajoitukset määräytyvät ohjelmointikielen tai tietyn kääntäjän mukaan .

Ohjelmointikielissä, joissa ohjelmoija voi ilmoittaa omat tyyppinsä , on yleensä mahdollista luoda "taulukko"-tyyppi. Tällaisen tyypin määrittelyssä määritellään kunkin indeksin tyypit ja/tai arvoalueet sekä taulukon elementtien tyyppi. Ilmoitettua tyyppiä voidaan myöhemmin käyttää muuttujien, muodollisten parametrien ja funktion palautusarvojen määrittämiseen. Jotkut kielet tukevat taulukkomuuttujien määritystoimintoja (kun yksi operaatio määrittää taulukon kaikki elementit toisen taulukon vastaavien elementtien arvoille).

Taulukkotyypin määritys Pascalissa tyyppi TArrayType = kokonaisluvun taulukko [ 0..9 ] ; _ _ _ (* Taulukot, joilla on seuraavat parametrit: 1. Koko - 10 solua; 2. Tallennukseen soveltuvien elementtien tyypit - - kokonaisluvut alueella [−32 768; 32 767], - ilmoitetaan operandityypillä nimeltä "TArrayType" . *) var arr1 , arr2 , arr3 : TArrayType ; (* Kolmen samantyyppisen taulukkomuuttujan ilmoitus (edellä oleva "TArrayType"). *)

APL - ohjelmointikielessä taulukko on päätietotyyppi (nollaulotteista taulukkoa kutsutaan skalaariksi, yksiulotteista taulukkoa kutsutaan vektoriksi ja kaksiulotteista taulukkoa kutsutaan matriisiksi) [3] . Matriisimäärityksen lisäksi tämä kieli tukee vektori- ja matriisiaritmeettisia operaatioita, joista kukin suoritetaan yhdellä komennolla, tiedonsiirtotoimintoja taulukoissa ja matriisirivien lajittelua.

Dynaamiset taulukot

Dynaamisia taulukoita kutsutaan taulukoiksi, joiden koko voi muuttua ohjelman suorituksen aikana. Tavallisia (ei-dynaamisia) taulukoita kutsutaan myös kiinteiksi tai staattisiksi .

Dynaamiset taulukot voidaan toteuttaa sekä ohjelmointikielen että järjestelmäkirjastojen tasolla. Toisessa tapauksessa dynaaminen taulukko on vakiokirjaston objekti, ja kaikki sen kanssa tehtävät toiminnot toteutetaan samassa kirjastossa. Tavalla tai toisella dynaamisten taulukoiden tuki edellyttää seuraavia ominaisuuksia:

Dynaamisen taulukon kuvaus. Kielitasolla tämä voi olla erityinen syntaktinen rakennelma, kirjastotasolla se voi olla kirjaston tietotyyppi, jonka arvo ilmoitetaan normaalisti. Yleensä kun kuvataan (luodaan) dynaamista taulukkoa, sen alkuperäinen koko määritetään, vaikka tämä ei ole välttämätöntä.
Dynaamisen taulukon nykyisen koon määrittäminen.
Dynaamisen taulukon koon muuttaminen.

Esimerkki rakenteista dynaamisten taulukoiden kanssa työskentelemiseen Delphissä :

var // Dynaamisten taulukoiden kuvaukset byteArray : Array of Byte ; // Yksiulotteinen taulukko multiArray : Array of Array of string ; // Moniulotteinen taulukko ... SetLength ( byteArray , 1 ) ; // Aseta taulukon kooksi 1 elementti. byteArray [ 0 ] := 16 ; // Kirjoituselementti. SetLength ( byteArray , Length ( byteArray ) + 1 ) ; // Kasvata taulukon kokoa yhdellä byteArray [ Length ( byteArray ) - 1 ] := 10 ; // Kirjoita arvo viimeiseen elementtiin. WriteLn ( byteArray [ pituus ( byteArray ) - 1 ]) ; // Näytä taulukon viimeinen elementti. ... SetLength ( multiArray , 20 , 30 ) ; // Aseta kaksiulotteisen taulukon koko multiArray [ 10 , 15 ] := 12 ; // Kirjoita arvo SetLength ( multiArray , 10 , 15 ) ; // Pienennä WriteLn:n kokoa ( pituus ( multiArray ) , ' ' , Length ( multiArray [ 0 ] )

Heterogeeniset taulukot

Heterogeeniseksi kutsutaan taulukkoa, jonka eri elementteihin voidaan kirjoittaa suoraan eri tietotyyppeihin liittyviä arvoja . Taulukko, joka tallentaa osoittimia eri tyyppisiin arvoihin, ei ole heterogeeninen, koska taulukkoon tosiasiallisesti tallennetut tiedot kuuluvat yhteen tyyppiin - "osoitin"-tyyppiin. Heterogeeniset taulukot ovat käteviä universaalina rakenteena mielivaltaisen tyyppisten tietojoukkojen tallentamiseen. Heterogeenisuuden toteutus edellyttää kielenkääntäjän taulukon tukimekanismin monimutkaisuutta.

Työskentely muistin kanssa

Tyypillinen tapa toteuttaa staattinen homogeeninen (samantyyppistä dataa tallentava) matriisi on allokoida jatkuva muistilohko, jonka tilavuus on , jossa on yhden elementin koko ja ovat indeksialueiden koot (eli arvojen määrä, jonka vastaava indeksi voi ottaa). Käytettäessä taulukon elementtiä indeksillä vastaavan elementin osoite lasketaan muodossa Osoitteenlaskentakaavan indeksien järjestys voi olla erilainen. (Tämä tapa vastaa toteutusta useimmissa C - kääntäjissä ; Fortranissa indeksijärjestys on päinvastainen [2] ). ${\displaystyle S\cdot m_{1}\cdot m_{2}\cdot \dots m_{n))$ $S$ $m_{1},\dots m_{n}$ $(i_{1},i_{2},\dots i_{n})$ $B+S\cdot \left(\left(\dots \left(i_{\text{1p}}m_{1}+i_{\text{2p}}\right)\cdot m_{2}+ \pisteet +i_{(n-1){\teksti{p}}}\oikea)\cdot m_{n-1}+i_{n{\teksti{p}}}\oikea)$ $B$ $i_{k\mathrm {p} }$ $k$

Siten tietyn indeksijoukon sisältävän elementin osoite lasketaan siten, että pääsyaika taulukon kaikille elementeille on teoreettisesti sama; Vastausviiveiden erilaiset arvot RAM-muistista eri muistielementeillä sijaitseviin soluihin voivat kuitenkin vaikuttaa, mutta korkean tason ohjelmoinnin käytännössä tällaiset hienoudet jätetään harvoin poikkeuksin huomiotta.

Tavallinen tapa toteuttaa heterogeeniset taulukot on tallentaa itse elementtien arvot erikseen ja sijoittaa osoittimet näihin elementteihin taulukon muistilohkoon (joka on järjestetty säännölliseksi homogeeniseksi taulukoksi, kuvattu yllä). Koska osoittimet minkä tahansa tyyppisiin arvoihin ovat yleensä samankokoisia, on mahdollista pitää osoitteen laskenta yksinkertaisena, vaikka elementtiarvojen varaamiseen ja käyttämiseen liittyy lisäkustannuksia.

Dynaamiset taulukot voivat käyttää samaa asettelumekanismia kuin staattiset taulukot, mutta lisämuistia on varattu laajentamista ja lisäämistä varten taulukon sisällön koon muuttamiseen ja siirtämiseen muistissa.

Myös dynaamiset ja heterogeeniset taulukot voidaan toteuttaa käyttämällä perustavanlaatuisia erilaisia menetelmiä arvojen tallentamiseen muistiin, esimerkiksi yksi- tai kaksinkertaisesti linkitetyillä listoilla. Tällaiset toteutukset voivat olla joustavampia, mutta vaativat yleensä lisäkustannuksia. Lisäksi ne eivät yleensä täytä jatkuvan elementin pääsyajan vaatimusta.

Muistiinpanot

↑ Drot V. L., Novikov F. A. "Nykyaikaisen tietokonesanaston selittävä sanakirja", taulukon mitat . Käyttöpäivä: 18. lokakuuta 2012. Arkistoitu alkuperäisestä 3. heinäkuuta 2013. (määrätön)
↑ 1 2 Bartejev, 2000 .
↑ 1 2 Magariu, 1983 .
↑ Wirth, 1989 , 1.6 Array.
↑ Michael McMillan. Tietorakenteet ja algoritmit JavaScriptillä (englanniksi) . - O'Reilly Media , 2014. - S. 30-32. — ISBN 978-1-4493-7396-2 .

Kirjallisuus

Wirth N. Algoritmit ja tietorakenteet = Algoritmit ja tietorakenne. - M .: Mir, 1989. - 360 s. — ISBN 5-03-001045-9 .
Magariu N.A. Ohjelmointikieli APL. - M . : "Radio ja viestintä", 1983. - 96 s.
Barteniev O. V. Moderni Fortran. - 3. painos, lisäys. ja tarkistettu .. - M . : Dialog-MEPhI, 2000. - 449 s.

Tietorakenteet
Luettelot	joukko yksittäin linkitetty lista kaksoislinkitetty lista Passilista
puut	B-puu Binäärihakupuu AVL puu Puna-musta puu pino
Laskee	Suunnattu graafi Suunnattu asyklinen graafi Binääripäätöskaavio Hypergraph
muu	Hash-taulukko Pino

Tietotyypit
Käsittämätön	Bitti Napostella Tavu qubit Kohdella Piirre Sana
Numeerinen	Koko kiinteä piste liukuluku Rationaalista Monimutkainen Pitkä intervalli
Teksti	Symbolinen merkkijono
Viite	Osoite Linkki Osoitin Kääre
Komposiitti	Algebrallinen tietotyyppi ( yleinen ) Luokka Tyyppituote ( Kirjoita Tuple rakenne ) Esine Konsolidointi ( tagged ) Järjestetty pari
abstrakti	joukko Lista Vuoro Pino Assosiatiivinen taulukko (näyttö, kartta ) Paljon multiset Tyyppi Kaavio
muu	Looginen Alempi Korkeampi Polymorfinen Toimiva lueteltava Kokoelma Poikkeus Suku ( metaluokka ) Monad Semafori Virtaus mitätön
liittyvät aiheet	Abstrakti tietotyyppi primitiivinen tyyppi Tietorakenne Yleinen tyyppinen muuttuja Käyttöliittymä Rakentaja (OOP) Rakentaja (FP) Tyyppi rakentaja Tyyppivalu Prototyyppi Tyyppijärjestelmä