SPEAKER 1: Okei, joten tämä on CS50 Tämä on viikon lopussa viisi. Ja muistaa, että viimeinen kerta alkoi tarkastella harrastaja tiedot rakenteiden alkoi ratkaista ongelmia, jotka alkoivat ottaa käyttöön uusia ongelmia, mutta avain tähän oli sellainen ketjuttaminen että me alkoi tehdä solmusta toiseen. Joten tämä on tietenkin yksittäin linkitetyn listan. Ja yksittäin liittyy, Siis siellä on vain yksi kierre jokaisen näistä solmuja. Osoittautuu voit tehdä harrastaja asioita, kuten kaksin verroin liittyvät luettelot jolloin sinulla nuoli menee molempiin suuntiin, joka voi auttaa tiettyjen tehokkuusetuja. Mutta tämä ratkaisi ongelman? Mikä ongelma ei tässä ratkaista? Miksi välitämme maanantaina? Miksi, teoriassa, ei välitämme maanantaina? Mitä se tekee? 

Yleisö: Voimme dynaamisesti muuttaa sen kokoa. 

SPEAKER 1: OK, joten voimme dynaamisesti muuttaa sen kokoa. Hyvin tehty molemmat. Joten voit dynaamisesti muuttaa tätä tietorakenne, kun taas array, Recall, sinun täytyy tietää priori kuinka paljon tilaa haluat ja jos tarvitset hieman enemmän tilaa, olet eräänlainen onnea. Sinun on luotava kokonaan uusi joukko. Sinun täytyy siirtää kaikki tietoja toisiinsa, lopulta vapauttaa vanha array jos voit, ja jatka sitten. Joka vain tuntuu erittäin kallista ja hyvin tehoton, ja se todellakin voi olla. Mutta tämä ei ole kaikki hyviä. Me maksamme hintaa, mikä oli yksi selvempi hintoja me maksaa käyttämällä linkitettyä listaa? 

Yleisö: Meidän on käytettävä kaksinkertainen tilaa jokaiselle. SPEAKER 1: Joo, joten tarvitsemme vähintään kaksi kertaa niin paljon tilaa. Itse tajusin tätä kuvaa n jopa hieman harhaanjohtava, koska on CS50 IDE paljon nykyaikaisen tietokoneet, osoitin tai osoite ei itse asiassa neljä tavua. Se on hyvin usein nämä päivää kahdeksan tavua, joka tarkoittaa alimmainen suorakulmioita siellä todellisuudessa ovat sellaisia ​​kaksi kertaa iso kuin mitä olen piirretään, mikä tarkoittaa käytät kolme kertaa paljon tilaa kuin meillä olisi muuten. Nyt samaan aikaan, olemme vielä puhuessaan tavua, eikö? Emme välttämättä puhu gigabitteinä, jollei näitä tietorakenteita saada iso. 

Ja niin tänään alkaa harkita miten voisimme tutkia tiedot tehokkaammin jos Itse asiassa tiedot suurenee. Mutta yritetään muunna toiminta ensimmäinen että voit tehdä näitä erilaisia ​​tietorakenteita. Joten jotain liittyy lista tukee yleisesti toimintoja, kuten poistaa, lisätä, ja etsi. Ja mitä minä tarkoitan, että? Se vain tarkoittaa, että yleensä, jos ihmiset käyttävät linkitetty lista, he tai joku muu on toteuttanut toimintoja, kuten poistaa, lisätä, ja haku, joten voit itse tehdä jotain hyödyllinen tietorakenne. Joten ottaa vilkaista miten voisimme toteuttaa Joissakin koodi linkitetyn listan seuraavasti. 

Joten tämä on vain joitakin C-koodia, ei edes täydellinen ohjelma että olen todella nopeasti lyöty jopa. Se ei ole verkossa jakelussa koodi, koska se ei todella ajaa. Mutta huomaa Olen juuri jossa kommentti sanoi, dot dot dot, on jotain siellä, piste piste piste, jotain siellä. Ja nyt vain katsoa mitä mehukas osat ovat. Niin linjalla kolme, muistuttaa, että tämä on nyt ehdotimme julistamisesta solmu viime aika, yksi niistä suorakulmainen esineitä. Se on int että soitamme N, mutta voisimme kutsua sitä jotain, ja sitten struct solmu tähti sanottujen seuraavan. Ja vain tehdä selväksi, että toinen linja, rivillä kuusi, mikä se on? Mitä se tekee meille? Koska se varmasti näyttää enemmän arvoituksellinen kuin tavallisia muuttujia. 

Yleisö: Se tekee siirtyä yksi. 

SPEAKER 1: Se tekee sen liikkua yli. Ja tarkemmin sanottuna, se tallentaa osoite solmun, joka on tarkoitus olla semanttisesti sen vieressä, eikö? Joten se ei tule välttämättä siirrä mitään. Se on vain menossa tallentaa arvon, joka on olemaan osoitteeseen joidenkin muiden solmun, ja siksi olemme sanoneet struct solmu tähti, tähti ilmaiseva osoitin tai osoite. OK, joten nyt jos oletetaan, että meillä on tämä N käytettävissämme, ja nyt olettaa, että joku muu on Lisätään koko joukko kokonaislukuja osaksi linkitetty lista. Ja että linkitetty lista on osoitteen sivulle jossain vaiheessa muuttuja nimeltä lista, joka on hyväksyttiin täällä parametri, miten voin mennä noin linja 14 täytäntöönpanosta haku? Toisin sanoen, jos olen täytäntöönpanosta jonka tehtävänä elämässä on otettava int ja sitten alussa linkitetty lista, että on osoitin linkitetyn listan. Kuten ensimmäinen, joka mielestäni David oli meidän vapaaehtoinen maanantaina, hän oli suunnattu koko linkitetty lista, se on ikään kuin me ohimennen David meidän argumentti täällä. Miten edetä liikkumisesta tämä lista? No, käy ilmi, että vaikka osoittimet ovat suhteellisen uusi nyt meille, voimme tehdä tämän suhteellisen mutkattomasti. 

Aion mennä eteenpäin ja julistaa väliaikainen muuttuja, joka sovitun käytännön on juuri menossa kutsua osoitin, tai PTR, mutta voit kutsua sitä mitä haluat. Ja aion alustaa sen alkua luettelon. Voit siis sellaista ajatella tämän kuten minulle opettaja toinen päivä, sellainen suunnattu joku keskuudessa ihmisten vapaaehtoisina. Joten olen väliaikainen muuttuja, joka on vain suunnattu sama asia että sattumalta nimetty vapaaehtoinen David oli myös muistuttaa. Nyt kun osoitin on ei null, koska muistaa että null on joitakin erityisiä Sentinel arvo rajataan listan loppuun, joten vaikka en ole suunnattu maahan kuin meidän viime vapaaehtoisten oli, mennään eteenpäin ja toimi seuraavasti. Jos pointer-- ja nyt olen sellainen haluavat tehdä, mitä teimme opiskelija structure-- jos osoitin piste seuraava equals-- pikemminkin, jos osoitin piste n on on yhtä suuri kuin muuttuja N, väite joka on ohitettu, sitten haluan mennä eteenpäin ja sano palata totta. Olen löytänyt lukumäärä N sisäpuoli yksi solmuista minun linkitetyn listan. Mutta piste ei enää toimii tässä yhteydessä, koska osoitin, PTR, on todellakin osoitin, osoite, me oikeastaan ​​voi ihanan käyttää lopulta pala syntaksin sellainen merkkeihin intuitiivinen tunne ja todella Käytä nuoli täällä, mikä tarkoittaa menevät että osoite kokonaisluku siellä. Joten se on hyvin samankaltainen henki piste operaattori, mutta koska osoitin ei ole osoitin eikä varsinaista struct itse, me vain nuolinäppäimillä. 

Joten jos nykyinen solmu, että minä, väliaikainen muuttuja, olen osoittaen ei ole N, mitä haluan tehdä? No, minun ihmisen vapaaehtoisten että meillä oli täällä toinen päivä, jos ensimmäinen ihmisen ei ole minun haluavat, ja ehkä toinen ihmisen ei ole yksi haluan, ja kolmanneksi, I täytyy pitää fyysisesti liikkuvat. Kuten miten voin selata lista? Kun meillä oli jono, te vain teimme kuten minä plus plus. Mutta tässä tapauksessa riittää, kun do osoitin, saa, osoitin, seuraavaksi. Toisin sanoen, seuraavan kentän on kuin kaikki jäljellä käsissä että meidän vapaaehtoisille ihmisille maanantaina käyttivät pisteeseen joitakin muita solmuun. Ne olivat seuraavaa naapureita. 

Joten jos haluan selata tähän luetteloon, En voi vain tehdä minä plus plus enää, Olen sen sijaan on sanottava Minä, osoitin, on menossa yhtä suureksi riippumatta seuraavaan kenttään on, seuraava kenttä, seuraava kenttä on, seuraavat kaikki nämä jäljellä käsissä että meillä oli lavalla osoittelee Joidenkin myöhemmin arvoja. Ja jos saan läpi että koko iteraation ja lopuksi, osuin null, joilla ei ole löytyi N vielä, minä vain return false. Joten jälleen, kaikki että teemme täällä, kohti kuvan hetki sitten, alkaa osoittamalla luettelon alussa oletettavasti. Ja sitten voin tarkistaa, on arvo Etsin yhtä yhdeksän? Jos näin on, palaan totta ja olen valmis. Jos ei, voin päivittää käsi, AKA osoitin, kohtaan seuraavassa nuolen sijainti, ja niin seuraava nuolen sijainti, ja seuraava. Olen yksinkertaisesti kävelemällä tämän taulukon. 

Joten jälleen, who cares? Kuten mitä on tämä ainesosa? No, muistuttaa, että otimme käyttöön käsite pino, joka on abstrakti tietotyyppi sikäli kuin se on ei C asia, se ei ole CS50 asia, se abstrakti ajatus, tämä ajatus pinoaminen asiat päällekkäin toistensa että voidaan toteuttaa rypäleterttuja eri tavoin. Ja yksi tapa ehdotimme oli kanssa array, tai linkitetty lista. Ja käy ilmi, että kanonisesti, pino tukee ainakin kaksi operaatiota. Ja sirinä sanat ovat push, että työntää jotain pinoon, kuten uusi lokero ruokasalissa, tai pop, mikä tarkoittaa poistaa ylimmän lokero pinosta dining sali, ja sitten ehkä joitakin muut toiminnot samoin. Miten me voimme määritellä rakenne että olemme nyt soittaa pino? 

No, meillä on kaikki tarvittavat syntaksi käytössämme C. sanon, antaa minulle eräänlainen määritelmä struct sisällä pino, Aion sanoa on joukko, on koko joukko numeroita ja sitten koko. Eli toisin sanoen, jos haluan toteuttaa tämän koodin, anna minun mennä ja juuri sellainen piirtää mitä tämä sanoo. Joten tämä sanoo, anna minulle rakenne, joka sai array, ja en tiedä mitä kapasiteetti on, se on ilmeisesti joitakin vakio, että olen määritelty muualla, ja se käy hyvin. Mutta kai se on vain yksi, kaksi, kolme, neljä, viisi. Joten kapasiteetti on 5. Tämä elementti sisällä minun rakenne kutsutaan numerot. Ja sitten tarvitsen yksi muut muuttuvat ilmeisesti nimeltään koko että aluksi aion säätää alustetaan nollaksi. Jos ei mitään pino, koko on nolla, ja se on roskaa arvot numeroina. Minulla ei ole aavistustakaan mitä siellä vielä. 

Joten jos haluan ajaa jotain pinoon, kai soittaa toiminto push, ja Sanon push 50, kuten numero 50, jossa ehdottaisitte Piirsin sitä tässä array? On viisi eri vastausvaihtoehtoa. Missä haluat ajaa numero 50? Jos tavoitteena täällä, taas, soita toiminto push, kulkea argumentti 50, jossa voin laittaa sen? Viisi possible-- 20% mahdollisuus arvaamaan oikein. Kyllä? 

Yleisö: Äärimmäisenä oikealla. 

SPEAKER 1: Äärimmäisenä oikealla. Nyt 25% mahdollisuus arvaamaan oikein. Jotta olisi todella hienoa. Sovitun käytännön sanon jossa joukko, olisimme yleensä alkaa vasemmalla, mutta voisimme varmasti alkavat oikeaan. Joten spoileri tässä olisi olen luultavasti piirtää sen vasemmalla, aivan kuten normaalissa array jossa I alkaa menee vasemmalta oikealle. Mutta jos voit kääntää aritmeettinen, hieno. Se vain ei ole tavanomaista. OK, minun täytyy tehdä yksi lisää muutos kuitenkin. Nyt kun olen ajanut jotain pinoon, mitä seuraavaksi? 

Okei, minun täytyy kasvattaa koko. Joten anna minun mennä eteenpäin ja vain päivittää tämän, joka oli nolla. Ja sen sijaan nyt, aion laittaa arvon yksi. Ja nyt kai työntää toisen numero pinoon, kuten 51. No, minun täytyy tehdä yksi muutos, joka on jopa koko kaksi. Ja sitten kai raivata lisää numero pinoon kuten 61, nyt minun täytyy päivittää koko yksi aika, ja saada arvo 3, kun koko. Ja nyt kai soittaa pop. Nyt pop Sopimuksen mukaan ei anneta argumentteja. Pino, koko kohta lokeron metafora on, että sinulla ei ole harkintavaltaa mennä saada, että tarjotin, kaikki mitä voi tehdä on pop ylin yksi pino, vain siksi. Sitähän tämä tietorakenne ei. 

Joten että logiikka jos minä sanoa pop, mikä irtoaa? Niin 61. Joten mitä todella on tietokone aikoo tehdä muistiin? Mitä minun koodi on tehtävä? Mitä ehdottaisitte muutamme ruudulla? Mitä pitäisi muuttaa? Anteeksi? Joten pääsemme eroon 61. Joten en voi varmasti tehdä sen. Ja voin päästä eroon 61. Ja sitten mitä muut muutos täytyy tapahtua? Koko luultavasti on palattava kaksi. Ja niin se on hieno. Mutta hetkinen, koko hetki sitten oli kolme. Haluan vain tehdä nopeasti järki tarkistaa. Kuinka me tiedämme, että me halusi päästä eroon 61? Koska olemme popping. Ja niin minulla on tämä toinen ominaisuus koko. 

Hetkinen, olen Muistelen viikko kaksi kun aloimme puhua taulukot, jossa tämä oli paikka nolla, tämä oli paikalla yksi, tämä oli paikka kaksi, tämä on paikka kolme, neljä, se näyttää suhde koko ja elementti, että haluan poistaa alkaen array näyttää vain olla mitä? Koko miinus yksi. Ja jotta Näin ihmisinä Tiedämme 61 tulee ensin. Miten tietokone menee tietää? Kun koodi, jossa luultavasti haluavat tehdä koko miinus yksi, joten kolme miinus yksi on kaksi, ja että tarkoittaa, että haluamme päästä eroon 61. Ja sitten voimme todellakin päivittää kokoa niin, että koko nyt menee kolmesta vain kaksi. Ja vain olla pikkutarkka, aion ehdottaa, että olen valmis, eikö? Ehdotitte intuitiivisesti oikein minun pitäisi päästä eroon 61. Mutta ei ole Olen sellainen tavallaan päässyt eroon 61? Olen tehokkaasti unohtanut että se on itse siellä. Ja muistelen PSET4, jos olet lukenut artikkeli Forensics, PDF että meillä oli te lukea, tai et lukee tällä viikolla PSET4. Muista, että tämä on todella germane koko ajatus tietokone oikeus. Mikä tietokone yleensä tekee, on se vain unohtaa missä jotain on, mutta se ei mene sisään ja kuten yrittää raapia sitä tai ohitus ne bitit nollia ja ykkösiä tai jokin muu satunnainen kuvio ellet itse niin tarkoituksella. Joten intuitio oli oikea, nyt päästä eroon 61. Todellisuudessa emme tarvitse vaivautua. Meidän täytyy vain unohtaa, että se on siellä muuttamalla koko. 

Nyt on ongelma tämän pinon. Jos minun pitää ajaa asioita pinoon, mitä ilmeisesti tule tapahtumaan vain hetken aikaa? Aiomme tila loppuu. Ja mitä me teemme? Olemme tavallaan ruuvattu. Tämä täytäntöönpano ei anna meille kokoa array, koska käyttämällä tämä syntaksi, jos muistelen viikolla kaksi, kun olet julistanut koko joukko, emme ole nähneet mekanismia vielä jossa voit muuttaa taulukon koko. Ja todellakin C ei ole kyseistä ominaisuutta. Jos sanot antaa minulle viisi Nths, soita heille numerot, siinä kaikki aiot saada se. Joten teemme nyt maanantaina, ovat kykyä ilmaista ratkaisu kuitenkin, meidän täytyy vain nipistää määritelmä meidän pinon jotta ei olla joitakin kovakoodattuja array, mutta vain tallentaa osoite. 

Nyt miksi tämä on? Nyt meidän täytyy vain olla tyytyväinen että kun minun ohjelma toimii, Olen luultavasti menossa on kysyttävä ihmisen, kuinka monta numeroa haluat tallentaa? Joten panos on tultava jostain. Mutta kun tiedän, että numero, niin voin vain käyttää mitä toimia antaa minulle kimpale muistia? Voin käyttää malloc. Ja voin sanoa minkä tahansa määrän tavua Haluan takaisin näiden Nths. Ja kaikki minun täytyy tallentaa numerot vaihteleva täällä sisällä tämän struct olisi mitä? Mitä todella menee numeroita tässä tilanteessa? Niin, osoitin ensimmäiseen tavu että kimpale muistia, tai tarkemmin, osoite Ensimmäisen näistä tavua. Ei ole väliä, jos se on yksi tavu tai miljardi tavua, Minun täytyy vain välitä ensin. Koska mitä malloc takuut ja käyttöjärjestelmää takeita, on että kimpale muisti I saada, se tulee olla vierekkäisiä. Siellä ei tule olemaan aukkoja. Joten jos olen pyytänyt 50 tavua tai 1000 tavua, he kaikki olemaan takaisin takaisin takaisin. Ja niin kauan kuin muistan, kuinka suuri, kuinka paljon pyysin, kaikki mitä tarvitsee tietää on ensimmäinen osoite. 

Joten nyt meillä on kyky koodi. Vaikkakin, se vie meitä enemmän aikaa kirjoittaa tämän ylös, voisimme nyt kohdentaa että muistia vain tallentamalla toinen osoite siellä jos haluamme isompi tai jopa pienempi kimpale muistia. Joten tässä on kaupan pois. Nyt saamme dynaamisuutta. Meillä on vielä contiguousness Olen väittäen. Koska malloc antaa meille vierekkäisiä kimpale muistia. Mutta tämä tulee olemaan kipua kaula meille, ohjelmoija, todella koodia ylös. Se on vain enemmän työtä. Meidän koodi sukua mitä olin paukutti ulos vain hetki sitten. Hyvin toteutettavissa, mutta se lisää monimutkaisuutta. Ja niin kehittäjä aikaa, ohjelmoija aika on vielä toinen resurssi että saatamme tarvita viettää jonkin aikaa saada uusia ominaisuuksia. Ja sitten tietysti on jono. Emme aio mennä tätä yksi yksityiskohtaisesti. Mutta se on hyvin samanlainen hengessä. Voisin toteuttaa jono, ja sen vastaava toiminta, enqueue tai dequeue, kuten lisätä tai poistaa, se on vain harrastaja tapa sanoa se, enqueue tai dequeue, seuraavasti. Voin vain antaa itselleni struct että jälleen on useita: n array, että jälleen on kooltaan, mutta miksi minun täytyy nyt seurata edessä jonossa? En tarvitse tietää edessä minun pinon. No, jos minä vielä kerran queue-- Haluan vain kovaa koodi sen olevan kuin viisi kokonaislukuja täällä mahdollisesti. Joten tämä on nolla, yksi, kaksi, kolme, neljä. Tämä tulee olemaan valitut numerot uudelleen. Ja tämä kutsutaan koko. 

Miksi se ei riitä on vain koko? No, työnnä nuo samat numerot. Joten en pushed-- I enqueued, tai työntää. Nyt olen laittaa jonoon 50, ja sitten 51, ja sitten 61, ja piste piste piste. Niin, että enqueue. I enqueued 50, sitten 51, sitten 61. Ja joka näyttää identtinen pinoon toistaiseksi paitsi en täytyy tehdä yksi muutos. Minun täytyy päivittää tämän koon, joten menen nollasta yhteen kolmelle nyt. Miten dequeue? Mitä tapahtuu dequeue? Kenen pitäisi tulla pois tästä luettelosta jos se linja Apple Storessa? Niin 50. Joten se on eräänlainen hankalampi tällä kertaa. Ottaa huomioon, että viime kerralla se oli super helppoa vain tehdä koko miinus yksi, Saan loppuun minun array tehokkaasti jos numerot ovat, se poistaa 61. Mutta en halua poistaa 61. Haluan ottaa 50, joka oli siellä 05:00 riviin uusi iPhone tai vaikka mitä. Ja niin päästä eroon 50, I voi vain tehdä tämän, eikö? Voin yliviivata 50. Mutta me vain sanoimme ei tarvitse olla niin anaali kuten raapia pois tai piilottaa tiedot. Voimme vain unohtaa missä se on. 

Mutta jos muutan kokoa nyt kaksi, on tämä riittävät tiedot tietää mitä minun jonossa? Ei oikeastaan. Mun koko on kaksi, mutta mistä jono alkaa, varsinkin jos minulla on vielä nämä samat numerot muistiin. 50, 51, 61. Joten minun täytyy muistaa nyt kun edessä on. Ja niin kuin ehdotin ylös siellä, me juuri nimeltään Nnen edessä, jonka ensimmäinen arvo olisi pitänyt mitä? Nolla, vain listan alkuun. Mutta nyt lisäksi decrementing koko, me vain increment edessä. Nyt täällä on toinen ongelma. Joten kun olen pitää käynnissä. Oletetaan tämä on määrä kuten 121, 124, ja sitten, perkele, Olen pois tilaa. Mutta hetkinen, en ole. Joten tässä vaiheessa tarinan, Oletetaan, että koko on yksi, kaksi, kolme, neljä, joten oletetaan, että koko on neljä, edessä on yksi, joten 51 on edessä. Haluan esittää toisen numeron täällä, mutta, Hemmetti, olen pois tilaa. Mutta en ole oikeastaan, eikö? Missä voisin laittaa lisäarvoa, kuten 171? Joo, voisin vain sellainen palata tuonne, eikö? Ja sitten yliviivaa 50, tai vain korvata se 171. Ja jos mietit miksi meidän numerot sai niin satunnainen, nämä ovat yleisesti otettu tietokone opiskelemaan Harvardin jälkeen CS50. Mutta se oli hyvä optimointi, koska nyt en tuhlaa tilaa. Minulla on vielä muistaa kuinka suuri tämä asia on yhteensä. Se on viisi yhteensä. Koska en halua Aloita korvaa 51. Joten nyt olen edelleen loppui, joten sama ongelma kuin ennen. Mutta voit nähdä, kuinka nyt koodissa, luultavasti täytyy kirjoittaa hieman monimutkaisuus tehdä tämän tapahtua. Ja itse asiassa, mitä operaattori C luultavasti avulla te maagisesti tehdä tämän kierron? Joo modulo operaattori, prosenttimerkki. Niin mitä eräänlainen jäähtyä noin jono, vaikka pidämme piirustus taulukot koska nämä kuten suoria viivoja, jos sellaista ajattele tätä kaartuvat ympärillä kuin ympyrän, sitten vain intuitiivisesti se tavallaan toimii henkisesti Mielestäni hieman siististi. Sinun olisi vielä toteuttaa että henkinen malli koodi. Joten ei ole niin kova, lopulta, toteuttaa, mutta me silti menettää size-- pikemminkin, kyky muuttaa, ellemme tee tätä. 

Meidän täytyy päästä eroon array, me korvata sen yhdellä osoitin, ja sitten jossain minun koodi Minulla soittaa mitä toimia itse luoda array soittanut? Malloc, tai vastaavalla toiminto, tarkalleen. Kysyttävää pinot tai jonoja. Joo? Hyvä kysymys. Mitä modulo käyttäisit täällä. Joten yleensä, kun käytät mod, voisitte tehdä sen koon koko tietorakenne. Joten jotain viisi tai kapasiteettia, jos se on vakio, on todennäköisesti mukana. Mutta juuri tekemässä modulo viisi luultavasti ei ole riittävä, koska meidän on tiedettävä me kääri täällä tai täällä tai täällä. Joten olet luultavasti myös menossa haluavat ottaa koko juttu, tai edessä muuttujaan. Joten se on vain tämän suhteellisen yksinkertainen aritmeettinen lauseke, mutta modulo on olennainen ainesosa. 

Joten lyhytelokuva jos tahtoa. Animaatio, että jotkut ihmiset muussa yliopistossa koota että olemme sovitettu tähän keskusteluun. Siihen liittyy Jack oppiminen faktoja jonoja ja tilastot. 

FILM: Olipa kerran, siellä oli mies nimeltä Jack. Kun se tuli ystävien, Jack ei ollut taito. Joten Jack meni puhumaan suosituin kaveri hän tiesi. Hän meni Lou ja kysyi, mitä teen? Lou näki, että hänen ystävänsä oli todella ahdistunut. No, hän alkoi, vain katso miten olet pukeutunut. Eikö sinulla ole mitään vaatteita jossa eri ulkoasua? Kyllä, sanoi Jack. Olen varma tehdä. Tulla kotiini ja Näytän ne teille. Niin he menivät pois Jackin. Ja Jack osoitti Lou laatikko jossa hän piti kaikki hänen paitoja, ja hänen housut, ja hänen sukat. Lou sanoi, Näen sinut on kaikki vaatteet kasaan. Miksi et käyttää joitakin toiset silloin tällöin? 

Jack sanoi, hyvin, kun riisu vaatteita ja sukat, Pesen ne ja laittaa ne pois ruutuun. Sitten tulee seuraava aamulla, ja jopa minä hop. Menen ruutuun ja saada vaatteeni päältä. Lou nopeasti tajusi ongelma Jack. Hän piti vaatteita, CD, ja kirjoja pino. Kun hän pääsi varten jotain lukea tai käyttää, hän oli valita alkuun kirjan tai alusvaatteet. Sitten kun hän oli tehnyt, hän olisi laittaa se takaisin. Takaisin se menisi päälle pinon. Tiedän ratkaisu, sanoi voittoisa Loud. Sinun täytyy oppia alkaa käyttää jono. Lou otti Jackin vaatteita ja ripustaa ne kaappiin. Ja kun hän oli tyhjentänyt laatikko, hän vain heitti sen. 

Sitten hän sanoi, nyt Jack, lopussa päivä, laittaa vaatteet vasemmalla kun laitat ne pois. Sitten huomisaamuna, kun katso auringonpaiste, saat vaatteet oikealla, lopusta linjan. Etkö näe? sanoi Lou. Se on niin mukavaa. Sinun käyttää kaiken kerran ennen käytät jotain kahdesti. Ja kaiken jonoissa hänen vaatekaappi ja hylly, Jack alkoi tuntua melko varma itsestään. Kaikki kiitos Lou ja hänen ihana jono. SPEAKER 1: Okei, se on ihana. Joten mitä on todella tapahtuu on alla huppu nyt? Että meillä on osoittimet, että meillä on malloc, että meillä on kyky luoda paloina muisti itsellemme dynaamisesti. Joten tämä on kuva me vilaukselta juuri muutama päivä. Emme todellakaan asu sitä, mutta tämä kuva on jatkunut alla huppu viikkoja nyt. Ja niin tämä merkitsee, vain suorakulmio että olemme laadittu, tietokoneen muistiin. Ja ehkä tietokone, tai CS50 ID, on gigatavu muistia tai RAM tai kaksi gigatavua tai neljä. Se ei ole oikeastaan ​​väliä. Käyttöjärjestelmä Windows tai Mac OS tai Linux, olennaisesti mahdollistaa ohjelman ajatella, että sillä on mahdollisuus sitten kaikkiin tietokoneen muistiin, vaikka saatat olla käynnissä useita ohjelmia kerralla. Joten todellisuudessa, että ei oikein toimi. Mutta se on eräänlainen illuusio annetaan kaikki ohjelmat. Joten jos sinulla on ollut kaksi keikkaa muistia, tämä on miten tietokone voisi ajatella sitä. 

Nyt sattumalta, yksi näistä asioita, yksi näistä segmenteistä muistia, kutsutaan pinon. Ja todellakin tahansa toistaiseksi kirjallisesti koodi että olet soittanut toiminto, esimerkiksi tärkein. Muista, että aina olen drawn tietokoneen muistiin, Olen aina piirtää tavallaan puolet suorakulmion täällä ja älä välitä puhua siitä, mitä edellä. Koska kun tärkein on nimeltään, minä väittävät että saat tämän suikale muistia että menee alas täällä. Ja jos tärkein kutsui toiminto kuten swap, hyvin swap menee täällä. Ja se kääntyy pois, se on jos se päätyy. Jotain kutsutaan pino sisällä tietokoneen muistiin. Nyt lopussa päivä, tämä on vain korjaa. Se on kuin tavu nolla, tavu yksi, tavu 2000000000. Mutta jos ajattelee sitä koska tämä suorakulmainen esine, kaikki teemme joka aika kutsumme toiminto on kerrospukeutuminen uusi siivu muistia. Annamme tämän tehtävän viipale sen omaa muistia työskennellä. 

Ja muistuttaa nyt, että tämä on tärkeää. Koska jos meillä on jotain swap ja kaksi paikallista muuttujaa kuten A ja B ja muutamme nuo arvot yhdestä ja kahdesta kaksi ja yksi, Recall että kun swap palaa, se on ikään kuin tämä siivu muistia on juuri mennyt. Todellisuudessa se on edelleen siellä forensically. Ja jotain on vielä todella siellä. Mutta käsitteellisesti, se on niin vaikka se on täysin poissa. Ja niin tärkein ei tiedä mitään työtä että tehtiin että swap-toiminto, ellei se on todella kulunut kyseisissä perustelut osoitin tai viittaamalla. Nyt, perusratkaisua tähän ongelmaan swap kulkee asiat osoitteen. Mutta näyttää siltä, ​​liian, mitä jatkunut edellä, että osa suorakulmion koko ajan on mutta siellä on enemmän muistia siellä. Ja kun dynaamisesti varata muistia, onko se sisällä GetString, joka olemme tehneet sinulle CS50 kirjasto, tai jos te soittaa malloc ja kysyä käyttöjärjestelmä kimpale muistia, se ei tule pinosta. Se tulee toisesta paikasta tietokoneen muistiin että kutsutaan kasaan. Ja se ei ole mitään erilaista. Se on sama RAM. Se on sama muisti. Se on vain RAM on jopa siellä sijaan täällä. 

Ja niin mitä se tarkoittaa? No, jos tietokoneessa on rajallinen määrä muistia ja pino on kasvamassa, joten puhua, ja kasan mukaan Tämän nuoli, kasvaa alaspäin. Toisin sanoen, jokainen kun soitat malloc, olet annetaan viipale muistia ylhäältä, niin ehkä hieman pienempi, sitten hieman alempi, aina soittaa malloc, kasaan, se käyttö, on eräänlainen kasvaa, kasvaa lähemmäs mitä? Pino. Joten tämä kuulostaa hyvä idea? Tarkoitan, jos se ei ole kovin selkeä mitä muuta voit tehdä, jos vain on rajallinen määrä muistia. Mutta tämä on varmasti huono. Nämä kaksi nuolet ovat tehokurssi toisiaan. 

Ja käy ilmi, että huono kaveri, ihmiset, jotka ovat erityisen hyvä ohjelma, ja yrittää murtautua tietokoneisiin, voi hyödyntää tätä todellisuutta. Itse asiassa, nyt harkita pieni pätkä. Joten tämä on esimerkki voit lukea noin tarkemmin Wikipediassa. Me kohta sinua artikkeli jos utelias. Mutta on hyökkäys yleisesti tunnettu puskurin ylivuoto että on olemassa niin kauan kuin ihmisillä on ollut kyky manipuloida tietokoneen muistiin, erityisesti C. Joten tämä on hyvin mielivaltainen ohjelma, mutta katsotaanpa lukea se alhaalta ylöspäin. Tärkeimmät osaksi argc merkkiä tähden argv. Joten se on ohjelma, joka ottaa komentoriviargumentteja. Ja kaikki tärkeimmät ei ilmeisesti on puhelu toiminto, kutsuvat sitä F yksinkertaisuuden. Ja se kulkee mitä? Argv yhden. Joten se kulkee F riippumatta sana on, että käyttäjä kirjoittanut kehoitteessa jälkeen Ohjelman nimi ollenkaan. Niin paljon kuin Caesar tai Vigenere, joka saatat muistaa teet argv. 

Joten mikä on F? F ottaa merkkijono ainoana väitteen, AKA char tähti, sama asia, kuten merkkijono. Ja sitä kutsutaan mielivaltaisesti baari tässä esimerkissä. Ja sitten char C 12, vain maallikon termein, mikä on char c kiinnike 12 tekee meille? Mitä se tekee? Varaaminen muisti, erityisesti 12 tavua 12 merkkiä. Aivan. Ja sitten viimeinen rivi, sekoita ja kopio, olet todennäköisesti ole nähnyt. Tämä on merkkijono kopio jonka tehtävänä elämässä on kopioida sen toiseen väitteeseen osaksi sen ensimmäinen väite, mutta vain tietty määrä tavua. Joten kolmas väite sanoo, kuinka monta tavua pitäisi kuuletko? Pituus baari, mitä käyttäjä kirjoitettu. Ja sisältö baari, että jono, ovat kopioitu muistiin osoitti at C 

Joten tämä näyttää typerää, ja se on. Se on keinotekoinen esimerkki, mutta se on edustava luokan hyökkäys vektoreita, tapa hyökätä ohjelman. Kaikki on hieno ja hyvä, jos käyttäjä nimikkeet sana, joka on 11 merkkiä tai vähemmän, sekä kenoviiva nolla. Entä jos käyttäjä on yli 11 tai 12 tai 20 tai 50 merkkiä? Mikä tämä ohjelma aikoo tehdä? Mahdollisesti seg vika. Se menee sokeasti kopioida kaiken bar ylös sen pituus, joka on kirjaimellisesti kaiken baari, osoiteriville osoitti C. Mutta C on vain ennaltaehkäisevästi annettu 12 tavua. Mutta ei ole ylimääräistä tarkistaa. Ei ole, jos olosuhteet. Ei ole virhe tarkkailun täällä. 

Ja niin mitä tämä ohjelma on aikoo tehdä, on vain sokeasti kopioida yksi asia toiseen. Joten jos me tehdä tätä kuten kuva, tässä vain suikale muistia. Niin huomaa alareunassa, me on paikallinen muuttuja baarissa. Niin että osoitin että menee store-- pikemminkin, että paikalliset väite, jonka on menossa tallentaa merkkijonon bar. Ja sitten huomaa vain sen yläpuolella pino, koska aina kun kysyä muisti pinoon, se menee vähän yläpuolella kuvallisesti, ilmoittaa, että meillä 12 tavua siellä. Ylhäällä vasemmalla yksi on C kiinnike nolla ja Alhaalla oikealla yksi on C kiinnike 11. Se on vain miten tietokoneet menossa antaa se pois. Joten intuitiivisesti, jos baari on enemmän kuin 12 merkkiä yhteensä, mukaan lukien kenoviiva nolla, jossa on 12 tai C kannatin 12 menossa? Tai pikemminkin jossa on 12 merkin tai 13 merkin, sadasosa merkki menossa päätyä kuvan? Yli tai alle? 

Oikea, sillä vaikka pino itse kasvaa ylöspäin, kun olet laittaa tavaraa se, se rakennesyistä, tuo muisti ylhäältä alas. Joten jos sinulla enemmän kuin 12 tavua, aiot alkaa korvata bar. Nyt se on vika, mutta se on ei oikeastaan ​​iso juttu. Mutta se on iso juttu, koska siellä lisää juttuja muistissa. Joten tässä miten voisimme laittaa Hei, olla selvillä. Jos olen kirjoittanut Hei kehoitteeseen. H-E-L-L-O kenoviiva nolla, päätyy sisällä ne 12 tavua, ja olemme erittäin turvallinen. Kaikki on hyvin. Mutta jos kirjoitan jotain pidempään, mahdollisesti se on menossa hiipiä bar avaruuteen. Mutta vielä pahempaa, se kääntyy kaikki tällä kertaa, vaikka emme ole koskaan puhuneet se, pino käytetään muita juttuja. Se ei ole vain paikallisia muuttujia. 

C on hyvin alhainen kieli. Ja se tavallaan salaa käyttää pinon myös muistaa toimintoa kutsutaan, mitä osoite on edellisen toiminnon, joten se voi hypätä takaisin tuon toiminnan. Joten kun tärkeimmät puhelut vaihtaa, joukossa asiat työnnetään pinoon eivät ole vain swapit paikallisia muuttujia, tai sen perusteluja, myös salaa työnsi pinoon edustamana jonka punainen siivu täällä, on osoite tärkein fyysisesti tietokoneen muistiin, niin, että kun vaihto on tehty, tietokone tietää minun täytyy mennä takaisin päävalikkoon ja lopuksi täytäntöönpanosta päätehtävä. Joten tämä on vaarallista nyt, koska jos käyttäjä on hyvin enemmän kuin hei, siten, että käyttäjä tulo clobbers tai korvaa että punainen osa, loogisesti jos tietokoneen juuri menossa sokeasti olettaa että tavua että punainen siivu ovat osoite, johon se pitäisi palauttaa, mitä jos vastustaja on fiksu tai onni laittaa järjestyksessä tavuja siellä joka näyttää osoitteen, mutta se on osoite koodia että hän haluaa tietokone suorittaa sijasta tärkein? 

Toisin sanoen, jos se, mitä käyttäjä on kirjoittaa kehoitteessa, ei ole vain jotain harmittomia kuten Hei, mutta se on itse asiassa koodi, joka on vastaava poistaa kaikki tämän käyttäjän tiedostot? Tai sähköpostitse salasanansa minulle? Tai aloita kirjautumalla niiden näppäimistön, oikea? Meillä on yksi keino, nyt säätää tänään, että he voivat kirjoittaa ei just hello maailma tai heidän nimensä, he voisivat olennaisesti pass koodin, nollat ​​ja ne, että tietokone virheitä sekä koodin ja osoite. Joten vaikkakin abstraktisti, jos käyttäjä on tarpeeksi kontradiktorisessa koodi että me yleistää täällä A. on hyökkäys tai vastustajia. Joten vain huonoja juttuja. Emme välitä numeroita tai nollia tai niistä tänään, niin että voit päätyä korvaamasta että punainen osa, huomata, että sekvenssi tavuja. O 835 C nolla kahdeksan nolla. Ja nyt Wikipedian artikkeli tästä on ehdottanut, jos nyt todella alkaa merkinnät tavua tietokoneesi muisti, mitä Wikipedia artikkeli on Ehdotuksen on, että mitä jos osoite Kyseisen vasemmassa yläkulmassa tavu on 80 C 0 3508. 

Toisin sanoen, jos pahis on fiksu kanssa hänen koodi todella laittaa numero täällä, että vastaa osoitteen koodin hän ruiskutetaan tietokoneeseen, voit voi huijata tietokoneen osaksi tee mitään. Tiedostojen poistaminen, sähköpostitse asioita, haistaa liikennettä, kirjaimellisesti mitään voisi olla ruiskutetaan tietokoneeseen. Ja niin puskurin ylivuoto hyökkäys sen ytimessä on vain tyhmä, tyhmä ohittaminen array, joka ei ollut sen rajoja tarkistetaan. Ja tämä on mitä on erittäin vaarallinen ja samanaikaisesti super tehokas C on se, että meillä todellakin on pääsy kaikkialle muistiin. Se on jopa meille, ohjelmoijat, joka kirjoittaa alkuperäisen koodin tarkistaa hiton pituus tahansa paneelit että olemme manipuloimalla. Joten tehdä selväksi, mikä on korjata? Jos me palauta tämä koodi, minun ei pitäisi vain muuttaa pituutta baari, mitä muuten minun pitäisi tarkistaa? Mitä muuta minun pitäisi tehdä jotta estää tämän hyökkäyksen täysin? En halua vain sokeasti sanoa että sinun pitäisi kopioida niin monta tavua kuten pituus bar. Haluan sanoa, kopioida kuin monet tavua ovat baarissa asti myönnetyn muisti, tai 12 maksimaalisesti. Joten minun on jonkinlainen jos ehto että ei tarkista pituus baari, mutta jos se ylittää 12, me vain kova koodi 12 koska suurin mahdollinen etäisyys. Muuten ns puskuriin ylivuoto hyökkäys voi tapahtua. Alareunassa näiden dioja, jos olet kiinnostunut lukea lisää on todellinen alkuperäinen artikkeli jos haluat katsoa. 

Mutta nyt, joukossa hinnat maksettu täällä oli tehottomuutta. Joten se oli nopea alhainen katsomaan mitä ongelmia voi syntyä nyt että me on pääsy tietokoneen muistiin. Mutta toinen ongelma meillä jo kompastellut maanantaina oli juuri tehottomuus linkitetyn listan. Olemme takaisin lineaarisen ajan. Meillä ei ole enää yhtenäinen joukko. Meillä ei ole random access. Emme voi käyttää hakasulku merkintätapa. Me kirjaimellisesti täytyy käyttää while-silmukka jollainen Kirjoitin hetki sitten. Mutta maanantaina, me väitti, että voimme hiipiä takaisin osaksi keskustelussa tehokkuus saavuttamiseksi jotain, joka on logaritminen ehkä, tai paras vielä, ehkä jopa jotain, joka on niin kutsuttu vakio ajan. Miten siis voimme tehdä, että käyttämällä näitä uusia työkalut, nämä osoitteet, nämä osoittimia, ja ketjuttaminen asioita oman? No, oletetaan, että täällä, nämä ovat joukko numeroita että haluamme tallentaa tietorakenne ja haku tehokkaasti. Voimme ehdottomasti kelata viikko kaksi, heittää nämä taulukkoon, ja etsiä niitä käyttämällä binäärihakupuu. Hajota ja hallitse. Ja itse asiassa kirjoitit binary toimialalla PSET3, jossa toteutetaan Etsi ohjelma. Mutta tiedätkö mitä. Siellä on tavallaan enemmän fiksu tapa tehdä tämä. Se on vähän enemmän hienostunut ja se ehkä antaa meille mahdollisuuden nähdä, miksi binary haku on niin paljon nopeammin. Ensimmäinen, nyt käyttöön käsite puu. Joka vaikka todellisuus puut eräänlainen kasvaa näin, maailman tietokoneen tiede he eräänlainen kasvaa alaspäin kuten sukupuu, jossa on isovanhemmat tai suurta isovanhemmat tai vaikka mitä huipulla, patriarkka ja matriarkka perheen, vain yksi ns root, solmu, alle jotka ovat sen lapsia, jonka alapuolella ovat sen lapsia, tai sen jälkeläiset yleisemmin. Ja kukaan roikkui pohja perheen puu on paitsi perheen pienimmille, voi myös vain olla yleisesti kutsutaan puun lehdet. 

Joten tämä on vain nippu sanoja ja määritelmiä jotain kutsutaan puu tietokone tiede, aivan kuten sukupuu. Mutta on harrastaja inkarnaatioita puita, joista yksi kutsutaan binäärihakupuu. Ja voit eräänlainen härnätä lisäksi mitä tämä asia ei. No, se on binary missä mielessä? Mistä binary tulevat tänne? Anteeksi? Se ei ole niin paljon joko tai. Se on enemmän, että kussakin solmussa ei ole enemmän kuin kaksi lasta, kuten näemme täällä. Yleensä, tree-- ja teidän vanhemmat ja isovanhemmat voi olla niin monta lasta tai grandkids koska he todella haluavat, ja niin esimerkiksi siellä meillä on kolme lapset pois, että oikea käsi solmu, mutta binääripuun, solmulla on nolla, yksi tai kaksi lasta maksimaalisesti. Ja se on mukava ominaisuus, koska jos se on rajattu kahdella, aiomme pystyä saada hieman log pohja kaksi toiminta täällä lopulta. Joten meillä on jotain logaritminen. Mutta siitä lisää hetken kuluttua. Hae puu tarkoittaa, että numerot ovat järjestetty siten, että vasen lapsen arvo on suurempi kuin juuri. Ja sen oikea lapsi on suurempi kuin juuri. Toisin sanoen, jos käytät jotakin solmut, piireissä tätä kuvaa, ja katsoo sen vasen lapsi ja sen oikea lapsi, ensimmäinen tulisi olla alle, Toinen tulisi olla suurempi kuin. Joten järki tarkistaa 55. Se on jäljellä lapsi on 33. Se on vähemmän kuin. 55, sen oikea lapsi on 77. Se on suurempi kuin. Ja se on rekursiivinen määritelmä. Voisimme tarkistaa jokainen näistä solmut ja sama kuvio vaikeuttaisivat. 

Niin mitä mukavaa binäärihakupuu, on että yksi, voimme toteuttaa sen kanssa struct, aivan kuten tämä. Ja vaikka olemme heitto paljon rakenteiden teidän, he hieman intuitiivinen nyt toivottavasti. Syntaksi on edelleen vaikeaselkoisten varma, mutta sisällön solmun tässä context-- ja pidämme käyttää sanaa solmu, onko se suorakulmio näytöllä tai ympyrä, se on vain joitakin yleisiä kontti, tässä tapauksessa puu, jollainen näimme, tarvitsemme kokonaisluku kussakin solmujen ja sitten minun täytyy kaksi osoitinta osoittelee vasemmalle lapsi ja oikea lapsi, vastaavasti. Niin, että miten voisimme toteuttaa että struct. Ja miten voisin toteuttaa se koodi? No, katsotaanpa ottaa nopeasti katsokaa tämä pieni esimerkki. Se ei ole toimiva, mutta olen kopioida ja liittää, että rakenne. Ja jos toiminto binary hakupuu kutsutaan haku, ja tämä ottaa kaksi argumenttia, kokonaisluku N ja osoitin solmuun, joten osoitin puun tai osoitin juureen puu, miten voin mennä noin etsivät N? No, ensinnäkin, koska olen käsitellään osoittimet, Aion tehdä järki tarkistaa. Jos puu tasavertaisten vastaa null, on N tässä puussa tai ei tässä puussa? Se ei voi olla, eikö? Jos olen viime null, Siellä ei ole mitään. Voisin yhtä hyvin vain sokeasti sanoa return false. Jos annat minulle mitään, en varmasti voi löytäneet numero N. Mitä muuta voisin Tarkista nyt? Aion sanoa hyvin muuta, jos N on vähemmän kuin mitä on puu solmu että olen ollut luovutettu N arvo. Toisin sanoen, jos määrä olen etsivät, N on pienempi kuin solmun että Etsin. Ja solmu etsin klo kutsutaan puu, ja muistaa edellisen esimerkin saada aikaa arvon osoitin, Käytän nuoli merkintää. Joten jos N on pienempi kuin puu nuoli N, haluan käsitteellisesti mennä vasemmalle. Miten ilmaista etsiminen jäljellä? Tehtävä selväksi, jos tämä on kuva kyseessä, ja olen läpäissyt että ylin nuoli, joka on alaspäin. Se on minun puu osoitin. Olen suunnattu puun juureen. Ja Etsin sanoa, varten numero 44, mielivaltaisesti. On 44 pienempi tai yli 55 ilmeisesti? Joten se on vähemmän kuin. Ja niin tämä jos ehto koskee. Joten käsitteellisesti, mitä haluan etsi seuraava jos Etsin 44? Joo? 

Aivan, haluan etsi vasen lapsi, tai vasen osa-puu tätä kuvaa. Ja itse asiassa, haluan kautta kuva täällä vain hetken, koska En voi naarmuttaa tätä. Jos aloitan täällä 55, ja Tiedän, että arvo 44 Etsin on vasemmalle, se on eräänlainen samankaltaisten repiminen puhelinluettelon puolet tai repiminen puu kahtia. En enää tarvitse välittää tämä koko puolet puusta. Ja kuitenkin, kumma suhteen rakenne, tämä asia täällä, että alkaa 33, että itse on binäärihakupuu. Sanoin sanan rekursiivinen ennen koska todellakin tämä on tietorakenne, joka määritelmän on rekursiivinen. Saatat olla puu, joka on tämän iso, mutta jokainen sen lapsista edustaa puu vain hieman pienempi. Sen sijaan se on Isoisä tai mummo, nyt se on vain äiti or-- En voi say-- ei äiti tai isä, joka olisi outoa. Sen sijaan kaksi lasta siellä olisi kuin veli ja sisarus. Uuden sukupolven sukupuun. Mutta rakenteellisesti, se on sama ajatus. Ja se osoittautuu Minulla toiminto jolla voin hakea binäärihaku puu. Sitä kutsutaan hakua. Etsin N puu nuoli vasemmalle muuten, jos N on suurempi kuin arvo että olen tällä hetkellä. 55 tarina hetki sitten. Minulla on toiminto nimeltään hakukone, jonka voin vain siirtää N tämä ja rekursiivisesti etsiä sub-puu ja vain paluu mitä se sitten vastaus. Else Minulla joitakin lopullinen pohja tässä tapauksessa. 

Mikä on lopullinen asia? Puu on joko nolla. Arvo Olen joko etsimässä on vähemmän kuin se tai suurempi kuin tai yhtä suuri kuin se. Ja voisin sanoa yhtä suuri tasa-arvoisia, mutta loogisesti se on vastaa vain sanoa muuta täällä. Niin totta on, miten löydän jotain. Joten toivottavasti tämä on entistäkin pakottavia esimerkki kuin tyhmä sigma toiminto teimme muutamia luentoja takaisin, jossa se oli yhtä helppo käyttää silmukka laskea ylös kaikki numerot yhdestä N. täällä tietorakenne että itse on rekursiivisesti määritelty ja rekursiivisesti piirretty, nyt meillä on kyky ilmaista itseämme koodin että itsessään on rekursiivinen. Joten tämä on täsmälleen sama koodi tähän. 

Mitä muita ongelmia voimme ratkaista? Joten nopea askeleen päässä puita vain hetken. Tässä on, sanovat, Saksan lipun. Ja siellä on selvästi kuvio tämä lippu. Ja siellä on paljon liput maailmassa ovat niin yksinkertaista kuin tämä suhteen niiden värejä ja kuvioita. Mutta olettaa, että tämä on tallennettu .GIF Tai JPEG, tai bittikartta, tai ping, tahansa graafinen tiedostomuoto jolla olet tuttu, joista osa olemme leikkii in PSET4. Tämä ei tunnu kannata tallentaa musta pikseli, musta pikseli, musta pikseli, piste, piste, piste, koko joukko musta pikseliä ensimmäinen juova, tai rivin, sitten koko joukko sama, niin koko joukko sama, ja sitten koko joukko punainen pikseliä, punainen pikseliä, punainen pikseliä, sitten koko nippu keltainen pikseliä, keltainen, eikö? 

Siellä on niin tehottomuutta täällä. Miten intuitiivisesti pakkaa Saksan lippu jos täytäntöönpanosta sen tiedostona? Kuten mitä tietoja voimme olla vaivautua tallentamiseen levyllä järjestyksessä pienentää meidän tiedoston koon kuten megatavu on kilotavu, jotain pienempiä? Jossa sijaitsee irtisanominen tässä tehdä selväksi? Mitä voisit tehdä? Joo? Aivan. Miksi ette ennemmin kuin muistaa väri jokaisen hiton pikselin aivan kuten olet tekemässä PSET4 kanssa bitmap tiedostomuoto, miksi et vain edustaa vasemmassa reunassa pikseliä, esimerkiksi joukko mustia pisteitä, nippu punainen, ja joukko keltainen, ja sitten vain jotenkin koodata Ajatus Toista 100 kertaa tai toista tämä 1000 kertaa? Jos 100 tai 1000 on vain kokonaisluku, joten voit saada pois vain yhden numeron sen sijaan, satoja tai tuhansia ylimääräisiä pikseliä. Ja todellakin, näin me voisi puristaa Saksan lippu. Ja Nyt Entä Ranskan lipun? Ja pieni jonkinlainen mielenterveyden käyttää, mikä lippu voidaan pakata enemmän levylle? Saksan lipun tai Ranskan lippu, jos otamme tämän lähestymistavan? Saksan lippu, koska siellä horisontaalisempaa irtisanominen. Ja suunnittelu, monet graafinen tiedosto formaatit todellakin toimi ositusriviä vaakasuunnassa. He voisivat toimia pystysuoraan, vain ihmiskunta päätti vuotta sitten, että me will yleensä ajatella asioita rivi riviltä sijaan sarake kerrallaan. Joten todellakin jos olisit tarkastella tiedosto koko Saksan lipun ja ranskalainen lippu, niin kauan kuin päätöslauselma on sama, sama leveys ja korkeus, tämä täällä tulee olemaan suurempi, koska olet on toistettava itse kolme kertaa. Sinun täytyy määrittää sininen, toista itse, valkoinen, toista itseäsi, punainen, Toistan itse. Et voi vain mennä aivan oikealle. Ja syrjään, jotta tyhjentää puristus on kaikkialla, jos nämä ovat neljä kehyksiä video-- sinua Muistanette, että elokuva tai video on yleensä kuten 29 tai 30 kuvaa sekunnissa. Se on kuin pieni läppä kirja, jossa vain nähdä kuva, kuva, kuva, kuva, kuva vain huippunopea niin se näyttää toimijoiden ruudulla liikkuvat. Tässä kimalaisten päälle alkuun kukkakimpun. Ja vaikka se voisi olla eräänlainen vaikea nähdä ensi silmäyksellä, ainoa asia liikkuvat tämä elokuva on mehiläinen. 

Mikä on tyhmä varastoinnista video pakkaamattomana? Se on tavallaan jätteiden tallentaa video neljä lähes identtinen kuvien poikkeavat toisistaan ​​vain siltä osin kuin jos mehiläinen on. Voit heittää pois useimmat näistä tiedoista ja muistan vain, esimerkiksi, ensimmäinen runko ja viimeisen kuvan, Avainruutujen jos olet koskaan kuullut sanan, ja vain säilytä keskimmäinen jossa mehiläinen on. Ja sinun ei tarvitse tallentaa kaikki vaaleanpunainen, ja sininen, ja vihreät arvot samoin. Joten tämä on vain sanoa, että puristus on kaikkialla. Se on tekniikka käytämme usein tai ottaa itsestäänselvyytenä näinä päivinä. 

Mutta miten pakata tekstin? Miten te sitten puristamalla tekstiä? No, jokainen merkkiä ASCII on yksi tavu, tai kahdeksan bittiä. Ja se on tavallaan tyhmä, eikö? Koska olet todennäköisesti kirjoitat ja E ja I ja O ja U paljon useammin kuin kuten W tai Q tai Z, riippuen kielestä, jolla kirjoitat varmasti. Ja niin miksi käytämme kahdeksan bittiä jokaisen kirjeen, mukaan lukien vähiten suosittu kirjaimia, eikö? Miksi ei käytä vähemmän bittiä Super suosittu kirjaimet, kuten E, mitä arvata ensimmäinen Wheel of Fortune, ja käyttää enemmän bittiä vähemmän suosittu kirjaimet? Miksi? Koska olemme juuri menossa käyttää niitä harvemmin. 

No, käy ilmi, että siellä on ollut yritetty tehdä tätä. Ja jos muistaa palkkaluokasta koulu tai lukion, morseaakkoset. Morseaakkoset on pisteitä ja viivoja, jotka voivat olla lähetetty pitkin lanka ääniä tai signaaleja jonkinlaisia. Mutta Morse koodi on super clean. Se on tavallaan binary järjestelmän että sinulla on pisteitä tai viivoja. Mutta jos näet esimerkiksi kaksi pistettä. Tai jos luulet takaisin toimijalle joka menee piip, piip, piip, äänimerkin, lyömällä hieman laukaista joka lähettää signaalin, jos, vastaanottaja, saa kaksi pisteitä, minkä viestin olet saanut? Täysin mielivaltaista. 

I? I? Tai mitä about-- tai I? Ehkä se oli vain kaksi E oikeutta? Joten ei tämä ongelma ja decodability kanssa Morse koodi, jolloin jollei henkilö lähettää sinulle viestin todella pysähtyy joten voit lajitella nähdä tai kuulla erot kirjaimet, se ei ole riittävää vain Lähetä virta nollia ja ykkösiä, tai pisteitä ja viivoja, koska siellä on epäselvyyttä. E on yksi piste, joten jos katso kaksi pistettä tai kuulet kaksi pistettä, ehkä se on kaksi E: n tai ehkä se on yksi I. Joten tarvitsemme järjestelmän, joka on hieman viisaampi kuin. Joten mies nimeltä Huffman vuotta sitten keksi juuri tämän. Joten me vain menossa ottaa nopealla silmäyksellä kuinka puut ovat Germane tähän. Oletetaan, että tämä on noin tyhmä viesti, jonka haluat lähettää, koostuu vain A, B, C: n D: n ja E: n, mutta siellä on paljon irtisanomisten täällä. Se ei ole tarkoitus olla Englanti. Se ei ole salattu. Se on vain tyhmä viestiä jossa on paljon toistoa. Joten jos todella laskea kaikki N, B: n, C: n, D: n ja E: n, tässä taajuus. 20% kirjaimet ovat A: n, 45%: n kirjainten ovat E: n, ja kolme muita taajuuksia. Laskimme siellä manuaalisesti ja vain teki matematiikka. 

Joten käy ilmi, että Huffman, jokin aika sitten, tajusi, että tiedät mitä, jos aloitan rakennus puu, tai metsä puita, jos haluatte, seuraavasti, voin tehdä seuraavasti. Aion antaa solmuun jokaiselle kirjaimet, jotka välitän ja aion säilyttää sisällä että solmun taajuuksia liukuluku arvo, tai voit käyttää sitä N, liian, mutta me vain käyttää float täällä. Ja algoritmi hän ehdotti, että te tätä metsä yhden solmun puita, joten Super lyhyt puita, ja aloitat liittämällä ne uusia ryhmiä, uudet vanhemmat, jos haluatte. Ja voit tehdä tämän valitsemalla kaksi pienintä taajuutta kerrallaan. Joten otin 10% ja 10%. Luon uuden solmu. Ja kehotan uusi solmu 20%. 

Joka kahden solmun yhdistän seuraavaksi? Se on vähän epäselvä. Joten on joitakin nurkkaan tapauksissa harkita, mutta pitää asiat melko, Aion valita 20% - Olen nyt sivuuttaa lapsia. Aion valita 20% ja 15% ja piirtää kaksi uutta reunat. Ja nyt joka kahden solmun voin loogisesti yhdistää? Ohita kaikki lapset, kaikki lapsenlapset, katsokaa juuret nyt. Mitkä kaksi solmua voin sitoa yhteen? Kohta kaksi ja 0,35. Sallikaa minun tehdä kaksi uutta reunat. Ja sitten Minulla on vain yksi jäljellä. Joten tässä on puu. Ja se on laadittu tarkoituksella etsiä sellainen aika, mutta huomaa, että reunat ovat myös merkitty nolla ja yksi. Joten kaikki vasemmat reunat ovat nolla mielivaltaisesti, mutta johdonmukaisesti. Kaikki oikeat reunat ovat sellaisia. 

Ja niin mitä Hoffman ehdotetaan, jos haluat edustaa B, sijaan edustavat useita 66 Ascii joka on kahdeksan koko bittiä, Tiedätkö mitä, juuri myymälä kuvio nolla, nolla, nolla, nolla, koska se on polku minun puu, herra Huffman n puu, lehteen juuresta. Jos haluat tallentaa E, sitä vastoin eivät Lähetä kahdeksan bittiä, jotka edustavat E. Sen sijaan, lähettää mitä kuvio bittiä? Yksi. Ja mitä mukavaa tästä on että E on suosituin kirjeen, ja käytät lyhin koodia. Seuraavaksi suosituimpia kirjain näyttää se oli A. Ja niin kuinka monta bittiä hän ehdottaa käyttävät tätä? Nolla, yksi. 

Ja koska se on pantu täytäntöön koska tämä puu, nyt haluaisin määrätä siellä ei epäselvyyttä Morse koodi, koska kaikki kirjeitä välität ovat lopussa näiden reunojen. Niin se on vain yksi soveltaminen puu. Tämä is-- ja minä aalto käteni tässä miten voisi toteuttaa tätä C rakenne. Meidän täytyy vain yhdistää symboli, kuten char, ja taajuus vasemmalle ja oikealle. Mutta katsokaamme kaksi lopullinen esimerkkejä että sinun saada varsin tuttuja jälkeen tietokilpailu nolla ongelma asettaa viisi. 

Joten on datarakenne tunnetaan hajautustaulua. Ja hash table on eräänlainen jäähtyä että se on kauhat. Ja oletetaan siellä on neljä kauhat täällä, vain neljä välilyöntejä. Tässä korttipakan, ja täällä on Club, lapio, klubi, timantit, klubi, timantteja, klubi, timantit, clubs-- joten tämä on satunnainen. Hearts, hearts-- joten olen bucketizing kaikille lähteille täällä. Ja tiiviste tarpeisiin katsomaan teidän panos, ja sitten laittaa se tietyllä aseta perustuu mitä näet. Se algoritmia. Ja Käytin super yksinkertainen visuaalinen algoritmi. Vaikein osa oli muistaa, mitä kuvat olivat. Ja sitten on neljä yhteensä asioita. 

Nyt pinot kasvoivat, mikä on tarkoituksellinen suunnittelu asia täällä. Mutta mitä muuta voisi tehdä? Joten oikeastaan ​​täällä meillä joukko vanhoja koulun tenttikirjat. Oletetaan, että joukko opiskelijat nimet ovat täällä. Tässä isompi hajautustaulua. Neljän sijasta kauhat, Olen, sanokaamme 26. Ja emme halua mennä lainata 26 asioita ulkopuolelta [? Annenberg?], Niin tässä on viisi, jotka edustavat Z. Ja jos minä katso opiskelija nimi alkaa, Aion laittaa hänen tietokilpailu siellä. Jos joku alkaa C, tuolla, A-- oikeastaan, ei halua tehdä sitä. B menee tänne. Joten minulla ja B ja C And nyt tässä on toinen opiskelija. Mutta jos tämä tiiviste on toteutettu joukko, Olen sellainen ruuvattu tässä vaiheessa, eikö? Olen sellainen täytyy laittaa tämä jonnekin. 

Joten yksi tapa voin ratkaista tämä on, kaikki oikea, on kiireinen, B on varattu, C on varattu. Aion laittaa hänet D. Joten ensimmäinen, minulla on satunnainen välittömän pääsyn kuhunkin kauhat opiskelijoille. Mutta nyt se on tavallaan hajautettujen jotain lineaarinen, koska jos haluan etsiä joku jonka nimi alkaa, tarkistan täällä. Mutta jos tämä ei ole opiskelija Etsin, Olen sellainen täytyy aloittaa tarkkailun kauhat, sillä mitä tein oli tavallaan lineaarisesti koetin tietorakennetta. Typerä tapa sanoa katsokaa ensimmäisen käytettävissä aukon, ja laittaa niin suunnitelma B, niin sanoakseni, tai suunnitelma D tässä tapauksessa arvo kyseisessä paikassa sijaan. Tämä on vain niin, että jos olet sai 26 paikkakunnalla ja ei opiskelijoiden nimi Q tai Z, tai jotain että ainakin käytät tilaa. 

Mutta olemme jo nähneet enemmän fiksu ratkaisuja täällä, eikö? Mitä sinä tekisit sen sijaan jos sinulla on törmäyksen? Jos kaksi ihmistä on nimi, mitä olisi ovat älykkäämpiä tai enemmän intuitiivinen ratkaisu kuin vain laskemisesta jossa D on tarkoitus olla? Miksi en vain mennä ulkopuolella [? Annenberg?], kuten malloc, toinen solmu, laita se täällä, ja sitten laittaa että opiskelija täällä. Niin että olen lähinnä on jonkinlainen array, tai ehkä enemmän tyylikkäästi kuin olemme alkavat nähdä linkitetty lista. 

Ja niin hash table on rakenne että voisi näyttää aivan kuten tämä, mutta enemmän taitavasti, jotain nimeltään erillinen ketjutus, jolloin tiiviste yksinkertaisesti on joukko, jokaisen jonka alkiot ei ole numero, on itse linkitetty lista. Niin että saat erittäin nopean pääsyn päätettäessä, missä hash oman arvon. Aivan kuten kanssa korttien esimerkiksi Tein erittäin nopeita päätöksiä. Hearts menee täällä, timantit menee täällä. Sama täällä, menee täällä, D menee täällä, B menee täällä. Joten huippunopea look-ups, ja jos satut törmätä tapaus jossa sinulla törmäyksiä, kaksi ihmiset samanniminen, hyvin sitten vain alkaa liittämällä ne yhteen. Ja ehkä pitää ne lajitellaan aakkosjärjestyksessä, ehkä et. Mutta ainakin nyt meillä on dynamiikkaa. Niin toisaalta meillä on huippunopea vakio aika, ja tavallaan lineaarisen ajan mukana jos nämä liittyvät luettelot alkaa saada hieman pitkä. 

Joten tällainen typerä, geeky vitsi vuotta sitten. Klo CS50 hakata--thon, kun opiskelijat tarkistaa, jotkut TF tai CA vuosittain mielestä on hauska sietää merkki näin, jos se vain tarkoittaa jos nimi alkaa, mennä tällä tavalla. Jos nimesi alkaa jossa B, mene this-- OK, se on hauskaa ehkä myöhemmin lukukauden. Mutta on toinen tapa tehdä tämä, liian. Tule takaisin, että. 

Joten on tämä rakenne. Ja tämä on meidän viimeinen rakenne tänään, joka on jotain kutsutaan trie. T-R-I-E, joka jostain syystä on lyhyt koskevia hakuja, mutta sitä kutsutaan trie. Joten trie on toinen mielenkiintoinen amalgaami paljon näitä ajatuksia. Se on puu, joka olemme nähneet aiemmin. Se ei ole binäärihakupuu. Se on puu väliä Lasten lukumäärä, mutta jokainen lasten trie on jono. Taulukon koko, sanovat, 26 tai ehkä 27 jos haluat tukea väliviivalliset nimet tai heittomerkit ihmisten nimet. 

Ja niin tämä on tietorakenne. Ja jos tarkastellaan ylhäältä alas, kuten jos katso yläsolmun siellä, M, on osoittaa vasemmanpuoleisin asia siellä, joka sitten, X, W, E, L, L. Tämä on vain tiedot rakenne, joka mielivaltaisesti on tallentamiseen ihmisten nimet. Ja Maxwell on tallentaa vain seuraavia polku array array array. Mutta mikä on hämmästyttävää noin trie on että, kun taas linkitetty lista ja jopa array, paras olemme koskaan saanut on lineaarisen ajan tai logaritminen aikaa etsimässä jonkun kyytiin. Tämän datarakenteen trien, jos tietoni rakenne on yksi nimi sen ja etsin Maxwell, minä olen menossa löytää hänet melko nopeasti. Minä vain etsiä M--X-W-E-L-L. Jos Näiden tietojen rakenne, sitä vastoin, jos N on miljoona, jos on miljoonaa nimeä tässä datarakenteeseen Maxwell on edelleen olemaan löydettävissä jälkeen vain M--X-W-E-L-L vaiheet. Ja David-- D--V-I-D-vaiheita. Toisin sanoen, rakentamalla tietorakenne, joka on sai kaikki nämä ryhmät, jotka kaikki itse tukea random access, Voin aloittaa etsii ihmisten nimi käyttämällä aikaa, joka on verrannollinen ei numero asioita tietorakenteen, kuin miljoona nykyiset nimet. Aikaa se vie minut löytää M--X-W-E-L-L tällä tietorakenne on verrannollinen ei datan koko rakenteen, vaan nimen pituus. Ja realistisesti nimet etsimme ylös eivät koskaan hullu pitkä. Ehkä joku on 10 merkki nimi, 20 nimi. Se on varmasti rajallinen, eikö? On ihmisen maan päällä, jotka on pisin mahdollinen nimi, mutta nimi on vakio arvo pituus, eikö? Se ei vaihtele millään tavoin. Joten tällä tavalla, olemme saavutti tietorakenne joka on vakio aika look-up. Se kestää useita vaiheita pituudesta riippuen syötteen, mutta ei määrää nimi tietorakenteen. Joten jos me kaksinkertainen määrä nimien ensi vuoden miljardista kahteen miljardiin, havainto Maxwell vie täsmälleen sama määrä seitsemän vaihetta löytää hänet. Ja niin me näytämme saavuttaneet Meidän pyhä Graal ajoaikaan. 

Joten Muutaman nopean ilmoituksia. Quiz nolla on tulossa. Siitä lisää kurssin verkkosivuilla seuraavien parin päivän. Maanantain lecture-- se loma täällä Harvardissa maanantaina. Se ei ole New Haven, joten viemme luokka New Haven luento maanantaina. Kaikki on filmattu ja suoratoistona kuten tavallista, mutta Lopetetaan tänään 30 s leike nimeltään "Deep Ajatuksia" by Daven Farnham, joka innostui viime vuonna lauantai Night Liven "syvä ajatuksia" Jack Handy, joka olisi nyt järkevää. 

FILM: Ja nyt, "Deep Ajatuksia "by Daven Farnham. Tiiviste. 

SPEAKER 1: Okei, siinä se nyt. Nähdään ensi viikolla. 

DOUG: Voit nähdä sen toiminnassa. Joten katsomaan juuri nyt. Joten tässä, meillä on lajittelemattoman jono. 

IAN: Doug, voit mennä eteenpäin ja uudelleenkäynnistys tämä vain yksi sekunti, kiitos. Selvä, kamerat liikkuva, joten toimenpiteet kun olet valmis, Doug, OK? DOUG: Hyvä on, niin mitä me on tässä lajittelematonta array. Ja olen värillinen kaikki elementit punaisena, eli se on, itse asiassa, lajittelemattomana. Niin muistaa, että ensimmäinen asia, teemme on me lajitella vasen puoli jono. Sitten lajitella oikea puolet jono. Ja ya-da, ya-da, ya-da, me yhdistää ne yhteen. Ja meillä on täysin lajitellun array. Niin, että miten yhdistää lajitella toimii. 

IAN: Hei, hei, hei, leikata, leikata, leikata, cut. Doug, et voi vain ya-da, ya-da, ya-da, läpi yhdistämisen lajitella. 

DOUG: tein. Se on okei. Olemme hyvä mennä. Haluan vain rullaa. Niin joka tapauksessa, 

IAN: on selitettävä se täydellisemmin kuin. Se vain ei ole tarpeeksi. DOUG: Ian, emme täytyy mennä takaisin yhteen. Se on okei. Niin joka tapauksessa, jos jatkamme merge-- Ian, olemme keskellä kuvaamisen. 

IAN: Tiedän. Ja emme voi vain ya-da, ya-da, ya-da, läpi koko prosessin. Sinun täytyy selittää, miten osapuolet saavat yhdistyivät. 

DOUG: Mutta olemme jo selitti kuinka kaksi sides-- 

IAN: Olet juuri osoittanut niitä yhdistää joukko. DOUG: He tietävät prosessi. He ovat kunnossa. Olemme menneet yli kymmenen kertaa. 

IAN: Sinä vain ohitetaan oikeus yli sen. Menemme takaisin yhteen, sinulle voi sinua ya-da, ya-da sen yli. Okei, takaisin yhteen. 

DOUG: Minun täytyy mennä takaisin läpi kaikki diat? Jumalani. Se on kuin kuudennen kerran, Ian. Se on okei. 

IAN: Selvä. Oletko valmis? Suuri. Toimi.