Ræðumaður 1: Allt í lagi, þannig að við erum aftur. Velkomin CS50. Þetta er endir viku sjö. Svo muna að síðasta sinn, við byrjuðum horfa á örlítið flóknari gögn uppbygging. Þar allt þar til nú, allt sem við höfðum í raun að ráða okkar var þetta fylki. En áður en við henda array sem ekki allt sem áhugavert, sem vissulega það reyndar er, hvað sumir af the plús af þessari einföldu gögn uppbygging svona langt? Hvað það er gott að? Svo langt eins og við höfum séð? Hvað ertu með? Ekkert. STUDENT: [inaudible]. Ræðumaður 1: Hvað er það? STUDENT: [inaudible]. Ræðumaður 1: Föst stærð. OK, svo hvers vegna er fastur stærð góð þó? STUDENT: [inaudible]. Ræðumaður 1: í lagi, svo það er duglegur í þeim skilningi að þú getur tekið að fast pláss, sem vonandi er einmitt eins mikið rúm eins og þú vilt. Svo það gæti verið alveg a auk. Hvað er annað upp hlið fylki? Já? STUDENT: [inaudible]. Ræðumaður 1: All the - Fyrirgefðu? STUDENT: [inaudible]. Ræðumaður 1: Öll kassa í minni eða við hliðina á hvort öðru. Og það er gagnlegt - af hverju? Það er alveg satt. En hvernig getum við nýta þann sannleika? STUDENT: [inaudible]. Ræðumaður 1: Einmitt, við getum haldið utan um þar sem allt er bara með því að þekkja eitt netfang, þ.e. heimilisfang Fyrsta bæti þeim klumpur af minni. Eða í tilfelli af the band, veffang fyrstu bleikju í þeim streng. Og þaðan, getum við fundið enda strengsins. Við getum fundið annað frumefni, Þriðji þátturinn, og svo framvegis. Og svo ímynda leið til að lýsa því eiginleiki er að fylki gefa okkur handahófi aðgangur. Bara með því að nota veldi krappi ritháttur og fjölda, getur þú hoppa til ákveðin þáttur í array í föstu tíma, stór O einn, svo að segja. En það er verið nokkur downsides. Hvað fylki ekki mjög auðveldlega? Hvað er það ekki góður í? STUDENT: [inaudible]. Ræðumaður 1: Hvað er það? STUDENT: [inaudible]. Ræðumaður 1: Útvíkkun í stærð. Svo downsides í fylkinu eru einmitt hið gagnstæða á því hvað er upsides eru. Svo er einn af downsides að það er fastur stærð. Svo þú getur í raun ekki vaxa það. Þú getur endurúthluta stærri klumpur af minni, og þá færa gamla þætti inn í nýja array. Og þá frjáls gamla array, fyrir ma með því malloc eða svipað fall sem kallast realloc, sem reallocates minni. Realloc, sem innskot, reynir að gefa þér minni sem er við hliðina á fjölda sem þú hefur nú þegar. En það gæti færa hlutina um að öllu leyti. En í stuttu máli, það er dýrt, ekki satt? Vegna þess að ef þú hafa a klumpur af minni þessari stærð, en þú vilt í raun einn af þessari stærð, og þú vilt að varðveita upprunalega frumefni, þú u.þ.b. línulegt tími afritun ferli sem þarf að gerast á gamla array að nýju. Og raunin er að spyrja starfa kerfi aftur og aftur og aftur fyrir stór klumpur af minni getur byrjað til kostnaður þér tíma og vel. Svo það er bæði blessun og bölvun í dulbúið, þá staðreynd að þessi fylki eru fasta stærð. En ef við kynna staðinn eitthvað eins og þetta, sem við kallað tengt lista, fáum við nokkrar upsides og nokkrar downsides hér eins og heilbrigður. Svo tengist listi er einfaldlega gögn uppbygging samanstendur af C structs í þessu ræða, þar sem strúktúr, muna, er bara gámur fyrir einn eða fleiri tiltekin tegundir af breytum. Í þessu tilfelli, hvað þau gögn tegundir virðast vera inni í strúktúr sem Síðast þegar við kallast hnút? Hver af þessum ferhyrninga er hnút. Og hver af smærri rétthyrninga innan þess er gögn tegund. Hvaða gerðir gerði við segjum þeir voru á mánudag? Já? STUDENT: [inaudible]. Ræðumaður 1: breytu og músina, eða nánar tiltekið, int, og fyrir N, og bendi neðst. Bæði af þeim verður að vera 32 bita, á kosti á tölvu eins og þessa CS50 Tæki, og svo þeir eru dregin jafn að stærð. Svo hvað ertu að nota músina þó fyrir víst? Hvers vegna að bæta þessum ör nú þegar fylki voru svo ágætur og hreinn og einfaldur? Hvað er bendillinn að gera fyrir okkur í öllum þessum hnúta? STUDENT: [inaudible]. Ræðumaður 1: Einmitt. Það er að segja þér hvar sá næsti er. Svo ég nota svoleiðis líkingar af með þráð til að raða í þræði þessa hnúta saman. Og það er einmitt það sem við erum að gera með ábendingum því að hver þessara klumpur af minni mega eða mega ekki vera samliggjandi, aftur til baka til baka inni RAM, því í hvert sinn sem þú kalla malloc segja, gefa mér nóg bæti fyrir nýjan hnút, gæti það vera hér eða það gæti verið hér. Það gæti verið hér. Það gæti verið hér. Þú bara veit ekki. En með ábendingum í heimilisföng þessir hnútar, getur þú sauma þá saman á þann hátt sem lítur sjónrænt eins og lista jafnvel ef þessir hlutir eru allt breiða út um einn eða tveir þínar eða fjórum gígabæta þinn af RAM inni í tölvunni þinni. Svo hæðir, þá að tengda lista er það? Hvað er verðið sem við erum virðist borga? STUDENT: [inaudible]. Ræðumaður 1: Meira pláss, ekki satt? Við höfum, í þessu tilfelli, tvöfaldast magn pláss vegna þess að við höfum farið frá 32 bita fyrir hvern hnút, fyrir hvern int, svo nú 64 bita vegna þess að við verðum að að halda í kring a músina eins vel. Þú færð meiri skilvirkni ef strúktúr þín er stærri en þetta einfaldur hlutur. Ef þú ert í raun að nemandi inni sem er a par af strengjum fyrir nafn og hús, kannski kennitala, kannski einhverjum öðrum sviðum að öllu leyti. Svo ef þú ert með nógu stór strúktúr, þá kannski er kostnaður við músina ekki svo stór samningur. Þetta er hluti af horninu að ræða í því við erum að geyma svo einfalt frumstæðar inni í tengda listanum. En punkturinn er sá sami. Þú ert örugglega að eyða meira minni, en þú ert að fá sveigjanleika. Því nú ef ég vil bæta þáttur í upphafi þessa lista, Ég verð að úthluta nýjan hnút. Og ég verð að bara uppfæra þá örvar einhvern veginn eftir bara að færa nokkrar ábendingar um. Ef ég vil setja eitthvað inn í miðjum listanum, ég er ekki að ýta öllum til hliðar eins og við gerðum í vikna fortíð með sjálfboðaliðum okkar sem fulltrúa fylki. Ég get bara tekið nýjan hnút og þá bara benda örvarnar á mismunandi áttir því það er ekki að vera í raun minni sannur lína eins og ég hef dregið það hér á skjánum. Og svo loks, ef þú vilt setja eitthvað í lok listanum, það er jafnvel auðveldara. Þetta er tegund af handahófi merki, en bendillinn 34, taka giska. Hvað er gildi músina hennar mest líklega dregið tegund af eins gamalt skóla loftnet þarna? STUDENT: [inaudible]. Ræðumaður 1: Það er líklega null. Og reyndar er það einn höfundar framsetning null. Og það er null vegna þú algerlega þarf að vita hvar lok tengt Listinn er, svo þú geymir eftirfarandi og fylgja og fylgja þessum örvarnar að einhverju sorp gildi. Svo null mun þar með að það er engin fleiri hnúta til hægri númer 34, í þessu tilfelli. Þannig að við leggjum til að við getum innleiða þetta hnút í kóða. Og við höfum séð svona af setningafræði áður. Typedef skilgreinir bara nýja tegund fyrir okkur, gefur okkur samheiti eins strengur var fyrir char *. Í þessu tilfelli, það er að fara að gefa okkur shorthand sýndur þannig að strúktúr hnút getur í staðinn bara að skrifa eins og hnút, sem er mikið hreinni. Það er mikið minna fjölorður. Inni í hnút er greinilega int kallað n, og þá struct tengipunktur * sem þýðir nákvæmlega það sem við vildum að örvarnar til að meina, bendi til annars hnút á nákvæmlega sömu gögn tegund. Og ég leggja til að við gætum innleiða leita virka eins og þetta, sem á fyrstu sýn kann að virðast smá flókið. En við skulum sjá það í samhengi. Leyfðu mér að fara yfir á tækið hér. Leyfðu mér að opna skrá sem heitir listi núll punktur klst. Og það inniheldur aðeins skilgreining vér bara sá smá stund síðan að þessum gögnum tegund kallast hnút. Þannig að við höfum sett það inn í a punktur h skrá. Og eins og til hliðar, jafnvel þótt það forrit sem þú ert að fara að sjá er ekki allt sem flókið, það er örugglega venju þegar þú skrifar forrit til setja hlutina eins konar gögn, til að draga Fastar stundum, inni af þinn hausaskrár og ekki endilega í C skrá, vissulega þegar þinn forrit fá stærri og stærri, þannig að þú veist hvar á að líta bæði til gögn í sumum tilvikum, eða fyrir grunnatriði eins og þetta, skilgreiningu einhvers konar. Ef ég opna nú upp lista núll punkt c, taka nokkra hluti. Það inniheldur nokkrar skrár haus, flest sem við höfum séð áður. Það felur eigin haus skrá þess. Og eins og til hliðar, hvers vegna það er tvöfaldur vitna hér, öfugt við hornið sviga á línu sem Ég hef bent þarna? STUDENT: [inaudible]. Ræðumaður 1: Já svo það er staðbundin skrá. Þannig að ef það er staðbundin skrá af þinn eiga hér á línu 15, til dæmis, þú nota tvöfaldur vitna í staðinn á horn sviga. Nú er svona áhugavert. Takið eftir að ég hef lýst alþjóðlegt breytu í þessari áætlun á línu 18. kallaði fyrst, hugmyndin að þessu er fara til vera a bendi til fyrsta hnút í tengda listanum mínum, og ég hef frumstilla það að núll, vegna þess að ég hef ekki úthlutað allir raunverulegur hnúður bara ennþá. Svo táknar þetta, pictorially, hvað við sá smá stund síðan í myndinni sem sem bendillinn á langt vinstri hönd. Svo núna, það bendi er ekki með ör. Það er í staðinn bara null. En það sýnir hvað verður veffang fyrstu raun hnút á þessum lista. Þannig að ég hef innleitt það er alþjóðlegt vegna þess, eins og þú munt sjá, allt þetta program hjartarskinn í lífinu er að innleiða tengda lista fyrir mig. Nú hef ég fengið nokkrar frumútgáfur hér. Ég ákvað að innleiða aðgerðir eins eyðingu, innsetning, rannsakandi, og traversal - síðasta bara að vera ganga yfir lista, prentun út þætti sína. Og nú er hér aðal venja minn. Og við munum ekki eyða of miklum tíma í þetta þar sem þetta er tegund af, vonandi gamall hattur núna. Ég ætla að gera eftirfarandi, meðan notandinn vinnur. Svo einn, ég ætla að prenta út þessari valmynd. Og ég hef sniðinn það sem eðlilega og ég gat. Ef notandinn slær í einu, sem þýðir þeir vilja til að eyða eitthvað. Ef notandinn slær í tvennt, sem þýðir þeir vilja til að setja eitthvað. Og svo framvegis. Ég ætla að þá hvetja þá fyrir stjórn. Og þá er ég að fara að nota GetInt. Þannig að þetta er mjög einfalt menuing tengi þar sem þú þarft bara að slá fjölda kortlagning til einn af þeim skipunum. Og nú hef ég fallegu hreinu skipta yfirlýsingu sem er að fara að kveikja á hvað notandinn slegið inn Og ef þeir slegið einn, ég kalla eyða og brjóta. Ef þeir slegið tvær, ég kalla setja og brjóta. Og nú eftir ég hef sett hver af þessum á sömu línu. Þetta er bara stylistic ákvörðun. Venjulega höfum við séð eitthvað svona. En ég ákvað bara, hreinskilnislega, program minn horfði meira læsileg vegna það var aðeins fjórum tilfellum til bara lista þetta svona. Algerlega lögmæta notkun stíl. Og ég ætla að gera þetta svo lengi sem notandi hefur ekki slegið núll, sem ég ákveðið vilja meina að þeir vilja til að hætta. Svo nú taka það sem ég er að fara að gera hér. Ég ætla að losa listann greinilega. En meira um það í aðeins augnablik. Skulum fyrst að keyra þetta forrit. Svo láta mig gera stærri flugstöðinni glugga, punktur rista lista 0. Ég ætla að fara á undan og setja af slá tvær, a tala eins 50, og nú þú munt sjá á listanum er nú 50. Og texti minn skrunað bara upp a hluti. Svo nú taka listinn inniheldur fjöldi 50. Skulum gera annað innskot með því að taka tvö. Skulum tegund í fjölda eins og einn. Listi er nú einn, fylgt eftir með 50. Þannig að þetta er bara texta framsetning af listanum. Og við skulum setja eitt auknum fjölda eins fjölda 42, sem er vonandi að fara að enda upp í the miðja, vegna Þetta forrit einkum konar það atriði sem það setur inn þá. Þannig að það að við höfum það. Super einfalt forrit sem gæti algerlega hafa notað array, en ég skyldir vera með tengda lista bara svo ég geti virk vaxa og minnka hana. Þannig að við skulum kíkja á leit, ef ég hlaupa stjórn þriggja, ég vil leita fyrir, segja, fjölda 43. Og ekkert var greinilega fann, vegna þess að ég fékk aftur ekkert svar. Svo skulum gera þetta aftur. Leita. Skulum leita að 50, eða öllu heldur að leita fyrir 42, sem hefur a ágætur lítið lúmskur merkingu. Og ég fann tilgang lífsins þar. Númer 42, ef þú veist ekki tilvísun, Google það. Allt í lagi. Svo hvað hefur þetta forrit gert fyrir mig? Það er bara leyft mér að setja svona langt og leita fyrir þætti. Skulum hratt áfram, þá til sem virka við leit á á mánudaginn sem beitu. Svo þessari aðgerð, halda ég, leitar liður í listanum með því að fyrst einn, vekur notanda og þá kalla GetInt að fá raunverulegt int sem þú vilt leita að. Þá taka þetta. Ég ætla að búa til tímabundinn breytu í samræmi 188 heitir bendiprik - PTR - hefði kallað það neitt. Og það er bendi hnút vegna þess að ég sagði hnút * þar. Og ég er að virkja það til að vera jafn fyrst svo að ég hef í raun minn fingur, svo að segja, á mjög Fyrsta þáttur af listanum. Þannig að ef hægri hönd mín hér er PTR Ég er benda á það sama sem fyrst bendir á. Svo nú aftur í númerið, hvað gerist næst - þetta er algengt mynstur þegar iterating yfir uppbyggingu eins tengda listanum. Ég ætla að gera eftirfarandi þegar bendillinn er ekki jafn núll Svo á meðan fingur minn er ekki að benda á einhvern null gildi, ef bendillinn arrow n jafnt n. Við munum taka fyrsta sem n er það sem notandinn slegið í á GetInts kalla hér. Og bendi arrow n þýðir hvað? Jæja ef við förum aftur til myndina hér, ef ég hef fingur sem bendir á sem fyrst hnút inniheldur níu, á arrow þýðir í raun að fara til að hnút og grípa gildi á staðsetningu n, í þessu tilfelli, the gögn svæðið merkt n. Sem innskot - og við sáum þetta nokkrum vikum síðan þegar einhver spurði - þetta setningafræði er ný, en það er ekki gefa okkur völd sem við ekki þegar hafa. Hvað var þetta orðasamband jafngildir nota punktur sýndur og stjörnu par vikum síðan þegar við skrældar aftur þetta lag svolítið snemma? STUDENT: [inaudible]. Ræðumaður 1: Nákvæmlega, það var stjörnu, og þá var það stjörnu punktur n, með sviga hér, sem lítur, hreinskilnislega, held ég mikið meira dulinn að lesa. En stjörnu músina, eins og alltaf, þýðir fara þangað. Og þegar þú ert þarna, hvaða gögn sviði viltu aðgang? Jæja þú notað punktur tákn til aðgang A structs gögn sviði, og ég sérstaklega vil n. Frankly, myndi ég halda því fram þetta er bara erfiðara að lesa. Það er erfiðara að muna þar gera sviga fara, stjörnu og allt það. Svo að heimurinn samþykkt nokkrar nokkur dæmi um setningarleg sykur, svo að segja. Bara kynþokkafullur leið til að segja, þetta jafngildir, og kannski meira innsæi. Ef bendillinn er örugglega músina, arrow auðkennisstillingar þýðir fara þangað og finna svæðið í þessu tilfelli kallast n. Svo ef ég finn það, taka það sem ég geri. Ég prenta bara út, ég fann prósent i, tengja í gildi fyrir þessi int. Ég kalla sofa í eina sekúndu bara að góður af hlutum að gera hlé á skjánum til gefa notandanum annað að gleypa hvað bara gerðist. Og svo ég brjóta. Annars, hvað geri ég? Ég uppfæri bendi til jafn bendillinn arrow næst. Svo bara að vera skýr, þetta þýðir fara þar með gamla skólann tákn mín. Þannig að þetta þýðir bara að fara whatever þú ert að benda á, sem í mjög Fyrsta mál er ég að benda á The strúktúr með níu í það. Þannig að ég hef farið þangað. Og þá þýðir punktur merki, fá verðmæti á næst. En verðmæti, jafnvel þó að það er dregið Sem þröngt, er bara tala. Það er tölugildi heimilisfang. Þannig að þetta einni línu af kóða, hvort skrifað svona, því meira dulinn hátt, eða eins og þetta, örlítið meira leiðandi leið, þýðir bara hreyfa hönd mína frá fyrsta hnút til næstu einn, og svo næsta einn, og þá næsta einn, og svo framvegis. Þannig að við munum ekki búa á hinn útfærslur af setja inn og eyða og traversal, fyrstu tveir af sem eru nokkuð við sögu. Og ég held að það er auðvelt að fá glataður þegar að gera það munnlega. En hvað getum við gert hér er reyna að ákvarða hvernig best að gera þetta sjónrænt. Þar sem ég myndi leggja til að ef við langar að setja þætti inn á þetta núverandi lista, sem hefur fimm þætti - 9, 17, 22, 26, og 33 - ef ég væri að fara að framkvæma þetta í kóða, ég þarf að íhuga hvernig á að fara um að gera þetta. Og ég myndi leggja að taka barn stíga þar, í þessu tilfelli ég meina, hvað eru mögulegar sviðsmyndir sem við gætir fundur í almennt? Við framkvæmd innskoti fyrir tengt listi, þetta gerist bara að vera sérstakur dæmi um stærð fimm. Jæja, ef þú vilt setja inn númerið, eins og segir töluna einn, og viðhalda raðað röð, þar augljóslega er númer eitt að fara í þetta tiltekna dæmi? Eins og í upphafi. En hvað er áhugavert er að ef þú vilt setja inn einn í þessu lista, hvað sérstakt bendillinn þarf að uppfæra virðist? Fyrst. Þannig að ég myndi halda því fram, þetta er fyrsta málið að við might vilja til íhuga, að atburðarás þar innsetning á upphaf listanum. Skulum ríf burt kannski eins auðvelt eða jafnvel auðveldara mál, tiltölulega séð. Segjum Ég vil setja á númer 35 í raðað röð. Það tilheyrir augljóslega þarna. Svo hvað músina augljóslega er að fara að verða að vera uppfærðar í þeirri atburðarás? Bendillinn 34 er að verða ekki null en heimilisfang strúktúr inniheldur fjölda 35. Svo er það málið tveir. Svo þegar, ég konar quantizing hversu mikil vinna ég þarf að gera hér. Og að lokum, hið augljósa miðja málið er reyndar í miðju, ef ég vil setja eitthvað eins og segir 23. sem fer milli 23 og 26, en nú hlutirnir fá smá meira þátt því hvað ábendingum þarf að breyta? Svo 22 þarf augljóslega að breyta vegna þess að hann getur ekki bent á 26 lengur. Hann þarf að benda á nýja hnút sem Ég ætla að úthluta því að hringja malloc eða einhver samsvarandi. En þá þarf ég líka að nýja hnút, 23 í þessu tilfelli, til að hafa músina sína bendir á hverjum? 26. Og það er að fara að vera Röð aðgerða hér. Vegna þess að ef ég geri þetta heimskulega og ég til að byrja dæmis í upphafi lista, og markmið mitt er að setja 23. Og ég athuga, er það tilheyri hér, nálægt níu? Nei Er það tilheyri hér, við hliðina á 17? Nei Er það tilheyrir hér við hliðina á 22? Já. Nú ef ég er heimskur hér, og ekki hugsa þetta í gegnum, gæti ég úthluta nýjum hnút mín fyrir 23.. Ég gæti uppfæra músina frá hnúturinn heitir 22, bendir það á nýja hnút. Og þá hvað þarf ég að uppfæra bendillinn nýju Hnútur til að vera? STUDENT: [inaudible]. Ræðumaður 1: Einmitt. Benda á 26.. En dammit ef ég vissi ekki þegar uppfæra Bendillinn 22 er að benda á þetta strákur, og nú hef ég munaðarlaus, en afgangurinn á listanum, svo að segja. Svo til starfsemi hér er að fara að vera mikilvægur. Til að gera þetta gæti ég stela, segja, sex sjálfboðaliðum. Og við skulum sjá hvort við getum ekki gert þetta sjónrænt í stað kóða-vitur. Og við höfum sumir yndislega streitu kúlur fyrir þig í dag. OK, hvernig væri einn, tveir, í aftur - á endanum. þrír, fjórir, bæði af þér krakkar á enda. Og fimm, sex. Jú. Fimm og sex. Allt í lagi og við munum koma að ykkur næst. Allt í lagi, komdu upp. Allt í lagi, þar sem þú ert upp hér fyrst, viltu vera einn vandræðalega í Google Glass hér? Allt í lagi, svo, OK, Gler, taka upp myndskeið. OK, þú ert góður til fara. Allt í lagi, svo ef þú krakkar geta komið yfir hér, ég hef undirbúið fyrirfram nokkrar tölur. Allt í lagi, komdu hérna. Og hvers vegna ertu ekki að fara svolítið frekar þannig. Og við skulum sjá, hvað er nafn þitt, með Google Glass? STUDENT: Ben. Ræðumaður 1: Ben? OK, Ben, verður þú að vera fyrstur, bókstaflega. Þannig að við erum að fara að senda þér til loka stigi. Allt í lagi, og nafn þitt? STUDENT: Jason. Ræðumaður 1: Jason, OK þú munt vera númer níu. Svo ef þú vilt að fylgja Ben þannig. STUDENT: Jill. Ræðumaður 1: Jill, þú ert að fara að vera 17, sem ef ég hefði gert þetta meira greindur, hefði ég byrjaði á hinum endanum. Þú ferð þessa leið. 22. Og þú ert? STUDENT: Mary. Ræðumaður 1: María, munt þú vera 22.. Og nafn þitt er? STUDENT: Chris. Ræðumaður 1: Chris, munt þú vera 26.. Og þá loks. STUDENT: Diana. Ræðumaður 1: Diana, munt þú vera 34.. Svo þú kemur á hérna. Allt í lagi, svo fullkominn raðað panta nú þegar. Og við skulum fara á undan og gera þetta svo að við getum í raun - Ben þú ert bara svona að leita út í hvergi þar. OK, þannig að við skulum fara á undan og lýsa þessu nota vopn, mikið eins og ég var, einmitt, hvað er að gerast. Svo fara á undan og gefa ykkur sem fótur eða tveir á milli handa. Og fara á undan og benda með einni hendi til hver sem þú ættir að vera að benda á byggt á þessu. Og ef þú ert null bara benda beint niður á gólf. OK, svo góður. Svo nú höfum við tengda lista, og láta mig leggja til að ég spila hlutverk PTR, svo ég mun ekki nenna vopnaður þessu í kring. Og þá - einhver heimskur samningur - þú getur hringt í þetta allt sem þú vilt - forvera músina, pred bendiprik - það er bara gælunafn við gáfum í dæmi um kóða okkar til vinstri handar. Hins vegar að fara að halda utan um hver er hver í eftir atburðarás. Svo ráð, fyrst ég vil reyta burt sem fyrst dæmi um innsetning, segja 20, inn á listann. Þannig að ég ætla að fara að þurfa einhvern til að staðfest fjölda 20 fyrir okkur. Þannig að ég þarf að malloc einhvern frá áhorfendum. Komdu upp. Hvað er nafn þitt? STUDENT: Brian. Ræðumaður 1: Brian, allt í lagi, þannig að þú skal hnúturinn inniheldur 20. Allt í lagi, komdu hérna. Og vitanlega, þar er Brian tilheyra? Svo, í the miðja af - í raun, Bíddu. Við erum að gera þetta út af röð. Við erum að gera þetta mikið erfiðara en það þarf að vera í fyrstu. OK, við erum að fara að losa Brian og realloc Brian eins fimm. OK, svo nú viljum við setja Brian eins fimm. Svo koma á hérna við hliðina á Ben fyrir réttlátur a augnablik. Og þú getur væntanlega sagt þar sem þessi saga er að fara. En við skulum hugsa vel um röð aðgerða. Og það er einmitt þetta sjón það er að fara að stilla upp með því dæmi um kóða. Svo hér er ég hef PTR bendir upphaflega ekki Ben, í sjálfu sér, en hvað gildi sem hann inniheldur, sem í þessu tilfelli er - hvað er nafnið þitt aftur? STUDENT: Jason. Ræðumaður 1: Jason, svo bæði Ben og ég er benda á Jason á þessari stundu. Svo nú þarf ég að ákveða, hvar Brian tilheyra? Svo það eina sem ég hef aðgang að núna er hann n gögn atriði. Þannig að ég ætla að athuga, er Brian minna en Jason? Svarið er satt. Svo þarf það nú að gerast, í réttri röð? Ég þarf að uppfæra hversu margar ábendingar samtals í þessari sögu? Þar hönd mín er enn að benda á Jason, og hönd þín - ef þú vilt legg hönd þína eins, konar, ég veit ekki, spurningarmerki. OK, gott. Allt í lagi, svo þú hefur nokkrar frambjóðendur. Annaðhvort Ben eða ég eða Brian eða Jason eða allir aðrir, sem ábendingum þarf að breyta? Hversu margir samtals? OK, svo tveir. Bendillinn minn skiptir ekki máli lengur því ég er bara tímabundið. Svo er það þessir tveir gaurar, væntanlega, bæði Ben og Brian. Svo láta mig leggja til að við uppfærum Ben, þar sem hann er fyrst. Fyrsti þátturinn af þessum lista er nú að fara að vera Brian. Svo Ben benda á Brian. OK, nú hvað? Sem fær bent á hvern? STUDENT: [inaudible]. Ræðumaður 1: OK svo hefur Brian að benda á Jason. En ég hef misst utan um þessi músina? Ég veit hvar Jason er? STUDENT: [inaudible]. Ræðumaður 1: Ég, þar sem ég er tímabundið músina. Og væntanlega hef ég ekki breytt að benda á nýja hnút. Svo við getum einfaldlega hafa Brian punkt á hver ég er að benda á. Og við erum að gera. Svo málið einn, innsetningu á að upphafið af listanum. Það voru tveir helstu skref. Eitt verðum við að uppfæra Ben, og þá við verðum einnig að uppfæra Brján. Og svo ég þarf ekki að standa traipsing gegnum the hvíla af the lista, því við fundum þegar hann staðsetningu, því að hann átti að vinstri á fyrstu frumefni. Allt í lagi, svo laglegur einfaldur. Í raun finnst eins og við erum næstum gera þetta of flókið. Svo skulum nú ríf burt enda af listanum og sjá hvar flókið byrjar. Þannig að ef nú, Alloc ég frá áhorfendum. Einhver vilja til að spila 55? Allt í lagi, sá ég hönd þína fyrst. Komdu upp. Já. Hvað er nafn þitt? STUDENT: [inaudible]. Ræðumaður 1: Habata. OK, komdu upp. Þú munt vera númer 55.. Svo er, að sjálfsögðu, tilheyra í lok listanum. Svo skulum spila á uppgerð með mér vera PTR fyrir réttlátur a augnablik. Þannig að ég ætla fyrst að fara að benda á hvað Ben er að benda á. Við erum bæði bendir nú Brian. Svo 55 er ekki minna en fimm. Þannig að ég ætla að uppfæra sjálfur með bendir til næsta músina Brian er, sem nú er auðvitað Jason. 55 er ekki minna en níu, svo Ég ætla að uppfæra PTR. Ég ætla að uppfæra PTR. Ég ætla að uppfæra PTR Ég ætla að uppfæra PTR. Og ég ætla að - Hmm, hvað er nafnið þitt aftur? STUDENT: Diana. Ræðumaður 1: Diana er að benda, að sjálfsögðu, á núll með vinstri hendi hennar. Svo hvar Habata raun tilheyra greinilega? Til vinstri, hér. Svo hvernig veit ég að setja hana hér Ég held að ég hef ruglaður upp. Því það er PTR list þetta augnablik í tíma? Null. Svo jafnvel þó sjónrænt, getum við augljóslega sjá allar þessar krakkar hér á sviðinu. Ég hef ekki haldið utan um fyrri maður á listanum. Ég hef ekki fingur benda, í þessu tilfelli, hnúturinn númer 34. Þannig að við skulum í raun að byrja þetta aftur. Svo nú er ég í raun ekki þörf annað staðbundin breytu. Og þetta er það sem þú munt sjá í Raunveruleg dæmi C kóða, þar sem ég fer, þegar ég uppfæri hægri hönd mína að benda Jason, þannig að fara Brian bak, ég betra að byrja að nota vinstri hendina mína uppfæra þar sem ég var, svo að þegar ég fer í gegnum þennan lista - meira vandræðalega en ég ætlaði nú hér sjónrænt - Ég ætla að komast að því endir á listanum. Þessi hönd er enn null, sem er nokkuð gagnslaus, annað en að gefa til kynna Ég er greinilega í lok listanum, en nú að minnsta kosti ég hef þetta forvera bendillinn bendir hér, svo nú hvað hendur og hvað vísbendingar þurfa að uppfæra? Hvers hönd viltu að endurstilla fyrst? STUDENT: [inaudible]. Ræðumaður 1: Allt í lagi, svo er Diana. Hvar viltu að benda Vinstri Diana er bendi á? At 55, væntanlega, þannig að við höfum sett þarna. Og hvar ætti 55 bendi fara? Down, fulltrúi null. Og hendurnar, á þessum tímapunkti, ekki máli vegna þess að þeir voru bara tímabundnar breytur. Svo nú erum við búin. Svo til viðbótar flókið þarna - og það er ekki það erfitt að framkvæma, en við þurfum öðru breytu til að gera viss um að áður en ég flyt rétt minn vegar uppfæri ég verðmæti vinstri handar vegar pred músina í þessu tilfelli, þannig að sem ég hef kom heimamönnum músina að halda utan um hvar ég var. Nú sem innskot, ef þú ert að hugsa þetta gegnum, þetta er eins og það er lítið pirrandi að þurfa að halda utan um þessa vinstri hendi. Hvað myndi annar lausn að þetta vandamál hafa verið? Ef þú got að endurhönnun gögn uppbyggingu við erum að tala gegnum núna? Ef þetta bara svona líður svolítið pirrandi að hafa, eins og, tvo punkta fara í gegnum listann, sem annars gæti hafa, í fullkomnum heimi, haldið upplýsingar sem við þurfum? Já? STUDENT: [inaudible]. Ræðumaður 1: Einmitt. Rétt svo að það er í raun áhugavert sýkill um hugmynd. Og þessi hugmynd um fyrri músina, bendir á fyrri frumefni. Hvað ef ég felst bara að inni á listanum sig? Og það er að fara að vera erfitt að sjón þetta án allra pappír falla á gólfið. En geri ráð fyrir að þessir krakkar nota bæði höndum þeirra að hafa fyrri músina, og næsta músina, þar með innleiða það sem við munum kalla tvöfalt tengda listanum. Sem myndi leyfa mér að raða á baka, miklu auðveldara án mín, að forritari, að þurfa að halda fylgjast handvirkt - sannarlega höndunum - um þar sem ég hafði verið áður í listanum. Þannig að við munum ekki gera það. Við munum halda það einfalt því það er fara að koma í verð, tvöfalt mikið pláss fyrir ábendingum, ef þú vilt seinni. En það er örugglega algengt gögn uppbygging þekktur sem tvöfalt tengd lista. Skulum gera endanlega dæmi hér og setja þessir krakkar út af eymd þeirra. Svo malloc 20. Komdu upp úr hillu þar. Allt í lagi, hvað er nafnið þitt? STUDENT: [inaudible]. Ræðumaður 1: Fyrirgefðu? STUDENT: [inaudible]. Ræðumaður 1: Demeron? OK komið upp. Þú skalt vera 20. Þú augljóslega ert að fara að tilheyra milli 17 og 22. Svo láta mig læra lexíu mína. Ég ætla að byrja músina benda á Brian. Og ég ætla að hafa vinstri hendina á mér aðeins endurnýja til Brian og ég flyt til Jason, stöðva er 20 minna en níu? Nei Er 20 minna en 17? Nei Er 20 minna en 22? Já. Svo ábendingum hvað eða hendur þarf að breyta þar sem þeir eru að benda núna? Svo við getum gert 17 benda á 20.. Svo það er allt í lagi. Hvar viljum við benda bendillinn þinn núna? Á 22.. Og við vitum hvar 22 er, aftur takk til tímabundinnar músina mína. Þannig að við erum í lagi þarna. Svo vegna þessa tímabundna geymslu Ég hef haldið utan um hvar allir eru. Og nú þú getur sjónrænt farið inn þar sem þú tilheyrir, og nú þurfum við 1, 2, 3, 4, 5, 6, 7, 8, 9 streitu boltar, og a umferð af lófaklapp fyrir þessir krakkar, ef við gátum. Fallega gert. [Applause] Ræðumaður 1: Allt í lagi. Og þú getur haldið stykki af pappír sem mementos. Allt í lagi, svo, treystu mér það er mikið auðveldara að ganga í gegnum það með menn en það er með raunverulegum kóða. En hvað sem þú munt finna í bara smá stund nú er, að sami - ó, þakka þér. Þakka þér - er að þú munt komast að því að sömu gögn uppbyggingu, tengda lista, getur raunverulega að nota sem byggja blokk til jafnvel meira háþróuð gögn uppbygging. Og átta sig of þemað hér er að við höfum alveg kynnt meira flókið í framkvæmd þessarar reiknirit. Innsetning, og ef við fórum í gegnum það, Eyðingaskrá og rannsakandi, er lítið flóknara en það var með fjölda. En við öðlast kraft. Við fáum aðlagandi gögn uppbygging. En aftur, borga við verð um að hafa sumir viðbótar flókið, bæði í útfæra hana. Og við erum gefið upp handahófi aðgang. Og til að vera heiðarlegur, það er ekki nokkur ágætur hreinsa renna ég get gefið þér að segir hér er ástæðan tengda lista er betra en fylki. Og láta það á því. Þar sem þema reoccurring nú, jafnvel meira svo á næstu vikum, er að það er ekki endilega A rétt svar. Þetta er ástæða þess að við höfum sérstakan ás af hönnun fyrir setur vandamál. Það verður mjög samhengi næmur hvort sem þú vilt nota þessi gögn byggingu eða að einn, og það mun ráðast á það sem skiptir máli til þín í skilmálar auðlinda og margbreytileika. En láta mig leggja til að hugsjón gögn uppbyggingu, Gral, væri eitthvað sem er stöðugt tíma, óháð því hversu mikið efni er inni það, myndi það ekki vera ótrúlegt ef gögn uppbygging skilað svör í föstu tíma. Já. Þetta orð er í gríðarstór orðabókinni. Eða nei, þetta orð er ekki. Eða einhver slík vandamál þar. Jæja við skulum sjá hvort við getum ekki að minnsta kosti taka skref í átt að. Leyfðu mér að leggja ný gögn uppbygging sem er hægt að nota fyrir mismunandi hluti, í þessu tilfelli kallast tæti töflu. Og svo við erum í raun aftur að glancing á fjölda, í þessu tilfelli, og nokkuð geðþótta, hef ég dregið þetta kjötkássa borð eins fjölda við konar tvívíð fylki - eða öllu heldur það er lýst hér sem tveir víddar array - en þetta er bara fylki af stærð 26, þannig að ef við kalla array borð, borð krappi núll er rétthyrningur efst. Tafla krappi 25 er rétthyrningur neðst. Og þetta er hvernig ég gæti teikna gögn uppbygging sem ég vil geyma fólks nöfn. Svo til dæmis, og ég mun ekki draga heild hlutur hér á höfuðið, ef ég hafði þetta fylki, sem ég ætla nú að fara að hringja í kjötkássa borð, og þetta er aftur Staðsetning núll. Þetta er hér staðsetning einn, og svo framvegis. Ég halda því fram að ég vil nota þessi gögn uppbygging, fyrir sakir umræðu, að geyma nöfn fólks, Alice og Bob og Charlie og öðrum slíkum nöfnum. Svo hugsa um þetta núna og upphaf á, segja, orðabók með fullt af orðum. Þeir koma til að vera nöfn í dæmi okkar hér. Og þetta er allt of germane, kannski, að innleiða stafa afgreiðslumaður, eins og við gæti til Heimadæmi sex. Þannig að ef við höfum fjölda heildarstærð 26 þannig að þetta er 25th staðsetning neðst, og ég halda því fram að Alice er fyrsta orðið í orðabók nöfn sem ég vil setja inn RAM, í þessum gögnum uppbyggingu, eru þar eðlishvöt að segja þér að Alice er nafn ætti að fara í þessu fylki? Við höfum 26 valkosti. Þar sem við viljum setja hana? Við viljum hana í krappi núll, ekki satt? A fyrir Alice, við skulum kalla það núll. Og B mun vera einn, og C verða tveir. Þannig að við erum að fara að skrifa Alice nafn upp hér. Ef við setja þá Bob, hans nafn mun fara hér. Charlie mun fara hér. Og svo framvegis niður í gegnum þessi gögn uppbygging. This er a dásamlegur gögn uppbygging. Hvers vegna? Jæja hvað er í gangi tími setja nafn manna er í þessu gögn uppbygging núna? Í ljósi þess að þessi tafla er hrint í framkvæmd, sannarlega, sem fylki. Jæja það er stöðug skipti. Það er til einn. Hvers vegna? Jæja hvernig ákveða þig þar Alice tilheyrir? Þú lítur á sem bréf af hennar nafni? The fyrstur. Og þú getur fengið það, ef það er a band, því bara að horfa á band krappi núll. Svo 0 eðli band. Það er auðvelt. Við gerðum það í Grafhvelfing verkefnatíma vikum. Og síðan þegar þú veist það er Alice bréf er höfuðborg A, getum við draga burt 65 eða Capital sig, sem gefur okkur núll. Þannig að við vitum nú að Alice tilheyrir á stað núll. Og gefið bendi að þessum gögnum uppbyggingu, af einhverju tagi, hversu lengi er það tekur mig að finna stað núll í fylki? Bara eitt skref, rétt það er stöðug tími vegna þess að handahófi aðgang við Fyrirhugað var eiginleiki fylki. Svo í stuttu máli, vangaveltur út hvað vísitala af nafn Alice er, sem er í þetta mál, er A, eða við skulum bara leysa að til þess að núll, þar sem B er ein og C er tveir, vangaveltur það út er stöðug skipti. Ég er bara að horfa á fyrsta staf hennar, vangaveltur út hvar núll er array er einnig fasti skipti. Svo tæknilega það er eins og tvö skref núna. En það er samt stöðug. Svo við köllum að stór O einn, þannig að við höfum sett Lísa í þessari töflu í föstu tíma. En auðvitað, ég er að barnaleg hérna, ekki satt? Hvað ef það er Aron í bekknum? Eða Alicia? Eða einhver önnur nöfn byrja með A. Hvert erum við að fara að setja sem maður, ekki satt? Ég meina, núna það er bara þrjú fólk á töflunni, svo kannski við ætti að setja Aron á stað núll einn tveir þrír. Einmitt, ég gat sett hér. En þá, ef við reynum að setja Davíð inn þessi listi, hvar Davíð fara? Nú byrjar kerfið okkar brjóta niður, ekki satt? Því nú endar David upp hér ef Aron er í raun hér. Og svo nú þetta allt hugmynd af having a hreinn gögn uppbygging sem gefur okkur föstu ísetningar tími er ekki lengur föstu tíma, vegna þess að ég þarf að athuga, ó, Damnit, einhver er nú þegar á stað Lísa. Leyfðu mér að rannsaka restina af þessum gögnum uppbyggingu, útlit fyrir a blettur til að setja einhver eins og nafn Arons. Og svo að of er farin að taka línulega tíma. Þar að auki, ef þú vilt nú að finna Aron í þessum gögnum uppbyggingu, og þú stöðva, og nafn Arons er ekki hér. Best væri að þú bara segja Aron ekki í gögn uppbygging. En ef þú byrjar að gera pláss fyrir Aron þar sem það ætti að hafa verið D eða E, þú, versta tilfelli, verður að athuga allt gögn uppbygging, í þeim tilvikum devolves í eitthvað línuleg á stærð af the borð. Svo allt í lagi, ég laga þetta. Vandamálið hér er að ég hafði 26 þættir í þessu fylki. Leyfðu mér að breyta því. Úpps. Leyfðu mér að breyta því svo að frekar að vera á stærð 26 talsins, taka eftir the botn Vísitalan er að fara að breyta til n mínus 1. Ef 26 er greinilega of lítið fyrir 'mönnum nöfn, vegna þess að það er þúsundir af nöfn í heiminum, við skulum bara gera í 100 eða 1000 eða 10.000. Við skulum bara úthluta miklu meira pláss. Jæja það þýðir ekki endilega lækka líkurnar á því að við munum ekki hafa tvo fólk með nöfn byrja með A og svo, þú varst að fara að reyna að setja Nöfn á núll staðsetningu enn. Þeir eru enn að fara að rekast, sem þýðir að við þurfum enn að lausn til að setja Alice og Aron og Alicia og öðrum nöfn byrja með annars staðar. En hversu mikið vandamál er þetta? Hver er líkur á að þú hafa árekstra í gögnum uppbyggingu svona? Jæja, láttu mig - við munum koma aftur við þeirri spurningu hér. Og líta á hvernig við gætum leysa það fyrst. Leyfðu mér að draga upp þessa tillögu hér. Það sem við lýst bara er reiknirit, leitandi kallast línuleg leit þar, ef þú reyndir að setja eitthvað hér í þessum gögnum uppbyggingu, sem er kallað kjötkássa borð, og það er ekkert pláss þarna, þú sannarlega rannsaka gögn uppbygging stöðva, er þetta í boði? Er þetta í boði er þetta í boði? Er þetta í boði? Og þegar það er loksins, setja þér Nafnið sem þú ætlaðir upphaflega annars staðar á þeim stað. En í versta falli, eina staðnum gæti verið mjög botn af the gögn uppbyggingu, enda í fylkinu. Svo línuleg leit, í versta tilfelli, devolves í línulega reiknirit þar Aron, ef hann gerist að vera sett síðasta í þessum gögnum uppbyggingu, gæti hann rekast á við þessa fyrsta stað, en þá enda með óheppni á enda. Svo er þetta ekki fasti tími Gral fyrir okkur. Þessi nálgun innsetning þætti í senda gögn uppbygging kallast kjötkássa borð virðist ekki vera fasti skipti að minnsta kosti ekki í almennu máli. Það getur flytjast í eitthvað línuleg. Svo hvað ef við leysa árekstra nokkuð öðruvísi? Svo er hér flóknari nálgun að það er enn kallað kjötkássa borð. Og með kjötkássa, Sem innskot, hvað Ég meina er vísitala sem Ég nefndi áðan. Til kjötkássa eitthvað getur verið hugsað sem sögn. Svo ef þú kjötkássa Alice er nafn, kjötkássa virka, svo að segja, eiga að skila inn fjölda. Í þessu tilfelli er núll ef hún tilheyrir í Staðsetning núll, einn ef hún tilheyrir í staðsetning einn, og svo framvegis. Svo kjötkássa virka minn svona langt hefur verið frábær einfalt, bara að horfa á fyrsti stafurinn í nafni einhvers. En kjötkássa virka tekur sem inntak sumir stykki af gögnum, sem band, int, hvað sem er. Og það spits út yfirleitt númer. Og þessi tala er þar að gögn þáttur tilheyrir í gögn uppbygging þekkt hér sem kjötkássa borð. Svo bara innsæi, þetta er aðeins öðruvísi samhengi. Þetta reyndar er vísað til dæmi þátttöku afmæli, þar það gæti verið eins margir eins og 31 dagar í mánuðinum. En hvað gerði þessi manneskja ákveður að gera í árekstur? Samhengi vera nú, ekki árekstur nöfn, en árekstur á afmæli, ef tveir menn hafa sömu afmæli á 2. október, til dæmis. STUDENT: [inaudible]. Ræðumaður 1: Já, svo hér höfum við að fá meira af tengd listum. Svo lítur það svolítið öðruvísi en við brá það áðan. En við virðast hafa til fjölda á vinstri hönd. Það er ein vísitala, fyrir ekkert einkum ástæða. En það er samt fylki. Það er fylki af ábendingum. Og hver af þeim þáttum, sem hver um þessir hringir eða skástrik - The skástriki fulltrúi null - hvert þessara ábendingum er virðist benda til hvaða gögn uppbygging? A tengd lista. Svo nú höfum við getu til harður kóða inn í kerfi okkar the stærð af the borð. Í þessu tilviki, við vitum að það er aldrei meira en 31 daga í mánuði. Svo hart erfðaskrá gildi eins 31 er sanngjarn í því samhengi. Í tengslum við nöfn, harður erfðaskrá 26 er ekki óraunhæft það fólks nöfn byrja aðeins með, til dæmis, stafrófið þátttöku A í gegnum Z. Við getum troða þeim öllum í þessi gögn uppbygging svo lengi sem, þegar við fáum árekstur, við ekki setja nöfn hér, við höldum í stað þessara frumna ekki eins strengir sig, en eins og ábendingum til, til dæmis, Alice. Og þá Alice getur haft annað bendi á annað nafn byrja með A. Og Bob fer í raun hérna. Og ef það er annað nafn sem byrjar með B, endar hann upp hérna. Og svo hvert atriði af þessu Tafla tvö, ef við hannað þetta lítið meira snjall - koma á - ef við hannað þetta aðeins meira snjall, nú verður aðlagandi gögn uppbygging, þar er enginn harður takmörk hversu margir þættir sem þú getur sett inn inn í það vegna þess að ef þú þarft árekstur, það er fínt. Bara fara á undan og auka við það að hvað við sáum svolítið síðan var þekktur sem tengd lista. Jæja við skulum hlé fyrir réttlátur a augnablik. Hverjar eru líkurnar á árekstri í fyrsta lagi? Einmitt, kannski er ég yfir að hugsa, kannski Ég er yfir verkfræði þetta vandamál, vegna þess að þú veist hvað? Já, ég get komið upp með handahófskennt dæmi burt the toppur af minn höfuð eins Allison og Aron, en í raun, gefið samræmdu dreifingu inntak, sem er sumir af handahófi ísetningar í gögn uppbygging, hvað raunverulega er líkurnar á árekstri? Jæja kemur í ljós, það er í raun frábær hár. Leyfðu mér að alhæfa þetta Vandamálið er eins og þetta. Svo í herbergi á n CS50 nemendur, hvað er líkurnar á því að minnsta kosti tveir nemendur í herberginu hafa sama afmæli? Svo er það það. nokkrar Hund - 200, 300 manns hér og nokkrir hundrað manns heima í dag. Svo ef þú vilja til spyrja okkur hvað er líkurnar á tveggja manna í þessu herbergi hafa sama afmæli, við getum reikna þetta út. Og ég kröfu í raun það eru tveir fólk með sama afmælisdaginn. Til dæmis, er einhver hafa afmæli í dag? Í gær? Á morgun? Allt í lagi, svo mér finnst eins og ég ætla að þurfa að gera þetta 363 eða svo meira sinnum til raunverulega reikna út Ef við höfum árekstur. Eða við gætum bara gert þetta stærðfræðilega frekar en tediously gera þetta. Og leggja eftirfarandi. Svo ég leggja til að við gætum fyrirmynd Líkur á tveggja manna hafa sama afmæli og líkurnar á 1 mínus líkurnar á enginn sem hefur sama afmæli. Svo til að fá þetta, og þetta er bara ímynda sér vegur af að skrifa þetta, fyrir fyrsta manneskjan í herberginu, hann eða hún getur haft hvaða einn af hugsanlegum Afmæli hrokafullur 365 daga á ári, með afsökunarbeiðni til einstaklinga með The 29 febrúar afmæli. Svo er fyrsta manneskjan í þessu herbergi frjáls hafa allir tala um afmæli út af 365 möguleika þannig að við munum gera það 365 deilt með 365, sem er eitt. Næsta manneskja í herberginu, ef markmiðið er að forðast árekstur, getur aðeins hafa hans eða afmæli hennar á hvernig margar mismunandi mögulegar daga? 364. Svo er annað hugtak í þessari tjáningu raun að gera að stærðfræði fyrir okkur með því að draga burt ein hugsanleg dag. Og svo næsta dag, næsta dag, sem Næsta dag niður til heildarfjölda af fólki í herberginu. Og ef við teljum þá, hvað þá líkur ekki allir hafa einstakt afmæli, en aftur 1 mínus að það sem við fáum er tjáning sem hægt er mjög fancifully líta svona út. En það er meira áhugavert að líta á sjónrænt. This er graf þar á x-ásnum er fjölda fólks í herberginu, fjöldi afmælisdaga. On y-ás eru líkurnar af árekstri, tvær manneskjur hafa sama afmæli. Og takeaway frá þessum ferli er að um leið og þú færð að eins 40 nemendur, þú ert upp á 90% líkur combinatorically tveggja fólk eða meira hafa sama afmæli. Og þegar þú færð að eins 58 manns og það er næstum 100% af tækifæri á tveggja fólk í herberginu eru að fara að hafa sama afmæli, jafnvel þó að það er 365 eða 366 mögulegar fötunum, og aðeins 58 manns í herberginu. Bara tölfræðilega þú ert líkleg til að fá árekstra, sem í stuttu máli hvetur þessa umræðu. Að jafnvel þótt við fáum ímynda hér, og byrjar með þessum keðjur, erum við enn fara að hafa árekstra. Svo sem bidur spurningin, hvað er Kostnaður við að gera innskot og úrfellingum í gögn uppbygging eins og þetta? Jæja látið mig leggja - og láta mig fara aftur á skjáinn á hér - ef við höfum n þætti í lista, þannig að ef við erum að reyna að setja n atriði, og við höfum hversu margir samtals fötunum? Segjum 31 Samtals fötunum um er að ræða afmæli. Hvað er hámarkslengd eitt þessara keðjur hugsanlega? Ef aftur er það 31 mögulegt afmæli í hverjum mánuði. Og við erum bara clumping alla - Reyndar er það heimskulegt dæmi. Við skulum gera 26 í staðinn. Þannig að ef raunverulega hafa fólk sem nöfn Byrja með í gegnum Z, þannig að gefa okkur 26 möguleikar. Og við erum að nota gögn uppbygging eins sá sem við sáum bara, þar sem við höfum fylki af ábendingum, sem hver um sig bendir á tengda listanum þar sem Fyrsti listi er allir með nafni Alice. Seinni listinn er hvert með nafn sem byrjar á A, byrja með B, og svo framvegis. Hvað er líklegt lengd hvers þessir listar ef við gerum ráð fallegu hreinu dreifingu nöfn A í gegnum Z yfir allan gögn uppbygging? Það er n fólk í gögn uppbygging deilt með 26, ef þeir eru vel breiða út yfir allt gögn uppbygging. Svo lengd hvert þessara keðjur er n skipt um 26. En í stórum O merki, hvað er það? Hvað er það raunverulega? Svo það er eiginlega bara n, ekki satt? Þar sem við höfum sagt í fortíðinni, sem ugh þú skiptir um 26. Já, í raun er það hraðar. En í orði, það er ekki í grundvallaratriðum allt sem hraðar. Svo við virðist ekki vera allt sem mikið nær þetta Gral. Í raun, þetta er bara línuleg tíma. Heck, á þessum tímapunkti, hví ekki við bara nota einn gríðarstór tengda lista? Hvers vegna eigum við ekki að nota bara einn stór array til að geyma nöfn allir í herberginu? Jæja er enn eitthvað sannfærandi um kjötkássa borð? Er það samt eitthvað sannfærandi um gögn uppbygging sem lítur svona út? Þetta. STUDENT: [inaudible]. Ræðumaður 1: Hægri, og aftur ef það er bara línulegt tíma algrím, og línuleg tími gögn uppbygging, hví ekki ég bara geyma nafn allra í stór array, eða í stórum tengda listanum? Og hætta að gera CS svo mikið erfiðara en það þarf að vera? Hvað er sannfærandi um þetta, jafnvel þótt ég klóra það út? STUDENT: [inaudible]. Ræðumaður 1: Innsetningar eru ekki? Dýrt lengur. Svo ísetningar gæti hugsanlega enn vera stöðug tími, jafnvel þótt gögnin þín uppbygging lítur svona út, fjölda ábendingum, sem hver um sig er að benda á hugsanlega tengda lista. Hvernig gastu náð stöðugum tími innsetningu nöfn? Halda það í framan, ekki satt? Ef við fórna hönnun markmið frá áðan, þar sem við vildum að halda nafn allra, til dæmis, raðað, eða allar tölur á sviðinu raðað, Segjum að við höfum unsorted tengd lista. Það kostar okkur bara eitt eða tvö skref, eins og í tilviki Ben og Brian fyrr, að setja stak í upphaf listanum. Þannig að ef við gerum ekki sama um flokkun allt af nöfnum sem byrja á A eða öllum nöfn sem byrja á B, getum við enn ná föstu tíma innsetningu. Nú leita upp Lísa eða Bob eða hvaða nafn almennt er enn það? Það er stór O af n deilt með 26, í tilvalið tilfelli þar sem allir er undantekningarlaust dreift, þar sem það er eins og margir A er þar sem það eru er Z, sem er líklega óraunhæf. En það er samt línuleg. En hér komum við aftur að þeim punkti af aðfelluþrýstingi merki sé fræðilega satt. En í hinum raunverulega heimi, ef ég halda því fram að program minn getur gert eitthvað 26 sinnum hraðar en þinn, sem program ert þú að fara að vilja að nota? Kveðja eða mín, sem er 26 sinnum hraðar? Raunhæft, sá sem er 26 sinnum hraðar, jafnvel þótt fræðilega reiknirit okkar hlaupa í sama asymptotic hlaupandi tíma. Leyfðu mér að leggja mismunandi lausn að öllu leyti. Og ef þetta er ekki blása þinn hugur, við erum út af uppbyggingu gagna. Svo er þetta það Trie - konar heimskulegt nafn. Það kemur frá retrievals, og orðið er stafsett Trie, T-r-i-e, vegna Námskeiðið sókn hljómar eins Trie. En það er saga á orðinu Trie. Svo er Trie örugglega einhvers konar tré, og það er líka að spila á því orði. Og jafnvel þó að þú getur ekki alveg séð það með þessari visualization, sem Trie er tré uppbyggð, eins og fjölskyldu trénu með einn forfaðir efst og margt barnabörn og frábær barnabörn sem skilur á botn. En hver hnútur í Trie er fylki. Og það er í fylki - og við skulum einfalda málin um stund - það er array, í þessu tilfelli, af stærð 26, þar sem hver hnútur er aftur fylki af stærð 26, þar sem 0 þáttur af því að array táknar A, og síðasti þáttur í hverju slík array táknar Z. Svo ég leggja til, þá, að þessi gögn uppbyggingu, þekktur sem Trie, er hægt að einnig notað til að geyma orð. Við sáum smá stund síðan hvernig við gætum geymt orð, eða í þessu tilfelli nöfn, og við sáum áðan hvernig við getum geymt tölur, en ef við einbeitum nöfn eða strengi hér, taka eftir hvað er áhugavert. Ég halda því fram að nafn Maxwell er inni þessum gögnum uppbyggingu. Hvar sérð þú Maxwell? STUDENT: [inaudible]. Ræðumaður 1: Á vinstri. Svo hvað er áhugavert við þessar upplýsingar uppbygging er frekar en geyma band M-A-X-W-E-L-L sviga núll, allt contiguously, hvað þú gerir í staðinn er eftir. Ef þetta er Trie eins gögn uppbygging, hvert hnúður Hvers er aftur fylki, og þú vilt geyma Maxwell, fyrst vísitölu og svo hnút rót, svo að tala, sem hæstur hnút, á staðsetningu M, hægri, svo u.þ.b. í miðjunni. Og síðan þaðan, fylgja þér músina til barn hnúður, svo að segja. Svo í ættartré skilningi, þú fylgja henni niður. Og það leiða þig á annan hnút á vinstri þar, sem er bara annað array. Og þá ef þú vilt geyma Maxwell, þú finnur músina sem sýnir A, sem er þetta einn hér. Síðan sem þú ferð í næsta hnút. Og tilkynning - þetta er hvers vegna myndin er smá blekkja - þetta hnút líta frábær pínulítill. En til hægri þetta er Y og Z. Það er höfundur bara hefur stytt í mynd þannig að þú í raun og veru sjá hlutina. Annars þessari mynd væri gríðarlega breiður. Svo nú þú vísitölu í staðsetningu X, þá W, þá E, þá L, þá L. Þá hvað er þetta forvitni? Jæja, ef við erum að nota þessa tegund af nýju taka á hvernig á að geyma streng í gögn uppbygging, þú þarft samt að meginatriðum sig burt í gögnum mannvirki sem orð endar hér. Með öðrum orðum, hver af þessum hnúður einhvern veginn þarf að muna að við í raun og veru fylgt öllum þessum ábendingum og eru að fara svolítið brauð Crumb neðst hér á þetta uppbygging til að gefa til kynna M-A-X-W-E-L-L er örugglega í þessum gögnum uppbyggingu. Svo við gætum gert þetta þannig. Hver af hnúður í myndinni við bara sá er einn, fylki af stærð 27. Og það er nú 27, þar á bls setja sex, við munum í raun að gefa þér úrfellingarmerki, svo við getum hafa nöfn eins og O'Reilly og aðrir með úrfellingarmerki. En sama hugmynd. Hver þessara þátta í array bendir á strúktúr hnút, svo bara hnút. Svo er þetta mjög minnir af tengda listanum okkar. Og þá hef ég Boolean, sem ég mun kalla orð, sem er bara að fara að vera satt ef orð endar á þessu hnút í trénu. Það táknar í raun litla þríhyrningur sáum fyrir augnabliki. Þannig að ef orð endar á þeim hnút í tré, að orð reitur verður satt, sem er eðli haka burt, eða við erum að teikna Þessi þríhyrningur, já það er orð hér. Þannig að þetta er Trie. Og nú er spurningin, hvað er í gangi tíma? Er það stór O í n? Er það eitthvað annað? Jæja, ef þú hefur n nöfn í þessum gögnum uppbyggingu, Maxwell vera bara einn af þá, hvað er í gangi tími innsetning eða finna Maxwell? Hvað er í gangi tími innsetning Maxwell? Ef það er n önnur nöfn þegar í töflunni? Já? STUDENT: [inaudible]. Ræðumaður 1: Já, það er lengd um nafn, ekki satt? Sem M-a-x-W-e-L-L þannig að það er eins og þessi reiknirit er stór O sjö. Nú, að sjálfsögðu, að nafn breytileg á lengd. Kannski er það stutt nafn. Kannski er það lengur nafn. En hvað er lykillinn hér er að það er stöðug tala. Og kannski er það ekki í raun fasti, en guð, ef raunhæft, í orðabók, það er líklega einhver takmörk á fjölda bréfa í A einstaklingsins nafn í viðkomandi landi. Og svo við getum gert ráð fyrir að gildið er fasti. Ég veit ekki hvað það er. Það er sennilega stærri en við teljum það er. Því það er alltaf einhver horn málið með brjálaður langa nafni. Svo skulum kalla það k, en það er samt fasti væntanlega, vegna þess að hvert nafn í heimi, að minnsta kosti í tilteknu landi, er að lengd eða styttri, svo það er stöðug. En þegar við höfum sagt eitthvað er stór O á föstu gengi, hvað er að virkilega jafngildir? Það er í raun það sama eins og að segja stöðugt tíma. Nú erum við konar svindl, ekki satt? Við erum eins konar meira sumir kenningar hér að segja að vel, til þess k er raunverulega bara til eitt, og það er stöðug skipti. En það er í raun. Vegna þess að lykillinn innsýn hér er að ef við höfum n nöfn þegar í þessu gögn uppbygging, og við setja Maxwell, er the magn af tími sem það tekur okkur að setja Maxwell á öllum viðkomandi eftir því hversu margir aðrir eru í gögn uppbygging? Virðist ekki vera. Ef ég hefði milljarð fleiri þætti til þessa Trie, og síðan að setja Maxwell, er hann yfirleitt áhrif? Nei Og það er ólíkt einhverju daga gögnum mannvirki sem við höfum séð hingað til, þar sem gangi tíma reiknirit er alveg óháð því hversu mikið efni er eða er ekki þegar í þessi gögn uppbygging. Og svo með þetta tryggir að þú er nú tækifæri fyrir p setja sex, sem munu aftur falið að innleiða eigin stafa afgreiðslumaður, lesa í 150.000 orð, hvernig best sé að geyma það er ekki endilega augljós. Og þó að ég hef sóst eftir að finna Gral, ég er ekki hermir, að Trie er. Í raun, tæti borð getur mjög vel reynst mun skilvirkari. En þeir eru bara - það er bara einn af the hönnun ákvarðanir þú verður að gera. En að loka skulum taka 50 eða svo sekúndur til að taka gægjast á hvað liggur undan í næstu viku og utan við umskipti frá þessari stjórn lína heiminum ef C forrit til hlutur vefnum undirstaða og tungumál eins og PHP og JavaScript og internetið sjálft, samskiptareglur eins og HTTP, sem þú hefur tekið sem sjálfsögðum hlut í mörg ár nú, og tegund flesta dag, ef til vill, eða séð. Og við munum byrja að afhýða aftur lag af Hvað er á internetinu. Og hvað er númer sem liggur verkfæri í dag. Svo 50 sekúndur af þessu beitu hér. Ég gef þér Warriors af Netinu. [Vídeó spilun] -Hann kom með skilaboð. Með siðareglur allt eiga sína. Hann kom til a veröld af grimmilegri eldveggir, uncaring leið, og hættum langt verra en dauðinn. Hann er fljótur. Hann er sterkur. Hann er TCPIP. Og hann fékk netfangið þitt. Warriors af Netinu. [END vídeó spilun] Ræðumaður 1: Það er hvernig internetið skal starfa frá næstu viku.