>> [TÓNLIST spila]
>> DOUG LLOYD: OK, þannig að þetta atriði í námskeiðinu,
við höfum fjallað mikið á grunnatriði C Við vitum mikið um breytur, fylki,
ábendingum, allt sem gott efni.
Þeir eru allir tegund af innbyggður til að sjá sem grundvallaratriði,
en við getum gert meira, ekki satt?
Við getum sameina hlutina saman á áhugaverðan hátt.
>> Og svo við skulum gera það, við skulum byrja að útibú út um hvað C gefur okkur,
og byrja að búa til eigin gögn okkar mannvirki sem nota þessar bygging
blokkir saman til að gera eitthvað mjög mikilvægt, að gagni.
Ein leið til að geta gert þetta er að tala um söfn.
Svo svo langt að við höfum haft eina tegund af gögnum uppbygging fyrir hönd söfn
af eins gildi, svipuð gildi.
Það væri fylki.
Við höfum söfn heiltölur eða söfn af stöfum og svo framvegis.
>> Mannvirki eru einnig tegund af gögnum uppbygging til að safna upplýsingum,
en það er ekki að safna eins gildum.
Það blandar yfirleitt mismunandi gögn gerðir saman inni í einn kassa.
En það er ekki sjálft er notað til að keðja saman
eða tengja saman svipað atriði, eins og fylki.
Fylki eru frábær fyrir þáttur líta upp, en muna
að það er mjög erfitt að setja inn í array,
nema við erum að setja á mjög lok þess array.
>> Og besta dæmið sem ég hef fyrir því er innsetning tegund.
Ef þú manst vídeó okkar á innsetningu tagi,
það var mikið af kostnað þátt í að hafa
að taka upp þætti, og skipta þeim út af leiðinni til að passa eitthvað
í miðju fylkisins þinn.
Fylki þjást einnig af öðru Vandamálið, sem er ósveigjanleika.
Þegar við lýsa fylki, við fáum eitt skot á það.
Við fáum að segja, ég vil þetta margir þættir.
Gæti verið 100, gæti það vera 1.000, gæti það
vera x þar sem x er tala sem notandinn gaf okkur á a hvetja eða á stjórn
lína.
>> En við fáum aðeins eitt skot á það, að við fæ ekki að þá segja ó, reyndar
þarf 101, eða ég þurfti x plús 20.
Of seint, við höfum nú þegar lýsti array, og ef við viljum fá 101 eða x
auk 20, verðum við að lýsa algjörlega mismunandi array,
afrita alla þætti array yfir, og þá höfum við nóg.
Og hvað ef við erum rangt aftur, hvað ef við þurfum í raun 102 eða x plús 40,
við verðum að gera þetta aftur.
Svo þeir eru mjög ósveigjanleg fyrir resizing gögn okkar,
en ef við sameina saman nokkrum grunnatriði sem við höfum nú þegar
lært um ábendingum og mannvirki, einkum með dynamic minni
úthlutun með malloc, við getur sett þessi stykki saman
til að búa til ný gögn structure-- A eintengdan lista við gætum say--
sem gerir okkur kleift að vaxa og skreppa safn af gildum
og við munum ekki hafa allir spara pláss.
>> Svo aftur, við köllum þessa hugmynd, Þessi hugmynd, tengda listanum.
Einkum í þessu myndbandi sem við erum að tala um stakar tengda listanum,
og þá annað video sem við munum tala um tvöfalt tengd listum, sem
er bara tilbrigði þema hér.
En ein tengda listanum er samsett af hnúður,
hnúður bara að vera ágrip term-- það er bara eitthvað sem ég er að hringja
það er eins konar uppbyggingu, í grundvallaratriðum, ég?
Bara að fara að kalla það node-- og þetta hnútur hefur tvo fulltrúa eða tveimur sviðum.
Það hefur gögn, yfirleitt heiltala, persónu fljóta,
eða gæti verið einhver önnur gögn tegund sem þú hefur skilgreint með gerð def.
Og það inniheldur bendi annan hnút af sömu gerð.
>> Þannig að við höfum tvennt inni þetta hnút, gögn og bendi
til annars hnút.
Og ef þú byrjar að sjón þetta, getur þú hugsa um það
eins keðju hnúður sem eru tengdir saman.
Við höfum í fyrsta hnút, það inniheldur gögn og bendi
til seinni hnút, sem inniheldur gögn, og bendi á þriðja hnút.
Og svo er það þess vegna sem við köllum það í tengda listanum, þeir tengdir saman.
>> Hvað þýðir þetta sérstaka hnút uppbyggingu líta út?
Jæja, ef þú manst frá vídeó okkar á skilgreina sérsniðna tegundir, með gerð def,
getum við að skilgreina structure-- og slá skilgreina uppbyggingu svona.
tyepdef struct sllist, og þá er ég nota orðið gildi hér geðþótta
að gefa til kynna hvaða gögn tegund í raun.
Þú gætir fara á heiltala eða fljóta, þú gætir hafa það sem þú vilt.
Það er ekki bundin við bara heiltölur, eða eitthvað svoleiðis.
Svo er gildi bara handahófskennt gögn gerð, og þá bendi
til annars hnút af sömu gerð.
>> Nú, það er a lítill afli hér með að skilgreina uppbyggingu
þegar það er sjálf vísun uppbyggingu.
Ég verð að hafa tímabundið nafn fyrir uppbyggingu mína.
Í lok dagsins I greinilega vilt kalla það
SLL hnút, það er að lokum nýja nefna hluta af gerð skilgreiningu mína,
en ég get ekki notað SLL hnút í miðju þessu.
Ástæðan sé, ég hef ekki skapað tegund heitir SLL hnút
þangað til ég lenti þessu endanlega lið hér.
Fram að þeim tímapunkti, ég verð að hafa önnur leið til að vísa til þessa tegund gagna.
>> Og þetta er sjálf vísun gögn tegund.
Það; s a gögn tegund a mannvirki sem inniheldur gögn,
og bendi til annars Uppbygging af sömu gerð.
Þannig að ég þarf að vera fær um að vísa til þessi gögn tegund amk tímabundið,
svo gefa það a tímabundinn nafn struct sllist
leyfa mér að þá segja að ég vil að bendi á annan struct sllist,
a struct sllist stjarna, og þá eftir að ég hef lokið við skilgreiningu,
Ég get nú kalla þessa tegund er SLL hnút.
>> Svo er það hvers vegna þú sérð að það er tímabundið nafn hér,
en varanleg nafn hér.
Stundum þú gætir séð skilgreiningar á uppbyggingu,
til dæmis, sem eru ekki sjálf vísun, sem
hafa ekki specifier nafn hér.
Það myndi bara segja typedef strúktúr, opna hrokkið Brace og þá skilgreina það.
En ef þú ert struct er sjálf vísun, sem þetta er,
þú þarft að tilgreina a tímabundin tegund nafn.
En að lokum, nú sem við höfum gert þetta,
við getum bara átt við þessir hnútar, þessar einingar,
sem SLL hnúður fyrir tilgangi af the hvíla af this vídeó.
>> Allt í lagi, þannig að við vitum hvernig á að búa til tengda listanum hnút.
Við vitum hvernig á að skilgreina tengda listanum hnút.
Nú, ef við erum að fara að byrja nota þær til að safna upplýsingum,
það er a par af rekstri við þurfa að skilja og vinna með.
Við þurfum að vita hvernig á að búa til tengdur listi úr lausu lofti.
Ef það er enginn listi þegar, Við viljum byrja einn.
Þannig að við þurfum að vera fær um til að búa til tengdan lista,
við þurfum að öllum líkindum að leita í gegnum tengilinn listann
að finna stak við erum að leita að.
Við þurfum að vera fær um að setja nýja hluti í listanum,
við viljum lista okkar til að vera fær um að vaxa.
Og sömuleiðis, við viljum vera fær um að eyða hlutum úr listanum okkar,
við viljum lista okkar til að vera fær um að skreppa saman.
Og í lok okkar forrit, sérstaklega
ef þú manst að við erum virk úthluta minni
til að byggja þessar listum yfirleitt, við viljum að losa öll þessi minni
þegar við erum búin að vinna með það.
Og svo þurfum við að vera fær um að eyða Allt tengda listanum í einu mistakast punda.
Svo skulum við fara í gegnum sumir af þessum aðgerðum
og hvernig við gætum sjón þá, tala í sauðakóðanum kóða sérstaklega.
Þannig að við viljum búa til tengd lista, svo kannski við
vilja til að skilgreina hlutverk með þessari frumgerð.
SLL hnút stjarna, búa til, og ég er liggur í einni rifrildi, sumir handahófskennt gögn
tegund aftur, einhvern handahófskenndan gögn tegund.
En ég er returning-- þessa aðgerð ætti Hverf aftur til mín bendi til a ein
tengda listanum hnút.
Aftur erum við að reyna að búa til tengdur listi úr lausu lofti,
þannig að ég þarf bendi þessi listi þegar ég er búin.
>> Svo það eru skref sem taka þátt hér?
Jæja, fyrsta sem ég að fara að gera er virk
úthluta pláss fyrir nýja hnút.
Aftur, við erum að búa það út af þunnt loft, þannig að við þurfum að malloc pláss fyrir það.
Og auðvitað, strax eftir að við malloc,
við athugum alltaf að ganga úr skugga um að okkar pointer-- við ekki fá til baka null.
Vegna þess að ef við reynum og tillitssemi núll músina,
við erum að fara að þjást segfault og við viljum ekki að.
>> Þá viljum við fylla á sviði, við viljum að frumstilla gildi sviði
og frumstilla næsta reit.
Og þá viljum to-- lokum sem virka frumgerð indicates-- við viljum
að skila bendi til SLL hnút.
Svo hvað gera þetta líta út eins sjónrænt?
Jæja, fyrst við erum að fara að virk úthluta pláss fyrir nýja SLL hnút,
svo við malloc-- það er Myndræn
hnútarins við bjuggum bara.
Og við athuga til að tryggja það er ekki null-- í þessu tilfelli,
myndin myndi ekki hafa sýnt upp ef það var null,
við hefðum keyrt út af minni, þannig að við erum gott að fara þangað.
Svo nú erum við á að stíga C, frumstillt hnúður gildi sviði.
Jæja, byggt á þessari aðgerð kalla ég nota hér,
lítur út eins og ég vil að fara í 6, Svo ég 6 í gildi sviði.
Nú, frumstilla næsta reit.
Jæja, hvað er ég að fara að gera það, það er ekkert næst, rétt,
þetta er það eina sem á listanum.
Svo er það næsta sem á listanum?
>> Það ætti ekki að benda á neitt, ekki satt.
Það er ekkert annað þarna, svo er það hugtakið sem við vitum af því er nothing--
ábendingum að engu?
Það ætti að vera kannski að við viljum að setja núll músina þar,
og ég ætla að tákna null bendillinn eins bara rauðan kassa,
við getum ekki farið lengra.
Eins og við munum sjá smá seinna, munum við hafa að lokum keðjur
örvum tengja þessir hnútar saman,
en þegar þú högg the rauður kassi, það er null,
við getum ekki farið lengra, það er enda á listanum.
>> Og loks, við viljum bara að aftur bendi þessum hnút.
Þannig að við munum kalla hann nýjan, og mun skila nýja
svo það er hægt að nota í hvað virka skapaði það.
Þannig að það sem við förum, við höfum sett ein tengda listanum hnút úr lausu lofti,
og nú erum við með lista sem við getum unnið með.
>> Nú, við skulum segja að við nú þegar hafa stóra keðju
og við viljum að finna eitthvað í það.
Og við viljum að aðgerð sem er að fara til að fara aftur satt eða ósatt, fer
um hvort gildi er í þeim lista.
Fall frumgerð, eða Yfirlýsing fyrir að virka,
gæti litið út this-- bool finna, og þá viljum við fara í tveimur rök.
>> Sú fyrsta, er bendi til Fyrsta þáttur í tengda listanum.
Þetta er í raun eitthvað sem þú munt alltaf vilja til að halda utan um,
og í raun gæti verið eitthvað sem þú setur jafnvel í alþjóðlegum breytu.
Þegar þú býrð til lista, alltaf, alltaf
langar að halda utan um það Fyrsti þátturinn af listanum.
Þannig að þú getur átt við allar aðrar þættir með bara eftir keðju,
án þess að þurfa að halda ábendingum ósnortinn hverjum einasta frumefni.
Þú þarft aðeins að halda utan um fyrsta einn ef þeir eru allir handjárnaða saman.
>> Og þá seinni sem við erum liggur aftur
er geðþótta some-- hvað gögn tegund við erum
að leita að þar er inni vonandi einn af hnúður á listanum.
Svo það eru skref?
Jæja, það fyrsta sem við gerum er við að búa til þversum músina
benda til minnislista höfuð.
Jæja, hvers vegna eigum við að gera það, sem við nú þegar hafa músina á listum höfuð,
Hvers vegna eigum við ekki að fara bara að einn í kring?
Jæja, eins og ég sagði bara, það er mjög mikilvægt fyrir okkur
að alltaf að halda utan um Fyrsti þáttur í listanum.
Og svo er það í raun betra til að búa til afrit af því,
og nota það til að færa sig svo við aldrei óvart flytja í burtu, eða við alltaf
hafa músina á einhverjum tímapunkti sem er rétt á fyrstu frumefni á listanum.
Svo það er betra að búa til seinni sem við notum til að hreyfa.
>> Þá erum við saman bara hvort gildi sviði í hnút
er það sem við erum að leita að, og ef það er ekki, hreyfa við bara í næsta hnút.
Og við höldum að gera það yfir, og aftur, og aftur,
þar til við annað hvort að finna þáttur, eða við högg
null-- við höfum náð enda af listanum og það er ekki þar.
Þetta ætti vonandi hringja bjöllu til þín sem bara línuleg leit,
við erum bara afrit það í eintengdan lista uppbygging
í stað þess að nota array að gera það.
>> Svo er hér dæmi um eintengdan lista.
Þetta eitt samanstendur af fimm hnúta, og við höfum
bendi á höfuð hins lista, sem heitir lista.
The fyrstur hlutur sem við viljum gera er að aftur, búa til að Traversal músina.
Þannig að við höfum nú tvær ábendingum sem benda til það sama.
>> Nú, eftir hingað, ég gerði ekki að malloc allir pláss fyrir Trav.
Ég sagði ekki Trav jafngildir malloc eitthvað, sem hnút þegar til,
sem pláss í minni er þegar til.
Svo er allt sem ég er í raun að gera búa til annað músina til þess.
Ég er ekki að mallocing til viðbótar rúm, bara nú tvær ábendingum
benda til það sama.
>> Svo er 2 sem ég er að leita að?
Jæja, nei, þannig að í stað ég er að fara að flytja til the næstur einn.
Svo í rauninni ég myndi segja, Trav jafngildir Trav næst.
Er 3 það sem ég er að leita að nr.
Svo ég held áfram að fara í gegnum, þar til að lokum
fá til 6 sem er það sem ég er að leita fyrir miðað við virka símtalinu
Ég hef efst þar, og svo ég er búin.
>> Nú, hvað ef þátturinn ég að leita að er ekki á listanum,
er það að fara enn að vinna?
Jæja, eftir að listinn hér er subtly mismunandi,
og þetta er annar hlutur sem er mikilvægt við tengd listum,
þú þarft ekki að varðveita þá í einhverju tilteknu skyni.
Þú getur ef þú vilt, en þú kannt að hafa þegar tekið
að við erum ekki að halda utan um hvað fjölda þáttur sem við erum á.
>> Og það er tegund af einum viðskiptum sem við hafa með tengda listanum vísur fylki,
er það að við höfum ekki handahófi aðgang lengur.
Við getum ekki bara segja, ég vil að fara í 0th frumefni,
eða 6 þáttur array minn, sem ég get gert í fylki.
Ég get ekki sagt að ég vil fara til 0 þáttur, eða 6 þáttur,
eða 25 þáttur tengda listanum mínum, það er engin Vísitala tengslum við þá.
Og svo það skiptir ekki máli ef við varðveita lista okkar í röð.
Ef þú vilt að þér vissulega getur, en það er
engin ástæða fyrir því að þeir þurfa að varðveitist í hvaða röð.
Svo aftur, við skulum reyna að finna 6 í þessum lista.
Jæja, byrjum við á að farin, finnum við ekki 6,
og þá erum við að halda áfram að finna 6, þar til við fáum loksins að hér.
Svo núna Trav stig til hnút inniheldur 8 og sex er ekki þar.
>> Þannig að næsta skref væri til að fara á næsta músina,
svo segja trav jafngildir Trav næst.
Jæja, Trav næsta, táknuð með rauða kassi það er null.
Þannig að það er hvergi annars staðar að fara, og svo á þessum tímapunkti
við getum gert það sem við höfum náð the endir af the tengda listanum,
og 6 er ekki þar.
Og það væri aftur rangar í þessu tilfelli.
>> OK, hvernig eigum við að setja nýtt hnút í tengda listanum?
Þannig að við höfum getað til að búa til tengdur listi út af hvergi,
en við viljum líklega að byggja upp keðju og ekki
búa til fullt af mismunandi listum.
Við viljum hafa einn lista sem hefur fullt af hnúður í það,
ekki fullt af listum með einum hnút.
Þannig að við getum ekki bara haldið áfram að nota Búa virka við skilgreint fyrr, nú erum við
langar að setja inn a listi sem er þegar til.
>> Svo þessu tilfelli erum við að fara að fara í tvær breytur,
bendillinn höfuð sem tengd lista sem við viljum bæta við.
Aftur, það er hvers vegna það er svo mikilvægt að við alltaf
halda utan um það, vegna þess að það er eina leiðin sem við raunverulega
að vísa til allt listi er bara með því að bendi á fyrstu frumefni.
Þannig að við viljum fara í bendi á að fyrsta frumefni,
og hvað sem gildi vér langar að bæta við listann.
Og að lokum þessi aðgerð er að fara að skila bendi
að nýr yfirmaður tengda listanum.
>> Hvaða skref sem taka þátt hér?
Jæja, bara eins og með að búa, við þurfum að virk úthluta
pláss fyrir nýja hnút, og þess viss um að við keyri ekki út af minni, aftur,
vegna þess að við erum að nota malloc.
Þá viljum við byggja og settu hnút,
svo setja fjölda, hvað Val er í hnút.
Við viljum að setja hnút á upphaf tengda listanum.
>> Það er ástæðan fyrir því að ég langar að gera þetta, og það
gæti verið þess virði að taka annað að gera hlé á vídeó hér,
og hugsa um hvers vegna ég myndi vilja setja í upphafi tengdur
lista.
Aftur, ég nefndi áðan að það er í raun ekki
máli hvort við varðveita það í hvaða röð, svo kannski er það vísbending.
Og þú sást hvað myndi gerast ef við vildi to-- eða bara annað
síðan þegar við vorum að fara gegnum leit þú
gat séð hvað gæti gerast ef við vorum að reyna
til að setja í lok listanum.
Þar sem við höfum ekki bendillinn til loka listanum.
>> Svo ástæða þess að ég myndi vilja til að setja í upphafi,
er vegna þess að ég get gert það strax.
Ég er með músina í upphafi, og við munum sjá þetta í sjón í annað.
En ef ég vil setja í lokin, Ég verð að byrja á byrjun,
fara yfir alla leið til enda, og þá tittur á því.
Svo sem myndi þýða að að setja í lok listanum
myndi verða eða n rekstur, að fara aftur
að umfjöllun okkar um computational flókið.
Það myndi verða eða af n rekstri, þar sem listinn fékk stærri og stærri,
og stærri, verður það verða fleiri og erfiðara að tittur eitthvað
á í lokin.
En það er alltaf mjög auðvelt að tittur eitthvað á í upphafi,
þú ert alltaf í upphafi.
>> Og við munum sjá sjón af þessu aftur.
Og þá þegar við erum búin, einu sinni við höfum sett nýja hnút,
við viljum aftur bendi okkar til nýr yfirmaður tengda listanum, sem
þar sem við erum að setja á the farin, mun reyndar vera
bendi á hnút við að búa til.
Skulum sjón þetta, vegna þess að ég held að það mun hjálpa.
>> Svo er hér listi okkar, samanstendur það af fjórir þættir, hnút inniheldur 15,
sem bendir til hnút sem inniheldur 9, þar sem
bendir til hnút inniheldur 13, sem bendir til hnút inniheldur
10, sem hefur núll bendillinn eins næsta bendillinn birtist
svo er að í lok listanum.
Þannig að við viljum að setja a Ný hnút með gildi 12
í upphafi þessa lista, hvað gerum við?
Jæja, fyrst við malloc pláss fyrir hnút, og þá erum við að setja 12 í það.
>> Svo nú höfum við náð Ákvörðun lið, ekki satt?
Við hafa a par af ábendingar sem við gátum
færa, sem maður á að við fara fyrst?
Ættum við að gera 12 stig til nýr yfirmaður list--
eða afsakið, ættum við að gera 12 benda á gamla höfuð listanum?
Eða ættum við að segja að Listinn hefst nú á 12.
Það er greinarmunur þar, og við munum líta
á hvað gerist með bæði í annað.
>> En þetta leiðir til a mikill efni fyrir skenkur,
sem er að ein af erfiðustu hluti með tengd listum
er að raða ábendingum í réttri röð.
Ef þú færir fram úr röð, þú getur endað óvart
orphaning restina af listanum.
Og hér er dæmi um það.
Svo skulum við fara með þá hugmynd of-- jæja við höfum bara búið 12.
Við vitum 12 er að fara að vera nýr yfirmaður lista,
og svo hvers vegna eigum við ekki að fara bara listi bendillinn að benda þar.
>> OK, svo er það gott.
Svo nú hvar 12 næsta lið?
Ég meina, sjónrænt getum við séð að það muni benda til 15,
eins og menn það er mjög augljóst að okkur.
Hvernig virkar tölva veit?
Við höfum ekki neitt benda til 15 lengur, ekki satt?
>> Við höfum misst neina getu til að vísa til 15.
Við getum ekki sagt nýtt örina við hliðina jafn eitthvað, það er ekkert þar.
Í raun höfum við munaðarlaus restin af listanum
með því að gera það, höfum við óvart brotið keðju.
Og við vissulega vil ekki að gera það.
>> Svo við skulum fara aftur og reyna þetta aftur.
Kannski rétt að gera er að setja næstu músina 12 er
að gamla höfuð listanum fyrsta, þá getum við flutt listann yfir.
Og í raun, það er rétt til þess að vér
þarf að fylgja þegar við erum vinna með stakar tengda listanum.
Við viljum alltaf að tengja Ný þáttur í listanum,
áður en við förum svona mikilvægt skref í að breyta
þar sem yfirmaður tengda listanum er.
Aftur, það er svo grundvallaratriði hlutur, við viljum ekki að missa utan um það.
>> Þannig að við viljum tryggja að allt er hlekkjaður saman,
áður en við fara að bendilinn.
Og svo þetta væri rétta röð, sem er að tengja 12 á listann,
þá segja að listinn byrjar 12.
Ef við sagði listinn byrjar á 12 og þá reynt að tengja 12 á listann,
við höfum þegar séð hvað gerist.
Við missa listann mistök.
>> OK, svo eitt í viðbót til að tala um.
Hvað ef við viljum losna við heilt tengd lista í einu?
Aftur, við erum mallocing allt þetta pláss, og svo við
þarf að losa það þegar við erum búin.
Svo nú viljum við að eyða allt tengda listanum.
Jæja, hvað viljum við gera?
>> Ef við höfum náð núll músina, við vilt hætta, annars, bara eyða
restin af listanum og síðan losa mig.
Eyða restinni af listanum, og þá losa núverandi hnút.
Hvað gerir þessi hljóð eins, hvað tækni höfum við ræddum
um áður Hefur þessi hljóð eins?
Eyða allir aðrir, þá koma aftur og eyða mér.
>> Það er endurkvæmni, höfum við gert Vandamálið svolítið minni,
við erum að segja að eyða allir annars, þá er hægt að eyða mér.
Og lengra niður veginn, sem hnút mun segja, eyða og allir aðrir.
En að lokum munum við fá til the málið þar sem listinn er null,
og það er undirstaða málið okkar.
>> Svo skulum taka a líta á þetta, og hvernig þetta gæti virkað.
Svo er hér listi okkar, það er sama listi við vorum bara að tala um,
og það er skref.
There 'a einhver fjöldi af texta hér, en vonandi visualization mun hjálpa.
>> Þannig að við have-- og ég dró líka upp stafla ramma okkar dæmi
frá vídeó okkar á vakt stafla, og vonandi allt þetta
saman mun sýna þér hvað er að gerast.
Svo hér sauðakóðanum númerið okkar.
Ef við náum null músina, stöðva, annars,
eyða restinni af listanum, þá frjáls núverandi hnút.
Svo núna, list-- bendillinn að við erum
liggur í að eyða stig til 12.
12 er ekki null músina, þannig að við erum að fara að eyða restina af listanum.
>> Hvað er að eyða restin af okkur að ræða?
Jæja, það þýðir að a kalla að eyðileggja, segja
að 15 er upphaf af restin af listanum sem við viljum eyða.
Og svo hringt til að eyða 12 er góður af á bið.
Það er fryst þar, bíða eftir kalla að eyða 15, til að ljúka starfi sínu.
>> Jæja, 15 er ekki null músina, og svo það er að fara að segja, allt í lagi,
vel, eyða restina af listanum.
The hvíla af listanum byrjar á 9, og svo við verðum bara
bíddu þar til þú eyðir öllu sem efni, þá komið aftur og eyða mér.
Jæja 9 er að fara að segja, vel, Ég er ekki null músina,
svo eyða hinum listanum hér.
Og svo reyna og eyðileggja 13.
13 segir, ég er ekki null músina, sama, fer það peninginn.
10 er ekki null músina, 10 inniheldur núll músina,
en 10 er ekki sjálf null músina núna,
og svo fer það peninginn líka.
>> Og nú lista stig þar, það virkilega myndi benda til some--
ef ég hefði meira pláss í myndinni, það myndi benda til sumir af handahófi rúm
að við vitum ekki hvað það er.
Það er null bendillinn þó listi er bókstaflega nú sett það gildi null.
Það er að benda beint í þeirri rauðum kassa.
Við náð núll músina, svo við getum hætt, og við erum að gera.
>> Og svo er að fjólublátt ramma now-- minnsta Efst á stack-- það er virka ramma,
en það er gert.
Ef við höfum náð núll músina, hætta.
Við gerum ekki neitt, við getur ekki frjáls núll músina,
við vissum ekki malloc eitthvað rúm, og svo við erum að gera.
Þannig að hlutverk ramma er eytt, og við
resume-- við taka upp þar sem við var burt með næsthæsta einn, sem
er þetta dökk blár rammi hér.
Þannig að við taka upp hægri þar sem við var horfið.
Við eytt restina af Listinn þegar, svo nú erum við
að fara að losa núverandi hnúta.
Svo nú getum við frjáls þennan hnút, og nú við höfum náð enda fallsins.
Og þannig að hlutverk ramma er eytt, og við tekið upp á ljósbláu einn.
>> Svo það says-- ég hef þegar done-- eyða restina af listanum, svo
frjáls núverandi hnút.
Og nú er gulur ramma aftur ofan á stafla.
Og svo eins og þú sérð, við erum nú eyðileggja listann frá hægri til vinstri.
>> Hvað hefði gerst, þó, ef við hefðum gert hlutina á rangan hátt?
Rétt eins og þegar við reyndum að bæta þáttur.
Ef við boðberi upp keðju, ef við vissum ekki tengja ábendingum
í réttri röð, ef við bara leysti fyrsta þáttur,
ef við leystur bara yfirmaður lista, nú erum við
hafa enga leið til að vísa til restin af listanum.
Og svo við hefðum munaðarlaus allt,
við hefðum haft það sé kallað minni leka.
Ef þú manst frá vídeó okkar á dynamic minni úthlutun,
það er ekki mjög gott.
>> Svo eins og ég sagði, það eru nokkrir aðgerðir
sem við þurfum að nota til að vinna með tengda listanum raun.
Og þú gætir hafa tekið eftir að ég sleppt einn, eyða einn þáttur frá tengdur
lista.
Ástæðan ég gerði það er að það er í raun eins konar
erfiður að hugsa um hvernig á að eyða einn þáttur frá a ein
tengda listanum.
Við þurfum að vera fær um að sleppa yfir eitthvað á listanum, sem
þýðir að við fá að point-- vér viljir eyða þessari node--
en í því skyni að gera það svo við missir ekki neinar upplýsingar,
við þurfum að tengja þetta hnút hérna, hér.
>> Svo ég gerði líklega að rangt frá sjón sjónarhorni.
Þannig að við erum í upphafi okkar lista, við erum áfram í gegnum,
við viljum eyða þennan hnút.
Ef við eyða bara það, við höfum brotið keðju.
Þetta hnút hérna er átt við allt annað,
það inniheldur keðja frá hér á út.
>> Svo það sem við þurfum að gera í raun og veru eftir að við fáum að þessum tímapunkti,
er að við þurfum að stíga til baka einn, og tengja þennan hnút yfir þessari hnút,
svo við getum þá eytt einn í miðju.
En ein tengd listum ekki veita okkur leið til að fara aftur á bak.
Þannig að við þurfum að annaðhvort halda tveir ábendingum og færa þau
konar burt skref, einn á bak við annað sem við förum, eða komast í lið
og þá senda annan músina í gegnum.
Og eins og þú geta sjá, það Hægt er að fá svolítið sóðalegur.
Sem betur fer, höfum við önnur leið til að leysa það,
þegar við tölum um tvöfalt tengd listum.
>> Ég er Doug Lloyd, þetta er CS50.