[Muzikos grojimo] 

Doug LLOYD: Gerai, kad ne Šis punktas yra, žinoma, mes apėmė nuo C pagrindai daug Mes žinome apie kintamuosius, masyvus daug, patarimų, visi, kad gerų dalykų. Tie visi tarsi pastatytas Norėdami matyti kaip pagrindus, bet mes galime padaryti daugiau, tiesa? Mes galime derinti dalykus kartu įdomių būdų. 

Ir taip darykime, kad pradėkime išsišakoti kas C mums suteikia, ir pradėti kurti savo duomenis struktūros, naudojant šiuos pastatą blokai kartu kažką daryti tikrai vertinga, naudinga. Vienas iš būdų mes galime tai padaryti kalbėti apie kolekcijas. Taigi iki šiol mes turėjome vienos rūšies duomenis struktūra kolekcijas atstovaujanti panašaus vertybes, panašias vertybes. Tai būtų masyvas. Mes turime kolekcijas skaičiais arba kolekcijos simbolių ir pan. 

Konstrukcijos taip pat tarsi duomenis struktūra rinkti informaciją, bet tai ne rinkti, kaip vertybes. Ji paprastai susimaišo įvairių duomenų tipų kartu viduje viename langelyje. Bet tai ne pats naudojamas grandinės kartu arba prijunkite kartu panašus elementai, kaip masyvą. Masyvai yra puikus elementas ieškoti, bet Prisiminkite kad tai labai sunku įterpti į masyvą, nebent mes įdėti ne galo tos masyvo. 

Ir geriausias pavyzdys Turiu už tai įterpimo rūšiuoti. Jei prisimenate mūsų vaizdo intarpų rūšiuoti, ten buvo daug sąskaita dalyvauja turintys pasiimti elementus ir juos perkelti iš kelio, kad tilptų kažką į centrą savo masyvo. Masyvai taip pat kenčia nuo kito problema, kuri yra nelanksti. Kai mes pareiškiame masyvą, mes gauname vieną kadrą į jį. Mes gauname pasakyti, aš noriu tai daug elementų. Gali būti 100, tai gali būti 1,000, tai gali būti x, kai x yra skaičius, kad vartotojo davė mums ne raginimas arba komandą linija. 

Bet mes tik vieną fotografiją tai, mes negaunu sakykite oh, iš tikrųjų aš reikia 101, ar man reikia x + 20. Per vėlu, mes jau paskelbė masyvas, ir jei mes norime gauti 101 arba X plius 20, mes turime pripažinti visiškai skirtingas masyvas, nukopijuoti visus masyvo elementus daugiau, ir tada mes turime pakankamai. O kas, jei mes neteisūs vėl, ką jei mes iš tikrųjų reikia 102, arba X + 40, mes turime tai padaryti ir vėl. Taigi jie labai nelankstus už dydį mūsų duomenis bet jei mes deriname kartu kai iš pagrindų, kad mes jau ve sužinojo apie rodykles ir struktūrų, ypač naudojant dinaminį atminties paskirstymas su malloc, mes galite įdėti šiuos gabalus kartu Norėdami sukurti naują duomenų structure-- A pavieniui susiję sąrašą galime say-- kuri leidžia mums augti ir trauktis vertybių kolekciją ir mes Neturime švaistomi erdvę. 

Taigi dar kartą, mes vadiname šią idėją, ši sąvoka, susijusiantrosios sąrašas. Visų pirma, šiame video mes kalbame apie vieną susietą sąrašą ir tada kitą vaizdo kalbėsimės apie dvigubai susiję sąrašus, kurie yra tik tam tikra tema čia variacija. Bet atskirai susijusi sąrašas yra sudaryta iš mazgų, mazgai tiesiog yra abstrakti term-- tai tik ką aš skambinti tai yra natūra struktūra, iš esmės, aš? Tiesiog ketinate jį vadiname node-- ir tai mazgas turi du nariai arba du laukus. Jis turi duomenis, paprastai yra sveikasis skaičius, simbolis plūdė, arba gali būti kai kurių kitų duomenų tipas kad jūs apibrėžti tipo def. Ir tai yra žymeklį į kita tos pačios rūšies mazgas. 

Taigi mes turime du dalykus viduje Tai mazgas, duomenų ir rodyklė į kitą mazge. Ir jei jums pradėti vizualizuoti tai, ką galima galvoti apie tai kaip mazgų grandinėje, kad yra tarpusavyje sujungtos. Mes turime pirmąjį mazgą, jį yra duomenų, ir rodyklė į antrąjį mazgas, kuriame yra duomenų, ir rodyklė į trečią mazge. Ir taip, tai kodėl mes tai vadiname susiję sąrašas, jie tarpusavyje susiję. 

Ką tai ypatinga mazgas struktūra atrodo? Na, jei jūs prisimenate iš mūsų vaizdo apibrėžti pasirinktinį tipus, su tipo def, mes galime apibrėžti structure-- ir įrašykite apibrėžti struktūrą, kaip šis. tyepdef struct sllist, tada aš naudojant žodžio vertė čia savavališkai nurodyti visus duomenų tipą tikrai. Jūs galite perduoti sveikasis skaičius arba plūdės, galite turėti viską, ką nori. Tai ne tik tik sveikieji skaičiai, ar ko nors panašaus, kad. Taigi vertė yra tik sutartinis duomenų tipas, ir tada rodyklė į kitą to paties tipo mazge. 

Dabar, ten šiek tiek laimikis čia su apibrėžti struktūrą kai jis savarankiškai referuoto struktūra. Aš turėti laikinas vardas mano struktūrą. Pasibaigus dieną aš pabaigos aiškiai norite jį pavadinti SLL mazgas, tai galiausiai nauja pavadinimas dalį mano tipo apibrėžimą, bet aš negaliu naudoti SLL mazgas viduryje tai. Priežastis yra, aš ne sukūrė tipas vadinamas SLL mazgas kol aš paspauskite šį galutinį tašką čia. Iki to momento, aš turėti Kitas būdas kreiptis į šį duomenų tipą. 

Ir tai yra savaime referuoto duomenų tipas. Tai, s duomenų tipą, turinti struktūra, kuri yra duomenų, ir rodyklė į kitą struktūra yra tokio paties tipo. Taigi, aš reikia, kad būtų galima kreiptis į ši duomenų tipas bent laikinai, taip suteikiant jam laikina pavadinimas struct sllist leidžia man tada pasakyti, kad aš noriu žymiklį į kitą struct sllist, konstrukto sllist žvaigždė, ir tada Po Aš baigė apibrėžimą, Aš dabar gali skambinti šio tipo SLL mazgas. 

Štai kodėl jūs matote ten laikinas vardas čia bet nuolatinis vardas čia. Kartais jūs galite pamatyti apibrėžimai struktūros, kad, pavyzdžiui, yra ne savarankiškai referuoto, kad neturiu specifikatorius vardą čia. Būtų tiesiog pasakyti Typedef konstrukto, atidaryti garbanotas petnešomis ir tada ją apibrėžti. Bet jei jūs konstrukto yra savaime referentiški, kaip tai vienas, Jums reikia nurodyti laikinas tipo pavadinimą. Bet galiausiai, dabar kad mes padarėme tai, mes galime tik nuoroda į Šie mazgai, tie vienetai, kaip SLL mazgų tikslais iš šio vaizdo poilsio. 

Gerai, kad mes žinome, kaip sukurti susietą sąrašą mazgas. Mes žinome, kaip apibrėžti susijusiantrosios sąrašas mazgas. Dabar, jei mes ketiname pradėti naudojant juos surinkti informaciją, ten operacijų pora mes reikia suprasti ir dirbti. Mums reikia žinoti, kaip sukurti susijusiantrosios sąrašas iš plonos oro. Jei nėra sąraše jau, norime pradėti vieną. Taigi mums reikia, kad būtų galima sukurti susietą sąrašą turime tikriausiai paiešką per nuorodą sąrašo rasti elementą mes ieškome. Turime, kad būtų galima įterpti naujų dalykų į sąrašą, norime, kad mūsų sąrašas, kad būtų galima augti. Ir panašiai, norime, kad būtų galima ištrinti dalykų iš mūsų sąrašo, mes norime, kad mūsų sąrašas, kad būtų galima trauktis. Ir pabaigoje mūsų programos, ypač Jei prisimenate, kad mes dinamiškai paskirstyti atmintį statyti šiuos sąrašus paprastai, norime atlaisvinti visus, kad atminties kai mes baigsime dirbti su juo. Ir todėl mes turime gebėti ištrinti Visa susijusi sąrašas viena nesugeba smigimas. Taigi eikime per kai kurie iš šių operacijų ir kaip mes galime vizualizuoti juos, kalbėti Pseudocode kodas specialiai. Taigi, mes norime sukurti susiję sąrašą, todėl galbūt mes nori apibrėžti funkciją su šiuo prototipu. SLL mazgas žvaigždė, kurti, ir aš artimųjų vienoje argumentas, kai savavališkai duomenys įrašykite vėl, kai kurių savavališkai duomenų tipą. Bet aš returning-- šią funkciją turėtų grįžti į mane rodyklę, iki A pavieniui susiję sąrašas mazgas. Vėlgi, mes bandome sukurti susijusiantrosios sąrašas iš plonos oro, todėl man reikia rodyklę į tas sąrašas, kai aš padariau. 

Taigi, kas yra žingsniai čia dalyvauja? Na, aš pirmas dalykas, tikiu, ketina daryti dinamiškai skirti vietos naują mazge. Vėlgi, mes jį kurti iš plonos oro, todėl turime malloc erdvėje už jį. Ir, žinoma, iš karto kai mes malloc, mes visada įsitikinkite, kad mūsų pointer-- mes ne grįžti null. Nes jei mes stengiamės ir Gerokai null žymeklį, mes ketiname patirti segfault ir mes nenorime, kad. 

Tada norime užpildyti lauką, mes norime inicijuoti vertės lauką inicijuoti ir kitą lauką. Ir tada mes norime to-- galiausiai kaip funkcija prototipas indicates-- norime grįžti žymiklį į SLL mazgas. Taigi, kas daro šį atrodyti vizualiai? Na, visų pirma mes ketiname dinamiškai skirti vietos naują SLL mazgas, todėl mes malloc-- tai vaizdinis mazgas, mes ką tik sukūrėte. Ir mes įsitikinkite, kad tai ne null-- šiuo atveju, vaizdas nebūtų parodyta iki, jei jis buvo niekinis, būtume paleisti iš atminties, todėl mes gerai ten. Taigi, dabar mes apie dėti C, inicijuoti mazgai vertės lauką. Na, remiantis šia funkcija skambinti Aš naudoju čia atrodo noriu praeiti 6, todėl aš 6 į vertės lauką. Dabar, inicijuoti kitą lauką. Na, ką aš ketinu ten daryti, nėra nieko šalia, tiesa, tai yra vienintelis dalykas, į sąrašą. Taigi, kas yra kitas dalykas, sąraše? 

Jis neturėtų ko nors, kas, tiesa. Nėra nieko kito ten, kad kas sąvoka mes žinome, kad tai nothing-- rodykles į nieką? Ji turėtų būti gal mes nori įdėti null žymeklį ten, ir aš atstovauti null žymiklį, kaip tik raudoną langelį, mes negalime eiti toliau. Kaip matysime truputį vėliau, turėsime galiausiai grandines strėlės prijungti šie mazgai kartu, bet kai paspausite raudona dėžutė, tai niekinis, mes negalime eiti toliau, tai iš sąrašo gale. 

Ir galiausiai, mes tiesiog norime grįžti žymiklį į šį mazgą. Taigi mes jį vadiname naujas, ir grįš naujo todėl jis gali būti naudojamas kokia funkcija jis sukurtas. Taigi mes einame, Sukūrėme atskirai susiję sąrašas mazgas iš plonos oro, ir dabar mes turime sąrašą galime dirbti. 

Dabar, tarkime, mes jau turime didelę grandinę, ir mes norime, kad rasti kažką į jį. Ir mes norime funkciją, kas vyksta grįžti true arba false, priklausomai nuo nuo to, ar tai yra, vertės egzistuoja tame sąraše. Funkcija prototipas, arba deklaracija šią funkciją, gali atrodyti this-- bool Rasti, tada mes norime perduoti dviem argumentais. 

Pirmoji yra rodyklė į Pirmasis elementas susijęs sąrašą. Tai tikrai kažkas jums visada nori sekti, ir iš tikrųjų gali būti kažkas, kad Jūs netgi atsižvelgiant į pasaulinį kintamąjį. Sukūrę sąrašą Jūs visada, visada nori sekti labai pirmasis elementas sąrašo. Tokiu būdu jūs galite kreiptis į visus kitus elementai, tiesiog po grandinėje, nereikalaujant išlaikyti patarimų nepažeistas į kiekvieną elementą. Jums tik reikia sekti pirmas viena, jei jie visi grandinines kartu. 

Ir tada antras dalykas mes artimųjų vėl yra savavališkai some-- kokia duomenų tipas mes ieško ten yra viduje tikiuosi viena iš sąrašo mazgų. Taigi, kas yra žingsniai? Na, pirmas dalykas, kurį mes darome, yra mes sukurti horizontalų žymiklį nukreipta į sąrašus galvos. Na, kodėl mes galime padaryti, kad mes jau turėti žymiklį į sąrašus galvos, kodėl ne mes tiesiog perkelti, kad vienas aplink? Na, kaip aš ką tik pasakė, tai tikrai svarbu mums visada sekti labai pirmasis elementas į sąrašą. Ir taip tai tikrai geriau sukurti, kad dublikatą, ir naudoti, kad judėti, todėl mes niekada netyčia tolti arba mes visada turi tam tikru momentu, kuris yra žymiklį tiesiai ant pirmojo elemento sąrašo. Taigi, tai geriau sukurti antrasis, kad mes naudoti judėti. 

Tada mes tiesiog palyginti, ar vertė laukas tuo mazgu yra tai, ką mes ieškome, ir jei tai ne, mes tiesiog perkelti į kitą mazgą. Ir mes nuolat daryti daugiau, ir daugiau, ir daugiau, kol mes arba susirasti elementas, arba mes hit null-- mes pasiekė pabaigą iš sąraše ir jis nėra. Tai turėtų tikiuosi žiedas varpas Jums kaip tik tiesinis paieška, mes tiesiog atkartoti jį atskirai susijusi sąrašas struktūra o ne naudojant masyvą tai padaryti. 

Taigi čia pavyzdys, atskirai susijusi sąrašas. Tai vienas susideda iš penki mazgai, ir mes turime rodyklė į galvą sąrašas, kuris yra vadinamas, sąrašą. Pirmas dalykas, mes norime padaryti, tai vėl sukurti, kad Sankryþos žymeklį. Taigi dabar turime dvi rodykles kad taškas tą patį. 

Dabar, pastebėsite, čia pat, aš ne turi malloc jokios erdvės Trav. Aš nesakiau Trav lygus malloc kažkas, kad mazgas jau egzistuoja, kad vietos atmintyje jau egzistuoja. Taigi, visi aš iš tikrųjų darote, yra sukurti kitą žymiklį į jį. Nesu mallocing papildomas Erdvė, tik dabar dvi rodykles nukreipta į tą patį. 

Taigi yra 2 ką aš ieškote? Na, ne, todėl vietoj aš ketina pereiti prie kito. Taigi, iš esmės sakyčiau, Trav lygus Trav šalia. Ar 3, ką aš ieškote, nėra. Taigi, aš ir toliau eiti per, kol galiausiai gauti iki 6 o tai, ką aš ieškote už remiantis skambinimo funkcijos Aš viršuje ten, ir todėl aš padaryti. 

Dabar, ką daryti, jei elementas aš ieško nėra sąraše, jis vis dar ketina dirbti? Na, pastebėsite, kad sąrašas čia yra subtiliai skiriasi, ir tai yra dar vienas dalykas, kad svarbus susijusių sąrašus, Jūs neturite išsaugoti jiems kokia nors ypatinga tvarka. Jūs galite, jei norite, bet jums gali jau pastebėjau kad mes ne sekti kokiu numeriu elementas mes esame. 

Ir tai tarsi viena prekybos, kad mes turi su susietą sąrašą eil masyvai, jis neturime laisvosios kreipties nebėra. Mes negalime tiesiog pasakyti, aš noriu eiti į 0th elementas, arba 6-oji elementas mano masyvas, kurį galiu padaryti masyvą. Aš negaliu pasakyti, aš noriu eiti į 0. elementas, arba 6. elementas, arba 25 elementas mano susietą sąrašą nėra rodiklis susijęs su jais. Ir todėl jis nėra iš tikrųjų klausimas jei mes išsaugoti mūsų sąrašą tvarka. Jei norite jumis tikrai gali, bet ten jokios priežasties, kodėl jiems reikia būti išsaugota bet kokia tvarka. Taigi dar kartą, pabandykime ir rasti 6 Šiame sąraše. Na, mes pradedame ne pradedant, mes negalime rasti 6, ir tada mes ir toliau neranda 6, kol mes pagaliau gauti čia. Taigi dabar Trav atkreipia dėmesį į mazgą yra 8, ir šešių yra ne ten. 

Taigi kitas žingsnis būtų eiti į kitą rodyklė, Taigi sako, Trav lygus Trav šalia. Na, Trav šalia, nurodomas raudona dėžutė ten, yra niekinis. Taigi ten niekur kitur eiti, ir kad šiuo metu galime daryti išvadą, kad mes pasiekėme linkowanego sąrašo pabaigoje, ir 6 yra ne ten. Ir tai būtų grąžintas klaidinga ir šiuo atveju. 

Gerai, kaip mes įterpti naują mazgas į susietą sąrašą? Taigi mums pavyko sukurti susijusiantrosios sąrašas iš niekur, bet mes tikriausiai norėsite statyti grandinę, o ne sukurti atskirus sąrašus krūva. Mes norime turėti vieną sąrašą, turi mazgų jį krūva, nėra sąrašą krūva su vienu mazge. Taigi, mes galime ne tik išlaikyti naudojant Sukurti funkcija mes apibrėžta anksčiau, dabar mes norite įterpti į "A sąrašą, kuris jau egzistuoja. 

Taigi šiuo atveju, mes ketiname perduoti dviem argumentais, kad sprendžiamas, kad galvos žymeklis susiję sąrašą, kad mes norime pridėti prie. Vėlgi, tai kodėl jis toks Svarbu, kad mes visada sekti juo, nes tai vienintelis būdas, kuriuo mes tikrai turi kreiptis į visas sąrašas tiesiog rodykle pirmojo elemento. Taigi mes norime perduoti A žymiklį į tą pirmąjį elementą, ir kokia vertė mes norite įtraukti į sąrašą. Ir galiausiai ši funkcija ketina grįžti rodyklę į naują galvos susietą sąrašą. 

Kokie yra žingsniai čia dalyvauja? Na, tiesiog kaip su kurti, turime dinamiškai paskirstyti erdvė naują mazgą, ir patikrinkite, Ar tikrai mes neturime paleisti iš atminties, ir vėl, nes mes naudojame malloc. Tada norime užpildyti ir įdėkite mazgas, kad įdėti skaičių, nepriklausomai nuo Val, į mazge. Mes norime įterpti mazgas ne linkowanego sąrašo pradžioje. 

Yra priežastis, kad aš nori tai padaryti, ir jis gali būti verta sekundę pristabdyti vaizdo įrašą čia ir manau, apie tai, kodėl aš noriu įdėkite į susieto pradžioje sąrašas. Vėlgi, aš minėjau anksčiau kad tai tikrai ne Nesvarbu, jei mes ją išsaugoti bet tvarką, kad gal tai yra raktas. Ir matėte, kas nutiktų, jei mes norėjau to-- arba tik sekundę prieš kai mes einasi per paiešką galite gali pamatyti, ką gali atsitiktų, jei mes stengiamės įterpti tuo sąrašo pabaigoje. Kadangi mes neturite rodyklę į sąrašo pabaigoje. 

Taigi dėl to, kad aš noriu įterpti pradžioje, yra todėl, kad aš galiu tai padaryti iš karto. Turiu čia pradžioje žymeklį ir mes tai matome vizualiai per sekundę. Bet jei noriu įterpti pabaigoje Turiu pradėti iš pradžių, feed visą kelią į pabaigos, ir tada smeigtuko jį ant. Taigi tai reikštų, kad įterpiant tuo sąrašo pabaigoje taptų n ° operacija, grįžta mūsų diskusija skaičiavimo sudėtingumas. Tai reikia tapti n operaciją, kur O kaip sąrašas gavo didesni ir didesni, ir daugiau, jis bus vis daugiau ir sunkiau smeigtuko kažką ant pabaigoje. Bet tai visada labai lengva smeigtuko kažką pradžioje, jūs visada pradžioje. 

Ir mes matome vaizdo tai dar kartą. Ir tada, kai baigsime, kai mes įterptas naujas mazgas, mes norime grįžti mūsų žymeklį į Naujasis vadovas susietą sąrašą, kuris nes mes įdėti ne pradeda, tikrai bus rodyklė į mazgą, mes ką tik sukūrėte. Leiskite vizualizuoti tai, nes manau, kad padėsime. 

Taigi čia mūsų sąraše, tai sudaro keturi elementai, mazgas, kuriame yra 15, kuri nurodo mazgas , kurių sudėtyje yra 9, kuri nurodo mazgas, kuriame yra 13, kuri nurodo mazgas, kuriame yra 10, kuris turi null žymeklis, kaip jos kito rodyklė taip, kad tai iš sąrašo gale. Taigi mes norime įterpti Naujas mazgas su verte 12 ties šis pradžioje sąrašas, ką mes galime padaryti? Na, visų pirma, mes malloc erdvė mazgas, ir tada mes įdėti 12 ten. 

Taigi dabar mes pasiekėme apsisprendimo tašką, tiesa? Turime pora patarimų, kad mes galėtume judėti, kurių vienas turėtų judame pirmas? Jei mes darome 12 tašką prie naujas vadovas list-- arba atsiprašau, mes turėtume padaryti 12 atkreipti dėmesį į senosios galvos sąrašo? Arba mes turėtume pasakyti, kad Sąraše prasideda 12. Yra skirtumas ten, ir mes pažvelgti ne tai, kas atsitinka su tiek per sekundę. 

Bet tai veda į puikus tema šoninę juostą kuris yra tai, kad viena iš sudėtingiausių dalykų, kurių susijusių sąrašus yra pasirūpinti patarimų teisinga tvarka. Jei perkelti daiktus iš eilės, galite baigti netyčia orphaning iš sąrašo pailsėti. Ir čia yra tos pavyzdys. Taigi eikime su mintimi of-- Na, mes ką tik sukūrėte 12. Mes žinome 12 bus Naujasis vadovas sąrašo ir taip, kodėl ne mes tiesiog perkelti sąrašas žymeklis ten punktą. 

Gerai, kad gerai. Taigi dabar, jei nėra 12 Sekantis taškas? Aš turiu galvoje, vizualiai matome kad ji bus taškas iki 15, kaip žmonėms tai tikrai akivaizdu mums. Kaip veikia kompiuteris žinoti? Neturime nieko nukreipta į 15 nebėra, tiesa? 

Mes prarado bet kokią galimybę kreiptis į 15. Mes negalime pasakyti, nauja rodyklę šalia dydžiu neprilygstami kažkas, ten nieko nėra. Tiesą sakant, mes našlaičiai iš sąrašo likusi tokiu būdu, mes netyčia sulaužė grandinę. Ir mes tikrai nenorime daryti. 

Taigi grįžkime ir bandykite dar kartą. Gal teisė, ką reikia padaryti yra nustatyti 12 anketa kitą rodyklę prie senosios galvos sąrašo pirmą, tada mes galime judėti sąrašą virš. Ir iš tikrųjų, tai yra teisinga tvarka, kad mes reikia laikytis, kai mes dirbant su atskirai susietą sąrašą. Mes visada nori prijungti naujas elementas į sąrašą, Prieš mes tą natūra svarbus žingsnis keisti kurioje, susietą sąrašo galva yra. Vėlgi, tai toks esminis dalykas, mes nenorime prarasti sekti juo. 

Taigi mes norime įsitikinti, kad viskas yra grandinines kartu, Prieš mes judėti, kad žymeklį. Ir taip, tai būtų teisinga tvarka, kuris yra prijungti 12 į sąrašą, Tada sako, kad sąrašas prasideda 12. Jei mes sakėme sąrašas prasideda 12 ir tada bandė prijungti 12 į sąrašą, mes jau matėme, kas nutiks. Mes prarandame sąrašą per klaidą. 

Gerai, kad dar vienas dalykas kalbėti apie. Ką daryti, jei norime atsikratyti visa susijusi sąrašą vienu metu? Vėlgi, mes mallocing visa tai erdvė, ir todėl mes reikia išlaisvinti jį, kai baigsime. Taigi dabar mes norime ištrinti visa susijusi sąrašas. Na, ką mes norime daryti? 

Jei mes pasiekė null žymeklį, mes norite sustabdyti, nes kitaip tiesiog ištrinti iš sąrašo poilsio ir tada išlaisvinti mane. Ištrinti poilsio sąrašo, ir tada laisvai esamą mazgas. Ką tai skamba, kokiu būdu turi mes kalbėjome apie anksčiau Ar tai kaip garsas? Ištrinti visi kiti, tada grįžti ir ištrinti mane. 

Štai rekursija, mes atlikote problema šiek tiek mažesnis, mes sakydamas ištrinti visiems kitur, galite mane ištrinti. Ir toliau žemyn kelio, kad mazgas sakys, ištrinti visi kiti. Bet galų gale mes susisieksime su vieta, kur sąrašas yra niekinis, ir kad mūsų bazinį scenarijų. 

Taigi tegul Šiuo išvaizdą, ir kaip tai galėtų veikti. Taigi čia mūsų sąrašas, tai tas pats sąrašą buvome tik kalbame apie, ir ten žingsniai. Yra daug teksto čia, bet Tikimės, kad vizualizacija padės. 

Taigi, mes have-- ir aš taip pat iškedentas iki mūsų kamino kadrų iliustracija iš mūsų vaizdo pokalbių kaminai, ir tikiuosi visa tai kartu bus parodyti jums, kas vyksta. Taigi čia mūsų Pseudocode kodą. Jei mes pasiekti null žymeklis, sustabdyti, kitaip, ištrinti poilsio sąrašo, tada išlaisvinti esamą mazgas. Taigi dabar, list-- rodyklė kad mes einančios sunaikinti taškų 12. 12 yra ne NULL žymiklį, todėl mes ketina išbraukti iš sąrašo pailsėti. 

Ką išbraukiant Kitos mus dalyvauti? Na, tai reiškia, tiekdami skambinti sunaikinti, sakydamas kad 15 yra pradžia poilsio sąrašo norime sunaikinti. Ir taip skambutis sunaikinti 12 rūšies sulaikytas. Tai užšaldyti ten, laukia skambinti sunaikinti 15, baigti savo darbą. 

Na, 15 tai ne nulinis žymeklis, ir todėl jis ketina pasakyti, viskas gerai, Na, ištrinti sąrašo pailsėti. Iš sąrašo poilsio prasideda , 9, ir taip mes tiesiog laukti, kol pašalinsite visus, kad Daiktai, tada grįžkite ir ištrinti mane. Na 9 manimi ketinate pasakyti, gerai, Nesu NULL rodyklė, taip ištrinti poilsio sąrašą iš čia. Ir todėl pabandykite ir sunaikinti 13. 13 sako, aš ne NULL rodyklė, Tas pats, jis eina spardytis. 10 yra ne NULL žymiklį, 10 yra null žymeklį, bet 10 yra pati nėra null pointer dabar, ir todėl ji eina spardytis per daug. 

Ir dabar list taškų ten, jis tikrai norėtų atkreipti dėmesį į some-- jei aš turėjo daugiau erdvės paveikslėlyje, jis norėtų atkreipti dėmesį į kai kurių atsitiktinių vietos kad mes nežinome, kas tai yra. Tai nulinis žymeklis nors, sąrašas yra tiesiog dabar nustatyti tai vertybės null. Tai nukreipta tiesiai tą raudoną dėžutę. Mes pasiekėme null žymeklį, todėl mes galime sustoti, o baigsime. 

Ir taip, kad violetinė rėmas yra now-- ne Į viršų stack-- tai aktyvus rėmas, bet tai daroma. Jei mes pasiekėme null žymeklį, sustoti. Mes nedarome nieko, mes negalėjo null žymeklį, mes ne malloc bet erdvės, ir todėl mes baigsite. Taigi šią funkciją rėmo yra sunaikinta, ir mes resume-- mes pasiimti ten, kur mes palikome išjungti su kito aukščiausio punktų, kuris tai tamsiai mėlyna rėmas čia. Taigi, mes pasiimti ten, kur mes palikome išjungtas. Mes išbraukė likusieji Sąrašas jau, todėl dabar mes ketina atlaisvinti dabartinius mazgai. Taigi, dabar mes galime išlaisvinti šį mazgą, o dabar mes pasiekė funkcija pabaigą. Ir taip, kad funkcija rėmas sunaikinti, ir mes pasiimti šviesos mėlyna vieną. 

Taigi says-- Aš jau done-- ištrinant sąrašo poilsio, taip, nemokamai esamą mazgas. Ir dabar geltonas rėmelis atgal ant kamino. Ir taip, kaip matote, mes dabar sunaikinti sąrašą iš dešinės į kairę. 

Kas būtų nutikę, nors, jei būtume veikėme neteisingą kelią? Tiesiog patinka, kai mes bandėme pridėti elementą. Jei mes messed up grandinę, jei mes ne prijungti patarimų teisinga tvarka, jei mes tik išlaisvino pirmąjį elementą, jei mes tiesiog išlaisvino vadovas sąrašo, dabar mes jokiu būdu kreiptis į iš sąrašo poilsio. Ir taip mes turėtume našlaičiais viskas, mes turėjome tai, kas vadinamas Atminties nutekėjimas. Jei prisimenate iš mūsų vaizdo nuo dinaminės atminties paskirstymo, tai nėra labai geras dalykas. 

Taigi, kaip jau sakiau, Yra keletas operacijos kad mes turime naudoti dirbti su susieta sąrašą efektyviai. Ir jūs turbūt pastebėjote, aš praleisti vieną, išbraukiant vieną elementą iš susietos sąrašas. Priežastis, kodėl aš padariau, kad tai tikrai rūšies sudėtinga galvoti apie tai, kaip ištrinti vienas elementas nuo A pavieniui susiję sąrašas. Mums reikia, kad būtų galima praleisti kažkas į sąrašą, kuris reiškia, kad mes patekti į point-- mes norite ištrinti šią node-- Tačiau, norint padaryti jį, todėl mes nepraranda jokios informacijos, turime prijungti šį mazgas per čia, čia. 

Taigi, aš tikriausiai padarė, kad negerai iš vizualiniu požiūriu. Taigi mes ne iš pradžių mūsų sąrašas, mes tęsdami per, mes norime ištrinti šį mazgą. Jei mes tiesiog ištrinti jį, mes suskaidytas į grandinę. Tai mazgas čia remiasi visa kita, jis yra iš čia atlikti grandinę. 

Taigi, ką mes turime padaryti iš tikrųjų kai mes gauti į šį punktą, yra mums reikia atsitraukti vieną, ir prijungti šį mazgą per šį mazgą, todėl mes galime tada ištrinti viduryje esanti viena. Bet pavieniui susiję sąrašai nėra pateikti mums būdą, kaip grįžti atgal. Taigi mums reikia arba išlaikyti dvi rodykles, ir perkelti juos rūšiuoti išjungimo žingsnio, viena už kita, kaip mes einame, arba gauti iki taško, ir tada siųsti kitą žymiklį per. Ir, kaip matote, ji gali gauti šiek tiek nepatogus. Laimei, mes turime dar vienas būdas išspręsti, kad kai kalbame apie dvigubai susijusių sąrašus. 

AÅ¡ Doug Lloyd, tai CS50.