[Music kucheza] SPIKA 1: All haki. Kila mtu kuwakaribisha nyuma na sehemu ya. Natumaini wote ni mafanikio zinalipwa kutoka Jaribio yako kutoka wiki iliyopita. Najua ni kidogo mambo mara kwa mara. Kama nilivyosema hapo kabla, kama wewe ni ndani ya kupotoka standard, si kweli wasiwasi kuhusu hilo, hasa kwa sehemu chini ya starehe. Hiyo ni kuhusu ambapo unapaswa kuwa. Kama alifanya kubwa, basi kutisha. Kudos na wewe. Na kama wewe kujisikia kama unahitaji kidogo msaada zaidi, tafadhali kujisikia huru na kufikia kufanyika kwa yoyote ya TFS. Sisi sote tuko hapa kusaidia. Hiyo ni kwa nini sisi kufundisha. Hiyo ni kwa nini mimi niko hapa kila Jumatatu kwa ajili yenu wavulana na katika ofisi masaa juu ya Alhamisi. Hivyo tafadhali jisikie huru basi mimi kujua kama wewe ni wasiwasi kuhusu kitu chochote au kama kuna kitu chochote juu ya jaribio kwamba Ningependa kwa kweli kama kushughulikia. Hivyo ajenda ya leo ni wote kuhusu miundo ya data. Baadhi ya hizi ni kwenda tu kuwa tu kupata wewe familiarized na haya. Unaweza milele kutekeleza nao katika darasa hili. Baadhi yao wewe, kama kwa Speller yako pset. Itabidi uchaguzi wako kati ya meza hash na anajaribu. Hivyo tutaweza dhahiri kuwa kwenda juu ya wale. Ni kwenda kuwa dhahiri zaidi ya aina ya kiwango cha juu cha kifungu leo, ingawa, kwa sababu kuna mengi ya yao, na kama sisi akaenda katika maelezo ya utekelezaji juu ya yote haya, sisi hakutaka hata kupata njia ya orodha wanaohusishwa na labda kidogo ya meza hash. Hivyo kuzaa na mimi. Sisi siyo kwenda kufanya kama kiasi coding wakati huu. Kama una maswali yoyote kuhusu hilo au unataka kuona kutekelezwa au kujaribu mwenyewe, Mimi dhahiri kupendekeza kwenda study.cs50.net, ambayo ina mifano ya yote haya. Ni itabidi PowerPoints yangu pamoja na maelezo kwamba sisi huwa na kutumia kama vile baadhi ya programu mazoezi, hasa kwa ajili ya mambo kama orodha wanaohusishwa na binary miti mwingi na cues. Ngazi ya juu zaidi hivyo kidogo, ambayo inaweza kuwa nzuri kwa ajili ya guys. Hivyo, pamoja na kwamba, tutaweza kupata kuanza. Na pia, yes-- Quizzes. Nadhani wengi wenu walio katika Sehemu yangu na Quizzes yako, lakini mtu akija katika au sababu baadhi yenu kufanya hivyo, wao ni haki hapa mbele. Hivyo wanaohusishwa orodha. Najua aina hii ya unaendelea nyuma kabla ya jaribio yako. Hiyo ilikuwa wiki moja kabla ya kwamba sisi kujifunza kuhusu hili. Lakini katika kesi hii, tutaweza tu kwenda kidogo zaidi kwa kina. Hivyo kwa nini huenda sisi kuchagua wanaohusishwa orodha juu ya safu? Nini tofauti kati yao? Ndiyo? Watazamaji: Unaweza kupanua wanaohusishwa orodha dhidi safu ya fasta ukubwa. SPIKA 1: Haki. safu ina ambapo fasta ukubwa orodha wanaohusishwa ina ukubwa kutofautiana. Hivyo kama sisi hawajui jinsi kiasi tunataka kuhifadhi, orodha wanaohusishwa inatupa kubwa njia ya kufanya kwamba kwa sababu tunaweza tu kuongeza juu ya nodi mwingine na kuongeza juu mwingine nodi na kuongeza juu ya nodi mwingine. Lakini nini inaweza kuwa biashara-off? Je, mtu yeyote kumbuka biashara-off kati ya arrays na orodha wanaohusishwa? Mmhmm? Watazamaji: Una kwenda kwa njia ya njia yote kupitia orodha wanaohusishwa kupata kipengele katika orodha. Katika safu, unaweza tu kupata kipengele. SPIKA 1: Haki. Hivyo pamoja na arrays-- Watazamaji: [inaudible]. SPIKA 1: Kwa arrays, tuna kile kinachoitwa upatikanaji random. Ina maana kwamba kama tunataka nini ni milele hatua ya tano ya orodha au uhakika wa tano wa wetu safu, tunaweza tu kunyakua hiyo. Kama ni orodha wanaohusishwa, tuna iterate kupitia, haki? Hivyo kupata kipengele katika safu ni muda mara kwa mara, ambapo pamoja na orodha wanaohusishwa ingekuwa zaidi uwezekano kuwa wakati linear kwa sababu labda kipengele yetu ni njia yote mwishoni. Tuna kutafuta njia ya kila kitu. Hivyo, pamoja na data zote hizi miundo tunakwenda kwa kutumia muda zaidi kidogo juu ya, kile ni pluses na hasi. Wakati wanaweza tunataka kutumia moja juu ya nyingine? Na hiyo ni aina ya Jambo kubwa ya kuchukua mbali. Hivyo tuna hapa ufafanuzi wa nodi. Ni kama moja ya kipengele katika orodha yetu wanaohusishwa, haki? Hivyo sisi ni wote ukoo na typedef structs yetu, ambayo sisi akaenda juu katika mapitio mara ya mwisho. Ilikuwa kimsingi kujenga tu aina nyingine data kwamba tunaweza kutumia. Na katika kesi hii, ni baadhi ya nodi kwamba itafanya baadhi integer katika. Na kisha nini sehemu ya pili hapa? Mtu yeyote? Watazamaji: [inaudible]. SPIKA 1: Yeah. Ni pointer nodi ijayo. Hivyo hii lazima kweli kuwa juu hapa. Hii ni pointer ya aina nodi kwa jambo la pili. Na kwamba ni nini wao amewazunguka nodi zetu. Baridi. Haki wote, hivyo pamoja na kutafuta, kama tulikuwa kusema tu kabla ya mkono, kama wewe ni kwenda kutafuta njia, una kweli iterate kupitia orodha yako wanaohusishwa. Hivyo kama sisi ni kuangalia kwa idadi 9, tunataka kuanza saa kichwa wetu na kwamba pointi sisi mwanzoni ya orodha yetu wanaohusishwa, haki? Na sisi kusema, sawa, hana huu nodi vyenye namba 9? Hakuna? Haki zote, kwenda moja ijayo. Kuifuata. Je vyenye namba 9? Hakuna Kufuata moja ijayo. Hivyo tuna kweli iterate kupitia orodha yetu wanaohusishwa. Hatuwezi tu kwenda moja kwa moja ambapo 9 ni. Na kama wewe guys kweli wanataka kuona baadhi kuna Pseudo-kificho up. Tuna baadhi ya kazi ya utafutaji hapa kwamba inachukua in-- nini kuchukua katika? Unafikiri nini? Hivyo ni rahisi moja. Hii ni nini? Watazamaji: [inaudible]. SPIKA 1: idadi sisi ni kuangalia kwa. Haki? Na nini itakuwa hii yanahusiana na? Ni pointer? Watazamaji: nodi. SPIKA 1: nodi kwa orodha kwamba sisi ni kuangalia, haki? Hivyo tuna baadhi nodes ni pointer hapa. Hii ni hatua ambayo inaenda kweli iterate kupitia orodha yetu. Sisi kuweka sawa kuorodhesha sababu tu kwamba kuiandaa sawa na kuanza ya orodha yetu wanaohusishwa. Na wakati ni si null, wakati bado tuna mambo katika orodha yetu, kuangalia kuona kama kwamba nodi ina idadi sisi ni kuangalia kwa. Kurudi kweli. Vinginevyo, update, haki? Kama ni null, sisi exit yetu kitanzi wakati na kurudi uongo kwa sababu hiyo ina maana sisi si kupatikana. Je, kila mtu kupata jinsi ya kuwa kazi? OK. Hivyo, pamoja na kuingizwa, wewe wana njia tatu tofauti. Unaweza prepend, unaweza append na unaweza kuingiza katika assorted. Katika kesi hiyo, sisi ni kwenda kufanya prepend. Je, mtu yeyote kujua jinsi wale kesi tatu wanaweza kutofautiana? Hivyo prepend ina maana kwamba kuweka ni mbele ya orodha yako. Hivyo kwamba itakuwa na maana kwamba hakuna jambo nini nodi yako, hakuna jambo nini thamani ni, wewe ni kwenda kuiweka haki hapa mbele, sawa? Ni kwenda kuwa ya kwanza kipengele katika orodha yako. Kama append yake, ni kwenda kwenda nyuma ya orodha yako. Na kuingiza ndani ya assorted maana wewe ni kwenda kuweka kweli katika nafasi ambapo ni kuvaa orodha yako wanaohusishwa yamepangwa. Tena, jinsi ya kutumia wale na wakati matumizi yao hutegemea kesi yako. Kama haina haja ya kutatuliwa, prepend inaelekea kuwa nini watu wengi kutumia kwa sababu huna kwenda kupitia orodha nzima kupata mwisho wa kuongeza juu, haki? Unaweza tu fimbo ni haki katika. Hivyo sisi kwenda kwa njia insertion 1 hivi sasa. Jambo hivyo moja kwamba mimi nina kwenda sana kupendekeza juu ya pset hii ni kuteka mambo ya nje, kama siku zote. Ni muhimu sana kwamba wewe update kuyatumia yako katika mpangilio sahihi kwa sababu kama wewe update yao kidogo nje ya utaratibu, wewe ni kwenda kuishia kupoteza sehemu ya orodha yako. Hivyo kwa mfano, katika kesi hii, sisi ni kuwaambia kichwa kwa uhakika tu 1. Kama sisi tu kufanya hivyo bila kuokoa hii 1, hatuna wazo nini 1 lazima kumweka kwa sasa kwa sababu tumekuwa waliopotea nini kichwa alisema kwa. Hivyo jambo moja kukumbuka wakati unafanya prepend ni kuokoa kile pointi kichwa kwanza, basi reassign yake, na kisha update nini nodi yako mpya lazima kumweka kwa. Katika kesi hiyo, hii ni njia moja ya kufanya hivyo. Hivyo kama sisi alikuwa amefanya hivyo kwa njia hii ambapo sisi tu reassigned kichwa, tunapoteza kimsingi wetu orodha nzima, haki? Njia moja ya kufanya hivyo ni kuwa na 1 uhakika kwa ijayo, na kisha kuwa na uhakika na kichwa 1. Au unaweza kufanya aina ya kama kuhifadhi muda, ambayo mimi aliyesema kuhusu. Lakini reassigning yako kuyatumia katika mpangilio sahihi ni kwenda kuwa sana, sana muhimu kwa pset hii. Vinginevyo, wewe ni kwenda kuwa na hash meza au kujaribu kuwa tu kwenda kuwa sehemu tu ya maneno kwamba wanataka na kisha mmhmm you're--? Watazamaji: Nini muda Jambo kuhifadhi wewe walikuwa wanazungumza juu? SPIKA 1: kuhifadhi muda. Hivyo kimsingi mwingine njia unaweza kufanya hivyo ni kuhifadhi mkuu wa kitu, kama kuhifadhi variable muda. Hawawajui kwa 1 na kisha update 1 kwa uhakika kwa chochote kichwa kutumika kwa uhakika na. Njia hii ni wazi zaidi ya kifahari kwa sababu wewe hawahitaji thamani ya muda mfupi, lakini tu kutoa njia nyingine ya kufanya hivyo. Na sisi kweli kufanya kuwa baadhi kificho kwa hili. Hivyo kwa orodha wanaohusishwa, sisi kweli kuwa baadhi ya kanuni. Hivyo kuingiza hapa, hii ni prepending. Hivyo hii inaingia ni katika kichwa. Jambo hivyo kwanza, unahitaji kujenga nodi yako mpya, bila shaka, na kuangalia kwa null. Daima ni nzuri. Na kisha unahitaji hawawajui maadili. Kila wewe kujenga nodi mpya, sijui nini ni akizungumzia ijayo, hivyo unataka initialize kwa null. Kama haina kuishia akizungumzia jambo mwingine, anapata reassigned na ni faini. Kama ni jambo la kwanza ni katika orodha, inahitaji kwa uhakika na kwa sababu null hiyo ni mwisho wa orodha. Hivyo basi kwa kuingiza, tunaona hapa sisi ni kumshirikisha thamani ya pili ya nodi wetu kuwa chochote kichwa ni, ambayo ni nini tulikuwa hapa. Hiyo ni nini sisi tu alivyofanya. Na kisha sisi ni kumshirikisha kichwa kwa uhakika nodi wetu mpya, kwa sababu kumbuka, mpya ni baadhi pointer nodi, na kwamba ni nini hasa kichwa ni. Hiyo ni kwa nini hasa sisi kuwa hii mshale accessor. Baridi? Mmhmm? Watazamaji: Je tuna initialize mpya ijayo null kwanza, au tunaweza tu initialize kwa kichwa? SPIKA 1: Mpya ijayo mahitaji ya kuwa NULL kuanza kwa sababu hamjui ambapo ni kwenda kuwa. Pia, hii ni aina ya tu kama dhana. Wewe kuweka sawa na NULL tu kufanya kuhakikisha kwamba besi yako yote ni kufunikwa kabla ya kufanya reassignment yoyote ili wewe ni daima uhakika kwamba itakuwa kuwa akizungumzia thamani maalum dhidi kama thamani ya takataka. Kwa sababu, yeah, sisi hawawajui mpya ijayo moja kwa moja, lakini ni zaidi kama mazoezi mazuri kwa initialize katika njia hiyo na kisha reassign. OK, hivyo doubly wanaohusishwa orodha ya sasa. Tufanye nini kufikiri? Nini tofauti na doubly wanaohusishwa orodha? Hivyo katika orodha yetu wanaohusishwa, tunaweza tu hoja katika mwelekeo mmoja, haki? Sisi tu ijayo. Tunaweza tu kwenda mbele. Na orodha doubly wanaohusishwa, sisi pia unaweza hoja nyuma. Hivyo tuna si tu idadi hiyo tunataka kuhifadhi, tuna ambapo inaelekeza katika ijayo na ambapo sisi tu alikuja kutoka. Hivyo hii inaruhusu kwa ajili ya baadhi traversal bora. Nodes hivyo doubly wanaohusishwa, sawa, haki? Tu tofauti ni sasa sisi kuwa ijayo na uliopita. Ni tofauti tu. Hivyo kama sisi walikuwa prepend au append-- sisi hawana kificho kwa hili hadi here-- lakini kama ungekuwa kujaribu na kuingiza, jambo muhimu ni haja ya kufanya kuhakikisha wewe ni kumshirikisha wote uliopita wako na yako pointer ijayo kwa usahihi. Hivyo katika kesi hii, wewe ungekuwa si tu initialize ijayo, you initialize uliopita. Kama tuko katika kichwa cha orodha, sisi itakuwa si tu kufanya kichwa sawa mpya, lakini mpya uliopita yetu lazima uhakika na kichwa, haki? Hiyo ni tofauti tu. Na kama unataka zaidi mazoezi na haya na orodha wanaohusishwa, na kuingiza, na kufuta, na kuingiza katika orodha assorted, tafadhali angalia study.cs50.net. Kuna kundi la mazoezi kubwa. Mimi sana kupendekeza yao. Napenda tulikuwa na wakati wa kwenda kwa njia yao lakini kuna mengi ya miundo data kupata njia. OK, hivyo meza hash. Hii pengine ni wengi muhimu kidogo kwa pset yako hapa kwa sababu wewe ni kwenda kuwa kutekeleza mmoja wa haya, au kujaribu. Mimi kwa kweli kama meza hash. Wao ni pretty cool. Hivyo kimsingi nini kinachotokea ni meza hash ni wakati sisi kwa kweli wanahitaji haraka insertion, kufutwa, na Luke. Hayo ni mambo ambayo sisi ni kipaumbele katika meza hash. Wanaweza kupata pretty kubwa, lakini kama tutaweza kuona na inajaribu, kuna mambo ambayo ni kubwa sana. Lakini kimsingi, hash wote meza ni hash kwamba anasema ambayo ndoo kuweka kila ya data yako, kila mmoja wa mambo yako katika. njia rahisi kufikiri ya meza hash ni kwamba ni ndoo tu ya mambo, haki? Hivyo wakati wewe ni kuchagua mambo kwa kama barua ya kwanza ya jina yao, hiyo ni aina ya kama meza hash. Hivyo kama mimi walikuwa na kundi guys ni katika makundi ya yeyote jina la kuanza na zaidi ya hapa, au mtu siku ya kuzaliwa ni katika Januari, Februari, Machi, chochote, kwamba ni ufanisi kujenga meza hash. Ni kujenga tu ndoo kwamba you kutatua mambo yako katika ili uweze kupata yao rahisi zaidi. Hivyo njia hii wakati mimi haja kupata moja ya wewe, Sina kutafuta njia ya kila ya majina yako. Naweza kuwa kama, oh, najua kwamba Danielle siku ya kuzaliwa ni in-- Watazamaji: --April. SPIKA 1: Aprili. Hivyo mimi kuangalia mwezi Aprili yangu ndoo, na kwa bahati yoyote, yeye itabidi kuwa moja tu huko na muda wangu alikuwa mara kwa mara katika maana ya kwamba, ambapo kama mimi kuwa na kuangalia kupitia rundo zima la watu, ni kwenda kuchukua muda mrefu zaidi. Hivyo meza hash ni kweli ndoo tu. Njia rahisi ya kufikiria yao. Hivyo jambo muhimu sana kuhusu meza hash ni kazi hash. Hivyo mambo mimi tu kuongelea, kama barua yako ya kwanza ya jina yako ya kwanza au siku yako ya kuzaliwa kwa mwezi, haya ni mawazo kwamba kweli correlate kwa hash kazi. Ni njia tu ya kuamua ambayo ndoo uko kipengele huenda katika, sawa? Hivyo kwa pset hii, unaweza kuangalia juu ya pretty much yoyote ya kazi hash unataka. Haina kuwa yako mwenyewe. Kuna baadhi ya wale kweli baridi nje pale kwamba kufanya kila aina ya mambo math. Na kama unataka kufanya yako spellchecker super haraka, Napenda dhahiri kuangalia katika moja ya hizo. Lakini pia kuna rahisi ndio, kama compute Jumla ya maneno, kama kila herufi ina idadi. Compute jibu. Kwamba huamua ndoo. Wao pia wana ndio rahisi kwamba ni tu kama wote wa A hapa, yote ya B hapa. Yoyote mmoja wa wale. Kimsingi, ni tu anakwambia ambayo safu ripoti kipengele yako lazima kwenda katika. Tu kuamua bucket-- ni wote hash kazi ni. Hivyo hapa tuna mfano ambayo ni tu barua ya kwanza ya kamba kwamba nilikuwa tu kuzungumza juu. Hivyo una baadhi hash kwamba tu barua ya kwanza ya kamba yako minus A, ambayo nitakupa baadhi idadi kati ya 0 na 25. Na nini unataka kufanya ni kuhakikisha kwamba hii inawakilisha ukubwa wa hash yako table-- jinsi ndoo wengi kuna. Na wengi wa hawa kazi hash, wao ni kwenda kuwa kurudi maadili kwamba huenda kuwa mbali juu idadi ya ndoo kwamba kwa kweli kuwa na katika hash meza yako, hivyo unahitaji kufanya uhakika na Mod na wale. Vinginevyo, ni kwenda kusema, oh, ni lazima kuwa katika ndoo 5,000 lakini wewe tu 30 ndoo katika hash meza yako. Na bila shaka, sisi wote tunajua kwamba ni kwenda kusababisha baadhi ya makosa mambo. Ili kuhakikisha Mod na ukubwa wa hash meza yako. Baridi. Hivyo migongano. Ni kila mtu nzuri hadi sasa? Mmhmm? Watazamaji: Kwa nini ni kurudi thamani kama mkubwa? SPIKA 1: Kulingana na algorithm kwamba hash kazi yako anatumia. Baadhi yao kufanya mambo ya kuzidisha. Na ni wote kuhusu kupata hata usambazaji, hivyo kufanya baadhi ya kweli mambo mambo wakati mwingine. Hayo ni yote. Kitu kingine chochote? OK. Hivyo migongano. Kimsingi, kama nilivyosema awali, katika bora kesi, ndoo yoyote mimi kuangalia katika ni kwenda na jambo moja, hivyo mimi si kuwa na kuangalia wakati wote, haki? Mimi aidha kujua ni huko au ni si, na kwamba ni nini sisi kweli wanataka. Lakini kama tuna maelfu ya pointi data na chini ya idadi hiyo ndoo, tunakwenda kuwa collisions ambapo hatimaye kitu ni kwenda kuwa na kuishia katika ndoo ambayo tayari ina kipengele. Hivyo swali ni, nini sisi kufanya katika kesi hiyo? Tufanye nini? Sisi tayari kuwa na kitu huko? Je, sisi tu kutupa nje? Hakuna Tuna kuweka wote wawili. Hivyo njia kwamba sisi kawaida kufanya hivyo ni nini? Ni muundo wa data kile sisi tu kuongelea? Watazamaji: Wanaohusishwa orodha. SPIKA 1: orodha wanaohusishwa. Hivyo sasa, badala ya kila moja ya haya ndoo tu kuwa moja ya kipengele, itakuja vyenye orodha wanaohusishwa ya mambo ambayo walikuwa heshi ndani yake. OK, haina kila mtu aina ya kupata wazo kwamba? Sababu sisi hakuweza kuwa safu kwa sababu hatujui mambo ngapi ni kwenda kuwa huko. orodha wanaohusishwa inaruhusu sisi kuwa tu idadi halisi kwamba ni heshi ndani ya kwamba ndoo, haki? Hivyo linear udadisi ni kimsingi idea-- hii ni moja ya njia ya kukabiliana na mgongano. Nini unaweza kufanya ni kama, katika hii kesi, berry ilikuwa heshi ndani ya 1 na tayari tuna kitu pale, wewe tu kuendelea chini mpaka kupata yanayopangwa tupu. Hiyo ni moja ya njia ya kushughulikia hilo. njia nyingine ya kushughulikia ni pamoja na kile sisi tu called-- wanaohusishwa orodha inaitwa chaining. Hivyo wazo hii kazi kama hash meza yako unafikiri ni kubwa kuliko data yako kuweka au kama wewe wanataka kujaribu na kupunguza chaining mpaka ni muhimu kabisa. Hivyo jambo moja ni linear uchunguzi wazi maana kwamba hash kazi yako si kama kabisa muhimu kwa sababu wewe ni kwenda kuishia kutumia hash kazi yako, kupata kwa uhakika, you linear kuchunguza chini mahali baadhi ya ambayo inapatikana. Lakini sasa, bila shaka, kitu chochote kingine kwamba mwisho huko juu, wewe ni kwenda kuwa na kutafuta hata zaidi chini. Na kuna mengi zaidi search gharama kwamba huenda katika inputting kipengele katika hash meza yako sasa, haki? Na sasa wakati wa kwenda na kujaribu na kupata berry tena, wewe kwenda hash yake, na ni kwenda kusema, oh, kuangalia katika ndoo 1, na si kwenda kuwa na katika ndoo 1, hivyo wewe ni kwenda na tindanga njia ya mapumziko ya haya. Hivyo ni wakati mwingine muhimu, lakini katika kesi nyingi, tunakwenda kusema kwamba chaining ni nini unataka kufanya. Hivyo sisi aliyesema kuhusu hili mapema. I got mbele kidogo mwenyewe. Lakini chaining kimsingi kwamba kila ndoo katika hash meza yako ni tu orodha wanaohusishwa. Hivyo njia nyingine, au zaidi ya kiufundi njia, kufikiria meza hash ni kwamba ni tu safu ya orodha wanaohusishwa, ambayo wakati wewe ni kuandika kamusi yako na wewe ni kujaribu mzigo, kufikiri ya kama safu ya orodha wanaohusishwa itakuwa kufanya ni rahisi sana kwa wewe initialize. Watazamaji: Hivyo hash meza ina ukubwa predetermined, kama [inaudible] ndoo? SPIKA 1: Haki. Hivyo ina idadi ya seti ya ndoo kwamba determine-- ambayo nyie lazima kujisikia huru kucheza na. Ni inaweza kuwa pretty baridi kuona nini kinatokea kama mabadiliko ya namba yako ya ndoo. Lakini yeah, ina kuweka idadi ya ndoo. Nini utapata fit kama mambo mengi kama unahitaji ni chaining hii tofauti ambapo wewe kuwa wanaohusishwa orodha katika kila ndoo. Hiyo ina maana hash meza yako itakuwa hasa ukubwa kwamba unahitaji kuwa, haki? Hiyo ni hatua nzima ya orodha wanaohusishwa. Baridi. Hivyo kila mtu OK huko? Wote haki. Ah. Nini kilichotokea tu? Kweli sasa. Nadhani kuna mtu mauaji yangu. OK tunakwenda kwenda katika inajaribu, ambayo ni mambo kidogo. Mimi kama meza hash. Nadhani wao ni kweli baridi. Inajaribu ni baridi, pia. Hivyo haina mtu yeyote kumbuka kile kujaribu ni? Unapaswa kuwa wamekwenda juu ya ni kwa ufupi katika hotuba? Unakumbuka aina ya jinsi kazi? Watazamaji: Mimi nodding tu kwamba hatukuwa kwenda juu yake. SPIKA 1: Hatuna kwenda juu yake. OK, sisi ni kweli kwenda juu yake sasa ni nini sisi ni kusema. Watazamaji: Hiyo ni kwa retrieval mti. SPIKA 1: Yeah. Ni retrieval mti. Kutisha. Hivyo jambo moja taarifa hapa ni kwamba sisi ni kuangalia wahusika binafsi hapa, haki? Hivyo kabla na hash yetu kufanya kazi, sisi walikuwa kuangalia maneno kwa ujumla, na sasa sisi ni kuangalia zaidi katika wahusika, haki? Hivyo tuna Maxwell juu hapa na Mendel. Hivyo kimsingi try-- njia ya kufikiri kuhusu hili ni kwamba kila ngazi hapa ni safu ya barua. Hivyo hii ni mzizi nodi yako hapa, haki? Hii ina wahusika wote wa alfabeti kwa ajili ya kuanza kila neno. Na nini unataka kufanya ni kusema, OK, tuna baadhi ya neno M. Sisi ni kwenda kuangalia kwa Maxwell, hivyo sisi kwenda M. Na M pointi kwa ujumla mengine safu ambapo kila neno, kwa muda mrefu kama kuna ni neno ambayo ina A kama barua ya pili, muda mrefu kama kuna neno kwamba ina B kama barua ya pili, itakuwa na pointer kwenda baadhi safu ijayo. Kuna pengine si neno kwamba mbunge kitu, hivyo katika P nafasi katika hii safu, itakuwa tu kuwa null. Ni kusema, sawa, kuna neno hakuna kwamba ina M ikifuatiwa na P, sawa? Hivyo kama sisi kufikiri juu yake, kila moja ya mambo haya madogo ni kweli mmoja wa haya arrays kubwa kutoka A kupitia Z. Hivyo kile inaweza kuwa moja ya mambo kwamba ni aina ya drawback ya kujaribu? Watazamaji: mengi ya kumbukumbu. SPIKA 1: Ni tani ya kumbukumbu, haki? Kila moja ya vitalu haya hapa inawakilisha nafasi ya 26, 26 kipengele safu. Hivyo inajaribu kupata incredibly nafasi nzito. Lakini wao ni haraka sana. Hivyo haraka sana lakini kweli nafasi ufanisi. Aina ya kuwa na takwimu nje ambayo moja unataka. Hizi ni kweli baridi kwa pset yako, lakini wao kufanya kuchukua mengi ya kumbukumbu, hivyo biashara mbali. Yeah? Watazamaji: Je, inawezekana kuanzisha kujaribu na kisha mara moja una yote data katika hilo kuwa wewe need-- Sijui kama kwamba ingekuwa kufanya maana. Mimi nilikuwa kupata kuondoa wote Wahusika NULL, lakini basi ungependa kuwa na uwezo wa ripoti ya them-- SPIKA 1: Bado unahitaji yao. Watazamaji: - njia ile ile kila wakati. SPIKA 1: Yeah. Unahitaji wahusika NULL basi unajua kama kuna si neno huko. Ben hakuwa una kitu unataka? OK. Haki wote, hivyo tunakwenda kwenda kidogo zaidi undani wa kiufundi nyuma a kujaribu na kazi kwa njia ya mfano. OK, hivyo hii ni kitu kimoja. Ambapo katika orodha wanaohusishwa, kuu yetu aina of-- nini neno nataka? - kama kujenga block ilikuwa nodi. Katika kujaribu, sisi pia kuwa nodi, lakini ni defined tofauti. Hivyo tuna baadhi bool kwamba inawakilisha kama neno kweli lipo katika eneo hili, na kisha tuna baadhi ya safu here-- au tuseme, hii ni pointer safu ya wahusika 27. Na hii ni kwa ajili ya, katika kesi hii, hii 27-- mimi nina uhakika wote wa wewe ni kama, kusubiri, kuna barua 26 katika alfabeti. Kwa nini tuna 27? Hivyo kutegemea njia wewe kutekeleza huu, hii ni kutoka pset kwamba kuruhusiwa kwa apostrophes. Hivyo kwamba ni kwa nini moja ya ziada. Utasikia pia kuwa katika baadhi ya kesi null Terminator ni pamoja kama moja ya wahusika kwamba ni kuruhusiwa kuwa, na kwamba ni jinsi wao kuangalia kuona kama ni mwisho wa neno. Kama wewe ni nia, angalia Video Kevin juu study.cs50, vile vile Wikipedia ina baadhi rasilimali nzuri huko. Lakini sisi ni kwenda kupitia tu aina jinsi unavyoweza kazi kwa njia ya kujaribu kama wewe ni kupewa moja. Hivyo tuna moja super rahisi hapa kwamba ina maneno "popo" na "zoom" katika wao. Na kama sisi kuona hapa, hii nafasi kidogo hapa inawakilisha bool yetu kwamba anasema, ndiyo, hii ni neno. Na kisha hii ina zetu arrays ya wahusika, haki? Hivyo sisi ni kwenda kupitia kutafuta "popo" katika kujaribu hili. Hivyo kuanza saa ya juu, haki? Na tunajua kwamba b sambamba na ripoti ya pili, kipengele cha pili katika safu hii, kwa sababu na b. Hivyo takriban moja ya pili. Na inasema, OK, baridi, kufuata kwamba katika safu ya pili, kwa sababu kama sisi kukumbuka, si kwamba kila moja ya haya kweli ina kipengele. Kila moja ya arrays haya ina pointer, haki? Ni tofauti muhimu kufanya. Najua hii ni kwenda be-- inajaribu ni kweli ni vigumu kupata mara ya kwanza, hivyo hata kama hii ni mara ya pili au ya tatu na ni bado aina ya Wanajidai vigumu, Mimi ahadi kama wewe kwenda kuangalia short tena kesho, utakuwa pengine mantiki mengi zaidi. Inachukua mengi Digest. Mimi bado wakati mwingine ni kama, kusubiri, ni nini kujaribu? Je, mimi kutumia hili? Hivyo tuna b katika kesi hii, ambayo ni ya pili ripoti yetu. Kama tungekuwa na, kusema, c au d au barua nyingine yoyote, tunahitaji ramani kwamba nyuma ya ripoti ya safu yetu kwamba kwamba sambamba na. Hivyo tunataka kuchukua kama rchar na sisi tu Ondoa mbali ramani ndani 0-25. Kila mtu mwema jinsi sisi ramani wahusika zetu? OK. Hivyo sisi kwenda moja ya pili na sisi kuona kwamba, ndiyo, ni si null. Tunaweza kuendelea na safu hii ijayo. Hivyo sisi kwenda kwenye safu hii ya pili hapa. Na sisi kusema, sawa, sasa sisi haja ya kuona kama ni hapa. Ni null au gani kweli kusonga mbele? Hivyo kweli hatua mbele katika safu hii. Na sisi kusema, sawa, t ni barua yetu ya mwisho. Hivyo sisi kwenda t katika ripoti. Na kisha sisi kusonga mbele kwa sababu kuna mtu mwingine. Na hii moja anasema kimsingi kwamba, ndiyo, inasema kwamba kuna neno here-- kwamba kama wewe kufuata hii njia, wewe wamewasili katika neno, ambayo sisi kujua ni "popo." Ndiyo? Watazamaji: Je, ni kiwango kuwa na kwamba kama index 0 na kisha kuwa na aina katika 1 au kuwa na mwishoni? SPIKA 1: Hapana Hivyo kama sisi kuangalia nyuma katika yetu tamko hapa, ni bool, hivyo ni kipengele yake mwenyewe katika nodi yako. Hivyo si sehemu ya safu. Baridi. Hivyo wakati sisi kumaliza neno yetu na tuko katika safu hii, nini tunataka kufanya ni kufanya kuangalia kwa hii neno. Na katika kesi hii, itakuwa kurudi ndiyo. Kadhalika kwamba kumbuka, tunajua kwamba "zoo" - sisi kujua kama binadamu kwamba "zoo" ni neno, haki? Lakini ni kujaribu hapa ingekuwa kusema, hakuna, siyo. Na kusema kwamba kwa sababu sisi si mteule kama neno hapa. Ingawa tunaweza traverse kupitia kwa safu hii, kujaribu hii kusema kwamba, hakuna, zoo si katika kamusi yako kwa sababu tuna si mteule kama vile. Hivyo njia moja ya kufanya that-- oh, sorry, hii moja. Hivyo katika kesi hii, "zoo" si neno, lakini ni katika kujaribu yetu. Lakini katika hii moja, wanasema tunataka kuanzisha neno "kuoga," nini kinatokea ni sisi kufuata through-- b,, t. Tuko katika safu hii, na sisi kwenda kutafuta h. Katika kesi hiyo, wakati sisi kuangalia pointer katika h, ni akizungumzia null, sawa? Hivyo isipokuwa ni wazi akizungumzia safu mwingine, kudhani kwamba kuyatumia yote katika safu hii ni akizungumzia null. Hivyo katika kesi hii, h ni akizungumzia kwa null hivyo hatuwezi kufanya kitu chochote, hivyo itakuwa pia kurudi uongo, "bath" si katika hapa. Hivyo sasa sisi ni kweli kwenda kupitia jinsi gani sisi kweli kusema kwamba "zoo" ni katika kujaribu yetu. Jinsi gani sisi kuingiza "zoo" katika kujaribu yetu? Hivyo katika njia sawa kwamba sisi ilianza na orodha yetu wanaohusishwa, sisi kuanza saa mizizi. Wakati katika shaka, kuanza saa mizizi ya mambo haya. Na tutaweza kusema, sawa, z. z ipo katika hili, na ni gani. Hivyo wewe ni kuhamia kwenye safu yako ijayo, sawa? Na kisha kwenye moja ya pili, sisi kusema, sawa, haina o zipo? Ni gani. Hii tena. Na kadhalika moja yetu ijayo, tumekuwa alisema, OK, "zoo" tayari lipo hapa. Wote tunahitaji kufanya ni kuweka hii sawa kwa kweli, kwamba kuna neno pale. Kama alikuwa na kufuatiwa kila kitu hadi kabla ya hatua hiyo, ni neno, hivyo tu kuweka sawa na hayo. Ndiyo? Watazamaji: Hivyo basi gani kwamba maana kwamba "ba" ni neno pia? SPIKA 1: Hapana Hivyo katika kesi hii, "ba" tunataka kupata hapa, tunataka kusema ni neno, na bado ingekuwa hakuna. OK? Mmhmm? Watazamaji: Hivyo mara moja wewe ni neno na kusema ndiyo, basi ni vyenye kwenda m? SPIKA 1: Hivyo hii ina kufanya with-- wewe ni upakiaji huu katika. Wewe kusema "zoo" ni neno. Baada ya kwenda kwa check-- kama, kusema unataka kusema, haina "zoo" zipo katika kamusi hii? Wewe ni kwenda tu kutafuta "zoo" na kisha kuangalia kuona kama ni neno. Wewe kamwe kwenda kwa hoja kupitia kwa m sababu si kwamba nini wewe kutafuta. Hivyo kama sisi kweli alitaka kuongeza "bath" katika kujaribu hii, tunataka kufanya kitu kimoja kama tulivyofanya na "zoo" ila tunataka kuona kwamba wakati sisi kujaribu na kupata h, haipo. Hivyo unaweza kufikiria hili kama kujaribu kuongeza nodi mpya katika orodha wanaohusishwa, hivyo tunataka haja ya kuongeza mwingine moja ya arrays haya, kama hivyo. Na kisha nini sisi ni sisi tu ya kuweka h kipengele cha safu hii akizungumzia hii. Na kisha gani tunataka kufanya hapa? Kuongeza sawa na kweli sababu ni neno. Baridi. Mimi najua. Inajaribu si kusisimua zaidi. Matumaini yangu, najua. Hivyo jambo moja kwa kutambua na inajaribu, Mimi alisema, wao ni ufanisi sana. Hivyo tumeona wao kuchukua tani ya nafasi. Wao ni aina ya utata. Hivyo ni kwa nini sisi milele kutumia haya? Sisi kutumia haya kwa sababu wao ni incredibly ufanisi. Hivyo kama wewe ni milele kuangalia neno, wewe ni tu imepakana na urefu wa neno. Hivyo kama wewe ni kuangalia kwa neno kwamba ni ya urefu tano, wewe ni milele tu kwenda na kufanya saa zaidi kulinganisha tano, sawa? Hivyo inafanya kimsingi mara kwa mara. Kama insertion na Luke ni wakati wa mara kwa mara kimsingi. Hivyo kama unaweza milele kupata kitu katika muda wa mara kwa mara, hiyo ni kama nzuri kama anapata. Huwezi kupata bora kuliko wakati mara kwa mara kwa ajili ya mambo haya. Hivyo kwamba ni moja ya pluses mkubwa ya anajaribu. Lakini ni nafasi kubwa mno. Hivyo aina ya kuwa na kuamua nini muhimu zaidi na wewe. Na juu ya kompyuta ya leo, nafasi hiyo kujaribu inaweza kuchukua hadi labda haina kuathiri kwamba mengi, lakini labda wewe ni kushughulika na kitu ambayo ina mambo mbali, mbali zaidi, na kujaribu si tu nafuu. Ndiyo? Watazamaji: Ngoja, hivyo una 26 barua katika kila moja? SPIKA 1: Mmhmm. Yeah, una 26. Una baadhi ni alama neno na kisha una 26 kuyatumia katika kila moja. Na wao ni point-- Watazamaji: Na kila 26, gani wao kila mmoja kuwa 26? SPIKA 1: Ndiyo. Na kwamba ni kwa nini, kama unaweza kuona, expands haraka kabisa. Wote haki. Hivyo sisi ni kwenda kupata katika miti, ambayo Najisikia kama ni rahisi na pengine kuwa nzuri ahueni kidogo kutoka inajaribu huko. Hivyo hopefully zaidi ya wewe tumeona mti kabla. Si kama pretty ndio nje, ambayo mimi sijui kama mtu yeyote akaenda nje hivi karibuni. Nilikwenda apple kuokota mwishoni mwa wiki hii, na oh gosh yangu, ilikuwa nzuri. Sikujua majani inaweza kuangalia kwamba pretty. Hivyo hii ni tu mti, haki? Ni baadhi tu ya nodi, na anazungumzia rundo la nodes nyingine. Kama unaweza kuona hapa, hii ni aina ya mandhari ya mara kwa mara. Vituo akizungumzia nodes ni aina ya kiini cha miundo wengi data. Ni tu inategemea jinsi sisi kuwa nao uhakika na kila mmoja na jinsi sisi traverse njia yao na jinsi sisi kuingiza mambo ambayo huamua sifa zao tofauti. Hivyo baadhi tu istilahi, ambayo nimekuwa kutumika kabla. Hivyo mzizi ni chochote ni saa ya juu sana. ni mahali ambapo sisi daima kuanza. Unaweza kufikiria kama kichwa pia. Lakini kwa ajili ya miti, sisi huwa na rejea ni kama mizizi. Chochote wakati here-- chini katika sana, bottom-- sana ni kuchukuliwa majani. Hivyo huenda pamoja na mti mzima jambo, haki? Majani ni pembezoni ya mti yako. Na kisha sisi pia kuwa wanandoa wa suala kwa majadiliano juu ya nodes katika uhusiano kwa kila mmoja. Hivyo tuna mzazi, watoto, na ndugu zake. Hivyo katika kesi hii, 3 ni mzazi wa 5, 6 na 7. Hivyo mzazi ni chochote ni hatua moja juu ya chochote ni akimaanisha, hivyo tu kama mti familia. Hopefully, hii ni kidogo wote kidogo zaidi Intuitive kuliko anajaribu. Ndugu ni yoyote kwamba kuwa mzazi sawa, haki? Wao uko juu ya kiwango sawa hapa. Na kisha, kama mimi nilikuwa akisema, watoto ni tu chochote ni hatua moja chini nodi katika swali, sawa? Baridi. Hivyo mti binary. Je, mtu yeyote athari ya nadhani kwenye moja ya sifa za mti binary? Watazamaji: Max majani mawili. SPIKA 1: Haki. Hivyo max ya majani mawili. Hivyo katika hii moja kabla, tulikuwa hii moja kwamba alikuwa tatu, lakini katika mti binary, una max ya mbili watoto kwa kila mzazi, haki? Kuna mwingine kuvutia tabia. Je, mtu yeyote kujua kwamba? Binary mti. Hivyo mti binary itakuwa na kila kitu juu ya the-- moja hii si sorted-- lakini katika yamepangwa binary mti, kila kitu juu ya haki ni mkubwa kuliko mzazi, na kila kitu juu ya kushoto ni chini ya mzazi. Na kwamba imekuwa Jaribio swali kabla, hivyo vizuri kujua. Hivyo njia sisi kufafanua hii, tena, tuna nodi nyingine. Hii inaonekana ni sawa na nini? Doubly Watazamaji: Wanaohusishwa orodha SPIKA 1: maradufu orodha wanaohusishwa, haki? Hivyo kama sisi kuchukua nafasi ya hii na uliopita na wa pili, hii itakuwa orodha doubly wanaohusishwa. Lakini katika kesi hii, sisi kweli kuwa kushoto na kulia na hiyo ni yake. Vinginevyo, ni sawa. Bado tuna kipengele wewe ni kuangalia kwa, na wewe tu kuyatumia mbili kwenda chochote ijayo. Yeah, hivyo binary tafuta mti. Kama sisi taarifa, kila kitu juu ya haki hapa ni than-- zaidi au kila kitu mara moja na haki hapa ni mkubwa kuliko, kila kitu hapa ni chini ya. Hivyo kama sisi walikuwa na kutafuta njia ya, ni inapaswa kuangalia karibu sana na binary tafuta hapa, haki? Isipokuwa badala ya kuangalia katika nusu safu, sisi ni kuangalia tu katika aidha kushoto upande au upande wa kulia wa mti. Hivyo anapata kidogo rahisi, nadhani. Hivyo kama mizizi yako ni null, wazi ni tu ya uongo. Na kama ni huko, ni wazi ni kweli. Kama ni chini ya, sisi kutafuta kushoto. Kama ni kubwa kuliko, sisi kutafuta haki. Ni hasa kama search binary, tu muundo tofauti data kwamba sisi ni kutumia. Badala ya safu, ni tu mti binary. OK, mwingi. Na pia, inaonekana kama sisi anaweza kuwa kidogo ya muda. Kama sisi kufanya, mimi nina furaha na kwenda juu ya yoyote ya hii tena. OK, hivyo mwingi. Je, mtu yeyote kumbuka kile stacks-- sifa yoyote ya stack? OK, hivyo wengi wetu, nadhani, kula katika dining halls-- kama vile sisi inaweza si kama. Lakini ni wazi, unaweza kufikiria stack literally tu kama stack ya trays au stack ya mambo. Na nini muhimu kutambua ni kwamba ni something-- tabia kwamba sisi kuiita by-- ni LIFO. Je, mtu yeyote kujua nini kwamba anasimama kwa ajili ya? Mmhmm? Watazamaji: Mwisho, kwanza nje. SPIKA 1: Haki, mwisho katika, kwanza nje. Hivyo kama sisi kujua, kama sisi ni stacking vitu up, jambo rahisi kunyakua off-- na labda jambo pekee tunaweza kunyakua mbali kama stack yetu ni enough-- kubwa ni kipengele kwamba juu. Hivyo chochote ilikuwa kuweka kwenye last-- kama tunaona hapa, chochote alikuwa kusukuma juu zaidi recently-- ni itakuwa ya kwanza Jambo kwamba sisi pop mbali, sawa? Hivyo nini sisi hapa ni mwingine typedef struct. Hii ni kweli tu kama ajali shaka katika muundo data, hivyo kuna mengi kutupwa katika wewe guys. Mimi najua. Hivyo bado struct nyingine. Yay kwa miundo. Na katika kesi hii, ni baadhi pointer safu ambayo ina baadhi ya uwezo. Hivyo hii inawakilisha stack yetu hapa, kama safu yetu halisi hiyo ni kufanya mambo yetu. Na kisha hapa tuna baadhi ya kawaida. Na kawaida, unataka kuweka wimbo wa jinsi kubwa stack yako ni kwa sababu kile ni kwenda kuruhusu wewe kufanya ni kama unajua ukubwa, utapata kusema, OK, mimi katika uwezo? Naweza kuongeza chochote zaidi? Na pia atakwambia ambapo juu ya stack yako ni hivyo unajua nini unaweza kweli kuchukua mbali. Na kwamba kweli kwenda kuwa zaidi kidogo ya wazi hapa. Hivyo kwa kushinikiza, jambo moja, kama wewe walikuwa milele kutekeleza kushinikiza, kama mimi alikuwa akisema tu, yako stack ina ukubwa mdogo, haki? Safu yetu alikuwa na baadhi ya uwezo. Ni safu. Ni fasta ukubwa, hivyo tunahitaji kuhakikisha kwamba sisi siyo kuweka zaidi katika safu yetu kuliko sisi kweli kuwa nafasi kwa. Hivyo wakati wewe ni kujenga kushinikiza kazi, jambo la kwanza kufanya ni kusema, sawa, kufanya mimi kuwa na nafasi katika stack yangu? Kwa sababu kama mimi si, pole, Siwezi kuhifadhi kipengele yako. Kama mimi kufanya, basi unataka kuhifadhi ni juu ya stack, haki? Na hii ni kwa nini tuna kuweka wimbo wa kawaida yetu. Kama hatuwezi kuweka wimbo wa kawaida yetu, hatujui ambapo kuweka. Hatujui mambo ngapi ni katika safu yetu tayari. Kama ni wazi kuna njia kwamba labda unaweza kufanya hivyo. Unaweza initialize kila kitu kwa null na kisha kuangalia kwa ajili ya karibuni NULL, lakini jambo rahisi tu kusema, sawa, kuweka wimbo wa kawaida. Kama Mimi najua kuwa mambo manne katika safu yangu, hivyo jambo la pili kwamba sisi kuweka juu, sisi ni kwenda kuhifadhi katika ripoti 4. Na kisha, bila shaka, hii ina maana kwamba umefanya mafanikio kusukuma kitu kwenye stack yako, wanataka kuongeza ukubwa ili kujua ambapo wewe ni hivyo kwamba unaweza kushinikiza mambo zaidi juu ya. Hivyo kama sisi ni kujaribu pop kitu mbali ya stack, nini inaweza kuwa jambo la kwanza kwamba tunataka kuangalia kwa? Wewe ni kujaribu kuchukua kitu mbali ya stack yako. Je, una hakika kuna kitu katika stack yako? Hakuna Hivyo nini kinaweza tunataka kuangalia? Watazamaji: [inaudible]. SPIKA 1: Angalia kwa kawaida? Ukubwa. Hivyo tunataka kuangalia kuona kama ukubwa yetu ni kubwa kuliko 0, sawa? Na kama ni, basi tunataka kupunguza kawaida yetu na 0 na kurudi kwamba. Kwa nini? Katika moja ya kwanza tulikuwa kusukuma, sisi kusukuma yake kwenye ukubwa na kisha updated kawaida. Katika kesi hii, sisi ni decrementing ukubwa na kisha kuchukua ni mbali, kukwanyua ni kutoka safu yetu. Kwa nini huenda sisi kufanya hivyo? Hivyo kama nina jambo moja juu ya stack yangu, nini itakuwa kawaida yangu katika hatua hiyo? 1. Na ambapo ni kipengele 1 kuhifadhiwa? Nini ripoti? Watazamaji: 0. SPIKA 1: 0. Hivyo katika kesi hii, sisi daima haja ya kufanya sure-- badala ya kurudi ukubwa minus 1, kwa sababu sisi kujua kwamba kipengele yetu ni kwenda kuhifadhiwa katika 1 chini chochote kawaida yetu ni, hii tu inachukua huduma hiyo. Ni njia kidogo zaidi ya kifahari. Na sisi tu ya mapunguzo wetu ukubwa na kisha kurudi kawaida. Mmhmm? Watazamaji: Mimi nadhani tu kwa ujumla, kwa nini muundo huu data kuwa na manufaa? SPIKA 1: Ni inategemea mazingira yako. Hivyo kwa baadhi ya nadharia, kama wewe ni kufanya kazi with-- OK, napenda kuona kama kuna mmoja manufaa kwamba ni manufaa kwa zaidi ya nje ya CS. Na mwingi, wakati wowote unahitaji kuweka wimbo wa kitu ambacho ni hivi karibuni aliongeza ni wakati wewe kwenda wanataka kutumia stack. Na siwezi kufikiria nzuri mfano wa kwamba hivi sasa. Lakini, wakati hivi karibuni Jambo muhimu zaidi na wewe, hiyo wakati stack ni kwenda kuwa na manufaa. Mimi nina kujaribu kufikiri kama kuna moja nzuri kwa ajili ya hii. Kama mimi nadhani wa mfano mzuri katika ijayo Dakika 20, mimi dhahiri kukuambia. Lakini kwa ujumla, kama kuna kitu chochote, kama nilivyosema zaidi, ambapo hivi karibuni ni muhimu zaidi, kwamba ambapo stack anakuja katika kucheza. Wakati foleni ni aina ya kinyume. Na mbwa wote kidogo. Je, huyu si kubwa, haki? Najisikia kama mimi lazima tu Bunny video haki ya katikati ya sehemu kwa ajili ya guys sababu hii ni sehemu makali. Hivyo foleni. Kimsingi foleni ni kama mstari. You guys mimi nina uhakika kama hii ya matumizi ya kila siku, tu kama katika dining kumbi zetu. Hivyo tuna kwenda katika na kupata trays yetu, mimi nina kuhakikisha una kusubiri katika mstari swipe au kupata chakula. Hivyo tofauti hapa ni kwamba hii ni FIFO. Hivyo kama LIFO kwa mara ya mwisho katika, kwanza nje, FIFO ni ya kwanza katika, nje ya kwanza. Hivyo hii ni ambapo chochote kuweka juu ya kwanza ni yako muhimu. Hivyo kama wewe walikuwa wakisubiri katika line-- unaweza you kufikiria kama wewe akaenda kwenda kupata iPhone mpya na ilikuwa stack ambapo Mtu wa mwisho katika mstari got ni ya kwanza, watu bila kuua kila mmoja. Hivyo FIFO, tuko wote familiar sana na katika ulimwengu wa kweli hapa, na yote ina nini na kweli aina ya recreating mstari huu nzima na kupanga foleni muundo. Hivyo ambapo pamoja na stack, tuna kushinikiza na pop. Na foleni, tuna enqueue na dequeue. Hivyo enqueue kimsingi ina maana kuiweka kwenye nyuma, na njia dequeue kuchukua mbali kutoka mbele. Hivyo mfumo wetu data ni kidogo ngumu zaidi. Tuna jambo la pili kwa kuweka wimbo wa. Hivyo bila kichwa, hii ni hasa stack, haki? Hii ni muundo sawa na stack. Kitu pekee tofauti na sasa ni sisi kichwa hii, ambayo unafikiri nini ni kwenda kuweka wimbo wa? Watazamaji: moja ya kwanza. SPIKA 1: Haki, Jambo la kwanza kwamba sisi kuweka katika. mkuu wa foleni yetu. Yeyote ni ya kwanza katika mstari. Haki wote, hivyo kama sisi kufanya enqueue. Tena, na yoyote ya hizi miundo data, tangu sisi ni kushughulika na safu, sisi haja ya kuangalia kama tuna nafasi. Hii ni aina ya kama mimi kuwaambia nyie, kama wewe kufungua faili, unahitaji kuangalia kwa null. Na yoyote ya hizi mwingi na foleni, unahitaji kuona kama kuna nafasi kwa sababu sisi ni kushughulika na fasta ukubwa safu, kama sisi kuona here-- 0, 1 yote hadi 5. Hivyo kile sisi kufanya katika kesi hiyo ni kuangalia kuona kama bado tuna nafasi. Ni kawaida yetu chini ya uwezo? Kama ni hivyo, tunahitaji kuhifadhi katika mkia na sisi update kawaida yetu. Hivyo nini kinaweza kuwa mkia katika kesi hii? Ni si wazi imeandikwa nje. Jinsi gani sisi kuhifadhi? Gani mkia kuwa? Basi hebu kutembea kwa njia ya mfano huu. Hivyo hii ni safu ya ukubwa 6, haki? Na tuna haki ya sasa, kawaida yetu ni 5. Na wakati sisi kuweka katika, ni kwenda kwenda katika tano ripoti, haki? Hivyo kuhifadhi katika mkia. Njia nyingine ya kuandika mkia ingekuwa tu kuwa safu yetu ya ripoti ya ukubwa, haki? Hii ni kawaida 5. Jambo la pili ni kwenda kwenda katika 5. Baridi? OK. Ni anapata kidogo ngumu zaidi wakati sisi kuanza messing na kichwa. Ndiyo? Watazamaji: Je, hiyo inamaanisha kwamba sisi ingekuwa alitangaza safu kwamba ilikuwa vipengele tano kwa muda mrefu na basi tuko kuongeza kwenye hilo? SPIKA 1: Hapana Hivyo katika kesi hii, hii ni stack. Hii itakuwa alitangaza kama safu ya ukubwa 6. Na katika kesi hii, sisi tu moja nafasi kushoto. OK, hivyo jambo moja ni katika hii kesi, kama kichwa yetu ni saa 0, kisha sisi tu inaweza kuongeza yake katika kawaida. Lakini anapata trickier kidogo kwa sababu kwa kweli, wao hawana slide kwa hili, hivyo mimi nina kwenda kuteka moja kwa sababu si kabisa kuwa rahisi mara moja kuanza kupata kuondoa mambo. Hivyo ambapo pamoja na stack wewe tu milele kuwa na wasiwasi kuhusu kile kawaida ni wakati wewe ni kuongeza kitu kwenye, na foleni pia unahitaji kufanya kuhakikisha kwamba kichwa yako ni waliendelea kwa, kwa sababu jambo zuri kuhusu foleni ni kwamba kama wewe si katika uwezo, unaweza kweli kufanya hivyo wrap kuzunguka. OK, hivyo moja thing-- oh, hii ni chaki kutisha. Jambo moja kufikiria ni kesi. Tutaweza tu kufanya mitano. OK, hivyo tunakwenda kusema kichwa ni hapa. Hii ni 0, 1, 2, 3, 4. kichwa huko, na tafadhali kuwa na mambo yao. Na tunataka kuongeza kitu katika, haki? Hivyo kitu kwamba tunahitaji kujua ni kwamba kichwa daima kwenda kwa hoja kwa njia hii na kisha kitanzi nyuma kote, sawa? Hivyo foleni hii ina nafasi, haki? Ina nafasi katika mwanzo, aina ya kinyume ya hii. Hivyo kile sisi haja ya kufanya ni sisi haja ya mahesabu ya mkia. Kama unajua kwamba yako kichwa hana wakiongozwa, mkia ni tu safu yako katika ripoti ya kawaida. Lakini katika hali halisi, kama wewe ni kutumia foleni, kichwa yako ni pengine kuwa updated. Hivyo nini unahitaji kufanya ni kweli mahesabu ya mkia. Hivyo kile sisi kufanya ni utaratibu huu hapa, ambayo mimi nina kwenda basi wewe guys kufikiri juu, na kisha tutaweza majadiliano juu yake. Hivyo hii ni uwezo. Hivyo hii itakuwa kweli kukupa njia ya kufanya hivyo. Kwa sababu katika kesi hii, ni nini? Kichwa yetu ni saa 1, ukubwa wetu ni 4. Kama sisi Mod kwamba kwa 5, sisi kupata 0, ambayo ni ambapo sisi lazima pembejeo yake. Hivyo basi katika kesi ya pili, kama tulikuwa kufanya hivyo, sisi kusema, sawa, hebu dequeue kitu. Sisi dequeue hii. Sisi kuchukua nje kipengele hii, haki? Na sasa kichwa yetu ni akizungumzia hapa, na tunataka kuongeza katika kitu kingine. Hii ni kimsingi nyuma ya mstari wetu, haki? Foleni unaweza wrap kuzunguka safu. Hiyo ni moja ya tofauti kubwa. Mwingi, huwezi kufanya hivyo. Na foleni, unaweza sababu wote kwamba mambo ni kwamba unajua nini ilikuwa hivi karibuni aliongeza. Tangu kila kitu kinaenda kuongezwa katika mwelekeo huu leftward, katika kesi hii, na kisha wrap kuzunguka, unaweza kuendelea kuweka katika mambo mapya mbele ya safu sababu si kweli mbele ya safu tena. Unaweza kufikiri ya mwanzo ya safu kama ambapo kichwa yako kweli ni. Hivyo formula hii ni jinsi mahesabu ya mkia yako. Je kwamba inafanya hisia? OK. OK, dequeue, na kisha wewe guys kuwa dakika 10 kuuliza mimi maswali yoyote inayoidhinisha unataka, kwa sababu najua ni mambo. Haki wote, hivyo katika way-- sawa Mimi sijui kama wewe guys niliona, lakini CS ni wote kuhusu mwelekeo. Mambo ni kiasi pretty huo, tu na tweaks vidogo. Jambo hivyo sawa hapa. Tunahitaji kuangalia kuona kama sisi kweli kuwa na kitu katika foleni yetu, haki? Kusema, sawa, ni kawaida yetu kubwa kuliko 0? Baridi. Kama sisi kufanya, basi sisi hoja kichwa yetu, ambayo ni nini mimi tu alionyesha hapa. Sisi update kichwa yetu kuwa moja zaidi. Na kisha sisi mapunguzo wetu ukubwa na kurudi kipengele. Kuna mengi zaidi ya saruji kanuni ya study.cs50.net, na mimi sana kupendekeza kwenda kwa njia hiyo kama una muda, hata kama ni tu Pseudo-kificho. Na kama wewe guys wanataka kuzungumza kupitia kwamba na mimi moja kwa moja, tafadhali napenda kujua. Ningependa kuwa na furaha kwa. Miundo data, kama wewe kuchukua CS 124, utasikia kujua kwamba miundo data kupata sana furaha na hii ni mwanzo tu. Hivyo najua ni vigumu. Ni sawa. Sisi mapambano. Mimi bado kufanya. Hivyo si wasiwasi sana kuhusu hilo. Lakini hiyo ni kimsingi yako ajali shaka katika miundo data. Najua ni mengi. Je, kuna chochote kwamba sisi ungependa kwenda tena? Chochote tunataka kuzungumza kupitia? Ndiyo? Watazamaji: Kwa mfano kwamba, hivyo mkia mpya ni katika 0 juu ya kwamba? SPIKA 1: Ndiyo. Watazamaji: OK. Hivyo basi kwenda kupitia, wewe d kuwa 1 plus 4 or-- SPIKA 1: Hivyo wewe walikuwa wakisema, wakati tunataka kwenda kufanya hii tena? Watazamaji: Yeah. Hivyo kama wewe walikuwa kuhesabia out-- ambapo ni you kuhesabu mkia kutoka katika hilo? SPIKA 1: Hivyo mkia ilikuwa in-- mimi iliyopita hii. Hivyo katika mfano huu hapa, hii ilikuwa safu sisi tunataka, sawa? Hivyo tuna mambo katika 1, 2, 3 na 4. Hivyo tuna kichwa yetu ni sawa na 1 katika hatua hii, na ukubwa wetu ni sawa na 4 katika hatua hii, haki? Wewe kukubaliana kwamba kesi? Hivyo sisi kufanya kichwa plus kawaida, ambayo inatupa 5, na kisha sisi Mod na 5. Sisi kupata 0, ambayo inatuambia kwamba ni 0 ambapo ni mkia yetu, ambapo tuna nafasi. Watazamaji: Nini kofia? SPIKA 1: uwezo. Pole. Hivyo kwamba ni ukubwa wa safu yako. Ndiyo? Watazamaji: [inaudible] kabla ya sisi kurudi kipengele? SPIKA 1: Hivyo sisi hoja kichwa au kurudi sasa? Hivyo kama sisi hoja moja, mapunguzo kawaida? Kushikilia. Mimi dhahiri alisahau nyingine. Kamwe akili. Kuna si formula nyingine. Yeah, wewe unataka kurudi kichwa na kisha kuondoka nyuma. Watazamaji: sawa, kwa sababu Katika hii uhakika, kichwani ilikuwa saa 0, na kisha unataka kurudi index 0 na kisha kufanya kichwa 1? SPIKA 1: Haki. Nadhani kuna mwingine formula aina ya kama hii. Sina ni juu ya kichwa yangu kama Sitaki kukupa moja sahihi. Lakini nadhani ni kikamilifu halali kwa kusema, sawa, kuhifadhi element-- hii chochote kipengele kichwa ya is-- mapunguzo yako ukubwa, hoja ya kichwa yako juu, na kurudi chochote kwamba kipengele ni. Hiyo ni kikamilifu halali. OK. Najisikia kama hii si kama most-- wewe si kwenda kutembea nje ya hapa kama, ndiyo, najua anajaribu. I got yote. Hiyo ni sawa. Mimi ahadi. Lakini miundo data ni kitu ambacho inachukua muda mwingi kupata kutumika. Pengine ni moja ya gumu mambo, nadhani, katika shaka. Hivyo ni dhahiri inachukua marudio na kuangalia at-- mimi hawakuwa kweli kujua orodha wanaohusishwa mpaka mimi mno pamoja nao, katika njia sawa kwamba sikuwa kweli kuelewa kuyatumia mpaka nimepata kufundisha kwa ajili ya mbili miaka na kufanya psets yangu mwenyewe kwa hayo. Inachukua mengi ya kikariri na wakati. Na hatimaye, itakuwa aina ya click. Lakini wakati huo huo, kama una aina ya kiwango cha juu ya uelewa wa nini hizi kufanya, faida yao na cons-- ambayo ni nini sisi kweli huwa na kusisitiza, hasa katika mwendo intro. Kama, kwa nini sisi kutumia a kujaribu juu ya safu? Kama, nini ni chanya na hasi ya kila mmoja wa wale? Na kuelewa biashara awamu ya pili kati ya kila ya miundo haya ni nini muhimu zaidi hivi sasa. Kuna inaweza kuwa moja mambo swali au mbili kwamba kwenda kuuliza wewe kutekeleza kushinikiza au kutekeleza pop au enqueue na dequeue. Lakini kwa sehemu kubwa, kuwa na kwamba kiwango cha juu ufahamu na zaidi ya kufahamu Intuitive ni muhimu zaidi kuliko kweli kuwa na uwezo wa kutekeleza. Ni d kuwa kweli kutisha kama nyote inaweza kwenda nje na kwenda kutekeleza kujaribu, lakini sisi kuelewa ni si lazima Jambo nzuri zaidi hivi sasa. Lakini unaweza katika pset yako, kama unataka kwa, na kisha utapata mazoezi, na kisha labda utasikia kweli kuelewa. Ndiyo? Watazamaji: OK, hivyo ambayo ndio ni sisi maana ya kutumia katika pset? Je, mimi haja ya kutumia mmoja wao? SPIKA 1: Ndiyo. Hivyo una uchaguzi wako. Nadhani katika kesi hii, tunaweza majadiliano juu ya pset kidogo kwa sababu mimi mbio kupitia hizi. Hivyo katika pset yako, una yako uchaguzi wa inajaribu au meza hash. Baadhi ya watu kujaribu na kutumia filters Bloom, lakini wale kitaalam si sahihi. Kwa sababu ya asili yao ya kubahatisha, wao kutoa chanya uongo wakati mwingine. Wao ni baridi kuangalia katika, ingawa. Sana kupendekeza kuangalia yao angalau. Lakini una uchaguzi wako kati ya hash meza na kujaribu. Na kwamba kinaendelea kuwa ambapo mzigo katika kamusi yako. Na wewe utakuwa haja ya kuchagua hash kazi yako, itabidi kuchagua jinsi wengi ndoo una, na itakuwa kutofautiana. Kama kama una ndoo zaidi, labda itabidi kukimbia kwa kasi. Lakini labda wewe ni kupoteza mengi ya nafasi ya kuwa njia, ingawa. Una takwimu ni nje. Mmhmm? Watazamaji: Ulisema kabla kwamba tunaweza kutumia kazi nyingine hash, kwamba hatuna kwa kujenga hash kazi? SPIKA 1: Ndiyo, haki. Hivyo literally kwa hash kazi yako, kama google "hash" na kuangalia kwa baadhi ya wale baridi. Wewe si inatarajiwa kujenga hash yako mwenyewe kazi. Watu kutumia yao Theses juu ya mambo haya. Hivyo msiwe na wasiwasi kuhusu kujenga yako mwenyewe. Kupata moja online kuanza na. Baadhi yao una kuendesha kidogo kuhakikisha aina ya kurudi mechi ya juu na whatnot, hivyo katika mwanzo, Ningependa kupendekeza kutumia kitu kweli rahisi kwamba labda tu hashes juu ya barua ya kwanza. Na kisha mara moja una kwamba kazi, kuchanganya baridi hash kazi. Mmhmm? Watazamaji: Je kujaribu kuwa au ufanisi lakini vigumu tu, like-- SPIKA 1: Hivyo kujaribu, nadhani, ni intuitively ngumu kutekeleza lakini ni haraka sana. Hata hivyo, inachukua hadi nafasi zaidi. Tena, unaweza kuongeza wote wawili wa wale walio katika njia tofauti na kuna njia to-- Watazamaji: Jinsi ni sisi graded juu ya hili? Je, ni matter-- SPIKA 1: Hivyo wewe ni hadhi njia ya kawaida. Wewe ni kwenda kuwa na hadhi ya kubuni. Njia yoyote ya kufanya, unataka kuhakikisha ni kama kifahari kama inaweza kuwa na kama ufanisi kama inaweza kuwa. Lakini kama wewe kuchagua kujaribu au hash meza, kwa muda mrefu kama ni kazi, sisi ni furaha na kwamba. Na kama wewe kutumia kitu ambacho hashes juu ya barua ya kwanza, hiyo ni nzuri, kama labda kama kubuni-busara. Sisi ni pia kufikia hatua katika semester-- hii Sijui kama guys noticed-- kama wewe ni pset darasa kushuka kidogo kwa sababu ya kubuni na whatnot, hiyo ni kikamilifu faini. Ni kupata kwa uhakika ambapo yako programu ni kupata ngumu zaidi. Kuna maeneo zaidi unaweza kuboresha. Hivyo ni kawaida kabisa. Siyo kwamba wewe ni kufanya mbaya zaidi juu ya pset yako. Ni tu sisi ni kuwa vigumu wewe sasa. Hivyo kila mtu ni hisia yake. Mimi tu graded psets yako yote. Najua kila mtu ni hisia yake. Hivyo si kuwa na wasiwasi juu ya hilo. Na kama una maswali yoyote kuhusu psets kabla au njia unaweza kuboresha, Mimi kujaribu na kutoa maoni maalum maeneo, lakini wakati mwingine ni marehemu na mimi kupata kuchoka. Je, kuna mambo mengine yoyote kuhusu data miundo? Mimi nina uhakika wewe guys si kweli wanataka kuzungumza kuhusu wao tena, lakini kama kuna, mimi nina furaha kwenda juu yao, kama vile kitu chochote kutoka hotuba ya zamani hii wiki au wiki iliyopita. Najua wiki iliyopita alikuwa mapitio wote, hivyo sisi inaweza kuwa skipped juu ya baadhi ya mapitio kutoka mihadhara. Maswali mengine yoyote naweza kujibu? OK, haki ya wote. Naam, wewe guys kupata nje ya dakika 15 mapema. Natumaini hii ilikuwa nusu kusaidia angalau, na mimi kuona wewe guys wiki ijayo, au Alhamisi ofisi masaa. Je, kuna maombi kwa vitafunio kwa wiki ijayo, ni jambo? Kwa sababu mimi alisahau pipi leo. Na mimi kuletwa pipi mwisho wiki, lakini ilikuwa Columbus Day, hivyo kulikuwa na kama watu sita ambao alikuwa mifuko minne ya pipi kwa wenyewe. Mimi inaweza kuleta Starbursts tena kama wewe kama. Starbursts? OK, sauti nzuri. Kuwa na siku kubwa, guys.