Tietorakenteen yleinen käsite. Tietorakenteet. Epävirallinen opas

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 latausrekisterin komennon digitaalisen koodin sijasta ohjelmoija voisi nyt kirjoittaa LOD:n ja muistiin kopiorekisterikomennon koodin sijaan ohjelmoija 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 ilmoitetaan 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 tyypillisesti 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 toisiinsa [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.

Ennätys

Tietue on rakenne, joka koostuu elementeistä, jotka eivät välttämättä ole samaa tyyppiä. 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, jossa kaikki elementit, joiden ensimmäinen indeksi on 0, on tarkoitettu tallentamaan tietoja 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() - läpikulku tai liikkuminen listalla;
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 merkintään

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 (
Operaatio
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. Tiedot työnnetään pinoon peräkkäin. Ensin pinoon työnnetty elementti on alareunassa, ja sen poistamiseksi pinosta täytyy ensin popata kaikki pinoon työnnetyt tiedot.

Pinon kanssa työskennellessä 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öön, 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 segmenttien 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-merkkikoodit 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.

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:

· kokonaislukuja;

· 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än ohjelmointikielen tukema (katso " Ohjelmointikielen operaattorit"). Abstraktien rakenteiden tietokoneesitykseen, Tietorakenteet, 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 Seuraava 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. Tietueilla itsellään on pääsääntöisesti 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ä listassa 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 "sulut 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 kunkin 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 tehtävä 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 mihin tahansa 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ä reunalistaa, jossa jokainen reuna määritellään parilla kärkipisteillä 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 kuvaajalle, joka sisältää N kärkipisteitä, vaikka graafissa olisi huomattavasti vähemmän reunoja kuin N 2 .

Kun käsitettä selitetään Tietorakenteet 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 prosessoituina objekteina. Käytännössä 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 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 mainitaan kaavion lyhimmän polun haku. 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.

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 erilainen. 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.

Tiedon tallennusmenetelmiä, joita kutsutaan "yksinkertaisiksi", eli jakamattomiksi osiin, kannattaa 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.

Ensin mainituilla 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 koon epävakaus, eli ohjelman suoritettaessa 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 esine.

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 tavallisten jonojen taustalla olevaa yksinkertaista sääntöä pidetään varsin 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 katsoa 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 oletuksen, että niiden välille luodaan analogia. Nimittäin yhdistetyillä ja samalla asyklisillä (ilman syklejä) kuvaajilla. Jälkimmäiset muistuttavat rakenteeltaan todella puita, mutta niissä on joitain eroja, esimerkiksi matemaattisia puita on tapana kuvata juurella yläosassa, 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 tiedolla on selkeä hierarkia. Esimerkiksi biologisia sukuja ja lajeja, työnimikkeitä, maantieteellisiä kohteita jne. koskevien tietojen käsittely edellyttää hierarkkisesti ilmaistua rakennetta, kuten matemaattisia puita.

Tietokoneen muistiin tallennetut tiedot ovat kokoelma nollia ja ykkösiä (bittejä). Bitit yhdistetään sekvensseihin: tavuja, sanoja jne. Jokaiselle RAM-muistin osalle, joka voi sisältää yhden tavun tai sanan, on määritetty järjestysnumero (osoite).

Mikä merkitys tiedoissa on, millä symboleilla ne ilmaistaan ​​- aakkosina tai digitaalisina, mitä tämä tai tuo numero tarkoittaa - kaikki tämä määritetään käsittelyohjelmalla. Kaikki käytännön ongelmien ratkaisemiseen tarvittava tieto on jaettu useisiin eri tyyppeihin ja käsitteeseen tyyppi ei liity ainoastaan ​​tietojen esittämiseen osoiteavaruudessa, vaan myös tapa käsitellä niitä.

Kaikki tiedot voidaan luokitella kahteen tyyppiin: perus (yksinkertainen), jonka esitystapa määräytyy tietokoneen arkkitehtuurin mukaan, tai monimutkainen, jonka käyttäjä on suunnitellut ratkaisemaan tiettyjä ongelmia.

Yksinkertaisia ​​tietotyyppejä ovat symbolit, numerot jne. elementtejä, joiden pirstoutuminen ei ole järkevää. Tietorakenteet (monimutkaiset tyypit) muodostetaan perustiedoista.

Jotkut rakenteet:

· Array(funktio, jolla on rajallinen määritelmäalue) - yksinkertainen kokoelma samantyyppisiä tietoelementtejä, keino toimia samantyyppisen tietoryhmän kanssa. Yksittäinen taulukkoelementti määritellään indeksillä. Taulukko voi olla yksiulotteinen, kaksiulotteinen jne. Vaihtelevan pituisten yksiulotteisten taulukoiden lajikkeet ovat tämän tyyppisiä rakenteita rengas, pino, jono ja deque.

· Ennätys(Karteesinen tuote) - kokoelma erityyppisiä tietoelementtejä. Yksinkertaisimmassa tapauksessa tietue sisältää vakiomäärän elementtejä, joita kutsutaan kentät. Kutsutaan kokoelma tietueita, joilla on sama rakenne tiedosto. (Tiedostoa kutsutaan myös tietojoukoksi ulkoisessa muistissa, esimerkiksi magneettilevyllä). Jotta tiedostosta voidaan poimia yksittäisiä tietueita, kullekin tietueelle annetaan yksilöllinen nimi tai numero, joka toimii sen tunnisteena ja sijaitsee erillisessä kentässä. Tätä tunnistetta kutsutaan nimellä avain.

Tietorakenteet, kuten taulukko tai tietue, vievät jatkuvasti tilaa tietokoneen muistissa, minkä vuoksi niitä kutsutaan staattisiksi rakenteiksi. Staattiset rakenteet sisältävät myös joukko.

On olemassa useita rakenteita, jotka voivat muuttaa pituuttaan - ns dynaamiset rakenteet. Näitä ovat puu, luettelo, linkki.

Tärkeä rakenne elementtien sijoittamiselle, joka vaatii epälineaarista osoiteavaruutta, on puu. On olemassa suuri määrä tietorakenteita, jotka voidaan esittää puina. Näitä ovat esimerkiksi luokittelu-, hierarkkiset, rekursiiviset ja muut rakenteet. Lisätietoja puista on kuvattu kohdassa 1.2.1.

Riisi. 1.1. Tietotyyppien luokittelu

1.1.2.Yleistetut rakenteet tai tietomallit.

Yllä tarkastelimme usean tyyppisiä rakenteita, jotka ovat tietoelementtien kokoelmia: taulukko, puu, tietue. Monimutkaisempi tietotyyppi saattaa sisältää nämä rakenteet elementteinä. Tietueen elementit voivat olla esimerkiksi taulukko, pino, puu jne.

Monimutkaisia ​​tietotyyppejä on monenlaisia, mutta laajalla käytännön materiaalilla tehdyt tutkimukset ovat osoittaneet, että niistä voidaan tunnistaa useita yleisimpiä. Yleistettyjä rakenteita kutsutaan myös tietomalleja, koska ne heijastavat käyttäjän näkemystä todellisesta datasta.

Jokaisen tietomallin tulee sisältää kolme osaa:

1. tietorakenne - kuvaa käyttäjän näkökulmaa tiedon esittämiseen.

2. joukko kelvollisia operaatioita suoritettavissa tietorakenteessa. Tietomalli olettaa ainakin niiden tallennuksen rakenteen kuvaavan datadefinition language (DLA) ja datan manipulointikielen (DML), joka sisältää toiminnot tietojen hakemiseksi ja muokkaamiseksi.

3. eheyden rajoituksia - mekanismi, jolla ylläpidetään aihealueen tietojen vaatimustenmukaisuutta muodollisesti määriteltyjen sääntöjen mukaisesti.

Historiallisen kehityksen aikana DBMS:ssä käytettiin seuraavia tietomalleja:

· hierarkkinen,

· verkko,

· suhteellinen.

Viime aikoina oliolähtöinen lähestymistapa tiedon esittämiseen on tullut yhä tärkeämmäksi.

1.2.Tietojen käyttötavat

Tiedon esittämiseen liittyvät ongelmat liittyvät läheisesti toimintoihin, joilla tietoja käsitellään. Tällaisia ​​operaatioita ovat: valinta, muutos, sisällyttäminen Ja poikkeus tiedot. Kaikki nämä toiminnot perustuvat operaatioon pääsy, jota ei voida ottaa huomioon esitystavasta riippumatta.

Hakuongelmissa oletetaan, että kaikki tiedot on tallennettu muistiin tietyllä tunnisteella ja kun puhutaan pääsystä, ne tarkoittavat ennen kaikkea pääsyä tietoihin (kutsutaan avaimiin), jotka yksilöivät niihin liittyvät tietojoukot.

Oletetaan, että meidän on järjestettävä pääsy tiedostoon, joka sisältää joukon identtisiä tietueita, joista jokaisella on yksilöllinen avainkentän arvo. Yksinkertaisin tapa etsiä on käydä läpi tiedoston jokainen tietue peräkkäin, kunnes löydät sellaisen, jonka avainarvo täyttää hakuehdot. Ilmeisesti tämä menetelmä on melko tehoton, koska tiedoston tietueita ei ole järjestetty avainkentän arvon mukaan. Tietueiden lajittelu tiedostossa ei myöskään ole käytännöllistä, koska se vie vielä enemmän aikaa ja se on tehtävä jokaisen tietueen lisäyksen jälkeen. Siksi ne etenevät seuraavasti - avaimet ja osoittimet tiedoston vastaaviin tietueisiin kopioidaan toiseen rakenteeseen, jonka avulla voit nopeasti suorittaa lajittelu- ja hakutoimintoja. Tietoa käsiteltäessä tästä rakenteesta löydetään ensin vastaava avainarvo ja sitten saadaan tietue tiedostosta sen mukana tallennetun osoittimen avulla.

On olemassa kaksi menetelmäluokkaa, jotka toteuttavat pääsyn tietoihin avaimella:

· puuhakumenetelmät,

· hajautusmenetelmiä.

1.2.1. Puuhakumenetelmät

Määritelmä: Puu on äärellinen joukko, joka koostuu yhdestä tai useammasta elementistä, joita kutsutaan solmuiksi, jolloin:

1. solmujen välillä on "lähde luotu" -tyyppinen suhde;

2. on vain yksi solmu, jolla ei ole lähdesolmua. Sitä kutsutaan juureksi;

3. kaikilla solmuilla, paitsi juurilla, on vain yksi lähde; jokaisella solmulla voi olla useita lapsisolmuja;

4. "alkuperäinen - luotu" -suhde toimii vain yhteen suuntaan, ts. ei solmun jälkeläisestä voi tulla sen esi-isä.

Yksittäisen solmun spawnien lukumäärää (tietyn juuren alipuiden lukumäärää) kutsutaan sen tutkinnon. Solmua, jonka aste on nolla, kutsutaan lehti- tai päätysolmuksi. Tietyn puun kaikkien solmujen maksimiastearvoa kutsutaan puun tutkinto.

Jos puussa luotujen solmujen välillä, joilla on yhteinen alku, niiden järjestystä pidetään merkittävänä, niin puuta kutsutaan tilattu. Hakuongelmat pitävät lähes aina tilattuja puita.

Järjestättyä puuta, jonka aste on enintään 2, kutsutaan binääri puu. Binääripuuta käytetään erityisen usein haettaessa RAM-muistista. Hakualgoritmi: Ensin hakuargumenttia verrataan juuressa olevaan avaimeen. Jos argumentti vastaa avainta, haku päättyy, mutta jos se ei täsmää, niin siinä tapauksessa, että argumentti on pienempi kuin avain, haku jatkuu vasemmassa alipuussa ja siinä tapauksessa, että se on suurempi kuin avain. avain oikeanpuoleisessa alipuussa. Kun tasoa on korotettu 1:llä, vertailu toistetaan pitäen nykyistä solmua juurina.

Esimerkki: Anna opiskelijoista luettelo, jossa on heidän sukunimensä ja keskiarvopisteensä (katso taulukko 1.1). Avaimena käytetään opiskelijan sukunimeä. Olettaen, että kaikilla tietueilla on kiinteä pituus, tietuenumeroa voidaan käyttää osoittimena. Tiedoston tietueen siirtymä lasketaan tässä tapauksessa muodossa ([tietueen_numero] -1) * [tietueen_pituus ] . Olkoon hakuargumentti "Petrov". Kuvassa 1.2 on esitetty yksi mahdollinen binäärihakupuu ja hakupolku tälle tietojoukolle.

Taulukko 1.1
Vasiljev
Kuznetsov
Tikhomirov

Riisi. 1.2. Binaaripuuhaku

Huomaa, että tässä käytetään seuraavaa merkkijonomuuttujien vertailusääntöä: oletetaan, että merkin arvo vastaa sen sarjanumeroa aakkosissa. Siksi "I" on pienempi kuin "K" ja "K" on pienempi kuin "C". Jos verrattujen merkkijonojen nykyiset merkit täsmäävät, seuraavissa kohdissa olevia merkkejä verrataan.

Binääripuut ovat erityisen tehokkaita, kun avainjoukko on tuntematon etukäteen tai kun tämä joukko muuttuu voimakkaasti. On selvää, että vaihtelevalla näppäinsarjalla on parempi olla tasapainoinen puu.

Määritelmä: Binääripuuta kutsutaan tasapainotetuksi, jos kunkin solmun vasemman alipuun korkeus eroaa oikean alipuun korkeudesta enintään 1.

Kun etsitään tietoja ulkoisesta muistista, VSD:ltä RAM-muistiin siirrettävien tietojen vähentämisongelma on erittäin tärkeä. Siksi tässä tapauksessa erittäin haarautuvat puut ovat kannattavampia verrattuna binääripuihin - koska Niiden korkeus on pienempi, silloin haku vaatii vähemmän pääsyä ulkoiseen muistiin. Tässä tapauksessa yleisimmin käytettyjä ovat B-puut (B - tasapainoinen)

Määritelmä: N-kertainen B-puu on vahvasti haarautunut 2n+1-asteinen puu, jolla on seuraavat ominaisuudet:

1. Jokainen solmu, paitsi juuri, sisältää vähintään n ja enintään 2n avainta.
2. Juuri sisältää vähintään yhden ja enintään 2n avainta.
3. Kaikki lehdet sijaitsevat samalla tasolla.
4. Jokainen välisolmu sisältää kaksi listaa: nouseva näppäinluettelo ja vastaava osoittimien luettelo (lehtisolmuille ei ole luetteloa osoittimista).

Tällaiselle puulle:

· Jaksottainen pääsy voidaan järjestää suhteellisen helposti, koska kaikki lehdet sijaitsevat samalla tasolla;

· kun lisäät ja vaihdat avaimia, kaikki muutokset rajoittuvat yleensä yhteen solmuun.

Riisi. 1.3. Tasapainoinen puu

SISÄÄN-kutsutaan puuta, jossa todelliset arvot sisältyvät vain lehtiin (päätesolmuihin). SISÄÄN +- puu. Tällaisen puun sisäiset solmut sisältävät erotinavaimet, jotka määrittävät alipuiden avainten muutosalueen.

Erilaisista tasapainopuista ja niiden toteuttamismenetelmistä voit lukea lisää kirjallisuudesta, josta on listattu sivun lopussa. On huomattava, että B- puut sopivat parhaiten vain melko yksinkertaisten (yksiulotteisten) tietorakenteiden pääsyn järjestämiseen. He ovat viime aikoina käyttäneet yhä enemmän monimutkaisempien rakenteiden, kuten spatiaalisen (moniulotteisen) tiedon R- puita.

R-puu ( R-Puu on A. Guttmanin (University of California, Berkeley) ehdottama hakemistorakenne paikkatietoihin pääsyä varten. R-tree mahdollistaa mielivaltaiset toiminnot tietojen lisäämiseksi, poistamiseksi ja etsimiseksi ilman säännöllistä uudelleenindeksointia.

Tietojen esittämiseen käytetään tietueita, joilla jokaisella on yksilöllinen tunniste (tuple-identifier). Jokainen puun päätesolmu (lehti) sisältää tietueen muodossa ( I, tuple-tunniste), Missä minä - n-ulotteinen kuutio, joka sisältää osoittimia paikkatietoihin (kutsutaan myös minimaaliseksi rajaavaksi suorakulmioksi, MBR) ja jokaisen elementin tuple-tunniste sisältää suuntaissärmiön ylä- ja alarajat vastaavassa ulottuvuudessa.

Muut kuin lehtisolmut sisältävät tietueita muodossa (I, lapsisolmuosoitin), Missä minä kaikkien tästä johdettujen solmujen MBR:n vähimmäisrajauslaatikko. Lapsisolmuosoitin on osoitin johdettuihin solmuihin.

Antaa M Ja m <= M/2 vastaavasti suurin ja pienin määrä elementtejä, jotka voidaan sijoittaa solmuun. Sitten R-puun ominaisuuksia voidaan kuvata seuraavasti:

· R-Tree on erittäin tasapainoinen puu, ts. kaikki lehdet ovat samalla tasolla.

· Juurisolmulla on vähintään kaksi lasta.

· Jokaiselle elementille (I, lapsisolmuosoitin) ei-päätesolmussa minä On pienin mahdollinen suuntaissärmiö, ts. sisältää kaikki johdettujen solmujen suuntaissärmiöt.

· Jokainen päätysolmu (lehti) sisältää from m ennen M hakemistomerkintöjä.

· Jokaiselle indeksimerkinnälle (I, tuple-tunniste) lopussa solmussa minä on suuntaissärmiö, joka sisältää n-ulotteinen tietoobjekti, johon osoitettiin tuple-tunniste .

1.2.2. Hashing

Tätä menetelmää käytetään, kun koko avainsarja tunnetaan etukäteen ja ne voidaan tallentaa RAM-muistiin käsittelyn ajaksi. Tässä tapauksessa rakennetaan erityinen funktio, joka yhdistää näppäinjoukon yksilöllisesti osoitinjoukkoon, jota kutsutaan hash-funktioksi (englannin sanasta "to hash" - leikkaa, leikkaa). Tällaisen toiminnon avulla voit laskea tietueen osoitteen tiedostossa käyttämällä annettua hakuavainta. Yleensä tietueen osoitteen määrittämiseen käytetyt avaintiedot on järjestetty taulukkoon, jota kutsutaan hash-taulukoksi.

Jos avainjoukko on tuntematon etukäteen tai se on erittäin suuri, hylätään ajatus tietueen osoitteen yksilöllisestä laskemisesta sen avaimesta ja hash-funktiota pidetään yksinkertaisesti funktiona, joka hajottaa avainjoukon joukko osoitteita.

• Käännös
• Palautus tila

Freelance-toimittaja Ekaterina Malakhova mukautti Beau Carnesin artikkelin tietorakenteiden päätyypeistä erityisesti Netology-blogia varten.

”Huono ohjelmoija ajattelee koodia. Hyvät ohjelmoijat ajattelevat tietorakenteita ja niiden suhteita." - Linus Torvalds, Linuxin luoja.

Tietorakenteilla on tärkeä rooli ohjelmistokehitysprosessissa, ja niitä kysytään usein myös kehittäjähaastatteluissa. Hyvä uutinen on, että ne ovat pohjimmiltaan vain erikoismuotoja tietojen järjestämiseen ja tallentamiseen.

Tässä artikkelissa näytän sinulle 10 yleisintä tietorakennetta. Jokaiselle niistä tarjotaan videoita ja esimerkkejä niiden toteutuksesta JavaScriptissä. Harjoittelun helpottamiseksi olen myös sisällyttänyt harjoituksia uuden freeCodeCamp-opetussuunnitelman beta-versiosta.

Artikkelissa annan esimerkkejä näiden tietorakenteiden toteuttamisesta JavaScriptissä. Ne ovat myös hyödyllisiä, jos käytät matalan tason kieltä, kuten C. Monissa korkean tason kielissä, mukaan lukien JavaScript, on jo sisäänrakennettu toteutus useimmista tietorakenteet, joista keskustelemme. Tällainen tieto on kuitenkin vakava etu työnhaussasi ja hyödyllistä kirjoitettaessa korkean suorituskyvyn koodia.

Linkitetyt listat

Linkitetty luettelo on yksi perustietorakenteista. Sitä verrataan usein taulukkoon, koska monet muut rakenteet voidaan toteuttaa joko taulukon tai linkitetyn listan avulla. Näillä kahdella tyypillä on etuja ja haittoja.

Näin linkitetty lista toimii

Linkitetty luettelo koostuu ryhmästä solmuja, jotka yhdessä muodostavat sekvenssin. Jokainen solmu sisältää kaksi asiaa: sen tallentaman todellisen datan (tämä voi olla mitä tahansa dataa) ja osoittimen (tai linkin) sekvenssin seuraavaan solmuun. On myös kaksinkertaisesti linkitettyjä listoja: niissä jokaisessa solmussa on osoitin sekä luettelon seuraavaan että edelliseen elementtiin.

Linkitetyn luettelon perustoimintoihin kuuluu elementin lisääminen, poistaminen ja etsiminen luettelosta.

Linkitetyn luettelon aika monimutkaisuus ═════════ ╗ ║ Algoritmi ║Keskiarvo ║ Huonoin tapaus ║ ╠═════════════════════════════════ ════════ ════ ╬═════════ ══════╣ ║ ║ O(n) ║ O(n) ║ O(n) ║ ║ O(n) ║ ert ║ O(1) ║ O(1) ║ ║ Poista ║ O (1) ║ O(1) ║ ╚═══════════╩════╩═══════════════════ ═ ═══╩════ ══════ ═════╝

Harjoituksia freeCodeCampista

Pinot

Pino on perustietorakenne, jonka avulla elementtejä voidaan lisätä tai poistaa vasta alussa. Se on kuin pino kirjoja: jos haluat katsoa kirjaa pinon keskellä, sinun on ensin poistettava päällä olevat kirjat.

Pino on järjestetty LIFO-periaatteen (Last In First Out) mukaan. Tämä tarkoittaa, että viimeinen elementti, jonka lisäät pinoon, irtoaa siitä ensimmäisenä.

Näin pino toimii

Pinot voivat suorittaa kolme toimintoa: elementin lisääminen (push), elementin poistaminen (pop) ja pinon sisällön näyttäminen (pip).

Pinon aika monimutkaisuus ════════╗ ║ Algoritmi ║Keskiarvo ║ Huonoin tapaus ║ ╠═══════════════════════════════════════════════ ═════════ ═ ╬══════════ ═════╣ ║ Välilyönti ║ O(n) ║ O(n) ║ ║ Haku ║ O(s)║ O(n) ) ║ O(1) ║ ║ Poista ║ O( 1) ║ O(1) ║ ╚═══════════╩═════════════════ ═══ ╩════ ═══════ ════╝

Harjoituksia freeCodeCampista

Jonot

Tätä rakennetta voidaan pitää linjana ruokakaupassa. Se, joka tuli aivan alussa, palvellaan ensin - aivan kuten elämässä.

Näin jono toimii

Jono on järjestetty FIFO-periaatteella (First In First Out). Tämä tarkoittaa, että voit poistaa elementin vasta, kun kaikki aiemmin lisätyt elementit on poistettu.

Jonon avulla voit suorittaa kaksi perustoimintoa: elementtien lisääminen jonon loppuun ( jonottaa) ja poista ensimmäinen elementti ( jonottaa).

Jonon aika monimutkaisuus ════════╗ ║ Algoritmi ║Keskiarvo ║ Huonoin tapaus ║ ╠════════════════════════════ ═════════ ═ ╬══════════ ═════╣ ║ Välilyönti ║ O(n) ║ O(n) ║ ║ Haku ║ O(s)║ O(n) ) ║ O(1) ║ ║ Poista ║ O( 1) ║ O(1) ║ ╚═══════════╩═════════════════ ═══ ╩════ ═══════ ════╝

Harjoituksia freeCodeCampista

Sarjat

Tältä moni näyttää

Joukko tallentaa data-arvot missään järjestyksessä toistamatta niitä. Sen lisäksi, että voit lisätä ja poistaa elementtejä, on useita muita tärkeitä toimintoja, joita voidaan soveltaa kahteen ryhmään kerralla.

• Liitto yhdistää kaikki elementit kahdesta eri joukosta yhdeksi (ilman kaksoiskappaleita).
• Leikkaus analysoi kahta joukkoa ja luo toisen niistä elementeistä, jotka ovat molemmissa alkuperäisissä joukoissa.
• Ero näyttää luettelon elementeistä, jotka ovat yhdessä joukossa mutta eivät toisessa.
• Osajoukko tuottaa Boolen arvon, joka osoittaa, sisältääkö yksi joukko toisen joukon kaikki elementit.

Esimerkki toteutuksesta JavaScriptissä

Harjoituksia freeCodeCampista

Kartta

Kartta on rakenne, joka tallentaa tiedot avain/arvo-pareihin, joissa jokainen avain on yksilöllinen. Joskus sitä kutsutaan myös assosiatiiviseksi taulukoksi tai sanakirjaksi. Karttaa käytetään usein tiedon nopeaan etsimiseen. Sen avulla voit tehdä seuraavat asiat:

• lisää pareja kokoelmaan;
• poista parit kokoelmasta;
• muuttaa olemassa olevaa paria;
• etsi tiettyyn avaimeen liittyvä arvo.

Näin karttarakenne toimii

Harjoituksia freeCodeCampista

Hash-taulukot

Näin hash-taulukko ja hash-funktio toimivat

Hash-taulukko on karttamainen rakenne, joka sisältää avain/arvo-pareja. Se käyttää hash-funktiota indeksin laskemiseen tietolohkojen joukkoon halutun arvon löytämiseksi.

Tyypillisesti hash-funktio ottaa merkkijonon syötteenä ja tulostaa numeerisen arvon. Samalle syötteelle hajautusfunktion pitäisi palauttaa sama numero. Jos kaksi eri syötettä tiivistetään samaan tulokseen, tapahtuu törmäys. Tavoitteena on, että tällaisia ​​tapauksia on mahdollisimman vähän.

Joten kun syötät avain/arvo-parin tiivistetaulukkoon, avain välitetään hash-funktion läpi ja muutetaan numeroksi. Tätä numeroa käytetään sitten varsinaisena avaimena, joka vastaa tiettyä arvoa. Kun syötät saman avaimen uudelleen, hash-funktio käsittelee sen ja palauttaa saman numeerisen tuloksen. Tätä tulosta käytetään sitten siihen liittyvän arvon etsimiseen. Tämä lähestymistapa lyhentää merkittävästi keskimääräistä hakuaikaa.

Hajautustaulukon aikamonimutkaisuus ═════════ ═╗ ║ Algoritmi ║Keskiarvo ║ Huonoin tapaus ║ ╠════════════╬══════════════ ════════ ════ ═╬════════ ═══════╣ ║ Välilyönti ║ O(n) ║ O(n) ║║║║║ ║ ║ Lisää ║ O(1) ║ O(n) ║ ║ Poista ║ O(1) ║ O(n) ║ ╚════════════════╩════╩═════════════════ ═ ════╩════ ═════ ══════╝

Harjoituksia freeCodeCampista

Binäärihakupuu

Binäärihakupuu

Puu on tietorakenne, joka koostuu solmuista. Sillä on seuraavat ominaisuudet:

• Jokaisella puulla on juurisolmu (yläosa).
• Juurisolmulla on nolla tai useampi alisolmu.
• Jokaisella lapsisolmulla on nolla tai useampi lapsisolmu ja niin edelleen.

Binäärihakupuulla on kaksi lisäominaisuutta:

• Jokaisella solmulla on enintään kaksi alisolmua (jälkeläisiä).
• Jokainen solmu on pienempi kuin sen lapset oikealla ja sen lapset vasemmalla ovat pienempiä kuin itseään.

Binaarihakupuiden avulla voit nopeasti etsiä, lisätä ja poistaa elementtejä. Ne on suunniteltu siten, että kunkin operaation aika on verrannollinen puun elementtien kokonaismäärän logaritmiin.

Binaarihakupuun aikamonimutkaisuus ════════ ╗ ║ Algoritmi ║Keskiarvo ║Pahin tapaus ║ ╠══════════════════════════════ ═══════ ═════ ╬═════════ ═════╣ ║ Välilyönti ║ O(n) ║ O(n) ║ ║ ║ O(n) ║ Lisää ║ o (log n) ║ o (n) ║ ║ Poista ║ o (log n) ║ o (n) ║ ╚═══════════╩═══════════ ══════╩════ ════ ══════╝

Harjoituksia freeCodeCampista

Etuliitteen puu

Etuliitepuu (ladattu) on eräänlainen hakupuu. Se tallentaa tiedot tarroihin, joista jokainen edustaa puun solmua. Tällaisia ​​rakenteita käytetään usein sanojen tallentamiseen ja niille pikahakujen tekemiseen - esimerkiksi automaattista täydennystoimintoa varten.

Näin etuliitepuu toimii

Jokainen solmu kielen etuliitepuussa sisältää yhden sanan kirjaimen. Muodostaaksesi sanan, sinun on seurattava puun oksia ohittaen yksi kirjain kerrallaan. Puu alkaa haarautua, kun kirjainten järjestys eroaa sen muista sanoista tai kun sana loppuu. Jokainen solmu sisältää kirjaimen (datan) ja Boolen arvon, joka osoittaa, onko se sanan viimeinen.

Katso kuvaa ja yritä muodostaa sanat. Aloita aina juurisolmusta ylhäältä ja jatka alaspäin. Tämä puu sisältää seuraavat sanat: pallo, maila, nukke, tee, dork, asuntolan, lähetä, tunne.

Harjoituksia freeCodeCampista

Binäärikasa

Binäärikeko on toinen puupohjainen tietorakenne. Jokaisella sen solmulla on enintään kaksi lasta. Se on myös täydellinen puu: tämä tarkoittaa, että kaikki sen tasot on täytetty kokonaan tiedoilla ja viimeinen on täytetty vasemmalta oikealle.

Näin minimi- ja maksimikasat toimivat

Binäärikeko voi olla joko minimi tai maksimi. Maksimikasossa minkä tahansa solmun avain on aina suurempi tai yhtä suuri kuin sen jälkeläisten avaimet. Pienessä kasassa kaikki toimii päinvastoin: minkä tahansa solmun avain on pienempi tai yhtä suuri kuin sen jälkeläisten avaimet.

Tasojen järjestys binäärikekassa on tärkeä, toisin kuin samalla tasolla olevien solmujen järjestys. Kuvassa näkyy, että kolmannen tason minimikasassa arvot ovat epäjärjestyksessä: 10, 6 ja 12.

Binäärikeon aika monimutkaisuus ═════════ ═╗ ║ Algoritmi ║ Keskiarvo ║ Huonoin tapaus ║ ╠════════════════ ═════════ 0 ║ Lisää ║ O(1) ║ O(log n) ║ ║ Poista ║ O(log n) ║ O(log n) ║ ║ Peek ║ O(1) ║ O(1) ║ ╚═══════ ══╩══════════ ════════—

Harjoituksia freeCodeCampista

Kaavio

Graafit ovat kokoelma solmuja (kärkipisteitä) ja niiden välisiä yhteyksiä (reunat). Niitä kutsutaan myös verkoiksi.

Kaaviot on jaettu kahteen päätyyppiin: suunnattuihin ja ohjaamattomiin. Suuntaamattomissa graafisissa solmujen välisillä reunoilla ei ole suuntaa, kun taas suunnattujen graafien reunoilla on.

Useimmiten kaavio esitetään kahdessa muodossa: se voi olla viereisyysluettelo tai viereisyysmatriisi.

Graafi vierekkäisyysmatriisina

Vierekkäisyysluetteloa voidaan pitää elementtiluettelona, ​​jossa yksi solmu on vasemmalla ja kaikki muut solmut, joihin se liittyy, oikealla.

Vierekkäisyysmatriisi on numeroiden ruudukko, jossa jokainen rivi tai sarake vastaa kaavion eri solmua. Rivin ja sarakkeen leikkauskohdassa on numero, joka osoittaa yhteyden olemassaolon. Nollat ​​tarkoittavat, että se puuttuu; yksiköt - että yhteys on olemassa. Kunkin yhteyden painon ilmaisemiseksi käytetään numeroita, jotka ovat suurempia kuin yksi.

Graafissa on erityisalgoritmeja reunojen ja kärkien katseluun – ns. traversal-algoritmeja. Niiden päätyyppejä ovat laajakuvahaku ( leveys ensimmäinen haku) ja syvältä ( syvähaku). Vaihtoehtoisesti niitä voidaan käyttää määrittämään, kuinka lähellä tietyt graafin kärjet ovat juurisolmua. Alla oleva video näyttää, kuinka tehdä laajuushaku JavaScriptissä.