Tietorakenne

Perustietorakenteet

Array

Yksinkertaisin tietorakennetyyppi on lineaarinen joukko. Tunnetaan myös nimellä yksiulotteinen array. Joukkoon mahtuu useita samantyyppisiä arvoja (kokonaisluku, liukuluku, merkkijono jne.). Joukon sisällä olevien elementtien käyttäminen on hyvin nopeaa. Joukko on yleensä kiinteän kokoinen. Sen jälkeen, kun joukon koko on määritetty alussa, joukon kokoa ei välttämättä ole mahdollista kasvattaa ilman, että luodaan uusi suurempi joukko ja kopioidaan kaikki arvot uuteen joukkoon. Tietojenkäsittelytieteessä array-tietorakenne tai yksinkertaisesti array on tietorakenne, joka koostuu kokoelmasta elementtejä (arvoja tai muuttujia), jotka kukin tunnistetaan vähintään yhdellä array-indeksillä tai avaimella. Joukko tallennetaan siten, että kunkin elementin sijainti voidaan laskea sen indeksituplasta matemaattisella kaavalla.

Esimerkiksi 10 kokonaislukumuuttujan joukko, jonka indeksit ovat 0-9, voidaan tallentaa 10 sanana muistiosoitteisiin 2000, 2004, 2008, 2036 siten, että indeksillä i olevan elementin osoite on 2000 + 4 × i.

Koska matriisin matemaattinen käsite voidaan esittää kaksiulotteisena ruudukkona, kaksiulotteisia matriiseja kutsutaan joskus myös matriiseiksi. Joissakin tapauksissa laskennassa käytetään termiä "vektori" viittaamaan matriisiin, vaikka matemaattisesti oikeampi vastine on pikemminkin tuplat kuin vektorit. Joukkoja käytetään usein taulukoiden, erityisesti hakutaulukoiden, toteuttamiseen; sanaa taulukko käytetäänkin joskus joukon synonyyminä.

Asettelut ovat vanhimpia ja tärkeimpiä tietorakenteita, ja niitä käytetään lähes kaikissa ohjelmissa. Niitä voidaan käyttää myös monien muiden tietorakenteiden, kuten listojen ja merkkijonojen, toteuttamiseen. Ne hyödyntävät tehokkaasti tietokoneiden osoitelogiikkaa. Useimmissa nykyaikaisissa tietokoneissa ja monissa ulkoisissa tallennuslaitteissa muisti on yksiulotteinen joukko sanoja, joiden indeksit ovat niiden osoitteita. Prosessorit, erityisesti vektoriprosessorit, on usein optimoitu array-operaatioita varten.

Joukot ovat hyödyllisiä, koska elementtien indeksit voidaan laskea suoritusaikana. Muun muassa tämä ominaisuus mahdollistaa sen, että yhdellä iteratiivisella lausekkeella voidaan käsitellä mielivaltaisen monta matriisin elementtiä. Tästä syystä array-tietorakenteen elementtien on oltava samankokoisia ja niiden on käytettävä samaa datan esitystapaa. Kelvollisten indeksituplien joukko ja elementtien osoitteet (ja siten elementtien osoitekaava) ovat yleensä, mutta eivät aina, kiinteitä, kun joukko on käytössä.

Termiä array käytetään usein tarkoittamaan array-tietotyyppiä, joka on useimpien korkean tason ohjelmointikielten tarjoama tietotyyppi, joka koostuu arvojen tai muuttujien kokoelmasta, joka voidaan valita yhden tai useamman ajonaikaisen indeksin avulla. Array-tyypit toteutetaan usein array-rakenteilla; joissakin kielissä ne voidaan kuitenkin toteuttaa hash-taulukoilla, linkitetyillä listoilla, hakupuilla tai muilla tietorakenteilla.

Linkitetty luettelo

Linkitetty tietorakenne on joukko tietoja, jotka on linkitetty toisiinsa viittauksilla. Tietoja kutsutaan usein solmuiksi. Viittauksia kutsutaan usein linkeiksi tai osoittimiksi. Jatkossa näistä käsitteistä käytetään sanoja solmu ja osoitin.

Linkitetyissä tietorakenteissa osoittimia vain poistetaan tai verrataan yhdenvertaisuuden osalta. Näin ollen linkitetyt tietorakenteet ovat erilaisia kuin taulukot, jotka vaativat osoittimien lisäämistä ja vähentämistä.

Linkitetyt luettelot, hakupuut ja lausekepuut ovat kaikki linkitettyjä tietorakenteita. Ne ovat myös tärkeitä algoritmeissa, kuten topologisessa lajittelussa ja joukkojen yhdistämisessä.

Pino

Pino on perustietorakenne, joka voidaan ajatella loogisesti lineaarisena rakenteena, jota edustaa todellinen fyysinen pino tai kasa, rakenne, jossa kohteiden lisääminen ja poistaminen tapahtuu pinon yläpäässä. Peruskonseptia voidaan havainnollistaa ajattelemalla tietokokonaisuutta lautas- tai kirjapinona, josta voi poistaa asioita vain pinon ylimmän kohteen avulla. Tätä rakennetta käytetään kaikkialla ohjelmoinnissa.

Pinon perustoteutusta kutsutaan myös "Last In First Out" -rakenteeksi, mutta pinototeutuksista on olemassa erilaisia variaatioita.

Pinoille voidaan suorittaa periaatteessa kolme toimintoa. Ne ovat:

• kohteen lisääminen ("työntäminen") pinoon
• kohteen poistaminen ("popping") pinosta.
• pinon ylimmän kohteen sisällön näyttäminen ("kurkistus").

Jono

Jono on abstrakti tietotyyppi tai lineaarinen tietorakenne, jossa ensimmäinen elementti lisätään toisesta päästä ("häntä") ja olemassa oleva elementti poistetaan toisesta päästä ("pää"). Jono on "First In First Out" -rakenne. "First In First Out" tarkoittaa sitä, että elementit, jotka laitetaan jonoon ensimmäisenä, tulevat ulos ensimmäisenä, ja elementit, jotka laitetaan jonoon viimeisenä, tulevat ulos viimeisenä. Esimerkki jonosta ovat jonot, joissa ihmiset odottavat. Jonon ensimmäinen henkilö menee ensimmäisenä ja viimeinen henkilö viimeisenä.

Elementin lisäämistä jonoon kutsutaan "jonoon asettamiseksi" ja elementin poistamista jonosta kutsutaan "jonosta poistamiseksi".

Kaavio

Graafi on abstrakti tietotyyppi, jonka tarkoituksena on toteuttaa matematiikan graafi- ja hypergraafikäsitteet.

Graafin tietorakenne koostuu äärellisestä (ja mahdollisesti muuttuvasta) joukosta järjestettyjä pareja, joita kutsutaan reunoiksi tai kaariksi, ja jotka muodostuvat tietyistä solmuiksi tai kärkipisteiksi kutsutuista yksiköistä. Kuten matematiikassa, reunan (x,y) sanotaan osoittavan tai kulkevan x:stä y:hen. Solmut voivat olla osa graafirakennetta tai ulkoisia kokonaisuuksia, joita edustavat kokonaislukuindeksit tai viittaukset. Graafin tietorakenne voi myös liittää kuhunkin reunaan jonkin reunan arvon, kuten symbolisen merkinnän tai numeerisen ominaisuuden.

Puu

Puu on yksi tehokkaimmista kehittyneistä tietorakenteista. Se esiintyy usein edistyneissä aiheissa, kuten tekoälyssä ja suunnittelussa. Yllättäen puu on tärkeä paljon yksinkertaisemmassa sovelluksessa - tehokkaan indeksin pitämisessä.

Kun käytetään puuta, on suuri todennäköisyys, että käytetään indeksiä. Yksinkertaisin indeksityyppi on avainkenttien lajiteltu luettelo. Puulla on yleensä määritelty rakenne. Kun kyseessä on binääripuu, voit käyttää binäärihakua minkä tahansa kohteen paikantamiseen ilman, että sinun tarvitsee tarkastella jokaista kohdetta.

Puutietotyyppi on eräänlainen graafi, mikä tarkoittaa, että monet algoritmit, jotka on tehty graafin läpikäymiseen, toimivat myös puun kanssa. Algoritmit voivat kuitenkin olla hyvin samankaltaisia, ja niillä on oltava oma aloitussolmu, eli solmu, johon ei ole linkkejä muista solmuista.

Yksinkertaisen järjestetyn luettelon ongelma ilmenee, kun alat lisätä uusia kohteita ja sinun on pidettävä luettelo lajiteltuna - se voidaan tehdä kohtuullisen tehokkaasti, mutta se vaatii joitakin muutoksia. Lisäksi lineaarista indeksiä ei ole helppo jakaa, koska koko indeksi on "lukittava", kun yksi käyttäjä muokkaa sitä, kun taas puun yksi "haara" voidaan lukita, jolloin muut käyttäjät voivat muokata muita haaroja (koska niihin ei voi vaikuttaa).

Hash-taulukko

Hash-taulukko on joukko, jossa jokainen indeksi osoittaa linkitettyyn listaan, joka perustuu hash-arvoon. Hash-arvo on arvo, jonka määrittää hash-funktio. Hash-funktio määrittää yksilöllisen arvon tallennettavien tietojen perusteella. Tämä mahdollistaa tietojen käytön jatkuvasti, koska tietokone tietää aina, mistä etsiä.

Jokainen solmu osoittaa toiseen solmuun.