[Powered by Google Translate] [It-Taqsima 7: Aktar komda]
[Rob Bowden] [Università ta 'Harvard]
[Dan huwa CS50] [CS50.TV]
Kull dritt. Allura bħal I said fil-email tiegħi,
dan se tkun sezzjoni binarja-siġra intensiv.
Iżda ma jkunx hemm li ħafna mistoqsijiet.
Allura aħna qed tmur biex jippruvaw u tfassal l kull mistoqsija
u jidħlu fid-dettal uġigħ ta 'l-aħjar modi ta' nagħmlu l-affarijiet.
Allura dritt fil-bidu, aħna jgħaddu tpinġijiet kampjun ta 'siġar binarju u l-għalf.
Allura hawnhekk, "Ftakar li siġra binarju għandha lymph simili għal dawk ta 'lista marbuta,
ħlief minflok waħda pointer hemm żewġ: waħda għal "tfal" ix-xellug
u wieħed għad-dritt "tfal". "
Allura siġra binarju huwa bħad lista marbuta,
ħlief il-Struct se jkollha żewġ pointers.
Hemm siġar trinary, li huma se jkollhom tliet pointers,
hemm N-ARY siġar, li biss għandhom pointer ġeneriku
li inti mbagħad ikollhom malloc li jkun kbir biżżejjed biex ikollhom
pointers biżżejjed għall-tfal kollha possibbli.
Allura siġra binarju jiġri biss li jkollhom numru kostanti ta 'tnejn.
Jekk trid, tista 'tagħti lista marbut kif siġra unary,
imma ma naħsibx xi ħadd jitlob dan li.
"Pinġi dijagramma kaxxi-u-vleġeġ ta 'nodu siġra binarju
li jkun fih in-numru favoriti Nate s, 7, fejn kull pointer wild huwa null. "
Allura iPad modalità.
>> Huwa ser ikun pjuttost sempliċi.
Aħna biss se jkollhom node, jien ser tiġbed bħala kwadru.
U jien ser tiġbed l-valuri fil hawn.
Allura l-valur se jmorru fil hawn,
u mbagħad stabbiliti hawn aħna ser ikollhom l-pointer xellug fuq ix-xellug u l-pointer dritt fuq il-lemin.
U huwa ferm hekk konvenzjoni li hija sejħa xellug u dritt, l-ismijiet pointer.
Kemm minn dawn ser ikunu nulli.
Li se biss tkun nulla, u li se jkun biss null.
Okay. Allura lura hawn.
"Ma 'lista marbuta, aħna biss kellhom biex jaħżnu pointer
l-node ewwel fil-lista sabiex tiftakar il-lista kollha marbutin, jew il-lista sħiħa.
Bl-istess mod, bis-siġar, aħna biss biex jaħżnu pointer
għal node wieħed sabiex tiftakar il-siġra kollha.
Dan node huwa Calle l-"għerq" tas-siġra.
Jibnu fuq dijagramma tiegħek minn qabel jew jiġbed waħda ġdida
b'tali mod li inti għandek rappreżentazzjoni kaxxi-u-vleġeġ ta 'siġra binarju
ma 'l-il-valur 7, imbagħad 3 fil-linja xellugija,
imbagħad 9 fuq il-lemin, u mbagħad 6 dwar id-dritt tal-magna 3. "
Ejja naraw jekk I jistgħu jiftakru kollha ta 'dak in my head.
Allura dan se jkun għeruq tagħna up here.
Aħna ser ikollhom xi pointer x'imkien, xi ħaġa li aħna ser sejħa għeruq,
u huwa tipponta lejn dan Guy.
Issa biex tagħmel node ġdid,
dak li għandna, 3 fuq ix-xellug?
Allura node ġdid bi 3, u huwa inizjalment punti null.
I ser biss jitqiegħed N.
Issa aħna tixtieq li tagħmel dan jmorru lejn ix-xellug ta '7.
Allura aħna bidla dan il-werrej li issa jindikaw dan Guy.
U aħna jagħmlu l-istess. Irridu a 9 minn hawn
li inizjalment biss jgħid null.
Aħna ser jibdlu dan il-werrej, punt sa 9,
u issa rridu li tqiegħed 6 lejn il-lemin ta '3.
Allura li għaddej biex - jagħmlu 6.
U li Guy se punt hemmhekk.
Okay. Allura dak kollu li jitlob minna li tagħmel.
>> Issa ejja jmorru fuq xi terminoloġija.
Aħna diġà tkellem dwar kif l-għerq tal-siġra huwa l-node top-aktar fil-siġra.
Il-wieħed li jkun fih 7. Il-lymph fil-qiegħ tas-siġra huma msejħa l-weraq.
Kull node li biss għandu null bħala tfal tagħha hija weraq.
Għalhekk huwa possibbli, jekk siġra binarju tagħna huwa biss node wieħed,
li siġra hija weraq, u li hu.
"Il-" għoli "tas-siġra huwa n-numru ta 'hops għandek tagħmel
biex tikseb mill-quċċata li werqa. "
Aħna ser jsibu rwieħhom, fit-tieni, id-differenza
bejn is-siġar binarju bilanċjat u żbilanċjata,
iżda għal issa, l-għoli ġenerali ta 'din is-siġra
Jien ngħid huwa 3, għalkemm jekk inti jgħoddu l-għadd tal-ħops
inti għandek tagħmel sabiex tikseb sa 9, allura huwa verament biss f'għoli ta '2.
Dritt issa dan huwa siġra binarju żbilanċjat,
iżda aħna ser tkellimna dwar bilanċjat meta jiġrilha li tkun rilevanti.
Allura issa nistgħu nitkellmu dwar nodes fi siġra f'termini
relattiv għall-lymph oħra fil-siġra.
Allura issa għandna ġenituri, tfal, aħwa, antenati, u dixxendenti.
Huma sens pjuttost komuni, dak li jfisser.
Jekk aħna nistaqsu - ġenituri huwa.
Allura x'inhi l-ġenitur tat-3 ta?
[Studenti] 7. >> Yeah. Il-ġenitur huwa biss se tkun liema punti lilek.
Imbagħad liema huma t-tfal ta 7?
[Studenti] 3 u 9. >> Yeah.
Avviż li "tfal" letteralment tfisser tfal,
hekk 6 ma tapplikax, għaliex dan huwa simili neputi.
Imma mbagħad jekk immorru dixxendenti, iva, liema huma l-dixxendenti ta '7?
[Studenti] 3, 6 u 9. >> Yeah.
Il-dixxendenti ta 'l-node għerq se tkun kollox fil-siġra,
ħlief forsi l-node għerq innifsu, jekk inti ma tridx li jikkunsidraw li dixxendent.
U fl-aħħarnett, antenati, dan huwa l-direzzjoni opposta.
Allura x'inhuma l-antenati ta '6?
[Studenti] 3 u 7. >> Yeah. 9 mhix inkluża.
Huwa biss id-dahar nisel dirett għall-għerq
se tkun antenati tiegħek.
>> "Aħna ngħidu li siġra binarju huwa" ordnat "jekk għal kull node fil-siġra,
kollha tal-dixxendenti tiegħu fuq ix-xellug għandhom valuri inqas
u kollha ta 'dawk fuq il-lemin għandhom valuri akbar.
Per eżempju, is-siġra ta 'hawn fuq huwa ordnat iżda mhux l-arranġament possibbli biss ordnat. "
Qabel nikbru għal dan,
siġra binarju ordnat hija magħrufa wkoll bħala siġra tfittxija binarja.
Hawnhekk aħna jiġri li jkun ssejjaħ dan siġra binarju ordnat,
imma jien qatt ma semgħu dan jissejjaħ siġra binarju ordnati qabel,
u fuq kwizz aħna huma ħafna aktar probabbli li jitqiegħdu siġra tfittxija binarja.
Huma qed l-istess,
u huwa importanti li inti jirrikonoxxu d-distinzjoni bejn siġra binarju u siġar tfittxija binarja.
A siġra binarju huwa biss siġra li l-punti għal żewġ affarijiet.
Kull node punti għal żewġ affarijiet.
M'hemm l-ebda motivazzjoni dwar il-valuri li jipponta lejn.
Allura bħal hawn fuq, peress li huwa siġra tfittxija binarju,
nafu li jekk immorru xellug ta '7,
allura kollha tal-valuri li nistgħu possibilment jilħaq
billi tmur xellug ta '7 għandhom ikunu anqas minn 7.
Avviż li l-valuri ta 'inqas minn 7 huma 3 u 6.
Dawk huma kollha fuq ix-xellug ta '7.
Jekk immorru lejn il-lemin tas-7, kollox għandu jkun ikbar minn 7,
hekk 9 huwa għad-dritt tas-7, hekk aħna qed tajba.
Dan mhuwiex il-każ għal siġra binarju,
għal siġra binarju regolari nistgħu biss għandhom 3 fil-quċċata, 7 għall-xellug,
9 ix-xellug ta '7; hemm l-ebda ordni ta' valuri tkun xi tkun.
Issa, aħna mhux se fil-fatt jagħmlu dan għaliex dan huwa tedious u bla bżonn,
imma "jippruvaw jiġbdu siġar kif ħafna ordnat kif inti tista 'taħseb
jużaw in-numri 7, 3, 9, u 6.
Kemm arranġamenti distinti hemm? X'inhu l-għoli ta 'kull waħda? "
>> Aħna ser tagħmel koppja, imma l-idea prinċipali hija,
dan huwa bl-ebda mod ta 'rappreżentazzjoni unika ta' siġra binarju jkun fih dawn il-valuri.
Kollha għandna bżonn huwa xi siġra binarju li fiha 7, 3, 6, u 9.
Ieħor validu possibbli tista 'tkun l-għerq huwa 3,
mur lejn ix-xellug u huwa 6, mur lejn ix-xellug u huwa 7,
mur lejn ix-xellug u huwa 9.
Din hija perfettament valida siġra tfittxija binarja.
Mhuwiex utli ħafna, għaliex dan huwa biss bħal lista marbuta
u kollha ta 'dawn pointers huma biss null.
Iżda huwa siġra valida. Yeah?
[Student] M'għandekx il-valuri għandhom ikunu akbar fuq il-lemin?
Jew hija din -? >> Dawn I fisser li jmorru l-mod ieħor.
Hemm ukoll - yeah, ejja jaqilbu li.
9, 7, 6, 3. Tajba qabda.
Hija xorta għandha li jobdu dak tfittxija siġra binarju suppost tagħmel.
Allura kollox lejn ix-xellug għandha tkun inqas minn kull node partikolari.
Nistgħu biss jiċċaqalqu, jgħidu, dan 6 u poġġih hawn.
Le, ma nistgħux. Għaliex għandi iżommu tagħmel dan?
Ejja nagħmlu - hawnhekk huwa 6, hawnhekk huwa 7, 6 punti sa 3.
Dan għadu siġra valida tfittxija binarja.
Dak li hu ħażin jekk I - ejja ara jekk nista 'toħroġ bi arranġament.
Yeah, okay. Allura dak li hu ħażin ma 'din is-siġra?
I raden stajt diġà tak ħjiel li hemm xi ħaġa ħażina magħha.
Għaliex għandi iżommu tagħmel dan?
Okay. Dan jidher raġonevoli.
Jekk inħarsu lejn kull node, bħal 7, allura ix-xellug ta '7 huwa 3.
Allura aħna għandna 3, il-ħaġa li d-dritt tat-3 huwa 6.
U jekk inti tħares lejn 6, il-ħaġa li d-dritt tas-6 hija 9.
Allura għaliex huwa dan mhuwiex siġra validu tfittxija binarju?
[Studenti] 9 għadu fuq ix-xellug ta '7. >> Yeah.
Għandu jkun veru li l-valuri kollha inti tista 'possibilment tilħaq billi tmur fuq ix-xellug ta' 7 huma inqas minn 7.
Jekk immorru xellug ta '7, we sa 3 u aħna xorta jistgħu jiksbu sa 6,
aħna xorta jistgħu jiksbu sa 9, iżda minn wara marret inqas minn 7,
aħna ma għandhom ikunu jistgħu jiksbu numru li l-ikbar minn 7.
Allura dan mhux siġra valida tfittxija binarja.
>> My brother attwalment kellu mistoqsija intervista
li kienet bażikament dan, biss il-kodiċi up xi ħaġa li jivvalida
jekk siġra hija siġra tfittxija binarju,
u għalhekk l-ewwel ħaġa huwa ma kien biss tikkontrolla biex tara
jekk ix-xellug u tal-lemin huma korretti, u mbagħad jtenni stabbiliti hemmhekk.
Imma int ma tista 'biss tagħmel dan, inti għandek biex iżommu kont
tal-fatt li issa li stajt marret xellug ta '7,
kollox f'dan subtree għandu jkun inqas minn 7.
L-algoritmu korretta jeħtieġ li jżommu rekord
tal-limiti li l-valuri jistgħu possibbilment jaqgħu pulzieri
Aħna mhux se jmorru permezz ta 'kull wieħed minnhom.
Teżisti relazzjoni rikorrenza sbieħ,
għalkemm aħna ma gotten għal dawk, jew aħna mhux se tikseb għal dawk,
jiddefinixxi kemm hemm fil-fatt huma.
Allura hemm 14 minnhom.
L-idea ta 'kif inti se tagħmel dan matematikament huwa simili,
inti tista 'pick xi wieħed li jkun l-node għerq,
u mbagħad jekk I pick 7 li tkun l-node għerq,
allura hemm, jiġifieri, xi numri li jistgħu imorru jkun node xellug tiegħi,
u hemm xi numri li jistgħu jkunu node dritt tiegħi,
imma jekk jien n għadd totali, allura l-ammont li tista 'tmur lejn ix-xellug
flimkien mal-ammont li jista 'jmur lejn il-lemin huwa n - 1.
Allura tan-numri li jifdal, dawn għandhom ikunu jistgħu jmorru jew lejn ix-xellug jew il-lemin.
Jidher diffiċli li, jekk nressaq 3 1 allura kollox irid imur lejn ix-xellug,
imma jekk nressaq 7, allura xi affarijiet jistgħu jmorru ix-xellug tal-u xi affarijiet jistgħu jmorru lejn il-lemin.
U billi '3 '1 I fisser kollox tista' tmur lejn il-lemin.
Huwa tassew, inti biss għandek biex jaħsbu dwar dan bħala,
affarijiet kemm tista 'tmur fuq il-livell li jmiss tas-siġra.
U niġu biex tkun 14; jew inti tista 'tiġbed minnhom kollha,
u allura inti ser tingħata 14.
>> Jmorru lura hawn,
"Siġar Ordered binarji huma jibred għaliex aħna tista 'tfittex permezz tagħhom
b'mod simili ħafna għal tiftix fuq firxa magħżula.
Biex tagħmel dan, nibdew l-għerq u x-xogħol mod tagħna isfel fil-siġra
lejn weraq, verifika valuri kull node kontra l-valuri li aħna qed tfittex.
Jekk il-valur tal-node attwali hija inqas mill-valur aħna qed tfittex,
inti tmur ħdejn tfal id-dritt tal-node s.
Inkella, inti tmur tifel xellug tal-node s.
F'xi punt, inti ser issib kemm il-valur li qed tfittex, jew tkun taf run fis null,
jindika l-valur mhux fil-siġra. "
Għandi biex tiġbed l-siġra kellna qabel; li ser tieħu t-tieni.
Iżda rridu nħarsu up jekk 6, 10, u 1 huma fil-siġra.
Allura dak li kien, 7, 9, 3, 6. Okay.
In-numri li inti tixtieq tfittex up, irridu li tfittex up 6.
Kif taħdem din algoritmu?
Ukoll, irridu wkoll xi pointer għeruq għall siġra tagħna.
U aħna se jmorru għall-għerq u jgħidu, hija din il-valur ekwivalenti għall-valur aħna qed tiftix għal?
Allura aħna qed infittxu 6, dan mhuwiex ugwali.
Allura aħna iżommu għaddejjin, u issa nistgħu ngħidu, okay, sabiex 6 huwa inqas minn 7.
Dan ifisser li aħna rridu li jmorru lejn ix-xellug, jew irridu li jmorru lejn il-lemin?
[Student] Xellug. >> Yeah.
Huwa ferm aktar faċli, kull ma għandek tagħmel hu li jiġbed 1 node possibbli tas-siġra
u allura inti don 't - minflok tipprova biex jaħsbu fir-ras,
okay, jekk huwa inqas, ma mmur lejn ix-xellug jew mur fuq il-lemin,
biss tħares lejn din l-istampa, huwa ċar ħafna li I ikollhom imorru lejn ix-xellug
jekk dan node huwa akbar mill-valur li jien infittxu.
Allura inti tmur lejn ix-xellug, issa jien fi 3.
Irrid li - 3 huwa anqas mill-valur jien infittxu, li hija 6.
Allura aħna jmorru lejn il-lemin, u issa I jispiċċaw ta '6,
li huwa l-valur jien infittxu, so I ritorn vera.
Il-valur li jmiss jien ser tfittex huwa 10.
Okay. Allura 10, issa, se - cut off li - ser isegwu l-għerq.
Issa, 10 se tkun ikbar minn 7, so I tixtieq tfittex għad-dritt.
Jien ser jiġi maż hawn, 10 se tkun ikbar minn 9,
hekk jien ser tixtieq tfittex għad-dritt.
Nasal hawn fuq, iżda minn hawn issa jien fil null.
X'għandi nagħmel jekk I hit null?
[Student] Ritorn falza? >> Yeah. I ma sabx 10.
1 se jkun hemm każ kważi identiċi,
ħlief huwa biss se jiġu flipped; minflok tħares
fuq il-lemin, jien ser tħares mal-linja xellugija.
>> Now I think we attwalment tikseb għall-kodiċi.
Hawn fejn - tiftaħ il-appliance CS50 u jinnavigaw mod tiegħek hemmhekk,
imma int tista 'wkoll biss tagħmel dan fl-ispazju.
Huwa probabbilment ideali biex jagħmlu dan fl-ispazju,
għaliex nistgħu naħdmu fl-ispazju.
"L-ewwel għandna bzonn definizzjoni tip ġdid għal node siġra binarju jkun fih valuri int.
Uża l-boilerplate typedef hawn taħt,
toħloq definizzjoni tip ġdid għal node fil-siġra binarju.
Jekk ikollok staġnati. . . "Blah, blah, blah. Okay.
Mela ejja tpoġġi l-boilerplate hawn,
typedef Struct node, u node. Yeah, okay.
Allura x'inhuma l-oqsma aħna qed tmur jridu fil node tagħna?
[Student] Int u allura żewġ pointers?
>> Int valur, żewġ pointers? Kif nista 'tikteb l-pointers?
[Student] Struct. >> I għandha zoom pulzieri Yeah, hekk Struct node * xellug,
u Struct node * dritt.
U ftakar-diskussjoni mill-aħħar darba,
li dan jagħmel ebda sens, dan jagħmel ebda sens,
dan jagħmel ebda sens.
Ikollok bżonn kollox hemm biex jiddefinixxu din Struct rikursivi.
Okay, hekk dan huwa dak siġra tagħna se look like.
Jekk għamilna siġra trinary, allura node jista 'dehra b1, b2, Struct * node b3,
fejn b hija fergħa - fil-fatt, stajt aktar smajtu xellug,, id-dritt tan-nofs, iżda tkun xi tkun.
Aħna biss jimpurtahom binarju, hekk id-dritt, xellug.
"Issa tiddikjara varjabbli globali * node għall-għerq tal-siġra."
Allura aħna ma tkunx qed tmur biex tagħmel dan.
Sabiex tagħmel l-affarijiet ftit aktar diffiċli u aktar ġeneralizzata,
aħna mhux se jkollhom varjabbli node globali.
Minflok, fl prinċipali aħna se jiddikjara l-affarijiet node tagħna,
u dan ifisser li hawn taħt, meta aħna tibda taħdem
ma fiha l-funzjoni tagħna u l-funzjoni daħħal tagħna,
minflok ma fiha tagħna jaħdem biss bl-użu dan il-varjabbli node globali,
aħna qed tmur biex ikollhom dan jieħu bħala argument l-siġra li aħna rridu li jipproċessaw.
Wara li l-varjabbli globali kien suppost li tagħmel affarijiet eħfef.
Aħna ser tagħmel l-affarijiet aktar diffiċli.
Issa tieħu minuta jew hekk biex biss tagħmel dan it-tip ta 'ħaġa,
fejn ġewwa tal ewlenija tixtieq toħloq din is-siġra, u li kollox inti trid tagħmel.
Ipprova u jibnu din is-siġra fil-funzjoni prinċipali tiegħek.
>> Okay. Allura inti ma jkollhomx biex tkun mibnija l-siġra l-mod kollu s'issa.
Imma ħadd xi ħaġa I tista 'pull up
biex turi kif wieħed jista 'jibda jibni tali siġra?
[Student] banging Xi ħadd, tipprova toħroġ.
[Bowden] Kull min komda mal-kostruzzjoni siġra tagħhom?
[Student] Sure. Huwa ma jsirx. >> Huwa tal-multa. Nistgħu biss finitura -
oh, tista 'tfaddal dan? Hooray.
Allura hawnhekk għandna - oh, jien ftit maqtugħa.
Am I żżomjati fil-?
Zoom fil-scroll barra. >> Għandi mistoqsija. >> Yeah?
[Student] Meta inti tiddefinixxi Struct, huma affarijiet simili initialized għal xejn?
[Bowden] No >> Okay. Allura inti jkollha initialize -
[Bowden] No Meta inti tiddefinixxi, jew meta inti tiddikjara Struct,
mhuwiex initialized fil-kontumaċja; huwa biss simili jekk inti tiddikjara int.
Huwa eżattament l-istess ħaġa. Huwa simili kull wieħed mill-oqsma individwali tiegħu
jista 'jkollhom valur żibel fiha. >> U huwa possibbli li wieħed jiddefinixxi - jew li jiddikjara Struct
b'mod li dan ma initialize minnhom?
[Bowden] Iva. Allura, sintassi inizjalizzazzjoni shortcut
se look like -
Hemm żewġ modi li nistgħu nagħmlu dan. Naħseb li għandna josservawha
biex clang żgur ukoll ma dan.
L-ordni ta 'argumenti li taqa' fil-Struct,
inti tpoġġi l-ordni ta 'argumenti ġewwa ta' dawn ċineg kaboċċi.
Mela jekk inti tixtieq li initialize li sa 9 u ħalla jiġu nulli u mbagħad dritt null,
ikun 9, null, null.
L-alternattiva hija, u l-editur ma bħal dan sintassi,
u jidhirlu Irrid blokk ġdid,
iżda l-alternattiva hija xi ħaġa simili -
hawn, jien ser poġġih fuq linja ġdida.
Tista 'b'mod espliċitu tgħid, I tinsa l-sintassi eżatta.
Allura inti tista 'espliċitament jindirizzawhom bl-isem, u jgħidu,
. C, jew. Valur = 9,. NULL xellug =.
Jien guessing dawn jeħtieġ li jkunu virgoli.
. Dritt = NULL, sabiex b'dan il-mod inti ma
fil-fatt jeħtieġ li tkun taf l-ordni tal-Struct,
u meta inti qed taqra dan, huwa ħafna aktar espliċita
dwar dak il-valur l-jiġu initialized għall.
>> Dan jiġri li jkun wieħed mill-affarijiet li -
hekk, għall-parti l-kbira, C + + huwa superset ta 'C.
Tista 'tieħu kodiċi C, jimxu jikkonsenjaha lill C + +, u għandu jikkompila.
Din hija waħda mill-affarijiet li C + + ma tagħti appoġġ, sabiex in-nies għandhom tendenza li ma tagħmel dan.
I do not know jekk dan huwa l-unika raġuni nies għandhom tendenza li ma tagħmel dan,
iżda l-każ fejn I meħtieġa sabiex jintuża meħtieġa biex taħdem ma 'C + + u so I ma setgħux jużaw dan.
Eżempju ieħor ta 'xi ħaġa li ma taħdimx mal-C + + huwa
kif malloc jirritorna "* vojt," teknikament,
imma int tista 'biss jgħidu char * x kwalunkwe malloc =,
u se awtomatikament mitfugħa sabiex a * char.
Dan mitfugħa awtomatika ma jiġri fis-C + +.
Dan ma jkunx tiġbor, u inti espliċitament bżonn li ngħidu
* char, malloc, tkun xi tkun, li jitfa hija għal * char.
M'hemmx ħafna affarijiet li C u C + + ma jaqblux fuq,
imma dawn huma tnejn.
Allura aħna ser jmorru ma 'dan sintassi.
Iżda anke jekk aħna ma jmorru ma 'dak sintassi,
dak li hu - jista 'jkun ħażin ma' dan?
[Student] I m'għandhomx bżonn li dereference dan? >> Yeah.
Ftakar li l-vleġġa għandha dereference impliċitu,
u għalhekk meta aħna qed biss jittrattaw ma 'Struct,
irridu jużaw. tikseb fuq ġewwa qasam ta 'l-Struct.
U l-ħin biss nużaw vleġġa huwa meta rridu nagħmlu -
ukoll, vleġġa huwa ekwivalenti għal -
dan huwa dak li kienet tfisser jekk I użati vleġġa.
Kollha mezzi vleġġa qiegħda, dereference dan, issa jien fuq Struct, u nista 'nikseb il-qasam.
Jew jiksbu l-qasam direttament jew dereference u jiksbu l-qasam -
I raden dan għandu jkun il-valur.
Imma hawn jien li jittrattaw biss bi Struct, mhux pointer għal Struct,
u so I ma tistax tuża l-vleġġa.
Iżda dan it-tip ta 'ħaġa li nistgħu nagħmlu għall-lymph.
Oh my God.
Dan huwa 6, 7, u 3.
Imbagħad nistgħu stabbilit il-fergħat fil-siġra tagħna, aħna jista 'jkollna 7 -
jista 'jkollna, xellug tagħha għandu punt sa 3.
Allura kif nistgħu nagħmlu dan?
[Studenti, mhux intelliġibbli] >> Yeah. L-indirizz tal node3,
u jekk inti ma kellhiex indirizz, allura biss ma jikkumpilaw.
Imma ftakar li dawn huma indikaturi għall-lymph jmiss.
Id-dritt għandu jiġi sa 9,
u 3 għandhom jindikaw fuq id-dritt għal 6.
Naħseb li dan huwa stabbilit. Xi kummenti jew mistoqsijiet?
[Student, mhux intelliġibbli] L-għerq se tkun 7.
Nistgħu biss jgħidu node * ptr =
jew, għeruq = & node7.
>> Għall-għanijiet tagħna, aħna qed tmur biex tkun jittrattaw daħħal,
hekk aħna qed tmur jridu jiktbu funzjoni li ddaħħal fil din is-siġra binarju
u daħħal hija inevitabbilment ser sejħa malloc li jinħoloq node ġdid għal din is-siġra.
Allura l-affarijiet se tikseb messy mal-fatt li xi glandoli
bħalissa fuq il-munzell
u l-lymph oħra ser jispiċċaw fuq il-borġ meta aħna daħħal minnhom.
Dan huwa perfettament validu, iżda l-unika raġuni
aħna kapaċi li jagħmlu dan fuq il-munzell
huwa għaliex dan huwa tali eżempju artifiċjali li nafu
l-siġra suppost tkun mibnija b'mod 7, 3, 6, 9.
Jekk aħna ma kellhomx din, allura aħna ma jkollhomx malloc fl-ewwel post.
Kif Ser naraw daqsxejn aktar tard, għandna nkunu malloc'ing.
Dritt issa huwa perfettament raġonevoli li jitpoġġew fuq il-munzell,
imma ejja bidla dan għal implimentazzjoni malloc.
Allura kull wieħed minn dawn huwa issa se tkun xi ħaġa simili
node * node9 = malloc (sizeof (node)).
U issa aħna qed tmur biex ikollhom jagħmlu verifika tagħna.
jekk (node9 == NULL) - I ma riedx li -
ritorn 1, u allura nistgħu nagħmlu node9-> għaliex issa dan huwa pointer,
valur = 6, node9-> = NULL xellug,
node9-> = NULL dritt,
u aħna qed tmur biex ikollhom jagħmlu dan għal kull waħda minn dawn lymph.
Allura minflok, ejja poġġih ġewwa ta 'funzjoni separata.
Ejja sejħa hija node * build_node,
u dan huwa pjuttost simili għall-APIs aħna jipprovdu għall Huffman kodifikazzjoni.
Aħna nagħtuk l-funzjonijiet initializer għal siġra
u deconstructor "funzjonijiet" għal dawk is-siġar u l-istess għall-foresti.
>> Allura hawnhekk aħna qed tmur biex ikollhom funzjoni initializer
għal ftit jibnu node għalina.
U li għaddej biex tħares pretty ħafna eżattament bħal dan.
U jien anke se tkun għażżien u ma jinbidel l-isem tal-varjabbli,
anki jekk node9 jagħmel ebda sens aktar.
Oh, I raden il-valur node9 li ma kellux 6.
Issa nistgħu lura node9.
U hawn għandna ritorn null.
Kulħadd jaqbel dwar dik il-funzjoni jibnu-a-node?
Allura issa nistgħu biss sejħa li jibnu kwalunkwe node b'valur partikolari u indikaturi nulla.
Issa nistgħu sejħa li, nistgħu nagħmlu node * node9 = build_node (9).
U ejja do. . .
6, 3, 7, 6, 3, 7.
U issa aħna tixtieq li twaqqaf l-pointers istess,
ħlief issa kollox huwa diġà f'termini tal pointers
sabiex l-ebda bżonn aktar l-indirizz ta '.
Okay. Allura x'inhu l-aħħar ħaġa li nixtieq do?
Hemm żball ta 'verifika li jien ma nagħmilx.
Xi jfisser jibnu ritorn node?
[Student, mhux intelliġibbli] >> Yeah. Naqset malloc Jekk, inneħħu ritorn null.
Allura jien ser lazily tpoġġi l-isfel hawn minflok tagħmel kondizzjoni għal kull wieħed.
Jekk (node9 == NULL, jew - anki sempliċi,
din hija ekwivalenti għal biss jekk mhux node9.
Mela jekk le node9, jew mhux node6, jew mhux node3, jew mhux node7, ritorn 1.
Forsi għandna jistampaw malloc naqas, jew xi ħaġa.
[Student] Huwa falza ugwali għal null kif ukoll?
[Bowden] Kwalunkwe valur żero hija falza.
Allura null hija valur żero.
Żero huwa valur żero. Foloz huwa valur żero.
Kull - pretty ħafna l-uniċi 2 valuri żero huma nulli u żero,
falza huwa biss hash definit bħala żero.
Dan japplika wkoll jekk aħna tiddikjara varjabbli globali.
Jekk aħna ma jkollhom l-għeruq * node up hawn,
allura - il-ħaġa sbieħ dwar fatturi varjabbli globali huwa li dawn dejjem ikollhom valur inizjali.
Li mhux veru tal-funzjonijiet, kif ġewwa ta 'hawn,
jekk ikollna, bħal, * node node jew x.
Għandna l-ebda idea dak x.value, x.whatever,
jew nistgħu jistampaw minnhom u dawn jistgħu jkunu arbitrarja.
Li mhux veru ta 'varjabbli globali.
Għerq Allura node node jew x.
Permezz ta 'default, dak kollu li globali, jekk mhux espliċitament initialized sa ċertu valur,
għandu valur żero bħala l-valur tagħha.
Allura hawnhekk, għeruq * node, aħna ma espliċitament initialize li xejn,
sabiex il-valur default tiegħu se tkun nulla, li huwa l-valur żero ta 'indikaturi.
Il-valur ta 'default ta' x se jfisser li x.value huwa żero,
x.left hija nulla, u x.right huwa null.
Allura peress li huwa Struct, kollha ta 'l-oqsma ta' l-Struct se jkun b'valur żero.
Aħna ma bżonn jużaw dan hawn, għalkemm.
[Student] Il-structs huma differenti minn varjabbli oħra, u l-varjabbli l-oħra
Valuri taż-żibel; dawn huma żerijiet?
[Bowden] Valuri oħra wisq. Għalhekk fl x, x se jkun żero.
Jekk huwa fuq firxa globali, ikollu valur inizjali. Okay. >>
[Bowden] Jew il-valur inizjali inti tatha jew żero.
Naħseb li jieħu ħsieb ta 'dan kollu.
>> Okay. Allura l-parti li jmiss tal-mistoqsija tistaqsi,
"Issa rridu li jiktbu funzjoni msejħa fih
ma 'prototip ta' bool fih valur int. "
Aħna mhux se tagħmel bool fih valur int.
Prototip tagħna se look like
bool fih (valur int.
U allura aħna wkoll qed tmur biex tgħaddih-siġra
li għandu jiġi verifikat biex tara jekk ikollu dak il-valur.
Allura node * siġar). Okay.
U allura nistgħu sejħa hija ma 'xi ħaġa simili,
forsi aħna ser jridu printf jew xi ħaġa.
Fih 6, għeruq tagħna.
Dan għandu jirritorna wieħed, jew vera,
billi fih 5 għerq għandu jirritorna falza.
Allura tieħu t-tieni biex jimplimentaw dan.
Tista 'tagħmel dan jew iteratively jew recursively.
Il-ħaġa sbieħ dwar il-mod kif konna stabbiliti affarijiet up huwa li
tippresta ruħha għall-soluzzjoni rikursivi tagħna ħafna aktar faċli
milli l-mod globali-varjabbli għamlet.
Għaliex jekk aħna biss għandhom jinkludi valur int, allura għandna l-ebda mod ta 'recursing isfel subtrees.
Aħna jkollu bżonn li jkollu funzjoni helper separata li recurses r-subtrees għalina.
Iżda peress li aħna stajt mibdula biex tieħu l-siġra bħala argument,
li għandha dejjem kienu fl-ewwel post,
Issa nistgħu recurse aktar faċilment.
Allura iterattiv jew rikursivi, aħna ser jmorru fuq it-tnejn,
imma aħna ser tara li l-truf jirrikorri biex tkun pjuttost faċli.
Okay. Ħadd ma jkollu xi ħaġa li nistgħu naħdmu ma?
>> [Student] Stajt ltqajna iterattiv soluzzjoni. >> Kull dritt, iterattiv.
Okay, dan jidher tajjeb.
Allura, tixtieq li jimxu lilna permezz ta 'dan?
[Student] Sure. So I sett ta 'varjabbli temperatura li jiksbu l-node 1 tas-siġra.
U mbagħad I biss looped permezz filwaqt temperatura ma null ugwali,
sabiex filwaqt li kien għadu fil-siġra, I raden.
U jekk il-valur huwa ugwali għall-valur li temperatura hija li tipponta lejn,
allura dan jirritorna dak il-valur.
Inkella, hija għandha tivverifika jekk huwa fuq il-lemin jew ix-xellug.
Jekk inti qatt tikseb sitwazzjoni fejn hemm l-ebda siġra aktar,
allura dan jirritorna - meta toħroġ il-linja u prospetti foloz.
[Bowden] Okay. Allura li jidher tajjeb.
Kull min ikollu xi kummenti dwar xi ħaġa?
Għandi l-ebda kummenti korrettezza fil-livelli kollha.
L-unika ħaġa li nistgħu nagħmlu huwa dan Guy.
Oh, li għaddej biex tmur longish ftit.
I ser jiffissaw dan up. Okay.
>> Kulħadd għandhom jiftakru jaħdem tenarji kif.
Kien hemm definittivament ġew kwizzijiet fil-passat
li jtik funzjoni ma 'operatur ta' tlett fibri,
u jgħidu, tittraduċi dan, jagħmel xi ħaġa li ma jużax tenarji.
Allura dan huwa każ komuni ħafna ta 'meta jiena naħseb li tuża tlett fibri,
fejn jekk xi kondizzjoni stabbilita varjabbli għal xi ħaġa,
inkella stabbilit dak il-varjabbli istess għal xi ħaġa oħra.
Dik xi ħaġa li ħafna drabi tista 'tiġi ttrasformata dan it-tip ta' ħaġa
fejn tistabbilixxi li varjabbli għal dan - jew, ukoll, dan huwa minnu? Imbagħad dan, inkella dan.
[Student] L-ewwel waħda hija jekk vera, right?
[Bowden] Yeah. Il-mod I dejjem taqra li huwa, temperatura ugwali valur akbar mill-valur temperatura,
allura dan, inkella dan. Huwa tistaqsi mistoqsija.
Huwa akbar? Imbagħad jagħmlu l-ewwel ħaġa. Inkella jagħmlu l-ħaġa tieni.
I kważi dejjem - il-kolon, I biss - fir-ras tiegħi, I jaqra kif ieħor.
>> Ħadd ma jkollu soluzzjoni rikursivi?
Okay. Dan wieħed aħna qed tmur biex - jista 'diġà jkun kbir,
imma aħna qed tmur biex jagħmilha ferm aħjar.
Dan huwa pjuttost l-idea eżatt l-istess.
Huwa biss, ukoll, inti tixtieq li tispjega?
[Student] Sure. Allura aħna qed jagħmlu ċert li l-siġra ma jkunx null 1,
għaliex jekk l-siġra huwa null allura huwa għaddej biex jirritornaw foloz għaliex aħna ma sabu dan.
U jekk hemm għadu siġra, immorru fis - aħna l-ewwel jiċċekkja jekk il-valur huwa l-node kurrenti.
Ritorn veru jekk huwa, u jekk mhux aħna recurse fuq il-lemin jew xellug.
Does that ħoss xierqa? >> Mm-HMM. (Ftehim)
Allura avviż li din hija kważi - strutturalment simili ħafna għall-soluzzjoni iterattiv.
Huwa biss li minflok recursing, kellna loop waqt.
U l-każ bażiku hawn fejn siġra ma null ugwali
kienet il-kundizzjoni li taħtha aħna kissru barra mill-linja waqt.
Huma qed simili ħafna. Iżda aħna qed tmur biex tieħu dan il-pass wieħed ieħor.
Issa, nagħmlu l-istess ħaġa hawn.
Avviż aħna qed jirritornaw l-istess ħaġa f'dawn iż-żewġ linji,
ħlief għal wieħed argument huwa differenti.
Allura aħna qed tmur biex jagħmlu dak ġo tenarji.
I hit xi ħaġa għażla, u għamel simbolu. Okay.
Allura aħna qed tmur biex jirritorna fih dik.
Dan huwa li jkollna jkun linji multipli, ukoll, żżomjati fl huwa.
Normalment, bħala ħaġa stilistika, ma naħsibx ħafna nies
tpoġġi l-ispazju wara l-vleġġa, imma I raden jekk int konsistenti, huwa multa.
Jekk il-valur huwa inqas mill-valur tas-siġar, irridu recurse fuq ix-xellug siġra,
inkella rridu recurse fuq id-dritt tas-siġar.
Allura li kien pass wieħed ta 'kif issir din tfittex iżgħar.
Pass 2 ta 'kif issir din tfittex iżgħar -
nistgħu separati din għal linji multipli.
Okay. Pass 2 ta 'jagħmilha ħarsa iżgħar hija hawnhekk,
sabiex il-valur tar-ritorn ugwali valur siġra, jew ikun fiha kwalunkwe.
>> Din hija ħaġa importanti.
M'inix ċert jekk hu qal li b'mod espliċitu fil-klassi,
iżda huwa msejjaħ short-circuit evalwazzjoni.
L-idea hija valur == valur siġra.
Jekk dan huwa minnu, allura dan huwa minnu, u rridu li "jew" li ma dak kollu li huwa minn hawn.
Allura mingħajr ma jaħsbu dwar dak kollu li huwa minn hawn,
dak li huwa l-espressjoni sħiħa ser jirritornaw?
[Student] Veru? >> Yeah, minħabba vera ta 'xejn,
or'd - or'd jew vera ma xejn huwa neċessarjament il-każ.
Allura hekk kif naraw valur tar-ritorn valur siġra =,
aħna qed biss jmorru lura veru.
Mhux anki tmur recurse aktar fih il-linja.
Nistgħu nkunu dan il-pass wieħed ieħor.
Siġra Ritorn ma null ugwali u kollha ta 'dan.
Hija għamlitha funzjoni waħda line.
Dan huwa wkoll eżempju ta 'short-circuit evalwazzjoni.
Imma issa huwa l-istess idea -
minflok - hekk jekk siġra ma null ugwali - jew, ukoll,
jekk siġra ma null ugwali, li huwa l-każ ħażin,
jekk siġra ugwali null, allura l-ewwel kundizzjoni se tkun falza.
Allura foloz anded ma 'xi ħaġa se tkun liema?
[Student] Foloz. >> Yeah. Dan huwa l-nofs l-ieħor ta 'ċirkwit qasir evalwazzjoni,
fejn jekk siġra ma null mhux ugwali, allura aħna mhux se anki jmorru -
jew jekk siġra ma null ugwali, allura aħna mhux se jagħmlu valur == valur siġra.
Aħna biss se immedjatament lura falza.
Li huwa importanti, peress li jekk hija ma short-circuit jevalwa,
allura jekk siġra ma null ugwali, din it-tieni kundizzjoni se tort seq,
minħabba siġra-> valur dereferencing null.
Allura dak li. Jista 'jagħmel dan - ċċaqlaq darba fuq.
Din hija ħaġa komuni ħafna wkoll, ma tkunx qed tagħmel din il-linja 1 ma 'dan,
iżda hija ħaġa komuni fil-kondizzjonijiet, forsi mhux dritt hawn,
imma jekk (! siġra = NULL, u siġra-> valur == valur), jagħmlu dak kollu.
Din hija kundizzjoni komuni ħafna, fejn minflok li
li jiksru dan f'żewġ IFs, fejn tixtieq, hija l-null siġra?
Okay, mhuwiex null, hekk issa huwa l-valur siġra ugwali għall-valur? Agħmel dan.
Minflok, din il-kundizzjoni, dan qatt ma se seg tort
minħabba li se break out jekk dan jiġri li jkun null.
Well, I raden jekk siġra tiegħek huwa pointer kompletament invalidu, xorta tista seg tort,
iżda ma jistax seg tort jekk siġra huwa null.
Kieku kien null, ikun break out qabel ma inti qatt dereferenced-pointer fl-ewwel post.
[Student] Huwa dan valutazzjoni għażżien imsejħa?
>> [Bowden] evalwazzjoni għażżien hija ħaġa separata.
Evalwazzjoni għażżien huwa aktar simili inti titlob għal xi valur,
inti ssaqsi li jiġi kkalkolat valur, tip ta ', imma inti m'għandekx bżonn dan immedjatament.
Allura sakemm inti fil-fatt bżonn, mhuwiex evalwat.
Dan mhux eżattament l-istess ħaġa, iżda fil-pset Huffman,
jgħid li aħna "lazily" tikteb.
Ir-raġuni nagħmlu dan huwa għaliex aħna qed attwalment lqugħ l write -
aħna ma jridu jiktbu bits individwali fi żmien,
jew bytes individwali kull darba, aħna minflok rridu nġibu blokki ta 'bytes.
Imbagħad ladarba għandna blokki ta 'bytes, allura aħna ser jiktbu out.
Anke jekk inti ssaqsi lilha biex jiktbu - u fwrite u fread jagħmlu l-istess tip ta 'ħaġa.
Huma buffer jaqra tiegħek u jikteb.
Anke jekk inti ssaqsi lilha biex tikteb immedjatament, hija probabbilment mhux se.
U inti ma jistgħux ikunu żguri li l-affarijiet ser ikunu bil-miktub
sakemm inti sejħa hfclose jew kwalunkwe huwa,
li mbagħad jgħid, okay, jien għeluq file tiegħi,
dan ifisser I d aħjar tikteb kollox I ma jkunux miktuba s'issa.
Hija l-ebda ħtieġa li tikteb kollox barra
sakemm inti qed jagħlqu l-fajl, u mbagħad jeħtieġ li.
Hekk li jinsab biss dak għażżien - huwa tistenna sakemm għandu jiġri.
Dan - jieħu 51 u tkun taf tmur fis dan f'aktar dettall,
minħabba OCaml u kollox fil-51, kollox huwa recursion.
M'hemm l-ebda iterattiv soluzzjonijiet, bażikament.
Kollox huwa recursion, u l-evalwazzjoni għażżien
se tkun importanti għal-lott ta 'ċirkostanzi
fejn, jekk inti ma lazily tevalwa, dan ikun ifisser -
L-eżempju huwa flussi, li huma infinitament twil.
Fit-teorija, inti tista 'taħseb-numri naturali bħala nixxiegħa ta' 1-2-3-4-5-6-7,
Affarijiet Allura lazily evalwati huma multa.
Jekk jiena ngħid irrid in-numru 10, imbagħad I tista 'tevalwa san-numru 10.
Jekk irrid in-numru mija, imbagħad I tista 'tevalwa san-numru mija.
Mingħajr evalwazzjoni għażżien, allura huwa għaddej biex tipprova tevalwa numri kollha immedjatament.
Int evalwazzjoni numri infinitament ħafna, u li jinsab biss mhux possibbli.
Allura hemm ħafna ta 'ċirkostanzi fejn għażżien evalwazzjoni
huwa biss essenzjali li jkollna affarijiet għax-xogħol.
>> Issa rridu li tikteb daħħal fejn daħħal se tkun
bl-istess mod jinbidlu fid-definizzjoni.
Allura issa dritt huwa daħħal bool (valur int).
Aħna ser jibdlu dik li daħħal bool (int valur, node * siġar).
Aħna fil-fatt se jibdlu dan mill-ġdid fi ftit, aħna ser tara għaliex.
U ejja jimxu build_node, biss għall-Heck ta 'dan,
hawn daħħal hekk aħna ma jkollhom jiktbu prototip funzjoni.
Liema huwa ħjiel li int ser tkun qed tuża build_node fl daħħal.
Okay. Ħu minuta għal dan.
I think I ffrankati r-reviżjoni jekk inti tixtieq li pull minn dan,
jew, għall-inqas, I ma issa.
I riedu waqfa żgħira biex jaħsbu dwar il-loġika ta 'daħħal,
jekk inti ma tista 'taħseb dan.
Bażikament, inti biss qatt jiġu inseriti fil-weraq.
Bħal, jekk I daħħal 1, allura jien inevitabbilment ser ikunu inseriti 1 -
I ser bidla għall-iswed - I'll jiġu inseriti 1 hawn fuq.
Jew jekk I daħħal 4, nixtieq li jkun ddaħħal 4 hawn fuq.
Allura l-ebda kwistjoni dak li inti tagħmel, int se tkun ddaħħal fil-weraq.
Kulma għandek tagħmel huwa jtenni r-siġra sakemm ikollok il-node
li għandha tkun ġenitur l-node, il-ġenitur l-node ġdid,
u mbagħad bidla pointer xellug jew id-dritt tagħha, jiddependi fuq jekk
huwa akbar minn jew inqas mill-node kurrenti.
Bidla li pointer għall-punt li node ġdida tiegħek.
Allura ttenni r-siġra, jagħmlu l-punt weraq tal-node ġdid.
Ukoll jaħsbu dwar għaliex li tipprojbixxi t-tip ta 'sitwazzjoni qabel,
fejn I mibnija l-siġra binarju fejn kien korrett
jekk inti biss ħares lejn node wieħed,
imma 9 kien fuq ix-xellug ta '7 jekk inti tenna l isfel it-triq kollha.
Allura dak impossibbli f'dan ix-xenarju, peress li -
jaħsbu dwar ddaħħal 9 jew xi ħaġa; fl-node ewwel,
Jien ser tara 7 u jien biss se jmorru lejn il-lemin.
Allura l-ebda kwistjoni dak I do, jekk jien ddaħħal billi tmur werqa,
u biex werqa permezz tal-algoritmu xierqa,
li għaddej biex tkun impossibbli għalija li daħħal 9 ix-xellug ta '7
għaliex malli I hit 7 jien ser imorru lejn il-lemin.
Ħadd ma jkollu xi ħaġa li tibda bil?
[Student] I do. >> Sure.
[Student, mhux intelliġibbli]
[Student ieħor, mhux intelliġibbli]
[Bowden] Huwa apprezzat. Okay. Trid jispjegaw?
>> [Student] Peress li nafu li konna ddaħħal
punti strateġiċi ġodda fl-aħħar tas-siġra,
I looped permezz tal-siġra iteratively
sakemm sibt li node li indikat null.
U mbagħad I iddeċieda li tqiegħed lilha jew fuq il-lemin jew ix-xellug
jużaw dan il-varjabbli id-dritt; dan qalli fejn li tqiegħed lilha.
U mbagħad, essenzjalment, I biss magħmula li l-aħħar -
dan il-punt node temperatura għall-node ġdid li kien joħloq,
jew fuq ix-xellug jew fuq il-lemin, jiddependi fuq dak il-valur id-dritt kien.
Fl-aħħarnett, I stabbilit il-valur node ġdid għall-valur tal-ittestjar tagħha.
[Bowden] Okay, so I ara waħda kwistjoni.
Dan huwa simili 95% tal-mod hemmhekk.
Il-kwistjoni waħda li nara, ukoll, ma xi ħadd ieħor tara kwistjoni?
X'inhu l-ċirkustanza li taħtha break out tal-linja?
[Student] Jekk temperatura huwa null? >> Yeah. Allura kif inti break out tal-linja hija jekk temperatura hija nulla.
Imma x'għandi nagħmel dritt hawn?
I dereference temperatura, li huwa inevitabbilment null.
Allura l-ħaġa oħra li għandek bżonn tagħmel huwa mhux biss iżommu kont sakemm temperatura huwa null,
inti tixtieq li żżomm rekord tal-ġenitur fil-ħinijiet kollha.
Aħna rridu wkoll ġenitur * node, I raden aħna nkunu nistgħu nżommu dak in null fl-ewwel.
Dan huwa se jkollu l-imġiba stramb għall-għerq tal-siġra,
iżda aħna ser jiksbu għal dak.
Jekk il-valur ikun akbar minn kwalunkwe, allura d-dritt temperatura temperatura =.
Iżda qabel ma nagħmlu dan, ġenitur = temperatura.
Jew li huma ġenituri dejjem se temperatura ugwali? Huwa li l-każ?
Jekk temperatura ma huwiex null, allura jien ser jinżel, irrelevanti x'inhu,
għal node li għalih temperatura hija l-ġenitur.
Allura ġenitur għaddej biex tkun temperatura, u mbagħad I jimxu temperatura isfel.
Issa temperatura hija nulla, iżda jinnota prinċipali għall-ġenitur tal-ħaġa li hija nulla.
Allura stabbiliti hawn, jien ma jridux stabbilit id-dritt huwa ugwali għal 1.
So I mċaqalqa lejn il-lemin, hekk jekk id-dritt = 1,
u I raden inti tixtieq ukoll li tagħmel -
jekk inti tmur lejn ix-xellug, inti tixtieq li twaqqaf id-dritt ugwali għal 0.
Jew inkella jekk inti qatt timxi lejn il-lemin.
Allura dritt = 0. Jekk id-dritt = 1,
issa irridu li l-ġenitur newnode pointer dritt,
inkella irridu li l-ġenitur newnode pointer xellug.
Mistoqsijiet dwar li?
Okay. Allura dan huwa l-mod aħna - ukoll, fil-fatt, minflok tagħmel dan,
aħna 1/2 mistennija biex tuża build_node.
U mbagħad jekk newnode ugwali null, ritorn foloz.
Dak li. Issa, dan huwa dak li aħna mistennija li inti tagħmel.
>> Dan huwa dak li s-soluzzjonijiet Persunal tagħhom jagħmlu.
Ma naqbilx ma 'dan bħala l-"dritt" mod ta' għaddej dwar dan
iżda dan huwa perfettament multa u se taħdem.
Ħaġa waħda thats dritt stramb ftit issa huwa
jekk l-siġra jibda off bħala null, aħna jgħaddu fil-siġra null.
I raden jiddependi fuq kif inti tiddefinixxi l-imġiba ta tgħaddi fil-siġra null.
Jiena naħseb li jekk inti tgħaddi fil-siġra null,
mbagħad ddaħħal il-valur fis-siġra null
għandhom biss ritorn siġra fejn il-valur biss hija li node wieħed.
In-nies jaqblu ma 'dak? Inti tista ', jekk int riedu,
jekk inti tgħaddi fil-siġra null
u inti tixtieq li daħħal il-valur fis dan, ritorn foloz.
Huwa sa inti biex jiddefinixxu dik.
Biex tagħmel l-ewwel ħaġa li għidt u mbagħad -
tajjeb, int ser jkollhom problemi tagħmel dan, minħabba li
ikun aktar faċli jekk kellna pointer globali għall-ħaġa,
iżda aħna ma, hekk jekk siġra huwa null, m'hemm xejn li nistgħu nagħmlu dwar dan.
Nistgħu biss ritorn foloz.
Allura jien se jibdlu daħħal.
Aħna teknikament jista 'biss bidla dan id-dritt hawn,
kif huwa iterazzjoni fuq affarijiet,
imma jien se jibdlu daħħal tieħu node ** siġra.
Pointers Double.
Xi jfisser dan?
Minflok li jittrattaw ma pointers għal punti strateġiċi,
il-ħaġa jien ser tkun manipulazzjoni hija din pointer.
Jien ser tkun manipulazzjoni dan il-werrej.
Jien ser tkun manipulazzjoni pointers direttament.
Dan jagħmel sens għaliex, jaħsbu dwar down -
ukoll, id-dritt issa dan jipponta lejn null.
Dak li nixtieq tagħmel hu li jimmanipulaw dan pointer għall-punt li ma null.
Irrid li punt li node ġdida tiegħi.
Jekk I biss iżommu rekord ta 'indikaturi għall-pointers tiegħi,
imbagħad I m'għandhomx bżonn li jżommu rekord ta 'pointer ġenitur.
I tista 'sempliċement iżommu kont biex tara jekk il-pointer hija li tipponta lejn null,
u jekk il-pointer hija li tipponta lejn null,
bidla għall-punt li l-node nixtieq.
U nista 'bidla dan peress I jkollhom pointer għall-pointer.
Ejja naraw dan id-dritt issa.
Inti tista 'attwalment jagħmlu dan recursively pjuttost faċilment.
Do rridu nagħmlu dan?
Iva, nagħmlu.
>> Ejja naraw dan recursively.
L-ewwel, dak li huwa każ ta 'bażi ​​tagħna se tkun?
Kważi dejjem il-każ bażi tagħna, imma fil-fatt, dan huwa tip ta 'delikata.
L-ewwelnett, jekk (== NULL siġra)
I raden aħna qed biss jmorru lura falza.
Din hija differenti minn null siġra tkun tiegħek.
Dan huwa l-pointer li għerq pointer tiegħek qed null
li jfisser li pointer għerq tiegħek ma teżistix.
Allura stabbiliti hawn, jekk nagħmel
* node - ejja biss użu mill-ġdid dan.
Node * għerq = NULL,
u mbagħad jien ser sejħa daħħal billi tagħmel xi ħaġa simili,
daħħal 4 fis & għerq.
Allura & għeruq, jekk għerq huwa * node
allura & għerq se jkun hemm ** node.
Dan huwa validu. F'dan il-każ, siġar, l hawn,
siġra ma huwiex null - jew daħħal.
Hawnhekk. Siġra ma huwiex null; * siġra huwa null, li huwa multa
għaliex jekk siġra * huwa null, imbagħad I tista 'timmanipola dan
li issa punt għal dak li nixtieq li għall-punt li.
Imma jekk siġra huwa null, dan ifisser I biss niżlet hawn u qal null.
Dan ma jagħmilx sens. I ma tistax tagħmel xejn ma 'dak.
Jekk siġra huwa null, ritorn foloz.
So I bażikament diġà qal dak il-każ tagħna bażi reali huwa.
U dak hu li se jkun?
[Student, mhux intelliġibbli]
[Bowden] Iva. Mela jekk (* siġra == NULL).
Dan jirrigwarda l-każ hawn fuq
fejn jekk pointer aħmar tiegħi huwa l-pointer jien iffukat fuq,
hekk bħal jien iffukat fuq dan il-werrej, issa jien iffukat fuq dan il-werrej.
Issa jien iffukat fuq dan il-werrej.
Mela jekk pointer aħmar tiegħi, li hija ** node tiegħi,
huwa dejjem - jekk *, pointer aħmar tiegħi, huwa qatt null,
dan ifisser li jien fil-każ fejn jien jiffoka fuq pointer li l-punti -
dan huwa pointer li jappartjeni għal werqa.
Irrid li jibdlu dan il-werrej li jindika node ġdida tiegħi.
Come lura fuq hawn.
Newnode tiegħi se jkun biss node * n = build_node (valur)
allura n, jekk n = NULL, ritorn foloz.
Else irridu li jibdlu dak il-pointer bħalissa tipponta lejn
li issa punt għal node mibnijin ġodda tagħna.
Nistgħu attwalment jagħmlu dan hawn.
Minflok qal n, ngħidu * siġra = jekk * siġra.
Kulħadd jifhem li? Illi jittrattaw pointers għal pointers,
nistgħu nbiddlu pointers nulla għall-punt li l-affarijiet li rridu lilhom għall-punt li.
Li każ bażi tagħna.
>> Issa rikorrenza tagħna, jew recursion tagħna,
se tkun simili ħafna għal kull recursions oħra aħna kont qed tagħmel.
Aħna ser tixtieq li daħħal il-valur,
u issa jien ser tuża tlett fibri darb'oħra, iżda dak li hu kundizzjoni tagħna se tkun?
X'inhu aħna qed tfittex li jiddeċiedu jekk irridu li jmorru lemin jew xellug?
Ejja nagħmlu dan fil-passi separati.
Jekk (valur <) liema?
[Student] Valur-siġra tal-?
[Bowden] Mela ftakar li jien bħalissa -
[Studenti, mhux intelliġibbli]
[Bowden] Yeah, hekk dritt hawn, ejja ngħidu li din aħdar vleġġa
huwa eżempju ta 'dak li siġra bħalissa hu, huwa pointer għal dan il-werrej.
Allura dan ifisser I am a pointer għal pointer sa 3.
Il dereference darbtejn tinstema tajba.
What do I - kif nista 'nagħmlu dan?
[Student] Dereference darba, u mbagħad jagħmlu vleġġa li mod?
[Bowden] Mela (* siġra) huwa l-dereference darba, -> valur
huwa ser jagħti lili l-valur tal-node li jien indirettament tipponta lejn.
So I tista 'wkoll tikteb ** tree.value jekk tippreferi li.
Jew xogħlijiet.
Jekk dan huwa l-każ, allura nixtieq li sejħa daħħal il-valur.
U dak li huwa node aġġornata tiegħi ** se tkun?
Irrid immur lejn ix-xellug, sabiex ** tree.left se tkun ix-xellug tiegħi.
U Irrid li l-pointer għal dak ħaġa
b'tali mod li jekk ix-xellug jispiċċa jkun l-pointer null,
I jista 'jimmodifika din għall-punt li node ġdida tiegħi.
>> U l-każ l-ieħor jista 'jkun simili ħafna.
Ejja fil-fatt jagħmlu dan ternarji tiegħi dritt issa.
Daħħal il-valur jekk il-valur <(** siġra). Valur.
Imbagħad irridu li taġġorna ** tagħna lejn ix-xellug,
inkella irridu li taġġorna ** tagħna lejn il-lemin.
[Student] Does li jiksbu l-pointer għall-pointer?
[Bowden] Ftakar li - ** tree.right hija stilla node.
[Student, mhux intelliġibbli] >> Yeah.
** Tree.right hija bħal dan il-werrej jew xi ħaġa.
Allura billi jittieħed pointer għal dan, li tagħti me dak li nixtieq
ta 'l-pointer għal dak Guy.
[Student] Jista immorru aktar mill-ġdid għaliex aħna qed jużaw l-pointers 2?
[Bowden] Yeah. Allura - l-ebda, inti tista ', u din is-soluzzjoni qabel
kien mod ta 'kif isir dan mingħajr ma jsir 2 pointers.
Inti jeħtieġ li tkun kapaċi jifhmu jużaw żewġ pointers,
u din hija soluzzjoni aktar nadifa.
Ukoll, avviż li, x'jiġri jekk siġra tiegħi -
x'jiġri jekk għerq tiegħi kien null? X'jiġri jekk jien tagħmel dan il-każ id-dritt hawn?
Allura node * għerq = NULL, daħħal 4 fis & għerq.
X'inhu għerq se tkun wara dan?
[Student, mhux intelliġibbli] >> Yeah.
Valur Root se tkun 4.
Xellug Root se tkun nulla, id-dritt għerq se tkun nulla.
Fil-każ fejn aħna ma jgħaddu għeruq mill-indirizz,
aħna ma setgħux jimmodifikaw għerq.
Fil-każ fejn l-siġra - fejn għerq kien null,
aħna biss kellhom jirritornaw falza. M'hemm xejn stajna nagħmlu.
Ma nistgħux daħħal node fi siġra vojta.
Imma issa nistgħu; aħna biss tagħmel siġra vojta ġo siġra waħda node.
Liema normalment huwa l-mod mistenni li huwa suppost li taħdem.
>> Barra minn hekk, dan huwa ferm iqsar minn
wkoll iżżomm rekord tal-ġenitur, u għalhekk inti jtenni l isfel it-triq kollha.
Issa għandi ġenitur tiegħi, u jien biss ikollhom ġenitur dritt tiegħi pointer għall-kwalunkwe.
Minflok, jekk aħna ma dan iteratively, huwa d jkun l-istess idea ma 'linja waqt.
Iżda minflok li biex jittrattaw ma 'pointer ġenitur tiegħi,
minflok pointer kurrenti tiegħi jkun il-ħaġa
li jien direttament timmodifika għall-punt li node ġdida tiegħi.
I ma jkollhomx għalfejn jinnegozjaw ma 'jekk huwa tipponta lejn ix-xellug.
I ma jkollhomx għalfejn jinnegozjaw ma 'jekk huwa tipponta lejn il-lemin.
Huwa biss x'ikun dan il-werrej huwa, jien ser tistabbilixxi li għall-punt li node ġdida tiegħi.
Kulħadd jifhem kif taħdem?
Jekk le għaliex irridu li tagħmel dan il-mod,
iżda għall-inqas li din taħdem bħala soluzzjoni?
[Student] Fejn nerġgħu lura vera?
[Bowden] Li probabbilment dritt hawn.
Jekk aħna korrett daħħalha, ritorn veru.
Inkella, stabbiliti hawn aħna qed tmur jridu jirritornaw prospetti daħħal ikun x'ikun.
>> U x'hemm speċjali dwar din il-funzjoni rikursivi?
Huwa denb rikursivi, dan sakemm aħna jikkompilaw ma 'xi ottimizzazzjoni,
se jirrikonoxxu dan u qatt mhu ser tikseb overflow munzell minn dan,
anki jekk siġra tagħna għandu għoli ta '10,000 jew 10 miljun.
[Student, mhux intelliġibbli]
[Bowden] Naħseb tagħmlu fi Dash - jew liema livell ottimizzazzjoni
hija meħtieġa għal recursion denb għandhom ikunu rikonoxxuti.
Naħseb li tirrikonoxxi - GCC u clang
għandhom ukoll tifsiriet differenti għal livelli ottimizzazzjoni tagħhom.
Irrid ngħid huwa DashO 2, għall żgur li se jirrikonoxxu recursion denb.
Iżda aħna - inti tista 'tibni bħal eżempju Fibonocci jew xi ħaġa.
Mhuwiex faċli biex jittestjaw ma 'dan, għaliex dan huwa diffiċli biex jinbena
siġra binarju li hekk kbir.
Iżda yeah, naħseb huwa DashO 2, li
jekk inti tiġbor l DashO 2, se tfittex recursion denb
u jottimizzaw l barra.
Ejja ħa mmorru lura għall - daħħal l litteralment l-aħħar ħaġa li għandha bżonn.
Ejja ħa mmorru lura għall-insert hawn fuq
fejn aħna qed tmur biex jagħmlu l-istess idea.
Hija ser għad għandhom il-difett li ma jkunux jistgħu kompletament jimmaniġġjaw
meta l-għerq innifsu huwa null, jew id-dħul fil-passat huwa null,
iżda minflok li jittrattaw ma 'pointer ġenitur,
ejja japplikaw l-istess loġika ta 'indikaturi żamma għall pointers.
Jekk hawn inżommu node tagħna ** kur,
u aħna ma bżonn li jżommu rekord ta 'dritt aktar,
iżda node ** kur = & siġra.
U issa loop filwaqt tagħna se tkun waqt kur * ma null ugwali.
M'għandekx bżonn biex iżżomm kont tal-ġenituri aktar.
M'għandekx bżonn biex iżżomm kont ta xellug u lemin.
U jien ser sejħa dan temperatura, għaliex aħna qed diġà jużaw temperatura.
Okay. Mela jekk (valur> * temperatura),
allura & (* temperatura) -> dritt
inkella temperatura = & (* temperatura) -> xellug.
U issa, f'dan il-punt, wara dan loop filwaqt li,
I biss tagħmel dan minħabba forsi huwa aktar faċli li wieħed jaħseb dwar iteratively minn recursively,
iżda wara dan loop filwaqt li,
* Temperatura hija l-pointer li rridu bidla.
>> Qabel kellna ġenitur, u ridna li jibdlu kull ġenitur xellug jew ġenitur lemin,
imma jekk irridu li jibdlu id-dritt ġenitur,
allura * temperatura huwa dritt ġenitur, u nistgħu nbiddlu direttament.
Allura stabbiliti hawn, nistgħu nagħmlu * temperatura = newnode, u li hu.
Allura l-avviż, kull għamilna f'din kien tieħu linji ta 'kodiċi.
Sabiex iżżomm kont ta 'l-ġenitur fil dak kollu li hu sforz addizzjonali.
Hawnhekk, jekk aħna biss iżommu rekord ta 'l-pointer għall-pointer,
u anki jekk ridna li teħles minn dawn ċineg kaboċċi issa,
jagħmluha ħarsa iqsar.
Dan issa huwa l-istess soluzzjoni eżatta,
iżda linji inqas ta 'kodiċi.
Ladarba inti tibda tirrikonoxxi dan bħala soluzzjoni valida,
huwa wkoll aktar faċli biex raġuni dwar minn simili, okay,
għaliex għandi din il-bandiera fuq id-dritt int?
X'ifisser dan? Oh, huwa li jfisser li
kull darba mmur id-dritt, I ħtieġa li stabbilixxa din,
inkella jekk immur xellug I ħtieġa li jiġu stabbiliti għal żero.
Hawnhekk, jien ma jkollhom raġuni dwar dan; huwa biss aktar faċli li wieħed jaħseb dwar.
Mistoqsijiet?
[Student, mhux intelliġibbli] >> Yeah.
Okay, hekk fil-aħħar bit -
I raden funzjoni waħda ta 'malajr u faċli li nistgħu nagħmlu huwa,
let's - flimkien, I raden, tipprova u jiktbu fiha funzjoni
li ma care jekk huwa siġra tfittxija binarja.
Dan fih il-funzjoni għandha tirritorna vera
jekk kullimkien fl din is-siġra binarju ġenerali huwa l-valur li aħna qed tfittex.
Mela ejja 1 tagħmel dan recursively u mbagħad aħna ser tagħmel dan iteratively.
Nistgħu attwalment biss tagħmel dan flimkien, għaliex dan se tkun verament qasir.
>> X'inhu każ bażiku tiegħi se tkun?
[Student, mhux intelliġibbli]
[Bowden] Mela jekk (== NULL siġra), imbagħad dak?
[Student] Ritorn falza.
[Bowden] Inkella, ukoll, I m'għandhomx bżonn l-ieħor.
Jekk kien każ tiegħi bażi oħra.
Valur [Student] Tree s? >> Yeah.
Mela jekk (valur == siġra> valur.
Avviż aħna qed lura għall * node, mhux node ** i?
Ma fiha qatt se jkollhom bżonn jużaw xi ** node,
peress li aħna ma timmodifika pointers.
Aħna biss jaqsmu magħhom.
Jekk dan iseħħ, allura aħna rridu li jirritornaw veru.
Else irridu li travers-tfal.
Allura ma nistgħux raġuni dwar jekk kollox lejn ix-xellug huwa inqas
u kollox lejn il-lemin huwa akbar.
Allura x'inhu kondizzjoni tagħna se jkun hawn - jew, liema huma aħna se jagħmlu?
[Student, mhux intelliġibbli] >> Yeah.
Ritorn fih (valur, siġra-> xellug)
jew fiha (valur, siġra-> lemin). U li dan.
U l-avviż li hemm xi evalwazzjoni ta 'ċirkwit qasir,
fejn jekk aħna jiġri li jsibu l-valur fil-siġra xellug,
aħna qatt bżonn li nħarsu lejn l-siġra dritt.
Dik hija l-funzjoni sħiħa.
Issa ejja tagħmel dan iteratively,
li se tkun anqas sbieħ.
Aħna ser tieħu l-bidu tas-soltu ta node * kur = siġra.
Filwaqt li (kur! = NULL).
Malajr se tara problema.
Jekk kur - hawn, jekk aħna qatt break out ta 'dan,
allura konna jispiċċaw ta 'affarijiet li tħares lejn, hekk ritorn foloz.
Jekk (kur-> valur == valur), jirritorna veru.
Allura issa, aħna f'post -
ma nafux jekk irridu li jmorru lemin jew xellug.
Allura arbitrarju, ejja biss jmorru xellug.
Stajt ovvjament run fis kwistjoni fejn stajt kompletament abbandunat kollox -
I se biss qatt jiċċekkja fuq ix-xellug ta 'siġra.
I qatt se jiċċekkja xi ħaġa li huwa tifel dritt ta 'xejn.
Kif nista jiffissaw dan?
[Student] Int għandek iżżomm kont ta 'ix-xellug u tal-lemin fil-munzell.
[Bowden] Yeah. Mela ejja jagħmilha
Struct lista, node * n, u mbagħad node ** jmiss?
Naħseb li xogħlijiet multa.
Aħna rridu li jmorru fuq ix-xellug, jew let's - up here.
= Struct lista lista, li ser tibda
fil din il-lista Struct.
* Lista = NULL. Allura li għaddej biex tkun lista linked tagħna
ta subtrees li għandna skipped fuq.
Aħna ser travers xellug issa,
iżda peress li aħna inevitabbilment bżonn li jiġu lura lejn il-lemin,
Aħna ser iżżomm il-lemin ta 'ġewwa tal-lista Struct tagħna.
Imbagħad aħna ser ikollhom new_list jew Struct,
Struct lista *, new_list = malloc (sizeof (lista)).
Jien ser jinjoraw żbalji kkontrollat ​​li, iżda inti għandek tikkontrolla biex tara jekk huwa null.
New_list-node li għaddej għall-punt li -
oh, hu għalhekk li jien ridt it up here. Huwa ser jiġi ma 'lista Struct 2.
Thats kemm marbuta listi tax-xogħol.
Dan huwa l-istess bħala lista int marbut
ħlief aħna qed biss tissostitwixxi int ma * node.
Huwa eżattament l-istess.
Allura new_list, il-valur tal-node new_list tagħna,
se tkun kur->-dritt.
Il-valur ta 'tagħna new_list-> jmiss se tkun lista oriġinali tagħna,
u allura aħna qed tmur biex taġġorna lista tagħna għall-punt li new_list.
>> Issa għandna bżonn xi tip ta 'mod ta' affarijiet ġbid,
bħal aħna għandna traversat l subtree xellug kollu.
Issa għandna bżonn biex tiġbed Jittieħed barra minnu,
bħal kur huwa null; aħna ma jridux biss jirritornaw falza.
Aħna rridu li issa jiġbdu barra mill-lista l-ġdida tagħna.
A mod konvenjenti ta 'kif isir dan - ukoll, fil-fatt, hemm diversi modi ta' kif isir dan.
Kull min ikollu suġġeriment?
Fejn I għandha tagħmel dan jew kif I għandhom jagħmlu dan?
Aħna biss ftit minuti, imma xi suġġerimenti?
Minflok - mod wieħed, minflok il-kundizzjoni tagħna qed waqt,
dak li aħna bħalissa qed tħares lejn mhux null,
minflok aħna qed tmur biex tkompli tmur sakemm lista tagħna nnifisha hija nulla.
Mela jekk lista tagħna jispiċċa jkun null,
allura għandna jispiċċaw ta 'affarijiet biex tfittex, tfittex fuq.
Iżda dan ifisser li l-ewwel ħaġa fil-lista tagħna huwa biss se tkun l-node ewwel.
L-ewwel ħaġa se jkun - aħna m'għadx bżonn biex tara dak.
Allura lista-> n se jkun siġra tagħna.
lista-> jmiss se tkun nulla.
U issa filwaqt lista ma null ugwali.
Kur se jiġbdu xi ħaġa mill-lista tagħna.
Allura kur se ugwali lista-> n.
U mbagħad lista se ugwali lista '> n, jew lista'>. Li jmiss
Mela valur kur jekk ugwali valur.
Issa nistgħu żid kemm pointer dritt tagħna u pointer xellug tagħna
sakemm dawn mhux qed null.
Down hawn, I raden għandna għamlu li fl-ewwel post.
Jekk (kur->-tajjeb! = NULL)
allura aħna ser daħħal dik node fil-lista tagħna.
Jekk (kur-> xellug), din hija xi ftit ta 'xogħol żejjed, iżda huwa multa.
Jekk (kur-> xellug! = NULL),
u aħna qed tmur biex daħħal ix-xellug fil-lista marbuta tagħna,
u li għandhom ikunu fiha.
Aħna jtenni - sakemm aħna għandna xi ħaġa fil-lista tagħna,
għandna ieħor node li tħares lejn.
Allura aħna nħarsu lejn dak node,
aħna bil-quddiem lista tagħna għal dak li jmiss.
Jekk dan node huwa l-valur li aħna qed tfittex, nistgħu ritorn vera.
Else daħħal kemm subtrees xellug u lemin tagħna,
sakemm dawn mhux qed null, fil-lista tagħna
sabiex inkunu inevitabbilment jmorru fuqhom.
Mela jekk dawn ma kinux null,
jekk pointer għeruq tagħna rrimarka żewġ affarijiet,
allura fl-ewwel aħna jinġibed xi ħaġa hekk lista tagħna jispiċċa jkun null.
U allura aħna mressqa żewġ affarijiet lura, hekk issa lista tagħna huwa ta 'daqs 2.
Imbagħad aħna qed tmur biex loop back-up u aħna qed biss jmorru biex tiġbed,
ejja ngħidu, il-pointer xellug tal node għerq tagħna.
U li ser biss iżommu jiġri; aħna ser jispiċċaw looping fuq kollox.
>> Avviż li dan kien ferm aktar ikkumplikat
fis-soluzzjoni rikursivi.
U stajt qal diversi drabi
li s-soluzzjoni rikursivi normalment għandha ħafna in komuni mal-iterattiv soluzzjoni.
Hawn dan huwa eżattament dak li l-soluzzjoni rikursivi qed tagħmel.
L-unika bidla hi li minflok impliċitament jużaw il-munzell, il-munzell programm,
bħala mod tiegħek ta 'iżżomm rekord ta' dak li għoqiedi inti xorta jkollok bżonn biex iżuru,
issa għandek biex espliċitament tuża lista marbuta.
Fiż-żewġ każijiet, inti qed iżommu rekord ta 'dak node għad irid jiġu viżitati.
Fil-każ rikursivi huwa biss aktar faċli għaliex munzell
hija implimentata għalik bħala l-munzell programm.
Avviż li din il-lista marbuta, huwa munzell.
Tkun xi tkun aħna biss jitqiegħed fuq il-munzell
huwa immedjatament dak li aħna qed tmur biex pull off-munzell li jżuru jmiss.
Aħna tardiv, iżda xi mistoqsijiet?
[Student, mhux intelliġibbli]
[Bowden] Yeah. Mela jekk ikollna lista linked tagħna,
attwali se punt għal dan Guy,
u issa aħna qed biss avvanz lista linked tagħna li tiffoka fuq dan Guy.
Aħna qed jaqsmu fuq il-lista marbut f'dik il-linja.
U allura I raden għandna ħielsa lista linked tagħna u l-għalf
darba qabel jirritornaw vera jew falza, għandna bżonn li
jtenni fuq lista marbuta tagħna u dejjem stabbiliti hawn, I raden,
jekk aħna cur dritt ma jkunx ugwali għal, żid dan, hekk issa irridu ħielsa
kur għaliex, ukoll, aħna ma kompletament tinsa dwar il-lista? Yeah.
Allura dak hu li rridu nagħmlu hawnhekk.
Fejn hi l-pointer?
Kur kien imbagħad - irridu li lista Struct * 10 ugwali lista li jmiss.
Lista Ħieles, lista = temperatura.
U fil-każ fejn nerġgħu lura minnu, aħna ma bżonn li jtenni
tul il-bqija tal-lista linked tagħna ħelsien affarijiet.
Il-ħaġa sbieħ dwar is-soluzzjoni rikursivi hi ħelsien affarijiet
ifisser biss factorings popping barra mill-munzell li se jiġri għalik.
Allura aħna ħadthom marret minn xi ħaġa li huwa simili 3 linji ta 'hard-to-think-kodiċi dwar
għal xi ħaġa li hija sinifikament aktar ħafna hard-to-think-dwar linji ta 'kodiċi.
Kwalunkwe aktar mistoqsijiet?
Kull dritt. Aħna qed tajba. Bye!
[CS50.TV]