[Music kucheza]
>> DAVID Malan: Hii ni CS50.
Na hii ni wa mwanzo na end-- kama literally-- karibu mwisho
ya wiki sita.
>> Nilidhani ningependa kushiriki kidogo ya ukweli na furaha.
Nimekuwa vunjwa hii kutoka data ya nyuma muhula ya kuweka.
Unaweza kukumbuka kwamba sisi kuuliza wewe juu ya kila p kuweka aina kama wameweza watched online
au kama wameweza walihudhuria katika mtu.
Na hapa ni data.
Hivyo leo ilikuwa sana kutabirika.
Lakini sisi alitaka kutumia kidogo muda na wewe hata hivyo.
Je, mtu yeyote kama dhana nini hii graph ni hivyo jaggy, hadi chini, juu chini,
hivyo mara kwa mara?
Nini kufanya kila ya peaks na Mabwawa kuwakilisha?
>> Watazamaji: [inaudible]
DAVID Malan: Hakika.
Na zaidi amusingly, mungu apishe, sisi kushikilia hotuba moja Ijumaa
mwanzoni mwa muhula, kwamba ni nini tunaona kutokea.
Hivyo leo, sisi kushiriki katika kidogo zaidi kuhusu miundo ya data.
Na kukupa zaidi ya imara mfano wa akili kwa ajili ya matatizo saa tano,
ambayo sasa ni nje.
Misspellings, eti, tutaweza mkono wewe faili Nakala baadhi 100,000
pamoja maneno ya Kiingereza, na wewe ni kwenda kuwa na
kufikiri jinsi ya cleverly shehena yao katika kumbukumbu, katika RAM, kwa kutumia baadhi ya data
muundo wa uchaguzi wako.
>> Sasa mmoja kama data muundo inaweza kuwa, lakini pengine lazima kuwa,
uungwana simplistic wanaohusishwa orodha, ambayo sisi ilianzisha mara ya mwisho.
Na orodha wanaohusishwa alikuwa angalau faida moja juu ya safu.
Nini faida moja ya orodha wanaohusishwa arguably?
>> Watazamaji: Insertion.
>> DAVID Malan: Insertion.
Nini maana na kwamba?
>> Watazamaji: popote pamoja orodha [inaudible].
>> DAVID Malan: Good.
Hivyo unaweza kuingiza kipengele popote unataka katikati ya orodha
bila ya kuwa na changa chochote, ambayo sisi alihitimisha, katika kuchagua wetu
majadiliano, si lazima jambo jema,
kwa sababu inachukua muda wa kweli hoja yote ya binadamu wale wa kushoto au kulia.
Na hivyo na orodha wanaohusishwa, unaweza tu kutenga na malloc, nodi mpya,
na kisha update michache pointers-- mbili, shughuli tatu max--
na sisi ni uwezo wa yanayopangwa mtu katika mahali popote katika orodha.
>> Kile kingine ilikuwa faida kuhusu orodha wanaohusishwa?
Yeah?
>> Watazamaji: [inaudible]
DAVID Malan: Perfect.
Kamilifu.
Ni kweli nguvu.
Na kwamba wewe si kufanya, mapema, baadhi ya ukubwa fasta
chunk ya kumbukumbu, kama ingekuwa kwa pamoja na safu, kichwa ambayo
ni kwamba unaweza kutenga nodes tu juu ya mahitaji na hivyo kutumia nafasi kama kiasi tu
kweli kama unahitaji.
Kwa kulinganisha na safu, unaweza ajali kutenga kidogo sana.
Na basi ni kwenda tu kuwa maumivu ya shingo
kwa reallocate mpya kubwa safu, nakala kila kitu juu, bure safu ya zamani,
na kisha kuondoka kuhusu biashara yako.
Au mbaya zaidi, unaweza kutenga njia zaidi ya kumbukumbu kuliko wewe kweli haja,
na hivyo wewe ni kwenda kuwa na sana wachache-wakazi safu, hivyo kusema.
>> Hivyo orodha wanaohusishwa inakupa haya faida ya mabadiliko na kubadilika
na insertions na kufuta maneno.
Lakini hakika lazima kuna bei ya kulipwa.
Kwa kweli, moja ya mandhari Kugundua juu ya jaribio sifuri
ilikuwa michache ya biashara awamu ya pili tumeona hivi sasa.
Basi nini au bei ya kulipwa upande wa chini ya orodha wanaohusishwa?
Yeah.
>> Watazamaji: Hakuna upatikanaji random.
>> DAVID Malan: Hakuna upatikanaji random.
Lakini anayejali?
Random upatikanaji haina sauti ya kulazimisha.
>> Watazamaji: [inaudible]
DAVID Malan: Hasa.
Kama unataka kuwa algorithm-- fulani
na napenda kweli kupendekeza binary tafuta hasa, ambayo
ni moja tumekuwa kutumika kabisa bit-- kama huna upatikanaji random,
unaweza kufanya hivyo hesabu rahisi ya kutafuta kama kipengele katikati
na kuruka haki yake.
Wewe badala kuanza kwa mara ya kwanza kipengele na linearly kutafuta kutoka kushoto
na haki kama unataka kupata katikati au kipengele nyingine yoyote.
>> Watazamaji: Ni pengine inachukua zaidi ya kumbukumbu.
>> DAVID Malan: inachukua zaidi ya kumbukumbu.
Ambapo ni kwamba ziada gharama kuja kutoka katika kumbukumbu?
>> Watazamaji: [inaudible]
DAVID Malan: Hasa.
Katika kesi hii hapa, tulikuwa orodha wanaohusishwa kwa integers,
na bado tuko mara dufu kiasi cha kumbukumbu
tunahitaji na pia kuhifadhi kuyatumia haya.
Sasa chini ya mpango kubwa kama structs yako kupata kubwa
na wewe ni hifadhi si idadi lakini labda mwanafunzi au baadhi kitu kingine.
Lakini uhakika hakika bado.
Na hivyo idadi ya shughuli katika orodha wanaohusishwa waliitwa
walikuwa O kubwa ya n-- linear.
Mambo kama insertion au tafuta au kufutwa katika kesi ya kipengele
kilichotokea kwa kuwa katika mwisho sana ya orodha kama ni vyema au la.
>> Wakati mwingine unaweza kupata bahati na katika mipaka hivyo chini juu ya shughuli hizo
anaweza pia kuwa wakati mara kwa mara kama wewe ni daima kuangalia kipengele kwanza,
kwa mfano.
Lakini hatimaye, sisi aliahidi kufikia grail takatifu
wa miundo data, au baadhi yake makadirio,
kwa njia ya muda wa mara kwa mara.
Tunaweza kupata mambo au kuongeza mambo au kuondoa vipengele kutoka orodha?
Tutaona kabisa hivi karibuni.
Na zinageuka kuwa moja ya taratibu tuko
kwenda kuanza kutumia leo, matumizi ya kila mwaka katika p kuweka tano,
ni kweli pretty ukoo.
Kwa mfano, kama hii ni rundo vitabu mtihani, ambayo kila mmoja
ina mwanafunzi wa kwanza jina na jina la mwisho juu yake,
na mimi kuwachukua kutoka mwishoni mwa mtihani,
na wao uko wote pretty kiasi ili random,
na tunataka kwenda juu ya kuchagua mitihani hizi hivyo kwamba mara graded
ni tu rahisi sana na kasi ya mkono wao nyuma nje
kwa wanafunzi alphabetically.
Gani silika yako kuwa kwa rundo la mitihani kama hii?
>> Naam, kama wewe ni kama mimi, wewe ili kuona kwamba hii ni m,
hivyo mimi nina kwenda aina ya kuweka hii katika, kama hii ni meza yangu au sakafu yangu ambapo
Mimi kueneza mambo out-- au safu yangu really--
Nipate kuweka yote ya Bi huko.
Oh.
Hapa ni A. Hivyo mimi ili kuweka Kama zaidi ya hapa.
Oh.
Hapa ni A. mwingine mimi nina kwenda kuweka kwamba zaidi ya hapa.
Hapa ni Z. Hapa ni mwingine M. Na hivyo Mimi ili kuanza kufanya piles kama hii.
Na kisha labda Ningependa kwenda katika baadaye na aina ya nitpicky-ly sana aina
piles ya mtu binafsi.
Lakini uhakika ni mimi bila kuangalia katika pembejeo kwamba mimi nina mitupu
na napenda kufanya baadhi ya mahesabu uamuzi kulingana na pembejeo kwamba.
Kama ni kuanza na, kuiweka zaidi ya hapo.
Kama ni kuanza kwa Z, kuiweka juu ya huko, na kila kitu katika kati.
>> Hivyo hii ni mbinu hiyo ni ujumla inayojulikana kama hashing-- H-A-S-H--
ambayo kwa ujumla ina maana ya kuchukua kama pembejeo na kutumia pembejeo kwamba compute
thamani, kwa ujumla idadi, na kwamba idadi ni index katika kuhifadhi
chombo, kama safu.
Hivyo kwa maneno mengine, mimi ili kuwa na kazi hash, kama mimi kufanya katika kichwa changu,
kwamba kama mimi kuona mtu ni jina ambao huanza na A,
Mimi nina kwenda ramani kwamba kwa sifuri katika kichwa changu.
Na kama mimi kuona mtu na Z, mimi nina kwenda ramani kwamba 25 katika kichwa changu
na kisha kuweka kwamba katika mwisho zaidi ya rundo.
>> Sasa, kama unafikiri kuhusu si ubongo wangu lakini C mpango, nini naweza namba
wanategemea kufikia matokeo kwamba huo?
Kwa maneno mengine, kama wewe alikuwa ASCII tabia A,
jinsi gani unaweza kuamua nini ndoo ili kuweka katika?
Pengine hawataki kuiweka katika ndoo 65, ambayo
itakuwa kama zaidi ya hapo kwa maana hakuna sababu nzuri.
Ambapo unataka kuweka A katika suala la thamani yake ASCII?
Ambapo unataka kufanya ASCII wake thamani kuja na ndoo nadhifu
kuiweka katika?
>> Watazamaji: Minus A.
>> DAVID Malan: Yeah.
Hivyo minus A au bala hasa 65 kama ni
mji mkuu A. Au 98 kama ni ndogo a.
Na hivyo kwamba itakuwa kuruhusu sisi, sana tu na kihisabati sana,
kuweka kitu ndani ya ndoo kama hiyo.
Hivyo ni zamu nje sisi kwa kweli kufanya hii vilevile hata kwa Quizzes.
>> Hivyo unaweza kukumbuka you ikizunguka yako jina mafundisho wenzake juu ya bima.
Na majina TF walikuwa kupangwa ndani ya nguzo hizi alphabetically,
vizuri, amini au si, wakati wote pamoja na 80 wa kwetu
got pamoja usiku mengine daraja, hatua ya mwisho katika mchakato wetu grading
ni hash Quizzes katika kubwa nafasi ya sakafu katika [inaudible]
na kuweka Quizzes kila mtu nje katika hasa utaratibu wa TF yao
majina juu ya bima, kwa sababu basi ni rahisi sana kwa ajili yetu
kutafuta njia ya kwamba kwa kutumia linear kutafuta au aina fulani ya ujanja
kwa TF kupata au wake wanafunzi wake 'Quizzes.
>> Hivyo hii wazo la hashing kwamba utaona ni
nguvu kabisa ni kweli pretty kawaida na Intuitive sana,
kiasi kama labda kugawanya na kushinda alikuwa katika wiki sifuri.
Mimi mbele kwa haraka na hackathon miaka michache iliyopita.
Hii ilikuwa Zamyla na michache ya mengine ya wanafunzi wafanyakazi salamu
walipokuwa katika.
Na tulikuwa na rundo zima la Folding meza kuna na vitambulisho jina.
Na tulikuwa na vitambulisho jina kupangwa na kama Kama zaidi ya hapo
na ZS zaidi ya hapo.
Na hivyo moja ya TFS cleverly sana aliandika hii kama maelekezo
kwa siku.
Na katika wiki ya 12 ya muhula hii yote yaliyotolewa akili kamilifu na kila mtu
alijua nini cha kufanya.
Lakini wakati wowote wameweza queued katika njia hiyo hiyo,
wewe ni kutekeleza dhana hiyo ya hash.
Basi hebu kurasimisha ni kidogo.
Hapa ni safu.
Ni inayotolewa kwa kuwa ni kidogo pana tu depict, kuibua,
tupate kuweka masharti katika kitu kama hiki.
Na safu hii ni wazi ya jumla ukubwa 26.
Na jambo inaitwa meza kiholela.
Lakini hii ni tu mpenyo msanii nini meza hash inaweza kuwa.
>> Hivyo meza hash sasa ni kwenda kuwa juu ya muundo data ngazi.
Mwisho wa siku sisi ni juu ya kuona kwamba
unaweza kutekeleza hash meza, ambayo ni kiasi kama line kuangalia katika
katika hackathon kiasi kama hii meza kutumika kwa ajili ya kuchagua vitabu mtihani.
Lakini meza hash ni aina ya ngazi hii ya juu
dhana kwamba inaweza kutumia safu chini ya kofia ya kutekeleza,
au inaweza kutumia orodha urefu, au hata labda baadhi wengine miundo data.
Na sasa kwamba kuchukua theme-- baadhi ya viungo haya ya msingi
kama safu na jengo hili kuzuia sasa ya orodha urefu
na kuona nini kingine tunaweza kujenga juu ya wale, kama viungo
ndani ya kichocheo, na kufanya zaidi na zaidi kuvutia na manufaa ya mwisho matokeo.
>> Hivyo pamoja na meza hash tupate kutekeleza
katika kumbukumbu pictorially kama hii, lakini jinsi gani ni kweli kuwa kutolewa up?
Vizuri, labda kama tu ni hii.
Kama UWEZO katika mechi zote, ni tu baadhi constant-- kwa mfano 26,
kwa herufi 26 ya alphabet-- Nipate kuwaita meza yangu variable,
na mimi ili kudai kwamba mimi nina kwenda kuweka nyota Char huko, au kamba.
Hivyo ni rahisi kama hii kama wewe wanataka kutekeleza meza hash.
Na bado, hii ni kweli tu safu.
Lakini tena, hash meza ni sasa nini tutaweza
kuwaita data abstract aina hiyo ni aina ya layering dhana juu
wa kitu zaidi mundane sasa kama safu.
>> Sasa, jinsi gani sisi kwenda kuhusu kutatua matatizo?
Naam, awali nilikuwa anasa ya kuwa na nafasi ya kutosha meza hapa
ili niweze kuweka Quizzes popote nilitaka.
Hivyo Kama wanaweza kwenda hapa.
ZS wanaweza kwenda hapa.
Bi wanaweza kwenda hapa.
Na kisha mimi alikuwa na baadhi ya nafasi ya ziada.
Lakini hii ni kidogo ya kudanganya haki sasa kwa sababu meza hii, kama kweli
mawazo ya kama safu, ni tu itakuwa ya baadhi ya kawaida fasta.
>> Basi kitaalam, kama mimi kuvuta up jaribio mwanafunzi mwingine
na kuona, oh, mtu huyu jina huanza na A pia,
Mimi aina ya kutaka kuiweka huko.
Lakini haraka kama mimi kuiweka huko, kama meza hii kweli inawakilisha safu,
Mimi nina kwenda kuwa kuu au clobbering yeyote Jaribio mwanafunzi huu ni.
Haki?
Kama hii ni safu, jambo moja tu unaweza kwenda katika kila moja ya seli hizi au vipengele.
Na hivyo mimi aina ya kuwa kuchukua na kuchagua.
>> Sasa mapema Mimi aina ya cheated na alifanya hii au mimi
tu aina ya sifa yao juu ya kila mmoja.
Lakini kwamba si kwenda kuruka katika kanuni.
Hivyo ambapo naweza kuweka mwanafunzi wa pili jina lake
A ni kama wote nilikuwa ni hii inapatikana meza nafasi?
Na nimekuwa kutumika inafaa tatu na Inaonekana kama kuna wengine chache tu.
Unaweza kufanya nini?
Watazamaji: [inaudible]
DAVID Malan: Yeah.
Labda hebu tu kushika ni rahisi.
Haki?
Haina fit ambapo nataka kuweka.
Hivyo nina kwenda kwa kuiweka kitaalam ambapo B aliamua kwenda.
Sasa, bila shaka, mimi nina kuanza rangi mwenyewe katika kona.
Kama mimi kupata mwanafunzi ambaye jina lake ni kweli B,
sasa B ni kwenda kuwa wakiongozwa kidogo mbele, kama inaweza kutokea, yep,
kama hii ni B, sasa ina kwenda hapa.
>> Na hivyo hii haraka sana inaweza kuwa tatizo,
lakini ni mbinu ambayo kweli ni inajulikana kama linear uchunguzi,
ambapo wewe tu kufikiria yako safu kuwa pamoja mstari.
Na wewe tu aina ya kuchunguza au kukagua kila kipengele inapatikana
kuangalia kwa doa inapatikana.
Na haraka kama wewe kupata moja, wewe kushuka huko.
>> Sasa, bei kulipwa sasa kwa ufumbuzi huu ni nini?
Tuna fasta ukubwa safu, na wakati mimi kuingiza majina
ndani yake, angalau awali, nini wakati mbio za insertion
kwa ajili ya kuweka ya wanafunzi ' Quizzes katika ndoo haki?
Big O nini?
>> Watazamaji: n.
DAVID Malan: nikasikia O kubwa ya n.
Si kweli.
Lakini tutaweza tease mbali nini katika muda tu.
Nini kingine inaweza kuwa kitu gani?
>> Watazamaji: [inaudible]
DAVID Malan: Na napenda kufanya hivyo kuibua.
Hivyo tuseme hii ni barua S.
>> Watazamaji: Ni moja.
DAVID Malan: Ni moja.
Haki?
Hii ni safu, ambayo ina maana sisi kupata random.
Na kama sisi kufikiri ya hii kama sifuri na hii kama 25,
na sisi kutambua kwamba, oh, hapa pembejeo yangu S,
Mimi tunaweza kubadilisha S, tabia ASCII,
kwa idadi inayolingana kati ya sifuri na 25
na kisha mara moja kuiweka ambapo ni mali.
>> Lakini bila shaka, haraka kama mimi kupata mtu wa pili ambaye ni jina ni A au B au C
hatimaye, kama nimekuwa kutumika linear uchunguzi kama ufumbuzi yangu,
wakati mbio za insertion katika kesi mbaya
ni kweli kwenda devolve katika nini?
Na mimi kusikia hapa usahihi mapema.
Watazamaji: [inaudible]
DAVID Malan: Hivyo ni kweli n mara moja una kubwa ya kutosha data kuweka.
Hivyo, kwa upande mmoja, kama safu yako ni kubwa ya kutosha
na data yako ni sparse kutosha, kupata muda huu mzuri wa mara kwa mara.
Lakini haraka kama wewe kuanza kupata mambo zaidi na zaidi,
na tu kitakwimu kupata watu zaidi na barua
kama jina yao au barua B, inaweza uwezekano
kukabidhi katika kitu zaidi linear.
Hivyo si kabisa kamilifu.
Hivyo tunaweza kufanya vizuri zaidi?
>> Naam, nini ilikuwa wetu ufumbuzi kabla ya wakati sisi
wanataka kuwa zaidi kuliko mabadiliko kitu kama safu kuruhusiwa?
Watazamaji: [inaudible]
DAVID Malan: Je, sisi kuanzisha?
Yeah.
Hivyo orodha wanaohusishwa.
Naam, hebu angalia nini wanaohusishwa orodha inaweza kufanya kwa ajili yetu badala yake.
Naam, napenda kupendekeza kwamba sisi kuchora picha kama ifuatavyo.
Sasa hii ni tofauti picha kutoka kwa mfano
kutoka Nakala tofauti, kwa kweli, kwamba ni kweli kutumia safu ya ukubwa 31.
Na mwandishi hii tu aliamua hash masharti
si kulingana na majina ya mtu, lakini kulingana na birthdates yao.
Bila kujali mwezi, wao figured kama wewe ni mzaliwa wa siku ya kwanza ya mwezi
au 31 ya mwezi, mwandishi itakuwa hash kulingana na thamani ya kwamba,
ili kuenea majina nje kidogo zaidi kuliko tu 26 matangazo ili kuruhusu.
Na labda ni kidogo zaidi sare kuliko kwenda kwa herufi herufi,
kwa sababu bila shaka kuna pengine watu zaidi katika dunia na majina
kwamba kuanza na kuliko kwa hakika baadhi ya barua nyingine ya alfabeti.
Hivyo labda hii ni kidogo sare zaidi, kuchukua
usambazaji sare ya watoto katika mwezi.
>> Lakini, bila shaka, hii ni bado kamili.
Haki?
Sisi ni kuwa migongano.
Watu mbalimbali katika hii Muundo data bado
kuwa tarehe ya kuzaliwa sawa angalau wewe ni bila ya kujali kwa mwezi.
Lakini kile mwandishi kosa gani?
Naam, inaonekana kama tuna safu upande wa kushoto mkono inayotolewa wima,
lakini hiyo ni mpenyo msanii.
Haijalishi nini mwelekeo kuteka safu, bado safu.
Ni nini hii safu ya inaonekana?
>> Watazamaji: Wanaohusishwa orodha.
>> DAVID Malan: Yeah.
Inaonekana kama ni safu ya orodha wanaohusishwa.
Hivyo tena, hatua hii ya aina ya kutumia miundo hizi data sasa
kama viungo zaidi ufumbuzi kuvutia,
unaweza kabisa kuchukua msingi, kama safu,
na kisha kuchukua kitu zaidi kuvutia kama orodha wanaohusishwa
na hata kuchanganya yao katika hata zaidi ya kuvutia data muundo.
Na kwa kweli, hii pia ingekuwa kuitwa meza hash,
ambapo safu ni kweli meza hash,
lakini kwamba meza hash ina minyororo, ili kuzungumza,
ambayo inaweza kukua au kuogopa kulingana na idadi ya vipengele unataka kuingiza.
>> Sasa, ipasavyo, nini mbio wakati sasa?
Kama nataka kuingiza mtu ambao siku ya kuzaliwa ni Oktoba 31,
ambapo haina yeye au yeye kwenda?
Wote haki.
Chini sana ambapo anasema 31.
Na kwamba ni kamilifu.
Hiyo ilikuwa mara ya mara kwa mara.
Lakini nini kama sisi kupata mtu mwingine ambao siku ya kuzaliwa ni, hebu angalia,
Oktoba, Novemba, Desemba 31?
Ambapo ni yeye au yeye kwenda?
Same kitu.
Hatua mbili ingawa.
Hiyo ni mara kwa mara ingawa si hivyo?
Wote haki.
Kwa sasa ni.
Lakini katika kesi ujumla, watu zaidi sisi kuongeza,
probabilistically, tunakwenda kupata collisions zaidi na zaidi.
>> Sasa hii ni kidogo bora kwa sababu kitaalam
sasa kifungoni inaweza kuwa katika kesi mbaya kwa muda gani?
Kama mimi kuingiza n watu katika hii zaidi Muundo wa kisasa data, n watu,
katika kesi mbaya ni kwenda kuwa n.
Kwa nini?
>> Watazamaji: Kwa sababu kama kila mtu ina siku ya kuzaliwa huo,
wao ni kwenda kuwa mstari mmoja.
DAVID Malan: Perfect.
Ni inaweza kuwa ni kidogo contrived, lakini kweli katika kesi mbaya,
kama kila mtu ana siku ya kuzaliwa huo, kupewa pembejeo una,
wewe ni kwenda kuwa na massively mlolongo mrefu.
Na hivyo, unaweza kuiita hash meza, lakini kwa kweli ni
tu kubwa wanaohusishwa orodha kwa mengi yote ya kupita nafasi.
Lakini kwa ujumla, kama sisi kudhani kwamba angalau siku za kuzaliwa ni uniform--
na pengine si.
Mimi nina kufanya kwamba up.
Lakini kama sisi kudhani, kwa ajili ya majadiliano
kwamba wao ni, basi katika nadharia, kama hii ni ya uwakilishi wima
wa safu, vizuri basi hopefully wewe ni kwenda kupata minyororo kwamba ni, unajua,
takribani urefu huo ambapo kila mmoja hizi inawakilisha siku ya mwezi.
>> Sasa kama kuna siku 31 katika mwezi, hiyo ina maana mbio wangu wakati kweli
ni O kubwa ya n juu ya 31, ambayo anahisi bora kuliko linear.
Lakini nini alikuwa mmoja wa wetu ahadi wiki kadhaa
iliyopita wakati wowote alikuja kuonyesha wakati wa algorithm mbio?
Tu tu kuangalia juu ili mfupi.
Haki?
31 ni dhahiri manufaa.
Lakini hii bado O kubwa ya n.
Lakini moja ya mandhari tatizo kuweka tano
ni kwenda kuwa na kukiri kwamba kabisa,
asymptotically, kinadharia muundo huu data
hakuna bora kuliko tu moja kubwa wanaohusishwa orodha.
Na kwa kweli, katika kesi mbaya, hii hash meza inaweza kukabidhi katika hiyo.
>> Lakini katika ulimwengu wa kweli, na sisi binadamu kwamba Macs mwenyewe au PC au chochote
na ni mbio ulimwengu halisi programu kwenye data halisi ya dunia,
ambayo algorithm ni wewe kwenda kupendelea?
moja kwamba inachukua hatua ya mwisho au moja kwamba inachukua n kugawanywa na hatua 31
kupata baadhi ya kipande cha data au kuangalia juu ya baadhi ya taarifa?
I mean, kabisa 31 hufanya tofauti katika ulimwengu wa kweli.
Ni mara 31 kwa kasi zaidi.
Na sisi wanadamu ni hakika kwenda kufahamu kwamba.
>> Hivyo kutambua dichotomy kuna kati ya kweli
kuzungumza juu ya mambo kinadharia na asymptotically ambayo dhahiri
ina thamani kama tumeona, lakini katika ulimwengu wa kweli,
kama huduma ya juu maamuzi tu furaha ya binadamu kwa ajili ya pembejeo kwa ujumla,
unaweza vizuri sana wanataka kukubali ukweli kwamba, ndiyo, hii ni linear,
lakini ni mara 31 kwa kasi kuliko linear inaweza kuwa.
Na bado bora, sisi si tu na kufanya kitu kiholela kama tarehe ya kuzaliwa,
tunaweza kutumia kidogo muda zaidi na ujanja
na kufikiri kuhusu nini sisi tupate kufanya, kupewa jina la mtu na labda
tarehe ya kuzaliwa yao kwa kuchanganya wale viungo kufikiri kitu
kwamba ni kweli zaidi sare na chini jaggy,
hivyo kusema kuliko picha hii sasa unaonyesha inaweza kuwa.
Jinsi gani sisi kutekeleza hili katika kanuni?
Naam, napenda kupendekeza kwamba sisi tu kukopa baadhi syntax tumekuwa
kutumika mara kadhaa hivi sasa.
Na mimi nina kwenda kufafanua nodi, ambayo tena
ni mrefu generic kwa baadhi tu chombo kwa ajili ya baadhi ya muundo data.
Mimi nina kwenda kupendekeza kwamba kamba ni kwenda huko.
Lakini sisi ni kwenda kuanza kuchukua wale mafunzo magurudumu mbali sasa.
>> Hakuna zaidi CS50 maktaba kweli, isipokuwa unataka
kuitumia kwa ajili ya fainali yako mradi, ambayo ni mzuri,
lakini sasa tunakwenda kuvuta nyuma pazia na kusema ni tu nyota Char.
Hivyo neno kuna ni kwenda kuwa na jina la mtu katika swali.
Na sasa nina kiungo hapa nodi ijayo
hivyo kwamba hawa kuwakilisha kila nodes
katika mlolongo, uwezekano, ya orodha wanaohusishwa.
>> Na sasa jinsi ya kufanya Mimi kutangaza hash meza yenyewe?
Je, mimi kutangaza muundo huu wote?
Vizuri, kwa kweli, kiasi kama mimi kutumika pointer tu kipengele kwanza ya orodha
kabla, vile vile naweza kusema tu Mimi tu haja rundo la kuyatumia
kutekeleza hash hii nzima meza.
Mimi nina kwenda kuwa safu aitwaye meza hash meza kwa.
Ni kwenda kuwa ukubwa wa uwezo.
Hiyo ni jinsi mambo mengi unaweza fit katika hilo.
Na kila moja ya mambo hayo katika hii safu ni kwenda kuwa nyota nodi.
Kwa nini?
Naam, kwa picha hii, nini mimi nina kutekeleza hash meza kama
ufanisi katika mwanzo tu safu hii kwamba tumepata wima,
kila mmoja wa viwanja ambao inawakilisha pointer.
Kwamba wale ambao mikwaju njia yao ni tu null.
Na wale ambao mishale ya kwenda haki
ni kuyatumia halisi kwa nodes halisi, Ergo mwanzo wa orodha wanaohusishwa.
>> Hivyo hapa, basi, ni jinsi sisi anaweza kutekeleza meza hash kwamba
kutekeleza tofauti chaining.
Sasa tunaweza kufanya vizuri zaidi?
Haki zote mimi aliahidi mara ya mwisho kwamba tunaweza kufikia wakati wa mara kwa mara.
Na mimi aina ya alitoa wewe wakati mara kwa mara hapa,
lakini basi alisema si kweli wakati mara kwa mara kwa sababu ni bado
tegemezi jumla idadi ya vipengele
wewe ni inputting katika data ya muundo.
Lakini tuseme sisi alifanya hivyo.
Napenda kwenda nyuma ya screen ya juu hapa.
Napenda pia mradi huu hadi hapa, wazi screen, na nadhani alifanya hivyo.
Tuseme nilitaka kuingiza jina Daven katika katika muundo wangu data.
>> Hivyo nataka kuingiza kamba Daven katika muundo data.
Nini kama mimi si kutumia hash meza, lakini mimi kutumia
kitu ambacho ni zaidi ya mti-kama kama familia mti, ambapo
una baadhi ya mizizi katika nodes juu na kisha na majani
kwamba kwenda kushuka na nje.
Tuseme basi, kwamba mimi wanataka kuingiza Daven ya
ndani ya nini sasa orodha tupu.
Mimi nina kwenda kufanya yafuatayo: Mimi nina kwenda kujenga nodi katika familia hii
mti-kama muundo data kwamba inaonekana kidogo kama hii, ambayo kila mmoja
mistatili ina, hebu sema, kwa sasa 26 mambo ndani yake.
Na kila seli katika safu hii ni kwenda
kuwakilisha barua ya alfabeti.
>> Hasa, mimi nina kwenda kutibu hii ni, basi B, basi C, basi D,
hii moja hapa.
Hivyo hii ni kwenda kwa ufanisi kuwakilisha barua D.
Lakini kuingiza yote ya Daven ya jina mimi haja ya kufanya kidogo zaidi.
Hivyo mimi nina kwanza kwenda hash, hivyo kusema.
Mimi nina kwenda kuangalia barua ya kwanza katika Daven ambayo ni wazi D,
na mimi nina kwenda kutenga nodi kwamba inaonekana
kama this-- Mstatili kubwa kubwa kutosha fit alfabeti nzima.
>> Sasa D ni kosa.
Sasa A. D-A-V-E-N ni lengo.
Hivyo sasa nini mimi kwenda kufanya ni hii.
Haraka kama mimi kuanza D taarifa hakuna pointer huko.
Ni wakati maadili ya takataka, au mimi ili initialize kwa null.
Lakini ngoja kuendelea na wazo hili la kujenga mti.
Napenda kutenga mwingine mmoja wa haya nodes kwamba ina mambo 26 ndani yake.
>> Na unajua nini?
Kama hii ni tu nodi katika kumbukumbu kwamba Mimi iliundwa na malloc, kwa kutumia struct
kama tutaweza hivi karibuni kuona, Mimi nina kwenda kufanya this--
Mimi nina kwenda kuteka mshale kutoka Jambo kwamba kuwakilishwa D chini
nodi hii mpya.
Na sasa, kwanza ijayo barua katika jina Daven wa,
V-- D-A-V-- mimi nina kwenda mbele na kuteka nodi mwingine kama huu,
ambapo, V mambo hapa, ambayo tutaweza kuteka kwa whoops instance--.
Sisi si kuteka huko.
Ni kwenda hapa.
>> Kisha tunakwenda kufikiria hili kuwa V.
Na kisha chini hapa tunakwenda index chini kutoka V katika kile tutaweza kufikiria E.
Na kisha kutoka hapa tunakwenda kwenda kuwa moja ya nodes hizi hapa.
Na sasa tuna swali kujibu.
Mimi haja ya namna fulani zinaonyesha kwamba tuko katika mwisho wa kamba Daven.
Ili niweze kuondoka tu null.
>> Lakini nini kama tuna Daven ya jina kamili pia, ambayo
yaani, kama tumekuwa alisema, Davenport?
Basi nini kama Daven ni kweli substring,
kiambishi ya kamba sana tena?
Hatuwezi tu kudumu kusema chochote ni kwenda
kwenda huko, kwa sababu tunaweza kamwe kuingiza neno kama Davenport
ndani ya hii Muundo data
>> Hivyo nini tunaweza kufanya badala ni kutibu kila ya mambo haya
kama labda kuwa na mbili mambo ya ndani yao.
Moja ni pointer, kwa hakika, kama nimekuwa kufanya.
Hivyo kila mmoja wa masanduku hayo si kiini moja tu.
Lakini nini kama juu one-- chini moja ya
itakuwa null, kwa sababu hakuna Davenport bado tu.
Nini kama moja ya juu ni baadhi ya thamani maalum?
Na ni kwenda kuwa kidogo ngumu kuteka ni ukubwa huu.
Lakini tuseme ni tu alama kuangalia.
Kuangalia.
D-A-V-E-N ni kamba katika muundo huu data.
>> Wakati huo huo, kama ningekuwa na nafasi zaidi hapa, mimi naweza kufanya P-O-R-T,
na mimi naweza kuweka hundi katika nodi ambayo ina barua T mwishoni sana.
Hivyo hii ni massively tata-kuangalia muundo data.
Na mwandiko wangu hakika haina msaada.
Lakini kama mimi alitaka kuingiza kitu mwingine, kufikiria nini tunataka kufanya.
Kama sisi alitaka kuweka Daudi katika, tunatarajia kufuata mantiki hiyo, D-A-V,
lakini sasa napenda kumweka katika ijayo kipengele si kutoka E, lakini kutokana na mimi kwa D.
Hivyo kuna kwenda kuwa nodes zaidi katika mti huu.
Tunakwenda kuwa wito malloc zaidi.
Lakini mimi sitaki kufanya fujo kamili ya picha hii.
Basi hebu badala kuangalia moja hiyo imekuwa kabla ya yaliyoandaliwa
kama hii na si dot, dot, dots, lakini arrays tu kifupi.
Lakini kila mmoja wa nodes katika hii hapa mti up
inawakilisha thing-- sawa safu Ray ya ukubwa 26.
>> Au kama tunataka kuwa kweli sahihi sasa, nini
kama jina la mtu kama apostrophe, hebu
kudhani kuwa kila nodi kweli ina kama 27 bahati katika hilo, si tu 26.
Hivyo hii sasa ni kwenda kuwa na data Muundo aitwaye trie-- T-R-I-E.
trie, ambayo ni eti kihistoria jina wajanja kwa mti
hiyo ni optimized kwa ajili ya retrieval, ambayo bila shaka,
yameandikwa na mimi-E hivyo ni trie.
Lakini hiyo ni historia ya trie.
>> Hivyo trie ni hii data mti-kama Muundo kama mti familia
kwamba hatimaye kutenda kama hiyo.
Na hapa ni mfano mwingine wa rundo zima la majina ya watu wengine.
Lakini swali sasa upande ni nini na
sisi kupata kwa kuanzisha arguably zaidi ngumu data muundo, na moja,
kusema ukweli, ambayo inatumia mengi ya kumbukumbu.
>> Kwa sababu hata ingawa, kwa wakati huu, mimi nina tu
kutumia D's pointer na A na V na Es na Ns,
Mimi kupoteza heck ya mengi ya kumbukumbu.
Lakini ambapo mimi kutumia rasilimali moja, Mimi huwa hawana kupata nyuma ya mwingine.
Hivyo kama mimi nina kutumia nafasi zaidi, nini pengine matumaini?
Kwamba mimi nina matumizi ya chini ya nini?
Watazamaji: Chini ya muda.
DAVID Malan: Time.
Sasa kwa nini huenda kuwa?
Vizuri, ni nini insertion muda, katika suala la big O sasa,
jina kama Daven au Davenport au Daudi?
Naam, Daven ilikuwa hatua tano.
Davenport itakuwa hatua tisa, hivyo itakuwa hatua chache zaidi.
Daudi itakuwa hatua tano kama vizuri.
Hivyo wale ni halisi namba, lakini hakika kuna
amefungwa juu juu ya urefu wa jina la mtu.
Na kwa kweli, katika tatizo seti ya tano vipimo,
tunakwenda kupendekeza kwamba ni kitu
hiyo ni wahusika 40-baadhi-isiyo ya kawaida.
>> Realistically, hakuna mtu ana jina kubwa kwa muda mrefu,
ambayo ni kusema kwamba urefu wa jina au urefu wa kamba tupate
kuwa baadhi ya hali ya muundo ni arguably nini?
Ni mara kwa mara.
Haki?
Inaweza kuwa mara kwa mara kubwa kama 40-kitu, lakini ni mara kwa mara.
Na ina hakuna utegemezi juu ya jinsi wengi majina mengine ni katika muundo huu data.
Kwa maneno mengine, kama mimi alitaka sasa kuingiza
Colton au Gabriel au Rob au Zamyla au Alison au Belinda au majina mengine yoyote
kutoka kwa wafanyakazi katika taarifa hii muundo, ni wakati mbio
ya kuingiza majina mengine itakuwa wakati wote wanashikiliwa
na mambo mengine jinsi wengi ni katika muundo data tayari?
Ni si.
Haki?
Sababu sisi ni kutumia kwa ufanisi hii tabaka mbalimbali hash meza.
Na wakati mbio ya yoyote ya shughuli hizo
ni tegemezi si juu ya idadi ya mambo ambayo ni katika muundo data
au kwamba ni hatimaye kwenda kuwa katika muundo data,
lakini juu ya urefu wa nini hasa?
>> kamba kuwa kuingizwa, ambayo haina kufanya
hii asymptotically mara kwa mara time-- kubwa O ya moja.
Na kusema ukweli, tu katika ulimwengu halisi, hii
ina maana ya kuingiza jina Daven inachukua kama hatua tano, au Davenport tisa
hatua, au Daudi hatua tano.
Hiyo ni pretty darn mara ndogo mbio.
Na kwa kweli, hiyo ni sana jambo jema, hasa wakati
si tegemezi kwa jumla idadi ya vipengele katika huko.
Hivyo ni jinsi inaweza sisi kutekeleza hii aina ya muundo katika kanuni?
Ni kidogo zaidi tata, lakini bado ni
tu ya maombi ya msingi jengo vitalu.
Mimi nina kwenda kutafsiri upya nasi nodi kama ifuatavyo:
bool aitwaye word-- na hii inaweza kuitwa chochote.
Lakini bool inawakilisha nini nilitoa kama alama ya kuangalia.
Ndiyo.
Hii ni mwisho wa kamba katika muundo huu data.
>> Na, bila shaka, nyota nodi kuna akimaanisha watoto.
Na kwa kweli, tu kama mti familia,
kufikiria nodes kuwa ni kunyongwa mbali
ya chini ya baadhi mzazi kipengele kuwa watoto.
Na hivyo watoto ni kwenda kuwa safu ya 27, moja 27
tu kuwa kwa apostrophe.
Tunakwenda aina ya kesi maalum kwamba.
Hivyo unaweza kuwa na baadhi ya majina na apostrophes.
Labda hata hyphen lazima kwenda huko, lakini utasikia
kuona katika p kuweka 5 sisi tu huduma kuhusu barua na apostrophes.
>> Na kisha jinsi ya kufanya wewe kuwakilisha data ya muundo yenyewe?
Jinsi gani unaweza kuwakilisha mizizi ya trie hii, ili kuzungumza?
Naam, tu kama na orodha wanaohusishwa, unaweza haja pointer kipengele kwanza.
Na trie wewe tu haja moja pointer mizizi ya trie hii.
Na kutoka huko unaweza hash njia yako chini zaidi na zaidi
kila nodi nyingine katika muundo.
Hivyo tu na unaweza hii sisi kuwakilisha kwamba struct.
>> Sasa Meanwhile-- Oh, swali.
>> Watazamaji: Nini bool neno?
>> DAVID Malan: Bool neno ni tu hii mwili C
ya kile ilivyoelezwa katika hii sanduku hapa, wakati
Mimi kuanza kugawanyika kila mambo vipande viwili safu ya.
Moja ni pointer nodi ijayo.
nyingine ina kuwa kitu kama sanduku hundi
kusema ndiyo, kuna neno Daven kwamba mwisho hapa,
kwa sababu hatutaki, kwa wakati huu, Dave.
>> Ingawa Dave ni kwenda kuwa na neno halali, yeye si katika trie
bado.
Na D ni neno.
Na D-A ni si neno au jina.
Hivyo alama hundi inaonyesha mara moja tu
kugonga nodi hii ni njia ya awali ya wahusika
kweli kamba kwamba umefanya kuingizwa.
Hivyo hiyo ni bool wote kuna ni kufanya kwa ajili yetu.
>> Maswali yoyote nyingine juu ya inajaribu?
Yeah.
>> Watazamaji: ni kuingiliana nini?
Nini kama una Dave na Daven?
DAVID Malan: Perfect.
Nini kama una Dave na Daven?
Hivyo kama sisi kuingiza, wanasema jina la utani, kwa David-- Dave-- D-A-V-E?
Hii ni kweli super rahisi.
Hivyo sisi ni kwenda tu kuchukua hatua nne.
D-A-V-E. Na nini nina kufanya mara moja mimi kugonga kwamba nodi ya nne?
Tu kwenda kuangalia.
Tuko tayari vizuri kwenda.
Kufanyika.
Hatua nne.
Wakati mara kwa mara asymptotically.
Na sasa tumekuwa zilionyesha kwamba wote Dave na Daven ni masharti katika muundo.
Hivyo si tatizo.
Na taarifa jinsi uwepo ya Daven hakuwa na kufanya hivyo
kuchukua wakati wowote zaidi au chini ya muda kwa ajili ya Dave na kinyume chake.
>> Hivyo kile kingine tunaweza sasa kufanya?
Tumekuwa alitumia mfano huu kabla ya trays anayewakilisha kitu.
Lakini zinageuka kuwa stack ya trays ni kweli
demonstrative ya mwingine data abstract type-- juu ya muundo data ngazi
kwamba mwishoni siku tu kama safu au orodha wanaohusishwa
au kitu zaidi mundane.
Lakini ni zaidi ya kuvutia dhana dhana.
stack, kama haya trays hapa katika Mather,
ujumla aitwaye tu that-- stack.
>> Na katika aina hii ya muundo data una mbili operations--
una mtu mmoja aitwaye kushinikiza kwa kuongeza kitu kwa stack,
kama kuweka tray mwingine nyuma juu ya stack.
Na kisha pop, ambayo ina maana kuchukua topmost tray mbali.
Lakini nini muhimu kuhusu stack ni kwamba ni got tabia hii curious.
Kama wafanyakazi dining ukumbi ni rearranging trays kwa ajili ya chakula ijayo,
nini kinaendelea kuwa kweli kuhusu jinsi wanafunzi
kuingiliana na muundo huu data?
Watazamaji: Wao wanaenda pop mbali moja.
DAVID Malan: Wao wanaenda pop mbali moja, hopefully juu.
Vinginevyo ni aina tu ya kijinga kwenda njia yote hadi chini.
Haki?
Muundo data si kweli kuruhusu wewe kunyakua tray chini angalau
urahisi.
Hivyo kuna hii curious mali kwa stack
kwamba bidhaa ya mwisho katika ni itakuwa kwanza moja nje.
Na wanasayansi wa kompyuta kuwaita hii LIFO-- mwisho katika, kwanza nje.
Na ni kweli haina kuwa kuvutia maombi.
Ni si lazima kama wazi kama baadhi wengine, lakini inaweza, kwa kweli, kuwa na manufaa,
na inaweza, kwa kweli, kutekelezwa katika michache ya njia tofauti.
>> Hivyo moja, na kwa kweli, basi mimi si kupiga mbizi katika hiyo.
Hebu kufanya hili badala.
Hebu tuangalie moja kwamba karibu wazo moja, lakini ni ya haki kidogo.
Haki?
Kama wewe ni mmoja wa wavulana hawa mashabiki au wasichana kwamba kweli anapenda bidhaa Apple
na wewe woke hadi saa 3:00 line up katika baadhi ya kuhifadhi
kupata latest sana iPhone, you anaweza kuwa foleni juu kama hii.
>> Sasa foleni makusudi sana jina.
Ni mstari kwa sababu kuna baadhi ya haki yake.
Haki?
Ingekuwa aina ya sucked kama wameweza got huko kwanza katika Hifadhi Apple
lakini wewe ni ufanisi bottommost tray kwa sababu wafanyakazi Apple basi
pop mtu wa mwisho ambaye kweli got katika mstari.
Hivyo mwingi na foleni, ingawa functionally wao ni aina ya same--
ni tu ukusanyaji hii rasilimali hiyo ni
kwenda kukua na shrink-- kuna hili suala haki yake,
angalau katika ulimwengu wa kweli, ambapo shughuli zoezi
ni tofauti kimsingi.
stack-- foleni rather-- alisema kuwa
shughuli mbili: n foleni na d foleni.
Au unaweza kuwaita idadi yoyote ya mambo.
Lakini unataka tu kukamata dhana kwamba moja ni kuongeza
na moja ni hatimaye subtracting.
>> Sasa chini ya Hood, wote stack na foleni inaweza kutekelezwa jinsi gani?
Sisi si kwenda katika kanuni za ni kwa sababu kiwango cha juu
wazo ni aina ya wazi zaidi.
I mean, nini binadamu kufanya do?
Kama mimi nina mtu wa kwanza katika Apple Kuhifadhi na hii ni mlango wa mbele,
unajua, mimi nina kwenda kusimama hapa.
Na mtu ujao kwenda kusimama hapa.
Hivyo kile muundo data imejikita kwenye foleni?
>> Watazamaji: foleni.
DAVID Malan: Sawa, foleni.
Uhakika.
Nini kingine?
>> Watazamaji: orodha wanaohusishwa.
>> DAVID Malan: wanaohusishwa orodha unaweza kutekeleza.
Na orodha wanaohusishwa ni nzuri kwa sababu kisha inaweza kukua kiholela muda mrefu kinyume
kwa kuwa baadhi ya simu za kudumu ya watu katika kuhifadhi.
Lakini labda idadi fasta ya maeneo ni halali.
Kwa sababu kama wao tu kama 20 iphone siku ya kwanza, labda
wao tu haja ya safu ya ukubwa 20 kwa kuwakilisha kwamba foleni, ambayo
ni tu kusema sasa mara moja sisi kuanza kuzungumza kuhusu hizi matatizo ngazi ya juu,
unaweza kutekeleza katika idadi yoyote ya njia.
Na kuna pengine tu kwenda kuwa biashara mbali katika nafasi na muda
au tu katika kanuni yako mwenyewe utata.
>> Nini kuhusu stack?
Naam, stack, tumeona pia inaweza tu kuwa trays haya.
Na unaweza kutekeleza hili safu.
Lakini katika baadhi ya uhakika kama wewe kutumia safu, nini kitatokea kwa trays
wewe ni kujaribu kuweka chini?
Wote haki.
Wewe kwenda tu kwa kuwa na uwezo wa kwenda juu mno.
Na nadhani katika Mather wao ni kweli recessed katika ufunguzi.
Hivyo kweli, ni karibu kama Mather ni kutumia
safu ya fasta ukubwa, kwa sababu unaweza tu
fit trays wengi katika ufunguzi katika ukuta chini chini ya magoti ya watu.
Na hivyo ambayo inaweza kuwa alisema kuwa safu,
lakini tunaweza shaka kutekeleza kwamba ujumla zaidi na orodha wanaohusishwa.
>> Naam, nini kuhusu mwingine muundo wa data?
Napenda kuvuta up moja nyingine Visual hapa.
Kitu kama jinsi kuhusu hili moja hapa?
Kwa nini huenda ni kuwa na manufaa kwa kuwa si kitu kama dhana kama trie, ambayo
tuliona alikuwa haya nodes pana sana, ambayo kila mmoja ni katika safu?
Lakini nini kama sisi kufanya kitu zaidi tu, kama zamani mti familia shule,
kila ambaye nodes hapa ni hifadhi ya idadi tu.
Badala ya jina au ukoo ni hifadhi ya idadi tu kama hii.
>> Naam, sisi kutumia jargon katika miundo data ni inajaribu wote
na miti, ambapo trie, tena, ni mtu ambaye nodes ni arrays tu,
bado nini huenda kutumia kutoka daraja ya shule
wakati alifanya familia majani tree-- na mizizi
ya mti na watoto wa mzazi na ndugu zake.
Na tuweze kutekeleza mti, kwa mfano, kama tu kama hii.
mti, ikiwa ni kama nodi, moja ya duru hizi kwamba ina idadi,
si kwenda kuwa na moja pointer, lakini mbili.
Na haraka kama wewe kuongeza pointer pili,
unaweza kweli sasa kufanya aina ya data mbili-dimensional
miundo katika kumbukumbu.
Kiasi kama mbili-dimensional safu, unaweza
kuwa na aina ya pande mbili orodha wanaohusishwa lakini wale
kwamba kufuata mfano ambapo hakuna mizunguko.
Ni kweli mti na moja grandparent njia ya juu hapa na kisha
baadhi ya wazazi na watoto na wajukuu na wajukuu kubwa.
na kadhalika.
>> Lakini nini nadhifu kweli kuhusu hili pia, tu tease wewe kwa kidogo ya kificho,
wanakumbuka recursion kutoka muda nyuma, ambapo
kuandika kazi kwamba wito yenyewe.
Hii ni fursa nzuri kutekeleza jambo
kama recursion, kwa sababu kufikiria hili.
>> Hii ni mti.
Na nimekuwa anal kidogo na jinsi Mimi kuweka integers katika mitaani.
Hivyo kiasi kwamba ina maalum name-- binary tafuta mti.
Sasa tumekuwa habari ya binary kutafuta, lakini unaweza
kazi nyuma kutoka jina Kitu huyu?
Ni mfano wa jinsi mimi nini kuingizwa integers katika mti huu?
Ni si holela.
Kuna baadhi ya muundo.
Yeah.
>> Watazamaji: Ndogo ndio upande wa kushoto.
>> DAVID Malan: Yeah.
Ndogo ndio ni upande wa kushoto.
Kubwa ndio ni juu ya haki.
Kama kwamba kauli ya kweli ni mzazi ni mkubwa kuliko mtoto wake wa kushoto,
lakini chini ya mtoto wake wa kulia.
Na kwamba peke yake ni hata kujirudia matusi ufafanuzi
kwa sababu unaweza kuomba kwamba mantiki hiyo kwa kila node
na tu bottoms nje, kesi ya msingi kama wewe
mapenzi, wakati hit moja ya majani, hivyo kusema,
ambapo idhini hana watoto zaidi.
>> Sasa jinsi gani unaweza kupata idadi 44?
Ungependa kuanza saa mizizi na kusema, hm.
55 si 44 Hivyo kufanya mimi nataka kwenda haki au kufanya mimi nataka kwenda kushoto?
Naam, ni wazi unataka kwenda kushoto.
Na hivyo ni kama simu kitabu mfano katika kutafuta binary
ujumla zaidi.
Lakini sisi ni kutekeleza hilo sasa zaidi kidogo dynamically
kuliko safu ili kuruhusu.
Na kwa kweli, kama unataka kuangalia katika kanuni, katika mtazamo wa kwanza uhakika.
Inaonekana kama rundo zima la mistari.
Lakini ni uzuri rahisi.
Kama unataka kutekeleza kazi aitwaye search ambao lengo katika maisha
ni kutafuta thamani kama n, integer,
na wewe ni kupita katika pointer-- moja pointer nodi ya mizizi,
badala yake, ya mti ambayo unaweza kupata kila kitu kingine,
taarifa jinsi straightforwardly unaweza kutekeleza mantiki.
Kama mti ni null, wazi ni huko.
Hebu tu kurudi uongo.
Haki?
Kama mkono ni kitu, kuna kitu huko.
>> Mwingine, kama n ni chini ya mti mshale n-- sasa mshale n,
kukumbuka sisi ilianzisha super ufupi siku nyingine,
na kwamba tu maana de-rejea pointer na kuangalia uwanja aitwaye n.
Hivyo ina maana kwenda huko na kuangalia uwanja aitwaye n.
Hivyo kama n, thamani wewe ni kupewa, ni chini kuliko thamani katika miti integer,
ambapo unataka kwenda?
Upande wa kushoto.
>> Hivyo taarifa recursion.
Mimi returning-- si kweli.
Si ya uongo.
Mimi kurudi chochote jibu ni kutoka wito kwa mwenyewe, kupita
n tena, ambayo ni kutokuwa na maana, lakini nini tofauti kidogo sasa?
Jinsi mimi kufanya tatizo kubwa?
Mimi kupita katika kama wa pili hoja, si mizizi ya mti,
lakini mtoto wa kushoto katika kesi hii.
Hivyo mimi nina kupita katika mtoto wa kushoto.
>> Wakati huo huo, kama n ni kubwa kuliko nodi Mimi sasa kuangalia,
Mimi kutafuta upande wa kulia.
Mwingine, kama mti si null, na kama kipengele si wa kushoto
na si kwa haki, nini ni ajabu kesi?
Tumekuwa kweli kupatikana nodi katika swali, na hivyo sisi kurudi kweli.
>> Hivyo tumekuwa tu scratched uso sasa baadhi ya miundo haya data.
Katika tatizo kuweka tano utasikia kuchunguza hizi bado zaidi,
na wewe utakuwa kupewa kubuni yako uchaguzi wa jinsi ya kwenda kuhusu hili.
Nini Ningependa kuhitimisha juu ya ni tu 30 teaser pili
ya nini watapata wiki ijayo na zaidi.
>> Kama sisi begin-- nashiriki waweza think-- mpito yetu polepole
kutoka katika ulimwengu wa C na chini maelezo ya utekelezaji ngazi,
kwa dunia ambayo tunaweza kuchukua kwa nafasi ya kuwa mtu mwingine ina hatimaye
kutekelezwa data haya miundo kwa ajili yetu,
na tutaweza kuanza kuelewa ulimwengu halisi ina maana ya kutekeleza
programu mtandao msingi na Nje ujumla zaidi
na pia usalama sana athari kwamba tumekuwa tu
wameanza scratch ya uso wa.
Hapa ni nini watapata sisi katika siku zijazo.
>> [Video avspelning]
>> Hapo akaja na ujumbe, na itifaki zake zote wenyewe.
Alikuja ulimwengu wa kikatili firewalls, asiyejali ruta,
na hatari mbaya zaidi kuliko kifo.
Yeye ni kufunga.
Yeye ni nguvu.
Yeye ni TCP / IP, na yeye got anwani yako.
"Wapiganaji wa Net."
[MWISHO video avspelning]
DAVID Malan: Coming wiki ijayo.
Tutaona wewe basi.
[Video avspelning]
-Na Sasa, "Mawazo Deep" na Daven Farnham.
-David Daima kuanza mihadhara na, "haki zote."
Nini, "Hapa ni ufumbuzi kuweka tatizo wiki hii "
au "Sisi ni kutoa nyote A?"
[Laughing]
[MWISHO video avspelning]