[Powered by Google Translate] Programmēšana, mēs bieži vien ir nepieciešams, lai pārstāvētu sarakstus vērtību, piemēram, tādu skolēnu vārdus sekcijā vai viņu rezultāti par jaunāko viktorīnas. 

In C valodā, paziņoja bloki var izmantot uzglabāt sarakstus. Tas ir viegli uzskaitīt elementus sarakstā uzglabā masīvā, un, ja jums ir nepieciešams, lai piekļūtu vai mainīt kārtējam saraksta elementu kādu patvaļīgi indekss es, ko var izdarīt pastāvīgu laiku, bet bloki ir trūkumi, too. 

Kad mēs tos deklarēt, mēs nepieciešams pateikt līdz priekšā cik lielas tās ir, tas ir, cik daudz elementi tās var uzglabāt un cik liels šie elementi ir, ko nosaka to veida. Piemēram, int arr (10) var uzglabāt 10 pozīcijas kas ir lielums int. 

Mēs nevaram izmainīt masīvs lielumu, pēc deklarācijas. Mums ir veikt jaunu masīvu, ja mēs vēlamies saglabāt vairāk elementus. Iemesls šis ierobežojums pastāv, ir, ka mūsu Programma saglabā visu masīvs kā pieguļošajā rieciens atmiņas. Teikt, tas ir buferi, kur mēs uzglabāt mūsu masīvā. Tur varētu būt citi mainīgie atrodas blakus masīva atmiņā, tāpēc mēs nevaram tikai padara masīvs lielāks. 

Dažreiz mēs gribētu tirgoties masīva s ātru datu piekļuves ātrums lai mazliet lielāku elastību. Ievadiet saistīts saraksts, cita pamata datu struktūra jūs varētu nebūt tik pazīstami ar. Augstā līmenī, saistīts saraksts glabā datus tādā secībā mezgliem kas ir saistīti viens ar otru ar saitēm, ceļas vārds "saistīts saraksts." Kā mēs redzēsim, šī atšķirība dizains noved pie dažādām priekšrocībām un trūkumiem kā masīvu. 

Lūk, daži c kods ļoti vienkāršu saistīts saraksts integers. Jūs varat redzēt, ka mēs esam pārstāvēti katrs mezgls sarakstā kā struct kas ir 2 lietas, skaitlim uzglabāt sauc par "val" un saite uz nākamo mezglu sarakstā ko mēs pārstāvam kā rādītājs sauc "nākamo." Tādā veidā, mēs varam izsekot visu sarakstu tikai ar vienu rādītāju uz 1 mezglu, un tad mēs varam sekot nākamajai norādes uz 2 mezglu, līdz 3 mezglu, ar 4 mezglu, un tā tālāk, kamēr mēs uz saraksta beigām. 

Jums varētu būt iespēja redzēt 1 labumu tas ir pa statisko masīvu struktūru - ar saistīta sarakstu, mums nav nepieciešams liels rieciens atmiņas vispār. Gada 1 mezgla sarakstu varētu dzīvot šajā vietā atmiņā, un 2. mezglu varētu būt līdz galam nekā šeit. Mēs varam nokļūt visiem mezgliem vienalga, kur atmiņā tie, jo sākot gada 1 mezglu, katrs mezgls nākamais rādītājs stāsta mums, kur tieši iet nākamo. 

Turklāt, mums nav ko teikt uzreiz cik liels saistīts saraksts būs kā mēs ar statisko bloki, jo mēs varam glabāt pievienojot mezglu sarakstu kamēr tur telpa kaut kur atmiņā jauniem punktiem. Tāpēc, saistītiem saraksti ir viegli mainīt dinamiski. Say, vēlāk programmā mums ir nepieciešams, lai pievienotu vairāk mezglu mūsu sarakstā. Lai ievietotu jaunu mezglu mūsu sarakstā par lidot, viss, kas mums ir jādara, ir piešķirt atmiņu šajā mezglā, plunkšķis kas ir datu vērtības, un tad ievieto to, kur mēs gribam, pielāgojot atbilstošas ​​norādes. 

Piemēram, ja mēs vēlējāmies, lai vieta mezglu starp gada 2 un 3 punkti no saraksta,  mums nebūtu pārvietot 2. vai 3 punktiem vispār. Saka, ka mēs esam ievietojot šo sarkano mezglā. Viss mēs ir jādara, ir noteikt jauno mezglu nākamo rādītāju norādīt līdz 3 mezglu un tad rewire gada 2 mezglu nākamo rādītāju norādīt uz mūsu jauno mezglu. Tātad, mēs varam mainīt mūsu saraksti par lidot jo mūsu datorā nav paļauties uz indeksāciju, bet gan uz saistot izmantojot norādes, lai saglabātu tos. 

Tomēr trūkums saistīti saraksti ir tas, ka, atšķirībā no statisku masīvu, dators var ne tikai lēkt uz vidu sarakstā. Tā kā dators ir apmeklēt katru mezglu saistītajā sarakstā nokļūt uz nākamo, tas notiek, lai ilgāk, lai atrastu konkrētu mezglu nekā tas būtu masīvā. Lai šķērsotu visu sarakstu nepieciešams laiks proporcionāls ar garumu saraksta, vai O (n) asimptotiskā pierakstā. Vidēji, sasniedzot jebkuru mezglu arī nepieciešams laiks proporcionāls n. 

Tagad, pieņemsim faktiski rakstīt kādu kodu kas strādā ar saistītas sarakstiem. Pieņemsim, ka mēs vēlamies saistītu sarakstu integers. Mēs varam pārstāvēt mezglu mūsu sarakstā atkal kā struct ar 2 jomās, vesels vērtību sauc par "val" un blakus rādītājs uz nākamo mezglu saraksta. Nu, šķiet vienkāršs pietiekami. 

Pieņemsim, ka mēs vēlamies, lai rakstītu funkciju kas šķērso to sarakstā un izdrukā vērtība saglabāta pēdējā mezgla saraksta. Nu, tas nozīmē, ka mums būs nepieciešams, lai šķērsotu visus mezglus sarakstā lai atrastu pēdējo vienu, bet, jo mēs esam ne pievienot vai izdzēšot kaut ko, mēs nevēlamies mainīt iekšējā struktūra nākamajos norādes sarakstā. 

Tātad, mums būs nepieciešams rādītāju īpaši šķērsošana ko mēs saucam par "rāpuļprogrammu." Tas būs rāpot cauri visiem saraksta elementu ko pēc ķēdi nākamo norādes. Visi mēs esam saglabāti, ir rādītājs uz 1 mezglu, vai "vadītājs" no saraksta. Galva norāda uz 1 mezglu. Tas ir tipa punktveida uz mezglu. 

Lai iegūtu faktisko 1. mezglu sarakstā, mums ir dereference šo rādītāju, bet pirms mēs varam dereference to, mums ir nepieciešams, lai pārbaudītu ja rādītājs ir nulle pirmais. Ja tas ir Null, saraksts ir tukšs, un mums vajadzētu izdrukāt ziņu, ka, jo saraksts ir tukšs, nav pēdējais mezgls. Bet, teiksim saraksts nav tukšs. Ja tā nav, tad mums vajadzētu indeksēt caur visam sarakstam kamēr mēs līdz pēdējam mezglā saraksta, un kā mēs varam pateikt, ja mēs meklējam pēdējo mezglu sarakstā? 

Nu, ja mezgla nākamais rādītājs ir nulle, Mēs zinām, mēs esam pie beigām kopš pēdējā nākamais rādītājs nebūtu blakus mezglu sarakstu, lai norādītu uz. Tā ir laba prakse, lai vienmēr saglabātu pagājušā mezglu blakus rādītāju inicializēts uz null lai standartizētu īpašumu, kas brīdina mūs, kad mēs esam sasnieguši saraksta. 

Tātad, ja kāpurķēžu → nākamais ir nulle, atcerieties, ka bultiņa sintakse ir īsceļu dereferencing rādītāju uz struct, tad piekļūstot tās nākamās lauka līdzvērtīga neērts: (* Kāpurķēžu). Nākamo. Kad mēs esam noskaidrojuši pēdējo mezglu, Mēs vēlamies, lai drukātu kāpurķēžu → val, vērtība pašreizējā mezglā ko mēs zinām, ir pēdējais. Pretējā gadījumā, ja mēs neesam vēl pēdējā mezglu sarakstā, Mums ir jāvirzās uz nākamo mezglu sarakstā un pārbaudiet, vai tas ir pēdējais. Lai to izdarītu, mēs vienkārši noteikt savu kāpurķēžu rādītāju norādīt uz tekošā mezgla nākamo vērtību, tas ir, nākamais mezglu sarakstā. Tas tiek darīts, nosakot kāpurķēžu = kāpurķēžu → nākamo. Tad mēs atkārtot šo procesu, ar cilpu piemēram, kamēr mēs atrastu pēdējo mezglu. Tātad, piemēram, ja kāpurķēžu bija norādot uz galvas, mēs noteikti rāpuļprogrammu norādīt uz kāpurķēžu → nākamajam kas ir tāds pats kā nākamo jomā gada 1 mezglu. Tātad, tagad mūsu kāpurķēžu ir vērsta uz 2 mezglu, un, atkal, mēs atkārtot ar cilpu, kamēr mēs esam atraduši pēdējo mezglu, tas ir, kur mezgla nākamais rādītājs ir vērsta uz null. Un tur mums ir tā, Mēs esam noskaidrojuši, pēdējo mezglu sarakstā, un izdrukāt savu vērtību, mēs tikai izmantot kāpurķēžu → val. 

Šķērso nav tik slikti, bet kas par ievietošanu? Lets teikt, mēs vēlamies, lai ievietotu skaitlim uz 4. stāvoklī jo skaitlim sarakstā. Tas ir starp pašreizējiem 3 un 4 punktiem. Atkal, mums ir traversa sarakstu tikai nokļūt līdz 3 elementu, viens mēs esam Ievietojot pēc. Tātad, mēs izveidojam kāpurķēžu rādītāju atkal šķērsotu sarakstu, pārbaudīt, ja mūsu galva rādītājs ir nulle, un, ja tas nav, norādīt savu kāpurķēžu rādītāju pie galvas mezglā. Tātad, mēs esam pie gada 1 elementā. Mums ir jāiet uz priekšu vēl 2 elementi, pirms mēs varam ievietot, lai mēs varētu izmantot, lai cilpa int i = 1, i <3; i + + un katrā atkārtojuma no cilpas, iepriekš mūsu rāpulim rādītāju priekšu ar 1 mezglu pārbaudot, ja tekošā mezgla nākamais lauks ir nulle, un, ja tas nav, pārvietot mūsu rāpulim rādītāju uz nākamo mezglu nosakot to vienāda tekošā mezgla nākamā rādītājs. Tātad, jo mūsu lai cilpa saka darīt, ka divreiz, Mēs esam sasnieguši arī 3 mezglā, un tiklīdz mūsu rāpuļprogramma rādītājs ir sasniedzis mezglu pēc ko mēs vēlamies ievietot mūsu jauno skaitlim, kā mēs faktiski darīt ievietojot? 

Nu, mūsu jaunais skaitlim ir jāiekļauj sarakstā kā daļa no tās pašas mezgla struct, jo tas ir patiešām secība mezgliem. Tātad, pieņemsim jaunu rādītāju uz mezglu saukta "new_node, ' un noteikt to norādīt uz atmiņu ka mēs tagad piešķirt par kaudzes par mezglā pati, un cik daudz atmiņas mums vajag piešķirt? Nu, lieluma mezglā, un mēs vēlamies noteikt savu val lauku uz skaitlim, ka mēs vēlamies, lai ievietotu. Teiksim, 6. Tagad mezglā ir mūsu veselam skaitlim. Tā ir arī laba prakse, lai sāktu jauno mezglu nākamo lauku norādīt uz null, bet tagad ko? 

Mums ir jāmaina iekšējo struktūru sarakstu un nākamie norādes sarakstā ietvertajām kādreizējā 3 un 4 punktiem. Tā kā nākamās norādes nosaka saraksta secību, un, jo mēs esam Ievietojot mūsu jauno mezglu labi vidū saraksta, tas var būt nedaudz grūts. Tas ir tāpēc, atcerieties, mūsu dators tikai zina vietu mezglu sarakstā jo nākamajos norādes glabājas iepriekšējos mezgliem. Tātad, ja mēs kādreiz zaudējis dziesmu no jebkura no šīm vietām, saka, mainot vienu no nākamajiem norādes mūsu sarakstā, Piemēram, saka, mēs mainīts The 3rd mezgla nākamais lauks norādīt uz kādu mezglu nekā šeit. Mēs gribētu būt no luck, jo mēs nebūtu ir kāda ideja, kur atrast pārējo sarakstu, un tas acīmredzot tiešām slikti. Tātad, mums ir jābūt ļoti uzmanīgiem par rīkojuma kurā mēs manipulēt mūsu nākamais palīglīdzekļi ievietošanas laikā. 

Tātad, lai vienkāršotu šo, pieņemsim, ka Mūsu pirmie 4 mezgliem sauc A, B, C un D, ​​ar bultiņām, kas pārstāv ķēdi norādes kas savieno mezglus. Tātad, mums ir nepieciešams, lai ievietotu mūsu jauno mezglu starp mezglu C un D Tas ir svarīgi to darīt pareizajā secībā, un es tev parādīšu, kāpēc. 

Apskatīsim nepareizā veidā to darīt vispirms. Hei, mēs zinām jaunais mezgls ir jānāk uzreiz pēc C, tāpēc pieņemsim noteikt C ir nākamais rādītājs norādīt uz new_node. Viss labais, šķiet labi, mēs vienkārši ir pabeigt līdz šim ar padarot jauno mezglu blakus rādītājs norāda uz D, Bet pagaidiet, kā mēs varam darīt? Vienīgais, kas varētu mums pastāstīt, kur D bija, Tika nākamais rādītājs iepriekš glabājas C, bet mēs vienkārši pārrakstīja ka rādītāju norādīt uz jaunu mezglu, tāpēc mums vairs nav nekādas jausmas, kur D ir atmiņā, un mēs esam zaudējuši pārējo sarakstu. Nav labi. 

Tātad, kā mēs izdarīt labi? Pirmkārt, punkts jaunā mezglu nākamo rādītāju pie D. Tagad gan jaunā mezglu un C ir nākamais norādes ir norāda uz to pašu mezglu, D, bet tas ir jauki. Tagad mēs varam punkts C 's nākamo rādītāju pie jaunu mezglu. Tātad, mēs esam izdarījuši, nezaudējot nekādus datus. Ar kodu, C ir pašreizējā mezgls ka šķērsošana rādītājs kāpurķēžu ir vērsta uz, un D ir pārstāvēta ar mezglu, ko uzrādīja tekošā mezgla nākamajā laukā, vai kāpurķēžu → nākamo. Tātad, mēs vispirms noteikt jauno mezglu nākamo rādītāju norādīt uz kāpurķēžu → nākamajam Tāpat mēs teikt new_node nākamais rādītājs būtu norāda uz D attēlā. Tad mēs varam noteikt tekošā mezgla nākamo rādītāju ar mūsu jauno mezglu, tāpat kā mums bija jāgaida, lai pielikuma C new_node zīmējumā. Tagad viss ir kārtībā, un mēs nezaudēja izsekot jebkuru datu, un mums bija iespēja tieši pieturēties mūsu jauno mezglu vidū saraksta bez pārbūves visa lieta vai pat novirzot nekādus elementus kā mēs būtu bijis ar noteikta garuma masīvs. 

Tātad, saistītiem saraksti ir pamata, bet svarīgi, dinamisku datu struktūra kas ir gan priekšrocības, gan trūkumi salīdzinot ar masīvu un citu datu struktūru, un kā tas bieži notiek datorzinātnes, tas ir svarīgi zināt, kad izmantot katru rīks, lai jūs varētu izvēlēties pareizo rīku labo darbu. 

Lai iegūtu plašāku prakses, mēģiniet rakstot funkcijas dzēst mezglu no saistītajā sarakstā - atcerieties jābūt uzmanīgiem par rīkojumu, kurā jūs pārkārtot jūsu nākamais norādes, lai nodrošinātu, ka jums nav zaudēt rieciens savu sarakstu - vai funkciju, lai saskaitītu mezglu saistītajā sarakstā, vai jautri viens, lai mainītu secību visu, kas ir saistīts saraksts mezgliem. 

Mans vārds ir Džeksons Steinkamp, ​​tas ir CS50.