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