>> 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.
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 -