Mihin datan strukturointia käytetään? Tietokantavaatimukset. Erityyppiset tietorakenteet

Tietorakenteiden luokitukset

Tietokoneen muistissa oleva data esitetään bittijonona. Bittisekvenssit eivät ole tarpeeksi rakenteellisia, mikä tekee niistä vaikean käytännön käyttöä. Siksi tietorakenteita käytetään käytännössä.

Määritelmä 1

Rakenne data on joukko tietoelementtejä ja sisäiset liitännät heidän välillään.

Olla olemassa yksinkertainen Ja integroitu Tietorakenteet. Yksinkertaiset tietorakenteet pelkistetään biteiksi ja järjestetään suoraan biteistä. Yksinkertaisia rakenteita ovat mm.

numeerinen;
bitti;
symbolinen;
aivojumppa;
osoittimia.

Integroidut tietorakenteet on järjestetty yksinkertaisista ja muista integroiduista rakenteista.

On tarpeen erottaa fyysistä Ja looginen tietorakenne. Kun puhumme yksinkertaisten tyyppien fyysisestä rakenteesta, tämä viittaa niiden kokoon ja tapaan, jolla bitit on järjestetty muistissa. Loogisen rakenteen näkökulmasta yksinkertainen tyyppi on jakamaton alkeisyksikkö.

Määritelmä 2

Vaihtuvuus rakennetta kutsutaan muutokseksi elementtien lukumäärässä ja niiden välisissä yhteyksissä.

Vaihtuvuusmerkin mukaan rakenteet jaetaan

Staattinen (vecotr, array, set, record, table);
Dynaaminen (pino, jono, merkkijono, lineaarinen aiheeseen liittyvät luettelot, haaroittuneet linkitetyt luettelot, kaaviot, puut.).

Rakenteen elementit voivat olla tilattuja tai tilaamattomia. Tämän ominaisuuden mukaisesti rakenteet on jaettu

Epälineaarinen (monilinkitetty lista, kaavio, puu);
Lineaarinen sekvenssijakaumalla (vektori, merkkijono, taulukko, pino, jono);
Lineaarinen mielivaltaisen yhdistetyn jakelun kanssa (yksinkertaisesti yhdistetyt ja kaksoisliitetyt luettelot).

Yksinkertaiset rakenteet ja tietotyypit

Yksinkertaisia tietorakenteita kutsutaan myös primitiiveiksi tai perusrakenteet. Ohjelmointikielissä yksinkertaisia tietorakenteita edustaa yksinkertaisia tyyppejä tiedot. SISÄÄN eri kielillä Ohjelmoinnissa tietotyyppien joukko on hieman erilainen, mutta on olemassa joitain yleisiä periaatteita.

Kokonaislukutyyppi käytetään edustamaan erillisten objektien määrää. Kokonaisluvut voivat olla etumerkittömiä tai negatiivisia. Kokonaisluvun sisäinen esitys voi olla 1, 2 tai 4 tavua.

Reaaliluvut esitetään muodossa liukulukumuoto. Liukuluku esitetään kahdella kokonaislukuja– tilaus ja matisse sekä kyltti.

Kun binäärijärjestelmä merkintä B=2.

Desimaalityyppi Kaikkia ohjelmointikieliä ei tueta. Joitakin tämän tyyppisiä lukuja edustaa m desimaalilukuja joista d numeroa ovat desimaalipilkun oikealla puolella.

Tapauksissa, joissa sinun on työskenneltävä numeron yksittäisten binäärinumeroiden kanssa, se tarjotaan bittitietotyyppi. Siinä olevaa dataa edustaa joukko bittejä, jotka on yhdistetty tavuiksi tai sanoiksi. Kaikki bittityypin toiminnot sisältävät pääsyn jokaiseen bittiin erikseen.

Muuttuva boolen tyyppi voi olla jompikumpi kahdesta arvosta: tosi tai epätosi. Boolen muuttujan tallentamiseen tarvitaan yksi tavu muistia. Tässä tapauksessa arvo "false" on koodattu nolla arvo tavu, ja arvo "true" on mikä tahansa muu arvo kuin nolla.

Hahmon tyyppi mahdollistaa tietojen esittämisen jonkin ennalta määrätyn joukon symbolien sarjana. Jokainen joukon symboli tallennetaan muistiin bittijonona. Merkkien ja tällaisten sekvenssien välistä vastaavuutta kutsutaan koodaukseksi. Erilaisia koodauksia edustavat merkkejä eripituisina bittisarjoina.

Osoitin on muuttuja, jonka arvo on muistisolun osoite. Siten osoitin viittaa tiettyyn tietolohkoon osoittamalla sen ensimmäisen solun.

Esimerkkejä staattisista rakenteista

Jos haluat viitata elementtiin, sinun on käytettävä taulukon nimeä ja elementin indeksiä. Muistissa taulukot sijaitsevat soluissa, jotka sijaitsevat peräkkäin.

Esimerkki 1

Annetaan taulukko nimeltä A.

Silloin elementti A on yhtä suuri kuin 30.

Esimerkki 2

Kaksiulotteinen matriisi on taulukko, jonka jokainen elementti on itsessään yksiulotteinen taulukko.

Kaksiulotteisessa taulukossa jokaisella elementillä on kaksi indeksiä.

Määritelmä 4

Tietueet (hash-taulukot, assosiatiiviset taulukot) ovat taulukoita, joita ei indeksoida luonnollisilla luvuilla, vaan merkkijonoilla.

Tällaisen taulukon elementin indeksiä kutsutaan avaimeksi. Elementtiin viitattaessa käytetään taulukon nimeä ja indeksiä.

Esimerkki 3

Olkoon annettu hash-taulukko nimeltä B.

Tällöin taulukon elementti B['vegetable'] on yhtä suuri kuin 'kurkku'.

Esimerkkejä dynaamisista rakenteista

Dynaamisille rakenteille muisti varataan lennossa ohjelman suorittamisen aikana. Työskennellä jonkun kanssa dynaamiset tyypit tiedot sisään eri kieliä Osoittimia käytetään laajasti ohjelmoinnissa. Itse osoittimet ovat staattisia.

Pino on vektori, jossa jokainen seuraava elementti osoitetaan osoittimella nykyiseen elementtiin. Kuvissa näkyy elementtien peräkkäinen lisääminen pinoon ja peräkkäinen poisto.

Jotta voit purkaa elementin, sinun on ensin purettava peräkkäin kaikki sen jälkeen lisätyt elementit. Ensimmäisenä lisätty elementti voidaan poistaa vain viimeisenä.

Jonottaa myös dynaaminen rakenne, joka eroaa pinosta kahden osoittimen läsnäololla: jonon ensimmäiseen ja viimeiseen elementtiin. Uudet elementit kirjoitetaan viimeisen kirjoitetun elementin jälkeen. Ja elementtien valinta alkaa ensimmäisestä. Tällä algoritmilla ensimmäisenä lisätty elementti saadaan ensin.

Millaisia tietorakenteita on olemassa (Voit ilmoittaa rakenteen nimen tietyllä ohjelmointikielellä) Haluaisin tietää niiden tarkoituksen, vahvuudet ja heikkoja puolia. Olen myös kiinnostunut luokittelusta, onko se kirjoitettu oikein wikissä? Luettelo tietorakenteista Jokaiselle rakenteelle ei vielä tarvita yksityiskohtaista vastausta, kerro vain lyhyesti esim. mikä tämän rakenteen etu on muihin verrattuna (esim. nopea aika pääsy elementtiin, mahdollisuus muuttaa dynaamisesti muistin määrää jne.) Ehkä ei kannata vastata kaikkeen kerralla, yhtäkkiä vastauksen määrä on merkittävä, voit peruuttaa ainakin yhden rakenteen tilauksen tiedän hyvin, ja lisään tiedot pääviestiin. On erittäin kätevää saada tällainen luettelo silmiesi edessä, voit tarkistaa sen heti ja valita tarvitsemasi.

1. Lineaariset tietorakenteet ovat tietorakenteita, joissa siirtyminen tietoelementistä toiseen ei riipu mistään loogisia ehtoja, eli lineaarisissa rakenteissa käytetään vain elementtien ehdottomia yhteyksiä.

1.1 Lista Voi olla sama kuin taulukko, mutta sen avulla voit lisätä elementtejä mihin tahansa paikkaan, poistaa elementtejä mistä tahansa ja saada nykyisen määrän elementtejä.

1.2 Assosiatiivinen matriisi

1.3 Hash-taulukko on säännöllinen taulukko, jossa on epätavallinen osoitus hash-funktiolla. Paras valinta, jos sinun ei tarvitse lajitella tietoja, vaan vain nopea pääsy Hänelle. Lisämuistia menee hukkaan.

edut:

Tärkeä tiivistetaulukoiden ominaisuus on, että joidenkin järkevien oletusten mukaan kaikki kolme toimintoa (haku, lisäys, elementtien poistaminen) suoritetaan keskimäärin O(1)-ajassa, pahimman tapauksen aikana O(n).

puutteet:

Toisto ei ole avainten nousevassa järjestyksessä
Tarve "uudelleenhajoamiseen", kun tallennettujen kohteiden määrä kasvaa (?)
on mahdotonta toteuttaa nopeasti juoksevia lisätoimintoja MIN, MAX ja algoritmia kaikkien tallennettujen parien läpikulkua varten nousevassa tai laskevassa näppäinjärjestyksessä (?)
ei ylläpidä järjestystä eikä säilytä elementtien järjestystä (?)
törmäysten mahdollisuus

rakenteiden yleiskuvaus:

Päätarkoitus, kuvaus

Tuetut toiminnot

Edut

Vikoja

Valmis toteutus ohjelmointikielellä (funktion tai luokan nimi)

symboleja

(?) - epävarma, korjaa, jos se on kirjoitettu väärin, tai päinvastoin vahvista se epäselvyyden poistamiseksi.

editointi jatkuu...

Mikä on tietorakenne?

Olen aina uskonut, että" tietorakenne"on termi, joka on luotu erityisesti hämmentämään meitä. Lopulta sain selville, mikä tietorakenne oli yksinkertaisesti järjestämällä sanat uudelleen termissä " tietorakenne" - Kanssa " tietorakenne" päällä " datan rakenne". Tällaisessa kontekstissa painopiste siirtyy datasta (asioista) rakenteeseen (organisaatio). Toisin sanoen emme keskity asioihin, vaan asioiden organisointiprosessiin.

Oletetaan, että asiat, joista puhumme, ovat kirjoja. Kumpi ilmaisu on järkevämpi: kirjat, joissa on rakenne vai kirjojen järjestys? Luulen, että se on jälkimmäinen. Painopiste on organisoinnissa kirjojen sijaan.

Erityyppiset tietorakenteet

Kirjat, kuten tiedot, voidaan järjestää eri tavoin. Kuvitellaan, että meillä on 20 kirjaa. Miten rakennamme ne?

Jos haluamme löytää kirjan nopeasti, tarvitsemme jonkinlaisen hakemiston. Voit esimerkiksi järjestää kirjoja hyllylle Aakkosjärjestys. Tämän ansiosta löydämme nopeasti tarvitsemamme volyymin.

Jos haluamme lukea kaikki kirjat tietyssä järjestyksessä, esimerkiksi lukea ensin kokoelmassamme ensimmäisenä esiintynyt kirja ja niin edelleen viimeiseen kirjaan asti, niin meidän on järjestettävä kirjat tämän mukaan. Lisäksi asennamme tietty rajoitus, jotta voimme lukea kirjoja uudelleen vain tässä järjestyksessä.

Jos meillä ei ole tarpeeksi tilaa säilyttää kaikkia kirjoja samassa huoneessa, voimme sijoittaa ne kaikkialle taloon. Luo sen jälkeen luettelo kahdella sarakkeella: ensimmäinen sarake sisältää kirjan nimen ja toinen sen sijainti.

Nyt on selvää, että kirjoja on monia tapoja lajitella. Mutta on myös monia erilaisia tietorakenteita. Verkkokehityksessä käyttämämme tietorakenne riippuu erityisolosuhteista.

Meidän on ymmärrettävä, että näitä tietorakenteita on mahdollista käyttää ja luoda ilman erityisiä ohjelmointitaitoja. Tarvitsemme vain ymmärryksen JavaScriptistä, sen yksinkertaisimmista tietotyypeistä ( Esimerkiksi, loogisia lausekkeita ) ja viitetyypit ( esimerkiksi esineitä).

Aluksi on vaikea kuvitella, mutta älä huoli. Ajattelin joukkoa, joka on myös eräänlainen tietorakenne, pelkkänä kokoelmana. Mutta joukko ei ole asia, vaan annettu nimi tietty menetelmä tietojen järjestäminen. Yhtä tärkeää on, että sarja luodaan esineiden avulla.

Meidän maalimme

Tämä artikkelisarja käsittelee tietojen jäsentämistä JavaScriptin avulla pitäisi näyttää, että tietorakenteita käytetään helpottamaan elämäämme.

Koska tässä artikkelisarjassa on liian monia tietorakenteita, joita ei voida kattaa kokonaan, käsittelemme niistä vain muutaman, mutta yleisimmät ovat:

Pino ja jono;
Yksittäin ja kahdesti linkitetyt luettelot;
Puu.

Johtopäätös

Kun lopetamme tämän artikkelisarjan, toivon, että et vain osaa ottaa käyttöön yleisiä tietorakenteita, vaan myös ymmärrät, että niitä käytetään ympärilläsi. Sitten alat ajatella eri tavalla datasta ja sen organisaatiosta.

Artikkelin käännös " Tietorakenteet JavaScriptillä: Mikä on tietorakenne?"Ystävällinen projektitiimi valmisteli.

Hyvä huono

Puu on yksi verkkokehityksen yleisimmin käytetyistä tietorakenteista. Jokainen verkkokehittäjä, joka kirjoitti HTML-koodin ja latasi sen selaimeen, loi...

Tietorakenne on ohjelmistoyksikkö, jonka avulla voit tallentaa ja käsitellä paljon samantyyppistä tai loogisesti liittyvää tietoa tietokoneisiin. Jos haluat lisätä, etsiä, muuttaa tai poistaa tietoja, kehys tarjoaa erityisen paketin vaihtoehtoja, jotka muodostavat sen käyttöliittymän.

Mitä tietorakenteen käsite sisältää?

Tällä termillä voi olla useita samanlaisia, mutta silti erottuvia merkityksiä. Tämä:

abstrakti tyyppi;
abstraktin tyyppisen tiedon toteuttaminen;
tietotyypin esiintymä, kuten tietty luettelo.

Jos puhumme tietorakenteesta kontekstissa toiminnallinen ohjelmointi, tämä on erikoisyksikkö, joka tallennetaan muutosten aikana. Sitä voidaan epävirallisesti kuvata yhdeksi rakenteeksi, vaikka siitä voi olla erilaisia versioita.

Mikä muodostaa rakenteen?

Se muodostetaan käyttämällä viitteitä ja operaatioita niille tietyllä ohjelmointikielellä. Se kannattaa sanoa eri tyyppejä toteuttamiseen sopivia rakenteita erilaisia sovelluksia Jotkut ovat esimerkiksi täysin kapea-alaisia ja ne soveltuvat vain vakiintuneiden tehtävien tuottamiseen.

Jos otamme B-puita, niin ne sopivat yleensä tietokantojen muodostamiseen ja vain niitä varten. Samanaikaisesti hash-taulukoita käytetään edelleen käytännössä kaikkialla erilaisten sanakirjojen luomiseen, esimerkiksi verkkotunnusten esittelyyn PC:n Internet-osoitteissa, ei vain tietokantojen muodostamiseen.

Tämän tai tuon kehityksen aikana ohjelmisto toteutuksen monimutkaisuus ja ohjelman toiminnan laatu riippuvat suoraan oikea sovellus Tietorakenteet. Tämä ymmärrys asioista antoi sysäyksen muodollisten kehitysmenetelmien ja ohjelmointikielten kehitykselle, joissa rakenteet sijoitetaan algoritmien sijaan johtoasemaan ohjelmaarkkitehtuurissa.

On syytä huomata, että monilla ohjelmointikielillä on asennettu tyyppi modulaarisuus, joka mahdollistaa tietorakenteiden turvallisen käytön erilaisissa sovelluksissa. Merkittäviä esimerkkejä ovat Java kielet, C# ja C++. Nyt käytettyjen tietojen klassinen rakenne esitetään ohjelmointikielten vakiokirjastoissa tai se on suoraan sisäänrakennettu itse kieleen. Esimerkiksi hash-taulukot on rakennettu Luaan, Pythoniin, Perliin, Rubyyn, Tcl:iin ja muihin. Laajalti sovellettu tavallinen kirjasto malleja C++:ssa.

Rakenteen vertailu toiminnallisessa ja pakottavassa ohjelmoinnissa

On syytä mainita heti, että rakenteiden suunnittelu toiminnallisia kieliä vaikeampaa kuin pakolliset, ainakin kahdesta syystä:

Itse asiassa kaikki rakenteet käyttävät usein käytännössä toimeksiantoa, jota ei käytetä puhtaasti toiminnalliseen tyyliin.
Toiminnalliset rakenteet- Nämä ovat joustavia järjestelmiä. Pakollisessa ohjelmoinnissa vanhat versiot vain korvataan uusilla, mutta toiminnallisessa ohjelmoinnissa kaikki toimii kuten ennenkin. Toisin sanoen imperatiivisessa ohjelmoinnissa rakenteet ovat ohimeneviä, mutta toiminnallisessa ohjelmoinnissa pysyviä.

Mitä rakenne sisältää?

Usein tiedot, joiden kanssa ohjelmat toimivat, tallennetaan käytetyn ohjelmointikielen taulukoihin, vakioihin tai sisäänrakennetuihin taulukoihin. vaihteleva pituus. Taulukko on yksinkertaisin rakenne Tiedon kanssa kuitenkin joidenkin ongelmien ratkaiseminen edellyttää joidenkin toimintojen tehokkuutta, joten käytetään muita (monimutkaisempia) rakenteita.

Yksinkertaisin ryhmä sopii usein käytettäväksi asennetut komponentit indekseillä ja niiden muutoksilla, ja elementtien poistaminen keskeltä toimii O(N)O(N)-periaatteella. Jos sinun on poistettava elementtejä tiettyjen ongelmien ratkaisemiseksi, sinun on käytettävä erilaista rakennetta. Esimerkiksi binääripuu (std::set) sallii tämän tekemisen muodossa O(logN)O(log⁡N), mutta se ei tue työskentelyä indeksien kanssa, se suorittaa vain yksitellen elementtien ja etsiä niitä arvon perusteella. Siten voidaan sanoa, että rakenne eroaa toiminnoista, joita se pystyy suorittamaan, sekä nopeuden, jolla ne suoritetaan. Esimerkkinä kannattaa harkita yksinkertaisimpia rakenteita, jotka eivät tuota tehokkuusetuja, mutta ovat ehdottomasti setti setti tuetut toiminnot.

Pino

Tämä on yksi tietorakenteiden tyypeistä, joka esitetään rajoitetun yksinkertaisen taulukon muodossa. Klassinen pino tukee vain kolmea vaihtoehtoa:

Työnnä elementti pinoon (vaikeusaste: O(1)O(1)).
Elementin popping pinosta (monimutkaisuus: O(1)O(1)).
Tarkista, onko pino tyhjä vai ei (Vaikeusaste: O(1)O(1)).

Selvittääksemme, kuinka pino toimii, voimme käyttää evästepurkin analogiaa käytännössä. Kuvittele, että kulhon pohjalla on useita keksejä. Päälle voi laittaa vielä pari palaa tai päinvastoin yhden keksin päälle. Loput evästeet peittävät ylimmät, etkä tiedä niistä mitään. Näin asiat toimivat pinon kanssa. Käsitteen kuvaamiseen käytetään lyhennettä LIFO (Last In, First Out), joka korostaa, että pinoon viimeisenä tullut komponentti poistetaan siitä ensimmäisenä.

Jonottaa

Tämä on toisenlainen tietorakenne, joka tukee samoja vaihtoehtoja kuin pino, mutta sillä on päinvastainen semantiikka. Lyhennettä FIFO (First In, First Out) käytetään kuvaamaan jonoa, koska ensimmäisenä lisätty elementti poistetaan ensin. Rakenteen nimi puhuu puolestaan - toimintaperiaate on täysin identtinen kaupassa tai supermarketissa näkyvien jonojen kanssa.

joulukuuta

Tämä on toisenlainen tietorakenne, jota kutsutaan myös kaksipäiseksi jonoksi. Vaihtoehto tukee seuraava setti toiminnot:

Lisää elementti alkuun (Vaikeusaste: O(1)O(1)).
Pura komponentti alusta (vaikeusaste: O(1)O(1)).
Elementin lisääminen loppuun (vaikeusaste: O(1)O(1)).
Elementin irrottaminen päästä (Monimutkaisuus: O(1)O(1)).
Tarkista, onko kansi tyhjä (Vaikeusaste: O(1)O(1)).

Luettelot

Tämä rakenne data määrittelee sarjan lineaarisesti toisiinsa liittyviä komponentteja, joille sallitaan komponenttien lisääminen mihin tahansa luettelon paikkaan ja sen poistaminen. Lineaarinen lista määritellään osoittimella luettelon alkuun. Tyypillisiä listojen operaatioita: läpikulku, tietyn komponentin haku, elementin lisääminen, komponentin poistaminen, kahden listan yhdistäminen yhdeksi kokonaisuudeksi, listan jakaminen pariksi ja niin edelleen. On syytä mainita, että lineaarisessa luettelossa on ensimmäisen lisäksi edellinen komponentti jokaiselle elementille, ei viimeistä. Tämä tarkoittaa, että luettelon osat ovat järjestetyssä tilassa. Kyllä, tällaisen luettelon käsittely ei ole aina kätevää, koska ei ole mahdollista siirtyä päinvastaiseen suuntaan - luettelon lopusta alkuun. Lineaarisessa luettelossa voit kuitenkin käydä läpi kaikki komponentit askel askeleelta.

Siellä on myös soittolistoja. Tämä on sama rakenne kuin lineaarinen luettelo, vaikka sillä on lisäviestintää ensimmäisen ja viimeisen komponentin välillä. Toisin sanoen seuraaminen viimeinen elementti on ensimmäinen komponentti.

Tämän luettelon elementit ovat yhtä suuret. Ensimmäisen ja viimeisen valinta on sopimus.

puut

Tämä on kokoelma komponentteja, joita kutsutaan solmuiksi, joissa on pääkomponentti (yksi) juuren muodossa ja kaikki muut on jaettu moniin epäyhtenäisiin elementteihin. Jokainen sarja on puu, ja jokaisen puun juuri on puun juuren lapsi. Toisin sanoen kaikki komponentit liittyvät toisiinsa esi-isä-lapsi-suhteilla. Tämän seurauksena voidaan havaita solmujen hierarkkinen rakenne. Jos solmuilla ei ole lapsia, niitä kutsutaan lehtiksi. Puulle määritellään seuraavat toiminnot: komponentin lisääminen ja poistaminen, läpikulku, komponentin etsiminen. Binääripuilla on erityinen rooli tietojenkäsittelytieteessä. Mikä se on? Tämä erikoistapaus puu, jossa kullakin solmulla voi olla enintään pari lapsia, jotka ovat vasemman ja oikean alipuun juuret. Jos lisäksi puun solmuille täyttyy ehto, että kaikki vasemman alipuun komponenttien arvot ovat pienempiä kuin juuren arvot ja oikean alipuun komponenttien arvot ovat suurempi kuin juuri, niin tällaista puuta kutsutaan binäärihakupuuksi, ja se on tarkoitettu elementtien nopeaan löytämiseen. Miten hakualgoritmi toimii tässä tapauksessa? Hakuarvoa verrataan juuriarvoon, ja tuloksesta riippuen haku joko päättyy tai jatkuu, mutta yksinomaan vasemmassa tai oikeassa alipuussa. Vertailuoperaatioiden kokonaismäärä ei ylitä puun korkeutta (tämä on suurin määrä komponentteja polulla juuresta yhteen lehteen).

Kaaviot

Graafit ovat kokoelma komponentteja, joita kutsutaan pisteiksi, sekä joukko näiden kärkien välisiä suhteita, joita kutsutaan reunoiksi. Graafinen tulkinta Tämä rakenne on esitetty joukon pisteitä, jotka vastaavat pisteitä, ja jotkut parit on yhdistetty viivoilla tai nuolilla, jotka vastaavat reunoja. Viimeinen tapaus ehdottaa, että graafia pitäisi kutsua suunnatuksi.

Graafeja voidaan käyttää minkä tahansa rakenteen objektien kuvaamiseen. Ne ovat pääasiallinen väline monimutkaisten rakenteiden ja kaikkien järjestelmien toiminnan kuvaamiseen.

Lisätietoja abstraktista rakenteesta

Algoritmin rakentamiseksi on tarpeen formalisoida tiedot tai toisin sanoen tiedot on saatettava tiettyyn tietomalli, joka on jo tutkittu ja kirjoitettu. Kun malli on löydetty, voidaan sanoa, että abstrakti rakenne on muodostettu.

Tämä on päätietorakenne, joka osoittaa kohteen ominaisuudet, ominaisuudet, objektin komponenttien välisen suhteen ja sille suoritettavat toiminnot. Päätehtävänä on etsiä ja näyttää tietokonekorjaukseen sopivia tiedonesitysmuotoja. On heti syytä mainita, että tietojenkäsittelytiede eksakti tieteenä toimii muodollisten objektien kanssa.

Tietorakenteita analysoivat seuraavat objektit:

Kokonainen ja todellisia lukuja.
Boolen arvot.
Symbolit.

Kaikkien tietokoneen elementtien käsittelemiseksi on olemassa asianmukaiset algoritmit ja tietorakenteet. Tyypillisiä esineitä voidaan yhdistää monimutkaiset rakenteet. Voit lisätä niille toimintoja, sääntöjä tämän rakenteen tiettyihin osiin.

Tietojen organisaatiorakenne sisältää:

Vektorit.
Dynaamiset rakenteet.
Taulukot.
Moniulotteiset taulukot.
Kaaviot.

Jos kaikki elementit valitaan onnistuneesti, tämä on avain tehokkaiden algoritmien ja tietorakenteiden muodostumiseen. Jos käytät rakenteiden ja todellisten esineiden analogiaa käytännössä, voit ratkaista olemassa olevia ongelmia tehokkaasti.

On syytä huomata, että ohjelmoinnissa kaikki tiedon organisointirakenteet ovat olemassa erikseen. He työskentelivät paljon niiden parissa 1700- ja 1800-luvuilla, jolloin tietokoneesta ei ollut jälkeäkään.

Algoritmi on mahdollista kehittää abstraktin rakenteen suhteen, mutta algoritmin toteuttamiseksi tietyllä ohjelmointikielellä on löydettävä tekniikka sen esittämiseksi tietotyypeissä, operaattoreissa, joita tietty ohjelmointikieli tukee. Rakenteiden, kuten vektorin, taulukon, merkkijonon, sekvenssin, luomiseksi on monia ohjelmointikieliä klassisia tyyppejä tiedot: yksi- tai kaksiulotteinen taulukko, merkkijono, tiedosto.

Olemme käsitelleet tietorakenteiden ominaisuuksia, nyt kannattaa kiinnittää enemmän huomiota rakenteen käsitteen ymmärtämiseen. Kun ratkaiset mitä tahansa ongelmaa, sinun on työskenneltävä joidenkin tietojen kanssa tietojen toimien suorittamiseksi. Jokaisella tehtävällä on omat operaatiosarjansa, mutta tiettyä joukkoa käytetään käytännössä useammin eri tehtävien ratkaisemiseen. Tässä tapauksessa on hyödyllistä keksiä tietty tapa järjestää tietoa, jonka avulla voit suorittaa nämä toiminnot mahdollisimman tehokkaasti. Heti kun tämä menetelmä on ilmestynyt, voit ajatella, että sinulla on "musta laatikko", johon tietynlaisia tietoja tallennetaan ja joka alkaa suorittaa tiettyjä toimintoja tiedoilla. Näin voit paeta yksityiskohtia ja keskittyä täysin tehtävän ominaispiirteisiin. Tämä "musta laatikko" voidaan toteuttaa millä tahansa tavalla, mutta on pyrittävä mahdollisimman tuottavaan toteutukseen.

Kenen tämä pitää tietää?

Aloittelevien ohjelmoijien, jotka haluavat löytää paikkansa tällä alalla, mutta eivät tiedä minne mennä, tulisi tutustua tietoihin. Nämä ovat jokaisen ohjelmointikielen perusasiat, joten olisi hyvä idea heti oppia tietorakenteet ja sitten työskennellä niiden kanssa konkreettisia esimerkkejä ja tietyllä kielellä. Emme saa unohtaa, että jokaista rakennetta voidaan luonnehtia loogisilla ja fyysisillä esityksillä sekä joukolla operaatioita näille esityksille.

Älä unohda: jos puhut tästä tai tuosta rakenteesta, pidä mielessä sen looginen esitys, koska fyysinen esitys on täysin piilossa "ulkoiselta tarkkailijalta".

Muista lisäksi, että looginen esitys on täysin riippumaton ohjelmointikielestä ja tietokoneesta, kun taas fyysinen esitys on päinvastoin riippuvainen kääntäjistä ja tietokone teknologia. Esim, kaksiulotteinen matriisi Fortranissa ja Pascalissa voidaan esittää samalla tavalla ja fyysistä esitystapaa samalla tavalla tietokone on erilainen näillä kielillä.

Älä kiirehdi oppimaan tiettyjä rakenteita, on parasta ymmärtää niiden luokittelu, tutustua niihin kaikkiin teoriassa ja mieluiten käytännössä. On syytä muistaa, että vaihtelevuus on tärkeä rakenteen ominaisuus ja se ilmaisee staattista, dynaamista tai puolistaattista sijaintia. Opi perusasiat ennen kuin siirryt globaalimpiin asioihin, tämä auttaa sinua jatkokehityksessä.

Tietopankki on tiedon tallennuksen ja pääsyn organisointimuoto, ja se on järjestelmä, jossa on erityisesti organisoituja tietoja, ohjelmistoja, teknisiä, kielellisiä, organisatorisia ja metodologisia työkaluja, jotka on suunniteltu varmistamaan tietojen keskitetty kerääminen ja kollektiivinen monikäyttöinen käyttö.

Tietopankin tulee täyttää seuraavat vaatimukset:

* tyydyttää tiedon tarpeisiin ulkoiset käyttäjät tarjoavat mahdollisuuden tallentaa ja muuttaa suuria määriä erilaisia tietoja;
* täyttää tallennetun tiedon määritetyn luotettavuustason ja sen johdonmukaisuuden;
* pääsy tietoihin vain käyttäjille, joilla on asianmukaiset oikeudet;
* mahdollistaa tiedon etsimisen minkä tahansa ominaisuusryhmän perusteella;
* tyydyttää tarvittavat vaatimukset suorituskyvyn suhteen pyyntöjen käsittelyssä;
* pystyä järjestämään uudelleen ja laajentamaan ohjelmistojen rajojen muuttuessa;
* antaa käyttäjille tietoja useita muotoja;
* takaa yksinkertaisuuden ja mukavuuden ulkoisille käyttäjille pääsyn tietoihin;
* toteuttaa samanaikaisen huollon mahdollisuus suuri numero ulkopuoliset käyttäjät.

Tietopankki koostuu kahdesta pääkomponentista: tietokannasta ja tietokannan hallintajärjestelmästä.

Tietopankin ydin on tietokanta, joka on kokoelma toisiinsa liittyviä tietoja, jotka on tallennettu yhdessä minimaalisella redundanssilla, jotta sitä voidaan käyttää optimaalisesti yhteen tai useampaan sovellukseen. Tässä tapauksessa tiedot tallennetaan siten, että ne ovat riippumattomia sitä käyttävistä ohjelmista; Yleistä, hallittua menetelmää käytetään uuden tiedon lisäämiseen tai olemassa olevien tietojen muuntamiseen sekä tietojen etsimiseen tietokannasta.

Tietokantojen järjestämiseen sovelletaan seuraavia vaatimuksia:

1) helppo, nopea ja halpa tietokantasovellusten kehittäminen;
2) tietojen toistuvan käytön mahdollisuus;
3) henkisen työn kustannusten säilyttäminen, jotka ilmaistaan ohjelman ja loogisten tietorakenteiden olemassaolossa, jotka eivät muutu tietokantaan tehtäessä muutoksia;
4) yksinkertaisuus;
5) helppokäyttöisyys;
6) käytön joustavuus;
7) suuri nopeus suunnittelemattomien tietopyyntöjen käsittely;
8) muutosten tekemisen helppous;
9) alhaiset kustannukset; halpa tietojen tallentaminen ja käyttäminen sekä muutosten tekemisestä aiheutuvien kustannusten minimoiminen;
10) alhainen dataredundanssi;
11) tuottavuus;
12) tietojen luotettavuus ja saman päivitystason noudattaminen; on tarpeen valvoa tietojen luotettavuutta; järjestelmä estää läsnäolon eri versioita samat tietoelementit, käyttäjien saatavilla, päällä eri vaiheita päivitykset;
13) salassapito; luvaton pääsy pääsy tietoihin ei ole mahdollista; rajoittaa pääsyä samoihin tietoihin erilaisia tyyppejä niitä voidaan käyttää eri tavoin;
14) suojaa vääristymiseltä ja tuhoutumiselta; tiedot on suojattava häiriöiltä;
15) valmius; käyttäjä saa nopeasti tietoja aina kun hän sitä tarvitsee.

Tietopankin luomiseen ja toimintaan osallistuu eri kategorioiden käyttäjiä, joista pääluokka on loppukäyttäjät eli ne, joiden tarpeita varten tietopankki ollaan luomassa.

Tallennetun tiedon tyypin perusteella tietokannat jaetaan

· dokumentti,
· tosiasiallinen ja
· leksikografinen.

Joukossa dokumentti tietokannat on jaettu bibliografisiin, abstrakteihin ja kokotekstisiin.

TO leksikografinen tietokannat sisältävät erilaisia sanakirjoja (luokittelijat, monikieliset sanakirjat, perussanastojen sanakirjat jne.).

Järjestelmissä tosiasiallinen tyyppi tietokanta tallentaa tietoa käyttäjää kiinnostavista kohteista aihealue"faktojen" muodossa (esimerkiksi työntekijöiden elämäkertatiedot, tiedot valmistajien tuotteiden tuotannosta jne.); vastauksena käyttäjän pyyntöön annetaan vaaditut tiedot häntä kiinnostavasta kohteesta (objekteista) tai viesti, että haettua tietoa ei tietokannassa.

SISÄÄN dokumentti DB-tallennusyksikkö on dokumentti (esimerkiksi lain tai artiklan teksti), ja käyttäjälle annetaan pyynnöstään joko linkki asiakirjaan tai itse asiakirjaan, josta hän löytää tiedot. hän on kiinnostunut.

DB dokumentti tyyppi voidaan järjestää eri tavalla: ilman säilytystä ja itse varastoinnin kanssa alkuperäinen dokumentti koneella. Ensimmäisen tyypin järjestelmiin kuuluvat bibliografiset ja abstraktit tietokannat sekä hakemistotietokannat, jotka viittaavat tiedon lähteeseen. Järjestelmät, jotka tarjoavat tallennustilaa koko teksti asiakirjoja kutsutaan kokoteksteiksi.

Järjestelmissä dokumentti tyyppiä, haun tarkoitus voi olla paitsi jotkin asiakirjoihin tallennetut tiedot, myös itse asiakirjat. Siten kyselyt, kuten "kuinka monta asiakirjaa luotiin aikana tietty ajanjakso aika" jne. Usein hakukriteereinä ovat "asiakirjan hyväksymispäivämäärä", "kuka sen hyväksyi" ja muut asiakirjojen "tulostustiedot".

Tietty tietokantatyyppi on asiakirjalomakkeiden tietokanta. Niissä on joitain dokumenttijärjestelmien ominaisuuksia (haetaan asiakirjaa, ei tietoa tietystä objektista; asiakirjan muodossa on nimi, jota käytetään yleensä sen etsimiseen) ja erityispiirteitä (asiakirjaa ei etsitä tietojen poimimiseksi siitä, mutta sen käyttämiseksi mallina).

SISÄÄN viime vuodet kehittyy aktiivisesti oliosuuntautunut lähestymistapa luomiseen tietojärjestelmä. Objektitietokannat on järjestetty objekteiksi ja viittauksiksi objekteihin. Objekti edustaa dataa ja sääntöjä, joiden mukaan näille tiedoille suoritetaan toimintoja. Objekti sisältää menetelmän, joka on osa kohteen määritelmää ja tallennetaan objektin mukana. Objektitietokannassa tiedot tallennetaan objekteina, jotka on luokiteltu luokkatyyppeihin ja järjestetty hierarkkiseen luokkaperheeseen. Luokka on kokoelma objekteja, joilla on samat ominaisuudet. Objektit kuuluvat luokkaan. Luokat on järjestetty hierarkiaan.

Tietojen tallennuksen luonteen ja niihin pääsyn perusteella ne erotetaan toisistaan

· paikallinen (henkilökohtainen),
yleinen (integroitu, keskitetty) ja
hajautetut tietokannat

Henkilökohtainen tietokanta - on tietokanta, joka on suunniteltu paikalliseen käyttöön yksi käyttäjä. Jokainen käyttäjä voi luoda paikallisia tietokantoja itsenäisesti tai ne voidaan hakea yhteisestä tietokannasta.

Integroitu ja hajautettu Tietokannat mahdollistavat useiden käyttäjien samanaikaisen pääsyn samoihin tietoihin (monikäyttäjä, rinnakkaiskäyttötila). Tämä tuo erityisiä ongelmia suunnittelun ja BnD:n käytön aikana. Hajautettu DB:illä on lisäksi ominaisuudet liittyy siihen, että tietokannan fyysisesti eri osia voidaan sijoittaa erilaisia tietokoneita, ja loogisesti käyttäjän näkökulmasta niiden tulisi edustaa yhtä kokonaisuutta.

Tietokannat luokitellaan äänenvoimakkuutta. Erityinen paikka täällä on niin sanotuilla erittäin suurilla tietokannoilla. Tämä johtuu siitä, että varten suuria tietokantoja Tietojen säilyttämisen tehokkuuden varmistaminen ja käsittelyn varmistaminen asetetaan eri tavalla.

Tekijä: tietojen organisoinnin luonne Tietokannat voidaan jakaa

· jäsentämätön,
· osittain jäsennelty ja
· jäsennelty.

Tämä luokituksen merkki viittaa symbolisessa muodossa esitettyyn tietoon. Strukturoimattomat tietokannat voivat sisältää semanttisten verkkojen muodossa järjestettyjä tietokantoja. Pelkkätekstitietokantoja tai hypertekstijärjestelmiä voidaan pitää osittain jäsenneltyinä. Strukturoidut tietokannat vaativat alustavan suunnittelun ja tietokantarakenteen kuvauksen. Vasta sitten tämän tyyppiset tietokannat voidaan täyttää tiedoilla.

Strukturoidut tietokannat puolestaan käytetyn mallin tyyppi on jaettu

· hierarkkinen,
· verkko,
· suhteellinen,
· sekoitettu ja
· monimalli.

Luokittelu mallityypin mukaan ei koske vain tietokantoja, vaan myös DBMS-järjestelmiä.

Hierarkkinen, verkostomainen, suhteellinen

Hierarkkisessa mallissa tietojen välisiä suhteita voidaan kuvata järjestetyn graafin (tai puun) avulla. Yksinkertaistettu esitys tietojen välisistä suhteista hierarkkisessa mallissa on esitetty kuvassa.

Hierarkkisen tietokannan rakenteen (kaavion) kuvaamiseen tietyllä ohjelmointikielellä käytetään puurakennetta, jonka solmut sisältävät objekteja, joiden tietotyyppi on "solmu". Solmuobjekti on samanlainen kuin C-ohjelmointikielten rakennetietotyypit ja tietuetietotyypit. Pascalin kieli. Ne mahdollistavat tyyppien sisäkkäisyyden, joista jokainen on tietyllä tasolla. Solmutyyppi on komposiitti. Se sisältää viittauksia aliobjekteihin ("alipuihin"), joista jokainen on vuorostaan "solmutyyppi" muiden sisäkkäisten objektien kanssa. Jokainen "puu" koostuu yhdestä "juuri"-objektista (solmusta) ja järjestetystä joukosta (mahdollisesti tyhjiä) alisteisia solmuja. Jokainen "puun" sisältävistä perussolmuista sisältää yksinkertaista tai yhdistettyä tietoa, joka sisältyy siihen liitetyn objektiin. Yksinkertainen "solmu" kuljettaa verkossa yhden tyyppistä objektia, esimerkiksi numeerista, ja yhdistelmäobjekti yhdistää tietyn tyypin joukon, esimerkiksi kokonaisluvun, merkkijonon ja osoittimen (linkin). Esimerkki "puusta" solmujen kokoelmana on esitetty kuvassa.

Juurisolmu on solmu, jolla on alisteisia solmuja ja joka ei itse ole alisolmu. Orjasolmu (alisolmu) on sen esi-isänä (vanhempana) toimivan solmun lapsi. Saman solmun jälkeläiset ovat toistensa kaksosia. Yleensä "puu" on hierarkkisesti järjestetty "solmutyyppien" joukko. Hierarkkinen tietokanta on järjestetty kokoelma puita, joka sisältää solmutyyppisiä ilmentymiä (tietueita). Usein tyyppien väliset suhteet laajennetaan itse tietueiden välisiin suhteisiin. Tietuekentät tallentavat todelliset numeeriset tai symboliset arvot, jotka muodostavat tietokannan pääsisällön. Hierarkkisen tietokannan kaikkien elementtien läpikulku tapahtuu yleensä ylhäältä alas ja vasemmalta oikealle.

Verkkotietomallin avulla voit näyttää erilaisia tietoelementtien suhteita mielivaltaisen kaavion muodossa, mikä yleistää hierarkkisen tietomallin.

Verkkotietokantakaavion kuvaamiseen käytetään kahta tyyppiryhmää: "tietue" ja "viestintä". "Suhde"-tyyppi on määritelty kahdelle "tietue"tyypille: esi-isä ja jälkeläinen Tyyppi muuttujat"linkki" ovat esimerkkejä linkeistä.

Verkkotietokanta koostuu joukosta tietueita ja joukosta vastaavia suhteita. Yhteyden muodostukselle ei ole asetettu erityisiä rajoituksia. Jos sisään hierarkkiset rakenteet jälkeläisten tietueella voi olla vain yksi esi-isätietue, sitten sisään verkkomalli jälkeläisetietueessa voi olla mielivaltainen määrä esi-isätietueita (äitipuolia). Esimerkki yksinkertaisesta verkkotietokantakaaviosta on esitetty kuvassa. Liitäntöjen merkitys osoitetaan tässä tietuetyyppejä yhdistävillä viivoilla olevilla kirjoituksilla. Eri DBMS-järjestelmissä Verkkotyyppi Eri termejä käytetään usein merkitsemään olennaisesti identtisiä käsitteitä. Esimerkiksi tietoelementit ja aggregaatit, tietueet, joukot, alueet jne. Fyysinen sijainti verkkotyyppisten tietokantojen tiedot voidaan järjestää lähes samoilla menetelmillä kuin kohdassa hierarkkiset perusteet tiedot.

IBM:n työntekijä Udgar Codd ehdotti relaatiotietomallia, ja se perustuu suhteen käsitteeseen.

Relaatio on joukko elementtejä, joita kutsutaan monikoiksi. Parisuhteen visuaalinen esitysmuoto on ihmisen havainnolle tuttu kaksiulotteinen taulukko.

Taulukossa on rivejä (tietueita) ja sarakkeita (sarakkeita). Jokaisella taulukon rivillä on sama rakenne ja se koostuu kentistä. Taulukon rivit vastaavat monikoita ja sarakkeet relaatioattribuutteja.

On kätevää kuvata yhdellä taulukolla yksinkertaisin muoto tietojen väliset yhteydet, eli yhden objektin (ilmiön, entiteetin, järjestelmän jne.), jonka tiedot tallennetaan taulukkoon, jakaminen useisiin aliobjekteihin, joista jokainen vastaa riviä tai taulukkotietuetta. Lisäksi jokaisella aliobjektilla on sama rakenne tai ominaisuudet, jotka kuvataan tietuekenttien vastaavilla arvoilla. Taulukko voi sisältää esimerkiksi tietoja opiskelijaryhmästä, joista jokaisesta tunnetaan seuraavat ominaisuudet: sukunimi, etunimi ja sukunimi, sukupuoli, ikä ja koulutus. Koska ei ole mahdollista kuvailla monimutkaisempaa loogisia rakenteita aihealueen dataa, käytetään taulukkolinkitystä.

Tietojen fyysinen sijoittaminen relaatiotietokannat päällä ulkoinen media helppo tehdä tavallisilla tiedostoilla.