>> [MUZIKO Ludante]
>> DOUG LLOYD: Bone, do ĉe tiu punkto de la kurso,
ni kovris multon de la basics de C. Ni scias tre pri variabloj, tabeloj,
punteros, cxiuj bonaj aĵoj.
Tiuj estas ĉiuj ia konstruita en vidi kiel la fundamentals,
sed ni povas fari pli, ĉu ne?
Ni povas kombini aferojn kune en interesaj manieroj.
>> Kaj do ni faru tion, ni komencu disbranĉigi el kio C donas ni,
kaj komenci krei nian propran datumoj strukturoj uzante tiujn konstruaĵo
blokoj kune fari ion vere valora, utila.
Unu vojo ni povas fari tion estas paroli pri kolektoj.
Do ĝis nun ni havis unu speco de datumoj strukturon por reprezenti kolektoj
de ŝati valoroj, similajn valorojn.
Tio estus tabelo.
Ni havas kolektojn de entjeroj, aŭ kolektoj de karakteroj kaj tiel plu.
>> Strukturoj ankaŭ ordigi de datumoj strukturon por kolekti informojn,
sed ĝi ne estas por kolektado kiel valoroj.
Ĝi kutime miksas malsamajn datumtipoj kune ene de sola skatolo.
Sed ĝi ne estas mem uzita ĉeni kune
aŭ kunligi simila erojn, kiel tabelo.
Arrays estas grandaj por elemento rigardu supren sed revokon
ke ĝi estas tre malfacila enmeti en tabelo,
se ni enmeto ĉe la fino de tiu tabelo.
>> Kaj la plej bona ekzemplo mi havas cxar tion inserción varon.
Se vi memoras nian video sur inserción varo,
tie estis multa elspezo implikita en havi
kapti elementojn, kaj movas ilin de la vojo konveni ion
en la mezo de via tabelo.
Arrays ankaŭ suferas de alia problemo, kiu estas inflexibilidad.
Kiam ni deklaras tabelo, ni preni unu pafon ĉe ĝi.
Ni alvenas al diri, mi volas tio multaj elementoj.
Povus esti 100, oni eble esti 1000, oni eble
estu x kie x estas numero kiu la uzanto donis nin ĉe prompto aŭ ĉe la komando
linio.
>> Sed ni nur akiras unu frapon al ĝi, ni ne atingos tiam diru ho, fakte mi
bezonis 101, aŭ mi bezonis x plus 20.
Tro malfrue, ni jam deklaris la tabelo, kaj se ni volas akiri 101 aŭ x
plus 20, ni devas deklari tute alia tabelo,
kopii ĉiujn elementojn de la tabelo super, kaj tiam ni havas sufiĉe.
Kaj kion se ni malpravas denove, kio se ni vere bezonas 102, aŭ x plus 40,
Ni devas fari tion denove.
Do ili estas tre nefleksebla por regrandigi niaj datumoj,
sed se ni kombinas kune iuj de la basics ke ni jam
lernis pri punteros kaj strukturoj, precipe uzante dinamika memoro
atribuo kun malloc, ni povas meti tiujn pecojn kune
krei novajn datumojn structure-- a unuope ligillisto ni povus say--
kiu permesas kreski kaj ŝrumpi kolekto de valoroj
kaj ni ne havos ajnan malŝparita spaco.
>> Do denove, ni nomas tiun ideon, ĉi nocio, ligillisto.
En aparta, en tiu video ni estas parolas sole ligillisto,
kaj poste alia vídeo ni parolos proksimume duoble ligitaj listoj, kiuj
estas nur variaĵo pri temo ĉi tie.
Sed unuope ligita listo konsistas el nodoj,
nodoj nur esti abstrakta term-- estas nur io mi vokas
jen ian strukturo, resume, mi estas?
Nur tuj nomas ĝin node-- kaj ĉi nodo havas du membroj, aŭ du kampoj.
Ĝi havas datumojn, kutime entjero, karaktero kaleŝego,
aŭ povis esti iu alia datumtipo ke vi difinis kun tipo def.
Kaj ĝi enhavas montrilon al alia nodo de la sama tipo.
>> Do ni havas du aferoj ene de tiu nodo, datumoj kaj puntero
al alia nodo.
Kaj se vi komencas visualizar tiu, vi povas pensi pri ĝi
kiel ĉeno de nodoj kiuj estas konektitaj kune.
Ni havas la unua nodo, ĝi enhavas datumon, kaj montrilo
al la dua vertico, kiu enhavas datumoj, kaj montrilo al la tria nodo.
Kaj tiel tio estas kial ni vokas ĝin ligillisto, ili estas ligitaj kune.
>> Kion faras ĉi speciala nodo strukturo aspektas?
Nu, se vi memoras de nia vídeo sur difinanta kutimo tipoj, kun tipo def,
ni povas difini structure-- kaj tajpu difini strukturon kiel tiu.
tyepdef struct sllist, kaj tiam mi uzante la vorto valoro tie arbitre
indiki ajnan datumtipo vere.
Vi povus pasi sur entjero aŭ kaleŝego, vi povus havi kion vi volas.
Ĝi ne estas limigita al nur entjeroj, aŭ io simila.
Do valoro estas nur arbitra datumtipo, kaj tiam puntero
al alia nodo de la sama tipo.
>> Nun, ekzistas iom kaptaĵo tie kun difinanta strukturo
kiam ĝi estas mem referenca strukturo.
Mi devas havi portempa citi por mia strukturo.
Fine de la tago mi klare volas nomi ĝin
SLL nodo, jen finfine la nova citi parton de mia tipo difino,
sed mi ne povas uzi SLL nodo en la mezo de ĉi tiu.
La kialo estaĵo, mi ne kreis tipo nomita SLL nodo
ĝis mi trafis tiun fina punkto tie.
Supren ĝis tiu punkto, mi devas havi alia maniero aludi al tiu datumtipo.
>> Kaj tiu estas mem referenca datumtipo.
Ĝi; s datumtipo de strukturo kiu enhavas datumojn,
kaj puntero al alia strukturo de la sama tipo.
Do mi bezonas por povi rilati al tiu datumtipo almenaŭ temporalmente,
tiel donante provizoran nomo de struct sllist
min permesas tiam diru mi volas montrilon al alia struct sllist,
struct sllist stelo, kaj tiam post mi kompletigis la difinon,
Mi povas nun nomas tiun tipon de SLL nodo.
>> Tial do komprenu ke estas provizora nomo tie,
sed permanenta nomo tie.
Foje vi povus vidi difinoj de strukturo,
ekzemple, kiuj ne memo referenca, ke
ne havas especificación nomo tie.
Estus ĝuste diri typedef struct, malfermi krispa streĉa kaj tiam difini ĝin.
Sed se vi estas struct estas mem referenca, kiel ĉi tiu estas,
vi devas specifi provizora tipo nomo.
Sed finfine, nun ke ni faris tion,
ni povas simple raporti al tiuj nodoj, tiuj unuoj,
kiel SLL nodoj por celoj de la resto de ĉi tiu video.
>> Bone, do ni scias kiel krei ligillisto nodo.
Ni scias kiel difini ligillisto nodo.
Nun, se ni tuj komencos uzante ilin por kolekti informojn,
ekzistas kelkaj operacioj ni bezonas kompreni kaj labori kun.
Ni bezonas scii kiel krei ligillisto el maldika aero.
Se ne estas lerta jam, ni volas komenci.
Do ni devas esti kapabla krei ligillisto,
ni bezonas probable serĉi tra la ligon listo
trovi elementon ni serĉas.
Ni bezonas por povi enŝovi novajn objektojn en la listo,
ni volas nian liston por povi kreski.
Kaj simile, ni volas povi forigi aĵojn de nia listo,
ni volas nian liston por povi ŝrumpi.
Kaj fine de nia programojn, speciale
se vi memoras ke ni estas dinamike asignante memoron
konstrui tiuj listoj tipe, ni volas liberigi ĉiujn ke memoro
kiam ni faris laboranta kun ĝi.
Kaj do ni bezonas por povi forigi tuta ligillisto en unu malsukcesos plonĝo.
Do ni iru tra iuj de ĉi tiuj operacioj
kaj kiel ni povus bildigi ilin, parolante en _pseudocode_ kodo specife.
Do ni volas krei ligillisto, do eble ni
volas difini funkcio kun ĉi tiu prototipo.
SLL nodo stelo, krei, kaj mi pasante en unu argumento, iuj arbitraj datumoj
tajpi denove, de iu arbitra datumtipo.
Sed mi returning-- tiu funkcio devas revenos al mi montrilo, al unuope
ligillisto nodo.
Denove, ni provas krei ligillisto el maldika aero,
do mi bezonas montrilon al tiu listo, kiam mi faris.
>> Do kio estas la paŝoj implikita tie?
Nu, unue mi estas tuj faros estas dinamike
destini spaco por nova nodo.
Denove, ni kreas ĝin el maldika aero, tiel ni devas malloc spaco por tio.
Kaj kompreneble, tuj post ni malloc,
ni ĉiam kontroli por certiĝi ke nia pointer-- ni ne reiri nula.
Ĉar se ni provas kaj cedemo nula puntero,
ni tuj suferos segfault kaj ni ne volas tion.
>> Tiam ni volas plenigi la kampon, ni volas pravalorizi la valoro kampo
kaj pravalorizi la sekva kampo.
Kaj poste ni volas to-- eventuale kiel la funkcio prototipo indicates-- ni volas
reveni puntero al SLL nodo.
Do kio faras ĉi aspekti vide?
Nu, unue ni tuj dinamike destini spaco por nova SLL nodo,
do ni malloc-- tio vida reprezentado
de la nodo ni simple kreitaj.
Kaj ni kontroli por certiĝi ĝi ne null-- tiukaze
la bildo ne havus montris supren, se ĝi estis nula,
ni estus kuri el memoro, do ni estas bonaj iri tien.
Do nun ni estas sur paŝi C, pravalorizi la nodoj valoro kampo.
Nu, bazita sur ĉi tiu funkcio vokas mi uzas tie,
aspektas kiel mi volas pasi en 6, Do mi devos 6 en la valoro kampo.
Nun, pravalorizi la sekva kampo.
Nu, kion mi povos fari tie, nenio estas proksima, dekstra,
ĉi estas la sola afero en la listo.
Do kio estas la sekvanta afero en la listo?
>> Ĝi ne devus celi ion, dekstre.
Ekzistas nenio pli, do kio estas la koncepto ni scias de tio nothing--
punteros al nenio?
Devus esti eble ni volas meti nula puntero tie,
kaj mi reprezentas la nula Pointer kiel ĝuste ruĝan skatolon,
ni ne povas iri plu.
Kiel ni vidos iom pli poste, ni devos eventuale ĉenoj
de sagoj konektanta tiuj nodoj kune,
sed kiam vi frapis la ruĝa skatolo, jen nula,
ni ne povas iri plu, tio estas la fino de la listo.
>> Kaj laste, ni nur volas reveni puntero al tiu nodo.
Do ni nomas ĝin novan, kaj revenos nova
do ĝi povas esti uzata en ajn funkcio kreis.
Do tie ni iras, Ni kreis unuope ligillisto nodo el maldika aero,
kaj nun ni havas liston ni povas labori kun.
>> Nun, diru ni jam havas grandan ĉenon,
kaj ni volas trovi ion en ĝi.
Kaj ni volas funkcio kiu okazas reveni vera aŭ malvera, depende
sur ĉu valoro ekzistas en tiu listo.
Funkcio prototipo, aŭ deklaro por tiu funkcio,
povus aspekti this-- bool trovi, kaj tiam ni volas pasi en du argumentojn.
>> La unua, estas puntero al la unua elemento de la ligitaj listo.
Tiu estas efektive io vin timige Ĉiam volas konservi trako de,
kaj fakte povus esti iu kiu vi eĉ metis en tutmonda variablo.
Unufoje vi krei liston, vi ĉiam, ĉiam
volas konservi trako de la tre unua elemento de la listo.
KE vojo vi povas referi al ĉiuj aliaj elementoj per ĝuste sekvante la ĉeno,
sen devi teni punteros nerompita por ĉiu ununura ero.
Vi nur bezonas konservi trakon de la unua unu se ili ĉiuj ĉenitaj kune.
>> Kaj tiam la dua afero ni pasante en denove
estas arbitre some-- ajn datumtipo ni estas
serĉanta ekzistas ene de espereble unu el la nodoj en la listo.
Do kio estas la paŝoj?
Nu, la unua aĵo kiun ni faras estas ni krei transversaj montrilon
indikante la lertaj kapo.
Nu, kial ni faru tion, ni jam havas puntero en la lertaj kapon,
kial ni ne simple proponas ke oni ĉirkaŭe?
Nu, kiel mi ĵus diris, ĝi estas vere grava por ni
ĉiam sekvigi la tre unua elemento en la listo.
Kaj tiel ĝi estas fakte pli bona krei duplikaton de tio,
kaj uzi tiun moviĝi ĉirkaŭ tiel ni neniam hazarde malproksimigi, aŭ ni ĉiam
havas puntero en iu punkto kiu estas ĝuste sur la unua elemento de la listo.
Do estas pli bone krei dua kiu ni uzas por deloki.
>> Tiam ni simple kompari ĉu la valoro kampo ĉe tiu nodo
kion ni serĉas, kaj se ĝi estas Ne, ni simple movi al la sekva nodo.
Kaj ni tenas faranta tion super kaj super kaj super,
ĝis ni ĉu trovi la elemento, aŭ ni trafis
null-- ni atingis la finon de la listo kaj ĝi ne estas tie.
Tio devus espereble sonorigi sonorilo al vi, kiel lineara serĉo,
ni nur repliki ĝin en oni unuope ligillisto strukturo
anstataŭ uzi tabelo por fari ĝin.
>> Do jen ekzemplo de oni unuope ligita listo.
Ĉi tiu konsistas kvin nodoj, kaj ni havas
sagon al la kapo de la listo, kiu nomigxas listo.
La unua afero ni volas fari estas denove, krei ke trairado montrilo.
Do ni havas nun du punteros tiu punkto ĝis la sama afero.
>> Nun, rimarki tie ankaŭ, mi ne havas malloc neniun spacon trav.
Mi ne diris trav egalas malloc io, ke nodo jam ekzistas,
ke spaco en memoro jam ekzistas.
Tiamaniere mi fakte faras estas krei alian puntero al ĝi.
Mi ne mallocing plia spaco, nur havas nun du punteros
montrante la saman aferon.
>> Do estas 2 kion mi serĉas?
Nu, ne, tiel anstataŭe mi estas tuj movi al la venonta unu.
Do resume mi dirus, trav egalas trav sekva.
Ĉu 3 kion mi serĉas, ne.
Do mi daŭrigas iri tra, ĝis fine
atingos 6 kiu estas kion Mi serĉas cxar bazita sur la funkcia alvoko
Mi havas ĉe la supro tie kaj do mi faris.
>> Nun, kio se la elemento mi serĉas ne estas en la listo,
estas ankoraŭ iranta labori?
Nu, rimarki ke la listo tie estas subtile malsama,
kaj ĉi tio estas alia afero, ke estas grava kun ligitaj listoj,
vi ne devas konservi ilin en ajna aparta ordo.
Vi povas se vi volas, sed Vi eble jam rimarkis
ke ni ne konservanta trako de kiu nombro elemento ni estas ĉe.
>> Kaj tio estas speco de unu komerco kiu ni havi kun ligillisto versoj arrays,
Estas tio ni ne havas hazarda aliro anymore.
Ni ne povas simple diri, mi volas iri al la 0th elemento,
aŭ la 6a elemento de mia tabelo, kion mi povas fari en tabelo.
Mi ne povas diri mi volas iri al la 0th elemento, aŭ la 6-a elemento,
aŭ la 25a ero de mia ligillisto, ekzistas neniu indekso asociita kun ili.
Kaj tiel ĝi ne vere gravas Se ni konservas nian liston en ordo.
Se vi volas vi certe povas, sed ekzistas
ne tial ili bezonas konserviĝi en iu ajn ordo.
Do denove, ni provu kaj trovi 6 en tiu listo.
Nu, ni starti je la komencante, ni ne trovas 6
kaj poste ni daŭre ne trovante 6, ĝis ni finfine atingos tie.
Do ĝuste nun trav punktoj al la nodo enhavanta 8 kaj ses ne estas en tie.
>> Do la sekva paŝo estus iri al la sekvanta puntero,
tiel diru trav egalas trav sekva.
Nu, trav sekva, indikita per la ruĝa skatolo tie, estas nula.
Do ekzistas nenie alie al iru, do ĉe tiu punkto
Ni povas konkludi ke ni atingis la fino de la ligillisto,
kaj 6 ne estas en tie.
Kaj estus revenis malvera en ĉi tiu kazo.
>> OK, kiel ni enŝovu nova nodo en la ligitaj listo?
Do ni povis krei ligillisto el nenie,
sed ni probable volas konstrui ĉenon kaj ne
krei aron de apartaj listoj.
Ni volas havi unu liston ke havas aron da nodoj en ĝi,
Ne faskon da listoj kun ununura nodo.
Do ni ne povas simple observu uzante la Create funkcio ni difinis pli frue, nun ni
volas enmeti enen lerta kiu jam ekzistas.
>> Do tiu kazo, ni tuj Iam en du argumentoj,
la puntero al la estro de tiu ligillisto ke ni volas aldoni.
Denove, tio estas kial ĝi estas tiel Gravas ke ni ĉiam
sekvigi ĝin, ĉar ĝi estas la nura maniero ni vere
devas rilati al la tuta listo estas nur montrilo al la unua elemento.
Do ni volas pasi en montrilon al tiu unua elemento,
kaj kion ajn valoron ni volas aldoni al la listo.
Kaj fine ĉi tiu funkcio tuj revenos montrilo
al la nova estro de ligitaj listo.
>> Kiuj estas la paŝoj implikita tie?
Nu, simile kun krei, ni bezonas dinamike asigni
spaco por nova nodo, kaj kontrolu fari Ni ja ne elĉerpas de memoro, denove,
ĉar ni uzas malloc.
Tiam ni volas popoli kaj enmeti la nodo,
tiel metis la numeron ajn val estas, en la nodo.
Ni volas enmeti la nodo ĉe la komenco de la ligitaj listo.
>> Tie estas kialo ke mi volas fari tion, kaj ĝi
eble valorus prenante duan paŭzi la video ĉi tie,
kaj pensas kial mi volus enmeti komence de ligitaj
lerta.
Denove, mi menciis antaŭe ke ĝi ne vere
gravas se ni konservu ĝin en ajna ordo, do eble tio estas postsigno.
Kaj vi vidis kion okazus se ni volis to-- aŭ el nur dua
antaŭe kiam ni iris tra serĉo vin
povis vidi kio povus okazi se ni provis
enmeti fine de la listo.
Ĉar ni ne havas sagon al la fino de la listo.
>> Do la kialo ke mi volas enmeti komence,
Estas ĉar mi povas fari ĝin tuj.
Mi havas puntero komence, kaj ni vidas tion en vida en sekundo.
Sed se mi volas enmeti fine, Mi devas komenci ĉe la komenco,
_traverse_ tutan vojon al la fino, kaj tiam najlu gxin plu.
Do tio signifus ke enmeto fine de la listo
igus o de n operacio, revenanta
al nia diskuto de komputa komplekseco.
Estus fariĝis o de n operacio, kie kiel la listo atingis pli grandan, kaj pli granda,
kaj pli granda, ĝi fariĝos pli kaj pli malfacile najlu ion
sur fine.
Sed estas ĉiam vere facila najlu ion sur komence,
vi estas ĉiam komence.
>> Kaj ni vidos vida de ĉi denove.
Kaj poste iam ni faris, fojo ni insertos la nova nodo,
ni volas reveni al niaj montrilon la nova kapo de ligitaj listo, kiu
ekde ni enmeto en la komencante, fakte estos
sagon al la nodo ni simple kreitaj.
Ni bildigi tion, ĉar mi pensas ĝi helpos.
>> Do jen nia listo, ĝi konsistas el kvar elementoj, nodo enhavanta 15,
kiu notas al nodo enhavanta 9, kiu
notas al nodo enhavanta 13, kiu notas al nodo enhavanta
10, kiu havas la nulan montrilo kiel lia sekva puntero
Do jen la fino de la listo.
Do ni volas enmeti nova nodo kun la valoro 12
komence de tiu ĉi listo, kion ni faru?
Nu, unue ni malloc spaco por la nodo, kaj tiam ni metis 12 en tie.
>> Do nun ni atingis decido punkto, dekstra?
Ni havas kelkajn punteros kiu ni povis
movi, kiun oni devus nin movi unue?
Ĉu ni faru 12 punkto la nova kapo de la list--
aŭ pardonu, devus nin fari 12 fingromontras la malnova kapo de la listo?
Sed se ni diros, ke la listo nun komencas ĉe 12.
Ekzistas distingo tie kaj ni esploros
ĉe kio okazas kun ambaŭ en sekundo.
>> Sed tio kondukas al grandan temon por sidebar,
kiu estas tiu de la trickiest aferoj kun ligitaj listoj
estas aranĝi la montriloj en la ĝusta ordo.
Se vi movas aferoj misfunkcias, vi povas fini hazarde
orphaning la resto de la listo.
Kaj jen ekzemplo de tio.
Do ni iru kun la ideo of-- bone, ni ĵus kreita 12.
Ni scias 12 tuj estos la nova kapo de la listo,
kaj do kial ni ne simple movi la listo puntero atentigi tie.
>> Bone, do tio estas bona.
Do nun kie faras 12 sekva punkto?
Mi volas diri, vide povas vidi ke indikos al 15,
kiel homoj estas vere evidenta al ni.
Kiel la komputila scias?
Ni ne havas ion indikante 15 plu, bone?
>> Ni perdis ajnan kapablon rilati al 15.
Ni ne povas diri novaj sago sekva egaluloj io, nenio estas tie.
Fakte, ni orfinoj la resto de la listo
farante tiel, ni hazarde rompis la ĉenon.
Kaj ni certe ne volas fari tion.
>> Do ni iru reen kaj provi tion denove.
Eble la ĝusta por fari estas fiksi 12 La sekva puntero
al la malnova kapo de la listo unue tiam ni povas movi la liston super.
Kaj fakte, tio estas la ĝusta ordo ke ni
bezonas sekvi kiam ni estas laborante kun unuope ligita listo.
Ni ĉiam volas konekti la nova elemento en la listo,
antaŭ ni preni tian grava paŝo de ŝanĝanta
kie la kapo de la ligitaj listo estas.
Denove, tio estas tia fundamenta afero, ni ne volas perdi trakon de ĝi.
>> Do ni volas certigi, ke ĉio estas ĉenitaj kune,
antaŭ ni movas tiu puntero.
Kaj tiel ĉi tio estus la ĝusta ordo, kiu estas konekti 12 al la listo,
tiam diru, ke la listo komenciĝas 12.
Se ni diris la listo komenciĝas ĉe 12 kaj tiam provis konekti 12 al la listo,
Ni jam vidis kio okazas.
Ni perdos la listo erare.
>> Bone, do unu pli da afero paroli.
Kio se ni volas forigi tutan ligillisto tuj?
Denove, ni mallocing ĉiuj tiu spaco, kaj tiel ni
bezonas liberigi ŝin kiam ni faris.
Do nun ni volas forigi la tutan ligillisto.
Nu, kion ni volas fari?
>> Se ni atingis la nula puntero, ni volas ĉesigi, alie, nur forigi
la resto de la listo kaj poste liberigi min.
Forigi la resto de la listo, kaj tiam liberigi la nuna nodo.
Kion signifas tiu sono kiel, kio tekniko ni parolis
pri antaŭe faras tiun sonon kiel?
Forigi ĉiuj aliaj, tiam revenu kaj forigi min.
>> Tio rekursio, ni faris la problemo iomete pli malgranda,
ni dirante forviŝi ĉiuj alia, tiam vi povas forigi min.
Kaj cetere malsupren la vojo, ke nodo diros, forigi ĉiuj aliaj.
Sed fine ni atingos la punkto kie la listo estas nula,
kaj jen nia bazo kazo.
>> Do ni rigardu ĉi, kaj kiel ĉi povus labori.
Do jen nia listo, ĝi estas la sama listo ni ĵus parolis,
kaj jen la paŝoj.
Ekzistas multe de teksto ĉi tie, sed espereble la videbligo helpos.
>> Do ni have-- kaj mi ankaŭ tiris ĝis nia stako kadroj ilustraĵo
de nia vídeo sur alvoko stakoj, Kaj espereble ĉio ĉi
kune montros vin kio okazas.
Do jen nia _pseudocode_ kodon.
Se ni atingas nula montrilon, ĉesu, alie,
forigi la reston de la listo, tiam liberigi la nuna nodo.
Do nun, list-- la puntero kiu ni estas
pasante por pereigi poentoj al 12.
12 estas ne nula puntero, tial ni estas tuj forigi la reston de la listo.
>> Kio viŝante la ni aliaj implikitaj?
Nu, ĝi signifas fari voki detrui, dirante
ke 15 estas la komenco de la resto de la listo ni volas detrui.
Kaj tiel la alvoko detrui 12 afablas sur tene.
Ĝi estas frostigita tie, atendante la voki detrui 15, por fini lian laboron.
>> Nu, 15 estas ne nula puntero, kaj tiel estas tuj diri, bone,
bone, forigi la reston de la listo.
La resto de la listo komenciĝas ĉe 9, kaj tiel ni simple
atendu ĝis vi forigi ĉiu tio ŝtofo, poste revenu kaj forigi min.
Nu 9 tuj diri, nu, Mi ne estas nula puntero,
do forigi la reston la lerta de ĉi tie.
Kaj tiel provi kaj detrui 13.
13 diras, mi ne estas nula puntero, samon, pasas la dolaron.
10 estas ne nula puntero, 10 enhavas nula puntero,
sed 10 ne estas mem nula puntero nun,
kaj tiel pasas la dolaron tro.
>> Kaj nun listo punktoj tie, vere notus al some--
se mi havus pli spaco en la bildo, ĝi notus al iu hazarda spaco
ke ni ne scias, kio ĝi estas.
Ĝi estas la nula puntero kvankam, la listo Estas laŭvorte nun starigis estas valoroj nula.
Ĝi estas indikante tute interne tiu ruĝa skatolo.
Ni atingis nula puntero, do ni povas halti, kaj ni faris.
>> Kaj por ke purpura kadro estas now-- ĉe la supro de stack-- jen la aktiva kadro,
sed ĝi estas farita.
Se ni atingis nula puntero, ĉesi.
Ni ne faru ion ajn, ni ne povas liberigi nula puntero,
ni ne malloc ajnan spaco, kaj tiel ni faris.
Por ke funkcio kadro estas detruita, kaj ni
resume-- ni reprenos kie ni maldekstre for kun la venonta plej alta unu, kiu
Estas ĉi malhelblua kadro tie.
Do ni repreni ĝuste kie ni cxesis.
Ni viŝis la cetera listo jam, do nun ni estas
tuj liberigi la nuna nodoj.
Do nun ni povas liberigi tiun nodon, kaj nun ni atingis la finon de la funkcio.
Kaj por ke funkcio kadro estas detruitaj, kaj ni reprenos en la lumo blua.
>> Do says-- Mi jam done-- viŝante la resto de la listo, tiel
liberigi la nuna nodo.
Kaj nun la flava kadro estas reen sur pinto de la stako.
Do kiel vi vidas, ni estas nun detruante la listo de dekstre maldekstren.
>> Kio okazus, se, se ni agis aferoj misfunkcias?
Ĝuste kiel kiam ni provis aldoni elementon.
Se ni paneas la ĉenon, se ni ne konektis la montriloj
en la ĝusta ordo, se ni nur liberigis la unuan elementon,
se ni ĵus liberigis la kapo de la listo, nun ni
neniel povus rilati al la resto de la listo.
Kaj do ni havus orfinoj ĉio,
ni devintus kio estas nomita memoro liko.
Se vi memoras de niaj filmetoj sur dinamika memoro atribuo,
Tio ne estas tre bona afero.
>> Do kiel mi diris, Estas pluraj operacioj
ke ni devas uzi labori kun ligillisto efike.
Kaj vi eble rimarkis mi preterlasis unu, viŝante sola elemento de kunligita
lerta.
La kialo mi faradis estas ĝi estas fakte speco de
malfacila pensi pri kiel forigi sola elemento el unuope
ligillisto.
Ni bezonas por povi salti super ion en la listo, kiun
Do oni akiras al point-- ni volas forviŝi ĉi node--
sed por fari ĝin tiel ni ne perdas ajnan informon,
ni bezonas konekti tiun nodo super tie, ĉi tie.
>> Do mi probable faris ke erara de vida perspektivo.
Do ni estas ĉe la komenco de nia listo, ni antaŭeniru tra,
ni volas forigi ĉi tiun nodon.
Se ni simple forigi ĝin, ni rompis la ĉenon.
Tiu nodo ĝuste ĉi tie rilatas al ĉio alia,
ĝi enhavas la ĉeno de ĉi tie sur eksteren.
>> Do kion ni devas fari reale post ni atingos tiun punkton,
Estas ni bezonos retropaŝi, kaj konekti tiu nodo super al ĉi tiu nodo,
do ni tiam povas forviŝi unu en la mezo.
Sed unuope ligitaj listoj ne havigi al ni kiudirekten iri malantaŭen.
Do ni bezonas ĉu konservi du punteros, kaj movas ilin
speco de off paŝo, unu malantaŭ la aliajn kiel ni iru, aŭ atingi punkton
kaj poste sendi alian montrilon tra.
Kaj kiel vi povas vidi, ĝi povas akiri iom senorda.
Feliĉe, ni havas alia maniero solvi tion,
kiam ni parolas pri duoble ligitaj listoj.
>> Mi Doug Lloyd, tiu estas CS50.