Arvuti mällu info salvestamise vajalik tingimus on just see info teisendamine arvutile sobivasse vormi. Kui see tingimus on täidetud, on vaja kindlaks määrata struktuur, mis sobib spetsiaalselt olemasoleva teabe jaoks, mis tagab sellega töötamiseks vajalikud võimalused.

helinanimekiri

Struktuuri all mõistetakse siin info esitamise viisi, mille kaudu moodustab üksikute elementide tervik omavahelise suhte tõttu midagi ühtset. Teatud reeglite järgi korraldatud ja omavahel loogiliselt ühendatud andmeid saab töödelda väga tõhusalt, kuna nende ühine struktuur pakub nende haldamiseks valikuvõimalusi - üks asju, mille tõttu teatud probleemide lahendamisel saavutatakse kõrgeid tulemusi.

Kuid mitte kõiki objekte ei esitata suvalisel kujul ja võib-olla on selle jaoks üldse ainult üks tõlgendusmeetod, seetõttu on kõigi olemasolevate andmestruktuuride tundmine programmeerija jaoks vaieldamatu eelis. Seega tuleb sageli teha valik erinevate teabe salvestamise viiside vahel ning sellisest valikust sõltub toote jõudlus.

Kui rääkida mittearvutitehnoloogiast, siis pole võimalik näidata mitte ühtegi juhtumit, kus teabel on selge struktuur. Heaks näiteks on väga erineva sisuga raamatud. Need on jagatud lehekülgedeks, lõikudeks ja peatükkideks, neil on tavaliselt sisukord ehk liides nende kasutamiseks. Laias laastus on igal elusolendil struktuur, ilma selleta oleks orgaanika vaevalt võimalik eksisteerida.

Tõenäoliselt on lugejal tulnud arvutiteaduses vahetult kokku puutuda andmestruktuuridega, näiteks nendega, mis on programmeerimiskeelde sisse ehitatud. Neid nimetatakse sageli andmetüüpideks. Nende hulka kuuluvad: massiivid, numbrid, stringid, failid jne.

Teabe salvestamise meetodeid, mida nimetatakse "lihtsateks", st jagamatuteks selle koostisosadeks, on eelistatav uurida koos konkreetse programmeerimiskeelega või süveneda nende töö olemusse. Seetõttu käsitletakse siin ainult "integreeritud" struktuure, neid, mis koosnevad lihtsatest, nimelt: massiivid, loendid, puud ja graafikud.

Massiivid.

Massiiv on andmestruktuur, millel on fikseeritud ja järjestatud sarnaste elementide (komponentide) komplekt. Juurdepääs mis tahes massiivi elemendile toimub selle elemendi nime ja numbri (indeksi) järgi. Indekside arv määrab massiivi mõõtme. Nii on näiteks kõige levinumad ühemõõtmelised (vektorid) ja kahemõõtmelised (maatriksid) massiivid.

Esimestel on üks indeks, teisel kaks. Olgu ühedimensiooniline massiiv nimeks A, siis selle i-ndale elemendile juurdepääsu saamiseks peate määrama massiivi nime ja vajaliku elemendi numbri: A[i]. Kui A on maatriks, esitatakse see tabelina, mille elementidele pääseb juurde massiivi nime, samuti selle rea ja veeru numbrid, mille ristumiskohas element asub: A, kus i on rea number, j on veeru number.

Erinevates programmeerimiskeeltes võib massiividega töötamine mõnevõrra erineda, kuid põhiprintsiibid on reeglina igal pool samad. Pascalis pääseb ühe- ja kahemõõtmelistele massiividele ligi täpselt nii, nagu ülal näidatud, kuid näiteks C++ puhul tuleks kahemõõtmeline massiiv määrata nii: A[i][j]. Massiivi elemendid nummerdatakse järjestikku. Programmeerimiskeel mõjutab nummerdamise algust. Enamasti on see väärtus 0 või 1.

Kirjeldatud tüüpi massiive nimetatakse staatilisteks, kuid on ka massiive, mis erinevad neist teatud mõttes: dünaamilised ja heterogeensed. Esimese dünaamilisust iseloomustab suuruse volatiilsus, st programmi töötamise ajal võib dünaamilise massiivi suurus muutuda. Selline funktsioon muudab andmetega töötamise paindlikumaks, kuid samas tuleb ohverdada kiirus ning protsess ise muutub keerulisemaks.

Staatilise massiivi kohustuslik kriteerium, nagu öeldud, on sellesse korraga salvestatud andmete homogeensus. Kui see tingimus ei ole täidetud, on massiiv heterogeenne. Selle kasutamine on tingitud eelmises vormis esinevatest puudustest, kuid see on paljudel juhtudel õigustatud.

Seega, isegi kui olete struktuuri üle otsustanud ja valinud massiivi, ei piisa sellest ikkagi. Lõppude lõpuks on massiiv ainult üldine tähistus, teatud arvu võimalike rakenduste perekond. Seetõttu on vaja otsustada konkreetne esitusmeetod kõige sobivama massiiviga.

Loendid.

Loend on abstraktne andmetüüp, mis rakendab järjestatud väärtuste komplekti. Loendid erinevad massiividest selle poolest, et nende elementidele pääseb juurde järjestikku, samas kui massiivid on juhusliku juurdepääsu andmestruktuur. Sellel abstraktsel tüübil on mitu rakendust andmestruktuuride kujul. Mõned neist vaadatakse siin üle.

Loend (lingitud loend) on andmestruktuur, mis on järjestatud elementide lõplik kogum, mis on omavahel seotud osutite abil. Struktuuri iga element sisaldab välja teatud teabega, samuti kursorit järgmisele elemendile. Erinevalt massiivist pole loendi elementidele juhuslikku juurdepääsu.

üksikult lingitud loend

Ülaltoodud üksikult lingitud loendis on esialgne element Head-loend (loendi pea [suvaline nimi]) ja kõike muud nimetatakse sabaks. Loendi saba koosneb elementidest, mis on jagatud kahte ossa: teave (infoväli) ja register (järgmine väli). Viimane element sisaldab kursori asemel loendi lõpu märki null.

Üksiklingitud loend pole eriti mugav, kuna ühest punktist on võimalik jõuda ainult järgmisse punkti, liikudes sellega lõppu. Kui lisaks järgmisele elemendile osutavale kursorile on kursor eelmisele, nimetatakse sellist loendit kahekordseks lingiks.

topeltlingitud loend

Võimalus liikuda nii edasi kui ka tagasi on mõne toimingu puhul kasulik, kuid lisaosutajad nõuavad rohkem mälu, kui on vaja samaväärses üksikult lingitud loendis.

Eespool kirjeldatud kahte tüüpi loendite jaoks on alamtüüp, mida nimetatakse ringloendiks. Saate muuta üksikult lingitud loendi ringikujuliseks loendiks, lisades viimasele elemendile vaid ühe osuti, nii et see osutab esimesele. Ja topeltühendatud elemendi jaoks on vaja kahte osutit: esimesele ja viimasele elemendile.

helinanimekiri

Lisaks vaadeldavatele loendistruktuuride tüüpidele on andmete korraldamiseks loendi tüübi järgi ka muid viise, kuid need on reeglina paljuski sarnased sõelutud struktuuridega, seega jäetakse need siin välja.

Lisaks suhete erinevustele on loendid jagatud andmetega töötamise meetodite järgi. Mõnda neist meetoditest käsitletakse allpool.

Virna.

Virna

Pinu iseloomustab asjaolu, et selle elemendile pääseb ligi ainult ühest otsast, mida nimetatakse virna ülaosaks, ehk teisisõnu: pinu on andmestruktuur, mis toimib LIFO põhimõttel (last in - first out, " viimane sisse – esimene välja"). Parem on seda andmestruktuur kujutada vertikaalse loendina, näiteks mõne asjade virna, kuhu ühe neist kasutamiseks peate üles korjama kõik selle kohal olevad asjad ja saate panna ainult objekti virna peal.

Näidatud üksikult lingitud loendis toimuvad toimingud elementidega rangelt ühest otsast: soovitud elemendi lisamiseks viiendasse lahtrisse on vaja sellel positsioonil olev element välja jätta. Kui elemente oleks näiteks 6 ja viiendasse lahtrisse oleks vaja sisestada ka konkreetne element, siis tuleks juba kaks elementi välja jätta.

Järjekord.

Queue andmestruktuur kasutab FIFO (First In, First Out) korralduspõhimõtet. Mõnes mõttes on see meetod õiglasem kui see, millel virn toimib, sest lihtsat reeglit, mis on erinevate kaupluste, haiglate tavapäraste järjekordade aluseks, peetakse üsna õiglaseks ja just see on selle struktuuri aluseks. Olgu see tähelepanek eeskujuks. Rangelt võttes on järjekord loend, mille elementide lisamine on lubatud ainult selle lõpus ja nende ekstraheerimine toimub teisel poolel, mida nimetatakse loendi alguseks.

Järjekord

dets

Dec (deque - kahe otsaga järjekord, "kahesuunaline järjekord") - kahe otsaga virn. Tõepoolest, vaatamata konkreetsele tõlkele, saab deque'i määratleda mitte ainult kahesuunalise järjekorrana, vaid ka virna, millel on kaks otsa. See tähendab, et selline loend võimaldab lisada elemente algusesse ja lõppu ning sama kehtib ekstraheerimistoimingu kohta.

dets

See struktuur töötab korraga kahel viisil andmete korraldamiseks: FIFO ja LIFO. Seetõttu võib selle omistada eraldi programmiüksusele, mis on saadud kahe eelneva loenditüübi summeerimise tulemusena.

Loeb.

Diskreetse matemaatika haru, mis tegeleb graafide uurimisega, nimetatakse graafiteooriaks. Graafiteoorias käsitletakse üksikasjalikult nende matemaatiliste objektide üldtuntud mõisteid, omadusi, esitusviise ja rakendusi. Meid huvitavad ainult need aspektid, mis on programmeerimises olulised.

Graafik on joontega ühendatud punktide kogum. Punkte nimetatakse tippudeks (sõlmedeks) ja sirgeid servadeks (kaaredeks).

Nagu jooniselt näha, on kahte peamist tüüpi graafikuid: suunatud ja suunamata. Esimeses on servad suunatud, st kahe ühendatud tipu vahel on ainult üks suund, näiteks võib minna tipust 1 tippu 2, aga mitte vastupidi. Suunamata ühendatud graafis saate liikuda igast tipust igasse ja tagasi. Nende kahe tüübi erijuhtum on segagraafik. Seda iseloomustab nii suunatud kui ka suunamata servade olemasolu.

Tipu sisenemisaste on sinna sisenevate servade arv, väljumise aste on väljuvate servade arv.

Graafi servad ei pea olema sirged ja tipud on tähistatud numbritega, nagu on näidatud joonisel. Lisaks on veel selliseid graafikuid, mille servadele omistatakse konkreetne väärtus, neid nimetatakse kaalutud graafikuteks ja see väärtus on serva kaal. Kui serva mõlemad otsad langevad kokku, st serv väljub tipust F ja siseneb sinna, siis nimetatakse sellist serva silmuseks.

Graafikuid kasutatakse laialdaselt inimeste loodud struktuurides, nagu arvuti- ja transpordivõrgud ning veebitehnoloogiad. Spetsiaalsed esitusmeetodid võimaldavad kasutada graafikut informaatikas (arvutites). Tuntuimad neist on: Adjacency Matrix, Incident Matrix, Adjacency List, Edge List. Esimesed kaks, nagu nimigi ütleb, kasutavad graafiku esitamiseks maatriksit ja kaks viimast loendit.

puud.

tellimata puu

Puu kui matemaatiline objekt on abstraktsioon sarnastest looduses leiduvatest ühikutest. Looduslike puude struktuuri sarnasus teatud tüüpi graafikutega viitab nendevahelise analoogia loomise eeldusele. Nimelt ühendatud ja samas atsükliliste (tsükliteta) graafikutega. Viimased meenutavad oma struktuurilt tõesti puid, kuid on mõningaid erinevusi, näiteks on kombeks kujutada matemaatilisi puid, mille juur asub tipus, see tähendab, et kõik oksad “kasvavad” ülalt alla. Teame, et looduses see nii ei ole.

Kuna puu on oma olemuselt graafik, kattuvad paljud selle määratlused viimasega või on intuitiivselt sarnased. Seega on puustruktuuri juursõlm (tipp 6) ainus tipp (sõlm), mida iseloomustab esivanemate puudumine, st selline, et sellele ei viita ükski teine ​​​​tipp ja juursõlmest endast on võimalik jõuda ükskõik millisesse saadaolevasse tippu. puu, mis tuleneb selle struktuuri ühenduvusomadusest. Sõlme, mis ei viita ühelegi teisele sõlmele, teisisõnu, millel pole lapsi, nimetatakse lehtedeks (2, 3, 9) või terminalisõlmedeks. Juuresõlme ja lehtede vahel asuvad elemendid on vahesõlmed (1, 1, 7, 8). Igal puusõlmel on ainult üks esivanem või kui see on juursõlm, siis pole sellel ühtegi.

Alampuu on osa puust, mis sisaldab mõnda juursõlme ja kõiki selle järeltulijaid. Nii näiteks sisaldab joonisel üks alampuu juurt 8 ja elemente 2, 1, 9.

Puuga saab teha palju toiminguid, näiteks elementide leidmine, elementide ja alampuude kustutamine, alampuude sisestamine, mõne tipu juursõlmede leidmine jne.Üks olulisemaid toiminguid on puu läbimine. On mitmeid lahendusmeetodeid. Kõige populaarsemad neist on: sümmeetriline, edasi- ja tagurpidi ümbersõit. Edasiliikumise korral külastatakse esivanemate sõlmi enne nende järeltulijaid, vastupidisel läbimisel aga vastupidine. Sümmeetrilisel läbimisel skaneeritakse ükshaaval peapuu alampuud.

Andmete esitamine vaadeldavas struktuuris on kasulik, kui teabel on selge hierarhia. Näiteks perekondade ja liikide, ametinimetuste, geograafiliste tunnuste jms andmetega töötamiseks on vaja hierarhiliselt väljendatud struktuuri, näiteks matemaatilisi puid.

ANDMETÜÜBID JA STRUKTUURID

Juhised erialale "Algoritmid ja andmestruktuurid"

Koostanud O.L. Tšagajeva

Koostanud osakond "Tarkvara ja süsteemid" FED UrFU

Sissejuhatus

IN Meid ümbritsevas maailmas on teabe kaudu kuvatud tohutult erinevaid objekte, objekte, nähtusi, protsesse.

Igal teabega esindatud olemil (objektil, nähtusel) on mitmeid talle iseloomulikke omadusi (tunnused, märgid, parameetrid, omadused, momendid). Näiteks materjali omadused on selle kaal, mõõtmed, mark, hind, kauba number jne. Omadused-omadused, mis iseloomustavad sellist üksust kui ostuorganisatsiooni, on nimi, osakonna kuuluvus, aadress, arvelduskonto number osariigis Pank jne.

Füüsilise olemi omadused kuvatakse muutujate abil, mis on elementaarsed teabeühikud ja mida nimetatakse atribuutideks.

Rekvisiit on mis tahes keeruka teabekogumi loogiliselt jagamatu element, mis on korrelatsioonis teabe kuvatava objekti või protsessi teatud omadusega.

IN töödeldud informatsiooni üksikasjad on kujutatud justkui "aatomitena", millest on kokku pandud kogu ülejäänud, informatsiooni moodustamise struktuuri poolest keerulisem. Ja vastupidi, mis tahes keerukusega teabeühikuid saab järjestikku lagundada koostisosadeks ja lõpuks jagada sellisteks komponentideks - muutujateks, mida ei saa täiendavalt loogiliselt jagada. Sellised elementaarsed komponendid on rekvisiidid.

Teised kirjanduses sageli kasutatavad rekvisiitide sünonüümid on element, väli, termin, atribuut ja atribuut .

Igal rekvisiidil on nimi. Algoritmiseerimisel ja programmeerimisel kasutatakse kompaktse kirjutamise eesmärgil kõige sagedamini lühendeid. nimed-identifikaatorid, konkreetsete rakendustega, mis üldiselt piiravad nende pikkust, tähestikku ja ulatust. Teatud juhtudel on lubatud kasutada ka detailide nimetuste sünonüüme, sh selliseid täisnimesid, mida kasutatakse ainult välistes dokumentides, näiteks aruande veergude pealkirjadena.

Igal atribuudil on teatud piiratud väärtuste kogum, mis sõltub selle atribuuti informatiivselt kuvava objekti (nähtuse) selle omaduse omadustest. See on komplekt, mida nimetatakse väärtuste klassiks, millest üks on näiteks parameetri "patsiendi temperatuur" ja teine ​​funktsiooni "patsiendi sugu" jaoks.

Seetõttu on atribuudi väärtus igal ajahetkel selle atribuudi väärtuste klassi üks positsioone, mis ootuspäraselt peegeldab objekti selle omaduse vastavat olekut (olekute hulgast). (nähtus), mis atribuuti iseloomustab. Seega võib muutuja "patsiendi temperatuur" praegune väärtus olla 37,4 ° ja muutuja "patsiendi sugu" - "mees". Teisisõnu kasutatakse atribuudi väärtust vastava olemi atribuudi väärtuse esitamiseks.

Olenevalt väärtustest, mis neil võivad olla, on mitmeid atribuutide tüüpe. Kõige levinumad rekvisiiditüübid on aga numbriline ja tekst.

Numbritüüpi rekvisiidid iseloomustavad olemite kvantitatiivseid omadusi, mis on saadud looduslike ühikute loendamise, mõõtmise, kaalumise, muude kvantitatiivsete summaandmete alusel arvutamise jms tulemusel. Seetõttu on selliste rekvisiitide väärtused arvud koos kõigi nende tunnustega. omadused ja atribuudid.

Konkreetsetes esitustes esinevad mitut tüüpi arvsuurused, olenevalt numbriklassist, numbrisüsteemist, koma fikseerimisest, pakkimisest ja muust; piirangud on seatud arvude vahemikule, nende esitusvormingutele sisendväljundis ja erinevatele andmekandjatele isegi sama teostuse piires. Kuna kõiki numbritüüpi atribuute kasutatakse aktiivselt erinevates aritmeetilistes operatsioonides ja enamik neist luuakse üldjuhul selliste tehtete tulemusel, tuleks alati meeles pidada neid erinevusi ja piiranguid, aga ka vajadust sobiva teisendusaparaadi järele. .

Tekstitüüpi rekvisiidid väljendavad reeglina olemite kvalitatiivseid omadusi ja iseloomustavad asjaolusid, milles uuritav protsess toimus ja teatud

muud arvväärtused. Seetõttu nimetatakse selliseid detaile tunnusteks.

Funktsioonide väärtused on tähemärkide jadad (tähed, numbrid, erinevad märgid ja erisümbolid), mida nimetatakse stringideks või tekstiks.

Teatud infosüsteemi erinevate paarikaupa eristatavate sümbolite komplekt moodustab selle tähestiku, mis sõltub ülesannete iseloomust, kasutatavatest andmetöötluse tehnilistest vahenditest ja muudest teguritest. Pealegi on töötlemise erinevates etappides ja isegi samas arvutisüsteemis võimalik kasutada erinevaid tähestikke.

Tähestiku suurus (erinevate märkide arv, mis võib olla ühes väärtuse bitis) ja selle koostis (komplekt) on otseselt seotud järgmiste probleemide lahendamisega:

kodeerimine ja dekrüpteerimine,

teabeühikute väärtuste kompaktne märge,

andmete tõhus salvestamine, nende otsingu kiirendamine, edastamine, arvutisse sisestamine,

masinatelt teabe saamine tarbimiseks kõige mugavamal kujul,

igasuguste ümberkirjutamiste kulude vähendamine.

Seetõttu pole tähestiku valikul vähe tähtsust.

Informatsiooni kasutamisel algoritmiseerimisel ja programmeerimisel omistatakse suurt tähtsust sellistele mõistetele nagu antud tüüp ja struktuur.

1. ANDMETÜÜBID

Arvutusprotsess arvutis realiseerub teatavasti programmide ja andmete abil. Programm ise on samuti andmetega. Seetõttu võime öelda, et andmed kirjeldavad igasugust teavet, millega arvuti saab töötada. Samas mõistetakse informatsiooni all mis tahes fakte ja teadmisi reaalse maailma objektide, protsesside ning nendevaheliste suhete ja seoste kohta. Kõiki andmeid iseloomustavad mitmed atribuudid (omadused, üksikasjad), sealhulgas väärtus.

Lisaks tähendusele hõlmavad sellised tunnused mõistet "andmetüüp". Antud tüübi määrab antud väärtuste kogum ja toimingute kogum, mida saab nende väärtustega teha vastavalt nende teadaolevatele omadustele. Seetõttu määrab andmetüüp toimingud, mis on vastava väärtusega lubatud.

Programmeerimiskeeled kasutavad tavaliselt selliseid levinud andmetüüpe nagu täisarvud, reaalarvud, märgid, bitid, osutid jne.

2. ANDMESTRUKTUURID

Selle konkreetse tüübi tunnuseks on organisatsiooni lihtsus (struktureerimata).

Andmestruktuur on andmeelementide kogum, mille vahel on mingid seosed ning andmeelemendid võivad olla nii lihtandmed (skalaarid) kui ka andmestruktuurid.

Seega saab struktuuri defineerida järgmiselt: S = (D, R), kus D on andmeelementide hulk, R on andmeelementide vaheliste seoste kogum.

Kõik ühe andmeelemendi lingid teistele moodustavad vastava andmeelemendiga seotud seoseelemendi.

Struktuuri graafiline esitus peaks peegeldama selle andmeelemente ja seoseid (nendevahelisi seoseid), mistõttu on struktuuri mugav kujutada graafikuna. Graafi tippe saab sel juhul tõlgendada andmeelementidena ning andmeelementide vahelised seosed vastavad orienteeritud kaaridele või suunamata servadele (joonis 1).

Nii kirjeldatud ja kujutatud andmestruktuuri nimetatakse abstraktseks või loogiliseks, kuna seda käsitletakse sõltumata selle esitusest masina mälus. Kuid igasugune andmestruktuur peab olema esindatud masina mälus. Sellist andmestruktuuri nimetatakse füüsiliseks struktuuriks, salvestusstruktuuriks, sisestruktuuriks või mälustruktuuriks.

Joonis 1. Suunamata (a) ja suunatud (b) graafik

Seega peegeldab füüsiline andmestruktuur seda, kuidas andmeid masina mälus esitatakse.

Üldjuhul on loogilise ja sellele vastava füüsilise struktuuri vahel erinevus, mille aste sõltub struktuurist endast ja füüsilise keskkonna omadustest, milles see peaks peegelduma.

Näiteks programmeerimiskeelte seisukohast on kahemõõtmeline massiiv ristkülikukujuline tabel ja mälus lineaarne lahtrite jada, millest igaüks salvestab ühe massiivi elemendi väärtuse ja massiivi elemendid. on järjestatud ridadesse (või veergudesse).

Loomulikult peab loogilise ja füüsilise struktuuri vahel olema mehhanism, mis võimaldab kaardistada loogilise struktuuri füüsilisega.

Seega saab iga andmestruktuuri iseloomustada selle loogilise (abstraktse) ja füüsilise (konkreetse) esituse ning ka nende kahe struktuuri esituse taseme operatsioonide kogumiga (joonis 2).

Tehted loogilisel struktuuril

Loogiline andmestruktuur

Toimingud füüsilise struktuuriga

Füüsiline andmestruktuur

Riis. 2. Andmestruktuuri loogilise ja füüsilise esituse vaheline kaardistamine

2.1. Andmestruktuuride klassifikatsioon

IN Sõltuvalt andmeelementide vaheliste selgelt määratletud linkide puudumisest või olemasolust tuleks eristada mitteseotud struktuure (vektorid, massiivid, stringid, virnad, järjekorrad) ja ühendatud struktuure (lingitud loendid).

Struktuuri oluliseks tunnuseks on selle muutlikkus – muutus elementide arvus ja/või struktuuri elementide omavahelistes suhetes. Andmeelemendi väärtust ei peeta silmas, kuna sel juhul oleks see omadus omane kõikidele andmestruktuuridele, välja arvatud konstandid ja ROM-i salvestatud andmed. Muutuvuse alusel eristatakse staatilisi, poolstaatilisi ja dünaamilisi struktuure.

Andmestruktuuri oluline tunnus on selle elementide järjestuse iseloom. Selle alusel saab struktuure jagada lineaarselt järjestatud ehk lineaarseteks ja mittelineaarseteks.

Sõltuvalt elementide vastastikuse paigutuse olemusest mälus saab lineaarsed struktuurid jagada struktuurideks, mille elemendid jaotuvad mälus järjestikku (vektorid, stringid, massiivid, virnad, järjekorrad) ja struktuurideks, mille elemendid on suvalise ühendatud jaotusega. mälu (üksikühendusega, topeltühendatud, tsükliliselt ühendatud, seoste loendid). Mittelineaarsete struktuuride näited on lingitud loendid, puustruktuurid ja üldised graafistruktuurid.

2.2. Lihtsamad staatilised struktuurid

TO Lihtsamad andmestruktuurid on tavaliselt vektorid, massiivid, kirjed, tabelid. Neid iseloomustavad järgmised omadused:

konstruktsiooni püsivus kogu selle eksisteerimise aja jooksul;

elementide külgnevus ja mäluala järjepidevus, mis eraldatakse koheselt kõikidele struktuurielementidele; elementidevaheliste suhete lihtsus ja püsivus

struktuurid, mis võimaldavad välistada info nende seoste kohta struktuurielementidele eraldatud mälualast ja salvestada seda näiteks kompaktsel kujul deskriptorites.

Nende omaduste tõttu peetakse vektoreid, massiive, kirjeid ja tabeleid staatilisteks struktuurideks.

2.2.1. Vektor

Vektor on sama tüüpi lihtsate andmete või skalaaride piiratud järjestusega kogum. Geomeetrilisest vaatenurgast määrab vektor punkti mitmemõõtmelises ruumis, mille koordinaadid on vektori elementide väärtused.

Vektori elemendid on üksteisega ainsas võimalikus suhtes – otseses järgnevuses. Vektorelementide range jada võimaldab

nummerdage need järjestikuste täisarvudega - indeksid. Vektori loogilist struktuuri kirjeldab täielikult selle elementide arv ja tüüp. Näiteks int massiiv on 10 elemendiga täisarvu massiiv.

Kõige olulisem toiming vektoriga on juurdepääs selle elementidele. Kui elemendile on juurdepääs, saab sellega teha mis tahes toimingu, mis on valitud andmetüübi jaoks mõistlik.

Loogilisel tasandil piisab vektori elemendile juurdepääsuks vektori nime ja vastava elemendi indeksi väärtuse määramisest. Näiteks: massiiv + massiiv.

Vektori füüsiline struktuur on võrdse pikkusega mälulõikude jada, mida nimetatakse väljadeks või pesadeks, millest igaüks on mõeldud ühe vektori elemendi salvestamiseks. Väli võib olla minimaalse adresseeritava mäluelemendi suurus või vastata tervele järjestikuste mälurakkude rühmale.

Pole harvad juhud, kui füüsiline struktuur on seotud deskriptori või päisega, mis sisaldab teavet selle füüsilise struktuuri kohta. Deskriptor on vajalik näiteks juhul, kui vektori piirmõõtmed saavad teada alles programmi täitmise etapis.

Deskriptor salvestatakse ka masina mällu ja see on struktuur, mida nimetatakse kirjeks. Vektori puhul salvestab deskriptor tavaliselt selle nime, suuruse, piiriindeksi väärtused, elemendi tüübi, välja või pilu suuruse, vektori esimese elemendi aadressi (välja, mis seda elementi salvestab).

2.2.2. massiivi

Massiiv on vektor, mille iga element on vektor. Omakorda võivad massiivi elemendiks oleva vektori elemendid olla ka vektorid. Üleminek elemendilt selle elemendi elemendile ja nii edasi peab varem või hiljem lõppema mingit andmetüübi skalaariga ja kõik massiivi skalaarelemendid peavad sellele tüübile vastama (joonis 3).

Riis. 3. Mitmemõõtmelise massiivi vaade

Joonisel 3 on kujutatud mitmemõõtmelise massiivi vaade: võre iga sõlm sisaldab massiivi elementi. Seega on selle mõõde võrdne (3,3,2).

Nagu vektori puhul, on massiivi kõige olulisem elementaarne toiming selle elemendile ligipääs. Loogilise struktuuri tasandil viiakse see läbi massiivi nime ja järjestatud indeksite komplekti kasutades, mis identifitseerivad üheselt massiivi elemendi. Näiteks: massiiv[i][j].

Erinevalt vektorist on üldmassiivi puhul loogilise struktuuri teisendamine füüsiliseks keerulisem. See teisendus viiakse läbi lineariseerimisprotsessi abil, mis kaardistab massiivi mitmemõõtmelise loogilise struktuuri ühemõõtmeliseks füüsiliseks struktuuriks. See füüsiline struktuur on lineaarselt järjestatud massiivi elementide jada. Seega on mitmemõõtmelise massiivi füüsiline struktuur sarnane vektori füüsilisele struktuurile.

Sellest hoolimata erineb mitmemõõtmeline massiivi käepide vektorkäepidemest. Näiteks peaks see salvestama teavet massiivi mõõtmete, elementide järjestamise (ridade või veergude kaupa) kohta.

2.2.3. Salvestamine

Kirje on piiratud järjestatud elementide kogum, mis sisaldab üldiselt erinevat tüüpi andmeid.

Kirje elemente nimetatakse sageli väljadeks. Kirje on vektori üldistatud mõiste, mis ei nõua ühtlust ega

Andmestruktuuri mõiste on nii fundamentaalne, et sellele on raske lihtsat definitsiooni leida. Ülesanne on lihtsustatud, kui proovime sõnastada seda mõistet seoses andmetüüpide ja muutujatega. Teatavasti on programm algoritmi (protseduurid, funktsioonid) ja nende poolt töödeldavate andmete ühtsus. Andmed on omakorda defineeritud baas- ja tuletatud andmetüüpidega – fikseeritud mõõtmetega muutujate "ideaalsed" esitused koos nende ja nende komponentide teadaolevate operatsioonide komplektidega. Muutujad on nimega mälupiirkonnad, kuhu konstrueeritud andmetüübid "kaardistatakse".
Programmis on alati võimalik eristada kaudselt seotud (kasutades andmeid samades protseduurides ja funktsioonides) ja otseselt seotud (osutite kaudu seoste olemasoluga) muutujate rühmi. Esimese lähendusena võib neid pidada andmestruktuurideks.

Andmestruktuure on LIHTNE (põhiline, primitiivne) ja INTEGREERITUD (struktureeritud, komposiit, kompleks). Lihtsad andmestruktuurid on need, mida ei saa jagada bitidest suuremateks osadeks. Füüsilise ülesehituse seisukohalt on oluline, et antud masinaarhitektuuris, antud programmeerimissüsteemis saaksime alati ette öelda, milline saab olema antud lihttüübi suurus ja milline on selle paigutuse struktuur. mälestus saab olema. Loogilisest vaatenurgast on lihtsad andmed jagamatud ühikud. Integreeritud andmestruktuurid on sellised andmestruktuurid, mille komponentideks on muud andmestruktuurid – lihtsad või omakorda integreeritud. Integreeritud andmestruktuure konstrueerib programmeerija, kasutades programmeerimiskeelte pakutavaid andmete integreerimise tööriistu.

Sõltuvalt andmeelementide vaheliste selgelt määratletud linkide puudumisest või olemasolust tuleks eristada ÜHENDAMATA struktuure (vektorid, massiivid, stringid, virnad, järjekorrad) ja CONNECTED struktuure (lingitud loendid).

Andmestruktuuri väga oluline tunnus on selle muutlikkus – muutus elementide arvus ja (või) struktuuri elementide omavahelistes suhetes. Struktuuri muutuvuse definitsioon ei kajasta asjaolu, et andmeelementide väärtused muutuvad, kuna sel juhul oleks kõigil andmestruktuuridel muutuvuse omadus. Muutuvuse alusel eristatakse struktuure STAATILINE, POOLSTAATILINE, DÜNAAMILINE. Andmestruktuuride klassifitseerimine varieeruvuse alusel on näidatud joonisel fig. 1.1. Aluseks olevad andmestruktuurid, staatilised, poolstaatilised ja dünaamilised, on põhimälule iseloomulikud ja neid nimetatakse sageli mälusisesteks struktuurideks. Failistruktuurid vastavad välismälu andmestruktuuridele.

Riis. 1.1. Andmestruktuuride klassifikatsioon

Andmestruktuuri oluline tunnus on selle elementide järjestuse iseloom. Selle alusel saab struktuure jagada LINEAARSEKS JA MITTELINEAARSEKS.

Sõltuvalt elementide vastastikuse paigutuse olemusest mälus võib lineaarsed struktuurid jagada struktuurideks, mille elemendid on mälus JÄRJEKORDSELT jaotatud (vektorid, stringid, massiivid, virnad, järjekorrad) ja struktuurideks, mille elementide jaotus mälus on SUVALISELT ÜHENDATUD. (üksiklingitud, topeltlingitud loendid). Mittelineaarsete struktuuride näiteks on mitme lingiga loendid, puud, graafikud.

Programmeerimiskeeltes on mõiste "andmestruktuurid" tihedalt seotud mõistega "andmetüübid". Kõik andmed, s.t. konstante, muutujaid, funktsiooni väärtusi või avaldisi iseloomustavad nende tüübid.

Iga tüübi teave määratleb unikaalselt:

1) kindlaksmääratud tüüpi andmesalvestusstruktuur, s.o. mälu eraldamine ja selles olevate andmete esitus ühelt poolt ning binaarse esituse tõlgendamine teiselt poolt;

2) kehtivate väärtuste kogum, mis ühel või teisel kirjeldatud tüüpi objektil võib olla;

· 3) lubatud toimingute kogum, mis on rakendatav kirjeldatud tüüpi objektile.

ANDMETE STRUKTUUR - füüsiliselt (andmetüübid) ja loogiliselt (algoritm, funktsioonid) omavahel seotud muutujate ja nende väärtuste kogum.

Pange tähele, et andmestruktuuri mõiste ei ole seotud mitte ainult muutujatega, mis seda moodustavad, vaid ka algoritmide (funktsioonidega), mis mitte ainult ei seo muutujaid üksteisega loogiliselt, vaid määravad kindlaks ka sisemised väärtused, mis peaksid samuti olema iseloomulikud. seda andmestruktuuri. Näiteks massiivi paigutatud ja muutuva mõõtmega (andmestruktuur) positiivsete väärtuste jadal võib olla nullterminaator. Kõik selle piiraja moodustamise ja kontrollimise toimingud rakendatakse funktsioonide kaudu. Seega võime öelda, et märkimisväärne osa andmestruktuurist on selle töötlemise algoritmidesse sisse lülitatud.
Tuntud meetodit andmetüüpide kaudu muutujate defineerimiseks iseloomustab see, et esiteks on muutujate arv programmis fikseeritud ja teiseks ei saa programmi töötamise ajal muuta nende dimensiooni. Kui nende muutujate vahelised seosed on enam-vähem konstantsed, siis võib selliseid andmestruktuure nimetada staatilisteks.

STAATILINE ANDMETE STRUKTUUR - kindlast arvust konstantse mõõtmega muutujatest koosnev kogum, mille vahel on samad suhted
Ja vastupidi, kui andmestruktuuri üheks parameetriks on muutujate arv, nende dimensioon või nendevaheline seos programmi töö käigus muutub, siis nimetatakse selliseid andmestruktuurid dünaamilisteks.

DÜNAAMILINE ANDMETE STRUKTUUR - muutujate kogum, mille vahelise seose arv, dimensioon või iseloom muutub programmide töö käigus.

Dünaamilised andmestruktuurid põhinevad kahel programmeerimiskeele elemendil:

· dünaamilised muutujad, mille arv võib muutuda ja mille määrab lõpuks programm ise. Lisaks võimaldab dünaamiliste massiivide loomise võimalus rääkida muutuva mõõtmega andmetest;

viiteid, mis pakuvad andmete otsest seost ja võimalust neid seoseid muuta.

Seega on järgmine definitsioon tõele lähedane: dünaamilised andmestruktuurid on osutitega seotud dünaamilised muutujad ja massiivid.
Andmestruktuuridest rääkides ei tohi unustada, et tavalised muutujad asuvad RAM-is (arvuti sisemälus). Seetõttu on andmestruktuurid tavaliselt seotud mäluga. Samas on olemas ka väline mälu, mis on keeles kaudselt kättesaadav failidega töötavate operaatorite (Pascal) või funktsioonide (C) kaudu. Binaarses suvapöördusfailirežiimis on mis tahes fail piiramatu otseaadresseeritava mäluala analoog, st programmi seisukohalt näeb see välja sama, mis tavamälu. Loomulikult saab programm kopeerida muutujaid mälust suvalisse kohta failis ja tagasi ning seetõttu korraldada failis mis tahes (sh dünaamilisi) andmestruktuure.
Andmestruktuur on täitja, mis korraldab tööd andmetega, sh nende salvestamist, lisamist ja kustutamist, muutmist, otsimist jne. Andmestruktuur toetab neile juurdepääsu teatud järjekorda. Andmestruktuuri võib pidada omamoodi laoks või raamatukoguks. Andmestruktuuri kirjeldamisel peate loetlema selle jaoks võimalike toimingute komplekti ja kirjeldama selgelt iga toimingu tulemust. Me nimetame selliseid toiminguid retseptideks. Programmilisest vaatenurgast on andmestruktuuri ettekirjutussüsteem funktsioonide kogum, mis toimib jagatud muutujatel.
Andmestruktuure on kõige mugavam realiseerida objektorienteeritud keeltes. Nendes vastab andmestruktuur klassile, andmed ise salvestatakse klassiliikme muutujates (või juurdepääs andmetele toimub liikmemuutujate kaudu), ettekirjutussüsteem vastab klassi meetodite komplektile. Reeglina realiseeritakse objektorienteeritud keeltes andmestruktuure standardse klassiteegi kujul: need on standardsesse STL klassiteegi kuuluvad C ++ keele nn konteinerklassid või klassid, mis realiseerivad erinevaid. andmestruktuurid Java keele Java Developer Kit teegist.
Andmestruktuure saab aga sama edukalt rakendada ka traditsioonilistes programmeerimiskeeltes, nagu Fortran või C. Samal ajal tuleks järgida objektorienteeritud programmeerimisstiili: määratleda selgelt andmestruktuuriga töötav funktsioonide kogum ja piirata juurdepääsu andmetele ainult selle funktsioonide komplektiga. Andmed ise on realiseeritud staatiliste (mitte globaalsete) muutujatena. C-keeles programmeerimisel vastab andmestruktuur kahele lähtetekstiga failile:
1. päis ehk h-fail, mis kirjeldab andmestruktuuri liidest, st. andmestruktuuri ettekirjutuste süsteemile vastav funktsioonide prototüüpide komplekt;
2. teostusfail ehk C-fail, milles on määratletud staatilised muutujad, mis salvestavad ja neile juurde pääsevad, ning on realiseeritud andmestruktuuri ettekirjutuste süsteemile vastavad funktsioonid.
Andmestruktuur realiseeritakse tavaliselt varem realiseeritud lihtsama põhistruktuuri alusel või massiivi ja lihtsate muutujate komplekti alusel. Selgelt tuleks eristada andmestruktuuri kirjeldamist loogilisest vaatenurgast ja selle teostuse kirjeldamist. Rakendusi võib olla palju erinevaid, kuid loogilisest vaatenurgast (st väliskasutaja vaatenurgast) on need kõik samaväärsed ja erinevad võib-olla ainult käskude täitmise kiiruse poolest.

Algoritmi koostamise vajalik tingimus on andmete vormistamine, st. teabe vähendamine mõnele teabemudel(cm. " Teabemudelid”), mida on juba kirjeldatud ja uuritud. Kui selline mudel leitakse, öeldakse, et see on määratletud. abstraktne andmestruktuur.

Abstraktne andmestruktuur kirjeldab objekti omadusi ja omadusi, suhe objekti elementide vahel, nii hästi kui võimalik operatsioonid antud objekti või objektide klassi üle.

Informaatika üheks ülesandeks on leida arvutitöötluseks mugavad infoesitusvormid. Arvutiteadus kui täppisteadus töötab formaalsete (matemaatiliselt rangelt kirjeldatud) objektidega. Sellised objektid - põhilised abstraktsed andmestruktuurid arvutiteaduses kasutatakse:

· täisarvud;

reaalarvud;

sümbolid;

tõeväärtused.

Nende objektide arvutitöötluseks programmeerimiskeeltes on olemas vastavad andmetüübid(cm. " Andmetüübid”). Põhiobjekte saab kombineerida keerukamateks struktuurideks, lisades toimingud juba struktuuri kui terviku kohta ja juurdepääsureeglid selle abstraktse andmestruktuuri üksikutele elementidele.

Need abstraktsed andmestruktuurid hõlmavad järgmist:

vektorid (lõplikud massiivid);

tabelid (maatriksid) ja üldiselt - mitmemõõtmelised massiivid;

dünaamilised struktuurid:

Tähemärkide jadad, numbrid;

järjekorrad;

puud;

Tõhusa algoritmi ja seda rakendava programmi loomisel on sageli võtmeks andmestruktuuri hea valik: andmestruktuuride ja reaalsete objektide analoogiat kasutades saab probleemidele tõhusaid lahendusi leida.

Pange tähele, et loetletud struktuurid eksisteerivad sõltumata nende rakendamisest programmeerimises. Nende andmestruktuuridega töötasid nad nii 18. kui 19. sajandil, kui arvutit polnud veel leiutatud. Algoritmi saame kavandada abstraktse andmestruktuuri alusel, kuid algoritmi rakendamiseks konkreetses programmeerimiskeeles peame leidma viisi, kuidas seda esitada andmetüübid Ja operaatorid toetab see programmeerimiskeel (vt " Programmeerimiskeele avaldused”). Abstraktsete struktuuride arvutiesitamiseks andmestruktuurid, mis on teatud viisil kombineeritud muutujate kogum, mis võib olla erinevat tüüpi andmetüüpidest. Selliste struktuuride nagu vektor, tabel, string, jada konstrueerimiseks on enamikus programmeerimiskeeltes standardsed andmetüübid: vastavalt ühemõõtmeline massiiv, kahemõõtmeline massiiv, string, fail (harva loend). Eelkõige muude andmestruktuuride organiseerimine dünaamilised struktuurid, mille suurus programmi täitmise käigus muutub, peab programmeerija selle ise juurutama, kasutades selleks põhiandmetüüpe. Vaatleme selliseid struktuure üksikasjalikumalt.

Loendid

Lineaarne loend- lineaarselt ühendatud elementide jada, mille puhul on lubatud elementide lisamine loendis suvalisele kohale ja mis tahes elemendi kustutamine. Lineaarne loend on üheselt määratletud loendi algusesse viiva kursori abil. Tüüpilised toimingud loenditega on: loendi läbimine, antud elemendi otsimine, elemendi sisestamine vahetult pärast või enne teatud elementi, antud elemendi kustutamine, kahe loendi ühendamine üheks, ühe loendi jagamine kaheks või enamaks loendiks jne.

Lineaarses loendis iga elemendi jaoks, välja arvatud esiteks, Seal on eelmine element; iga elemendi jaoks, välja arvatud viimane, Seal on järgmiseks element. Seega on kõik loendi elemendid järjestatud. Lineaarse üksikult lingitud loendi töötlemine ei ole aga alati mugav, sest puudub võimalus liikuda vastupidises suunas - nimekirja lõpust algusesse. Lineaarses loendis on võimalik kõiki elemente läbida ainult liikudes järjestikku aktiivselt elemendilt järgmisele, alustades esimesest, otsejuurdepääs i-th element on võimatu.

Näide 1. Järjekord, milles lugejate perekonnanimed raamatukoguhoidja arvutis loetletakse, määratleb suhte "eelmine-järgmine". Reeglina on kirjetel endil lisaomadus – need on järjestatud tähestikulises järjekorras. Selle loendi kohal on realiseeritud uue lugeja lisamise ja vajadusel vana kustutamise toimingud. Kui lisaks peetakse arvestust igale lugejale väljastatud raamatute üle, siis on mugav iga selline arvestus uuesti esitada väljaantud raamatute nimekirja abil.

Helinate nimekirjad- sama struktuur kui lineaarsel loendil, kuid viimase ja esimese elemendi vahelise täiendava seosega, see tähendab, et esimene element pärast viimast elementi on esimene element.

Ringikujulises loendis, mitte lineaarses loendis kõik elemendid on võrdsed(sest iga elemendi jaoks on määratletud nii eelmine kui ka järgmine element). "Esimese" ja "viimase" elementide valimine ringikujulises loendis on väga tingimuslik, kuna tegelikult loendi struktuuril pole selgesõnaliselt eraldatud elemente!

Näide 2 Paljudes mängudes kasutavad lapsed loendusriime, et valida liider, jaguneda meeskondadeks jne. Reeglina on loendusriimid pikad ja lapsed koostavad (seda teadmata) ringikujulise nimekirja. "Eelmine-järgmine" suhte määrab see, kuidas juht mõtleb. Sellise struktuuri tüüpiline toiming on elemendi eemaldamine loendist, säilitades samal ajal selle ringstruktuuri.

Lineaarsed loendid, milles elementide sisestamine, kustutamine ja juurdepääs neile väärtustele tehakse ainult äärmuslike elementidega (esimene või viimane), said erinimed.

Virna- lineaarse üksikult lingitud loendi erijuhtum, mille jaoks on määratletud kaks toimingut: elemendi lisamine virna ülaossa (enne esimest elementi) ja elemendi eemaldamine virna ülaosast (esimese elemendi eemaldamine).

Näide 3 Mõelge aritmeetilises avaldises erinevat tüüpi sulgude tasakaalu määramise probleemile. Näiteks soovite analüüsida, kas sulud on tasakaalustatud avaldises, mis sisaldab sulgusid ja nurksulge: ? Selle probleemi lahendamiseks kasutame dünaamilist struktuuri andmeid virna. Esitame selle probleemi lahendamise algoritmi samm-sammult. Kasutame järgmist tähistust:

i- analüüsitava märgi number;

n- märkide arv avaldises.

1. i = 0.

2. i = i + 1.

3. Kui in, siis minge üksuse (4) juurde, vastasel juhul kui virn on tühi, väljastame teate "sulgud on tasakaalustatud", vastasel juhul väljastame teate " sulgud ei ole tasakaalustatud". Algoritmi lõpp.

4. Kui i märk erineb sulgmärkidest, seejärel minge üksuse (2) juurde.

5. Kui i-th märk võrdub "(" või "[", siis paneme selle virna, hüppame üksuse (2) juurde.

6. Kui i-th märk on võrdne ")", siis kontrollime virna ülaosa: kui virna ülaosa on "(", siis ekstraheerime selle virnast; jätkake sammuga (2), vastasel juhul väljastame sõnumi “ sulgud ei ole tasakaalustatud". Algoritmi lõpp.

7. Kui i-th märk on võrdne “]”, siis kontrollime virna ülaosa: kui virna ülaosa on “[”, siis eraldame selle virust; minge punkti (2) juurde, vastasel juhul väljastame sõnumi " sulgud ei ole tasakaalustatud". Algoritmi lõpp.

Järjekord- lineaarse üksikult seotud loendi erijuhtum, mille puhul on lubatud ainult kaks toimingut: elemendi lisamine järjekorra lõppu (saba) ja elemendi eemaldamine järjekorra algusest (pea).

Järjekorra mõiste on tõesti väga lähedane igapäevasele terminile "järjekord". Klientide järjekord poes on selle andmestruktuuriga hästi kirjeldatud.

puud

Puu on elementide kogum nimega sõlmed, milles on valitud üks element ( juur) ja ülejäänud elemendid jagatakse mittelõikuvateks hulkadeks (alampuudeks), millest igaüks on puu, samas kui iga alampuu juur on järeltulija puujuur, s.o. Kõik elemendid on seotud suhtega (esivanem-järglane). Selle tulemusena moodustub sõlmede hierarhiline struktuur. Nimetatakse sõlmed, millel pole lapsi lehed. Puuga on defineeritud järgmised toimingud: puule elemendi lisamine, puust elemendi eemaldamine, puu läbimine, puust elemendi otsimine.

Näide 4 Puu on kõige mugavam andmestruktuur sugupuu kujutamiseks, mille abil saab lahendada kahe inimese vahelise suhte määramise probleemi.

Puid kasutatakse ka mängudes võidustrateegia määramiseks (vt artiklit “ Mängud. Võidustrateegiad”) ja erinevate teabemudelite loomiseks (vt „ Teabemudelid”).

Eriti oluline roll informaatikas on nn kahendpuud.

Binaarne (binaarne) puu- puu erijuhtum, kus igal sõlmel ei saa olla rohkem kui kaks järglast, mis on vasaku ja parema alampuu juured.

Kui lisaks on puu sõlmede puhul täidetud tingimus, et kõik vasakpoolse alampuu elementide väärtused on väiksemad kui puu juure väärtus ja kõik puu elementide väärtused parempoolne alampuu on suuremad kui juure väärtus, siis nimetatakse sellist puud binaarne otsingupuu ja on loodud esemete kiireks leidmiseks. Otsingualgoritm sellises puus töötab järgmiselt: soovitud väärtust võrreldakse puu juure väärtusega ja olenevalt võrdluse tulemusest otsing kas lõpeb või jätkub ainult vasakul või ainult paremal. vastavalt alampuu. Võrdlustoimingute koguarv ei ületa nn puu kõrgus- maksimaalne elementide arv teel puu juurest ühe leheni. Seega on joonisel näidatud puu kõrgus 4.

Loeb

Graafik on elementide kogum, mida nimetatakse tipud graafik koos nende tippude vaheliste suhete komplektiga, nn ribid graafik. Selle andmestruktuuri graafiline tõlgendus on tippudele vastav punktide kogum, mille mõned paarid on ühendatud servadele vastavate joonte või nooltega. Viimasel juhul nimetatakse graafikut orienteeritud(vaata ka artikleid “ Graafilised mudelid"Ja" Tabelikujulised mudelid”).

Tulenevalt asjaolust, et graafikute abil on võimalik kirjeldada suvalise struktuuriga objekte, on graafikud peamiseks tööriistaks keerukate objektide struktuuride ja süsteemide toimimise kirjeldamisel. Näiteks arvutivõrgu, transpordisüsteemi, hierarhilise struktuuri kirjeldamiseks (puu on üks graafiku variante). Algoritmide plokkskeemid (vt " Algoritmide kirjutamise viisid”) on samuti graafikud.

Kui igale servale on määratud ka kindel number ( kaal), siis nimetatakse sellist graafikut kaalutud. Näiteks Venemaa teedesüsteemi kirjeldamisel graafi abil on oluline teatud asulaid (graafiku tippe) ühendava tee pikkus (graafiku serva kaal). Samas ei pea joonisel vastavate servade pikkused vastupidiselt teekaardile vastama neile määratud kaaludele.

Näide 5 Kaalutud graafiku abil on mugav lahendada järgmine ülesanne. Venemaa valitsus koostab plaani ehitada üle miljoni elanikuga linnu ühendavad moodsad kiirteed. Milliseid teid peaks ehitama, et igast sellisest linnast saaks mööda uusi kiirteid kuhugi mujale ja teede kogupikkus oleks minimaalne?

Sellel graafiteooria probleemil on lihtne ja täpne lahendus. Teedevõrgu planeerimist saame alustada igast linnast, näiteks Peterburist. Ühendame selle lähima miljonilinnaga. Lisaks lisatakse igas etapis olemasolevasse võrku lühim tee, mis suudab ühendada veel võrku ühendamata linna mõne juba võrku lisatud linnaga. Teede arv on seega linnade arvust ühe võrra väiksem.

Abstraktset andmestruktuuri – graafikut – saab programmis kujutada mitmel viisil, s.t. kasutades erinevaid andmetüüpe. Näiteks saab graafi kirjeldada servade loendi abil, täpsustades iga serva tipupaariga ja vajadusel ka kaaluga. Kõige levinum on graafiku tabelina salvestamine (vt “ Tabelikujulised mudelid"), nimetatud ka naabrusmaatriks, st. kahemõõtmeline massiiv, ütleme A, kus kaalumata graafi puhul (või 1), kui tippude vaheline serv i Ja j on olemas ja (või 0) muul viisil. Kaalutud graafiku jaoks A[i][j] on võrdne vastava serva kaaluga ja serva puudumist mitmes ülesandes tähistatakse mugavalt lõpmatusega. Suunamata graafikute puhul on naabrusmaatriks alati sümmeetriline põhidiagonaali suhtes ( i = j). Külgnevusmaatriksi abil on lihtne kontrollida, kas tippu ühendavas graafis on serv iüleval j. Selle peamine puudus on see, et naabrusmaatriks nõuab, et mälumaht oleks salvestamiseks piisav N 2 väärtust sisaldava graafiku jaoks N tipud, isegi kui graafikul on oluliselt vähem servi kui N 2 .

Mõiste selgitamisel andmestruktuurid võite kasutada järgmist illustratsiooni.

Mis tahes probleemi lahendamisel on vaja töötada andmeid ja nendega operatsioone teha. Nende toimingute komplekt iga ülesande jaoks on üldiselt erinev. Kui aga erinevate probleemide lahendamisel kasutatakse sageli teatud toimingute komplekti, siis on kasulik välja mõelda viis andmete korrastamiseks, mis võimaldab neid konkreetseid toiminguid võimalikult tõhusalt sooritada. Pärast sellise meetodi leiutamist võime konkreetse probleemi lahendamisel eeldada, et meil on "must kast" (nimetame seda andmestruktuuriks), mille kohta on teada, et sellesse salvestatakse mingisuguseid andmeid, ja mis suudab nende andmetega mingeid toiminguid teha. See võimaldab teil üksikasjadest abstraktsiooni võtta ja keskenduda probleemi olulisematele tunnustele. Sees (s.o arvutis) saab seda “musta kasti” mitmel viisil realiseerida ning peaks püüdlema võimalikult efektiivse (kiire ja mälusäästliku) teostuse poole.

Riiklik haridusstandard näeb ette erinevate andmestruktuuride uurimist nii põhikooli põhikursuses kui ka gümnaasiumis. Põhikooli programmeerimise kursusel Näidisprogrammis on töödeldud objektidena mainitud märgiahelaid (stringe), numbreid, loendeid, puid, graafikuid. Praktilises töös mainitakse aga keerulise struktuuriga andmetest vaid massiivi (vt artiklit “ Massiivi operatsioonid”). Põhikoolis tundub, et graafiliste ja muude mudelite ehitamisel on mõtet uurida eelkõige muid struktuure (vt entsüklopeedia IV jaotis).

Erikooli eeskujulik programm hõlmab arvude, maatriksite, stringide, loendite ja puudega töötamist. Lihtsa näitena loenditega töötamise kohta saate valida virna korraldamise ühemõõtmelise massiivi ja täisarvulise muutuja abil, mis osutab virna ülaosale (virna "alumine" on alati massiivi esimeses elemendis ). Lisaks artiklis toodud sulgude tasakaalu kontrollimise ülesandele saate uurida virnakalkulaatori tööd, kasutades algoritmi aritmeetilise avaldise tõlkimiseks poola pöördmärgistusse ( postfix rekord) tavapärasest infix kirjed ja aritmeetilise avaldise väärtuse edasine arvutamine.

Samuti on lihtne esitada binaarpuud arvutimälus ühemõõtmelise massiivi abil, samas kui massiivi esimene element salvestab puu juure ja puusõlme järeltulijad. i-massiivi element asub 2 i-m ja (2 i+ 1)-ndad elemendid vastavalt. Kui sõlmel pole alamosa, võrdub vastav element näiteks 0-ga. Rekursiivne puu läbimise protseduur t ja selle elementide printimine sel juhul näeb välja järgmine:

protseduuri järjekord(i:täisarv);

kui t[i]<> 0 siis

Loendite ja massiivide rakendamisest dünaamiliste muutujate abil saab lugeda näiteks N. Wirthi klassikalisest raamatust "Algoritmid ja andmestruktuurid".

Erikooli programmis on ka graafikute algoritmid. Eelkõige mainitakse lühima tee otsimist graafikus. Kaalumata graafi puhul saab seda ülesannet lahendada näiteks laius-esimese otsingu algoritmi abil, kui esmalt märgistatakse graafi tipud, mis on servaga ühendatud algse tipuga, seejärel kõik märgistatutega ühendatud tipud jne. Kaalutud graafiku jaoks kasutatakse kõige sagedamini Dijkstra algoritmi (vt nt E.V. Andreeva artiklit “Informaatikaolümpiaadid. Teed tippu”, “Arvutiteadus” nr 8/2002). Selliste algoritmide tundmine on vajalik arvutiteaduse olümpiaadiülesannete edukaks lahendamiseks. Nii pakuti 2007. aasta ülevenemaalise informaatikaolümpiaadi IV föderaalringkonna etapil välja ülesanne "Kaevikud ja kaevikud", mille lahenduseks oli lihtsalt lühima tee leidmine kaalutud graafikus.

Algselt nägi programmeerimisprotsess ette, et programmeerija kirjutas kõik algoritmid otse masinkeeles. Selline lähenemine raskendas niigi rasket ülesannet algoritmide väljatöötamisel ja tõi liiga sageli kaasa vigu, mis tuli leida ja parandada [see on silumiseks tuntud protsess], enne kui töö lõpetatuks lugeda.

Esimene samm programmeerimise hõlbustamise suunas oli keeldumine numbrite kasutamisest käskude ja operandide kirjutamiseks otse sellisel kujul, nagu neid masinas kasutatakse. Selleks hakati programme arendades laialdaselt kasutama erinevate käskude mnemomärki nende kuueteistkümnendsüsteemi esituse asemel. Näiteks võiks programmeerija nüüd registri laadimiskäsu digitaalse koodi asemel kirjutada LOD ja registri sisu mällu kopeerimise käsukoodi asemel kasutada mnemoloogilist STO-d. Operandide kirjutamiseks töötati välja reeglid, mille järgi võis programmeerija määrata teatud mälupiirkondadele kirjeldavaid nimetusi [sageli nimetatakse identifikaatoriteks] ja kasutada neid programmikäskude kirjutamisel vastavate mälurakkude aadresside asemel. Selliseid identifikaatoreid nimetatakse tavaliselt muutujateks. See rõhutab, et antud mälukohale eraldatud väärtuse muutmisega muudame programmi täitmise ajal sellele asukohale määratud identifikaatoriga seotud väärtust.

Kui muutuja on programmis deklareeritud, määratakse nende tüüp tavaliselt samal ajal. Andmetüüp määrab nii konkreetsete andmete tõlgendamise kui ka nendega tehtavad toimingud. Andmetüüpide hulka kuuluvad täisarv [täisarv], reaalne [tõeline], märk [märk] ja tõeväärtus [tõvearv].

Tüüpi Integer kasutatakse arvandmete tähistamiseks, mis on täisarvud. Mälus on need kõige sagedamini esindatud kahe täiendusena. Täisarvudega saate teha tavalisi aritmeetilisi ja võrdlustehinguid.

Tüüp Real on loodud esitama arvandmeid, mis võivad sisaldada mittetäisarvulisi väärtusi. Mällu salvestatakse need tavaliselt binaarsete ujukomaarvudena. Toimingud, mida saab teha pärisandmetega, on sarnased täisarvuandmetega tehtavatele toimingutele. Kuid manipulatsioonid, mida tuleb teha kahe Real-tüüpi andmeelemendi lisamiseks, erinevad manipulatsioonidest, mis on vajalikud Integer tüüpi muutujatega toimingute tegemiseks.

Märgitüüpi kasutatakse andmete jaoks, mis koosnevad ASCII- või UNICODE-koodidena mällu salvestatud märkidest. Seda tüüpi andmeid saab omavahel võrrelda [määrake, milline kahest tähemärgist on tähestiku järjekorras teineteisele eelnev]; kontrollige, kas üks tähemärkide jada on teine, ja ühendage kaks stringi üheks pikemaks stringiks, lisades ühe neist teise järel [konkateneerimisoperatsioon].

Boolean viitab andmetele, millel on ainult kaks väärtust Tõene [tõene] ja Väär [vale]. Selliste andmete näide on kahe numbri võrdlusoperatsiooni tulemus. Boole'i ​​andmetega tehtavad toimingud hõlmavad kontrollimist, kas muutuja praegune väärtus on tõene või väär.

Masina põhimälu on korraldatud eraldi lahtrite kujul, mille aadressid kasvavad järjestikku. Neid lahtreid kasutatakse aga sageli muude andmete paigutamise viiside rakendamise alusena. Näiteks teksti vaadeldakse tavaliselt pikkade tähemärkide jadana, müügiteavet aga ristkülikukujulise tabelina, millel on arvväärtused, millest igaüks tähistab konkreetse töötaja konkreetsel päeval suletud tehingute arvu. Väljakutse seisneb selles, et pakkuda kasutajale vahendeid selliste abstraktsete struktuuridega töötamiseks, selle asemel et süveneda masina põhimälus olevate andmete tõelise korralduse üksikasjadesse. Arvuti õigeks kasutamiseks on vaja hästi tunda andmete struktuurseid seoseid, põhilisi arvutisiseste struktuuride kujutamise meetodeid, aga ka nendega töötamise meetodeid. Arvuti andmetevaheliste linkide jaoks kasutatakse järgmisi teabestruktuure: massiiv, kirje, loend, puu, virn, järjekord.

Massiivid

Massiiv on struktuur, mis sisaldab mitut sama tüüpi elementi. Indekseid kasutatakse massiivi elementide sortimiseks. Indeksid kirjutatakse massiivi nime järele sulgudes. Ühe indeksiga massiivi nimetatakse ühemõõtmeliseks, kahe - kahemõõtmeliseks jne.

Salvestamine

Kirje on struktuur, mis koosneb elementidest, mis ei pruugi olla sama tüüpi. Kirje üksikuid elemente nimetatakse väljadeks. Põld omakorda võib olla ka rekord.

rekord Õpilane (
eesnimi,
perekonnanimi,
Grupp
)

Loendid

Loend on kirjete kogum, millest igaüks sisaldab spetsiaalset välja – indeksit. Kursor seob kirje mõne muu kirjega või sisaldab nullväärtust, mis näitab, et kursori väärtus on määramata.

Üksiklingitud loendi kirjetel on igaühel üks osuti ja need on lingitud ahelas:

Joonisel olev nool tähistab kursori sisu ja sõna Data tähistab väljade kogu, kuhu andmeid salvestatakse. Loendit saab korraldada kahemõõtmelise massiivina, mille kõik elemendid, mille esimene indeks on 0, on mõeldud andmete salvestamiseks ja elemendid, mille esimene indeks on võrdne 1-ga, on osutid.

Selles loendis on ingliskeelse tähestiku tähti sisaldavad kirjed järjestatud tähestikulises järjekorras. Loendi esimene kirje sisaldab märki "A", teine ​​- "B" ja nii edasi.

Loendiga töötamiseks peate suutma teha kolm põhitoimingut:

Pass() - loendist möödasõit või liikumine;
Add() - uue kirje lisamine nimekirja;
Kustuta() – kirje kustutamine loendist.

Lisaks toimingutele on loendiga töötamiseks vaja veel kahte muutujat:

muutuja Head, mis salvestab teabe loendi esimese kirje kohta
muutuja Current, mis osutab loendi praegusele kirjele

Tabelis on kokku võetud mõnede loendis olevate toimingute kirjeldused, mille rakendamise näide on toodud ülal.

Operatsiooni nimi	Pseudokood
Liigutage loendis üks samm allapoole	funktsioon Läbi (praegune) ( kui (M Null), siis Praegune:=M; tagasi (Praegune); }
	funktsioon Lisa (praegune, uus) ( M:=M; M:=Uus; tagastamine; }
Lisage loendisse kirje, millele viitab muutuja Uus	funktsioon Kustuta (praegune) ( kui (M Null) siis M = M]; tagastamine; }

Topeltlingitud loendis olevad kirjed on aheldatud, kuid neil on kaks osutivälja. Üks neist osutab loendis eelmisele elemendile, teine ​​- järgmisele elemendile. See struktuur võimaldab teil loendis liikuda kahes suunas: edasi ja tagasi.

Rõngas on loend, mille viimane sisestus osutab esimesele. Nendes loendites pole ühtegi nullkirjet.

Puu on hargnenud loend, mille iga kirje võib sisaldada mitut osutit. Puu kirjeid nimetatakse sõlmedeks. Sõlme, millel on kõik nullviidid, nimetatakse lehtedeks. Puu ülemist algussõlme nimetatakse juursõlmeks. Paljude probleemide puhul piisab binaarsete [binaarsete] puude kasutamisest, mille sõlmedel ei ole rohkem kui kaks osutit.

Näide. See on vajalik matemaatilise avaldise (3+7)*(2/(3-1)) arvutamiseks. Esitame selle avaldise puuna:

Selle puu iga sõlm on järgmise vormi kirje:

Record Node(
operatsiooni
number
vasak kursor
parem osuti
)

Puu lehed sisaldavad numbreid, ülejäänud sõlmed on tehte sümbolid.

Rakendades kirjeldatud puu kahemõõtmelisele massiivile, saame järgmise pildi:

Puu väärtuse arvutamiseks peate arvutama parema ja vasaku alampuu väärtused ning seejärel tegema neile vastava toimingu. Probleemi lahendava algoritmi pseudokood näeb välja järgmine:

funktsioon Arvuta(praegune)(
kui (M = null), siis
Tulemus:=M;
muu (
R1: = Arvuta (M);
R2: = Arvuta (M);
Tulemus: =R1(M)R2;
}
tagastama(tulemus);
}

Virn on andmestruktuur, mis on korraldatud põhimõttel "viimane sisse, esimene välja". Virna salvestatud andmetele pääseb juurde ülaosa kaudu. Andmed lükatakse virnasse järjestikku Esimesena virna lükatud element asub allosas ja selle virnast väljatõmbamiseks tuleb kõigepealt poputada kõik andmed, mis virnasse lükati hiljem.

Virnaga töötamisel on võimalikud kaks hädaolukorda: katse lugeda andmeid tühjast virust; katse lükata element virna, kui elementide arv virnas on saavutanud maksimaalse lubatud arvu.

Järjekord on andmestruktuur, mis on korraldatud põhimõttel esimene sisse, esimene välja. Järjekorras on muutuv hulk andmeid. Järjekorras lisatakse andmed sabasse, kättesaamisel võetakse peast.

Räsi tabel

Räsimine on tehnika, mis võimaldab dokumentidele otsest juurdepääsu ilma täiendavaid struktuure kasutamata. Protsessi saab lühidalt kirjeldada järgmiselt. Andmete salvestamise ruum on jagatud mitmeks segmendiks. Kirjed eraldatakse nendele kildudele vastavalt mõnele algoritmile, mida nimetatakse räsimisalgoritmiks ja mis teisendab võtmevälja väärtuse killuarvuks. Iga kirje salvestatakse selle protsessiga määratletud segmenti. Seetõttu saab kirje kätte saada, rakendades selle võtmevälja väärtusele räsimise algoritmi ja lugedes vastava segmendi kirjeid. Sel viisil koostatud andmestruktuuri nimetatakse räsitabeliks.

Näiteks kui teil on vaja korraldada räsitabel ingliskeelse tähestiku suurtähtede salvestamiseks, saate klahvidena valida ASCII märgikoodid ning räsimise algoritm lõikab ära alumise viis bitti ja moodustab massiivielementide indeksi tegelane nende põhjal:

Üldjuhul peaks räsimisalgoritm võtme väärtust arvestades tootma indeksi väärtuse massiivi piirides ja jaotama võtmed ühtlaselt massiivi elementide vahel. Viimase nõude täitmata jätmine põhjustab olukordi, kus mitu kirjet langeb samasse segmenti. Neid olukordi nimetatakse kokkupõrgeteks.