[Musiikki soi]
DAVID J. MALAN: Okei.
Tämä on CS50.
Tämä on viikolla viisi jatkui, ja me on hyviä uutisia ja huonoja uutisia.
Niin hyvä uutinen on, että CS50 lanseeraa tänä perjantaina.
Jos haluat liittyä meihin, suunnata tavallista URL-osoite tähän.
Vielä parempi uutinen, ei luentoa Ensi maanantaina 13. päivä.
Hieman vähemmän parempi uutinen, tietokilpailu nolla on ensi keskiviikkona.
Lisätietoja saa löytää tähän URL-osoite tähän.
Ja parin seuraavan päivän me voidaan täydentäviä tehtäviä
suhteen huoneita että olemme pidätetään.
Parempi uutinen on, että siellä tulee olla kurssin laajuinen tarkastelu
istunto tulevana Maanantaina illalla.
Pysy kuulolla kurssin verkkosivuilla sijainti ja yksityiskohdat.
Kohdat, vaikka se on loma, tapaa myös samoin.
Paras uutinen, luento ensi perjantaina.
Joten tämä on perinne meillä on, kuten per oppimäärän.
Vain-- se tulee olemaan mahtavaa.
Näet asioita, kuten vakioaikavälein tietorakenteita
ja hash taulukoita ja puita ja yrittää.
Ja me puhumme syntymäpäivä ongelmia.
Läjän tavaraa odottaa ensi perjantaina.
OK.
Oli miten oli.
>> Niin muistaa, että olemme olleet Keskityn tähän kuvan siitä, mitä on
sisällä myös tietokoneen muistiin.
Joten muistin tai RAM on, jos ohjelmat olemassa, kun käytät niitä.
Jos kaksoisnapsautat ikoni ajaa jotain ohjelmaa
tai kaksoisnapsauta kuvake avaa joitakin tiedosto,
se ladataan kiintolevyn ajaa tai SSD-asemalla
RAM, Random Access Memory, jossa se elää kunnes virta katkeaa,
kannettavan tietokoneen kansi suljetaan, tai lopetat ohjelman.
>> Nyt kun muisti, ja joka luultavasti on
1 gigatavu näinä päivinä, 2 gigatavua, tai jopa enemmän,
on yleensä vahvistetut tietyn ohjelman
tämäntyyppiseen suorakaiteen käsitteellinen malli
jolloin meillä on pino alareunassa ja joukko muita juttuja yläreunassa.
Asia huipulla olemme nähneet tätä kuvaa
ennen mutta ei koskaan puhunut on ns tekstin segmentin.
Teksti segmentti on vain hieno tapa sanoa nollia ja ykkösiä, että
säveltää todellista käännetty ohjelma.
>> Joten kun kaksoisnapsautat Microsoft Word Macin tai PC: n,
tai kun suoritetaan piste slash Mario Linux-tietokone teidän pääteikkunaa
nollia ja ykkösiä, jotka muodostavat Sana tai Mario varastoidaan väliaikaisesti
tietokoneen RAM ns tekstisegmentin tietyn ohjelman.
Alla, että menee alustettu ja alustamatonta tiedot.
Tämä on tavaraa kuten globaaleja muuttujia, että emme ole käytetty monia,
mutta toisinaan olemme oli yleismuuttujat
tai staattisesti määrätty jouset että on koodattu sanoja kuten "hei"
joita ei ole otettu sisään käyttäjältä jotka on koodattu ohjelmaan.
>> Nyt alas alareunassa me on ns pino.
Ja pino tähän asti olemme olleet käyttäen millaisia ​​tarkoituksiin?
Mitä pino käytetty?
Joo?
>> Yleisö: toiminnot.
>> DAVID J. MALAN: For toimintoja?
Missä mielessä funktioiden?
>> Yleisö: Kun soitat toiminto, argumentit kopioidaan pinoon.
>> DAVID J. MALAN: Aivan.
Kun soitat toiminto, sen argumentit kopioidaan pinoon.
Joten kaikki X: n tai Y: n tai: n tai B: n että olet meneviä toiminto
tilapäisesti laittaa ns pino,
aivan kuten yksi Annenberg ruokasali tarjottimet, ja myös asioita,
kuten paikallisia muuttujia.
Jos foo toiminto tai sivutustilan toiminto on paikallisia muuttujia,
kuten lämpötila, nämä kaksi päätyvät pinoon.
Nyt emme puhu liikaa heitä, mutta nämä ympäristömuuttujat
alareunassa näimme taas sitten kun Olin futzing näppäimistöllä yksi päivä
ja aloin päästä asioita kuten argv 100 tai argv 1000,
vain elements-- Unohdan numbers-- mutta että
ei pitänyt käsiksi minuun.
Aloimme nähdä joitakin outoja symbolit ruudulla.
Ne olivat niin sanottuja Ympäristömuuttujien
kuten yleiset asetukset minun ohjelma tai tietokoneeseeni, ei
liity äskettäin vika, josta keskustelimme,
Shellshock, joka on ollut vaivaavat melkoisesti tietokoneita.
>> Nyt lopuksi nykypäivän keskittyy me lopulta kasaan.
Tämä on toinen kimpale muistia.
Ja pohjimmiltaan kaikki tämä muisti on samat jutut.
Se on sama kone.
Olemme vain eräänlainen hoitoon eri klustereiden
tavujen eri tarkoituksiin.
Kasaan myös olemaan missä muuttujat ja muistin, että pyydät
alkaen käyttöjärjestelmän tallennetaan väliaikaisesti.
>> Mutta on sellainen ongelma täällä, koska kuva merkitsee.
Meillä tavallaan on kaksi aluksia noin törmäävät.
Koska käytät enemmän ja enemmän pinon, ja kuten näemme tänään
eteenpäin, koska käytät enemmän ja enemmän kasaan, varmasti pahoja asioita voi tapahtua.
Ja todellakin, me voimme aiheuttaa, että tahallisesti tai tahattomasti.
Joten jännitysnäytelmä viimeksi aika oli tämän ohjelman,
joka ei palvele mitään toiminnallista muuhun tarkoitukseen kuin osoittamaan
miten niin pahis voi itse ottaa etu bugeja jonkun ohjelman
ja ottaa ohjelman tai jopa koko tietokonejärjestelmä tai palvelimeen.
Joten vain silmäyksellä lyhyesti, sinun huomaa, että tärkein alareunassa
ottaa komentoriviltä argumentteja, kuten per argv.
Ja se on kutsu funktio f, lähinnä nimetön toiminto nimeltään
f, ja se kulkee argv [1].
>> Joten mitä sana käyttäjä on osoitteessa nopea jälkeen tämän ohjelman nimi,
ja sitten tämä mielivaltainen funktio ylös top, f, vie merkkijonon, AKA char *,
kuten olemme alkaneet keskustella, ja se vain kutsuu sitä "bar".
Mutta voisimme kutsua sitä jotain.
Ja sitten se ilmoittaa, sisältä f, joukko merkkejä
nimeltään C-- 12 tällaista merkkiä.
>> Nyt, jonka tarina kerroin hetki sitten, jos muistissa
on C, tai ovat niitä, 12 merkkiä päätyvät?
Vain olla selvä.
Joo?
>> Yleisö: pinoon.
>> DAVID J. MALAN: pinoon.
Joten c on paikallinen muuttuja.
Kysymme 12 merkkiä tai 12 tavua.
Nämä ovat menossa päätyä on ns pino.
Nyt vihdoin on tämä toinen toiminto Se on oikeastaan ​​aika hyödyllinen,
mutta emme ole oikeastaan ​​käytetty sen itse, strncopy.
Se tarkoittaa merkkijonon kopion, mutta vain n kappaletta kirjaimia, n merkkiä.
Joten n merkkejä ovat kopioidaan tanko c.
Ja kuinka monta?
Pituus baarissa.
Eli toisin sanoen, että yksi linja, strncopy,
tulee kopioida tehokkaasti baarin c.
>> Nyt vain sellainen ennakoida Tarinan,
mikä on mahdollisesti ongelmallista täällä?
Vaikka me tarkastamme pituus bar ja kulkee sen strncopy,
mikä on teidän gut kertoo sinulle on edelleen rikki tästä ohjelmasta?
Joo?
>> Yleisö: Ei sisällä tilaa null merkki.
DAVID J. MALAN: Ei sisällä tilaa null merkki.
Mahdollisesti, toisin kuin Aiemman käytännön emme edes
on niin paljon kuin plus 1 majoittaa että null merkki.
Mutta se on vielä pahempi.
Mitä muuta me vältämme tekemästä?
Joo?
>> Yleisö: [kuulumaton]
DAVID J. MALAN: Perfect.
Olemme koodattu 12 melko mielivaltaisesti.
Se ei ole niin paljon ongelma, vaan se,
että emme edes tarkistaa, jos pituus palkki on pienempi kuin 12,
jolloin se tulee olemaan turvallista laittaa se muistiin
nimeltään C että olemme varattu.
Todellakin, jos baari on kuin 20 merkkiä pitkä,
tämä toiminto näyttää kopiointi 20 merkkiä tanko c, jolloin
ottaen vähintään 8 tavua että sen ei pitäisi olla.
Se on seuraus tästä.
>> Niin lyhyt, rikki-ohjelma.
Ei niin iso juttu.
Ehkä saat segmentointi vika.
Meillä kaikilla on ollut vikoja ohjelmissa.
Meillä kaikilla saattaa olla vikoja ohjelmiin juuri nyt.
Mutta mitä vaikutuksia?
No, tässä lähennettyä versio että kuva minun tietokoneen muistiin.
Tämä on pohja minun pinon.
Ja todellakin, alareunassa on mitä on nimeltään vanhempi rutiini pino, hieno tapa
sanoa, että tärkein.
Niin että kuka kutsui toiminto f että puhumme.
Tämä on siis pinon pohjalle.
Palautusosoite on jotain uutta.
Se on aina ollut siellä, aina ollut tuossa kuvassa.
Olemme juuri koskaan kiinnittänyt huomiota siihen.
Koska se kääntyy pois tieltä c toimii on että kun yksi toiminto kutsuu toista,
eivät ainoastaan ​​argumentit, jotka toiminto työnnetään pinoon,
eivät ainoastaan ​​funktion paikallinen muuttujat työnnetään pinoon,
jotain kutsutaan paluuosoite myös saa laittaa pinoon.
Erityisesti jos tärkeimmät puhelut foo Mainin oma osoite muistiin, ox jotain,
tehokkaasti saa laittaa pinoon niin että kun f on tehty sen suorittamista
tietää mistä hypätä takaisin tekstiin segmentti voidakseen jatkaa täytäntöönpanosta.
>> Joten jos olemme täällä käsitteellisesti, main, niin f saa kutsutaan.
Miten f tiedä kuka käteen ohjaus takaisin?
No, tämä pieni breadcrumb punaisella täällä,
nimeltään palautusosoite, se vain tarkastuksia, mikä on, että tuotto-osoite?
Oi, anna minun hypätä takaisin tärkein täällä.
Ja se on hieman on liian yksinkertaistava,
koska nollia ja ykkösiä Pitkien ovat teknisesti
tänne Tech segmentin.
Mutta se ajatus. f vain on tietää, mitä
missä valvonta lopulta palaa.
>> Mutta niin tietokoneet ovat jo pitkään säädettyihin asioita
kuten paikalliset muuttujat ja väitteet on näin.
Joten päälle tätä kuvaa sininen on pinokehys f, joten kaikki
muistin, että f Erityisesti on käytössä.
Niin ollen, huomaa, että Baari on tässä kuvassa.
Baari oli sen väitettä.
Ja me väitti, että argumentit toimintoja työnnetään pinoon.
Ja c, on tietenkin Myös tässä kuvassa.
>> Ja vain merkinnällinen tarkoituksiin, huomaa yläreunassa vasemmassa alakulmassa
on mikä olisi c kiinnike 0 ja sitten hieman oikealle
on c kiinnike 11.
Eli toisin sanoen, voitte kuvitella että siellä verkkoon tavua
siellä, joista ensimmäinen on vasemmassa yläkulmassa, pohja
on viimeinen näistä 12 tavua.
>> Mutta nyt yrittää kelata eteenpäin.
Mitä on tapahtumassa, jos ohitamme merkkijono baarissa, joka on pidempi kuin c?
Ja emme tarkistaa, jos se on todellakin yli 12.
Mikä osa tätä kuvaa on menossa päällekirjoiteta tavujen 0, 1, 2, 3,
dot dot dot, 11, ja sen jälkeen huono, 12, 13: sta 19?
Mitä tulee tapahtumaan täällä, jos päätellä tilaaminen
että c kiinnike 0 on ylimmässä ja c kiinnike 11 on tavallaan alas
oikealle?
Joo?
>> Yleisö: No, se tulee korvata char * bar.
>> DAVID J. MALAN: Joo, se näyttää aiot korvata char * bar.
Ja pahempaa, jos lähetät todella pitkä merkkijono, saatat jopa korvata mitä?
Palautusosoite.
Joka taas on aivan linkkipolku kertoa ohjelma, jossa
palata kun f tehdään kutsutaan.
>> Joten mitä pahikset tekevät yleensä jos he törmännyt ohjelmaan
että he ovat uteliaita siitä on hyödynnettävissä, buginen siten
että hän voi ottaa etu, että vika,
yleensä he eivät saa tämä oikeus ensimmäistä kertaa.
He vain alkavat lähettää esimerkiksi satunnaisia ​​merkkijonoja omaan ohjelmaan,
onko näppäimistöllä, tai suoraan sanottuna he luultavasti
kirjoittaa vähän ohjelmaa vain automaattisesti jouset,
ja alkaa hakkaa oman ohjelman lähettämistä paljon eri tuotantopanosten
eri pituudet.
>> Heti kun ohjelma kaatuu, Se on uskomaton juttu.
Koska se tarkoittaa, että hän tai hän on löytänyt
mikä on luultavasti todellakin bugi.
Ja sitten he voivat saada viisaampi ja alkaa keskittyä tiukemmin
miten hyödyntää että vika.
Erityisesti mitä hän voisi tehdä, on lähettää, parhaassa tapauksessa, hei.
No big deal.
Se on merkkijono, joka on riittävän lyhyt.
Mutta entä jos hän lähettää, ja me yleistää sitä,
hyökkäys code-- niin nollat ja ne, jotka tekevät asioita
kuten rm-rf, että poistaa kaikki kiintolevyltä tai lähettää roskapostia
tai jotenkin hyökätä kone?
>> Joten, jos kaikki nämä kirjaimet vain edustaa,
käsitteellisesti, hyökkäys, hyökkäys, hyökkäys, hyökkäys, huonoja koodi
että joku muu kirjoitti, mutta jos kyseinen henkilö on fiksu
paitsi sisältää kaikki Näiden rm-RFS, mutta myös
on hänen viime tavua olla numero, joka vastaa
osoitteeseen hänen tai oman hyökkäyksen koodi
että hän läpäisi vain antamalla se sitä kysyy,
voit tehokkaasti huijata tietokoneen tulee huomaamatta, kun f on tehty täytäntöönpanosta,
Voi, se on aika minun hypätä takaisin punainen palautusosoite.
Mutta koska hän on jotenkin päällekkäinen paluuosoite
omalla numerolla, ja he ovat tarpeeksi älykkäitä
on määrittänyt, että numero viittaa, kun
katso super alkuun vasemmassa alakulmassa siellä,
todellinen osoite tietokoneen muisto joidenkin hyökkäys koodi,
pahis voi huijata tietokoneen osaksi täytäntöönpanovaltion oman koodin.
>> Ja että koodi taas voi olla mitä tahansa.
On yleisesti kutsutaan kuori-koodi, joka on vain
tapa sanoa, että se ei ole yleensä jotain niin yksinkertaista kuin rm-rf.
Se on oikeastaan ​​jotain Bash, tai varsinainen ohjelma, joka antaa hänelle
tai hänen ohjelmallisen säädön suorittamiseksi muuta, että he haluavat.
Niin lyhyt, tämä kaikki johtuu yksinkertaisesti siitä,
että tämä vika mukana ei tarkista rajat matriisisi.
Ja sillä tavalla tietokoneet työ on, että ne
Käytä pino tehokkaasti, käsitteellisesti,
alhaalta ylös, mutta sitten elementit painat pinoon kasvaa ylhäältä alas,
Tämä on uskomattoman ongelmallista.
Nyt on olemassa tapoja kiertää tämän.
Ja rehellisesti, on olemassa muitakin kieliä jonka kanssa kiertää.
Java on immuuni, esimerkiksi tähän kysymykseen.
Koska he eivät anna viitteitä.
Ne eivät anna sinulle suora muisti osoitteita.
Joten tämä voima, joka meillä on koskematta mihinkään muistiin
Haluamme tulee, tosin suuri riski.
>> Joten pitää silmällä.
Jos rehellisesti sanottuna kuukausina tai tulevina vuosina, milloin
olet lukenut joitakin hyväksikäyttö ohjelman tai palvelin,
jos joskus nähdä aavistuksen jotain kuten puskurin ylivuoto hyökkäys,
tai pinon ylivuoto on toinen tyyppi hyökkäys, hengeltään samanlainen,
jopa inspiroi sivuston nimi, jos tiedät sen,
se kaikki puhuvat vain täynnä koko jokin merkki
array tai jotkut array yleisemmin.
Kysyttävää, niin, tähän?
Älä kokeile tätä kotona.
>> Kunnossa.
Joten malloc on tähän mennessä ollut uuden ystävä, että voimme varata muistia
että emme välttämättä tiedä etukäteen, että haluamme niin meillä ei ole
kovaa koodi meidän ohjelmanumeroita, kuten 12.
Kun käyttäjä kertoo, kuinka paljon tietoja hän haluaa syöttää,
Voimme malloc niin paljon muistia.
>> Joten malloc se kääntyy pois, jotta määrin olemme käyttäneet sitä,
nimenomaisesti viime kerralla, ja sitten te ovat käyttäneet sitä
varten getstring tietämättään varten useita viikkoja, kaikki malloc muistista
tulee ns pino.
Ja tästä syystä getstring, esimerkiksi voi varata muistia dynaamisesti
tietämättä mitä olet menossa kirjoittaa etukäteen,
käden takaisin osoittimen, joka muisti, ja että muisti on edelleen sinun pitää,
jälkeenkin getstring palaa.
Koska muistaa kaiken sen jälkeen pino jatkuvasti menee ylös ja alas,
ylös ja alas.
Ja heti kun se menee alas, että mitä tahansa muistia
Tätä toimintoa käytetään pitäisi ei saa käyttää kukaan muu.
Se on roskaa arvot nyt.
>> Mutta keko on täällä.
Ja mikä on mukavaa noin malloc on, että kun malloc varaa muistia täällä,
se ei ole vaikuttanut, sillä suurin osa on pino.
Ja niin jokin toiminto voi käyttää muistin, joka on malloc'd,
jopa toimivat kuin getstring, senkin jälkeen se palautetaan.
>> Nyt päinvastainen malloc on ilmainen.
Ja todellakin, sääntö sinua täytyy alkaa hyväksyä
on mikä tahansa, mitä tahansa, milloin käytät malloc sinun täytyy itse käyttää vapaa, lopulta,
samana osoitin.
Koko tämän ajan olemme kirjallisesti buginen, buginen koodi, monista syistä.
Mutta joista yksi on ollut käyttämällä CS50 kirjasto, joka
itsessään on tarkoituksella buginen, se vuotaa muistia.
Aina kun olen kutsunut getstring viime viikkoina
Pyydämme toiminta järjestelmä, Linux, muistin.
Ja et ole kertaakaan antanut sitä takaisin.
Ja tämä ei ole, vuonna harjoitella, hyvä juttu.
>> Ja Valgrind, yksi työkalujen käyttöön PSET 4,
tarkoitus on auttaa sinua nyt löytää vikoja niin.
Mutta onneksi PSET 4 et tarvitse käyttää CS50 kirjaston tai getstring.
Joten vikoja liittyvät muisti ovat lopulta olemaan oma.
>> Joten malloc on enemmän kuin vain kätevä tähän tarkoitukseen.
Voimme todella nyt ratkaista perustavanlaatuisesti erilaisia ​​ongelmia,
ja pohjimmiltaan ratkaise ongelmia lisää tehokkaasti viikossa nolla lupaus.
Toistaiseksi tämä on seksikkäin tietorakenne meillä on ollut.
Ja tietorakenne Tarkoitan vain tapa käsitteellistää muistia
tavalla, joka ylittää vain sanomalla, tämä on int, tämä on merkkiä.
Voimme aloittaa klusterin asioita yhdessä.
>> Joten array näytti tältä.
Ja mikä oli keskeinen noin Asetelma on, että se antaa sinulle
back-to-back paloina muistin, joista jokainen
tulee olemaan samaa tyyppiä, int, int, int, int, tai char, char, char,
merkkiä.
Mutta siellä on muutama haittoja.
Tässä esimerkiksi on taulukon koko kuusi.
Oletetaan täytät tämän array kuusi numerot ja sitten jostain syystä,
Käyttäjänimesi haluaa antaa te seitsemännen numeron.
Mistä sinä sen?
>> Mikä on ratkaisu, jos olet luotu array pinoon,
Esimerkiksi pelkästään viikolla kaksi merkintää, jotka otimme käyttöön,
neliön kannattimet numero sisällä?
No, sinulla on kuusi numerot näissä laatikoissa.
Mitä vaistosi olla?
Minne haluaisit laittaa sen?
>> Yleisö: [kuulumaton]
>> DAVID J. MALAN: Anteeksi?
>> Yleisö: Laita se loppuun.
>> DAVID J. MALAN: Laita se loppuun.
Joten hieman yli oikealle, ulkopuolella tämän laatikon.
Mikä olisi kiva, mutta se Osoittautuu, et voi tehdä sitä.
Koska jos et ole pyytänyt Tämän kimpale muistia,
se voi olla sattumaa, että tämä käytetään jonkin muun muuttujan
kokonaan.
Muistelen viikon tai niin kun loimme ulos Zamyla ja Davin ja Gabe nimet
muistiin.
He olivat kirjaimellisesti takaisin takaisin takaisin.
Joten emme voi välttämättä luottaa siihen, että mitä on
täällä on saatavilla minulle käyttää.
>> Mitä muuta voisi tehdä?
No, kun ymmärtämättä sinua tarvitsevat taulukon koko seitsemän,
voisit luoda taulukon koko seitsemän sitten
silmukka tai while-silmukka, kopioi se uuteen array,
ja sitten jotenkin vain päästä eroon tämän taulukon tai vain lakata käyttämästä sitä.
Mutta se ei ole erityisen tehokasta.
Lyhyesti, taulukot eivät anna voit dynaamisesti muuttaa.
>> Niin toisaalta saat random access, mikä on hämmästyttävä.
Koska se antaa meidän tehdä asioita kuten hajoita ja hallitse,
Binäärihaku, jotka kaikki olemme puhui ruudulla täällä.
Mutta maalaat itsesi nurkkaan.
Heti kun osut lopussa oman array,
sinun täytyy tehdä hyvin kallis toimenpide
tai kirjoittaa koko joukko koodin nyt käsitellä tätä ongelmaa.
>> Joten mitä jos sen sijaan meillä oli jotain kutsutaan lista,
tai linkitetty lista erityisesti?
Mitä jos sen sijaan, suorakulmioita takaisin takaisin takaisin,
meillä ruutuihin jättää hieman vähän liikkumavaraa niiden väliin?
Ja vaikka olen laatinut tämän kuva tai mukauttaa tätä kuvaa
yhdestä tekstien ja tule takaisin takaisin takaisin hyvin järjestelmällisesti, todellisuudessa,
yksi niistä suorakaide voisi olla täällä muistissa.
Yksi niistä voisi olla täällä.
Yksi niistä voisi olla täällä, tänne, ja niin edelleen.
>> Mutta entä jos me kiinnitti, Tässä tapauksessa, nuolet
että jotenkin yhdistää nämä suorakulmiot yhteen?
Itse asiassa olemme nähneet teknisen inkarnaatio nuoli.
Mitä olemme käytetty viime päivinä, alla huppu,
edustaa nuoli?
Osoitin, eikö?
>> Joten mitä jos sen sijaan, vain tallentamalla numerot,
kuten 9, 17, 22, 26, 34, mitä jos emme ole tallennettu
vain puhelinnumeron, mutta osoitin vierekkäin niin numero?
Niin paljon kuin olisit kierre neula läpi koko joukko kangasta,
jotenkin sitominen asiat yhdessä, samoin voi
me viitteitä, kuten ruumiillistunut nuolilla täällä,
tavallaan kutoa yhteen Näiden yksittäisten suorakaide
tehokkaasti käyttämällä osoitinta vierekkäin useita, jotka
eräisiin seuraava numero, joka osoittaa puolestaan, joissakin seuraava numero?
Eli toisin sanoen, mitä jos me todella halusimme
toteuttaa jotain tällaista?
No valitettavasti näitä suorakaide, ainakin yksi 9, 17, 22,
ja niin edelleen, nämä eivät ole enää kiva neliöitä yhtä numerot.
Pohja, suorakaide alle 9, esimerkiksi,
edustaa sitä, mikä olisi olla osoitin, 32 bittiä.
Nyt en ole vielä tiedossa tietotyyppi C, joka antaa sinulle paitsi int
mutta osoitin kokonaan.
>> Joten mikä on ratkaisu, jos haluamme keksiä omia vastaus tähän?
Joo?
>> Yleisö: [kuulumaton]
>> DAVID J. MALAN: Mikä tämä on?
>> Yleisö: Uusi rakenne.
>> DAVID J. MALAN: Joo, niin miksi emme luo uutta rakennetta,
tai C, struct?
Olemme nähneet structs ennen, jos lyhyesti, jossa käsitellään opiskelijan rakenne
kuten tämä, jolla oli nimi ja talon.
Vuonna PSET 3 Breakout käytit koko nippu structs-- GRect ja GOvals
että Stanford luotu cluster tiedot yhdessä.
Joten mitä jos otamme tämän saman ajatuksen avainsanat "typedef" ja "struct"
ja sitten jotkut opiskelija-erityisiä juttuja, ja kehittyä tämän huomioon seuraavat:
struct node-- ja solmu on vain hyvin yleinen tietotekniikassa
termi jotain datarakenteen, säiliö tietorakenteeseen.
Solmu Väitän joutuu int n, täysin suoraviivainen,
ja sitten hieman arvoituksellisesti, tämä toinen linja, struct solmu * seuraavaksi.
Mutta vähemmän teknisiä termejä, mikä on että toisen linjan
Koodin sisällä aaltosulkeita?
Joo?
>> Yleisö: [kuulumaton]
DAVID J. MALAN: osoitin toiseen solmuun.
Niin tosin lauseenrakenteen hieman arvoituksellinen.
Mutta jos olet lukenut sen kirjaimellisesti, seuraava on muuttujan nimenä.
Mikä on sen tietotyyppi?
Se on vähän monisanainen tällä kertaa, mutta se on tyyppiä struct solmu *.
Tahansa olemme nähneet jotain tähden, että tarkoittaa että se on osoitin, että tietotyyppi.
Joten seuraavaksi on ilmeisesti Osoitin struct solmu.
>> Nyt, mikä on struct solmu?
No, huomaa näet ne samat sanat oikeassa yläkulmassa.
Ja todellakin, näet myös sana "Solmu" täällä alhaalla vasemmalla.
Ja tämä on oikeastaan ​​vain mukavuussyistä.
Huomaa, että meidän opiskelija määritelmä siellä on sana "opiskelija" vain kerran.
Ja se johtuu siitä, opiskelija esine ei ollut itseensä viittaavan.
Mikään ei sisällä opiskelija joka tarvitsee tuoda toisen opiskelijan,
persay.
Se olisi eräänlainen outo todellisessa maailmassa.
>> Mutta solmun linkitetty lista, mehän haluamme solmun
olla viite on samanlainen tarkoitus.
Ja niin huomaat muutoksen tässä ole vain mitä sisällä aaltosulkumerkkien.
Mutta lisäämme sanan "solmu" yläosassa sekä
lisäämällä sen pohjaan sijasta "opiskelija".
Ja tämä on vain tekninen yksityiskohta niin että, jälleen, tietosi rakenne
voi olla itseensä viittaavan, niin että solmu voi osoittaa toiselle tällaiselle solmuun.
>> Joten mitä tämä lopulta menossa merkitsee meille?
No, yksi, tätä tavaraa sisällä on sisältö meidän solmun.
Tämä juttu täällä, oikeassa yläkulmassa, on vain niin
että, jälleen, voimme viitata itseämme.
Ja sitten syrjäisimpien tavaraa, vaikka solmu on uusi termi,
ehkä se on silti sama kuin opiskelija ja mitä
oli alla huppu SPL.
>> Joten jos nyt halunnut aloittaa täytäntöönpanossa linkitetty lista,
miten voisi käännämme jotain tällaista koodia?
No, haluan vain nähdä esimerkki ohjelmasta, joka
tosiasiallisesti käyttää linkitetty lista.
Keskuudessa nykypäivän jakelu koodi on ohjelma nimeltä List Zero.
Ja jos juoksen tämän olen luonut erittäin yksinkertainen GUI, graafinen käyttöliittymä,
mutta se on oikeastaan ​​vain printf.
Ja nyt olen antanut itselleni muutaman valikon options-- poistaa, lisätä, haku,
ja Traverse.
Ja Lopeta.
Nämä ovat vain yhteisiä operaatioita tietorakenne tunnetaan linkkilista.
>> Nyt Delete on menossa poistaa numeron luettelosta.
Insert tulee lisätä numeron luetteloon.
Haku on menossa katsomaan Numeron luettelossa.
Ja poikittainen on vain hieno tapa sanoa, kävele listalle
tulostaa sen, mutta siinäpä se.
Älä muuta sitä millään tavalla.
>> Joten kokeile tätä.
Mennään eteenpäin ja tyypin 2.
Ja sitten aion lisätä numeron, sanovat 9.
Enter.
Ja nyt ohjelma on vain ohjelmoitu sanoa, lista on nyt 9.
Nyt, jos menen eteenpäin ja älä laita se uudelleen, anna
minun mennä eteenpäin ja loitontaa ja kirjoita 17.
Nyt lista on 9, sitten 17.
Jos en laita se takaisin, katsotaanpa ohittaa yhden.
Sen sijaan 22, joka on pakkauksessa olemme etsinyt täällä, haluan siirtyä eteenpäin
ja aseta 26 seuraava.
Joten aion kirjoittaa 26.
Luettelo on odotan.
Mutta nyt vain nähdä, jos tämä koodi tulee olla joustava, haluan nyt
tyyppi 22, joista ainakin käsitteellisesti, jos olemme
Pidä tämä lajitellaan, joka on todellakin olemaan toinen tavoite juuri nyt,
pitäisi mennä välillä 17 ja 26.
Joten osuin Enter.
Todellakin, että toimii.
Ja nyt haluan lisätä viimeinen, per kuva, 34.
>> Kunnossa.
Joten nyt haluan ilmoittaa, että Poista ja Traverse ja haku tehdä,
itse asiassa toimi.
Itse asiassa, jos en suorita haku, katsotaanpa etsi numero 22, Enter.
Se löytyi 22.
Niin sitähän tämä Ohjelman List Zero tekee.
>> Mutta mitä todella tapahtuu siitä, että toteuttaa tämä?
No, ensin voisin olla, ja todellakin Minulla ei ole, tiedosto nimeltä list0.h.
Ja jossain on tämä linja, typedef, struct solmu,
Sitten minulla on aaltosulkeita, int n, ja Sitten struct-- mikä oli määritelmän?
Struct solmu seuraavaksi.
Joten tarvitsemme tähti.
Nyt teknisesti pääsemme tapana piirtämällä täällä.
Saatat nähdä oppikirjoja ja Online viittaukset siihen siellä.
Se on toiminnallisesti vastaava.
Itse asiassa tämä on hieman enemmän tyypillinen.
Mutta olen sitä, mitä teimme viime kerralla ja tehdä tämän.
Ja sitten lopuksi, aion tehdä tämän.
>> Joten otsikkotiedosto jonnekin, vuonna list0.h
tänään on tämä struct määritelmä, ja ehkä joitakin muita juttuja.
Samaan aikaan list0c siellä olemaan muutamia asioita.
Mutta me aiomme vain aloittaa eikä lopettaa tämän.
List0.h on tiedosto haluan sisällyttää minun C-tiedosto.
Ja sitten jossain vaiheessa olen menossa on int, tärkein, mitätöidä.
Ja sitten aion joitakin tehtävälista on täällä.
Olen myös menossa prototyyppi, kuten mitätön, haku, int,
n, jonka tarkoitus elämässä on etsiä elementti.
Ja sitten täällä olen väittänyt Nykypäivän koodia, mitätön, haku, int, n,
ei puolipiste mutta avoin aaltosulkeita.
Ja nyt haluan jotenkin hakea varten elementti tässä listassa.
Mutta meillä ei ole tarpeeksi kuvaruudussa vielä.
En ole oikeastaan edusti luetteloa.
Joten yksi tapa voisimme toteuttaa linkitetty lista ohjelmassa
on Olen sellainen halua tehdä jotain kuten Julistan linkitetyn listan tänne.
Yksinkertaisuuden vuoksi aion tehdä tämä globaali, vaikka yleensä me
ei pitäisi tehdä tätä liikaa.
Mutta se yksinkertaistaa tätä esimerkkiä.
Joten en halua julistaa linkitetyn listan tänne.
Nyt, miten voisin tehdä?
>> Tässä on kuva linkitetyn listan.
Ja en oikein tiedä tällä hetkellä, miten
Aion edetä edustavat niin monet asiat vain yhdellä
muuttuja muistiin.
Mutta muistelen hetki.
Koko ajan meillä on ollut jouset, jonka sitten
paljastuu paneelit merkkiä, jonka sitten
paljasti vain olla osoitin ensimmäisen merkin
riviksi merkkiä joka on null irtisanotaan.
Niin, että logiikka, ja tämän kuva tavallaan kylvö ajatuksiasi,
Mitä me oikeastaan ​​kirjoittaa meidän koodi edustaa linkitetty lista?
Kuinka paljon tästä tietoa tarvitsemme vangita C-koodia, sanoisit?
Joo?
>> Yleisö: Tarvitsemme osoitin solmuun.
David J. MALAN: osoitin solmuun.
Erityisesti, mikä solmu Olisiko vaistot olla pitää osoitin?
>> YLEISÖ: ensimmäiseen solmuun.
>> DAVID J. MALAN: Joo, luultavasti vain ensimmäinen.
Ja huomaa, ensimmäinen solmu on erilainen muoto.
Se on vain puolet koko struct, koska se on todellakin vain osoitin.
Joten mitä voit todella tehdä, on ilmoittaa linkitetty lista on tyyppiä solmu *.
Ja haluan vain kutsua sitä ensin ja alustaa sen nollaamaan.
Joten null taas on tulossa kuvaan tässä.
Ei vain null käytetään kuten erityinen paluuarvo asioita, kuten getstring
ja malloc, nolla on myös nolla osoitin, ettei osoitin,
jos haluatte.
Se vain tarkoittaa, mikään ei ole vielä täällä.
Nyt ensin, olisin voinut kutsui tätä kaikkea.
Olisin voinut kutsui sitä "listan" tai useita muita asioita.
Mutta soitan sitä "ensimmäinen" niin, että se on linjassa tämän kuvan.
Joten aivan kuten merkkijono voidaan esittää osoitteen kanssa sen ensimmäinen tavu,
niin voi linkitetty lista.
Ja näemme muita tietoja rakenteet ovat edustettuina
vain yksi osoitin, 32-bittinen nuoli osoittaen
aivan ensimmäisen solmun rakenteessa.
>> Mutta nyt katsotaanpa ennakoida ongelma.
Jos olen vain muistaa minun ohjelma osoite
Ensimmäisen solmun, ensimmäinen suorakulmio tässä tietorakenne,
mikä oli parempi olla kyse siitä täytäntöönpanoa muun listalta?
Mikä on avain yksityiskohta, joka menee varmistamiseksi tämä todella toimii?
Ja "oikeasti toimii" I Tarkoitan, aivan kuten merkkijono,
antaa meidän mennä ensimmäinen merkki vuonna Davin nimi toiseen,
kolmanteen, että Neljäs, loppuun asti,
Mistä tiedämme, milloin olemme lopussa linkitetyn listan, joka näyttää tältä?
Kun se on tyhjä.
Ja olen edusti tällainen kuin kuten sähkö-insinööri voimin,
pikku maadoitus symboli, tapaisena.
Mutta se vain tarkoittaa, null tässä tapauksessa.
Voit piirtää haluamansa määrän tavoilla, mutta tämän kirjoittajan
tapahtui käyttää tätä symbolia täällä.
>> Niin kauan kuin olemme nauhassa kaikki nämä solmut yhdessä,
vain muistaa missä Ensimmäinen on, niin kauan
niin laitamme erikoissymboli osoitteessa viimeinen solmu listassa,
ja käytämme null, koska se on mitä meillä on käytettävissämme,
tämä lista on valmis.
Ja vaikka minä vain antaa sinulle osoittimen ensimmäinen elementti, te, ohjelmoija,
voi varmasti käyttää loput siitä.
Mutta katsotaanpa anna mielissä vaeltaa hieman,
jos ne eivät ole jo aivan wandered-- mitä
olemaan käyntiaika löytää jotain seuraavista?
Hitto, se on iso O n, joka ei ole huono, oikeudenmukaisuus.
Mutta se on lineaarinen.
Olemme luopuneet mitä ominaisuutta Taulukoiden siirtämällä lisää
kohti tätä kuvaa dynaamisesti kudottu yhteen tai siihen solmuja?
Olemme luopuneet random access.
Array on mukavaa, koska matemaattisesti kaiken
on palannut takaisin takaisin takaisin.
Vaikka tämä kuva näyttää aika, ja jopa
vaikka se näyttää nämä solmut ovat hyvin erillään toisistaan, todellisuudessa
he voisivat olla missä tahansa.
OX1, OX50, Ox123, Ox99, nämä solmut voi olla missä tahansa.
Koska malloc ei varata muistia kasaan, mutta kaikkialla kasaan.
Et välttämättä tiedä, että se on tulee takaisin takaisin takaisin.
Ja niin tätä kuvaa todellisuudesta n ei tule olemaan ihan näin kaunis.
>> Joten se tulee ottaa vähän työtä toteuttaa tätä toimintoa.
Joten toteuttaa haun nyt.
Ja näemme, millaisia näppärä tapa tehdä tämä.
Joten jos olen hakutoiminto ja Olen antanut muuttuja, kokonaisluku n
etsiä, minun täytyy tietää uusi syntaksi etsii sisällä
rakenne, joka on osoitti, löytää n.
Joten tehdään tämä.
>> Joten ensin aion mennä eteenpäin ja julistaa solmu *.
Ja aion kutsua sitä osoitin, vain sopimuksen mukaan.
Ja aion alustaa sen ensin.
Ja nyt en voi tehdä tätä useilla tavoilla.
Mutta aion olla yhteinen lähestymistapa.
Vaikka osoitin ei ole yhtä suuri null, ja se on voimassa syntaksin.
Ja se tarkoittaa vain toimi seuraavasti, joten kunhan et osoita mitään.
Mitä haluan tehdä?
>> Jos osoitin dot n, haluan tulla takaisin vastaavasti, equals-- vastaa mitä?
Mikä arvo etsin?
Varsinainen n että hyväksyttiin.
Joten tässä on toinen ominaisuus C ja monilla kielillä.
Vaikka rakenne nimeltään solmu on arvo n, täysin laillista
että myös paikallinen argumentti tai muuttuja Kutsutaan.
Sillä vaikka me, joilla ihmisten silmissä, voidaan erottaa
että tämä n on oletettavasti eroaa tästä n.
Koska syntaksi on erilainen.
Sinulla piste ja osoitin, tämä yksi ei ole olemassakaan.
Joten tämä on OK.
Se on OK kutsua niitä samoja asioita.
>> Jos en löydät tämän, olen menossa haluavat tehdä jotain
kuin ilmoittaa, että löysimme n.
Ja jätämme että kommentoida tai pseudokoodilla koodia.
Else, ja tässä mielenkiintoinen osa, mitä
En halua tehdä, jos nykyinen solmu ei sisällä n että välitän?
Miten saavuttaa seuraava?
Jos sormella hetki on PTR, ja se on
osoittaen tahansa ensimmäinen on suunnattu,
miten voin siirtää sormi seuraavaan solmuun koodi?
No, mitä linkkipolun olemme menossa seuraamaan tässä asiassa?
Yleisö: [kuulumaton].
DAVID J. MALAN: Joo, niin seuraavaksi.
Joten jos menen takaisin minun koodi täällä, todellakin, olen
aio mennä eteenpäin ja sanoa osoitin, joka on vain väliaikainen variable-- se on
outo nimi, PTR, mutta se on aivan kuin temp--
Aion asettaa osoittimen yhtä suuri kuin mikä tahansa osoitin on--
ja uudestaan, tämä tulee olemaan vähän buginen moment-- piste seuraavaksi.
Toisin sanoen, aion ottaa minun sormi, joka on suunnattu tähän solmuun
täällä ja aion sanoa, tiedäthän mitä, katsomaan seuraavaan kenttään
ja siirrä sormea mitä se on suunnattu.
Ja tämä tulee toista, toista, toista.
Mutta kun ei minun sormi lakata tekemästä yhtään mitään?
Heti mitä riviä koodia potkuja?
Yleisö: [kuulumaton]
DAVID J. MALAN: Jos kohta taas osoitin ei ole yhtä suuri null.
Jossain vaiheessa minun sormen aiotaan osoittaen null
ja aion toteuttaa se on tämän listan loppuun.
Nyt, tämä on hieman valkoinen valhe yksinkertaisuuden.
On käynyt ilmi, että vaikka me juuri oppinut tämän dot merkintä
Rakenteita, osoitin ei ole struct.
PTR on mitä?
Vain olla enemmän nitpicky.
Se on osoitin solmuun.
Se ei ole solmu itse.
Jos minulla ei ollut tähti täällä, osoitin absolutely-- se on solmu.
Tämä on kuin viikolla yksi ilmoitus muuttuja,
vaikka sana "solmu", on uusi.
>> Mutta heti kun esittelemme tähti, se on nyt osoitin solmuun.
Ja valitettavasti et voi käyttää dot merkintätapa osoitin.
Sinun täytyy käyttää nuoli merkintätapa, joka häkellyttävän,
on ensimmäistä kertaa kaikki pala syntaksin näyttää intuitiivinen.
Tämä kirjaimellisesti näyttää nuoli.
Ja niin se on hyvä asia.
Ja täällä kirjaimellisesti näyttää nuoli.
Joten luulen, että se la-- en taidan yli-syyllistyneet here-- I
taitaa olla viimeinen uusi kappale syntaksin aiomme nähdä.
Ja onneksi se on todellakin hieman enemmän intuitiivinen.
>> Nyt niille teistä, jotka ehkä mieluummin vanha tapa,
voit silti käyttää dot merkintä.
Mutta kohti Maanantain keskustelun, ensin
täytyy mennä sinne, mene että käsitellä, ja sitten käyttää kenttään.
Joten tämä on myös oikea.
Ja suoraan sanottuna, tämä on hieman pikkutarkka.
Olet kirjaimellisesti sanoen dereference osoitin ja mennä sinne.
Sitten napata .N, kenttä Kutsutaan.
Mutta rehellisesti sanottuna, kukaan ei halua kirjoittaa tai lukea tätä.
Ja niin maailma keksitty nuoli merkintätapa, joka
on sama, samanlainen, se on vain syntaktista sokeria.
Niin hieno tapa sanoa tämä näyttää paremmalta, tai näyttää yksinkertaisempi.
>> Joten nyt aion tehdä yhden asian.
Aion sanoa "tauolla", kun olen löytyi niin en pidä etsimässä sitä.
Mutta tämä on ydin of hakutoiminto.
Mutta se on paljon helpompaa, vuonna Lopulta ei kulkea koodin.
Tämä on todellakin muodollinen täytäntöönpano haku nykypäivän jakelu koodia.
Uskallan väittää, että insertti ei ole Erityisen hauskaa kulkea
visuaalisesti, eikä poistaa, vaikka vaikka lopussa päivän
he pohjimmiltaan melko yksinkertainen heuristiikka.
>> Joten tehdään tämä.
Jos sinulla huumori minut tänne, tein tuo joukko stressi pallot.
Toin joukko numeroita.
Ja saisimme vain muutamia vapaaehtoisia edustaa 9, 17, 20, 22, 29, ja 34?
Niin olennaisesti kaikki kuka täällä tänään.
Se oli yksi, kaksi, kolme, neljä, viisi, kuusi ihmistä.
Ja olen pyytänyt go-- nähdä, ei yksi takana nostaa kätensä.
OK, yksi, kaksi, kolme, neljä, five-- anna minun ladata balance-- kuusi.
OK, olet kuusi tule ylös.
Tarvitsemme muita ihmisiä.
Toimme ylimääräistä stressiä pallot.
Ja jos voisit varten vain hetken, linja
itsenne vain kuten tämä kuva täällä.
>> Kunnossa.
Katsotaan, mikä on nimesi?
>> Yleisö: Andrew.
>> DAVID J. MALAN: Andrew, olet numero 9.
Hauska tavata.
Tässä mennään.
Yleisö: Jen.
DAVID J. MALAN: Jen.
David.
Numero 17.
Kyllä?
>> Yleisö: Olen Julia.
>> DAVID J. MALAN: Julia, David.
Numero 20.
Yleisö: Christian.
DAVID J. MALAN: Christian, David.
Numero 22.
Ja?
>> Yleisö: JP.
DAVID J. MALAN: JP.
Numero 29.
Joten mene eteenpäin ja saada in-- Uh oh.
Uh oh.
Valmiustilassa.
20.
Onko kellään merkki?
Yleisö: Minulla Sharpie.
DAVID J. MALAN: Sinulla Sharpie?
OK.
Ja ei kellään paperia?
Säästä luento.
Tule.
Yleisö: Meillä sitä.
DAVID J. MALAN: Saimme sen?
Okei, kiitos.
Tässä sitä mennään.
Oliko tämä sinulta?
Olet juuri pelasti päivän.
Niin 29.
Kunnossa.
Olen kirjoitettu väärin 29, mutta OK.
Mennä eteenpäin.
Okei, minä annan sinulle kynän takaisin hetkellisesti.
Joten meillä on nämä ihmiset täällä.
Mennään yksi muu.
Gabe, haluatko pelata ensimmäinen elementti täällä?
Me tarvitsemme sinua kohtaan näitä hienoja ihmisiä.
Joten 9, 17, 20, 22, lajitella 29, ja sitten 34.
Eksytimmekö joku?
Minulla on 34.
Jos did-- OK, joka haluaa olla 34?
OK, tule ylös, 34.
Okei, tämä on arvoinen huipentuma.
Mikä sinun nimesi on?
>> Yleisö: Peter.
>> DAVID J. MALAN: Peter, tule ylös.
Okei, joten tässä on koko joukko solmuja.
Jokainen teistä kaverit edustaa yksi näistä suorakulmioita.
Gabe, hieman outoa ihminen, edustaa ensin.
Joten hänen osoitin on hieman pienempi ruudulla kuin kaikki muutkin.
Ja tässä tapauksessa kukin vasemmalla kädet tulee joko kohta alas,
mikä edustaa null, joten vain puuttuminen osoittimen,
tai se tulee voida osoittaa solmussa vieressäsi.
>> Joten nyt jos koristavat itsenne kuten kuva
täällä, mennä eteenpäin ja kohta toisilleen, ja Gabe
erityisesti suunnattu numero 9 edustaa luetteloon.
OK, ja numero 34, vasemmalla kädellä pitäisi vain olla suunnattu lattiaan.
>> OK, joten tämä on linkitetty lista.
Joten tämä on skenaario kyseessä.
Ja todellakin, tämä on tyypillinen luokan ongelmia
että saatat yrittää ratkaista koodilla.
Haluat lopulta lisätä uusi elementti luettelosta.
Tässä tapauksessa aiomme kokeile asettaa numero 55.
Mutta siellä tulee olemaan eri tapauksissa harkita.
Ja todellakin, tämä tulee olemaan yksi iso-kuva takeaways täällä on,
mitkä ovat eri tapauksia.
Mitä eri jos olosuhteet tai oksat, että ohjelma voisi olla?
>> No, numero yrität insertti, jonka tiedämme nyt olevan 55,
mutta jos et tiedä etukäteen, rohkenen sanoa
kuuluu ainakin kolmeen mahdolliset tilanteet.
Missä lienee uusi elementti olla?
Yleisö: Ja lopussa tai keskellä.
DAVID J. MALAN: Lopussa, vuonna keskellä tai alussa.
Joten väitän siellä ainakin kolme ongelmaa meidän on ratkaistava.
Valitaan mitä ehkä luultavasti yksinkertaisin
yksi, jos uusi elementti kuuluu alussa.
Joten aion olla koodin melko kuten haku, jonka minä vain kirjoitti.
Ja aion olla PTR, joka Minä edustan täällä minun sormi,
kuten tavallista.
>> Ja muistaa, mitä arvoa me alustaa PTR?
Joten me alustetaan se nollaamaan aluksi.
Mutta mitä sitten me teimme, kun olemme olivat sisällä hakutoiminto?
Asetimme sen yhtä ensin, mikä ei tarkoita näin.
Jos otan PTR yhtä ensin, mitä olisi käteni todella olla suunnattu?
Oikea.
Joten jos Gabe ja minä menemme olla samoja arvoja täällä,
meidän molemmat pisteeseen numero 9.
>> Joten tämä oli alku meidän tarina.
Ja nyt tämä on vain yksinkertainen, vaikka syntaksi on uusi.
Käsitteellisesti tämä on vain lineaarinen haku.
On 55 yhtä kuin 9?
Tai pikemminkin, sanokaamme alle 9.
Koska Yritän selvittää, mihin 55.
Alle 9, alle 17, alle yli 20, alle 22, alle 29,
alle 34, ei.
Joten nyt olemme asiassa yksi vähintään kolme.
>> Jos haluan lisätä 55 tänne, mitä riviä koodia täytyy saada toteuttaa?
Miten tämä kuva ihmisten täytyy muuttaa?
Mitä teen vasemmalla kädellä?
Tämän pitäisi olla null aluksi, koska olen lopussa luettelosta.
Ja mitä pitäisi tapahtua täällä Pietarin kanssa oli?
Hän on toki osoittaa minulle.
Joten väitän siellä ainakin kaksi riviä koodia mallikoodi tänään
joka tulee toteuttaa tämän skenaario lisätään 55 häntää.
Ja voisin olla joku hop ja vain edustavat 55?
Okei, olet uuden 55.
>> Joten nyt mitä jos seuraavaksi skenaario tulee pitkin,
ja haluamme lisätä osoitteessa alussa tai pään listalta?
Ja mikä on nimesi, numero 55?
>> Yleisö: Jack.
>> DAVID J. MALAN: Jack?
OK, kiva tavata.
Tervetuloa.
Joten nyt aiomme lisätä vaikkapa numero 5.
Tässä toisessa tapauksessa kolme keksimme ennen.
Joten jos 5 kuuluu alussa, Katsotaanpa, miten voimme selvittää asia.
Olen alustaa minun ptr osoitin numero 9 uudelleen.
Ja tajusin, oh, 5 on alle 9.
Korjatkaa tämä kuva meille.
Joiden kädet, Gaben tai Daavidin tai-- mikä numero 9: n nimi?
>> Yleisö: Jen.
>> DAVID J. MALAN: Jen hands-- joka kätemme täytyy muuttaa?
OK, joten Gabe muistuttaa, mitä nyt?
Minua.
Olen uusi solmu.
Joten minä vain sellainen liikkua Näytä se visuaalisesti.
Ja sillä välin mitä voin todeta, että?
Silti jossa minä osoitan.
Joten se siitä.
Joten oikeastaan ​​yksi rivi koodikorjaukset tässä kysymyksessä, se näyttäisi.
Kunnossa, niin se on hyvä.
Ja voi joku olla paikanpitäjä 5?
Tule ylös.
Saamme sinut seuraavan kerran.
>> Okei, joten now-- ja Sivuhuomautuksena, nimet
En tee nimenomaista mainintaa oikeus nyt pred osoitin, edeltäjä osoitin
ja uuden osoittimen, joka on vain annetut nimet
näytteessä koodin viitteitä tai käteni Sellainen osoittaa ympärillä.
Mikä sinun nimesi on?
>> Yleisö: Christine.
>> DAVID J. MALAN: Christine.
Tervetuloa.
Okei, joten Tarkastellaan nyt hieman harmittaa skenaario,
jolloin haluan lisätä jotain 26 tähän.
20?
Mitä?
Nämä are-- hyvä, että meillä on tämä kynä.
Okei, 20.
Jos joku voisi saada toisen palan paperin valmis, juuri case-- kunnossa.
Oh, mielenkiintoinen.
No tämä on esimerkki luennon bugi.
OK niin mikä nimesi olikaan?
Yleisö: Julia.
DAVID J. MALAN: Julia, voitko pop pois ja teeskennellä olit koskaan siellä?
OK, tämä ei koskaan tapahtunut.
Kiitos.
Joten kai haluamme lisätä Julia tähän linkitetty lista.
Hän on numero 20.
Ja tietysti hän on menossa kuuluvat osoitteessa
begin-- eivät viittaa vielä mitään.
Joten kätesi voi sellaista olla alas null tai jotkut roskat arvo.
Kerrotaan nopean tarinan.
Olen suunnattu numero 5 tällä kertaa.
Sitten voin tarkistaa 9.
Sitten voin tarkistaa 17.
Sitten voin tarkistaa 22.
Ja ymmärrän, ooh, Julia tarvitsee mennä ennen 22.
Joten mitä pitää tapahtua?
Joiden kädet täytyy muuttaa?
Julia, minun, tai-- Mikä sinun nimesi olikaan?
>> Yleisö: Christian.
>> DAVID J. MALAN: Christian tai?
>> Yleisö: Andy.
>> DAVID J. MALAN: Andy.
Christian tai Andy?
Andy tarvitsee pisteeseen?
Julia.
Kunnossa.
Joten Andy, haluatko pisteeseen Julia?
Mutta hetkinen.
Vuonna tarina tähän mennessä, Olen tavallaan yksi
vastuussa, siinä mielessä, että osoitin on asia, joka on
liikkuvat läpi listan.
Meillä saattaa olla nimi Andy, mutta ei ole muuttuja nimeltään Andy.
Ainoa muuttuja meillä on Ensimmäinen, joka on edustettuna Gabe.
>> Joten tämä on todella, miksi näin asti olemme ei tarvita tätä.
Mutta nyt ruudulla on mainita jälleen ennustearvo osoittimen.
Joten anna minun olla täsmällisempi.
Jos tämä on osoitin, minulla oli parempi saada hieman enemmän älykkäitä
minun iterointia.
Jos et pahastu eletään täällä taas osoittaa täällä, osoittaa täällä.
Mutta haluan olla ennustearvo osoitin, edeltäjä osoitin, joka on
Tällainen suunnattu elementti Olin juuri.
Joten kun menen tänne, nyt minun vasen käsi päivityksiä.
Kun menen tänne minun vasen käsi päivityksiä.
Ja nyt minulla ei vain osoitin elementti, joka menee jälkeen Julia,
Minulla on vielä osoitin Andy, elementti ennen.
Joten sinulla on mahdollisuus saada tietää, korppujauhoja, jos haluatte,
kaikki vaaditun viitteitä.
>> Joten jos olen osoittaen Andy ja olen myös osoittaa
klo Christian, joiden kädet Nyt olisi todettava muualla?
Joten Andy voi nyt osoitat Julia.
Julia voi nyt osoitat Christian.
Koska hän voi kopioida minun oikean käden osoitin.
Ja että tehokkaasti vie sinut takaisin tähän paikkaan täällä.
Niin lyhyt, vaikka tämä vie meidät tavallaan ikuisesti
itse päivittää linkitetty lista, ymmärtää
että toiminta ovat suhteellisen yksinkertaisia.
Se on yksi, kaksi, kolme riviä koodia lopulta.
Mutta kiedottu nämä riviä koodia oletettavasti
on vähän logiikkaa, joka tehokkaasti kysyy kysymyksen, missä olemme?
Olemmeko alussa, keskimmäinen, tai loppua?
>> Nyt varmasti joitakin muita toiminnot voisimme toteuttaa.
Ja nämä kuvat täällä vain kuvata mitä me vain teimme ihmisten kanssa.
Entä poisto?
Jos haluan esimerkiksi Poista numero 34 tai 55,
Saatan olla samanlaista koodia, mutta aion tarvitaan yksi tai kaksi vaihetta.
Koska mitä uutta?
Jos poistan jonkun lopussa, kuten numero 55 ja sitten 34,
mitä täytyy myös muuttaa kuin minä, että?
Täytyy ole evict-- Mikä sinun nimesi olikaan?
>> Yleisö: Jack.
>> DAVID J. MALAN: Jack.
Minun on paitsi evict-- ilmaiseksi Jack, niin kirjaimellisesti soittaa ilmaiseksi Jack, tai ainakin
osoitin sielläkin, mutta nyt Tarvittavien muutosten Peter?
Hänen kätensä parempi alkaa osoittaa alaspäin.
Koska heti kun kehotan ilmaiseksi Jack, jos Pietarin vielä osoittaen Jack
ja siksi pitää liikkumisesta lista ja käyttää tätä osoitinta,
silloin meidän vanha ystävä segmentointi vika voi todella potkia.
Koska olemme antaneet muisti takaisin Jack.
>> Voit pysyä siellä hankalasti vain hetken.
Koska meillä on vain pari loppukäsittelyinä harkita.
Pään poistaminen luettelosta, tai beginning-- ja tämä on
vähän harmittaa.
Koska meidän täytyy tietää, että Gabe on sellainen erityinen tässä ohjelmassa.
Koska todellakin, hänellä on oma osoitin.
Hän ei vain on suunnattu, kuten lähes kaikki muutkin täällä.
>> Joten kun pää luettelo on poistettiin, joiden kädet täytyy muuttaa nyt?
Mikä nimesi olikaan?
>> Yleisö: Christine.
>> DAVID J. MALAN: Olen kauhea klo nimiä, ilmeisesti.
Joten Christine ja Gabe, joiden kädet täytyy muuttaa
kun yritämme poistaa Christine, numero 5, kuvasta?
OK, joten tehkäämme Gabe.
Gabe menee kohtaan, oletettavasti, numero 9.
Mutta mitä seuraavaksi pitäisi tapahtua?
Yleisö: Christine pitäisi olla null [äänetön].
DAVID J. MALAN: OK, meidän pitäisi luultavasti make-- kuulin "null" jonnekin.
Yleisö: Null ja vapaa häntä.
DAVID J. MALAN: null mitä?
Yleisö: Null ja vapaa häntä.
DAVID J. MALAN: Null ja vapaa häntä.
Joten tämä on erittäin helppoa.
Ja se on täydellinen, että olet nyt tavallaan seisovan siellä, ei omistaja.
Koska olet ollut irrotettu luettelosta.
Olet samalla ollut orvoksi listasta.
Ja niin meidän on parasta soittaa ilmaiseksi nyt Christine antaa että muisti takaisin.
Muuten joka kerta poistaa solmun listasta
saatamme tehdä lista lyhyempi, mutta ei oikeastaan ​​laskussa
koon muistiin.
Joten jos pitää lisätä ja lisäämällä, lisäämällä asioita listalle
tietokone saattaa hidastua ja hitaammin ja hitaammin,
koska olen loppumassa muistiin, vaikka en ole oikeastaan
käyttäen Christine tavut muistia enää.
>> Joten lopulta on muitakin skenaarioita, ja course-- poisto
keskellä, poisto lopussa, kuten näimme.
Mutta mielenkiintoisempaa Nyt haasteena on
olemaan harkita tarkasti mitä käyntiaika on.
Niin ei vain voi pitää paperinpaloja, jos Gabe,
et mielessä antaa jokainen stressipallo.
Kiitos paljon meidän linkitetty lista Vapaaehtoisten täällä, jos voisit.
>> [APPLAUSE]
>> DAVID J. MALAN: Okei.
Joten pari analyyttinen kysymyksiä niin, jos voisin.
Olemme nähneet tämän merkintätapa ennen, iso O ja omega, ylärajan
ja alarajat ajoaika noin algoritmin.
Joten harkita vain pari kysymystä.
>> Yksi, ja sanoimme sen ennen, mikä on käynnissä
aika etsiä lista kannalta iso O?
Mikä yläraja käynnissä aika etsiä linkitetyn listan
toteutettuna vapaaehtoistemme täällä?
Se on iso O n, lineaarinen.
Koska pahimmassa tapauksessa, elementti, kuten 55,
saatamme olla etsimässä voisi olla, Jack oli aina lopussa.
Ja valitettavasti, toisin kuin array emme voi saada fancy tällä kertaa.
Vaikka kaikki meidän ihmiset olivat lajitellaan pienistä elementeistä, 5,
kaikki tavalla jopa isompi elementti, 55, joka on yleensä hyvä asia.
Mutta mitä se oletus enää antaa meille mahdollisuuden tehdä?
Yleisö: [kuulumaton]
DAVID J. MALAN: Sano uudestaan?
Yleisö: Random access.
DAVID J. MALAN: Random access.
Ja taas se tarkoittaa, emme voi mitään enää käytä heikko nollia, intuitio,
ja ilmeisyyttä binäärilukujen etsiä ja jakaa ja valloittaa.
Sillä vaikka me Ihmiset voisivat ilmeisesti
nähdä, että Andy tai kristitty olivat suunnilleen keskellä luettelon,
tiedämme vain, että tietokone kuorimalla lista
alusta alkaen.
Joten olemme luopuneet että random access.
>> Niin iso O n on nyt ylempi sidottu meidän hakuaika.
Entä omega etsiä?
Mikä on alaraja etsimisestä joillekin numero tässä listassa?
Yleisö: [kuulumaton]
DAVID J. MALAN: Sano uudestaan?
Yleisö: Yksi.
DAVID J. MALAN: One.
Niin vakioaikaisia.
Parhaassa tapauksessa Christine on todellakin alussa luettelon.
Ja etsimme numero 5, joten löysimme hänet.
Joten no big deal.
Mutta hänellä olevan luettelon alkuun tässä asiassa.
Entä jotain Delete?
Mitä jos haluat poistaa elementin?
Mikä on yläraja ja alaraja poistamisesta jotain sidoksissa
listata?
Yleisö: [kuulumaton]
DAVID J. MALAN: Sano uudestaan?
Yleisö: n.
DAVID J. MALAN: n on todellakin yläraja.
Koska pahimmassa tapauksessa yritämme poistaa Jack, kuten me vain teimme.
Hän on aina lopussa.
Vie meidät ikuisesti, tai n vaiheet löytää hänet.
Niin, että yläraja.
Se on lineaarinen, varmasti.
Ja parhaassa tapauksessa ajoaika, tai alarajoja parhaassa tapauksessa
olisi vakioaikaisia.
Koska ehkä me yritetään poistaa Christine, ja me vain onnekas
hän alussa.
Hetkinen.
Gabe oli myös alussa, ja meillä oli myös päivittää Gabe.
Niin että ei ollut vain yksi askel.
Onko siis todellakin jatkuvaa aikaa, parhaassa tapauksessa
poistaa pienimmän alkion?
Se on, vaikka se voi olla kaksi, kolme tai jopa 100 riviä koodia,
jos se on sama määrä linjat, ei joissakin silmukka,
ja riippumaton koko luettelon, ehdottomasti.
Poistamalla elementin listan alkuun,
vaikka meidän on käsiteltävä Gabe, on yhä jatkuva aika.
>> Joten tämä tuntuu massiivinen askel taaksepäin.
Ja mitä ajanhukkaa jos viikolla yksi ja viikko
nolla meillä oli paitsi pseudokoodilla koodi mutta varsinainen koodi
toteuttaa jotain, joka on log base n, tai kirjaudu pikemminkin N, pohja 2,
kannalta sen käyntiaika.
Joten miksi hitossa haluaisimme aloittaa käyttäen jotain linkitetty lista?
Joo.
>> Yleisö: Joten voit lisätä elementtejä array.
DAVID J. MALAN: Voit siis lisätä elementtejä array.
Ja tämäkin on temaattinen.
Ja jatkamme nähdä tämä, tämä kompromissi, paljon
kuten olemme nähneet kompromissi yhdistämisjäljitystä tavallaan.
Voisimme todella nopeuttaa etsiä tai lajittelu, pikemminkin
jos käytämme hieman enemmän tilaa ja on vielä kimpale muistia
tai matriisia yhdistämisen lajitella.
Mutta kulutamme enemmän tilaa, mutta säästämme aikaa.
Tässä tapauksessa olemme luopumassa aikaa, mutta olemme
saada joustavuutta, dynaamisuus jos haluatte,
joka on kiistatta myönteinen ominaisuus.
>> Olemme myös menoja tilaa.
Missä mielessä on sidoksissa luetella kalliimpia
suhteen tilaa kuin array?
Jos on ylimääräistä tilaa tulee?
Joo?
>> Yleisö: [kuulumaton] osoitin.
>> DAVID J. MALAN: Joo, me myös osoitin.
Joten tämä on minorly ärsyttävää että enää am
Olen tallentamiseen vain int edustaa int.
Olen tallentamiseen int ja osoitin, joka on myös 32 bittiä.
Joten olen kirjaimellisesti kaksinkertaistaa paljon tilaa mukana.
Niin, että kompromisseja, mutta se kun on kyse int.
Oletetaan, että et ole tallentamiseen int, mutta kai jokainen näistä suorakaide
tai kaikkien näiden ihmisten edusti sana, Englanti sana, joka
voi olla viisi merkkiä, 10 merkkiä, ehkä jopa enemmän.
Sitten lisätään vain 32 enemmän bittejä saattaa aiheuttaa vähemmän iso juttu.
>> Mitä jos jokainen opiskelijat mielenosoitukseen
olivat kirjaimellisesti opiskelija structs että on nimet ja taloja ja ehkä
puhelinnumeroita ja Twitter käsittelee ja vastaavat.
Joten kaikki kentät aloitimme puhumme toinen päivä,
paljon vähemmän iso juttu kuin meidän solmut saavat mielenkiintoisempaa
ja iso viettää, eh, ylimääräinen osoitin vain liittää ne yhteen.
Mutta tosiaan, se on kompromissi.
Ja todellakin, koodi on monimutkaisempi, koska sinun
katso kuorimalla läpi että erityinen esimerkki.
Mutta mitä jos oli Joissakin Graalin malja täällä.
Mitä jos emme ota askel taaksepäin mutta valtava edistysaskel
ja toteuttaa datan rakenne, jonka kautta me
voi löytää elementtejä, kuten Jack tai Christine tai muita osia
Tässä array totta vakioaikavälein?
Haku on jatkuva.
Delete on vakio.
Insertti on vakio.
Kaikki nämä toiminnot ovat vakioita.
Se olisi meidän pyhä Graal.
Ja sinne me poimia seuraavan kerran.
Nähdään sitten.