Koti-Selaimet-Abstrakti tietotyypin käsite. Abstraktit luokat ja luokan jäsenet

Abstrakti tietotyypin käsite. Abstraktit luokat ja luokan jäsenet

Osan "Tietojenkäsittelyn rakenteet ja algoritmit tietokoneessa" työohjelman liite

Abstrakti tietotyyppi "Lista".

Lista- tietyn tyyppisten elementtien sarja a1 , a2 , ..., a n, missä n https://pandia.ru/text/78/308/images/image001_307.gif "width =" 13 "height =" 16 "> 1, sitten a1

Kutsutaan ensimmäiseksi elementiksi ja an- luettelon viimeinen elementti. Luettelon kohteet on järjestetty lineaarisesti niiden sijainnin mukaan luettelossa. Ai elementti edeltää elementti ai+1 varten i = 1,2, n-1 ja ai pitäisi per ai-1 varten i = 2,3, n. Jokainen luettelon kohde ai Sillä on asemaa i, i=1,2, n. Listassa on paikka , merkitsee listan loppua - nolla. Se seuraa luettelon viimeistä kohtaa.

ADT "List" -operaattorit:

1. INSERT ( x, R,L). Tämä lause lisää objektin NS asemassa R luettelossa L, elementtien siirtäminen paikasta p ja edelleen seuraavaksi korkeampaan asemaan. Joten jos lista L koostuu elementeistä a1 , a2 , ..., an a1, a2, ..., ap-1, x, ap, ..., an.... Jos p ottaa arvon nolla, niin meillä on a1 , a2 , ..., an , , NS... Jos listassa L ei asentoa R, silloin tämän lausunnon tulos on määrittelemätön.

2. PAIKANTAA(x , L ). Tämä funktio palauttaa objektin sijainnin NS luettelossa L. Jos kohde on luettelossa x esiintyy useita kertoja, sitten palautetaan ensimmäisen objektin sijainti luettelon alusta NS. Jos esine NS ei listalla L sitten se palaa nolla.

3. HAKEA(p , L ). Tämä funktio palauttaa elementin sijaintiin R luettelossa L. Tulos on määrittelemätön jos p = nolla tai listassa L ei asentoa R.

4. POISTAA(p , L ). Tämä operaattori poistaa elementin sijainnissa R lista L. Joten jos lista L koostuu elementeistä a1 , a2 , ..., an, tämän operaattorin suorittamisen jälkeen se näyttää tältä a1, a2, ...,, ap- i , ap+ i, ..., a n. Tulos on määrittelemätön, jos luettelo sisältää L ei asentoa R tai R = nolla.

5. SEURAAVA ( p, L ) ja EDELLINEN (p, L ). Nämä funktiot palauttavat vastaavasti seuraavan ja edellisen sijainnin paikasta R luettelossa L. Jos R - viimeinen sija listalla L, sitten SEURAAVA (p, L) = nolla... NEXT-toiminto on määrittelemätön milloin p =nolla... PREVIOUS-toiminto on määrittelemätön, jos p = 1. Molemmat toiminnot ovat määrittelemättömiä, jos luettelo L ei asentoa R.

6. MAKENULL( L ) ... Tämä toiminto tekee luettelon L tyhjä ja palauttaa paikan nolla.

7. ENSIMMÄINEN(L ). Tämä funktio palauttaa listan L ensimmäisen sijainnin. Jos lista on tyhjä, paikka palautetaan nolla.

8. TULOSTUSLISTA(L ). Tulostaa luettelon kohteet L siinä järjestyksessä kuin ne näkyvät luettelossa.

Luettelonäkymä taulukon avulla:

Luettelonäkymä käyttäen Yksittäin linkitetty lista:

Legenda:

- osoitin luettelon alkuun,

· kestää - osoitin luettelon viimeiseen kohtaan ,

· maxpituus - luettelon enimmäispituus (elementtien lukumäärä).

Listan esittäminen kaksoislinkitetyn luettelon avulla:

Harjoitukset:

1. Kirjoita ohjelmia lajitellun listan elementtien lisäämiseen, poistamiseen ja etsimiseen käyttämällä listan toteuttamiseen

§ joukko,

§ osoittimia.

2. Kirjoita yhdistävä ohjelma

§ kaksi lajiteltua linkitettyä luetteloa,

§ n lajiteltua linkitettyä luetteloa,

3. Annettu muotoinen polynomi

p (x) = c1 xe1 + c2 xe2 + + kanssanNSn, missä e1> e2> ...> en> 0.

Tällainen polynomi voidaan esittää linkitettynä listana, jossa jokaisella elementillä on kolme kenttää: yksi kertoimelle kanssai toinen on eksponenttia varten ei kolmas on osoitin seuraavaan elementtiin. Kirjoita kuvatulle polynomien esitykselle ohjelma polynomien yhteen- ja kertolaskulle käyttämällä tätä esitystä.

4. Toteuta LIST ADT mille tahansa tietotyypille ja sen INSERT-, LOCATE-, RETRIEVE-, DELETE-, NEXT-, PREVIOUS-, MAKENULL-, PRINTLIST-käskyt:

§ luettelo annetaan taulukkona,

§ luettelo on määritelty yksittäiseksi linkitetyksi luetteloksi,

§ luettelo on määritetty kaksoislinkitetyksi luetteloksi.

Työohjelman kohta 2.1.2

Abstrakti tietotyyppi "Stack".

Pino - se on erityinen luettelo, jossa kaikki lisäykset ja poistot tehdään vain yhdessä päässä nimeltä huippu , (ylhäällä). Lisälaitetta käytetään pinoon LIFO(viimeinen sisään-ensimmäinen ulos - viimeinen sisään - ensimmäinen ulos).

ATD "Stack" -operaattorit:

1. MAKENULL(S). Tyhjennä S-pino.

2. TOP(S). Palauttaa kohteen pinon S yläosasta. Tavallisesti pinon yläosa tunnistetaan sijainnista 1, jolloin TOP (S) voidaan kirjoittaa yleisillä listaoperaattoreilla RETRIEVE (FIRST (S), S).

3. POP(S). Poistaa kohteen pinon yläosasta (pomppaa pinosta), listalausekkeissa tämä lause voidaan kirjoittaa muodossa DELETE (FIRST (S), S).

4. TYÖNTÄÄ(x, S ). Lisää elementin NS pinon S yläosaan (työntää esineen pinoon). Kohteesta, joka oli aiemmin pinon yläosassa, tulee se kohde, joka oli yläosan vieressä jne. Yleisten luettelooperaattoreiden kannalta tämä lauseke voidaan kirjoittaa muodossa INSERT (; c, FIRST (S, S).

5. TYHJÄ(S) ... Tämä funktio palauttaa arvon tosi, jos pino S tyhjä ja muuten väärä.

joukko:

Pinonäkymä käyttämällä Yksittäin linkitetty lista:

Harjoitukset:

Toteuta STACK ADT mille tahansa tietotyypille ja sen MAKENULL, TOP, POP, PUSH, EMPTY-operaattoreille.

§ pino on määritetty taulukoksi,

Pino on asetettu yksittäin linkitetyksi luetteloksi.

Työohjelman kohta 2.1.2

Abstrakti tietotyyppi "Jono".

Jonottaa (jono) on erityinen luettelo, jossa kohteet lisätään yhdestä päästä nimeltä takaosa (takana) ja poistetaan toisesta, edessä (edessä). Jonoja kutsutaan myös "FIFO-luetteloiksi" (FIFO tarkoittaa ensimmäinen sisään, ensimmäinen ulos). Jonoille suoritetut operaattorit ovat samanlaisia ​​kuin pinooperaattorit. Olennainen ero niiden välillä on, että niihin lisätään uusia elementtejä listan loppu eikä alussa, kuten pinoissa.

ADT "Queuen" operaattorit:

1. MAKENULL(K) tyhjentää jonon Q , tehdä siitä tyhjäksi.

2. ETU(K) - funktio, joka palauttaa jonon ensimmäisen elementin K. Voit ottaa tämän ominaisuuden käyttöön käyttämällä luettelooperaattoreita, kuten RETRIEVE (FIRST (Q), Q ).

3. ENQUEUE(a, Q) lisää elementin NS jonon lopussa Q.

Listaoperaattoreilla tämä operaattori voidaan suorittaa seuraavasti: INSERT (x, END (Q), Q ).

4. DEQUEUE(K) poistaa jonon Q ensimmäisen elementin . Toteutettavissa myös listakäskyillä, kuten DELETE (FIRST (Q), Q).

5. TYHJÄ(K) palauttaa tosi, jos ja vain jos Q ​​on tyhjä jono.

syklinen joukko:

Legenda:

K- jono,

K. edessä- osoitin jonon alkuun,

K. takaosa- osoitin jonon loppuun.

Jonoesitys kanssa Yksittäin linkitetty lista:

Harjoitukset:

Toteuta QUEUE ADT mille tahansa tietotyypille ja sen MAKENULL, FRONT, ENQUEUE, DEQUEUE, EMPTY käskyt.

Jono on määritetty pyöreäksi taulukoksi,

Jono on määritetty kaksoislinkitetyksi luetteloksi.

Abstrakti tietotyyppi "Puu".

Puu on kokoelma elementtejä nimeltä solmut (joista yksi on määritelty juuri ), ja suhteet ("emo"), jotka muodostavat solmujen hierarkkisen rakenteen. Solmut, kuten luetteloelementit, voivat olla minkä tahansa tyyppisiä elementtejä. Muodollisesti puu voidaan määritellä rekursiivisesti seuraavasti.

1. Yksi solmu on puu. Sama solmu on myös tämän puun juuri.

2. Anna NS - tämä on solmu, a T1 , T2, ...,Tk- juuret puut n1 . n2 , ..., nk vastaavasti. Voit rakentaa uuden puun tekemällä NS solmujen vanhempi n1 . n2 , ..., nk... Tässä puussa NS on juuri, a T1 , T2, ...,Tk - alipuut tämä juuri. Solmut n1 . n2 , ..., nk kutsutaan pojat solmu NS.

Tämä määritelmä sisältää usein käsitteen tyhjä puu , eli "puu" ilman solmuja, tällainen puu on merkitty sanalla nolla .

Esimerkki: Tietoja kirjan luku voidaan esittää kaavamaisesti puulla. Vanhemman ja pojan suhde näytetään rivinä. Puut piirretään yleensä ylhäältä alas vanhempien ollessa "lasten" yläpuolella.

DIV_ADBLOCK135 ">

Solmun korkeus puu on pisimmän polun pituus tästä solmusta lehtiin. Esimerkissä solmun korkeus Luku 1 on yhtä suuri kuin 1, solmu Kappale 2 - 2 ja solmu Ch. Z - 0. Puun korkeus on sama kuin juuren korkeus. Solmun syvyys määritellään polun pituudeksi (se on ainoa) juuresta tähän solmuun.

Solmun pojat järjestetään yleensä vasemmalta oikealle. Siksi kuvion kaksi puuta ovat erilaisia ​​solmun poikien järjestyksessä a eri. Jos poikien järjestystä ei oteta huomioon, niin sellaista puuta kutsutaan häiriintynyt , muuten puu on nimeltään järjestyksessä .

ATD "Treen" operaattorit:

1. VANHEMPI(n, T). Tämä funktio palauttaa solmun vanhemman NS puussa T. Jos NS on juuri, jolla ei ole vanhempia, niin tässä tapauksessa se palauttaa nolla... Tässä nolla osoittaa, että rajojen ulkopuolinen puu on tapahtunut.

2. VASEMMALLA__ LAPSI(n , T). Tämä funktio palauttaa solmun vasemmanpuoleisimman lapsen. n puussa T. Jos n on lehti (ja siksi sillä ei ole poikaa), niin se palaa nolla.

3. OIKEIN_ sisarus(n , T). Tämä funktio palauttaa solmun oikean sisaruksen NS puussa T tai arvo nolla,. jos sitä ei ole olemassa. Tätä varten vanhempi on R solmu NS ja kaikki solmun pojat R, sitten näiden poikien joukossa on solmu välittömästi oikealla puolella. solmu NS.

4. LABEL(n , T ). Palauttaa solmun tunnisteen n... puu T. Tämä toiminto edellyttää, että puun solmuihin määritetään tunnisteet.

5. LUODA(v , T 1 , T 2 , ..., Ti ,) on funktioperhe, joka luo uuden juuren jokaiselle i = 0, 1, 2, ... r etiketillä v ja sitten tälle juurelle syntyy i poikia, joista tulee alipuiden juuria T1 , T2, ....Ti;. Nämä funktiot palauttavat juurtuneen puun r... Huomaa, että jos i = 0, palautetaan yksi solmu r, joka on sekä juuri että lehti.

6. JUURI(T ) palauttaa solmun, joka on puun juuri T, Jos T- tyhjä puu palaa sitten nolla.

7. MAKENULL(T ). Tämä operaattori tekee puun T tyhjä puu.

Puun esittäminen vanhempien ryhmällä:

Puunäkymä linkitetyillä listoilla:

Edustaa puuta vasemmiston poikien ja oikeiden veljien avulla.

Kuvan nimitykset:

solmutila – joukko puun solmuja,

    etiketti – solmutunniste, otsikko – vasemman pojan hakemisto poikaluettelossa,

solupaasi – joukko luetteloita solmujen pojista,

    solmu – osoitin taulukon solmuunsolmutila , Seuraava – oikean pojan hakemisto poikaluettelossa.

Harjoitukset:

1. Annettu puu:

DIV_ADBLOCK137 ">

§ puu annetaan joukkona solmutietueita, jotka sisältävät vasemmanpuoleisimman pojan indeksin, oikean sisaruksen indeksin ja tunnisteen,

Yhdistetty binääripuu määritellään osoittimilla vasemmalle ja oikealle pojille.

4. Kirjoita funktiot binääripuun läpikulkua varten eteenpäin, taaksepäin ja symmetrisessä järjestyksessä.

Työohjelman kohta 2.1.3

Abstrakti tietotyyppi "Set".

Paljon on yleensä kuvattu sen elementtien sarjana, joka on suljettu aaltosulkeisiin, esimerkiksi (1, 4) tarkoittaa joukkoa, joka koostuu kahdesta alkiosta - numeroista 1 ja 4. Joukon elementtien kirjoitusjärjestys ei ole olennainen, joten voit kirjoittaa (4, 1) samalla tavalla kuin (1, 4), kun kirjoitat samaa joukkoa. Joukko ei ole luettelo (ainakaan elementtien mielivaltaisen järjestyksen vuoksi). Joukossa ei ole päällekkäisiä elementtejä ((1, 4, 1) ei ole joukko).

Joukkoteorian peruskäsite on relaatiokäsite sarjaan kuuluvaa merkitty symbolilla. Eli sisääntulo NS NS ei kuulu sarjaan A", eli NS ei ole sarjan jäsen A... On olemassa erityinen joukko, joka on merkitty symbolilla nimeltä tyhjä, monta , ja jossa ei ole elementtejä. Aseta DIV_ADBLOCK138 ">

He sanovat, että joukko A sisältää setissä V(tai kytkeytyy päälle joukossa V), kirjoitettu A V tai V A jos jokin joukon elementti A on myös osa settiä V. Kun A V myös sanoa, että asetettu A on joukon osajoukko V.

Esimerkiksi (1, 2) https://pandia.ru/text/78/308/images/image019_36.gif "width =" 15 "height =" 15 src = "> V ja AB, niin joukkoa A kutsutaan oma, totta tai tiukka alajoukko joukoittain V.

Tärkeimmät joukoille suoritettavat operaatiot ovat liitto, leikkaus ja ero. Konsolidointi sarjat A ja V(merkitty A V) kutsutaan joukoksi, joka koostuu vähintään yhteen joukkoon kuuluvista alkioista A ja V.

Ylitys sarjat A ja V(merkitty A V) kutsutaan joukoksi, joka koostuu vain niistä alkioista, jotka kuuluvat joukkoon A, ja setti V. Ero sarjat A ja V(merkitty A\ B) kutsutaan joukoksi, joka koostuu vain joukon niistä elementeistä A jotka eivät kuulu joukkoon V.

Jos esimerkiksi A = (a, b, c) ja B = (b, a), niin A B = (a, b, c, d), A B = (b) ja A \ B = (a, c ) .

ADT "Set" -operaattorit:

1. LIITTO(A, B, C) A ja V KANSSA, yhtä suuri A V.

2. RISTEYS(A, B, C) on "input"-argumentit asetettu A ja V, ja seurauksena - "lähtö" -joukko KANSSA, yhtä suuri A V..

3. ERO(A, B, C) on "input"-argumentit asetettu A ja V, ja seurauksena - "lähtö" -joukko KANSSA, yhtä suuri A \ B.

4. YHDISTÄÄ( A , B, C) operaattori suorittaa fuusio (yhdistää), tai hajautettujen joukkojen liitto . Tämä operaattori ei eroa operaattorista. LIITTO, mutta tässä oletetaan, että operandi asettaa älä leikkaa (eli niillä ei ole yhteisiä elementtejä). Operaattori määrittää joukon KANSSA merkitys A V, mutta tulos on määrittelemätön, jos A B, eli siinä tapauksessa, että sarjat A ja V niillä on yhteisiä elementtejä.

5. jäsen(x, A ) on asetettu argumentteja A ja vastustaa NS samaa tyyppiä kuin joukon elementit A, ja palauttaa loogisen arvon totta(tosi) jos NS a "," b "," c ")) = "a". Operaattori MAX.

11.YHTÄ SUURI(A , V ) palauttaa arvon totta jos ja vain jos asetetaan A ja V koostuvat samoista elementeistä.

12. LÖYTÖ(x ) toimii ympäristössä, jossa on joukko hajanaisia ​​joukkoja. Se palauttaa elementin sisältävän joukon nimen (yksikkö). NS.

Aseta edustus:

Joukko voidaan määrittää taulukon tai linkitetyn listan avulla.

Harjoitukset:

1. Kaksi joukkoa A = (1, 2, 3) ja B = (3, 4, 5) on annettu. Mikä on tulos seuraavien lauseiden suorittamisesta?

UNIONI (A.B.C),

RISTEKSI (A, B, C),

EROTUS (A. B. C),

JÄSEN (l. A),

LISÄÄ (1, A),

POISTA (1, A),

2. Toteuta Set ADT mille tahansa tietotyypille ja sen MAKENULL-, UNION-, INTERSECTION-, MEMBER-, MIN-operaattoreille.

Joukko määritetään käyttämällä kiinteän pituista taulukkoa ja osoitinta taulukon viimeiseen varattuun kohtaan,

Joukko määritetään lajittelemattoman linkitettyjen luettelon avulla,

Joukko määritetään käyttämällä lajiteltua linkitettyä luetteloa,

Työohjelman kohta 2.1.3

Erikoissarjat

Binäärihakupuu Abstrakti tietotyyppi

Binäärihakupuu - tietorakenne joukkojen esittämiseksi, joiden elementit on järjestetty jonkin lineaarisen järjestysrelaation mukaan. Binäärihakupuut voivat toteuttaa joukkooperaattoreita LISÄÄ, POISTAA, JÄSEN ja MIN, ja niiden keskimääräinen suoritusaika on suuruusluokkaa O (log n) joukoille, jotka koostuvat NS elementtejä.

Binäärihakupuulle on ominaista, että sen solmut on merkitty joukkoelementeillä (puun solmut sisältävät joukkoelementtejä). Lisäksi kaikki elementit, jotka on tallennettu minkä tahansa solmun vasemman alipuun solmuihin NS, pienempi kuin solmun sisältämä elementti NS, ja kaikki solmun oikean alipuun solmuihin tallennetut elementit NS, enemmän kuin solmun sisältämä elementti NS.

Esimerkkejä binääripuusta:

https://pandia.ru/text/78/308/images/image023_7.jpg "width =" 277 "height =" 122 src = ">

AVL-puunäkymä on sama kuin binäärihakupuunäkymä.

Toinen tasapainoisen hakupuun tyyppi on 2-3 puuta. 2-3 puun rakenne eroaa binäärihakupuun rakenteesta.2-3 puulle on tyypillistä, että kaikilla solmuilla on 2 tai 3 poikaa, kaikki polut juuresta lehtiin ovat samanpituisia ja kaikki sarjan elementit sisältyvät lehtiin. Puun solmut 2-3 on jaettu sisäisiin ja terminaalisiin (lehtiin). Sisäisiä solmuja käytetään vain reitityspuuhakuihin. Jokainen sisäinen solmu sisältää toisen ja kolmannen pojan pienimpien elementtien avaimet (jos on kolmas poika) ja osoittimet poikien solmuihin.

Binaarihaku yhdistetty puunäkymä:

Tasapainoisesti yhdistetyn 2-3 puun esitys:

Harjoitukset:

1. Piirrä kaikki mahdolliset binäärihakupuut neljälle elementille 1, 2, 3 ja 4.

2. Lisää kokonaisluvut 7, 2, 9, 0, 5, 6, 8, 1 tyhjään binäärihakupuuhun.

3. Näytä edellisessä harjoituksessa saadusta puusta luvun 7 ja sitten luvun 2 poistamisen tulos.

4. Piirrä 2-3 puu, joka syntyy lisäämällä elementit 5, 2, 7, 0, 3, 4, 6, 1, 8, 9 tyhjään joukkoon (esitetty puuna 2-3).

5. Näytä edellisessä harjoituksessa saadun puun elementin 3 poistamisen tulos 2-3:sta.

3. Toteuta hakupuu ADT mille tahansa tietotyypille ja sen INSERT-, DELETE-, MEMBER- ja MIN-käskyt.

Puu annetaan yhdistettynä binääripuuna

Puu annetaan 2-3 puuna

Työohjelman kohta 2.1.3

Abstrakti tietotyyppi "Sanakirja".

Sanakirja - sarja, joka on tarkoitettu "nykyisten" objektien tallentamiseen lisäämällä tai poistamalla joitain niistä ajoittain. Ajoittain on myös tarpeen selvittää, onko tietty elementti läsnä tietyssä joukossa. Sanakirja on toteutettu käyttämällä sanakirja ADT:tä operaattorien kanssa LISÄÄ,POISTAA ja JÄSEN... Sanakirjaoperaattorisarja sisältää myös operaattorin MAKENULL ADT-tietorakenteiden alustamiseen.

Sanakirja voidaan esittää hash-taulukon avulla. Taulukko on rakennettu seuraavan idean pohjalta: potentiaalinen elementtijoukko (mahdollisesti ääretön) jaetaan äärelliseen määrään luokkia. varten V luokat numeroitu 0 - KOHDASSA 1, rakenteilla hash-toiminto h niin että mille tahansa elementille NS alkuperäinen asetustoiminto h (x) ottaa kokonaisluvun väliltä 0, ..., V - 1, joka vastaa luokkaa, johon elementti kuuluu NS. Elementti NS usein soittaa avain, h ( x) - hash-arvo x, ja "luokat" - segmentit ... Hajautustörmäysten ratkaiseminen (joukon kahdella elementillä on sama arvo h (x)), käytetään sekä julkista että yksityistä tiivistystä.

avaa hash-taulukko

Joukko nimeltään segmenttitaulukko ja indeksoitu segmentin numerot 0, 1, ..., B - 1 , sisältää otsikot kohteelle V linkitetyt luettelot. Elementti i-th list on alkuperäisen joukon elementti, jolle h(.x :) =i.

Sanakirjaesitys kanssa yksityinen hash-taulukko

Segmenttitaulukko tallentaa suoraan sanaston elementit. Siksi kuhunkin segmenttiin voidaan tallentaa vain yksi sanakirjaelementti. Yksityisessä hajautustekniikassa käytetään tekniikkaa uudelleen hajautus ... Kun yritetään sijoittaa elementtiä x segmenttiin numeroitu h ( x ) , joka on jo toisen elementin varaama, valitaan segmenttinumeroiden sarja h 1 ( x ) ,h 2 ( x ) , … mihin elementti voidaan sijoittaa. Jokaisen segmentin käyttöaste tarkistetaan peräkkäin, kunnes vapaa segmentti löytyy. Elementti asetetaan siihen x ... Erilaisia ​​törmäyksen ratkaisumenetelmiä käytetään segmenttinumeroiden asettamiseen uudelleen hajauttamisen yhteydessä. Esimerkiksi lineaarinen hajautusmenetelmä, keskineliön menetelmä, satunnainen hajautusmenetelmä

Harjoitukset:

1. Oletetaan, että käytät tiivistefunktiota h (i) = i% 7 tiivistämään kokonaisluvut 7-segmentiseen hash-taulukkoon.

· Anna tuloksena saatu hash-taulukko, jos siihen on lisätty tarkat kuutiot 1, 8, 27,64,125, 216,343;

· Toista edellinen kohta suljetulle hash-taulukolle lineaarisella törmäysratkaisutekniikalla.

2. Oletetaan, että on olemassa yksityinen hajautustaulukko, jossa on 5 segmenttiä, hash-funktio h (i) = i% 5 ja lineaarinen törmäysratkaisutekniikka. Näytä tulos numerosarjan 23, 48, 35, 4, 10 lisäämisestä alun perin tyhjään hash-taulukkoon.

3. Toteuta sanakirja ADT tekstijonoille ja sen INSERT-käskyt , POISTA, JÄSEN ja MAKENULL

Sanakirja määritetään avoimella hash-taulukolla,

Sanakirja määritetään suljetulla hash-taulukolla lineaarisella törmäysratkaisutekniikalla,

Työohjelman kohta 2.1.3

Abstrakti tietotyyppi "Näyttö".

Näyttö - tämä on joukko, jonka elementeille on määritelty samantyyppisten elementtien näyttötoiminto ( määrittelyalueita ) toisen tyyppisiin elementteihin ( arvoalue ) toista tyyppiä. Näyttö M vastaa elementtiä d tyypin domaintype laajuudesta elementtiin r tyyppiä aluetyyppi alueelta: M(d) = r.Tyhjä näyttö ei sisällä mitään elementtejä

ADT "Display" -operaattorit:

1. MAKENULL(M ). Tekee näytön M tyhjä.

2. ASSIGN (M DR). Tekee M(d) yhtä suuri r ei väliä kuinka M(d) määriteltiin aiemmin.

3. LASKE ( M, d, r). Palauttaa tosi ja antaa arvon r:lle M(d), jos jälkimmäinen on määritelty, ja palauttaa muuten epätosi.

Näyttönäkymä: kartoitus voidaan toteuttaa tehokkaasti hash-taulukoiden avulla. Tässä x määrittää arvon näytön määritelmän laajuudesta ja taulukon elementin numerolla h ( x ) - elementti valikoimasta.

Työohjelman kohta 2.1.3

Priority Queue Abstrakti tietotyyppi

Prioriteettijono on joukko, jonka elementeille on asetettu prioriteettifunktio, eli jokaiselle elementille x set, voit laskea funktion R( x )- elementin prioriteetti x , joka yleensä ottaa arvot joukosta reaalilukuja tai yleisemmin jostain lineaarisesti järjestetystä joukosta.

ADT "prioriteettijono" perustuu ADT "Set" operaattoreiden kanssa LISÄÄ ja POISTA ja myös operaattorin kanssa MAKENULL alustaaksesi tietorakenteen. Operaattori LISÄÄ prioriteettijonolle ymmärretään tavallisessa merkityksessä, while POISTA on funktio, joka palauttaa alimman prioriteetin omaavan elementin ja sivuvaikutuksena poistaa sen joukosta.

Jonoesitys kanssa tilattu kaksoislinkitetty luettelo.


Jonoesitys kanssa osittain tilattu yhdistetty puu:

Tämän toteutuksen pääideana on järjestää jonon elementit binääripuuhun. Alemmalla tasolla, josta jotkut lehdet saattavat puuttua, kaikki puuttuvat lehdet voivat sijaita vain nykyisten alemman tason lehtien oikealla puolella. Se on tärkeämpää kuin puu osittain tilattu . Tämä tarkoittaa, että solmun prioriteetti v ei suurempi kuin minkään solmun pojan prioriteetti v, missä solmun prioriteetti on tähän solmuun tallennetun kohteen prioriteettiarvo. Kuvasta näkyy, että pienet prioriteettiarvot eivät voi esiintyä korkeammalla tasolla, missä on suuria prioriteettiarvoja.

DELETEMIN-funktio palauttaa alimman prioriteetin kohteen, jonka on oltava puun juuri. Puun tuhoamisen välttämiseksi ja puun prioriteettiarvojen osittaisen järjestyksen säilyttämiseksi juuren poistamisen jälkeen suoritetaan seuraavat toimenpiteet: oikeanpuoleisin solmu sijaitsee alimmalla tasolla ja sijoitetaan väliaikaisesti puun juurelle. puu. Tämä elementti laskeutuu sitten alas puun oksia (alemmille tasoille) vaihtaen paikkoja alemman prioriteetin poikien kanssa matkan varrella, kunnes tästä elementistä tulee lehti tai se joutuu asemaan, jossa sen pojilla on vähintään yhtä suuri etuoikeus.

Jonon esitys taulukolla, joka sisältää osittain järjestetyn puun solmut:

Joukossa A ensimmäinen n paikat vastaavat n puun solmut. Elementti A sisältää puun juuren. Puusolmun vasen poika A[ i], jos se on olemassa, se on solussa A, ja oikea poika, jos hän on olemassa, on sellissä A. Päinvastoin, jos poika on sellissä A[ i], sitten sen vanhempi on solussa A[ i%2] ... Puun solmut täyttävät solut A, A, … A[ n] peräkkäin taso tasolta alkaen juuresta ja tason sisällä - vasemmalta oikealle. Yllä esitettyä puuta edustaa taulukossa seuraava solmujen sekvenssi: 3, 5, 9, 6, 8, 9, 10, 10, 18, 9.

Harjoitukset:

1. Piirrä osittain järjestetty puu lisäämällä tyhjään puuhun kokonaisluvut 5, 6, 4, 9, 3, 1 ja 7. Mitä seuraa kolmen peräkkäisen DELETEMIN-käskyn soveltamisesta tähän puuhun?

2. Ota käyttöön Priority Queue ADT mille tahansa tietotyypille ja sen INSERT-, DELETEMIN- ja MAKENULL-käskyt

§ osittain järjestetty puu toteutetaan osoittimilla,

§ Osittain järjestetty puu toteutetaan taulukon avulla.

Työohjelman kohta 2.1.3

Abstrakti tietotyyppi "Union of Sets".

ADT on objektien liitto, joista jokainen on joukko. Tärkeimmät tällaiselle joukolle suoritettavat toimet ovat joukkojen yhdistäminen tiettyyn järjestykseen sekä sen tarkistaminen, kuuluuko tietty objekti tiettyyn joukkoon. Nämä tehtävät ratkaistaan ​​operaattoreiden avulla YHDISTÄÄ(Tyhjennä) ja LÖYTÖ(Löytö). Yhdistä operaattori ( A, B, C) tekee sarjan KANSSA yhtä suuri kuin joukkojen liitto A ja V jos nämä joukot eivät leikkaa (eli niillä ei ole yhteisiä elementtejä); tämä operaattori on määrittelemätön, jos asettaa A ja V leikkaavat. ETSI-toiminto ( x) palauttaa joukon, johon elementti kuuluu NS; siinä tapauksessa, kun NS kuuluu useaan joukkoon tai ei kuulu yhteenkään, tämän funktion arvo on määrittelemätön.

ADT "Union of Sets" operaattorit:

1. YHDISTÄÄ(A , V) yhdistää komponentteja A ja ... V, tulokseksi määritetään joko A tai V.

2. LÖYTÖ(x ) - funktio, joka palauttaa sen komponentin nimen, johon se kuuluu NS.

3. ALKUKIRJAIN(A , NS ) luo A-nimisen komponentin, joka sisältää vain elementin NS.

Joukkojen liiton esitys taulukoita käyttämällä:

Asetuksen nimi on sama kuin taulukon indeksiarvo setheaders ( nimi 0 )

Legenda:

setheaders - joukko asetettuja otsikoita:

§ kanssa count - sarjan elementtien lukumäärä,

§ ensimmäinen elementti - taulukkoindeksinimetjoukon ensimmäisen elementin kanssa,

nimet – joukko joukon elementtiluetteloita:

    setname - sen joukon nimi, johon elementti kuuluu, seuraava elementti - annetun joukon listan seuraavan alkion indeksi (indeksin arvo 0 on listan lopussa).

Työohjelman kohta 2.1.3

Abstrakti tietotyyppi “ Suunnattu kaavio "

Perusmääritelmät:

Suunnattu graafi (digrafi ) G = (V, E) koostuu useista pisteistä V ja monia kaaria E. Pisteitä kutsutaan myös solmut , ja kaaria - suunnatut kylkiluut . Kaari voidaan esittää järjestetynä kärkiparina ( u, w), missä on huippu ja nimeltään alku , a w - loppu kaaria.

He myös sanovat, että kaari ja -> w johtaa ylhäältä huipulle w, ja yläosa w vieressä topin kanssa v.

Digraafiesimerkki 1:

Digrafipisteitä voidaan käyttää edustamaan objekteja ja kaaria voidaan käyttää objektien välisten suhteiden esittämiseen.

Tekijä: digraafissa tarkoitamme kärkijonoa v1 , v2 , … , vn , , joille on olemassa kaaria v1 -> v2 , v2 , -> v3, , ..., vn-1 , -> vn. Tämä polku alkaa ylhäältä v1 ja kulkee yläosien läpi v2 , v3 , ..., vn-1 päättyy yläosaan vn. Polun pituus - polun muodostavien kaarien lukumäärä, tässä tapauksessa polun pituus on NS - 1 ... Tarkastellaan polun erikoistapauksena yhtä kärkeä v poluna, jonka pituus on 0 kärjestä vVastaanottaja sama huippu v... Kuvassa kärkien 1, 2, 4 sarja muodostaa 2 pituisen polun kärjestä 1 kärkeen 4.

Polkua kutsutaan yksinkertainen , jos kaikki sen kärjet, ensimmäistä ja viimeistä mahdollisesti lukuun ottamatta, ovat erilaisia. Kierrä - se on yksinkertainen polku, jonka pituus on vähintään 1 ja joka alkaa ja päättyy samaan kärkeen. Kuvassa kärjet 3, 2, 4, 3 muodostavat syklin, jonka pituus on 3.

Monissa sovelluksissa on kätevää liittää tietoja digraafin kärkiin ja kaareihin. Näihin tarkoituksiin sitä käytetään merkitty digrafi , eli digrafi, jossa jokaisella kaarella ja/tai jokaisella kärjellä on vastaavat tunnisteet. Tarra voi olla nimi, paino tai arvo (kaaret) tai jonkin tietyn tyyppinen tietoarvo.

Esimerkki 2 merkitystä digraafista:

DIV_ADBLOCK149 ">

3. Transitiivinen sulkemisalgoritmi (Warshallin algoritmi):

Kaaviota varten G = (V, E) algoritmi laskee transitiivisuusmatriisin T, jonka jokainen elementti T[i, j] = 1 vain silloin, kun ylhäältä on polku i huipulle j ja T[ i, j] = 0 muuten.

4. Algoritmi digraafin keskipisteen löytämiseksi:

Anna olla ja - digraafin mielivaltainen kärki G = (V, E). Epäkeskisyys (maksimi poisto) topit ja määritelty

max (vähimmäisreitin pituus ylhäältä w huipulle v }

w V

Digrafikeskus G kutsutaan kärkeä, jolla on pienin epäkeskisyys. Toisin sanoen digrafin keskipiste on se kärki, jonka maksimietäisyys (polun pituus) muihin pisteisiin on minimaalinen.

Esimerkki: Digraafin keskipiste on kärki d

Eccentr-t

5. Algoritmi digrafin läpikulkua varten (syvyyshaku):

Monien suunnattujen graafien ongelmien ratkaisemisessa tarvitaan tehokas menetelmä digrafien kärkien ja kaarien systemaattiseen läpikulkuun. Tämä menetelmä on ns syvähaku - ennakkotilauspuun läpikulkumenetelmän yleistäminen. Syvyyshaku alkaa valitsemalla aloituspiste v Kreivi G, tämä kärki on merkitty etiketillä vieraili (vieraillut). Sitten jokaiselle kärjen viereiselle kärjelle v ja jossa ei ole vieraillut aikaisemmin, syvähakua käytetään rekursiivisesti. Kun kaikki huiput, joihin huipulta pääsee v, "kunniataan" vierailulla, haku päättyy. Jos joissakin pisteissä ei ole käyty, valitaan yksi niistä ja haku toistetaan. Tätä prosessia jatketaan, kunnes kaikki digraafin kärjet on kuljetettu G.

6. Algoritmi graafin syvän virittävän puun muodostamiseksi:

Kun graafia kuljetetaan käyttämällä syvyyshakua, vain tietyt kaaret johtavat käyttämättömiin huippupisteisiin. Tällaisia ​​kaaria, jotka johtavat uusiin pisteisiin, kutsutaan puukaareiksi ja muodostavat graafin syvyyden ensimmäinen ulottuva metsä – syvälle ulottuva metsä ... Metsää rakennettaessa erotetaan myös kolme tyyppistä kaaria: käänteinen, suora ja poikittainen. Käänteiset kaaret - sellaiset kaaret, jotka menevät jälkeläisistä esivanhemmille kattavassa metsässä. Suorat kaaret Kaariksi kutsutaan kaaria, jotka siirtyvät esivanhemmista todellisiksi jälkeläisiksi, mutta jotka eivät ole puukaareja.

Kaaria, jotka yhdistävät pisteitä, jotka eivät ole toistensa esi- tai jälkeläisiä, kutsutaan poikittaiskaaret ... Jos virittävää puuta rakennettaessa yhden kärjen pojat sijoittuvat käyntinsä järjestyksessä vasemmalta oikealle ja jos metsään lisätään myös uusia puita vasemmalta oikealle, niin kaikki poikittaiskaaret menevät oikealta vasemmalle. .

Esimerkiksi kaaria D-> C ja G-> D- poikittainen, kaari C-> A- taaksepäin, suoria kaaria ei ole.

Kun puuta kuljetetaan syvältä, on usein kätevää numeroida kärjet siinä järjestyksessä, jossa niissä on käyty. Tällaisia ​​lukuja kutsutaan syvyysluvuiksi.

Digrafiesitys:

§ Digraafin esitys vierekkäisyysmatriisin avulla:

Vierekkäisyysmatriisi digrafille G - tämä on matriisi A koko n n boolen arvoilla, missä A[ i, j] = totta jos ja vain jos kärjestä tulee kaari i kärkeen j. Usein vierekkäisissä matriiseissa arvo totta korvataan luvulla 1 ja arvolla väärä- 0:aan.

Digraafin esityksen yleistämistä vierekkäisyysmatriisin avulla voidaan pitää leimatun digraafin esityksenä myös vierekkäisyysmatriisia käyttäen, mutta jolle elementti A[ i, j] yhtä suuri kuin kaarimerkki minä ->j. Jos kaaria ylhäältä i huipulle j ei ole olemassa, niin arvo A [ i, j] ei voi olla minkään kelvollisen tunnisteen arvo, mutta sitä voidaan pitää "tyhjänä" soluna.

Vierekkäisyysmatriisi merkitylle digrafille (esimerkki 2):

§ Digraafin esitys vierekkäisyysluetteloilla:

Vertexin viereisyysluettelo i kutsutaan luetteloksi kaikista kärjen viereisistä pisteistä i, lisäksi tilattu tietyllä tavalla. Digraph G voidaan esittää taulukon avulla PÄÄ(Otsikko), jonka elementti PÄÄ[i] on osoitin kärkipisteiden viereisyysluetteloon i.


ATD "Orgraph" -operaattorit:

Yleisimmät suunnatuille graafille suoritettavat operaattorit sisältävät vertexin ja kaaritunnisteen lukemisen, kärjen ja kaaren lisääminen ja poistaminen sekä kaarisekvenssin läpikulku.

Vierekkäisten kärkien joukon katsomiseen tarvitaan seuraavat kolme operaattoria.

1. ENSIMMÄINEN ( v) palauttaa kärjen vieressä olevan ensimmäisen kärjen indeksin v. Jos yläosa v ei ole vierekkäisiä pisteitä, niin "nolla" -piste palautetaan nolla.

2. SEURAAVA ( v, i) palauttaa kärjen vieressä olevan kärjen indeksin v, indeksin jälkeen i. Jos minä - tämä on viimeisen kärjen vieressä olevan kärjen indeksi v, sitten se palaa nolla.

3. VERTEX ( v,i) palauttaa yläosan indeksillä i viereisestä kärkijoukosta v.

Harjoitukset:

Annettu suunnattu graafi (digraafi):

https://pandia.ru/text/78/308/images/image043_12.gif "width =" 125 "height =" 100 src = ">


Esimerkki kytkemättömästä kaaviosta:

Kierrä (yksinkertainen) on polku, jonka (yksinkertainen) pituus on vähintään 3 mistä tahansa kärjestä itseensä. Graafia kutsutaan syklinen , jos siinä on vähintään yksi kierto. Yhdistettyä asyklistä graafia, joka on "puu ilman juurta", kutsutaan ilmainen puu . Toisessa yllä olevassa kuvassa on kaavio, joka koostuu kahdesta yhdistetystä komponentista, joista jokainen on vapaa puu. Vapaasta puusta voidaan tehdä "säännöllinen" puu, jos jokin kärki on nimetty juureksi ja kaikki reunat on suunnattu tästä juuresta tulevaan suuntaan.

Irtonaisilla puilla on kaksi tärkeää ominaisuutta:

1. Jokainen vapaa puu, jossa on määrä pisteitä n, n > 1 , on täsmälleen n - 1 kylkiluut.

2. Jos lisäät uuden reunan ilmaiseen puuhun, saat varmasti syklin.

Anna olla G = (V, E) - yhdistetty graafi, jossa jokainen reuna ( r, w) merkitty numerolla kanssa(v, w), jota kutsutaan kylkiluiden hinta . Ylittävä puu Kreivi G kutsutaan vapaaksi puuksi, joka sisältää kaikki kärjet V kreivi G. Hinta virittävä puu lasketaan kaikkien tähän puuhun sisältyvien reunojen kustannusten summana

Perusalgoritmit ohjaamattomien graafien käsittelyyn:

1. Vähimmäiskustannukset kattavan puun rakentamisen (Primin algoritmi):

Monia huippuja rakennetaan U josta ylittävä puu "kasvaa". Anna olla V = (1, 2, ...,n}. Ensiksi U = (1). Algoritmin jokaisessa vaiheessa löydetään pienimmän kustannustason reuna ( u, v) sellasta u U ja v V \ U sitten päälle v siirretään sarjasta V \ U joukossa U... Tämä prosessi jatkuu sarjaan asti U ei ole yhtä suuri kuin joukko V.

Virittävä puun rakennusjärjestys on annettu alla.

https://pandia.ru/text/78/308/images/image048_12.gif "width =" 501 "height =" 384 src = ">

3. Suuntaamattomien kaavioiden DFS-läpikulku:

Syvyys-ensin hakua käytetään systemaattisesti läpikäymään graafin kaikki kärjet. Syvyys-ensimmäinen hakualgoritmi on samanlainen kuin digraafin kärkien kulkemisen algoritmi. Jälkimmäistä käytetään myös suuntaamattomille graafille, koska suuntaamaton reuna (v, w) voidaan esittää suuntautuneiden kaarien parina v -> w ja w -> v.

Syvyysläpikulkua voidaan käyttää virittävän puun rakentamiseen.

Kuvaaja ja virittävä puu, joka on saatu kulkemalla sen kärjet syvyys-ensimmäisen hakumenetelmällä, on esitetty alla:

4. Leveys ensin Haku ohjaamattomilla kaavioilla

Toista menetelmää graafin kärkien systemaattiselle läpikäymiselle kutsutaan Leveys ensimmäinen haku . Se sai nimensä, koska se saavutti minkä tahansa kärjen läpikäynnin aikana v Lisäksi tarkastelemme kaikkia kärjen vieressä olevia pisteitä v, eli kärjet skannataan "leveydeltä". Tätä tekniikkaa voidaan soveltaa myös suunnattuihin kaavioihin.

Kuten syvyyshaku, myös leveyshaku luo kattavan metsän, kun kaaviota kuljetetaan. Jos huipulle pääsemisen jälkeen NS kun katsot kylkiluuta (x, y) kärkipiste klo ei ole ennen käynyt, niin tätä reunaa pidetään puun reunana. Jos yläosa klo on jo käynyt, kylkiluu (x, y) on poikittaisreuna, koska se yhdistää toisiinsa pisteet, jotka eivät liity periytyvästi toisiinsa.

Leveys ensimmäinen ulottuva puu on esitetty alla.

Suuntaamattoman graafin esitys vierekkäisyysmatriisin avulla:

Suuntaamattomien graafien esittämiseen voidaan käyttää samoja menetelmiä kuin suunnattujen graafien esittämiseen, jos kärkien välinen suuntaamaton reuna v ja w katsottuna kahtena suuntautuneena kaarena kärjestä v to huippu w ja ylhäältä w huipulle v.

https://pandia.ru/text/78/308/images/image051_12.gif "width =" 159 "height =" 106 ">

Suuntaamattoman graafin esittäminen vierekkäisyysluetteloilla:

https://pandia.ru/text/78/308/images/image053_12.gif "width =" 339 "height =" 115 src = ">

1. Rakenna:

vähimmäiskustannusten ulottuva puu käyttäen Primin algoritmia;

vähimmäiskustannusten ulottuva puu käyttäen Kruskalin algoritmia;

virittävä puu syvyys-ensimmäisellä haulla, alkaen pisteistä a ja d;

ulottuva puu leveyshakulla alkaen pisteistä a ja d.

2. Toteuta Primin ja Kruskalin algoritmit.

3. Toteuta virittävän puun rakentaminen käyttämällä syvyyshakua

§ suuntaamattomalle graafille, jota edustaa vierekkäisyysmatriisi,

§ suuntaamattomalle graafille, jota edustavat vierekkäisyysluettelot.

4. Toteuta ylittävä puurakenne käyttämällä Breadth First -hakua

§ suuntaamattomalle graafille, jota edustaa vierekkäisyysmatriisi,

§ suuntaamattomalle graafille, jota edustavat vierekkäisyysluettelot.

Abstrakti tietotyyppi

Abstrakti tietotyyppi (ATD) on tietotyyppi, joka tarjoaa tietyn joukon toimintoja tämän tyyppisten elementtien kanssa työskentelemiseen sekä mahdollisuuden luoda tämän tyyppisiä elementtejä erikoistoimintojen avulla. Tämän tyyppinen koko sisäinen rakenne on piilotettu ohjelmistokehittäjältä - tämä on abstraktion ydin. Abstrakti tietotyyppi määrittelee joukon toteutuksesta riippumattomia toimintoja, jotka toimivat sen arvoilla. ADT:n erityisiä toteutuksia kutsutaan tietorakenteiksi.

Ohjelmoinnissa abstraktit tietotyypit esitetään yleensä rajapinnoina, jotka piilottavat vastaavat tyyppitoteutukset. Ohjelmoijat työskentelevät abstraktien tietotyyppien kanssa yksinomaan rajapintojensa kautta, koska toteutus saattaa muuttua tulevaisuudessa. Tämä lähestymistapa on yhdenmukainen olio-ohjelmoinnin kapseloinnin periaatteen kanssa. Tämän tekniikan vahvuus on toteutuksen piilottaminen. Kun vain rajapinta on julkaistu ulkopuolella, niin niin kauan kuin tietorakenne tukee tätä rajapintaa, kaikki kyseisellä abstraktin tietotyypin rakenteella toimivat ohjelmat jatkavat toimintaansa. Tietorakenteiden kehittäjät pyrkivät muuttamatta ulkoista käyttöliittymää ja funktioiden semantiikkaa, jalostamaan toteutuksia asteittain parantaen algoritmeja nopeuden, luotettavuuden ja käytetyn muistin suhteen.

Abstraktien tietotyyppien ja abstrakteja tyyppejä toteuttavien tietorakenteiden välinen ero voidaan havainnollistaa seuraavassa esimerkissä. Abstrakti tietotyyppilista voidaan toteuttaa taulukon tai lineaarisen listan avulla käyttämällä erilaisia ​​dynaamisia muistinvarausmenetelmiä. Jokainen toteutus määrittää kuitenkin samat ominaisuudet, joiden pitäisi toimia samalla tavalla (suorituskyvyn, ei nopeuden suhteen) kaikissa toteutuksissa.

Abstraktien tietotyyppien avulla voit saavuttaa ohjelmistotuotteiden modulaarisuuden ja niillä on useita eri moduulin vaihtoehtoisia keskenään vaihdettavia toteutuksia.

Esimerkkejä ADT:stä

Katso myös

Linkit

  • Lapshin V.A. Abstraktit tietotyypit ohjelmoinnissa

Wikimedia Foundation. 2010.

Katso, mitä "Abstract data type" on muissa sanakirjoissa:

    abstrakti tietotyyppi- Tietotyyppi (abstrakti luokka), joka määritellään luettelemalla sen menetelmät ja ominaisuudet luomatta niiden konkreettista toteutusta. Tietotekniikan aiheet yleisesti FI Abstract Data TypeADT ... Tekninen kääntäjän opas

    Ohjelmointiteoriassa mikä tahansa tyyppi, jonka arvot ovat jonkin muun tyyppisiä arvoja, jotka on "kääritty" algebrallisen tyypin rakentajien toimesta. Toisin sanoen algebrallisella tietotyypillä on joukko tyyppikonstruktoreja, joista jokainen ... ... Wikipedia

    Kokonaisluku, kokonaislukutietotyyppi (eng. Integer), tietojenkäsittelytieteessä, yksi ohjelmointikielten yksinkertaisimmista ja yleisimmistä tietotyypeistä. Edustaa kokonaislukuja. Monet tämän tyyppiset numerot edustavat ... ... Wikipediaa

    Tällä termillä on muita merkityksiä, katso joukko (merkityksiä). Joukko, tietojenkäsittelytieteen tyyppi ja tietorakenne, on matemaattisen objektijoukon toteutus. Tietotyyppijoukon avulla voit tallentaa rajoitetun määrän arvoja... ... Wikipedia

    Jotkut ohjelmointikielet tarjoavat erityisen tietotyypin kompleksiluvuille. Sisäänrakennettu tyyppi tekee monimutkaisten arvojen tallentamisesta ja laskemisesta helppoa. Sisältö 1 Aritmetiikka monimutkaisen yli 2 Tuki kielillä... Wikipedia

    Tällä termillä on muita merkityksiä, katso hakemisto. Osoitinkaavio Osoitin (osoitin) on muuttuja, jonka arvoalue koostuu muistiosoitteista ja nolla-osoitteen erikoisarvosta. ... ... Wikipedia

    Yksi algebrallisten tietotyyppien tyypeistä, jolle on ominaista se, että sen rakentajat voivat palauttaa arvoja, jotka eivät ole omaa tyyppiään. Tämä konsepti on toteutettu useilla ohjelmointikielillä, erityisesti ML- ja Haskell-kielillä, ja ... ... Wikipediassa

    Ominaisuus on abstrakti tyyppi, jota käytetään tietojenkäsittelytieteessä "yksinkertaisena käsitteellisenä mallina olioohjelmien jäsentämiseen". Ominaisuudet ovat samanlaisia ​​kuin mixins, mutta voivat sisältää luokkametodin määritelmiä ... ... Wikipedia

    Binääripuu, yksinkertainen esimerkki haarautuneesta yhdistetystä tietorakenteesta. Tietorakenne on ohjelmayksikkö, joka mahdollistaa... Wikipedia

    - (huipputyyppi) tyyppiteoriassa, usein merkitty vain yläpääksi tai "kiinteäksi" symboliksi (⊤), universaali tyyppi, eli tyyppi, joka sisältää kaikki mahdolliset objektit halutussa tyyppijärjestelmässä. Korkeinta tyyppiä kutsutaan joskus ... ... Wikipediaksi

1.2. Abstraktit tietotyypit

Suurin osa edellisessä osiossa esitellyistä käsitteistä esitellään yleensä ohjelmoinnin alkeiskurssilla ja niiden pitäisi olla sinulle tuttuja. Vain abstraktit tietotyypit voivat olla uusia, joten keskustellaan ensin niiden roolista ohjelman kehitysprosessissa. Ensinnäkin verrataan abstraktia tietotyyppiä niin tuttuihin käsitteisiin kuin proseduuri.

Proseduuria, kiinteää ohjelmointityökalua, voidaan pitää yleisenä operaattorin käsitteenä. Toisin kuin ohjelmointikielen sisäänrakennetut operaattorit (yhteen-, kertolasku jne.), joiden ominaisuudet ovat rajalliset, ohjelmoija voi käyttää menetelmiä luodakseen omia operaattoreita ja soveltaa niitä erityyppisiin, ei vain perusoperandeihin. Esimerkki tällaisesta operaattoriproseduurista on standardimatriisikertolutiini.

Toinen menettelyjen etu (uusien operaattoreiden luomisen lisäksi) on kyky käyttää niitä kapselointi algoritmin osia sijoittamalla erilliseen ohjelman osioon kaikki operaattorit, jotka ovat vastuussa tietystä ohjelman toiminnan osa-alueesta. Kapselointiesimerkki: yhden toimenpiteen käyttäminen minkä tahansa tyyppisten syöttötietojen lukemiseen ja sen oikeellisuuden tarkistamiseen. Kapseloinnin etuna on, että tiedämme, mitä kapseloituja lauseita tulee muuttaa, jos ohjelman toiminnassa ilmenee ongelmia. Jos esimerkiksi on tarpeen järjestää positiivisten arvojen syöttötietojen varmentaminen, vain muutama koodirivi tulee muuttaa, ja tiedämme tarkalleen missä nämä rivit sijaitsevat.

Abstraktin tietotyypin määritelmä

Me määrittelemme abstrakti tietotyyppi(ADT) matemaattisena mallina, jossa on joukko operaattoreita, jotka on määritelty tässä mallissa. Yksinkertainen esimerkki ADT:stä on joukko kokonaislukuja, joissa on joukkojen liiton, leikkauspisteen ja erotuksen operaattorit. ADT-mallissa operaattoreilla voi olla paitsi ADT:n määrittelemää dataa, myös muuntyyppisiä tietoja: ohjelmointikielen vakiotyyppejä tai muissa ADT:issä määriteltyjä tietoja. Myös operaattorin toiminnan tulos voi olla erityyppistä kuin tässä ADT-mallissa määritellyt. Mutta oletetaan, että ainakin yhdellä operandilla tai tuloksella on tarkasteltavassa ADT-mallissa määritetty tietotyyppi.

Proseduurien kaksi ominaista piirrettä - yleistäminen ja kapselointi - jotka on käsitelty edellä, ovat erinomaisia ​​abstrakteille tietotyypeille. ADT voidaan ajatella yleistyksenä yksinkertaisista tietotyypeistä (kokonaisluvut, reaaliluvut jne.), aivan kuten proseduuri on yleistys yksinkertaisista operaattoreista (+, - jne.). ADT kapseloi tietotyypit siinä mielessä, että tyypin määritelmä ja kaikki tämän tyyppisille tiedoille suoritetut lausunnot sijoitetaan yhteen ohjelman osaan. Jos ADT-toteutusta on tarpeen muuttaa, tiedämme mistä löytää ja mitä muutettavaa yhdestä pienestä ohjelman osiosta, ja voimme olla varmoja, että tämä ei johda virheisiin missään ohjelmassa tämän tietotyypin kanssa työskennellessään. Lisäksi ADT-operaattoreiden määrittelyä käsittelevän osan ulkopuolella voimme pitää ADT-tyyppejä ensisijaisina tyyppeinä, koska tyyppien ilmoittaminen ei liity muodollisesti niiden toteutukseen. Mutta tässä tapauksessa voi syntyä vaikeuksia, koska jotkut operaattorit voidaan käynnistää useammalle kuin yhdelle ADT:lle ja viittaukset näihin operaattoreihin on oltava useiden ADT:iden osissa.

Havainnollistaaksesi ADT:n luomisen taustalla olevia perusideoita, harkitse edellisen osan (Lista 1.3) ahnetta rutiinia, joka käyttää yksinkertaisia ​​operaattoreita abstraktille tietotyypille LIST (kokonaislukuluettelo). Näiden operaattoreiden on suoritettava seuraavat toiminnot LIST-tyypin muuttujalle newclr.

1. Tyhjennä luettelo.

2. Valitse listan ensimmäinen elementti ja jos lista on tyhjä, palauta arvo tyhjä.

3. Valitse luettelosta seuraava kohde ja palauta arvo tyhjä, jos seuraavaa kohdetta ei ole.

4. Lisää luetteloon kokonaisluku.

On mahdollista käyttää erilaisia ​​tietorakenteita, joilla voit suorittaa kuvatut toiminnot tehokkaasti. (Tietorakenteita käsitellään tarkemmin aiheessa 2.) Jos listassa 1.3 korvaat vastaavat operaattorit lausekkeilla

MAKENULL (uusiJr);

w: = ENSIMMÄINEN (uusiJr);

w: = SEURAAVA (newcfr);

INSERT (v, newclr);

silloin yksi abstraktien tietotyyppien tärkeimmistä näkökohdista (ja eduista) ymmärretään. Voit toteuttaa tietotyypin millä tahansa tavalla, eivätkä ohjelmat, jotka käyttävät tämän tyyppisiä objekteja, riipu siitä, kuinka tyyppi on toteutettu - menettelyt, jotka toteuttavat tämän tietotyypin operaattoreita, ovat vastuussa tästä.

Palataan abstraktiin tietotyyppiin GRAPH (Graph). Tämän tyyppiset objektit vaativat operaattoreita, jotka suorittavat seuraavat toiminnot.

1. Ensimmäinen maalaamaton kärki valitaan.

2. Tarkista, onko näiden kahden kärjen välillä reuna.

3. Merkitse kärki värillä.

4. Valitse seuraava maalaamaton kärki.

Ilmeisesti muut operaattorit jäävät poissa ahneesta menettelystä, kuten pisteiden ja reunojen lisääminen graafiin tai graafin kaikkien kärkien merkitseminen avoimina. Erilaisia ​​tietorakenteita, jotka tukevat tätä tietotyyppiä, käsitellään aiheissa 6 ja 7.

On syytä korostaa, että tämän matemaattisen mallin objekteihin sovellettavien operaattoreiden määrää ei ole rajoitettu. Jokainen operaattorijoukko määrittelee erillisen ADT:n. Tässä on esimerkkejä operaattoreista, jotka voit määrittää SET (Set) abstraktille tietotyypille.

1. MAKENULL (A), Tämä toimenpide tekee joukosta A tyhjän.

2. UNIONI (A, B, C). Tässä menettelyssä on kaksi "tulo"-argumenttia, joukot A ja B, ja se määrittää näiden joukkojen liiton "lähtö"-argumentille, joukkoon C.

3. KOKO (A). Tällä funktiolla on joukko-argumentti A ja se palauttaa kokonaislukutyyppisen objektin, joka on yhtä suuri kuin joukon A elementtien lukumäärä. Termi ADT-toteutus tarkoittaa seuraavaa: tämän abstraktin tietotyypin muuttujia määrittävien ilmoitusten kääntäminen ohjelmointikielen käskyiksi sekä proseduurit jokainen operaattori suoritetaan ADT-objekteille. Toteutus riippuu Tietorakenteet, edustaa ADT:tä. Jokainen tietorakenne on rakennettu käytetyn ohjelmointikielen perustietotyyppien pohjalta käyttämällä tällä kielellä saatavilla olevia tiedon strukturointityökaluja. Taulu- ja tietuerakenteet ovat kaksi tärkeää Pascalissa saatavilla olevaa tiedon strukturointityökalua. Esimerkiksi yksi SET-tyypin muuttujan S mahdollisista toteutuksista voi olla matriisi, joka sisältää joukon elementtejä. S.

Yksi tärkeimmistä syistä määritellä kaksi erilaista ADT:tä saman mallin sisällä on se, että näiden ADT:iden kohteille on suoritettava erilaisia ​​toimia, ts. määrittää erityyppisiä operaattoreita. Tässä tiivistelmässä tarkastellaan vain muutamia matemaattisia perusmalleja, kuten joukkoteoriaa ja graafiteoriaa, mutta erilaisille toteutuksille näiden tiettyjen ADT-mallien pohjalta rakennetaan erilaisia ​​operaattorijoukkoja.

Ihannetapauksessa on toivottavaa kirjoittaa ohjelmia kielellä, jonka perustietotyypit ja operaattorit riittävät ADT:n toteuttamiseen. Tästä näkökulmasta Pascal-kieli ei ole kovin sopiva kieli erilaisten ADT:iden toteuttamiseen, mutta toisaalta on vaikea löytää toista ohjelmointikieltä, jolla ADT:t olisi mahdollista deklaroida suoraan. Lisätietoja tällaisista ohjelmointikielistä on aiheen lopussa olevissa bibliografisissa huomautuksissa.

Abstraktiksi tyypiksi on tapana kutsua tietotyyppiä, jota ei ole erikseen saatavilla ohjelmointikielessä; tässä mielessä tämä käsite on suhteellinen - tietotyyppi, joka puuttuu toisesta ohjelmointikielestä, voi olla olemassa toisessa.

Abstrakti tietotyyppi (ADT) määritetään riippumatta siitä, miten se on toteutettu:

    tämän tyyppisten mahdollisten arvojen joukko,

    ja joukko operaatioita tämän tyyppisille arvoille.

ADT:n käyttö voidaan rajoittaa ohjelmistokehitysvaiheeseen, mutta sen eksplisiittistä käyttöä varten ohjelmassa tulee olla sen toteutus perustuen jo olemassa oleviin (ja aiemmin toteutettuihin) tietotyyppeihin ohjelmointikielessä:

    tapa esittää tämän tyyppisiä arvoja,

    ja operaatioiden toteuttaminen tämän tyyppisillä arvoilla.

Ohjelmointikielessä ei ole ennalta määritettyä ADT:tä, ja vielä enemmän tällaisten kielellä ennalta määritettyjen tyyppien rakentamistoiminnot siirtävät kysymyksen siitä, kuinka tämän tyyppisiä arvoja esitetään ja kuinka operaatioita toteutetaan tämän tyyppisillä arvoilla. ohjelmoija-kehittäjällä. Siksi tällaisille tietotyypeille kysymys lomakkeen toimintojen määritelmien ja toteutusmenetelmien valinnasta rakentaja tämän tyyppiset arvot ja tietovarastot, valitsin ja muuntaja Tämän tyyppiset komponentit (arvot ja tietovarastot) ovat kehittäjä-ohjelmoijan vastuulla.

ADT:n käsitteessä seuraavilla käsitteillä on erityinen asema: käyttöliittymä avoin käyttäjälle ja toteutumista häneltä piilossa. Näiden käsitteiden erityinen rooli ADT-käsityksessä liittyy perustavanlaatuiseen säännökseen, joka koskee ADT-käsitteen riippumattomuutta sen täytäntöönpanomenetelmästä.

Nykyaikaisissa "käytännöllisissä ohjelmointikielissä" ADT:iden rakentamiseen käytetään yleensä ennalta määrättyä tyyppiä olevaa rakennusoperaatiota luokkaa , joka antaa kehittäjälle-ohjelmoijalle keinon ryhmitellä dataa ja operaatioita (näillä tiedoilla) yhdeksi kokonaisuudeksi, mutta myös keinot kapseloimiseen, periytymiseen ja polymorfismiin hallita tapaa rakentaa ja käyttää tällaisia ​​tietoja. Huomaa, että luokka kuvaa yhtä mahdollista ADT:n toteutusta, luokan kartoitus ADT:hen ilmaistaan ​​abstraktiofunktiolla, mutta käänteinen suhde ei yleensä ole toiminnallinen, samalle ADT:lle voi olla useita toteutuksia.

Abstraktien tietotyyppien tutkimuksessa käsitteen tärkeä rooli " tyypin parametrointi ". Itse asiassa esimerkiksi "pino" ADT ei riipu pinoelementtien tyypistä, mutta tätä ADT:tä on mahdotonta toteuttaa osoittamalla "saman tyyppisiä elementtejä". Ada-ohjelmointikielessä vastaavat välineet parametroitujen tietotyyppien rakentamiseen sisältyivät aluksi ja nykyaikaisissa "käytännöllisissä ohjelmointikielissä", jotka työkalut ovat ilmestyneet vasta STL-kirjaston kehityksen jälkeen. Nykyään "yleisen ohjelmoinnin" käsitteellä on merkittävä asema käytännön ohjelmoinnissa, koska se sisällytetään "käytännöllisiin ohjelmointikieliin" välineet parametroitujen tietotyyppien (mallien, sapluuna , yleinen) .

Kaikki edellä mainittu tarkoittaa, että metodologisesta ja teoreettisesta näkökulmasta katsottuna tarvitaan "abstraktin tietotyypin" käsitteen yksityiskohtaisempi ja tarkempi määritelmä. Teoriassa "abstraktin tietotyypin" käsite määritellään yleensä seuraavasti monilajiteltu (monikantainen) algebrallinen järjestelmä , jossa mahdollisten arvojen (kantoaalto) ja tällaisille arvoille suoritettavien operaatioiden joukon lisäksi korostetaan seuraavat käsitteet:

    Lajittele ja allekirjoitus – näiden käsitteiden avulla voit luokitella sekä mediaelementit että niillä tehtävät toiminnot niiden tyyppien mukaan (operaatioiden argumenttien tyypin ja palautusarvon mukaan).

    Predikaatit ovat suhteita kantajan elementteihin. Tämä mahdollistaa mahdollisten arvojen alueen määrittämisen asettamalla rajoituksia (vaatimuksia) sallituille arvoille sekä luonnollisessa tulkinnassa työskennellä mielivaltaisten loogisten lausekkeiden kanssa pakottamatta niitä tulkitsemaan joukkojen tai joukon jäsenyysfunktioina. moniarvoisina operaatioina.

Tältä pohjalta on mahdollista tarkastella abstrakteja tietotyyppejä yhdestä integraalisesta loogis-algebrallisesta näkökulmasta, mukaan lukien kysymykset tämän tyyppisten objektien konstruktoreista (tyypeistä ja arvoista), valitsimista ja ominaisuuksien muokkaajista.

Käsitteet "tietorakenne" ja "abstrakti tietotyyppi" ovat jossain määrin samanlaisia. Voit tietysti ajatella, että nämä käsitteet ovat vain kaksi näkemystä samasta asiasta. ADT-arvojen esitystapa perustuu aina johonkin tietorakenteeseen, vähemmän tai monimutkaisempaan, ja operaatioiden toteutus tällaisilla arvoilla riippuu luonnollisesti tästä valitusta tietorakenteesta. Toisaalta, jos haluamme, voimme aina suunnitella tietorakenteen, joka kiinnostaa meitä ADT:nä.

Mutta silti teemme eron näiden kahden käsitteen välillä, kun otetaan huomioon:

    Abstrakti tietotyyppi tarkoittaa tietyn tason abstraktiota sovelletun (verkkoaluekohtaisen) tietotyypin kiinnittämiseksi riippumatta siitä, miten se on toteutettu, ja tämä tietotyyppi on mahdollista sisällyttää sovelluskirjastoon, no, ainakin tietyn ohjelmistojärjestelmän erityistä kehitystä varten. ADT:llä voi olla useita vaihtoehtoisia toteutuksia, jotka perustuvat erilaisiin tietorakenteisiin.

    Tietorakenne on pikemminkin jokin tiedon organisoinnin ja hallinnan kaavio, joka edellyttää asianmukaista konkretisointia, kun sitä käytetään tietyissä tilanteissa tiettyjen ongelmien ratkaisemisessa.

Ensinnäkin matemaattiset algebralliset perusjärjestelmät - sekvenssit, joukot, relaatiot ja mappaukset (funktionaaliset suhteet, funktiot) - kuuluvat luonnollisesti abstrakteihin tietotyyppeihin. Mutta ohjelmoinnissa etualalla ei ole näiden matemaattisten käsitteiden yleisten ominaisuuksien tutkiminen, vaan niiden käyttömahdollisuudet kehitettäessä malleja aihealueen ongelmien ratkaisemiseksi, algoritmeja näiden ongelmien ratkaisemiseksi ja kehitettyjen käsitteiden tehokas toteuttaminen. algoritmeja. Siksi ADT-muotoisessa ohjelmoinnissa näistä algebrallisista perusjärjestelmistä muodostetaan toisaalta rajoitettuja versioita, ja toisaalta niitä laajennetaan erikoistuneilla operaatiosarjoilla, jotka ovat pragmaattisen kannalta kiinnostavia. soveltamisalasta.

Samanlaisia ​​julkaisuja: