[Powered by Google Translate] [Linggo 6, patuloy na] [David J. Malan] [Harvard University] [Ito ay CS50.] [CS50.TV] Ito ay CS50 at ito ay ang katapusan ng linggo 6. Kaya CS50x, isa sa Harvard ng mga unang kurso na kasangkot sa edX inisyatiba katunayan debuted ito nakaraang Monday. Kung nais mong upang makakuha ng isang sulyap sa kung ano ang iba sa Internet na ngayon ang mga sumusunod na kasama ng, maaari kang magtungo sa x.cs50.net. Na-redirect ka sa naaangkop na lugar sa edx.org, na kung saan ang mga ito at iba pang mga kurso mula sa MIT at Berkeley Live na ngayon. Magkakaroon ka upang mag-sign up para sa isang account, makikita mo na ang materyal ay higit sa lahat ang parehong habang ikaw ay nagkaroon semestre na ito, kahit na ng ilang linggo maantala, bilang makuha namin ang lahat handa. Ngunit ano ay ngayon makita ang mag-aaral sa CS50x ay isang interface medyo tulad ng isang ito. Ito, halimbawa, Zamyla humahantong ang walkthrough para sa hanay ng problema 0. Sa pag-log in sa edx.org, CS50x mag-aaral ay nakikita ang mga uri ng mga bagay gusto mong asahan na makita sa isang kurso: ang panayam para sa Lunes, panayam para sa Miyerkules, iba't ibang mga shorts, set ang problema, walkthroughs, PDF. Sa karagdagan, tulad ng nakikita mo dito, machine pagsasalin ng Ingles transcript sa Chinese, Japanese, Espanyol, Italyano, at ng buong bungkos ng iba pang mga wika na ay tiyak na hindi lubos na pagsisisi bilang roll namin sa kanila ang programa gamit ang isang bagay na tinatawag ng isang API, o application programming interface, mula sa Google na nagbibigay-daan sa amin upang i-convert ang Ingles sa iba pang mga wika. Ngunit salamat sa magandang espiritu ng ilang daang-plus na boluntaryo, random na mga tao sa Internet na Pinapayuhan inaalok sa mga makibahagi sa proyektong ito, ipapakita namin dahan-dahan na pagpapabuti ng kalidad ng mga pagsasalin sa pamamagitan ng pagkakaroon ng tao itama ang mga pagkakamali na ang aming mga computer ay ginawa. 

Kaya ito lumiliko out namin ng ilang higit pang mga mag-aaral ay nagpapakita sa Lunes kaysa sa inaasahan namin simula. Sa katunayan, ngayon CS50x ay may 100,000 taong sumusunod sa kasama sa bahay. Kaya Napagtanto ikaw ay ang lahat ng bahagi ng ito pampasinaya klase ng kursong ito sa computer science edukasyon mas pangkalahatan, mas malawak, naa-access. At ang katotohanan na ngayon, sa ilan sa mga napakalaking online na kurso, lahat ng mga ito ay magsimula sa mga napakataas na numero, bilang tila namin nagawa dito. Ngunit ang layunin, sa huli, para sa CS50x talagang upang makakuha ng maraming mga tao sa ang tapusin linya hangga't maaari. Sa pamamagitan ng disenyo, CS50x ay pagpunta sa inaalok mula sa nakaraang Monday ang lahat ng mga paraan sa pamamagitan ng Abril 15, 2013, sa gayon ang mga tao na may pagtuon sa paaralan sa ibang lugar, trabaho, pamilya, iba pang mga salungatan at tulad, ng kaunti pang kakayahang umangkop na sumisid sa kursong ito, na, sumapat ito sa sabihin, ay medyo ambitiously tapos kung lamang sa loob ng tatlong buwan sa panahon ng isang karaniwang semestre. Subalit ang mga mag-aaral na ito ay tackling ang parehong hanay ng problema, tingnan ang parehong nilalaman, sa pagkakaroon ng access sa parehong shorts at ang mga tulad ng. Kaya Napagtanto na namin ang lahat talagang sa ito sama-sama. At isa sa mga layunin ng pagtatapos ng CS50x ay hindi lamang upang makakuha ng maraming mga tao sa linya ng tapusin at bigyan sila ito newfound unawa ng computer science at programming kundi pati na rin sa kanila ang nakabahaging karanasan. Isa ng mga tumutukoy na katangian na 50 sa campus, inaasahan namin, ang ganitong uri ng communal karanasan, para sa mas mahusay o para sa mas masahol pa, minsan, ngunit ang mga taong ito upang i-sa kaliwa at sa kanan, at mga oras ng opisina at ang hackathon at ng patas. Ito ay isang maliit na mahirap upang gawin iyon sa taong may mga tao online, ngunit CS50x ay pagtibayin sa buwan ng Abril sa unang kailanman CS50 Expo, kung saan ay isang online na paglalapat ng aming mga ideya ng patas kung saan ang mga libu-libong ng mga mag-aaral ay iniimbitahan upang magsumite ng 1 - sa 2-minutong video, alinman sa isang screencast sa kanilang panghuling proyekto o video sa kanila waving kumusta at pakikipag-usap tungkol sa kanilang mga proyekto at demoing ito, magkano tulad ng iyong mga predecessors ginawa dito sa campus sa patas, kaya na sa pamamagitan ng pagtatapos ng semestre, ang pag-asa ay upang magkaroon ng isang pandaigdigang exhibition ang CS50x mga mag-aaral 'panghuling proyekto, tulad ng na kung saan naghihintay sa iyo na ito Disyembre dito sa campus. Kaya higit pa sa buwan na darating. 

May mga 100,000 mga mag-aaral, bagaman, ay isang pangangailangan para sa isang ilang higit pang mga Cas. Given na iyong guys ay nagliliyab ang trail dito at pagkuha CS50 ilang linggo sa bago release ang materyal na ito sa mga tao sa edX, Napagtanto ibig naming sangkot ng maraming ng aming sariling mga mag-aaral hangga't maaari sa ito inisyatiba, parehong panahon ng semestre pati na rin ang taglamig na ito at ito darating na tagsibol. Kaya kung nais mong upang makakuha ng kasangkot sa CS50x, lalo pagsali sa sa CS50x talakayin, ang edX bersyon ng CS50 talakayin, kung saan marami sa inyo ay gamit sa campus, ang online bulletin board, mangyaring pumunta sa URL na iyon, ipaalam sa amin kung sino ka, dahil gusto namin ibigin upang bumuo ng isang koponan ng mga mag-aaral at kawani at faculty magkamukha sa campus na lamang sa paglalaro ng kahabaan at pagtulong ang. At kapag nakita sila ng isang tanong na pamilyar sa kanila, marinig mo ang isang mag-aaral sa pag-uulat ilang mga bug sa isang lugar out doon sa ilang mga bansa sa Internet, at na mga singsing ng isang kampanilya dahil masyado kang nagkaroon na parehong isyu sa iyong d-hall ng ilang oras ang nakalipas, sana pagkatapos maaari mong tugtog ng relos sa at ibahagi ang iyong sariling karanasan. Kaya mangyaring huwag makibahagi kung nais mong. 

Computer science courses sa Harvard ay may isang bit ng isang tradisyon, CS50 kasama ng mga ito, ng pagkakaroon ng ilang mga damit, ilang mga damit, na maaari mong magsuot buong kapurihan sa pagtatapos ng semestre, na sinasabi medyo buong kapurihan na tapos ka CS50 at kinuha CS50 at tulad, at lagi naming subukan upang makasali ang mga mag-aaral sa prosesong ito hangga't maaari, kung saan inaanyayahan namin, sa paligid ng oras na ito ng semestre, ang mga mag-aaral upang isumite ang mga disenyo gamit ang Photoshop, o anumang tool ng pagpipilian na nais mong gamitin kung ikaw ay isang designer, upang isumite ang mga disenyo para sa mga T-shirt at sweatshirt at payong at maliit na bandanas para sa aso na namin ngayon at ang gusto. At ang lahat ay pagkatapos - ang mga nagwagi ng bawat taon ay exhibited sa website ng kurso sa store.cs50.net. Lahat ay ibinebenta sa gastos doon, ngunit ang website tumatakbo lamang sa mismong at nagbibigay-daan sa mga tao na piliin ang mga kulay at mga disenyo na gusto nila. Kaya ko naisip lang namin ibahagi ang ilan sa disenyo ng nakaraang taon na sa website bukod ang isang ito dito, kung saan ay isang taunang tradisyon. "Bawat Araw ako Seg Faultn" ay isa ng pagsusumite nakaraang taon, na magagamit pa rin para sa mga alumni. Nagkaroon kami ng isang ito, "CS50, Itinatag 1989." Isa ng aming mga Bowdens, Rob, ay napaka-tanyag nakaraang taon. "Team Bowden" ay ipinanganak, disenyo na ito ay isinumite, kabilang sa mga tuktok na nagbebenta. Bilang ang isang ito dito. Maraming mga tao ay may "Bowden Fever" ayon sa mga tala ng mga benta. Napagtanto na na maaaring na ngayong iyong disenyo doon, hanggang sa Internet. Higit pang mga detalye sa ito sa susunod na problema Nagtatakda darating. 

Isa pang tool: nagkaroon ka ilang pagkakalantad at sana ngayon ilang hands-on na karanasan sa GDB, na, siyempre, isang debugger at nagbibigay-daan sa iyo upang manipulahin iyong programa sa isang medyo mababa antas, ginagawa kung ano ang mga uri ng bagay? Ano ang ginagawa ng ng GDB hayaan mong gawin? Oo? Bigyan mo ako ng isang bagay. [Estudyante sagot, hindi maintindihan] Mabuti. Hakbang sa function na, kaya hindi mo na lang ay i-type patakbuhin at sumuntok sa programa sa pamamagitan ng kabuuan nito, pag-print out ng mga bagay sa standard output. Sa halip, maaari mong hakbang sa pamamagitan ng ito linya sa pamamagitan ng linya, alinman sa mag-type sa tabi pumunta ng linya sa pamamagitan ng linya sa pamamagitan ng linya o hakbang sa sumisid sa isang function, karaniwang isa na iyong sinulat ni. Ano pa ang GDB sabihin gagawin mo? Oo? [Estudyante sagot, hindi maintindihan] I-print variable. Kaya kung gusto mong gawin ang isang maliit na pagsisiyasat ng sarili sa loob ng iyong programa nang hindi na kinakailangang resort sa pagsusulat ng printf pahayag sa lahat ng dako ng lugar, Maaari mo lamang i-print ang isang variable o magpakita ng isang variable. Ano pa ang maaari mong gawin sa isang debugger tulad GDB? [Estudyante sagot, hindi maintindihan] Eksakto. Maaari mong itakda ang breakpoints, maaari mong sabihin na ang break na pagpapatupad sa pangunahing function na o ang foo function na. Maaari mong sabihin ang pagpapatupad ng pahinga sa line 123. At mga breakpoints talagang malakas na diskarte dahil kung mayroon kang isang pangkalahatang pakiramdam ng kung saan ang problema sa iyong marahil, hindi mo kailangang-aaksaya ng oras sa stepping sa kabuuan ng programa. Maaari mong mahalagang tumalon doon at pagkatapos ay simulang mag-type - stepping sa pamamagitan nito na may hakbang o sa tabi o ang tulad ng. Ngunit ang catch na may isang bagay tulad ng GDB ay tumutulong ito sa iyo, ang mga tao, mahanap ang iyong mga problema at hanapin ang iyong mga bug. Ito ay hindi kinakailangang makita ang mga ito kaya magkano para sa iyo. 

Kaya ipinakilala namin ang iba pang mga araw style50, na kung saan ay isang maigsing command line tool na sinusubukan sa stylize ang iyong code ng kaunti nang malinis kaysa sa iyo, ang mga tao, ay maaaring magkaroon ng tapos. Ngunit iyon, masyadong, ay talaga lamang ng isang Aesthetic bagay. Ngunit ito lumiliko out doon ang iba pang mga tool na tinatawag na Valgrind na ng kaunti pa arcane upang gamitin. Ang output nito ay misteriyoso atrociously sa unang tingin. Ngunit kamangha-mangha kapaki-pakinabang, lalo na ngayon na hindi namin sa bahagi ng termino kung saan ka simula upang gamitin ang malloc at dynamic na paglalaan ng memorya. Mga bagay na maaari pumunta talaga, talagang mali mabilis. Dahil kung nakalimutan mo upang magbakante ang iyong memorya, o dereference kang ilang mga null pointer, o dereference kang ilang mga basura pointer, ano ay karaniwang ang sintomas na mga resulta? Seg kasalanan. At makakakuha ka ng ito core file ng ilang bilang ng kilobytes o megabytes na kumakatawan sa estado ng memorya ng iyong programa kapag nag-crash, ngunit ang iyong programa sa huli seg ng mga faults, segmentation fault, na nangangahulugan ng isang bagay masamang nangyari halos palaging may kaugnayan sa isang memory-kaugnay na pagkakamali na iyong ginawa sa isang lugar. Kaya Valgrind tumutulong sa iyo na mahanap ang mga bagay tulad nito. Ito ay isang tool na iyong pinapatakbo, tulad ng GDB, pagkatapos mong pinagsama-sama ang iyong programa, ngunit sa halip na patakbuhin ang iyong programa nang direkta, patakbuhin mo Valgrind at pumasa ka dito ang iyong programa, tulad ng gagawin mo sa GDB. Ngayon, ang paggamit, upang makuha ang pinakamahusay na uri ng output, ay isang maliit na mahaba, kaya doon nasa ibabaw ng screen makikita mo makita ang Valgrind-v. "-V" sa halos pangkalahatang ay nangangahulugan maligoy kapag gumagamit ka ng mga programa sa isang Linux computer. Kaya ibig sabihin nito ay sabihin ang lahat ng mga mas maraming data kaysa sa maaari bilang default. "- Mahayag-check = puno na." Ito ay sinasabi ng tseke para sa lahat ng posibleng mga paglabas ng memorya, pagkakamali na maaaring ko ginawa. Ito, masyadong, ay isang pangkaraniwang paradaym sa Linux programa. Sa pangkalahatan, kung mayroon kang isang command line argument na isang "lumipat", na dapat baguhin ang pag-uugali ng programa, at ito ng isang sulat, ito-v, ngunit kung na lumipat, lamang sa pamamagitan ng disenyo ng programmer, ay isang buong salita o serye ng mga salita, ang argument ng linya ng command na nagsisimula sa -. Ito lamang ang tao convention, ngunit makikita mo ang mga ito nagiging. At pagkatapos, sa wakas, "a.out" ay ang arbitrary pangalan para sa programa sa partikular na halimbawa. At narito ang ilang kinatawan output. 

Bago masaya naming sa kung ano na maaaring ibig sabihin, hayaan mo akong pumunta sa isang snippet ng code sa paglipas dito. At hayaan mo akong ilipat ito ng paraan, paparating, at sabihin tingnan sa memory.c, na kung saan ay ang maikling halimbawa dito. Kaya sa programang ito, hayaan mo akong mag-zoom in sa mga pag-andar at mga tanong. Mayroon kaming isang function pangunahing na tawag sa isang function, f, at pagkatapos ay kung ano ang f magpatuloy na gawin, sa bahagyang teknikal na Ingles? Ano ang f magpatuloy sa ko? Paano tungkol sa ko makikita magsimula sa linya 20, at hindi mahalaga ang lokasyon ng bituin, ngunit ko lang maging pare-pareho dito sa huling panayam. Ano ang linya 20 para sa amin? Sa kaliwang bahagi. Hihimayin namin ito nang higit pa. Int * x: kung ano ang na gawin? Okay. Ito ay deklarasyon ng isang pointer, at ngayon sabihin mas teknikal. Ano ang ibig sabihin, napaka concretely, upang idedeklara ng pointer? Ibang tao? Oo? [Estudyante sagot, hindi maintindihan] Masyadong malayo. Kaya ka binabasa sa kanang bahagi ng katumbas sign. Natin tumutok lamang sa kaliwa, sa int * x. Ito ay "idedeklara" pointer, ngunit ngayon natin sumisid sa mas malalim na kahulugan. Ano ang na concretely, ibig sabihin technically? Oo? [Estudyante sagot, hindi maintindihan] Okay. Ito ay naghahanda upang i-save ang isang address sa memorya. Mabuti. At sabihin sa isang hakbang karagdagang; ito deklarasyon ng variable, x, na 32 bit. At alam ko ito ay 32 bits dahil -? Hindi ito dahil ito ay isang int, dahil ito ay isang pointer sa kasong ito. Pagkakataon na ito ay isa at ang parehong may isang int, ngunit ang katotohanan na may star ang nangangahulugan na ito ay isang pointer at sa appliance, na may maraming mga computer, ngunit hindi lahat, ng mga payo 32 bit. Sa mas modernong hardware tulad ng pinakabagong Mac, ang pinakabagong PC, maaaring mayroon ka ng mga 64-bit na payo, ngunit sa appliance, ang mga bagay na ito ay 32 bit. Kaya namin ilagay sa pamantayan sa na. Higit pang concretely, kuwento naging tulad ng sumusunod: Namin ang "idedeklara" ng pointer; kung ano ang na ibig sabihin nito? Hinahanda namin upang mag-imbak ng address ng memorya. Ano ang na ibig sabihin nito? Namin na lumikha ng isang variable na tinatawag na x na tumatagal ng hanggang 32 bit na madaling iimbak ang address ng isang integer. At na maaaring tungkol sa bilang tumpak hangga't maaari naming makakuha ng. Masarap na paglipat ng pasulong upang gawing simple ang mundo at sabihin ipinapahayag ng pointer na tinatawag na x. Magpahayag ng isang pointer, ngunit mapagtanto at maunawaan kung ano ang aktwal na pagpunta sa kahit sa mga ilang mga character lamang. 

Ngayon, ito ang halos isang maliit na mas madali, kahit na ito ang isang na expression. Kaya kung ano ang ito ginagawa, na naka-highlight na ngayon: "malloc (10 * sizeof (int));" Oo? [Estudyante sagot, hindi maintindihan] Mabuti. At Kukunin ko ang mga ito doon. Ito ay paglaan ng isang tipak ng memory para sa sampung integer. At ngayon sabihin sumisid sa bahagyang mas malalim; paglaan ito isang tipak ng memory para sa sampung integer. Ano ang malloc pagkatapos bumabalik? Ang address ng tigkal na, o, mas concretely, ang address ng unang byte ng tigkal na. Paano Ako, programmer, malaman kung saan na tipak ng mga dulo ng memory? Alam ko na ito ay magkadikit. Malloc, sa pamamagitan ng kahulugan, ay magbibigay sa iyo ng isang magkadikit na tipak ng memorya. Walang mga gaps sa loob nito. Mayroon kang access sa bawat byte sa tigkal na, bumalik upang i-back-back, ngunit paano ko malalaman kung saan ang dulo ng ito tipak ng memory? Kapag mong gamitin ang malloc? [Estudyante sagot, hindi maintindihan] Magandang. Hindi mo gusto. Mong matandaan. Kong tandaan na ginamit ko ang halaga 10, at hindi ko kahit na mukhang nagawa na dito. Ngunit pananagutan ay ganap na sa akin. Strlen, na kung saan kami maging bahagyang tiwala para sa mga string, gumagana lamang dahil sa ang convention na ito ng pagkakaroon ng \ 0 o ito espesyal na character na nul, NUL, sa dulo ng isang string. Na hindi pindutin nang matagal para lamang arbitrary chunks ng memory. Ito ay hanggang sa iyo. Kaya linya 20, pagkatapos, allocates ng tipak ng memory na maaaring iimbak ng sampung integer, at iniimbak ang address ng unang byte ng na tipak ng memory sa variable na tinatawag na x. Samakatuwid, na kung saan ay isang pointer. Kaya linya 21, sa kasamaang-palad, ng pagkakamali. Ngunit una, kung ano ang ginagawa? Ito ay sinasabi ng tindahan sa lokasyon 10, 0 na-index, ng tipak ng memory na tinatawag na x ang halaga 0. 

Kaya mapansin ng ilang mga bagay ay pagpunta sa. Kahit na ang isang pointer ang x, isipin ang mula sa ilang linggo na ang nakakaraan na maaari mo pa ring gamitin ang array-style square bracket pagtatanda. Dahil na talagang maikling-kamay pagtatanda para sa higit pa misteriyoso mukhang aritmetika pointer. kung saan gusto naming gawin ang isang bagay tulad nito: Dumaan sa address x, ilipat ang 10 spot sa paglipas ng, pagkatapos ay pumunta doon sa anumang address ay naka-imbak sa lokasyon na iyon. Ngunit lantaran, ito ay mabangis na basahin at maging komportable. Kaya ang mundo ay karaniwang gumagamit ng mga square bracket dahil lang sa ito ay kaya mas tao friendly na basahin ang. Ngunit iyon lamang ang kung ano talaga ang nangyayari sa ilalim ng hood; x ay isang address, hindi isang array, per se. Kaya ito ay ang pag-iimbak ng 0 sa lokasyon 10 sa x. Bakit ito masama? Oo? [Estudyante sagot, hindi maintindihan] Mismong. Inilalaan lamang namin sampung ints, ngunit umaasa kami mula 0 kapag programa sa C, kaya mayroon kang access 0 1 2 3 4 5 6 7 8 9, ngunit hindi 10. Kaya ang programa ay pagpunta sa seg kasalanan o hindi. Ngunit hindi pa namin talaga alam, ito ay uri ng nondeterministic pag-uugali. Ito talagang depende sa kung makuha namin masuwerteng. Kung ito ay lumiliko out na ang mga operating system ay hindi tututol kung gagamitin ko na ang dagdag na byte, kahit na hindi ito ay ibinigay ito sa akin, ang aking programa ay hindi maaaring pag-crash ng. Ito raw, maraming surot, ngunit hindi mo maaaring makita na sintomas, o maaari mong makita ang mga ito nang isang beses lamang sa isang habang. Ngunit ang katotohanan ay na ang bug ay, sa katunayan, may. At talagang problemang kung ikaw ay nakasulat sa isang programa na nais mong tama, na iyong ibinebenta ang program na ginagamit ng mga tao ang bawat isang beses sa isang habang nagka-crash dahil, siyempre, ito ay hindi maganda. Sa katunayan, kung mayroon kang isang Android phone o isang iPhone at mong i-download ang apps mga araw na ito, kung sakaling mo ay nagkaroon ng isang app lang mag-quit, ang lahat ng isang biglaang ito mawala, na halos palaging resulta ng ilang mga isyu na nauugnay sa memory, kung saan programmer screwed up at dereferenced pointer na siya o hindi siya dapat magkaroon, at ang mga resulta ng iOS o Android pumatay lamang ang programa sa kabuuan kaysa sa panganib hindi natukoy na pag-uugali o ilang mga uri ng kompromiso sa seguridad. 

May isa pang bug sa programang ito bukod sa isang ito. Ano pa ko screwed sa programang ito? Hindi ko na ensayado kung ano ang ko na ipinangaral. Oo? [Estudyante sagot, hindi maintindihan] Magandang. Hindi ko pa napalaya ang memory. Kaya ang pamantayan ngayon na anumang oras tumawag ka malloc, dapat mong tawagan ang libreng kapag tapos ka na gamit na memory. Ngayon, kapag Gusto ko nais upang magbakante ito memory? Marahil, ipagpalagay na ang unang linya na ito ay tama, Gusto ko nais na gawin ito dito. Dahil hindi ako, halimbawa, gawin ito dito. Bakit? Lamang sa labas ng saklaw. Kaya kahit pinag-uusapan natin ang tungkol sa mga payo, ito ay isang linggo 2 o 3 isyu, kung saan ang x ay lamang sa saklaw sa loob ng kulot tirante na kung saan ito ay ipinahayag. Kaya talagang hindi maaaring magbakante doon. Aking lamang pagkakataon upang magbakante ito ay halos pagkatapos linya 21. Ito ay isang medyo simpleng programa; ito ay medyo madali sa sandaling uri ng balot ang iyong isip sa paligid ng kung ano ang programa ng paggawa, kung saan ang mga pagkakamali ay. At kahit na hindi mo makita ang mga ito sa unang, sana ito ng kaunti halata ngayon na ang mga pagkakamali na ito ay medyo madaling malutas at madaling ginawa. Ngunit kapag ang isang programa ay higit sa 12 linya ang haba, 50 linya mahaba, 100 linya ang haba, paglalakad sa pamamagitan ng iyong linya ng code sa pamamagitan ng linya, iniisip lohikal na sa pamamagitan nito, ay posible ngunit hindi partikular na masaya na gawin, patuloy na naghahanap para sa mga bug, at ito ay din mahirap gawin, at na kung bakit umiiral ang isang tool tulad ng Valgrind. Hayaan akong magpatuloy at gawin ito: hayaan mo akong buksan ang aking terminal na window, at ipaalam sa akin hindi lamang magpatakbo ng memorya, dahil memorya ay tila na maging fine. Nakakakuha ako ng masuwerteng. Pagpunta sa na ang karagdagang mga byte sa dulo ng array ay hindi mukhang masyadong problema. Ngunit ipaalam sa akin, gayunman, katinuan check, kung saan ay nangangahulugan lamang upang suriin man o hindi ito ay talagang tama. 

Kaya sabihin gawin valgrind-v - mahayag-check = buong, at pagkatapos ay ang pangalan ng programa sa kasong ito ay memory, hindi a.out. Kaya hayaan mo akong magpatuloy at gawin ito. Pindutin ang Enter. Minamahal naming Diyos. Ito ay ang output nito, at ito ay kung ano ang ko alluded sa mas maaga. Ngunit, kung matuto mong basahin ang lahat ng bagay na walang kapararakan dito, karamihan sa mga ito ay lamang diagnostic output na hindi na kawili-wili. Ano ang iyong mata ay talagang nais na hinahanap anumang pagbanggit ng error o di-wasto. Salita na iminumungkahi ng mga problema. At sa katunayan, sabihin makita kung ano ang nangyayari maling pababa dito. Mayroon akong isang buod ng mga uri, "sa paggamit sa exit: 40 bytes sa 1 bloke" Hindi ako talagang sigurado kung ano ang bloke ng pa, ngunit 40 bytes aktwal na nararamdaman tulad ko maaaring malaman kung saan na nagmumula. 40 bytes. Bakit 40 bytes sa paggamit sa exit? At higit na partikular, kung mag-scroll pababa namin dito, bakit ako siguradong nawala 40 bytes? Oo? [Estudyante sagot, hindi maintindihan] Perpekto. Oo, eksakto. Mayroong sampung integer, at sa bawat isa ng mga laki ng 4, o 32 bit, kaya nawala ko ang tiyak 40 bytes dahil, bilang iminungkahi, hindi ko na tinatawag na libreng. Iyon ay isang bug, at ngayon tingnan natin ang isang maliit na karagdagang at makita sa tabi ito, "Di-wasto ang sumulat ng laki 4." Ngayon kung ano ito? Address na ito ay ipinahayag kung ano ang base notation, tila? Ito ay hexadecimal, at anumang oras nakakita ka ng isang numero na nagsisimula sa 0x, ito ay nangangahulugan na hexadecimal, na ginawa namin ang paraan pabalik sa, tingin ko, pset 0 seksyon ng mga tanong, na lang gawin isang warmup ehersisyo, na-convert ng decimal sa hex sa binary at iba pa. Hexadecimal, sa pamamagitan ng tao na convention, ay karaniwang ginagamit upang kumatawan payo o, mas pangkalahatan, address. Lang ng convention, dahil ito ay isang maliit na mas madaling basahin, ito ay isang maliit na mas compact kaysa sa isang bagay tulad ng decimal, at binary ay walang silbi para sa karamihan ng mga tao upang gamitin. Kaya ngayon kung ano ang ibig sabihin nito? Well, mukhang may isang di-wastong write ng laki 4 sa linya 21 ng memory.c. Kaya sabihin bumalik sa linya 21, at sa katunayan, dito ay ang mga di-wastong write. Kaya Valgrind ay hindi ganap na hawakan ang aking kamay at sabihin sa akin kung ano ang fix ang, ngunit ito ay paghanap na ako paggawa ng di-wastong write. Ako pagpindot 4 bytes na hindi ko dapat na, at tila na dahil, habang ikaw ay tulis out, ako ginagawa [10] sa halip na [9] maximally o [0] o isang bagay sa pagitan. Sa Valgrind, Napagtanto anumang oras ngayon sumusulat ka ng isang programa na gumagamit ng mga payo at gumagamit ng memory, at malloc higit na partikular, talagang makakuha sa ang ugali ng tumatakbo ito mahaba ngunit napaka madaling kopyahin at ilagay ang utos ng Valgrind upang makita kung mayroong ilang mga error sa doon. At ito ay napakalaki sa bawat oras na makita mo ang output, ngunit lamang parse sa pamamagitan ng biswal lahat ng output at makita kung makakita ka pagbanggit ng mga error o babala o di-wasto o mawawala. Anumang mga salita na tunog tulad mo screwed up sa isang lugar. Kaya Napag-alaman na ang isang bagong tool sa iyong toolkit. 

Ngayon sa Monday, nagkaroon kami ang maramihang mga tao ang dumating dito at kumatawan sa paniwala ng isang naka-link na listahan. At ipinakilala namin ang naka-link na listahan bilang isang solusyon sa kung ano ang problema? Oo? [Estudyante sagot, hindi maintindihan] Magandang. Array ay hindi maaaring magkaroon ng memory naidagdag sa kanila. Kung maglaan ka ng isang hanay ng mga laki 10, na ang lahat makakuha ka. Maaari mong tawagan ang isang katangian tulad realloc kung una mong tinatawag malloc, at na maaaring subukan upang palaguin ang array kung may puwang patungo sa dulo ng na walang pang gumagamit, at kung mayroong hindi, ito lang mahanap ka ng mas malaking tipak sa ibang lugar. Ngunit ito ay kopyahin ang lahat ng mga byte sa bagong array. Ito tunog tulad ng isang tamang solusyon. Bakit ito hindi nakaaakit? Ibig kong sabihin ito gumagana, ang mga tao na malutas ang problemang ito. Bakit kailangan namin upang malutas ito sa Lunes na may mga naka-link na listahan? Oo? [Estudyante sagot, hindi maintindihan] Maaaring magtagal. Sa katunayan, anumang oras sa pagtawag ka malloc o realloc o calloc, na pa isa pa, anumang oras, ang program, pakikipag-usap sa operating system, malamang ka upang mapabagal ang program. At kung gumagawa ka ng mga ganitong uri ng mga bagay sa mga loop, ikaw talaga ay pagbagal bagay. Hindi ka pagpunta upang mapansin ito para sa pinakasimpleng ng "hoy mundo" na mga programa uri, ngunit sa mas malaking programa, na humihiling sa operating system na muli at muli para sa memory o pagbibigay ito muli at muli ay may kaugaliang hindi upang maging isang magandang bagay. Plus, ito ay uri ng intellectually - ito ay isang kumpletong basura ng oras. Bakit magtalaga ng higit pa at higit pa memory, panganib ng pagkopya ng lahat sa bagong array, kung mayroon kang isang alternatibong na hinahayaan maglaan ka lamang ng mas maraming memorya bilang iyong aktwal na kailangan? Kaya may mga plus at minuses in dito. Isa ng ang plus na ngayon ay mayroon kaming dynamism. Hindi mahalaga kung saan ang mga chunks ng memory na libre, Maaari ko lang ayusin ng lumikha ng mga crumbs ng tinapay sa pamamagitan ng mga payo string aking buong naka-link na listahan. Ngunit magbayad ako ng hindi bababa sa isang presyo. 

Ano ang gagawin ko upang bigyan sa pagkakaroon ng mga naka-link na listahan? Oo? [Estudyante sagot, hindi maintindihan] Magandang. Kailangan mo ng karagdagang memorya. Ngayon ay kailangan ko ng espasyo para sa mga payo, at sa kaso ng mga ito sobrang simple na naka-link listahan na lamang sinusubukan upang mag-imbak ng mga integer, na 4 bytes, panatilihin namin sinasabi na rin, ang pointer ng 4 bytes, kaya ngayon literal ko Dinoble ang halaga ng memory kailangan ko lang-imbak sa listahang ito. Ngunit muli, ito ay isang patuloy na tradeoff sa computer science sa pagitan ng oras at space at pag-unlad, pagsusumikap at iba pang mga mapagkukunan. Ano ang isa pang downside ng paggamit ng isang naka-link na listahan? Oo? [Estudyante sagot, hindi maintindihan] Mabuti. Hindi bilang madaling i-access. Aming makakaya na pakikinabangan linggo 0 prinsipyo tulad hatiin at lupigin. At higit na partikular, binary paghahanap. Dahil kahit kami tao makita ang halos kung saan sa gitna ng listahang ito, computer lamang alam na ito ay naka-link na listahan ay nagsisimula sa address tinatawag na unang. At na ang 0x123 o isang bagay tulad na. At ang tanging paraan sa programa hanapin ang gitnang elemento ay sa aktwal na hanapin ang buong listahan. At kahit pagkatapos, literal upang maghanap sa buong listahan dahil kahit na sa sandaling naabot mo na ang gitnang elemento sa pamamagitan ng pagsunod sa mga payo, mo, ang programa, walang ideya kung gaano katagal ang listahang ito ay, potensyal, hanggang maabot ang dulo nito, at kung paano alam mo sa programa na ikaw ay sa dulo ng isang naka-link na listahan? May isang espesyal null pointer, kaya muli, isang convention. Sa halip na gamitin ito pointer, tiyak namin ay hindi gusto ang mga ito sa ilang mga halaga ng basura pagturo off ang yugto sa isang lugar, gusto naming ito sa kamay, null, kaya mayroon kaming ang terminal na ito sa istraktura ng data na ito upang malaman namin kung saan ito nagtatapos. 

Ano kung gusto namin upang manipulahin ito? Ginawa namin karamihan ng ito biswal, at sa mga tao, ngunit kung ano kung gusto naming gawin ang isang pagpapasok ng? Kaya ang orihinal na listahan ay 9, 17, 20, 22, 29, 34. Paano kung gusto namin pagkatapos sa malloc espasyo para sa bilang 55, node para dito, at pagkatapos ay gusto naming upang ipasok ang 55 sa listahan tulad ng ginawa namin sa Lunes? Paano namin gawin ito? Well, Anita dumating up at mahalagang lumakad siya sa listahan. Siya ay nagsimula sa unang elemento, pagkatapos ay sa susunod, sa susunod, sa susunod, sa susunod, sa susunod. Panghuli pindutin ang kaliwang lahat ang paraan down at natanto oh, ito ay null. Kaya kung ano ang pointer pagmamanipula kailangan gawin? Ang taong sa dulo, bilang 34, kailangan ang kanyang kaliwang itinaas upang ituro sa 55, 55 kailangan kanilang kaliwang braso na nakaturo pababa sa bagong null Terminator. Tapos na. Medyo madali upang ipasok 55 sa isang pinagsunod-sunod na listahan. At kung paano ito tumingin? 

Hayaan akong sige at buksan ang ilang mga halimbawa ng code dito. Kukunin ko na buksan gedit, at hayaan mo akong magbukas ng dalawang mga file muna. Isa ay list1.h, at ipaalam sa akin lamang ipaalala na ito ay tipak ng code na aming ginamit upang kumatawan sa isang node. Ang isang node ay parehong isang int tinatawag n at pointer na tinatawag na susunod na lang puntos sa susunod na bagay sa listahan. Na ngayon ang isang file na. H. Bakit? May convention na ito, at hindi namin kinuha ang bentahe ng ito sa isang malaking halaga ating sarili, ngunit ang mga tao na sinulat ni printf at iba pang mga function ibinigay bilang isang regalo sa mundo ang lahat ng mga function sa pamamagitan ng pagsusulat ng isang file na tinatawag na stdio.h. At pagkatapos ay may string.h, at pagkatapos ay may map.h, at mayroong lahat ng mga h file na maaari mong nakikita o na ginamit sa panahon ng termino na isinulat ng mga ibang tao. Karaniwan sa mga h file lamang na mga bagay tulad ng mga typedefs o pagdeklara ng mga pasadyang uri o pagdeklara ng constants. Hindi mo ilagay ang function 'pagpapatupad sa mga file ng header. Mong ilagay, sa halip, lamang ang kanilang modelo. Ikaw ang maglalagay ng mga bagay na nais mong ibahagi sa mundo kung ano ang kailangan nila upang makatipon ng kanilang code. Kaya lamang upang makakuha ng sa ito ugali, napagpasyahan naming gawin ang parehong bagay. Walang mas sa list1.h, ngunit namin na ilagay ang isang bagay na maaaring ng interes sa mga tao sa mundo na nais na gamitin ang aming naka-link na listahan ng pagpapatupad. Ngayon, sa list1.c, hindi ako ay pumunta sa pamamagitan ng buong bagay dahil ito ay isang bit mahaba, ang programang ito, ngunit sabihin patakbuhin ito real mabilis sa prompt. Ipaalam sa akin makatipon List1, ipaalam sa akin pagkatapos patakbuhin List1, at kung ano ang makikita mo ay na namin simulate ng isang simpleng maliit na programa dito na pagpunta upang payagan ang sa akin upang magdagdag at alisin ang mga numero sa isang listahan. Kaya hayaan mo akong magpatuloy at i-type ang 3 para sa mga pagpipilian sa menu ng 3. Gusto kong ipasok ang numero - sabihin gawin ang unang numero, kung saan ay 9, at ngayon ako sinabi sa listahan na ngayon 9. Hayaan akong magpatuloy at gawin ang isa pang pagpapasok ng, kaya ko maabot ang opsyon sa menu 3. Ano ang numero ang gusto kong isingit? 17. Enter. At makikita ko lamang isa pang. Hayaan akong ipasok ang numero 22. Kaya namin ang Beginnings ng naka-link na listahan na nagkaroon kami sa slide anyo ng ilang sandali ang nakalipas. Paano ang pagpapasok ng ito aktwal na nangyayari? Sa katunayan, 22 na ngayon sa dulo ng listahan. Kaya ang kuwento sinabi namin sa yugto sa Lunes at recapped ngayon lang dapat aktwal na nangyayari sa code. Natin tingnan. Hayaan ang mag-scroll pababa sa akin sa file na ito. Susubukan naming pagtakpan ang ilan sa mga pag-andar, ngunit gagamitin namin down sa, sabihin nating, ang insert function na. 

Natin makita kung paano namin pumunta tungkol sa pagpasok ng isang bagong node sa ito naka-link na listahan. Kung saan ay ang listahan ng ipinahayag? Well, sabihin mag-scroll ang lahat ng mga paraan sa itaas, at mapansin na ang aking naka-link na listahan ay mahalagang ipinahayag bilang isang solong pointer na simula null. Kaya ako gamit ang isang pandaigdigang variable dito, na sa pangkalahatan namin ang ipinangaral laban sapagkat ito ay gumagawa ng iyong code ng kaunti magulo upang mapanatili, uri ng tamad, karaniwan, ngunit hindi tamad at hindi ito mali at ito ay hindi masama kung ang tanging layunin ng iyong programa sa buhay ay upang gayahin ang isang naka-link na listahan. Na kung saan ay eksakto kung ano ang ginagawa namin. Kaya sa halip na idedeklara ito sa pangunahing at pagkatapos ay upang pumasa ito sa bawat function na namin ang nakasulat sa programang ito, Napagtanto namin sa halip oh, sabihin lamang gawin ito pandaigdigang dahil ang buong layunin ng programang ito ay upang ipakita ang isa at isa lamang na naka-link listahan. Kaya na nararamdaman okay. Narito ang aking mga modelo, at hindi namin ay pumunta sa pamamagitan ng lahat ng ito, ngunit ako ay sinulat ni isang tanggalin ang function, mahanap ang function, isang ipasok ang function na, at pagbagtas function na. Ngunit sabihin ngayon bumalik pababa upang ipasok ang pag-andar at makita kung paano ang isang ito gumagana dito. Ipasok sa linya - dito kami. Ipasok ang. Kaya hindi ito gumawa ng anumang argumento, dahil kami ay pagpunta sa hilingin ng gumagamit sa loob ng ang function na ito para sa bilang na nais nilang upang ipasok. Ngunit una, hinahanda namin upang bigyan ang mga ito ng ilang espasyo. Ito ay uri ng kopyahin at i-paste mula sa iba pang mga halimbawa. Sa kasong iyon, tayo ay paglaan ng isang int; oras na ito namin ang paglaan ng node. Hindi ko talagang tandaan kung gaano karaming mga byte node, ngunit na fine. Maaaring malaman ng Sizeof na para sa akin. At bakit ako check para sa null sa linya 120? Ano ang maaaring pumunta mali sa linya 119? Oo? [Estudyante sagot, hindi maintindihan] Mabuti. Lamang ay maaaring ang kaso na tatanungin ko na para sa masyadong maraming memorya o isang bagay na mali at operating system ay hindi sapat na bytes ninyo ako, kaya signal ng mas maraming sa pamamagitan ng pagbalik null, at kung hindi ko check para sa at ko lang nang walang taros magpatuloy upang gamitin ang address ibinalik, maaari itong maging null. Ito ay maaaring maging ng ilang hindi kilalang halaga; hindi isang magandang bagay maliban kung ko - aktwal na ay hindi isang hindi kilalang halaga. Ito ay maaaring maging null, kaya hindi ko nais upang abusuhin ito at ipagsapalaran dereferencing ito. Kung nangyari iyon, ko lang bumalik at kami na magpanggap tulad ng hindi ako makabalik anumang memorya sa lahat. 

Kung hindi man, sabihin ko ang user ninyo akong bigyan ng numero upang ipasok, tumawag ako aming lumang kaibigan GetInt, at pagkatapos ito ay ang bagong syntax ipinakilala namin sa Lunes. 'Newptr-> n' ay nangangahulugan na ang address na ikaw ay ibinigay sa pamamagitan ng malloc na kumakatawan sa unang byte ng isang bagong bagay node, at pagkatapos ay pumunta sa patlang na tinatawag n. Ang isang maliit na mga bagay na walang kabuluhan tanong: Ito ay katumbas sa kung ano ang higit pa misteriyoso linya ng code? Paano pa ang maaari kong nakasulat na ito? Nais mo bang gumawa ng isang ulos? [Estudyante sagot, hindi maintindihan] Mabuti. Paggamit ng n, ngunit ito ay hindi pa kasing simple ng ito. Ano ang gagawin ko munang gawin? [Estudyante sagot, hindi maintindihan] Mabuti. Kailangan kong gawin * newptr.n. Kaya ito ay sinasabi ng bagong pointer malinaw naman ng isang address. Bakit? Dahil ito ay ibinalik ng malloc. Ang * newptr nagsasabing "pumunta doon," at pagkatapos ay sa sandaling nandoon ka, maaari mong gamitin ang mas pamilyar. n, ngunit ito lamang hitsura ng kaunti pangit, lalo na kung namin tao ay pagpunta sa gumuhit ng mga payo na may mga arrow sa lahat ng oras; mundo ay may Standardized sa arrow pagtatanda na ito, na ang eksaktong parehong bagay. Kaya mo lamang gamitin ang -> notation kapag ang mga bagay sa kaliwa ay isang pointer. Kung hindi man, kung ito ay isang aktwal na struct, gamitin ang. N. At pagkatapos ay ito: Bakit ko initialize ang newptr-> susunod sa Null? Hindi namin gusto ang nakalawit kaliwang kamay off ng dulo ng entablado. Gusto naming pagturo tuwid pababa, na nangangahulugan na ang dulo ng listahang ito maaaring potensyal sa node, kaya mas mahusay naming tiyakin na ito ay null. At, sa pangkalahatan, Sinisimulan ang iyong mga variable o ang iyong data ng mga miyembro at structs sa isang bagay lamang ang mahusay na kasanayan. Lamang pagpapaalam ng basura umiiral at patuloy na umiiral sa pangkalahatan ay nakakakuha ka sa pag- kung nakalimutan mo na gawin ang isang bagay sa susunod. 

Narito ang ilang mga kaso. Ito, muli, ang insert function na, at ang unang bagay na check ko para sa ay kung ang variable ang tinatawag na unang, na global variable ay null, ibig sabihin ay hindi naka-link na listahan. Hindi namin ipinasok ang anumang mga numero, kaya trivia sa isingit ang kasalukuyang numero sa listahan, dahil ito lamang nabibilang sa simula ng listahan. Kaya ito ay kapag Anita ay lamang nakatayo dito nag-iisa, nagpapanggap walang ibang tao ay dito sa entablado hanggang inilalaan namin ang isang node, maaaring siya itataas ang kanyang kamay sa unang pagkakataon, kung ang iba ay ay up sa entablado pagkatapos ng kanyang sa Lunes. Ngayon dito, ito ay isang maliit na check kung saan mayroon akong sasabihin kung sulit ang bagong node ng n <ang halaga ng n sa kasalukuyang unang node, ito ay nangangahulugan na may isang naka-link na listahan na nagsimula. May ng hindi bababa sa isang node sa listahan, ngunit ang bagong tao nabibilang bago ito, kaya kailangan namin upang ilipat ang mga bagay sa paligid. Sa ibang salita, kung ang listahan ay nagsimula sa pamamagitan lamang ng, sabihin nating, ang bilang 17, na ang - aktwal na, maaari naming gawin ito mas malinaw. Kung simulan namin ang aming mga kuwento na may isang pointer dito tinatawag na unang, at simula ito null, at namin ipasok ang numero 9, ang bilang 9 malinaw na nabibilang sa simula ng listahan. Kaya sabihin magpanggap na lang namin malloced address o numero ng 9 at ilagay ito dito. Kung ang una ay 9 sa pamamagitan ng default, ang unang sitwasyon na namin tinalakay ay nangangahulugan na natin ang puntong ito tao dito, iwanan ito bilang null, ngayon mayroon kaming ang bilang 9. Ang susunod na bilang na gusto naming upang ipasok ay 17. 17 nabibilang sa paglipas dito, kaya kami ay pagpunta sa gawin ang ilang mga lohikal na stepping sa pamamagitan ng. Kaya sabihin sa halip, bago gawin namin na, sabihin magpanggap na gusto naming ipasok ang numero 8. 

Kaya para sa alang-alang sa kaginhawahan, ako pagpunta upang gumuhit dito. Ngunit tandaan, malloc Maaaring ilagay ito sa pinaka-kahit saan. Ngunit para sa kapakanan ng drawing, makikita ko bang ilagay ito dito. Kaya magpanggap lamang ko na inilalaan ng node para sa bilang 8, null na ito ay sa pamamagitan ng default. Ano na ngayon ay mangyayari? Ang ilang mga bagay. Ginawa namin ang pagkakamaling ito sa yugto sa Lunes kung saan-update namin ang isang pointer tulad nito, pagkatapos ay ginawa ito, at pagkatapos namin inaangkin - naulila namin lahat tao sa entablado. Dahil Hindi mai - ang pagkakasunud-sunod ng mga pagpapatakbo dito ay mahalaga, dahil na namin ngayon ang nawala ito node 9 na uri ng lumulutang sa espasyo. Kaya ito ay hindi ang tamang diskarte sa Lunes. Muna namin upang gawin ang iba pa. Ang estado ng mundo ay ganito ang hitsura. Una, 8 ay inilaan. Ano ang gusto ng isang mas mahusay na paraan ng pagpasok 8? Sa halip ng pag-update na ito pointer sa unang, i-update ang isang ito dito sa halip. Kaya kailangan namin ng isang linya ng code na ito upang i-null na character sa isang aktwal na pointer na pagturo sa node 9, at pagkatapos ay maaari naming ligtas na baguhin unang upang ituro sa tao dito. Ngayon kami ay may isang listahan, sa naka-link na listahan, ng dalawang elemento. At ano ang aktwal na hitsura dito? Kung titingnan namin sa code, mapansin na nagawa ko ang eksaktong na. Ko ang sinabi newptr, at sa kuwentong ito, newptr ay na tumuturo sa ito tao. 

Kaya ipaalam sa akin gumuhit ng isa pang bagay, at ang dapat kong umalis ng kaunti pa sa room para sa. Kaya patawarin ang mga maliliit na maliit na guhit. Tao na ito ay tinatawag na newptr. Iyon ay ang variable na ipinahayag namin ng ilang linya nang mas maaga, sa linya - sa itaas 25. At ito na tumuturo sa 8. Kaya kapag sinabi ko newptr-> susunod, na ibig sabihin nito ay pumunta sa struct na tulis sa sa pamamagitan ng newptr, kaya dito tayo ay, pumunta doon. Pagkatapos arrow sinasabi na makuha ang susunod na field, at pagkatapos = ang sinasabi na ilagay kung ano ang halaga doon? Ang halaga na sa unang; kung ano ang halaga sa unang? Una ay pagturo sa node na ito, kaya na nangangahulugan na dapat ngayon ituro ito sa node. Sa madaling salita, kung ano ang hitsura kahit na isang katawa-tawa gulo sa aking sulat-kamay, kung ano ang isang simpleng ideya ng paglilipat ng mga arrow sa paligid ibig sabihin sa code na may lamang ito isang Liner. Iimbak ang kung ano ang sa unang sa susunod na patlang at pagkatapos ay i-update kung ano ay aktwal na ang unang. Natin sige at fast-forward sa pamamagitan ng ilan sa mga ito, at hanapin lamang sa pagpapasok ng buntot na ito sa ngayon. Ipagpalagay na ako makakakuha sa punto kung saan nakita ko na ang susunod na patlang ng ilang mga node null. At sa puntong ito sa kuwento, isang detalye na ako glossing sa paglipas ng na ipinakilala ko ang pointer ng isa pang dito sa linya 142, hinalinhan pointer. Mahalaga, sa puntong ito sa kuwento, sa sandaling ang listahan ay nakakakuha ng mahaba, Ko uri ng kailangang maglakad ang mga ito gamit ang dalawang daliri dahil kung pumunta ako masyadong malayo, tandaan sa isang solong-haba na listahan, hindi ka maaaring pumunta paurong. Kaya ito ideya ng predptr ang aking kaliwang daliri, at newptr - hindi newptr. Isa pang pointer na dito ang aking iba pang mga daliri, at ako lamang ang uri ng paglalakad sa listahan. Iyon ang dahilan kung bakit na umiiral. Ngunit ipaalam ay isinasaalang-alang lamang ng isa ng ang simple kaso dito. Kung ang susunod na field na pointer ay null, kung ano ang lohikal na implikasyon? Kung ikaw ay traversing ang listahan na ito at pindutin ang null pointer? Ikaw sa dulo ng listahan, at kaya ang code sa pagkatapos na ikabit ang ito isang karagdagang elemento ang uri ng ang intuitive na node na ang susunod na pointer ay null, kaya ito ay kasalukuyang null, at baguhin ang mga ito, bagaman, na ang address ng bagong node. Kaya lamang namin ang pagguhit sa code ang arrow na iginuhit namin sa entablado sa pamamagitan ng pagtataas ng kaliwang kamay ng isang tao. 

At kaso na iwagayway ko ang aking mga kamay sa sa ngayon, dahil lang sa tingin ko madaling mawala kapag ginagawa namin ito sa ganitong uri ng kapaligiran, ay check para sa pagpapasok ng sa gitna ang listahan. Ngunit lamang intuitively, kung ano ang kailangang mangyari kung gusto mong malaman kung kung saan ang ilang bilang nabibilang sa gitna mo ay maglakad ito na may higit sa isang daliri, higit sa isang pointer, malaman kung saan ito ay kabilang sa pamamagitan ng checking ang elemento <ang kasalukuyang, > Ang kasalukuyang, at sa sandaling mahanap ka ng lugar na iyon, pagkatapos ay mayroon kang upang gawin ito uri ng shell laro kung saan ililipat mo ang pointer sa paligid napaka maingat. At sagot na iyon, kung gusto mong i-dahilan sa pamamagitan ng sa bahay sa iyong sariling, kahulihan babagsak lamang sa mga dalawang linya ng code, ngunit ang pagkakasunud-sunod ng mga linya ay sobrang mahalaga. Dahil kung mong ilagay ang kamay ng isang tao at itataas ng ibang tao sa maling pagkakasunud-sunod, muli, maaari mong orphaning sa listahan. Upang ibuod higit pa conceptually, ang pagpapasok ng sa buntot ay medyo direkta. Ang pagpapasok ng sa ulo ay medyo direkta, ngunit kailangan mong i-update ang isang karagdagang pointer sa oras na ito pisilin numero 5 sa listahan dito, at pagkatapos ay ang pagpapasok ng sa gitna ay nagsasangkot ng higit pang pagsisikap, napaka-maingat na ipasok ang numero ng 20 sa tamang lokasyon nito, na kung saan ay sa pagitan ng 17 at 22. Kaya kailangan mong gawin ang isang bagay tulad ng bagong node 20 point sa 22, at pagkatapos, ang pointer kung saan node sa Kailangang ma-update huling? Ito ay 17, upang aktwal na ipasok ito. Kaya muli, makikita ko iliban ang aktwal na code para sa partikular na pagpapatupad. 

Sa unang tingin, isang maliit na napakalaki, ngunit ito ay talagang isang walang-katapusang loop na looping, looping, looping, looping, at paglabag sa lalong madaling mo pindutin ang null pointer, sa puntong maaari mong gawin ang mga kinakailangang pagpapasok ng. Ito, pagkatapos, ay kinatawan naka-link na listahan ng code sa pagpapasok ng. Na uri ng ng maraming, at ito nararamdaman tulad namin na malutas ang isang problema, ngunit ipinakilala namin ang isang buong iba pang isa. Lantaran, namin na ginugol ang lahat ng oras na ito sa malaking O at Ω at tumatakbo ang oras, sinusubukan upang malutas ang mga problema mas mabilis, at dito ay namin ang paglalaan ng isang malaking hakbang paurong, ito nararamdaman. At pa, kung ang layunin ay upang mag-imbak ng data, ito nararamdaman tulad ng Banal na Kopita, tulad ng sinabi namin sa Monday, ay talagang hindi upang mag-imbak ng mga bagay agad. 

Sa katunayan, ipagpalagay na ginawa namin isaisantabi naka-link na listahan para sa isang sandali at ipinakilala namin sa halip ang paniwala ng isang table. At sabihin lamang-isip ng isang talahanayan para sa isang sandali bilang isang array. Ito array at kasong ito dito ay may ilang 26 elemento, 0 sa pamamagitan ng 25, at ipagpalagay na kailangan mo ng ilang mga tipak ng imbakan para sa mga pangalan: Alice at Bob at Charlie at katulad. At kailangan kang ilang mga istraktura ng data upang mag-imbak ng mga pangalan. Well, maaari mong gamitin ang isang bagay tulad ng isang naka-link na listahan at maaari kang maglakad sa listahan pagpasok Alice bago Bob at Charlie pagkatapos Bob at iba pa. At, sa katunayan, kung nais mong makita ang code na tulad nang bilang isang bukod, malaman na sa list2.h, gawin namin ang eksaktong na. Hindi namin pumunta sa pamamagitan ng ang code na ito, ngunit ito ay isang variant ng unang halimbawa na introduces ng isa pang struct nakakita kami bago tinatawag na mag-aaral, at pagkatapos ay kung ano ang aktwal na nag-iimbak sa naka-link na listahan ay isang pointer sa istruktura ng mag-aaral kaysa sa isang simpleng maliit na integer, n. Kaya Napagtanto may code doon na nagsasangkot ng aktwal na mga string, ngunit kung ang layunin sa kamay ay talagang ngayon ay upang matugunan ang problema ng kahusayan, hindi magiging gandang kung kami ay bibigyan ng isang bagay na tinatawag na Alice, gusto naming upang ilagay sa kanya sa tamang lokasyon sa isang istraktura ng data, ito nararamdaman tulad ng gusto ito talagang magaling sa lamang na ilagay Alice, na ang pangalan nagsisimula sa A, sa unang lokasyon. At Bob, na ang pangalan nagsisimula sa B, sa ikalawang lokasyon. Sa pamamagitan ng isang array, o sabihin simulan ang pagtawag sa ito ng isang table, ng hash table sa na, maaari naming gawin eksakto na. Kung kami ay bibigyan ng isang pangalan tulad ng Alice, isang string tulad Alice, kung saan inilagay mo ang A-l-i-c-e? Kailangan namin ang ng hueristic. Kailangan namin ang isang function tumagal ng ilang input tulad ng Alice at ibalik ang isang sagot, "Ilagay Alice sa lokasyon na ito." At ito function, ito itim na kahon, na tinatawag na hash. 

Isang hash ay isang bagay na tumatagal ng isang input, tulad ng "Alice", at babalik sa iyo, karaniwan, ang numerong lokasyon sa ilang mga istraktura ng data kung saan Alice nabibilang. Sa kasong ito, ang aming hash ay dapat relatibong simpleng. Aming hash ay dapat sabihin, kung ikaw ay binibigyan ng "Alice", kung character na dapat kong pakialam tungkol sa? Ang unang isa. Kaya tumingin ako sa [0], at sinasabi ko kung ang [0] na character ay A, ibalik ang bilang 0. Kung B, bumalik 1. Kung ito ay C, bumalik 2, at iba pa. Lahat ng 0 index, at na ay magpapahintulot sa akin upang ipasok ang Alice at pagkatapos Bob at pagkatapos Charlie at iba pa sa istraktura ng data na ito. Ngunit may problema. Paano kung Anita ay kahabaan muli? Kung saan inilalagay namin ang Anita? Kanyang pangalan,, nagsisimula sa ang titik A, at pakiramdam ng tulad ng ginawa naming ang isang mas mas malaking gulo sa problemang ito. Namin ay mayroon na ngayong agarang pagpapasok ng, pare-pareho ang pagpapasok ng oras, sa isang istraktura ng data kaysa sa mas masahol pa-case linear, ngunit kung ano ang maaari naming gawin na may Anita sa kasong ito? Ano ang dalawang mga pagpipilian, talagang? Oo? [Estudyante sagot, hindi maintindihan] Okay, sa gayon ay maaari kaming magkaroon ng isa pang dimensyon. Iyon ay mabuti. Upang maaari naming bumuo ng mga bagay sa 3D tulad ng usapan natin ang tungkol pasalita sa Lunes. Namin maaaring magdagdag ng isa pang access dito, ngunit ipagpalagay na hindi, sinusubukan ko upang panatilihin ito simpleng. Ang buong layunin dito ay upang agarang pare-pareho-time na access, sa gayon ay pagdaragdag ng labis na kumplikado. Ano ang iba pang mga pagpipilian kapag sinusubukan upang ipasok ang Anita sa istrakturang ito ng data? Oo? [Estudyante sagot, hindi maintindihan] Magandang. Kaya kami maaaring ilipat ang iba, tulad ng Charlie nudges pababa Bob at Alice, at pagkatapos ay inilalagay namin Anita kung saan siya talagang nais na maging. 

Siyempre, ngayon, mayroong isang gilid na epekto ng mga ito. Ang data na ito istraktura ay maaaring kapaki-pakinabang hindi dahil gusto naming magpasok ng mga tao sa sandaling ngunit dahil gusto naming upang suriin kung ang mga ito doon mamaya kung gusto naming upang i-print ang lahat ng mga pangalan sa istraktura ng data. Kami ay pagpunta sa gawin ang isang bagay na may data na ito kalaunan. Kaya ngayon na namin ang uri ng screwed sa ibabaw ng Alice, na hindi na kung saan siya ay dapat na maging. Nor ay Bob, ni Charlie. Kaya marahil ito ay hindi tulad ng isang magandang ideya. Ngunit sa katunayan, ito ay isang pagpipilian. Namin shift ang lahat, o ano ba, Anita dumating late sa laro, bakit hindi namin lamang ilagay Anita hindi dito, hindi dito, hindi dito, sabihin lamang na ilagay ang kanyang ng kaunti mas mababa sa listahan. Ngunit ang problemang ito ay nagsisimula sa malipat muli. Na maaaring magawa upang makahanap ng Alice agad, batay sa kanyang pangalan. At Bob agad, at Charlie. Ngunit pagkatapos ay tumingin para sa Anita, at makikita mo, Hmm, Alice ay sa paraan. Well, hayaan mo akong tingnan sa ibaba Alice. Bob ay hindi Anita. Charlie ay hindi Anita. Oh, may Anita. At kung patuloy na tren ng logic ang lahat ng mga paraan, ano ang pinakamasama-case na oras ng paggana ng paghahanap o pagpasok ng Anita sa ang bagong istraktura ng data? Ito ay O (n), i-right? Dahil sa ang pinakamasama kaso, may Alice, Bob, Charlie. . . ang lahat ng mga paraan pababa sa isang pinangalanang "Y", kaya mayroon lamang isang lugar na natitira. Thankfully, mayroon kaming tinatawag na "Z", kaya namin ilagay Anita sa pinakailalim. 

Hindi namin talagang malutas ang problema na. Kaya siguro namin kailangan upang ipakilala ang ikatlong dimensyon. At ito ay lumiliko out, kung namin ipakilala ito ikatlong dimensyon, hindi namin maaaring gawin ito perpektong, ngunit ang Banal na Kopita ay na pagkuha ng pare-pareho-time pagpapasok ng at dinamikong mga pagpapasok kaya hindi namin sa hard-code ng isang hanay ng mga laki 26. Maaari naming ipasok ng maraming mga pangalan tulad ng gusto namin, ngunit sabihin ang aming 5-minutong break na dito at pagkatapos ay gawin na maayos. Ayos lang. Ako magse-set ang kuwento medyo artipisyal doon sa pamamagitan ng pagpili ng Alice at Bob at pagkatapos ng pagkatapos Charlie at pagkatapos Anita, na ang pangalan ay malinaw naman sumalungat sa Alice. Subalit ang tanong na namin natapos sa Lunes na may lamang kung paano maaaring magkatotoo ito na nais mong makakuha ng mga ganitong uri ng banggaan? Sa ibang salita, kung sinimulan namin upang gamitin ito sa hugis ng mga talaan na istraktura, na kung saan ay talagang isang array lamang, sa kasong ito ng 26 na lokasyon, kung ano kung ang aming mga input sa halip pantay na ipinamamahagi sa? Hindi artipisyal Alice at Bob at Charlie at David at iba pa ayon sa alpabeto, pantay ito ay ibinahagi sa paglipas ng A sa pamamagitan Z. 

Siguro makikita lang namin makakuha ng masuwerteng at hindi namin ay may dalawang Isang o dalawang B sa na may napakataas na posibilidad, ngunit bilang isang tao tulis out, kung namin heneralisado ang problemang ito at hindi gawin ang 0 sa 25 ngunit, sabihin nating, 0 pamamagitan ng 364 o 65, madalas na ang bilang ng mga araw sa isang tipikal na taon, at tinanong ang tanong, "Ano ang posibilidad na dalawang sa atin sa kuwartong ito ay may parehong kaarawan?" Ilagay ito ng isa pang paraan, sa kung ano ang ang posibilidad na ang dalawang sa atin ay may pangalan na nagsisimula sa A? Ang uri ng pinag-uusapan ay ang parehong, ngunit ang address na ito space, ang paghahanap na ito space, ay mas malaki sa kaso ng mga kaarawan, dahil mayroon kaming maraming higit pang mga araw sa taon kaysa sa mga titik sa alpabeto. Ano ang posibilidad ng isang banggaan? Well, maaari naming isipin ng mga ito sa pamamagitan ng pag-uunawa ng ang matematika ng kabaligtaran paraan. Ano ang posibilidad ng walang banggaan? Well, ito expression dito sabi na ano ang posibilidad kung may isang tao lamang sa kuwartong ito, na mayroon silang isang natatanging kaarawan? Ito ay 100%. Dahil kung mayroon lamang isang tao sa kuwarto, kanyang kaarawan ay maaaring maging anumang ng 365 araw ng taon. Kaya ng 365/365 na mga pagpipilian ay nagbibigay sa akin ang halaga ng 1. Kaya ang posibilidad na pinag-uusapan sa sandaling ito ay 1. Ngunit kung may pangalawang tao sa kuwarto, ano ang posibilidad na ang kanilang mga kaarawan ay naiiba? Mayroong lamang 364 posibleng mga araw, pagbalewala sa hakbang taon, para sa kanilang mga kaarawan ay hindi sumalungat sa ang iba pang mga tao. Kaya 364/365. Kung ang isang ikatlong tao ay sa, 363/365, at iba pa. Kaya panatilihin namin ang multiply nang magkasama ang mga fraction, na nakakakuha ng mas maliit at mas maliit, upang malaman kung ano ang posibilidad na ang lahat sa atin ay may natatanging mga kaarawan? Ngunit kami, siyempre, lamang na sagot at i-flip ang mga ito sa paligid at gawin ang 1 minus lahat ng na, isang expression na makikita namin kalaunan makakuha ng kung tandaan mo sa likod ng iyong mga libro sa matematika, ito mukhang isang maliit na bagay tulad nito, na kung saan ay mas madali kahulugan graphically. At ito graphic dito ay sa axis x ang bilang ng mga kaarawan, o ang bilang ng mga tao sa mga kaarawan, at sa y axis ay ang posibilidad ng isang tugma. At kung ano ito ay sinasabi ay na kung mayroon kang, sabihin nating, kahit, sabihin pumili ng isang bagay tulad ng 22, 23. Kung may 22 o 23 mga tao sa kuwarto, ang posibilidad na ang dalawang ng mga napaka-ilang mga tao ay pagpunta sa magkaroon ng parehong kaarawan talagang sobrang mataas, combinatorially. 50% logro na sa isang klase ng 22 tao lamang, seminar, halos, 2 ng mga tao ay pagpunta sa magkaroon ng parehong kaarawan. Dahil mayroong maraming mga paraan kung saan maaari kang magkaroon ng parehong kaarawan. Kahit na mas masahol pa, kung titingnan mo sa kanang bahagi ng tsart, ng oras na mayroon kang isang klase may 58 mag-aaral sa loob nito, ang posibilidad ng 2 tao na pagkakaroon ng kaarawan ay sobrang, sobrang mataas, halos 100%. Ngayon, na ang uri ng isang masaya katotohanan tungkol sa tunay na buhay. 

Ngunit ang mga implikasyon, ngayon, para sa mga data kaayusan at pag-iimbak ng impormasyon nangangahulugan na lamang ipagpalagay na mayroon kang gandang, malinis, unipormeng pamamahagi ng data at mayroon kang isang malaking sapat na array upang magkasya ang isang grupo ng mga bagay ay hindi nangangahulugan na ikaw ay upang makakuha ng mga tao sa natatanging lokasyon. Ay pagpunta sa may banggaan. Kaya ito paniwala ng hashing, dahil ito ay tinatawag na, pagsasagawa ng isang input tulad ng "Alice" at masahe ang mga ito sa ilang mga paraan at pagkatapos pagbalik ng sagot tulad ng 0 o 1 o 2. Pagbalik ilang output mula sa function na ay plagued sa pamamagitan ng ang posibilidad ng banggaan. Kaya kung paano namin pinangangasiwaan ang mga banggaan? Well, sa isang kaso, maaari naming ang ideya na iminungkahing. Maaari lang namin shift ang lahat, o marahil, ang kaunti pa lamang, sa halip na ilipat ang iba, sabihin lamang ilipat ang Anita sa ilalim ng mga magagamit na lugar. Kaya kung Alice sa 0, Bob sa 1, Charlie sa 2, namin lamang ilagay ang Anita sa lokasyon 3. At ito ay isang diskarte sa istraktura ng data na tinatawag linear probing. Linear dahil ka maigsing linya na ito, at ikaw ay uri ng probing para sa mga magagamit na mga spot sa istraktura ng data. Siyempre, ito devolves sa O (n). Kung ang istraktura ng data talagang buong, may 25 tao sa loob nito na, at pagkatapos Anita ay kasama, siya ay nagtatapos up sa kung ano ang magiging lokasyon Z, at na fine. Umaangkop pa rin siya, at maaari naming mahanap ang kanyang mamaya. 

Ngunit ito ay salungat sa layunin ng pagpapabilis ng mga bagay up. Kaya kung ano kung ipinakilala namin sa halip ikatlong dimensyon na ito? Na diskarte ay karaniwang tinatawag na nakahiwalay na chaining, o pagkakaroon ng mga chain. At kung ano ng hash table ngayon, ito sa hugis ng mga talaan na istraktura, iyong talahanayan ay isang array ng mga payo. Ngunit ano ang mga payo ay ituro sa hula kung ano? Ang isang naka-link na listahan. Kaya kung ano kung namin ang pinakamahusay ng parehong ng mga mundo? Ginagamit namin ang mga array para sa unang na-index sa istraktura ng data upang maaari namin agad pumunta sa [0] [1], [30] o iba pa, ngunit sa gayon ay mayroon kaming ilang mga kakayahang umangkop at maaari naming magkasya ang Anita at Alice at Adan at anumang iba ang pangalan, sa halip namin ipaalam sa iba pang mga axis palaguin mang. At hindi na namin sa wakas, bilang ng Lunes, na nagpapahayag na kakayahan sa naka-link na listahan. Maaari naming palaguin mang ang istraktura ng data. Bilang kahalili, maaari naming lamang gumawa ng isang malaking 2-dimensional array, ngunit na pagpunta sa isang kahindik-hindik na sitwasyon kung isa ng mga hilera sa isang 2-dimensional array ay hindi malaki sapat para sa dagdag na tao na may pangalan ang mangyayari sa magsimula sa A. Huwag sana naming reallocate isang malaking 2-dimensional na istraktura lamang dahil mayroong maraming mga taong may pangalang A, lalo na kapag may kaya ilang mga tao na may pangalang Z isang bagay. Lamang Ito ay pagpunta sa hiwa-hiwalay na istraktura ng data. Kaya hindi perpekto sa pamamagitan ng anumang mga pamamaraan, ngunit ngayon namin ng hindi bababa sa may kakayahang upang agad na makita kung saan Alice o Anita nabibilang, ng hindi bababa sa mga tuntunin ng vertical axis, at pagkatapos lang namin upang magpasya kung saan ilagay Anita o Alice sa naka-link na listahan. Kung hindi namin pakialam tungkol sa pag-uuri-uri ng mga bagay, kung gaano kabilis maaari kaming isingit Alice sa isang istraktura tulad nito? Pare-pareho ang oras. Ini-index namin sa [0], at kung mayroong walang, Alice pupunta sa simula ng na naka-link na listahan. Ngunit hindi iyon isang malaking deal. Dahil kung Anita pagkatapos ay kahabaan ilang bilang ng mga hakbang sa ibang pagkakataon, kung saan ay Anita nabibilang? Well, [0]. Oop. Alice ay sa na-link na listahan. 

Ngunit kung hindi namin pakialam tungkol sa pag-uuri-uri ng mga pangalan, maaari lamang namin ilipat Alice sa paglipas ng, insert Anita, ngunit kahit na pare-pareho ang oras. Kahit na may Alice at Adan at lahat ng iba pang mga A pangalan, hindi ito talagang paglilipat sa kanila pisikal. Bakit? Dahil lang namin ginawa dito sa naka-link na listahan, na nakakaalam ay mga node ay pa rin? Ang kailangan mong gawin ay ilipat ang mga crumbs ng tinapay. Ilipat ang mga arrow sa paligid, hindi mo na kailangang pisikal na ilipat ang anumang data sa paligid. Upang maaari naming magpasok ng Anita, sa kasong iyon, agad. Pare-pareho ang oras. Kaya kami ay may pare-pareho-time lookup, at pare-pareho-time na pagpasok ng isang tao tulad ng Anita. Ngunit ang uri ng oversimplifying ang mundo. Paano kung gusto namin mamaya upang mahanap ang Alice? Paano kung gusto namin mamaya upang mahanap ang Alice? Gaano karaming mga hakbang ay na pagpunta sa tumagal? [Estudyante sagot, hindi maintindihan] Eksakto. Ang bilang ng mga tao bago Alice sa naka-link na listahan. Kaya ito ay hindi pa perpekto, dahil ang aming istraktura ng data, muli, ay ang vertical access at pagkatapos ay may mga naka-link na listahan na nagha-hang - aktwal na, ipaalam sa ay hindi gumuhit ng isang array. Ito ang mga naka-link na listahan nakikipag-hang-off nito na mukhang isang maliit na bagay tulad nito. Ngunit ang problema ay kung Alice at Adan at lahat ng iba pang mga A pangalan humantong sa higit pa at higit pa doon, paghahanap ng isang tao ay maaaring pagkuha ng grupo ng mga hakbang, bcause mayroon kang pagbagtas sa naka-link na listahan, kung saan ay isang linear na pagpapatakbo. Kaya talagang, pagkatapos, ang pagpapasok ng oras sa huli ay O (n), kung saan ang n ay ang bilang ng mga elemento sa listahan. Hinati sa, sabihin mang tumawag ito m, kung saan ang m ay ang bilang ng mga naka-link na listahan na mayroon kami sa ito vertical axis. Sa ibang salita, kung ipinapalagay namin tunay unipormeng pamamahagi ng mga pangalan, lubos na hindi makatotohanang. Mayroong malinaw naman higit pa sa ilang mga titik kaysa sa iba. 

Ngunit kung ipinapalagay namin para sa ilang sandali ng isang unipormeng pamamahagi, at hindi na namin n kabuuang mga tao, at m kabuuang chain magagamit sa amin, ang haba ng bawat ng mga chain patas lamang ay ang kabuuang, n na hinati sa pamamagitan ng bilang ng mga chain. Kaya n / m. Ngunit narito ang kung saan maaari namin ang lahat ng mathematically matalino. m ay isang pare-pareho, dahil may isang nakapirming numero sa mga ito. Ka na idedeklara ang iyong array sa simula, at hindi namin ang pagbabago ng laki ng vertical axis. Sa pamamagitan ng kahulugan, na pananatili maayos. Lamang ang horizontal axis, kaya na magsalita, na pagbabago. Kaya technically, ito ay isang pare-pareho. Kaya ngayon, ang pagpapasok ng oras ay medyo magkano O (n). Kaya na hindi pakiramdam ang lahat ng na magkano ang mas mahusay. Ngunit ano ang katotohanan dito? Well, lahat ng oras na ito, para sa mga linggo, namin ang sinasabi O (n ²). O (n), 2 x n ², - n, na hinati sa pamamagitan ng 2. . . ech. Lang n ². Ngunit ngayon, sa bahaging ito ng semestre, maaari naming simulan ang pakikipag-usap tungkol sa tunay na mundo muli. At n / m ay ganap na mas mabilis kaysa lamang n nag-iisa. Kung mayroon ka ng isang libong mga pangalan, at masira ang mga ito sa maramihang mga bucket kaya na mayroon kang sampung pangalan lamang sa bawat isa sa mga chain, talagang naghahanap ng sampung bagay na mas mabilis kaysa sa isang libong mga bagay. At kaya isa ng paparating na mga set ng problema na hamunin ka mag-isip tungkol sa eksakto na kahit, oo, asymptotically at mathematically, ito ay pa rin lamang linear, na sucks sa pangkalahatan kapag sinusubukan upang mahanap ang mga bagay. Sa katotohanan, ito ay mas mabilis kaysa sa dahil sa ang panghati na ito. At kaya mayroong muli ito kalakalan-off at ito salungatan sa pagitan ng teorya at katotohanan, at isa ng ang knobs ay magsimulang i sa puntong ito sa semestre ay higit pa sa katotohanan isa namin ang uri ng maghanda para sa semster end, bilang namin ipakilala sa mundo ng web programming, kung saan talaga, ang pagganap upang mabilang dahil ang iyong mga gumagamit ay pagpunta sa magsimula sa pakiramdam at Pinahahalagahan ng mga mahihirap na desisyon disenyo. 

Kaya paano mo pumunta tungkol sa pagpapatupad ng isang naka-link na - ng hash table na may 31 mga elemento? At ang nakaraang halimbawa ay mang tungkol sa mga kaarawan. Kung ang isang tao ay may kaarawan ng Enero 1 o Pebrero 1, maglalagay kami ng mga ito sa bucket. Kung Enero 2, Pebrero 2, Marso 2, maglalagay kami ng mga ito sa bucket. Iyon ang dahilan kung bakit ito ay 31. Paano mo ipinapahayag ng hash table? Maaari itong medyo simple, node * talahanayan ay aking arbitrary pangalan para dito, [31]. Ito ay nagbibigay sa akin 31 pointer sa node, at na nagbibigay-daan sa akin upang 31 pointer sa naka-link na listahan kahit na mga chain simula null. Ano ang gusto kong ilagay kung gusto ko upang mag-imbak ng "Alice," "Bob," "Charlie"? Well, kailangan namin upang I-wrap ang mga bagay sa isang istraktura dahil kailangan namin Alice upang tumuro sa Bob, upang tumuro sa Charlie, at iba pa. Hindi lamang namin maaaring magkaroon ng pangalan ng nag-iisa, kaya maaari ba akong lumikha ng isang bagong istraktura na tinatawag na node dito. 

Ano ang isang aktwal na node? Ano ang isang node sa bagong na-link na listahan? Ang unang bagay, na tinatawag na salita, ay para sa pangalan ng tao. LENGTH, baka, nauugnay sa maximum na haba ng pangalan ng isang tao, anumang iyon ay, 20, 30, 40 character sa mga nakatutuwang mga kaso ng sulok, at mag-+1 para sa kung ano? Ang labis na character null, \ 0. Kaya node na ito ay wrapping "isang bagay" sa loob ng mismong, ngunit ito rin declares susunod na tinatawag na isang pointer upang maaari naming kadena Alice sa Bob sa Charlie at iba pa. Null ngunit hindi kinakailangan upang maging. Anumang mga katanungan sa mga hash na mga talahanayan? Oo? [Mag-aaral na humihiling sa tanong, hindi maintindihan] isang array - magandang tanong. Bakit ito magpasinda salita sa isang array sa halip na lamang magpasinda *? Ito medyo arbitrary Halimbawa, hindi ko gusto sa resort sa malloc para sa bawat isa sa mga orihinal na pangalan. Gusto ko na idedeklara ng isang maximum na halaga ng memory para sa string sa gayon na maaari kong kopyahin sa ang istraktura Alice \ 0 at hindi humarap sa malloc at libreng at ang mga tulad ng. Ngunit maaari kong gawin na kung gusto ko upang maging mas may malay-tao ng espasyo paggamit. Magandang tanong. Kaya sabihin subukan upang magbigay ng tuntuning panlahat ang layo mula sa at ituon ang natitira ngayon sa mga istraktura ng data sa mas pangkalahatang at iba pang mga problema na maaari naming malutas gamit ang parehong batayan kahit na ang data istraktura ay maaaring ang kanilang sarili-iba sa kanilang mga particular. 

Kaya ito lumiliko sa computer science, ang mga puno ay napaka-karaniwang. At maaari mong isipin ng isang puno uri ng tulad ng isang puno ng pamilya, kung saan may ilang mga Roots, ilang matriarch o apo, lola o grandpa o mas maaga bumalik, sa ilalim na ina at ama o iba't-ibang mga kapatid o ang gusto. Kaya ng mala-punong balangkas ay may node at ito ay may mga anak, karaniwang 0 o higit pang mga anak para sa bawat node. At ang ilan sa mga hindi maintindihang pag-uusap na nakikita mo sa larawan na ito dito anumang ng mga maliit na bata o Apo sa mga gilid na may walang arrow na emanating mula sa kanila, mga tinatawag na dahon, at sinuman sa loob ay isang panloob na node, maaari mong tawagin ang mga ito anumang kahabaan ng mga linya. Ngunit ang istraktura na ito ay medyo karaniwang. Isa na ito ng kaunti arbitrary. Mayroon kaming isang bata sa kaliwa, mayroon kaming tatlong mga bata sa kanan, dalawang bata sa ibaba ang natitira. Upang maaari naming ibang-sized na puno, ngunit kung simulan namin upang isunod sa pamantayan ng mga bagay, at maaari mong maalala muli ang mula sa Patrick ng video sa binary paghahanap mula sa isang nakaraang maikling online, binary paghahanap ay hindi ipinatupad sa isang array o mga piraso ng papel sa isang pisara. Ipagpalagay na nais mong iimbak ang iyong mga numero sa isang mas sopistikadong istraktura ng data. Maaari kang lumikha ng isang puno tulad nito. Maaari kang magkaroon ng isang node na ipinahayag sa C, at node na maaaring magkaroon ng hindi bababa sa dalawang mga elemento sa loob nito. Ay isa ang numero na nais mong iimbak, at ang iba pa ay - maayos, kailangan namin ng isa pang. Ang iba pang mga bata nito. Kaya narito ang isa pang data istraktura. Oras na ito, node ay tinukoy bilang pag-iimbak ng isang numero n at pagkatapos ay dalawang payo; kaliwa anak at kanang anak. At hindi arbitrary. Ano ang mga kawili-wiling tungkol sa puno? 

Ano ang pattern sa kung paano inilatag namin ang ito o kung paano inilatag Patrick ito sa kanyang video? Ito ay uri ng halata na may ilang mga pag-uuri sa pagpunta sa dito, ngunit kung ano ang simpleng panuntunan? Oo? [Estudyante sagot, hindi maintindihan] Perpekto. Kung ikaw sulyap sa, makikita mo ang mga maliit na numero sa kaliwa, malaking mga numero sa kaliwa, ngunit na totoo para sa bawat node. Para sa bawat node, kaliwang anak nito na mas mababa kaysa sa ito, at kanang anak nito na mas malaki kaysa ito. Ano ang ibig sabihin nito ay ngayon ay kung gusto ko upang maghanap ang istraktura ng data para sa, sabihin nating, ang bilang 44, Mayroon akong magsimula sa root, dahil bilang sa lahat ng mga mas kumplikadong kaayusan data ngayon, lamang namin ay isang pointer sa isang bagay, sa simula. At sa kasong ito, simula sa root. Ito ay hindi ang kaliwang dulo, ito ay ang root ng istraktura na ito. Kaya nakikita ko dito ang 55, at Naghahanap ako ng 44. Aling mga direksyon Gusto kong pumunta? Well, gusto kong pumunta sa kaliwa, dahil malinaw naman, sa kanan ay masyadong malaki. Kaya mapansin dito, ikaw ay ang uri ng conceptually pagpuputol tree sa kalahati dahil hindi ka kailanman pagpunta down sa kanang bahagi. Kaya ngayon ko pumunta mula sa 55 sa 33. Masyadong maliit ng isang numero. Naghahanap ako ng 44, ngunit ngayon alam ko kung 44 sa puno, maaari ba akong mag-malinaw naman sa kanan. Sa muli, ako pruning tree sa kalahati. Medyo mas magkakahawig conceptually sa aklat ng telepono. Ito ay katulad sa kung ano ang ginawa namin sa mga paper sa pisara, ngunit ito ay mas sopistikadong istraktura na nagbibigay-daan sa aktwal na sa amin upang gawin ito hatiin at lupigin sa pamamagitan ng disenyo ng algorithm, at sa katunayan, traversing isang istraktura tulad nito - Whoops. Traversing isang istraktura tulad nito, kung saan ito lamang "pumunta ang paraan na ito o pumunta na paraan," ay nangangahulugan na ang lahat ng code na Baluktot ang iyong isip sa unang kapag pagpapatupad ito sa seksyon o paglalakad sa pamamagitan nito sa bahay, para sa binary paghahanap, gamit ang recursion o pag-ulit, ito ay isang sakit sa ulo. Hanapin ang gitnang elemento, pagkatapos ay gawin ang iyong rounding pataas o pababa. 

May beauty na ito dahil na namin ngayon gamitin ang recursion muli, ngunit mas nang malinis. Sa katunayan, kung ikaw ay sa bilang 55 at gusto mong mahanap ang 44, pumunta ka pakaliwa sa kasong ito, kung ano ang mong gawin? Patakbuhin mo ang eksaktong parehong algorithm. Mong suriin ang halaga ng node, pagkatapos ay pumunta ka pakaliwa o pakanan. Pagkatapos mong suriin ang halaga ng node, pumunta sa kaliwa o kanan. Ito ay perpektong angkop sa recursion. Kaya kahit na sa nakalipas na namin nagawa mo na ang ilang mga medyo arbitrary halimbawa kinasasangkutan recursion na hindi kailangan na recursive, may stuctures data, lalo na puno, ito ay isang perpektong application ng ito ideya ng pagkuha ng isang problema, pag-urong ito, at pagkatapos paglutas ng ang parehong uri ng, ngunit mas maliit, programa. 

Kaya may isa pang istraktura ng data na maaari naming ipakilala. Ito ay dinisenyo sa unang tingin upang tumingin misteriyoso, ngunit ito ang mga kamangha-manghang. Kaya ito ay ang istraktura ng data na tinatawag trie, trie, na minana mula sa pagkuha ng salita, na hindi malinaw muling Subukan-Val, ngunit kung ano ang mundo ang tawag sa mga bagay na ito. Sinusubukan. T-r-i-e. Ito ay isang mala-punong balangkas ng uri, ngunit ang bawat isa ng ang mga node sa isang trie Lumilitaw na kung ano? At ito ay isang bit nakaliligaw na dahil ito uri ng dinaglat. Ngunit mukhang bawat node sa trie ay talagang isang array. At kahit na ang may-akda ng diagram na ito ay hindi ipinapakita ito, sa kasong ito, ang trie ito ay isang istraktura ng data na may layunin sa buhay ay upang mag-imbak ng mga salita tulad ng A-l-i-c-e o B-o-b. At ang paraan na kung saan ang data na ito tindahan Alice at Bob at Charlie at Anita at iba pa ay gumagamit ng isang array kung saan upang mag-imbak ng Alice sa isang trie, sisimulan namin sa root node na mukhang isang array, at ito ay nakasulat sa shorthand notation. May-akda ang mga tinanggal na abcdefg dahil walang mga pangalan na iyon. Sila lamang ay nagpakita M at P at T, ngunit sa kasong ito, sabihin ilipat ang layo mula sa Alice at Bob at Charlie sa ilang mga pangalan na dito. Maxwell ay talagang sa diagram. Kaya kung paano ginawa ng may-akda store M-a-x-w-e-l-l? Siya na nagsimula sa root node, at napunta sa [M], kaya halos 13, ang ika-13 na lokasyon sa array. Pagkatapos mula doon, ang isang pointer. Ang pointer na humahantong sa isa pang array. Mula doon, ang may-akda ang na-index sa array na sa isang lokasyon, bilang itinatanghal doon sa itaas na kaliwang, at pagkatapos siya sinundan na pointer sa isa pang array, at nagpunta sa pointer sa lokasyon X. Pagkatapos ay sa ang susunod na lokasyon array W, E, L, L, at iba pa, at sa wakas, sabihin aktwal subukang maglagay ng larawan na ito. Ano ang isang node itsura sa code? Ang node sa isang trie ay naglalaman ng isang array ng mga payo sa higit pang mga node. Subalit mayroong ding nakuha sa ilang mga uri ng boolean na halaga, ng hindi bababa sa pagpapatupad na ito. Mangyayari kong tumawag ito is_word. Bakit? Dahil kapag ikaw ay pagpasok Maxwell, hindi ka pagpasok anumang bagay sa ito istraktura ng data. Hindi mo ay sumusulat ng M. Hindi mo ay sumusulat X. Lahat ng iyong ginagawa ng pagsunod sa mga payo. Ang pointer na kumakatawan M, pagkatapos ang pointer na kumakatawan A, pagkatapos pointer na kumakatawan X, pagkatapos W, E, L, L, ngunit kung ano ang kailangan mong gawin sa dulo uri ng pumunta, suriin, naabot ko ang lokasyon na ito. Nagkaroon ng isang salita na nagtatapos dito sa istraktura ng data. 

Kaya kung ano ang trie isang talaga puno ng at may-akda ng pinili upang kumatawan mga terminuses na may kaunti triangles. Ito lamang ay nangangahulugan na ang katunayan na ang tatsulok na ito ang dito, ito boolean na halaga ng tunay na ay nangangahulugan na kung pumunta ka pabalik sa tree, na ay nangangahulugan na ang isang salita na may pangalang Maxwell sa. Ngunit ang salita ng foo, halimbawa, ay hindi sa tree, dahil kung sisimulan ko sa root node up dito sa itaas, Walang f pointer, walang o pointer, walang o pointer. Foo ay hindi isang pangalan sa diksyunaryo. Ngunit sa pamamagitan ng kaibahan, ang turing, t-u-r-i-n-g. Muli, hindi ko-imbak t o u o r o i o n o g. Subalit ko ginawa store sa istraktura ng data ng halaga ng tunay na paraan pababa dito sa node na ito - sa tree sa pamamagitan ng pagtatakda ng ito boolean na halaga ng is_word sa true. Kaya trie isang uri ng lubhang kawili-wili meta istraktura, kung saan hindi ka talaga sa pag-iimbak ng mga ang mga salita ang kanilang sarili para sa ganitong uri ng diksyunaryo. Upang maging malinaw, ka sa pag-iimbak ng oo o hindi, may isang salita na nagtatapos dito. 

Ngayon kung ano ang implikasyon? Kung mayroon kang 150,000 salita sa isang diksyunaryo na sinusubukan upang mag-imbak sa memorya gamit ang isang bagay tulad ng isang naka-link na listahan, ikaw ay pagpunta sa 150,000 node sa iyong listahan ng naka-link. At paghahanap ng isa ng mga salitang iyon sa alpabeto O (n) na oras. Linear oras. Ngunit sa kaso dito ng isang trie, ano ang oras ng paggana ng paghahanap ng salita? Ito lumiliko ang beauty dito ay na kahit kung mayroon kang 149,999 salita na ito diksyunaryo, tulad ng ipinatupad gamit ang istraktura ng data, kung gaano karaming oras aabutin upang mahanap o magpasok ng isa pang tao sa na, tulad Alice, Alice? Well, lamang 5, siguro 6 na hakbang para sa sumusunod na karakter. Dahil ang presense ng iba pang mga pangalan sa istraktura ay hindi makakuha ng sa paraan ng pagpasok Alice. Bukod dito, ang paghahanap ng Alice sa sandaling may mga 150,000 salita sa diksyunaryo hindi makakuha sa iyong paraan ng paghahanap ng Alice sa lahat, dahil Alice ay. . . . . dito, dahil nakita ko ang isang boolean na halaga. At kung walang boolean totoo, pagkatapos Alice ay hindi sa istraktura ng data na ito ng mga salita. Sa ibang salita, ang oras ng paggana ng paghahanap ng mga bagay at pagpasok ng mga bagay sa ang bagong data ng istraktura ng trie O ng - hindi ito n. Dahil ang presense ng 150,000 tao ay walang epekto sa Alice, tila. Kaya sabihin tumawag ito k, kung saan k sa maximum na haba ng isang salita sa Ingles na kung saan ay karaniwang hindi hihigit sa 20-isang bagay na character. Kaya k ay patuloy. Kaya ang Banal na Kopita tila namin natagpuan ngayon ay ng isang trie, pare-pareho ang oras para sa mga insert, para sa mga lookup, para sa pagtanggal. Dahil ang bilang ng mga bagay na sa istraktura, na hindi kahit na pisikal doon. Muli, sila-uri-uriin ng tsek, oo o hindi, ay walang epekto sa nito sa hinaharap tumatakbo oras. 

Ngunit mayroong nakuha sa isang catch, kung hindi man, hindi namin maaaring nasayang kaya karaming oras sa lahat ng mga iba pang mga istraktura ng data sa wakas makakuha ng sa lihim na kamangha-manghang. Kaya kung ano ang presyo ay namin ang pagbabayad dito upang makamit ang kadakilaan? Space. Ang bagay na ito ay napakalaking. At ang dahilan na ang mga may-akda ay hindi ipakita ito dito, mapapansin na ang lahat ng mga bagay na ito na hitsura array, hindi siya gumuhit ang natitirang bahagi ng puno, ang iba ng trie, dahil hindi nila lang hindi nauugnay sa kuwento. Ngunit ang lahat ng mga node ay sobrang malawak, at tumatagal ng hanggang ang bawat node sa tree 26 o aktwal, 27 character dahil sa kasong ito ako ay kabilang ang espasyo para sa kudlit sa gayon na maaaring namin may apostrophized salita. Sa kasong ito, ang mga ito ang mga malawak na array. Kaya kahit na hindi sila picutured, ito tatagal ay isang napakalaking halaga ng RAM. Na maaaring fine, especilly sa modernong hardware, ngunit ang tradeoff. Makakakuha tayo ng mas kaunting oras sa pamamagitan ng paggastos ng mas maraming espasyo. Kaya kung saan ay ang lahat ng pagpunta? Well, sabihin gawin - sabihin makikita dito. Natin gawin ng pagtalon sa tao na ito dito. 

Maniwala ka man o hindi, ng mas maraming masaya bilang C ay para sa ilang oras na ngayon, kami ay maabot ang punto sa semestre kung saan ito ay oras upang lumipat sa mga bagay na mas makabago. Mga bagay sa isang mas mataas na antas. At kahit na para sa susunod na ilang mga linggo pa rin namin patuloy na malulong ating sarili sa mundo ng mga payo at pamamahala ng memory upang makakuha ng na ginhawa na kung saan maaari naming pagkatapos ay bumuo sa, huli sa pagtatapos ng laro ay upang ipakilala, ironically, hindi na ito wika. Susubukan naming gastusin, tulad ng 10 minuto pakikipag-usap tungkol sa HTML. Lahat ng HTML ay isang markup language, at kung ano ang isang markup language ay mga serye ng mga bukas na mga braket at closed bracket na nagsasabing 'gumawa ito bold' 'Ito italics' 'gumawa ito Iginitna.' Ito ay hindi lahat na intellectually kawili-wili, ngunit ito ay sobrang kapaki-pakinabang. At ito ay tiyak na nasa lahat ng dako mga araw na ito. Ngunit ano makapangyarihang tungkol sa mundo ng HTML, at web programming mas pangkalahatang, ay pagbuo ng mga dynamic na bagay; pagsusulat code sa mga wika tulad ng PHP o Python o Ruby o Java o C #. Talagang, anumang ang iyong wika ng pagpili, at pagbuo ng HTML dynamic. Bumubuo ng isang bagay na tinatawag CSS dynamic. Cascading style sheet, na kung saan ay tungkol din sa aesthetics. At kaya kahit, ngayon, kung pumunta ako sa ilang mga website tulad ng sa pamilyar Google.com, at pumunta ako upang tingnan, developer, ang pinagmulan ng pagtingin, na maaaring nagawa mo na bago, ngunit upang tingnan ang pinagmulan, ang mga bagay na ito ay marahil hitsura medyo misteriyoso. Ngunit ito ay ang kalakip na code na ipinapatupad Google.com. Sa front end. At aktwal na ang lahat ng ito ay malambot aesthetics bagay. Ito ay CSS dito. Kung panatilihing ako ng scroll down na namin ang ilang mga kulay-code na mga bagay-bagay. Ito ay HTML. Hitsura ng code ng Google tulad ng isang gulo, ngunit kung ako aktwal na magbukas ng ibang window, maaari naming makita ang ilang mga istraktura na ito. Kung buksan ko ito up, mapapansin dito, ng kaunti pa nababasa. Kami ay pagpunta upang makita bago mahaba ang tag na ito, [salita] ng tag, HTML, ulo, katawan, div, script, text area, span, Iginitna, div. At ito ay din ayusin ng misteriyoso-mukhang sa unang tingin, ngunit ang lahat ng ito gulo sumusunod ilang mga pattern, at repeatable pattern, kaya na sa sandaling makuha namin ang mga pangunahing kaalaman, magagawa mong upang isulat ang code tulad nito at pagkatapos ay manipulahin ng code tulad nito gamit ang isa pang wika, na tinatawag JavaScript. At JavaScript ay isang wika na tumatakbo sa loob ng isang browser ngayon na ginagamit namin sa Harvard kurso, para sa tool ng shopping ng kurso na mga mapa ng Google ay gumagamit ng upang bigyan ka ng buong bungkos ng dynamism, Facebook ay nagbibigay sa iyo upang ipakita ang mga instant na update sa katayuan, Twitter gumagamit upang ipakita sa iyo ng mga tweet agad. Lahat ng ito magsisimula kami sa malulong ating sarili. Ngunit upang makakuha ng doon, kailangan namin upang maunawaan ang isang maliit na isang bagay tungkol sa Internet. Ang clip na ito dito lamang ng isang minuto ang haba, at sabihin ipinapalagay sa ngayon ito ay, sa katunayan, kung paano ang Internet ay gumagana bilang isang teaser para sa kung ano ang tungkol sa darating. Bigyan mo ako "Warriors ng Net." 

[♫ Mabagal koro musika ♫] [Lalaki tagapagsalaysay] Siya ay dumating na may isang mensahe. May isang protocol na lahat ng kanyang sariling. [♫ Mas mabilis electronic musika ♫] Dumating siya sa isang mundo ng mga cool na firewall, uncaring router, at mga panganib malayo mas masahol pa kaysa sa kamatayan. Siya ay mabilis. Siya ay malakas. Siya TCP / IP, at siya nakuha iyong address. Mandirigma ng Net. [Malan] Sa susunod na linggo, pagkatapos. Sa Internet. Web programming. Ito ay CS50. [CS50.TV]