>> [Predvaja glasba]
>> Doug LLOYD: OK, tako da na to točko v času,
smo pokrili veliko osnov C. Vemo veliko o spremenljivke, nizi,
kazalci, vse to dobra stvar.
Tisti, ki so vsi nekako zgradili V videti kot temeljev,
vendar lahko storimo več, kajne?
Mi lahko združite stvari skupaj v zanimive načine.
>> In tako naredimo, da začnimo da vejo iz tega, kar nam daje C,
in začeli ustvarjati lastne podatke struktur, ki uporabljajo te stavbe
bloki skupaj nekaj narediti res dragoceno, koristno.
Eden od načinov, da lahko to storite govoriti o zbirkah.
Torej, če smo imeli eno vrsto podatkov struktura za predstavitev zbirke
od všeč vrednote, podobne vrednote.
To bi bilo array.
Imamo zbirke števil, ali zbirke znakov, in tako naprej.
>> Strukture so tudi neke vrste podatkov struktura za zbiranje informacij,
vendar to ni za zbiranje kot vrednote.
To ponavadi meša različne vrste podatkov skupaj znotraj enotnega prostora.
Ampak to ni samo po sebi uporablja za verigo skupaj
ali pa se povežite skupaj podobno predmetov, kot array.
Polja so super za element poglej gor, ampak se spomni
da je zelo težko vstaviti v array,
če smo vstavitvijo samega konca tega niza.
>> In najboljši primer imam za to je vstavljanje nekako.
Če se spomnite naš video na vstavljanja vrste,
ni bilo veliko odhodek vključen v ob
da poberem elemente in jih prestavite odročen se prilega nekaj
v sredi svojega polja.
Arrays trpijo tudi drugi problem, ki je neprožnost.
Ko izjavljamo niz, smo dobili en strel na njo.
Smo dobili reči, želim to veliko elementov.
Morda 100, morda pa bilo 1000, bi bilo
je x, kjer je x število, ki uporabniku nam je dal na poziv ali na ukaz
linijo.
>> Vendar pa smo dobili le en strel na to, smo ne dobijo potem pravijo oh, pravzaprav sem
Potrebna 101, ali pa sem potreboval x plus 20.
Prepozno, smo že razglasili matrika, in če želimo dobiti 101 ali x
plus 20, moramo razglasiti povsem drugačen matrika,
kopirati vse elemente matrike več, in potem imamo dovolj.
In kaj, če se bomo spet narobe, kaj če bomo dejansko potrebovali 102, ali je X plus 40,
moramo to storiti še enkrat.
Torej, oni so zelo neprilagodljiv za spreminjanje velikosti naše podatke,
če pa združite nekaterih od osnov, ki smo jih že
spoznavali kazalci in struktur, zlasti z uporabo dinamičnega pomnilnika
Dodelitev z knjižnične funkcije malloc smo lahko postavite te koščke
ustvariti novo podatkovno structure-- a posamič povezani seznam bomo morda say--
ki nam omogoča, da raste in shrink zbirko vrednot
in ne bomo imeli nobenega zapravljen prostor.
>> Torej še enkrat, pravimo to idejo, ta pojem, A povezani seznam.
Zlasti v tem videu smo Govorimo o posamič povezani seznam,
nato pa še video bomo govorili približno dvakrat povezani seznam, ki
je samo variacija na temo tukaj.
Ampak posamič povezani seznam je sestavljen iz vozlišč,
vozlišča kot le abstraktna term-- to je samo nekaj Kličem
to je neke vrste struktura, v bistvu, da sem?
Šele tekoč, da ga pokličete node-- in to vozlišče ima dva člana, ali dve polji.
Ima podatke, navadno celo, plovec značaj,
ali je lahko kakšna druga vrsta podatkov ki ste jo določili s tipom def.
In vsebuje kazalec na drugo vozlišče istega tipa.
>> Torej imamo dve stvari v notranjosti to vozlišče, podatki in kazalec
v drugo vozlišče.
In če začnete vizualizirati to, lahko si misliš o njem
kot verige vozlišč, da med seboj povezane.
Imamo prvo vozlišče, ga vsebuje podatke, in kazalec
Na drugo vozlišče, ki vsebuje Podatki, in kazalec na tretje vozlišče.
In da je, zakaj smo ga poklical povezani seznam, oni so med seboj povezani.
>> Kaj to posebno Struktura vozlišče izgledal?
No, če se spomnimo iz naše video na opredelitev vrst po meri, s tipom def,
moremo opredeliti structure-- in tip opredeliti strukturo, kot je ta.
tyepdef struct sllist, in potem sem uporabo vrednosti besedo tukaj samovoljno
kažejo nobenih podatkovni tip res.
Lahko prenese na celo število ali likvidna sredstva, bi lahko imeli karkoli hočeš.
To ni omejen samo cela, ali kaj podobnega.
Torej vrednost je samo poljubna podatkovni tip in nato kazalec
v drugo vozlišče iste vrste.
>> Zdaj pa je malo ulov tukaj pri opredeljevanju strukture
ko je struktura samo referenčna.
Moram imeti začasna ime za mojo strukturo.
Ob koncu dneva I očitno želijo, da ga pokličete
sll vozlišče, ki je na koncu novega naštejemo del moje definicije tipa,
vendar ne morem uporabljati SLL vozlišče v sredini tega.
Razlog je, nimam ustvaril vrsto imenovano SLL vozlišče
dokler nisem udaril to zadnjo točko tukaj.
Do te točke, sem imeti še en način, da se sklicuje na te vrste podatkov.
>> In to je samo referenčni podatkovni tip.
To, S tip podatkov struktura, ki vsebuje podatke,
in kazalec na drugo Struktura istega tipa.
Tako da moram imeti možnost, da se nanašajo na Ta podatkovni tip vsaj začasno,
tako da mu daje začasna ime struct sllist
mi omogoča, da potem reči Hočem kazalec na drugo struct sllist,
struct sllist zvezda, nato pa ko sem zaključila z opredelitvijo,
Zdaj lahko imenujemo ta tip sll vozlišče.
>> Torej, to je, zakaj vidite tam začasno ime tukaj,
ampak stalna ime tukaj.
Včasih boste morda videli definicije strukture,
na primer, da niso samo referenčna, da
nimajo tu ime določilo.
To bi šele rekli typedef struct, odpreti kodrasti opornico, nato pa ga definirati.
Ampak, če ste struct je self referenčno, saj je to ena stvar,
morate določite začasno ime tipa.
Ampak na koncu, zdaj da smo to storili,
bomo lahko sklicujejo le na ti vozlišča te enote,
kot SLL vozlišč za namene preostalega ta video.
>> Vse je v redu, tako da vemo, kako ustvarijo povezani seznam vozlišče.
Vemo, kako opredeliti vezavni seznam vozlišče.
Zdaj, če bomo za začetek jih uporabljajo za zbiranje informacij,
tam je nekaj operacij smo morajo razumeti in delati.
Moramo vedeti, kako ustvariti vezavni seznam iz zraka.
Če ni seznam že, želimo začeti eno.
Torej moramo biti sposobni ustvariti povezan seznam,
moramo verjetno iskati po seznamu povezavo
poiščite element, ki ga iščemo.
Moramo biti sposobni vstaviti nove stvari v seznamu,
želimo naš seznam, da bi lahko rasla.
In podobno, želimo, da bi lahko izbrisati stvari iz našega seznama,
želimo naš seznam, da bi lahko skrči.
In na koncu našega programi, zlasti
če se spomnimo, da smo dinamično dodeljevanje pomnilnika
za izgradnjo te sezname običajno, želimo osvoboditi vse te spomin
ko končamo delo z njim.
In zato moramo biti sposobni izbrisati Celoten povezani seznam, v enem ne Nalet.
Torej pojdiva skozi nekateri od teh postopkov
in kako bi jih vizualizirati, govoril v psevdokoda kodo posebej.
Torej želimo ustvariti povezani seznam, tako da morda smo
želeli določiti funkcijo s tem prototipom.
sll vozlišče zvezda, ustvarjanje, in sem mimo v enem argumentu, nekateri samovoljno podatki
tip spet neke samovoljno vrste podatkov.
Ampak jaz sem returning-- to funkcijo naj bi vrne k meni kazalec, da za enkrat
povezani seznam vozlišče.
Spet smo poskušali ustvariti vezavni seznam iz zraka,
tako da moram kazalec na ta seznam, ko bom končal.
>> Torej, kaj so koraki, ki sodelujejo tukaj?
No, prva stvar, ki sem tekoč storiti, je dinamično
dodeli prostor za novo vozlišče.
Spet smo ga ustvarili iz tanke zraka, zato moramo malloc prostora za njo.
In seveda takoj ko smo malloc,
smo vedno preverite, da je naš pointer-- nismo dobili nazaj null.
Ker če bomo poskušali Priklanjanje null kazalec,
bomo trpeti segfault in ne želimo, da.
>> Potem smo želeli zapolniti na tem področju, želimo inicializacijo polja vrednosti
in inicializacijo naslednje polje.
In potem smo se želeli to-- koncu kot Funkcija prototip indicates-- želimo
vrne kazalec na SLL vozlišče.
Torej, kaj bi to izgledal vizualno?
No, najprej bomo dinamično dodeli prostor za novo SLL vozliščem
zato smo malloc-- da je vizualna reprezentacija
vozlišča smo pravkar ustvarili.
In smo preverite, to ni null-- v tem primeru,
slika ne bi imela prikazano gor, če je bila nična,
mi pa bi zmanjkalo pomnilnika, tako da smo na dobri poti tja.
Torej, zdaj smo na korak C, inicializacijo polja vozlišča vrednosti.
No, glede na to funkcijo poklical sem z igro,
Izgleda želim opraviti v 6, tako da bom 6 v polju vrednosti.
Zdaj, inicializacijo naslednje polje.
No, kaj bom tam naredil, nič zraven, kajne,
to je edino v seznamu.
Torej, kaj je naslednja stvar na seznamu?
>> To ne bi smelo poudariti, da nič, kajne.
Nič drugega ni, kaj je koncept vemo, da je to nothing--
kazalci na nič?
Treba bi bilo morda želimo postaviti null kazalec tam,
in bom predstavljajo null kazalec kot le rdeče polje,
ne more iti več naprej.
Kot bomo videli malo kasneje, bomo morali sčasoma verige
puščic povezovanje ti vozlišča skupaj,
vendar, ko ste zadeli rdeče polje, ki je nična,
ne moremo iti dalje, da je konec seznama.
>> In nazadnje, hočemo samo vrne kazalec na tem vozlišču.
Torej bomo ga pokličete nov, in se bo vrnil novo
tako da se lahko uporablja pri karkoli funkcija je ustvaril.
Torej tam gremo, smo ustvarili posamezno povezani seznam vozlišče iz zraka,
in zdaj imamo seznam moremo delati.
>> Zdaj, recimo, smo že imajo veliko verigo
in želimo, da bi našli nekaj v njej.
In želimo funkcijo, ki se dogaja vrne true ali false, odvisno
o tem, ali obstaja vrednost na tem seznamu.
Funkcija prototip, ali Izjava za to funkcijo,
bi izgledal this-- bool najti, in potem želimo prenesti v dveh argumentov.
>> Prvi kazalec na Prvi element povezani seznam.
To je pravzaprav nekaj, kar boste vedno želeli, da bi spremljali,
in dejansko je lahko nekaj, kar si celo dal v globalne spremenljivke.
Ko ustvarite seznam, vedno, vedno
želijo, da bi spremljali zelo Prvi element seznama.
Na ta način se lahko nanašajo na vse druge Elementi, ki jih samo po verigo,
ne da voditi kazalce nedotaknjen, da vsak element.
Morate le, da spremljate prvi ena, če oni vsi priklenjen skupaj.
>> In potem druga stvar smo mimo znova
je samovoljno some-- ne glede na tip podatkov smo
išče obstajajo znotraj upamo eden izmed vozlišč v seznamu.
Torej, kaj so koraki?
No, prva stvar, ki mi je ustvarimo prečni kazalec
kaže na seznamih glavo.
No, zakaj smo to storili, smo že ima kazalec na seznamih verjeti,
zakaj ne bomo samo premaknete, da je eden okoli?
No, kot sem rekel, to je res pomembno za nas
da vedno spremljate Prvi element v seznamu.
In zato je dejansko boljša ustvariti dvojnik, ki,
in uporabo, da se premaknete okoli, tako da ne bomo nikoli nehote odmakne, ali smo vedno
imajo kazalec na neki točki, ki je prav na prvi element seznama.
Torej je bolje, da ustvarite Drugi, ki jih uporabljamo za premikanje.
>> Potem smo samo primerjati, ali polje vrednost na tem vozlišču
je tisto, kar smo iskali, in če je Ne, samo premaknete na naslednje vozlišče.
In bomo vztrajati početje, da več, in več, in več,
dokler ne bomo niti našli element, ali smo zadeli
null-- smo dosegli konec seznama in je ni tam.
To bi, upajmo, zvonil zvonec za vas, kot samo linearno iskanje,
smo samo posnemajo v za enkrat povezani seznam struktura
namesto z matriko, da to storite.
>> Torej, tukaj je primer za enkrat povezani seznam.
Ta je sestavljen iz pet vozlišč, in imamo
kazalec vodjo Seznam, ki se imenuje seznam.
Prva stvar, ki jo želite storiti, je ponovno ustvarite, da prečkanje kazalec.
Tako da imamo zdaj dve kazalce ki kažejo na isto stvar.
>> Zdaj, obvestilo tudi tukaj, nisem morali malloc nobenega prostora za trav.
Nisem rekel, trav enaka malloc nekaj, da je vozlišče že obstaja,
da je prostor v pomnilniku že obstaja.
Torej, vse sem pravzaprav počne, je ustvariti nov kazalec na njej.
Nisem mallocing dodaten prostora, samo imajo zdaj dve kazalce
kaže na isto stvar.
>> Torej je 2, kar iščem?
No, no, tako da namesto da sem dogaja, da se premaknete na naslednjo.
Torej v bistvu jaz bi rekel, trav trav enaka naslednji.
3, kar iščem, ne.
Tako sem še naprej iti skozi, dokler sčasoma
priti do 6, ki je tisto, kar sem iskal Za temelji na klicu funkcije
Moram na vrhu tam, in tako sem storil.
>> Zdaj, kaj če je element sem iščete, ni na seznamu,
se še vedno dogaja, da deluje?
No, opazil, da se seznam tukaj je nekoliko drugačna,
in to je še ena stvar, ki je pomembno pri povezanih seznamov,
nimate ohraniti jih v določenem vrstnem redu.
Lahko, če hočeš, ampak ste morda že opazili
da nismo sledenja kaj več element smo na.
>> In to je nekako eni trgovini, ki smo imajo s povezano seznamu verzov nizi,
se nimamo bralno več.
Ne moremo samo reči, želim iti v 0th element,
ali 6. element mojega array, ki lahko storim v matriki.
Ne morem reči, želim iti na 0. element, ali 6. element,
ali 25. element mojega povezanega seznama, ni indeks, povezane z njimi.
In tako v resnici ne važno če želimo ohraniti naš seznam v vrstnem redu.
Če želite, da vas seveda lahko, vendar pa je
Nobenega razloga ni, zakaj jih potrebujejo za shranijo v poljubnem vrstnem redu.
Torej še enkrat, poskusimo in našli 6 na tem seznamu.
No, bomo začeti izvajati začenja, ne bomo našli 6,
in potem bomo še naprej ne najde 6, dokler ne bomo na koncu dobili tukaj.
Torej, zdaj trav kaže na vozlišču vsebuje 8, in šest ni tam.
>> Tako da bi naslednji korak da gredo na naslednjo kazalec,
tako pravijo trav trav enaka naslednji.
No, trav zraven, označena z rdeče polje obstaja, je nična.
Torej obstaja nikjer drugje na iti, in zato na tej točki
lahko sklepamo, da smo dosegli Konec povezani seznam,
in 6 ne noter.
In bi se vrnil false v tem primeru.
>> OK, kako vstavite novo vozlišče v povezano seznamu?
Torej smo bili sposobni ustvariti vezavni seznam od nikoder,
vendar smo verjetno želeli izgradnjo verige in ne
ustvariti kup različnih seznamov.
Želimo, da imajo en seznam, ki ima kup vozlišč v njem,
ne kup seznamov z enim vozliščem.
Torej ne moremo kar naprej uporabljate Ustvari Funkcija smo opredelili že prej, zdaj smo
želite vstaviti v Seznam, ki že obstaja.
>> Torej tem primeru bomo prenesti v dveh argumentov,
kazalec z glavo, ki povezani seznam, ki ga želimo dodati.
Še enkrat, to je razlog, zakaj je tako pomembno je, da smo vedno
spremljate to, ker to je edini način, da res
imajo, da se nanašajo na celoten seznam samo s kazalcem na prvem elementu.
Torej želimo prenesti v kazalec na ta prvi element,
in ne glede na vrednost, ki jo želite dodati na seznam.
In na koncu je ta funkcija se dogaja, da se vrnete kazalec
novemu glavo povezanega seznama.
>> Kateri koraki so vključeni tukaj?
No, tako kot pri ustvarjanju, moramo dinamično dodeli
prostor za novo vozlišče, in preverite, prepričan, da ne bo zmanjkalo pomnilnika, še enkrat,
ker smo s pomočjo malloc.
Potem želimo zapolnijo in vstavite vozlišče,
tako dal številko, ne glede na val je v vozlišče.
Želimo, da vstavite vozlišče na začetek povezani seznam.
>> Obstaja razlog, da sem želeli, da to stori, in to
bi bilo vredno vzeti trenutek da začasno ustavite video tukaj,
in razmišljati o tem, zakaj bi hotel vstavite na začetku vezana
seznam.
Spet sem že prej omenil da to ni res
važno, če smo ga ohranili v vseh Da, tako da morda je to namig.
In ste videli, kaj bi se zgodilo, če bi Želeli to-- ali samo sekundo
nazaj, ko smo šli skozi iskanje si
lahko videli, kaj lahko se zgodilo, če bomo skušali
vstaviti na koncu seznama.
Ker ne bomo imeli kazalec na koncu seznama.
>> Torej razlog, da bi si želel vstaviti na začetku,
je zato, ker sem lahko to storite takoj.
Imam kazalec na začetku, in bomo to videli v vizualni v sekundi.
Ampak, če hočem vstaviti na koncu, Moram začeti na začetku,
prečkanje vso pot do konec, in ga nato prečenje.
Tako, da bi to pomenilo, da je vstavljanje na koncu seznama
bi postala o n delovanje, vrača
za našo razpravo računska zahtevnost.
To bi postalo o n delovanja, kjer kot seznam dobil večji in večji,
in večje, da bomo postali bolj in težje prečenje nekaj
na konec.
Ampak to je vedno zelo enostavno prečenje nekaj na na začetku,
ste vedno na začetku.
>> In bomo videli še vizualni tega.
In potem, ko bomo končali enkrat smo vstavili novo vozlišče,
želimo vrniti našo kazalec novi vodja povezanega seznama, ki
saj smo vstavljanje Na začenši bo dejansko
kazalec na vozlišče smo pravkar ustvarili.
Oglejmo vizualizirati to, ker mislim, da bom pomagal.
>> Torej, tukaj je naš seznam, je sestavljena iz štirje elementi, vozlišče, ki vsebuje 15,
kar kaže na vozlišču ki vsebuje 9, ki
kaže na vozlišče, ki vsebuje 13, kar kaže na vozlišče vsebuje
10, ki ima null kazalec kot svoji naslednji kazalec
tako da je konec seznama.
Zato želimo, da vstavite Novo vozlišče z vrednostjo 12
na začetku tega seznam, kaj naj naredimo?
No, najprej smo malloc prostor za vozlišče, nato pa dal 12 noter.
>> Torej, zdaj smo doseže Odločitev točka, kajne?
Imamo nekaj kazalci, da smo lahko
premakniti, eden od njiju naj gremo najprej?
Moramo narediti 12 točk do Novi vodja list--
ali oprostite, moramo narediti 12 opozarjajo na stari glavi seznama?
Ali bi morali reči, da je seznam zdaj se začne pri 12.
Tam je razlikovati tam, in bomo pogled
kaj se zgodi z obema v sekundi.
>> Toda to vodi do super tema za sidebar,
ki je, da je eden izmed najtežavnejših stvari s povezanimi seznami
je urediti kazalce v pravilnem zaporedju.
Če ste premakniti stvari v okvari, lahko končajo po nesreči
orphaning preostanek seznama.
In tukaj je primer tega.
Torej, pojdimo z idejo of-- dobro, smo pravkar ustvarili 12.
Vemo 12 se bo novi vodja seznama
in zakaj ne bi kar preselila seznam kazalec tam točko.
>> OK, tako da je dobro.
Torej, zdaj, ko pa 12 naslednjo točko?
Mislim, vizualno lahko vidimo, da bo to imelo za 15,
saj človeka je res očitno, da nas.
Kako računalnik vedeli?
Nimamo ničesar kaže, da 15 več, kajne?
>> Izgubili smo kakršno koli možnost, da se sklicujem na 15.
Ne moremo reči, novo puščico zraven enaka nekaj, nič ni tam.
V bistvu smo osiroteli preostanek seznama
s tem, ki smo jih po nesreči zlomili verigo.
In mi zagotovo ne želite, da to storim.
>> Torej vrnimo se in poskusite s tem še enkrat.
Mogoče je prava stvar je določiti 12 na naslednjo kazalec
na stari glavi seznama prvega, potem lahko gremo seznam čez.
In z dejstvom, da je pravilno, da bomo
morate slediti, ko smo delo s posamezno povezano seznama.
Vedno smo želeli povezati Nov element v seznamu,
preden smo vzeli to vrsto Pomemben korak spreminjanja
kjer je vodja povezanega seznama je.
Še enkrat, da je tako temeljna stvar, ne želimo, da bo zmanjkalo tem.
>> Zato želimo zagotoviti, da vse je priklenjen skupaj,
preden gremo ta kazalec.
In tako bi bilo to v pravilnem vrstnem redu, ki je povezati 12 na seznamu,
potem pa pravijo, da se seznam začne 12.
Če smo rekli, seznam se začne pri 12 in nato poskuša povezati 12 na seznamu,
smo že videli, kaj se zgodi.
Izgubimo seznam po pomoti.
>> OK, še ena stvar, da govoriti o tem.
Kaj pa, če želimo, da se znebite celotno povezan seznam naenkrat?
Spet smo mallocing vse to prostor, in tako smo
morate sprostiti, ko bomo končali.
Torej, zdaj smo želeli izbrisati celoten povezani seznam.
No, kaj želimo narediti?
>> Če smo dosegli null kazalec smo želeli ustaviti, sicer šele izbrisati
ostali na seznamu, nato pa me je osvobodil.
Izbrišite preostanek seznama, in nato sprostite trenutno vozlišče.
Kaj to zvok všeč, kaj tehniko smo govorili
o prej pa to zvok všeč?
Izbriši vsakogar drugega, potem vrnil in izbrisati me.
>> To je rekurzija, smo tokrat na problem malo manjši,
smo govoriš izbrisati vsakogar drugega, potem lahko izbrišete me.
In še naprej po cesti, ki vozlišče bodo rekli, izbrisati vsi ostali.
Ampak na koncu bomo dobili do točka, kjer je seznam null,
in to je naša baza primera.
>> Tako da je lahko pogled na to, in kako bi to lahko delovalo.
Torej, tukaj je naš seznam, to je enako Seznam smo samo govoriš,
in tam je korake.
Tam je veliko besedila tukaj, ampak upajmo, da bo vizualizacija pomaga.
>> Tako smo have-- in tudi jaz potegnil up naši konzoli okvirjev sliki
iz naše video na klic nizov, in upajmo, da vse to
skupaj vam bo pokazal, kaj se dogaja.
Torej, tukaj je naša psevdokoda koda.
Če bomo dosegli null kazalec, nehaj, sicer
izbrisati ostanek seznama, nato sprostiti trenutno vozlišče.
Torej sedaj, list-- kazalec, da smo
poteka v uničiti točk, do 12.
12 ni null kazalec, tako da smo dogaja, da se črta preostanek seznama.
>> Kaj je izbrisali ostali vpleteni?
No, to pomeni izdelavo klic, da se uniči, rekoč:
da 15 je na začetku Preostanek seznamu želimo uničiti.
In zato je poziv, da se uniči 12 je nekako na čakanju.
Prav tam je zamrznjen, čakanja na klic, da se uniči 15, da konča svoje delo.
>> No, 15 ni null kazalec, in tako da je hotel reči, vse v redu,
dobro, izbrišite preostanek seznama.
Preostanek seznama začne ob 9., tako da bomo in samo
počakajte, dokler ne boste izbrisali vse, stvari, potem pa pridi nazaj in izbrisati me.
No 9 dogaja reči, dobro, Nisem null kazalec,
tako izbrisati ostanek seznam od tukaj.
In zato poskusite in uničiti 13.
13 pravi, da nisem null kazalec, Ista stvar, saj prehaja buck.
10 ni null kazalec, 10 vsebuje null kazalec,
ampak 10 je sam po sebi ni null kazalec prav zdaj,
in tako prehaja buck preveč.
>> In zdaj seznam točk tam, ga Res bi opozoril, da some--
če bi imel več prostora v sliki, da bi opozoril na nekaj naključno prostor
da ne vemo, kaj je to.
To je null kazalec, čeprav seznam je dobesedno sedaj nastavljena je vrednost null.
To se kaže prav znotraj tega rdečega polja.
Dosegli smo null kazalec, tako moremo ustaviti, in smo končali.
>> In da vijolična okvir je now-- Na Vrh stack-- da je aktivna okvir,
vendar pa je to storjeno.
Če smo dosegli ničelni kazalec, stop.
Mi ne storiti ničesar, smo ni mogel znebiti null kazalec,
nismo malloc koli prostor, in tako smo storili.
Torej, to funkcijo okvirja uniči, in smo
resume-- bomo pick up, kjer se nam z leve off z naslednjo najvišjo enega, ki
je ta temno modra frame tukaj.
Tako smo dvignili tam, kjer smo končali.
Mi črta ostalega seznam že, zdaj smo
bo osvobodil sedanjih vozlišč.
Torej, zdaj smo lahko osvobodi to vozlišče, in zdaj smo prišli do konca funkcije.
In tako je ta funkcija okvir uničena, in smo se dvignili na svetlo modri.
>> Tako je says-- sem že done-- brisanje preostanek seznama, tako da
sprostiti trenutno vozlišče.
In zdaj je dobil rumeni okvir je nazaj na vrhu kupa.
In tako, kot vidite, mi smo zdaj uničevanje seznama od desne proti levi.
>> Kaj bi se zgodilo, čeprav, če smo naredili stvari v napačno smer?
Tako kot ko smo poskušali dodati element.
Če bomo zamočil verige, če je nismo povezati kazalce
v pravilnem vrstnem redu, če bomo Samo sprosti prvi element,
če smo le osvobodil Vodja seznamu, zdaj smo
ne način, da se sklicujem preostanek seznama.
In tako bi imeli osiroteli vse,
mi pa bi imeli kaj imenujemo pomnilnika.
Če se spomnite iz naše video na dinamično dodeljevanje pomnilnika,
da ni zelo dobra stvar.
>> Torej, kot sem rekel, ni več operacij
da moramo uporabiti za delo učinkovito povezani seznam.
In ste morda opazili izpustijo enega sem, brisanje en sam element iz povezanega
seznam.
Razlog, da sem storil, da je, da je pravzaprav neke vrste
težavno, da razmišljajo o tem, kako izbrisati en sam element od A enkrat
povezani seznam.
Moramo biti sposobni preskočiti Nekaj ​​na seznamu, ki je
pomeni, da smo prišli do Point-- mi želite izbrisati ta node--
ampak, da bi bi bilo, zato smo ne izgubijo vse informacije,
moramo povezati ta node tukaj, tukaj.
>> Torej sem verjetno naredil narobe vizualnega vidika.
Torej smo na začetku našega seznam, mi nadaljujemo skozi,
želimo izbrisati to vozlišče.
Če smo ga šele izbrisati, smo zlomili verigo.
To vozlišče tukaj nanaša na vse ostalo,
da vsebuje verigo od tu naprej.
>> Torej, kaj moramo storiti, dejansko potem, ko smo prišli do te točke,
se moramo korak nazaj eno, in povezati to vozlišče v to vozlišče,
tako da bomo lahko nato izbrišite tista na sredini.
Ampak posamič povezani seznami ne da nam je pot nazaj.
Zato moramo bodisi obdržati dva kazalca, in jih premakniti
nekako off koraku, eden za drugo, ko gremo, ali priti do točke
in nato pošlje drugo kazalec skozi.
In kot vidite, jo lahko dobili malo grdo.
Na srečo smo imeli še en način rešiti da,
ko govorimo o dvakrat povezanih seznamov.
>> Sem Doug Lloyd, to je CS50.