[Jwe mizik] DAVID J. Malan: Tout dwa. Sa a se CS50. Sa a se semèn senk kontinye, epi nou gen kèk bon nouvèl ak kèk move nouvèl. Se konsa, bon nouvèl se ke CS50 lanse sa a Vandredi. Si ou ta renmen rantre nan nou, tèt nan URL la abityèl isit la. Menm pi bon nouvèl, pa gen konferans sa a ap vini Lendi 13 an. Yon ti kras mwens pi bon nouvèl, egzamen zewo se Mèkredi pwochen. Plis detay ka jwenn nan sa a URL isit la. Ak sou jou ki koup pwochen nou pral ranpli nan espas vid yo ak concerne nan chanm yo ke nou ap gen rezève. Pi bon nouvèl se ke gen pral gen yon revizyon kou-lajè sesyon sa a ap vini Lendi nan aswè an. Rete branche nan la kou sit entènèt ki kote ak detay. Seksyon, menm si li se yon jou ferye, pral tou satisfè tou. Pi bon nouvèl, konferans Vandredi kap vini an. Se konsa, sa a se yon tradisyon nou genyen, tankou pou chak progranm la. Just-- li pral yo dwe dwòl. Ou gen pou wè bagay sa yo tankou tan konstan estrikti done ak tablo yo regle ak pye bwa ak ap eseye. Epitou, n ap pale sou pwoblèm anivèsè nesans. Yon pakèt antye nan bagay ap tann Vandredi kap vini an. OK. Kanmèm. Se konsa, sonje ke nou ve yo te ki konsantre sou foto sa a nan sa ki nan andedan nan memwa òdinatè nou an. Se konsa, memwa oswa RAM se kote pwogram egziste pandan w ap kouri yo. Si ou doub-klike sou yon icon a kouri kèk pwogram oswa doub-klike sou yon icon yo louvri kèk dosye, li nan chaje soti nan difisil ou kondwi oswa kondwi eta solid nan RAM, Random Aksè memwa, kote li ap viv jouk pouvwa a ale nan, kouvèti a laptop fèmen, oswa ou kite pwogram nan. Kounye a ke memwa, nan ki pwobableman ou gen 1 jigokte jou sa yo, 2 jigokte, oswa menm plis ankò, se jeneralman mete deyò pou yon pwogram bay nan sa a sòt de rektangilè konseptyèl ekspresyon modèl kijan nou gen chemine a nan pati anba a ak yon pakèt moun sou lòt bagay nan tèt la. Bagay la nan tèt la anpil nou te wè sou foto sa a anvan men li pat janm te pale osijè de se sa yo rele segman nan tèks. Segman Tèks se jis yon fason anpenpan pou li di zewo yo ak moun yo ki konpoze pwogram aktyèl ou konpile. Se konsa, lè ou doub-klike sou Microsoft Word sou Mac ou a oswa PC, oswa lè ou kouri dot koupe Mario sou yon Òdinatè Linux nan fenèt tèminal ou, zewo yo ak moun yo ki konpoze Yo mo oubyen yon Mario ki estoke pou yon ti tan nan RAM òdinatè ou a nan sa yo rele an segman tèks pou yon pwogram an patikilye. Anba a ki ale initialisé ak done uninitialized. Sa a se bagay tankou varyab mondyal, ke nou pa te itilize anpil nan, men sou okazyon nou te te gen varyab mondyal oswa statics defini strings ki se difisil kode mo tankou "alo" ki pa yo te pran nan soti nan itilizatè a ke yo difisil-kode nan pwogram ou an. Koulye a, desann nan pati anba a nou gen chemine a sa yo rele. Ak chemine a, konsa byen lwen, nou ve yo te lè l sèvi avèk pou sa kalite rezon? Ki sa ki nan chemine a te itilize pou? Yeah? ODYANS: Fonksyon. DAVID J. Malan: Pou fonksyon? Nan ki sans pou fonksyon? ODYANS: Lè ou rele yon fonksyon, nan agiman yo se kopye sou chemine a. DAVID J. Malan: Egzakteman. Lè ou rele yon fonksyon, li agiman yo se kopye sou chemine a. Se konsa, nenpòt X la oswa Y a oswa Yon a oswa B a ke w ap pase nan yon fonksyon yo pou yon ti tan mete yo sou chemine a sa yo rele, jis tankou youn nan Annenberg la manje plato sal, epi tou bagay tankou varyab lokal. Si fonksyon foo ou oswa swap ou fonksyon gen varyab lokal yo, tankou tanporèr, sa yo de fini sou pil la. Koulye a, nou pa pral pale twòp sou yo, men sa yo varyab anviwònman nan pati anba a nou te wè yon ti tan de sa lè Mwen te futzing nan klavye a yon sèl jou epi mwen te kòmanse gen aksè nan bagay sa yo tankou argv 100 oswa argv 1,000, jis elements-- mwen bliye numéros a, men ki pa te sipoze jwenn aksè pa m '. Nou te kòmanse wè kèk senbòl fenki sou ekran an. Moun sa yo ki te sa yo rele varyab anviwònman tankou anviwònman mondyal la pou m ' pwogram oswa pou òdinatè mwen an, pa gen rapò ak ki sot pase a ensèk ki nou diskite, Shellshock, ki te gen plaguing byen kèk òdinatè. Koulye a, anfen, nan konsantre a jodi a nou pral finalman dwe sou pil wòch la. Sa se yon lòt moso nan memwa. E fondamantalman tout bagay sa a memwa se bagay la menm. Li nan menm pyès ki nan konpitè. Nou jis sòt de trete grap diferan nan bytes pou rezon diferan. Pil wòch la se tou ale nan dwe kote varyab ak memwa ke ou mande soti nan sistèm nan fonksyone la tanporèman estoke. Men, gen nan kalite yon pwoblèm isit la, kòm foto a implique. Nou sòt de gen de bato sou yo kolizyon. Paske jan ou sèvi ak pi plis ak plis nan chemine a, ak jan nou wè jodi a pati, jan ou sèvi ak pi plis ak plis nan a pil wòch, siman move bagay ka rive. Ak tout bon, nou ka antrene ki entansyonèlman oubyen san. Se konsa, cliffhanger an dènye tan te pwogram sa a, ki pa t 'sèvi nenpòt fonksyonèl objektif lòt pase yo demontre ki jan ou kòm yon nèg move ka aktyèlman pran avantaj de pinèz nan pwogram yon moun nan ak pran sou yon pwogram oswa menm yon sistèm òdinatè antye oswa sèvè. Se konsa, jis gade yon ti tan, ou remake ke prensipal nan pati anba a pran nan liy lòd agiman, tankou pou chak argv. Epi li gen yon apèl nan yon f fonksyon, esansyèlman yon fonksyon nameless rele f, ak li a pase nan argv [1]. Se konsa, tou sa pawòl itilizatè a kalite nan nan èd memwa a apre non pwogram sa a la, ak Lè sa a fonksyon sa a abitrè moute tèt, f, pran nan yon fisèl, AKA * Char, kòm nou te fèk kòmanse fè diskite, epi li jis rele l "ba." Men, nou ta ka rele li anyen. Lè sa a, li deklare, andedan nan f, yon etalaj de karaktè rele c-- 12 karaktè sa yo. Koulye a, pa istwa a mwen te vle di yon ti moman de sa, ki kote nan memwa se c, oswa moun sa yo ki 12 char ale nan fini? Jis yo dwe klè. Yeah? ODYANS: sou pil la. DAVID J. Malan: sou pil la. Se konsa, c se yon varyab lokal yo. Nou ap mande pou 12 charaktèr oswa 12 bytes. Moun sa yo ki yo ale nan fini sou chemine a sa yo rele. Koulye a, finalman se fonksyon sa a lòt sa a, se aktyèlman trè itil, men nou pa te reyèlman itilize li tèt nou, strncopy. Sa vle di kopi fisèl, men sèlman n lèt, n karaktè. Se konsa, karaktè n pral kopye soti nan bar nan c. Ak konbyen? Longè a nan ba. Se konsa, nan lòt mo, ki yon sèl liy, strncopy, ki pral a kapab bay kopi efektivman defann nan c. Koulye a, jis kalite antisipe moral nan istwa sa a, ki sa ki potansyèlman Pwoblematik isit la? Menm si nou ap tcheke longè a nan ba yo, e pase l 'nan strncopy, ki sa ki zantray ou di ou se toujou kase sou pwogram sa a? Yeah? ODYANS: pa gen ladan plas pou pèsonaj la nil. DAVID J. Malan: pa gen ladan plas pou pèsonaj la nil. Ki kapab, kontrèman ak nan pratik sot pase yo nou fè pa menm gen anpil kòm yon plis 1 akomode ke karaktè nil. Men, li la menm vin pi mal pase sa. Ki lòt bagay yo nou li pap resevwa yo fè? Yeah? ODYANS: [fèbl] DAVID J. Malan: pafè. Nou te difisil kode 12 trè abitrèman. Sa se pa konsa pou sa anpil nan pwoblèm, men reyalite a ke nou ap pa menm tcheke si longè a nan bar se mwens pase 12, nan ka sa a li pral yo dwe san danje yo mete l 'nan memwa a rele c ke nou te resevwa lajan. Vreman vre, si bar se tankou 20 karaktè long, fonksyon sa a parèt yo dwe kopye 20 karaktè soti nan ba nan c, kidonk pran omwen 8 bytes ke li pa ta dwe. Sa a enplikasyon la isit la. Se konsa, nan pwogram ti bout tan, kase. Pa tankou yon kontra gwo. Petèt ou jwenn yon fay segmentation. Nou tout te gen pinèz nan pwogram yo. Nou tout ta ka gen pinèz nan pwogram kounye a. Men, sa ki nan enplikasyon la? Oke, isit la nan yon vèsyon agrandi-an nan foto ki nan memwa òdinatè mwen an. Sa a se anba a nan chemine mwen. Ak tout bon, nan pati anba nan anpil se sa ki nan rele paran chemine woutin, fason anpenpan pou li di sa a, se prensipal la. Se konsa, ki moun ki va rele fonksyon an f ke nou ap pale de. Se konsa, sa a se pati anba a nan chemine a. Adrès retou a se yon nouvo bagay. Li te toujou la, toujou nan foto sa. Nou jis pa janm rele atansyon a li. Paske li vire soti wout la c ap travay se ke lè yon fonksyon rele yon lòt, pa sèlman fè agiman yo ak sa yo ki fonksyon jwenn pouse sou chemine a, pa sèlman fè lokal fonksyon an nan varyab jwenn pouse sou chemine a, yon bagay yo rele yon adrès retou tou vin mete sou chemine a. Espesyalman, si apèl prensipal foo, nan prensipal pwòp adrès nan memwa, bèf yon bagay, efektivman vin mete sou chemine a se konsa ke lè f se fè pwomenad li konnen ki kote yo so tounen nan nan tèks la segman nan lòd yo kontinye egzekite. Se konsa, si nou isit la concept, nan prensipal la, Lè sa a, f vin rele. Kouman f konnen ki moun ki nan kontwòl men tounen ankò? Oke, sa a ti kras myèt an wouj isit la, rele adrès la retounen, li jis chèk, sa sa adrès retou? Oh, kite m 'so tounen nan prensipal isit la. Epi sa a, yon ti kras nan yon Senplifikasyon, paske zewo yo ak moun yo pou prensipal yo se teknikman moute isit la nan segman nan teknoloji. Men, sa a lide la. f jis gen konnen ki sa nan kote kontwòl finalman ale tounen. Men, òdinatè yo fason gen lontan yo mete deyò bagay sa yo tankou varyab lokal ak agiman se tankou sa a. Se konsa, nan tèt la nan foto sa a nan ble se ankadreman an pil pou f, se konsa tout nan memwa nan ki f espesyalman lè l sèvi avèk se. Se konsa, kòmsadwa, remake ke bar se nan foto sa a. Bar te agiman li yo. Epi nou te deklare ke agiman fonksyon jwenn pouse sou chemine a. Epi c, nan kou, se tou nan foto sa a. Ak jis pou rezon notation, remake nan kwen ki anwo a sou gòch-men se sa ki ta c bracket 0 ak Lè sa a, yon ti kras desann a dwat a se c bracket 11. Se konsa, nan lòt mo, ou ka imajine ke gen nan yon griy nan bytes gen, premye a ki se gòch anwo, anba nan yo ki se dènye a nan tout sa yo 12 bytes. Men koulye a, eseye fè jèn pou pi devan. Ki sa ki se sou yo rive si nou pase nan yon bar fisèl sa a, se pi long pase c? Epi nou pa ap tcheke si li nan tout bon pi lontan pase 12. Ki pati nan foto sa a ki pral jwenn ranplase pa bytes 0, 1, 2, 3, dot dot dot, 11, ak Lè sa a, move, 12, 13 a 19? Ki sa ki nan pral rive isit la, si ou dégager soti nan kòmann-nan nan ki c bracket 0 se sou tèt la epi c bracket 11 se sòt de desann a dwat a? Yeah? ODYANS: Oke, li la pral recouvrir ba a * Char. DAVID J. Malan: Yeah, li sanble w ap ale nan recouvrir Char bar *. Ak pi mal, si ou voye nan yon reyèlman long fisèl, ou ta ka menm recouvrir ki sa? Retounen adrès la. Ki ankò, se jis tankou yon myèt di pwogram nan kote pou tounen nan lè f se fè ke yo te rele. Se konsa, sa nèg move tipikman fè se si yo vini nan tout yon pwogram yo ke yo ap kirye si se lezot, buggy nan yon fason ke li oswa li ka pran avantaj de ki ensèk, jeneralman yo pa jwenn dwa sa-a premye fwa. Yo jis kòmanse voye, pou egzanp, strings o aza nan pwogram ou an, si wi ou non nan klavye a, oswa franchman yo pwobableman ekri yon pwogram ti kras nan jis otomatikman jenere strings, epi yo kòmanse frape sou pwogram ou an pa voye nan anpil nan entrain diferan nan longè diferan. Le pli vit ke aksidan pwogram ou an, sa a, se yon bagay dwòl. Paske sa vle di li te oswa li te dekouvri ki sa ki pwobableman tout bon yon ensèk. Lè sa a, yo ka jwenn plis entelijan epi yo kòmanse konsantre plis etwatman sou kòman yo esplwate ki ensèk. An patikilye, sa li oswa li ta ka fè se voye, nan ka ki pi bon, hello. Pa gen kontra gwo. Li se yon fisèl sa a, se ase kout. Men, sa ki si li voye, epi nou pral jeneralizasyon li kòm, atak code-- konsa zewo ak moun yo ki fè bagay sa yo tankou rm-rf, ki retire tout bagay soti nan kondwi a difisil oswa voye Spam oswa yon jan kanmenm atake machin nan? Se konsa, si chak nan sa yo lèt A jis reprezante, concept, atak, atak, atak, atak, kèk kòd move ke yon lòt moun te ekri, men si moun sa a se entelijan ase pa sèlman gen ladan tout nan tout sa yo rm-RFs, men tou, gen dènye bytes kèk li oswa li gen yon nimewo ki koresponn nan adrès ki nan l ' oswa pwòp Kòd atak l ' ke li oswa li te pase nan jis lè yo bay li nan èd memwa a, ou ka efektivman je chèch òdinatè a nan remarke lè f se fè egzekite, oh, li lè pou m 'so tounen nan adrès ki retounen wouj. Men, paske se li oswa li te gen yon jan kanmenm anpyete ki adrès retou avèk nimewo pwòp yo, e yo ap entelijan ase yo te configuré ki Nimewo yo, al gade, jan ou wè nan tèt la super kwen gòch-men gen, adrès aktyèl la nan la nan òdinatè memwa nan kèk nan Kòd atak yo, yon nèg move ka je chèch òdinatè a nan egzekite Kòd li oswa li pwòp. Epi sa Kòd, ankò, ka anyen. Li nan jeneralman yo rele koki Kòd, ki se jis yon fason pou di ke li pa jeneralman yon bagay kòm senp tankou rm-RF. Li la aktyèlman yon bagay tankou bach, oswa yon pwogram aktyèl ki ba l ' oswa kontwòl pwogramatik li yo egzekite nenpòt lòt bagay ke yo vle. Se konsa, nan kout, sa a tout proceed soti nan reyalite a senp ke sa a ensèk ki enplike pa tcheke limit yo nan etalaj ou. Epi paske wout la òdinatè travay se yo ke yo sèvi ak chemine a soti nan efektivman, Concept, anba sou moute, men Lè sa a, eleman yo ou pouse sou chemine a grandi tèt anba, sa a se ekstrèmman Pwoblematik. Koulye a, gen fason yo travay alantou sa a. Ak franchman, gen lang ak ki travay alantou sa a. Java se iminitè a, pou egzanp, nan pwoblèm sa a an patikilye. Paske yo pa ba ou endikasyon. Yo pa ba ou adrès memwa dirèk. Se konsa, avèk pouvwa sa a ke nou gen manyen anyen nan memwa nou vle vini, Byensir, gwo risk. Se konsa, kenbe yon grenn je deyò. Si, franchman, nan mwa kap oswa ane k ap vini, nenpòt lè w ap li sou kèk eksplwatasyon nan yon pwogram oswa yon sèvè, si ou te janm wè yon allusion nan yon bagay tankou yon atak debòde tanpon, oswa chemine debòde yon lòt kalite nan atak, menm jan an nan lespri, anpil jan enspire nan a sou sit wèb non, si ou konnen li, li nan tout pale de jis debòde gwosè a nan kèk karaktè etalaj oswa kèk etalaj plis jeneralman. Nenpòt kesyon, Lè sa a, sou sa a? Pa eseye sa a lakay yo. Tout dwa. Se konsa, malok konsa byen lwen te gen nouvo nou an zanmi nan ke nou ka asiyen memwa ke nou pa nesesèman konnen nan avanse ke nou vle pou nou pa gen Kòd difisil nan nou an nimewo pwogram tankou 12. Yon fwa itilizatè a di nou konbyen lajan done li oswa li te vle D ', nou ka malok ke memwa anpil. Se konsa, malok li vire soti, nan limit nou ve yo te lè l sèvi avèk li, klèman dènye fwa, ak Lè sa a, ou nèg yo te lè l sèvi avèk li pou getstring enkonsyaman pou plizyè semèn, tout nan memwa malok a soti nan pil wòch la sa yo rele. Lè sa a se poukisa getstring, pou egzanp, ka asiyen memwa dynamique san yo pa konnen sa w ap pral tape an avanse, men ou tounen yon konsèy nan ki memwa, e ke memwa se toujou ou epi ou kapab kenbe, menm apre getstring retounen. Paske sonje apre tout sa ki nan chemine se toujou ap monte e desann, leve, li desann. Ak le pli vit ke li ale desann, sa vle di nenpòt memwa fonksyon sa a itilize yo ta dwe pa kapab itilize pa nenpòt lòt moun. Li nan valè fatra kounye a. Men, pil wòch la se leve isit la. Ak sa ki nan bèl sou malok se ke lè malok repati memwa moute isit la, li pa nan afekte, pou la pi pati, pa chemine a. Se konsa, nenpòt ki fonksyon kapab jwenn aksè nan memwa ki te malloc'd, menm pa yon fonksyon tankou getstring, menm apre li se retounen. Koulye a, konvès la nan malok se gratis. Ak tout bon, règ la ou bezwen kòmanse adopte se nenpòt, nenpòt, nenpòt ki lè ou itilize malok ou dwe tèt ou itilize gratis, evantyèlman, sou ki konsèy menm. Tout tan sa a nou te ekri buggy, kòd buggy, pou plizyè rezon. Men, yonn nan ki te gen lè l sèvi avèk bibliyotèk la CS50, ki tèt li se fè espre buggy, li fwit memwa. Nenpòt ki lè ou te rele getstring sou semèn ki sot pase yo kèk nou ap mande opere nan sistèm, Linux, pou memwa. Epi ou pa janm gen yon lòt fwa bay l 'tounen. Lè sa a se pa, nan pratike, yon bon bagay. Epi Valgrind, youn nan la zouti prezante nan Pset 4, se tout sou ede ou kounye a jwenn pinèz tankou sa. Men, Erezman pou Pset 4 ou pa bezwen yo sèvi ak bibliyotèk la CS50 oswa getstring. Se konsa, nenpòt pinèz ki gen rapò ak memwa yo finalman pral fè pwòp ou yo. Se konsa, malok se pi plis pase jis bon pou objektif sa a. Nou ka aktyèlman kounye a rezoud pwoblèm fondamantalman diferan, e fondamantalman rezoud pwoblèm plis efektivman tankou pou chak pwomès semèn zewo a. Se konsa, lwen sa a se sèksi la estrikti done nou te gen. Ak pa estrikti done Mwen jis vle di yon fason pou konsèptualize memwa nan yon fason ki ale pi lwen pase jis di, sa a se yon int, sa a se yon Char. Nou ka kòmanse nan bagay sa yo grap yo ansanm. Se konsa, yon etalaj te sanble ak sa a. Ak sa ki te kle nan sou yon etalaj se ke li ba ou do-a-tounen fragman nan memwa, chak nan yo ki a pwal nan kalite la menm, Int, Int, Int, Int, oswa Char, Char, Char, Char. Men, gen nan yon enkonvenyans kèk. Sa a pou egzanp, se yon etalaj de gwosè sis. Sipoze ou ranpli sa a etalaj ak sis nimewo ak lè sa a, pou kèlkeswa rezon, itilizatè ou vle bay ou yon setyèm nimewo. Ki kote ou mete l '? Ki sa ki nan solisyon an si ou gen kreye yon etalaj sou chemine a, pou egzanp, jis ak semèn nan de notasyon ke nou prezante, nan parantèz kare ak yon kantite andedan? Oke, ou te gen sis nimewo nan bwat sa yo. Ki sa ki ta ensten ou ta dwe ye? Ki kote ou ta vle mete li? ODYANS: [fèbl] DAVID J. Malan: Padon? ODYANS: Mete l 'sou fen an. DAVID J. Malan: Mete l 'sou fen an. Se konsa, jis plis pase a dwat la, deyò nan bwat sa a. Ki ta dwe nice, men li vire soti ou pa ka fè sa. Paske si ou pa te mande pou sa a ti moso nan memwa, li te kapab fè pa konyensidans ke sa a se ke yo te itilize pa kèk lòt varyab tout ansanm. Panse tounen yon semenn oswa Se konsa, lè nou mete soti Zamyla ak Davin ak Gabe nan non nan memwa. Yo te literalman tounen nan tounen nan tounen. Se konsa, nou pa kapab nesesèman konfyans ke kèlkeswa sa a sou isit la ki disponib pou mwen pou m sèvi ak. Se konsa, ki lòt bagay ou ta ka fè? Oke, yon fwa ka akonpli ou bezwen yon etalaj de gwosè sèt, ou ta ka jis kreye yon etalaj de gwosè sèt Lè sa a, sèvi ak yon riban pou oswa yon riban pandan y ap, kopi li nan etalaj nan nouvo, ak Lè sa a yon jan kanmenm jis debarase m de sa a etalaj oswa jis sispann lè l sèvi avèk li. Men, sa a pa patikilyèman efikas. Nan ti bout tan, ranje pa kite ou dynamique rdimansyonman. Se konsa, sou men nan yon sèl ou jwenn aksè o aza, ki se dwòl. Paske li pèmèt nou fè bagay sa yo tankou separe ak konkeri, rechèch binè, nan tout ki nou te te pale osijè de sou ekran an isit la. Men, ou penti tèt ou nan yon kwen. Osito ke ou frape nan fen etalaj ou, sa ou dwe fè yon trè chè operasyon oswa ekri yon pakèt antye nan Kòd kounye a fè fas ak pwoblèm sa. Se konsa, sa si olye pou nou te gen yon bagay yo rele yon lis, oswa yon lye lis an patikilye? E si olye pou yo gen rektang bak nan do nan do, nou gen rektang ki kite yon ti kras ti jan nan chanm jwe nan ant yo? E menm si mwen te trase sa a foto oswa adapte foto sa a nan youn nan tèks yo isit la yo dwe tounen nan tounen nan tounen trè lòd, an reyalite, youn nan moun ki rektang ta ka moute isit la nan memwa. Youn nan yo ta ka moute isit la. Youn nan yo ta ka moute isit la, sou isit la, ak pou fè. Men, sa ki si nou te trase, nan ka sa a, flèch ki yon jan kanmenm lyen sa yo rektang ansanm? Vreman vre, nou te wè yon teknik enkarnasyon nan yon flèch. Kisa nou yo itilize nan sot pase jou sa a, anba kapo a, se reprezantan nan yon flèch? Yon konsèy, dwa? Se konsa, sa si, olye pou yo jis estoke nimewo yo, tankou 9, 17, 22, 26, 34, sa ki si nou ki estoke pa sèlman yon kantite men yon konsèy pwochen youn ak nimewo sa yo? Se konsa, ki anpil tankou ou ta fil yon zegwi nan yon pakèt antye nan twal, bagay sa yo yon jan kanmenm mare ansanm, Menm jan an tou kapab nou ak endikasyon, kòm incarne pa flèch isit la, kalite mare ansanm sa yo rektang endividyèl pa efektivman lè l sèvi avèk yon konsèy pwochen youn ak nimewo ki pwen nan kèk nimewo kap vini an, ki pwen nan, nan vire, kèk nimewo vin apre a? Se konsa, nan lòt mo, ki sa si nou aktyèlman te vle aplike yon bagay tankou sa a? Oke malerezman, rektang sa yo, omwen youn nan ak 9, 17, 22, ak pou fè, sa yo, se pa gen okenn ankò bèl kare ak nimewo sèl. Anba, rektang lan anba a 9, pou egzanp, reprezante sa yo ta dwe gen yon konsèy, 32 miyèt moso. Koulye a, mwen se pa ankò okouran de nenpòt kalite done nan C ki ba ou pa sèlman yon int men yon konsèy tout ansanm. Se konsa, sa ki nan solisyon an si nou vle envante pwòp repons nou yo sa a? Yeah? ODYANS: [fèbl] DAVID J. Malan: Ki sa ki nan sa? ODYANS: New estrikti. DAVID J. Malan: Yeah, se konsa poukisa nou pa nou kreye yon estrikti nouvo, oswa nan C, yon konstri? Nou te wè strukt anvan, si yon ti tan, kote nou te fè fas ak yon estrikti elèv tankou sa a, ki te gen yon non ak yon kay. Nan Pset 3 levasyon ou te itilize yon antye pakèt moun sou structs-- GRect ak GOvals ki Stanford kreye yo gwoup enfòmasyon ansanm. Se konsa, sa si nou pran ide sa a menm nan mo kle sa yo "tipedèf" ak "konstri," ak Lè sa a kèk bagay elèv-espesifik, ak evolye sa a nan bagay sa yo: tipedèf konstri node-- ak ne se jis yon syans òdinatè trè jenerik tèm pou yon bagay nan yon estrikti done, yon veso ki nan yon estrikti done. Yon ne mwen reklame ki pral gen yon n Int, totalman dwat, ak Lè sa a yon ti kras plis cryptically, liy sa a dezyèm lan, struct ne * vini an. Men, nan mwens tèm teknik, ki sa ki ke liy dezyèm nan kòd andedan aparèy òtopedik yo Curly? Yeah? ODYANS: [fèbl] DAVID J. Malan: Yon konsèy nan yon lòt ne. Se konsa, Byensir, sentaks yon ti kras skre. Men, si ou li li l 'literalman, pwochen se non an nan yon varyab. Ki sa ki kalite done li yo? Li se yon ti kras sil tan sa a, men li la nan kalite struct ne *. Nenpòt ki lè nou te wè zetwal yon bagay, ki vle di li nan yon konsèy ak sa yo ki kalite done. Se konsa, pwochen se aparamman yon konsèy nan yon ne konstri. Koulye a, ki sa ki yon ne struct? Oke, remake ou wè sa yo mo menm nan tèt dwat. Ak tout bon, nou menm tou nou wè pawòl Bondye a "Ne" desann isit la sou bò gòch la anba. Lè sa a se aktyèlman jis yon konvenyans. Remake nan definisyon elèv nou gen nan pawòl Bondye a "elèv" yon sèl fwa. Epi sa a, paske yon elèv objè pa t 'pwòp tèt ou-referansyèl. Pa gen anyen andedan nan yon elèv ki bezwen yo lonje dwèt sou yon lòt elèv, persay. Ki ta ka sòt de etranj nan mond lan reyèl. Men, avèk yon ne nan yon lye lis, nou fè vle yon ne yo dwe referansyèl nan yon objè menm jan an. Se konsa, remake chanjman nan isit la se pa jis sa ki andedan aparèy òtopedik yo Curly. Men, nou ajoute pawòl Bondye a "ne" nan tèt la kòm byen ke ajoute li nan pati anba a nan plas "elèv yo." Lè sa a se sèlman yon ti detay teknik se konsa ke, ankò, estrikti done ou kapab pwòp tèt ou-referansyèl, se konsa ke yon ne ka lonje dwèt sou yon lòt ne sa yo. Se konsa, sa se sa a finalman pral vle di pou nou? Oke, yon sèl, sa a bagay andedan se sa ki nan ne nou an. Bagay sa a moute isit la, tèt dwat, se jis pou ki, ankò, nou ka al gade nan tèt nou. Lè sa a, bagay la eksteryè, menm si ne se yon tèm nouvo, petèt, li la toujou nan menm jan ak elèv yo ak sa ki te anba kapo a nan spl. Se konsa, si nou kounye a te vle kòmanse mete ann aplikasyon lis sa a lye, ki jan ta ka nou tradui yon bagay tankou sa nan kòd? Oke, kite la jis wè yon egzanp nan yon pwogram ki aktyèlman sèvi ak yon lis lye. Pami kòd distribisyon jodi a se yon pwogram ki rele Lis Zewo. Men, si mwen kouri sa a mwen te kreye yon super senp entèfas, Grafik koòdone itilizatè, men li la vrèman jis printf. Epi, koulye a mwen te bay tèt mwen yon meni kèk options-- efase, Antre, Search, ak Traverse. Ak kite fimen. Sa yo se operasyon jis komen sou yon estrikti done ke yo rekonèt kòm yon lis lyen. Koulye a, efase ki pral efase yon nimewo nan lis la. Antre nan ale nan ajoute yon nimewo nan lis la. Search ki pral gade pou yon nimewo pou nan lis la. Ak Traverse se jis yon fason anpenpan pou li di, mache nan lis la, enprime li, men sa a li. pa chanje li nan okenn fason. Se konsa, kite a eseye sa a. Ann al pi devan epi tape 2. Lè sa a, mwen pral insert nimewo a, di 9. Antre nan. Epi, koulye a pwogram mwen an se jis pwograme yo di, lis se kounye a 9. Koulye a, si m 'ale pi devan epi Antre ankò, se pou m 'ale pi devan epi rale soti ak kalite nan 17. Koulye a, lis mwen an se 9, lè sa a 17. Si m 'fè insert ankò, se pou yo sote yon sèl. Olye pou yo 22, tankou pou chak foto a nou te te gade nan isit la, kite m 'so devan yo ak insert 26 pwochen an. Se konsa, mwen pral tape 26. Lis la se jan mwen espere. Men, kounye a, jis yo wè si sa a kòd a pwal fleksib, kite m 'kounye a kalite 22, ki omwen concept, si nou ap Kenbe sa a Ranje, ki se tout bon pral fè yon lòt objektif kounye a, ta dwe ale nan ant 17 ak 26. Se konsa, mwen frape Mete. Vreman vre, ki travay. Se konsa, kounye a kite m 'insert nan pase a, pou chak foto a, 34. Tout dwa. Se konsa, pou kounye a, kite m 'ladann ki Efase ak Traverse ak Search fè, an reyalite, travay. An reyalite, si mwen kouri Search, se pou yo rechèch pou yon nimewo pou la 22, Antre. Li te jwenn 22. Se konsa, ki se ki sa sa a pwogram Lis Zewo fè. Men, sa ki se aktyèlman ale sou ki aplike sa a? Oke, premye fwa mwen ta ka gen, ak tout bon Mwen gen, yon dosye rele list0.h. Ak yon kote nan gen sa a liy, tipedèf, konstri ne, Lè sa a, mwen gen aparèy òtopedik Curly mwen, Int n, ak Lè sa a, struct-- sa ki te definisyon an? Struct ne vini an. Se konsa, nou bezwen etwal la. Koulye a, teknikman nou jwenn nan abitid la nan desen li isit la. Ou ta ka wè liv ak referans sou entènèt fè li a. Li nan fonksyonèl ekivalan. An reyalite, sa a se yon ti kras pi plis òdinè. Men, mwen pral dwe konsistan ak sa nou te fè dènye fwa epi fè sa. Lè sa a, alafen, mwen pral fè sa. Se konsa, nan yon dosye header yon kote, nan list0.h jodi a se definisyon konstri sa a, e petèt kèk bagay lòt. Pandan se tan nan list0c gen nan pral gen yon bagay kèk. Men, nou ap ale nan jis kòmanse epi yo pa fini sa a. List0.h se yon dosye mwen vle genyen ladan yo nan dosye mwen C. Lè sa a, nan kèk pwen mwen se ale nan gen Int, prensipal la, anile. Lè sa a, mwen pral gen kèk a-fè a isit la. Mwen tou pral gen yon pwototip, tankou anile, rechèch, Int, n, objektif ki gen nan lavi a se pou fè rechèch pou yon eleman. Lè sa a, desann isit la mwen reklame nan Kòd jodi a, anile, rechèch, Int, n, pa gen okenn virgules men louvri aparèy òtopedik Curly. Koulye a, mwen vle yon jan kanmenm rechèch pou yon eleman nan lis sa a. Men, nou pa gen ase enfòmasyon sou ekran an ankò. Mwen gen pa aktyèlman reprezante lis nan tèt li. Se konsa, yon fason nou te ka aplike yon lis lye nan yon pwogram se mwen kalite vle fè yon bagay tankou deklare lye lis moute isit la. Pou senplisite, mwen pral fè sa a mondyal, menm si nan nou jeneral pa ta dwe fè sa a twòp. Men, li va senplifye egzanp sa a. Se konsa, mwen vle deklare yon lis moute isit la lye. Koulye a, ki jan mwen ta ka fè sa? Isit la nan foto a nan yon lis lye. Apre sa, mwen pa fè sa vrèman konnen nan moman sa a ki jan Mwen pral ale sou reprezante bagay sa yo anpil ak yon sèl jis varyab nan memwa. Men, panse tounen yon ti moman. Tout tan sa a nou te gen strings, ki nou Lè sa a, devwale yo dwe ranje nan karaktè, ki nou Lè sa a, devwale bay jis pou yon konsèy karaktè nan premye nan yon etalaj de karaktè ki nan nil sispann. Se konsa, pa ki lojik, epi ak sa a foto kalite ansmans panse ou, sa bezwen nou aktyèlman ekri nan nou an Kòd ki reprezante yon lis lye? Ki kantite nan enfòmasyon sa a nou bezwen pran nan C kòd, ou ta di? Yeah? ODYANS: Nou bezwen yon konsèy nan yon ne. DAVID J. Malan: yon konsèy nan yon ne. An patikilye, ki ne ta ou ensten gen kenbe yon konsèy nan? ODYANS: ne an premye. DAVID J. Malan: Yeah, pwobableman jis premye a. Ak avi, premye a ne se yon fòm diferan. Li nan sèlman mwatye gwosè a nan konstri a, paske li nan tout bon sèlman yon konsèy. Se konsa, sa ou ka fè se tout bon deklare yon lis lye yo dwe nan kalite ne *. Li kite yo jis rele li premye ak inisyalize li a nil. Se konsa, nil, ankò, se vini nan foto a isit la. Se pa sèlman se nil itilize kòm tankou yon espesyal retounen valè pou bagay sa yo tankou getstring ak malok, nil se tou zewo a konsèy, mank nan yon konsèy, si ou vle. Li jis vle di pa gen anyen ki ankò isit la. Koulye a, an premye, mwen te kapab te gen rele anyen sa a. Mwen te kapab yo te rele li "lis" oswa nenpòt ki kantite lòt bagay. Men, mwen rele li "premye" pou ke liy li moute ak foto sa a. Se konsa, jis tankou yon fisèl ka reprezante ak adrès la an premye multiple li yo, se konsa kapab yon lis lye. Epitou, n ap wè lòt done dwe reprezante estrikti ak sèlman yon sèl konsèy, yon flèch 32-ti jan, montre nan ne an trè premye nan estrikti an. Men koulye a, se pou yo antisipe yon pwoblèm. Si mwen sèlman sonje nan pwogram mwen an adrès la nan ne an premye, premye a rektang nan estrikti sa a done, sa te gen pi bon dwe ka a sou la aplikasyon nan rès la nan lis mwen an? Ki sa ki nan yon detay kle ki k ap pase asire sa a aktyèlman ap travay? Ak pa "aktyèlman ap travay" Mwen vle di, anpil tankou yon fisèl, pèmèt nou ale nan karaktè nan premye nan non Davin nan dezyèm lan, nan twazyèm lan, nan la katriyèm, nan fen a trè, jan nou konnen lè nou ap nan fen a nan yon lis lye ki sanble tankou sa a? Lè li nan nil. Apre sa, mwen te reprezante sa a sòt de jan tankou yon fòs enjenyè elektrik, ak baz la ti kras senbòl, nan kalite. Men, ki jis vle di nil nan ka sa a. Ou ka trase li nenpòt ki nimewo nan fason, men sa a otè ki te pase yo sèvi ak senbòl sa a isit la. Se konsa, lontan ke nou ap stringing tout nœuds sa yo ansanm, sèlman sonje ki kote youn nan premye se, se konsa tan kòm nou mete yon senbòl espesyal nan ne a trè dènye nan lis la, epi nou pral sèvi ak nil, paske se sa sa nou genyen disponib nan nou, lis sa a se konplè. E menm si mwen sèlman ba ou yon konsèy nan eleman an premye, ou menm, pwogramè a, kapab sètènman jwenn aksè nan rès la nan li. Men, kite a kite lespri ou moute desann yon ti jan, si yo pa ap deja byen wandered-- sa ki nan pral fè tan an kouri nan jwenn anyen nan lis sa a? Damn li, li nan gwo O n, ki se pa move, nan etidye ekite Règleman. Men, li se lineyè. Nou te bay moute ki sa karakteristik nan ranje pa deplase plis nan direksyon foto sa a nan dynamique tise ansanm oswa lye nœuds? Nou te bay moute aksè o aza. Yon etalaj se bèl paske matematik tout bagay se tounen nan bak nan do nan tounen. Menm si foto sa a sanble trè, e menm menm si li sanble sa yo nœuds yo joliman espace apa, an reyalite yo te kapab nenpòt kote. OX1, Ox50, Ox123, Ox99, sa yo nœuds te kapab nenpòt kote. Paske malok fè asiyen memwa soti nan pil wòch la, men nenpòt kote nan pil wòch la. Ou pa nesesèman konnen ke li nan pral fè tounen nan tounen nan tounen. Se konsa, foto sa a nan reyalite a pa pral yo dwe byen sa a bèl. Se konsa, li nan pral pran yon ti jan nan travay aplike fonksyon sa a. Se konsa, kite a aplike rechèch kounye a. Epi nou pral wè kalite yon entelijan fason pou fè sa a. Se konsa, si mwen menm ki yon fonksyon rechèch ak Mwen bay yon varyab, nonb antye ki pè n yo gade pou li a, mwen bezwen konnen nan nouvo sentaks pou kap andedan nan yon estrikti sa a, se pwente nan, yo jwenn n. Se konsa, kite a fè sa. Se konsa, premye fwa mwen pral ale pi devan epi deklare yon ne *. Men, mwen pral yo rele li konsèy, jis pa konvansyon. Men, mwen pral inisyalize li nan premye. Epi, koulye a mwen ka fè sa nan yon nimewo nan fason. Men, mwen pral pran yon apwòch komen. Pandan ke konsèy se pa egal a nil, epi ki nan sentaks ki valid. Epi li jis vle di fè bagay sa a, se konsa lontan ke ou pa ap lonje dwèt nan pa gen anyen. Ki sa mwen vle fè? Si konsèy dot n, kite m 'tounen ak sa yo ki, equals-- egal ki sa? Ki valè mwen chèche pou? N aktyèl la ki te pase nan. Se konsa, isit la nan yon lòt karakteristik nan C ak plizyè lang. Menm si estrikti rele ne a te gen yon n valè, totalman lejitim yo te genyen tou yon agiman lokal oswa varyab rele n. Paske menm nou, ak je moun, ka distenge ki n sa a se prezimableman diferan de n sa a. Paske sentaks la se diferan. Ou te gen yon dot ak yon konsèy, Lè nou konsidere ke yon sèl sa a pa gen okenn bagay sa yo. Se konsa, sa a se OK. Sa a OK yo rele yo menm bagay yo. Si m 'ou jwenn sa a, mwen se ale nan vle fè yon bagay tankou anonse ke nou te jwenn n. Epitou, n ap kite ke kòm yon kòmantè oswa kòd pseudocode. Lòt moun, ak isit la a nan enteresan pati, sa ki fè mwen vle fè si ne aktyèl la se pa ki gen n ke mwen pran swen sou? Kouman pou mwen reyalize sa ki annapre yo? Si dwèt mwen nan la moman sa a se ptr, epi li lonje dwèt nan tou sa premye ap lonje dwèt nan, ki jan mwen deplase dwèt mwen ne nan pwochen nan kòd? Oke, sa ki nan myèt nan nou ap ale nan swiv nan ka sa a? ODYANS: [fèbl]. DAVID J. Malan: Yeah, se konsa vini an. Se konsa, si mwen tounen al jwenn mwen Kòd isit la, tout bon, mwen se pral ale pi devan epi di konsèy, ki se jis yon varyab pou yon ti tan li a yon non etranj, ptr, men li nan jis tankou temp-- Mwen pral mete konsèy egal a tou sa konsèy is-- e ankò, sa a se pral gen yon ti kras buggy pou yon dot moment-- vini an. Nan lòt mo, mwen pral pran m ' dwèt ki nan montre nan sa a ne isit la ak mwen pral di, ou konnen ki sa, pran yon gade nan jaden nan pwochen yo epi li deplase dwèt ou nan tou sa li nan montre nan. Lè sa a ki pral repete, repete, repete. Men, lè fè dwèt mwen sispann fè anyen nan tout? Le pli vit ke sa ki liy nan anvwaye kòd nan? ODYANS: [fèbl] DAVID J. Malan: Si pwen pandan y ap konsèy se pa egal a nil. Nan kèk pwen nan dwèt mwen yo pral montre nan nil ak mwen pral reyalize sa a, se nan fen lis sa a. Koulye a, sa a se yon ti kras manti blan pou senplisite. Li sanble ke menm si nou jis te aprann sa a notasyon dot pou estrikti, konsèy se pa yon konstri. ptr se ki sa? Jis yo dwe plis nitpicky. Li se yon konsèy nan yon ne. Li pa yon ne tèt li. Si m 'pa te gen okenn zetwal isit la, konsèy absolutely-- li nan yon ne. Sa a se tankou semèn youn deklarasyon nan yon varyab, menm si mo "ne" se nouvo. Men, le pli vit ke nou prezante yon etwal, li la kounye a yon konsèy nan yon ne. Ak malerezman ou pa kapab itilize notasyon an dot pou yon konsèy. Ou gen yo sèvi ak flèch la notasyon, ki, fason frapan, se premye fwa a nenpòt moso pyès nan sentaks sanble entwisyon. Sa a literalman sanble yon flèch. Se konsa, sa a, se yon bon bagay. , Li desann isit la literalman sanble yon flèch. Se konsa, mwen panse ke sa ka la-- a mwen pa fè sa panse mwen sou-komèt here-- mwen panse ke sa ka pase a moso nan nouvo nan sentaks nou ap ale nan wè. Ak Erezman, li la tout bon yon ti kras plis entwisyon. Koulye a, pou moun nan nou ki ta ka prefere wout la fin vye granmoun, ou ka toujou itilize notasyon a dot. Men, tankou pou chak Lendi a konvèsasyon, nou premye bezwen ale a, ale nan ki adrès, ak Lè sa a, jwenn aksè nan jaden an. Se konsa, sa a se tou kòrèk. Ak franchman, sa a se yon ti kras pi plis pedant. W ap literalman di, dèreferans konsèy la ak ale la. Lè sa a, gen tan pwan .n, jaden an te rele n. Men, franchman, pesonn pa vle tape oswa li sa a. Se konsa, mond lan envante notasyon a flèch, ki ki ekivalan, ki idantik, li nan jis sik Massachusetts Institute of Technology. Se konsa, yon fason anpenpan nan di sa a sanble pi bon, oswa sanble pi senp. Se konsa, koulye a, mwen mwen pral fè yon lòt bagay. Mwen pral di "kraze" yon fwa mwen te jwenn li se konsa mwen pa kenbe kap chèche li. Men, sa a se esansyèl la nan yon fonksyon rechèch. Men, li la yon anpil pi fasil, an nan fen, pa mache nan kòd la. Sa a se tout bon aplikasyon an fòmèl nan rechèch nan kòd distribisyon a jodi a. Mwen bay gabèl di ke insert se pa patikilyèman plezi yo mache nan vizyèlman, ni se efase, menm menm si nan fen an nan jounen an yo bouyi desann nan san patipri eristik senp. Se konsa, kite a fè sa. Si ou pral imè m 'isit la, mwen te fè pote yon pakèt moun sou voye boul estrès. Mwen te fè yon pakèt moun nan nimewo. Epi li ka nou jwenn jis yon kèk volontè ki reprezante 9, 17, 20, 22, 29, ak 34? Se konsa, esansyèlman tout moun ki moun ki nan isit la jodi a. Sa ki te yon sèl, de, twa, kat, senk, sis moun. Apre sa, mwen ve yo te mande yo go-- wè, pa gen okenn youn nan do a ogmante men yo. OK, yonn, de, twa, kat, five-- kite m 'chaje balance-- sis. OK, ou sis vini sou yo. Nou pral bezwen lòt moun. Nou pote l 'voye boul estrès siplemantè. Men, si ou te kapab, pou jis yon, liy moman sa nou moute jis tankou foto sa a isit la. Tout dwa. Ann wè, ki sa nan non ou? ODYANS: Andre. DAVID J. Malan: Andre, ou se nimewo 9. Nice al kontre ou. Isit la ou ale. ODYANS: Jen. DAVID J. Malan: Jen. David. Nimewo 17. Wi? ODYANS: mwen se Julia. DAVID J. Malan: Jili, David. Nimewo 20. ODYANS: kretyen. DAVID J. Malan: kretyen, David. Nimewo 22. Epi? ODYANS: JP. DAVID J. Malan: JP. Nimewo 29. Se konsa, ale pi devan epi pou yo jwenn in-- Uh oh. Uh oh. Sibstiti an. 20. nenpòt moun ki gen yon makè? ODYANS: Mwen te gen yon sharpie. DAVID J. Malan: Ou te resevwa yon sharpie? OK. Epi nenpòt moun ki gen yon moso papye? Save konferans la. Vini non sou. ODYANS: Nou te gen li. DAVID J. Malan: Nou te resevwa li? Tout dwa, di ou mèsi. Isit la nou ale. Te sa a nan men ou? Ou jis sove jou a. Se konsa, 29. Tout dwa. Mwen mal ekri 29, men OK. Ale pi devan. Tout dwa, Mwen pral ba w plim ou tounen ti tan. Se konsa, nou gen sa yo jan isit la. Se pou nou gen yon sèl lòt. Gabe, ou vle jwe eleman nan premye isit la? Nou pral bezwen ou nan pwen nan jan amann sa yo. Se konsa, 9, 17, 20, 22, sòt nan 29, ak Lè sa a, 34. Èske nou pèdi yon moun? Mwen fè gen yon 34. Ki kote did-- OK, ki moun ki vle gen 34? OK, vini sou yo, 34. Tout dwa, sa a pral byen vo Pi gwo pwen an. Ki sa ki nan non ou? ODYANS: Pyè. DAVID J. Malan: Pyè, vini sou yo. Tout dwa, se konsa isit la nan yon pakèt antye nan nœuds. Chak nan ou nèg reprezante youn nan rektang sa yo. Epi Gabe, yon ti kras enpè nan nonm soti, reprezante premye. Se konsa, konsèy l 'yo se yon ti kras pi piti sou ekran an pase tout lòt moun. Ak nan ka sa a, chak nan ou kite men ki pral swa pwen desann, kidonk reprezante nil, se konsa jis absans la nan yon konsèy, oswa li a pral yo dwe montre nan yon ne kap vini jwenn ou. Se konsa, kounye a si ou dekore nou tankou foto a isit la, ale pi devan epi pwen nan chak lòt, ak Gabe nan montre patikilye nan Nimewo 9 a reprezante lis la. OK, ak nimewo 34, men gòch ou ta dwe jis dwe montre nan etaj la. OK, se konsa sa a se lis la lye. Se konsa, sa a se senaryo a nan kesyon an. Ak tout bon, sa a se reprezantan nan yon klas nan pwoblèm ke ou ta ka eseye rezoud ak kòd. Ou vle finalman insert yon eleman nouvo nan lis la. Nan ka sa a, nou ap ale nan eseye mete nimewo a 55. Men, gen nan pral fè ka diferan nan konsidere. Ak tout bon, sa a se pral yo dwe youn nan gwo-foto a takeaways isit la, se, ki sa yo diferan ka yo. Ki sa ki diferan nan si kondisyon oswa branch ki pwogram ou an ta ka genyen? Oke, nimewo a ou ap eseye insert, ki nou konnen kounye a yo dwe 55, men si ou pa t 'konnen nan avanse, mwen daresay tonbe nan omwen twa sitiyasyon posib. Ki kote yon eleman nouvo ta ka? ODYANS: Lè fen a oswa presegondè. DAVID J. Malan: Nan fen a, nan mitan an, oswa nan konmansman an. Se konsa, mwen fè reklamasyon gen nan omwen twa pwoblèm nou bezwen rezoud. Se pou yo chwazi sa ki nan petèt joui pi senp la yon sèl, kote eleman nan nouvo ki dwe nan kòmansman an. Se konsa, mwen ale nan gen Kòd byen tankou rechèch, ki mwen jis te ekri. Men, mwen pral gen ptr, ki Mwen pral reprezante isit la ak dwèt mwen, kòm dabitid. Epi sonje, sa ki valè t 'nou inisyalize ptr? Se konsa, nou initialisé li a nil okòmansman. Men, Lè sa a, nou sa nou te fè yon fwa nou yo te andedan fonksyon rechèch nou an? Nou mete l 'egal a an premye, ki pa vle di fè sa. Si m 'mete ptr egal a an premye, sa ki ta dwe men m 'vrèman dwe montre nan? Dwa. Se konsa, si Gabe ak mwen yo pral yo dwe valè egal isit la, nou bezwen tou de pwen nan nimewo 9. Se konsa, sa a te nan konmansman an nan istwa nou an. Epi, koulye a sa a se jis dwat, menm si sentaks la se nouvo. Concept sa a se jis rechèch lineyè. Se 55 egal a 9? Oswa olye, kite a di mwens pase 9. Paske mwen ap eseye konnen ki kote yo mete 55. Mwens pase 9, mwens pase 17, mwens pase 20, mwens pase 22, mwens pase 29, mwens pase 34, pa gen okenn. Se konsa, kounye a nou ap nan ka youn nan omwen twa. Si m 'vle insert 55 sou isit la, sa ki liy nan kòd bezwen jwenn egzekite? Kijan foto sa a nan moun bezwen chanje? Kisa pou mwen fè ak men gòch mwen an? Sa a ta dwe nil okòmansman, paske mwen se nan fen nan lis la. Ak sa ki ta dwe rive isit la ak Pyè, li te ye? Li te evidamman ale nan lonje dwèt sou mwen. Se konsa, mwen fè reklamasyon gen nan omwen de liy nan kòd nan kòd la echantiyon soti nan jodi a ki nan ale nan aplike sa a senaryo nan ajoute 55 nan ke la. Epi li ka Mwen gen yon moun hop moute ak jis reprezante 55? Tout dwa, ou se nouvo 55 an. Se konsa, kounye sa ki si pwochen an senaryo vini ansanm, epi nou vle insert nan la kòmanse oswa tèt la nan lis sa a? Ak sa ki nan non ou, nimewo 55? ODYANS: Jack. DAVID J. Malan: Jack? OK, bèl al kontre ou. Byenveni abò. Se konsa, kounye a nou ap ale nan insert, di, nimewo a 5. Isit la nan ka, dezyèm lan a nan twa nou te vini ak anvan. Se konsa, si 5 ki dwe nan kòmansman an, kite a wè ki jan nou jwenn ke deyò. Mwen inisyalize ptr mwen konsèy nan nimewo 9 ankò. Apre sa, mwen reyalize, oh, 5 se mwens pase 9. Se konsa, ranje foto sa a pou nou. Ki gen men, Gabe a oswa David la or-- sa ki nan non nimewo 9 la? ODYANS: Jen. DAVID J. Malan: hands-- Jen an ki nan men nou an bezwen chanje? OK, se konsa Gabe pwen nan sa ki kounye a? Nan m '. Se mwen menm ki ne la nouvo. Se konsa mwen pral jis kalite mouvman la a yo wè li vizyèlman. Ak pandan se tan sa m 'pwen sa? Toujou kote mwen lonje dwèt. Se konsa, ki nan li. Se konsa, jis reyèlman yon sèl liy nan Kòd fikse pwoblèm sa a an patikilye, li ta sanble. Tout dwa, kidonk sa a, se bon. Epi yo ka yon moun gen yon kontneur pou 5? Vini non sou yo. Nou pral fè ou jwenn pwochen fwa. Tout dwa, kidonk now-- ak kòm yon sou kote, non yo Mwen pa fè eksplisit mansyone nan dwa kounye a, pred konsèy, predesesè konsèy ak nouvo konsèy, sa a, se jis non yo bay nan echantiyon kòd la endikasyon yo oswa men m 'ki nan kalite montre alantou. Ki sa ki nan non ou? ODYANS: Christine. DAVID J. Malan: Christine. Byenveni abò. Tout dwa, kidonk kite a konsidere kounye a yon senaryo yon ti kras plis anmèdan, kijan mwen vle insert yon bagay tankou 26 an sa a. 20? Ki sa? Sa yo are-- bon bagay nou gen plim sa a. Tout dwa, 20. Si yon moun te kapab jwenn yon lòt moso nan papye ki pare, jis nan case-- tout dwa. Oh, ki enteresan. Oke sa a se yon egzanp nan yon ensèk konferans. OK Se konsa, sa nan non ou ankò? ODYANS: Julia. DAVID J. Malan: Julia, ka ou pòp soti ak pretann ou te pa janm genyen? OK, sa a pa janm rive. Mèsi poutèt ou. Se konsa, ta kwè nou vle insert Julia nan lis sa a lye. Li se nimewo a 20. Ak nan kou li nan ale nan apatni a an begin-- pa pwen nan anyen ankò. Se konsa, men ou kapab kalite gen desann nil oswa kèk valè fatra. Se pou yo rakonte istwa a rapid. Mwen lonje dwèt nan nimewo 5 moman sa a. Lè sa a, mwen tcheke 9. Lè sa a, mwen tcheke 17. Lè sa a, mwen tcheke 22. Apre sa, mwen reyalize, Ooh, Julia bezwen ale anvan 22. Se konsa, sa bezwen yo rive? Ki gen men bezwen chanje? Julia a, min, or-- sa ki nan non ou ankò? ODYANS: kretyen. DAVID J. Malan: kretyen oswa? ODYANS: Andy. DAVID J. Malan: Andy. Kretyen oswa Andy? Andy bezwen nan pwen nan? Julia. Tout dwa. Se konsa, Andy, ou vle nan pwen nan Julia? Men, tann yon minit. Nan istwa a konsa byen lwen, Mwen se sòt nan nan yon sèl an chaj, nan sans ke konsèy se bagay ki sa a, se k ap deplase nan lis la. Nou ta ka gen yon non pou Andy, men gen nan pa gen varyab rele Andy. Sèlman lòt varyab la nou genyen se premye, moun ki nan reprezante pa Gabe. Se konsa, sa a se aktyèlman poukisa konsa byen lwen nou pa te nesesè sa a. Men koulye a, sou ekran an gen mansyone ankò nan pred konsèy. Se konsa, kite m 'gen plis eksplisit. Si sa a se konsèy, mwen te pi bon jwenn yon ti kras plis entelijan sou iteration mwen. Si ou pa lide m 'ale atravè tout isit la ankò, montre isit la yo, montre isit la. Men, kite m 'gen yon konsèy pred, predesesè konsèy, sa a, se kalite montre nan nan eleman Mwen te jis nan. Se konsa, lè m 'ale isit la, kounye a dènye kite men mwen. Lè m 'ale isit la dènye enfòmasyon gòch men mwen. Epi, koulye a mwen gen pa sèlman yon konsèy nan eleman an ki ale apre Jili, Mwen toujou gen yon konsèy nan Andy, eleman nan anvan. Se konsa, ou gen aksè, esansyèlman, pen, si ou vle, nan tout nan pwent yo voulu. Se konsa, si mwen montre nan Andy ak mwen tou lonje dwèt nan kretyen, ki gen men ta dwe kounye a dwe pwente yon lòt kote? Se konsa, Andy kapab kounye a pwen nan Julia. Julia kapab kounye a pwen nan kretyen. Paske li ka kopye mwen konsèy men dwat la. Epi sa efektivman mete ou tounen nan kote sa a isit la. Se konsa, nan kout, menm si sa a ap pran nou kalite pou tout tan yo aktyèlman mete ajou yon lye lis, reyalize ki operasyon yo yo se relativman senp. Li nan nan yon sèl, de, twa liy nan kòd finalman. Men, mare nan ren moun liy nan kòd prezimableman se yon ti jan nan lojik ki efektivman mande kesyon an, kote nou ye? Eske nou kwè nou nan kòmansman an, mitan an, oswa nan fen a? Koulye a, gen sètènman kèk lòt operasyon nou ta ka aplike. Ak foto sa yo isit la jis dekri sa nou jis te fè ak moun. Ki sa ki sou retire elèv? Si m 'vle, pou egzanp, retire nimewo a 34 oswa 55, Mwen ta ka gen kalite a menm nan kòd, men mwen m 'ale nan bezwen youn oubyen de etap. Paske sa ki nouvo? Si mwen retire yon moun nan fen a, tankou nimewo 55 ak Lè sa a, 34, sa tou te gen yo chanje jan mwen fè sa? Mwen gen pa evict-- sa ki nan non ou ankò? ODYANS: Jack. DAVID J. Malan: Jack. Mwen gen pa sèlman evict-- gratis Jack, se konsa literalman rele gratis Jack, oswa omwen konsèy la gen twò, men kounye a sa ki bezwen yo chanje avèk Pyè? Men l 'pi bon kòmanse lonje dwèt desann. Paske le pli vit ke mwen rele gratis sou Jack, si Pyè a toujou montre nan Jack ak mwen poutèt sa kenbe Travelers lis la ak aksè konsèy sa a, ki nan lè zanmi segmentation fin vye granmoun nou fòt ta ka aktyèlman choute nan. Paske nou te bay la tounen memwa Jack. Ou ka rete la malabiyman sèlman pou moman yon. Paske nou gen jis yon koup operasyon final nan konsidere. Retire tèt la nan lis la, oswa beginning-- a ak yon sèl sa a nan yon ti kras anmèdan. Paske nou gen konnen ke Gabe se kalite espesyal nan pwogram sa a. Paske tout bon, li te gen konsèy pwòp tèt li. Li pa nan jis yo te pwente nan, kòm se prèske tout lòt moun isit la. Se konsa, lè tèt la nan lis la se retire, ki gen men bezwen chanje kounye a? Ki sa ki nan non ou ankò? ODYANS: Christine. DAVID J. Malan: mwen se terib nan non, aparamman. Se konsa, Christine ak Gabe, ki gen men bezwen chanje lè nou eseye retire Christine, nimewo 5, ki soti nan foto a? OK, se konsa se pou yo fè Gabe. Gabe k ap pase nan pwen, prezimableman, nan nimewo 9. Men, sa ki pwochen ta dwe rive? ODYANS: Christine ta dwe pral nil [fèbl]. DAVID J. Malan: OK, nou ta dwe pwobableman make-- Mwen tande "nil" yon kote. ODYANS: Null ak gratis l '. DAVID J. Malan: nil ki sa? ODYANS: Null ak gratis l '. DAVID J. Malan: Null ak gratis l '. Se konsa, sa a se trè fasil. Lè li nan pafè ke w ap kounye a sòt nan kanpe la, pa sa ki. Paske ou ve yo te découplé nan lis la. Ou te efektivman te òfelen nan lis la. Se konsa, nou te gen pi bon rele gratis kounye a sou Christine bay ki memwa tounen. Sinon chak fwa nou efase yon ne nan lis la nou kapab fè lis la pi kout, men se pa aktyèlman diminye gwosè a nan memwa. Se konsa, si nou kenbe ajoute ak pandan l ajoute, pandan l ajoute bagay sa yo nan lis la, òdinatè mwen ta ka jwenn pi dousman ak pi dousman ak pi dousman, paske mwen m 'kouri soti nan memwa, menm si mwen pa aktyèlman lè l sèvi avèk bytes Christine a nan memwa ankò. Se konsa, nan fen a, gen lòt senaryo, nan retire course-- nan mitan, pou retire elèv la nan fen a, kòm nou te wè. Men, plis enteresan an defi kounye a se pral fè yo konsidere egzakteman ki lè an kouri se. Se konsa, pa sèlman ou ka kenbe ou moso papye, si, Gabe, ou pa ta lide bay tout moun yon boul estrès. Mèsi poutèt ou tèlman yo lis lye nou an nan volontè isit la, si ou te kapab. [Aplodisman] DAVID J. Malan: Tout dwa. Se konsa, yon koup la analyse kesyon Lè sa a,, si mwen te kapab. Nou te wè notasyon sa a anvan, gwo O ak Omega, limit anwo ak pi ba limit sou la kouri tan nan kèk algorithm. Se konsa, kite a konsidere jis yon koup nan kesyon. Youn, epi nou di li anvan, sa ki nan kouri a lè nan rechèch pou yon lis an tèm de gwo O? Ki sa ki nan yon limit siperyè sou kouri a tan nan chèche yon lis lye kòm aplike pa volontè nou isit la? Li nan gwo O n, lineyè. Paske nan ka ki pi mal, eleman nan, tankou 55, nou ta ka kap pou ta kapab ki kote Jack te, tout wout la nan fen an. Ak malerezman, kontrèman ak yon etalaj nou pa ka jwenn anpenpan tan sa a. Menm si tout nan moun nou yo te ranje soti nan eleman piti, 5, tout wout la jiska eleman nan pi gwo, 55, ki nan anjeneral yon bon bagay. Men, sa ki fè sa sipozisyon pa gen okenn ankò pèmèt nou fè? ODYANS: [fèbl] DAVID J. Malan: Di ankò? ODYANS: Random aksè. DAVID J. Malan: Random aksè. Ak nan vire sa vle di nou kapab pa gen okenn sèvi ankò ak zewo fèb, entwisyon, ak evid a lè l sèvi avèk binè rechèch ak divize ak konkeri. Paske menm si nou moun te kapab evidamman wè ke Andy oswa kretyen yo te apeprè nan mitan an nan lis la, nou ka konnen sèlman ke kòm yon òdinatè pa ekremaj lis la depi nan konmansman an anpil. Se konsa, nou te bay moute ke aksè o aza. Se konsa, gwo O n kounye a se anwo a mare sou tan rechèch nou an. Ki sa ki sou omega nan rechèch nou an? Ki sa ki nan pi ba a mare sou chèche pou kèk nimewo nan lis sa a? ODYANS: [fèbl] DAVID J. Malan: Di ankò? ODYANS: Yon. DAVID J. Malan: Yon. Se konsa, konstan tan. Nan ka ki pi bon, Christine se tout bon nan kòmansman an nan lis la. Epi nou ap chèche pou nimewo 5, se konsa nou jwenn l '. Se konsa, pa gen okenn kontra gwo. Men, li te nan te resevwa yo dwe nan a kòmanse nan lis la nan ka sa a. Ki sa ki sou yon bagay tankou efase? E si ou vle efase yon eleman? Ki sa ki nan mare a anwo ak pi ba mare sou efase yon bagay ki soti nan yon lye lis? ODYANS: [fèbl] DAVID J. Malan: Di ankò? ODYANS: n. DAVID J. Malan: n se tout bon anwo a mare. Paske nan ka ki pi mal nou eseye efase Jack, tankou nou jis te fè. Li nan tout wout la nan fen an. Pran nou pou tout tan, oswa n etap sa yo jwenn li. Se konsa, se yon limit siperyè. Sa a lineyè, asire w. Epi ka-a pi bon kouri tan, oswa limit ki pi ba nan ka a pi bon ta dwe tan konstan. Paske petèt nou eseye efase Christine, epi nou jis jwenn chans li la nan kòmansman an. Koulye a, rete tann yon minit. Gabe te tou nan kòmansman an, ak nou menm tou te gen yo mete ajou Gabe. Se konsa, sa ki te pa jis yon sèl etap. Se konsa, li tout bon konstan tan, nan ka a pi bon, yo retire eleman ki pi piti? Li se, menm si li ta ka de, twa, oswa menm 100 liy nan kòd, si li nan menm kantite liy, pa nan kèk riban, ak endepandan nan gwosè a nan lis la, absoliman. Efase eleman an nan nan konmansman an nan lis la, menm si nou gen fè fas ak Gabe, se toujou tan konstan. Se konsa, sa sanble tankou yon masiv etap bak. Ak sa ki yon fatra nan tan si, nan semèn yon sèl ak semèn zewo nou te gen pa sèlman Kòd pseudocode men Kòd aktyèl aplike yon bagay ki nan boutèy demi lit baz n, oswa ale, olye, nan n, baz 2, an tèm de tan kouri li yo. Se konsa, poukisa èk an nou ta vle kòmanse lè l sèvi avèk yon bagay tankou yon lis lye? Yeah. ODYANS: Se konsa, ou kapab ajoute eleman etalaj la. DAVID J. Malan: Se konsa, ou kapab ajoute eleman etalaj la. Lè sa a tou se tematik. Epitou, n ap kontinye wè sa a, sa a komès-off, anpil tankou nou te wè yon komès-off ak sòt unifye. Nou te ka reyèlman pi vit rechèch oswa klasman, olye, si nou depanse yon espas ti jan pi plis ak gen yon ti moso anplis nan yon memwa oswa yon etalaj pou rantre sòt. Men, nou pase plis espas, men nou ekonomize tan. Nan ka sa a, nou ap bay moute tan, men nou ap pran fleksibilite, dynamism si ou pral, ki se joui yon karakteristik ki pozitif. Nou ap tou depans espas. Nan ki sans se yon lye lis pi chè an tèm de espas pase yon etalaj? Ki kote espas ki la siplemantè vini soti nan? Yeah? ODYANS: [fèbl] konsèy. DAVID J. Malan: Yeah, nou yo te genyen tou konsèy la. Se konsa, sa a se minorly anmèdan nan ki pa gen okenn ankò menm Mwen estoke jis yon int ki reprezante yon Int. Mwen estoke yon int ak yon konsèy, ki se tou 32 miyèt moso. Se konsa, mwen literalman double kantite lajan an nan espas ki enplike. Se konsa, ki se yon komès-off, men sa a, se nan ka a nan Int. Sipoze ke ou pa ap estoke Int, men ta kwè chak nan rektang sa yo oswa chak nan moun sa yo te reprezante yon mo, yon mo angle ki ta ka senk karaktè, 10 karaktè, petèt menm plis. Lè sa a, pandan l ajoute jis 32 plis Bits ta ka mwens nan yon kontra gwo. E si chak nan elèv yo nan demonstrasyon an yo te literalman strukt elèv ki gen non ak kay e petèt nimewo telefòn ak Twitter manch ak renmen an. Se konsa, tout nan jaden yo nou te kòmanse ap pale de lòt jou a, anpil mwens nan yon kontra gwo kòm nœuds nou jwenn plis enteresan ak gwo yo ap depanse, eh, yon lòt konsèy jis fè rapò ant yo ansanm. Men, tout bon, li nan yon komès-off. Ak tout bon, kòd la se pi konplèks, jan ou pral wè pa ekremaj a ki egzanp patikilye. Men, sa ki si te gen kèk grail apa pou Bondye isit la. E si nou pa pran yon etap bak men yon etap masiv pou pi devan epi aplike yon done estrikti via ki nou ka jwenn eleman tankou Jack oswa Christine oswa nenpòt lòt eleman nan sa a etalaj nan vrè tan konstan? Search se konstan. Efase se konstan. Antre se konstan. Tout moun nan operasyon sa yo, se konstan. Ki ta ka grail apa pou Bondye nou an. E ke se kote nou ap ranmase pwochen fwa. Al gade nan ou lè sa a.