[Musika sa pag-play] David MALAN: Ito ang CS50. At ito ay ang parehong sa simula at ang end-- tulad ng literally-- halos dulo ng linggo anim. 

Akala ko Gusto ko magbahagi ng Medyo ng isang masaya katotohanan. Nakuha ko na ito up mula sa isang itakda ang data ng nakaraang semestre ay. Maaari mong isipin na hinihiling namin sa iyo sa bawat hanay ng form p kung pinapanood online o kung nag-aral sa tao. At dito ay ang data. Kaya ngayon ay napaka mahuhulaang. Pero gusto naming gastusin ng kaunti ng panahon sa iyo gayunman. Gusto sinuman nais na haka-haka kung bakit ito Ang graph ay kaya may mga tulis, hanggang pababa, pataas pababa, kaya tuloy-tuloy? Ano ang bawat isa sa mga peak at troughs kumakatawan? 

Madla: [hindi marinig] David MALAN: Sa katunayan. At higit pa amusingly, diyos ipagbawal, hawakan namin ang isang aralin sa isang Biyernes sa simula ng semestre, na kung ano ang namin makita ang mangyayari. Kaya ngayon, makibahagi namin sa ilang sandali higit pa tungkol sa mga istraktura ng data. At upang magbigay ng higit pa sa isang matatag ka modelo ng isip para sa mga problema sa limang, na ngayon ay out. Mga maling spelling, kung saan, kami ay ibigay sa iyo ng isang text file ilang 100,000 plus mga salitang Ingles, at ka ng pagpunta sa may upang malaman kung paano cleverly-load ang mga ito sa memory, sa RAM, gamit ang ilang data istraktura na iyong gusto. 

Ngayon isa tulad istraktura ng data ng dati , ngunit marahil ay hindi dapat, ang medyo simplistic naka-link na listahan, na ipinakilala namin huling beses. At isang naka-link na listahan ay nagkaroon ng hindi bababa sa isang kalamangan sa isang array. Ano ang isang kalamangan ng naka-link na listahan arguably? 

Madla: Insertion. 

David MALAN: Insertion. Ano ang ibig mong sabihin sa pamamagitan ng na? 

Madla: Saanman sa kahabaan ang listahan [hindi marinig]. 

David MALAN: Mahusay. Kaya maaari mong ipasok ang isang elemento kung saan man Gusto mo sa gitna ng listahan nang hindi na kinakailangang kaladkarin ang mga paa ng anumang bagay, na aming Napagpasyahan ng mga, sa aming uuri-uri mga talakayan, ay hindi nangangahulugang isang magandang bagay, dahil nangangailangan ng panahon upang aktwal na ilipat lahat ng mga tao pakaliwa o pakanan. At kaya may naka-link na listahan, maaari kang maglaan lamang sa malloc, isang bagong node, at pagkatapos ay i-update ng ilang mga pointers-- dalawa, tatlo pagpapatakbo max-- at magawa naming puwang ng isang tao sa kahit saan sa isang listahan. 

Ano pa ay may pakinabang tungkol sa isang naka-link na listahan? Oo? 

Madla: [hindi marinig] David MALAN: Perpekto. Perpekto. Ito ay talagang dynamic. At na hindi ka paggawa, nang maaga, sa ilang mga nakapirming laki tipak ng memorya, tulad ng gusto mong magkaroon ng sa gamit ang isang array, ang bentahe ng na ay maaari mong maglaan ng node lamang sa demand na sinusulit ang paggamit lamang ng mas maraming espasyo ng kung aktwal na kailangan mo. Sa pamamagitan ng kaibahan sa isang array, maaari kang aksidenteng maglaan ng masyadong maliit. At pagkatapos lamang ito nangyayari maging isang sakit sa ulo upang reallocate ng isang bagong mas malaking array, kopyahin lahat ng bagay sa ibabaw, magbakante sa lumang array, at pagkatapos ay ilipat ang tungkol sa iyong negosyo. O mas masahol pa, maaari kang magtalaga ng paraan higit pang memory kaysa sa aktwal na kailangan mo, at kaya ka ng pagpunta sa magkaroon ng isang napaka sparsely-populated na array, kaya upang makipag-usap. 

Kaya ay nagbibigay sa iyo ng isang naka-link na listahan ng mga bentahe ng dynamism at kakayahang umangkop may mga pagpapasok at pagtatanggal. Ngunit tiyak ay dapat na mayroong isang presyo na babayaran. Sa katunayan, ang isa sa mga tema ginalugad sa pagsusulit zero ay isang pares ng mga trade-off nasaksihan namin sa gayon ay malayo. Kaya kung ano ang isang presyong nabayaran o isang downside ng isang naka-link na listahan? Oo. 

Madla: Walang random na pag-access. 

David MALAN: Walang random na pag-access. Ngunit na nagmamalasakit? Random na access ay hindi akma sa nakapanghihimok. 

Madla: [hindi marinig] David MALAN: Eksaktong. Kung gusto mong magkaroon ng isang tiyak na algorithm-- at ipaalam sa akin aktwal na ipanukala binary paghahanap sa partikular, na ay isa na ginagamit namin ang isang medyo bit-- kung hindi mo na kailangang random na pag-access, hindi mo maaaring gawin iyon simpleng palatuusan ng paghahanap tulad ng gitnang elemento at tumatalon karapatang ito. Sa halip ay mayroon kang upang magsimula sa unang elemento at linearly naghahanap mula sa kaliwa sa kanan kung gusto mong mahanap ang gitna o anumang iba pang mga elemento. 

Madla: marahil tumatagal ng higit pang memory. 

David MALAN: Dadalhin higit pang memory. Saan ang karagdagang gastos na nagmumula sa sa memory? 

Madla: [hindi marinig] David MALAN: Eksaktong. Sa kasong ito dito, nagkaroon kami isang listahan na naka-link para sa integer, at pa naka-pagdodoble namin ang dami ng memorya kailangan naming sa pamamagitan ng pag-iimbak din ang mga payo. Ngayon mas mababa ng isang malaking bilang deal ang iyong structs makakuha ng mas malaki at tapos ka sa pag-iimbak hindi isang numero ngunit siguro isang mag-aaral o ilang iba pang mga bagay. Ngunit ang punto ay tiyak na nanatiling. At sa gayon ang isang bilang ng mga pagpapatakbo sa naka-link na listahan ay tinawag ay malaki O ng n-- linear. Mga bagay tulad ng paghahanap na pagpapasok o o pagtanggal sa kaso ng isang elemento ang nangyari sa maging sa pinakadulo ng ang listahan ng kung ito ay pinagsunod-sunod o hindi. 

Minsan maaari kang makakuha ng masuwerteng at sa kaya mas mababang mga hangganan sa mga pagpapatakbong ito maaari ring maging pare-pareho ang oras kung ikaw ay laging naghahanap sa unang elemento, halimbawa. Ngunit sa huli, aming ipinangako upang makamit ang banal na Kopita ng mga istraktura ng data, o ang ilang mga pagtatantya nito, sa paraan ng pare-pareho ang oras. Puwede ba kaming mahanap ang mga elemento o magdagdag ng mga elemento o alisin ang mga elemento mula sa isang listahan? Ay dapat namin makita pa sa lalong madaling panahon. At ito ay lumiliko ang isa na ng mga mekanismo kami pagpunta sa simulan na gamitin ngayon, taunang paggamit sa p-set limang, ay talagang kaakit-akit na pamilyar. Halimbawa, kung ito ay isang bungkos ng mga aklat pagsusulit, ang bawat isa May isang mag-aaral muna ni pangalanan at apelyido dito, at ako kunin ang mga ito mula sa sa dulo ng isang pagsusulit, at ang mga ito ay ang lahat ng kaakit-akit magkano sa isang random na pagkakasunod-sunod, at gusto naming pumunta tungkol sa pag-uuri ang mga pagsusulit nang sa gayon ay isang beses gradong ito ay isang marami lang mas madali at Mas mabilis na ipasa ang mga ito pabalik out mag-aaral ayon sa abakada. Ano ang gusto iyong instincts maging para sa isang tumpok ng mga pagsusulit na tulad nito? 

Well, kung ikaw ay tulad ng sa akin, ikaw Maaaring makita na ito ay m, kaya ako pagpunta sa uri ng ilagay ito sa, kung ito ang aking talahanayan o ang aking palapag kung saan Ako nagkakalat bagay out-- o ang aking array really-- Maaari ko bang ilagay ang lahat ng mga Ms doon. Oh. Narito ang isang A. Kaya maaari ko ilagay ang Tulad ng sa paglipas dito. Oh. Narito ang isa pang A. pupuntahan ko upang ilagay na sa paglipas dito. Narito ang isang Z. Narito ang isa pang M. At kaya Maaaring simulan ko na gawin piles tulad nito. At pagkatapos ay marahil Gusto ko pumunta sa ibang pagkakataon at uri ng napaka-nitpicky-.ly pag-uuri ang mga indibidwal na piles. Ngunit ang punto ay gusto ko bang tingnan sa input na ako kamay at gusto kong gumawa ng ilang kinakalkula batay sa input na desisyon. Kung nagsisimula ito sa A, ilagay ito doon. Kung nagsisimula ito sa Z, ilagay ito sa paglipas ng doon, at lahat ng bagay sa pagitan. 

Kaya ito ay isang diskarte na Sa pangkalahatan ay kilala bilang hashing-- H-A-S-H-- na sa pangkalahatan ay nangangahulugan na ang pagkuha ng -input at paggamit ng pag-input na upang makalkula isang halaga, sa pangkalahatan ay isang numero, at na bilang na ito ay index sa isang imbakan lalagyan, tulad ng isang array. Kaya sa ibang salita, maaaring mayroon akong hash, tulad ng ginagawa ko sa aking ulo, na kung makikita ko ang isang tao ay pangalan na nagsisimula sa A, Pupunta ako sa map na sa zero sa aking ulo. At kung makikita ko ang isang tao na may Z, ako pagpunta sa map na sa 25 sa aking ulo at pagkatapos ay ilagay na sa ang huling pinaka-pile. 

Ngayon, kung sa tingin mo tungkol sa hindi aking utak ngunit isang programa C, kung ano ang mga numero ng dati umasa sa upang makamit ang parehong resulta? Sa ibang salita, kung Nagkaroon ng ASCII na character na A, paano ko sa iyo na matukoy ano bucket upang ilagay ito sa? Malamang na hindi nais na ilagay ito sa bucket 65, na ay magiging tulad ng doon para sa walang magandang dahilan. Saan mo nais na ilagay ang isang sa mga tuntunin ng halaga ASCII nito? Saan ang gusto mong gawin sa kanyang ASCII halaga upang makabuo ng isang mas matalinong bucket upang ilagay ito sa? 

Madla: Minus A. 

David MALAN: Oo. Kaya minus A o minus partikular na 65 kung ito ay ng kapital A. O 98 kung ito ay isang maliit na mga a. At upang ang daan sa amin na, napaka nang simple at napaka-arithmetically, maglagay ng isang bagay sa isang bucket tulad na. Kaya ito ay lumiliko ang aktwal na namin gawin ito pati na rin kahit na ang mga pagsusulit. 

Kaya maaari mong isipin ang mo ang iyong circled Pangalan ng pagtuturo kapwa sa mga pabalat. At pangalan ng tf ni ay isinaayos sa mga hanay na ito ayon sa abakada, well, naniniwala ito o hindi, kapag ang lahat ng 80 plus sa atin Nakakuha magkasama ang iba pang mga gabi sa grado, ang huling hakbang sa aming proseso grading ay ang pag-hash ang pagsusulit sa isang malaking espasyo ng sahig sa [hindi marinig] at upang mag-ipon ng mga pagsusulit ng lahat out sa eksaktong pagkakasunud-sunod ng kanilang tf ni mga pangalan sa cover, dahil pagkatapos ay ito ay isang mas madaling para sa amin upang maghanap sa pamamagitan ng na ang paggamit ng linear maghanap o ilang mga uri ng talino para sa isang tf upang makita ang kanyang o mga pagsusulit sa kanyang mga mag-aaral '. 

Kaya ito ideya ng hashing na makikita mo ay masyadong malakas ay talagang kaakit-akit palasak at napaka madaling maunawaan, tulad marahil hatiin at gumahis ay nasa linggo zero. Ako mabilis inaabangan ang panahon na ang hackathon ng dalawang taon na ang nakakaraan. Ito ay Zamyla at isang pares ng mga iba pang mga mag-aaral na pagbati kawani bilang sila ay dumating sa. At nagkaroon kami ng buong bungkos ng natitiklop mga talahanayan doon sa mga name tag. At kami ay isinaayos ng mga name tag may tulad ng Tulad ng doon at ang Zs doon. At kaya isa sa mga TFs napaka cleverly nagsulat na ito bilang ang mga tagubilin para sa araw. At sa linggo 12 ng semestre na ito lahat ginawa perpektong pakiramdam at ang lahat Alam kung ano ang gagawin. Ngunit anumang oras ikaw ay nakapila sa parehong paraan, ka sa pagpapatupad ng mga parehong kuru-kuro ng isang hash. Kaya gawing pormal natin ito nang kaunti ipaalam. Narito ang isang array. Ito ay iginuhit upang maging isang maliit na malawak lamang sa ilarawan, biswal, na maaari naming ilagay ang mga string sa isang bagay na katulad nito. At ito array ay malinaw na sukat ng 26 kabuuang. At ang bagay ay tinatawag na talahanayan nagkataon. Ngunit ito lamang ang pag-awit ng artist ng kung ano ang maaaring maging isang hash table. 

Kaya isang hash talahanayan ngayon ay pagpunta sa maging isang mas mataas na istraktura ng data na antas. Sa pagtatapos ng araw kami ay tungkol sa upang makita na iyong Maaari ipatupad ang hash talahanayan, na ay halos tulad ng linya ng check-in sa isang hackathon tulad ito talahanayan na ginagamit para sa pagbubukod-bukod ng mga aklat pagsusulit. Ngunit isang hash talahanayan ay uri ng mga ito mataas na antas konsepto na maaaring gamitin ng isang array sa ilalim ng hood sa ipatupad ito, o maaaring gumamit ng isang listahan ng haba, o kahit na marahil ilang iba pang mga istraktura ng data. At ngayon na ang theme-- pagkuha ang ilan sa mga pangunahing sangkap tulad ng isang array at ang gusaling ito -block na ngayon ng isang listahan ng haba at makita kung ano pa ang maaari naming bumuo ng sa itaas ng mga, tulad ng mga sangkap sa isang recipe, na ginagawang higit pa at higit pa kawili-wili at kapaki-pakinabang huling resulta. 

Kaya gamit ang hash talahanayan maaari naming ipatupad ito sa memory pictorially na tulad nito, ngunit kung paano maaaring aktwal na ito ay naka-code up? Well, siguro ay ito bilang simple. Kung kapasidad sa lahat ng mga pag-cap, ay lamang ilang constant-- halimbawa 26, para sa 26 titik ng alphabet-- Maaaring tumawag ako variable talahanayan aking, at maaaring i-claim ko na pupuntahan ko ilagay char bituin sa doon, o string. Kaya ito ay kasing simple ng ito kung nais na ipatupad ng hash table. At pa, ito ay talagang lamang ng isang array. Ngunit muli, isang hash talahanayan na ngayon kung ano ang kami ay tumawag sa isang abstract na uri ng data na lamang uri ng isang haka-haka layering sa tuktok ng isang bagay na mas pangmundo ngayon gusto ang isang array. 

Ngayon, paano mo kami tungkol sa paglutas ng mga problema? Well, mas maaga ako ay nagkaroon ng luxury ng pagkakaroon ng sapat na espasyo talahanayan dito nang sa gayon ay maaari ko bang ilagay ang mga pagsusulit sa kahit saan ko gusto. Kaya Tulad ng maaaring pumunta dito. Baka pumunta dito Zs. Ms maaaring umalis dito. At pagkatapos ay nagkaroon ako ng ilang dagdag na espasyo. Ngunit ito ay isang bit ng isang impostor kanan ngayon dahil table na ito, kung ako talaga naisip ng ito bilang isang array, ay lamang magiging ng ilang mga nakapirming laki. 

Kaya technically, kung hilahin ko up ng isa pang pagsusulit ng mag-aaral at tingnan, oh, ng taong ito pangalan ay nagsisimula sa isang A masyadong, Ako uri ng nais na ilagay ito doon. Ngunit sa lalong madaling ko bang ilagay doon, kung talahanayang ito sa katunayan ay kumakatawan sa isang array, Pupunta ako sa i-override o clobbering kung sinuman ang pagsusulit ng mag-aaral na ito ay. Mag-right? Kung ito ay isang array, tanging isang bagay na maaari pumunta sa bawat isa sa mga cell o mga elemento. At kaya ko uri ng mayroon upang pumili at piliin ang. 

Ngayon mas maaga ako uri ng ginulangan at ginawa ito o ko lamang uri ng nakasalansan ang mga ito sa itaas ng bawat isa. Ngunit na hindi pagpunta sa lumipad sa code. Kaya kung saan maaari ko bang ilagay ang pangalawang mag-aaral na ang pangalan ay isang kung ang lahat ko ay nagkaroon ay ito magagamit na puwang ng talahanayan? At ginamit ko ang tatlong mga puwang at ito Mukhang mayroong ilang iba. Ano ang maaari mong gawin? Madla: [hindi marinig] David MALAN: Oo. Siguro hayaan panatilihin ito ng mga simpleng lamang. Mag-right? Hindi ito magkasya kung saan ako gustong ilagay ito. Kaya ako pagpunta sa ilagay ito technically kung saan ang isang B ay pupunta. Ngayon, siyempre, ako nagsisimula upang ipinta ang aking sarili sa isang sulok. Kung nakuha ko sa isang mag-aaral ang pangalan ay talagang B, ngayon B ay pagpunta sa ililipat ng kaunti pasulong, tulad ng maaaring mangyari, yep, kung ito ay isang B, ngayon ito ay may upang pumunta dito. 

At kaya ito masyadong mabilis maaaring maging problema, ngunit ito ay isang diskarte na aktwal na ay tinutukoy na linear probing, kung saan isaalang-alang mo lamang ang iyong array na sa kahabaan ng linya. At mo lamang uri ng suriin o siyasatin bawat magagamit na elemento naghahanap para sa isang magagamit na lugar. At sa lalong madaling mahanap ka isa, i-drop mo ito doon. 

Ngayon, ang presyo na binabayaran ngayon para sa solusyon na ito ay kung ano? Mayroon kaming nakapirming laki ng array, at kapag ipasok ko pangalan sa ito, hindi bababa sa una, kung ano ang ang oras ng paggana ng pagpapasok para sa paglalagay ng mga mag-aaral ' mga pagsusulit sa kanang bucket? Big O kung ano? 

Madla: n. David MALAN: Narinig ko malaking O ng n. Hindi totoo. Ngunit kami ay mang-ulol hiwalayin kung bakit sa sandali lamang. Ano pa ang maaari itong maging? 

Madla: [hindi marinig] David MALAN: At hayaan mo akong gawin ito biswal. Kaya ipagpalagay na ito ay ang titik S. 

Madla: Ito ay isa. David MALAN: Ito ay isa. Mag-right? Ito ay isang array, na Nangangahulugan mayroon kaming mga random na pag-access. At kung sa tingin namin ng ito bilang zero at ito bilang 25, at Napagtanto namin na, naku, narito ang aking input S, Maaari ko tiyak na mag-convert S, isang character na ASCII, sa isang katumbas na dami sa pagitan ng zero at 25 at pagkatapos ay agad-agad ilagay ito kung saan ito ay kabilang. 

Ngunit siyempre, sa lalong madaling makakuha ako sa pangalawang tao kung sino ang pangalan ay A o B o C Sa kalaunan, kung iyong ginamit ko ang linear probing bilang aking solusyon, ang oras ng paggana ng pagpapasok sa pinakamasamang sitwasyon ay talagang pagpunta sa malipat sa kung anong? At ko narinig ito dito tama nang maaga. Madla: [hindi marinig] David MALAN: Kaya ito ay sa katunayan n-sabay mayroon kang sapat na malaki ang hanay ng data. Kaya, sa isang banda, kung ang iyong mga array ay sapat na malaki at ang iyong data ay kalat-kalat sapat, mo makuha ang magandang pare-pareho ang oras. Ngunit sa lalong madaling simulan mo pagkuha ng higit pa at higit pang mga elemento, at istatistika lamang kang makakuha ng higit pang mga tao na may sulat Ang bilang kanilang pangalan o ang titik B, ito ay maaaring potensyal na malipat sa isang bagay na mas linear. Kaya hindi pa perpekto. Kaya maaari naming gawin mas mahusay? 

Well, kung ano ang aming solusyon bago kung kailan namin nais na magkaroon ng higit pa sa dynamism isang bagay tulad ng isang array pinapayagan? Madla: [hindi marinig] David MALAN: Ano ang ipakilala kami? Oo. Kaya naka-link na listahan. Well, sabihin makita kung ano ang isang naka-link maaaring gawin listahan para sa amin sa halip. Well, hayaan mo akong magpanukala na namin gumuhit ng larawan tulad ng sumusunod. Ngayon ito ay isang iba't ibang larawan mula sa isang halimbawa mula sa ibang teksto, talaga, na ay aktwal na paggamit ng isang hanay ng mga laki 31. At lamang ang may-akda nagpasyang hash string hindi batay sa mga pangalan ng tao, ngunit batay sa kanilang birthdates. Hindi isinasaalang-alang ng buwan, sila ay may korte kung gumagamit ka ipinanganak sa unang ng buwan o ang ika-31 ng buwan, ang may-akda ay hash batay sa halaga na iyon, upang ikalat ang mga pangalan out ng kaunti higit pa kaysa sa maaaring payagan lamang 26 spot. At marahil ito ay isang kaunti pa uniporme kaysa sa pagpunta sa alpabetikong titik, dahil sa kurso doon ay marahil higit pang mga tao sa mundo na may mga pangalan na panimula sa isang tiyak kaysa sa ilang iba pang mga titik ng alpabeto. Kaya marahil ito ay isang maliit na higit uniporme, sa pag-aakala isang pare-parehong pamamahagi ng sanggol sa isang buwan. 

Ngunit, siyempre, ito ay hindi lubos na pagsisisi pa rin. Mag-right? Nagkakaroon kami ng collisions. Maraming tao sa istraktura ng data ay pa rin pagkakaroon ng parehong petsa ng kapanganakan ng hindi bababa sa ikaw ay hindi isinasaalang-alang ng buwan. Ngunit kung ano ang ginawa ng may-akda? Well, mukhang mayroon kaming isang array sa kaliwang gilid iginuhit patayo, ngunit ito lamang ay pag-awit ng artist. Hindi mahalaga kung ano ang direksyon mo gumuhit ng isang array, ito ay isang array pa rin. Ano ang isang array ng wari? 

Madla: Naka-link na listahan. 

David MALAN: Oo. Mukhang ito ay isang hanay ng mga naka-link na listahan. Kaya muli, sa punto ng pag-uuri ng paggamit ng mga kaayusan data ngayon bilang sangkap sa mas maraming kagiliw-giliw na mga solusyon, maaari mong ganap na kumuha ng isang pangunahing, tulad ng isang array, at pagkatapos gumawa ng isang bagay na higit pa kagiliw-giliw na tulad ng isang naka-link na listahan at kahit pagsamahin ang mga ito sa isang pantay na mas kawili-wiling istraktura ng data. At sa katunayan, ito masyadong gagawin tawagin ng hash table, kung saan ang array ay talaga ang hash talahanayan, ngunit na hash talahanayan ay chain, kaya upang magsalita, na maaaring lumaki o Paliitin batay sa numero ng mga elemento na gusto mong ipasok. 

Ngayon, nang naaayon, kung ano ang ang oras tumatakbo na ngayon? Kung gusto kong ipasok ang isang tao na ang kaarawan ay Oktubre 31, kung saan ay siya pumunta? Lahat ng karapatan. Sa ilalim napaka kung saan sinasabi nito na 31. At iyon ay perpekto. Iyon ay pare-pareho ang oras. Ngunit paano kung malaman naming ibang tao na ang kaarawan ay, sabihin makita, Oktubre, Nobyembre, Disyembre 31? Saan ay siya pagpunta sa pumunta? Parehong bagay. Dalawang hakbang na. Iyon ay pare-pareho kahit na hindi ito? Lahat ng karapatan. Sa sandaling ito ay. Ngunit sa pangkalahatang kaso, ang higit pang mga tao magdagdag namin, probabilistically, kami ay pagpunta upang makakuha ng higit at higit pa collisions. 

Ngayon ito ay isang maliit na mas mahusay dahil technically ngayon ang aking chain ay maaaring maging sa ang pinakamasamang sitwasyon kung gaano katagal? Kung ipasok ko n ang mga tao sa ito nang higit pa sopistikadong istraktura ng data, n tao, sa pinakamalala kaso ito ay magiging n. Bakit? 

Madla: Dahil kung lahat May parehong petsa ng kapanganakan, sila ay magiging isang linya. David MALAN: Perpekto. Maaaring maging isang maliit na contrived, pero tunay na sa pinakamasamang sitwasyon, kung ang lahat ay may parehong petsa ng kapanganakan, na naibigay ang mga input na mayroon ka, na iyong pupuntahan ay may massively mahabang chain. At kaya, maaari mo itong isang tumawag hash talahanayan, ngunit talagang ito isang napakalaking listahan ng naka-link lamang sa marami ng nasayang na espasyo. Ngunit sa pangkalahatan, kung ipinapalagay namin na hindi bababa sa mga kaarawan ng mga uniform-- at ito ay malamang na hindi. Ako sa paggawa na up. Ngunit kung ipinapalagay namin, para sa ang alang-alang ng talakayan na ang mga ito, pagkatapos ay sa teorya, kung ito ay ang vertical na representasyon ng array, na rin pagkatapos sana ikaw ay pagpunta upang makakuha ng chain na, alam mo na, halos kapareho ng haba kung saan ang bawat isa sa ang mga kumakatawan sa isang araw ng buwan. 

Ngayon kung mayroong 31 araw sa buwan, nangangahulugan iyon na aking ng panahon talaga ay malaking O ng n higit sa 31, na pakiramdam ng mas mahusay kaysa sa linear. Ngunit ano ang isa sa aming mga pagtatalaga ng ilang linggo nakalipas tuwing ito ay dumating sa pagpapahayag ang oras ng paggana ng isang algorithm? Lamang tumingin lamang sa mataas na terminong ginamit sa pagkakasunod-sunod. Mag-right? 31 ay talagang kapaki-pakinabang. Ngunit ito ay malaking O ng n pa rin. Ngunit ang isa sa mga tema ng problema itakda ang limang ay magiging sa Kinikilala na ganap, asymptotically, theoretically ang istraktura ng data Walang mas mahusay kaysa lamang isang napakalaking naka-link na listahan. At sa katunayan, sa pinakamasama kaso, ito Maaaring malipat hash talahanayan sa iyon. 

Ngunit sa tunay na mundo, sa amin tao na sariling mga Mac o PC o anumang at tumatakbo ang tunay na mundo software sa totoong data mundo, na algorithm pupunta ka ba sa ginusto? Ang isa na tumatagal ng mga hakbang sa dulo o ang isa na tumatagal n hinati sa 31 mga hakbang upang makahanap ng ilang mga piraso ng data o upang maghanap ng ilang mga impormasyon? Ibig kong sabihin, walang pasubali sa 31 Gumagawa isang pagkakaiba sa tunay na mundo. Ito ay 31 beses na mas mabilis. At namin ang mga tao ay tiyak pagpunta sa Pinahahalagahan na iyon. 

Kaya Napagtanto ang paghihiwalay sa dalawang bahagi doon sa pagitan ng aktwal na pakikipag-usap tungkol sa mga bagay theoretically at asymptotically na siguradong May halaga bilang nasaksihan namin, ngunit sa tunay na mundo, kung mahalaga sa iyo sa paggawa ng lamang ang masaya tao para sa pangkalahatang input, maaari mong lubos na rin nais na tanggapin ang katotohanan na, oo, ito ay linear, ngunit ito ay 31 beses na mas mabilis kaysa sa guhit ay maaaring maging. At mas mahusay pa, hindi namin lamang magkaroon upang gawin ang isang bagay arbitrary tulad ng isang petsa ng kapanganakan, maaari kaming magpalipas ng kaunti mas maraming oras at katalasan ng isip at sa tingin tungkol sa kung ano ang maaari naming gawin, ibinigay na pangalan at marahil ng isang tao ang kanilang mga petsa ng kapanganakan upang pagsamahin ang mga sangkap upang malaman kung ang isang bagay na tunay na higit pa pare-pareho at mas may mga tulis, kaya upang makipag-usap sa larawang ito Kasalukuyang nagmumungkahi maaari itong maging. Paano namin ipatupad ito sa code? Well, hayaan mo akong magpanukala na namin humiram lamang ng ilang syntax hindi namin ginamit ng ilang beses kaya sa ngayon. At ako pupunta upang tukuyin ang isang node, na muli ay isang generic na termino para lamang ng ilang lalagyan para sa ilang mga istraktura ng data. Pupunta ako sa ipanukala na isang string ay pagpunta sa doon. Ngunit kami ay pagpunta upang simulan ang pagkuha mga pagsasanay gulong-off ngayon. 

Wala nang CS50 library talaga ito, maliban kung gusto mo gamitin ito para sa iyong panghuling proyekto, na kung saan ay multa, ngunit ngayon kami ay pagpunta upang hilahin pabalik ang kurtina at sabihin ito ay lamang ng isang pansamantalang trabaho star. Kaya ang salitang doon ay magiging pangalan ng tao na pinag-uusapan. At ngayon Mayroon akong isang link dito sa susunod na node upang ang mga kumatawan bawat isa sa mga node sa chain, potensyal, ng isang naka-link na listahan. 

At ngayon kung paano gawin Ipinahahayag ko mismo ang hash talahanayan? Paano ko idedeklara ito buong kaayusan? Well, talaga, tulad ng ginamit ko ng isang pointer lang sa unang elemento ng isang listahan bago, katulad maaari ko lang sabihin Kailangan ko lamang ng isang bungkos ng mga payo upang ipatupad ang buong hash talahanayan. Pupunta ako sa may isang array tinatawag na table para sa hash talahanayan. Ito ay magiging ng kapasidad laki. Iyon ay kung gaano karaming mga elemento mapagkasya sa loob nito. At bawat isa sa mga elemento sa array ay magiging isang node bituin. Bakit? Well, sa bawat ang larawang ito, kung ano ang ako pagpapatupad ng hash talahanayan bilang epektibo sa simula lamang ang array na na-iginuhit namin nang patayo, ang bawat isa sa kung saan ang mga parisukat ay kumakatawan sa isang pointer. Na mga na may slashes sa pamamagitan ng mga ito ay lamang null. At ang mga na mayroon mga arrow ng pagpunta sa kanan ay mga aktwal na pointer sa aktwal na node, samakatuwid sa simula ng isang naka-link na listahan. 

Kaya dito, pagkatapos, ay kung paano namin maaari ipatupad ng hash talahanayan na ipinapatupad ng nakahiwalay na chaining. Ngayon ay maaari naming gawin mas mahusay? Ang lahat ng mga karapatan ipinangako ko huling beses na maaari kaming makamit ang pare-pareho ang oras. At uri ng ko ibinigay sa iyo pare-pareho ang oras dito, ngunit pagkatapos ay sinabi hindi talaga pare-pareho ang oras dahil ito ay pa rin nakadepende sa kabuuang numero ng mga elemento ka inputting sa ang istraktura ng data. Ngunit ipagpalagay na ginawa namin ito. Hayaan akong bumalik sa screen sa paglipas dito. Hayaan akong i-project din up dito, malinaw na screen, at ipagpalagay na ginawa ko ito. Ipagpalagay na nais kong ipasok ang pangalan Daven sa sa aking istraktura ng data. 

Kaya gusto kong ipasok ang isang string Daven sa istraktura ng data. Paano kung hindi ko ginagamit ang hash talahanayan, ngunit gagamitin ko isang bagay na mas tree-tulad ng tulad ng isang pamilya tree, kung saan mayroon kang ilang mga ugat sa itaas at pagkatapos ay i-node at mga dahon na pumunta pababa at palabas. Ipagpalagay na pagkatapos, na aking Gusto upang ipasok Daven ni sa kung ano ang kasalukuyang isang walang lamang listahan. Pupunta ako sa gawin ang mga sumusunod: ako pagpunta upang lumikha ng isang node sa pamilya na ito tree-tulad ng istraktura ng data na ganito ang isang maliit na tulad nito, ang bawat isa mga parihaba ay, sabihin nating, sa ngayon 26 mga elemento sa loob nito. At bawat isa sa mga cell sa array ay pagpunta upang kumatawan sa sulat ng isang alpabeto. 

Sa partikular, pupunta ako sa paggamot sa ito ay A, pagkatapos ay B, pagkatapos ay C, pagkatapos D, ang isang ito dito. Kaya ito ay pagpunta upang epektibong kumakatawan sa mga titik D. Ngunit upang ipasok ang lahat ng Daven ni pangalanan ang kailangan kong gawin nang kaunti pa. Kaya ako unang pagpunta sa hash, kaya upang makipag-usap. Pupunta ako sa tumingin sa ang unang titik sa Daven kung saan ay malinaw naman isang D, at ako pagpunta sa maglaan isang node na mukhang tulad ng this-- isang malaking parihaba malaki sapat na upang magkasya ang buong alpabeto. 

Ngayon D ay tapos na. Ngayon A. D-A-V-E-N ay ang layunin. Kaya ngayon kung ano ang ako pagpunta sa gawin ay ito. Sa sandaling sinimulan ko notice D walang pointer doon. Ito ay mga halaga ng basura sa sandaling ito, o maaaring initialize ko ito sa null. Ngunit hayaan mo akong panatilihing pagpunta sa ang ideya ng pagbuo ng isang puno. Hayaan akong maglaan ng isa pang isa sa mga node na may 26 mga elemento sa loob nito. 

At alam mo kung ano? Kung ito ay isang node lamang sa memorya na Nilikha ko ang malloc, gamit ang isang struct bilang makikita sa lalong madaling panahon namin makita, Pupunta ako sa gawin this-- Pupunta ako upang gumuhit ng isang arrow mula sa ang bagay na kinakatawan D pababa sa bagong node. At ngayon, sa unang susunod na sulat sa pangalan ni Daven, V-- D-A-V-- Pupunta ako sa sige at gumuhit ng isa pang node na tulad nito, kung saan, ang mga elemento ng V dito, na kami ay gumuhit para sa instance-- Oops. Hindi namin gumuhit doon. Ito ay pagpunta sa pumunta dito. 

Pagkatapos kami ay pagpunta sa isaalang-alang na ito upang maging V. At pagkatapos ay down na dito kami ng pagpunta sa index down na mula sa V sa kung ano ang makikita namin isaalang-alang ang E. At pagkatapos ay mula dito kami ng pagpunta sa pumunta magkaroon ng isa sa mga node dito. At ngayon kami ay may isang tanong upang sagutin. Kailangan ko bang kahit papaano ay nagpapahiwatig na Ikinalulungkot namin sa dulo ng string Daven. Kaya maaari ko bang iwan lang ito null. 

Ngunit kung ano kung mayroon Daven ng namin buong pangalan din, na ay, pati na sinabi namin, Davenport? Kaya kung ano kung Daven ay tunay na isang substring, isang prefix ng isang mas matagal string? Hindi namin magagawa permanenteng lamang sabihin walang pagpunta pumunta doon, dahil maaari naming Hindi kailanman magpasok ng isang salita tulad ng Davenport sa ito Istraktura ng data 

Kaya ano ang maaari naming gawin sa halip ay ituturing ng bawat isa sa mga elemento bilang marahil pagkakaroon ng dalawang mga elemento sa loob ng mga ito. Isa ay isang pointer, sa katunayan, bilang ko ang paggawa. Kaya bawat isa sa mga kahon Hindi isang cell lamang. Ngunit paano kung ang tuktok one-- ang isa sa ibaba pagpunta sa null, dahil walang Davenport pa lamang. Paano kung ang isa tuktok ay ilang mga espesyal na halaga? At ito ay magiging isang maliit na mahirap upang gumuhit ng mga ito sa ganitong laki. Ngunit ipagpalagay na ito ay lamang ng isang marka ng tsek. Lagyan ng check. D-A-V-E-N ay isang string sa istraktura ng data. 

Samantala, kung nagkaroon ako ng mas maraming espasyo dito, maaari kong gawin P-O-R-T, at maaari ko bang ilagay ang check sa node na may sulat T sa dulo. Kaya ito ay isang massively complex-naghahanap istraktura ng data. At ang aking sulat-kamay tiyak na hindi ito makatulong. Ngunit kung nais kong ipasok ang isang bagay iba, isaalang-alang kung ano ang gusto naming gawin. Kung gusto naming ilagay David sa, nais naming sundin ang parehong logic, D-A-V, ngunit ngayon Gusto ko ituro sa susunod na elemento hindi mula sa E, ngunit mula ako sa D. Kaya may pupuntahan maging higit pang mga node sa puno na ito. Kami ay pagpunta sa magkaroon ng higit tawag malloc. Ngunit hindi ko nais upang gumawa ng Kumpleto na ang gulo ng ang larawang ito. Kaya sa halip na tumingin sa isa hayaan na na-pre-formulated tulad nito sa hindi tuldok, tuldok, mga tuldok, ngunit dinaglat lamang array. Subalit ang bawat isa sa mga node sa puno hanggang dito kumakatawan sa parehong thing-- isang array Ray ng laki 26. 

O kung gusto namin na maging talagang maayos na ngayon, kung ano kung pangalan ng isang tao bilang isang kudlit, sabihin ipagpalagay na ang bawat node ay talagang tulad ng 27-i-index sa loob nito, hindi lang 26. Kaya ito ngayon ay magiging isang data istraktura na tinatawag na trie-- T-R-I-E. Ang isang trie, na parang kasaysayan ng isang matalino pangalan para sa isang puno na-optimize para sa pagbawi, na syempre, ay na-spell na may I-E kaya trie. Ngunit iyon ay ang kasaysayan ng trie. 

Kaya isang trie ay ang data na ito tulad ng tree- istraktura tulad ng isang pamilya puno na ganap na behaves tulad na. At dito ay isa lamang halimbawa ng isang ang maramihang mga pangalan ng ibang tao. Subalit ang tanong ngayon sa kamay ay kung ano ang Nakakuha kami ng nagpapakilala arguably ng isang mas kumplikadong istraktura ng data, at isa, nang tapat, na ginagamit ng maraming memory. 

Dahil kahit na, sa sandaling ito, lamang ako gamit D's pointer at A at V at Es at NS, Ako aksaya ng isang ano ba ng maraming memory. Ngunit kung saan gagastusin ko ang isa na mapagkukunan, Malamang kong huwag makakuha muli ng isa pa. Kaya kung ako gumagastos ng karagdagang espasyo, kung ano ang malamang na ang pag-asa? Na ako gumagasta ng mas mababa sa kung ano? Madla: Mas mababa oras. David MALAN: Time. Ngayon kung bakit maaaring maging iyon? Well, ano ang pagpapasok oras, sa mga tuntunin ng malaking O ngayon, ng isang pangalan tulad ng Daven o Davenport o David? Well, Daven ay limang mga hakbang. Maringal na aparador ay magiging siyam na mga hakbang, kaya magiging ilan pang mga hakbang. David ay magiging pati na rin ang limang hakbang na ito. Kaya mga mga kongkreto numero, ngunit tiyak na mayroong isang upper bound sa haba ng pangalan ng isang tao. At sa katunayan, sa problema hanay ng limang pagtutukoy, kami ay pagpunta sa ipanukala na ito ay isang bagay na na 40 ilang-kakaiba character. 

Realistically, walang isa ay isang walang hanggan mahaba ang pangalan, na kung saan ay upang sabihin na ang haba ng isang pangalan o ang haba ng isang string maaari naming May ilang mga estado ng istraktura ay arguably kung ano? Ito ay pare-pareho. Mag-right? Maaaring maging isang malaking pare-pareho tulad ng 40-isang bagay, ngunit ito ay pare-pareho. At ito ay walang dependency sa kung gaano karaming iba pang mga pangalan ay nasa ito istraktura ng data. Sa ibang salita, kung ako Nais na ngayon magpasok Colton o Gabriel o Rob o Zamyla o Alison o Belinda o anumang iba pang mga pangalan mula sa mga tauhan sa ang data na ito istraktura, ang oras tumatakbo ng pagpasok ng iba pang mga pangalan magiging sa lahat ng naapektuhan sa pamamagitan ng kung gaano karaming iba pang mga elemento ay sa istraktura ng data na? Hindi ito. Mag-right? Dahil epektibo aming ginagamit ito multi-layer hash talahanayan. At ang oras ng paggana ng anuman sa mga pagpapatakbong ito Nakadepende hindi sa bilang ng mga mga elemento na sa istraktura ng data o na huli ng pagpunta upang maging sa istraktura ng data, ngunit sa haba ng kung ano ang partikular na? 

Ang string pagiging Ipinasok, na ang gumawa ito asymptotically pare-pareho time-- malaking O na isa. At lantaran, lamang sa sa tunay na mundo, ito Nangangahulugan pagpasok ng pangalan Daven ni tumatagal tulad ng limang mga hakbang, o Davenport siyam mga hakbang, o David limang hakbang. Iyon ay medyo nagsulsi maliit na mga panahon ng pagtakbo. At, sa katunayan, iyon ay isang napaka mabuting bagay, lalo na kapag hindi ito nakasalalay sa kabuuang numero ng mga elemento doon. Kaya kung paano na maaari naming ipatupad ang uri ng istruktura sa code? Ito ay isang kaunti pa complex, ngunit pa rin ito ang isang application lamang ng pangunahing gusali bloke. Pupunta ako sa muling tukuyin amin node bilang mga sumusunod: bool tinatawag word-- at ito ma-tinatawag na kahit ano. Ngunit ang bool ay kumakatawan kung ano ang aking iginuhit bilang isang marka ng tsek. Oo. Ito ang katapusan ng isang string sa istraktura ng data. 

At, siyempre, ang node bituin doon ay nagre-refer sa mga bata. At, sa katunayan, i lamang isang pamilya tree, mo Gusto isaalang-alang ang mga node na nakikipag-hang-off ng ibaba ng ilang mga magulang elemento na maging bata. At upang ang mga bata ay pagpunta sa isang array ng 27, ang isang 27 lamang pagiging para sa kudlit. Kami ay pagpunta sa uri-uriin ng mga espesyal na kaso na iyon. Kaya maaaring magkaroon ka ng ilang mga pangalan na may kudlit. Siguro kahit gitling dapat pumunta doon, ngunit ikaw ay makita sa hanay p 5 lamang sa pangangalaga namin tungkol sa mga titik at kudlit. 

At pagkatapos ay kung paano gawin kinakatawan ang mismong istraktura ng data? Paano mo kumatawan sa root ng trie, kaya upang makipag-usap? Well, gusto lamang na may naka-link na listahan, mo Kailangan ng pointer sa unang elemento. Sa isang trie kailangan mo lang ng isang pointer sa root ng ito trie. At mula doon maaari mong hash ang iyong paraan down na mas malalim at mas malalim sa bawat iba pang mga node sa istraktura. Kaya lang sa lata kumakatawan namin na struct. 

Ngayon Meanwhile-- Oh, pinag-uusapan. 

Madla: Ano ang bool salita? 

David MALAN: Bool salita ay lamang ito C pagkakatawang-tao ng kung ano ang ko na inilarawan sa sa kahon na ito dito, kapag Nagsimula ako paghiwalayin ang bawat isa sa mga elemento ng array na sa dalawang piraso. Isa ay isang pointer sa susunod na node. Ang iba pang ay dapat na isang bagay tulad ng isang check box sabihin ninyo ang oo, may salita Daven na nagtatapos dito, dahil hindi namin nais, sa sandaling ito, Dave. 

Kahit na Dave ay magiging isang lehitimong salita, siya ay wala sa trie pa. At D ay hindi isang salita. At D-A ay hindi isang salita o ng isang pangalan. Kaya check mark Ipinapahiwatig lamang ng isang beses sa iyo maabot ang na node ay ang mga nakaraang path ng character tunay na isang string na iyong ipinasok. Kaya na ang lahat ng mga bool doon ay ginagawa para sa atin. 

Anumang iba pang mga katanungan sa pagsubok? Oo. 

Madla: Ano ang overlap? Paano kung mayroon kang Dave at Daven? David MALAN: Perpekto. Paano kung mayroon kang Dave at Daven? Kaya kung ipasok namin, sinasabi ng isang palayaw, para sa David-- Dave-- D-A-V-E? Ito ay talagang napaka-simple. Kaya namin lamang ng pagpunta sa tumagal ng apat na hakbang. D-A-V-E. At kung ano ang kailangan kong gagawin sa sandaling pindutin ko na pang-apat na node? Pagpunta lamang upang suriin. Kami ay naka-handa na upang. Tapos na. Apat na hakbang. Ang patuloy na oras asymptotically. At ngayon Isinaad namin na ang parehong Dave at Daven ay mga string sa istraktura. Kaya hindi problema. At pansinin kung paano ang presensya ng Daven ay hindi nakaabot gumawa ng anumang higit pang mga oras o mas mababa oras para sa Dave at vice versa. 

Kaya ano pa ang maaari naming gawin ngayon? Ginagamit namin ang talinghaga bago ng trays na kumakatawan sa isang bagay. Ngunit ito ay lumiliko out na ang isang stack ng mga trays ay talagang nagpapakilala ng isa pang abstract data type-- isang mas mataas na istraktura ng data sa antas ng na sa pagtatapos ng araw lamang tulad ng isang array o naka-link na listahan o isang bagay na mas pangmundo. Ngunit ito ay isang mas kawili-wiling haka-haka konsepto. Ang isang stack, tulad ng mga ito trays dito sa Mather, ay karaniwang tinatawag na that-- lamang ng stack. 

At sa ganitong uri ng istraktura ng data mayroon kang dalawang operations-- mayroon kang isa na tinatawag na push para sa pagdaragdag ng isang bagay sa stack, tulad ng paglalagay ng isa pang tray -back sa tuktok ng stack. At pagkatapos ay i-pop, na nangangahulugang gawin ang mga kataas-taasan-off ang tray. Ngunit kung ano ang key tungkol sa isang stack ay na ito ay nakuha ko ito kataka-taka katangian. Bilang dining hall staff rearranging ang trays para sa susunod na pagkain, kung ano ang magiging totoo tungkol sa kung paano mag-aaral makipag-ugnayan sa ang istraktura ng data? Madla: Ang mga ito ay pagpunta sa pop-off ang isa. David MALAN: Ang mga ito ay pagpunta sa -pop isa-off, sana sa itaas. Kung hindi man ito lamang uri ng nakababagod upang pumunta sa lahat ng mga paraan sa ibaba. Mag-right? Ang istraktura ng data ay hindi talaga payagan mong i-grab sa ibaba tray ng hindi bababa sa madali. Kaya ito hindi karaniwan ari-arian sa isang stack na ang huling item sa ay pagpunta sa maging unang isa out. At mga siyentipiko computer na tumawag ito LIFO-- magtatagal in, unang out. At talagang mayroon kawili-wiling mga application. Ito ay hindi kinakailangan ng kapansin-pansing bilang ilang mga iba, ngunit ito ay maaaring, sa katunayan, maging kapaki-pakinabang, at ito ay maaaring, sa katunayan, ay ipinatupad sa loob ng ilang iba't ibang mga paraan. 

Kaya isa, at aktwal na, sabihin sa akin ay hindi na sumisid sa iyon. Ni gawin ito sa halip Hayaan. Tingnan natin ang isang bagay na halos Hayaan parehong ideya, ngunit ito ay isang maliit na fairer. Mag-right? Kung ikaw ay isa sa mga fan lalaki o mga batang babae na talaga ang may gusto mga produkto ng Apple at woke up sa 03:00 sa line up sa ilang mga tindahan upang makuha ang pinakabagong iPhone, mo maaaring naka-queue up na katulad nito. 

Ngayon isang queue ay napaka sadyang may pangalang. Ito ay isang linya dahil mayroong ilang pagkamakatarungan dito. Mag-right? Ito ay uri ng sinipsip kung ikaw ay nakapunta roon muna sa Apple Store ngunit ikaw ay epektibo ang pinakamababa tray dahil ang mga empleyado ng Apple pagkatapos ay -pop ang huling taong nag aktwal na nakuha ko sa linya. Kaya stack at queues, kahit na sa pagtakbo ang mga ito ay uri ng same-- ito lamang ang koleksyon na ito ng mga mapagkukunan na pagpunta sa lumalaki at shrink-- doon ay ang pagiging makatarungan aspeto dito, hindi bababa sa tunay na mundo, kung saan ang mga pagpapatakbo ng ehersisyo sa iyo ay sa panimula naiiba. Isang stack-- isang queue rather-- ay sinabi na magkaroon ng dalawang pagpapatakbo: n queue at d queue. O kaya, maaari kang tumawag sa kanila anumang bilang ng mga bagay. Ngunit nais mo lamang upang makuha ang ang paniwala na ang isa ay pagdaragdag at ang isa ay sa huli ng pagbabawas. 

Ngayon sa ilalim ng hood, ang parehong ng stack at isang queue ma-ipinatupad paano? Hindi namin pumunta sa code ng ito dahil ang mas mataas na antas ideya ay isang uri ng higit pang mga halatang. Ibig kong sabihin, ano ang mga tao gawin? Kung ako ang unang tao sa Apple Mag-imbak at ito ay ang pinto, alam mo na, pupuntahan ko tumayo dito. At sa susunod na tao pagpunta sa tumayo dito. At sa susunod na tao pagpunta sa tumayo dito. Kaya kung ano ang istraktura ng data lends mismo sa isang queue? 

Madla: Ang isang queue. David MALAN: Well, isang queue. Oo naman. Ano pa? 

Madla: Ang isang naka-link na listahan. 

David MALAN: Isang naka-link ilista ang maaari mong ipatupad. At isang naka-link na listahan ay maganda dahil pagkatapos maaari itong lumalago nagkataon mahaba bilang kabaligtaran sa pagkakaroon ng ilang mga nakapirming numero ng mga tao sa store. Pero siguro isang nakapirming numero ng mga lugar ay lehitimo. Dahil kung ang mga ito ay may lamang tulad ng 20 iPhone sa unang araw, siguro Kailangan lang nila ng isang hanay ng mga laki 20 upang kumatawan na queue, na ay lamang na sabihin ngayon sa sandaling sinimulan namin ang pakikipag-usap tungkol sa mga mas mataas na mga problema sa antas ng, maaari mo itong ipatupad sa anumang bilang ng mga paraan. At doon ay marahil lamang ng pagpunta sa maging off ang isang kalakalan sa espasyo at oras o lamang sa iyong sariling pagiging kumplikado code. 

Ano ang tungkol sa isang stack? Well, isang stack, nasaksihan namin masyadong ay maaaring lamang ang mga trays. At maaari mong ipatupad ang isang array. Ngunit sa ilang mga punto kung gumagamit ka ng isang array, kung ano ang nangyayari sa mangyayari sa trays na sinusubukan mong ilagay down? Lahat ng karapatan. Ka lamang ng pagpunta sa magagawang pumunta kaya mataas. At sa tingin ko sa Mather ang mga ito talaga recessed sa na pagbubukas. Kaya nga, ito ay halos tulad ng Mather ay gumagamit ng isang hanay ng mga nakapirming laki, dahil maaari ka lamang magkasya kaya maraming mga trays sa pambungad na sa sa pader pababa sa ibaba tuhod ng mga tao. At sa gayon ay maaaring maging sinabi sa isang array, ngunit maaari kaming tiyak na ipatupad na higit pa sa pangkalahatan ay may isang naka-link na listahan. 

Well, kung ano ang tungkol sa isa pang istraktura ng data? Hayaan akong makuha ang isa sa iba pang mga visual na dito. Isang bagay na tulad ng kung paano tungkol sa isang ito dito? Kung ano ang maaaring maging kapaki-pakinabang na magkaroon ng hindi isang bagay bilang magarbong bilang isang trie, na nakita namin ay may mga napaka lapad nodes, ang bawat isa ay nasa isang array? Ngunit paano kung ang ginagawa namin ng isang bagay na higit pa lamang, tulad ng isang lumang puno ng pamilya ng paaralan, ang bawat isa sa kung saan ang mga node dito ay ang pag-iimbak lamang ang isang numero. Sa halip na isang pangalan o isang supling ay ang pag-iimbak lamang ng isang numero tulad nito. 

Well, ang magulong pag-uusap na ginagamit namin sa mga istraktura ng data ay ang parehong pagsubok at mga puno, kung saan ang isang trie, muli, ay isa na kung saan ang mga node ay array lamang, pa rin ang kung ano ang maaari kang gamitin mula sa mababang paaralan kapag gumawa ka ng isang pamilya tree-- dahon at root mula sa puno at mga bata ng mga magulang at kapatid noon. At maaari naming ipatupad ng isang puno, halimbawa, bilang simpleng bilang na ito. Puno A, kung ito bilang isang node, isa sa mga lupon na may isang numero, hindi ito pagpunta sa may isang pointer, ngunit dalawang. At sa sandaling idagdag mo isang pangalawang pointer, mo Maaari aktwal na ngayon ng pag-uuri ng dalawang-dimensional na data kaayusan sa memory. Karamihan tulad ng isang dalawang-dimensional array, maaari kang May uri ng dalawang-dimensional mga listahan ng mga ngunit naka-link na sundin ang isang pattern kung saan walang cycle. Ito ay tunay na isang puno na may isang lolo o lola paraan up dito at pagkatapos ay ang ilang mga magulang at mga anak at apo at apo sa apo. at iba pa. 

Ngunit kung ano ang talagang kapong baka tungkol sa masyadong, lamang upang mang-ulol sa iyo ng isang bit ng code, pagpapabalik mula sa Rekursiyon sandali bumalik, kung saan sumulat ka ng isang function na tawag mismo. Ito ay isang magandang pagkakataon upang ipatupad ang isang bagay tulad ng Rekursiyon, dahil isaalang-alang na ito. 

Ito ay isang tree. At ko pa ng kaunti anal sa kung paano Naglagay ako ng integer sa kalye. Kaya magkano upang ito ay may espesyal na name-- isang binary paghahanap tree. Ngayon nalaman namin ng binary maghanap, ngunit maaari kang gumagana pabalik mula pangalan bagay na ito? Ano ang pattern ng kung paano ko Ipinasok ang integer sa puno na ito? Ito ay hindi di-makatwirang. Mayroong ilang mga pattern. Oo. 

Madla: Mas Maliit mga nasa kaliwa. 

David MALAN: Oo. Mas maliit alin ang sa kaliwa. Mas malaki alin ang sa kanan. Ang ganitong na ang isang tunay na pahayag ay isang magulang ay mas malaki sa kaliwang anak nito, ngunit mas mababa sa kanang anak nito. At na lamang ang kahit na isang recursive pandiwang kahulugan dahil maaari kang mag-aplay na parehong logic sa bawat node at ito lamang bottoms out, isang batayang kaso kung gagawin kapag pinindot ninyo ang isa sa mga mga dahon, kaya upang magsalita, kung saan ang isang bakasyon ay may karagdagang mga bata. 

Ngayon kung paano maaari mong makita ang bilang 44? Gusto mong simulan sa root at sabihin, Hm. 55 Hindi 44 Kaya ang gusto ko ang umalis karapatan o ang gusto kong sasamang kaliwa? Well, malinaw naman gusto mong pumunta kaliwa. At kaya tulad lamang ang telepono Halimbawa aklat sa binary paghahanap higit pa sa pangkalahatan. Ngunit kami ay pagpapatupad ng mga ito ngayon ng kaunti pa sa pabagu-bagong kaysa sa maaaring payagan ang isang array. At sa katunayan, kung nais mong hanapin sa code, sa unang tingin sigurado. Mukhang ang maramihang mga linya. Ngunit ito ay maganda simple. Kung gusto mong ipatupad ang isang function tinatawag na paghahanap na layunin sa buhay ay upang maghanap para sa isang halaga tulad n, isang integer, at tapos ka nakapasa sa isang isa pointer-- isang pointer sa node ng mga ugat, sa halip, ng punong kahoy na mula sa kung saan maaari mong ma-access ang lahat ng iba pa, pansinin kung paano straightforwardly maaari mong ipatupad ang logic. Kung puno ay null, Malinaw na hindi ito doon. Hayaan ang mga bumalik na lamang false. Mag-right? Kung ipasa mo ito wala, walang mayroong. 

Iba Pa, kung n ay mas mababa sa puno arrow n-- ngayon arrow n, isipin ipinakilala namin ang sobrang sa madaling sabi ang iba pang mga araw, at na lamang ay nangangahulugan de-reference ang pointer at tumingin sa patlang na tinatawag n. Kaya ito ay nangangahulugan na pumunta doon at tumingin sa patlang na tinatawag n. Kaya kung n, ang halaga na iyong ibinigay, ay mas mababa kaysa sa halaga sa mga puno integer, kung saan mo gustong pumunta? Sa kaliwa. 

Kaya mapansin ang Rekursiyon. Ako returning-- hindi totoo. Hindi totoo. Ako bumabalik anuman ang sagot ay mula sa isang pagtawag sa sarili ko, pagpasa muli ng isang n, na paulit-ulit, ngunit kung ano ang bahagyang naiiba ngayon? Paano ako sa paggawa ng mga problema sa mas maliit? Ako pagpasa sa bilang ikalawang argument, hindi root ng tree, ngunit sa kaliwang bata sa kasong ito. Kaya ako pagpasa sa kaliwang bata. 

Samantala, kung n ay mas malaki kaysa ang node na kasalukuyan kong tinitingnan, Hahanapin ko ang kanang bahagi. Iba Pa, kung ang puno ay hindi null, at kung ang elemento hindi sa kaliwa at ito ay hindi sa kanan, kung ano ang kamangha-mangha ang kaso? Na tunay na nakita namin ang node sa -uusapan, at kaya bumalik kami totoo. 

Kaya nagbigay lamang scratched namin ang ibabaw ngayon ang ilan sa mga mga istraktura ng data. Sa set problema limang ikaw galugarin ang mga pang karagdagang, at makikita mo dapat ibigay ang iyong mga disenyo pagpili ng kung paano pumunta tungkol dito. Ano Gusto kong pagtibayin sa ay isang 30 segundong teaser lamang ng kung ano ang naghihintay sa susunod na linggo at higit pa. 

Bilang begin-- namin Sa kabutihang palad maaari kang think-- aming transition mabagal mula sa mundo ng C at mas mababang Mga detalye ng pagpapatupad antas, sa isang mundo kung saan maaari kaming magsagawa ng para sa Binigyan na ibang tao ay sa wakas nagpatupad ng mga data kaayusan para sa atin, at magsisimula kami upang maunawaan ang mga tunay na mundo ay nangangahulugan ng pagpapatupad mga programa ng web-based at mga website sa mas pangkalahatang paraan at din ang seguridad napaka implikasyon na hindi namin lamang nagsimula sa scratch sa ibabaw ng. Narito ang kung ano ang naghihintay sa amin sa araw na darating. 

[VIDEO pag-playback] 

-He Kasama ang isang mensahe, may protocol ang lahat ng sarili niyang. Dumating siya sa isang mundo ng malupit firewall, uncaring router, at mga panganib malayo mas masahol pa kaysa sa kamatayan. Siya ay mabilis. Siya ay malakas. Siya ay TCP / IP, at nakuha niya ang iyong address. "Warriors ng Net." [END VIDEO pag-playback] David MALAN: Paparating susunod na linggo. Makikita natin sa iyo pagkatapos. [VIDEO pag-playback] -And Ngayon, "Deep saloobin" sa pamamagitan ng Daven Farnham. Laging nagsisimula -David mga aralin sa, "Lahat ng karapatan." Bakit hindi, "Narito ang solusyon sa hanay problemang ito linggong " o "Kami ay nagbibigay sa lahat ng mga ka ng A?" [Tumatawa] [END VIDEO pag-playback]