DAVID Malan: Kull dritt. Merħba lura għall CS50. Dan huwa l-bidu tal-ġimgħa d 8. U tfakkar li problema sett 5 intemm bi ftit ta 'sfida. Allura jekk wieħed jassumi inti rkuprati kollha ta 'tiegħek Fellows tagħlim u ritratti CA fil-fajl card.raw, inti eliġibbli li issa jsibu kollha ta 'dawk in-nies, u rebbieħ wieħed xxurtjati se jimxu dar ma 'wieħed ta 'dawn l-affarijiet, il-mozzjoni qabża mezz li tista 'tuża għall finali proġetti, per eżempju. Dan, kull sena, iwassal għal daqsxejn ta creepiness. U hekk dak li ħsibt I d tagħmel huwa sehem miegħek xi wħud mill-noti li għandhom marret quddiem u lura fuq il-lista tal-persunal ta tard. Per eżempju, biss aħħar lejl, kwotazzjoni unquote, minn wieħed mill-istaff membri, "I biss kellhom riperkussjonijiet student fuq bieb tiegħi li jieħdu ritratt miegħi. Stalkers, I jgħidlek. "Bdiet pjuttost deskrittiva u mbagħad aħna mċaqalqa fuq, kull siegħa jew hekk aktar tard, "I kellhom student stennija għalija wara taqsima u kellu kollha ta 'ismijiet tagħna u ritratti fuq xi folji tal-karta. "Kull dritt. Hekk organizzat, iżda mhux dak kollu li creepy għadu. Imbagħad, "I kien barra mill-belt din weekend, u meta sirt lura, kien hemm waħda fil tiegħi kamra tas-sodda. "[Rires] DAVID Malan: kwotazzjoni Next minn staff membru, "student waslet għall-dar tiegħi fil Somerville fil 04:00 dalgħodu. "Li jmiss persunal, "I ltqajna biex lukanda tiegħi f'San Francisco u student kien stennija għal me fil-lobby bi tliet DSLRs. " Tip ta 'kamera. "Jien ma anki fuq staff dan is-semestru, iżda student kissru fis-dar tiegħi dan filgħodu u rreġistrati l-ħaġa sħiħa ma 'Google ħġieġ. "U mbagħad fl-aħħar, "Mill-inqas 12-il persuna kienu eagerly jistennew għalija meta I ltqajna barra tal tiegħi LIMO, u mbagħad I woke up. "Kull dritt. Allura fost l-ritratti, kif inti tista ' ifakkar, huma dan sħabi hawnhekk, li inti tista 'tkun taf kif Milo Banana, li jgħix ma Lauren Carvalho, ras tagħna tagħlim Fellow. Milo, Milo, jiġu hawn boy. Milo. Milo. Mind you, hu liebes Google ħġieġ, hekk aħna ser nuruk kollha ta 'dan wara. Allura dan huwa Milo jekk inti tixtieq li jieħdu ritratt miegħu afterward. Jekk inti tixtieq li toqgħod attent fil-udjenza hemm. OK. C'est footage tajba. Ukoll, Milo Banana. Oh, ma tagħmel dan. [Daħk] OK. Allura kelma imbagħad fuq dak li jinsab quddiem, għaliex kif aħna jibdew transizzjoni, din il-ġimgħa speċifikament, minn Ċ kmand linja ambjentali għall PHP u JavaScript u SQL u HTML u CSS fl ambjent fuq l-internet, aħna ser tkun jgħammru inti ma 'l- aktar għarfien għal proġetti finali li huma potenzjali. Lejn dan il-għan, il-kors għandu tradizzjoni li jsiru seminars li huma dwar suġġetti tanġenzjali għall-kors. Ħafna x'jaqsmu mal-programmazzjoni u l- iżvilupp app u oħrajn, iżda mhux neċessarjament esplorata billi sillabu stess il-kors tal. Mela jekk inti jistgħu jkunu interessati fil waħda jew aktar ta 'seminars din is-sena, jirreġistraw fil cs50.net/seminar. Hemm seminars anzjani fil cs50.net/seminars. U fuq ir-roster s'issa din is-sena huma Apps Web aqwa mal Ruby fuq Binarji, li hija alternattiva lingwa li PHP. Lingwistika komputazzjonali. Introduzzjoni għall IOS, li hija l- pjattaforma li użaw għall-iPhone u iżvilupp iPad. JavaScript għal apps Web, aħna ser ikopru li, iżda dan is-seminar, inti ser tmur aktar fid-dettall. Qabża Mozzjoni, hekk aħna ser attwalment ikollhom xi tal-ħbieb tagħna mill Leap Mozzjoni, il-kumpanija stess, jingħaqdu magħna. Għada, fil-fatt, li jipprovdu hands-on seminar, jekk ta 'interess għalik. Meteor.js, teknika alternattiva għal użu JavaScript mhux fil-browser, iżda fuq server. Node.js, li huwa ferm f'dak vina kif ukoll. Sleek Disinn Android. Android tkun alternattiva popolari ħafna għall IOS u Windows Phone u pjattaformi mobbli oħra. U Web Sigurtà Difiża Attiva. Allura fil-fatt, jekk inti tixtieq li jidħlu għal din, let me jagħmlu nota ta 'dan. Aħna kuntenti ħafna li jgħidu li ħbieb tagħna fuq Leap Mozzjoni, li hija l-istartjar - dan il-mezz verament biss daħal out ftit xhur ilu - tkun graciously mogħtija 30 dawn il-mezzi għall-klassi għal kif ħafna studenti, jekk inti tixtieq li jissellef il-hardware lejn tmiem semestru u jużawh għall- proġett finali attwali. Huma jappoġġaw numru ta 'lingwi. Ħadd minnhom C, ħadd minnhom PHP, sabiex tirrealizza wieħed jew aktar minn dawn is-seminars jistgħu jkunu ta 'interess. U kollha se jkunu iffilmjati F'każ li m'intix kapaċi biex jattendu personalment. L-iskeda jitħabbru permezz email kif aħna ssolidifikat kmamar. U fl-aħħar, jekk inti tmur projects.cs.50.net, din hija website għandna tinżamm kull sena li nistiednu folks mill-komunità, fakultà, dipartimenti, persunal, u kemm fi barra ta 'CS50 li tipproponi ideat għall-proġetti. Affarijiet ta 'interess għall gruppi ta' studenti. Things ta 'interess għall-dipartimenti. Allura mbagħad hemm jekk int qed jitħabtu l-inċertezza dwar dak li yourself tixtieq tindirizza. Allura aħħar darba aħna introduċiet forsi struttura tad-data aktar kumplessi minn aħna'd jidhru fil-ġimgħat li għaddew. Aħna'd kienu jużaw arrays pretty heureusement bħala utli jekk struttura tad-data simplistiku. Imbagħad aħna introdotti dawn, li naturalment huma listi marbuta. U dak kien wieħed mill-motivazzjonijiet għall- introduzzjoni ta 'din l-istruttura tad-data? Yeah? X'hemm li? UDJENZA: Daqs Dynamic. DAVID Malan: Daqs Dynamic. Allura billi array, inti għandek taf daqs tagħha bil-quddiem meta inti tatiha. Fil-lista marbuta, inti ma għandek tkun taf li. Inti tista 'sempliċement malloc, jew b'mod iktar ġenerali, jalloka addizzjonali node, biex ngħidu hekk, kwalunkwe ħin li inti tixtieq li daħħal data aktar. U node tkun tifsira ebda predeterminat. Huwa biss terminu ġeneriku li jiddeskrivi xi tip ta 'kontenitur li aħna qed użu fl-istruttura tad-data tagħna biex jaħżnu xi oġġett ta 'interess, li f'dan il- każ jiġri li jkun interi. Iżda hemm dejjem tradeoff. Allura irridu jiksbu daqsijiet dinamiċi tad-data istruttura, iżda b'liema prezz inħallsu? X'hemm l-tnaqqis ta 'listi marbuta? Yeah? UDJENZA: Jirrikjedi memorja aktar. DAVID Malan: Hija teħtieġ aktar memorja, kif eżattament? UDJENZA: [inaudible]. DAVID Malan: Eżattament. Allura issa għandna pointers bidu memorja addizzjonali li aħna qabel ma kellhomx bżonn, minħabba li l-vantaġġ ta 'firxa, naturalment, huwa li kollox huwa kontigwa, lura lura biex lura, li jagħtik aċċess bl-addoċċ. Minħabba biss bl-użu bracket kwadru notazzjoni, jew teknikament aktar pointer aritmetika, minbarra sempliċi ħafna, inti tista 'aċċess kwalunkwe elementi fil-ħin kostanti. U fil-fatt, li tip ta 'ssemmi prezz ieħor li aħna qed tħallas bil- lista marbuta. X'jiġri mill-running time ta ' xi ħaġa simili Search, jekk irrid ssib xi valur u ġewwa ta 'lista marbut? X'jagħmel running time tiegħi sar? Big O ta 'n. Jekk huwa magħżula għal? X'jiġri jekk s magħżula l-istruttura tad-data? Nista 'nagħmel aħjar minn big O ta 'n għat-tiftix? Le, għaliex fl-agħar każ tista ' tajjeb ħafna jiġu magħżula, iżda n-numru qed tfittex jista 'jkun kbir. Jista 'jkun in-numru 100, li jista 'jiġri li tkun kollha il-mod fl-aħħar. U għaliex inti tista 'biss aċċess linked lista f'dan l-implimentazzjoni mill- mod ta 'l-ewwel node tagħha, int xorta tip ta 'minn xortih. Int għandek travers il-ħaġa sħiħa mill-ewwel għall-aħħar sabiex isibu li l-valur kbar bħall 100. Jew biex jiddeterminaw jekk huwa lanqas hemm. Allura ma nistgħux nagħmlu dak algoritmu fi data struttura li tidher bħal dan? Aħna ma tistax tagħmel tfittxija binarju, minħabba tfittxija binarju meħtieġ li kellna aċċess bl-addoċċ. Nistgħu biss qabża minn post għal post mingħajr ma jkollhom isegwu dawn frak tal-ħobż fil-forma ta 'dawn pointers. Issa, kif ma nimplimentaw dan? Ukoll, jekk immorru l-iskrin hawn, jekk nistgħu malajr reimplement din id-data istruttura - kalligrafija tiegħi li mhux kollha li kbira hawn, iżda aħna ser nippruvaw. Struct Allura typedef, u dak li għamlet I tixtieq li sejħa dan ħaġa up here? Node. So I ser tingħata us beda. U issa, dak li jeħtieġ li jkun ġewwa ta ' l-istruttura tad-data għal dak weħidhom marbuta lista? Kif oqsma ħafna? Allura tnejn. Wieħed huwa pjuttost faċli. Allura int n. U aħna tista 'sejħa n xejn irridu, iżda għandu jkun int jekk aħna qed implimentazzjoni ta 'lista marbuta għall ints. U issa dak ma-tieni qasam għandhom ikunu? Struct node *. Mela jekk nagħmel Struct node *, u mbagħad I tista 'sejħa dan ukoll kwalunkwe I jixtiequ, iżda biss li tkun ċara I ser sejħa dan li jmiss, kif aħna kont qed tagħmel. U allura jien ser tagħlaq braces kaboċċi tiegħi. U issa, kif l-aħħar darba, Nressaq node stabbiliti hawn. Imma jekk jien tiddikjara dan huwa bħala node, għaliex ma I jolqot li huma tant verbose hawn fil tiddikjara Struct node * li jmiss, għall-kuntrarju għal ftit node * jmiss? Yeah? UDJENZA: [inaudible]. DAVID Malan: Eżattament. Eżattament. Minħabba C verament tieħdok litteralment u biss jara d-definizzjoni ta node mod stabbiliti hawn, inti ma tistax jirreferu għaliha up here. Allura aħna għandna dan it-tip ta 'preemptive dikjarazzjoni hawnhekk, li hija ċertament aktar verbose. Struct node, dan ifisser aħna issa tista 'aċċess ġewwa tal-istruttura tad-data. U bħala twarrib, għaliex dan huwa isir ftit aktar suġġettiva issa, l-istilla jistgħu teknikament mur hawn, ikun jista 'jimxi hawn, tista' anki jmorru fin-nofs. Imxejna adottat, fil-Gwida tal-Istil għall il-kors, il-konvenzjoni ta 'tqegħid l-istilla dritt li jmiss għall-informazzjoni tip, li f'dan il-każ, ikun node Struct. Iżda realizzata fil-lott ta 'kotba u referenzi online, inti tista 'tabilħaqq tara fuq in-naħa l-oħra. Iżda biss jirrealizzaw li kemm fil-fatt se jaħdmu u inti għandek sempliċement tkun konsistenti. Kull dritt. Allura li kien dikjarazzjoni tagħna ta node Struct. Imma allura aħna bdiet tagħmel aktar affarijiet sofistikati. Per eżempju, aħna iddeċieda li jintroduċi xi ħaġa bħal tabella hash. Allura hawnhekk huwa tabella hash tal n daqs, indiċjati minn 0 fuq il-quċċata xellug għal n minus 1 fuq il-qiegħ tax-xellug. Dan jista 'jkun hash tabella għal xejn. Imma liema tipi ta 'affarijiet ma nitkellmu dwar l-użu ta 'tabella hash għall? Kif taħżen liema? Ismijiet. Stajna nagħmlu ismijiet simili għamilna aħħar darba. U tassew, inti jista 'jaħżen xejn. U aħna ser tara dan mill-ġdid fl PHP u JavaScript. A tabella hash huwa tip sbieħ ta 'Swiss Sikkina Armata li tippermetti int taħżen pretty ħafna xi trid ġewwa tal dan billi jassoċjaw ċwievet b'valuri. Keys b'valuri. Issa f'dan il-każ sempliċi, tagħna ċwievet huma biss numri. Aħna qed timplimenta hash tabella bħala firxa. U għalhekk il-keys huma 0, 1, 2, u oħrajn. U hekk aħna, bħala bnedmin, iddeċieda aħħar ġimgħa li inti taf liema, jekk aħna qed ser ismijiet taħżen, ejja biss arbitrarju, iżda pjuttost raġonevolment, jassumu li Alice, isem A, biss se jiġu indiċjati fis 0. U Bob, isem B, se jiġu indiċjati fis 1, u oħrajn. Allura kellna mapping bejn inputs, li huma kordi, u l-hash postijiet, li huma numri. Allura dak il-proċess hija ġeneralment magħrufa bħala funzjoni hash, u inti tista 'verament timplimentah fil-kodiċi. Jekk jien ridt li jimplimenta funzjoni hash li ma eżattament dak li aħna biss deskritta minn aħħar darba, I jista tiddikjara funzjoni li jieħu, bħala input per eżempju - u ejja tagħmel dan fuq dan iskrin hawn fuq. Jekk jien ridt li timplimenta hash funzjoni, I jista 'jgħid xi ħaġa bħal din. Huwa ser jirritorna int. Huwa ser jiġi msejjaħ hash, u huwa ser jaċċetta bħala argument a spag, jew nistgħu nkunu aktar xierqa issa, u jgħidu char *, aħna ser sejħa hija s. U allura dan kollu funzjoni għandha tagħmel, finalment, huwa jirritorna l-int. Issa, kif tagħmlu li jista ma jkunx tant ċara. Jien ser timplimenta din mingħajr ebda forma ta 'żball verifika dritt issa. Jien biss ser addoċċ ngħid, ritorn dak kollu li huwa fil-parentesi s 0, minus, ejja ngħidu, il-kapital A virgola. Totalment imkisser. Huwa mhux perfett għax wieħed, dak li jekk i huwa null? Affarijiet ħżiena huma jiġri. Żewġ, dak li jekk l-ewwel ittra f'dan isem mhuwiex ittra kapitali? Li mhux se jduru out ukoll lanqas. Jista 'jkun ittra lowercase jew mhux ittra fil-livelli kollha. Allura totalment isir sforz akbar, iżda din hija l-idea bażika. Dak li aħna deskritti aħħar ġimgħa verbalment kif biss proċess ta 'immappjar Alice biex 0 u Bob sa 1 jista 'jiġi espress ċertament aktar formulaically bħala C jiffunzjonaw hawn. Imsejħa mill-ġdid hash, tieħu string bħala input, u mbagħad b'xi mod ma xi ħaġa ma 'dak input li jipproduċi output. Mhux b'differenza deskrizzjoni tagħna kaxxa sewda li konna twil isir. I do not know kif dan jista 'jkun taħdem taħt il-barnuża. Għal problema sett 6, waħda mill-isfidi hija għalik li jiddeċiedu liema se funzjoni hash tiegħek tkun? Dak li għaddej biex tkun ġewwa ta 'dik iswed kaxxa, u preżumibbilment, li ser tkun ftit aktar interessanti minn dan, u definittivament aktar suxxettibbli għall-iżbalji verifika minn din partikolari implimentazzjoni. Imma l-problemi jistgħu jinqalgħu, right? Jekk għandna struttura data bħal din waħda, x'hemm waħda mill-problemi inti tista 'taħdem fis maż-żmien kif inti daħħal aktar u aktar ismijiet fil- tabella hash? Ikollok kolliżjonijiet, id-dritt? X'jiġri jekk ikollok Alice u Aaron, żewġ persuni li isimhom ġara biex tibda bil A? Li iqajjem il-kwistjoni, fejn inti tpoġġi t-tieni bħall-isem? Ukoll, inti tista 'naively biss jitqiegħed fejn Bob jappartjeni, iżda mbagħad Bob huwa tip ta 'invitat jekk inti tipprova daħħal l-isem tiegħu li jmiss u hemm l-ebda lok għalih. Allura inti tista 'tpoġġi Bob fejn Charlie huwa, u tista 'timmaġina dan malajr ħafna jiddevolvu fis daqsxejn ta 'mess. Xi ħaġa lineari fl-aħħar, fejn inti biss għandek tfittex l-ħaġa sħiħa tfittex Alice jew Bob jew Aaron jew Charlie. Allura minflok aħna propost, minflok sempliċiment linearment probing għal spazji miftuħa u plopping-ismijiet hemmhekk, aħna pproponiet approċċ fancier. A tabella hash implimentati xorta ma ' firxa ta 'indiċi, iżda t-tip ta' data dawk indiċijiet issa kienu pointers. Pointers għal dak? Pointers għal listi marbuta. Minħabba recall li lista marbut huwa verament ftit pointer għal node, u l-node għandha qasam li jmiss, u li node għandha kamp li jmiss, u oħrajn. Allura inti issa tista 'taħseb dan array fuq in-naħa tax-xellug ta 'tabella hash bħala jwassal għal lista marbuta. Il-vantaġġ ta 'liema hija jekk ikollok ħabta bejn Alice u Aaron, x'tagħmel mal- tieni persuna? Inti biss ehmeż lilu jew tagħha għall- aħħar, jew saħansitra l-bidu ta 'dik il-lista marbuta. U fil-fatt, ejja biss noodle permezz li għal ftit tieni. Fejn jagħmel l-iktar sens? Jekk I daħħal Alice u hi jispiċċa fil l-ewwel post, imbagħad I jippruvaw daħħal l-isem Aaron, u hemm ovvjament ħabta, għandu nressaq lilu fil-bidu tal-lista marbuta? C'est f'dak ewwel post, jew fl-aħħar? UDJENZA: [inaudible]. DAVID Malan: OK. Smajt bidu. Għaliex fil-bidu? UDJENZA: [inaudible]. DAVID Malan: OK. Huwa alfabetika, hekk li sbieħ. Li l-proprjetà tajba. Hija se jiffrankaw me xi żmien potenzjalment. Dan mhux se let me do tfittxija binarja, iżda I jista inqas ikunu jistgħu break out ta 'linja jekk I realizzata, ukoll, jien mod passat kienu Aaron ma jkunx f'din magħżula lista linked. I ma jkollhom l-iskart ħin tiegħi tfittex it-triq kollha sa l-aħħar. Allura dak raġonevoli. Għaliex inkella jista inti tixtieq li daħħal l-isem jaħbtu fl- bidu tal-lista? X'hemm li? UDJENZA: [inaudible]. DAVID Malan: Hija tista 'tieħu żmien twil biex jiksbu l-aħħar tal-lista. U fil-fatt, aktar u aktar. L-ismijiet aktar inti daħħal li tibda bil A, l-itwal li katina hija se tikseb. L-itwal li marbuta lista hija se tikseb. Allura int verament ftit ħela ta 'ħin tiegħek. Forsi int aħjar off żamma ħin tad-dħul kostanti, big O ta '1, billi dejjem tqegħid-isem jaħbtu fi il-bidu tal-lista marbuta, u mhux inkwetanti kemm dwar issortjar. X'inhu l-aħjar risposta? Huwa ċar. Huwa tip ta 'tiddependi fuq dak li l- distribuzzjoni huwa, dak li l-mudell huwa mill-ismijiet inti ddaħħal. Mhuwiex neċessarjament risposta ovvja. Iżda hawn biex, għal darb'oħra, huwa opportunità disinn. Allura aħna mbagħad ħares lejn din il-ħaġa, li huwa verament l-opportunità kbira oħra għal p-set 6. U jirrealizzaw, jekk inti ma jkunux diġà, Ads Zamyla fis kemm ta 'dawn, hash tabelli u tipprova, f'aktar dettall. U l-walkthrough video huwa inkorporati fil-p-set spec. Dan kien trie - T-R-I-E. U dak li kien interessanti dwar dan kienet li l-running time ta 'tiftix għal isem, bħal Maxwell aħħar darba, kien big O ta 'dak? X'hemm li? UDJENZA: In-numru ta 'ittri. DAVID Malan: Numru ta 'ittri. Smajt żewġ affarijiet. Numru ta 'ittri u l-ħin kostanti. Mela ejja jmorru ma 'dak l-ewwel. In-numru ta 'ittri. Ukoll, din l-istruttura tad-data, recall, huwa bħal siġra, siġra tal-familja, li kull wieħed lymph li huma magħmula minn arrays. U dawk arrays huma pointers għal lymph oħra bħal dawn, jew oħra bħal arrays fil-siġra. Hekk jekk ridna li mbagħad tiddetermina jekk Maxwell hija fil hawn, I jista 'jmur għall-ewwel firxa, fuq nett tal- l-siġra, l-għerq hekk imsejħa, quċċata ta ' il-trie, u mbagħad segwi l-pointer m, allura l-pointer a, allura x, w, e, l, l. U mbagħad meta nara xi simbolu speċjali, denotat hawn bħala trijangolu. Fil kodiċi tkun taf tara nipproponu li inti implimentati bħala bool, biss qal iva jew xejn, ta 'kelma jieqaf hawn. Ukoll, ladarba aħna ħadthom marret M-A-X-W-E-L-L, jħoss simili seba, forsi tmienja jekk immorru waħda passat, tmien passi biex isibu Maxwell. Jew ejja sejħa hija K. Imma recall aħħar time, I argumentat li jekk hemm realistikament tul massimu fuq kelma, bħal karattri 40-xi-fard, a tul massimu jimplika valur kostanti. Allura verament, iva, huwa teknikament O big tat-8 jew 7, jew O verament kbir ta 'K. Imma jekk ikun hemm limitu finite dwar liema K jista 'jkun, huwa kostanti. U dan huwa big O ta '1 fil- l-aħħar tal-ġurnata. Mhux fid-dinja reali. Mhux meta inti attwalment tibda jaraw arloġġ tiegħek bħala running program tiegħek. Huwa assolutament se tkun daqsxejn aktar kajman milli verament kostanti ħin ma 'pass wieħed. Huwa ser jkun ta 'seba' jew tmien passi, iżda xorta dan huwa ħafna, ħafna aħjar minn algoritmu bħal big O ta 'n li jiddependi mid-daqs ta 'x'hemm fil- struttura tad-data. Avviż tal-rasu hawnhekk hija li nistgħu daħħal miljun ismijiet aktar fis dan struttura tad-data, imma kif ħafna aktar passi huwa se jieħu magħna biex isibu Maxwell f'dak il-każ? Xejn. Hu affettwat. U sal-lum, ma naħsibx Rajna eżempju ta 'struttura data jew algoritmu li kienet kompletament affettwat mill esterna imgieba bħal dik. Iżda dan ma jistax ikun aqwa. Dan ma jistax ikun l-unika soluzzjoni għall-p-set U mhuwiex. Dan mhuwiex neċessarjament id-data istruttura għandek ixaqilbu, għaliex bħal tabelli hash, tradeoff. X'hemm-prezz li inti tħallas hawn? Memorja. I mean, dan huwa atroċi ammont tal-memorja. U inti ma tistax pjuttost tara hawnhekk għaliex l-awtur ta 'din l-istampa ovvjament maqtugħ kollha tal-arrays, u aħna mhux qed jaraw lottijiet ta 'A u Tal-B u C tal-u l-Q u l-Y u Z f'dawn l-arrays. Iżda dawn qed hemmhekk. Kull wieħed minn dawn lymph huwa firxa sħiħa ta 'xi 26 jew aktar bytes, b'kull wieħed minn li jirrappreżenta ittra. 27 fil-każ tagħna, sabiex inkunu nistgħu appoġġ apostrophes fil-problema sett. Allura din l-istruttura tad-data huwa verament, verament dens u wiesa '. U li waħdu jista 'jispiċċa jonqos affarijiet isfel, jew għall-inqas jiswew inti spazju ħafna aktar. Iżda għal darb'oħra, nistgħu tiġbed paraguni hawn. Recall ftit lura, ksibna ħafna żmien aktar eċċitanti running fl-għażla meta nużaw tip jingħaqdu, imma l-prezz aħna mħallsa biex tinkiseb n log n għall jingħaqdu sort meħtieġ li aħna jonfqu aktar dak riżorsa? Aktar spazju. Għandna bżonn firxa sekondarja li kopja nies fi, bħad għamilna hawn fuq il-palk. Għalhekk għal darb'oħra, l-ebda rebbieħa ċari, iżda biss disinn suġġettiva deċiżjonijiet li jridu jittieħdu. Kull dritt. Allura kif dwar dan? Kulħadd jirrikonoxxu li D-Hall? OK. Allura tlieta minna. Mather House. Allura dan huwa għall dining Mather tal. I ser bet l-swali dining jkollhom munzelli ta 'dixxijiet bħal dan. U dan huwa attwalment rappreżentattiv ta 'xi ħaġa konna ovvjament jidher diġà. Aħna hija imsejħa litteralment munzell. U l-munzell, f'termini ta 'tiegħek memorja tal-kompjuter, huwa fejn tmur data filwaqt funzjonijiet qed ikunu msejjħa. Per eżempju, liema tipi ta 'affarijiet imorru fuq il-munzell rigward il- tqassim memorja konna diskussi fil-ġimgħat li għaddew? X'hemm li? UDJENZA: Sejħiet għall-funzjonijiet. DAVID Malan: Jien sorry. UDJENZA: Sejħiet għall-funzjonijiet. DAVID Malan: Sejħiet għall-funzjonijiet, iżda speċifikament, x'hemm ġewwa ta 'kull dawk frames? Liema tip ta 'affarijiet? Yeah. Allura varjazzjonijiet lokali. Ghaċ aħna għandna bżonn ftit ħażna lokali, bħal argument, jew int I, jew int temperatura, jew kull lokali varjabbli, aħna kont qed tpoġġija ta 'dak fuq il-munzell. U aħna sejħa hija ta 'ċumnija minħabba ta 'dik l-idea saffi. Just tip ta 'logħbiet up mar-realtà, il-kunċett tiegħu. Iżda jirriżulta li munzell jistgħu wkoll titqies bħala struttura data, l- alternattiva għal firxa, alternattiva għal lista marbuta. Xi ħaġa kunċettwalment aktar interessanti li xorta tista 'tkun implimentata bl-użu jew ta 'dawk affarijiet, imma hija tip differenti ta ' struttura tad-data ta 'sostenn, verament, biss żewġ operazzjonijiet. Iżda int tista 'żżid fuq fancier karatteristiċi minn dawn. Iżda dawn huma l-baŜi - timbotta u pop. U l-idea ma 'munzell hija li jekk jien jkollhom hawn, bi jew mingħajr Annenberg jafu, trej minn bieb li jmiss bin-numru 9 fuq dan. Allura biss int. U nixtieq li timbotta din fuq id-dejta istruttura, li bħalissa hija vojta. Ikkunsidra dan il-qiegħ tal-munzell. Nixtieq push dan in-numru 9 fuq il- munzell, u issa huwa hemm dritt. Imma l-ħaġa interessanti dwar munzell hija li jekk jien issa tixtieq li timbotta xi valur, bħall 17, u I imbotta dan fuq il-munzell, jien ser tagħmel l-unika ħaġa intuwittivi, jien biss ser biex tpoġġi dan id-dritt fejn aħna bnedmin ikunu inklinati li tqiegħed lilha, fuq nett. Imma x'hemm interessanti issa hija, kif nista 'nikseb fuq 9? You know, I do mhux mingħajr xi sforz. Allura x'hemm interessanti dwar munzell huwa li permezz tad-disinn, huwa struttura data LIFO. Mod iblah li jiddeskrivu aħħar, l-ewwel out. Allura l-aħħar numru fis f'dan il-ħin kien 17. Mela jekk jien tixtieq li pop xi ħaġa off tal-munzell, jista 'jkun biss 17. Allura hemm ordni obbligatorja ta ' operazzjonijiet hawn, fejn l-aħħar oġġett fl għandu jkun l-ewwel wieħed out. Għalhekk l-akronimu, LIFO. Allura għaliex jista 'dan jiġi utli? Huma kuntesti tagħhom li youd tixtieq struttura data bħal din? Ukoll, huwa ċertament kien utli ġewwa ta 'kompjuter. Sistemi tantx jaħdmu jużaw dan b'mod ċar tip ta 'struttura tad-data għall stacks. Aħna ser tara wkoll l-istess idea meta niġu għall-paġni web. Allura din il-ġimgħa u ġimgħa d-dieħla u lil hinn, u kif inti tibda timplimenta web paġni f'lingwa msejħa HTML, inti tista ' attwalment jużaw struttura data bħal dan biex jiddeterminaw jekk il-paġna huwa formattjati b'mod korrett. Għaliex aħna ser tara l-paġni web jsegwu speċi ta 'ġerarkija, indentazzjoni li se, fl-aħħar tal-ġurnata, ikun struttura ta 'siġra taħt il-barnuża. Allura aktar fuq li fi ftit ftit. Iżda għal issa, ejja suġġeriti għal mument, kif nistgħu tmur dwar li jirrappreżenta dak munzell hu? Let me tipproponi li nimplimentaw munzell bil-kodiċi bħal dan. Allura munzell hu ser ikollhom ġewwa ta 'dan żewġ affarijiet, l-firxa, imsejħa trejs, biss sabiex ikunu konsistenti mal-demo. U kull wieħed mill-oġġetti f'dak array se tkun int tip. U l-kapaċità x'aktarx li huwa dak? Għaliex stajt ma jkunx miktub il- definizzjoni sħiħa hawn. Huwa probabbilment l-massimu daqs tal-array. U huwa probabbilment ddikjarat bħala sharp jiddefinixxu fil-quċċata tal-fajl, xi tip ta 'kostanti kif implikat is-sempliċi kapitalizzazzjoni. Allura x'imkien saħħa hija definita id-daqs massimu possibbli. Sadanittant, ġewwa tal-istruttura tad-data magħrufa bħala munzell se jkun hemm tkun numru sħiħ biss magħrufa sempliċement bħala daqs. Mela jekk jien kienu jirrappreżentaw dan issa pictorially, ejja nassumu li din kaxxa s-sewda kollu jirrappreżenta munzell tiegħi. Ġewwa ta 'dan huwa ta' żewġ varjabbli. Hekk jien ser tiġbed l- ewwel wieħed bħala daqs. U t-tieni waħda jien ser biex tiġbed bħala firxa. Iżda biss li żżomm affarijiet ordnat, normalment I jiġbed firxa bħal dan, iżda dan l-xorta ta 'sbieħ jekk aħna logħba realtà, jew jaqblu mal-mudell mentali. So let me minflok jiġbed l-array vertikalment, li huwa biss, għal darb'oħra, konsenja artist. Ma verament kwistjoni dak li huwa taħt il-barnuża. U aħna ser ngħidu li, awtomatikament, kapaċità se tkun tlieta. Allura dan se jkun post 0, dan se jkun post 1, dan se jkun post 2. Jekk I jixtru bil-ballun stress, kieku xi ħadd jixtieq li toħroġ u tmexxi l- jitla 'abbord hawn għal ftit mument? OK, raw idejn tiegħek l-ewwel. Come fuq up. Kull dritt. So I jemmnu li huwa Steven. Come fuq up. Kull dritt. Imma jissoponi issa aħna Rewind għall-bidu istat tad-dinja fejn I għadek iddikjarat munzell, u huwa se jkun ta 'kapaċità tlieta. Iżda d-daqs għadu ma ġiex determinat. Trays għadu ma ġiex determinat. Allura koppja ta 'mistoqsijiet ewwel. U let me jagħtuk mic sabiex inti tista ' ikollhom sehem aktar attiv f'dan. Allura dak li hu ġewwa ta 'daqs f'dan il-mument fil-ħin jekk I kollha għamlu huwa iddikjarata munzell ma linja waħda tal-kodiċi? STEVEN: Mhux ħafna. DAVID Malan: OK, mhux wisq. Nafu x'hemm ġewwa ta 'daqs, nafu x'hemm ġewwa ta 'dan array hawn? STEVEN: kodiċi Just każwali, right? Just - DAVID Malan: Yeah, jien ser sejħa hija kodiċi, iżda każwali - STEVEN: Things. DAVID Malan: Affarijiet simili każwali STEVEN: Bits. DAVID Malan: Bits, right? Allura valuri taż-żibel, id-dritt? Allura permutazzjonijiet ta 'l-0 u 1 ta. Fdalijiet ta 'użanzi ta' qabel ta 'dan il-memorja. U aħna ma verament jafu liema l-valuri huma, hekk aħna tipikament tiġbed minnhom bħala trade marks in kwistjoni. Allura l-ewwel ħaġa li għandna qed preżumibbilment tmur jridu nagħmlu hawnhekk - u let me jagħtu f'dan il-qasam ġewwa li jkun hemm l-isem - trays. X'għandu aħna preżumibbilment initialize daqs għal jekk irridu tibda tuża din munzell? STEVEN: Tray huwa sub 3. DAVID Malan: Allura, OK. Biex ikunu ċari, il-kapaċità hija dikjarata f'postijiet oħra kif tlieta. U dan huwa dak li stajt użati li jallokaw l-array. Daqs se jirreferu għal kemm trejs huma bħalissa fuq il-munzell. STEVEN: Zero. DAVID Malan: Għalhekk għandu jkun żero. Allura aqbad, u ma 'kwalunkwe finger, jiġbed żero fid-daqs. Kull dritt. Allura issa, x'hemm ġewwa ta 'dan hawn, ma nafux. Dawn huma verament valuri taż-żibel biss. Allura aħna jista 'jiġbed trade marks in kwistjoni, iżda ejja iżommu l-bord nadif għal issa għaliex ma jimpurtax x'hemm hemmhekk. Aħna ma bżonn li initialize-firxa għal xejn, għaliex jekk aħna nafu li id-daqs tal-munzell huwa żero, ukoll, aħna m'għandhomx ikunu tħares lejn xejn fil din array xorta waħda fuq dan il-punt fil-ħin. Allura issa I jissoponi li timbotta l- numru 9 fuq il-munzell. Kif nistgħu taġġorna l-istruttura tad-data ġewwa ta 'din il-kaxxa sewda? Dak valuri bżonn għall-bidla? STEVEN: Fi - id-daqs? DAVID Malan: OK. Daqs għandu jsir dak? STEVEN: Daqs tkun waħda. DAVID Malan: OK. Allura daqs għandha ssir waħda. Allura inti tista 'tagħmel dan fil-modi koppja. Ħalli nagħtikom, issa tiegħek saba huwa Eraser. Kull dritt. Allura issa finger tiegħek huwa brush. Kull dritt. U issa x'iktar għandha tinbidel, ovvjament, fl-istruttura tad-data? STEVEN: Aħna qed tmur minn bottom up sa 9. DAVID Malan: 9. OK, Good. Allura xorta ma jimpurtax x'hemm fuq post wieħed jew tnejn għaliex qed Valuri taż-żibel, imma aħna ma għandhom jolqot tfittex hemmhekk minħabba d-daqs huwa tgħidilna li biss l-ewwel element huwa attwalment leġittimu. Allura issa I imbotta 17 fuq il-lista. X'jiġri din l-istampa? STEVEN: Allura daqs huwa se jmorru għal tnejn. DAVID Malan: OK. Inti Eraser - oops. Int Eraser. STEVEN: Eraser. DAVID Malan: Inti brush. STEVEN: xkupilja. DAVID Malan: OK. U x'iktar? STEVEN: U allura aħna - DAVID Malan: Aħna imbuttat 17. STEVEN: Aħna nimxu 17 fuq, hekk - DAVID Malan: OK, tajba. STEVEN: - qatra l-isfel. DAVID Malan: Kull dritt. Huwa jkollna faċli. Jien ma jmur biex jgħinek dan iż-żmien. Imbotta 22. STEVEN: Magħmul. Issir Eraser. Jien issir brush. U mbagħad I am tqegħid 22. DAVID Malan: 22. Eċċellenti. Allura wieħed aktar ħin. Jien issa ser timbotta fuq il-munzell 26. STEVEN: Ooh. Oh gosh. Int verament maqbuda me off guard. DAVID Malan: Inti ma tara dan ġejjin? STEVEN: I ma tara dan ġejjin. Nistgħu kapaċità jerġgħu inizjali? DAVID Malan: Dik hija mistoqsija tajba. Allura konna tip ta 'miżbugħa nfusna fil-kantuniera hawn. M'hemm l-ebda verament out tajba għall Steven għaliex aħna ħadthom allokat dan array statikament, biex ngħidu hekk, ġewwa tal-istruttura tad-data. U konna essenzjalment hard kodifikati li jkun ta 'daqs tlieta. Allura ma nistgħux verament jallokah. Nistgħu jekk aħna marru lura fi, aħna definiti mill-ġdid trejs li tkun pointer li aħna mbagħad jużaw malloc għall-memorja idejn biex. Għaliex jekk aħna ltqajna l-memorja minn -munzell permezz malloc, aħna allura tista 'jeħles minnu. Iżda qabel ħelsien dan, nistgħu jirriallokaw blokki akbar ta 'memorja, taġġorna l-pointer, u oħrajn. Iżda għal issa, dan huwa verament l-aħjar li nistgħu nagħmlu. Imbotta u pop huma preżumibbilment tmur li jkollhom mmarkati xi żball. Allura per eżempju, l-implimentazzjoni tagħna ta 'push tista tirritorna bool li lura qabel vera, vera, vera. Iżda l-raba 'darba, li għaddej biex ikollhom li jirritornaw foloz, per eżempju. Kull dritt. Ħafna isir ukoll. Prosit. You ħadthom qalgħu ballun stress tiegħek illum. [Applause] STEVEN: Grazzi. DAVID Malan: Grazzi. OK, sabiex dan jidher li mhux wisq ta 'pass' il quddiem, id-dritt? Aħna deskritti din l-istruttura tad-data. Huwa kien konvinċenti, right? Sistemi operattivi bhalu. Apparentement il-web tista 'tagħmel użu ta' dan, u applikazzjonijiet oħra għadhom. Imma dak limitazzjoni stupid li aħna qed lura għall tip ta 'ġimgħa żewġ limiti fejn għandna fissi arrays daqs. Allura hemm tabilħaqq huma koppja ta ' modi nistgħu issolvi din. Nistgħu dinamikament jallokaw il-firxa, mhux billi hard kodifika bħala stajt jsir hawn, iżda minflok li tiddikjara mill-ġdid dan, biss li tkun ċara, kif xi ħaġa bħal din. Int * trejs, mhux deċiż fuq kapaċità s'issa. Imma meta I jiddikjara l-munzell x'imkien ieħor fil-kodiċi tiegħi, I jistgħu mbagħad is-sejħa malloc, jiksbu l-indirizz ta 'blokki ta' memorja, u I jistgħu jassenjaw dak l-indirizz għall-trejs. U mbagħad, għaliex huwa biss blokki ta ' memorja, I jistgħu jkomplu jużaw kwadri notazzjoni bracket bil-mod normali. Minħabba darb'oħra, hemm tip ta 'dan ekwivalenti funzjonali ta 'arrays u biċċiet ta 'memorja li ġejjin lura mill malloc. Nistgħu jittrattaw lil bħall-oħra użu aritmetika pointer jew notazzjoni bracket kwadru. Allura dak l-approċċ wieħed. Imma kif inkella jista nimplimentaw dan struttura tad-data istess, potenzjalment? Dritt? Inħoss bħal aħna biss solvuta din problema bħal ġimgħa ilu. Liema kienet l-soluzzjoni għal din il-problema li Steven dam fis? Listi Allura marbuta, id-dritt. Jekk il-problema hija li aħna qed pittura lilna nfusna fis-kantuniera billi jallokaw bil-quddiem memorja ftit wisq li aħna mbagħad ikollhom li b'xi mod jittrattaw, ukoll, għaliex mhux biss evitat li joħroġ għal kollox? Għaliex mhux biss tiddikjara trejs biex tkun pointer għal node, ergo lista marbuta, u mbagħad sempliċement talloka lymph ġodda kull darba Steven meħtieġ biex jitwaħħal numru fl-istruttura tad-data. Allura l-istampa jkollha għall-bidla. Huwa mhux ser tkun nadifa u bħala sempliċi kemm biss firxa ta 'tliet ints. Issa li għaddej biex tkun pointer għal Struct, u li Struct se ikollhom int u werrej li jmiss. Huwa ser twassal permezz ta 'dak pointer li Struct ieħor tali Struct oħra bħal din. Allura l-istampa fil-fatt jiksbu Messier daqsxejn. U aħna'd jkollhom vleġeġ irbit kollox flimkien. Iżda li l-multa, id-dritt, għaliex Rajna kif għandek tagħmel dan. U ladarba inti tikseb komda xi ħaġa implimentazzjoni bħal linked lista, li inti ser ikollok tagħmel jekk inti jagħżlu li jimplimentaw tabella hash ma chaining separata għal p-set 6, inti tista ' jużawha bħala blokk bini, jew ingredjent, jew Scratch jitkellmu, a proċedura, xi ħaġa li inti tpoġġi, inti maħluqa biċċa tiegħek puzzle stess li inti tista 'mbagħad użu mill-ġdid. Kompromessi hekk, imma soluzzjonijiet potenzjali li konna fil-fatt rajna qabel. Allura ħafna drabi, inti tara dan kull sena jew tnejn meta rilaxxi Apple xi ħaġa ġdida, u l-poplu crazy line up barra tal-Apple taħżen jixtru marġinali tagħhom upgrade fuq il-hardware. Jien ngħid dan, huwa OK, għaliex Jiena wieħed minn dawk in-nies. Allura liema tip ta 'struttura data jafu jirrappreżentaw din ir-realtà? Well, ejja sejħa hija ta 'kju, linja. Allura British sejħa hija tipikament kju xorta, dan huwa isem sbieħ. U ż-żewġ operazzjonijiet li kju għandha tappoġġa aħna ser sejħa enqueue operazzjoni u operazzjoni dequeue, li huma simili fil- ispirtu biex timbotta u pop. Huwa biss tip ta 'differenti konvenzjoni, dak li aħna qed titlob dawn. Iżda biex enqueue xi ħaġa mezzi biex iżżid jew daħħal għall-istruttura tad-data. Biex dequeue mezzi biex tneħħiha. Iżda billi munzell kien data LIFO istruttura, kju hija l-ewwel fi, ewwel out istruttura tad-data. Jekk inti l-ewwel persuna fil-linja, inti se tkun l-ewwel persuna li tikseb barra tal-linja u jixtru tagħmir ġdid tiegħek. Immaġina kif mqalleb dawn in-nies ikunu jekk Apple minflok tintuża 'ċumnija, għal Pereżempju, biex jimplimentaw il-picking up ta 'ġugarell ġdida tiegħek. Allura kjuwijiet jagħmel sens, ċertament, u nistgħu naħsbu ta 'kull xorta ta' applikazzjonijiet, preżumibbilment, għal kjuwijiet, speċjalment meta inti tixtieq ġustizzja. Allura kif tista 'nimplimentaw dawn bħala struttura data? Well, nipproponi li aħna jistgħu bżonn tagħmel dan il-mod. Hekk jien ser issa għandhom numri. Allura aħna ser jżommha sempliċi u mhux neċessarjament jitkellmu f'termini ta 'dixxijiet. Just numri li n-nies ta gotten. Kapaċità se, għal darb'oħra, tiffissa l- numru totali ta 'nies li jistgħu jkunu fil- din il-linja, bħala tlieta jew x'ikun oħra valur. Imma jiena nipproponi li għandi bżonn li jżommu rekord mhux biss tad-daqs tal- kju, affarijiet kemm huma fiha. Allura daqs huwa d-daqs attwali, il-kapaċità huwa d-daqs massimu. Just mill-ġdid, in-nomenklatura minn konvenzjoni. Għaliex għandi bżonn int addizzjonali ġewwa ta 'kju biex iżżomm kont ta' min huwa fil- quddiem tal-linja? Għaliex għandi bżonn li tagħmel dan f'dan il-każ? Well, kif huwa din l-istampa se jibdlu? I tista 'probabbilment użu mill-ġdid aktar ta 'din l-istampa. Let me imorru quddiem u tħassar x'hemm hawn. Aħna ser tagħti dan ftit isem differenti up here. Ejja jeħles mill-17, ejja jeħles tal-9, ejja jeħles mill-3. U ejja żid ħaġa waħda oħra. Nipproponi li għandi bżonn biex iżżomm kont ta ' quddiem tal-lista, li huwa biss se tkun int ukoll. U aħna qed tmur biex jżommha sempliċi. Nru lista marbuta għal issa. Aħna ser jammettu li aħna qed tmur biex bump up kontra dan il-limitu. Imma dak li nixtieq li tara jiġri dan iż-żmien? So I jissoponi aqbad u l-ewwel persuna tkun fil-linja, u huwa n-numru 9. We do jkollhom blalen istress. Nista steal, ngħidu aħna, tnejn jew tliet persuni? Wieħed, tnejn, tlieta? Come fuq up. Dritt minn quddiem, għaliex aħna ser jagħmlu dan wieħed malajr. Kull wieħed inti issa se tkun tifel fan fil-linja fil Apple. Inti mhux se jkun jirċievu Apple hardware fl-aħħar ta 'dan għalkemm. Kull dritt. Allura int numru 9, int numru 17, numru 22. Dawn huma numri arbitrarji, bħal student IDs jew whatnot. U fi ftit mument, ejja tibda biex tibda żżid affarijiet. U jien ser imexxu l-bord hawn dan iż-żmien. Allura f'dan il-każ, stajt initialized quddiem li tkun - I attwalment ma verament kura dak l- quddiem huwa, minħabba d-daqs huwa żero. Allura dan tista 'ukoll biss tkun kwistjoni mark. Dawn huma kollha trade marks in kwistjoni. Allura issa aħna ser tibda attwalment tara xi nies lining up fil-maħżen. Mela jekk numru 9, int l-ewwel waħda hemm fil 5:00, imorru quddiem u line up, jew il-lejl ta 'qabel. OK. Allura issa 9 huwa hawnhekk. Allura 9 huwa quddiem tal-lista. Hekk jien ser jimxi 'l quddiem u taġġorna id-daqs ta din id-data attwali istruttura li ma jkunux 0 jibqgħalu, iżda li tkun 1. Jien ser tpoġġi 9 fil- quddiem tal-lista. Let me imorru quddiem u toggle l-iskrin hekk nistgħu naraw passat us hawn. U issa dak li nixtieq biex fuq quddiem? Jien ser iżommu kont li l- quddiem tal-kju dritt issa huwa fil-post 0. Għaliex dak li hu jmiss jiġri? Ukoll, ejja ngħidu issa I enqueue 17 ukoll. Allura ħops fil-linja hemmhekk. U għal darb'oħra, il-tip ta bieb għall- maħżen se jkun hawn. Allura issa stajt miżjud 17. U anki jekk dawn guys huma imblukkar l-iskrin, li OK, għaliex nistgħu naraw it up here. Jiddispjacini. UDJENZA: Nistgħu jiċċaqalqu - DAVID Malan: Le, li OK. Huwa enormi up hemm. Allura 17 issa huwa ġewwa tal-kju. I bżonn jaġġornaw li oqsma issa għalkemm? OK, definittivament daqs. U kif madwar quddiem? OK, l-ebda. Front m'għandux jinbidel, għax b'differenza munzell, aħna tixtieq li tinżamm l-ġustizzja. Mela jekk 9 daħal fl-ewwel, irridu 9 tkun l-ewwel barra tal-linja u fil-maħżen. Fil-fatt, ejja ara dak. Qabel ma aħna daħħal 22, ejja imorru quddiem u dequeue 9. X'hemm isem tiegħek mill-ġdid? UDJENZA: Jake. DAVID Malan: Jake se li għandha dequeued issa. Allura ikollok biex jimxu fil-maħżen. U nippretendu li l-maħżen huwa hemmhekk. Allura issa dak li jeħtieġ - dit-dit-dit! Dak li jeħtieġ li jiġri issa? Deċiżjoni disinn. Allura mhux istint ħażina, iżda - dak l-isem tiegħek mill-ġdid? UDJENZA: David. DAVID Malan: David. Allura dak li ma David tagħmel? Huwa kien qed jipprova biex issolvi tad tiffissa d-data istruttura u jimxu minn post tiegħu fis lokalità preċedenti Jake. U li l-multa jekk aħna qed lesti li jaċċetta li bħala dettall implimentazzjoni. Iżda l-ewwel, ejja jaġġornaw l-informazzjoni istruttura qabel nagħmlu dan. Għaliex jien ma Predisposizzjoni l-idea ta 'kulħadd il-poplu ċaqliq fil-linja. Huwa no big deal jekk David ma dan ma pass wieħed, iżda għal darb'oħra, jaħsbu lura meta aħna kellna tmien voluntiera fuq l- istadju u aħna ghamilt like inserzjoni sort, fejn kellna biex tibda jiċċaqalqu kulħadd madwar. Li ltqajna għaljin, right? Li jagħmel me cringe dwar big O ta 'ln, big O ta' n kwadrat mill-ġdid. Mhuwiex sensazzjoni bħal riżultat ideali. Mela ejja taġġorna dan biss. Allura l-daqs tal-kju m'għadux 2. Huwa issa sempliċiment 1. Imma I issa tista 'taġġorna xi ħaġa I ma taġġorna qabel, il- quddiem tal-lista. I tista 'biss jgħidu, huwa li post 1? Allura issa għandna valur żibel hawn, valur żibel hawn, u David fil- nofs ta 'dan żibel. Iżda l-istruttura tad-data hija għadhom intatti. U fil-fatt, jien ma anki ħtieġa li jibdlu n-numru ex Jake 9, minħabba quién. I jkollhom biżżejjed informazzjoni issa fil- daqs li naf hemm persuna waħda dan kju. U naf li dik il-persuna huwa fil-post 1, ma 0. Jien ma tingħadd. Allura 1 ukoll. Allura l-istruttura tad-data għadu OK. Ukoll, dak li jiġri li jmiss? Ejja enqueue - dak l-isem tiegħek? UDJENZA: Callen. DAVID Malan: Callen. Ejja enqueue a Callen, u 22 issa hija fil-kju. Allura issa dak li għandu jinbidel hawn? Front mhux se bidla, ovvjament. Id-daqs huwa se jibdlu li jkun 2 għal darb'oħra. U 22 jispiċċa hawn, 9 għadu preżenti, imma hija effettivament valur żibel issa. Huwa biss fdal ta 'Jake passat. Allura issa x'jiġri jekk I dequeue David? Waħda mill-aħħar operazzjoni, dequeue David. Aħna jista 'jċaqlaq, imma jiena nipproponi ejja do bħala xogħol inqas possibbli. Issa struttura tad-data tiegħi tmur lura fid-daqs 2-1. Iżda l-quddiem tal-kju issa jsir 2. I m'għandhomx bżonn li tibdel dawn in-numri għadha biss, għaliex qed Valuri taż-żibel biss. Imma issa x'jiġri? Ejja ngħidu I enqueue myself, 26? Inħoss bħal I jappartjenu hawn fuq. Hekk jien qed enqueued. So I tip ta jappartjenu hawn. U anki jekk inti ma pjuttost japprezzaw dan viżwalment fuq il-palk, għaliex għandna ħafna spazju, I għandhom ma tkun wieqfa hawn, għaliex? UDJENZA: Inti barra mill-limiti. DAVID Malan: Dritt. Jien minn limiti. Stajt indiċjati lil hinn mill- limiti ta 'din array. I really għandhom ikunu f'wieħed mill- tliet postijiet possibbli. Issa, fejn l-aktar naturali biex tmur? Nipproponi aħna leveraged ġimgħa trick waħda. L-operatur mod, persentaġġ. Għaliex jien teknikament wieqfa fil post 3, iżda I do kapaċità mod 3, hekk 3, sinjal fil-mija, 3 - kapaċità għamilhom 3. X'hemm li? X'hemm l-bqija meta inti jaqsam 3 minn 3? 0. Allura li tpoġġi me Jake kienu kienet, li huwa attwalment tajba. Allura issa l-implimentazzjoni ta 'dan il-ħaġa li għaddej biex tkun daqsxejn ta 'ras. Huwa tassew biss linja waħda uġigħ ta 'ras, tal-kodiċi. Imma l-anqas issa hemm żibel valur hawn, iżda hemm żewġ ints leġittimi hawn. U jien jsostnu li issa għamilna eżattament dak li għandna bżonn biex jagħmlu dan sakemm nagħmlu l-bidla dak tal Jake valur kellha tkun 26. Issa għandna biżżejjed tagħrif li għadu biex tinżamm l-integrità ta 'din l-istruttura tad-data. Aħna qed għadhom tip ta 'minn xortih meta aħna tixtieq li daħħal erba 'jew aktar total elementi, iżda nista 'mill-anqas tagħmel pretty użu effiċjenti ta 'din il-kostanti żmien, fil-fatt. I ma jkollhomx għalfejn tinkwieta dwar ċaqliq kulħadd, kif inklinazzjoni David kien. Kwalunkwe mistoqsijiet dwar stacks, jew dan kju? UDJENZA: Huwa r-raġuni għaliex għandek bżonn daqs sabiex inti tkun taf fejn jkollha persuna? DAVID Malan: Eżattament. I bżonn ikunu jafu l-daqs tal-array minħabba I bżonn tkun taf eżattament kif ħafna minn dawn il-valuri huma leġittimi, u hekk li nista 'nsib fejn jitqiegħdu il-persuna li jmiss. Eżattament. Id-daqs huwa - attwalment, aħna ma jaġġornaw din s'issa. I miżjuda myself fuq 26. Id-daqs huwa issa, mhux 1, iżda 2. Allura issa dan tabilħaqq jgħin lili isibu l- kap tal-lista, li mhix 0, mhux 1, iżda huwa 2. Il-faċċata tal-lista huwa tabilħaqq numru 22. Minħabba li huwa daħal fl-ewwel, hekk hu għandu jitħallew fil-maħżen qabel me, anki jekk viżwalment jien wieqfa eqreb lejn il-maħżen. Kull dritt? A rawnd ta 'applause għal dawn guys u aħna ser ħallihom minn hemmhekk. [Applause] DAVID Malan: I tista let inti żżomm il-trej. Nistgħu naraw x'jiġri jekk trid, imma forsi le. Kull dritt. Allura dak li issa ma dan il-leave us? Well, let me tipproponi li hemm ftit strutturi oħra ta 'data nistgħu tibda żżid li kit għodda tagħna li se attwalment jiġi pjuttost, pjuttost rilevanti kif aħna adsa fis Jittieħed web. Li għal darb'oħra, għandu xi tip ta 'konnessjoni siġar fil-forma ta ' xi ħaġa imsejħa DOM, dokument mudell oġġett. Iżda aħna ser tara aktar ta ' li qabel twil. Let me tipproponi definitionally li aħna sejħa siġra issa dak li inti tista 'taf kif aktar ta 'siġra tal-familja, fejn inti jkollhom xi antenat fil- għeruq tas-siġra. A matriarch patrijarkali jew fi nett ta 'l-siġra. Mingħajr konjuġi tagħhom, f'dan il-każ. Imma issa għandna dak li aħna ser sejħa tfal, li huma lymph li hang off-tfal tax-xellug jew il-wild dritt, vleġeġ kif muri hawn. Fi kliem ieħor, fi struttura data siġra fil-kompjuter, siġra għandha żero jew aktar nodes. Jekk ikun node mill-inqas wieħed, li sejjaħ l-għerq. Hu l-affarijiet viżwalment li aħna tiġbed fil-quċċata. U li node, bħal kull node oħra, tista ' jkollhom żero, wieħed, jew tnejn, jew tlieta, jew ħafna tfal madankollu l- struttura tad-data jappoġġja. F'dan il-każ, l-għerq, il-ħażna tal- valur wieħed, għandu żewġt itfal, 2 u 3, hekk aħna ġeneralment sejħa 2-xellug tfal u 3-tfal dritt. U allura meta aħna tikseb sa 5, 6, u 7, 6 tista 'tissejjaħ il-wild nofs. Jekk għandek erbat itfal, jiġrilha konfużjoni. Allura aħna tieqaf tuża dak it-tip ta 'shortcut verbalment. Imma huwa verament ftit siġra tal-familja. U l-weraq hawn huma l-lymph li infushom ikollhom l-ebda tfal. Huma hang off-qiegħ tas-siġra. Allura kif tista 'nimplimentaw siġra li għandha biss żewġ tfal maximally? Aħna ser sejħa hija siġra binarju. Bi darb'oħra jfisser tnejn, f'dan każ, bħal ma binarja. U hekk dan jista 'jkollu żero, wieħed, jew żewġt itfal maximally. I ser nipproponi li nimplimentaw l-node għal dik l-istruttura ma 'n int, u allura żewġ pointers, wieħed imsejjaħ xellug, wieħed imsejjaħ dritt. Iżda dawn huma biss sbieħ konvenzjonijiet arbitrarji. U x'hemm sbieħ issa, speċjalment jekk inti tip ta 'tħabtu kunċettwalment ma recursion, jew ħasbu li ma kienx verament soluzzjoni għal xejn, speċjalment jekk inti tista ' jispiċċaw tal-memorja. Issa li aħna qed jitkellem dwar data istrutturi u algoritmi li jippermettu ahna travers u timmanipula minnhom, Jirriżulta li recursion taqa 'lura fil- ħafna aktar konvinċenti jekk mhux mod sabiħ. Allura dan nipproponi huwa l-implimentazzjoni ta 'funzjoni Search. Minħabba żewġ inputs - sabiex jaħsbu ta 'dan bħala kaxxa sewda. Minħabba żewġ inputs, n, int, u pointer għal siġra, a pointer għal node, jew verament l-għerq ta 'siġra, I pretensjoni li din il-funzjoni tista 'ritorn vera jew falza, li l-valur n huwa ġewwa ta 'din is-siġra. X'hemm ġewwa ta 'din il-kaxxa sewda? Ukoll, erba 'fergħat. L-ewwel biss kontrolli. Jekk siġra huwa null, biss ritorn foloz. Jekk hemm l-ebda node, hemm ebda n, hemm l-ebda numru, biss ritorn foloz. Jekk għalkemm, n, il-valur li qed tfittex għal, huwa inqas minn siġra vleġġa n, u biss li jkun ċar, dak ma jfisser meta I jiktbu siġra u allura l-vleġġa notazzjoni, n? Eżattament. Dan ifisser li dereference pointer imsejħa siġra. Jmorru hemm, u mbagħad jiksbu ġewwa ta 'dan node u jiksbu qasam tagħha imsejħa n. U mbagħad iqabbel ir-n attwali li kien għadda fis Fittex kontriha. Mela jekk n huwa inqas minn, il-valur n fil-node siġra nnifisha, ukoll, dak ma jfisser? Dan ifisser xejn ewwel daqqa t'għajn. Dritt? Eżatt bħal meta jkollok firxa ta ' il-valuri, inti tista 'tixtieq tapplika binarju tfittxija bħala forma ta 'qasma u conquer. Imma dak suppożizzjoni ma hemm bżonn li nagħmlu għal tfittxija binarja li jaħdmu fil-livelli kollha fil-ktieb tat-telefon u eżempji preċedenti? Kif jiġu magħżula. Mela ejja tirfina d-definizzjoni ta 'siġra hawn mhux biex tkun biss siġra, li jista ' jkollhom kwalunkwe numru ta 'tfal. Mhux biss siġra binarju, li jista ' għandhom 0, 1, 2 jew maximally. Iżda bħala siġra tfittxija binarju, jew BST, li huwa biss mod fancy ta 'tgħid a siġra binarju tali li kull node tal tifel xellug, jekk preżenti, huwa inqas mill-node. U tat-tfal kull node id-dritt, jekk preżenti, huwa akbar mill-node innifsu. Allura fi kliem ieħor, jekk ġejt biex tiġbed l-out siġra, kollha tal-numri huma bbilanċjati bir-reqqa bħal dan hekk li jekk għandek 55 bħala l-għerq, 33 tista 'tmur għax-xellug tagħha għaliex dan huwa inqas minn 55. 77 tista 'tmur dritt tagħha minħabba huwa akbar minn 55. Imma issa avviż, l-istess definizzjoni, huwa definizzjoni rikursivi verbalment, għandu japplika għal 33. Child Left 33 trid tkun inqas minn dan, u tat-tfal dritt 33, l-44, għandu jkun akbar minn dan. Allura dan huwa siġra tfittxija binarju, u Nipproponi, bl-użu ftit tal- recursion, nistgħu issa jsibu n. Mela jekk n huwa inqas mill-valur n li l- node attwali, jien se jmorru quddiem u Punt, biex ngħidu hekk, u biss ritorn ikun x'ikun l-tweġiba hija ta ' tiftix għal n fuq il- Child Left siġar. Avviż mill-ġdid, din il-funzjoni biss jistenna stilla node, a pointer għal node. Allura żgur I tista 'biss tagħmel siġra vleġġa xellug, li se jwassal me node ieħor. Imma dak hu li node? Ukoll, skond din id-dikjarazzjoni, xellug huwa biss pointer, hekk li biss ifisser jien tgħaddi għall-funzjoni ta 'tfittxija a pointer differenti, jiġifieri il-wieħed li jirrappreżenta siġra tifel xellug tiegħi. Allura f'dan il-każ, il-pointer sa 33, jekk dan huwa input kampjun tagħna Sadanittant, jekk n huwa akbar mill-valur n fil- node attwali fil-siġra, allura jien se jmorru quddiem u Punt fl-ieħor direzzjoni u biss jgħidu, I ma tkun taf jekk dan il-valur n huwa fil-siġra, imma naf jekk huwa, huwa isfel tiegħi fergħa dritt, biex ngħidu hekk. So let me sejħa recursively tfittxija, jgħaddu minn n-ġdid, iżda li tgħaddi fil- pointer għat-tarbija dritt tiegħi. Fi kliem ieħor, jekk jien bħalissa 55 u jien infittxu 99, naf li 99 huwa akbar minn 55, hekk bħad I Tore il-ġimgħat ktieb tat-telefon ilu u aħna marru dritt, bl-istess mod aħna se jmorru dritt hawn. U jien ma nafx jekk huwa fil-lemin tiegħi tfal, u mhuwiex, 77 hemm, iżda Naf huwa f'dik id-direzzjoni. So I call tfittxija fuq tifel lemin tiegħi, 77, u ħalli figura tfittxija out minn hemm jekk 99 f'dan arbitrarja Eżempju huwa attwalment hemm. Else, x'inhu l-każ finali? Jekk siġra huwa null każ wieħed. Jekk n huwa inqas mill-node tal attwali valur huwa każ ieħor. Jekk n hija akbar mill-kurrenti valur node huwa terz każ. X'hemm-raba 'u laħħar każ? I think we qed barra ta 'każijiet, id-dritt? Hija għandha tkun li n hija fil- node attwali li jien fuq. Mela jekk jien tiftix għal 55 f'dan il-punt fl-istorja, dik il-fergħa ta 'l- siġra se jerġa 'lura veru. Allura x'hemm interessanti hawnhekk huwa li aħna attwalment, b'differenza ġimgħat li għaddew, irridu tip ta 'jkollu żewġ każijiet bażi. U dawn ma jkollhom ikunu kollha fil-quċċata. Il-quċċata hija każ bażiku għaliex jekk il- siġra huwa null, hemm xejn li jagħmlu. Just jirritornaw hard kodifikata valur ta 'riżultati foloz. Il-fergħa tal-qiegħ huwa tip ta 'l- default, fejn jekk konna ċċekkjati għal null, konna ċċekkjati jekk għandu jkun xellug, iżda ma għandu jkun, konna ċċekkjati jekk għandu jkun dritt, iżda m'għandux ikun, b'mod ċar għandu jkun dritt fejn aħna. Li l-każ bażi. Allura hemm żewġ każijiet rikursivi mgħaffeġ hemm fin-nofs. Imma I setgħet bil-miktub dan fi kwalunkwe ordni. I maħsub biss tip ta 'ħass naturali li l-ewwel jikkontrolla għal żball possibbli, mbagħad tiċċekkja xellug, mbagħad tiċċekkja dritt, imbagħad jassumi li int fil-node int fil-fatt tfittex. Allura għaliex jista 'dan jiġi utli? Għalhekk jirriżulta li - u let me jaqbżu teaser hawn li fil-web. Aħna ser tibda tuża mhux programmazzjoni lingwa fl-ewwel, iżda lingwa markup. A lingwa markup hija waħda li l- simili fl-ispirtu l-ipprogrammar lingwa, iżda ma jagħtuk l- ħila biex tesprimi ruħek loġikament. Hija biss jagħtik l-abbiltà li tesprimi lilek innifsek strutturalment. Meta inti tixtieq li tqiegħed xi ħaġa fuq il-paġna, il-paġna web? Liema kulur inti tixtieq li tagħmel dan? Liema daqs tat-tipa inti tixtieq li tagħmel dan? Liema kliem do inti fil-fatt trid fuq il-paġna web? Allura dak lingwa markup. Imma allura aħna ser jintroduċu malajr ħafna JavaScript, li hija full-sħiħ programmazzjoni lingwa. Simili ħafna sintattikament fid-dehra li C, iżda ser ikollhom xi sbieħ, aktar qawwija, aktar karatteristiċi faċli għall-utent. U wieħed mill-frustrazzjonijiet f'dan punt fil-semestru hija li aħna ser Hekk jimplimentaw speller fil ferm inqas linji ta 'kodiċi li jużaw lingwi minn C nnifisha tippermetti, iżda għal raġuni ta aħna ser dalwaqt jifhmu. Dan se jkun l-ewwel paġna web tali. Din se tkun kompletament underwhelming, l-ewwel waħda nagħmlu. Hija se sempliċement jgħidu, bonjour dinja. Imma jekk inti stajt qatt raw dan qabel, dan huwa HTML, HyperText Markup Language. Jekk inti tmur lil ċerti għażla menu fil aktar xi browser, fuq kull paġna web fuq l-internet, tista 'tara l-HTML li xi nies kiteb joħolqu dik il-paġna web. U probabbilment ma tfittex qosor jew kif pulita bħala dan. Iżda se ssegwi l-mudell ta 'dawn parentesi miftuħa u slashes u ittri u n-numri potenzjalment. Ħsibt I d jagħtik teaser ta 'dak li inti ser tkun tista' tagħmel wara li tieħu CS50. Let me mur cs.harvard.edu / Rob, homepage tagħna stess Bowden Rob tal. Huwa għamel dan għalina. Allura inti ser dalwaqt tkun kapaċi li jagħmlu dan. U wkoll, dak li inti smajt dalgħodu - dak li inti smajt dalgħodu - [Ħamster DANCE MUSIC] - You'll ikunu jistgħu jagħmlu dan. Li jistenna minna nhar l-Erbgħa. Aħna se tara inti mbagħad. [Ħamster DANCE MUSIC] DAVID Malan: Fl-CS50 jmiss -