Tietorakenne

Tietorakenne on ohjelmistoyksikkö, jonka avulla  voit tallentaa ja käsitellä samantyyppisiä ja/tai loogisesti liittyviä tietoja . Tietojen lisäämistä, etsimistä, muuttamista ja poistamista varten tietorakenne tarjoaa tietyn joukon toimintoja, jotka muodostavat sen käyttöliittymän.

Termillä "tietorakenne" voi olla useita läheisiä, mutta kuitenkin erilaisia ​​merkityksiä [1] :

• Abstrakti tietotyyppi ;
• Jonkin abstraktin tietotyypin toteutus;
• Tietotyypin esiintymä, kuten tietty luettelo ;
• Toiminnallisen ohjelmoinnin yhteydessä - uniikki yksikkö ( eng.  yksilöllinen identiteetti ), joka säilyy muutosten aikana. Sitä kutsutaan epävirallisesti yhdeksi tietorakenteeksi huolimatta mahdollisista eri versioista.

Tietorakenteet muodostetaan käyttämällä tietotyyppejä , viittauksia ja niihin liittyviä operaatioita valitulla ohjelmointikielellä .

Erilaiset tietorakenteet sopivat erilaisiin sovelluksiin; Jotkut heistä ovat erikoistuneet tiettyihin tehtäviin. Esimerkiksi B-puut sopivat yleensä tietokantojen luomiseen , kun taas hash-taulukoita käytetään kaikkialla erilaisten sanakirjojen luomiseen, esimerkiksi verkkotunnusten yhdistämiseen tietokoneiden Internet-osoitteisiin .

Ohjelmistokehityksessä toteutuksen monimutkaisuus ja ohjelmien työn laatu riippuvat merkittävästi tietorakenteiden oikeasta valinnasta. Tämä ymmärrys johti muodollisiin kehitysmenetelmiin ja ohjelmointikieliin, jotka asettivat tietorakenteet, eivät algoritmit, ohjelmistoarkkitehtuurin eturintamaan. Useimmissa näistä kielistä on jonkinlainen modulaarisuus , jonka avulla tietorakenteita voidaan käyttää turvallisesti uudelleen eri sovelluksissa. Oliopohjaiset kielet , kuten Java , C# ja C++ , ovat esimerkkejä tästä lähestymistavasta.

Monet klassiset tietorakenteet tarjotaan ohjelmointikielten vakiokirjastoissa tai suoraan ohjelmointikieliin. Esimerkiksi hash-taulukon tietorakenne on sisäänrakennettu ohjelmointikieliin Lua , Perl , Python , Ruby , Tcl jne. C++- standardimallikirjasto (STL) on laajalti käytössä.

Useimpien tietorakenteiden perustavanlaatuisia rakennuspalikoita ovat taulukot , tietueet ( Cstruct : ssä ja Pascalissa ), erotetut liitot ( C : ssä) ja viittaukset . Esimerkiksi kaksoislinkitetty lista voidaan rakentaa käyttämällä merkintöjä ja linkkejä, joissa jokainen merkintä (solmu) tallentaa tiedot ja linkit "vasemmalle" ja "oikealle" solmulle. recordunion

Tietorakenteiden vertailu toiminnallisessa ja pakottavassa ohjelmoinnissa

Tietorakenteiden suunnittelu toiminnallisille kielille on vaikeampaa kuin pakollisille kielille ainakin kahdesta syystä [1] :

1. Melkein kaikki tietorakenteet käyttävät paljon tehtävää , jota ei käytetä puhtaasti toiminnallisessa tyylissä;
2. Toiminnalliset tietorakenteet ovat joustavampia, joten jos pakollisessa ohjelmoinnissa vanha versio katoaa yksinkertaisesti korvaamalla se uudella, toiminnallisessa ohjelmoinnissa se pysyy automaattisesti olemassa. Toisin sanoen pakollisessa ohjelmoinnissa (jos et ryhdy erityistoimenpiteisiin, jotka voivat vakavasti monimutkaista ohjelmaa) tietorakenteet ovat lyhytaikaisia ​​( englanniksi  efemeral ), ja toiminnallisissa ohjelmissa ne ovat yleensä vakioita ( englanniksi  persistent ).

Muistiinpanot

1. ↑ 12 Okasaki , 1998 , s. 3-4.

Kirjallisuus

• Alfred W. Aho, John Hopcroft , Jeffrey D. Ullman. Tietorakenteet ja algoritmit = Data Structures and Algorithms. - M .: Williams , 2000. - 384 s. — ISBN 0-201-00023-7 .
• Michael Main, Walter Savitch. Tietorakenteet ja muut objektit C++:lla. - 2. painos - M .: Williams , 2002. - 832 s. — ISBN 0-201-70297-5 .
• Chris Okasaki. Puhtaasti toiminnalliset tietorakenteet. - Cambridge University Press, 1998. - 232 s. - ISBN 978-0521663502 .

Linkit

• Tietorakenteet ja hajautus