Susietų sąrašų vadovėlis: – Kaip pradėti naudotis dinamine duomenų saugykla

Atskleidimas: Jūsų palaikymas padeda išlaikyti svetainę! Mes uždirbame siuntimo mokestį už kai kurias paslaugas, kurias rekomenduojame šiame puslapyje.


Susieti sąrašai gali būti vertinga priemonė, kai reikia struktūruoti įvairius duomenų rinkinius ir organizuoti linijinę programos informaciją. Paprastai jie naudojami kaip masyvo pakaitalas, nes jie turi tam tikrų privalumų.

Savo esme susietas sąrašas yra paprasta duomenų struktūra, turinti mazgų seką. Kiekvienas mazgas turi savo duomenis, be to, rodyklę į kitą mazgą. Tiesą sakant, jie dažnai mokomi, kad studentams būtų patogu naudotis rodyklėmis.

Žemiau sužinosite, kokie yra susieti sąrašai, kodėl jie yra vertingi ir kaip juos sudaryti. Taip pat pasiūlysime kelis papildomus išteklius, kurie padės toliau mokytis.

Kas yra susiję sąrašai?

Paprasčiau tariant, susietas sąrašas yra užsakytas duomenų rinkinys. Jis skirtas linijinėms duomenų struktūroms ir yra viena lengviausiai įgyvendinamų dinaminių duomenų struktūrų. Kiekvienas duomenų elementas vadinamas mazgu ir turi vieną reikšmę ir žymiklį kitam sąrašo mazgui. Jei rodyklė turi NULL reikšmę, tada tas mazgas yra paskutinis sąraše.

Čia pateiktas ne kompiuterinės technologijos pavyzdys, kuris padėtų suvokti šią sąvoką:

Tarkime, kad vertinate kiekvieną biuro žmogų pagal spausdinimo greitį. Jūsų sąrašas prasidėtų nuo Annos, nes visi žino, kad ji greičiausia – galite išgirsti garsą, sklindantį iš jos kabinos. Jai buvo pasakyta, kad kitas greičiausias žmogus yra Steve’as. Steve’as žino, kad jo spausdinimo greitis yra panašus į Annos, tačiau ne toks geras. Jis taip pat žino, kad Karen beveik taip greitai, kaip jis, bet ne visai. Tada sąrašas gali tęstis tokiu būdu. Kiekvienas narys turi unikalią informaciją ir indikatorių, kuris yra kitas greičiausias mašinininkas.

Kadangi mazgai egzistuoja nepriklausomai vienas nuo kito, išskyrus rodyklės ryšį, juos labai lengva pridėti, ištrinti ir perkelti.

Susietų sąrašų tipai

Yra keli skirtingi susietų sąrašų tipai. Vienas susietas sąrašas, dvigubai susietas sąrašas, daugkartinis sąrašas ir apskritas susietų sąrašas. Žemiau panagrinėsime kiekvieną iš jų. Naudodami susietus sąrašus galite atlikti įterpimo, naikinimo ir perėjimo operacijas.

1. Vieno susieto sąrašo sąrašas

Vienas susietas sąrašas yra duomenų objektų, kurie yra susieti tam tikromis nuorodomis iš vieno objekto į kitą, rinkinys. Šie objektai dažnai vadinami mazgais. Kiekviename mazge bus bent vienas duomenų laukas ir nuoroda į kitą mazgą. Pavieniai susieti sąrašai pasiekiami per pirmąjį mazgą ir jais galima pereiti iki sąrašo pabaigos.

2. Dvigubai susijęs sąrašas

Dvigubai susieti sąrašai turi dvi nuorodas kiekviename mazge. Nuorodos nurodo kito mazgo ir ankstesnio mazgo link. Naudodamiesi šia struktūra, turite abipusę prieigą prie duomenų rinkinio. Tai suteikia daugiau lankstumo ir greičio, nes galite naršyti sąraše abiem kryptimis..

3. Susietas sąrašas

Susieti sąrašai yra bendrieji susieti sąrašai, turintys kelis papildomus sąrašus iš tam tikro mazgo. Nauji sąrašai gali būti bet kurio iš čia paminėtų stilių. Šis sąrašo stilius gali būti naudingas rūšiuojant sąrašą, suskirstytą pagal vartotojo vardą ir amžių. Arba kiti duomenų rinkinių stiliai, kai kiekvienas duomenų taškas turi papildomą klasifikaciją.

4. Susietas sąrašas

Galutinis susieto sąrašo tipas vadinamas apvaliu susietų sąrašą. Vietoj to, kad galutinis mazgas turėtų NULL komandą, jis nurodo nuorodą į sąrašo galvą. Sąrašo struktūra panaši į aukščiau pateiktas parinktis.

Kodėl svarbūs susieti sąrašai?

Susieti sąrašai yra naudingi dėl jų dinaminio pobūdžio. Skaičiavimo prasme, ji skiria atmintį tik tada, kai to reikia. Taigi, jei turite programą, kuriai reikia dažnai keisti dydį, ištrinti, įterpti ir atnaujinti duomenis, susietas sąrašas bus tobulas.

Susieti sąrašai dažniausiai naudojami grafikams, krūvoms, eilėms ir kitoms panašioms programoms įgyvendinti. Turėdami susietą sąrašą, galite įterpti elementus bet kurioje sąrašo vietoje. Be to, jums nereikia iš anksto žinoti galutinio sąrašo dydžio. Tai gali padidinti ar sumažinti dydį, kaip jums atrodo tinkama.

Lengvas įdėjimas ir ištrynimas yra pagrindinis susietų sąrašų pranašumas. Pvz., Galėtumėte naudoti masyvą, tačiau masyvai leidžia tik pridėti ir pašalinti paskutinį sekos objektą, nejudindami krūvos duomenų, kad sukurtumėte atvirą plyšį. Susieti sąrašai leidžia lengvai valdyti nuoseklų duomenų rinkinį, nesukeldami didžiulės apkrovos atminties ištekliams.

Daugelis kompiuterių mokslo programų ir toliau moko studentus, kaip įgyvendinti susietus sąrašus, kaip tvirtą įvadą į dinamiškas duomenų struktūras, kurias galbūt norėsite naudoti realiose programose. Be to, net jei niekada nenaudosite susieto sąrašo, jis suteiks pakankamai supratimo, kad galėtumėte naudoti rodykles. Jūs tikrai naudosite rodykles daugelyje savo realaus gyvenimo programų.

Susieto sąrašo trūkumai

Susieti sąrašai yra puikūs norint sukurti lengvai modifikuojamą sąrašą. Tačiau jie nėra tobulas sprendimas kiekvienai programai, kaip pamatysite toliau:

  1. Susieti sąrašai nesiūlo atsitiktinės prieigos taško. Norėdami pasiekti tam tikrą sąrašą savo sąraše, turite pakartoti kiekvieną sąrašą iki to momento.
  2. Kodas gali būti šiek tiek sudėtingas, nes norint, kad kodas veiktų, reikalingas tiek dinaminis atminties paskirstymas, tiek rodyklės.
  3. Bendra susieto sąrašo pridėtinė vertė gali būti didesnė už masyvą, nes sąrašai paskirstomi dinamiškai.

Visa tai sakydami, žinodami, kaip naudoti susietus sąrašus, galėsite įsisavinti rodyklių naudojimą ir geriau suprasti dinaminius duomenų rinkinius kaip visumą..

Susietų sąrašų vadovėlis

Žemiau sužinosite, kaip sukurti ir įgyvendinti pagrindinį susietų sąrašą. Pradėsime nuo vieno susieto sąrašo ir jo mazgų sudarymo bei parodysime, kaip ištrinti ir įterpti naujus mazgus.

Mazgo struktūros sukūrimas

Susietą sąrašą sudaro keli mazgai, todėl turėsime sukurti struktūrą, apibrėžiančią mazgą. Tai turės apimti bent vieną duomenų kintamąjį ir vieną rodyklę, nukreipiančią į kitą mazgą. Siekdami tikslo, mes laikysimės savo spausdinimo greičio pavyzdžio ir naudosime asmens vardą, pavardę, greitį ir mūsų duomenis. C dalyje duomenys struktūroje būtų apibūdinami taip:

struktūros mazgas {
stygos pavadinimas [32];
int greitis;
struktūros mazgas * šalia;
}

Svarbus dalykas yra kitas rodyklė, kuri mums leidžia dirbti pagal sąrašą.

Susieto sąrašo sudarymas

Dabar turėsime sukurti sąrašą, kuris iš tikrųjų tik sukuria pirmąjį mazgą. Taigi mes jį apibrėžiame, paskirstome pakankamai atminties vienam mazgui ir nustatome kitą rodyklę ties NULL, kad žinotume, jog tai sąrašo pabaiga. Jūs taip pat nustatote rodyklę į galvą, nes čia prasideda susietų sąrašas.

Tada galite užpildyti šio mazgo informaciją: darbuotojo vardą ir pavardę bei jų spausdinimo greitį.

Mazgo įterpimas

Sukūrę pagrindinį sąrašą, dabar galime pradėti įtraukti elementus į sąrašą. Taigi tarkime, kad pradėjote nuo Karen, kurio spausdinimo greitis yra 58 žodžiai per minutę. Toliau norite įvesti Steve’ą 63 greičiu. Jūs sukursite jam mazgą ir užpildysite duomenis. Tada jūs ieškotumėte susieto sąrašo, tačiau tokiu atveju būtų tik vienas elementas. Atkreipkite dėmesį, kad Steve’as spausdina greičiau, todėl kitą jo rodyklę nustatytumėte į Kareno rodyklę. Kadangi Kareno rodyklė taip pat yra galvos rodyklė, jūs turėtumėte nukreipti galvą į Steve’o mazgą.

Dabar turite susietą sąrašą, prasidedantį Steve’o mazgu. Kitas ženklas bus Kareno mazgas. O Karen mazgas rodytų į NULL, nurodydamas, kad jos mazgas yra paskutinis sąraše.

Jei darbuotojas būtų pasamdytas spausdinimo sparta tarp Karen ir Steve, jiems būtų sukurtas mazgas. Bet tada kitas Steve’as rodytų į naują darbuotoją, o naujasis kitas nurodytų į Karen’s.

Kita vertus, jei darbuotojas būtų pasamdytas mažesne nei Karen rašymo sparta, jiems vėl būtų sukurtas mazgas. Bet tada kitas Karenas nurodytų naują darbuotoją, o kitas naujasis nurodytų NULL.

Naikinimo mazgas

Ištrinti mazgą iš susieto sąrašo iš tikrųjų yra gana lengvas procesas. Kitą darbuotojo rodyklę padarytume prieš darbuotoją, kurį norime ištrinti, nukreipdami į darbuotoją, po darbuotojo, kurį norime ištrinti. Tada paleisime ištrinto mazgo atmintį arba nutekės atmintis.

Žinoma, su nuorodų sąrašais galite nuveikti dar daug. Jei jus domina dar daugiau panagrinėti susietus sąrašus, tada patikrinkite žemiau paryškintus išteklius.

Susieto sąrašo šaltiniai

Kai suprantate pagrindinę susietų sąrašų sąvoką, laikas tobulinti savo žinias. Žemiau mes siūlome keletą papildomų šaltinių, kurie padės iš tikrųjų įvaldyti susietus sąrašus ir giliau suprasti duomenų struktūras:

  • Narasimha Karumanchi parengtos duomenų struktūros ir algoritmai (2016): puiki knyga apie duomenų struktūras, kuri nuves jus toli nuo susietų sąrašų.
  • Susietų sąrašų pagrindai (PDF): šis 26 puslapių PDF suteiks jums beveik viską, ką jūs kada nors norėtumėte žinoti, naudodamiesi pseudokodais ir C kalbų pavyzdžiais..
  • Švelnus duomenų struktūrų įvadas: šis paprastas įvadas padės sukurti visą savo susietų sąrašų programą.
  • Susietų sąrašų vadovėliai: tai 7 trumpų vaizdo įrašų rinkinys, susijęs su susietų sąrašų kūrimu C++.
  • Sužinokite-C.org Susietų sąrašų puslapis: šiame puslapyje pateikiami nurodymai, kaip sukurti paprastą C kalba susietą sąrašą.
  • Duomenų struktūros naudojant „Javascript“: sužinokite susietus sąrašus savo naršyklėje naudodamiesi šia „JavaScript“ mokymo programa.

Santrauka

Susieti sąrašai yra puiki idėja ir praktinis būdas valdyti ir kurti dinaminius duomenų rinkinius. Tikimės, kad aukščiau pateikta informacija padėjo jums suvokti ir įgyvendinti pagrindinį susietų sąrašą ir jūs judėsite toliau.

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