[Zenelejátszási] 

ANDI Peng: Üdvözöljük héten 6 szakasz. Mi eltért a szokásos szakasza idején kedd délután ezt a szép vasárnap reggel. Köszönjük mindenkinek, hogy csatlakozott hozzám ma, de komolyan, a tapsot. 

Ez egy elég nagy erőfeszítést. Én szinte nem is teszik fel időben, de minden rendben volt. Így tudom, hogy mindannyian imént tette, hogy a tesztre. Először is, szívesen A másik oldala az, hogy. 

Másodszor, megbeszéljük. Megbeszéljük a teszt. Megbeszéljük, hogyan csinálsz az osztályban. Rendben leszel. Nálam van a vetélkedők Ön végén van, így ha akartok venni nézzék meg, teljesen rendben van. 

Olyan gyorsan, mielőtt elkezdjük, a napirendjét ma a következő. Mint látható, mi vagyunk alapvetően a gyors tüzelés egy csomó adatstruktúrák Nagyon, nagyon, nagyon gyorsan. Tehát mint ilyen, nem lesz szuper interaktív ma. Akkor csak velem ilyen kiabálva dolog, amit, és ha én megzavarja akkor, ha én is megyek gyorsan, hadd tudjam. Ezek csak a különböző adatok struktúrák, és részeként a PSET ezt következő hétre, akkor kérni, hogy hajtsák végre az egyiket, talán a két them-- ketten a PSET. OK, szóval csak fog először néhány bejelentéseket. Átnézzük halom és a sorban állás több mélysége, mint amit tettünk, mielőtt a kvíz. Megyünk át kapcsolódik listához újra, ismét, mélyebben, mint amit miénk volt a teszt. És akkor fogunk beszélni hash asztalok, fák és próbál, amelyek mind nagyon szükséges a PSET. És akkor megyünk át néhány Hasznos tippek pset5. 

OK, így kvíz 0. Az átlag 58% -os. Ez nagyon alacsony volt, és így a srácok minden nem nagyon, de nagyon jól szerint azzal. 

Elég sokat, ökölszabály, ha belül szórás az átlag különösen azért, mert mi vagyunk a kevésbé kényelmes részén, te teljesen rendben. Maga a pályán. Az élet jó. 

Tudom, hogy ez ijesztő arra gondolni, hogy Kaptam, mint egy 40% -os ezt a kvízt. Megyek nem ebben az osztályban. Megígérem neked, hogy te nem kudarcot vall az osztály. Te teljesen rendben. 

Azoknak, akik túltette Az átlagos, lenyűgöző, impozáns, mint, komolyan jól sikerült. Én azokat velem. Nyugodtan gyere őket A szakasz végén. Hadd tudja, ha bármilyen kérdések, kérdések velük. Ha összeadjuk a pontszámot rossz, ossza meg velünk. 

OK, így pset5, ez egy igazán fura héten Yale abban az értelemben, hogy mi PSET miatt Szerdán délben beleértve A nap végén, így ez valójában elméletileg fizetni kedd délben. Valószínűleg senki sem fejezte kedden délben. Ez teljesen rendben. Megyünk, hogy munkaidőben Ma este, valamint hétfőn este. És az összes szakaszt ezen a héten valójában alakítani műhelyek, így nyugodtan pop bármely kívánt szakasz, és lesz egyfajta mini-PSET műhelyek segítségért. Tehát mint ilyen, ez az egyetlen szakasz ahol tanítunk anyagot. Az összes többi részt fog koncentrálni kizárólag a segítség a PSET. Igen? 

Közönség: Hol vannak munkaidőben? 

ANDI PENG: Munkaidő tonight-- ó, jó kérdés. Azt hiszem, munkaidőn este vannak Teal vagy Commons. Ha megnézed az online CS50 és akkor megy a hivatali időben, léteznie kell egy ütemtervet, amely árulja el, hol mindegyik. 

Tudom, akár ma este illetve holnapi réce, és azt hiszem, lehet, hogy commons a múltkor. Nem vagyok benne biztos. Jó kérdés. Ellenőrizze a CS50. 

Cool, kérdések merülnek programomat a következő, mint három nap alatt? Megígérem nektek, mint David azt mondta, ez a domb tetején. Srácok, már majdnem ott. Csak három napig. Oda, és akkor majd minden jön le. Mi lesz egy szép CS-mentes szünetet. Üdv újra. Majd belevetik magukat web programozás és fejlesztés, dolog, hogy nagyon szórakoztató, mint hogy néhány, a többi psets. És ez lesz hideg, és mi lesz sok-sok móka. Majd több édességet. Elnézést a cukorkát. Elfelejtettem édességet. Ez volt egy durva reggel. Szóval ti majdnem ott, és én nagyon büszke vagyok, srácok. 

OK, így halmozódik. Aki szerette a kérdés Jack és a ruhája a kvízt? Senki? OK, ez rendben van. 

Tehát lényegében csak tudsz Képet Jack, ez a fickó itt, szeret, hogy a ruházati ki az a verem tetején, és ő hozza vissza rá A verem után tett. Tehát ily módon, soha Úgy tűnik, egyre hogy az alján a verem a ruhája. Tehát ez a fajta leírja Az alapadatok szerkezete hogyan verem megvalósítása. 

Lényegében, gondolom, egy verem, mint bármely tárgyak halmaza hová tette a dolgokat rá a tetejére, és akkor pop őket a tetején. Tehát LIFO a rövidítése szeretjük hogy use-- utolsó, first out. És így is megmaradnak, hogy a tetején a verem az első, hogy jön ki. És így a két fogalmat szeretjük társítani azzal hívják Push és Pop. Ha megnyomja valamit rá a verem, és akkor pop vissza. 

És így azt hiszem, ez a fajta egy elvont fogalom azok számára, akik szeretnék látni, mint egy tényleges végrehajtásának a valós világban. Hányan írtak esszét Talán, mint egy órával korábban, hogy volt köszönhető, és véletlenül törölt egy hatalmas darab ez, mint a véletlenül? És akkor mi vezérlő csinálni használjuk, hogy tegye vissza? Control-V, igen? Ellenőrző-Z, így az összeg idők Ennek az ellenőrző-Z megmentette az életemet, mentette meg a seggem, minden alkalommal ami végre egy kéményen keresztül. 

Lényegében az összes információt ez a Word dokumentumot, ez lesz tolta, és beugrott a fog. És így lényegében bármikor töröl semmit, akkor pop vissza. És akkor, ha szükség van rá vissza, akkor tolja, ami pedig a Control-C-nek. És így valós függvény Az, hogy milyen egyszerű adatszerkezet segíthet a mindennapi életben. 

Tehát egy struct az az út, mi valójában létre egy verem. Mi írja meghatározzák struct, majd hívjuk verem alján. És a verem, van két paraméter hogy mi is lényegében manipulálni, így van char csillagos húrok kapacitást. 

Minden, hogy csinál, teremt egy tömböt hogy tudjuk tárolni, amit akarsz ami meg tudjuk határozni a kapacitását. Kapacitás csak a max létszámú tételek tudjuk helyezni ezt a tömböt. int mérete a számláló, ami megtartja követni, hogy hány példány jelenleg a veremben. Tehát akkor mi is nyomon követni, A, Mindkét mekkora a tényleges verem, és A, B, hogy mennyi az adott köteg töltöttünk, mert nem akarjuk túlcsordulás alatt, amit a kapacitás. 

Így például, ez a szép kérdés volt a kvíz. Lényegében hogyan is álljon rá a tetejére egy halom. Elég egyszerű. Ha megnézzük azt, megyünk végig ezt. Ha [hallhatatlan] size-- emlékszem, amikor szeretnénk hozzáférni paraméter egy struct, te a neve a struct.parameter. 

Ebben az esetben, s értéke a neve a mi verem. Azt szeretné elérni a méretet belőle, így nem s.size. Tehát amíg a mérete nem egyenlő kapacitással, vagy ameddig mivel ez kevesebb, mint a kapacitás, sem lenne itt dolgozni. 

El szeretné érni a belső a verem, így s.strings, és meg fogsz tenni, hogy az új számot hogy akar szúrni ott. Mondjuk úgy, hogy mi lesz akar helyezze int n a verembe, tudnánk tenni s.strings, konzolok, s.size egyenlő n. Mivel a méret, ahol Jelenleg a verem ha megyünk, hogy álljon azt, mi csak hozzáférni bárhol a méret, a aktuális teljessége a verem, és mi nyomja a int n rá. És akkor azt akarjuk, hogy győződjön meg arról, hogy mi is megnő méret a N, így tudjuk nyomon követni voltunk hozzáadott egy extra dolog, hogy a verem. Most van egy nagyobb méretű. Van ennek értelme itt mindenki, hogyan logikusan működik? Ez kedves volt gyors. Közönség: Tud megy át A s.stringss.strings [s.size] újra? ANDI Peng: Persze, így mit jelent s.size jelenleg nekünk? Közönség: Ez a jelenlegi méretét. ANDI Peng: Pontosan, tehát a aktuális index, hogy mi nagysága lesz, és így akarjuk helyezni az új egész hogy mi akar szúrni s.size. Ennek van értelme? Mert s.strings, minden, ez a neve a tömbben. Minden ez a hozzáférés a tömb a mi struct, és ezért ha azt akarjuk, hogy helyezze n át az indexnek, mi csak hozzáférni konzollal s.size. Hűvös. 

Rendben, pop, én pszeudókód ki srácok, de hasonló elgondolás. Ennek van értelme? Ha a méret nagyobb nullánál, akkor tudom, hogy azt szeretné, hogy valamit ki, mert ha a mérete nem nullánál nagyobb, akkor Nincs semmi a veremben. 

Szóval csak azt akarom, hogy végre ezt a kódot, akkor csak pop ha van valami, hogy a pop. Tehát, ha a méret nagyobb mint 0, mi mínusz a méretét. Mi gyel csökkenti a méretet, majd visszatér bármi belsejében van, mert popping, szeretnénk hozzáférést bármilyen tárolják Az index a tetején a verem. Minden van értelme? Ha tettem srácok írom ezt ki, kíván srácok tudják, írja le? OK, maguk játszadozik vele. Nem gond, ha nem kap meg. Nincs ideje, hogy kódot ki még ma, mert már Van egy csomó ilyen szerkezetek hogy menjen át, de lényegében pszeudokódja, nagyon, nagyon hasonló, hogy álljon. Csak kövesse végig a logikát. Győződjön meg róla Ön által elérni az összes funkciók a struktúra megfelelően. Igen? 

Közönség: Will ezeket a diákat és ez az egész dolog akár ma-szerű? ANDI Peng: Mindig, aha. Megyek próbálja fel ezt fel, mint egy óra után. Én e-mailt Davidnek, David megpróbálja tedd fel, mint egy óra után. 

OK, így aztán beköltözik a másik szép adatstruktúra nevű sorban. Ahogy ti is látható, a sorban, a brit köztünk, Mindenek előtt ez egy sort. Tehát ellentétben azzal, amit Szerinted egy köteg, egy sort, hogy pontosan mit logikusan úgy gondolja, hogy ez. Ez birtokában szabályai FIFO, amely First In, First Out. Ha te vagy az első egy a sorban, akkor Az első, hogy jön ki a sor. 

Tehát mi szeretjük hívni ezt A dequeueing és enqueueing. Ha azt akarjuk, hogy adjunk valamit a mi sorban, mi sorba állítását. Ha azt akarjuk, hogy dequeue, vagy tegyen valamit el, mi dequeue. 

Így ugyanabban az értelemben, hogy mi vagyunk a fajta megteremtése fix méretű elemeket, hogy tárolhatja bizonyos dolgok, de mi is megváltoztatni, ahol mi vagyunk forgalomba paraméterek bennük alapján, hogy milyen típusú funkcionalitást szeretnénk. Szóval halom, azt akartuk az utolsó Egy, az N, hogy az első, aki ki. Várólista szeretnénk az első dolog, be az első dolgot. 

Így a struktúra-típus meghatározni, mint látható, ez egy kicsit más attól, amit a verem volt mert nem csak meg kell tartani követni, ahol a méret jelenleg, mi is szeretnénk nyomon követni a fej valamint, ahol jelenleg is. Tehát úgy gondolom, hogy könnyebb ha rajzolok ezt fel. Szóval képzeljük el mi van egy sorban, Mondjuk a feje itt van. A fej a vonal, hadd Csak azt mondják, hogy jelenleg, és szeretnénk beszúrni valamit a sorba. Én fogom hívni mérete lényegében ez ugyanaz, mint a farok, A végén, ahol a várólista van. Mondjuk úgy, hogy a méret itt. 

Szóval hogyan lehet ténylegesen helyezze valamit egy sorban? Mit index akarunk helyezni ahol szeretnénk szúrni. Ha ez az elején a sorba, és ez a vége vagy a mérete is, ahol mi is kívánja adni a következő objektumot? 

Közönség: [hallható] ANDI Peng: Pontosan, a felvenni kívánt hogy attól függően írtál meg. Vagy ez üres, vagy, hogy üres. Tehát a felvenni kívánt valószínűleg itt, mert ha a méret is-- ha ezek teljesen tele van, azt szeretnénk, hozzá, hogy jobb itt, ugye? 

És ez az, miközben nagyon, nagyon egyszerű, nem egészen mindig helyes mert a fő különbség között a sorba, és egy halom az, hogy a várólista is valójában manipulálható úgy, hogy a fej változások attól függően, hogy hol szeretné Az elején a végszó kezdeni. És ennek eredményeként, a farok is fog változni. És így vessen egy pillantást ezt a kódot most. Ahogy ti is megkérdezték, hogy írjon ki a kvízt, Enqueue. Talán majd átbeszéljük, hogy miért A válasz az volt, hogy mi az. 

Nem tudtam elég illik ez a vonal egyik, de alapvetően ez a kódrészletet legyen egy sorban. Költeni, mint 30 másodperc. Vessen egy pillantást, és miért ez a módja, hogy az. 

Nagyon, nagyon hasonló struktúra, nagyon, nagyon hasonló szerkezetű, mint az előző verem, kivéve talán egy sor kód. És, hogy egy sor kód meghatározza a funkcionalitást. És ez igazán megkülönbözteti sorban kéményből. 

Bárki, aki akar, hogy a stab elmagyarázása, miért voltál Van ez a bonyolult dolog itt? Látjuk a visszatérés a mi csodálatos barátom modulus. Mivel a srácok hamarosan felismerni a programozásban, szinte bármikor szükséged van valamire tekerje körül semmit, modulus lesz a módja annak, hogy csináld. Így tudta, hogy nem akarna bárki is kipróbálni kifejtve, hogy a kódsort? Igen, minden a válaszok elfogadott és üdvözlendő. Közönség: Te beszélsz velem? ANDI Peng: Igen. Közönség: Ó, nem sajnálom. ANDI Peng: OK, úgyhogy séta ezt a kódot. Tehát, ha akarsz adjunk valamit rá egy sorban, a gyönyörű esetben, ha a fej történik hogy igaza van, akkor nagyon könnyű számunkra hogy csak megy a végére helyezze valamit, nem? De a lényeg az egy sort hogy a fej ténylegesen dinamikusan változhat attól függően, hol vagyunk szeretné, hogy a kezdete a q lenni, és mint ilyen, a farok is fog változni. 

És így elképzelhető, hogy nem ez volt a sorba, hanem ez volt a sorban. Mondjuk a feje itt van. Mondjuk mi sorban így nézett ki. Ha akarnánk váltani, ahol az elején a vonal, mondjuk toltuk vezetője Ily módon és méretben itt. 

Most szeretnénk adni valamit ez a sorban, de ahogy ti is látni, ez nem olyan egyszerű, mint, hogy csak hozzá, amit az a méret után mert akkor elfogy a határait a tényleges tömb. Ahol szeretnénk igazán hozzá van itt. Ez a szépség egy sorban az, hogy nekünk, vizuálisan is néz ki, mint a vonal megy, mint ez, de amikor tárolt adatszerkezetet, Adnak, hogy úgy, mint egy ciklus. Ez a fajta körbe az elülső ugyanúgy hogy egy sort is csomagolja körül függően bárhova is szeretné a sor elején kell lennie. És így ha veszünk egy nézz le ide, hadd mondjuk akart létrehozni nevezett funkció Enqueue. Azt akartuk, hogy adjunk int n át, hogy q. Ha q.size q-- fogjuk hívni, hogy adatainkat structure-- ha a mi queue.size nem egyenlő kapacitása, vagy ha ez kevesebb, mint a kapacitás, q.strings a tömb a mi q. Fogunk beállítani hogy egyenlő q.heads, ami itt van, plusz q.size modulus a kapacitást, amely csavarja vissza minket errefelé. 

Tehát ebben a példában, index A fej 1, ugye? Az index a mérete 0, 1, 2, 3, 4. Így nem tehetünk 1 plusz 4 modulusa az a képességünk, amely 5. Mit jelent, hogy adjon nekünk? Mi az index, hogy jön ki ez? 

Közönség: 0. 

ANDI Peng: 0, ami előfordul, hogy éppen itt, és ezért szeretnénk, hogy képes beilleszteni itt. És így ez az egyenlet itt fajta csak működik minden szám attól függően, hol fej és a mérete is. Ha tudod, hogy mik azok dolgok, tudod, pontosan ott, ahol be szeretné szúrni bármit, ami után a sorban. Van ennek értelme mindenki? 

Tudom, milyen az agy teaser különösen azért, mert ez a jött a utóhatásaként a kvíz. De remélhetőleg mindenki Most megértem Ezért ez a megoldás, vagy ezt funkció a módon, hogy az. Bárki egy kicsit nem világos, hogy? OKÉ. 

És így most, ha akarta dequeue, ennek van, ahol a fej lenne váltás mert ha voltunk dequeue, nem vesszük le a végén a q. Azt akarjuk, hogy vegye le a fejét, nem igaz? Tehát ennek eredményeként, a fej nem fogja megváltoztatni, és ezért, ha sorba állítását, neked kell nyomon követni ahol a fej és a méretet vannak, hogy képes legyen beszúrni a megfelelő helyzetbe. 

És így ha dequeue, Én is pszeudókód ki. Nyugodtan ha azt szeretné, hogy megpróbálja kódolási ezt. Azt akarod, hogy mozog a feje, igaz? Ha akartam dequeue, én mozgatja feje fölött. Ez lenne a fejét. 

És a jelenlegi méret lenne kivonni, mert mi már nem Van négy elem a tömbben. Már csak három, majd azt akarjuk, vissza bármi is volt tárolt A fej, mert azt akarjuk, hogy ezt érték el, így nagyon hasonlít a verem. Csak szedi egy másik helyre, és van, hogy hozzárendelése mutatót a másik helyen eredményeként. Logikusan, mindenki követni? Nagy. 

OK, így fogunk beszélni egy kicsit mélyebben mintegy láncolt listák mert akkor nagyon, nagyon értékes Önnek során e heti psets. Láncolt listák, ahogy a srácok emlékszem, ezek csak a csomópontok, amelyek csomópontok bizonyos értékei mindkét érték és mutatóját hogy egymáshoz kapcsolódnak azok a mutatók. És így a struktúra hogyan létrehozunk egy node itt vagyunk van int n, amely bármilyen Az érték egy üzletben vagy string n vagy amit akarsz nevezni, a char csillagos n. Struct csomópont csillag, amely a mutató hogy azt szeretné, hogy az egyes csomópontok, fogsz is, hogy a pointer pont felé jövő. Itt van a feje Egy hivatkozott lista, amelyet fog mutatni a többi az értékeket így tovább és így tovább amíg meg végül elérjük a végét. És ez az utolsó csomópont csak megy, hogy nem egy mutatót. Meg fog mutatni null, és ez az, amikor tudod, hogy elérje a végén a láncolt lista az, amikor az utolsó mutatót nem mutat sehova. 

Így fogunk menni egy kicsit többet mélysége tekintetében hogyan feltehetően Keressen egy láncolt lista. Ne feledje, mik a Hátránya az láncolt listák verseket tömb kapcsolatos keresések. Egy tömb tudsz bináris keresés, de miért nem tudsz csinálni, hogy egy láncolt lista? 

Közönség: Mert ők az összes csatlakoztatott, de nem igazán tudom, hol [NEM HALLHATÓ]. 

ANDI Peng: Igen, pontosan úgy emlékszem, hogy a fényessége tömb volt az a tény, hogy mi volt véletlen hozzáférésű memória, ahol ha akartam az érték indexe hat, tudtam csak mondani index hat, adj ez az érték. És ez azért van, mert tömbök vannak sorolva, egy összefüggő tér memória egy helyen, míg fajta láncolt listák a véletlenszerűen tarkított körül, és az egyetlen módja van az ország egyik van egy mutatót, amely megmondja, A címe, ha ez a következő csomópont. 

És így ennek eredményeként, az egyetlen módja keresgélni egy láncolt lista lineáris keresést. Mert én nem tudom pontosan, hol A 12. értéke a kapcsolódó lista, Én áthalad a teljes e kapcsolt lista egyik egy a fejét az első csomóponthoz, a második csomóponthoz, hogy a harmadik csomópont, egészen addig, amíg végül kap hogy ha ez a csomópont keresem az. És így ebben az értelemben, keresés egy láncolt lista mindig n. Mindig n. Ez mindig lineáris időben. 

Ezért a kód, amelyben mi végre ezt, és ezt a egy kicsit az új srácok, mióta srácok még nem igazán beszéltünk, vagy soha láttam a mutatókat, hogy hogyan keresgélni mutatók, így megyünk végig ez nagyon, nagyon lassan. Szóval bool kereső, igaz, képzeljük el akarunk hogy hozzon létre olyan függvény is kereső, amely igazat ad vissza Ha találtál egy értéket belül a kapcsolt listára, és hamis értékkel tér vissza másként. Node csillagos lista Jelenleg csak a mutató Az első elem a láncolt lista. int n az az érték, hogy te keresnek fel a listára. 

Tehát csomópont csillagos mutató értéke listát. Ez azt jelenti, hogy az aktuális állítást és megteremti a mutatót ebben az első csomópont belsejében a lista. Mindenki velem? Tehát, ha mennénk vissza ide, szerettem volna inicializált egy mutatót, amely arra utal, hogy a feje, amit ez a lista. 

És majd ha egyszer gyere le, míg a mutató nem egyenlő null, úgy, hogy az a hurok, amelyben vagyunk lesz a későbbiekben áthaladó A többi a mi lista, mert mi történik, amikor a mutató értéke null? Tudjuk, hogy have-- 

Közönség: [hallható] 

ANDI Peng: Pontosan, tehát tudjuk, hogy elértük a lista végére, ugye? Ha megy vissza, minden csomópont kell néznie egy másik csomópont és így tovább, és így tovább amíg eléred végül A farok a láncolt lista, amely egy mutatót, hogy csak nem pont máshol, mint nem. És így alapvetően tudjuk, hogy A lista még mindig ott fel amíg a mutató nem egyenlő null, mert ha egyszer eléri null, Tudja, hogy nincs több cuccot. 

Tehát ez a hurok, amelyben vagyunk megy, hogy a tényleges keresést. És ha a pointer-- látod ez a fajta nyíl funkciója van? Tehát, ha mutató n, ha A mutató a n összege egyenlő n, így ez azt jelenti, hogy ha A mutató, hogy te keresi a végén minden csomópont valójában értékével egyenlő keres, akkor vissza akar térni igaz. Tehát alapvetően, ha egy csomópont, az értéke, amit keres, tudod, hogy te voltál Sikeresen keresni. 

Ellenkező esetben, ha szeretné beállítani A mutató a következő csomópontot. Ez az, amit a vonal itt csinál. Pointer egyenlő melletti mutatóra. Mindenki látni, hogy hogyan működik? 

És lényegében fogsz most áthalad a teljes a lista, újraindítani a mutatót minden alkalommal, amíg akkor végül csúnyán a lista végén. És tudod, hogy nincs több csomópont keresgélni, és akkor return false mert tudja, hogy, jaj, nos, Ha képes voltam keresni keresztül a teljes egészében a lista. Ha ebben a példában, ha akarnám hogy keresse meg a 10-es érték, és elkezdem a fejét, és Én keresni egészen, és én végül kapott erre, ami egy mutatót, amely arra utal, hogy null, Tudom, hogy szar, azt hiszem, 10 nem ez a lista, mert nem tudtam megtalálni. És én vagyok az a lista végén. És ebben az esetben tudja Megyek vissza hamis. 

Legyen ez hatni egy kicsit. Ez lesz elég fontos a PSET. A logika nagyon egyszerű, talán mondattanilag csak végrehajtásában. Kértek, hogy arról, hogy érti. Hűvös. 

OK, akkor hogyan lennénk behelyezése csomópontok, igaz, egy listát, mert emlékszem mi a mi a haszon Az rendelkező kapcsolt lista versus tömb a tárolás szempontjából? 

Közönség: Ez a dinamikus, így könnyebb az alábbiakra: 

ANDI Peng: Pontosan, így ez a dinamikus, amelyek azt jelenti, hogy bővítse és összezsugorodik attól függően, hogy a felhasználó igényeinek. És így, ebben az értelemben, hogy nem kell pazarolni felesleges emlék, mert ha nem tudom, hány érték akarok a boltba, akkor nincs értelme számomra hogy hozzon létre egy tömböt, mert ha azt akarom, hogy tárolja 10 értékek és én létrehozunk egy tömböt 1000, ez a sok elvesztegetett memória, kiosztott. Ezért szeretnénk, ha készítesz egy lista, hogy képes legyen a dinamikusan megváltoztatni, vagy csökken a mérete. 

És így teszi beillesztés egy kicsit bonyolultabb. Mivel nem tudjuk véletlenszerűen hozzáférés elemei az is, hogy mi lenne a tömb. Ha azt szeretnénk, hogy helyezzen be egy elemet a hetedik index, Egyszerűen helyezze a hetedik index. Egy láncolt lista, ez nem egészen működik olyan könnyen, és így ha azt akartuk, hogy helyezze Az egyik itt, a láncolt lista, vizuálisan, ez nagyon könnyen látható. Csak azt akarjuk, hogy helyezze ott, jobb elején a listán, után a fejét. 

De milyen módon van átminősítése A mutatók egy kicsit nyakatekert vagy, logikusan, akkor van értelme, de azt szeretnénk, hogy győződjön meg arról, hogy van ez Teljesen le, mert Az utolsó dolog, amit szeretnénk, az, hogy hozzárendelése egy mutatót a hogy itt csinálunk. Ha dereference a pointer tetőtől 1, majd hirtelen a többi a láncolt lista elvész, mert mi még nem próbáltuk létrehozott egy ideiglenes semmit. Ez az, rámutatott, hogy a 2. Ha hozzárendeli a mutatót, majd a többi a lista teljesen elveszett. Szóval azt szeretné, hogy Nagyon, nagyon vigyáznunk az első rendelheti pointer, amit akar szúrni bárhova akarsz, és akkor lehet követéssel, a többi a lista. 

Tehát ez vonatkozik bárhova akarsz szúrni. Ha azt szeretnénk, hogy helyezze át a fejét, ha azt szeretné, hogy válaszoljon itt, Ha azt szeretnénk, hogy helyezze át A végén, nos, a végén én hiszem, akkor csak nincs mutató, de szeretnénk, hogy győződjön meg arról, hogy nem elveszíti a többi a lista. Mindig akarja, hogy megbizonyosodjon arról Az új csomópont mutat felé, amit akar szúrni, majd felveheti a láncolás tovább. Mindenki tiszta? 

Ez lesz az egyik az igazi kérdés. Az egyik legfontosabb kérdések fogsz van a PSET az, hogy meg fogsz megpróbál létrehozni A láncolt lista és betét dolgokat de aztán csak elveszti az többi a láncolt lista. És te leszel, mint én Nem tudom, miért történik mindez? És ez a fájdalom, hogy menjen át és keresni az összes mutató. 

És garantálom, hogy ezen PSET, írás és rajz ezek a csomópontok ki lesz nagyon, nagyon hasznos. Szóval akkor teljesen nyomon követni Az, ahol minden a pointerek, mi baj, ahol minden csomópont, mit kell tennie, hogy elérje vagy beszúrni vagy törölni, vagy ezek közül bármelyik. Mindenki jó ebben? Hűvös. 

Tehát ha azt akartuk, hogy nézd meg a kódot? Ó, nem tudom, ha Láthatjuk the-- OK, így a tetején is ez egy olyan funkció, elemzi betét, ahol szeretnénk beszúrni int n a láncolt lista. Fogunk séta ezt. Ez egy csomó kódot, sok új szintaxis. Mi minden rendben lesz. 

Szóval fel a tetején, amikor akarunk létrehozni semmit Mit kell tennünk, különösen akkor, ha akarjuk, hogy ne a veremben tárolt de a kupac? Elmegyünk egy malloc, ugye? Mi is így fogjuk létrehozni egy mutató. Node, mutató, új egyenlők malloc a mérete egy csomópont mert azt szeretnénk, hogy létrehozandó csomóponttal. Szeretnénk, ha az összeg memória hogy egy csomópont vesz fel felosztható a létrehozására az új csomópont. 

És akkor mi lesz, hogy ellenőrizze, hogy hátha új egyenlők egyenlő null. Emlékszel, mit mondtunk? Bármit malloc, Mit kell mindig csinálni? Mindig ellenőrizni kell, hogy e vagy sem, hogy null. 

Például, ha az operációs rendszer teljesen megtelt, ha nem volt több memóriát minden, és megpróbálja malloc, lenne visszatérni null az Ön számára. És így ha megpróbál használni amikor mutató null, ugye nem fog tudni hozzáférni az információkhoz. És így mint ilyen, azt akarta, hogy arról, hogy ha te mallocing, te mindig ellenőrzi, hogy ha hogy a memória adott neked null. És ha nem, akkor meg tudjuk mozgatni tovább a többi a mi kódot. 

Szóval megyünk inicializálja az új csomópont. Fogunk csinálni új n összege n. És akkor fogunk csinálni meg az új a mutatót az új null, mert most nem tesszük akar semmit érte, hogy pont. Fogalmunk sincs, hol ez fog téged, majd ha azt akarjuk, hogy illessze be a fejét, akkor tudjuk hozzárendelése A mutatót a fejét. Mindenkinek logikáját követik hol, ami történik? 

Minden csinálunk teremt egy új csomópont, amelyben a mutató értéke NULL, majd átcsoportosítása azt, hogy a fej, ha tudni akarjuk illessze be a fejét. És akkor a fej fog pont felé, hogy az új csomópont. Mindenki rendben van ezzel? 

Tehát ez egy kétlépcsős folyamat. Megvan az első hozzárendelése Bármit létre. Állítsa hogy a mutató a hivatkozás, és akkor lehet ilyen hivatkozás feloldási Az első mutató és pont ez iránt az új csomópont. Ahol szeretné, hogy helyezze, E logika fog tartani igaz. 

Ez olyan, mint hozzárendelése ideiglenes változók. Ne feledje, ha már van hogy megbizonyosodjon arról, hogy Nem veszítjük el, ha csere. Azt akarod, hogy megbizonyosodjon arról, hogy van egy ideiglenes változó, hogy milyen tart követni, ahol a dolog van tárolva úgy, hogy ne vesszenek el érték során hasonló szórakozni vele. 

OK, így kódot itt lesz. Srácok, nézzen szakasz után. Ott lesz. 

Szóval azt hiszem, hogyan működik ez különböznek ha akarnánk szúrni a közepén vagy végén? Van valakinek ötlete, hogy mi a pszeudokódja, mint a logikai referencia hogy mi lenne, hogy ha akarnánk hogy helyezze a közepén? Tehát ha azt akartuk, hogy illessze be a fejét, csak annyit teszünk, hozzon létre egy új csomópontot. Mi meg a mutatót az, hogy új csomópont bármilyen fejét, majd elindultunk a fejét Az új csomópont, ugye? Ha akartuk, hogy helyezze a közepén A lista, hogy mi kell tennünk? 

Közönség: ez még mindig lehet egy hasonló folyamat A oszt ki például a mutató és a ezt rendelve, hogy a mutató, de mi lett volna, hogy keresse meg ott. 

ANDI Peng: Pontosan, tehát pontosan ugyanez a folyamat csak akkor hogy keresse meg, pontosan hogy szeretnénk, hogy az új mutató bemenni, így ha akar szúrni közepén kapcsolódik list-- OK, Tegyük fel, hogy a mi láncolt lista. Ha azt akarjuk, hogy beillessze azt itt, fogunk létrehozni egy új csomópontot. Megyünk malloc. Megyünk, hogy hozzon létre egy új csomópont. Megyünk rendelheti pointer e csomópont van. 

De a probléma, amely különbözik ahonnan a fej az, hogy pontosan tudtuk, ahol a fej. Helyes volt az első, ugye? De itt megvan, hogy nyomon követhesse hol vagyunk, ha behelyezi. Ha behelyezésekor a node itt, nálunk hogy győződjön meg arról, hogy a Egy korábbi ehhez a csomóponthoz az egyik, hogy ismét kiosztja a mutatót. Szóval akkor meg kell egyfajta nyomon követheti a két dolgot. Ha nyomon követni, ahol ezt csomópont jelenleg be van vezetve. Azt is meg kell nyomon követni, ahol Az előző csomópont, amely nézel is ott volt. Mindenki jó ebben? OKÉ. 

Hogyan behelyezésével a végén? Ha akartam felvenni here-- ha akarnék hogy egy új csomópont a végén egy listát, hogyan lehet azt járni csinálja? Közönség: Tehát jelenleg a Utolsó ember mutatott null. ANDI Peng: Igen. Pontosan, így ez az egyik Jelenleg is rámutatott, hogy tudja, és így azt hiszem, ebben az értelemben, hogy Nagyon könnyű hozzáadni, hogy a végén egy listát. Mindössze annyit kell tennie, hogy állítsa egyenlő null majd bumm. Pont ott, nagyon könnyű. Nagyon egyszerű. 

Nagyon hasonló a fejét, de logikailag akkor szeretnénk, hogy győződjön meg arról, hogy a lépések veszel cél megvalósítása sem ezt, te követi végig. Ez nagyon könnyű, a közepén a kód, akad fenn, ó, kaptam sok tanácsot. Nem tudom, hol bármit mutat. Azt sem tudom, melyik csomópont vagyok. Mi történik? 

Pihenjen, nyugodj meg, vegyél egy mély lélegzetet. Felhívni arra a láncolt lista. Ha azt mondod, tudom, hogy pontosan hol Azt kell helyeznie ezt figyelembe és pontosan tudom, hogyan kell átminősítése én mutatók, sokkal, de sokkal könnyebb elképzelni out-- sokkal, de sokkal könnyebb és nem eltévedni a hibákat a kódot. Mindenki rendben van ezzel? OKÉ. 

Szóval azt hiszem, a koncepció, hogy mi nem Tényleg beszélt előtt most, és azt hiszem, akkor valószínűleg nem fog találkozni sok yet-- ez a fajta fejlett concept-- az, hogy mi valóban van egy adat szerkezet az úgynevezett kétszeresen láncolt lista. Tehát ahogy ti is látni, minden, amit csinálunk létrehozása a tényleges érték, egy extra mutatót minden a mi csomópontok hogy arra is rámutat, hogy az előző csomópont. Tehát nem csak mi van a csomópontok pont a következő alkalommal. Arra is rámutatnak, hogy az előzőt. Megyek figyelmen kívül hagyni ezt a két most. 

Tehát akkor van egy lánc hogy lehet mozgatni mindkét irányban, és akkor ez egy kicsit könnyebb hogy logikusan kövesse végig. Mint itt, ahelyett, követi nyomon a, ó, Tudnunk kell, hogy ez a csomópont Az egyik, hogy azt kell átminősítése, Én is csak megy itt, és csak húzza az előző. Akkor tudom, hogy hol azaz, és akkor Nem kell, hogy áthalad a teljes egészében a láncolt lista. Ez egy kicsit könnyebb. 

De mint ilyen, akkor kétszeresen is az összeg a mutatók, ez duplája a memóriát. Ez egy csomó mutatók nyomon követni. Ez egy kicsit bonyolultabb, de ez egy kicsit felhasználóbarátabb függően hogy mit akarsz elérni. 

Tehát ilyen típusú adatok struktúra teljesen létezik, és a struktúra nagyon, nagyon egyszerű kivéve az összes Ön rendelkezik az, ahelyett, hogy csak egy mutató a következő, Önnek is van egy mutató az előző. Ez minden volt a különbség. Mindenki jó ebben? Hűvös. 

Rendben, akkor most én vagyok hogy valóban költeni valószínűleg mint a 15-től 20 percig, vagy az ömlesztett a fennmaradó időben szakaszban beszélünk hash táblák. Hányan vagytok srácok Elolvastam pset5 spec? Rendben, jó. Ez magasabb, mint a 50% -a általában. Oké. 

Tehát ahogy a srácok fogják látni, Ön kihívás pset5 lesz, hogy végre egy szótár ahol betöltöd több mint 140.000 szó hogy adunk és helyesírás-ellenőrzés ez ellen a szöveg. Adunk véletlenszerű szépirodalmi műveket. Adunk az Odüsszeia. Adunk az Iliász. Adunk Austin Powers. 

És a kihívás az lesz, hogy helyesírás-ellenőrző minden egyes szót minden e szótárak lényegében a mi helyesírás-ellenőrző. És így van egy pár alkatrészt létrehozzák az említett PSET, első akar lenni valóban képes betölteni minden szavakat a szótár, és akkor akarjuk, hogy képes legyen helyesírás-ellenőrzés mindet. És így mint ilyen, akkor lesz szükség adatszerkezetet, hogy képes erre gyorsan és hatékonyan és dinamikusan. 

Szóval azt hiszem, a legegyszerűbb módja ennek, akkor Valószínűleg létrehozunk egy tömböt, ugye? A legegyszerűbb módja a tárolás te létrehozhat egy sor 140.000 szó és csak helyezze őket oda, és ezután keresztülmegy őket bináris keresés vagy választás vagy nem-- Sajnálom, hogy ez a válogatás. Tudod rendezni őket, majd áthalad őket a bináris keresés, vagy csak lineáris keresés és csak végső szava, de ez vesz egy hatalmas mennyiségű memória, és ez nem túl hatékony. 

És így fogunk kezdeni beszélünk módon teszi a futási idő hatékonyabb. És a célunk az, hogy konstans időben, amikor ez majdnem olyan, mint tömbök, ahol Ön azonnali hozzáférést. Ha akartam keresni valamit, Azt akarom, hogy képes legyen igazságos, boom, meg pontosan, és húzza ki. És így egy olyan struktúra, amelyben fogunk egyre nagyon közel hogy képes legyen hozzáférni konstans idő, ez a szent grál A programozásban állandó alkalommal hívják hash tábla. És így David korábban említettük [Hallhatatlan] egy kicsit az előadás, de mi lesz igazán merülés mélyen a héten egy darab, ami kapcsolatban hogy egy hash tábla működik. 

Tehát az is, hogy a hash táblázat munkák, például, ha akartam, hogy tárolja egy csomó szó, a csomó szó az angol nyelv, Én elméletileg fel banán, alma, kiwi, mangó, pár, és sárgadinnye mind csak egy tömbben. Tudtak fér bele, és lehet találni. Jó lenne egyfajta fájdalom, hogy keresgélni és a hozzáférés, de az egyszerűbb módja, ez hogy mi is létrehozhatunk valójában egy struktúra úgynevezett hash tábla, ahol hash. Futunk minden kedves gombok segítségével hash függvény, egy egyenletet, amely bekapcsolja őket mind valamiféle értéket hogy akkor tudjuk tárolni rá Lényegében egy sor láncolt lista. 

És így van, ha akarnánk tárolni angol szavak, tudnánk esetleg csak, én nem tudom, viszont minden az első betű valamiféle egy számot. És így, például, ha akartam Egy, hogy egyet apple-- vagy az index 0, és B, hogy egyet 1, mi lehet 26 bejegyzés amely csak tárolja minden betűjét a ábécét, hogy kezdjük. És akkor mi lehet Az Apple a indexe 0. Mi lehet a banán, a indexe 1, sárgadinnye meg az index a 2, és így tovább, és így tovább. És így ha akartam keresni én hash tábla és a hozzáférés alma, Tudom, alma kezdődik egy A, és pontosan tudom, hogy kell, és a hash asztal index 0, mert A korábban kijelölt funkciót. 

Szóval nem tudom, mi felhasználói program, ahol akkor terhelhetik arbitrarily-- nem önkényesen, A próbál elgondolkodva gondolom jó egyenletek hogy képes terjedni ki az összes értékek oly módon, egyszerűen érhetőek el hogy a későbbiekben a hasonló egyenlet hogy te magad tudod. Tehát abban az értelemben, ha akartam menni mangó, tudom, ó, azzal kezdődik, m. Meg kell lennie az index a 12. Nem kell keresni semmit. Tudom exactly-- tudnék menni Az index 12 és húzza, hogy ki. 

Mindenki tisztában, hogy egy hash tábla funkció? Elég csak egy bonyolultabb tömb. Ez minden van. OKÉ. 

Szóval azt hiszem, befut ezt a kérdést, hogy mi előfordul, ha több dolgot hogy megadja ugyanazt index? Tehát mondjuk a függvényt, mindent meg az volt, hogy az első levél és viszont, hogy egy megfelelő 0 és 25 index. Ezt teljesen rendben van, ha már csak egy minden. De a második indításakor hogy több, maga megy, hogy az úgynevezett ütközés. 

Szóval, ha megpróbál beilleszteni temetni egy hash táblázatot, amely már a banán rajta, mi fog történni, ha megpróbál beilleszteni ezt? Rossz dolgok, mert a banán Már létezik az index kívánt tárolja. Berry fajta, mint, ah, mit tegyek? Nem tudom, hová menjen. Hogyan tudom megoldani ezt? 

És így a srácok a fajta lásd ezt tesszük trükkös dolog ahol tudunk ilyen ténylegesen hozzon létre láncolt lista a mi tömböket. És így a legegyszerűbb módja ezen gondolkodni, Az összes hash tábla egy tömb láncolt listák. És így, ebben az értelemben, hogy van ez a gyönyörű tömb mutató, majd minden mutatót ezt az értéket, az adott index, valójában pont az más dolog. És így van mindezen külön láncok jön ki egy nagy tömb. 

És így van, ha én akarta szúrni bogyó, Tudom, OK, megyek bemenet ez az én hash függvény. Megyek, hogy a végén az index 1, majd fogok tudni kell Csak egy kisebb részét ennek óriás 140.000 szavas szótárban. És akkor tudok csak nézz keresztül 1/26 e. 

És így akkor tudok csak helyezze bogyó előtt vagy után banán ebben az esetben? Miután, ugye? És így fogsz akar helyezze a csomópont után banán, és így fogsz szúrni a farka, hogy láncolt lista. Én megyek vissza ehhez előző diára Szóval ti láthatod, hogy hash függvény működik. 

Tehát hash függvény ennek az egyenletnek hogy futsz fajta a bemeneti keresztül kap bármilyen index hozzárendelni kívánt felé. És így, ebben a példában az összes akartunk tennem, hogy tegye meg az első levelet, viszont, hogy egy indexet, akkor tárolhatja, hogy a hasító függvény. Minden csinálunk itt vagyunk konvertáló az első levél. Tehát KeyKey [0] csak az első betű bármilyen karakterlánc vagyunk, amelynek, mi halad. Mi konvertáló, hogy a felső és mi levonjuk a nagybetűs Egy, így minden, ami csinál ad nekünk egy számot ahol tudunk hash értékeinket rá. 

És akkor mi lesz visszatérni hash modulus SIZE. Legyen nagyon, nagyon óvatos mert, elméletileg, ide A hash érték lehet végtelen. Lehet, hogy csak megy tovább és tovább és tovább. Ez lehet néhány igazán, Nagyon nagy érték, hanem azért, mert a hash tábla Ön erről csak 26 indexek, azt szeretnénk, hogy győződjön meg róla, modulusing úgy, hogy Nem run-- ez ugyanaz dolog, mint a queue-- úgy, hogy ne fogyjon ki a alján a hash függvény. 

Azt akarod, hogy csavarja vissza mintegy azonos módon [hallható], amikor Önnek volt, mint egy nagyon, nagyon nagy levelet, akkor Nem akartam, hogy a csak fuss ki a végét. Ugyanezt itt, azt szeretnénk, hogy győződjön meg arról, nem fut le a végén a csomagolás körül, hogy a táblázat tetején. Tehát ez csak egy nagyon egyszerű hash függvény. Minden, ami az volt, hogy az első levelében, amit mi bemeneti volt és kapcsolja be, hogy egy index, tudtuk helyezni a hash tábla. 

Ja, és így mint már mondtam, az is, hogy elhatározzuk ütközések a hasító táblák vannak, hívjuk, láncolt. Tehát, ha megpróbál beilleszteni több szóval kezdődő ugyanaz a dolog, fogsz egy hash értéket. Az avokádó és alma, ha már futtassuk át a hash függvény, fog adni a ugyanazt a számot, a szám a 0. És így, ahogy mi megoldani, hogy az hogy mi is valójában milyen összekapcsolják őket okon láncolt listák. 

És így ebben az értelemben, srácok láthatjuk a fajta hogyan adatszerkezetekről mi már korábban beállítása mint egy mazsola láncolt lista természetbeni Az jöhet össze egy. És akkor hozhat létre messze hatékonyabb adatszerkezetek amely képes kezelni nagyobb mennyiségű adatokat, amelyek dinamikusan átméretezni függően hogy az Ön igényeinek. Mindenki tiszta? Mindenki fajta tiszta mi történik itt? 

Ha akartam insert-- mi egy gyümölcsöt, hogy kezdődik, nem tudom, B, kivéve bogyó, banán. 

Közönség: Blackberry. 

ANDI Peng: Blackberry, szeder. Hol szeder megy itt? Nos, valójában nem rendezve ez még, de elméletileg ha azt akartuk, hogy ezt ábécésorrendben, hol kellene szeder menni? 

Közönség: [hallható] 

ANDI Peng: Pontosan, miután itt, ugye? De mivel ez nagyon nehéz reorder-- Azt hiszem, ez akár srácok. Srácok lehet teljesen végrehajtja, amit akarsz. A hatékonyabb módszer Az ezt talán lenne rendezni a kapcsolt sorolja be, betűrendben és így, ha éppen behelyezése a dolgokat, azt szeretnénk, hogy biztos, hogy be őket betűrendbe így aztán, ha éppen próbál keresni őket, Önnek nem kell bejárására mindent. Pontosan tudod, hol ez, és akkor könnyebb. 

De ha ilyen van, dolgokat tarkított véletlenszerűen, még mindig megy, hogy bejárására is egyébként. És így ha akartam csak helyezze szeder itt és szerettem volna keresni ez, tudom, ó, szeder kell kezdeni az index az 1, úgyhogy tudni azonnal, csak keresni 1. És akkor én is egyfajta keresztezik a láncolt lista amíg nem kap a BlackBerry, és then-- igen? 

Közönség: Ha akarsz create-- Azt hiszem, ez egy nagyon egyszerű hash funkció. És ha azt akartuk csinálni több réteg, amely, mint, OK, azt akarjuk, hogy szét lehessen választani mint az összes abc betűk majd ismét szeretnék egy másik alfabetikus betűk belül, vagyunk üzembe, mint egy hash asztal belül hash tábla, vagy mint egy programon belül egy funkciót? Vagy hogy-- 

ANDI Peng: Szóval a hash function-- a hash tábla lehet olyan nagy, mint azt akarja, hogy. Tehát ebben az értelemben, azt hittem, nagyon könnyű volt, nagyon egyszerű számomra, hogy csak egyfajta alapján A leveleket az első szó. És így már csak 26 lehetőségeket. Csak azt tudom, hogy 26 opciókat 0-25 hiszen csak kezdeni tól Z-ig, de ha akarod hozzá, talán még összetettsége vagy gyorsabb futás közben a hash tábla, amit feltétlenül tehetünk mindenféle dolgot. Tudod, hogy a saját egyenletet, hogy megadja neked Több elosztó a szavakat, majd amikor keresni, ez lesz gyorsabb. 

Ez teljesen rajtad múlik srácok hogyan szeretné megvalósítani ezt. Gondold azt, hogy csak vödrök. Ha azt akartam, hogy 26 vödrök, megyek rendezni a dolgokat abba a vödörben. De megyek van egy rakás A cucc minden vödör, ezért ha azt szeretnénk, hogy győződjön meg gyorsabb és hatékonyabb, hadd száz vödör. 

De akkor meg kell kitalálni a milyen módon rendezi a dolgokat, hogy azok a megfelelő vödör kellene lennie. De akkor, ha valóban szeretné nézni, hogy vödröt, ez sokkal gyorsabb, mert van kevesebb cucc minden vödör. És igen, igen, ez valóban A trükk az Ön srácok pset5 az, hogy te leszel vitatta, hogy csak teremt függetlenül a leghatékonyabb funkcióval lehet gondolni, hogy képes tárolni, és ellenőrizze ezeket az értékeket. 

Teljesen fel srácok ahogy akarod csinálni, de ez egy nagyon jó pont. Hogy a fajta logika akkor szeretnénk kezdeni gondolkodni van, nos, miért nem érzem, hogy több vödör. És akkor azt kell keresni kevesebb dolgokat, és akkor talán Van egy másik hash függvény. 

Igen, van egy csomó módon, hogy ezt PSET, néhány gyorsabb, mint mások. Én teljesen fog éppen milyen gyors volt a leggyorsabb srácok lesz tudja, hogy a funkciók dolgozni. OK, mindenki jó láncolás és hash táblák? Ez valójában, mint egy nagyon egyszerű fogalmát, ha belegondolsz. Minden ez az elválasztó bármi A bemenetek gyűjtőzónákba, válogatás őket, majd keresni a felsorolja, hogy van társítva. 

Hűvös. Rendben, most van egy másik fajta Az adatok szerkezete, hogy hívják a fa. Menjünk tovább és beszélni próbál amelyek határozottan eltérő, de ugyanabban a kategóriában. Lényegében minden a fa helyett A szervező adatok a lineárisan hogy a hash tábla does-- Önnek Tudja, hogy van egy felső és egy alsó és akkor milyen hivatkoznak le it-- egy fa egy felső, amely hívja a gyökér, és akkor van levelek minden körülötte. 

És így minden, ami itt csak a legfelső csomópont hogy pont más csomópontok, hogy pont hogy több csomópont, és így tovább, és így tovább. És így csak ki hasító ágak. Ez csak egy másik módja a szervező adatok, és mert ez egy fa, srácok csak-- ez csak modellezett ki néz ki, mint egy fa. Ezért nevezzük ezt fák. 

Hash tábla úgy néz ki, mint egy asztal. A fa csak úgy néz ki, mint egy fa. Minden ez egy külön szervezési módja csomópontok attól függően, hogy milyen igényei. 

Szóval van egy gyökér és akkor már a levelek. Az így tudjuk különösen belegondolsz egy bináris fa, egy bináris fa csak egy bizonyos típusú fát ahol minden csomópont csak pont a, max, két másik csomópont. És így itt van külön szimmetria a fán hogy megkönnyíti a fajta néz hogy milyen értékek vagytok, mert akkor mindig a bal vagy jobbra. Soha nincs, mint egy bal harmadával A bal vagy egy negyedik balról. Csak van egy jobb és bal és kereshetünk akár az említett kettő. És így ez miért hasznos? Az út, hogy ez hasznos az, ha keres keresgélni értékek, ugye? Ahelyett végrehajtási bináris Keressen egy hiba tömb, ha akarod, hogy tudja beszúrni csomópontok és elvenni a csomópontok lesz, és azt is megőrizni a keresési kapacitásainak bináris keresés. Tehát így vagyunk a fajta tricking-- emlékszem, amikor említett kapcsolt listák nem bináris keresés? Mi vagyunk a fajta létre egy adatstruktúra hogy trükkök, hogy a munka. 

És így, mert láncolt listák lineáris, ők csak hivatkozó egyik a másik után. Mi lehet ilyen van másfajta mutatók Ezen a ponton a különböző csomópontok amely segíthet a keresésben. És így van, ha akartam Van egy bináris kereső fa, Tudom, hogy a középső, ha 55. Én csak létre fog hozni, hogy mint az én közepén, mint az én gyökér, és akkor én megyek is értékeket spin off belőle. 

Tehát itt, ha fogom keresni értékének 66, kezdhetem 55. Ez 66 több mint 55? Igen ez, így tudom, hogy a MUS keresni i n jobb mutatót ennek a fának. Megyek 77. OK, 66-nél kisebb vagy nagyobb, mint a 77? Ez kevesebb, mint, hogy tudd, ó, hogy kell lennie a bal csomópont. 

És így itt vagyunk a fajta megőrzése Minden nagy dolog tömbök, így, mint a dinamikus átméretezés tárgyak, hogy tudja beszúrni és törölni az akarat, anélkül, hogy aggódnia a rögzített mennyiségű helyet. Még mindig megőrizze az összes ezek a csodálatos dolgokat míg a szintén képes megőrizni a jelentkezzen, és keressen ideje bináris keresés hogy mi volt korábban csak tudja, hogy egy mondatot. 

Cool adatok szerkezete, egyfajta megvalósításuk, a csomópont. Mint látható, minden tőle a struktúra a csomópont az, hogy van egy bal és a jobb mutatót. Ez minden van. Tehát ahelyett, hogy csak amelynek x vagy korábbi. Van egy bal vagy jobb oldali, majd akkor milyen összekapcsolja őket azonban úgy döntenek. 

OK, mi történt valójában Csak egy pár percig. Így fogunk visszamenni itt. Ahogy korábban mondtam, Valahogy magyarázható a logikája, hogy hogyan lenne végig ezt. Fogunk próbálni pseudocoding ezt ki, hogy ha tudjuk milyen alkalmazni a Ugyanez a logika a bináris keresés egy másik típusú adat struktúrát. Ha akartok venni, mint egy pár perc, hogy csak gondol erről. OKÉ. Rendben, megyek valójában csak kapsz the-- nem, fogunk beszélni a pszeudokódja először. Tehát nem mindenki szeretné, hogy a stab a mi Az első dolog, amit akarok, amikor kezded el keresés? Ha keresünk értékének 66, mi Az első dolog, amit akarok, ha azt akarjuk, hogy a bináris keresés ezt a fát? 

Közönség: Azt akarod, hogy néz ki jól és nézd bal és látni [hallhatatlan] nagyobb számot. 

ANDI Peng: Igen, pontosan. Szóval nézzük át a root. Van sok módon lehet hívni ez, a szülő csomópont az emberek mondanak. Azt szoktam mondani, gyökér, mert ez olyan, mint a gyökér a fa. Fogsz nézni a gyökér csomópontot, és te fog látni a 66 nagyobb kisebb vagy kevesebb mint 55. És ha ez nagyobb, mint, nos, ez nél nagyobb, hol akarunk nézni? Hol akarunk keresni, igaz? Azt akarjuk, hogy keressen a jobb fele ezt a fát. 

Tehát van, kényelmesen, egy a mutató, mely arra utal, hogy a jobb oldalon. És akkor tudjuk meg Az új gyökér, hogy 77. Mi is csak menni bárhova A mutató mutat. Nos, ó, itt kezdünk 77, és mi csak Ehhez rekurzív újra és újra. Ily módon, akkor milyen A funkciója van. Van egy módja a keresést, hogy egyszerűen csak ismételni újra és újra és újra, attól függően, hogy hol szeretné nézni amíg meg előbb-utóbb eljut arra az értékre hogy maga keresett. Van értelme? 

Én azon vagyok, hogy mutassa meg a tényleges kódot, és ez sok kód. Nem kell kiborulni. Beszélni fogunk rajta. 

Igazából nem. Ez csak pszeudokódja. OK, ez csak a pszeudokódja, ami egy kicsit komplex, de ez teljesen rendben van. Mindenki a következő mentén itt? Ha a gyökér null, cserébe hamis, mert azt jelenti akkor nem is kell semmit ott. 

Ha a root n az érték, így ha ez előfordul, hogy az egyik nézel, akkor fogsz visszatérni igaz mert tudod, hogy megtaláltad. De ha az érték kisebb, a root-n, akkor fog keresni a bal gyermek vagy a bal levél, amit csak akarsz nevezni. És ha az érték nagyobb, mint gyökér, fogsz keresni a megfelelő fát, akkor csak futtassa a funkciót a keresési újra. 

És ha gyökér null, hogy ez a azt jelenti, hogy elérte a végén? Ez azt jelenti, hogy nincs tovább tovább levelek keresni, akkor tudod, ó, Szerintem ez nem ide mert miután már átnéztem az egészet, és nincs itt, ez csak lehet nem lesz itt. 

Van ennek értelme mindenki? Tehát ez olyan, mint a bináris keresés megőrzése képességeit láncolt listák. Cool, és így a második típus Az adatok szerkezete srácok kipróbálhatják végrehajtási a PSET, Önnek csak ki kell választani egy módszer. De talán egy alternatív módszert A hash tábla, hogy mit nevezünk Trie. 

Minden olyan Trie van egy bizonyos típusú fa vannak olyan értékei megy más értékeket. Tehát ahelyett, hogy a bináris fa, abban az értelemben, hogy csak egy dolog is pont két, akkor már Egy dolog pont sok-sok dolgot. Meg kell főként tömbök amelynek belsejében tárolt mutatók, mely egy másik tömböt. 

Tehát a csomópont, hogy hogyan meghatározná a Trie az azt akarjuk, hogy a Logikai, c szót, ugye? Tehát a csomópont logikai mint igaz vagy hamis, Először élén tömb, ez a szó? Másodszor, azt akarjuk, hogy a mutatók mindenre, amit a többiek is. Egy kicsit bonyolult, egy kicsit elvont, de Meg fogom magyarázni, mi, hogy minden eszközt. 

Tehát itt, a tetején, ha Van egy sor kijelentette már, Egy csomópont, ahol van egy logikai tárolt érték az elülső hogy megmondja, hogy ez a szó? Ez nem egy szó? És akkor már a többi a tömb ténylegesen eltárolja az összes lehetőségeit, mi lehet az. Tehát, például, mint a a tetején van Az első dolog, hogy azt mondja, igaz, vagy hamis, igen vagy nem, ez az egy szó. 

És akkor már 0-tól 26 A levelek tárolható. Ha akartam keresni itt A denevér, megyek a top és nézek B. találom B én tömb, és így tudom, OK, B egy szót? B nem egy szó, így tehát Azt kell tovább keresni. Menjek a B, és nézek a mutatót, hogy a B felé mutat és látok egy másik sor információt, ugyanazt a szerkezetet, hogy a miénk volt. 

És here-- ó, a következő levél [hallhatatlan] az A. Szóval nézzük, hogy tömbben. Találunk a nyolcadik értéket, majd megnézzük, hogy, jaj, hé, hogy egy szó, van B-A szó? Ez nem egy szó. Van, hogy keresd. 

És akkor nézzük, hogy hol A mutató az egy pontot, és megjegyzi, hogy más módon is amely már több értéket tárolni. És végül eljutunk B-A-T, amely egy szót. És így a következő alkalommal nézel, te leszel is, hogy a csekket a, igen, ez a logikai függvény igaz. És így abban az értelemben mi vagyunk a fajta Az rendelkező fa tömböket. 

Tehát akkor milyen keressen meg. Ahelyett hashing egy funkciót, és értékadásra a láncolt lista, ha csak végre egy Trie, hogy a keresések downwords. Nagyon, nagyon bonyolult dolog. Nem könnyű gondolkodni, mert olyan vagyok, mint köpködni számos adat struktúrákat rád, de nem mindenki ilyen megérteni, hogy a logika működik? 

OK, hűvös. Tehát a B-A-T, majd fogsz keresni. A következő alkalommal fogsz látni, ó, hé, ez igaz, így tudom, hogy ez legyen szó. 

Ugyanezt állatkertben. Tehát itt van a dolog most, ha akart keresni állatkertbe, most, Jelenleg állatkertben nem szó, hogy a szótár mert, ahogy ti is látni, a Először is, hogy van egy logikai return true van végén zoom. Van Z-O-O-M. 

És így van, akkor valójában nem is a szó, állatkert, az, hogy a szótár mert ez a jelölőnégyzet nincs bejelölve. Így a számítógép nem tudjuk, hogy állatkertben egy szót mert az is, hogy mi már tárolta, csak zoom itt valójában egy logikai értéket hogy a már megfordult igaz. Tehát, ha azt akarjuk, hogy helyezze be a szót, állatkert, figyelembe, hogy a szótár, hogyan érjük el ezt csinálod? Mit kell tennünk, hogy győződjön meg arról, mi számítógép tudja, hogy a Z-O-O egy szó és nem az első szó a Z-O-O-M? 

Közönség: [hallható] 

ANDI Peng: Pontosan, mi szeretnénk, hogy győződjön meg arról, hogy ez a Itt, hogy logikai érték pipálni, hogy ez igaz. Z-O-O, akkor megyünk, hogy ellenőrizze, hogy így pontosan tudjuk, hé, állatkertben egy szót sem. Azt fogom mondani a számítógép, hogy ez az egy szó, így hogy amikor a számítógép ellenőrzi, tudja, hogy állatkertben egy szót sem. 

Mert emlékszem mindezen adatok struktúrák, akkor nagyon könnyű számunkra mondani, ó, a BAT szó. Zoo egy szó. Zoom egy szó. De ha építünk rá, A számítógép nem tudja. 

Tehát meg kell mondani, hogy pontosan mi pont ez a szó? Mi az a pont ez nem egy szó? És mi pont tudom kell keresni a dolgokat, és mi pont kell ahhoz, hogy a következő? Mindenki egyértelmű, hogy? Hűvös. 

És akkor jön a probléma, hogy hogyan tennénk menj behelyezésével valamit hogy valójában nem létezik? Tehát mondjuk, szeretnénk beszúrni a szó, fürdő, a mi Trie. Ahogy ti is látni, mint a jelenleg minden van most a B-A-T, és ez az új adatstruktúra ott volt egy korsó, amely Rámutatott, hogy null mert azt feltételezzük hogy, jaj, nincs szó után a B-A-T, miért kell tartani miután a dolgok után, hogy a T. 

De a probléma merül fel, ha nem teszünk Önnek szeretnénk, hogy egy szó, ami után A T. Ha van fürdő, te szeretne majd egy H jogot. És így, ahogy mi fogunk tenni, hogy az fogunk létrehozni egy külön csomópont. Mi nem oszt bármilyen mennyiségű A memória az új tömb, és megyünk máshová átirányítani mutatók. 

Megyünk rendelheti H Először is, ez a null, fogunk megszabadulni. Fogunk van A H-pont lefelé. Ha látunk egy H, azt akarjuk, hogy menjen máshová. 

Itt, akkor ellenőrizze le igen. Ha elérünk egy H után T, ó, akkor tudjuk, hogy ez a szó. A logikai fog visszatérni igaz. Mindenki tisztában, hogy történhetett? OKÉ. 

Tehát lényegében az összes Ezen adatok struktúrák hogy eljutottunk addig több mint ma, én már ment át őket nagyon, nagyon gyorsan és nem az, hogy sokkal részletek és ez rendben. Miután elkezdte a Messiás vele, akkor lesz nyomon követése, ahol minden pointerek, mi folyik a adatstruktúrák, satöbbi. Ők lesznek nagyon hasznos, és ez rajtad múlik srácok, hogy teljesen kitalálni, hogyan azt szeretné, hogy végre a dolgokat. 

És így pset4, a 5-- ó, hogy rossz. Pset5 a helyesírási hibák. Mint már mondtam, fogsz, ha egyszer újra letölteni a forráskódot tőlünk. Ott lesz három fő Ez az, amire lehet letölteni. Majd letölthető szótárak, KERS, és a szövegeket. 

Mindazok a dolgok vannak sem szótárak a szavak hogy azt akarom, hogy ellenőrizze vagy vizsgálati információk hogy szeretnénk, ha a helyesírás-ellenőrző. És így a szótárak adunk fogsz hogy az Ön aktuális szó, hogy szeretnénk tárolását valahogy oly módon, hogy az hatékonyabb, mint egy tömb. És akkor a szövegek lesz, amit mi megkérdezi, hogy pontosan ellenőrizze, hogy Minden a szavait vannak valós szavakat. 

És így a három blokk programok, akkor adunk Önnek nevezzük dictionary.c, dictionary.h, és speller.c. És így az egész dictionary.c tesz, amit kért, hogy hajtsák végre. Betölti szó. Ez helyesírás ellenőrzést őket, és ez biztosítja, hogy minden megfelelően van behelyezve. 

diction.h csak egy könyvtár fájl hogy kijelenti mindazokat a funkciókat. És speller.c, fogunk adni. Önnek nem kell módosítani semmit. Minden speller.c jelent az, hogy ezt, betölti azt, sebességét ellenőrzi azt, teszteli a benchmark, mint hogy hogyan Gyorsan te képes csinálni a dolgokat. 

Ez egy helyesírás. Csak ne szórakozz vele, de hogy Biztosan érti, hogy mit csinál. Az általunk használt nevezett funkció getrusage, hogy teszteli a teljesítményét a varázslat ellenőrzőt. Csak annyit tesz, alapvetően tesztelésére ideje mindent a szótárban, úgyhogy győződjön meg róla, hogy te érted. Legyen óvatos, hogy ne szórakozz vele, vagy más dolgok nem fog megfelelően futni. 

És ennek nagy része Kihívást jelent srácok, hogy valóban módosítani dictionary.c. Megyünk, hogy az Ön 140.000 szavak szótára. Fogunk kapsz egy szöveges fájlt, amely ezeket a szavakat, és azt szeretnénk, ha meg tudjuk szervezni őket egy hash tábla vagy Trie mert amikor azt kérjük, hogy pontosan check-- elképzelni, ha varázslat ellenőrzésére, mint Homérosz Odüsszeia. Ez olyan, mint ez a hatalmas, óriási tesztet. 

Képzeld el, ha minden egyes szó, amit meg kellett nézni keresztül egy sor 140.000 értékeket. Ez lenne, hogy örökre a gép futtatására. Ezért is szeretnénk szervezni a adatok hatékonyabb adatszerkezetek például egy hash tábla vagy Trie. És akkor ti is egyfajta A keresés esetén elérhető dolgokat könnyebben és gyorsabban. 

És ezért legyen óvatos, hogy megoldja ütközések. Fogsz kapni egy csomó A szavai kezdetű A. Fogsz kapni egy csomó szó kezdetű B. Akár te srácok hogyan szeretné megoldani azt. Talán van még hatékony hash függvény mint az első betű valamit, és így rajtad múlik srácok, hogy milyen csinálsz, amit akarsz. 

Talán szeretne hozzáadni összes betűt együtt. Lehet, hogy szeretne tetszik csinálni furcsa dolgokat hogy számot a betűk száma, bármi. Akár srácok hogyan akarsz csinálni. Ha azt szeretnénk, hogy csinál egy hash tábla, ha szeretnék kipróbálni egy Trie, teljesen rajtad múlik. Én figyelmezteti Önt idő előtt, hogy a Trie jellemzően egy kicsit nehezebb csak azért, mert van egy csomó több mutató nyomon követni. De teljesen rajtad múlik srácok. Ez sokkal hatékonyabb a legtöbb esetben. Azt akarod, hogy valóban képes tartani követhetjük a mutatók. Mint ugyanezt csinálja hogy csinálok itt. Ha akarsz beszúrni értékeket egy hash tábla vagy törölni, győződjön meg róla, hogy te Tényleg nyomon követése ahol minden azért van, mert ez nagyon egyszerű, mert ha én vagyok próbál beszúrni, mint a szó, Andy. Mondjuk azt, hogy ez egy igazi szó, a szó, Andy, egy hatalmas listát A szavak. 

Ha én csak véletlenül átminősítése egy mutató rossz, hoppá, ott megy a teljes egészében A többi az én láncolt lista. Most az egyetlen szó, amit van Andy, és most az összes többi szavakat a Szótár elvesztek. És így azt szeretnénk, hogy győződjön meg róla, nyomon követni az összes mutató különben meg fogsz kapni hatalmas gondok vannak a kódot. Döntetlen a dolgokat alaposan, lépésről lépésre. Azt teszi, hogy sokkal könnyebb gondolni. 

És végül, azt szeretné, hogy képes legyen tesztelje a teljesítményét a programot a táblán. Ha a srácok, hogy egy nézd meg CS50 most, mi nevezzük a nagy táblára. Ez a ponttáblára a leggyorsabb helyesírás-ellenőrzés alkalommal minden a CS50 most, azt hiszem, a felső, mint 10 alkalommal azt hiszem, nyolc közülük személyzet. Valóban szeretnénk srácok verni minket. 

Mindannyiunkat igyekszünk végrehajtani a leggyorsabb kódot, mint lehetséges. Szeretnénk, ha a srácok, hogy megpróbálja megtámadni velünk, és végrehajtása gyorsabb, mint mindannyiunk tud. És így ez valóban az első alkalom, hogy mi vagyunk kérve srácok, hogy nem egy PSET, hogy akkor tényleg bármilyen módszerrel akarsz. 

Mindig azt mondom, ez inkább hasonlít hogy egy valós megoldást, igaz? Azt mondják, hé, szükségem van rád, hogy ezt. Építeni egy program, amely nem ezt nekem. Csináld, ahogy akarod. Csak azt tudom, hogy én akarom, hogy gyors. Ez a kihívás ezen a héten. Srácok, megyünk hogy kapsz egy feladatot. Fogunk kapsz egy kihívás. És akkor ez akár a srácok hogy teljesen csak kitalálni mi a leggyorsabb és hatékony módja annak, hogy végre ezt. Igen? 

Közönség: Megengedi, ha akart kutatás gyorsabb módja csinálni hash táblák online tehetünk hogy és idézik valaki másnak a kódot? ANDI Peng: Igen, teljesen jól. Tehát, ha a srácok olvassa el a spec, van egy határ a spec, amely azt mondja, srácok teljesen mentesek a kutatás hash funkciók mik A gyorsabb hash függvények futtatni a dolgokat, mint Amíg arra hivatkoznak, hogy kódot. Tehát egyesek már kitalálta gyors módja csinál helyesírás-ellenőrző, a gyors módjait információ tárolására. Teljesen rajtad múlik srácok, ha szeretnénk, hogy csak úgy, hogy, ugye? Győződjön meg róla hivatkozva. A kihívás itt tényleg hogy próbálunk tesztelni ügyelve arra, hogy tudod, magad körül mutatók. Amennyire csak végrehajtási a tényleges hash függvény és jön, mint A matematikai erre, srácok a kutatás bármi módszerek Online akartok. Igen? 

Közönség: Meg tudjuk idézni csak használja a [hallhatatlan]? 

ANDI Peng: Igen. Tudod csak, itt a magyarázat, akkor idézni, mint, ó, kivett yada, blabla, blabla, hash függvény. Bárki bármilyen kérdése? Igazából libbent a szekció ma. Én leszek itt, hogy válaszoljon a kérdésekre is. 

Is, mint mondtam, irodai órát ma és holnap. A specifikáció ezen a héten valóban szuper könnyű és szuper rövid olvasni. Azt javasoljuk, hogy egy pillantást, csak olvassa el a teljes egészében meg. 

És Zamyla ténylegesen végigvezet keresztül minden egyes funkciók meg kell végrehajtani, és így Nagyon, nagyon világos, hogyan kell csinálni mindent. Csak azért, hogy győződjön meg róla, követi nyomon a mutatók. Ez egy nagyon nehéz PSET. 

Ez nem támadja, mert tetszik, ó, a fogalmak sokkal több nehéz, vagy meg kell tanulni annyira új szintaxist az utat hogy te az utolsó PSET. Ez PSET nehéz, mert olyan sok mutató, és akkor nagyon, nagyon könnyen egyszer Van egy hiba a kód nem lesz képes találni, ahol ez a bogár van. 

És így teljes és tökéletes benned srácok, hogy képes legyen legyőzni [hallhatatlan] szócikk. Igazából már nem olyan írásos bányában még, de én vagyok arról, hogy írjon az enyém. Tehát miközben írsz tiéd, én leszek az írás az enyém. Én fogom próbálni, hogy az enyém gyorsabb, mint a tiéd. Meglátjuk, aki a leggyorsabb. 

És igen, én is látni az összes srácok itt kedden. Futok egyfajta mint egy PSET műhely. Az összes szakasz ezen heti PSET műhelyek, így a srácok sok lehetőséget segítségért, hivatali időben, mint mindig, és én nagyon várom, hogy elolvasás a srácok "kódot. Van vetélkedők ide, ha srácok akarnak jönni kap e. Ez minden.