>> DAVID Malan: zote haki.
Karibu tena kwa CS50.
Huu ni mwanzo wa wiki 8.
Na kukumbuka kwamba kuweka tatizo 5 kumalizika na kidogo kidogo ya changamoto.
Hivyo kuchukua wewe zinalipwa yote ya yako mafundisho Fellows na picha ya CA
katika faili card.raw, wewe ni chakula cha mchana kwa sasa kupata yote ya watu hao, na
mshindi mmoja bahati kutembea nyumbani na mmoja juu ya mambo hayo, mwendo leap
kifaa kwamba unaweza kutumia kwa ajili ya fainali miradi, kwa mfano.
>> Hii, kila mwaka, husababisha kidogo ya creepiness.
Na hivyo nilifikiri nini ningependa kufanya ni kushiriki na wewe baadhi ya maelezo ambayo
gone na kurudi zaidi ya orodha ya wafanyakazi wa marehemu.
Kwa mfano, tu jana usiku quote, unquote, kutoka mmoja wa wafanyakazi
wanachama, "Mimi tu alikuwa mwanafunzi yangekuwa mlango wangu kwa kuchukua picha na mimi.
Stalkers, nawaambia ". Started mbali haki maelezo na kisha sisi wakiongozwa
kwenye, saa au hivyo baadaye, "Mimi nilikuwa mwanafunzi wa kusubiri kwa ajili yangu baada ya sehemu ya
naye alikuwa na majina yetu wote na picha juu ya baadhi ya karatasi. "haki zote.
Hivyo kupangwa, lakini si wote kwamba creepy bado.
>> Basi, "Nilikuwa nje ya mji mwishoni mwa wiki hii, na niliporudi nyuma, kulikuwa na mtu mmoja katika
yangu
chumba cha kulala ". [kicheko]
DAVID Malan: Next quote kutoka kwa wafanyakazi mwanachama, "mwanafunzi alikuja nyumba yangu katika
Somerville saa 4:00 asubuhi hii ". Next wafanyakazi, "I got hoteli yangu katika San
Francisco na mwanafunzi alikuwa kusubiri kwa mimi katika kushawishi na DSLRs tatu. "
Aina ya kamera.
"Mimi si hata juu ya wafanyakazi hii muhula, lakini mwanafunzi kukatika ndani ya nyumba yangu hii
asubuhi na ilirekodi yote na kioo Google ". Na kisha mwisho,
"Angalau watu 12 walikuwa shauku wanasubiri kwa mimi wakati mimi got nje ya yangu
Limo, na kisha mimi
woke up ". haki zote.
Hivyo kati ya picha, kama unaweza kukumbuka, ni huyu hapa, ambao unaweza
wapate kujua kama Milo Banana, ambaye anaishi na Lauren Carvalho, mkuu wetu
kufundisha wenzangu.
Milo, Milo, kuja hapa mvulana.
Milo.
Akili wewe, yeye amevaa Google kioo, hivyo tutaweza kuonyesha wote wa hii baada ya.
Hivyo hii Milo ni kama ungependa kuchukua picha pamoja naye baadaye.
Kama Ningependa kwa kuangalia nje saa watazamaji huko.
OK.
Hiyo ni nzuri Footage.
Naam, Milo Banana.
Oh, si kufanya hivyo.
>> [Kicheko]
>> OK.
Hivyo basi neno juu ya kile uongo mbele, kwa sababu kama sisi kuanza mpito,
wiki hii hasa, kutoka C katika amri line mazingira kwa PHP na
JavaScript na SQL na HTML na CSS katika mazingira ya mtandao msingi, tutaweza kuwa
kuwaandaa kwa yote maarifa zaidi kwa
uwezo wa mwisho miradi.
Kuelekea mwisho kwamba, bila shaka ina utamaduni wa kufanya semina ambayo
ni juu ya mada tangential na bila shaka.
Mengi sana kuhusiana na programu na programu ya maendeleo na kadhalika, lakini
si lazima Kugundua na Bila shaka ya mwenyewe mtaala.
>> Hivyo kama unaweza kuwa na nia moja katika au zaidi ya semina ya mwaka huu,
kujiandikisha katika cs50.net/seminar.
Kuna wazee semina saa cs50.net/seminars.
Na juu ya orodha ya majina ya hivi sasa kwa mwaka huu ni Amazing Programu Mtandao na Ruby juu ya
Reli, ambayo ni mbadala lugha ya PHP.
Computational Linguistics.
Kuanzishwa kwa iOS, ambayo ni jukwaa hiyo ni kutumika kwa ajili ya iPhone na
iPad maendeleo.
JavaScript kwa Programu ya Mtandao, tutaweza cover kwamba, lakini katika semina hii, itabidi kwenda
kwa undani zaidi.
>> Leap Motion, hivyo tutaweza kweli kuwa baadhi ya wa marafiki zetu kutoka Motion Leap,
kampuni yenyewe, kujiunga nasi.
Kesho, kwa kweli, kwa kutoa mikono juu ya semina, ikiwa
wa maslahi na wewe.
Meteor.js, mbinu mbadala kwa ajili ya kutumia JavaScript si katika browser,
lakini juu ya server.
Node.js, ambayo ni mengi sana katika mshipa kuwa vilevile.
Sleek Android Design.
Admin kuwa mbadala maarufu sana kwa Simu iOS na Windows
na simu nyingine majukwaa.
Na Mtandao wa Usalama Active Ulinzi.
>> Hivyo katika kweli, kama ungependa kushiriki katika hii, napenda
kufanya kumbuka ya hii.
Sisi ni furaha sana kusema kwamba marafiki zetu katika Leap
Mwendo, ambayo ni startup -
kifaa hiki kweli alikuja tu nje miezi michache iliyopita -
kwa neema walichangia 30 ya vifaa kama hivyo darasani kwa kama wanafunzi wengi, kama
Ningependa kukopa vifaa kuelekea mwisho wa muhula na kuitumia kwa ajili ya
halisi ya mwisho wa mradi.
Wao kusaidia idadi ya lugha.
Hakuna hata mmoja wao C, hakuna hata mmoja wao PHP, hivyo kutambua moja au zaidi ya semina hizi
ili kuthibitisha ya riba.
Na wote watakuwa zingine katika tukio hilo kuwa wewe si uwezo
kuhudhuria katika mtu.
ratiba itatangazwa kupitia email kama sisi kuimarisha vyumba.
>> Na Mwisho, kama kwenda kwa projects.cs.50.net, hii ni tovuti
sisi kudumisha kila mwaka kwamba sisi kukaribisha folks kutoka kwa jamii, Kitivo,
idara, wafanyakazi, na wote katika nje ya CS50 kwa
kupendekeza mawazo mradi.
Mambo ya maslahi ya makundi ya mwanafunzi.
Mambo ya maslahi kwa idara.
Hivyo kugeuka huko kama wewe ni zinakabiliwa na kutokuwa na uhakika kama kwa nini
mwenyewe angependa kukabiliana.
>> Hivyo mwisho wakati sisi ilianzisha arguably ngumu zaidi kuliko data muundo tunatarajia
kuonekana katika kipindi cha wiki.
Tunatarajia wamekuwa kutumia arrays pretty furaha kama manufaa kama
simplistic data muundo.
Kisha sisi ilianzisha haya, ambayo bila shaka ni wanaohusishwa orodha.
Na nini ilikuwa moja ya motisha kwa kuanzisha muundo huu data?
Yeah?
Nini hiyo?
>> Watazamaji: Dynamic kawaida.
>> DAVID Malan: Dynamic kawaida.
Hivyo ambapo katika safu, una kujua ukubwa wake mapema wakati
kutenga yake.
Katika orodha wanaohusishwa, huna kujua kwamba.
Unaweza tu malloc, au zaidi kwa ujumla, kutenga ziada
nodi, ili kuzungumza, wakati wowote wanataka kuingiza data zaidi.
Na node hana predetermined maana.
Ni tu generic mrefu kuelezea baadhi ya aina ya chombo kwamba sisi ni
kutumia data katika muundo wetu wa kuhifadhi baadhi ya bidhaa ya riba, ambayo katika hii
kesi kutokea kwa kuwa integers.
>> Lakini kuna siku zote tradeoff.
Ili tuweze kupata nguvu ukubwa wa data muundo, lakini kile bei gani sisi kulipa?
Nini upande wa chini ya orodha zilizounganishwa?
Yeah?
>> Watazamaji: Inahitaji kumbukumbu zaidi.
>> DAVID Malan: Ni inahitaji zaidi kumbukumbu, jinsi gani hasa?
>> Watazamaji: [inaudible].
>> DAVID Malan: Hasa.
Hivyo sasa tuna kuyatumia na kuchukua ziada kumbukumbu kwamba sisi awali
hakuwa na haja, kwa sababu faida wa safu, bila shaka, ni kwamba
kila kitu ni contiguous, nyuma nyuma kwa nyuma, ambayo
inakupa upatikanaji random.
Kwa sababu tu kwa kutumia mabano mraba nukuu, au zaidi kitaalam pointer
hesabu, rahisi sana Aidha, unaweza kupata yoyote
vipengele katika wakati mara kwa mara.
Na kwa kweli, hiyo ni aina ya hinting katika mwingine bei ya kwamba sisi ni kulipa na
wanaohusishwa orodha.
>> Nini kinatokea kwa wakati mbio ya kitu kama Search, kama nataka
kupata baadhi ya thamani na ndani ya ya orodha wanaohusishwa?
Je, muda wangu kuwa mbio?
Kubwa O ya n.
Kama ni kwa namna?
Nini kama muundo wa data ni sorted?
Naweza kufanya vizuri zaidi kuliko kubwa O ya n kwa ajili ya kutafuta?
Hapana, kwa sababu katika hali mbaya ni nguvu vizuri sana kutatuliwa, lakini idadi
wewe ni kuangalia kwa wapate kuwa kubwa.
Inaweza kuwa ni namba 100, ambayo kinaweza kutokea kwa kuwa wote
njia mwishoni.
Na kwa sababu unaweza tu kupata wanaohusishwa orodha hii katika utekelezaji na
njia ya nodi yake ya kwanza, wewe ni bado aina ya nje ya bahati.
Una tembeeni jambo zima kutoka mwanzo hadi mwisho ili kupata
kwamba thamani kubwa kama 100.
Au kuamua kama ni hata huko.
>> Hivyo hatuwezi kufanya kile algorithm katika data muundo kwamba inaonekana kama hii?
Hatuwezi kufanya tafuta binary, kwa sababu binary tafuta required kwamba tulikuwa
random kupata.
Tunaweza tu leap kutoka eneo kwa mahali bila ya kuwa na kufuata
makombo ya chakula hizi katika fomu ya kuyatumia haya yote.
>> Sasa, jinsi gani sisi kutekeleza hili?
Naam, kama sisi kwenda kwa screen hapa, kama tunaweza haraka reimplement data hii
muundo -
mwandiko wangu si wote kwamba kubwa hapa, lakini tutaweza kujaribu.
Hivyo typedef struct, na nini mimi unataka kuita jambo hili hapa juu?
Nodi.
Hivyo mimi itabidi kupata yetu ilianza.
Na sasa, nini mahitaji ya kuwa ndani ya muundo wa data kwa kuwa moja moja
wanaohusishwa orodha?
Wangapi mashamba?
>> Hivyo mbili.
Moja ni rahisi pretty.
Hivyo int n.
Na tungeweza kuwaita kitu n tunataka, lakini ni lazima kuwa int kama sisi ni
kutekeleza orodha wanaohusishwa kwa ints.
Na sasa ni nini pili shamba kuwa?
Struct nodi *.
Hivyo kama mimi kufanya struct nodi *, na kisha mimi unaweza kuita hii pia chochote mimi nataka,
lakini tu kuwa wazi Mimi nitakuita ijayo, kama tumekuwa kufanya.
Na basi mimi itabidi karibu yangu braces curly.
>> Na sasa, kama mara ya mwisho, Mimi kuweka nodi chini hapa.
Lakini kama mimi nina kutangaza hii ni kama nodi, kwa nini mimi bother kuwa hivyo
verbose hapa katika kutangaza struct nodi * ijayo, kinyume
tu * nodi ijayo?
Yeah?
>> Watazamaji: [inaudible].
>> DAVID Malan: Hasa.
Hasa.
Sababu C kweli inachukua wewe halisi na anaona tu ufafanuzi wa nodi
njia ya chini hapa, huwezi rejea ni hapa juu.
Hivyo tuna aina hii ya preemptive tamko hapa, ambayo ni admittedly
zaidi verbose.
Struct nodi, kwamba maana ya sasa tunaweza kupata huduma hiyo
ndani ya muundo data.
>> Na kama kando, kwa sababu hii ni kuwa zaidi kidogo subjective sasa,
nyota wanaweza kitaalam kwenda hapa, inaweza kwenda hapa, inaweza
hata kwenda katikati.
Tumekuwa kupitishwa, katika mwongozo style kwa Bila shaka, mkataba wa kuweka
nyota haki ya karibu na data aina, ambayo katika kesi hii,
itakuwa struct nodi.
Lakini kutambua katika mengi ya vitabu vya kiada na marejeo online, waweza kweli
kuona upande wa pili.
Lakini tu kutambua kwamba wote wawili kwa kweli kazi na wewe lazima tu kuwa
thabiti.
>> Wote haki.
Ili kwamba ilikuwa tamko wetu ya nodi struct.
Lakini basi sisi kuanza kufanya zaidi kisasa mambo.
Kwa mfano, sisi aliamua kuanzisha kitu kama meza hash.
Hivyo hapa ni meza hash ya n kawaida, indexed kutoka 0 juu kushoto na n
minus 1 juu ya chini kushoto.
Hii inaweza kuwa hash meza kwa ajili ya kitu chochote.
Lakini ni aina gani ya mambo gani sisi majadiliano kuhusu kutumia meza hash kwa?
Hifadhi ya nini?
>> Majina.
Tunaweza kufanya majina kama tulivyofanya wakati wa mwisho.
Na kwa kweli, unaweza kuhifadhi kitu.
Na tutaweza kuona hii tena katika PHP na katika JavaScript.
meza hash ni aina nzuri ya Uswisi Jeshi kisu kwamba utapata kuhifadhi
pretty kiasi chochote unataka ndani ya hivyo kwa kujihusisha funguo na maadili.
Funguo na maadili.
>> Sasa katika kesi hii rahisi, yetu funguo ni idadi tu.
Sisi ni kutekeleza hash meza kama safu.
Na hivyo funguo ni 0, 1, 2, na kadhalika.
Na hivyo sisi, kama wanadamu, aliamua mwisho wiki kwamba unajua nini, kama sisi ni
kwenda majina kuhifadhi, hebu tu kiholela, lakini pretty sababu,
kudhani kwamba Alice, jina, tu kuwa indexed katika 0.
Na Bob, jina B, itakuwa indexed ndani ya 1, na kadhalika.
Hivyo tulikuwa ramani kati ya pembejeo, ambayo ni ya masharti, na hash
maeneo, ambayo ni namba.
>> Hivyo mchakato kwamba ni ujumla inayojulikana kama kazi hash, na unaweza kweli
kutekeleza katika kanuni.
Kama nilitaka kutekeleza kazi hash kwamba anafanya nini hasa sisi
tu ilivyoelezwa kutoka wakati wa mwisho, mimi ili kutangaza kwamba inachukua kazi, kama
pembejeo kwa mfano -
na hebu kufanya hili juu ya hili screen zaidi ya hapa.
Kama nilitaka kutekeleza hash kazi, mimi wanaweza kusema
kitu kama hiki.
>> Ni kwenda na kurudi int.
Ni kwenda kuitwa hash, na ni kwenda kukubali kama hoja
uzi, au tunaweza kuwa sawa zaidi sasa, na kusema * Char, tutaweza kuiita s.
Na kisha hii kazi yote ina nini, hatimaye, ni kurudi int.
Sasa, jinsi gani kwamba nguvu kuwa hivyo wazi.
Mimi nina kwenda kutekeleza mpango huu bila kuunda wa makosa ya kuangalia hivi sasa.
Mimi tu kwenda kwa upofu kusema, kurudi chochote ni saa s mabano 0, bala,
hebu sema, mji mkuu semicolon.
>> Kabisa kuvunjwa.
Ni si kamili kwa sababu moja, nini kama s ni null?
Mambo mabaya ni kwenda kutokea.
Mbili, nini kama barua ya kwanza katika hii jina si herufi?
Kwamba si kwenda na kurejea nje vizuri ama.
Inaweza kuwa ni barua lowercase au si barua wakati wote.
Hivyo kabisa chumba kwa ajili ya kuboresha hapa, lakini hii ni wazo la msingi.
>> Nini sisi ilivyoelezwa wiki iliyopita kwa maneno kama tu mchakato wa kuchora ramani Alice
0 na Bob na 1 inaweza kuwa walionyesha hakika zaidi formulaically kama C
kazi hapa.
Kuitwa tena hash, inachukua kamba kama pembejeo, na kisha kwa namna fulani haina kitu
na kwamba pembejeo kuzalisha pato.
Si tofauti na maelezo yetu nyeusi sanduku kwamba tumekuwa muda mrefu kufanyika.
Sijui jinsi hii inaweza kuwa kufanya kazi chini ya Hood.
>> Kwa tatizo seti 6, moja ya changamoto ni kwa ajili ya wewe kuamua nini
itakuwa kazi yako hash kuwa?
Nini kinaendelea kuwa ndani ya kuwa nyeusi sanduku, na pengine, utakuwa ni
kidogo ya kuvutia zaidi kuliko huu, na dhahiri zaidi kukabiliwa na kosa
kuangalia zaidi kuliko huu hasa utekelezaji.
>> Lakini matatizo yanaweza kutokea, sawa?
Kama tuna muundo wa data kama vile hii moja, nini moja ya matatizo
unaweza kukimbia katika baada ya muda kama wewe kuingiza zaidi na zaidi katika majina
hash meza?
Kupata migongano, haki?
Nini kama una Alice na Haruni, watu wawili ambao majina kilichotokea
kuanza na?
Kwamba anaomba swali, ambapo kuweka pili vile jina?
>> Naam, unaweza naively tu ya kuweka ambapo Bob ni mali, lakini basi ni Bob
aina ya Star kama kujaribu kuingiza jina lake ijayo na
hakuna chumba kwa ajili yake.
Hivyo unaweza kuweka Bob ambapo Charlie ni, na unaweza kufikiria hii haraka sana
kukabidhi katika kidogo ya fujo.
Kitu linear katika mwisho, ambapo tu na kutafuta jambo zima
kuangalia kwa Alice au Bob au Haruni au Charlie.
>> Hivyo badala sisi mapendekezo, badala ya linearly uchunguzi kwa ajili ya maeneo ya wazi
na plopping majina huko, sisi mapendekezo ya mbinu fancier.
meza hash kutekelezwa bado na safu ya fahirisi, lakini aina ya data ya
wale fahirisi sasa walikuwa kuyatumia.
Kuyatumia kwa nini?
Kuyatumia kwa orodha wanaohusishwa.
>> Sababu kukumbuka kwamba orodha wanaohusishwa ni kweli tu pointer nodi, na
nodi ana shamba ijayo, na kwamba nodi ana shamba ijayo, na kadhalika.
Hivyo sasa unaweza kufikiria safu hii ya upande wa mkono wa kushoto wa meza hash kama
inayoongoza kwa orodha wanaohusishwa.
faida ya ambayo ni kama kupata mgongano kati ya Alice na Haruni,
unafanya nini na pili vile mtu?
Wewe tu ambatisha kwake kwa mwisho, au hata mwanzo
ya kwamba orodha wanaohusishwa.
>> Na kweli, hebu tu Tambi kupitia kwamba kwa ajili tu ya pili.
Ambapo ingekuwa kufanya maana zaidi?
Kama mimi kuingiza Alice na yeye kuishia hadi saa mahali ya kwanza, basi mimi kujaribu
kuingiza jina la Haruni, na kuna wazi mgongano, lazima mimi kuweka
naye mwanzoni ya orodha wanaohusishwa?
Hiyo ni katika eneo hilo kwanza, au mwisho?
>> Watazamaji: [inaudible].
>> DAVID Malan: OK.
Nikasikia mwanzo.
Kwa nini mwanzoni?
>> Watazamaji: [inaudible].
>> DAVID Malan: OK.
Ni herufi, hivyo kwamba ni nzuri.
Hiyo ni mali nzuri.
Itakuwa kuokoa yangu baadhi ya wakati uwezekano.
Itakuwa si basi mimi kufanya binary tafuta, lakini mimi wanaweza angalau kuwa na uwezo wa kuvunja nje
ya kitanzi kama mimi kutambua, vizuri, mimi nina njia zamani walikuwa Haruni itakuwa katika hii
yamepangwa orodha wanaohusishwa.
Sina kupoteza muda wangu kuangalia njia yote hadi mwisho.
Hivyo hiyo ni ya kuridhisha.
Kwa nini kingine ili unataka kuingiza jina mbumburisho saa
mwanzo wa orodha?
Nini hiyo?
>> Watazamaji: [inaudible].
>> DAVID Malan: Ni inaweza kuchukua muda mrefu kupata mwisho wa orodha.
Na kwa kweli, tena na tena.
majina zaidi ya kuingiza kwamba kuanza na, tena kwamba
mnyororo ni kwenda kupata.
tena kwamba wanaohusishwa orodha ni kwenda kupata.
Hivyo wewe ni kweli tu kupoteza muda wako.
Labda wewe ni bora zaidi kudumisha mara kwa mara kuingizwa wakati, kubwa O ya 1,
na daima kuweka jina mbumburisho saa mwanzo wa orodha wanaohusishwa,
na si wasiwasi sana kama kuhusu kuchagua.
>> Nini jibu bora?
Ni wazi.
Ni aina ya unategemea nini usambazaji ni, nini muundo
ya majina wewe ni kuingiza.
Siyo lazima Jibu la wazi.
Lakini hapa, tena, ni nafasi ya kubuni.
>> Hivyo sisi basi inaonekana katika jambo hili, ambayo ni kweli nafasi nyingine kubwa
kwa ajili ya p-seti 6.
Na kutambua, kama wewe si tayari, Zamyla dives katika wawili hawa, hash
meza na inajaribu, kwa undani zaidi.
Na walkthrough video iliyoingia katika spec p-kuweka.
Hii ilikuwa trie -
T-R-I-E. Na nini ilikuwa ya kuvutia kuhusu huu ni kwamba wakati mbio
ya kutafuta kwa jina, kama Maxwell mara ya mwisho, ilikuwa kubwa O ya nini?
Nini hiyo?
>> Watazamaji: idadi ya barua.
>> DAVID Malan: Idadi ya barua.
Nikasikia mambo mawili.
Idadi ya herufi na wakati mara kwa mara.
Basi hebu kwenda na kwamba kwanza.
idadi ya herufi.
Naam, hii muundo wa data, kukumbuka, ni kama mti, mti wa familia, kila moja ya
nodes ambaye ni alifanya juu ya arrays.
Na wale arrays ni kuyatumia na wengine vile nodes, au nyingine kama
arrays katika mti.
>> Hivyo kama sisi alitaka kisha kuamua kama Maxwell ni katika hapa, mimi ili kwenda
na safu ya kwanza, katika sana juu ya mti, mizizi kinachojulikana, juu ya
trie, na kisha kufuata pointer m, kisha pointer, kisha x,
w, e, l, l.
Na kisha wakati mimi kuona baadhi ya alama maalum, ulionyehsa hapa kama pembetatu.
Katika kanuni utaona sisi kupendekeza kwamba wewe kutekelezwa kama bool, kusema tu ndiyo
au hakuna, neno ataacha hapa.
>> Naam, mara moja tumeenda kwa M-A-X-W-E-L-L, anahisi kama saba, labda
nane kama sisi kwenda moja siku za nyuma, nane hatua ya kupata Maxwell.
Au hebu kuiita K. Lakini kukumbuka mwisho wakati, mimi alisema kwamba kama kuna
realistically urefu upeo juu ya neno, kama 40-baadhi ya isiyo ya kawaida wahusika,
upeo urefu ina maana thamani mara kwa mara.
Hivyo kweli, ndiyo, ni kitaalam kubwa O wa 8 au 7, au O kweli kubwa ya K. Lakini
kama kuna cap finite juu ya nini K inaweza kuwa, ni mara kwa mara.
Na hivyo ni kubwa O ya 1 katika mwisho wa siku.
>> Si katika ulimwengu wa kweli.
Si wakati kwa kweli kuanza kuangalia saa yako kama mbio ya mpango wako.
Ni kabisa kwenda kuwa kidogo polepole zaidi kuliko kweli mara kwa mara
muda na hatua moja.
Ni kwenda kuwa saba au nane hatua, lakini bado hiyo ni mengi, bora
kuliko algorithm kama kubwa O ya n kwamba inategemea ukubwa wa nini katika
data muundo.
>> Taarifa kichwa hapa ni tunaweza kuingiza zaidi ya milioni majina ndani ya hii
data muundo, lakini jinsi wengi zaidi hatua ni kwenda kuchukua sisi kupata
Maxwell katika kesi hiyo?
Hakuna.
Yeye ni unaffected.
Na hadi sasa, sidhani tumeona mfano wa muundo wa data au
algorithm kwamba ilikuwa kabisa unaffected na nje
tabia kama hiyo.
Lakini hii inaweza kuwa ya ajabu.
Hii haiwezi kuwa suluhisho pekee kwa p kuweka-
>> Na si.
Hii si lazima data muundo unapaswa wanaamua kwenda,
kwa sababu kama meza hash, tradeoff.
Nini bei ya kulipa hapa?
Kumbukumbu.
I mean, hii ni za mauaji kiasi cha kumbukumbu.
Na huwezi kabisa kuona hapa kwa sababu mwandishi wa picha hii
wazi truncated yote ya arrays, na sisi siyo kuona kura ya na
B na C na Q na Y ya na Z katika arrays haya.
Lakini wao uko pale.
>> Kila moja ya nodi hiyo ni safu nzima ya baadhi ya 26 au zaidi ka, kila aina ya
ambayo inawakilisha barua.
27 katika kesi yetu, ili tuweze kusaidia apostrophes katika kuweka tatizo.
Hivyo mfumo huu data ni kweli, kweli mnene na upana.
Na kwamba peke yake inaweza kuishia kupunguza mambo ya chini, au angalau gharama wewe
mengi zaidi nafasi.
Lakini tena, tunaweza kuchora kulinganisha hapa.
>> Kumbuka wakati nyuma, sisi mafanikio kiasi zaidi ya kusisimua mbio wakati katika kuchagua
wakati sisi kutumia kuunganisha aina, lakini bei ya sisi kulipwa kufikia n logi n kwa kuunganisha
aina required kwamba sisi kutumia zaidi nini rasilimali?
Nafasi zaidi.
Sisi zinahitajika safu ya sekondari kwa nakala watu ndani, kama
tulivyofanya hapa juu ya hatua.
Hivyo tena, hakuna washindi wazi, lakini tu subjective kubuni
maamuzi kufanywa.
>> Wote haki.
Basi vipi kuhusu hili?
Mtu yeyote kutambua ambayo D-Hall?
OK.
Hivyo sisi watatu kufanya.
Mather House.
Hivyo hii ni kwa dining Mather ya.
Mimi itabidi bet kumbi zote dining kuwa mwingi wa sania kama hii.
Na hii ni kweli mwakilishi ya kitu tumekuwa
wazi kuonekana tayari.
Sisi kuitwa ni halisi stack.
Na stack, katika suala la wako kumbukumbu ya kompyuta, ni mahali ambapo takwimu huenda
wakati kazi ni kuitwa.
>> Kwa mfano, ni aina gani ya mambo kwenda juu ya stack kwa heshima na
kumbukumbu mpangilio tumekuwa kujadiliwa katika kipindi cha wiki?
Nini hiyo?
>> Watazamaji: Wito kwa kazi.
>> DAVID Malan: Samahani.
>> Watazamaji: Wito kwa kazi.
>> DAVID Malan: Wito kwa kazi, lakini hasa, nini ndani ya kila moja ya
wale muafaka?
Ni aina gani ya mambo?
Yeah.
Hivyo mitaa vigezo.
Wakati wowote sisi zinahitajika baadhi ya kuhifadhi mitaa, kama hoja, au int mimi, au int
temp, au chochote mitaa kutofautiana ni, tumekuwa
kuweka kwamba kwenye stack.
Na sisi kuiita stack kwa sababu ya kwamba wazo layering.
Aina tu ya mechi up na hali halisi, dhana yake.
>> Lakini zinageuka kuwa stack unaweza pia kuonekana kama muundo wa data,
mbadala kwa safu, mbadala kwenye orodha ya wanaohusishwa.
Kitu conceptually zaidi ya kuvutia kwamba bado anaweza kuwa
kutekelezwa kwa kutumia aidha ya wale mambo, lakini ni aina tofauti ya
data muundo wa kusaidia, kwa kweli, mbili tu shughuli.
Lakini unaweza kuongeza juu ya fancier sifa zaidi ya hizi.
Lakini haya ni mambo ya msingi -
kushinikiza na pop.
>> Na wazo na stack ni kwamba kama mimi hapa, na au bila Annenberg
kujua, tray kutoka mlango wa pili na namba 9 juu yake.
Hivyo tu int.
Na mimi nataka hii kushinikiza kwenye data muundo, ambayo kwa sasa ni tupu.
Fikiria hili chini ya stack.
Napenda kushinikiza hii namba 9 kwenye stack, na sasa ni haki pale.
>> Lakini jambo kuvutia kuhusu stack ni kwamba kama mimi sasa wanataka kushinikiza
baadhi ya thamani ya wengine, kama 17, na mimi kushinikiza hii kwenye stack, mimi naenda kufanya
tu angavu kitu, Mimi tu kwenda ili kuweka haki ambapo sisi binadamu
itakuwa kutega kuweka, juu.
Lakini nini kuvutia sasa ni, jinsi gani mimi kupata saa 9?
Unajua, mimi si bila juhudi baadhi.
>> Basi nini kuvutia kuhusu stack ni kwamba kwa kubuni,
ni data LIFO muundo.
Silly njia ya kuelezea mwisho, kwanza nje.
Hivyo idadi ya mwisho katika wakati huu ilikuwa 17.
Hivyo kama nataka pop kitu mbali ya stack, inaweza tu kuwa 17.
Hivyo kuna utaratibu lazima ya shughuli hapa, ambapo bidhaa mwisho
katika ina kuwa ya kwanza mmoja nje.
Hivyo kifupi, LIFO.
>> Hivyo kwa nini huenda hii kuwa muhimu?
Ni mazingira yao ambayo wewe d wanataka muundo wa data kama hii?
Naam, ni hakika imekuwa muhimu ndani ya kompyuta.
Hivyo uendeshaji wa mifumo ya wazi kutumia hii aina ya data muundo kwa mwingi.
Tutaweza pia kuona wazo moja linapokuja kurasa za mtandao.
Hivyo wiki hii na wiki ijayo na zaidi, na kama wewe kuanza kutekeleza mtandao
kurasa katika lugha inayoitwa HTML, unaweza kweli matumizi ya muundo wa data kama
hii kuamua kama ukurasa ni ipo.
Kwa sababu tutaweza kuona kurasa za mtandao wote kufuata aina ya uongozi, anatengeneza
kwamba, mwisho wa siku, kuwa mti muundo wa chini ya Hood.
Hivyo zaidi juu ya kwamba katika kidogo tu.
>> Lakini kwa sasa, hebu kupendekeza kwa sasa, ni jinsi gani sisi kwenda juu
anayewakilisha nini stack ni?
Napenda kupendekeza kwamba sisi kutekeleza stack na kanuni kama hii.
Hivyo stack ni kwenda na ndani yake mambo mawili, safu, aitwaye sania,
tu kuwa thabiti na demo.
Na kila moja ya vitu katika safu kwamba ni kwenda kuwa int aina.
Na uwezo ni labda nini?
Sababu nimekuwa Hayakuandikwa kamili ufafanuzi hapa.
>> Ni pengine upeo ukubwa wa safu.
Na pengine ni alitangaza kama mkali kufafanua juu ya faili, baadhi ya
aina ya mara kwa mara kama alisema kwa mtaji tu.
Hivyo uwezo mahali fulani inaelezwa kama kawaida ya upeo iwezekanavyo.
Wakati huo huo, ndani ya muundo data inayojulikana kama stack kutakuwa
kuwa integer tu inajulikana tu kama kawaida.
>> Hivyo kama ningekuwa na kuwakilisha hii sasa pictorially, hebu tuseme kwamba hii
nzima sanduku nyeusi inawakilisha stack yangu.
Ndani yake ni mbili vigezo.
Hivyo nina kwenda kuteka kwanza moja kama kawaida.
Na wa pili mimi naenda kuteka kama safu.
>> Lakini tu kuweka mambo kwa utaratibu, kawaida napenda kuteka safu kama
hii, lakini ni ya aina ya nice kama sisi mechi ya ukweli, au
mechi mfano wa akili.
Hivyo basi mimi badala kuteka safu wima, ambayo ni ya haki, tena,
msanii wa kuhamisha wafungwa.
Kweli haina jambo nini ni chini ya Hood.
Na tutaweza kusema kwamba, kwa default, uwezo ni kwenda kuwa tatu.
Hivyo hii itakuwa mahali 0, hii itakuwa eneo 1, hii
itakuwa mahali 2.
>> Kama mimi rushwa na mpira stress, ingekuwa mtu kama kuja juu na kukimbia
bodi ya hapa kwa muda tu?
OK, niliona mkono wako wa kwanza.
Kuja juu juu.
Wote haki.
Hivyo mimi kuamini kuwa ni Steven.
Kuja juu juu.
Wote haki.
>> Lakini tuseme sasa sisi rewind ya awali hali ya dunia ambapo mimi
kuwa tu alitangaza stack, na ni kwenda kuwa ya uwezo wa tatu.
Lakini ukubwa bado ilivyopangwa.
Sania bado ilivyopangwa.
Hivyo wanandoa wa maswali ya kwanza.
Na nikupe mic hivyo unaweza kushiriki kikamilifu zaidi katika hili.
>> Hivyo ni nini ndani ya kawaida katika wakati huu katika wakati kama wote nimefanya ni
alitangaza stack na mstari mmoja wa kanuni?
>> Steven: Si sana.
>> DAVID Malan: OK, si sana.
Je, sisi kujua nini ndani ya kawaida, gani tunajua nini ndani
wa safu hii hapa?
>> Steven: Tu random kanuni, haki?
Tu -
>> DAVID Malan: Yeah, mimi naenda kuiita kanuni, lakini random -
>> Steven: Mambo.
>> DAVID Malan: Mambo kama random
>> Steven: Bits.
>> DAVID Malan: Bits, haki?
Hivyo takataka maadili, haki?
Hivyo permutations ya ya 0 na 1 ya.
Mabaki ya Matumizi uliopita ya kumbukumbu hii.
Na sisi si kweli kujua nini maadili ni, hivyo sisi kawaida kuteka yao
kama alama ya kuuliza.
>> Hivyo jambo la kwanza tuko labda kwenda kutaka kufanya hapa -
na napenda kutoa hii shamba ndani ya huko jina - sania.
Tufanye labda initialize ukubwa kama tunataka
kuanza kutumia hii stack?
>> Steven: Tray ni ndogo 3.
>> DAVID Malan: Hivyo, OK.
Kuwa wazi, uwezo ni alitangaza mahali pengine kama tatu.
Na kwamba ni nini nimekuwa kutumika kutenga safu.
Ukubwa ni kwenda kwa kutaja jinsi wengi sania sasa ni juu ya stack.
>> Steven: Zero.
>> DAVID Malan: Hivyo ni lazima sifuri.
Hivyo kwenda mbele, na kwa kidole yoyote, kuteka sifuri katika kawaida.
Wote haki.
Hivyo sasa, nini ndani ya hii hapa, hatujui.
Haya ni kweli tu takataka maadili.
Hivyo tunaweza kuchora alama swali, lakini hebu kuweka bodi safi kwa sasa
kwa sababu haijalishi kuna nini huko.
Hatuna haja ya initialize safu kwa kitu chochote, kwa sababu kama tunajua kwamba
ukubwa wa stack ni sifuri, vizuri, sisi haipaswi kuangalia kitu chochote katika
hii safu anyway saa hatua hii kwa wakati.
>> Hivyo sasa tuseme kwamba mimi kushinikiza namba 9 kwenye stack.
Ni jinsi gani sisi update data muundo ndani ya sanduku hili nyeusi?
Nini maadili haja ya mabadiliko?
>> Steven: Ndani -
kawaida?
>> DAVID Malan: OK.
Kawaida lazima kuwa nini?
>> Steven: Ukubwa itakuwa moja.
>> DAVID Malan: OK.
Hivyo ukubwa uwe moja.
Hivyo unaweza kufanya hivyo kwa njia ya wanandoa.
Nikupe, sasa wako kidole ni Raba.
Wote haki.
Basi sasa kidole yako ni brashi.
Wote haki.
Na sasa nini kingine ina mabadiliko, ni wazi, katika muundo wa data?
>> Steven: Sisi ni kwenda kutoka chini hadi 9.
>> DAVID Malan: 9.
OK, Good.
Hivyo bado haijalishi nini katika eneo moja au mbili kwa sababu wao ni
takataka maadili, lakini sisi lazima bother kuangalia pale kwa sababu ya kawaida ni
kutuambia kwamba tu kipengele kwanza ni kweli ni halali.
Hivyo sasa mimi kushinikiza 17 kwenye orodha.
Nini kinatokea kwa picha hii?
>> Steven: Hivyo ukubwa ni kwenda kwenda mbili.
>> DAVID Malan: OK.
Wewe Raba -
oops.
Wewe Raba.
>> Steven: Raba.
>> DAVID Malan: Wewe ni brashi.
>> Steven: Brashi.
>> DAVID Malan: OK.
Na nini kingine?
>> Steven: Na kisha sisi -
>> DAVID Malan: Sisi kusukuma 17.
>> Steven: Sisi fimbo 17 juu, hivyo -
>> DAVID Malan: OK, nzuri.
>> Steven: - kushuka chini.
>> DAVID Malan: zote haki.
Ni kupata rahisi.
Mimi si kwenda kukusaidia wakati huu.
Kushinikiza 22.
>> Steven: Done.
Kuwa Raba.
Mimi nina kuwa na brashi.
Na kisha Mimi kuweka 22.
>> DAVID Malan: 22.
Bora.
Hivyo muda zaidi.
Mimi sasa kwenda kushinikiza kwenye stack 26.
>> Steven: Ooh.
Oh gosh.
Wewe kweli hawakupata yangu mbali ulinzi.
>> DAVID Malan: Wewe si kuona hii inayokuja?
>> Steven: Sikuona hii ijayo.
Naweza sisi re-awali uwezo?
>> DAVID Malan: Hiyo ni swali zuri.
Hivyo tumekuwa aina ya walijenga wenyewe katika kona hapa.
Pale kweli hakuna nzuri nje kwa Steven kwa sababu tumekuwa zilizotengwa hii safu
statically, hivyo kusema, ndani ya ya muundo wa data.
Na tumekuwa kimsingi ngumu coded kuwa ni ya kawaida tatu.
Hivyo hatuwezi kweli reallocate yake.
>> Tunaweza kama sisi akaenda nyuma katika, sisi upya sania kuwa pointer kwamba
sisi kisha kutumia malloc mkono kumbukumbu.
Kwa sababu kama sisi got kumbukumbu kutoka lundo kupitia malloc, sisi
ingeweza huru yake.
Lakini kabla ya kumkomboa, tunaweza reallocate chunk kubwa ya kumbukumbu,
update pointer, na kadhalika.
Lakini kwa sasa, hii ni kweli bora tunaweza kufanya.
Kushinikiza na pop ni labda kwenda kuwa na kuashiria baadhi ya makosa.
>> Hivyo kwa mfano, yetu utekelezaji ya kushinikiza inaweza kurudi bool ambayo
awali akarudi kweli, kweli, kweli.
Lakini mara ya nne, ni kwenda kuwa kurudi uongo, kwa mfano.
Wote haki.
Vizuri sana kufanyika.
Hongera.
Ve chuma dhiki yako mpira leo.
>> [Makofi]
>> Steven: Asante.
>> DAVID Malan: Asante.
OK, hivyo hii inaonekana kuwa si nyingi ya hatua mbele, haki?
Sisi ilivyoelezwa muundo huu data.
Imekuwa ni kulazimisha, haki?
Uendeshaji wa mifumo kama hiyo.
Inavyoonekana mtandao wanaweza kufanya matumizi ya hii, na maombi mengine bado.
Lakini kile kiwango cha juu kijinga kwamba tuko nyuma kwa aina ya wiki mbili ya mipaka ya
ambapo tuna fasta arrays kawaida.
>> Hivyo kuna kweli michache ya njia sisi inaweza kutatua hili.
Tunaweza dynamically kutenga safu, si kwa bidii coding kama nimekuwa
kufanyika hapa, lakini badala yake tena kutangaza hii, tu kuwa wazi, kama
kitu kama hiki.
Int * sania, si kuamua juu ya uwezo bado.
Lakini wakati mimi kutangaza stack mahali pengine katika kanuni yangu, mimi naweza kisha piga malloc,
kupata anwani ya chunk ya kumbukumbu, na mimi nilikuwa hawawajui
kwamba anwani kwa sania.
>> Na kisha, kwa sababu ni tu chunk ya kumbukumbu, mimi naweza kuendelea kutumia mraba
bracket nukuu katika njia ya kawaida.
Sababu tena, kuna aina ya hii kazi sawa ya arrays na
chunks ya kumbukumbu kwamba kuja nyuma kutoka malloc.
Tunaweza kutibu mtu kama wengine kutumia hesabu au pointer
mraba mabano nukuu.
Hivyo kwamba ni moja ya mbinu.
>> Lakini jinsi ya mwingine ili sisi kutekeleza hii data muundo huo, uwezekano wa?
Haki?
Najisikia kama sisi tu kutatuliwa hii tatizo kama wiki moja iliyopita.
Nini ilikuwa ufumbuzi wa tatizo hili kwamba Steven mbio katika?
Hivyo wanaohusishwa orodha, kulia.
>> Kama tatizo ni kwamba sisi ni uchoraji sisi wenyewe ndani ya kona na kugawa
mapema kumbukumbu kidogo sana kwamba sisi kisha kuwa kwa namna fulani kukabiliana na, pia,
nini siyo tu kwamba kuepuka suala kabisa?
Mbona si tu kutangaza sania kuwa pointer ergo nodi, orodha wanaohusishwa,
na kisha tu kutenga nodes mpya kila wakati Steven zinahitajika fit
simu katika muundo wa data.
>> Hivyo picha bila kuwa na mabadiliko.
Ni si kwenda kuwa kama safi na kama rahisi kama tu safu ya ints tatu.
Sasa ni kwenda kuwa pointer struct, na struct kwamba ni kwenda
kuwa int na pointer ijayo.
Ni kwenda kuongoza kupitia pointer kwamba na mwingine struct vile
mwingine struct vile.
Hivyo picha ingekuwa kweli kupata Messier kidogo.
Na tunatarajia kuwa mishale zililingana kila kitu pamoja.
>> Lakini hiyo ni nzuri, haki, kwa sababu tumeona jinsi ya kufanya hivyo.
Na mara moja kupata starehe kutekeleza kitu kama wanaohusishwa
orodha, ambayo itabidi kufanya kama wewe kuchagua kutekeleza meza hash na
tofauti chaining kwa p-seti 6, unaweza kutumia kama kuzuia ujenzi, au
kingo, au katika Scratch kusema, utaratibu, kitu ambacho wewe kuweka, wewe
kuundwa puzzle yako mwenyewe kipande kwamba unaweza kisha kutumia tena.
Hivyo tradeoffs, lakini ufumbuzi uwezo kwamba tumekuwa kweli kuona mbele.
>> Hivyo mara nyingi kabisa, unaweza kuona hii kila mwaka mmoja au miwili wakati Apple releases
kitu kipya, na watu wote mambo line up nje ya Apple
kuhifadhi kununua yao kidogo kidogo kuboresha na vifaa.
Nasema hili, ni sawa, kwa sababu Mimi ni mmoja wa watu hao.
Hivyo ni aina gani ya muundo wa data wanaweza kuwakilisha ukweli huu?
>> Naam, hebu kuiita foleni, line.
Hivyo British kuita ni kawaida foleni anyway, hivyo ni jina nzuri.
Na shughuli mbili ambazo foleni atakuwa msaada Tutamwita enqueue
operesheni na operesheni dequeue, ambayo ni sawa katika
roho kushinikiza na pop.
Ni tu aina ya tofauti katika mkataba, kile sisi ni wito haya.
Lakini kwa enqueue kitu maana ya kuongeza au kuingiza kwa muundo wa data.
Kwa dequeue maana ya kuondoa hiyo.
Lakini wakati stack alikuwa data LIFO muundo, foleni ni katika wa kwanza,
kwanza nje ya muundo data.
>> Kama wewe ni mtu wa kwanza katika mstari, utakuwa mtu wa kwanza kupata
nje ya mstari na kununua kifaa yako mpya.
Fikiria jinsi upset watu hawa itakuwa kama Apple badala kutumika stack, kwa
mfano, kutekeleza kuokota juu ya toy yako mpya.
Hivyo foleni mantiki, kwa hakika, na tunaweza kufikiri ya kila aina ya
maombi, labda, kwa foleni, hasa wakati unataka haki.
Hivyo ni jinsi gani tunaweza kutekeleza hizo kama muundo wa data?
>> Naam, mimi kupendekeza kwamba tupate haja ya kufanya hivyo kwa njia hii.
Hivyo nina kwenda kwa sasa kuwa na namba.
Hivyo tutaweza kushika ni rahisi na si lazima kuzungumza katika suala la sania.
Idadi tu kwamba watu wa wamezipata.
Uwezo ni kwenda, tena, kurekebisha jumla ya idadi ya watu kwamba wanaweza kuwa katika
mstari huu, kama mitatu au chochote nyingine thamani.
>> Lakini mimi kupendekeza kwamba mimi haja ya kuweka wimbo si tu ya kawaida ya
foleni, jinsi mambo mengi ni ndani yake.
Hivyo ukubwa ni sasa ukubwa, uwezo ni ukubwa wa upeo.
Tu tena, utaratibu wa majina na mkataba.
Kwa nini nahitaji int ziada ndani ya foleni kwa kuweka wimbo wa nani katika
mbele ya mstari?
Kwa nini mimi haja ya kufanya hivyo katika kesi hii?
>> Naam, ni jinsi gani picha hii kwenda na mabadiliko?
Mimi pengine unaweza kutumia tena zaidi ya picha hii.
Hebu kwenda mbele na kufuta nini hapa.
Tutaweza kutoa hii kidogo tofauti jina hapa juu.
Hebu kujikwamua 17, hebu kujikwamua ya 9, hebu kujikwamua 3.
Na hebu kuongeza jambo moja nyingine.
Napendekeza kwamba mimi haja ya kuweka wimbo wa mbele ya orodha, ambayo ni tu
kwenda kuwa int pia.
Na tunakwenda kuitunza rahisi.
Hakuna orodha wanaohusishwa kwa sasa.
>> Tutaweza kukubali kwamba tunakwenda mapema juu dhidi ya kikomo hii.
Lakini je, nataka kuona kutokea wakati huu?
Hivyo nadhani kwenda mbele na kwanza mtu anakuja juu katika line, na
ni namba 9.
Hatuwezi kuwa na mipira ya dhiki.
Naweza kuiba, kusema, watu wawili au watatu?
Moja, mbili, tatu?
Kuja juu juu.
Haki kutoka mbele, kwa sababu tutaweza kufanya hii moja ya haraka.
>> Kila mmoja wenu sasa ni kwenda kuwa mvulana shabiki katika mstari wa saa Apple.
Huwezi kuwa na kupokea Apple vifaa mwisho wa hii ingawa.
Wote haki.
Hivyo wewe ni namba 9, wewe ni namba 17, namba 22.
Hizi ni holela namba, kama mwanafunzi wa Vitambulisho au mengineyo.
Na katika muda tu, hebu kuanza kuanza kuongeza mambo.
Na mimi itabidi kukimbia bodi hapa wakati huu.
>> Hivyo katika kesi hii, nimekuwa initialized mbele kuwa -
Mimi kwa kweli si kweli huduma nini mbele ni, kwa sababu ukubwa ni sifuri.
Hivyo hii ili kama vizuri tu kuwa alama ya swali.
Hizi ni alama swali wote.
Hivyo sasa tutaweza kuanza kweli kuona baadhi ya watu wanaojitokeza katika kuhifadhi.
>> Hivyo kama namba 9, wewe ni mmoja wa kwanza kuna saa 5:00, kwenda mbele na kujipanga,
au usiku kabla.
OK.
Hivyo sasa 9 ni hapa.
Hivyo 9 ni mbele ya orodha.
Hivyo nina kwenda mbele na update ukubwa wa data hii ya sasa
muundo na si kuwa 0 tena, lakini kwa kuwa 1.
Mimi naenda kuweka 9 katika mbele ya orodha.
Hebu kwenda mbele na kugeuza screen hivyo tunaweza kuona nyuma sisi hapa.
>> Na sasa je, nataka kuweka mbele?
Mimi naenda kuweka wimbo kwamba mbele ya foleni sasa hivi
ni katika eneo 0.
Kwa sababu kile ijayo kitatokea?
Naam, tuseme sasa mimi enqueue 17 pia.
Hivyo hop katika mstari huko.
Na tena, aina ya mlango kwa kuhifadhi ni kwenda kuwa hapa.
Hivyo sasa nimekuwa aliongeza 17.
Na hata kama hawa guys ni kuzuia screen, hiyo ni sawa,
sababu tunaweza kuona hapa.
Sorry.
>> Watazamaji: Tunaweza hoja -
>> DAVID Malan: Hapana, hiyo ni sawa.
Ni kubwa hadi pale.
Hivyo sasa ni 17 ndani ya foleni.
Nahitaji update ambayo mashamba ya sasa ingawa?
OK, dhahiri ukubwa.
Na vipi kuhusu mbele?
OK, hakuna.
Mbele lazima mabadiliko, kwa sababu tofauti na stack, sisi
wanataka kudumisha haki.
Hivyo kama 9 alikuja katika kwanza, tunataka 9 kuwa nje ya kwanza ya mstari
na katika kuhifadhi.
>> Kwa kweli, hebu angalia hiyo.
Kabla ya sisi kuingiza 22, hebu kwenda mbele na dequeue 9.
Nini jina lako tena?
>> Watazamaji: Jake.
>> DAVID Malan: Jake ni kwenda kuwa dequeued sasa.
Ili kupata kutembea katika kuhifadhi.
Kujifanya kuwa na kuhifadhi ni zaidi ya hapo.
Hivyo sasa nini anahitaji - dit-dit-dit!
Kinachohitajika kutokea sasa?
Kubuni maamuzi.
Hivyo sio silika mbaya, lakini - nini jina lako tena?
>> Watazamaji: David.
>> DAVID Malan: David.
Hivyo kile Daudi kufanya?
Alikuwa kujaribu aina ya kurekebisha data muundo na hoja kutoka eneo lake
katika eneo Jake wa zamani.
Na kwamba ni mzuri kama tuko tayari kukubali kwamba kama
utekelezaji undani.
Lakini kwanza, hebu update data muundo wa kabla ya sisi kufanya hivyo.
Kwa sababu mimi si liking wazo la kila watu kuhama katika mstari huu.
>> Ni hakuna mpango mkubwa kama Daudi gani na hatua moja, lakini tena, kufikiri nyuma
wakati tulikuwa na kujitolea nane juu ya hatua na tumekuwa kufanyika kama kuingizwa
aina, ambapo tulikuwa na kuanza kusonga kila mtu duniani.
Kwamba got ghali, haki?
Hiyo inanifanya cringe kuhusu kubwa O ya n, kubwa O ya n squared tena.
Siyo hisia kama matokeo bora.
>> Basi hebu tu update hii.
Hivyo ukubwa wa foleni ni tena 2.
Ni sasa tu 1.
Lakini sasa naweza update kitu Sikuweza update kabla,
mbele ya orodha.
Mimi nilikuwa tu kusema, ni kwamba eneo 1?
Basi sasa tuna taka thamani hapa, takataka thamani hapa, na Daudi katika
katikati ya takataka hii.
Lakini muundo data bado intact.
>> Na kwa kweli, sijui hata haja ya mabadiliko Jake wa zamani wa simu
9, kwa sababu anayejali.
Nina taarifa za kutosha sasa katika kawaida kwamba mimi najua kuna mtu mmoja katika
hii foleni.
Na najua kwamba mtu huyo ni katika eneo 1, si 0.
Mimi si kuhesabu kura.
Hivyo 1 pia.
Hivyo muundo data bado ni sawa.
>> Naam, kile kinachotokea ijayo?
Enqueue hebu -
nini jina lako?
>> Watazamaji: Callen.
>> DAVID Malan: Callen.
Hebu enqueue Callen, na 22 sasa ni katika foleni.
Hivyo sasa nini ina mabadiliko hapa?
Mbele si kwenda mabadiliko, ni wazi.
Ukubwa ni kwenda na mabadiliko kuwa 2 tena.
Na 22 inaishia hapa, 9 bado ni sasa, lakini ni vizuri
takataka thamani sasa.
Ni tu mabaki ya zamani Jake.
>> Hivyo sasa nini kinatokea kama Mimi dequeue Daudi?
Moja ya mwisho operesheni, dequeue Daudi.
Tunaweza kuhama, lakini napendekeza hebu kufanya kama kazi kidogo iwezekanavyo.
Sasa data zangu muundo huenda nyuma katika kawaida 2-1.
Lakini mbele ya foleni sasa inakuwa 2.
Sina haja ya kubadili namba hizi bado tu, kwa sababu wao ni
tu takataka maadili.
>> Lakini sasa nini hufanyika?
Nadhani enqueue mwenyewe, 26?
Najisikia kama mimi ni zaidi ya hapa.
Hivyo mimi nina kuwa enqueued.
Hivyo mimi aina ya mali hapa.
Na hata kama huna kabisa kufahamu hii kuibua juu ya hatua,
sababu tuna mengi ya chumba, mimi lazima kuwa amesimama hapa, kwa nini?
>> Watazamaji: Wewe ni nje ya mipaka.
>> DAVID Malan: Haki.
Mimi nina nje ya mipaka.
Nimekuwa indexed ya zaidi ya mipaka ya safu hii.
Mimi kwa kweli lazima kuwa katika moja ya tatu inawezekana maeneo.
Sasa, ambapo ni zaidi ya asili ya kwenda?
Napendekeza sisi leveraged wiki moja hila.
operator Mod, asilimia.
Kwa sababu mimi nina kitaalam wamesimama katika eneo la 3, lakini mimi kufanya 3 Mod uwezo,
hivyo 3, ishara asilimia, 3 -
uwezo ni 3.
Nini hiyo?
Nini salio wakati kugawanya 3 na 3?
0.
>> Hivyo kwamba unaweka yangu walikuwa Jake ilikuwa, ambayo ni kweli nzuri.
Hivyo sasa utekelezaji ya jambo hili kinaendelea
kuwa kidogo ya maumivu ya kichwa.
Ni kweli tu mstari mmoja maumivu ya kichwa, wa kanuni.
Lakini angalau sasa kuna takataka thamani hapa, lakini kuna mawili
halali ints hapa.
Na mimi kudai kwamba sasa tumefanya nini hasa tunahitaji kufanya hivyo kwa muda mrefu kama
sisi mabadiliko nini Jake ya thamani ilikuwa kuwa 26.
>> Sisi sasa kuwa na taarifa za kutosha bado kudumisha uadilifu
ya muundo huu data.
Bado tuko aina ya nje ya bahati wakati sisi wanataka kuingiza nne au zaidi taarifa
vipengele, lakini naweza angalau kufanya pretty ufanisi matumizi ya hii mara kwa mara
wakati, kwa kweli.
Mimi si kuwa na wasiwasi kuhusu kuhama kila mtu, kama mwelekeo wa Daudi mara.
>> Maswali yoyote juu mwingi, au hii foleni?
>> Watazamaji: Je, sababu ni kwa nini unahitaji ili kujua ukubwa
ambapo kuwa na mtu?
>> DAVID Malan: Hasa.
Nahitaji kujua ukubwa ya safu kwa sababu mimi haja ya kujua hasa jinsi
wengi wa maadili haya ni halali, na hivyo kwamba naweza kupata wapi kuweka
mtu mwingine.
Hasa.
kawaida ni -
kweli, hatukuwa update hii bado.
Mimi aliongeza mwenyewe katika 26.
kawaida ni sasa, si 1, lakini 2.
Hivyo sasa kweli hii husaidia mimi kupata mkuu wa orodha, ambayo si 0, si
1, lakini ni 2.
mbele ya orodha kweli ni namba 22.
Kwa sababu yeye alikuja katika kwanza, hivyo yeye anatakiwa kuruhusiwa kuingia katika duka mbele yangu,
hata ingawa kuibua Nimesimama karibu na kuhifadhi.
>> Wote haki?
raundi ya applause kwa guys hawa na tutaweza waache nje ya hapo.
>> [Makofi]
>> DAVID Malan: Mimi inaweza basi wewe kushika tray.
Tunaweza kuona nini kinatokea kama unataka, lakini labda si.
Wote haki.
Basi nini sasa gani kwamba kuondoka sisi?
Naam, napenda kupendekeza kwamba kuna nyingine chache data miundo tunaweza
kuanza kuongeza na kit chombo yetu kwamba mapenzi kweli kabisa, kabisa husika kama
sisi kupiga mbizi katika mambo ya mtandao.
Ambayo tena, ina aina fulani ya uhusiano kwa miti katika fomu ya
kitu kinachoitwa DOM, hati kitu mfano wa kuigwa.
Lakini tutaweza kuona zaidi ya kwamba kabla ya muda mrefu.
>> Napenda kupendekeza kwamba sisi definitionally kuwaita mti sasa nini unaweza kujua kama
zaidi ya mti wa familia, ambapo kuwa na baadhi ya babu katika
mizizi ya mti.
matriarch mfumo dume au katika sana juu ya mti.
Bila wenzi wao, katika kesi hii.
Lakini sasa tuna kile Tutamwita watoto, ambayo ni nodes kwamba hutegemea
mbali ya mtoto wa kushoto au mtoto wa kulia, mishale kama taswira ya hapa.
>> Kwa maneno mengine, katika muundo wa data mti katika kompyuta, mti ina sifuri
au zaidi nodi.
Kama ana angalau moja nodi, kwamba wito mizizi.
Ni mambo kuibua kwamba sisi kuteka saa ya juu.
Na node ya kwamba, kama nodi nyingine yoyote, unaweza na sifuri, moja, au mbili, au tatu,
au hata hivyo watoto wengi data muundo mkono.
Katika kesi hiyo, mizizi, hifadhi thamani mmoja, ana watoto wawili, 2 na 3,
hivyo sisi ujumla kuwaita 2 kushoto mtoto na 3 mtoto haki.
>> Na wakati sisi kupata chini ya 5, 6, na 7 6, wanaweza kuitwa mtoto katikati.
Kama una watoto wanne, anapata utata.
Hivyo sisi kuacha kutumia aina njia ya mkato ya maneno.
Lakini ni kweli tu mti wa familia.
Na majani hapa ni kwamba nodes wenyewe hawana watoto.
Wao hutegemea mbali chini ya mti.
>> Hivyo ni jinsi gani tunaweza kutekeleza mti ana watoto wawili tu maximally?
Tutaweza kuiita mti mapacha.
Bi tena maana mbili, katika hii kesi, kama na mapacha.
Na ndivyo inaweza kuwa na sifuri, moja, au watoto wawili maximally.
>> Mimi itabidi kupendekeza kwamba sisi kutekeleza nodi kwa kuwa muundo na n int,
na kisha mbili kuyatumia, mtu mmoja aitwaye kushoto, mtu mmoja aitwaye haki.
Lakini wale ni nzuri tu holela makongamano.
Na nini ni nzuri sasa, hasa kama wewe aina ya Jihadi conceptually na
recursion, au walidhani kwamba haikuwa kweli ufumbuzi kwa kitu chochote,
hasa kama unaweza kukimbia nje ya kumbukumbu.
Sasa kwa kuwa tunazungumzia juu ya data miundo na algorithms kwamba kuruhusu
sisi tembeeni na kuendesha yao, zinageuka kuwa recursion anakuja nyuma katika
mengi zaidi ya kulazimisha kama si nzuri njia.
>> Hivyo hii napendekeza ni utekelezaji ya kazi Search.
Kutokana na pembejeo mbili -
hivyo kufikiri ya hii kama sanduku nyeusi.
Kutokana na pembejeo mbili, n, int, na pointer mti, pointer
nodi, au kweli mizizi ya mti, mimi kudai kwamba kazi hii inaweza kurudi
kweli au uongo, kwamba thamani n ni ndani ya mti huu.
>> Nini ndani ya sanduku hili nyeusi?
Naam, wanne matawi.
tu kwanza hundi.
Kama mti ni null, tu kurudi uongo.
Kama kuna nodi hakuna, kuna n hakuna, kuna idadi hakuna, tu kurudi uongo.
Kama ingawa, n, thamani wewe ni kuangalia kwa maana, ni chini ya mti mshale n, na
tu kuwa wazi, ni nini maana wakati Mimi kuandika mti na kisha mshale
nukuu, n?
Hasa.
Ina maana kwamba dereference pointer kuitwa mti.
Kwenda huko, na kisha kupata ndani ya kwamba nodi na kupata uwanja wake aitwaye n.
Na kisha kulinganisha n halisi kwamba alikuwa kupita katika Tafuta dhidi yake.
>> Hivyo kama ni chini ya n, thamani n katika nodi mti wenyewe, vizuri,
hiyo ina maana gani?
Hiyo ina maana kitu katika mtazamo wa kwanza.
Haki?
Tu kama wakati una safu ya maadili, unaweza kama kuomba binary
kutafuta kama namna ya kugawanya na kushinda.
Lakini nini dhana gani sisi haja ya kufanya kwa binary tafuta kufanya kazi wakati wote
katika kitabu cha simu na mapema mifano?
>> Jinsi ya kutatuliwa.
Basi hebu kuboresha ufafanuzi wa mti hapa si kwa kuwa tu mti, ambayo inaweza
kuwa na idadi yoyote ya watoto.
Si tu mti binary, ambayo inaweza wana 0, 1, au 2 maximally.
Lakini kama binary tafuta mti, au BST, ambayo ni njia tu ya dhana ya kusema
binary mti vile kwamba kila nodi ya mtoto wa kushoto, kama sasa, ni
chini ya nodi.
Na kila nodi ya haki ya mtoto, kama sasa, ni makubwa zaidi
kuliko nodi yenyewe.
>> Hivyo kwa maneno mengine, kama ungekuwa na kuteka nje ya mti, wote wa idadi ni
makini uwiano kama hii ili kwamba kama una 55 kama mzizi, 33 wanaweza kwenda
kwa upande wake wa kushoto kwa sababu ni chini ya 55.
77 anaweza kwenda kwa haki yake kwa sababu ni mkubwa kuliko 55.
Lakini sasa taarifa, ufafanuzi huo, ni ufafanuzi kujirudia kwa maneno,
ana kuomba kwa ajili ya 33.
33 ya mtoto wa kushoto lazima kuwa chini ya hilo, na 33 ya haki ya mtoto, 44, lazima
kubwa kuliko yake.
>> Hivyo hii ni binary tafuta mti, na Napendekeza, kwa kutumia kidogo kidogo ya
recursion, sasa tunaweza kupata n.
Hivyo kama n ni chini ya n thamani hiyo ni nodi sasa, mimi nina kwenda
mbele na Punt, hivyo kusema, na tu kurudi chochote jibu ni ya
kwa ajili ya kutafuta n juu ya mti wa kushoto wa mtoto.
Taarifa tena, hii kazi tu anatarajia nyota nodi,
pointer nodi.
Basi hakika naweza tu kufanya mti mshale wa kushoto, ambayo itasababisha
mimi nodi mwingine.
Lakini ni nini nodi kwamba?
>> Naam, kwa mujibu wa tamko hili, kushoto ni tu pointer, ili tu
maana mimi nina kupita kwa kazi tafuta pointer tofauti, yaani
moja kwamba inawakilisha mtoto wangu wa kushoto ya mti.
Hivyo katika kesi hii, pointer 33, ikiwa hii ni sampuli zetu pembejeo Wakati huo huo, kama
n, ni mkubwa kuliko n thamani katika sasa nodi katika mti, basi mimi nina
kwenda mbele na Punt katika nyingine mwelekeo na kusema tu, mimi si
kujua kama hii ni n thamani katika mti, lakini mimi kujua kama ni, ni chini yangu
haki ya tawi, hivyo kusema.
Hivyo basi mimi wito recursively kutafuta, kupita n tena, lakini kupita katika
pointer mtoto wangu wa kulia.
>> Kwa maneno mengine, kama nina sasa saa 55 na mimi nina kuangalia kwa ajili ya 99, najua kwamba 99
ni mkubwa kuliko 55, hivyo kama mimi akararua kitabu cha simu wiki iliyopita na sisi
akaenda haki, vile vile ni sisi kwenda kulia hapa.
Na sijui kama ni katika haki yangu mtoto, na siyo, 77 ni pale, lakini
Najua ni katika mwelekeo.
Hivyo mimi wito tafuta juu ya mtoto wangu wa kulia, 77, na basi tafuta takwimu kutoka
huko kama 99 mwaka huu holela mfano ni kweli huko.
>> Mwingine, nini kesi ya mwisho?
Kama mti ni null ni moja ya kesi.
Kama n ni chini ya sasa ya nodi ya thamani ni kesi nyingine.
Kama n ni mkubwa kuliko sasa thamani ya nodi ni kesi ya tatu.
Nini Kesi ya nne na ya mwisho?
Nadhani tuko nje ya kesi, sawa?
Ni lazima kwamba n ni katika sasa nodi kwamba mimi nina juu.
>> Hivyo kama mimi nina kwa ajili ya kutafuta 55 katika hatua hii katika hadithi, kwamba tawi la
mti atarudi kweli.
Basi nini kuvutia hapa ni kwamba sisi kweli, tofauti na wiki iliyopita, sisi aina
ya msingi na kesi mbili.
Na wao hawana kuwa wote kwa juu.
juu ni kesi ya msingi kwa sababu kama mti ni null, kuna kitu cha kufanya.
Tu kurudi coded ngumu thamani ya uongo.
>> tawi chini ni aina ya msingi, ambapo kama tumekuwa checked kwa
null, tumekuwa checked ikiwa ni lazima kushoto, lakini ni lazima kuwa, tumekuwa
checked ikiwa ni lazima kuwa na haki, lakini haipaswi kuwa, ni wazi kuwa ina kuwa
haki ambapo sisi ni.
Hiyo ni kesi ya msingi.
Hivyo kuna kesi mbili kujirudia ipo katikati.
Lakini mimi nilikuwa wameandika hii ili yeyote.
Mimi tu walidhani ni aina ya waliona asili kwanza kuangalia kwa kosa inawezekana,
kisha kuangalia kushoto, kisha kuangalia haki, basi kudhani kuwa uko katika nodi
wewe ni kweli kutafuta.
>> Hivyo kwa nini huenda hii kuwa muhimu?
Hivyo ni zamu nje -
na napenda Rukia teaser hapa kwamba katika mtandao.
Sisi ni kwenda kuanza kutumia si programu ya lugha ya kwanza, lakini
ghafi lugha.
ghafi lugha kuwa moja kwamba ni sawa katika roho na programu
lugha, lakini haina kukupa uwezo wa kueleza mwenyewe kifikra.
Ni tu inakupa uwezo wa kueleza mwenyewe kimuundo.
>> Ambapo unataka kuweka kitu kwenye ukurasa, ukurasa wa mtandao?
Nini rangi unataka kufanya hivyo?
Nini fonti unataka kufanya hivyo?
Ni maneno gani kufanya kweli unataka kwenye ukurasa wa mtandao?
Hivyo kwamba ni lugha ghafi.
Lakini basi tutaweza haraka sana kuanzisha JavaScript, ambayo ni full-fledged
programu ya lugha.
Sawa sana syntactically katika muonekano na C, lakini utakuwa na baadhi ya
nzuri, na nguvu zaidi, zaidi user kirafiki makala.
>> Na mmoja wa Matatizo katika hii kumweka katika muhula ni kwamba tutaweza
haraka kutekeleza Speller katika mbali wachache mstari wa kanuni kwa kutumia lugha nyingine
kuliko C yenyewe inaruhusu, lakini kwa sababu ya tutaweza karibuni kuelewa.
Hii itakuwa ni mara ya kwanza vile mtandao ukurasa.
Itakuwa ni aghali kabisa, moja ya kwanza sisi kufanya.
Itakuwa tu kusema, hello dunia.
Lakini kama wewe sijawahi kuona ni kabla, hii ni HTML,
HyperText ghafi lugha.
>> Kama wewe kwenda chaguo fulani katika orodha ya yoyote zaidi browser, katika ukurasa wa mtandao wowote juu ya
internet, unaweza kuona HTML kwamba baadhi ya watu aliandika kwa
kuunda kwamba ukurasa wa mtandao.
Na pengine haina kuangalia kama kifupi au kama nadhifu kama hii.
Lakini itakuwa kufuata mfano wa haya wazi na mabano na mikwaju
herufi na namba uwezekano.
>> Nilidhani ningependa kukupa teaser ya nini wewe utakuwa na uwezo wa kufanya
baada ya kuchukua CS50.
Hebu kwenda cs.harvard.edu / kuwaibia, Mzee Rob yetu wenyewe Bowden ya.
Yeye alifanya hivyo kwa ajili yetu.
Hivyo itabidi karibuni kuwa na uwezo wa kufanya hivyo.
Na pia, nini habari asubuhi hii -
nini wewe habari asubuhi hii -
>> [Hamster DANCE MUSIC]
>> - You'll kuwa na uwezo wa kufanya hili.
Kwamba watapata sisi juu ya Jumatano.
Tutaona wewe hapo.
>> [Hamster DANCE MUSIC]
DAVID Malan: Katika CS50 ijayo -