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