[Musika sa pag-play]
Tagapagsalita 1: Ang lahat ng karapatan.
Ang bawat tao'y maligayang pagdating pabalik sa seksyon.
Umaasa ako mo ang lahat ng mga matagumpay na nakuhang muli galing sa iyong pagsusulit
mula noong nakaraang linggo.
Alam ko ito nang kaunti mabaliw minsan.
Tulad ng sinasabi ko dati, kung ikaw ay sa loob ng karaniwang lihis,
hindi talaga mag-alala tungkol dito, lalo na para sa isang mas kumportable na seksyon.
Iyon ang tungkol sa kung saan mo na dapat.
>> Kung ginawa mo mahusay, pagkatapos ay kahanga-hanga.
Paggalang sa iyo.
At kung sa palagay mo bang kailangan mo Medyo sa karagdagang tulong, mangyaring
huwag mag-atubiling makipag-ugnay out sa alinman sa mga TFs.
Kami lahat dito upang makatulong.
>> Iyon ang dahilan kung bakit namin magturo.
Iyon ang dahilan kung bakit ako dito tuwing Lunes para sa iyo guys at sa tanggapan ng oras sa Huwebes.
Kaya mangyaring huwag mag-atubiling ipaalam sa akin kung ikaw ay nag-aalala tungkol sa anumang bagay
o kung mayroong anumang bagay sa pagsusulit na nais mo ba talagang i-matugunan.
>> Kaya ang agenda para sa araw ay ang lahat tungkol sa mga istraktura ng data.
Ang ilan sa mga ito ay lamang ng pagpunta sa maging lamang upang makakuha ka familiarized sa mga ito.
Maaari mong hindi kailanman ipatupad ang mga ito sa klase na ito.
Ang ilan sa kanila habilin sa iyo, tulad ng para sa iyong speller pset.
>> Magkakaroon ka ng iyong mga pagpipilian sa pagitan ng hash table at pagsubok.
Kaya makikita talagang kami ay pagpunta sa ibabaw ng mga iyon.
Ito ay magiging talagang higit pa sa mga uri ng isang mataas na antas ng seksyon ngayon, bagaman,
dahil mayroong maraming mga ito, at kung nagpunta kami sa mga detalye ng pagpapatupad
sa lahat ng mga ito, kami ng gagawin hindi kahit na makakuha sa pamamagitan ng naka-link na mga listahan
at marahil ng kaunting hash talahanayan.
>> Kaya makisama sa akin.
Hindi namin pagpunta sa ginagawa ng maraming coding oras na ito.
Kung mayroon kang anumang mga katanungan tungkol dito o gusto mong makita ito ipinatupad
o subukan ito sa iyong sarili, Ako siguradong inirerekumenda
pagpunta sa study.cs50.net, na May mga halimbawa ng lahat ng mga ito.
Magkakaroon ito ng aking PowerPoints sa mga tala na aming
ay may posibilidad na gamitin pati na rin ang ilang mga programming pagsasanay, lalo na para sa mga bagay
tulad ng naka-link na mga listahan at binary puno stack at mga pahiwatig.
Kaya kaunti pa mataas na antas, na Maaaring maging maganda para sa iyo guys.
>> Kaya sa na, magpapadala kami makapagsimula.
At din, yes-- pagsusulit.
Sa tingin ko ang karamihan sa iyo kung sino ang nasa ang aking mga seksyon ng iyong mga maikling pagsusulit,
ngunit sinuman ay sa o sa ilang mga dahilan kung bakit mo hindi, ang mga ito ay dito mismo sa harap.
>> Kaya naka-link na mga listahan.
Alam ko ang uri na ito ng pupunta upang i-back bago ang iyong pagsusulit.
Iyon ay ang linggo bago na natutunan namin tungkol dito.
Ngunit sa kasong ito, kami ay lamang pumunta Medyo mas malalalim na.
>> Kaya bakit maaari naming pumili ng isang listahan na naka-link sa isang array?
Ano Tinutukoy ang mga ito?
Oo?
>> Madla: Maaari mong palawakin ang isang naka-link ilista kumpara sa nakapirming laki ng array na.
Tagapagsalita 1: I-right.
Isang array ay naayos na laki samantalang ang isang naka-link na listahan ay may laki na variable.
Kaya kung hindi namin alam kung paano magkano ang gusto namin upang mag-imbak,
naka-link na listahan ay nagbibigay sa amin ng mahusay na paraan upang gawin iyon dahil kami maaari lamang
idagdag sa isa pang node at idagdag sa isa pang node at idagdag sa isa pang node.
Ngunit kung ano ang maaaring maging isang kalakalan-off?
Tandaan ang sinuman sa trade-off sa pagitan ng array at naka-link listahan?
Mmhmm?
>> Madla: Mayroon kang sa pumunta sa lahat ng mga paraan
sa pamamagitan ng naka-link na listahan makahanap ng isang elemento sa isang listahan.
Sa isang array, maaari mong hanapin lamang ang isang elemento.
>> Tagapagsalita 1: I-right.
Kaya sa arrays--
>> Madla: [hindi marinig].
>> Tagapagsalita 1: Sa array, mayroon kaming kung ano ang tinatawag na random na pag-access.
Nangangahulugan itong kung gusto namin kung ano ang kailanman ikalimang punto ng isang listahan
o ang ika-limang puntos sa aming mga array, maaari naming grab lamang ito.
Kung ito ay isang naka-link na listahan, mayroon kaming upang umulit sa pamamagitan ng, tama?
Kaya pag-access sa isang elemento sa isang array ay pare-pareho ang oras,
samantalang may naka-link na listahan ng gagawin ito pinaka-malamang na maging linear oras dahil siguro
ang aming elemento ay ang lahat ng mga paraan sa dulo.
Mayroon kaming upang maghanap sa lahat ng bagay.
Kaya sa lahat ng mga data na ito kaayusan kami ng pagpunta
na paggastos ng konting oras sa, ano ang mga plus at negatibo.
Kapag Maaaring gusto naming gamitin ang isa sa ibabaw ng iba pang?
At iyon ang uri ng mas malaking bagay na kumuha ang layo.
>> Kaya mayroon kaming dito ang kahulugan ng isang node.
Ito ay tulad ng isang elemento sa ang aming listahan na naka-link, i-right?
Kaya kami ay lahat ng mga pamilyar sa aming typedef structs,
kung saan nagpunta kami sa paglipas ng pagsusuri sa huling beses.
Ito ay isa lamang lamang paglikha isa pang uri ng data na maaaring naming gamitin.
>> At sa kasong ito, ito ang ilang node iyon ay hawak ng ilang integer in.
At pagkatapos ay kung ano ang ikalawang bahagi dito?
Sinuman?
>> Madla: [hindi marinig].
>> Tagapagsalita 1: Oo.
Ito ay isang pointer sa susunod na node.
Kaya ito ay dapat na tunay na maging up dito.
Ito ay isang pointer ng uri node sa susunod na bagay.
At iyon ang kung ano ang kanilang sumasaklaw sa aming mga node.
Ayos.
>> Ang lahat ng mga karapatan, kaya sa paghahanap, bilang namin lamang sinasabi bago banda, kung ikaw ay
pagpunta upang maghanap sa pamamagitan ng, mayroon kang upang aktwal na umulit
sa pamamagitan ng iyong listahan ng naka-link.
Kaya kung kaming naghahanap ng para sa bilang 9, gusto naming magsimula sa aming ulo
at na tumuturo sa amin sa simula sa aming mga naka-link na listahan, i-right?
At sabihin namin, OK, ginagawa ito node naglalaman ng mga numero ng 9?
Walang?
>> Ang lahat ng mga karapatan, pumunta sa susunod na isa.
Sundin ito.
Ito ay naglalaman ng mga numero ng 9?
Hindi.
Sundin ang mga susunod na isa.
>> Kaya mayroon kaming upang aktwal na umulit sa pamamagitan ng aming listahan na naka-link.
Hindi namin lamang pumunta nang direkta sa kung saan 9 ay.
At kung talagang nais mong guys sa makakita ng ilang palsipikado-code up doon.
Mayroon kaming ilang mga pag-andar ng paghahanap dito na tumatagal in-- kung ano ang aabutin sa?
Ano ang iyong palagay?
Kaya madaling isa.
Ano ito?
Madla: [hindi marinig].
Tagapagsalita 1: Ang dami kaming naghahanap ng para sa.
Mag-right?
At kung ano ay tumutugma ito sa?
Ito ay isang pointer sa?
>> Madla: Isang node.
>> Tagapagsalita 1: Isang node sa listahan na kaming naghahanap sa, i-right?
Kaya mayroon kaming ilang mga node ay pointer dito.
Ito ay isang punto na pupuntahan aktwal na umulit sa pamamagitan ng aming listahan.
Itinakda namin ito katumbas ng ilista dahil iyon lamang
pagtatakda dito katumbas ng simulan sa aming listahan na naka-link.
>> At habang hindi null, habang mayroon pa rin kaming mga bagay sa aming listahan,
suriin upang makita kung na node ay may ang bilang kaming naghahanap ng para sa.
Nagbabalik ng tunay.
Kung hindi man, i-update ito, i-right?
>> Kung ito ay walang bisa, lumabas namin ang aming habang loop at return false
dahil ibig sabihin nito ay hindi pa kami nakakahanap ito.
Lahat ng tao makakuha ba kung paano na gumagana?
OK.
>> Kaya may mga pagpapasok, mo May tatlong iba't ibang paraan.
Maaari mong i-prepend, maaari mong ikabit ang at maaari mong ipasok sa sari-sari.
Sa kasong ito, hindi namin pagpunta sa gawin ang isang i-prepend.
Sinuman Alam ba ng kung paano mga ay maaaring maiba tatlong mga kaso?
>> Kaya i-prepend nangangahulugan na inilagay mo ito sa harap ng iyong listahan.
Kaya na nangangahulugan na hindi mahalaga ano ang iyong mga node ay, hindi mahalaga
kung ano ang halaga ay, na iyong pupuntahan upang ilagay ito dito mismo sa harap, OK?
Ito ay pagpunta sa maging una sangkap sa iyong listahan.
>> Kung isama mo ito, ito ay pagpunta upang pumunta sa likod ng iyong listahan.
At ipasok sa sari-sari ibig sabihin ikaw ay pagpunta sa ilagay sa lugar na aktwal
kung saan ito ay nagpapanatili pinagsunod-sunod sa iyong listahan ng naka-link.
Muli, kung paano gamitin mo mga at kapag ginagamit mo ang
ang mga ito ay nag-iiba depende sa iyong kaso.
Kung hindi ito kailangang ay pinagsunod-sunod, i-prepend ay may gawi
upang maging kung ano ang karamihan ng mga tao gamitin dahil hindi mo
kailangang pumunta sa pamamagitan ng buong listahan upang mahanap ang dulo upang idagdag ito sa, i-right?
Maaari mong ilagay lang ito sa mismong.
>> Kaya magpapatuloy kami sa pamamagitan ng isang pagpapasok 1 ngayon.
Kaya isang bagay na pupuntahan ko lubos na inirerekomenda sa pset
ay upang gumuhit ng mga bagay out, tulad ng nakasanayan.
Napakahalaga na i-update ka ang iyong mga payo sa tamang pagkakasunod-sunod
dahil kung i-update mo ang mga ito bahagyang out sa pagkakasunud-sunod,
na iyong pupuntahan ay napupunta pagkawala ng mga bahagi ng iyong listahan.
>> Kaya halimbawa, sa kasong ito, hindi namin na nagsasabi sa pinuno sa punto lamang sa 1.
Kung gagawin lamang namin na walang pag-save ito ng 1,
wala kaming ideya kung ano ang 1 ay dapat tumuro sa ngayon
dahil nawalan kami kung ano ang ulo itinuturo sa.
Kaya isa bagay na dapat tandaan kapag gumawa ka ng isang i-prepend
ay upang i-save ang kung ano ang ulo punto upang una,
pagkatapos ay i-reassign ito, at pagkatapos ay i-update ano ang dapat tumuro sa iyong bagong node.
Sa kasong ito, ito ay isang paraan upang gawin ito.
>> Kaya kung tapos na kami ay ito sa ganitong paraan kung saan kami reassigned lang ulo,
mawalan kami talaga ang aming buong listahan, i-right?
Ang isang paraan upang gawin ito ay ang magkaroon ng 1 punto upang susunod na, at pagkatapos ay magkaroon ng ulo punto upang 1.
O maaari mong gawin uri ng tulad ng pansamantalang imbakan, na usapan ko ang tungkol.
>> Ngunit reassigning iyong mga payo sa tamang pagkakasunod-sunod
ay magiging napaka, napaka mahalaga para sa pset.
Kung hindi man, na iyong pupuntahan ay may hash talahanayan o isang try na lang magiging
lamang ng bahagi ng mga salita na gusto at pagkatapos ay you're-- mmhmm?
Madla: Ano ang pansamantalang storage bagay na iyong pinag-uusapan?
Tagapagsalita 1: Ang pansamantalang imbakan.
Kaya isa lamang ng isa pang paraan na maaari mong gawin ito
ay iimbak ang pinuno ng isang bagay, tulad ng iimbak ito ang pansamantalang variable.
Magtalaga ito sa 1 at pagkatapos ay i-update ang 1 upang tumuro
sa anumang ulo ginamit upang tumuro sa.
Sa paraang ito ay malinaw naman higit pa eleganteng dahil sa iyo
hindi na kailangan ng pansamantalang halaga, ngunit nag-aalok lamang ng isa pang paraan upang gawin ito.
At talagang namin ang mayroon ang ilang mga code para sa na ito.
Kaya para sa naka-link na listahan, namin aktwal na magkaroon ng ilang code.
Kaya ipasok dito, ito ay prepending.
Kaya ito ay pumasok ito sa ulo.
>> Kaya unang bagay, kailangan mong lumikha ng iyong bagong node, siyempre,
at suriin para sa null.
Palaging mabuti.
At pagkatapos ay kailangan mo upang magtalaga ng mga halaga.
Tuwing kang lumikha ng isang bagong node, mo hindi malaman kung ano ang nagtuturo sa susunod,
kaya gusto mong i-initialize ito sa null.
Kung ito ay nagtatapos up na tumuturo sa isang bagay tao, maipo-reassigned at ito ay multa.
Kung ito ang unang bagay sa listahan, kailangan nito
upang tumuro sa null dahil iyon ang katapusan ng listahan.
>> Kaya pagkatapos ay upang ipasok ito, makikita natin dito namin ay magtatalaga sa susunod na halaga ng aming mga node
upang maging anumang head ay, na kung saan ay kung ano ang namin ay may dito.
Iyon ay kung ano ang ginawa namin lamang.
At pagkatapos kami ay nagtatalaga ng ulo papunta sa puntong sa aming bagong node, dahil tandaan,
bagong ay ilang pointer sa isang node, at iyon mismo ang ulo ay.
Iyon ay eksakto kung bakit namin Mayroon na ito arrow accessor.
Cool?
Mmhmm?
>> Madla: Mayroon kaming pagsisimula ng bagong tabi ng unang null,
o maaari naming initialize lang ito sa magtungo?
>> Tagapagsalita 1: Bagong susunod Kailangang maging null upang magsimulang
dahil hindi mo alam kung saan ito magiging.
Gayundin, ito ay uri ng gusto lang tularan.
Itakda mo ito katumbas ng null upang gumawa lamang Siguraduhin na ang lahat ng iyong mga bases ay sakop
bago mo gawin ang anumang reassignment upang ang Palagi ka katiyakan na ito
ay nagtuturo sa isang tukoy na halaga kumpara tulad ng isang halaga ng basura.
Dahil, oo, magtalaga namin bagong susunod na awtomatiko,
ngunit higit pa tulad ng isang mahusay na kasanayan i-initialize ito
sa paraang iyon at pagkatapos ay i-reassign.
>> OK, kaya doble naka-link na mga listahan ngayon.
Ano ang palagay namin?
Ano ang naiiba sa doble naka-link na listahan?
>> Kaya sa aming mga listahan na naka-link, maaari naming ilipat lamang sa isa direksyon, i-right?
Mayroon susunod na lamang kami.
Maaari lamang kami pumunta pasulong.
>> Sa isang doble naka-link na listahan, Maaari din namin ilipat pabalik.
Kaya mayroon kaming hindi lamang ang numero na nais naming mag-imbak,
mayroon kaming kung saan ito tumuturo sa tabi at kung saan lamang kami nanggaling.
Kaya ito ay nagbibigay-daan para sa ilang mas mahusay na traversal.
>> Kaya doble naka-link node, halos katulad na, i-right?
Pagkakaiba lamang ay na namin ngayon May susunod at nakaraang.
Ito ay ang pagkakaiba lamang.
>> Kaya kung kami ay upang i-prepend o append-- namin walang anumang code para sa hanggang here--
ngunit kung ikaw ay upang subukan at ipasok ito, ang mga mahalagang bagay
ay kailangan mong gumawa ng mga sigurado ka sa pagtatalaga
pareho sa iyong nakaraang at ang iyong susunod na pointer tama.
Kaya sa kasong ito, nais mong hindi lamang simulan ang susunod,
initialize mo nakaraang.
Kung hindi namin sa ulo ng listahan, namin gagawin ulo katumbas bagong hindi lamang,
ngunit ang aming mga bagong dating dapat tumuturo sa ulo, tama?
>> Iyan ang pagkakaiba lamang.
At kung gusto mong higit pang mga kasanayan sa ang mga may naka-link na listahan, na may Pagpasok,
sa pagtanggal, na may insert sa isang sari-sari listahan,
mangyaring tingnan ang study.cs50.net.
Mayroong isang bungkos ng mahusay na pagsasanay.
Masidhing kong inirerekumenda ang mga ito.
Gusto ko namin ay may oras upang pumunta sa pamamagitan ng mga ito ngunit maraming mga istraktura ng data
upang makakuha ng sa pamamagitan ng.
>> OK, kaya hash talahanayan.
Ito ay malamang na ang karamihan kapaki-pakinabang na bit para sa iyong pset
dito dahil ka pagpunta sa maging pagpapatupad ng isa sa mga ito, o isang try.
Talagang gusto ko ng hash talahanayan.
Ang mga ito ay medyo cool.
>> Kaya kung ano talaga ang mangyayari ay isang hash talahanayan
ay kapag talagang kailangan naming mabilis pagpapasok ng, pagtanggal, at lookup.
Iyon ang mga bagay na hindi namin prioritizing sa isang hash table.
Maaari silang makakuha ng medyo malaki, ngunit bilang namin makita sa pagsubok,
may mga bagay na magkano ang mas malaking.
>> Ngunit talaga, ang lahat ng hash talahanayan ay isang hash
na nagsasabi sa iyo kung aling mga bucket upang ilagay ang bawat ng iyong data, bawat isa sa iyong mga elemento sa.
Ang isang simpleng paraan upang i-isip ng isang hash talahanayan ay tumutulong ito lamang bucket ng mga bagay,
tama?
Kaya kapag naka-uuri-uri ng mga bagay sa pamamagitan ng tulad ng unang titik ng kanilang pangalan,
na uri ng tulad ng isang hash talahanayan.
>> Kaya kung ako ay sa pangkat na iyong guys ay sa mga grupo ng kahit sino ay nagsisimula sa pangalan
may isang paglipas dito, o kung sinuman ang kaarawan Nasa Enero, Pebrero, Marso,
anumang, na epektibong paglikha ng isang hash table.
Ay lamang paglikha ito bucket na mong ayusin ang mga elemento sa
nang sa gayon ay maaari kang makahanap ng mas madali ang mga ito.
Kaya sa ganitong paraan kapag kailangan ko upang mahanap ang isa sa iyo,
Hindi ko na kailangang maghanap sa pamamagitan ng bawat isa sa iyong pangalan.
Maaari ko bang maging tulad ng, oh, alam ko na Kaarawan Danielle ay in--
Madla: --April.
Tagapagsalita 1: Abril.
Kaya tumingin ako sa aking Abril bucket, at sa sinumang swerte,
Makikita niya maging ang isa lamang doon at ang aking oras ay pare-pareho sa na-unawa,
samantalang kung mayroon akong upang tumingin sa pamamagitan ng isang buong bungkos ng mga tao,
ito ay pagpunta sa tumagal ng mas matagal.
Kaya hash talahanayan ay talagang lamang bucket.
Madaling paraan upang isipin ang mga ito.
>> Kaya isang napaka-mahalagang bagay tungkol sa isang hash talahanayan ay isang hash.
Kaya ang mga bagay lamang usapan ko, tulad ng ang iyong unang titik ng iyong unang pangalan
o ang iyong mga buwan petsa ng kapanganakan, ang mga ito ay mga ideya na
talagang kaugnayan sa isang hash.
Ito ay lamang ng isang paraan ng pagpapasya kung aling mga Bucket ka elemento napupunta sa, OK?
Kaya para sa pset, maaari kang tumingin up halos anumang hash na gusto mo.
>> Hindi na kailangang maging ang iyong sariling.
Mayroong ilang mga talagang cool na mga out doon na gawin ang lahat ng uri ng mga nakatutuwang matematika.
At kung nais mong gumawa ng iyong napakabilis na spellchecker,
Gagawin ko talaga tumingin sa isa sa mga iyon.
>> Ngunit may mga din ang simpleng na, tulad ng tayahin
ang kabuuan ng salita, tulad ng bawat titik na may isang numero.
I-compute ang kabuuan.
Na tumutukoy sa bucket.
Mayroon din nila ang mga madaling mga iyon ay tulad lang ng lahat ng mga A dito,
lahat ng mga B meron dito.
Anumang isa sa mga iyon.
>> Talaga, sinasabi lang ito sa iyo kung aling array index ay dapat pumunta sa iyong elemento.
Pagpapasya lamang ang bucket-- lahat ng ito ay isang hash ay.
Kaya dito mayroon kaming isang halimbawa kung saan ay lang ang unang titik ng string
na ako ay pakikipag-usap lamang tungkol.
>> Kaya mayroon kang ilang mga hash na lang ang unang titik ng iyong string minus A,
na kung saan ay magbibigay sa iyo ng ilang mga numero sa pagitan ng 0 at 25.
At ano ang gusto mong gawin ay tiyakin na ito ay kumakatawan sa
sa laki ng iyong hash table-- kung gaano karaming mga bucket mayroong.
Sa marami sa mga hash function, ang mga ito ay
pagpunta na bumabalik na halaga na maaari maging malayo sa itaas ng mga numero ng mga bucket
na iyong aktwal na mayroon sa iyong talahanayan ng hash,
kaya kailangan mong gumawa ng mga Tiyaking at mod sa pamamagitan ng mga iyon.
Kung hindi man, ito ay pagpunta sa sabihin, naku, dapat itong maging sa bucket 5,000
ngunit mayroon 30 ka lang mga bucket sa iyong talahanayan ng hash.
At siyempre, namin ang lahat ng alam na pagpunta sa magresulta sa ilang mga nakatutuwang mga error.
Kaya tiyaking i-mod ng laki ng iyong talahanayan ng hash.
Ayos.
Kaya collisions.
Mabuti ay lahat ng tao sa ngayon?
Mmhmm?
>> Madla: Bakit gagawin ito bumalik tulad ng napakalaking halaga?
>> Tagapagsalita 1: Depende sa mga algorithm na ang iyong hash gumagamit.
Ang ilan sa kanila ay gawin basag ang pula pagpaparami.
At lahat ng ito ay tungkol sa pagkuha ng isang pantay na pamamahagi,
kaya ginagawa nila ang ilang mga talagang minsan na nakatutuwang bagay.
Iyon lang.
Ano pa?
OK.
>> Kaya collisions.
Talaga, tulad ng mga naunang sinabi ko, sa pinakamahusay na sitwasyon kaso,
anumang mga bucket tumingin ako sa ay pagpunta sa magkaroon ng isang bagay,
kaya wala akong upang tumingin sa lahat, tama?
Ako alinman alam ito doon o ito Hindi, at iyon ang kung ano ang namin talagang gusto.
Ngunit kung mayroon kaming libu-libong mga data point at mas mababa sa numero na
ng mga bucket, kami ay pagpunta sa may collisions kung saan huli ay isang bagay na
ay pagpunta sa may upang tapusin up sa isang bucket na mayroon isang elemento.
>> Kaya ang tanong ay, kung ano ang huwag namin gawin sa kasong iyon?
Ano ang naming gawin?
Kami ay mayroon ng isang bagay doon?
Huwag magtapon namin lamang ito?
>> Hindi.
Mayroon kaming upang panatilihing pareho sa mga ito.
Kaya ang paraan na aming Karaniwang gawin iyon ay kung ano?
Ano ang istraktura ng data usapan lang namin tungkol sa?
Madla: Naka-link na listahan.
Tagapagsalita 1: Isang naka-link na listahan.
Kaya ngayon, sa halip na bawat isa sa mga mga bucket lamang pagkakaroon ng isang elemento,
ito ay pagpunta sa maglaman ng isang naka-link na listahan ng mga ang mga elemento na-hash na ito.
OK, ang lahat uri ng makakuha na ideya?
Dahil hindi namin maaaring magkaroon ng isang array dahil hindi namin alam kung gaano karaming mga bagay
ay magiging doon.
Ay nagbibigay-daan sa amin ang isang naka-link na listahan upang Mayroon lamang ang eksaktong numero na
ay na-hash na sa bucket, tama?
>> Kaya linear probing ay talaga ito idea--
ito ay isang paraan upang harapin ang isang banggaan.
Ano ang maaari mong gawin ay kung, sa kaso, isang itlog ng isda ay na-hash sa 1
at kami ay mayroon ng isang bagay doon, lamang sa iyo
panatilihin ang pagpunta pababa hanggang sa mahanap ka ng isang walang laman na slot.
Iyon ay isang paraan upang mahawakan ito.
Ang iba pang mga paraan upang mahawakan ito ay may kung ano ang namin lamang
called-- sa naka-link listahan ay tinatawag na chaining.
>> Kaya gumagana sa ideya na ito kung sa iyong talahanayan ng hash sa tingin mo
ay mas malaki kaysa ang iyong data set o kung
gusto mong subukan at i-minimize chaining hanggang sa ito ay talagang kinakailangan.
Kaya ang isang bagay ay linear probing malinaw naman ay nangangahulugan
na ang iyong mga hash ay hindi masyadong kapaki-pakinabang
dahil ka pagpunta sa mga end up gamit ang iyong hash, nakakakuha sa isang punto,
linear mong suriin pababa sa ang ilang mga lugar na iyon ay magagamit.
Ngunit ngayon, siyempre, kahit ano tao na nagtatapos up doon,
ka ng pagpunta sa mayroon sa maghanap ng kahit na sa mas ibaba pa.
>> At maraming higit pa gastos sa paghahanap na
Naging inputting isang elemento sa iyong talahanayan ng hash ngayon, tama?
At ngayon kapag kang pumunta at subukan at maghanap ng isang itlog ng isda muli, na iyong pupuntahan hash ito,
at ito ay pagpunta sa sabihin, oh, tumingin sa bucket 1,
at ito ay hindi magiging sa bucket 1, kaya ikaw ay
pagpunta sa may upang tumawid sa pamamagitan ng natitirang bahagi ng mga ito.
Kaya minsan ito ay kapaki-pakinabang, ngunit sa karamihan ng mga kaso,
kami ay pagpunta sa sabihin na chaining ay kung ano ang gusto mong gawin.
>> Kaya usapan natin ang tungkol na ito nang mas maaga.
Nakakuha ako ng isang maliit na mas maaga sa kanilang sarili ko.
Ngunit chaining ay isa na sa bawat bucket sa iyong talahanayan ng hash
lamang ang naka-link na listahan.
>> Kaya isa pang paraan, o mga teknikal na paraan, mag-isip ng isang hash talahanayan
ay tumutulong ito lamang ay isang array ng naka-link na mga listahan, na
kapag sumusulat ka sa iyong diksyunaryo at sinusubukan mong i-load ito,
iniisip ito bilang isang hanay ng mga naka-link na mga listahan
Gagawing mas madali para sa iyo na simulan ang.
>> Madla: Kaya hash talahanayan May isang paunang natukoy na laki,
tulad ng isang [hindi marinig] ng mga bucket?
>> Tagapagsalita 1: I-right.
Kaya ito ay may isang hanay na bilang ng mga mga bucket na determine-- mo
kung saan mo guys dapat huwag mag-atubiling i-play sa.
Maaari itong maging medyo cool upang makita kung ano ang mangyayari
bilang baguhin mo ang iyong numero ng mga bucket.
Ngunit oo, ito ay may itakda ang numero ng mga bucket.
Ano ay nagbibigay-daan sa iyo upang magkasya bilang maraming mga sangkap na kailangan mo
ay ang nakahiwalay na chaining kung saan mo na mga listahan na naka-link sa bawat bucket.
Iyon ay nangangahulugang ang iyong talahanayan ng hash ay eksakto ang laki
na kakailanganin mo ito upang maging, tama?
Iyan ang buong punto ng naka-link na mga listahan.
Ayos.
>> Kaya OK lahat doon?
Lahat ng karapatan.
Ah.
Ano lamang ang nangyari?
Talagang ngayon.
Hulaan ang isang tao ay pagpatay sa akin.
>> OK kami ng pagpunta sa pumunta sa pagsubok, na kung saan ay isang maliit na mabaliw.
Gusto ko ng hash talahanayan.
Sa tingin ko ang mga ito ay talagang cool.
Pagsubok ay cool na, masyadong.
>> Kaya ang sinuman tandaan kung ano ang isang try ay?
Dapat mo na nawala na sa paglipas ng ito sa madaling sabi sa aralin?
Tandaan mo ba ang uri ng kung paano ito gumagana?
Madla: lamang ako nodding na namin pumunta sa paglipas ng ito.
Tagapagsalita 1: namin pumunta sa paglipas ng ito.
OK, talagang kami ng pagpunta sa pumunta sa paglipas dito ngayon ay kung ano ang sinasabi namin.
>> Madla: Iyon ay para sa isang punong kahoy na pagbawi.
>> Tagapagsalita 1: Oo.
Ito ay isang punong kahoy na pagbawi.
Kahanga-hanga.
Kaya isang bagay na mapansin dito ay na namin ay tumitingin sa indibidwal na mga character
dito, tama?
>> Kaya bago sa aming hash, namin ay tumitingin sa mga salita bilang isang buo,
at ngayon naghahanap kami ng higit pa sa mga character, tama?
Kaya mayroon kaming Maxwell sa paglipas dito at Mendel.
Kaya isa lamang try-- isang paraan upang tingin tungkol sa ito ay na ang bawat antas dito
ay isang hanay ng mga titik.
Kaya ito ay ang iyong root node dito, tama?
Ito ay ang lahat ng mga character ng alpabeto para sa simula ng bawat salita.
>> At ano ang gusto mong gawin ay sabihin nating, OK, mayroon kaming ilang mga M salita.
Kami ay pagpunta sa hitsura para sa Maxwell, kaya pumunta kami sa M. At M punto sa kabuuan
iba pang isang array kung saan ang bawat salita, hangga't mayroong
ay isang salita na may isang bilang ikalawang sulat,
hangga't mayroong isang salita na May B bilang ikalawang sulat,
magkakaroon ito ng pointer pagpunta sa ilang mga susunod na array.
>> May malamang na hindi salita na MP ang isang bagay,
kaya sa posisyon P sa array, magiging walang bisa lamang.
Ito ay sabihin, OK, walang salita na M sinusundan ng isang P, OK?
Kaya kung sa tingin namin tungkol dito, ang bawat isa ang isa sa mga mas maliliit na bagay
ay talagang isa sa mga malaking array mula sa isang sa pamamagitan ng Z.
Kaya kung ano ang maaaring maging isa sa mga bagay na uri ng isang sagabal ng isang subukan?
>> Madla: Isang maraming memory.
>> Tagapagsalita 1: Ito ay isang tonelada ng memorya, i-right?
Ang bawat isa sa mga bloke dito kumakatawan sa 26 mga puwang, 26 element ng array.
Kaya pagsusubok na makakuha ng mga hindi kapani-paniwalang espasyo mabigat.
>> Ngunit ay napakabilis nila.
Kaya hindi mapaniniwalaan o kapani-paniwala mabilis pero talagang hindi mabisa espasyo.
Uri ng kailangang malaman kung alin ang gusto mo.
Ang mga ito ay talagang cool na para sa iyong pset, ngunit ginagawa nila tumagal ng hanggang ng maraming memorya,
kaya Trade-off mo.
Oo?
>> Madla: Gusto posible -set up ng try at pagkatapos ay
sa sandaling mayroon ka ng lahat ng data sa loob nito na need-- mo
Hindi ko alam kung na saysay.
Nagsisimula ako ay mapupuksa ng lahat ng mga Null character, ngunit pagkatapos ay
hindi mo magagawang i-index them--
>> Tagapagsalita 1: Kailangan mo pa rin ang mga ito.
>> Madla: - sa parehong paraan sa bawat oras.
Tagapagsalita 1: Oo.
Kailangan mo ang null na character upang ipaalam alam mo kung mayroong hindi isang salita doon.
Ben ay mayroon kang isang bagay na gusto mo?
OK.
Ang lahat ng mga karapatan, kaya kami ay pagpunta upang pumunta nang kaunti nang higit pa
sa mga teknikal na detalye sa likod ng isang subukan at gumagana sa pamamagitan ng isang halimbawa.
>> OK, kaya ito ay ang parehong bagay.
Sapagkat sa isang naka-link na listahan, ang aming pangunahing uri of-- ano ang salita na gusto ko? -
tulad ng pagbuo bloke ay isang node.
Sa isang try, mayroon din kami ng isang node, ngunit ito ay tinukoy sa ibang paraan.
>> Kaya mayroon kaming ilang bool na Kinakatawan kung ang isang salita talaga
nang nasa lokasyong ito, at pagkatapos ay mayroon kaming ilang mga array here-- o sa halip,
ito ay isang pointer sa isang array ng 27 mga character.
At ito ay para sa, sa kasong ito, ito 27-- ako na ang lahat ng sa iyo ay tulad, maghintay,
may 26 titik sa alpabeto.
Bakit mayroon kaming 27?
>> Kaya depende sa paraan mong ipatupad ito,
ito ay mula sa isang pset na pinapayagan para sa kudlit.
Kaya na ang dahilan kung bakit ang mga extrang isa.
Magkakaroon ka rin sa ilang kaso ang null Terminator
ay kasama bilang isa sa mga mga character na ito ay pinapahintulutan upang maging,
at iyon ang kung paano sila suriin upang makita kung ito ay sa dulo ng salita.
Kung interesado ka, tingnan ang Video Kevin sa study.cs50,
pati na rin ang Wikipedia ay ang ilang mga mahusay na mga mapagkukunan doon.
>> Ngunit kami ay pagpunta sa pumunta sa pamamagitan ng uri lamang ng kung paano mo maaaring gumana sa pamamagitan ng isang try
kung bibigyan ka ng isa.
Kaya mayroon kaming isang napaka-simpleng isa dito na May mga salitang "bat" at "pag-zoom" sa kanila.
At tulad ng nakikita namin dito, ang maliit na espasyo dito
Kinakatawan ng aming bool na sabi, oo, ito ay isang salita.
At pagkatapos na ito ay ang aming array ng mga character, tama?
>> Kaya kami ay pagpunta sa pumunta sa pamamagitan ng paghahanap ng "bat" sa try.
Kaya magsimula sa itaas, tama?
At alam namin na b tumutugon sa ang pangalawang index, ang pangalawang elemento
sa array, dahil ang isang at b.
Kaya humigit-kumulang sa ikalawang isa.
>> At sinasabi nito, OK, cool, sundin na sa sa susunod na array, dahil kung tandaan namin,
hindi ito ang bawat isa sa mga aktwal na naglalaman ng mga elemento.
Ang bawat isa sa mga array ay naglalaman ng isang pointer, tama?
Ito ay isang mahalagang pagkakaiba upang gumawa.
>> Alam ko na ito ay pagpunta sa be-- pagsubok ay talagang mahirap upang makakuha ng sa unang pagkakataon,
kaya kahit na ito ay ang pangalawa o pangatlong beses
at ito ay uri pa rin ng tila mahirap,
Nangangako ako kung pumunta ka sa panonood ang maikling muli bukas,
Makikita ito marahil gumawa ng maraming higit pang mga kahulugan.
Inaabot ng maraming upang digest.
Ako minsan am pa rin tulad ng, maghintay, ano ay isang try?
Paano ko gagamitin ito?
>> Kaya namin b sa kasong ito, na kung saan ay ang aming ikalawang index.
Kung nagkaroon kami, sabihin nating, c o d o anumang iba pang sulat,
kailangan namin upang i-map na bumalik sa index sa aming mga array na na tumutugon sa.
Kaya gusto naming maglaan tulad ng rchar at kami lamang ibawas-off ang isang upang i-map ito sa 0-25.
Bawat tao magandang kung paano namin -map ang aming mga character?
OK.
>> Kaya pumunta kami sa ikalawang isa at kami makita na, oo, ito ay hindi na wasto.
Maaari naming lumipat sa susunod na ito array.
Kaya pumunta kami sa sa susunod na array dito.
>> At sabihin namin, OK, ngayon namin Kailangan upang makita kung ang isang ay dito.
Null ay A o ang ginagawa nito aktwal na sumulong?
Kaya isang aktwal na gumagalaw ipasa sa array.
At sabihin namin, OK, hindi ang ating huling titik.
Kaya pumunta kami sa t sa index.
At pagkatapos ay ilipat naming inaabangan ang panahon dahil mayroong isa pa.
At ang isang ito talaga sabi na, oo, sinasabi nito na mayroong isang salita here--
na kung mong sundin ito landas, dumating ka pa
sa isang salita, na alam namin ay "bat."
Oo?
>> Madla: ba ito standard na magkaroon na bilang index ng 0 at pagkatapos ay magkaroon ng isang pag-uuri sa 1
o magkaroon ng sa dulo?
>> Tagapagsalita 1: Hindi.
Kaya't kung tiningnan namin pabalik sa aming mga pagpapahayag dito, ito ay isang bool,
kaya sarili nitong sangkap sa iyong node.
Kaya ito ay hindi bahagi ng array.
Ayos.
Kaya kapag tapos na kami sa aming mga salita at nagpapaumanhin kami sa ito array, kung ano ang gusto naming gawin
ay gawin ang isang tseke para ay ito isang salita.
At sa kasong ito, ito ay bumalik yes.
>> Kaya sa na tala, alam namin na "zoo" - alam namin bilang mga tao na "zoo" ay isang salita,
tama?
Ngunit subukan dito ay sabihin, hindi, hindi.
At gusto itong sabihin na dahil namin hindi itinalaga ito bilang isang salita dito.
Kahit na maaari naming bagtasin sa pamamagitan ng sa array,
ito try ang sasabihin iyon, hindi, zoo ay wala sa iyong diksyunaryo
dahil mayroon kaming hindi itinalaga ito bilang tulad.
>> Kaya isang paraan upang gawin that-- naku, paumanhin, ang isang ito.
Kaya sa kasong ito, "zoo" ay hindi isang salita, ngunit ito ay nasa aming try.
Ngunit sa isang ito, sabihin natin na gusto namin ito ipakilala ang salitang "bath," kung ano ang mangyayari
ay sinusunod namin ang through-- b, a, t.
Humihingi kami sa array, at pumunta kami upang maghanap para sa h.
>> Sa kasong ito, kapag namin tingnan ang pointer h,
ito ay tumuturo sa null, OK?
Kaya maliban kung ito ay hayagang na tumuturo sa isa pang array,
ipagpalagay mo na ang lahat ng mga payo sa array ay tumuturo sa null.
Kaya sa kasong ito, h nakaturo sa null kaya't hindi natin kailangang gawin,
kaya ito ay bumalik din false, "bath" ay hindi in dito.
Kaya ngayon kami ay talagang pagpunta sa pumunta sa pamamagitan ng
kung paano namin talagang sabihin na "zoo" ay nasa aming try.
Paano kami magpasok ng "zoo" sa aming try?
Kaya sa parehong paraan na aming pagsisimula sa ang aming listahan na naka-link, sisimulan namin sa root.
Kapag may pagdududa, magsimula sa ang root ng mga bagay na ito.
>> At kami sabihin, OK, z.
z umiiral sa ito, at ginagawa nito.
Kaya nagpapalipat-lipat ka sa sa ang inyong susunod na array, OK?
At pagkatapos ay sa susunod na isa, sabihin namin, OK, umiiral o?
Ginagawa nito.
Ito muli.
>> At kaya sa aming susunod na isa, na sinabi namin, OK, "zoo" Umiiral dito.
Lahat ng kailangan naming gawin ay itakda ito katumbas sa totoo, na may isang salita doon.
Kung si sinundan ang lahat ng bagay hanggang sa bago sa puntong iyon,
ito ay isang salita, kaya lamang itakda ito katumbas ng tulad.
Oo?
>> Madla: ang Kaya pagkatapos na nangangahulugan na "BA" ay salita rin?
>> Tagapagsalita 1: Hindi.
Kaya sa kasong ito, ang "BA" naming makakuha ng dito, gusto naming sabihin ay ito ang isang salita,
at ito ay pa rin walang.
OK?
Mmhmm?
>> Madla: Kaya sa sandaling ito ng salita at sabihin ninyo ang oo, pagkatapos ito
Maglalaman upang pumunta sa m?
>> Tagapagsalita 1: Kaya ito ay may upang gawin with-- ka sa paglo-load ito sa.
Sinabi mo ang "zoo" ay salita.
Kapag pumunta ka sa check-- tulad ng, sabihin nating nais mong sabihin,
ang "zoo" umiiral sa diksyunaryo ito?
Ka lamang ng pagpunta sa paghahanap para sa "zoo," at pagkatapos ay suriin upang makita kung ito ay isang salita.
Hindi ka pagpunta sa ilipat sa pamamagitan ng m dahil hindi iyon
kung ano ang iyong hinahanap.
>> Kaya kung talagang namin nais na idagdag ang "bath" sa ito try,
Gusto naming gawin ang parehong bagay tulad ng ginawa namin sa "zoo,"
maliban gusto naming makita na kapag namin subukan at makapunta sa h, ito ay hindi umiiral.
Kaya maaari mong isipin na ito bilang pagsubok upang magdagdag ng bagong node sa isang naka-link na listahan,
kaya gusto naming kailangan upang magdagdag ng isa pang ang isa sa mga array, tulad ng sa gayon.
At pagkatapos ay kung ano ang namin ang naka-set lang namin ang h elemento ng array na tumuturo sa ito.
>> At pagkatapos ay kung ano ang gusto naming gawin dito?
Idagdag ito katumbas ng totoo dahil ito ay isang salita.
Ayos.
Alam ko.
Pagsubok ay hindi ang pinaka-kapana-panabik.
Pagkatiwalaan sa akin, alam ko.
>> Kaya isang bagay upang mapagtanto na may pagsubok, Sinabi ko, ang mga ito ay napaka-epektibo.
Kaya nakita namin ang mga ito tumagal nang hanggang isang tonelada ng espasyo.
Ang mga ito ay uri ng nakalilito.
Kaya bakit namin kailanman gamitin ang mga ito?
Ginagamit namin ang mga dahil ang mga ito ay hindi mapaniniwalaan o kapani-paniwala mahusay.
>> Kaya kung sakaling ang iyong hinahanap up ng isang salita, ikaw lamang
bounded sa pamamagitan ng haba ng salita.
Kaya kung naghahanap ka para sa isang salita na haba ng limang,
ka kailanman lamang ng pagpunta sa mayroon sa gumawa ng hindi hihigit sa limang mga paghahambing, OK?
Kaya ginagawang ito isa lamang pare-pareho.
Tulad ng pagpapasok at lookup ay isa lamang pare-pareho ang oras.
>> Kaya kung maaari kang makakuha ng kailanman isang bagay sa pare-pareho ang oras,
na kasing ganda ng ito ay nakakakuha.
Hindi ka maaaring makakuha ng mas mahusay kaysa sa pare-pareho ang oras para sa mga bagay na ito.
Kaya na ay isa sa mga malaking plus ng pagsubok.
>> Ngunit ito ay isang maraming espasyo.
Kaya mo uri ng kailangang magpasya kung ano ang mas mahalaga sa iyo.
At sa mga computer ngayon, ang puwang na iyon ng try maaaring tumagal ng hanggang
siguro ay hindi nakakaapekto sa iyo na magkano, ngunit marahil
ka pagharap sa isang bagay na may malayo, malayo higit pang mga bagay,
at isang try lang ay hindi makatwirang.
Oo?
>> Madla: Maghintay, kaya mayroon kang 26 mga titik sa bawat solong isa?
>> Tagapagsalita 1: Mmhmm.
Oo, mayroon kang 26.
Mayroon kang ilang mga marker ay salita at pagkatapos ay mayroon kang 26 na pointer sa bawat isa.
At sila ay point--
>> Madla: At sa bawat 26, ang mga ito ay may 26?
>> Tagapagsalita 1: Oo.
At iyon ang dahilan kung bakit, bilang maaari mong makita, ito ang lilitaw pa masyadong mabilis.
Lahat ng karapatan.
Kaya kami ay pagpunta upang makakuha ng sa mga puno, na Sa palagay ko ay mas madali at magpo marahil
maging isang magandang maliit na ipagpaliban ang pagbitay mula sa pagsubok doon.
Kaya sana karamihan sa iyo nakakita ng isang puno bago.
Hindi gusto ng mga kaakit-akit mga nasa labas, na aking
hindi alam kung sinuman nagpunta labas kamakailan.
Nagpunta ako sa pagpili ng mansanas na ito katapusan ng linggo, at oh aking sus, ito ay maganda.
Hindi ko alam kung dahon maaaring tumingin na kaakit-akit.
>> Kaya ito ay isang puno lamang, tama?
Ito ay ilan lang na node, at ito tumuturo sa isang bungkos ng iba pang mga node.
Tulad ng iyong nakikita dito, ito ay uri ng isang umuulit na tema.
Node pagturo sa node ay uri ng ang kakanyahan ng maraming mga istraktura ng data.
Depende lang ito sa kung paano namin Mayroon ituro ang mga ito sa isa't isa
at kung paano namin tumawid sa pamamagitan ng mga ito at kung paano namin
magpasok ng mga bagay na tinutukoy ang kanilang mga iba't ibang mga katangian.
>> Kaya ilan lang terminolohiya, na ginagamit ko na dati.
Kaya ugat ay anumang ay nasa tuktok napaka.
ito ay kung saan palagi naming magsimula.
Maaari mong isipin na ito bilang pinuno rin.
Ngunit para sa mga puno, may posibilidad namin upang sumangguni sa ito bilang root.
>> Anumang bagay sa ilalim here-- sa pinakadulo, napaka-bottom--
ay itinuturing na dahon.
Kaya mangyaring hindi kasama ang buong puno bagay, tama?
Dahon ay nasa gilid ng iyong tree.
>> At pagkatapos ay mayroon din kami ng ilang mga mga termino upang makipag-usap tungkol sa mga node na may kaugnayan
sa isa't isa.
Kaya mayroon kaming magulang, mga anak, at kapatid.
Kaya sa kasong ito, 3 ay ang magulang ng 5, 6, at 7.
Kaya ang magulang ay anumang ay isang hakbang sa itaas ng kahit anupamang ikaw ay
nagre-refer sa, kaya lamang tulad ng isang pamilya tree.
Sana, ito ay ang lahat ng kaunti bit mas magaling kaysa sa pagsubok.
>> Kapatid ay ang anuman na mayroon ang parehong magulang, tama?
Ang mga ito ay nasa parehong antas dito.
At pagkatapos, bilang ako ay sinasabi, ang mga bata ay lamang
anumang ay isang hakbang sa ibaba ang node na pinag-uusapan, OK?
Ayos.
Kaya isang binary tree.
Maaari sinuman Hazard ng hula sa isa sa ang mga katangian ng binary puno?
>> Madla: Max dalawang dahon.
>> Tagapagsalita 1: I-right.
Kaya max ng dalawang dahon.
Kaya sa isang ito bago, nagkaroon kami ng isang ito na nagkaroon ng tatlong, ngunit sa isang binary puno,
mayroon kang isang max ng dalawang mga bata sa bawat magulang, tama?
Mayroong isa pang kagiliw-giliw na katangian.
Sinuman Alam ba iyon?
Binary tree.
>> Kaya isang binary puno ay magkakaroon ng lahat ng bagay sa the-- ang isang ito ay hindi sorted--
ngunit sa isang pinagsunod-sunod binary tree, lahat ng bagay sa kanan
ay mas malaki sa magulang, at lahat ng nasa kaliwa
ay mas mababa sa magulang.
At iyon ay isang pagsusulit tanong bago, kaya magandang malaman.
Kaya ang paraan tukuyin namin ito, muli, mayroon kaming isa pang node.
Ito ay mukhang katulad na katulad sa kung ano?
Doble
>> Madla: Naka-link na mga listahan
>> Tagapagsalita 1: Isang double naka-link na listahan, i-right?
Kaya kung papalitan namin ito sa nakaraan at susunod,
ito ay magiging isang doble naka-link na listahan.
Ngunit sa kasong ito, kami talaga Mayroon pakaliwa at pakanan at iyon ito.
Kung hindi man, ito ay eksaktong kapareho.
Mayroon pa kaming mga elemento hinahanap mo,
at mayroon kang lamang ng dalawang mga payo pagpunta sa kahit anong susunod.
Oo, kaya binary paghahanap tree.
Kung napansin namin, lahat ng bagay sa dito mismo ay mas malaki than--
o lahat agad sa kanan dito
ay mas malaki kaysa sa, lahat ng bagay dito ay mas mababa.
>> Kaya kung kami ay upang maghanap sa pamamagitan ng, ito dapat mukhang masyado nang malapit sa binary paghahanap
dito, tama?
Maliban sa halip na naghahanap sa kalahati ng array,
kami ay lamang ng pagtingin sa alinman sa kaliwa gilid o sa kanang bahagi ng tree.
Kaya ito ay nakakakuha ng kaunti mas simple, sa tingin ko.
>> Kaya kung ang iyong mga ugat ay null, Malinaw na ito ay hindi totoo lang.
At kung ito ay doon, malinaw naman ito totoo.
Kung ito ay mas mababa, maghanap namin sa kaliwa.
Kung ito ay mas malaki kaysa sa, maghanap namin ang karapatan.
Ito ay eksakto tulad ng binary paghahanap, lamang ng ibang istraktura ng data
na ginagamit namin.
Sa halip na isang array, ito lamang ay isang binary tree.
>> OK, stack.
At din, mukhang namin Maaaring magkaroon ng kaunting oras.
Kung gagawin namin, Ikinagagalak kong pumunta sa paglipas ng alinman sa mga ito muli.
OK, kaya stack.
Sinuman tandaan ba kung ano stacks-- anumang mga katangian ng isang stack?
>> OK, kaya ang karamihan sa atin, sa palagay ko, kumain sa dining halls--
hangga't maaaring hindi namin nais na.
Ngunit malinaw naman, maaari mong isipin ang isang stack Literal na lamang bilang isang stack ng mga trays
o isang stack ng mga bagay.
At kung ano ang mahalaga upang mapagtanto ay na ito
something-- ang katangian na tinatawag namin itong by-- ay LIFO.
Sinuman Alam ba kung ano na ang ibig sabihin ay?
Mmhmm?
>> Madla: Huling in, unang out.
>> Tagapagsalita 1: I-right, tatagal sa, out muna.
Kaya kung alam namin, kung kami ay stacking bagay up, ang pinakamadaling bagay upang grab off--
at marahil ang tanging bagay na maaari naming grab -off kung ang aming stack ay malaki enough--
ay ang nangungunang elemento.
Kaya kahit anong ay ilagay sa last-- tulad ng nakikita namin dito,
anumang ay hunhon sa karamihan ng mga recently-- ay
pagpunta sa maging una bagay na pop-off namin, OK?
>> Kaya kung ano ang mayroon kami dito ay isa pang typedef struct.
Ito ay talagang gusto lamang Siyempre crash sa istraktura ng data,
kaya maraming itinapon sa iyo guys.
Alam ko.
Kaya isa pang struct.
Ayos para sa mga istraktura.
>> At sa kasong ito, ito ang ilang pointer sa isang array na may ilang mga kapasidad.
Kaya ito ay kumakatawan sa aming mga stack dito, tulad ng ating mga aktwal na array
na may hawak na aming elemento.
At pagkatapos dito mayroon kaming ilang mga laki.
>> At karaniwan, ang gusto mong panatilihing track ng kung gaano kalaki ang iyong stack ay
dahil kung ano ang pagpunta sa payagan mo lang gawin ay kung alam mo ang laki,
Nagbibigay-daan ito sa iyo na sabihin, OK, ako sa kapasidad?
Maaari ba akong magdagdag ng ano pa?
At nagsasabi rin ito sa iyo kung saan sa tuktok ng iyong stack
ay gayon alam mo kung ano ang Maaari aktwal na lumipad.
At na aktwal na pagpunta sa maging isang maliit na mas malinaw dito.
>> Kaya para sa push, isang bagay, kung ay kailanman upang ipatupad ang push,
tulad ng ako ay sinasabi, ang iyong stack ay may limitadong laki, tama?
Ang aming mga array ay may ilang mga kapasidad.
Ito ay isang array.
Ito ay isang nakapirming laki, kaya kailangan namin upang tiyakin na hindi kami naglalagay ka ng higit pa
sa aming array kaysa namin talaga may espasyo para sa.
>> Kaya kapag lumilikha ka ng isang push function, ang unang bagay na ginawa mo ay sabihin nating, OK,
ang mayroon ako espasyo sa aking stack?
Dahil kung gagawin ko hindi, paumanhin, Hindi ko ma-imbak ang iyong mga elemento.
Kung gagawin ko, pagkatapos ay nais mong iimbak ito sa tuktok ng stack, tama?
>> At ito ang dahilan kung bakit mayroon kaming upang masubaybayan ang aming laki.
Kung hindi namin masubaybayan ang aming mga sukat, hindi namin alam kung saan upang ilagay ito.
Hindi namin alam kung gaano karaming mga bagay ay nasa aming array na.
Tulad ng malinaw naman may mga paraan na siguro maaari mong gawin ito.
Maaari mong simulan ang lahat ng bagay sa null at pagkatapos suriin para sa pinakabagong null,
ngunit isang mas madaling bagay lamang sasabihin, OK, subaybayan ang laki.
Tulad ng alam ko Mayroon akong apat na mga elemento sa aking array, kaya ang susunod na bagay
na inilalagay namin sa, kami ay pagpunta upang mag-imbak sa index 4.
At pagkatapos ay, siyempre, nangangahulugan ito na matagumpay mong na-hunhon isang bagay
papunta sa iyong stack, mo nais na dagdagan ang laki
kaya na alam mo kung nasaan ka kaya na maaari mong itulak higit pang mga bagay sa.
>> Kaya kung namin na sinusubukan mong i-pop isang bagay off ang stack,
kung ano ang maaaring maging unang bagay na gusto naming suriin para sa?
Sinusubukan mong gumawa ng isang bagay off ang iyong stack.
Sigurado ka bang mayroong isang bagay sa iyong stack?
Hindi.
Kaya kung ano ang maaaring gusto naming suriin?
>> Madla: [hindi marinig].
Tagapagsalita 1: I-check para sa laki?
Laki.
Kaya gusto naming suriin upang makita kung ang aming laki ay mas malaki kaysa sa 0, OK?
At kung ito ay, pagkatapos ay nais naming bawasan ang aming laki sa pamamagitan ng 0 at ibalik iyon.
Bakit?
>> Sa unang isa namin panunulak, matutulak namin ito
sa laki at pagkatapos ay i-update ang laki.
Sa kasong ito, kami ay decrementing laki at pagkatapos ay pagkuha off ito, plucking ito
mula sa aming mga array.
Bakit maaaring gawin namin iyon?
Kaya kung mayroon akong isang bagay sa aking stack, kung ano ang magiging aking mga laki sa puntong iyon?
1.
>> At kung saan ay elemento 1 na naka-imbak?
Sa anong index?
Madla: 0.
Tagapagsalita 1: 0.
Kaya sa kasong ito, kami laging kailangan upang gumawa ng sure--
sa halip ng pagbabalik laki ng minus 1, dahil kami
alam na ang aming elemento ay pagpunta sa ay naka-imbak sa 1 mas mababa
anumang aming laki ay, ito lamang tumatagal ng pag-aalaga ng mga ito.
Ito ay isang bahagyang higit pa eleganteng paraan.
At pagbawas lamang namin ang aming laki at pagkatapos ay bumalik ang laki.
Mmhmm?
>> Madla: hulaan ko pa lang sa pangkalahatan, bakit gagawin ito istraktura ng data
maging kapaki-pakinabang?
>> Tagapagsalita 1: Depende ito sa iyong konteksto.
Kaya para sa ilan sa mga teorya, kung nagtatrabaho ka with-- OK,
hayaan mo akong makita kung mayroong ay isang kapaki-pakinabang na kapaki-pakinabang sa higit pa sa labas
ng CS.
Sa stack, anumang oras na kailangan mo upang subaybayan ang mga bagay na
ay ang pinaka-kamakailang idinagdag ay kapag ka ng pagpunta sa nais na gumamit ng stack.
>> At hindi ako makapag-isip ng isang magandang halimbawa ng na ngayon.
Ngunit sa tuwing ang pinakabagong bagay ay pinakamahalaga sa iyo,
na kapag ang isang stack ay magiging kapaki-pakinabang.
Sinusubukan kong mag-isip kung mayroong isang magandang isa para sa ito.
Kung sa tingin ko ng isang magandang halimbawa sa susunod na 20 minuto, talagang ay ko bang sabihin sa iyo.
>> Ngunit sa pangkalahatan, kung mayroong anumang bagay, tulad ng sinabi ko sa karamihan, kung saan ang pinaka-kamakailang
ang pinaka-mahalaga, na kung saan isang stack ay sa pag-play.
Sapagkat ang queues ay uri ng ng kabaligtaran.
At ang lahat ng mga maliit na aso.
Ay hindi ito mahusay na, tama?
Nararamdaman kong dapat kong mayroon lamang isang kuneho video
karapatan sa gitna ng na seksyon para sa iyo guys
dahil ito ay isang malakas na seksyon.
>> Kaya isang queue.
Isa lamang queue ay tulad ng isang linya.
Ikaw guys ako bang gamitin ang araw-araw, gusto lang sa aming dining hall.
Kaya mayroon kaming upang pumunta sa at kumuha ng aming mga trays, ako ay
Tiyaking mayroon kang maghintay sa linya upang mag-swipe o kunin ang iyong pagkain.
>> Kaya ang pagkakaiba dito ay na ito ay FIFO.
Kaya kung huling sa LIFO ay, unang out, FIFO unang in, unang out.
Kaya ito ay kung saan ang anumang ilagay mo sa una ay ang iyong pinakamahalagang.
Kaya kung ikaw ay naghihintay sa isang line-- maaari kang
isipin kung napunta ka sa pumunta makuha ang bagong iPhone
at ito ay isang stack na kung saan ang nakuha ko huling tao sa linya una,
mga tao na gusto pumatay sa bawat isa.
>> Kaya FIFO, hindi namin ang lahat ng masyadong pamilyar may sa tunay na mundo dito,
at ang lahat ng ito ay gagawin sa aktwal uri ng nililikha ang buong linya
at queuing istraktura.
Kaya samantalang may stack, mayroon kaming push at mga pop.
Sa isang pila, mayroon kaming I-enqueue at dequeue.
Kaya I-enqueue talaga ang ibig sabihin ilagay ito sa likod,
at dequeue paraan tumagal -off mula sa front.
Kaya aming mga istraktura ng data ay isang Medyo higit pang kumplikado.
Mayroon kaming ikalawang bagay upang masubaybayan.
>> Kaya walang ulo, ito ay eksaktong isang stack, tama?
Ito ay ang parehong istraktura bilang isang stack.
Ang tanging bagay ibang ngayon ay namin may ito ulo, na kung ano sa tingin mo
Mawawala upang masubaybayan?
>> Madla: Ang una.
>> Tagapagsalita 1: I-right, ang unang bagay na aming inilagay sa.
Ang ulo ng aming queue.
Sinumang unang nasa linya.
Ang lahat ng mga karapatan, kaya kung gawin namin enqueue.
Muli, gamit ang alinman sa mga kayarian ng data,
dahil kami ay pagharap sa isang array, kailangan namin upang suriin kung mayroon kaming espasyo.
>> Ito ay uri ng tulad ng sa akin na nagsasabi mo guys, kung nagbukas ka ng isang file,
kailangan mong i-check para sa null.
Gamit ang anuman sa mga stack at queues, kailangan mong
upang makita kung mayroong espasyo dahil kami pagharap sa isang nakapirming laki ng array,
tulad ng nakikita namin here-- 0, 1 lahat ng hanggang 5.
Kaya kung ano ang ginagawa namin sa kasong iyon ay check upang makita kung mayroon pa rin kaming espasyo.
Ay ang aming laki mas mababa sa kapasidad?
>> Kung gayon, kailangan namin upang mag-imbak ito sa ang buntot at i-update namin ang aming laki.
Kaya kung ano ang maaaring ang buntot na sa kasong ito?
Ito ay hindi tahasang nakasulat out.
Paano namin iimbak ito?
Ano ang magiging buntot?
>> Kaya sabihin maglakad sa pamamagitan ng halimbawa na ito.
Kaya ito ay isang hanay ng mga laki 6, tama?
At mayroon kaming ngayon, ang aming laki ay 5.
At kapag inilalagay namin ito, ito ay pagpunta pumunta sa ikalimang index, tama?
Kaya mag-imbak sa likod o hulihan.
>> Ang isa pang paraan upang isulat ang buntot gagawin lamang maging, i-right aming array sa index ng laki?
Ito ay laki 5.
Susunod na bagay ay pagpunta sa pumunta sa 5.
Cool?
OK.
Ito ay makakakuha ng bahagyang mas komplikado kapag sinimulan namin ang panggugulo sa ulo.
Oo?
>> Madla: Nangangahulugan ba na na namin sana ay ipinahayag na isang array na
ay limang elemento ng mahaba at pagkatapos naming idinadagdag sa ito?
>> Tagapagsalita 1: Hindi.
Kaya sa kasong ito, ito ay isang stack.
Ito ay ipinahayag bilang isang hanay ng mga laki 6.
At sa kasong ito, kami mayroon lamang isang puwang kaliwa.
>> OK, kaya ang isang bagay ay nasa ito kaso, kung ang aming ulo ay sa 0,
pagkatapos ay ito lamang namin ay maaaring magdagdag sa laki.
Ngunit ito ay nakakakuha ng kaunti trickier dahil aktwal na, ang mga ito
walang slide para sa na ito, kaya ako pupunta
upang gumuhit ng isang dahil hindi ito medyo na simple sa sandaling
simulan inaalis ng mga bagay.
Kaya samantalang may stack lamang kailanman mayroon kang
mag-alala tungkol sa kung ano ang laki ay kapag nagdadagdag ka ng isang bagay sa,
may isang queue kailangan mo rin gawin Tiyakin na ang iyong ulo ay accounted para sa,
dahil ang isang cool na bagay tungkol sa queues ay kung wala ka sa kapasidad,
Maaari mong aktwal na gawin itong balutin sa paligid.
>> OK, kaya isa thing-- oh, ito ay kahila-hilakbot na tisa.
Ang isang bagay upang isaalang-alang ang kaso.
Makikita lang namin gawin lima.
OK, kaya kami ay pagpunta sa ang sinasabi ng mga pinuno ay dito.
Ito ay 0, 1, 2, 3, 4.
>> Ulo ang naroon, at mangyaring magkaroon ng mga bagay sa kanila.
At gusto naming idagdag ang isang bagay sa, i-right?
Kaya ang bagay na kailangan namin upang alam na ang ulo ay laging
pagpunta sa ilipat ang paraan at pagkatapos ay i-loop pabalik sa paligid, OK?
>> Kaya may mga puwang na ito queue, i-right?
Mayroon itong puwang sa pinakadulo simula, uri ng tapat ng ito.
Kaya kung ano ang kailangan naming gawin ay namin Kailangan upang makalkula ang buntot.
Kung alam mo na ang iyong Hindi inilipat ulo, buntot
lamang ang iyong mga array sa sa index ng laki.
>> Ngunit sa katotohanan, kung gumagamit ka ng isang pila, ang iyong ulo ay malamang na ina-update.
Kaya kung ano ang kailangan mong gawin ay aktwal na kalkulahin ang buntot.
Kaya kung ano ang ginagawa namin ay ang formula dito, na kung saan ako pupunta upang ipaalam sa iyo
guys isipin ang tungkol sa, at pagkatapos ay gagamitin namin makipag-usap tungkol dito.
Kaya ito ay kapasidad.
>> Kaya na ito ay talagang magbibigay sa iyo ng isang paraan upang gawin ito.
Dahil sa kasong ito, ano?
Ang aming mga pinuno ay nasa 1, ang aming laki ay 4.
Kung mod namin na sa pamamagitan ng 5, makuha namin ang 0, na kung saan ay dapat namin pag-input na ito.
>> Kaya pagkatapos ay sa susunod na kaso, kung kami ay upang gawin ito,
sabihin namin, OK, dequeue ng isang bagay na ipaalam.
Dequeue namin ito.
Kumuha namin ang elementong ito, i-right?
>> At ngayon ang aming mga ulo nakaturo dito, at gusto naming idagdag sa isa pang bagay.
Ito ay isa lamang sa pabalik sa aming mga linya, tama?
Queues maaari wrap sa paligid ng array.
Iyon ang isa sa mga pangunahing pagkakaiba.
Stack, hindi mo maaaring gawin ito.
>> Sa queues, maaari mong dahil ang lahat na mahalaga
ay na-alam sa iyo kung ano ang Idinagdag ang pinaka-kamakailang.
Dahil ang lahat ng bagay ay pagpunta na idaragdag sa ito pakaliwa direksyon, sa kasong ito,
at pagkatapos ay i-wrap sa paligid, maaari kang magpatuloy paglalagay sa mga bagong elemento
sa harap ng array dahil hindi ito talaga
sa harap ng array na ngayon.
Maaari mong isipin na ang simula ng array ng kung saan ang iyong ulo talaga.
>> Kaya ito formula ay kung paano makalkula mo ang iyong buntot.
Sinusuportahan ba na saysay?
OK.
OK, dequeue, at pagkatapos ay ka guys ay may 10 minuto
upang hilingin sa akin ang anumang mga tanong pagpapaliwanag gusto mo, dahil alam kong ito'y mabaliw.
>> Ang lahat ng mga karapatan, kaya sa parehong way-- Hindi ko alam kung napansin mo guys,
ngunit CS ay tungkol sa mga pattern.
Mga bagay ay medyo magkano ang parehong, lamang sa mga maliliit na pag-aayos.
Kaya parehong bagay dito.
Kailangan naming suriin upang makita kung kami talaga May isang bagay sa aming queue, i-right?
Sabihing, OK, ang aming laki mas malaki kaysa sa 0?
Ayos.
>> Kung gagawin namin, pagkatapos ay ilipat namin ang aming mga pinuno, na ay kung ano lamang ang nagpakita ko dito.
-Update namin ang aming ulo upang maging isa pa.
At pagkatapos ng pagbawas namin ang aming laki at ibalik ang mga elemento.
>> May mas kongkreto code sa study.cs50.net,
at lubos na inirerekomenda ko ng pagpunta sa pamamagitan nito kung mayroon kang panahon,
kahit na ito ay isang palsipikado-code lamang.
At kung gusto mong guys na makipag-usap sa pamamagitan ng na sa akin ng isa sa isa, mangyaring ipaalam sa akin
alam.
Gusto ko ay magiging masaya na.
Mga istraktura ng data, kung Dadalhin ka ng CS 124, ikaw ay
malaman na ang mga istraktura ng data makakuha ng napaka masaya at ito ay nagsisimula pa lang.
>> Kaya alam ko mahirap.
Ito ay ang OK.
Nagpupumilit namin.
Ko pa rin gawin.
Kaya huwag mag-alala masyadong maraming tungkol dito.
>> Ngunit iyon ay isa lamang ang iyong Siyempre pag-crash sa mga istraktura ng data.
Alam ko ito ng maraming.
Mayroon bang anumang bagay na namin gustong pumunta muli?
Anumang bagay na gusto naming makipag-usap sa pamamagitan?
Oo?
>> Madla: Halimbawa iyon, kaya ang bagong buntot ay nasa 0 ibabaw iyon?
Tagapagsalita 1: Oo.
Madla: OK.
Kaya pagkatapos ng pagpunta sa pamamagitan ng, kailangan mong 1 plus 4 or--
>> Tagapagsalita 1: Kaya ay nagsasabi sa iyo, kung kailan namin gustong pumunta gawin ito muli?
Madla: Oo.
Kaya kung ikaw ay pag-uunawa ng out-- kung nasaan mo pagkalkula ng buntot mula sa iyon?
>> Tagapagsalita 1: Kaya ang buntot ay in-- Nabago ko na ito.
Kaya sa halimbawa dito, ito ay ang array kaming naghahanap sa, OK?
Kaya mayroon kaming mga bagay sa loob ng 1, 2, 3, at 4.
Kaya mayroon namin ang aming mga ulo ay katumbas ng 1 sa puntong ito, at ang aming laki ay katumbas ng 4
sa puntong ito, tama?
>> Mo ang lahat ng sumang-ayon na ang kaso?
Kaya ang ginagawa namin ang ulo kasama ang laki, na Binibigyan kami ng 5, at pagkatapos ay i-mod namin sa pamamagitan ng 5.
Makuha namin ang 0, na nagsasabi sa amin na ang 0 ay kung saan ay ang aming buntot, kung saan mayroon kaming espasyo.
>> Madla: Ano ang isang cap?
>> Tagapagsalita 1: kapasidad Ang.
Sorry.
Kaya na ay ang laki ng iyong array.
Oo?
>> Madla: [hindi marinig] bago bumalik namin ang elemento?
>> Tagapagsalita 1: Kaya ilipat namin ang magtungo o bumalik sa sandaling ito?
Kaya kung ililipat namin ang isa, ng pagbawas sa laki?
Sandali.
Siguradong Nakalimutan ko ang isa pa.
Hindi na bale.
Walang ibang formula.
Oo, gusto mo upang bumalik ang ulo at pagkatapos ay ilipat ito pabalik.
>> Madla: OK, dahil Sa na ito point, ang ulo ay sa 0,
at pagkatapos ay gusto mong bumalik index ng 0 at pagkatapos ay gumawa ng ulo 1?
>> Tagapagsalita 1: I-right.
Sa tingin ko mayroong isa pang formula uri ng ganito.
Wala akong ito sa tuktok ng aking ulo bilang Hindi ko nais upang mabigyan ka ng isang mali.
Ngunit tingin ko ito ay ganap na wasto upang sabihin nating, OK, iimbak ang element-- anumang
elemento ng ulo ni is-- ng pagbawas sa iyong laki, ilipat ang iyong ulo sa ibabaw, at return
anumang elemento na.
Iyon ang perpektong wastong.
OK.
Pakiramdam ko ay tulad nito ay hindi tulad ng most-- hindi ka
pagpunta sa walk out sa dito tulad ng, oo, alam ko pagsubok.
Mayroon akong lahat ng ito.
Iyon ang OK.
Nangangako ako.
Ngunit mga istraktura ng data ay isang bagay na gumugugol ito ng maraming oras upang masanay.
Malamang na isa sa mga hardest mga bagay, sa tingin ko, sa kurso.
>> Kaya nga tumatagal ito pag-uulit at naghahanap at-- ko
ay hindi talaga alam na naka-link listahan hanggang ginawa ko sa ngayon labis sa kanila,
sa parehong paraan na aking ginawa hindi talagang nauunawaan na pointer
hanggang sa nagkaroon ako magturo ito para sa dalawang taon at ang aking sariling psets dito.
Inaabot ng maraming pag-uulit at oras.
At sa huli, ito uri ng click.
>> Ngunit pansamantala, kung mayroon kang uri ng isang mataas na antas ng pag-unawa kung ano ang
mga gagawin, ang kanilang mga pro at cons-- na kung ano ang
kami talaga ay may posibilidad upang bigyan ng diin, lalo na sa intro course.
Tulad ng, kung bakit naming gamitin isang subukan sa isang array?
Tulad ng, ano ang mga positibo at mga negatibo ng bawat isa sa mga?
>> At pag-unawa sa mga trade-off sa pagitan ng bawat isa sa mga kaayusan
ay kung ano ang mas mahalaga sa ngayon.
Maaaring may isa mabaliw tanong o dalawang na
pagpunta sa hilingin sa iyo upang ipatupad ang push o ipatupad ang mga pop o enqueue at dequeue.
Ngunit para sa pinaka-bahagi, nagkakaroon na mas mataas na antas ng pag-unawa at higit pa
ng isang intuitive hawakang mahigpit ay mas mahalaga kaysa sa aktwal
kawalan ng kakayahang ipatupad ito.
>> Gusto ito ay talagang kahanga-hangang kung ang lahat ng sa iyo maaaring lumabas at pumunta ipatupad ang try,
ngunit naiintindihan namin ito ay hindi kinakailangan ang pinaka-makatwirang bagay ngayon.
Ngunit maaari mo sa iyong pset, kung nais mong sa, at pagkatapos ay makakakuha ka ng mga kasanayan,
at pagkatapos ay marahil ikaw ay talagang maunawaan ito.
Oo?
>> Madla: OK, kaya kung alin ang mga namin sinadya upang gamitin sa pset?
Kailangan ko bang gamitin ang isa sa mga ito?
Tagapagsalita 1: Oo.
Kaya mayroon kang ang iyong pinili.
Sa tingin ko sa kasong ito, maaari naming makipag-usap tungkol sa pset Medyo
dahil nagpatakbo ako sa pamamagitan ng mga ito.
Kaya sa iyong pset, mayroon kang iyong pagpili ng pagsubok o hash talahanayan.
Ang ilang mga tao ay subukan at gamitin ang pamumulaklak ng mga filter,
ngunit ang mga technically ay hindi tama.
Dahil sa kanilang probabilistic likas na katangian, bigyan sila maling positibo minsan.
Ang mga ito ay cool na hitsura sa, bagaman.
Lubos na inirerekomenda hinahanap sa mga ito ng hindi bababa sa.
Ngunit mayroon kang iyong pinili sa pagitan ng isang hash table at try.
At na pupuntahan maging kung saan -load mo sa iyong diksyunaryo.
>> At kailangan mong pumili ang iyong hash,
kakailanganin mong piliin kung gaano karaming mga bucket na mayroon ka, at ito ay mag-iiba.
Tulad ng kung mayroon kang higit bucket, marahil ito ay tumakbo nang mas mabilis.
Pero siguro ka pag-aaksaya ng maraming espasyo na paraan, bagaman.
Kailangan mong malaman ito.
Mmhmm?
>> Madla: Sinabi mo dati na Maaari naming gamitin ang iba pang mga pag-andar ng hash,
na hindi namin kailangang lumikha ng isang hash?
>> Tagapagsalita 1: Oo, tama.
Kaya literal para sa iyong hash, tulad ng google "hash"
at hanapin para sa ilang mga magandang mga bago.
Hindi mo ay inaasahan na bumuo ng ang iyong sariling mga pag-andar ng hash.
Gastusin mga tao ang kanilang theses sa mga bagay na ito.
>> Kaya huwag mag-alala tungkol sa pagbuo ng iyong sariling.
Hanapin ang isa sa mga online na magsimula sa.
Ang ilan sa mga ito ay mong manipulahin Medyo
upang gawin tumugma bang uri ng return up at watnat, kaya sa simula,
Gusto ko inirerekomenda ang paggamit ng isang bagay talagang madali na siguro lang
hash sa unang titik.
At pagkatapos ay sa sandaling mayroon ka na sa pagtatrabaho, nagsasama ng mas cool na function na hash.
Mmhmm?
>> Madla: Gusto ng subukang maging o mahusay na ngunit mas mahirap lamang sa, like--
>> Tagapagsalita 1: Kaya isang try, sa palagay ko, ay intuitively mahirap na ipatupad
ngunit ito ay napakabilis.
Gayunpaman, tumatagal ng mas maraming espasyo.
Muli, maaari mong i-optimize ang parehong mga nasa iba't ibang paraan at may mga paraan to--
Madla: Paano kami ay namarkahan sa ito?
Ito ay matter--
>> Tagapagsalita 1: Kaya ka namarkahan ang normal na paraan.
Na iyong pupuntahan ay namarkahan sa disenyo.
Alinmang paraan gagawin mo, nais mong tiyakin na ito ay bilang eleganteng bilang maaari itong maging
at bilang mahusay na bilang maaari itong maging.
Ngunit kung pumili ka ng isang pagsubok o hash talahanayan, hangga't ito gumagana,
kami ay masaya na iyon.
At kung gumagamit ka ng isang bagay na hash sa unang titik, na multa,
tulad siguro tulad ng disenyo-matalino.
Kami ay pag-abot din ang point sa semester--
Hindi ko alam kung guys noticed-- kung ikaw ay
grado pset tanggihan Medyo dahil sa disenyo at watnat,
na ganap na multa.
Nagiging sa isang punto kung saan ang iyong programa ay nakakakuha ng mas komplikado.
Mayroong higit pang mga lugar maaari mong pagbutihin sa.
>> Kaya ito ay ganap na normal.
Ito ay hindi na ikaw ay paggawa ng mas masahol pa sa iyong pset.
Ito ay lamang namin ang pagiging mahirap sa iyo ngayon.
Kaya lahat ay pakiramdam ito.
Ko lang namarkahan ang lahat ng iyong mga psets.
Alam ko ang lahat ay pakiramdam ito.
>> Kaya huwag maging nag-aalala tungkol na iyon.
At kung mayroon kang anumang mga tanong tungkol sa bago psets o mga paraan na maaari mong pagbutihin,
Ako subukan at magkomento sa mga partikular na mga lugar, ngunit minsan ito ay huli na
at makakakuha ng pagod.
Mayroon bang anumang iba pang mga bagay tungkol sa data na kaayusan?
Ako ba mo guys ay hindi talaga nais na makipag-usap tungkol sa mga ito,
ngunit kung mayroong, Ikinagagalak kong pumunta sa ibabaw ng mga ito, pati na rin ang anumang bagay
mula sa aralin na ito nakalipas linggo o noong nakaraang linggo.
>> Alam ko noong nakaraang linggo ay ang lahat ng pagsusuri, kaya Maaaring namin nilaktawan sa paglipas ng ilang mga review
mula sa aralin.
Anumang iba pang mga katanungan maaari kong sagutin?
OK, ang lahat ng karapatan.
Well, mo guys makakuha ng out ng 15 minutong maaga.
>> Umaasa ako na ito ay semi-kapaki-pakinabang na hindi bababa sa, at ako ay nakikita mo guys sa susunod na linggo,
o oras ng opisina Huwebes.
Mayroon bang humiling para sa mga meryenda para sa susunod na linggo, ito ang bagay?
Dahil nakalimutan ko ang kendi ngayon.
At dinala ako candy huling linggo, ngunit ito ay Columbus Day,
kaya mayroong tulad ng anim na taong Nagkaroon ng apat na mga bag ng kendi sa kanilang mga sarili.
Maaari ko bang magdala ng Starbursts muli kung nais mo.
Starbursts?
OK, Maganda iyan.
Mayroon ba kayong dakilang araw, guys.