Abstract data structures
tietojenkäsittelytieteessä Abstrakti tietotyyppi (ADT) on matemaattinen malli tietotyypeille, joissa tietotyyppi määritellään sen käyttäytymisen (semantiikan) perusteella datan käyttäjän näkökulmasta, erityisesti mahdollisten arvojen, tämän tyyppisten tietojen mahdollisten operaatioiden ja näiden operaatioiden käyttäytymisen kannalta. Tämä on ristiriidassa tietorakenteiden kanssa, jotka ovat konkreettisia tiedon esityksiä ja ovat toteuttajan, Ei käyttäjän näkökulmasta.
muodollisesti ADT voidaan määritellä ”niiden olioiden luokaksi, joiden looginen käyttäytyminen määritellään arvojen ja operaatioiden joukon avulla”; tämä on matematiikassa analogista algebrallisen rakenteen kanssa. Se, mitä tarkoitetaan ”käyttäytymisellä”, vaihtelee kirjoittajittain, ja käyttäytymisen muodollisten määrittelyjen kaksi päätyyppiä ovat Aksiomaattinen (algebrallinen) määrittely ja abstrakti malli; nämä vastaavat abstraktin koneen aksiomaattista semantiikkaa ja operatiivista semantiikkaa. Jotkut kirjoittajat sisältävät myös laskennallisen monimutkaisuuden (”kustannukset”) sekä ajan (laskutoimitusten) että avaruuden (arvojen edustamisen) suhteen.
abstrakteja rakenteita käytetään siksi, että ne käyttävät tehokkaasti niihin tallennetun datan rakenteeseen perustuvaa muistia. Erittäin suuria tietomääriä tai hyvin usein muuttuvat TIEDOT, tietorakenne voi tehdä valtava ero tehokkuutta (ajonaika) tietokoneohjelmasi.
yleisemmässä kielenkäytössä Abstrakti tietorakenne on vain jokin datan järjestely, jonka olemme rakentaneet järjestykseen.
täydellisen ihana yleiskuva
eräät abstraktien tietorakenteiden tyypit
IB: n arvioima
- staattinen ja dynaaminen tietorakenne
puu puu
ekursio
ei ole IB: n arvioima, mutta ne pitäisi tuntea
luettelee
tietorakenteiden perustoiminnot
löysin tämän erinomaisen dian Simon allardicelta.
eri tietorakenteiden Vertailu
| tietorakenne | vahvuudet | heikkoudet | lajittelu ja haku, lisääminen ja poistaminen – varsinkin jos lisäät ja poistat taulukon alussa tai lopussa |
| linkitetty lista | suora indeksointi, helppo luoda ja käyttää | suora pääsy, haku ja lajittelu |
| pinon ja jonon | suunniteltu LIFO / FIFO | suora pääsy, haku ja lajittelu |
| binääripuu | lisäys-ja poistonopeus, käytön nopeus, lajiteltun järjestyksen ylläpitäminen | jotkut yläpuoliset |
- kiinteät rakenteet ovat nopeampia / pienempiä
- kun pohditaan, kannattaako käyttää abstraktia tietorakennetta, kannattaa kysyä itseltään: mikä pitää hallussaan eniten dataa ja mikä eniten muuttunutta dataa?
staattisten vs dynaamisten tietorakenteiden Vertailu
tätä vertailua käytetään tietojenkäsittelytieteen oppikirjastamme.
| Staattinen tietorakenne | dynaaminen tietorakenne |
| tehoton, koska muistiin on varattu sellaista, jota ei välttämättä tarvita. | tehokas, koska muistin määrä vaihtelee tarpeen mukaan. |
| Nopea pääsy jokaiseen tietoelementtiin, sillä muistipaikka on kiinteä ohjelmaa kirjoitettaessa. | hitaampi pääsy kuhunkin elementtiin, koska muistin sijainti jaetaan suoritusaikana. |
| varatut Muistiosoitteet ovat vierekkäisiä, joten niiden käyttö on nopeampaa. | annetut Muistiosoitteet voivat olla pirstaloituneita, joten niiden käyttö on hitaampaa. |
| rakenteet ovat kiinteän kokoisia, mikä tekee niiden kanssa työskentelystä ennakoitavampaa. Ne voivat sisältää esimerkiksi otsikon. | rakenteiden koko vaihtelee, joten tarvitaan mekanismi, jolla tiedetään nykyisen rakenteen koko. |
| tietojen eri osien välinen suhde ei muutu. | tiedon eri osien välinen suhde muuttuu ohjelmaa suoritettaessa. |
valitsemalla mitä tietorakennetta käyttää
tätä graafia käytetään valtavalla kiitoksella Dartford Grammar Schoolin tietojenkäsittelytieteen osastolta.
standardit
- tunnistavat tilanteen, joka vaatii rekursiivisen ajattelun käyttöä.
- tunnista rekursiivinen ajattelu tietyssä ongelmaratkaisussa.
- Jäljitä rekursiivinen algoritmi, jolla ilmaistaan ratkaisu ongelmaan.
- kuvaa kaksiulotteisen joukon ominaisuuksia.
- rakentaa algoritmeja käyttäen kaksiulotteisia taulukoita.
- kuvaa pinon ominaisuuksia ja sovelluksia.
- rakentaa algoritmeja käyttäen pinon pääsymenetelmiä.
- kuvaa jonon ominaisuuksia ja sovelluksia.
- muodosta algoritmeja jonon pääsymenetelmiä käyttäen.
- selittää matriisien käytön staattisina pinoina ja jonoina.
- kuvaa dynaamisen tietorakenteen ominaisuuksia ja ominaisuuksia.
- kuvaa, miten linkitetyt listat toimivat loogisesti.
- Sketsiyhteiset listat (single -, tupla-ja ympyrälistat).
- kuvaile kokoelman ominaisuuksia ja sovelluksia.
- rakentaa algoritmeja käyttäen kokoelman pääsymenetelmiä.
- keskustelee aliohjelmien ja kokoelmien tarpeesta ohjelmoitujen ratkaisujen sisällä.
- rakentaa algoritmeja käyttäen ennalta määriteltyjä aliohjelmia, yksiulotteisia taulukoita ja / tai kokoelmia.
- kuvaa, miten puut toimivat loogisesti (sekä binääriset että ei-binääriset).
- Määrittele termit: vanhempi, vasen-lapsi, oikea-lapsi, subtre, juuri ja lehti.
- ilmoita inerder -, postorder-ja preerder tree traversialin tulos.
- Sketch binary trees.
- Määrittele termi dynaaminen tietorakenne.
- vertaa staattisten ja dynaamisten tietorakenteiden käyttöä.
- ehdottaa sopivaa rakennetta tiettyyn tilanteeseen.
Leave a Reply