David MALAN: Lahat ng karapatan. Maligayang pagbalik sa CS50. Ito ang simula ng linggo 8. At isipin ang problema na hanay 5 natapos na na may isang maliit na bit ng isang hamon. Kaya ipagpalagay na nakuhang muli ang lahat ng iyong pagtuturo Fellows at CA ng litrato sa file card.raw, ikaw ay karapat-dapat sa ngayon mahanap ang lahat ng mga tao, at isa masuwerteng nagwagi ay lumakad tahanan sa isa ng mga bagay na ito, ang mga hakbang paggalaw aparato na maaari mong gamitin para sa final mga proyekto, halimbawa. 

Na ito, sa bawat taon, ay humahantong sa ng kaunting creepiness. At kung ano ang kaya naisip ko na gusto kong gawin ay ibahagi sa iyo ang ilan sa mga tala na mayroon nawala na pabalik-balik sa ibabaw ang kawani ng listahan ng mga late. Halimbawa, lamang kagabi, quote magpanipi, mula sa isa sa mga tauhan mga miyembro, "ko lang ay nagkaroon ng isang mag-aaral magpatumba sa aking pinto na kumuha ng larawan sa akin. Stalkers, Sinasabi ko sa iyo. "Pagsisimula off medyo mapaglarawan at pagkatapos namin inilipat on sa, isang oras o kaya mamaya, "ako ay nagkaroon ng isang mag-aaral ng paghihintay para sa akin pagkatapos ng seksyon at siya ay nagkaroon ng lahat ng aming mga pangalan at larawan sa ilang mga sheet ng papel. "Lahat ng karapatan. Kaya isinaayos, ngunit hindi lahat na katakut-takot pa. 

Pagkatapos, "ako ay sa labas ng bayan sa pagtatapos ng linggo na ito, at kapag ang nakuha ko pabalik, nagkaroon ng isa sa ko bedroom. "[tawa] David MALAN: Susunod na quote mula sa isang kawani miyembro, "isang mag-aaral ang dumating sa aking bahay sa Somerville sa 4:00 ito umaga. "Susunod staff, "ang nakuha ko sa aking hotel na ito sa San Francisco at isang mag-aaral ay na naghihintay para sa sa akin sa lobby na may tatlong DSLRs. " Uri ng camera. "Hindi ako kahit na sa mga kawani na ito semestre, ngunit ang mag-aaral ng isang sinira sa aking bahay na ito umaga at naitala ang buong bagay gamit ang Google Glass. "At pagkatapos ay bilang wakas, "Hindi bababa sa 12 mga tao ay sabik naghihintay para sa akin kapag ang nakuha ko out ng aking Limo, at pagkatapos ay ako woke up. "Lahat ng karapatan. Kaya kabilang sa mga litrato, bilang maaari mong pagkuhang muli, ay kapwa ito dito, kung sino ka maaaring malaman bilang Milo Saging, nakatira may Lauren Carvalho, ang aming ulo pagtuturo Fellow. Milo, Milo, halika batang lalaki. Milo. Milo. Tututol ka, siya suot Google Glass, kaya ipapakita namin sa iyo ang lahat ng ito pagkatapos. Kaya ito ay Milo kung nais mong tumagal ng isang larawan na kasama niya Pagkatapos. Kung gusto mo upang tumingin out sa madla doon. OK. Iyan ay mahusay na footage. Well, Milo Saging. Oh, huwag gawin iyon. 

[Tawa] 

OK. Kaya ang salita pagkatapos ay sa kung ano ang namamalagi maaga, dahil bilang namin magsimula sa transition na ito, ngayong linggo partikular, mula sa C sa isang command line kapaligiran sa PHP at JavaScript at SQL at HTML at CSS sa isang web-based na kapaligiran, kami ay magiging equipping sa iyo ng lahat ng mga higit na kaalaman para sa potensyal na huling proyekto. Patungo sa layuning iyon, ang mga kurso ay may tradisyon ng mga may hawak na seminar kung saan ay tanghential sa mga paksa sa kurso. Sobra na may kaugnayan sa programming at upang app development at iba pa, ngunit hindi kinakailangang ginalugad sa pamamagitan ng sariling syllabus ang kurso ni. 

Kaya kung maaari kang maging interesado sa isa o higit pa sa mga seminar na ito taon, magparehistro sa cs50.net/seminar. Mayroong mas lumang seminar sa cs50.net/seminars. At sa roster kaya malayo para sa taong ito ang mga kamangha-manghang mga Web Apps na may Ruby sa Daang-bakal, na kung saan ay isang alternatibo wika na PHP. Computational lingguwistika. Panimula sa iOS, kung saan ay ang platform na ginamit para sa iPhone at iPad-develop. JavaScript para sa Web Apps, tatalakayin namin na, ngunit sa mga seminar na ito, pupunta ka mas detalyado. 

Tumalon Paggalaw, kaya ipapakita namin talagang makakuha ng ilang ng ating mga kaibigan mula sa tumalon Motion, ang kumpanya mismo, sumali sa amin. Bukas, sa katunayan, upang magbigay ng isang hands-on seminar, kung ng interes sa iyo. Meteor.js, isang alternatibong pamamaraan para gamit ang JavaScript ay hindi sa isang browser, ngunit sa isang server. Node.js, na higit na mas sa na ugat pati na rin. Sleek Android Design. Android pagiging isang napaka-tanyag na alternatibo sa iOS at Windows Phone at iba pang mga mobile platform. At Web Security Aktibo Defense. 

Kaya sa katunayan, kung nais mong upang makisali sa mga ito, ipaalam sa akin gumawa ng tala ng mga ito. Kami ay labis na nasisiyahan na sabihin na ang aming mga kaibigan sa tumalon Paggalaw, na isang startup - aparato na ito ay talagang lamang ay dumating out ng ilang mga buwan na nakalipas - si marikit donasyon 30 tulad na mga aparato sa klase para sa maraming mga mag-aaral, kung gusto mong hiramin ang hardware patungo sa katapusan ng semestre at gamitin ito para sa isang aktwal na huling proyekto. Sinusuportahan ng mga ito ay may bilang ng mga wika. Wala sa mga ito C, wala sa kanila ang PHP, kaya Napagtanto ng isa o higit pa sa mga seminar na ito maaaring patunayan ng interes. At lahat ng mga ito ay kumuha sa mga kaganapan na hindi ka makapag na dumalo sa tao. Ang iskedyul ay inihayag sa pamamagitan ng mag-email bilang pagkaisahin namin kuwarto. 

At bilang wakas, kung pumunta ka sa projects.cs.50.net, ito ay isang website panatilihin namin ang bawat taon na naming mag-anyaya kakailanganin ng mga tao mula sa komunidad, faculty, kagawaran, kawani, at pareho sa isang labas ng CS50 sa ipanukala ang mga ideya sa proyekto. Mga bagay ng interes sa mga mag-aaral. Mga bagay ng interes sa mga kagawaran. Kaya huwag i-on doon kung ikaw ay struggling sa kawalan ng katiyakan bilang sa kung ano ang iyong Gusto mo mismo i-pagharap sa isang bagay. 

Kaya huling beses na ipinakilala namin ang isang arguably mas kumplikadong istraktura ng data kaysa sa kami ay nakita sa nakalipas na linggo. Gusto naming ginagamit ang array medyo maligaya bilang isang kapaki-pakinabang kung simplistic data istraktura. Pagkatapos ay ipinakilala namin ang mga ito, na siyempre ay naka-link listahan. At kung ano ay isa sa mga motivations para sa nagpapakilala ang data na kaayusan? Oo? Ano iyan? 

Madla: Dynamic na laki. 

David MALAN: Dynamic na laki. Kaya samantalang sa array, mayroon kang upang alam nito laki nang maaga kapag magtalaga ng mga ito sa iyo. Sa listahan na naka-link, hindi mo pag mayroon na malaman na. Maaari mo lamang malloc, o sa mas pangkalahatang paraan, magtalaga ng isang karagdagang node, kaya na magsalita, anumang oras mo nais upang ipasok higit pang data. At node ay walang paunang natukoy na kahulugan. Ito ay lamang ng isang generic term na naglalarawan ang ilang mga uri ng lalagyan na hindi namin paggamit sa aming mga istraktura ng data upang mag-imbak ilang mga item ng interes, na sa ganitong sakaling mangyari na maging integer. 

Ngunit mayroong palaging isang tradeoff. Kaya makuha namin dynamic na sukat ng data istraktura, ngunit kung ano ang presyo namin magbayad? Ano ang downside ng naka-link na mga listahan? Oo? 

Madla: Nangangailangan ng higit pang memory. 

David MALAN: Ito ay nangangailangan ng higit pa memorya, nang eksakto kung paano? 

Madla: [hindi marinig]. 

David MALAN: Mismong. Kaya ngayon namin ang pointer pagkuha up dagdag na memorya na kami dati ay hindi kailangan, dahil ang kalamangan ng isang array, siyempre, ay na ang lahat ng bagay ay magkadikit, likod upang i-back sa likod, na Binibigyan ka ng random access. Dahil sa pamamagitan lamang ng paggamit ng square bracket pagtatanda, o mas technically pointer pang-aritmetika, napaka-simple pa rito, maaari mong ma-access ang anumang mga mga elemento sa pare-pareho ang panahon. At sa katunayan, iyon ang uri ng hinting sa ibang presyo na kami nagbabayad sa isang naka-link na listahan. 

Ano ang mangyayari sa mga oras ng paggana ng isang bagay tulad ng Search, kung gusto kong mahanap ang ilang mga halaga at loob ng isang naka-link na listahan? Ano ang aking tumatakbo oras maging? Big O ng n. Kung ito ay pinagsunod-sunod sa? Paano kung ang data ng istraktura ay pinagsunod-sunod? Maaari ko bang gawin mas mahusay kaysa sa malaki O ng n para maghanap? Hindi, dahil sa ang pinakamasama kaso ay maaaring ito napaka mahusay na pinagsunod-sunod, ngunit ang bilang naghahanap ka ng mga maaaring maging malaki. Maaaring maging ang numero 100, na maaaring mangyari upang maging lahat ang paraan sa dulo. At dahil maaari ka lamang ma-access ang isang naka-link na sa listahan na ito sa pamamagitan ng pagpapatupad paraan ng kanyang unang node, ikaw ay pa rin ang uri ng out ka sana. Mayroon kang upang tawirin ang buong bagay mula sa unang tatagal upang matagpuan ang na malaking halaga tulad ng 100. O upang matukoy kung ito ay hindi kahit doon. 

Kaya hindi namin maaaring gawin kung ano ang algorithm sa isang data istraktura na ganito ang hitsura? Hindi namin maaaring gawin binary paghahanap, dahil binary paghahanap kinakailangan na nagkaroon kami random access. Maaari lang namin tumalon mula sa lokasyon lokasyon nang hindi na kinakailangang sundin mga tinapay crumbs sa anyo ng lahat ng mga payo. 

Ngayon, kung paano namin ay ipatupad ito? Well, kung pumunta kami sa screen dito, kung maaari naming mabilis reimplement ang data na ito istraktura - ang aking sulat-kamay ay hindi lahat na mahusay dito, ngunit susubukan naming. Kaya typedef struct, at kung ano ang ginawa ko nais na itawag sa bagay up dito? Node. Kaya makikita ako makakakuha ng sa amin makapagsimula. At ngayon, ano ang mga kailangan upang maging sa loob ng ang istraktura ng data para sa kanyang sarili na naka-link na listahan? Gaano karaming mga patlang? 

Kaya dalawa. Ang isa ay medyo madali. Kaya int n. At maaari kaming tawagan n kahit ano gusto namin, ngunit ito ay kailangang maging isang int kung hindi kami pagpapatupad ng isang naka-link na listahan para sa ints. At ngayon kung ano ang ipinapakita ng ikalawang patlang na kailangang maging? Struct node *. Kaya kung gagawin ko struct node *, at pagkatapos ay ako maaaring tumawag ito din kahit anong gusto ko, ngunit para lamang maging malinaw Tatawag ako susunod na ito, bilang namin nai-paggawa. At pagkatapos ay kukunin ko isasara ang aking kulot tirante. 

At ngayon, bilang huling oras, Ko bang ilagay ang node down na dito. Ngunit kung ako deklarasyon na ito ay bilang isang node, bakit ako mag-abala sa pagiging kaya masyadong masalita dito sa deklarasyon struct node * susunod, bilang kabaligtaran upang lamang node * susunod? Oo? 

Madla: [hindi marinig]. 

David MALAN: Mismong. Mismong. Dahil C talagang magdadala sa iyo literal at nakikita lamang ang kahulugan ng node paraan down na dito, hindi mo magagawa sumangguni sa mga ito up dito. Kaya mayroon kaming ang ganitong uri ng preemptive pagpapahayag dito, na kung saan ay tinatanggap na mas maligoy. Struct node, na nangangahulugang maaari naming ngayon itong ma-access sa loob ng data ng istraktura. 

At bilang isang tabi, dahil ito ay nagiging isang kaunti pa subjective ngayon, bituin ang maaaring technically pumunta dito, maaari itong pumunta dito, maaari itong kahit na pumunta sa gitna. Aming ampon, sa estilo gabay para sa ang kurso, ang convention ng paglalagay ng ang star sa tabi mismo ng data uri, na sa kasong ito, magiging struct node. Ngunit Napagtanto ng maraming mga aklat-aralin at online na mga sanggunian, maaari mo talaga makita ito sa kabilang panig. Ngunit lamang mapagtanto na ang parehong kalooban talaga gumana at dapat mo lamang maging pare-pareho. 

Ayos lang. Kaya na noon ay aming deklarasyon ng struct node. Ngunit pagkatapos namin sinimulan ang paggawa nang higit pa sopistikadong mga bagay. Halimbawa, napagpasyahan naming ipakilala isang bagay tulad ng isang hash table. Kaya dito ay isang hash talahanayan ng n laki, na-index mula sa 0 sa tuktok na kaliwa sa n minus 1 sa ibabang kaliwa. Ito ay maaaring maging isang hash mesa para sa kahit ano. Ngunit ano ang mga uri ng mga bagay ay namin makipag-usap tungkol sa paggamit ng hash talahanayan para sa? Ang pag-iimbak ano? 

Mga Pangalan. Maaari naming gawin ang mga pangalan tulad ng ginawa namin huling oras. At talagang, maaari kang mag-imbak ng kahit ano. At kami na makita ito muli sa PHP at sa JavaScript. Ang isang hash talahanayan ay isang magaling na uri ng Swiss Army kutsilyo na nagbibigay-daan sa iyo upang mag-imbak medyo magkano ang kahit anong gusto mo sa loob ng ito sa pamamagitan ng uugnay ng mga susi na may halaga. Keys na may halaga. 

Ngayon sa ito simpleng kaso, ang aming key lang ang mga numero. Kami ay pagpapatupad ng hash talahanayan bilang isang array. At kaya ang mga key ay 0, 1, 2, at iba pa. At kaya namin, bilang mga tao, nagpasya huling linggo na alam mo kung ano, kung hindi kami pagpunta sa mga pangalan ng tindahan, sabihin lamang mang, ngunit medyo makatwirang, ipinapalagay na Alice, isang Isang pangalan, lamang ay mai-index sa 0. At si Bob, ang isang B pangalan, ay mai-index sa 1, at iba pa. Kaya nagkaroon kami ng mapping sa pagitan ng input, na kung saan ay mga string, at ang hash lokasyon, na mga numero. 

Kaya proseso na ay karaniwang kilala bilang isang hash, at maaari mong tunay ipatupad ito sa code. Kung Nais kong ipatupad ang isang hash na gumagana nang eksakto kung ano ang aming na inilarawan mula sa huling oras, maaari ko magpahayag ng isang function na tumatagal, bilang input halimbawa - at sabihin gawin ito sa ito screen sa paglipas dito. Kung Nais kong ipatupad ng hash function, maaari ko bang sabihin isang bagay na katulad nito. 

Ito ay pagpunta sa bumalik sa isang int. Ito ay pagpunta sa ay tinatawag na hash, at ito ay pagpunta sa tanggapin bilang isang argument isang string, o maaari naming maging mas maayos na ngayon, at sabihin pansamantalang trabaho *, magpapadala kami tumawag ito s. At pagkatapos ay ang lahat ng mga function na ito ay may sa gawin, sa huli, ay bumalik sa isang int. Ngayon, kung paano ito gumagana na kapangyarihan hindi kaya maging malinaw. Pupunta ako sa ipatupad ito nang walang anumang bumubuo ng mga error ng pagsuri sa ngayon. Lamang ako ng pagpunta sa sabihin nang walang taros, bumalik ano ay sa mga bracket 0, minus, sabihin nating, kabisera Isang tuldok-kuwit. 

Lahat-lahat nasira. Ito ay hindi perpekto dahil isa, paano kung s ay walang bisa? Hindi mahusay na mga bagay ay pagpunta sa mangyayari. Two, kung ano ang unang titik sa mga ito pangalan ay hindi isang malaking titik? Na hindi pagpunta sa i out na rin ang alinman. Maaaring maging isang maliit na mga titik o hindi ang isang sulat sa lahat. Kaya lubos na kuwarto para sa pagpapabuti dito, ngunit ito ay ang pangunahing ideya. 

Ano kami ng inilarawan noong nakaraang linggo pasalita bilang lamang ang proseso ng paggawa ng mga mapa Alice sa 0 at Bob sa 1 maaaring ipinahayag tiyak mas formulaically bilang isang C gumana dito. Tinatawag na muli hash, tumatagal ng isang string bilang input, at pagkatapos ay sa paanuman ang isang bagay may na input upang makabuo ng isang output. Hindi hindi tulad ng aming itim na kahon paglalarawan matagal na ginawa namin. Hindi ko alam kung paano maaaring ito ay nagtatrabaho sa ilalim ng hood. 

Para sa mga problema sa set 6, isa sa mga hamon ay para sa iyo na magpasya kung ano ang ay ang iyong hash maging? Ano kaya ang nangyari sa maging sa loob ng itim na kahon, at siguro, makikita ito maging isang kaunti pa kaysa sa mga kagiliw-giliw na ito, at Talagang mas madaling kapitan ng sakit sa error pagsusuri kaysa sa partikular na pagpapatupad. 

Ngunit ang problema ay maaaring lumabas dahil, tama? Kung mayroon kaming data istraktura tulad ng mga ito isa, ano ang isa sa mga problema maaari mong patakbuhin sa paglipas ng panahon bilang mong isingit higit pa at higit pang mga pangalan sa hash talahanayan? Makakakuha ka ng banggaan, tama? Paano kung mayroon kang Alice at Aaron, dalawang tao ang mga pangalan nangyari upang magsimula sa A? Na begs ang tanong, kung saan ka ilagay ang pangalawang katulad Isang pangalan? 

Well, maaari mong naively lamang ilagay ito kung saan si Bob ay kabilang, ngunit pagkatapos ay Bob uri ng screwed kung sinusubukan mong isingit ang kanyang pangalan at susunod walang room para sa kanya. Kaya maaari mong ilagay Bob kung saan Charlie ay, at maaari mong isipin na ito masyadong mabilis devolving sa isang bit ng isang gulo. Isang bagay na linear sa dulo, kung saan ka lamang magkaroon upang hanapin ang buong bagay naghahanap ng Alice o Bob o Aaron o Charlie. 

Kaya sa halip iminungkahi namin, sa halip na lamang linearly probing para sa open space at plopping ang mga pangalan doon, namin Ipinanukala isang may interes na diskarte. Ang isang hash talahanayan ipinatupad pa rin gamit ang isang array ng mga indeks, ngunit ang data uri ng mga indeks ng ngayon ay mga payo. Mungkahi ukol sa kung ano? Payo sa naka-link na mga listahan. 

Dahil na isipin ang isang naka-link na ang listahan talaga lang ang pointer sa isang node, at na node ay may susunod na patlang, at na node May susunod na patlang, at iba pa. Kaya maaari ka na ngayong mag-isip ng array na ito sa sa kaliwang bahagi ng isang hash talahanayan bilang humahantong sa isang naka-link na listahan. Ang bentahe ng na kung kumuha ka ng isang banggaan sa pagitan ng Alice at Aaron, ano ang iyong magagawa sa mga pangalawang nasabing tao? Ikaw lamang maglakip sa kanyang mga pagtatapos, o kahit na sa simula ng mga naka-link na listahan. 

At talagang, sabihin lamang sa pamamagitan ng pansit na para lang isang segundo. Saan masulit ang kahulugan? Kung ako isingit Alice at siya ay nagtatapos up sa sa unang lokasyon, pagkatapos ay subukan kong isingit Aaron ang pangalan, at mayroong malinaw naman isang banggaan, dapat ko bang ilagay sa kanya sa simula ng mga naka-link na listahan? Iyon na sa unang lokasyon, o sa dulo? 

Madla: [hindi marinig]. 

David MALAN: OK. Narinig ko simula. Bakit sa simula? 

Madla: [hindi marinig]. 

David MALAN: OK. Ito ay alphabetical, kaya na magaling. Iyon ay isang mahusay na ari-arian. Ito ay i-save sa akin ang ilang oras potensyal. Hindi ito ay magbibigay-daan sa akin gawin binary paghahanap, ngunit ko maaaring hindi bababa sa magagawang masira out ng isang loop kung Napag-alaman kong, well, ako paraan nakaraan ay Aaron ay magiging sa pinagsunod-sunod naka-link na listahan. Hindi ko kailangang mag-aaksaya ng aking oras hinahanap ang lahat ng mga paraan sa dulo. Kaya na makatwirang. Bakit iba baka gusto mong isingit ang nagbabanggaan na pangalan sa simula ng listahan? Ano iyan? 

Madla: [hindi marinig]. 

David MALAN: Maaaring magtagal ng mahabang panahon upang makakuha ng sa dulo ng listahan. At sa katunayan, mas mahaba at mas mahaba. Ang higit pang mga pangalan sa iyo na ipasok magsimula sa A, ang mas mahaba na chain ay pagpunta upang makakuha ng. Ang mas mahaba na naka-link listahan ay pagpunta upang makakuha ng. Kaya't kung ikaw talaga lamang pag-aaksaya ng iyong oras. Marahil, ikaw ay mas mahusay na off pagpapanatili pare-pareho ang pagpapasok ng oras, malaki O ng 1, sa pamamagitan ng palaging paglalagay ang nagbabanggaan sa pangalan simula ng naka-link na listahan, at hindi nag-aalala bilang magkano tungkol sa pag-uuri. 

Ano ang pinakamahusay na sagot? Hindi ito malinaw. Ito uri ng depende sa kung ano ang pamamahagi ay, kung ano ang pattern ay ng pangalan mo ay pagpasok. Ito ay hindi kinakailangan isang halata sagot. Ngunit dito sa, muli, ay isang disenyo pagkakataon. 

Kaya namin pagkatapos ay tumingin sa bagay na ito, na talaga ang iba pang mga malaking pagkakataon para p-set 6. At napagtanto, kung hindi mo pa nagagawa, Zamyla dives sa pareho sa mga ito, hash mga talahanayan at sinusubukang, nang mas detalyado. At ang video na walkthrough ay naka-embed sa p-set spec. Ito ay isang trie - T-R-I-E. At kung ano ang tungkol sa mga kawili-wiling ito ay na tumatakbo ang oras ng paghahanap para sa isang pangalan, tulad ng Maxwell huling beses, ay malaki O ng kung ano? Ano iyan? 

Audience: Ang bilang ng mga titik. 

David MALAN: Bilang ng mga titik. Narinig ko ang dalawang bagay. Bilang ng mga titik at pare-pareho ang panahon. Kaya sabihin pumunta sa na una. Ang bilang ng mga titik. Well, ang data na istraktura, isipin ang, ay ng isang puno, isang family tree, sa bawat isa sa na node ay binubuo ng array. At ang mga array ay pointer sa ibang tulad ng mga node, o iba pang ganoong array sa tree. 

Kaya kung gusto naming pagkatapos malaman kung Maxwell ay nasa dito, maaari ba akong mag- sa unang array, sa pinakatuktok ng sa puno, ang tinaguriang ugat, tuktok ng ang trie, at pagkatapos ay sundin ang m pointer, pagkatapos ng isang pointer, pagkatapos ay x, w, e, l, l. At pagkatapos ay kapag nakita ko ang ilang mga espesyal na simbolo, naitala dito bilang isang tatsulok. Sa code na makikita mo naming imungkahi na sa iyo ipinatupad bilang isang bool, sinasabi lang yes o hindi, ang isang salita tumitigil dito. 

Well, isang beses na namin nawala sa M-A-X-W-E-L-L, nararamdaman tulad ng pitong, siguro walo kung pumunta kami ng isa nakalipas na ito, walong hakbang na ito upang makahanap ng Maxwell. O kaya sabihin call ito K. Ngunit isipin ang huling oras, ako Nagtalo na kung mayroong realistically isang maximum na haba sa isang salita, tulad ng 40-ilang-kakaiba character, isang maximum na haba nagpapahiwatig isang pare-pareho ang halaga. Kaya talaga, oo, ito ay technically malaki O ng 8 o 7, o talagang malaki O ng K. Ngunit kung mayroong isang may wakas cap sa kung ano ang K maaaring maging, ito ay isang constant. At kaya malaki O ng 1 sa ang pagtatapos ng araw. 

Hindi sa tunay na mundo. Kapag hindi mo talagang simulan ang panonood ang iyong orasan bilang tumatakbo ang iyong mga program. Talagang Ito ay pagpunta sa maging isang bit mas mabagal kaysa sa tunay na pare-pareho oras na may isang hakbang. Ito ay pagpunta sa maging pitong o walong mga hakbang, ngunit pa rin na magkano, magkano ang mas mahusay na kaysa sa isang algorithm tulad ng malaki ng O n na Depende sa laki ng kung ano ang sa istraktura ng data. 

Pansinin ng bentahe dito ay maaari naming isingit isang milyong higit pang mga pangalan na ito sa istraktura ng data, ngunit kung gaano karaming mga karagdagang hakbang ito ay pagpunta sa tumagal sa amin upang mahanap ang Maxwell sa kasong iyon? Wala. Siya ay hindi maaapektuhan. At sa petsa, palagay ko ay hindi nasaksihan namin isang halimbawa ng data ng istraktura o isang algorithm na noon ay ganap na maaapektuhan ng panlabas tulad ng pag-uugali na. Ngunit ito ay hindi maaaring maging kahanga-hangang. Ito ay hindi maaaring ang tanging solusyon para sa mga p-set 

At ito ay hindi. Ito ay hindi nangangahulugang ang data istraktura dapat mong i-gravitate, dahil tulad ng hash talahanayan, tradeoff. Ano ang presyo na binabayaran mo dito? Memory. Ibig kong sabihin, ito ay isang mabangis halaga ng memorya. At hindi pa ninyo makita ito dito dahil ang may-akda ng larawan na ito malinaw naman pinutol lahat ng mga array, at hindi namin nakikita ng maraming mga A at B at C at T at Y ay at Z sa mga array. Ngunit ang mga ito doon. 

Ang bawat isa sa ang mga nodes ay isang buong array ng ilang mga 26 o higit pang mga bytes, ang bawat isa ng na kung saan ay kumakatawan sa isang liham. 27 sa aming kaso, upang maaari naming suportahan apostrophes sa hanay problema. Kaya ang data na istraktura talaga, talagang siksik at malawak na. At mag-isa na maaaring magtapos up pagbagal bagay down, o hindi bababa sa ay nagkakahalaga ng sa iyo ng isang maraming mas maraming espasyo. Ngunit muli, maaari naming gumuhit mga paghahambing dito. 

Isipin ang isang habang pabalik, namin nakakamit magkano mas kapana-panabik na tumatakbo sa oras ng pag-uuri kapag ginagamit namin ang pagsasama-uri, ngunit ang mga presyo kami binayaran upang makamit n log n para sa pagsasama sort kailangan na gastusin namin higit pang mga mapagkukunan kung ano? Higit pang mga puwang. Kinakailangan namin ng isang pangalawang array sa kopyahin ang mga tao sa, tulad ng ginawa namin dito sa entablado. Kaya muli, walang malinaw na nagwagi, ngunit lamang subjective disenyo pagpapasya na isasagawa. 

Ayos lang. Kaya kung paano tungkol dito? Sinuman makilala kung aling mga D-Hall? OK. Kaya tatlo sa amin gawin. Mather House. Kaya ito ay para sa Mather sa mga dining. Magpapadala ako pumusta lahat sa dining hall mayroon stack ng trays na katulad nito. At ito ay talagang kinatawan ng isang bagay na namin malinaw naman nakita pa. Namin na tinatawag na ito ng isang literal na stack. At ang stack, sa mga tuntunin ng iyong computer memory, ay kung saan ilalagay ang data habang ang mga function ay ina tinatawag. 

Halimbawa, kung ano ang mga uri ng mga bagay pumunta sa stack na may pagsasaalang-alang sa memory layout namin tinalakay sa nakaraang linggo? Ano iyan? 

Audience: Ang mga tawag sa mga function. 

David MALAN: Sorry. 

Audience: Ang mga tawag sa mga function. 

David MALAN: Ang mga tawag sa pag-andar, ngunit partikular, kung ano ang nasa loob ng bawat isa sa mga frame? Anong mga uri ng mga bagay-bagay? Oo. Kaya lokal na variable. Anumang oras kinailangan naming ang ilang mga lokal na imbakan, tulad ng isang argument, o int ko, o int Temp, o anumang ang lokal variable ay, kami nakapunta paglalagay na sa stack. At tinatawag namin itong isang stack dahil ng layering na ideya. Lang ang uri ng pagtutugma up sa katotohanan, ang konsepto hinggil doon. 

Ngunit ito lumiliko out na stack ng lata din ay nakita bilang isang istraktura ng data, isang alternatibo sa isang array, isang alternatibong sa isang naka-link na listahan. Isang bagay na conceptually mas kawili-wiling na maaari pa ring maging ipinatupad gumagamit ng alinman sa mga bagay, ngunit ito ay isang iba't ibang mga uri ng data istraktura pagsuporta, talaga, lamang ng dalawang mga operasyon. Ngunit maaari mong idagdag sa may interes mga tampok kaysa sa mga ito. Ngunit ang mga ito ay ang mga pangunahing kaalaman - itulak at magpa-pop. 

At ang mga ideya na may isang stack ay na kung ako mayroon dito, mayroon o walang Annenberg pag-alam, isang tray mula sa susunod na pinto kasama ang numero 9 sa ito. Kaya lang sa isang int. At gusto ko upang itulak ito papunta sa data istraktura, na kung saan ay kasalukuyang walang laman. Isaalang-alang na ito sa ilalim ng stack. Gusto ko itulak ang numerong 9 papunta sa isalansan, at ngayon ito doon. 

Ngunit ang mga kagiliw-giliw na bagay tungkol sa isang stack ay kung ako ngayon ay nais upang itulak sa ilang ibang mga halaga, tulad ng 17, at itulak ako ito papunta sa stack, pupuntahan ko gawin ang tanging bagay na madaling maunawaan, lamang ako pupunta upang ilagay ito ng tama kung saan kami mga kawani na tao ay hilig upang ilagay ito, sa tuktok. Ngunit kung ano ang kawili-wili ngayon ay, paano ako makakakuha ng sa 9? Alam mo yun, gagawin ko hindi na walang ilang mga pagsisikap. 

Kaya kung ano ang tungkol sa mga kawili-wiling isang stack ay na sa pamamagitan ng disenyo, ito ay isang istraktura ng LIFO data. Hangal na paraan ng naglalarawan huling in, out muna. Kaya ang huling numero sa sa oras na ito ay 17. Kaya kapag gusto kong mag-pop ng isang bagay off ng stack, maaari itong lamang maging 17. Kaya mayroong isang ipinag-uutos na pagkakasunud-sunod ng pagpapatakbo dito, kung saan ang huling item sa may upang maging ang unang isa out. Samakatuwid ang acronym, LIFO. 

Kaya bakit ito ay maaaring maging kapaki-pakinabang? Sigurado kanilang konteksto kung saan ikaw ay Gusto ng data kaayusan tulad ng ito? Well, tiyak na ito ay naging kapaki-pakinabang sa loob ng isang computer. Kaya mga operating system malinaw na gamitin ito uri ng data na istraktura para sa stack. Makikita rin namin makikita ang parehong ideya pagdating sa mga pahina ng web. Kaya ito linggo at mga susunod na linggo at higit pa, at bilang simulan mo ang pagpapatupad ng web mga pahina sa isang wika na tinatawag na HTML, maaari mong talaga gumamit ng data kaayusan tulad ng ito upang matukoy kung ang pahina tama ang format. Dahil makikita namin makita ang lahat ng mga web page sundin isang uri ng hierarchy, isang indentation iyon ay, sa pagtatapos ng araw, maging isang puno istraktura sa ilalim ng hood. Kaya higit pa sa na sa loob lamang ng kaunti. 

Ngunit para sa ngayon, sabihin ipanukala para sa isang sandali, paano kami maaaring pumunta tungkol sa na kumakatawan sa kung ano ang isang stack ay? Hayaan akong magpanukala na aming ipapatupad isang stack gamit ang code na tulad nito. Kaya isang stack ay pagpunta sa may loob nito dalawang bagay, isang array, na tinatawag na trays, lamang na maging pare-pareho sa demo. At ang bawat isa sa mga item sa array na ay magiging isang uri ng int. At kapasidad ay siguro ano? Dahil hindi ko na nakasulat sa buong kahulugan dito. 

Ito ay marahil ang pinakamalaking laki ng array. At marahil ito ay ipinahayag bilang isang matalim tukuyin sa tuktok ng file, ang ilang mga uri ng pare-pareho ang bilang ipinahiwatig sa pamamagitan ng galos lamang ang capitalization. Kaya sa isang lugar kapasidad ay tinukoy bilang ang maximum na posibleng laki. Samantala, sa loob ng mga istraktura ng data Kilala bilang isang stack doon kalooban maging isang integer lamang kilala lamang bilang laki. 

Kaya kung ako ay upang kumatawan ito ngayon pictorially, sabihin ipagpalagay na ito buong itim na kahon ay kumakatawan sa aking stack. Sa loob nito ay dalawang variable. Kaya ako ng pagpunta sa gumuhit ang unang isa bilang laki. At ang pangalawang isa ako pupunta upang gumuhit ng isang array. 

Ngunit lamang upang panatilihin ang mga bagay na nasa ayos, normal Gusto ko gumuhit ng isang array tulad ng ito, ngunit ito uri ng magaling kung namin ay tumutugma sa katotohanan, o tumugma sa mental modelo. Kaya ipaalam sa akin sa halip gumuhit ng array patayo, na kung saan ay, muli, pag-awit artist. Hindi talaga mahalaga kung ano ito ay sa ilalim ng hood. At kami na sabihin, sa pamamagitan ng default, kapasidad ay magiging tatlo. Kaya ito ang magiging lokasyon ng 0, ito Magiging lokasyon 1, ito Magiging lokasyon 2. 

Kung ako suhol na may bola stress, gagawin isang tao na gusto na dumating up at magpatakbo ng mga pumanhik dito para sa sandali lamang? OK, nakakita ng iyong mga kamay muna. Halika sa up. Ayos lang. Kaya naniniwala akong ito ay Steven. Halika sa up. Ayos lang. 

Ngunit ipagpalagay na namin ngayon ang rewind sa paunang kalagayan ng mundo kung saan ako Na ipinahayag lamang ng isang stack, at ito ay pagpunta sa maging kapasidad ng tatlo. Ngunit laki ay hindi pa natutukoy. Trays ay hindi pa natutukoy. Kaya isang pares ng mga katanungan muna. At hayaan mo akong bigyan ka ng mic sa gayon maaari mong saluhan mas aktibo sa ito. 

Kaya kung ano ay nasa loob ng laki sa panahon na ito sa oras kung lahat gumawa ako ay ipinahayag ng isang stack na may isang linya ng code? 

Steven: Hindi magkano. 

David MALAN: OK, hindi magkano. Huwag namin alam kung ano ang nasa loob ng laki, huwag naming malaman kung ano ang nasa loob ng array na ito dito? 

Steven: lamang random code, tama? Lang - 

David MALAN: Oo, pupuntahan ko tumawag itong code, ngunit random - 

Steven: Mga bagay. 

David MALAN: Mga bagay tulad ng random 

Steven: Bits. 

David MALAN: Bits, tama? Kaya basura mga halaga, tama? Kaya permutations ng 0 at 1 ni. Mga Labi ng nakaraang usages ng memorya na ito. At hindi namin talaga alam kung ano ang mga halaga ay, kaya kami ay karaniwang gumuhit ng mga ito bilang tanong marks. 

Kaya ang unang bagay na kami siguro pagpunta sa nais na gawin dito - at hayaan mo akong bigyan ang patlang na ito sa loob ng ng may isang pangalan - trays. Ano ang dapat naming siguro initialize laki sa kung gusto naming simulan ang paggamit ito stack? 

Steven: Tray ay sub 3. 

David MALAN: Kaya, OK. Upang maging malinaw, kapasidad ay ipinahayag sa ibang dako bilang tatlong. At na kung ano na nagamit ko upang maglaan ng array. Laki ay pagpunta sa sumangguni sa kung gaano karaming trays kasalukuyang nasa stack. 

Steven: Zero. 

David MALAN: Kaya ito ay kailangang maging zero. Kaya't sige, at sa sinumang daliri, gumuhit ng zero ang laki. Ayos lang. Kaya ngayon, kung ano ang nasa loob ng mga ito dito, hindi namin alam. Ang mga ito ay talagang lamang ang mga halaga ng basura. Kaya maaari naming gumuhit ng mga marka tanong, ngunit sabihin board panatilihin ang malinis para sa ngayon dahil hindi mahalaga kung ano ang doon. Hindi namin kailangang mag-initialize ang array sa anumang bagay, dahil kung alam namin na ang laki ng stack ay zero, mahusay, namin Hindi dapat na tumitingin sa anumang bagay sa ito array pa rin sa ang puntong ito sa panahon. 

Kaya ngayon ipagpalagay na ako itulak ang number 9 papunta sa stack. Paano dapat naming i-update ang data ng istraktura sa loob ng ito itim na kahon? Anong mga halaga ang kailangang baguhin? 

Steven: Sa loob ng - ang laki? 

David MALAN: OK. Laki dapat bang maging ano? 

Steven: Laki ay magiging isa. 

David MALAN: OK. Kaya laki dapat bang maging isa. Kaya maaari mong gawin ito sa isang paraan pares. Hayaan akong magbigay sa iyo, ngayon ay ang iyong daliri ay isang pambura. Ayos lang. Pagkatapos ngayon ang iyong daliri ay isang brush. Ayos lang. At ngayon kung ano pa ang may upang baguhin, malinaw naman, sa istraktura ng data? 

Steven: Kami ay pagpunta mula sa ilalim ng hanggang sa 9. 

David MALAN: 9. OK, Magandang. Kaya pa rin ay hindi mahalaga kung ano ang sa lokasyon ng isa o dalawang dahil hindi nila mga halaga ng basura, ngunit hindi namin dapat mag-abala Naghahanap doon dahil ang sukat ng na nagsasabi sa amin na ang unang lamang ang elemento ay talagang lehitimo. Kaya ngayon ako itulak 17 papunta sa listahan. Ano ang mangyayari sa ang larawang ito? 

Steven: Kaya laki ay pagpunta sa pumunta sa dalawa. 

David MALAN: OK. Ikaw pambura - oops. Ikaw ay isang pambura. 

Steven: Pambura. 

David MALAN: Ikaw ang brush. 

Steven: Brush. 

David MALAN: OK. At ano pa? 

Steven: At pagkatapos namin - 

David MALAN: Aming hunhon 17. 

Steven: dumikit namin 17 sa tuktok, kaya - 

David MALAN: OK, mabuti. 

Steven: - drop ito pababa. 

David MALAN: Lahat ng karapatan. Nagiging madali. Hindi ako pagpunta upang makatulong sa iyo sa oras na ito. Itulak 22. 

Steven: Tapos na. Mawalan ng pambura. Ako magiging isang brush. At pagkatapos ay ako ay paglalagay 22. 

David MALAN: 22. Magaling. Kaya isa pang beses. Ngayon ako pagpunta sa itulak papunta sa stack 26. 

Steven: Ooh. Oh sus. Ikaw talaga nahuli ako off bantay. 

MALAN David: Ikaw ay hindi makita ito darating? 

Steven: Hindi ko nakita ito darating. Ma muli naming paunang kapasidad? 

David MALAN: Iyon ay isang mahusay na tanong. Kaya namin ang uri ng pininturahan ating sarili sa isang sulok dito. Mayroong talaga ay walang mabuting out para sa Steven dahil kami inilalaan array na ito statically, kaya na magsalita, sa loob ng mga istraktura ng data. At kami ng lubos na hard code ito upang maging sukat ng tatlo. Kaya hindi talaga namin maaaring reallocate ito. 

Maaaring namin kung kami nagpunta bumalik sa, namin redefined trays na maging isang pointer na namin pagkatapos ay gamitin ang malloc sa kamay memory sa. Dahil kung namin ang nakuha mula sa memory ang kimpal sa pamamagitan ng malloc, namin pagkatapos ma magbakante ito. Ngunit bago pagbabakante ito, maaari naming reallocate ng mas malaking tipak ng memory, i-update ang pointer, at iba pa. Ngunit para sa ngayon, talaga ito ang pinakamahusay na maaari naming gawin. Itulak at magpa-pop ay siguro pagpunta upang magkaroon ng upang magsenyas ng ilang mga error. 

Kaya halimbawa, ang aming pagpapatupad ng push maaaring magbalik ng bool na dati ibinalik na totoo, totoo, totoo. Ngunit ang ika-apat na oras, ito ay pagpunta sa may upang bumalik false, halimbawa. Ayos lang. Tunay na magaling. Binabati kita. Kumita ka ng stress ang iyong mga bola ngayon. 

[Palakpakan] 

Steven: Salamat sa iyo. 

David MALAN: Salamat sa iyo. OK, sa gayon ito ay anyong hindi magkano ng isang hakbang pasulong, tama? Inilalarawan namin ang data na ito istraktura. Naging nakakahimok, tama? Operating system ito nais. Tila ang web ay maaaring gamitin ng mga ito, at iba pang mga application pa rin. Ngunit kung ano ang isang bobo limitasyon na kami i-back sa isang uri ng dalawang linggo limitasyon kung saan kami naayos array laki. 

Kaya may mga talaga ng dalawang paraan maaari naming malutas ito. Maaari naming dynamic na magtalaga ng mga array, hindi sa pamamagitan ng matapang na coding ito bilang nag ako tapos dito, ngunit sa halip ay muling deklarasyon ito, para lamang maging malinaw, bilang isang bagay na katulad nito. Int * trays, hindi nagpapasya sa isang kapasidad pa. Ngunit kapag ako magpahayag ng stack sa ibang lugar sa aking code, maaari ko pagkatapos tawagan malloc, makuha ang address ng isang tipak ng memorya, at maaari ba akong magtalaga na address sa trays. 

At pagkatapos, dahil ito lamang ay isang tipak ng memorya, maaari ba akong patuloy na gamitin ang square bracket notation sa karaniwang paraan. Dahil muli, mayroong uri ng mga ito functional katumbas ng array at chunks ng memorya na dumating pabalik mula sa malloc. Maaari naming ituring bilang isa sa iba pang mga gamit ang pointer aritmetika o square bracket pagtatanda. Kaya iyon ang isa na diskarte. 

Ngunit paano pa ang maaari naming ipatupad ang parehong istraktura ng data, potensyal na? I-right? Pakiramdam ko ay tulad lang namin malutas ito problema tulad ng isang linggo na ang nakakalipas. Ano ang solusyon sa problemang ito na Steven bumangga sa? Kaya naka-link na mga listahan, i-right. 

Kung ang problema ay na kami ay pagpipinta ating sarili sa isang sulok sa pamamagitan ng paglaan ng maaga masyadong maliit na memory namin pagkatapos ay sa paanuman upang harapin ang, mahusay, bakit hindi iwasan lamang na maglalabas ng sama-sama? Bakit hindi lamang magpahayag ng trays na maging isang pointer sa isang node samakatuwid, isang naka-link na listahan, at pagkatapos lamang magtalaga ng bagong node tuwing Steven na kailangan upang umangkop sa isang numero sa ang istraktura ng data. 

Kaya ang larawan ay magkakaroon upang baguhin. Hindi Ito ay pagpunta sa maging bilang malinis at bilang simple lamang bilang isang array ng tatlong ints. Ngayon ito ay pagpunta sa maging isang pointer sa isang struct, at struct na pagpunta sa magkaroon ng isang int at isang susunod na pointer. Ito ay pagpunta sa humantong sa pamamagitan ng na ang pointer sa isa pang tulad struct sa isa pang tulad struct. Kaya larawan ang gagawin talaga makakuha ng isang bit Messier. At gusto namin ang mga arrow tinali lahat ng bagay magkasama. 

Ngunit iyon fine, kanan, dahil nasaksihan namin kung paano gawin ito. At sa sandaling makakuha ka komportable pagpapatupad ng isang bagay tulad ng isang naka-link na listahan, na kung saan kailangan mong gawin kapag mo pumili upang ipatupad ang isang hash talahanayan na may hiwalay chaining para p-set 6, maaari mong gamitin ito bilang isang bloke ng gusali, o isang sahog, o sa scratch magsalita, isang pamamaraan, isang bagay na inilagay mo, mo nilikha ang iyong sariling mga puzzle piraso na maaari mong gamitin muli pagkatapos. Kaya tradeoffs, ngunit potensyal na solusyon na aktwal na nasaksihan namin dati. 

Kaya medyo madalas, makikita mo ito sa bawat taon o dalawang kapag Apple release ng isang bagong bagay, at ang lahat ng mga nakatutuwang mga tao line up sa labas ng Apple mag-imbak upang bumili ng kanilang mga nasa gilid mag-upgrade sa hardware. Sinasabi ko ito, ito ay OK, dahil Ako ay isa sa mga taong iyon. Kaya kung anong uri ng data na istraktura Maaaring kumatawan ang katotohanan? 

Well, sabihin call ito ng isang pila, isang linya. Kaya gusto British tumawag ito isang karaniwang pila pa rin, sa gayon ito ay isang magaling na pangalan. At ang dalawang mga operasyon na ang isang queue dapat suportahan namin tumawag sa isang enqueue operasyon at isang dequeue pagpapatakbo, na kung saan ay katulad sa espiritu upang itulak at magpa-pop. Ito ay lamang uri ng iba't ibang mga sa convention, ano kami mga pagtawag. Ngunit sa enqueue isang bagay ay nangangahulugan na upang magdagdag ng o ipasok ito sa istraktura ng data. Upang dequeue nangangahulugan na alisin ito. Ngunit habang ang isang stack ay isang LIFO data istraktura, isang pila ay isang unang in, out muna ang istraktura ng data. 

Kung ikaw ang unang tao sa linya, ay ikaw ang unang tao upang makakuha ng out ng mga linya at bilhin ang iyong bagong device. Isipin kung paano sira ang mga taong ito ay magiging kung Apple sa halip ay gumamit ng isang stack, para sa Halimbawa, upang ipatupad ang pagpili up ng iyong bagong laruan. Kaya queues kabuluhan, walang duda, at maaari naming isipin ang lahat ng uri ng application, siguro, para sa queues, lalo na kapag gusto mong pagkamakatarungan. Kaya kung paano namin ipatupad ang mga bilang isang istraktura ng data? 

Well, ipinapanukala ko na maaari naming kailangang gawin ito sa ganitong paraan. Kaya pupuntahan ko ay mayroon na ngayong mga numero. Kaya naming panatilihin itong simple at hindi kinakailangan na makipag-usap sa mga tuntunin ng trays. Lamang ang mga numero na ang mga tao ng nakuha. Kapasidad ay pagpunta sa, muli, ayusin ang kabuuang bilang ng mga tao na maaaring nasa ang linyang ito, bilang tatlo o anumang iba pang mga halaga. 

Ngunit ipanukala ko na kailangan kong i-track ang hindi lamang ng laki ng queue, kung gaano karaming mga bagay ang sa loob nito. Kaya't ang sukat ng kasalukuyang laki, kapasidad ay ang maximum na laki. Lang ulit, mga katawagan sa pamamagitan ng convention. Bakit ko kailangan ng isang karagdagang int loob ng isang pila upang masubaybayan kung sino ang nasa harapan ng linya? Bakit kailangan kong gawin iyon sa kasong ito? 

Well, kung paano ay ang larawang ito pagpunta sa palitan? Maaari ko bang gamitin muli marahil pinaka- ng larawan na ito. Hayaan akong sige at burahin ang kung ano ang meron dito. Susubukan naming bigyan ito ng isang bahagyang ibang pangalan up dito. Natin mapupuksa ang mga 17, sabihin mapupuksa ng 9, sabihin mapupuksa ng 3. At sabihin magdagdag ng isa pang bagay. Ipanukala ko na kailangan kong subaybayan harap ng listahan, na kung saan ay lamang pagpunta sa maging isang int pati na rin. At kami ay pagpunta sa panatilihin itong simple. Walang naka-link na listahan para sa ngayon. 

Susubukan naming umamin na kami ng pagpunta sa mauntog up laban sa limitasyong ito. Ngunit kung ano ang gusto kong makita mangyari oras na ito? Kaya ipagpalagay ko sige at ang unang tao ay lumalabas sa linya, at ito ang numero 9. Kami ng mga bola stress. Maaari ko bang nakawin, sabihin nating, dalawa o tatlong mga tao? Ang isa, dalawa, tatlo? Halika sa up. Kanan mula sa harap, dahil magsasagawa kami ng isang mabilis na ito. 

Ang bawat isa sa iyo ngayon ay pagpunta sa maging isang fan boy sa linya sa Apple. Ikaw ay hindi pagtanggap ng Apple hardware sa dulo ng ito bagaman. Ayos lang. Kaya ikaw ay number 9, ikaw ay number 17, number 22. Ito ang mga arbitrary na numero, tulad ng mga ID ng mag-aaral o watnat. At sa loob lamang ng isang sandali, sabihin simulan upang magsimulang magdagdag ng mga bagay-bagay. At kukunin ko na tumakbo sa board dito oras na ito. 

Kaya sa kasong ito, ko na nasimulan front ang upang maging - Ko talagang hindi talagang mahalaga kung ano ang front ay, dahil ang laki ay zero. Kaya ito ay maaaring pati na rin lamang maging isang tandang pananong. Ito ang lahat ng mga marka tanong. Kaya ngayon sisimulan naming upang aktwal na makita ang ilang mga mga tao lining up sa tindahan. 

Kaya kung number 9, ikaw ang unang isa doon sa 5:00, sige at pumila, o ang gabi bago. OK. Kaya ngayon ay 9 dito. Kaya 9 ay nasa harap ng mga listahan. Kaya pupuntahan ko sige at i-update ang laki ng mga ito ang kasalukuyang data istraktura upang hindi maging 0 ngayon, ngunit upang maging 1. Pupunta ako sa 9 na ilagay sa harapan ng listahan. Hayaan akong sige at magpalipat-lipat ng screen upang maaari naming makita ang nakaraan sa amin dito. 

At ngayon kung ano ang gusto ko upang ilagay sa harap? Pupunta ako sa subaybayan na ang harapan ng pila sa ngayon ay nasa 0 lokasyon. Dahil kung ano ang susunod na pagpunta sa mangyayari? Well, ipagpalagay na ngayon ko enqueue 17 pati na rin. Kaya Hop sa linya doon. At muli, ang uri ng mga pintuan ng tindahan ay magiging dito. Kaya ngayon Idinagdag ko na 17. At kahit na ang mga guys ay hinaharangan ang screen, na OK lang, dahil maaari naming makita ito up dito. Sorry. 

Madla: Maaari naming ilipat - 

David MALAN: Hindi, iyan ay OK. Ito ay malaking up doon. Kaya 17 ay ngayon sa loob ng queue. Kailangan ko upang i-update na field ngayon bagaman? OK, siguradong laki. At kung paano tungkol sa front? OK, hindi. Front ay hindi dapat magbago, dahil hindi katulad ng isang stack, kami nais upang mapanatili ang pagiging patas. Kaya kung 9 ay dumating sa unang, nais naming 9 upang maging una sa labas ng linya at sa mga tindahan. 

Sa katunayan, sabihin makita na. Bago namin isingit 22, sabihin sige at dequeue 9. Ano ang inyong pangalan muli? 

Madla: Jake. 

David MALAN: Jake ay pagpunta na dequeued ngayon. Kaya mo makakuha upang maglakad papunta sa tindahan. At magpanggap na mga tindahan ay banda roon. Kaya ngayon ano ang mga kailangan - dit-dit-dit! Ano ang kailangang mangyari ngayon? Disenyo desisyon. Kaya hindi isang masamang likas na hilig, ngunit - ano ang iyong pangalan muli? 

Madla: David. 

David MALAN: David. Kaya kung ano ang David gawin? Siya ay sinusubukan upang ayusin ng maayos ang data istraktura at ilipat mula sa kanyang lokasyon sa dating lokasyon ni Jake. At iyon ang masarap na kung hindi kami payag tanggapin na bilang isang pagpapatupad detalye. Ngunit una, sabihin i-update ang data istraktura bago gawin namin iyon. Dahil hindi ako paggusto ang ideya ng lahat ang mga tao paglilipat sa linyang ito. 

Ito ay hindi sang-ayon kung David ang ipinapakita ito sa isang hakbang, ngunit muli, sa tingin pabalik sa kapag mayroon kaming walong boluntaryo sa stage at ginawa namin tulad ng pagpapasok -uri-uriin, kung saan nagkaroon kami upang magsimulang paglipat ng lahat ng tao sa paligid. Nakakuha na mahal, tama? Na gumagawa sa akin sumukot tungkol sa malaking O ng n, malaki O ng n nakalapat muli. Hindi ito tulad ng pakiramdam isang mainam na kalalabasan. 

Kaya sabihin lamang i-update ito. Kaya ang laki ng queue Hindi na 2. Ito ay ngayon lamang 1. Ngunit maaari ko na ngayong i-update ang isang bagay Hindi ko i-update ang bago, ang harapan ng listahan. Maaari ko lang sabihin, ang lokasyon na 1? Kaya ngayon kami ay may basura halaga dito, basura halaga dito, at David sa gitna ng basura ito. Ngunit ang data ng istraktura ay pa rin buo. 

At sa katunayan, hindi ko kahit na kailangan upang baguhin ang dating numero Jake ni 9, dahil sino nagmamalasakit. Mayroon akong sapat na impormasyon ngayon sa laki na alam ko may marami sa isang tao sa ito queue. At alam ko na ang taong iyon ay nasa lokasyon 1, hindi 0. Hindi ako pagbibilang. Kaya 1 pati na rin. Kaya ang data ng istraktura pa rin ang OK. 

Well, kung ano ang susunod na mangyayari? Sabihin enqueue - ano ang pangalan mo? 

Madla: Callen. 

David MALAN: Callen. Sabihin enqueue isang Callen, at 22 ay nasa queue. Kaya ngayon kung ano ay may upang baguhin dito? Front ay hindi papunta sa baguhin, nang walang alinlangan. Laki ay pagpunta upang baguhin upang maging 2 muli. At 22 ay nagtatapos up dito, 9 ay naroroon pa rin, ngunit ito ay isang epektibong basura halaga ngayon. Ito ay lamang ng isang labi ng Jake nakaraan. 

Kaya ngayon kung ano ang mangyayari kung Dequeue kong David? Isang huling operasyon, dequeue David. Maaari naming shift, ngunit ipanukala ko sabihin gawin bilang maliit na trabaho hangga't maaari. Ngayon ang aking data istraktura napupunta i-back sa laki 2-1. Ngunit sa harap ng pila ngayon nagiging 2. Hindi ko kailangang baguhin ang mga bilang na ito sa ngayon, dahil hindi nila lamang ang mga halaga ng basura. 

Ngunit ngayon kung ano ang mangyayari? Ipagpalagay ko enqueue sarili ko, 26? Pakiramdam ko ay tulad nabibilang ako sa ibabaw dito. Kaya ako ina-enqueued. Kaya ako uri ng nabibilang dito. At kahit na hindi mo pa masyadong Pinahahalagahan ito biswal sa entablado, dahil kami ay may maraming kuwarto, ang dapat kong Hindi ma-nakatayo dito, bakit? 

Madla: Naubusan ka na ng hanggahan. 

David MALAN: Kanan. Ako out sa hanggahan. Ko na ang na-index na higit sa hanggahan ng array na ito. Ako talaga ay dapat nasa isa sa mga tatlong posibleng mga lokasyon. Ngayon, nasaan ang pinaka-natural na pumunta? Ipanukala ko naming magagamit sa isang linggo sa isang kahanga-hangang gawa. Ang mga mod operator, porsyento. Dahil technically ako nakatayo sa 3 lokasyon, ngunit kong gawin 3 mod kapasidad, kaya 3, isang porsiyento sign, 3 - kapasidad ang 3. Ano iyan? Ano ang natitira kapag hatiin mo ang 3 sa pamamagitan ng 3? 0. 

Kaya na naglalagay sa akin ay Jake noon, na kung saan ay tunay mabuti. Kaya ngayon ang pagpapatupad ng mga bagay na ito ang nangyayari sa maging isang bit ng isang sakit ng ulo. Ito ay talagang lamang ng isang linya ng sakit ng ulo, ng code. Ngunit hindi bababa sa ngayon ay may basura halaga dito, ngunit mayroong dalawang lehitimong ints dito. At inaangkin ko na ngayon na namin tapos kung ano mismo ang kailangan namin upang gawin ito hangga't naming baguhin kung ano Jake ni halaga ay upang maging 26. 

Kami ngayon ay may sapat na impormasyon pa rin upang mapanatili ang integridad ng data na ito istraktura. Kami pa rin ang uri ng out ka sana kapag kami nais upang ipasok apat o higit pang kabuuang mga elemento, ngunit maaari ko ng hindi bababa sa gawing kaakit-akit mahusay na paggamit ng mga ito pare-pareho oras, sa katunayan. Hindi ko kailangang mag-alala tungkol sa paglilipat lahat ng tao, pati na ni David ang pagkahilig noon. 

Ang anumang mga katanungan sa stack, o ito queue? 

Madla: ba ang dahilan kung bakit kailangan mo laki kaya alam mo kung saan upang magkaroon ng isang tao? 

David MALAN: Mismong. Kailangan kong malaman ang laki ng array dahil kailangan kong malaman kung paano mismo marami sa mga halagang ito ay lehitimo, at sa gayon ay maaari ko bang mahanap kung saan upang ilagay sa susunod na tao. Mismong. Ang laki ay - talaga, hindi kami i-update ito pa. Nagdagdag ako sa sarili ko 26. Ang laki na ngayon, hindi 1, pero 2. Kaya ngayon ito sa katunayan ay nakakatulong sa akin mahanap ang ulo ng listahan, na kung saan ay hindi 0, hindi 1, ngunit ay 2. Ang harap ng listahan talaga ang numero 22. Dahil siya ay dumating sa unang, kaya dapat siya pahihintulutang papunta sa tindahan bago sa akin, kahit na biswal na ako nakatayo mas malapit sa mga tindahan. 

Ang lahat ng mga karapatan? Ang isang ikot ng papuri para sa mga guys at ipapaalam namin sa out ang mga ito doon. 

[Palakpakan] 

David MALAN: kaya kong ipaalam panatilihin mo ang tray. Maaari naming makita kung ano ang mangyayari kung gusto mo, ngunit marahil hindi. Ayos lang. Kaya kung ano ngayon ay na mag-iwan sa amin? Well, hayaan mo akong magpanukala na mayroong isang ilang iba pang data ng mga istraktura ng dati namin magsimulang magdagdag sa aming tool kit na kalooban talaga lubos na, medyo may-katuturang mga bilang namin sumisid sa web stuff. Aling muli, ay may ilang mga uri ng koneksyon sa mga puno sa anyo ng isang bagay na tinatawag na DOM, dokumento bagay na modelo. Ngunit kailangan naming makita ang higit pa sa na bago ang haba. 

Hayaan akong magpanukala definitionally na namin tumawag puno ngayon kung ano ang maaaring kilala bilang higit pa sa isang family tree, kung saan ka May ilang mga ninuno sa Roots ng puno. Ang isang makaama o isang matriarch sa pinakatuktok ng puno. Kapag wala ang kanilang mga asawa, sa kasong ito. Ngunit kami ay mayroon na ngayong kung ano ang makikita namin tumawag mga anak, na mga nodes na mag-hang off sa kaliwa anak o sa kanan anak, mga arrow bilang itinatanghal dito. 

Sa ibang salita, sa isang puno istraktura ng data sa computer, puno ng isang may zero o higit pang mga node. Kung ito ay may hindi bababa sa isang node, na tinatawag na ugat ng. Ito ay ang mga bagay na biswal na gumuhit kami sa tuktok. At node na, tulad ng anumang iba pang mga node, maaari mayroon zero, isa, o dalawa, o tatlong, o gayunpaman maraming mga bata ang data istraktura ay sumusuporta sa. Sa kasong ito, ang mga ugat, pag-iimbak ng mga halaga ng isa, ay may dalawang mga bata, 2 at 3, kaya namin sa pangkalahatan ay tumawag 2 sa kaliwa bata at 3 sa kanan anak. 

At pagkatapos ay kapag makuha namin down sa 5, 6, at 7, 6 na maaaring tawagin sa gitna anak. Kung mayroon kang apat na mga anak, ito ay makakakuha ng nakalilito. Kaya naming ihinto ang paggamit ng ganoong uri shortcut ng pasalita. Ngunit ito ay talagang lamang ng isang family tree. At ang mga dahon dito ay ang mga nodes na mayroon kanilang mga sarili walang mga bata. Hang-off ang mga ito sa ilalim ng tree. 

Kaya kung paano namin ipatupad ang isang puno na Mayroon lamang dalawang bata maximally? Susubukan naming tumawag ito ng isang binary tree. Bi muli ibig sabihin dalawa, sa ganitong kaso, tulad ng sa binary. At sa gayon maaari itong magkaroon zero, isa, o dalawang bata maximally. 

Kukunin ko ipanukala na namin ipapatupad ang node para na istraktura sa isang int n, at pagkatapos ay dalawang payo, isa na tinatawag na pakaliwa, isa na tinatawag na karapatan. Ngunit iyon lamang ang maganda arbitrary balarila. At kung ano ang maganda ngayon, lalo na kung uri ng struggled conceptually may recursion, o naisip na ito ay hindi talaga isang solusyon sa anumang bagay, lalo na kung magagawa mong Naubusan ng memorya. Ngayon na pinag-uusapan natin ang tungkol sa data mga istraktura at mga algorithm na payagan sa amin sa pagtawid at manipulahin ang mga ito, lumiliko out na recursion ay bumalik sa isang magkano ang mas nakakahimok kung hindi magandang paraan. 

Kaya ito ipanukala ko ay ang pagpapatupad ng isang Search function. Given dalawang input - kaya sa tingin ng mga ito bilang isang itim na kahon. Given dalawang input, n, isang int, at isang pointer sa isang puno, isang pointer sa isang node, o talagang ugat ng isang puno, ako paghabol na ang function na ito ay maaaring bumalik tama o mali, na ang halaga n ay nasa loob ng tree. 

Ano ang nasa loob ng mga ito itim na kahon? Well, apat na sanga. Ang unang lamang ang sumusuri. Kung ang puno ay null, bumalik lang hindi totoo. Kung mayroong walang node, mayroong n walang, mayroong walang numero, bumalik lang mali. Kung bagaman, n, ang halaga na iyong hinahanap para sa, ay mas mababa sa puno n arrow, at para lamang maging malinaw, kung ano ang ibig sabihin kapag Isulat ko ang tree at pagkatapos ay ang arrow pagtatanda, n? Mismong. Ito ay nangangahulugan na dereference pointer tinatawag tree. Pumunta doon, at pagkatapos ay makakuha sa loob ng na node at makakuha nito field na tinatawag n. At pagkatapos ay ihambing ang aktwal n na noon ay pumasa sa Search laban dito. 

Kaya kung n ay mas mababa, ang halaga n sa tree node mismo, na rin, ano ang nilalaman na ibig sabihin nito? Iyon ay nangangahulugang wala sa unang tingin. I-right? Katulad ng kapag mayroon kang isang hanay ng mga mga halaga, maaari mong mag-apply binary maghanap bilang isang paraan ng hatiin at lupigin. Ngunit ano ang palagay ay kailangan namin upang magsagawa ng para sa binary paghahanap upang gumana sa lahat sa phone book at mas maaga mga halimbawa? 

Paano na pinagsunod-sunod. Kaya sabihin pinuhin ang kahulugan ng puno dito ay hindi upang maging lamang ng isang puno, na kung saan maaari magkaroon ng anumang bilang ng mga bata. Hindi lamang isang binary tree, kung saan maaari mayroon kang 0, 1, 2 o maximally. Ngunit bilang isang binary puno ng paghahanap, o BST, na kung saan ay lamang ng isang magarbong paraan ng sinasabi ng binary puno tulad na ang bawat node ni kaliwa bata, kung kasalukuyan, ay mas mababa kaysa sa node. At karapatan bata bawat node ni, kung kasalukuyan, ay mas malaki kaysa sa node mismo. 

Kaya sa ibang salita, kung ikaw ay upang gumuhit sa puno out, ang lahat ng mga numero ay maingat na balanse ang ganito upang kung mayroon kang 55 bilang root, 33 maaaring pumunta sa kaliwa nito dahil ito ay mas mababa kaysa sa 55. 77 maaaring pumunta sa kanan nito dahil ito ay mas malaki sa 55. Ngunit ngayon mapansin, ang parehong kahulugan, ito ay isang recursive kahulugan sa salita, May mag-aplay para sa 33. 33 ni kaliwa bata ay dapat mas mababa ito, at kanan anak ni 33, 44, dapat mas malaki kaysa ito. 

Kaya ito ay isang binary puno ng paghahanap, at Ipanukala ko, gamit ang isang kaunting recursion, maaari naming ngayon mahanap n. Kaya kung n ay mas mababa sa halaga n na kasalukuyang node, pupuntahan ko pumunta Magpatuloy at magtikin, kaya na magsalita, at lamang bumalik ano ang sagot ay sa naghahanap ng n sa kaliwa anak ni puno. Pansinin muli, function na ito lamang Inaasahan ng isang node bituin, isang pointer sa isang node. Kaya tiyak lamang ako maaaring magawa puno kaliwang arrow, na kung saan ay hahantong sa akin sa isa pang node. Ngunit ano ang node na? 

Well, ayon sa pahayag na ito, kaliwa lamang ang pointer, kaya na lamang ibig sabihin ako ng pagpasa sa pag-andar ng paghahanap ng ibang pointer, lalo ang isa na kumakatawan puno ang aking kaliwang anak. Kaya sa kasong ito, ang pointer sa 33, kung ito ay ang aming sample input Samantala, kung n ay mas mataas kaysa sa halaga n sa kasalukuyang node sa tree, pagkatapos ay ako pagpunta sa sige at magtikin sa iba pang mga direksyon at lang sabihin, gawin ko hindi malalaman kung ang halagang ito n ay sa tree, pero alam ko kung ito ay, ito ay ang aking karapatan branch, kaya na magsalita. Kaya ipaalam sa akin recursively tawagan kayo maghanap, pagdaan ng isang n ulit, pero ang pagpasa sa isang pointer sa aking kanan anak. 

Sa ibang salita, kung ako sa kasalukuyan sa 55 at Naghahanap ako para sa 99, alam ko na 99 ay mas malaki sa 55, kaya lang tulad ko torus ang phone book linggo ang nakalipas at hindi na namin nagpunta ang mga karapatan, katulad tayo pagpunta sa pumunta dito mismo. At hindi ko alam kung ito ay sa aking mga karapatan bata, at ito ay hindi, 77 ay doon, ngunit Alam ko ito sa na direksyon. Kaya tumawag ako sa paghahanap sa aking kanan anak, 77, at hayaan ang paghahanap figure out mula sa kung may 99 na ito sa di-makatwirang Halimbawa ay talagang doon. 

Iba Pa, ano ang huling kaso? Kung ang puno ay walang bisa ay isa kaso. Kung n ay mas mababa kaysa sa kasalukuyang node ni halaga ay isa pang kaso. Kung n ay mas mataas kaysa sa kasalukuyang node na halaga ay isang third kaso. Ano ang pang-apat at huling kaso? Sa tingin ko kami ay out ng mga kaso, tama? Ito dapat na n ay nasa kasalukuyang node na ako sa. 

Kaya kung ako naghahanap ng mga 55 sa puntong ito sa mga kuwento, na sangay ng puno ay magbabalik totoo. Kaya kung ano ang kawili-wiling dito ay ang pagpapalit namin talaga, hindi tulad ng mga linggo nakaraan, kami uri magkaroon ng dalawang mga kaso base. At hindi nila kailangang mag- maging lahat sa tuktok. Ang tuktok ay isang base ng kaso dahil kung ang puno ay null, mayroong walang kinalaman. Bumalik lang ng hard-code halaga ng huwad. 

Ang ilalim ng sangay ay isang uri ng mga default, kung saan kung kami naka-check para sa null, kami naka-check kung ito ay kailangang maging umalis, ngunit hindi ito dapat maging, na namin naka-check kung ito ay kailangang maging karapatan, ngunit ito hindi dapat, malinaw na ito ay dapat na karapatan kung nasaan kami. Iyan ay isang batayang case. Kaya mayroong dalawang mga kaso recursive sandwiched doon sa gitna. Ngunit maaaring isinulat ko ito sa anumang pagkakasunud-sunod. Ko lang naisip ito uri ng nadama natural sa unang suriin para sa isang posibleng mga error, pagkatapos suriin pakaliwa, pagkatapos ay i-check ang karapatan, pagkatapos ay ipinapalagay na ikaw ay sa node talaga ang hinahanap mo. 

Kaya bakit ito ay maaaring maging kapaki-pakinabang? Kaya ito lumiliko out - at hayaan mo akong lumipat sa teaser dito na sa web. Kami ay pagpunta sa simulan ang paggamit ng isang hindi mga programa na wika sa unang, ngunit isang markup language. Ang isang markup language pagiging isang bagay na katulad sa espiritu sa programming wika, ngunit hindi ito nagbibigay sa iyo ng kakayahan upang ipahayag ang iyong sarili lohikal. Ito lamang ay nagbibigay sa iyo ng kakayahan upang ipahayag ang iyong sarili structurally. 

Saan ang nais mong ilagay ang isang bagay sa pahina, ang web page na ito? Anong kulay ang gusto mong gawin ito? Ano ang laki ng font ang gusto mong gawin ito? Ano ang mga salita gawin mo talaga gusto sa web page? Kaya na ang isang markup language. Ngunit pagkatapos ay magpapadala kami masyadong mabilis ipakilala JavaScript, na isang full-nasimulan mga programa wika. Tunay na katulad syntactically sa hitsura sa C, ngunit magkakaroon ito ng ilang magaling, mas malakas, mas user friendly na mga tampok. 

At ang isa sa mga frustrations sa ito punto sa semestre ay na bibigyan namin ng madaling ipatupad speller sa malayo mas kaunting linya ng code gamit ang iba pang mga wika C kaysa sa sarili nito ay nagbibigay-daan, ngunit para sa dahilan ng ipapakita namin sa lalong madaling panahon maunawaan. Ito ang magiging unang tulad ng web page. Ito ay magiging ganap na underwhelming, ang unang isa ginawa namin. Ito ay simpleng sabihin, kumusta mundo. Ngunit kung hindi mo pa nakikita ito bago, ito ay HTML, Hypertext Markup Language. 

Kung pupunta ka sa isang tiyak na pagpipilian sa menu karamihan ng anumang browser, sa anumang web page sa ang internet, maaari mong makita ang HTML na ang ilang mga tao ay sumulat sa lumikha ng mga web na pahina. At ito ay malamang na hindi kamukha ng maikling o bilang kapong baka bilang na ito. Ngunit ito ay sundin ang mga pattern ng mga open bracket at slashes at titik at potensyal na mga numero. 

Naisip ko na gusto kong bigyan ka ng isang teaser ng kung ano ang magagawa mong gawin pagkatapos ng pagkuha ng CS50. Hayaan akong pumunta sa cs.harvard.edu / looban, ating sariling Rob Bowden gumagana sa homepage. Siya ginawa ito para sa amin. Kaya makikita mo sa lalong madaling panahon magagawang upang gawin iyon. At din, kung ano ang iyong narinig ito umaga - kung ano ang iyong narinig ito umaga - 

[Hamster dance musika] 

- You'll magagawang gumawa ito. Na naghihintay sa amin sa Miyerkules. Kami ay makita mo pagkatapos. 

[Hamster dance musika] David MALAN: Sa susunod na CS50 -