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. 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 -