[Zenelejátszó]
SPEAKER 1: Rendben.
Mindenki szívesen vissza a szakasz.
Remélem mindenki sikeresen visszanyert kvíz
a múlt héten.
Tudom, hogy egy kicsit őrült időnként.
Ahogy mondtam korábban, ha a szórás,
Nem igazán aggódni, főleg a kevésbé kellemes rész.
Ez az, hogy hol legyen.
>> Ha nem nagy, akkor félelmetes.
Kudos neked.
És ha úgy érzi, mint amire szükség van egy kicsit több segítséget, kérem
nyugodtan, hogy elérje ki, hogy bármely, a TF.
Mindannyian itt, hogy segítsünk.
>> Ezért tanítunk.
Ezért vagyok itt, minden hétfőn az Ön számára fiúk és munkaidőn csütörtökönként.
Tehát ne habozzon, hogy tudassa velem Ha aggódsz valami
vagy ha van valami a kvíz hogy tényleg szeretnék foglalkozni.
>> Így hát a menetrend ma is szól adatszerkezeteket.
Néhány ezek közül csak lesz csak hogy neked megismerjék ezeket.
Lehet, hogy soha nem végre őket ebben az osztályban.
Néhányan közülük úgy tetszik, mint a helyesírás PSET.
>> Itt van a választás között hash táblák és próbál.
Szóval akkor biztosan megy át azokat.
Ez lesz minden bizonnyal több fajta a magas szintű szakasz ma, mégis,
mert van egy csomó közülük, és ha bementünk a végrehajtás részleteit
Az összes ilyen, mi nem még átjutni láncolt listák
és talán egy kicsit a hash táblák.
>> Tehát medve velem.
Nem fogunk, hogy csinál annyi kódoló ebben az időben.
Ha bármilyen kérdése van az vagy szeretne látni végre
vagy próbáld ki magad, Azt ajánlom
megy study.cs50.net, amely példákat az összes ilyen.
Ez lesz az én PowerPoint az megállapítja, hogy mi
hajlanak arra, valamint néhány programozás gyakorlatok, különösen a dolgok
mint láncolt listák és bináris fák és halmok dákó.
Szóval kicsit magas, ami jó lenne srácok.
>> Tehát, hogy mi lesz az induláshoz.
És azt is, yes-- vetélkedők.
Azt hiszem, a legtöbben, akik a én szakasz már a vetélkedők,
de valaki jön, vagy valamilyen okból nem, ők itt az első.
>> Így kapcsolt listák.
Tudom, hogy ez a fajta megy vissza, mielőtt a kvíz.
Ez volt a megelőző héten hogy tanultunk erről.
De ebben az esetben, akkor csak megy egy kicsit mélyrehatóbban.
>> Akkor miért lehet választani a láncolt lista felett egy tömb?
Mi különbözteti meg őket?
Igen?
>> KÖZÖNSÉG: bővítheti a kapcsolt bejegyzés szemben egy tömb mérete rögzített.
SPEAKER 1: Jobb.
Egy tömb rögzített méretű, míg a láncolt lista változtatható mérettel rendelkezik.
Tehát, ha nem tudjuk, hogyan nagyon szeretnénk tárolni,
a kapcsolt listát ad nekünk egy nagy módja, hogy azért, mert mi is csak
add másik csomóponton és add tovább másik csomópont és adjunk hozzá egy másik csomóponton.
De mi lehet a kompromisszum?
Tudja valaki emlékszik a trade-off között tömbök és a kapcsolt listák?
Mmhmm?
>> KÖZÖNSÉG: Meg kell menjen végig az úton
a láncolt lista talál egy elemet a listában.
Egy sor, akkor csak talál egy elemet.
>> SPEAKER 1: Jobb.
Tehát arrays--
>> KÖZÖNSÉG: [hallható].
>> SPEAKER 1: A tömbök, mi az úgynevezett véletlen hozzáférés.
Azt jelenti, hogy ha azt akarjuk, hogy mi mindig az ötödik pont a lista
vagy az ötödik pont a mi tömb, mi csak fogd meg.
Ha ez a láncolt lista, van végiglépkedhetünk, ugye?
Tehát hozzáférés egy elem Egy tömb konstans idő,
míg a kapcsolt listát is lenne valószínűleg a lineáris idő, mert talán
mi elem is egészen a végén.
Meg kell keresni mindent.
Tehát mind ezek az adatok szerkezetek megyünk
kell eltölteni egy kis időt a, mi a pluses és negatívok.
Ha lehet, szeretnénk használja, mint a másik?
És ez a fajta a nagyobb dolog, hogy vegye el.
>> Tehát itt a meghatározása a csomópont.
Ez olyan, mint egy eleme a láncolt lista, ugye?
Tehát mind ismerős a mi typedef struktúrákat,
amely mentünk át felülvizsgálat utoljára.
Ez alapvetően csak létre más adattípusok, hogy mi lehetett használni.
>> És ebben az esetben, ez néhány csomópont hogy tart néhány egész szám.
És akkor mi van a második rész itt?
Valaki?
>> KÖZÖNSÉG: [hallható].
>> SPEAKER 1: Igen.
Ez egy mutató a következő csomópont.
Tehát ez valójában itt.
Ez a mutató a típus csomópont a következő dolog.
És ez az, amit magában foglalja a csomópont.
Cool.
>> Rendben, a keresés, mint mi voltunk csak azt mondom, mielőtt kezét, ha
fog keresni, van, hogy valóban navigálhat
át a láncolt lista.
Tehát, ha keresünk a szám 9., mi lenne kezdődik a fejünk
és hogy mutat nekünk az elején mi láncolt lista, ugye?
És azt mondjuk, rendben van, nem ez a node tartalmazza a 9-es szám?
Nem?
>> Rendben, menj a következőre.
Kövesse azt.
Vajon tartalmaz a 9-es szám?
Nem.
Kövesse a következő.
>> Tehát ténylegesen navigálhat keresztül láncolt lista.
Nem csak megy egyenesen, ahol 9.
És ha ti valóban szeretne látni néhány pszeudo-kód odafent.
Van néhány keresési funkció itt vevő in-- mit tart be?
Ön mit gondol?
Így könnyű.
Mi ez?
KÖZÖNSÉG: [hallható].
SPEAKER 1: Az a szám, amit keresünk.
Jobb?
És mi lenne ez felel meg?
Ez egy mutatót?
>> KÖZÖNSÉG: A csomópont.
>> SPEAKER 1: A csomópont a listára hogy keresünk, igaz?
Tehát van néhány csomópont mutató itt.
Ez az a pont, hogy fog tulajdonképpen halad végig a listát.
Mi meg azt egyenlő a listára mert ez csak
beállítás, hogy egyenlő a kezdete a láncolt lista.
>> És bár ez nem NULL, míg még mindig a dolgokat listánkon,
nézze meg, ha azt csomópont a szám keresünk.
Vissza igaz.
Egyébként frissíti azt, ugye?
>> Ha ez NULL, akkor lépjen ki a while ciklus és return false
mert ez azt jelenti, hogy nem találtam meg.
Mindenki kap, hogy hogyan működik?
OK.
>> Tehát beillesztés, akkor Három különböző módon.
Ön neve elé, akkor fűzze és szúrhat be válogatott.
Ebben az esetben, mi vagyunk csinálni egy elő-.
Tudja valaki, hogy ezek a Három esetben eltérő lehet?
>> Tehát azt jelenti, hogy átadjuk tesz azt az első a listán.
Tehát ez azt jelenti, hogy nem számít, mi a csomópont, nem számít,
mi az érték, mész hogy azt itt előtte, OK?
Ez lesz az első elem a listában.
>> Ha hozzáfűzi, ez megy hogy menjen vissza az a lista.
És helyezze válogatott azt jelenti, te megy, hogy valóban arra a helyre,
hol tartja a láncolt lista rendezésre.
Ismét hogyan használja e és ha használja
őket függ az Ön esetében.
Ha nem kell, hogy rendezhetők, elő- hajlamos
hogy amit a legtöbb ember használni, mert nem
kell, hogy menjen át a teljes lista találni a végén, hogy add meg, igaz?
Tudod csak kibír ez jobb.
>> Így megy keresztül 1 beillesztés most.
Tehát az egyik dolog, hogy megyek nagyon ajánlom ezt a PSET
hogy felhívja a dolgokat, mint mindig.
Nagyon fontos, hogy frissítse A mutatók a megfelelő sorrendben
mert ha frissíti őket kissé ki annak érdekében,
fogsz a végén vesztes részei a lista.
>> Így például, ebben az esetben, vagyunk mondja a fejét, hogy csak 1 pont.
Ha csak tehetem mentés nélkül ez 1,
fogalmunk sincs, hogy mi 1 mutatnia kellene most
mert elvesztettük mi a fej mutatott.
Tehát az egyik dolog, hogy emlékezzen ha csinálsz egy elő-
az, hogy mentse, ami a fejjel pont az első,
akkor újra ki kell jelölni, majd frissítse mi az új csomópontot kell mutatnia.
Ebben az esetben, ez az egyik módja annak, hogy csináld.
>> Tehát, ha azt tette ezt így ahol csak újraosztani fej,
elveszítjük alapvetően a teljes lista, ugye?
Az egyik módja, hogy az, hogy az 1. pont következő, és ezt követően fej pont 1.
Vagy meg tudod csinálni olyan, mint a átmeneti tárolás, amit beszéltem.
>> De átcsoportosítása a mutatók a megfelelő sorrendben
lesz nagyon, nagyon fontos ez PSET.
Ellenkező esetben, akkor lesz egy hash tábla vagy egy próbát, ami csak lesz
csak egy része a szavak, amit szeretne, majd you're-- mmhmm?
KÖZÖNSÉG: Mi volt az ideiglenes tárolás dolog amiről beszélt?
SPEAKER 1: az átmeneti tárolás.
Tehát alapvetően egy másik módja, hogy ezt
A tárolja a fejét valami, mint tárolja az ideiglenes változó.
Rendelje meg 1 és majd frissítse az 1. pont
hogy bármilyen head használt mutatnak.
Így nyilvánvalóan elegánsabb, mert
nem kell ideiglenes érték, de csak újabb lehetőséget, hogy csináld.
És valóban van néhány kód.
Tehát láncolt lista, mi valóban van némi kódot.
Tehát itt beilleszteni, ez elé írott.
Szóval ez beírja a fejét.
>> Tehát az első dolog, amit meg kell létrehozhatunk új node, persze,
és ellenőrizze a NULL.
Mindig jó.
És akkor meg kell rendelni az értékeket.
Amikor létrehoz egy új csomópont, akkor nem tudom, mi ez mutat a jövő,
így szeretnénk inicializálni azt a NULL.
Ha ez nem fog mutatni, hogy valami más, ez lesz újraosztani, és ez rendben van.
Ha ez az első dolog, a listán, akkor kell
hogy pont azért, mert NULL ez az a lista végére.
>> Így majd helyezze, látjuk itt rendel hozzá a következő értéke a csomópont
hogy bármi fej, amelyet mi volt itt.
Ez az, amit csináltál.
És akkor mi hozzárendelése fej pont az új csomópont, mert emlékszem,
néhány új mutató a csomópont, és pontosan ez az, amit fej.
Pontosan ezért ezt arrow accessor.
Cool?
Mmhmm?
>> KÖZÖNSÉG: Muszáj formáznia az új mellett NULL első,
vagy mi csak inicializálása fej?
>> SPEAKER 1: Új next kell lennie NULL kezdeni
mert nem tudod ahol lesz.
Továbbá, ez a fajta Csakúgy, mint a paradigma.
Beállítod egyenlő NULL csak azért, hogy meg arról, hogy minden a bázisok vonatkozik
Mielőtt tegye átváltoztató, hogy Ön mindig biztos, hogy ez lesz
mutatva, hogy egy adott érték szemben, mint a szemét érték.
Mert, igen, rendelni új next automatikusan,
de ez több, mint egy helyes gyakorlat inicializálása
ily módon, majd hozzárendelését.
>> OK, így kétszeresen láncolt listák most.
Mit gondolsz?
Mi a különbség az kétszeresen láncolt listák?
>> Tehát a mi láncolt listák, tudjuk csak mozog egy irányba, igaz?
Már csak a következő.
Csak megy előre.
>> A kétszeresen láncolt lista, mi is hátrafelé.
Tehát nem csak a számot szeretnénk tárolni,
van, ahol a következő pontok és ahol csak jött.
Így ez lehetővé teszi, hogy néhány jobb bejárás.
>> Így kétszeresen kötött csomópontok, nagyon hasonló, ugye?
Csak a különbség most egy következő és az előző.
Ez az egyetlen különbség.
>> Tehát, ha mi voltunk az elé vagy mi append-- nincs kód fel here--
de ha úgy döntesz, hogy megpróbálja helyezze be, az a fontos,
az meg kell, hogy meg róla, hogy kiosztása
mind a korábbi, és a következő mutató helyesen.
Tehát ebben az esetben, ha lenne nem csak inicializálni következő,
inicializálja a korábbi.
Ha mi vagyunk a lista élére, mi Nem csak, hogy egyenlő fej új,
de az új előző kellene pont a fej, igaz?
>> Ez az egyetlen különbség.
Ha többet szeretne gyakorlatot ezeket kapcsolt listák, a beszúrás,
törlésének, betéttel egy válogatott lista,
kérlek nézd meg study.cs50.net.
Van egy csomó nagy gyakorlatokat.
Én nagyon ajánlom őket.
Bárcsak lenne ideje, hogy menjen át őket de van egy csomó adat struktúrák
átvészelni.
>> OK, így hash táblák.
Ez talán a legnagyobb hasznos bit a PSET
itt, mert te leszel végrehajtása egy ilyen, vagy egy próbát.
Én nagyon szeretem hash táblák.
Ők elég jó.
>> Tehát alapvetően mi történik, a hash tábla
az, amikor valóban szükség van gyors beszúrás, törlés és keresés.
Ezek azok a dolgok, hogy mi vagyunk előnyben egy hash tábla.
Ők tud elég nagy, de mint látni fogjuk a próbálkozás,
vannak olyan dolgok, amelyek sokkal nagyobb.
>> De alapvetően, mind a hash táblázat egy hash függvény
hogy megmondja, melyik vödröt, hogy az egyes az adatokat, minden egyes elemek.
Egy egyszerű módja annak, hogy úgy gondolja, a hash tábla az, hogy ez csak vödör dolgok,
ugye?
Tehát, ha a dolgokat rendezés mint az első levél a nevüket,
ez olyan, mint egy hash tábla.
>> Tehát, ha én a csoportos srácok is a csoport, aki a neve kezdődik
val ide, vagy akárki születésnap a január, február, március,
bármi, ami hatékonyan létrehozása hash tábla.
Ez csak létre gyűjtőmezők Ön rendezheti elemek
így megtalálja őket könnyebb.
Tehát így, amikor szükségem van találni egy van,
Nem kell keresni keresztül minden a nevét.
Én lehet, mint, oh, tudom, hogy Danielle születésnapja in--
KÖZÖNSÉG: --April.
SPEAKER 1: április.
Így nézek én április vödör, és egy kis szerencsével,
ő lesz az egyetlen, és ott időmet állandó volt abban az értelemben,
mivel ha azt kell nézni egy csomó ember,
ez fog sokkal tovább tart.
Tehát hash táblák tényleg csak kanalak.
Könnyű módja annak, hogy gondolunk rájuk.
>> Tehát egy nagyon fontos dolog a hash tábla egy hash függvény.
Így a dolog, amit csak beszéltem, mint az első betű a név első
vagy a születésnapját hónapban, Ezek ötletek
valóban korrelál a hash függvény.
Ez csak egy módja annak eldöntésekor, hogy mely vödör Te elem megy, OK?
Tehát ez PSET, akkor nézz fel elég sok olyan hash kívánt funkciót.
>> Nem kell a saját.
Van néhány igazán jó is ki ott nem mindenféle őrült matematika.
És ha azt szeretnénk, hogy a helyesírás szuper gyors,
Szeretném határozottan vizsgálja meg egy ilyen.
>> De vannak még a egyszerű is, mint a compute
az összeget a szavak, mint például a minden betű egy szám.
Számoljuk ki az összeget.
Ez határozza meg a vödröt.
Ők is az egyszerű is, hogy olyanok, mint az összes A itt van,
az összes B itt.
Bármelyik ilyen.
>> Alapvetően, csak megmondja, hogy melyik tömb index az elem kell mennie.
Csak döntés a bucket-- ez az egész egy hash függvény.
Tehát itt van egy példa, amely csak az első betű a húr
hogy én csak beszélek.
>> Szóval van valami hash ez csak a első betű a húr mínusz A,
ami ad egy kis szám 0 és 25 között.
És mit akarsz csinálni az győződjön meg arról, hogy ez jelent
A méret a hash table-- hány vödör van.
Sok ilyen hash függvények, ők
majd visszatér értékeket esetleg Sokkal felett száma kanalak
hogy valóban van a hash tábla,
így meg kell, hogy biztos és mod azok.
Egyébként, ez fog mondani, ó, meg kell vödör 5000
de már csak 30 kanalak a hash tábla.
És persze mindannyian tudjuk, hogy ez fog eredményezni néhány őrült hibákat.
Ezért győződjön meg arról, hogy a mod mérete a hash tábla.
Cool.
Így ütközések.
Mindenki jó eddig?
Mmhmm?
>> KÖZÖNSÉG: Miért lenne vissza ilyen nagy érték?
>> SPEAKER 1: Attól függően, hogy az algoritmus hogy a hash függvény.
Néhányan közülük fog tenni őrült szorzás.
És ez az egész kezd egy egyenletes eloszlás,
így meg néhány igazán őrült dolgokat néha.
Ez minden.
Bármi más?
OK.
>> Így ütközések.
Alapvetően, ahogy már mondtam, A legjobb esetben,
minden vödör Nézek az megy, hogy egy dolog,
így nem kell nézni minden, igaz?
Azt sem tudom, hogy ott van, vagy ez Nem, és ez az, amit igazán akar.
De ha van több tízezer adatpontok és kevesebb, mint ez a szám
A kanalak, mi megy, hogy ütközések ahol végül valami
megy, hogy a végén egy vödör, amely már rendelkezik egy elem.
>> A kérdés tehát az, hogy mi teszünk ebben az ügyben?
Mit tegyünk?
Már van ott valami?
Vajon csak dobd ki?
>> Nem.
Meg kell tartani mind a ketten.
Így az is, hogy mi általában erre van, mi?
Mi az adatstruktúra mi csak beszélgettünk?
KÖZÖNSÉG: láncolt lista.
SPEAKER 1: A láncolt lista.
Tehát most, ahelyett, hogy minden egyes ilyen vödrök csak úgy, egyik eleme,
ez meg fog tartalmaz csatolt listát az elemeket, amelyeket kivonatos bele.
OK, nem mindenki olyan, hogy ez az ötlet?
Mert nem lehetett tömb mert nem tudom, hogy sok mindent
lesznek ott.
A láncolt lista lehetővé teszi számunkra, hogy már csak a pontos számot,
a kivonatos ebbe a vödör, ugye?
>> Tehát lineáris tapintás alapvetően ez ötletem
ez az egyik módja annak, hogy foglalkozik az ütközést.
Mit tehetünk, ha ebben a ügy, bogyó volt a kivonatos 1
és mi már valamit, csak
menj le, amíg találsz egy üres helyet.
Ez az egyik módja annak, hogy kezelni.
A másik módja, hogy ez, amit mi csak
called-- a kapcsolt lista hívják láncolás.
>> Tehát ez a gondolat akkor működik, ha A hash tábla úgy gondolja,
sokkal nagyobb, mint az adathalmaz, vagy ha
szeretné próbálni, és minimalizálni láncolás amíg nem feltétlenül szükséges.
Tehát az egyik dolog lineáris szondázás nyilvánvalóan azt jelenti,
hogy a hash függvény nem annyira hasznos
mert fogsz a végén segítségével A hash függvény, kapok egy pontot,
Ön lineáris szondával le Néhány hely, ami elérhető.
De most, persze, semmi más, ami végül oda,
fogsz kell keresés még lejjebb.
>> És van egy sokkal nagyobb keresés költség, amelyet
megy bevitele egy elemet a hash tábla, igaz?
És most, ha megy, és próbálja megtalálni bogyó megint, fogsz hash azt,
és azt fogja mondani, ó, nézz vödör 1,
és ez nem lesz 1 vödör, szóval
kell majd áthalad keresztül a többi hasonló.
Szóval ez néha hasznos, de a legtöbb esetben,
fogjuk mondani, hogy láncolás az, amit akarok.
>> Így beszéltünk erről korábban.
Van egy kis magam előtt.
De láncolás alapvetően azt minden vödör a hash tábla
csak egy láncolt lista.
>> Tehát más módon, vagy több műszaki Így, hogy gondoljanak egy hash tábla
az, hogy ez csak egy tömb kapcsolt listák, amelyek
amikor írsz a szótárba és próbál betölteni azt,
gondolt rá, mint egy tömb kapcsolt listák
teszi sokkal könnyebb az Ön inicializálása.
>> KÖZÖNSÉG: Tehát hash tábla van egy előre meghatározott méretű,
mint a [hallható] kanalak?
>> SPEAKER 1: Jobb.
Tehát van egy meghatározott számú kanalak hogy determine--
amely srácok kellene nyugodtan játszani.
Ez is elég jó hogy mi történik
ahogy változik a több vödör.
De igen, van egy meghatározott számú kanalak.
Mi teszi lehetővé, hogy illeszkedjen a sok elem, amennyire szüksége van
ez külön láncolás, ahol összekapcsolta listákat minden vödör.
Ez azt jelenti, a hash tábla lesz pontosan a méret
hogy meg kell, hogy legyen, nem igaz?
Ez a lényege a kapcsolt listák.
Cool.
>> Tehát mindenki OK ott?
Rendben van.
Ah.
Mi történt?
Tényleg most.
Találd valaki megöl.
>> OK fogunk menni próbálkozás, ami egy kicsit őrült.
Szeretem hash táblák.
Azt hiszem, nagyon jó.
Megpróbálja hűvös is.
>> Tehát nem mindenki emlékszik, mi egy próbát az?
Meg kellett volna át azt röviden előadás?
Emlékszel milyen, hogyan működik?
KÖZÖNSÉG: Én csak bólogat hogy mi nem megy rajta.
SPEAKER 1: Mi nem megy rajta.
OK, mi igazán fog menni mint most az, amit mondasz.
>> KÖZÖNSÉG: Ez a visszakeresés fa.
>> SPEAKER 1: Igen.
Ez egy visszakeresés fa.
Félelmetes.
Tehát az egyik dolog, hogy észre itt az, hogy mi keres az egyes karaktereket
itt, ugye?
>> Szóval mielőtt a mi hash függvény, keresték meg a szavak, mint az egész,
és most keresünk tovább a karakterek, igaz?
Tehát Maxwell ide, és Mendel.
Tehát alapvetően egy try-- módon gondolkodni ez, hogy minden szinten van
egy tömb betűk.
Szóval ez a gyökér csomópont itt, ugye?
Ez az összes karakter a ábécé a kezdete minden szó.
>> És mit akarsz csinálni az mondjuk, OK, van néhány M szó.
Fogunk keresni Maxwell, így megyünk M. és M pontok egy egész
másik a tömb, ahol minden szó, amíg van
van szó, hogy van egy mivel a második levél,
amíg van egy szó, van B, mint a második levél,
akkor azt a mutató majd néhány következő tömb.
>> Ott valószínűleg nem a szó MP valami,
így a P álláspontját e tömb, ez csak NULL.
Azt mondaná, rendben van, nincs szó hogy a M követ P, OK?
Tehát, ha belegondolunk, minden az egyik ilyen kisebb dolgokat
valójában egyik ilyen nagy tömbök, A-tól Z
Szóval, mi lehet az egyik dolog ez egyfajta hátránya egy próbát?
>> KÖZÖNSÉG: Sok memóriát.
>> SPEAKER 1: Ez egy csomó emlék, ugye?
Mindegyik blokk itt jelentése 26. terek, 26 elem tömb.
Így próbál helyet kap hihetetlenül nehéz.
>> De nagyon gyorsan.
Szóval hihetetlenül gyors, de igazán tér hatékony.
Kicsit ki kell találnom ki melyiket szeretné.
Ezek nagyon klassz a PSET, de ők nem vesznek fel sok memóriát,
így kompromisszumot.
Igen?
>> KÖZÖNSÉG: Lehetséges volna hogy hozzanak létre egy próbát, majd
ha az összes adatokat, hogy te need--
Én nem tudom, hogy lenne értelme.
Én megszabadulni az összes NULL karaktert, de aztán
akkor nem lesz képes index them--
>> SPEAKER 1: Még mindig szükség van rájuk.
>> KÖZÖNSÉG: - az azonos módon minden alkalommal.
SPEAKER 1: Igen.
Meg kell a NULL karakter legyen tudod, ha nem egy szó ott.
Ben ettél, amit akar?
OK.
Rendben, megyünk hogy menjen egy kicsit
a technikai részletek mögött egy próbát és a munka egy példán keresztül.
>> OK, így ez ugyanaz a dolog.
Mivel a láncolt lista, a legfontosabb kedves of-- mi a szó, amit akar? -
mint építőköve volt a csomópont.
Egy próbát, mi is van egy csomópont, de ez mást jelent.
>> Tehát néhány bool hogy jelenti, hogy a szó valóban
létezik ezen a helyen, majd van néhány tömb here-- vagy inkább,
ez a mutató egy sor 27 karakter.
És ez az, ebben az esetben, ez a 27-- Biztos vagyok benne, mindannyian olyanok, mint a vár,
van 26 betű az ábécében.
Miért van 27?
>> Tehát attól függően, hogy Így végre ezt,
ez egy PSET hogy engedélyezett aposztróf.
Szóval ezért a plusz egy.
Akkor is van néhány esetben a null terminátor
szerepel, mint az egyik karakterek, hogy ez lehetővé tette, hogy,
és ez hogyan ellenőrizze, hogy ha ez a vége a szó.
Ha érdekel, nézd meg a Kevin videó study.cs50,
valamint Wikipedia jó források hiányában.
>> De megyünk, hogy menjen át csak egyfajta arra, hogyan lehet a munka révén egy próbát
ha az adott ember.
Tehát van egy szuper egyszerű, hogy itt rendelkezik a "denevér" és a "zoom" bennük.
És mint látjuk itt, ez a kis hely itt
képviseli bool hogy azt mondja, igen, ez egy szó.
És akkor ennek a tömbök karakterek, ugye?
>> Így fogunk átmenni megtalálása "denevér" ebben a próbát.
Így kezdődik a tetején, igaz?
És tudjuk, hogy b megfelel A második index, a második elem
ebben tömb, mert a és b.
Tehát nagyjából a második.
>> És azt mondja, rendben van, hűvös, következik, hogy a a következő sor, mert ha emlékszünk,
ez nem, hogy minden ilyen valójában tartalmazza az elemet.
Mindegyik tömbök egy mutatót tartalmaz, igaz?
Ez egy fontos különbség, hogy a.
>> Tudom, hogy ez fog be-- megpróbálja a nagyon nehéz, hogy az első alkalom,
így akkor is, ha ez a második vagy harmadik alkalommal
és még mindig kedves A látszólag nehéz,
Ígérem, ha megy az óra Rövid megint holnap,
ez lesz valószínűleg, hogy sokkal több értelme van.
Nagyon nagy megemészteni.
Én néha még mindig vagyok mint, várj, mi egy próbát?
Hogyan kell használni ezt?
>> Így már b ebben az esetben, amely a második index.
Ha lenne, mondjuk, c vagy d vagy bármely más betű,
kell feltérképezni, hogy vissza az index mi tömb, amely megfelel.
Így venné mint rchar és mi csak vonjuk le a leképezni a 0 és 25.
Mindenki jó, hogyan Térkép a karaktereket?
OK.
>> Szóval megy a második, és látni, hogy igen, akkor nem NULL.
Mi lehet lépni ezt a következő tömb.
Így megyünk tovább, hogy ez a következő tömb itt.
>> És azt mondjuk, rendben van, most kell, hogy ha egy van itt.
Van egy null vagy mégsem valójában előrelépni?
Így a valóban mozog továbbítja az ezt a tömböt.
És azt mondjuk, OK, t az utolsó levél.
Szóval megy a t az index.
És akkor haladunk előre mert van egy másik.
És ezt mondja lényegében, hogy igen, azt mondja, hogy van egy szó here--
hogy ha követi ezt út, megérkezett
olyan szó, amiről tudjuk, hogy "denevér".
Igen?
>> KÖZÖNSÉG: Vajon szabvány is, hogy a a 0. index, majd egy sort 1
vagy hogy a végén?
>> SPEAKER 1: Nem.
Tehát, ha visszatekintünk a mi nyilatkozat itt, ez egy bool,
így saját eleme a csomópont.
Szóval ez nem része a tömb.
Cool.
Tehát, ha véget ér a szó, és mi vagyunk Ebben a tömb, amit akarunk csinálni
ez nem egy csekket ez a szó.
És ebben az esetben, akkor visszatér igen.
>> Szóval ez a megjegyzés, tudjuk, hogy "állatkert" - , mint tudjuk, az emberek, hogy a "állatkert" egy szó,
ugye?
De próbáld itt lenne azt mondják, nem, ez nem az.
És azt mondják, hogy azért, mert nem jelöltek meg, mint a szó itt.
Annak ellenére, hogy tud elmozdulni át ez a tömb,
ezt próbálja azt mondaná, hogy nem, állatkert nincs a szótárban
mert mi nem megjelölt, mint olyan.
>> Tehát az egyik módja, hogy-- ó, bocsánat, ez egy.
Így ebben az esetben a "állatkert" nem egy szó, de ez a mi próbát.
De ez, mondjuk azt akarjuk bevezetni a "fürdő", hogy mi történik
az követjük through-- b, a, t.
Vagyunk ebben a tömbben, és megyünk keresni órán.
>> Ebben az esetben, amikor nézd meg a mutató az óra,
ez mutató NULL, OK?
Tehát, ha ez kifejezetten rámutatva, hogy egy másik tömb,
ha feltételezzük, hogy a mutatók ebben tömb mutatnak null.
Így ebben az esetben, h mutat null így nem tehetünk semmit,
így ez is visszatér hamis, "fürdő" nem itt.
Tehát most vagyunk valójában megyek át
hogyan valójában mondjuk hogy "állatkert" a mi próbát.
Hogyan helyezze "állatkert" a mi próbát?
Így az azonos módon, hogy kezdtük a láncolt lista, kezdjük a gyökér.
Ha kétségei vannak, kezdődik a gyökere ezeket a dolgokat.
>> És mi mondjuk, OK, z.
z van ebben, és igen.
Szóval áttérnek az a következő tömb, OK?
És akkor a következő, azt mondjuk, OK, nem o létezik?
Ez nem.
Ez megint.
>> És így tovább a következő, azt mondtam, OK, "állatkert" már létezik itt.
Csak annyit kell tennie, hogy megadja ezt az egyenlő igaz, hogy van egy szó van.
Ha követték mindent akár korábban azon a ponton,
ez egy szó, így csak a állítsd egyenlő ilyen.
Igen?
>> KÖZÖNSÉG: Tehát akkor ez azt azt jelenti, hogy a "ba" szó is?
>> SPEAKER 1: Nem.
Tehát ebben az esetben a "ba" kapnánk itt, azt mondanám, hogy egy szó,
és ez még mindig nem lehet.
OK?
Mmhmm?
>> KÖZÖNSÉG: Tehát, ha ez a szó és igent mondasz, akkor
tartalmaznak menni m?
>> SPEAKER 1: Tehát ez arról szól, hogy with-- töltöd ezt.
Azt mondják, hogy "állatkert" szó.
Ha megy a check-- mint, mondjuk azt akarom mondani,
jelent "állatkert" létezik ebben a szótárban?
Te csak akkor fog keresni "állatkert" és nézze meg, hogy ha ez a szó.
Te soha nem fog mozogni át m, mert ez nem
amit keres.
>> Tehát, ha azt akarta, hogy valóban add "fürdő" ebbe a próbálkozás,
tennénk ugyanezt mint mi a "állatkert"
kivéve azt látnánk, hogy amikor megpróbál és kap h, ez nem létezik.
Szóval lehet gondolni ezt próbálják kell egy új csomópont egy láncolt lista,
ezért kellene egy újabb egy ilyen tömbök, mint így.
És akkor mit teszünk mi van csak meg a h eleme a tömb mutató ezt.
>> És akkor mi akarunk itt csinálni?
Add meg egyenlő a valódi mert ez egy szó.
Cool.
Tudom.
Megpróbálja nem a legizgalmasabb.
Hidd el, én tudom.
>> Tehát az egyik dolog, hogy észre a próbálkozás, Azt mondtam, ők nagyon hatékony.
Így láttuk őket vesz fel egy csomó helyet.
Ők olyan zavaros.
Szóval miért is valaha is használni ezeket?
Használjuk ezeket, mert ők hihetetlenül hatékony.
>> Tehát, ha valaha is keresett egy szó, akkor csak a
által határolt hossza a szó.
Tehát, ha keres egy szó, hogy a hossza öt,
te csak mindig kell majd hogy legfeljebb öt összehasonlítás, OK?
Így teszi alapvetően állandó.
Mint beillesztés és keresés alapvetően konstans idő.
>> Tehát, ha valaha is valami állandó időben,
ez olyan jó dolog.
Nem lehet jobb, mint állandó ideje ezeket a dolgokat.
Úgy, hogy az egyik hatalmas pluses próbál.
>> De ez sok helyet.
Szóval ilyen van dönteni mi a fontosabb az Ön számára.
És a mai számítógépek, a hely, hogy a próbát is eltarthat
talán nem befolyásolja , hogy sok, de talán
van dolgunk valami amely sokkal, sokkal több dolgot,
és egy próbát csak nem ésszerű.
Igen?
>> KÖZÖNSÉG: Várj, így van 26 levelek minden egyes ember?
>> SPEAKER 1: Mmhmm.
Igen, van 26.
Van néhány olyan szó, marker, majd Van 26 eligazítást mindenki.
És ők point--
>> KÖZÖNSÉG: És minden 26, nem mindegyikük 26?
>> SPEAKER 1: Igen.
És ezért, mint te látni, hogy kiterjeszti elég gyorsan.
Rendben van.
Így fogunk bejutni a fák, ami Úgy érzem, könnyebb, és valószínűleg
egy szép kis haladékot re próbál ott.
Így remélhetőleg a legtöbben láttam egy fa előtt.
Nem úgy, mint a szép azok kívül, amit
Nem tudom, ha valaki ment szabadban mostanában.
Elmentem alma szedés ezen a hétvégén, és jaj, istenem, gyönyörű volt.
Nem tudtam, hogy a levelek lehet nézni, hogy a szép.
>> Tehát ez csak egy fa, igaz?
Ez csak néhány csomópont, és azt rámutat arra, hogy egy csomó más csomópontok.
Amint látod itt, ez egyfajta visszatérő téma.
Csomópontok mutató csomópontok a fajta a lényeg a sok adatstruktúrák.
Ez csak attól függ, hogy mi azokat mutatnak egymással
és hogyan áthalad rajtuk keresztül és hogyan
helyezze be a dolgokat, hogy meghatározza, eltérő jellemzőkkel.
>> Így csak néhány terminológia, amit eddig látott.
Tehát gyökér bármi is legtetején.
ez, ahol mindig kezdeni.
Akkor úgy mondanám, hogy a feje is.
De a fák, hajlamosak vagyunk hivatkoznak rá, mint a gyökér.
>> Bármi alul here-- A nagyon, nagyon bottom--
a figyelembe vett levelek.
Így együtt jár a egész fa, ugye?
A levelek a széleken a fa.
>> És akkor mi is van egy pár feltételek beszélni csomópontok kapcsolatban
egymáshoz.
Tehát szülő, gyermekek és testvérek.
Így ebben az esetben, 3 a szülő 5, 6, és 7.
Így a szülő bármi is egy lépés felett bármit is
hivatkozva, így csak mint a családfa.
Remélhetőleg, ez az egész egy kicsit bit intuitívabb, mint a próbálkozás.
>> Testvérek bármilyen, amelyek ugyanazon anyavállalat, ugye?
Ők ugyanazon a szinten van.
És akkor, mint én mondván, a gyerekek csak
bármi is van egy lépés alatt a kérdéses csomópont, OK?
Cool.
Tehát egy bináris fa.
Tud valaki Megkockáztatom az egyik jellemzői a bináris fa?
>> KÖZÖNSÉG: Max két levél.
>> SPEAKER 1: Jobb.
Tehát max két levél.
Tehát ez előtt, mi volt ez bizonyítjuk a három, de egy bináris fa,
van egy max két gyermekek egy szülő, ugye?
Van egy másik érdekes jellemző.
Tudja valaki, hogy?
Bináris fa.
>> Tehát egy bináris fa lesz minden A a-- ez nem sorted--
de egy rendezett bináris fa, mindent a jobb
nagyobb, mint a szülő, és minden a bal oldalon
kevesebb, mint a szülő.
És ez volt a teszt kérdés előtt, ezért jó tudni.
Tehát ahogy mi határozza ezt meg, megint, van egy másik csomópont.
Ez nagyon hasonlít ahhoz, amit?
Kétszeresen
>> KÖZÖNSÉG: láncolt listák
>> SPEAKER 1: A kettős láncolt lista, ugye?
Tehát, ha kicseréljük ezt az előző és a következő,
ez egy kétszeresen láncolt lista.
De ebben az esetben, mi valójában van bal és jobb, és ennyi.
Egyébként ez pontosan ugyanaz.
Még mindig az elem keres,
és csak két mutatót fog, bármi is legyen a következő.
Igen, így bináris kereső fába.
Ha azt vesszük észre, mindent a Itt nagyobb than--
vagy mindent azonnal Az itt
nagyobb, mint, minden itt kisebb, mint.
>> Tehát, ha mi voltunk keresgélni, azt meg kell nézni, nagyon közel a bináris keresés
itt, ugye?
Kivéve ahelyett, fele a tömb,
mi csak nézte vagy a bal oldali vagy a jobb oldalon a fa.
Szóval ez egy kicsit egyszerűbb, azt hiszem.
>> Tehát, ha a gyökér NULL, nyilván ez csak hamis.
És ha ott van, nyilván ez igaz.
Ha ez kevesebb, mint keressük a bal oldalon.
Ha ez nagyobb, mint, keressük a megfelelő.
Ez pontosan olyan, mint a bináris keresés, csak egy másik adat struktúra
hogy mi használ.
Helyett egy tömb, ez csak egy bináris fa.
>> OK, halom.
És azt is, úgy néz ki, mint mi Lehet, hogy egy kis időt.
Ha így teszünk, boldog vagyok, hogy menjen bármely e újra.
OK, így halmozódik.
Tudja valaki emlékszik mi stacks-- bármely jellemzői kéményen?
>> OK, így a legtöbben, azt hiszem, eszik az étkezőben halls--
mint ahogy mi nem szeretnénk.
De természetesen, akkor gondolom, egy halom szó szerint csak egy halom tálcák
vagy egy halom dolog.
És ami fontos észre, hogy ez az
something-- jellemző hogy hívjuk by-- a LIFO.
Tudja valaki, hogy mi áll az?
Mmhmm?
>> KÖZÖNSÉG: Utolsó in, first out.
>> SPEAKER 1: Jobb, utolsóként, first out.
Tehát, ha tudjuk, hogy mi a dolgok egymásra rakható fel, a legegyszerűbb dolog, hogy megragad off--
és talán az egyetlen dolog, amit megragad ki, ha a verem nagy enough--
az, hogy a felső elem.
Tehát bármit került a last-- mint látjuk itt,
bármilyen szorult A legtöbb recently-- a
lesz az első dolog, hogy elsül, OK?
>> Szóval mi van itt másik typedef struct.
Ez tényleg csak olyan, mint egy gyorstalpaló az adat struktúra,
így van egy csomó dobott srácok.
Tudom.
Így még egy struct.
Yay szerkezetekhez.
>> És ebben az esetben, ez néhány mutató egy tömb, amely bizonyos kapacitás.
Tehát ez azt jelenti, a stack itt, mint a mi jelenlegi tömb
ami tartja az elemeket.
És akkor itt van egy kis méret.
>> És általában, meg szeretné tartani követi, hogy nagy a verem
mert mi ez lesz, hogy , hogy nem az, ha tudod, hogy a méret,
lehetővé teszi, hogy azt mondják, OK, én vagyok a kapacitás?
Adhatok mást?
És azt is mondja, ahol a tetején a verem
annyira tudod, mit ténylegesen felszállni.
És ez valóban lesz egy kicsit világos van.
>> Így push, egy dolog, ha valaha végrehajtani tolja,
mivel én csak azt mondom, a verem korlátozott méret, ugye?
A tömb volt némi kapacitással.
Ez egy tömb.
Ez egy fix méretű, így meg kell győződjön meg arról, hogy nem vagyunk hogy több
a mi tömb, mint mi valójában hely.
>> Ha tehát létre egy push funkció, az első dolog, amit teszel, mondjuk, rendben van,
tudom van hely az én verem?
Mert ha én nem, bocs, Nem tudom tárolni a elemet.
Ha igen, akkor a tárolni kívánt azt a tetején a halom, ugye?
>> És ez miért van nyomon követni a méret.
Ha nem követhető nyomon méret, nem tudjuk, hová tegye.
Azt nem tudom, hogy sok mindent vannak a tömbben már.
Mint nyilván vannak olyan módon, hogy talán meg tudná csinálni.
Lehet inicializálni mindent NULL majd ellenőrizze a legújabb NULL,
de egy sokkal egyszerűbb dolog csak mondani, hogy rendben van, nyomon követheti a méret.
Mint tudom, hogy van négy elem az én tömb, így a következő dolog
hogy mi fel vagyunk majd tárolja index 4.
És akkor, természetesen, ez azt jelenti, hogy Sikeresen tolt valami
rá a verem, akkor szeretnék növelni a méretét
úgy, hogy tudja, hol van olyan hogy akkor nyomja jobban a dolgokat.
>> Tehát, ha megpróbáljuk a pop valamit a verem,
mi lehet az első dolog hogy szeretnénk ellenőrizni?
Megpróbálod venni valami ki a verem.
Biztos benne van valami a stack?
Nem.
Szóval mit is akarunk ellenőrizni?
>> KÖZÖNSÉG: [hallható].
SPEAKER 1. Ellenőrizze a méret?
Méret.
Ezért szeretnénk, hogy ellenőrizze, hogy a mérete nagyobb, mint 0, OK?
És ha igen, akkor szeretnénk csökkenteni mi mérete 0 és vissza azt.
Miért?
>> Az első voltunk toló, mi tolta
ra méretet, majd frissített méretét.
Ebben az esetben, mi fogásvétel- csökkentéssel méret és akkor vesz le, kopasztás azt
a mi tömb.
Miért is tesszük ezt?
Tehát, ha van egy dolog, én verem, mi lenne az én méretem ezen a ponton?
1.
>> És hol van 1 elem tárolva?
A mi index?
KÖZÖNSÉG: 0.
SPEAKER 1: 0-ra.
Így ebben az esetben, mi Mindig kell, hogy sure--
visszatérés helyett méret mínusz 1, mert
tudják, hogy mi az elem fog tárolni 1-gyel kevesebb
függetlenül a mérete, ez a csak vigyáz rá.
Ez egy kicsit elegáns módon.
És mi csak csökkentse a méret majd vissza méretét.
Mmhmm?
>> KÖZÖNSÉG: Azt hiszem, csak általánosságban, miért lenne ez az adat struktúra
előnyös?
>> SPEAKER 1: Attól függ, hogy az összefüggésben.
Így néhány elmélet, ha dolgozik with-- OK,
hadd lássa, van egy előnyös egy ami előnyös a több, mint kívül
CS.
Halom, bármikor szüksége nyomon követni valamit, ami
a legutóbb hozzáadott amikor fogsz használni kívánt a verem.
>> És én nem hiszem, egy jó példája, hogy most.
De amikor a legutóbbi dolog a legfontosabb az Ön számára,
ez az, amikor egy halom lesz hasznos.
Próbálok gondolkodni, ha van egy jó ehhez.
Ha azt hiszem, egy jó példa a következő 20 percig, én biztosan mondani.
>> De összességében, ha van valami, mint mondtam a legtöbb, ahol a legutóbbi
a legfontosabb, hogy ez ahol egy halom kerül szóba.
Mivel a sorok a fajta az ellenkezőjét.
És a kis kutya.
Hát nem ez a jó hír, nem?
Úgy érzem, kellene csak egy nyuszi videó
kellős közepén szakasz srácok
mert ez egy intenzív szakasz.
>> Így a sor.
Alapvetően egy sor olyan, mint egy vonal.
Srácok én biztos vagyok benne, ez a mindennapi használat, csakúgy, mint a mi étkezőben.
Tehát menni és megkapjuk a tálcák, én vagyok
arról, hogy van, hogy sorban hogy ellop vagy kap az étel.
>> Tehát itt a különbség az, hogy ez FIFO.
Tehát, ha LIFO volt utolsó, első ki, FIFO először, first out.
Szóval, ez az, ahol bármit tesz az első a legfontosabb.
Tehát, ha vártál Egy line-- te is
képzeld el, ha elment megy kap az új iPhone
és ez volt a verem, ahol az utolsó ember a sorban megvan az első,
emberek megölik egymást.
>> Szóval FIFO, mindannyian nagyon ismerős és a való világban itt,
és ez mind köze van a ténylegesen milyen felüdítő az egész vonalon
és sorban szerkezet.
Így mivel a verem, mi nyomja és pop.
Egy sor, mi Enqueue és dequeue.
Így Enqueue lényegében azt jelenti, tedd rá a hátsó,
és dequeue eszközök figyelembe le elölről.
Így a adatstruktúra a kicsit bonyolult.
Van egy másik dolog, hogy nyomon követni.
>> Így anélkül, hogy a fej, ez a pontosan egy halom, ugye?
Ez ugyanaz a szerkezet, mint egy verem.
Az egyetlen dolog, más most az, hogy mi ezt a fejet, ami mit gondolsz
fog nyomon követni?
>> KÖZÖNSÉG: Az első.
>> SPEAKER 1: Igaz, a az első dolog, amit hozott.
A feje a sor.
Aki az első a sorban.
Rendben, ha mi Enqueue.
Ismét bármelyikével ezeket az adatstruktúrákat,
mivel van dolgunk tömb, azt kell ellenőrizni, ha van hely.
>> Ez olyan, mint én mondom srácok, ha megnyit egy fájlt,
meg kell, hogy ellenőrizze a null.
Ezekkel a halom és sorok, meg kell
hogy ha van hely, mert vagyunk foglalkozik a fix méretű tömb,
mint látjuk here-- 0, 1 mind 5.
Mi tehát ebben az esetben az ellenőrzés hogy ha van még hely.
A mi mérete kisebb, mint képesség?
>> Ha igen, meg kell tárolni a a farok és mi frissítjük méret.
Tehát mi is a farok lesz ebben az esetben?
Ez nem kifejezetten írva.
Hogyan tároljuk?
Mi lenne a farok lesz?
>> Szóval séta ezt a példát.
Tehát ez egy sor 6-os méret, ugye?
És mi van most, a mérete 5.
És amikor betette, ez lesz hogy menjen be az ötödik index, igaz?
Így tárolja farok.
>> Egy másik módja, hogy írjon farok lenne csak a mi tömbbel index a méret, ugye?
Ez a méret 5.
Következő dolog fog menni 5.
Cool?
OK.
Egyre kissé bonyolultabb amikor elkezdjük Messiás a fejét.
Igen?
>> KÖZÖNSÉG: Ez azt jelenti, hogy volna nyilvánítani tömb
öt elem hosszú és akkor mi adunk rá?
>> SPEAKER 1: Nem.
Így ebben az esetben, ez egy verem.
Ez kell bejelenteni mint egy sor 6-os méret.
És ebben az esetben, mi csak egy hely maradt.
>> OK, így egy dolog ebben esetben, ha a fej 0,
akkor egyszerűen hozzá a méret.
De ez egy kicsit trükkösebb mert valóban, azok
nincs dia ezt, úgyhogy megyek
felhívni egy, mert ez nem ennyire egyszerű, ha egyszer
kezdeni megszabadulni a dolgokat.
Tehát míg a verem még mindig csak
aggódnia, hogy mi a mérete amikor hozzá valamit,
egy sor akkor is kell, hogy arról, hogy a fejed elszámolni,
mert egy klassz dolog sorok az, hogy ha nem a kapacitás,
akkor valóban tenni kerületi.
>> OK, így egy thing-- ó, Ez szörnyű kréta.
Egy dolog, hogy fontolja meg a helyzet.
Majd csak nem öt.
OK, így megyünk azt mondják, a fej itt.
Ez értéke 0, 1, 2, 3, 4.
>> A fej ott van, és Kérjük, a dolgok bennük.
És azt akarjuk, hogy adjunk valamit, nem?
Tehát a dolog, hogy meg kell tudom, hogy a fej mindig
fog mozogni, és így akkor visszahurkoló körül, OK?
>> Tehát ez a sor van hely, igaz?
Ez hely a legelején, milyen a fordítottja.
Szóval, mit kell tennie, hogy mi kell számítani a farok.
Ha tudja, hogy a fej nem mozdult, farok
csak a tömbbel az index a méretét.
>> De a valóságban, ha egy sor, a feje valószínűleg frissítése.
Szóval, mit kell tennie, hogy tulajdonképpen kiszámítja a farok.
Mi tehát ez a formula itt, amit én hagyom, hogy
srácok gondol, és aztán majd beszélünk róla.
Tehát ez a képesség.
>> Tehát ez valóban kapsz egy módja annak, hogy csináld.
Mert ebben az esetben, mi?
Fejünk az 1, a mérete 4.
Ha mod, hogy 5, megkapjuk 0, ott, ahol mi kellene bemenet is.
>> Tehát akkor a következő helyzet, ha mi voltunk erre,
azt mondjuk, OK, menjünk dequeue valamit.
Mi dequeue ezt.
Mi ki ezt az elemet, ugye?
>> És most a fejünk mutat itt, és szeretnénk adni egy másik dolog.
Ez alapvetően a vissza a mi sor, ugye?
Sorok tekerje körbe a tömböt.
Ez az egyik fő különbség.
Stacks, akkor nem ezt.
>> A sorok, akkor mert minden, ami számít
az, hogy tudod, mi legutóbb hozzá.
Mivel minden lesz hozzá ez balra irányban, ebben az esetben,
, majd tekerje körbe, akkor tovább üzembe új elemek
elején a tömb mert ez nem igazán
az első a tömb többé.
Azt hiszem az elején a tömb, ahol a feje valójában.
>> Szóval ez a képlet, hogy hogyan kiszámítja a farok.
Van ennek értelme?
OK.
OK, dequeue, majd srácok 10 perc
kérdezd bármilyen tisztázó kérdéseket akarsz, mert tudom, hogy őrült.
>> Rendben, tehát ugyanabban a way-- Nem tudom, hogy ti észre,
de CS szól mintákat.
A dolgok nagyjából az ugyanaz, csak apró trükk.
Tehát ugyanaz a dolog itt.
Meg kell nézni, hogy mi valójában Van valami a sorban, igaz?
Mondjuk, OK, mi mérete nagyobb, mint 0?
Cool.
>> Ha így teszünk, akkor haladunk a fej, amely az, amit én most itt bemutatott.
Mi frissítjük fejét, hogy még egy.
És akkor csökkentse a méret és vissza az elemet.
>> Sokkal több konkrét kód study.cs50.net,
és én nagyon ajánlom megy keresztül, ha van időd,
akkor is, ha ez csak egy pszeudo-kódot.
És ha akartok beszélni keresztül hogy velem egy az egy, kérem tudassa velem
tudom.
Lennék szívesen.
Adatszerkezetek, ha szedése CS 124, akkor
tudom, hogy nagyon fog adatszerkezetek szórakoztató és ez csak a kezdet.
>> Szóval tudom, hogy nehéz.
Ez rendben van.
Küzdünk.
Még mindig.
Szóval ne aggódj túl sokat róla.
>> De ez alapvetően a gyorstalpaló az adatszerkezeteket.
Tudom, hogy sokat.
Van valami, amit szeretnék menni újra?
Bármit akarunk beszélni keresztül?
Igen?
>> KÖZÖNSÉG: Az, hogy például így az új farok 0 keresztül?
SPEAKER 1: Igen.
KÖZÖNSÉG: OK.
Akkor megy keresztül, ha volna 1 plusz 4 or--
>> SPEAKER 1: Szóval mondtál, amikor akarunk menni ezt megint?
KÖZÖNSÉG: Igen.
Tehát, ha arra rájönni out-- hol vannak Ön kiszámításának farok ebben?
>> SPEAKER 1: Tehát a farok volt in-- megváltoztattam ezt.
Tehát ebben a példában ide, ez volt A tömb keresünk, OK?
Tehát a dolgokat az 1., 2., 3., és 4..
Tehát fejünk egyenlő 1-es Ezen a ponton, és a mi mérete egyenlő 4
ezen a ponton, igaz?
>> Mindannyian egyetértenek abban, hogy ez a helyzet?
Tehát mi a fej és a méret, ami ad nekünk az 5, majd mi mod 5.
Kapunk 0, ami azt mondja, hogy 0 hol van a farok, ahol van hely.
>> KÖZÖNSÉG: Mi az a sapka?
>> SPEAKER 1: kapacitása.
Bocsánat.
Annak érdekében, hogy a méret a tömb.
Igen?
>> KÖZÖNSÉG: [hallható] előtt térjünk vissza az elem?
>> SPEAKER 1: így haladunk a fej vagy vissza a pillanat?
Tehát, ha valaki mozog, csökkentse a méret?
Várj.
Én biztosan elfelejtettem másik.
Semmi baj.
Nincs még egy formula.
Igen, amit szeretne visszatérni a fejét, majd helyezze vissza.
>> KÖZÖNSÉG: OK, mert ez pont, a fej volt a 0,
és akkor vissza akar térni index 0 és végezze fej 1?
>> SPEAKER 1: Jobb.
Azt hiszem, van egy másik formula olyan, mint ez.
Nem tudom, hogy a tetején a fejét, Én nem akarom, hogy ön a rossz.
De azt hiszem, ez teljesen érvényes mondjuk, OK, tárolja ezt element-- bármi
fej elem ez-- csökkentse a méret, mozog a feje fölött, és visszatérés
bármi ez az elem.
Ez tökéletesen érvényes.
OK.
Úgy érzem, ez nem mint a most-- te nem
fog kisétálni innen mint, igen, tudom, hogy próbál.
Megvan minden.
Ez rendben van.
Ígérem.
De adatszerkezetek van valami, hogy ez veszi el a legtöbb időt, hogy megszokja a.
Talán az egyik legnehezebb dolog, azt hiszem, a tanfolyam.
>> Így biztosan tart ismétlés és keres at-- én
Nem igazán tudom, láncolt listák amíg én túl sokat velük,
ugyanúgy, hogy én nem igazán értem mutatók
míg Elegem tanítani két év, és nem a saját psets vele.
Beletelik sok újraiterálási és idő.
És végül, ez a fajta kattintson.
>> De addig is, ha van ilyen a magas szintű megértése, hogy mit
ezek nem, a profik és cons-- amely a mi
valóban hajlamosak hangsúlyozni, különösen az intro során.
Mint, miért használjuk egy próbát át egy tömb?
Mint, mi a pozitív és negatív a minden egyes ilyen?
>> És megérteni a trade-off között minden egyes ilyen struktúrák
az, ami sokkal fontosabb most.
Lehet, hogy egy őrült kérdést, vagy két, ez
fog kérni, hogy végre push or végre pop vagy Enqueue és dequeue.
De a legtöbb esetben, hogy miután magasabb szintű megértést és több
Egy intuitív megértése is sokkal fontosabb, mint a ténylegesen
hogy képes végrehajtani azt.
>> Ez lenne igazán félelmetes, ha mindannyian mehet, és megy végre egy próbát,
de megértjük, hogy nem feltétlenül a legésszerűbb dolog most.
De akkor a PSET, ha azt szeretnénk, a, és akkor kapsz gyakorlat,
és akkor talán azt is megtudhatod igazán megérteni.
Igen?
>> KÖZÖNSÉG: OK, tehát melyek azok, amelyek azt jelentette, hogy használja a PSET?
Muszáj, hogy az egyik közülük?
SPEAKER 1: Igen.
Szóval van a választás.
Azt hiszem, ebben az esetben tudjuk beszélni a PSET egy kicsit
mert én futottam át ezeket.
Így a PSET, akkor az választás próbálkozások vagy hash táblák.
Vannak, akik megpróbálják és használja virágzás szűrők,
de ezek technikailag nem helyes.
Mivel a valószínűségi jellegű, adnak álpozitív néha.
Ők hűvös pillantást, bár.
Erősen javasoljuk, akik őket legalább.
De van a választás között a hash tábla és egy próbát.
És ez lesz, ha betölt a szótárban.
>> És akkor el kell választani A hash függvény,
akkor el kell választani, hogy hány kanalak van, és ez változhat.
Mint ha több kanalak, talán ez lesz gyorsabban fusson.
De talán te pazarlás sok helyet, hogy így, bár.
Meg kell kitalálni.
Mmhmm?
>> KÖZÖNSÉG: Azt mondtam, hogy tudjuk használni más hash függvények,
hogy nem kell hozzon létre egy hash függvény?
>> SPEAKER 1: Igen, van.
Tehát a szó szoros értelmében a hash függvény, mint a Google "hash függvény"
és keresni valami jó is.
Nem várható, hogy épít saját hash függvények.
Az emberek töltik tézisek ezeket a dolgokat.
>> Szóval ne aggódj épület saját.
Keresse meg az egyik online kezdeni.
Néhányan közülük van, hogy manipulálni egy kicsit
hogy megbizonyosodjon arról, visszatérő típusok egyeznek meg és miegymás, így az elején,
Azt javasoljuk valamit nagyon egyszerű, hogy talán csak
hash az első betű.
És akkor, ha már a munka-, beépített hűtő hash függvény.
Mmhmm?
>> KÖZÖNSÉG: Lenne egy próbát lehet, vagy hatékony, de csak nehezebb, like--
>> SPEAKER 1: Tehát egy próbát, azt hiszem, intuitíve nehezen megvalósítható
de nagyon gyors.
Ugyanakkor több helyet.
Ismét optimalizálhatja mindkét lévők különböző módon, és olyan módon to--
KÖZÖNSÉG: Hogy vagyunk osztályozzák ezt?
Vajon matter--
>> SPEAKER 1: Szóval osztályozni szokásos módon.
Fogsz osztályozni a design.
Bárhogyan is csinál, azt szeretnénk, hogy győződjön meg róla, hogy olyan elegáns, mint lehet
és olyan hatékony, mint lehet.
De ha úgy dönt, egy próbát vagy hash táblázat, amíg működik,
vagyunk boldogok vele.
És ha használni valamit, hash az első betű, ez rendben van,
mint talán hasonló design-bölcs.
Mi is elérte a pont ebben semester--
Nem tudom, ha srácok noticed-- ha
PSET évfolyamon csökken egy kicsit mert a tervezés és miegymás,
ez tökéletesen megfelel.
Ez kezd arra a pontra, ahol a programok egyre bonyolultabb.
Van több helyen akkor javítani.
>> Tehát ez teljesen normális.
Ez nem, hogy te rosszabbul a PSET.
Ez csak mi vagyunk, hogy nehezebb most.
Szóval mindenki érzi azt.
Csak osztályozott összes psets.
Tudom, hogy mindenki érzi azt.
>> Tehát ne legyen aggódik, hogy.
És ha bármilyen kérdése van korábbi psets vagy módon lehet javítani,
Megpróbálom, és írja meg véleményét a konkrét helyen, de néha késő
és kapok fáradt.
Vannak más dolgok körülbelül adatszerkezetek?
Biztos vagyok benne, a srácok nem igazán akar beszélni őket többé,
de ha van, boldog vagyok, hogy megy át őket, valamint bármi
ettől előadás a múlt hét vagy a múlt héten.
>> Tudom, hogy a múlt héten volt az egész felülvizsgálat, így akkor lehet, hogy kimarad néhány felülvizsgálat
tól előadás.
Minden egyéb kérdésre tudok válaszolni?
OK, rendben.
Hát, srácok, hogy ki 15 perccel korábban.
>> Remélem, ez volt a félig segítőkész legalábbis, és én találkozunk a jövő héten,
vagy csütörtök munkaidőben.
Vannak kéri snackek A jövő héten, ez a dolog?
Mert elfelejtettem édességet ma.
És én hozott édességet utolsó hét, de nem volt Columbus Day,
így volt, mint a hat ember, aki négy zsák cukorkát magukat.
Tudom hozni starbursts újra, ha úgy tetszik.
Starbursts?
OK, jól hangzik.
Volna egy nagy nap, srácok.