[Daqq ta mużika]
>> DAVID Malan: Dan huwa CS50.
U dan huwa kemm l-bidu u l- end-- bħall literally-- kważi l-aħħar
ta 'sitt ġimgħat.
>> Ħsibt I d jaqsmu ftit ta 'fatt gost.
Stajt jinġibed dan up minn data semestru passat issettjat.
Inti tista 'tfakkar li aħna nitolbuk fuq kull p forma sett jekk inti stajt jarah online
jew jekk inti stajt attendew personalment.
U hawn huwa l-data.
Hekk illum kien ferm prevedibbli.
Imma ridna li jonfqu ftit ta 'ħin miegħek xorta.
Kieku xi ħadd tixtieq konġettura għaliex dan graff hija tant jaggy, up isfel, up isfel,
hekk konsistentement?
What do kull wieħed mill-qċaċet u ħwat jirrappreżentaw?
>> UDJENZA: [inaudible]
DAVID Malan: Tabilħaqq.
U aktar divertenti, Alla jipprojbixxu, aħna istiva taħdita waħda nhar ta 'Ġimgħa
fil-bidu tas-semestru, dan huwa dak li naraw jiġri.
Hekk illum, aħna ikollhom sehem fl daqsxejn aktar dwar strutturi ta 'dejta.
U biex jagħtuk aktar ta 'solidu mudell mentali għall-problemi fil-ħames,
li huwa issa out.
Misspellings, fejn, aħna ser banda inti fajl test xi 100,000
plus kliem Ingliż, u int ser ikollhom
biex insemmu kif cleverly jitgħabbew fil-memorja, fis RAM, bl-użu xi data
istruttura ta 'l-għażla tiegħek.
>> Issa wieħed istruttura tad-data bħal seta jkun, iżda probabbilment ma għandhiex tiġi,
il-lista hija pjuttost simplistika marbuta, li aħna introdotti aħħar darba.
U lista marbuta kellhom mill-inqas wieħed vantaġġ fuq firxa.
X'hemm vantaġġ wieħed lista marbuta forsi?
>> UDJENZA: Inserzjoni.
>> DAVID Malan: Inserzjoni.
X'tifhem minn dik?
>> UDJENZA: Kullimkien flimkien il-lista [inaudible].
>> DAVID Malan: Tajba.
Allura inti tista 'daħħal element kulfejn inti tixtieq fin-nofs tal-lista
mingħajr ma jkollhom shuffle xejn, li aħna kkonkludiet, fl issortjar tagħna
diskussjonijiet, mhuwiex bilfors ħaġa tajba,
minħabba li jieħu ż-żmien biex attwalment jiċċaqalqu kollha ta 'dawk bnedmin lemin jew xellug.
U hekk ma 'lista marbuta, inti tista biss jalloka malloc, node ġdid,
u mbagħad taġġorna koppja ta ' pointers-- żewġ, tliet operazzjonijiet max--
u aħna qed kapaċi li slots xi ħadd fi kullimkien fi lista.
>> X'iktar kien vantaġġuż dwar lista marbuta?
Yeah?
>> UDJENZA: [inaudible]
DAVID Malan: Perfect.
Perfect.
Huwa tassew dinamiku.
U li int mhux jikkommettu, bil-quddiem, sa ċertu daqs fiss
blokki ta 'memorja, bħal inti jkollok li ma 'firxa, il-rasu ta' liema
hija li inti tista jalloka lymph biss fuq domanda u b'hekk jintużaw biss bħala ħafna spazju
kif inti attwalment ħtieġa.
B'kuntrast ma 'firxa, inti tista aċċidentalment jallokaw ftit wisq.
U allura huwa biss se li jkunu uġigħ fl-għonq
li jirriallokaw firxa ġdida akbar, kopja kollox fuq, tilliberalizza l-array qodma,
u mbagħad jimxu dwar in-negozju tiegħek.
Jew agħar, inti tista 'talloka mod memorja aktar milli suppost attwalment ħtieġa,
u hekk int se jkollhom ħafna firxa b'popolazzjoni skarsa, biex ngħidu hekk.
>> Allura lista marbuta jagħtik dawn vantaġġi ta 'dinamiżmu u l-flessibilità
ma inserzjonijiet u tħassir.
Iżda żgur għandu jkun hemm prezz imħallas.
Fil-fatt, waħda mit-temi esplorati fuq kwizz żero
kien koppja ta 'l-kompromessi Rajna s'issa.
Allura x'hemm prezz imħallas jew ta ' negattivi ta 'lista marbuta?
Yeah.
>> UDJENZA: L-ebda aċċess bl-addoċċ.
>> DAVID Malan: L-ebda aċċess bl-addoċċ.
Iżda quién?
Aċċess bl-addoċċ ma ħoss konvinċenti.
>> UDJENZA: [inaudible]
DAVID Malan: Eżattament.
Jekk inti tixtieq li jkollok a algorithm-- ċerta
u let me attwalment tipproponi tfittxija binarju, b'mod partikolari, li
hija waħda konna użati pjuttost bit-- jekk inti ma għandekx aċċess bl-addoċċ,
inti ma tistax tagħmel dan aritmetika sempliċi ta 'konstatazzjoni bħall-element tan-nofs
u jaqbeż dritt għaliha.
Inti minflok għandek tibda fl-ewwel element u lineari tfittxija mix-xellug
biex id-dritt jekk inti tixtieq li ssib nofs jew kwalunkwe element ieħor.
>> UDJENZA: Huwa probabbilment jieħu memorja aktar.
>> DAVID Malan: Jieħu memorja aktar.
Fejn hi li addizzjonali ispiża ġejjin minn fil-memorja?
>> UDJENZA: [inaudible]
DAVID Malan: Eżattament.
F'dan il-każ hawnhekk, kellna lista marbuta għall-interi,
u għadhom aħna qed irduppjar l-ammont tal-memorja
għandna bżonn mill-ħażna wkoll dawn pointers.
Issa inqas ta 'big deal bħala structs tiegħek tikseb akbar
u int ħażna ma jkunx numru iżda forsi student jew xi oġġett ieħor.
Iżda l-punt ċertament tibqa.
U għalhekk numru ta 'l-operazzjonijiet fuq il-listi marbuta kienu jissejħu
kienu O kbira ta 'lineari n--.
Affarijiet simili inserzjoni jew tfittxija jew tħassir fil-każ element
li jkun ġara fl-aħħar nett ta ' il-lista jekk huwa magħżula jew le.
>> Kultant inti tista 'tikseb xortik tajba u fil- limiti hekk aktar baxxi fuq dawn l-operazzjonijiet
Jista 'wkoll ikun ta' żmien kostanti jekk int dejjem tħares lejn l-ewwel element,
per eżempju.
Iżda fl-aħħar, aħna imwiegħed biex jintlaħaq l-Grail qaddis
ta 'strutturi ta' dejta, jew xi tieghu approssimazzjoni,
permezz ta 'ħin kostanti.
Nistgħu nsibu l-elementi jew jiżdiedu elementi jew tneħħi elementi minn lista?
Ser naraw pjuttost malajr.
U jirriżulta li wieħed tal-mekkaniżmi aħna qed
ser tibda tuża llum, użu annwali fil-p sett ħamsa,
huwa attwalment pretty familjari.
Per eżempju, jekk dan huwa mazz ta 'kotba eżami, li kull wieħed minnhom
għandha l-ewwel student isem u l-aħħar isem fuqha,
u I pick up lilhom minn fl-aħħar ta 'eżami,
u dawn qed kollha pretty ħafna f 'ordni każwali,
u rridu li tmur dwar għażla dawn l-eżamijiet b'tali mod li ladarba gradati
huwa biss ħafna aktar faċli u aktar mgħaġġel biex jgħadduhom lura
lill-istudenti alfabetikament.
Liema jkun instincts tiegħek tkun għal munzell ta 'eżamijiet bħal dan?
>> Ukoll, jekk int simili me, inti tista 'tara li dan huwa m,
hekk jien ser tip ta 'tpoġġi dan fi, jekk dan huwa mejda tiegħi jew mill-art tiegħi fejn
Jien tixrid affarijiet out-- jew firxa tiegħi really--
I tista 'tpoġġi kollha ta' l Sinjura fil hemmhekk.
Oh.
Hawn A. So I jista tpoġġi l-Kif hawn fuq.
Oh.
Hawn A. ieħor jien ser biex iqiegħed dak hawn fuq.
Hawn Z. Hawnhekk huwa M. ieħor U hekk I tista 'tibda tagħmel munzelli bħal dan.
U allura forsi I d jmorru fl aktar tard u tip ta 'nitpicky-ly ħafna sort
l-puntali individwali.
Imma l-punt hu jien look fid-dħul li jien f'idha
u nixtieq tagħmel xi kkalkulat deċiżjoni bbażata fuq dik input.
Jekk jibda ma 'A, poġġih hemmhekk.
Jekk jibda ma 'Z, poġġih fuq hemm, u kollox bejniethom.
>> Allura dan huwa teknika li l- ġeneralment magħrufa bħala hashing-- H-A-S-H--
li ġeneralment ifisser li jieħdu bħala input u l-użu li l-kontribut biex tiġi kkalkulata
valur, ġeneralment numru, u li in-numru huwa l-indiċi fil-ħażna
kontenitur, bħal firxa.
Allura fi kliem ieħor, I jista 'jkollhom funzjoni hash, kif nagħmel in my head,
li jekk nara xi ħadd huwa isem li tibda bil A,
Jien ser mappa li għal żero fl my head.
U jekk nara xi ħadd bil Z, jien ser Mappa li biex 25 in my head
u mbagħad titqiegħed dan in l-aħħar pile aktar.
>> Issa, jekk inti taħseb dwar li ma moħħ tiegħi iżda programm C, liema numri jista
inti tistrieħ fuq biex jintlaħaq dak l-istess riżultat?
Fi kliem ieħor, jekk inti kellu l-ASCII karattru A,
kif taħseb li jiddeterminaw dak barmil li tqiegħed fil?
You probabbilment ma jridux poġġih fil-barmil 65, li
ikun simili hemmhekk għall-ebda raġuni tajba.
Fejn do inti tixtieq li tqiegħed A f'termini ta 'valur ASCII tagħha?
Fejn do inti tixtieq li tagħmel biex ASCII tagħha valur li toħroġ bi barmil aktar intelliġenti
li tqiegħed fil?
>> UDJENZA: Minus A.
>> DAVID Malan: Yeah.
Allura minus A jew minus speċifikament 65 jekk huwa
kapital A. Jew 98 jekk huwa zghar a.
U hekk li tippermetti magħna biex, ħafna sempliċi u aritmetikament ħafna,
xi ħaġa fi barmil bħal dik.
Għalhekk jirriżulta li għandna attwalment nagħmlu dan ukoll anke mal-kwiżż.
>> Allura inti tista 'recall inti circled tiegħek isem sħabi tagħlim fuq il-qoxra.
U ġew organizzati ismijiet tal-TF tal f'dawn kolonni alfabetikament,
ukoll, jemmnu jew le, meta kollha 80 plus minna
ltqajna flimkien oħra bil-lejl għall-grad, l-aħħar pass fil-proċess ta 'gradazzjoni tagħna
huwa li hash l kwizzijiet fi big ispazju ta 'l-art fil-[inaudible]
u li jiġu kwizzijiet kulħadd out eżattament fl-ordni ta 'l TF tagħhom
ismijiet fuq il-qoxra, għaliex allura huwa ħafna aktar faċli għalina
li tfittex li l-użu lineari tfittxija jew xi tip ta 'cleverness
għal TF biex isibu tiegħu jew kwizzijiet istudenti tagħha ".
>> Allura din l-idea ta 'hashing li inti ser tara hija
pjuttost qawwija huwa attwalment pretty komuni ħafna u intuwittivi,
ferm simili forsi jaqsam u Conquer kien żero ġimgħa.
I bil-ħerqa sew mal-hackathon ftit ta 'snin ilu.
Dan kien Zamyla u l-koppja ta ' studenti oħra greeting persunal
kif daħal.
U kellna mazz sħiħ ta 'tiwi tabelli hemm ma tikketti l-isem.
U kellna l-tikketti l-isem organizzata mal bħall-AS fuq hemmhekk
u l-Zs hemmhekk.
U għalhekk wieħed mill-TFS ħafna cleverly kiteb dan bħala l-istruzzjonijiet
għall-jum.
U fil-ġimgħa 12 tal-semestru dan kollha magħmula sens perfetta u kulħadd
kien jaf x'għandek tagħmel.
Imma ghaċ inti stajt kju bl-istess mod,
int li timplimenta l- istess kunċett ta 'hash.
Mela ejja jifformalizzaw dan ftit.
Hawnhekk huwa firxa.
Huwa mfassal li jkun ftit wiesgħa biss biex juru, viżwalment,
li aħna tista 'tpoġġi kordi fil xi ħaġa bħal din.
U dan firxa hija b'mod ċar mid-daqs 26 totali.
U l-ħaġa hija msejħa tabella arbitrarju.
Iżda din hija biss konsenja ta 'l-artist ta 'dak tabella hash jista' jkun.
>> Allura tabella hash issa se jkun struttura data livell ogħla.
Fl-aħħar tal-ġurnata aħna qed dwar li tara li inti
tista 'timplimenta tabella hash, li huwa ferm simili l-linja check-in
fi hackathon ħafna bħal dan tabella wżata għal issortjar kotba eżami.
Iżda tabella hash huwa tip ta 'dan il-livell għoli
kunċett li tista 'tuża firxa taħt il-barnuża biex jimplimentawha,
jew jista 'juża lista tul, jew saħansitra forsi xi strutturi oħra ta 'data.
U issa li l-teħid theme-- xi wħud minn dawn l-ingredjenti fundamentali
bħal firxa u dan il-bini blokk issa ta 'lista tul
u tara dak li inkella nistgħu nibnu fuq quċċata ta 'dawk, bħal ingredjenti
fi riċetta, jagħmlu aktar u aktar riżultati finali interessanti u utli.
>> Allura mat-tabella hash nistgħu jimplimentawha
fil-memorja pictorially bħal dan, iżda kif jista 'attwalment jiġi kkodifikat up?
Well, forsi bħala sempliċi hija din.
Jekk il-kapaċità fil-tappijiet kollha, huwa biss xi constant-- per eżempju 26,
għal 26 ittri tal-alphabet-- I tista 'sejħa tabella varjabbli tiegħi,
u I jista jsostnu li jien ser tpoġġi istilel Salvelinus fil hemm, jew string.
Allura huwa sempliċi kemm dan jekk inti jridu jimplimentaw tabella hash.
And yet, dan huwa verament ftit firxa.
Iżda għal darb'oħra, a hash tabella issa huwa dak li aħna inneħħu
sejħa ta 'tip ta' data astratta li jinsab biss tip ta 'saffi kunċettwali fuq nett
ta 'xi ħaġa aktar mundane issa tixtieq firxa.
>> Issa, kif do we go dwar soluzzjoni ta 'problemi?
Well, aktar kmieni kelli l-lussu ta 'wara spazju biżżejjed tabella hawn
I hekk li jista 'tpoġġi l- kwizzijiet kullimkien ridt.
Allura Kif jista mur hawn.
Zs jista 'jmur hawn.
Is-Sinjura jista 'jmur hawn.
U mbagħad I kellhom xi spazju żejjed.
Iżda dan huwa daqsxejn ta 'iqarrqu dritt issa għaliex din it-tabella, jekk I really
ħsieb ta 'dan bħala firxa, huwa biss se jkunu ta 'xi daqs fiss.
>> Allura teknikament, jekk I iġbed up kwizz student ħaddieħor
u ara, oh, tal din il-persuna isem jibda ma 'A wisq,
I tip ta 'tixtieq li tqiegħed lilha hemmhekk.
Imma malli I poġġih hemmhekk, jekk din it-tabella tabilħaqq jirrappreżenta firxa,
Jien ser tkun prevalenti jew clobbering min kwizz dan l-istudent huwa.
Dritt?
Jekk dan huwa firxa, biss ħaġa waħda jista jmorru f'kull wieħed minn dawn iċ-ċelluli jew elementi.
U so I tip ta 'jkollhom li pick u jagħżlu.
>> Issa qabel I tip ta ' misruqin u ma dan jew I
biss tip ta 'f'munzelli minnhom hawn fuq xulxin.
Iżda dan mhux se jtiru fil-kodiċi.
Għalhekk, fejn jista I tpoġġi l- istudent tieni li ismu
huwa A jekk kollox kelli huwa dan ispazju tabella disponibbli?
U stajt użati tliet slots u li Dehra hemm biss ftit oħrajn.
Liema jista inti tagħmel?
UDJENZA: [inaudible]
DAVID Malan: Yeah.
Forsi ejja biss jżommha sempliċi.
Dritt?
Ma jwaħħalx fejn I tixtieq li tqiegħed lilha.
Hekk jien ser tqiegħed lilha teknikament fejn B tmur.
Issa, naturalment, jien jibdew żebgħa myself fil-kantuniera.
Jekk niġi lil student li ismu huwa attwalment B,
issa B se jiġu mċaqalqa ftit quddiem, kif jista 'jiġri, Yep,
jekk dan huwa B, issa hija għandha tmur hawn.
>> U hekk dan malajr ħafna tista 'ssir problematika,
imma hija teknika li attwalment huwa msemmi bħala lineari probing,
fejn inti biss tikkunsidra tiegħek array li jkun matul il-linja.
U inti biss tip ta 'sonda jew jispezzjona kull element disponibbli
tfittex għal post disponibbli.
U hekk kif issib waħda, inti qatra fil hemmhekk.
>> Issa, il-prezz imħallas issa għal din is-soluzzjoni huwa dak?
Għandna firxa daqs fiss, u meta I daħħal ismijiet
fis dan, mill-inqas inizjalment, x'hemm il running time ta 'inserzjoni
għat-tqegħid tal-istudenti kwizzijiet fil-bramel dritt?
Big O ta 'dak?
>> UDJENZA: n.
DAVID Malan: Smajt O kbira ta 'n.
Mhux veru.
Iżda aħna ser tease apparti għaliex fi ftit mument.
X'iktar jista jkun?
>> UDJENZA: [inaudible]
DAVID Malan: U let me tagħmel dan viżwalment.
Allura jissoponi dan huwa l-ittra S.
>> UDJENZA: Huwa wieħed.
DAVID Malan: Huwa wieħed.
Dritt?
Dan huwa firxa, li ifisser li għandna aċċess bl-addoċċ.
U jekk naħsbu ta 'dan kif żero u dan bħala 25,
u aħna tirrealizza li, oh, hawnhekk input tiegħi S,
I jista 'ċertament jikkonvertu S, karattru ASCII,
għal numru korrispondenti bejn żero u 25
u mbagħad minnufih poġġih fejn jappartjeni.
>> Iżda naturalment, malli I jiksbu l- tieni persuna li l-isem huwa A jew B jew C
eventwalment, jekk stajt użati l- lineari probing bħala soluzzjoni tiegħi,
il-ħin running ta inserzjoni fl-agħar każ
huwa attwalment għaddejjin biex tittrasferixxi fis liema?
U jien ma tismagħha hawn korrett kmieni.
UDJENZA: [inaudible]
DAVID Malan: Allura huwa n tabilħaqq darba inti għandek sett ta 'dejta kbira biżżejjed.
Allura, min-naħa waħda, jekk array tiegħek huwa kbir biżżejjed
u d-data tiegħek hija skarsa biżżejjed, inti nikseb dan iż-żmien kostanti beautiful.
Iżda hekk kif tibda jkollna aktar u aktar elementi,
u biss statistikament ikollok aktar nies bl-ittra
A kif l-isem tagħhom jew l-ittra B, din tista 'potenzjalment
jiddevolvu fis xi ħaġa aktar lineari.
Allura ma pjuttost perfetta.
Allura nistgħu nagħmlu aħjar?
>> Ukoll, dak li kien tagħna Soluzzjoni qabel meta aħna
tixtieq li jkollhom dinamiżmu aktar minn xi ħaġa bħal firxa permessa?
UDJENZA: [inaudible]
DAVID Malan: What did aħna jintroduċu?
Yeah.
Allura lista marbuta.
Well, ejja ara dak marbut lista tista 'tagħmel għalina minflok.
Well, let me tipproponi li aħna jiġbed l-istampa kif ġej.
Issa dan huwa differenti stampa minn eżempju
minn test differenti, attwalment, li huwa attwalment jużaw firxa ta 'daqs 31.
U dan awtur sempliċement iddeċieda li hash kordi
mhux ibbażati fuq l-ismijiet tal-persuna, iżda bbażata fuq birthdates tagħhom.
Irrispettivament tax-xahar, huma dehret jekk int imwieled fl-ewwel ta 'xahar
jew il-31 ta ta 'xahar, l-awtur se hash bbażati fuq dak il-valur,
sabiex jinfirxu l-ismijiet out a bit aktar milli sempliċiment 26 spots tista 'tippermetti.
U forsi huwa ftit aktar uniformi milli jmorru ma 'ittri alfabetiċi,
minħabba naturalment hemm probabilment aktar nies fid-dinja bl-ismijiet
li tibda bil minn ċertament xi ittri oħra tal-alfabett.
Allura forsi dan huwa ftit aktar uniformi, jekk wieħed jassumi
distribuzzjoni uniformi ta 'trabi madwar xahar.
>> Imma, naturalment, dan għadu imperfetta.
Dritt?
Qed ikollna ħabtiet.
Nies multipli f'dan struttura tad-data għadhom
jkollhom l-istess birthdate inqas int irrispettivament mill xahar.
Imma dak li l-awtur jsir?
Ukoll, jidher qisu għandna firxa fuq in-naħa tax-xellug mfassla vertikalment,
iżda li biss konsenja ta 'l-artist.
Ma jimpurtax liema direzzjoni inti jiġbed firxa, huwa għadu firxa.
X'inhu dan firxa ta 'apparentement?
>> UDJENZA: lista Marbuta.
>> DAVID Malan: Yeah.
Jidher qisu huwa ta ' firxa ta 'lista marbuta.
Għalhekk għal darb'oħra, dan il-punt ta 'tip ta 'użu ta dawn l-istrutturi tad-data issa
bħala ingredjenti għal aktar soluzzjonijiet interessanti,
inti tista 'assolutament tieħu fundamentali, bħal firxa,
u mbagħad ħu xi ħaġa aktar interessanti bħal lista marbuta
u anke għaqqadhom fi saħansitra istruttura tad-data aktar interessanti.
U fil-fatt, dan kieku wisq jiġi msejjaħ tabella hash,
li biha l-firxa hija verament il-mejda hash,
iżda dik it-tabella hash għandha ktajjen, biex ngħidu hekk,
li tista 'tikber jew tiċkien ibbażata fuq l- għadd ta 'elementi li inti tixtieq li daħħal.
>> Issa, għaldaqstant, x'hemm il-ħin running issa?
Jekk irrid li daħħal xi ħadd birthday tiegħu huwa 31 Ottubru,
fejn ma hu jew hi tmur?
Kull dritt.
Fil-qiegħ nett fejn jgħid 31.
U li perfett.
Dan kien żmien kostanti.
Imma x'jiġri jekk insibu xi ħadd ieħor birthday tiegħu huwa, ejja ara,
Ottubru, Novembru, Diċembru 31?
Fejn hu jew hi se jmorru?
Istess ħaġa.
Żewġ stadji għalkemm.
C'est kostanti għalkemm hux?
Kull dritt.
Fil-mument huwa.
Iżda fil-każ ġenerali, L-aktar nies aħna żid,
probabilistically, aħna qed tmur biex jiksbu aktar u aktar kolliżjonijiet.
>> Issa dan huwa ftit aħjar għaliex teknikament
issa ktajjen tiegħi jista 'jkun fil- l-agħar każ kemm żmien?
Jekk I daħħal n-nies fis dan aktar istruttura tad-data sofistikati, n-nies,
fl-agħar każ li għaddej biex tkun n.
Għaliex?
>> UDJENZA: Għaliex jekk kulħadd għandu l-istess birthday,
dawn qed tmur biex tkun linja waħda.
DAVID Malan: Perfect.
Jista 'jkun ftit artifiċjali, iżda tassew fl-agħar każ,
jekk kulħadd għandu l-istess birthday, minħabba l-inputs ikollok,
int se jkollhom katina massiv twil.
U għalhekk, inti tista 'sejħa hija ta' hash tabella, imma verament huwa
biss lista marbuta massiv ma lott kollu ta 'spazju moħli.
Iżda b'mod ġenerali, jekk nassumu li inqas għeluq is-snin huma uniform--
u probabbilment mhuwiex.
Jien jagħmlu dan up.
Imma jekk aħna nassumu, għal l-fini ta 'diskussjoni
li huma, imbagħad fit-teorija, jekk dan huwa l-rappreżentazzjoni vertikali
tal-firxa, tajjeb allura nisperaw int se tikseb ktajjen li huma, inti taf,
bejn wieħed u ieħor l-istess tul fejn kull waħda dawn jirrappreżenta jum tax-xahar.
>> Issa jekk hemm 31 jum fix-xahar, dan ifisser running time tiegħi verament
huwa O kbira ta 'n aktar minn 31, li iħoss aħjar minn lineari.
Imma dak kien wieħed ta 'tagħna impenji ftit ġimgħat
ilu meta ġie biex jesprimu il running time ta 'algoriżmu?
Biss ħarsa biss fil-terminu ordni għolja.
Dritt?
31 huwa definittivament utli.
Iżda dan għadu O kbira ta 'n.
Iżda waħda mit-temi ta 'problema sett ħamsa
se jkun li jirrikonoxxu li assolutament,
asimptotikalment, teoretikament din l-istruttura tad-data
l-ebda aħjar minn sempliċiment lista waħda enormi marbuta.
U fil-fatt, fl-agħar każ, din tabella hash jista jiddevolvu f'dak.
>> Iżda fid-dinja reali, magħna bnedmin li MACs jew PCs stess jew kwalunkwe
u qed jitħaddmu dinja reali software fuq data dinja reali,
li algoritmu huma inti tmur tippreferi?
Il-wieħed li jieħu passi finali jew li l- wieħed li jieħu n diviż bil 31 passi
biex isibu xi biċċa ta 'data jew tfittex up xi informazzjoni?
I mean, assolutament l-31 jagħmel differenza fid-dinja reali.
Huwa 31 darbiet aktar mgħaġġla.
U aħna bnedmin huma ċertament se japprezzaw li.
>> Allura jirrealizzaw il-dikotomija hemm bejn attwalment
jitkellem dwar affarijiet teoretikament u asimptotikalment li żgur
għandu valur bħala Rajna, iżda fid-dinja reali,
jekk int jimpurtak biss tagħmel il- kuntenti bniedem għal inputs ġenerali,
inti tista 'tajjeb ħafna' tixtieq li taċċetta il-fatt li, iva, dan huwa lineari,
imma hija 31 darbiet aktar mgħaġġla milli lineari jista 'jkun.
U aħjar għadhom, aħna ma biss għandhom tagħmel xi ħaġa arbitrarja bħal birthdate,
nistgħu jonfqu ftit aktar ħin u cleverness
u jaħsbu dwar dak li nistgħu nagħmlu, mogħti isem ta 'persuna u forsi
birthdate tagħhom li jgħaqqdu dawk ingredjenti biex insemmu xi ħaġa
li hija verament aktar uniformi u inqas jaggy,
biex ngħidu hekk minn din l-istampa bħalissa jissuġġerixxi li jista 'jkun.
Kif nistgħu jimplimentaw dan fil-kodiċi?
Well, let me tipproponi li aħna biss tissellef xi sintassi konna
użat koppja darbiet s'issa.
U jien ser jiddefinixxu node, li għal darb'oħra
huwa terminu ġeneriku għall biss xi kontenitur għal xi struttura tad-data.
Jien ser tipproponi li string huwa għaddej fil hemmhekk.
Iżda aħna qed tmur biex jibdew jieħdu dawk taħriġ roti off issa.
>> Nru aktar librerija CS50 verament, jekk inti tixtieq
jużawha għal finali tiegħek proġett, li huwa multa,
iżda issa aħna qed tmur biex jiġbdu lura l- purtieri u jgħidu huwa biss stilla char.
Allura l-kelma hemm se tkun isem tal-persuna kkonċernata.
U issa għandi rabta hawn għall-node li jmiss
sabiex dawn jirrappreżentaw kull wieħed mill-lymph
fil-katina, potenzjalment, ta 'lista marbuta.
>> U issa kif do Niddikjara il-mejda hash innifsu?
Kif nista niddikjara din l-istruttura sħiħa?
Ukoll, verament, ħafna bħal I użati pointer biss l-ewwel element ta 'lista
qabel, b'mod simili nista biss jgħidu I biss bżonn mazz ta 'pointers
biex jimplimentaw din it-tabella hash kollu.
Jien ser ikollhom firxa sejjaħ tabella għal tabella hash.
Li għaddej biex tkun ta 'kapaċità daqs.
Thats kemm elementi jistgħu joqogħdu fiha.
U kull wieħed minn dawn l-elementi f'din array se tkun stilla node.
Għaliex?
Ukoll, kull din l-istampa, dak jien implimentazzjoni tal-mejda hash bħala
effettiv fil-bidu huwa biss dan array li aħna ve mfassla vertikalment,
kull wieħed li kwadri jirrappreżenta pointer.
Li dawk li jkollhom slashes permezz tagħhom huma biss nulli.
U dawk li jkollhom vleġeġ li jmorru lejn il-lemin
huma pointers attwali għall-lymph attwali, għalhekk jimmiraw il-bidu ta 'lista marbuta.
>> Allura hawnhekk, allura, huwa kif nistgħu jimplimentaw tabella hash li
timplimenta chaining separat.
Issa nistgħu nagħmlu aħjar?
Kull dritt I wiegħed aħħar darba li nistgħu jiksbu ħin kostanti.
U jien tip ta ħadt ħin kostanti hawn,
iżda mbagħad qal mhux verament ħin kostanti għaliex huwa għadu
dipendenti fuq it-total numru ta 'elementi
int inputjar fis l-istruttura tad-data.
Iżda jissoponi għamilna dan.
Let me jmorru lura għall-iskrin hawn fuq.
Let me wkoll proġettata dan up hawn, ċara l-iskrin, u jissoponi Jien għamilt dan.
Suppose I riedu li daħħal l-isem Daven fil fl-istruttura tad-data tiegħi.
>> So I tixtieq li daħħal string Daven fl-istruttura tad-data.
X'jiġri jekk I ma jużawx hash tabella, iżda I użu
xi ħaġa li l-aktar siġar simili bħal siġra tal-familja, fejn
ikollok xi għeruq fil- lymph top u mbagħad u weraq
li jmorru isfel u barra.
Ejja ngħidu mbagħad, li jien tixtieq li daħħal l Daven
lejn dak li bħalissa huwa lista vojta.
Jien ser tagħmel dan li ġej: Ninsab se toħloq node fil din il-familja
istruttura tad-data bħal siġra li jistenna ftit bħal dan, li kull wieħed minnhom
rettangoli tkun, ejja ngħidu, għal issa 26 elementi fiha.
U kull wieħed mill-ċelluli f'dan array huwa għaddej
biex jirrappreżentaw l-ittra ta 'alfabett.
>> Speċifikament, jien ser jikkura Din hija, imbagħad B, allura Ċ, imbagħad D,
dan wieħed hawn.
Allura dan se effettivament jirrappreżentaw l-ittra D.
Iżda biex daħħal kollha tal Daven isem I bżonn tagħmel daqsxejn aktar.
Hekk jien l-ewwel ser hash, biex ngħidu hekk.
Jien ser tħares lejn l-ewwel ittra fil Daven ta li hija ovvjament D,
u jien ser jalloka node li jistenna
bħal this-- rettangolu big big biżżejjed sabiex taqdi l-alfabett kollu.
>> Issa D isir.
Issa A. D-A-V-E-N huwa l-għan.
Allura issa dak li jien ser tagħmel hu li dan.
Hekk kif bdejt avviż D hemm l-ebda pointer hemmhekk.
Huwa valuri taż-żibel fil-mument, jew I tista initialize lill nulla.
Iżda let me iżommu għaddejjin ma din l-idea ta 'bini ta' siġra.
Let me jallokaw xulxin minn dawn lymph li għandha 26-elementi fiha.
>> U inti taf liema?
Jekk din hija biss node fil-memorja li I maħluqa bl malloc, bl-użu Struct
kif aħna ser malajr tara, Jien ser tagħmel this--
Jien ser jiġbed vleġġa minn il-ħaġa li tirrappreżenta D isfel
għal dan node ġdid.
U issa, l-ewwel il-li jmiss ittra fl-isem Daven tal,
V-- D-A-V-- jien ser jimxi 'l quddiem u jiġbed node ieħor bħal dan,
li biha, l-elementi V hawn, li aħna ser tiġbed għall Whoops instance--.
Aħna mhux se tiġbed hemmhekk.
Li għaddej biex tmur hawn.
>> Allura aħna qed tmur biex jqisu li dan V.
U allura l isfel hawn aħna qed tmur biex indiċi isfel minn V fis-dak li aħna ser jikkunsidraw E.
U allura minn hawn aħna qed tmur biex mur jkollhom waħda minn dawn lymph hawn.
U issa għandna mistoqsija li jwieġbu.
I-ħtieġa li b'xi mod jindikaw li aħna qed fl-aħħar tas-sekwenza Daven.
So I jistgħu biss jitilqu minnu null.
>> Imma x'jiġri jekk għandna l Daven isem sħiħ ukoll, li
huwa, kif aħna stajt qal, Davenport?
Allura dak li jekk Daven hu attwalment substring,
prefiss ta string ħafna itwal?
Ma nistgħux sempliċement b'mod permanenti jgħidu xejn huwa għaddej
li jmorru hemm, għaliex nistgħu qatt daħħal kelma bħal Davenport
fis dan Struttura data
>> Allura dak li stajna nagħmlu minflok qed jittrattaw kull wieħed minn dawn l-elementi
kif forsi jkollhom żewġ Elementi ġewwa minnhom.
Wieħed huwa pointer, tabilħaqq, kif stajt qed tagħmel.
Allura kull wieħed minn dawn il-kaxxi huwa mhux biss ċellola waħda.
Imma x'jiġri jekk il-quċċata one-- l-waħda qiegħ tal-
se tkun nulla, għaliex m'hemm l-ebda Davenport għadha biss.
X'jiġri jekk il-wieħed mill-quċċata hija xi valur speċjali?
U li għaddej biex tkun ftit diffiċli biex tiġbed dan id-daqs.
Imma jissoponi huwa biss check mark.
Iċċekkja.
D-A-V-E-N hija sekwenza f'din l-istruttura tad-data.
>> Sadanittant, jekk kelli aktar spazju hawn, I jistgħu jagħmlu P-O-R-T,
u I tista 'tpoġġi check fl-node li għandha l-ittra T fl-aħħar nett.
Allura dan huwa massiv istruttura tad-data tħares kumplessi.
U kalligrafija tiegħi ċertament ma jgħinx.
Imma jekk jien ridt li daħħal xi ħaġa inkella, jikkunsidraw dak li nixtiequ nagħmlu.
Jekk ridna li tpoġġi David fi, aħna'd isegwu l-istess loġika, D-A-V,
imma issa nirrileva fil-li jmiss element mhux minn E, iżda minn I sa D.
Allura hemm għaddej li jkun aktar lymph f'dan siġra.
Aħna qed tmur biex ikollhom malloc sejħa aktar.
Imma jien ma jridux jagħmlu mess kompluta ta 'din l-istampa.
Mela ejja minflok tħares lejn wieħed li kien ifformulat minn qabel
bħal dan ma 'jkunx dot, dot, tikek, iżda arrays biss abbrevjati.
Iżda kull tal-lymph f'dan siġra up here
jirrappreżenta l-istess thing-- firxa Ray ta 'daqs 26.
>> Jew jekk irridu nkunu verament tajjeb issa, liema
jekk l-isem ta 'xi ħadd bħala apostrophe, ejja
jassumi li kull node attwalment għandha bħal 27 indiċi fiha, mhux biss 26.
Allura dan issa se jkun data struttura tissejjaħ trie-- T-R-I-E.
A trie, li hija allegatament storikament isem għaqlija għal siġra
thats ottimizzati għal irkupru, li naturalment,
spjegat ma 'I-E hekk huwa trie.
Iżda dan huwa l-istorja tal-trie.
>> Allura trie huwa din id-data 'siġra like struttura bħal siġra tal-familja
li finalment iġib ruħu bħal dik.
U hawn huwa biss eżempju ieħor ta ' mazz sħiħ ta 'ismijiet ta' nies oħrajn.
Iżda l-kwistjoni issa fil-idejn huwa dak ikollu
aħna miksuba billi tintroduċi forsi aktar istruttura tad-data ikkumplikata, u wieħed,
franchement, li juża ħafna ta 'memorja.
>> Għaliex anki jekk, fil-mument, jien biss
użu D's pointer u A u V u Es u Ns,
Jien ħela Heck ta lott ta 'memorja.
Iżda fejn I jonfqu wieħed tar-riżorsi, I-tendenza li do jiksbu lura ieħor.
Mela jekk jien infiq aktar spazju, x'hemm probabbilment l-tama?
Li jien infiq inqas liema?
UDJENZA: Inqas ħin.
DAVID Malan: Time.
Issa għaliex jista 'jkun?
Ukoll, dak li huwa l-inserzjoni żmien, f'termini ta 'O big issa,
ta 'isem bħal Daven jew Davenport jew David?
Ukoll, Daven kien ta 'ħames passi.
Davenport ikun disa passi, għalhekk ikun ftit aktar passi.
David tkun ħames passi kif ukoll.
Għalhekk dawn huma konkreti numri, iżda żgur hemm
rbit għoli fuq il- tul ta 'isem ta' xi ħadd.
U fil-fatt, fil-problema settijiet ta 'ħames ispeċifikazzjoni,
aħna qed tmur biex tipproponi li huwa xi ħaġa
li l-karattri 40-xi-fard.
>> Realistikament, l-ebda wieħed għandu isem infinitament twil,
li huwa li jgħidu li t-tul ta ' isem jew it-tul ta 'sekwenza nistgħu
ikollhom ċerti l-istat ta ' istruttura huwa probabbilment dak?
Huwa kostanti.
Dritt?
Jista 'jkun kostanti kbar bħal 40-xi ħaġa, iżda huwa kostanti.
U għandu l-ebda dipendenza fuq kemm ismijiet oħra huma f'din l-istruttura tad-data.
Fi kliem ieħor, jekk I riedu issa daħħal
Colton jew Gabriel jew Rob jew Zamyla jew Alison jew Belinda jew xi ismijiet oħra
mill-persunal fis din id-data istruttura, huwa l-ħin qed taħdem
ta 'ddaħħal ismijiet oħra se tkun fil-livelli kollha milquta
mill kif ħafna elementi oħra huma fl-istruttura tad-data diġa?
Mhuwiex.
Dritt?
Għaliex aħna qed jużaw b'mod effettiv din it-tabella hash multi-saff.
U l-running time ta ' kwalunkwe minn dawn l-operazzjonijiet
ma jiddependix fuq in-numru ta ' elementi li huma fl-istruttura tad-data
jew li huma eventwalment sejrin li jkun fl-istruttura tad-data,
iżda fuq it-tul ta 'dak speċifikament?
>> L-sekwenza tkun jiddaħħal, li ma jagħmilx
dan asimptotikalment kostanti O big time-- ta 'wieħed.
U franchement, biss fil -dinja reali, dan
ifisser ddaħħal isem Daven iqisx bħall-ħames passi, jew Davenport disgħa
passi, jew David ħames passi.
Li pjuttost darn drabi running żgħar.
U, tabilħaqq, thats ħafna Ħaġa tajba, speċjalment meta
mhuwiex dipendenti fuq it-total numru ta 'elementi fil hemmhekk.
Allura kif tista nimplimentaw dan tip ta 'struttura fil-kodiċi?
Huwa ftit aktar kumpless, iżda xorta huwa
biss applikazzjoni ta ' blokki bażiċi tal-bini.
Jien ser tirridefinixxi us node kif ġej:
BOOL sejjaħ word-- u dan jista 'jissejjaħ xejn.
Iżda l-BOOL tirrappreżenta dak I ġibdet bħala marka kontroll.
Iva.
Dan huwa l-aħħar ta 'sekwenza f'din l-istruttura tad-data.
>> U, naturalment, l-istilla node hemm qed tirreferi għat-tfal.
U, tabilħaqq, bħad siġra tal-familja, inti
jikkunsidraw il-lymph li huma mdendlin off
tal-qiegħ ta 'xi ġenitur element li jkun tfal.
U għalhekk it-tfal se tkun firxa ta '27, is-27 wieħed
biss qed għall apostrophe.
Aħna qed tmur biex issolvi ta 'każ speċjali li.
Allura inti jista 'jkollhom ċerta ismijiet bil apostrophes.
Forsi anke sing suppost jmorru fil hemm, iżda inti ser
tara fil-sett p 5 aħna biss kura dwar ittri u apostrophes.
>> U allura kif do inti tirrappreżenta l-istruttura tad-data nnifisha?
Kif taħseb li tirrappreżenta l-għerq ta 'dan trie, biex ngħidu hekk?
Ukoll, Eżatt bħal ma 'lista marbuta, inti bżonn ta 'pointer li l-ewwel element.
Bil trie inti biss bżonn waħda pointer li l-għerq ta 'din trie.
U minn hemm inti tista hash tiegħek mod isfel aktar profonda u aktar profonda
għal kull node oħra fl-istruttura.
Allura sempliċiment ma dan jista aħna nirrappreżentaw li Struct.
>> Issa Meanwhile-- Oh, kwistjoni.
>> UDJENZA: X'hemm kelma BOOL?
>> DAVID Malan: kelma BOOL huwa biss dan Inkarnazzjoni C
ta 'dak I deskritt f'din il-kaxxa hawn, meta
I bdew inqasmu kull wieħed mill- Elementi array f'żewġ biċċiet.
Wieħed huwa pointer għall-node li jmiss.
L-oħra għandha tkun xi ħaġa bħal kaxxa kontroll
biex ngħid iva, hemm kelma Daven li tispiċċa hawnhekk,
għaliex aħna ma rridux, fil-mument, Dave.
>> Anki jekk Dave se jkun kelma leġittimu, huwa ma fil-trie
s'issa.
U D mhijiex kelma.
U D-A mhijiex kelma jew isem.
Allura l-check mark jindika biss ladarba inti
hit dan node huwa l- passaġġ preċedenti ta 'karattri
attwalment string li inti stajt mdaħħal.
Allura li kollox l-BOOL hemm qed tagħmel għalina.
>> Kwalunkwe mistoqsijiet oħra fuq tipprova?
Yeah.
>> UDJENZA: X'inhu l-overlap?
X'jiġri jekk għandek Dave u Daven?
DAVID Malan: Perfect.
X'jiġri jekk għandek Dave u Daven?
Hekk jekk aħna daħħal, ngħidu nickname, għall David-- Dave-- D-A-V-E?
Dan huwa attwalment sempliċi super.
Allura aħna qed biss ser jieħdu erba 'passi.
D-A-V-E. U dak li għandi biex tagħmel darba I hit li r-raba node?
Biss jmorru biex jiċċekkjaw.
Aħna diġà tajba biex tmur.
Isir.
Erba 'passi.
Ta 'żmien kostanti asimptotikalment.
U issa konna indikat li kemm Dave u Daven huma kordi fl-istruttura.
Allura mhux problema.
U avviż kif il-preżenza ta Daven ma jagħmluhiex
tieħu kwalunkwe aktar ħin jew inqas żmien għall Dave u viċi versa.
>> Allura dak li inkella nistgħu issa tagħmel?
Imxejna użat dan metafora qabel ta 'dixxijiet jirrappreżentaw xi ħaġa.
Iżda jirriżulta li l- munzell ta 'dixxijiet huwa attwalment
dimostrattiva tad-data ieħor astratt type-- data struttura livell ogħla
li fl-aħħar il-jum huwa biss bħal firxa jew lista marbuta
jew xi ħaġa aktar mundane.
Imma hija aktar interessanti kunċett kunċettwali.
A munzell, bħal dawn trejs hawn fil Mather,
huma ġeneralment jissejħu biss that-- munzell.
>> U f'dan it-tip ta 'struttura data għandek żewġ operations--
għandek wieħed imsejjaħ push għal żżid xi ħaġa li l-munzell,
bħal tqegħid trej ieħor Lura fuq il-quċċata tal-munzell.
U mbagħad pop, li jfisser li inti jieħdu l-topmost off trej.
Imma x'hemm ewlieni dwar munzell hu li huwa ltqajna din il-karatteristika kurjuż.
Peress li l-persunal dining sala huma titranġa l-trejs għall-ikla li jmiss,
dak li għaddej biex tkun vera dwar kif l-istudenti
jinteraġixxu ma 'din l-istruttura tad-data?
UDJENZA: Huma qed tmur biex pop off wieħed.
DAVID Malan: Huma qed tmur biex pop off waħda, nisperaw il-quċċata.
Inkella huwa biss tip ta 'stupid li jmorru it-triq kollha lejn il-qiegħ.
Dritt?
L-istruttura tad-data ma verament jippermettu inti grab-trej qiegħ inqas
faċilment.
Allura hemm dan kurjuż proprjetà lil munzell
li l-aħħar oġġett fil hija se tkun l-ewwel wieħed out.
U xjenzjati tal-kompjuter sejħa dan LIFO-- aħħar fl-ewwel out.
U fil-fatt ma jkollu applikazzjonijiet interessanti.
Mhuwiex neċessarjament bħala ovvju kif xi wħud oħrajn, iżda tista ', tabilħaqq, ikun utli,
u tista ', tabilħaqq, jiġi implimentat fi ftit ta 'modi differenti.
>> Allura wieħed, u fil-fatt, let me ma adsa fis dan.
Ejja nagħmlu dan minflok.
Ejja nħarsu lejn wieħed li kważi l- istess idea, imma hija aktar ġust ftit.
Dritt?
Jekk int wieħed minn dawn subien fann jew bniet li verament jħobb prodotti Apple
u inti woke up fil 03:00 għal-linja up f'xi maħżen
biex tikseb l-aħħar ħafna iPhone, inti jista 'jkollhom fil-kju up bħal dan.
>> Issa kju hija deliberatament ħafna jismu.
Huwa linja għaliex hemm xi ġustizzja miegħu.
Dritt?
Ikun tip ta mirdugħa jekk inti stajt ltqajna hemm l-ewwel fil-Aħżen Apple
imma inti effettivament l-bottommost trej minħabba li l-impjegati Apple allura
pop l-aħħar persuna li attwalment marret fil-linja.
Allura stacks u kjuwijiet, anke jekk funzjonalment dawn qed tip ta 'l-same--
huwa biss dan il-ġbir ta 'riżorsi li l-
hemm għaddej biex jikbru u shrink-- s dan l-aspett ġustizzja miegħu,
inqas fid-dinja reali, fejn l-operazzjonijiet inti eżerċizzju
huma fundamentalment differenti.
A stack-- kju rather-- huwa qal li jkollhom
żewġ operazzjonijiet: kju n u d kju.
Jew tista 'sejħa lilhom kwalunkwe numru ta 'affarijiet.
Imma inti biss tixtieq li jaqbdu l-idea li wieħed qed iżżid
u wieħed huwa finalment jitnaqqas.
>> Issa taħt il-barnuża, kemm il-munzell u kju jista 'jiġi implimentat kif?
Aħna mhux se jmorru fil-kodiċi ta ' minħabba li l-livell ogħla
idea hija tip ta 'aktar ovvji.
I mean, liema do bnedmin do?
Jekk jien l-ewwel persuna fil-Apple Jaħżnu u dan huwa l-bieb ta 'quddiem,
tafu, jien ser toqgħod hawn.
U l-persuna li jmiss tmur toqgħod hawn.
Allura dak struttura tad-data jippresta ruħu għal kju?
>> UDJENZA: A kju.
DAVID Malan: Well, kju.
Sure.
X'iktar?
>> UDJENZA: Lista marbuta.
>> DAVID Malan: A marbuta lista inti jista 'jimplimenta.
U lista marbuta huwa sbieħ għaliex imbagħad li tista 'tikber arbitrarjament twil kif oppost
li jkollhom xi numru fiss ta 'nies fil-maħżen.
Imma forsi numru fiss ta 'postijiet huwa leġittimu.
Għaliex jekk għandhom biss bħal 20 iPhones fl-ewwel jum, forsi
huma jeħtieġu biss firxa ta 'daqs 20 biex jirrappreżenta dak kju, li
huwa biss ngħid issa ladarba nibdew nitkellmu dwar dawn il-problemi ta 'livell ogħla,
inti tista jimplimentawha fi kwalunkwe numru ta 'modi.
U hemm probabbilment biss se tkun kummerċ off fl-ispazju u l-ħin
jew biss fil-kodiċi kumplessità tiegħek stess.
>> What about munzell?
Ukoll, munzell, Rajna wisq jista 'jkun biss dawn trejs.
U inti tista 'timplimenta din firxa.
Iżda f'xi punt jekk inti tuża firxa, x'inhu jiġri lill-trejs
inti qed tipprova li jħott?
Kull dritt.
Int biss ser ikunu jistgħu jmorru daqshekk għolja.
U naħseb fil Mather li qed attwalment minquxa f'dak ftuħ.
Allura fil-fatt, huwa kważi bħall Mather qed tuża
firxa ta 'daqs fiss, għaliex inti tista 'biss
tajbin tant trejs f'dak ftuħ il-ħajt stabbiliti hawn taħt irkopptejn tan-nies.
U hekk li jista 'jkun qal li jkun firxa,
imma nistgħu ċertament jimplimentaw dik b'mod aktar ġenerali ma 'lista marbuta.
>> Ukoll, dak dwar l-istruttura tad-data ieħor?
Let me pull up wieħed ieħor viżwali hawn.
Xi ħaġa simili kif dwar dan wieħed hawn?
Għaliex jista 'dan ikun utli li jkun hemm ma xi ħaġa bħala fancy bħala trie, li
aħna raw kellhom dawn lymph wiesgħa ħafna, kull wieħed minnhom huwa fil-firxa?
Imma x'jiġri jekk nagħmlu xi ħaġa aktar sempliċement, bħal siġra tal-familja iskola antika,
kull wieħed li lymph hawn huwa biss ħażna numru.
Minflok ta 'isem jew dixxendent huwa biss ħażna numru bħal dan.
>> Ukoll, il-jargon nużaw fil strutturi ta 'dejta huwa kemm jipprova
u siġar, fejn trie, għal darb'oħra, huwa wieħed li l lymph huma arrays biss,
għadu dak li inti tista ' jużaw mill-iskola grad
meta inti ssir familjari weraq tree-- u l-għerq
tas-siġra u t-tfal ta 'l- ġenitur u aħwa tiegħu.
U aħna tista 'timplimenta siġra, per eżempju, bħala sempliċement bħala dan.
A siġra, jekk bħala node, wieħed mill dawn ċrieki li għandha numru,
mhuwiex ser ikollhom wieħed pointer, iżda tnejn.
U hekk kif inti żid tieni pointer, inti
jistgħu attwalment issa jagħmlu sort ta 'data żewġ dimensjonijiet
strutturi fil-memorja.
Ħafna bħal żewġ dimensjonijiet array, inti tista
jkollhom tip ta 'żewġ dimensjonijiet listi marbuta iżda dawk
li jsegwu mudell fejn hemm l-ebda ċikli.
Huwa verament siġra ma 'wieħed mod nanniet up hawn u mbagħad
xi ġenituri u t-tfal u neputijiet u great-neputijiet.
u ibqa 'sejjer hekk.
>> Imma x'hemm verament pulita dwar dan ukoll, biss biex tease inti ma 'ftit ta' kodiċi,
recursion irtirar minn awhile lura, fejn
tikteb funzjoni li s-sejħiet innifsu.
Din hija opportunità sabiħa biex jimplimentaw xi ħaġa
bħal recursion, għaliex jikkunsidraw dan.
>> Din hija siġra.
U stajt kien anali ftit mal-mod kif I tpoġġi l-interi fit-triq.
Tant li hija għandha speċjali name-- siġra tfittxija binarja.
Issa aħna widnejna binarja tfittxija, imma tista 'inti
xogħol b'lura mill-isem dan ħaġa l-?
X'inhu l-mudell ta 'kif I mdaħħla l-interi fis din is-siġra?
Mhuwiex arbitrarja.
Hemm xi mudell.
Yeah.
>> UDJENZA: dawk iżgħar fuq ix-xellug.
>> DAVID Malan: Yeah.
Dawk iżgħar huma fuq ix-xellug.
Oħrajn akbar huma fuq il-lemin.
Tali li dikjarazzjoni vera hija ġenitur huwa akbar minn tifel xellug tagħha,
iżda inqas minn wild dritt tagħha.
U li waħdu huwa saħansitra definizzjoni verbali rikursivi
għaliex inti tista 'tapplika dak istess loġika għal kull node
u biss qigħan out, f'każ bażiku jekk inti
se, meta inti hit waħda il-weraq, biex ngħidu hekk,
fejn leave m'għandha l-ebda tfal aktar.
>> Issa kif tista 'issib l-għadd 44?
Inti tibda fil-għerq u jgħidu, hm.
55 mhuwiex 44 So do Irrid immur dritt jew għandi tixtieq li tmur xellug?
Well, ovvjament inti tixtieq li tmur xellug.
U hekk huwa bħad-telefon Eżempju ktieb fit-tfittxija binarja
b'mod aktar ġenerali.
Iżda aħna qed jimplimentawh issa ftit aktar dinamiku
minn firxa tista 'tippermetti.
U fil-fatt, jekk inti trid tfittex lejn il-kodiċi, ewwel daqqa t'għajn żgur.
Jidher qisu mazz sħiħ ta 'linji.
Iżda huwa beautifully sempliċi.
Jekk inti tixtieq li jimplimentaw funzjoni imsejħa tfittxija li l-iskop fil-ħajja
huwa ta 'tiftix għal valur bħal n, integer,
u int għadda fi pointer-- wieħed pointer għall-node ta 'l-għeruq,
pjuttost, ta 'dak siġra li minnha inti tista 'aċċess kollox,
avviż kif jinftiehem inti tista 'timplimenta l-loġika.
Jekk siġra huwa null, ovvjament mhuwiex hemmhekk.
Ejja biss ritorn foloz.
Dritt?
Jekk inti jagħtih xejn, hemm xejn hemmhekk.
>> Inkella, jekk n hija inqas minn vleġġa siġra n-- issa vleġġa n,
recall aħna introdotti super qosor l-oħra jum,
u li biss ifisser de-referenza tal- pointer u ħarsa lejn il-qasam imsejħa n.
Allura dan ifisser jmorru hemm u tħares lejn il-qasam imsejħa n.
Hekk jekk n, il-valur int tingħata, hija inqas mill-valur fil-numru sħiħ siġar,
fejn do inti tixtieq li tmur?
Lejn ix-xellug.
>> Allura avviż-recursion.
Jien returning-- mhux veru.
Mhux falza.
Jien jirritornaw x'ikun ir-risposta huwa minn sejħa għal myself, li jgħaddi
n darb'oħra, li huwa żejjed, imma dak kemmxejn differenti issa?
Kif am I jagħmlu l-problema iżgħar?
Jien tgħaddi fit bħala t-tieni argument, mhux l-għerq tal-siġra,
iżda l-wild xellug f'dan il-każ.
Hekk jien tgħaddi fil-wild xellug.
>> Sadanittant, jekk n hija akbar minn l-node jien bħalissa tħares lejn,
I tfittex il-lemin.
Inkella, jekk l-siġra ma huwiex null, u jekk l-element mhuwiex lejn ix-xellug
u mhuwiex għad-dritt, dak li huwa wonderfully il-każ?
Imxejna attwalment jinstabu l-node fil kwistjoni, u għalhekk nerġgħu lura veru.
>> Allura aħna ħadthom biss scratched-wiċċ issa xi wħud minn dawn l-istrutturi tad-data.
Fil problema sett ħamsa tkun taf jesploraw dawn għadhom ulterjuri,
u tkun taf tkun tingħata disinn tiegħek għażla ta 'kif imorru dwar dan.
What I tixtieq li jikkonkludu fuq huwa biss 30 sekonda teaser
ta 'dak li jistenna ġimgħa d-dieħla u lil hinn.
>> Kif aħna begin-- Thankfully inti tista think-- transizzjoni tagħna bil-mod
mid-dinja ta 'C u t'isfel dettalji tal-implimentazzjoni livell,
għal dinja li nistgħu tieħu għall mogħti li xi ħadd ieħor ħa finalment
din id-dejta implimentati strutturi għalina,
u aħna ser tibda biex jifhmu l- dinja reali mezzi ta 'implimentazzjoni
programmi fuq l-internet u websajts aktar ġenerali
u wkoll is-sigurtà ħafna implikazzjonijiet li Imxejna biss
bdew tobrox il-wiċċ ta '.
Hawnhekk huwa dak li jistenna us fil-jiem li ġejjin.
>> [Daqq ta 'video]
>> -He Daħal bil-messaġġ, bi protokoll kollu tiegħu stess.
Huwa daħal għal dinja ta krudili firewalls, routers uncaring,
u l-perikli ferm agħar milli mewt.
Hu mgħaġġel.
Hu b'saħħtu.
Hu TCP / IP, u hu ltqajna l-indirizz tiegħek.
"ġellieda tal-Net."
[END daqq ta 'video]
DAVID Malan: Niġu ġimgħa d-dieħla.
Aħna se tara inti mbagħad.
[Daqq ta 'video]
-u Issa, "Ħsibijiet Deep" billi Daven Farnham.
-David Dejjem jibda lectures ma, "Kull dritt."
Għaliex ma, "Hawn is-soluzzjoni għal sett problema din il-ġimgħa "
jew "Aħna qed tagħti kollha inti A?"
[Laughing]
[END daqq ta 'video]