Tagapagsalita 1: Ang lahat ng mga karapatan, sa gayon ito ay CS50 ito ay ang katapusan ng linggo limang. At isipin na ang huling oras na namin nagsimula ang pagtingin sa mga may interes data istruktura na nagsimula upang malutas problema, na nagsimula upang ipakilala bagong mga problema, ngunit ang key na ito ay ang uri ng threading na tayo nagsimula na gawin mula sa node sa node. Kaya ito ng mga kurso ay isang isa-isa naka-link na listahan. At sa pamamagitan ng isa-isa naka-link, Ibig kong sabihin may isa lamang thread sa pagitan ng bawat isa sa mga nodes. Lumiliko out na maaari mong gawin ng may interes mga bagay tulad ng doble listahan ng link kung saan ikaw ay may isang arrow pagpunta sa parehong direksyon, na kung saan maaaring makatulong sa ilang mga kahusayan. Ngunit ito nalutas na ang problema? Ano ang problema ay malutas ito? Bakit pag-aalaga namin sa Lunes? Bakit, sa teorya, ay nagmamalasakit kami sa Lunes? Ano ang ginagawa nito? 

Madla: Maaari dynamic naming baguhin ang laki nito. 

Tagapagsalita 1: OK, upang maaari naming magilas na baguhin ang laki nito. Magaling sa inyong dalawa. Kaya maaari mong dynamic na baguhin ang laki ng mga ito istraktura ng data, kung saan ang isang array, pagpapabalik, kailangan mong malaman kung ang isang walang pagsubok kung magkano ang space na gusto mo at kung kailangan mo ng kaunti pa space, ikaw ay uri ng out of luck. Mayroon kang lumikha ng isang buong bagong array. Kailangan mong ilipat ang lahat ng iyong data mula sa isa sa iba pang, huli free ang lumang array maaari mong, at pagkatapos ay magpatuloy kung. Aling lamang pakiramdam ng masyadong magastos at napaka walang kakayahan, at sa katunayan ito ay maaaring. Ngunit ito ay hindi lahat ng mabuti. Nagbabayad kami ng isang presyo, ano ang isa sa mga mas malinaw na mga presyo namin magbayad sa pamamagitan ng paggamit ng isang listahan ng mga link? 

Madla: Mayroon kaming upang gamitin ang double space para sa bawat isa. Tagapagsalita 1: Oo, kaya kailangan namin ng hindi bababa sa dalawang beses ng mas maraming espasyo. Sa katunayan, ako na natanto na larawan na ito kahit na isang maliit na mali, dahil sa CS50 IDE sa isang pulutong ng mga modernong mga computer, ang isang pointer o address ay hindi sa katunayan apat na bytes. Very madalas ang mga ito ay araw walong bytes, kung saan nangangahulugan ibaba karamihan parihaba doon sa katotohanan mga uri ng dalawang beses bilang malaking bilang kung ano ang iginuhit ko na, na nangangahulugan na ikaw ay gumagamit ng tatlong beses ng mas maraming espasyo bilang ay magkaroon tayo ng ibang paraan. Ngayon at sa parehong oras, hindi namin pakikipag-usap pa rin bytes, di ba? Hindi kami palaging pakikipag-usap megabytes o gigabytes, maliban kung ang mga data kaayusan makakuha ng malaki. 

At kaya ngayon namin simulan upang isaalang-alang kung paano namin maaaring galugarin ang data mas mahusay kung in katunayan ang data ay makakakuha ng mas malaki. Ngunit sabihin subukan upang canonicalize ipaalam ang operasyon ng unang na maaari mong gawin sa mga mga uri ng istruktura ng data. Kaya ang isang bagay tulad ng isang naka-link list pangkalahatan ay sumusuporta sa operations gusto tanggalin, ipasok, at sa paghahanap. At kung ano ang ibig sabihin ako sa pamamagitan ng na? Iyon ay nangangahulugan lamang na kadalasan, kung ang mga tao ay gumagamit ng naka-link na listahan, sila o sa ibang tao ay ipinatupad function tulad ng delete, insert, at sa paghahanap, sa gayon maaari mong talagang gawin ang isang bagay kapaki-pakinabang sa mga istraktura ng data. Kaya sabihin kumuha ng isang mabilis na pagtingin sa kung paano namin maaaring ipatupad ang ilang mga code para sa isang listahan ng mga link tulad ng sumusunod. 

Kaya ito ay ilan lamang sa C code, hindi kahit isang kumpletong programa na ako tunay mabilis wip up. Ito ay hindi online sa pamamahagi code, dahil hindi ito aktwal na tatakbo. Ngunit mapansin na hindi ko na lang sa isang komento nagsabi, dot dot dot, may isang bagay doon, tuldok tuldok tuldok, isang bagay doon. At Tingnan lang natin ang hahanapin kung ano ang mga makatas mga bahagi ay. Kaya sa tatlong linya, pagpapabalik na ito ay ngayon namin ipinanukalang deklarasyon ng isang node huling panahon, isa sa mga parihabang bagay. Ito ay may isang int na namin ang tawag N, ngunit kami ay maaaring tumawag ito anumang bagay, at pagkatapos ng isang struct node bituin na tinatawag na susunod. At upang maging lamang malinaw, na second line, sa anim na linya, ano na? Ano ang ginagawa nito para sa amin? Dahil ito ay tiyak na mukhang mas cryptic sa aming karaniwang mga variable. 

Madla: Ito ay ginagawang ilipat sa ibabaw ng isa. 

Tagapagsalita 1: Ito ay ginagawang ilipat sa ibabaw ng isa. At upang maging mas tiyak, ito store ang address ng node na ay sinadya upang maging semantically sa tabi nito, di ba? Kaya ito ay hindi pagpunta sa kinakailangang ilipat ang anumang bagay. Lamang Ito ay pagpunta sa tindahan ng isang halaga, na kung saan ay magiging address ng ilang mga iba pang node, at iyon ang dahilan kung bakit namin sinabi na struct node star, ang star nagsasaad isang pointer o address. OK, kaya ngayon kung akala mo na mayroon kami na magagamit sa amin ang N, at sabihin ipalagay na ang ibang tao ay may nakapasok ng buong bungkos ng mga integer sa isang listahan ng mga link. At na listahan ng mga link ay nakatutok sa pamamagitan ng ilang mga punto isang variable na tinatawag na listahan na lumipas in dito bilang isang parameter, paano ko pumunta tungkol sa line 14 pagpapatupad ng paghahanap? Sa ibang salita, kung ako ay pagpapatupad function na ang layunin sa buhay ay ang kumuha ng isang int at pagkatapos ay ang simula ng isang listahan ng mga link, iyon ay isang pointer sa naka-link na listahan. Tulad ng una, na sa tingin ko David ay ang aming volunteer sa Lunes, siya ay nakaturo sa ang buong listahan ng mga link, ito ay bilang bagaman kami ay pagpasa David sa bilang ating argument dito. Paano namin pumunta tungkol bumabagtas sa listahang ito? Well, ito ay lumiliko out na kahit na mga payo ay relatibong bago ngayon sa amin, maaari naming gawin ito relatibong tuwiran. 

Pupunta ako sa sige at magpahayag ng isang pansamantalang variable na sa pamamagitan ng convention ay lamang ang pagpunta na tinatawag na pointer, o PTR, ngunit maaari kang tumawag ito anumang nais mo. At ako pagpunta sa magpasimula ito sa simula ng listahan. Kaya maaari mong uri ng tingin ng mga ito bilang ako guro sa isang araw, uri ng pagturo sa isang tao sa gitna ng aming mga kawani na tao bilang boluntaryo. Kaya ako ng isang pansamantalang variable na lamang ng pagturo sa parehong bagay na ang aming coincidentally pinangalanan volunteer David ay din ng pagturo out. Ngayon habang pointer ay hindi null, dahil pagpapabalik na null ay ang ilang mga espesyal na halaga nagbabantay ang demarkasyon sa dulo ng listahan, kaya habang hindi ko na nakaturo sa lupa tulad ng aming huling volunteer ay, sabihin sige at gawin ang sumusunod. Kung pointer-- at ngayon ako uri ng gusto upang gawin kung ano ang ginawa namin sa mag-aaral ang structure-- kung pointer tuldok sa tabi equals-- halip, kung pointer dot N katumbas ay katumbas ng variable N, ang argument na na lumipas sa, pagkatapos ay gusto kong sige at sabihin nagbabalik ng tunay. Ako ay may natagpuan ang bilang N sa loob ng isa sa mga node ng aking listahan na naka-link. Ngunit walang mga tuldok na gumagana sa kontekstong ito, dahil pointer, PTR, ay sa katunayan ng isang pointer, isang address, talaga namin maaari kamangha-mangha gamitin ang wakas ng isang piraso ng syntax na uri ng mga gumagawa intuitive na kahulugan at ang tunay na gamitin ang isang arrow dito, na nangangahulugan na pumunta mula sa address na sa integer may in. Kaya ito ay lubos na katulad sa espiritu na ang tuldok operator, ngunit dahil pointer ay hindi isang pointer at hindi isang aktwal struct mismo, gamitin lamang namin ang mga arrow. 

Kaya kung ang kasalukuyang node na ako, ang pansamantalang variable, ay tumuturo sa Hindi N, ano ang gusto kong gawin? Well, sa aking mga tao boluntaryo na nagkaroon kami dito sa ibang mga araw, kung ang aking unang tao ay hindi ang isa ko gusto, at marahil ang pangalawang tao ay hindi ang isa na nais ko, at sa pangatlo, ako kailangan upang mapanatili ang pisikal na paglipat. Tulad ng kung paano mo ako na hakbang sa pamamagitan ng isang listahan? Mo ang Kapag nagkaroon kami ng isang array, ginawa lamang tulad ko plus plus. Ngunit sa kasong ito, sapat na gawin pointer, nakakakuha, pointer, susunod. Sa ibang salita, ang susunod na field ay tulad ng lahat ng kaliwang kamay na ang aming mga tao boluntaryo sa Lunes ay gamit upang ituro sa ilang iba pang mga node. Mga ay ang kanilang susunod na mga kapitbahay. 

Kaya kung gusto kong magbasa-basa sa listahan na ito, Hindi ko lang gagawin ko plus plus anymore, Sa halip ko na kailangang sabihin I, pointer, ay pagpunta sa pantay ano man ang susunod na field ay, ang susunod na field ay, ang susunod na field ay, pagsunod sa lahat ng mga kaliwa sa kamay na nagkaroon kami sa entablado pagturo sa ilang mga kasunod na mga halaga. At kung makakuha ako sa pamamagitan ng na ang buong pag-ulit, at sa wakas, ako pindutin null hindi pagkakaroon natagpuan N pa, babalik ko na lang na hindi totoo. Kaya muli, ang lahat na ginagawa namin dito, bilang sa bawat ang mga larawan ng ilang sandali ang nakalipas, ay nagsisimula sa pamamagitan ng pagturo sa simula ng listahan siguro. At pagkatapos kong i-check, ay ang halaga Naghahanap ako ng katumbas ng siyam? Kung gayon, bumalik ako totoo at ako tapos na. Kung hindi, i-update ko ang aking kamay, AKA pointer, upang ituro sa lokasyon na ang susunod na arrow, at pagkatapos ay lokasyon sa susunod na arrow, at sa susunod. Lang ako sa paglalakad sa pamamagitan ng array. 

Kaya muli, na nagmamalasakit? Tulad ng kung ano ito ng isang sangkap para sa? Well, isipin ang na ipinakilala namin ang paniwala ng isang stack, na ay i-type ang isang abstract data sa abot ng ito ay hindi isang C bagay, ito ay hindi isang CS50 bagay, ito ay isang abstract na ideya, ito ideya ng stacking mga bagay sa ibabaw ng bawat isa na maaaring ipatupad sa kumpol na iba't ibang paraan. At isang paraan namin iminungkahi ay may isang array, o sa isang naka-link na listahan. At ito ay lumiliko out na canonically, isang stack sinusuportahan ng hindi bababa sa dalawang mga operasyon. At ang mga salita buzz ay push, upang itulak ang isang bagay papunta sa stack, tulad ng isang bagong tray sa dining hall, o pop, na nangangahulugan na tanggalin ang kataas-taasan tray mula sa stack sa dining hall, at pagkatapos ay marahil ilang iba pang mga pagpapaandar na rin. Kaya kung paano namin maaaring tukuyin ang istraktura na ngayon kami ay pagtawag ng isang stack? 

Well, kami ay lahat ng mga bagay na kailangan syntax sa aming itapon sa C. sinasabi ko, bigyan ako ng isang uri ng kahulugan ng isang struct sa loob ng isang stack, Pupunta ako sa sabihin ay isang array, ng isang buong grupo ng mga numero at pagkatapos ay ang laki. Kaya sa ibang salita, kung gusto ko upang ipatupad ito sa code, hayaan mo akong pumunta at lamang uri ng gumuhit ng kung ano ito ay sinasabi. Kaya ito ay nagsasabi, bigyan ako ng isang structure na nakuha ng isang array, at hindi ko alam kung ano ang kapasidad ay, ito ay tila ang ilang mga tapat na ko tinukoy sa ibang lugar, at na fine. Ngunit ipagpalagay na ito ay isa lamang, dalawa, tatlo, apat, lima. Kaya kapasidad ay 5. Elementong ito sa loob ng aking istraktura ay tinatawag na numero. At pagkatapos ay kailangan ko ng isa iba pang mga variable sa malas tinatawag na laki na sa una pupuntahan ko sa magtadhana ay nasimulan sa zero. Kung may wala sa stack, laki ay zero, at ito ay mga halaga ng basura sa mga numero. Wala akong palagay kung ano ang doon pa lamang. 

Kaya kung nais kong itulak isang bagay papunta sa stack, Ipagpalagay tawag ko ang function push, at Sinasabi ko itulak 50, tulad ng bilang sa 50, kung saan nais mong imungkahi Gumuhit ko ito sa array na ito? May limang iba't ibang posibleng sagot. Saan mo gustong upang itulak ang bilang ng 50? Kung ang layunin dito, muli, tumawag sa function na push, pumasa sa isang argument 50, kung saan ko ilalagay ito? Five possible-- 20% na pagkakataon ng paghula tama. Oo? 

Madla: Far karapatan. 

Tagapagsalita 1: Far karapatan. Mayroon na ngayong isang 25% na pagkakataon ng paghula tama. Kaya na ay tunay na maging fine. Sa pamamagitan ng convention, kukunin ko na sabihin na may isang array, Gusto naming simulan ang pangkalahatan sa kaliwa, ngunit maaari naming tiyak simulan sa kanan. Kaya ang spoiler dito ay Ako marahil pagpunta sa gumuhit ito sa kaliwa, gusto lang sa isang normal na array kung saan Sisimulan ko ang pagpunta sa kaliwa papuntang kanan. Ngunit kung maaari mong i-flip ang arithmetic, fine. Ito lamang ay hindi maginoo. OK, kailangan kong gumawa ng isa higit pang mga pagbabago kahit na. Ngayon na itinulak ako ng isang bagay papunta sa stack, ano ang susunod? 

Lahat ng mga karapatan, mayroon akong upang dagdagan ang laki. Kaya hayaan mo akong magpatuloy at lang i-update ito, na kung saan ay zero. At sa halip na ngayon, pupuntahan ko upang ilagay sa ang halaga ng isa. At ngayon ipagpalagay itulak ako ng isa pang number papunta sa stack, tulad ng 51. Well, kailangan kong gumawa ng isa pa pagbabago, na kung saan ay hanggang sa ang laki dalawa. At pagkatapos ay ipagpalagay itulak ako ng isa pa number papunta sa stack tulad ng 61, ngayon ay kailangan ko upang i-update ang laki ng isa pa panahon, at makuha ang halaga ng 3 bilang ang laki. At ngayon ipagpalagay tawag ko pop. Ngayon pop, sa pamamagitan ng convention, ay hindi kumuha ng isang argumento. Sa pamamagitan ng isang stack, ang buong punto ng tray talinghaga ay na hindi mo na kailangang discretion pumunta makakuha ng na tray, maaari lahat ng gagawin mo ay pop ang pinakamataas na isa mula sa stack, dahil lamang. Iyon ay kung ano ang ibig istraktura ng data. 

Kaya sa pamamagitan ng na ang logic kung ako sabihin pop, kung ano ang dumating off? Kaya 61. Kaya kung ano ang tunay ay ang computer pagpunta sa gawin sa memory? Ano ang kailangang gawin ng aking code? Ano ang gusto mong ipanukala palitan namin sa screen? Ano ang dapat baguhin? Paumanhin? Kaya natin mapupuksa ang 61. Kaya ko talagang gawin iyon. At maaari ko mapupuksa ang 61. At pagkatapos ay kung ano ang iba pang mga kailangang mangyari sa pagbabago? Size marahil ay may upang bumalik sa dalawang. At kaya na multa. Ngunit maghintay ng isang minuto, laki ilang sandali ang nakalipas ay tatlo. Gawin ni lamang ng isang mabilis katinuan suriin Hayaan. Paano nakarating ang alam namin na kami ay wanted mapupuksa ang 61? Dahil kami ay pop. At kaya mayroon akong ito pangalawang size property. 

Sandali lang, hindi ako iisip bumalik sa linggo dalawang kapag sinimulan namin ang pakikipag-usap tungkol array, kung saan ito ay lokasyon zero, ito ay lokasyon sa isa, ito ay lokasyon dalawang, ito ay lokasyon tatlo, apat, tila ang relasyon sa pagitan ng laki at ang mga elemento na gusto kong tanggalin mula sa mga array ay lilitaw upang maging kung ano lang? Size minus isa. At kaya na kung paano bilang tao Alam namin ang unang 61 ay dumating. Paano ang pagpunta upang malaman ang mga computer? Kapag ang iyong code, kung saan ikaw ay malamang na nais na gawin size minus isa, kaya tatlong minus isa ay dalawa, at na ay nangangahulugan na gusto naming mapupuksa 61. At pagkatapos ay maaari naming katunayan agad ang laki kaya laki na ngayon napupunta 3-2 lang. At upang maging pedantic lang, pupuntahan ko imungkahi na ako tapos na, i-right? Iminungkahi mong intuitively tama ang dapat ko mapupuksa ang 61. Subalit hindi ako uri ng uri ng tapat na paraan alisan ng 61? Epektibo ko nakalimutan na ito ay aktwal na doon. At sa tingin bumalik sa PSET4, kung nabasa mo na mga artikulo tungkol sa forensics, ang PDF na nagkaroon kami sa iyo guys basahin, o mo ay basahin sa linggong ito para PSET4. Alalahanin na ito ay tunay na dyermeyn sa ang buong ideya ng forensics computer. Ano pangkalahatan ay isang computer ay lamang nakalimutan ito kung saan ang isang bagay ay, ngunit ito ay hindi pumunta sa at tulad ng subukan upang scratch ito sa labas o override mga bits na may mga zero at mga o ilang iba pang mga random na pattern maliban kung mong gawin ang iyong sarili kaya't kusa. Kaya ang iyong Swersey ay karapatan, sabihin mapupuksa 61. Ngunit sa katotohanan, hindi namin kailangang mag-abala. Kailangan lang namin na kalimutan na ito ay doon sa pamamagitan ng pagbabago sa aming laki. 

Ngayon ay mayroong isang problema sa mga ito stack. Kung patuloy kong pagtulak ng mga bagay papunta sa stack, kung ano ang malinaw naman pagpunta sa mangyayari sa loob lamang ng ilang oras sandali? Kami ay pagpunta sa maubusan ng space. At kung ano ang gagawin namin? Uri ng Kami ay screwed. Pagpapatupad na ito ay hindi nagpapahintulot amin palitan ang laki ng array, dahil ang paggamit ng ang syntax na ito, kung ikaw sa tingin bumalik sa dalawang linggo, kapag nakalikha ka na ipinahayag ang laki ng isang array, hindi pa namin kung saan makikita ang isang mekanismo maaari mong baguhin ang laki ng array. At sa katunayan C wala na katangian ay. Kung sinasabi mo bigyan mo ako ng limang Nths, tumawag sa kanila ng mga numero, na ang lahat ng iyong pagpunta sa kumuha ito. Kaya ang ginagawa namin ngayon bilang ng Lunes, mayroon ang kakayahan upang ipahayag ang isang solusyon bagaman, kailangan lang namin na mag-tweak ang kahulugan ng ating stack upang hindi maging ilang mga hard-code na array, ngunit upang mag-imbak lamang ng isang address. 

Ngayon kung bakit ito? Ngayon lang namin na maging komportable sa ang katotohanan na kapag tumatakbo ang aking mga programa, Siguro ako pagpunta sa kailangang tanungin ang mga tao, kung gaano karaming mga numero nais mong i-store? Kaya ang input ay na dumating mula sa isang lugar. Ngunit sa sandaling alam ko na numero, pagkatapos ay maaari ko lamang gamitin kung ano ang gumana upang bigyan sa akin ng isang tipak ng memory? Maaari ko bang gamitin ang malloc. At maaari kong sabihin ang anumang bilang ng mga bytes gusto kong bumalik para sa mga Nths. At lahat ng kailangan kong mag-imbak sa mga numero variable dito sa loob ng struct dapat na kung ano? Ano ang tunay na napupunta sa numero sa sitwasyon na ito? Oo, isang pointer sa unang byte ng na tipak ng memory, o mas partikular, ang mga address sa mga unang ng mga bytes. Hindi mahalaga kung ito ay isa byte o isang bilyong bytes, Kailangan ko lang pag-aalaga tungkol sa mga unang. Dahil kung ano ang garantiya malloc at ang aking mga garantiya operating system, ay na ang mga tipak ng memorya ko makakuha ng, ito ay pagpunta sa maging magkalapit. Mayroong hindi magiging gaps. Kaya kung ko na hiniling para sa 50 bytes o 1000 bytes, lahat sila ay magiging bumalik sa likod sa likod. At hanggang matandaan ko kung gaano kalaki, kung paano marami akong tinanong para sa, lahat ng kailangan kong malaman ay ang unang tulad address. 

Kaya ngayon kami ay may kakayahan sa code. Kahit na, ito ay pagpunta sa kumuha sa amin mas maraming oras upang isulat ito up, maaaring namin ngayon reallocate na memorya sa pamamagitan ng pag-iimbak lamang ng ibang address doon kung gusto namin ng mas malaking o kahit isang mas maliit na tipak ng memory. Kaya dito sa isang kalakalan off. Ngayon makuha namin dynamism. Mayroon pa kaming contiguousness ko na pagtubos. Dahil malloc ay magbibigay sa amin isang magkadikit na tipak ng memory. Ngunit ito ay magiging isang sakit sa leeg para sa amin, ang mga programmer, sa aktwal na code up. Ito ay lamang ng mas maraming trabaho. Kailangan namin ang code na katulad sa kung ano ako ay banging out lamang ng isang sandali ang nakalipas. Very maaaring gawin, ngunit ito ay nagdadagdag ng pagiging kumplikado. At kaya oras na developer, programmer oras ay isa pang mapagkukunan na maaaring kailangan naming gastusin ilang oras upang makakuha ng mga bagong tampok. At pagkatapos ng kurso doon ay isang queue. Hindi namin pumunta sa ito isa sa maraming detalye. Ngunit ito ay lubos na katulad sa espiritu. Maaari ko bang ipatupad ang isang pila, at kanyang kaukulang mga pagpapatakbo, enqueue o dequeue, tulad ng magdagdag o mag-alis, ito lamang ay isang may interes paraan ng pagsabi nito, enqueue o dequeue, tulad ng sumusunod. Maaari ko lang bigyan ang aking sarili ng isang struct na muli ay may array ng isang numero, ang na muli ay may sukat, ngunit bakit kailangan ko ngayon upang subaybayan ang mga harap ng isang queue? Hindi ko kailangang malaman harap ng aking stack. Well, kung ako muli para sa isang queue-- sabihin mahirap lamang code na ito bilang pagkakaroon ng tulad ng limang integer in dito potensyal. Kaya ito ay zero, isa, dalawa, tatlo, apat. Ito ay magiging muli tinatawag na numero. At ito ay tatawaging laki. 

Bakit hindi sapat upang magkaroon ng laki lamang? Well, itulak ni ang mga parehong numero sa ipaalam. Kaya pushed-- ko enqueued ko, o itinulak. Ngayon kukunin ko na enqueue 50, at pagkatapos ay 51, at pagkatapos ay 61, at tuldok tuldok tuldok. Kaya na enqueue. Enqueued ko 50, pagkatapos 51, pagkatapos ay 61. At na mukhang magkapareho sa isang stack kaya sa ngayon, maliban na kailangan ko upang gumawa ng isang pagbabago. Kailangan ko upang i-update ang sukat na ito, kaya pumunta ako mula sa zero sa isa sa 02:58 ngayon. Paano ko dequeue? Ano ang mangyayari sa dequeue? Sino ang dapat dumating off muna ang listahan na ito kung ito ay ang linya sa Apple Store? Kaya 50. Kaya ito ay uri ng trickier oras na ito. Sapagkat huling oras na ito ay sobrang madaling gawin lang size minus isa, Nakukuha ko na ang dulo ng aking array epektibong kung saan ang mga numero ay, ito ay nagtanggal 61. Ngunit hindi ko nais na alisin ang 61. Gusto kong kumuha ng 50, na ay naroon at 5:00 sa line up para sa bagong iPhone o watnat. At kaya mapupuksa 50, ako hindi maaari lamang gawin ito, i-right? Maaari ko bang i-cross out 50. Ngunit sinabi namin namin lamang Hindi mo na kailangang maging kaya anal bilang sa scratch out o itago ang data. Maaari lang namin kalimutan kung saan ito. 

Ngunit kapag binago ko ang aking mga sukat na ngayon upang dalawa, ay ito ng sapat na impormasyon malaman kung ano ang nangyayari sa aking queue? Hindi naman. Tulad ng aking mga sukat ay dalawa, ngunit kung saan magsisimula ang pila, lalo na kung mayroon pa rin ako ang mga parehong mga numero sa memorya. 50, 51, 61. Kaya kailangan kong matandaan ngayon kung saan ang front ay. At gayon na gaya ng iminungkahi up doon, makikita namin lamang na tinatawag na Nth front, na ang unang halaga ang dapat ay kung ano? Zero, isa lamang sa simula ng listahan. Ngunit ngayon bilang karagdagan sa decrementing ang laki, dinagdagan pa lang namin sa harap. Ngayon dito ay isa pang problema. Kaya minsan ako panatilihin ang pagpunta. Ipagpalagay na ito ay ang bilang ng mga tulad ng 121, 124, at pagkatapos, dammit, Ako sa labas ng space. Ngunit maghintay ng isang minuto, hindi ako. Kaya sa puntong ito sa kuwento, Ipagpalagay na ang sukat ay isa, dalawa, tatlo, apat, kaya ipagpalagay na ang laki ay apat, ang harap ay isa, kaya 51 ay sa harap. Gusto kong maglagay ng isa pang numero dito, ngunit, dammit, ako sa labas ng space. Ngunit hindi talaga ako, di ba? Saan ko maaaring ilagay ang ilang mga karagdagang halaga, tulad ng 171? Oo, maaari ko lamang ang uri ng bumalik sa banda roon, di ba? At pagkatapos ay i-cross out ang 50, o patungan lamang ito sa 171. At kung ikaw ay nagtataka kung bakit ang aming mga numero nakuha kaya random, ang mga ito ay karaniwang kinuha ng computer science courses sa Harvard pagkatapos CS50. Ngunit iyon ay isang mahusay na optimization, dahil ngayon Hindi ko na pag-aaksaya ng espasyo. Mayroon pa akong upang tandaan kung paano malaki ang bagay na ito ay total. Ito ay limang total. Dahil hindi ko nais na simulan Sasapawan 51. Kaya ngayon ako pa rin ang out of space, kaya ang parehong problema tulad ng dati. Ngunit maaari mong makita kung paano ngayon sa iyong code, ikaw ay malamang na kailangang magsulat ng isang maliit na mas pagiging kumplikado upang gumawa na mangyari. At sa katunayan, kung ano ang operator sa C marahil ay nagbibigay-daan ikaw ay magically gawin ito ang circularity? Oo ang modulo operator, ang tanda porsyento. Kaya kung ano ang uri ng mga cool tungkol sa isang pila, kahit na panatilihin namin ang pagguhit ng array dahil ang mga ito tulad ng tuwid na mga linya, kung ikaw uri ng isipin ang tungkol sa mga ito pati na curving sa paligid bilang isang bilog, pagkatapos lamang intuitively ito uri ng gumagana sa pag-iisip Tingin ko ang isang maliit na mas malinis. Gusto mo pa rin na ipatupad na model ng isip sa mga code. Kaya hindi na mahirap, sa huli, upang ipatupad, ngunit nawala pa rin namin ang size-- sa halip, ang kakayahan upang baguhin ang laki, maliban kung gagawin namin ito. 

Mayroon kaming upang makakuha ng alisan ng array, kami palitan ito ng isang solong pointer, at pagkatapos ay sa isang lugar sa aking mga code na nakuha ko isang tawag kung ano gumana sa tunay na lumikha ang array na tinatawag na numero? Malloc, o ilang mga katulad function, eksakto. Anumang mga katanungan sa mga stack o queue. Oo? Magandang tanong. Ano modulo nais mong gamitin dito. Kaya sa pangkalahatan, kapag ang paggamit ng mod, gusto mong gawin ito sa laki ng buong istraktura ng data. Kaya ang isang bagay tulad ng lima o kapasidad, kung ito ay pare-pareho, ay malamang na kasangkot. Ngunit ginagawa lamang modulo limang marahil ay hindi sapat, dahil kailangan naming malaman ang ginagawa namin pambalot sa paligid dito o dito o dito. Kaya ikaw ay malamang din sa iyo pagpunta sa nais na kasangkot sa ang laki ng mga bagay, o sa harap na variable rin. Kaya lamang ito relatibong simple arithmetic expression, ngunit modulo ay ang susi sahog. 

Kaya short film kung ikaw ay. Ang isang animation na ang ilang mga kamag-anak sa ibang unibersidad magkasama na kami iniakma para sa talakayang ito. Ito ay nagsasangkot ng Jack-aaral ang mga katotohanan tungkol sa queue at stats. 

FILM: Minsan, nagkaroon ng isang tao na may pangalang Jack. Kapag dumating ito sa paggawa ng mga kaibigan, Jack ay hindi magkaroon ng isang pambihirang kakayahan. Kaya nagpunta Jack na makipag-usap sa mga pinaka-tanyag na tao na alam niya. Pumunta siya sa Lou at nagtanong, Ano ang gagawin ko? Nakita Lou na ang kanyang kaibigan ay talagang nababalisa. Well, siya ay magsimula, lamang tingnan kung paano ka manamit. Huwag kang magkaroon ng anumang mga damit may isang iba't ibang mga hitsura? Oo, sinabi Jack. Ako ba na gawin. Halika sa aking bahay at Kukunin ko ipakita ang mga ito sa iyo. Kaya sila nagpunta off sa Jack. At ipinakita Jack Lou ang kahon kung saan siya nag-iingat sa lahat ng kanyang mga kamiseta, at ang kanyang pantalon, at ang kaniyang medyas. Sinabi Lou, nakikita ko ikaw ay may lahat ng iyong mga damit sa isang pile. Bakit hindi ka magsuot ng ilang iba beses sa sandali? 

Jack sinabi, well, kapag ako tanggalin ang mga damit at medyas, Hugasan ko ang mga ito at ilagay ito ang layo sa kahon. Pagkatapos ay dumating ang susunod na umaga, at up ko hop. Pumunta ako sa kahon at makakuha ng aking mga damit off sa tuktok. Lou mabilis na natanto ang mga problema sa Jack. Tinupad niya ang mga damit, CD, at mga libro sa stack. Kapag siya naabot para isang bagay na basahin o isuot, gusto niya piliin ang mga top libro o underwear. At kapag siya ay tapos na, siya ay ilagay ito sa kanan likod. Bumalik ito ay pumunta, sa itaas ng stack. Alam ko ang solusyon, Sinabi ng isang matagumpay na malakas. Kailangan mong malaman upang simulan ang paggamit ng isang queue. Kinuha Lou damit Jack at nag-hang ang mga ito sa maliit na silid. At kapag siya ay mawawalan ng laman kahon, siya tossed lamang ito. 

Pagkatapos ay sinabi niya, ngayon Jack, sa dulo ng ang araw, ilagay ang iyong mga damit sa kaliwa kapag ikaw ay ilagay ang mga ito ang layo. Pagkatapos bukas ng umaga kapag ikaw makita ang liwanag ng araw, kumuha ng iyong mga damit sa kanan, mula sa dulo ng linya. Huwag mong makita? sinabi Lou. Ito ay kaya maganda. Makikita magsuot lahat nang isang beses bago ka magsuot ng isang bagay nang dalawang beses. At sa lahat ng bagay sa queue sa kanyang closet at shelf, Nagsimula Jack sa pakiramdam lubos na sigurado ng kanyang sarili. Lahat salamat sa Lou at ang kanyang mga kahanga-hangang queue. Tagapagsalita 1: Ang lahat ng mga karapatan, ito ay karapat-dapat sambahin. Kaya kung ano ay talagang pagpunta sa ilalim ng hood ngayon? Na kami ay may mga payo, na kami malloc, na kami ay may kakayahan upang lumikha ng tipak ng memory para sa ating sarili pabago-bago. Kaya ito ay isang larawan namin glimpsed lamang ng ibang mga araw. Kami ay hindi talagang tumira sa mga ito, ngunit ang larawang ito Wala na nangyayari sa ilalim ng hood para sa linggo ngayon. At kaya ito ay kumakatawan, makatarungan isang parihaba na iyong iginuhit namin, memory ng iyong computer. At siguro iyong computer, o CS50 ID, may isang gigabyte ng memorya o RAM o dalawang gigabytes o apat. Ito ay hindi talagang mahalaga. Ang iyong operating system Windows o Mac OS o Linux, mahalagang nagpapahintulot sa iyong mga programa mag-isip na may access dito sa kabuuan ng memory ng iyong computer, kahit na maaari mong patakbuhin ang maramihang mga programa ng sabay-sabay. Kaya sa katotohanan, na hindi talaga gumagana. Ngunit ito ay uri ng isang ilusyon na ibinibigay sa lahat ng iyong mga programa. Kaya kung mayroon kang dalawang gig ng RAM, ito ay kung paano maaaring sa tingin ng mga ito sa computer. 

Ngayon coincidentally, ang isa sa mga bagay na ito, isa sa mga segment ng memorya, ay tinatawag na isang stack. At sa katunayan anumang oras kaya sa ngayon sa pamamagitan ng pagsulat ng code na ikaw ay tinatawag na isang function, halimbawa main. Alalahanin na anumang oras na hindi ko na memory iginuhit computer, Ako palaging gumuhit ng uri ng kalahati ng isang parihaba dito at hindi abala sa pakikipag-usap tungkol sa kung ano ang nasa itaas. Dahil kapag main ay tinatawag na, inaangkin ko na makuha mo ito magtilad ng memory na napupunta down dito. At kung main tinatawag na isang function tulad swap, well mapupunta dito swap. At ito ay lumiliko out, na ang kung saan ito ay nagtatapos up. Sa isang bagay na tinatawag na isang stack sa loob ng memory ng iyong computer. At sa katapusan ng araw, ito ay lamang ng mga address. Ito ay tulad ng byte zero, byte isa, byte 2 bilyon. Pero kung sa tingin mo ang tungkol dito bilang na ito ng hugis-parihaba object, lahat ng ginagawa namin sa bawat time ang tawag namin sa isang function ay layering isang bagong slice ng memory. Kami ay nagbibigay sa mga function na ang isang slice ng kanyang sariling memory upang gumana sa. 

At isipin na ngayon na ito ay mahalaga. Dahil kung mayroon tayo isang bagay tulad ng swap at dalawang lokal na mga variable tulad ng A at B at palitan namin ang mga halaga mula sa isa at dalawa sa dalawang at isa, pagpapabalik na kapag swap nagbabalik, ito ay parang ito slice ng memory ay wala na lang. Sa katotohanan, ito ay pa rin may forensically. At ang isang bagay ay talagang pa rin doon. Ngunit conceptually, ito ay bilang kahit na ito ay ganap na nawala. At kaya main ay hindi alam ang alinman sa mga trabaho na gawa sa na swap function, maliban na lamang kung talagang ito ay lumampas na sa mga argumento sa pamamagitan ng pointer o sa pamamagitan ng reference. Ngayon, ang pangunahing solusyon sa na problema sa swap ay paglipas ng mga bagay sa pamamagitan ng address. Ngunit ito ay lumiliko out, masyadong, kung ano ang na-pagpunta sa itaas na bahagi ng rektanggulo ang lahat ng oras na ito ay pa mayroon pa memory up doon. At kapag ikaw magilas magtalaga ng memory, maging ito man ay sa loob ng GetString, na kami ay ginagawa para sa iyo sa CS50 library, o kung ikaw guys tumawag malloc at hilingin mga operating system para sa isang tipak ng memory, ito ay hindi dumating mula sa stack. Nagmumula ito mula sa ibang lugar sa memory ng iyong computer na tinatawag ang magbunton. At iyan ay hindi anumang naiiba. Ito ay ang parehong RAM. Ito ay ang parehong memory. Ito lang ang RAM na ang bahala doon sa halip ng pababa dito. 

At kaya kung ano ang ibig sabihin nito? Well, kung ang iyong computer ay may takda na halaga ng memory at ang stack ay lumalaking up, kaya magsalita, at magbunton, ayon sa arrow, ay lumalaking pababa. Sa ibang salita, ang bawat oras na tawagan ka malloc, na kayo ay bibigyan ng isang slice ng memorya mula sa itaas, pagkatapos ay marahil isang maliit na mas mababa, at pagkatapos ng isang maliit na mas mababa, sa bawat oras na ikaw ay tumawag malloc, magbunton, ito ay ang paggamit, ay uri ng lumalagong, lumalaking mas malapit at mas malapit sa kung ano? Ang stack. Kaya ito ay tila tulad ng isang magandang ideya? Ibig kong sabihin, kung saan ito ay hindi talagang malinaw ano pa ang maaari mong gawin kung ikaw lamang magkaroon ng isang tiyak na halaga ng memory. Ngunit ito ay tiyak na masama. Mga dalawang arrow ay nasa isang course crash sa isa't isa. 

At ito ay lumiliko out na ang masamang tao, kamag-anak na ay partikular na mahusay sa programming, at sinusubukan mong tadtarin sa mga computer, maaaring kasangkapanin ito katotohanan. Sa katunayan, isaalang-alang ng ipaalam isang maliit na snippet. Kaya ito ay isang halimbawa maaari mong basahin ang tungkol sa mas maraming detalye sa Wikipedia. Susubukan naming ituro sa iyo sa artikulo kung curious. Subalit mayroong isang pag-atake sa pangkalahatan kilala bilang buffer overflow na ay umiiral para sa hangga't ang tao ay nagkaroon ng kakayahan upang mamanipula memory computer, lalo na sa C. Kaya ito ay isang napaka-arbitrary na programa, ngunit sabihin basahin ang mga ito mula sa ilalim up. Main sa argc char star argv. Kaya ito ay isang programa na tumatagal command line argumento. At ang lahat ng mga pangunahing ay tila ay call isang function, tumawag ito F para sa simple. At ito ay ipinapasa sa kung ano? Argv ng isa. Kaya ito ay ipinapasa sa F anuman ang salita ay na nag-type ang user sa prompt pagkatapos ng pangalan ng programa sa lahat. Kaya marami tulad ng Caesar o Vigenere, na maaari mong isipin ang ginagawa sa argv. 

Kaya kung ano ang F? F tumatagal sa isang string bilang sarili nitong argument, AKA isang char star, parehong bagay, bilang isang string. At ito ay tinatawag na nagkataon bar sa halimbawang ito. At pagkatapos char c 12, lamang sa mga tuntunin ng karaniwang tao, ano ang char c bracket 12 ginagawa para sa atin? Ano ang gagawin? Paglaan memory, partikular 12 bytes para sa 12 na karakter. Mismong. At pagkatapos ay ang huling linya, pukawin at kopya, marahil mo na hindi nakita. Ito ay isang string ng kopya function na ang layunin sa buhay ay upang kopyahin ang kanyang ikalawang argument sa kanyang unang argument, ngunit lamang hanggang sa isang tiyak na bilang ng bytes. Ganito ang sabi ng ikatlong argument, kung ilang bytes dapat kopyahin mo? Ang haba ng bar, ano man ang user na nai-type in. At ang mga nilalaman ng bar, na string, ay kinopya sa memory nakatutok sa sa C. 

Kaya ito ay tila uri ng hangal, at ito ay. Ito ay isang contrived halimbawa, ngunit ito ay kinatawan ng isang klase ng pag-atake vectors, isang paraan ng umaatake ang isang programa. Lahat ay multa at mabuti kung ang user mga uri sa isang salita na 11 character o mas kaunti, kasama ang backslash zero. Paano kung ang uri ng user sa higit sa 11 o 12 o 20 o 50 mga character? Ano ang programang ito ng pagpunta sa gawin? Potensyal seg fault. Ito ay pagpunta nang walang taros kopyahin ang lahat sa bar up sa haba nito, na kung saan ay literal lahat ng bagay sa bar, sa address itinuturo sa C. Ngunit C ay may lamang preemptively ibinigay bilang 12 bytes. Ngunit walang karagdagang check. Walang kung kondisyon. Walang error checking dito. 

At kaya kung ano ang program na ito ay pagpunta sa gawin ay lamang taros kopyahin ang isang bagay sa iba. At kaya kung gumuhit namin ito bilang isang larawan, ito ang lamang ng isang salubsob ng puwang sa memorya. Kaya paunawa sa ibaba, kami ay Mayroon ang mga lokal na variable bar. Kaya na pointer na pupuntahan store-- sa halip na ang mga lokal argument na pagpunta sa mga tindahan ang string bar. At pagkatapos lamang na abiso sa itaas nito sa isang stack, dahil sa tuwing hihilingin sa iyo para sa memory sa stack, ito ay pumunta sa isang maliit na piraso sa itaas nito pictorially, paunawa na nakuha namin ang 12 bytes doon. Ang tuktok ng isa sa kaliwa ay C bracket zero at ang tama ilalim ay C bracket 11. Iyan na lamang kung paano ang mga computer pagpunta sa maglatag na ito. Kaya intuitively lang, kung bar ay may higit sa 12 mga character sa kabuuan, kabilang ang backslash zero, kung saan ay ang 12 o ang C bracket 12 pagpunta sa pumunta? O sa halip na kung saan ay ang ika-12 karakter o ang ika-13 na character, bahagi ng isang daan karakter pagpunta sa dulo hanggang sa larawan? Sa itaas o sa ibaba? 

Right, dahil kahit na stack mismo lumalaki paitaas, kapag nakalikha ka na maglagay ng mga bagay-bagay sa ito, ito para sa mga dahilan na disenyo, inilalagay ang memorya mula sa itaas hanggang sa ibaba. Kaya kung mayroon ka ng higit sa 12 bytes, ikaw ay pagpunta sa simulan upang patungan bar. Ngayon na ang isang bug, ngunit ito ay hindi talagang isang malaking pakikitungo. Ngunit ito ay isang malaking pakikitungo, dahil mayroong higit pang mga bagay-bagay na nangyayari sa memory. Kaya narito ang kung paano namin maaaring ilagay hello, upang maging malinaw. Kung nai-type ko sa halo sa prompt. H-E-L-L-O backslash zero, nagtatapos up sa loob ng mga 12 bytes, at nagpapaumanhin kami super safe. Ang lahat ay mabuti. Ngunit kung nagta-type ako ng isang bagay mas matagal, potensyal na ito ay pagpunta sa kilabot sa bar space. Ngunit mas masahol pa, ito ay lumiliko out ang lahat ng oras na ito, kahit na hindi namin na-usapan ang tungkol sa ito, ang mga stack ay ginagamit para sa iba pang mga bagay-bagay. Ito ay hindi lokal na mga variable lamang. 

C ay isang mababang antas ng wika. At ito ang uri ng mga lihim ay gumagamit ng mga stack din tandaan na kapag ang isang function ay tinatawag na, kung ano ang address ay sa mga nakaraang pag-andar, kaya ito ay maaaring lumipat pabalik sa na function. Kaya kapag magpalit pangunahing mga tawag, kabilang ang mga bagay na itinulak papunta sa stack ay hindi lamang swaps lokal na variable, o mga argument nito, lihim din itinulak papunta sa stack na kinakatawan sa pamamagitan ng pulang slice dito, ay ang address ng main pisikal sa memory ng iyong computer, upang kapag swap ay tapos na, ang computer alam na kailangan ko upang bumalik sa pangunahing at tapusin Isinasagawa ang pangunahing pag-andar. Kaya ito ay mapanganib na ngayon, dahil kung uri ng user sa well higit hello, tulad na input ng user clobbers o overwrites na red na seksyon, lohikal na kung ang computer lamang ang pagpunta sa walang taros ipalagay na ang bytes sa na red slice ay ang address kung saan dapat itong bumalik, paano kung ang kalaban ay smart sapat o mapalad sapat na upang ilagay ang isang pagkakasunod-sunod ng mga byte diyan na ganito ang hitsura ng isang address, ngunit ito ay ang address ng code na siya ay nais ang computer upang maipatupad sa halip ng main? 

Sa ibang salita, kung ano ang user ay nagta-type sa prompt, ay hindi lamang isang bagay hindi nakasasama tulad ng hello, ngunit ito ay aktwal na code na katumbas upang tanggalin ang lahat ng mga file ng user na ito? O mag-email ng kanilang mga password sa akin? O simulan ang pag-log sa kanilang mga keystroke, di ba? May ay isang paraan, magtadhana sa ngayon hayaan, na maaaring sila ay nagta-type sa Hindi lang kumusta mundo o sa kanilang mga pangalan, maaaring ito ay mahalagang pumasa sa code, zero at sa buhay, na ang computer pagkakamali para sa parehong code at isang address. Kaya kahit na medyo abstractly, kung ang mga uri ng user sa sapat adversarial code na kami ng tuntuning panlahat dito bilang A. A ay atake o kaaway. Kaya lang masamang bagay-bagay. Hindi namin pakialam tungkol sa numero o ang zero o iyan ngayon, tulad na ang katapusan mo up Sasapawan nito na red na seksyon, mapapansin na ang pagkakasunod-sunod ng bytes. O 835 C zero eight zero. At ngayon habang artikulo ng Wikipedia dito ay iminungkahi, kung ikaw ay tunay na ngayong simulan label ang mga bytes sa computer ang iyong memory, ano ang mga artikulo sa Wikipedia ay minumungkahi ay na, kung ano kung ang address ng na kaliwang tuktok byte ay 80 C 0 3508. 

Sa ibang salita, kung ang masamang tao ay matalino na sapat sa kanyang code upang aktwal na ilagay ang isang numero dito na tumutugon sa address ng code siya iturok sa mga computer, mo maaari lansihin ang computer sa paggawa ng anumang bagay. Inaalis ang mga file, pag-email mga bagay-bagay, sniffing ang iyong trapiko, literal anumang bagay ang maaaring maging iturok sa computer. At sa gayon ang isang buffer overflow pag-atake sa kanyang kaibuturan ay lamang ng isang hangal, tangang pinakamahalaga ng isang array na ay hindi magkaroon ng naka-check na mga hangganan nito. At ito ay kung ano ay sobrang mapanganib at sabay na sobrang malakas sa C ay na sa katunayan tayong pag-access sa kahit saan sa memory. Ito ay nasa sa amin, ang mga programmers, na magsulat ng mga orihinal na code upang suriin ang haba darn ng anumang array na kami ay pagmamanipula. Kaya upang maging malinaw, ano ang ayusin? Kung roll kami pabalik sa ito code, hindi ko dapat lamang baguhin ang haba ng bar, kung ano pa ang dapat kong ma-check? Ano pa ang dapat kong gawin upang maiwasan ang atake na ito ganap? Hindi ko gusto na walang taros lamang sabihin na dapat mong kopyahin ng maraming bytes bilang ay ang haba ng bar. Gusto kong sabihin, kopyahin bilang maraming byte bilang ay sa bar hanggang sa ang inilalaan memory, o 12 maximally. Kaya kailangan ko ng ilang mga uri ng kung kondisyon na ginagawa ng check ang haba ng bar, ngunit kung ito ay lumampas sa 12, lamang mahirap naming code 12 bilang ang pinakamataas na posibleng distance. Kung hindi man ang tinatawag na buffer overflow atake ay maaaring mangyari. Sa ibaba ng mga slide, kung gusto mong malaman upang basahin ang nalalaman ay ang aktwal na orihinal na artikulo kung gusto mo na tingnan. 

Ngunit ngayon, sa gitna ng mga presyo binayaran dito ay inefficiencies. Kaya na ay isang mabilis mababang pagtingin antas kung ano problema ay maaaring lumitaw ngayon na kami may access sa memory computer. Ngunit ang isa pang problema namin na stumbled sa Lunes ay isa lamang ang kawalan ng kaalaman ng isang naka-link na listahan. Kami ay pabalik sa haba ng panahon. Hindi na kami ay may isang magkadikit na array. Wala kaming random access. Hindi namin maaaring gamitin ang square bracket pagtatanda. Kami literal na kailangang gumamit ng isang habang loop tulad ng isa na sinulat ko ng ilang sandali ang nakalipas. Ngunit sa Lunes, inaangkin namin na makakaya namin gumapang pabalik sa kaharian ng kahusayan pagkamit ng isang bagay na logarithmic siguro, o pinakamahusay pa, marahil kahit na isang bagay na tinatawag na pare-pareho ang panahon. Kaya kung paano namin gawin iyon sa pamamagitan ng paggamit ng mga bagong mga kasangkapan, mga address, mga payo, at threading bagay sa aming mga sarili? Well, ipagpalagay na dito, ang mga ito ay isang bungkos ng mga numero na nais naming mag-imbak sa isang istraktura ng data at mga search mahusay. Maaari ganap namin rewind upang week dalawang, itapon ang mga ito sa isang array, at hanapin ang mga ito gamit ang binary paghahanap. Hatiin at mapaglabanan. At sa katunayan ang iyong sinulat binary paghahanap sa PSET3, kung saan mo ipatupad ang programa find. Pero alam mo kung ano. Mayroong uri ng isang mas matalino na paraan ng paggawa nito. Ito ay isang maliit na mas sopistikadong at ito marahil ay nagbibigay-daan sa amin upang makita kung bakit binary search ay kaya mas mabilis. Una, sabihin ipakilala ipaalam ang paniwala ng isang puno. Aling kahit na sa katotohanan puno uri ng lumaki na tulad nito, sa mundo ng mga computer agham uri ng lumalaki sila pababa tulad ng isang pamilya tree, kung saan mayroon kang ang iyong mga lolo at lola o dakilang grandparents o watnat sa tuktok, ang apo at ang matriarch ng pamilya, isa lang tinatawag na root, node, sa ibaba na kung saan ay ang kanyang mga anak, ibaba kung saan ay ang kanyang mga anak, o kaapu-apuhan nito sa mas pangkalahatang. At sinuman sa pader off sa ibaba ng pamilya tree, bukod sa pagiging bunsong sa pamilya, ay maaari ding maging generically lamang tinatawag na ang mga dahon ng punong kahoy. 

Kaya ito ay isang bungkos lamang ng mga salita at mga kahulugan para sa isang bagay na tinatawag na isang puno sa computer science, marami tulad ng isang family tree. Ngunit mayroong mga may interes anyo ng mga puno, isa rito ay tinatawag na isang binary puno ng paghahanap. At maaari mong uri ng mang-ulol bukod sa kung ano ang ginagawa ang bagay na ito. Well, ito ay binary sa kung ano ang kahulugan? Saan nanggagaling ang binary mula dito? Paumanhin? Ito ay hindi kaya magkano ang isang mag-o. Ito ay higit pa ang bawat isa sa mga node ay walang higit sa dalawang mga bata, tulad ng nakikita natin dito. Sa pangkalahatan, ang isang tree-- at ang iyong mga magulang at mga lolo at lola maaaring magkaroon ng maraming mga bata o Mga Apo pati talagang gusto nila, at iba halimbawa may kami ay may tatlong bata off kanang kamay na node, ngunit sa isang binary puno, isang node ay may zero, isa, o dalawang bata maximally. At iyon ay isang magaling na ari-arian, dahil kung ito ay nilimitahan sa pamamagitan ng dalawang, kami ay pagpunta sa ma- makakuha ng isang maliit log base dalawang action na nangyayari dito sa huli. Kaya kami ay may isang bagay na logarithmic. Ngunit higit pa sa na sa isang sandali. Puno Search ay nangangahulugan na ang mga numero ay nakaayos tulad na kaliwang anak halaga ay mas malaki kaysa sa root. At karapatan ng bata nito ay mas malaki kaysa sa root. Sa ibang salita, kung kumuha ka ng alinman sa mga nodes, ang mga lupon sa larawan na ito, at tumitingin sa kaliwa nito anak at kanang bata nito, ang unang dapat na mas mababa kaysa sa, dapat na mas malaki kaysa sa pangalawa. Kaya katinuan check 55. Ito ay iniwan ang bata ay 33. Ito ay mas mababa kaysa sa. 55, right anak nito ay 77. Ito ay mas malaki kaysa sa. At iyon ay isang recursive kahulugan. Maaari naming suriin ang bawat isa sa mga iyon nodes at ang parehong pattern ay hold. 

Kaya kung ano ang magaling sa isang binary puno ng paghahanap, ay na ang isa, maaari naming ipatupad may isang struct, gusto lamang ito. At kahit na kami ay ibinabato maraming mga istraktura sa iyong, ang mga ito ay medyo intuitive ngayon sana. Ang syntax ay arcane para bang pa rin, ngunit ang mga nilalaman ng isang node sa ito context-- at panatilihin namin gamit ang salitang node, maging ito man ay isang parihaba sa screen o sa isang bilog, ito lamang ang ilang mga pangkaraniwang lalagyan, sa kasong ito ng isang puno, tulad ng isa Nakita namin, kailangan namin ng isang integer sa bawat isa sa mga nodes at pagkatapos ay kailangan ko ng dalawang mga payo na tumuturo sa kaliwa anak at kanang bata, ayon sa pagkakabanggit. Kaya na kung paano namin maaaring ipatupad na sa isang struct. At kung paano maaaring ako ipatupad ito sa code? Well, sabihin kumuha ng isang mabilis tingnan ang mga ito maliit na maliit na halimbawa. Ito ay hindi sa pagganap, ngunit hindi ko na kopyahin at ilagay sa istraktura na. At kung ang aking pag-andar para sa isang binary puno ng paghahanap ay tinatawag na paghahanap, at ito ay tumatagal ng dalawang argumento, isang integer N at isang pointer sa isang node, kaya isang pointer sa puno o isang pointer sa ugat ng isang puno, paano ko pumunta tungkol sa paghahanap para N? Well, una, dahil ako pagharap sa mga payo, Pupunta ako upang gawin ang isang katinuan check. Kung puno equals katumbas null, ay N sa punong kahoy na ito o hindi sa punong kahoy na ito? Hindi ito maaaring maging, tama? Kung ako ay nakalipas na null, may walang may. Ako maaaring pati na rin lamang walang taros sabihin bumalik false. Kung ako magbibigay sa iyo wala, tiyak kong hindi maaari mahanap ang anumang bilang N. Kaya ano pa ang maaari ko Tingnan ngayon? Pupunta ako sa sabihin na rin ng iba pa kung N ay mas mababa sa kahit na ano ay sa puno ng buko na ako ng kamay N value. Sa ibang salita, kung ang bilang ako hinahanap, N, ay mas mababa kaysa sa node na Naghahanap ako sa. At ang mga node Naghahanap ako sa ay tinatawag na puno, at pagpapabalik mula sa mga nakaraang mga halimbawa upang makakuha ng sa halaga sa isang pointer, Gamitin ko ang arrow pagtatanda. Kaya kung N ay mas mababa sa puno arrow N, gusto kong conceptually pumunta kaliwa. Paano searching ko express kaliwa? Upang maging malinaw, kung ito ay ang mga larawan na pinag-uusapan, at ako ay lumipas na kataas-taasan palaso na nakaturo pababa. Iyon ang aking puno pointer. Ako sa pagturo sa ugat ng puno. At Naghahanap ako sabihin, ang bilang 44, nagkataon. Ay 44 mas mababa sa o mas malaki kaysa sa 55 malinaw naman? Kaya ito ay mas mababa kaysa sa. At kaya ito kung ang condition ay nalalapat. Kaya conceptually, kung ano ang gusto kong maghanap susunod kung ako naghahanap para sa 44? Oo? 

Eksakto, gusto kong maghanap sa kaliwang bata, o kaliwa sub-puno ng mga larawan na ito. At sa katunayan, sabihin sa akin sa pamamagitan ang larawan down dito para sa sandali lamang, dahil Hindi ko ma-scratch ito out. Kung sisimulan ko dito at 55, at Alam ko na ang halaga ng 44 Naghahanap ako ng ay upang sa kaliwa, ito ay uri ng mga tulad ng mapunit ang libro ng telepono sa kalahati o mapunit ang tree sa kalahati. Wala na akong pakialam tungkol sa ang buong kalahati ng mga puno. At gayon pa man, nang mausisa sa mga tuntunin ng istraktura, ang bagay na ito sa paglipas dito na nagsisimula sa 33, na sa kanyang sarili ay isang binary puno ng paghahanap. Sinabi ko ang salitang recursive bago dahil sa katunayan na ito ay isang istraktura ng data na sa pamamagitan ng kahulugan ay recursive. Maaari mong magkaroon ng isang puno na ito malaki, ngunit ang bawat isa sa kanyang mga anak ay kumakatawan sa isang puno lamang ng isang maliit na mas maliit. Sa halip na ito sa pagiging lolo o lola, ngayon ay ang ina lamang or-- Hindi ko say-- hindi mom o ama, na magiging kakaiba. Sa halip na ang dalawang mga bata doon ay magiging tulad ng kapatid na lalaki at kapatid. Ang isang bagong henerasyon ng pamilya tree. Ngunit structurally, ito ay ang parehong mga ideya. At ito ay lumiliko out mayroon akong isang function na kung saan maaari ba akong maghanap ng isang binary search tree. Ito ay tinatawag na paghahanap. Ako sa paghahanap para N sa puno arrow kaliwa iba kung N ay mas malaki sa halaga na ako ay kasalukuyang sa. 55 sa mga kuwento ng ilang sandali ang nakalipas. Mayroon akong isang function na tinatawag na search na maaari ko lamang ipasa N na ito at recursively maghanap mga sub-puno at return lamang kahit na ano na sagot. Iba Pa Mayroon akong ilang huling base kaso dito. 

Ano ang huling kaso? Tree ay alinman null. Ang halaga ng alinman Naghahanap ako ay mas mababa kaysa ito o mas mataas kaysa sa na o katumbas ng mga ito. At maaari ko bang sabihin pantay pantay-pantay, ngunit lohikal ito ay katumbas lang sinasabi ng ibang tao dito. Kaya totoo ay kung paano mahanap ko ang isang bagay. Kaya sana ito ay isang kahit na mas nakakahimok halimbawa kaysa sa tangang pag-andar na palatandaan Ginawa namin ang ilang mga aralin sa likod, kung saan ito ay tulad ng madaling upang gamitin ang isang loop upang mabilang ang lahat ng mga numero mula sa isang sa N. Dito sa isang istraktura ng data na mismo ay recursively tinukoy at recursively iginuhit, ngayon kami may kakayahan upang ipahayag ang ating sarili sa code na mismo ay recursive. Kaya ito ay ang parehong code dito. 

Kaya kung ano ang iba pang mga problema na maaari naming malutas? Kaya isang mabilis na hakbang ang layo mula puno para sa sandali lamang. Dito ay, sabihin, ang bandila German. At mayroong malinaw na ang isang pattern upang i-flag ito. At mayroong maraming mga flags sa mundo na ay kasing simple ng ito sa mga tuntunin ng kanilang mga kulay at mga pattern. Ngunit ipagpalagay na ito ay naka-imbak bilang .GIF, O isang JPEG, o bitmap, o isang ping, anumang graphical na format ng file na kung saan hindi ka pamilyar, ang ilan ay hindi namin naglalaro sa mga in PSET4. Ito ay hindi mukhang kapaki-pakinabang sa mga tindahan ng black pixel, black pixel, black pixel, tuldok, tuldok, tuldok, ang maramihang mga black pixels para sa unang scanline, o hilera, pagkatapos ng buong bungkos ng ang parehong, pagkatapos ng buong bungkos ng parehong, at pagkatapos ay isang buong bungkos ng pulang pixels, pulang pixels, red pixels, at pagkatapos ng isang buong grupo ng mga kulay-dilaw na mga pixel, yellow, di ba? 

May tulad ng kawalan ng kaalaman dito. Paano gagawin mo intuitively compress ang bandila German kung ang pagpapatupad ng mga ito bilang isang file? Tulad ng kung anong impormasyon ang maaari naming hindi abala sa pag-iimbak sa disk upang upang bawasan ang aming laki ng file mula sa tulad ng isang megabyte sa isang kilobyte, isang bagay mas maliit? Kung saan namamalagi ang kalabisan para maging malinaw? Ano ang maaari mong gawin? Oo? Mismong. Bakit hindi sa halip na tandaan ang kulay ng bawat darn pixel tulad ng iyong ginagawa sa PSET4 na may format na bitmap file, bakit hindi kumakatawan ikaw lamang ang pinakakaliwa haligi ng pixels, halimbawa ng grupo ng mga black pixels, ng grupo ng pula, at ng grupo ng yellow, at pagkatapos lamang sa paanuman encode ang ideya ng ulitin ito 100 ulit o ulitin ito 1,000 ulit? Saan 100 o 1000 ay lamang ng isang integer, kaya mo maaaring makakuha ng malayo na may lamang ng isang numero sa halip ng daan-daan o libu-libo ng mga karagdagang pixels. At sa katunayan, na kung paano namin maaaring i-compress ang bandila German. At Ngayon kung ano ang tungkol sa mga Pranses bandila? At isang maliit na ilang mga uri ng mental na ehersisyo, na kung saan bandila maaaring compress more on disk? Ang German bandila o ang Pranses flag, kung lubos naming diskarte na? Ang bandila German, dahil mayroong mas horizontal kalabisan. At sa pamamagitan ng disenyo, maraming mga graphical file format gawin sa katunayan trabaho linya bilang scan horizontally. Sila ay maaaring magtrabaho patayo, lamang ang sangkatauhan nagpasya taon na nakalipas na bibigyan namin ng karaniwang tingin ng row bagay sa pamamagitan ng hilera sa halip ng haligi sa pamamagitan ng column. Kaya nga kung ikaw ay upang tingnan ang mga file laki ng isang German bandila at isang Pranses flag, kaya hangga't ang resolution ay ang parehong, ang parehong lapad at taas, ang isang ito dito ay magiging mas malaki, dahil ikaw kailangang ulitin ang iyong sarili ng tatlong beses. Kailangang tukuyin mo ang blue, ulitin sa iyong sarili, puti, ulitin ang iyong sarili, pula, ulitin ang iyong sarili. Hindi ka maaaring pumunta lamang ang lahat ang daan sa kanan. At bilang isang bukod, na gumawa i-clear ang compression sa lahat ng dako, kung ang mga ito ay apat na mga frame mula sa isang video-- mo maaaring isipin na ang isang pelikula o video ay karaniwang tulad ng 29 o 30 mga frame sa bawat segundo. Ito ay tulad ng isang maliit na tingnan ang mga libro na kung saan kayo makita lamang ng imahe, larawan, imahe, larawan, image lang sobrang bilis kaya mukhang ang mga aktor sa screen ay gumagalaw. Narito ang isang gumulo pukyutan sa tuktok ng isang bungkos ng mga bulaklak. At bagaman maaari itong maging uri ng mahirap na makita sa unang tingin, ang tanging bagay na gumagalaw sa pelikula na ito ay ang pukyutan. 

Ano ang pipi tungkol sa pag-iimbak hindi naka-compress video? Ito ay uri ng isang pag-aaksaya sa mga tindahan ng video bilang apat na halos magkapareho mga imahe na naiiba lamang sa abot ng kung saan ang mga laywan ay. Maaari mong itapon ang pinaka ng impormasyon na iyon at tandaan lamang, halimbawa, ang unang frame at ang huling frame, key frames kung na sa iyo kailanman narinig ang mga salita, at mag-imbak lamang sa gitna kung saan ang mga laywan ay. At hindi mo na kailangang tindahan ng lahat ng mga rosas, at ang asul, at ang green halaga pati na rin. Kaya ito ay upang lamang sabihin na compression ay lahat ng dako. Ito ay isang pamamaraan madalas naming gamitin o mang-ahas na mga araw. 

Ngunit paano mo compress ang text? Paano mo pumunta tungkol sa pigain text? Well, ang bawat isa sa mga character sa Ascii ay isa byte, o walong bits. At iyon ay uri ng pipi, di ba? Dahil malamang type ka A at E at I at ng O at U ng isang pulutong mas madalas kaysa sa gusto W o Q o Z, depende sa wika kung saan sumusulat ka tiyak. At kaya bakit kami gamit walong bits para sa bawat titik, kabilang ang hindi bababa sa popular na mga titik, i-right? Bakit hindi gamitin ang mas kaunting mga bits para ang sobrang sikat na mga titik, tulad ng E, ang mga bagay na hulaan mo una sa gulong ng kapalaran, at gamitin ang higit pang mga piraso ng ang mas popular na titik? Bakit? Dahil lang kami ng pagpunta sa gamitin ang mga ito ng mas madalas. 

Well, ito ay lumiliko out na magkaroon ng mga pagtatangka na ginawa upang gawin ito. At kung ang pagpapabalik sa iyo mula sa grade school o high school, Morse code. Morse code ay tuldok at gitling na maaaring maging ipinapadala kasama ng isang wire bilang tunog o signal ng ilang mga uri. Ngunit Morse code ay isang napakabilis malinis. Ito ay uri ng isang binary system in na ikaw ay may mga tuldok o gitling. Ngunit kung makakita ka ng, halimbawa, dalawang tuldok. O kung sa tingin mo bumalik sa operator na napupunta tulad beep, beep, beep, beep, pagpindot ng isang maliit na mag-trigger na nagpapadala ng isang senyas, kung ikaw, ang tatanggap, na natatanggap ng dalawang mga tuldok, kung ano ang mensahe na natanggap mo? Ganap na arbitrary. 

I? I? O kung ano about-- o ako? Siguro, ito ay lamang ng dalawang mga karapatan E ni? Kaya may problemang ito ng decodability may Morse code, kung saan maliban kung ang tao sa pagpapadala sa iyo ng mga mensahe talagang pause upang maaari mong ayusin ng makita o marinig ang puwang sa pagitan ng mga titik, ito ay hindi sapat lamang upang magpadala ng isang stream ng mga zero at mga, o tuldok at gitling, dahil may kalabuan. E ay isang single dot, kaya kung ikaw makakita ng dalawang tuldok o marinig ng dalawang tuldok, marahil ito ay dalawang E o marahil ito ay isa I. Kaya kailangan namin ng isang sistema na ang isang maliit na mas matalino kaysa sa. Kaya ang isang lalaki na nagngangalang Huffman taon ang nakalipas ay dumating up na may eksaktong ito. Kaya lamang kami ay pagpunta upang kumuha ng isang mabilis na sulyap at kung paano ang puno ay dyermeyn sa ito. Ipagpalagay na ito ay ilang tangang mensahe na nais mong ipadala, binubuo ng lamang A, B, C D'ni S at E ni, ngunit may isang pulutong ng mga kalabisan dito. Hindi ito ay nilalayong maging Ingles. Ito ay hindi naka-encrypt. Ito ay lamang ng tangang mensahe na may maraming pag-uulit. Kaya kung aktwal mong bilangin ang lahat ng mga A, E ni B, C, D, at, narito ang ang dalas. 20% ng mga titik ay A, ang 45% ng mga titik mga E, at ang tatlong iba pang mga frequency. Kami ay mabibilang up doon manu-mano at ginawa ang matematika. 

Kaya ito ay lumiliko out na Huffman, ilang oras ang nakalipas, natanto na, alam mo ano, kung sisimulan ko na gusali isang puno, o gubat ng mga puno, kung ikaw ay, tulad ng sumusunod, maaari kong gawin ang mga sumusunod. Pupunta ako upang bigyan ng node sa bawat sa mga titik na ako pag-aalaga tungkol at ako pagpunta sa mga tindahan ng sa loob ng na node ang frequency bilang isang lumulutang point halaga, o maaari mo itong gamitin ng isang N, masyadong, ngunit lamang namin makikita gumamit ng isang float dito. At ang mga algorithm na iminungkahi na siya ay na kayo tumagal ito ng gubat ng solong node puno, kaya super maikling puno, at simulan mo pagkonekta sa kanila sa bagong grupo, bagong mga magulang, kung ikaw ay. At gawin mo ito sa pamamagitan ng pagpili ng dalawang pinakamaliit na frequency sa isang pagkakataon. Kaya ko kinuha ng 10% at 10%. Lumikha ako ng bagong node. At ang tawag ko sa bagong node sa 20%. 

Ano ang dalawang nodes pagsamahin ko susunod? Ito ay isang maliit na hindi maliwanag. Kaya may ilang mga sulok ng mga kaso sa isaalang-alang, ngunit upang panatilihin medyo bagay, Pupunta ako upang pumili ng 20% ​​- Ngayon huwag pansinin ko ang mga anak. Pupunta ako upang pumili ng 20% ​​at 15% at gumuhit ng dalawang bagong mga gilid. At ngayon kung saan ang dalawang nodes huwag lohikal kong pagsamahin? Huwag pansinin ang lahat ng mga bata, ang lahat ng mga apo, tingnan lamang sa mga ugat ngayon. Ano ang dalawang nodes ko itali? Dalawang Point at 0.35. Kaya ipaalam sa akin gumuhit ng dalawang bagong mga gilid. At pagkatapos lamang ang nakuha ko ang isa kaliwa. Kaya narito ang isang puno. At ito ay iguguhit kusa upang tumingin ng uri ng pretty, ngunit mapapansin na ang mga gilid ay may din ay may label na zero at isa. Kaya lahat ng kaliwang gilid ay zero nagkataon, ngunit patuloy. Ang lahat ng mga karapatan gilid ay bago. 

At kaya kung ano ipinanukalang Hoffman ay, kung nais mong kumatawan ng isang B, sa halip na kumakatawan sa bilang 66 bilang isang Ascii kung saan ay walong buong bits, alam mo kung ano, kung store mga pattern zero, zero, zero, zero, dahil iyon ang landas mula sa aking mga puno, tree Mr. Huffman ni, sa dahon mula sa mga ugat. Kung nais mong i-store ang isang E, sa pamamagitan ng kaibahan, hindi magpadala ng walong bits na kumakatawan sa isang E. Sa halip, magpadala ng kung ano ang pattern ng bits? One. At kung ano ang magaling tungkol sa ito ay na E ay ang pinaka-popular na mga titik, at gumagamit ka ng mga pinakamaikling code para dito. Ang susunod na pinaka popular Mukhang sulat tulad nito ay A. At kaya kung gaano karaming mga bits niya iminungkahing gamit para sa na? Zero, isa. 

At dahil ito ay ipinatupad bilang punong ito, para sa ngayon hayaan mo akong magtadhana mayroong walang kalabuan bilang sa Morse code, dahil ang lahat ng mga titik na mahalaga sa iyo ay nasa dulo ng mga gilid. Kaya na ang isa lamang sa application ng isang puno. Ito is-- at makikita ko iwagayway ang aking mga kamay sa ito kung paano mo maaaring ipatupad ito bilang isang istraktura C. Kailangan lang namin upang pagsamahin isang simbolo, tulad ng isang pansamantalang trabaho, at ang dalas sa kaliwa at kanan. Ngunit Tingnan natin ang dalawang ipaalam huling halimbawa na makikita mo makakuha ng lubos na pamilyar sa matapos quiz zero sa hanay ng problema limang. 

Kaya may mga istraktura ng data kilala bilang isang hash table. At isang hash table ay uri ng palamig na ito ay may mga bucket. At ipagpalagay na mayroong apat na timba dito, lamang ng apat na blangko ang puwang. Narito ang isang deck ng mga baraha, at dito ay club, pala, club, diamonds, club, diamonds, club, diamonds, clubs-- kaya ito ay ang random. Puso, kaya hindi ako hearts-- bucketizing lahat ng mga input dito. At isang pangangailangan hash table upang tumingin sa iyong input, at pagkatapos ay ilagay ito sa isang tiyak maglagay batay sa kung ano ang nakikita mo. Ito ay isang algorithm. At ako ay gumagamit ng isang super simpleng visual algorithm. Ang pinakamahirap na bahagi ng kung saan ay alala kung ano ang mga larawan ay. At pagkatapos ay may apat na total bagay. 

Ngayon ang mga stack ay lumalaki, na ay isang sinadya disenyo bagay dito. Ngunit ano pa ang maaari kong gawin? Kaya talagang dito kami ay may isang grupo ng mga lumang libro pagsusulit paaralan. Ipagpalagay na ang isang grupo ng mga pangalan mag-aaral ay sa dito. Narito ang isang mas malaking hash table. Sa halip ng apat na bucket, Ako ay may, sabihin natin 26. At hindi namin nais na pumunta humiram 26 mga bagay-bagay mula sa labas [? Annenberg?], Kaya narito ang limang na kumakatawan A pamamagitan Z. At kung ako makita ang isang mag-aaral na ang pangalan ay nagsisimula sa A, Pupunta ako upang ilagay ang kanyang quiz doon. Kung ang isang tao ay nagsisimula sa C, sa banda roon, A-- talaga, ay hindi nais na gawin iyon. B napupunta sa paglipas dito. Kaya ko na nakuha ng A at B at C. At ngayon narito ang isa pang Ang mag-aaral. Ngunit kung ito hash table ay ipinatupad sa isang array, Uri ng ako screwed sa puntong ito, right? Ako uri ng kailangan upang ilagay ito sa isang lugar. 

Kaya isang paraan ang maaari kong malutas ito ay, ang lahat ng karapatan, A ay abala, B ay abala, C ay abala. Pupunta ako sa ilagay sa kanya sa D. Kaya sa una, ako ay may random instant access sa bawat isa sa mga bucket para sa mga mag-aaral. Ngunit ngayon ito ay uri ng devolved sa isang bagay na sa guhit, dahil kung gusto ko upang maghanap para sa isang tao Pangalan na nagsisimula sa A, i-check ko dito. Ngunit kung ito ay hindi ang isang mag-aaral na Naghahanap ako ng, Ako uri ng may upang simulan ang paglagay ng tsek ang mga balde, dahil ang aking ginawa ay isang uri ng linear suriing mabuti ang istraktura ng data. Isang hangal na paraan ng sinasabi tingnan lamang para sa unang magagamit pagbubukas, at ilagay bilang isang plan B, kaya na magsalita, o plano D sa kasong ito, ang halaga sa lokasyong iyon sa halip. Ito ay upang lamang na kung na sa iyo Nakakuha ng 26 mga lokasyon at walang mga mag-aaral may pangalan Q o Z, o isang bagay tulad na, hindi bababa sa ikaw ay gumagamit ng space. 

Ngunit na namin nakita pa matalino solusyon dito, tama? Ano ang gusto mong gawin sa halip kung mayroon kang isang banggaan? Kung ang dalawang tao ay may ang pangalan A, ano ang gagawin ay isang mas matalinong o higit pa madaling gamitin na solusyon na lamang paglagay A kung saan ang D ay dapat na maging? Bakit hindi ko na lang pumunta sa labas [? Annenberg?], tulad ng malloc, isa pang node, ilagay ito dito, at pagkatapos ay ilagay na isang mag-aaral dito. Kaya na ako ay may mahalagang ilang mga uri ng isang array, o marahil mas elegante bilang hindi namin simula upang makita ang isang listahan ng mga link. 

At kaya ng hash table ay isang istraktura na maaaring maging ganito ang hitsura lamang, ngunit mas cleverly, ka ng isang bagay na tinatawag na hiwalay na pagdudugtong, kung saan ang isang hash table lubos na lamang ay isang array, ang bawat isa sa na ang mga elemento ay hindi isang numero, ay mismong isang listahan ng mga link. Kaya na makakuha ka ng sobrang mabilis na access pagpapasya kung saan upang sirain ang iyong halaga sa. Karamihan tulad ng sa halimbawa sa card, Ginawa ko ang sobrang mabilis na mga desisyon. Hearts mapupunta dito, diamonds mapupunta dito. Parehong dito, A dito napupunta, D mapupunta dito, B mapupunta dito. Kaya napakabilis na look-ups, at kung mangyari sa iyo upang tumakbo sa isang case kung saan nakuha mo na ang mga banggaan, dalawang mga tao na may parehong pangalan, kung sa gayon simulan mo na lang pag-link ang mga ito nang magkakasama. At siguro mong panatilihin ang pinagsunod-sunod ang mga ito alpabeto, marahil hindi mo gusto. Ngunit hindi bababa sa ngayon kami ay ang dynamism. Kaya sa isang banda mayroon kaming sobrang mabilis pare-pareho ang oras, at ang uri ng haba ng panahon kasangkot kung ang mga naka-link na mga listahan simulan upang makakuha ng isang maliit na mahaba. 

Kaya ito uri ng isang walang isip, geeky joke taon na ang nakakaraan. Sa CS50 hack-a-Thon, kapag mag-aaral-check in, ilang TF o CA sa bawat taon sa palagay nito ay nakatatawa upang ilagay up isang tanda na ito, kung saan ito lamang ay nangangahulugan na ang iyong pangalan ay nagsisimula sa isang A, pumunta sa ganitong paraan. Kung ang iyong pangalan ay nagsisimula may isang B, pumunta this-- OK, ito ay nakatatawa baka mamaya sa semester. Subalit mayroong isa pang paraan ng paggawa nito, masyadong. Bumalik sa na. 

Kaya may structure na ito. At ito ang aming huling istraktura para sa araw na ito, na kung saan ay isang bagay na tinatawag na isang trie. T-R-I-E, na para sa ilang kadahilanan ay maikli para sa pagkuha, ngunit ito ay tinatawag trie. Kaya ang isang trie ay isa pang kawili-wiling amalgam ng isang pulutong ng mga ideya. Ito ay isang puno, na kung saan namin nakita bago. Ito ay hindi isang binary puno ng paghahanap. Ito ay isang puno na may anumang bilang ng mga bata, ngunit ang bawat isa sa mga anak sa isang trie ay isang array. Isang hanay ng mga sukat, sabihin, 26 o marahil 27 kung gusto mong suportahan nagigitlingan mga pangalan o apostrophes sa mga pangalan ng mga tao. 

At kaya ito ay isang istraktura ng data. At kung titingnan mo mula sa tuktok hanggang sa ibaba, tulad ng kung ikaw tumingin sa itaas node doon, M, ay tumuturo sa pinakakaliwa bagay doon, na kung saan pagkatapos A, X, W, E, L, L. Ito ang lamang ng isang istraktura ng data na nagkataon ay pag-iimbak ng mga pangalan ng mga tao. At Maxwell ay naka-imbak sa pamamagitan ng mga sumusunod na lamang isang landas ng array na array na array. Ngunit kung ano ang amazing tungkol sa isang trie ay na iyon, kung saan ang isang listahan ng mga link at kahit na isang array, ang pinakamahusay na kailanman namin nakuha ay sa haba ng panahon o logarithmic oras ng pagtingin isang tao up. Sa data na istraktura ng isang trie, kung aking mga istraktura ng data ay may isang pangalan sa loob nito at Naghahanap ako ng Maxwell, ako pagpunta upang mahanap sa kanya ng medyo mabilis. Inaasahan ko lamang para sa M-A-X-W-E-L-L. Kapag ito istraktura ng data, sa pamamagitan ng kaibahan, kung N ay isang milyon, kung may isang milyong pangalan sa istraktura ng data, Maxwell ay pa rin pagpunta sa maging natutuklasan matapos lamang M-A-X-W-E-L-L hakbang. At David-- D-A-V-I-D na mga hakbang. Sa ibang salita, sa pamamagitan ng pagbuo isang istraktura ng data na nakuha ko ang lahat ng mga array, ang lahat ay suportahan ang kanilang sarili random access, Maaari ko bang magsimula naghahanap up tao pangalan ng paggamit ng isang halaga ng oras na proporsyonal sa hindi ang bilang ng mga bagay sa istraktura ng data, tulad ng isang milyong mga umiiral na mga pangalan. Ang halaga ng oras na aabutin sa akin upang mahanap M-A-X-W-E-L-L sa ganitong istraktura ng data ay proportional na hindi ang laki ng mga istraktura ng data, ngunit sa ang haba ng pangalan. At makatotohanan ang pangalan hinahanap namin up ay hindi kailanman pagpunta na mabaliw sa haba. Siguro isang tao ay may isang 10 na karakter pangalan, 20 pangalan ng character. Ito ay tiyak na may hangganan, di ba? May isang tao sa Earth na may pinakamahabang posibleng pangalan, ngunit na ang pangalan ay isang pare-pareho haba ng halaga, i-right? Hindi ito nag-iiba sa anumang kahulugan. Kaya sa ganitong paraan, na namin nakakamit ng isang istraktura ng data iyon ay pare-pareho ang time look-up. Ito ay tumagal ng isang bilang ng mga hakbang depende sa haba ng input, ngunit hindi ang bilang ng mga pangalan sa istraktura ng data. Kaya kung double namin ang bilang ng mga pangalan sa susunod na taon mula sa isang bilyon sa dalawang bilyon, paghahanap ng Maxwell ay pagpunta sa tumagal ang eksaktong parehong bilang ng mga pitong hakbang upang mahanap sa kanya. At kaya kami ay tila na magkaroon ng nakakamit ang aming banal na Kopita ng pagtakbo ng oras. 

Kaya ang isang pares ng mga mabilis announcements. Pagsusulit zero ay paparating na. Higit pa sa na sa website ng kurso sa loob ng susunod na ilang mga araw. Lunes ng lecture-- ito ay isang holiday dito sa Harvard sa Lunes. Hindi ito sa New Haven, kaya kami ay ang pagkuha ng mga klase sa New Haven para sa mga panayam sa Lunes. Lahat ng bagay ay kumuha at stream ng live na tulad ng dati, ngunit magtapos sa ngayon hayaan may isang 30 segundong clip tinatawag na "Deep saloobin" sa pamamagitan ng Daven Farnham, na ay inspirasyon ng nakaraang taon sa pamamagitan ng Sabado "Deep saloobin" Night Live ni sa pamamagitan ng Jack na madaling gamitin, na kung saan dapat gumawa na ngayon ng kahulugan. 

Pelikula: At ngayon, "Deep Mga saloobin "sa pamamagitan ng Daven Farnham. Hash table. 

Tagapagsalita 1: Ang lahat ng mga karapatan, na ito para sa ngayon. Kami ay makikita mo sa susunod na linggo. 

DOUG: Upang makita ang mga ito sa aksyon. Kaya sabihin kumuha ng isang pagtingin sa na ngayon. Kaya dito, mayroon kaming isang unsorted array. 

IAN: Doug, maaari mong sige, at i-restart na ito para lang isang segundo, please. Lahat ng mga karapatan, mga camera ay lumiligid, kaya pagkilos sa tuwing ikaw ay handa na, Doug, OK? DOUG: Lahat ng mga karapatan, kaya kung ano ang aming Mayroon dito ay isang unsorted array. At ako may kulay na ang lahat ng mga elemento red upang ipahiwatig na ito ay, sa katunayan, unsorted. Kaya isipin na ang unang bagay na aming ay namin ayusin ang kaliwa kalahati ng array. Pagkatapos ayusin namin ang karapatan kalahati ng array. At ya-da, ya-da, ya-da, sumanib namin ang mga ito nang magkakasama. At kami ay may isang ganap na pinagsunod-sunod array. Kaya na kung paano pagsamahin ang mga uri gumagana. 

IAN: Whoa, aba, aba, cut, cut, cut, cut. Doug, maaari mong hindi lamang ya-da, ya-da, ya-da, ang iyong paraan sa pamamagitan ng pagsasama-uuri. 

DOUG: ginawa ko lang. Ayos lang. Humihingi kami ng magandang pumunta. Lamang panatilihin ang rolling Hayaan. Kaya pa rin, 

IAN: Ikaw ay may na ipaliwanag mas ganap kaysa sa na ito. Iyan na lamang hindi sapat. DOUG: Ian, hindi tayo kailangan upang bumalik sa isa. Ayos lang. Kaya pa rin, kung patuloy naming may merge-- Ian, hindi namin sa gitna ng paggawa ng pelikula. 

IAN: alam ko. At hindi namin maaari lamang ya-da, ya-da, ya-da, sa pamamagitan ng buong proseso. Ikaw ay may na ipaliwanag kung paano ang dalawang panig makakuha ipinagsama-sama. 

DOUG: Ngunit hindi namin nai ipinaliwanag kung paano ang dalawang sides-- 

IAN: Lamang ka na ipinapakita kanila ng isang merge array. DOUG: Alam nila ang proseso. Ang mga ito ay multa. Na wala na kami ng mahigit sa sampung beses. 

IAN: lalaktawan mo tama lang sa ibabaw nito. Kami ay pagpunta bumalik sa isa, ikaw hindi maaari ya-da mo, ya-da sa ibabaw nito. Sige, bumalik sa isa. 

DOUG: Mayroon akong upang bumalik sa pamamagitan ng lahat ng mga slide? Diyos ko. Ito ay tulad ng ika-anim na oras, Ian. Ayos lang. 

IAN: Lahat ng karapatan. Handa ka na? Great. Action.