>> [Muusika mängib]
>> DOUG LLOYD: OK, nii et siinkohal muidugi
oleme kaetud palju põhitõdesid C. Me teame palju muutujaid, massiivid,
suunanäitajaks, kõik, mis hea kraam.
Need on kõik omamoodi ehitatud et näha, kui alused,
kuid me saame teha rohkem, eks?
Me võime kombineerida asju koos huvitavaid võimalusi.
>> Ja teeme siis, et alustame Tegevust, mida C annab meile
ja alustada luua oma andmed struktuure kasutades neid hoone
plokid koos midagi teha tõesti väärtuslik, kasulik.
Üks viis, kuidas me saame seda teha on rääkida kogudest.
Nii seni oleme olnud ühte liiki andmeid struktuuri esindavad kogud
sarnaste väärtuste, sarnased väärtused.
See oleks massiivi.
Meil on kogud täisarvud, või kogude tegelased ja nii edasi.
>> Struktuurid on ka omamoodi andmeid struktuur teabe kogumiseks,
kuid see ei ole kogumiseks nagu väärtusi.
Tavaliselt segab erinevat tüüpi andmeid koos sees ühe kasti.
Aga see ei ole iseenesest kasutatakse kett koos
või omavahel ühendada sarnase esemed, nagu massiivi.
Massiivid on suur element otsida, kuid tagasikutsumise
et see on väga raske lisada massiivi,
kui me oleme sisestamist juures päris lõpus, et massiivi.
>> Ja parim näide mul eest, mis on sisestamise omamoodi.
Kui te mäletate meie video paigutamist omamoodi,
seal oli palju kulul kaasatud võttes
kiirenemist elemente ja suunata neid välja viis sobitada midagi
keskele oma valikut.
Massiivid kannatavad ka teise probleem, mis on jäikus.
Kui me kinnitame massiivi, saame ühe tulistas ta.
Me saame öelda, ma tahan Selle elemente.
Võib olla 100, see võib olla 1000, see võib
olla x, kus x on number, et kasutaja andis meile kiire või käsk
line.
>> Aga me ainult saada üks lask, siis me ei saada, siis ütle oh, tegelikult ma
vaja 101 või ma vajasin x pluss 20.
Liiga hilja, me oleme juba tunnistanud massiiv, ja kui me tahame saada 101 või x
pluss 20, meil on kuulutada täiesti erinevat valikut,
kopeerige kõik elemendid massiivi üle, ja siis on meil piisavalt.
Ja mis siis, kui oleme eksinud jälle, mida kui me tegelikult vajame 102 või x pluss 40,
Me ei pea seda tegema jälle.
Nii nad väga paindumatuks saneerimist meie andmeid
aga kui me ühendame koos mõnede põhitõed, et me oleme juba
õppinud viiteid ja struktuure, eriti kasutades dünaamilise mälu
jaotamine malloc, me panna need tükid kokku
luua uusi andmeid structure-- üksikult ahelloendid võiksime say--
mis võimaldab meil kasvada ja kahaneb kogumise väärtused
ja me ei pea mingeid raisatud ruumi.
>> Nii jälle, me nimetame seda ideed, Sellel põhimõttel ahelloend.
Eelkõige selle video me oleme räägime üksikult seotud nimekirja,
ja siis teine ​​video räägime umbes kahekordselt ahelloendid, mis
on lihtsalt variatsioon teema siin.
Aga üksi seotud nimekirja koosneb sõlmed,
sõlmed lihtsalt on abstraktne term-- see on lihtsalt midagi Ma helistan
see on mingi struktuuri, põhimõtteliselt ma olen?
Just kavatse seda nimetada node-- ja selle sõlm on kaks liiget, või kahes valdkonnas.
See on andmeid, tavaliselt täisarv, iseloomu float,
või võib olla mõne muu andmetüübi et olete määratletud tüüpi def.
Ja see sisaldab viit Järgmises sõlme sama tüüpi.
>> Nii et meil on kaks asja sees Selle sõlme, andmete ja osuti
teise sõlme.
Ja kui te hakkate visualiseerida see, mida sa ei mõtle selle peale
nagu kett sõlmed, mis on omavahel ühendatud.
Meil on esimese sõlme, see sisaldab andmeid, ja osuti
Teise sõlme, mis sisaldab andmed ja viit kolmanda sõlme.
Ja nii see on, miks me nimetame seda seotud nimekirja, nad on omavahel ühendatud.
>> Mida see eriline sõlme struktuur välja näeb?
Noh, kui te mäletate meie video määratleda oma tüüpe, tüüpi def,
saame määratleda structure-- ja kirjuta määratleda struktuuri niimoodi.
tyepdef struct sllist, ja siis ma olen kasutades sõna väärtus siin meelevaldselt
kuhu märgitakse andmete tüübi tõesti.
Sa võid edasi täisarv või float, sa oleks võinud mida iganes sa tahad.
See ei piirdu ainult täisarvud, või midagi sellist.
Nii väärtus on lihtsalt suvaline andmete tüüp ja osuti
teise sõlme sama tüüpi.
>> Nüüd, seal on vähe saaki siin määratlemisel struktuur
kui see on ise referentsiaalse struktuuri.
Ma pean ajutise nimi minu struktuur.
Lõpus päeval, kui ma selgelt tahad seda kutsuda
sll sõlme, mis on lõppkokkuvõttes uus nimi osa minu tüübi definitsioon,
aga ma ei saa kasutada sll sõlme keset seda.
Põhjus on selles, ma ei ole loodud tüüp nimega sll sõlme
kuni ma tabanud seda viimast punkti siin.
Kuni selle punkti, ma pean olema Teine võimalus viidata andmete tüübist.
>> Ja see on ise võrdlusandmete tüübist.
See S andmebaasi tüübi kohta struktuur, mis sisaldab andmeid,
ja osuti teise struktuur sama tüüpi.
Nii et ma pean olema võimalik viidata ka See andmetüüp vähemalt ajutiselt,
nii annab see ajutine nimi struct sllist
võimaldab mul siis öelda, et ma tahan kursor teise struct sllist,
struct sllist star, ja seejärel kui olen lõpetanud määratlus,
Ma võin nüüd nimetame seda AN sll sõlme.
>> Nii et miks sa näed seal Ajutise nimi siin
kuid püsiva nimi.
Mõnikord võib näha mõisted struktuuriga,
näiteks, et ei ole ise referentsiaalse, et
ei ole specifier nimi.
See oleks lihtsalt öelda typedef struct, avada lokkis traksidega ja seejärel määratleda.
Aga kui sa oled struct on ise referentsiaalse, nagu see on,
peate määrama Ajutise tüübi nimi.
Aga lõpuks, nüüd et me oleme seda teinud,
saame lihtsalt viidata need sõlmed need üksused,
kui sll sõlmede eesmärkidel ülejäänud seda videot.
>> Kõik õige, et me teame, kuidas luua ahelloend sõlme.
Me teame, kuidas määratleda ahelloend sõlme.
Nüüd, kui me ei kavatse hakata kasutades neid koguda teavet,
seal on paar toimingud oleme on vaja mõista ja töötada.
Me peame teadma, kuidas luua ahelloend välja õhuke õhk.
Kui seal ei ole nimekirjas juba, tahame alustada üks.
Nii et me peame olema võimelised luua ahelloend,
peame ilmselt otsida lingi kaudu nimekirja
leida element ootame.
Me peame suutma sisestada uued asjad nimekirja,
Me tahame, et meie nimekiri saaks kasvada.
Ja täpselt samamoodi, me tahame, et oleks võimalik kustutada asjad meie nimekirjas,
Me tahame, et meie nimekiri saaks kahaneb.
Ja lõpus meie programme, eriti
Kui te mäletate, et me oleme dünaamiliselt eraldada mälu
ehitada need nimekirjad tavaliselt, Me tahame, et vabastada kõik selle mälu
kui me teinud koostööd selle.
Ja seega peame suutma kustutada Kogu seotud nimekirja ühes suuda sööstma.
Nii lähme läbi mõned nendest toimingutest
ja kuidas me võiksime visualiseerida neid, räägib pseudokoodi koodi konkreetselt.
Nii et me tahame luua seotud nimekirja, et äkki me
soovite määratleda funktsiooni Selle prototüüp.
sll sõlme star, luua, ja ma möödaminnes ühes argument, mõned suvalise andmeid
kirjuta uuesti mõne suvalise andmete tüübi.
Aga ma returning-- see funktsioon peaks tagasi mulle pointer, et ühekaupa
ahelloendid sõlme.
Jällegi, me üritame luua ahelloend välja õhuke õhk,
nii et ma vaja viit seda nimekirja, kui ma olen teinud.
>> Millised on etappe siin?
Noh, esimene asi, mida ma olen lähen tegema, on dünaamiliselt
eraldada ruumi uue sõlme.
Jällegi, me luua see välja õhuke õhku, nii et me peame malloc ruumi on.
Ja muidugi kohe pärast me malloc,
me alati veenduge, et meie pointer-- me ei saanud tagasi null.
Sest kui me püüame lugupidamisavaldus nullviida,
me ei kavatse kannatada segfault ja me ei taha seda.
>> Siis me tahame täita väljad, tahame initsialiseerida väärtuse väljal
ja initsialiseerida järgmisele väljale.
Ja siis me tahame mina-- lõpuks, kui funktsiooni prototüüp indicates-- tahame
tagasi osuti kaasa sll sõlme.
Mida teha seda nägema visuaalselt?
Noh, esiteks me ei kavatse dünaamiliselt eraldada ruumi uuele SLL sõlme,
nii et me malloc-- see on piltlikuks
sõlme me lihtsalt loodud.
Ja me veenduge see ei ole null-- sel juhul,
pilt ei oleks näidanud üles, kui ta oli null,
oleksime otsa mälu nii et me oleme hea sinna minna.
Nüüd oleme sammuga C, initsialiseerida sõlmede väärtus valdkonnas.
Noh, mis põhineb selle funktsiooni helistada ma kasutan siin
Tundub, tahan sündis 6, Nii et ma 6 väärtuse valdkonnas.
Nüüd, initsialiseerida järgmisele väljale.
Noh, mida ma kavatsen teha seal, miski kõrval, paremal,
see on ainus asi, mida nimekirjas.
Mis siis järgmine asi nimekirjas?
>> See ei tohiks näidata millelegi, eks.
Seal on midagi olemas, nii et mis on mõiste, mida me teame, et on nothing--
viiteid midagi?
See peaks olema äkki me tahame panna nullviida seal,
ja ma esindavad null pointer kui lihtsalt punane kast
Me ei saa minna kaugemale.
Nagu me näeme veidi hiljem, meil lõpuks ketid
nooli ühendamiseks need sõlmed kokku
aga kui vajutad punane kast, mis on null,
Me ei saa minna kaugemale, see on loendi lõppu.
>> Ja lõpuks, me lihtsalt tahame tagasi kursor selle sõlme.
Nii me nimetame seda uut, ja naaseb uue
seega saab kasutada mis iganes funktsiooni loonud.
Nii et me läheme, oleme loonud üksikult ahelloendid sõlme välja õhuke õhk,
ja nüüd on meil nimekirjas saame töötada.
>> Nüüd oletame, et me juba on suur kett,
ja me tahame, et leida midagi ta.
Ja me tahame funktsioon, mis läheb tagasi õige või vale, sõltuvalt
kas väärtus on olemas, et nimekirja.
Funktsioon prototüübi või deklaratsiooni, et funktsiooni,
tunduda see-- bool leida, ja siis tahame sündis kaks argumenti.
>> Esimene on kursor Esimene osa seotud nimekirja.
See on tegelikult midagi, mida sa tahavad alati jälgida,
ja tegelikult võiks olla midagi, mis sa isegi kasutusele globaalse muutuja.
Kui olete loonud nimekirja, sa alati, alati
soovite jälgida väga Esimene osa nimekirja.
Nii võid pöörduda kõigi teiste elemendid, mida just pärast kett,
ilma, et hoida viiteid tervena iga element.
Teil on vaja ainult jälgida esimene üks, kui nad kõik aheldatud koos.
>> Ja siis teine ​​asi me möödaminnes jälle
on meelevaldselt some-- sõltumata andmete tüübi me oleme
otsin seal on sees loodetavasti üks tippe nimekirja.
Millised on sammud?
Noh, esimene asi, mida me teeme on loome läbivaid pointer
osutades nimekirjad pea.
Noh, miks me seda teeme, oleme juba on osuti nimekirjad pea,
miks me lihtsalt ei liigu, et ühe ringi?
Noh, nagu ma ütlesin, see on tõesti meie jaoks oluline
alati hoida silma peal Kõige esimene element nimekirjas.
Ja nii see on tegelikult parem luua duplikaadi, et
ja kasutada, et liikuda, et me kunagi kogemata minema, või me alati
on osuti mingil hetkel, et on paremale esimese osa nimekirja.
Nii et see on parem luua teine, et me kasutame liikuda.
>> Siis me lihtsalt võrrelda, kas väärtus põllul, et sõlm
on see, mida me otsime, ja kui see on ei, me lihtsalt liikuda järgmisele sõlme.
Ja me peame seda tehes Üle ja üle ja üle,
kuni me kas leida element või me tabanud
null-- oleme jõudnud nimekirja ja seda seal ei ole.
See peaks loodetavasti häirekella teile lihtsalt lineaarne otsing,
me lihtsalt imitatsiooniga seda ühekaupa seotud nimekirja struktuur
selle asemel massiivi seda teha.
>> Nii et siin on näide ühekaupa seotud nimekirja.
See üks koosneb viis tippu, ja meil on
kursor juht nimekiri, mida nimetatakse nimekirja.
Esimene asi, mida me tahame teha, on uuesti luua, et läbipääsusüsteemid pointer.
Nii et meil on nüüd kaks viiteid Sel hetkel, et sama asi.
>> Nüüd märgata ka siin, ma ei pea malloc tahes ruumi matk.
Ma ei öelnud trav võrdub malloc midagi, mis sõlme juba olemas,
et ruumi mälu on juba olemas.
Nii ma olen tegelikult seda on luua uus kursor ta.
Ma ei mallocing veel ruumi, lihtsalt nüüd kaks viiteid
osutades sama asi.
>> Nii on 2, mida ma otsin?
Noh, ei, nii et selle asemel ma olen kavatse minna järgmise üks.
Nii et põhimõtteliselt ma ütleksin, trav võrdub trav kõrval.
Kas 3, mida ma otsin, ei.
Nii et ma jätkuvalt minna läbi, kuni lõpuks
saada 6, mis on see, mida ma otsin jaoks põhineb funktsioon kõne
Mul on tipus seal, ja nii ma olen teinud.
>> Nüüd, aga kui element ma olen otsin ei ole nimekirjas,
on see ikka läheb tööle?
Noh, märkate, et nimekiri siin on delikaatselt erinevad,
ja see on veel üks asi, mis on tähtis ahelloendid,
sa ei pea säilitada neid kindlas järjekorras.
Saate, kui soovite, kuid olete juba märganud
et me ei jälgimine Mis number element oleme.
>> Ja see on omamoodi üks kaubanduse, et me on lingitud nimekirja salmid massiivid,
on see meil ei ole random access enam.
Me ei saa öelda, ma tahan minna 0. element,
või 6. osa minu rida, mis ma teha saan massiivi.
Ma ei saa öelda, et ma tahan minna 0. element, või 6. element,
või 25. osa minu ahelloendid, pole indeks nendega.
Ja nii see ei ole tegelikult küsimus Kui me säilitame oma nimekirja järjekorras.
Kui soovite teid Kindlasti saab, kuid seal on
mingit põhjust, miks nad peavad säilitatakse suvalises järjekorras.
Nii jälle, proovime ja leida 6 selles nimekirjas.
Noh, hakkame juures Alguses me ei leia 6,
ja siis jätkame ei leia 6, kuni me lõpuks saada siin.
Nii kohe trav punkte sõlme sisaldab 8 ja kuus ei ole olemas.
>> Nii et järgmine samm oleks minna järgmisele pointer,
nii öelda trav võrdub trav kõrval.
Noh, trav kõrval, näitab punane kast seal on null.
Nii et kuhugi minna, ja et selles kohas
võib järeldada, et oleme jõudnud lõppu ahelloendid,
ja 6 ei ole olemas.
Ja see oleks tagastatud vale sel juhul.
>> OK, kuidas me lisada uusi sõlme sisse ahelloendid?
Nii oleme suutnud luua ahelloend välja kuhugi,
kuid me ilmselt tahad ehitada kett ja ei
luua hunnik eraldi nimekirja.
Me tahame olla üks nimekiri, mis on hunnik tippe see,
ei kamp nimekirjad ühe sõlme.
Nii et me ei saa lihtsalt hoida abil Loo funktsiooni me eelnevalt defineeritud, nüüd
soovite sisestada ümber nimekirja, mis on juba olemas.
>> Nii Sel juhul me läheme läbida kaks argumenti,
kursor juht, et seotud nimekirja, mida tahame lisada.
Jällegi, see on põhjus, miks see nii oluline, et me alati
jälgida, sest see on ainus viis, kuidas me tõesti
on viidata kogu nimekirja on lihtsalt kursor esimene element.
Nii et me tahame edasi oma kursor, et esimene element,
ja mis iganes väärtust me tahan lisada nimekirja.
Ja lõpuks see funktsioon läheb tagasi pointer
Uue juhi ahelloend.
>> Millised on etappe siin?
Noh, nagu on luua, peame dünaamiliselt eraldada
ruumi uue sõlme, ja kontrollige, Kindlasti me ei otsa mälu, taas,
sest me kasutame malloc.
Siis me tahame asustada ja paigaldage sõlme,
nii panna number, mida iganes val on võetud sõlme.
Tahame lisada sõlme alguses ahelloendid.
>> Seal on põhjus, et ma tahad seda teha, ja see
Võib-olla tasub võtta teist Video esitamise peatamiseks siin
ja mõelda, miks ma ei tahaks sisestada alguses lingitud
nimekirja.
Jällegi, ma mainisin et see ei ole tegelikult
oluline, kui me seda säilitada mis tahes Selleks, et äkki see aimugi.
Ja sa nägid, mis juhtuks, kui me tahtsin mina-- või lihtsalt teist
tagasi, kui me ei kavatse läbi otsida teid
võis näha, milline võiks siis, kui me püüdsime
sisestada lõpus nimekirjast.
Sest me ei ole kursor nimekirja lõppu.
>> Nii et põhjus, miks ma tahan lisada alguses,
on, sest ma ei saa seda teha kohe.
Mul on osuti alguses, ja me näeme seda visuaalset teine.
Aga kui ma tahan lisada lõpus, Ma pean alustama algusest,
läbida kõik viis lõpus ja seejärel pühitakse seda.
Nii see tähendaks, et sisestades lõpus nimekiri
muutuks o n operatsioon, minnes tagasi
meie arutelu arvutuslik keerukus.
Oleks saanud o n operatsioon, kus kui nimekiri sai suurem ja suurem,
ja suurem, siis see muutub üha raskem tack midagi
kohta lõpus.
Aga see on alati väga lihtne tack midagi alguses,
sa oled alati alguses.
>> Ja me näeme visuaalne seda uuesti.
Ja siis, kui me teinud, kui oleme sisestatud uus sõlm,
tahame naasta oma viit uue juhi ahelloend, mis
kuna me sisestamist juures hakanud, on tegelikult
kursor sõlme me lihtsalt loodud.
Teeme seda visualiseerida, sest ma arvan, et see aitame.
>> Nii et siin on meie nimekirjas, siis see koosneb neli elementi, sõlm, mis sisaldavad 15,
mis viitab sõlme sisaldab 9, mille
osutab sõlme sisaldavad 13, mis viitab sõlme sisaldav
10, millel on null pointer selle kõrval pointer
nii et see lõpuks nimekirja.
Nii et me tahame lisada uus sõlm väärtusega 12
alguses käesoleva nimekirja, mida me teeme?
Noh, esiteks me malloc ruumi sõlme, ja siis me paneme 12 seal.
>> Nüüd oleme jõudnud otsuse punkti, eks?
Meil on paar viiteid, et võiksime
liikuda, millest üks peaks me liigume esimesena?
Kas me peaksime tegema 12 punkti uus juht list--
või vabandage, me peaksime tegema 12 viitavad vana juht nimekirja?
Või peaks ütlema, et Avalda oma kuulutused algab kell 12.
Seal on vahet seal, ja me vaatame
kell, mis juhtub nii teine.
>> Aga see toob kaasa suur teema sidebar,
mis seisneb selles, et üks trickiest asju ahelloendid
on korraldada viiteid õiges järjekorras.
Kui liigutad asju rikkis, võid sattuda kogemata
orvustumine ülejäänud nimekirja.
Ja siin on näide sellest.
Nii lähme mõttega of-- noh, me oleme lihtsalt loodud 12.
Me teame, 12 läheb uus juht nimekirja,
ja miks me lihtsalt ei liigu nimekirja kursorit juhtida seal.
>> OK, nii et see on hea.
Nüüd, kus ei 12. Järgmine küsimus?
Ma mõtlen, et visuaalselt näeme et see toob välja 15,
kui inimesel on tõesti meile selge.
Kuidas arvuti tea?
Meil ei ole midagi osutades 15 enam, eks?
>> Me oleme kaotanud võime viidata 15.
Me ei saa öelda uue noolt võrdsete midagi, seal on midagi seal.
Tegelikult oleme orvuks Ülejäänud nimekirja
tehes oleme kogemata katki kett.
Ja me kindlasti ei taha seda teha.
>> Nii lähme tagasi ja proovige seda uuesti.
Võib-olla õige asi, mida teha on seatud 12 järgmise pointer
vana juht nimekirja esimene, siis saame liikuda nimekirja üle.
Ja tegelikult, et on õiges järjekorras, et me
pea järgima, kui me oleme töötavad üksi seotud nimekirja.
Oleme alati tahtnud ühendada uus element nimekirja,
enne võtame sellist oluline samm muutmise
kus juht ahelloendid on.
Jällegi, see on selline oluline asi, me ei taha kaotada jälgida seda.
>> Nii et me tahame veenduda, et kõik on aheldatud koos,
Enne astume, et osuti.
Ja nii see oleks õiges järjekorras, mis on ühendada 12 loetellu,
siis öelda, et nimekiri algab 12.
Kui me ütlesime nimekirja algab kell 12 ja Seejärel üritas ühendada 12 nimekirja,
me oleme juba näinud, mis juhtub.
Me kaotame nimekirja kogemata.
>> OK, nii et üks asi veel rääkida.
Mis siis, kui me tahame vabaneda kogu ahelloendid korraga?
Jällegi, me mallocing kõik selle ruumi, ja nii me
peame vabastama seda, kui me teinud.
Nüüd tahame kustutada Kogu seotud nimekirja.
Noh, mida me tahame teha?
>> Kui oleme jõudnud nullviida, me tahad lõpetada, muidu lihtsalt kustutada
Ülejäänud nimekirjas ja seejärel vabastada mind.
Kustuta ülejäänud nimekirja, ja siis vabastada aktiivse sõlme.
Mida see tunduda, Mis tehnikat on rääkisime
umbes eelnevalt Kas see tunduda?
Kustuta kõik teised, siis tagasi tulla ja kustutada mind.
>> See on recursion, oleme teinud Probleem natuke väiksem,
me ütleme kustutada kõik muud, siis saab kustutada mind.
Ja edasi mööda teed, et sõlm ütlevad, kustutada kõik teised.
Aga lõpuks me jõuame kus nimekirjas on null,
ja see on meie tugipunkt.
>> Võtame pilk sellele, ja kuidas see võib töötada.
Nii et siin on meie nimekirjas, see on sama List just rääkisime,
ja seal on sammud.
Seal on palju teksti siin, aga loodetavasti visualiseerimine aitab.
>> Nii me have-- ja ma ka tõmmata up meie stack raamid illustratsioon
meie video kõne korstnad, ja loodetavasti see kõik
koos näitan sulle, mis toimub.
Nii et siin on meie pseudokoodi koodi.
Kui jõuame null pointer, peatus, muidu
kustutada Ülejäänud nimekiri, siis tasuta aktiivse sõlme.
Nii kohe, list-- kursorit, et me oleme
kulgeb hävitada punkte 12.
12 ei ole nullviida, nii et me oleme kustutamas ülejäänud nimekirja.
>> Mis on kustutamata Ülejäänud meist kaasatud?
Well, see tähendab, tehes helistada hävitada, öeldes
et 15 on alguses Ülejäänud nimekiri tahame hävitada.
Ja nii kõne hävitada 12 on selline ootele.
See on külmunud seal, oodates helistada hävitada 15, et lõpetada oma töö.
>> Noh, 15 ei ole nullviida ja nii see läheb öelda, on kõik korras,
noh, kustutage ülejäänud nimekirja.
Ülejäänud nimekirjas algab kell 9, ja nii me lihtsalt
oodake, kuni sa kustutada kõik, mis kraami, siis tagasi tulla ja kustutada mind.
Noh 9 läheb öelda, hästi, Ma ei ole nullviida,
nii kustutada ülejäänud nimekirja siit.
Ja nii proovida ja hävitada 13.
13 ütleb, ma ei ole null pointer, Sama asi, see paneb selle.
10 ei ole null pointer, 10 sisaldab nullviida,
kuid 10 ei ole ise nullviida kohe,
ja nii see paneb selle ka.
>> Ja nüüd tuuakse loetelus olemas, siis tõesti viitaks some--
kui mul oleks rohkem ruumi pildi, see viitaks mõne juhusliku ruumi
et me ei tea, mis see on.
See on nullviida kuigi nimekirja on sõna otseses mõttes nüüdsest on väärtused null.
See on suunatud paremale sees, et punane kast.
Jõudsime nullviida, nii Me ei saa peatada, ja ongi kõik.
>> Ja nii, et lilla raam on now-- juures peal stack-- see on aktiivses vaates
kuid ta on teinud.
Kui oleme jõudnud nullviida, peatus.
Me ei saa midagi teha, siis ei saa vabastada nullviida,
Me ei malloc tahes ruumi, ja nii me teinud.
Nii et funktsioon raam on hävinud, ja me
resume-- me sealt, kus me lahkusime maha järgmise suurima üks, mis
see tumesinine raami siin.
Nii me kiirenemist õigus, kus pooleli jäime.
Me kustutatakse ülejäänud nimekiri on juba, nii et nüüd me oleme
läheb vabalt praeguse sõlmed.
Nüüd saame vabastada selle sõlme ja nüüd oleme jõudnud funktsiooni.
Ja nii, et funktsiooni raam on hävinud, ja me kiirenemist helesinine üks.
>> Seega says-- Olen juba done-- kustutada ülejäänud nimekirjas, siis
tasuta aktiivse sõlme.
Ja nüüd kollane raam on Tagasi peal virnas.
Ja nii nagu näete, me oleme nüüd hävitades nimekirja paremalt vasakule.
>> Mis oleks juhtunud, kuigi kui me teinud asju valesti?
Just nagu siis, kui me püüdsime lisada element.
Kui me segi kett, kui Me ei ühenda viiteid
õiges järjekorras, kui me lihtsalt vabaks esimene osa,
kui me lihtsalt vabastas juht nimekirja, nüüd
kuidagi viidata Ülejäänud nimekirjas.
Ja nii me oleks orvuks kõike,
oleks meil olnud, mis on nimetatakse Mälulekke.
Kui te mäletate meie video dünaamilise mälu eraldamise,
see ei ole väga hea.
>> Nii nagu ma ütlesin, On mitmeid operatsioone
et me peame kasutama tööd koos seotud nimekirja tõhusalt.
Ja sa ehk märganud ma jätta üks, kustutada ühe elemendi lingitud
nimekirja.
Põhjus, miks ma seda tegin see on tegelikult omamoodi
keeruline mõelda, kuidas kustutada ühe elemendi ühekaupa
seotud nimekirja.
Me peame olema võimelised vahele üle midagi nimekirjas, mis
tähendab, et saame kaasa point-- me soovite kustutada selle node--
vaid selleks, et teha seda nii meil ei kaota andmeid,
meil on vaja ühendada see sõlme siin, siin.
>> Nii et ma vist tegin seda valesti et visuaalselt.
Nii et me alguses oma nimekirja, me protsesside raames,
tahame kustutada sõlme.
Kui me lihtsalt kustutada, oleme murtud ketti.
See sõlm siin viitab kõik muu,
see sisaldab kett Siitmaalt.
>> Mida me peame tegema tegelikult pärast saame selle punkti,
on meil vaja astuda sammu tagasi üks, ja ühendada selle sõlme üle selle sõlme,
nii et me saame siis kustuta Ühest keskel.
Aga üksi ahelloendid ei anda meile võimalus minna tagasi.
Seega peame kas hoida kaks suunanäitajaks, ja neid liigutada
omamoodi off samm, üks taga muu kui me minna, või saada punkti
ja siis saadab teise pointer kaudu.
Ja nagu näete, see võib natuke segane.
Õnneks on meil muul viisil lahendada, et
kui me räägime kahekordselt seotud nimekirju.
>> Ma olen Doug Lloyd, see on CS50.