Luettelo (tietokonetiede)

Tietojenkäsittelytieteessä lista ( englanniksi lista ) on abstrakti tietotyyppi , joka on järjestetty arvojoukko , jossa tietty arvo voi esiintyä useammin kuin kerran. Listan esiintymä on äärellisen sekvenssin matemaattisen käsitteen tietokonetoteutus . Luettelon arvojen esiintymiä kutsutaan luettelon elementeiksi ( englanniksi item, entry tai element ); jos arvo esiintyy useita kertoja, jokainen esiintyminen katsotaan erilliseksi elementiksi.   

Käsite lista viittaa myös useisiin erityisiin tietorakenteisiin , joita käytetään abstraktien listojen, erityisesti linkitettyjen listojen , toteutuksessa .

Määritelmä

Käyttämällä C. Hoaren syntaktisesti suuntautuneen rakennusmenetelmän merkintää listan määritelmä voidaan kirjoittaa seuraavasti:

Tämän määritelmän ensimmäinen rivi tarkoittaa, että tyypin elementtien luettelo (sanotaan: "luettelo yli ") on tyhjän listan ja tyypin atomin karteesisen tulon eroteltu liitto, jossa lista on yli . Listojen luomiseen käytetään kahta konstruktoria (määritelmän toinen rivi), joista ensimmäinen luo tyhjän luettelon ja toinen - ei-tyhjän luettelon. On aivan selvää, että toinen konstruktori vastaanottaa jonkin atomin ja listan parametreiksi syötteenä ja palauttaa listan, jonka ensimmäinen elementti on alkuperäinen atomi ja loput alkuperäisen listan elementtejä. Eli atomi on listan etuliitteenä, mikä on syy tällaiseen rakentajan nimeen. Tyhjä luettelo ei ole atomi, joten sitä ei voida liittää etuliitteeseen. Toisaalta tyhjä lista on nollaelementti listojen rakentamisessa, joten mikä tahansa lista sisältää tyhjän listan aivan lopussa - rakentaminen alkaa siitä.

Kolmas rivi määrittelee luettelon valitsimet , toisin sanoen toiminnot luettelon elementtien käyttämiseksi. Valitsija ottaa syötteeksi listan ja palauttaa tämän luettelon ensimmäisen elementin, eli tuloksen tyyppi on type . Tämä valitsin ei voi vastaanottaa tyhjää listaa syötteenä - tässä tapauksessa toiminnon tulos on määrittelemätön. Valitsin palauttaa syötteestä saadun listan pään (ensimmäinen elementti) katkaisemisen seurauksena. Tämä valitsin ei myöskään voi hyväksyä tyhjää listaa syötteeksi, koska tässä tapauksessa toiminnon tulos on määrittelemätön. Käyttämällä näitä kahta toimintoa voit saada minkä tahansa elementin luettelosta. Esimerkiksi saadaksesi luettelon kolmannen elementin (jos sellainen on), sinun on käytettävä valitsinta kahdesti peräkkäin ja sitten valitsin . Toisin sanoen, saadaksesi luettelon elementin, joka on paikallaan (alkaen ensimmäisestä elementistä, kuten ohjelmoinnissa on tapana), sinun on käytettävä valitsinta kerran ja sitten valitsinta .

Määritelmän neljäs rivi kuvaa listapredikaatteja eli funktioita, jotka palauttavat boolen arvon tietyistä ehdoista riippuen. Ensimmäinen predikaatti palauttaa arvon , jos annettu lista on tyhjä. Toinen predikaatti toimii käänteisesti. Lopuksi viides rivi kuvaa listan osia, jotka, kuten jo mainittiin, ovat tyhjät ja ei-tyhjät listat.

Ominaisuudet

Tällä tavalla määritellyllä tietorakenteella on joitain ominaisuuksia:

• Listan koko  on siinä olevien elementtien lukumäärä, pois lukien viimeinen "nolla"-elementti, joka on määritelmän mukaan tyhjä lista.
• Elementtien tyyppi  on sama kuin listan tyyppi; kaikkien luettelon elementtien on oltava tämän tyyppisiä.
• Lajiteltu  - lista voidaan lajitella joidenkin lajittelukriteerien mukaan (esim. nousevat kokonaislukuarvot, jos lista koostuu kokonaisluvuista).
• Helppokäyttöisyys  - Jotkin luettelot, toteutuksesta riippuen, voivat tarjota ohjelmoijalle valitsimia numeroitujen elementtien suoraa käyttöä varten.
• Vertailukelpoisuus  - listoja voidaan verrata keskenään vastaavuuden suhteen, ja toteutuksesta riippuen listavertailuoperaatiossa voidaan käyttää erilaisia ​​tekniikoita.

Listoja käytetään samantyyppisten elementtijoukkojen tallentamiseen. Tällaisia ​​elementtejä voidaan lajitella käytettäviksi hakutoiminnoissa tai funktioissa, joilla lisätään nopeasti uusia elementtejä luetteloon.

Luettelot ohjelmointikielillä

Toiminnalliset kielet

Toiminnallisten kielten luettelot ovat perusrakenne. Useimmissa toiminnallisissa kielissä on sisäänrakennetut toiminnot luetteloiden kanssa työskentelyä varten, kuten luettelon pituuden, pään (luettelon ensimmäinen elementti), hännän (luettelon ensimmäistä elementtiä seuraava osa) saaminen, funktion käyttäminen luettelon jokaiseen elementtiin ( Kartta ), luettelon taittaminen jne.