SPIKA 1: zote haki, hivyo sisi ni nyuma. Karibu CS50. Hii ni mwisho wa wiki saba. Hivyo kukumbuka kuwa wakati wa mwisho, sisi ilianza kuangalia kidogo kisasa zaidi data miundo. Tangu hadi sasa, wote tulikuwa kweli ovyo yetu ilikuwa hii safu. Lakini kabla ya sisi kuondokana na safu kama si yote ya kuvutia, ambayo kwa kweli ni kweli ni, ni nini baadhi ya pluses ya data hii rahisi muundo wa hivi sasa? Nini ni nzuri? Hadi sasa kama tumeona? Je, unayo? Chochote. MWANAFUNZI: [inaudible]. SPIKA 1: Ni nini hiyo? MWANAFUNZI: [inaudible]. SPIKA 1: zisizohamishika kawaida. OK, hivyo kwa nini ni kawaida fasta nzuri ingawa? MWANAFUNZI: [inaudible]. SPIKA 1: OK, hivyo ni ufanisi katika maana ya kwamba unaweza kutenga fasta kiasi cha nafasi, ambayo hopefully hasa ni kama vile nafasi kama unataka. Hivyo kwamba inaweza kuwa ni pamoja na kabisa. Nini upande mwingine juu ya safu? Yeah? MWANAFUNZI: [inaudible]. SPIKA 1: zote - sorry? MWANAFUNZI: [inaudible]. SPIKA 1: masanduku wote katika kumbukumbu au karibu na kila mmoja. Na kwamba ni manufaa - kwa nini? Hiyo ni kweli kabisa. Lakini jinsi gani tunaweza kutumia kwamba kweli? MWANAFUNZI: [inaudible]. SPIKA 1: Hasa, tunaweza kuweka wimbo wa ambapo kila kitu ni tu kwa kujua moja ya anwani, yaani anuani ya kwanza Byte ya kwamba chunk ya kumbukumbu. Au katika kesi ya kamba, anwani ya kwanza Char katika kamba hiyo. Na kutoka huko, tunaweza kupata mwisho wa kamba. Tunaweza kupata kipengele cha pili, ya tatu kipengele, na kadhalika. Na hivyo njia ya kuelezea dhana kwamba kipengele ni kwamba arrays kutupatia random kupata. Tu kwa kutumia mabano mraba nukuu na simu, unaweza kuruka kwa kipengele maalum katika safu katika muda wa mara kwa mara, kubwa O mmoja, hivyo kusema. Lakini kuna kuwa baadhi downsides. Nini safu si kufanya sana kwa urahisi? Nini ni si nzuri wakati? MWANAFUNZI: [inaudible]. SPIKA 1: Ni nini hiyo? MWANAFUNZI: [inaudible]. SPIKA 1: Kupanua katika kawaida. Hivyo downsides wa safu ni just kinyume cha kile upsides ni. Hivyo moja ya downsides ni kwamba ni kawaida fasta. Hivyo unaweza si kweli kukua yake. Unaweza reallocate chunk kubwa ya kumbukumbu, na kisha kuondoka mambo ya zamani katika safu mpya. Na kisha bure safu ya zamani, kwa mfano, kwa kutumia malloc au sawa kazi kuitwa realloc, ambayo reallocates kumbukumbu. Realloc, kama kando, anajaribu kutoa kumbukumbu hiyo ni karibu na safu kwamba wewe tayari. Lakini inaweza hoja mambo karibu kabisa. Lakini katika muda mfupi, hiyo ni ghali, haki? Kwa sababu kama una chunk ya kumbukumbu ya kawaida hii, lakini kweli unataka moja ya kawaida hii, na unataka kuhifadhi mambo ya awali, una takribani linear wakati kuiga mchakato kwamba mahitaji ya kutokea kutoka umri wa safu mpya. Na ukweli ni kuuliza uendeshaji mfumo tena na tena na tena kwa chunks kubwa ya kumbukumbu unaweza kuanza kwa gharama ya baadhi ya muda pia. Hivyo ni baraka na laana katika kujificha, ukweli kwamba haya arrays ni ya ukubwa wa kudumu. Lakini kama sisi kuanzisha badala kitu kama hii, ambayo sisi kuitwa wanaohusishwa orodha, sisi kupata upsides chache na downsides chache hapa pia. Hivyo orodha wanaohusishwa ni tu data muundo alifanya juu ya structs C katika hii kesi, ambapo struct, kukumbuka, ni tu chombo kwa moja au zaidi maalum aina ya vigezo. Katika kesi hiyo, je, aina ya data kuonekana kuwa ndani ya struct kwamba Mara ya mwisho sisi kuitwa nodi? Kila moja ya hizi ni mistatili nodi. Na kila moja ya mistatili ndogo ndani yake ni aina ya data. Ni aina gani gani sisi kusema walikuwa Jumatatu? Yeah? MWANAFUNZI: [inaudible]. SPIKA 1: kutofautiana na pointer, au hasa zaidi, int, kwa n, na pointer chini. Wote wa wale kutokea kwa kuwa 32 bits, saa angalau kwenye kompyuta kama hii CS50 Appliance, na hivyo ni inayotolewa kwa usawa katika kawaida. Hivyo kile ni kutumia pointer ingawa kwa inaonekana? Kwa nini kuongeza hii mshale sasa wakati arrays walikuwa hivyo nzuri na safi na rahisi? Kile ni pointer kufanya kwa ajili ya sisi katika kila aina ya nodes haya? MWANAFUNZI: [inaudible]. SPIKA 1: Hasa. Ni nawaambia ambapo moja ijayo. Hivyo mimi aina ya kutumia mfano wa kutumia thread ya aina ya thread nodes haya pamoja. Na kwamba ni nini hasa sisi ni kufanya na kuyatumia kwa sababu kila moja ya haya chunks ya kumbukumbu au anaweza kuwa na contiguous, nyuma kwa nyuma kwa nyuma ndani ya RAM, kwa sababu kila wakati kuwaita malloc akisema, nipe kutosha ka kwa nodi mpya, nguvu kuwa hapa au inaweza kuwa hapa. Inaweza kuwa ni hapa. Inaweza kuwa ni hapa. Wewe tu sijui. Lakini kwa kutumia kuyatumia katika anwani ya wale nodes, unaweza kuyashona pamoja katika njia kwamba inaonekana kuibua kama orodha hata kama mambo haya ni ya wote kuenea nje katika moja au mbili yako au yako gigabytes minne ya RAM ndani ya kompyuta yako mwenyewe. Hivyo upande wa chini, basi, ya orodha wanaohusishwa ni nini? Nini bei tuko inaonekana kulipa? MWANAFUNZI: [inaudible]. SPIKA 1: Zaidi nafasi, haki? Tumekuwa, katika kesi hii, mara mbili ya kiasi wa nafasi kwa sababu tumeenda kutoka 32 bits kwa kila node, kwa kila int, hivyo sasa bits 64 kwa sababu tuna kuweka karibu pointer pia. Kupata ufanisi zaidi kama struct yako ni kubwa kuliko jambo hili rahisi. Kama wewe kweli kuwa mwanafunzi wa ndani ambayo ni ya wanandoa wa masharti kwa jina na nyumba, labda idadi ID, labda baadhi ya maeneo mengine kabisa. Hivyo kama una kubwa ya kutosha struct, basi labda gharama ya pointer ni si kama mpango kubwa. Hii ni kidogo ya kona katika kesi kwamba sisi ni kuhifadhi primitive vile rahisi ndani ya orodha wanaohusishwa. Lakini uhakika ni sawa. Wewe ni dhahiri kutumia zaidi kumbukumbu, lakini wewe ni kupata kubadilika. Kwa sababu sasa kama nataka kuongeza kipengele katika mwanzo wa orodha hii, Nina kutenga nodi mpya. Na mimi tu update wale mishale na kwa namna fulani tu kusonga baadhi ya kuyatumia kote. Kama nataka kuingiza kitu katika katikati ya orodha, mimi hawana kushinikiza kila mtu kando kama tulivyofanya katika kipindi cha wiki na kujitolea wetu ambao kuwakilishwa safu. Naweza tu kutenga nodi mpya na basi tu kumweka mishale katika tofauti maelekezo kwa sababu haina kubaki katika halisi kumbukumbu mstari wa kweli kama nimekuwa inayotolewa hapa kwenye screen. Na kisha mwisho, kama unataka kuingiza kitu mwisho wa orodha, ni hata rahisi. Hii ni aina ya nukuu holela, lakini pointer 34 wa, kuchukua nadhani. Nini thamani ya pointer wake wengi uwezekano inayotolewa aina ya kama miaka shule antenna huko? MWANAFUNZI: [inaudible]. SPIKA 1: Ni pengine null. Na kwa kweli kwamba ni moja ya mwandishi uwakilishi wa null. Na ni kwa sababu wewe kabisa null haja ya kujua ambapo mwisho wa wanaohusishwa orodha ni, usije kushika zifuatazo na kufuatia na kufuatia mishale hizi kwa baadhi ya thamani ya takataka. Hivyo itakuwa null yanamaanisha kwamba hakuna zaidi nodes na haki ya idadi ya 34, katika kesi hii. Hivyo sisi kupendekeza kwamba tunaweza kutekeleza hii nodi katika kanuni. Na tumeona aina hii ya syntax kabla. Typedef tu amefafanua aina mpya kwa ajili ya nasi, inatupa kisawe kama kamba ilikuwa kwa ajili ya * Char. Katika kesi hiyo, ni kwenda kutupa shorthand nukuu ili struct nodi unaweza badala tu kuandikwa kama nodi, ambayo ni safi sana. Ni mengi chini verbose. Ndani ya nodi ni inaonekana int kuitwa n, na kisha nodi struct * ambayo ina maana hasa nini sisi alitaka mishale ya maana, pointer mwingine nodi ya aina exact data. Na napendekeza kwamba tunaweza kutekeleza tafuta kazi kama hii, ambayo kwa mtazamo wa kwanza inaweza kuonekana tata kidogo. Lakini hebu angalia katika mantiki yake. Nivuke kwa appliance hapa. Napenda kufungua faili inayoitwa orodha ya sifuri nukta h. Na kwamba tu ina maana sisi tu kuona wakati iliyopita kwa ajili ya data hii aina kuitwa nodi. Hivyo tumekuwa kuweka kwamba katika faili dot h. Na kama kando, hata ingawa hii mpango kwamba wewe ni juu ya kuona ni si tata kwamba wote, ni kweli mkataba wakati wa kuandika mpango wa kuweka mambo kama aina ya data, kuvuta constants wakati mwingine, ndani ya yako header faili na si lazima katika yako C faili, hakika wakati wako mipango ya kupata kubwa na kubwa, hivyo kwamba unajua ambapo wote kuangalia kwa nyaraka katika baadhi ya kesi, au kwa misingi kama hii, ufafanuzi wa aina fulani. Kama mimi sasa kufungua orodha ya sifuri nukta c, taarifa mambo machache. Ni pamoja na header files wachache, wengi ambayo tumekuwa kuona mbele. Ni pamoja na kichwa yake mwenyewe faili. Na kama kando, kwa nini hiyo ni mara mbili quotes hapa, kinyume na angle mabano kwenye mstari kwamba Nimekuwa yalionyesha huko? MWANAFUNZI: [inaudible]. SPIKA 1: Yeah hivyo ni faili za mitaa. Hivyo kama ni faili za mitaa yako mwenyewe hapa kwenye mstari wa 15, kwa mfano, unaweza kutumia quotes mbili badala ya mabano angled. Sasa hii ni aina ya kuvutia. Taarifa kwamba nimepata alitangaza kimataifa kutofautiana katika mpango huu juu ya mstari wa 18 iitwayo ya kwanza, wazo kuwa hii ni kwenda kuwa pointer kwanza nodi katika orodha yangu wanaohusishwa, na nimekuwa initialized ni null, kwa sababu nimekuwa si zilizotengwa yoyote halisi nodes bado tu. Hivyo hii inawakilisha, pictorially, nini sisi aliona wakati iliyopita katika picha kama kwamba pointer juu mbali mkono wa kushoto upande. Hivyo sasa hivi, kwamba pointer hana mshale. Badala yake ni null. Lakini inawakilisha nini itakuwa anuani ya halisi ya kwanza nodi katika orodha hii. Hivyo nimekuwa kutekelezwa ni wa kimataifa kwa sababu, kama utaona, yote hii haina mpango katika maisha ni kutekeleza orodha wanaohusishwa kwa ajili yangu. Sasa mimi nimepata prototypes chache hapa. Mimi aliamua kutekeleza makala kama kufutwa, kuingizwa, kutafuta, na traversal - mwisho kuwa tu kutembea katika orodha, uchapishaji nje mambo yake. Na sasa hapa ni kawaida yangu kuu. Na sisi si kutumia muda sana juu ya hizi tangu hii ni aina ya, hopefully zamani kofia kwa sasa. Mimi nina kwenda kufanya yafuatayo, wakati mtumiaji inashirikiana. Hivyo moja, mimi nina kwenda magazeti nje orodha hii. Na nimekuwa formatted kama cleanly kama mimi naweza. Kama mtumiaji aina katika moja, ina maana kwamba wanataka kufuta kitu. Kama mtumiaji aina mbili, kwamba maana ya wanataka kuingiza kitu. Na kadhalika. Mimi nina kwenda kisha kuchochea kisha kwa ajili ya amri. Na kisha mimi naenda kutumia GetInt. Hivyo hii ni kweli rahisi menuing interface ambapo wewe tu kuwa na aina ramani ya simu kwa moja ya wale amri. Na sasa nina nzuri safi kubadili Kauli hiyo ni kwenda kubadili juu chochote mtumiaji typed in Na kama wao typed moja, mimi itabidi kuwaita kufuta na kuvunja. Kama wao typed mbili, mimi itabidi kuwaita kuingiza na kuvunja. Na sasa taarifa nimekuwa kuweka kila ya haya juu ya mstari huo. Hii ni uamuzi Stylistic. Kawaida tumeona kitu kama hii. Lakini mimi tu aliamua, kusema ukweli, mpango wangu inaonekana zaidi someka kwa sababu ilikuwa ni nne tu kesi tu orodha ni kama hii. Kabisa halali matumizi ya mtindo. Na mimi naenda kufanya hii ya muda mrefu kama mtumiaji hana typed sifuri, ambayo mimi aliamua itakuwa na maana wanataka kujiondoa. Hivyo sasa taarifa ya nini mimi nina kwenda kufanya hapa. Mimi nina kwenda huru orodha inaonekana. Lakini zaidi juu ya kwamba katika muda tu. Hebu kwanza kuendesha mpango huu. Hivyo basi mimi kufanya terminal kubwa dirisha, dot kufyeka orodha 0. Mimi nina kwenda mbele na kuingiza na kuandika mbili, idadi kama 50, na sasa utaona orodha sasa ni 50. Na maandishi yangu tu scrolled juu kidogo. Hivyo sasa taarifa orodha ina simu 50. Hebu kufanya mwingine Insert kwa kuchukua mbili. Hebu aina katika idadi kama mmoja. Orodha ya sasa ni moja, ikifuatiwa na 50. Hivyo hii ni tu uwakilishi textual ya orodha. Na hebu kuingiza moja zaidi ya simu kama namba 42, ambayo ni hopefully kwenda kuishia katikati, kwa sababu programu hii katika aina fulani ni mambo kama kuwekeza yao. Hivyo kuna sisi kuwa nayo. Super rahisi mpango kwamba angeweza kabisa wametumia safu, lakini mimi kutokea kwa kutumia orodha wanaohusishwa hivyo tu naweza dynamically kukua na kuogopa hilo. Hivyo hebu tuangalie kwa ajili ya utafutaji, kama mimi kukimbia amri tatu, nataka kutafuta kwa kusema, simu 43. Na hakuna kitu ilikuwa inaonekana kupatikana, kwa sababu mimi got nyuma hakuna majibu. Basi hebu kufanya hii tena. Kutafuta. Hebu tafuta kwa ajili ya 50, au tuseme kutafuta kwa ajili ya 42, ambayo ina nice kidogo hila maana. Na nimeona maana ya maisha huko. Namba 42, kama hamjui kumbukumbu, Google yake. Wote haki. Hivyo kile ina mpango huu kufanyika kwa ajili yangu? Ni tu kuruhusiwa mimi kuingiza hivyo mbali na kutafuta kwa ajili ya mambo. Hebu haraka mbele, basi, kwa kwamba kazi ya sisi akapiga saa Jumatatu kama kichocheo. Hivyo kazi hii, mimi kudai, utafutaji kwa ajili ya kipengele katika orodha ya kwanza na moja, na kusababisha mtumiaji na basi wito GetInt kupata int halisi kwamba unataka kutafuta. Basi taarifa hii. Mimi nina kwenda kujenga variable muda katika mstari 188 kuitwa pointer - PTR - ingeweza kuitwa ni kitu chochote. Na ni pointer nodi kwa sababu nalisema nodi * huko. Na mimi nina initializing kuwa ni sawa na kwanza ili mimi na ufanisi wangu kidole, hivyo kusema, juu sana kwanza kipengele cha orodha. Hivyo kama mkono wangu wa kulia hapa ni PTR mimi nina akionyesha kitu kimoja kwamba kwanza ananyoosha katika. Hivyo sasa nyuma katika kanuni, kile kinachotokea ijayo - hii ni dhana ya kawaida wakati iterating juu ya muundo kama wanaohusishwa orodha. Mimi nina kwenda kufanya yafuatayo wakati pointer si sawa na null Hivyo wakati kidole yangu si akionyesha null baadhi thamani, kama pointer mshale n sawa n. Tutaweza taarifa ya kwanza kwamba n ni nini mtumiaji typed katika GetInts kwa kuwaita hapa. Na pointer mshale n maana yake nini? Vizuri kama sisi kwenda nyuma ya picha hapa, kama nina kidole akionyesha kwamba nodi kwanza zenye tisa, mshale kimsingi ina maana kwamba kwenda nodi na kunyakua thamani katika eneo n, katika kesi hii, shamba data kuitwa n. Kama kando - na tuliona hii michache ya wiki iliyopita wakati mtu aliuliza - syntax hii ni mpya, lakini haina kutupatia nguvu kwamba sisi hakuwa tayari. Nini ilikuwa hii maneno sawa na kutumia nukta nukuu na nyota wanandoa ya wiki iliyopita wakati sisi peeled nyuma safu hii mapema kidogo? MWANAFUNZI: [inaudible]. SPIKA 1: Hasa, ilikuwa ni nyota, na basi ni nyota dot n, na mabano hapa, ambayo inaonekana, kusema ukweli, nadhani mengi zaidi fumbo kusoma. Lakini nyota pointer, kama siku zote, njia kwenda huko. Na mara moja uko huko, kile data shamba unataka kupata? Vizuri kutumia nukuu dot kupata structs shamba data, na mimi hasa wanataka n. Kusema ukweli, napenda wanasema hii ni vigumu kusoma. Ni vigumu kukumbuka ambapo wala mabano kwenda, nyota na wote ya kwamba. Hivyo dunia iliyopitishwa baadhi ya kisintaksia sukari, hivyo kusema. Njia tu sexy ya kusema, hii ni sawa, na labda zaidi Intuitive. Kama pointer ni kweli pointer, mshale nukuu njia kwenda huko na kupata shamba katika kesi hii inaitwa n. Hivyo kama mimi kupata hiyo, taarifa ya nini mimi kufanya. Mimi tu magazeti nje, nimeona asilimia i, plugging katika thamani kwa int kwamba. Mimi wito kulala kwa moja ya pili tu ya aina mambo ya pause kwenye screen kutoa user pili wa kunyonya kile tu kilichotokea. Na kisha mimi kuvunja. Vinginevyo, nini mimi? Mimi update pointer sawa pointer mshale ijayo. Hivyo tu kuwa wazi, hii ina maana kwenda huko, kutumia yangu zamani shule nukuu. Hivyo hii ina maana tu ya kwenda chochote wewe ni akionyesha, ambayo kwa sana kesi ya kwanza ni mimi nina akionyesha struct na tisa katika hilo. Hivyo nimekuwa amekwenda huko. Na kisha nukuu dot maana yake, kupata thamani saa ijayo. Lakini thamani, hata kama ni inayotolewa kama nyembamba, ni idadi tu. Ni anuani nambari. Hivyo hii line moja ya kanuni, kama imeandikwa kama hii, zaidi fumbo njia, au kama hii, kidogo zaidi njia angavu, tu ina maana hoja mkono wangu na nodi ya kwanza kwa moja ijayo, na kisha moja ijayo, na kisha ijayo mmoja, na kadhalika. Hivyo sisi si kukaa juu ya nyingine utekelezaji wa kuingiza na kufuta na traversal, wawili wa kwanza wa ambayo ni haki ya kushiriki. Na nadhani ni rahisi kabisa ya kupata waliopotea wakati wa kufanya hivyo kwa maneno. Lakini nini tunaweza kufanya hapa ni kujaribu kuamua jinsi bora kufanya hivyo kuibua. Kwa sababu napenda kupendekeza kwamba kama sisi wanataka kuingiza mambo ya ndani ya hii zilizopo orodha, ambayo ina mambo tano - 9, 17, 22, 26, na 33 - kama mimi walikuwa kwenda kutekeleza hili katika kanuni, mimi haja ya kufikiria jinsi ya kwenda juu ya kufanya hii. Na napenda kupendekeza kuchukua hatua mtoto ambapo, katika kesi hii I mean, ni nini matukio inawezekana kwamba sisi anaweza kukutana kwa ujumla? Wakati utekelezaji Insert kwa wanaohusishwa orodha, hii hutokea tu kuwa maalum mfano wa ukubwa tano. Vizuri kama unataka kuingiza idadi, kama kusema namba moja, na kudumisha yamepangwa ili, ambapo wazi haina namba moja wanahitaji kwenda katika mfano huu maalum? Kama mwanzoni. Lakini nini kuvutia kuna ni kwamba kama unataka kuingiza moja katika hili orodha, nini pointer maalum mahitaji ya kuwa updated inaonekana? Kwanza. Hivyo napenda kusema, hii ni kesi ya kwanza kwamba sisi kutaka kufikiria, mazingira ya kuwashirikisha kuingiza katika mwanzo wa orodha. Hebu konoa labda kama rahisi au hata rahisi kesi, kiasi kuzungumza. Tuseme nataka kuingiza namba 35 ili Iliyopangwa. Ni wazi ni mali ya zaidi ya hapo. Hivyo kile pointer wazi ni kwenda kuwa updated katika hali hiyo? Pointer 34 ya kuwa si null lakini anwani ya struct zenye namba 35. Hivyo kwamba ni kesi mbili. Hivyo tayari, mimi nina aina ya quantizing kiasi gani kazi mimi kufanya hapa. Na hatimaye, wazi katikati kesi ni kweli kweli, katikati, kama nataka kuingiza kitu kama kusema 23, kwamba huenda kati ya 23 na 26, lakini sasa mambo kupata zaidi kidogo kushiriki kwa sababu gani kuyatumia haja ya kuwa iliyopita? Hivyo ni wazi 22 inahitaji kubadilishwa kwa sababu hawezi uhakika na 26 tena. Yeye mahitaji kwa uhakika na node mpya ambayo Mimi itabidi kutenga kwa kumwita malloc au baadhi ya sawa. Lakini basi mimi pia haja ya kuwa nodi mpya, 23 katika kesi hii, kuwa na pointer yake akionyesha nani? 26. Na kuna kwenda kuwa utaratibu wa shughuli hapa. Kwa sababu kama mimi kufanya hivyo kwa ujinga, na mimi kwa mfano kuanza mwanzoni mwa orodha, na lengo langu ni kuingiza 23. Na mimi kuangalia, je, ni mali ya hapa karibu tisa? No Je, ni mali ya hapa, karibu na 17? No Je, ni mali hapa karibu na 22? Ndiyo. Sasa kama mimi nina wajinga hapa, na si kufikiri hili kwa njia ya, mimi ili kutenga nodi wangu mpya kwa 23. Nipate update pointer kutoka nodi kuitwa 22, akizungumzia ni kwenye nodi mpya. Na kisha nini nina update pointer nodi mpya ya kuwa? MWANAFUNZI: [inaudible]. SPIKA 1: Hasa. Akionyesha 26. Lakini Dammit kama sikuwa tayari update Pointer 22 wa uhakika katika guy hii, na sasa mimi na yatima, wengine ya orodha, hivyo kusema. Hivyo utaratibu wa shughuli hapa ni kwenda kuwa muhimu. Kufanya hii inaweza mimi kuiba, kusema, watu sita. Na hebu angalia kama hatuwezi kufanya hii kuibua badala ya kanuni ya-busara. Na tuna baadhi ya dhiki lovely mipira kwa leo. OK, vipi kuhusu moja, mbili, katika nyuma - tarehe ya mwisho huko. tatu, nne, wote wewe guys juu ya mwisho. Na tano, sita. Uhakika. Tano na sita. Yote ya haki na tutaweza kuja kwa nyie wakati ujao. Haki wote, kuja juu juu. Haki zote, tangu uko hapa juu ya kwanza, ungependa kuwa mmoja awkwardly katika kioo Google hapa? Haki ya wote, hivyo, OK, kioo, kurekodi video. OK, wewe ni vizuri kwenda. Haki wote, hivyo kama wewe guys unaweza kuja juu hapa, mimi tayari mapema baadhi ya namba. Haki wote, kuja juu zaidi ya hapa. Na kwa nini wewe kwenda kidogo zaidi kwamba njia. Na hebu angalia, nini jina lako, na kioo Google? MWANAFUNZI: Ben. SPIKA 1: Ben? OK, Ben, utakuwa wa kwanza, literally. Hivyo sisi ni kwenda kukutumia hadi mwisho wa hatua. Haki ya wote, na jina lako? MWANAFUNZI: Jason. SPIKA 1: Yasoni, OK utasikia kuwa idadi tisa. Hivyo kama unataka kufuata Ben njia hiyo. MWANAFUNZI: Jill. SPIKA 1: Jill, wewe ni kwenda kuwa 17, ambayo kama ningependa jambo hili zaidi akili, mimi ingekuwa ilianza saa nyingine ya mwisho. Kwenda njia hiyo. 22. Na wewe ni? MWANAFUNZI: Maria. SPIKA 1: Maria, wewe utakuwa na 22. Na jina lako ni nani? MWANAFUNZI: Chris. SPIKA 1: Chris, wewe utakuwa na 26. Na kisha mwishowe. MWANAFUNZI: Diana. SPIKA 1: Diana, wewe utakuwa na 34. Hivyo kuja juu zaidi ya hapa. Haki ya wote, hivyo kukamilisha sorted kuamuru tayari. Na hebu kwenda mbele na kufanya hii ili tuweze kweli - Ben wewe ni aina tu ya kuangalia nje katika mahali pa huko. OK, hivyo hebu kwenda mbele na depict hii kutumia silaha, kiasi kama mimi nilikuwa, hasa, nini kinaendelea. Hivyo kwenda mbele na kutoa nafsi zenu mguu au mbili kati yenu. Na kwenda mbele na uhakika na mmoja mkono kwa anaye wewe lazima akionyesha msingi huu. Na kama wewe ni null tu kumweka moja kwa moja chini ya sakafu. OK, hivyo nzuri. Basi sasa tuna orodha wanaohusishwa, na napenda kupendekeza kwamba mimi itabidi kucheza nafasi ya PTR, hivyo mimi si bother kubeba hii kote. Na kisha - mtu kijinga mkataba - unaweza kuita hii kitu chochote unataka - mtangulizi pointer, pred pointer - ni tu jina la utani sisi alitoa katika sampuli zetu kanuni na mkono wangu wa kushoto. upande mwingine kwamba kwenda na kuweka wimbo wa nani ni nani katika kufuatia matukio. Hivyo tuseme, kwanza, nataka konoa kwamba mfano wa kwanza wa kuingiza, kusema 20, katika orodha. Hivyo nina kwenda haja ya mtu uliopo namba 20 kwa ajili yetu. Hivyo mimi haja ya mtu malloc kutoka kwa watazamaji. Kuja juu juu. Nini jina lako? MWANAFUNZI: Brian. SPIKA 1: Brian, haki ya wote, hivyo atakuwa nodi zenye 20. Haki wote, kuja juu zaidi ya hapa. Na ni wazi, ambapo haina Brian ni mali? Hivyo, katikati ya - kweli, kusubiri dakika. Sisi ni kufanya hii nje ya utaratibu. Sisi ni kufanya hii vigumu sana kuliko mahitaji kwa kuwa saa ya kwanza. OK, tunakwenda bure Brian na realloc Brian kama tano. OK, hivyo sasa tunataka kuingiza Brian kama tano. Hivyo kuja juu juu hapa karibu na Ben kwa muda tu. Na unaweza kuwaambia labda ambapo hadithi hii ni kwenda. Lakini hebu kufikiri kwa makini kuhusu utaratibu wa shughuli. Na ni just hii Visual hiyo ni kwenda kujipanga na kwamba kanuni ya sampuli. Hivyo hapa mimi PTR akizungumzia awali si wakati Ben, per se, lakini katika kila thamani yeye ina, ambayo katika kesi hii ni - nini jina lako tena? MWANAFUNZI: Jason. SPIKA 1: Jason, hivyo wote Ben na mimi ni akionyesha Jason katika wakati huu. Hivyo sasa mimi na kuamua, ambapo gani Brian ni mali? Hivyo kitu pekee mimi kupata sasa hivi ni yake n data bidhaa. Hivyo nina kwenda kuangalia, ni Brian chini ya Jason? Jibu ni kweli. Basi nini sasa mahitaji ya kutokea, katika mpangilio sahihi? Mimi haja ya update kuyatumia jinsi wengi kwa jumla katika hadithi hii? Ambapo mkono wangu bado ni akionyesha Yasoni, na mkono wako - kama unataka kuweka mkono wako kama, aina ya, mimi sijui, alama ya swali. OK, nzuri. Haki ya wote, hivyo kuwa wagombea wachache. Ama Ben au mimi au Brian au Jason au kila mtu mwingine, ambayo kuyatumia haja ya mabadiliko? Wangapi katika jumla? OK, hivyo mbili. Pointer yangu kweli haina jambo tena kwa sababu mimi nina tu ya muda mfupi. Hivyo ni haya guys mbili, labda, wote Ben na Brian. Hivyo basi mimi kupendekeza kwamba sisi update Ben, tangu yeye kwanza. kipengele kwanza ya orodha hii sasa ni kwenda kuwa Brian. Hivyo Ben mchemko ifikapo Brian. OK, sasa nini? Ambaye anapata alisema saa nani? MWANAFUNZI: [inaudible]. SPIKA 1: OK hivyo Brian ana kwa uhakika katika Jason. Lakini mimi waliopotea track ya pointer kwamba? Sijui ambapo Jason ni? MWANAFUNZI: [inaudible]. SPIKA 1: mimi kufanya, tangu mimi nina pointer ya muda mfupi. Na labda, mimi si iliyopita kwa kumweka kwenye nodi mpya. Hivyo tunaweza tu na Brian hatua saa yeyote nina akionyesha. Na sisi ni kosa. Hivyo kesi moja, kuingizwa katika mwanzo wa orodha. Kulikuwa hatua mbili muhimu. Moja, tuna update Ben, na kisha sisi pia kuwa na update Brian. Na kisha mimi hawana bother traipsing njia ya mapumziko ya orodha, kwa sababu sisi tayari kupatikana yake mahali, kwa sababu yeye ni mali ya kushoto wa kipengele kwanza. Haki ya wote, hivyo pretty moja kwa moja. Kwa kweli, anahisi kama tuko karibu kufanya hii ngumu sana. Basi hebu sasa konoa mwisho ya orodha, na kuona ambapo utata kuanza. Hivyo kama sasa, mimi alloc kutoka kwa watazamaji. Mtu yeyote unataka kucheza 55? Haki zote, niliona mkono wako wa kwanza. Kuja juu juu. Yeah. Nini jina lako? MWANAFUNZI: [inaudible]. SPIKA 1: Habata. OK, kuja juu juu. Wewe utakuwa na simu 55. Hivyo, bila shaka, ni mali mwisho wa orodha. Basi hebu Replay simulation na mimi kuwa PTR kwa muda tu. Hivyo nina uhakika kwanza kwenda katika chochote Ben ni akionyesha. Tuko wote akizungumzia sasa saa Brian. Hivyo 55 ni si chini ya watano. Hivyo nina kwenda kwa update mwenyewe kwa akizungumzia pointer Brian ijayo, ambao sasa ni mwendo wa Jason. 55 ni si chini ya tisa, hivyo Mimi nina kwenda update PTR. Mimi nina kwenda update PTR. Mimi nina kwenda update PTR Mimi kwenda update PTR. Na mimi naenda - hmm, nini jina yako tena? MWANAFUNZI: Diana. SPIKA 1: Diana ni akizungumzia, bila shaka, saa null kwa mkono wake wa kushoto. Hivyo ambapo gani Habata kweli ni wazi? Kwa upande wa kushoto, hapa. Hivyo ni jinsi gani mimi kujua kuweka wake Hapa Nadhani nimepata Star up. Kwa sababu ni nini PTR sanaa huu katika muda? Null. Hivyo hata kama, kuibua, tunaweza wazi kuona yote haya guys hapa juu ya hatua. Nimekuwa si naendelea wimbo wa uliopita mtu katika orodha. Sina kidole kuonyesha nje, katika kesi hii, idadi nodi 34. Basi hebu kweli kuanza hii zaidi. Hivyo sasa mimi kwa kweli kufanya haja pili mitaa kutofautiana. Na hii ni nini utaona katika halisi sampuli C kanuni, ambapo kama mimi kwenda, wakati mimi update mkono wangu wa kulia kwa uhakika Jason, na hivyo kuacha Brian nyuma, mimi bora kuanza kutumia mkono wangu wa kushoto kwa update ambapo nilikuwa, ili kama mimi kwenda kupitia orodha hii - zaidi kuliko mimi nia awkwardly sasa hapa kuibua - Mimi nina kwenda kupata mwisho wa orodha. Mkono hii bado ni null, ambayo ni pretty haina maana, zaidi ya kuonyesha Mimi nina wazi mwisho wa orodha, lakini sasa angalau nina hii mtangulizi pointer akizungumzia hapa, hivyo sasa nini mikono na nini kuyatumia haja kuwa updated? Ambaye mkono unataka reconfigure kwanza? MWANAFUNZI: [inaudible]. SPIKA 1: OK, hivyo Diana. Ambapo unataka uhakika Diana kushoto pointer saa? Saa 55, labda, ili kwamba tumekuwa kuingizwa huko. Na ambapo wanapaswa 55 pointer kwenda? Chini, anayewakilisha null. Na mikono yangu, katika hatua hii, wala jambo kwa sababu walikuwa tu muda vigezo. Hivyo sasa sisi ni kosa. Hivyo utata ziada hapo - na siyo kwamba ni vigumu kutekeleza, lakini tunahitaji kutofautiana sekondari ya kufanya uhakika kwamba kabla mimi hoja haki yangu mkono, mimi update thamani ya kushoto yangu mkono, pred pointer katika kesi hii, hivyo kwamba nina pointer trailing kuweka wimbo wa wapi nilipo. Sasa kama kando, kama wewe ni kufikiri hii kupitia, hii anahisi kama ni kidogo annoying kuwa na kuweka wimbo wa mkono huo wa kushoto. Gani ufumbuzi mwingine wa tatizo hili wamekuwa? Kama got wa kuunda upya data muundo tunazungumzia kupitia hivi sasa? Kama aina hii tu ya anahisi kidogo annoying kuwa, kama, mbili kuyatumia kwenda kupitia orodha, nani mwingine anaweza kuwa, katika ulimwengu halisi, iimarishwe habari kwamba tunahitaji? Yeah? MWANAFUNZI: [inaudible]. SPIKA 1: Hasa. Haki hivyo kuna kweli ya kuvutia kijidudu ya wazo. Na hili wazo la pointer uliopita, akionyesha kipengele uliopita. Nini kama mimi tu ilivyo kwamba ndani ya orodha yenyewe? Na ni kwenda kuwa ngumu kwa taswira huu bila ya karatasi kila kuanguka kwa sakafu. Lakini tuseme kwamba hawa guys kutumika wote ya mikono yao ya kuwa uliopita pointer, na pointer ijayo, na hivyo kutekeleza kile Tutamwita doubly wanaohusishwa orodha. Hiyo naomba aina ya rewind, kwa urahisi zaidi bila mimi, programu, baada ya kuweka kufuatilia manually - kweli manually - ya ambapo mimi alikuwa hapo awali katika orodha. Hivyo sisi si kufanya hivyo. Tutaweza kushika ni rahisi kwa sababu hiyo ni yatakuja kwa bei, mara mbili kama mengi nafasi kwa ajili ya kuyatumia, kama unataka moja ya pili. Lakini hiyo ni kweli ya kawaida data muundo inajulikana kama doubly wanaohusishwa orodha. Hebu kufanya mfano wa mwisho hapa na kuweka haya guys nje ya taabu yao. Hivyo malloc 20. Kuja juu juu kutoka aisle huko. Haki zote, nini jina lako? MWANAFUNZI: [inaudible]. SPIKA 1: Samahani? MWANAFUNZI: [inaudible]. SPIKA 1: Demeron? OK kuja juu juu. Mtakuwa 20. Wewe ni wazi ni kwenda ni kati ya 17 na 22. Hivyo basi mimi kujifunza somo yangu. Mimi naenda kuanza pointer akionyesha Brian. Na mimi nina kwenda kuwa na mkono wangu wa kushoto tu update kwa Brian kama mimi hoja ya Jason, kuangalia anafanya 20 chini ya tisa? No Ni 20 chini ya 17? No Ni 20 chini ya 22? Ndiyo. Hivyo kile kuyatumia au mikono haja ya kubadili ambapo wao ni akizungumzia sasa? Hivyo tunaweza kufanya 17 akionyesha 20. Hivyo kwamba ni faini. Wapi tunataka uhakika pointer yako sasa? Saa 22. Na tunajua ambapo 22 ni, tena shukrani pointer yangu ya muda mfupi. Hivyo sisi ni OK huko. Hivyo kwa sababu ya hii ya kuhifadhi muda Nimekuwa naendelea wimbo wa ambapo kila mtu ni. Na sasa unaweza kwenda katika kuibua ambapo wewe ni mali, na sasa tunahitaji 1, 2, 3, 4, 5, 6, 7, 8, 9 dhiki mipira, na pande zote ya applause kwa haya guys, kama tunaweza. Nicely kufanyika. [Makofi] SPIKA 1: zote haki. Na unaweza kuweka vipande ya karatasi kama mementos. Haki ya wote, hivyo, imani yangu ni mengi rahisi kutembea kwa njia ya kwamba pamoja na binadamu zaidi ni pamoja na kanuni halisi. Lakini nini utapata katika muda tu sasa, ni kwamba huo - oh, asante. Asante - ni kwamba utapata kwamba data huo muundo, orodha wanaohusishwa, unaweza kweli kutumika kama kuzuia ujenzi na hata zaidi kisasa data miundo. Na kutambua pia mandhari hapa ni kwamba tumekuwa kabisa ilianzisha zaidi utata katika utekelezaji ya algorithm hii. Kuingizwa, na kama sisi akaenda kwa njia hiyo, kufuta na kutafuta, ni kidogo ngumu zaidi kuliko alikuwa pamoja na safu. Lakini sisi kupata baadhi ya mabadiliko. Sisi kupata adaptive data muundo. Lakini tena, sisi kulipa bei ya kuwa na baadhi ya ziada utata, katika kutekeleza hilo. Na sisi ni kupewa upatikanaji random. Na kwa kuwa waaminifu, kuna si baadhi nice safi slide naweza kukupa kwamba anasema hapa ni kwa nini orodha wanaohusishwa ni bora kuliko safu. Na kuondoka saa hiyo. Kwa sababu mandhari reoccurring sasa, hata zaidi ya hivyo katika wiki ijayo, ni kwamba kuna si lazima jibu sahihi. Hii ni kwa nini tuna mhimili tofauti ya kubuni kwa seti tatizo. Itakuwa sana mazingira nyeti kama unataka kutumia data hii muundo au kwamba mmoja, na itakuwa itategemea kile mambo na wewe katika suala wa rasilimali na utata. Lakini basi mimi kupendekeza kwamba data bora muundo, grail takatifu, itakuwa kitu ambacho ni mara kwa mara wakati, bila kujali jinsi mambo mengi ni ndani yake, si ingekuwa ajabu ikiwa data muundo akarudi majibu katika mara kwa mara wakati. Ndiyo. Hii neno ni katika kamusi yako kubwa. Au hakuna, hii si neno. Au tatizo lolote vile huko. Naam hebu angalia kama hatuwezi angalau kuchukua hatua kuelekea hiyo. Basi mimi kupendekeza mpya data muundo kwamba inaweza kutumika kwa ajili ya mambo mbalimbali, katika kesi hii inaitwa meza hash. Na hivyo sisi ni kweli nyuma ya glancing katika safu, katika kesi hii, na kiasi fulani kiholela, nimekuwa inayotolewa hii hash meza kama safu na aina ya mbili-dimensional safu - au tuseme ni taswira ya hapa kama mbili dimensional safu - lakini hii ni safu ya ukubwa 26, vile kwamba kama sisi piga meza safu, meza bracket sifuri ni Mstatili kwa juu. Meza bracket 25 ni mstatili chini. Na hii ni jinsi mimi ili kuteka data muundo ambayo mimi unataka kuhifadhi watu majina. Hivyo kwa mfano, na mimi si kuteka nzima kitu hapa juu ya uendeshaji, kama mimi alikuwa na safu hii, ambayo mimi sasa kwenda piga meza hash, na hii ni tena eneo sifuri. Hii hapa ni mahali mmoja, na kadhalika. Mimi kudai kwamba mimi nataka kutumia data hii muundo, kwa ajili ya majadiliano, kuhifadhi majina ya watu, Alice na Bob na Charlie na majina mengine kama hayo. Hivyo kufikiri ya hii sasa kama mwanzo ya, kusema, kamusi kwa kura ya maneno. Wao kutokea kwa kuwa majina katika mfano wetu hapa. Na hii yote ni pia germane, pengine, kwa kutekeleza kusahihisha Spell, kama sisi ili kwa tatizo kuweka sita. Hivyo kama tuna safu ya kawaida ya jumla 26 hivyo kwamba hii ni mahali 25 chini, na mimi kudai kwamba Alice ni neno la kwanza katika kamusi ya majina ya kwamba mimi nataka kuingiza ndani ya RAM, ndani ya muundo huu data, ambapo ni silika kuwaambia kwamba Alice jina lazima kwenda katika safu hii? Tuna njia 26. Ambapo tunataka kuweka wake? Tunataka yake katika mabano sifuri, haki? kwa Alice, hebu wito kwamba sifuri. Na B itakuwa moja, na C itakuwa mbili. Hivyo sisi ni kwenda kuandika Jina Alice hapa juu. Kama sisi kisha kuingiza Bob, wake jina kwenda hapa. Charlie kwenda hapa. Na kadhalika chini kupitia muundo huu data. Hii ni ajabu data muundo. Kwa nini? Vizuri ni nini wakati mbio ya kuingiza jina binadamu ndani ya hii data muundo hivi sasa? Kutokana na kwamba meza hii ni kutekelezwa, kweli, kama safu. Naam ni mara kwa mara wakati. Ni utaratibu wa moja. Kwa nini? Vizuri jinsi gani unaweza kuamua ambapo Alice ni mali? Ukiangalia ambayo barua ya jina lake? kwanza. Na unaweza kupata huko, kama ni kamba, na kuangalia tu kamba bracket sifuri. Hivyo tabia 0 wa kamba. Hiyo ni rahisi. Sisi gani kwamba katika crypto zoezi wiki iliyopita. Na kisha mara moja, unajua kwamba Alice mbili ni mji mkuu, tunaweza Ondoa mbali ya 65 au mji mkuu yenyewe, ambayo inatupa sifuri. Hivyo sisi sasa tunajua kuwa ni mali ya Alice katika eneo sifuri. Na kupewa pointer data hii muundo, wa aina fulani, jinsi muda gani ni kuchukua yangu ya kupata eneo sifuri katika safu? Hatua moja tu, haki Ni mara kwa mara wakati sababu ya kupata random sisi mapendekezo ilikuwa kipengele wa safu. Hivyo katika muda mfupi, kuhesabia nje nini index jina la Alice ni, ambayo ni, katika kesi hii, ni, au hebu tu kutatua kwamba kwa sifuri, ambapo ni moja B na C ni mbili, kuhesabia kwamba nje ni mara kwa mara wakati. Mimi tu na kuangalia barua yake ya kwanza, kuhesabia ambapo sifuri ni safu pia ni mara kwa mara wakati. Basi kitaalam kwamba kama hatua mbili sasa. Lakini hiyo bado mara kwa mara. Hivyo tunatoa wito kwamba O kubwa ya moja, hivyo tumekuwa Alice kuingizwa katika meza hii katika mara kwa mara wakati. Lakini kwa kweli, mimi nina kuwa naive hapa, sawa? Nini kama kuna Haruni katika darasa? Au Alicia? Au majina mengine ya kuanzia na A. wapi sisi kwenda kuweka kwamba mtu, haki? I mean, hivi sasa kuna tatu tu watu juu ya meza, hivyo labda sisi wanapaswa kuweka Haruni katika eneo sifuri moja mbili tatu. Haki, mimi naweza kuweka hapa. Lakini basi, kama sisi kujaribu kuingiza Daudi katika orodha hii, ambapo gani Daudi kwenda? Sasa mfumo wetu kuanza kuvunja chini, sawa? Kwa sababu sasa Daudi kuishia hapa kama Haruni ni kweli hapa. Na hivyo sasa hii dhana nzima ya kuwa na safi data muundo kwamba inatupa mara kwa mara wakati insertions ni tena mara kwa mara wakati, kwa sababu mimi kuangalia, oh, damnit, mtu tayari ni katika eneo Alice. Hebu kuchunguza wengine wa data hii muundo, kuangalia kwa doa kuweka mtu kama jina la Haruni. Na hivyo kuwa pia ni kuanzia kuchukua muda linear. Aidha, kama wewe sasa unataka kupata Haruni katika muundo huu data, na wewe kuangalia, na jina la Haruni si hapa. Kimsingi, ungekuwa tu kusema Haruni si katika muundo wa data. Lakini kama wewe kufanya kuanza kufanya chumba kwa ajili ya Haruni ambapo kuna lazima wamekuwa D au E, wewe, kesi mbaya, na kuangalia nzima data muundo, katika kesi ambayo ni warithi katika kitu linear katika ukubwa wa meza. Hivyo haki ya wote, mimi itabidi kurekebisha hii. Tatizo hapa ni kwamba nilikuwa 26 vipengele katika safu hii. Hebu mabadiliko hayo. Whoops. Hebu mabadiliko hayo ili badala ya kuwa kawaida 26 kwa jumla, taarifa ya chini index ni kwenda na mabadiliko kwa n bala 1. Kama 26 ni wazi ndogo mno kwa 'binadamu majina, kwa sababu kuna maelfu ya majina ya dunia, hebu tu kufanya katika 100 au 1,000 au 10,000. Hebu tu kutenga mengi zaidi nafasi. Vizuri kwamba siyo lazima kupungua uwezekano kwamba hatutakuwa na mbili watu wenye majina kuanzia na, na hivyo, walikuwa kwenda kujaribu kuweka majina katika sifuri eneo bado. Wao bado uko kwenda yanapogongana, ambayo ina maana bado tunahitaji ufumbuzi wa kuweka Alice na Haruni na Alicia na nyingine majina kuanzia na mahali pengine. Lakini ni kiasi gani cha tatizo ni hii? Nini uwezekano kwamba wewe kuwa na migongano katika data muundo kama hii? Vizuri, basi mimi - tutaweza kurudi kwa swali hapa. Na kuangalia jinsi gani tupate kutatua hilo kwanza. Hebu vuta hadi pendekezo hili hapa. Nini sisi tu ilivyoelezwa ni algorithm, heuristic kuitwa linear uchunguzi ambapo, kama walijaribu kuingiza kitu hapa katika data hii muundo, ambayo inaitwa meza hash, na kuna chumba hakuna huko, kweli kuchunguza muundo wa data kuangalia, ni hii inapatikana? Je, hii ni Available hii inapatikana? Ni hii inapatikana? Na wakati hatimaye ni, wewe kuingiza jina kwamba awali lengo mahali pengine katika eneo hilo. Lakini katika hali mbaya zaidi, doa tu ili kuwa chini kabisa ya data muundo, mwisho wa safu. Hivyo linear uchunguzi, katika hali mbaya zaidi, warithi katika algorithm linear ambapo Haruni, kama yeye hufanyika kuwa na kuingizwa mwisho katika muundo huu data, apate collide na eneo hili kwanza, lakini kisha mwisho kwa bahati mbaya mwishoni sana. Hivyo hii si mara kwa mara wakati takatifu grail kwa ajili yetu. Mbinu hii ya mambo ya ndani ya kuingiza muundo wa data kuitwa hash meza haionekani kuwa mara kwa mara wakati angalau si katika kesi ujumla. Ni wanaweza kukabidhi katika kitu linear. Basi nini kama sisi kutatua migongano kiasi fulani tofauti? Hivyo hapa ni ya kisasa zaidi mbinu nini bado kuitwa meza hash. Na kwa hash, kama kando, nini I mean ni index kwamba Mimi inajulikana mapema. Kwa kitu hash unaweza kuwa mawazo ya kama kitenzi. Hivyo kama wewe Alice hash ni jina, kazi hash, hivyo kusema, wanapaswa kurudi idadi. Katika kesi hii ni sifuri kama yeye ni katika eneo sifuri, moja ikiwa yeye ni saa eneo moja, na kadhalika. Hivyo kazi yangu hash hivi sasa imekuwa super rahisi, tu kuangalia barua ya kwanza kwa jina la mtu. Lakini kazi hash inachukua kama pembejeo baadhi ya kipande cha data, kamba, int, chochote. Na ni mtemi nje kwa kawaida idadi. Na kwamba idadi hiyo ni wapi kwamba data kipengele ni katika muundo wa data inajulikana hapa kama meza hash. Hivyo tu intuitively, hii ni tofauti kidogo mazingira. Hii kweli ni akimaanisha mfano kuwashirikisha siku za kuzaliwa, ambapo huenda kuna wengi kama Siku 31 katika mwezi. Lakini ni nini mtu huyu kuamua kufanya katika tukio la mgongano? Muktadha sasa kuwa, si mgongano wa majina, lakini mgongano wa siku za kuzaliwa, kama watu wawili na kuzaliwa sawa juu ya Oktoba 2, kwa mfano. MWANAFUNZI: [inaudible]. SPIKA 1: Yeah, hivyo hapa tuna leveraging ya orodha wanaohusishwa. Hivyo inaonekana tofauti kidogo kuliko sisi akauchomoa mapema. Lakini sisi kuonekana kuwa na safu upande wa kushoto. Hiyo ni moja index, kwa maana hakuna Hasa sababu. Lakini bado ni safu. Ni safu ya kuyatumia. Na kila moja ya mambo hayo, kila mmoja haya duru au milalo - kufyeka anayewakilisha null - kila moja ya haya kuyatumia ni inaonekana akizungumzia nini data muundo? orodha wanaohusishwa. Hivyo basi, tuna uwezo wa ngumu kificho katika mpango wetu ukubwa wa meza. Katika kesi hiyo, tunajua kuna kamwe zaidi ya siku 31 kwa mwezi. Hivyo ngumu coding thamani kama 31 ni kuridhisha katika mazingira. Katika mazingira ya majina, ngumu coding 26 si ya maana ni watu majina tu kuanza na, kwa mfano, alfabeti kuwashirikisha kupitia Z. Tunaweza cram wote ndani ya data kwamba muundo wa muda mrefu kama, wakati sisi kupata mgongano, hatuwezi kuweka majina hapa, sisi badala kufikiri ya seli hizi si kama masharti wenyewe, lakini kama kuyatumia kwa, kwa mfano, Alice. Na kisha Alice unaweza kuwa mwingine pointer kwa jina la mtu mwingine kwa kuanzia na A. Na Bob kweli inakwenda zaidi ya hapa. Na kama kuna mwingine jina kuanzia na B, yeye mwisho juu zaidi ya hapa. Na hivyo kila mmoja wa mambo ya hii meza mbili, kama sisi iliyoundwa hii zaidi kidogo cleverly - kuja juu - kama sisi iliyoundwa hii zaidi kidogo cleverly, sasa inakuwa data adaptive muundo, ambapo hakuna kikomo kwa bidii juu ya jinsi mambo mengi unaweza kuingiza ndani yake kwa sababu kama una mgongano, hiyo faini. Tu kwenda mbele na append kwa yale tuliona kidogo iliyopita alikuwa inayojulikana kama orodha wanaohusishwa. Naam hebu pause kwa muda tu. Je, ni uwezekano wa mgongano katika nafasi ya kwanza? Haki, labda mimi nina zaidi ya kufikiri, labda Nina zaidi ya uhandisi na tatizo hili, kwa sababu unajua nini? Ndiyo, naweza kuja na holela mifano mbali juu ya kichwa yangu kama Allison na Haruni, lakini katika hali halisi, aliyopewa usambazaji sare ya pembejeo, kwamba ni baadhi ya insertions random katika muundo wa data, kile kwa kweli ni uwezekano wa mgongano? Vizuri zamu nje, ni kweli super juu. Hebu kujumlisha hii Tatizo ni kama hii. Hivyo katika chumba ya n CS50 wanafunzi, nini uwezekano kwamba angalau wanafunzi wawili katika chumba kuwa kuzaliwa sawa? Hivyo kuna nini. Hund wachache - 200, 300 watu hapa na kadhaa mia watu nyumbani leo. Hivyo kama alitaka tujiulize nini uwezekano wa watu wawili katika chumba kuwa siku ya kuzaliwa huo, tunaweza takwimu hii nje. Na mimi kudai kweli kuna mambo mawili watu na kuzaliwa sawa. Kwa mfano, haina mtu yeyote kuwa na siku ya kuzaliwa leo? Jana? Kesho? Haki wote, hivyo ni anahisi kama mimi nina kwenda kwa kuwa kufanya hivyo 363 au hivyo zaidi mara kwa kweli kufikiri kama sisi kufanya kuwa na mgongano. Au sisi inaweza tu kufanya hivyo kihisabati badala ya tediously kufanya hivyo. Na kupendekeza yafuatayo. Hivyo napendekeza kwamba tunaweza kubuni uwezekano wa watu wawili huo siku ya kuzaliwa kama uwezekano wa 1 bala uwezekano wa mtu kuwa na kuzaliwa sawa. Hivyo kupata hii, na hii ni dhana njia ya kuandika hii, kwa mtu wa kwanza katika chumba, yeye au yeye unaweza kuwa na mtu yeyote wa inawezekana kuzaliwa kuchukua siku 365 kwa mwaka, pamoja na msamaha kwa watu wenye Februari 29 siku ya kuzaliwa. Hivyo mtu wa kwanza katika chumba hiki ni bure kuwa na idadi yoyote ya siku za kuzaliwa nje ya uwezekano 365 ili tutaweza kufanya hivyo 365 kugawanywa na 365, ambayo ni moja. mtu wa pili katika chumba, kama lengo ni kuepuka mgongano, unaweza tu kuwa na wake au kuzaliwa kwake juu ya jinsi ya nyingi tofauti inawezekana siku? 364. Hivyo awamu ya pili katika msemo huu ni kimsingi kufanya kwamba math kwa ajili yetu kwa kutoa off moja inawezekana siku. Na kisha siku ya pili, siku ya pili, siku ya pili chini ya idadi ya jumla ya watu katika chumba. Na kama sisi kisha kufikiria, nini basi ni uwezekano si ya kila mtu kuwa kipekee siku za kuzaliwa, lakini tena 1 bala kwamba, nini sisi kupata ni usemi ambayo inaweza sana fancifully kuangalia kama hii. Lakini ni zaidi ya kuvutia kuangalia kuibua. Hii ni chati ambapo kwenye mhimili x-ni idadi ya watu katika chumba, idadi ya siku za kuzaliwa. Kwenye mhimili y-uwezekano wa mgongano, watu wawili baada ya kuzaliwa sawa. Na takeaway kutoka Curve hii ni kwamba haraka kama wewe kupata kama 40 wanafunzi, uko uwezekano hadi saa 90% combinatorically wa mbili watu au zaidi baada ya kuzaliwa sawa. Na mara moja kupata kama watu 58 ni karibu asilimia 100% ya nafasi mbili watu katika chumba ni kwenda na kuzaliwa sawa, hata kama kuna 365 au 366 ndoo inawezekana, na 58 tu ya watu katika chumba hicho. Tu kitakwimu uko uwezekano wa kupata migongano, ambayo katika muda mfupi kilichomsukuma mjadala huu. Kwamba hata kama sisi kupata dhana hapa, na kuanza kuwa na minyororo ya haya, bado tuko kwenda na migongano. Hivyo kwamba anaomba swali, ni nini gharama ya kufanya insertions na kufuta maneno katika muundo wa data kama hii? Vizuri basi mimi kupendekeza - na napenda kwenda nyuma ya screen juu ya hapa - kama sisi n vipengele katika orodha, hivyo kama sisi ni kujaribu kuingiza n vipengele, na tuna wangapi taarifa ndoo? Hebu sema 31 ndoo taarifa katika kesi ya siku za kuzaliwa. Nini upeo wa urefu wa moja ya haya minyororo uwezekano? Kama tena kuna 31 inawezekana kuzaliwa katika mwezi huo. Na tuko tu clumping kila mtu - kweli kwamba ni mfano wa kijinga. Hebu kufanya 26 badala yake. Hivyo kama kweli kuwa watu ambao majina kuanza na kupitia Z, na hivyo kutoa sisi 26 uwezekano. Na sisi ni kutumia mfumo wa data kama mmoja sisi tu kuona, ambapo tuna safu ya kuyatumia, ambayo kila mmoja pointi kwa orodha wanaohusishwa ambapo orodha ya kwanza ni ya kila mtu na Alice jina. orodha ya pili ni kila na jina kwa kuanzia na, kuanzia na B, na kadhalika. Nini urefu uwezekano wa kila moja ya wale orodha kama sisi kudhani safi nzuri usambazaji wa majina kupitia Z hela mfumo mzima data? Kuna n watu katika muundo data kugawanywa na 26, kama uko nicely kuenea nje zaidi ya yote data muundo. Hivyo urefu wa kila moja ya haya minyororo ni n kugawanywa na 26. Lakini katika nukuu kubwa O, ni nini? Nini ni kwamba kweli? Hivyo ni kweli tu n, haki? Kwa sababu tumekuwa alisema katika siku za nyuma, kwamba ugh kugawanya na 26. Ndiyo, katika hali halisi ni kasi zaidi. Lakini katika nadharia, siyo kimsingi yote kwa kasi zaidi. Hivyo hatuna wanaonekana kuwa kiasi kwamba wote karibu na hii grail takatifu. Kwa kweli, hii ni linear wakati. Heck, katika hatua hii, kwa nini sio sisi tu kutumia moja kubwa wanaohusishwa orodha? Mbona sisi tu kutumia moja kubwa safu ya kuhifadhi majina ya kila mtu katika chumba? Vizuri, bado kuna kitu kulazimisha juu ya meza hash? Je, bado kuna kitu kulazimisha kuhusu muundo data kwamba inaonekana kama hii? Hii. MWANAFUNZI: [inaudible]. SPIKA 1: Haki, na tena kama ni tu linear wakati algorithm, na linear wakati data muundo, kwa nini si mimi tu kuhifadhi jina la kila mtu katika kubwa safu, au katika orodha kubwa wanaohusishwa? Na kuacha kufanya hivyo CS vigumu sana kuliko mahitaji kwa kuwa? Je, ni kulazimisha kuhusu hili, hata ingawa mimi kukwangua nje? MWANAFUNZI: [inaudible]. SPIKA 1: insertions siyo? Ghali tena. Hivyo insertions uwezekano bado nilikuwa kuwa mara kwa mara wakati, hata kama wako data muundo inaonekana kama hii, safu ya kuyatumia, ambayo kila mmoja ananyoosha katika uwezekano wa orodha wanaohusishwa. Jinsi gani unaweza kufikia mara kwa mara wakati kuingizwa ya majina? Fimbo yake mbele, haki? Kama sisi sadaka lengo kubuni kutoka mapema, ambapo sisi alitaka kuweka jina la kila mtu, kwa mfano, namna, au wote wa idadi ya juu ya hatua sorted, tuseme kwamba tuna zisizochambuliwa wanaohusishwa orodha. Ni tu yanatugharimu hatua moja au mbili, kama katika kesi ya Ben na Brian mapema, kuingiza kipengele katika mwanzo wa orodha. Hivyo kama sisi hawajali kuhusu kuchagua kila ya majina kuanzia na au wote majina kuanzia na B, tunaweza bado kufikia mara kwa mara wakati kuingizwa. Sasa kuangalia juu Alice au Bob au jina lolote zaidi kwa ujumla bado ni nini? Ni kubwa O ya n kugawanywa na 26, katika bora kesi ambapo kila mtu ni enhetligt kusambazwa, ambapo kuna kama wengi wa kama kuna Z, ambayo pengine ni unrealistic. Lakini hiyo bado linear. Lakini hapa, sisi kuja nyuma kwa uhakika ya nukuu asymptotic kuwa kinadharia kweli. Lakini katika ulimwengu wa kweli, kama mimi kudai kwamba mpango wangu anaweza kufanya kitu 26 mara kasi zaidi kuliko yako, ambaye mpango ni wewe kwenda wanapendelea kutumia? Wako au yangu, ambayo ni 26 mara kwa kasi? Realistically, mtu ambaye ni 26 mara kwa kasi, hata kama kinadharia algorithms wetu kukimbia katika huo asymptotic mbio wakati. Basi mimi kupendekeza mbalimbali ufumbuzi kabisa. Na kama hii haina pigo akili yako, tuko nje ya miundo ya data. Hivyo hii ni trie - aina ya jina kijinga. Inakuja kutoka retrievals, na neno ni yameandikwa trie, t-r-i-e, kwa sababu ya Bila shaka retrieval inaonekana kama trie. Lakini hiyo ni historia trie ya neno. Hivyo trie ni kweli baadhi ya aina ya mti, na pia ni kucheza kwenye neno hilo. Na hata kama huwezi kabisa kuona na taswira hii, trie ni mti muundo, kama mti familia na moja babu saa ya juu na kura wajukuu na vitukuu kama majani juu ya chini. Lakini kila nodi katika trie ni safu. Na ni katika safu - na hebu oversimplify kwa sasa - ni safu, katika kesi hii, ya ukubwa wa 26, ambapo kila node tena ni safu ya ukubwa 26, ambapo kipengele 0 kwa kuwa safu inawakilisha, na ya mwisho kipengele katika kila vile safu inawakilisha Z. Hivyo napendekeza, basi, kwamba hiki data muundo, unaojulikana kama trie, unaweza kuwa kutumika pia kuhifadhi maneno. Tuliona wakati iliyopita jinsi gani tunaweza kuhifadhi maneno, au katika majina ya kesi hii, na sisi aliona mapema jinsi tunaweza kuhifadhi namba, lakini kama sisi kuzingatia majina au masharti hapa, taarifa nini kuvutia. Mimi kudai kwamba Maxwell jina ni ndani ya muundo huu data. Ambapo unaona Maxwell? MWANAFUNZI: [inaudible]. SPIKA 1: Upande wa kushoto. Basi nini kuvutia na data hii muundo ni badala ya kuhifadhi kamba ya M-A-X-W-E-L-L backslash sifuri, kila contiguously, nini badala kufanya ni kufuatia. Kama hii ni trie kama muundo data, kila aina ya nodi ambaye ni tena safu, na unataka kuhifadhi Maxwell, wewe kwanza index na hivyo mzizi wa nodi, hivyo kusema, nodi juu kabisa, katika eneo M, haki, hivyo takribani katika katikati. Na kisha kutoka huko, wewe kufuata pointer nodes mtoto, hivyo kusema. Hivyo kwa mantiki familia mti, wewe kufuata ni kushuka. Na kwamba kusababisha wewe nodi mwingine upande wa kushoto huko, ambayo ni mwingine tu safu. Na kisha kama unataka kuhifadhi Maxwell, unakuta pointer kwamba inawakilisha , Ambayo ni hii moja hapa. Basi wewe kwenda nodi ijayo. Na ilani - hii ni kwa nini picha ya kudanganya kidogo - nodi hii kuangalia super vidogo. Lakini haki ya hii ni Y na Z. Ni tu mwandishi ina truncated picha hivyo kwamba kweli kuona mambo. Vinginevyo hii picha itakuwa hugely kote. Hivyo sasa index katika eneo X, kisha W, Kisha E, basi L, kisha L. Kisha nini hii udadisi? Naam, kama sisi ni kutumia aina hii ya mpya kuchukua juu ya jinsi ya kuhifadhi kamba katika data muundo, bado wanahitaji kimsingi kuangalia mbali katika data muundo kwamba neno kuishia hapa. Kwa maneno mengine, kila mmoja wa nodi hiyo namna fulani ana kukumbuka kwamba sisi kweli ikifuatiwa yote ya kuyatumia haya na ni kuacha kidogo mkate chembe chini ya hii hapa muundo zinaonyesha M-A-X-W-E-L-L ni Hakika katika muundo huu data. Hivyo tupate kufanya kazi hii kama ifuatavyo. Kila wa nodi katika picha ya sisi tu msumeno ina moja, safu ya ukubwa 27. Na ni sasa 27, kwa sababu katika p kuweka sita, tutaweza kweli kukupa apostrophe, ili tuweze kuwa na majina kama O'Reilly na wengine na apostrophes. Lakini huo wazo. Kila moja ya mambo hayo katika safu pointi struct nodi, hivyo tu nodi. Hivyo hii ni kukumbusha ya orodha yetu ya wanaohusishwa. Na kisha nina Boolean, ambayo mimi itabidi kuwaita neno, ambayo ni kwenda tu kuwa kweli kama neno mwisho katika hii nodi katika mti. Ni kwa ufanisi inawakilisha kidogo pembetatu tuliona wakati iliyopita. Hivyo kama neno mwisho katika kwamba nodi katika mti, kwamba shamba neno itakuwa kweli, ambayo ni conceptually kuangalia mbali, au sisi ni kuchora hii pembetatu, ndiyo kuna ni neno hapa. Hivyo hii ni trie. Na sasa swali ni, nini ni yake mbio wakati? Je, ni kubwa O ya n? Je, ni kitu kingine? Naam, kama una n majina katika data hii muundo, Maxwell kuwa moja tu ya yao, ni nini wakati mbio ya kuingiza au kutafuta Maxwell? Nini wakati mbio wa kuingiza Maxwell? Kama kuna n majina mengine tayari katika meza? Yeah? MWANAFUNZI: [inaudible]. SPIKA 1: Yeah, ni urefu ya jina, haki? Hivyo M--x-w-e-l-l hivyo anahisi kama hii algorithm ni kubwa O ya saba. Sasa, bila shaka, jina zitatofautiana kwa urefu. Labda ni jina fupi. Labda ni jina tena. Lakini nini muhimu hapa ni kwamba ni idadi ya mara kwa mara. Na labda ni kweli mara kwa mara, lakini mungu, kama realistically, katika kamusi, pengine kuna baadhi ya kikomo juu ya idadi ya herufi katika jina la mtu katika nchi fulani. Na hivyo tunaweza kudhani kuwa thamani ni mara kwa mara. Mimi sijui ni nini. Ni pengine kubwa kuliko tunafikiri ni. Kwa sababu kuna daima kona baadhi kesi na jina mambo ya muda mrefu. Basi hebu kuiita k, lakini bado mara kwa mara labda, kwa sababu kila jina duniani, angalau katika nchi fulani, ni kwamba urefu au mfupi, hivyo ni mara kwa mara. Lakini wakati tumekuwa alisema kitu ni kubwa O ya thamani ya mara kwa mara, nini kwamba kweli sawa na? Hiyo ni kweli kitu kimoja kama akisema wakati mara kwa mara. Sasa sisi ni aina ya cheating, haki? Sisi ni aina ya leveraging baadhi ya nadharia hapa kusema kisima utaratibu wa k ni kweli ili tu ya moja, na ni mara kwa mara wakati. Lakini ni kweli ni. Kwa sababu ufahamu muhimu hapa ni kwamba kama sisi n majina tayari katika hii data muundo, na sisi Insert Maxwell, ni kiasi cha muda inachukua sisi kuingiza Maxwell wakati wote walioathirika na jinsi watu wengine wengi ni katika muundo wa data? Haionekani kuwa. Kama mimi alikuwa bilioni mambo zaidi na hii trie, na kisha kuingiza Maxwell, ni yeye wakati wote walioathirika? No Na kwamba ni tofauti yoyote ya data siku miundo tumeona hivi sasa, ambapo wakati mbio ya algorithm yako ni kujitegemea kabisa ya kiasi gani mambo ni au si tayari katika kuwa muundo data. Na hivyo na hii erbjuder wewe sasa ni fursa kwa p seti sita, ambayo itakuwa tena kuhusisha kutekeleza yako mwenyewe Spell kusahihisha, kusoma katika 150,000 maneno, namna bora ya kuhifadhi kwamba ni lazima si dhahiri. Na ingawa nimekuwa aspired kupata grail takatifu, sijui kudai kwamba trie ni. Kwa kweli, meza hash anaweza vizuri sana kuthibitisha kuwa ufanisi mkubwa zaidi. Lakini wale ni tu - hiyo ni moja tu ya maamuzi ya kubuni utakuwa na kufanya. Lakini katika kufunga hebu kuchukua 50 au hivyo sekunde kuchukua Peek katika kile uongo mbele wiki ijayo na zaidi ya mpito sisi kutoka hii mstari amri dunia kama C mipango ya mtandao mambo msingi na na lugha kama PHP JavaScript na biashara yenyewe, itifaki kama HTTP, ambayo wewe wameweza kuchukuliwa kwa nafasi kwa miaka sasa, na typed wengi kila siku, labda, au kuonekana. Na tutaweza kuanza peel nyuma tabaka ya nini ni ya internet. Na ni nini kificho kwamba underlies leo zana. Hivyo 50 sekunde ya teaser hii hapa. Nawapa Warriors ya Net. [Video avspelning] -Yeye alikuja na ujumbe. Na itifaki ya yote peke yake. Yeye alikuja kwa dunia ya mpenyo kikatili, asiyejali ruta, na hatari ya mbali mbaya zaidi kuliko kifo. Yeye ni kufunga. Yeye ni nguvu. Yeye ni TCPIP. Na yeye got anwani yako. Warriors ya Net. [MWISHO video avspelning] SPIKA 1: Hiyo ni jinsi ya internet atakuwa kazi kama ya wiki ijayo.