[MUSIC nagpe-play] 

[Playback ng video] 

-Siya Ay nakahiga. 

-Tungkol saan? 

-Hindi Ko alam. 

-Kaya Kung ano ang alam namin? 

-na Sa ganap na 9:15, Ray Santoya ay sa ATM. -Yeah. Kaya ang tanong ay, kung ano ang ang ginagawa niya sa 9:16? 

-Shooting Ang 9 milimetro sa isang bagay. Siguro nakita niya ang sniper. 

-O Ay nagtatrabaho sa kanya. 

-Maghintay. Bumalik isa. 

-Ano ang nakikita mo? 

-Bring Kanyang mukha up full screen. 

-Ang Kanyang baso. 

-Mayroong Isang pagmuni-muni. 

-Ito Ay ang koponan ng baseball Nuevitas. Iyon ang kanilang logo. 

-At Ang pakikipag-usap niya sa kung sinuman ang may suot na jacket. 

[END playback] 

David MALAN: Lahat ng karapatan. Ito ay CS50 at ito ay medyo mas ng [hindi marinig] na kung saan ikaw ay dabbling sa hanay ng problema apat. Ngayon namin simulan upang tumingin ng kaunti pa malalim sa mga bagay na ito na tinatawag na mga payo, na kahit na ito ay isang pretty arcane topic, ito ay lumiliko out na ito ay pagpunta na ang paraan kung saan tayo maaari simulan ang pagbuo at assembling higit na mas sopistikadong mga programa. Pero ginawa namin ito sa huling Miyerkules sa pamamagitan ng paraan ng ilang claymation unang. Kaya ito, pagpapabalik, ay Binky at ginagamit namin siya upang tingnan ang isang programa na ay hindi talagang gawin kagiliw-giliw na kahit ano, ngunit ito ay magbunyag ng ilang mga problema. Kaya upang simulan ang araw na ito, kung bakit hindi namin maglakad mabilis sa pamamagitan ng ilang sa mga hakbang na ito, subukan upang distill sa mga tuntunin ng tao ni kung ano mismo ang nangyayari sa dito at kung bakit ito ay masama, at pagkatapos ay ilipat sa at talagang simulan ang paggawa ng isang bagay sa diskarteng ito? Kaya ang mga ito ay ang unang dalawang linya sa programang ito at sa mga tuntunin ng karaniwang tao, kung ano ang ginagawa ito ng dalawang mga linya? May isang tao kung sino ang makatwirang maginhawa sa kung ano ang ipinahayag sa screen? Ano ang mga ito ng dalawang linya ng paggawa? Ito ay hindi lahat na naiiba mula sa isang linggo, ngunit may ilang bagong mga espesyal na simbolo. Oo? Bumalik doon. 

Madla: pagdeklara ng payo? David MALAN: Sabihing muli? Madla: pagdeklara ng payo? David MALAN: Ang pagdeklara ng payo at pinuhin ang mga ito ng isang maliit na kaunti pang ipaalam. Madla: [hindi marinig] address x at pagkatapos ay y. David MALAN: At pagkatapos ay address. Kaya partikular kung anong ginagawa namin ay deklarasyon kami ay dalawang variable. Ang mga variable, bagaman, ay pagpunta na ng uri int star, na kung saan higit na partikular ay nangangahulugan sila ay pagpunta sa tindahan ang address ng isang int, ayon sa pagkakabanggit, x at y. Ngayon ay may anumang mga halaga? Mayroon bang anumang mga aktwal na mga address sa mga dalawang variable sa puntong ito sa oras? Hindi. Ito lang ang mga tinatawag na mga halaga ng basura. Kung hindi mo talaga magtalaga ng isang variable, anumang ay sa RAM dati ay pagpunta upang punan na may mga zero at pareho ng mga variable na iyan. Ngunit kami ay hindi pa alam ano ang mga ito at na ang magiging susi sa kung bakit Binky nawala ang kanyang ulo noong nakaraang linggo. 

Kaya ito ay ang claymation pagkakatawang-tao ng mga ito kung saan ikaw ay may mga variable ay dalawa lamang, maliit na bilog na piraso ng putik, na maaaring tindahan ng variable, ngunit bilang Iminumungkahi ang mga abala arrow, hindi sila ay tunay na tumuturo sa kahit saan kilala per se. Kaya pagkatapos namin ang linyang ito, at ito ay bago sa nakaraang linggo, malloc para sa memory laang-gugulin, na kung saan ay lamang ng isang magarbong paraan ng pagsabi ng operating system, Linux o Mac OS o Windows, hey, bigyan ako ng ilang memory, at ang kailangan mo upang sabihin sa mga operating system ay kung ano kapag humihingi ito para sa memory. Ito ay hindi pagpunta sa pag-aalaga kung ano ang ikaw ay pagpunta sa gawin sa mga ito, ngunit kailangan mong gawin upang sabihin sa mga operating sistema kung ano ang sa pamamagitan ng paraan ng malloc. Oo? 

Madla: Magkano? David MALAN: Magkano? Magkano sa bytes, at sa gayon, ito, muli, isang contrived halimbawa, sinasabi lang, bigyan ako ang laki ng isang int. Ngayon, ang laki ng isang int ay apat na bytes o 32 bits. Kaya ito ay isang paraan ng na nagsasabi, hey, operating system, bigyan ako ng apat na bytes ng memory na maaari kong gamitin sa aking itapon, at partikular, kung ano ang ginagawa malloc return na may paggalang sa na tipak ng apat na bytes? Madla: Address? David MALAN: Ang address. Ang address ng na tipak ng apat na bytes. Mismong. At kaya na kung ano ang naka-imbak sa huli sa x at iyon ang dahilan kung bakit hindi namin talagang aalaga kung ano ang bilang ng mga na address ay, kung ito ay OX1 o OX2 o ilang misteryosong hexadecimal address. Pinapahalagahan namin lamang pictorially na x na variable ay ngayon tumuturo sa na tipak ng memory. Kaya ang arrow ay kumakatawan sa isang pointer, o higit na partikular, ang isang memory address. Ngunit muli, hindi namin kadalasang pinapahalagahan kung ano ang mga tunay na mga address ay. Ngayon, sinasabi ang linyang ito ano sa mga tuntunin ng karaniwang tao? Star x nakakakuha ng 42 semicolon. Ano ang ibig sabihin nito? Gusto mong pumunta? Huwag scratch iyong leeg. 

Madla: Ang address ng x ay nasa 42. 

David MALAN: Ang address ng x ay 42. Hindi masyado. Kaya malapit, ngunit hindi pa, dahil mayroong ang bituin na prefixing ito x. Kaya kailangan namin upang mag-tweak ng kaunti. Oo? 

Madla: Ang halaga na ang pointer x ay tumuturo sa ay 42. David MALAN: OK. Ang halaga na ang pointer x ay tumuturo sa, sabihin nating, ay magiging 42, o maglagay ng isa pang paraan, ang star x sabi, pumunta sa kahit anong address ay nasa x, maging ito man ay 1 Oxford Street o 33 Oxford Street o OX1 o ox33, ano man na numeric address ay, star x ay ang dereferencing ng x. Kaya pumunta sa address na iyon at pagkatapos ay ilagay ang numero ng 42 doon. Kaya na ay magiging isang katumbas paraan ng pagsasabi na. Kaya na ang lahat ng multa at pagkatapos ay Gusto namin ang kumakatawan sa mga larawan sumusunod na kung saan namin nagdagdag ang 42 na na tipak ng apat bytes sa kanang gilid, ngunit ang linyang ito ay kung saan nagpunta ang mga bagay magkagulo at tumuloy Binky pop off sa puntong ito, dahil masamang bagay na mangyayari kapag mong dereference mga halaga ng basura o ikaw dereference hindi balidong payo, at sinasabi ko hindi balidong dahil sa puntong ito sa mga kuwento, ano ang nasa loob ng y? Ano ang halaga ng y batay sa nakalipas na ilang mga hakbang? Oo? Ano yan? 

Madla: Isang address. David MALAN: Isang address. Ito ay dapat na isang address ngunit initialize ko ito? Kaya hindi pa ako. Kaya kung ano ay kilala na maging doon? Ito lamang ang ilang mga halaga ng basura. Ito ay maaaring maging anumang mga address mula sa zero sa 2 bilyon kung mayroon kang dalawang gig ng RAM, o zero na 4 na bilyon kung na sa iyo Nakakuha apat na gigabytes ng RAM. Ito ay ilang mga halaga ng basura, ngunit ang problema ay na ang mga operating system, kung hindi ito ay nagbigay sa iyo na tipak ng memorya na sadyang na sinusubukan mong pumunta sa, pangkalahatan ito ay pagpunta sa maging sanhi ng kung ano ang nasaksihan namin bilang segmentation fault. Kaya sa katunayan, ang sinuman sa inyo na magkaroon ng nahirapan sa mga problema sa oras ng opisina o sa mga problema na mas Sa pangkalahatan ay may sinusubukan mong malaman ng segmentation fault, na karaniwan ay nangangahulugan ka ng pagpindot ng isang segment ng memory na hindi mo dapat. Ikaw ay pagpindot ng memorya na ang mga operating system ay hindi pinapayagan ka na hawakan, kung ito ay sa pamamagitan ng pagpunta masyadong malayo sa iyong array o simula ngayon, kung ito ay dahil ikaw ay pagpindot memory na lamang ay ang ilang mga halaga ng basura. 

Kaya ginagawa star x dito ay uri ng hindi natukoy na pag-uugali. Hindi ka dapat gawin ito dahil logro ay, ang programa lang ang pagpunta sa crash, dahil ikaw ay nagsasabi, pumunta sa address na ito at wala kang mga ideya kung saan address na talagang. Kaya ang operating system ay malamang pagpunta sa crash ang iyong programa bilang isang resulta at sa katunayan, iyon kung ano ang nangyari doon sa Binky. Kaya sa huli, Binky naayos ito problema sa mga ito. Kaya programa na mismo ay flawed. Ngunit kung ikaw uri ng sumulong at sa halip na maipatupad ang linyang ito, y katumbas x lamang nangangahulugan na anumang address ay isang x, ilagay din ito sa y. 

At kaya pictorially, na namin kinakatawan sa dalawang arrow mula sa x at mula y pagturo sa parehong lugar. Kaya semantically, x ay katumbas sa y dahil pareho ng mga ay nag-iimbak ang parehong address, samakatuwid tumuturo sa 42, at ngayon, kapag sinabi mong star y, pumunta sa address sa y, na ito ay may isang kagiliw-giliw na epekto. Kaya ang address sa y ay ang parehong bagay tulad ng address sa x. Kaya kung sabihin mo pumunta sa address sa y at baguhin ang halaga sa 13, sino pa ang apektado? X ay, point D, kaya na magsalita, dapat maaapektuhan rin. 

At sa katunayan, kung gaano Drew Nick ang larawang ito sa claymation ay eksakto na. Kahit na sundin namin ang pointer y, napunta kami sa parehong lugar, at iba kung tayo ay upang i-print out x o pointee y ni, pagkatapos ay namin makita ang halaga na 13. Ngayon, sinasabi ko pointee na maging pare-pareho sa video. Programmer, sa aking kaalaman, hindi talaga sabihin ang salita pointee, na kung saan ay tulis sa, ngunit para sa pagkakapare-pareho may mga video, mapagtanto na ang lahat na noon ay sinadya sa na sitwasyon. Kaya ang anumang mga katanungan sa claymation o payo o malloc pa lang? Hindi? Lahat tama. 

Kaya nang walang karagdagang ado, sabihin kumuha ng isang pagtingin sa kung saan ito ay may tunay na ito ay ginagamit para sa ilang oras. Kaya mayroon kaming ito CS50 library na nakuha ang lahat ng mga function. Ginamit namin ang GetInt ng maraming, GetString, marahil GetLongLong mas maaga sa aking Pset isa o kaya, ngunit kung ano ang aktwal na nangyayari? Well, sabihin kumuha ng isang mabilis na pagtingin ilalim ng hood sa isang programa na binibigyang inspirasyon kung bakit namin sa iyo ang CS50 library, at sa katunayan bilang ng nakaraang linggo, sinimulan namin ang pagkuha ng mga training wheels off. Kaya ito ay inayos ngayon ng isang postmortem ng kung ano ang may na-pagpunta sa sa loob ng CS50 library, kahit na ngayon ay magsisimula kami sa paglipat ang layo mula sa mga ito para sa karamihan ng mga programa. 

Kaya ito ay isang programa na tinatawag na scanf 0. Ito ay sobrang short. Ito lamang ay may mga linyang ito, ngunit ito nagpapakilala ng isang function na tinatawag na scanf na aktwal na kami ay pagpunta upang makita sa sa isang sandali sa loob ng CS50 library, kahit na sa isang bahagyang kakaibang paraan. Kaya ang program na ito sa 16 na linya ay deklarasyon ng variable x. Kaya bigyan ako ng apat na bytes para sa isang int. Ito ay nai-nagsasabi sa user, number please, at pagkatapos ay ito ay isang kagiliw-giliw na linya na talagang relasyon magkasama noong nakaraang linggo at ito. Scanf, at pagkatapos ay mapapansin ito ay tumatagal ng format string, tulad ng printf, % i nangangahulugang isang int, at pagkatapos ay tumatagal ito ng isang pangalawang argumento na kamukha ng kaunti funky. Ito ay ampersand x, at sa pagpapabalik, lamang nakita namin ito nang isang beses noong nakaraang linggo. Ano ang ampersand x kumakatawan? Ano ang ampersand gawin sa C? Oo? 

Madla: Ang address ng. David MALAN: Ang address ng. Kaya ito ay ang kabaligtaran ng star operator, samantalang ang star operator sabi, pumunta sa address na ito, ang mga ampersand operator sabi, malaman kung ang address ng variable na ito, at sa gayon ito ay susi, dahil layunin scanf sa buhay ay upang i-scan ng gumagamit input mula sa keyboard, depende sa anumang siya mga uri, at pagkatapos ay basahin ang input ng user na iyon sa isang variable, ngunit hindi namin nakita sa nakalipas na dalawang linggo na na swap function na tayo Sinubukan walang kahirap-hirap na ipatupad ay nasira lamang. Alalahanin na may swap function, kung ipinahayag lang namin ng A at B bilang ints, Matagumpay namin ginawa swap ang dalawang variable sa loob ng swap gusto lang na may gatas at OJ, ngunit sa lalong madaling swap ibinalik, ano ang naging resulta na may paggalang sa x at y, ang orihinal na halaga? Wala. Oo. Walang nangyari oras na iyon, dahil swaps baguhin lamang nito sa mga lokal na mga kopya, na ang ibig sabihin, ang lahat ng oras na ito, sa tuwing hindi namin tinanggal ang pagpasa sa mga argumento sa mga pag-andar, hindi namin pagpasa lamang ng mga kopya ng mga argumento. Maaari mong gawin sa mga na kahit anong gusto mo sa kanila, pero ang mga ito ay pagpunta sa may walang epekto sa mga orihinal na halaga. Kaya ito ay may problema kung ikaw ay gusto mong magkaroon ng isang function tulad ng scanf sa buhay, na ang layunin ay upang i-scan input ng user mula sa mga keyboard at pagkatapos ay punan ang mga patlang, kaya na magsalita, iyon ay, magbigay ng isang variable tulad ng x ang halaga, dahil kung ako ay upang pumasa lamang x sa scanf, kung isinasaalang-alang mo ang logic ng huling linggo, maaari scanf gawin ang anumang nais may isang kopya ng x, ngunit hindi ito maaaring permanenteng baguhin x maliban kung bigyan namin scanf isang mapa ng kayamanan, kaya na magsalita, kung saan ang x ay minamarkahan ang lugar, kung saan ang ipasa namin sa address ng x sa gayon ay scanf maaaring pumunta doon at talagang pagbabago ang halaga ng x. At kaya nga, ang lahat ng na ang programang ito ay kapag gumawa ako scanf 0, sa aking pinagmulan Directory 5M, gumawa scanf 0, dot slash scanf, numero mangyaring 50, salamat para sa 50. 

Kaya ito ay hindi lahat na kawili-wili, ngunit kung ano ang talagang nangyayari ay na sa lalong madaling ang tawag ko scanf dito, ang halaga ng x ay tuluyang binago. Ngayon, ito ay tila magandang at mabuti, at katunayan sa, ito Tila tulad ng hindi mo talagang kailangan namin CS50 library sa lahat ng anymore. Halimbawa, sabihin tumakbo ipaalam isang beses pa ito dito. Hayaan akong muling buksan ito para sa isang segundo. Subukan natin ang isang bilang Hayaan mangyaring at sa halip na sabihing 50 tulad ng dati, sabihin lang no. OK, na ang isang maliit na kakaiba. SIGE. At lamang ng ilang mga bagay na walang kapararakan dito. Kaya ito ay hindi mukhang hawakan maling sitwasyon. Kaya kailangan namin upang Minimally start pagdagdag ng ilang mga error-checking tiyakin na ang gumagamit ay may nai-type sa isang aktwal na numero tulad ng 50, dahil tila type ng mga salita ay hindi nakita bilang katiyakan, ngunit ito marahil ay dapat na. 

Tingnan natin ang bersyon na ito ngayon na ang Ipaalam aking mga pagtatangka upang reimplement GetString. Kung mayroon ng lahat na ito scanf functionality built in, bakit kami ay dabbling sa mga gulong ng pagsasanay tulad ng GetString? Well, dito ay marahil ang aking sariling simpleng bersyon ng GetString kung saan ang isang linggo na ang nakakaraan, ay maaaring magkaroon ng sinabi ko, bigyan ako ng isang string at tawagan ito buffer. Ngayon, ako pagpunta sa simulan lamang sinasabi char star, na kung saan, pagpapabalik, ito lamang ay magkasingkahulugan. Mukhang scarier ngunit ito ay ang eksaktong parehong bagay. Kaya bigyan ako ng variable na tinatawag na buffer ng isang na ang pagpunta sa tindahan ng isang string, sabihin ang string user po, at pagkatapos, tulad lamang ng dati, Subukan nating humiram ng araling ito ipaalam scanf % s oras na ito at pagkatapos ay pumasa sa buffer. Ngayon, ang isang mabilis katinuan suriin. Bakit hindi ko sinasabi ampersand buffer oras na ito? Magpakilala mula sa nakaraang halimbawa. Madla: Pansamantalang trabaho star ay isang pointer. David MALAN: Eksakto, dahil sa pagkakataong ito, pansamantalang trabaho star nang isang pointer, isang address, sa pamamagitan ng kahulugan ng na star na doon. At kung Inaasahan scanf ng isang address, sapat nang lamang pumasa sa buffer. Hindi ko kailangan sabihin ampersand buffer. Para sa mga curious, maaari mong gawin ang isang bagay tulad nito. Ito ay may iba't ibang kahulugan. Ito ay magbibigay sa iyo ng isang pointer sa isang pointer, na kung saan ay tunay na isang wastong bagay sa C, ngunit para sa ngayon, panatilihin ito simple hayaan at panatilihin ang pare-pareho ang kuwento. Tingin lang ako sa pagpunta sa pumasa sa nagpapahina ng lakas at iyon ang tama. Ang problema bagaman ay na ito. Hayaan akong magpatuloy at patakbuhin ang programa matapos pag-ipon ng mga ito. Gumawa ng scanf 1. Mapapahamak ang mga ito, ang aking tagatala pansing aking error. Bigyan mo ako ng isang segundo. Clang. Sabihin natin na scanf-1.c. SIGE. Mayroon kaming pumunta. Kailangan ko. CS50 ID may iba't-ibang mga setting ng configuration na maprotektahan ka laban sa iyong sarili. Kailangan ko upang huwag paganahin ang mga iyon sa pamamagitan mano-mano ang pagpapatakbo clang oras na ito. Kaya string please. Pupunta ako sa sige at mag-type sa aking mga paboritong kumusta mundo. OK, null. Iyan ay hindi kung ano ang nai-type ko. Kaya ito ay nagpapakilala ng isang bagay na mali. Hayaan akong magpatuloy at i-type sa isang talagang mahabang string. Salamat para sa mga null at hindi ko alam kung ako pagpunta upang ma-crash ito. Subukan ang isang maliit na kopya Ipaalam idikit at alamin kung makakatulong ito. Ilagay lamang ang isang pulutong ng mga ito. Ito ay tiyak na isang mas malaking string kaysa sa karaniwan. Lang talaga isulat natin ito. Hindi. Mapapahamak ang mga ito. Command hindi natagpuan. Kaya na hindi kaugnay. Ito ay dahil nailagay ko ilang hindi magandang mga character, ngunit ito ay lumiliko out na ito ay hindi pagpunta sa trabaho. 

Subukan ito nang isa pang beses Ipaalam, dahil ito ay mas masaya kung namin ang tunay na pag-crash ng mga ito. Ni-type ito Hayaan at ngayon, ako pagpunta sa kopyahin ang isang tunay na mahabang string at ngayon sabihin makita kung kami ay maaaring bumagsak ang bagay na ito. Pansinin tinanggal ko na espasyo at bagong linya at semicolons at ang lahat ng funky mga character. Enter. At ngayon, ang network lang ang pagiging mabagal. Ako gaganapin down Command-V masyadong mahaba, malinaw. Mapapahamak ang mga ito! Command hindi natagpuan. 

SIGE. Well, ang punto ay gayunman ang mga sumusunod. Kaya kung ano ang tunay na nangyayari sa may ito deklarasyon ng char star buffer sa 16 na linya? Kaya kung ano ang ako pagkuha kapag ipinapahayag ko ang isang pointer? Lahat Nakakakuha ako ay isang halaga na apat byte tinatawag na buffer, ngunit kung ano ang nasa loob ng mga ito sa sandaling ito? Ito lamang ang ilang mga halaga ng basura. Dahil anumang oras ipinapahayag mo ang isang variable sa C, ito lamang ang ilang mga halaga ng basura, at kami ay nagsisimula upang trip sa paglipas ng ito sa katotohanan. Ngayon, kapag ako sabihin scanf, pumunta sa address na ito at ilagay ang kahit anong uri ng user sa. Kung ang uri ng user sa halo mundo, na rin, kung saan ko ilalagay ito? Buffer ay isang halaga ng basura. 

Kaya na uri ng tulad ng isang arrow na tumuturo na nakakaalam kung saan. Siguro ito ay tumuturo dito mismo sa aking memorya. At kaya kapag ang user uri sa kumusta mundo, ang programa sumusubok na ilagay ang string hello world backslash 0 sa na tipak ng memory. Ngunit may mataas na posibilidad, ngunit malinaw na hindi 100% na posibilidad na mangyari, ang computer ay pagpunta sa pagkatapos ng pag-crash ang programa dahil ito ay hindi memory ko dapat pinapayagan sa pagpindot. Kaya sa maikling salita, ang programang ito ay flawed para sa eksaktong na dahilan. Panimula ko hindi ginagawa kung ano? Ano ang mga hakbang kung tinanggal ko, tulad ng namin tinanggal na sa unang halimbawa Binky? Oo? 

Madla: paglalaan Memory? 

David MALAN: paglalaan Memory. Hindi ko pa talaga inilalaan anumang memory para sa na string. Kaya maaari naming ayusin ito sa isang pares ng mga paraan. One, maaari naming panatilihin ito simple at sa katunayan, ngayon ikaw ay pagpunta sa simulan na makita ang isang paglabo mga linya sa pagitan ng kung ano ang isang array ay, kung ano ang isang string ay, kung ano ang isang char star ay, kung ano ang isang array ng mga karakter ay. Narito ang isang pangalawang halimbawa kinasasangkutan string at notice lahat ng nagawa ko on line 16 ay, sa halip na sabihing na buffer ay magiging isang pansamantalang trabaho star, isang pointer sa isang tipak ng memory, Pupunta ako sa napaka-proactively bigyan sarili ko ng isang buffer para sa 16 mga character, at sa katunayan, kung hindi ka pamilyar sa mga kataga ng buffering, marahil mula sa mundo ng mga video, kung saan ang isang video ay buffering, buffering, buffering. Well, ano ang connection dito? Well, Inside ng YouTube at sa loob ng video player sa pangkalahatan ay isang array na mas malaki kaysa sa 16. Ito ay maaaring maging isang hanay ng mga laki ng isa megabyte, marahil 10 megabytes, at sa na array ang ginagawa ng iyong browser i-download ng isang buong grupo ng mga bytes, ang maramihang mga megabytes ng video, at mga video player, , Nagsisimula YouTube o kung sinuman ang pagbabasa ng mga bytes mula sa na array, at anumang oras na makita mo ang mga word buffering, buffering, ay nangangahulugan na ang manlalaro ay may tapat na paraan sa dulo ng array na. Ang network ay kaya mabagal na ito ay hindi refilled ang array na may higit pang mga bytes at iba nasa labas ka ng bits upang ipakita sa mga gumagamit. 

Kaya buffer ay isang apt term dito sa na ito lamang ay isang array, isang tipak ng memory. At ito ay ayusin ito dahil ito ay lumiliko out na maaari mong ituring array na parang ang mga ito ay mga address, kahit na buffer ay isang simbolo lamang, ito ay isang pagkakasunod-sunod ng mga character, buffer, na kapaki-pakinabang para sa akin, ang mga programmer, maaari mong ipasa ang pangalan nito sa paligid na parang ito ay isang pointer, na parang ito ay ang address ng isang tipak ng memory para sa 16 na karakter. Kaya na sabihin, maaari ko bang ipasa ang scanf eksakto na salita at kaya ngayon, kapag gumawa ako ng program na ito, gumawa scanf 2, tuldok slash scanf 2, at sa uri ng kumusta mundo, Ipasok, na time-- 

Hmm, ano ang nangyari? String please. Ano ang nagawa kong mali? Kamusta mundo, buffer. Kamusta mundo. Ah, alam ko kung ano ang ginagawa nito. SIGE. Kaya ito ay ang pagbabasa up hanggang sa unang space. Kaya sabihin impostor para sa sandali lamang at sinasabi ko lamang nais na mag-type ng isang bagay talagang mahaba tulad nito ay isang mahabang pangungusap iyon ang isa, dalawa, tatlo, apat, lima, anim, pito, walo, siyam, 10, 11, 12, 13, 14, 15, 16. SIGE. Ito ay sa katunayan ng isang mahabang pangungusap. Kaya pangungusap na ito ay mas mahaba sa 16 character at kaya kapag ako pindutin ang Enter, kung ano ang nangyayari sa mangyayari? Well, sa kasong ito ng kuwento, ako ay ipinahayag buffer sa tunay na pagiging isang array may 16 na karakter ay handa na upang patakbuhin. Kaya isa, dalawa, tatlo, apat, lima, anim, pito, walo, siyam, 10, 11, 12, 13, 14, 15, 16. Kaya 16 mga character, at ngayon, kapag ako basahin sa isang bagay tulad ng ito ay isang mahabang pangungusap, kung ano ang nangyayari sa mangyari ay na ako pagpunta sa basahin sa ito ay isang mahabang S-E-N-T-E-N-C-E, pangungusap. 

Kaya ito ay sadyang isang masamang bagay na ako panatilihin ang pagsulat sa kabila ng hangganan ng aking array, sa kabila ng hangganan ng aking buffer. Ako ay maaaring makakuha ng masuwerteng at ang programa ay patuloy na sa pagtakbo at hindi pag-aalaga, ngunit sa pangkalahatan ay nagsasalita, ito sa katunayan ay pag-crash ng aking mga programa, at ito ay isang bug sa aking code sa sandali hakbang ko sa ibayo ng hangganan ng na array, dahil ako hindi alam kung ito ay palaging pagpunta sa pag-crash o kung ako lamang ang pagpunta upang makakuha ng masuwerteng. Kaya ito ay may problema dahil sa kasong ito, ito ay tila na magtrabaho at hayaan tuksuhin ng kapalaran dito, kahit na parang tiisin lubos ng kaunti ang IDE of-- 

Mayroon kaming pumunta. Sa wakas. Kaya ako ang isa lamang na maaaring makita ito. Kaya lang ako nagkaroon ng maraming masaya pag-type ang isang tunay na matagal na aktwal na parirala na ito ay tiyak na nalampasan 16 bytes, dahil ako nag-type sa mga ito mabaliw pang multi-line parirala, at pagkatapos ay mapapansin kung ano ang nangyari. Sinubukan programa pag-print ito at pagkatapos ay nakuha ng segmentation fault at segmentation faults ay kapag isang bagay tulad ng nangyari ito at sinasabi ng operating system hindi, hindi maaaring hawakan na memory. Kami ay pagpunta sa pumatay ang programa sa kabuuan. 

Kaya ito ay tila problemang. Pinabuting ko na ang mga programa kung saan ang hindi bababa sa magkaroon ng ilang mga memory, ngunit ito ay tila na makulong ang function GetString sa pagkuha ng string ng ilang mga hangganan ng haba 16. Kaya kung nais mong upang suportahan ang mas matagal na pangungusap sa 16 mga character, ano ang gagawin mo? Well, maaari mong taasan ang laki ng buffer sa 32 o na tila uri ng short. Bakit hindi kami gumawa lamang ito 1,000 ngunit uurong. Ano ang tugon intuitively ng pag-iwas lamang ang problemang ito sa pamamagitan ng paggawa aking buffer mas malaki, tulad ng 1,000 karakter? Sa pamamagitan ng pagpapatupad GetString sa ganitong paraan. Ano ang mabuti o masama dito? Oo? Madla: Kung ikaw magpagaling ng isang pulutong ng space at hindi mo gamitin ang mga ito, pagkatapos ay hindi ka maaaring reallocate puwang na iyon. David MALAN: Ganap. Ito ay mapag-aksaya sa abot ng kung hindi mo gusto talagang kailangan 900 mga bytes at gayon pa man ikaw ay humihingi ng 1,000 sa kabuuang anyway, lamang ikaw ay ubos ng mas maraming memorya sa computer ng user sa kailangan mo na, at pagkatapos ng lahat, ang ilan sa na nakaranas ka na sa buhay na kapag ikaw ay tumatakbo ng maraming mga programa at sila ay kumakain up ng maraming memorya, ito ay maaari talagang epekto sa pagganap at karanasan ng gumagamit sa computer. Kaya na uri ng isang tamad na solusyon, para sigurado, at pasalungat, ito ay mapag-aksaya hindi lamang, kung ano ang problema nananatili pa rin, kahit na kapag gumawa ako nang aking buffer 1,000? Oo? 

Madla: string ay haba 1,001. David MALAN: Eksakto. Kung ang iyong mga string ay haba 1,001, mayroon ka ng parehong problema, at sa pamamagitan ng aking mga argument, gagawin ko lamang pagkatapos ay gawin itong 2000, ngunit hindi mo alam kung in isulong kung paano malaki ito ay dapat, at pa, ako ay hindi na ilista ang aking mga program bago pagpapaalam sa mga tao na gamitin at i-download ito. Kaya ito ay eksakto ang uri ng mga bagay-bagay na ang mga sumusubok CS50 library upang makatulong sa amin sa at makikita lamang namin sulyap ang ilan sa mga batayan sa pagpapatupad dito, ngunit ito ay CS50 dot C. Ito ay ang file na ay naging sa CS50 IDE lahat ng mga linggo na kayo ay gumagamit ng. Ito ay pre-naipon at na sa iyo Awtomatikong na ito gamit ang sa pamamagitan ng likas na katangian ng pagkakaroon ng Dash L CS50 bandila na may kalatungin, ngunit kung mag-scroll ko pababa sa pamamagitan ng lahat ng mga mga function na ito, narito ang GetString, at lamang na bigyan ka ng lasa ng kung ano ang nangyayari, sabihin kumuha ng isang mabilis na pagtingin sa mga kamag-anak kumplikado. Ito ay hindi isang super long function, ngunit kami ay hindi kailangang isipin ang lahat ng husto tungkol sa kung paano pumunta tungkol sa pagkuha ng mga string. 

Kaya narito ang aking buffer at ako Lumilitaw na magpasimula ito sa null. Ito, siyempre, ay ang parehong bagay tulad ng char star, ngunit ako ay nagpasya sa pagpapatupad ng CS50 library na kung kami ay pagpunta sa maging ganap na dynamic, Hindi ko alam nang maaga kung paano malaki ng isang gumagamit string ay pagpunta sa gusto upang makakuha ng. Kaya ako pagpunta sa simulan sa pamamagitan lamang ng isang walang laman na string at ako pagpunta upang bumuo ng up ng mas maraming memory bilang kailangan ko upang magkasya ang mga string ng user at kung hindi ko magkaroon ng sapat, ako pagpunta sa hilingin mga operating system para sa mas maraming memory. Pupunta ako upang ilagay ang kanilang string sa isang mas malaking tipak ng memory at ako pagpunta upang palabasin o libre ang insufficiently malaking tipak ng memory at lamang kami ay pagpunta upang gawin ito iteratively. 

Kaya isang mabilis na sulyap, narito ang isang variable lang na kung saan ako pupunta upang subaybayan ng kapasidad ng aking buffer. Gaano karaming bytes ko magkasya? Narito n isang variable na may kung saan ako pagpunta sa panatilihin subaybayan kung gaano karaming mga byte ay talagang sa ang buffer o na ang gumagamit ay nag-type. Kung hindi mo na makikita ito bago, ikaw ay maaaring tukuyin na ang isang variable tulad ng isang int ay unsigned, na ang pangalan ay nagpapahiwatig, nangangahulugan na ito ay hindi-negatibong, at bakit gagawin Ko kailanman nais na abala na tumutukoy na ang isang int ay hindi lamang isang int, ngunit ito ay isang unsigned int? Ito ay isang hindi-negatibong int. Ano ang ibig sabihin ng [hindi marinig]? 

Madla: Ito ay naglalarawan ng isang halaga ng memorya na maaaring maging [hindi marinig]. 

David MALAN: Oo. Kaya kung sinasabi ko unsigned, ito ay tunay na nagbibigay sa iyo ng isang piraso ng dagdag na memory at tila uri ng hangal, ngunit kung ikaw magkaroon ng isa bit ng karagdagang memory, na nangangahulugan na ikaw ay dalawang beses ng maraming halaga na maaari mong kumatawan, dahil ito ay maaaring maging isang 0 o 1. Kaya sa pamamagitan ng default, ang isang int maaaring humigit-kumulang negatibong 2 bilyong lahat ng mga paraan hanggang sa positibong 2 bilyong. Ang mga ay malaking saklaw, ngunit ito ay uri ng mapag-aksaya pa rin kung mahalaga sa iyo lamang tungkol sa na laki, na intuitively lamang dapat na di-negatibong o positibo o 0, sa gayon, bakit ka pag-aaksaya ng 2 bilyong posibleng halaga para sa mga negatibong numero kung hindi ikaw ay pagpunta sa gamitin ang mga ito? Kaya sa pamamagitan ng pagsasabi unsigned, ngayon ang aking int Maaari nasa pagitan ng 0 at halos 4 na bilyon. 

Kaya dito lang ang isang int C para sa mga dahilan Hindi namin makuha sa ngayon lang bilang sa kung bakit ito ay isang int sa halip ng isang pansamantalang trabaho, ngunit dito ay ang buod ng kung ano ang nangyayari sa, at ang ilan sa inyo maaaring gumagamit, halimbawa, ang fgetc function na kahit na sa pset apat o pagkatapos nito, makikita natin na gagawin muli sa hanay ng problema limang, fgetc ay dahil sa ganda tulad ng pangalan uri ng, uri ng arcanely nagmumungkahi, ito ay isang function na makakakuha ng isang character at sa gayon, ano ang panimula ng iba't ibang tungkol sa kung ano ang aming ginagawa sa GetString ay hindi kami gumagamit scanf sa parehong paraan. Kami ay gumagapang lamang kasama step-by-step higit sa anuman ang gumagamit ay nai-type sa, dahil maaari naming laging maglaan ng isa char, at sa gayon maaari naming laging ligtas tumingin sa isang char sa isang panahon, at mga ang magic ay nagsisimula sa mangyari dito. Pupunta ako upang mag-scroll pababa sa sa gitna ng mga function na ito lamang sa madaling sabi kitang ipakilala ang function na ito. Karamihan tulad ng mayroong isang malloc function, mayroong isang realloc function na kung saan realloc Hinahayaan ka ng reallocate isang tipak ng memory at gawin itong mas malaki o mas maliit. Kaya mahaba kuwento maikli at may isang alon ng aking mga kamay para sa araw na ito, alam na kung ano ang GetString ay ginagawa ay ito ay isang uri ng magically lumalaki o pag-urong ang buffer bilang ng gumagamit uri sa kanyang string. 

Kaya kung ang uri ng user sa isang maikling string, ang code na ito lamang naglalaan ng sapat na memory upang magkasya ang string. Kung patuloy na pag-type ng user ang tulad ng ginawa ko itong muli at muli at muli, well, kung ang buffer ni una ito malaki at ang mga programa napagtanto, upang maghintay ng isang minuto, ako sa labas ng espasyo, ito ay pagpunta sa double ang laki ng buffer at pagkatapos ay double ang laki ng buffer at ang mga code na gumagana ang pagdodoble, kung tinitingnan namin ang mga ito dito, ito ay lang ito matalino one-liner. Hindi maaaring nakita ang syntax na ito bago, ngunit kung sabihin mo star katumbas, ito ay ang parehong bagay tulad ng sinasabi beses kapasidad 2. Kaya ito lamang mapigil ang pagdodoble ang kapasidad ng buffer at pagkatapos ay nagsasabi realloc upang bigyan mismo na marami pa memory. 

Ngayon, bilang isang bukod, may mga iba pang mga function in dito na hindi namin ay tumingin sa anumang mga detalye maliban sa upang ipakita sa GetInt, ginagamit namin ang GetString sa GetInt. Nagsusuri kami na ito ay hindi null, na kung saan, pagpapabalik, ay ang espesyal na halaga na nangangahulugan may nangyaring mali. Humihingi kami ng out of memory. Mas mahusay na suriin para sa na. At bumalik kami ang halaga ng isang nagbabantay. Ngunit kukunin ko na umalinsunod sa mga komento bilang upang kung bakit at pagkatapos ay ginagamit namin ang pinsan ni scanf tinatawag sscanf at ito ay lumiliko out na sscanf, o string scanf, hinahayaan kang tingnan ang mga line na ang gumagamit ay nag-type sa at ipaalam sa iyo pag-aralan ito mahalagang at kung ano ako ginagawa dito ay ako na nagsasabi sscanf, suriin ang anumang mga user ay may nai-type sa at siguraduhin% i, may isang integer sa loob nito, at hindi kami kumuha sa ngayon nang eksakto kung bakit mayroon ding ay nagpapahintulot sa isang% c dito, ngunit na sa maikling sabi amin upang tuklasin kung ang gumagamit ay nag-type sa isang bagay na bogus pagkatapos ay ang numero. Kaya ang dahilan na GetInt at GetString sabihin sa inyo na subukan muli, muling subukan, subukang muli ay dahil sa ang lahat ng mga na code na aming sinulat, ito ay uri ng pagtingin sa input ng gumagamit sa siguraduhin ito ay ganap numeric o ito ay isang aktwal na lumulutang halaga o mga katulad na punto, depende sa kung ano ang halaga gumana ang ginagamit mo. 

Whew. SIGE. Iyon ay isang katiting ngunit ang punto dito ay na ang dahilan namin ay mga gulong ng pagsasanay sa ay dahil sa ang pinakamababang antas, may lamang kaya maraming mga bagay na maaaring magkamali na gusto naming upang preemptively hawakan tiyak na mga bagay-bagay sa pinakamaagang linggo ng klase, ngunit ngayon ay may Pset apat at Pset limang at lampas ay makikita mo na ito ay higit sa sa iyo ngunit din ikaw ay mas may kakayahang ng paglutas ng mga uri ng mga problema iyong sarili. Anumang mga katanungan sa GetString o GetInt? Oo? 

Madla: Bakit gusto mong i-double ang kapasidad ng buffer sa halip na lamang ang pagtaas ito sa pamamagitan ng eksaktong halaga? 

David MALAN: Magandang katanungan. Bakit namin double ang kapasidad ng buffer bilang laban sa pagtaas lang ito sa pamamagitan ng ilang tapat na halaga? Ito ay isang desisyon na disenyo. Nagpasya kaming lamang na ito sapagkat ito ay may gawi na medyo mahal oras-pera na magtanong mga operating system para sa memory, kami ay hindi gusto mong tapusin ang pagkuha sa isang sitwasyon para sa malaking mga string na kami ay humihingi muli at muli ang OS at muli at muli sa sunud-sunod para sa memory. Kaya't nagpasya na lang kami, medyo nagkataon ngunit umaasa kami na makatwirang, na, alam mo kung ano, sabihin subukan upang makakuha ng maagang ng ating sarili at lamang panatilihin ang pagdodoble ito upang ang minimize namin ang dami ng beses Mayroon namin ang tumawag sa malloc o realloc, ngunit isang kabuuang paghatol tumawag sa kawalan ng pag-alam kung ano ang maaaring gusto ang mga gumagamit na i-type. Ang parehong paraan ay maaaring hindi tiyak. Arguably mabuti. 

Kaya sabihin kumuha ng isang tumingin sa isang pares ng iba pang mga epekto ng memorya, mga bagay na maaaring maging mali at mga tool na maaari mong gamitin upang mahuli ang mga ganitong uri ng mga pagkakamali. Ito ay lumiliko out ang lahat ng sa iyo, kahit na check50 nang hindi sinasabi sa iyo ng mas maraming, ay sumusulat buggy code mula noong linggo ng isa, kahit na ang lahat pagsusuri check50 ay lumipas, at kahit na kung ikaw at ang iyong TF ay sobrang tiwala na gumagana ang iyong code tulad ng inilaan. Ang iyong code ay maraming surot o flawed sa na ang lahat ng sa iyo, in gamit ang CS50 library, ay pagtulo memory. Hindi ka na humihiling sa mga operating system para sa memory sa karamihan ng mga programa na iyong isinulat, ngunit na sa iyo hindi tunay na ibinigay ito pabalik. Mo na tinatawag GetString at GetInt at GetFloat, pero sa pamamagitan ng GetString, na sa iyo hindi na tinatawag unGetString o Bigyan String Back o mga katulad, ngunit nasaksihan namin na GetString ay magtalaga ng memory sa pamamagitan ng paraan ng malloc o ito function na realloc, na lamang halos kapareho sa espiritu, at gayon pa man, kami ay humihingi ng mga operating system para sa memory at memory muli at muli ngunit hindi kailanman nagbibigay ito pabalik. 

Ngayon, bilang isang bukod, ito ay lumiliko out na kapag ang isang programa tabla, ang lahat ng memory ay awtomatikong napalaya. Kaya ito ay hindi isang malaking pakikitungo. Ito ay hindi pagpunta sa basagin ang IDE o mabagal down na mga bagay, ngunit kapag ang mga programa gawin pangkalahatan tumagas memory at sila ay tumatakbo para sa isang mahabang panahon. Kung kailanman na iyong nakita ang hangal kaunti beach ball sa Mac OS o orasa sa Windows na kung saan ito ay uri ng alalay o pag-iisip o pag-iisip o talagang lamang nagsisimula sa mabagal sa isang crawl, ito masyadong marahil ay maaaring ang resulta ng isang memory tumagas. Ang mga programmer na nagsulat ang software na iyong ginagamit tanungin ang operating system para sa memory bawat ilang minuto, oras-oras. Ngunit kung ikaw ay nagpapatakbo ng mga software, kahit na ito ay mababawasan sa iyong computer para sa mga oras o araw sa dulo, maaari kang maging na humihingi para sa higit pa at mas memory at hindi aktwal na paggamit nito at iba ay maaaring ang iyong code, o programa ay maaaring pagtulo memory, at kung sinimulan mo sa tumagas na memorya, mayroong mas mababa memory para sa iba pang mga programa, at ang mga epekto ay upang mabagal lahat pababa. 

Ngayon, ito ay sa pamamagitan ng malayo ang isa sa mga ang pinaka-mabangis programa magkakaroon ka ng pagkakataon upang tumakbo sa CS50 insofar bilang output nito ay mas pribado kaysa clang o gumawa o anuman sa mga utos programs line na namin tumakbo bago ngunit Sa kabutihang palad, naka-embed sa kanyang output ay ang ilang mga sobrang mga helpful tips na ay magiging kapaki-pakinabang para sa alinman sa pset apat o tiyak Pset lima. Kaya valgrind ay isang kasangkapan na maaaring magamit upang tumingin para sa memory paglabas sa inyong programa. Ito ay medyo simple upang tumakbo. Patakbuhin mo valgrind at pagkatapos, kahit na kahit na ito ay isang maliit na masyadong masalita, dash check dash tumagas ay katumbas ng buong, at pagkatapos ay tuldok slash at ang pangalan ng iyong programa. Kaya ay pagkatapos tumakbo valgrind iyong programa at sa dulo ng iyong programa tumatakbo bago ito tabla at nagbibigay sa iyo ng isa pang prompt, ito ay pagpunta sa-aralan ang iyong program habang ito ay tumatakbo at sabihin mo tumagas mo anumang memorya at mas mahusay pa, humipo ka ng memorya na hindi naman sa iyo? Hindi na ito maaaring mahuli ang lahat, ngunit ito ay medyo magandang sa pansing karamihan sa mga bagay. 

Kaya narito ang isang halimbawa ng aking pagkakaroon run ang program na ito, ang pagkakaroon ng run valgrind, sa isang programa na tinatawag na memory, at ako pagpunta upang i-highlight ang mga linya na huli ng interes sa amin. Kaya may mas higit pang distractions na tinanggal ko na mula sa mga slide. Ngunit sabihin makita lamang kung ano ang mga ito programa ay kaya ng pagsabi sa amin. Ito ay kaya ng pagsabi sa amin ng mga bagay tulad ng mga di-wastong write ng mga laki 4. Sa ibang salita, kung pindutin mo memory, partikular na 4 bytes ng memory na hindi ka dapat magkaroon ng, Maaari sabihin sa iyo valgrind iyon. Di-wastong write ng mga laki 4. Baliw kang apat na bytes na hindi mo kailangang. Saan ginawa mo na? Ito ang kagandahan. Dot Memory c line 21 ay kung saan mo screwed up at iyon ang dahilan kung bakit ito ay kapaki-pakinabang. Karamihan tulad ng GDB, maaari itong makatulong ituro sa iyo sa tunay na mga error. 

Ngayon, ang isang ito ay isang kaunti pa masyadong masalita, kung hindi nakakalito. 40 bytes in 1 bloke ay tiyak nawala sa pagkawala tala 1 of 1. Ano ang ibig sabihin nito? Well, ito ay nangangahulugan lamang na iyong hiniling para sa 40 bytes at hindi ka nagbigay ng ito pabalik. Ikaw ay tumawag malloc o tumawag kayo GetString at ang operating system nagbigay ka ng 40 bytes, ngunit hindi mo napalaya o inilabas na memorya, at upang maging patas, hindi namin ipakita sa iyo kung paano magbigay ng bumalik memory. Ino-out may isang super simpleng function na tinatawag na libre. Dadalhin ng isang argument, ang mga bagay nais mong libreng o magbigay ng likod, ngunit 40 bytes, tila, sa programang ito ay nawala sa linya 20 ng memory dot c. 

Kaya sabihin makita programang ito. Ito ay sobrang walang silbi. Ito ay nagpapakita lamang ito partikular na error. Kaya sabihin tumagal ng isang pagtingin. Narito ang mga pangunahing at pangunahing, paunawa, tawag isang function na tinatawag f at pagkatapos ay nagbalik. Kaya hindi lahat na kawili-wili. Ano ang ibig f gawin? Pansinin na hindi ako nag-abala na may isang tularan. Nais kong panatilihin ang code bilang kaunti hangga't maaari. Kaya ko bang ilagay f itaas pangunahing at na multa, tiyak, para sa maikling programa tulad nito. Kaya f ay hindi bumalik sa anumang bagay at ang hindi kumuha ng anumang bagay, ngunit ito ay hindi gawin ito. Ito ay nagpapahayag, magkano ang gusto sa halimbawa sa Binky, isang pointer na tinatawag na x na pagpunta sa tindahan ng mga address ng isang int. Kaya na ang kaliwang bahagi. Sa Ingles, ano ang side-kanan na ginagawa? Kahit sino? Ano itong ginagawa para sa atin? Oo? 

Madla: [hindi marinig] beses ang laki ng isang int na kung saan ay 10 beses na [hindi marinig] David MALAN: Magandang at ipaalam sa akin sabihin sa maikling pangungusap. Kaya maglaan ng sapat na espasyo para sa 10 integer o 10, ano ang sukat ng isang int, ito ay apat na bytes, kaya 10 beses 4 ay 40, kaya kanang kamay na side na ko naka-highlight ay bigyan ako ng 40 bytes at tindahan ang address ng unang byte sa x. At ngayon, sa wakas, at narito ang kung saan ang program na ito ay maraming surot, kung ano ang mali sa linya 21 batay sa na logic? Ano ang mali sa linya 21? Oo? Madla: Maaari mong hindi index sa x [hindi marinig]. David MALAN: Oo. Hindi ko dapat index sa x mo na. Kaya syntactically, na ang OK. Ano ang maganda ay, magkano ang gusto mong maaaring gamutin ang pangalan ng isang array parang ito ay isang pointer, katulad maaari mong ituring ang isang pointer na parang ito ay isang array, at sa gayon maaari kong syntactically sabihin x bracket ng isang bagay, x bracket i, ngunit ang 10 ay may problema. Bakit? 

Madla: Dahil ito ay hindi sa loob. 

David MALAN: Ito ay hindi sa loob na tipak ng memory. Ano ang pinakamalaking halaga ang dapat kong ay paglagay sa mga square bracket? 9, 0 hanggang 9. Dahil sa zero-index. Kaya 0 hanggang 9 ay magiging masarap. Bracket 10 ay hindi mabuti at ngunit, pagpapabalik bagaman, sa bawat oras Mukhang ako na subukan na gumawa ng CS50 IDE crash sa pamamagitan ng pag-type sa bogus na mga halaga, ito ay hindi laging tumulong, at sa katunayan, na madalas mong makakuha ng masuwerteng dahil lang sa operating system ay hindi mapapansin mo na ikaw napaka bahagyang pumasa ang ilang tipak ng memory, dahil ikaw ay nanatili sa loob ng technically iyong segment, ngunit higit pa sa na sa isang klase ng mga operating system, at iba bagay na tulad nito maaaring tunay madaling pumunta undetected. Ang iyong programa ay hindi kailanman pagpunta sa crash patuloy ngunit marahil isang beses sa sandali. 

At subukan ni valgrind kaya hayaan sa mga ito, at narito ang kung saan kami makakuha ng bumagsak sa pamamagitan ng output sa ilang sandali. Kaya gumawa ng memory check valgrind tumagas ay katumbas ng full dot slash memory. At narito ang kung bakit nangangako ako ito ay mapuspos. Narito kung ano ang valgrind, narito kung ano isang programmer, ilang taon na ang nakaraan nagpasya na ito ay isang magandang ideya para sa mga output sa hitsura. Kaya sabihin gumawa ng kahulugan ng mga ito. Kaya lahat ng mga paraan sa kaliwa-kamay side ng walang magandang dahilan ay ang proseso ng ID ng programa tumakbo lang namin, ang mga natatanging identifier para sa programa tumakbo lang namin. Tinanggal namin na mula sa mga slide, ngunit may ay ang ilang mga kapaki-pakinabang na impormasyon dito. 

Ni mag-scroll pataas sa pinakatuktok Hayaan. Narito kung saan sinimulan namin. Kaya ito ay hindi lahat na marami output. Narito na ang mga di-wastong write ng laki 4 sa 21 linya. Well, kung ano ang linya 21? Line 21 ay eksaktong ito at ito ang akma na ako sa validly pagsulat ng 4 bytes dahil ako sinusubukan mong ilagay ito integer, na kung saan ay maaaring maging anumang bagay, mangyayari lamang ito upang maging zero, ngunit sinusubukan ko upang ilagay ito sa isang lokasyon na ay hindi nabibilang sa akin. Bukod pa rito, rito, 40 bytes sa isa bloke ay talagang nawala sa record 1. Ito ay dahil kapag tumawag ako malloc dito, hindi ko talaga libre ang memory. 

Kaya kung paano namin ito aayusin? Hayaan akong magpatuloy at maging isang maliit na mas ligtas at gawin 9 doon at ipaalam sa akin dito libre x. Ito ang bagong pag-andar para sa araw na ito. Kung muling palabas ng pelikula ko ngayong gumawa ng memory tuldok slash, ni patakbuhin valgrind muli sa ito ipaalam, i-maximize ang aking window at pindutin ang Enter. Ngayon, ito ay mabuti. Ibaon nila ang mabuting balita sa lahat ng mga ito output. Lahat magbunton bloke ay libre. Darating kami pabalik sa kung ano ang magbunton ay, ngunit walang mga paglabas ay maaari. Kaya ito ay isa lamang kasangkapan para sa iyong tool kit na kung saan maaari mong simulan upang hanapin mo ngayon ang mga error na tulad ng. 

Ngunit sabihin makita kung ano higit pa maaaring magkamali dito. Ni transition Hayaan ngayon upang tunay na paglutas ng problema. Bilang isang tabi, kung ito ay sa hitsura ng isang maliit na piraso ng pagkalito o pag-aalaala, ito ay nakakatawa ngayon. Oo. Iyan ay medyo mabuti. Dahil payo ay address at address sa pangkalahatan sa pamamagitan ng convention nakasulat sa hexadecimal. Ha, ha, na ito ay funny ngayon. Sa papaano mang paraan, kaya sabihin ngayon aktwal na malutas ang isang problema. Ito ay naging sobrang, sobrang low-level kaya sa ngayon, at maaari naming aktwal na gawin kapaki-pakinabang mga bagay-bagay na may mga detalye ng mababang antas. 

Kaya ipinakilala namin ng ilang linggo nakalipas ang paniwala ng isang array. Isang array ay dahil sa ganda ito ay mahirap upang linisin ang aming code dahil kung gusto naming magsulat ng isang program na may maramihang mga mag-aaral o maramihang mga pangalan at mga bahay at dorms at mga kolehiyo at lahat ng iyon, kami ay maaaring tindahan ng higit pa sa lahat ng bagay nang malinis sa loob ng isang array. Ngunit imungkahi isa downside ng isang array kaya sa ngayon. Kahit na hindi mo na pinagdudusahan ito sa iyong sarili sa isang programa, katutubo lamang, kung ano ay isang masamang bagay tungkol sa isang array marahil,? Ako marinig ng ilang murmurs. Madla: Ito ay mahirap upang baguhin ang laki. David MALAN: Ito ay mahirap upang baguhin ang laki. Hindi mo maaaring baguhin ang laki ng isang array, sa katunayan, per se sa C. Maaari kang magtalaga ng isa pang array, ilipat ang lahat ng bagay mula sa mga lumang isa sa bagong, at ngayon magkaroon ng ilang dagdag na espasyo, ngunit ito ay hindi tulad ng isang wika tulad ng Java o sawa o anumang bilang ng iba pang mga mga wika na kung saan ang ilan sa iyo maaaring maging pamilyar kung saan mo Maaari lamang panatilihin ang pagdaragdag ng mga bagay-bagay hanggang sa pagkainis ad hanggang sa dulo ng isang array. Kapag mayroon kang isang hanay ng mga laki 6, iyon ay ang laki nito, at kaya magkano tulad ng mas maaga ang mga ideya pagkakaroon ng isang buffer ng isang tiyak na laki, mayroon kang hulaan sa labas ng gate ano ang laki na gusto mo ito upang maging? Kung hulaan mo masyadong malaki, ikaw ay pag-aaksaya ng espasyo. Kung hulaan mo masyadong maliit, ikaw ay Hindi maaaring mag-imbak ang data na iyon, hindi bababa sa walang isang pulutong ng mas maraming trabaho. 

Kaya ngayon, salamat sa mga payo, magagawa namin simulan stitching magkasama ang aming sariling mga pasadyang istruktura ng data, at sa katunayan, dito ay isang bagay na mukhang ng kaunti pa cryptic sa unang tingin, ngunit ito ay kung ano ang makikita namin tumawag ng isang naka-link listahan, at ang pangalan ng kanyang uri ng nagbubuod ito. Ito ay isang listahan ng mga numero, o sa kasong ito, ang isang listahan ng mga numero, ngunit ito ay maaaring maging isang listahan ng anumang bagay, ngunit ito ay naka-link nang sama-sama sa pamamagitan ng paraan ng mga arrow, at tumagal lamang ng isang hulaan sa kung ano ang diskarteng kami ay pagpunta sa ma tahiin magkasama, uri ng tulad ng popcorn sa isang thread, isang listahan ng link parihaba dito? Ang mga numero? Ano ang mga tampok na pinagbabatayan ng wika? 

Madla: A pointer. 

David MALAN: Isang pointer. Kaya ang bawat isa sa mga arrow na ito dito ay kumakatawan sa isang pointer o lamang ng isang address. Kaya sa ibang salita, kung gusto ko upang mag-imbak ng isang listahan ng mga numero, Hindi ko lang mag-imbak ito kung gusto ko ng kakayahan sa paglaki at pag-urong aking mga istraktura ng data sa isang array. Kaya kailangan ko upang magkaroon ng isang maliit mas sopistikado, ngunit mapapansin na ito larawan ng uri ng nagmumungkahi na kung lang kayong maliit na mga thread pagkonekta sa lahat ng bagay magkasama, marahil ay hindi na mahirap upang gumawa ng puwang sa pagitan ng dalawang ng mga parihaba o dalawang ng mga nodes, tulad ng kami ay magsimula pagtawag sa kanila, ilagay sa isang bagong node, at pagkatapos ay may ilang mga bagong thread, lamang umaagos ang tatlong nodes magkasama, ang unang isa, ang huling isa, at ang isa na ipinasok mo lamang sa gitna. 

At sa katunayan ng isang listahan ng mga link, hindi katulad ng isang array, ay dynamic. Maaari itong maging at kaya nito pag-urong at wala ka kung alam o pag-aalaga ng maaga kung magkano ang data na ay pagpunta sa pag-iimbak, ngunit ito ay lumiliko out na namin na maging isang maliit maingat tungkol sa kung paano ipatupad ito. Kaya isaalang-alang kung paano namin ipatupad ang unang hayaan ang isa sa maliliit na parihaba. Ito ay madali upang ipatupad ang isang int. Sabihin mo lang int n at pagkatapos ay makakakuha ka ng 4 bytes para sa isang int, ngunit kung paano ako makakakuha ng isang int, tumawag ito n, at pagkatapos ng isang pointer, tumawag ito sa susunod ipaalam. Kami ay maaaring tumawag sa mga mga bagay-bagay kahit ano ang gusto namin ngunit kailangan ko ng isang istraktura custom data. Oo? 

Madla: Ampersand [hindi marinig]. 

David MALAN: Kaya ampersand gagamitin namin upang makuha ang address ng isang node potensyal. Ngunit kailangan namin ng isa pang Ang tampok ng C upang upang bigyan ako ng kakayahan upang lumikha ito pasadyang parihaba, ang custom variable kung ikaw ay, sa memorya. Madla: A struct. David MALAN: Isang struct. Pagpapabalik mula noong nakaraang linggo, ipinakilala namin struct, ito medyo simple keyword na nagbibigay-daan sa amin gumawa ng mga bagay na tulad nito. C ay hindi dumating sa isang data istraktura na tinatawag na mag-aaral. Ito ay nanggagaling sa int at float at char at tulad, ngunit ito ay hindi nanggaling sa mga estudyante, ngunit maaari naming lumikha ng isang uri ng data na estudyante, isang istraktura ng mag-aaral, na may syntax na ito dito. At makikita mo ito muli at muli. Kaya huwag mag-alala tungkol sa pagsasaulo ng mga keyword, ngunit ang mga keyword na iyon ang mahalaga ay lamang ang katotohanan na sinabi namin struct at pagkatapos ay tinatawag naming ito ang mag-aaral at sa loob ng ng mag-aaral ay isang pangalan at isang bahay o isang dorm o mga katulad. 

At kaya ngayon araw na ito, ni imungkahi ito ipaalam. Idinagdag ko na ang ilang mga salita, ngunit kung gusto ko upang ipatupad ang rectangle na ito na Nakakuha parehong isang int at isang pointer, alam mo kung ano, ako pagpunta na idedeklara ng isang struct tinatawag node. Ako din, sa loob ng mga ito, pagpunta sa sabihin na ang isang node, ito parihaba, may isang int at kami ay tumawag ito n at ito ay may susunod na pointer. At ito ay isang maliit na masyadong masalita, ngunit kung sa tingin mo tungkol dito, ang mga arrow na nasa larawan ilang sandali ang nakalipas ay kung ano ang uri ng data? Saan bawat isa ng mga arrow ay nakaturo sa kung ano ang uri ng istraktura ng data? Ito ay hindi lamang ng pagturo sa isang int per se. Ito ay nakaturo sa buong parihabang bagay at na parihabang bagay, sinabi namin, ay tinatawag na isang node. At kaya namin uri ng kung recursively tukuyin ang mga ito tulad ng na ang isang node, sabihin natin, ay maglalaman ng isang int tinatawag n at isang pointer na tinatawag na susunod at ang uri ng data na istraktura na kung saan ang na pointer mga puntos ay tila magiging struct node. 

Kaya ito ay annoyingly masyadong masalita at upang maging pilosopo lamang, ang dahilan kung bakit hindi namin maaari sabihin lang na ito, na lantaran Mukhang mas nababasa ng isang pulutong, ay dahil pagpapabalik na C basahin mga bagay-bagay sa itaas hanggang sa ibaba, kaliwa papuntang kanan. Ito ay hindi hanggang sa makuha namin ang semicolon na ang tunay na umiiral ang keyword node. Kaya kung nais namin na magkaroon ng ganitong uri ng mga cyclical reference sa loob ng data istraktura, kami ay may sa gawin ito, na kung saan ang sinasabi namin struct node sa tuktok, na kung saan ay nagbibigay sa amin ng isang mas matagal na paraan ng naglalarawan na ito bagay, at pagkatapos sa loob sabihin namin struct node, at pagkatapos ay sa huling linya sinasabi namin, lahat ng karapatan, C, sa daan, tumawag lamang sa mga ito ang buong sumpain bagay sa isang node at itigil gamit ang keyword na struct kabuuan. Kaya ito ay lamang ng isang uri ng isang syntactic bilis ng kamay na nagbibigay-daan sa huli kaming lumikha isang bagay na mukhang eksakto tulad nito. 

Kaya kung ipinapalagay namin ngayon ng aming makakaya ipatupad ang bagay na ito sa C, kung paano gawin namin talagang simulan traversing ito? Well, sa katunayan, ang kailangan lamang nating gawin ay umulit mula kaliwa papuntang kanan at lamang uri ng ipasok nodes o tanggalin nodes o maghanap para sa mga bagay-bagay kung saan man gusto namin, ngunit upang gawin ito, sabihin sige at gumawa mga bagay-bagay ng kaunti pa sa real dahil ito ay sobrang mababa ang antas ng kaya sa ngayon. Gusto sinuman literal na maging una? SIGE. Lumapit sa up. Ano ang pangalan mo? 

DAVID: David. David MALAN: David. Masaya akong makilala kayo. Ako rin. Lahat tama. At kailangan namin ng isang number 9. Hindi kasing ganda ng una, marahil. OK, number 9. Ang bilang 17, please. Hayaan akong bumalik sa dako pa roon. Number 22, paki, at kung paano tungkol sa malayo sa likod kung ang maaari kong makita ang anumang mga kamay sa lahat ng mga light o hindi. Isang tao ang pagiging nagboluntaryo may karapatan. Gusto mo bang magkaroon ng? Ang iyong bisig ay pwersahang pagpunta up. OK, 17. 22. 26 ay darating pababa. Gusto kahit sino pa ang nais na forcefully-- Halika up. Isang aktwal na volunteer. 

Kaya nang masyadong mabilis, kung ka guys ay maaaring ayusin Gusto ninyo ang inyong sarili lamang ang mga node sa screen. Salamat. At makikita mo na 26. Lahat ng mga karapatan at mabilis na pagpapakilala. Kaya ako si David at ikaw din? DAVID: David. David MALAN: At ikaw? JAKE: Jake. SUE: idemanda. ALEX: Alex. RAPHAEL: Raphael. TAYLOR: Taylor. David MALAN: Taylor. Magaling. Kaya ito ay ang aming mga boluntaryo para sa araw at sige at maglipat ng isang maliit na paraan, at pumunta lamang magpatuloy at panatilihin humahawak ng iyong numero bilang ikaw o ang iyong unang pag-sign at gamit ang iyong kaliwang kamay, sige, at ipatupad lamang mga arrow, lamang upang ang iyong kaliwang kamay ay literal pagturo sa anumang dapat mong ituro sa, at bigyan ang iyong sarili ng ilang silid sa gayon ay maaari naming makita ang iyong mga arm talaga pagturo, at maaari mo lamang ituro uri ng sa lupa ay ayos lang. 

Kaya dito kami ay may isang listahan ng mga link ng isa, dalawa, tatlo, apat, lima nodes sa una, at mapapansin na namin ang mga espesyal na pointer sa simula kung sino ang key dahil kami ay may upang subaybayan ng buong listahan haba kahit paano. Ang mga lalaki, kahit na sila ay nag-iwan sa kanan, pabalik sa likod sa memorya, ito ay maaari talagang maging kahit saan sa memory ng computer. Kaya ang mga guys ay maaaring nakatayo kahit saan sa entablado at na multa, kaya hangga't ang mga ito ay tunay na tumuturo sa isa't isa, ngunit upang panatilihin ang mga bagay-bagay malinis at simple, bibigyan namin ng gumuhit lamang ang mga ito kaliwa hanggang kanang tulad na ito, ngunit may maaaring napakalaking gaps sa pagitan ng mga nodes. 

Ngayon, kung gusto kong talagang ipasok ang ilang mga bagong halaga, sige at gawin ito ipaalam. Kami ay may isang pagkakataon na ngayon upang pumili ng isa pang node. Say ni magsimula sa mallocing 55 ipaalam. Gusto ng isang tao isip na malloc? OK, dumating sa up. Ano ang pangalan mo? RAINBOW: Rainbow. David MALAN: Rainbow? Lahat tama. Malloc Rainbow. Lumapit sa up. Kaya ngayon kami ay upang hilingin sa ating sarili algorithmically kung saan maaari naming ilagay ang 55. Kaya ang lahat ng sa amin, malinaw naman, kung saan siya ay malamang na nabibilang kung kami ay nagsisikap upang panatilihin ang pinagsunod-sunod na ito at kung ikaw guys ay maaaring tumagal ng isa hakbang pabalik kaya hindi namin malagas entablado, na magiging malaki. Kaya talaga, Rainbow, magsimulang muli dito sa akin, dahil kami na ang computer ngayon ay maaari makita lamang ang isang variable sa isang pagkakataon. Kaya kung ito ay ang unang node. Pansinin siya ay hindi isang node, siya ay isang pointer lamang, at iyon ang dahilan kung bakit siya ay iguguhit na maging lamang sa sukat ng isang pointer, hindi isa sa mga full parihaba. Kaya kami ay pagpunta upang suriin sa bawat pag-ulit ay 55 mas mababa sa 9? Hindi. Ay 55 mas mababa sa 17? Hindi. Mas mababa sa 22? Mas mababa sa 26? Mas mababa sa 34? At kaya ngayon, nang walang alinlangan Rainbow nabibilang sa dulo. Kaya upang maging malinaw, at kung ano ang ay ang iyong pangalan, Taylor? 

TAYLOR: Taylor. David MALAN: Kaya bukod sa Taylor kaliwang kamay at kamay Rainbow dito, pangangailangan na ang kamay upang ituro sa kung ano ang sa order upang ipasok 55 sa listahang ito? Ano ang dapat nating gawin? Oo? 

Madla: hand Taylor pangangailangan sa point kaliwa. 

David MALAN: Eksakto. Kaya ng pagpasok ng isang node sa dulo ng listahan ay medyo simple dahil Taylor lamang Wala sa punto, sa halip ng sa lupa o kami ay tumawag ito null, null ay uri ng kawalan ng isang pointer o ng isang espesyal zero pointer, ikaw ay pagpunta sa point sa iyong kaliwang kamay sa Rainbow at pagkatapos Rainbow, kung saan dapat iyong kaliwa kamay marahil point? Down. Ito ay hindi mabuti kung ang kanyang kamay ay isang uri ng pagturo off dito o uri ng anumang na paraan. Iyon ay ituturing ang halaga ng basura, ngunit kung siya puntos sa ilang kilalang halaga, ipapakita namin tawag na ito sa zero o null, na OK dahil kami ay may isang term na ito sa at alam namin ang listahan na ngayon ay kumpleto na. 

Kaya kung ano ang isa pang medyo simple kaso? Puwede naming malloc 5? Lumapit sa up. Ano ang pangalan mo? TIFFANY: Tiffany. David MALAN: Sorry? TIFFANY: Tiffany. David MALAN: Tiffany. Lahat tama. Tiffany ay malloced may halaga 5. Lumapit sa up. Isa na ito ay medyo madali masyadong, ngunit Isaalang-alang natin sunod ng mga operasyon sa ngayon. Ito ay medyo madali Taylor sa dulo. Number 5 ay siyempre mas mababa sa 9, at sa gayon kami David, mayroon kaming Tiffany, at kung ano ang pangalan mo? 

JAKE: Jake. 

David MALAN: Jake. Tiffany, Jake, at David. Dapat na unang na-update na ang mga kamay? Ano ang gusto mong gawin dito? May isang pares ng posibleng paraan, ngunit may isa o higit pang mga maling paraan din. 

Madla: Magsimula sa pinakakaliwa. 

David MALAN: Magsimula sa pinakakaliwa. Sinong pinakakaliwa dito pagkatapos? Madla: Una. 

David MALAN: OK. Kaya magsimula sa una at kung saan mo nais na i-update ang mga kamay ni David upang maging? Madla: Patungo sa 5. David MALAN: OK. Kaya David, point sa limang o Tiffany dito, at ngayon? 

Madla: Tiffany puntos sa mga 9? David MALAN: Perfect, maliban Binky ulo lamang ang uri ng nahulog off, right? Dahil kung ano ang mali sa ang larawang ito ng literal? Madla: Wala ay pagturo. David MALAN: Wala ay tumuturo sa Jake ngayon. Literal na naulila kaming 9 at 17, at na namin literal leaked lahat ng ito memory, dahil sa pamamagitan ng pag-update ng unang kamay ni David, na ang fine sa abot ng ito ay tama pagturo sa Tiffany ngayon, ngunit kung hindi isa ay nagkaroon ng iintindi sa hinaharap upang ituro sa Jake, pagkatapos namin nawala ang kabuuan ng listahan na iyon. Kaya ni-undo ipaalam. Kaya na ay isang magandang bagay na paglalakbay sa loob ngunit ni iwasto ngayon hayaan. Ano ang dapat naming gawin sa halip unang? Oo? 

Madla: dapat point Tiffany sa 9? David MALAN: hindi ko makakaya kumuha na malapit sa iyo. Sino ang dapat ituro sa 9? 

Madla: Tiffany. 

David MALAN: Lahat ng karapatan. Kaya dapat Tiffany unang punto sa 9. Kaya Tiffany ay dapat kumuha ng sa isang kaparehong halaga kay David, na tila kalabisan para sa isang sandali, ngunit na fine dahil ngayon, pangalawa hakbang, maaari naming i-update ang kamay ni David upang ituro sa Tiffany, at pagkatapos ay kung lamang ng uri ng malinis na namin ang mga bagay up na parang ito ay uri ng spring-gusto, ngayon na ang isang tamang insertion. Kaya mahusay. Kaya ngayon kami ay halos doon. Ipasok ni isa huling Ipaalam halaga tulad ng mga halaga ng 20. Kung maaari naming malloc isang huling volunteer? Lumapit sa up. Kaya ang isang ito ay mas ng isang maliit na manlilinlang. Ngunit talagang, ang code ay hindi namin pagsulat, kahit na sa bibig, ay tulad ng pagkakaroon ng grupo ng kung kundisyon ngayon, tama? Nagkaroon kami ng isang kondisyon check kung nabibilang ito sa dulo, siguro sa simula. Kailangan namin ang ilang mga uri ng loop sa hanapin ang spot sa gitna. Kaya sabihin gawin iyon sa kung ano ang iyong pangalan? 

ERIC: Eric. 

David MALAN: Eric? Eric. Masaya akong makilala kayo. Kaya kami ay may 20. Mas mababa sa limang? Hindi. Mas mababa sa siyam? Hindi. Mas mababa sa 17? Hindi. SIGE. Siya ay kabilang dito at iyong pangalan muli ay ang mga? SUE: idemanda. David MALAN: idemanda. ALEX: Alex. David MALAN: idemanda, Alex, at? ERIC: Eric. David MALAN: Eric. Kaninong mga kamay kailangan upang makakuha ng unang-update? 

Madla: Eric. SIGE. Kaya dapat ituro ni Eric sa kung saan? Sa 22. Good. At ngayon kung ano ang susunod? Maaari pagkatapos ay ituro ang idemanda sa Eric at ngayon, kung kayo guys lamang gumawa ng ilang mga kuwarto, na kung saan ay mainam na biswal, ngayon tapos na namin ang insertion. Kaya isaalang-alang ngayon ng isang katanungan ipaalam ngunit salamat sa iyo kaya magkano para sa aming mga boluntaryo. Tunay na magaling. Maaari mong panatilihin ang mga iyon, kung gusto mo. At kami ay may isang kaibig-ibig pamamaalam nito kung Gusto mo sa bawat nais na kumuha ng isang stress ball. Hayaan lamang pumasa sa akin ang mga down. Kaya kung ano ang takeaway ng mga ito? Parang amazing na ito sa abot ng mayroon kami ngayon nagpasimula ng isang alternatibo sa isang array na ay hindi kaya nakakulong sa isang hanay ng ilang mga nakapirming laki. Maaari silang lumaki magilas. 

Subalit marami tulad namin na iyong nakita sa linggo nakaraan, hindi namin makuha ang anumang bagay para sa libreng, tulad ng tiyak na may isang kalakalan-off dito. Kaya may isang baligtad ng isang naka-link listahan, ito dynamism? Kakayahan na ito sa paglaki at lantaran, maaaring kami delete at maaari naming pag-urong kung kinakailangan. Ano ang presyo ay namin nagbabayad? Dalawang beses ng mas maraming espasyo, una sa lahat. Kung tumingin ka sa mga larawan, hindi na Ako pagtatabi ng isang listahan ng mga integer. Ako sa pagtatabi ng isang listahan ng mga integer plus payo. Kaya ako pagdodoble ang halaga ng puwang. Ngayon, marahil na hindi tulad ng sang-ayon 4 bytes, 8 bytes, ngunit ito ay maaaring tiyak na magdagdag ng up para sa mga malalaking mga hanay ng data. Ano ang isa pang downside? Oo? 

Madla: Mayroon kaming na tawirin ang mga ito ng isa-isa. David MALAN: Oo. Mayroon kaming upang tumawid ang mga ito ng isa-isa. Alam mo kung ano, binigyan up namin ito super maginhawa tampok ng square bracket notation, mas maayos kilala bilang random access, kung saan maaari naming lamang tumalon sa isang indibidwal na sangkap ngunit ngayon kung hindi pa rin ako nagkaroon aking volunteers dito, kung nais ko upang mahanap ang number 22, hindi ko na lang tumalon sa bracket ng isang bagay ng isang bagay. Mayroon akong upang tumingin sa ibabaw ng listahan, marami tulad ng ating mga halimbawa searching linearly, upang mahanap ang numero 22. Kaya tila namin na may bayad na isang presyo doon. Ngunit maaari naming gayunman malutas ang iba pang mga problema. 

Sa katunayan, hayaan mo akong ipakilala lamang ng ilang mga visual. Kaya kung kayo ay pababa sa Dining Hall Mather kamakailan, kayo pagpapabalik na ang kanilang stack ng mga trays na tulad nito, hiniram natin ang mga mula Annenberg bago klase. Kaya ito stack ng mga trays, bagaman, ay kinatawan aktwal ng isang computer science istraktura ng data. May ay isang istraktura ng data sa computer science kilala bilang isang stack na lubhang mabuti lends mismo sa eksaktong ganitong visual. Kaya kung bawat isa sa mga trays ay hindi isang tray ngunit tulad ng isang numero at ang nais ko upang mag-imbak ng mga numero, ako maaaring ilagay ang isa rito, at maaari ko bang ilagay ang isa pang down dito, at magpatuloy stacking numero sa ibabaw ng bawat isa, at kung ano ang potensyal na mga kapaki-pakinabang tungkol sa mga ito ay ang kung ano ang implikasyon ng istraktura ng data? Aling numero ang maaari kong bunutin unang pinaka Maginhawang? Ang pinaka-kamakailan isa ilagay sa doon. 

Kaya ito ay kung ano ang gusto naming tumawag sa computer science ng LIFO istraktura ng data. Huling in, first out. At kami na makita bago mahaba kung bakit na maaaring maging kapaki-pakinabang ngunit sa ngayon, isaalang-alang lamang ang mga ari-arian. At ito ay uri ng tangang kung sa tingin mo tungkol sa kung paano gumagana ang mga ito sa dining hall. Sa bawat oras na sila ay malinis trays at ilagay ang pinakasariwang mga nasa tuktok, maaari kang magkaroon ng isang dati malinis ngunit sa huli napaka marumi at maalikabok tray sa pinakadulo ibaba kung hindi mo talaga kumuha sa ilalim ng na stack, dahil ikaw lang panatilihin ang paglalagay ng mga bago at ang malinis na mga sa ibabaw ng mga ito. Ang parehong bagay ang maaaring mangyari sa isang supermarket masyadong. Kung mayroon kang isang display case ng gatas at sa bawat oras na CVS o kahit sino ang makakakuha ng mas maraming gatas, isalya mo lang ang mga gatas ikaw ay mayroon sa likod at ilagay mo ang mga bago up harap, ikaw ay pagpunta sa may ilang medyo bastos gatas sa dulo ng mga istraktura ng data, dahil ito ay palaging sa ilalim o equivalently ito ay palaging sa likod. 

Subalit mayroong isa pang paraan upang isipin ang tungkol sa lining up ng data at halimbawa, ito. Kung ikaw ay isa sa mga tao na may gusto sa line up sa labas ng tindahan ng Apple kapag dumating ang isang bagong produkto out, ikaw ay malamang na hindi gumagamit ng isang data stack istraktura dahil ikaw Gusto ipagkakaloob sa iba ang iba kung sino ay panig hanggang sa pagbili ng ilang mga bagong laruan. Sa halip, ikaw ay malamang na gamit kung anong uri ng mga istraktura ng data o kung ano ang uri ng system sa tunay na mundo? Sana ito ay isang linya, o higit pa maayos o mas British-like, isang pila. At ito ay lumiliko out ang isang pila ay isa ring istraktura ng data sa computer science, ngunit isang queue ay isang napaka iba't-ibang mga ari-arian. Ito ay hindi LIFO. Huling in, first out. Huwag nawang mangyari. Ito ay sa halip FIFO. Unang in, first out. At iyon ay isang magandang bagay para sa pagkamakatarungan 'alang-alang tiyak na kapag ikaw ay lining up super maaga sa umaga. Kung makakuha ka muna doon, ikaw gusto mong lumabas muna rin. 

At sa gayon ang lahat ng mga data na ito kaayusan, queues at stack at mga kumpol ng iba, lumiliko out ka maaaring sa tingin ng mga ito bilang lamang ng isang array. Ito ay isang array, siguro isang nakapirming laki 4, ngunit gusto ito maging uri ng magaling kung lamang namin mai pagtira trays halos walang hanggan ang taas kung tayo Mayroon na ang maraming mga trays o numero. Kaya marahil, gusto nating gumamit ng isang listahan ng mga link dito, ngunit ang kalakalan-off ay magiging potensyal na kailangan namin ng higit pang memory, tumatagal ng kaunti pang panahon, ngunit hindi namin huwag limitahan ang taas ng stack, marami tulad ng display case Mather ni Maaaring limitahan ang laki ng stack, at iba ang mga ito ay disenyo ng mga desisyon o mga opsyon na magagamit sa amin sa huli. Kaya sa mga data kaayusan, sinimulan namin sa nakakakita ng mga bagong itaas na hangganan potensyal sa kung ano ang dati ay sobrang mabilis at kung saan kami ay umalis off ngayon at kung saan kami ay umaasa upang makakuha ng sa ay sa Miyerkules, bibigyan namin ng simulan upang tumingin sa isang data istraktura na nagbibigay-daan sa amin sa paghahanap sa pamamagitan ng data sa oras ng pagtatapos log muli. At nakita namin na, pagpapabalik, sa linggo zero at isa sa binary paghahanap o hatiin at mapaglabanan. Ito ay babalik at mas mahusay pa, ang banal na Kopita para ito Miyerkules ay upang makabuo ng mga istraktura ng data na tumatakbo tunay o theoretically in tapat na oras, kung saan ang hindi mahalaga kung gaano karaming milyon o bilyong bagay kami ay may sa istraktura ng data, ito ay kumuha sa amin constant time, siguro isang hakbang o dalawang hakbang o 10 mga hakbang, ngunit pare-pareho ang bilang ng mga hakbang sa paghahanap sa pamamagitan na istraktura ng data. Na sa katunayan ay ang banal na Kopita ngunit higit pa sa na sa Miyerkules. Tingnan ang ya pagkatapos. 

[MUSIC nagpe-play]