[Powered by Google Translate] [Linggo 6] [David J. Malan] [Harvard University] [Ito ay CS50.] [CS50.TV] 

Ito ay CS50, at ito ay ang simula ng Linggo 6, kaya ng ilang mga bagong tool ay magagamit na ngayon para sa iyo upang samantalahin ng, ang unang na kung saan ay tinatawag na CS50 Estilo. Logro ay kung ikaw ay tulad ng sa akin o anumang ng Fellows pagtuturo, malamang na nakita mo ang isang programa na may estilo hitsura ng kaunti ng isang bagay tulad nito. Siguro simulan mo paggupit ilang mga sulok late sa gabi, o makikita mo haharapin ang mga ito sa ibang pagkakataon, at pagkatapos ng tf o CA ay sa panahon ng mga oras ng opisina. Pagkatapos ito ay mahirap para sa amin upang basahin. Well, ang code na ito syntactically tamang, at ito makatipon, at ito ay aktwal na patakbuhin. Ngunit ito ay talagang hindi isang 5 para sa estilo. 

Ngunit ngayon, kung pumunta kami sa direktoryong ito dito at mapansin na mayroon akong conditions2.c- at nagpatakbo ako ito bagong utos, style50, sa file na ito conditions2.c, Ipasok, mapapansin na ito alam sa akin na ito ay inilarawan sa pangkinaugalian. Gedit napansin na ang file ay nabago na sa disk, at kung i-click ko reload, ngayon ang lahat ng iyong mga problema ay awtomatiko. [Palakpakan] Na ang isa sa mga bagay na ginawa namin ito weekend. Mapagtanto na ito ay hindi lubos na pagsisisi dahil may mga code ilang na hindi lang ito ay upang stylize perpektong, ngunit Napagtanto ito ngayon ang isang tool na maaari mong samantalahin kung lamang sa maglinis ang ilan sa mga mas errantly inilagay kulot tirante at ang gusto. 

Ngunit mas nakakahimok ngayon ay CS50 Check. Sa CS50 Check, maaari mong aktwal na isagawa ang parehong mga pagsubok sa katumpakan sa iyong sariling code na ang mga Fellows ng pagtuturo ay magagawang. Ito ay isang command line utility na ay ngayon sa appliance sa lalong madaling gawin mo isang update50 ng bawat pset 4 pagtutukoy, at gamitin ito mahalagang tulad nito. Patakbuhin mo ang command check50. Pagkatapos pumasa ka sa isang argument ng linya ng command, o mas karaniwang kilala bilang isang lumipat o isang flag. Sa pangkalahatan, ang mga bagay na may gitling ay tinatawag na lumipat sa isang programa ng command line, kaya-c tinutukoy ang mga tseke na gusto mong patakbuhin. 

Ang mga pagsubok na gusto mong patakbuhin ang katangi-tangi na kinilala sa pamamagitan ng ang string na ito, 2012/pset4/resize. Sa ibang salita, ito lamang ay isang arbitrary ngunit natatanging string na ginagamit namin para makilala ang mga pagsubok na kawastuhan pset 4. At pagkatapos mong tukuyin ang isang puwang na nakahiwalay na listahan ng mga file na nais mong i-upload sa CS50 Suriin para sa pagtatasa. Halimbawa, kung pumunta ako sa aking solusyon dito para resize.c- hayaan mo akong magbukas ng mas malaking terminal na window- at pumunta ako magpatuloy at patakbuhin sabihin nating check50-c 2012/pset4/resize, at pagkatapos kong magpatuloy at tukuyin ang mga pangalan ng file, resize.c, at pagkatapos ay pindutin ang Enter, compresses, ito upload, sumusuri, at Nabigo ko lang ng buong bungkos ng mga pagsubok. Ang isa sa pula sa kaliwang tuktok sabi na resize.c at bmp umiiral. Na ang test. Na ang tanong na hiniling namin. At masaya dahil ang sagot ay maling. Ang puting teksto sa ibaba nito sabi inaasahan bmp.h na umiiral, at lamang na Kasalanan ko. Nakalimutan ko ang upang i-upload ang mga ito, kaya kailangan ko upang i-upload ang parehong mga file, resize.c at bmp.h. Ngunit ngayon mapansin ang lahat ng iba pang mga pagsubok sa dilaw dahil hindi nila patakbuhin, at kaya ang SMILEY mukha vertical dahil siya alinma'y hindi masaya ni malungkot, ngunit mayroon kaming sa pagtutumpak na isyu sa pula bago tumakbo ang mga iba pang mga tseke ay. 

Hayaan akong ayusin ito. Hayaan akong mag-zoom out at muling patakbuhin ito, oras na ito na may bmp.h din sa command line, Ipasok, at ngayon kung lahat ng napupunta na rin, ito upang suriin at pagkatapos ay bumalik sa isang resulta ng hawakan ang iyong hininga- lahat ng berde, na nangangahulugan na ako ginagawa talagang na rin sa pset 4 sa ngayon. Maaari mong makita at magpakilala mula sa mapaglarawang teksto dito kung ano mismo ang ay sumubok kami. Sinubukan namin ang unang ko ang mga file ay umiiral? Pagkatapos ay sinubukan namin ang resize.c makatipon? Pagkatapos sumubok kami ay hindi ito baguhin ang laki ng isang 1x1 pixel BMP kapag n, ang resize kadahilanan, 1. Ngayon, kung mayroon kang mga ideya kung ano n ay, ikaw ay sa sandaling sumisid sa pset 4, ngunit lamang ay isang katinuan suriin upang tiyakin na hindi ka pagpapalit ng sukat isang imahe sa lahat kung ang resize kadahilanan ay 1. Kung, sa pamamagitan ng kaibahan, resizes isang 1x1 pixel sa isang 1x1 pixel BMP sa 2x2 tama kapag n ay 2, pagkatapos ay katulad, minahan bumubuo nang naaayon. 

Sa maikli, ito ay nilalayong, isa, gawin ang tumatawid ng daliri ng equation tama bago mo isumite ang iyong pset. -Alam sa iyo nang eksakto kung ano ang iyong tf ay madaling malaman kapag pumunta tungkol sa pagsusumite ng ilan ng mga set ng problema, at rin ang paturo pagganyak talaga upang ilagay ng pagkakataon sa harap mo upang na kapag alam mo ang walang pagsubok na may mga bug sa iyong code at pagsubok na hindi pumasa sa, maaari mong ilagay sa mas epektibong oras up harap upang malutas ang mga problema sa halip na mawala ang mga puntos, makakuha ng feedback mula sa iyong tf, at pagkatapos ay pumunta, "Ahh," tulad ng dapat kong naisip na out. Ngayon hindi bababa sa isang tool upang matulungan kang makahanap na. Hindi ito upang ituro kung saan ay ang bug, ngunit ito ay sabihin sa iyo kung ano ang palatandaan nito. 

Ngayon ay nauunawaan ang mga pagsubok na ito ay hindi kinakailangang malawakan. Lamang dahil makakakuha ka ng isang screen na puno ng berdeng SMILEY mukha ay hindi nangangahulugan na ang iyong code ay perpekto, ngunit ito nangangahulugan na nakapasa ito sa ilang mga pagsubok na inireseta ng spec. Minsan hindi namin ilabas ang mga tseke. Halimbawa, sinong may kagagawan, isa sa mga aspeto ng pset 4, ang uri ng disappointing kung kami magbibigay sa iyo ng ang sagot sa kung ano ito ay, at mayroong isang bilang ng mga paraan upang ipakita ang na ang tao sa ingay na pula. Spec ay palaging tinukoy sa hinaharap para sa pset 5 pasulong kung ano ang sumusuri ang umiiral para sa iyo. Mapapansin mo ito puting URL sa ibaba. Sa ngayon, ito ay lamang diagnostic output. Kung ikaw bisitahin ang URL na iyon, makakakuha ka ng isang buong grupo ng mabaliw, misteriyoso mensahe na isa kang upang tumingin sa pamamagitan ng, ngunit karamihan ito ay para sa mga tauhan ng upang maaari naming diagnose at i-debug ang mga bug sa check50 mismo. 

Nang walang linggal, sabihin ilipat sa kung saan kami tumigil. CS50 library na kinuha namin para sa ibinigay para sa ilang mga linggo, ngunit pagkatapos ay noong nakaraang linggo, nagsimula kaming pagbabalat pabalik isa ng ang mga layer nito. Nagsimula kami bukod string sa pabor ng kung ano ang sa halip? [Mag-aaral] magpasinda. Magpasinda *, na kung saan ay magpasinda * lahat ng oras na ito, ngunit ngayon ay hindi namin upang magpanggap na ito ay isang aktwal na data ng uri ng string. Sa halip, ito ay isang kasingkahulugan ng mga uri para sa pansamantalang trabaho *, at ang string ng isang pagkakasunud-sunod ng mga character, kaya bakit ang kabuluhan upang kumatawan ng mga string bilang magpasinda * s? Ano ang isang pansamantalang trabaho * kumatawan sa konteksto ng konseptong ito ng isang string? Oo. >> [Mag-aaral] Ang unang character. Magandang, ang unang character, ngunit hindi pa ang unang character. Ng [mga mag-aaral] Address. Magandang, ang address ng unang character. Ang lahat na kinakailangan upang kumakatawan sa isang string sa memorya ng isang computer ay ang natatanging address ng mga unang byte. Hindi mo na malaman kung gaano katagal ito ay dahil kung paano maaari mong malaman na ang dynamic? [Mag-aaral] String haba. Maaari mong tawagan ang haba ng string, mahusay, ngunit kung paano gumagana ang string haba? Ano ang gagawin? Oo. [Mag-aaral] Panatilihin ang pagpunta hanggang sa makuha mo ang mga null karakter. Oo, eksakto, ito lamang iterates na may para sa loop, habang loop, anumang mula * sa dulo, at sa dulo ay kinakatawan ng \ 0, ang tinatawag na nul karakter, nul, hindi malito null, na kung saan ay isang pointer, na kung saan ay sa pakikipag-usap muli ngayon. 

Peeled namin pabalik isang layer ng GetInt, at pagkatapos ay kinuha namin ang isang pagtingin sa GetString, at isipin ang na ang parehong mga function, o talagang, GetString, ay gamit ang isang tiyak na function na upang aktwal na-parse, na, basahin o pag-aralan, ang input ng user. At kung ano na ang mga bagong function na? Scanf o sscanf. Aktwal na ito ay sa loob ng ilang iba't ibang mga lasa. Mayroong scanf, may sscanf, may fscanf. Sa ngayon, bagaman, sabihin tumutok sa pinaka madali na isinalarawan, at ipaalam sa akin sige at buksan up sa appliance isang file na tulad nito, scanf1.c. Ito ay isang napaka-simpleng programa, ngunit ang isang bagay na hindi namin nagawa mo na nang walang tulong ng CS50 library. Ito ay nakakakuha ng isang int mula sa isang user. Paano ito gumagana? Well, sa linya 16 doon, mapansin na idedeklara namin ang isang int tinatawag x, at sa puntong ito sa kuwento, ano ang halaga ng x? [Hindi marinig na mag-aaral ng tugon] [David M.] Kanan, na nakakaalam, ilang basura halaga potensyal na, kaya sa 17, kami lang sabihin sa user bigyan ako ng isang numero, mangyaring, at hakbang 18 kung saan ito ay nakakakuha ng mga kawili-wiling. Mukhang Scanf upang humiram ng isang ideya mula sa printf na ito ay gumagamit ng mga code ng format sa mga panipi. % D ng kurso ng decimal numero. Ngunit kung bakit ako pagpasa sa & x sa halip ng x? Ang dating ay tama. Oo. [Hindi marinig na mag-aaral ng tugon] Eksakto, kung ang layunin ng programang ito, tulad ng pag-andar GetInt mismo, ay upang makakuha ng isang int mula sa user Maaari ba akong magpasa ng mga function ang lahat ng mga variable na gusto ko, ngunit kung hindi ko ipasa ang mga ito sa pamamagitan ng reference o sa pamamagitan ng address o sa pamamagitan ng pointer, ang lahat ng mga kasingkahulugan para sa mga layuning ngayon, ang function na ay walang kakayahan upang baguhin ang mga nilalaman ng variable na. Ito ay pumasa sa isang kopya tulad ng maraming surot na bersyon ng makipagpalitan na namin ang uusapang tungkol sa ilang beses ngayon. 

Ngunit sa halip, sa pamamagitan ng paggawa at x, literal ako pagpasa sa kung ano? [Mag-aaral] Ang address. >> Ang address ng x. Ito ay tulad ng pagguhit ng isang mapa para sa mga function na tinatawag na scanf at sinasabi dito, mga ito ay mga direksyon sa isang tipak ng memory sa computer na maaari kang pumunta-imbak ng ilang integer. Upang para sa sscanf sa ngayon gawin na ano operator, ano piraso ng syntax ito upang gamitin kahit na hindi namin makita ito dahil may ibang tao sinulat ni ang pagpapaganang ito? Sa ibang salita - kung ano ang na? [Mag-aaral] X basahin. Mayroong pagpunta sa ilang pagbabasa, ngunit lamang tungkol sa x dito. Kung ang scanf ay nakapasa sa address ng x, syntactically, ano operator ay sumunod na umiiral sa isang lugar sa loob ng scanf ng pagpapatupad upang scanf aktwal na magsulat ng isang numero ng 2 sa address na iyon? Oo, kaya ang *. Manariwa sa diwa na * aming dereference operator, na mahalagang ibig sabihin nito ay pumunta doon. 

Sa sandaling iyong ipinasa address, tulad ng kaso dito, scanf ay marahil-kung namin aktwal na tumingin sa buong source code nito- paggawa ng * x o ang katumbas sa aktwal na pumunta sa address na iyon at maglagay ng ilang mga halaga doon. Ngayon, bilang para sa kung paano scanf nakakakuha ng input mula sa keyboard, iwagayway namin ang aming mga kamay para sa ngayon. Lamang ipagpalagay na operating system ay nagbibigay-daan sa sscanf makipag-usap sa keyboard ng user, ngunit sa puntong ito sa ngayon sa linya 19, kapag lamang namin i-print ang mga x, tila ang kaso na scanf ilagay int sa x. Iyon mismo kung paano scanf gumagana, at isipin ang huling linggo na kung paano GetString at GetInt at ang iba pang mga pamilya ng mga function huli gumagana, kahit na may bahagyang pagkakaiba tulad sscanf, na nangangahulugan na i-scan ang isang string sa halip na ang keyboard. Ngunit sabihin tumagal ng isang pagtingin sa isang maliit na pagkakaiba ng ito. Sa scanf2, aktwal na ako screwed up. Ano ang mali-at ko bang itago ang mga komento na nagpapaliwanag ng maraming- kung ano ang mali sa programang ito, bersyon 2? Teknikal bilang posibleng oras na ito. Mukhang medyo magandang. Mabuti ito indent, ngunit- okay, kung paano tungkol sa sabihin pungusin ito sa mas maikling tanong? Linya 16. Ano ang paggawa sa linya 16 sa tumpak na ngunit teknikal na Ingles? Pagkuha ng kaunti mahirap. Oo, Michael. [Mag-aaral] ito na tumuturo sa ang unang titik ng isang string. 

Okay, malapit. Hayaan akong tweak na nang kaunti. Na tumuturo sa ang unang titik ng isang string, ang deklarasyon ng variable na tinatawag na buffer na magtuturo sa unang address ng isang string, o sa halip, na magtuturo higit na partikular sa isang pansamantalang trabaho. Pansinin na hindi ito aktwal na tumuturo kahit saan dahil walang operator sa pagtatalaga. Walang katumbas sign, kaya ang lahat ng ginagawa namin ay paglaan ng variable na tinatawag na buffer. Ito ay nangyayari sa 32 bit dahil ang isang pointer, at ang nilalaman ng buffer baka kalaunan ay naglalaman ng isang address ng isang pansamantalang trabaho, ngunit sa ngayon, kung ano ang buffer naglalaman? Ilang bogus, na nakakaalam, ang ilang mga halaga ng basura, dahil hindi pa namin tahasang nasimulan ito, kaya hindi namin dapat ipagpalagay anumang. Okay, kaya ngayon linya 17-ano ang linya 17? Siguro na magpainit up ito. Mga Kopya isang string, i-right? Mga Kopya String mangyaring. 

Linya 18 uri ng pamilyar na ngayon sa na lamang namin nakita ang isang pagkakaiba ng mga ito ngunit may isang iba't ibang mga format ng code, kaya sa ika-18 linya, kami ay nagsasabi sa scanf dito ang address ng isang tipak ng memorya. Gusto kong mong tumawag sa isang string, tulad ng ipinahiwatig ng% s, ngunit ang problema ay na hindi namin nagawa ang ilang mga bagay dito. Ano ang isa sa mga problema? [Mag-aaral] Ito ay sinusubukang sa dereference null pointer. Magandang, null o kung hindi man ay hindi kilala na mga payo. Ka handing scanf ng isang address, ngunit sinabi mo lang ng ilang sandali ang nakalipas na ang address na ilang basura halaga dahil hindi namin aktwal italaga ito sa anumang bagay, at kaya sinasabi mo sa scanf mabisa pumunta maglagay ng string dito, ngunit hindi namin alam kung saan dito pa ay, kaya hindi namin na aktwal na inilalaan memory para sa buffer. Bukod dito, kung ano ang hindi mo rin kahit na nagsasabi ng scanf? Ipagpalagay na ito ay isang tipak ng memorya, at ito ay hindi isang halaga ng basura, ngunit ka pa rin hindi na nagsasabi scanf bagay na mahalaga. [Mag-aaral] Saan aktwal na ito ay, ang ampersand. Ampersand, kaya sa kasong ito, ito ay okay. Dahil buffer na ipinahayag bilang isang pointer * piraso ng syntax, hindi namin kailangang gamitin ang ampersand dahil ito ay isang address, ngunit tingin ko Narinig ko ito dito. [Mag-aaral] gaano kalaki? Mabuti, hindi kami ay nagsasabi sa scanf kung gaano kalaki ang buffer ito, na nangangahulugan na kahit na kung buffer ay isang pointer, sinasabi namin scanf, ilagay ang isang string dito, ngunit dito 2 bytes, maaari itong 10 bytes, maaaring ito ay isang megabyte. Ang Scanf ay walang mga ideya, at dahil ito ay isang tipak ng memory siguro, ito ay hindi isang string pa. Lamang ito isang string sa sandaling sumulat ka ng mga character at \ 0 na tipak ng memory. Ngayon lang ilang tipak ng memorya. Scanf hindi alam kapag upang itigil ang sulat sa address na iyon. 

Kung manariwa sa diwa mo ang ilang mga halimbawa sa nakaraan kung saan ko random type sa keyboard sinusubukan sa pag-apaw ng buffer, at usapan natin sa Biyernes tungkol sa eksakto na. Kung ang isang kalaban sa paanuman injects sa iyong programa sa isang mas mas malaking salita o pangungusap o parirala ikaw ay umaasa maaari mong kumalat at maminsala isang tipak ng memorya, na maaaring magkaroon ng hindi magandang kahihinatnan, tulad ng pagkuha sa buong programa mismo. Kailangan naming ayusin ito sa paanuman. Hayaan akong mag-zoom out at pumunta sa bersyon 3 ng programang ito. Na ng kaunti mas mahusay. Sa ang bersyon na ito, mapansin ang pagkakaiba. Sa ika-16 linya, muli ako deklarasyon ng isang variable na tinatawag na buffer, ngunit ano ito ngayon? Isang array ng 16 karakter. Ito ay mabuti dahil nangangahulugan ito na maaari ko ngayon sabihin ng scanf dito ay isang aktwal na tipak ng memory. Maaari ka nang mag-isip ng array bilang payo na ngayon, kahit na hindi sila aktwal na katumbas. Makikita nila kumilos naiiba sa iba't ibang konteksto. Ngunit ito ay tiyak ang kaso na ang buffer ay tumutukoy sa 16 magkadikit char dahil iyon ang array ng at para sa ilang mga linggo ngayon. 

Dito, sinasabi ako sa scanf narito ang isang tipak ng memory. Oras na ito, ito ay talagang isang tipak ng memory, ngunit bakit pa rin ang programang ito exploitable? Ano ang mali pa rin? Ko ang sinabi bigyan ako ng mga 16 bytes ngunit- [Mag-aaral] Ano kung type sa higit sa 16? Eksakto, kung ano ang kung ang mga uri ng user sa 17 character o 1700 character? Sa katunayan, sabihin makita kung hindi namin mai-biyahe sa paglipas ng pagkakamali na ito ngayon. Ito ay mas mahusay na ngunit hindi perpekto. Hayaan akong magpatuloy at patakbuhin ang gumawa scanf3 upang makatipon ng programang ito. Hayaan akong magpatakbo ng scanf3, String mangyaring: kumusta, at tila namin na okay. Hayaan akong subukan ang isang bahagyang mas mahaba, kumusta doon. Okay, sabihin ko kumusta doon kung paano ikaw ay ngayon, ang Enter. Pagkuha ng uri ng masuwerteng dito, sabihin kamustahin doon kung paano ikaw ay. Diyablo. Okay, kaya namin nakuha masuwerteng. Hayaan ang mga makita kung hindi namin maaaring ayusin ito. Hindi, ito ay hindi pagpunta sa ipaalam sa akin kopyahin. Natin subukan ito muli. Lahat ng karapatan, tumayo sa pamamagitan ng. Namin makita kung gaano katagal ang maaari kong magpanggap upang tumuon habang ginagawa ito. Diyablo. Na sa halip naaangkop, aktwal. Doon kami. Point ginawa. 

Ito, nakakahiya kahit na ito din ay, ito ay din isa sa mga mapagkukunan ng mahusay na pagkalito kapag pagsulat ng mga programa na may bug dahil manifest nila ang kanilang mga sarili lamang ito nang isang beses sa isang habang minsan. Katotohanan ay na kahit na ang iyong code ay ganap na pinaghiwa, maaaring ito lamang ganap na pinaghiwa-minsan dahil minsan, mahalagang kung ano ang mangyayari sa operating system allocates ng kaunti pa sa memory kaysa sa iyo na aktwal na kailangan para sa anumang dahilan, at kaya wala pang gumagamit ang memorya pagkatapos ng iyong tipak ng 16 na mga character, kaya kung pumunta sa 17, 18, 19, anumang, hindi tulad ng isang malaking deal. Ngayon, ang computer, kahit na ito ay hindi pag-crash ng sa puntong iyon, maaaring kalaunan gamitin byte numero 17 o 18 o 19 para sa iba pa, kung saan ay ituro ang iyong mga data na inilagay mo doon, kahit na labis mahaba, ay pagpunta upang makakuha ng mapapatungan potensyal na sa pamamagitan ng ilang mga iba pang mga function na. Hindi ito nangangahulugang mananatiling buo, ngunit hindi kinakailangang ito ay magdudulot ng seg kasalanan. Ngunit sa kasong ito, ibinigay ko sa wakas sapat na mga character na mahalagang ko Lumagpas sa aking segment ng memorya, at magdaya, operating system sinabing, "Paumanhin, hindi magandang, segmentation fault." 

At ipaalam sa makita ngayon kung ano ang nananatiling dito sa aking direktoryo- mapansin na mayroon akong ang file na ito dito, ang core. Pansinin na ito ay muli na tinatawag na core dump. Ito ay mahalagang isang file na naglalaman ng nilalaman ng memorya ng iyong programa sa punto kung saan ito nag-crash, at subukan ang isang maliit na halimbawa dito hayaan mo akong pumunta sa dito at patakbuhin ang gdb sa scanf3 at pagkatapos ay tukuyin ang isang third argument na tinatawag na core, at mapansin dito na kung ko bang ilista ang mga code, magagawa naming gaya ng dati may gdb upang simulan ang paglalakad sa pamamagitan ng programang ito, at maaari ba akong magpatakbo ng ito at sa lalong madaling panahon bilang ko pindutin bilang ang utos ng hakbang sa gdb- sa lalong madaling pindutin ko ang potensyal na maraming surot linya matapos ang pagta-type sa isang malaking string, Ko sa aktwal na kilalanin ang mga ito dito. Higit pa sa ito, bagaman, sa seksyon sa mga tuntunin ng lungkot core at ang gusto upang maaari mong aktwal sundutin sa paligid sa loob ng dump core at makita sa kung ano ang linya Nabigo ang programa mo. Anumang mga katanungan pagkatapos ay sa mga payo at sa mga address? Dahil ngayon sa, kami ay pagpunta upang simulan ang pagkuha para sa ipinagkaloob na ang mga bagay na ito umiiral at alam namin kung ano mismo ang mga ito. Oo. 

[Mag-aaral] Paano dumating hindi mo maglagay ng isang ampersand tabi sa bahagi- Magandang tanong. Paano dumating ako ay hindi maglagay ng isang ampersand sa tabi ng character array ng ginawa ko dati karamihan sa aming mga halimbawa? Ang maikling sagot ay array ng kaunti espesyal. Maaari ka nang tingin ng buffer ng aktwal na pagiging isang address, at ito lamang kaya mangyayari ang kaso na ang mga square bracket pagtatanda ay isang kaginhawahan upang maaari naming pumunta sa bracket 0, bracket 1, bracket 2, nang hindi kinakailangang gamitin ang * pagtatanda. Na ang isang bit ng isang maliit na kasinungalingan dahil array at pointer , sa katunayan, Medyo naiiba, ngunit maaaring sila madalas ngunit hindi laging magamit ng salitan. Sa maikling, kapag ang isang function na ay umaasa ng pointer sa isang tipak ng memorya, maaari mong ipasa ang mga ito ng isang address na ay ibinalik ng malloc, at kami na makita ang malloc muli mamaya, o maaari mong ipasa ang mga ito ang pangalan ng isang array. Hindi mo kailangang gawin ang ampersand may array dahil ang mga ito ay mahalagang i address. Iyon ay isang pagbubukod. Ang mga square bracket gawin silang espesyal na. 

Puwede bang maglagay ng isang ampersand susunod sa buffer? Hindi sa kasong ito. Na hindi gagana dahil, muli, ng kasong ito corner kung saan ang mga array ay hindi pa aktwal na address. Ngunit makikita marahil namin bumalik na bago mahaba sa iba pang mga halimbawa. Natin subukan upang malutas ang isang problema dito. Mayroon kaming isang istraktura ng data na aming ginagamit para sa ilang oras na kilala bilang isang array. Kaso sa point, kung ano lamang namin ay may. Ngunit array ay may ilang mga upsides at downsides. Array ay magaling bakit? Ano ang isang bagay na gusto sa iyo ang lawak na gusto mo array-tungkol array? Ano ang maginhawang tungkol sa mga ito? Ano ang nakapanghihimok? Bakit namin ipakilala ang mga ito sa unang lugar? Oo. [Mag-aaral] Maaari silang mag-imbak ng maraming data, at hindi mo na kailangang gamitin ang isang buong bagay. Maaari mong gamitin ang isang seksyon. Mabuti, na may isang array maaari kang mag-imbak ng maraming data, at hindi mo kinakailangang upang gamitin ang lahat ng ito, kaya maaari mong overallocate, na maaaring maging maginhawa kung hindi mo alam nang maaga kung gaano karami ng isang bagay sa inaasahan. 

GetString ay isang perpektong halimbawa. GetString, na nakasulat sa pamamagitan ng sa amin, ay walang mga ideya kung gaano karaming karakter ang aasahan, kaya ang katunayan na maaari naming magtalaga ng mga chunks ng magkadikit memory ay mabuti. Array rin malutas ang isang problema na nakita namin ng ilang linggo na ang nakakaraan ngayon kung saan ang iyong code ay nagsimulang upang malipat sa isang bagay na napaka mahinang dinisenyo. Manariwa sa diwa na nilikha ko ang isang mag-aaral ng istraktura na tinatawag na David, at pagkatapos na talagang isang alternatibong, bagaman, sa pagkakaroon ng isang variable na tinatawag na pangalan at isa pang variable na tinatawag na, tingin ko, ang bahay, at isa pang variable na tinatawag na ID dahil sa na kuwento pagkatapos ko nais upang ipakilala ang iba pa gusto Rob sa programa, kaya pagkatapos ko nagpasya maghintay ng isang minuto, Kailangan ko upang palitan ang pangalan ng mga variable na ito. Sabihin tumawag minahan NAME1, ID1, house1. Sabihin tumawag Rob ng NAME2, house2, ID2. Ngunit pagkatapos na maghintay ng isang minuto, kung ano ang tungkol sa Tommy? Pagkatapos kami ay may tatlong higit pang mga variable. Ipinakilala namin ang ibang tao, apat na hanay ng mga variable. Ang mundo ay nagsimula upang makakuha ng magulo masyadong mabilis, kaya ipinakilala namin structs, at kung ano ang nakapanghihimok tungkol sa isang struct? Ano ang isang C struct sabihin gagawin mo? Ito ay talagang mahirap ngayon. Ano? >> [Hindi marinig na mag-aaral tugon] Oo, partikular, typedef nagpapahintulot sa iyo na lumikha ng isang bagong uri ng data, at struct, ang struct keyword, ay nagbibigay-daan sa iyo upang encapsulate conceptually na may kaugnayan piraso ng data nang magkasama at pagkatapos noon ay tumawag sa kanila ng isang bagay tulad ng isang mag-aaral. 

Na ay mabuti dahil ngayon maaari naming modelo higit pa uri ng conceptually pare-pareho ang paniwala ng isang mag-aaral sa isang variable kaysa mang pagkakaroon ng isa para sa isang string, isa para sa isang ID, at iba pa. Array ay magaling dahil pinapayagan nila sa amin upang simulan ang paglilinis up ng aming code. Ngunit ano ang downside ngayon ng isang array? Ano ang hindi mo maaaring gawin? Oo. [Mag-aaral] Mayroon kang malaman kung gaano kalaki ito ay. Mong malaman kung gaano kalaki ito ay, sa gayon ito ay uri ng isang sakit. Yaong mo may bago programming karanasan alam na sa maraming wika, tulad ng Java, maaari mong hilingin sa isang tipak ng memorya, partikular na isang array, kung gaano kalaki ang sa iyo, na may haba, ari-arian, kaya na magsalita, at na talagang maginhawa. Sa C, hindi kahit ka maaaring tumawag strlen sa isang generic na array dahil strlen, ng salita ay nagpapahiwatig, ay para lamang sa string, at maaari mong malaman kung ang haba ng isang string dahil sa ito tao convention ng pagkakaroon ng \ 0, ngunit isang array, mas generically, ay isang tipak ng memorya. Kung ito ay isang array ng ints, mayroong pagpunta sa ilang mga espesyal na character sa dulo naghihintay para sa iyo. Mong matandaan ang haba ng array. Isa pang downside ng isang array reared ang ulo nito sa mismong GetString. Ano ang isa pang downside ng isang array? Sir, lamang sa iyo at sa akin ngayon. [Hindi marinig na mag-aaral tugon] >> Ito ay kung ano ang? Ito ay ipinahayag sa stack. Okay, ipinahayag sa stack. Bakit hindi mo gusto na? [Mag-aaral] Dahil ito ay makakakuha reused. Maipo reused. Okay, kung ikaw ay gumamit ng isang array upang magtalaga ng memory, hindi mo maaaring, halimbawa, ibalik ito dahil ito sa stack. Okay, na dehado. At kung paano tungkol sa isa pang may isang array? Sandaling maglaan ka, ikaw uri ng screwed kung kailangan mo ng karagdagang espasyo kaysa sa array na may. 

Pagkatapos ay ipinakilala namin, manariwa sa diwa, malloc, na nagbigay sa amin ng kakayahan upang dynamic na magtalaga ng memory. Ngunit ano kung sinubukan naming ng ibang mundo sa sama-sama? Paano kung gusto naming malutas ng ilang mga problema upang namin sa halip na aking panulat nahulog tulog dito- paano kung gusto namin sa halip sa mahalagang lumikha ng isang mundo na hindi na tulad nito? Ito ay isang array, at, siyempre, ang ganitong uri ng deteriorates sabay-sabay namin pindutin ang dulo ng array, at ako ngayon hindi na magkaroon ng espasyo para sa isa pang integer o isa pang character na. Paano kung namin uri ng preemptively sabihin na rin, bakit hindi namin mamahinga ang mga bisita ito kinakailangan na ang lahat ng mga chunks ng memory magkadikit na bumalik upang i-back, at bakit hindi, kapag kailangan ko ng isang int o isang pansamantalang trabaho, lamang ninyo akong bigyan ng espasyo para sa isa sa mga ito? At kapag kailangan ko ng isa pang, bigyan ako ng isa pang espasyo, at kapag kailangan ko ng isa pang, bigyan ako ng isa pang espasyo. Ang kalamangan na kung saan ngayon na kung ibang tao tumatagal ang memory sa paglipas dito, hindi sang-ayon. Kukunin ko ang karagdagang tipak ng memory dito at pagkatapos ay ang isang ito. 

Ngayon, ang tanging catch dito ay na ito halos nararamdaman tulad ng mayroon akong isang buong grupo ng mga iba't ibang mga variable. Ito nararamdaman tulad ng limang iba't ibang mga variable potensyal. Ngunit ano kung magnakaw namin ng isang ideya mula sa mga string kung saan sa paanuman namin link mga bagay na ito nang sama-sama conceptually, at paano kung ginawa ko ito? Ito ang aking napaka-mahina iguguhit arrow. Ngunit ipagpalagay na ang bawat isa sa mga chunks ng memory tulis sa isa, at ang tao na ito, na may walang kapatid sa kanyang karapatan, ay walang tulad arrow. Ito ay sa katunayan kung ano ang tinatawag na naka-link listahan. Ito ay isang bagong istraktura ng data na nagbibigay-daan sa amin upang magtalaga ng isang tipak ng memory, pagkatapos ng isa pang, pagkatapos ng isa pang, pagkatapos ng isa pang, anumang oras nais naming panahon ng isang programa, at tandaan namin na hindi lahat ng mga ito sa paanuman kaugnay ng literal chaining iyon nang magkakasama, at ginawa namin na pictorially dito na may isang arrow. Ngunit sa code, kung ano ay ang mekanismo sa pamamagitan ng na maaari mong sa paanuman kumonekta, halos tulad ng simula, isang tipak sa ibang tipak? Maaari kaming gumamit ng pointer, i-right? Dahil talaga ang arrow na ng pagpunta mula sa tuktok na kaliwang parisukat, ito tao dito sa isang ito, maaaring maglaman sa loob ng square na ito hindi lamang ang ilang mga ints, hindi lamang ang ilang mga pansamantalang trabaho, ngunit kung ano kung ako aktwal na inilaan isang maliit na dagdag na espasyo upang ang ngayon, sa bawat isa sa aking mga chunks ng memory, kahit na ito ay pagpunta sa gastos sa akin, ngayon mukhang ng kaunti pa sa hugis-parihaba kung saan isa ng chunks ng memory ay ginagamit para sa isang numero, tulad ng numero 1, at pagkatapos ay kung ang tao na ito nag-iimbak ang bilang 2, ang iba pang mga tipak ng memorya ay ginagamit para sa isang arrow, o mas concretely, isang pointer. At ipagpalagay ko imbak ang bilang 3 sa dito habang ginagamit ko ito upang ituro sa tao na, at ngayon ang tao na ito, sabihin ipagpalagay na gusto ko lang tatlong tulad chunks ng memorya. Ako gumuhit ng linya sa pamamagitan ng na, na nagpapahiwatig null. May ay walang karagdagang character. 

Sa katunayan, ito ay kung paano namin pumunta tungkol sa pagpapatupad isang bagay na tinatawag na naka-link listahan. Isang naka-link na listahan ay isang bagong istraktura ng data, at ito ay isang stepping bato patungo sa mas may interes mga istraktura ng data na nagsisimula sa paglutas ng mga problema sa kahabaan ng linya ng Facebook-uri ng mga problema at Google-uri problema kung saan mayroon kang malaking hanay ng data, at hindi na mapuputol ito upang mag-imbak ang lahat contiguously at gamitin ang isang bagay tulad ng linear paghahanap o kahit na isang bagay tulad ng binary paghahanap. Gusto mong mas mahusay na mga panahon ng pagtakbo. Sa katunayan, isa ng Banal na Grails magpapadala kami makipag-usap tungkol sa ibang pagkakataon sa linggong ito o sa susunod na ay isang algorithm na tumatakbo ang oras ay pare-pareho. Sa ibang salita, ito laging tumatagal ang parehong dami ng oras kahit kung gaano kalaki ang input, at na sa katunayan ay nakapanghihimok, mas ito kaysa sa isang bagay logarithmic. Ano ito sa screen dito? Ang bawat isa ng parihaba ay kung ano mismo ang ko lang iginuhit sa pamamagitan ng kamay. Subalit ang bagay na ang lahat ng mga paraan sa kaliwa ay isang espesyal na variable. Ito ay upang maging isang solong pointer dahil ang gotcha na may naka-link na listahan, ng mga bagay na ito ay tinatawag na, na mayroon kang mag-hang patungo sa daloy ng mga sasakyan sa isang dulo ng naka-link na listahan. 

Tulad ng isang string, mayroon kang malaman ang address ng unang magpasinda. Parehong deal para sa mga naka-link na listahan. Mong malaman ang address ng unang tipak ng memory dahil mula doon, maaari mong maabot ang bawat iba pang mga. Downside. Ano ang presyo ay namin nagbabayad para sa masaklaw na karunungan ng pagkakaroon ng isang dynamic na malaki data ng istraktura na kung kailangan namin ng higit pang memory, fine, lamang magtalaga ng isa pang tipak at gumuhit ng isang pointer mula sa ang lumang sa bagong buntot ng listahan? Oo. [Mag-aaral] tumatagal tungkol sa dalawang beses ng mas maraming espasyo. Ito ay tumatagal ng dalawang beses ng mas maraming espasyo, kaya na talagang isang downside, at nasaksihan namin ito tradeoff bago sa pagitan ng oras at espasyo at kakayahang umangkop kung saan sa ngayon, hindi kailangan namin 32 piraso para sa bawat isa sa mga numerong ito. Namin talagang kailangan 64, 32 para sa numero at 32 para sa pointer. Ngunit hey, mayroon akong 2 gigabytes ng RAM. Ang pagdadagdag ng isa pang 32 bit dito at dito ay mukhang hindi na malaki ng isang pakikitungo. Ngunit para sa malaking hanay ng data, tiyak na nagdadagdag ng hanggang sa literal dalawang beses bilang magkano. Ano ang isa pang downside ngayon, o kung ano ang tampok na naming magbigay ng, kung kumakatawan namin ang listahan ng mga bagay na may naka-link na listahan at hindi isang array? [Mag-aaral] Hindi ka maaaring pagbagtas ito paurong. Hindi ka maaaring pagbagtas ito pabalik, kaya ikaw uri ng screwed kung ikaw ay naglalakad mula kaliwa hanggang kanang gamit ang isang para sa loop o habang loop at pagkatapos ay natanto, "Oh, gusto ko upang bumalik sa simula ng listahan." Hindi ka maaaring dahil ang mga payo lamang mula kaliwa papuntang kanan bilang Ipinapahiwatig ng mga arrow. 

Ngayon, maaari mong tandaan ang simula ng listahan sa isa pang variable, ngunit na ng pagiging kumplikado upang tandaan. Isang array, kahit gaano kalayo kang pumunta, maaari mong laging gawin minus, minus, minus, minus at bumalik mula sa kung saan ka dumating. Ano ang isa pang downside dito? Oo. [Hindi marinig na mag-aaral tanong] Maaari mong, kaya aktwal na iyong lang iminungkahi ng data ng istraktura tinatawag ng doble-link sa listahan, at sa katunayan, nais mong magdagdag ng isa pang pointer sa bawat isa ng mga parihaba na napupunta sa iba pang mga direksyon, ang bentahe ng ngayon ay maaari mong pagbagtas papunta at pabalik, ngayon ang downside kung saan ka gumagamit ng tatlong beses bilang maraming memorya bilang ginamit namin upang at din ng pagdaragdag hirap sa mga tuntunin ng code mayroon kang sumulat ito ng tama. Ngunit ito ay ang lahat marahil napaka-makatwirang tradeoffs, kung ang pagkabaligtad ay mas mahalaga. Oo. [Mag-aaral] Hindi mo rin maaaring magkaroon ng isang 2D na naka-link listahan. Mabuti, hindi ikaw talaga ay maaaring magkaroon ng isang 2D na naka-link na listahan. Maaari mong. Ito ay hindi halos bilang madaling bilang isang array. Tulad ng isang array, gawin mo open bracket, closed bracket, bukas bracket, sarado bracket, at makakakuha ka ng ilang mga 2-dimensional na istraktura. Maaari mong ipatupad ang 2-dimensional na naka-link na listahan kung gagawin mo add-bilang iminungkahi-isang third pointer sa bawat isa sa mga bagay na ito, at kung sa tingin mo tungkol sa isa pang listahan darating sa 3D estilo mula sa screen sa lahat sa atin, na lamang ng isa pang hanay ng mga uri. Maaari namin gawin ito, ngunit ito ay hindi kasing simple ng pag-type ng open bracket, square bracket. Oo. [Hindi marinig na mag-aaral tanong] Mabuti, kaya ito ay isang tunay na kabayong naninipa. 

Mga algorithm na kami pined sa paglipas ng, tulad ng oh, binary paghahanap, maaari kang maghanap ng isang hanay ng mga numero sa board o phone book upang mas mabilis kung gumamit ka hatiin at lupigin at binary paghahanap algorithm, ngunit binary paghahanap kinakailangan dalawang pagpapalagay. Isa, na ang data ay pinagsunod-sunod. Ngayon, maaari naming baka panatilihin ito pinagsunod-sunod, kaya marahil na hindi isang alalahanin, ngunit din ang binary paghahanap ipinapalagay na may random na pag-access sa listahan ng mga numero, at isang array ay nagpapahintulot sa iyo na magkaroon ng random na access, at sa pamamagitan ng random na pag-access, Ibig sabihin ko kung bibigyan ka isang array, kung gaano karaming oras ang magdadala sa iyo upang makakuha ng sa bracket 0? Isa pagpapatakbo, mo lamang gamitin ang [0] at hindi ka doon. Gaano karaming mga hakbang aabutin upang makakuha ng sa lokasyon 10? Isang hakbang, pumunta lamang sa [10] at nandoon ka. Sa pamamagitan ng kaibahan, paano mo makukuha sa ika-10 na integer sa isang naka-link na listahan? Mayroon kang magsimula sa simula dahil ka lamang pagtanda ang simula ng isang naka-link na listahan, tulad ng isang string ay remembered ng mga address ng mga unang magpasinda, at upang makita na ang ika-10 int o na ika-10 na character sa isang string, mayroon kang maghanap sa buong sumpain bagay. 

Muli, hindi namin paglutas ng lahat ng aming mga problema. Ipinapakilala namin mga bago, ngunit ito talagang depende sa kung ano ang iyong sinusubukan upang mag-disenyo para sa. Sa mga tuntunin ng pagpapatupad na ito, maaari naming humiram ng isang ideya mula sa mag-aaral na istraktura. Syntax ay katulad na katulad, maliban ngayon, ang ideya ng kaunti pa sa abstract sa bahay at pangalan at ID. Ngunit ipanukala ko na maaari naming magkaroon ng isang data na istraktura sa C na tinatawag na node, bilang ang huling salita sa slide ay nagmumungkahi, sa loob ng isang node, at ang node ng isang generic na lalagyan sa computer science. Karaniwang Ito ay iguguhit bilang isang bilog o isang parisukat o parihaba namin nagawa. At sa istraktura ng data na ito, mayroon kaming isang int, n, sa gayon ay ang bilang na nais ko na mag-imbak. Ngunit ano ang pangalawang linya na ito, struct node * susunod? Bakit ito tama, o kung ano ang papel ito bagay-play, kahit ng kaunti misteriyoso sa unang tingin? Oo. [Hindi marinig na mag-aaral ng tugon] Eksakto, kaya * uri ng spoils na ito ng pointer ng uri. Ang pangalan ng pointer na ito ay mang susunod, ngunit maaari kaming tinatawag na ito ang anumang gusto naming, ngunit kung ano ang pointer point na ito sa? [Mag-aaral] node isa pang. >> Mismong, mga punto sa isa pang tulad node. 

Ngayon, ito ay uri ng isang pagkausyoso ng C. Manariwa sa diwa na ang C ay basahin ng isang tagatala itaas hanggang sa ibaba, kaliwa papuntang kanan, na nangangahulugan na kung-ito ay isang maliit na naiiba mula sa kung ano ang ginawa namin sa mga mag-aaral. Kapag tinukoy na namin ang isang mag-aaral, namin ang aktwal na ay hindi maglagay ng salita doon. Sinabi lang ito typedef. Pagkatapos namin ay int id, pangalan ng string, string bahay, at pagkatapos ay mag-aaral sa ilalim ng struct. Deklarasyon Ito ay isang maliit na iba't ibang dahil, muli, ang C tagatala ng kaunti pipi. Lamang ito upang basahin itaas hanggang sa ibaba, kaya kung umabot sa 2nd na linya dito kung saan susunod ay ipinahayag at nakikita, oh, narito ang isang variable na tinatawag na susunod. Isang pointer sa isang struct node. Tagatala ay upang mapagtanto kung ano ang struct node? Hindi ko narinig ng mga bagay na ito bago, dahil ang salita ng node ay hindi maaaring kung hindi man ay lilitaw hanggang sa ibaba, kaya ay kalabisan na ito. Ang iyong sasabihin struct node dito, na maaari mong paikliin sa paglaon salamat sa typedef pababa dito, ngunit ito ay dahil namin ay tumutukoy sa istraktura mismo sa loob ng istraktura. Iyon ang isa gotcha doon. 

Ilang mga kawili-wiling mga problema ay pagpunta sa pumailanglang. Mayroon kaming isang listahan ng mga numero. Paano namin isingit ito? Paano namin ito maghanap? Paano namin tanggalin ang mula dito? Lalo na ngayon na mayroon kaming upang pamahalaan ang lahat ng mga payo. Tingin mo pointer uri ng isip-baluktot kapag mayroon kang isa sa mga ito lamang sinusubukang basahin ang isang int dito. Ngayon ay mayroon kaming upang manipulahin ang nagkakahalaga ng isang buong listahan. Bakit hindi namin ang aming 5-minutong break na dito, at pagkatapos ay makikita namin dalhin ilang mga tao up sa entablado upang gawin eksakto na. 

C ay mas mas masaya kapag ito kumilos. Sino ang gusto literal bang unang? Okay, darating sa up. Mo munang. Sino ang gusto mong maging 9? Okay, 9. Paano tungkol sa 9? 17? Ang isang maliit na grupo dito. 22 at 26 sa hilera na front. At pagkatapos ay kung paano tungkol sa isang tao doon na tulis sa. Ikaw ay 34. Okay, 34, ay sa up. Una ay banda roon. Okay, ang lahat ng apat ng ka guys. At kung sino ang sinasabi namin para sa 9? Sino ang aming 9? Sino ang talagang gustong 9? Lahat ng karapatan, darating, 9. Narito kami. 34, ipapakita namin nakamit mo banda roon. Ang unang bahagi ay gumawa ng sarili hitsura na. 26, 22, 17, mabuting. Kung maaari mong tumayo sa gilid, dahil kami ay pagpunta sa malloc sa isang sandali. 

Mabuti, mabuti. Okay, mahusay, kaya sabihin hilingin sa isang ilang mga katanungan dito. At aktwal na, kung ano ang iyong pangalan? >> Anita. Anita, okay, darating sa paglipas ng dito. Anita ay pagpunta upang makatulong sa amin sa uri ng malutas ang isa medyo simpleng tanong sa unang, na kung paano mo mahanap man o hindi ng isang halaga sa listahan? Ngayon, mapapansin na ang unang, kinakatawan dito sa pamamagitan ng Lucas, ng kaunti ibang, at kaya ang kanyang piraso ng papel ay sadyang patagilid dahil ito ay hindi pa matangkad at hindi tumagal ng maraming mga bits, kahit technically siya ay ang parehong laki ng papel na lang Pinaikot. Ngunit siya ay isang maliit na iba't ibang na siya 32 bit lamang para sa isang pointer, at ang lahat ng mga guys ay 64 bit, kalahati ng kung saan ay ang bilang, kalahati ng kung saan ay isang pointer. Ngunit ang pointer ay hindi itinatanghal, kaya kung ka guys maaari medyo awkwardly gamitin ang iyong kaliwang upang ituro sa tao na susunod sa iyo. At ikaw bilang 34. Ano ang iyong pangalan? Ari. Ari, kaya aktwal, pindutin nang matagal ang papel sa iyong kanang kamay, at kaliwang napupunta tuwid down na. Kumakatawan null ka sa kaliwa. 

Ngayon ang aming tao larawan ay napaka pare-pareho. Ito ay talagang kung paano payo gumagana. At kung maaari mong pumipi ng kaunti ang paraan na ito upang Hindi ako sa iyong paraan. Anita dito, hanapin sa akin ang bilang 22, ngunit ipinapalagay ng hadlang ng hindi tao na may hawak na piraso ng papel, ngunit ito ay isang listahan, at mayroon ka lamang Lucas upang magsimula sa dahil siya ay literal ang unang pointer. Ipagpalagay mo ang iyong sarili ng pointer, at kaya masyado kang kakayahan upang tumuro sa isang bagay. Bakit hindi ka magsimula sa pamamagitan ng pagturo sa kung ano mismo ang Lucas ay pagturo sa? Mabuti, at hayaan mo akong gumawa ng batas ito sa paglipas dito. Lamang para sa kapakanan ng talakayan, hayaan mo akong makuha ang isang blangkong pahina dito. Paano mo ispel ang pangalan? >> Anita. Okay, Anita. Sabihin nating node * Anita = Lucas. Well, hindi namin dapat tawagan ka Lucas. Dapat naming tumawag ka muna. Bakit ito sa katotohanan na pare-pareho sa katotohanan dito? Isa, unang Umiiral na. Una ay inilaan baka sa isang lugar hanggang dito. Node * unang, at ito ay inilalaan listahan sa paanuman. Hindi ko alam kung paano na nangyari. Na nangyari bago klase makapagsimula. Na ito ay naka-link na listahan ng mga tao ay nalikha na. At ngayon sa puntong ito ang kuwento na ito ay lahat ng pagpunta sa Facebook tila mamaya sa puntong ito sa kuwento, Anita ay nasimulan katumbas sa unang, na ay hindi nangangahulugan na ang mga puntos ng Anita sa Lucas. Sa halip, siya mga punto sa kung ano ang kanyang mga punto sa dahil ang parehong address na loob ng Lucas sa 32 bit - 1, 2, 3 - ay ngayon din sa loob ng Anita sa 32 bit - 1, 2, 3. 

Ngayon mahanap ang 22. Paano mo pumunta tungkol sa paggawa nito? Ano iyon? >> Point sa anumang. Ituro sa anumang, kaya sige at kumilos ito bilang pinakamahusay na maaari mong dito. Magandang, magandang, at ngayon ka na tumuturo sa kung ano ang iyong pangalan na may 22? Ramon. >> Ramon, kaya Ramon ay may hawak na hanggang 22. Ngayon nagawa mo na ang tseke. Ba Ramon == 22, at kung kaya, halimbawa, maaari naming nagbabalik ng tunay. Hayaan akong-habang ang mga guys tumayo dito medyo awkwardly- hayaan mo akong gawin ang isang bagay mabilis tulad bool mahanap. Ako pagpunta sa magpatuloy at sabihin (node ​​* listahan, int n). Akong karapatan sa iyo guys. Ko na lang ay sumulat ng ilang code. At ngayon ako pagpunta upang magpatuloy at gawin ito, node * Anita = listahan. At ako pagpunta sa magpatuloy at sabihin habang (Anita! = Null). 

Ang talinghaga dito ay nakakakuha ng isang maliit na stretch, ngunit habang (Anita! = Null), ano ang gusto kong gawin? Kailangan ko ng ilang mga paraan ng tumutukoy sa integer na Anita ay pagturo sa. Sa nakaraan, kapag nagkaroon kami istraktura, kung saan ang isang node ay, ginamit namin ang tuldok pagtatanda, at gusto naming sabihin isang bagay tulad ng anita.n, ngunit ang problema dito ay na Anita ay hindi isang struct per se. Ano siya? Niya ang isang pointer, kaya talaga, kung gusto naming gamitin ang tuldok pagtatanda- at ito ay pagpunta upang tumingin sadyang isang maliit na misteriyoso- mayroon kaming upang gawin ang isang bagay tulad ng pumunta sa kaliwang kamay ng anumang Anita ay pagturo sa at pagkatapos ay makakuha ng patlang na tinatawag n. Anita ay isang pointer, ngunit kung ano ay * Anita? Ano ang gagawin mong makita kapag ikaw ay pumunta sa kung ano Anita ay pagturo sa? Isang struct, node, at isang node, manariwa sa diwa, may isang patlang na tinatawag n dahil ito, isipin ang, mga 2 mga patlang, susunod at n, na nakita namin ng ilang sandali ang nakalipas sa dito. 

Upang aktwal na gayahin ito sa code, maaari naming gawin ito at sabihin kung ((* Anita). n == n), sa n na Naghahanap ako. Pansinin na ang function ay naipasa sa bilang mahalaga ako tungkol sa. Pagkatapos ay maaari kong magpatuloy at gawin ang isang bagay tulad ng return totoo. Iba Pa, kung na hindi ito ang kaso, ano ang gusto kong gawin? Paano ko isalin ang sa code kung ano Anita ginawa kaya intuitively sa pamamagitan ng paglalakad sa pamamagitan ng listahan? Ano ang dapat kong gawin dito upang gayahin Anita paglalaan na hakbang sa kaliwa, na hakbang sa kaliwa? [Hindi marinig na mag-aaral ng tugon] >> Ano iyon? [Hindi marinig na mag-aaral ng tugon] Mabuti, hindi isang masamang ideya, ngunit sa nakaraan, kapag ginawa namin ito, kami tapos Anita + + dahil na magdagdag ng numero 1 sa Anita, kung saan ay karaniwang ituro sa susunod na tao, tulad ng Ramon, o ang taong susunod sa kanya, o sa susunod na sa kanya tao ang linya. Ngunit hindi masyadong mahusay na dito dahil sa kung ano ang bagay na ito hitsura sa memory? Hindi na. Mayroon kaming upang huwag paganahin iyon. Mukhang ito sa memory, at kahit ko ang iginuhit 1 at 2 at 3 malapit sa isa't isa, kung talaga namin gayahin ito-maaari mong guys, habang na tumuturo sa parehong mga tao, maaaring ang ilan sa inyo ay kumuha ng isang random na hakbang likod, ang ilan sa isang random na hakbang pasulong? 

Gulo na ito pa rin ang isang naka-link na listahan, ngunit ang mga guys na ito ay maaaring saanman sa memorya, kaya Anita + + ay hindi pagpunta upang gumana kung bakit? Ano sa lokasyon Anita + +? Sino ang nakakaalam. Ito ang ilang iba pang mga halaga na lang kaya ang mangyayari sa interposed sa lahat ng mga node sa pamamagitan ng pagkakataon dahil hindi namin gamit ang isang array. Inilalaan namin ang bawat sa mga node indibidwal. Okay, kung ikaw guys ay maaaring linisin sarili-back up. Hayaan akong magpanukala na sa halip ng Anita + +, gawin namin sa halip Anita ay nakakakuha- maayos, bakit hindi namin pumunta sa anumang Anita ay pagturo sa at pagkatapos ay gawin. susunod? Sa ibang salita, pumunta kami sa Ramon, kung sino ang may hawak ang bilang 22, at pagkatapos. susunod na parang Anita ay kopyahin kanyang kaliwang kamay pointer. Ngunit hindi siya ay pumunta mas malayo kaysa Ramon dahil nakita namin 22. Ngunit iyon ay ang ideya. Ngayon, ito ay isang diyos-kakila-kilabot gulo. Totoo lang, ang walang kailanman tandaan ang syntax na ito, at kaya thankfully, ito ay aktwal na maliit na sinadya oh, hindi mo aktwal na makita kung ano ang ko sinulat ni. Ito ay mas nakakahimok kung magagawa mong. Voila! 

Likod ng mga eksena, ako ay paglutas ang problema sa ganitong paraan. Anita, na hakbang sa kaliwa, una, kami pumunta sa address na Anita ay pagturo sa at kung saan siya ay mahanap hindi lamang n, na-check lang namin para sa kapakanan ng paghahambing, ngunit maaari ka ring makahanap ng susunod na - sa kasong ito, Kaliwang Ramon na tumuturo sa susunod na node sa listahan. Ngunit ito ay ang diyos-kakila-kilabot gulo na tinutukoy ko mas maaga, ngunit ito ay lumiliko out C ay nagbibigay-daan sa amin upang gawing simple ito. Sa halip ng pagsulat (* Anita), maaari naming halip magsulat lamang Anita-> n, at ang eksaktong parehong bagay pagtakbo, ngunit ito ng maraming mas madaling maunawaan, at ng maraming mas pare-pareho na may larawan na namin ang pagguhit lahat ng oras na ito gamit ang mga arrow. 

Panghuli, kung ano ang kailangan namin gawin sa pagtatapos ng programang ito? May isang linya ng code natitirang. Bumalik kung ano? Maling, dahil kung makuha namin sa pamamagitan ng buo habang loop at Anita ay, sa katunayan, null, na nangangahulugan na siya nagpunta ang lahat ng mga paraan sa dulo ng listahan kung saan siya ay pagturo sa-kung ano ang iyong pangalan muli? Kaliwang Ari. >> Ari, na null. Anita ay ngayon null, at Napag-alaman kong ka nakatayo dito awkwardly sa limbo dahil ako pagpunta off sa isang monologo dito, ngunit gagamitin namin sangkot muli sa sandali lamang. Anita ay null sa puntong iyon sa kuwento, kaya terminate ang habang loop, at mayroon kaming upang bumalik false dahil kung nakuha niya ang lahat ng mga paraan upang null pointer ng Ari pagkatapos ay nagkaroon ng walang bilang na hinahangad niya sa listahan. Maaari naming linisin ito up masyadong, ngunit ito ay isang medyo magandang pagpapatupad pagkatapos ng isang function ng traversal, mahanap ang function para sa isang naka-link na listahan. Pa rin linear sa paghahanap, ngunit ito ay hindi kasing simple ng + + isang pointer o + + isang i variable dahil ngayon hindi namin maaaring hulaan kung saan ang bawat isa sa mga node sa memory. Mayroon kaming sa literal na sundin ang trail ng mga breadcrumbs o, higit na partikular, payo, upang makakuha ng mula sa isang node sa ibang. 

Ngayon sabihin subukan ang isa pa. Anita, ang gusto mong bumalik dito? Bakit hindi namin magpatuloy at magtalaga ng isa pang tao mula sa madla? Malloc-kung ano ang iyong pangalan? >> Rebecca. Rebecca. Rebecca ay malloced mula sa madla, at ngayon siya ay itinatago ang bilang 55. At ang layunin sa kamay ngayon ay para sa Anita upang ipasok Rebecca sa naka-link na listahan dito sa naaangkop na lugar nito. Halika sa paglipas ng dito para sa isang sandali. Tapos ko na ang isang bagay tulad nito. Tapos ko na node *. At kung ano ang iyong pangalan muli? Rebecca. >> Rebecca, okay. Rebecca nakakakuha ng malloc (sizeof (node)). Tulad lamang na inilalaan namin ang mga bagay tulad ng mga mag-aaral at watnat sa nakaraan, kailangan namin ang laki ng node, kaya ngayon Rebecca ay pagturo sa kung ano? Rebecca ay may dalawang mga patlang sa loob ng kanyang, isa sa kung saan ay 55. Natin gawin kung ano, Rebecca-> = 55. Ngunit Rebecca-> susunod dapat bang ngayon, ang kanyang mga kamay uri na nakakaalam? Ito ay pagturo sa ilang halaga ng basura, kaya bakit hindi para sa mabuting panukala namin ng hindi bababa sa gawin ito upang ang kaliwang kamay ay ngayon sa kanyang bahagi. Ngayon Anita, dalhin ito mula dito. Mayroon kang Rebecca pagkakaroon ng pag-inilalaan. Sige at hanapin kung saan dapat naming ilagay Rebecca. Mabuti, napakabuti. Okay, mahusay, at ngayon ay kailangan naming sa iyo upang magbigay ng isang bit ng direksyon, kaya naabot mo na Ari. Ang kanyang kaliwang null, ngunit Rebecca ay malinaw nabibilang sa kanan, kaya kung paano namin upang baguhin ito naka-link na listahan upang ipasok ng Rebecca sa naaangkop na lugar? Kung maaari mong literal ilipat ang kaliwang kamay ng tao sa paligid tulad ng kinakailangan, makikita naming ayusin ang problema na paraan. Okay, mabuti, at samantala, kaliwang Rebecca ngayon sa pamamagitan ng kanyang bahagi. 

Na ay masyadong madaling. Subukan nating paglaan-lubos Halos tapos, 20. Okay, darating sa up. 20 ay inilalaan, kaya ipaalam sa akin sige at sabihin muli dito lang kami tapos node * Saad. Mayroon kaming malloc (sizeof (node)). Naming gawin ang parehong eksaktong syntax bilang ginawa namin bago para sa 20, at kukunin ko na gawin ang susunod = null, at ngayon ito sa Anita upang ipasok sa naka-link na listahan, kung maaari mong i-play na eksaktong parehong papel. Ipatupad. Okay, mabuti. Ngayon sa tingin maingat bago simulan mo ang paglipat ng kaliwa mga kamay sa paligid. Iyo sa pamamagitan ng malayo nakuha ang pinaka-mahirap na papel ngayon. Kaninong mga kamay ay dapat ilipat muna? Okay, maghintay, ako marinig ilang hindi. Kung ang ilang mga tao ay magalang bang upang makatulong na malutas ang isang mahirap na sitwasyon dito. Kaninong kaliwang dapat ma-update sa unang marahil? Oo. [Mag-aaral] Saad. Okay, Saad, bakit, bagaman? [Hindi marinig na mag-aaral ng tugon] Mabuti, dahil kung ililipat kung ano ang namin ang iyong pangalan? >> Marshall. Marshall, kung namin ilipat ang kanyang kamay sa unang pababa null, ngayon literal namin na naulila apat na tao sa listahang ito dahil siya ay ang tanging bagay na tumuturo sa Ramon at lahat ng tao sa kaliwa, kaya nag-a-update na pointer unang ay hindi maganda. Natin i-undo na. Mabuti, at ngayon sige at ilipat ang mga naaangkop na kaliwang kamay na tumuturo sa Ramon. Ito pakiramdam ng isang maliit na paulit-ulit. Ngayon ay mayroong dalawang tao na tumuturo sa Ramon, ngunit na fine dahil ngayon kung paano iba pa naming i-update ang listahan? Ano kabilang banda ay may upang ilipat? Mahusay na, ngayon nawala namin ang anumang memory? Hindi, kaya mahusay na, sabihin makita kung hindi namin maaaring masira ito nang isa pang beses. 

Mallocing ng isang huling oras, bilang 5. Ang lahat ng mga paraan sa likod, dumating pababa. Napaka kapana-panabik. [Palakpakan] Ano ang iyong pangalan? >> Ron. Ron, okay, ikaw ay malloced bilang numero 5. Lamang namin na maisakatuparan ang code na halos kapareho ng mga sa pamamagitan lamang ng ibang pangalan. Mahusay na. Ngayon, Anita, good luck pagpasok ng numero 5 sa listahan ngayon. Magandang, at? Mahusay, kaya talaga ito ang ikatlong ng tatlong kabuuang kaso. Namin unang nagkaroon ng isang tao sa dulo, Rebecca. Kami ay may isang tao sa gitna. Ngayon ay mayroon kaming isang tao sa simula, at sa halimbawang ito, na namin ngayon ay upang i-update ang Lucas sa unang pagkakataon dahil ang unang elemento sa listahan ay mayroon na ngayong upang tumuro sa isang bagong node, na, sa pagliko, ay pagturo sa node bilang 9. 

Ito ay isang hugely mahirap demonstration, ako ba, kaya isang malaking ikot ng papuri para sa mga guys kung magagawa mong. Maayos na Natapos. Iyon lang. Maaari mong panatilihin ang iyong mga piraso ng papel bilang isang maliit na memory. Ito lumiliko out ang paggawa nito sa code ay hindi lubos bilang simpleng bilang lamang ang paglipat ng mga kamay sa paligid at pagturo ng mga payo sa iba't ibang mga bagay. Ngunit Napagtanto na pagdating panahon upang ipatupad ang isang bagay tulad ng isang naka-link na listahan o isang variant nito kung kang tumuon sa talagang mga pangunahing batayan, ang kagat-laki ng mga problema na mayroon ako upang malaman kung, ito ang kamay na ito o ito kamay, Napagtanto na kung ano ay kung hindi man ay isang medyo kumplikadong programa maaari, sa katunayan, na bumaba sa medyo simpleng mga bloke ng gusali tulad nito. 

Natin ang mga bagay sa isang mas sopistikadong direksyon pa rin. Namin ngayon ang paniwala ng mga naka-link na listahan. Mayroon din kaming-salamat sa mungkahi pabalik doon-doble na naka-link sa listahan, na kamukha halos pareho, ngunit ngayon ay mayroon kaming dalawang mga payo sa loob ng struct sa halip na isa, at kami marahil tumawag sa nakaraan at susunod na ang mga payo o pakaliwa o pakanan, ngunit namin, sa katunayan, kailangan dalawa sa kanila. Code ay ng kaunti pa kasangkot. Anita ay nagkaroon pang trabaho dito sa entablado. Ngunit maaari naming tiyak na ipatupad na uri ng istraktura. Sa mga tuntunin ng tumatakbo oras, bagaman, kung ano ang ang oras para sa Anita ng paghahanap ng numero ng n sa isang naka-link na listahan ngayon? Pa ring malaking O ng n, kaya hindi na mas mahusay kaysa sa linear paghahanap. Hindi namin maaaring gawin binary paghahanap, bagaman, muli. Bakit ay na ang kaso? Hindi ka maaaring tumalon sa paligid. Kahit na malinaw naman namin makita ang lahat ng mga tao sa entablado, at Anita maaaring eyeballed ito at sinabi, "Ito ay sa gitna ng listahan," hindi niya alam na kung siya ay computer program dahil ang tanging bagay na siya ay may sa aldaba sa sa simula ng sitwasyon ay Lucas, na ang unang pointer. Gusto niya kinakailangang sundin ang mga link na iyon, pagbibilang ang kanyang paraan hanggang siya nahanap na halos gitna, at kahit pagkatapos, hindi niya na malaman kung kailan niya naabot gitna maliban kung siya ay napupunta ang lahat ng mga paraan sa dulo upang malaman kung gaano karaming mga may, backtracks, at masyadong mahirap maliban kung mayroon kang doble-link sa listahan ng mga uri. 

Paglutas ng ilang mga problema ngayon, ngunit nagpapakilala iba. Paano ang tungkol sa isang iba't ibang mga istraktura ng data sa kabuuan? Ito ay isang litrato ng mga trays sa Mather House, at sa kasong ito, mayroon kaming isang istraktura ng data na rin namin ang uri ng na-pakikipag-usap tungkol sa. Usapan natin ang tungkol sa isang stack sa konteksto ng memorya, at na uri ng sadyang na pinangalanang dahil isang stack sa mga tuntunin ng memory ay epektibong istraktura ng data na may higit pa at higit pa na mga bagay-bagay layered sa tuktok nito. Ngunit kawili-wiling bagay tungkol sa isang stack, tulad ng kaso sa katotohanan, ay na ito ay isang espesyal na uri ng mga istraktura ng data. Ang istraktura ng data kung saan ang unang elemento sa ang huling elemento out. Kung ikaw ay ang unang tray na ilagay papunta sa stack, ka na sa kasamaang-palad ang huling tray ay dadalhin off ang stack ang, at na hindi kinakailangan ng isang magandang bagay. Sa kabaligtaran, maaari mong isipin ang tungkol dito sa iba pang mga paraan sa paligid, sa huling sa unang out. 

Ngayon, ang anumang mga sitwasyon ay dumating sa isipan kung saan nagkakaroon ng stack istraktura ng data kung saan mayroon kang na ari-arian ng huling sa, unang out, ay talagang Nakakamangha? Ay na ang isang magandang bagay? Ay na ang isang masamang bagay? Ito ay talagang isang masamang bagay kung ang mga trays ay hindi lahat ng magkakahawig at sila ay ang lahat ng mga espesyal na iba't ibang kulay o watnat, at ang kulay na gusto mo ang lahat ng mga paraan sa ibaba. Siyempre, hindi ka maaaring makakuha ng na walang mahusay na pagsisikap. Mayroon kang upang simulan mula sa tuktok at gumagana ang iyong paraan pababa. Katulad nito, kung ano ang kung ikaw ay isa sa mga lalaki fan na naghihintay lahat ng gabi na sinusubukan upang makakuha ng isang iPhone at linya up sa isang lugar na tulad nito? Hindi magiging gandang kung ang Apple store ay isang stack ng data ng istraktura? Yay? Hindi sang-ayong boto? Ito ay mahusay lamang para sa mga tao na magpapakita sa huling posibleng minuto at pagkatapos makapag-plucked off queue. At sa katunayan, ang katotohanan na kaya ako ay hilig upang sabihin ng queue aktwal na pare-pareho sa kung ano ang gusto namin tumawag sa ganitong uri ng data ng istraktura, isa sa katotohanan kung saan ang order bagay, at nais mong ang unang isa sa unang out kung lamang para sa kapakanan ng tao pagkamakatarungan. Karaniwan naming tumawag na isang istraktura ng data ng queue. 

Ito lumiliko bukod sa naka-link na listahan, maaari naming simulan ang paggamit ng mga parehong pangunahing ideya at simulan ang paglikha ng mga bagong at iba't-ibang uri ng mga solusyon sa mga problema. Halimbawa, sa kaso ng isang stack, maaari naming kumakatawan sa isang stack gamit ang isang data na istraktura tulad nito, nais kong ipanukala. Sa kasong ito, ipinahayag ko ang struct ng, at ko na sinabi sa loob ng istrakturang ito ay isang hanay ng mga numero at pagkatapos ay isang variable na tinatawag na laki, at ako na tumawag sa bagay na ito ng stack. Ngayon, kung bakit ito aktwal na gumagana? Sa kaso ng isang stack, maaari ko gumuhit ito epektibo sa screen bilang isang array. Narito ang aking stack. Iyon ang aking numero. At kami na gumuhit ng mga ito bilang na ito, ito, ito, ito, ito. At pagkatapos Mayroon akong ilang iba pang mga miyembro ng data dito, na kung saan ay tinatawag na laki, kaya ito ay sukat, at ito ay numero, at sama-sama, ang buong iPad dito ay kumakatawan sa isang stack istraktura. Ngayon, sa pamamagitan ng default, laki na siguro nakuha na nasimulan sa 0, at kung ano ang sa loob ng hanay ng mga numero simula kapag ko munang magtalaga ng isang array? Basura. Sino ang nakakaalam? At hindi ito aktwal na mahalaga. Hindi mahalaga kung ito ay 1, 2, 3, 4, 5, ganap na random sa pamamagitan ng malas na naka-imbak sa aking istraktura dahil hangga't alam ko na ang laki ng stack ay 0, pagkatapos ay alam ko programa, hindi tumingin sa anumang ng mga elemento sa array. Hindi mahalaga kung ano ang doon. Huwag tumingin sa kanila, na magiging implikasyon ng isang sukat na 0. 

Ngunit ngayon ipagpalagay ko sige at ipasok ang isang bagay sa stack. Gusto kong ipasok ang numero 5, kaya ko bang ilagay ang numero 5 dito, at pagkatapos ano ang gagawin ko bang ilagay down na dito? Ngayon Gusto ko aktwal na ilagay ang 1 para sa laki, at ngayon stack ng laki 1. Paano kung pumunta ako magpatuloy at ipasok ang numero, sabihin nating, 7 susunod? Pagkatapos ay makakakuha ng update sa 2, at gagawin namin 9, at pagkatapos na ito ay makakakuha-update sa 3. Ngunit ang mga kawili-wiling tampok na ngayon ng stack na ito ay na Ako dapat upang alisin kung aling mga elemento kung gusto kong mag-pop isang bagay off ng stack, upang magsalita? 9 ay ang unang bagay na upang pumunta. Paano dapat ang larawan baguhin kung gusto kong mag-pop ang isang elemento off ang stack, magkano ng isang tray sa Mather? Oo >> [Mag-aaral] Itakda ang laki sa 2. Eksakto, ang lahat ng gagawin ko ay nakatakda laki sa 2, at ano ang gagawin ko gamit ang array? Hindi ko dapat gawin. Maaari kong, lamang na anal, maglagay ng 0 doon o ng -1 o isang bagay upang magpahiwatig na ito ay hindi isang legit halaga, ngunit hindi mahalaga dahil Ko record sa labas ng ang array mismo kung gaano ito kahaba kaya na alam ko lamang tumingin sa ang unang dalawang mga elemento sa array na ito. Ngayon, kung pumunta ako at idagdag ang numero 8 sa array na ito, kung paano ang mga larawan baguhin susunod? Ito ay magiging 8, at ito ay nagiging 3. Ako paggupit ng ilang sulok dito. Ngayon ay mayroon kaming 5, 7, 8, at hindi namin pabalik sa isang sukat ng 3. Ito ay medyo simple ipatupad, ngunit kapag kami ikinalulungkot ang design desisyon? Kailan bagay simulan upang pumunta napaka, napaka-mali? Oo. [Hindi marinig na mag-aaral ng tugon] Kapag nais mong upang bumalik at makakuha ng unang elemento na inilagay mo. 

Ito lumiliko out dito kahit isang stack ay isang array sa ilalim ng hood, din ang mga istraktura ng data na sinimulan namin ang pakikipag-usap tungkol sa karaniwang kilala bilang abstract istraktura ng data kung saan kung paano sila ay ipinatupad ganap na bukod sa punto. Isang data ng istraktura tulad ng isang stack ay dapat upang magdagdag ng suporta pagpapatakbo tulad ng push, na pushes isang tray papunta sa stack, at mga pop, na-aalis ng isang elemento mula sa stack, at na ito. Kung ikaw ay upang i-download ng ibang tao code na na ipinatupad bagay na ito ay tinatawag na stack, ang taong iyon ay nakasulat dalawang function lamang para sa iyo, itulak at pop, na ang tanging layunin sa buhay ay gawin eksakto na. Mong o kanya na ipinatupad program na maaaring naging ganap ang isa upang magpasya kung paano ipatupad ang mga semantika ng pagtulak at popping sa ilalim ng hood o ang pag-andar ng pagtulak at popping. At ginawa ko ang isang medyo hindi makakita sa malayo desisyon dito sa pamamagitan ng pagpapatupad ng aking stack na may ito simpleng istraktura ng data bakit? Kapag ang break na istraktura ang data na ito? Sa anong punto ko upang bumalik ang isang error kapag ang user na ang tawag push, halimbawa? [Mag-aaral] Kung walang mas maraming espasyo. Eksakto, kung mayroong hindi mas maraming espasyo, kung Nalampasan ko ang kapasidad, na ang lahat ng mga caps dahil ito ay nagmumungkahi na ang ilang uri ng pandaigdigang pare-pareho. Well, pagkatapos lamang ako pagpunta sa may upang sabihin, "Paumanhin, hindi ko maaaring itulak ng isa pang halaga papunta sa stack, "mas gusto sa Mather. 

Sa ilang mga punto, sila ay pagpunta sa pindutin ang tuktok na bahagi ng na maliit na cabinet. Walang karagdagang espasyo o kapasidad sa stack, sa puntong ang ilang uri ng error. Ang mga ito ay ilagay ang elemento sa ibang lugar, sa tray sa ibang lugar, o wala saanman sa lahat. Ngayon, na may queue, maaari naming ipatupad ito ng isang maliit na naiiba. Queue ay isang maliit na iba't ibang na sa ilalim ng hood, maaari itong ipinatupad bilang isang array, ngunit bakit, sa kasong ito, ako pagpapanukala ring magkaroon ng ulo elemento na kumakatawan sa pinuno ng listahan, sa harap ng listahan, ang unang tao sa linya sa tindahan ng Apple, sa karagdagan sa laki? Bakit ko kailangan ng isang karagdagang piraso ng data dito? Isipin pabalik sa kung ano ang numero ay kung ako na iginuhit tulad ng sumusunod. Ipagpalagay na ang na ito ay ngayon isang queue sa halip ng isang stack, ang pagkakaiba sa pagiging-tulad ng Apple store-queue ay patas. Ang unang tao sa linya sa simula ng listahan, numero 5 sa kasong ito, siya na ipaalam muna sa tindahan. Natin gawin iyon. Ipagpalagay na ang na ito ay ang estado ng aking queue sa sandaling ito sa oras, at ngayon ang Apple store bubukas at ang unang tao, bilang 5, ay humantong sa tindahan. Paano ko babaguhin ang larawan ngayon ko de-nakapila ang unang tao sa harap ng linya? Ano iyan? >> [Mag-aaral] Baguhin ang queue. Baguhin ang ulo, kaya 5 mawala. Sa katotohanan, bilang bagaman-kung paano pinakamahusay na gawin ito? Sa katotohanan, na parang ang tao na ito mawala. Ano ang numero 7 sa isang aktwal na tindahan? Sila ay gumawa ng isang malaking hakbang pasulong. 

Ngunit ano na namin dumating sa Pinahahalagahan pagdating sa array at paglipat ng mga bagay sa paligid? Na uri ng basura ng iyong oras, i-right? Bakit kaya anal sa unang tao sa simula ng linya sa pisikal ang simula ng tipak ng memory? Na ganap na hindi kailangang. Bakit? Ano ang maaari kong lamang tandaan sa halip? >> [Hindi marinig na mag-aaral tugon] Eksakto, maaari ko lang tandaan na ito ng karagdagang data ng miyembro ng ulo na ngayon ang pinuno ng listahan ay hindi na 0, kung saan ito ay ng ilang sandali ang nakalipas. Ngayon ito ay talagang numero 1. Sa ganitong paraan, makakakuha ako ng bahagyang pag-optimize. Dahil lang ko ang de-nakapila isang tao mula sa linya sa simula ng linya sa Apple store ay hindi nangangahulugan na ang lahat sa shift, kung saan manariwa sa diwa ay isang linear na pagpapatakbo. Ko sa halip gastusin ng pare-pareho ang oras lamang at makamit ang isang mas mabilis na tugon. Ngunit ang presyo ako nagbabayad ay kung ano upang makakuha na karagdagang pagganap at hindi pagkakaroon upang ilipat ang lahat? Oo. >> [Hindi marinig na mag-aaral tugon] Maaaring magdagdag ng higit pang mga tao, na rin, ang problema na orthogonal sa katotohanan na hindi namin ang paglilipat ng mga tao sa paligid. Pa ito sa isang array, gayon man o hindi namin shift ang lahat o hindi- oh, tingnan ko kung ano ang ibig mong sabihin, okay. Aktwal, Sumasang-ayon ako sa kung ano ang iyong sinasabi na ito nang parang ngayon kami ay hindi kailanman gamitin ang simula ng array na ito dahil kung alisin ko 5, pagkatapos kong alisin ang 7. Ngunit ko lamang inilagay ang mga tao sa kanan. 

Nararamdaman tulad ako pag-aaksaya ng espasyo, at kalaunan aking queue disintegrates sa wala sa lahat, kaya kami lang tao wraparound, at sa tingin namin ng ito array talaga dahil ang ilang mga uri ng pabilog na istraktura, ngunit ginagamit namin kung ano ang operator sa C upang gawin na uri ng wraparound? [Hindi marinig na mag-aaral tugon] >> Ang modulo operator. Ito ay isang maliit na nakakainis na sa tingin sa pamamagitan ng kung paano ang gagawin mo sa wraparound, ngunit maaari naming gawin ito, at maaaring namin simulan ang paglalagay ng mga tao sa kung ano ang ginamit sa harap ng linya, ngunit hindi namin lamang tandaan na ito ulo variable na talaga ang aktwal na pinuno ng linya. Paano kung, sa halip, ang aming layunin sa huli, bagaman, ay maghanap ng mga numero, tulad ng ginawa namin dito sa entablado na may Anita, ngunit hindi namin talagang gusto ang pinakamahusay na ng lahat ng mga mundo? Gusto namin ng karagdagang pagiging sopistikado kaysa array ay nagbibigay-daan sa dahil gusto naming ang kakayahan upang dynamic na palaguin ang data na istraktura. Ngunit hindi namin nais sa resort sa isang bagay na tulis namin ang sa unang panayam ay hindi isang pinakamainam na algorithm, na ng linear paghahanap. Ito lumiliko out na maaari mong, sa katunayan, makamit o hindi bababa sa malapit sa pare-pareho ang oras, kung saan ang isang tao tulad ng Anita, kung siya Kino-configure ang kanyang data istraktura hindi sa isang naka-link na listahan, hindi isang stack, hindi queue, maaari, sa katunayan, makabuo ng mga istraktura ng data na nagbibigay-daan sa kanya upang maghanap ng mga bagay, kahit salita, hindi lamang mga numero, sa kung ano ang namin tumawag ng pare-pareho ang oras. 

At sa katunayan, naghahanap magpatuloy, isa sa ang mga psets sa ganitong uri ay halos palaging isang pagpapatupad ng isang spellchecker, kung saan bigyan ka namin muli ng ilang 150,000 na mga salitang Ingles at ang layunin ay upang load ang mga sa memory at mabilis na upang sagutin ang mga katanungan ng form ay naisulat ng tama ang salitang ito? At ito talaga sipsipin kung mayroon kang umulit sa pamamagitan ng lahat ng 150,000 salita upang sagutin na. Ngunit, sa katunayan, gagamitin namin makita na maaari naming gawin ito sa napaka, napaka-mabilis na oras. At ito upang makasali ang pagpapatupad ng isang bagay na tinatawag na ng hash table, at kahit sa unang tingin ito bagay na tinatawag ng hash table ay pagpunta sa ipaalam sa amin makamit ang mga sobrang mabilis na oras ng pagtugon, ito lumiliko out na may ay sa katunayan ang problema. Pagdating panahon upang ipatupad ang bagay na tinatawag na-muli, ako ginagawa itong muli. Ako isa lamang dito. Pagdating oras sa pagpapatupad na ito bagay na tinatawag ng hash table, kami ay pagpunta sa may upang gumawa ng desisyon. Gaano kalaki ang dapat bagay na ito aktwal na? At kapag sinimulan namin ang pagpasok ng mga numero sa ito hash table, paano namin upang mag-imbak ang mga ito sa isang paraan namin ang mga ito pabalik ang nang mabilis hangga't nakuha namin sa kanila sa? Ngunit gagamitin namin ang bago mahaba na ang tanong na ito ng kapag ang kaarawan ng lahat sa klase ay medyo dyermeyn. Ito lumiliko out na sa kuwartong ito, Mayroon kami ng ilang daang mga tao, kaya ang mga logro na ang dalawang sa atin ang parehong kaarawan marahil ay medyo mataas. Paano kung may 40 lamang ng sa amin sa kuwartong ito? Ano ang mga logro ng dalawang tao na nagkakaroon ng parehong kaarawan? [Mag-aaral] Higit sa 50%. Oo, higit sa 50%. Sa katunayan, dinala ko kahit isang chart. Ito lumiliko out at talaga ito ng sneak preview- kung may 58 lamang ng sa amin sa kuwartong ito, ang posibilidad ng 2 sa atin pagkakaroon ng parehong kaarawan hugely mataas, halos 100%, at na pagpunta sa maging sanhi ng ang maramihang mga nasaktan para sa amin sa Miyerkules. 

Gamit na sinabi, sabihin ipinid dito. Susubukan naming makita sa Miyerkules. [Palakpakan] [CS50.TV]