[Daqq ta mużika] DAVID J. Malan: Kull dritt. Dan huwa CS50. Dan huwa ħamsa ġimgħa kontinwa, u aħna għandhom xi aħbar tajba u xi aħbar ħażina. Allura aħbar tajba hija li CS50 tniedi dan Ġimgħa. Jekk inti tixtieq li jingħaqdu magħna, ras għall-URL tas-soltu hawn. Aħbarijiet anki aħjar, ebda lecture dan ġejjin it-tnejn l-13. Ftit inqas aħbarijiet aħjar, kwizz żero hija l-Erbgħa li jmiss. Aktar dettalji jistgħu jkunu tinstab fuq dan il-URL hawn. U matul il-jiem koppja li jmiss aħna ser tkun timla l-vojt fir-rigward l-kmamar li aħna se jkunu riżervati. Aħbarijiet Aħjar hija li hemm ser tkun reviżjoni kors wiesgħa sessjoni din ġejjin It-tnejn fil-għaxija. Soġġorn sintonizzat għall-tal-kors websajt għal post u dettalji. Taqsimiet, anki jekk huwa vaganzi, se jiltaqa 'wkoll ukoll. Best aħbarijiet, lecture il-ġimgħa d-dieħla. Allura dan huwa tradizzjoni aħna jkollhom, kif fis-sillabu. Just-- li għaddej biex tkun aqwa. Inti se tara affarijiet simili data strutturi ħin kostanti u tabelli hash u siġar u tipprova. U aħna ser nitkellmu dwar problemi birthday. A mazz sħiħ ta 'għalf jistenna il-ġimgħa li jmiss. OK. Xorta. Allura jfakkru li aħna kont qed jiffoka fuq din l-istampa ta 'x'hemm ġewwa tal-memorja tal-kompjuter tagħna. Allura memorja jew RAM huwa fejn programmi jeżistu waqt li int taħdem magħhom. Jekk inti double-click ikona jiddekorri xi program jew double-click ikona biex tiftaħ xi fajl, huwa mgħobbija minn hard tiegħek issuq jew stat solidu drive fis RAM, Random Access Memory, fejn jgħix sakemm il-qawwa imur off, l-għatu laptop tagħlaq, jew inti nieqaf-programm. Issa li l-memorja, ta ' li inti probabilment jkollhom 1 gigabyte dawn il-ġranet, 2 gigabytes, jew saħansitra ħafna aktar, huwa ġeneralment stabbiliti għal programm partikolari fil dan it-tip ta 'forma rettangolari mudell konċettwali li biha aħna għandna l-munzell fil-qiegħ u mazz ta 'għalf ieħor fil-quċċata. Il-ħaġa fil-quċċata ħafna Rajna fuq din l-istampa qabel imma qatt ma tkellem dwar huwa l-hekk imsejħa segment test. Segment Test huwa biss mod fancy ta 'tgħid l-żerijiet u dawk li compose program kkompilata tiegħek attwali. Allura meta inti double-click Microsoft Word fuq Mac tiegħek jew PC, jew meta inti tmexxi dot mmejla Mario fuq Linux kompjuter fid-tieqa terminal tiegħek, l-żerijiet u dawk li compose Word jew Mario huma maħżuna temporanjament fil RAM kompjuter tiegħek fl-hekk imsejħa segment test għal programm partikolari. Hawn taħt li tmur initialized u data uninitialized. Dan huwa Jittieħed simili varjabbli globali, li konna mhux użati ħafna, iżda fuq okkażjoni konna kellhom varjabbli globali jew kordi statikament definit li huwa diffiċli kliem bħal "bonjour" kodifikati li mhumiex jittieħdu mill-utent li huma hard-kodifikati fil-programm tiegħek. Issa, stabbiliti fil-qiegħ we jkollhom l-hekk imsejħa munzell. U l-munzell, s'issa, aħna kont qed jużaw għal liema tipi ta 'għanijiet? X'hemm-munzell ġew użati għall? Yeah? Udjenza: Funzjonijiet. DAVID J. Malan: Għal funzjonijiet? F'liema sens għall-funzjonijiet? UDJENZA: Meta inti sejħa funzjoni, il- l-argumenti huma kkopjati fuq il-munzell. DAVID J. Malan: Eżattament. Meta inti sejħa funzjoni, tagħha l-argumenti huma kkopjati fuq il-munzell. Allura xi X ta jew tal Y jew A jew B tal- li int tgħaddi ġol funzjoni huma temporanjament jitqiegħdu fuq l-hekk imsejħa munzell, biss bħal wieħed mill-Annenberg trejs sala dining, u wkoll affarijiet bħal varjabbli lokali. Jekk il-funzjoni foo tiegħek jew swap tiegħek funzjoni jkollhom varjabbli lokali, bħal temperatura, dawn iż-żewġ jispiċċaw fuq il-munzell. Issa, aħna mhux se jitkellmu wisq dwar minnhom, iżda dawn il-varjabbli ambjent fil-qiegħ rajna filwaqt li ilu meta I kien futzing fuq il-keyboard jum wieħed u bdejt aċċess affarijiet bħall ARGV 100 jew ARGV 1,000, biss elements-- ninsa l numbers-- iżda li ma kellhomx jiġu aċċessati mill me. Aħna bdew jaraw xi simboli funky fuq l-iskrin. Dawk kienu l-hekk imsejħa varjabbli ambjent bħal settings globali għall tiegħi programm jew għall-kompjuter tiegħi, ma mhux relatati mal-riċenti bug li aħna diskussi, Shellshock, li kien plaguing pjuttost ftit kompjuters. Issa fl-aħħarnett, fil-fokus tal-lum aħna ser finalment tkun fuq il-borġ. Dan huwa chunk ieħor ta 'memorja. U fundamentalment dan kollu memorja huwa l-istess għalf. Hu l-istess ħardwer. Aħna biss tip ta ' trattament clusters differenti ta 'bytes għal skopijiet differenti. Il borġ huwa wkoll se jkun fejn varjabbli u l-memorja li inti titlob mis-sistema operattiva huwa maħżun temporanjament. Iżda hemm tip ta 'problema hawnhekk, bħala l-istampa jimplika. Aħna tip ta 'żewġ vapuri li waslu biex jikkonfliġġu. Għaliex kif inti tuża aktar u aktar tal-munzell, u kif naraw llum onward, kif tuża aktar u aktar ta 'l- borġ, żgur affarijiet ħżiena jista 'jiġri. U fil-fatt, nistgħu jinduċu li intenzjonalment jew mhux intenzjonalment. Allura l-cliffhanger aħħar iż-żmien kien dan il-programm, li ma sservi ebda funzjonali skop ieħor ħlief li juri kif inti bħala bad Guy tista 'attwalment tieħu vantaġġ ta 'bugs fil-programm ta' xi ħadd u tieħu f'idejha l-programm jew saħansitra sistema tal-kompjuter sħiħ jew server. Hekk biss li t'għajn fil-qosor, inti avviż li prinċipali fil-qiegħ jieħu fil-kmand linja argumenti, kif kull ARGV. U għandu sejħa għal funzjoni f, essenzjalment funzjoni nameless msejħa f, u huwa tgħaddi fis-ARGV [1]. Allura x'ikun kelma t-tipi utent f'mill fil-pront wara isem dan il-programm, u mbagħad din il-funzjoni arbitrarja up top, f, jieħu fil string, char AKA *, kif aħna ħadthom bdiet tiddiskuti, u hija biss jitlob li "bar." Iżda nistgħu sejħa hija xejn. U allura jiddikjara, ġewwa ta f, firxa ta 'karattri imsejħa c-- 12-il karattru bħal dawn. Issa, mill-istorja I kien javżak mument ilu, fejn fil-memorja huwa ċ, jew huma dawk 12 Chars ser jispiċċaw? Just biex tkun ċara. Yeah? UDJENZA: Fuq il-munzell. DAVID J. Malan: Fuq il-munzell. Allura c hija varjabbli lokali. Aħna qed jitolbu għal 12 Chars jew 12 bytes. Dawk huma ser jispiċċaw fuq l-hekk imsejħa munzell. Issa finalment hija din il-funzjoni l-oħra li attwalment pretty utli, imma aħna ħadthom mhux użati verament dan lilna nfusna, strncopy. Dan ifisser kopja string, iżda biss N ittri, n-karattri. Allura n-karattri se jkunu kkupjati mill bar fis c. U kemm? It-tul ta 'bar. Allura fi kliem ieħor, li linja waħda, strncopy, se kopja effettiv bar fil sa c. Issa, just biex tip ta jantiċipaw l-morali ta 'din l-istorja, dak li huwa potenzjalment problematiku hawn? Anki jekk aħna qed iċċekkjar t-tul ta 'bar u li jgħaddi fis strncopy, dak li hu imsaren tiegħek tghidlek huwa xorta maqsuma dwar dan il-programm? Yeah? UDJENZA: Ma tinkludix spazju għall-karattru null. DAVID J. Malan: Ma tinkludix spazju għall-karattru null. Potenzjalment, b'differenza prattika tal-passat aħna ma anki jkollhom daqshekk plus 1 sa jakkomodaw dan il-karattru null. Iżda huwa saħansitra agħar minn dik. X'iktar huma aħna naqset milli tagħmel? Yeah? UDJENZA: [inaudible] DAVID J. Malan: Perfect. Imxejna hard-coded 12 pretty arbitrarju. Dan mhuwiex tant l- problema, iżda l-fatt li aħna mhux qed anki iċċekkjar jekk it-tul ta 'bar huwa inqas minn 12, f'liema każ li għaddej biex tkun sikur biex tqiegħed lilha fil-memorja imsejħa c li konna allokati. Tabilħaqq, jekk bar huwa simili 20 karattru twal, din il-funzjoni tidher li ikkupjar 20 karattri mill bar fis c, u b'hekk tieħu mill-inqas 8 bytes li ma għandu jkun. Dik hija l-implikazzjoni hawnhekk. Għalhekk fil-qosor programm, imkisser. Mhux tali big deal. Forsi ikollok tort segmentazzjoni. Imxejna kollha kellhom bugs fil-programmi. Aħna lkoll jista 'jkollhom bugs fi programmi dritt issa. Imma x'inhu l-implikazzjoni? Well, Heres verżjoni żżomjati-in ta ' li stampa ta 'memorja tal-kompjuter tiegħi. Dan huwa l-qiegħ tal munzell tiegħi. U fil-fatt, fil-qiegħ ħafna huwa x'hemm imsejħa munzell ta 'rutina ġenitur, mod fancy ta 'tgħid li l-prinċipali. Allura li kull min jissejjaħ il-funzjoni f li aħna qed jitkellem dwar. Allura dan huwa l-qiegħ tal-munzell. Indirizz Ritorn hija xi ħaġa ġdida. Huwa dejjem kien hemm, dejjem kienet f'dak istampa. Aħna biss qatt ma imsejħa attenzjoni għalih. Minħabba jirriżulta l-mod c jaħdem huwa li meta funzjoni waħda sejħiet ieħor, mhux biss tagħmel l-argumenti li funzjoni nikseb imbuttat fuq il-munzell, mhux biss tagħmel lokali l-funzjoni tal- varjabbli tikseb imbuttat fuq il-munzell, xi ħaġa imsejħa indirizz ta 'ritorn wkoll gets tpoġġi fuq il-munzell. Speċifikament, jekk sejħiet ewlenin foo, tat ewlenin indirizz stess fil-memorja, xi ħaġa ox, effettivament gets tpoġġi fuq il-munzell b'tali mod li meta f isir eżekuzzjoni tagħha jaf fejn jaqbżu lura fit-test segment sabiex ikomplu eżekuzzjoni. Mela jekk aħna qed hawn kunċettwalment, fil prinċipali, allura f gets imsejħa. Kif ma f taf min għall-kontroll idejn lura? Ukoll, dan ftit Breadcrumb aħmar hawn, imsejjaħ il-indirizz ta 'ritorn, hija biss kontrolli, dak li huwa dak l-indirizz ta 'ritorn? Oh, let me jaqbżu lura lill prinċipali hawnhekk. U li ftit ta oversimplification, minħabba li l-żerijiet u dawk għall prinċipali huma teknikament up hawn fil-segment tech. Imma dak li l-idea. f biss irid ikun jaf liema li fejn il-kontroll finalment tmur lura. Iżda l-mod kompjuters ilhom stabbiliti affarijiet bħall varjabbli lokali u argumenti huwa bħal dan. Allura fil-quċċata ta 'din l-istampa fil- blu huwa l-qafas munzell għall f, sabiex kollha tal-memorja li f speċifikament qed tuża. Allura għaldaqstant, avviż li bar huwa fil din l-istampa. Bar kien argument tagħha. U aħna qal li l-argumenti li funzjonijiet tikseb imbuttat fuq il-munzell. U c, naturalment, huwa wkoll fil din l-istampa. U biss għal skopijiet ta 'notazzjoni, avviż fil-kantuniera tan-naħa tax-xellug huwa dak li jkun c bracket 0 u imbagħad ftit isfel lejn il-lemin huwa ċ bracket 11. Allura fi kliem ieħor, tista 'timmaġina li hemm grilja ta 'bytes hemm, l-ewwel minnhom hija top xellug, qiegħ tagħha hija l-aħħar waħda minn dawk 12 bytes. Imma issa jippruvaw fast quddiem. X'inhu dwar li jiġri jekk aħna jgħaddu fil-bar string li l-itwal minn c? U aħna mhux qed iċċekkjar jekk huwa tabilħaqq aktar minn 12. Liema parti ta 'din l-istampa se nikseb miktub fuq ieħor minn bytes 0, 1, 2, 3, dot dot dot, 11, u mbagħad bad, 12, 13 sa 19? X'hemm jiġri hawn, jekk inti jiddeduċu mill-ordni li ċ bracket 0 qegħda fil-quċċata u c bracket 11 huwa tip ta isfel lejn il-lemin? Yeah? UDJENZA: Well, li għaddej li jissostitwixxu l-bar char *. DAVID J. Malan: Yeah, jidher qisu int ser jissostitwixxu * bar char. U agħar, jekk inti tibgħat fil verament twila string, inti tista 'anki jissostitwixxu liema? L-indirizz ta 'ritorn. Li għal darb'oħra, huwa biss bħal Breadcrumb li tgħid il-programm fejn li jmorru lura meta f isir qed jissejjaħ. Allura dak guys ħżiena tipikament do hija jekk dawn jiltaqgħu ma 'programm li dawn qed kurjuż jekk huwa sfruttat, Buggy b'tali mod li hu jew hi jista 'jieħu vantaġġ ta 'dan bug, ġeneralment dawn ma jsibux dan id-dritt l-ewwel darba. Huma biss tibda tibgħat, per eżempju, kordi każwali fis-program tiegħek, jekk fuq il-keyboard, jew franchement huma probabbilment jikteb programm ftit li biss awtomatikament jiġġeneraw kordi, u jibdew banging fuq il program tiegħek billi jibgħat fil-lottijiet ta 'inputs differenti fil tulijiet differenti. Hekk kif crashes programm tiegħek, li l-ħaġa aqwa. Għaliex dan ikun ifisser li hu jew hi skopra dak li huwa probabbilment tabilħaqq bug. U allura dawn jistgħu jiksbu aktar għaqlija u tibda tiffoka b'mod aktar restrittiv dwar kif jisfruttaw dak bug. B'mod partikolari, dak li hu jew hi jista ' tagħmel hu li tibgħat, fl-aħjar każ, bonjour. No big deal. Huwa string li l-qasir biżżejjed. Imma x'jiġri jekk hu jew hi jibgħat, u aħna ser tiġġeneralizza bħala, attakk code-- hekk żerijiet u dawk li jagħmlu l-affarijiet bħal rm-rf, li tneħħi kollox mill-hard drive jew jibgħat spam jew b'xi mod tattakka l-magna? Mela jekk kull wieħed minn dawn ittri A biss tirrappreżenta, kunċettwalment, attakk, attakk, attakk, attakk, xi kodiċi bad li xi ħadd ieħor kiteb, imma jekk dik il-persuna huwa intelliġenti biżżejjed li mhux biss jinkludi kollox għal dawk it-RFS RM, iżda wkoll jkollhom aħħar ftit bytes tiegħu jew tagħha jkun hemm numru li jikkorrispondi fl-indirizz ta 'dmirijietu jew kodiċi attakk tagħha stess li hu jew hi mgħoddija fil biss billi jipprovdulha fil-pront, inti tista 'effettivament trick l-kompjuter fis jinnota meta f isir eżekuzzjoni, oh, wasal iż-żmien għalija biex tiżdied lura għall-indirizz tar-ritorn aħmar. Iżda għaliex hu jew hi għandu b'xi mod jikkoinċidu dak l-indirizz ta 'ritorn bin-numru tagħhom stess, u dawn qed intelliġenti biżżejjed li konfigurati li numru li jirreferu, kif inti tara fil-quċċata super rokna tax-xellug hemm, l-indirizz attwali fil-tal-kompjuter memorja ta 'xi wħud mill-kodiċi attakk tagħhom, Guy ħażina tista trick l-kompjuter fis eżekuzzjoni kodiċi tiegħu jew tagħha stess. U dan il-kodiċi, għal darb'oħra, jistgħu jiġu xejn. Huwa ġeneralment sejjaħ kodiċi qoxra, li huwa biss mod ta 'tgħid li mhuwiex ġeneralment xi ħaġa sempliċi bħala rm-rf. Huwa fil-fatt xi ħaġa simili Bash, jew programm attwali li tagħtih jew kontroll programmatiku tagħha biex tesegwixxi kull ħaġa oħra li jkunu jridu. Allura fil-qosor, dan kollu joħroġ mill-fatt sempliċi li dan bug involut ma iċċekkjar il-konfini ta 'firxa tiegħek. U minħabba l-mod kompjuters xogħol huwa li dawn jużaw il-munzell minn b'mod effettiv, kunċettwalment, qiegħ fuq up, iżda mbagħad l-elementi timbotta fuq il-munzell jikber top down, dan huwa oerhört problematiku. Issa, hemm modi biex jaħdmu madwar dan. U franchement, hemm lingwi li biex jaħdmu madwar dan. Java huwa immuni, per eżempju, biex din il-kwistjoni partikolari. Minħabba li ma jagħtuk pointers. Huma ma jagħtuk indirizzi memorja diretti. Allura ma dan il-poter li għandna tmissx xejn fil-memorja Irridu taqa, ċertament, ir-riskju kbir. Allura żżomm għajnejk out. Jekk, franchement, fix-xhur jew snin li ġejjin, ghaċ inti taqra dwar xi wħud isfruttament ta 'programm jew ta' server, jekk inti qatt tara ħjiel ta 'xi ħaġa bħal attakk overflow buffer, jew overflow Munzell huwa tip ieħor ta 'attakk, simili fl-ispirtu, kemm tispira l-tal-websajt isem, jekk tkun taf, dan kollu jitkellem dwar biss overflowing-daqs ta 'xi karattru array jew xi array b'mod aktar ġenerali. Kwalunkwe mistoqsijiet, allura, fuq dan? Tippruvax din id-dar. Kull dritt. Allura malloc s'issa kien ġdida tagħna ħabib f'dak nistgħu jallokaw memorja li aħna ma neċessarjament jaf fil javvanzaw li aħna rridu hekk aħna ma jkollhomx għall-kodiċi hard fis tagħna numri programm bħal 12. Ladarba l-utent jgħidilna kemm data hu jew hi trid input, nistgħu malloc li l-memorja ħafna. Allura malloc jirriżulta, għall- estent konna ilhom jużawha, espliċitament aħħar darba, u mbagħad inti guys ilhom jużawha għall getstring unknowingly għall diversi ġimgħat, kollha tal-memorja malloc ta ġej mill-borġ hekk imsejħa. U dan huwa għaliex getstring, per eżempju, jistgħu jallokaw memorja dinamiku mingħajr ma jkunu jafu dak li int ser tip bil-quddiem, inti idejn lura pointer għal dak memorja, u li l-memorja għadu tiegħek li żżomm, anki wara getstring prospetti. Minħabba irtirar wara kollox li l- munzell huwa kontinwament jitla 'u' l isfel, up u 'l isfel. U hekk kif din tmur isfel, li tfisser kull memorja din il-funzjoni użat għandu m'għandux jintuża minn ħaddieħor. Huwa valuri taż-żibel issa. Iżda l-borġ huwa up here. U x'hemm sbieħ dwar malloc hija li meta malloc jalloka memorja up here, mhuwiex impatt, għall- parti l-kbira, mill-munzell. U hekk kull funzjoni tista 'aċċess memorja li ġie malloc'd, anke permezz ta 'funzjoni bħal getstring, anki wara hu ritornat. Issa, il-maqlub ta 'malloc huwa b'xejn. U fil-fatt, ir-regola inti bżonn biex tibda tadotta huwa kwalunkwe, kwalunkwe, kwalunkwe ħin li inti tuża malloc inti trid yourself tuża ħielsa, eventwalment, fuq dik l-istess pointer. Dan il-ħin aħna ġew miktub Buggy, kodiċi buggy, għal ħafna raġunijiet. Iżda wieħed minnhom kien tuża l-librerija CS50, li nnifisha hija deliberatament Buggy, tnixxijiet memorja. Kwalunkwe ħin li inti stajt imsejħa getstring matul l-aħħar ftit ġimgħat aħna qed tistaqsi l operattiva sistema, Linux, għall-memorja. U inti qatt ma ladarba jingħata lura. U dan mhux, fil- prattika, ħaġa tajba. U Valgrind, wieħed mill- għodod introdotti fl Pset 4, hija kollha dwar tgħin inti issa jsibu bugs bħal dik. Iżda grazzi għat-tobba Pset 4 inti m'għandekx bżonn li tuża l-librerija CS50 jew getstring. Allura xi bugs relatati mal-memorja huma finalment se tkun tiegħek stess. Allura malloc hija aktar minn sempliċiment konvenjenti għal dan il-għan. Nistgħu attwalment issa ssolvi problemi fundamentalment differenti, u fundamentalment isolvu problemi aktar effettivament bħala kull wegħda ġimgħa żero tal. S'issa dan huwa l-sexiest struttura tad-data aħna kellna. U mill-istruttura tad-data I jfissirx biss mod ta 'conceptualizing memorja b'mod li jmur lil hinn minn sempliċiment tgħid, dan huwa int, dan huwa char. Nistgħu tibda affarijiet cluster flimkien. Allura firxa dehru qishom dan. U dak kien importanti f'madwar array huwa li jagħtik back-to-back biċċiet ta ' memorja, li kull wieħed minnhom se tkun tal-istess tip, int, int, int, int, jew char, char, char, char. Iżda hemm ftit negattivi. Dan per eżempju, huwa firxa ta 'daqs sitta. Ejja ngħidu li inti timla dan array b'sitt numri u mbagħad, għal xi raġuni, utent tiegħek trid li tagħti inti-seba 'numru. Fejn do inti tpoġġi dan? X'hemm-soluzzjoni jekk għandek ħolqot firxa fuq il-munzell, per eżempju, biss bil-ġimgħa tnejn notazzjoni li aħna introdotti, ta 'parentesi kwadri ma' numru ġewwa? Well, inti ħadthom ltqajna sitt numri fil dawn il-kaxxi. Liema jkun instincts tiegħek tkun? Fejn kieku inti tixtieq li tqiegħed lilha? UDJENZA: [inaudible] DAVID J. Malan: Jiddispjacini? UDJENZA: Poġġi fuq it-tmiem. DAVID J. Malan: Poġġi fuq it-tmiem. Hekk biss fuq il-lemin, barra ta 'din il-kaxxa. Liema ikun sbieħ, iżda jinstabx inti ma tistax tagħmel dan. Għaliex jekk inti ħadthom ma talabx għal dan blokki ta 'memorja, jista 'jkun minn koinċidenza li din qed tintuża minn xi varjabbli oħra għal kollox. Think lura ġimgħa jew hekk meta aħna stabbiliti out ismijiet Zamyla u Davin u Gabe tal fil-memorja. Huma kienu litteralment lura lura lura. Allura aħna ma tistax neċessarjament fiduċja li kwalunkwe ta minn hawn hija disponibbli għall nagħmel użu. Allura x'iktar jista inti tagħmel? Well, ladarba jirrealizzaw inti bżonn ta 'firxa ta' daqs seba, inti tista 'biss toħloq firxa ta 'daqs seba mbagħad jużaw a għal loop jew loop waqt, kopja hija fil-firxa ġdida, u mbagħad b'xi mod biss jeħles ta ' dan array jew biss tieqaf tuża din. Iżda li mhux partikolarment effiċjenti. Fil-qosor, arrays ma let inti dinamikament resize. Allura fuq naħa waħda ikollok aċċess bl-addoċċ, li huwa aqwa. Minħabba li tikri us do affarijiet bħall firda u conquer, tfittxija binarja, li kollha konna tkellem dwar fuq l-iskrin hawn. Imma inti żebgħa lilek innifsek fis-kantuniera. Hekk kif inti hit l-aħħar tal-firxa tiegħek, inti għandek tagħmel ħafna operazzjoni għaljin jew jikteb mazz sħiħ ta 'kodiċi li issa tittratta dik il-problema. Allura dak li jekk minflok kellna xi ħaġa imsejħa lista, jew lista marbuta b'mod partikolari? X'jiġri jekk minflok li rettangoli lura lura biex back, għandna rettangoli li jħallu ftit daqsxejn ta 'kamra wiggle bejniethom? U anki jekk stajt miġbuda dan stampa jew adattati din l-istampa minn wieħed mit-testi hawn biex tkun lura lejn lura lura ħafna ordnat, fir-realtà, wieħed minn dawk rettangoli jista 'jkun up hawn fil-memorja. Wieħed minnhom jista 'jkun up here. Wieħed minnhom jista 'jkun up here, hawn fuq, u ibqa 'sejjer hekk. Imma dak jekk aħna ġibdet, f'dan il-każ, vleġeġ li b'xi mod link dawn rettangoli flimkien? Tabilħaqq, Rajna tekniku Inkarnazzjoni ta vleġġa. Dak li aħna użati fl-aħħar jiem li, taħt il-barnuża, huwa rappreżentattiv ta vleġġa? A pointer, id-dritt? Allura dak li jekk, minflok biss ħażna tal-numri, bħall 9, 17, 22, 26, 34, dak jekk aħna maħżuna ma biss numru iżda pointer li jmiss għal kull tali numru? Allura li ferm simili inti Thread labra permezz mazz sħiħ ta 'drapp, affarijiet b'xi irbit flimkien, bl-istess mod jista aħna ma pointers, kif incarnated mill vleġeġ hawn, tip ta 'nisġa flimkien dawn rettangoli individwali billi effettivament jużaw pointer li jmiss għal kull numru li punti li xi numru li jmiss, li punti li, imbagħad, xi numru li jmiss? Allura fi kliem ieħor, liema jekk aħna fil-fatt riedu biex jimplimentaw xi ħaġa bħal din? Well sfortunatament, dawn rettangoli, inqas l-wieħed ma 9, 17, 22, u ibqa 'sejjer hekk, dawn m'għadhomx pjazez sbieħ ma 'numri singoli. Il-qiegħ, rettangolu hawn taħt 9, per eżempju, jirrappreżenta dak għandu tkun pointer, 32 bits. Issa, jien ma għadhom konxji ta 'kwalunkwe tip ta' dejta fis-C li jagħtik mhux biss int iżda pointer kollox. Allura x'inhu l-soluzzjoni jekk irridu jivvintaw tweġiba tagħna stess għal dan? Yeah? UDJENZA: [inaudible] DAVID J. Malan: X'hemm li? UDJENZA: Struttura ġdida. DAVID J. Malan: Yeah, hekk għaliex ma noħolqu struttura ġdida, jew Ċ, Struct? Imxejna structs rajna qabel, jekk fil-qosor, fejn aħna ttrattati bi struttura student bħal dan, li kellhom l-isem u dar. Fil Pset 3 tbegħid inti użati kollu mazz ta 'GRect structs-- u GOvals li Stanford maħluqa biex informazzjoni cluster flimkien. Allura dak li jekk nieħdu din l-istess idea ta ' l-keywords "typedef" u "Struct," u mbagħad xi għalf speċifiku student, u jevolvu dan fil-segwenti: typedef Struct node-- u node huwa biss xjenza tal-kompjuter ġeneriku ħafna tul għal xi ħaġa fi struttura tad-data, kontenitur fi struttura tad-data. A node nitlob huwa se jkollu l n int, totalment sempliċi, u mbagħad ftit aktar cryptically, din it-tieni linja, node Struct * jmiss. Iżda f'termini tekniċi inqas, dak li huwa dan it-tieni linja tal-kodiċi ġewwa l-braces kaboċċi? Yeah? UDJENZA: [inaudible] DAVID J. Malan: A pointer li node ieħor. Allura ċertament, sintattiku ftit cryptic. Imma jekk inti taqra dan litteralment, li jmiss huwa l-isem ta 'varjabbli. X'inhu tip ta 'dejta tagħha? Huwa verbose ftit dan iż-żmien, imma hija ta node Struct tip *. Kwalunkwe ħin Rajna star xi ħaġa, li ifisser huwa pointer għal dak it-tip data. Allura li jmiss hija apparentement a pointer li node Struct. Issa, dak li huwa node Struct? Well, Avviż inti tara dawk istess kliem fil kantuniera. U fil-fatt, inti wkoll tara l-kelma "Node" stabbiliti hawn fil-qiegħ tax-xellug. U dan huwa attwalment biss konvenjenza. Avviż li fid-definizzjoni student tagħna hemm il-kelma "student" darba biss. U dan għaliex student oġġett ma kienx awto-referenzjali. M'hemm xejn ġewwa ta 'student li jeħtieġ għall-punt li student ieħor, persay. Dan ikun tip ta ' stramb fid-dinja reali. Iżda ma 'node fil marbuta lista, nagħmlu rridu node li jkun referenzjali għal oġġett simili. U hekk avviż-bidla hawnhekk mhix biss x'hemm ġewwa l-braces kaboċċi. Iżda aħna żid il-kelma "node" fil-quċċata kif ukoll żżidu mal-qiegħ minflok "student." U dan huwa biss f'dettalji, b'tali mod li, għal darb'oħra, l-istruttura tad-data tiegħek jista 'jkun awto-referenzjali, b'tali mod li node jista 'jiġbed l node oħra bħal din. Allura dak li huwa dan finalment ser ifisser għalina? Ukoll, wieħed, dan il-għalf ġewwa huwa l-kontenut ta 'node tagħna. Din ħaġa up here, kantuniera, huwa biss hekk li, għal darb'oħra, nistgħu jirreferu għall nfusna. U allura l-għalf aktar imbiegħda, anki jekk node huwa terminu ġdid, forsi, huwa għadu l- istess bħal student u liema kien taħt il-barnuża fl SPL. Allura jekk aħna issa riedet tibda implimentazzjoni ta 'din il-lista marbuta, kif jista aħna tittraduċi xi ħaġa bħal din għall-kodiċi? Well, ejja biss tara Eżempju ta 'programm li effettivament juża lista marbuta. Fost kodiċi tad-distribuzzjoni tal-lum huwa programm imsejjaħ Lista Zero. U jekk I run dan I ħolqot super GUI sempliċi, grafiċi User Interface, iżda huwa verament ftit printf. U issa stajt mogħtija lili nnifsi menu ftit options-- Ħassar, Daħħal, Search, u travers. U Nieqaf. Dawn huma operazzjonijiet biss komuni fuq struttura tad-data magħrufa bħala lista link. Issa, Ħassar se jitħassru ċertu numru mil-lista. Daħħal għaddej biex iżżid numru għal-lista. Fittex ser tħares għall numru fil-lista. U travers huwa biss mod fancy ta 'tgħid, walk permezz tal-lista, ipprintjaha, imma thats it. Tbiddilx fi kwalunkwe mod. Mela ejja jippruvaw dan. Ejja imorru quddiem u tat-tip 2. U mbagħad jien ser daħħal in-numru, jgħidu 9. Ikteb. U issa program tiegħi huwa biss pprogrammata biex jgħidu, lista issa huwa 9. Issa, jekk I imorru quddiem u do Daħħal għal darb'oħra, let me imorru quddiem u zoom out u tip 17. Issa lista tiegħi huwa 9, allura 17. Jekk I do daħħal mill-ġdid, ejja skip wieħed. Minflok 22, kif kull l-istampa konna ġew tħares lejn hawnhekk, let me jaqbżu l quddiem u daħħal 26 li jmiss. So jien ser tip 26. Il-lista huwa kif I jistennew. Imma issa, biss biex tara jekk dan il-kodiċi se tkun flessibbli, let me issa tip 22, li mill-inqas kunċettwalment, jekk aħna qed Żamma dan magħżula, li huwa tabilħaqq se tkun gowl ieħor dritt issa, għandhom imorru fl bejn 17 u 26. So I hit Ikteb. Tabilħaqq, li x-xogħlijiet. U hekk issa let me daħħal il- aħħar, kull l-istampa, 34. Kull dritt. Allura għal issa let me jistipulaw li Ħassar u travers u Search tagħmel, fil-fatt, ix-xogħol. Fil-fatt, jekk I do run Fittex, ejja tfittxija għall-numru 22, Ikteb. Hija sabet 22. Allura dan huwa dak li din programm Lista Zero ma. Imma dak li huwa attwalment għaddejjin fuq li jimplimenta dan? Well, l-ewwel I jista 'jkollhom, u tabilħaqq I do jkollhom, fajl imsejjaħ list0.h. U x'imkien fil hemm huwa dan linja, typedef, node Struct, imbagħad I jkollhom ċingi kaboċċi tiegħi, int n, u imbagħad struct-- dak li kien id-definizzjoni? Node Struct jmiss. Allura għandna bżonn l-istilla. Issa teknikament we jsibu rwieħhom l-vizzju tat-tfassil hawnhekk. Inti tista 'tara kotba u referenzi online do hemmhekk. Huwa funzjonalment ekwivalenti. Fil-fatt, dan huwa xi ftit aktar tipiku. Imma I ser tkun konsistenti ma 'dak għamilna aħħar darba u jagħmlu dan. U mbagħad fl-aħħar, jien ser jagħmlu dan. Allura fil-fajl tal-header x'imkien, fil list0.h llum hija din id-definizzjoni Struct, u forsi xi għalf ieħor. Sadanittant list0c hemm ser ikunu ftit affarijiet. Iżda aħna qed tmur biex ftit jibdew u mhux jintemm dan. List0.h huwa fajl irrid biex jinkludu fil-fajl C tiegħi. U mbagħad f'xi punt jien ser ikollhom int, prinċipali, null. U mbagħad jien ser għandhom xi to do hawnhekk. Jien ukoll se jkollhom prototip, bħal null, tfittxija, int, n, l-iskop tagħhom fil-ħajja huwa tiftix għal element. U mbagħad stabbiliti hawn nitlob fl kodiċi tal-lum, null, tfittxija, int, n, ebda virgola iżda braces kaboċċi miftuħa. U issa I trid tfittex b'xi mod għal element f'din il-lista. Iżda aħna ma jkollhomx biżżejjed informazzjoni fuq l-iskrin għadu. I jkollhom ma attwalment irrappreżentata lista nnifisha. Allura mod wieħed nistgħu jimplimentaw lista marbuta fi programm huwa I tip ta 'tixtieq li tagħmel xi ħaġa bħall tiddikjara marbuta lista up here. Għas-sempliċità, jien ser jagħmlu dan globali, anke jekk b'mod ġenerali aħna m'għandekx tagħmel dan wisq. Iżda se tissimplifika dan l-eżempju. So I jridu jiddikjaraw lista marbuta up here. Issa, kif jista 'nagħmel dan? Hawn l-istampa ta 'lista marbuta. U jien ma verament taf fil-mument kif Jien ser tmur dwar jirrappreżentaw tant affarijiet b'sett wieħed biss varjabbli fil-memorja. Imma naħseb lura mument. Dan il-ħin aħna kellna kordi, li aħna mbagħad żvelat li jkun arrays ta ' karattri, li aħna mbagħad żvelat li jkun biss pointer l-ewwel karattru fil-firxa ta 'karattri thats null terminat. Allura billi li l-loġika, u ma 'dan stampa tip ta 'jinżera ħsibijiet tiegħek, dak li għandna attwalment bżonn jiktbu tagħna kodiċi jirrappreżentaw lista marbuta? Kemm ta 'din l-informazzjoni għandna bżonn biex jaqbdu fil-kodiċi C, would you say? Yeah? UDJENZA: Għandna bżonn pointer għal node. DAVID J. Malan: A pointer għal node. B'mod partikolari, liema node kieku tiegħek instincts jkun li żżomm pointer li? UDJENZA: L-ewwel node. DAVID J. Malan: Yeah, probabbilment biss l-ewwel. U avviż, l-ewwel node hija forma differenti. Huwa biss nofs id-daqs ta 'l-Struct, għaliex dan huwa tabilħaqq biss pointer. Allura dak li inti tista 'tabilħaqq tagħmel huwa jiddikjara lista marbuta ma jkunu ta 'node tip *. U ejja biss sejħa hija l-ewwel u initialize lill null. Allura null, għal darb'oħra, huwa li ġejjin fis-istampa hawn. Mhux biss huwa null użat bħala bħal speċjali valur tar-ritorn għal affarijiet simili getstring u malloc, null hija wkoll l-żero pointer, in-nuqqas ta 'pointer, jekk inti se. Dan ifisser biss xejn għadu hawn. Issa l-ewwel, I jistgħu stajt sejjaħ dan xejn. I setgħet hija imsejħa "lista" jew kwalunkwe numru ta 'affarijiet oħra. Imma jien ssejjaħ dan "l-ewwel" b'tali mod li linji it up ma din l-istampa. Hekk biss bħal string jistax jiġi rappreżentat bl-indirizz ta 'l-ewwel byte tagħha, sabiex tista 'lista marbuta. U aħna ser tara informazzjoni oħra istrutturi jkunu rappreżentati b'sett wieħed biss pointer, vleġġa 32-bit, tipponta fl-ewwel node fl-istruttura. Imma issa ejja tantiċipa problema. Jekk jien biss ftakar fil-programm tiegħi l-indirizz ta 'l-ewwel node, l-ewwel rettangolu f'din l-istruttura tad-data, liema kellhom jkun aħjar il-każ dwar il- implimentazzjoni tal-bqija tal-lista tiegħi? X'hemm dettall ewlieni li għaddej biex tiżgura li dan attwalment xogħlijiet? U billi "attwalment xogħlijiet" I mean, ħafna bħal string, tikri us go mill-ewwel karattru fl-isem Davin għall-tieni, għat-tielet, għall- raba, sa l-aħħar ħafna, kif nafu meta nkunu fl-aħħar ta 'lista marbuta li tidher bħal dan? Meta huwa null. U stajt rappreżentati dan it-tip ta 'bħala bħal-jista inġinier elettriku, mal-ert ftit simbolu, ta 'tip. Iżda dan ifisser biss null f'dan il-każ. Tista 'tiġbed kull numru ta 'modi, iżda dan awtur ġara biex jużaw dan is-simbolu hawn. Sakemm aħna qed stringing kollha ta 'dawn lymph flimkien, biss ftakar fejn l-ewwel waħda hija, sakemm kif aħna tpoġġi simbolu speċjali fil l-ħafna aħħar node fil-lista, u aħna ser tuża null, minħabba li l dak li għandna disponibbli lilna, din il-lista hija kompluta. U anki jekk I biss jagħtuk pointer biex l-ewwel element, inti, il-programmer, tista 'ċertament aċċess għall-bqija ta' dan. Imma ejja ejja imħuħ tiegħek wander ftit, jekk dawn mhux qed diġà pjuttost wandered-- x'hemm se jkun il-ħin qed taħdem ta ' konstatazzjoni xejn f'din il-lista? Indanna dan, huwa O kbir ta 'n, li mhix ħażina, fl-ekwità. Iżda huwa lineari. Aħna taw up dak karatteristika ta arrays billi jersqu aktar lejn din l-istampa ta 'dinamikament minsuġa flimkien jew lymph marbuta? Imxejna rrinunzjaw aċċess bl-addoċċ. Firxa huwa sbieħ għaliex kollox matematikament huwa lura lura lura biex lura. Anke jekk din l-istampa jistenna pretty, u anki għalkemm jidher qisu dawn lymph huma nicely spazjati, fir-realtà dawn jistgħu jkunu kullimkien. OX1, Ox50, Ox123, Ox99, dawn lymph jista 'jkun kullimkien. Minħabba malloc ma jalloka memorja mill-munzell, iżda kullimkien fid-borġ. Inti ma neċessarjament jaf li huwa se tkun lura lura lura. U hekk din l-istampa fil-proċess tat-realtà mhux se jkun pjuttost dan pretty. Allura li għaddej biex jieħu ftit tal- jaħdmu biex jimplimentaw din il-funzjoni. Mela ejja jimplimentaw search issa. U aħna ser tara tip ta ' mod għaqlija ta 'kif isir dan. Mela jekk I am a funzjoni ta 'tfittxija u Jien mogħti varjabbli, numru sħiħ n biex tfittex, I bżonn tkun taf l- sintassi ġdida għall tfittex ġewwa ta 'struttura li l- indikat, biex isibu n. Mela ejja tagħmel dan. Allura l-ewwel jien se jmorru quddiem u tiddikjara node *. U jien ser sejħa hija pointer, biss billi konvenzjoni. U jien ser initialize lill-ewwel. U issa I tista 'tagħmel dan f'numru ta 'modi. Imma jien ser tieħu approċċ komuni. Filwaqt pointer mhuwiex ugwali għal null, u li l-sintassi validu. U dan ifisser biss tagħmel dan li ġej, hekk Sakemm int ma tipponta lejn xejn. What do I trid tagħmel? Jekk pointer dot n, let me terga 'lura għal dan, equals-- ugwali liema? What am I valur tfittex? Il n attwali li kienet għaddiet. Allura hawnhekk fattur ieħor ta 'C u ħafna lingwi. Anki jekk l-istruttura imsejħa node għandha n-valur, totalment leġittimu li jkollu wkoll argument lokali jew varjabbli imsejħa n. Minħabba anke aħna, ma ' għajnejn tal-bniedem, jista 'jiddistingwi li dan huwa n preżumibbilment differenti minn dan n. Minħabba li l-sintassi hija differenti. You ħadthom ltqajna dot u pointer, billi dan wieħed m'għandu l-ebda ħaġa bħal din. Allura dan huwa OK. C'est OK li jsejħu lilhom l-istess affarijiet. Jekk I do inti ssib dan, jien tmur trid tagħmel xi ħaġa bħal jħabbar li sibna n. U aħna ser tħalli li bħala jikkummenta jew kodiċi pseudocode. Else, u hawnhekk l- parti interessanti, liema do I trid tagħmel jekk il-node attwali ma fihx n li I care about? Kif nista jinkiseb dan li ġej? Jekk finger tiegħi fil- mument huwa PTR, u huwa tipponta fi kwalunkwe ewwel hija li tipponta lejn, kif nista jimxu finger tiegħi għall-node li jmiss fil-kodiċi? Ukoll, x'inhu l-Breadcrumb aħna qed sejra ssegwi f'dan il-każ? UDJENZA: [inaudible]. DAVID J. Malan: Yeah, hekk li jmiss. Mela jekk jien jmorru lura għall tiegħi kodiċi hawn, tabilħaqq, jien se jmorru 'l quddiem u jgħidu pointer, li huwa biss variable-- temporanju huwa isem stramb, PTR, iżda huwa biss bħal temp-- Jien ser jistabbilixxu pointer ugwali għal dak kollu is-- pointer u għal darb'oħra, dan se jkun ftit Buggy għal dot moment-- jmiss. Fi kliem ieħor, jien ser tieħu tiegħi finger thats tipponta lejn dan node hawn u jien ser ngħid, inti taf dak, tagħti ħarsa lejn il-qasam li jmiss u jimxu saba biex x'ikun huwa tipponta lejn. U dan se irrepeti, irrepeti, irrepeti. Imma meta ma finger tiegħi tieqaf tagħmel xejn affattu? Hekk kif liema linja ta 'kicks kodifika fil? UDJENZA: [inaudible] DAVID J. Malan: Jekk il-punt waqt pointer mhuwiex ugwali għal nulla. F'xi punt finger tal tiegħi ser tkun tipponta lejn null u jien ser tirrealizza dak l-aħħar ta 'din il-lista. Issa, dan huwa ftit jimteddu abjad għas-sempliċità. Jirriżulta li anke jekk aħna biss tgħallmu dan dot notazzjoni għal strutturi, pointer mhix Struct. PTR huwa dak? Just biex tkun aktar nitpicky. Huwa pointer għal node. Mhuwiex node innifsu. Jekk I kellu l-ebda stilla hawn, pointer absolutely-- huwa node. Dan huwa bħal wieħed ġimgħa dikjarazzjoni ta 'varjabbli, anke jekk il-kelma "node" huwa ġdid. Imma hekk kif aħna jintroduċu star, huwa issa pointer għal node. U sfortunatament inti ma tistax tuża l-dot notazzjoni għal pointer. Int għandek tuża l-vleġġa notazzjoni, li, impressjonanti, hija l-ewwel darba xi biċċa tal sintassi jistenna intuwittivi. Dan litteralment qisu vleġġa. U hekk li l-ħaġa tajba. U 'l isfel hawn litteralment Dehra vleġġa. So I think dak l-la-- I ma think jien over-tikkommetti here-- I jaħsbu li huwa l-aħħar biċċa ġdida tal sintassi aħna qed tmur biex tara. U Thankfully, huwa tabilħaqq ftit aktar intuwittivi. Issa, għal dawk minnkom li jista 'jippreferi l-mod qodma, inti xorta tista 'tuża l-dot notazzjoni. Imma kif kull nhar it-Tnejn konverżazzjoni, aħna l-ewwel bżonn li jmorru hemm, tmur f'dak jindirizzaw, u mbagħad ikollhom aċċess l-qasam. Allura dan huwa wkoll korrett. U franchement, dan huwa ftit aktar pedantic. Inti litteralment qal, dereference l-pointer u jmorru hemm. Imbagħad grab .n, il-qasam imsejħa n. Iżda franchement, ebda wieħed irid tip jew taqra dan. U hekk id-dinja ivvintat in-notazzjoni vleġġa, li hija ekwivalenti, identika, huwa biss zokkor sintattika. Allura mod fancy ta 'tgħid dan jistenna aħjar, jew jistenna aktar sempliċi. Allura issa jien ser tagħmel ħaġa waħda oħra. Jien se ngħid "break" darba stajt sabuha so I ma jżommux tfittex għaliha. Iżda dan huwa l-GIST ta 'funzjoni ta' tfittxija. Iżda huwa ħafna aktar faċli, fil- aħħar, ma jimxu permezz tal-kodiċi. Dan huwa tabilħaqq l-implimentazzjoni formali ta 'tfittxija fil-kodiċi ta' distribuzzjoni tal-lum. I DARE ngħid li daħħal mhix partikolarment gost li jimxu permezz viżwalment, u lanqas ma hija tħassar, anke għalkemm fl-aħħar tal-ġurnata huma jsarrafx biss fl pjuttost heuristics sempliċi. Mela ejja tagħmel dan. Jekk inti ser Humer lili hawn, jien ma ġġib mazz ta 'blalen istress. I miġjuba mazz ta 'numri. U nistgħu tikseb biss ftit voluntiera biex jirrappreżentaw 9, 17, 20, 22, 29, u 34? Allura essenzjalment kulħadd li hawnhekk illum. Dan kien wieħed, tnejn, tlieta, erba ', ħames, sitt persuni. U stajt ġew mitluba biex go-- tara, l-ebda wieħed fil-dahar tqajjem idejn tagħhom. OK, wieħed, tnejn, tlieta, erba ', five-- let me tagħbija balance-- sitta. OK, inti sitta come fuq up. Aħna ser bżonn nies oħra. Aħna miġjuba blalen stress żejjed. U jekk inti tista ', għall- ftit mument, linja yourselves up biss bħal din l-istampa hawn. Kull dritt. Ejja naraw, x'hemm isem tiegħek? UDJENZA: Andrew. DAVID J. Malan: Andrew, inti numru 9. Nizza li jissodisfaw inti. Hawnhekk inti tmur. UDJENZA: Jen. DAVID J. Malan: Jen. David. Numru 17. Iva? UDJENZA: Jien Julia. DAVID J. Malan: Julia, David. Numru 20. UDJENZA: Christian. DAVID J. Malan: Christian, David. Numru 22. U? UDJENZA: JP. DAVID J. Malan: JP. Numru 29. Allura aqbad u jiksbu in-- Uh oh. Uh oh. Standby. 20. Ħadd ma jkollu markatur? UDJENZA: Stajt ltqajna Sharpie. DAVID J. Malan: You ltqajna Sharpie? OK. U ħadd ma jkollu biċċa karta? Salv l-lecture. Come fuq. UDJENZA: Imxejna ltqajna. DAVID J. Malan: Aħna ltqajna? Kull dritt, grazie. Here we go. Kien dan mill inti? Inti biss salvati l-ġurnata. Allura 29. Kull dritt. I misspelled 29, iżda OK. Jimxi 'l quddiem. Kull dritt, I ser jagħtuk pinna tiegħek lura mumentarjament. Allura aħna għandna dawn folks hawn. Ejja jkollhom waħda oħra. Gabe, do inti tixtieq li jkollha l-ewwel element hawn? Aħna ser bżonn li inti punt lejn dawn folks multa. Allura 9, 17, 20, 22, sort 29, u mbagħad 34. Did we jitilfu xi ħadd? I do jkollhom 34. Fejn did-- OK, li jixtieq li jkun 34? OK, come fuq up, 34. Kull dritt, dan se jkun ukoll jiswa l-quċċata. X'hemm isem tiegħek? UDJENZA: Peter. DAVID J. Malan: Peter, come fuq up. Kull dritt, hekk Heres mazz sħiħ ta 'nodes. Kull wieħed inti guys jirrappreżenta waħda minn dawn rettangoli. U Gabe, il-ftit fard bniedem out, tirrappreżenta l-ewwel. Allura pointer tiegħu hija ftit iżgħar fuq l-iskrin milli kulħadd. U f'dan il-każ, kull waħda minn tiegħek xellug idejn se jew punt isfel, li b'hekk jirrappreżentaw null, hekk biss l-assenza ta 'pointer, jew li għaddej biex jiġu tipponta fi node li jmiss lilek. Allura issa dritt jekk inti adorn yourselves bħall-istampa hawn, imorru quddiem u l-punt fuq xulxin, ma Gabe b'mod partikolari tipponta lejn numru 9 li jirrappreżentaw il-lista. OK, u n-numru 34, naħa tax-xellug tiegħek għandhom biss jiġu tipponta lejn l-art. OK, għalhekk dan huwa l-lista marbuta. Allura dan huwa l-xenarju in kwistjoni. U fil-fatt, dan huwa rappreżentattiv ta 'klassi ta' problemi li inti tista 'tipprova biex isolvu bil-kodiċi. Inti tixtieq li finalment daħħal element ġdid fil-lista. F'dan il-każ, aħna qed tmur biex ipprova ddaħħal in-numru 55. Iżda hemm għaddej li jkun każijiet differenti li jikkunsidraw. U fil-fatt, dan se jkun wieħed tal-istampa kbar takeaways hawnhekk, hija, liema huma l-każijiet differenti. X'inhuma l-kundizzjonijiet differenti jekk jew fergħat dak il-programm tiegħek jista 'jkollhom? Ukoll, in-numru inti qed tipprova daħħal, li nafu issa li tkun 55, imma jekk inti ma taf bil-quddiem, I daresay taqa 'mill-inqas tliet sitwazzjonijiet possibbli. Fejn jista element ġdid tkun? UDJENZA: U l-aħħar jew nofs. DAVID J. Malan: Fl-aħħar, fil- nofs, jew fil-bidu. So I jallegaw hemm mill-inqas tliet problemi għandna bżonn biex isolvu. Ejja jagħżlu x'hemm forsi forsi l-aktar sempliċi wieħed, fejn l-element il-ġdid tappartjeni fil-bidu. So jien ser ikollhom kodiċi pjuttost bħal tiftix, li I biss kiteb. U jien ser ikollhom PTR, li I ser jirrappreżentaw hawn ma finger tiegħi, bħas-soltu. U ftakar, liema valur aħna ma initialize PTR li? Allura aħna initialized li nulla inizjalment. Imma allura dak ma nagħmlu ladarba aħna kienu ġewwa funzjoni ta 'tfittxija tagħna? Waqqafna din ugwali għal ewwel, li ma jfissirx tagħmel dan. Jekk I sett PTR ugwali għal ewwel, liema Għandu naħa tiegħi verament tkun tipponta lejn? Dritt. Mela jekk Gabe u I huma għaddejjin li jkun valuri ugwali hawn, għandna bżonn li kemm punt numru 9. Allura dan kien il-bidu ta 'l-istorja tagħna. U issa dan huwa biss sempliċi, anki jekk l-sintassi huwa ġdid. Kunċettwalment dan huwa biss tfittxija lineari. Huwa 55 ugwali għal 9? Jew pjuttost, ejja ngħidu anqas minn 9. Minħabba jien tipprova insemmu fejn jitqiegħdu 55. Inqas minn 9, inqas minn 17, inqas minn 20, inqas minn 22, inqas minn 29, inqas minn 34, l-ebda. Allura issa aħna qed fil-każ wieħed ta 'mill-inqas tlieta. Jekk irrid daħħal 55 hawn fuq, liema linji ta 'kodiċi ħtieġa li tikseb esegwiti? Kif ma din l-istampa ta ' bnedmin bżonn għall-bidla? What do I do mal-xellug tiegħi? Dan għandu jkun null inizjalment, għaliex jien fl-aħħar tal-lista. U dak li għandu jiġri hawn ma 'Peter, kien dan? Hu ovvjament se punt lili. So I jallegaw hemm mill-inqas żewġ linji tal-kodiċi fil-kodiċi tal-kampjun mill-lum li għaddej biex jimplimentaw din xenarju ta 'żżid 55 fil-denb. U jista I jkollhom xi ħadd hop up u biss jirrappreżentaw 55? Kull dritt, inti l-ġdid 55. Allura issa dak li jekk il-li jmiss xenarju tidħol flimkien, u rridu li daħħal fil- bidu jew il-kap ta 'din il-lista? U x'hemm isem tiegħek, numru 55? UDJENZA: Jack. DAVID J. Malan: Jack? OK, sbieħ li jissodisfaw inti. Merħba abbord. Allura issa aħna qed tmur biex daħħal, jiġifieri, in-numru 5. Hawn il-tieni każ ta 'l- tlieta aħna ħarāet bil qabel. Mela jekk 5 jappartjeni fil-bidu, ejja ara kif insibu li out. I initialize PTR tiegħi pointer li numru 9 darb'oħra. And I realizzati, oh, 5 hija anqas minn 9. Allura jiffissaw din l-istampa għalina. Li f'idejha, ​​tal Gabe jew David or-- x'hemm isem numru 9 tal-? UDJENZA: Jen. DAVID J. Malan: hands-- Jen tal liema minn idejn tagħna bżonn għall-bidla? OK, hekk Gabe punti fuq dak li issa? Fuq me. I am l-node ġdid. So I ser biss tip ta 'mossa hawn biex tara viżwalment. U sadanittant liema do I punt li? Still fejn jien tipponta. Allura thats it. Hekk biss verament linja waħda ta 'jiffissa kodiċi din il-kwistjoni partikolari, jidher. Kull dritt, hekk li tajjeb. U jista 'xi ħadd tkun placeholder għal 5? Come fuq up. Aħna inti ser tingħata ħin li jmiss. Kull dritt, hekk now-- u Bħala twarrib, l-ismijiet Jien ma tagħmel referenza espliċita dritt issa, pointer pred, pointer predeċessur u pointer ġdida, li l- biss l-ismijiet mogħtija fil-kodiċi tal-kampjun għall-pointers jew idejn tiegħi thats it-tip ta tipponta madwar. X'hemm isem tiegħek? UDJENZA: Christine. DAVID J. Malan: Christine. Merħba abbord. Kull dritt, hekk ejja jikkunsidraw issa xenarju ftit aktar annoying, li biha Irrid li daħħal xi ħaġa bħal 26 fis dan. 20? What? Dawn are-- ħaġa tajba li għandna dan pinna. Kull dritt, 20. Jekk xi ħadd jistgħu jiksbu ieħor biċċa ta ' karta lesta, biss fil case-- kollha dritt. Oh, interessanti. Ukoll dan huwa eżempju ta 'bug lecture. OK hekk x'hemm isem tiegħek mill-ġdid? UDJENZA: Julia. DAVID J. Malan: Julia, inti tista pop out u nippretendu inti kienu qatt hemmhekk? OK, dan qatt ma ġara. Grazzi. Allura jissoponi irridu daħħal Julia fis din il-lista marbuta. Hija huwa n-numru 20. U naturalment hi ser jappartjenu fil- begin-- ma jurux fil xejn s'issa. Allura naħa tiegħek jista 'tip ta' jkun isfel null jew xi valur żibel. Ejja tgħid l-istorja ta 'malajr. Jien tipponta lejn numru 5 f'dan il-ħin. Imbagħad I check 9. Imbagħad I check 17. Imbagħad I check 22. And I realizzata, ooh, Julia jeħtieġ li tmur qabel it-22. Allura dak li jeħtieġ li jiġri? Li f'idejha bżonn għall-bidla? Tal Julia, mini, or-- x'hemm isem tiegħek mill-ġdid? UDJENZA: Christian. DAVID J. Malan: Christian jew? UDJENZA: Andy. DAVID J. Malan: Andy. Christian jew Andy? Andy jeħtieġ li jiġi fi? Julia. Kull dritt. Allura Andy, tridu punt fuq Julia? Iżda stenna minuta. Fl-istorja s'issa, Jien il-tip ta 'wieħed responsabbli, fis-sens li pointer huwa l-ħaġa li l- jiċċaqilqu permezz tal-lista. Aħna jista 'jkollhom isem għal Andy, iżda hemm ebda varjabbli imsejħa Andy. L-unika varjabbli oħra li għandna huwa ewwel, li s irrappreżentata minn Gabe. Allura dan huwa attwalment għaliex b'hekk S'issa aħna ve mhux meħtieġ dan. Imma issa fuq l-iskrin hemm isemmu għal darb'oħra ta 'pointer pred. So let me jkun aktar espliċitu. Jekk dan huwa pointer, kelli aħjar jiksbu ftit aktar intelliġenti dwar iterazzjoni tiegħi. Jekk inti ma mind għaddejjin tiegħi permezz ta 'hawn darb'oħra, tipponta hawn, tipponta hawn. Imma let me jkollhom pointer pred, predeċessur pointer, li l- tip ta tipponta lejn l- element I kien biss fil. Allura meta I go here, issa aġġornamenti naħa tax-xellug tiegħi. Meta mmur here aġġornamenti tiegħi tax-xellug. U issa għandi mhux biss pointer biex l-element li tmur wara Julia, I għad għandhom pointer biex Andy, l-element qabel. Allura inti għandek aċċess, essenzjalment, breadcrumbs, jekk inti se, kollha tal-pointers meħtieġa. Mela jekk jien tipponta lejn Andy u jien wkoll tipponta fil Christian, li f'idejha issa għandu jiġi osservat x'imkien ieħor? Allura Andy issa jistgħu punt fuq Julia. Julia issa tista 'punt fuq Christian. Minħabba li hija tista 'kopja tiegħi pointer lemin tal. U li effettivament tpoġġik lura fis dan il-post hawn. Għalhekk fil-qosor, anke jekk dan qed tieħu us tip ta 'dejjem li attwalment jaġġorna marbuta lista, tirrealizza li l-operazzjonijiet huma relattivament sempliċi. Huwa ta 'wieħed, tnejn, tlieta linji ta 'kodiċi finalment. Iżda imgeżwer madwar dawk linji ta 'kodiċi preżumibilment huwa daqsxejn ta 'loġika li effettivament tqajjem il-mistoqsija, fejn aħna? Are we fil-bidu, l-nofs, jew l-aħħar? Issa, hemm ċertament xi oħra operazzjonijiet nistgħu jimplimentaw. U dawn l-istampi hawn biss juru dak li aħna biss għamlet mal-bnedmin. Xi ngħidu dwar it-tneħħija? Jekk irrid, per eżempju, neħħi l-għadd 34 jew 55, I jista 'jkollhom l-istess tip ta' kodiċi, imma jien ser bżonn waħda jew żewġ passi. Minħabba x'hemm ġdid? Jekk I neħħi xi ħadd fl-aħħar, bħal numru 55 u mbagħad 34, dak għandha wkoll tinbidel hekk kif nista 'nagħmlu? Għandi biex ma evict-- x'hemm isem tiegħek mill-ġdid? UDJENZA: Jack. DAVID J. Malan: Jack. Għandi biex mhux biss evict-- Jack ħielsa, hekk litteralment sejħa Jack b'xejn, jew għall-inqas l-pointer hemmhekk wisq, iżda issa x'għandu jinbidel ma 'Peter? Idejn Tiegħu aħjar tibda tipponta 'l isfel. Għaliex malli I call b'xejn fuq Jack, jekk Pietru għadu tipponta lejn Jack u jien għalhekk iżommu traversat il-lista u l-aċċess dan il-werrej, li meta segmentazzjoni tagħna ħabib antik tort jista 'attwalment kick fil. Għaliex aħna ħadthom tingħata l- memorja lura għall Jack. Inti tista 'tissospendi hemm awkwardly għal ftit mument. Għaliex għandna biss ftit operazzjonijiet finali li jikkunsidraw. Tneħħi l-kap tal-lista, jew il-beginning-- u tal dan wieħed ftit annoying. Għaliex aħna għandek tkun taf li Gabe huwa tip ta 'speċjali f'dan il-programm. Minħabba fil-fatt, huwa għandu pointer tiegħu stess. Hu mhux biss qed mfakkar fil, kif huwa kważi kulħadd hawn. Allura meta l-kap tal-lista hija jitneħħew, li f'idejha bżonn għall-bidla issa? X'hemm isem tiegħek mill-ġdid? UDJENZA: Christine. DAVID J. Malan: Ninsab orribbli fil ismijiet, apparentament. Allura Christine u Gabe, li f'idejha bżonn għall-bidla meta aħna tipprova tneħħi Christine, numru 5, mill-istampa? OK, so ejja do Gabe. Gabe għaddej għall-punt, preżumibbilment, f'numru 9. Imma dak li jmiss għandu jiġri? UDJENZA: Christine għandhom jkun null [inaudible]. DAVID J. Malan: OK, għandna probabbilment make-- Smajt "null" x'imkien. UDJENZA: Null u liberu tagħha. DAVID J. Malan: NULL liema? UDJENZA: Null u liberu tagħha. DAVID J. Malan: Null u liberu tagħha. Allura dan huwa faċli ħafna. U huwa perfett li int issa sort tal permanenti hemmhekk, ma jappartienux. Għaliex inti kont qed diżakkoppjat mill-lista. You ħadthom effettivament ġiet orfni mil-lista. U hekk kellna aħjar sejħa b'xejn issa fuq Christine li jagħti l-memorja lura. Inkella kull darba we tħassar node mil-lista aħna jista 'jkun qed jagħmel il-lista iqsar, iżda mhux attwalment qed jonqos id-daqs fil-memorja. U hekk jekk inżommu żżid u żżid, żżid affarijiet mal-lista, kompjuter tiegħi tista 'tikseb aktar bil-mod u bil-mod u bil-mod, għaliex jien baqgħalna ta ' memorja, anki jekk jien ma attwalment użu bytes Christine ta tal-memorja aktar. Għalhekk fl-aħħar hemm oħrajn xenarji, ta 'tneħħija course-- fin-nofs, it-tneħħija fl-aħħar, kif rajna. Iżda l-aktar interessanti isfida issa hija ser tkun li jikkunsidraw eżattament dak il-ħin tal-ġiri hu. Allura mhux biss inti tista 'żżomm tiegħek biċċiet tal-karti, jekk, Gabe, inti ma mind tagħti kulħadd ballun stress. Grazzi tant għall-lista marbuta tagħna ta 'voluntiera hawn, jekk inti tista'. [Applause] DAVID J. Malan: Kull dritt. Allura koppja ta analitika mistoqsijiet Imbagħad, jekk I jistgħu. Rajna dan notazzjoni qabel, O kbar u omega, limiti ta 'fuq u limiti aktar baxxi fuq il- żmien ta 'xi algoritmu running. Mela ejja jikkunsidraw biss koppja ta 'mistoqsijiet. Wieħed, u aħna qal li qabel, x'inhu l-running ħin tat-tfittxija għal lista f'termini ta 'O big? X'hemm marbuta massimu fuq it-tmexxija żmien ta tiftix lista marbuta kif implimentati mill-voluntiera tagħna hawn? Huwa O kbir ta 'n, lineari. Minħabba li fl-agħar każ, l-element, bħal 55, aħna tista 'tfittex għal jista' jkun fejn Jack kien, it-triq kollha fl-aħħar. U sfortunatament, b'differenza firxa aħna ma tistax tikseb fancy dan iż-żmien. Anke jekk kollha ta 'bnedmin tagħna kienu magħżula minn elementi żgħar, 5, it-triq kollha sa l-element akbar, 55, li normalment ħaġa tajba. Imma dak ma dik is-suppożizzjoni m'għadhomx inessu tagħmel? UDJENZA: [inaudible] DAVID J. Malan: Say mill-ġdid? UDJENZA: aċċess Random. DAVID J. Malan: aċċess Random. U mbagħad dan ifisser nistgħu ebda jibqgħux jużaw żerijiet dgħajfa, intwizzjoni, u obviousness ta 'użu binarja tfittxija u jaqsmu u conquer. Minħabba li anke jekk aħna bnedmin jistgħu ovvjament tara li Andy jew Christian kienu bejn wieħed u ieħor fin-nofs tal-lista, aħna biss nafu li bħala kompjuter permezz ta 'xkumar tal-lista mill-bidu nett. Allura aħna ħadthom rrinunzjaw li l-aċċess bl-addoċċ. O Allura kbira ta 'n issa Hija l-ikona marbuta fil-ħin tfittxija tagħna. What about omega tat-tfittxija tagħna? X'hemm-aktar baxx illegat dwar it-tiftix għal xi numru f'din il-lista? UDJENZA: [inaudible] DAVID J. Malan: Say mill-ġdid? UDJENZA: One. DAVID J. Malan: One. Allura waqt li kostanti. Fl-aħjar każ, Christine hija tabilħaqq fil-bidu tal-lista. U aħna qed tfittex numru 5, hekk sibna tagħha. Allura l-ebda big deal. Iżda hi ltqajna biex tkun fil- bidu tal-lista f'dan il-każ. What about xi ħaġa bħal Ħassar? X'jiġri jekk inti tixtieq li tħassar element? X'hemm-illegat fuq u inferjuri fuq tħassir xi ħaġa minn marbuta lista? UDJENZA: [inaudible] DAVID J. Malan: Say mill-ġdid? UDJENZA: n. DAVID J. Malan: n huwa tabilħaqq l-ogħla marbuta. Minħabba li fl-agħar każ nippruvaw li tħassar Jack, bħal aħna biss għamlet. Huwa tal-triq kollha fl-aħħar. Iqarribna għal dejjem, jew n passi biex issib lilu. Allura dak rbit għoli. C'est lineari, żgur. U l-aħjar każ running time, jew il-limiti aktar baxxi fil-każ aħjar Ikun ħin kostanti. Minħabba forsi nippruvaw li tħassar Christine, u aħna biss jiksbu xxurtjati hi tal fil-bidu. Issa stenna minuta. Gabe kien ukoll fil-bidu, u aħna wkoll kellhom taġġorna Gabe. Allura li ma kienx biss pass wieħed. Allura huwa tabilħaqq kostanti time, fl-aħjar każ, biex tneħħi l-element iżgħar? Huwa, anki jekk jista 'jkun tnejn, tliet, jew saħansitra 100 linji ta 'kodiċi, jekk huwa l-istess numru ta ' linji, mhux f'xi loop, u indipendenti mid-daqs tal-lista, assolutament. Tħassar l-element fil- il-bidu tal-lista, anke jekk aħna jkollhom jittrattaw Gabe, għadu żmien kostanti. Allura din tidher qisha pass enormi lura. U dak ħela ta 'ħin jekk, fil-ġimgħa u ġimgħa żero kellna mhux biss kodiċi pseudocode imma kodiċi attwali biex jimplimentaw xi ħaġa li log bażi n, jew log, pjuttost, ta 'n, bażi 2, f'termini ta 'ħin għat-tmexxija tagħha. Allura għaliex l-Heck kieku rridu nibdew użu xi ħaġa bħal lista marbuta? Yeah. UDJENZA: Allura inti tista 'żżid Elementi għall-firxa. DAVID J. Malan: Allura inti tista ' jiżdiedu elementi għall-firxa. U dan ukoll huwa tematika. U aħna ser tkompli tara dan, dan il-kummerċ off, ħafna simili aħna stajt tidher trade-off mal sort jingħaqdu. Aħna jista 'verament tħaffef tfittxija jew issortjar, pjuttost, jekk nonfqu spazju daqsxejn aktar u jkollhom chunk addizzjonali ta 'memorja jew firxa għall tip jingħaqdu. Iżda aħna jonfqu aktar ispazju, imma aħna jiffranka ħin. F'dan il-każ, aħna qed tagħti up ħin, iżda aħna qed jiksbu flessibilità, dinamiżmu jekk inti se, li huwa probabbilment karatteristika pożittiva. Aħna wkoll qed infiq ispazju. F'liema sens huwa marbut lista aktar għaljin f'termini ta 'spazju minn firxa? Fejn l-ispazju żejda li ġejjin minn? Yeah? UDJENZA: [inaudible] pointer. DAVID J. Malan: Yeah, aħna ukoll għandek l-pointer. Allura dan huwa minorly annoying f'dak m'għadhomx am I ħażna biss int li jirrappreżentaw int. Jien ħażna ta int u pointer, li huwa wkoll 32 bits. So jien litteralment irduppjar l-ammont ta 'spazju involut. Allura dak kompromess, iżda li fil-każ ta 'int. Ejja ngħidu li int mhux ħażna int, iżda jissoponi kull wieħed minn dawn rettangoli jew kull wieħed minn dawn il-bnedmin kien jirrappreżenta kelma, kelma Ingliża li jista jkun ta 'ħames karattri, 10 karattri, forsi anke aktar. Imbagħad żżid biss 32 bits aktar jista 'jkun inqas ta' big deal. X'jiġri jekk kull wieħed mill-istudenti fil-dimostrazzjoni kienu litteralment structs studenti li għandhom ismijiet u djar u forsi numri tat-telefon u Twitter mankijiet u simili. Allura kollha ta 'l-oqsma bdejna jitkellem dwar il-ġurnata l-oħra, ħafna inqas ta 'big deal bħala lymph tagħna jiksbu aktar interessanti u kbar biex jonfqu, eh, addizzjonali pointer biss biex jorbtuhom flimkien. Iżda tabilħaqq, huwa kompromess. U fil-fatt, il-kodiċi hija aktar kumplessi, kif inti ser tara permezz ta 'xkumar permezz li eżempju partikolari. Imma x'jiġri jekk kien hemm xi Grail qaddis hawn. X'jiġri jekk aħna ma jieħdu pass lura iżda massiv pass 'il quddiem u timplimenta data istruttura via li aħna jistgħu jsibu elementi bħall Jack jew Christine jew xi elementi oħra f'dan array fil-ħin kostanti vera? Fittex huwa kostanti. Ħassar hija kostanti. Daħħal hija kostanti. Kollha ta 'dawn l-operazzjonijiet huma kostanti. Dan ikun Grail qaddis tagħna. U li huwa fejn aħna se jittellgħu ħin li jmiss. Ara inti mbagħad.