[MŪZIKA ATSKAŅOTĀSSKAN MŪZIKA]
DUGS LOJSDAGS LOIDS: Labi, tāpēctātad šajā kursa punktā mēs esam
apskatījuši daudzus C valodas pamatus.
Mēs daudz zinām par mainīgajiem lielumiem, masīviem, rādītājiem un
visu to labovisām tām noderīgajām lietām.
Tie visi ir iebūvēti, lai tos uzskatītu par pamatiem, taču mēs varam
darīt vairāk, vai ne?
Mēs varam apvienot lietas interesantā veidā.
Un tāpēc darīsim to, sāksim atzarot no tāizvērst to, ko mums sniedz
C, un sāksim veidot savas datu struktūras, izmantojot šos veidojošos
blokus kopā, lai paveiktu kaut ko patiešām vērtīgu, noderīgu.
Viens no veidiem, kā mēs to varam izdarīt, ir runāt par
kolekcijāmdatu kopām.
Līdz šim mums ir bijusi viena veida datu struktūra līdzīgu vērtību,
līdzīgu vērtību kolekcijasdatu kopu attēlošanai.
Tas būtu masīvs.
Mums ir veselu skaitļu kolekcijasdatu kopas vai rakstzīmju
kolekcijasdatu kopas un tā tālāk.
Struktūras ir arī sava veida datu struktūra informācijas vākšanai,
taču tā nav paredzēta līdzīgu vērtību apkopošanai.
TasTā parasti sajauc dažādus datu tipus vienā lodziņā.
Bet tas pats par sevi netiek izmantots, lai savienotu kopā vai
savienotu līdzīgus vienumus, piemēram, masīvukā, piemēram, masīvs.
Masīvi ir lieliski piemēroti elementu meklēšanai, taču atcerieties,
ka tos ir ļoti grūti ievietot masīvā, ja vien mēs neievietojam šī
masīva pašās beigās.
Un labākais piemērs tam ir ievietošanas kārtošana.
Ja atceraties mūsu video par ievietošanas kārtošanu, bija daudz
izdevumu, kas saistīti ar elementu paņemšanu un pārvietošanu, lai
kaut ko ievietotu jūsu masīva vidū.
Masīvi cieš arī no citas problēmas, kas ir neelastība.
Kad mēs deklarējam masīvu, mēs iegūstam vienu šāvienuiespēju.
Mums jāsakavaram pateikt, ka es vēlos tik daudz elementu.
Var būt 100, 1000, var būt x, kur x ir skaitlis, ko lietotājs mums
norādījis uzvednē vai komandrindā.
Bet mēs to saņemam tikai vienu reizi, mēs nevaram pateikt, ak,
patiesībā man vajadzēja 101 vai man vajadzēja x plus 20.
Par vēlu, mēs jau esam deklarējuši masīvu, un, ja mēs vēlamies iegūt
101 vai x plus 20, mums ir jādeklarē pavisam cits masīvs, jāpārkopē
visi masīva elementi, un tad mums ir pietiekami daudz.
Un ko darīt, ja mēs atkal kļūdāmies, ja mums tiešām ir nepieciešams
102 vai x plus 40, mums tas ir jādara vēlreiz.
Tāpēc tie ir ļoti neelastīgi, lai mainītu mūsu datu izmērus, taču, ja
mēs apvienojam dažus pamatus, ko jau esam iemācījušies par rādītājiem
un struktūrām, jo īpaši izmantojot dinamisko atmiņas piešķiršanu ar
mallocmalloc, mēs varam apvienot šīs daļas, lai izveidotu jaunu. datu
struktūrastruktūru — atsevišķi saistīts sarakstssaistītu sarakstu, ko
mēs varētu teikt —, kas ļauj mums palielināt un samazināt vērtību
kolekcijudatu kopu, un mēs netērēsim vietu.
Tātad atkal mēs šo ideju, šo jēdzienu saucam par saistīto sarakstu.
KonkrētiProti, šajā videoklipā mēs runājam par atsevišķi saistītu
sarakstu, un pēc tam citā videoklipā mēs runāsim par divkārši
saistītiem sarakstiem, kas šeit ir tikai tēmas variants.
Bet atsevišķi saistīts saraksts sastāv no mezgliem, mezgli ir tikai
abstrakts termins — tas ir tikai kaut kas, ko es saucunosaucu, tā ir
sava veida struktūra, vai es esmune?
Vienkārši nosauksim to par mezglu — un šim mezglam ir divi
dalībniekidivi elementi vai divi lauki.
Tam ir dati, parasti vesels skaitlis, rakstzīmju pludiņšpeldošā
punkta skaitlis, vai kāds cits datu tips, ko esat definējisdefinējuši
ar tipu typedef.
Un tajā ir rādītājs uz citu tāda paša veida mezglu.
Tātad šajā mezglā ir divas lietas: dati un rādītājs uz citu mezglu.
Un, ja sākat to vizualizēt, varat domāt par to kā par mezglu ķēdi,
kas ir savienoti kopā.
Mums ir pirmais mezgls, tajā ir dati un rādītājs uz otro mezglu, kurā
ir dati, un rādītājs uz trešo mezglu.
Un tāpēc mēs to saucam par saistīto sarakstu, tie ir saistīti kopā.
Kā izskatās šī īpašā mezgla struktūra?
Ja atceraties mūsu videoklipu par pielāgoto tipu definēšanu,
izmantojot tipu deftypedef, mēs varam definēt struktūru, betun tips
definēttype define šādu struktūru.
tyepdeftypedef struct sllist, un tad es patvaļīgi izmantoju vārdu
vērtību, lai norādītu jebkuru datu tipu.
Jūs varētu nodot veselu skaitli vai peldētpeldošā punkta skaitli,
jums var būt viss, ko vēlaties.
Tas neaprobežojas tikai ar veseliem skaitļiem vai kaut ko tamlīdzīgu.
Tātad vērtība ir tikai patvaļīgs datu tips un pēc tam rādītājs uz
citu tāda paša veida mezglu.
Tagad šeit ir neliela nozīmeaizķeršanās, definējot struktūru, ja tā
ir pašreferences struktūra.
Man ir jābūt pagaidu nosaukumam manai struktūrai.
Galu galā es to nepārprotami vēlos saukt par sll node, kas galu galā
ir mana tipa definīcijas jaunā nosaukuma daļa, taču es nevaru
izmantot sll node šī savienojuma vidū.
Iemesls ir tāds, ka es neesmu izveidojis tipu, ko sauc par sll node,
līdz es šeit sasniedzu pēdējo punktu.
Līdz šim brīdim man ir jābūt citam veidam, kā atsaukties uz šo datu
veidu.
Un tas ir pašreferences datu tips.
Tas ir datu tips struktūrai, kurā ir dati, un rādītājs uz citu tāda
paša veida struktūru.
Tāpēc man ir jābūt iespējai vismaz īslaicīgi atsaukties uz šo datu
tipu, tāpēc, piešķirot tam pagaidu nosaukumu struct sllist, es varu
pateikt, ka vēlos rādītāju uz citu struct sllist, struct sllist
zvaigznistar, un pēc tam pabeidzu definīciju, tagad varu saukt šo
tipu par sll mezglunode.
Tāpēc jūs redzat, ka šeit ir pagaidu nosaukums, bet šeit pastāvīgs
nosaukums.
Dažkārt var tikt rādītas, piemēram, struktūras definīcijas, kas nav
pašreferences, kurām šeit nav norādīts precizējošs nosaukums.
Tas vienkārši teiktu typedef struct, atveriet cirtaini
figūriekavafigūriekavas un pēc tam definējiet to.
Bet, ja jūsu struktūra ir pašreference, kā tas ir šajā gadījumā, jums
ir jānorāda pagaidu tipa nosaukums.
Bet galu galā, tagad, kad esam to izdarījuši, mēs varam vienkārši
atsaukties uz šiem mezgliem, šīm vienībām kā maziem mezgliemsll nodes
pārējā šī videoklipa nolūkos.
Labi, tāpēctātad mēs zinām, kā izveidot saistītā saraksta mezglu.
Mēs zinām, kā definēt saistītā saraksta mezglu.
Tagad, ja mēs sāksim tos izmantot informācijas vākšanai, mums ir
jāsaprot dažas darbības un ar tām jāstrādā.
Mums ir jāzina, kā no zila gaisa izveidot saistīto sarakstu.
Ja vēl nav saraksta, mēs vēlamies to sākt.
Tāpēc mums ir jāspēj izveidot saistīto sarakstu, iespējams, ir
jāmeklē saišu sarakstā, lai atrastu elementu, ko meklējam.
Mums ir jāspēj sarakstā ievietot jaunas lietas, mēs vēlamies, lai
mūsu saraksts varētu augt.
Un līdzīgi, mēs vēlamies, lai mēs varētu izdzēst lietas no sava
saraksta, mēs vēlamies, lai mūsu saraksts varētu sarukt.
Un mūsu programmu beigās, it īpaši, ja atceraties, ka mēs parasti
dinamiski piešķiram atmiņu, lai izveidotu šos sarakstus, mēs vēlamies
atbrīvot visu šo atmiņu, kad esam pabeiguši darbu ar to.
Un tāpēc mums ir jāspēj dzēst visu saistīto sarakstu vienā piegājienā.
Tāpēc apskatīsim dažas no šīm darbībām un to, kā tās varētu
vizualizēt, runājot īpašikonkrēti pseidokoda kodā.
Tāpēc mēs vēlamies izveidot saistīto sarakstu, tāpēc varbūt mēs
vēlamies definēt funkciju ar šo prototipu.
sll node star, izveidojietcreate, un es nododu vienu argumentu, atkal
kaut kādu patvaļīgu datu tipu, kādu patvaļīgu datu tipu.
Bet es atgriežos — šai funkcijai ir jāatgriež man rādītājs, uz
atsevišķi saistītu saraksta mezglu.
Atkal mēs cenšamies no zila gaisa izveidot saistīto sarakstu, tāpēc
man ir nepieciešams rādītājs uz šo sarakstu, kad esmu pabeidzis.
Tātad, kādi soļi šeit ir saistītiiesaistīti?
Pirmā lieta, ko es darīšu, ir dinamiski piešķirt vietu jaunam mezglam.
Atkal mēs to veidojam no zila gaisa, tāpēc mums ir jāatrod vieta.
Un, protams, uzreiz pēc tam, kad mēs esam izspiedušipiešķīruši vietu,
mēs vienmēr pārbaudām, vai mūsu rādītājs — mums nav atgriezts nulles
rādītājs.
Jo, ja mēs cenšamies neievērot nulles rādītāju, mēs cietīsim no
bloķēšanas, un mēs to nevēlamies.
Tad mēs vēlamies aizpildīt lauku, mēs vēlamies inicializēt vērtības
lauku un inicializēt nākamo lauku.
Un tad mēs vēlamies — galu galā, kā norāda funkcijas prototips — mēs
vēlamies atgriezt rādītāju uz sll nodemezglu.
Tātad, kā tas izskatās vizuāli?
Vispirms mēs dinamiski atvēlēsim vietu jaunam sll nodemezglam, tāpēc
mēs mallocējammalloc — tas ir tikko izveidotā mezgla vizuāls
attēlojums.
Un mēs pārbaudām, vai tas nav nullesnulle — šajā gadījumā attēls
netiktu parādīts, ja tas būtu nulle, mums būtu beigusies atmiņa,
tāpēc mēs varam tur doties.
Tātad tagad mēs ejam uz darbību C, inicializējiet mezglu vērtības
lauku.
Pamatojoties uz šo funkciju izsaukumu, ko izmantoju šeit, izskatās,
ka es vēlos nokārtotiet uz 6, tāpēc vērtību laukā likšu 6.
Tagad inicializējiet nākamo lauku.
Nu, ko es tur darīšu, tālāk nekā nav, labipareizi, tas ir vienīgais,
kas sarakstā.
Tātad, kāda ir nākamā lieta sarakstā?
Tam nevajadzētu ne uz ko norādīt, vai ne.
Tur nekā cita nav, tāpēc kāds ir mūsu zināmais jēdziens, kas ir
nekas — norādesrādītāji uz neko?
Varbūt mēs vēlamies tur ievietot nulles rādītāju, un es attēlošu
nulles rādītāju kā tikai sarkanu lodziņu, mēs nevaram iet tālāk.
Kā mēs redzēsim nedaudz vēlāk, galu galā mums būs bultu ķēdes, kas
savienos šos mezglus, taču, noklikšķinot uz sarkanā lodziņa, tas ir
nulle, mēs nevaram iet tālāk, tas ir saraksta beigas.
Un visbeidzot, mēs vienkārši vēlamies atgriezt rādītāju uz šo mezglu.
Tāpēc mēs to nosauksim par jaunu un atgriezīsim jaunu, lai to varētu
izmantot jebkurā funkcijā, kas to izveidoja.
Tā nu mēs esam izveidojuši atsevišķi saistītu saraksta mezglu, un
tagad mums ir saraksts, ar kuru varam strādāt.
Tagad pieņemsim, ka mums jau ir liela ķēde, un mēs vēlamies tajā kaut
ko atrast.
Un mēs vēlamies funkciju, kas atgriezīs patieso vai nepatieso vērtību
atkarībā no tā, vai šajā sarakstā ir kāda vērtība.
Funkcijas prototips vai šīs funkcijas deklarācija varētu izskatīties
šādi - bool find, un tad mēs vēlamies nodot divus argumentus.
Pirmais ir rādītājs uz saistītā saraksta pirmo elementu.
Tas patiesībā ir kaut kas tāds, kam vienmēr vēlēsities sekot līdzi,
un patiesībā tas var būt kaut kas tāds, ko pat ievietojat globālā
mainīgāmainīgajā.
Kad esat izveidojis sarakstu, jūs vienmēr vēlaties sekot līdzi
pirmajam saraksta elementam.
Tādā veidā jūs varat atsaukties uz visiem pārējiem elementiem,
vienkārši sekojot ķēdei, nesaglabājot norādes neskartasneskartus
rādītājus uz katru elementu.
Jums tikai ir jāseko līdzi pirmajam tikai tad, ja tie visi ir
savienoti kopā.
Un tad otrā lieta, ko mēs atkal nododam, ir patvaļīgi daži —
neatkarīgi no tā, kādu datu veidu mēs meklējam, tas, cerams, atrodas
vienā no saraksta mezgliem.
Tātad, kādi ir soļi?
Pirmkārt, mēs izveidojam šķērsvirzienatransversālo rādītāju, kas
norāda uz saraksta galvu.
Kāpēc mēs to darām, mums jau ir rādītājs uz sarakstupie saraksta
galvas, kāpēc mēs to vienkārši nepārvietojam?
Nu, kā es tikko teicu, mums ir ļoti svarīgi vienmēr sekot līdzi
saraksta pirmajam elementam.
Tāpēc labāk ir izveidot tā dublikātu un izmantot to, lai pārvietotos,
lai mēs nekad nejauši neatkāptosneaizvirzītos projām, vai arī mums
vienmēr ir rādītājs, kas atrodas tieši uz saraksta pirmā elementa.
Tāpēc labāk ir izveidot otru, ko izmantojam pārvietošanai.
Pēc tam mēs vienkārši salīdzinām, vai vērtību lauks šajā mezglā ir
tas, ko mēs meklējam, un, ja tā nav, mēs vienkārši pārejam uz nākamo
mezglu.
Un mēs turpinām to darīt atkal un atkal, un vēl, līdz mēs vai nu
atrodam elementu, vai arī nospiežam nulli — esam sasnieguši saraksta
beigas, un tā tur nav.
Cerams, ka tam vajadzētu zvanīt jums atgādināt kā tikai lineārai
meklēšanailineāro meklēšanu. Mēs to tikai atkārtojam atsevišķi
saistītā saraksta struktūrā, nevis izmantojam masīvu.
Tātad, šeit ir atsevišķi saistīta saraksta piemērs.
Šis sastāv no pieciem mezgliem, un mums ir rādītājs uz saraksta
galvu, ko sauc par sarakstu.
Pirmā lieta, ko mēs vēlamies darīt, ir vēlreiz izveidot šo
šķērsošanastransversālo rādītāju.
Tāpēc tagad mums ir divas norādesdivi rādītāji, kas norāda uz vienu
un to pašu.
Tagad ievērojiet arī šeit, man nebija jāatstāj vieta trav.
Es neteicu, ka trav ir vienāds ar malloc kaut koequals malloc
something, katas mezgls jau pastāv, katā vieta atmiņā jau pastāv.
Tāpēc viss, ko es patiesībā daru, ir izveidot citu rādītāju.
Es neizmantoju papildu atstarpivietu, tikai tagad ir divas
norādesdivi rādītāji, kas norāda uz vienu un to pašu.
Tātad, vai 2 ir tas, ko es meklēju?
Nu` nē, tā vietā es pāriešu uz nākamo.
Tātad būtībā es teiktu, trav ir vienāds arequals trav kā nākamo.
Vai es meklēju 3, nē.
Tāpēc es turpinu iet cauri, līdz galu galā nokļūstu līdz 6, ko es
meklēju, pamatojoties uz funkcijas izsaukumu, kas man ir augšpusē, un
es esmu pabeidzis.
Ko darīt, ja elementselementa, kuru meklēju, nav sarakstā, vai tas
joprojām darbosies?
Ņemiet vērā, ka saraksts šeit ir smalkimazliet atšķirīgs, un šī ir
vēl viena lieta, kas ir svarīga saistītajos sarakstos. Jums tie nav
jāsaglabā noteiktā secībā.
Ja vēlaties, varat, taču, iespējams, jau esat pamanījis, ka mēs
nesekojam uz totam, kurāpie kāda skaitļa elementāelementa atrodamies.
Un tas ir viens no darījumiem, kas mums ir ar saistītiem
sarakstasaistīto sarakstu pantupretstatā masīviem, vai mums vairs nav
nejaušas piekļuves.
Mēs nevaram vienkārši pateikt, es gribu pāriet uz 0. elementu vai 6.
elementu savā masīvā, ko es varu darīt masīvā.
Es nevaru teikt, ka vēlos pāriet uz saistītā saraksta 0. vai 6.
elementu, vai 25. elementu, ar tiem nav saistīts rādītājs.
Un tāpēc nav īsti svarīgi, vai mēs saglabājam savu sarakstu kārtībā.
Ja vēlaties, jūs noteikti varat, bet nav iemesla, kāpēc tie ir
jāsaglabā jebkurākaut kādā secībā.
Tātad vēlreiz, mēģināsim atrast 6 šajā sarakstā.
Nu, mēs sākam no sākuma, mēs neatrodam 6, un tad mēs turpinām,
neatrodam 6, līdz galu galā nonākam šeit.
Tāpēc šobrīd trav norāda uz mezglu, kurā ir 8, un seši tur nav.
Tātad nākamais solis būtu pāriet uz nākamo rādītāju, tāpēc sakiet, ka
trav ir vienāds arequals trav nextkā nākamo.
Nu, trav next, ko norāda sarkanais lodziņš, ir nulle.
Tātad vairs nav, kur iet, un tāpēc šobrīd mēs varam secināt, ka esam
sasnieguši saistītā saraksta beigas un 6 tajā nav.
Un šajā gadījumā tas tiktu atgriezts kā nepatiess.
Labi, kā saistītajā sarakstā ievietot jaunu mezglu?
TāpēcTātad mēs esam varējuši izveidot saistītu sarakstu no
nekurienes, taču mēs, iespējams, vēlamies izveidot ķēdi, nevis
izveidot dažādu sarakstu kopumu.
Mēs vēlamies, lai būtu viens saraksts, kurā būtu virkne mezglu, nevis
sarakstu ķekarskopums ar vienu mezglu.
Tāpēc mēs nevaram vienkārši turpināt izmantot iepriekš definēto
funkciju IzveidotCreate function, tagad mēs vēlamies ievietot to
sarakstā to, kas jau pastāv.
Tātad šajā gadījumā mēs nodosim divus argumentus — norādirādītāju uz
šī saistītā saraksta sākumugalvu, kuru mēs vēlamies papildināt.
Atkal, tāpēc ir tik svarīgi, lai mēs vienmēr tam sekotu līdzi, jo
vienīgais veids, kā mums patiešām ir jāatsaucas uz visu sarakstu, ir
tikai ar rādītāju uz pirmo elementu.
Tāpēc mēs vēlamies nodot rādītāju šim pirmajam elementam un jebkurai
vērtībai, ko mēs vēlamies pievienot sarakstam.
Un galu galā šī funkcija atgriezīs rādītāju uz saistītā saraksta
jauno galvu.
Kādas darbības šeit ir ietvertas?
Tāpat kā izveides gadījumā, mums ir dinamiski jāpiešķir vieta jaunam
mezglam un vēlreiz jāpārbauda, vai mums nav beigusies atmiņa, jo mēs
izmantojam mallocmalloc.
Pēc tam mēs vēlamies aizpildīt un ievietot mezglu, tāpēc ievietojiet
mezglā numuruskaitli neatkarīgi no tā, kas ir val.
Mēs vēlamies ievietot mezglu saistītā saraksta sākumā.
Ir iemesls, kāpēc es vēlos to darīt, un, iespējams, ir vērts nedaudz
pauzēt videoklipu un padomāt par to, kāpēc es vēlos ievietot saistītā
saraksta sākumā.
Atkal jau iepriekš minēju, ka nav īsti svarīgi, vai mēs to saglabājam
kādā secībā, tāpēc varbūt tas ir pavediens.
Un jūs redzējāt, kas notiktu, ja mēs to vēlētos, vai tikai pirms
sekundes, kad veicām meklēšanu, jūs varētuvarējāt redzēt, kas varētu
notikt, ja mēs mēģinātu ievietot saraksta beigās.
Jo mums nav rādītāja uz saraksta beigām.
Tāpēc iemesls, kokāpēc es vēlētos ievietot sākumā, ir tāpēc, ka es to
varu izdarīt nekavējoties.
Man sākumā ir rādītājs, un mēs to redzēsim vizuālā veidā pēc sekundes.
Bet, ja es gribu ievietot beigās, man ir jāsāk no sākuma, jāšķērso
līdz galam un tad jāpieliekjāpievieno.
Tātad tas nozīmētu, ka ievietošana saraksta beigās kļūtu par o no n
darbībudarbības, atgriežoties pie mūsu diskusijas par skaitļošanas
sarežģītību.
Tā būtu kļuvusi par o no n operācijasdarbības, kur, sarakstam kļūstot
arvien lielākam, arvien lielākam un lielākam, beigās būs arvien
grūtāk kaut ko pieminētpievienot.
Bet vienmēr ir ļoti viegli kaut ko pielikt sākumā, jūs vienmēr esat
sākumā.
Un mēs to redzēsim vēlreiz.
Kad esam pabeiguši, kad esam ievietojuši jauno mezglu, mēs vēlamies
atgriezt savu rādītāju uz jauno saistītā saraksta galvenigalvu, kas,
tā kā mēs ievietojam sākumā, faktiski būs rādītājs uz mezglu., ko mēs
tikko izveidojām.
Vizualizēsim to, jo es domāju, ka tas palīdzēs.
Tātad, šeit ir mūsu saraksts, tas sastāv no četriem elementiem,
mezgla, kurā ir 15, kas norāda uz mezglu, kurā ir 9, kas norāda uz
mezglu, kurā ir 13, kas norāda uz mezglu, kurā ir 10, kuram ir nulles
rādītājs kā nākamais rādītājs. tasTās ir saraksta beigas.
Tātad mēs vēlamies ievietot jaunu mezglu ar vērtību 12 šī saraksta
sākumā. Ko mums darīt?
Vispirms mēs atvēlam vietu mezglam un pēc tam ievietojam 12.
Tātad tagad mēs esam sasnieguši lēmuma pieņemšanas punktu, vai ne?
Mums ir pāris norādesrādītāju, ko mēs varētu pārvietot, kuru
vajadzētu pārvietot vispirms?
Vai mums vajadzētu likt 12 punktus jaunajamjaunajai saraksta
priekšgalamgalvai vai, atvainojiet, vai 12 punktus likt
vecajamvecajai saraksta vadītājamgalvai?
Vai arī jāsaka, ka saraksts tagad sākas ar 12.?
Tur ir atšķirība, un mēs pēc mirkļa apskatīsim, kas notiek ar abiem.
Bet tas noved pie lieliskas tēmas sānjoslai, proti, viena no
sarežģītākajām lietām saistītajos sarakstos ir sakārtot rādītājus
pareizā secībā.
Ja izvedīsiet lietas no ierindas, varat nejauši kļūt par
bāreņiemiznīcināt pārējo saraksta daļu.
Un šeit ir piemērs tam.
Tātad, pieņemsim, ka mēs tikko esam izveidojuši 12.
Mēs zinām, ka 12 būs jaunaisjaunā saraksta vadītājsgalva, un kāpēc
gan mēs vienkārši nepārvietojamtāpēc varbūt vienkārši pārvietosim
saraksta rādītāju uz turieni.
Labi, tas ir labi.
Tātad, kur tagad ir 12 nākamais punktsrāda?
Es domāju, ka vizuāli mēs varam redzēt, ka tas norādīs uz 15, jo mums
kā cilvēkiem tas ir patiešām acīmredzams.
Kā dators zina?
Mums vairs nav nekā, kas norāda uz 15, vai ne?
Mēs esam zaudējuši jebkādu spēju atsaukties uz 15.
Mēs nevaram teikt, ka jaunā bultiņa ir vienāda ar kaut ko, tur nekā
nav.
Faktiski, šādi rīkojoties, mēs esam atstājuši bāreņuiznīcinājuši
pārējo sarakstu, mēs nejauši esam pārrāvuši ķēdi.
Un mēs noteikti nevēlamies to darīt.
Tāpēc atgriezīsimies un mēģināsim vēlreiz.
Varbūt pareizi ir vispirms iestatīt 12. nākamo rādītāju uz veco
saraksta galvu, pēc tam varam pārvietot sarakstu.
Un patiesībā tā ir pareizā secība, kas mums jāievēro, strādājot ar
atsevišķi saistītu sarakstu.
Mēs vienmēr vēlamies pievienot jauno elementu sarakstam, pirms veicam
tik svarīgu soli, mainot to, kur atrodas saistītā saraksta galva.
Atkal, tā ir tik būtiska lieta, ka mēs nevēlamies to zaudēt.
Tāpēc pirms rādītāja pārvietošanas mēs vēlamies pārliecināties, ka
viss ir savienots kopā.
Un tā būtu pareizā secība, proti, savienot 12 ar sarakstu, pēc tam
teikt, ka saraksts sākas ar 12.
Ja mēs teicām, ka saraksts sākas ar 12, un pēc tam mēģinājām
pievienot sarakstam 12, mēs jau esam redzējuši, kas notiek.
Mēs sarakstu zaudējam kļūdas dēļ.
Labi, vēl viena lieta, par ko runāt.
Ko darīt, ja mēs vēlamies uzreiz atbrīvoties no visa saistītā
saraksta?
Atkal, mēs bloķējamizmantojam visu šo vietu, tāpēc mums tā ir
jāatbrīvo, kad esam pabeiguši.
Tāpēc tagad mēs vēlamies izdzēst visu saistīto sarakstu.
Nu, ko mēs gribam darīt?
Ja esam sasnieguši nulles rādītāju, mēs vēlamies apstāties, pretējā
gadījumā vienkārši izdzēsiet pārējo sarakstu un pēc tam atbrīvojiet
mani.
Izdzēsiet pārējo saraksta daļu un pēc tam atbrīvojiet pašreizējo
mezglu.
Kā tas izklausās, par kādu tehniku mēs iepriekš runājām, vaikā tas
izklausās?
Izdzēsiet visus pārējos, pēc tam atgriezieties un izdzēsiet mani.
Tā ir rekursija, mēs esam padarījuši problēmu mazliet mazāku, mēs
sakām, ka izdzēsiet visus pārējos, tad varat izdzēst mani.
Un tālāk pa ceļuceļam šis mezgls teiks: dzēst visus pārējos.
Bet galu galā mēs nonāksim līdz vietai, kur saraksts ir nulle, un tas
ir mūsu pamata gadījumspamatgadījums.
Apskatīsim to un kā tas varētu darboties.
Tātad, šeit ir mūsu saraksts, tas ir tas pats saraksts, par kuru mēs
tikko runājām, un tur ir norādītas darbības.
Šeit ir daudz teksta, bet cerams, ka vizualizācija palīdzēs.
Mēs esam izdarījuši — un es arī izvilku mūsu steka kadru ilustrāciju
no mūsu video par zvanu skursteņiemizsaukuma stekiem, un cerams, ka
tas viss kopā parādīs notiekošo.
Tātad, šeit ir mūsu pseidokoda kods.
Ja sasniedzam nulles rādītāju, apstājieties, pretējā gadījumā
izdzēsiet pārējo sarakstu un pēc tam atbrīvojiet pašreizējo mezglu.
Tāpēc šobrīd uzskaitietsaraksts — rādītājs, kuru mēs virzām, lai
iznīcinātu, punktusnorāda uz 12.
12 nav nulles rādītājs, tāpēc mēs dzēsīsim pārējo sarakstu.
Kas ir mūsu pārējo iesaistīto personu dzēšana?
Tas nozīmē, ka jāaicinaizsaukumu iznīcināt, sakot, ka 15 ir sākums
pārējam sarakstam, kuru vēlamies iznīcināt.
Un tāpēc aicinājumsizsaukums iznīcināt 12 ir sava veidatāds kā
aizturēts.
Tas tur ir sasalisiesaldēts, gaidot aicinājumu iznīcināt 15, lai
pabeigtu savu darbu.
Nu, 15 nav nulles rādītājs, un tāpēc tas saka: labi, labi, izdzēsiet
pārējo sarakstu.
Pārējā saraksta daļa sākas ar 9, tāpēc mēs vienkārši pagaidīsim, līdz
izdzēsīsit visu šo saturu, un pēc tam atgriezīsimies un izdzēsīsim
mani.
Nu, 9 teiks, nu, es neesmu nulles rādītājs, tāpēc izdzēsiet pārējo
sarakstu no šejienes.
Un tāpēc mēģiniet iznīcināt 13.
13 saka: es neesmu nulles rādītājs, tas pats, tas nokārtonoveļ
atbildību uz nākamo.
10 nav nulles rādītājs, 10 satur nulles rādītāju, bet 10 pats par
sevi šobrīd nav nulles rādītājs, tāpēc tas arī uzņemasneuzņemas
atbildību.
Un tagad uzskaitīt punktussaraksts norāda uz turieni, tas tiešām
norādītu uz dažiem — ja man attēlā būtu vairāk vietas, tas norādītu
uz kādu nejaušu vietu, par kuru mēs nezinām, kas tas ir.
Tomēr tas ir nulles rādītājs, saraksts burtiski tagad ir iestatīts kā
nulles vērtības.
Tas rāda tieši tajā sarkanajā lodziņā.
Mēs sasniedzām nulles rādītāju, tāpēc varam apstāties, un viss.
Un tā, ka purpursarkanais rāmis tagad atrodas steka augšdaļā, tas ir
aktīvais rāmis, taču tas ir pabeigts.
Ja esam sasnieguši nulles rādītāju, apstājieties.
Mēs neko nedarām, mēs nevaram atbrīvot nulles rādītāju, mēs
neizmantojām atstarpivietu, un tas ir darītsizdarīts.
Tātad šis funkciju rāmis tiek iznīcināts, un mēs turpinām darbu — mēs
turpinām no vietas, kur mēs to pārtraucām, ar nākamo augstāko, kas ir
šis tumši zilais rāmis.
Tāpēc mēs turpinām tur, kur pārtraucām.
Mēs jau esam izdzēsuši pārējo sarakstu, tāpēc tagad mēs atbrīvosim
pašreizējos mezglus.
Tātad tagad mēs varam atbrīvot šo mezglu, un tagad esam sasnieguši
funkcijas beigas.
Un tā tas funkciju rāmis tiek iznīcināts, un mēs paņemam pie gaiši
zilāsākam izmantot gaiši zilo.
Tā saka — es jau esmu izdarījis — dzēst pārējo sarakstu, tāpēc
atbrīvojiet pašreizējo mezglu.
Un tagad dzeltenais rāmis ir atkal uz kaudzessteka augšpusē.
Un, kā redzat, mēs tagad iznīcinām sarakstu no labās uz kreiso pusi.
Tomēr, kas būtu noticis, ja mēs būtu rīkojušies nepareizi?
Tāpat kā tad, kad mēģinājām pievienot elementu.
Ja mēs sajaucām ķēdi, ja mēs nesavienojām rādītājus pareizajā secībā,
ja mēs tikko atbrīvojām pirmo elementu, ja mēs vienkārši atbrīvojām
saraksta galvgaligalvu, tagad mums nav iespējas atsaukties uz pārējo
sarakstu.
Un tā mēs visu būtu palikuši bāreņiiznīcinājuši, mums būtu tā sauktā
atmiņas noplūde.
Ja atceraties no mūsu video par dinamisko atmiņas piešķiršanu, tas
nav īpaši labi.
Tātad, kā jau teicu, ir vairākas darbības, kas mums ir jāizmanto, lai
efektīvi strādātu ar saistīto sarakstu.
Un jūs, iespējams, pamanījāt, ka es vienu izlaidu, izdzēšot vienu
elementu no saistītā saraksta.
Iemesls, kāpēc es to darīju, ir tāds, ka patiesībā ir diezgan
sarežģīti domāt par to, kā izdzēst vienu elementu no atsevišķi
saistīta saraksta.
Mums ir jāspēj izlaist kaut ko sarakstā, kas nozīmē, ka mēs nonākam
pie punkta — mēs vēlamies dzēst šo mezglu — bet, lai to
padarītuizdarītu un nezaudētu informāciju, mums tas ir jāsavieno.
mezglsšis mezgls ir jāsavieno šeit, šeit.
Tāpēc es, iespējams, izdarīju to nepareizi no vizuālā viedokļa.
Tātad mēs esam sava saraksta sākumā, mēs turpinām, mēs vēlamies dzēst
šo mezglu.
Ja mēs to vienkārši izdzēsīsim, mēs esam pārrāvuši ķēdi.
Šis mezgls šeit attiecas uz visu pārējo, tas satur ķēdi no šī
brīžašejienes uz priekšu.
Tas, kas mums faktiski jādara, kad esam nonākuši līdz šim punktam, ir
jāatkāpjas par vienu un jāsavieno šis mezgls ar šo mezglu, lai mēs
varētu izdzēst vidū esošo.
Taču atsevišķi saistītie saraksti nedod mums iespēju atgriezties
atpakaļ.
Tāpēc mums ir vai nu jāsaglabā divas norādesdivi rādītāji un
jāpārvieto tāstie kā nobīdes vienu aiz otrasotra, vai arī jānokļūst
punktā un pēc tam jānosūta cits rādītājs.
Un, kā redzat, tas var kļūt nedaudz netīrsmazliet sajukt.
Par laimi, mums ir cits veids, kā to atrisināt, runājot par divkārši
saistītiem sarakstiem.
Es esmu Dags Loids, šis ir CS50.