[Musiikkia] [VIDEOTOISTOSTA] -Hän Valehtelee. -Noin Mitä? -Minä en tiedä. -No Mitä tiedämme? -Se Klo 9.15, Ray Santoya oli ATM. -Joo. Joten kysymys on, mitä hän oli tekemässä 09:16? -Shooting 9 millimetrin jotain. Ehkä hän näki ampuja. -tai Oli työskennellä hänen kanssaan. -Wait. Mene takaisin yksi. -Mitä näet? -Bring Hänen kasvonsa ylöspäin koko näytön. -His Lasit. -On On heijastus. -Se Nuevitas baseball-joukkue. Se on heidän logo. -Ja Hän puhuu kuka on päällään että takki. [Lopeta toisto] DAVID MALAN: Selvä. Tämä on CS50 ja tämä on hieman of [äänetön], jolla olet puuhastellessa ongelma asetettu neljä. Tänään alamme näyttää hieman enemmän syvästi näitä asioita kutsutaan osoittimia, joka vaikka se on melko arcane aihe, käy ilmi, että se on menossa olla keinoja, joilla me voi alkaa rakentaa ja kokoonpano paljon kehittyneempiä ohjelmia. Mutta teimme sen viime keskiviikkona Poiketen joidenkin claymation ensin. Joten tämä, muistaa, on Binky ja käytimme häntä jotta katsomaan ohjelmaa, joka ei oikeastaan ​​tee mitään mielenkiintoista, mutta se teki paljastaa muutamia ongelmia. Joten alkaa tänään, miksi emme kävele nopeasti läpi muutamia näistä vaiheista, yritä tislata ihmisen ehdoilla mitä täällä on tekeillä ja miksi tämä on huono, ja sitten siirtyä ja todella alkaa rakentaa jotain tätä tekniikkaa? Niinpä nämä olivat ensimmäiset kaksi riviä tässä ohjelmassa ja maallikon termein, mitä nämä kaksi riviä tehdä? Joku, joka on kohtuullisen mukava mitä on ilmoitettu ruudulla? Mitä nämä kaksi riviä tehdä? Se ei ole kaikki, että eroaa viikko yksi, mutta on joitakin uusia erityinen symboli. Joo? Takaisin sinne. Yleisö: ilmoittaminen viitteitä? DAVID MALAN: Sano uudestaan? Yleisö: ilmoittaminen viitteitä? DAVID MALAN: ilmoittaminen osoittimet ja katsotaanpa tarkentaa sitä vähän enemmän. Yleisö: [äänetön] osoite X ja sitten y. DAVID MALAN: Ja sitten käsitellä. Joten erityisesti mitä teemme on me julistaa kaksi muuttujaa. Nämä muuttujat kuitenkin menossa on tyyppiä int tähti, joka tarkemmin sanottuna tarkoitetaan he aikovat säilyttää osoite int, vastaavasti, x ja y. Nyt on olemassa mitään arvoja? Onko todellinen osoitteet näissä kaksi muuttujaa tässä vaiheessa? Ei. Se on vain niin sanottu roskat arvot. Jos et itse määrittää muuttuja, mikä oli RAM aiemmin aikoo täyttää nollilla ja ne molemmat näistä muuttujista. Mutta emme vielä tiedä mitä ne ovat ja se on olemaan avain miksi Binky menetti päänsä viime viikolla. Joten tämä oli claymation inkarnaatio tämän jolloin sinulla on vain kaksi muuttujaa, pieni pyöreä kappaletta savi, joka voi tallentaa muuttujia, mutta kääritty ylös nuolet osoittavat, he eivät oikeastaan ​​osoittaa minne tahansa sinänsä tunnettuja. Joten sitten meillä oli tätä linjaa, ja tämä oli uutta viime viikolla, malloc muistin jako, joka on vain hieno tapa kertoa käyttöjärjestelmä, Linux tai Mac OS tai Windows, hei, antaa minulle muistia, ja kaikki sinun täytyy kertoa käyttöjärjestelmä on mitä kun he pyytävät sitä muistia. Se ei tule välitä mitä aiot tehdä sen kanssa, mutta sinun täytyy kertoa toiminta järjestelmä mitä Poiketen malloc. Joo? Yleisö: Kuinka paljon? DAVID MALAN: Kuinka paljon? Kuinka paljon tavuina, ja niin, tämä, jälleen, keinotekoinen esimerkki, on vain sanoa, antaa minulle koko int. Nyt koko int on neljä tavua tai 32 bittiä. Joten tämä on vain tapa sanomalla, hei, käyttöjärjestelmä, anna minulle neljä tavua muistia että voin käyttää käytettävissäni, ja erityisesti, mitä malloc paluu osalta kuin kimpale neljän tavun? Yleisö: Osoite? DAVID MALAN: osoite. Osoitteen että murikka neljä tavua. Aivan. Ja niin se mitä on tallennettu lopulta x ja siksi emme oikeastaan välitä mitä määrää, että osoite on, onko se OX1 tai OX2 tai jotkut arvoituksellinen heksadesimaaliosoitteen. Me vain välitä kuvallisesti että muuttuja x on nyt osoittaen että murikka muistia. Niin, että nuoli edustaa osoitin, tai tarkemmin sanottuna, muistin osoite. Mutta jälleen kerran, emme yleensä välitä mitä nämä todelliset osoitteet ovat. Nyt tämä linja sanoo mitä maallikon termein? Star X saa 42 puolipiste. Mitä tämä tarkoittaa? Haluatko mennä? Älä naarmuta niskaasi. Yleisö: osoite x on 42. DAVID MALAN: Osoite x on 42. Ei aivan. Niin lähellä, mutta ei aivan, koska siellä tähti, joka on prefixing tämä x. Joten meidän täytyy nipistää hieman. Joo? Yleisö: arvo osoitin x osoittaa on 42. DAVID MALAN: OK. Arvo että osoitin x on osoittaa, sanotaan, on 42, tai toisin sanoin, tähti X sanoo, löytää minkä osoite on x, onko se 1 Oxford Katu tai 33 Oxford Street tai OX1 tai ox33 riippumatta että numeerinen osoite on, tähti x on dereferencing x. Niin mene, että osoite ja sitten laittaa numero 42 siellä. Jotta olisi vastaava tapa sanoa, että. Niin, että kaikki hieno ja sitten me edustaisi kuva seuraavasti jossa olemme lisänneet 42 että kimpale neljä tavua oikealla puolella, mutta tämä linja oli, mikä meni pieleen ja Binky pää piipahti pois tässä vaiheessa, koska pahoja asioita tapahtuu, kun te dereference roskat arvot tai voit dereference kelpaa osoittimia, ja sanon kelpaa koska tässä vaiheessa tarina, mitä on sisällä y? Mikä arvo y perustuu on viime vaiheet? Joo? Mikä tuo on? Yleisö: osoite. DAVID MALAN: osoite. Sen pitäisi olla osoite mutta olen alustettu se? Joten en ole vielä. Joten mitä tiedetään olevan siellä? Se on vain noin roskat arvo. Se voi olla mikä tahansa osoite nollasta 2000000000 jos sinulla on kaksi keikkaa muistia, tai nolla 4000000000 jos olet sai neljä gigatavua RAM-muistia. On joitakin roskat arvo, mutta ongelma on että käyttöjärjestelmä, jos se ei ole antanut sinulle että kimpale muisti erityisesti että yrität mennä, se yleensä tulee aiheuttamaan mitä olemme nähneet niin segmentointi vika. Joten itse asiassa, joku teistä, jotka ovat kamppailivat ongelmia virka tai ongelmia, jotka on enemmän yleensä yrittää selvittää segmentointi vika, että yleensä tarkoittaa olet koskettaa segmentin muisti että sinun ei pitäisi olla. Olet koskettaa muisti että käyttöjärjestelmä ei ole salli teidän koskettaa, onko se menemällä liian pitkälle matriisisi tai alkaa nyt, onko se johtuu olet koskettaa muisti että vain on jonkin verran roskaa arvo. Näin tähti X täällä on tavallaan määrittelemätön käyttäytymistä. Sinun ei pitäisi koskaan tehdä sitä, koska kertoimet ovat, ohjelman juuri menossa kaatua, koska sanot, mennä tähän osoitteeseen ja sinulla ei ole aavistustakaan, missä että osoite todella on. Joten käyttöjärjestelmä on todennäköisesti menossa kaataa ohjelman seurauksena ja todellakin, se on mitä tapahtui siellä Binky. Joten lopulta, Binky kiinteä tämä ongelma tässä. Niin että ohjelma itsessään oli virheellinen. Mutta jos sellainen eteenpäin ja suorittaa tämän linjan sijaan, y on yhtä kuin X tarkoittaa vain sitä, mitä osoite on X, myös laittaa se y. Ja niin kuvallisesti, olemme edusti tätä kaksi nuolta X ja y osoittaa samaan paikkaan. Niin semanttisesti, x on yhtä suuri y, koska molemmat näistä varastoivat sama osoite, ergo osoittaen 42, ja nyt, kun sanot tähti y, siirry osoitteeseen y, tämä on mielenkiintoinen sivuvaikutus. Joten osoite y on sama asia kuin osoite x. Joten jos sanot mennä osoitteeseen y ja vaihda arvoksi 13, kuka muu vaikuttaa? X, D kohta, niin sanoakseni, tulisi vaikuttaa samoin. Ja todellakin, miten Nick piirsi tämä kuva vuonna claymation oli juuri sitä. Vaikka me seuraamme osoitin y, päädyimme samaan paikkaan, joten jos me tulostaa ulos X tai Y: n pointee, niin näkisimme arvoa 13. Nyt, minä sanon pointee olla sopusoinnussa videon. Ohjelmoijat, minun tieto, koskaan itse sano sana pointee, se, mikä on terävä at, mutta johdonmukaisuuden videon kanssa, ymmärtää siinä kaikki, että oli tarkoitti tässä tilanteessa. Joten kaikki kysymykset claymation tai viitteitä tai malloc aivan vielä? Ei? Selvä. Joten ilman puheitta katsomaan klo jossa tämä on todella käytetty jonkin aikaa. Joten meillä on ollut tämä CS50 kirjasto että sai kaikki nämä toiminnot. Olemme käyttäneet GetInt paljon, GetString, luultavasti GetLongLong aikaisemmin minun PSET yksi tai niin, mutta mitä todella tapahtuu? No, ottaa vilkaista alla huppu on ohjelma, joka inspiroi miksi annamme sinulle CS50 kirjasto, ja todellakin kuin viime viikolla, aloimme tehdä niitä apupyörät pois. Joten tämä on nyt lajitellaan of jälkipuinti mitä on ollut käynnissä sisällä CS50 kirjasto, vaikka me nyt alkaa liikkua pois useimmissa ohjelmissa. Joten tämä on ohjelma nimeltä scanf 0. Se on erittäin lyhyt. Se vain on näitä rivejä, mutta se otetaan käyttöön toiminto nimeltään scanf että olemme todella menossa nähdä hetki sisällä CS50 kirjasto, vaikkakin hieman eri muodossa. Niin tämä ohjelma rivillä 16 julistaa muuttujan x. Joten antaa minulle neljä tavua int. Se kertoneet käyttäjä, numero ota, ja sitten tämä on mielenkiintoinen linja, joka todella sitoo yhteen viime viikolla ja tämä. Scanf, ja sitten huomaa se vie muotoilumerkkijonoa, kuten printf, % I tarkoittaa int, ja sitten se kestää Toinen väite, joka näyttää hieman funky. Se et-merkki X, ja muistuttaa, me vain näki tämän kerran viime viikolla. Mitä et-merkki X edustaa? Mitä et-merkki tehdä C? Joo? Yleisö: osoite. DAVID MALAN: osoite. Joten se päinvastainen Star operaattori, katsoo tähti operaattori sanoo, siirry tämä osoite, et-merkki operaattori sanoo, selvittää osoite tämän muuttujan, ja niin tämä on avain, koska scanf tarkoitus elämässä on skannata käyttäjän panosta näppäimistö, riippuen mitä hän tyypit, ja sitten lukea, että käyttäjän syöte muuttujaan, mutta me näki viimeisen kahden viikon että swap toiminto että me yritti vaivattomasti toteuttaa oli juuri rikki. Muista, että swap-toiminto, jos me vain ilmoitettu ja B ints, teimme onnistuneesti vaihtaa kaksi muuttujaa sisällä swap Aivan kuten maito ja EYVL, mutta heti kun swap palasi, mikä oli seurausta suhteen x ja y, alkuperäiset arvot? Mitään. Joo. Mitään ei tapahtunut, että aika, koska swap muuttaa vain sen paikallisia kopioita, toisin sanoen, kaikki tällä kertaa, kun olemme on ohimennen perustelut toimintojen, olemme vain ohimennen kopioita nämä väitteet. Voit tehdä, että mitä haluat heidän kanssaan, mutta he aikovat ei ole Vaikutus alkuperäiset arvot. Joten tämä on ongelmallista, jos haluavat toimivat kuin scanf elämässä, jonka tarkoituksena on kartoittaa käyttäjän näppäinsyötteisin ja sitten täytä tyhjät, niin puhua, että on, anna muuttuja kuin X arvoa, koska jos olisin vain siirtää x scanf, jos pidätte logiikkaa viime viikko, scanf voi tehdä mitä haluaa jäljennös x, mutta se ei voinut pysyvästi muuttaa x ellei annamme scanf aarrekartan, niin sanoakseni, jossa x merkitsee paikan, jossa ohitamme osoitekenttään x siten, että scanf voi mennä sinne ja todella muuttaa x: n arvo. Ja niin todellakin, kaikki että tämä ohjelma tekee jos teen scanf 0, minun lähde 5m hakemiston, tehdä scanf 0, piste slash scanf, numero ota 50, kiitos 50. Joten se ei ole kaikki, että mielenkiintoinen, mutta mitä todella tapahtuu on, että heti kun kutsun scanf täällä, x arvo on pysyvästi muuttunut. Nyt, tämä vaikuttaa mukavalta ja hyvä, ja itse asiassa, se tuntuu me ei todellakaan tarvitse CS50 kirjasto enää ollenkaan. Esimerkiksi katsotaanpa juosta tämän kerran lisää täältä. Saanen uudelleen sitä toista. Yritetään numero ota ja sijasta sanomalla 50 kuten ennen, Haluan vain sanoa ei. OK, että on hieman outo. OK. Ja vain joitakin hölynpölyä täällä. Joten se ei näytä kahva virheellinen tilanteita. Joten meidän on minimaalisesti alku lisäämällä joitakin virhe tarkkailun varmistaa, että käyttäjä on kirjoitettu todellinen määrä, kuten 50, koska ilmeisesti kirjoittamalla sanoja ei tunnisteta ongelmallista, mutta se todennäköisesti pitäisi olla. Katsotaanpa tämä versio nyt se minun yrittää reimplement GetString. Jos scanf on kaikki tämän toiminnallisuus rakennettu, Miksi olemme olleet dabbling näillä apupyörät kuten GetString? No, tässä on ehkä oma yksinkertainen versio GetString jolloin viikko sitten, olisin sanonut, antaa minulle merkkijono ja kutsua sitä puskuri. Tänään aion aloittaa vain sanomalla char tähti, joka muistaa, se on vain synonyymi. Se näyttää pelottavampi mutta se on täsmälleen sama asia. Joten antaa minulle muuttuja nimeltä puskuri joka tulee tallentaa merkkijonon, kertoa käyttäjälle merkkijono kiitos, ja sitten, aivan kuten ennen, koetamme lainata tämä oppitunti scanf % S tällä kertaa ja sitten siirtää puskurissa. Nyt nopeasti järki tarkistaa. Miksi en sano Ampersand puskuri tällä kertaa? Päätellä edellisessä esimerkissä. Yleisö: Char tähti on osoitin. DAVID MALAN: Aivan, koska tällä kertaa, char tähti on jo osoitin, osoite, määritelmän kyseisen tähti siellä. Ja jos scanf odottaa osoitteen, riittää vain siirtää puskurissa. Minun ei tarvitse sanoa ampersand puskuriin. Utelias, voisit tehdä jotain tällaista. Se on eri merkitys. Tämä antaisi sinulle osoitin on osoitin, joka on itse asiassa voimassa asia C, mutta Nyt, pidettävä yksinkertaisina ja pitää tarina johdonmukainen. Olen juuri menossa kulkea puskuri ja se on oikein. Ongelmana kuitenkin on tämä. Anna minun mennä eteenpäin ja suorittaa tämän Ohjelman jälkeen kääntämiseen. Tee scanf 1. Hitto, minun kääntäjän kiinni minun virhe. Anna minulle yksi sekunti. Kalahtaa. Sanotaan scanf-1.c. OK. Siellä mennään. Tarvitsen sitä. CS50 tunnus on eri kokoonpanoasetukset että suojella sinua itseäsi. Tarvitsin poistaa ne vuoteen käynnissä kalahtaa käsin tällä kertaa. Joten merkkijono kiitos. Aion mennä eteenpäin ja kirjoita suosikkini Hei maailma. OK, null. Se ei ole mitä olen kirjoittanut. Joten se osoitus jotain on vialla. Anna minun mennä eteenpäin ja kirjoita vuonna todella pitkä jono. Kiitos nolla ja en tiedä jos aion pystyä kaada. Kokeillaan hieman kopio liitä ja nähdä, jos tämä auttaa. Vain liittää paljon tätä. Se on varmasti isompi merkkijono kuin tavallisesti. Haluan vain todella kirjoittaa se. Ei. Perkele. Komento ei löytynyt. Joten se liity. Että koska olen liittänyt huonoja merkkejä, mutta tämä osoittautuu ei tule toimimaan. Kokeillaan vielä kerran, koska se on hauskempaa, jos me todella kaada. Katsotaanpa kirjoitan tätä ja nyt, olen menossa kopioida todella pitkä jono ja nyt katsotaanpas jos me voi kaataa tämä asia. Huomaan pois tiloja ja uusia linjoja ja puolipisteellä ja kaikki outoja merkkejä. Anna. Ja nyt verkko on vain oltava hitaasti. Pidin alhaalla Komento-V liian pitkä, selvästi. Perkele! Komento ei löytynyt. OK. No, kohta on kuitenkin seuraavat. Joten mitä todella tapahtuu on tähän julkilausumaan nieriää tähti puskuri rivillä 16? Joten mitä saan kun Julistan osoitin? Kaikki Saan on neljä tavulla nimeltään puskuri, mutta mitä sen sisällä hetkellä? Se on vain noin roskat arvo. Koska tahansa julistaa muuttuja C, se on vain joitakin roskat arvo, ja olemme alkaneet kompastua tätä todellisuutta. Nyt, kun sanon scanf, mennä tähän osoitteeseen ja laittaa mitä käyttäjä on. Jos käyttäjä on hei maailman, hyvin, mistä voin laittaa sen? Puskuri on roskaa arvo. Niin, että on ikään kuin nuoli joka on osoittaa ties minne. Ehkä se osoittaa täällä mieleeni. Ja niin kun käyttäjä nimikkeet Hello World, ohjelma yrittää laittaa string Hello World kenoviiva 0 että murikka muistia. Mutta suurella todennäköisyydellä, mutta selvästikään ole 100% todennäköisyydellä, tietokone tulee sitten kaatuu ohjelmaa, koska tämä ei ole muisti Olisin saa koskettaa. Joten lyhyt, tämä ohjelma on virheellinen täsmälleen tästä syystä. En pohjimmiltaan ole sitä, mitä? Mihin toimiin olen pois, aivan kuten me pois kanssa Binky ensimmäinen esimerkki? Joo? Yleisö: Muistin varaus? DAVID MALAN: Muistin varaus. En ole oikeastaan ​​myönnetty kaikki muisti merkkijono. Jotta voimme korjata tämän pari tapaa. Yksi, voimme pitää asiat yksinkertaisina ja itse asiassa, nyt olet menossa alkaa nähdä hämärtymisestä linjojen välillä, mitä matriisi on, mitä merkkijono on, mitä char tähti on, mitä joukko merkkiä on. Tässä toinen esimerkki johon jouset ja huomautus kaikki Olen tehnyt verkossa 16 on, sen sijaan että hän että puskuri tulee olemaan char tähti, osoitin kimpale muistia, Aion hyvin ennakoivasti antaa itseäni puskuri 16 merkkiä, ja itse asiassa, jos olet perehtynyt termillä puskurointia, luultavasti maailman videoita, jos video on puskurointi, puskurointi, puskurointi. No, mikä on yhteys täällä? No, Inside YouTube ja sisältä videonauhuriyhdistelmä yleensä on array joka on suurempi kuin 16. Se voi olla taulukon koko yhden megatavu, ehkä 10 megatavua, ja tuohon array ei selaimen ladata koko joukko tavua, koko joukko megatavua video, ja videosoitin, YouTuben tai kuka on, alkaa lukeminen tavua että jono, ja milloin tahansa nähdä sana puskurointi, puskurointi, se tarkoittaa, että pelaaja on mennyt loppuun, että jono. Verkko on niin hidasta, että se ei ole täytetään array enemmän tavua ja niin olet poissa bittiä näyttää käyttäjälle. Joten puskuri on osuva termi täällä että se on vain joukko, kimpale muistia. Ja tämä korjata sen koska se kääntyy pois että voit hoitaa taulukot ikään kuin ne ovat osoitteita, vaikka puskuri on vain symboli, se on merkkijono, puskuria, se on hyödyllinen minulle, ohjelmoija, voit siirtää sen nimi ympäri ikään kuin se olisi osoitin, ikään kuin se olivat osoite kimpale muistia 16 merkkiä. Niin se sanoa, voin kulkea scanf juuri tätä sanaa ja niin nyt, jos teen tätä ohjelmaa, tehdä scanf 2, piste slash scanf 2, ja kirjoita Hei maailma, Anna, että time-- Hmm, mitä tapahtui? String kiitos. Mitä tein väärin? Hei maailma, puskuri. Hei maailma. Ah, tiedän mitä se tekee. OK. Joten se lukee ylös kunnes ensimmäinen avaruudessa. Joten huijata vain hetken ja say Halusin vain kirjoittaa jotain todella pitkä kuin tämä on pitkä lause se on yksi, kaksi, kolme, neljä, viisi, kuusi, seitsemän, kahdeksan, yhdeksän, 10, 11, 12, 13, 14, 15, 16. OK. Se on todellakin pitkä lause. Joten tämä lause on pidempi kuin 16 merkkiä ja kun minä paina Enter, mitä tulee tapahtumaan? No, tässä tapauksessa tarina, olin julistanut puskuri todella on array 16 merkkiä valmis menemään. Joten yksi, kaksi, kolme, neljä, viisi, kuusi, seitsemän, kahdeksan, yhdeksän, 10, 11, 12, 13, 14, 15, 16. Niin 16 merkkiä, ja nyt, kun lukea jotain tällaista on pitkä lause, mitä tulee tapahtumaan on että aion lukea tässä on pitkä S-E-N-T-E-N-C-E-, lause. Joten tämä on tarkoituksella huono asia, että olen pitää kirjallisesti yli rajat minun array, rajojen minun puskuria. Saisin onnekas ja ohjelma pitää käynnissä ja välitä, mutta yleisesti ottaen, tämä todellakin kaataa ohjelman, ja se on bugi minun koodata hetki astun rajojen Kyseisen array, koska olen en tiedä jos se on väistämättä menossa kaatua tai jos olen juuri menossa onnekas. Joten tämä on ongelmallista, koska Tässä tapauksessa se ei näytä toimivan ja nyt uhmata kohtaloa täällä, vaikka IDE näyttää sietää melko vähän of-- Siellä mennään. Lopuksi. Joten olen ainoa, joka voi nähdä tämän. Joten Minulla oli hauskaa konekirjoitus ulos todella pitkä todellinen ilmaisu että se varmasti ylittänyt 16 tavua, koska olen kirjoitetaan tässä hullu pitkä multi-line lause, ja sitten huomaa, mitä tapahtui. Ohjelma yritti tulostaa sen ja sitten sai segmentointi vika ja segmentointi viat on kun jotain tällaista tapahtuu ja käyttöjärjestelmä sanoo ei, ei voi koskettaa, että muisti. Aiomme tappaa ohjelma kokonaan. Joten tämä vaikuttaa ongelmalliselta. Olen parantaneet ohjelman puitteissa ainakin joitakin muisti, mutta tämä näyttäisi rajoittaa toiminto GetString saada jouset joidenkin äärellinen pituus 16. Joten jos haluat tukea enää lauseita kuin 16 merkkiä, Mitä sinä teet? No, voit lisätä koko on puskurin 32 tai että tuntuu sellainen lyhyt. Miksemme vain tehdä se 1000 mutta työntää takaisin. Mikä vastaus intuitiivisesti ja vain välttää tämän ongelman tekemällä minun puskuri isompi, kuin 1000 merkkiä? Toteuttamalla GetString tällä tavalla. Mikä on hyvä tai huono täällä? Joo? Yleisö: Jos sitoa paljon tilaa ja et käytä sitä, niin et voi jakaa uudelleen, että tilaa. DAVID MALAN: Ehdottomasti. Se on tuhlaileva sikäli kuin jos et todella tarvitsevat 900 näistä tavua ja kuitenkin olet pyytänyt 1000 yhteensä muutenkin, olet vain kuluttaa enemmän muistia käyttäjän tietokoneessa kuin sinun täytyy, ja kun kaikki, jotkut olet jo kohdannut elämässä, että kun olet käynnissä paljon ohjelmia ja he syövät paljon muistia, tämä voi todella vaikuttaa suorituskykyyn ja käyttäjän kokemus tietokoneella. Niin, että sellainen laiska ratkaisun, varmasti, ja päinvastoin, se ei ole vain tuhlausta, mitä ongelma edelleen, vaikka saan puskuri 1000? Joo? Yleisö: merkkijono on pituus 1001. DAVID MALAN: Aivan. Jos merkkijono on pituus 1001, sinulla on täsmälleen sama ongelma, ja minun väite, olisin vain tee se 2000, mutta et tiedä etukäteen, kuinka suuri se olisi, ja vielä, minun on kääntää minun ohjelma ennen kerroit ihmiset käyttävät ja lataa se. Joten tämä on juuri sellainen kamaa että CS50 kirjasto yrittää auttaa meitä ja me vain silmäyksellä joitakin taustalla täytäntöönpanon täällä, mutta tämä on CS50 piste C. Tämä on tiedosto, joka on ollut CS50 IDE kaikki nämä viikot olet käyttänyt. Se on valmiiksi käännetty ja olet käyttänyt sitä automaattisesti luonteeltaan ottaa dash L CS50 lippu kanssa kalahtaa, mutta jos minä selaa läpi kaikki Näiden toimintojen, tässä on GetString, ja vain antaa sinulle maku mitä tapahtuu, sallikaa vilkaista monimutkaisuus. Se ei ole erittäin pitkä toiminto, mutta emme täytyy ajatella kaikki hartaasti miten edetä saada jouset. Joten tässä on minun puskuri ja minä ilmeisesti alustaa sen null. Tämä tietenkin on sama asia kuin char tähti, mutta päätin täytäntöönpanosta CS50 kirjasto että jos aiomme olla täysin dynaaminen, En tiedä etukäteen, kuinka suuri string käyttäjät ovat menossa halua saada. Joten aion aloittaa vain tyhjä merkkijono ja aion rakentaa niin paljon muistia kuin minun täytyy sovittaa käyttäjälle merkkijono ja jos minulla ei ole tarpeeksi, aion kysyä käyttöjärjestelmän enemmän muistia. Aion siirtää merkkijono isompi murikka muistia ja aion vapauttaa tai vapauttaa riittävän suuren osan muistia ja olemme juuri menossa tehdä tämän iteratiivisesti. Niin nopealla silmäyksellä, täällä on vain muuttuja jonka kanssa aion seurata kapasiteetin minun puskuria. Kuinka monta tavua voin mahdu? Tässä muuttujan n kanssa joka Aion pitää seuraa, kuinka monta tavua ovat todella puskuri tai siitä, että käyttäjä on kirjoittanut. Jos et ole nähnyt tätä ennen, te voi määrittää, että muuttuja kuin int on allekirjoitettu, joka kuten nimestä voi päätellä, tarkoittaa että se on ei-negatiivinen, ja miksi En koskaan halua vaivata täsmennetään että int ei ole vain int, mutta se on unsigned int? Se on ei-negatiivinen int. Mitä [äänetön] tarkoittaa? Yleisö: Se kuvailee määrä muistia voi olla [äänetön]. DAVID MALAN: Joo. Joten jos sanon allekirjoittamaton, tämä on todella antaa sinulle yksi vähän ylimääräistä muistia ja se tuntuu sellainen typerä, mutta jos on yksi vähän lisämuistia, että tarkoittaa olet kaksi kertaa niin paljon arvot voit edustaa, koska se voi olla 0 tai 1. Niin oletuksena, int voi olla karkeasti negatiivinen 2000000000 aina jopa positiivinen 2000000000. Ne ovat suuria alueita, mutta se on vielä sellainen tuhlausta jos vain välitä koot, joka vain intuitiivisesti pitäisi olla ei-negatiivinen tai positiivinen tai 0, hyvin sitten, miksi olet tuhlaa 2000000000 mahdolliset arvot negatiiviset luvut jos olet koskaan aio käyttää niitä? Joten sanomalla allekirjoittamaton, nyt minun int voi olla välillä 0 ja noin 4 miljardia euroa. Joten tässä on vain int C syistä emme päästä juuri nyt miksi se int sijasta of char, mutta tässä Käydyn mitä tapahtuu päälle, ja jotkut teistä voidaan käyttää, esimerkiksi, fgetc toiminto jopa PSET neljä tai sen jälkeen, näemme sen jälleen ongelma asettaa viisi, fgetc on mukavaa, koska kuten nimi sellainen, tavallaan arcanely ehdottaa, se on toiminto, saa hahmo ja niin, mitä pohjimmiltaan erilainen mitä teemme vuonna GetString ei emme käyttäen scanf samalla tavalla. Olemme vain hiipivät pitkin askel-askeleelta yli mitä käyttäjä on kirjoittanut, koska voimme aina jakaa yksi nieriä, ja niin voimme aina turvallisesti katso yksi char kerrallaan, ja taika alkaa tapahtua täällä. Aion selaa Keskellä tätä toimintoa vain esitellä lyhyesti tämän toiminnon. Aivan kuten on olemassa malloc funktio, siellä RealLOC toiminto jossa realloc avulla voit jakaa uudelleen kimpale muisti ja tehdä se isompi tai pienempi. Niin pitkän tarinan lyhyesti ja aalto minun käsi tänään, tietää, että mitä GetString tekee se on eräänlainen maagisesti kasvaa tai kutistuu puskuria käyttäjä nimikkeet hänen merkkijono. Joten jos käyttäjä kirjoittaa lyhyt merkkijono, tämä koodi vain jakaa tarpeeksi muisti sopivaksi merkkijono. Jos käyttäjä pitää kirjoittamisen kuten tein sen uudestaan ​​ja uudestaan ja taas, hyvin, jos puskurin aluksi tämä iso ja ohjelma ymmärtää, että Hetkinen, olen pois tilaa, se tulee kaksinkertaistaa puskurin koko ja sitten kaksinkertaiseksi puskurin ja koodi, jolla ei kaksinkertaistaminen, jos katsomme sen täällä, se on vain tämä fiksu sutkaus. Et ehkä ole nähnyt tätä syntaksin ennen, mutta jos sanot tähti vastaa, tämä on sama asia kuin sanomalla kapasiteetti kertaa 2. Joten se vain pitää kaksinkertaistaa kapasiteetti puskurin ja sitten kertoa realloc antaa siitä, että paljon enemmän muistia. Nyt, kun sivuun, siellä ovat muita toimintoja täällä että emme tutkia mitään yksityiskohtia muut kuin näkyä GetInt, käytämme GetString vuonna GetInt. Me tarkistamme, että se ei ole null, joka muistaa, on erityinen arvo, tarkoittaa jotain meni pieleen. Olemme muisti. Parempi tarkistaa, että. Ja palaamme Sentinel arvo. Mutta minä taipua kommentit siitä, miksi ja sitten käytämme tätä serkku scanf kutsui sscanf ja se osoittautuu että sscanf, tai merkkijono scanf, avulla voit katsomaan linjaa käyttäjä on kirjoitettu ja voit analysoida se olennaisesti ja mitä minä olen tekee täällä on kerron sscanf, analysoida mitä käyttäjä on kirjoitettu ja varmista% i, on kokonaisluku sitä, emmekä päästä tänään juuri siksi siellä on myös % C täällä, mutta pähkinänkuoressa mahdollistaa meitä havaita, jos käyttäjä on kirjoittanut jotain vale numeron jälkeen. Niin siitä syystä, että GetInt ja GetString kertoa yrittää uudelleen, yritä uudelleen, yritä uudelleen on, koska kaikki on että koodi olemme kirjoitettu, Se on eräänlainen katsomalla käyttäjän syöttää sen varmistamisessa, se on täysin numeerinen tai se on todellinen kelluva piste arvo tai vastaavan, riippuen siitä, mitä arvo toimiakseen käytät. Vau. OK. Se oli suupala mutta tässä on että syy meillä oli ne apupyörät päälle johtuu alimmalla tasolla, On vain niin paljon asioita, voi mennä vikaan, että halusimme ja ennaltaehkäisevästi käsitellä niitä asioita varmasti aikaisintaan viikon luokan, mutta nyt PSET neljä ja PSET viisi ja kuin sinä näet, että se on enemmän tykö sinua mutta myös olet enemmän pystyy ratkaista näitä erilaisia ​​ongelmia sinä itse. Kysyttävää GetString tai GetInt? Joo? Yleisö: Miksi kaksinkertainen kapasiteetti puskurin eikä vain kasvaa sen tarkka määrä? DAVID MALAN: Hyvä kysymys. Miksi me kaksinkertaistaa kapasiteetin puskurin vastakohtana vain lisätä sitä noin vakioarvo? Se oli suunnittelu päätös. Olemme juuri päättänyt, että koska se pyrkii olla vähän kallis ajan viisasta kysyä käyttöjärjestelmä muistin, emme halua päätyä joutumassa tilanne iso jousille että me pyysivät OS uudelleen ja uudelleen ja uudelleen ja uudelleen peräkkäin muistin. Joten me vain päättänyt, hieman mielivaltaisesti mutta toivomme kohtuudella, että, tiedätkö mitä, katsotaanpa yrittää mennä asioiden edelle ja vain pitää kaksinkertaistaa niin, että me minimoida kertaa Meidän täytyy soittaa malloc tai RealLOC, mutta yhteensä tuomio soittaa ilman tietäen mitä käyttäjät kannattaa kirjoittaa. Molemmat tavat voivat olla kyseenalainen. Luultavasti hyvä. Joten katsomaan pari Muiden haittavaikutuksia muistia, asioita, jotka voivat mennä pieleen ja työkaluja, joita voit käyttää kiinni tällaisia ​​virheitä. On käynyt ilmi kaikille teille, vaikka check50 ei ole kertonut sinulle niin paljon, on kirjallisesti buginen koodi vuodesta viikko yksi, vaikka kaikki check50 testit kulunut, ja vaikka sinä ja TF ovat super varmoja, että koodi toimii tarkoitetulla tavalla. Koodi on viallisista tai virheellinen, että te kaikki, käyttämään CS50 kirjasto, on vuotaa muistia. Olet pyytänyt käyttöjärjestelmä muistin useimmissa ohjelmissa olet kirjoittanut, mutta olet koskaan itse antanut sen takaisin. Olet kutsutaan GetString ja GetInt ja GetFloat, mutta GetString, olet koskaan kutsuta unGetString tai Anna String Takaisin tms, mutta olemme nähneet että GetString ei varata muistia Poiketen malloc tai tämän toiminto RealLOC, joka on vain hyvin samanlainen henki, ja vielä, olemme olleet pyytää käyttöjärjestelmä muisti ja muisti uudelleen ja uudelleen mutta koskaan antaa sitä takaisin. Nyt, syrjään, käy ilmi, että kun ohjelma sulkeutuu, kaikki muisti automaattisesti vapautuu. Joten se ei ollut valtava käsitellä. Se ei tule rikkoa IDE tai hidas asioita alas, mutta kun ohjelmat eivät yleensä vuotaa muistia ja ne käynnissä pitkään. Jos olet koskaan nähnyt tyhmä pikku rantapallo Mac OS tai tiimalasi Windows missä se on eräänlainen hidastaa tai ajatella tai ajattelu tai vain todella alkaa hidastuvan ryömiä, se hyvin mahdollisesti voisi olla tulos on muisti vuotaa. Ohjelmoijia jotka kirjoittivat ohjelmisto käytät pyytää käyttöjärjestelmä muistia muutaman minuutin välein, joka tunti. Mutta jos käytät ohjelmisto, vaikka se on minimoitu tietokoneen tunteja tai päiväkausia, saatat kysyä lisää ja lisää muisti ja koskaan todellisuudessa käyttävät sitä ja niin koodi saattaa olla, tai ohjelmat saattavat vuotaa muistia, ja jos alkaa vuotaa muistia, siellä on vähemmän muistia muiden ohjelmien, ja vaikutus on hidastaa kaiken alas. Nyt, tämä on ehdottomasti yksi kaikkein hirvittävät ohjelmat sinulla on mahdollisuuksia ajaa CS50 sikäli koska sen tuotanto on vieläkin esoteerinen kuin kalahtaa n tai tehdä tai jonkin komennon line ohjelmien olemme ajaa ennen, mutta onneksi, upotettu sen ulostulo on joitakin erittäin hyödyllisiä vinkkejä että on hyötyä joko PSET neljä tai varmasti PMääritä viisi. Joten Valgrind on työkalu , joita voidaan käyttää etsimään muistin vuotoja ohjelmaan. Se on suhteellisen helppo ajaa. Suoritat Valgrind ja sitten, jopa vaikka se on vähän verbose, dash viiva vuoto Tarkista vastaa täynnä, ja sitten piste kauttaviiva ja nimi ohjelman. Joten Valgrind sitten ajaa ohjelma ja aivan lopussa oman ohjelman käynnissä ennen kuin se sulkeutuu ja antaa sinulle toinen nopea, se tulee analysoida ohjelma, kun se on ollut käynnissä ja kertoa sinä vuotaa kaikki muisti ja vielä parempaa, Koskitko muisti että ei kuulu sinulle? Se voi saalis kaikkea, mutta se on aika hyvä kiinni useimmat asiat. Joten tässä on esimerkki minun jolla on ajettu Tämän ohjelman, jolla on ajettu valgrind, on ohjelma nimeltä muistia, ja aion korostaa rivit, jotka ovat lopulta kiinnostaa meitä. Joten on vielä enemmän häiriötekijöitä että olen poistettu liukumäki. Mutta haluan vain nähdä, mitä tämä ohjelma pystyy kertoa meille. Se pystyy kertoa meille asioita kuten virheellinen kirjoittavat koko 4. Toisin sanoen, jos kosket muisti, erityisesti 4 tavua muistia että sinun ei pitäisi olla, Valgrind voi kertoa. Virheellinen kirjoitus koko 4. Kosketit neljä tavua että sinun ei pitäisi olla. Missä teit tuon? Tämä on kauneus. Muisti piste C linja 21 on silloin, kun mokasi ja siksi se on hyödyllistä. Aivan kuten GDB, se voi auttaa kohta sinua todellinen virhe. Nyt, tämä on hieman verbose, jos ei sekava. 40 tavua 1 lohkot ovat ehdottomasti hävisi tappio ennätys 1 1. Mitä se tarkoittaa? No, se vain tarkoittaa pyysit 40 tavua ja et koskaan antanut sitä takaisin. Soitit malloc tai soitit GetString ja käyttöjärjestelmä antoi sinulle 40 tavua, mutta et koskaan vapautettu tai vapautetaan, että muisti, ja olla oikeudenmukainen, olemme koskaan näytä miten antaa takaisin muistiin. Osoittautuu olemassa Super yksinkertainen funktio kutsutaan vapaaksi. Ottaa yhden argumentin, asia haluat vapauttaa tai antaa takaisin, mutta 40 tavua, ilmeisesti, tässä ohjelmassa on menetetty rivillä 20 muistia piste C. Joten katso tätä ohjelmaa. Se on erittäin hyödytön. Se vain osoittaa tässä virhe. Joten katsomaan. Tässä on tärkein ja tärkein, huomautus, puhelut toiminto nimeltään f ja sitten palaa. Joten kaikki, että mielenkiintoinen. Mitä f tekee? Huomaa, en vaivaudu kanssa prototyyppi. Halusin pitää koodi mahdollisimman vähäiset. Joten laitoin f edellä tärkein ja se on hieno, varmasti, lyhyitä ohjelmia, kuten tämä. Joten f ei palaa mitään ja tekee ei ota mitään, mutta se ei tee tätä. Se julistaa, aivan kuten vuonna Binky esimerkissä, osoitin nimeltään x että menee tallentaa osoitteen int. Niin, että vasemmalla puolella. Englanti, mikä on oikea puoli tekee? Kukaan? Mitä tämä tekee meille? Joo? Yleisö: [äänetön] kertaa koko int joka on 10 kertaa, että [äänetön] DAVID MALAN: Hyvä ja haluan tiivistää. Joten varata tarpeeksi tilaa 10 kokonaislukuja tai 10, mikä on koko int, se on neljä tavua, joten 10 kertaa 4 on 40, niin että oikea puoli, että olen korostettu on antaa minulle 40 tavua ja tallentaa osoitteen ensimmäisen tavun osaksi X. Ja nyt lopuksi, ja tässä tarina tämä ohjelma on buginen, mitä vikaa linja 21 perustuu että logiikka? Mitä vikaa linja 21? Joo? Yleisö: Et voi indeksinä x [kuultavissa]. DAVID MALAN: Joo. Minun ei pitäisi indeksinä x niin. Niin syntaktisesti, se on OK. Mitä mukavaa on, aivan kuten sinä voi hoitaa nimi array ikään kuin se on osoitin, samoin voit käsitellä osoittimen kuin se on array, ja niin voin syntaktisesti sanoa X kiinnike jotain, X teline i, mutta 10 on ongelmallinen. Miksi? Yleisö: Koska se ei sisällä. DAVID MALAN: Se ei ole sisällä että murikka muistia. Mikä on suurin arvo minun pitäisi laittamalla näissä hakasulkeissa? 9, 0 kautta 9. Koska nolla indeksointi. Joten 0 kautta 9 olisi hienoa. Kiinnike 10 ei ole hyvä ja mutta, muistuttaa kuitenkin, joka kerta En tahdo yrittää tehdä CS50 IDE Crash kirjoittamalla väärä arvoja, se ei aina yhteistyötä, ja todellakin, usein onnekas vain siksi Käyttöjärjestelmä ei huomaat koskaan niin hieman siirtää joitakin kimpale muistia, koska Oletko yöpynyt sisällä teknisesti segmentille, mutta siitä lisää vuonna käyttöjärjestelmien luokka, ja niin jotain tällaista voisi hyvin helposti mennä huomaamatta. Ohjelmasi ei ikinä kaatumaan johdonmukaisesti mutta ehkä silloin tällöin. Ja niin yritetään valgrind Tämän, ja tässä jossa me hukkua lähdön hetkellisesti. Joten muisti valgrind vuotaa Tarkista vastaa koko piste slash muisti. Ja tästä syystä Lupaan tämä hukuttaa. Tässä mitä valgrind, tässä mitä ohjelmoija, joitakin vuosia avarien päättänyt, että olisi hyvä idea tuotoksen näyttää. Joten järkeä tämän. Joten kaikki tavoin vasen puoli ilman hyvää syytä on prosessi ID ohjelman me vain ajaa, yksilöllinen tunniste Ohjelman me loppui juuri. Poistimme että vuodesta dia, mutta siellä on joitakin hyödyllisiä tietoja täällä. Katsotaanpa selaamalla ylös hyvin alkuun. Tässä kun aloitimme. Joten se ei ole kovin paljon teho. Tässä että virheellinen kirjoittaa koosta 4 rivillä 21. No, mikä oli linja 21? Rivi 21 oli täsmälleen tämä ja se on järkevää että olen pätevästi kirjallisesti 4 tavua, koska olen yrittää laittaa tämän kokonaisluku, joka voisi olla mitään, se vain sattuu olemaan nolla, mutta yritän laittaa sen sijainti joka ei kuulu minulle. Lisäksi täällä, 40 tavua yhdessä lohkot ovat varmasti menetetään ennätys 1. Tämä johtuu siitä, kun soitan malloc täällä, en koskaan todella vapaa muisti. Joten kuinka voimme korjata tämän? Anna minun mennä eteenpäin ja olla hieman turvallisempi ja tehdä 9 siellä ja haluaisin tästä ilmaiseksi x. Tämä on uusi toiminto tänään. Jos minä nyt uusintana tehdä muisti piste slash, Katsotaanpa ajaa valgrind sitä uudelleen, maksimoida minun ikkuna ja paina Enter. Nyt, se on hyvä. He haudata hyvä uutinen kaikissa tämän tuotoksen. Kaikki pino lohkot olivat vapaat. Tulemme takaisin mitä kasaan on, mutta ei vuotoja ovat mahdollisia. Joten tämä on vain yksi työkalu työkalusarja jolla voit alkaa löytää nyt virheitä, kuten että. Mutta katsotaanpa mitä lisää voi mennä pieleen. Katsotaanpa siirtyminen nyt todella ratkaista ongelman. Sivuhuomautuksena, jos tämä lievittää hieman sekaannusta tai jännitystä, tämä on nyt hauska. Joo. Se on aika hyvä. Koska osoittimet ovat osoitteet ja osoitteet ovat yleensä sopimuksen mukaan kirjoitettu heksadesimaalimuodossa. Ha, ha, tämä on hauska nyt. Oli miten oli, joten katsotaanpa nyt todella ratkaista ongelman. Tämä on ollut erittäin, Super matalan tason toistaiseksi, ja voimme todella tehdä hyödyllinen asioita nämä matalan tason tiedot. Joten otimme käyttöön muutaman viikon sitten käsite array. Array oli mukavaa, koska on vaikea puhdistaa meidän koodi koska jos halusimme kirjoittaa ohjelma useita opiskelijoita tai useampia nimiä ja taloja ja asuntoloissa ja korkeakoulujen ja kaikki tämä, voisimme tallentaa kaiken enemmän siististi sisällä array. Mutta ehdottaa yhtä haittapuoli array toistaiseksi. Vaikka et ole kärsinyt itse ohjelmassa, vain vaistomaisesti, mikä on huono asia noin array, kenties? Kuulen joidenkin sivuääniä. Yleisö: On vaikeaa muuttaa kokoa. DAVID MALAN: Vaikea muuttaa kokoa. Et voi muuttaa kokoa array, itse asiassa, sinänsä C. Voit jakaa toisen array, siirtää kaiken vanhan uuteen, ja nyt on ylimääräistä tilaa, mutta se ei ole kuin kieli kuten Java tai Python tai useita muita kielet, jolla jotkut teistä saattaa olla tuttu, jos olet voi vain pitää lisäämällä asiat kyllästymiseen loppuun array. Kun sinulla on joukko koko 6, joka on sen koko, ja niin paljon kuin ajatus aikaisemmin jonka puskuri tietyn koon, sinun täytyy arvata ulos portista mitä kokoa haluat sen olevan? Jos arvaa liian iso, olet tuhlaa tilaa. Jos arvaa liian pieni, sinun voi tallentaa että tiedot, ainakin ilman paljon enemmän työtä. Joten tänään, kiitos osoittimia, voimme Aloita ompelemalla yhteen meidän omia tietorakenteita, ja Itse asiassa tässä on jotain joka näyttää hieman enemmän arvoituksellinen ensi silmäyksellä, mutta tämä on mitä me kutsumme liittyy luettelosta, ja sen nimi sellainen on yhteenveto se. Se on luettelo numeroita, tai Tässä tapauksessa listan numeroita, mutta se voisi olla luettelon mitään, mutta se toisiinsa tavalla nuolet, ja ota arvaus mitä tekniikkaa aiomme pystyä pistellä yhdessä, tavallaan kuin popcornia kanssa kierre, linkitettyjen listojen suorakulmioita täällä? Sen numerot? Mikä taustalla kieli ominaisuus? Yleisö: osoitin. DAVID MALAN: osoitin. Joten jokainen näistä nuolet täällä edustaa osoitin tai vain osoite. Eli toisin sanoen, jos haluan tallentaa listan numeroita, En voi vain tallentaa se jos haluan kykyä kasvaa ja kutistua tietoni rakenne array. Joten minun täytyy olla vähän enemmän hienostuneisuutta, mutta huomaa, että tämä kuva eräänlainen ehdottaa että jos olet juuri vähän viestiketjut yhdistää kaiken yhdessä, luultavasti ei ole niin vaikea tehdä tilaa välissä kaksi näistä suorakulmioita tai kaksi näistä solmuja, kuten aloitamme kutsumalla heitä, laittaa uusi solmu, ja sitten joitakin uusia kierre, vain oja kolme solmua yhdessä, ensimmäinen, viimeinen, ja yksi että juuri työnnetty keskelle. Ja todellakin linkitetty lista, toisin array, on dynaaminen. Se voi kasvaa ja se voi kutistua ja et täytyy tietää tai välitä etukäteen, miten paljon tietoa aiot olla varastoinnin, mutta se osoittautuu meidän on oltava hieman varovainen miten toteuttaa tämä. Joten Katsotaanpa ensin miettiä, miten toteutamme yhden näistä pienistä suorakulmioita. Se on helppo toteuttaa int. Sanoit int n ja sitten saat 4 tavua varten int, mutta miten saan int, kutsuvat sitä n, ja sitten osoitin, kutsukaamme sitä seuraava. Voisimme kutsua näitä asiat mitä haluamme mutta tarvitsen mukautetun tietorakennetta. Joo? Yleisö: Ampersand [äänetön]. DAVID MALAN: Joten Ampersand aiomme käyttää saada osoitteen solmun mahdollisesti. Mutta tarvitsemme toisen piirre C, jotta antaa minulle mahdollisuuden luoda Tämä tapa suorakulmio, tämä custom muuttuja jos haluatte, muistiin. Yleisö: struct. DAVID MALAN: struct. Recall viime viikolla, esittelimme struct, tämä suhteellisen yksinkertainen avainsanan jonka avulla meitä tekemään asioita, kuten tämä. C ei tullut tiedot rakenne kutsutaan opiskelija. Sen mukana tulee int ja kellua ja nieriää ja kuten, mutta se ei tule opiskelija, mutta voimme luoda opiskelija tietotyyppi, opiskelija rakenne, tällä syntaksilla täällä. Ja näet tämän uudestaan ​​ja uudestaan. Joten älä ole huolissasi ulkoa avainsanoja, mutta avainsanan, joka on tärkeää on juuri siitä, että sanoimme struct ja sitten kutsuimme opiskelija ja sisällä Opiskelijan oli nimi ja talon tai asuntolan tai vastaavaa. Ja nyt tänään, nyt ehdottaa tätä. Olen lisännyt muutaman sanan, mutta jos haluan toteuttaa tämän suorakulmion se sai sekä int ja osoitin, tiedätkö mitä, minä olen menossa julistaa struct kutsutaan solmu. Olen myös, sen sisälle, aikoo sanoa että solmu, tämä suorakulmio, on int ja me kutsumme sitä n ja sillä on seuraava osoitin. Ja tämä on hieman verbose, mutta jos ajattelee sitä, nuolet, jotka olivat kuva hetki sitten ovat, mitä tietoja tyyppi? Kun nämä molemmat nuolet osoittaa millaista tietojen rakenne? Se ei osoita vain int sinänsä. Se osoittaa koko suorakulmainen juttu ja että suorakulmainen asia, sanoimme, kutsutaan solmu. Ja niin me tavallaan on rekursiivisesti määritellä tästä niin että solmu, me sanomme, sisältää int nimeltään n ja osoitin sanottujen seuraavan ja millaisia ​​tietoja rakenteesta, johon että osoitin on ilmeisesti olemaan struct solmu. Joten tämä on ärsyttävän monisanainen ja vain olla pikkumainen, miksi emme voi vain sanoa, mikä rehellisesti näyttää paljon enemmän luettavissa, johtuu muistuttaa, että C lukea asioita ylhäältä alas, vasemmalta oikealle. Se ei ole kunnes saamme puolipiste että avainsana solmu todella on olemassa. Joten jos haluamme olla tällainen syklinen viittaus sisällä tietoja rakenne, meidän täytyy tehdä tämä, jos sanomme struct solmu huipulla, joka antaa meille enää tapa kuvata tätä asia, sitten sisällä sanomme struct solmu, ja sitten aivan viimeinen rivi sanomme, kaikki hyvin, C, muuten, vain soittaa tämä koko hemmetin asia solmu ja lopettaa hakusanalla struct kokonaan. Joten tämä on vain eräänlainen syntaktisten temppu, joka lopulta antaa meidän luoda jotain, joka näyttää täsmälleen samalta kuin tämä. Joten jos oletamme nyt voimme toteuttaa tämä asia C, miten me oikeastaan aloittaa liikkumisesta tämä? No, itse asiassa, meidän täytyy tehdä, on kerrata vasemmalta oikealle ja vain Tällainen lisätä solmuja tai poistaa solmut tai etsiä asioita minne haluamme, mutta tehdä tämän, mennään eteenpäin ja tehdä asiat hieman todellista, koska tämä on ollut erittäin matalan tason toistaiseksi. Onko joku kirjaimellisesti haluaisi olla ensimmäinen? OK. Tule ylös. Mikä on nimesi? DAVID: David. DAVID MALAN: David. Kiva tavata. Minä myös. Selvä. Ja tarvitsemme numero 9. Ei niin hyvä kuin ensimmäinen, ehkä. OK, numero 9. Numero 17, kiitos. Anna minun mennä takaisin hieman kauempana. Numero 22, kiitos, ja entä kauemmas taaksepäin jos näen käsiä kaikki valo tai ei. Joku on vapaaehtoinen oikeassa. Haluatko keksiä? Kyynärvarresta on väkisin menossa ylös. OK, 17. 22. 26 on tulossa alas. Onko kukaan muu haluatko forcefully-- Tule ylös. Varsinainen vapaaehtoinen. Niin hyvin nopeasti, jos te voisi järjestää itsenne aivan kuten solmut ruudulla. Kiitos. Ja voit olla 26. Hyvä ja nopea esittelyt. Joten olen Daavidin ja olet myös? DAVID: David. DAVID MALAN: Ja sinä olet? JAKE: Jake. SUE: Sue. ALEX: Alex. RAPHAEL: Raphael. TAYLOR: Taylor. DAVID MALAN: Taylor. Erinomainen. Joten nämä ovat vapaaehtoisia tänään ja mennä eteenpäin ja siirtää vähän, että tapa, ja vain mennä eteenpäin ja pitää tilalla numerot kuin olet tai ensimmäinen merkki ja vasemmalla kädellä, mennä eteenpäin ja vain toteuttaa nämä nuolet, vain niin, että vasen käsi on kirjaimellisesti osoittamalla mitä pitäisi kohta klo, ja anna itsellesi tilaa niin, että voimme visuaalisesti nähdä kädet todella osoittaa, ja voit vain pisteen tavallaan on maa on hieno. Joten tässä meillä on linkitetty lista yhden, kaksi, kolme, neljä, viisi solmua aluksi, ja huomaat meillä on tämä erityinen osoitin alussa kuka avain koska meillä on seurata Koko pituudeltaan lista jotenkin. Nämä kaverit, vaikka he jäljellä oikealle, takaisin takaisin muistiin, he voivat itse olla missä tahansa tietokoneen muistiin. Joten nämä kaverit voivat olla seisoo tahansa vaiheessa ja se on hieno, kunhan ne ovat todella suunnattu toisiaan, mutta pitää asiat puhdas ja yksinkertainen, käymme vain vetää ne vasemmalta oikealle kuten tämä, mutta voisi olla massiivinen aukkoja välillä näiden solmujen. Nyt, jos haluan todella lisätä joitakin uusi arvo, mennään eteenpäin ja tehdä tämän. Meillä on nyt tilaisuus valita toiseen solmuun. Sano nyt alkajaisiksi mallocing 55. Voisiko joku pahaksesi malloc? OK, tule ylös. Mikä on nimesi? RAINBOW: Rainbow. DAVID MALAN: Rainbow? Selvä. Malloc Rainbow. Tule ylös. Joten nyt meidän on kysyttävä itseltämme algoritmisesti jossa voimme laittaa 55. Joten me kaikki tiedämme, tietenkin, jossa hän luultavasti kuuluu jos me yritämme pitää tämä lajitellaan ja jos te voisi ottaa yhden askel taaksepäin joten emme putoa vaiheessa, että olisi hienoa. Joten oikeastaan, Rainbow, aloittaa täällä kanssani, koska me tietokoneen nyt voi näkevät vain yksi muuttuja kerrallaan. Joten jos tämä on ensimmäinen solmu. Huomaa, hän ei ole solmu, hän on vain osoitin, ja siksi hän vetoa olla vain koko osoittimen, ei yksi niistä koko suorakulmioita. Joten aiomme tarkistaa jokaisen iterointia on 55 vähemmän kuin 9? Ei. On 55 vähemmän kuin 17? Ei. Alle 22? Alle 26? Alle 34? Ja niin nyt, ilmeisesti Rainbow kuuluu lopussa. Joten oltava selkeä, ja mitä oli nimesi, Taylor? TAYLOR: Taylor. DAVID MALAN: Joten keskuudessa Taylorin vasemmalla ja Rainbow kädet täällä, jonka käsi on osoitat mitä velvoittaa lisätä 55 tähän luetteloon? Mitä meidän pitää tehdä? Joo? Yleisö: Taylorin käsi on kohtaan vasemmalle. DAVID MALAN: Aivan. Joten lisäämällä solmu osaksi listan loppuun on melko yksinkertainen, koska Taylor vain on kohtaan, eikä maata kohti tai me kutsumme sitä null, null on eräänlainen puuttuessa osoittimen tai erityinen nolla osoitin, olet menossa kohta vasemmalla käsi Rainbow ja sitten Rainbow, Missä vasenta käytetyt luultavasti kohta? Alas. Se ei ole hyvä, jos hänen kätensä on eräänlainen ja osoittaa tehoilla tai lajitella tahansa millä tavalla. Se olisi otettava huomioon roskat arvo, mutta jos hän osoittaa jotkut tunnettu arvo käymme kutsuvat sitä nolla tai nolla, se on OK koska meillä on termi tässä ja tiedämme luettelo on nyt valmis. Niin mitä toinen suhteellisen yksinkertainen tapaus? Voisimmeko malloc 5? Tule ylös. Mikä on nimesi? TIFFANY: Tiffany. DAVID MALAN: Anteeksi? TIFFANY: Tiffany. DAVID MALAN: Tiffany. Selvä. Tiffany on malloced arvolla 5. Tule ylös. Tämä on suhteellisen helppoa myös, mutta Tarkastellaan järjestystä toiminnan nyt. Se oli melko helppo Taylor lopussa. Numero 5 on tietenkin pienempi kuin 9, ja niin meillä on David, olemme Tiffany, ja mikä oli nimesi? JAKE: Jake. DAVID MALAN: Jake. Tiffany, Jake, David. Jonka käsi olisi päivitettävä ensin? Mitä haluat tehdä täällä? On pari mahdollisuuksia, mutta siellä on myös yksi tai useampi väärä tavalla. Yleisö: Aloita vasemmassa reunassa. DAVID MALAN: Aloita vasemmanpuoleisin. Kuka vasemmanpuoleisin täällä sitten? Yleisö: Ensimmäinen. DAVID MALAN: OK. Joten aloittaa ensimmäisen ja missä sinä haluat päivittää Daavidin käsiin olla? Yleisö: Kohti 5. DAVID MALAN: OK. Daavid, piste viisi tai Tiffany täällä, ja nyt? Yleisö: Tiffany viittaa 9? DAVID MALAN: Perfect, paitsi Binky n johtaja juuri sellainen putosi, eikö? Koska mitä vikaa tämä kuva kirjaimellisesti? Yleisö: Mitään ei osoittaa. DAVID MALAN: Mikään ei ole osoittaa Jake nyt. Olemme kirjaimellisesti orvoksi 9 ja 17, ja olemme kirjaimellisesti vuotanut kaikki tämä muisti, koska mukaan päivittäminen Davidin käden ensimmäinen, joka on hieno sikäli kuin se on oikein osoittaen Tiffany nyt, mutta jos kukaan ei ollut kaukokatseisuutta osoitat Jake, sitten olemme menettäneet kokonaisuudessaan tähän luetteloon. Joten kumota. Joten se oli hyvä asia kompastua mutta nyt korjata nyt. Mitä meidän pitäisi tehdä ensin sen sijaan? Joo? Yleisö: Tiffany olisi piste 9? DAVID MALAN: En voi saada, että lähellä sinua. Kenen pitäisi piste 9? Yleisö: Tiffany. DAVID MALAN: Selvä. Joten Tiffany ensimmäiseksi pisteen 9. Joten Tiffany olisi otettava on sama arvo David, joka näyttää tarpeeton hetkeksi, mutta se on hieno koska nyt, toinen vaihe, voimme päivittää Davidin käden pisteeseen Tiffany, ja sitten jos me juuri sellainen puhdas asioita ikään kuin tämä on tavallaan keväinen, nyt se oikea asennus. Niin erinomainen. Joten nyt olemme melkein perillä. Katsotaanpa aseta yksi lopullinen arvo kuin arvo 20. Jos voisimme malloc yksi lopullinen vapaaehtoinen? Tule ylös. Joten tämä on hieman mutkikkaampi. Mutta oikeasti, koodi olemme kirjallisesti, vaikkakin suullisesti, on aivan kuin ottaa nippu ja jos olosuhteet nyt, eikö? Meillä oli kunnossa tarkistaa, jos se kuuluu lopussa, ehkä alussa. Tarvitsemme jonkinlaisen silmukan löytää paikka keskellä. Joten tehdä, että mikä on nimesi? ERIC: Eric. DAVID MALAN: Eric? Eric. Kiva tavata. Joten meillä on 20. Alle viisi? Ei. Alle yhdeksän? Ei. Alle 17? Ei. OK. Hän kuuluu tässä ja teidän nimenne taas ovat? SUE: Sue. DAVID MALAN: Sue. ALEX: Alex. DAVID MALAN: Sue, Alex, ja? ERIC: Eric. DAVID MALAN: Eric. Joiden kädet täytyy saada päivitetään ensin? Yleisö: Eric. OK. Joten Ericin olisi osoitat missä? 22. Hyvä. Ja nyt, mitä seuraavaksi? Sue voi sitten piste Eric ja nyt, jos te vain tehdä joitakin huone, joka on hieno visuaalisesti, nyt olemme tehneet lisäys. Joten nyt käsittelemään kysymystä mutta Kiitos paljon meidän vapaaehtoisille. Erittäin hyvin tehty. Voit pitää ne, jos haluat. Ja meillä on kaunis jakaus lahja, jos haluat jokaisen haluavat viedä stressipallo. Haluan vain välittää tämän alas. Joten mikä on takeaway tämän? Tämä näyttää olevan hämmästyttävä sikäli kuin meillä on nyt esitteli vaihtoehto array, joka ei ole niin rajoitu array noin kiinteä koko. Ne voivat kasvaa dynaamisesti. Mutta aivan kuten olemme nähneet viikkoa Aiemmin emme koskaan saa mitään ilmaiseksi, kuten varmasti siellä kauppaa tehoilla. Joten ylösalaisin liittyy lista, on tämä dynaamisuus? Tämä kyky kasvaa ja rehellisesti, olisimme voineet tehdä delete ja voisimme kutistua tarpeen mukaan. Minkä hinnan maksamme? Kaksi kertaa niin paljon tilaa, ensiksi. Jos katsot kuvaa, ei enää olen tallentamiseksi kokonaislukujen lista. Olen tallentamiseen luettelo kokonaislukuja plus viitteitä. Joten olen kaksinkertaistaa määrä tilaa. Nyt, ehkä se ei ole niin iso juttu 4 tavua, 8 tavua, mutta se voi varmasti lisätä up suuria tietomääriä. Mikä on toinen haittapuoli? Joo? Yleisö: Meidän on kulkevat ne yksi kerrallaan. DAVID MALAN: Joo. Meidän on kuljettava niitä yksi kerrallaan. Tiedätkö mitä, luovuimme super kätevä ominaisuus hakasulkeen merkintä, oikeammin tunnettu random access, jossa voimme vain hypätä yksittäiselle elementin mutta nyt jos minulla oli vielä minun vapaaehtoisia täällä, jos halusin löytää numero 22, en voi vain hypätä kannatin jotain jotain. Minun täytyy käydä läpi lista, paljon kuten meidän haku esimerkkejä lineaarisesti, löytää numero 22. Joten me näytämme ovat maksaneet siellä. Mutta voimme silti ratkaista muita ongelmia. Itse asiassa, haluan esitellä vain pari grafiikka. Joten jos olet ollut alas Mather ruokasalissa äskettäin, voit muistaa, että niiden pinot tarjottimia näin, me lainattu nämä maasta Annenberg ennen luokan. Joten tämä pino tarjottimia, vaikka, on tyypillinen todella Tietokoneen tietoarkisto rakenne. On tietorakenne tietotekniikassa tunnetaan pino joka hyvin kauniisti omiaan juuri tämä visuaalinen. Joten jos jokainen näistä lokerot eivät ole tarjotin mutta kuten numero ja halusin tallentaa numeroita, I voisi laittaa yksi tänne, ja voisin laittaa toinen tänne, ja jatkaa pinoaminen numerot päällekkäin toisen, ja mitä suotuisia tästä on, että mitä vaikutuksia Näiden tietojen rakenne? Joka määrä voi vetää ulos ensimmäinen kätevimmin? Viimeksi yksi laittaa siellä. Joten tämä on mitä me kutsuisi tietojenkäsittelytiede LIFO tietorakennetta. Last in, first out. Ja näemme ennen pitkää miksi että voisi olla hyödyllistä, mutta nyt, vain pitävät omaisuutta. Ja se on typerää, jos luulet, miten ruokasalissa tekee sen. Joka kerta he puhdas tarjottimia ja laittaa tuoreimmat niitä päälle, sinulla voisi olla aiemmin puhdas mutta lopulta hyvin likainen ja pölyinen lokero alareunassa jos et koskaan todella saada pohjaan kyseisen pino, koska juuri sysäämään uuden ja puhtaisiin sen päälle. Sama voi tapahtua supermarket liian. Jos sinulla on vitriinissä maidon ja joka kerta CVS tai kuka saa enemmän maitoa, juuri työntää maidot sinulla on jo taakse ja laitat uusia edessä, olet menossa on joitakin melko kurja maito lopussa tietorakenteen, koska se on aina alareunassa tai vastaavasti se on aina takana. Mutta on toinen tapa ajatella riviin tiedot ja esimerkiksi tämä. Jos olet yksi niistä ihmisistä, jotka tykkää riviin ulkopuolella Applen myymälöissä kun uusi tuote tulee ulos, olet luultavasti ei käytä pino tiedot rakenne koska olet vieraannuttaisi kaikkia muita, jotka on vuori jopa ostaa joitakin uusia lelu. Pikemminkin, olet luultavasti käyttäen millaisia ​​tietoja rakenne tai millainen järjestelmä todellisessa maailmassa? Toivottavasti se linja, tai enemmän asianmukaisesti tai enemmän Britannian kaltainen, jono. Ja käy ilmi, jono on myös tietorakenne tietotekniikassa, mutta jono on hyvin eri omaisuutta. Se ei ole LIFO. Last in, first out. Jumala varjelkoon. Se on sen sijaan FIFO. Ensimmäinen sisällä ensimmäinen ulkona. Ja se on hyvä asia oikeudenmukaisuuden "vuoksi varmasti kun olet vuori up Super aikaisin aamulla. Jos sinne ensin, sinua haluavat saada ensin samoin. Ja niin kaikki nämä tiedot rakenteet, jonot ja pinot ja rypäleterttuja muiden osoittautuu sinua voi ajatella tätä vain array. Tämä on joukko, ehkä kiinteä koko 4, mutta se would olla sellainen kiva jos voisimme vain kasa tarjottimet lähes äärettömän pitkä jos me on, että monta lokeroa tai numeroita. Joten ehkä haluamme Käytä linkitetty lista täällä, mutta kompromissi tulee olemaan mahdollisesti, että tarvitsemme enemmän muistia, vie hieman enemmän aikaa, mutta meidän eivät rajoita pinon korkeus, aivan kuten Mather: n vitriinissä saattaa rajoittaa koko pinon, ja niin nämä ovat suunnittelun päätöksiä tai vaihtoehtoja meille lopulta. Joten nämä tiedot rakenteet, olemme aloittaneet nähdä uusia ylärajan mahdollisesti mitä aiemmin oli huippunopea ja jos jätämme pois tänään ja missä me toivoa päästä on keskiviikko, käymme alkaa tarkastella tietoja rakenne, joka antaa meidän etsi kautta tietoja tukin päättymisaika uudelleen. Ja näimme, että muistatte, viikolla nolla ja yksi binäärihaku tai jakaa ja valloittaa. Se tulee takaisin ja vielä parempaa, pyhä Graal tänä keskiviikkona on keksiä tietorakenne, joka toimii aidosti tai teoreettisesti vakio aika, jolloin sillä ei ole väliä kuinka monta miljoonia tai miljardeja asioita meillä tietorakenteessa, se vie meidät vakio aikaa, ehkä yksi askel tai kaksi askelta tai 10 askelta, mutta jatkuva numerot vaiheet etsiä tietojen rakenne. Se todellakin on pyhä Graal mutta siitä lisää keskiviikkona. Nähdään sitten. [Musiikkia]