Vadnica za povezane sezname: – Uvod v dinamično shranjevanje podatkov

Razkritje: Vaša podpora pomaga pri vzdrževanju spletnega mesta! Za nekatere storitve, ki jih priporočamo na tej strani, zaslužimo naročnino.


Povezani seznami so lahko dragoceno orodje pri strukturiranju različnih nizov podatkov in organiziranju linearnih informacij za program. Običajno se uporabljajo kot nadomestilo za matriko, ker imajo določene prednosti pri njihovi uporabi.

V svojem jedru je povezan seznam preprosta podatkovna struktura, ki vsebuje zaporedje vozlišč. Vsako vozlišče ima svoje podatke in kazalec na drugo vozlišče. Pravzaprav jih pogosto poučujejo, da bi se študentom lahko počutili s kazalci.

Spodaj boste izvedeli, kaj so povezani seznami, zakaj so dragoceni in kako jih ustvariti. Ponudili bomo tudi nekaj dodatnih virov, s katerimi bomo lahko nadaljevali vaše izobraževanje.

Kaj so povezani seznami?

Preprosto povedano, povezan seznam je urejena zbirka podatkov. Namenjeno je linearnim strukturam podatkov in je ena najlažjih dinamičnih struktur podatkov. Vsak podatkovni element se imenuje vozlišče in vsebuje eno vrednost in kazalec na naslednje vozlišče na seznamu. Če ima kazalec vrednost NULL, je to vozlišče zadnje na seznamu.

Za lažje razumevanje koncepta je primer zunaj računalniške tehnologije:

Recimo, da ocenjujete vse osebe v pisarni glede na hitrost tipkanja. Vaš seznam bi se začel pri Ann, ker vsi vedo, da je najhitrejša – slišite lahko zvok iz njene kabine. Očitali so ji, da je naslednja najhitrejša oseba Steve. Steve ve, da je njegova hitrost tipkanja blizu Annovi, a ni ravno dobra. Prav tako ve, da je Karen skoraj tako hiter, kot je, vendar ne povsem. Seznam se lahko nato nadaljuje na ta način. Vsak član ima edinstvene podatke in indikator, kdo je naslednji najhitrejši tipkar.

Ker vozlišča obstajajo med seboj neodvisna, razen glede na odnos kazalcev, jih je zelo enostavno dodati, izbrisati in premakniti.

Vrste povezanih seznamov

Obstaja nekaj različnih vrst povezanih seznamov. En sam povezan seznam, dvojno povezan seznam, večpovezani seznam in krožni povezan seznam. Vsako podrobneje raziščemo v nadaljevanju. S povezanimi seznami lahko izvajate operacije vstavljanja, brisanja in prečkanja.

1. Enotni povezan seznam

Enotni povezani seznam je zbirka podatkovnih objektov, ki jih povezujejo določene reference od enega predmeta do drugega. Te predmete pogosto imenujemo vozlišča. Vsako vozlišče bo vsebovalo vsaj eno podatkovno polje in sklic na naslednje vozlišče. Do posameznih povezanih seznamov lahko dostopate prek prvega vozlišča in jih lahko premikate do konca seznama.

2. Dvostransko povezan seznam

Dvojno povezani seznami imajo po vsakem vozlišču dve referenci. Sklici kažejo na naslednje vozlišče in prejšnje vozlišče. S to strukturo imate dvosmerni dostop do nabora podatkov in vam nudi več prilagodljivosti in hitrosti, saj lahko po seznamu krmarite v obeh smereh.

3. Povečan seznam

Večpovezani seznami so splošno povezani seznami, ki imajo več dodatnih seznamov iz določenega vozlišča. Novi seznami so lahko v katerem koli od tukaj omenjenih slogov. Ta slog seznama je lahko koristen za razvrščanje seznama, ki je razčlenjen po uporabnikovem imenu in starosti. Ali druge sloge podatkovnih nizov, pri katerih ima vsaka podatkovna točka nadaljnje klasifikacije.

4. Krožni povezan seznam

Končna vrsta povezanega seznama se imenuje krožni povezan seznam. Namesto da bi končno vozlišče imelo ukaz NULL, se bo to vrnilo na glavo seznama. Struktura seznama je podobna zgornjim možnostim.

Zakaj so povezani seznami pomembni

Povezani seznami so uporabni zaradi svoje dinamične narave. V računalniškem smislu dodeljuje pomnilnik le, kadar je to potrebno. Če imate torej aplikacijo, ki zahteva pogosto spreminjanje velikosti, brisanje, vstavljanje in posodobitve podatkov, bo povezan seznam popoln.

Povezani seznami se običajno uporabljajo za izvajanje grafov, skladov, čakalnih vrst in drugih podobnih programov. S povezanim seznamom lahko elemente vstavite kamor koli na seznam. Poleg tega vam ni treba vnaprej vedeti velikosti končnega seznama. Velikost se lahko poveča ali zmanjša, če se vam zdi primerno.

Enostavno vstavljanje in brisanje je velika prednost povezanih seznamov. Na primer, lahko uporabite matriko, vendar matrike omogočajo samo dodajanje in odstranjevanje zadnjega predmeta v zaporedju, ne da bi premaknili kup podatkov, da ustvarite odprto režo. Povezani seznami omogočajo enostavno zaporedno manipulacijo z naborom podatkov, ne da bi obremenili spominske vire.

Večina programov Computer Science še naprej uči študente, kako izvajati povezane sezname, kar je trden uvod v dinamične strukture podatkov, ki jih morda želite uporabiti v resničnih programih. Poleg tega, tudi če nikoli ne boste uporabljali povezanega seznama, vam bo zagotovil dovolj razumevanja za uporabo kazalcev. Zagotovo boste uporabljali kazalce v številnih programih v resničnem življenju.

Pomanjkljivosti povezanih seznamov

Povezani seznami so odlični za ustvarjanje seznama, ki ga je enostavno spremeniti. Vendar niso odlična rešitev za vsak program, kot boste videli spodaj:

  1. Povezani seznami ne ponujajo naključne dostopne točke. Če želite doseči določeno postavko na svojem seznamu, morate do tega trenutka ponoviti vsak element na seznamu.
  2. Koda se lahko nekoliko zaplete, ker sta za delovanje kode potrebna tako dinamična dodelitev pomnilnika kot kazalci.
  3. Skupni režijski stroški povezanega seznama so lahko višji od niza, ker so seznami dinamično razporejeni.

Vse našteto vam bo pomagalo obvladati uporabo kazalcev in bolje razumeti dinamične naloge podatkov kot celoto.

Vadnica za povezane sezname

Spodaj boste izvedeli, kako ustvariti in izvajati osnovni povezan seznam. Začeli bomo z ustvarjanjem enega povezanega seznama in njegovih vozlišč ter prikazali, kako izbrisati in vstaviti nova vozlišča.

Ustvarjanje strukture vozlišča

Povezani seznam je sestavljen iz več vozlišč, zato bomo morali ustvariti strukturo, ki določa vozlišče. To bo moralo vključiti vsaj eno spremenljivko za podatke in en kazalec, da se bo nanašalo na naslednje vozlišče. V naš namen se bomo držali primera hitrosti tipkanja in uporabili ime in hitrost osebe ter naše podatke. V C bi bili podatki v strukturi opredeljeni tako:

strukturno vozlišče {
ime niza [32];
int hitrost;
vozlišče strukture * naslednji;
}

Pomembno pri tem je naslednji kazalec, ki nam omogoča, da delamo skozi seznam.

Ustvarjanje povezanega seznama

Zdaj bomo morali ustvariti seznam, ki dejansko ustvarja prvo vozlišče. Tako ga definiramo, dodelimo dovolj pomnilnika za eno vozlišče in naslednji kazalec nastavimo na NULL, tako da vemo, da je to konec seznama. Nanj nastavite tudi kazalec glave, ker se tu začne povezan seznam.

Nato lahko vnesete podatke za to vozlišče: ime zaposlenega in hitrost tipkanja.

Vstavljanje vozlišča

Z ustvarjenim osnovnim seznamom lahko zdaj začnemo dodajati elemente na seznam. Predpostavimo, da ste začeli s Karen, ki ima hitrost tipkanja 58 besed na minuto. Nato želite vnesti Steva s hitrostjo 63. Ustvarili bi vozlišče zanj in vnesli podatke. Potem bi iskali po povezanem seznamu, vendar bi bil v tem primeru samo en element. Opazili bi, da ima Steve večjo hitrost tipkanja, zato bi naslednji kazalec postavili na Karenin kazalec. Ker je Karenin kazalec tudi kazalnik glave, bi z glavo usmerili na Stevevo vozlišče.

Zdaj imate povezan seznam, ki se začne s Stevejevim vozliščem. Naslednje bi kazalo na Karenino vozlišče. Karenino vozlišče bi kazalo na NULL, kar bi pomenilo, da je njeno vozlišče zadnje na seznamu.

Če bi zaposleni zaposlili s hitrostjo tipkanja med Karen in Steveom, bi zanje nastalo vozlišče. Toda potem bo Steve naslednji pokazal na novega uslužbenca, novi zaposleni pa na Karen.

Po drugi strani pa bi, če bi zaposlenega zaposlili s tipkanjem, manjšim od hitrosti Karen, znova ustvarili vozlišče zanje. Potem pa bi naslednja Karen kazala na novega zaposlenega, naslednja pa na NULL.

Brisanje vozlišča

Brisanje vozlišča s povezanega seznama je pravzaprav dokaj enostaven postopek. Naslednji kazalec zaposlenega naredimo pred zaposlenim, ki ga želimo izbrisati, potem ko zaposlenega želimo izbrisati. Nato bi sprostili pomnilnik izbrisanega vozlišča ali pa bi na koncu prišlo do puščanja spomina.

Seveda lahko na povezanih seznamih naredite veliko več. Če vas še zanima raziskovanje povezanih seznamov, si oglejte spodaj poudarjene vire.

Viri s seznami

Ko razumete osnovni koncept povezanih seznamov, je čas, da razširite svoje znanje. Spodaj ponujamo nekaj dodatnih virov, s katerimi lahko resnično obvladamo povezane sezname in globlje razumevanje struktur podatkov:

  • Podatkovne strukture in algoritmi, ki jih je Narasimha Karumanchi naredila enostavno (2016): odlična knjiga o strukturah podatkov, ki vas bo popeljala daleč preko povezanih seznamov.
  • Osnove povezanih seznamov (PDF): ta 26-stranski dokument PDF vam bo zagotovil skoraj vse, kar bi kdaj želeli vedeti s primeri psevdo kod in jezikov C.
  • Nežen uvod v podatkovne strukture: ta preprost uvod vas bo popeljal do konca skozi ustvarjanje vašega prvega seznama povezanih programov.
  • Vadnice za povezane sezname: to je zbirka 7 kratkih videoposnetkov o ustvarjanju povezanih seznamov na C++.
  • Stran s povezanimi seznami Learn-C.org: ta stran vas vodi skozi ustvarjanje preprostega seznama, povezanega z jezikom C.
  • Strukture podatkov z Javascriptom: s tem vodnikom JavaScript se naučite povezanih seznamov neposredno v vašem brskalniku.

Povzetek

Povezani seznami ponujajo odličen koncept in praktičen način upravljanja in ustvarjanja dinamičnih podatkovnih nizov. Upajmo, da so vam zgornji podatki pomagali dojeti in uvesti osnovni povezan seznam in od tam se boste premaknili naprej.

Jeffrey Wilson Administrator
Sorry! The Author has not filled his profile.
follow me
    Like this post? Please share to your friends:
    Adblock
    detector
    map