>> DAVID MALAN: Rendben.
Üdv újra a CS50.
Ez a kezdete a 8. héten.
És emlékszem, hogy a probléma meg 5 ért véget egy kis kihívás.
Tehát feltételezve, hogy vissza az összes tanítás Fellows és a CA fotói
A card.raw fájlt, akkor jogosult hogy most meg az összes olyan ember, és
egy szerencsés nyertes hazafelé egy ezeket a dolgokat, az ugrás mozgás
eszköz, amelyek segítségével a végső projektek, például.
>> Ez minden évben, vezet egy kis creepiness.
És amit én gondoltam, csinálni is megosztani veletek néhány a jegyzeteket, amelyek
ment oda-vissza a személyzet lista végén.
Például, csak tegnap este, idézet idézet vége, az egyik a személyzet
tagjai, "Csak volt egy diák kopogás az ajtómon, hogy egy fotót velem.
Stalker, mondom. "Indult meglehetősen leíró aztán elköltöztünk
tovább, egy órával később, "volt egy diák vár rám szakasz után
és volt minden a nevét és fényképét néhány lapot. "Rendben.
Tehát szervezett, de nem minden hátborzongató még.
>> Aztán: "Én voltam a városban ezen a hétvégén, és amikor visszaértem, ott volt a
én
hálószoba. "[nevetés]
DAVID MALAN: Next idézet a személyzet tag, "egy diák jött a házamba a
Somerville at 4:00 ma reggel. "Next személyzet, "kaptam az én hotel San
Francisco és a diák várta nekem a lobby három DSLRs. "
Típusa kamera.
"Én nem is az alkalmazottak ebben a félévben, hanem egy diák betört a házamba a
reggel és rögzíteni az egészet Google Glass. "És akkor végül,
"Legalább 12 ember vesztette mohón vár rám, mikor kiszálltam az
limuzin, aztán
felébredt. "Rendben.
Tehát között a fényképek, ahogy lehet emlékszem, van ez a fickó itt, hogy ki vagy
is ismert Milo Banana, aki él Lauren Carvalho, a fejünk
tanítás Fellow.
Milo Milo, gyere ide fiam.
Milo.
Ne feledd, van rajta Google Glass, így mi megmutatjuk, mindezt után.
Tehát ez Milo, ha szeretné hogy egy fényképet vele utána.
Ha szeretné, hogy néz ki A közönség is.
OK.
Ez jó felvételeket.
Nos, Milo Banana.
Ó, ne csináld ezt.
>> [Nevetés]
>> OK.
Így egy szót, akkor a mi a tennivaló, mert ahogy elkezdünk átmenet,
ezen a héten különösen a C- parancssori környezet PHP és
JavaScript és SQL és HTML-és CSS-ben A web-alapú környezetben leszünk
felszerelése akkor az összes nagyobb tudás
lehetséges végső projekteket.
E cél érdekében a kurzus egy hagyománya szemináriumok, amelyek
vannak érintő témákban a tanfolyam.
Nagyon kapcsolatos programozás és a app fejlődés, és így tovább, de
nem feltétlenül által feltárt során saját tananyag.
>> Tehát, ha lehet, hogy érdekel egy vagy több az idei szemináriumok,
regisztrálni cs50.net/seminar.
Vannak idősebb szemináriumok A cs50.net/seminars.
És a naptárban eddig az idei évre csodálatos Web Apps a Ruby on
Sínek, ami egy alternatív nyelv PHP.
Számítógépes nyelvészet.
Bevezetés a IOS, amely a platform, hogy a használt iPhone és
iPad fejlesztés.
JavaScript Web Apps, fogjuk fedezni , de ezen a szemináriumon, akkor menj
be részletesebben.
>> Leap Motion, így lesz valóban van néhány A barátaink Leap Motion,
maga a vállalat, csatlakozz hozzánk.
Tomorrow, sőt, hogy a a gyakorlati szeminárium, ha
az Ön számára.
Meteor.js, egy alternatív technikát JavaScript segítségével nem a böngészőben,
hanem a szerveren.
Node.js, ami nagyon sok ebben a szellemben is.
Karcsú Android Design.
Android, hogy egy nagyon népszerű alternatíva az iOS és a Windows Phone
és más mobil platformokon.
És Web Security aktív védelem.
>> Tehát valójában, ha szeretné hogy vegyenek részt ebben, hadd
jegyezze meg.
Nagyon boldogok vagyunk, hogy azt mondják, hogy barátaink a Leap
Motion, mely egy startup -
ez a készülék tényleg most jött ki néhány hónappal ezelőtt -
kegyesen adományozott 30 ilyen eszközök Az osztály, mint sok diák, ha
szeretné kölcsönkérni a hardver felé félév végén, és használja a
tényleges végleges projekt.
Ezek támogatják a több nyelven.
Egyikük sem C, egyikük sem PHP, ezért megvalósítani egy vagy több ilyen szemináriumok
bizonyulhat az érdeklődés.
És mindegyik lesz forgatták az esetben, ha nem tudja
részt venni személyesen.
Az ütemterv közzé keresztül e-mail, ahogy megszilárdul szoba.
>> És végül, ha megy a projects.cs.50.net, ez egy weboldal
tartunk minden évben, hogy mi meghívjuk emberek a közösség, kar,
osztályok, a személyzet, és mind a egy külső CS50 a
javaslatot projektötletek.
Érdekességek a diákcsoportok.
Érdekességek a szervezeti egységek.
Tehát nem pedig ott, ha küzd A bizonytalanság, hogy mit
magát, szeretne foglalkozni.
>> Így utoljára bevezetett egy vitathatatlanul bonyolultabb adatstruktúra, mint ahogy azt
látható hét múltban.
Mi volna a tömbök elég boldogan, mint hasznos, ha
egyszerű adatstruktúra.
Aztán bevezette ezeket, ami természetesen kapcsolódnak listákat.
És mi volt az egyik motivációja bevezetésével az adatok szerkezete?
Igen?
Mi ez?
>> Közönség: Dinamikus méretét.
>> DAVID MALAN: Dinamikus méretét.
Tehát míg a tömbben, akkor a tudja a mérete előre, amikor
Ön osztja azt.
A láncolt lista, akkor nem Tudnunk kell, hogy.
Ha csak malloc, vagy még általánosabban, osztja kiegészítő
csomópont, hogy úgy mondjam, minden alkalommal, amikor szeretné szúrni több adatot.
És csomópont nincs előre meghatározott jelentése.
Ez csak egy általános kifejezés leíró valamiféle tároló, hogy mi vagyunk
felhasználásával a mi adatstruktúra tárolni Néhány tétel az érdeklődés, amely ebben az
esetben megtörténhet, hogy egész.
>> De mindig van egy kompromisszum.
Így kapunk dinamikus mérete az adatok szerkezet, de milyen árat fizetünk?
Mi a hátránya a kapcsolt listák?
Igen?
>> Közönség: több memóriát igényel.
>> DAVID MALAN: többre van szükség, memória, pontosan hogyan?
>> Közönség: [hangtalan].
>> DAVID MALAN: Pontosan.
Tehát most már mutatókat megkezdéséről további memória, hogy a korábban
nem volt szükség, mivel az az előnye egy sor, az természetesen az, hogy
minden rendben van összefüggő, vissza vissza az vissza, ami
ad véletlen elérésű.
Mivel csak a szögletes zárójel jelöléssel, vagy nagyobb technikai mutató
számtani, nagyon egyszerű felül tud hozzáférni
elemek állandó időben.
És valóban, ez a fajta hint egy ár, amit fizetünk a
láncolt lista.
>> Mi történik a futási ideje valami, mint a Search, ha azt akarom, hogy
néhány értéket és belül A láncolt lista?
Mit jelent a működési idő lesz?
Big O n.
Ha ez a sorrendje?
Mi van, ha az adat struktúra sorrendje?
Lehet, hogy jobban, mint a nagy O n a keresést?
Nem, mert a legrosszabb esetben ez talán nagyon jól lehet válogatni, de ez a szám
keres lehet nagy.
Lehet, hogy a szám 100, ami Előfordulhat, hogy az összes
az utat a végén.
És mivel csak akkor férhet hozzá a kapcsolt listát a végrehajtás
ahogy az első csomópont, akkor mindig ilyen a szerencse.
Meg kell áthalad az egészet az első az utolsó, hogy megtalálják
az a nagy érték, mint 100 fő.
Vagy annak megállapítására, hogy nincs még ott.
>> Így nem tudja, mit algoritmus adat szerkezet úgy néz ki, mint ez?
Nem tehetünk bináris keresés, mert a bináris keresés szükséges, hogy mi volt
véletlen elérésű.
Így egyszerűen ugrani helyről a helyre anélkül, hogy követni
Ezen zsemlemorzsa formában Mindezen mutatók.
>> Nos, hogyan is alkalmazzák ezt?
Nos, ha elmegyünk a képernyő itt, ha akkor gyorsan újraimplementálni az adatok
struktúra -
a kézírás nem minden jó, de megpróbáljuk.
Tehát typedef struct, és mit tettem szeretnénk felhívni a dolog itt?
Node.
Úgyhogy minket kezdődött.
És most, mit kell belsejében az adatszerkezetet, amely egyszeresen
láncolt lista?
Hány területen?
>> Tehát két.
Egy elég egyszerű.
Így int n.
És nevezhetjük n, amit csak akarunk, de meg kell egy int, ha vagyunk
végrehajtása láncolt lista a ints.
És most mit jelent a második terület kell?
Struct node *.
Tehát, ha én struct node *, aztán nevezhetjük ezt is, amit akarok,
de csak hogy világos hívom mellé, ahogy csináltam.
És aztán majd becsukom a zárójelek.
>> És most, mint a múltkor, Tettem node ide.
De ha én kijelentette, ez a node, miért törődöm, hogy olyan
verbose itt kijelentette struktúra node * mellett, szemben
csak node * a következő lépés?
Igen?
>> Közönség: [hangtalan].
>> DAVID MALAN: Pontosan.
Pontosan.
Mivel a C igazán viszi szó szerint és csak akkor találkozik a meghatározása csomópont
idáig, akkor nem hivatkoznak rá itt.
Tehát ez a fajta elsőbbségi nyilatkozat itt, ami kétségkívül
annál részletesebb.
Struct csomópont, ez azt jelenti, most már elérheti
belsejében az adatszerkezetet.
>> És mint félre, mert ez válik egy kicsit szubjektív most,
A csillag technikailag megy itt, ez megy itt, akkor
még megy a közepén.
Már elfogadott, a stílus útmutató A kurzus az egyezmény helyezése
a csillag mellett az adatok típusú, ami ebben az esetben,
lenne struct csomópont.
De észre a sok tankönyvek és Online referenciák, lehet, hogy valóban
látni a másik oldalon.
De csak észre, hogy a két fog ténylegesen működik, és egyszerűen ki kell
következetes.
>> Rendben van.
Szóval ez volt a nyilatkozat A struct csomópont.
De aztán elkezdtem több kifinomult dolgok.
Például, úgy döntöttünk, hogy be olyasmi, mint egy hash tábla.
Tehát itt van egy hash tábla méret n indexei 0-tól a bal felső sarokban, hogy n
mínusz 1 a bal alsó sarokban.
Ez lehet egy hash táblázat semmit.
De milyen dolgok beszélünk körülbelül egy hash tábla?
Tárolása, mi?
>> Nevek.
Megtehetjük nevek, mint a mi a múltkor.
És tényleg, bármi tárolható.
És majd meglátjuk, ezt újra PHP és JavaScript.
A hash tábla egy szép egyfajta svájci Bicska, amely lehetővé teszi, hogy tárolja
nagyjából bármit belsejében azt tömörítő kulcsokat értékeket.
Keys értékekkel.
>> Most ebben az egyszerű esetben, a gombok csak számok.
Mi megvalósítása hash tábla, mint egy tömb.
És így a gombok 0, 1, 2, és így tovább.
És így mi, emberek, úgy döntött, utolsó héten, hogy tudod mit, ha vagyunk
majd neveket, nézzük csak önkényesen, de elég ésszerűen,
Feltételezem, hogy Alice, egy A név, majd csak indexelt be 0-ra.
És Bob, a B név lesz indexelve ba 1, és így tovább.
Tehát volt egy leképezés bemenetek között, amelyek vonósok, és a hash
helyek, melyek számokat.
>> Annak érdekében, hogy a folyamatot általában ismert a hash függvényt, és akkor igazán
végrehajtja a kódot.
Ha akartam, hogy végre egy hash függvény hogy pontosan mit is
csak le az utolsó alkalom, talán kijelentik, hogy a funkció kerül, mint
input például -
és csináljuk ezt a képernyő ide.
Ha akartam, hogy végre egy hash funkció, mondhatnám
valami ilyesmi.
>> Ez lesz, hogy visszatérjen egy int.
Ez lesz az úgynevezett hash, és ez fog elfogadni érvként a
string, vagy mi lehet a megfelelő most, és azt mondják char *, hívjuk meg s.
És akkor ezt a funkciót kell tennie, végül is visszatér egy int.
Most, hogy ez, amely Nem ennyire egyértelmű.
Fogom végrehajtani ezt a nélkül formájában hiba ellenőrzése most.
Én csak úgy vakon mondani, vissza bármi van s konzol 0, mínusz,
mondjuk, a tőke A pontosvessző.
>> Teljesen megtört.
Ez nem tökéletes, mert Egy, mi van, ha s nulla?
Rossz dolgok fognak történni.
Két, mi van, ha az első betű a név nem nagybetűvel?
Ez nem fog fordulni ki jól.
Lehet, hogy a kisbetű vagy nem betű egyáltalán.
Így teljesen javítani itt, de ez az alapötlet.
>> Amit leírt a múlt héten szóban, mint csak egy folyamat feltérképezése Alice
0 és Bob 1 lehet kifejezni bizonnyal több formulaically a C
működik itt.
Megint hívott hash, vesz egy string bemenet, és aztán valahogy csinál valamit
azzal, hogy a bemeneti, hogy készítsen egy kimenetet.
Nem úgy, mint a fekete doboz leírás hogy már régóta kész.
Nem tudom, hogy ez lehet, dolgozik a motorháztető alatt.
>> A probléma szett 6, az egyik kihívás az Ön számára, hogy eldöntse, hogy milyen
lesz a hash függvény legyen?
Mi lesz benne, hogy a fekete doboz, és valószínűleg ez lesz a
kicsit érdekesebb, mint ez, és határozottan több a hibalehetőség
ellenőrzés, mint az adott végrehajtását.
>> De a problémák merülnek fel, ugye?
Ha van egy adatstruktúra, mint ez Egy, mi az egyik probléma,
akkor befut idővel behelyezi egyre több nevet a
hash tábla?
Kapsz ütközések, ugye?
Mi van, ha Alice és Áron, két ember, akiknek a neve történt
kezdeni egy?
Ez felveti a kérdést, ahol a hogy a második ilyen név?
>> Nos, lehet, hogy naiv módon csak tedd ahol Bob tartozik, de aztán Bob
olyan csavaros, ha megpróbálja be a nevét a következő és
nincs hely neki.
Szóval lehet, hogy fel Bob hol van Charlie, és el tudják képzelni ezt a nagyon gyorsan
háruló egy kis rendetlenség.
Valami lineáris a végén, ahol a Csak meg kell keresni az egészet
keres Alice és Bob vagy Aaron vagy Charlie.
>> Tehát ahelyett, hogy azt javasolta, ahelyett, hogy csak lineárisan szondázás nyitott terek
és plopping a nevét ott, javasolt szakértő megközelítés.
A hash tábla végre még egy tömb indexek, de az adatok típusát
az indexek már voltak mutatók.
Mutatók mi?
Mutatók láncolt listák.
>> Mert emlékszem, hogy a csatolt lista tényleg csak egy mutató egy csomópont, és
A csomópont a következő mezőre, és a csomópont van egy következő mezőre, és így tovább.
Így most már gondolni a tömb A bal oldali egy hash táblát
ami a láncolt lista.
Az előnye, hogy melyik az, ha kap egy ütközés között Alice és Áron,
mit csinálsz a második ilyen ember?
Csak csatlakoztassa őt a végén, vagy akár a kezdet
, hogy a láncolt lista.
>> És valóban, most csak a tészta hogy csak egy pillanatra.
Hol lenne a legtöbb értelme?
Ha be Alice, és ő végül a Az első hely, akkor megpróbálom
Aaron be nevét, és ott nyilván egy ütközés, rakjam
neki az elején A láncolt lista?
Ez az, hogy az első helyre, vagy végén?
>> Közönség: [hangtalan].
>> DAVID MALAN: OK.
Hallottam elején.
Miért az elején?
>> Közönség: [hangtalan].
>> DAVID MALAN: OK.
Ez ábécé, így szép.
Ez egy jó tulajdonság.
Ez megment egy kis időt potenciálisan.
Ez nem engedi bináris keresést, de Lehet, legalább tudja, hogy kitörjön
egy hurok, ha látom, jól vagyok, ahogy Aaron múltban lenne ebben
rendezett láncolt lista.
Nincs vesztegetni az időmet keres egészen a végéig.
Szóval ez ésszerű.
Miért más is a beszúrni kívánt Az ütköző név a
elején a lista?
Mi ez?
>> Közönség: [hangtalan].
>> DAVID MALAN: Lehet, hogy egy hosszú ideig hogy az a lista végére.
És valóban, a hosszabb és hosszabb.
Minél több neveket beszúrni a Kezdjünk egy, a hosszabb,
láncot fog kapni.
A hosszabb, összefüggő lista fog kapni.
Szóval tényleg csak az idejét vesztegeti.
Lehet, hogy te jobb megőrzése állandó behelyezésének időpontjával, nagy O 1,
által mindig amivel az ütköző nevet az elején a láncolt lista,
és nem annyira aggasztó a válogatás.
>> Mi a legjobb megoldás?
Ez világos.
Ez a fajta attól függ, mi a eloszlás, amit a minta
A neveket behelyezésekor.
Ez nem feltétlenül nyilvánvaló válasz.
De itt az, megint, tervezési lehetőséget.
>> Szóval akkor nézett ez a dolog, ami valóban a másik nagy lehetőség
A p-set 6.
És észre, ha még nem tette meg, Zamyla merülés mindkét, hash
asztalok és próbálkozás, részletesebben.
És a video Walkthrough az ágyazott p-set spec.
Ez egy Trie -
T-R-I-E. És mi volt érdekes az volt, hogy a működési idő
keres egy nevet, mint a Maxwell utoljára, nagy volt Ó, mi?
Mi ez?
>> Közönség: A betűk száma.
>> DAVID MALAN: száma leveleket.
Hallottam két dolgot.
Betűk száma és a folyamatos idő.
Szóval megy az első.
A betűk száma.
Nos, ez az adat struktúra, emlékszem, az mint egy fa, egy családfát, minden
akinek a csomópontok alkotják a tömbök.
És ezek a tömbök mutatókat más ilyen csomópontok, vagy más ilyen
tömbök a fán.
>> Tehát, ha azt akartuk, hogy majd meg hogy Maxwell van itt, lehet, hogy el
Az első tömb, az egyik legfontosabb a a fa, az úgynevezett gyökér, tetején
A Trie, és kövesse az m mutató, akkor a mutató, akkor x,
W, E, L, L.
És akkor, amikor látom, néhány speciális szimbólum, jelöli itt, mint egy háromszög.
A kód látni fogod, javasoljuk, hogy végre egy bool, csak azt mondom, igen
vagy nem, a szó megáll itt.
>> Nos, ha már elment a M-A-X-W-E-L-L, érzés hét, talán
nyolc, ha megy valaki mellette, nyolc lépéseket, hogy megtalálja Maxwell.
Vagy nevezzük K. De emlékszem utolsó alkalommal, azt állította, hogy ha van
reálisan maximum hosszúság szó, mint a 40-valami furcsa karakterek, a
maximális hossza azt jelenti, állandó érték.
Szóval tényleg, igen, ez technikailag nagy O 8 vagy 7, vagy igazán nagy O K. azonban
ha van egy véges kupakot milyen K lehet, hogy ez egy állandó.
És ez nagy O 1-es a végén a nap.
>> Nem a valós világban.
Nem, ha tényleg kezdeni nézni az óra, mint a program fut.
Ez feltétlenül lesz egy kicsit lassabb, mint igazán állandó
időt egy lépésben.
Ez lesz hét-nyolc lépés, de ez sokkal, de sokkal jobb
mint egy algoritmus, mint a nagy O n, hogy méretétől függ, hogy mi van a
adatstruktúra.
>> Figyeljük meg a fejjel itt tudjuk be egy millió további nevek ebbe
adatstruktúra, de hány lépés ez fog minket megtalálni
Maxwell ebben az esetben?
Nincs.
Ő nem befolyásolja.
És a mai napig, nem hiszem, hogy láttam egy példa egy adatstruktúra vagy
algoritmus teljesen befolyásolja a külső
viselkedések, mint ezt.
De ez nem lehet csodálatos.
Ez nem lehet az egyetlen megoldás a p-set
>> És ez nem az.
Ez nem szükségszerűen az adatok struktúra kell vonzódik,
mert mint hash táblák, kompromisszum.
Mi az ár, amit fizetni itt?
Memória.
Úgy értem, ez egy kegyetlen memória.
És akkor nem igazán látom itt, mert A szerző ezt a képet
nyilvánvalóan csonka összes tömbök, és nem látunk sok A és a
B és C és a Q és a Y és Z ezen tömbök.
De ott vannak.
>> Minden ilyen csomópontok egy egész tömb néhány 26 vagy több bájt, mindegyik
ami egy levelet.
27. a mi esetünkben, hogy tudjuk támogatni aposztrófok a probléma meg.
Tehát ez az adat struktúra valóban, Nagyon sűrű és széles.
És ez csak talán a végén lassul dolgokat, vagy legalábbis olcsóbb a
sokkal több helyet.
De ismétlem, levonhatjuk összehasonlítás itt.
>> Emlékezzünk egy kicsit vissza, hogy sok mindent elért izgalmasabb futó időt válogatás
ha az általunk használt merge sort, de az ár fizettünk elérni n log n merge
sort kell, hogy töltünk még milyen erőforrás?
Több hely.
Szükségünk volt egy másodlagos tömb másolni az embereket, mint
mi itt a színpadon.
Tehát újra, nincs egyértelmű győztes, de csak szubjektív tervezés
döntéseket kell hozni.
>> Rendben van.
Szóval, mi a helyzet ezzel?
Bárki, aki ismeri, amely D-Hall?
OK.
Így hárman nem.
Mather House.
Tehát ez a Mather étkezőjében.
Lefogadom, minden étkezőben van halom tálcák, mint ez.
És ez valóban reprezentatív valamit most már
nyilván látott már.
Úgy hívják, hogy szó szerint egy verem.
És a verem, tekintve a számítógép memóriája, ahol adat megy
míg a funkciók, hogy hívják.
>> Például, milyen dolgok a verem tekintetében a
Memória kialakítása már tárgyalt hetekben múltban?
Mi ez?
>> Közönség: hívások a funkciókat.
>> DAVID MALAN: Sajnálom.
>> Közönség: hívások a funkciókat.
>> DAVID MALAN: kéri a funkciók, de pontosabban, mi van az egyes
a keretek?
Milyen dolgokat?
Igen.
Tehát lokális változók.
Bármikor szükségünk van egy kis helyi tároló, mint érv, vagy int I, vagy int
temp, vagy bármi, a helyi változó, voltunk
üzembe, hogy a verem.
És ez egy verem, mert , hogy a réteg ötlet.
Csak olyan mérkőzés a valóságnak, a koncepció figyelemmel.
>> De kiderül, hogy egy köteg is kell tekinteni, mint egy adat struktúra, egy
alternatíva, hogy egy sor, egy másik egy láncolt lista.
Valami fogalmilag sokkal érdekesebb még lehet, hogy a
megvalósíthatók bármelyik ezek dolgok, de ez egy más típusú
adatstruktúra támogatja, de tényleg, csak két művelet.
De lehet hozzá a szakértő funkciók, mint ezek.
De ezek az alapok -
push és pop.
>> És az ötlet egy halom, hogy ha én van itt, vagy anélkül Annenberg
tudva, egy tálcát a szomszédból A 9-es szám rajta.
Tehát csak egy int.
És azt akarom, hogy álljon a rá az adatokat szerkezet, amely jelenleg üres.
Tekintsük ezt az alján a verem.
Én nyomja ezt a számot 9-re a verem, és most ott van.
>> De az érdekes dolog a stack az, hogy ha most akarja nyomni
más érték, mint a 17, és nyomja ez a verembe, azt fogom tenni
az egyetlen intuitív dolog, én csak megy hogy azt ott, ahol mi, emberek
hajlamos lenne, hogy azt, a tetejére.
De ami igazán érdekes már az, hogyan jutok 9-kor?
Tudod, én nem mentes némi erőfeszítést.
>> Szóval mi az érdekes a a verem, hogy a tervezés,
ez egy LIFO adatszerkezet.
Silly leírási módja utolsó, first out.
Tehát az utolsó szám ebben az időben 17 éves volt.
Tehát, ha azt akarom, hogy a pop valamit le a verem, akkor csak 17.
Szóval van egy kötelező sorrendben műveletek itt, ahol az utolsó elem
az is, hogy az első egyet.
Ezért a rövidítése, LIFO.
>> Miért lehet ez hasznos lehet?
Vannak-e összefüggésben, amelyben azt szeretnék egy adatstruktúra, mint ez?
Nos, ez bizonyára hasznos belsejében egy számítógép.
Tehát operációs rendszerek egyértelműen ezt milyen adatszerkezetet stack.
Azt is látni ugyanezt a gondolatot amikor a weboldalakat.
Így ezen a héten és a jövő héten, és azon túl, és ahogy végrehajtásának megkezdése web
oldalakat egy nyelv nevű HTML, akkor ténylegesen használni egy adat struktúra, mint
ez határozza meg, hogy ha az oldal helyesen formázott.
Mivel fogod az összes internetes oldalak követik egyfajta hierarchia, egy bemélyedés
lehet, amely a végén a nap, hogy egy fa struktúra a motorháztető alatt.
Így még az, hogy csak egy kicsit.
>> De most nézzük javasolni pillanat, hogyan megyünk a
ami mi a verem?
Hadd javaslom, hogy végre a verem a kódot, mint ez.
Tehát egy köteg megy, hogy belsejébe két dolog, egy sor, az úgynevezett tálcák,
csak hogy összhangban van a demo.
És az egyes elemek, hogy a tömbben lesz a típus int.
És kapacitás feltehetőleg mi?
Mert én nem írtam a teljes definíció.
>> Ez talán a legnagyobb a tömb méretét.
És ez valószínűleg nyilvánított éles meghatározzák a tetején a fájl, néhány
fajta állandó viszonyokat a puszta nagybetűs.
Tehát valahol kapacitás meghatározása mivel a lehető legnagyobb méretet.
Eközben belsejében az adatstruktúra néven egy halom nem lesz
egész szám lehet, csak ismert egyszerűen a méret.
>> Tehát, ha én, hogy képviselje ezt most képszerűen, tegyük fel, hogy ez a
egész fekete doboz képviseli a verem.
Belül van két változó között.
Így fogom felhívni a első a méret.
És a második fogok felhívni tömbként.
>> De csak, hogy a dolgok rendben, általában szeretném felhívni egy tömb, mint a
, de ez a fajta szép ha egyezik valóság, vagy
egyezik a mentális modell.
Hadd inkább felhívni a tömb függőlegesen, ami csak ismét
művész előadásában.
Nem igazán számít, hogy mit van a motorháztető alatt.
És azt mondom, hogy az alapértelmezés szerint, kapacitás lesz három.
Szóval ez lesz a 0 helyen, a lesz hely 1, ez
lesz hely 2.
>> Ha megvesztegetni egy stressz labdát, lenne valaki szeretné, hogy jöjjön fel, és futtassa a
fórumon itt egy pillanatra?
OK, láttam a kezét először.
Gyere fel.
Rendben van.
Tehát azt hiszem, hogy Steven.
Gyere fel.
Rendben van.
>> De tegyük most hátra a kezdeti állam a világon, ahol azt
éppen bejelentették a verem, és ez lesz a kapacitás három.
De a méret még nem határozták meg.
Tálcák még nem határozták meg.
Így egy-két kérdést.
És hadd adjak mic így Ön aktívabban részt venni ebben.
>> Tehát mi van belül a méret ebben a pillanatban az időben, ha minden, amit tett,
kijelentette, a verem egy sort?
>> Steven: Nem sok.
>> DAVID MALAN: OK, nem sok.
Nem tudjuk, hogy mi van benne a méret, tudjuk, hogy mi van benne
Ennek a tömbnek itt?
>> Steven: csak véletlenszerű kódot, igaz?
Just -
>> DAVID MALAN: Igen, megyek hívják kód, de a véletlen -
>> Steven: A dolgok.
>> DAVID MALAN: Dolgok, mint véletlen
>> Steven: Bit.
>> DAVID MALAN: Bit, igaz?
Tehát szemét értékek, nem igaz?
Így permutációk 0-t és 1-es.
Maradványai a korábbi használat az a memória.
És nem igazán tudom, mi az értékeket vannak, ezért általában felhívni őket
mint kérdőjelek.
>> Tehát az első dolog, amit még valószínűleg szeretne majd csinálni itt -
és hadd ezen a területen belül onnan a név - tálcákat.
Mit kellene feltehetően inicializálása mérete, ha azt akarjuk, hogy
elkezdené alkalmazni ezt a stack?
>> Steven: Tray sub 3.
>> DAVID MALAN: Szóval, OK.
Ahhoz, hogy tiszta, kapacitás nyilvánítják máshol három.
És ez az, amit én is használtam kiosztani a tömb.
Méret fog hivatkozni, hogy hány tálcák jelenleg a verem.
>> Steven: Zero.
>> DAVID MALAN: Így kell nulla.
Így megy előre, és minden ujját, rajzoljon egy nulla méretű.
Rendben van.
Akkor most, mi van ennek a itt, nem tudjuk.
Ezek tényleg csak szemetet értékeket.
Így lehet rajzolni kérdőjelek, de maradjunk a tábla tiszta már
mert nem számít mi van ott.
Nem kell, hogy inicializálja a tömböt semmit, mert ha tudjuk, hogy
a méret a verem nulla, nos, nem nézett semmit
ez egyébként a tömb Ezen a ponton az időben.
>> Ezért most tételezzük fel, hogy nyomja meg a 9-es szám a verembe.
Hogyan kellene frissíteni az adatstruktúra belül a fekete doboz?
Milyen értékeket kell változtatni?
>> Steven: Within -
a méret?
>> DAVID MALAN: OK.
Méret váljon, mi?
>> Steven: Méret lenne az egyik.
>> DAVID MALAN: OK.
Így a méret kell, hogy legyen.
Így ezt egy pár módon.
Hadd adjak, most a ujj egy radír.
Rendben van.
, Akkor most az ujját egy ecsettel.
Rendben van.
És most mit kell változtatni, Nyilvánvaló, hogy az adatstruktúra?
>> Steven: megyünk a alulról felfelé 9-ig.
>> DAVID MALAN: 9.
OK, jó.
Tehát még mindig nem számít, mi a helyen, egy-két, mert ők
szemét értékeket, de ne zavarja keres ott, mert mérete
azt mondja, hogy csak az első elem valóban jogos.
Szóval most nyomja rá a 17 listán.
Mi történik ezen a képen?
>> Steven: Szóval méretet fog menni a kettő.
>> DAVID MALAN: OK.
Te radír -
hoppá.
Te egy radír.
>> Steven: radír.
>> DAVID MALAN: Te egy ecsettel.
>> Steven: Brush.
>> DAVID MALAN: OK.
És még?
>> Steven: És akkor mi -
>> DAVID MALAN: szorgalmaztuk 17.
>> Steven: Kitartunk 17 a tetején, így -
>> DAVID MALAN: OK, jó.
>> Steven: - ejtse le.
>> DAVID MALAN: Rendben.
Egyre egyszerű.
Nem fogok segíteni ebben az időben.
Nyomja 22..
>> Steven: Kész.
Válás radír.
Kezdek egy ecsettel.
És akkor én üzembe 22.
>> DAVID MALAN: 22.
Kiváló.
Tehát még egyszer.
Én most megy, hogy álljon a verembe 26.
>> Steven: Ó.
Ó istenem.
Tényleg elkapott ki őr.
>> DAVID MALAN: Ön nem látni a jövő?
>> Steven: Nem láttam a jövő.
Tudnánk újra kezdeti kapacitása?
>> DAVID MALAN: Ez egy jó kérdés.
Így már egyfajta festett magunkat a sarokban itt.
Tényleg nem jó ki Steven mert már kiosztott a tömb
statikusan, hogy úgy mondjam, belülről az adatszerkezetet.
És most már lényegében kemény kódolt azt, hogy a méret három.
Tehát nem igazán újraelosztása azt.
>> Tudtuk, ha mentünk vissza, azt újra tálcák, hogy egy mutató, amely
mi majd malloc kéznél memória.
Mert ha megvan a memóriát a kupac keresztül malloc, mi
aztán kiszabadítani.
De mielőtt felszabadítása, mi lehetett átcsoportosítása egy nagyobb darab memória,
frissíti a mutatót, és így tovább.
De most, ez nagyon A legjobb, amit tehetünk.
Push és Pop feltehetőleg lesz hogy a jel valamilyen hiba.
>> Így például, a végrehajtás push visszatérhet a bool, amely
korábban tért vissza igaz, igaz, igaz.
De a negyedik alkalom, hogy megy, hogy hogy visszatérjen hamis, például.
Rendben van.
Nagyon jól sikerült.
Gratulálok.
Megérdemled a stressz labdát ma.
>> [Taps]
>> Steven: Köszönöm.
>> DAVID MALAN: Köszönöm.
OK, így ez úgy tűnik, hogy nem sok Egy lépés előre, nem igaz?
Leírtuk az adatok szerkezetét.
Ez volt meggyőző, nem?
Operációs rendszerek tetszik.
Úgy látszik, a web is, hogy ezzel, és más alkalmazásokat is.
De milyen hülye korlátozás, hogy nem vagyunk vissza a fajta a hét két határérték
ahol már fix méretű tömbök.
>> Tehát valóban egy pár hogyan tudnánk megoldani ezt.
Tudtuk dinamikusan osztja a tömb, nem nehéz kódolás, mint én már
itt történik, hanem újra kijelentette ez, csak hogy világos legyen, mint
valami ilyesmi.
Int * tálcák, nem döntő a kapacitás még.
De amikor állapítsa meg a stack máshol az én kódot, tudtam akkor hívja malloc,
kap a címét egy darab memória, és én hozzá
a címet a tálcákat.
>> Aztán, mivel ez csak egy darab memória, nem tudtam tovább használni tér
konzol jelölést a szokásos módon.
Mert megint van valami a funkcionális megfelelője tömbök és
darabokban a memóriát, hogy jön vissza malloc.
Tudjuk kezelni az egyik, mint a másik a mutató számtani vagy
szögletes zárójel jelölést.
Tehát ez az egyik megközelítés.
>> De hogyan lehet, hogy más is alkalmazzák ezt a azonos adatstruktúra, esetleg?
Nem igaz?
Úgy érzem, mi csak megoldotta ezt a probléma, mint egy héttel ezelőtt.
Mi volt a megoldás erre a problémára hogy Steven ütközött?
Tehát láncolt listák, igaz.
>> Ha a probléma az, hogy mi vagyunk festés magunkat szögletre elosztása
előre túl kevés a memória, hogy akkor meg kell valahogy kezelni, nos,
miért nem csak elkerülni, hogy ki összesen?
Miért nem csak kijelentik tálcák lenni mutató egy csomópont, ergo a láncolt lista,
majd egyszerűen osztja új csomópontok minden alkalommal Steven szükséges, hogy illeszkedjen a
számot az adatszerkezetet.
>> Így a kép meg kell változtatni.
Ez nem lesz olyan tiszta és egyszerű, mint most egy sor három ints.
Most lesz egy mutató a struct, és hogy a struktúra fog
egy int, és a következő mutató.
Meg fog vezetni, hogy a mutató segítségével másik ilyen struktúra a
egy ilyen struktúra.
Így a kép valójában egy kicsit Messier-.
És mi volna nyilak árukapcsolás mindent együtt.
>> De ez rendben van, igaz, mert a láttunk, hogyan kell ezt csinálni.
És ha egyszer kap kényelmes végrehajtása olyasmi, mint egy kapcsolt
lista, amit meg kell tennie, ha úgy dönt, hogy végre egy hash tábla
külön láncolás a p-set 6, akkor használni, mint egy építőköve, vagy
összetevő vagy Scratch beszélni, a eljárás, amit teszel, akkor
létrehozta a saját puzzle-darab , amit aztán újra.
Tehát kompromisszumok, de a lehetséges megoldásokat hogy már tényleg látott.
>> Így elég gyakran, látod ezt minden két évvel, amikor az Apple kiadások
valami új, és az egész őrültek sorakoznak kívül az Apple
boltba vásárolni marginális frissíteni a hardver.
Ezt mondom, hogy rendben van, mert a Én egyike vagyok azoknak az embereknek.
Szóval milyen adatstruktúra jelenthet ez a valóság?
>> Nos, ez egy sor, egy sor.
Így a brit nevezném általában a sor, úgyhogy ez egy szép név.
És a két művelet, hogy a sor támogatja hívjuk a Enqueue
működés és a dequeue működés, amelyek hasonló
szellem push és pop.
Ez csak valami különböző egyezmény, amit mi meghívjuk ezeket.
De sorba állítását valamit azt, hogy adjunk vagy helyezze azt az adatszerkezetet.
A dequeue jelenti, hogy távolítsa el azt.
De míg a verem egy LIFO adat szerkezet, a sorban az első az,
first out adatstruktúra.
>> Ha te vagy az első, aki a sorban, lesz az első, aki kap
a sorból, és vásárolni az új eszközt.
Képzeld el, hogy ezek az emberek ideges lenne ha az Apple helyett használt verem, a
Például, hogy hajtsák végre a szedés fel az új játék.
Tehát sorok értelme, természetesen, és el tudunk képzelni mindenféle
alkalmazások, feltehetően, a sorok, különösen, ha azt szeretné, méltányosság.
Szóval, hogyan lehet, hogy mi végre ezeket mint egy adatstruktúra?
>> Nos, azt javaslom, hogy mi is kell csinálni így.
Így fogok most számokat.
Szóval majd tartsa egyszerű, és nem feltétlenül beszélünk szempontjából tálcák.
Csak számok, hogy az emberek az ütött.
Kapacitás fog ismét rögzítse a száma az embereknek, hogy lehet
Ezen a vonalon három- bármilyen más értéket.
>> De azt javaslom, hogy el kell követni nem csak a méret a
sor, hogy sok dolog benne.
Így a méret a jelenlegi méret, kapacitás a legnagyobb méret.
Csak újra nómenklatúra megállapodás szerint.
Miért kell egy újabb int belső Egy sor nyomon követni, hogy ki van
első a sorban?
Miért kell tennem, hogy ebben az esetben?
>> Nos, hogy ez a kép fog változni?
Én talán újra a legtöbb ezt a képet.
Hadd menjek előre, és törli, mi van itt.
Majd ad ez egy kicsit más néven itt.
Menjünk megszabadulni a 17, menjünk megszabadulni A 9, menjünk megszabadulni a 3.
És tegyük hozzá még valami.
Azt javaslom, hogy el kell nyomon követni az első a listán, ami csak
lesz egy int is.
És fogunk tartani, hogy egyszerű.
Nem láncolt lista most.
>> Majd elismerem, hogy fogunk bump ellen ezt a határt.
De mit akarok látni, történni ebben az időben?
Tegyük fel, hogy megyek előre, és az első ember jön a sorban, és a
ez a 9-es számú.
Mi a stressz labda.
Lehet lopni, mondjuk, két vagy három ember?
Egy, kettő, három?
Gyere fel.
Már az első, mert a fogjuk, hogy ez egy gyors.
>> Mindannyian most lesz egy rajongó fiú sort Apple.
Akkor nem kap az Apple hardver a végén ez mégis.
Rendben van.
Szóval 9-es számú, akkor 17-es szám, 22-es számú.
Ezek tetszőleges számok, mint a diák azonosítók vagy miegymás.
És csak egy pillanatra, kezdjük elkezd hozzá dolgokat.
És én futni a fórumon itt ebben az időben.
>> Tehát ebben az esetben, már inicializált Az első, hogy -
Igazából nem igazán érdekel, mi a elöl van, mert a mérete nulla.
Szóval ez lehet, hogy csak egy kérdőjel.
Ezek mind kérdőjelek.
Tehát most elkezdjük, hogy valóban látni néhány emberek sorakoznak a boltban.
>> Tehát, ha a 9., te vagy az első ott 5:00, megy előre, és sorban,
vagy este.
OK.
Tehát most 9 itt.
Tehát 9-ben az első a listán.
Szóval megyek előre, és frissíti mérete az aktuális adatok
szerkezet már nem lehet 0, hanem, hogy 1.
Megyek, hogy 9-én a előtt a listából.
Hadd menjek előre, és váltani a képernyő így láthatjuk múlt minket.
>> És most mit akarok , hogy elöl?
Fogom nyomon követni, hogy a első a sorban most
a 0 helyen.
Mert ami mellett fog történni?
Nos, tegyük fel, most sorba állítását 17 is.
Így hop sorban van.
És ismét, a fajta ajtót, hogy a üzlet lesz itt.
Tehát most adtam 17.
És bár ezek a srácok blokkolja a képernyőn, ez rendben van,
mert látjuk, hogy itt.
Bocsánat.
>> Közönség: tudunk mozogni -
>> DAVID MALAN: Nem, ez rendben van.
Hatalmas ott.
Tehát 17 most belül a sorban.
Meg kell frissíteni, amely mezők most mégis?
OK, határozottan méret.
És mi van elöl?
OK, nem.
Front nem kell változtatni, mert a ellentétben a verem, akkor
szeretné, hogy a méltányosság.
Tehát, ha 9 jött először, azt akarjuk, 9 , hogy az első a sorból
és a boltba.
>> Valójában, lássuk ezt.
Mielőtt be 22, nézzük megy előre, és dequeue 9.
Mi a neved?
>> Közönség: Jake.
>> DAVID MALAN: Jake megy hogy dequeued most.
Így kap járni a boltba.
És úgy, mintha a boltban ott van.
Akkor most mit kell - DIT-dit-dit!
Mit kell most történni?
Tervezési döntés.
Tehát nem egy rossz ösztön, de - mi is a neved?
>> Közönség: David.
>> DAVID MALAN: David.
Szóval, mit tett Dávid?
Megpróbálta rendezni az adatok rögzítése struktúra és áttérés a helyzetét
Jake a korábbi helyen.
És ez rendben van, ha hajlandóak vagyunk elfogadja, hogy, mint egy
végrehajtás részletesen.
De először nézzük frissíti az adatokat szerkezet mielőtt csinálni.
Mert nem tetszik az ötlet minden az emberek változó ebben a sorban.
>> Ez nem nagy ügy, ha David csinálja egy lépés, de a lényeg, szerintem vissza
amikor már nyolc önkéntesek a színpad és tettünk, mint az elhelyezési
sort, ahol meg kellett kezdeni mozog mindenki körül.
Hogy van drága, ugye?
Ez tesz engem szervilizmus a nagy O n, nagy O n négyzeten újra.
Ez nem érzi, mint az ideális eredményt.
>> Szóval csak frissíteni ezt.
Tehát a méret a sorban 2. már nem.
Ez most csak 1.
De most már frissíteni valamit Én nem frissíti korábban, a
előtt a listából.
Én is csak azt mondom, hogy a hely 1?
Tehát most már szemét érték itt, szemét érték itt, és David a
közepén a szemetet.
De az adatstruktúra még mindig érintetlen.
>> És valóban, nem is kell változás Jake korábbi számát
9, mert kit érdekel.
Van elég információt most a méret, Tudom, hogy van egy ember
ez a sor.
És tudom, hogy ez a személy van hely 1, nem 0-ra.
Én nem számítva.
Tehát 1 is.
Így az adatok szerkezete még mindig rendben van.
>> Nos, mi történik ezután?
Nézzük Enqueue -
mi a neve?
>> Közönség: Callen.
>> DAVID MALAN: Callen.
Nézzük sorba állításához Callen és 22 már a sorban.
Akkor most mi kell változtatni itt?
Front nem fog változtatni, természetesen.
Méret fog változni, hogy ismét a 2.
És végül itt 22, 9 még mindig jelen van, de ez gyakorlatilag egy
szemét érték most.
Ez csak egy maradványa Jake múlt.
>> Most mi történik, ha Én dequeue David?
Még egy utolsó műtét, dequeue David.
Mi is elmozdulhatnak, de azt javaslom, nézzük csinálni, mint kis munka lehetséges.
Most a adatstruktúra megy vissza méretben 2-1.
De az első a sorban most lesz 2.
Nem kell változtatni ezeket a számokat most még, mert ők
csak szemetet értékeket.
>> De most mi történik?
Tegyük fel, hogy sorba állítását magam, 26?
Úgy érzem, tartozom ide.
Szóval, hogy enqueued.
Szóval ilyen ide tartozom.
És annak ellenére, hogy nem egészen értékelik ezt vizuálisan a színpadon,
mert van bőven, nekem nem állt itt, miért?
>> Közönség: Te a határokat.
>> DAVID MALAN: Így van.
Én vagyok a határokat.
Már indexelt túl határai a tömb.
Nagyon kellene az egyik három lehetséges helyszín.
Hol van a legtöbb természetes, hogy menjen?
Azt javaslom, hogy hitelből egy hét egy trükk.
A mod operátor, százalékban.
Mert én gyakorlatilag állt 3 helyzet, de én 3 mod kapacitás
így 3 százalékos jel, 3 -
teljesítmény az 3.
Mi ez?
Mi a maradék, ha akkor osszuk 3 * 3?
0-ra.
>> Tehát, hogy hozza nekem volt Jake, ami valóban jó.
Tehát most a végrehajtás ez a dolog fog
egy kicsit a fejem.
Ez tényleg csak egy sort A fejfájás, a kód.
De legalább most már szemét érték itt, de van két
törvényes ints itt.
És azt állítják, hogy most már kész pontosan mit kell tennie, amíg
mi a változás, amit Jake érték volt, hogy 26..
>> Most már elég információ még integritásának fenntartása
Ezen adatok szerkezetét.
Még mindig olyan jártál, amikor szeretné szúrni négy vagy több teljes
elemeket, de azt legalább, hogy elég hatékony ez az állandó
időt, sőt.
Nem kell aggódnia, változó mindenki, ahogy David hajlam volt.
>> Bármilyen kérdése a halom, vagy a sor?
>> Közönség: az oka annak, szükséges méretet, hogy tudd
hol van a személy?
>> DAVID MALAN: Pontosan.
Tudnom kell, hogy a méret a tömb mert kell, hogy pontosan hogyan
sok ilyen értékek legitim, és így, hogy találok hová tegye
a következő személyt.
Pontosan.
A mérete -
Igazából nem frissíti e még.
Én hozzá magam a 26.
A méret már nem 1, hanem 2.
Tehát most ez valóban segít megtalálni a A lista élére, ami nem 0, nem
1, de 2 lehet.
Az első a lista valóban a 22.
Mert jött először, így kell megengedett a boltba előttem,
bár vizuálisan állok közelebb a boltba.
>> Minden rendben?
A tapsot ezek a srácok és mi hagyjuk őket onnan.
>> [Taps]
>> DAVID MALAN: arra, hogy majd tartsa a tálcát.
Láttuk, mi történik, ha akarsz, de lehet, hogy nem.
Rendben van.
És most mi marad nekünk?
Nos, hadd javasoljuk, hogy van egy néhány más adatszerkezeteket tudtunk
elkezd hozzátéve, hogy a szerszámkészlet, amely valóban elég, elég releváns
merülünk a webes dolgokat.
Ami megint van valamilyen kapcsolat a fák formájában
úgynevezett DOM, a dokumentum objektum modell.
De majd meglátjuk többet hogy nemsokára.
>> Hadd javaslom definitionally hogy hívási fa most mi lehet ismert
inkább egy családfát, ahol néhány őse a
gyökerei a fa.
A patriarchális vagy matriarcha a éppen a fa tetején.
Anélkül, hogy házastársa, ebben az esetben.
De most mit fogunk hívni gyerekek, amelyek a csomópontok, hogy lefagy
le a bal vagy a jobb gyermek gyermek, nyilak ábrázolt itt.
>> Más szóval, egy fa adatstruktúra A számítógép, a fa nulla
vagy több csomópont.
Ha van legalább egy csomóponthoz, hogy hívják a gyökér.
Ez a dolog, hogy a vizuálisan felhívjuk a tetején.
És csomópont, mint minden más csomóponthoz is nulla, egy, vagy két, vagy három,
vagy ahogy sok gyerek a adatstruktúra támogatja.
Ebben az esetben, a gyökér, a tároló értéke egy, két gyermeke van, a 2. és 3.
így általában véve 2 a bal gyermek-és 3 a jobb fia.
>> És amikor most az 5., 6., és 7, 6 nevezhetnénk a középső gyerek.
Ha a négy gyerek, lesz zavaró.
Tehát ne használja ezt a fajta A parancsikon szóban.
De ez tényleg csak egy családfát.
És a levelek itt a csomópontok maguk nincsenek gyerekek.
Azt tedd le az alján a fa.
>> Szóval, hogyan lehet, hogy mi végre egy fa, csak két gyermek maximálisan?
Majd ez egy bináris fa.
Bi jelenti ismét két, ebben a esetében, mint a bináris.
És így ez lehet nulla, egy, vagy két gyerek maximálisan.
>> Én javaslom, hogy hajtsák végre a csomópont az, hogy a struktúra egy int n,
, majd két mutató, az egyik neve balra, az egyik neve van.
De ezek csak szép önkényes egyezmények.
És mi szép most, különösen, ha fajta küzdött fogalmilag
rekurzió, vagy úgy gondolta, hogy ez nem volt tényleg megoldás semmire,
különösen akkor, ha lehetne elfogy a memória.
Most, hogy beszélünk az adatok struktúrák és algoritmusok, amelyek lehetővé teszik
bennünket, hogy áthalad, és manipulálni őket, Kiderül, hogy a rekurzió jön vissza
sokkal vonzóbb ha nem szép módon.
>> Szóval ez azt javaslom a végrehajtása A keresés funkcióval.
Mivel két bemenet -
így gondolom, hogy ez egy fekete doboz.
Mivel két bemenet, n, int, és a mutató egy fa, egy mutatót a
csomópont, vagy tényleg a fa gyökerét, azt azt állítják, hogy ez a funkció visszatérhet
igaz vagy hamis, ezt az értéket n belül van ez a fa.
>> Mi van a fekete doboz?
Nos, négy ága.
Az első csak ellenőrzi.
Ha a fa null, csak vissza hamis.
Ha nincs csomópont, nincs n, nincs több, csak vissza hamis.
Ha mégis, n, az értéket, amit keresel A kevesebb, mint fa nyíl n, és
Csak hogy tisztázzuk, mit jelent, ha Írok fát, majd a nyíl
jelölés, n?
Pontosan.
Ez azt jelenti, hogy a hivatkozás feloldási pointer nevű fa.
Menj oda, és majd bejutni, hogy a csomópont, és kap a területen az úgynevezett n.
És hasonlítsa össze a tényleges n volt átment Search ellene.
>> Tehát, ha n kisebb, mint az n érték A fa csomópont is, jól,
mit jelent ez?
Ez semmit nem jelent az első pillantásra.
Nem igaz?
Mint amikor van egy sor értékeket, ami biztosan tetszeni alkalmazni bináris
keresés egyfajta szakadék és uralkodj.
De mit feltételezés volt meg kell, hogy bináris keresés működik egyáltalán
A telefonkönyv és korábban példa?
>> Hogyan kell válogatni.
Szóval finomítani meghatározása fa Itt nem csak egy fa, amely
bármilyen gyermekek száma.
Nem csak egy bináris fa, amely 0, 1, vagy 2 maximálisan.
De mint egy bináris keresést fa, vagy BST, ami csak egy divatos szóval a
bináris fa olyan, hogy minden csomópont bal gyermek, ha jelen van,
kevesebb, mint a csomópont.
És minden csomópont jobb fia, ha jelen van, a nagyobb
mint maga a csomópont.
>> Más szóval, ha úgy döntesz, hogy dolgozzon a fa ki, mind a számok
gondosan egyensúlyban ilyen, hogy ha van 55, mint a gyökér, 33 mehet
hogy a bal, mert kevesebb, mint 55.
77 mehet a jogát, mivel ez több mint 55.
De most észre, ugyanazt a meghatározást, ez egy rekurzív definíció szóban,
kell alkalmazni 33.
33 bal gyermeke kisebb legyen, mint az, és 33 jobb gyermek, 44, meg kell
nagyobb, mint azt.
>> Tehát ez egy bináris keresést fa, és Azt javaslom, egy kis
rekurzió, akkor most meg n.
Tehát, ha n kisebb, mint az érték n, ami jelenlegi csomópont, én megyek
előre, és punt, hogy úgy mondjam, és csak vissza, amit a válasz a
keres n a fa bal fia.
Figyeljük meg újra, ez a funkció csak vár csomópont csillag,
mutató egy csomópont.
Így biztosan meg tudom csinálni, csak fa Balra mutató nyíl, ami ahhoz vezet,
nekem egy másik csomópont.
De mi az, hogy a csomópont?
>> Nos, a ezt a nyilatkozatot, bal csak egy mutató, hogy a csak
azt jelenti, hogy én halad a keresési funkció egy másik mutató, azaz
az, amelyik a bal gyerek fa.
Tehát ebben az esetben a mutató 33, ha a ez a mi minta input Közben, ha
n értéke nagyobb, mint az n érték a jelenlegi csomópont a fában, akkor én vagyok
megyek előre, és punt a másik irányba, és csak annyit, én nem
tudom, hogy ez az érték n a fán, de azt tudom, hogy az, hogy végig a
jobb ág, hogy úgy mondjam.
Hadd hívjam fel rekurzívan megkeresi, leadott n újra, de halad a
mutató az én jobb fia.
>> Más szóval, ha én vagyok jelenleg 55 és én keresek 99, tudom, hogy 99
nagyobb, mint 55, úgyhogy ahogy téptem A telefonkönyv héttel ezelőtt, és
rendben zajlott, hasonlóan vagyunk fog menni itt.
És nem tudom, hogy ez az én jobb gyerek, és ez nem 77 van, de
Tudom, hogy ebben az irányban.
Így hívom keresést a jobb gyermek, 77., és hagyja, hogy keresési alak ki
ott van, ha 99 ebben tetszőleges példa valójában ott van.
>> Else, mi a végső helyzet?
Ha a fa null egy eset.
Ha n kisebb, mint a jelenlegi csomópont értéke egy másik eset.
Ha n nagyobb, mint a jelenlegi csomópont értéke egy harmadik eset.
Mi a negyedik és egyben utolsó eset?
Azt hiszem, az esetek, nem igaz?
Meg kell adni, hogy az n értéke jelenlegi csomópont, hogy én vagyok az.
>> Tehát, ha én keresem 55 ezen a ponton a történetben, hogy a fióktelep a
fa visszatér igaz.
Tehát mi az érdekes az, hogy mi valójában, ellentétben hét múlt, azt a fajta
A két alap esetben.
És nem kell legyen minden a tetején.
A felső egy alapeset, mert ha a fa null, nincs semmi köze.
Csak vissza kemény kódolt értéke hamis.
>> Az alsó ág van valami a alapértelmezett, ahol ha már ellenőrizték
null, már ellenőrzik, ha kell, maradt, de nem lehet, most már
ellenőrzik, ha kell, van, de nem kell, egyértelműen azt kell
ott, ahol vagyunk.
Ez egy alapeset.
Tehát van két rekurzív esetben szendvics ott középen.
De én írtam ez bármilyen sorrendben.
Csak azt gondoltam, hogy ilyen filc természetes először ellenőrizze a lehetséges hiba
majd ellenőrizze balra, majd ellenőrizze van, akkor Feltételezem, hogy te vagy a csomópont
te tényleg keres.
>> Miért lehet ez hasznos lehet?
Így kiderül -
és hadd ugrani egy teaser , hogy itt van az interneten.
Fogunk kezdeni a nem programozási nyelv az első, de a
jelölőnyelv.
A jelölőnyelv, hogy az egyik, hogy ez hasonló szellemben programozási
nyelv, de nem adja meg a képes kifejezni magát logikailag.
Csak ad arra, hogy kifejezni magát szerkezetileg.
>> Hol szeretne tenni valamit az oldalon, a weboldal?
Milyen színű akarsz csinálni?
Milyen betűméret akarsz csinálni?
Milyen szavakat, hogy tényleg szeretné a honlapon?
Szóval ez egy jelölőnyelv.
De aztán nagyon gyorsan be JavaScript, amely egy teljes körű
programozási nyelv.
Nagyon hasonló szintaktikai megjelenésű a C, de lesz egy kis
szép, erősebb, felhasználóbarát funkciók.
>> És az egyik a frusztráció ebben pont a félévben, hogy mi lesz
hamarosan végre helyesírás-ben sokkal kevesebb sornyi kódot más nyelvek
mint a C is lehetővé teszi, de az ész mi hamarosan érteni.
Ez lesz az első ilyen weboldal.
Ez lesz teljesen underwhelming, Az első, amit tenni.
Ez egyszerűen azt mondják, hello world.
De ha még soha nem láttad előtt, ez a HTML,
HyperText Markup Language.
>> Ha megy, hogy egy bizonyos menüpontra legtöbb olyan böngészővel, bármilyen internetes oldalt
Az internet, láthatjuk a HTML hogy néhány ember azt írta, hogy
létre, hogy a web oldalon.
És ez valószínűleg nem úgy néz ki, rövid, vagy tiszta, mint ez.
De ez mintáját követik e nyitott zárójelet és vágás és
betűk és potenciálisan számokat.
>> Gondoltam, kapsz egy teaser Az, hogy mit lesz képes tenni
bevétele után CS50.
Hadd menjen cs.harvard.edu / rabolni, saját Rob Bowden honlapján.
Tette ezt a számunkra.
Szóval hamarosan képes erre.
És azt is, hogy mit hallott ma reggel -
mit hallott ma reggel -
>> [HAMSTER DANCE MUSIC]
>> - Meg fogja tudni, hogy ezt a.
Ez vár ránk szerdán.
Majd meglátjuk, akkor majd.
>> [HAMSTER DANCE MUSIC]
DAVID MALAN: A következő CS50 -