DAVID MALAN: Okei. Tervetuloa takaisin CS50. Tämä on alku viikolla 8. Ja muistaa, että ongelma asetettu 5 päättyi kanssa hieman haastetta. Joten olettaen talteen kaikki Opetuksen Fellows ja CA: n valokuvia vuonna card.raw tiedoston, olet oikeutettu nyt löytää kaikki ne ihmiset, ja yksi onnekas voittaja kävellä kotiin yhdellä näistä asioista, harppaus liikettä laite, että voit käyttää lopullisen hankkeita, esimerkiksi. 

Tämä, joka vuosi, johtaa vähän creepiness. Ja niin mitä ajattelin tehdä, on kertoa teille joitakin säveliä, jotka ovat mennyt edestakaisin henkilöstön luettelo myöhään. Esimerkiksi juuri viime yönä, lainaus listatut, yhdestä henkilöstön jäsenet, "Minulla oli opiskelija knock oveni ottaa valokuvan kanssani. Stalkers, minä sanon teille. "Aloitit melko kuvaileva ja sitten muutimme edelleen, tunti tai niin myöhemmin, "Minulla oli opiskelija odottaa minua jakson jälkeen Hän oli meidän kaikkien nimet ja kuvat joitakin arkkia paperia. "Selvä. Niin järjestetty, mutta ei kaikki kammottava vielä. 

Sitten, "Olin poissa kaupungista tänä viikonloppuna, ja kun tulin takaisin, oli yksi minun makuuhuone. "[naurua] DAVID MALAN: Seuraava lainaus henkilöstö jäsen ", opiskelija tuli kotiini Somerville kello 4 aamulla. "Seuraava henkilökunta, "pääsin hotelli San Francisco ja opiskelija odotti minua aulassa kolme DSLRs. " Tyyppinen kamera. "En ole edes henkilökuntaa tämän lukukauden, mutta opiskelija murtautui talooni tämän aamu ja kirjataan koko juttu Google Glass. "Ja sitten lopuksi, "Ainakin 12 ihmistä olivat innokkaasti odottavat minua, kun sain ulos limusiinin, ja sitten minä heräsi. "Selvä. Joten keskuudessa valokuvia, kuten ehkä muistaa, ovat tämän kaveri täällä, kuka olet voi tietää kuin Milo Banana, joka asuu Lauren Carvalho, meidän pään opetus Fellow. Milo, Milo, tule tänne poika. Milo. Milo. Huomatkaa, hän on päällään Google Glass, joten näytämme sinulle kaiken tämän jälkeen. Joten tämä on Milo, jos haluat ottaa valokuvan hänestä jälkeenpäin. Jos haluat varoa yleisöön siellä. OK. Se on hyvä kuvamateriaalia. No, Milo Banana. Voi, älä tee sitä. 

[Naurua] 

OK. Joten sana sitten mitä on edessä, sillä kun alamme siirtyminen, tällä viikolla nimenomaan, alkaen C komentoriviympäristössä PHP ja JavaScript ja SQL ja HTML ja CSS web-pohjainen ympäristö, me olemme varustaminen sinulle kaikki lisää tietämystä mahdollisten lopullisten hankkeita. Kohti sitä varten kurssi on perinteisesti järjestetty seminaareja, jotka ovat sivuaa aiheita sen kurssin. Hyvin paljon ohjelmointia ja app kehitystä ja niin edelleen, mutta ei välttämättä selvittävät Tietenkin oma oppimäärä. 

Joten jos saatat olla kiinnostunut yksi tai enemmän tämän vuoden seminaareja, rekisteröityä cs50.net/seminar. On vanhempia seminaarit klo cs50.net/seminars. Ja lista tähän mennessä tänä vuonna ovat Amazing Web Apps kanssa Ruby on Kiskot, joka on vaihtoehtoinen kieli PHP. Computational Linguistics. Johdatus IOS, joka on alustan, joka käyttää iPhone ja iPad kehitystä. JavaScript Web Apps, me kattaa että, mutta tässä seminaarissa, voit mennä yksityiskohtaisempi. 

Leap Motion, niin me todella on joitakin meidän ystäviä Leap Motion, yhtiölle itselleen, liittyä meihin. Huomenna, itse asiassa, jotta voidaan tarjota käytännön seminaarin, jos kiinnostaa sinua. Meteor.js, vaihtoehtoinen tekniikka JavaScriptin avulla ei selain, mutta palvelimella. Node.js, joka on hyvin paljon että vein samoin. Tyylikäs Android muotoilu. Android on erittäin suosittu vaihtoehto iOS ja Windows Phone ja muut mobiilialustoille. Ja Web Security Active Defense. 

Joten itse asiassa, jos haluat osallistua tähän, haluan muistiin tämän. Olemme erittäin iloinen voidessani todeta, että ystävämme Leap Motion, joka on käynnistyksen - tämä laite todella vain tuli muutama kuukausi sitten - on armollisesti lahjoitti 30 tällaisia ​​laitteita luokkaan, niin monet opiskelijat, jos haluat lainata laitteisto kohti lukukauden lopussa ja käyttää sitä Varsinainen opinnäytetyön. Ne tukevat useita kieliä. Mikään niistä C, mikään niistä PHP, niin saavuttamaan yksi tai useampi näistä seminaareja saattaa osoittautua kohteisiin. Ja ne kaikki on kuvattu Jos et pysty osallistua henkilökohtaisesti. Aikataulu julkistetaan kautta email me jähmettyä huonetta. 

Ja lopuksi, jos menet projects.cs.50.net, tämä on sivusto meidän pitää joka vuosi, että kutsumme folks yhteisö, tiedekunta, yksiköt, henkilökunta ja molemmat in ulkopuolella CS50 on ehdottaa projekti-ideoita. Asiat kiinnostavat opiskelijaryhmille. Kiinnostavia asioita osastojen. Joten älä käännä siellä, jos olet kamppailee epävarmuutta siitä, mitä itse haluaisi puuttua. 

Joten viimeinen kerta toimme kiistatta monimutkaisempi tietorakenne kuin olimme nähdään viikkoa aikaisemmin. Olimme käyttäen paneelit melko onnellisina hyödyllistä, jos yksinkertainen tietorakenne. Sitten otimme käyttöön nämä, jotka tietenkin liittyvät luettelot. Ja mikä oli yksi motiiveja käyttöön tämän tietorakenne? Niin? Mikä tuo on? 

Yleisö: Dynamic koko. 

DAVID MALAN: Dynamic koko. Joten taas joukko, joudut tietää sen koko etukäteen, kun voit jakaa sitä. Vuonna linkitetty lista, et täytyy tietää, että. Voit vain malloc, tai yleisemmin myöntää lisää solmu, niin sanotusti, milloin tahansa haluat lisätä enemmän tietoa. Ja solmu ei ole ennalta määrättyä merkitystä. Se on vain yleinen termi, joka kuvaa jonkinlainen säiliö, että olemme käyttämällä meidän tietorakenne tallentaa jotkut erä kohteisiin, jotka tässä Jos sattuvat olemaan kokonaislukuja. 

Mutta on aina kompromissi. Joten saamme dynaaminen koot tiedot rakenne, mutta paljonko maksaa me maksamme? Mitä haittapuoli linkitettyjen listojen? Niin? 

Yleisö: Vaatii enemmän muistia. 

DAVID MALAN: se vaatii enemmän muisti, miten tarkalleen? 

Yleisö: [kuultavissa]. 

DAVID MALAN: Aivan. Joten nyt meillä on viitteitä aloittamisesta lisämuistia, että aiemmin ei tarvitse, koska etu array, on tietenkin se, että kaikki on yhtenäinen, takaisin takaisin takaisin, joka antaa random access. Koska vain käyttämällä hakasulkeen merkintä, tai teknisesti osoitin aritmeettinen, hyvin yksinkertainen Lisäksi Pääsetkö elementit jatkuvasti ajan. Ja itse asiassa, että on tavallaan vihjaten toinen hinta, että maksat kanssa linkitetty lista. 

Mitä tapahtuu käyntiaika jotain Etsi, jos haluan löytää arvo ja sisällä of linkitetty lista? Mitä minun käyntiaika tullut? Big O n. Jos se lajitellaan? Mitä jos tietorakenne on järjestetty? Voinko tehdä paremmin kuin suuret O n etsimiseen? Ei, koska pahimmassa tapauksessa se voisi hyvin lajitellaan, mutta määrä etsit saattaa olla suuri. Se voi olla numero 100, joka ehkä sattuvat olemaan kaikki Muuten lopussa. Ja koska voit käyttää vain linkitetyn Luettelen tällä täytäntöönpano tapa sen ensimmäisen solmun, olet vielä sellainen epäonninen. Sinun täytyy kulkea koko juttu ensimmäisestä viimeiseen, jotta löydettäisiin että iso arvo kuin 100. Tai onko se ei edes siellä. 

Joten emme voi tehdä mitä algoritmia datan rakenne, joka näyttää tältä? Emme voi tehdä binäärihaku, koska binäärihaku vaaditaan, että meillä oli random access. Voisimme vain harppaus sijainnista sijainti ilman seuraa Näiden korppujauhoja muodossa kaikki nämä viitteet. 

Nyt, miten voimme toteuttaa tämän? No, jos menemme näytön täällä, jos Voimme nopeasti reimplement nämä tiedot rakenne - minun käsiala ei ole kaikki, että hyvä täällä, mutta me yritämme. Joten struct, ja mitä tein haluat soittaa tämä asia täällä? Solmu. Joten Haen alkoi. Ja nyt, mitä pitää sisällä datarakenteen, että yksittäin linkitetty lista? Kuinka monilla aloilla? 

Joten kaksi. Yksi on melko helppoa. Joten int n. Ja voisimme kutsua n mitä me haluamme, mutta sen pitäisi olla int, jos olemme täytäntöön linkitetty lista ints. Ja nyt, mitä tekee toinen alan olla? Struct solmu *. Joten jos en struct solmu *, ja sitten minä voi kutsua tätä myös mitä haluan, mutta vain olla selkeä soitan sitä seuraava, kuten olemme tehneet. Ja sitten minä suljen aaltosulkeita. 

Ja nyt, kuin viime kerralla, Laitoin solmun tänne. Mutta jos olen julistaa tämä on niin solmu, miksi olen vaivautua on niin verbose täällä julistaa struct solmu * seuraavaksi, toisin vain solmu * seuraavaksi? Niin? 

Yleisö: [kuultavissa]. 

DAVID MALAN: Aivan. Täsmälleen. Koska C todella vie kirjaimellisesti ja näkee vain määritelmän solmun alas täällä, et voi viitata siihen täällä. Joten meillä on tällainen ennaltaehkäisevä ilmoitus täällä, joka on tosin Pidempi. Struct solmu, joka tarkoittaa voimme nyt käyttää sitä sisällä tieto-rakenteesta. 

Ja syrjään, koska tämä on tulossa hieman subjektiivinen nyt tähti voi teknisesti mennä täällä, se voi mennä täällä, se voi jopa mennä keskellä. Olemme hyväksytty, tyyliin opas Tietenkin yleissopimus laskemisesta tähden vieressä tiedot tyyppi, joka tässä tapauksessa olisi struct solmu. Mutta realisoida paljon oppikirjoja ja online-viittauksia, saatat todellakin nähdä sen toisella puolella. Mutta vain ymmärtää, että molemmat todella työtä ja sinun pitäisi vain olla johdonmukainen. 

Selvä. Niin, että oli meidän ilmoitus struct solmu. Mutta sitten aloimme tehdä enemmän kehittyneempiä asioita. Esimerkiksi päätimme ottaa käyttöön jotain tiiviste. Joten tässä on hash taulukon koko on n, indeksoitu 0 päälle vasemmalle n miinus 1 vasemmassa alareunassa. Tämä voisi olla hash taulukossa mitään. Mutta millaisia ​​asioita ei puhumme noin käyttämällä hash taulukon? Tallentaminen mitä? 

Nimet. Voisimme tehdä nimiä kuten teimme viime kerralla. Ja oikeastaan, voit tallentaa mitään. Ja näemme tämän uudelleen PHP ja JavaScript. Tiiviste on mukava eräänlainen Sveitsin Armeijan veitsi, jonka avulla voit tallentaa aika paljon mitä haluat sisällä se liittämällä avaimet arvot. Avaimet arvot. 

Nyt tässä yksinkertaisessa tapauksessa meidän avaimet ovat vain numeroita. Olemme täytäntöönpanosta hash taulukon array. Ja niin näppäimet ovat 0, 1, 2, ja niin edelleen. Ja niin me, ihmisinä, päätti viime viikolla, että tiedät mitä, jos olemme menossa tallentaa nimiä, haluan vain mielivaltaisesti, vaan ihan kohtuullisesti, olettaa, että Alice, nimi, vain indeksoidaan 0. Ja Bob, B nimen, indeksoidaan otetaan 1, ja niin edelleen. Joten meillä oli kartoitus tulojen välillä, jotka ovat jouset, ja hash paikoissa, jotka ovat numeroita. 

Niin, että prosessi on yleisesti tunnettu hash funktio, ja voit todella pantava se koodi. Jos halusin toteuttaa hajautusfunktio joka tekee täsmälleen mitä me juuri kuvattu viime aikaa, voisin julistaa funktio, joka ottaa, koska input esimerkiksi - ja tehdään tämä tästä näytön tänne. Jos halusin toteuttaa hash toiminto, voisin sanoa jotain tällaista. 

Se tulee palauttaa int. Se tulee kutsua hash, ja se on aio hyväksyä väitettä string, tai voimme olla oikeampi nyt ja sanoa char *, me kutsumme sitä s. Ja sitten kaikki tämä toiminto on tekemistä, lopulta on palauttaa int. Nyt, miten se, että saattaisi ei ole niin selvä. Aion toteuttaa tätä ilman muodossa virheentarkistusta juuri nyt. Olen juuri menossa sokeasti sanoa, palauta mitä on s kiinnike 0, miinus, sanotaanko, pääoman puolipiste. 

Täysin rikki. Se ei ole täydellinen, koska yksi, mitä jos s on nolla? Pahoja asioita tapahtuu. Kaksi, mitä jos ensimmäinen kirjain tässä nimi ei ole kirjain? Se ei tule kääntää ulos hyvin joko. Se voi olla pieni kirjain tai kirjeen ollenkaan. Joten täysin parantamisen varaa, mutta tämä on perusajatus. 

Mitä me kuvattu viime viikolla sanallisesti vain kartoituksesta Alice 0 ja Bob 1 voidaan ilmaista varmasti enemmän formulaically kuin C toimi täällä. Kutsutaan uudelleen hash, vie merkkijonon tulo, ja sitten jotenkin tekee jotain kanssa tulo tuottaa tuotoksen. Ei toisin kuin meidän musta laatikko kuvaus että olemme pitkään tehneet. En tiedä, miten tämä voisi olla työskentelevät alla huppu. 

Jos ongelma asettaa 6, yksi haasteista on sinun päättää, mitä tulee teidän hajautusfunktio olla? Mikä tulee olemaan sisällä että musta ruutuun, ja oletettavasti se tulee olemaan hieman mielenkiintoisemman kuin tämä, ja varmasti enemmän virhealtista tarkkailun kuin tässä täytäntöönpanoa. 

Mutta ongelmia voi syntyä, eikö? Jos meillä on tietorakenne kuten tämän yksi, mikä on yksi ongelmista voit törmätä ajan, kun asetat enemmän ja enemmän nimiä tiiviste? Saat törmäykset, eikö? Mitä jos sinulla on Alice ja Aaron, kaksi ihmistä, joiden nimet tapahtui aloittaa? Tässä herääkin kysymys, missä laita toinen tällainen nimi? 

No, ehkä naiivisti laittaa sen jossa Bob kuuluu, mutta sitten Bob on Tällainen ruuvattu jos yrität lisätä hänen nimensä vieressä ja Ei ole tilaa hänelle. Joten voit saattaa Bob missä Charlie on, ja voitte kuvitella tämän hyvin nopeasti hajauttaa osaksi hieman sekaisin. Jotain lineaarinen lopussa, jossa täytyy vain etsiä koko juttu etsivät Alice tai Bob tai Aaron tai Charlie. 

Joten sen sijaan ehdotimme, eikä vain lineaarisesti luotaa aukiot ja plopping nimet siellä, me ehdotti harrastaja lähestymistapaa. Tiiviste toteutettu silti joukko indeksejä, mutta tietotyyppi nämä indeksit olivat nyt viitteitä. Viitteitä mitä? Osoittimet liittyvät luettelot. 

Koska muistaa, että linkitetty lista on oikeastaan ​​vain osoitin solmuun, ja solmu on seuraavaan kenttään, ja että solmu on seuraava kenttä, ja niin edelleen. Joten nyt voit ajatella tätä array vasemmalla puolella hash-taulukon mikä linkitetty lista. Etuna on, jos saat yhteentörmäys Alice ja Aaron, mitä te teette Toinen tällainen henkilö? Sinä vain liittää hänet loppuun, tai jopa alussa Tämän linkitetty lista. 

Ja oikeastaan ​​haluan vain nuudeli kautta että vain toinen. Jos olisi mielekästä? Jos asetan Alice ja hän päätyy ensimmäinen paikka, sitten yritän aseta Aaronin nimi, ja siellä on ilmeisesti törmäyksen, minun pitäisi laittaa hänelle alussa on linkitetty lista? Se on, että ensimmäinen paikka, tai lopussa? 

Yleisö: [kuultavissa]. 

DAVID MALAN: OK. Kuulin alussa. Miksi alussa? 

Yleisö: [kuultavissa]. 

DAVID MALAN: OK. Se on aakkosjärjestyksessä, joten on mukavaa. Se on hyvä ominaisuus. Se säästää minulle aikaa mahdollisesti. Se ei anna minun tehdä binäärihaku, mutta voisi ainakin voi puhjeta loop-jos ymmärrän hyvin, olen niin aiemmin olivat Aaron olisi tässä lajiteltu linkitetty lista. Minulla ei tarvitse tuhlata aikaa etsimässä aina loppuun. Niin, että on kohtuullista. Miksi muuten ehkä haluat lisätä törmäävän nimi on listan alkuun? Mikä tuo on? 

Yleisö: [kuultavissa]. 

DAVID MALAN: Se voi kestää kauan päästä listan loppuun. Ja itse asiassa, pidempään. Enemmän nimiä asetat, että aloittaa, mitä kauemmin ketju on menossa. Enää, että linkitetty lista on menossa. Joten olet todella vain tuhlaa aikaa. Ehkä olet parempi säilyttää jatkuva asetettiin paikoilleen, iso O 1, olemalla aina laittamalla törmätä nimitys alussa linkitetty lista, eikä huolestuttava niin paljon lajitteluun. 

Mikä on paras vastaus? On epäselvää. Se ikään kuin riippuu siitä, mitä jakelu on, mikä malli on nimet asetat. Se ei ole välttämättä ilmeinen vastaus. Mutta täällä on taas suunnittelu tilaisuus. 

Niin me sitten katsoin tämä asia, joka on todella toinen suuri mahdollisuus p-set 6. Ja ymmärtää, jos et ole jo, Zamyla sukeltaa molempia, hash taulukoita ja yrittää, yksityiskohtaisemmin. Ja videoesityksen on upotettu p-set spec. Tämä oli trie - T-R-I-E. Ja mikä oli mielenkiintoista Tämä oli se, että ajoaika etsivät nimi, kuten Maxwell viime kerralla, oli iso O mitä? Mikä tuo on? 

Yleisö: määrä kirjaimia. 

DAVID MALAN: Numero kirjeitä. Kuulin kaksi asiaa. Useita kirjeitä ja jatkuva ajan. Joten mennä, että ensin. Määrä kirjaimia. No, tämä tietorakenne, muistaa, on kuten puu, sukupuu, kukin jonka solmut koostuvat ryhmät. Ja ne paneelit ovat osoittimia muita tällaisia ​​solmuja, tai muita sellaisia taulukot puu. 

Joten jos halusimme sitten määrittää onko Maxwell on täällä, voisin mennä ensimmäiseen array, aivan huipulla puu, niin sanottu juuri, alkuun trie ja noudata m osoitin, Sitten osoitin, niin x, w, e, l, l. Ja sitten kun näen joitakin erikoismerkkejä, merkitään täällä kolmio. Koodin näet ehdotamme, että toteutetaan bool, vain sanomalla kyllä tai no, sana loppuu tähän. 

No, kun olemme menneet M--X-W-E-L-L, tuntuu seitsemän, ehkä kahdeksan jos menemme ohi, kahdeksan ohjeita löytää Maxwell. Tai kutsutaan sitä K. Mutta muistaa viimeksi aikaa, totesin, että jos siellä realistisesti maksimipituus on sana, kuten 40-joitakin-kummallisia merkkejä, enimmäispituus merkitsee vakioarvo. Siis todella, kyllä, se on teknisesti iso O 8 tai 7, tai oikeastaan ​​iso O K. Mutta jos on rajallinen korkki mitä K voisi olla, se on vakio. Ja niin se on iso O 1 at päivän päätteeksi. 

Ei todellisessa maailmassa. Ei kun todella alkaa katsella kellon kuin ohjelman käynnissä. Se ehdottomasti olemaan hieman hitaammin kuin todella jatkuvasti aikaa yksi askel. Se tulee olemaan seitsemän tai kahdeksan vaihetta, mutta silti se on paljon, paljon parempi kuin algoritmi iso O n että riippuu koosta mitä on tietorakenne. 

Huomaa ylösalaisin tässä voimme lisätä euroa enemmän nimiä tähän tietorakenne, mutta kuinka paljon enemmän vaiheita se aikoo viedä meidät löytää Maxwell tässä tapauksessa? Ei mitään. Hän on ennallaan. Ja tähän mennessä, en usko, olemme nähneet Esimerkkinä tietojen rakenteen tai algoritmi, joka oli täysin vaikuta ulkoiset käyttäytymistä niin. Mutta tämä ei voi olla hämmästyttävä. Tämä ei voi olla ainoa ratkaisu ja p-set 

Ja se ei ole. Tämä ei välttämättä ole tietoa rakenne pitäisi kallistua, koska kuten hash taulukoita, kompromissi. Mikä on hinta maksat täällä? Muisti. Tarkoitan, tämä on kamalaa muistin määrä. Ja et oikein näe sitä täällä, koska Kirjailija tämän kuvan ilmeisesti katkaistu kaikki paneelit ja emme näe paljon n ja B: n ja C: n ja Q: n ja Y: n ja Z: n näissä ryhmät. Mutta ne ovat siellä. 

Jokainen näistä solmuista on koko joukko on noin 26 tavua tai useampia tavuja, ja jokainen mikä kirjain. 27 meidän tapauksessamme, jotta voimme tukea heittomerkit ongelma set. Joten tämä tieto rakenne on todella, todella tiheä ja leveä. Ja että yksin päätyä hidastaa asioita alas, tai ainakin maksaa sinulle paljon enemmän tilaa. Mutta jälleen kerran, voimme tehdä vertailuja tässä. 

Recall taas takaisin, olemme saavuttaneet paljon jännittävämpää käyntiaika lajittelu kun käytämme yhdistäminen tavallaan, mutta hinta maksoimme saavuttaa n log n ja yhdistäminen sort vaaditaan, että käytämme enemmän mitä resursseja? Enemmän tilaa. Tarvitsimme toisen array kopioida ihmisiä, aivan kuten teimme täällä lavalla. Joten jälleen, ei ole selvää voittajaa, mutta vain subjektiivinen suunnittelu päätökset tehdään. 

Selvä. Joten miten tästä? Jokainen tunnistaa mikä D-Hall? OK. Joten me kolme tehdä. Mather House. Tässä siis Mather ruokasalissa. Lyön vetoa, kaikki ruokasalia on pinot tarjottimia näin. Ja tämä on todella edustava jotain olemme ilmeisesti nähnyt jo. Kutsuimme sitä kirjaimellisesti pino. Ja pino, mitä teidän tietokoneen muistiin, on, jos data menee kun toimintoja on kutsuttu. 

Esimerkiksi millaisia ​​asiat menevät pinoon nähden Muistin sijoittelu olemme keskustelleet viikkoina aikaisemmin? Mikä tuo on? 

Yleisö: Puhelut toimintoja. 

DAVID MALAN: Olen pahoillani. 

Yleisö: Puhelut toimintoja. 

DAVID MALAN: Puhelut toimintoja, mutta nimenomaan, mitä sisällä kunkin näitä kehyksiä? Millaiset asiat? Joo. Niin paikallisia muuttujia. Aina kun tarvitaan joitakin paikallisia varastointi, kuten väite, tai int I, tai int temp, tai mitä tahansa paikallisen muuttuja, olemme olleet laskemisesta, että pinoon. Ja me kutsumme sitä pino, koska Tämän kerrospukeutuminen idea. Juuri sellainen otteluita jopa todellisuuden kanssa, käsite viipymättä. 

Mutta näyttää siltä, ​​että pino voi myös pidettävä tietorakenne, vaihtoehto array, vaihtoehtoisen on linkitetty lista. Jotain käsitteellisesti mielenkiintoisempaa , joka voi vielä olla toteutetaan käyttäen joko näiden asioita, mutta se on eri tyyppistä tietorakenne tukevat, todella, vain kaksi operaatiota. Mutta voit lisätä harrastaja ominaisuuksia kuin nämä. Mutta nämä ovat perusasiat - push ja pop. 

Ja idea pino on, että jos minä täällä, tai ilman Annenberg tietäen, lokero vieressä jossa numero 9 sitä. Joten int. Ja haluan ajaa tämän päälle tiedot rakenne, joka tällä hetkellä on tyhjä. Mieti tätä pinon pohjalle. Haluaisin ajaa tämän numeron 9 päälle pino, ja nyt se on tuolla. 

Mutta mielenkiintoinen asia pino on, että jos en nyt halua työntää jokin muu arvo, kuten 17, ja painan Tämän pinoon, aion tehdä vain intuitiivinen asia, olen juuri menossa laittaa ne juuri siinä missä me ihmiset olisivat taipuvaisia ​​laittaa sen, päälle. Mutta mitä nyt mielenkiintoinen on, miten saan klo 9? Tiedäthän, en ilman jonkin verran vaivaa. 

Niin mitä mielenkiintoista pino on, että suunnittelu, se LIFO tietorakenne. Typerä tapa kuvata last in, first out. Joten viimeinen numero tällä kertaa oli 17. Joten jos haluan pop jotain pois pinon, se voi olla vain 17. Joten on pakollista järjestyksessä toimintaa täällä, missä viimeinen kohde siihen on oltava ensimmäinen ulos. Näin lyhenne, LIFO. 

Joten miksi tämä voisi olla hyödyllistä? Ovatko ne puitteet, joissa olisit haluavat tietorakenne näin? No, se on varmasti ollut hyötyä sisällä tietokoneen. Joten käyttöjärjestelmien selvästi käyttää tätä Tällainen tietorakenne pinot. Otamme myös nähdä sama ajatus kun se tulee web-sivuja. Joten tällä viikolla ja ensi viikolla ja sen jälkeen, ja kun alkaa toteuttaa web sivut kieltä kutsutaan HTML, voit itse käyttää tietorakenne kuten Tämä määrittää, onko sivu on oikein muotoiltu. Koska näemme kaikki sivut noudattavat eräänlainen hierarkia, syvennys joka, lopussa päivä, olla puurakenne alla huppu. Joten lisää, että vain vähän. 

Mutta nyt, nyt ehdottaa hetkellä, miten voisimme edetä eli mitä pino on? Saanen ehdottaa, että toteutamme pino koodilla näin. Joten pino tulee olemaan sen sisällä kaksi asiaa, array, nimeltään tarjottimia, vain oltava demo. Ja jokainen kohteita, että joukko tulee olemaan tyyppiä int. Ja kapasiteetti on oletettavasti mitä? Koska en ole kirjoittanut koko määritelmä täällä. 

Se on luultavasti suurin koko joukko. Ja se on luultavasti ilmoitettu terävä määritellä tiedoston alkuun, jotkut Tällainen jatkuva kuten ehdotetun pelkkä arvo. Joten jonnekin kapasiteetti määritellään kuin suurin mahdollinen koko. Samaan aikaan, sisällä tietorakenteen tunnetaan pino siellä tulee olla kokonaisluku vain tiedossa yksinkertaisesti koko. 

Joten jos olisin edustamaan tätä nyt kuvallisesti Oletetaan, että tämä koko musta laatikko edustaa minun pino. Sisältä se on kaksi muuttujaa. Joten aion tehdä Ensimmäinen kuin koko. Ja toinen aion piirtää taulukkona. 

Mutta vain pitää asiat hallittu, normaalisti Haluaisin kiinnittää array kuten , mutta se on tavallaan mukavaa jos vastaa todellisuutta, tai ottelu mielikuvaan. Joten haluan sen sijaan kiinnittää array pystysuunnassa, joka on vain, jälleen, taiteilijan luovuttamista. Ei ole oikeastaan ​​väliä, mitä se on alla huppu. Ja me sanomme, että oletuksena, kapasiteetti tulee olemaan kolme. Joten tämä on paikka 0, tämä on paikalla 1, tämä on paikka 2. 

Jos minä lahjoa kanssa stressipallo, olisi joku haluaa tulla ja ajaa aluksella tässä vain hetken? OK, näki kätesi ensin. Tule ylös. Selvä. Joten mielestäni on Steven. Tule ylös. Selvä. 

Mutta oletetaan nyt kelaa alkuperäisen maailman tilasta, jossa I juuri ilmoittanut pino, ja se on olemaan kapasiteetin kolme. Mutta koko ei ole vielä määritelty. Alustat ei ole vielä määritelty. Joten pari kysymystä ensin. Ja minä annan sinulle mikrofoni, joten voit osallistumme aktiivisemmin tässä. 

Joten mitä on sisällä koko tällä hetkellä ajoissa, jos kaikki olen tehnyt on julisti pino yhtä riviä koodia? 

STEVEN: Ei paljon. 

DAVID MALAN: OK, ei paljon. Tiedämmekö mitä sisällä koko, tiedämme mitä sisällä Tämän array täällä? 

STEVEN: Vain satunnainen koodi, eikö? Just - 

DAVID MALAN: Joo, aion kutsuvat sitä koodia, mutta satunnainen - 

STEVEN: Things. 

DAVID MALAN: Asiat kuten random 

Steven: Bits. 

DAVID MALAN: Bits, eikö? Joten roskat arvot, eikö? Joten permutaatiot 0: n ja 1. Jäänteitä edellisen käyttötarkoituksissa Tämän muistin. Ja emme todellakaan tiedä, mitä arvoja ovat, niin me yleensä tehdä niitä kysymysmerkkejä. 

Joten ensimmäinen asia, olemme oletettavasti menossa haluavat tehdä täällä - ja haluan antaa tämän alan sisällä siellä nimi - tarjottimia. Mitä meidän pitäisi luultavasti alustaa kokoa, jos haluamme aloitat pino? 

STEVEN: Alusta on osa 3. 

DAVID MALAN: Niin, OK. Olla selkeä, kapasiteetti on julistettu muualla kuin kolme. Ja se mitä olen käyttänyt jakaa array. Koko aikoo viitata kuinka monta lokerot ovat tällä hetkellä pino. 

STEVEN: Zero. 

DAVID MALAN: Niin sen pitäisi olla nolla. Joten mene eteenpäin, ja kaikki sormella, piirtää nolla kokoisia. Selvä. Joten nyt, mitä sisällä tämän täällä, emme tiedä. Nämä ovat oikeastaan ​​vain roskaa arvot. Jotta voisimme tehdä kysymysmerkkejä, mutta Pidetään hallituksen puhtaana nyt koska se ei ole väliä mitä siellä. Meidän ei tarvitse alustaa array mitään, sillä jos me tiedämme pinon koon on nolla, no, me ei pitäisi tarkastella mitään Tämän array muutenkin at tässä vaiheessa. 

Joten nyt olettaa, että painan numero 9 pinoon. Miten meidän pitäisi päivittää tietorakenne sisällä tämä musta laatikko? Mitä arvoja täytyy muuttaa? 

STEVEN: Within - koko? 

DAVID MALAN: OK. Koko pitäisi tulla mitä? 

STEVEN: Koko olisi yksi. 

DAVID MALAN: OK. Joten koko tulisi olla yksi. Joten voit tehdä tämän pari tapaa. Annan teille nyt oman sormi on pyyhekumi. Selvä. Niin nyt sormi on harjalla. Selvä. Ja nyt, mitä muuta on muututtava, On selvää, että tietojen rakenne? 

STEVEN: Menemme alkaen alhaalta ylöspäin 9. 

DAVID MALAN: 9. OK, hyvä. Niin silti ei ole väliä mitä on sijainti yksi tai kaksi, koska he roskat arvot, mutta meidän ei pitäisi vaivata näköinen siellä, koska koko on kertovat meille, että vain ensimmäinen tekijä on todella oikeutettua. Joten nyt painan 17 päälle lista. Mitä tapahtuu tätä kuvaa? 

STEVEN: Eli koko on menossa kaksi. 

DAVID MALAN: OK. Olet pyyhekumi - oho. Olet pyyhekumi. 

STEVEN: Eraser. 

DAVID MALAN: Olet harjalla. 

STEVEN: Brush. 

DAVID MALAN: OK. Ja mitä muuta? 

STEVEN: Ja sitten me - 

DAVID MALAN: Työnsimme 17. 

STEVEN: Pysymme 17 päälle, niin - 

DAVID MALAN: OK, hyvä. 

STEVEN: - pudota alas. 

DAVID MALAN: Okei. Se on tulossa helppoa. En aio auttaa sinua tällä kertaa. Push 22. 

STEVEN: Valmis. Becoming pyyhekumi. Olen tulossa harjalla. Ja sitten olen laskemisesta 22. 

DAVID MALAN: 22. Erinomainen. Joten vielä kerran. Minä lähden nyt työntää pinoon 26. 

STEVEN: Ooh. Voi hemmetti. Olet todella sai minut kiinni kenet. 

DAVID MALAN: Et ole näkee tällaista? 

Steven: En näe tätä tulossa. Voisimme uudelleen alkuperäisestä kapasiteetista? 

DAVID MALAN: Se on hyvä kysymys. Joten olemme sellainen maalattu itse huoneen nurkkaan täällä. Ei todellakaan ole mitään hyvää ulos Steven koska olemme myönnetty tämän taulukon staattisesti, niin sanotusti sisälle tieto-rakenteesta. Ja olemme lähinnä kova koodattu se on kooltaan kolme. Joten emme voi kohdentaa sitä. 

Voisimme jos menimme takaisin, me uudelleen kaukaloiden osoitin, että me sitten käyttää malloc käteen muistia. Koska jos saimme muisti kasaan kautta malloc, me voisi sitten vapauttaa sen. Mutta ennen vapauttaa se, voisimme kohdentaa isompi kimpale muisti, päivittää osoitin, ja niin edelleen. Mutta nyt, tämä on todella Parasta mitä voimme tehdä. Push ja pop ovat oletettavasti menossa on viestittää jokin virhe. 

Niin esimerkiksi meidän täytäntöönpano push voisi palata bool joka aiemmin palasi totta, totta, totta. Mutta neljännen kerran, se tulee olemaan palata vääriä, esimerkiksi. Selvä. Hyvin tehty. Onneksi olkoon. Olet ansainnut stressipallo tänään. 

[APPLAUSE] 

STEVEN: Kiitos. 

DAVID MALAN: Kiitos. OK, joten tämä tuntuu olla paljon ja askel eteenpäin, eikö? Me kuvataan tämän tietorakenteen. Se on ollut vakuuttava, eikö? Käyttöjärjestelmät pidä siitä. Ilmeisesti verkossa voi käyttää tätä, ja muita sovelluksia edelleen. Mutta mitä tyhmä rajoitus, että olemme Takaisin tavallaan viikon kahden rajan jossa on kiinteä koko taulukot. 

Joten on todellakin pari tavalla voisimme ratkaista. Voisimme dynaamisesti jakaa array, eikä kova koodaus sen olen täällä tehnyt, vaan uudelleen julistamisesta Tämän vain olla selkeä, sillä jotain tällaista. Int * tarjottimia, ei päättää tarjonnan vielä. Mutta kun julistaa pino muualla minun koodi, voisin sitten soittaa malloc, saada osoitteen kimpale muisti, ja voisin antaa että osoite tarjottimia. 

Ja sitten, koska se on vain kimpale muisti, voisin edelleen käyttää neliö kiinnike merkintä tavalliseen tapaan. Koska uudelleen, siellä on tavallaan tämän toiminnallinen vastine taulukot ja paloina muistia, jotka tulevat takaisin malloc. Voimme kohtelevat kuin muut käyttäen osoitin aritmeettinen tai hakasulkeen merkintätapa. Niin, että yksi lähestymistapa. 

Mutta miten muuten voisimme toteuttaa tämän yhtä ja samaa rakennetta, mahdollisesti? Oikea? Tunnen me vain ratkaisi ongelma kuin viikko sitten. Mikä oli ratkaisu tähän ongelmaan että Steven törmäsi? Joten liittyvät luettelot, oikealle. 

Jos ongelma on se, että olemme maalaus itsemme nurkkaan kohdentamalla etukäteen liian vähän muistia, että sitten on jotenkin käsitellä, hyvin, miksi ei vain välttää antaa kokonaan? Miksi ei vain julistaa kaukaloiden osoitin solmuun, ergo linkitetty lista, ja sitten yksinkertaisesti jakaa uutta solmuja joka kerta Steven tarvitaan sopivaksi numeron tietorakenne. 

Joten kuva olisi muutettava. Se ei tule olemaan niin puhtaita ja yksinkertainen kuin vain joukko kolme ints. Nyt se tulee olemaan osoitin struct, ja että struct on menossa on int ja ensi osoitin. Se tulee johtamaan kautta, että osoitin toiselle tällaiselle struct on toinen tällainen struct. Joten kuva todella saada hieman Messier. Ja olisimme nuolet sitominen kaikki yhdessä. 

Mutta se on hieno, oikea, koska olemme nähneet, miten tämä. Ja kun saat mukavan täytäntöön jotain linkitetyn lista, joka sinun täytyy tehdä, jos päättää panna hash taulukon erillinen ketjutus p-sarja 6, voit käyttää sitä rakennuspalikka, tai ainesosa tai Scratch puhua, menettelyä, jotain, mitä laittaa, et luonut oman palapelin pala että voit käyttää uudelleen. Joten kompromissit, mutta mahdollisia ratkaisuja että olemme nähneet ennen. 

Niin usein, näet tämän joka vuosi tai kaksi, kun Apple julkaisee jotain uutta, ja kaikki hulluja ihmisiä riviin ulkopuolella Apple ostamaan marginaali päivittää laitteisto. Sanon tämän, se on OK, koska Olen yksi niistä ihmisistä. Millainen tietorakenne voisi edustaa tätä todellisuutta? 

No, kutsutaan sitä jono, rivi. Joten British kutsuisi sitä tyypillisesti jono joka tapauksessa, joten se on kiva nimi. Ja kaksi operaatiota, että jono tuetaan me kutsumme enqueue toiminta ja dequeue toimintaa, , jotka ovat samanlaisia henki työntää ja pop. Se on vain eräänlainen erilainen yleissopimus, mitä me soittaa näitä. Mutta laittaa jonoon jotain tarkoittaa lisätä tai aseta se tietorakennetta. Voit dequeue keino poistaa se. Mutta taas pino oli LIFO tiedot rakenne, jono on ensimmäinen, first out tietorakenne. 

Jos olet ensimmäinen henkilö linjassa, olet ensimmäinen henkilö saada ulos linja ja ostaa uusi laite. Kuvittele kuinka järkyttynyt nämä ihmiset olisivat jos Apple sen sijaan käytetään pino varten Esimerkiksi toteuttaa poiminta jopa oman uuden lelun. Joten jonot järkeä, varmasti ja voimme ajatella kaikenlaisia sovelluksia, oletettavasti, jonot, varsinkin kun haluat oikeudenmukaisuutta. Joten miten voisimme toteuttaa nämä sillä tietorakenne? 

No, ehdotan, että voisimme täytyy tehdä se tällä tavalla. Joten aion nyt numeroita. Joten me pitää se yksinkertainen ja ei välttämättä puhutaan lokeroihin. Vain numeroita että ihmiset mennyt. Kapasiteetti on menossa jälleen korjata henkilöiden määrä, jotka voivat olla tätä linjaa, sillä kolme tai mitä muita arvo. 

Mutta ehdotan, että minun täytyy seurata ei ainoastaan ​​koosta jono, kuinka monet asiat ovat siinä. Joten koko on nykyinen koko, kapasiteetti on enimmäiskoko. Vain kerran, nimikkeistö sopimuksen mukaan. Miksi tarvitsen lisää int sisällä jonon seurata kuka on rivin? Miksi minun pitää tehdä, että tässä tapauksessa? 

No, miten tämä kuva tulee muuttumaan? Voin ehkä uudelleen useimmat Kuvan. Anna minun mennä eteenpäin ja poistaa mitä on täällä. Annamme tässä hieman eri nimellä täällä. Mennään eroon 17 Mennään eroon ja 9, nyt päästä eroon 3. Ja antaa vielä yhden asian. Ehdotan, että minun täytyy seurata edessä lista, joka on vain olemaan int samoin. Ja me aiomme pitää asiat yksinkertaisina. Ei linkitetty lista nyt. 

Me myönnettävä, että aiomme kolahtaa vastaan ​​tämän rajan. Mutta mitä haluan nähdä tapahtuu tällä kertaa? Joten kai mennä eteenpäin ja ensimmäinen henkilö keksii linjassa, ja se on numero 9. Meillä on stressi pallot. Voinko varastaa, eli kaksi tai kolme ihmistä? Yksi, kaksi, kolme? Tule ylös. Oikea edestä, koska Tästä tehdään yksi nopea. 

Jokainen teistä on nyt olemaan tuuletin poika jonossa Apple. Et ehkä saa Applen laitteet lopussa tämän kuitenkin. Selvä. Joten olet numero 9, olet numero 17, numero 22. Nämä ovat mielivaltaisia ​​numeroita, kuten Opiskelija tunnukset tai vaikka mitä. Ja vain hetken, aloitetaan aloittaa lisäämällä asioita. Ja minä ajaa aluksella tässä tällä kertaa. 

Joten tässä tapauksessa, olen alustettu edessä on - Olen itse ei välitä, mitä edessä on, koska koko on nolla. Joten tämä saattoi aivan hyvin olla kysymysmerkki. Nämä kaikki ovat kysymysmerkkejä. Joten nyt alamme todella nähdä ihmiset riviin myymälässä. 

Joten jos numero 9, olet ensimmäinen siellä 5 AM, mennä eteenpäin ja riviin, tai iltana. OK. Joten nyt 9 on täällä. Joten 9 on edessä luettelosta. Joten aion mennä eteenpäin ja päivittää koko nykyisten tietojen rakennetta ei ole 0 enää, vaan olla 1. Aion laittaa 9 at edessä luettelosta. Anna minun mennä eteenpäin ja vaihtaa näytön jotta voimme nähdä ohitsemme täällä. 

Ja nyt, mitä haluan laittaa edessä? Aion seurata, että jonon nyt on paikalla 0. Sillä se, mitä seuraavaksi tapahtuu? No, kai nyt laittaa jonoon 17 samoin. Joten hop linjassa siellä. Ja vielä, eräänlainen oven myymälä tulee olemaan täällä. Joten nyt olen lisätty 17. Ja vaikka nämä kaverit ovat estämässä näyttö, se on OK, koska voimme nähdä sen täällä. Anteeksi. 

Yleisö: Voimme liikkua - 

DAVID MALAN: Ei, se on OK. Se on valtava siellä. Joten 17 on nyt sisä-jonon. Minun täytyy päivittää joka kentät nyt vaikka? OK, varmasti koko. Ja miten edessä? OK, no. Edessä ei pitäisi muuttaa, koska toisin kuin pinon, me haluavat säilyttää oikeudenmukaisuutta. Joten jos 9 tuli ensin, haluamme 9 olla ensimmäinen ulos linja ja myymälä. 

Itse asiassa, nyt nähdä, että. Ennen kuin voimme lisätä 22, nyt mennä eteenpäin ja dequeue 9. Mikä sinun nimesi olikaan? 

Yleisö: Jake. 

DAVID MALAN: Jake on menossa voidaan dequeued nyt. Joten saat kävellä kauppaan. Ja teeskennellä, että myymälä on tuolla. Joten nyt mitä tarvitsee - dit-dit-dit! Mitä täytyy tapahtua nyt? Suunnittelu päätös. Joten ei paha vaisto, mutta - Mikä sinun nimesi olikaan? 

Yleisö: David. 

DAVID MALAN: David. Mitäs David tehdä? Hän yritti tavallaan vahvistaa tiedot rakenne ja siirtyä hänen sijainnistaan osaksi Jake entinen sijainti. Ja se on hienoa, jos olemme valmiita hyväksyä, että täytäntöönpanon yksityiskohtia. Mutta ensin on päivittää tiedot rakenne ennen kuin teemme sen. Koska en ole mieltynyt ajatukseen kaikkien ihmiset siirtymässä tätä linjaa. 

Se ei ole iso juttu, jos David tekee sen yksi askel, mutta jälleen kerran, muistelen kun meillä on ollut kahdeksan vapaaehtoisille vaiheessa ja olemme tehneet kuten paikoilleen lajitella, jossa meidän piti aloittaa liikkuvat kaikki ympärillä. Se sai kallista, eikö? Se saa minut punastumaan noin iso O n, iso O n potenssiin uudelleen. Se ei ole tunne kuin Paras lopputulos. 

Joten haluan vain päivittää. Joten koko jonon ei ole enää 2. Nyt on yksinkertaisesti 1. Mutta voin nyt päivittää jotain En päivittänyt ennen, edessä luettelosta. Voisin sanoa, että paikka 1? Joten nyt meillä on roskaa arvo tähän, roskat arvo täällä, ja David Keskellä tätä roskaa. Mutta tietorakenne on ehjä. 

Ja itse asiassa, en edes tarvitse muuttaa Jaken entisen numeron 9, koska who cares. Minulla on tarpeeksi tietoa nyt koko, että tiedän siellä on yksi henkilö tähän jonoon. Ja tiedän, että kyseinen henkilö on paikassa 1, ei 0. En laskenta. Joten 1 samoin. Joten tietorakenne on vielä OK. 

No, mitä tapahtuu seuraavaksi? Katsotaanpa enqueue - Mikä sinun nimesi on? 

Yleisö: Callen. 

DAVID MALAN: Callen. Katsotaanpa laittaa jonoon Callen, ja 22 on nyt jonossa. Mitä nyt on muututtava täällä? Etu ei tule muuttaa, tietenkin. Koko on muuttumassa olla 2 uudelleen. Ja 22 päätyy tänne, 9 on edelleen läsnä, mutta se on tehokkaasti roskat arvo nyt. Se on vain jäänne Jake ohi. 

Joten nyt mitä tapahtuu, jos Olen dequeue David? Viimeinen toiminta, dequeue David. Voisimme siirtää, mutta ehdotan, katsotaanpa tehdä niin vähän työtä kuin mahdollista. Nyt tietoni rakenne menee takaisin kooltaan 2-1. Mutta jonon nyt tulee 2. Minun ei tarvitse muuttaa näitä numeroita vielä, koska he vain roskat arvot. 

Mutta mitä nyt tapahtuu? Kai laittaa jonoon itse, 26? Tunnen kuulun tänne. Joten Minua enqueued. Joten olen sellainen kuulu tänne. Ja vaikka et ole aivan Arvostan tätä visuaalisesti vaiheessa koska meillä on runsaasti tilaa, haluan ei seison tässä, miksi? 

Yleisö: Olet out of bounds. 

DAVID MALAN: Oikea. Olen out of bounds. Olen indeksoitu yli bounds tämän taulukon. En todellakaan pitäisi olla yksi kolme mahdollisia paikkoja. Nyt, missä on kaikkein luonnollisin mennä? Ehdotan velkarahalla viikolla yksi temppu. Mod operaattori prosenttiyksikköä. Koska olen teknisesti seisoo sijainti 3, mutta en 3 mod kapasiteettia, niin 3, prosenttimerkki, 3 - kapasiteetti on 3. Mikä tuo on? Mikä on jakojäännös, kun jaat 3 noin 3? 0. 

Niin että saa minut oli Jake oli, joka on todella hyvä. Joten nyt täytäntöönpanoa tämä asia tulee olla hieman päänsärkyä. Se on oikeastaan ​​vain yksi rivi päänsärky, koodia. Mutta ainakin nyt on roskaa arvo täällä, mutta siellä on kaksi laillista ints täällä. Ja väitän, että nyt olemme tehneet mitä meidän täytyy tehdä niin kauan kuin muutamme mitä Jaken arvo oli 26 jäsentä. 

Meillä on nyt tarpeeksi tietoa edelleen luotettavuuden säilyttämiseksi Tämän tietorakenteen. Olemme vielä sellainen pois onnea, kun olemme haluat lisätä vähintään neljä yhteensä elementtejä, mutta ainakin voin tehdä melko tehokas käyttö tämän jatkuvan aikaa, itse asiassa. En tarvitse murehtia siirtymässä kaikille, sillä Davidin kaltevuus oli. 

Kysyttävää pinoja, tai tähän jonoon? 

AUDIENCE: Onko miksi tarvitset kokoa niin tiedät missä on ihminen? 

DAVID MALAN: Aivan. Minun täytyy tietää koko joukko koska minun täytyy tietää tarkalleen, kuinka Monet näistä arvoista ovat oikeutettuja, ja niin, että voin löytää mihin seuraava henkilö. Täsmälleen. Koko on - Oikeastaan ​​emme päivittää tätä vielä. Lisäsin itseni 26. Koko on nyt, ei 1, mutta 2. Joten nyt tämä todellakin auttaa minua löytämään johtaja luettelon, joka ei ole 0, ei 1, mutta on 2. Edessä lista on todellakin numero 22. Koska hän tuli ensin, niin hän olisi päästetä varastoida ennen minua, vaikka visuaalisesti Seison lähempänä myymälän. 

Kaikki hyvin? Aplodit nämä kaverit ja annamme ne pois sieltä. 

[APPLAUSE] 

DAVID MALAN: antaisin pidät lokeroon. Voisimme nähdä, mitä tapahtuu, jos haluat, mutta ehkä ei. Selvä. Joten mitä nyt se jättää meidät? No, minäpä ehdottaa, että on olemassa muutamia muita tietorakenteita voisimme aloittaa lisäämällä meidän työkalusarja joka tulee itse asiassa olla melko, melko osuvia me sukeltaa web kamaa. Joka taas on jonkinlainen yhteys puita muodossa jotain kutsutaan DOM, asiakirja objektimalli. Mutta näemme enemmän että ennen pitkää. 

Sallikaa minun määritelmällisesti että kutsupuu mitä nyt ehkä tiedätte kuin enemmän sukupuun, jossa joitakin kantaisä on juuret puu. Patriarkaalinen tai matriarkka at hyvin puun latvaan. Ilman heidän puolisonsa, tässä tapauksessa. Mutta meillä on nyt, mitä me kutsumme lapset, jotka ovat solmuja, jotka roikkuvat pois vasen lapsi tai oikea lapsi, nuolet kuten kuvattu täällä. 

Toisin sanoen, kun puu tietorakenne tietokoneen, puu on nolla tai useampi solmu. Jos se on ainakin yksi solmu, sitä kutsutaan root. Se on asioita visuaalisesti että vedämme huipulla. Ja että solmu, kuten mikä tahansa muu solmu, voi on nolla, yksi tai kaksi tai kolme, tai miten monta lasta tietorakenne tukee. Tässä tapauksessa juuri, varastointi arvo yksi, on kaksi lasta, 2 ja 3, niin me yleensä soittaa 2 vasen lapsi ja 3 oikea lapsi. 

Ja sitten kun pääsemme 5, 6, ja 7, 6 voisi kutsua keskimmäinen lapsi. Jos sinulla on neljä lasta, se saa hämmentävä. Joten lopeta tuollainen pikakuvake sanallisesti. Mutta se on oikeastaan ​​vain sukupuun. Ja lehdet tässä ovat solmuja, jotka itse ei ole lapsia. Ne roikkuvat pois puun alaosaa. 

Joten miten voisimme toteuttaa puu, joka on vain kaksi lasta maksimaalisesti? Me kutsumme sitä binääripuu. Bi taas tarkoittaa kahta tässä tapauksessa, kuten binary. Ja niin se voi olla nolla, yksi, tai kaksi lasta maksimaalisesti. 

Minä ehdotan, että toteutamme solmu että rakenne int n, ja sitten kaksi osoitinta, yksi nimeltään vasemmalle, yksi nimeltään oikea. Mutta ne ovat vain mukavia mielivaltainen yleissopimukset. Ja mitä mukavaa nyt, varsinkin jos Tällainen kamppaillut käsitteellisesti rekursio, tai ajatellut, että se ei ollut todella ratkaisu mihinkään, varsinkin jos voisit muisti loppuu. Nyt puhumme tiedot rakenteita ja algoritmeja, jotka mahdollistavat meitä kulkemaan ja manipuloida niitä, Osoittautuu, että rekursiivisista tulee takaisin paljon pakottavia jos ei kauniilla tavalla. 

Joten tämä Ehdotan täytäntöönpano ja hakutoiminto. Koska kaksi tuloa - niin ajattele tätä musta laatikko. Koska kaksi tuloa, n, int, ja osoitin puu, osoitin solmu, tai oikeastaan ​​juuri puu, I väittävät, että tämä toiminto voi palauttaa totta vai tarua, että arvo n on sisällä tämän puun. 

Mitä sisällä tämä musta laatikko? No, neljä oksat. Ensimmäinen vain tarkistaa. Jos puu on null, vain palauttaa false. Jos ei ole solmu, ei ole n, ei ole numero, vain palauttaa false. Jos kuitenkin, n, arvo etsit varten, on pienempi kuin puu nuoli n ja vain olla selvää, mitä se tarkoittaa, kun Kirjoitan puu ja sitten nuoli merkintätapa, n? Täsmälleen. Se tarkoittaa dereference että osoitin kutsutaan puu. Mene sinne, ja sitten päästä sisälle, että solmu ja saada alansa Kutsutaan. Ja sitten verrata todellisia n, joka oli johdetaan Haku sitä vastaan. 

Joten jos n on pienempi kuin n-arvo puussa solmun itse, hyvin, mitä se tarkoittaa? Tämä tarkoittaa mitään ensi silmäyksellä. Oikea? Aivan kuten silloin, kun on joukko arvot, haluat ehkä soveltaa binary etsiä muotona kahtiajaon ja valloittaa. Mutta mitä oletus ei meidän tehdä binary haku toimi lainkaan puhelinluettelosta, ja Aiempia esimerkkejä? 

Miten voidaan lajitella. Joten tarkentaa määritelmää puu täällä ei olla vain puu, joka voi mitään määrän lapsia. Ei vain binääripuu, joka voi on 0, 1 tai 2 maksimaalisesti. Mutta binäärihakupuu tai BST, joka on vain hieno tapa sanoa binääripuussa siten, että jokaisen solmun vasen lapsi, jos on läsnä, on vähemmän kuin solmu. Ja jokainen solmun oikea lapsi, jos läsnä on suurempi kuin solmu itse. 

Eli toisin sanoen, jos olisit tehdä puu pois, kaikki numerot ovat tasapainoisia näin niin, että jos sinulla on 55 root, 33 voi mennä sen vasemmalla puolella, koska se on vähemmän kuin 55. 77 voi mennä sen oikein, koska se on suurempi kuin 55. Mutta nyt huomaa, samaa määritelmää, se on rekursiivinen määritelmä sanallisesti, on haettava 33. 33 vasemman Lapsen tulee olla alle sen, ja 33: n oikea lapsi, 44, on oltava suurempi kuin se. 

Joten tämä on binäärihakupuu, ja Ehdotan, käyttäen hieman rekursio, voimme nyt löytää n. Joten jos n on pienempi kuin arvo n, joka on nykyinen solmu, aion mennä eteenpäin ja ruuhi, niin sanotusti, ja vain palata riippumatta vastaus on etsivät n päälle puun vasen lapsi. Huomaa jälleen, tämä toiminto vain odottaa solmu tähden, osoitin solmuun. Niin varmasti voin vain tehdä puiden nuoli vasemmalle, mikä johtaa minut toiseen solmuun. Mutta mikä on se solmu? 

No, tämän julistuksen, vasemmalla on vain osoitin, niin että vain tarkoittaa olen ohimennen hakutoiminto eri osoitin, eli yksi, joka edustaa minun vasen lapsen puu. Joten tässä tapauksessa osoitin 33, jos Tämä on meidän näyte tulo Samaan aikaan, jos n on suurempi kuin arvo n on nykyinen solmu puussa, niin olen mene eteenpäin ja punt muiden suuntaan ja vain sanoa, en tietää, jos tämä arvo n on puu, mutta en tiedä, jos se on, se on alas minun oikea haara, niin sanoakseni. Joten Soitan rekursiivisesti etsiä, kulkee n uudelleen, mutta ohimennen osoitin minun oikea lapsi. 

Toisin sanoen, jos olen tällä hetkellä 55 ja etsin 99, tiedän, että 99 on suurempi kuin 55, joten aivan kuten Revin puhelinluettelosta viikkoa sitten ja me meni oikein, samoin me olemme menossa täällä. Ja en tiedä onko se minun oikealle lapsi, ja se ei ole, 77 on olemassa, mutta Tiedän, että se siihen suuntaan. Joten pyydän haku minun oikea lapsi, 77, ja anna hakuun luku ulos siellä jos 99 tämä mielivaltainen Esimerkiksi on todella olemassa. 

Muu, mikä on viimeinen asia? Jos puu on nolla on yksi tapaus. Jos n on pienempi kuin nykyisen solmun arvo on toinen asia. Jos n on suurempi kuin nykyinen solmun arvo on kolmas tapaus. Mikä on neljäs ja viimeinen asia? Luulen, että olemme pois tapauksissa, eikö? Sen täytyy olla, että n on nykyinen solmu, joka olen. 

Joten jos Etsin 55 tässä vaiheessa tarina, että haara puu palaisi totta. Niin mitä mielenkiintoista tässä on se, että me itse, toisin kuin viikkoa aiemmin, olemme eräänlainen ja kaksi pohja tapauksissa. Ja he eivät tarvitse olla kaikki huipulla. Alkuun on pohja tapauksessa, koska jos puu on null, ei ole mitään tekemistä. Vain palata kovakoodattu arvo false. 

Alahaaran on eräänlainen oletus, jonka mukaan jos olemme tarkastetaan null, olemme tarkastetaan, jos se olisi vasemmalle, mutta sen ei pitäisi olla, olemme tarkistetaan, jos se olisi oikea, mutta se ei pitäisi olla selvästi sen on oltava juuri siellä missä olemme. Se on pohja tapauksessa. Joten siellä kaksi rekursiivinen tapauksissa alumiinifoliota siellä keskellä. Mutta en voinut kirjoittaa Tässä missä tahansa järjestyksessä. Ajattelin vain se sellainen tuntui luontevalta ensin tarkistaa mahdollisen virheen, tarkista sitten vasemmalle, sitten tarkistaa oikealle, sitten olettaa, että olet solmussa olet todella etsivät. 

Joten miksi tämä voisi olla hyödyllistä? Joten se kääntyy pois - ja haluan hypätä teaser täällä se on verkossa. Aiomme alkaa käyttää ei ohjelmointikieli aluksi, mutta kuvauskieli. Kuvauskieli on yksi, joka on hengeltään samanlainen ohjelma kieli, mutta se ei anna kyky ilmaista itseäsi loogisesti. Se vain antaa sinulle mahdollisuuden ilmaista itseäsi rakenteellisesti. 

Minne haluat laittaa jotain sivulla, sivun? Mitä väriä haluat tehdä? Mitä fontin kokoa haluat tehdä? Mitä sanoja sinä itse haluavat www-sivulla? Niin, että kuvauskieli. Mutta sitten me nopeasti käyttöön JavaScript, joka on täysimittainen ohjelmointikieli. Hyvin samanlainen rakenteeltaan ulkonäöltään C, mutta se tulee olla kiva, tehokkaampia ja käyttäjäystävällisiä ominaisuuksia. 

Ja yksi turhautumisen tässä kohta lukukausi on, että me pian täytäntöön aapinen vuonna huomattavasti vähemmän riviä koodia muilla kielillä kuin C puolestaan ​​sallitaan, mutta syystä: n me pian ymmärtää. Tämä on ensimmäinen tällainen web-sivun. Se on täysin underwhelming, ensimmäinen teemme. Se yksinkertaisesti sanoa, hello world. Mutta jos et ole koskaan nähnyt ennen kuin tämä on HTML, Hypertext Markup Language. 

Jos menet tiettyjä valikon vaihtoehto Useimmissa tahansa selaimella, millä tahansa web-sivu Internetissä voit nähdä HTML että jotkut ihmiset kirjoitti luoda kyseisen sivun. Ja se luultavasti ei näytä yhtä lyhyt tai siisti kuin tämä. Mutta se seuraa mallia näistä avoin suluissa ja viiltää ja kirjaimia ja mahdollisesti numeroita. 

Ajattelin antaa teille teaser mitä voit tehdä ottamisen jälkeen CS50. Anna minun mennä cs.harvard.edu / ryöstää, oman Rob Bowden kotisivulla. Hän teki tämän meille. Joten voit pian olla mahdollisuus tehdä niin. Ja myös, mitä kuulit tänä aamuna - mitä tänä aamuna - 

[HAMSTER DANCE MUSIC] 

- You'll voi tehdä tätä. Joka meitä odottaa keskiviikkona. Me nähdään sitten. 

[HAMSTER DANCE MUSIC] DAVID MALAN: Seuraavassa CS50 -