[MUSIC nagpe-play] ANDI PENG: Maligayang pagdating sa week 6 ng section. Lumihis namin mula sa aming standard time na seksyon ng Martes hapon na ito kaibig-ibig na umaga Linggo. Salamat sa iyo para sa lahat na sumama sa akin ngayon, pero sa totoo lang, isang ikot ng papuri. Iyan ay isang medyo malaking pagsisikap. Halos ako ay hindi kahit na gawin itong up sa oras, ngunit ito ay OK. Kaya alam ko na ang lahat ng sa iyo may ginawa lamang ito sa pagsusulit. Una sa lahat, maligayang pagdating sa tingnan ang bahagi ng na. Pangalawa, makikita namin makipag-usap tungkol dito. Susubukan naming makipag-usap tungkol sa pagsusulit. Susubukan naming makipag-usap tungkol sa kung paano ang iyong ginagawa sa klase. Ikaw ay fine. Mayroon akong ang iyong mga pagsusulit para sa sa iyo sa dulo ng dito, kaya kung gusto mong guys na kumuha ng isang tumingin sa ito, lubos fine. Kaya mabilis bago tayo magsimula, ang mga agenda para sa araw na ito ay ang mga sumusunod. Tulad ng iyong nakikita, hindi namin talaga mabilis na pagpapaputok sa pamamagitan ng isang buong grupo ng mga istruktura ng data tunay, tunay, tunay mabilis. Kaya bilang gayon, hindi ito magiging super interactive ngayon. Makikita ito lamang maging akin uri ng abot mga bagay-bagay na sa iyo, at kung malito ko sa inyo, kung ako pagpunta masyadong mabilis, ipaalam sa akin. Sila ay lamang ng iba't-ibang data kaayusan, at bilang bahagi ng iyong pset para sa mga ito paparating na linggo, makikita mo hilingin sa iyo na ipatupad ang isa sa kanila, marahil ang dalawa sa them-- dalawa sa kanila sa iyong pset. OK, kaya ako lamang ang pagpunta sa magsimula sa ilang mga announcements. Kami ay pumunta sa paglipas ng mga stack at queues higit pa sa malalim kaysa sa kung ano ang ginawa namin bago ang pagsusulit. Kami ay pumunta sa paglipas ng naka-link listahan muli, muli, mas malalalim na kaysa sa kung ano kami ay nagkaroon ng bago ang pagsusulit. At pagkatapos ay gagamitin namin makipag-usap tungkol hash mga talahanayan, mga puno at mga pagsusubok, na ay ang lahat ng kaakit-akit na kinakailangan para sa iyong pset. At pagkatapos kami ay pumunta sa paglipas ng ilang helpful tips para sa pset5. OK, kaya quiz 0. Average ay isang 58%. Ito ay napaka-mababa, at kaya mo guys lahat Ginawa tunay, tunay mabuti alinsunod na iyon. Medyo marami, patakaran ng hinlalaki ay na kung ikaw ay sa loob ng isang standard na paglihis ng mga ibig sabihin ng lalo na dahil hindi namin sa isang mas umaliw seksyon, ikaw ay ganap na multa. Ikaw ay nasa track. Maganda ang buhay. Alam ko ito ay nakakatakot na isipin na Tulad ng isang 40% sa mga pagsusulit na ito ang nakuha ko. Pupunta ako sa mabibigo klase na ito. Pangako ko sa iyo, hindi ka pagpunta sa mabibigo sa klase. Ikaw ay lubos na fine. Para sa mga mo na nakuha sa ibabaw ang ibig sabihin, kahanga-hanga, kahanga-hanga, tulad ng, sineseryoso magaling. Mayroon akong mga ito sa akin. Huwag mag-atubili na dumating makakuha ng mga ito sa dulo ng seksyon. Ipaalam sa akin kung mayroon kang anumang mga isyu, mga katanungan sa kanila. Kung idagdag namin ang iyong iskor mali, ipaalam sa amin. OK, kaya pset5, ito ay isang tunay na kakaiba linggo para sa Yale sa kamalayan na ang aming pset ay dahil Miyerkules sa tanghali kasama ang late na araw, kaya ito ay aktwal na theoretically dahil Martes sa tanghali. Marahil hindi isa tapos sa Martes sa tanghali. Iyan ay lubos fine. Kami ay pagpunta sa may mga oras ng opisina ngayong gabi pati na rin ang Lunes ng gabi. At ang lahat ng mga seksyon sa linggong ito ay talagang i-turn papunta workshops, kaya huwag mag-atubiling mag-pop in anumang mga seksyon na nais mo, at ang mga ito ay uri ng mini-pset workshops para sa tulong sa mga iyon. Kaya dahil dito, ito ay ang tanging seksyon na kung saan kami ay pagtuturo materyal. Ang lahat ng mga iba pang mga seksyon ay nagbibigay-diin eksklusibo sa tulong para sa pset. Oo? Madla: Kung nasaan oras ng opisina? ANDI PENG: Oras ng opisina tonight-- oh, magandang katanungan. Sa tingin ko oras ng opisina ngayong gabi ay nasa Teal o sa Commons. Kung tingnan mo online CS50 at pumunta ka sa oras ng opisina, dapat ay mayroong isang iskedyul na ay nagsasabi sa iyo kung saan ang lahat ng mga ito ay. Alam ko mag-ngayong gabi o bukas ay tial, at sa tingin ko ay magkaroon kayo ng commons para sa iba pang mga gabi. Di ako sigurado. Magandang tanong. Lagyan ng check sa CS50. Cool, anumang mga katanungan tungkol sa iskedyul para sa susunod tulad ng tatlong araw? Pangako ko sa inyo guys gaya ni David sinabi, ito ay ang tuktok ng burol. Ikaw guys ay halos doon. Just tatlong higit pang mga araw. Kumuha ng doon, at pagkatapos ay gagamitin namin ang lahat ng dumating down. Magkakaroon kami ng isang magandang CS-free break. Maligayang pagbabalik. Ipapakita namin sumisid sa web programming at pag-unlad, mga bagay na napaka-masaya kumpara sa ilan sa mga iba pang psets. At makikita ito ay ginaw, at kakailanganin naming maraming masaya. Magkakaroon kami ng mas maraming kendi. Paumanhin para sa kendi. Nakalimutan ko ang kendi. Ito ay isang magaspang umaga. Kaya ka guys ay halos doon, at ako ay talagang maipagmamalaki mo guys. OK, kaya stack. Sino ang mga mahal sa tanong tungkol sa Jack at ang kanyang mga damit sa pagsusulit? Walang sinuman? OK, na fine. Kaya mahalagang hangga't maaari mong picture Jack, ito tao dito, nagmamahal upang gawin ang mga damit out sa tuktok ng stack, at inilalagay ito pabalik papunta stack pagkatapos siya ay tapos na. Kaya sa ganitong paraan, hindi siya parang pagkuha ng sa ibaba ng stack sa kanyang damit. Kaya ito uri ng naglalarawan ang pangunahing istraktura ng data kung paano ang isang stack ay ipinatupad. Mahalaga, sa tingin ng isang stack bilang ng anumang stack ng mga bagay kung saan mo ilagay ang mga bagay papunta sa itaas, at pagkatapos ay pop mo ang mga ito out mula sa tuktok. Kaya LIFO ay ang acronym tulad namin upang use-- Huling In, First Out. At kaya tatagal sa sa itaas ng stack ay ang unang isa na dumating out. At upang ang dalawang termino gusto namin upang iugnay may mga tinatawag na push at pop. Kapag itulak mo ang isang bagay papunta sa stack, at pop mo ito back up. At kaya ako hulaan ito ay uri ng isang abstract konsepto, para sa inyo na nais na makita tulad ng isang aktwal na pagpapatupad ng mga ito sa tunay na mundo. Ilan sa inyo ang may nakasulat na sanaysay siguro tulad ng isang oras bago ito ay dahil, at hindi mo sinasadyang natanggal ang isang malaking tipak ng mga ito, tulad ng aksidenteng? At pagkatapos ay kung ano ang control gawin ginagamit namin upang ilagay ito pabalik? Control-Z, oo? Control-Z, kaya ang halaga ng beses na Control-Z ay nai-save ang aking buhay, Iniligtas aking asno, sa bawat panahon na ipinatupad sa pamamagitan ng isang stack. Totoo lahat ng mga impormasyon na sa iyong Word document, ito ay makakakuha ng hunhon at pop sa kalooban. At kaya mahalagang kailan mo tanggalin ang anumang bagay, pop mo ito back up. At pagkatapos ay kung kailangan mo ito muli, ikaw itulak ito, na kung saan ay kung ano ang Control-C. At kaya tunay na function mundo ng kung paano simpleng istraktura ng data maaaring makatulong sa iyong pang-araw araw na buhay. Kaya ang isang struct ay ang paraan na kami ang tunay na lumikha ng isang stack. Type naming tukuyin struct, at pagkatapos ay tawag namin ito stack sa ilalim. At sa loob ng stack, kami ay may dalawang mga parameter na maaari naming mahalagang manipulahin, kaya kami ay may char kapasidad star string. Lahat na ito ay ginagawa ay ang paglikha ng isang array na maaari kaming mag-imbak ng anumang nais mo na kung saan maaari naming matukoy ang kapasidad nito. Kapasidad Ay lang ang max na halaga ng mga item na maaari naming ilagay sa array na ito. size int ay ang counter na mapigil subaybayan kung gaano karaming mga item ay kasalukuyang sa stack. Kaya pagkatapos ay maaari naming subaybayan ang, A, pareho kung paano malaki ang aktwal na stack ay, at, B, kung gaano karami ng stack aming pinuno dahil hindi namin nais pag-apaw sa kung ano ang aming kapasidad ay. Kaya halimbawa, ang kaibig-ibig tanong ay sa iyong pagsusulit. Mahalaga kung paano gawin namin itulak papunta sa tuktok ng isang stack. Medyo simple. Kung titingnan mo ang mga ito, babagtasin namin ito. Kung [hindi marinig] size-- Tandaan, kahit kailan mo nais na ma-access ang anumang mga parameter sa loob ng isang struct, gawin mo ang pangalan ng struct.parameter. Sa kasong ito, s ay pangalan ng ating stack. Gusto naming ma-access ang laki ng mga ito, kaya ginagawa namin s.size. Kaya't hangga't ang laki ay hindi katumbas ng kapasidad o hangga't bilang na ito ay mas mababa kaysa sa kapasidad, alinman na nais magtrabaho dito. Gusto mong ma-access ang loob ng iyong stack, kaya s.strings, at ikaw ay pagpunta sa ilagay na bagong numero ng na gusto mong ipasok sa doon. Sabihin lang kami nais na ipasok int n papunta sa stack, maaari naming gawin s.strings, bracket, s.size katumbas n. Dahil laki ay kung saan namin kasalukuyang nasa stack kung kami ay pagpunta sa itulak ito sa, namin ma-access lamang nasaan ang laki ay, ang kasalukuyang kabuuan ng stack, at itulak namin ang int n papunta ito. At pagkatapos ay nais naming tiyakin na kami ay incrementing din laki ng n, upang maaari naming subaybayan ang mga na namin idinagdag ng dagdag na bagay sa stack. Ngayon kami ay may isang mas mataas na laki. Ito dito magkaroon ng kahulugan sa lahat ng tao, kung paano lohikal ito gumagana? Ito ay uri ng mabilis. Madla: Maaari kang pumunta sa ibabaw ang s.stringss.strings [s.size] muli? ANDI PENG: Oo naman, kaya kung ano ang ginagawa s.size kasalukuyang bigyan kami ng? Madla: Ito ay ang kasalukuyang laki. ANDI PENG: Eksakto, kaya ang kasalukuyang index na ang aming mga sukat ay, at kaya gusto naming ilagay ang bagong integer na gusto naming ipasok sa s.size. Ba na magkaroon ng kahulugan? Dahil s.strings, ang lahat na ay ang pangalan ng array. Lahat ng ito ay ay ma-access ang array sa loob ng aming struct, at kaya kung gusto naming ilagay n sa index na, maaari naming ma-access lamang ito paggamit ng mga braket s.size. Cool. Lahat ng mga karapatan pop,, Pseudocode ko ito para sa iyo guys, ngunit katulad na konsepto. Ba na magkaroon ng kahulugan? Kung ang sukat ay mas malaki kaysa sa zero, at pagkatapos ay malaman na nais mong kumuha ng isang bagay out dahil kung ang laki ay hindi mas mataas sa zero, at pagkatapos ay walang kinalaman sa stack. Kaya gusto mo lamang i-execute ang code na ito, ito ay maaari lamang pop kung may isang bagay sa pop. Kaya kung ang laki ay mas malaki kaysa sa 0, kami ay binawasan ang laki. Pagbawas namin ang laki at pagkatapos ay bumalik kahit na ano ay sa loob ng mga ito dahil sa pamamagitan ng pop, gusto naming access ang anumang ay naka-imbak sa index ng tuktok ng stack. Lahat ng bagay ay magkaroon ng kahulugan? Kung ginawa ko sa inyo guys isulat ito out, ay maaaring isulat ito sa iyo guys? OK, ka guys ay maaaring i-play sa paligid sa mga ito. Huwag mag-alala kung hindi mo makuha ang mga ito. Wala kaming oras upang code ito ngayon dahil hindi namin Nakakuha ng maraming mga kaayusan pumunta sa pamamagitan ng, ngunit mahalagang pseudocode, tunay, tunay na katulad sa itulak. Sundan lang sa kahabaan ng logic. Tiyakin na ikaw ay pag-access sa lahat ng mga mga tampok ng iyong struct tama. Oo? Madla: ba ang mga slide at ang buong bagay na maging up ngayon-ish? ANDI PENG: Laging, yep. Pupunta ako sa subukan upang ilagay ito up tulad ng isang oras pagkatapos. Kukunin ko i-email David, David ay susubukan na ilagay ito up tulad ng isang oras matapos na ito. OK, kaya pagkatapos naming ilipat ito sa iba pang mga kaibig-ibig na istraktura ng data na tinatawag na isang queue. Tulad nang nakikita dito sa iyo guys, isang pila, para sa mga British sa gitna natin, lahat ng ito ay ay isang linya. Kaya salungat sa kung ano sa tingin mo ang isang stack ay, isang pila ay kung ano mismo lohikal na sa tingin mo ay ito. Ito ay gaganapin sa pamamagitan ng mga patakaran ng FIFO, na kung saan ay Una Sa, Unang Out. Kung ikaw ay ang unang isa sa mga linya, ikaw ay ang unang isa na dumating sa labas ng linya. Kaya kung ano ang aming nais na tawag ito ay dequeueing at enqueueing. Kung nais namin na magdagdag ng isang bagay sa aming pila, enqueue namin. Kung gusto naming dequeue, o kumuha ng isang bagay ang layo, dequeue namin. Kaya parehong kahulugan na hindi namin uri ng paglikha elemento nakapirming-size na tayo Maaaring mag-imbak ng ilang mga mga bagay-bagay, ngunit maaari din namin baguhin kung saan kami ay paglalagay parameter sa loob ng mga ito batay sa kung anong uri ng functionality gusto namin. Kaya stack, gusto naming huling isa, N na ang unang isa out. Queue ay gusto namin ang unang bagay sa na maging ang unang bagay out. Kaya ang struct-type tukuyin, tulad ng makikita mo, ito ay Medyo naiiba mula sa kung ano ang stack ay dahil lamang hindi kami ay may upang panatilihin subaybayan kung saan ang laki sa kasalukuyan ay, Gusto din namin upang subaybayan ang ulo pati na rin kung saan kami ay kasalukuyang ay. Kaya sa tingin ko mas madali kung gumuhit ko ito up. Kaya ni isipin namin nakuha ng isang queue ipaalam, kaya sabihin natin na ang ulo ay karapatan dito. Ang ulo ng linya, sabihin lang sabihin na kasalukuyang doon, at gusto naming ipasok isang bagay sa queue. Pupunta ako sa tawagan size mahalagang ay ang parehong bagay tulad ng likod o hulihan, sa dulo ng kung saan ang iyong queue. Sabihin lang ang laki ay karapatan dito. Kaya kung paano gumagana ang isa feasibly ipasok ang isang bagay sa isang queue? Ano index ang gusto namin upang ilagay kung saan gusto naming ipasok sa. Kung ito ang simula ng iyong queue at ito ay ang dulo ng ito o ang laki ng mga ito, kung saan tayo gustong idagdag ang susunod na object? Madla: [hindi marinig] ANDI PENG: Eksakto, na nais mong idagdag ito depende sa ikaw ay may nakasulat na ito. Alinman ito ay blangko o ng nasa blangko. Kaya nais mong idagdag ang mga ito ay malamang na dito dahil kung ang laki is-- kung ang mga ito ay puno ng lahat, na nais mong upang idagdag ito dito mismo, di ba? At kaya na, habang tunay, tunay simple, hindi lubos na laging tama dahil ang pangunahing pagkakaiba sa pagitan ng isang queue at isang stack ay na ang queue Maaari talagang manipulahin upang ang mga pagbabago sa ulo depende sa kung saan mo nais sa simula ng iyong cue upang magsimula. At bilang isang resulta, ang iyong mga buntot ay din ng pagpunta sa pagbabago. At kaya tingnan sa ang code na ito sa ngayon. Bilang ka guys ay nagtanong din sa isulat sa pagsusulit, enqueue. Siguro makikita namin makipag-usap sa pamamagitan ng kung bakit ang sagot ay kung ano iyon. Hindi ko lubos na magkasya ang linyang ito sa isa, ngunit mahalagang ito piraso ng code ay dapat na sa isang linya. Spend tulad ng 30 segundo. Kunin ang hitsura, at makita kung bakit ito ay ang paraan na ito ay. Tunay, halos katulad struct, tunay, tunay katulad na istraktura bilang ang nakaraang stack maliban para marahil isang linya ng code. At na isang linya ng code ang tumutukoy sa mga pag-andar. At talagang iiba isang pila mula sa isang stack. Sinuman na nais na kumuha ng isang ulos sa nagpapaliwanag kung bakit na sa iyo Nakakuha ito komplikadong bagay in dito? Nakikita natin ang pagbabalik ng ating kahanga-hangang kaibigan modulus. Bilang ka guys ay malapit nang dumating upang makilala sa programming, halos anumang oras na kailangan mo ng isang bagay sa wrapper sa paligid ng anumang bagay, modulus ay magiging ang paraan upang gawin ito. Kaya alam na, ang sinuman na nais subukan na nagpapaliwanag na linya ng code? Oo, ang lahat ng mga sagot ay tinanggap at maligayang pagdating. Madla: Ikaw ba ay nakikipag-usap sa akin? ANDI PENG: Oo. Madla: Oh, walang sorry. ANDI PENG: OK, kaya sabihin maglakad sa pamamagitan ng code na ito. Kaya kapag sinusubukan mong magdagdag ng isang bagay papunta sa isang pila, sa kaibig-ibig na kaso na ang ulo mangyayari upang maging dito mismo, ito ay tunay madali para sa amin pumunta lamang sa dulo ipasok ang isang bagay, i-right? Ngunit ang buong punto ng isang pila ay na ang ulo ang tunay na maaari dynamically magbago depende sa kung saan kami gusto sa simula ng aming q na, at dahil dito, ang buntot ay din ng pagpunta sa pagbabago. At kaya isipin na hindi ang mga ito ay nakatayo sa hilera, ngunit sa halip ito ay ang queue. Ipagpalagay natin na ang ulo ay karapatan dito. Ipagpalagay natin na ang ating queue mukhang ito. Kung gusto naming shift kung saan sa simula ng linya ay, sabihin natin Nilipat namin ulo sa ganitong paraan at sukat dito. Ngayon nais namin na magdagdag ng isang bagay sa ito queue, ngunit bilang maaari mong makita ang isang lalaki, ito ay hindi kaya simple bilang na lamang magdagdag ng kahit na ano ay pagkatapos ng laki dahil pagkatapos kami maubusan ng hangganan ng aming mga aktwal na array. Saan ang gusto naming talagang magdagdag ay dito. Iyan ang kagandahan ng isang queue ay na sa amin, biswal na ito Mukhang ang linya napupunta tulad nito, ngunit kapag naka-imbak sa isang istraktura ng data, bigyan nila ito bilang tulad ng isang cycle. Ito ay uri ng bumabalot sa palibot sa harap na sa parehong paraan na maaari ring balutin ng isang linya sa paligid depende sa kung saan mo man nais na simula ng linya na. At kaya kung tumagal kami ng isang tumungo dito, sabihin sabihin gusto naming lumikha ng isang function na tinatawag enqueue. Nais naming magdagdag ng int n sa na q. Kung q.size q-- namin ang tawag na ang aming data structure-- kung ang aming queue.size hindi katumbas ng kapasidad o kung ito ay mas mababa kaysa sa kapasidad, q.strings ay ang array sa loob ng aming q. Kami ay pagpunta upang i-set na katumbas ng q.heads, na kung saan ay dito mismo, kasama ang q.size modulus ng kapasidad, na balutin sa amin pabalik sa paligid dito. Kaya sa ganitong halimbawa, index ng ulo ay 1, di ba? Ang index ng laki ay 0, 1, 2, 3, 4. Kaya maaari naming gawin 1 plus 4 modulus pamamagitan ng aming kapasidad na kung saan ay 5. Ano ang ibig na magbibigay sa atin? Ano ang index na dumating sa labas ng ito? Madla: 0. ANDI PENG: 0, kung saan mangyayari sa maging dito mismo, at kaya gusto naming ma upang ipasok sa karapatan dito. At kaya ito equation dito uri ng lang gumagana sa anumang mga numero ng depende sa kung saan ang iyong mga ulo at ang iyong mga sukat ay. Kung alam mo kung ano ang mga bagay na ito ay, alam mo eksakto kung saan mo nais na ipasok kahit na ano ay pagkatapos ng iyong queue. Ba na magkaroon ng kahulugan sa lahat ng tao? Alam ko ang uri ng isang utak teaser lalo na dahil ito dumating sa mga resulta ng iyong pagsusulit. Ngunit sana sa lahat ng tao ngayon ay maaaring maunawaan kung bakit ito solusyon o ito function na ay ang paraan na ito ay. Sinuman isang bit hindi maliwanag sa mga iyon? SIGE. At kaya ngayon, kung ikaw Nais upang dequeue, ito ay kung saan ang aming mga ulo ay paglilipat dahil kung kami ay upang dequeue, hindi kami gumawa ng off sa dulo ng q. Gusto naming mag-alis ng ulo, di ba? Kaya bilang isang resulta, ang ulo ay pagpunta sa pagbabago, at iyon ay kung bakit kapag enqueue mo, nakuha mo na subaybayan ang kung saan ang iyong ulo at ang iyong mga laki ay para ma-ipasok sa tamang posisyon. At kaya kapag dequeue mo, Pseudocode ito rin ako out. Huwag mag-atubiling kung nais mong upang tangkain coding na ito out. Gusto mong ilipat ang ulo, di ba? Kung Nais kong dequeue, ako nais ilipat ang ulo sa ibabaw. Ito ay ang ulo. At ang aming mga kasalukuyang laki ng gagawin ibawas dahil hindi na kami may apat na mga elemento sa array. Kami lamang magkaroon ng tatlo, at pagkatapos ay nais naming upang bumalik anumang ay naka-imbak sa loob ng ulo dahil gusto naming gawin ito halaga sa labas kaya halos kapareho sa stack. Basta ikaw ay dinadala mula sa ibang lugar, at kailangan mong muling italaga ang iyong pointer sa ibang lugar bilang isang resulta. Logically, sundin ang lahat? Great. OK, kaya kami ay pagpunta sa makipag-usap ng kaunti higit pa sa malalim tungkol sa mga listahan ng link dahil ang mga ito ay tunay, tunay na mahalaga para sa iyo sa kurso ng na ito linggo psets. Mga listahan ng naka-link, tulad ng sa iyo guys matandaan, ang lahat ng mga ito ay mga nodes na nodes ng mga tiyak mga halaga ng pareho ang halaga at isang pointer na-link na magkasama sa pamamagitan ng mga payo. At upang ang struct sa kung paano lumikha kami ng isang node dito ay namin Mayroon int n, na kung saan ay kahit na ano ang halaga sa isang tindahan o string n o kahit anong gusto mong tawag na ito, ang mga char star n. Struct node star, na kung saan ay ang pointer na nais mong magkaroon sa bawat node, ikaw ay pagpunta sa may na pointer point patungo sa susunod. Magkakaroon ka ng ulo ng isang listahan ng mga link na pagpunta upang tumuro sa mga natitirang bahagi ng ang mga halaga para sa at iba pa hanggang sa huli mong maabot ang dulo. At ito huling node ay lamang pagpunta sa hindi magkaroon ng isang pointer. Ito ay pagpunta upang tumuro sa null, at na kapag alam mo mo na pindutin ang dulo ng iyong listahan na naka-link ay kapag ang iyong huling pointer ay hindi point sa kahit ano. Kaya kami ay pagpunta sa pumunta ng kaunti pa sa malalim tungkol sa kung paano ang isa gagawin posibleng maghanap ng isang listahan ng mga link. Tandaan kung ano ang ilan sa mga drawbacks ng mga listahan ng link mga bersikulo ng isang array patungkol paghahanap. Isang hanay ng maaari mong binary paghahanap, ngunit kung bakit hindi mo maaaring gawin na sa isang listahan ng mga link? Madla: Dahil sila ay konektado sa lahat, ngunit hindi mo masyadong alam kung saan [Hindi marinig]. ANDI PENG: Oo, eksakto kaya tandaan na ang kinang ng isang array ay ang katunayan na kami ay random access memory kung saan kung gusto ko ang mga halaga mula sa index anim, maaari ko lamang sabihin index anim, bigyan ako ng halagang iyon. At iyon ay dahil array ay pinagsunod-sunod sa isang magkadikit na puwang ng memory sa isang lugar, kung saan ang uri ng mga listahan ng link ay sapalarang kahalong lahat sa paligid, at ang tanging paraan na maaari mong mahanap ang isa ay sa pamamagitan ng isang pointer na nagsasabi sa iyo ang address kung saan na ang susunod na node ay. At kaya bilang isang resulta, ang tanging paraan sa paghahanap sa pamamagitan ng isang listahan ng mga link ay linear paghahanap. Dahil hindi ko alam kung saan mismo ang ika-12 na halaga sa naka-link na listahan ay, Kailangan ko bang tawirin ang kabuuan ng na listahan ng mga link sa isa sa pamamagitan ng isa mula sa ulo sa unang node, sa ikalawang node, sa ikatlong node, lahat ng mga paraan pababa hanggang sa wakas ako makakuha na kung saan na node Naghahanap ako ay. At kaya sa puntong ito, ang paghahanap sa isang listahan ng mga link ay palaging n. Ito ay palaging n. Ito ay palaging sa haba ng panahon. At upang ang mga code na kung saan ang kami ipatupad ito, at ito ay isang bit bago para sa iyo guys dahil ikaw guys ay hindi tunay na usapan tungkol sa o kailanman nakita mga payo sa kung paano sa paghahanap sa pamamagitan ng mga payo, kaya kami ay sa pamamagitan ng paglalakad ito tunay, tunay dahan-dahan. Kaya bool search, kanan, Sabihin isipin gusto naming ipaalam upang lumikha ng isang function na tinatawag na paghahanap na nagbabalik ng tunay kung nakita mo ang halaga sa loob ng mga naka-link list, at ito ay nagbabalik ng mga maling paraan. Listahan Node star ay kasalukuyan lamang ang pointer sa unang item sa iyong listahan ng naka-link. int n ay ang halaga na ikaw ay na naghahanap para sa listahang iyon. Kaya node star pointer katumbas listahan. Ito ay nangangahulugan na kami ay pagtatakda at paglikha ng isang pointer sa na unang node sa loob ng listahan. Ang bawat sa akin? Kaya kung kami ay upang pumunta bumalik dito, nais kong magkaroon ng initialize isang pointer na tumuturo sa ang ulo ng kahit anong listahan na. At pagkatapos ay sa sandaling makakuha ka down na dito, habang pointer ay hindi katumbas null, nang sa gayon ay ang mga loop na kung saan tayo magiging sa dakong huli traversing ang natitirang bahagi ng aming listahan dahil kung ano mangyayari kapag pointer katumbas null? Alam namin na have-- namin Madla: [hindi marinig] ANDI PENG: Eksakto, upang malaman namin na naabot na namin ang dulo ng listahan, i-right? Kung ikaw ay bumalik dito, ang bawat node dapat na tumuturo sa ibang node at iba pa hanggang maabot mo sa huli sa likod o hulihan ng iyong listahan ng naka-link, na kung saan ay may isang pointer na lamang ay hindi point kahit saan maliban sa no. At kaya talaga alam mo na ang iyong listahan ay mayroon pa rin up hanggang pointer ay hindi katumbas ng null dahil sa sandaling ito ay katumbas ng null, Alam mo ba na walang higit pang mga bagay-bagay. Kaya na ang loop na kung saan hindi namin pagpunta sa may ang aktwal na paghahanap. At kung ang pointer-- mo makita na uri ng mga arrow na function doon? Kaya kung pointer mga puntos upang n, kung ang pointer sa n katumbas ng ay katumbas n, kaya na nangangahulugan na kung ang ang pointer na kayo na naghahanap para sa dulo ng bawat node ay talagang katumbas ng halaga naghahanap ka ng, at pagkatapos ay gusto mong bumalik totoo. Kaya talaga, kung ikaw ay nasa isang node na ay ang halaga na iyong hinahanap para sa, alam mo na ikaw ay naging matagumpay na mai maghanap. Kung hindi man, nais mong itakda iyong pointer sa susunod na node. Iyon ay kung ano ang ginagawa na linya dito. Pointer katumbas pointer susunod. Ang bawat makita kung paano na gumagana? At mahalagang kayo ay pagpunta sa makatarungan tawirin ang kabuuan ng listahan, reset ang iyong pointer sa bawat oras hanggang sa wakas pindutin ang dulo ng listahan. At alam mo na walang mga higit pang mga node sa paghahanap sa pamamagitan ng, at pagkatapos ay maaari kang bumalik false dahil alam mo na, oh, well, kung ako ay ma-search sa pamamagitan ng kabuuan ng listahan. Kung sa halimbawang ito, kung nais ko upang hanapin ang halaga ng 10, at sisimulan ko sa ulo, at Ako sa paghahanap ng lahat ng mga paraan down, at sa huli nakuha ko na ito, kung saan isang pointer na tumuturo sa null, Alam ko na, crap, hulaan ko 10 ay wala sa ang listahan na ito dahil hindi ko mahanap ang mga ito. At ako sa dulo ng listahan. At sa kaso na kilala mo Pupunta ako sa bumalik false. Hayaan na magbabad sa para sa ilang sandali. Ito ang magiging pretty mahalaga para sa iyong pset. Ang lohika ng mga ito ay napaka-simple, marahil syntactically lang ang pagpapatupad nito. Gusto mong guys na gumawa tiyakin na iyong naiintindihan. Cool. OK, kaya kung paano kami ay magiging pagpasok nodes, kanan, sa isang listahan dahil tandaan ano ang mga ano ang mga benepisyo ng pagkakaroon ng isang listahan ng mga link na laban isang array sa mga tuntunin ng imbakan? Madla: Ito ay dynamic, kaya mas madaling to-- ANDI PENG: Eksakto, kaya dynamic, na ay nangangahulugan na maaari itong palawakin at pag-urong depende sa mga pangangailangan ng gumagamit. At ito, sa puntong ito, hindi namin kailangan mag-aksaya ng mga hindi kailangan na memory dahil ako kung hindi ko alam kung gaano karaming mga halaga ko gusto sa store, ito ay hindi magkaroon ng kahulugan para sa akin upang lumikha ng isang array dahil kung gusto kong mag-imbak 10 halaga at gumawa ako ng isang array ng 1000, na ang isang pulutong ng mga nasayang na memorya, na inilaan. Iyon ang dahilan kung bakit gusto naming gamitin ang isang naka-link list para ma-dynamically baguhin o pag-urong ng aming laki. At kaya na gumagawa ng insertion ng kaunti pang kumplikado. Dahil hindi namin sapalarang maaaring ma-access na mga elemento ang paraan na gusto naming ng isang array. Kung gusto kong ipasok ang isang elemento sa ikapitong index, Ko lamang maaari itong ipasok sa ikapitong index. Sa isang naka-link na listahan, ito ay hindi lubos na magtrabaho bilang madali, at kaya kung gusto naming ipasok ang isa dito sa naka-link na listahan, biswal, ito ay tunay madali upang makita. Gusto lang namin na ipasok ito doon, karapatan sa simula ng listahan, karapatan pagkatapos ulo. Ngunit ang paraan na kung saan mayroon kaming upang muling italaga ang mga payo ay isang bit convoluted o, lohikal, ito ang akma, ngunit Gusto mong tiyakin na mayroon ka nito ganap down dahil ang huling bagay na gusto mo ay upang muling italaga ang isang pointer sa paraan na ginagawa namin dito. Kung ikaw dereference ang pointer mula sa ulo sa 1, at pagkatapos ang lahat ng isang biglaang ang natitirang bahagi ng iyong listahan ng mga link ay nawala dahil hindi mo pa talaga lumikha ng isang pansamantalang kahit ano. Iyan ay itinuturo sa 2. Kung muling italaga mo ang pointer, at pagkatapos ay ang natitirang bahagi ng iyong listahan ay ganap na nawala. Kaya nais mong maging tunay, tunay maingat dito sa unang magtalaga ng pointer mula sa anumang ikaw nais na ipasok sa kahit saan gusto mo, at pagkatapos ay sa iyo Maaari dereference ang natitirang bahagi ng iyong listahan. Kaya ito ay naaangkop para sa kahit saan sinusubukan mong ipasok sa. Kung nais mong ipasok sa ulo, kung gusto mong sagutin dito, kung gusto mong ipasok sa Sa katapusan, na rin, ang katapusan ko hulaan gagawin mo lang walang pointer, ngunit ikaw nais na tiyakin na hindi mo mawala ang natitirang bahagi ng iyong listahan. Gusto mong palaging upang tiyakin ang iyong bagong node ay tumuturo patungo sa kahit anong ka nais na ipasok sa, at pagkatapos ay maaari mong idagdag ang pagdudugtong pa. Ang bawat malinaw? Ito ay magiging ang isa sa mga tunay na mga isyu. Isa sa mga pinaka pangunahing isyu ikaw ay pagpunta sa may sa iyong pset ay na kayo ay pagpunta sa subukan upang lumikha ng isang listahan ng mga link at insert bagay ngunit pagkatapos ay mawawala lamang ang natitirang bahagi ng iyong listahan ng naka-link. At ikaw ay pagpunta sa maging tulad ng, ako ay hindi alam kung bakit ito ang nangyayari? At ito ay isang sakit upang pumunta sa pamamagitan ng at hanapin ang lahat ng iyong mga payo. At ginagarantiya ko sa iyo na ito sa pset, pagsulat at pagguhit ng mga nodes out ay tunay, tunay na kapaki-pakinabang. Kaya maaari mong ganap na subaybayan ng kung saan ang lahat ng iyong mga payo ay, ano ang pagpunta mali, na kung saan ang lahat ng iyong mga nodes ay, kung ano ang kailangan mong gawin upang ma-access o ipasok o tanggalin o anuman sa mga ito. Ang bawat mabuting may na? Cool. Kaya kung nais namin na tingnan ang code? Oh, hindi ko alam kung kami maaaring makita the-- OK, kaya sa tuktok ng lahat ng ito ay isang function pinangalanan insert kung saan nais namin upang ipasok int n sa mga naka-link na listahan. Kami ay pagpunta sa paglalakad sa pamamagitan ng mga ito. Ito ay isang pulutong ng mga code, ang isang pulutong ng mga bagong syntax. Babalik kami OK. Kaya up sa tuktok, sa tuwing nais namin na lumikha ng anumang bagay kung ano ang kailangan namin upang gawin, lalo na kung ikaw gusto hindi ito na naka-imbak sa stack ngunit sa magbunton? Pumunta kami sa isang malloc, di ba? Kaya kami ay pagpunta upang lumikha ng isang pointer. Node, pointer, bagong equals malloc ang laki ng isang node dahil gusto naming na node na nilikha. Gusto naming ang dami ng memory na ang isang node ay tumatagal ng hanggang na inilaan para sa paglikha ng mga bagong node. At pagkatapos kami ay pagpunta upang suriin upang makita kung ang bagong equals katumbas null. Tandaan kung ano ang sinabi namin? Anuman ang malloc, kung ano ang dapat mo rin itong gawin? Dapat mong palaging suriin upang makita kung o hindi na null. Halimbawa, kung ang iyong mga operating sistema ay ganap na puno na, kung ikaw ay walang higit pang memory sa lahat at mong subukan na malloc, ito ay bumalik null para sa iyo. At kaya kung sinubukan mong gamitin ito kapag ito ay tumuturo sa null, Hindi ka pagpunta sa ma upang ma-access ang impormasyon na iyon. At kaya dahil dito, gusto naming gawing Siguraduhin na kapag ikaw ay mallocing, lagi ka check upang makita kung na memory na ibinigay sa iyo ay null. At kung ito ay hindi, pagkatapos ay maaari naming ilipat sa sa mga natitirang bahagi ng aming code. Kaya kami ay pagpunta sa magpasimula ng bagong node. Kami ay pagpunta sa gawin ang mga bagong n ay katumbas ng n. At pagkatapos kami ay pagpunta sa gawin itakda ang bagong mga pointer sa bagong sa null dahil sa ngayon ay hindi kami gusto anumang bagay para sa mga ito upang tumuro sa. Wala kaming ideya kung saan ito ay pagpunta sa ilagay mo, at pagkatapos ay kung nais nating ipasok ito sa ulo, pagkatapos ay maaari naming muling italaga ang pointer sa ulo. Lahat ng tao sundin ba ang logic ng kung saan na ang nangyayari? Lahat ng aming ginagawa ay ang paglikha ng isang bagong node, ang pagtatakda ng pointer na null, at pagkatapos reassigning ito sa ulo kung tayo alam gusto naming ipasok ito sa ulo. At pagkatapos ay ang ulo ay pagpunta sa point patungo na ang mga bagong node. Ang bawat ok na? Kaya ito ay isang proseso na may dalawang hakbang. Mayroon kayong na unang magtalaga kahit anong lumilikha ka. Itakda na pointer sa isangguni, at pagkatapos ay sa iyo Maaari uri ng dereference ang unang pointer at ituro ito patungo sa bagong node. Hangga't gusto mong ipasok ito, na logic ay pagpunta sa hold totoo. Ito ay uri ng tulad ng pagtatalaga pansamantalang variable. Tandaan, nakuha mo na tiyakin na ikaw ay huwag mawala sa pagsubaybay ng kung ikaw ay pagpapalit. Gusto mong tiyakin na ikaw ay may isang pansamantalang variable na uri ng mapigil subaybayan kung saan bagay na ay naka-imbak sa gayon ay ikaw huwag mawalan ng anumang mga halaga sa kurso ng mga tulad ng panggugulo sa paligid sa mga ito. OK, kaya ang code ay magiging dito. Ikaw guys kumuha ng isang pagtingin pagkatapos ng seksyon. Ito ay magiging doon. Kaya ako hulaan kung paano gumagana ang ito ay naiiba na kung gusto naming upang ipasok sa gitna o sa dulo? Kahit sino ay may isang ideya ng kung ano ang mga pseudocode bilang ang lohikal na reference na kami ay kumuha ng kung gusto naming ipasok ito sa gitna? Kaya kung gusto naming upang ipasok ito sa head, ang lahat ng aming gagawin ay lumikha ng isang bagong node. Itinakda namin ang pointer ng na bagong node sa ano man ang ulo, at pagkatapos ay itakda natin ang ulo sa bagong node, di ba? Kung gusto naming upang ipasok ito sa gitna ng listahan, kung ano ang kailangan nating gawin? Madla: Ito ay pa rin maging isang katulad na proseso ng mga tulad ng pagtatalaga ng pointer at pagkatapos ay nagtatalaga na pointer, ngunit kami ay may sa mahanap doon. ANDI PENG: Eksakto, kaya eksakto ang parehong proseso maliban sa iyo kung hanapin kung saan ang eksaktong ikaw gusto na ang mga bagong pointer upang pumunta sa, kaya kung gusto kong ipasok sa sa gitna ng naka-link list-- OK, sabihin natin na ang aming listahan na naka-link. Kung nais namin na ipasok ito dito mismo, kami ay pagpunta upang lumikha ng isang bagong node. Kami ay pagpunta sa malloc. Kami ay pagpunta upang lumikha ng isang bagong node. Kami ay pagpunta sa italaga ang pointer ng node dito. Ngunit ang problema na naiiba mula sa kung saan ang ulo ay ay na namin alam ang eksaktong kung saan ang ulo ay. Ito ay karapatan sa unang, tama? Ngunit dito namin nakuha upang subaybayan ng kung saan kami ay pagpasok ito sa. Kung kami ay pagpasok ng aming node dito, mayroon ka namin tiyakin na ang mga isang nakaraang sa node ay ang isa na reassigns ang pointer. Kaya pagkatapos ninyong mag-uri ng subaybayan ng dalawang bagay. Kapag patuloy mong subaybayan ng kung saan ito node ay kasalukuyang pagpasok sa. Mayroon ka ding upang subaybayan kung saan ang nakaraang node na ikaw ay naghahanap sa ay naroon din. Ang bawat mabuting may na? SIGE. Paano ang tungkol sa pagpasok sa dulo? Kung Nais kong idagdag ito here-- kung nais ko upang magdagdag ng bagong node sa dulo ng isang listahan, paano ko maaaring pumunta tungkol sa paggawa na? Madla: Kaya sa kasalukuyan, ang mga matulis huling isa upang null. ANDI PENG: Oo. Eksakto, kaya ang isang ito kasalukuyan ay itinuturo na malaman, at upang hulaan ko, sa ganitong kahulugan, ito ay madali upang magdagdag ng hanggang sa dulo ng isang listahan. Ang kailangan mong gawin ay itakda ito katumbas ng null at pagkatapos ay biglang lumakas. Right doon, napakadaling. Very simple. Na halos kapareho sa ulo, ngunit lohikal iyo nais na tiyakin na ang mga hakbang magdadala sa iyo patungo sa paggawa sa alinman sa mga ito, ikaw ay sumusunod sa kahabaan. Ito ay napakadaling, sa gitna ng iyong code, mahuli up sa, oh, Mayroon akong kaya maraming mga payo. Hindi ko alam kung saan anumang bagay ay tumuturo sa. Hindi ko kahit na malaman kung aling mga node on ako. Ano ang nangyayari? Mamahinga, tahimik na, huminga nang malalim. Gumuhit ang iyong listahan ng naka-link. Kung sinasabi mo, alam ko na kung saan ang eksaktong Kailangan ko bang ipasok ito sa at alam ko nang eksakto kung paano muling italaga ang aking mga payo, magkano, mas madali na larawan out-- much, lubhang mas madaling hindi mawala sa bugs ng iyong code. Ang bawat ok na? SIGE. Kaya ako hulaan ang isang konsepto na kami ay hindi talagang usapan tungkol sa bago ngayon, at ako hulaan ikaw ay malamang na hindi makaharap marami yet-- ito ay uri ng isang advanced concept-- ay na namin talagang magkaroon ng isang data istraktura na tinatawag na isang doble-link na listahan. Kaya bilang maaari mong makita ang isang lalaki, lahat ng aming ginagawa ay ang paglikha isang aktwal na halaga, ng dagdag na pointer sa bawat isa sa aming mga nodes na din ang mga puntos sa nakaraang node. Kaya hindi lamang ang mayroon namin ang aming mga nodes point sa susunod na isa. Sila din point sa isang nakaraan. Pupunta ako upang huwag pansinin ito ng dalawang ngayon. Kaya nga ikaw ay may isang kadena na maaaring ilipat sa parehong paraan, at pagkatapos ay ito ay isang bit mas madali lohikal na sundin kasama. Tulad dito, sa halip ng pagpapanatili ng track ng, oh, ako kung alam na ito node ay ang isa na kailangan kong muling italaga, Maaari ba akong pumunta lang dito at lamang pull sa nakaraang. Pagkatapos ako kung saan iyon ay, at pagkatapos ay sa iyo Hindi mo na kailangang tawirin ang kabuuan ng mga naka-link na listahan. Ito ay isang bit mas madali. Ngunit dahil dito, mayroon kang doble ang dami ng mga payo, na double ang halaga ng memorya. Ito ay isang pulutong ng mga payo upang subaybayan. Ito ay isang bit mas kumplikado, ngunit ito ay ng kaunti pang user friendly depende sa kung ano ang sinusubukan mong makamit. Kaya ito uri ng data istraktura ganap na umiiral, at ang istraktura para sa ay tunay, tunay simple maliban sa lahat nagkakaroon ka ay, sa halip ng isang pointer lang sa susunod, ikaw din ay mayroong isang pointer sa nakaraang. Iyan na ang lahat ng mga pagkakaiba ay. Ang bawat mabuting may na? Cool. Lahat ng karapatan, kaya ngayon ako na talagang gastusin marahil tulad ng 15 hanggang 20 minuto o ang bulk mga natitirang bahagi ng oras sa seksyon pakikipag-usap tungkol hash talahanayan. Ilan sa inyo guys nabasa pset5 spec? Lahat ng mga karapatan, mabuti. Iyan ay mas mataas kaysa sa 50% ng normal. Ito ay OK. Kaya bilang ka guys ay makita, ikaw ay hamon sa pset5 ay upang ipatupad ang isang diksiyunaryo kung saan nag-load ng higit sa 140,000 mga salita na bigyan ka namin at pagtiyak ng pagbaybay ito laban sa lahat ng mga teksto. Bibigyan ka namin ng random mga piraso ng panitikan. Bibigyan ka namin ng Odyssey Ang. Bibigyan ka namin ng The Iliad. Bibigyan ka namin ng Austin Powers. At ang iyong mga hamon ay i-spell check bawat solong salita sa lahat ng mga diksyunaryo mahalagang sa aming spell checker. At kaya mayroong ilang mga bahagi ng paglikha ng mga ito pset, unang gusto mong maging able sa tunay na-load lahat ng mga salita sa iyong diksyonaryo, at pagkatapos ay sa iyo nais na ma- spell-check ang lahat ng mga ito. At kaya dahil dito, ikaw ay pagpunta sa nangangailangan isang istraktura ng data na maaaring gawin ito mabilis at mahusay at pabago-bago. Kaya ipagpalagay ko ang pinakamadaling paraan upang gawin ito, ikaw ay malamang na lumikha ng isang array, di ba? Ang pinakamadaling paraan ng imbakan ay sa iyo ay maaaring lumikha ng isang hanay ng mga 140,000 mga salita at ilagay lamang ang mga ito ang lahat doon at pagkatapos bagtasin ang mga ito sa pamamagitan ng paghahanap ng binary o sa pamamagitan ng pagpili, o not-- Paumanhin na pag-uuri. Maaari mong ayusin ang mga ito at pagkatapos bagtasin ang mga ito sa pamamagitan ng binary paghahanap o lamang linear paghahanap at lamang huling mga salita, ngunit na tumatagal ng isang malaking halaga ng memorya, at ito ay hindi masyadong mahusay. At kaya kami ay pagpunta sa simulan pakikipag-usap tungkol sa mga paraan ng paggawa ng mas mahusay ang aming mga oras na tumatakbo. At ang aming layunin ay upang makakuha ng pare-pareho ang mga oras kung saan ito ay halos tulad array, kung saan mayroon kang madalian access. Kung gusto ko upang maghanap para sa anumang bagay, Gusto ko na ma-lamang, boom, hanapin ito eksakto, at bunutin ito. At kaya isang kaayusan kung saan makikita ay nagiging kami masyadong malapit upang ma-access ang constant panahon, ang banal na Kopita sa programming ng pare-pareho oras ay tinatawag na isang hash table. At kaya David naunang nabanggit ang [Hindi marinig] nang kaunti sa panayam, ngunit kami ay pagpunta sa tunay dive sa malalim na ngayong linggo sa isang piraso na patungkol kung paano ang isang hash table. Kaya ang paraan na ang isang hash gawa table, halimbawa, kung nais ko upang mag-imbak ng grupo ng mga salita, ang isang grupo ng mga salita sa wikang Ingles, Kaya kong theoretically ilagay banana, apple, kiwi, mangga, pair, at milong bilog lahat sa isang array. Maaari nilang lahat magkasya sa at maaaring mahanap. Gusto Ito ay uri ng isang sakit na paghahanap sa pamamagitan ng at pag-access, ngunit ang mga mas madaling paraan ng paggawa nito ay na maaari naming lumikha talagang isang istraktura tinatawag na isang hash table kung saan namin hash. Nagpapatakbo kami ng lahat ng aming mga key sa pamamagitan sumira ng isang function, isang equation, na lumiliko silang lahat sa ilang uri ng mga halaga ng isang na pagkatapos ay maaari naming mag-imbak papunta mahalagang isang hanay ng mga naka-link na listahan. At kaya dito, kung gusto naming sa tindahan ng mga salitang Ingles, maaari namin potensyal na lang, hindi ako alam, i-lahat ang mga unang titik sa ilang mga uri ng isang numero. At kaya, halimbawa, kung nais ko A na magkasingkahulugan sa apple-- o sa index ng 0, at B na magkasingkahulugan sa 1, maaari kaming magkaroon ng 26 mga entry na maaari lamang mag-imbak lahat ng mga titik ng alpabeto na kami ay magsimula sa. At pagkatapos ay maaari kaming magkaroon ng apple sa index ng 0. Maaari naming magkaroon ng banana sa index ng 1, milong bilog sa index ng 2, at iba pa. At kaya kung gusto ko upang maghanap aking hash table at pag-access ng mansanas, Alam ko nagsisimula mansanas na may isang A, at alam ko nang eksakto na ito ay dapat at ang hash talahanayan sa index 0 dahil ng pag-andar na dating nakatalaga. Kaya hindi ko alam, tayo isang programa kung saan ang user sisingilin ka na may arbitrarily-- hindi nagkataon, sa sinusubukan na thoughtfully mag-isip ng mabuti equation para ma-kumalat ang lahat ng iyong mga halaga sa isang paraan na maaari nilang madaling ma-access ito sa susunod na may tulad ng isang equation na ikaw, ang iyong sarili, malaman. Kaya sa kamalayan kung Nais kong pumunta sa mangga, alam ko, oh, ito ay nagsisimula sa m. Ito ay dapat na sa index ng 12. Hindi ko na kailangang maghanap sa pamamagitan ng kahit ano. Alam ko exactly-- maaari kong pumunta lamang sa ang index ng 12 at hilahin na out. Ang bawat malinaw sa kung paano ang isang gumagana hash talahanayan? Ito ay uri ng lamang ng isang mas kumplikadong array. Iyan na ang lahat ng ito ay. SIGE. Kaya ako hulaan namin tumakbo sa ang isyu na ito ng kung ano ang ang mangyayari kung mayroon kang maramihang mga bagay-bagay na magbibigay sa iyo ng parehong index? Kaya sinasabi ng aming mga function, ang lahat ng ito ginawa ay gawin na ang unang titik at turn na sa isang kani 0 hanggang 25 index. Iyan ay lubos na multa kung magkaroon ng isa sa bawat ka lamang. Ngunit ang pangalawang simulan mo pagkakaroon ng mas maraming, ikaw ay pagpunta sa may kung ano ang tinatawag na isang banggaan. Kaya kung sinusubukan kong ipasok ibaon sa isang hash mesa na mayroon ng banana sa mga ito, kung ano ang nangyayari sa mangyayari kapag subukan mong ipasok na? Bad bagay dahil saging Umiiral na sa loob ng index na nais mong i-imbak ang mga ito sa. Berry uri ng ay tulad ng, ah, kung ano ang gagawin ko? Hindi ko alam kung saan pupunta. Paano ko malutas ito? At kaya ka guys ay uri ng makita ang ginagawa namin ito mapaglalang bagay kung saan maaari naming uri ng aktwal na lumikha ng listahan ng mga link sa aming mga array. At kaya ang pinakamadaling paraan mag-isip tungkol sa mga ito, lahat ng hash table ay isang ang dami ng mga naka-link na mga listahan. At ito, sa kamalayan na, mayroon kang ito maganda ang dami ng mga payo, at pagkatapos ay sa bawat pointer sa halaga na, sa index na, maaaring aktwal na tumuturo sa ibang mga bagay. At kaya mayroon ka ng lahat ng mga hiwalay na chains darating off ng isang malaking array. At kaya dito, kung ako Nais upang ipasok itlog ng isda, Alam ko, OK, ako pagpunta sa input ito sa pamamagitan ng aking hash. Pupunta ako sa dulo hanggang sa index ng 1, at pagkatapos ay ako pagpunta upang ma-magkaroon ng lamang ng isang mas maliit na subset ng mga ito 140,000-salita sa diksyunaryo giant. At pagkatapos ay ako ay maaari lamang tumingin sa pamamagitan ng 1/26 na iyon. At kaya pagkatapos ko ma lang ipasok isang itlog ng isda alinman sa bago o pagkatapos ng banana sa kasong ito? Pagkatapos, i-right? At kaya ikaw ay pagpunta sa nais na ipasok ito node matapos saging, at upang ikaw ay pagpunta upang magsingit sa likod o hulihan ng na naka-link na listahan. Pupunta ako sa bumalik sa nakaraang slide, kaya ka guys ay maaaring makita kung paano gumagana hash. Kaya hash ay equation na ito na ikaw ay nagpapatakbo ng mga uri ng iyong input sa pamamagitan ng upang makakuha ng anumang index na nais mong italaga ito patungo. At ito, sa halimbawang ito, gusto namin ang lahat ng na gawin ay gawin ang unang titik, turn na sa isang index, at pagkatapos namin Maaaring mag-imbak na sa aming hash. Lahat ng ginagawa namin dito ay hindi namin nagko-convert ang mga unang titik. Kaya Keykey [0] ay lamang ang mga unang titik ng anumang string namin sa pag, kami ay pagpasa sa. Kami ay nagko-convert na sa itaas, at ng kami ay pagbabawas ng uppercase A, kaya ang lahat na ang ginagawa ay nagbibigay sa amin ng isang bilang sa kung saan namin hash aming mga halaga papunta. At pagkatapos kami ay pagpunta sa bumalik hash modulus SIZE. Maging tunay, tunay maingat dahil, theoretically, dito ang iyong halaga ng hash ay maaaring maging walang hanggan. Ito ay maaaring pumunta lamang sa at sa at sa. Ito ay maaaring maging ng ilang mga talagang, talagang malaking halaga, ngunit dahil ang iyong mga talahanayan ng hash na nalikha mo na lamang ay may 26 na index, nais mong tiyakin na ang iyong modulusing upang ikaw huwag run-- ito ay ang parehong bagay bilang iyong queue-- sa gayon ay hindi mo na tumakbo off ang ibaba ng iyong hash. Gusto mong ibalot ito pabalik sa paligid sa parehong paraan sa [hindi marinig] kapag nagkaroon ka ng tulad ng isang tunay, napakalaking sulat, ikaw ay Ayaw na sa patakbuhin lamang off sa dulo. Parehong bagay dito, gusto mong tiyakin hindi ito tatakbo off ang katapusan sa pamamagitan ng pambalot sa paligid sa tuktok ng talahanayan. Kaya ito ay lamang ng isang napaka simple hash. Lahat na ginawa ay gawin ang unang sulat ng ano man ang aming input ay at turn na sa isang index na maaari naming ilagay sa aming hash table. Oo, at sa gayon tulad ng sinabi ko bago, ang paraan na malutas namin ang banggaan sa aming hash talahanayan ay nakakaranas ng, kung ano ang aming tawagan, pagdudugtong. Kaya kung subukan mong ipasok ang maramihang salita na nagsisimula sa mga parehong bagay, ikaw ay pagpunta sa magkaroon ng isa hash value. Avocados at mansanas, kung na sa iyo patakbuhin ito sa pamamagitan ng aming hash function, ay pagpunta sa magbibigay sa iyo ng parehong numero, ang bilang ng mga 0. At upang ang mga paraan namin malutas na na namin ang tunay na uri ng link ang mga ito sama sa pamamagitan ng mga listahan ng link. At kaya sa ganitong kahulugan, ka guys ay maaaring makita ang mga uri ng kung paano mga istraktura ng data na namin nai-set dati tulad ng isang raisin linked uri list ng maaaring dumating nang magkasama sa isa. At pagkatapos ay maaari kang lumikha ng malayo mas mahusay na istruktura ng data na maaaring hawakan ng mas malaking halaga ng data, na dynamic na baguhin ang laki depende sa iyong mga pangangailangan. Ang bawat malinaw? Ang bawat uri ng malinaw na sa kung ano ang mangyayari dito? Kung Nais kong insert-- kung ano ang isang prutas na nagsisimula sa, hindi ko alam, B, na iba sa isang itlog ng isda, saging. Madla: Blackberry. ANDI PENG: Blackberry, blackberry. Saan ang blackberry pumunta dito? Well, talagang hindi pa namin inayos ito pa, ngunit theoretically kung gusto naming magkaroon ng ganitong sa alpabetong pagkakasunud-sunod, kung saan dapat BlackBerry pumunta? Madla: [hindi marinig] ANDI PENG: Eksakto, pagkatapos dito, tama? Pero dahil ito ay masyadong mahirap na reorder-- Hulaan ko ito ay nasa sa iyo guys. Ikaw guys Maaari ganap ipatupad ang anumang gusto mo. Ang mas mahusay na paraan ng paggawa nito marahil ay magiging upang ayusin ang iyong mga naka-link ilista sa alpabetong pagkakasunud-sunod, at iba kapag ikaw ay pagpasok ng mga bagay, na nais mong upang siguraduhin na ipasok ang mga ito sa alpabetong pagkakasunud-sunod kaya na pagkatapos ay kapag ikaw ay sinusubukan mong hanapin ang mga ito, hindi mo na kailangang tawirin ang lahat. Alam mo nang eksakto kung saan ito ay, at ito ay mas madali. Ngunit kung ikaw uri ng may bagay kahalong random, pupuntahan mo pa rin na magkaroon ng sa pagtawid ito anyways. At kaya kung Nais kong lamang ipasok blackberry dito at nais ko upang maghanap para sa ito, alam ko, oh, blackberry dapat magsimula sa mga index ng 1, kaya ko Alam agad lamang ng paghahanap sa 1. At pagkatapos ay maaari ako uri ng tawirin ang listahan ng mga link hanggang sa makakuha ako sa BlackBerry, at then-- oo? Madla: Kung sinusubukan mong create-- Hulaan ko ito ay isang napaka-simpleng hash function. At kung gusto naming gawin maramihang mga layer ng ganyan, OK, gusto naming hiwalay sa tulad ng lahat ng alpabetikong titik at pagkatapos ay muli upang gustuhin ng isa pang hanay ng alpabetikong titik sa loob nito, ay namin ang paglalagay ko ng hash mesa sa loob ng isang hash table, o tulad ng isang function sa loob ng isang function? O kaya ay na- ANDI PENG: So iyong hash function-- iyong hash talahanayan maaaring bilang malaking bilang na gusto mo ito sa. Kaya sa puntong ito, naisip ko ito ay tunay madali, napaka simple para sa akin na uri lamang batay sa mga titik ng unang salita. At kaya may mga opsyon 26 lamang. Maaari lamang ba akong makakuha ng 26 mga pagpipilian mula sa 0 hanggang 25 dahil sila lamang simulan mula A hanggang Z. Subalit kung nais mong upang idagdag, marahil, mas kumplikado o magpatakbo ng mas mabilis na oras sa iyong hash table, kung talagang maaaring gawin ang lahat ng uri ng bagay. Maaari kang gumawa ng iyong sariling equation na nagbibigay sa iyo higit pang pamamahagi sa iyong mga salita, at pagkatapos ay kapag naghanap ka, ito ay magiging mas mabilis. Ito ay lubos na nakasalalay sa iyo guys paano mo nais na ipatupad na. Isipin ito bilang lamang ng mga bucket. Kung Nais kong magkaroon ng 26 mga bucket, pupuntahan ko upang ayusin ang mga bagay sa mga bucket. Ngunit ako pagpunta sa magkaroon ng isang grupo ng mga bagay-bagay sa bawat bucket, kaya kung nais mong gumawa ng ito mas mabilis at mas mahusay, hayaan mo akong magkaroon ng isang daang mga bucket. Ngunit pagkatapos ay mayroon kang upang malaman kung ang isang paraan upang ayusin ang mga bagay upang ang mga ito sa wastong bucket dapat sila ay sa. Ngunit pagkatapos ay kapag ikaw talaga nais na tingnan ang mga na bucket, ito ay isang pulutong ng mas mabilis dahil mayroong mas bagay-bagay sa bawat bucket. At kaya, oo, na talagang ang bilis ng kamay para sa iyo guys sa pset5 ay na kayo ay hinamon upang lumikha lamang kahit na ano ay ang pinaka mahusay na function na maaari mong isipin na maging makakapag-imbak at i-check ang mga halagang ito. Lubos na nakasalalay sa iyo guys subalit nais mong gawin ito, ngunit iyan ay isang tunay na magandang point. Iyon ang mga uri ng logic mo gusto mong simulan ang pag-iisip tungkol ay, well, bakit hindi ako gumawa ng mas maraming mga bucket. At pagkatapos ko bang hanapin mas bagay, at pagkatapos ay marahil ko magkaroon ng isang iba't ibang mga pag-andar hash. Oo, mayroong isang pulutong ng mga paraan upang gawin ito pset, ang ilan ay mas mabilis kaysa sa iba. Ganap na ako pagpunta upang makita kung paano mabilis ay ang pinakamabilis na ka guys ay ay maaaring makakuha ng iyong mga function sa trabaho. OK, lahat ng mabuti sa chaining at hash talahanayan? Ito ay tulad ng isang napaka-simple talaga konsepto kung sa tingin mo ang tungkol dito. Lahat ng ito ay ay naghihiwalay sa kahit anong iyong input ay sa mga bucket, paghihiwalay sa kanila, at pagkatapos ay sa paghahanap sa naglilista na nauugnay sa. Cool. Lahat ng karapatan, ngayon kami ay may isang iba't ibang mga uri ng istraktura ng data na tinatawag na isang puno. Sabihin pumunta sa at makipag-usap tungkol pagsusubok na kung saan ay malinaw na iba't ibang, ngunit sa parehong kategorya. Mahalaga, ang lahat ng punong kahoy ay sa halip ng pag-aayos ng data sa mga guhit na paraan na ang isang hash table does-- mo malaman, ito ay nakuha ng isang tuktok at ibaba at pagkatapos mong uri ng link off ng it-- isang puno ay may isang tuktok na kayong tumawag sa root, at pagkatapos ito ay may mga dahon sa palibot. At kaya lahat ng kailangan mo dito ay lamang tuktok node na ang mga puntos sa iba pang mga nodes, na puntos sa mas maraming mga nodes, at iba pa at iba pa. At kaya mo na lang paghahati sanga. Ito lamang ay isang iba't ibang mga paraan ng pag-aayos data, at dahil tinatawag namin itong isang puno, ka guys just-- ito lamang imo-modelo out sa hitsura ng isang puno. Iyon ay kung bakit ang tawag namin ito puno. Mukhang hash talahanayan tulad ng isang table. Ang isang puno lang ang hitsura ng isang puno. Lahat ng ito ay isang hiwalay na paraan ng pag-aayos ng mga node depende sa kung ano ang inyong mga pangangailangan. Kaya ikaw ay may isang ugat at pagkatapos ay mayroon kang mga dahon. Ang paraan na aming makakaya lalo isipin ang tungkol sa ito ay isang binary tree, isang binary puno ay lamang ng isang partikular na uri ng isang puno kung saan ang tanging mga puntos bawat node upang, sa max, dalawang iba pang mga nodes. At kaya dito mayroon kang natatanging mahusay na proporsyon sa iyong mga puno na ginagawang mas madali ang uri ng hitsura sa kung ano ang halaga na ikaw ay dahil pagkatapos mo Mayroon palaging isang kaliwa o kanan. Mayroong hindi kailanman tulad ng isang kaliwang ikatlong mula sa kaliwa o isang ika-apat mula sa kaliwa. Ito lang ang mayroon ka ng isang kaliwa at isang kanan at maaari mong hanapin ang alinman sa mga dalawang. At kaya kung bakit kapaki-pakinabang na ito ay? Ang paraan na ito ay kapaki-pakinabang ay kung ikaw ay naghahanap sa paghahanap sa pamamagitan values, di ba? Sa halip na ang pagpapatupad ng binary maghanap sa isang error array, kung iyong nais na ma-ipasok nodes at mag-alis ng nodes sa kalooban at din mapanatili ang search kakayahan ng binary paghahanap. Kaya sa ganitong paraan, hindi namin uri ng tricking-- tandaan kapag kami ay Sinabi listahan ng link ay maaaring hindi binary paghahanap? Kami ay uri ng paglikha ng isang istraktura ng data na trick na sa pagtatrabaho. At kaya dahil naka-link na listahan ay linear, sila lamang ang link ng isa pagkatapos ng isa. Maaari uri ng kaming may iba't ibang uri ng mga payo sa puntong iyon sa iba't ibang mga node na maaaring makatulong sa amin sa paghahanap. At kaya dito, kung nais kong magkaroon ng isang binary puno ng paghahanap, Alam ko na ang aking gitna kung 55. Ako lamang ang pagpunta upang lumikha ng na bilang aking middle, tulad ng aking mga ugat, at pagkatapos ay ako pagpunta sa may mga halaga iikot off ng mga ito. Kaya dito, kung ako pagpunta upang maghanap para sa ang halaga ng 66, maaari ba akong magsimula sa 55. Ito ay 66 mas malaki kaysa sa 55? Oo ito ay, upang malaman ko mus ko sa paghahanap i n kanan pointer ng punong ito. Pumunta ako sa 77. OK, ay 66 mas mababa sa o mas malaki kaysa sa 77? Ito ay mas mababa kaysa sa, upang malaman mo, oh, na may upang maging kaliwa node. At kaya dito namin uri ng na pinapanatili lahat ng mahusay na mga bagay-bagay tungkol sa array, kaya tulad ng mga dynamic na pagbabago ng laki ng mga bagay, pagiging maaaring ipasok at tanggalin sa kalooban, nang hindi na kinakailangang mag-alala tungkol sa mga fixed halaga ng puwang. Mapanatili pa rin namin ang lahat ng mga magagandang bagay habang nagagawa ring upang mapanatili ang mag-log at oras ng binary paghahanap sa paghahanap na lamang namin dati maaaring makakuha ng isang phrase. Cool istraktura ng data, uri ng kumplikadong upang ipatupad, ang node. Tulad ng iyong nakikita, ang lahat ng ito ay ang struct ng buko ay na mayroon ka ng isang kaliwa at isang karapatan pointer. Iyan na ang lahat ng ito ay. Kaya sa halip na lamang pagkakaroon ng isang x o isang nakaraang. Mayroon kang isang kaliwa o kanan, at pagkatapos ay maaari mong uri ng link ang mga ito nang sama-sama gayunpaman pinili mo ito. OK, aktwal na kami ay pagpunta tumagal lamang ng ilang minuto. Kaya kami ay pagpunta upang bumalik dito. Tulad ng dati sabi ko, Ako uri ng ipinaliwanag ang logic sa likod kung paano namin Gusto paghahanap sa pamamagitan ng mga ito. Kami ay pagpunta sa subukan pseudocoding this out upang makita ang kung maaari naming uri ng mag-apply ang parehong lohika ng binary paghahanap sa iba't ibang uri ng istraktura ng data. Kung ikaw guys na nais na kumuha ng tulad ng isang pares minuto upang lamang isipin ang tungkol ito. SIGE. Lahat ng karapatan, ako pagpunta sa talagang lamang magbigay the-- mo ang hindi, Kukunin namin ang unang makipag-usap tungkol sa mga pseudocode. Kaya kahit sino ay gusto na magbigay ng isang ulos sa kung ano ang ang unang bagay na gusto mong gawin kapag kayo ay nagsisimula searching ay? Kung kami ay naghahanap para sa ang halaga ng 66, kung ano ang ang unang bagay na gusto naming gawin kung gusto naming binary paghahanap punong kahoy na ito? Madla: Gusto mong tingnan ang karapatan at tumingin sa kaliwa at makita [hindi marinig] mas malaking bilang. ANDI PENG: Oo, eksakto. Kaya ikaw ay pagpunta upang tumingin sa iyong root. Mayroong maraming mga paraan na maaari mong tawagan ito, sabihin sa iyong mga magulang na node tao. Gusto kong sabihin na ugat dahil na tulad ng mga ugat ng puno. Ikaw ay pagpunta sa tumingin sa iyong root node, at ikaw ay pagpunta upang makita ang 66 na mas malaki kaysa sa o mas mababa kaysa sa 55. At kung ito ay mas malaki kaysa sa, well, ito ay mas malaki kaysa sa, kung saan nais namin na tingnan ang? Saan ang gusto namin sa paghahanap ngayon, tama? Gusto naming hanapin ang kanang kalahati ng punong kahoy na ito. Kaya mayroon kami, Maginhawang, isang pointer na tumuturo sa kanan. At kaya pagkatapos ay maaari naming i-set ang aming bagong ugat na 77. Maaari naming pumunta lamang sa kung saan man ang pointer ay pagturo. Well, oh, dito kami ay nagsisimula sa 77, at maaari naming lamang gawin ito recursively muli at muli. Sa ganitong paraan, uri kayo ng magkaroon ng isang function. Mayroon kang isang paraan ng paghahanap na iyong Maaari lamang ulitin paulit-ulit-ulit, depende sa kung saan nais mong tingnan ang hanggang sa wakas makakuha ng halaga na kayo ay naghahanap para sa. Magkaroon ng kahulugan? Ako ay tungkol sa upang ipakita sa iyo ang aktwal code, at ito ay isang pulutong ng code. Hindi na kailangang mag pambihira out. Susubukan naming makipag-usap sa pamamagitan nito. Sa totoo lang, hindi. Iyon ay pseudocode lamang. OK, na lamang ang pseudocode, kung saan ay isang bit kumplikado, ngunit ito ay ganap na multa. Ang bawat mga sumusunod na kasama dito? Kung ang ugat ay null, return hindi totoo dahil ang ibig sabihin nito hindi mo kahit na magkaroon ng kahit ano doon. Kung ugat n ay ang halaga, kaya kung ito ang mangyayari sa maging ang isa ikaw ay naghahanap sa, pagkatapos ikaw ay pagpunta upang bumalik true dahil alam mo na iyong natagpuan ito. Ngunit kung ang mga halaga ay mas mababa sa ugat ng n, ikaw ay pagpunta sa paghahanap sa kaliwa bata o kaliwa na dahon, kahit anong gusto mo sa tawag na ito. At kung ang mga halaga ay mas malaki kaysa sa root, ikaw ay pagpunta sa paghahanap ng tamang tree, pagkatapos ay tatakbo lamang sa mga function sa pamamagitan ng search muli. At kung ugat ay null, na na nangangahulugan naabot mo na ang dulo? Ito ay nangangahulugan na wala kang mas higit pang mga dahon sa paghahanap, pagkatapos ay alam mo, oh, ako hulaan ito ay hindi in dito dahil matapos ko na tumingin sa pamamagitan ng ang buong bagay at ito ay hindi dito, ito ay maaaring hindi lamang dito. Ba na magkaroon ng kahulugan sa lahat ng tao? Kaya ito ay tulad ng paghahanap ng binary pinapanatili ang mga kakayahan ng mga listahan ng link. Cool, at sa gayon ang ikalawang uri ng istraktura ng data guys Maaari subukan ang pagpapatupad sa iyong pset, mayroon na lamang kayong pumili ng isang paraan. Ngunit marahil isang alternatibong paraan upang ang hash table ay kung ano ang tawag namin sa isang trie. Lahat ng isang trie ay ay isang partikular na uri ng puno na may halaga na pumunta sa iba pang mga halaga. Kaya sa halip ng pagkakaroon ng isang binary puno sa kamalayan na ang isa lamang sa bagay ay maaaring punto sa dalawa, maaari kang magkaroon ng isang bagay point sa maraming, maraming mga bagay. Ikaw ay may mahalagang mga array sa loob ng na-imbak mo mga payo na tumuturo sa ibang mga array. Kaya ang node ng kung paano namin nais tukuyin ang isang trie ay nais naming magkaroon ng isang Boolean, c salita, tama? Kaya ang node ay Boolean tulad ng tama o mali, una sa lahat sa ulo ng na array, salita kaya ito? Pangalawa, nais mong magkaroon ng mga payo sa ano man ang iba sa kanila ay. A bit complex, medyo abstract, ngunit Ako ay ipaliwanag kung ano na ang lahat ng paraan. Kaya dito, sa tuktok, kung ikaw ipinahayag ng isang array na, isang node kung saan ikaw ay may isang Boolean halaga na naka-imbak sa harap na nagsasabi sa iyo na ito ay isang salita? Hindi ba ito ang isang salita? At pagkatapos ay mayroon kang mga natitirang bahagi ng iyong array na tunay na mga tindahan ng lahat ng mga posibilidad ng kung ano ito ay maaaring. Kaya, halimbawa, tulad ng sa tuktok mayroon kang ang unang bagay na nagsasabing totoo o false, oo o hindi, ito ay isang salita. At pagkatapos ay mayroon kang 0 hanggang 26 ng ang mga titik na maaari mong tindahan. Kung Nais kong hanapin dito para sa bat, pumunta ako sa tuktok at ako ay tumingin para sa B. mahanap ko B sa aking array, at upang malaman ko, OK, ay B ng isang salita? B ay hindi isang salita, kaya ganito Dapat ko bang patuloy na maghanap. Pumunta ko mula sa B, at ako ay tumingin sa pointer na B puntos na patungo at nakikita ko ang ibang hanay ng mga impormasyon, ang parehong istraktura na kami dati. At here-- oh, ang susunod na sulat sa [hindi marinig] ay A. Kaya tingnan natin sa na array. Makikita natin ang ika-walong halaga, at pagkatapos, hanapin namin upang makita, oh, hey, na isang salita, ay B-A ng isang salita? Ito ay hindi isang salita. Mayroon kaming upang patuloy na naghahanap. At kaya pagkatapos namin tumingin sa kung saan ang pointer ng isang puntos, at ang mga puntos sa ibang paraan sa na kung saan kami ay may higit na halaga na naka-imbak. At sa huli, na nakukuha namin na B-A-T, na kung saan ay isang salita. At upang ang mga susunod na panahon tumingin ka, ikaw ay pagpunta na magkaroon ng na-check ng, oo, Boolean function na ito ay totoo. At kaya sa kamalayan hindi namin uri ng pagkakaroon ng isang puno na may mga array. Kaya pagkatapos ay maaari mong uri ng paghahanap down. Kaysa sa hashing isang function at pagtatalaga ng mga halaga sa pamamagitan ng listahan ng mga link, maaari mo lamang ipatupad ang isang trie na mga paghahanap downwords. Talagang, talagang kumplikado stuff. Hindi madaling mag-isip tungkol sa dahil ako tulad ng pagdura kaya maraming mga istruktura ng data out sa iyo, ngunit ang ginagawa ng lahat ng uri ng maunawaan kung paano gumagana ang logic ng mga ito? OK, cool. Kaya B-A-T, at pagkatapos ay ikaw ay pagpunta upang maghanap. Ang susunod na panahon na kayo ay pagpunta upang makita, oh, hey, ito ay totoo, kaya alam ko na ito ay dapat na isang salita. Parehong bagay para sa zoo. Kaya dito ang mga bagay sa ngayon, kung tayo Nais upang maghanap para sa mga zoo, sa ngayon, kasalukuyang zoo ay hindi isang salita sa aming diksyunaryo dahil, gaya ng maaaring makakita sa iyo guys, ang unang lugar na kami ay may isang Boolean nagbabalik ng tunay ay sa dulo ng zoom. Mayroon kaming Z-O-O-M. At kaya dito, hindi namin talagang magkaroon ang salita, zoo, sa aming diksyunaryo dahil ang check box na ito ay hindi naka-check. Kaya ang computer ay hindi malaman na ang zoo ay isang salita dahil ang paraan na kami naka-imbak ito, tanging isang zoom dito talaga ay isang Boolean halaga na na-naka-totoo. Kaya kung nais namin na ipasok ang salita, zoo, sa aming diksyonaryo, kung paano namin pumunta tungkol sa paggawa na? Ano ang kailangan namin upang gawin upang tiyakin na ang aming alam computer na Z-O-O ay isang salita at hindi ang unang salita ay Z-O-O-M? Madla: [hindi marinig] ANDI PENG: Eksakto, namin nais na tiyakin na ang dito, na Boolean halaga ay checked off na ito ay totoo. Z-O-O, pagkatapos kami ay pagpunta upang suriin na, upang malaman namin ang eksaktong, hey, zoo ay isang salita. Pupunta ako upang sabihin sa computer na ito ay isang salita sa gayon na kapag ang mga tseke computer, alam na zoo ay isang salita. Dahil tandaan ang lahat ng mga data na ito kaayusan, ito ay tunay madali para sa amin sabihin, oh, bat ang isang salita. Zoo ay isang salita. Mag-zoom ay isang salita. Ngunit kapag ikaw ay pagbuo ng mga ito, ang computer ay walang mga ideya. Kaya ikaw ay may upang sabihin ito nang eksakto sa anong punto salita kaya ito? Sa anong punto ay hindi ito isang salita? At sa anong punto ko kailangan upang maghanap ng mga bagay, at sa anong punto ang kailangan kong pumunta sa susunod? Ang bawat malinaw na iyon? Cool. At kaya pagkatapos ay dumating ang problema ng kung paano gagawin namin pumunta tungkol sa pagpasok ng isang bagay na talagang hindi doon? Kaya sabihin lang sabihin gusto naming ipasok ang salita, bakit, sa aming trie. Tulad nang nakikita mo guys tulad ng kasalukuyan lahat ng mayroon kami ngayon ay B-A-T, at ang bagong istraktura ng data doon ay isang pinta na matulis sa null dahil ipinapalagay namin na, oh, walang mga salita pagkatapos ng B-A-T, bakit kailangan namin upang panatilihin pagkakaroon ng mga bagay-bagay matapos na T. Ngunit ang problema arises kung gagawin namin sa iyo gusto mong magkaroon ng isang salita na nauuna matapos ang T. Kung ikaw ay may paliguan, ikaw ay pagpunta sa gusto ng isang H karapatan. At upang ang mga paraan namin ay pagpunta sa gawin iyon ay kami ay pagpunta upang lumikha ng isang hiwalay na node. Hindi kami mag-ukol kahit anong halaga ng memory para sa bagong array, at kami ay pagpunta sa muling italaga ang mga payo. Kami ay pagpunta sa italaga ang H, Una sa lahat, ito null, kami ay pagpunta sa mapupuksa. Kami ay pagpunta sa may ang H point pababa. Kapag nakita namin ang isang H, gusto namin ito upang pumunta sa ibang lugar. Sa dito, maaari naming pagkatapos ay i-check off yes. Kung ang hit namin ang isang H pagkatapos ng T, oh, pagkatapos ay alam namin na ito ay isang salita. Ang Boolean ay pagpunta sa bumalik totoo. Ang bawat malinaw sa kung paano na nangyari? SIGE. Kaya mahalagang, ang lahat ng mga mga istruktura ng data na kami ay wala sa paglipas ng araw na ito, hindi ko na wala na sa kanila tunay, tunay mabilis at hindi in sa marami detalye, at iyon ang OK. Sa sandaling simulan mo ang panggugulo sa mga ito, makikita mo ang pagpapanatili ng track ng kung saan lahat ng payo ay, kung ano ang nangyayari sa iyong istruktura ng data, at iba pa. Makikita nila na tunay na kapaki-pakinabang, at ito ay nakasalalay sa iyo guys sa ganap na malaman kung paano na nais mong ipatupad bagay. At kaya pset4, ng 5-- oh, na ang mali. Pset5 ay maling spelling. Tulad ng sinabi ko bago, ikaw ay pagpunta sa, isang beses muli, i-download ang source code mula sa amin. May pupuntahan ng tatlong pangunahing bagay na makikita mo ay pag-download. Makikita mong i-download diksyunaryo, kers, at teksto. Lahat ng mga bagay ay ang mga mag mga diksyunaryo ng mga salita na gusto namin sa iyo na suriin ang o test ng impormasyon na gusto namin sa iyo sa oras ng paggawa check. At upang ang mga diksyunaryo bigyan ka namin ay pagpunta upang bigyan ka ng aktwal na mga salita na gusto naming sa inyo na tindahan sa anumang paraan sa isang paraan na mas mahusay kaysa sa isang array. At pagkatapos ay ang teksto ay magiging kung ano kami na humihiling sa iyo na baybayin suriin upang tiyakin na lahat ng mga salita na may mga tunay na salita. At upang ang mga tatlong bloke ng mga programa na ibibigay namin sa iyo ay tinatawag dictionary.c, dictionary.h, at speller.c. At sa gayon ang lahat dictionary.c ay ay kung ano ang iyong hiniling na ipatupad. Naglo-load Ito salita. Ito spell tseke ang mga ito, at ito ay gumagawa sigurado na ang lahat ng bagay ay wastong inilagay. diction.h ay isang file library lamang na nagpapahayag ng lahat ng mga pag-andar. At speller.c, kami ay pagpunta sa magbibigay sa iyo. Hindi mo kailangang baguhin ang anuman sa mga ito. Lahat speller.c ay ay tumagal na, naglo-load ito, sinusuri ang bilis ng mga ito, pagsusulit ang benchmark ng tulad ng kung paano mabilis na nagawa mong gawin ang mga bagay. Ito ay isang speller. Gawin lamang na hindi gulo sa mga ito, ngunit gumawa siguraduhin na maunawaan kung ano ang ginagawa nito. Ginagamit namin ang isang function na tinatawag na getrusage na pagsusulit ang pagganap ng iyong mga oras ng paggawa checker. Lahat ng ginagawa nito ay talaga subukan ang mga oras ng lahat ng bagay sa iyong diksyunaryo, kaya tiyaking nauunawaan mo ang mga ito. Maging maingat sa hindi gulo sa mga ito o pa ang mga bagay-bagay ay hindi tatakbo nang maayos. At sa karamihan ng mga hamon na ito ay para sa mga ka guys upang talagang baguhin dictionary.c. Kami ay pagpunta sa magbibigay sa iyo ng 140,000 mga salita sa isang diksiyunaryo. Kami ay pagpunta sa magbibigay sa iyo ng isang text file na may mga salitang iyon, at nais ka naming ma-organisa mga ito sa isang hash table o isang trie dahil kapag hinihiling namin sa iyo sa oras ng paggawa check-- isipin kung ikaw ay spell suri tulad Odyssey ni Homer. Ito ay tulad nito malaking, malaking pagsubok. Isipin kung ang bawat isang word mo ay nagkaroon upang tumingin sa pamamagitan ng isang hanay ng mga 140,000 na mga halaga. Iyon ay tumagal magpakailanman para sa iyong machine na tumakbo. Iyon ang dahilan kung bakit gusto naming ayusin ang aming data sa mas mahusay na mga istraktura ng data tulad ng isang hash table o isang trie. At pagkatapos mong guys Maaari uri ng kapag naghahanap ka ng access mas madali at mas mabilis na mga bagay. At kaya maging maingat upang malutas ang mga banggaan. Ikaw ay pagpunta upang makakuha ng grupo ng mga salita ng yaong magsimula sa A. Ikaw ay pagpunta upang makakuha ng grupo ng mga salita na nagsisimula sa B. Hanggang sa iyo guys kung paano mo gusto upang malutas ito. Marahil mayroong higit pa mabisa hash na lamang ang unang titik ng isang bagay, at sa gayon ay ang bahala sa iyo guys sa uri ng gawin ang anumang gusto mo. Siguro gusto mong idagdag lahat ang mga titik na magkasama. Siguro gusto mong gusto gawin kakaiba mga bagay sa account ang bilang ng mga titik, kahit ano. Hanggang sa iyo guys kung paano mo nais na gawin. Kung nais mong gumawa ng isang hash table, kung ikaw Gusto mong subukan ang isang trie, ganap na nakasalalay sa iyo. Ko sa inyo kung maagang ng panahon na ang trie ay karaniwang isang bit mas mahirap dahil lang may isang pulutong higit pang mga payo upang subaybayan. Ngunit ganap sa inyo guys. Ito ay malayo mas mabisa sa karamihan ng pagkakataon. Gusto mong talagang magagawang upang panatilihin subaybayan ng lahat ng iyong mga payo. Tulad gawin ang parehong bagay na ako ay ginagawa dito. Kapag sinusubukan mong ipasok mga halaga sa isang hash table o tanggalin, tiyakin na ikaw ay talagang sa pagpapanatili ng track ng kung saan ang lahat ay dahil sa ito ay tunay madali para sa kung ako sinusubukan mong ipasok tulad ng mga salita, andy. Sabihin lang sabihin na ang isang tunay na salita, ang salita, andy, sa isang higanteng listahan ng A salita. Kung mangyari ko lang na muling italaga isang pointer mali, Oops, may napupunta ang kabuuan ng ang natitirang bahagi ng aking listahan ng mga link. Ngayon ang tanging salita ko magkaroon ay andy, at ngayon lahat ng iba pang mga salita sa diksiyunaryo ay nawala. At kaya gusto mong tiyakin na ikaw ay subaybayan ang lahat ng iyong mga payo o ibang tao ikaw ay pagpunta upang makakuha ng malaking problema sa iyong code. Gumuhit ng mga bagay sa labas ng mabuti sa bawat hakbang. Ito ay ginagawang mas madaling i-isip ng. At sa wakas, na nais mong ma- subukan ang iyong pagganap ng iyong mga programa sa malaking board. Kung ikaw guys kumuha ng isang tingnan CS50 sa ngayon, mayroon kaming kung ano ang tinatawag na ang malaking board. Ito ay ang score sheet sa pinakamabilis pagtiyak sa pagbaybay beses sa kabuuan ng lahat ng CS50 sa ngayon, tingin ko ang mga top tulad ng 10 beses sa tingin ko walong ng mga ito ay mga kawani. Kami ay talagang nais mong guys na matalo sa amin. Lahat tayo ay sinusubukan upang ipatupad ang pinakamabilis na code hangga't maaari. Gusto namin sa iyo guys upang subukan upang tutulan amin at magpatupad ng mas mabilis kaysa sa ating lahat maaari. At kaya ito ay talagang ang unang pagkakataon na hindi namin na humihiling sa iyo guys na gawin ang isang pset na Maaari mo ba talagang gawin sa kahit anong paraan gusto mo. Ako palaging sabihin, ito ay higit pa sa akin sa isang solusyon sa tunay na buhay, di ba? Sinasabi ko, hey, kailangan ko sa iyo na gawin ito. Bumuo ng isang programa na ito para sa akin. Gawin ito gayunpaman gusto mo. Alam ko lang na gusto kong mag-ayuno. Iyan ang iyong hamon para sa linggong ito. Ikaw guys, kami ay pagpunta upang bigyan ka ng isang gawain. Kami ay pagpunta sa magbibigay sa iyo ng isang hamon. At pagkatapos ito ay nakasalalay sa iyo guys upang ganap na malaman lamang ano ang pinakamabilis at pinaka mahusay na paraan upang ipatupad ito. Oo? Madla: Pinapahintulutan namin na kung wanted sa pananaliksik mas mabilis na paraan gawin hash talahanayan online, maaari naming gawin na at sipiin code ng ibang tao? ANDI PENG: Oo, ganap na fine. Kaya't kung ikaw guys basahin ang spec, may isang linya sa spec na nagsasabing kayo guys ay libre upang magsaliksik ng hash function sa kung ano ang ilang ng mas mabilis na mga pag-andar hash upang magpatakbo ng mga bagay-bagay sa pamamagitan ng bilang hangga't banggitin mo na ang code. Kaya ang ilang mga tao ay may mga naka korte ang mabilis na paraan ng paggawa ng spell dama, ng mabilis paraan ng pag-iimbak ng impormasyon. Lubos na nakasalalay sa iyo guys kung ikaw nais na kunin lang iyon, di ba? Tiyakin na ikaw ay binabanggit. Ang hamon dito talagang na kami ay sinusubukan upang subukan ay siguraduhin na alam mo ang iyong paraan sa paligid ng mga payo. Bilang malayo bilang ka pagpapatupad ang aktwal na pag-andar hash at pagdating sa tulad ng ang matematika upang gawin iyon, ka guys ay maaaring magsaliksik ng kahit anong pamamaraan online ka guys gusto. Oo? Madla: Maaari naming banggitin lamang pamamagitan ng paggamit ng [hindi marinig]? ANDI PENG: Oo. Ikaw lamang ang maaaring, sa iyong mga komento, maaari mong sipiin tulad ng, oh, kinuha mula sa EK, EK, yada, hash. Sinuman ay may anumang mga katanungan? Kami ay talagang breezed sa pamamagitan ng seksyon na ngayon. Ako ay magiging up para sagutin ang mga tanong na rin. Gayundin, tulad ng sinabi ko, office oras ngayong gabi at bukas. Ang spec this week ay talagang napakadaling at super maikling magbasa. Imumungkahi ko ang pagkuha ng isang pagtingin, makatarungan basahin sa pamamagitan ng kabuuan ng mga ito. At Zamyla talagang nagtuturo sa iyo sa sa pamamagitan ng bawat isa sa mga pag-andar kailangan mo upang ipatupad, at sa gayon ito ay tunay, tunay na malinaw kung paano gawin ang lahat. Lamang upang matiyak na ikaw ay pagpapanatili ng track ng mga payo. Ito ay isang lubhang mahirap pset. Ito ay hindi mahirap dahil gusto, naku, ang mga konsepto ay kaya marami pang iba mahirap, o kailangan mong malaman kaya magkano bagong syntax ng ang paraan na ginawa mo para sa huling pset. Pset na ito ay mahirap dahil may mga kaya maraming mga payo, at pagkatapos ay masyadong, napakadaling isang beses ikaw ay may isang bug sa iyong code ay hindi ma upang mahanap kung saan na bug ay. At kaya kumpleto at salitain pananampalataya sa iyo guys para makapag-matalo ang aming [hindi marinig] baybay. Ako tunay na may hindi anumang nakasulat mine pa, ngunit ako isusulat ko. Kaya habang ikaw ay sumusulat iyo, Kukunin ko ay sumusulat mine. Pupunta ako sa subukan na gumawa minahan ng mas mabilis kaysa sa iyo. Susubukan naming makita kung sino ang may pinakamabilis na isa. At oo, ako makita ang lahat ng kayo guys dito sa Martes. Ako ay tatakbo sa isang uri tulad ng isang pset workshop. Lahat ng mga seksyon na ito linggo ay pset workshops, kaya ikaw ay may isang lalaki ng maraming pagkakataon para sa tulong, mga oras ng opisina gaya ng lagi, at talagang ako inaabangan pagbabasa ng lahat ng code sa iyong mga guys '. Mayroon up quizzes ko dito kung ikaw Gusto guys na dumating makakuha ng mga iyon. Iyan na ang lahat.