Välttämätön edellytys tietojen tallentamiselle tietokoneen muistiin on kyky muuntaa nämä tiedot tietokoneelle sopivaan muotoon. Jos tämä ehto täyttyy, on tarpeen määrittää rakenne, joka sopii erityisesti olemassa olevalle tiedolle, joka tarjoaa tarvittavat ominaisuudet sen kanssa työskentelyyn.

Soittolista

Rakenne ymmärretään tässä tapana esittää tietoa, jonka kautta joukko yksittäisiä elementtejä muodostaa jotain yhtenäistä, jonka määrää niiden välinen suhde. Tiettyjen sääntöjen mukaan järjestettynä ja loogisesti toisiinsa yhdistettynä dataa voidaan käsitellä erittäin tehokkaasti, koska niille yhteinen rakenne tarjoaa joukon mahdollisuuksia niiden hallintaan - yksi syy siihen, että tiettyjen ongelmien ratkaisemisessa saavutetaan korkeita tuloksia.

Mutta jokaista objektia ei esitetä mielivaltaisessa muodossa, ja ehkä sille on vain yksi tulkintamenetelmä, joten kaikkien olemassa olevien tietorakenteiden tuntemus on ohjelmoijalle kiistaton etu. Siksi sinun on usein tehtävä valinta erilaisten tietojen tallennusmenetelmien välillä, ja tuotteen suorituskyky riippuu tästä valinnasta.

Kun puhutaan ei-tietokonetekniikasta, ei ole mahdollista näyttää yhtään tapausta, jossa tiedolla on ilmeinen rakenne. Hyvä esimerkki ovat kirjat, joiden sisältö on erilaista. Ne on jaettu sivuihin, kappaleisiin ja lukuihin, ja niissä on yleensä sisällysluettelo eli käyttöliittymä. Laajassa mielessä jokaisella elävällä olennolla on rakenne ilman sitä, orgaanista ainetta tuskin olisi olemassa.

Lukija on todennäköisesti kohdannut tietorakenteita suoraan tietojenkäsittelytieteessä, esimerkiksi ohjelmointikieleen sisäänrakennettuja. Näitä kutsutaan usein tietotyypeiksi. Näitä ovat: taulukot, numerot, merkkijonot, tiedostot jne.

Tiedontallennusmenetelmiä, joita kutsutaan "yksinkertaisiksi" eli jakamattomiksi osiin, on parempi tutkia yhdessä tietyn ohjelmointikielen kanssa tai syventää niiden työn olemusta. Siksi tässä tarkastellaan vain "integroituja" rakenteita, jotka koostuvat yksinkertaisista, nimittäin: taulukot, luettelot, puut ja kaaviot.

Taulukot.

Taulukko on tietorakenne, jossa on kiinteä ja järjestetty joukko samanlaisia ​​elementtejä (komponentteja). Pääsy mihin tahansa taulukon elementtiin tapahtuu tämän elementin nimellä ja numerolla (indeksillä). Indeksien määrä määrittää taulukon koon. Useimmiten löytyy esimerkiksi yksiulotteisia (vektorit) ja kaksiulotteisia (matriisit) taulukoita.

Edellisellä on yksi indeksi, jälkimmäisellä kaksi. Olkoon yksiulotteinen taulukko nimeltään A, jolloin päästäksesi käsiksi sen i:nnen elementin tulee määrittää taulukon nimi ja tarvittavan elementin numero: A[i]. Kun A on matriisi, se esitetään taulukon muodossa, jonka elementteihin pääsee käsiksi taulukon nimellä sekä rivi- ja sarakenumeroilla, joiden leikkauskohdassa elementti sijaitsee: A, jossa i on rivin numero, j on sarakkeen numero.

Taulujen kanssa työskentely voi vaihdella jollain tavalla eri ohjelmointikielissä, mutta perusperiaatteet ovat yleensä samat kaikkialla. Pascal-kielessä pääsy yksi- ja kaksiulotteiseen taulukkoon tapahtuu täsmälleen kuten yllä on esitetty, ja esimerkiksi C++:ssa kaksiulotteinen taulukko tulisi määrittää seuraavasti: A[i][j]. Taulukon elementit on numeroitu peräkkäin. Ohjelmointikieli vaikuttaa arvoon, josta numerointi alkaa. Useimmiten tämä arvo on 0 tai 1.

Kuvatun tyyppisiä taulukoita kutsutaan staattisiksi, mutta on myös taulukoita, jotka eroavat niistä tietyllä tavalla: dynaamisia ja heterogeenisia. Edellisen dynaamiselle on ominaista muuttuva koko, eli ohjelman suorittaessa dynaamisen taulukon koko voi muuttua. Tämä toiminto tekee tietojen kanssa työskentelystä joustavampaa, mutta samalla joudut uhraamaan suorituskyvyn ja itse prosessista tulee monimutkaisempi.

Pakollinen kriteeri staattiselle taulukolle, kuten sanottiin, on siihen samanaikaisesti tallennettujen tietojen homogeenisuus. Jos tämä ehto ei täyty, taulukko on heterogeeninen. Sen käyttö johtuu edellisessä muodossa olevista haitoista, mutta se on monissa tapauksissa perusteltua.

Näin ollen, vaikka olisit päättänyt rakenteen ja valinnut taulukon sellaisenaan, tämä ei silti riitä. Onhan matriisi vain yleinen nimitys, suku tietylle määrälle mahdollisia toteutuksia. Siksi on tarpeen päättää tietystä esitysmenetelmästä sopivimman taulukon kanssa.

Luettelot.

Lista on abstrakti tietotyyppi, joka toteuttaa järjestetyn arvojoukon. Listat eroavat taulukoista siinä, että niiden elementtejä käytetään peräkkäin, kun taas taulukot ovat hajasaantitietorakenteita. Tällä abstraktilla tyypillä on useita toteutuksia tietorakenteiden muodossa. Joitakin niistä käsitellään täällä.

Lista (linkitetty lista) on tietorakenne, joka on rajallinen joukko järjestettyjä elementtejä, jotka on kytketty toisiinsa osoittimien avulla. Jokainen rakenteen elementti sisältää kentän, jossa on tietoa, sekä osoittimen seuraavaan elementtiin. Toisin kuin taulukossa, luettelon elementteihin ei ole satunnaista pääsyä.

Yksittäin linkitetty lista

Yllä olevassa erikseen linkitetyssä luettelossa alkuperäinen elementti on Head-lista (mielivaltainen nimi) ja kaikkea muuta kutsutaan häntäksi. Listan loppu koostuu elementeistä, jotka on jaettu kahteen osaan: tiedotus (tietokenttä) ja indeksinen (seuraava kenttä). Viimeinen elementti sisältää osoittimen sijasta listan päätteen - nolla.

Yksittäin linkitetty lista ei ole kovin kätevä, koska yhdestä pisteestä on mahdollista päästä vain seuraavaan pisteeseen ja siten siirtyä loppuun. Kun seuraavaan elementtiin osoittavan osoittimen lisäksi on myös osoitin edelliseen, tällaista luetteloa kutsutaan kaksoislinkitetyksi.

Kaksoislinkitetty lista

Mahdollisuus liikkua sekä eteen- että taaksepäin on hyödyllinen joissakin toiminnoissa, mutta lisäosoittimet vaativat enemmän muistia kuin vastaavassa erikseen linkitetyssä luettelossa tarvitaan.

Edellä kuvatuille kahdelle luettelotyypille on alatyyppi, jota kutsutaan pyöreäksi listaksi. Voit tehdä pyöreän luettelon erikseen linkitetystä luettelosta lisäämällä vain yhden osoittimen viimeiseen elementtiin, jotta se viittaa ensimmäiseen. Ja kaksoisliitetylle elementille tarvitaan kaksi osoitinta: ensimmäiseen ja viimeiseen elementtiin.

Soittolista

Tarkasteltavien luettelorakennetyyppien lisäksi on olemassa muita tapoja järjestää tietoja käyttämällä "lista"-tyyppiä, mutta ne ovat pääsääntöisesti samankaltaisia ​​kuin käsitellyt, joten ne jätetään tässä pois.

Yhteyksien erojen lisäksi listat on jaettu datan työskentelymenetelmien mukaan. Joitakin näistä menetelmistä käsitellään alla.

Pino.

Pino

Pinolle on tunnusomaista, että sen elementteihin pääsee käsiksi vain yhdestä päästä, eli pinon huipulta, eli pino on tietorakenne, joka toimii LIFO-periaatteella (last in - first out). On parempi kuvata tämä tietorakenne pystysuoran luettelon muodossa, esimerkiksi pinona joitain asioita, joissa yhden niistä käyttämiseksi sinun on nostettava kaikki sen yläpuolella olevat asiat, ja voit laittaa vain pinon päällä oleva kohde.

Esitetyssä erikseen linkitetyssä luettelossa elementtien toiminnot tapahtuvat tiukasti toisessa päässä: halutun elementin sisällyttämiseksi viidenteen soluun on välttämätöntä sulkea pois elementti, joka sijaitsee tässä paikassa. Jos elementtejä oli esimerkiksi 6 ja viidenteen soluun olisi myös lisättävä tietty elementti, kaksi elementtiä olisi jätettävä pois.

Jonottaa.

Queue-tietorakenteessa käytetään FIFO-organisaatioperiaatetta (First In, First Out). Tämä menetelmä on tietyssä mielessä oikeudenmukaisempi kuin pinon toiminta, koska eri myymälöiden ja sairaaloiden tavanomaisten jonojen taustalla olevaa yksinkertaista sääntöä pidetään melko oikeudenmukaisena, ja juuri tämä on tämän rakenteen perusta. Olkoon tämä havainto esimerkkinä. Tarkkaan ottaen jono on lista, jossa elementtejä voidaan lisätä vain loppuun ja ne voidaan hakea toiselta puolelta, jota kutsutaan listan alusta.

Jonottaa

joulukuuta

Deque (double ended queue) on pino, jossa on kaksi päätä. Tietystä käännöksestä huolimatta pakki voidaan määritellä paitsi kaksisuuntaiseksi jonoksi, myös pinoksi, jolla on kaksi päätä. Tämä tarkoittaa, että tämäntyyppinen luettelo sallii elementtien lisäämisen alkuun ja loppuun, ja sama pätee hakutoimintoon.

joulukuuta

Tämä rakenne toimii samanaikaisesti kahdella tavalla järjestää dataa: FIFO ja LIFO. Siksi se voidaan luokitella erilliseksi ohjelmayksiköksi, joka saadaan summaamalla kaksi edellistä luettelotyyppiä.

Kaaviot.

Diskreetin matematiikan haaraa, joka käsittelee graafien tutkimusta, kutsutaan graafiteoriaksi. Graafiteoria tutkii yksityiskohtaisesti näiden matemaattisten objektien tunnettuja käsitteitä, ominaisuuksia, esitystapoja ja sovellusalueita. Olemme kiinnostuneita vain niistä seikoista, jotka ovat tärkeitä ohjelmoinnin kannalta.

Kaavio on kokoelma pisteitä, jotka on yhdistetty viivoilla. Pisteitä kutsutaan pisteiksi (solmuiksi) ja viivoja kutsutaan reunoiksi (kaareiksi).

Kuten kuvasta näkyy, kaavioita on kahta päätyyppiä: suunnatut ja suuntaamattomat. Ensimmäisessä reunat on suunnattu, eli kahden yhdistetyn kärjen välillä on vain yksi suunta, esimerkiksi kärjestä 1 voidaan siirtyä kärkeen 2, mutta ei päinvastoin. Suuntaamattomassa yhdistetyssä graafissa voit siirtyä jokaisesta kärjestä kuhunkin ja takaisin. Näiden kahden tyypin erikoistapaus on sekakaavio. Sille on ominaista sekä suunnattujen että suuntaamattomien reunojen läsnäolo.

Huippupisteen sisäaste on siihen tulevien reunojen määrä, ulkoaste on lähtevien reunojen lukumäärä.

Graafin reunojen ei tarvitse olla suoria, ja kärjet on merkitty tarkasti numeroilla, kuten kuvassa näkyy. Lisäksi on kaavioita, joiden reunoilla on tietty arvo, niitä kutsutaan painotetuiksi graafiksi, ja tämä arvo on reunan paino. Kun reunan molemmat päät yhtyvät, eli reuna lähtee ja tulee kärkeen F, niin tällaista reunaa kutsutaan silmukaksi.

Graafeja käytetään laajalti ihmisen luomissa rakenteissa, esimerkiksi tietokone- ja liikenneverkoissa sekä verkkoteknologioissa. Erityiset esitystavat mahdollistavat graafin käytön tietojenkäsittelytieteessä (tietokoneissa). Tunnetuimmat niistä: "Naapurimatriisi", "Incident Matrix", "Adjacency List", "Edge List". Kaksi ensimmäistä, kuten nimestä voi päätellä, käyttävät matriisia kuvaamaan kaaviota ja kaksi viimeistä listaa.

puut.

Järjestämätön puu

Puu matemaattisena esineenä on abstraktio luonnossa esiintyvistä homonyymisistä yksiköistä. Luonnollisten puiden rakenteen samankaltaisuus tietyntyyppisten kaavioiden kanssa osoittaa niiden välisen analogian oletuksen. Nimittäin yhdistetyillä ja samalla asyklisillä (ilman syklejä) kuvaajilla. Jälkimmäiset muistuttavat rakenteeltaan todella puita, mutta joissain tapauksissa on eroja, esimerkiksi matemaattisia puita on tapana kuvata juurilla, eli kaikki oksat "kasvavat" ylhäältä alas. Tiedetään, että luonnossa näin ei ole ollenkaan.

Koska puu on pohjimmiltaan graafi, monet sen määritelmistä vastaavat jälkimmäistä tai ovat intuitiivisesti samanlaisia. Puurakenteen juurisolmu (vertex 6) on siis ainoa kärkipiste (solmu), jolle on tunnusomaista esi-isten poissaolo, eli sellainen, ettei siihen viittaa mikään muu kärki, ja juurisolmusta itsestään pääset mihin tahansa olemassa olevista vertices -puu, mikä seuraa tämän rakenteen liitettävyysominaisuudesta. Solmuja, jotka eivät viittaa muihin solmuihin, toisin sanoen joilla ei ole lapsia, kutsutaan lehtiksi (2, 3, 9) tai päätesolmuiksi. Juurisolmun ja lehtien välissä sijaitsevat elementit ovat välisolmuja (1, 1, 7, 8). Jokaisella puusolmulla on vain yksi esi-isä, tai jos se on juurisolmu, sillä ei ole yhtään.

Alipuu on osa puuta, joka sisältää juurisolmun ja kaikki sen jälkeläiset solmut. Joten esimerkiksi kuvassa yksi alipuista sisältää juuren 8 ja elementit 2, 1, 9.

Voit suorittaa puulle monia toimintoja, kuten etsiä elementtejä, poistaa elementtejä ja alipuita, lisätä alipuita, löytää juurisolmuja joillekin pisteille jne. Yksi tärkeimmistä toiminnoista on puun läpikulku. Kiertomenetelmiä on useita. Suosituimmat niistä ovat: symmetrinen, suora ja käänteinen ohitus. Eteenpäin kuljetettaessa esi-isolmuissa käydään ennen niiden jälkeläisiä, ja käänteisessä liikenteessä tilanne käännetään vastaavasti. Symmetrisessä läpikulkussa pääpuun alipuita tarkastellaan vuorotellen.

Tietojen esittäminen tarkasteltavassa rakenteessa on hyödyllistä, jos tiedoilla on selkeä hierarkia. Esimerkiksi biologisia sukuja ja lajeja, työnimikkeitä, maantieteellisiä kohteita jne. koskevien tietojen käsittely edellyttää hierarkkisesti ilmaistua rakennetta, kuten matemaattisia puita.

TIETOTYYPIT JA RAKENTEET

Ohjeet tieteenalalle "Algoritmit ja tietorakenteet"

Kokoanut O.L. Chagaeva

Valmisteli liittovaltion koulutuslaitoksen UrFU:n ohjelmistotyökalujen ja järjestelmien osasto

Johdanto

IN Ympäröivässä maailmassa on valtava valikoima esineitä, esineitä, ilmiöitä, prosesseja, jotka näkyvät tiedon kautta.

Jokaisella tiedon edustamalla kokonaisuudella (objektilla, ilmiöllä) on joukko sille ominaisia ​​ominaisuuksia (piirteitä, merkkejä, parametreja, ominaisuuksia, momentteja). Esimerkiksi materiaalin ominaisuuksia ovat sen paino, mitat, laatu, hinta, tuotenumero jne. Ominaisuudet-merkit, jotka luonnehtivat tällaista kokonaisuutta hankintaorganisaatioksi ovat nimi, osasto, osoite, käyttötilin numero valtionpankissa jne.

Fyysisen kokonaisuuden ominaisuudet näytetään muuttujilla, jotka ovat tiedon alkeisyksiköitä ja joita kutsutaan yksityiskohdiksi.

Tuki on minkä tahansa monimutkaisen tietojoukon loogisesti jakamaton elementti, joka korreloi informaation näyttämän kohteen tai prosessin tietyn ominaisuuden kanssa.

IN käsitellystä tiedosta yksityiskohdat esitetään ikään kuin "atomeina", joista kootaan kaikki muut, monimutkaisemmat tiedonmuodostusrakenteet. Ja päinvastoin, minkä tahansa monimutkaisen tiedon yksiköt voidaan jakaa peräkkäin niiden muodostaviksi komponenteiksi, ja ne voidaan lopulta jakaa sellaisiksi komponenteiksi - muuttuviksi suureiksi, joita ei voida jakaa loogisesti. Tällaiset peruskomponentit ovat yksityiskohtia.

Muita kirjallisuudessa usein esiintyviä rekvisiitta synonyymejä ovat elementti, kenttä, termi, attribuutti iattribuutti.

Jokaisella rekvisiitillä on nimi. Kompaktikirjoitusta varten algoritmisoitaessa ja ohjelmoitaessa käytetään useimmiten lyhenteitä tunnisteiden nimet, erityisillä toteutuksilla, jotka tyypillisesti rajoittavat niiden pituutta, aakkostoa ja laajuutta. Joissain tapauksissa on myös sallittua käyttää synonyymejä tietojen nimissä, mukaan lukien sellaiset täydet nimet, joita käytetään vain ulkoisissa asiakirjoissa, esimerkiksi raporttisarakkeiden otsikoina.

Jokainen attribuutti on luontainen tiettyyn rajalliseen arvojoukkoon, joka riippuu kohteen (ilmiön) ominaisuuden ominaisuuksista, joita tämä attribuutti näyttää. Tätä joukkoa kutsutaan arvoluokiksi, joista yksi on esimerkiksi parametrille "potilaan lämpötila" ja toinen attribuutille "potilaan sukupuoli".

Attribuutin arvo on siten kullakin tietyllä ajanhetkellä yksi tämän attribuutin arvoluokan paikoista, joka odotetusti heijastaa ominaisuuden vastaavaa tilaa (tilajoukosta). objekti (ilmiö), joka luonnehtii attribuuttia. Näin ollen "potilaan lämpötila" -muuttujan nykyinen arvo voi olla 37,4° ja "potilaan sukupuoli" -muuttuja voi olla "mies". Toisin sanoen attribuutin arvoa käytetään edustamaan vastaavan entiteettiominaisuuden arvoa.

Attribuutteja on useita sen mukaan, minkä tyyppisiä arvoja niillä voi olla. Yleisimmät rekvisiittatyypit ovat kuitenkin numeerinen ja teksti.

Numeerisen tyypin yksityiskohdat kuvaavat luonnollisten yksiköiden laskemisen, mittauksen, punnituksen, muihin kvantitatiivisiin summatietoihin perustuvien laskelmien jne. tuloksena saatujen entiteettien kvantitatiivisia ominaisuuksia. Siksi tällaisten yksityiskohtien arvot ovat lukuja kaikilla niiden ominaisuuksilla ominaisuuksia ja ominaisuuksia.

Tietyissä esityksissä esiintyy usean tyyppisiä numeerisia määriä riippuen numeroluokista, numerojärjestelmästä, desimaalipisteen kiinnityksestä, pakkauksesta ja muista; rajoituksia asetetaan numeroalueille, niiden esitysmuodoille tulo/lähtöön ja erilaisille medioille, jopa saman toteutuksen sisällä. Koska kaikkia numeerisia attribuutteja käytetään aktiivisesti erilaisissa aritmeettisissa operaatioissa ja suurin osa niistä syntyy yleensä tällaisten operaatioiden tuloksena, on aina pidettävä mielessä esitetyt erot ja rajoitukset sekä tarve sopivalle muunnoslaitteistolle.

Tekstityyppiset yksityiskohdat ilmaisevat pääsääntöisesti kokonaisuuksien laadullisia ominaisuuksia ja kuvaavat olosuhteita, joissa tutkittava prosessi tapahtui ja tiettyjä tai

muita numeerisia arvoja. Siksi tällaisia ​​yksityiskohtia kutsutaan attribuuteiksi.

Ominaisuusarvot ovat merkkijonoja (kirjaimet, numerot, erilaiset merkit ja erikoismerkit), joita kutsutaan merkkijonoiksi tai tekstiksi.

Tietyn tietojärjestelmän kaikkien mahdollisten pareittain erotettavissa olevien symbolien täydellinen sarja muodostaa sen aakkoset riippuen tehtävien luonteesta, käytetyistä tietojenkäsittelyn teknisistä keinoista ja muista tekijöistä. Lisäksi käsittelyn eri vaiheissa ja jopa saman laskentajärjestelmän sisällä on mahdollista käyttää erilaisia ​​aakkosia.

Aakkosten koko (eri symbolien määrä, jotka voivat olla yhdessä arvon numerossa) ja sen koostumus (joukko) liittyvät suoraan seuraavien ongelmien ratkaisemiseen:

koodaus ja salauksen purku,

tietoyksiköiden arvojen kompakti tallennus,

tietojen tehokas tallennus, niiden hakujen nopeuttaminen, siirto, tietokoneisiin syöttäminen,

tietojen vastaanottaminen koneista kulutusta varten sopivimmassa muodossa,

vähentää kaikenlaisten uudelleenkirjoitusten kustannuksia.

Siksi aakkosten valinnalle annetaan suuri merkitys.

Tietojen käyttämiseksi algoritmisoinnissa ja ohjelmoinnissa on erittäin suuri merkitys sellaisille käsitteille kuin tiedon tyyppi ja rakenne.

1. TIETOTYYPIT

Tietokoneen laskentaprosessi toteutetaan tunnetusti ohjelmien ja tietojen avulla. Ohjelma itsessään viittaa myös dataan. Siksi voidaan sanoa, että data kuvaa mitä tahansa tietoa, jonka kanssa tietokone voi toimia. Tässä tapauksessa tiedolla tarkoitetaan mitä tahansa faktaa ja tietoa todellisen maailman objekteista, prosesseista ja niiden välisistä suhteista ja yhteyksistä. Kaikille tiedoille on ominaista joukko attribuutteja (ominaisuuksia, yksityiskohtia), mukaan lukien arvo.

Tällaisia ​​ominaisuuksia ovat merkityksen lisäksi käsite "tietotyyppi". Datumin tyyppi määräytyy datapisteen arvojen joukon ja toimintojen joukon perusteella, jotka voidaan suorittaa näille arvoille niiden tunnettujen ominaisuuksien mukaan. Näin ollen tietyn arvon tyyppi määrää vastaavalle arvolle sallitut toiminnot.

Ohjelmointikielet käyttävät tyypillisesti yleisiä tietotyyppejä, kuten kokonaisluku, reaaliluku, merkki, bitti, osoitin jne.

2. TIETOJEN RAKENTEET

Tämän tyypin ominaisuus on organisoinnin yksinkertaisuus (strukturoimattomuus).

Tietorakenne on kokoelma tietoelementtejä, joiden välillä on tiettyjä suhteita, ja tietoelementit voivat olla joko yksinkertaisia ​​tietoja (skalaareja) tai tietorakenteita.

Rakenne voidaan siis määritellä seuraavasti: S = (D, R), missä D on tietoelementtien joukko, R on tietoelementtien välisten suhteiden joukko.

Kaikki yhden tietoelementin suhteet muiden kanssa muodostavat vastaavaan tietoelementtiin liittyvän suhdeelementin.

Rakenteen graafisen esityksen tulee heijastaa sen tietoelementtejä ja yhteyksiä (niiden välisiä suhteita), joten rakenne on kätevä kuvata graafina. Tällöin graafin kärjet voidaan tulkita tietoelementeiksi ja dataelementtien väliset suhteet vastaavat suunnattuja kaaria tai suuntaamattomia reunoja (kuva 1).

Tällä tavalla kuvattua ja esitettyä tietorakennetta kutsutaan abstraktiksi tai loogiseksi, koska sitä tarkastellaan ottamatta huomioon sen esitystapaa tietokoneen muistissa. Mutta mikä tahansa tietorakenne on esitettävä koneen muistissa. Tätä tietorakennetta kutsutaan fyysiseksi rakenteeksi, tallennusrakenteeksi, sisäiseksi rakenteeksi tai muistirakenteeksi.

Kuva 1. Suuntaamaton (a) ja suunnattu (b) graafi

Siten tietojen fyysinen rakenne heijastaa tapaa, jolla tiedot esitetään tietokoneen muistissa.

Yleensä loogisen rakenteen ja sitä vastaavan fyysisen rakenteen välillä on ero, jonka aste riippuu rakenteesta itsestään ja sen fyysisen ympäristön ominaisuuksista, jossa sen tulee heijastua.

Esimerkiksi ohjelmointikielten näkökulmasta kaksiulotteinen taulukko on suorakaiteen muotoinen taulukko, ja muistissa se on lineaarinen solusarja, joista jokainen tallentaa yhden taulukon elementin arvon ja taulukon elementit. on järjestetty rivien (tai sarakkeiden) mukaan.

Tietysti loogisen ja fyysisen rakenteen välillä täytyy olla mekanismi, joka mahdollistaa loogisen rakenteen yhdistämisen fyysiseen rakenteeseen.

Siten kutakin tietorakennetta voidaan luonnehtia sen loogisella (abstraktilla) ja fysikaalisella (konkreettisella) esityksellä sekä operaatioiden sarjalla näillä kahdella rakenteen esityksen tasolla (kuva 2).

Toiminnot loogisella rakenteella

Looginen tietorakenne

Toiminnot fyysisellä rakenteella

Fyysinen datarakenne

Riisi. 2. Tietorakenteen loogisen ja fyysisen esityksen kartoitus

2.1. Tietorakenteiden luokittelu

IN Tietoelementtien välisten eksplisiittisesti määriteltyjen yhteyksien puuttumisesta tai olemassaolosta riippuen tulee erottaa toisistaan ​​riippumattomat rakenteet (vektorit, taulukot, merkkijonot, pinot, jonot) ja yhdistetyt rakenteet (linkitetyt listat).

Tärkeä rakenteen ominaisuus on sen vaihtelevuus - muutos elementtien lukumäärässä ja/tai rakenteen elementtien välisissä yhteyksissä. Tietoelementin arvoa ei ole tarkoitettu, koska tässä tapauksessa tämä ominaisuus olisi tyypillinen kaikille tietorakenteille, lukuun ottamatta mahdollisesti vakioita ja ROM:iin tallennettuja tietoja. Vaihtuvuuden perusteella erotetaan staattiset, puolistaattiset ja dynaamiset rakenteet.

Tietorakenteen tärkeä piirre on sen elementtien järjestysluonne. Tämän kriteerin perusteella rakenteet voidaan jakaa lineaarisesti järjestettäviin eli lineaarisiin ja epälineaarisiin.

Muistissa olevien elementtien suhteellisen järjestelyn luonteesta riippuen lineaariset rakenteet voidaan jakaa rakenteiksi, joiden elementit jakautuvat peräkkäin muistissa (vektorit, merkkijonot, taulukot, pinot, jonot) ja rakenteiksi, joilla on mielivaltainen yhdistetty elementtijakauma muistissa. muisti (yksinkertaisesti kytketty, kaksoisliitetty, syklisesti yhdistetty, assosiaatioluettelot). Esimerkkejä epälineaarisista rakenteista ovat monilinkitetyt listat, puurakenteet ja yleiset graafirakenteet.

2.2. Yksinkertaisimmat staattiset rakenteet

TO Yksinkertaisimmat tietorakenteet sisältävät yleensä vektoreita, taulukoita, tietueita ja taulukoita. Niille on ominaista seuraavat ominaisuudet:

rakenteen pysyvyys koko sen olemassaolon ajan;

elementtien vierekkäisyys ja kaikille rakenteen elementeille allokoidun muistialueen jatkuvuus elementtien välisten suhteiden yksinkertaisuus ja pysyvyys

rakenteita, joiden avulla voit sulkea pois tietoa näistä suhteista rakenteen elementeille varatusta muistialueesta ja tallentaa ne esimerkiksi kompaktissa muodossa kuvaajiin.

Näiden ominaisuuksien vuoksi vektoreita, taulukoita, tietueita ja taulukoita pidetään staattisina rakenteina.

2.2.1. Vektori

Vektori on äärellinen järjestys joukko samantyyppisiä yksinkertaisia ​​tietoja tai skalaareja. Geometrialta katsottuna vektori määrittelee pisteen moniulotteisessa avaruudessa, jonka koordinaatit ovat vektorin elementtien arvoja.

Vektorin elementit ovat ainoassa mahdollisessa suhteessa toisiinsa - välittömän peräkkäisyyden suhteen. Vektorielementtien tiukka järjestys sallii

numeroi ne peräkkäisillä kokonaisluvuilla - indekseillä. Vektorin looginen rakenne on täysin kuvattu sen elementtien lukumäärällä ja tyypillä. Esimerkiksi int-taulukko on kokonaislukutaulukko, joka koostuu 10 elementistä.

Tärkein operaatio vektorilla on pääsy sen elementteihin. Kun elementtiä on käytetty, sille voidaan suorittaa mikä tahansa toiminto, joka on järkevä valitulle tietotyypille.

Loogisella tasolla vektorin elementtiin pääsemiseksi riittää, että määrität vektorin nimen ja vastaavan elementin indeksiarvon. Esimerkiksi: array + array.

Vektorin fyysinen rakenne on samanpituisten muistiosien sarja, joita kutsutaan kentiksi tai aikaväleiksi ja joista jokainen on suunniteltu tallentamaan yksi vektorin elementti. Kenttä voi olla pienimmän osoitettavissa olevan muistisolun koko tai vastata kokonaista ryhmää peräkkäisiä muistisoluja.

Usein fyysinen rakenne liittyy kuvaajaan tai otsikkoon, joka sisältää tietoa fyysisestä rakenteesta. Kuvaaja on välttämätön esimerkiksi siinä tapauksessa, että vektorin rajamitat tulevat tunnetuksi vasta ohjelman suoritusvaiheessa.

Kuvaaja on myös tallennettu koneen muistiin ja se on tietueeksi kutsuttu rakenne. Vektorille kuvaaja yleensä tallentaa sen nimen, koon, rajaindeksiarvot, elementin tyypin, kentän tai paikan koon sekä vektorin ensimmäisen elementin osoitteen (kentän, joka tallentaa tämän elementin).

2.2.2. Array

Taulukko on vektori, jossa jokainen elementti on vektori. Matriisin elementtinä olevan vektorin elementit voivat puolestaan ​​olla myös vektoreita. Tämän elementin elementistä elementtiin ja niin edelleen siirtymisen prosessin on ennemmin tai myöhemmin päätyttävä jonkin tietotyypin skalaariin, ja kaikkien taulukon skalaarielementtien on vastattava tätä tyyppiä (kuva 3).

Riisi. 3. Moniulotteisen taulukon tyyppi

Kuvassa 3 on esitetty moniulotteisen taulukon ulkonäkö: jokainen hilasolmu sisältää taulukkoelementin. Siten sen mitta on (3,3,2).

Kuten vektorin kanssa, taulukon tärkein perustoiminto on pääsy sen elementtiin. Loogisen rakenteen tasolla se suoritetaan käyttämällä taulukon nimeä ja järjestettyä joukkoa indeksejä, jotka yksilöivät taulukon elementin. Esimerkiksi: array[i][j].

Toisin kuin vektorilla, yleisessä taulukossa loogisen rakenteen muunnos fyysiseksi on monimutkaisempi muoto. Tämä muunnos suoritetaan linearisointiprosessilla, joka kartoittaa taulukon moniulotteisen loogisen rakenteen yksiulotteiseksi fyysiseksi rakenteeksi. Tämä fyysinen rakenne on lineaarisesti järjestetty taulukkoelementtien sarja. Siten moniulotteisen taulukon fyysinen rakenne on samanlainen kuin vektorin fyysinen rakenne.

Tästä huolimatta moniulotteisen taulukon kuvaaja on erilainen kuin vektorin kuvaaja. Sen pitäisi esimerkiksi tallentaa tietoa taulukon koosta ja elementtien järjestystavoista (riveittäin tai sarakkeittain).

2.2.3. Tallentaa

Tietue on äärellinen järjestetty elementtijoukko, joka sisältää yleensä erityyppistä dataa.

Tietueen elementtejä kutsutaan usein kentiksi. Tietue on vektorin yleinen käsite, joka ei vaadi yhtenäisyyttä tai

Tietorakenteen käsite on niin perustavanlaatuinen, että sille on vaikea löytää yksinkertaista määritelmää. Tehtävä helpottuu, jos yritämme muotoilla tätä käsitettä suhteessa tietotyyppeihin ja muuttujiin. Kuten tiedät, ohjelma on algoritmin (menettelyt, toiminnot) ja niiden käsittelemän tiedon yksikkö. Data puolestaan ​​määritellään perus- ja johdetuilla tietotyypeillä - "ihanteellisilla" esityksillä kiinteäulotteisista muuttujista, joissa on joukot tunnettuja operaatioita niille ja niiden komponenteille. Muuttujat ovat nimettyjä muistialueita, joihin rakennetut tietotyypit "kartoitetaan".
Ohjelmassa on aina mahdollista erottaa epäsuorasti liittyvien (käyttämällä tietoja samoissa proseduureissa ja funktioissa) ja suoraan toisiinsa liittyvien (osoittimien kautta olevien suhteiden) muuttujien ryhmät. Ensimmäisen likiarvon mukaan niitä voidaan pitää tietorakenteina.

On olemassa SIMPLE (perus, primitive) tietorakenteita (tyypit) ja INTEGRATED (strukturoitu, komposiitti, kompleksi). Yksinkertaiset tietorakenteet ovat sellaisia, joita ei voida jakaa bittejä suurempiin komponentteihin. Fyysisen rakenteen kannalta on tärkeää, että tietyssä konearkkitehtuurissa, tietyssä ohjelmointijärjestelmässä voimme aina etukäteen kertoa, minkä kokoinen tietyn yksinkertaisen tyypin koko tulee olemaan ja mikä on sen sijoittelun rakenne. muisti tulee olemaan. Loogisesta näkökulmasta yksinkertaiset tiedot ovat jakamattomia yksiköitä. Integroituja ovat tietorakenteet, joiden komponentit ovat muita tietorakenteita - yksinkertaisia ​​tai vuorostaan ​​integroituja. Integroidut tietorakenteet rakentaa ohjelmoija käyttäen ohjelmointikielten tarjoamia tiedon integrointityökaluja.

Tietoelementtien välisten eksplisiittisesti määriteltyjen yhteyksien puuttumisesta tai olemassaolosta riippuen tulisi erottaa DISCONNECTED-rakenteet (vektorit, taulukot, merkkijonot, pinot, jonot) ja LINKED-rakenteet (linkitetyt luettelot).

Tietorakenteen erittäin tärkeä ominaisuus on sen vaihtelevuus - muutos elementtien lukumäärässä ja (tai) rakenteen elementtien välisissä yhteyksissä. Rakenteen vaihtelevuuden määritelmä ei heijasta sitä tosiasiaa, että tietoelementtien arvot muuttuvat, koska tässä tapauksessa kaikilla tietorakenteilla olisi vaihtelevuuden ominaisuus. Vaihtuvuuden perusteella rakenteet erotetaan: STAATTINEN, PUOLISTAATTINEN, DYNAAMINEN. Tietorakenteiden luokittelu vaihtelevuuden perusteella on esitetty kuvassa. 1.1. Perustietorakenteet, staattiset, puolistaattiset ja dynaamiset, ovat ominaisia ​​RAM:lle ja niitä kutsutaan usein toimintarakenteiksi. Tiedostorakenteet vastaavat ulkoisen muistin tietorakenteita.

Riisi. 1.1. Tietorakenteiden luokittelu

Tietorakenteen tärkeä piirre on sen elementtien järjestysluonne. Tämän ominaisuuden perusteella rakenteet voidaan jakaa LINEAARISIIN JA EI-LINEAARISIIN rakenteisiin.

Muistissa olevien elementtien suhteellisen järjestelyn luonteesta riippuen lineaariset rakenteet voidaan jakaa rakenteiksi, joissa on SEURAAVAA elementtien jakautumista muistissa (vektorit, merkkijonot, taulukot, pinot, jonot) ja rakenteiksi, joissa elementtien jakautuminen muistissa on MITELMÄLLINEN YHTEYS (yksinkertaisesti linkitetyt, kaksoislinkitetyt luettelot). Esimerkki epälineaarisista rakenteista ovat monilinkitetyt listat, puut, graafit.

Ohjelmointikielissä "tietorakenteiden" käsite liittyy läheisesti käsitteeseen "tietotyypit". Kaikki tiedot, esim. vakioille, muuttujille, funktioarvoille tai lausekkeille on ominaista niiden tyypit.

Kunkin tyypin tiedot osoittavat selvästi:

· 1) tietyn tyyppinen tiedontallennusrakenne, ts. toisaalta muistin varaaminen ja siinä olevan datan esittäminen ja toisaalta binääriesityksen tulkitseminen;

· 2) sallittujen arvojen joukko, joka tällä tai toisella kuvatun tyyppisellä objektilla voi olla;

· 3) joukko kelvollisia operaatioita, jotka soveltuvat kuvatun tyyppiseen kohteeseen.

TIETOJEN RAKENNE on joukko fyysisesti (tietotyypit) ja loogisesti (algoritmi, funktiot) toisiinsa liittyviä muuttujia ja niiden arvoja.

Huomaa, että tietorakenteen käsite ei liity ainoastaan ​​muuttujiin, jotka muodostavat sen, vaan myös algoritmeihin (funktioihin), jotka eivät vain yhdistä muuttujia loogisesti toisiinsa, vaan määrittävät myös sisäiset arvot, joiden tulisi myös olla ominaisia. tästä tietorakenteesta. Esimerkiksi taulukkoon sijoitetulla positiivisten arvojen sarjalla, jolla on muuttuva ulottuvuus (tietorakenne), voi olla nollaerotin. Kaikki toiminnot tämän rajoittimen luomiseksi ja tarkistamiseksi toteutetaan funktioilla. Voidaan siis sanoa, että merkittävä osa tietorakenteesta on "kiinnitetty" sen käsittelyalgoritmeihin.
Menetelmälle muuttujien määrittelyssä tunnetuilla tietotyypeillä on se, että ensinnäkin muuttujien määrä ohjelmassa on kiinteä, ja toiseksi, niiden ulottuvuutta ei voida muuttaa ohjelman ollessa käynnissä. Jos näiden muuttujien väliset suhteet ovat enemmän tai vähemmän vakioita, niin tällaisia ​​tietorakenteita voidaan kutsua staattisiksi.

STAATTINEN TIETARAKENNE - joukko kiinteän määrän muuttujia, joiden mittasuhteet ovat vakio, niiden välisten yhteyksien muuttumattomina
Käänteisesti, jos jokin tietorakenteen parametreista – muuttujien määrä, niiden ulottuvuus tai niiden väliset suhteet – muuttuu ohjelman ollessa käynnissä, tällaisia ​​tietorakenteita kutsutaan dynaamiksi.

DYNAAMINEN TIETOJEN RAKENNE - joukko muuttujia, joiden välisten suhteiden lukumäärä, ulottuvuus tai luonne muuttuu ohjelman toiminnan aikana.

Dynaamiset tietorakenteet perustuvat kahteen ohjelmointikielen elementtiin:

· dynaamiset muuttujat, joiden lukumäärä voi muuttua ja jonka lopulta määrittää itse ohjelma. Lisäksi kyky luoda dynaamisia taulukoita antaa meille mahdollisuuden puhua muuttuvan mittasuhteen tiedoista;

· osoittimet, jotka tarjoavat suoran yhteyden tietojen ja näiden yhteyksien muuttamisen välillä.

Näin ollen seuraava määritelmä on lähellä totuutta: dynaamiset tietorakenteet ovat dynaamisia muuttujia ja taulukoita, jotka on linkitetty osoittimilla.
Tietorakenteista puhuttaessa emme saa unohtaa, että tavalliset muuttujat sijaitsevat RAMissa (tietokoneen sisäisessä muistissa). Siksi tietorakenteilla on yleensä myös jotain tekemistä muistin kanssa. On kuitenkin olemassa myös ulkoista muistia, johon pääsee epäsuorasti tiedostojen kanssa toimivien operaattoreiden (Pascal) tai funktioiden (C) kautta. Binäärisessä hajasaantitilassa mikä tahansa tiedosto on analoginen rajoittamattomalle suoraan osoitettavalle muistialueelle, eli ohjelman näkökulmasta se näyttää samalta kuin tavallinen muisti. Luonnollisesti ohjelma voi kopioida muuttujia muistista mielivaltaiseen paikkaan tiedostossa ja takaisin ja siten järjestää tiedoston (mukaan lukien dynaamiset) tietorakenteet.
Tietorakenne on suorittaja, joka järjestää tiedon kanssa työskentelyn, mukaan lukien sen tallennuksen, lisäämisen ja poistamisen, muuttamisen, haun jne. Tietorakenne ylläpitää tiettyä pääsyjärjestystä siihen. Tietorakennetta voidaan ajatella eräänlaisena varastona tai kirjastona. Tietorakennetta kuvattaessa sinun on lueteltava sille mahdolliset toiminnot ja kuvattava selkeästi kunkin toiminnon tulos. Kutsumme tällaisia ​​toimia resepteiksi. Ohjelmoinnin näkökulmasta tietorakennemääräysten järjestelmä vastaa joukkoa toimintoja, jotka toimivat yhteisillä muuttujilla.
Tietorakenteet toteutetaan kätevimmin oliokielillä. Niissä tietorakenne vastaa luokkaa, itse data on tallennettu luokan jäsenmuuttujiin (tai dataan päästään jäsenmuuttujien kautta) ja joukko luokkamenetelmiä vastaa määräysjärjestelmää. Pääsääntöisesti oliokielissä tietorakenteet toteutetaan vakioluokkien kirjaston muodossa: nämä ovat C++-kielen ns. konttiluokkia, jotka sisältyvät vakio-STL-luokkakirjastoon, tai luokkia, jotka toteuttavat erilaisia tietorakenteet Java-kielen Java Developer Kit -kirjastosta.
Tietorakenteita voidaan kuitenkin toteuttaa yhtä menestyksekkäästi perinteisillä ohjelmointikielillä, kuten Fortran tai C. Tässä tapauksessa sinun tulee noudattaa olio-ohjelmointityyliä: tunnistaa selvästi joukko funktioita, jotka toimivat tietorakenteen kanssa, ja rajaa pääsy tietoihin vain tähän toimintosarjaan. Itse data on toteutettu staattisina (ei globaaleina) muuttujina. C-kielellä ohjelmoitaessa tietorakenne vastaa kahta tiedostoa lähdeteksteineen:
1. otsikko, tai h-tiedosto, joka kuvaa tietorakenteen rajapintaa, ts. joukon toimintoprototyyppejä, jotka vastaavat tietorakennemääräysten järjestelmää;
2. toteutustiedosto eli C-tiedosto, joka määrittelee staattiset muuttujat, jotka tallentavat ja pääsevät käsiksi dataan sekä toteuttaa tietorakennevaatimusjärjestelmää vastaavat toiminnot
Tietorakenne toteutetaan yleensä yksinkertaisemman jo toteutetun perusrakenteen perusteella tai taulukon ja yksinkertaisten muuttujien joukon perusteella. Tietorakenteen kuvaileminen loogisesta näkökulmasta ja toteutuskuvaus tulisi tehdä selväksi. Toteutuksia voi olla monia erilaisia, mutta loogiselta kannalta (eli ulkopuolisen käyttäjän näkökulmasta) ne ovat kaikki samanarvoisia ja eroavat ehkä vain käskyjen suoritusnopeuden suhteen.

Välttämätön ehto algoritmin rakentamiselle on tietojen formalisointi, eli tiedon vähentäminen joillekin tietomalli(cm." Tietomallit"), on jo kuvattu ja tutkittu. Kun tällainen malli löytyy, sen sanotaan olevan määritelty abstrakti tietorakenne.

Abstrakti tietorakenne kuvaa kohteen ominaisuuksia ja ominaisuuksia, suhdetta objektielementtien välillä mahdollisimman hyvin toiminnot tietyn kohteen tai objektiluokan yli.

Yksi tietojenkäsittelytieteen tehtävistä on löytää tietokonekäsittelyyn sopivia tiedon esitysmuotoja. Tietojenkäsittelytiede tarkana tieteenä toimii muodollisten (matemaattisesti tiukasti kuvattujen) objektien kanssa. Tällaiset esineet - perus abstrakteja tietorakenteita Tietojenkäsittelytieteessä käytetään:

· kokonaisluvut;

· reaaliluvut;

· symbolit;

· loogiset arvot.

Näiden objektien tietokonekäsittelyyn ohjelmointikielillä on sopivia tietotyypit(cm." Tietotyypit"). Perusobjekteja voidaan yhdistää monimutkaisempiin rakenteiksi lisäämällä operaatioita rakenteeseen kokonaisuutena ja pääsysääntöjä tämän abstraktin tietorakenteen yksittäisiin elementteihin.

Näitä abstrakteja tietorakenteita ovat:

· vektorit (äärelliset taulukot);

· taulukot (matriisit) ja yleisessä tapauksessa - moniulotteiset taulukot;

· dynaamiset rakenteet:

Symbolien sekvenssit, numerot;

Jonot;

Puut;

Onnistunut tietorakenteen valinta on usein avain tehokkaan algoritmin ja sen toteuttavan ohjelman luomiseen: tietorakenteiden ja todellisten objektien analogiaa käyttämällä voidaan löytää tehokkaita ratkaisuja ongelmiin.

Huomaa, että luetellut rakenteet ovat olemassa riippumatta niiden toteutuksesta ohjelmoinnin aikana. He työskentelivät näiden tietorakenteiden parissa sekä 1700- että 1800-luvuilla, jolloin laskentakonetta ei ollut vielä keksitty. Voimme kehittää algoritmin abstraktilla tietorakenteella, mutta algoritmin toteuttamiseksi tietyllä ohjelmointikielellä meidän on löydettävä tapa esittää se termeillä tietotyypit Ja operaattorit tämä ohjelmointikieli tukee (katso " Ohjelmointikielen operaattorit"). Käytämme abstraktien rakenteiden tietokoneesitykseen tietorakenteita, jotka ovat joukko muuttujia, mahdollisesti eri tietotyyppejä, jotka on yhdistetty tietyllä tavalla. Rakenteiden, kuten vektorin, taulukon, merkkijonon, sekvenssin, rakentamiseen useimmilla ohjelmointikielillä on standardi tietotyypit: yksiulotteinen taulukko, kaksiulotteinen taulukko, merkkijono, tiedosto (harvemmin luettelo). Muiden tietorakenteiden organisointi ennen kaikkea dynaamiset rakenteet, jonka koko muuttuu ohjelman suorituksen aikana, ohjelmoijan on toteutettava itsenäisesti perustietotyyppejä käyttäen. Tarkastellaanpa tällaisia ​​rakenteita yksityiskohtaisemmin.

Luettelot

Lineaarinen lista- lineaarisesti toisiinsa liittyvien elementtien sarja, jolle sallitaan elementtien lisääminen mielivaltaiseen paikkaan luettelossa ja minkä tahansa elementin poistaminen. Lineaarinen luettelo tunnistetaan yksilöllisesti luettelon alkuun osoittavalla osoittimella. Tyypillisiä toimintoja listoilla ovat: listan läpikulku, tietyn elementin etsiminen, elementin lisääminen välittömästi tietyn elementin jälkeen tai ennen, tietyn elementin poistaminen, kahden listan yhdistäminen yhdeksi, yhden luettelon jakaminen kahdeksi tai useammaksi listaksi jne.

Lineaarisessa luettelossa jokaiselle elementille paitsi ensimmäinen, On edellinen elementti; jokaiselle elementille paitsi kestää, On seuraavaksi elementti. Siten kaikki luettelon elementit ovat järjestyksessä. Lineaarisen erikseen linkitetyn luettelon käsittely ei kuitenkaan aina ole kätevää, koska ei ole mahdollista liikkua vastakkaiseen suuntaan - luettelon lopusta alkuun. Lineaarisessa luettelossa voit kulkea kaikkien elementtien läpi vain siirtymällä peräkkäin nykyisestä elementistä seuraavaan, alkaen ensimmäisestä, suora pääsy i th elementti on mahdoton.

Esimerkki 1. Lukijoiden nimien järjestys kirjastonhoitajan tietokoneessa määrittää "edellinen-seuraava" -suhteen. Pääsääntöisesti tietueilla itsellään on lisäominaisuus - ne on järjestetty aakkosjärjestyksessä. Tässä listassa on toteutettu uuden lukijan lisääminen ja tarvittaessa vanhan poistaminen. Jos lisäksi pidetään kirjaa kullekin lukijalle annetuista kirjoista, on tarkoituksenmukaista esittää kukin tällainen tietue käyttämällä jälleen annettujen kirjojen luetteloa.

Soittoluettelot- sama rakenne kuin lineaarisella listalla, mutta lisäyhteydellä viimeisen ja ensimmäisen elementin välillä, eli viimeisen elementin jälkeen seuraava elementti on ensimmäinen elementti.

Pyöreässä luettelossa lineaarisen sijaan kaikki elementit ovat samanarvoisia(koska jokaiselle elementille on määritelty sekä edellinen että seuraava elementti). "Ensimmäisen" ja "viimeisen" elementin valinta soittolistassa on hyvin mielivaltaista, koska itse asiassa listarakenteessa ei ole nimenomaisesti allokoituja elementtejä!

Esimerkki 2. Monissa peleissä lapset käyttävät laskureita valitakseen johtajan, jakaakseen ryhmiin jne. Yleensä laskurit ovat pitkiä, ja lapset (tietämättään) järjestävät pyöreän luettelon. "Edellinen-seuraava" -suhde määräytyy sen mukaan, mihin suuntaan johtaja laskee. Tyypillinen toimenpide tällaisessa rakenteessa on elementin poistaminen luettelosta säilyttäen samalla sen pyöreä rakenne.

Lineaariset luettelot, joissa lisäys-, poisto- ja elementtiarvoihin pääsytoiminnot suoritetaan vain uloimmille elementeille (ensimmäinen tai viimeinen), ovat saaneet erityisnimet.

Pino- erikoistapaus lineaarisesta yksitellen linkitetystä luettelosta, jolle on määritelty kaksi toimintoa: elementin lisääminen pinon yläosaan (ennen ensimmäistä elementtiä) ja elementin poistaminen pinon yläosasta (ensimmäisen elementin poistaminen).

Esimerkki 3. Tarkastellaan ongelmaa aritmeettisen lausekkeen erityyppisten sulkeiden tasapainon määrittämisessä. Haluat esimerkiksi analysoida, ovatko sulut tasapainossa sulkuja ja hakasulkeja sisältävässä lausekkeessa: ? Tämän ongelman ratkaisemiseksi käytämme dynaamista rakennetta tiedot pino. Esitetään algoritmi tämän ongelman ratkaisemiseksi askel askeleelta. Käytämme seuraavaa merkintää:

i- analysoidun symbolin numero;

n- lausekkeen merkkien määrä.

1. i = 0.

2. i = i + 1.

3. Jos in, siirry sitten vaiheeseen (4), muussa tapauksessa, jos pino on tyhjä, näytämme viestin "Hakasulkeet ovat tasapainossa", muuten näytämme viestin " kiinnikkeet eivät ole tasapainossa" Algoritmin loppu.

4. Jos i Symboli eroaa hakasulkeista, siirry sitten vaiheeseen (2).

5. Jos i Symboli on yhtä suuri kuin "(" tai "[", sitten laitamme sen pinoon, siirry vaiheeseen (2).

6. Jos i th symboli on ")", sitten tarkistamme pinon yläosan: jos pinon yläosassa on "(", poistamme sen pinosta; siirry vaiheeseen (2), muuten näytämme viestin " kiinnikkeet eivät ole tasapainossa" Algoritmin loppu.

7. Jos i th merkki on "]", sitten tarkistamme pinon yläosan: jos pinon yläosassa on "[", poistamme sen pinosta; siirry vaiheeseen (2), muuten näytämme viestin " kiinnikkeet eivät ole tasapainossa" Algoritmin loppu.

Jonottaa- Lineaarisen yksittäislinkitetyn luettelon erikoistapaus, jolle sallitaan vain kaksi toimintoa: elementin lisääminen jonon loppuun (häntä) ja elementin poistaminen jonon alusta (head).

Jonon käsite on todellakin hyvin lähellä jokapäiväistä termiä "jono". Asiakkaiden jono myymälässä on kuvattu hyvin tämän tietorakenteen avulla.

puut

Puu on kokoelma elementtejä nimeltä solmut, jossa yksi elementti on valittu ( juuri), ja loput elementit on jaettu epäyhtenäisiksi joukoiksi (alipuiksi), joista jokainen on puu ja jokaisen alipuun juuri on jälkeläinen puun juuri, ts. kaikki elementit liittyvät toisiinsa suhteella (esi-isä-jälkeläinen). Tämän seurauksena muodostuu solmujen hierarkkinen rakenne. Solmuja, joilla ei ole lapsia, kutsutaan lähtee. Puulle määritellään seuraavat toiminnot: elementin lisääminen puuhun, elementin poistaminen puusta, puun läpikulku, elementin etsiminen puusta.

Esimerkki 4. Puu on kätevin tietorakenne sukupuun esittämiseen, jonka avulla voidaan ratkaista kahden ihmisen välisen suhteen asteen määrittelyongelmia.

Puita käytetään myös pelien voittostrategioiden määrittämiseen (katso artikkeli " Pelit. Voittostrategiat") ja erilaisten tietomallien rakentamiseen (katso " Tietomallit”).

Tietojenkäsittelytieteessä erityisen tärkeä rooli on ns binääripuut.

Binäärinen puu- puun erikoistapaus, jossa kullakin solmulla voi olla enintään kaksi jälkeläistä, jotka ovat vasemman ja oikean alipuun juuret.

Jos lisäksi puun solmujen ehto täyttyy, että kaikki vasemman alipuun elementtien arvot ovat pienempiä kuin puun juuren arvo ja oikean alipuun elementtien kaikki arvot ovat suurempi kuin juuren arvo, niin tällaista puuta kutsutaan binäärihakupuu ja se on suunniteltu elementtien nopeaan etsimiseen. Hakualgoritmi tällaisessa puussa toimii näin: haettua arvoa verrataan puun juuren arvoon ja vertailun tuloksesta riippuen haku joko päättyy tai jatkuu vain vasemmalla tai vain oikealla. alipuu, vastaavasti. Vertailuoperaatioiden kokonaismäärä ei ylitä ns puun korkeus- elementtien enimmäismäärä polulla puun juuresta yhteen lehteen. Joten kuvassa näkyvän puun korkeus on 4.

Kaaviot

Kaavio on joukko elementtejä nimeltä huiput graafi sekä joukko näiden kärkien välisiä suhteita, ns kylkiluut kaavio. Tämän tietorakenteen graafinen tulkinta on joukko pisteitä, jotka vastaavat pisteitä, joiden jotkin parit on yhdistetty reunoja vastaavilla viivoilla tai nuolilla. Jälkimmäisessä tapauksessa graafia kutsutaan suuntautunut(katso myös artikkelit " Graafiset mallit"ja" Taulukkomallit”).

Koska mielivaltaisen rakenteellisia objekteja voidaan kuvata graafien avulla, graafit ovat pääasiallinen väline monimutkaisten objektien rakenteiden ja järjestelmien toiminnan kuvaamiseen. Esimerkiksi kuvaamaan tietokoneverkkoa, kuljetusjärjestelmää, hierarkkista rakennetta (puu on yksi graafin tyypeistä). Algoritmien vuokaaviot (katso " Tapoja kirjoittaa algoritmeja”) ovat myös kaavioita.

Jos jokaiselle reunalle on määritetty myös tietty numero ( paino), niin tällaista kuvaajaa kutsutaan painotettu. Esimerkiksi Venäjän tiejärjestelmää kuvattaessa graafin avulla tiettyjä asuinalueita yhdistävän tien pituus (kaavion reunan paino) on tärkeä. Lisäksi kuvassa vastaavien reunojen pituuksien ei tarvitse vastata niille annettuja painoja, toisin kuin tiekartassa.

Esimerkki 5. Seuraava ongelma on kätevää ratkaista painotetun graafin avulla. Venäjän hallitus laatii suunnitelmaa nykyaikaisten moottoriteiden rakentamisesta, jotka yhdistävät yli miljoonan asukkaan kaupunkeja. Millaisia ​​teitä pitäisi rakentaa, jotta mistä tahansa sellaisesta kaupungista pääsee uusien valtateiden kautta toiseen ja teiden kokonaispituus olisi minimaalinen?

Tällä graafiteorian ongelmalla on yksinkertainen ja tarkka ratkaisu. Voimme aloittaa tieverkoston suunnittelun mistä tahansa kaupungista, esimerkiksi Pietarista. Yhdistetään se lähimpään yli miljoonakaupunkiin. Sitten jokaisessa vaiheessa olemassa olevaan verkkoon lisätään lyhin tie, joka voi yhdistää verkkoon vielä liittymättömän kaupungin johonkin verkkoon jo kuuluvista kaupungeista. Teiden määrä on siten yksi vähemmän kuin kaupunkien määrä.

Abstrakti tietorakenne - graafi - voidaan esittää ohjelmassa useilla tavoilla, ts. käyttämällä erilaisia ​​tietotyyppejä. Graafia voidaan kuvata esimerkiksi käyttämällä reunojen listaa, jossa jokainen reuna määritellään parilla pisteillä ja valinnaisesti painolla. Taulukkokaavioiden tallennus on yleistynyt (katso " Taulukkomallit"), kutsutaan myös viereisyysmatriisi, eli esimerkiksi kaksiulotteinen taulukko A, missä painottamattomalle graafille (tai 1), jos kärkien välinen reuna i Ja j on olemassa ja (tai 0) muuten. Painotetulle kaaviolle A[i][j] on yhtä suuri kuin vastaavan reunan paino, ja reunan puuttuminen useissa tehtävissä on sopivasti merkitty äärettömyyteen. Suuntaamattomissa kaavioissa vierekkäisyysmatriisi on aina symmetrinen päädiagonaalin suhteen ( i = j). Vierekkäisyysmatriisin avulla on helppo tarkistaa, onko graafissa kärkeä yhdistävä reuna i topin kanssa j. Sen suurin haitta on, että viereisyysmatriisi edellyttää, että muistia on riittävästi tallennettavaksi N 2 arvoa kaaviolle, joka sisältää N kärkipisteitä, vaikka graafissa olisi huomattavasti vähemmän reunoja kuin N 2 .

Kun käsitettä selitetään tietorakenteita Voit käyttää seuraavaa kuvaa.

Mitä tahansa ongelmaa ratkaistaessa on tarpeen työskennellä tiedot ja suorittaa niille operaatioita. Näiden operaatioiden joukko jokaiselle tehtävälle on yleisesti ottaen erilainen. Kuitenkin, jos tiettyä toimintosarjaa käytetään usein erilaisten ongelmien ratkaisemiseen, on hyödyllistä keksiä tapa järjestää data siten, että voit suorittaa nämä tietyt toiminnot mahdollisimman tehokkaasti. Kun tällainen menetelmä on keksitty, voidaan tiettyä ongelmaa ratkaistaessa olettaa, että meillä on "musta laatikko" (kutsumme sitä tietorakenteeksi), josta tiedetään, että siihen on tallennettu jonkinlaista tietoa, ja joka voi suorittaa joitain toimintoja näille tiedoille. Näin voit paeta yksityiskohtia ja keskittyä tehtävän erityispiirteisiin. Sisällä (eli tietokoneessa) tämä "musta laatikko" voidaan toteuttaa monella tapaa, mutta kannattaa pyrkiä mahdollisimman tehokkaaseen (nopeaan ja muistia säästävään) toteutukseen.

Valtion koulutusstandardi mahdollistaa erilaisten tietorakenteiden tutkimisen sekä peruskoulun peruskurssilla että lukiossa. Peruskoulun ohjelmointikurssilla Malliohjelma mainitsee merkkiketjut (merkkijonot), numerot, listat, puut ja graafit käsiteltyinä objekteina. Käytännön töissä monimutkaisen rakenteen tiedoista mainitaan kuitenkin vain taulukko (katso artikkeli " Array Operations"). Peruskoulussa on ilmeisesti järkevää tutkia jäljellä olevia rakenteita ennen kaikkea graafisia ja muita malleja rakennettaessa (ks. tietosanakirjan osa IV).

Suunniteltu erityiskoulun ohjelma sisältää lukujen, matriisien, merkkijonojen, listojen ja puiden käsittelyn. Yksinkertaisena esimerkkinä listojen kanssa työskentelystä voit järjestää pinon käyttämällä yksiulotteista taulukkoa ja pinon yläosaan osoittavaa kokonaislukumuuttujaa (pinon "ala" on aina taulukon ensimmäisessä elementissä ). Artikkelissa esitetyn sulkeiden tasapainon tarkistamisen ongelman lisäksi voit tutkia pinolaskimen toimintaa esimerkkiä algoritmista, jolla aritmeettinen lauseke muunnetaan käänteisiksi puolalaiseksi merkinnöiksi ( postfix tallennus) siitä, johon olemme tottuneet infix tallennetaan ja lasketaan edelleen aritmeettisen lausekkeen arvo.

Binääripuu voidaan myös helposti esittää tietokoneen muistissa yksiulotteisen taulukon avulla, jolloin taulukon ensimmäinen elementti tallentaa puun juuren ja puusolmun jälkeläiset. i-taulukon elementti sijaitsee kohdassa 2 i-m ja (2 i+ 1):nnet elementit, vastaavasti. Jos solmulla ei ole jälkeläistä, vastaava elementti on yhtä suuri kuin esimerkiksi 0. Rekursiivinen puun läpikulkuproseduuri t ja sen elementtien tulostaminen tässä tapauksessa näyttää tältä:

menettelyjärjestys(i:kokonaisluku);

jos t[i]<> 0 sitten

Listojen ja taulukoiden toteutuksesta dynaamisten muuttujien avulla voit lukea esimerkiksi N. Wirthin klassikkokirjasta “Algoritmit ja tietorakenteet”.

Erikoiskoulun ohjelma sisältää myös graafialgoritmeja. Erityisesti siinä mainitaan lyhimmän polun löytäminen kaaviosta. Painottamattomalle graafille tämä ongelma voidaan ratkaista esimerkiksi "leveys-first-haku" -algoritmilla, jolloin ensin merkitään graafin kärjet, jotka on liitetty reunaan alkuperäiseen kärkipisteeseen, sitten kaikki merkittyihin liittyvät pisteet jne. . Painotetussa graafissa käytetään useimmiten Dijkstran algoritmia (katso esimerkiksi E.V. Andreevan artikkeli "Olympiads in Informatics. Paths to the Top", "Informatiikka" nro 8/2002). Tällaisten algoritmien tuntemus on välttämätöntä tietojenkäsittelytieteen olympialaisten ongelmien ratkaisemiseksi. Niinpä koko Venäjän tietotekniikan olympiadin IV liittovaltion piirivaiheessa vuonna 2007 ehdotettiin ongelmaa "Haudot ja juoksuhaudot", jonka ratkaisu kiteytyi lyhimmän polun löytämiseen painotetussa kaaviossa.

Aluksi ohjelmointiprosessi sisälsi ohjelmoijan, joka kirjoitti kaikki algoritmit suoraan konekielellä. Tämä lähestymistapa lisäsi jo ennestään vaikeaa algoritmien kehittämistehtävää ja johti liian usein virheisiin, jotka oli löydettävä ja korjattava [virheenkorjausprosessi] ennen kuin työtä voitiin pitää valmiina.

Ensimmäinen askel ohjelmoinnin helpottamiseksi oli lopettaa numeroiden käyttö käskyjen ja operandien kirjoittamiseen suoraan siinä muodossa, jossa niitä käytetään koneessa. Tätä tarkoitusta varten ohjelmia kehitettäessä alettiin laajalti käyttää eri komentojen muistomerkintää niiden heksadesimaaliesityksen sijaan. Esimerkiksi rekisterin lataamiskomennon digitaalisen koodin sijaan ohjelmoija voisi nyt kirjoittaa LOD:n ja rekisterin sisällön muistiin kopiointikomennon koodin sijaan hän voisi käyttää muistikirjaa STO. Operandien kirjoittamista varten kehitettiin säännöt, joiden mukaan ohjelmoija saattoi antaa tietyille muistialueille kuvaavia nimiä [usein nimikkeitä] ja käyttää niitä kirjoittaessaan ohjelmakäskyjä vastaavien muistisolujen osoitteiden sijasta. Tällaisia ​​tunnisteita kutsutaan yleensä muuttujiksi. Tämä korostaa, että kun muutamme tietylle muistipaikalle allokoitua arvoa, muutamme kyseiselle paikalle osoitettuun tunnisteeseen liittyvää arvoa ohjelman suorittamisen aikana.

Kun muuttuja määritetään ohjelmassa, sen tyyppi määritetään yleensä samalla. Tietotyyppi määrittää sekä tietyn tiedon tulkinnan että sille suoritettavat toiminnot. Tietotyyppejä ovat Integer, Real, Character ja Boolean.

Kokonaislukutyyppiä käytetään esittämään numeerista dataa, joka on kokonaisluku. Muistissa ne esitetään useimmiten binäärisenä komplementtikoodina. Voit suorittaa normaaleja aritmeettisia ja vertailutoimintoja kokonaislukutiedoille.

Real-tyyppi on tarkoitettu edustamaan numeerista dataa, joka voi sisältää muita kuin kokonaislukuja. Ne tallennetaan yleensä muistiin binäärisinä liukulukuina. Toiminnot, jotka voidaan suorittaa todellisille tiedoille, ovat samat kuin ne, jotka voidaan suorittaa kokonaislukutiedoille. Kahden todellisen dataelementin lisäämiseen vaadittavat käsittelyt ovat kuitenkin erilaisia ​​kuin kokonaislukumuuttujien toimintojen suorittamiseen vaadittavat käsittelyt.

Merkkityyppiä käytetään tiedoissa, jotka koostuvat merkeistä, jotka on tallennettu muistiin ASCII- tai UNICODE-koodeina. Tämän tyyppisiä tietoja voidaan verrata keskenään [päätä, kumpi kahdesta merkistä edeltää toista aakkosjärjestyksessä]; tarkista, onko yksi merkkijono toinen, ja yhdistä myös kaksi merkkijonoa yhdeksi pidemmäksi merkkijonoksi lisäämällä niistä toinen toisensa jälkeen [ketjutustoiminto].

Boolen arvo viittaa tietoihin, joilla voi olla vain kaksi arvoa: tosi ja epätosi. Esimerkki tällaisista tiedoista on kahden luvun vertailuoperaation tulos. Boolen datan toimintoihin kuuluu sen tarkistaminen, onko muuttujan nykyinen arvo True vai False.

Koneen päämuisti on järjestetty erillisiin soluihin, joiden osoitteet kasvavat peräkkäin. Näitä soluja käytetään kuitenkin usein perustana muiden tietojen tallennustapojen toteuttamiselle. Esimerkiksi tekstiä tarkastellaan tyypillisesti pitkänä merkkijonona, kun taas myyntitietoja voidaan tarkastella suorakaiteen muotoisena taulukkona, jossa on numeerisia arvoja, joista jokainen edustaa tietyn työntekijän tiettynä päivänä suorittamien tapahtumien määrää. Tavoitteena on tarjota käyttäjälle keino manipuloida tällaisia ​​abstrakteja rakenteita sen sijaan, että hänen pitäisi syventyä koneen päämuistissa olevien tietojen varsinaisen järjestämisen yksityiskohtiin. Käyttääksesi tietokonetta oikein, sinulla on oltava hyvät tiedot tietojen välisistä rakenteellisista suhteista, tietokoneen sisäisten rakenteiden esittämisen perusmenetelmistä sekä niiden kanssa työskentelytavoista. Tietokoneen tietojen välisissä yhteyksissä käytetään seuraavia tietorakenteita: array, tietue, lista, puu, pino, jono.

Taulukot

Taulukko on rakenne, joka sisältää useita samantyyppisiä elementtejä. Indeksejä käytetään taulukon elementtien järjestämiseen. Indeksit kirjoitetaan sulkeisiin taulukon nimen jälkeen. Yhden indeksin taulukkoa kutsutaan yksiulotteiseksi, kahdeksi - kaksiulotteiseksi jne.

Tallentaa

Tietue on rakenne, joka koostuu elementeistä, jotka eivät välttämättä ole samantyyppisiä. Tietueen yksittäisiä elementtejä kutsutaan kentäksi. Kenttä puolestaan ​​voi olla myös ennätys.

ennätys Opiskelija (
Etunimi,
Sukunimi,
ryhmä
)

Luettelot

Lista on joukko tietueita, joista jokainen sisältää erityisen kentän - indeksin. Osoitin linkittää tietueen johonkin toiseen tietueeseen tai sisältää Null-arvon, joka osoittaa, että osoittimen arvo on määrittelemätön.

Yksittäin linkitetyn luettelon merkinnöillä jokaisella on yksi osoitin, ja ne on yhdistetty ketjuun:

Kuvan nuoli osoittaa osoittimen sisällön ja sana Data tarkoittaa kenttien kokoelmaa, johon tiedot on tallennettu. Lista voidaan järjestää käyttämällä kaksiulotteista taulukkoa, kaikki elementit, joiden ensimmäinen indeksi on 0, on tarkoitettu tietojen tallentamiseen, ja kaikki elementit, joiden ensimmäinen indeksi on 1, ovat osoittimia.

Tässä luettelossa englannin aakkosten kirjaimia sisältävät merkinnät on järjestetty aakkosjärjestykseen. Luettelon ensimmäinen merkintä sisältää merkin "A", toinen - "B" jne.

Jotta voit työskennellä luettelon kanssa, sinun on kyettävä suorittamaan kolme perustoimintoa:

Pass() - listan poikki tai liikkuminen;
Add() - uuden merkinnän lisääminen luetteloon;
Poista() - poistaa merkinnän luettelosta.

Toimintojen lisäksi luettelon käyttäminen vaatii vielä kaksi muuttujaa:

Päämuuttuja, joka tallentaa tiedot luettelon ensimmäisestä merkinnästä
Nykyinen muuttuja, joka osoittaa luettelon nykyiseen kohtaan

Taulukossa on yhteenveto joidenkin toimintojen kuvauksista luettelossa, jonka toteutuksesta on esimerkki edellä.

Toiminnan nimi	Pseudokoodi
Siirrä luettelossa yksi askel alaspäin	toiminto Hyväksy (nykyinen) ( jos (M Nolla) niin Virta:=M; paluu (nykyinen); }
	toiminto Lisää(nykyinen, uusi) ( M: = M; M: = Uusi; palata; }
Lisää luetteloon merkintä, johon Uusi muuttuja viittaa	toiminto Poista (nykyinen) ( jos (M Null) sitten M: = M]; palata; }

Kaksinkertaisesti linkitetyn luettelon merkinnät on ketjutettu yhteen, mutta niissä on kaksi osoitinkenttää. Toinen niistä osoittaa luettelon edelliseen elementtiin, toinen seuraavaan elementtiin. Tämän rakenteen avulla voit siirtyä luettelossa kahteen suuntaan: eteenpäin ja taaksepäin.

Listaa, jonka viimeinen merkintä osoittaa ensimmäiseen, kutsutaan pyöreäksi listaksi. Näissä luetteloissa ei ole nollaosoittimella varustettua merkintää.

Puu on haarautunut luettelo, jonka jokainen merkintä voi sisältää useita osoittimia. Puuhun sisältyviä merkintöjä kutsutaan solmuiksi. Solmuja, joiden osoittimet ovat kaikki tyhjiä, kutsutaan lehtiksi. Puun ylintä aloitussolmua kutsutaan juurisolmuksi. Monissa ongelmissa riittää käyttää binääripuita, joiden solmuissa on enintään kaksi osoitinta.

Esimerkki. Sinun on laskettava matemaattinen lauseke (3+7)*(2/(3-1)). Kuvitellaanpa tämä ilmaus puuna:

Jokainen tämän puun solmu on seuraavan muotoinen tietue:

Record Node (
Toiminta
Määrä
Vasen osoitin
Oikea osoitin
)

Puun lehdet sisältävät numeroita, loput solmut sisältävät operaatioiden symboleja.

Kun kuvattu puu on toteutettu kaksiulotteisessa taulukossa, saamme seuraavan kuvan:

Puun arvon laskemiseksi sinun on laskettava oikean ja vasemman alipuun arvot ja suoritettava sitten tuloksena oleva toiminto niille. Ongelman ratkaisevan algoritmin pseudokoodi näyttää tältä:

funktio Laske (nykyinen) (
jos (M=nolla) niin
Tulos: = M;
muu(
R1: = Laske (M);
R2: = Laske (M);
Tulos: =R1(M)R2;
}
palautus (tulos);
}

Pino on tietorakenne, joka on järjestetty viimeinen sisään, ensimmäinen ulos -periaatteella. Pinoon tallennettuihin tietoihin pääsee käsiksi yläosan kautta. Data työnnetään pinoon peräkkäin Ensimmäisenä pinoon työnnetty elementti on alareunassa, ja jotta se voidaan nostaa pinosta, sinun täytyy ensin popata kaikki pinoon työnnetyt tiedot.

Kun työskentelet pinon kanssa, kaksi hätätilannetta on mahdollista: yritys lukea tietoja tyhjästä pinosta; yritys työntää elementti pinoon, kun pinossa olevien elementtien määrä on saavuttanut suurimman sallitun määrän.

Jono on tietorakenne, joka on järjestetty ensin sisään, ensin ulos -periaatteella. Jonossa on vaihteleva määrä dataa. Jonossa tiedot lisätään pyrstölle, kun se haetaan, se otetaan päästä.

Hash-taulukko

Hashing on tekniikka, joka mahdollistaa suoran pääsyn tietueisiin ilman lisärakenteita. Prosessi voidaan kuvata lyhyesti seuraavasti. Tila, jossa tietoja säilytetään, on jaettu useisiin segmentteihin. Tietueet jaetaan näiden ryhmien kesken jonkin algoritmin, jota kutsutaan hajautusalgoritmiksi, mukaan, joka muuntaa avainkentän arvon sängyn numeroksi. Jokainen tietue tallennetaan tämän prosessin määrittelemään segmenttiin. Siksi tietue voidaan noutaa soveltamalla hajautusalgoritmia sen avainkentän arvoon ja lukemalla vastaavan segmentin tietueet. Tällä tavalla muodostettua tietorakennetta kutsutaan hash-taulukoksi.

Jos esimerkiksi sinun on järjestettävä hash-taulukko tallentaaksesi englannin aakkosten isoja kirjaimia, voit valita ASCII-merkkikoodeja avaimille, jolloin hajautusalgoritmi katkaisee matalan kertaluvun viisi bittiä ja käyttää niitä indeksin muodostamiseen. taulukon elementti merkin tallentamista varten:

Yleensä hajautusalgoritmin on avainarvon perusteella tuotettava indeksiarvo taulukon rajojen sisällä ja jaettava avaimet tasaisesti taulukon elementtien kesken. Jälkimmäisen vaatimuksen noudattamatta jättäminen johtaa tilanteisiin, joissa useat tietueet kuuluvat samaan segmenttiin. Näitä tilanteita kutsutaan törmäyksiksi.