[MIZIK jwe] 

Doug Lloyd: OK, se konsa nan pwen sa a nan kou a, nou te kouvri yon anpil nan Basics yo nan C. Nou konnen anpil bagay sou varyab, ranje, endikasyon, tout sa ki bon bagay. Moun sa yo ki, yo tout sòt de bati nan nan wè kòm fondamantal yo, men nou ka fè plis, dwa? Nou ka konbine bagay sa yo ansanm nan fason ki enteresan. 

Se konsa, kite a fè sa, kite la kòmanse nan branch soti nan sa ki C ba nou, epi yo kòmanse yo kreye done pwòp nou estrikti lè l sèvi avèk sa yo bilding blòk ansanm fè yon bagay reyèlman gen anpil valè, itil. Youn nan fason nou ka fè sa a se pale sou koleksyon. Se konsa, byen lwen tèlman nou te gen yon sèl kalite done estrikti pou reprezante koleksyon a renmen valè, valè menm jan an. Ki ta ka yon etalaj. Nou gen koleksyon nan nonm antye relatif, oswa koleksyon nan karaktè ak sou sa. 

Estrikti yo tou sòt de yon done estrikti pou kolekte enfòmasyon, men li la pa pou kolekte tankou valè. Li anjeneral melanje kalite done diferan ansanm andedan nan yon bwat sèl. Men, li la pa tèt li itilize yo chèn ansanm oswa konekte ansanm menm jan atik, tankou yon etalaj. Ranje yo se gwo pou eleman gade moute, men sonje ke li nan trè difisil insert nan yon etalaj, sof si nou ap mete an fen la anpil nan ki etalaj. 

Ak egzanp ki pi bon mwen gen pou sa a se sòt ensèsyon. Si ou sonje videyo nou an sou sòt ensèsyon, te gen yon anpil nan depans ki enplike nan li te gen ranmase eleman, ak chanjman yo soti nan fason an nan anfòm yon bagay nan mitan an nan etalaj ou yo. Ranje tou soufri soti nan yon lòt pwoblèm, ki se frigidité. Lè nou deklare yon etalaj, nou jwenn yon sèl piki nan li. Nou jwenn yo di, mwen vle sa a eleman anpil. Ta kapab 100, li ta ka gen 1,000, li ta ka gen x kote x se yon nimewo ki itilizatè a te ban nou nan yon èd memwa oswa nan yo lòd, ki liy. 

Men, nou sèlman jwenn yon sèl piki nan li, nou pa jwenn Lè sa a, di oh, aktyèlman mwen bezwen 101, oswa mwen te bezwen x plis 20. Twò ta, nou te deja deklare nan etalaj, epi si nou vle jwenn 101 oswa x plis 20, nou gen deklare yon etalaj totalman diferan, kopi tout eleman ki nan etalaj la sou, ak Lè sa a nou gen ase. Ak sa ki si nou se sa ki mal ankò, ki sa si nou aktyèlman bezwen 102, oswa x plis 40, nou dwe fè sa a ankò. Se konsa, yo ap trè souplesse pou rèsizin done nou an, men si nou konbine ansanm kèk nan Basics yo ke nou te deja te aprann enfòmasyon sou endikasyon yo ak estrikti, an patikilye lè l sèvi avèk dinamik memwa alokasyon ak malok, nou ka mete moso sa yo ansanm yo kreye yon done nouvo structure-- yon separeman lye lis nou ta ka say-- ki pèmèt nou grandi ak retresi yon koleksyon valè epi nou pa pral gen nenpòt espas gaspiye. 

Se konsa, ankò, nou rele ide sa a, nosyon sa a, yon lis lye. An patikilye, nan videyo sa a nou ap ap pale de lis separeman lye, ak Lè sa a yon lòt videyo nou pral pale lis sou doubl lye, ki se jis yon varyasyon sou yon tèm isit la. Men, yon lis separeman lye se konpoze de nœuds, nœuds jis ke yo te yon term-- abstrè li nan jis yon bagay mwen ap rele sa a, se yon kalite estrikti, fondamantalman, mwen se? Jis ale nan rele li yon node-- ak sa a ne te gen de manm yo, oswa de jaden yo. Li te gen done, nòmalman yon nonb antye relatif, yon flote karaktè, oswa te kapab gen kèk lòt kalite done ke ou te defini ak yon def kalite. Apre sa, li gen yon konsèy nan yon lòt ne nan kalite la menm. 

Se konsa, nou gen de bagay sa yo andedan nan ne sa a, done ak yon konsèy nan yon lòt ne. Men, si ou kòmanse visualized sa, ou ka panse osijè de sa tankou yon chèn nan nœuds ki yo ki konekte ansanm. Nou gen ne an premye, li gen done, ak yon konsèy ne, dezyèm lan, ki gen done, ak yon konsèy nan twazyèm ne la. Se konsa, Se poutèt sa nou rele li yon lis lye, yo ap lye ansanm. 

Ki sa sa a espesyal estrikti ne sanble? Oke, si ou sonje soti nan videyo nou an sou defini kalite koutim, ak kalite def, nou ka defini yon structure-- ak tape defini yon estrikti tankou sa a. tyepdef struct sllist, ak Lè sa mwen se lè l sèvi avèk valè a mo isit la abitrèman yo endike nenpòt ki kalite done vrèman. Ou te kapab pase sou yon nonb antye relatif oswa flote, ou te kapab gen tou sa ou vle. Li pa nan restriksyon nan jis nonm antye relatif, oswa yon bagay tankou sa. Se konsa, valè jis yon abitrè done kalite, ak Lè sa a yon konsèy nan yon lòt ne nan kalite la menm. 

Koulye a, gen nan yon ti kras trape isit la ak defini yon estrikti lè li yon estrikti referansyèl pwòp tèt ou. Mwen gen gen yon ti tan non pou estrikti m 'yo. Nan fen jou I klèman vle rele l ' sl ne, sa a, se finalman nouvo nan non yon pati nan definisyon kalite m 'yo, men mwen pa ka sèvi ak sl ne nan mitan an nan sa a. Rezon ki fè ke yo te la, mwen pa gen kreye yon kalite rele sl ne jouk tan mwen frape pwen final sa a isit la. Jiska pwen sa a, mwen gen gen yon lòt fason pou fè referans a sa a ki kalite done. 

Lè sa a se yon pwòp tèt ou referansyèl done kalite. Li; s yon kalite done nan yon estrikti ki gen yon done, ak yon konsèy nan yon lòt estrikti nan kalite la menm. Se konsa, mwen bezwen pou kapab al gade nan sa a ki kalite done omwen pou yon ti tan, se konsa bay li yon ti tan non struct sllist pèmèt m 'Lè sa a, di mwen vle yon konsèy nan yon lòt sllist struct, yon etwal struct sllist, ak Lè sa apre mwen te fini definisyon an, Koulye a, mwen ka rele sa a ki kalite yon ne sl. 

Se konsa, Se poutèt sa ou wè gen nan yon non pou yon ti tan isit la, men yon non pèmanan isit la. Pafwa ou ta ka wè definisyon nan estrikti, pou egzanp, ki pa referansyèl pwòp tèt ou, ki pa gen yon non Dvi isit la. Li ta jis di tipedèf struct, louvri Curly atèl ak Lè sa a defini li. Men, si w ap struct se pwòp tèt ou referansyèl, tankou sa a se yon sèl, ou bezwen presize yon Non kalite tanporè. Men, finalman, kounye a ke nou te fè a, nou ka jis, al gade nan nœuds sa yo, inite sa yo, kòm nœuds sl pou rezon nan rès la nan videyo sa a. 

Tout dwa, se konsa nou konnen ki jan yo kreye yon lis lye ne. Nou konnen ki jan yo defini yon lis lye ne. Koulye a, si nou ap ale nan kòmanse lè l sèvi avèk yo kolekte enfòmasyon, gen nan yon koup la operasyon nou bezwen pou konprann epi pou travay avèk yo. Nou bezwen konnen ki jan yo kreye yon lis lye soti nan lè mens. Si gen nan pa gen lis deja, nou vle kòmanse yon sèl. Se konsa, nou bezwen kapab yo kreye yon lis lye, nou bezwen pwobableman rechèch nan lis la lyen jwenn yon eleman nou ap chèche pou. Nou bezwen pou kapab Insert bagay ki nouvo nan lis la, nou vle lis nou an pou kapab grandi. Apre sa, Menm jan an tou, nou vle kapab yo efase bagay nan lis nou an, nou vle lis nou an pou kapab retresi. Ak nan fen a nan nou an pwogram, espesyalman si ou sonje ke nou ap dynamique allocation memwa yo bati sa yo bay lis tipikman, nou vle libere tout nan ke memwa lè nou ap fè travay ak li. Se konsa, nou bezwen pou kapab efase yon tout lis lye nan yon sèl ne plongée. Se konsa nou ale nan kèk nan operasyon sa yo ak ki jan nou ta ka visualized yo, pale nan kòd pseudocode espesyalman. Se konsa, nou vle kreye yon lye lis, se konsa petèt nou vle defini yon fonksyon ak pwototip sa a. sl zetwal ne, kreye, ak mwen pase nan yon sèl agiman, kèk done abitrè tape ankò, nan kèk kalite done abitrè. Men, mwen returning-- fonksyon sa a ta dwe tounen vin jwenn mwen yon konsèy, nan yon separeman lye lis ne. Yon fwa ankò, nou ap eseye yo kreye yon lis lye soti nan lè mens, Se konsa, mwen bezwen yon konsèy nan ke lis lè m ap fè. 

Se konsa, sa yo se etap ki konsène isit la? Oke, premye bagay mwen se pral fè se dynamique asiyen espas pou yon nouvo ne. Yon fwa ankò, nou ap kreye l 'soti nan mens lè, se konsa nou bezwen espas malok pou li. Ak nan kou, imedyatman apre nou malok, nou toujou tcheke a asire w ke nou an pointer-- nou pa t 'jwenn tounen nil. Paske si nou eseye ak deferans yon konsèy nil, nou ap ale nan soufri yon segfault epi nou pa vle sa. 

Lè sa a, nou vle ranpli nan jaden an, nou vle inisyalize jaden an valè ak inisyalize jaden an kap vini an. Lè sa a, nou vle to-- a evantyèlman kòm pwototip fonksyon indicates-- nou vle retounen yon konsèy nan yon ne sl. Se konsa, sa fè sa-a gade tankou vizyèlman? Oke, premye nou ap ale nan dynamique asiyen espas pou yon nouvo ne sl, se konsa nou malloc-- sa a, se yon reprezantasyon vizyèl a ne la nou jis kreye. Apre sa, nou tcheke a asire w li pa nan null-- nan ka sa a, foto a pa ta gen montre moute si li te nil, nou ta gen kouri soti nan memwa, se konsa nou ap bon yo ale la. Se konsa, kounye a nou ap sou nan etap C, inisyalize jaden an nœuds valè. Oke, ki baze sou sa a fonksyon rele mwen lè l sèvi avèk isit la, sanble mwen vle pase nan 6, se konsa mwen pral 6 nan jaden an valè. Koulye a, inisyalize jaden an kap vini an. Oke, sa mwen pral fè a, pa gen anyen kap vini an, dwa, sa a se bagay la sèlman nan lis la. Se konsa, sa ki nan bagay la pwochen nan lis la? 

Li pa ta dwe lonje dwèt sou yon bagay, dwa. Pa gen anyen lòt bagay la, se konsa ki sa ki konsèp la nou konnen nan sa a, se nothing-- endikasyon pa gen anyen? Li ta dwe petèt nou vle yo mete yon konsèy nil a, epi mwen pral reprezante nil nan konsèy kòm jis yon bwat wouj, nou pa ka ale nenpòt ki pi lwen. Kòm nou pral wè yon ti kras pita sou li a, nou pral gen evantyèlman chenn pou flèch konekte sa yo nœuds ansanm, Men, lè ou frape nan bwat wouj, sa a, se nil, nou pa ka ale nenpòt ki pi lwen, sa a, se nan fen lis la. 

Epi anfen, nou jis vle retounen yon konsèy nan ne sa a. Se konsa, nou pral rele li nouvo, epi yo pral retounen nouvo se konsa li kapab itilize nan tou sa fonksyon kreye li. Se konsa, gen nou ale, Nou te kreye yon separeman lye lis ne soti nan lè mens, epi kounye a nou gen yon lis nou ka travay avèk yo. 

Koulye a, kite a di nou deja gen yon gwo chèn, e nou vle jwenn yon bagay nan li. Epi nou vle yon fonksyon ki k ap pase retounen vre oubyen fo, tou depann sou si se yon valè egziste nan ke lis. Yon pwototip fonksyon, oswa deklarasyon pou sa fonksyon, ta ka sanble sa a men bouleen jwenn, ak lè sa a nou vle pase nan de agiman. 

Premye a, se yon konsèy nan la premye eleman nan lis la lye. Sa a se aktyèlman yon bagay ou pral toujou vle kenbe tras nan, ak aktyèlman ta ka yon bagay ki ou menm mete nan yon varyab mondyal la. Yon fwa ou kreye yon lis, ou toujou, toujou vle kenbe tras nan trè an premye eleman nan lis la. Nan fason sa a ou ka al gade nan lòt nan tout eleman pa jis sa yo chèn lan, san yo pa gen kenbe endikasyon entak nan chak eleman sèl. Ou sèlman bezwen kenbe tras nan premye nan yon sèl si yo ap tout nan chenn ansanm. 

Lè sa a, bagay la dezyèm nou ap pase nan ankò se abitrèman some-- tou sa done kalite nou ap kap chèche gen andedan nan èspere ke youn nan nœuds yo nan lis la. Se konsa, sa yo se etap yo? Oke, premye bagay la nou fè se nou kreye yon konsèy dwat sekant montre nan tèt la lis. Oke, poukisa nou fè sa, nou deja gen yon konsèy nan plas tèt la lis, poukisa pa nou jis deplase ke youn nan jiwon l? Oke, tankou mwen jis te di, li vrèman enpòtan pou nou toujou kenbe tras nan la trè premye eleman nan lis la. Se konsa, li la aktyèlman pi bon yo kreye yon kopi de sa, epi sèvi ak ki fè mouvman pou nou pa janm aksidantèlman avanse pou pi lwen, oswa nou toujou gen yon konsèy nan kèk pwen ki se dwa sou eleman nan premye nan lis la. Se konsa, li pi bon yo kreye yon dezyèm yon sèl ke nou itilize pou avanse pou pi. 

Lè sa a, nou jis konpare si wi ou non jaden an valè nan ki ne se sa nou ap chèche pou, epi si li nan pa, nou jis deplase li nan yon ne kap vini an. E nou kontinye ap fè ki sou, ak sou, yo ak sou, jiskaske nou swa jwenn eleman a, oswa nou frape null-- nou te rive jwenn fen an nan lis la epi li se pa la. Sa a ta dwe èspere ke sonnen yon klòch bay ou kòm jis rechèch lineyè, nou ap jis repwodui l 'nan yon lis separeman lye estrikti olye pou yo lè l sèvi avèk yon etalaj fè li. 

Se konsa, isit la nan yon egzanp sou yon lis separeman lye. Yon sèl sa a konsiste de senk nœuds, e nou gen yon konsèy nan tèt la nan la lis, ki te rele lis. Premye bagay nou vle fè se ankò, kreye ki konsèy parcourt. Se konsa, nou gen kounye a de endikasyon pwen sa a menm bagay la. 

Koulye a, remake isit la tou, mwen pa t ' gen malok nenpòt espas pou Trav. Mwen pa t 'di Trav egal malok yon bagay, ki ne deja egziste, espas sa nan memwa deja egziste. Se konsa, tout mwen aktyèlman fè se kreye yon lòt konsèy nan li. Mwen pa mallocing yon lòt espas, jis gen kounye a de endikasyon montre nan menm bagay la. 

Se konsa, se 2 sa m ap chèche pou? Oke, pa gen okenn, se konsa olye pou mwen se ale pou avanse pou pi nan yon sèl kap vini an. Se konsa, fondamantalman mwen ta ka di, Trav egal Trav kap vini an. Se 3 sa m ap chèche pou yo, pa gen okenn. Se konsa, mwen kontinye ale a, jouk evantyèlman li ale nan 6 ki se sa ki M 'ap chache pou ki baze sou apèl la fonksyon Mwen gen nan tèt la la, ak se konsa mwen fè. 

Koulye a, sa ki si eleman nan mwen se kap chèche se pa nan lis la, se li toujou ale nan travay? Oke, remake ke lis la isit la se subtile diferan, ak sa a se yon lòt bagay sa a, se enpòtan ak lis lye, ou pa bezwen prezève yo nan nenpòt lòd patikilye. Ou kapab si ou vle, men ou ka te deja remake ke nou pa ap kenbe tras nan ki nimewo eleman nou yo nan. 

Epi sa a, sòt de yon sèl komès ke nou genyen ak lis lye vèsè ranje, se li nou pa gen aksè o aza ankò. Nou pa ka jis di, mwen vle pou yo ale nan eleman nan 0th, oswa eleman nan 6th nan etalaj mwen, ki mwen ka fè nan yon etalaj. Mwen pa ka di mwen vle pou yo ale nan nan 0th eleman, oswa eleman nan 6th, oswa eleman nan 25th nan lis lye m 'yo, gen nan pa gen endèks ki asosye ak yo. Se konsa, li pa reyèlman gen pwoblèm si nou prezève lis nou an nan lòd. Si ou vle ou sètènman kapab, men gen nan pa gen okenn rezon ki fè yo bezwen dwe konsève nan nenpòt lòd. Se konsa, ankò, se pou yo eseye ak jwenn 6 nan lis sa a. Oke, nou kòmanse nan la kòmansman, nou pa jwenn 6, ak Lè sa a nou pa kontinye jwenn 6, jiskaske nou evantyèlman ale nan isit la. Se konsa, dwa pwen kounye a Trav ne la ki gen 8, ak sis se pa nan la. 

Se konsa, pwochen etap la ta dwe pou yo ale nan konsèy kap vini an, se konsa di Trav egal Trav kap vini an. Oke, Trav kap vini an, sa endike nan ti bwat la wouj la, se nil. Se konsa, gen nan okenn kote lòt bagay yo ale, e konsa nan pwen sa a nou ka konkli ke nou te rive jwenn nan fen lis la lye, ak 6 se pa nan la. Epi li ta dwe retounen fo nan ka sa a. 

OK, ki jan nou insert yon nouvo ne nan lis la lye? Se konsa, nou ve yo te kapab kreye yon lis lye soti nan okenn kote, men nou pwobableman vle bati yon chèn epi yo pa kreye yon pakèt moun sou lis diferan. Nou vle gen yon sèl lis ki gen yon pakèt moun sou nœuds nan li, pa yon pakèt moun sou lis ak yon ne sèl. Se konsa, nou pa ka jis kenbe lè l sèvi avèk Kreye nan fonksyon nou defini pi bonè, kounye a nou vle insert nan yon lis ki deja egziste. 

Se konsa, sa a, nou ap ale yo pase nan de agiman, konsèy la nan tèt la nan ki lye lis ke nou vle pou ajoute pou. Yon fwa ankò, sa a, se poutèt sa li a tèlman enpòtan pou nou toujou kenbe tras nan li, paske li nan wout la sèlman nou reyèlman gen, al gade nan lis la antye se jis pa yon konsèy nan eleman a an premye. Se konsa, nou vle pase nan yon konsèy ak sa yo ki eleman an premye, ak tou sa nou valè vle ajoute nan lis la. Ak evantyèlman sa a fonksyon ki pral retounen yon konsèy nan tèt nan nouvo nan yon lis lye. 

Ki sa ki etap sa yo ki enplike isit la? Oke, jis tankou ak kreye, nou bezwen dynamique asiyen espas pou yon nouvo ne, epi tcheke fè ke nou pa kouri soti nan memwa, ankò, paske nou ap sèvi ak malok. Lè sa a, nou vle peple ak insert ne la, se konsa mete nimewo a, tou sa Val se, an ne la. Nou vle insert ne la nan nan konmansman an nan lis la lye. 

Genyen yon rezon ki fè ke mwen vle fè sa, epi li ta ka vo pran yon dezyèm pran yon poz videyo a isit la, epi reflechi sou poukisa mwen ta vle Insert nan kòmansman an nan yon lye lis. Yon fwa ankò, mwen mansyone pi bonè ki li fè sa pa reyèlman gen pwoblèm si nou konsève li nan nenpòt lòd, se konsa petèt sa a, se yon siy. Apre sa, ou te wè sa ki ta rive si nou te vle to-- oswa ki soti nan jis yon dezyèm de sa lè nou te ale a rechèch ou te kapab wè sa ki ka rive si nou t ap insert nan fen lis la. Paske nou pa gen yon konsèy nan fen a nan lis la. 

Se konsa, rezon ki fè yo ke mwen ta vle insert nan kòmansman an, se paske mwen kapab fè li imedyatman. Mwen gen yon konsèy nan kòmansman an, ak nou pral wè sa a nan yon vizyèl nan yon dezyèm fwa. Men, si mwen vle insert nan fen a, Mwen gen yo kòmanse nan kòmansman an, Traverse tout wout la nan la ka fèt, ak Lè sa a fofile l 'sou. Se konsa, ki ta vle di ke mete nan fen lis la ta vin yon O nan n operasyon an, pral tounen nan diskisyon nou an nan enfòmatik konpleksite. Li ta vin yon o nan n operasyon, kote kòm lis la te resevwa pi gwo, ak pi gwo, ak pi gwo, li pral vin pi plis ak pi difisil yo fofile yon bagay sou nan fen an. Men, li la toujou reyèlman fasil yo fofile yon bagay sou nan kòmansman an, w ap toujou nan konmansman an. 

Epitou, n ap wè yon vizyèl nan sa a ankò. Lè sa a, yon fwa nou ap fè, yon fwa nou te mete ne nan nouvo, nou vle retounen konsèy nou yo tèt nan nouvo nan yon lis lye, ki depi nou ap mete nan la kòmanse, yo pral aktyèlman ap yon konsèy nan ne la nou jis kreye. Se pou nou visualized sa a, paske mwen panse ke li pral ede. 

Se konsa, isit la nan lis nou an, li gen ladann nan kat eleman, yon ne ki gen 15, ki lonje dwèt nan yon ne ki gen 9, ki lonje dwèt nan yon ne ki gen 13, ki lonje dwèt nan yon ne ki gen 10, ki te gen nil nan konsèy kòm konsèy pwochen li yo se konsa sa a, se nan fen lis la. Se konsa, nou vle insert yon nouvo ne ak valè a 12 nan kòmansman an nan sa a lis, ki sa nou fè? Oke, premye nou malok espas pou la ne, ak Lè sa nou mete 12 nan la. 

Se konsa, kounye nou te rive jwenn yon pwen desizyon, dwa? Nou gen yon koup la endikasyon ki nou te kapab avanse pou pi, ki youn ta dwe nou deplase premye? Eske nou ta dwe fè 12 pwen A ak tèt nan nouvo nan list-- nan oswa eskize mwen, yo ta dwe nou fè 12 lonje dwèt sou tèt la fin vye granmoun nan lis la? Osinon èske nou dwe di ke nan lis kounye a kòmanse nan 12. Genyen yon diferans a, epi n ap gade nan sa ki k ap pase ak tou de nan yon dezyèm fwa. 

Men, sa a mennen nan yon gwo sijè pou ankadre, ki se ke youn nan la trickiest bagay sa yo ak lis lye se pou fè aranjman pou pwent yo yo nan lòd ki kòrèk la. Si w demenaje bagay sa yo soti nan lòd, ou ka fini aksidantèlman orphaning rès la nan lis la. Ak isit la nan yon egzanp sou sa. Se konsa an n ale ak lide la de- byen, nou te jis te kreye 12. Nou konnen 12 a pwal tèt nan nouvo nan lis la, ak konsa poukisa pa nou jis deplase lis konsèy la nan pwen a. 

OK, se konsa sa a, se bon. Se konsa, kounye kote fè 12 pwen apre a? Mwen vle di, nou ka wè vizyèlman ke li pral lonje dwèt sou 15, kòm moun li vrèman evidan yo ban nou. Ki jan òdinatè a konnen? Nou pa gen anyen montre a 15 ankò, dwa? 

Nou te pèdi nenpòt kapasite, al gade nan 15. Nou pa ka di nouvo flèch egal pwochen yon bagay, pa gen anyen la. An reyalite, nou te òfelen rès la nan lis la pa fè sa, nou te aksidantèlman kase chèn lan. E nou sètènman pa vle fè sa. 

Se konsa, kite yo ale retounen lakay yo epi eseye sa a ankò. Petèt bagay ki dwat yo fè se yo mete 12 nan pwochen konsèy nan tèt la fin vye granmoun nan lis nan premye, lè sa a nou kapab deplase lis la sou. Lè an reyalite, se sa ki nan lòd kòrèk ke nou bezwen swiv lè nou ap travay ak lis separeman lye. Nou toujou vle konekte nan nouvo eleman nan lis la, anvan nou pran ki kalite etap enpòtan nan chanje kote tèt la nan lis la lye se. Yon fwa ankò, sa a, se tankou yon bagay fondamantal, nou pa vle pèdi tras nan li. 

Se konsa, nou vle asire w ke tout bagay se nan chenn ansanm, anvan nou deplase ki konsèy. Se konsa, sa a ta ka lòd ki kòrèk la, ki se yo konekte 12 a lis la, Lè sa a, di ke lis la kòmanse yon 12. Si nou di lis la kòmanse nan 12 ak Lè sa a, te eseye konekte 12 a lis la, nou te deja wè sa ki rive. Nou pèdi lis la pa erè. 

OK, se konsa yon sèl bagay plis yo pale sou. E si nou vle debarase m de yon tout lye lis nan yon fwa? Yon fwa ankò, nou ap mallocing tout espas sa a, epi pou nou bezwen libere li lè nou ap fè. Se konsa, kounye a nou vle efase tout lis la lye. Oke, sa nou vle fè? 

Si nou te rive nan konsèy la nil, nou vle sispann, otreman, jis efase rès la nan lis la ak Lè sa a libere m '. Debarase m de rès la nan lis la, ak Lè sa a gratis ne aktyèl la. Ki sa ki son tankou, sa teknik gen nou te pale sou deja fè sa son tankou? Debarase m de tout lòt moun, lè sa a tounen ak efase m '. 

Sa a rkursyon, nou te fè a pwoblèm yon ti kras pi piti, nou ap di tout moun efase lòt moun, lè sa a ou ka efase m '. Ak plis desann wout la, ki ne pral di, efase tout lòt moun. Men evantyèlman nou pral ale nan nan pwen kote lis la se nil, e ke sa a ka baz nou an. 

Se konsa, kite a pran yon gade nan sa a, ak ki jan sa a ta ka travay. Se konsa, isit la nan lis nou an, li nan menm bagay la tou lis nou te jis ap pale de, ak gen nan etap sa yo. Genyen yon anpil nan tèks isit la, men èspere ke vizyalizasyon a ap ede. 

Se konsa, nou en-epi tou mwen te rale moute nou an ilistrasyon ankadreman chemine soti nan videyo nou an sou apèl pil, ak èspere ke tout bagay sa yo ansanm pral montre w sa k ap pase sou. Se konsa, isit la nan Kòd pseudocode nou an. Si nou rive nan yon nil konsèy, sispann, otreman, efase rès la nan lis la, Lè sa a, libere ne aktyèl la. Se konsa, kounye a, list-- konsèy la ke nou ap pase nan detwi pwen yo 12. 12 se pa yon konsèy nil, se konsa nou ap ale nan efase rès la nan lis la. 

Ki sa ki efase nan rès nan nou patisipe? Oke, sa vle di fè yon rele detwi, li di ki 15 se nan konmansman an nan nan rès nan lis la nou vle detwi. Se konsa, rele nan detwi 12 se kalite sou kenbe. Li nan frizè a, ap tann pou nan rele detwi 15, a fini travay li yo. 

Oke, 15 se pa yon konsèy nil, ak se konsa li k ap pase yo di, tout dwa, byen, efase rès la nan lis la. Rès la nan lis la kòmanse nan 9, e konsa nou pral jis rete tann jiskaske ou efase tout sa ki bagay, Lè sa a, tounen vin ak efase m '. Oke 9 k ap pase yo di, byen, Mwen pa yon konsèy nil, se konsa efase rès la lis la soti isit la. Se konsa, eseye epi detwi 13. 13 di, mwen pa nil konsèy, menm bagay, li pase Buck la. 10 se pa nil konsèy, 10 gen yon konsèy nil, men 10 se pa tèt li yon nil konsèy kounye a, ak pou li pase Buck a tou. 

Epi, koulye a lis pwen la, li reyèlman ta lonje dwèt sou some-- si mwen te gen plis espas nan imaj la, li ta lonje dwèt sou kèk espas o aza ke nou pa konnen sa li ye. Li nan konsèy la nil menm si, lis la se literalman kounye a mete li nan valè null. Li nan lonje dwèt dwat andedan ki bwat wouj. Nou te rive nan yon konsèy nil, se konsa nou ka sispann, epi nou ap fè. 

Se konsa, ki ankadreman koulè wouj violèt se now-- nan la tèt stack-- sa a, se ankadreman an aktif, men li la fè. Si nou te rive nan yon konsèy nil, sispann. Nou pa fè anyen, nou pa ka libere yon konsèy nil, nou pa t 'nenpòt ki malok espas, ak se konsa nou ap fè. Se konsa, ki ankadreman fonksyon la ap fini, epi nou resume-- nou ranmase kote nou te kite koupe ak pwochen pi wo youn nan, ki se sa a ankadreman ble fonse isit la. Se konsa, nou ranmase dwa ki kote nou te kite la. Nou efase rès la nan la lis deja, se konsa kounye a nou ap ale nan libere nœuds yo kounye a. Se konsa, kounye a nou ka libere ne sa a, e kounye a, nou te rive jwenn nan fen fonksyon an. Se konsa, se ke ankadreman fonksyon detwi, epi nou ranmase nan yon sèl nan limyè ble. 

Se konsa, li says-- Mwen te deja done-- efase rès la nan lis la, se konsa libere ne aktyèl la. Epi, koulye a ankadreman an jòn se tounen sou tèt pil la. Se konsa, ke ou wè, nou ap kounye a detwi lis la de dwat a gòch. 

Ki sa ki ta te rive, menm si, si nou te fè bagay sa yo wout la mal? Jis tankou lè nou te eseye ajoute yon eleman. Si nou messed moute chèn lan, si nou pa t 'konekte pwent yo nan lòd ki kòrèk, si nou jis libere eleman nan premye, si nou jis libere nan ki an tèt lis la, kounye a nou pa gen okenn fason pou fè referans a rès la nan lis la. Se konsa, nou ta gen òfelen tout bagay, nou ta ka gen sa ki nan rele yon fwit memwa. Si ou sonje soti nan videyo nou an sou alokasyon memwa dinamik, sa a, se pa trè bon bagay. 

Se konsa, jan mwen te di, gen plizyè operasyon ke nou bezwen yo sèvi ak nan travay ak lye lis efektivman. Epi ou ka remake gen mwen omisyon yon sèl, efase yon eleman sèl ki sòti nan yon lye lis. Rezon ki fè la mwen te fè ki se li la aktyèlman kalite difisil yo reflechi sou ki jan yo efase yon eleman sèl ki sòti nan yon separeman lye lis. Nou bezwen pou kapab sote sou yon bagay nan lis la, ki vle di nou jwenn nan yon nou point-- vle efase sa a node-- men yo nan lòd yo fè l 'pou nou pa pèdi nenpòt enfòmasyon, nou bezwen konekte sa a ne sou isit la, isit la. 

Se konsa, mwen te fè sa ki mal pwobableman sòti nan yon pèspektiv vizyèl. Se konsa, nou ap nan konmansman an nan nou an lis, nou ap pwosedi a, nou vle efase ne sa a. Si nou jis efase li, nou te kase chèn lan. Ne sa a dwa isit la refere a tout lòt bagay, li gen chèn lan soti nan isit la sou deyò. 

Se konsa, sa nou bezwen fè aktyèlman apre nou ale nan pwen sa a, se nou bezwen etap tounen yon sèl, ak konekte ne sa a nan men ne sa a, pou nou ka Lè sa a, efase yon sèl la nan mitan yo. Men, lis separeman lye pa fè sa bay nou yon fason yo ale bak. Se konsa, nou bezwen swa kenbe de endikasyon, epi li deplase yo sòt de koupe etap, youn dèyè a lòt jan nou ale, oswa pou w jwenn nan yon pwen ak Lè sa a voye yon lòt konsèy nan. Ak jan ou ka wè, li ka jwenn yon ti kras sal. Erezman, nou gen yon lòt fason yo rezoud sa, lè nou pale sou lis doubl lye. 

Mwen se Doug Lloyd, sa a se CS50.