DAVID Malan: Allt í lagi. Velkomin aftur til CS50. Þetta er upphaf 8. viku. Og muna að Heimadæmi 5 lauk með smá áskorun. Svo miðað við að þú batna öllum þínum kennslu Fellows og ljósmyndir CA í card.raw skrá, þú ert rétt að nú finna alla þá fólks, og einn heppinn sigurvegari vilja ganga heim með einn af þessum hlutum, sem stökk hreyfing tæki sem þú getur notað til endanlegrar verkefni, til dæmis. Þetta, á hverju ári, leiðir til smá creepiness. Og svo það sem ég hélt að ég myndi gera er að deila með þér nokkrum af þeim athugasemdum sem hafa farið fram og til baka yfir starfsfólk lista á síðkastið. Til dæmis, vitna bara í gærkvöldi Unquote, frá einu af the staff meðlimir, "Ég hafði bara nemandi högg á hurðina mína til að taka mynd með mér. Stalkers, ég segi þér. "Byrjaði nokkuð lýsandi og þá við fluttum á, klukkutíma eða svo síðar, "ég átti nemandi að bíða eftir mér eftir hluta og hann hafði allt af nöfnum okkar og myndir á sumum blöð. "Allt í lagi. Sem skipuleggja, en ekki allt sem enn hrollvekjandi. Þá, "ég var út úr bænum um helgina, og þegar ég kom aftur, það var einn í minn svefnherbergi. "[hlátur] DAVID Malan: Næsta tilvitnun úr starfsfólki félagi, "nemandi kom til mín á Somerville á 4:00 í morgun. "Næsta starfsfólk, "ég fékk að hótelinu mínu í San Francisco og nemandi var að bíða eftir mig á móttöku með þremur DSLRs. " Tegund af myndavél. "Ég er ekki einu sinni á starfsfólki þessari önn, en nemandi braut inn í hús mitt þetta morgun og skráð í heild hlutur með Google Glass. "Og svo loks, "Að minnsta kosti 12 manns voru ákaft bíða fyrir mig þegar ég fékk út af mínum Eðalvagn, og þá er ég vaknaði. "Allt í lagi. Svo meðal ljósmyndum, eins og þú getur muna, eru þessi náungi hér, sem þú gæti vita sem Milo Banana, sem býr við Lauren Carvalho, yfirmaður okkar kennslu náungi. Milo, Milo, komdu hingað drengur. Milo. Milo. Mind þér, hann þreytandi Google Glass, svo við munum sýna þér þetta allt eftir. Svo er þetta Milo ef þú vildi eins og til taka mynd með honum síðan. Ef þú vilt líta út á áhorfendur þar. OK. Það er gott myndefni. Jæja, Milo Banana. Ó, gera það ekki. [Hlátur] OK. Svo orði þá á hvað er framundan, því eins og við byrjum að umskipti, í þessari viku sérstaklega, úr C í a stjórn lína umhverfi til PHP og JavaScript og SQL og HTML og CSS í A vefur-undirstaða umhverfi, munum við vera útbúnað þér allar meiri þekkingu fyrir hugsanlega lokaverkefni. Undir því skyni, að sjálfsögðu hefur hefð að halda námskeið sem eru á snertifleti efni að sjálfsögðu. Mjög mikið sem tengjast forritun og app þróun og svo framvegis, en ekki endilega kanna með eigin Námskeiðið er kennsluáætlun. Svo ef þú gætir haft áhuga á einu eða meira af námskeiðum á þessu ári, Skráning er á cs50.net/seminar. Það eru eldri námskeið á cs50.net/seminars. Og á verkefnaskrá Hingað á þessu ári eru ótrúlega Apps vefur með Ruby á Teinar, sem er val tungumál til PHP. Tölvumálvísindum. Inngangur að IOS, sem er pallur sem er notað fyrir iPhone og iPad þróun. JavaScript til að Web Apps, munum við ná að, en í þessu námskeiði, munt þú fara inn í fleiri smáatriði. Stökk Motion, svo við munum í raun hafa sumir af vinum okkar frá Motion Leap, fyrirtækið sjálft, tengja okkur. Á morgun, í raun, að veita a snertið ekki-á námskeið, ef áhugaverð fyrir þig. Meteor.js, val aðferð fyrir nota JavaScript ekki í vafra en á netþjóni. Node.js, sem er mjög mikið í því bláæð og vel. Sléttur Android Design. Android vera mjög vinsæll valkostur til IOS og Windows Sími og annar hreyfanlegur pallur. Og Web Security Active Defense. Svo í raun, ef þú vilt að taka þátt í þessu, láttu mig gera mið af þessu. Við erum mjög ánægð að segja að vinir okkar á Leap Hreyfing, sem er gangsetning - þetta tæki virkilega bara kom út nokkrum mánuðum síðan - hefur vingjarnlega gaf 30 slík tæki á bekknum fyrir eins margra nemenda, ef þú vilt að láni vélbúnað að lok hverrar annar og nota það til í raun lokaverkefni. Þeir styðja takmarkaðan fjölda tungumála. Ekkert af þeim C, enginn þeirra PHP, svo gera sér grein fyrir einn eða fleiri af þessum málstofum gæti reynst áhugaverð. Og öllum þeim verður tekið í ef að þú ert ekki fær að mæta í eigin persónu. Dagskráin verið tilkynnt um email og við styrkja herbergi. Og loks, ef þú ferð til projects.cs.50.net, þetta er vefsíða við höldum á hverju ári sem við bjóðum gott fólk frá samfélaginu, kennara deildir, starfsfólk, og bæði í utan CS50 til leggja verkefni hugmyndir. Things af áhuga að námsmenn. Atriði af áhugi til deilda. Svo snú þar ef þú ert í erfiðleikum með óvissu um hvað þú sjálfur langar að glíma við. Svo síðast þegar við kynntum að öllum líkindum flóknari gögn uppbygging en við myndum séð í vikum áður. Við höfðum verið að nota fylki nokkuð hamingjusöm eins gagnlegt ef einföldu gögn uppbygging. Þá kynntum þetta, sem auðvitað eru tengd listum. Og hvað var einn af motivations fyrir kynna þessi gögn uppbygging? Já? Hvað er það? Áhorfendur: Dynamic stærð. DAVID Malan: Dynamic stærð. Svo þar í fylki, þú þarft að vita stærð sína fyrirfram þegar þú úthluta því. Í tengda listanum, þarftu ekki að vita það. Þú getur bara malloc eða fleiri almennt, úthluta til viðbótar hnút, svo að segja, hvenær sem þú langar að setja inn fleiri upplýsingar. Og hnút hefur ekki fyrirfram merkingu. Það er bara almenn orð sem lýsa einhvers konar ílát sem við erum nota í uppbyggingu okkar gögn til að geyma einhver atriði af áhugi, sem í þessu Málið verður að vera heiltölur. En það er alltaf tradeoff. Svo við fáum öflugt stærðir af gögnum uppbyggingu, en hvaða verð borga við? Hvað er hæðir af tengdum listum? Já? Áhorfendur: þarf meira minni. DAVID Malan: Það þurfa fleiri minni, hvernig nákvæmlega? Áhorfendur: [inaudible]. DAVID Malan: Einmitt. Svo nú höfum við ábendingum taka upp fleiri minni sem við áður þarf ekki, vegna þess að kostur um fjölda, að sjálfsögðu, er að allt er samliggjandi, aftur til aftur til baka, sem gefur þér af handahófi aðgang. Því bara með því að nota veldi krappi ritháttur eða meira tæknilega músina tölur, mjög einfalt viðbót, getur þú fengið aðgang að hvaða þættir í föstu tíma. Og í raun, það er eins konar vísbending um annað verð sem við erum að borga með tengda listanum. Hvað gerist í gangi tíma eitthvað eins og leit, ef ég vil finna nokkur gildi og inni um tengda lista? Hvað þýðir að keyra minn tími orðið? Big O n. Ef það er raðað í? Hvað ef gögn uppbygging er raðað? Get ég gert betur en stór O n til að leita? Nei, vegna þess að í versta tilfelli gæti mjög vel að vera flokkaður, en fjöldi þú ert að leita að gæti verið stór. Það gæti verið númer 100, sem gæti gerst að vera allt leið á endanum. Og vegna þess að þú getur aðeins opna tengd lista í þessari framkvæmd með því leið fyrsta hnút hennar, þú ert enn svona út af heppni. Þú þarft að fara yfir allt hlutur frá fyrstu til varað í því skyni að finna að stór gildi eins 100 manns. Eða til að ákvarða hvort það er ekki einu sinni það. Svo við getum ekki gert það reiknirit í gögnum uppbyggingu sem lítur svona út? Við getum ekki gert tvöfaldur leit, því tvöfaldur leita þarf að við höfðum handahófi aðgangur. Við gætum bara stökk frá stað til stað án þess að fylgja þessar brauð mola í formi af öllum þessum ábendingum. Nú, hvernig var við að framkvæma þetta? Jæja, ef við förum á skjáinn hér, ef við getum fljótlega reimplement þessi gögn uppbygging - rithönd mín er ekki allt sem mikill hér, en við munum reyna. Svo typedef strúktúr, og hvað gerði ég vilt hringja þetta upp hér? Hnút. Svo ég næ okkur byrjaði. Og nú, hvað þarf að vera inni gögn uppbygging fyrir að ein tengd lista? Hversu mörgum sviðum? Svo tveir. Einn er nokkuð auðvelt. Svo int n. Og við gætum hringt n hvað sem við viljum, en það ætti að vera int ef við erum framkvæmd tengda lista fyrir ints. Og nú er það annað sviði að vera? Strúktúr hnút *. Svo ef ég strúktúr hnút *, og svo ég getur hringt í þetta líka hvað ég vil, en bara til að vera skýr Ég hringi það næsta, eins og við höfum verið að gera. Og þá ég loka hrokkið axlabönd mínum. Og nú, eins og síðasta sinn, Ég setti hnút niður hér. En ef ég er að lýsa þessu er sem hnút, af hverju gerði ég nennir að vera svo fjölorður hér í að lýsa strúktúr tengipunktur * næst, öfugt til bara hnút * er? Já? Áhorfendur: [inaudible]. DAVID Malan: Einmitt. Einmitt. Vegna C tekur virkilega bókstaflega og aðeins sér skilgreiningu á hnút leið niður hér, getur þú ekki átt við það upp hér. Þannig að við höfum svona sjáum yfirlýsingu hér, sem er að vísu meira fjölorður. Strúktúr hnút, sem þýðir við getum nú nálgast hana innan við gögn uppbygging. Og eins og til hliðar, því þetta er verða aðeins meira huglægt nú, stjarnan geta tæknilega farið hér, það getur farið hér, getur það jafnvel fara í miðju. Við höfum samþykkt, í stíl fylgja fyrir Námskeiðið, sem venju að setja stjarnan við hliðina á þeim gögnum gerð, sem í þessu tilfelli, væri strúktúr hnút. En átta sig í fullt af kennslubókum og netinu tilvísanir, gætir þú örugglega sjá það á hinni hliðinni. En bara grein fyrir því að báðir vilja raunverulega vinna og þú ættir einfaldlega að vera stöðug. Allt í lagi. Svo sem var yfirlýsing okkar á hnút strúktúrinn. En þá erum við byrjaði að gera meira háþróuð hlutir. Til dæmis ákváðum við að kynna eitthvað eins og kjötkássa töflunni. Svo hér er kjötkássa borð af n stærð, verðtryggð frá 0 á efst til vinstri til n mínus 1 á neðst til vinstri. Þetta gæti verið kjötkássa borð fyrir neitt. En hvað konar hluti gerði við tölum um að nota kjötkássa borð fyrir? Geymsla hvað? Nöfn. Við gætum gert nöfn eins við gerðum síðast. Og í raun er hægt að geyma neitt. Og við munum sjá þetta aftur í PHP og JavaScript. A kjötkássa borð er ágætur konar Swiss Army hnífur sem leyfir þér að vista nánast hvað sem þú vilt inni það með því að tengja takkana með gildum. Lyklar með gildin. Nú í þessari einföldu tilfelli, okkar lyklar eru bara tölur. Við erum að innleiða kjötkássa borð sem fylki. Og svo takkarnir eru 0, 1, 2, og svo framvegis. Og svo við, eins og menn, ákvað síðasta viku sem þú veist hvað, ef við erum fara að geyma nöfn, við skulum bara geðþótta, en nokkuð sæmilega, ráð fyrir að Alice, A nafn, mun bara vera verðtryggð í 0. Og Bob, B nafn, verða verðtryggð í 1, og svo framvegis. Svo höfðum við kortlagning á milli aðfanga, sem eru strengir, og tætið stöðum, sem eru tölur. Svo þessi aðferð er almennt þekktur eins og kjötkássa virka, og þú getur sannarlega innleiða hana í kóða. Ef ég vildi framkvæma kjötkássa virka sem er einmitt það sem við bara lýst frá síðasta tíma, gæti ég lýsa aðgerð sem tekur, eins og inntak til dæmis - og við skulum gera þetta á þetta skjár hérna. Ef ég vildi innleiða kjötkássa virka, gæti ég sagt eitthvað eins og this. Það er að fara að skila int. Það er að fara að vera kölluð kjötkássa, og það er að fara að taka sem rök fyrir band, eða við getum verið meira viðeigandi nú, og segja char *, munum við kalla það s. Og þá hefur allt þetta aðgerð til að gera, lokum, er skila int. Nú, hvernig það virkar sem gæti ekki að vera svo skýr. Ég ætla að framkvæma þetta án þess að allir Form villuprófun núna. Ég ætla bara að fara að blindni segja, aftur hvað er á s þrepi 0, mínus, skulum segja, höfuðborg semíkommu. Algjörlega brotinn. Það er ekki fullkominn því einn, hvað ef s er núll? Slæmir hlutir eru að fara að gerast. Tveir, hvað ef fyrsti stafurinn í þessu nafn er ekki höfuðborg bréf? Það er ekki að fara að snúa vel heldur. Það gæti verið lágstafir bréf eða ekki bréf yfirleitt. Svo algerlega pláss fyrir framfarir hér, en þetta er grundvallar hugmynd. Það sem við sem lýst er í síðustu viku munnlega og bara ferli að kortleggja Lísa til 0 og Bob til 1 er hægt að sýna vissulega meira formulaically sem C virka hér. Kallaði aftur kjötkássa, tekur streng sem inntak, og þá er á einhvern hátt eitthvað með því inntak að framleiða framleiðsla. Ekki ólíkt svartur kassi lýsingu okkar sem við höfum lengi gert. Ég veit ekki hvernig þetta gæti verið vinna undir hetta. Fyrir sett Dæmi 6., einn af þeim áskorunum er fyrir þig að ákveða hvað mun kjötkássa virka þín? Hvað er að fara að vera inni að svart kassi, og væntanlega verður það að vera lítið meira áhugavert en þetta, og örugglega hættara við villa stöðva en þetta tiltekna framkvæmd. En vandamál geta komið upp, ekki satt? Ef við höfum gögn uppbygging eins og þessa einn, hvað er eitt af þeim vandamálum þú getur keyrt inn í tímanum sem þú setur fleiri og fleiri nöfn inn í kjötkássa borð? Þú færð árekstra, ekki satt? Hvað ef þú ert með Alice og Aron, tvær manneskjur sem nöfn gerðist til að byrja með? Það bidur spurningin, þar sem þú setja annað svo nafn? Jæja, þú might naively bara setja það þar sem Bubbi tilheyrir, en þá er Bob konar ruglaður ef þú reynir að setja nafnið hans næsta og það er ekkert pláss fyrir hann. Svo þú gætir sett Bob þar Charlie er, og þú getur ímyndað þetta mjög fljótt devolving inn í a hluti af a sóðaskapur. Eitthvað línuleg á endanum, þar sem þú bara að leita á allri leita Alice eða Bob eða Aron eða Charlie. Þeirra í stað lagt, í staðinn af réttlátur línulega leit fyrir opin rými og plopping nöfn þarna, við Lagt áhugamaður nálgun. A kjötkássa borð til framkvæmda enn með array af vísitölum, en gögnin gerð þessir vísitölur voru nú ábendingum. Ábendingum til hvaða? Ábendingum til tengd listum. Vegna muna að tengjast listi er raun bara bendi á hnút, og hnúturinn hefur næsta reit, og að hnút hefur næsta reit, og svo framvegis. Svo þú getur nú hugsa um þetta fylki á vinstri-hönd hlið af kjötkássa töflu sem leiðir til tengda listanum. Kosturinn sem er ef þú færð árekstur milli Alice og Aron, hvað gerir þú með önnur slík manneskja? Þú hengja bara hann eða hana til endir, eða jafnvel í byrjun þess tengda listanum. Og reyndar, við skulum bara núðla gegnum að fyrir bara annað. Hvar myndi gera sem mest vit? Ef ég setja Lísa og hún endar á fyrsta location, þá reyni ég að setja nafn Arons, og það er augljóslega árekstur, ætti ég að setja honum í upphafi á tengda lista? Það er á þeim fyrsta stað, eða í lok? Áhorfendur: [inaudible]. DAVID Malan: OK. Ég heyrði byrjun. Hvers vegna í upphafi? Áhorfendur: [inaudible]. DAVID Malan: OK. Það er stafrófsröð, svo það er gott. Það er góð eign. Það mun spara mér tíma mögulega. Það mun ekki láta mig gera tvöfaldur leit, en ég gæti að minnsta kosti að vera fær um að brjóta út af lykkju ef ég grein, vel, ég leið framhjá voru Aaron myndi vera í þessari raðað tengda listanum. Ég þarf ekki að eyða tíma mínum að leita alla leið til enda. Svo er það sanngjarnt. Hvers vegna í ósköpunum getur þú vilt setja að rekast nafn á því upphafið af listanum? Hvað er það? Áhorfendur: [inaudible]. DAVID Malan: Það gæti tekið langan tíma til að fá til the endir af listanum. Og í raun, lengri og lengri. Því fleiri nöfnum þú setja það Byrja með, því lengur sem keðja er að fara að fá. Því lengur sem tengd Listinn er að fara að fá. Svo þú ert í raun bara að sóa tíma þínum. Kannski þú ert betur að viðhalda stöðug innsetningu sinni, stór O 1, því alltaf að setja rekast nafn á upphaf tengda lista, og ekki hafa áhyggjur eins mikið um flokkun. Hvað er besta svarið? Það er óljóst. Það konar veltur á hvað dreifing er, hvað mynstur er af nöfnum sem þú ert að setja. Það er ekki endilega augljóst svar. En hér, aftur er, hönnun tækifæri. Þannig að við fórum síðan á þetta, sem er í raun annar stór tækifæri p-setja 6. Og átta sig á, ef þú hefur ekki nú þegar, Zamyla kafar í báðum þessum, kjötkássa borðum og reynir, nánar. Og vídeó walkthrough er fellt í p-setja sérstakur. Þetta var Trie - T-R-I-E. Og hvað var áhugavert um þetta var að keyra tími að leita að nafni, eins og Maxwell síðasta sinn, var stór O hvað? Hvað er það? Áhorfendur: Fjöldi bréfa. DAVID Malan: Fjöldi bréfa. Ég heyrði tvennt. Fjöldi bréfa og föstu tíma. Svo skulum við fara með það fyrst. Fjölda af bréfum. Jæja, þessi gögn uppbygging, muna, er eins og tré, fjölskyldu tré, hvert af hnúður Hvers samanstanda af fylki. Og þeir fylki eru ábendingar til aðrar slíkar hnúður eða önnur slík fylki í trénu. Þannig að ef við vildum að þá ákveða hvort Maxwell er í hér, ég gæti farið til fyrsta array, á mjög toppur af tré, svokallaða rót, efst The Trie, og þá fylgja m músina, þá bendillinn, þá x, w, E, I, l. Og svo þegar ég sé einhverjum sérstökum tákn, táknað hér eins og þríhyrningur. Í merkjamál þú munt sjá að við leggjum til að þú framkvæmda sem bool, bara segja já eða nei, orð hættir hér. Jæja, þegar við höfum farið til M-A-X-W-E-L-L, líður eins og sjö, kannski átta ef við förum einn framhjá henni, átta Leiðir til að finna Maxwell. Eða við skulum kalla það K. En muna síðustu tími, hélt ég að ef það er raunhæft að hámarki lengd í orð, eins og 40-sumir-stakur persónur, sem Hámarkslengd felur stöðug gildi. Svo í raun, já, það er tæknilega stór O frá 8. eða 7, eða mjög stór O K. En ef það er endanlegt hettu á hvað K gæti verið, það er stöðug. Og svo er það stór O 1 á í lok dagsins. Ekki í hinum raunverulega heimi. Ekki þegar þú byrjar í raun að horfa á klukka sem hlaupandi program þíns. Það er alveg að fara að vera svolítið hægari en sannarlega fasti tíma með einu skrefi. Það er að fara að vera sjö eða átta skref, en samt er það miklu, miklu betra en reiknirit eins stór O í n að fer eftir stærð á því hvað er í gögn uppbygging. Tilkynning um kosti hér er að við getum sett milljón fleiri nöfn í þessu gögn uppbygging, en hversu margir fleiri skref er það að fara að taka okkur að finna Maxwell í því tilviki? Ekkert. Hann er óbreytt. Og hingað til, ég held ekki að við höfum séð dæmi um gögn uppbygging eða reiknirit sem var alveg óháð ytri hegðun eins og þessi. En þetta getur ekki verið magnað. Þetta getur ekki verið eina lausnin fyrir p-setja Og það er ekki. Þetta er ekki endilega gögnin uppbygging þú ættir sökkva til, því eins og kjötkássa matskeið, tradeoff. Hvað er það verð sem þú borgar hér? Minni. Ég meina, þetta er grimmilegur magn af minni. Og þú getur ekki alveg séð það hér því höfundur þessarar mynd augljóslega stytt öllum fylki, og við erum ekki að sjá fullt af A og Er b og s C og Spurningar og svör er Y og er Z í þessum fylki. En þeir eru þar. Hver af þessum hnúta er í heild array sumra 26 eða fleiri bæti, hvert um sem táknar bréf. 27 í okkar tilviki, svo að við getum styðja úrfellingarmerki í Heimadæmi. Þannig að þetta gögn uppbygging er í raun, mjög þéttur og breiður. Og það eitt og sér gæti endað hægur það niður, eða að minnsta kosti kosta þig miklu meira pláss. En aftur, getum við dregið samanburð hér. Muna á meðan bak, náð við mikið meira spennandi hlaupandi tíma í flokkun þegar við notum Mergesort, en verðið við greitt að ná n log n fyrir sameiningu Raða þarf að við eyða meira hvað auðlind? Meira pláss. Við þurftum öðru fylki til afrita fólk inn, rétt eins og við gerðum hér á sviðinu. Svo aftur, engin skýr sigurvegari, en bara huglæg hönnun ákvarðanir um að vera. Allt í lagi. Svo hvernig um þetta? Hver kannast sem D-Hall? OK. Svo þrír af okkur að gera. Mather House. Svo er þetta fyrir veitingastöðum Mather er. Ég veðja alla veitingastöðum sölum hafa stafla af bakka svona. Og þetta er í raun fulltrúi um eitthvað sem við höfum augljóslega séð nú þegar. Við kölluð það bókstaflega stafla. Og stafla, í skilmálar af þinn minni tölva ', er þar gögn fer en aðgerðir eru kallaðir. Til dæmis, fara hvaða tegundir af hlutum á mánudaginn með tilliti til minni skipulag sem við höfum rætt í vikur síðustu? Hvað er það? Áhorfendur: Símtöl til aðgerða. DAVID Malan: Fyrirgefðu. Áhorfendur: Símtöl til aðgerða. DAVID Malan: Símtöl til aðgerða, en sérstaklega, hvað er inni hvers þessir rammar? Hvers konar hlutum? Já. Svo staðbundnar breytur. Hvenær sem við vantaði staðbundna geymslu, eins rifrildi, eða int ég, eða int Hitastig, eða hvað á staðnum breyta er, höfum við verið setja það á mánudaginn. Og við köllum það stafla því þess layering hugmynd. Bara svona passar upp við raunveruleikann, hugtakið stað. En það kemur í ljós að stafla getur einnig talist gögn uppbygging, sem val til fjölda, val til tengda lista. Eitthvað eðli meira áhugavert sem getur samt verið útfærð með annaðhvort þeirra hlutir, en það er önnur tegund af gögn uppbygging styðja, virkilega, aðeins tvær aðgerðir. En þú getur bætt á áhugamaður lögun en þessir. En þetta eru grundvallaratriði - ýta og skjóta. Og hugmyndin með stafla er að ef ég hér hafa, með eða án Annenberg vitund, bakki úr næsta húsi með númer 9 á það. Svo bara int. Og ég vil að ýta þessu á gögnum uppbygging, sem nú er tómur. Hugleiddu þetta neðst á stafla. Ég myndi ýta þetta númer 9 inn á stafla, og nú er það rétt þar. En áhugaverður hlutur óður í stafla er að ef ég vil nú að ýta einhver önnur gildi, eins og 17, og ég ýta þetta á mánudaginn, ég er að fara að gera eina leiðandi hlutur, ég ætla bara að fara Til að setja það rétt þar sem við mennirnir myndi vera hneigðist að setja það á toppinn. En hvað er áhugavert nú er, hvernig fæ ég á 9? Þú veist, ég er ekki án einhverrar vinnu. Svo hvað er áhugavert um stafla er að við hönnun, það er LIFO gögn uppbygging. Kjánalegt leið til að lýsa síðast í, fyrst út. Svo í síðasta númer í á þessum tíma var 17. Svo ef ég vil skjóta eitthvað af á mánudaginn, það geta aðeins verið 17. Þannig að það er nauðsynlegur til þess starfsemi hér, þar sem síðasta atriði í að vera sá fyrsti út. Þess vegna skammstöfun, LIFO. Svo hvers vegna gæti þetta verið gagnlegt? Eru aðstæður þeirra sem þú vilt að vilja gögn uppbygging eins og þetta? Jæja, það er verið vissulega gagnlegt inni í tölvunni. Svo stýrikerfi nota skýrt þetta konar uppbyggingu gagna í stöflum. Við munum einnig sjá sömu hugmynd þegar það kemur að því að vefur blaðsíða. Svo í þessari viku og í næstu viku og utan, og eins og þú byrja að innleiða vefnum síður á tungumáli kallast HTML, getur þú reyndar nota gögn uppbygging eins þetta til að ákvarða hvort síða er rétt sniðinn. Vegna þess að við munum sjá allar vefsíður fylgja eins konar stigveldi, sem inndrátt sem mun, í lok dagsins, verið tré uppbyggingu undir hetta. Svo meira um það í bara smá. En nú skulum við leggja fyrir stund, hvernig gætum við farið um alþingismaður hvað stakkur er? Leyfðu mér að leggja til að við framkvæmd stafla með kóða eins og þetta. Svo stafla er að fara að hafa innan þess tvennt, fylki, sem kallast stæði, bara til að vera í samræmi við kynningu. Og hvert atriði í þeirri fylking er að fara til vera a tegund int. Og getu er væntanlega hvað? Vegna þess að ég hef ekki skrifað fullur skýring hér. Það er líklega hámark stærð fylkisins. Og það er líklega skilgreind sem mikil define efst á skránni, sumir konar fasti skyn eins með eingöngu hástafi. Svo einhvers staðar getu er skilgreint eins og hæsta mögulega stærð. Á sama tíma, innan við gögn uppbygging þekktur sem stafla það verður að vera heiltala bara þekkt einfaldlega sem stærð. Þannig að ef ég væri að tákna þetta núna pictorially, skulum gera ráð fyrir að þetta heild svartur kassi táknar stafla mitt. Innan þess er tvær breytur. Þannig að ég ætla að draga fyrsta sem stærð. Og annað sem ég ætla að draga eins og fylki. En bara til að halda hlutum skipulegan, venjulega myndi ég draga fylki eins þetta, en það er góður af gaman ef við passa veruleika, eða passa andlega fyrirmynd. Svo láta mig draga stað array lóðrétt, sem er bara, aftur, listamannsins flutningur. Skiptir ekki máli hvað það er undir hetta. Og við munum segja að við vanræksla, getu er að fara að vera þrír. Þannig að þetta verður staðsetning 0, þetta verður staðsetning 1, þessi verður staðsetning 2. Ef ég mútur með streitu boltanum, myndi einhver vilja koma upp og keyra borð hér fyrir réttlátur a augnablik? OK, sá hönd þína fyrst. Komdu upp. Allt í lagi. Svo ég held að það sé Steven. Komdu upp. Allt í lagi. En geri ráð fyrir að við nú til baka til fyrstu ástand í heiminum þar sem ég hafa bara lýst stafla, og það er að fara að vera á getu þrjú. En stærð hefur ekki enn verið ákveðinn. Stæði hefur ekki enn verið ákveðinn. Svo a par af spurningum fyrst. Og láta mig gefa þér mic svo þú getur þátt virkari í þessu. Svo hvað er inni á stærð á þessari stundu í tíma ef allt sem ég hef gert er lýst stafla með ein lína af kóða? STEVEN: Ekki mikið. DAVID Malan: OK, ekki mikið. Vitum við hvað er inni stærð, vitum við hvað er inni af þessu fylki hér? STEVEN: Bara handahófi númer, ekki satt? Bara - DAVID Malan: Já, ég ætla að kalla það númer, en handahófi - STEVEN: Things. DAVID Malan: Hluti eins handahófi STEVEN: Bits. DAVID Malan: Bits, ekki satt? Svo gildum sorp, ekki satt? Svo permutations af 0 og 1 er. Leifar af fyrri málnotkun þessa minni. Og við í raun ekki vita hvað gildin eru, svo við draga yfirleitt þá sem spurningarmerkjum. Svo það fyrsta sem við erum væntanlega fara til að vilja gera hér - og láta mig gefa þessu sviði inni þarna nafn - stæði. Hvað eigum við að frumstilla væntanlega stærð til ef við viljum byrjað að nota þessa stafla? STEVEN: Bakki er undir 3. DAVID Malan: Svo, OK. Til að vera skýr, er getu lýst annars staðar eins og þrjú. Og það er það sem ég hef notað að úthluta array. Stærð er að fara að vísa til hversu margir stæði eru nú á mánudaginn. STEVEN: Zero. DAVID Malan: Svo það ætti að vera núll. Svo fara á undan, og með hvaða fingri, draga núll að stærð. Allt í lagi. Svo nú, hvað er inni í þessu Hér vitum við ekki. Þetta eru í raun bara sorp gildi. Svo við gætum draga spurningarmerki, en skulum halda stjórn hreint fyrir nú því það skiptir ekki máli hvað er þarna. Við þurfum ekki að frumstilla array við neitt, því ef við vitum að the stærð af the stakkur er núll, vel, við ætti ekki að vera að horfa á neitt í þetta array samt á þessum tímapunkti. Svo nú ætla ég að ýta á númer 9 á mánudaginn. Hvernig ættum við að uppfæra gögn uppbygging inni af þessu svarta kassanum? Hvaða gildi þarf að breyta? STEVEN: Innan - stærð? DAVID Malan: OK. Stærð ætti að verða hvað? STEVEN: Stærð vildi vera einn. DAVID Malan: OK. Svo stærð ætti að verða eitt. Svo þú getur gert þetta á nokkra vegu. Leyfðu mér að gefa þér, nú þinn fingur er strokleður. Allt í lagi. Þá er nú fingurinn bursta. Allt í lagi. Og nú hefur það annað að breyta, augljóslega, í gögn uppbygging? STEVEN: Við erum að fara frá botn allt að 9. DAVID Malan: 9. OK, Good. Svo enn skiptir ekki máli hvað er á Staðsetning einn eða tveir af því að þeir eru sorp gildi, en við ættum ekki að nenna leita þar vegna stærð er segja okkur að aðeins fyrsti þáttur er í raun lögmætur. Svo nú er ég að ýta 17 á listanum. Hvað gerist við þessa mynd? STEVEN: Svo stærð er að fara að fara til tveggja. DAVID Malan: OK. Þú ert Strokleður - Úps. Þú ert strokleður. STEVEN: Strokleður. DAVID Malan: Þú ert bursta. STEVEN: Brush. DAVID Malan: OK. Og hvað annað? STEVEN: Og þá erum við - DAVID Malan: Við ýtt 17. STEVEN: Við fast 17 ofan, svo - DAVID Malan: OK, gott. STEVEN: - falla því niður. DAVID Malan: Allt í lagi. Það er að fá auðvelt. Ég ætla ekki að hjálpa þér í þetta sinn. Ýta 22. STEVEN: Lokið. Becoming strokleður. Ég er að verða bursta. Og þá er ég að setja 22. DAVID Malan: 22. Excellent. Svo einu sinni enn. Ég ætla nú að fara að ýta á mánudaginn 26.. STEVEN: Ooh. Ó gosh. Þú lent virkilega mig burt vörður. DAVID Malan: Þú varst ekki sjá þetta koma? STEVEN: Ég vissi ekki að sjá þetta koma. Gætum við aftur fyrstu getu? DAVID Malan: Það er góð spurning. Þannig að við höfum konar máluð okkur í horninu hér. Það raunverulega er ekki gott út fyrir Steven vegna þess að við höfum úthlutað þessu fylki statically, svo að segja, inni af gögn uppbygging. Og við höfum í raun erfitt dulmáli það að vera af stærð þrjú. Svo við getum í raun ekki endurúthluta því. Við gætum ef við fórum aftur í, við skilgreina stæði að vera bendill sem við notum þá malloc að hönd minni til. Vegna þess að ef við fengum minni frá hrúga gegnum malloc, við gæti þá losa hana. En áður en frjáls það, gætum við endurúthluta stærri klumpur af minni, uppfæra músina, og svo framvegis. En nú, er þetta virkilega besta sem við getum gert. Ýta og skjóta eru væntanlega að fara að þurfa að merki sumir villa. Svo til dæmis, framkvæmd okkar af ýta gæti skila bool sem áður skilað satt, satt, satt. En í fjórða sinn, það er að fara að hafa að aftur ósatt, til dæmis. Allt í lagi. Mjög vel gert. Til hamingju. Þú hefur unnið streitu boltanum í dag. [Applause] STEVEN: Þakka þér. DAVID Malan: Þakka þér. OK, svo virðist þetta vera ekki mikið um skref fram á við, ekki satt? Við lýst þessari gögn uppbygging. Það hefur verið sannfærandi, ekki satt? Stýrikerfi eins og það. Virðist vefnum geta nýtt þetta, og önnur forrit enn. En hvað heimskulegt takmörkun sem við erum aftur til að raða í viku tvö mörk þar sem við höfum fasta stærð fylki. Þannig að það eru örugglega nokkrar leiðir sem við gætum leyst þetta. Við gætum virk úthluta array, ekki af harður erfðaskrá það sem ég hef gert hér, heldur aftur lýsa þetta, bara til að vera skýr, og eitthvað eins og this. Int * stæði, ekki ákveða á afkastagetu enn. En þegar ég lýsa stafla annars staðar í númerið mitt, gæti ég þá kalla malloc, fá veffang klumpur minni, og ég gat tengt að tölu til stæði. Og þá, því það er bara klumpur af minni, gæti ég haldið áfram að nota veldi krappi sýndur á hefðbundinn hátt. Því aftur, það er tegund af þessu hagnýtur jafngildi fylki og klumpur af minni sem koma baka frá malloc. Við getum meðhöndla einn sem hin nota músina tölur eða ferningur krappi tákn. Svo er það ein aðferð. En hvernig annars gætum við framkvæma þetta Sama gögn uppbygging, hugsanlega? Ekki satt? Mér finnst eins og við leyst bara þetta vandamál eins og fyrir viku síðan. Hvað var lausn á þessu vandamáli sem Steven hljóp inn? Svo tengd listum, ekki satt. Ef vandamálið er að við erum að mála okkur út í horn með því að úthluta fyrirfram of lítið minni að við þá hafa einhvern veginn tekist á við, vel, hvers vegna ekki bara að forðast það gefa með öllu? Hvers vegna ekki bara að lýsa stæði til að vera bendi á hnút, Ergo tengda lista, og þá einfaldlega úthluta nýja hnúta hvert skipti Steven þarf að passa númer í gögn uppbygging. Svo myndin þyrfti að breyta. Það er ekki að fara að vera eins hrein og eins einfalt og bara fjölda þremur ints. Nú það er að fara til vera a bendi til a strúktúr, og að struct er að fara að hafa int og næsta músina. Það er að fara að leiða í gegnum þessi bendillinn til annars svo strúktúr til annars slíks strúktúr. Svo myndin væri í raun fá smá Messier. Og við myndum hafa örvarnar binda allt saman. En það er allt í lagi, ekki satt, vegna þess að við höfum séð hvernig á að gera þetta. Og þegar þú færð ánægð innleiða eitthvað eins tengt lista, sem þú þarft að gera ef þú valið að innleiða kjötkássa borð með aðskilin chaining fyrir p-setja 6, getur þú nota hana sem byggja blokk, eða efni, eða í grunni tala, sem aðferð, eitthvað sem þú setur, þér búið til eigin þraut stykki sem þú getur þá endurnýta. Svo Tradeoffs, en hugsanlega lausnir að við höfum í raun séð áður. Svo oft, sérð þú þetta á hverjum ár eða tvö þegar Apple gefa út eitthvað nýtt, og allt klikkaði fólk lína upp fyrir utan Apple geyma að kaupa lélegur þeirra uppfærsla á vélbúnaði. Ég segi þetta, það er allt í lagi, vegna þess að Ég er einn af þeim. Svo hvers konar gögn uppbygging gæti tákna þessa veruleika? Jæja, við skulum kalla það biðröð, línu. Svo British myndi kalla það yfirleitt biðröð samt, svo það er gott nafn. Og tvær aðgerðir sem biðröð skal styðja við munum hringja í e, rekstur og dequeue rekstur, sem eru svipaðar í andi að ýta og skjóta. Það er bara svona mismunandi í venju, hvað við köllum þetta. En til e, eitthvað þýðir að bæta eða setja það til the gögn uppbygging. Til dequeue þýðir að fjarlægja það. En þar stafla var LIFO gögn uppbyggingu, biðröð er fyrst í fyrst út gögn uppbygging. Ef þú ert fyrsta manneskjan í línu, þú verður að vera fyrsta manneskjan til að fá af línu og kaupa nýja tækið. Ímyndaðu þér hvernig uppnámi þetta fólk væri ef Apple staðinn notað stafla, fyrir dæmi, til að hrinda samtíningur upp á nýja leikfangið þitt. Svo biðraðir skynsamleg, vissulega, og við getum hugsað um alls konar forrit, væntanlega, að biðröð, sérstaklega þegar þú vilt sanngirni. Svo hvernig gæti við framkvæmd þessara sem gögn uppbygging? Jæja, leggja ég að við gætum þarf að gera það með þessum hætti. Þannig að ég ætla að nú hafa númer. Þannig að við munum halda þetta einfalt og ekki endilega tala hvað varðar bakka. Bara tölur sem fólk af fengið. Getu er að fara að, aftur, laga um heildarfjöldi fólks sem getur verið í Þessi lína, sem þrír eða hvað annað gildi. En ég leggja til að ég þarf að halda utan ekki aðeins að stærð sem biðröð, hversu margir hlutir í henni. Svo er stærð núverandi stærð, getu er hámarks stærð. Bara aftur, tegundaheiti með því að venju. Hvers vegna þarf ég til viðbótar int inni af biðröð að halda utan um hver er í framan á línu? Hvers vegna þarf ég að gera það í þessu tilfelli? Jæja, hvernig er þetta mynd að fara að breyta? Ég get sennilega endurnýta mest á þessari mynd. Leyfðu mér að fara á undan og eyða hvað er hér. Við munum gefa þessu örlítið mismunandi nafn upp hér. Skulum losna við 17, skulum losna af 9, skulum losna við 3. Og við skulum bæta einn annar hlutur. Ég leggja til að ég þarf að halda utan um framan á listanum, sem er bara að fara að vera int eins vel. Og við erum að fara að halda það einfalt. Engin tengd lista fyrir nú. Við munum viðurkenna að við erum að fara að högg upp á móti þessum mörkum. En hvað ég vil sjá gerast í þetta sinn? Svo ætla ég að fara á undan og fyrsta maður kemur upp í línu, og það er númer 9. Við höfum streitu kúlur. Get ég stela, segja, tveir eða þrír gestir? Einn, tveir, þrír? Komdu upp. Réttur frá the andlit, því við munum gera þetta einn fljótur. Hver ykkar er nú að fara að vera aðdáandi drengur í samræmi við Apple. Þú munt ekki vera að fá Apple vélbúnað í lok þessarar þó. Allt í lagi. Svo þú ert númer 9, þú ert númer 17, númer 22.. Þetta eru handahófskennt tölur, eins og nemandi auðkenni eða whatnot. Og á aðeins augnablik, við skulum byrja að byrja að bæta hlutina. Og ég keyrt stjórn hér í þetta sinn. Svo í þessu tilfelli, ég hef frumstilla framan til að vera - Ég reyndar ekki alveg sama hvað framan er, vegna þess að stærð er núll. Þannig að þetta gæti eins vel bara vera spurningarmerki. Þetta eru allt spurningarmerki. Svo nú munum við byrja að raunverulega sjá sumir fólk fóður upp í búð. Þannig að ef númer 9, þú ert sá fyrsti þar á 5:00, fara fram í tímann og stilla upp, eða kvöldið áður. OK. Svo er nú 9 hér. Svo 9 er í framan á listanum. Þannig að ég ætla að fara á undan og uppfæra Stærð þessa núverandi gögn uppbyggingu að ekki vera 0 lengur, en til að vera 1.. Ég ætla að setja 9 á á framan á listanum. Leyfðu mér að fara á undan og skipta skjánum svo við getum séð framhjá okkur hér. Og nú hvað ég vil að setja að framan? Ég ætla að halda utan um að framan biðröð núna er á stað 0. Vegna þess að það er næst að fara að gerast? Jæja, ætla nú ég e, 17 eins vel. Svo step í línu þar. Og aftur, eins konar dyr til verslun er að fara að vera hér. Svo nú hef ég bætt 17. Og jafnvel þó þessir krakkar eru að blokka skjánum, það er allt í lagi, vegna þess að við getum séð það allt hér. Því miður. Áhorfendur: Við getum fært - DAVID Malan: Nei, það er allt í lagi. Það er mikið þarna. Svo er 17 nú inni í biðröð. Ég þarf að uppfæra sem reitir nú þó? OK, örugglega stærð. Og hvernig óður í framan? OK, nei. Framan ætti ekki að breyta því ólíkt stafla, við vilja til að viðhalda sanngirni. Þannig að ef 9 kom fyrst, viljum við 9 til að vera fyrsta af línunni og inn í búðina. Í staðreynd, við skulum sjá það. Áður en við setja 22, við skulum fara á undan og dequeue 9. Hvað heitirðu aftur? Áhorfendur: Jake. DAVID Malan: Jake er að fara að dequeued núna. Þannig að þú færð að ganga inn í búðina. Og þykjast að geyma er þarna. Svo nú hvað þarf - dit-dit-dit! Hvað þarf að gerast núna? Hönnun ákvörðun. Svo ekki slæmur eðlishvöt, en - hvað er nafnið þitt aftur? Áhorfendur: David. DAVID Malan: David. Svo hvað gerði Davíð að gera? Hann var að reyna að raða á festa gögn uppbyggingu og færa frá staðsetningu hans í fyrrum stað Jake. Og það er allt í lagi ef við erum tilbúin að taka því sem að framkvæmd smáatriði. En fyrst skulum uppfæra gögn uppbyggingu áður en við gerum það. Því ég er ekki mætur hugmynd allra fólk breytast í þessari línu. Það er ekki máli ef Davíð gerir það með eitt skref, en aftur, hugsa til baka til þegar við höfum haft átta sjálfboðaliða á stigi og við höfum gert eins innsetningu tegund, þar sem við þurftum að byrja færa alla í kringum. Sem fékk dýr, ekki satt? Það gerir mig cringe um stór O af N, stór O af n veldi aftur. Það er ekki tilfinning eins tilvalið niðurstaða. Þannig að við skulum bara uppfæra þetta. Þannig að stærð biðröð er ekki lengur 2. Það er nú einfaldlega 1. En ég get nú uppfæra eitthvað Ég vissi ekki að uppfæra fyrr framan á listanum. Ég gæti bara sagt, er þessi staðsetning 1? Svo nú höfum við sorp gildi hér, sorp gildi hér, og Davíð í miðja rusli. En gögn uppbygging er enn óbreytt. Og í raun, ég er ekki einu sinni að breyta fyrrum númer Jake 9, því hver blíðuhót. Ég hef nægar upplýsingar nú í stærð sem ég veit að það er einn maður í þetta biðröð. Og ég veit að þessi manneskja er á staðsetningu 1, ekki 0. Ég ætla ekki að telja. Sem 1 eins vel. Svo er gögn uppbygging enn OK. Jæja, hvað gerist næst? Skulum e, - hvað er nafn þitt? Áhorfendur: Callen. DAVID Malan: Callen. Skulum e, a Callen, og 22 er nú í biðröð. Svo nú er það að breytast hér? Framan er ekki að fara að breyta, vitanlega. Stærð er að fara að breyta til að vera 2 aftur. Og 22 endar hér, 9 er enn til staðar, en það er í raun að sorp gildi núna. Það er bara leifar af Jake fortíð. Svo nú hvað gerist ef Ég dequeue Davíð? Einn síðastur aðgerð, dequeue David. Við gætum skipta, en ég leggja skulum gera eins litla vinnu og mögulegt er. Nú fer gögn uppbygging minn aftur í stærð 2-1. En framan biðröð nú verður 2.. Ég þarf ekki að breyta þessum númerum bara enn, því þeir eru bara sorp gildi. En nú gerist það? Býst ég e, mig, 26? Mér finnst eins og ég tilheyri hérna. Þannig að ég hef verið enqueued. Svo ég tilheyri konar hér. Og jafnvel þó að þú ert ekki alveg þakka þetta sjónrænt á sviðinu, vegna þess að við höfum nóg pláss, ætti ég ekki að standa hér, hvers vegna? Áhorfendur: Þú ert út af mörk. DAVID Malan: Hægri. Ég er út af mörk. Ég hef verðtryggð utan mörk af þessu fylki. I raun ætti að vera í einu af þrjár mögulegar staðsetningar. Nú, hvar er eðlilegast að fara? Ég leggja til við skuldsett í viku eitt bragð. Unga fólkið rekstraraðila, hlutfall. Því ég er tæknilega standa á Staðsetning 3, en ég 3 unga fólkið getu, svo 3, sem er prósentumerkið, 3 - getu er 3. Hvað er það? Hvað er afgangurinn þegar þú skiptir 3 um 3? 0. Svo sem setur mig voru Jake var, sem er í raun gott. Svo nú framkvæmd þetta hlutur er að fara að vera hluti af höfuðverk. Það er í raun bara ein lína höfuðverkur, af kóða. En að minnsta kosti nú er það sorp gildi hér, en það er tveir lögmæt ints hér. Og ég halda því fram að nú höfum við gert nákvæmlega það sem við þurfum að gera svo lengi sem við að breyta því sem er Jake gildi var að vera 26.. Við höfum nú nægar upplýsingar ennþá að viðhalda heilleika af þessum gögnum uppbyggingu. Við erum enn eins konar út af heppni þegar við langar að setja fjögur eða fleiri samtals þættir, en ég get að minnsta kosti að gera nokkuð skilvirka notkun þessa föstu tíma, í raun. Ég þarf ekki að hafa áhyggjur af að breytast allir, sem halla Davíðs var. Einhverjar spurningar um stafla, eða þetta biðröð? Áhorfendur: Er ástæðan þú þarft stærð svo þú veist þar sem að hafa mann? DAVID Malan: Einmitt. Ég þarf að vita stærð fylkisins vegna þess að ég þarf að vita nákvæmlega hvernig margir af þessum gildum er lögmætur, og svo að ég geti fundið hvar á að setja á næsta mann. Einmitt. Stærð er - Reyndar höfum vér ekki að uppfæra þetta enn. Ég bætti mig í 26. The stærð er nú, ekki 1, en 2. Svo nú hjálpar þetta örugglega mér að finna höfuð á listanum, sem er ekki 0, ekki 1, en er 2. Framan af listanum er örugglega númer 22.. Vegna þess að hann kom í fyrsta, svo hann ætti að fá í búðina fyrir mig, jafnvel þó sjónrænt ég stend nær út í búð. Allt í lagi? A umferð af lófaklapp fyrir þessar krakkar og við munum láta þá út þaðan. [Applause] DAVID Malan: ég gæti látið þú halda bakkanum. Við gátum séð hvað gerist ef þú vilt, en kannski ekki. Allt í lagi. Svo hvað nú er að yfirgefa okkur? Jæja, láttu mig leggja til að það er Nokkur önnur mannvirki gögn við gátum byrja að bæta við verkfærasett okkar sem raun vera alveg, alveg eins viðeigandi og við kafa inn í vefsíðu efni. Sem aftur hefur einhvers konar tengslum til tre i formi eitthvað sem kallast DOM, skjal mótmæla líkan. En við munum sjá meira af að áður en langur. Leyfðu mér að leggja skilgreiningar sem við kalla tré nú hvað þú might vita sem meira af fjölskyldu tré, þar sem þú hafa sumir forfaðir á the rætr trésins. A rutt eða matriarch á the mjög toppur af trénu. Án maka þeirra, í þessu tilfelli. En við höfum nú það sem við munum kalla Börn, sem eru hnútar sem hanga burt vinstri barn eða hægri barn, Örvarnar sem lýst hér. Með öðrum orðum, í gögn tré uppbyggingu í tölvunni, tré hefur núll eða fleiri hnútar. Ef það hefur að minnsta kosti einn tengipunktur sem er kallað rót. Það er það sjónrænt sem við drögum efst. Og það hnút, eins og allir aðrir hnút, getur hafa núll, einn, eða tveir, eða þrír, eða hvernig sem mörg börn sem gögn uppbygging styður. Í þessu tilfelli er rót, geyma gildi einu, á tvö börn, 2 og 3, svo við köllum yfirleitt 2 á vinstri barn og 3 hægri barn. Og svo þegar við komum niður í 5, 6, og 7, 6 mætti ​​kalla miðju barnið. Ef þú hefur fjögur börn, það fær ruglingslegt. Þannig að við hætta að nota svona á flýtileið munnlega. En það er í raun bara fjölskyldu tré. Og blöðin hér eru hnútar sem sjálfir hafa engin börn. Þeir hanga á the botn af trénu. Svo hvernig gæti við innleiða tré sem hefur bara tvö börn hámarks? Við munum kalla það tvöfaldur tré. Bi þýðir aftur tvær, í þessu ræða, eins og tvöfaldur. Og svo það getur haft núll, einn, eða tvö börn hámarks. Ég leggja til að við framkvæmd hnút fyrir að uppbygging með int n, og þá tveir ábendingum, kallaði einn vinstri, kallaði einn rétt. En þeir eru bara nice handahófskennt samninga. Og hvað er gott núna, sérstaklega ef þú konar barátta eðli með endurkvæmni, eða hélt að það væri ekki raunverulega lausn á neinu, sérstaklega ef þú gætir hlaupa út af minni. Nú þegar við erum að tala um gögn mannvirki og reiknirit sem leyfa okkur að fara og vinna þá, kemur í ljós að endurkvæmni kemur aftur í miklu meira sannfærandi ef ekki falleg leið. Þannig að þetta sem ég leggja er framkvæmd á leit virka. Gefið tvær inntak - svo hugsa um þetta sem svartur kassi. Gefið tvær inntak, N, int, og bendi á tré, bendi til að hnút, eða í raun rót á tré, ég halda því fram að þessi aðgerð getur skilað satt eða ósatt, sem gildi n er inni í þessu tré. Hvað er inni í þessum svarta kassa? Jæja, fjórar deildir. Fyrsta bara tékka. Ef tré er null, bara return false. Ef það er engin hnút, það er engin n, það er ekkert númer skaltu bara aftur ósatt. Ef þó n, gildi sem þú ert að leita fyrir, er minna en tree arrow n, og bara til að vera skýr, hvað þýðir það þegar Ég skrifa tré og síðan á örina merki, n? Einmitt. Það þýðir dereference að bendillinn heitir tré. Fara þangað, og þá fá inni í því hnút og fá sínu sviði kallast n. Og þá bera saman raunverulegan n sem var lentu í Leita gegn henni. Þannig að ef n er minna en, í n value í tré Hnútur sig vel, hvað þýðir það? Það þýðir ekkert við fyrstu sýn. Ekki satt? Bara eins og þegar þú ert með fjölbreytta gildi, þú might eins og til að sækja tvöfaldur leita eins og a mynd af skipta og sigra. En hvað forsendu höfum vér þurfum að gera Fyrir tvöfaldur leita að vinna á öllum í símaskránni og fyrri dæmi? Hvernig á að vera flokkaður. Svo skulum betrumbæta skilgreiningu tré hér ekki að vera bara tré, sem getur hafa allir tala um börn. Ekki bara tvöfaldur tré, sem getur have 0, 1, eða 2 hámarks. En eins og a tvöfaldur leita tré eða BST, sem er bara fínt leið til að segja að tvöfaldur tré svo að sérhver hnútur er vinstri barn, ef til staðar, er minna en í hnút. Og hægri hverjum hnút er barn, ef til staðar, er meiri en hnút sjálft. Svo í öðrum orðum, ef þú varst að teikna tré út, eru allar tölur vandlega jafnvægi svona þannig að ef þú hefur 55 sem rót, 33 getur farið til vinstri þar sem hún er minna en 55. 77 getur farið til hægri þess vegna það er meiri en 55. En nú taka, sama skýring, það er endurkvæma skilgreiningu munnlega, þarf að sækja um 33. Vinstri barn 33 verður að vera minna en það, og hægri barn 33 er, 44, verður að vera stærri en það. Þannig að þetta er tvöfaldur leita tré, og Ég leggja til, með smá endurkvæmni, getum við nú fundið n. Þannig að ef n er minna en gildið n sem er núverandi hnút, ég ætla að fara undan og Punt, svo að segja, og bara aftur hvað svarið er leita n á vinstri glugganum er barn. Tilkynning aftur, þessi aðgerð bara væntir hnút Star, bendi á hnút. Svo örugglega ég get bara gert tré arrow vinstri, sem mun leiða mér annan hnút. En hvað er að hnútur? Jæja, samkvæmt þessari yfirlýsingu, vinstri er bara músina, þannig að bara þýðir að ég er liggur við leit virka annað músina, þ.e. sá sem stendur Vinstri barnsins míns tré. Þannig að í þessu tilfelli, the músina til 33, ef þetta er dæmi um inntak okkar sama tíma, ef n er meiri en gildi n AT THE núverandi hnút í trénu, þá er ég að fara á undan og Punt í öðrum stefnu og bara segja, ég er ekki vita ef þetta gildi n er í trénu, en ég veit ef það er, er það niður mín rétt grein, svo að segja. Svo láta mig símtali leita endurkvæmt, standast n aftur, en farið í bendillinn hægra barnið mitt. Með öðrum orðum, ef ég er nú á 55 og ég er að leita að 99, ég veit að 99 er meiri en 55, þannig að alveg eins og ég rifu Símaskrárstillingar vikum og við fór rétt, eru álíka við að fara hérna. Og ég veit ekki hvort það er á hægri hönd barn, og það er ekki, 77 er þar, en Ég veit að það er í þessa átt. Svo ég kalla leit á hægri barnið mitt, 77, og láta leita reikna út frá þar ef 99 í þessu handahófskennt dæmi er í raun þar. Annars, hvað er það sem kemur síðas málið? Ef tré er null er eitt mál. Ef n er minna en núverandi hnút er gildi er annað mál. Ef n er stærra en núverandi gildi Hnútur er þriðja mál. Hvað er fjórða og síðasta málið? Ég held að við séum út af málum, ekki satt? Það verður að vera að n sé á núverandi hnút sem ég er á. Þannig að ef ég er að leita að 55 á þessum tímapunkti í sögunni, að útibú á tré myndi skila satt. Svo er það sem er áhugavert hér að við reyndar, ólíkt vikum áður, góður við af hafa tvö grunn tilvikum. Og þeir þurfa ekki að vera allt að ofan. Efsta er undirstaða tilfelli vegna þess að ef Tréð er null, það er ekkert að gera. Bara aftur a harður dulmáli Verðmæti rangar. The botn útibú er tegund af sjálfgefið, þar ef við höfum athugað fyrir null, höfum við kannað hvort það ætti að vera vinstri, en það ætti ekki að vera, við höfum hakað ef það ætti að vera rétt, en það ætti ekki að vera, greinilega hefur það að vera rétt þar sem við erum. Það er grunn tilfelli. Svo er það tvö endurkvæma tilvikum samloka þarna í miðjunni. En ég gæti hafa skrifað þetta í hvaða röð sem er. Ég hélt bara að það var svona eðlilegt fyrst að athuga fyrir hugsanleg mistök, þá stöðva vinstri, þá stöðva rétt, þá gera ráð fyrir að þú ert í hnút þú ert í raun að leita að. Svo hvers vegna gæti þetta verið gagnlegt? Svo kemur í ljós - og láta mig hoppa til beitu hér er það á vefnum. Við erum að fara að byrja að nota ekki Forritunarmál í fyrstu, en Markup Language. A Markup Language vera einn sem er svipuð í anda að forritun tungumál, en það þýðir ekki að gefa þér hæfni til að tjá þig rökrétt. Það gefur aðeins þér möguleika á að tjá þig byggingu. Hvar viltu setja eitthvað á síðunni, heimasíðu? Hvaða litur viltu gera það? Hvaða leturstærð viltu gera það? Orð hvað gerir þú í raun vilt á vefsíðu? Svo er að Markup Language. En þá munum við mjög fljótlega kynna JavaScript, sem er a fullur-viðvaningur forritunarmál. Mjög svipuð setningafræðilega í útliti til C, en það mun hafa sumir nice, öflugri, meira notandi vingjarnlegur lögun. Og einn af óánægju í þessu benda á önn er að við munum fljótt innleiða Speller í mun færri línur af kóða með önnur tungumál en C sjálft gerir, en er ástæða við munum brátt skilja. Þetta verður fyrsta vefsíðan. Það verður alveg underwhelming, sá fyrsti sem við tökum. Það verður einfaldlega að segja halló heimur. En ef þú hefur aldrei séð það áður, þetta er HTML, HyperText Markup Language. Ef þú ferð að ákveðnu matseðill valkostur í flest allir flettitæki, á hvaða vefsíðu á internetið getur þú séð HTML að sumir skrifaði Búa þessi vefur blaðsíða. Og það sennilega ekki líta út eins og stutt eða eins snyrtilegur og þetta. En það mun fylgja mynstri þessara opna sviga og rista og bókstafir og hugsanlega númer. Ég hélt ég myndi gefa þér beitu af því sem þú munt vera fær um að gera eftir að taka CS50. Leyfðu mér að fara til cs.harvard.edu / ræna, Heimasíðan eigin Rob Bowden okkar. Hann gerði þetta fyrir okkur. Svo þú munt bráðum vera fær til gera þessi. Og einnig, hvað þú heyrt í morgun - hvað þú heyrt í morgun - [Hömstrum DANCE MUSIC] - You'Ll vera fær um að gera þetta. Það bíður okkar á miðvikudag. Við munum sjá þig þá. [Hömstrum DANCE MUSIC] DAVID Malan: Á næsta CS50 -