Meni

Uvod v podatkovne strukture v jeziku C ++

  • Glavni
  • Drugo
  • Uvod v podatkovne strukture v jeziku C ++

introduction data structures c

Preizkusite Naš Instrument Za Odpravo Težav

Uvodna vadnica o podatkovnih strukturah v jeziku C ++.

»Strukturo podatkov lahko definiramo kot organizirano zbiranje podatkov, ki programu pomaga do učinkovitega in hitrega dostopa do podatkov, tako da lahko celoten program deluje učinkovito. “

Vemo, da so v programskem svetu podatki središče in vse se vrti okoli podatkov. Vse podatkovne operacije moramo opraviti učinkovito, vključno s shranjevanjem, iskanjem, razvrščanjem, organiziranjem in dostopom do podatkov, in šele potem lahko naš program uspe.

=> Za ogled celotnega seznama vadnic za C ++ glejte tukaj.

Uvod v podatkovne strukture v jeziku C ++ (1)

Kaj se boste naučili:

Pregled

Poiskati moramo najučinkovitejši način shranjevanja podatkov, ki nam lahko pomaga pri gradnji dinamičnih rešitev. Struktura podatkov nam pomaga pri oblikovanju takšnih rešitev.

Med organiziranjem ali razvrščanjem podatkov v strukture moramo zagotoviti, da ureditev predstavlja skoraj resnični objekt. Drugič, ta ureditev mora biti dovolj preprosta, da lahko vsakdo do nje zlahka dostopa in jo kadar koli obdela.

V tej seriji bomo podrobno spoznali tako osnovno kot tudi napredno strukturo podatkov. Podrobno bomo spoznali tudi različne tehnike iskanja in razvrščanja, ki jih je mogoče izvajati na podatkovnih strukturah.

Po učenju te vadnice se mora bralec dobro seznaniti z vsako podatkovno strukturo in njenim programiranjem.

Poglejmo si nekaj izrazov, ki jih uporabljamo pri obravnavi podatkovnih struktur:

Na primer,vzemite določenega študenta. Študent ima lahko naslednje podrobnosti, kot so predstavljene slikovno.

Primer - struktura podatkov

  • Podatki: To je osnovna vrednost. Na zgornji sliki so lahko podatki o številu študentov.
  • Postavka skupine: To je podatkovna postavka, ki ima več kot ene podpostavke. Na zgornji sliki ima Student_name ime in priimek.
  • Zapis: Je zbirka podatkovnih postavk. V zgornjem primeru podatkovni elementi, kot so številka študentskega seznama, ime, razred, starost, ocena itd., Skupaj tvorijo zapis.
  • Entiteta: To je razred zapisov. V zgornjem diagramu je študent entiteta.
  • Atribut ali polje: Lastnosti entitete se imenujejo atributi in vsako polje predstavlja atribut.
  • Mapa: Datoteka je zbirka zapisov. V zgornjem primeru ima lahko študentska entiteta na tisoče zapisov. Tako bo datoteka vse te zapise.

Bralec se mora zavedati vseh teh izrazov, saj jih vsake toliko uporabljamo pri uporabi različnih podatkovnih struktur.

Podatkovne strukture so glavni gradnik programa in kot programerji bi morali biti previdni pri izbiri podatkovne strukture. Natančna struktura podatkov, ki jo je treba uporabiti, je najtežja odločitev, kar zadeva programiranje.

Pogovorimo se o potrebi po strukturi podatkov pri programiranju.

Potreba po strukturi podatkov pri programiranju

Ko količina podatkov še naprej narašča, so aplikacije vedno bolj zapletene, zato programerju postane težko upravljati s temi podatki in programsko opremo.

Običajno se lahko aplikacija kadar koli sooča z naslednjimi ovirami:

# 1) Iskanje velikih količin podatkov: Zaradi velike količine podatkov, ki se obdelujejo in shranjujejo, bo morda kadar koli potreben naš program za iskanje določenih podatkov. Če so podatki preveliki in niso pravilno organizirani, bo trajalo veliko časa, da pridobite zahtevane podatke.

Ko za shranjevanje in organiziranje podatkov uporabljamo podatkovne strukture, je pridobivanje podatkov hitrejše in enostavnejše.

# 2) Hitrost obdelave: Neorganizirani podatki lahko povzročijo počasno hitrost obdelave, saj bo pri iskanju in dostopu do podatkov zapravljeno veliko časa.

Če podatke med shranjevanjem pravilno organiziramo v podatkovno strukturo, potem ne bomo izgubljali časa pri dejavnostih, kot je pridobivanje, in to vsakič organizirali. Namesto tega se lahko osredotočimo na obdelavo podatkov, da dobimo želene rezultate.

# 3) Več hkratnih zahtev: Številne aplikacije dandanes zahtevajo hkratno zahtevo za podatke. Te zahteve bi bilo treba učinkovito obdelati, da bi se aplikacije nemoteno izvajale.

Če so naši podatki shranjeni samo naključno, potem ne bomo mogli obdelati vseh sočasnih zahtev hkrati. Zato je pametna odločitev, da podatke razporedimo v pravilno podatkovno strukturo, tako da čas obratovanja sočasnih zahtev čim bolj zmanjšamo.

Klasifikacija podatkovne strukture

Podatkovne strukture, uporabljene v jeziku C ++, lahko razvrstimo na naslednji način.

Klasifikacija podatkovnih struktur

Podatkovna struktura je način organiziranja podatkov. Tako lahko razvrstimo podatkovne strukture, kot so prikazane, v primitivne ali standardne podatkovne strukture in neprimitivne ali uporabniško določene podatkovne strukture.

Videli smo vse vrste podatkov, ki jih podpira C ++. Ker je to tudi način organiziranja podatkov, pravimo, da gre za standardno strukturo podatkov.

Druge podatkovne strukture niso primitivne in jih mora uporabnik definirati, preden jih uporabi v programu. Te uporabniško določene podatkovne strukture so nadalje razvrščene v linearne in nelinearne podatkovne strukture.

Linearna struktura podatkov

Linearne podatkovne strukture imajo vse svoje elemente razporejene linearno ali zaporedno. Vsak element v linearni podatkovni strukturi ima predhodnika (prejšnji element) in naslednika (naslednji element)

Linearne podatkovne strukture se nadalje delijo na statične in dinamične podatkovne strukture. Statične podatkovne strukture imajo običajno fiksno velikost in ko je njihova velikost prijavljena v času prevajanja, je ni več mogoče spremeniti. Dinamične podatkovne strukture lahko dinamično spreminjajo svojo velikost in se prilagodijo sebi.

Najbolj priljubljen primer linearne statične strukture podatkov je matrika.

Matrika

Matrika je zaporedna zbirka elementov iste vrste. Do vsakega elementa matrike je mogoče dostopati s pomočjo njenega položaja v matriki, imenovanega indeks ali podpisnik matrike. Ime matrice kaže na prvi element v matriki.

matriko

Zgornje prikazano je polje 'a' od n elementov. Elementi so oštevilčeni od 0 do n-1. Velikost matrike (v tem primeru n) se imenuje tudi dimenzija matrike. Kot je prikazano na zgornji sliki, ime polja kaže na prvi element polja.

Matrika je najpreprostejša podatkovna struktura in je učinkovita, saj je do elementov mogoče dostopati neposredno z naročniki. Če želimo dostopati do tretjega elementa v matriki, moramo reči le (2).

Toda dodajanje ali brisanje elementov matrike je težko. Zato uporabljamo polja samo v preprostih aplikacijah ali v aplikacijah, kjer dodajanje / brisanje elementov ni potrebno.

Priljubljene linearne dinamične podatkovne strukture so povezani seznam, sklad in čakalna vrsta.

Povezani seznam

Povezani seznam je zbirka vozlišč. Vsako vozlišče vsebuje podatkovni element in kazalec na naslednje vozlišče. Vozlišča je mogoče dinamično dodajati in brisati. Povezani seznam je lahko posamezno povezan seznam, v katerem ima vsako vozlišče kazalec samo na naslednji element. Za zadnji element je naslednji kazalec nastavljen na nič.

Na dvojno povezanem seznamu ima vsako vozlišče dva kazalca, enega na prejšnje in drugo na naslednje vozlišče. Za prvo vozlišče je prejšnji kazalec ničen, za zadnje vozlišče pa naslednji.

Povezani seznam

Kot je prikazano na zgornji sliki, se začetek seznama imenuje glava, konec povezanega seznama pa rep. Kot je prikazano zgoraj, ima vsako vozlišče kazalec na naslednji element. S spreminjanjem kazalca na naslednje vozlišče lahko elemente enostavno dodamo ali izbrišemo.

Stack

Sklad je linearna podatkovna struktura, pri kateri je mogoče elemente dodajati ali odstranjevati samo z enega konca, imenovanega 'Vrh' sklada. Na ta način sklad razkrije vrsto dostopa do pomnilnika LIFO (zadnji vhod, prvi izhod).

Stack

Kot je prikazano zgoraj, se elementi v svežnju vedno dodajo na enem koncu in odstranijo tudi z istega konca. To se imenuje 'Vrh' sklada. Ko je element dodan, ga potisnemo navzdol, njegov vrh pa povečamo za en položaj.

Podobno se pri odstranjevanju elementa zmanjša zgornji del sklada. Ko je kup prazen, je vrh sklada nastavljen na -1. Na kupu se izvedeta dve glavni operaciji 'Push' in 'Pop'.

Čakalna vrsta

Čakalna vrsta je še ena linearna podatkovna struktura, pri kateri so elementi dodani na enem koncu, imenovanem 'zadaj', in izbrisani z drugega konca, imenovanem 'spredaj'. Čakalna vrsta prikazuje FIFO (First In, First Out) vrsto metodologije dostopa do pomnilnika.

Čakalna vrsta

Zgornji diagram prikazuje vrsto z zadnjim in sprednjim koncem. Ko je vrsta prazna, zadnja in sprednja kazalca sovpadata med seboj.

Nelinearna struktura podatkov

V nelinearnih podatkovnih strukturah podatki niso razporejeni zaporedno, temveč so razporejeni nelinearno. Elementi so med seboj povezani v nelinearni razporeditvi.

Nelinearne podatkovne strukture so Drevesa in Grafi.

primer sortiranja izbire c ++

Drevesa

Drevesa so nelinearne večnivojske podatkovne strukture, ki imajo hierarhično razmerje med elementi. Elementi drevesa se imenujejo vozlišča.

Vozlišče na vrhu se imenuje koren drevesa. Koren ima lahko eno ali več podrejenih vozlišč. Naslednja vozlišča imajo lahko tudi eno ali več podrejenih vozlišč. Vozlišča, ki nimajo podrejenih vozlišč, se imenujejo listna vozlišča.

Drevesa

V zgornjem diagramu smo prikazali drevo s 6 vozlišči. Od teh treh vozlišč so listna vozlišča, eno najvišje vozlišče je korensko, druga pa so podrejena vozlišča. Glede na število vozlišč, podrejenih vozlišč itd. Ali odnos med vozlišči imamo različne vrste dreves.

Grafi

Graf je niz vozlišč, ki se imenujejo oglišča med seboj povezani s pomočjo povezav Robovi . Grafi imajo lahko v sebi cikel, tj. Ista točka je lahko izhodišče in končna točka določene poti. Drevesa nikoli ne morejo imeti cikla.

Grafi

Zgornji diagram je neusmerjen graf. Lahko imamo tudi usmerjene grafe, kjer robove predstavljamo z usmerjenimi puščicami.

Operacije na strukturi podatkov

Vse podatkovne strukture izvajajo različne operacije nad njegovimi elementi.

Ti so skupni vsem podatkovnim strukturam in so navedeni na naslednji način:

  • Iskanje: Ta operacija se izvede za iskanje določenega elementa ali ključa. Najpogostejša algoritma iskanja sta zaporedno / linearno iskanje in binarno iskanje.
  • Razvrščanje: Postopek razvrščanja vključuje razvrščanje elementov v podatkovni strukturi v določenem vrstnem redu naraščajoče ali padajoče. Za podatkovne strukture so na voljo različni algoritmi za razvrščanje. Najbolj priljubljeni med njimi so Quicksort, Selection sort, Merge sort itd.
  • Vstavitev: Operacija vstavljanja se ukvarja z dodajanjem elementa v podatkovno strukturo. To je najpomembnejša operacija in zaradi dodajanja elementa se ureditev spremeni in poskrbeti moramo, da ostane podatkovna struktura nedotaknjena.
  • Izbris: Postopek brisanja odstrani element iz podatkovne strukture. Enaki pogoji, ki jih je treba upoštevati za vstavljanje, morajo biti izpolnjeni tudi v primeru postopka brisanja.
  • Prečkanje: Pravimo, da prehodimo podatkovno strukturo, ko obiščemo vsak element v strukturi. Prehod je potreben za izvedbo nekaterih posebnih operacij na podatkovni strukturi.

V naslednjih temah se bomo najprej naučili različnih tehnik iskanja in razvrščanja, ki jih je treba izvesti v podatkovnih strukturah.

Prednosti strukture podatkov

  • Abstrakcija: Podatkovne strukture se pogosto izvajajo kot abstraktni tipi podatkov. Uporabniki dostopajo samo do njegovega zunanjega vmesnika, ne da bi skrbeli za osnovno izvedbo. Tako struktura podatkov zagotavlja plast abstrakcije.
  • Učinkovitost: Pravilna organizacija podatkov ima za posledico učinkovit dostop do podatkov, s čimer so programi učinkovitejši. Drugič, glede na naše zahteve lahko izberemo pravilno strukturo podatkov.
  • Ponovna uporabnost: Podatkovne strukture, ki smo jih zasnovali, lahko ponovno uporabimo. Lahko jih zberemo tudi v knjižnico in jih distribuiramo stranki.

Zaključek

S tem zaključujemo to vadnico o uvodu v podatkovne strukture. V tej vadnici smo na kratko predstavili vsako podatkovno strukturo.

V naslednjih vajah bomo raziskali več o podatkovnih strukturah skupaj z različnimi tehnikami iskanja in razvrščanja.

=> Kliknite tukaj za absolutno serijo usposabljanj C ++.

Priporočeno branje

^