[Muusika mängimine] DAVID J. Humala: Olgu. See on CS50. See on nädala viie jätkus ning me on häid uudiseid ja halbu uudiseid. Nii hea uudis on see, et CS50 käivitab sel reedel. Kui soovid meiega liituda, pea tavaline URL siia. Veelgi parem uudis, ei loeng tuleval esmaspäeval 13.. Veidi vähem parem uudis, viktoriin null on järgmisel kolmapäeval. Rohkem infot saab leida see URL siia. Ja järgmise paari päeva jooksul saadame täites toorikud seoses tuba et me oleme kaitstud. Parem uudis on see, et saad on muidugi hõlmavast istungil tuleval Esmaspäev õhtul. Jälgige kursuse veebisait asukoha ja detailid. Sektsioonid, kuigi see on puhkus, kohtub ka samuti. Parim uudis, loeng järgmisel reedel. Nii et see on traditsioon, et me on, kui ühe õppekava. Lihtsalt-- see saab olema hämmastav. Sa näed asju konstantse ajaga andmestruktuurid ja hash tabeleid ja puud ja proovib. Ja me räägime sünnipäev probleeme. Terve hunnik kraami ootab järgmisel reedel. OK. Igatahes. Nii et meelde tuletada, et me oleme olnud keskendub see pilt, mis on sees meie arvuti mällu. Nii et mälu või muutmälu on koht, kus programmid olemas, kui sa kasutad neid. Kui te topeltklõps ikooni, et käivitada mõned programmi või topeltklõpsake ikooni, et avada mõnda faili, see on koormatud kõvakettalt autot või tahkes olekus autot RAM, muutmälu, kus ta elab kuni toide välja lülitub, sülearvuti kaas sulgub, või sa väljud rakendusest. 

Nüüd, kui mälu on mis siis ilmselt on 1 GB nendel päevadel, 2 gigabaiti või isegi palju rohkem, Üldiselt on sätestatud antud programmi Selles omamoodi ristkülikukujuline kontseptuaalse mudeli kusjuures meil stack allosas ja hunnik muid asju ülaosas. Asi tipus Me oleme näinud seda pilti Enne aga ei rääkinud on nn tekstiosa. Tekst segment on lihtsalt fancy viis öelda nullid ja need, mis kirjutada oma tegelik koostatud programmi. 

Nii et kui te topeltklõps Microsoft Word Mac või PC, või kui sa jooksed dot kaldkriips Mario kohta Linuxi arvuti oma terminali aknas nullid ja need, mis moodustavad Word või Mario ladustatakse ajutiselt Teie arvuti muutmälu nn teksti segment konkreetse programmi. Allpool mis läheb vormindatud ja uninitialized andmed. See on midagi sellist globaalsed muutujad, et me ei kasuta paljud, kuid mõnikord me oleme oli globaalsete muutujate või staatiliselt määratud stringe, mis on kõva kodeeritud sõnu nagu "tere" mis ei ole tehtud kasutaja mis on kodeeritud oma programmi. 

Nüüd alumises otsas me on nn pinu. Ja virna, seni oleme olnud kasutades milliseid eesmärgil? Mis stack on kasutatud? Jah? 

Sihtrühm: funktsioonid. 

DAVID J. Humala: Funktsioonide? Mis mõttes funktsioonide? 

Sihtrühm: Kui te helistate funktsiooni argumendid kopeeritakse pinu. 

DAVID J. Humala: Täpselt. Kui te helistate funktsiooni oma argumendid kopeeritakse pinu. Nii et iga X või Y või A või B et sa pääsemist funktsioon ajutiselt panna nn korstna nagu üks Annenberg söögisaal plaate ja ka asjad nagu kohalikud muutujad. Kui teie foo funktsiooni või oma swap funktsioon on kohalikud muutujad, nagu temp, need kaks lõpuks on virnas. Nüüd me ei räägi liiga palju neid, kuid need keskkonnamuutujateta allosas nägime aega tagasi, kui Olin futzing klaviatuuri üks päev ja hakkasin pääseb asju nagu argv 100 või argv 1000, lihtsalt elements-- ma unustan numbers-- kuid ei pidanud juurde mind. Me hakkasime nägema mõned funky sümbolid ekraanil. Need olid nn keskkonnamuutujateta nagu globaalne seadeid minu programmi või minu arvuti, ei mitteseotud viimastel viga, mis me arutasime, Shellshock, mis on olnud kannatavad üsna vähe arvuteid. 

Nüüd lõpuks, tänapäeva fookus me lõpuks hunnik. See on veel üks patakas mälu. Ja põhimõtteliselt kõik see mälu on sama värk. See on sama riistvara. Oleme vaid omamoodi ravides erinevaid klastrite baitide erinevatel eesmärkidel. Hunnik on ka saab olema, kui muutujad ja mälu, et teil paluda alates operatsioonisüsteemi ajutiselt hoitakse. 

Aga seal on mingi probleem siin, nagu pilt tähendab. Meil on justkui kaks laevade kohta põrkuvad. Sest kui te kasutate rohkem virna ja nagu me täna näeme aastast, kui te kasutate rohkem ja rohkem hunnik, kindlasti halbu asju võib juhtuda. Ja tõepoolest, saame esile, et tahtlikult või tahtmatult. Nii et pinge viimase aega oli see programm, mis ei teeni ühtegi funktsionaalne muul eesmärgil kui näidata kuidas sa nii halb, võib tegelikult võtta ära vead kellegi programmi ja üle võtta programmi või isegi Kogu arvutisüsteemi või server. Nii lihtsalt pilgu korraks, siis märgata, et peamine allosas võtab käsurea argumentide kohta argv. Ja see on kõne funktsioon f, sisuliselt nimetu funktsiooni nimetatakse f, ja see kulgeb argv [1]. 

Nii et mis iganes sõna kasutaja liigid juures kiiret pärast selle programmi nime, ja siis see suvalise funktsiooni üles top, f, võtab string, AKA char * sest me oleme hakanud arutama, ja see lihtsalt kutsub seda "bar". Aga me võime seda kutsuda midagi. Ja siis ta teatab, sees f array tähemärki nimetatakse c-- 12 sellist märki. 

Nüüd, aasta lugu ma ütlen Hetk tagasi, kui mälu on c, või on need 12 tähemärki läheb lõpuks? Lihtsalt olla kindel. Jah? 

Sihtrühm: korstnat. 

DAVID J. Humala: korstnat. Nii on c kohaliku muutuja. Me palume 12 tähemärki või 12 baiti. Need hakkavad lõpuks aasta nn pinu. Nüüd lõpuks on see teine ​​funktsioon see on tegelikult päris kasulik, aga meil ei ole tegelikult kasutatud ta ise strncopy. See tähendab string koopia, kuid ainult n tähed, n tähemärki. Nii n märgid kopeeritud baar arvesse c. Ja kui palju? Pikkus baari. Nii teisisõnu, et üks liin, strncopy, läheb kopeerida tõhusalt baar c. 

Nüüd, lihtsalt selline ennetada Moraal sellest loost, mis on potentsiaalselt probleemne siin? Kuigi me kontrollime pikkus baar ja kulgeb see strncopy, Mis on su soole ütlen sulle ei ikka katki selle programmi? Jah? 

Sihtrühm: Ei sisalda ruumi null iseloomu. DAVID J. Humala: Ei sisalda ruumi null iseloomu. Potentsiaalselt erinevalt varasem praktika me isegi ei on nii palju kui pluss 1 kuni mahutada, et null iseloomu. Aga see on veel hullem kui see. Mida muud me ei suuda teha? Jah? 

Sihtrühm: [kuuldamatu] DAVID J. Humala: Perfect. Me oleme kõvasti kodeeritud 12 päris suvaliselt. See ei ole nii palju probleem, vaid asjaolu et me ei ole isegi kontrollida, kas pikkusega riba on väiksem kui 12, sellisel juhul saab olema ohutu panna see mällu nimetatakse c, et oleme eraldatud. Tõepoolest, kui riba on nagu 20 tähemärki pikk, Selle funktsiooni näib kopeerides 20 märki baar arvesse c, mis võttes vähemalt 8 baiti et see ei tohiks olla. See tähendas siin. 

Lühidalt öeldes katki programmi. Mitte nii suur asi. Äkki saad killustatust süü. Me kõik oleme olnud vead programmides. Me kõik võib olla vigu programmides kohe. Aga mis on kaudselt? Noh, siin on suumitud-in versioon et pilt minu arvuti mällu. See on alt mu virna. Ja tõepoolest, väga põhjas on see, mis kutsus vanem rutiinne stack, fancy viis öelda, et see on peamine. Nii et kes nimetatakse funktsiooni f, mis me räägime. Nii et see on põhja pinu. Tagasi aadress on midagi uut. See on alati olemas olnud, alati olnud, et pilt. Me lihtsalt ei helistanud tähelepanu. Sest selgub, kuidas c töötab, on et kui üks funktsioon nõuab teise mitte ainult teha argumente, mis funktsioon saada surunud peale virna, mitte ainult ei funktsiooni kohaliku muutujad saada surunud peale virna, midagi, mida nimetatakse saatja aadress Samuti saab panna peale virna. Täpsemalt, kui peamised kõned foo, peamised on oma aadress mällu, härg midagi, tegelikult saab panna peale virna nii, et kui f on tehtud käivitamata teab, kuhu hüpata tagasi tekstis segment, et jätkuvalt täidetakse. 

Nii et kui me siin oleme kontseptuaalselt aastal peamine, siis f saab nn. Kuidas f tea, kes et käsitsi kontrolli tagasi? Noh, see väike riivsai punaselt siin nimetatakse saatja aadress, see lihtsalt kontrolli, mis seisneb selles, et saatja aadress? Oh, andke mulle tagasi hüpata Otse siin. Ja see on natuke ülelihtsustatuna, sest nulli ja need jaoks peamine on tehniliselt siia üles tech segment. Aga see mõte. f lihtsalt peab teadma, mida kus kontroll lõpuks läheb tagasi. 

Aga kuidas arvutid on ammu sätestatud asjad nagu kohalikud muutujad ja argumendid on niimoodi. Nii peal see pilt sinine on freimi jaoks f, nii et kõik ning mälu, et f konkreetselt ei kasuta. Nii et järelikult märgata, et baar on siin pildil. Baar oli tema argument. Ja me väita, et argumendid funktsioonid vajutata peale virna. Ja c, on muidugi see, ka seda pilti. 

Ja just Tähistused eesmärkidel, teate ülaosas vasakul nurgas on see, mis oleks c sulg 0 ja siis veidi alla paremale on c sulg 11. Nii teisisõnu, te võite ette kujutada et seal on ruudustik baiti seal, esimene on Üleval vasakul on põhjas, mis on viimase nendest 12 baiti. 

Aga nüüd proovida kiiresti edasi. Mis hakkab juhtuma siis, kui võtame string riba, mis on enam kui c? Ja me ei ole kontrollida, kas see on tõesti enam kui 12. Milline osa sellest pilt läheb saada kirjutatakse baiti 0, 1, 2, 3, dot dot dot, 11 ja seejärel halb, 12, 13 kuni 19? Mis juhtub siin, Kui te järeldada tellimine et c sulg 0 on peal ja c sulg 11 on justkui maha paremale? Jah? 

Sihtrühm: Noh, see läheb kirjutada char * baar. 

DAVID J. Humala: Jah, see näeb välja nagu sa lähed kirjutada char * baar. Ja mis veel hullem, kui saadate tõesti pikk string, siis võib isegi kirjutada, mida? Saatja aadress. Mis jällegi on nagu riivsai öelda programmi, kus tagasi minna, kui f tehakse kutsutakse. 

Mida pahad tavaliselt teha on see, kui nad kohanud programmi et nad on uudishimulik, kas on kasutatavust, lollakas viisil et ta võib võtta ära, mis viga, Üldiselt nad ei saa Selle õiguse esmakordselt. Nad lihtsalt saatma hakata, näiteks juhuslikult koostatud stringe oma programmi kas klaviatuuri, või ausalt öeldes nad ilmselt kirjutada väike programm lihtsalt automaatselt genereerida stringid, ja hakata peksma oma programmi saates palju erinevaid sisendeid erineva pikkusega. 

Niipea, kui teie programm jookseb kokku, see on hämmastav asi. Sest see tähendab, et ta või ta on avastanud mis on ilmselt tõepoolest viga. Ja siis nad saavad rohkem targad ja alustada keskendudes kitsamalt kuidas kasutada, et viga. Eelkõige, milline ta võib tegema, on saata, parimal juhul, tere. Ei midagi erilist. See on string, mis on piisavalt lühike. Aga mis siis, kui ta saadab, ja me üldistada seda, rünnak code-- nii nulli ja need, kes teevad asju nagu rm-rf, et eemaldada kõik kõvakettale või saata rämpsposti või kuidagi rünnata masin? 

Seega, kui kõik need tähed lihtsalt on, kontseptuaalselt, rünnak, rünnak, rünnak, rünnak, halbu kood et keegi kirjutas, kuid kui see inimene on piisavalt tark, mitte ainult hõlmama kõiki Nende rm-RFS, vaid ka on tema viimastel baiti olla number, mis vastab Lisa aadress tema või tema enda rünnak kood et ta möödunud aastal vaid esitades küsimuse järel saate tõhusalt trikk arvuti arvesse märganud, kui f on teinud täidesaatva, Oh, see on minu jaoks aega hüpata tagasi punane saatja aadress. Aga kuna ta on kuidagi kattusid et saatja aadress oma number, ja nad on piisavalt targad, et on konfigureeritud, et number viidata, kui näed super top vasakus nurgas, tegeliku aadressi arvuti mälestuseks mõned nende rünnaku kood, paha poiss saab trikk arvuti arvesse täidesaatva enda kood. 

Ja see kood uuesti, võib olla mis iganes. See on tavaliselt nimetatakse shell kood, mis on lihtsalt viis öelda, et see ei ole üldiselt midagi nii lihtne rm-rf. See on tegelikult midagi Bash, või tegelik programm, mis annab talle või tema programmilisi kontrolli teostada midagi muud, mis nad tahavad. Lühidalt öeldes, see kõik tuleneb tõsiasjast, et see viga on seotud mitte kontrollida piire oma valikut. Ja kuna teed arvutite tööd on, et nad kasuta virna tõhusalt, kontseptuaalselt alt ülesse, kuid siis elemendid surute peale virna kasvab ülevalt alla, see on uskumatult problemaatiline. Nüüd on võimalusi töötada selle ümber. Ja ausalt öeldes, on keeled kellega töötada selle ümber. Java on immuunsüsteemi, näiteks selles konkreetses küsimuses. Sest nad ei anna teile vihjeid. Nad ei anna teile otsene mälu aadressid. Nii et see vägi, mis meil on puudutada midagi mälestuseks soovime tuleb küll suur risk. 

Nii et hoidke silmad lahti. Kui aus olla, siis on kuu või aastaid, millal lugesid mõned ärakasutamise programmi või server, kui sa kunagi näha vihjet midagi nagu buffer overflow rünnak, või stack overflow on teist tüüpi rünnak, sarnase sisuga, palju inspireerib veebisaidi nimi, kui sa tead seda, see on kõik räägime lihtsalt täis suurust mõned iseloomu massiiv või mõni massiivi üldisemalt. Kõik küsimused, siis selles küsimuses? Ärge proovige seda kodus. 

Olgu. Nii malloc Seni on meie uus sõber, et saame eraldada mälu et me ei pruugi teada, ette, et me tahame, et meil ei ole kõva kood meie Programmi numbrid nagu 12. Kui kasutaja ütleb meile, kui palju Andmete ta tahab sisend, saame malloc et palju mälu. 

Nii malloc selgub, et määral oleme seda kasutanud, sõnaselgelt viimast korda, ja siis Te olete seda kasutanud jaoks getString teadmatult eest mitu nädalat, kõik malloc mällu pärineb nn hunnik. Ja see on põhjus, miks getString näiteks võib eraldada mälu dünaamiliselt teadmata, mida sa oled läheb kirjuta ette, käe tagasi pointer, et mälu ja et mälu on ikka sinu hoida, isegi pärast getString tulu. Sest tagasivõtmine ju, et stack on pidevalt läheb üles ja alla, üles ja alla. Ja niipea, kui see läheb sätestatakse, et mis tahes mälu seda funktsiooni kasutada tuleks ei tohi kasutada keegi teine. See prügi väärtused nüüd. 

Aga hunnik on siin. Ja mis on tore malloc on see, et kui malloc eraldab mälu siin, see ei mõjutanud, sest põhiliselt virna. Ja nii iga funktsiooni saab kasutada mälu, mis on malloc'd, isegi funktsioon nagu getString, isegi pärast seda tagasi. 

Nüüd vastupidist malloc on tasuta. Ja tõepoolest, õigusriigi sa vaja alustada vastuvõtmist on midagi, mis tahes, iga kord, kui kasutate malloc peate ise kasutada tasuta lõpuks aasta sama pointer. Kogu selle aja oleme olnud kirjalikult lollakas, lollakas kood, mitmel põhjusel. Kuid üks, mis on olnud kasutades CS50 raamatukogu, mis iseenesest on sihilikult lollakas, see lekib mälu. Iga kord, kui sa oled kutsutud getString Viimase paari nädala jooksul Me palume operatsioonisüsteemi süsteemi, Linux, mälu. Ja sa ei ole kunagi kunagi andnud seda tagasi. Ja see ei ole a harjutada, hea asi. 

Ja Valgrind üks vahendeid kasutusele pset 4, on kõike, mis aitab teil nüüd leida vigu niimoodi. Aga õnneks pset 4 sa ei pea kasutada CS50 raamatukogu või getString. Nii tahes vigu, mis on seotud mälu on lõpuks saab olema oma. 

Nii malloc on rohkem kui lihtsalt mugav selleks. Me ei saa tegelikult nüüd lahendada põhimõtteliselt erinevad probleemid, ja põhimõtteliselt lahendada probleeme rohkem tõhusalt nädalas null lubadust. Senini on see seksikaim andmestruktuur oleme olnud. Ja andmestruktuur ma tähenda ainult viis kontseptualiseerimiseks mälu viisil, mis läheb kaugemale lihtsalt öeldes see on int, see on paalia. Me ei saa hakata klastri asju koos. 

Nii massiivi nägi välja selline. Ja mis oli võti kohta massiiv on, et see annab sulle back-to-back tükkideks mälu, millest igaüks saab olema sama tüüpi, int, int, int, int või char, char, char, char. Aga seal on mõned varjuküljed. See on näiteks massiivi suurus kuus. Oletame, et täita seda massiivi kuus numbrid ja siis mingil põhjusel, Sinu kasutaja tahab anda sa seitsmes number. Kust sa seda? 

Mis on lahendus, kui teil on loodud massiivi korstnat näiteks lihtsalt koos nädalal kaks märke, et oleme kasutusele ruudu sulgudes number sees? Noh, sul on kuus numbrid need kastid. Mida su instinktid olema? Kuhu sa tahad seda? 

Sihtrühm: [kuuldamatu] 

DAVID J. Humala: Vabandust? 

Sihtrühm: Pane see lõpuni. 

DAVID J. Humala: Pane see lõpuni. Nii lihtsalt üle paremale, väljaspool seda kasti. Milline oleks tore, kuid see Selgub, sa ei saa seda teha. Sest kui sa ei küsita Selle patakas mälu, see võib olla juhus, et see kasutatakse mõne muu muutuja kokku. Mõtle tagasi nädala või nii, kui me ette välja Zamyla ja Davin ja Gabe nimed mällu. Nad olid sõna otseses mõttes tagasi tagasi tagasi. Nii et me ei saa alati usun, et kõike, mis on siin on olemas minu jaoks kasutada. 

Mida veel võiks teha? Noh, üks kord aru, sa vajame massiivi suurus seitse, võid lihtsalt luua massiivi suurus seitse, siis kasuta loop või samas loop, kopeerige see uue massiivi, ja siis kuidagi lihtsalt vabaneda Selle massiivi või lihtsalt kasutamise lõpetamiseks. Aga see ei ole eriti tõhus. Ühesõnaga, massiivid ei lase sa dünaamiliselt suurust. 

Nii et ühest küljest saad muutmälu, mis on hämmastav. Sest see võimaldab meil teha asju nagu lõhe ja vallutada, binaarne otsing, mis kõik me oleme rääkis ekraanil siin. Aga sa värvi ise nurka. Niipea kui sa tabanud lõpuks oma valikut, mida sa pead tegema väga kallis operatsioon või kirjutada terve hunnik koodi nüüd tegeleda selle probleemiga. 

Mis siis, kui selle asemel oli meil midagi, mida nimetatakse nimekiri, või ahelloend eriti? Mis siis, kui selle asemel, et ristkülikud seljad tagasi, meil on ristkülikud, mis jätavad vähe natuke kõigutama ruumi nende vahel? Ja kuigi ma olen koostanud käesoleva pilt või kohandatud seda pilti ühest tekste siin tuleb tagasi seljad väga korrapärane, tegelikult, üks neist ristkülikud võiks olla siin mälu. Üks neist võiks olla siin üleval. Üks neist võiks olla siin üleval, siin, ja nii edasi. 

Aga mis siis, kui me joonistasin, sel juhul nooled et kuidagi seostada neid ristkülikuid koos? Tõepoolest, me oleme näinud tehniline kehastus nool. Mida oleme kasutatud viimastel päeva, et all kapuuts, esindaks nool? Pointer, eks? 

Mis siis, kui selle asemel, et lihtsalt ladustamiseks numbrid, nagu 9, 17, 22, 26, 34, Mis siis, kui me ei salvestata mitte ainult number, kuid osuti kõrvuti sellise arvu? Nii et palju nagu sa oleks niit nõel läbi terve hunnik kangast, kuidagi sidumine asjad koos, samamoodi ei saa me koos suunanäitajaks, kui kehastunud nooltega siin liiki jutustama koos individuaalsete ristkülikud tõhusalt kasutades pointer kõrvuti number, et märgib, et mõned järgmine number, et osutab omakorda mõned järgmine number? Nii teisisõnu, mida kui me tegelikult tahtsime rakendada midagi sellist? Noh kahjuks need ristkülikud, vähemalt üks 9, 17, 22, ja nii edasi, need ei ole enam kena ruudud ühte numbrid. Alt, ristkülik Allpool 9, näiteks näitab, mida peaksid olema pointer, 32 bitti. Nüüd, ma ei ole veel teadlik mis tahes andmete tüüp C, mis annab teile mitte ainult int kuid pointer täielikult. 

Mis siis lahendus, kui tahame leiutada oma vastus sellele? Jah? 

Sihtrühm: [kuuldamatu] 

DAVID J. Humala: Mis see on? 

Sihtrühm: Uus struktuur. 

DAVID J. Humala: Jah, miks ei me luua uus struktuur, või C, struct? Me oleme näinud structs enne, kui lühidalt, kus tegelesime õpilane struktuur nagu see, kellel oli nimi ja maja. In pset 3 Breakout sa kasutada kogu hunnik structs-- GRect ja GOvals et Stanford loodud klastri info koos. Mis siis, kui me võtame selle sama idee märksõnad "typedef" ja "struct" ja siis mõned üliõpilane spetsiifilised asjad, ja arenema seda arvesse järgmised: typedef struktuure node-- ja sõlm lihtsalt väga generic arvutiteadus perspektiivis midagi andmestruktuur, konteinerit andmestruktuur. Sõlme Väidan läheb on int n, täiesti arusaadav, ja siis veidi salapäraselt, see teine ​​joon, struct node * kõrval. Aga vähem tehnilisi termineid, Mis on see, et teine ​​rida koodi sees looksulg? Jah? 

Sihtrühm: [kuuldamatu] DAVID J. Humala: kursor teise sõlme. Nii tõsi, süntaks veidi segasena. Aga kui sa loed seda sõna otseses mõttes, Järgmine on nime muutuja. Mis on selle andmetüübi? See on veidi verbaalselt, seekord aga see tüüp struct node *. Iga kord, kui me oleme näinud midagi star, et tähendab, et see kursor andmete tüüp. Nii et järgmine on ilmselt kursor struct node. 

Nüüd, mis on struct node? Noh, teate te näete neid samad sõnad ülevalt paremalt. Ja tõepoolest, te vaadake ka sõna "Sõlm" siin all vasakul. Ja see on tegelikult lihtsalt mugavuse. Pange tähele, et meie õpilane määratlus seal on sõna "õpilane" ainult üks kord. Ja see on sellepärast, et üliõpilane objekti ei eneseleosutavad. Seal ei ole midagi sees õpilane mis vajab punktist teise üliõpilase, persay. See oleks omamoodi imelik reaalses maailmas. 

Kuid sõlmega seotud nimekiri, me ei taha sõlme olema referentsiaalse sarnase objekti. Ja nii märkate muutusi siin ei ole lihtsalt, mis seal sees looksulg. Aga me lisada sõna "sõlm" ülaosas, samuti lisades selle alt asemel "õpilane". Ja see on vaid tehniline detail nii et jälle oma andmestruktuur saab eneseleosutavad, nii et sõlm võib juhtida ka teise sellise sõlme. 

Nii et mis see on lõppkokkuvõttes läheb meie jaoks tähendab? Noh, üks, seda kraami sees on sisu meie sõlme. See asi siin, Paremal ülal on lihtsalt nii veel kord, et me ei viita endale. Ja siis äärepoolseimate kraami kuigi sõlm on uus mõiste, võib-olla, et see on ikka sama õpilane ja mida oli all kapuuts SPL. 

Nii et kui me nüüd tahtis alustada rakendamisel seotud nimekirja, kuidas võiks tõlkida midagi sellist koodi? Noh, lihtsalt vaata näide programm, mis tegelikult kasutab seotud nimekirja. Seas tänapäeva jaotus kood on programm nimega Eesti Zero. Ja kui ma saan seda ma loodud super lihtne GUI, graafiline kasutajaliides, aga see on tõesti lihtsalt printf. Ja nüüd ma olen andnud ennast mõne menüü options-- Kustuta, Lisa, otsing, ja Traverse. Ja lõpetan. Need on vaid ühised toimingud andmestruktuur tuntud lingi nimekirja. 

Nüüd Kustuta läheb Numbri kustutamine nimekirjast. Sisesta läheb lisada number nimekirjas. Otsi läheb otsima jaoks number nimekirjas. Ja Traverse on lihtsalt fancy viis öelda, kõndida läbi nimekirja prindi see välja, kuid see on kõik. Ära muuda see kuidagi. 

Nii et proovime seda. Lähme edasi ja 2. tüüpi. Ja siis ma lähen sisestada, ütleme 9. Sisesta. Ja nüüd mu programm on lihtsalt programmeeritud öelda, nimekiri on nüüd 9. Nüüd, kui ma edasi minna ja ei Paigaldage uuesti, lase mul minna ja välja suumida ja kirjuta 17. Nüüd on mu nimekirjas on 9, siis 17. Kui ma sisestada uuesti, lähme vahele üks. Selle asemel, et 22, kui ühe pildi me oleme otsinud siin, las ma sinna hüpata ja lisada 26 järgmine. Nii et ma lähen kirjuta 26. Nimekiri on mul oodata. Aga nüüd, lihtsalt et näha, kas see kood saab olema paindlik, andke mulle nüüd tüüp 22, milles vähemalt kontseptuaalselt, kui me oleme Hoides seda sorteerida, mis on tõepoolest saab veel ühe värava kohe, peaks minema vahemikus 17 ja 26. Nii et ma Enter. Tõepoolest, mis töötab. Ja nüüd lubage mul lisada Viimase kohta pilt, 34. 

Olgu. Nii et nüüd las ma ette näha, et Kustuta ja Traverse ja otsing teha, tegelikult töötavad. Tegelikult, kui ma joosta Search, olgem otsida number 22, Enter. Ta leidis 22. Nii et on, mida see Programmi Eesti Zero teeb. 

Aga mis tegelikult toimub kohta, mis rakendab seda? Noh, esiteks ma võib-olla, ja tõepoolest Ma ei ole, fail nimega list0.h. Ja kusagil on see line, typedef, struct node, siis on mul looksulg, int n, ja siis struct-- mis oli mõiste? Struct node kõrval. Seega peame star. Nüüd tehniliselt kui me sattuda harjumus joonistus siin. Võite näha õpikute ja Internetis viited seda seal. See on funktsionaalselt samaväärne. Tegelikult on see natuke rohkem iseloomulik. Aga ma tulen kooskõlas sellega, mida eelmisel korral ja seda teha. Ja siis lõpuks, ma lähen seda tegema. 

Nii päisefailist kusagil on list0.h täna on see struct määratlus, ja võibolla mõned muud kraami. Vahepeal list0c seal kavatse olla mõned asjad. Aga me lihtsalt alustada ja ei lõpeta seda. List0.h on fail tahan lisada oma C-faili. Ja siis mingil hetkel ma olen läheb on int, peamine, tühine. Ja siis ma lähen mõned to-do on siin. Ma olen ka kavatse olla prototüüp, nagu tühine, otsing, int, n, mille eesmärk elus on otsida element. Ja siis siin ma väita Tänapäeva kood, tühine, otsing, int n, no semikooloniga kuid avatud looksulg. Ja nüüd ma tahan kuidagi otsida element selles loetelus. Aga meil ei ole piisavalt informatsiooni ekraanil veel. Ma ei ole tegelikult esindatud nimekiri ise. Nii et üks viis, kuidas me võiks rakendada seotud nimekirja programmi on mul selline tahan teha midagi nagu kuulutab seotud nimekirja siin. Lihtsuse mõttes ma lähen tegema Selle ülemaailmse, kuigi üldiselt me ei tohiks seda liiga palju. Aga see Näite lihtsustamiseks. Nii et ma tahan kuulutada seotud nimekirja siin. Nüüd, kuidas võiks seda teha? 

Siin on pilt, mis on seotud nimekirja. Ja ma tõesti ei hetkel teada, kuidas Ma lähen edasi minna esindavad nii palju asju vaid ühe muutuja mälu. Aga arvan, et tagasi hetkel. Kogu selle aja oleme olnud stringid, mis me siis selgus, et massiive märki, mis me siis selgus, et lihtsalt olla pointer Lisa esimese märgi array tähemärki et on null lõpetada. Nii et selle loogika ja selle pilt liiki külv oma mõtteid, mida vaja me tegelikult kirjutada meie kood esindama seotud nimekirja? Kui palju seda teavet me vajame lüüa C kood, mis sa ütled? Jah? 

Sihtrühm: Meil ​​on vaja viit sõlme. DAVID J. Humala: kursor sõlme. Eriti mis sõlme oleks oma instinktid on hoida kursorit? 

Sihtrühm: esimene sõlm. 

DAVID J. Humala: Jah, ilmselt esimene. Ja teate, esimene sõlm on erineva kujuga. See on ainult poole väiksem struktuure, sest see on tõesti ainult pointer. Nii et see, mida saab tõesti teha, on tunnistada ahelloend olema tüüpi sõlme *. Ja olgem lihtsalt nimetame seda esimest ja initsialiseerida see tühjaks. Nii null jällegi on tulemas sellele pildile siin. Mitte ainult null kasutada nagu erilist tagastatav väärtus asjad getString ja malloc, null on null pointer puudumine pointer, kui soovite. See tähendab lihtsalt, midagi on veel siin. Nüüd esimene, ma oleks pidanud nimetatakse seda kõike. Ma oleks võinud nimetas seda "nimekiri" või mitmeid muid asju. Aga ma kutsun seda "esimene", nii et see ridade järele see pilt. Nii nagu string võib olla esindatud koos aadressi esimese baidi, nii saab seotud nimekirja. Ja me näeme, muud andmed struktuurid on esindatud vaid üks pointer, 32-bit nool, mis osutab väga esimesel sõlme struktuuri. 

Aga nüüd lähme ennetada probleemi. Kui ma vaid meeles pidada minu programm aadress ning esimene sõlm, esimese ruut selles andmestruktuur, Mis oleks parem olla nii umbes rakendamise mu ülejäänud nimekiri? Mis peamine detail, mis läheb tagada see tegelikult toimib? Ja "tegelikult töötab" I Tähendab, palju nagu string, laseb meil minna esimene märk aastal Davin nime teiseks Lisa kolmandaks Neljas, kuni lõpuni, kuidas me teame, kui me aasta lõpus on seotud nimekirja, mis näeb välja nagu see on? Kui see on null. Ja ma olen esindatud selline nagu nagu elektriinsener väest, koos vähe madalikule sümbol, kehvasti. Aga see tähendab lihtsalt null käesolevas asjas. Võite teha seda iga number viisil, kuid selle autor juhtus, et kasutada seda sümbolit siin. 

Nii kaua, kui me nöörile kõik need sõlmed kokku ainult mäleta, kuhu Esimene on, nii kaua kui me paneme erilist sümboli väga viimase sõlme nimekirja ja me kasutame null, sest see on mis meil on meie käsutuses, see nimekiri on täielik. Ja isegi kui ma ainult teile kursor Esimene element, sa, programmeerija, saab kindlasti juurde edasi. Kuid olgem lase oma meeled tiir natuke, kui nad ei ole juba üsna wandered-- mis saab sõiduaega leida midagi selles nimekirjas? Kurat, see on suur O n, mis ei ole halb, õiglus. Aga see on lineaarne. Oleme loobunud mida funktsioon massiivid, liikudes rohkem suunas see pildi dünaamiliselt põimitud või seotud sõlmed? Me oleme loobunud muutmälu. Massiiv on tore, sest matemaatiliselt kõik on seljad et seljad. Kuigi seda pilti tundub päris, ja isegi kuigi tundub, et need sõlmed on ilusti vahedega, tegelikkuses nad võivad olla kõikjal. OX1, Ox50, Ox123, Ox99 need sõlmed võivad olla kõikjal. Kuna malloc ei eraldada mälu laduma, kuid kõikjal hunnik. Sa ei pruugi teada, et see on läheb tagasi tagasi tagasi. Ja nii see pildi reaalsus ei kavatse olla päris see ilus. 

Nii see läheb võtab natuke tööle rakendada seda funktsiooni. Nii et olgem rakendada Otsi. Ja me näeme, millist nutikas viis seda teha. Nii et kui ma otsingu funktsiooni ja Ma antud muutuja täisarv n otsida, ma pean teadma, uus süntaks otsin sees struktuur, mis on osutas, et leida n. Nii et teeme seda. 

Nii et kõigepealt ma lähen edasi ja kuulutada sõlme *. Ja ma kutsun seda pointer, lihtsalt kokkuleppeliselt. Ja ma initsialiseerida see esimene. Ja nüüd ma saan seda aastal mitmel viisil. Aga ma lähen võtta ühine lähenemisviis. Kuigi osuti ei ole võrdne null, ja see on kehtiv süntaks. Ja see tähendab lihtsalt seda järgmise, nii Niikaua kui sa ei osutavad midagi. Mida ma tahan teha? 

Kui osuti dot n, lubage mul tagasi tulla sellele võrdub-- võrdub mis? Mis väärtust ma otsin? Tegelik n, mis oli möödunud aastal. Nii et siin on veel üks omadus, C ja paljudes keeltes. Kuigi struktuuri nimetatakse sõlm on väärtus n, täiesti õigustatud et ka kohalikud argument või muutuja nimega n. Sest isegi me koos inimese silmad, võib eristada et see n on eeldatavasti sellest erinevad n. Kuna süntaks on erinev. Sul on dot ja pointer, arvestades, et see üks ei ole sellist asja. Nii et see on OK. See on OK, et helistada neile samu asju. 

Kui ma sind leida, ma olen lähed tahan teha midagi nagu teatada, et oleme leidnud n. Ja me lahkume, et kui kommentaar või pseudokoodi kood. Else, ja siin on Huvitav osa, mida ma tahan teha, kui aktiivse sõlme ei ole seal n, et ma hoolin? Kuidas saavutada järgmised? Kui mu sõrme Praegu on PTR ja see on osutades mis tahes Esimene on osutavad, kuidas ma liikuda mu sõrme Lisa järgmisel sõlme koodi? Noh, mis on riivsai oleme kavatse järgida antud juhul? Sihtrühm: [kuuldamatu]. DAVID J. Humala: Jah, järgmine. Nii et kui ma lähen tagasi oma kood siia, tõepoolest, ma olen läheb minna ja öelda, pointer, mis on vaid ajutine variable-- see imelik nimi, PTR, kuid see on nagu temp-- Ma lähen, et seada kursor võrdne iganes pointer on-- ja jälle, et see saab olema väike käru jaoks moment-- dot kõrval. Teisisõnu, ma lähen võtan sõrme, mis sihib seda sõlme siin ja ma ütlen, sa tead, mida, kui heita pilk järgmisele väljale ja liigutage oma sõrme mis iganes see osutavad. Ja see läheb korrata, korrata, korrata. Aga kui ei oma sõrme enam ei tee üldse midagi? Niipea, mida koodirida tunda? Sihtrühm: [kuuldamatu] DAVID J. Humala: Kui punkt samas osuti ei ole võrdne null. Mingil hetkel mu sõrm on kavatse olla vastakuti null ja ma realiseerida see on lõpuks see nimekiri. Nüüd on see väike hädavale lihtsuse. Selgub, et kuigi me lihtsalt õppinud seda dot märke struktuuridele, osuti ei struct. PTR on mis? Lihtsalt olla nitpicky. See on kursor sõlme. See ei ole sõlm ise. Kui mul ei olnud star siin, pointer absolutely-- see sõlm. See on nagu nädal üks deklaratsiooni muutuja, kuigi sõna "sõlm" on uus. 

Aga niipea, kui me võtame kasutusele star, see on nüüd kursor sõlme. Ja kahjuks ei saa kasutada dot märke pointer. Sa pead kasutama noole märke, mis silmatorkavalt, on esimene kord, iga tükk süntaks näeb intuitiivne. See paistab sõna otseses mõttes nool. Ja see on hea asi. Ja siin sõna otseses mõttes näeb välja nagu nool. Nii et ma arvan, et see la-- ma ei arvad, et ma üle-toimepanemise siin-- I arvan, et on viimane uus teos süntaksi me näeme. Ja õnneks on see tõepoolest natuke rohkem intuitiivne. 

Nüüd neile, kes võiks eelistada vana viisi, saate endiselt kasutada dot märke. Aga nagu iga esmaspäeval vestlus, me esimest korda vaja sinna minna, minna, et käsitleda, ja seejärel juurdepääsu valdkonnas. Nii et see on ka õige. Ja ausalt öeldes, see on natuke pedantne. Sa sõna otseses mõttes öelda, dereference osuti ja sinna minna. Seejärel haarata .n, valdkonnas nimetatakse n. Aga ausalt, keegi ei taha kirjutada või lugeda. Ja nii maailmas leiutatud noole märke, mis võrdub identsed, see on lihtsalt süntaktiline suhkur. Nii fancy viis öelda seda näeb parem välja, või tundub lihtsam. 

Nii et nüüd ma lähen tegema üks teine ​​asi. Ma ütlen "murda", kui olen leidis ta, et ma ei pea otsima seda. Kuid see on asja olemus otsingu funktsiooni. Aga see on palju lihtsam, et Lõpuks ei kõndida läbi kood. See on tõepoolest formaalne rakendamine otsingu tänapäeva jaotus kood. Julgen öelda, et insert ei ole eriti tore jalutada läbi visuaalselt, ega kustutada, isegi kuigi lõpuks päeval need taanduvad üsna lihtne heuristika. 

Nii et teeme seda. Kui sa mu tuju siin, ma tegin tuua hunnik stress pallid. Ma tõin hunnik numbreid. Ja kas me saada paar vabatahtlikud esindada 9, 17, 20, 22, 29 ja 34? Nii et sisuliselt kõik kes on täna siin. See oli üks, kaks, kolm, neli, viis, kuus inimest. Ja ma olen palutud go-- näha, ei üks taga tõstab oma käed. OK, üks, kaks, kolm, neli, five-- andke laadida balance-- kuus. OK, sa kuus tule üles. Meil on vaja teisi inimesi. Tõime extra stress pallid. Ja kui sa võiksid võtta hetk, joon endid lihtsalt nagu see pilt siin. 

Olgu. Vaatame, mis su nimi on? 

Sihtrühm: Andrew. 

DAVID J. Humala: Andrew, te arv 9. Meeldiv kohtuda. Palun. Sihtrühm: Jen. DAVID J. Humala: Jen. David. Number 17. Jah? 

Sihtrühm: ma olen Julia. 

DAVID J. Humala: Julia, David. Number 20. Sihtrühm: Christian. DAVID J. Humala: Christian, David. Number 22. Ja siis? 

Sihtrühm: JP. DAVID J. Humala: JP. Number 29. Nii et laske käia ja saada sisse-- Uh oh. Uh oh. Ooterežiim. 20. Kas kellelgi on SM? Sihtrühm: Mul Sharpie. DAVID J. Humala: Sul Sharpie? OK. Ja kas keegi on tükk paberit? Säästa loeng. Tule. Sihtrühm: Meil ​​on see. DAVID J. Humala: Me saime? Olgu, tänan. Siit me tuleme. Kas see on teie? Sa lihtsalt salvestada päev. Nii 29. Olgu. Ma valesti 29, kuid OK. Lase käia. Olgu, ma annan sulle Teie pen tagasi jõudma. Nii et meil on need inimesed siin. Teeme veel ühe. Gabe, sa tahad mängida Esimene element siin? Me vajame sind juhtida neid trahvi folks. Nii et 9, 17, 20, 22, sort 29. ja seejärel 34. Kas me kaotame keegi? Mul on 34. Kui tegin-- OK, kes tahab olla 34? OK, tule üles, 34. Olgu, seda saab väärt haripunkti. Mis su nimi on? 

Sihtrühm: Peter. 

DAVID J. Humala: Peter, tule üles. Olgu, siin on terve hunnik tippe. Iga kutid esindab üks neist ristküliku. Ja Gabe, veidi veider mees välja, moodustab esimene. Nii tema osuti on veidi väiksem ekraanile kui kõik teisedki. Ja sel juhul, iga oma vasakule käed läheb kas suunaga allapoole, mis esindavad null, nii lihtsalt puudumisel osuti või see saab olema suunaga at sõlme kõrval. 

Nii et kohe kui te kaunistavad endid nagu pildil siin, edasi minna ja punkt üksteist, koos Gabe eriti osutavad number 9 esindama nimekirja. OK, ja number 34, vasaku käega tuleks lihtsalt osutades põrandale. 

OK, nii et see on seotud nimekirja. Nii et see on stsenaarium küsimus. Ja tõepoolest, see on tüüpiline of klassiks et sa võiksid proovida lahendada koodiga. Tahad lõpuks sisestada uus element nimekirja. Sel juhul me ei kavatse proovida sisestades number 55. Aga seal saab olema mõnevõrra erinevat juhtumit. Ja tõepoolest, see saab olema üks big-picture takeaways siin on, Millised on erinevad juhtumid. Millised on erinevad, kui tingimused või oksad, et teie programm võib olla? 

Noh, number üritad insert, mida me teame nüüd, et 55, aga kui sa ei tea, ette, Julgen väita, kuulub vähemalt kolm võimalikke olukordi. Kus võiks uus element olla? Sihtrühm: Ja otsas või keskel. DAVID J. Humala: Lõpus sisse keskel või alguses. Nii et ma väita, seal on vähemalt kolm probleemid peame lahendama. Olgem valida, mida on võib-olla vaieldamatult kõige lihtsam üks, kus uus element kuulub alguses. Nii et ma lähen on kood üsna nagu otsing, mis ma kirjutasin. Ja ma lähen on PTR, mis Ma esindan oma sõrme, nagu tavaliselt. 

Ja pidage meeles, millist väärtust Kas me initsialiseerida 'p'? Nii et meil tuleb kõigepealt tühjaks esialgu. Aga mida me teeme, kui me olid sees meie otsingu funktsiooni? Seame see võrdub esimese, mis ei tähenda seda teed. Kui ma panen PTR võrdub esimene, mida peaks minu poolt tõesti juhtides? Õigus. Nii et kui Gabe ja ma ei kavatse võrdne väärtuste siin me peame nii punkti number 9. 

Nii et see oli alguses meie lugu. Ja nüüd see on lihtsalt arusaadav, kuigi süntaks on uus. Kontseptuaalselt on see lihtsalt lineaarset otsingut. Kas 55 on võrdne 9? Või pigem, ütleme, et alla 9. Kuna ma üritan nuputada, kuhu panna 55. Vähem kui 9, vähem kui 17 ja vähem kui 20, vähemalt 22, vähemalt 29, alla 34, no. Nüüd oleme puhul üks vähemalt kolm. 

Kui ma tahan, et lisada 55 siin, mida rida koodi on vaja saada täidetud? Kuidas see pilt Inimestel on vaja vahetada? Mida ma pean tegema minu vasak käsi? See peaks olema null esialgu sest ma olen lõpus nimekirja. Ja mis peaks juhtuma, siin Peter, see oli? Ta on ilmselt läheb punkt mulle. Nii et ma väita, seal on vähemalt kaks rida koodi proovi kood täna mis toimub rakendada seda stsenaariumi lisades 55 juures saba. Ja kas ma saaksin kellegi hop up ja lihtsalt esindavad 55? Olgu, sa oled uus 55. 

Mis nüüd, kui järgmine stsenaarium tuleb mööda, ja me tahame, et sisestada juures algab või juht nimekirjas? Ja mis sinu nimi, number 55? 

Sihtrühm: Jack. 

DAVID J. Humala: Jack? OK, meeldiv kohtuda. Tere tulemast pardale. Nüüd me ei kavatse sisestada, ütleme, number 5. Siin on teine ​​kui kolm tulime varem. Nii et kui 5 kuulub alguses, Vaatame, kuidas me seda teada. Ma initsialiseerida minu PTR kursor number 9 uuesti. Ja ma sain aru, oh, 5 on alla 9. Nii et määrata see pilt meile. Kelle käsi, Gabe või Taaveti või-- mis number 9 nime? 

Sihtrühm: Jen. 

DAVID J. Humala: Jen hands-- mida meie käed on vaja vahetada? OK, nii et Gabe punktid, mida nüüd? Mind. Olen uus sõlm. Nii et ma lihtsalt selline käik siin see visuaalselt. Ja vahepeal, mida ma rõhutada, et? Ikka, kui ma juhtides. Nii ongi. Nii lihtsalt tõesti üks rida koodi parandused selles konkreetses küsimuses, tundub. Olgu, see on hea. Ja kas keegi on kohatäide 5? Tule. Me saame teile järgmine kord. 

Olgu, nüüd-- ja Nagu kõrvale, nimed Ma ei tee selgesõnalise õiguse nüüd Paku pointer, eelkäija pointer ja uue pointer, mis on ainult eesnimedega Valimisse koodi viiteid või mu käed, mis on omamoodi suunaga ümber. Mis su nimi on? 

Sihtrühm: Christine. 

DAVID J. Humala: Christine. Tere tulemast pardale. Olgu, lähme kaaluma nüüd pisut tüütu stsenaariumi mille ma tahan lisada midagi 26 sellesse. 20? Mis? Need oled-- hea asi on see pen. Olgu, 20. Kui keegi võiks saada veel üks paber valmis igaks juhul-- eks. Oh, huvitav. Noh see on näide loeng viga. OK, siis millised on teie nimi oligi? Sihtrühm: Julia. DAVID J. Humala: Julia, saate pop välja ja teeskle, et sa olid kunagi olemas? OK, see ei juhtunud. Aitäh. Seega arvan, et me tahame lisada Julia sellesse seotud nimekirja. Ta on number 20. Ja muidugi on ta läheb kuuluvad juures begin-- ei viita juures veel midagi. Nii et teie käsi võib selline olla alla null või mõned prügi väärtus. Olgem öelda kiire lugu. Ma osutades number 5 seekord. Siis ma kontrollin 9. Siis ma saan vaadata 17. Siis ma saan vaadata 22. Ja ma saan aru, ooh, Julia peab minema enne 22. Mis siis peab juhtuma? Kelle käes on vaja vahetada? Julia, minu või-- mis su nimi oligi? 

Sihtrühm: Christian. 

DAVID J. Humala: Christian või? 

Sihtrühm: Andy. 

DAVID J. Humala: Andy. Christian või Andy? Andy peab käsk juures? Julia. Olgu. Nii Andy, sa tahad osutavad Julia? Kuid oodake minut. Loos seni Ma olen omamoodi üks eest, mis tähendab, et osuti on asi, mis on liigub läbi nimekirja. Me võib-olla nime Andy, aga pole muutuja nimega Andy. Ainuke muutuja meil on Esimene, kes esindab Gabe. 

Nii et see on tegelikult miks nii kaugele oleme ei vaja seda. Kuid nüüd ekraanil on rääkimata taas progn pointer. Nii et lubage mul olla selgesõnaline. Kui see on osuti, mul oli parem natuke arukam minu iteratsiooni. Kui sa ei pahanda, et ma lähen siit läbi uuesti, tuues siia, juhtides siin. Aga andke mulle progn pointer, eelkäija pointer, mis on liiki osutades element olin just. Nii et kui ma lähen siit, nüüd mu vasak käsi uuendused. Kui ma lähen siin mu vasak käsi uuendused. Ja nüüd ma ei ole mitte ainult viit element, mis läheb pärast Julia, Mul on veel viit Andy, element enne. Nii et teil on juurdepääs sisuliselt riivsai, kui soovite, kõik nõutavad osuti. 

Nii et kui ma osutades Andy ja ma ka osutades at Christian, kelle käed Nüüd tuleks märkida mujal? Nii Andy saab nüüd osutavad Julia. Julia saab nüüd juhtida at Christian. Sest ta saab kopeerida oma parema käe pointer. Ja mis tegelikult paneb sind tagasi see koht siin. Nii lühike, kuigi see viib meid omamoodi igavesti tegelikult uuendada seotud nimekirja, mõistma et toimingud on suhteliselt lihtne. See on üks, kaks, kolm rida koodi lõpuks. Aga pakitud ümber nende rida koodi eeldatavasti on natuke loogikat, et tõhusalt küsib küsimuse, et kus me oleme? Kas me oleme alguses, keskel või lõpus? 

Nüüd on kindlasti mõne teise operatsioonide võiksime rakendada. Ja need pildid siin lihtsalt kirjeldada mida tegime inimestega. Aga eemaldamist? Kui ma tahan näiteks eemaldage number 34 või 55, Ma võin olla sama koodi, aga ma lähen vaja üks või kaks sammu. Sest see, mis uudist? Kui ma eemaldan keegi lõpus, nagu number 55 ja siis 34, Mis on ka muuta, kui ma seda teen? Pean ei evict-- mis su nimi oligi? 

Sihtrühm: Jack. 

DAVID J. Humala: Jack. Mul on mitte ainult evict-- tasuta Jack, nii sõna otseses mõttes helistada tasuta Jack, või vähemalt pointer seal liiga, kuid nüüd mida peaks muutma, Peter? Tema käsi parem alustada suunaga allapoole. Sest niipea, kui ma helistada tasuta Jack, kui Peter on ikka osutades Jack ja seetõttu ma hoida liiklevad nimekirja ja juurdepääs sellele pointer, see on kui meie vana sõber segmenteerimine viga võib tegelikult algama. Kuna me oleme andnud mälu tagasi Jack. 

Võite viibida seal kohmakalt hetkeks. Kuna meil on ainult paar lõpptoimingute kaaluda. Pea eemaldamine loetelu, või alguse-- ja see on natuke tüütu. Sest meil on teada, et Gabe on selline eriline selles programmis. Sest tõepoolest, ta on oma pointer. Ta ei ole lihtsalt on osutanud, nagu peaaegu kõik teisedki siin. 

Nii et kui juht nimekiri on eemaldatud, kelle kätes on vaja vahetada nüüd? Mis su nimi oligi? 

Sihtrühm: Christine. 

DAVID J. Humala: Ma olen kohutav at nimesid, ilmselt. Nii Christine ja Gabe, kelle käed on vaja muuta kui me püüame eemaldada Christine, number 5, pildilt? OK, teeme siis Gabe. Gabe läheb punkt, arvatavasti on number 9. Aga mis edasi juhtub? Sihtrühm: Christine peaks olema null [kuuldamatu]. DAVID J. Humala: OK, me peaks ilmselt make-- kuulsin "null" kusagil. Sihtrühm: Null ja vaba teda. DAVID J. Humala: NULL mida? Sihtrühm: Null ja vaba teda. DAVID J. Humala: Null ja vaba teda. Nii et see on väga lihtne. Ja see on suurepärane, et sa oled nüüd sorteeri Kasvava sinna ei kuulu. Sest sa oled olnud lahtiseotud nimekirja. Olete edukalt toimunud orvuks nimekirjast. Ja nii oli meil parem helistada tasuta nüüd Christine andma, et mälu tagasi. Muidu iga kord, kui me kustutada sõlme nimekirjast me võiks muuta nimekiri lühem, kuid tegelikult väheneb suurus mälu. Ja kui me hoida lisades ja Lisades, lisades asjad loendisse minu arvuti võib saada aeglasem ja aeglasem ja aeglasem, sest ma otsa mälu, isegi kui ma ei ole tegelikult kasutades Christine baiti mälu enam. 

Nii lõpuks on teisi stsenaariume, muidugi-- eemaldamine keskel, eemaldamine aasta lõpus, kui me nägime. Aga huvitav Nüüd on küsimus saab kaaluda täpselt Mis on käigu aeg. Nii et mitte ainult sa saad hoida oma paberitükke, kui Gabe, sa ei pahanda, andes kõik stressi pall. Tänan sind nii palju, et meie seotud nimekirja Vabatahtlike siin, kui sa saaksid. 

[APPLAUSE] 

DAVID J. Humala: Olgu. Nii paar analüütiline küsimused siis, kui suutsin. Me oleme näinud seda muutma enne, suur O ja omega, ülemised piirid ja alumised piirid sõiduaega mõne algoritmi. Nii et olgem kaaluma ainult paar küsimust. 

Üks, ja me ütlesime seda enne, mis töötab aeg otsida nimekirja nii suur O? Mis on ülemine piir on pooleli aega otsides seotud nimekirja mida rakendatakse meie vabatahtlikele siin? See on suur O n lineaarne. Sest halvimal juhul element, nagu 55, me võiks otsin võiks olla, kui Jack oli kõik kuidagi lõpuni. Ja kahjuks erinevalt array me ei saa fancy seekord. Kuigi kõik meie inimesed olid sorteeritud väike elemente, 5, kõik viis kuni suurem osa, 55, mis on tavaliselt hea. Aga mida see eeldus enam ei võimalda meil teha? Sihtrühm: [kuuldamatu] DAVID J. Humala: Ütle uuesti? Sihtrühm: Muutmälu. DAVID J. Humala: Muutmälu. Ja omakorda see tähendab, et me ei ole kasuta enam nõrk nulle, intuitsiooni, ja ilmselget kasutades binaarne Otsige ja jaga ja valitse. Sest kuigi me inimestele võib ilmselt näha, et Andy ja Christian olid umbes keskel nimekirja Me teame ainult, et kui arvuti koorides nimekirja algusest. Nii et me oleme loobunud, et muutmälu. 

Nii suur O n on praegu üleval seotud meie search aega. Aga omega meie search? Mis alampiiri otsimine mõnda number selles loetelus? Sihtrühm: [kuuldamatu] DAVID J. Humala: Ütle uuesti? Sihtrühm: One. DAVID J. Humala: One. Nii konstantse ajaga. Parimal juhul, Christine on tõepoolest alguses nimekirja. Ja me otsime number 5, nii et me ta leidsime. Nii et ei ole suur asi. Aga ta ju olema loetelu alguses käesolevas asjas. Aga midagi sellist Kustuta? Mis siis, kui soovid kustutada element? Milline on ülemise ja alumise tõkke kustutamise kohta midagi, mis on seotud List? Sihtrühm: [kuuldamatu] DAVID J. Humala: Ütle uuesti? Sihtrühm: n. DAVID J. Humala: n on tõepoolest ülemise. Sest halvimal juhul püüame kustutada Jack, nagu me tegime. Ta on kogu tee lõpus. Viib meid igavesti, või n samme teda leida. Nii et see on ülemine piir. See on lineaarne, kindlasti. Ja parimal juhul sõiduaega või alumised piirid on parimal juhul oleks konstantne aeg. Sest äkki proovite kustutada Christine ja me lihtsalt veab ta alguses. Nüüd oota. Gabe oli ka alguses, ja meil oli ka uuendada Gabe. Nii et see ei olnud vaid üks samm. Nii et see on tõepoolest konstantne aega, parimal juhul eemaldada väikseima elemendi? See on, kuigi see võib olla kaks, kolm või isegi 100 rida koodi, kas see on sama palju read, mitte mõnes tsüklina ja sõltumatu suurus nimekirja, absoluutselt. Kustutamine element alguses nimekirja isegi kui me peame tegelema Gabe, on ikka konstantne aega. 

Nii et see tundub suur samm tagasi. Ja milline ajaraiskamine siis, kui nädalas ühe ja nädalas null me ei ole mitte ainult pseudokoodi kood kuid tegelikku koodi rakendada midagi, mis on samamoodi base n, või logige pigem n, base 2 poolest sõiduaega. Nii et miks kuradit oleks tahame alustada kasutades midagi seotud nimekirja? Jah. 

Sihtrühm: Nii saate lisada elemendid massiivi. DAVID J. Humala: nii saate lisada elemente massiivi. Ja ka see on temaatilised. Ja me näeme jätkuvalt see on see kompromiss, palju nagu me oleme näinud kompromissile merge sort. Me võiks tõesti kiirendada otsida või sortimine, pigem kui me kulutame veidi rohkem ruumi ning on täiendav patakas mälu või massiivi merge sort. Aga me kulutame rohkem ruumi, kuid me aega säästa. Sel juhul me oleme loobuvad aega, kuid me oleme saada paindlikkust, dünaamilisust kui soovite, mis on vaieldamatult positiivne omadus. 

Jälgime ka kulutada ruumi. Mis mõttes on seotud list kallim nii ruumi kui massiivi? Kus on lisaruumi tuleb? Jah? 

Sihtrühm: [kuuldamatu] pointer. 

DAVID J. Humala: Jah, me Samuti on osuti. Nii et see on minorly tüütu et enam olen Ma ladustamiseks lihtsalt int esindama int. Ma hoidmiseks int ja osutiga, mis on samuti 32 bitti. Nii, et ma sõna otseses mõttes kahekordistunud palju ruumi vahel. Nii et see on kompromiss, kuid see on juhul, int. Oletame, et sa ei ole hoidmiseks int, kuid arvan, et kõik need ristkülikud või iga nende inimeste esindas Ühesõnaga, ingliskeelne sõna, mis võib olla viis märki, 10 märki, võib-olla isegi rohkem. Siis lisades vaid 32 rohkem bitte võib olla vähem tähtis. 

Mida teha, kui iga üliõpilastele tutvustamise olid sõna otseses mõttes õpilane structs et on nimed ja majad ja võibolla telefoninumbreid ja Twitter käepidemed ja sarnased. Nii et kõik väljad hakkasime räägime teisel päeval, palju vähem suur asi, kui meie tippe saada rohkem huvitavaid ja suur veeta, eh, täiendav osuti lihtsalt ühendada neid koos. Aga tõesti, see on kompromiss. Ja tõepoolest, kood on keerulisem, nagu te peate vaata koorides kaudu et konkreetne näide. Aga mis siis, kui oli mõned Püha Graal siin. Mis siis, kui me ei võta samm tahapoole, kuid tohutu samm edasi ja rakendada info struktuuri, mille kaudu me võib leida elemente nagu Jack või Christine või mis tahes muud osad Selles massiivi tõsi konstantset aega? Otsing on konstantne. Kustuta konstantne. Sisesta on konstantne. Kõik need toimingud on konstantne. See oleks meie Püha Graal. Ja see on koht, kus me kiirenemist järgmine kord. Näeme siis.