SPEAKER 1: Id-dritt, għalhekk dan huwa CS50 Dan huwa l-aħħar ta 'ħames ġimgħa. U tfakkar li aħħar darba aħna bdiet tħares lejn l-informazzjoni fancier strutturi li bdew isolvu problemi, li bdew jintroduċu problemi ġodda, iżda l-muftieħ għal dan kien il-tip ta 'kamini li aħna bdew jagħmlu minn node biex node. Allura dan il-kors huwa lista marbuta weħidhom. U billi marbut waħdu, I jfisser hemm biss wieħed ħajt bejn kull ta'dawk il-lymph. Jirriżulta li tista 'tagħmel fancier affarijiet simili listi marbuta doppjament fejn inti għandek vleġġa għaddejjin fiż-żewġ direzzjonijiet, li jistgħu jgħinu ma 'ċerti effiċjenzi. Iżda din solvuta l-problema? Liema problema ma dan issolvi? Għaliex ma aħna kura nhar it-Tnejn? Għaliex, fit-teorija, ma aħna kura nhar it-Tnejn? X'tikkontrolla do? 

UDJENZA: Nistgħu dinamiku resize. 

SPEAKER 1: OK, sabiex inkunu nistgħu dinamiku resize. Prosit tnejn inti. Allura inti tista 'dinamikament resize dan istruttura tad-data, filwaqt firxa, irtirar, inti għandek tkun taf priori kemm l-ispazju trid u jekk għandek bżonn ta 'aktar ftit ispazju, int tip ta 'minn xortih. Inti għandek toħloq firxa sħiħa ġdida. Int għandek timxi kollha ta 'tiegħek data minn waħda għall-oħra, eventwalment ħielsa l-firxa qodma jekk inti tista ', u mbagħad jipproċedi. Li biss iħoss jiswew ħafna u ħafna ineffiċjenti, u tabilħaqq jista 'jkun. Iżda dan mhux kollox tajjeb. Qed inħallsu prezz, dak li kien wieħed tal-prezzijiet aktar ovvji aħna tħallas permezz tintuża lista marbut? 

UDJENZA: Irridu użu ispazju doppja għal kull wieħed. SPEAKER 1: Yeah, għalhekk għandna bżonn mill-inqas darbtejn ħafna spazju. Fil-fatt, I realizzati din l-istampa ta anki ftit qarrieqa, minħabba fuq IDE CS50 fil-lott ta 'moderna kompjuters, pointer jew indirizz mhuwiex fil-fatt erba 'bytes. Huwa ħafna drabi dawn jiem tmien bytes, li tfisser il-qiegħ l-aktar rettangoli hemm fir-realtà huma tip ta 'darbtejn kbar kif dak li stajt mfassla, li jfisser li inti qed tuża tliet darbiet spazju kemm aħna jista 'jkollha mod ieħor. Issa fl-istess ħin, aħna qed xorta jitkellem bytes, id-dritt? Aħna qed mhux neċessarjament jitkellem megabytes jew gigabytes, sakemm din id-data istrutturi tikseb big. 

U hekk illum aħna jibdew jikkunsidraw kif nistgħu tesplora data b'mod aktar effiċjenti jekk fatt l-informazzjoni tkompli tikber. Imma ejja jippruvaw canonicalize l-ewwel operazzjonijiet li inti tista 'tagħmel fuq dawn tipi ta 'strutturi ta' dejta. Allura xi ħaġa bħal marbut Lista ġeneralment jappoġġja operazzjonijiet simili tħassar, daħħal, u tfittxija. U dak li għandi jfisser minn dak? Li sempliċiment ifisser li s-soltu, jekk in-nies qed jużaw lista marbuta, dawn jew xi ħadd ieħor ħa implimentat funzjonijiet bħall tħassar, daħħal, u tfittxija, sabiex inti tista ' fil-fatt jagħmlu xi ħaġa utli ma 'l-istruttura tad-data. Mela ejja tagħti ħarsa lejn kif nistgħu jimplimentaw xi kodiċi għall lista marbut kif ġej. 

Allura dan huwa biss xi kodiċi C, lanqas programm sħiħ li jien verament malajr bit-tarjola up. Mhuwiex online fid-distribuzzjoni kodiċi, minħabba li mhux se tmexxi effettivament. Imma avviż stajt biss ma kumment qal, dot dot dot, hemm xi ħaġa hemm, dot dot dot, xi ħaġa hemmhekk. U ejja biss ħarsa lejn dak li l-partijiet mmerraq huma. Allura fuq il-linja tlieta, ifakkar li issa dan huwa aħna pproponiet li tiddikjara node aħħar ħin, wieħed minn dawk l-oġġetti rettangolari. Hija għandha int li aħna ser sejħa N, imma nistgħu sejħa hija xi ħaġa, u mbagħad stilla node Struct imsejħa jmiss. U biss li jkun ċar, li t-tieni linja, fuq il-linja sitt, dak li huwa dan? X'inhu tagħmel għalina? Minħabba li ċertament jistenna aktar cryptic minn varjabbli tas-soltu tagħna. 

UDJENZA: Dan jagħmilha jimxu wieħed. 

SPEAKER 1: Dan jagħmilha aktar jimxu wieħed. U biex ikunu aktar preċiżi, se taħżen l-indirizz tal-node li kien ifisser li jkun semantikament li jmiss lilu, id-dritt? Allura huwa mhux ser neċessarjament jimxu xejn. Huwa biss se jaħżnu valur, li huwa se tkun l-indirizz ta 'xi node oħra, u hu għalhekk li konna qal Istituzzjonjijiet star node, l-istilla li turi pointer jew indirizz. OK, hekk issa jekk għandek tassumi li għandna din N disponibbli għalina, u ejja jassumi li xi ħadd ieħor ħa mdaħħal mazz sħiħ ta 'numri interi fi lista marbuta. U dik il-lista marbuta hija indikat minn xi punt a imsejjaħ lista varjabbli li l- għadda fil hawn bħala parametru, kif nista tmur dwar linja 14 implimentazzjoni engine? Fi kliem ieħor, jekk I am implimentazzjoni funzjoni li l-għan fil-ħajja huwa li jieħdu int u allura l- bidu ta 'lista marbuta, li huwa pointer għal-lista marbuta. Bħal ewwel, li naħseb David kien voluntier tagħna nhar it-Tnejn, kien tipponta lejn il-lista sħiħa marbuta, huwa kif jekk aħna qed tgħaddi David fil bħala argument tagħna hawn. Kif do we go dwar traversat din il-lista? Ukoll, jirriżulta li għalkemm pointers huma relattivament ġodda issa lilna, nistgħu nagħmlu dan relattivament jinftiehem. 

Jien ser jimxi 'l quddiem u tiddikjara varjabbli temporanju li b'konvenzjoni huwa biss se li se jkun jismu pointer, jew PTR, imma int tista 'sejħa hija xi ħaġa li trid. U jien ser initialize dan il-bidu tal-lista. Allura inti tista 'tip ta think ta' dan kif me l-għalliem l-oħra jum, tip ta 'tipponta lejn xi ħadd fost il-bnedmin tagħna bħala voluntiera. Hekk jien varjabbli temporanju li l- biss tipponta fl-istess ħaġa li tagħna inzerta jismu voluntier David kien ukoll fakkret. Issa filwaqt pointer huwa mhux null, minħabba recall li null hija xi valur sentinella speċjali l tiddemarka l-aħħar tal-lista, so filwaqt Jien ma tipponta lejn il- art bħal aħħar voluntier tagħna kien, ejja imorru quddiem u jagħmel dan li ġej. Jekk Pointer u issa I tip ta 'tixtieq biex jagħmlu dak li għamilna mal-istudent structure-- jekk pointer dot li jmiss equals-- pjuttost, jekk pointer dot N ugwali huwa daqs il-varjabbli N, il- argument li kien għadda fi, imbagħad Irrid immur quddiem u jgħidu ritorn vera. I sabu l-għadd N ġewwa ta ' wieħed mill-lymph tal-lista marbuta tiegħi. Iżda l-dot m'għadhomx xogħlijiet f'dan il-kuntest, minħabba pointer, PTR, huwa tabilħaqq pointer, indirizz, aħna attwalment jistgħu wonderfully użu fl-aħħar biċċa ta 'sintassi dak it-tip ta 'jagħmel sens intuwittivi u fil-fatt użu vleġġa hawn, li jfisser jmorru minn li tindirizza lill-eqreb numru sħiħ hemmhekk in. Allura huwa simili ħafna fl ispirtu lill-operatur dot, iżda minħabba pointer mhix pointer u mhux Struct innifisha, aħna biss jużaw il-vleġġa. 

Allura jekk il-node attwali li I, l varjabbli temporanju, am tipponta lejn mhux N, dak li nixtieq do? Ukoll, ma 'voluntiera umani tiegħi li kellna hawn l-oħra jum, jekk l-ewwel bniedem tiegħi ma jkunx dak I trid, u forsi t-tieni umana mhix l-waħda li nixtieq, u t-tielet, I bżonn li jżommu fiżikament jiċċaqalqu. Bħal kif nista pass permezz ta 'lista? Meta kellna firxa, inti biss ma simili I plus plus. Iżda f'dan il-każ, huwa biżżejjed li do pointer, gets, pointer, li jmiss. Fi kliem ieħor, il-qasam li jmiss huwa bħall kollha tal-idejn xellug li l-voluntiera umani tagħna nhar it-Tnejn kienu qed jużaw punt f'xi node ieħor. Dawk kienu ġirien tagħhom li jmiss. 

Mela jekk jien tixtieq li pass permezz din il-lista, I ma tista 'biss tagħmel I plus plus aktar, I minflok ngħid I, pointer, va daqs il x'ikun il-qasam li jmiss, qasam jmiss huwa,-qasam li jmiss, wara kollha ta 'dawk l-idejn xellug li kellna fuq tipponta istadju għal xi valuri sussegwenti. U jekk niġi permezz li iterazzjoni kollu, u finalment, I hit null li ma jkollhomx misjuba N għadhom, I biss ritorn foloz. Għalhekk għal darb'oħra, dak kollu li aħna qed tagħmel hawn, kif fis-istampa mument ilu, qed jibda mill tipponta lejn l- bidu tal-lista preżumibbilment. U mbagħad I kontroll, huwa l-valur I infittex ugwali għal disa? Jekk iva, I ritorn vera u jien jsir. Jekk le, I taġġorna naħa tiegħi, AKA pointer, punt fil-post tal-vleġġa li jmiss, u imbagħad lokazzjoni il-vleġġa li jmiss, u dak li jmiss. Jien sempliċiment mixi permezz ta 'dan array. 

Għalhekk għal darb'oħra, quién? Bħal dak li huwa dan ingredjent għall? Ukoll, ifakkar li daħħalna il-kunċett ta 'ċumnija, li hija data astratta tip sakemm huwa mhux xi ħaġa C, mhuwiex xi ħaġa CS50, huwa ta 'idea astratta, din l-idea ta' stivar affarijiet fuq quċċata ta 'xulxin li jistgħu jiġu implimentati għenieqed ta 'modi differenti. U mod wieħed aħna propost kien ma firxa, jew ma 'lista marbuta. U jirriżulta li kanonikament, a munzell jappoġġja mill-inqas żewġ operazzjonijiet. U l-kliem buzz huma timbotta, biex imbotta xi ħaġa fuq il-munzell, bħal trej ġdid fil- dining sala, jew pop, li jfisser li tneħħi l-topmost trej mill-munzell fil-dining sala, u mbagħad forsi xi operazzjonijiet oħrajn ukoll. Allura kif tista 'niddefinixxu l-istruttura li aħna issa qed ssejjaħ munzell? 

Well, aħna għandna kollha tal-meħtieġa sintassi għad-dispożizzjoni tagħna fil C. I say, tagħti me definizzjoni tip ta ' a Struct ġewwa ta 'ċumnija, Jien se ngħid huwa firxa, ta ' mazz sħiħ ta 'numri u mbagħad daqs. Allura fi kliem ieħor, jekk irrid biex jimplimentaw dan il-kodiċi, let me go u biss tip ta ' jiġbed dak li dan huwa qal. Allura dan huwa qal, tagħti me a struttura li ltqajna firxa, u jien ma nafx f'liema kapaċità hija, huwa apparentement xi kostanti li stajt definiti x'imkien ieħor, u li l-multa. Iżda jissoponi huwa biss wieħed, tnejn, tlieta, erba ', ħames. Allura kapaċità hija 5. Dan l-element ġewwa tal tiegħi istruttura se tissejjaħ numri. U mbagħad I bżonn wieħed varjabbli oħra apparentement imsejħa daqs li inizjalment jien ser li jkun stipulat huwa initialized għal żero. Jekk hemm xejn fil l-munzell, id-daqs huwa żero, u huwa l-valuri taż-żibel fin-numru. Għandi l-ebda idea x'inhu fil hemm għadha biss. 

Mela jekk jien tixtieq li timbotta xi ħaġa fuq il-munzell, suppose I call il-buttuna funzjoni, u I say push 50, bħan-numru 50, fejn tipproponi I tiġbed f'dan array? Hemm ħames tweġibiet differenti possibbli. Fejn tridu li timbotta l-għadd 50? Jekk l-għan hawnhekk, għal darb'oħra, sejħa tal- push funzjoni, jgħaddu fi argument ta '50, fejn ma nressaq dan? Ta 'ħames possible-- 20% ċans ta guessing korrett. Iva? 

UDJENZA: Far dritt. 

SPEAKER 1: Far dritt. Issa hemm ċans 25% ta guessing korrett. Allura li fil-fatt tkun multa. B'konvenzjoni, I ser jgħidu ma 'firxa, aħna ġeneralment tibda fil-xellug, iżda nistgħu ċertament tibda fil-lemin. Allura l-spoiler hawn ikunu jien probabbilment se tiġbed fuq ix-xellug, bħad fil-firxa normali fejn I tibda tmur xellug għal-lemin. Imma jekk inti tista 'flip l-aritmetika, multa. Huwa biss mhux konvenzjonali. OK, I bżonn tagħmel waħda bidla aktar għalkemm. Issa li stajt imbuttat xi ħaġa fuq il-munzell, xi jmiss? 

Kull dritt, ikolli inkrement-daqs. So let me jimxi 'l quddiem u biss jaġġornaw dan, li kien żero. U minflok issa, jien ser li jitqiegħdu fil-valur waħda. U issa suppose I push ieħor Numru fuq il-munzell, bħal 51. Well, I jkollhom jagħmlu waħda aktar bidla, li jkun sa l-daqs tnejn. U allura suppose I push waħda aktar Numru fuq il-munzell bħal 61, issa I bżonn jaġġornaw id-daqs wieħed aktar ħin, u jiksbu l-valur 3 skond il-qies. U issa jissoponi I call pop. Issa pop, b'konvenzjoni, ma jieħdu argument. Bil-munzell, il-sħiħ punt tal-metafora trej hija li inti ma għandekx diskrezzjoni mur jiksbu dak trej, inti kollha tista 'tagħmel huwa pop l topmost wieħed mill l-munzell, sempliċement minħabba. Dak hu li din l-istruttura tad-data ma. 

Allura billi li l-loġika jekk I jgħidu pop, dak li jiġi off? Allura 61. Allura dak li verament huwa l-kompjuter se jagħmlu fil-memorja? Xi jfisser kodiċi tiegħi għandek tagħmel? What would you tipproponi nagħmlu l-bidla fuq l-iskrin? X'għandu jinbidel? Jiddispjacini? Allura aħna jeħles 61. So I definittivament jistgħu jagħmlu dan. U nista 'jeħles 61. U allura dak l-oħra bidla jeħtieġ li jiġri? Daqs probabbilment irid imur lura għal tnejn. U hekk li l-multa. Iżda stenna minuta, daqs mument ilu kien tlieta. Ejja biss tagħmel verifika sanità malajr. Kif ma nafu li aħna riedu li teħles minn 61? Għaliex aħna qed popping. U so I jkollhom din it-tieni daqs proprjetà. 

Stenna minuta, jien ħsieb lura għall ġimgħatejn meta bdejna nitkellmu dwar arrays, fejn dan kien post żero, din kienet f'post wieħed, dan kien post tnejn, dan huwa post tlieta, erba, jidher qisu l- relazzjoni bejn id-daqs u l-element li nixtieq li jitneħħew mill-firxa jidher li jkun biss dak? Daqs minus wieħed. U hekk li kif bħala bnedmin nafu 61 jiġi l-ewwel. Kif jgħid il-kompjuter ser tkun taf? Meta kodiċi tiegħek, fejn inti probabilment trid tagħmel wieħed nieqes daqs, hekk tlieta nieqes wieħed hu ta 'tnejn, u li ifisser irridu li teħles minn 61. U allura nistgħu tabilħaqq taġġorna id-daqs hekk li d-daqs issa jmur minn tlieta sa tnejn biss. U biss sabiex ikunu pedantic, jien ser biex jipproponi li jien jsir, right? You propost intuwittivament korrett I għandhom jeħles 61. Imma ma jkunux I tip ta ' tip ta 'gotten rid ta '61? Stajt effettiv minsija li huwa attwalment hemm. U jaħsbu lura għal PSET4, jekk inti stajt taqra l-artiklu dwar forensika, il-PDF li kellna inti guys taqra, jew inti se jaqra din il-ġimgħa għall PSET4. Ifakkar li dan huwa effettivament germane li l-idea kollha tal-forensiċi kompjuter. What a kompjuter ġeneralment ma huwa hija biss jinsa fejn xi ħaġa, iżda ma jmorru fi u simili jippruvaw li tobrox it out jew override dawk bits biż-żeri u dawk jew xi mudell każwali ieħor sakemm inti stess tagħmel hekk deliberatament. Allura intwizzjoni tiegħek kienet dritt, ejja jeħles 61. Iżda fir-realtà, aħna ma għandekx li jolqot. Jinħtieġ li ninsew li huwa hemmhekk billi jinbidlu daqs tagħna. 

Issa hemm problema ma 'dan munzell. Jekk I iżommu imbuttar affarijiet fuq il-munzell, x'hemm ovvjament jiġri fi ftit ftit żmien mumenti? Aħna qed tmur biex jispiċċaw l-ispazju. U dak li nagħmlu? Aħna tip ta 'invitat. Din l-implimentazzjoni ma jħallux us resize l-array, għaliex bl-użu dan sintassi, jekk inti think lura għal ġimgħatejn, ladarba inti ħadthom iddikjarat id-daqs ta 'firxa, ma rajniex mekkaniżmu għadu fejn tista 'tbiddel id-daqs tal-array. U tabilħaqq C ma jkollux din il-karatteristika. Jekk inti tgħidli tagħti me ħames Nths, jsejħulhom numri, li kollox int ser ġġibu. Allura nagħmlu issa bħala tat-Tnejn, ikollhom l-abbiltà li jesprimu soluzzjoni għalkemm, aħna biss bżonn tweak id-definizzjoni ta 'munzell tagħna li ma jkun hemm xi firxa hard-kodifikati, iżda biss biex jaħżnu l-indirizz. 

Issa għaliex huwa dan? Issa aħna biss għandhom tkun komda ma il-fatt li meta programm tiegħi runs, Jien preżumibbilment se għandek titlob il-bniedem, kemm numri tridu taħżen? Allura l-input trid tiġi minn x'imkien. Imma ladarba naf li numru, allura nista 'biss użu dak jiffunzjonaw biex jagħtu me blokki ta 'memorja? I jistgħu jużaw malloc. U nista 'ngħid xi numru ta' bytes Irrid lura għal dawn Nths. U kollha jien li jaħżen fil-numri varjabbli hawn ġewwa ta 'dan Struct għandu jkun dak? X'inhu dak li attwalment tmur fil- numri f'dan ix-xenarju? Yeah, pointer għall-ewwel byte ta 'dak blokki ta' memorja, jew b'mod aktar speċifiku,-indirizz ta 'l-ewwel minn dawn bytes. Ma jimpurtax jekk huwa wieħed byte jew biljun bytes, I biss ħtieġa li jimpurtak mill-ewwel. Għaliex dak garanziji malloc u tiegħi garanziji sistema operattiva, huwa li l-blokki ta 'memorja I nikseb, li għaddej biex jkun kontigwu. Hemm mhux ser tkun nuqqasijiet. Mela jekk stajt talab għal 50 bytes jew 1,000 bytes, dawn qed kollha ser ikunu lura lura lura. U sakemm I remember kif big, kif ħafna I talab għal, kull I bżonn tkun taf hija l-ewwel indirizz tali. 

Allura issa għandna l-ħila fil-kodiċi. Għalkemm, li għaddej biex tieħu us aktar ħin biex jikteb dan up, aħna issa tista 'talloka mill-ġdid li l-memorja billi biss ħażna f'indirizz differenti hemmhekk jekk irridu akbar jew saħansitra blokki iżgħar ta 'memorja. Allura hawnhekk għal off-kummerċ. Issa irridu jiksbu dinamiżmu. Għad għandna contiguousness Jien titlob. Minħabba malloc se tagħtina blokki kontigwi ta 'memorja. Iżda dan se jkunu uġigħ fl l-għonq għalina, il-programmer, li attwalment kodiċi up. Huwa biss aktar xogħol. Għandna bżonn kodiċi simili għal dak I kien banging out ftit mument ilu. Doable ħafna, iżda żżid kumplessità. U hekk time iżviluppatur, programmer ħin għadu riżorsa ieħor li nistgħu bżonn li jonfqu xi żmien biex tikseb karatteristiċi ġodda. U allura naturalment hemm kju. Aħna mhux se jmorru fis dan wieħed b'reqqa. Imma hija simili ħafna fl-ispirtu. I jista 'jimplimenta kju, u operazzjonijiet korrispondenti tagħha, enqueue jew dequeue, bħal iżżid jew tneħħi, huwa biss mod fancier ta 'tgħid dan, enqueue jew dequeue, kif ġej. I tista 'biss jagħtu lili nnifsi Istituzzjonjijiet li għal darb'oħra għandu firxa numru, il li għal darb'oħra għandu daqs, iżda għaliex għandi issa jeħtieġ li jżommu rekord ta 'quddiem tal-kju? I ma kellhomx bżonn tkun taf quddiem tal munzell tiegħi. Ukoll, jekk I darb'oħra għal queue-- ejja biss hard kodiċi bħala li bħall ħamsa interi fil hawn potenzjalment. Allura dan huwa żero, wieħed, tnejn, tlieta, erbgħa. Dan se jkun imsejħa numri mill-ġdid. U dan se tissejjaħ daqs. 

Għaliex huwa mhux biżżejjed li għadek daqs? Well, ejja timbotta dawn l-istess numri fuq. So I pushed-- I enqueued, jew imbuttat. Now I ser enqueue 50, u mbagħad 51, u mbagħad 61, u dot dot dot. Allura dak enqueue. I enqueued 50, imbagħad 51, imbagħad 61. U li tidher identika li munzell s'issa, ħlief I do għandek bżonn tagħmel bidla waħda. I bżonn jaġġornaw dan id-daqs, so I go minn żero għal wieħed li 2-3 issa. Kif nista dequeue? X'jiġri ma 'dequeue? Min għandu come off din il-lista l-ewwel jekk huwa l-linja fil-Apple Aħżen? Allura 50. Allura huwa tip ta delikati dan iż-żmien. Billi aħħar darba li kien super faċli biex biss tagħmel wieħed nieqes daqs, I nikseb l-aħħar tal-firxa tiegħi b'mod effettiv fejn in-numri huma, tneħħi 61. Imma jien ma jridux li jitneħħew 61. I tixtieq li tieħu 50, li kien hemm fil 05:00 għal-linja up għall- iPhone jew whatnot ġdid. U dan biex jeħles ta '50, I tista 'mhux biss tagħmel dan, id-dritt? I jistgħu jaqsmu l-50. Iżda aħna biss qal aħna ma għandhom ikunu tant anali kif li tobrox jew jaħbu l-informazzjoni. Nistgħu biss tinsa fejn hu. 

Imma jekk jien tibdil fid-daqs tiegħi issa biex tnejn, huwa dan it-tagħrif biżżejjed li tkun taf x'inhu għaddej fil-kju tiegħi? Mhux ezatt. Bħal daqs tiegħi huwa tnejn, iżda fejn ma l-kju jibda, speċjalment jekk I għad għandhom dawn l-istess numri fil-memorja. 50, 51, 61. So I bżonn li wieħed jiftakar issa fejn il-quddiem hu. U hekk kif ipproponejt up hemm, aħna ser għadek imsejħa Quddiem nth, li inizzjali valur kellu jkun dak? Żero, biss il-bidu tal-lista. Imma issa minbarra decrementing id-daqs, aħna biss inkrement quddiem. Issa hawn problema oħra. Allura ladarba I jibqgħu għaddejjin. Ejja ngħidu dan huwa n-numru ta ' bħal 121, 124, u mbagħad, dammit, Jien l-ispazju. Iżda stenna minuta, jien ma. Allura f'dan il-punt fl-istorja, jissoponi li d-daqs huwa wieħed, tnejn, tlieta, erba ', sabiex jissoponi li l- daqs huwa erba, il-quddiem huwa wieħed, hekk 51 ikun fuq quddiem. I tixtieq li tqiegħed numru ieħor hawnhekk, iżda, dammit, jien l-ispazju. Imma jien ma verament, right? Fejn jista I jqajjem xi valur addizzjonali, bħal 171? Yeah, I jistgħu biss tip ta ' jmorru lura hemmhekk, id-dritt? U mbagħad jaqsmu l-50, jew biss jissostitwixxu bl 171. U jekk int mintix għaliex numri tagħna ltqajna hekk każwali, dawn huma komunement jittieħdu kompjuter korsijiet tax-xjenza fil-Harvard wara CS50. Iżda dan kien ottimizzazzjoni tajba, għaliex issa jien ma ħela ispazju. I still għandek tiftakar kemm hu kbir dan il-ħaġa hija totali. Huwa ħamsa totali. Minħabba I ma jridux tibda kitba fuq 51. Allura issa I am għadhom barra mill-ispazju, hekk l-istess problema bħal qabel. Iżda int tista 'tara kif issa fil-kodiċi tiegħek, inti probabilment jkollhom jiktbu ftit aktar kumplessità li naraw li dan iseħħ. U fil-fatt, dak operatur fis-C probabbilment tikri inti magically tagħmel dan il-ċirkolarità? Yeah l-operatur modulo, is-sinjal fil-mija. Allura x'inhu l-tip ta 'kessaħ dwar kju, anke jekk inżommu tpinġija arrays kif dawn il-linji dritti simili, jekk inti tip ta 'jaħsbu dwar dan bħala b'tidwira madwar bħala ċirku, allura biss intuwittivament dan it-tip ta jaħdem mentalment I think ftit aktar nadif. Inti xorta jkollhom jimplimentaw dan il-mudell mentali fil-kodiċi. Allura mhux li iebes, finalment, biex jimplimentaw, imma aħna xorta jitilfu l-size-- pjuttost, il- abbiltà li resize, sakemm nagħmlu dan. 

Għandna biex jeħles mill-firxa, aħna tibdilha ma 'pointer waħda, u mbagħad x'imkien fil-kodiċi tiegħi stajt ltqajna Sejħa dak jiffunzjonaw li attwalment joħolqu l-array imsejħa numri? Malloc, jew xi simili funzjoni, eżattament. Kwalunkwe mistoqsijiet dwar stacks jew kjuwijiet. Yeah? Tajba kwistjoni. What modulo would you tuża hawn. Allura ġenerali, meta jużaw mod, inti tagħmel dan mad-daqs tal- istruttura data sħiħa. Allura xi ħaġa simili ħamsa jew il-kapaċità, jekk huwa kostanti, huwa probabbilment involut. Iżda biss tagħmel modulo ħamsa probabbilment ma jkunx biżżejjed, għaliex għandna bżonn inkunu nafu għandna perimetrika hawn jew hawn jew hawn. Allura int probabilment wkoll tmur jridu jinvolvu id-daqs tal-ħaġa, jew il-varjabbli quddiem ukoll. Allura huwa biss dan relattivament espressjoni aritmetika sempliċi, iżda modulo tkun l-ingredjent ewlieni. 

Film tant qasir jekk inti se. Animazzjoni li xi folks fil università oħra jitqiegħdu flimkien li konna adattati għal din id-diskussjoni. Dan jinvolvi Jack tagħlim tal- fatti dwar kjuwijiet u stats. 

FILM: Darba waħda, kien hemm Guy msemmija Jack. Meta ġie biex jagħmlu ħbieb, Jack ma kellux knack. Allura Jack marru li tkellem lill- aktar popolari Guy kien jaf. Huwa mar Lou u staqsa, What do I do? Lou raw li l-ħabib tiegħu kien verament f'diffikultà. Ukoll, huwa beda, biss tfittex kif int dressed. Ma inti xi ħwejjeġ bil-ħarsa differenti? Iva, qal Jack. I żgur do. Come to my house u I ser juru lilhom lilek. Allura dawn marru off għall Jack. U Jack wera Lou-kaxxa fejn hu miżmum shirts kollha tiegħu, u pants tiegħu, u kalzetti tiegħu. Lou qal, I ara inti għandek ħwejjeġ kollha tiegħek fil-pile. Għaliex ma tilbes xi oħrajn darba awhile? 

Jack qal, ukoll, meta I neħħi ħwejjeġ u kalzetti, I aħsilhom u mqiegħda bogħod minnhom fil-kaxxa. Imbagħad jiġi l-li jmiss filgħodu, u sa I ħops. I tmur fil-kaxxa u jiksbu ħwejjeġ tiegħi off-quċċata. Lou rrealizzaw malajr il-problema ma Jack. Hu jinżamm ħwejjeġ, CD, u kotba fil-munzell. Meta huwa laħaq għal xi ħaġa li taqra jew li jilbsu, huwa d jagħżlu l-ktieb quċċata jew ħwejjeġ ta 'taħt. Imbagħad meta kien sar, huwa ipoġġiha dritt lura. Back dan imur, fuq nett tal-munzell. Naf li l-soluzzjoni, qal Loud trijonfanti. Għandek bżonn biex jitgħallmu biex tibda tuża kju. Lou ħa ħwejjeġ Jack u mdendla minnhom fil-closet. U meta huwa kien jitbattal l-kaxxa, hu biss tossed dan. 

Imbagħad qal, issa Jack, fl-aħħar tal il-jum, tpoġġi ħwejjeġ tiegħek fuq ix-xellug meta inti tpoġġi lilhom bogħod. Imbagħad għada filgħodu meta inti tara l-xemx, jiksbu ħwejjeġ tiegħek fuq il-lemin, mill-aħħar tal-linja. Ma tara? qal Lou. Se jkun hekk sbieħ. Int ser ikollok jilbsu kollox ladarba qabel tilbes xi ħaġa darbtejn. U ma 'kollox fil-kjuwijiet fil closet tiegħu u ixkaffa, Jack bdew iħossu pjuttost ċert ta lilu nnifsu. Grazzi għall Lou u kju isbaħ tiegħu. SPEAKER 1: Id-dritt, huwa adorable. Allura dak li ġie verament għaddejjin fuq minn taħt il-barnuża issa? Li għandna pointers, li għandna malloc, li aħna għandna l-kapaċità li joħolqu biċċiet ta 'memorja għalina dinamiku. Allura dan huwa stampa aħna glimpsed biss l-oħra jum. Aħna ma verament nitkellem fuqha, iżda din l-istampa ilu għaddej taħt il-barnuża għal ġimgħat issa. U għalhekk dan jirrappreżenta, just rettangolu li konna mfassla, memorja tal-kompjuter tiegħek. U forsi kompjuter tiegħek, jew CS50 ID, għandha gigabyte ta 'memorja jew RAM jew tnejn gigabytes jew erbgħa. Hija ma verament kwistjoni. Sistema operattiva tiegħek Windows jew Mac OS jew Linux, essenzjalment jippermetti program tiegħek biex jaħsbu li għandu aċċess għall-totalità tal memorja tal-kompjuter tiegħek, anki jekk inti tista 'tkun qed taħdem programmi multipli f'daqqa. Allura fir-realtà, li ma verament jaħdmu. Iżda huwa tip ta 'illużjoni mogħtija lill-programmi kollha tiegħek. Mela jekk kellek żewġ gigs ta 'RAM, dan huwa kif l-kompjuter tista 'taħseb minnha. 

Issa inzerta, waħda minn dawn affarijiet, wieħed minn dawn is-segmenti ta 'memorja, tissejjaħ munzell. U fil-fatt kwalunkwe ħin s'issa bil-miktub kodiċi li inti sejħu funzjoni, per eżempju prinċipali. Ifakkar li kull darba stajt memorja mfassla s kompjuter, Jien dejjem tiġbed tip ta ' nofs ta 'rettangolu hawn u ma jolqot jitkellem dwar x'hemm fuq. Għaliex meta prinċipali huwa msejjaħ, I jitolbu li inti tikseb dan sliver ta 'memorja li jinżel hawn. U jekk ewlenija imsejħa funzjoni bħal tpartit, sew swap tmur hawn. U jirriżulta, li l- fejn huwa jispiċċa. Fuq xi ħaġa imsejħa 'ċumnija ġewwa tal-memorja tal-kompjuter tiegħek. Issa fl-aħħar tal-ġurnata, dan huwa biss tindirizza. Huwa simili byte żero, byte wieħed, byte 2 biljuni. Imma jekk inti taħseb dwarha kif dan l-oġġett rettangolari, kollha li aħna qed tagħmel kull ħin nitolbu funzjoni hija saffi porzjon ġdid ta 'memorja. Aħna qed tagħti dik il-funzjoni porzjon tal-memorja tagħha stess biex jaħdmu ma '. 

U tfakkar issa li dan huwa importanti. Għaliex jekk aħna għandna xi ħaġa bħal tpartit u żewġ varjabbli lokali bħall A u B u nagħmlu l-bidla dawk il-valuri minn wieħed u tnejn għal żewġ u wieħed, irtirar li meta swap jirritorna, huwa bħallikieku dan porzjon tal-memorja huwa biss marret. Fir-realtà, huwa għadu hemm forensically. U xi ħaġa għadu attwalment hemm. Iżda kunċettwali, huwa daqs li għalkemm huwa kompletament marret. U hekk prinċipali ma jafx xi waħda minn dawn xogħol li sar f'dik il-funzjoni tpartit, sakemm huwa attwalment mgħoddija f'dawk argumenti mid pointer jew b'referenza. Issa, is-soluzzjoni fundamentali biex din il-problema ma 'swap hija tgħaddi affarijiet fil mill-indirizz. Iżda jirriżulta, wisq, x'hemm ilu għaddej hawn fuq dik il-parti tar-rettangolu dan il-ħin huwa iżda hemm aktar memorja up hemm. U meta inti dinamikament jalloka memorja, jekk huwa ġewwa tal GetString, li aħna kont qed tagħmel għalik fil-CS50 librerija, jew jekk inti guys sejħa malloc u jistaqsi is-sistema operattiva għal blokki ta ' memorja, dan ma jaqax mill-munzell. Jidħol minn post ieħor fil-memorja tal-kompjuter tiegħek li sejjaħ-borġ. U li mhux xi differenti. Huwa l-istess RAM. Huwa l-istess memorja. Huwa biss l-RAM li f'idejn hemm minflok stabbiliti hawn. 

U hekk xi jfisser? Ukoll, jekk il-kompjuter tiegħek ammont finit ta 'memorja u l-munzell hu jikbru, hekk biex jitkellmu, u l-borġ, skond għal dan vleġġa, qed jikber l isfel. Fi kliem ieħor, kull darba li inti sejħa malloc, int qed jingħataw porzjon tal-memorja minn fuq, allura forsi ftit aktar baxxa, imbagħad ftit aktar baxxi, kull darba li inti sejħa malloc, -borġ, huwa l-użu, qed tip ta 'tkabbir, jikber eqreb u eqreb lejn xiex? Il-munzell. Allura ma dan jidher bħala idea tajba? I mean, fejn mhuwiex verament ċara dak li inkella tista 'tagħmel jekk inti biss jkollhom ammont finit ta 'memorja. Iżda dan huwa żgur ħażin. Dawn iż-żewġ vleġeġ huma fuq crash kors għal xulxin. 

U jirriżulta li Guy ħażina, folks li huma partikolarment tajba mal-programmazzjoni, u jippruvaw Hack fil-kompjuters, jistgħu jisfruttaw din ir-realtà. Fil-fatt, ejja jikkunsidraw snippet ftit. Allura dan huwa eżempju inti tista 'taqra dwar f'aktar dettall fuq il-Wikipedija. Aħna ser punt inti fil- artikolu jekk kurjużi. Iżda hemm xi attakk ġeneralment magħrufa bħala overflow buffer li ilha teżisti sakemm bnedmin kellhom il-ħila biex jimmanipulaw memorja tal-kompjuter, speċjalment fil C. Allura dan huwa programm arbitrarja ħafna, imma ejja taqrah mill-qiegħ up. Main fis star char argC ARGV. Allura huwa programm li jieħu argumenti kmand linja. U kollha prinċipali ma jidher li huwa call funzjoni, sejħa hija F għas-sempliċità. U tgħaddi fil xiex? ARGV ta 'wieħed. Għalhekk jgħaddi fil F x'ikun il-kelma hija li l-utent ittajpjat fil-pront wara l- isem tal-programm fil-livelli kollha. Tant simili Caesar jew Vigenere, li inti tista 'recall tagħmel ma' ARGV. 

Allura x'inhi l F? F ittieħdet fi string kif argument unika tiegħu, AKA stilla char, l-istess ħaġa, bħala sekwenza. U huwa msejjaħ arbitrarju bar f'dan l-eżempju. U imbagħad xawwat c 12, biss f'termini laymans, dak li huwa char c parentesi 12 tagħmel għalina? X'hemm do? Allokazzjoni memorja, speċifikament 12 bytes għal 12 Chars. Eżattament. U allura l-aħħar linja, ħawwad u kopja, inti ħadthom probabbilment ma bbenefikawx. Din hija kopja string funzjoni li l-għan fil-ħajja huwa li kopja tieni argument tagħha fis-ewwel argument tagħha, iżda biss sa Ċertu numru ta 'bytes. Allura l-tielet argument jgħid, kemm bytes għandek kopja? It-tul ta 'bar, ikun x'ikun l-utent ittajpjat fil. U l-kontenut ta ' bar, li string, huma ikkopjata fil-memorja osservat f'mill C. 

Allura dan jidher tip ta 'stupid, u huwa. Dan huwa eżempju artifiċjali, imma hija rappreżentattiva ta 'klassi ta' vetturi attakk, mod ta 'jattakkaw programm. Kollox huwa multa u tajba jekk l-utent tipi Fi ftit kliem li l-11-karattri jew inqas, flimkien mal-backslash żero. X'jiġri jekk it-tipi utent f'aktar minn 11 jew 12 jew 20 jew 50 karattru? X'hemm dan il-programm se jagħmlu? Tort Potenzjalment SEG. Huwa ser li bl-addoċċ kopja kollox bar up t-tul tiegħu, li huwa litteralment kollox fil-bar, fil-indirizz indikat fil C. Iżda C għandha biss preemptively mogħti bħala 12 bytes. Iżda hemm ebda verifika addizzjonali. M'hemm l-ebda jekk il-kondizzjonijiet. M'hemm l-ebda żball iċċekkjar hawn. 

U iva, liema dan il-programm huwa se tagħmel huwa biss bl-addoċċ kopja ħaġa waħda għall-oħra. U hekk jekk aħna tiġbed bħala stampa, hawn biss sliver ta 'l-ispazju memorja. Allura avviż fil-qiegħ, aħna għandhom il-bar varjabbli lokali. Allura li pointer li għaddej biex store-- pjuttost li argument lokali li l- ser taħżen l-bar sekwenza. U mbagħad avviż biss fuq minnu fix munzell, għaliex kull darba li inti ssaqsi għall-memorja fuq il-munzell, din tmur ftit hawn fuq pictorially, avviż li konna ltqajna 12 bytes hemmhekk. Il-wieħed fuq tax-xellug huwa C parentesi żero u l-waħda qiegħ dritt huwa Ċ parentesi 11. Li jinsab biss kif il-kompjuters ser jistabbilixxu dan jitwettaq. Hekk biss intuwittivament, jekk bar għandha aktar minn 12 karattri fit-total, inklużi l-backslash żero, fejn huwa l- 12 jew il-kategorija C 12 se jmorru? Jew pjuttost fejn huwa l-12 karattru jew il-karattru 13, il-karattru mija jmorru li jispiċċaw fl-istampa? Fuq jew taħt? 

Dritt, għaliex anki jekk il-munzell innifsu tikber fuq, ladarba inti ħadthom tpoġġi Jittieħed fil dan, għal raġunijiet tad-disinn, ipoġġi l-memorja minn fuq għal isfel. Mela jekk inti ħadthom ltqajna aktar minn 12 bytes, int ser tibda biex jissostitwixxu bar. Issa li l-bug, imma hija mhux verament big deal. Iżda huwa big deal, għaliex hemm Jittieħed aktar għaddejjin fil-memorja. Allura hawnhekk kif nistgħu jitqiegħdu hello, li huma ċari. Jekk I ittajpjat fil bonjour fil-prompt. Backslash zero H-E-L-L-O, jispiċċa fil dawk 12 bytes, u aħna qed super sikur. Kollox huwa tajjeb. Imma jekk jien xi ħaġa tip itwal, potenzjalment huwa ser creep fl-ispazju bar. Iżda agħar għadu, jirriżulta out dan il-ħin, anke jekk aħna qatt ma stajt tkellem dwar dan, il-munzell huwa użat għall-għalf oħra. Huwa mhux biss varjabbli lokali. 

C hija lingwa f'livell baxx ħafna. U tip ta 'segretament juża l-munzell wkoll li tiftakar meta funzjoni hija magħrufa, liema l-indirizz huwa tal-funzjoni ta 'qabel, sabiex ikun jista 'tiżdied lura għal dik il-funzjoni. Allura meta sejħiet ewlenin tpartit, fost l-affarijiet imbuttat fuq il-munzell huma mhux biss swaps varjabbli lokali, jew argumenti tagħha, wkoll segretament imbuttat fuq il-munzell kif rappreżentat billi dak il-porzjon aħmar hawn, huwa l-indirizz ta 'prinċipali fiżikament fil-memorja tal-kompjuter tiegħek, b'tali mod li meta swap isir, il-kompjuter jaf I bżonn li jmorru lura għal main u finitura jesegwixxi l-funzjoni prinċipali. Allura dan huwa perikoluż issa, għaliex jekk it-tipi utent fil ukoll aktar minn bonjour, tali li l-input l-utent clobbers jew overwrites dik is-sezzjoni aħmar, loġikament jekk il-kompjuter biss ser bl-addoċċ jassumi li l-bytes f'dak porzjon aħmar huma l-indirizz fejn għandu jirritorna, X'jiġri jekk l-avversarju huwa intelliġenti biżżejjed jew xortik tajba biżżejjed li jitqiegħed sekwenza ta 'bytes hemmhekk li tidher bħal indirizz, imma hija l-indirizz tal-kodiċi li hu jew hi trid il-kompjuter li jesegwixxi minflok prinċipali? 

Fi kliem ieħor, jekk dak il- utent huwa ittajpjar fil-pront, mhix biss xi ħaġa bħal innokwa hello, iżda huwa attwalment kodiċi li s ekwivalenti li jitħassar fajls kollha din utent? Jew email password tagħhom lili? Jew jibdew qtugħ tagħhom keystrokes, id-dritt? Hemm mod, ejja jistipulaw llum, li dawn jistgħu tip fil mhux biss bonjour dinja jew l-isem tagħhom, dawn jistgħu essenzjalment jgħaddu bi kodiċi, żerijiet u dawk, li l-kompjuter żbalji kemm għall-kodiċi u l-indirizz. Allura għalkemm kemmxejn astratt, jekk il- tipi utent fil-kodiċi tal-kontradittorju biżżejjed li aħna ser tiġġeneralizza hawn bħala A. A hija attakk jew avversarji. Jittieħed hekk biss ħżiena. Aħna ma jimpurtahom dwar il- numri jew l-żerijiet jew dawk illum, b'tali mod li inti tispiċċa kitba fuq dik it-taqsima aħmar, avviż li sekwenza ta 'bytes. O 835 C żero tmienja żero. U issa kif artikolu Wikipedija hawn ippropona, jekk inti issa attwalment tibda ittikkettjar tal-bytes fil-kompjuter tiegħek memorja, dak l-artikolu Wikipedia huwa tipproponi tkun li, dak jekk l-indirizz ta 'dak byte fuq tax-xellug huwa 80 C 0 3508. 

Fi kliem ieħor, jekk il-Guy ħażina hija intelliġenti biżżejjed bil-kodiċi tiegħu jew tagħha li fil-fatt imqiegħda numru hawnhekk li jikkorrispondi għall-indirizz tal-kodiċi hu jew hi injettata fil-kompjuter, inti jista trick il-kompjuter fis tagħmel xejn. It-tneħħija fajls, email affarijiet, xamm traffiku tiegħek, litteralment xejn jista 'jkun injettat fil-kompjuter. U għalhekk overflow buffer attakk fil-qalba tagħha huwa biss stupid, stupid prevalenti ta 'firxa li ma kellux konfini tagħha ċċekkjati. U dan huwa dak li huwa super perikoluż u simultanjament super qawwija fis-C hija li aħna tabilħaqq għandhom aċċess għall kullimkien fil-memorja. Huwa f'idejn lilna, il-programmers, li jiktbu l-kodiċi oriġinali biex jiċċekkja l-tul darn ta 'kwalunkwe arrays li aħna qed manipulazzjoni. Allura biex tkun ċara, x'inhu l-jiffissaw? Jekk aħna roll lura għal din kodiċi, I m'għandhomx biss jibdlu t-tul ta 'bar, dak inkella għandi jiġi verifikat? X'iktar għandi tkun qiegħda tagħmel biex jipprevjenu dan l-attakk kollox? Ma rridx li biss bl-addoċċ jgħidu li inti għandek kopja kif ħafna bytes kif huwa t-tul ta 'bar. Irrid ngħid, kopja kif ħafna bytes kif huma bar sal-allokati memorja, jew 12 maximally. So I bżonn xi tip ta 'jekk il-kundizzjoni li ma tivverifika t-tul ta 'bar, imma jekk dan jaqbeż 12, aħna kodiċi biss hard 12 bħala l-akbar distanza possibbli. Inkella l-buffer hekk imsejħa attakk overflow jista 'jiġri. Fil-qiegħ ta 'dawk slajds, jekk int kurjużi biex taqra aktar huwa l-artikolu oriġinali attwali jekk inti tixtieq li tagħti ħarsa. 

Imma issa, fost l-prezzijiet mħallsa hawn kien ineffiċjenzi. Allura li kien malajr Ħarsa livell baxx lejn dak problemi jistgħu jinqalgħu issa li aħna ikollhom aċċess għall-memorja tal-kompjuter. Iżda problema oħra aħna diġà stumbled fuq it-tnejn kien biss il-ineffiċjenza ta 'lista marbuta. Aħna lura għal żmien lineari. Aħna m'għadx għandhom firxa kontigwi. Aħna ma jkollhom aċċess bl-addoċċ. Aħna ma tistax tuża notazzjoni parentesi kwadri. Aħna litteralment jkollu juża loop filwaqt bħal dak I kiteb mument ilu. Iżda nhar it-Tnejn, aħna qal li nistgħu creep lura fil-isfera ta 'effiċjenza kisba xi ħaġa li logaritmika forsi, jew aħjar għadhom, forsi anki xi ħaġa li hekk imsejħa time kostanti. Allura kif nistgħu nagħmlu dan billi jużaw dawn ġdida għodod, dawn l-indirizzi, dawn pointers, u kamini affarijiet ta 'tagħna stess? Ukoll, ejja ngħidu li hawn, dawn huma mazz ta 'numri li rridu li jaħżen fil- istruttura tad-data u tfittxija effiċjenti. Aħna assolutament jistgħu Rewind għal ġimgħa tnejn, tarmi dawn fi firxa, u tfittxija billi jużaw search binarja. Iddividi u conquer. U fil-fatt li kiteb tfittxija binarju fil PSET3, fejn inti implimentax il-programm isibu. Imma inti taf liema. Hemm tip ta 'aktar mod għaqlija li jagħmlu dan. Huwa ftit aktar sofistikati u forsi jippermetti li tara għaliex binarju tfittxija hija tant malajr. L-ewwel, ejja jintroduċu il-kunċett ta 'siġra. Li anki jekk fil siġar realtà tip ta ' jikbru bħal dan, fid-dinja tal-kompjuter xjenza huma tip ta 'jikbru isfel bħal siġra tal-familja, fejn inti għandek nanniet tiegħek jew in-nanniet kbira jew whatnot fil-quċċata, il-patrijarka u l-matriarch tal-familja, biss wieħed hekk imsejħa għeruq, node, hawn taħt li huma tfal tagħha, hawn taħt li huma tfal tagħha, jew dixxendenti tiegħu b'mod aktar ġenerali. U ħadd mdendlin off l-qiegħ tal-familja siġra, minbarra li l- iżgħar fil-familja, jista 'wkoll jkun biss ġenerikament imsejjaħ il-weraq tas-siġra. 

Allura dan huwa biss mazz ta 'kliem u definizzjonijiet għal xi ħaġa imsejħa siġra fil-kompjuter xjenza, ħafna bħal siġra tal-familja. Iżda hemm incarnations fancier ta 'siġar, li waħda minnhom jissejjaħ siġra tfittxija binarju. U inti tista 'tip ta' tease apparti dak dan ħaġa ma. Ukoll, huwa binarju fis F'liema sens? Fejn ma l-binarju jiġu minn hawn? Jiddispjacini? Huwa mhux tant l waħda jew. Huwa aktar li kull wieħed mill-lymph m'għandha l-ebda aktar minn żewġt itfal, kif naraw hawn. B'mod ġenerali, tree-- u ġenituri tiegħek u nanniet jista 'jkollhom bħala ħafna tfal jew grandkids kif huma attwalment jixtiequ, u għalhekk per eżempju hemm għandna tliet tfal off li node lemin, iżda fil-siġra binarju, node għandha żero, wieħed, jew żewġt itfal maximally. U li l-proprjetà sbieħ, għaliex jekk huwa mgħotti b tnejn, aħna qed tmur biex tkun tista ' jiksbu log bażi ftit tnejn azzjoni għaddejjin hawn finalment. Allura aħna għandna xi ħaġa logaritmika. Iżda aktar fuq li fil-mument. Fittex siġra ifisser li n-numri huma rranġati b'tali mod li l-wild xellug valur huwa akbar mill-għerq. U tat-tfal id-dritt tagħha huwa akbar mill-għerq. Fi kliem ieħor, jekk inti tieħu xi waħda minn dawn lymph,-ċrieki fil din l-istampa, u tħares lejn xellug tagħha tfal u tat-tfal dritt tiegħu, l-ewwel għandu jkun inqas minn, it-tieni għandu jkun akbar minn. Allura sanità jiċċekkjaw 55. Huwa ħalla tfal 33. Huwa inqas minn. 55, tfal id-dritt tagħha huwa 77. Huwa akbar minn. U li definizzjoni rikursivi. Nistgħu jivverifikaw kull wieħed minn dawk lymph u l-istess mudell kien iżomm. 

Allura x'hemm sbieħ fil- siġra tfittxija binarju, huwa li wieħed, nistgħu jimplimentawha bil-Struct, bħad dan. U anki jekk aħna qed jitfg lottijiet ta 'strutturi f'livell tiegħek, dawn qed pjuttost intuwittivi issa nisperaw. Is-sintassi għadu arcane ċerta, iżda l-kontenut ta 'node f'dan context-- u nżommu jużaw il-node kelma, jekk huwa rettangolu fuq l-iskrin jew ċirku, huwa biss ftit kontenitur ġenerika, f'dan il-każ ta 'siġra, bħal dak rajna, għandna bżonn integer f'kull wieħed mill-lymph u mbagħad I bżonn żewġ pointers tipponta għat-tarbija xellug u l-wild dritt, rispettivament. Allura li kif nistgħu jimplimentaw dik fil-Struct. U kif tista I timplimentah fil-kodiċi? Well, ejja tagħti quick ħarsa lejn dan l-eżempju ċkejkna. Mhuwiex funzjonali, imma stajt kkupjati u pasted dik l-istruttura. U jekk il-funzjoni tiegħi għal binarja siġra tfittxija tissejjaħ tfittxija, u dan jieħu żewġ argumenti, integer N u werrej li għal node, so a pointer għall-siġra jew pointer l-għerq ta 'siġra, kif nista tmur dwar tiftix għal N? Ukoll, l-ewwel, għaliex jien jittrattaw pointers, Jien ser tagħmel verifika sanità. Jekk ugwali siġra ugwali null, hija N f'dan siġra jew le f'dan il-siġra? Ma jistax ikun, right? Jekk I am passat null, hemm xejn hemmhekk. I tista 'ukoll biss addoċċ jgħidu ritorn foloz. Jekk inti tagħti me xejn, I żgur ma tistax ssib xi numru N. Allura x'iktar jista I check issa? Jien se ngħid ukoll inkella jekk N hija inqas minn dak kollu li huwa fil-node siġra li stajt ġiet valur N mogħtija. Fi kliem ieħor, jekk in-numru jien tfittex, N, hija inqas mill-node li jien tħares lejn. U l-node I infittex fil jissejjaħ siġra, u jitlob lura mingħandhom il-eżempju preċedenti li jiksbu fil-valur fil-pointer, I jużaw in-notazzjoni vleġġa. Mela jekk N hija inqas minn vleġġa siġra N, nixtieq li kunċettwalment tmur xellug. Kif nista jesprimu tiftix xellug? Biex ikunu ċari, jekk dan huwa l-istampa in kwistjoni, u stajt ġiet mgħoddija li topmost vleġġa li l-tipponta 'l isfel. C'est pointer siġra tiegħi. Jien tipponta lejn l-għerq tal-siġra. U jien infittxu jiġifieri, għal in-numru 44, arbitrarju. Huwa 44 jew anqas jew iktar minn 55 ovvjament? Dan huwa inqas minn. U hekk dan jekk il-kundizzjoni tapplika. Allura kunċettwalment, dak li nixtieq li tfittxija jmiss jekk I infittex 44? Yeah? 

Eżattament, nixtieq li tfittex il-wild xellug, jew is-siġra xellug tal din l-istampa. U fil-fatt, let me permezz l-istampa isfel hawn għal ftit mument, peress I ma jistgħu scratch dan out. Jekk nibda hawn fuq 55, u Naf li l-valur 44 I infittex huwa li fuq ix-xellug, huwa tip ta 'prodotti simili dmugħ-ktieb tat-telefon fil nofs jew dmugħ-siġra fil nofs. I m'għadx għandhom jimpurtahom Din it-taqsima kollu tas-siġra. And yet, curiously f'termini tal- istruttura, dan il-ħaġa minn hawn li jibda bil 33, li hi stess hija siġra tfittxija binarju. I qal li l-kelma rikursivi qabel minħabba tabilħaqq din hija struttura ta 'data li skond id-definizzjoni hija rikursivi. Inti jista 'jkollhom siġra li l-din big, iżda kull waħda ta 'tfal tagħha jirrappreżenta siġra biss ftit iżgħar. Minflok ma jkun nanniet jew nannu, issa huwa biss mom or-- I ma jistgħux say-- ma mom jew dad, li jkun stramb. Minflok l-żewġt itfal hemmhekk tkun simili brother u aħwa. Ġenerazzjoni ġdida ta 'l-siġra tal-familja. Iżda strutturalment, huwa l-istess idea. U jirriżulta I għandhom funzjoni li magħhom I tista 'tfittex tfittxija binarja siġra. Huwa sejjaħ tfittxija. I tfittxija għal N siġra vleġġa xellug inkella jekk N hija ikbar mill-valur li jien bħalissa. 55 fl-istorja mument ilu. I jkollhom funzjoni msejħa tfittxija li nista 'biss jgħaddu N dan u recursively tfittxija is-sub-tree u biss ritorn tkun xi tkun din ir-risposta. Else Stajt ltqajna xi każ bażiku finali hawnhekk. 

X'inhu l-każ finali? Tree huwa jew null. Il-valur jien kemm infittxu huwa inqas minn jew akbar minn dik jew ugwali għal dan. U nista 'ngħid ugwali ugwali, iżda loġikament huwa ekwivalenti għal biss qal ieħor hawn. Allura vera hija kif I issib xi ħaġa. Allura nisperaw li dan huwa anki eżempju aktar konvinċenti milli l-funzjoni sigma stupid għamilna ftit lectures lura, fejn kien daqstant faċli biex jintuża linja biex jingħaddu l-numri minn wieħed N. Hawnhekk bi struttura data li hi stess hija recursively definiti u recursively mfassla, issa aħna l-abbiltà li jesprimu nfusna fil-kodiċi li hi stess hija rikursivi. Allura dan huwa l-istess kodiċi eżatt hawn. 

Allura liema problemi oħra nistgħu issolvi? Allura pass quick bogħod mill siġar għall ftit mument. Hawnhekk jiġifieri, jgħidu, il-bandiera Ġermaniża. U hemm b'mod ċar mudell għal din il-bandiera. U hemm lottijiet ta ' bnadar fid-dinja li huma sempliċi kemm dan f'termini ta 'kuluri tagħhom u l-mudelli. Iżda jissoponi li din hija maħżuna bħala Gif, jew JPEG, jew Bitmap, jew ping, kwalunkwe format tal-fajl grafika li magħhom int familjari, li wħud minnhom aħna qed playing magħhom PSET4. Dan ma jidhirx utli li jaħżen pixel iswed, pixel iswed, pixel iswed, dot, dot, dot, mazz sħiħ ta ' pixels iswed għall-ewwel scanline, jew ringiela, allura mazz sħiħ ta ' l-istess, allura mazz sħiħ tal-istess, u mbagħad mazz sħiħ ta 'aħmar pixels, pixels ħomor, aħmar pixels, imbagħad kollu mazz ta 'isfar pixels, isfar, id-dritt? 

Hemm tali ineffiċjenza hawn. Kif inti intuwittivament jikkompressa l-bandiera Ġermaniża jekk jimplimentawh bħala fajl? Bħal liema informazzjoni tista aħna ma jolqot ħażna fuq diska sabiex li jnaqqas daqs tal-fajl tagħna minn bħall a megabyte għal kilobyte, xi ħaġa iżgħar? Fejn tinsab il-redundancy hawn biex tkun ċara? Liema jista inti tagħmel? Yeah? Eżattament. Għaliex ma pjuttost milli tiftakar il-kulur ta 'kull pixel darn bħad inti qed tagħmel fil PSET4 mal-format tal-fajl Bitmap, għaliex ma inti biss jirrappreżentaw il- kolonna fuq ix-xellug ta 'pixels, per eżempju mazz ta 'iswed pixels, mazz ta 'aħmar, u mazz ta' isfar, u mbagħad biss b'xi mod encode l idea ta irrepeti dan 100 darba jew irrepeti dan 1,000 darba? Fejn 100 jew 1000 hija biss integer, sabiex inti jista 'jitbiegħed ma biss numru wieħed minflok mijiet jew eluf pixels ta addizzjonali. U fil-fatt, li kif aħna jista jikkompressa l-bandiera Ġermaniża. U Issa dak dwar il-bandiera Franċiża? U ftit xi tip ta ' eżerċizzju mentali, li flag jista 'jkun kompressat aktar fuq diska? Il-bandiera Ġermaniża jew l-Franċiż bandiera, jekk nieħdu dak l-approċċ? Il-bandiera Ġermaniża, għaliex hemm aktar redundancy orizzontali. U mid-disinn, fajl grafika ħafna formati tabilħaqq jaħdmu linji kif scan orizzontalment. Huma jistgħu jaħdmu vertikalment, biss umanità snin deċiżi ilu li aħna ser ġeneralment jaħsbu ta 'affarijiet ringiela billi ringiela minflok kolonna minn kolonna. Mela jekk inti kienu tabilħaqq li tħares lejn il-fajl daqs ta 'bandiera Ġermaniża u Franċiża bandiera, sakemm ir-riżoluzzjoni hija l-istess, l-istess wisa ' u l-għoli, dan wieħed hawn se tkun akbar, għaliex inti jkollhom jirrepetu lilek innifsek tliet darbiet. Għandek tispeċifika blu, irrepeti yourself, abjad, irrepeti yourself, aħmar, irrepeti yourself. Inti ma tistax biss jmorru kollha il-mod lejn il-lemin. U bħala twarrib, li jagħmlu ċar l-kompressjoni hija kullimkien, jekk dawn huma erba frames minn video-- inti jista tfakkar li movie jew video huwa ġeneralment bħal 29 jew 30 frejm kull sekonda. Huwa bħal ktieb flip ftit fejn inti biss tara l-immaġni, immaġni, immaġni, immaġni, immaġni biss super fast hekk jidher qisu l-atturi fuq l-iskrin mexjin. Hawn naħla bagħlija fuq quċċata ta mazz ta 'fjuri. U għalkemm jista 'jkun it-tip ta' diffiċli li wieħed jara ewwel daqqa t'għajn, l-unika ħaġa li jiċċaqilqu fil dan movie huwa l-naħla. 

X'inhu dumb dwar ħażna video mhux kompressat? Huwa tip ta 'ħela li jaħżen video kif erba immaġini kważi identiċi li differenti biss safejn fejn il-naħla hu. Inti tista tarmi l bogħod aktar ta 'dik l-informazzjoni u ftakar biss, per eżempju, l-ewwel frame u l-aħħar qafas, frejms importanti jekk inti stajt qatt semgħu l-kelma, u biss jaħżnu fil- nofs meta l-naħla hu. U inti ma għandekx taħżen kollha tal-roża, u l-blu, u l Valuri aħdar kif ukoll. Allura dan huwa li jgħidu biss li kompressjoni hija kullimkien. Huwa ta 'teknika aħna sikwit jużaw jew jieħdu għal mogħtija f'dawn il-jiem. 

Imma kif taħseb li jikkompressa test? Kif inti tmur dwar kompressjoni test? Ukoll, kull wieħed mill-karattri fit Ascii huwa byte wieħed, jew tmien bits. U dan huwa tip ta 'mutu, right? Għaliex inti probabilment tip A u E u I u O u U ħafna aktar spiss milli bħal W jew Q jew Z, jiddependi fuq il-lingwa li fiha int bil-miktub żgur. U hekk għaliex aħna jużaw tmien bits għal kull ittra, inkluż l-inqas ittri popolari, id-dritt? Għaliex ma jużaw inqas bits għal l-ittri super popolari, bħall E, l-affarijiet inti raden ewwel fil tmun tas Fortune, u l-użu aktar bits għal l-ittri inqas popolari? Għaliex? Għaliex aħna qed biss ser jużawhom inqas frekwenti. 

Ukoll, jirriżulta li kien hemm Kien tentattivi magħmula biex jagħmlu dan. U jekk inti recall mill-grad iskola jew skola għolja, kodiċi Morse. Kodiċi Morse għandha tikek u daxxijiet li jista 'jkun trasmessi tul wajer kif ħsejjes jew is-sinjali ta 'xi tip. Iżda kodiċi Morse huwa super nadif. Huwa tip ta 'sistema binarja fil li inti għandek tikek jew dashes. Imma jekk inti tara, per eżempju, żewġ tikek. Jew jekk inti taħseb lura lill-operatur li tmur bħal ħoss, ħoss, ħoss, ħoss, laqtu grillu ftit li jittrasmetti sinjal, jekk inti, il-benefiċjarju, jirċievi żewġ tikek, dak messaġġ irċevejt? Kompletament arbitrarja. 

I? I? Jew dak about-- jew I? Forsi kien biss tnejn id-dritt E ta? Allura hemm din il-problema tal decodability ma Morse kodiċi, fejn sakemm il- persuna li tibgħat il-messaġġ inti attwalment pauses sabiex inti tista sort ta tara jew tisma l-lakuni bejn ittri, mhuwiex biżżejjed biss biex tibgħat nixxiegħa ta 'żerijiet u dawk, jew tikek u daxxijiet, għaliex hemm ambigwità. E huwa dot wieħed, hekk jekk inti tara żewġ tikek jew tisma żewġ tikek, forsi huwa s tnejn E jew forsi huwa wieħed I. Għalhekk għandna bżonn ta 'sistema li l- ftit aktar għaqlija minn dak. Allura raġel jismu snin Huffman ilu ħarāet bil eżattament dan. Allura aħna qed biss jmorru li tieħu t'għajn malajr lejn kif siġar huma germane għal dan. Ejja ngħidu li dan huwa xi messaġġ stupid inti tixtieq li tibgħat, komposta minn ftit A, B, D'C iu E, il imma hemm ħafna ta 'redundancy hawn. Mhuwiex maħsub li jkun l-Ingliż. Mhuwiex encrypted. Huwa biss messaġġ stupid ma 'lottijiet ta' ripetizzjoni. Mela jekk inti fil-fatt għadd out kollha l- 'A, B, Ċ, D, u E tal, hawn il-frekwenza. 20% ta 'l-ittri huma 'A, 45% ta' l-ittri huma s E, u tliet frekwenzi oħra. Aħna jingħaddu up hemm manwalment u biss ma l-matematika. 

Għalhekk jirriżulta li Huffman, xi żmien ilu, induna li, inti taf dak, jekk nibda bini siġra, jew għall-foresti ta 'siġar, jekk inti se, kif ġej, I tista 'tagħmel dan li ġej. Jien ser tagħti lil kull node mill-ittri li I jimpurtahom u jien ser taħżen ġewwa ta 'dik node il-frekwenzi bħala b'punt li jvarja valur, jew inti tista 'tagħmel użu minnha għal N, wisq, imma aħna ser biss użu float hawn. U l-algoritmu li huwa propost huwa li inti jieħdu din foresti ta 'node wieħed siġar, siġar hekk super qasir, u tibda konnessjoni tagħhom ma ' gruppi ġodda, ġenituri l-ġodda, jekk inti se. U inti tagħmel dan billi jagħżlu l- żewġ frekwenzi iżgħar kull darba. So I ħa 10% u 10%. I joħolqu node ġdid. U I-sejħa tal node ġdid 20%. 

Liema tnejn lymph I jikkombinaw jmiss? Huwa ftit ambigwa. Allura hemm xi każijiet rokna sa jikkunsidraw, iżda li żżomm affarijiet pretty, Jien ser jagħżlu 20% - I issa jinjora t-tfal. Jien ser jagħżlu 20% u 15% u jisiltu żewġ truf ġodda. U issa li żewġ nodi do I loġikament jikkombinaw? Injora-tfal kollha, kollha l- neputijiet, biss ħarsa lejn l-għeruq issa. Liema tnejn lymph nista jorbtu flimkien? Punt tnejn u 0.35. So let me jisiltu żewġ truf ġodda. U allura stajt biss ltqajna wieħed xellug. Allura hawnhekk siġra. U huwa kien imfassal apposta tfittex tip ta 'pretty, iżda tinnota li t-trufijiet għandhom wkoll ġiet ittikkettjata żero u wieħed. Sabiex kollha tat-truf tax-xellug huma żero arbitrarju, iżda b'mod konsistenti. L-truf dritt huma dawk. 

U iva, liema Hoffman propost jiġifieri, jekk inti tixtieq li jirrappreżentaw B, aktar milli jirrappreżentaw in-numru 66 kif l ASCII li huwa tmien bits kollu, inti taf liema, just maħżen il-mudell żero, żero, żero, żero, għaliex dak l-passaġġ minn siġra tiegħi, siġra Sur Huffman, il il-weraq mill-għeruq. Jekk inti tixtieq li taħżen E, b'kuntrast, ma tibgħat tmien bits li jirrappreżentaw E. Minflok, tibgħat dak mudell ta 'bits? One. U x'hemm sbieħ dwar dan hija li E hija l-ittra l-aktar popolari, u inti qed tuża l- kodiċi iqsar għal dan. Li jmiss aktar popolari ittra qisu kien A. U hekk kif ħafna bits ma hu jipproponi li jużaw għal dan? Zero, wieħed. 

U għaliex dan huwa implimentat kif din is-siġra, għal issa let me jistipulaw hemm ebda ambigwità bħal fil Morse kodiċi, minħabba kollha ta 'l- ittri li jimpurtahom huma fl-aħħar ta 'dawn truf. Allura li jinsab biss wieħed applikazzjoni ta 'siġra. Dan is-- u jien ser mewġa naħa tiegħi f'dan kif inti tista jimplimentaw dan bħala struttura C. Jinħtieġ li jgħaqqdu simbolu, bħal char, u l-frekwenza tax-xellug u lemin. Imma ejja nħarsu lejn żewġ Eżempji finali li inti ser jiksbu pjuttost familjari ma 'wara kwizz żero problema stabbiliti ħamsa. 

Għalhekk hemm l-istruttura tad-data magħruf bħala mejda hash. U tabella hash huwa tip ta jibred fid li għandha bramel. U jissoponi hemm erba bramel hawn, biss erba spazji vojta. Hawn gverta ta 'karti, u hawn huwa klabb, spade, klabb, djamanti, klabb, djamanti, klabb, djamanti, clubs-- għalhekk dan huwa l-każwali. Qlub, hearts-- hekk jien bucketizing kollha tal-inputs hawn. U ħtiġijiet mejda hash li tħares lejn input tiegħek, u mbagħad titqiegħed f'ċertu post ibbażati fuq dak li tara. Huwa ta 'algoritmu. UI kienet qed tuża super algoritmu viżwali sempliċi. Il-parti l-agħar tagħha kien ftakar dak l-istampi kienu. U allura hemm erba 'affarijiet totali. 

Issa l-stacks kienu qed tikber, li hija ħaġa disinn deliberat hawn. Imma dak li inkella jista 'nagħmel? Allura fil-fatt hawnhekk għandna mazz ta 'qodma kotba eżami iskola. Ejja ngħidu li mazz ta ' ismijiet istudenti are here fuq. Hawn tabella hash akbar. Minflok erba bramel, Għandi, ejja ngħidu 26. U aħna ma jridu jmorru tissellef 26 affarijiet minn barra [? Annenberg?], Hekk hawnhekk ħames dak jirrappreżentaw A permezz Z. U jekk jien tara student li ismu jibda bl A, Jien ser tpoġġi tiegħu jew kwizz tagħha hemmhekk. Jekk xi ħadd jibda bil Ċ, hemmhekk, A-- attwalment, ma riedx li tagħmel dan. B tmur minn hawn. So I ħadthom ltqajna A u B u C. U issa hawnhekk student ieħor A. Iżda jekk din it-tabella hash huwa implimentati ma 'firxa, Jien tip ta 'invitat f'dan il-punt, id-dritt? I tip ta 'bżonn li jdaħħlu dan x'imkien. 

Allura mod wieħed I tista 'ssolvi din hija, kollha dritt, A huwa busy, B hija okkupata, C hija okkupata. Jien ser jniżżlu fil D. Għalhekk fl ewwel, I jkollhom aċċess immedjat bl-addoċċ għal kull bramel għall-istudenti. Imma issa huwa tip ta 'devoluti fis lineari xi ħaġa, għaliex jekk I trid tfittex għal xi ħadd isem tiegħu jibda bi A, I check hawn. Iżda jekk dan ma jkunx il-A student I infittex, I tip ta 'għandek tibda ikkontrollar l bramel, għaliex dak li għamilt kien tip ta 'lineari sonda l-istruttura tad-data. Mod stupid ta 'tgħid biss ħarsa għall-ewwel ftuħ disponibbli, u mqiegħda bħala pjan B, biex ngħidu hekk, jew pjan D f'dan il-każ, il-valur f'dak il-lok minflok. Dan huwa biss hekk li jekk inti stajt ltqajna 26 postijiet u l-ebda istudenti bl-isem Q jew Z, jew xi ħaġa bħal li, għall-inqas inti qed tuża l-ispazju. 

Iżda aħna stajt diġà raw aktar soluzzjonijiet għaqlija hawn, id-dritt? What would you do minflok jekk għandek xi ħabta? Jekk żewġ persuni jkollhom l-isem A, dak li kienu aktar intelliġenti jew Soluzzjoni intuwittivi milli sempliċiment tqegħid A fejn D suppost tkun? Għaliex ma I biss jmorru [barra? Annenberg?], bħal malloc, node ieħor, poġġih hawn, u mbagħad iwettqu l Student hawn. I hekk li essenzjalment ikollhom xi tip ta 'firxa, jew forsi aktar elegantly kif aħna qed jibdew biex tara lista marbuta. 

U hekk tabella hash hija struttura li jista 'jidher biss bħal din, iżda aktar cleverly, inti xi ħaġa imsejħa chaining separata, li biha tabella hash pjuttost sempliċement firxa, kull wieħed l-elementi tagħhom ma jkunx numru, hija nnifisha lista marbuta. Hekk li tikseb aċċess super fast jiddeċiedu fejn issir hash valur tiegħek biex. Ħafna bħall mal-eżempju cards, I għamel deċiżjonijiet super malajr. Qlub tmur hawn, djamanti tmur hawn. Istess hawn, A tmur hawn, D tmur hawn, B tmur hawn. Allura super fast ħarsa-ups, u jekk jiġri li jinżel fit każ kolliżjonijiet fejn inti ħadthom ltqajna, żewġ nies bl-istess isem, tajjeb allura inti biss tibda jgħaqqduhom flimkien. U forsi inti jżommhom magħżula alfabetikament, forsi inti ma. Imma l-anqas issa għandna l-dinamiżmu. Allura fuq naħa waħda għandna super fast ħin kostanti, u tip ta 'żmien lineari involut jekk dawn il-listi marbuta tibda tikseb ftit twil. 

Allura dan it-tip ta 'iblah, snin Joke geeky ilu. Fil-CS50 Hack-a-Thon, meta l-istudenti check in, xi TF jew CA kull sena jaħseb huwa umoristiċi li imqiegħda sinjal bħal dan, fejn hija biss ifisser li jekk isem tiegħek tibda ma 'A, jmorru b'dan il-mod. Jekk tibda ismek ma 'B, mur this-- OK, huwa umoristiċi forsi aktar tard fil-semestru. Iżda hemm ieħor mod ta 'kif isir dan, wisq. Come lura għal dak. 

Allura hemm din l-istruttura. U dan huwa aħħar tagħna istruttura għal-lum, li hija xi ħaġa imsejħa trie. T-R-I-E, li għal xi raġuni huwa qasir għall-irkupru, iżda huwa msejjaħ trie. Allura trie hija ieħor interessanti amalgama ta 'lott ta' dawn l-ideat. Huwa siġra, li konna rajna qabel. Mhuwiex siġra tfittxija binarju. Huwa siġra ma 'kwalunkwe numru ta' tfal, iżda kull wieħed mill-tfal fi trie huwa firxa. Firxa ta 'daqs, jiġifieri, 26 jew forsi 27 jekk inti tixtieq li tappoġġja ismijiet hyphenated jew apostrophes fl-ismijiet tan-nies. 

U għalhekk din hija struttura ta 'data. U jekk inti tħares minn fuq għal isfel, bħal jekk inti tħares lejn il-node quċċata hemm, M, huwa tipponta lejn il-ħaġa fuq ix-xellug hemm, li mbagħad A, X, W, E, L, L. Dan huwa biss struttura data li b'mod arbitrarju huwa ħażna ismijiet tan-nies. U Maxwell tkunx maħżuna mis ftit wara triq ta 'firxa biex array biex array. Imma x'hemm aqwa dwar trie huwa li, billi lista marbuta u anke firxa, l-aħjar aħna stajt qatt gotten huwa żmien lineari jew il-ħin logaritmika tfittex xi ħadd up. F'din l-istruttura tad-data ta 'trie, jekk istruttura tad-data tiegħi isem wieħed fih u jien infittxu Maxwell, jien ser issib lilu pretty malajr. I biss tfittex M-A-X-W-E-L-L. Jekk din l-istruttura tad-data, għall-kuntrarju, jekk N hija miljun, jekk ikun hemm miljun ismijiet f'din l-istruttura tad-data, Maxwell għadu għaddej li jkun discoverable wara biss M-A--X W-E-L-L passi. U passi David-- D-A-V-I-D. Fi kliem ieħor, permezz tal-bini struttura data li l- ltqajna kollha ta 'dawn arrays, li kollha infushom jappoġġjaw l-aċċess bl-addoċċ, I tista 'tibda tfittex up Popolari isem użu ta 'ammont ta' ħin li l- proporzjonali għall mhux in-numru ta 'affarijiet fl-istruttura tad-data, bħal miljun ismijiet eżistenti. L-ammont ta 'ħin li tieħu lili biex isibu M-A--X W-E-L-L f'din l-istruttura tad-data huwa proporzjonali ma 'l- daqs tal-istruttura tad-data, iżda għat-tul tal-isem. U realistiku l- ismijiet aħna qed tfittex up huma qatt ser tkun crazy twil. Forsi xi ħadd ikollu karattru 10 isem, 20 isem karattru. Huwa ċertament finite, id-dritt? Hemm umana fid-Dinja li għandu l-isem itwal possibbli, iżda li isem huwa kostanti tul valur, id-dritt? Ma jvarjaw fid ebda sens. Allura b'dan il-mod, konna kisbu istruttura tad-data li huwa żmien kostanti ħarsa-up. Hija ma tieħu għadd ta 'passi skond it-tul tal-input, iżda mhux in-numru ta 'isem fl-istruttura tad-data. Allura jekk aħna doppju tal-għadd ta 'ismijiet sena d-dieħla minn biljun għal żewġ biljun, sejba Maxwell se jieħu l-istess numru eżatt ta 'seba' passi biex issib lilu. U hekk aħna jidhru li kisbu Grail qaddis tagħna ta 'running time. 

Allura ftit avviżi malajr. Quiz żero huwa ġejjin up. Aktar dwar dan fuq il-websajt tal-kors ta matul il-koppja li jmiss ta 'ġranet. Tnejn lecture-- huwa btala hawn fil-Harvard nhar it-Tnejn. Mhuwiex fi New Haven, hekk aħna qed tieħu l-klassi lejn New Haven għall taħdita nhar it-Tnejn. Kollox se jkun iffilmjati u streaming live bħas-soltu, imma ejja tispiċċa llum bit-tieni clip 30 imsejħa "Ħsibijiet Deep" billi Daven Farnham, li kienet ispirata aħħar sena sas-Sibt "Ħsibijiet Deep" Night Live s billi Jack Handy, li għandu issa jagħmel sens. 

FILM: U issa, "Deep Ħsibijiet "mill Daven Farnham. Tabella hash. 

SPEAKER 1: Id-dritt, li hu għal issa. Aħna ser tara int ġimgħa d-dieħla. 

Doug: Biex tara li fl-azzjoni. Mela ejja tagħti ħarsa lejn dak id-dritt issa. Allura hawnhekk, għandna firxa mhux magħżul. 

IAN: Doug, inti tista 'tmur quddiem u jerġgħu jibdew dan għal wieħed biss sekonda, jekk jogħġbok. Kull dritt, kameras huma rolling, hekk azzjoni kull meta int lest, Doug, OK? Doug: Kull dritt, hekk dak li aħna hawn huwa firxa mhux magħżul. U stajt kkulurita l-elementi kollha aħmar li jindika li huwa, fil-fatt, mhux magħżul. Allura tfakkar li l-ewwel ħaġa li nagħmlu hija aħna issolvi l-nofs xellug tal-firxa. Imbagħad aħna issolvi d-dritt nofs il-firxa. U ya-da, ya-da, ya-da, aħna jingħaqdu flimkien. U aħna jkollhom firxa kompletament separat kif. Allura li kif jingħaqdu sort xogħlijiet. 

IAN: Whoa, Whoa, Whoa, maqtugħ, imqatta ', imqatta, maqtugħin. Doug, inti ma tistax biss ya-da, ya-da, ya-da, triqtek tip jingħaqdu. 

Doug: I biss għamlet. Huwa tal-multa. We qed imorru tajjeb. Ejja biss iżommu rolling. Allura xorta, 

IAN: Int għandek tispjega aktar bis-sħiħ minn dak. Li jinsab biss mhux biżżejjed. Doug: Ian, aħna ma bżonn li jmorru lura għal wieħed. Huwa tal-multa. Allura xorta, jekk aħna nkomplu bil merge-- Ian, aħna qed fil-nofs ta 'iffilmjar. 

IAN: I know. U ma nistgħux biss ya-da, ya-da, ya-da, permezz tal-proċess kollu. Int għandek tispjega kif il- żewġ naħat tikseb magħquda flimkien. 

Doug: Iżda aħna stajt diġà spjega kif it-tnejn sides-- 

IAN: You ħadthom biss murija minnhom firxa jingħaqdu. Doug: Huma jafu l-proċess. Huma qed multa. Imxejna marret fuqha għaxar darbiet. 

IAN: Inti biss skipped dritt fuqha. Aħna wieħed imur lura lejn, inti ma tista 'inti ya-da, ya-da fuqha. Dritt kollox, lura għal wieħed. 

Doug: irrid immur lura kollha permezz ta 'l-pjastri? Alla tiegħi. Huwa bħall-sitt darba, Ian. Huwa tal-multa. 

IAN: Kull dritt. Inti lest? Great. Azzjoni.