Kakšne so podatkovne strukture?

Struktura podatkov je programska enota, ki vam omogoča shranjevanje in obdelavo veliko istih ali logično povezanih informacij v računalniških napravah. Če želite dodati, najti, spremeniti ali izbrisati podatke, bo struktura zagotovila določen paket možnosti, ki je njegov vmesnik.

Kaj vključuje koncept podatkovne strukture?

Ta izraz ima lahko nekaj tesnih, a še vedno značilnih pomenov. To so:

• abstraktni tip;
• izvajanje abstraktne vrste informacij;
• Primer podatkovne vrste, na primer, določen seznam.

Če govorimo o strukturi podatkov v kontekstu funkcionalnega programiranja, potem je to posebna enota, ki se shrani, ko pride do sprememb. Neformalno je opisan kot enotna struktura, kljub temu, da obstajajo različne različice.

Kakšna je struktura?

Podatkovna struktura se oblikuje z uporabo vrst informacij, povezav in operacij na njih v določenem programskem jeziku. Treba je povedati, da so različne vrste struktur primerne za različne aplikacije, nekatere imajo na primer zelo ozko specializacijo in so primerne le za izdelavo uveljavljenih nalog.

Če vzamemo B-drevesa, potem so običajno primerni za oblikovanje podatkovnih baz in samo za njih. Hkrati se razpršilne tablice uporabljajo povsod v praksi za ustvarjanje različnih slovarjev, na primer za prikaz domenskih imen v internetnih naslovih računalnikov in ne samo za oblikovanje podatkovnih baz.

Pri razvoju določene programske opreme je kompleksnost izvajanja in kakovost funkcionalnosti programov neposredno odvisna od pravilne uporabe podatkovnih struktur. To razumevanje stvari je spodbudilo razvoj formalnih razvojnih tehnik in programskih jezikov, kjer so na vodilnih položajih v arhitekturi programa postavljene strukture in ne algoritmi.

Treba je opozoriti, da imajo številni programski jeziki vzpostavljeno vrsto modularnosti, ki omogoča varno uporabo podatkovnih struktur v različnih aplikacijah. Močni primeri so jeziki Java, C # in C + +. Zdaj je klasična struktura uporabljenih podatkov predstavljena v standardnih knjižnicah programskih jezikov ali pa je že vgrajena v sam jezik. Na primer, ta struktura razpredelnice hash je vgrajena v Lua, Python, Perl, Ruby, Tcl in druge. V knjižnici C ++ se pogosto uporablja standardna knjižnica predlog.

Primerjamo strukturo v funkcionalnem in nujnem programiranju

Treba je takoj določiti, da je težje oblikovati strukture za funkcionalne jezike kot za nujne jezike, vsaj za to obstajajo dva razloga:

1. Dejansko vse strukture v praksi pogosto uporabljajo nalogo, ki se ne uporablja v povsem funkcionalnem slogu.
2. Funkcionalne strukture so prilagodljivi sistemi. V nujnem programiranju starejše različice preprosto zamenjamo z novimi različicami, vendar v funkcionalnem programiranju deluje vse, kar je delovalo. Z drugimi besedami, v nujnih programskih strukturah so efemerne in funkcionalne so trajne.

Kaj vsebuje struktura?

Podatki, s katerimi programi delujejo, so pogosto shranjeni v nizih, vgrajenih v programskem jeziku, konstantne ali spremenljive dolžine. Niz je preprosta struktura z informacijami, vendar nekatere naloge zahtevajo večjo učinkovitost nekaterih operacij, zato se uporabljajo druge strukture (bolj zapletene).

Najenostavnejši matrika primeren za pogosto glede na sestavne dele nameščen na indekse in njihove spremembe in brisanje predmetov iz sredine poglavitnih nalog O (N) O (N). Če želite izbrisati elemente, da bi nekatere naloge, boste morali uporabiti drugačno strukturo. Na primer, binarno drevo (std :: set) vam omogoča, da to storite na O (logN) O (log⁡N), vendar pa ne deluje z indeksi se izvajajo izključno nadomestnih obvoza elemente in njihovo iskanje smisla. Tako lahko rečemo, da je struktura različnih operacij, ki jih je mogoče opravljati, kot tudi njihove stopnje kršenja. Na primer, da je vredno razmisliti enostavno strukturo, ki ne zagotavlja prednosti v učinkovitosti, ampak ima točno določen nabor podprtih operacij.

Stack

To je ena od vrst podatkovnih struktur, predstavljenih v obliki omejene osnovne elemente. Klasični kupček podpira le tri možnosti:

• Dodajanje elementa v sklad (Kompleksnost: O (1) O (1)).
• Izvleček elementa iz sklada (kompleksnost: O (1) O (1)).
• Preverite, ali je sklad prazen ali ne (Kompleksnost: O (1) O (1)).

Za pojasnitev načela svežnja lahko v praksi uporabite analogijo s pločevinko. Predstavljajte si, da na dnu plovila leži nekaj piškotov. Na zgornjem nadstropju lahko postavite še nekaj kosov ali pa, nasprotno, vzemite en piškotek z vrha. Preostali piškotki bodo zaprti na vrhu in ne boste vedeli ničesar o njih. To velja za sklad. Za opis koncepta se uporablja kratica LIFO (Last In, First Out), ki poudarja, da bo komponenta, ki je prišla v sklad, nazadnje prva in izvlečena iz nje.

V vrsti

To je druga vrsta podatkovne strukture, ki podpira isti niz možnosti kot sklad, vendar ima nasprotno semantiko. Za opis čakalne vrste se uporablja okrajšava FIFO (First In, First Out), ker je prvič dodan element najprej izvlečen. Ime zgradbe govori zase - načelo dela popolnoma sovpada z vrstami, ki jih lahko vidite v trgovini, v supermarketu.

Dec

To je druga vrsta podatkovne strukture, ki se imenuje tudi čakalna vrsta z dvema koncema. Možnost podpira naslednji niz operacij:

• Dodajte element na začetek (Kompleksnost: O (1) O (1)).
• Izvlecite komponento od začetka (Kompleksnost: O (1) O (1)).
• Dodajanje elementa do konca (zapletenost: O (1) O (1)).
• Izvleček elementa od konca (kompleksnost: O (1) O (1)).
• Preverite, ali so krovi prazni (Kompleksnost: O (1) O (1)).

Seznami

Ta podatkovna struktura definira zaporedje linearno povezanih komponent, za katere so dovoljene in izbrisane operacije dodajanja komponent na katero koli mesto na seznamu. Linearni seznam določa kazalec na začetek seznama. Tipični postopki na seznamih: pajkanje, iskanje določene komponente, vstavljanje elementa, brisanje komponente, združevanje dveh seznamov v eno celoto, razdelitev seznama v pare in tako naprej. Omeniti velja, da je v linearnem seznamu poleg prvega tudi predhodna komponenta za vsak element, ki ne vključuje zadnjega. To pomeni, da so komponente seznama v urejenem stanju. Da, obdelava takega seznama ni vedno priročna, ker ni možnosti premikanja v nasprotni smeri - od konca seznama do začetka. Vendar pa lahko v linearnem seznamu korak za korakom skozi vse komponente.

Obstajajo tudi obročni seznami. To je ista struktura kot linearni seznam, vendar ima dodatno povezavo med prvimi in zadnjimi komponentami. Z drugimi besedami, naslednja komponenta je prva komponenta.

Na tem seznamu so elementi enaki. Dodelitev prvega in zadnjega je pogojenost.

Drevesa

Ta kombinacija sestavin, ki so navedene kot vozlišča, ki je glavni (a) komponento v obliki koren in vsa ostala razdeljena v množico Disjunktan elementov. Vsak set je drevo, in koren vsakega drevesa - potomec korena. Z drugimi besedami, vse komponente so povezane z odnosom med predniki in otroki. Posledično lahko opazujete hierarhično strukturo vozlišč. Če vozlišča nimajo potomca, potem se imenujejo listi. Nad drevesa so opredeljene dejavnosti, kot so dodajanje komponente in njeno odstranjevanje, mimo komponento iskanja. Posebno vlogo v računalništvu igrajo binarna drevesa. Kaj je to? To je poseben primer drevesa, kjer ima lahko vsako vozlišče ne več kot nekaj potomcev, ki so korenine levo in desno poddrevo. Če poleg drevesa vozlišč se izvaja še pogoj, da je vse vrednosti komponent na levem poddrevesu manjši od temeljnih vrednot in vrednosti sestavin desno poddrevo večje korenine, je drevo imenuje binarno iskalno drevo, in je zasnovan tako, da hitro najti elemente. Kako deluje iskalni algoritem v tem primeru? Želena vrednost je v primerjavi s korenske vrednosti in glede na rezultat iskanja ali konča ali pa se nadaljuje, vendar le v levo ali desno poddrevo. Skupno število primerjav ne bo presegla višine drevesa (največje število komponent na poti od korena do listov).

Grafi

Grafi so zbirka komponent, ki se imenujejo tocke, skupaj s skupino povezav med temi tockami, ki se imenujejo robovi. Grafična interpretacija te strukture je predstavljena v obliki niza točk, ki ustrezajo tockam, nekateri pa so povezani z vrsticami ali puščicami, ki ustrezajo robovi. Slednji primer nakazuje, da je graf treba usmeriti.

Grafi lahko opisujejo objekte katere koli strukture, so glavno sredstvo za opisovanje kompleksnih struktur in delovanje vseh sistemov.

Več informacij o abstraktni strukturi

Če želite zgraditi algoritem, morate formalizirati podatke ali, z drugimi besedami, morate podatke prenesti v določen informacijski model, ki je že bil raziskan in napisan. Ko najdemo model, je mogoče trditi, da je vzpostavljena abstraktna struktura.

To je glavna podatkovna struktura, ki prikazuje atribute, kakovost predmeta, razmerje med sestavnimi deli predmeta in operacijo, ki jih je mogoče opraviti nad njim. Glavna naloga je najti in prikazati obrazce za predstavitev informacij, ki so primerne za popravljanje računalnika. Omeniti je treba, da računalništvo kot točna znanost deluje s formalnimi predmeti.

Analizo podatkovnih struktur opravljajo naslednji predmeti:

• Celice in realne številke.
• Boolove vrednosti.
• Simboli.

Za obdelavo vseh elementov na računalniku obstajajo ustrezni algoritmi in podatkovne strukture. Tipične predmete lahko združimo v kompleksne strukture. Na njih lahko dodate operacije in pravila za določene komponente te strukture.

Struktura podatkovne organizacije vključuje:

• Vektorji.
• Dinamične strukture.
• Tabele.
• Večdimenzionalni nizi.
• Grofje.

Če bodo vsi elementi uspešno izbrani, bo to ključ do oblikovanja učinkovitih algoritmov in podatkovnih struktur. Če v praksi uporabite analogijo struktur in realnih predmetov, lahko učinkovito rešite obstoječe težave.

Treba je omeniti, da vse strukture organizacije podatkov ločeno obstajajo v programiranju. Nad njimi je veliko dela v osemnajstem in devetnajstem stoletju, ko na računalniku še ni bilo računalnika.

Mogoče je razviti algoritem v smislu abstraktne strukture, za izvedbo algoritma v določenem programskem jeziku pa bo treba najti metodologijo za njeno zastopanost v tipih podatkov, operaterjih, ki jih podpira poseben programski jezik. Za ustvarjanje struktur, kot so vektor, imenska tablica, niz, zaporedje, v številnih programskih jezikih obstajajo klasične vrste podatkov: enodimenzionalna ali dvodimenzionalna matrika, niz, datoteka.

Kakšna so metodološka priporočila za delo s strukturami?

Obravnavali smo značilnosti podatkovnih struktur, zdaj pa bi morali posvetiti več pozornosti razumevanju koncepta strukture. Pri reševanju absolutno vsakršne težave je potrebno delati z nekaterimi podatki za opravljanje operacij na informacijah. Vsaka naloga ima svoj nabor operacij, vendar se v praksi pogosteje uporablja določen niz za reševanje različnih nalog. V tem primeru je koristno pripraviti določen način organizacije informacij, kar bo omogočilo čim bolj učinkovito izvajanje teh postopkov. Ko se pojavi taka metoda, lahko domnevate, da imate "črno okno", v katerem bodo shranjeni podatki določene vrste in ki bodo izvajali nekatere podatkovne operacije. To bo odvrnilo od podrobnosti in se v celoti osredotočilo na značilne lastnosti problema. Ta "črna škatla" se lahko izvaja na kakršen koli način, čeprav je treba si prizadevati za čim večjo produktivno izvajanje.

Kdo mora to vedeti?

Poznani programerji, ki želijo najti svoje mesto na tem področju, so seznanjeni z informacijami, vendar ne vedo, kam iti. To so osnove v vsakem programskem jeziku, zato ne bo odvečno, če se takoj naučimo o podatkovnih strukturah in po delu z njimi na določenih primerih in s posebnim jezikom. Ne smemo pozabiti, da lahko vsako strukturo karakteriziramo z logičnimi in fizičnimi predstavitvami, pa tudi z nizom postopkov na teh predstavitvah.

Ne pozabite: če govorite o določeni strukturi, potem ne pozabite njene logične predstavitve, ker je fizično predstavljanje povsem skrito od "zunanjega opazovalca".

Poleg tega upoštevajte, da je logična predstavitev povsem neodvisna od programskega jezika in računalnika, fizično predstavljanje pa je nasprotno odvisno od prevajalcev in računalnikov. Na primer, dvodimenzionalna matrika v Fortran in Pascal je lahko enako zastopana, fizična predstavitev v istem računalniku v teh jezikih pa bo drugačna.

Ne pohitite, da začnete poučevati določene strukture, najbolje je razumeti njihovo klasifikacijo, se seznaniti z vsemi v teoriji in po možnosti v praksi. Treba je spomniti, da je spremenljivost pomembna značilnost strukture in kaže statično, dinamično ali pol-statično situacijo. Spoznajte osnove, preden zaženete več globalnih stvari, kar vam bo pomagalo pri prihodnjem razvoju.