[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.