Saistītā saraksta apmācība: – darba sākšana ar dinamisko datu glabāšanu

Atklāšana: Jūsu atbalsts palīdz vietnei darboties! Mēs nopelnām nodošanas maksu par dažiem pakalpojumiem, kurus mēs iesakām šajā lapā.


Saistītie saraksti var būt vērtīgs rīks, kad nepieciešams strukturēt dažādas datu kopas un organizēt programmas lineāro informāciju. Tos parasti izmanto kā masīva aizstājēju, jo to izmantošanai ir noteiktas priekšrocības.

Saistītā saraksta pamatā ir vienkārša datu struktūra, kurā ir mezglu secība. Katram mezglam ir savi dati, kā arī rādītājs citam mezglam. Patiesībā viņi bieži tiek mācīti, lai studentiem būtu ērtāk izmantot norādes.

Zemāk jūs uzzināsit, kādi ir saistītie saraksti, kāpēc tie ir vērtīgi un kā tos izveidot. Mēs arī piedāvāsim dažus papildu resursus, lai palīdzētu turpināt izglītību.

Kādi ir saistītie saraksti?

Vienkārši sakot, saistītais saraksts ir pasūtīts datu apkopojums. Tas ir paredzēts lineārām datu struktūrām un ir viena no vienkāršākajām dinamisko datu struktūru ieviešanai. Katru datu elementu sauc par mezglu, un tajā ir viena vērtība un rādītājs nākamajam mezglam sarakstā. Ja rādītājam ir NULL vērtība, tad šis mezgls ir pēdējais sarakstā.

Šis ir piemērs, kas palīdz aptvert šo jēdzienu, izņemot datortehnoloģiju:

Sakiet, ka vērtējat katru personu birojā, pamatojoties uz drukas ātrumu. Jūsu saraksts sākas ar Annu, jo visi zina, ka viņa ir ātrākā – jūs varat dzirdēt skaņu, kas nāk no viņas kabīnes. Viņai tika teikts, ka nākamais ātrākais cilvēks ir Stīvs. Stīvs zina, ka viņa mašīnrakstīšanas ātrums ir tuvs Annam, taču ne tik labi. Viņš arī zina, ka Karena ir gandrīz tikpat ātra kā viņš, bet ne gluži. Pēc tam sarakstu var turpināt šādā veidā. Katram loceklim ir unikāla informācija, kā arī rādītājs tam, kurš ir nākamais ātrākais mašīnrakstītājs.

Tā kā mezgli pastāv neatkarīgi viens no otra, izņemot ar rādītāja attiecībām, tos ir ļoti viegli pievienot, izdzēst un pārvietot.

Saistīto sarakstu veidi

Ir daži dažādi saistīto sarakstu veidi. Vienots saistīts saraksts, divreiz saistīts saraksts, vairākkārt saistīts saraksts un apļveida saišu saraksts. Mēs izpētīsim katru sīkāk zemāk. Izmantojot saistītos sarakstus, varat veikt ievietošanas, dzēšanas un šķērsošanas darbības.

1. Vienots saistītais saraksts

Vienots saistīts saraksts ir datu objektu kopums, kurus savstarpēji saista noteiktas atsauces no viena objekta uz nākamo. Šos objektus bieži sauc par mezgliem. Katrā mezglā būs vismaz viens datu lauks un atsauce uz nākamo mezglu. Vieniem saistītajiem sarakstiem var piekļūt, izmantojot pirmo mezglu, un tos var šķērsot līdz saraksta beigām.

2. Divkārt piesaistīts saraksts

Divkārt piesaistītajos sarakstos ir divas atsauces uz katru mezglu. Atsauces norāda uz nākamo mezglu un iepriekšējo mezglu. Izmantojot šo struktūru, jums ir divvirzienu pieeja datu kopai, un tā piedāvā lielāku elastību un ātrumu, jo varat pārvietoties sarakstā abos virzienos.

3. Saistīts saraksts

Saistītie saraksti ir vispārīgi saistīti saraksti, kuriem ir vairāki papildu saraksti no noteikta mezgla. Jaunie saraksti var būt jebkurā no šeit minētajiem stiliem. Šis saraksta stils var būt noderīgs, lai sakārtotu sarakstu, kas sadalīts pēc lietotāja vārda un vecuma. Vai arī citi datu kopu stili, kur katram datu punktam ir papildu klasifikācija.

4. Apļveida saišu saraksts

Saistītā saraksta galīgo veidu sauc par apļveida saistīto sarakstu. Tā vietā, lai galīgajam mezglam būtu komanda NULL, tas atsaucas uz saraksta galvu. Saraksta struktūra ir līdzīga iepriekš minētajām iespējām.

Kāpēc saistītie saraksti ir svarīgi

Saistītie saraksti ir noderīgi to dinamiskā rakstura dēļ. Skaitļošanas nozīmē tā atmiņu piešķir tikai pēc nepieciešamības. Tātad, ja jums ir lietojumprogramma, kurai nepieciešama bieža izmēra maiņa, dzēšana, ievietošana un datu atjaunināšana, tad saistītais saraksts būs ideāls.

Saistītos sarakstus parasti izmanto, lai ieviestu diagrammas, skursteņus, rindas un citas līdzīgas programmas. Izmantojot saistīto sarakstu, objektus var ievietot jebkur sarakstā. Turklāt jums iepriekš nav jāzina galīgā saraksta lielums. Pēc jūsu izvēles tas var palielināties vai samazināties.

Vienkārša ievietošana un dzēšana ir saistīto sarakstu galvenā priekšrocība. Piemēram, jūs varētu izmantot masīvu, bet masīvi ļauj pievienot un noņemt tikai secīgo objektu, nepārvietojot datu kopu, lai izveidotu atvērtu slotu. Saistītie saraksti ļauj viegli manipulēt ar secīgu datu kopu, neradot lielu slodzi atmiņas resursiem.

Lielākā daļa datorzinātņu programmu turpina mācīt studentiem, kā ieviest saistītos sarakstus, jo tas ir labs ievads dinamiskajās datu struktūrās, kuras jūs varētu vēlēties izmantot reālās programmās. Turklāt, pat ja jūs nekad neizmantojat saistītu sarakstu, tas jums sniegs pietiekamu izpratni, lai izmantotu norādes. Jūs noteikti izmantosit rādītājus daudzās reālās dzīves programmās.

Saistītā saraksta trūkumi

Saistītie saraksti ir lieliski, lai izveidotu viegli modificējamu sarakstu. Tomēr tie nav ideāls risinājums katrai programmai, kā redzēsit tālāk:

  1. Saistītie saraksti nepiedāvā izlases piekļuves punktu. Lai sasniegtu noteiktu vienumu jūsu sarakstā, jums ir jākoriģē pār katru saraksta vienību līdz tam brīdim.
  2. Kods var kļūt nedaudz sarežģīts, jo koda funkcionēšanai ir nepieciešama gan dinamiskā atmiņas iedalīšana, gan norādes.
  3. Saistītā saraksta kopējās pieskaitāmās izmaksas var būt lielākas par masīvu, jo saraksti tiek dinamiski iedalīti.

Tas viss, kas teikts, zinot, kā izmantot saistītos sarakstus, palīdzēs jums labāk izmantot norādes un labāk izprast dinamiskās datu kopas kopumā.

Saistīto sarakstu apmācība

Zemāk jūs uzzināsit, kā izveidot un ieviest saistīto pamata sarakstu. Mēs sāksim ar viena saistīta saraksta izveidi un tā mezgliem, kā arī parādīsim, kā izdzēst un ievietot jaunus mezglus.

Mezgla struktūras izveidošana

Saistītais saraksts sastāv no vairākiem mezgliem, tāpēc mums būs jāizveido struktūra, kas nosaka mezglu. Tam būs jāietver vismaz viens datu mainīgais un viens rādītājs, lai atsauktos uz nākamo mezglu. Savam mērķim mēs pieturēsimies pie mūsu mašīnrakstīšanas ātruma piemēra un izmantosim personas vārdu un ātrumu, kā arī mūsu datus. C daļā datus struktūrā definē šādi:

struktūras mezgls {
virknes nosaukums [32];
int ātrums;
struktūras mezgls * nākamais;
}

Svarīgi šeit ir nākamais rādītājs, kas ļauj mums strādāt, izmantojot sarakstu.

Saistītā saraksta izveidošana

Tagad mums būs jāizveido saraksts, kas patiesībā ir tikai pirmā mezgla izveidošana. Tātad mēs to definējam, piešķiram pietiekami daudz atmiņas vienam mezglam un nākamo rādītāju iestatām uz NULL, lai mēs zinātu, ka tas ir saraksta beigas. Jūs tam iestatāt arī galvas rādītāju, jo tieši šeit sākas saistītais saraksts.

Tad jūs varat aizpildīt informāciju par šo mezglu: darbinieka vārdu un viņa mašīnrakstīšanas ātrumu.

Mezgla ievietošana

Kad ir izveidots mūsu pamata saraksts, mēs tagad varam sākt elementu pievienošanu sarakstam. Tātad, pieņemsim, ka jūs sākāt ar Karenu, kura mašīnrakstīšanas ātrums ir 58 vārdi minūtē. Tālāk jūs vēlaties ievadīt Stīvu ar ātrumu 63. Jūs izveidotu viņam mezglu un aizpildītu datus. Tad jūs meklētu, izmantojot saistīto sarakstu, taču šajā gadījumā būtu tikai viens elements. Jāatzīmē, ka Stīvam ir lielāks mašīnrakstīšanas ātrums, tāpēc viņa nākamo rādītāju iestatījāt uz Karena rādītāju. Tā kā Karenas rādītājs ir arī galvas rādītājs, jūs varētu norādīt galvu uz Stīva mezglu.

Tagad jums ir saistīts saraksts, kas sākas ar Stīva mezglu. Nākamais norāda uz Karenas mezglu. Karenas mezgls norāda uz NULL, norādot, ka viņas mezgls ir pēdējais sarakstā.

Ja darbinieku nolīgtu ar drukas ātrumu starp Karenu un Stīvu, viņiem tiktu izveidots mezgls. Bet tad Stīva nākamais norādītu uz jauno darbinieku, un nākamais nākamais norādītu uz Karena.

No otras puses, ja darbinieks tiktu pieņemts darbā ar mašīnrakstīšanas ātrumu, kas ir mazāks nekā Karena, viņiem atkal tiktu izveidots mezgls. Bet tad Karena nākamais norādītu uz jauno darbinieku, un jaunā darbinieka nākamais norādītu uz NULL.

Mezgla dzēšana

Mezgla izdzēšana no saistītā saraksta faktiski ir diezgan viegls process. Nākamais darbinieka rādītājs, kas atrodas priekšā darbiniekam, kuru vēlamies izdzēst, norāda uz darbinieku pēc darbinieka, kuru vēlamies izdzēst. Pēc tam mēs atbrīvotu izdzēstā mezgla atmiņu vai arī mums rastos atmiņas noplūde.

Protams, ar saistītajiem sarakstiem var paveikt vēl daudz vairāk. Ja jūs interesē vēl vairāk izpētīt saistītos sarakstus, pārbaudiet resursus, kas izcelti zemāk.

Saistītā saraksta resursi

Kad esat sapratis saistošo sarakstu pamatkoncepciju, ir pienācis laiks pilnveidot savas zināšanas. Zemāk mēs piedāvājam dažus papildu resursus, lai palīdzētu patiesi apgūt saistītos sarakstus un labāk izprast datu struktūras:

  • Narasimha Karumanchi izveidotās datu struktūras un algoritmi (2016): lieliska grāmata par datu struktūrām, kas jūs aizvedīs tālu pāri saistītajiem sarakstiem.
  • Saistīto sarakstu pamati (PDF): šis 26 lappušu PDF fails ar pseidokodi un C valodas piemēriem nodrošinās gandrīz visu, ko jūs vēlētos uzzināt..
  • Maigs ievads datu struktūrās: šis vienkāršais ievads ļaus jums izveidot visu savu saistīto sarakstu programmu.
  • Saistītā saraksta konsultācijas: šī ir 7 īsu video kolekcija, lai izveidotu saistītus sarakstus C++.
  • Mācību-C.org saistīto sarakstu lapa: šī lapa palīdzēs jums izveidot vienkāršu ar C valodu saistītu sarakstu.
  • Datu struktūras ar Javascript: apgūstiet saistītos sarakstus tieši pārlūkprogrammā, izmantojot šo JavaScript apmācību.

Kopsavilkums

Saistītie saraksti piedāvā lielisku ideju un praktisku metodi dinamisku datu kopu pārvaldībai un izveidošanai. Cerams, ka iepriekš sniegtā informācija ir palīdzējusi jums saprast un ieviest saistīto pamata sarakstu, un jūs tur virzīsities uz priekšu.

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