>> SPEAKER 1: Olgu, me oleme tagasi.
Tere tulemast CS50.
See on nädala lõpuks seitse.
Nii meelde, et viimane kord, hakkasime vaadates veidi keerukamate
andmestruktuurid.
Kuna siiani on kõik meil oli tõesti meie käsutuses, oli see massiiv.
>> Aga enne kui me visake massiivi ei kõik mis huvitav, mis tõepoolest
tegelikult on, milline on mõned plussid seda lihtsat andmed
struktuur seni?
Mis on see hea?
Nii palju, kui me oleme näinud?
Mis sul on?
Mitte midagi.
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Mis see on?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1. Fikseeritud suurusega.
OK, nii et miks on fikseeritud suurus hea küll?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: OK, nii et see on tõhus selles mõttes, et saate eraldada
fikseeritud summa ruumi, mis loodetavasti Just nii palju
ruumi, kui soovite.
Nii et võib olla absoluutselt pluss.
>> Mis on veel kuni pool massiivi?
Jah?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: All - sorry?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Kõik lahtrid mälu või üksteise kõrval.
Ja see on kasulik - miks?
See on täiesti tõsi.
Aga kuidas me saame kasutada, et tõde?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Täpselt, saame jälgida kus kõik on lihtsalt teada
üks aadress, so aadressi Esimene bait et patakas mälu.
Või juhul, kui string, aadress esimese
char selles string.
Ja sealt leiame stringi lõpuni.
Me võime leida teine ​​element, Kolmas element, ja nii edasi.
>> Ja nii fancy viis kirjeldada, et omadus on, et massiivid meile
muutmälu.
Lihtsalt abil nurksulg märke ja number, saab hüpata
konkreetne element massiivi pidevas ajal suur O
ühe, nii rääkida.
>> Aga seal on olnud mõned varjuküljed.
Mis array ei tee väga lihtsalt?
Mis see ei ole hea?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Mis see on?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Muutuvad suurusega.
Nii varjuküljed massiiv on täpselt vastupidine sellele, mida
plussid on.
Nii et üks varjuküljed on et see on fikseeritud suurus.
Nii et te ei saa tõesti kasvada.
Võite suunata suurem patakas mälu ja seejärel liikuda vana elemendid
uude massiivi.
Ja siis tasuta vana massiivi jaoks Näiteks kasutades malloc või sarnane
funktsiooni nimetatakse RealLOC, mis reallocates mälu.
>> RealLOC, nagu kõrvale, üritab anda sulle mälu, mis on kõrval massiivi
mis teil juba on.
Aga see võib liigutada asju ümber kokku.
Aga lühidalt öeldes, et see on kallis, eks?
Sest kui sul on patakas mälu Selle suurus, kuid sa tõesti tahad ühe
Selle suurus ja soovite säilitada originaal elemente, mida
ligikaudu lineaarne aeg kopeerimise protsess mis vajab juhtuda
vana massiivi uus.
Ja reaalsus on see, paludes operatsioonisüsteemi süsteem uuesti ja uuesti ja
jälle suur tükkideks mälu saab alustada teile maksma veidi aega samuti.
Nii et see on nii õnnistus ja needus varjata asjaolu, et need massiivid
on fikseeritud suurus.
Aga kui me võtame kasutusele selle asemel midagi nagu see, mis me kutsusime seotud
nimekirja, saame mõned plussid ja mõned varjuküljed ka siin.
>> Niisiis, mis on seotud nimekirja on lihtsalt andmed struktuur, mis koosneb C structs selles
juhul, kui struktuure, mäletate, on lihtsalt konteinerisse ühe või mitme konkreetse
tüüpi muutujaid.
Sellisel juhul mida teha andmetüübid olevat sees struct et
Viimasel ajal oleme kutsutud sõlm?
Kõik need ristkülikud on sõlme.
Ja iga väike ristkülik sees on andmetüübi.
Millised me öelda nad olid esmaspäeval?
Jah?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: muutuv ja pointer, või Täpsemalt int, n,
ja osuti allosas.
Mõlemad neist juhtub olema 32 bitti, kell vähemalt arvuti niimoodi CS50
Appliance ja nii nad tõmmatud võrdselt suurusega.
>> Niisiis, mida kasutate pointer kuigi näiliselt?
Miks lisada see nool nüüd kui massiivid olid nii kena ja puhas ja lihtne?
Mis on pointer jaoks teed meile igas need sõlmed?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Täpselt.
Ta räägib sulle, kus Järgmise üks on.
Nii et ma omamoodi kasutada analoogiat kasutades niit sortida
niit need sõlmed kokku.
Ja see on täpselt see, mida me teeme koos suunanäitajaks, sest iga
tükkideks mälu võib olla või mitte olla terviklik, seljad tagasi
sees RAM, sest iga kord, kui helistada malloc öeldes mulle piisavalt
baiti uus sõlm, võib see siin olla või võib olla siin.
Võib-olla on siin.
Sa lihtsalt ei tea.
>> Kuid kasutades lähtekohad aadressid need sõlmed, saate õmblema neid
kokku viisil, mis näeb visuaalselt nagu nimekirjas, isegi kui need asjad on
kõik laiali kogu oma ühe või oma kaks või oma neli gigabaiti operatiivmälu
sees oma arvutist.
>> Nii negatiivsed, siis on seotud nimekirja on mis?
Mis on hind, mida me oleme ilmselt maksavad?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Rohkem ruumi, eks?
Me oleme selles asjas kahekordistunud summa ruumi, sest oleme läinud
32 bitti iga sõlme iga int, nii et nüüd 64 bitti, sest peame
hoida umbes pointer samuti.
Sa saad rohkem efektiivsust kui oma struktuure on suurem kui see lihtne asi.
Kui sa tegelikult üliõpilane sees mis on paari stringe
nimi ja maja, võibolla ID number, äkki mõned muudes valdkondades kokku.
>> Nii et kui sul on piisavalt suur, struktuure, siis võibolla maksumus osuti on
mitte nii suur asi.
See on natuke nurgas puhul selles me ladustamiseks selline lihtne primitiivne
sisemus seotud nimekirja.
Aga point on sama.
Sa oled kindlasti kulutusi rohkem mälu, kuid sa saad
paindlikkust.
Sest nüüd, kui ma tahan lisada element alguses see nimekiri,
Mul on eraldada uus sõlm.
Ja ma pean lihtsalt ajakohastada neid nooled millegipärast just liikuvate
mõned näpunäited ümber.
>> Kui ma tahan lisada midagi arvesse Keset nimekirja, ma ei pea
push kõik kõrvale nagu me tegime nädalat varem meie vabatahtlikke, kes
esindatud massiivi.
Võin lihtsalt eraldada uus sõlm ja siis lihtsalt juhtida nooltega
erinevates suundades, sest see ei peavad jääma tegelik
mälu tõsi liin nagu ma olen juhtinud see siin ekraanil.
>> Ja siis lõpuks, kui soovite sisestada midagi lõpus nimekirja, see on
isegi lihtsam.
See on omamoodi omavoliline märke, kuid 34 on pointer, peaksin arvama.
Mis on väärtus selle osuti kõige tõenäoliselt välja omamoodi nagu vana
kooli antenn on?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: See on ilmselt null.
Ja tõepoolest see on üks autori esindatuse null.
Ja see on null, sest sa absoluutselt vaja teada, kust lõpuks lingitud
Nimekiri on, muidu te ei hoia järgmine ja järel ja pärast need nooled
mõned prügi väärtus.
Nii null, tähendab, et seal ei ole rohkem tippe paremal number 34,
käesolevas asjas.
>> Seega teeme ettepaneku, et saame rakendada Selle sõlme kood.
Ja me oleme näinud sedalaadi süntaks enne.
Typedef lihtsalt määratleb uut tüüpi kohta meid, annab meile sünonüüm nagu
string oli char *.
Antud juhul see läheb meile stenografisti märke nii et struct sõlme
võib selle asemel lihtsalt kirjutada sõlme, mis on palju puhtam.
See on palju vähem verbose.
>> Toas sõlm on ilmselt int nimetatakse n ja seejärel struct tipp *
mis tähendab täpselt seda, mida me tahtsime nooli tähendab, kursor teise
sõlme täpselt sama andmetüüp.
Ja ma teen ettepaneku, et me võiksime rakendada otsingu funktsiooni niimoodi, mis on
Esmapilgul võib tunduda, veidi keeruline.
Aga vaatame seda konteksti.
>> Lubage mul minna üle seadme siin.
Lubage mul avada fail nimega nimekiri null dot h.
Ja see sisaldab ainult määratlus me nägin just hetk tagasi selle andmed
tüüp kutsus sõlme.
Nii et me panime seda arvesse dot h faili.
>> Ja kõrvale, kuigi see programmi, mida parasjagu näha on
ei ole kõik nii keeruline, et see on tõepoolest konventsiooni kui kirjalikult programmi
asjad nagu andmetüübid, pull konstandid mõnikord sees oma
päisefailist ja mitte tingimata oma C fail, kindlasti, kui teie
programme saada suuremaks ja suuremaks, nii et sa tead, kust otsida nii
dokumentatsioon mõningatel juhtudel või jaoks põhitõdesid nagu see,
määratlus teatud tüüpi.
>> Kui ma nüüd avada nimekiri null dot c, märkate mõningaid asju.
See sisaldab vähe header faili, kõige millest me oleme näinud.
See hõlmab oma header fail.
>> Ja kõrvale, miks see on topelt tsitaadid siin, mitte nurga
Sulgudes on joon, mis Olen rõhutanud seal?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Jah, nii see on kohalik fail.
Nii et kui see on kohalik fail oma siin on line 15, näiteks, saate kasutada
jutumärkide asemel Euroopa noolsulge.
>> Nüüd on see omamoodi huvitav.
Pange tähele, et ma olen kuulutanud maailma muutuja selles programmis on line 18
kutsutud esimene, mille idee seisneb selles on läheb osuti esimesse
sõlm minu ahelloend, ja ma olen käivitub see tühjaks, sest ma olen
ei eraldatud ühtegi tegelikku sõlmede veel.
>> Nii et see esindab, piltlikult, mida me nägin hetk tagasi pilt
et osuti palju vasakul pool.
Nii kohe, et pointer ei ole noolt.
Selle asemel on lihtsalt null.
Aga see tähendab, milline saab olema aadress esimesed
sõlme selles loetelus.
Nii et ma olen rakendanud on ülemaailmne sest, nagu te näete, kõik see
Programm ei elus on rakendada seotud nimekirja minu jaoks.
>> Nüüd on mul mõned prototüübid siin.
Ma otsustasin, et rakendada funktsioone, nagu kustutamine, lisamine, otsimine ja
läbipääsusüsteemid -
viimane lihtsalt on kõndida üle nimekirja, prindib selle elemente.
Ja nüüd siin on mu peamine rutiinist.
Ja me ei veedavad liiga palju aega Nende sest see on omamoodi loodetavasti
vana müts nüüd.
>> Ma lähen tegema järgmised kui kasutaja teeb.
Nii et üks, ma lähen välja printida läbi selle menüü.
Ja ma olen vormindatud see nagu puhtalt kui suutsin.
Kui kasutaja liigid üks, mis tähendab, nad tahavad kustutada midagi.
Kui kasutaja liigid kaks, mis tähendab, et nad tahavad, et lisada midagi.
Ja nii edasi.
Ma lähen siis küsi siis käsk.
Ja siis ma lähen kasutada GetInt.
>> Nii et see on tõesti lihtne menuing liides, kus sa lihtsalt tüüp
number kaardistamise üks nende käske.
Ja nüüd on mul kena puhas switch kinnitus, et läheb sisse lülitada
olenemata kasutaja sisestatud sisse
Ja kui nad kirjutada üks, siis ma helistada kustutada ja murda.
Kui nad kirjutasid kaks, ma helistada sisestada ja murda.
>> Ja nüüd märkate Olen panna iga Nende ühel ja samal joonel.
See on vaid stiililine otsus.
Tavaliselt oleme näinud midagi niimoodi.
Aga ma otsustasin, ausalt, minu programmi Vaatasin veel loetav, sest
see oli ainult neli juhtumit lihtsalt loetleda see niimoodi.
Täiesti õigustatud kasutamist stiilis.
Ja ma teen seda nii kaua, kui kasutaja ei ole kirjutatud null, mida ma
otsustas tähendab nad soovivad loobuda.
>> Nüüd teate, mida ma olen teeme siin.
Ma lähen, et vabastada nimekiri ilmselt.
Aga rohkem sellest vaid hetk.
Vaatame kõigepealt käivitada see programm.
Nii et lubage mul teha suurem terminal akna dot kaldkriipsuga nimekiri 0.
Ma lähen edasi minna ja sisestada poolt kirjutades kaks, number nagu 50, ja nüüd
näete nimekiri on nüüd 50.
Ja minu tekst lihtsalt kerida natuke.
Nüüd teate, kui loend sisaldab number 50.
>> Teeme veel lisada, võttes kaks.
Olgem kirjuta number nagu üks.
Nimekiri on nüüd üks, millele järgneb 50.
Nii et see on lihtsalt tekstiline esitus nimekirja.
Ja olgem lisada veel üks number nagu number 42, mis on loodetavasti
läheb lõpuks keskel, sest see programm eriti kehvasti see
elemente nagu ta lisab neid.
Nii et meil on see.
Super lihtne programm, mis võiks absoluutselt on kasutada massiivi, aga ma
juhtub olema, kasutades seotud nimekirja lihtsalt, et ma saaks dünaamiliselt
kasvab ja kahaneb see.
>> Võtame pilk otsinguks, kui ma käivitada käsk kolm, ma tahan, et otsida
, ütleme, number 43.
Ja midagi oli ilmselt leidis, sest ma sain tagasi mingit vastust.
Teeme seda uuesti.
Otsing.
Otsime 50 või pigem otsida 42, mis on kena
veidi peenem tähendus.
Ja ma leidsin elu mõtte seal.
Number 42, kui te ei tea, viide, Google seda.
Hea küll.
Mis siis on see programm minu heaks teinud?
See on lihtsalt võimaldanud mul sisestada seega kaugelt ja otsida elemente.
>> Lähme edasi, siis, et et funktsioon me pilgu
Esmaspäeval nagu teaser.
Nii et see ülesanne, ma väita, otsingud element nimekirjas esimesel
üks, mis sunnib kasutaja ja siis helistades GetInt saada tegelik int
, mida soovite otsida.
>> Siis teate seda.
Ma lähen luua ajutise muutuja vastavalt 188 kutsutud pointer -
PTR -
võinuks see midagi.
Ja see on kursor sõlme sest ma ütlesin sõlme * seal.
Ja ma käivitumist see olema võrdne esimene nii et ma tegelikult olema minu
sõrme, nii et rääkida, on väga esimene element nimekirjas.
Nii et kui mu parem käsi siin on PTR Ma olen juhtides samal asi et esimene
on osutavad.
>> Nüüd tagasi kood, mis juhtub järgmisena -
see on ühine paradigma kui iterating üle struktuur nagu
seotud nimekirja.
Ma lähen tegema ajal järgmisi osuti ei ole võrdne null Niisiis, kui
minu sõrm ei osutades mõned null väärtus, kui osuti nool n võrdub n.
Me märkad esimesena, et n on mis kasutaja tipitud kohta GetInts helistada siin.
>> Ja pointer nool n tähendab mida?
Noh, kui me tagasi minna pilt siin kui mul on sõrme osutavad
et esimese sõlme sisaldav üheksa, nool tähendab sisuliselt minema, et
sõlm ja haarata väärtus asukoha n, sel juhul andmeväljale nimetatakse n.
>> Nagu kõrvale - ja me nägime seda paar nädalat tagasi, kui keegi küsis -
Selle süntaks on uus, kuid see ei ole annab meile volitused, et me
ei ole veel.
Mis oli selle fraasi kasutamisega võrdväärset dot märke ja star paar
nädalat tagasi, kui me kooritud tagasi see kiht veidi enneaegselt?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Just, see oli täht, ja siis oli star dot n, kus
sulud siia, mis näeb välja, Ausalt, ma arvan, et palju
rohkem segasena lugeda.
Aga täht pointer, nagu alati, vahendid sinna minna.
Ja kui sa oled seal, milliseid andmeid valdkonnas sa tahad pääseda?
Noh te kasutate dot märke juurde structs andmeväljale ja ma
konkreetselt tahad n.
>> Ausalt, ma väidan seda on lihtsalt raskem lugeda.
See on raskem meeles pidada, kui ei sulgudes minna,
täht ja kõik see.
Nii maailma vastu mõned süntaktiline suhkur, nii rääkida.
Just seksikas viis öelda, see on samaväärne, ja
ehk rohkem intuitiivne.
Kui osuti on tõepoolest pointer, nool märke viisil sinna minna ja leida
valdkonnas sel juhul nimetatakse n.
>> Nii et kui ma leian ta, teate, mida ma teen.
Ma lihtsalt välja printida, leidsin protsenti i, kõrvaldamine on raha, et int.
Kutsun magada üks teine ​​lihtsalt selline Pauside asjad ekraanil
anda kasutajale teine ​​absorbeerida mis just juhtus.
Ja siis ma murda.
Muidu ma pean tegema?
Ma värskendada kursor võrdne pointer noolt.
>> Nii lihtsalt, et oleks selge, see tähendab, minna seal, kasutades minu vana kooli märke.
Niisiis tähendab see lihtsalt seda, et minna ükskõik olete osutades, mis on väga
Esimesel juhul on Ma osutades struct üheksa ta.
Nii et ma olen käinud seal.
Ja siis dot märke tähendab, saada väärtus järgmine.
>> Kuid raha, kuigi see on koostatud kui kitsas, on lihtsalt number.
See on numbriline aadress.
Nii et see üks rida koodi, kas kirjutatud niimoodi, rohkem segasena
viis, või sellist, pisut rohkem intuitiivne viis, tähendab lihtsalt liikuda mu käsi
alates esimese sõlme kõrval üks, ja siis järgmine ja siis
kõrval üks, ja nii edasi.
>> Nii et me ei tegele muu rakendusi lisada ja kustutada
ja läbipääsusüsteemid, kaks esimest mis on üsna seotud.
Ja ma arvan, et see on üsna lihtne saada kaduma, kui teed seda suuliselt.
Aga mida me teha saame, on siin proovige teha kindlaks, kuidas
parim teha seda visuaalselt.
Kuna ma teen ettepaneku, et kui me soovite lisada elemendid käesolevasse
olemasolev loetelu, mis on viis tegurit -
9, 17, 22, 26 ja 33 -
kui ma ei kavatse rakendada seda kood, mul on vaja mõelda, kuidas edasi minna
seda teed.
>> Ja ma teen ettepaneku, võttes lapse sammud kusjuures, sel juhul ma mõtlen, mis on
võimalikke stsenaariume, et me võib tekkida üldiselt?
Rakendamisel infolehest seotud nimekirja, see lihtsalt juhtub olema
konkreetne näide suurus viis.
Aga kui sa tahad sisestada number, nagu öelda number üks, ja
säilitades sorteeritud et vajaduse ilmselt ei number üks pea
mine selle konkreetse näite?
Nagu alguses.
>> Aga mis on huvitav on see, et kui soovite lisada ühe sellesse
nimekiri, mida erilist osuti peab ajakohastada ilmselt?
Esimene.
Nii et ma väidan, et see on esimene juhtum et me võiksite kaaluda,
stsenaarium hõlmab lisades juures loetelu alguses.
>> Olgem sikutama off ehk kui lihtne või isegi lihtsam juhul suhteliselt.
Oletame, tahan lisada number 35 in sorteeritud järjekorras.
See ilmselt kuulub sinna.
Mis siis osuti ilmselt läheb tuleb ajakohastada, et stsenaarium?
34 pointer muutub mitte null kuid aadress struct
sisaldavad number 35.
Nii et juhul kaks.
Nii juba, ma olen omamoodi Kvantimisplokk kui palju tööd mul teha siin.
>> Ja lõpuks, selge keskel puhul on tõepoolest, keset, kui tahan
sisestada midagi öelda 23, mis läheb vahel 23 ja 26, kuid
nüüd asju natuke rohkem kaasatud, sest mida
suunanäitajaks tuleb välja vahetada?
Nii 22 ilmselt tuleb muuta sest ta ei saa osutada 26 enam.
Ta peab käsk uus sõlm, et Võtan eraldada helistades
malloc või mõnda samaväärset.
>> Aga siis ma ka vaja, et uus sõlm, 23 Sellisel juhul on selle osuti
osutades kellele?
26.
Ja seal saab olema tehetejärjekord siin.
Sest kui ma teen seda rumalalt ja ma näiteks start alguses
nimekirja ning minu eesmärk on lisada 23.
Ja ma saan vaadata, kas see kuulub Siin lähedal üheksa?
Ei.
Kas see kuulub siin kõrval 17?
Ei.
Kas see kuulub siin kõrval 22?
Jah.
>> Nüüd, kui ma olen rumal siin, ja mitte mõtlemine see läbi, ma võin
eraldada minu uus sõlm 23.
Ma võiks uuendada pointer sõlme nimetatakse 22, juhtides
see on uus sõlm.
Ja mis ma siis pean uuendama uus sõlm osuti olema?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Täpselt.
Osutades 26.
Aga kurat võtaks, kui ma ei ole juba uuendada 22 pointer juhtida seda meest, ja
nüüd mul on orvud, ülejäänud nimekirja, nii rääkida.
Nii et operatsioonide siin saab olema oluline.
>> Selleks võiks ma varastama ütleme, kuus vabatahtlikku.
Ja vaatame, kas me saame seda teha visuaalselt asemel kood tark.
Ja meil on mõned armas stress pallid teile täna.
OK, kuidas üks, kaks, on tagasi - on lõpuks olemas.
kolm, neli, teie mõlema poisid lõpuks.
Ja viis, kuus.
Muidugi.
Viis ja kuus.
Olgu ja me tuleme teiega järgmine kord.
Olgu, tulge siia.
>> Olgu, kuna sa oled siin esimene, sa tahaksid olla üks kohmakalt
Google Klaas here?
Olgu nii, OK, klaas, salvestada video.
OK, sa oled hea minna.
>> Olgu, kui te ei tule siin olen eelnevalt ettevalmistatud
mõned numbrid.
Olgu, tule siia.
Ja miks sa ei lähe natuke edasi niimoodi.
Ja vaatame, mis su nimi on, Google Glass?
>> Üliõpilane: Ben.
>> SPEAKER 1: Ben?
OK, Ben, siis esimene sõna otseses mõttes.
Nii et me ei kavatse saata et etapi lõpus.
Olgu, ja teie nimi on?
>> Üliõpilane: Jason.
>> SPEAKER 1: Jason, OK teid olema number üheksa.
Nii et kui soovite jälgida Ben niimoodi.
>> Üliõpilane: Jill.
>> SPEAKER 1: Jill, sa lähed, et olla 17, mis siis, kui ma seda teinud veel
arukalt, oleksin alustas teises otsas.
Sa minna nii.
22.
Ja teie olete?
>> Üliõpilane: Mary.
>> SPEAKER 1: Mary, on sul 22.
Ja teie nimi on?
>> Üliõpilane: Chris.
>> SPEAKER 1: Chris, sa pead olema 26.
Ja siis lõpuks.
>> Üliõpilane: Diana.
>> SPEAKER 1: Diana, sa pead olema 34.
Nii et tulge siia.
>> Olgu, nii täiuslik järjestatud Tellimiseks juba.
Ja olgem minna ja teha seda nii et me saame tegelikult -
Ben oled lihtsalt selline vaadates viidud kusagil seal.
OK, nii et lähme edasi ja kujutada seda kasutada relvi, palju nagu ma olin, täpselt,
mis toimub.
Nii et laske käia ja andke iseendid suu või kaks vahel ise.
Ja minna ja juhtida ühe käega kes sa tuleks osutades
põhinevad.
Ja kui sa oled null lihtsalt juhtida otse alla põrandale.
OK, nii hea.
>> Nüüd on meil seotud nimekirja, ja lase mind ettepaneku, et ma mängida rolli
PTR, nii et ma ei viitsinud kes selle ümber.
Ja siis - keegi loll leping - võite helistada see midagi, mida soovite -
eelkäija pointer, pred pointer -
see on lihtsalt hüüdnimi andsime sisse meie proovi koodi mu vasak käsi.
Teisest küljest, mis saab olema hoida arvet, kes on kes
järgmised stsenaariumid.
>> Nii oletame, esiteks tahan sikutama off et esimene näide paigaldamisel öelda
20. osa loetellu.
Nii et ma vajan kedagi, kes kehastavad number 20 juures.
Nii et ma vaja malloc keegi saalist.
Tule üles.
Mis su nimi on?
>> Üliõpilane: Brian.
>> SPEAKER 1: Brian, eks, et sa on sõlm, mis sisaldab 20.
Olgu, tule siia.
Ja loomulikult, kui ei Brian kuuluvad?
Niisiis, keset - tegelikult, oodake minut.
Me teeme seda rikkis.
Me teeme seda palju raskem kui see peaks olema esimene.
OK, me läheme tasuta Brian ja RealLOC Brian kui viis.
>> OK, nii et nüüd me tahame lisada Brian kui viis.
Nii tule siia kõrvale Ben hetkeks.
Ja sa võid arvatavasti öelda kus see lugu läheb.
Kuid olgem hoolikalt mõelda tehetejärjekord.
Ja see on täpselt see visuaalne et läheb rivistama
selle proovi kood.
Nii et siin ma olen PTR osutades esialgu mitte Ben iseenesest, kuid mis iganes
Väärtustame ta sisaldab, mis antud juhul on - mis su nimi oligi?
>> Üliõpilane: Jason.
>> SPEAKER 1: Jason, et nii Ben ja mina osutades Jason praegusel hetkel.
Nüüd mul on võimalik kindlaks teha, kus ei Brian kuuluvad?
Nii et ainus asi, mida ma oleks juurdepääs Praegu on tema n andmete element.
Ma lähen, et kontrollida, kas Brian alla Jason?
Vastus on tõene.
>> Mis siis nüüd peab juhtuma, õiges järjekorras?
Mul on vaja uuendada, kui palju viiteid kokku selles loos?
Kui mu käsi on endiselt vastakuti Jason ja käsi - kui soovite, et
pane oma käsi nagu, justkui, I ei tea, küsimärk.
OK, hea.
>> Olgu, nii et teil on vähe kandidaate.
Kas Ben või I või Brian või Jason või keegi teine, kes
suunanäitajaks vaja muuta?
Mitu kokku?
>> OK, nii et kaks.
Minu kursor ei ole tegelikult küsimus enam sest ma olen lihtsalt ajutine.
Seega on need kaks meest, arvatavasti, nii Ben ja Brian.
Nii et lubage mul ettepanek, et me värskendame Ben, sest ta on esimene.
Esimene element selle nimekirja nüüd saab olema Brian.
Nii Ben punktini Brian.
OK, mis nüüd?
>> Kes saab märkida, kellele?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: OK, nii Brian on punkti juures Jason.
Aga ma olen kaotanud jälgida, et pointer?
Kas ma tean, kui Jason on?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: mina, sest ma olen ajutine pointer.
Ja ilmselt ma ei ole muutunud punkti juures uus sõlm.
Nii saame lihtsalt Brian punkt kell iganes ma osutavad.
Ja me oleme valmis.
Nii kui üks, sisestamise juures loetelu alguses.
Seal oli kaks olulist sammu.
Üks, peame ajakohastama Ben ja seejärel meil on ka ajakohastada Brian.
Ja siis ma ei pea vaeva nägema traipsing läbi ülejäänud
nimekirja, sest me juba leidnud oma asukohta, sest ta kuulus
vasakule esimene element.
>> Olgu, päris lihtne.
Tegelikult tundub, nagu me oleme peaaegu muuta see liiga keeruline.
Teeme nüüd sikutama ära lõpuks nimekirja ja vaata, kus
keerukus hakkab.
Nii et kui nüüd, ma alloc saalist.
Igaüks taha mängida 55?
Olgu, ma nägin oma käsi esimene.
Tule üles.
Jah.
Mis su nimi on?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Habata.
OK, tulge siia.
Sul on number 55.
Nii et loomulikult kuuluvad lõpus nimekirja.
Teeme kordus simulatsiooni mind on PTR hetkeks.
Nii et ma olen esimene läheb näpuga mis iganes Ben osutavad.
Me mõlemad osutavad praegu Brian.
Nii 55 on vähemalt viis.
Nii et ma lähen uuendada ise poolt osutades Brian järgmise pointer, kes
nüüd on muidugi Jason.
55 on vähemalt üheksa, nii Ma lähen uuendada PTR.
Ma lähen uuendada PTR Ma lähen uuendada PTR.
Ja ma lähen - hmm, mis su nimi oligi?
>> Üliõpilane: Diana.
>> SPEAKER 1: Diana on suunatud muidugi kell null temaga vasaku käega.
Nii et kui ei Habata tegelikult kuuluvad selgelt?
Vasakul siin.
Niisiis, kuidas ma tean, et panna teda siin Ma arvan, et ma olen segane.
Sest see, mis on PTR kunst Sel hetkel kasutab?
Null.
Nii et kuigi visuaalselt, saame ilmselt näha kõiki neid
poisid siin laval.
Ma ei ole hoida silma peal eelmise Isiku nimekirja.
Mul ei ole sõrmega osutades, sel juhul sõlme number 34.
>> Teeme tegelikult alustada seda üle.
Nüüd ma tegelikult ei vaja teine ​​kohalik muutuja.
Ja see on see, mida näete tegeliku valimi C kood, kus, kui ma lähen,
kui ma update minu paremal käel juhtida Jason, jättes Brian taga, ma
parem hakata kasutama oma vasakut kätt ajakohastada, kus ma olin, nii et kui ma lähen
läbi selle nimekirja -
rohkem kohmakalt kui ma ette nüüd siin visuaalselt -
Ma lähen, et saada nimekirja lõppu.
>> See käsi on ikka null, mis on päris kasutu, välja arvatud, et näidata
Ma olen selgelt lõpus nimekirja aga nüüd vähemalt on mul see
eelkäija osuti osutab siin, nii mis nüüd käed ja mida suunanäitajaks vaja
tuleb ajakohastada?
Kelle poolt sa tahad reconfigure esimesena?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: OK, nii et Diana.
Kui sa tahad, et juhtida Diana vasakul pointer?
Kell 55, arvatavasti, et oleme sisestatud seal.
Ja kui peaks 55 pointer minna?
Alla esindava null.
Ja minu käed, sel hetkel, ei oluline, sest nad olid lihtsalt
ajutised muutujad.
Nüüd me oleme valmis.
>> Nii keerukust seal - ja see ei ole nii raske rakendada,
kuid me peame teisene muutuja teha et enne, kui ma liikuda mu õigus
aga ma update väärtus minu vasak küljest pred pointer sel juhul nii
et mul tagumisel pointer jälgida, kus ma olin.
Nüüd kui kõrvale, kui sa mõtled seda läbi, see tunne, et see on
natuke tüütu on, et hoida jälgida seda vasaku käega.
>> Mis oleks teine ​​lahendus see probleem on?
Kui sul ümber kujundada andmed struktuur me räägime
läbi kohe?
Kui see lihtsalt omamoodi tunneb vähe tüütud on, nagu, kaks viiteid
läbimas nimekiri, kes veel võiks on, Ideaalses maailmas, säilitada
informatsiooni, mida me vajame?
Jah?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Täpselt.
Just nii seal on tegelikult huvitav idud idee.
Ja see idee eelmine pointer, osutades eelmine element.
Mis siis, kui ma lihtsalt kehastab et sisemus nimekirjaga?
Ja see saab olema raske visualiseerida see ilma kogu paber
kukkumist põrandale.
Aga oletame, et need kutid kasutada nii nende käed on eelmise
pointer, ja järgmise pointer, mis rakendamisel, mida me kutsume kahekordselt
seotud nimekirja.
See võimaldaks mind omamoodi tagasikerimiseks palju kergem ilma minuta,
programmeerija, võttes hoida jälitada käsitsi -
tõesti käsitsi -
kus ma ei olnud varem nimekirjas.
Nii et me ei tee seda.
Hoiame seda lihtsalt sellepärast, et see on tulemas hinnaga, kaks korda
palju ruumi suunanäitajaks, kui sa tahad teist.
Aga see on tõesti ühine andmete struktuuri, mida
kahekordselt seotud nimekirja.
>> Teeme lõplik näiteks siin ja pane need poisid välja oma viletsuses.
Nii malloc 20.
Tule üles vahekäiku seal.
Olgu, mis su nimi on?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Vabandust?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Demeron?
OK tulge siia.
Sul peab olema 20.
Sa ilmselt ei kavatse kuuluvad 17-22.
Nii et lubage mul õppida oma õppetund.
Ma hakkan pointer osutades Brian.
Ja ma lähen on minu vasak käsi ainult värskendada Brian nagu ma liikuda
Jason, kontrolli kas 20 alla üheksa?
Ei.
Kas 20 on alla 17?
Ei.
Kas 20 on alla 22?
Jah.
Mis siis osuti või käsi vaja muuta kus nad osutavad nüüd?
>> Nii et me saame teha 17 osutades 20.
Nii et pole midagi.
Kui me tahame juhtida kursor nüüd?
Kell 22.
Ja me teame, kus 22 on jällegi tänu minu ajutine pointer.
Nii et me oleme OK seal.
Niisiis, kuna see ajutine ladustamine Olen hoida silma peal, kus kõik on.
Ja nüüd saab visuaalselt minna kus te kuulute, ja nüüd on meil vaja 1, 2, 3,
4, 5, 6, 7, 8, 9 stress pallid, ning aplaus
need kutid, kui saime.
Ilusti tehtud.
>> [APLAUS]
>> SPEAKER 1: Olgu.
Ja te võite hoida tükki paber nagu mälestusesemete.
>> Olgu nii, usalda mind see on palju lihtsam kõndida läbi, et koos
inimesele, kui see on tegelike kood.
Aga mida sa leiad vaid hetk nüüd on see, et sama - oh, aitäh.
Aitäh -
on see, et sa leiad, et samu andmeid struktuur, mis on seotud nimekirja, võib tegelikult
kasutada alustalana veelgi keerukamaid andmestruktuurid.
>> Ja realiseerida liiga teema on see, et oleme absoluutselt kasutusele rohkem
keerukamaks rakendamine Selle algoritmi.
Sisestamisel ja kui me läksime läbi see, kustutamine ja otsimine, on vähe
keerulisem kui oli massiivi.
Aga me saame mõned dünaamilisus.
Me saame adaptiivne andmestruktuur.
>> Aga jälle, me maksame hind teatav täiendavat keerukust nii
rakendamisel.
Ja me loobunud muutmälu.
Ja kui aus olla, siis ei ole mõne kena puhas slide võin teile anda, et
ütleb siin ongi seotud nimekirja on parem kui massiivi.
Ja jätke see seda.
Kuna teema reoccurring nüüd, isegi seda enam, et lähinädalatel on
et seal ei ole tingimata õige vastus.
>> See on põhjus, miks meil on eraldi telg projekteerimise jaoks probleem komplekti.
See saab olema väga konteksti kas soovite kasutada neid andmeid
struktuur või et üks, ja see tahe sõltub sellest, mida teie jaoks tähtis nii
ressursside ja keerukust.
>> Aga lubage mul ettepanek, et ideaalne andmed struktuur, Püha Graal, oleks
midagi, mis on pidevas ajal olenemata sellest, kui palju asju on
sees, kas ei oleks hämmastav, kui andmestruktuur tagastatakse vastuseid
konstantse ajaga.
Jah.
See sõna on oma tohutu sõnastik.
Või ei ole see sõna ei ole.
Või mõni selline probleem olemas.
Noh vaatame, kui me ei saa vähemalt astuda samm lähemale sellele.
>> Lubage mul esitada uus andmestruktuur võib kasutada erinevaid asju,
sel juhul nimetatakse hash tabelis.
Ja nii me tegelikult tagasi põrkav kell massiivi, antud juhul, ja
mõnevõrra meelevaldselt, olen juhtinud seda hash tabelit massiivi omamoodi
kahemõõtmeline massiiv -
või pigem see siin on kujutatud kui kaks mõõtmeline massiiv - kuid see on lihtsalt
massiivi suurus 26, nii et kui me helistada massiivi, laud sulg
null on ristküliku tipus.
Tabel sulg 25 on ristküliku allosas.
Ja see on, kuidas ma võiks teha andmebaasi konstruktsioon, kus ma tahan salvestada
inimeste nimesid.
>> Nii näiteks, ja ma ei tarbi kogu see asi siin on õhuliinid, kui ma
oli see massiiv, mis ma nüüd lähen helistada hash tabel ja see on jälle
Asukoht null.
See siin on asukoht üks, ja nii edasi.
Väidan, et ma tahan kasutada neid andmeid struktuuri huvides arutelu,
salvestada inimeste nimesid, Alice ja Bob ja Charlie ja muud sellised nimed.
Nii et mõtle selle nüüd algused , ütleme, sõnastik
kus on palju sõnu.
Nad juhtub olema nimed Meie näites siin.
Ja see on kõik liiga Sobiv võib-olla ka rakendamisel õigekirjakontrolli, nagu me
võib jaoks probleem määrata kuus.
>> Nii et kui meil on massiivi kogupindalaga 26 nii, et see on 25. asukoht
allosas, ja ma väita, et Alice on esimene sõna sõnaraamatus
nimed, et ma tahan lisada RAM, sellesse andmestruktuur, kus on
instinktid ütlen teile, et Alice'i nimi peaks minema selle massiivi?
>> Meil on 26 võimalusi.
Kui me tahame, et panna teda?
Me tahame teda sulg null, eks?
Alice, kutsume seda null.
Ja B on üks, ja C on kaks.
Nii et me ei kavatse kirjutada Alice'i nimi siia.
Kui me siis sisesta Bob, tema nimi läheb siin.
Charlie läheb siin.
Ja nii edasi ette läbi see andmestruktuur.
>> See on suurepärane andmestruktuur.
Miks?
Noh, mis on töötamise aeg sisestades inimese nime sellesse
andmestruktuur kohe?
Arvestades, et see tabel on rakendatud, tõesti, kui massiiv.
Noh see on pidev aja.
See, et üks.
Miks?
>> Noh, kuidas sa kindlaks kus Alice kuulub?
Sa vaata, mis kirjas tema nimi?
Esimene.
Ja saad seal, kui see on string, lihtsalt vaadata string
sulg null.
Nii nullis iseloomu string.
See on lihtne.
Me tegime seda krüpto loovutamise nädalat tagasi.
Ja siis, kui sa tead, et Alice'i kirjas on kapitali, saame lahutama
välja 65 või kapitali ise, mis annab meile null.
Nii et me teame nüüd, et Alice kuulub Kohapeal null.
>> Ja arvestades osuti sellele andmed struktuur, mingisugune, kui kaua
see mind leida asukoht nulli massiivi?
Lihtsalt üks samm, eks see on konstantne aeg sest muutmälu me
Kavandatud oli funktsioon massiivi.
Nii lühike, figuring mida indeks Alice'i nimi on, mis on
Sel juhul ei või olgem lihtsalt lahendada et nulliga, kus B on üks ja C on
kaks, selgitades, et välja on konstantne aeg.
Ma pean vaatama oma esimese kirja, figuring kus null on
massiiv on ka pidevalt aega.
Nii tehniliselt see on nagu kaks sammu nüüd.
Aga see on ikka samaks.
Nii me nimetame et suur O ühe, nii et me oleme sisestatud Alice sellesse tabelisse
konstantse ajaga.
>> Aga muidugi, ma oleks naiivne siin, eks?
Mis siis, kui seal on Aaron klassis?
Või Alicia?
Või muud nimed algavad A. Kuhu me läheme üles
et inimene, eks ole?
Ma mõtlen, et praegu on ainult kolm inimesed lauale, nii et võib-olla me
tuleks panna Aaron saabus null üks kaks kolm.
>> Just, ma võiksin panna siia.
Aga siis, kui me püüame lisada Taaveti see nimekiri, kus Taavet minna?
Nüüd meie süsteem hakkab purustamine maha, eks?
Sest nüüd David jõuab siia Kui Aaron on tegelikult siin.
Ja nüüd kogu see idee, millel puhas andmestruktuur, mis annab meile
pidev aja sisestamisel ei ole enam pidev ajal sest ma pean
vaadake, oh, damnit, keegi on juba Alice asukohast.
>> Lubage mul sondi ülejäänud seda andmed struktuur, otsin kohapeal üles
keegi nagu Aaroni nimi.
Ja nii, et liiga on hakanud võtta lineaarne aeg.
Pealegi, kui sa nüüd tahad leida Aaron selles andmestruktuur, ja sa
vaadake, ja Aaroni nimi ei ole siin.
Ideaalis oleks lihtsalt öelda Aaroni ei andmestruktuur.
Aga kui sa hakata ruumi Aaron, kus oleks pidanud olema D
või E, teid, halvimal juhul pead kontrollima Kogu info konstruktsioon
mille puhul devolves midagi lineaarne suurus tabelis.
>> Nii et kõik õige, ma ajan asja korda.
Probleem on selles, et mul oli 26 elementi see massiiv.
Lubage mul seda muuta.
Oih.
Lubage mul seda muuta nii, et pigem heaolu suurus 26 kokku märka alt
indeks on muutu kuni n miinus 1.
Kui 26 on selgelt liiga väike inimesele " nimesid, sest seal on tuhandeid
nimed maailmas, lähme lihtsalt 100 või 1000 või 10000.
Olgem lihtsalt eraldada palju rohkem ruumi.
>> Noh, et ei pruugi väheneda tõenäosus, et me ei pea kaks
inimeste nimed algavad ja Niisiis, te ei kavatse proovida panna
nimede asukohta null ikka.
Nad ikka läheb kokku põrkavad, mis tähendab, et meil on vaja veel lahendus panna
Alice ja Aaron ja Alicia ja muu nimed algavad mujal.
Aga kuidas suur probleem see on?
Milline on tõenäosus, et sa on kokkupõrked andmed
struktuuri nagu see on?
>> Noh, las ma - me tuleme tagasi Sellele küsimusele siin.
Ja vaadata, kuidas me võiksime lahendada see esimene.
Lase ma tõmban seda ettepanekut siin.
Mida me just kirjeldatud on algoritm, heuristiline nimetatakse lineaarse
katsetamine, mille kohaselt juhul, kui sa püüdsid lisada midagi siin andmed
struktuur, mida nimetatakse hash tabel, ja seal pole ruumi seal, siis
tõeliselt sondi andmestruktuur kontrollimine, kas see on võimalik?
Kas see Saadaval on see võimalik?
Kas see olemas?
Ja kui see lõpuks on, siis sisesta nimi, mida algselt kavandatud
mujal selles kohas.
Kuid halvimal juhul ainult kohapeal võib olla väga põhjas andmed
struktuur, päris lõpus massiivi.
>> Nii lineaarne katsetamine, halvimal juhul, devolves lineaarne algoritm, kus
Aaron, kui ta juhtub olema sisestatud viimane Selles andmestruktuur, võib ta
põrkuvad see esimene asukoht, kuid siis lõpetuseks ebaõnn päris lõpus.
Nii et see ei ole konstantne aeg Püha Graal meile.
Selline lähenemine, mille puhul lisatakse elemendid andmete struktuuri nimetatakse räsi
Tabel ei tundu olevat pidev aeg vähemalt mitte üldiselt juhul.
See võib vaimule midagi lineaarne.
>> Mis siis, kui me lahendada kokkupõrkeid mõnevõrra teisiti?
Nii et siin on keerukam lähenemine, mis on ikka veel
nimetatakse hash tabelis.
Ja hash, nagu kõrvale, mida Ma mõtlen on indeks, mis
Mainisin.
Hash midagi saab mõelnud kui verb.
>> Nii et kui te hash Alice'i nimi, räsifunktsiooni, niiöelda,
peaks tagasi number.
Antud juhul on null, kui ta kuulub juures Asukoht null, üks, kui ta kuulub juures
Asukoht üks, ja nii edasi.
Nii et minu räsifunktsiooni Seni on super lihtne, vaid vaadates
esitäht kellegi nimi.
Aga räsifunktsiooni võtab nii sisend mõned tükk andmed,
string, int, mida iganes.
Ja ta sülitab välja tavaliselt number.
Ja see number on, kui need andmed element kuulub andmestruktuur
mida tuntakse hash tabelis.
>> Nii lihtsalt vaistlikult, et see on veidi erinevas kontekstis.
See tegelikult viitab näiteks kaasates sünnipäevad, kus
siis võib olla sama palju kui 31 päeva kuus.
Aga mis see inimene otsustada teha kokkupõrke korral?
Kontekst nüüd on, ei ole kokkupõrge nimesid, kuid kokkupõrge sünnipäevad,
Kui kaks inimest on sama sünnipäeva 2. oktoober, näiteks.
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Jah, siin on meil võimendades seotud nimekirju.
Nii tundub natuke teistmoodi kui me juhtis ta varem.
Aga me ilmselt array vasakul servas.
See on üks indeks, mitte erilist põhjust.
Aga see on ikka massiivi.
See on massiivi osuti.
Ja kõik need elemendid, igaüks need ringid või jooned - kaldkriips
esindavad null - kõik need osuti on ilmselt osutades
milliseid andmeid struktuur?
Seotud nimekirja.
>> Nüüd on meil võimalus kõva kood meie programm
Laua suurus.
Sel juhul me teame, pole kunagi rohkem kui 31 päeva kuus.
Nii raske kodeerimine väärtus nagu 31 mõistlik selles kontekstis.
Kontekstis nimed, kõva kodeerimine 26 ei ole mõistlik see inimeste
nimed alles algavad, näiteks tähestiku kaasates läbi Z.
>> Saame tuupima neid kõiki arvesse, et andmed struktuuri nii kaua, kui me
kokkupõrge, me ei pane nimesid siin me selle asemel mõtlema nende rakkude
mitte nagu stringid ise, kuid kui vihjeid, näiteks, Alice.
Ja siis Alice võib olla teise osuti teise nime alustades
A. Ja Bob tegelikult läheb siia.
>> Ja kui seal on teine ​​nimi algab B-ga, ta jõuab siia.
Ja nii iga osa käesoleva tabelis kaks, kui me loodud see
veidi rohkem nutikalt -
tule -
kui me loodud see veidi rohkem nutikalt, nüüd muutub adaptiivne andmed
struktuur, kus pole raske piiri kui palju elemente saate sisestada
arvesse seda, sest kui sul on kokkupõrge, see on hea.
Lihtsalt minna ja lisada see mida nägime natuke tagasi oli
tuntud seotud nimekirja.
>> Noh olgem pausi hetkeks.
Milline on tõenäosus kokkupõrke esiteks?
Õigus, võibolla ma olen üle mõelnud, äkki Ma olen üle insener Selle probleemi
sest sa tead, mis?
Jah, ma ei saa tulla suvalise näited välja ülalt mu peas nagu
Allison ja Aaron, kuid tegelikkuses antud ühtlase jaotuse
sisendeid, mis on mõne juhusliku sisestamise arvesse andmete struktuuri, mis tegelikult on
kokkupõrke tõenäosus?
Noh selgub, et see on tegelikult super suur.
Las ma üldistada seda Probleem on selles.
>> Nii et ruumi n CS50 õpilast, mis on on tõenäosus, et vähemalt
kaks õpilast ruumis on sama sünnipäev?
Nii et seal on mis. mõni Hund -
200 300 inimest siin ja mitmel sada inimest kodus täna.
Nii et kui sa tahad küsida, mis on tõenäosus kaks inimest
selles ruumis, millel on sama sünnipäev, me leiame vastuse.
Ja ma väita, tegelikult on kaks inimesed sama sünnipäev.
>> Näiteks, kas keegi on täna sünnipäev?
Täna?
Homme?
Olgu, tundub, nagu ma et pean seda tegema 363 või nii rohkem
korda tegelikult aru saada, kui meil on kokkupõrke.
Või me võiks lihtsalt teha seda matemaatiliselt mitte tüütult
seda tegema.
Ja järgmine ettepanek.
>> Seega teen ettepaneku, et me võiks modelleerida tõenäosus kaks inimest, kellel on
sama sünnipäev on tõenäosus 1 miinus tõenäosus keegi, kellel
sama sünnipäev.
Nii, et saada seda, ja see on alles fancy viis kirjutamise jaoks
esimene inimene toas, ta võib olla mõni võimalik
sünnipäevad eeldades 365 päeva aastas, koos vabandused isikutele
29. veebruar sünnipäev.
>> Nii et esimene inimene selles toas on tasuta mingit arvu sünnipäevad
välja 365 võimalusi, et me teeme seda 365 jagatud 365,
mis on üks.
Järgmine inimene toas, kui eesmärgiks on kokkupõrke vältimiseks, saab ainult
on tema sünnipäev, kuidas palju erinevaid võimalikke päeva?
364.
Nii teise ametiaja see väljend on sisuliselt seda, et matemaatikat meile
lahutatakse maha üks võimalik päev.
Ja siis järgmisel päeval, järgmisel päeval, Järgmisel päeval alla koguarv
inimesi ruumis.
>> Ja kui me siis leian ka, siis on tõenäosus mitte igaüks, kellel
ainulaadne sünnipäevad, aga jälle 1 miinus et see, mida me saada on väljend
mida saab väga luulelennuliselt näeb välja selline.
Aga see on rohkem huvitav vaadata visuaalselt.
See on skeem, kus on x-telg on inimeste arvu ruumis,
arvu sünnipäevad.
Y-telg on tõenäosus Kokkupõrke kaks inimest
millel on sama sünnipäev.
>> Ja Buffee alates nimetatud kõver on et niipea, kui saad nagu 40
õpilased, sa oled üles 90% tõenäosusega combinatorically kahe
inimesed või rohkem, millel sama sünnipäev.
Ja kui sa saad nagu 58 inimesed on peaaegu 100% võimalus kaks
inimesed ruumis on plaanis sama sünnipäev, kuigi seal on
365 või 366 võimalik ämbrid ja ainult 58 inimest toas.
Just statistiliselt oled tõenäoliselt saada kokkupõrked, mis lühidalt
motiveerib see arutelu.
Et isegi kui me fancy siin, ja alustate võttes need ketid, me oleme ikka
läheb on kokkupõrkeid.
>> Nii et tekib küsimus, mis on kulud on talutavad Lisatud ja kustutatud
arvesse andmete struktuuri nagu see on?
Noh andke mulle ettepaneku -
ja lubage mul minna tagasi ekraanil üle siin - kui me oleme n elementi
nimekirja, nii et kui me üritame lisada n elementi, ja meil on
kui palju kokku ämbrid?
Oletame, et 31 kokku ämbrid puhul sünnipäevad.
Mis on maksimaalne pikkus on Nende kettide potentsiaalselt?
>> Kui jälle seal 31 võimalik sünnipäevad antud kuul.
Ja me lihtsalt kokkukleepumist kõigile -
tegelikult see on loll näide.
Teeme 26 asemel.
Seega, kui tegelikult on inimesed, kelle nimed Alustame läbi Z, andes
meile 26 võimalusi.
Ja me kasutame andmestruktuuri nagu üks me just nägime, kusjuures meil on
massiivi osuti, millest igaüks osutab seotud nimekirja, kus
Esimene nimekiri on igaühe nimega Alice.
Teine nimekiri on igal koos algavat nime, mis algab
B-ga, ja nii edasi.
>> Mis on tõenäoline pikkus iga need nimekirjad, kui me eeldame, kena puhas
jaotus nimede kaudu Z kogu andmestruktuuri?
Seal on n inimest andmestruktuur jagatud 26, kui nad kenasti
laiali üle kogu andmestruktuur.
Nii pikkuse iga ketid on n jagatud 26.
Aga suur O märke, mis see on?
Mis see on tõesti?
Nii et see on tõesti lihtsalt n, eks?
Kuna me oleme varem öelnud, et vuih sa jagad 26.
Jah, tegelikult on see kiirem.
Aga teoreetiliselt, see ei ole põhimõtteliselt kõik, et kiiremini.
>> Nii et me ei tundu olevat kõik, et palju lähemale see Püha Graal.
Tegelikult, see on lihtsalt lineaarne aeg.
Heck, sel hetkel, siis miks me ei lihtsalt kasutada üks tohutu seotud nimekirja?
Miks me ei võiks lihtsalt kasutada üks suur array salvestada nimed
kõik ruumis?
Noh, kas on veel midagi kaalukaid umbes hash tabel?
Kas on veel midagi kaalukat kohta andmete struktuuri
, mis näeb välja nagu see on?
See.
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: õige ja uuesti, kui see on lihtsalt lineaarne algoritm, ja
lineaarne aeg andmestruktuur, miks ma ei lihtsalt hoida igaühe nime suur
massiiv või suur seotud nimekirja?
Ja lõpetage tehes CS nii palju raskem kui see peaks olema?
Mis on kaalukaid sellest, isegi kuigi ma kriimustatud välja?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Insertsioonid ei ole?
Kallimad enam.
Nii sisestamisel potentsiaalselt võiks ikka olema pidev, isegi kui ta oma andmed
struktuur näeb välja selline, array suunanäitajaks, millest igaüks on vastakuti
potentsiaalselt seotud nimekirja.
Kuidas sa saavutada püsiv aeg sisestamise nimed?
Pista see ees, eks?
>> Kui me ohverdama disaini eesmärk alates varem, kui me tahtsime hoida
igaühe nimi, näiteks, sorteeritud, või kõik numbrid laval sorteeritud,
oletame, et meil on sortimata seotud nimekirja.
See ainult maksab meile ühe või kaks sammu, meeldib puhul Ben ja Brian
varem, et lisada element loetelu alguses.
Nii et kui me ei hooli sorteerimine kõik nimed algavad või kõik
nimed algavad B, saame ikka saavutada püsiv aja sisestamist.
Nüüd soojaks Alice või Bob või nimi üldiselt on ikka see, mida?
See on suur O n jagatud 26, et Ideaalne juhul, kui kõik on ühtlaselt
jaotatud, kus on nii palju oma kui on Z, mis on ilmselt
ebareaalne.
Aga see on ikka lineaarne.
>> Aga siin me tuleme tagasi punkti asümptootilisest märge on
teoreetiliselt õige.
Kuid reaalses maailmas, kui ma väita, et Minu programm ei tee midagi 26 korda
kiiremini kui sinu oma, kelle programm sa lähed eelistavad kasutada?
Sinu või minu, mis on 26 korda kiiremini?
Reaalselt kelle on 26 korda kiiremini, isegi kui teoreetiliselt
meie algoritmid töötavad samal asümptootiliseks sõiduaega.
>> Lubage mul välja teistsuguse lahendus üldse.
Ja kui see ei ole löök meelt, oleme välja andmestruktuurid.
Nii et see on see Prefiksipuu -
mingi loll nimi.
Ta on pärit väljavõtete ja sõna on kirjutatud Prefiksipuu, t-r-i-e, sest
Muidugi ülekanne kõlab Prefiksipuu.
Aga see on ajalugu Sõna Prefiksipuu.
>> Nii Prefiksipuu on tõepoolest mingi puu, ja see on ka mängida, et sõna.
Ja kuigi sa ei saa päris näha Selle visualiseerimine, Prefiksipuu on
puu struktuuri, nagu sugupuu koos üks esivanem tipus ja palju
ja lapselapsed ja lapselapsed kui jätab põhjale.
Aga iga sõlme Prefiksipuu on massiiv.
Ja see on massiiv - ja olgem lihtsustavad hetkeks - see on
massiiv, sel juhul on suurus 26, kus Iga sõlme uuesti ei massiivi suurus
26, kui nullis element kõnealuses massiivi esindab ja viimane
element iga sellise massiivi esindab Z.
>> Seega teen ettepaneku, et seejärel need andmed struktuur, mida nimetatakse Prefiksipuu, võib olla
kasutada ka salvestada sõnu.
Nägime hetk tagasi, kuidas saaksime säilitada sõnad, või antud juhul nimed ja me
nägime, kuidas meil on võimalik salvestada numbreid, aga kui me keskendume nimed või stringid
siin, teate, mis on huvitav.
Väidan, et nimi Maxwell on sees see andmestruktuur.
Kus sa näed Maxwell?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: vasakul.
Niisiis, mida on huvitav selle andmed struktuur on pigem poest
string M--X-W-E-L-L Kenoviiva null, kõik contiguously, mida mitte teha
jälgib.
Kui see on Prefiksipuu nagu andmestruktuur, iga, mille tipud on jälle massiiv,
ja soovite salvestada Maxwell, siis esimene indeks ja nii root sõlmes, nii
rääkida, tipmine sõlme, Kohapeal M, paremale, nii
umbes keskele.
Ja siis sealt sa järgima kursor tütartippu nii rääkida.
Nii sugupuu mõttes te järgite seda allapoole.
Ja see viib sind teise sõlme vasakul seal, mis on
lihtsalt üks massiiv.
>> Ja siis, kui soovite salvestada Maxwell, leida pointer, mis tähistab
, Mis on see siin.
Siis minge järgmise sõlme.
Ja teate - see on põhjus, miks pildi veidi petlik -
See sõlm vaadata super pisike.
Aga õige on see, Y ja Z. See on lihtsalt autor on kärbitud
pilt, et sa tegelikult vaata asju.
Muidu see pilt oleks väga lai.
Nüüd sa indeks asukoha X, siis W, siis E, siis L, seejärel L. Milles siis
see uudishimu?
>> Noh, kui me kasutame seda tüüpi uus võtta, kuidas hoida stringi
andmete struktuuri, siis on vaja veel sisuliselt kontrollima off andmete
struktuur, mis sõna lõppeb siin.
Teisisõnu, kõik need sõlmed millegipärast on meeles pidada, et me
tegelikult järgida kõiki neid viiteid ja lahkute vähe
riivsaiaga allosas siin selle struktuur, mis näitab M--X-W-E-L-L on
tõepoolest selles andmestruktuur.
>> Nii et me võiks seda teha järgmiselt.
Iga tippe pilt me ​​lihtsalt Saag on üks, massiivi suurus 27.
Ja see on nüüd 27, sest p seatud kuus, me tegelikult sulle ülakoma,
et saaksime nimed nagu O'Reilly ja teised ülakoma.
Aga sama mõte.
Kõik need elemendid massiiv punktid struct
sõlm, nii lihtsalt sõlme.
Nii et see on väga meenutab Meie seotud nimekirja.
>> Ja siis on mul Loogiline, kus ma helistada sõna, mis on lihtsalt saab olema
tõsi, kui sõna lõpeb see sõlme puu.
See tõhusalt tähistab vähe kolmnurk nägime hetkeks tagasi.
Nii et kui sõna lõpeb, et sõlme puu, mis sõna valdkonnas on tõsi,
mis on põhimõtteliselt kontrollida lülitatud või me joonistus see kolmnurk, jah seal
on sõna siin.
>> Nii et see on Prefiksipuu.
Ja nüüd on küsimus selles, mida on oma sõiduaega?
Kas see suur O n?
Kas see midagi muud?
Noh, kui sa oled n nimed selles andmed struktuur, Maxwell on vaid üks
neid, mis on töötamise aeg sisestamist või leida Maxwell?
Mis sõiduaega sisestades Maxwell?
Kui seal on n muud nimed juba tabelis?
Jah?
>> Õpilane: [kuuldamatu].
>> SPEAKER 1: Jah, see on pikkus nime, eks?
Nii M--x-w-e-l-l, nii tundub, nagu see algoritm on suur O seitse.
Nüüd, muidugi, nimi on erineva pikkusega.
Võibolla on see nimetus.
Võib-olla on pikk nimi.
Aga mis peamine on see, et see on pidev number.
Ja võib-olla see ei ole tegelikult pidevalt, aga jumal, kui realistlikult lähenedes
sõnastik, seal on ilmselt mingi piir arvu tähed
isiku nimi konkreetses riigis.
>> Ja nii me võime eeldada, et väärtus on konstantne.
Ma ei tea, mis see on.
See on ilmselt suurem kui me arvame, et on.
Sest seal on alati mõned nurgas puhul hull pikk nimi.
Nii ütleme k, aga see on veel pidev arvatavasti, sest igal
nimi maailmas, vähemalt riigis, on see, et pikkus või
lühem, nii et see on pidev.
Aga kui me oleme öelnud midagi on suur O püsiv väärtus, mis see on
tegelikult võrdne?
See on tegelikult sama asi öeldes pidevalt aega.
>> Nüüd oleme omamoodi petmine, eks?
Oleme omamoodi võimendades mõned teooria siin öelda, et hästi, et k on
tõesti lihtsalt, et üks, ja see on pidevalt aega.
Aga see on tõesti.
Sest Võtmeküsimuseks on see, et kui meil on n nimed juba selles
andmete struktuuri ja me sisestada Maxwell, on, kui palju aega kulub, et me
sisestada Maxwell üldse mõjutatud kui palju teisi inimesi
on andmestruktuur?
Kas ei tundu olevat.
Kui mul oleks miljard rohkem elemente seda Prefiksipuu ning seejärel sisestada Maxwell, on
ta üldse mõjutab?
Ei.
Ja see, et erinevalt mõne päeva andmed struktuuride oleme näinud siiani, kus
sõiduaega oma algoritmi täiesti sõltumatu, kui palju
asjad on või ei ole juba selles andmestruktuur.
>> Ja nii seda annab teile nüüd on võimaluse p set kuus, mis kestab
uuesti kaasata rakendamisel oma Õigekirja, lugemine 150000
sõnadega, kuidas salvestada et ei ole tingimata selge.
Ja kuigi ma olen püüdnud leida Püha Graal, ma ei
väidavad, et Prefiksipuu on.
Tegelikult hash tabel võib väga hästi osutuda palju tõhusamaks.
Aga need on vaid -
see on lihtsalt üks disaini otsuseid sa pead tegema.
>> Aga sulgemine võtame 50 või nii sekundit kurkistaa mis peitub
edasi järgmisel nädalal ja pärast me üleminek selle käsurea
maailmas kui C programme asjad web aluseks ja keeltes nagu PHP ja
JavaScript ja internet ise protokolle nagu HTTP, mille olete
enesestmõistetavaks aastaid nüüd, ja trükitud rohkem kui kord
päev, ehk või näinud.
Ja hakkame koorida tagasi kihist, mis on internet.
Ja mis on kood, mis aluseks tänapäeva tööriistu.
Nii 50 sekundit selle teaser siin.
Ma annan sulle Warriors of the Net.
>> [VIDEO PLAYBACK]
>> -Ta tuli sõnum.
Koos protokolliga kõik omal.
Ta tuli maailma julm tulemüürid uncaring ruuterid, ja ohud kaugele
hullem kui surm.
Ta on kiire.
Ta on tugev.
Ta TCPIP.
Ja tal on oma aadress.
Warriors of the Net.
>> [END VIDEO PLAYBACK]
>> SPEAKER 1: See, kuidas internet teeb tööd järgmisel nädalal.