>> DAVID MALAN: Okei.
Tervetuloa takaisin CS50.
Tämä on alku viikolla 8.
Ja muistaa, että ongelma asetettu 5 päättyi kanssa hieman haastetta.
Joten olettaen talteen kaikki Opetuksen Fellows ja CA: n valokuvia
vuonna card.raw tiedoston, olet oikeutettu nyt löytää kaikki ne ihmiset, ja
yksi onnekas voittaja kävellä kotiin yhdellä näistä asioista, harppaus liikettä
laite, että voit käyttää lopullisen hankkeita, esimerkiksi.
>> Tämä, joka vuosi, johtaa vähän creepiness.
Ja niin mitä ajattelin tehdä, on kertoa teille joitakin säveliä, jotka ovat
mennyt edestakaisin henkilöstön luettelo myöhään.
Esimerkiksi juuri viime yönä, lainaus listatut, yhdestä henkilöstön
jäsenet, "Minulla oli opiskelija knock oveni ottaa valokuvan kanssani.
Stalkers, minä sanon teille. "Aloitit melko kuvaileva ja sitten muutimme
edelleen, tunti tai niin myöhemmin, "Minulla oli opiskelija odottaa minua jakson jälkeen
Hän oli meidän kaikkien nimet ja kuvat joitakin arkkia paperia. "Selvä.
Niin järjestetty, mutta ei kaikki kammottava vielä.
>> Sitten, "Olin poissa kaupungista tänä viikonloppuna, ja kun tulin takaisin, oli yksi
minun
makuuhuone. "[naurua]
DAVID MALAN: Seuraava lainaus henkilöstö jäsen ", opiskelija tuli kotiini
Somerville kello 4 aamulla. "Seuraava henkilökunta, "pääsin hotelli San
Francisco ja opiskelija odotti minua aulassa kolme DSLRs. "
Tyyppinen kamera.
"En ole edes henkilökuntaa tämän lukukauden, mutta opiskelija murtautui talooni tämän
aamu ja kirjataan koko juttu Google Glass. "Ja sitten lopuksi,
"Ainakin 12 ihmistä olivat innokkaasti odottavat minua, kun sain ulos
limusiinin, ja sitten minä
heräsi. "Selvä.
Joten keskuudessa valokuvia, kuten ehkä muistaa, ovat tämän kaveri täällä, kuka olet
voi tietää kuin Milo Banana, joka asuu Lauren Carvalho, meidän pään
opetus Fellow.
Milo, Milo, tule tänne poika.
Milo.
Huomatkaa, hän on päällään Google Glass, joten näytämme sinulle kaiken tämän jälkeen.
Joten tämä on Milo, jos haluat ottaa valokuvan hänestä jälkeenpäin.
Jos haluat varoa yleisöön siellä.
OK.
Se on hyvä kuvamateriaalia.
No, Milo Banana.
Voi, älä tee sitä.
>> [Naurua]
>> OK.
Joten sana sitten mitä on edessä, sillä kun alamme siirtyminen,
tällä viikolla nimenomaan, alkaen C komentoriviympäristössä PHP ja
JavaScript ja SQL ja HTML ja CSS web-pohjainen ympäristö, me olemme
varustaminen sinulle kaikki lisää tietämystä
mahdollisten lopullisten hankkeita.
Kohti sitä varten kurssi on perinteisesti järjestetty seminaareja, jotka
ovat sivuaa aiheita sen kurssin.
Hyvin paljon ohjelmointia ja app kehitystä ja niin edelleen, mutta
ei välttämättä selvittävät Tietenkin oma oppimäärä.
>> Joten jos saatat olla kiinnostunut yksi tai enemmän tämän vuoden seminaareja,
rekisteröityä cs50.net/seminar.
On vanhempia seminaarit klo cs50.net/seminars.
Ja lista tähän mennessä tänä vuonna ovat Amazing Web Apps kanssa Ruby on
Kiskot, joka on vaihtoehtoinen kieli PHP.
Computational Linguistics.
Johdatus IOS, joka on alustan, joka käyttää iPhone ja
iPad kehitystä.
JavaScript Web Apps, me kattaa että, mutta tässä seminaarissa, voit mennä
yksityiskohtaisempi.
>> Leap Motion, niin me todella on joitakin meidän ystäviä Leap Motion,
yhtiölle itselleen, liittyä meihin.
Huomenna, itse asiassa, jotta voidaan tarjota käytännön seminaarin, jos
kiinnostaa sinua.
Meteor.js, vaihtoehtoinen tekniikka JavaScriptin avulla ei selain,
mutta palvelimella.
Node.js, joka on hyvin paljon että vein samoin.
Tyylikäs Android muotoilu.
Android on erittäin suosittu vaihtoehto iOS ja Windows Phone
ja muut mobiilialustoille.
Ja Web Security Active Defense.
>> Joten itse asiassa, jos haluat osallistua tähän, haluan
muistiin tämän.
Olemme erittäin iloinen voidessani todeta, että ystävämme Leap
Motion, joka on käynnistyksen -
tämä laite todella vain tuli muutama kuukausi sitten -
on armollisesti lahjoitti 30 tällaisia ​​laitteita luokkaan, niin monet opiskelijat, jos
haluat lainata laitteisto kohti lukukauden lopussa ja käyttää sitä
Varsinainen opinnäytetyön.
Ne tukevat useita kieliä.
Mikään niistä C, mikään niistä PHP, niin saavuttamaan yksi tai useampi näistä seminaareja
saattaa osoittautua kohteisiin.
Ja ne kaikki on kuvattu Jos et pysty
osallistua henkilökohtaisesti.
Aikataulu julkistetaan kautta email me jähmettyä huonetta.
>> Ja lopuksi, jos menet projects.cs.50.net, tämä on sivusto
meidän pitää joka vuosi, että kutsumme folks yhteisö, tiedekunta,
yksiköt, henkilökunta ja molemmat in ulkopuolella CS50 on
ehdottaa projekti-ideoita.
Asiat kiinnostavat opiskelijaryhmille.
Kiinnostavia asioita osastojen.
Joten älä käännä siellä, jos olet kamppailee epävarmuutta siitä, mitä
itse haluaisi puuttua.
>> Joten viimeinen kerta toimme kiistatta monimutkaisempi tietorakenne kuin olimme
nähdään viikkoa aikaisemmin.
Olimme käyttäen paneelit melko onnellisina hyödyllistä, jos
yksinkertainen tietorakenne.
Sitten otimme käyttöön nämä, jotka tietenkin liittyvät luettelot.
Ja mikä oli yksi motiiveja käyttöön tämän tietorakenne?
Niin?
Mikä tuo on?
>> Yleisö: Dynamic koko.
>> DAVID MALAN: Dynamic koko.
Joten taas joukko, joudut tietää sen koko etukäteen, kun
voit jakaa sitä.
Vuonna linkitetty lista, et täytyy tietää, että.
Voit vain malloc, tai yleisemmin myöntää lisää
solmu, niin sanotusti, milloin tahansa haluat lisätä enemmän tietoa.
Ja solmu ei ole ennalta määrättyä merkitystä.
Se on vain yleinen termi, joka kuvaa jonkinlainen säiliö, että olemme
käyttämällä meidän tietorakenne tallentaa jotkut erä kohteisiin, jotka tässä
Jos sattuvat olemaan kokonaislukuja.
>> Mutta on aina kompromissi.
Joten saamme dynaaminen koot tiedot rakenne, mutta paljonko maksaa me maksamme?
Mitä haittapuoli linkitettyjen listojen?
Niin?
>> Yleisö: Vaatii enemmän muistia.
>> DAVID MALAN: se vaatii enemmän muisti, miten tarkalleen?
>> Yleisö: [kuultavissa].
>> DAVID MALAN: Aivan.
Joten nyt meillä on viitteitä aloittamisesta lisämuistia, että aiemmin
ei tarvitse, koska etu array, on tietenkin se, että
kaikki on yhtenäinen, takaisin takaisin takaisin, joka
antaa random access.
Koska vain käyttämällä hakasulkeen merkintä, tai teknisesti osoitin
aritmeettinen, hyvin yksinkertainen Lisäksi Pääsetkö
elementit jatkuvasti ajan.
Ja itse asiassa, että on tavallaan vihjaten toinen hinta, että maksat kanssa
linkitetty lista.
>> Mitä tapahtuu käyntiaika jotain Etsi, jos haluan
löytää arvo ja sisällä of linkitetty lista?
Mitä minun käyntiaika tullut?
Big O n.
Jos se lajitellaan?
Mitä jos tietorakenne on järjestetty?
Voinko tehdä paremmin kuin suuret O n etsimiseen?
Ei, koska pahimmassa tapauksessa se voisi hyvin lajitellaan, mutta määrä
etsit saattaa olla suuri.
Se voi olla numero 100, joka ehkä sattuvat olemaan kaikki
Muuten lopussa.
Ja koska voit käyttää vain linkitetyn Luettelen tällä täytäntöönpano
tapa sen ensimmäisen solmun, olet vielä sellainen epäonninen.
Sinun täytyy kulkea koko juttu ensimmäisestä viimeiseen, jotta löydettäisiin
että iso arvo kuin 100.
Tai onko se ei edes siellä.
>> Joten emme voi tehdä mitä algoritmia datan rakenne, joka näyttää tältä?
Emme voi tehdä binäärihaku, koska binäärihaku vaaditaan, että meillä oli
random access.
Voisimme vain harppaus sijainnista sijainti ilman seuraa
Näiden korppujauhoja muodossa kaikki nämä viitteet.
>> Nyt, miten voimme toteuttaa tämän?
No, jos menemme näytön täällä, jos Voimme nopeasti reimplement nämä tiedot
rakenne -
minun käsiala ei ole kaikki, että hyvä täällä, mutta me yritämme.
Joten struct, ja mitä tein haluat soittaa tämä asia täällä?
Solmu.
Joten Haen alkoi.
Ja nyt, mitä pitää sisällä datarakenteen, että yksittäin
linkitetty lista?
Kuinka monilla aloilla?
>> Joten kaksi.
Yksi on melko helppoa.
Joten int n.
Ja voisimme kutsua n mitä me haluamme, mutta sen pitäisi olla int, jos olemme
täytäntöön linkitetty lista ints.
Ja nyt, mitä tekee toinen alan olla?
Struct solmu *.
Joten jos en struct solmu *, ja sitten minä voi kutsua tätä myös mitä haluan,
mutta vain olla selkeä soitan sitä seuraava, kuten olemme tehneet.
Ja sitten minä suljen aaltosulkeita.
>> Ja nyt, kuin viime kerralla, Laitoin solmun tänne.
Mutta jos olen julistaa tämä on niin solmu, miksi olen vaivautua on niin
verbose täällä julistaa struct solmu * seuraavaksi, toisin
vain solmu * seuraavaksi?
Niin?
>> Yleisö: [kuultavissa].
>> DAVID MALAN: Aivan.
Täsmälleen.
Koska C todella vie kirjaimellisesti ja näkee vain määritelmän solmun
alas täällä, et voi viitata siihen täällä.
Joten meillä on tällainen ennaltaehkäisevä ilmoitus täällä, joka on tosin
Pidempi.
Struct solmu, joka tarkoittaa voimme nyt käyttää sitä
sisällä tieto-rakenteesta.
>> Ja syrjään, koska tämä on tulossa hieman subjektiivinen nyt
tähti voi teknisesti mennä täällä, se voi mennä täällä, se voi
jopa mennä keskellä.
Olemme hyväksytty, tyyliin opas Tietenkin yleissopimus laskemisesta
tähden vieressä tiedot tyyppi, joka tässä tapauksessa
olisi struct solmu.
Mutta realisoida paljon oppikirjoja ja online-viittauksia, saatat todellakin
nähdä sen toisella puolella.
Mutta vain ymmärtää, että molemmat todella työtä ja sinun pitäisi vain olla
johdonmukainen.
>> Selvä.
Niin, että oli meidän ilmoitus struct solmu.
Mutta sitten aloimme tehdä enemmän kehittyneempiä asioita.
Esimerkiksi päätimme ottaa käyttöön jotain tiiviste.
Joten tässä on hash taulukon koko on n, indeksoitu 0 päälle vasemmalle n
miinus 1 vasemmassa alareunassa.
Tämä voisi olla hash taulukossa mitään.
Mutta millaisia ​​asioita ei puhumme noin käyttämällä hash taulukon?
Tallentaminen mitä?
>> Nimet.
Voisimme tehdä nimiä kuten teimme viime kerralla.
Ja oikeastaan, voit tallentaa mitään.
Ja näemme tämän uudelleen PHP ja JavaScript.
Tiiviste on mukava eräänlainen Sveitsin Armeijan veitsi, jonka avulla voit tallentaa
aika paljon mitä haluat sisällä se liittämällä avaimet arvot.
Avaimet arvot.
>> Nyt tässä yksinkertaisessa tapauksessa meidän avaimet ovat vain numeroita.
Olemme täytäntöönpanosta hash taulukon array.
Ja niin näppäimet ovat 0, 1, 2, ja niin edelleen.
Ja niin me, ihmisinä, päätti viime viikolla, että tiedät mitä, jos olemme
menossa tallentaa nimiä, haluan vain mielivaltaisesti, vaan ihan kohtuullisesti,
olettaa, että Alice, nimi, vain indeksoidaan 0.
Ja Bob, B nimen, indeksoidaan otetaan 1, ja niin edelleen.
Joten meillä oli kartoitus tulojen välillä, jotka ovat jouset, ja hash
paikoissa, jotka ovat numeroita.
>> Niin, että prosessi on yleisesti tunnettu hash funktio, ja voit todella
pantava se koodi.
Jos halusin toteuttaa hajautusfunktio joka tekee täsmälleen mitä me
juuri kuvattu viime aikaa, voisin julistaa funktio, joka ottaa, koska
input esimerkiksi -
ja tehdään tämä tästä näytön tänne.
Jos halusin toteuttaa hash toiminto, voisin sanoa
jotain tällaista.
>> Se tulee palauttaa int.
Se tulee kutsua hash, ja se on aio hyväksyä väitettä
string, tai voimme olla oikeampi nyt ja sanoa char *, me kutsumme sitä s.
Ja sitten kaikki tämä toiminto on tekemistä, lopulta on palauttaa int.
Nyt, miten se, että saattaisi ei ole niin selvä.
Aion toteuttaa tätä ilman muodossa virheentarkistusta juuri nyt.
Olen juuri menossa sokeasti sanoa, palauta mitä on s kiinnike 0, miinus,
sanotaanko, pääoman puolipiste.
>> Täysin rikki.
Se ei ole täydellinen, koska yksi, mitä jos s on nolla?
Pahoja asioita tapahtuu.
Kaksi, mitä jos ensimmäinen kirjain tässä nimi ei ole kirjain?
Se ei tule kääntää ulos hyvin joko.
Se voi olla pieni kirjain tai kirjeen ollenkaan.
Joten täysin parantamisen varaa, mutta tämä on perusajatus.
>> Mitä me kuvattu viime viikolla sanallisesti vain kartoituksesta Alice
0 ja Bob 1 voidaan ilmaista varmasti enemmän formulaically kuin C
toimi täällä.
Kutsutaan uudelleen hash, vie merkkijonon tulo, ja sitten jotenkin tekee jotain
kanssa tulo tuottaa tuotoksen.
Ei toisin kuin meidän musta laatikko kuvaus että olemme pitkään tehneet.
En tiedä, miten tämä voisi olla työskentelevät alla huppu.
>> Jos ongelma asettaa 6, yksi haasteista on sinun päättää, mitä
tulee teidän hajautusfunktio olla?
Mikä tulee olemaan sisällä että musta ruutuun, ja oletettavasti se tulee olemaan
hieman mielenkiintoisemman kuin tämä, ja varmasti enemmän virhealtista
tarkkailun kuin tässä täytäntöönpanoa.
>> Mutta ongelmia voi syntyä, eikö?
Jos meillä on tietorakenne kuten tämän yksi, mikä on yksi ongelmista
voit törmätä ajan, kun asetat enemmän ja enemmän nimiä
tiiviste?
Saat törmäykset, eikö?
Mitä jos sinulla on Alice ja Aaron, kaksi ihmistä, joiden nimet tapahtui
aloittaa?
Tässä herääkin kysymys, missä laita toinen tällainen nimi?
>> No, ehkä naiivisti laittaa sen jossa Bob kuuluu, mutta sitten Bob on
Tällainen ruuvattu jos yrität lisätä hänen nimensä vieressä ja
Ei ole tilaa hänelle.
Joten voit saattaa Bob missä Charlie on, ja voitte kuvitella tämän hyvin nopeasti
hajauttaa osaksi hieman sekaisin.
Jotain lineaarinen lopussa, jossa täytyy vain etsiä koko juttu
etsivät Alice tai Bob tai Aaron tai Charlie.
>> Joten sen sijaan ehdotimme, eikä vain lineaarisesti luotaa aukiot
ja plopping nimet siellä, me ehdotti harrastaja lähestymistapaa.
Tiiviste toteutettu silti joukko indeksejä, mutta tietotyyppi
nämä indeksit olivat nyt viitteitä.
Viitteitä mitä?
Osoittimet liittyvät luettelot.
>> Koska muistaa, että linkitetty lista on oikeastaan ​​vain osoitin solmuun, ja
solmu on seuraavaan kenttään, ja että solmu on seuraava kenttä, ja niin edelleen.
Joten nyt voit ajatella tätä array vasemmalla puolella hash-taulukon
mikä linkitetty lista.
Etuna on, jos saat yhteentörmäys Alice ja Aaron,
mitä te teette Toinen tällainen henkilö?
Sinä vain liittää hänet loppuun, tai jopa alussa
Tämän linkitetty lista.
>> Ja oikeastaan ​​haluan vain nuudeli kautta että vain toinen.
Jos olisi mielekästä?
Jos asetan Alice ja hän päätyy ensimmäinen paikka, sitten yritän
aseta Aaronin nimi, ja siellä on ilmeisesti törmäyksen, minun pitäisi laittaa
hänelle alussa on linkitetty lista?
Se on, että ensimmäinen paikka, tai lopussa?
>> Yleisö: [kuultavissa].
>> DAVID MALAN: OK.
Kuulin alussa.
Miksi alussa?
>> Yleisö: [kuultavissa].
>> DAVID MALAN: OK.
Se on aakkosjärjestyksessä, joten on mukavaa.
Se on hyvä ominaisuus.
Se säästää minulle aikaa mahdollisesti.
Se ei anna minun tehdä binäärihaku, mutta voisi ainakin voi puhjeta
loop-jos ymmärrän hyvin, olen niin aiemmin olivat Aaron olisi tässä
lajiteltu linkitetty lista.
Minulla ei tarvitse tuhlata aikaa etsimässä aina loppuun.
Niin, että on kohtuullista.
Miksi muuten ehkä haluat lisätä törmäävän nimi on
listan alkuun?
Mikä tuo on?
>> Yleisö: [kuultavissa].
>> DAVID MALAN: Se voi kestää kauan päästä listan loppuun.
Ja itse asiassa, pidempään.
Enemmän nimiä asetat, että aloittaa, mitä kauemmin
ketju on menossa.
Enää, että linkitetty lista on menossa.
Joten olet todella vain tuhlaa aikaa.
Ehkä olet parempi säilyttää jatkuva asetettiin paikoilleen, iso O 1,
olemalla aina laittamalla törmätä nimitys alussa linkitetty lista,
eikä huolestuttava niin paljon lajitteluun.
>> Mikä on paras vastaus?
On epäselvää.
Se ikään kuin riippuu siitä, mitä jakelu on, mikä malli on
nimet asetat.
Se ei ole välttämättä ilmeinen vastaus.
Mutta täällä on taas suunnittelu tilaisuus.
>> Niin me sitten katsoin tämä asia, joka on todella toinen suuri mahdollisuus
p-set 6.
Ja ymmärtää, jos et ole jo, Zamyla sukeltaa molempia, hash
taulukoita ja yrittää, yksityiskohtaisemmin.
Ja videoesityksen on upotettu p-set spec.
Tämä oli trie -
T-R-I-E. Ja mikä oli mielenkiintoista Tämä oli se, että ajoaika
etsivät nimi, kuten Maxwell viime kerralla, oli iso O mitä?
Mikä tuo on?
>> Yleisö: määrä kirjaimia.
>> DAVID MALAN: Numero kirjeitä.
Kuulin kaksi asiaa.
Useita kirjeitä ja jatkuva ajan.
Joten mennä, että ensin.
Määrä kirjaimia.
No, tämä tietorakenne, muistaa, on kuten puu, sukupuu, kukin
jonka solmut koostuvat ryhmät.
Ja ne paneelit ovat osoittimia muita tällaisia ​​solmuja, tai muita sellaisia
taulukot puu.
>> Joten jos halusimme sitten määrittää onko Maxwell on täällä, voisin mennä
ensimmäiseen array, aivan huipulla puu, niin sanottu juuri, alkuun
trie ja noudata m osoitin, Sitten osoitin, niin x,
w, e, l, l.
Ja sitten kun näen joitakin erikoismerkkejä, merkitään täällä kolmio.
Koodin näet ehdotamme, että toteutetaan bool, vain sanomalla kyllä
tai no, sana loppuu tähän.
>> No, kun olemme menneet M--X-W-E-L-L, tuntuu seitsemän, ehkä
kahdeksan jos menemme ohi, kahdeksan ohjeita löytää Maxwell.
Tai kutsutaan sitä K. Mutta muistaa viimeksi aikaa, totesin, että jos siellä
realistisesti maksimipituus on sana, kuten 40-joitakin-kummallisia merkkejä,
enimmäispituus merkitsee vakioarvo.
Siis todella, kyllä, se on teknisesti iso O 8 tai 7, tai oikeastaan ​​iso O K. Mutta
jos on rajallinen korkki mitä K voisi olla, se on vakio.
Ja niin se on iso O 1 at päivän päätteeksi.
>> Ei todellisessa maailmassa.
Ei kun todella alkaa katsella kellon kuin ohjelman käynnissä.
Se ehdottomasti olemaan hieman hitaammin kuin todella jatkuvasti
aikaa yksi askel.
Se tulee olemaan seitsemän tai kahdeksan vaihetta, mutta silti se on paljon, paljon parempi
kuin algoritmi iso O n että riippuu koosta mitä on
tietorakenne.
>> Huomaa ylösalaisin tässä voimme lisätä euroa enemmän nimiä tähän
tietorakenne, mutta kuinka paljon enemmän vaiheita se aikoo viedä meidät löytää
Maxwell tässä tapauksessa?
Ei mitään.
Hän on ennallaan.
Ja tähän mennessä, en usko, olemme nähneet Esimerkkinä tietojen rakenteen tai
algoritmi, joka oli täysin vaikuta ulkoiset
käyttäytymistä niin.
Mutta tämä ei voi olla hämmästyttävä.
Tämä ei voi olla ainoa ratkaisu ja p-set
>> Ja se ei ole.
Tämä ei välttämättä ole tietoa rakenne pitäisi kallistua,
koska kuten hash taulukoita, kompromissi.
Mikä on hinta maksat täällä?
Muisti.
Tarkoitan, tämä on kamalaa muistin määrä.
Ja et oikein näe sitä täällä, koska Kirjailija tämän kuvan
ilmeisesti katkaistu kaikki paneelit ja emme näe paljon n ja
B: n ja C: n ja Q: n ja Y: n ja Z: n näissä ryhmät.
Mutta ne ovat siellä.
>> Jokainen näistä solmuista on koko joukko on noin 26 tavua tai useampia tavuja, ja jokainen
mikä kirjain.
27 meidän tapauksessamme, jotta voimme tukea heittomerkit ongelma set.
Joten tämä tieto rakenne on todella, todella tiheä ja leveä.
Ja että yksin päätyä hidastaa asioita alas, tai ainakin maksaa sinulle
paljon enemmän tilaa.
Mutta jälleen kerran, voimme tehdä vertailuja tässä.
>> Recall taas takaisin, olemme saavuttaneet paljon jännittävämpää käyntiaika lajittelu
kun käytämme yhdistäminen tavallaan, mutta hinta maksoimme saavuttaa n log n ja yhdistäminen
sort vaaditaan, että käytämme enemmän mitä resursseja?
Enemmän tilaa.
Tarvitsimme toisen array kopioida ihmisiä, aivan kuten
teimme täällä lavalla.
Joten jälleen, ei ole selvää voittajaa, mutta vain subjektiivinen suunnittelu
päätökset tehdään.
>> Selvä.
Joten miten tästä?
Jokainen tunnistaa mikä D-Hall?
OK.
Joten me kolme tehdä.
Mather House.
Tässä siis Mather ruokasalissa.
Lyön vetoa, kaikki ruokasalia on pinot tarjottimia näin.
Ja tämä on todella edustava jotain olemme
ilmeisesti nähnyt jo.
Kutsuimme sitä kirjaimellisesti pino.
Ja pino, mitä teidän tietokoneen muistiin, on, jos data menee
kun toimintoja on kutsuttu.
>> Esimerkiksi millaisia ​​asiat menevät pinoon nähden
Muistin sijoittelu olemme keskustelleet viikkoina aikaisemmin?
Mikä tuo on?
>> Yleisö: Puhelut toimintoja.
>> DAVID MALAN: Olen pahoillani.
>> Yleisö: Puhelut toimintoja.
>> DAVID MALAN: Puhelut toimintoja, mutta nimenomaan, mitä sisällä kunkin
näitä kehyksiä?
Millaiset asiat?
Joo.
Niin paikallisia muuttujia.
Aina kun tarvitaan joitakin paikallisia varastointi, kuten väite, tai int I, tai int
temp, tai mitä tahansa paikallisen muuttuja, olemme olleet
laskemisesta, että pinoon.
Ja me kutsumme sitä pino, koska Tämän kerrospukeutuminen idea.
Juuri sellainen otteluita jopa todellisuuden kanssa, käsite viipymättä.
>> Mutta näyttää siltä, ​​että pino voi myös pidettävä tietorakenne,
vaihtoehto array, vaihtoehtoisen on linkitetty lista.
Jotain käsitteellisesti mielenkiintoisempaa , joka voi vielä olla
toteutetaan käyttäen joko näiden asioita, mutta se on eri tyyppistä
tietorakenne tukevat, todella, vain kaksi operaatiota.
Mutta voit lisätä harrastaja ominaisuuksia kuin nämä.
Mutta nämä ovat perusasiat -
push ja pop.
>> Ja idea pino on, että jos minä täällä, tai ilman Annenberg
tietäen, lokero vieressä jossa numero 9 sitä.
Joten int.
Ja haluan ajaa tämän päälle tiedot rakenne, joka tällä hetkellä on tyhjä.
Mieti tätä pinon pohjalle.
Haluaisin ajaa tämän numeron 9 päälle pino, ja nyt se on tuolla.
>> Mutta mielenkiintoinen asia pino on, että jos en nyt halua työntää
jokin muu arvo, kuten 17, ja painan Tämän pinoon, aion tehdä
vain intuitiivinen asia, olen juuri menossa laittaa ne juuri siinä missä me ihmiset
olisivat taipuvaisia ​​laittaa sen, päälle.
Mutta mitä nyt mielenkiintoinen on, miten saan klo 9?
Tiedäthän, en ilman jonkin verran vaivaa.
>> Niin mitä mielenkiintoista pino on, että suunnittelu,
se LIFO tietorakenne.
Typerä tapa kuvata last in, first out.
Joten viimeinen numero tällä kertaa oli 17.
Joten jos haluan pop jotain pois pinon, se voi olla vain 17.
Joten on pakollista järjestyksessä toimintaa täällä, missä viimeinen kohde
siihen on oltava ensimmäinen ulos.
Näin lyhenne, LIFO.
>> Joten miksi tämä voisi olla hyödyllistä?
Ovatko ne puitteet, joissa olisit haluavat tietorakenne näin?
No, se on varmasti ollut hyötyä sisällä tietokoneen.
Joten käyttöjärjestelmien selvästi käyttää tätä Tällainen tietorakenne pinot.
Otamme myös nähdä sama ajatus kun se tulee web-sivuja.
Joten tällä viikolla ja ensi viikolla ja sen jälkeen, ja kun alkaa toteuttaa web
sivut kieltä kutsutaan HTML, voit itse käyttää tietorakenne kuten
Tämä määrittää, onko sivu on oikein muotoiltu.
Koska näemme kaikki sivut noudattavat eräänlainen hierarkia, syvennys
joka, lopussa päivä, olla puurakenne alla huppu.
Joten lisää, että vain vähän.
>> Mutta nyt, nyt ehdottaa hetkellä, miten voisimme edetä
eli mitä pino on?
Saanen ehdottaa, että toteutamme pino koodilla näin.
Joten pino tulee olemaan sen sisällä kaksi asiaa, array, nimeltään tarjottimia,
vain oltava demo.
Ja jokainen kohteita, että joukko tulee olemaan tyyppiä int.
Ja kapasiteetti on oletettavasti mitä?
Koska en ole kirjoittanut koko määritelmä täällä.
>> Se on luultavasti suurin koko joukko.
Ja se on luultavasti ilmoitettu terävä määritellä tiedoston alkuun, jotkut
Tällainen jatkuva kuten ehdotetun pelkkä arvo.
Joten jonnekin kapasiteetti määritellään kuin suurin mahdollinen koko.
Samaan aikaan, sisällä tietorakenteen tunnetaan pino siellä tulee
olla kokonaisluku vain tiedossa yksinkertaisesti koko.
>> Joten jos olisin edustamaan tätä nyt kuvallisesti Oletetaan, että tämä
koko musta laatikko edustaa minun pino.
Sisältä se on kaksi muuttujaa.
Joten aion tehdä Ensimmäinen kuin koko.
Ja toinen aion piirtää taulukkona.
>> Mutta vain pitää asiat hallittu, normaalisti Haluaisin kiinnittää array kuten
, mutta se on tavallaan mukavaa jos vastaa todellisuutta, tai
ottelu mielikuvaan.
Joten haluan sen sijaan kiinnittää array pystysuunnassa, joka on vain, jälleen,
taiteilijan luovuttamista.
Ei ole oikeastaan ​​väliä, mitä se on alla huppu.
Ja me sanomme, että oletuksena, kapasiteetti tulee olemaan kolme.
Joten tämä on paikka 0, tämä on paikalla 1, tämä
on paikka 2.
>> Jos minä lahjoa kanssa stressipallo, olisi joku haluaa tulla ja ajaa
aluksella tässä vain hetken?
OK, näki kätesi ensin.
Tule ylös.
Selvä.
Joten mielestäni on Steven.
Tule ylös.
Selvä.
>> Mutta oletetaan nyt kelaa alkuperäisen maailman tilasta, jossa I
juuri ilmoittanut pino, ja se on olemaan kapasiteetin kolme.
Mutta koko ei ole vielä määritelty.
Alustat ei ole vielä määritelty.
Joten pari kysymystä ensin.
Ja minä annan sinulle mikrofoni, joten voit osallistumme aktiivisemmin tässä.
>> Joten mitä on sisällä koko tällä hetkellä ajoissa, jos kaikki olen tehnyt on
julisti pino yhtä riviä koodia?
>> STEVEN: Ei paljon.
>> DAVID MALAN: OK, ei paljon.
Tiedämmekö mitä sisällä koko, tiedämme mitä sisällä
Tämän array täällä?
>> STEVEN: Vain satunnainen koodi, eikö?
Just -
>> DAVID MALAN: Joo, aion kutsuvat sitä koodia, mutta satunnainen -
>> STEVEN: Things.
>> DAVID MALAN: Asiat kuten random
>> Steven: Bits.
>> DAVID MALAN: Bits, eikö?
Joten roskat arvot, eikö?
Joten permutaatiot 0: n ja 1.
Jäänteitä edellisen käyttötarkoituksissa Tämän muistin.
Ja emme todellakaan tiedä, mitä arvoja ovat, niin me yleensä tehdä niitä
kysymysmerkkejä.
>> Joten ensimmäinen asia, olemme oletettavasti menossa haluavat tehdä täällä -
ja haluan antaa tämän alan sisällä siellä nimi - tarjottimia.
Mitä meidän pitäisi luultavasti alustaa kokoa, jos haluamme
aloitat pino?
>> STEVEN: Alusta on osa 3.
>> DAVID MALAN: Niin, OK.
Olla selkeä, kapasiteetti on julistettu muualla kuin kolme.
Ja se mitä olen käyttänyt jakaa array.
Koko aikoo viitata kuinka monta lokerot ovat tällä hetkellä pino.
>> STEVEN: Zero.
>> DAVID MALAN: Niin sen pitäisi olla nolla.
Joten mene eteenpäin, ja kaikki sormella, piirtää nolla kokoisia.
Selvä.
Joten nyt, mitä sisällä tämän täällä, emme tiedä.
Nämä ovat oikeastaan ​​vain roskaa arvot.
Jotta voisimme tehdä kysymysmerkkejä, mutta Pidetään hallituksen puhtaana nyt
koska se ei ole väliä mitä siellä.
Meidän ei tarvitse alustaa array mitään, sillä jos me tiedämme
pinon koon on nolla, no, me ei pitäisi tarkastella mitään
Tämän array muutenkin at tässä vaiheessa.
>> Joten nyt olettaa, että painan numero 9 pinoon.
Miten meidän pitäisi päivittää tietorakenne sisällä tämä musta laatikko?
Mitä arvoja täytyy muuttaa?
>> STEVEN: Within -
koko?
>> DAVID MALAN: OK.
Koko pitäisi tulla mitä?
>> STEVEN: Koko olisi yksi.
>> DAVID MALAN: OK.
Joten koko tulisi olla yksi.
Joten voit tehdä tämän pari tapaa.
Annan teille nyt oman sormi on pyyhekumi.
Selvä.
Niin nyt sormi on harjalla.
Selvä.
Ja nyt, mitä muuta on muututtava, On selvää, että tietojen rakenne?
>> STEVEN: Menemme alkaen alhaalta ylöspäin 9.
>> DAVID MALAN: 9.
OK, hyvä.
Niin silti ei ole väliä mitä on sijainti yksi tai kaksi, koska he
roskat arvot, mutta meidän ei pitäisi vaivata näköinen siellä, koska koko on
kertovat meille, että vain ensimmäinen tekijä on todella oikeutettua.
Joten nyt painan 17 päälle lista.
Mitä tapahtuu tätä kuvaa?
>> STEVEN: Eli koko on menossa kaksi.
>> DAVID MALAN: OK.
Olet pyyhekumi -
oho.
Olet pyyhekumi.
>> STEVEN: Eraser.
>> DAVID MALAN: Olet harjalla.
>> STEVEN: Brush.
>> DAVID MALAN: OK.
Ja mitä muuta?
>> STEVEN: Ja sitten me -
>> DAVID MALAN: Työnsimme 17.
>> STEVEN: Pysymme 17 päälle, niin -
>> DAVID MALAN: OK, hyvä.
>> STEVEN: - pudota alas.
>> DAVID MALAN: Okei.
Se on tulossa helppoa.
En aio auttaa sinua tällä kertaa.
Push 22.
>> STEVEN: Valmis.
Becoming pyyhekumi.
Olen tulossa harjalla.
Ja sitten olen laskemisesta 22.
>> DAVID MALAN: 22.
Erinomainen.
Joten vielä kerran.
Minä lähden nyt työntää pinoon 26.
>> STEVEN: Ooh.
Voi hemmetti.
Olet todella sai minut kiinni kenet.
>> DAVID MALAN: Et ole näkee tällaista?
>> Steven: En näe tätä tulossa.
Voisimme uudelleen alkuperäisestä kapasiteetista?
>> DAVID MALAN: Se on hyvä kysymys.
Joten olemme sellainen maalattu itse huoneen nurkkaan täällä.
Ei todellakaan ole mitään hyvää ulos Steven koska olemme myönnetty tämän taulukon
staattisesti, niin sanotusti sisälle tieto-rakenteesta.
Ja olemme lähinnä kova koodattu se on kooltaan kolme.
Joten emme voi kohdentaa sitä.
>> Voisimme jos menimme takaisin, me uudelleen kaukaloiden osoitin, että
me sitten käyttää malloc käteen muistia.
Koska jos saimme muisti kasaan kautta malloc, me
voisi sitten vapauttaa sen.
Mutta ennen vapauttaa se, voisimme kohdentaa isompi kimpale muisti,
päivittää osoitin, ja niin edelleen.
Mutta nyt, tämä on todella Parasta mitä voimme tehdä.
Push ja pop ovat oletettavasti menossa on viestittää jokin virhe.
>> Niin esimerkiksi meidän täytäntöönpano push voisi palata bool joka
aiemmin palasi totta, totta, totta.
Mutta neljännen kerran, se tulee olemaan palata vääriä, esimerkiksi.
Selvä.
Hyvin tehty.
Onneksi olkoon.
Olet ansainnut stressipallo tänään.
>> [APPLAUSE]
>> STEVEN: Kiitos.
>> DAVID MALAN: Kiitos.
OK, joten tämä tuntuu olla paljon ja askel eteenpäin, eikö?
Me kuvataan tämän tietorakenteen.
Se on ollut vakuuttava, eikö?
Käyttöjärjestelmät pidä siitä.
Ilmeisesti verkossa voi käyttää tätä, ja muita sovelluksia edelleen.
Mutta mitä tyhmä rajoitus, että olemme Takaisin tavallaan viikon kahden rajan
jossa on kiinteä koko taulukot.
>> Joten on todellakin pari tavalla voisimme ratkaista.
Voisimme dynaamisesti jakaa array, eikä kova koodaus sen olen
täällä tehnyt, vaan uudelleen julistamisesta Tämän vain olla selkeä, sillä
jotain tällaista.
Int * tarjottimia, ei päättää tarjonnan vielä.
Mutta kun julistaa pino muualla minun koodi, voisin sitten soittaa malloc,
saada osoitteen kimpale muisti, ja voisin antaa
että osoite tarjottimia.
>> Ja sitten, koska se on vain kimpale muisti, voisin edelleen käyttää neliö
kiinnike merkintä tavalliseen tapaan.
Koska uudelleen, siellä on tavallaan tämän toiminnallinen vastine taulukot ja
paloina muistia, jotka tulevat takaisin malloc.
Voimme kohtelevat kuin muut käyttäen osoitin aritmeettinen tai
hakasulkeen merkintätapa.
Niin, että yksi lähestymistapa.
>> Mutta miten muuten voisimme toteuttaa tämän yhtä ja samaa rakennetta, mahdollisesti?
Oikea?
Tunnen me vain ratkaisi ongelma kuin viikko sitten.
Mikä oli ratkaisu tähän ongelmaan että Steven törmäsi?
Joten liittyvät luettelot, oikealle.
>> Jos ongelma on se, että olemme maalaus itsemme nurkkaan kohdentamalla
etukäteen liian vähän muistia, että sitten on jotenkin käsitellä, hyvin,
miksi ei vain välttää antaa kokonaan?
Miksi ei vain julistaa kaukaloiden osoitin solmuun, ergo linkitetty lista,
ja sitten yksinkertaisesti jakaa uutta solmuja joka kerta Steven tarvitaan sopivaksi
numeron tietorakenne.
>> Joten kuva olisi muutettava.
Se ei tule olemaan niin puhtaita ja yksinkertainen kuin vain joukko kolme ints.
Nyt se tulee olemaan osoitin struct, ja että struct on menossa
on int ja ensi osoitin.
Se tulee johtamaan kautta, että osoitin toiselle tällaiselle struct on
toinen tällainen struct.
Joten kuva todella saada hieman Messier.
Ja olisimme nuolet sitominen kaikki yhdessä.
>> Mutta se on hieno, oikea, koska olemme nähneet, miten tämä.
Ja kun saat mukavan täytäntöön jotain linkitetyn
lista, joka sinun täytyy tehdä, jos päättää panna hash taulukon
erillinen ketjutus p-sarja 6, voit käyttää sitä rakennuspalikka, tai
ainesosa tai Scratch puhua, menettelyä, jotain, mitä laittaa, et
luonut oman palapelin pala että voit käyttää uudelleen.
Joten kompromissit, mutta mahdollisia ratkaisuja että olemme nähneet ennen.
>> Niin usein, näet tämän joka vuosi tai kaksi, kun Apple julkaisee
jotain uutta, ja kaikki hulluja ihmisiä riviin ulkopuolella Apple
ostamaan marginaali päivittää laitteisto.
Sanon tämän, se on OK, koska Olen yksi niistä ihmisistä.
Millainen tietorakenne voisi edustaa tätä todellisuutta?
>> No, kutsutaan sitä jono, rivi.
Joten British kutsuisi sitä tyypillisesti jono joka tapauksessa, joten se on kiva nimi.
Ja kaksi operaatiota, että jono tuetaan me kutsumme enqueue
toiminta ja dequeue toimintaa, , jotka ovat samanlaisia
henki työntää ja pop.
Se on vain eräänlainen erilainen yleissopimus, mitä me soittaa näitä.
Mutta laittaa jonoon jotain tarkoittaa lisätä tai aseta se tietorakennetta.
Voit dequeue keino poistaa se.
Mutta taas pino oli LIFO tiedot rakenne, jono on ensimmäinen,
first out tietorakenne.
>> Jos olet ensimmäinen henkilö linjassa, olet ensimmäinen henkilö saada
ulos linja ja ostaa uusi laite.
Kuvittele kuinka järkyttynyt nämä ihmiset olisivat jos Apple sen sijaan käytetään pino varten
Esimerkiksi toteuttaa poiminta jopa oman uuden lelun.
Joten jonot järkeä, varmasti ja voimme ajatella kaikenlaisia
sovelluksia, oletettavasti, jonot, varsinkin kun haluat oikeudenmukaisuutta.
Joten miten voisimme toteuttaa nämä sillä tietorakenne?
>> No, ehdotan, että voisimme täytyy tehdä se tällä tavalla.
Joten aion nyt numeroita.
Joten me pitää se yksinkertainen ja ei välttämättä puhutaan lokeroihin.
Vain numeroita että ihmiset mennyt.
Kapasiteetti on menossa jälleen korjata henkilöiden määrä, jotka voivat olla
tätä linjaa, sillä kolme tai mitä muita arvo.
>> Mutta ehdotan, että minun täytyy seurata ei ainoastaan ​​koosta
jono, kuinka monet asiat ovat siinä.
Joten koko on nykyinen koko, kapasiteetti on enimmäiskoko.
Vain kerran, nimikkeistö sopimuksen mukaan.
Miksi tarvitsen lisää int sisällä jonon seurata kuka on
rivin?
Miksi minun pitää tehdä, että tässä tapauksessa?
>> No, miten tämä kuva tulee muuttumaan?
Voin ehkä uudelleen useimmat Kuvan.
Anna minun mennä eteenpäin ja poistaa mitä on täällä.
Annamme tässä hieman eri nimellä täällä.
Mennään eroon 17 Mennään eroon ja 9, nyt päästä eroon 3.
Ja antaa vielä yhden asian.
Ehdotan, että minun täytyy seurata edessä lista, joka on vain
olemaan int samoin.
Ja me aiomme pitää asiat yksinkertaisina.
Ei linkitetty lista nyt.
>> Me myönnettävä, että aiomme kolahtaa vastaan ​​tämän rajan.
Mutta mitä haluan nähdä tapahtuu tällä kertaa?
Joten kai mennä eteenpäin ja ensimmäinen henkilö keksii linjassa, ja
se on numero 9.
Meillä on stressi pallot.
Voinko varastaa, eli kaksi tai kolme ihmistä?
Yksi, kaksi, kolme?
Tule ylös.
Oikea edestä, koska Tästä tehdään yksi nopea.
>> Jokainen teistä on nyt olemaan tuuletin poika jonossa Apple.
Et ehkä saa Applen laitteet lopussa tämän kuitenkin.
Selvä.
Joten olet numero 9, olet numero 17, numero 22.
Nämä ovat mielivaltaisia ​​numeroita, kuten Opiskelija tunnukset tai vaikka mitä.
Ja vain hetken, aloitetaan aloittaa lisäämällä asioita.
Ja minä ajaa aluksella tässä tällä kertaa.
>> Joten tässä tapauksessa, olen alustettu edessä on -
Olen itse ei välitä, mitä edessä on, koska koko on nolla.
Joten tämä saattoi aivan hyvin olla kysymysmerkki.
Nämä kaikki ovat kysymysmerkkejä.
Joten nyt alamme todella nähdä ihmiset riviin myymälässä.
>> Joten jos numero 9, olet ensimmäinen siellä 5 AM, mennä eteenpäin ja riviin,
tai iltana.
OK.
Joten nyt 9 on täällä.
Joten 9 on edessä luettelosta.
Joten aion mennä eteenpäin ja päivittää koko nykyisten tietojen
rakennetta ei ole 0 enää, vaan olla 1.
Aion laittaa 9 at edessä luettelosta.
Anna minun mennä eteenpäin ja vaihtaa näytön jotta voimme nähdä ohitsemme täällä.
>> Ja nyt, mitä haluan laittaa edessä?
Aion seurata, että jonon nyt
on paikalla 0.
Sillä se, mitä seuraavaksi tapahtuu?
No, kai nyt laittaa jonoon 17 samoin.
Joten hop linjassa siellä.
Ja vielä, eräänlainen oven myymälä tulee olemaan täällä.
Joten nyt olen lisätty 17.
Ja vaikka nämä kaverit ovat estämässä näyttö, se on OK,
koska voimme nähdä sen täällä.
Anteeksi.
>> Yleisö: Voimme liikkua -
>> DAVID MALAN: Ei, se on OK.
Se on valtava siellä.
Joten 17 on nyt sisä-jonon.
Minun täytyy päivittää joka kentät nyt vaikka?
OK, varmasti koko.
Ja miten edessä?
OK, no.
Edessä ei pitäisi muuttaa, koska toisin kuin pinon, me
haluavat säilyttää oikeudenmukaisuutta.
Joten jos 9 tuli ensin, haluamme 9 olla ensimmäinen ulos linja
ja myymälä.
>> Itse asiassa, nyt nähdä, että.
Ennen kuin voimme lisätä 22, nyt mennä eteenpäin ja dequeue 9.
Mikä sinun nimesi olikaan?
>> Yleisö: Jake.
>> DAVID MALAN: Jake on menossa voidaan dequeued nyt.
Joten saat kävellä kauppaan.
Ja teeskennellä, että myymälä on tuolla.
Joten nyt mitä tarvitsee - dit-dit-dit!
Mitä täytyy tapahtua nyt?
Suunnittelu päätös.
Joten ei paha vaisto, mutta - Mikä sinun nimesi olikaan?
>> Yleisö: David.
>> DAVID MALAN: David.
Mitäs David tehdä?
Hän yritti tavallaan vahvistaa tiedot rakenne ja siirtyä hänen sijainnistaan
osaksi Jake entinen sijainti.
Ja se on hienoa, jos olemme valmiita hyväksyä, että
täytäntöönpanon yksityiskohtia.
Mutta ensin on päivittää tiedot rakenne ennen kuin teemme sen.
Koska en ole mieltynyt ajatukseen kaikkien ihmiset siirtymässä tätä linjaa.
>> Se ei ole iso juttu, jos David tekee sen yksi askel, mutta jälleen kerran, muistelen
kun meillä on ollut kahdeksan vapaaehtoisille vaiheessa ja olemme tehneet kuten paikoilleen
lajitella, jossa meidän piti aloittaa liikkuvat kaikki ympärillä.
Se sai kallista, eikö?
Se saa minut punastumaan noin iso O n, iso O n potenssiin uudelleen.
Se ei ole tunne kuin Paras lopputulos.
>> Joten haluan vain päivittää.
Joten koko jonon ei ole enää 2.
Nyt on yksinkertaisesti 1.
Mutta voin nyt päivittää jotain En päivittänyt ennen,
edessä luettelosta.
Voisin sanoa, että paikka 1?
Joten nyt meillä on roskaa arvo tähän, roskat arvo täällä, ja David
Keskellä tätä roskaa.
Mutta tietorakenne on ehjä.
>> Ja itse asiassa, en edes tarvitse muuttaa Jaken entisen numeron
9, koska who cares.
Minulla on tarpeeksi tietoa nyt koko, että tiedän siellä on yksi henkilö
tähän jonoon.
Ja tiedän, että kyseinen henkilö on paikassa 1, ei 0.
En laskenta.
Joten 1 samoin.
Joten tietorakenne on vielä OK.
>> No, mitä tapahtuu seuraavaksi?
Katsotaanpa enqueue -
Mikä sinun nimesi on?
>> Yleisö: Callen.
>> DAVID MALAN: Callen.
Katsotaanpa laittaa jonoon Callen, ja 22 on nyt jonossa.
Mitä nyt on muututtava täällä?
Etu ei tule muuttaa, tietenkin.
Koko on muuttumassa olla 2 uudelleen.
Ja 22 päätyy tänne, 9 on edelleen läsnä, mutta se on tehokkaasti
roskat arvo nyt.
Se on vain jäänne Jake ohi.
>> Joten nyt mitä tapahtuu, jos Olen dequeue David?
Viimeinen toiminta, dequeue David.
Voisimme siirtää, mutta ehdotan, katsotaanpa tehdä niin vähän työtä kuin mahdollista.
Nyt tietoni rakenne menee takaisin kooltaan 2-1.
Mutta jonon nyt tulee 2.
Minun ei tarvitse muuttaa näitä numeroita vielä, koska he
vain roskat arvot.
>> Mutta mitä nyt tapahtuu?
Kai laittaa jonoon itse, 26?
Tunnen kuulun tänne.
Joten Minua enqueued.
Joten olen sellainen kuulu tänne.
Ja vaikka et ole aivan Arvostan tätä visuaalisesti vaiheessa
koska meillä on runsaasti tilaa, haluan ei seison tässä, miksi?
>> Yleisö: Olet out of bounds.
>> DAVID MALAN: Oikea.
Olen out of bounds.
Olen indeksoitu yli bounds tämän taulukon.
En todellakaan pitäisi olla yksi kolme mahdollisia paikkoja.
Nyt, missä on kaikkein luonnollisin mennä?
Ehdotan velkarahalla viikolla yksi temppu.
Mod operaattori prosenttiyksikköä.
Koska olen teknisesti seisoo sijainti 3, mutta en 3 mod kapasiteettia,
niin 3, prosenttimerkki, 3 -
kapasiteetti on 3.
Mikä tuo on?
Mikä on jakojäännös, kun jaat 3 noin 3?
0.
>> Niin että saa minut oli Jake oli, joka on todella hyvä.
Joten nyt täytäntöönpanoa tämä asia tulee
olla hieman päänsärkyä.
Se on oikeastaan ​​vain yksi rivi päänsärky, koodia.
Mutta ainakin nyt on roskaa arvo täällä, mutta siellä on kaksi
laillista ints täällä.
Ja väitän, että nyt olemme tehneet mitä meidän täytyy tehdä niin kauan kuin
muutamme mitä Jaken arvo oli 26 jäsentä.
>> Meillä on nyt tarpeeksi tietoa edelleen luotettavuuden säilyttämiseksi
Tämän tietorakenteen.
Olemme vielä sellainen pois onnea, kun olemme haluat lisätä vähintään neljä yhteensä
elementtejä, mutta ainakin voin tehdä melko tehokas käyttö tämän jatkuvan
aikaa, itse asiassa.
En tarvitse murehtia siirtymässä kaikille, sillä Davidin kaltevuus oli.
>> Kysyttävää pinoja, tai tähän jonoon?
>> AUDIENCE: Onko miksi tarvitset kokoa niin tiedät
missä on ihminen?
>> DAVID MALAN: Aivan.
Minun täytyy tietää koko joukko koska minun täytyy tietää tarkalleen, kuinka
Monet näistä arvoista ovat oikeutettuja, ja niin, että voin löytää mihin
seuraava henkilö.
Täsmälleen.
Koko on -
Oikeastaan ​​emme päivittää tätä vielä.
Lisäsin itseni 26.
Koko on nyt, ei 1, mutta 2.
Joten nyt tämä todellakin auttaa minua löytämään johtaja luettelon, joka ei ole 0, ei
1, mutta on 2.
Edessä lista on todellakin numero 22.
Koska hän tuli ensin, niin hän olisi päästetä varastoida ennen minua,
vaikka visuaalisesti Seison lähempänä myymälän.
>> Kaikki hyvin?
Aplodit nämä kaverit ja annamme ne pois sieltä.
>> [APPLAUSE]
>> DAVID MALAN: antaisin pidät lokeroon.
Voisimme nähdä, mitä tapahtuu, jos haluat, mutta ehkä ei.
Selvä.
Joten mitä nyt se jättää meidät?
No, minäpä ehdottaa, että on olemassa muutamia muita tietorakenteita voisimme
aloittaa lisäämällä meidän työkalusarja joka tulee itse asiassa olla melko, melko osuvia
me sukeltaa web kamaa.
Joka taas on jonkinlainen yhteys puita muodossa
jotain kutsutaan DOM, asiakirja objektimalli.
Mutta näemme enemmän että ennen pitkää.
>> Sallikaa minun määritelmällisesti että kutsupuu mitä nyt ehkä tiedätte kuin
enemmän sukupuun, jossa joitakin kantaisä on
juuret puu.
Patriarkaalinen tai matriarkka at hyvin puun latvaan.
Ilman heidän puolisonsa, tässä tapauksessa.
Mutta meillä on nyt, mitä me kutsumme lapset, jotka ovat solmuja, jotka roikkuvat
pois vasen lapsi tai oikea lapsi, nuolet kuten kuvattu täällä.
>> Toisin sanoen, kun puu tietorakenne tietokoneen, puu on nolla
tai useampi solmu.
Jos se on ainakin yksi solmu, sitä kutsutaan root.
Se on asioita visuaalisesti että vedämme huipulla.
Ja että solmu, kuten mikä tahansa muu solmu, voi on nolla, yksi tai kaksi tai kolme,
tai miten monta lasta tietorakenne tukee.
Tässä tapauksessa juuri, varastointi arvo yksi, on kaksi lasta, 2 ja 3,
niin me yleensä soittaa 2 vasen lapsi ja 3 oikea lapsi.
>> Ja sitten kun pääsemme 5, 6, ja 7, 6 voisi kutsua keskimmäinen lapsi.
Jos sinulla on neljä lasta, se saa hämmentävä.
Joten lopeta tuollainen pikakuvake sanallisesti.
Mutta se on oikeastaan ​​vain sukupuun.
Ja lehdet tässä ovat solmuja, jotka itse ei ole lapsia.
Ne roikkuvat pois puun alaosaa.
>> Joten miten voisimme toteuttaa puu, joka on vain kaksi lasta maksimaalisesti?
Me kutsumme sitä binääripuu.
Bi taas tarkoittaa kahta tässä tapauksessa, kuten binary.
Ja niin se voi olla nolla, yksi, tai kaksi lasta maksimaalisesti.
>> Minä ehdotan, että toteutamme solmu että rakenne int n,
ja sitten kaksi osoitinta, yksi nimeltään vasemmalle, yksi nimeltään oikea.
Mutta ne ovat vain mukavia mielivaltainen yleissopimukset.
Ja mitä mukavaa nyt, varsinkin jos Tällainen kamppaillut käsitteellisesti
rekursio, tai ajatellut, että se ei ollut todella ratkaisu mihinkään,
varsinkin jos voisit muisti loppuu.
Nyt puhumme tiedot rakenteita ja algoritmeja, jotka mahdollistavat
meitä kulkemaan ja manipuloida niitä, Osoittautuu, että rekursiivisista tulee takaisin
paljon pakottavia jos ei kauniilla tavalla.
>> Joten tämä Ehdotan täytäntöönpano ja hakutoiminto.
Koska kaksi tuloa -
niin ajattele tätä musta laatikko.
Koska kaksi tuloa, n, int, ja osoitin puu, osoitin
solmu, tai oikeastaan ​​juuri puu, I väittävät, että tämä toiminto voi palauttaa
totta vai tarua, että arvo n on sisällä tämän puun.
>> Mitä sisällä tämä musta laatikko?
No, neljä oksat.
Ensimmäinen vain tarkistaa.
Jos puu on null, vain palauttaa false.
Jos ei ole solmu, ei ole n, ei ole numero, vain palauttaa false.
Jos kuitenkin, n, arvo etsit varten, on pienempi kuin puu nuoli n ja
vain olla selvää, mitä se tarkoittaa, kun Kirjoitan puu ja sitten nuoli
merkintätapa, n?
Täsmälleen.
Se tarkoittaa dereference että osoitin kutsutaan puu.
Mene sinne, ja sitten päästä sisälle, että solmu ja saada alansa Kutsutaan.
Ja sitten verrata todellisia n, joka oli johdetaan Haku sitä vastaan.
>> Joten jos n on pienempi kuin n-arvo puussa solmun itse, hyvin,
mitä se tarkoittaa?
Tämä tarkoittaa mitään ensi silmäyksellä.
Oikea?
Aivan kuten silloin, kun on joukko arvot, haluat ehkä soveltaa binary
etsiä muotona kahtiajaon ja valloittaa.
Mutta mitä oletus ei meidän tehdä binary haku toimi lainkaan
puhelinluettelosta, ja Aiempia esimerkkejä?
>> Miten voidaan lajitella.
Joten tarkentaa määritelmää puu täällä ei olla vain puu, joka voi
mitään määrän lapsia.
Ei vain binääripuu, joka voi on 0, 1 tai 2 maksimaalisesti.
Mutta binäärihakupuu tai BST, joka on vain hieno tapa sanoa
binääripuussa siten, että jokaisen solmun vasen lapsi, jos on läsnä, on
vähemmän kuin solmu.
Ja jokainen solmun oikea lapsi, jos läsnä on suurempi
kuin solmu itse.
>> Eli toisin sanoen, jos olisit tehdä puu pois, kaikki numerot ovat
tasapainoisia näin niin, että jos sinulla on 55 root, 33 voi mennä
sen vasemmalla puolella, koska se on vähemmän kuin 55.
77 voi mennä sen oikein, koska se on suurempi kuin 55.
Mutta nyt huomaa, samaa määritelmää, se on rekursiivinen määritelmä sanallisesti,
on haettava 33.
33 vasemman Lapsen tulee olla alle sen, ja 33: n oikea lapsi, 44, on oltava
suurempi kuin se.
>> Joten tämä on binäärihakupuu, ja Ehdotan, käyttäen hieman
rekursio, voimme nyt löytää n.
Joten jos n on pienempi kuin arvo n, joka on nykyinen solmu, aion mennä
eteenpäin ja ruuhi, niin sanotusti, ja vain palata riippumatta vastaus on
etsivät n päälle puun vasen lapsi.
Huomaa jälleen, tämä toiminto vain odottaa solmu tähden,
osoitin solmuun.
Niin varmasti voin vain tehdä puiden nuoli vasemmalle, mikä johtaa
minut toiseen solmuun.
Mutta mikä on se solmu?
>> No, tämän julistuksen, vasemmalla on vain osoitin, niin että vain
tarkoittaa olen ohimennen hakutoiminto eri osoitin, eli
yksi, joka edustaa minun vasen lapsen puu.
Joten tässä tapauksessa osoitin 33, jos Tämä on meidän näyte tulo Samaan aikaan, jos
n on suurempi kuin arvo n on nykyinen solmu puussa, niin olen
mene eteenpäin ja punt muiden suuntaan ja vain sanoa, en
tietää, jos tämä arvo n on puu, mutta en tiedä, jos se on, se on alas minun
oikea haara, niin sanoakseni.
Joten Soitan rekursiivisesti etsiä, kulkee n uudelleen, mutta ohimennen
osoitin minun oikea lapsi.
>> Toisin sanoen, jos olen tällä hetkellä 55 ja etsin 99, tiedän, että 99
on suurempi kuin 55, joten aivan kuten Revin puhelinluettelosta viikkoa sitten ja me
meni oikein, samoin me olemme menossa täällä.
Ja en tiedä onko se minun oikealle lapsi, ja se ei ole, 77 on olemassa, mutta
Tiedän, että se siihen suuntaan.
Joten pyydän haku minun oikea lapsi, 77, ja anna hakuun luku ulos
siellä jos 99 tämä mielivaltainen Esimerkiksi on todella olemassa.
>> Muu, mikä on viimeinen asia?
Jos puu on nolla on yksi tapaus.
Jos n on pienempi kuin nykyisen solmun arvo on toinen asia.
Jos n on suurempi kuin nykyinen solmun arvo on kolmas tapaus.
Mikä on neljäs ja viimeinen asia?
Luulen, että olemme pois tapauksissa, eikö?
Sen täytyy olla, että n on nykyinen solmu, joka olen.
>> Joten jos Etsin 55 tässä vaiheessa tarina, että haara
puu palaisi totta.
Niin mitä mielenkiintoista tässä on se, että me itse, toisin kuin viikkoa aiemmin, olemme eräänlainen
ja kaksi pohja tapauksissa.
Ja he eivät tarvitse olla kaikki huipulla.
Alkuun on pohja tapauksessa, koska jos puu on null, ei ole mitään tekemistä.
Vain palata kovakoodattu arvo false.
>> Alahaaran on eräänlainen oletus, jonka mukaan jos olemme tarkastetaan
null, olemme tarkastetaan, jos se olisi vasemmalle, mutta sen ei pitäisi olla, olemme
tarkistetaan, jos se olisi oikea, mutta se ei pitäisi olla selvästi sen on oltava
juuri siellä missä olemme.
Se on pohja tapauksessa.
Joten siellä kaksi rekursiivinen tapauksissa alumiinifoliota siellä keskellä.
Mutta en voinut kirjoittaa Tässä missä tahansa järjestyksessä.
Ajattelin vain se sellainen tuntui luontevalta ensin tarkistaa mahdollisen virheen,
tarkista sitten vasemmalle, sitten tarkistaa oikealle, sitten olettaa, että olet solmussa
olet todella etsivät.
>> Joten miksi tämä voisi olla hyödyllistä?
Joten se kääntyy pois -
ja haluan hypätä teaser täällä se on verkossa.
Aiomme alkaa käyttää ei ohjelmointikieli aluksi, mutta
kuvauskieli.
Kuvauskieli on yksi, joka on hengeltään samanlainen ohjelma
kieli, mutta se ei anna kyky ilmaista itseäsi loogisesti.
Se vain antaa sinulle mahdollisuuden ilmaista itseäsi rakenteellisesti.
>> Minne haluat laittaa jotain sivulla, sivun?
Mitä väriä haluat tehdä?
Mitä fontin kokoa haluat tehdä?
Mitä sanoja sinä itse haluavat www-sivulla?
Niin, että kuvauskieli.
Mutta sitten me nopeasti käyttöön JavaScript, joka on täysimittainen
ohjelmointikieli.
Hyvin samanlainen rakenteeltaan ulkonäöltään C, mutta se tulee olla
kiva, tehokkaampia ja käyttäjäystävällisiä ominaisuuksia.
>> Ja yksi turhautumisen tässä kohta lukukausi on, että me
pian täytäntöön aapinen vuonna huomattavasti vähemmän riviä koodia muilla kielillä
kuin C puolestaan ​​sallitaan, mutta syystä: n me pian ymmärtää.
Tämä on ensimmäinen tällainen web-sivun.
Se on täysin underwhelming, ensimmäinen teemme.
Se yksinkertaisesti sanoa, hello world.
Mutta jos et ole koskaan nähnyt ennen kuin tämä on HTML,
Hypertext Markup Language.
>> Jos menet tiettyjä valikon vaihtoehto Useimmissa tahansa selaimella, millä tahansa web-sivu
Internetissä voit nähdä HTML että jotkut ihmiset kirjoitti
luoda kyseisen sivun.
Ja se luultavasti ei näytä yhtä lyhyt tai siisti kuin tämä.
Mutta se seuraa mallia näistä avoin suluissa ja viiltää ja
kirjaimia ja mahdollisesti numeroita.
>> Ajattelin antaa teille teaser mitä voit tehdä
ottamisen jälkeen CS50.
Anna minun mennä cs.harvard.edu / ryöstää, oman Rob Bowden kotisivulla.
Hän teki tämän meille.
Joten voit pian olla mahdollisuus tehdä niin.
Ja myös, mitä kuulit tänä aamuna -
mitä tänä aamuna -
>> [HAMSTER DANCE MUSIC]
>> - You'll voi tehdä tätä.
Joka meitä odottaa keskiviikkona.
Me nähdään sitten.
>> [HAMSTER DANCE MUSIC]
DAVID MALAN: Seuraavassa CS50 -