[Powered by Google Translate] [Semèn 6, Kontinye] [David J. Malan] [Inivèsite Harvard] [Sa a se CS50.] [CS50.TV] Sa a se CS50 ak sa a se nan fen semèn 6. Se konsa, CS50x, youn nan kou premye Harvard la ki enplike nan èdo inisyativ sa a tout bon debut sa a Lendi sot pase yo. Si ou ta renmen yo ka resevwa yon aperçu nan ki sa lòt moun sou entènèt la yo kounye a se swiv ansanm ak, ou ka tèt a x.cs50.net. Ki pral redireksyon ou nan plas la apwopriye sou edx.org, ki te kote sa a ak lòt kou soti nan MIT ak Berkeley viv koulye a. Ou ap gen pou enskri pou yon kont, ou ap jwenn ki materyèl la se lajman menm bagay la tou menm jan ou te gen sa a semès, byen yon kèk semèn reta, menm jan nou jwenn tout bagay pare. Men, sa ki elèv ki nan CS50x pral wè koulye a se yon koòdone byen tankou sa youn. Sa a, pou egzanp, se Zamyla ki mennen solisyon pou ansanm pwoblèm 0. Lè li antre nan edx.org, yon elèv CS50x wè kalite ki nan bagay sa yo ou ta espere wè nan yon kou: konferans la pou Lendi a, konferans pou Mèkredi, bout pantalon divès kalite, ansanm sa yo, pwoblèm, valktroug yo, pdf. Anplis de sa, kòm ou wè la a, machin tradiksyon nan relve nòt angle nan Chinwa, Japonè, Espayòl, Italyen, ak yon pakèt antye nan lòt lang yo ki pral sètènman se enpafè jan nou woule yo soti kite programatik lè l sèvi avèk yon bagay yo rele yon API, oswa aplikasyon pwogram koòdone, ki soti nan Google ki pèmèt nou konvèti angle sa yo lòt lang yo. Men, gras a Lespri Bondye a bèl bagay nan kèk volontè san-plis, moun o aza sou Entènèt la ki te byen avè yo ofri patisipe nan pwojè sa a, nou pral piti piti pou amelyore bon jan kalite a nan moun ki tradiksyon pa gen moun korije erè sa yo ke òdinatè nou yo te fè fè yo. Se konsa, li vire soti nou te yon tijan plis elèv montre moute nan Lendi pase nou okòmansman atann. An reyalite, kounye a CS50x gen 100,000 moun swiv ansanm nan kay la. Se konsa, reyalize ou se tout yon pati nan klas sa a inogirasyon nan fè kou sa a nan syans òdinatè edikasyon plis jeneralman, plis lajman, ki aksesib. Ak reyalite a se kounye a, ak kèk nan kou sa yo masiv sou entènèt, yo tout kòmanse ak nimewo sa yo wo anpil, kòm nou yo sanble yo te fè isit la. Men, objektif la, finalman, pou CS50x se reyèlman jwenn moun kòm anpil nan liy lan fini ke posib. By konsepsyon, CS50x yo pral ofri sa a soti nan sot pase Lendi tout wout la nan, 15 avril 2013, se konsa ke jan ki gen angajman lekòl yon lòt kote, travay, fanmi, konfli ak lòt tankou an, gen yon ti jan pi plis fleksibilite ak ki plonje nan kou sa a, ki, sufi li vle di, se byen Ambisyon fè si sèlman sou kou nan de twa jis mwa pandan yon semès dabitid. Men, sa yo elèv yo ap fèt abòde ansanm sa yo, pwoblèm menm, gade kontni an menm, gen aksè a bout pantalon yo menm ak tankou la. Se konsa, reyalize ke nou tout nou vrèman nan sa a yo ansanm. Ak youn nan objektif yo nan fen CS50x se pa sèlman yo ka resevwa jan kòm anpil nan liy lan fini, e bay yo sa a konpreyansyon newfound nan syans òdinatè ak pwogramasyon, men tou yo fè yo gen eksperyans sa a pataje. Youn nan karakteristik sa yo defini nan 50 sou lakou lekòl la, nou espere, te gen sa a sòt de eksperyans kominotè, pou pi bon oswa pou pi mal, pafwa, men gen moun sa yo ale nan a gòch la ak sou bò dwat la, ak biwo èd tan ak hackathon la ak kèmès la. Li se yon ti kras pi difisil fè sa nan moun ki gen jan sou entènèt, men CS50x ap detèmine nan mwa avril ak premye tout tan Ekspozisyon an CS50, ki pral yon adaptasyon sou entènèt nan lide nou an jis nan kote sa yo dè milye de elèv yo tout pral envite yo soumèt yon 1 - a 2-minit videyo, swa yon skreankast nan pwojè final yo oswa videyo nan yo leve alo ak pale sou pwojè yo epi yo demoing li, anpil tankou chèf anvan ou te fè isit la sou kanpis lekòl-la jis la, pou ke nan fen semès la, se espwa a se gen yon egzibisyon mondyal nan pwojè final elèv yo CS50x ', anpil tankou sa ki ap tann nou isit la sou sa a desanm kanpis lekòl la. Se konsa, plis sou sa nan mwa ki ap vini yo. Avèk 100,000 elèv yo, menm si, vini yon bezwen pou yon sèrtifikasyon kèk plis. Sitiyasyon ou Etandone ke ou nèg yo ap flanm santye an isit la epi si w pran CS50 plizyè semèn nan avanse, ki se lage materyèl sa a nan jan yo sou èdo, reyalize nou ta renmen gen pou wè ak kòm anpil nan elèv yo pwòp nou ke posib nan inisyativ sa a, ni pandan semès la kòm byen ke sezon fredi sa a ak sa a sezon prentan vini yo. Se konsa, si ou ta renmen patisipe nan CS50x, patikilyèman rantre nan nan sou CS50x diskite, vèsyon an èdo nan CS50 diskite, ki anpil nan nou yo te lè l sèvi avèk nan kanpis la, tablo afichaj sou entènèt, tanpri fè tèt ak sa yo ki URL, fè nou konnen ki moun ou ye, paske nou ta renmen bati yon ekip nan elèv ak anplwaye lekòl ak pwofesè yo sanble sou lakou lekòl la ki yo se tou senpleman ap jwe ansanm epi ede deyò. Epi lè yo wè yon kesyon ki nan abitye yo: ou tande yon elèv rapòte kèk ensèk yon kote yo deyò nan kèk peyi sou Entènèt la, ak ke bag yon klòch paske ou twò te gen pwoblèm sa menm nan sal d-ou kèk tan de sa, èspere ke Lè sa a, ou ka sone nan epi pataje eksperyans pwòp ou yo. Se konsa, tanpri patisipe si ou ta renmen. Kou syans Odinatè nan Harvard gen yon ti jan nan yon tradisyon, CS50 nan mitan yo, pou yo gen kèk rad, kèk rad sou li, ke ou ka mete ak fyète nan fen semès la, yo di byen ak fyète ke ou fini CS50 , li pran CS50 ak renmen an, epi nou toujou eseye enplike elèv yo nan pwosesis sa a kòm anpil ke posib, annakò ak sa nou envite, alantou tan sa a nan semès la, elèv yo soumèt desen lè l sèvi avèk fotoschop, oswa kèlkeswa sa zouti nan chwa ou ta renmen itilize si ou se yon designer, yo soumèt desen pou mayo-yo ak swetè mayo ak parapli ak foula ti kras pou chen nou genyen kounye a ak renmen an. Ak tout bagay se lè sa a - ganyan yo chak ane yo Lè sa a, ekspoze sou sit entènèt kou a nan store.cs50.net. Tout bagay se vann nan pri a, men sou sit wèb la jis kouri tèt li ak pèmèt moun yo chwazi koulè yo ak desen yo ke yo renmen. Se konsa, mwen te panse nou ta jis pataje kèk nan desen ane pase a ki te sou sit entènèt la san konte yon sèl sa a isit la, ki se yon tradisyon chak ane. "Chak Jou mwen segman Faultn" se te youn nan observation yo ane pase a, ki se toujou disponib la pou ansyen elèv. Nou te gen yon sèl sa a, "CS50, Etabli 1989." Youn nan Bowdens nou an, Rob, te trè popilè ane pase a. "Ekip Bowden" te fèt, sa a te konsepsyon soumèt, nan mitan vandè an tèt yo. Kòm te yon sèl sa a isit la. Anpil moun te gen "Bowden Lafyèv" selon bwa nan lavant yo. Reyalize ke ki ta kapab kounye a gen konsepsyon ou gen, moute sou entènèt la. Plis detay sou sa nan pwoblèm nan pwochen kouche ap vini yo. Youn nan pi plis zouti: ou te te gen kèk ekspoze ak èspere ke kounye a yon ti eksperyans men-sou ak gdb, ki se, nan kou, yon debugjeur ak pèmèt ou manipile pwogram ou an nan yon nivo san patipri ki ba, ap fè sa kalite bagay? Ki sa ki gdb kite ou fè? Yeah? Ban m 'yon bagay. [Repons elèv, enkonpreansibl] Bon. Etap nan fonksyon, pou w pa jis gen nan tape kouri epi yo gen kou pwogram nan atravè nèt, enprime soti bagay sa yo nan pwodiksyon estanda. Olye de sa, ou ka etap atravè li liy pa liy, swa ou tape pwochen ale liy pa liy pa liy oswa etap plonje nan yon fonksyon, tipikman yon sèl ke ou te ekri. Ki lòt bagay gdb kite ou fè? Yeah? [Repons elèv, enkonpreansibl] Ekri an lèt detache varyab. Se konsa, si ou vle fè yon antre anndan nanm nou ti kras andedan nan pwogram ou an san yo pa gen Resort ekri deklarasyon printf sou tout plas la, ou ka jis enprime yon varyab oswa montre yon varyab. Ki lòt bagay ou ka fè ak yon debugjeur tankou gdb? [Repons elèv, enkonpreansibl] Egzakteman. Ou ka mete breakpoints; ou ka di ekzekisyon repo nan fonksyon prensipal oswa fonksyon nan foo. Ou ka di ekzekisyon repo nan liy 123. Ak breakpoints yo se yon teknik vrèman pwisan paske si w gen yon sans jeneral nan kote pwoblèm ou pwobableman se, ou pa bezwen gaspiye tan kite atravè antye pwogram nan. Ou ka esansyèlman so dwa gen ak Lè sa a, kòmanse sezisman - kite nan l 'ak etap oswa pwochen oswa tankou an. Men, trape an ak yon bagay tankou gdb se ke li ede ou, moun lan, jwenn pwoblèm ou epi jwenn pinèz ou a. Li pa nesesèman jwenn yo tèlman pou ou. Se konsa, nou prezante style50 a lòt jou, ki se yon lòd zouti kout liy ki ap eseye stilize kòd ou yon ti jan ti kras pi plis propr pase ou, moun lan, ta ka gen fè. Men, ki, tou, se reyèlman jis yon bagay ayestetik. Men, li vire soti gen nan zouti sa a lòt te rele Valgrind ki se yon ti kras pi plis Esoteric yo itilize. Pwodiksyon li se atrociously skre nan zye premye. Men, li la bèl bagay ki itil, espesyalman kounye a ke nou ap nan pati nan tèm nan ki kote ou kòmanse itilize malok ak dinamik alokasyon memwa. Bagay sa yo ka ale reyèlman, reyèlman mal byen vit. Paske si ou bliye libere memwa ou, oswa ou dèreferans kèk konsèy nil, oswa ou dèreferans kèk konsèy fatra, ki sa ki tipikman sentòm a ki rezilta? Segman fay. Epi ou jwenn sa a ranpli debaz nan kèk kantite kilookte oswa megabit ki reprezante eta a nan memwa pwogram ou an lè li te fè aksidan, men pwogram ou an finalman segman fot, fòt segmentation, ki vle di yon move bagay ki te pase prèske toujou ki gen rapò nan yon erè memwa ki gen rapò ak ke ou te fè kèk kote. Se konsa, Valgrind ap ede w jwenn bagay sa yo tankou sa a. Li se yon zouti ki ou kouri, tankou gdb, apre ou te konpile pwogram ou an, men olye ke kouri pwogram ou an dirèkteman, ou kouri Valgrind epi ou pase sou li pwogram ou an, jis tankou ou fè ak gdb. Koulye a, l 'a, yo ka resevwa kalite a pi bon nan pwodiksyon, se yon ti kras tan, se konsa dwa gen anlè nan ekran an ou pral wè Valgrind-V. "-V" prèske inivèsèl vle di sil lè w ap sèvi ak pwogram sou yon òdinatè Linux. Se konsa, sa vle di li krache soti plis done pase ou ka pa default. "- Fuit radyasyon-tcheke = plen." Sa a se jis di chèk pou tout fwit memwa sa posib, erè ke mwen te ka te fè fè yo. Sa a, tou, se yon paradigm komen avèk pwogram Linux. Anjeneral, si w gen yon agiman liy lòd sa a, se yon "switch", ki nan sipoze chanje konpòtman pwogram nan, ak li nan yon lèt yon sèl, li nan-V, men si ki nan commuté, jis pa konsepsyon nan pwogramè a, se yon mo plen oswa seri de mo, agiman an liy lòd kòmanse ak -. Sa yo se sèlman konvansyon moun, men ou pral wè yo de pli zan pli. Lè sa a,, finalman, "a.out" se non yo abitrè pou pwogram lan nan egzanp sa a an patikilye. Ak isit la a kèk pwodiksyon reprezantan. Anvan nou gade nan ki sa sa kapab vle di, kite m 'ale sou nan yon brib nan kòd sou isit la. Ak kite m 'deplase sa a soti nan wout la, vini byento, ak kite a pran yon gade nan memory.c, ki se egzanp sa a kout isit la. Se konsa, nan pwogram sa a, kite m 'rale nan sou fonksyon yo ak kesyon yo. Nou gen yon fonksyon prensipal ki mande yon fonksyon, f, ak Lè sa a, ki sa f kontinye nan fè sa, nan lang angle yon ti kras teknik? Ki sa ki f kontinye nan? Kouman sou mwen pral kòmanse avèk liy 20, ak kote etwal nan pa gen pwoblèm, men m ap jis dwe konsistan isit la ak konferans dènye. Ki sa ki nan liy 20 pou nou? Sou bò men gòch. Nou pral kraze li desann pi lwen. Int * x: ki sa sa fè? Oke. Li nan deklare yon konsèy, ak kounye a kite a gen menm plis teknik. Kisa sa vle di, trè konkrètman, deklare yon konsèy? Yon lòt moun? Yeah? [Repons elèv, enkonpreansibl] twò lwen. Se konsa, ou ap li bò lanmè a men dwat-ou nan siy ki egal. Se pou nou konsantre jis sou bò gòch la, jis sou int x *. Sa a "deklare" yon konsèy, men kounye a nan kite l 'plonje nan pi fon ak sa yo ki definisyon. Ki sa sa konkrètman, teknikman vle di? Yeah? [Repons elèv, enkonpreansibl] Oke. Li nan prepare pou konsève pou yon adrès nan memwa. Bon. Ak kite a pran etap sa a yon sèl pli lwen; li a deklare yon varyab, x, ki nan 32 Bits. Apre sa, mwen konnen li nan 32 Bits paske -? Li pa paske li nan yon int, paske li nan yon konsèy nan ka sa a. Konyensidans ke li nan yon sèl ak menm bagay la ak yon int, men lefèt ke gen nan zetwal la gen vle di sa a se yon konsèy ak nan aparèy la, menm jan ak òdinatè anpil, men se pa tout, endikasyon yo se 32 miyèt moso. Sou plis kenkayri modèn yo tankou Macs dènye yo, PC yo dènye yo, ou ka gen endikasyon 64-ti jan, men nan aparèy la, bagay sa yo se 32 miyèt moso. Se konsa, nou pral estandadize sou sa. Plis konkrètman, istwa an ale jan sa a: Nou "deklare" yon konsèy; ki sa sa vle di? Nou prepare nan magazen yon adrès memwa. Kisa sa vle di? Nou kreye yon varyab x rele ki pran moute 32 Bits ki pral byento sere adrès ki nan yon nonb antye relatif. Epi sa a, pwobableman sou kòm egzak kòm nou ka jwenn. Li nan amann deplase pou pi devan pou senplifye mond lan ak jis di deklare yon konsèy rele x. Deklare yon konsèy, men mwen reyalize ak konprann sa ki aktyèlman pral sou menm nan jis sa yo characters kèk. Koulye a, yon sèl sa a nan prèske yon ti kras pi fasil, menm si li nan yon ekspresyon pi long lan. Se konsa, sa sa a ap fè, ki nan make kounye a: "malok (10 * sizof (Int));" Yeah? [Repons elèv, enkonpreansibl] Bon. Apre sa, m'a pran l la. Li nan allocation yon ti moso nan memwa pou dis nonm antye relatif. Ak kounye a kite a plonje nan yon ti kras pi fon; li nan allocation yon ti moso nan memwa pou dis nonm antye relatif. Ki sa ki malok Lè sa a, retounen? Adrès postal la nan ki moso, oswa, plis konkrètman, adrès la nan multiple an premye nan ki moso. Ki jan Lè sa a, mwen ye menm pwogramè a, yo konnen kote ki ti moso nan dènye bout memwa? Mwen konnen ke li nan contiguous. Malok, pa definisyon, pral ba ou yon moso contiguous nan memwa. Pa gen twou vid ki genyen nan li. Ou gen aksè a tout multiple nan ki moso, tounen nan fè bak nan do, men ki jan mwen konnen ki kote nan fen sa a ti moso nan memwa se? Lè ou sèvi ak malok? [Repons elèv, enkonpreansibl] Bon. Ou pa fè sa. Ou gen sonje. Mwen gen sonje ke mwen te itilize valè a 10, epi mwen pa menm sanble yo te fè ki isit la. Men, apartyin a se antyèman sou m '. Strlèn, ki nou te vin yon ti kras reliant sou pou strings, travay sèlman paske sa a konvansyon ki gen \ 0 oswa sa a espesyal karaktè nul, nul, nan fen yon kòd. Ki pa kenbe pou jis sègman abitrè nan memwa. Li a jiska ou. Se konsa, liy 20, lè sa a, repati yon ti moso nan memwa ki ka magazen dis nonm antye yo, epi li estoke adrès ki nan multiple nan premye nan ki ti moso nan memwa nan x la varyab rele. Èrgo, ki se yon konsèy. Se konsa, liy 21, malerezman, se te yon erè. Men, an premye, ki sa ki li ap fè? Li nan di magazen an, 10 kote 0 Catalogue, nan moso nan memwa rele x 0 a valè. Se konsa, remake yon koup la bagay yo ap mache sou. Menm si x ki se yon konsèy, sonje ki sòti nan yon semèn koup Anons sa pibliye depi ki ou ka toujou itilize kare etalaj-style notasyon a bracket. Paske sa a, se aktyèlman kout-men notasyon pou aritmetik a konsèy plis skre-ap chèche. kote nou ta fè yon bagay tankou sa a: Pran x la adrès, deplase 10 tach sou, Lè sa a, ale la kèlkeswa adrès la ki estoke nan ki kote. Men, franchman, sa a se jis atròs li epi pou yo jwenn alèz avèk li. Se konsa, mond lan tipikman itilize parantèz yo kare jis paske li nan anpil plis moun-zanmitay li. Men, se sa ki nan reyèlman ale sou anba kapo a; x se yon adrès, pa yon etalaj, se pou chak. Se konsa, sa a se estoke 0 nan kote 10 nan x. Poukisa se sa a move? Yeah? [Repons elèv, enkonpreansibl] Egzakteman. Nou sèlman afekte dis antye, men nou konsidere ki ant 0 lè pwogramasyon nan C, konsa ou gen aksè a 0 10 1 2 3 4 5 6 7 8 9, men se pa. Se konsa, swa pwogram nan ki pral fòt segman oswa li pa. Men nou pa vrèman konnen; sa a se sòt de yon konpòtman nondeterministic. Li reyèlman depann de si wi ou non nou jwenn chans. Si li sanble ke sistèm nan fonksyone pa lide si mwen itilize ki multiple siplemantè, menm si li pa te bay li nan m ', pwogram mwen pa ta ka aksidan. Li nan kri, li nan buggy, men ou pa ta ka wè ke sentòm, oswa ou ta ka wè l 'yon sèl fwa nan yon ti tan. Men, reyalite a se sa pinèz la se, an reyalite, la. Epitou, se vrèman pwoblèm si ou te ekri yon pwogram ki ou vle yo ki kòrèk, ke ou te vann pwogram nan ke gen moun ki ap itilize ke chak yon fwa nan yon pandan y ap kolizyon paske, nan kou, sa a se pa bon. An reyalite, si ou genyen yon telefòn android oswa iPhone yon epi ou download apps jou sa yo, si ou janm genyen yon app jis kite fimen, tout nan yon toudenkou li disparèt, sa se prèske toujou rezilta a nan kèk pwoblèm memwa ki gen rapò ak, kote pwogramè a vise leve, li dereferenced yon konsèy ke li pa ta dwe genyen, epi rezilta a nan yo oswa android se jis touye pwogram nan tout ansanm olye pase risk konpòtman endefini oswa kèk kalite konpwomi sekirite. Genyen yon bug lòt nan pwogram sa a san konte sa a youn. Ki lòt bagay mwen te vise moute nan pwogram sa a? Mwen pa te pratike sa mwen te anonse bon nouvèl. Yeah? [Repons elèv, enkonpreansibl] Bon. Mwen pa janm te libere memwa a. Se konsa, règ la nan gwo pous kounye a gen yo dwe nenpòt ki lè ou rele malok, ou dwe rele gratis lè w ap fè lè l sèvi avèk ki memwa. Koulye a, lè ta mwen vle libere sa a memwa? Pwobableman, an konsideran liy sa a premye te kòrèk, mwen ta vle fè li isit la. Paske mwen pa t 'kapab, pou egzanp, fè li desann isit la. Poukisa? Jis soti nan dimansyon. Se konsa, menm si n ap pale endikasyon, sa a se yon semèn 2 oubyen 3 pwoblèm, kote x se sèlman nan dimansyon andedan aparèy òtopedik yo Curly kote li te deklare. Se konsa, ou definitivman pa ka libere li a. Chans sèlman mwen nan libere li se apeprè apre liy 21. Sa a se yon pwogram san patipri senp; li te jistis fasil yon fwa ou kalite vlope tèt ou alantou sa pwogram lan ap fè, ki kote erè sa yo te ye. Ak menm si ou pa t 'wè li an premye, èspere ke li nan yon ti kras evidan kounye a ki sa yo erè yo trè fasil rezoud ak byen fasil fè fè yo. Men, lè yon pwogram se plis pase 12 liy long, li nan 50 liy long, 100 liy long, mache nan liy kòd ou a pa liy, panse atravè li lojikman, se posib, men se pa patikilyèman plezi bagay yo fè, toujou ap chèche pou pinèz, ak li la tou difisil yo fè, ak sa a, se poukisa yon zouti tankou Valgrind egziste. Kite m 'ale pi devan epi fè sa: kite m' louvri fenèt tèminal m 'yo, ak kite m 'pa sèlman kouri memwa, paske memwa sanble ap amann. Mwen ap resevwa chans. Ale nan ki multiple adisyonèl nan fen etalaj la pa sanble yo dwe twò Pwoblematik. Men, se pou m ', Alòske, fè yon chèk saniti, ki jis vle di yo tcheke si ou pa sa a se aktyèlman kòrèk. Se konsa, kite a fè valgrind-V - fuit radyasyon-tcheke = plen, ak Lè sa a, non an nan pwogram nan nan ka sa a se memwa, pa a.out. Se konsa, kite m 'ale pi devan epi fè sa. Frape Antre nan. Chè Bondye. Sa a se pwodiksyon li, e sa se ki sa mwen mansyone pi bonè. Men, si w aprann li atravè tout sou istwa san sans la isit la, pi fò nan sa a se jis pwodiksyon dyagnostik sa a, se pa sa ki enteresan. Ki sa ki je ou reyèlman vle yo dwe chèche pou se nenpòt mansyone nan erè oswa valab. Mo ki sijere pwoblèm. Ak tout bon, se pou yo wè sa k ap pase sa ki mal desann isit la. Mwen gen yon rezime de kèk sòt, "ap itilize nan sòti:. 40 bytes nan 1 blòk" Mwen pa reyèlman asire ki sa yon blòk se ankò, men 40 bytes aktyèlman santi l tankou mwen te ka konnen ki kote ki nan vini soti nan. 40 bytes. Pou ki sa yo 40 bytes ap itilize nan sòti? Ak plis espesyalman, si nou desann isit la, poukisa m 'definitivman pèdi 40 bytes? Yeah? [Repons elèv, enkonpreansibl] pafè. Yeah, egzakteman. Te gen dis nonm antye yo, epi chak moun sa yo se gwosè nan 4, oswa 32 Bits, Se konsa, mwen pèdi jisteman 40 bytes paske, jan ou pwopoze, mwen pa te rele gratis. Se youn ensèk, ak kounye a kite a gade desann yon ti kras pi lwen ak al gade nan pwochen sa a, "Envalid ekri nan gwosè 4." Kounye a ki sa sa a ye? Sa a se adrès eksprime sa ki notasyon baz, aparamman? Sa a se ekzadesimal, ak nenpòt ki lè ou wè yon nimewo kòmanse avèk 0x, sa vle di li ekzadesimal, ki nou te fè sa chemen tounen nan, mwen panse, seksyon pset 0 a nan kesyon, ki te jis fè yon egzèsis rechofman, konvèti desimal nan Egzagòn binè ak pou fè. Ekzadesimal, jis pa konvansyon imen, se anjeneral itilize reprezante endikasyon oswa, pi plis jeneralman, adrese. Se jis nan yon konvansyon, paske li nan yon ti kras pi fasil li, li nan yon ti kras plis kontra enfòmèl ant pase yon bagay tankou desimal, ak binè se initil pou pifò moun yo itilize. Se konsa, kounye a ki sa sa a vle di? Oke, li sanble gen nan yon ekri envalid nan gwosè 4 sou liy 21 nan memory.c. Se konsa, kite a tounen nan liy 21, ak tout bon, isit la se ke ekri valab. Se konsa, Valgrind pa pral konplètman kenbe men m ', di m' sa ranje a se, men li se detekte ke mwen fè yon ekri valab. Mwen manyen 4 bytes ke mwen pa ta dwe, ak aparamman sa a, se paske, menm jan ou vize deyò, mwen fè [10] olye pou yo [9] omaksimòm oswa [0] oswa yon bagay nan ant. Avèk Valgrind, reyalize nenpòt ki lè w ap kounye a ekri yon pwogram ki sèvi ak endikasyon epi li sèvi ak memwa, ak malok plis espesyalman, definitivman jwenn nan abitid la nan kouri sa a long men trè fasil kopye ak kole lòd nan Valgrind yo wè si gen nan kèk erè nan la. Epi li pral akablan chak fwa ou wè pwodiksyon an, men jis analizan nan vizyèlman tout nan pwodiksyon an ak wè si ou wè mansyone nan erè oswa avètisman oswa envalid oswa pèdi. Nenpòt mo ki son tankou ou vise moute kèk kote. Se konsa, reyalize ke se yon nouvo zouti nan bwat zouti ou a. Koulye a, nan Lendi, nou te gen yon pakèt antye nan jan vini isit la epi yo reprezante nosyon de yon lis lye. E nou prezante lis la lye kòm yon solisyon a sa pwoblèm? Yeah? [Repons elèv, enkonpreansibl] Bon. Matris pa ka gen memwa ajoute nan yo. Si ou asiyen yon etalaj de gwosè 10, ki nan tout sa ou jwenn. Ou ka rele yon fonksyon tankou realloc si ou initially rele malok, e ki kapab eseye grandi etalaj la si gen espas nan direksyon nan fen li ki pa gen yon lòt la lè l sèvi avèk, epi si gen nan pa, li pral jis jwenn ou yon moso pi gwo yon lòt kote. Men, Lè sa a, li pral kopye tout moun ki bytes nan etalaj nan nouvo. Sa a son tankou yon solisyon trè kòrèk. Poukisa se sa a dézagréabl? Mwen vle di li ap travay, moun te ka rezoud pwoblèm sa a. Poukisa nou bezwen rezoud li nan Lendi ak lye lis? Yeah? [Repons elèv, enkonpreansibl] Li kapab pran yon tan long. An reyalite, nenpòt ki lè w ap rele malok oswa realloc oswa calloc, ki se ankò yon lòt yon sèl, nenpòt moman ou, pwogram nan, ap pale ak sistèm nan fonksyone, ou gen tandans ralanti pwogram nan desann. Men, si ou ap fè sa yo kalite bagay sa yo nan pasan, w ap reyèlman ralentissement bagay sa yo desann. Ou pa ap ale nan avi sa a pou pi senp lan nan pwogram "mond alo" kalite, men nan pi gwo pwogram, mande sistèm nan fonksyone ankò e ankò pou memwa oswa bay li tounen ankò e ankò gen tandans pa yo dwe yon bon bagay. Plus, li jis sòt de entelektyèl - li nan yon fatra konplè sou tan. Poukisa asiyen pi plis ak plis memwa, risk kopye tout bagay nan etalaj nan nouvo, si ou gen yon altènatif ki pèmèt ou asiyen memwa sèlman otan ke ou aktyèlman bezwen? Se konsa, gen nan pluses ak minuses nan isit la. Youn nan pluses yo kounye a se ke nou gen dynamism. pa gen pwoblèm ki kote sègman yo nan memwa yo se ke yo gratis, Mwen ka jis sòt nan kreye sa yo ti kal pen pen via endikasyon fisèl antye mwen lye lis yo ansanm. Men, mwen peye omwen yon pri. Ki sa mwen gen bay yo nan pran lye lis? Yeah? [Repons elèv, enkonpreansibl] Bon. Ou bezwen plis memwa. Koulye a, mwen bezwen espas pou sa yo endikasyon, ak nan ka sa a super lis ki senp lye ke se sèlman ap eseye nan magazen nonm antye relatif yo, ki se 4 bytes, nou kenbe li di byen, yon konsèy se 4 bytes sa, koulye a mwen te literalman double kantite lajan an nan memwa mwen bezwen jis nan magazen lis sa a. Men ankò, sa a se yon konpwomi konstan nan syans konpitè ant tan ak espas ak devlopman, efò ak lòt resous. Ki sa ki nan yon lòt inconvénient nan lè l sèvi avèk yon lis lye? Yeah? [Repons elèv, enkonpreansibl] Bon. Pa tankou fasil jwenn aksè nan. Nou pap kapab kontinye ogmante semèn 0 prensip tankou separe ak konkeri. Ak plis espesyalman, binè rechèch. Paske menm si nou moun ka wè apeprè kote mitan an nan lis sa a se, òdinatè a sèlman konnen ke lis sa a lye kòmanse nan adrès rele an premye. Epi sa a, 0x123 oswa yon bagay tankou sa. Ak wout la sèlman pwogram nan kapab jwenn eleman nan mitan se aktyèlman rechèch lis la tout antye. E menm si sa, li literalman gen nan rechèch lis la tout antye paske menm yon fwa ou rive nan eleman nan mitan pa swiv endikasyon yo, ou, pwogram nan, pa gen okenn lide konbyen tan lis sa a se, potansyèlman, jiskaske ou frape nan fen li, epi ki jan ou konnen programatik ke ou se nan fen yon lis lye? Genyen nan yon konsèy espesyal nil, se konsa ankò, yon konvansyon. Olye de itilize sa a konsèy, nou definitivman pa vle li nan dwe gen kèk valè fatra lonje dwèt sou sèn yon kote; nou vle li nan dwe men desann, nil, pou ke nou gen sa a tèminal nan estrikti sa a done pou nou konnen ki kote li fini. Ki sa ki si nou vle manipile sa a? Nou te fè pi fò nan sa a vizyèlman, epi ak moun, men ki sa si nou vle fè yon ensèsyon? Se konsa, lis orijinal la te 9, 17, 20, 22, 29, 34. E si nou Lè sa a, te vle espas malok pou yon nimewo pou 55, yon ne pou li, ak Lè sa a, nou vle insert 55 nan lis la jis tankou nou te fè nan Lendi? Ki jan nou fè sa? Oke, Anita li moute soti deyò epi li esansyèlman te mache lis la. Li te kòmanse nan eleman a an premye, Lè sa a, pwochen an, pwochen an, pwochen an, pwochen an, pwochen an. Finalman frape bò gòch la tout wout la a desann e yo reyalize oh, sa a se nil. Se konsa, sa manipilasyon konsèy ki nesesè ki dwe fèt? Moun nan ki moun ki te sou fen a, nimewo 34, bezwen pla men gòch li leve soti vivan nan pwen nan 55, 55 nesesè bra gòch yo lonje dwèt desann yo dwe nouvo nil Terminator a. Fè. Trè fasil a insert 55 nan yon lis Ranje. Ak ki jan ta ka sa a gade? Kite m 'ale pi devan epi louvri moute kèk egzanp kòd isit la. Mwen pral louvri moute jdi, ak kite m 'louvri moute de dosye premye. Youn nan se list1.h, ak kite m 'jis raple ke sa a te moso nan kòd ke nou itilize yo reprezante yon ne. Yon ne gen tou de yon int rele n ak konsèy yon rele pwochen ki jis pwen bagay la pwochen nan lis la. Sa a se kounye a nan yon. Dosye h. Poukisa? Genyen nan sa a konvansyon, epi nou pa te pran avantaj de sa a yon kantite lajan gwo tèt nou, men moun ki te ekri fonksyon printf ak lòt te bay kòm yon kado nan mond lan tout moun ki fonksyon pa ekri yon dosye rele stdio.h. Lè sa a, gen nan string.h, ak Lè sa a, gen nan map.h, ak gen nan tout bagay sa yo h dosye ke ou ta ka gen pou wè oswa itilize nan tèm nan ekri pa lòt moun. Tipikman nan sa yo. Dosye h yo se bagay sèlman tankou typedefs oswa deklarasyon kalite koutim oswa deklarasyon nan konstan. Ou pa mete en fonksyon yo nan dosye header. Ou mete, olye de sa, jis prototip yo. Ou mete bagay sa yo ou vle pataje avèk mond lan sa yo bezwen yo nan lòd yo konpile kòd yo. Se konsa, jis jwenn nan sa a abitid, nou deside fè menm bagay la. Genyen nan pa anpil nan list1.h, men nou te mete yon bagay ki ta ka nan enterè moun nan mond lan ki ta vle itilize aplikasyon lye lis nou an. Koulye a, nan list1.c, mwen pa pwal ale travèse bagay sa a tout antye paske li nan yon ti jan long, pwogram sa a, men kite a kouri li reyèl byen vit nan èd memwa a. Kite m 'konpile list1, kite m' Lè sa a, kouri list1, e ki sa ou pral wè a Nou te fo yon senp pwogram ti kras isit la ki k ap pase pou pou pèmèt mwen ajoute epi retire nimewo nan yon lis. Se konsa, kite m 'ale pi devan epi tape 3 pou 3 a opsyon meni. Mwen vle insert nimewo a - kite a fè nimewo a an premye, ki te 9, e kounye a, mwen te di a lis la se kounye a 9. Kite m 'ale pi devan epi fè yon lòt ensèsyon, se konsa mwen frape opsyon meni 3. Ki nonb ki mwen vle insert? 17. Antre. Apre sa, mwen pral fè jis youn plis. Kite m 'insert nimewo a 22. Se konsa, nou gen kòmanse yo nan lis la lye ke nou te nan fòm glise yon ti moman de sa. Kijan sa a ensèsyon aktyèlman rive? Vreman vre, yo 22 se kounye a nan fen lis la. Se konsa, istwa a te di nou sou sèn nan Lendi e recapped jis kounye a dwe aktyèlman ap pase nan kòd. Se pou nou pran yon gade. Kite m 'desann nan sa a dosye. Nou pral enteprete sou kèk nan fonksyon yo, men nou pwal desann nan, di, fonksyon an insert. Ann gade pou wè ki jan nou ale sou yo mete yon ne nouvo nan lis sa a lye. Ki kote se lis la te deklare? Oke, kite la woulo liv tout wout la moute nan tèt la, ak avi ke se lis lye mwen esansyèlman te deklare kòm yon konsèy sèl sa a, se okòmansman nil. Se konsa, mwen sèvi ak yon varyab mondyal isit la, ki an jeneral nou te anonse bon nouvèl kont paske li fè kòd ou a yon sal ti kras yo kenbe, li nan sòt de parese anjeneral,, men li pa parese epi li pa mal epi li pa move si objektif sèl pwogram ou a nan lavi a se simule yon sèl lye lis la. Ki se ekzakteman ki sa nou ap fè. Se konsa, olye ke deklare sa a nan prensipal ak Lè sa a, dwe pase l 'bay chak fonksyon nou te ekri nan pwogram sa a, nou olye reyalize oh, kite la jis fè li mondyal , paske objektif an antye nan pwogram sa a se yo demontre yon sèl ak sèlman yon sèl lye lis la. Se konsa, ki santi l oke. Isit la yo se prototip mwen an, epi nou pa pral ale nan tout sa yo, men mwen te ekri yon fonksyon efase, yon fonksyon jwenn, yon fonksyon insert, ak yon fonksyon Traverse. Men, se pou a kounye a ale tounen desann nan fonksyon an insert ak wè kòman yon sèl sa a ap travay isit la. Mete se sou liy - isit la nou ale. Antre. Se konsa, li pa pran okenn agiman, paske nou ap ale nan mande andedan nan itilizatè sa a fonksyon pou yon nimewo pou la yo vle insert. Men, anvan, nou prepare ba yo kèk espas. Sa a se sòt de kopi ak keratin nan egzanp lan ak lòt. Nan ka sa a, nou te allocation yon int; tan sa a nou ap allocation yon ne. Mwen pa reyèlman sonje konbyen bytes yon ne se, men sa a amann. Sizof kapab konnen ki soti pou mwen. Epi poukisa mwen tcheke pou nil nan liy 120? Kisa ki ta kapab ale mal nan liy 119? Yeah? [Repons elèv, enkonpreansibl] Bon. Jis te kapab ka a ke mwen te mande pou memwa twòp oswa yon bagay nan sa ki mal ak sistèm nan fonksyone pa gen bytes ase yo ban m ', se konsa li siyal kòm anpil ki te retounen nil, ak si mwen pa tcheke pou ki epi mwen jis je fèmen kontinye nan sèvi ak adrès la tounen, li ka nil. Li ta ka gen kèk valè sèks, pa yon bon bagay sof si mwen - aktyèlman pa pral yon valè sèks. Li ta ka nil, se konsa mwen pa vle abize l ', li riske dereferencing li. Si sa ta rive, mwen jis retounen epi n ap pretann tankou mwen pa t 'jwenn tounen nenpòt memwa nan tout. Sinon, m'ap di itilizatè a ban m 'yon nonm a insert, mwen rele GetInt fin vye granmoun zanmi nou an, ak Lè sa a, sa a te sentaks nan nouvo nou prezante nan Lendi. 'Newptr-> n' vle di pran adrès la ke ou te bay nan malok ki reprezante multiple an premye nan yon objè ki ne nouvo, ak Lè sa a, ale nan jaden an te rele n. Yon ti kras kesyon Trivia: Sa a se ekivalan a sa ki liy nan kòd plis skre? Konbyen lòt bagay te kapab mwen te ekri sa a? Vle pran yon koud? [Repons elèv, enkonpreansibl] Bon. Lè l sèvi avèk n nan., Men li la pa byen kòm senp tankou sa a. Ki sa mwen premye bezwen? [Repons elèv, enkonpreansibl] Bon. Mwen bezwen fè * newptr.n. Se konsa, sa a ap di konsèy nouvo nan evidamman yon adrès. Poukisa? Paske li te tounen pa malok. Newptr a * li di: "ale la," ak Lè sa a, yon fwa w ap la, Lè sa a, ou ka itilize plis yo konnen yo. N a, men sa a jis sanble yon ti kras lèd, espesyalman si nou moun yo ale nan trase endikasyon ak flèch tout tan tout tan an; mond la genyen yon ofisyèl sa a sou notasyon flèch, ki fè sa ki egzakteman menm bagay la. Se konsa, ou sèlman itilize -> notasyon a lè bagay la sou bò gòch la se yon konsèy. Sinon, si li nan yon struct aktyèl, itilize n a.. Lè sa a, sa a: Poukisa mwen inisyalize newptr-> akote nil? Nou pa vle yon pendants men gòch koupe nan nan fen sèn nan. Nou vle li lonje dwèt tou dwat desann, ki vle di nan fen lis sa a te kapab potansyèlman kapab nan sa a ne, konsa nou pi bon asire w ke li se nil. Epi, an jeneral, inisyalizin varyab ou oswa manm done ou yo ak strukt a yon bagay se jis bon pratik. Jis kite fatra egziste yo e yo kontinye egziste jeneralman vin ou nan pwoblèm si ou bliye fè yon bagay pita sou. Isit la nan kèk ka. Sa a, ankò, se fonksyon an insert, ak bagay la premye fwa mwen tcheke pou se si varyab la rele an premye, varyab sa a mondyal se nil, sa vle di pa gen okenn lis lye. Nou pa t 'antre nenpòt ki nimewo, kidonk li a trivial insert nan nimewo sa a kounye a nan lis la, paske li jis ki dwe nan kòmansman lis la. Se konsa, sa a se te lè Anita te jis kanpe isit la pou kont li, samblan pa gen yon lòt te moute isit la sou sèn jiskaske nou resevwa lajan yon ne, Lè sa a, li te kapab leve men l 'la pou premye fwa, si te tout lòt moun moute vin sou sèn nan dèyè l 'nan Lendi. Koulye a isit la, sa a se yon chèk ti kras kote mwen te vle di si valè ne nan nouvo nan n se denmen, ki vle di ale nan struct la ki k ap pwente nan pa newptr, se konsa isit la nou ye a, ale la. Lè sa a, flèch la ap di jwenn jaden an kap vini an, ak Lè sa a, = a ap di sa ki mete valè a? Valè a sa ki te nan premye; sa ki valè te nan an premye? Premye te lonje dwèt nan nivo sa a ne, se konsa sa vle di sa a ta dwe kounye a nan pwen sa a nan ne. Nan lòt mo, sa ki sanble byen yon dezòd ridikil ak ekriti m 'yo, sa ki nan yon lide ki senp pou yo jis k ap deplase sa yo flèch alantou tradui nan kòd ak jis revètman yon sèl sa a. Estoke ki sa ki nan premye nan jaden nan pwochen ak Lè sa a, mete ajou sa ki premye aktyèlman se. Se pou nou ale pi devan epi vit-pou pi devan nan kèk nan sa a, epi gade sèlman nan nivo sa a ensèsyon ke pou kounye a. Sipoze mwen jwenn nan pwen kote mwen jwenn ke jaden an pwochen nan kèk ne se nil. Ak nan pwen sa a nan istwa a, yon detay ke mwen glossing sou se ke mwen te entwodwi yon lòt konsèy moute isit la nan, 142 liy konsèy predesesè. Esansyèlman, nan pwen sa a nan istwa a, yon fwa lis la vin long, Mwen kalite bezwen mache l 'ak de dwèt paske si m' ale twò lwen, sonje ki nan yon lis sèl-longè, ou pa kapab ale bak. Se konsa, ide sa a nan predptr se dwèt bò gòch mwen an, epi newptr - pa newptr. Yon lòt konsèy sa a, se isit la se dwèt lòt m 'yo, epi mwen jis kalite mache lis la. Se poutèt sa ki egziste. Men, kite a sèlman konsidere youn nan ka yo ki pi senp isit la. Si jaden pwochen ke konsèy la se nil, sa ki nan enplikasyon a ki lojik? Si w ap travèse lis sa a epi ou frape yon konsèy nil? Ou se nan fen lis la, epi konsa kòd la Lè sa a, tache yon sèl sa a adisyonèl eleman se sòt de entwisyon la ap pran ki ne ki gen pwochen konsèy se nil, kidonk sa a se kounye a nil, ak chanje li, menm si, yo dwe adrès ki nan ne nan nouvo. Se konsa, nou jis ap fè desen nan kòd flèch la ke nou te trase sou sèn yo si nou ogmante bò gòch yon moun. Epi ka-a ke mwen ap balanse men m 'nan pou kounye a, jis paske mwen panse ke li fasil jwenn pèdi lè nou fè l 'nan sa a sòt de anviwònman, se tcheke pou ensèsyon nan mitan lis la la. Men, jis intuitivement, ki sa ki bezwen rive si ou vle konnen ki kote kèk nonb ki dwe nan mitan an se ou gen nan mache li ki gen plis pase yon dwèt, plis pase yon konsèy, konnen ki kote li fè pati pa w tcheke se eleman ki Aktyèl yon sèl la, epi yon fwa ou jwenn kote sa a, Lè sa a, sa ou dwe fè sa a sòt de jwèt koki kote ou deplase bagèt yo ozalantou anpil atansyon. E ke repons lan, si ou ta renmen rezon nan sa a nan kay sou pwòp ou a, klou desann jis liy sa yo de nan kòd, men lòd la nan sa yo liy se super enpòtan. Paske si ou lage men yon moun ak ogmante yon lòt moun nan yo nan lòd la sa ki mal, ankò, ou te kapab fini orphaning lis la. Pou rezime plis Concept, ensèsyon an nan ke a se relativman senp. Ensèsyon an nan plas tèt la tou se relativman senp, men ou bezwen mete yon konsèy plis tan sa a peze nimewo 5 nan lis la isit la, ak Lè sa a, ensèsyon an nan mitan enplike nan efò menm plis, avèk anpil atansyon insert nimewo a 20 nan kote kòrèk li yo, ki se ant 17 ak 22. Se konsa, ou bezwen fè yon bagay tankou gen ne nouvo 20 pwen nan 22, ak lè sa a, konsèy ki ne a bezwen yo dwe mete ajou sot pase a? Li nan 17, nan aktyèlman insert li. Se konsa, ankò, m ap ranvwaye kòd la aktyèl pou sa aplikasyon an patikilye. Nan zye premye, li nan yon ti kras boulvèsan, men li vrèman jis yon riban enfini ki nan loupin, loupin, loupin, loupin, ak kraze le pli vit ke ou frape konsèy la nil, nan ki pwen ou ka fè ensèsyon an voulu. Sa a, lè sa a, se kòd reprezantan lye ensèsyon lis la. Sa yo ki te kalite yon anpil, epi li santi l tankou nou te rezoud yon pwoblèm, men nou te entwodwi yon antye youn ak lòt. Franchman, nou te depanse tout tan sa a sou gwo O ak Ω ak kouri tan, ap eseye rezoud pwoblèm pi vit, ak isit la nou yo ap pran yon gwo etap bak, li santi l. E ankò, si objektif la se nan magazen done, li santi l tankou Sentespri Grail a, kòm nou te di nan Lendi, ta reyèlman dwe nan magazen bagay sa yo imedyatman. An reyalite, sipoze ke nou te fè sa mete lis sou kote lye pou yon moman epi nou olye introduced nosyon de yon tab. Li kite yo jis panse a yon tab pou yon moman kòm yon etalaj. Sa a etalaj ak ka sa a isit la gen kèk 26 eleman, 0 a 25, ak ta kwè ke ou bezwen kèk ti moso nan depo pou non: Alice ak Bob ak Charlie ak renmen an. Epi ou bezwen kèk estrikti done nan magazen sa yo non. Oke, ou ta ka itilize yon bagay tankou yon lis lye epi ou te kapab mache a lis la yo mete Alice anvan Bob ak Charlie apre Bob ak pou fè. Epi, an reyalite, si ou vle wè kòd tankou sa kòm yon sou kote, konnen ke nan list2.h, nou fè egzakteman sa. Nou pa pwal ale travèse sa a kòd, men sa a se yon Variant nan premye egzanp lan ki entwodui yon sèl struct lòt nou te wè anvan elèv yo rele, ak Lè sa a, ki sa li aktyèlman estoke nan lis la lye se yon konsèy nan yon estrikti elèv olye ke yon senp nonb antye relatif ti kras, n. Se konsa, reyalize gen nan kòd la ki enplike nan strings reyèl, Men, si objektif la nan men li vrèman kounye a se nan adrès pwoblèm nan efikasite a, pa t 'vle bon pou li si n ap bay yon objè rele Alice, nou vle mete l 'nan kote a dwa nan yon estrikti done, li santi l tankou li ka d 'reyèlman bon jis mete Alice, ki gen non kòmanse ak A, nan kote a an premye. Ak Bob, ki gen non kòmanse ak B, nan kote, dezyèm lan. Avèk yon etalaj, oswa kite la kòmanse rele li yon tab, yon tab regle nan sa, nou ka fè egzakteman sa. Si nou ap bay yon non tankou Alice, yon kòd tankou Alice, kote ou te mete A-L-m-c-e? Nou bezwen yon hueristic. Nou bezwen yon fonksyon pran kèk D 'tankou Alice epi retounen yon repons, "Mete Alice nan sa a kote." Lè sa a fonksyon, bwat sa a nwa, yo pral rele yon fonksyon regle. Yon fonksyon regle se yon bagay ki pran yon D ', tankou "Alice", epi retounen ba ou, anjeneral, ki kote nimerik nan kèk estrikti done kote Alice ki dwe. Nan ka sa a, fonksyon regle nou ta dwe relativman senp. Fonksyon regle nou ta dwe di, si w ap bay "Alice", ki karaktè mwen ta dwe pran swen sou? Yon sèl la an premye. Se konsa, mwen gade nan [0], ak Lè sa a, mwen di si [0] karaktè se A, retounen nimewo a 0. Si li nan B, retounen 1. Si C li a, tounen 2, ak pou fè. Tout endèks 0, epi ki ta pèmèt m 'nan insert Alice ak Lè sa a, Bob ak Lè sa a, Charlie ak pou fè nan estrikti sa a done. Men, gen nan yon pwoblèm. E si Anita vini ansanm ankò? Ki kote nou mete Anita? Non li, tou, kòmanse ak lèt ​​la A, epi li santi l tankou nou te fè yon dezòd menm pi gwo nan pwoblèm sa a. Nou kounye a gen imedya ensèsyon, konstan ensèsyon tan, nan yon estrikti done olye ke vin pi mal ka-lineyè, men ki sa nou ka fè ak Anita nan ka sa a? Ki chwa nou genyen de, reyèlman? Yeah? [Repons elèv, enkonpreansibl] Oke, kidonk nou te ka gen yon lòt dimansyon. Sa a se bon. Se konsa, nou kapab bati bagay sa yo deyò nan 3D tankou nou te pale de vèbalman nan Lendi. Nou te ka ajoute yon lòt aksè isit la, men ta kwè ke pa gen okenn, mwen ap eseye kenbe sa a ki senp. Objektif la an antye isit la se yo gen imedya aksè konstan-tan, pou ki nan ajoute konpleksite twòp. Ki lòt opsyon ki lè w ap eseye insert Anita nan estrikti sa a done? Yeah? [Repons elèv, enkonpreansibl] Bon. Se konsa, nou te ka deplase tout lòt moun desann, tankou Charlie nudges desann Bob ak Alice, ak Lè sa a, nou mete Anita kote li te vrèman vle fè. Natirèlman, kounye a, gen nan yon efè segondè sa a. Estrikti sa a done se pwobableman itil pa paske nou vle insert moun yon fwa men se paske nou vle tcheke si yo ap gen pi ta si nou vle enprime soti tout nan non yo nan estrikti a done. Nou pwal fè yon bagay ak sa a done evantyèlman. Se konsa, kounye a nou te kalite vise sou Alice, ki moun ki nan pa gen pi long kote li te sipoze ye. Ni se Bob, ni se Charlie. Se konsa, petèt sa a se pa tankou yon bon lide. Men, tout bon, sa a se yon sèl opsyon. Nou te ka chanje tout moun desann, oswa èk, Anita te vin anreta nan jwèt la, poukisa pa nou jis mete Anita pa isit la, pa isit la, pa isit la, kite yo jis mete l 'yon ti kras pi ba nan lis la. Men, Lè sa a, pwoblèm sa a kòmanse transfere ankò. Ou ta ka kapab jwenn Alice imedyatman, ki baze sou premye non li. Ak Bob imedyatman, ak Charlie. Men, Lè sa a, ou gade pou Anita, epi ou wè la a, hmm, Alice se nan chemen an. Oke, kite m 'tcheke anba a Alice. Bob se pa Anita. Charlie se pa Anita. Oh, gen Anita. Men, si ou kontinye ke tren nan lojik tout wout la, sa ki nan pi move-ka tan an kouri pou jwenn pou yo mete Anita nan estrikti sa a done nouvo? Li nan O (n), dwa? Paske nan ka ki pi mal la, gen nan Alice, Bob, Charlie. . . tout wout la desann nan yon moun yo te rele "Y", se konsa gen nan sèlman yon sèl plas kite. Erezman, nou pa gen okenn yon sèl rele "Z", se konsa nou mete Anita nan pati anba a anpil. Nou pa t 'reyèlman te rezoud pwoblèm sa a. Se konsa, petèt nou bezwen prezante sa a dimansyon twazyèm. Epi li vire soti, si nou prezante sa a dimansyon twazyèm, nou pa kapab fè sa a parfe, men Grail Bondye a yo pral resevwa konstan-fwa ensèsyon ak parusyon dinamik pou ke nou pa oblije difisil-kòd yon etalaj de gwosè 26. Nou ka insert kòm yo anpil non jan nou vle, men kite a pran repo-5 minit nou yo isit la ak Lè sa a, fè sa byen. Tout dwa. Mwen mete istwa a moute bèl atifisyèlman gen pa chwazi Alice ak Lè sa a, Bob ak Lè sa a, Charlie ak Lè sa a, Anita, ki gen non te evidamman pral fè kolizyon avèk Alice. Men, kesyon an nou te fini nan Lendi ak se jis ki jan pwobab se li ke ou ta jwenn sa yo kalite kolizyon? Nan lòt mo, si nou kòmanse sèvi avèk estrikti sa a tabulaire, ki se vrèman jis yon etalaj, nan ka sa a nan 26 lokasyon, ki sa si entrées nou yo ap olye egzakteman menm jan distribye? Li pa atifisyèlman Alice ak Bob ak Charlie ak David ak pou fè lòd avèk lèt ​​alfabè, li nan egzakteman menm jan distribye plis pase A jiska Z. Petèt nou pral jis jwenn chans epi nou pa ap ale nan gen de A oswa de nan B ak pwobabilite wo anpil, men kòm yon moun pwente soti, si nou jeneralize pwoblèm sa a epi nou pa fè 0 a 25 men, di, 0 a 364 oswa 65, souvan ki kantite jou nan yon ane tipik, epi li te mande kesyon an, "Ki sa ki nan pwobabilite ki genyen pou de nan nou nan sal sa a gen menm jou fèt?" Mete li yon lòt fason sa a, sa ki nan pwobabilite ki genyen pou de nan nou gen yon non kòmanse avèk A? Sòt nan nan kesyon se menm bagay la, men espas sa a adrès, espas sa a rechèch, se pi gwo nan ka a nan dat nesans, paske nou gen anpil plis jou nan ane a pase lèt nan alfabè an. Ki sa ki nan pwobabilite ki genyen pou yon kolizyon? Bon, nou ka panse a sa a pa n ap kalkile konnen matematik nan fason opoze a. Ki sa ki nan pwobabilite ki genyen pou pa gen okenn kolizyon? Bon, sa a ekspresyon isit la di ke sa ki nan pwobabilite a si gen nan jis yon sèl moun nan sal sa a, ke yo gen yon anivèsè nesans inik? Li nan 100%. Paske si gen nan yon sèl moun nan sal la, li oswa anivèsè nesans li kapab gen nenpòt ki jou yo 365 soti nan ane a. Se konsa, 365/365 opsyon ki ban m 'yon valè de 1. Se konsa, pwobabilite a nan kesyon nan moman an se jis 1. Men, si gen nan yon moun ki dezyèm nan sal la, sa ki nan pwobabilite ki genyen pou anivèsè nesans yo se diferan? Genyen sèlman 364 jou sa posib, inyore ane kwasans, pou anivèsè nesans yo, yo pa fè kolizyon avèk moun ki lòt. Se konsa, 364/365. Si yon moun twazyèm vini nan, li nan 363/365, ak pou fè. Se konsa, nou kenbe miltipliye ansanm sa yo fraksyon, ki ap resevwa pi piti ak pi piti, konnen sa ki se pwobabilite ki genyen pou tout moun nan nou gen anivèsè nesans inik? Men, Lè sa a, nou ka, nan kou, jis pran ki repons ak baskile l 'nan epi fè 1 mwens nan tout sa, yon ekspresyon n ap pètèt jwenn si ou sonje do a nan liv matematik ou a, li sanble yon ti kras yon bagay tankou sa a, ki se pi plis fasil entèprete grafik. Lè sa a grafik isit la gen sou aks ki x kantite dat nesans, oswa kantite moun ki gen dat nesans, ak sou aks y pwobabilite ki genyen pou yon match. Ak sa ki sa a ap di se ke si ou gen, kite la di, menm, kite a chwazi yon bagay tankou 22 23,. Si gen nan 22 oswa 23 moun ki nan sal la, pwobabilite ki genyen pou de nan moun sa yo trè kèk yo ale nan gen menm jou fèt se aktyèlman segondè Super, combinatorially. 50 akwochaj% ki nan yon klas nan jis 22 moun, yon seminè-a, pratikman, 2 nan moun sa yo yo ale nan gen menm jou fèt. Paske gen nan anpil nan ki fason ou ka gen anivèsè nesans la menm. Menm pi mal, si w gade nan bò kote men dwat-ou nan tablo a, pa tan an ou gen yon klas avèk 58 elèv yo nan li, pwobabilite ki genyen pou 2 moun ki gen yon anivèsè nesans se super, gwo super, prèske 100%. Koulye a, sa a, se sòt de yon reyalite plezi sou lavi reyèl. Men, enplikasyon yo, koulye a, pou estrikti done epi estoke enfòmasyon vle di ke jis asepte ou gen yon bèl, pwòp, inifòm distribisyon done epi ou gen yon gwo etalaj ase anfòm yon pakèt moun sou bagay sa yo sa pa vle di w ap ale nan jwenn moun ki nan kote inik. W ap ale nan gen kolizyon. Se konsa, sa a nosyon nan achin, kòm sa yo rele, w ap pran yon D 'tankou "Alice" ak masaj li nan kèk fason ak Lè sa a, vin tounen yon repons tankou 0 oswa 1 oswa 2. Vin tounen kèk pwodiksyon de sa fonksyon an gwo malè tonbe sou sa a pwobabilite nan kolizyon. Se konsa, ki jan nou ka okipe sa yo kolizyon? Oke, sou ka a yon sèl, nou ka pran lide nan ki te sijere. Nou ka jis chanje tout moun desann, oswa petèt, yon ti kras pi plis tou senpleman, olye ke tout moun deplase lòt bagay, kite yo jis deplase Anita nan fon plas nan disponib. Se konsa, si Alice se nan 0, Bob se nan 1, Charlie se nan 2, nou pral jis mete Anita nan kote 3. Ak sa a se yon teknik nan estrikti done rele lineyè sonde. Lineyè paske w ap sèlman mache liy sa a, epi w ap sòt de sonde pou tach ki disponib nan estrikti nan done. Natirèlman, sa a devolu nan O (n). Si estrikti nan done se vrèman plen, gen nan 25 moun ki nan li deja, ak Lè sa a, Anita vini ansanm, li fini moute nan sa ki ta Z kote, ak sa a, se amann. Li ap toujou adapte, epi nou ka jwenn li pi ta. Men, sa a te kontrè nan objektif la nan eksè vitès sou bagay yo. Se konsa, sa si nou olye introduced sa a dimansyon twazyèm? Sa teknik se jeneralman yo rele separe Anchènman, oswa gen ti chenn. Ak sa ki yon tab regle kounye a se, estrikti sa a tabulaire, tab ou se jis yon etalaj de pwent. Men, sa ki sa yo endikasyon lonje dwèt sou se devine kisa? Yon lis lye. Se konsa, sa si nou pran pi bon nan tou de nan sa yo mond? Nou itilize ranje pou endèks yo premye nan estrikti nan done pou nou ka imedyatman ale nan [0] [1], [30] oswa pou fè, men se konsa ke nou gen kèk fleksibilite ak nou ka anfòm Anita ak Alice ak Adan ak nenpòt lòt Yon non, nou olye kite aks nan lòt grandi abitrèman. E nou finalman, kòm nan Lendi, gen sa kapasite espresif ak lis lye. Nou ka grandi yon estrikti done abitrèman. Altènativman, nou te ka jis fè yon gwo etalaj 2 dimansyon, men sa k ap pase yo dwe genyen yon sitiyasyon terib si youn nan ranje yo nan yon etalaj 2-dimansyon se pa gwo ase pou moun nan adisyonèl ki gen non k ap pase nan kòmanse ak A. Mande Bondye padon! Nou dwe aloue yon gwo estrikti 2-dimansyon jis paske gen nan pou anpil moun yo te rele A, espesyalman lè gen nan sa kèk moun yo te rele Z yon bagay. Li nan jis ale nan yon trè rar done estrikti. Se konsa, li pa pafè pa nenpòt vle di, men kounye a nou nan omwen gen kapasite pou imedyatman jwenn kote Alice oswa Anita ki dwe, omwen an tèm de aks vètikal la, ak Lè sa a, nou jis gen deside ki kote yo mete Anita oswa Alice nan lis sa a lye. Si nou pa pran swen sou Fouye bagay sa yo, ki jan byen vit nou ta ka insert Alice nan yon estrikti tankou sa a? Li lè konstan. Nou endèks nan [0], epi si gen pa gen yon an, Alice ale nan kòmansman ke lis lye. Men se pa sèlman yon kontra gwo. Paske si Anita Lè sa a, vini ansanm kèk nimewo nan etap pita, kote Anita apatni? Oke, [0]. Op. Alice se deja nan lis ki lye. Men, si nou pa pran swen sou klasman sa yo non, nou ka jis deplase Alice sou, insert Anita, men menm ki se tan konstan. Menm si gen nan Alice ak Adan ak tout bagay sa yo lòt Yon non, li pa vrèman déplacement yo fizikman. Poukisa? Paske nou jis te fè isit la ak lye lis, moun ki konnen yo te sa yo nœuds yo se de tout fason? Tout sa ou dwe fè se deplase ti kal pen yo pen. Deplase flèch yo otou; ou pa bezwen fizikman deplase nenpòt done alantou. Se konsa, nou ka insert Anita, nan ka sa a, imedyatman. Constant tan. Se konsa, nou gen Passage konstan-tan, ak konstan-fwa ensèsyon nan yon moun tankou Anita. Men, kalite oversimplifying mond lan. E si nou pita vle jwenn Alice? E si nou pita vle jwenn Alice? Konbyen etap se ke pral pran? [Repons elèv, enkonpreansibl] Egzakteman. Kantite moun ki anvan Alice nan lis la lye. Se konsa, li pa byen pafè, paske estrikti done nou an, ankò, gen sa a aksè vètikal ak Lè sa a, li gen sa yo bay lis lye pandye - aktyèlman, se pou yo pa rale l 'yon etalaj yon. Li te gen sa yo bay lis lye pandye koupe nan li ki sanble yon ti kras yon bagay tankou sa a. Men, pwoblèm lan se si Alice ak Adan ak tout bagay sa yo lòt non Yon fini pi plis ak plis lòt bò a, jwenn yon moun te kapab fini pran yon pakèt moun sou etap, bcause ou gen Traverse lis la lye, ki se yon operasyon lineyè. Se konsa, reyèlman, lè sa a, tan an ensèsyon finalman se O (n), kote n se nimewo a nan eleman nan lis la. Divize pa, kite la abitrèman rele li m, kote m se nimewo a nan lis lye ke nou gen nan sa a aks vètikal. Nan lòt mo, si nou vrèman asime yon distribisyon inifòm nan non, totalman ireyèl. Genyen nan evidamman plis nan kèk lèt ​​pase lòt moun. Men, si nou sipoze pou moman an yon distribisyon inifòm, epi nou te n moun total, ak m chenn total disponib nan nou, Lè sa a, longè a nan chak nan sa yo chenn jistis tou senpleman a pwal total la, n divize pa kantite a nan ti chenn. Se konsa, n / m. Men, isit la nan kote nou ka tout matematik entelijan. m se yon konstan, paske gen yon nimewo fiks nan sa yo. W ap ale nan deklare etalaj ou nan kòmansman an, ak nou pa rèsizin aks vètikal la. Pa definisyon, ki rete fiks yo. Li nan sèlman aks orizontal la, se konsa pale, ki nan chanje. Se konsa, teknikman, sa a se yon konstan. Se konsa, koulye a, ensèsyon tan an se bèl anpil O (n). Se konsa, ke pa santi tout sa ki pi bon. Men, sa ki nan sa a verite a isit la? Oke, tout tan sa a, pou de semèn, nou ve yo te di O (n ²). O (n), 2 x n ², - n, divize pa 2. . . me. Se jis ² n. Men, koulye a, nan pati sa a nan semès la, nou ka kòmanse pale osijè mond reyèl la ankò. Ak n / m se absoliman pi vit pase jis n pou kont li. Si ou gen yon non mil, epi ou kraze yo moute nan bokit miltip pou ke ou gen sèlman dis non nan chak nan sa yo chenn, absoliman chèche dis bagay a pwal pi vit pase yon mil bagay sa yo. Se konsa, youn nan ansanm sa yo, pwoblèm kap vini ki pral defi ou panse sou egzakteman ki menm si, yeah, asenptotik ak matematik, sa a se toujou jis lineyè, ki suk an jeneral lè w ap eseye jwenn bagay sa yo. An reyalite, li pral yo dwe pi vit pase sa paske nan sa divizè. Se konsa, gen nan ankò pral fè sa a komès-off ak sa a konfli ant teyori ak reyalite, ak youn nan bouton yo ap kòmanse kap vire nan pwen sa a nan semès la se pi plis nan reyalite a yon sèl jan nou sòt de prepare pou fen semster a, jan nou prezante mond lan nan pwogram entènèt, kote reyèlman, pèfòmans ki pral konte paske itilizatè ou yo ale nan kòmanse santi ak apresye desizyon konsepsyon pòv yo. Se konsa, kouman ou ale sou mete sou pye yon lye - yon tab regle ak 31 eleman? E nan egzanp ki anvan te abitrèman sou anivèsè. Si yon moun gen yon anivèsè nesans nan janvye 1 oswa Fevriye 1, nou pral mete yo nan sa a ki gen bokit. Si li la, 2 janvye, 2 Fevriye Mas 2, nou pral mete yo nan sa a ki gen bokit. Se poutèt sa li te 31. Ki jan ou fè deklare yon tab regle? Li kapab trè senp, tab ne * se non abitrè mwen an pou li, [31]. Sa a ba m '31 endikasyon nœuds, ak ki pèmèt m 'nan gen 31 endikasyon lye lis menm si sa yo chenn yo se okòmansman nil. Ki sa mwen vle mete si mwen vle nan magazen "Alice", "Bob", "Charlie"? Oke, nou bezwen vlope bagay sa yo nan yon estrikti paske nou bezwen Alice nan pwen Bob, nan pwen Charlie a, ak pou fè. Nou pa ka jis gen non yo pou kont yo, konsa mwen te kapab kreye yon estrikti nouvo rele ne isit la. Ki sa ki yon ne aktyèl? Ki sa ki se yon ne nan lis sa a nouvo lye? Premye bagay, ki rele mo, se pou non moun nan an. Longè, prezimableman, gen rapò ak longè a maksimòm de non yon moun nan, kèlkeswa sa ki se, 20, 30, 40 karaktè nan ka kwen fou, ak +1 se pou ki sa? Se jis nan pèsonaj la nil siplemantè, \ 0. Se konsa, sa a ne ap vlope "yon bagay" andedan nan tèt li, men tou li deklare yon konsèy rele pwochen pou nou ka chèn Alice Bob Charlie ak pou fè. Èske pral nil, men se pa nesesèman gen yo dwe. Nenpòt kesyon sou tab sa yo regle? Yeah? [Elèv mande kesyon, enkonpreansibl] Yon etalaj - bon kesyon. Poukisa se pawòl sa a Char nan yon etalaj olye ke sèlman * Char? Nan egzanp sa a yon ti jan abitrè, mwen pa t 'vle gen Resort malok pou chak nan non yo orijinal yo. Mwen te vle deklare yon kantite lajan maksimòm nan memwa pou fisèl la pou ke mwen te ka kopye nan estrikti nan Alice \ 0 epi yo pa gen fè fas ak malok ak gratis epi yo tankou la. Men, mwen ta ka fè ke si mwen te vle gen plis konsyan de itilize espas. Bon kesyon. Se konsa, kite a eseye jeneralizasyon lwen sa a soti nan epi konsantre rès tan ki rete nan jounen jodi a sou estrikti done plis jeneralman ak lòt pwoblèm ke nou ka rezoud lè l sèvi avèk eleman fondamantal yo menm menm si estrikti yo done tèt yo ta ka diferan nan Nap yo. Se konsa, li vire soti nan syans konpitè, pye bwa yo se trè komen. Epi ou ka panse a yon sòt pyebwa ki nan tankou yon pyebwa fanmi yo, kote gen nan kèk rasin, kèk matron oswa patriyach, granmè oswa granpapa oswa pi bonè tounen, anba ki se manman ak yon papa oswa frè ak sè divès oswa renmen an. Se konsa, yon estrikti pye bwa gen nœuds ak li gen timoun, anjeneral 0 oubyen plis timoun pou chak ne. Ak kèk nan jagon la ke ou wè nan foto sa a isit la se nenpòt nan timoun yo ti kras oswa ki grandkids sou bor yo ki pa gen okenn flèch pemanan nan yo, sa yo se fèy yo sa yo rele, epi nenpòt moun ki sou anndan an se yon ne anndan; ou ka rele li anyen ansanm liy sa yo. Men, estrikti sa a se trè komen. Yon sèl sa a nan yon ti kras abitrè. Nou gen yon sèl pitit sou bò gòch la, nou gen twa timoun sou bò dwat la, de timoun sou anba a kite. Se konsa, nou ka gen pye bwa diferan ki menm gwosè ak, men si nou kòmanse estandadize bagay sa yo, epi ou ta ka sonje sa a soti nan videyo Patrick a sou rechèch binè ki sòti nan yon kout anvan sou entènèt, binè rechèch pa bezwen aplike avèk yon etalaj oswa moso papye sou yon tablo. Sipoze ke ou te vle nan magazen nimewo ou a nan yon estrikti pi plis sofistike done. Ou te kapab kreye yon pye bwa tankou sa a. Ou te kapab gen yon ne te deklare nan C, ak ki ne ka gen omwen de eleman andedan nan li. Youn nan se nimewo a ou vle nan magazen, ak lòt la se - byen, nou bezwen yon sèl plis. Lòt la se timoun li yo. Se konsa, isit la nan yon lòt estrikti done. Tan sa a, se yon ne defini kòm estoke yon nimewo n ak Lè sa a, de pwent; gòch pitit ak pitit dwat. Apre sa, yo se pa abitrè. Ki sa ki nan enteresan sou pye bwa sa a? Ki sa ki nan modèl ki nan ki jan nou te mete sa a soti oswa ki jan Patrick mete l 'deyò nan videyo l'? Li nan kalite evidan ke gen nan kèk klasman ale sou isit la, men sa ki nan règ la senp? Yeah? [Repons elèv, enkonpreansibl] Pafè. Si ou gade nan sa a, ou wè nimewo yo ti sou bò gòch la, nimewo gwo sou bò gòch la, men sa a vre pou chak ne. Pou chak ne, pitit gòch li yo pi piti pase li, ak pitit dwa li pi gran pase li. Ki sa sa vle di kounye a se si mwen vle nan rechèch estrikti sa a done pou li a, di, nimewo a 44, Mwen dwe kòmanse nan rasin lan, paske menm jan ak tout moun sa yo estrikti pi konplèks done, koulye a, nou sèlman gen yon konsèy nan yon sèl bagay, nan konmansman an. Ak nan ka sa a, nan konmansman an se rasin lan. Li pa nan fen agoch, li nan rasin nan estrikti sa a. Se konsa, mwen wè isit la nan 55, ak mwen kap chèche 44. Ki direksyon Mwen vle ale? Oke, mwen vle pou yo ale nan bò gòch la, paske evidamman, sou bò dwat la a pwal twò gwo. Se konsa, remake isit la, ou se sòt de teori découper pye bwa a nan mwatye paske ou pa janm ap pral desann nan bò nan men dwat-ou. Se konsa, koulye a, mwen ale nan 55 a 33 an. Li nan twò piti nan yon nimewo. Mwen kap chèche 44, men kounye a pou mwen konnen si 44 se nan pye bwa sa a, mwen ka ale evidamman a dwat la. Se konsa, ankò, mwen koupe pye bwa a nan mwatye. Li nan bèl anpil ki idantik concept nan liv telefòn nan. Li nan ki idantik ak sa nou te fè ak papye yo sou tablo a, men li la yon estrikti pi plis sofistike ki pèmèt nou aktyèlman fè sa a separe ak konkeri nan konsepsyon nan algorithm a, ak an reyalite, Travelers yon estrikti tankou sa a - whoops. Travelers yon estrikti tankou sa a, kote li a sèlman "ale nan fason sa a oswa ale fason sa a," vle di tout sa ki kòd ki Bent lide ou nan premye lè mete ann aplikasyon li nan seksyon oswa mache atravè li nan kay la, pou rechèch binè, lè l sèvi avèk rkursyon oswa iterasyon, li nan yon doulè nan kou an. Jwenn eleman nan mitan, lè sa a fè awondi ou monte oswa desann. Genyen nan yon bote sa a paske nou kapab kounye a itilize rkursyon ankò, men pi plis propr. Vreman vre, si ou se nan nimewo ki 55 ak ou vle jwenn 44, ou ale rete nan ka sa a, Lè sa a, kisa w fè? Ou kouri egzak algorithm a menm. Ou tcheke valè a nan ne an, Lè sa a, ou ale agoch ​​oswa adwat. Lè sa a, ou tcheke valè a nan ne an, ale agoch ​​oswa adwat. Sa a se parfe ki ale ak rkursyon. Se konsa, menm si nan tan lontan an nou te fè kèk egzanp jistis abitrè ki enplike rkursyon ki pa t 'bezwen yo dwe repetitif, ak stuctures done, espesyalman pye bwa, li nan yon aplikasyon pou pafè nan ide sa a pou yo pran yon pwoblèm, ratresi l ', li Lè sa a, pou rezoud menm kalite, men ki pi piti pwogram nan,. Se konsa, gen nan yon lòt estrikti done ke nou ka prezante. Sa a se yon sèl ki fèt nan zye premye yo gade skre, men yon sèl sa a nan dwòl. Se konsa, sa a se yon estrikti done yo te rele yon trye, trye, ki se eritye de reaparisyon nan mo, ki pa pwononse re-TRY-Val, men se sa ki mond lan rele bagay sa yo. Ap eseye. T-r-m-e. Li se yon estrikti pyebwa ki nan kèk sòt, men chak nan nœuds yo nan yon trye parèt gen ki sa? Ak sa a se yon ti jan ki twonpe paske li nan kalite abreje. Men, li sanble chak ne sa a nan trye se aktyèlman yon etalaj. E menm si otè a nan dyagram sa a pa te montre li, nan ka sa a, sa a trye se yon estrikti done ki gen objektif nan lavi se nan magazen mo tankou A-L-m-c e-oswa B-o-b. Ak fason an nan ki sa a done magazen Alice ak Bob ak Charlie ak Anita ak pou fè se li itilize yon etalaj kote nan magazen Alice nan yon trye, nou kòmanse nan ne an rasin ki sanble yon etalaj, ak li a te ekri an notasyon steno. Otè ki manke abcdefg paske pa te gen okenn non ak sa. Yo sèlman te montre M ak P ak T, men nan ka sa a, kite yo deplase lwen Alice ak Bob ak Charlie nan kèk non ki isit la. Maxwell se aktyèlman nan dyagram sa a. Se konsa, kouman fè magazen an otè M-yon-x-w-e-L-l? Li te oswa li te kòmanse nan ne an rasin, l 'al jwenn [M], se konsa apeprè 13, ki kote 13th nan etalaj la. Lè sa a, apati de la, gen nan yon konsèy. Yon konsèy ki mennen ale nan yon lòt pozisyon. Soti nan gen otè a Catalogue nan ki etalaj nan pozisyon A, kòm repwezante gen sou bò gòch tèt, ak Lè sa a, li oswa li swiv ki konsèy nan yon lòt pozisyon, l 'al jwenn konsèy la nan kote X. Lè sa a, nan pwochen W la kote etalaj, E, L, L, ak pou fè, epi finalman, kite a aktyèlman eseye mete yon foto sa a. Ki sa yon gade ne tankou nan kòd? Yon ne nan yon trye gen yon etalaj de pwent nan plis nœuds. Men, gen la tou gen yo dwe kèk kalite valè Boolean, omwen nan sa a aplikasyon. Mwen rive rele li is_word. Poukisa? Paske lè w ap mete Maxwell, ou pa ap mete anyen nan estrikti sa a done. Ou pa ap ekri M. Ou pa ap ekri X. Tout sa ou ap fè se swiv endikasyon. Konsèy la ki reprezante M, Lè sa a, konsèy la ki reprezante A, Lè sa a, konsèy la ki reprezante X, Lè sa a, W, E, L, L, men ki sa ou bezwen fè nan fen an se sòt de ale, tcheke, mwen te rive nan sa a kote. Vwala se te yon mo ki fini isit la nan estrikti nan done. Se konsa, sa se yon trye vrèman ki te ranpli avèk ak otè a te chwazi yo reprezante sa yo terminuses ak triyang ti kras. Sa a jis vle di ke reyalite a nan triyang sa a isit la, sa a valè Boolean nan vre vle di si ou ale bak nan pyebwa a, sa vle di yon mo rele Maxwell se nan sa a. Men, pawòl foo a, pou egzanp, se pa nan pyebwa a, paske si mwen kòmanse nan ne an rasin moute isit la nan tèt, Gen nan pa gen konsèy f, pa gen okenn konsèy o, pa gen okenn konsèy o. Man se pa yon non yo nan sa a diksyonè. Men, pa kontra, Turing, T-u-r-m-n-g. Yon fwa ankò, mwen pa t 'sere t oswa u oswa r oswa mwen oswa n oswa g. Men, mwen te fè magazen nan estrikti sa a done yon valè de fason vre desann isit la nan sa a ne - nan pye bwa a pa mete sa a valè Boolean nan is_word vre. Se konsa, yon trye se kalite estrikti sa a meta trè enteresan, kote ou pa ap reyèlman estoke mo sa yo tèt yo pou sa a kalite diksyonè. Pou yo kapab klè, w ap sèlman estoke wi oswa non, gen yon mo ki fini isit la. Koulye a, sa ki nan enplikasyon la? Si ou gen 150,000 mo nan yon diksyonè ki w ap eseye nan magazen nan memwa lè l sèvi avèk yon bagay tankou yon lis lye, ou yo ale nan gen 150,000 nœuds nan lye lis ou an. Ak jwenn youn nan mo sa yo lòd avèk lèt ​​alfabè kapab pran O (n) tan. Lineyè tan. Men, nan ka a isit la nan yon trye, sa ki nan lè a kouri pou jwenn yon mo? Li vire soti bote a isit la se ke menm si w gen 149.999 mo ki deja nan sa a diksyonè, diksyonè kòm aplike ak estrikti sa a done, konbyen tan li pran pou chache oswa pou insert yon sèl plis moun nan ki, tankou Alice, Alice? Oke, li nan sèlman 5, petèt 6 etap pou pèsonaj la fin. Paske pwezans nan lòt non nan estrikti a pa jwenn nan fason a nan mete Alice. Anplis, jwenn Alice yon fwa gen 150,000 mo sa a nan diksyonè pa jwenn nan fason ou nan jwenn Alice nan tout, paske Alice se. . . . . isit la, paske mwen te jwenn yon valè Boolean. Men, si pa gen okenn Boolean vre, Lè sa a, Alice se pa nan estrikti sa a done nan mo yo. Nan lòt mo, tan an ap kouri pou jwenn bagay sa yo ak inséré bagay sa yo nan sa a nouvo done estrikti nan trye se O nan - li pa n. Paske pwezans nan 150,000 moun pa gen okenn efè sou Alice, li sanble. Se konsa, kite a rele l 'k, kote k se longè a maksimòm nan yon mo nan lang angle ki se tipikman pa gen okenn plis pase 20-yon bagay karaktè. Se konsa, k se yon konstan. Se konsa, Grail nan Sentespri nou yo sanble yo te jwenn kounye a se sa yo ki an yon trye, tan konstan pou mete anndan, pou rchèrch, pou reyur. Paske nimewo a de bagay sa yo deja nan estrikti a, ki fè yo pa menm fizikman la. Yon fwa ankò, yo ap jis sòt de tcheke koupe, wi oswa non, pa gen okenn enpak sou tan pwochen li kouri. Men, gen a te rive nan gen yon trape, otreman nou pa ta gaspiye tan tèlman sou tout bagay sa yo estrikti lòt done jis finalman jwenn nan yon sèl la sekrè ki nan dwòl. Se konsa, sa pri yo nou peye reyalize sa a Grandè isit la? Espas. Bagay sa a se masiv. Ak rezon ki fè otè a pa t 'prezante l isit la, avi ke tout nan bagay sa yo ki sanble ranje, li pa t 'trase rès pyebwa a, rès la nan trye a, paske yo ap jis pa ki gen rapò ak istwa a. Men, tout moun sa yo nœuds yo se super nan lajè, ak chak ne nan pye bwa a pran moute 26 oswa aktyèlman, ta ka 27 karaktè paske nan ka sa a mwen te ki gen ladan espas pou apostwòf la pou nou te kapab menm ki gen pawòl apostrophized. Nan ka sa a, sa yo se ranje nan lajè. Se konsa, menm si yo pa ap picutured, sa a pran moute yon kantite lajan masiv nan RAM. Ki ta ka amann, especilly nan kenkayri modèn, men sa a arbitraj la. Nou jwenn mwens tan pa depanse plis espas. Se konsa, kote sa a se tout prale? Oke, kite la fè - kite a wè isit la. Se pou nou fè yon so sa a nèg isit la. Kwè li oswa pa, kòm anpil plezi kòm C ki te pou kèk tan kounye a, n ap rive nan pwen an nan semès la kote li lè pou tranzisyon nan bagay ki pi modèn. Bagay sa yo sou yon nivo ki pi wo. E menm si pou koup la pwochen de semèn nou pral toujou kontinye bay plonje tèt nou nan mond lan nan pwent ak jesyon memwa jwenn ki konfò ak ki nou ka Lè sa a, bati sou li a, jwèt la fen se alafen prezante, iwonilman, pa lang sa a. Nou pral pase, tankou 10 minit ap pale de HTML. Tout HTML se se yon lang baliz, e ki sa yon lang baliz se se sa yo seri de parantèz louvri, epi parantèz ki fèmen di 'fè sa-a fonse' 'Fè sa-a italik' 'fè sa-a santre. Li pa tout sa ki entelektyèlman enteresan, men li la super itil. Epitou, se sètènman omniprezan jou sa yo. Men, sa ki nan pwisan sou mond lan nan HTML, ak pwogramasyon wèb plis jeneralman, ap konstwi bagay sa yo dinamik; ekri kòd nan lang tankou PHP oswa Piton oswa Ruby oswa Java oswa C #. Reyèlman, kèlkeswa lang ou nan chwa se, ak génération HTML dynamique. Génération yon bagay yo rele CSS dynamique. Kaskad style dra, ki se tou sou estetik. Se konsa, menm si, jodi a, si mwen ale nan kèk sit entènèt tankou Google.com a yo konnen yo, ak m 'ale nan wè, pwomotè, sous vi, ki petèt ou te fè anvan, men pral wè sous, bagay sa a pwobableman sanble trè skre. Men, sa a se kòd la siyalen ki aplike Google.com. Sou fen a devan. Ak aktyèlman tout sa a se an gonfle estetik bagay. Sa a se CSS moute isit la. Si m 'kenbe defile desann nou pral jwenn kèk bagay koulè-kode. Sa a se HTML. Kòd Google an sanble yon dezòd, men si mwen aktyèlman louvri moute yon fenèt diferan, nou ka wè kèk estrikti sa a. Si m 'ouvè sa a leve, avi isit la, li nan yon ti kras plis lizib. Nou pwal wè anvan lontan sa a tag, [mo] se yon tag, HTML, tèt, kò, div, script, zòn tèks, span, santre, DIV. Ak sa a se tou sòt de skre ap chèche-a zye premye, men tout nan dezòd sa a swiv modèl sèten, ak modèl repekte, pou ke yon fwa nou jwenn Basics yo desann, ou pral kapab ekri kòd tankou sa a ak Lè sa a, manipile kòd tankou sa a lè l sèvi avèk ankò yon lòt lang, rele JavaScript. Ak JavaScript se yon lang ki kouri andedan yon navigatè jodi a ke nou itilize sou Harvard pou kou yo, pou zouti nan fè makèt kou ki sèvi ak kat Google ba w yon pakèt antye nan dynamism, Facebook ba ou yo montre nouvèl enstantane, Twitter sèvi ak li nan montre w tweets imedyatman. Tout sa nou a pral kòmanse bay tèt nou plonje pous Men, sa yo rive,, nou bezwen konprann yon bagay sou ti entènèt la. Sa a clip isit la se jis yon minit long, e kite yo pran pou kounye a sa a se, an reyalite, kouman entènèt la travay kòm yon kol pou sa a sou ap vini yo. M 'ba ou "gèrye nan Net la." [♫ Ralanti koral mizik ♫] [Gason konteur] Li te vini ak yon mesaj. Ak yon pwotokòl tout pwòp li. [♫ rapid mizik elektwonik ♫] Li vin nan yon mond nan firewall fre, uncaring routeurs, ak danje lwen pi mal pase lanmò. Li nan vit. Li se fò. Li se tchp / IP, ak li te leve adrès ou. Gèrye nan Net la. [Malan] Next semèn, lè sa a. Entènèt la. Pwogramasyon entènèt. Sa a se CS50. [CS50.TV]