[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.