[Zenelejátszó] DAVID MALAN: Ez CS50. És ez mind a kezdő és a end-- mint literally-- majdnem vége A hét hat. 

Azt gondoltam megosztani a kicsit a móka tény. Én ezt húzta fel a Az elmúlt félév adatai beállítva. Talán emlékeznek, hogy arra kérünk, minden p szereplő űrlapot, ha már figyelte az interneten vagy ha már részt vesz. És itt van az adat. Szóval ma nagyon is kiszámítható. De azt akartuk, hogy kiad egy kicsit Az idő veled mégis. Bárki szeretné sejtjük, hogy miért ezt a gráf olyan csipkézett, akár lefelé, akár lefelé, így folyamatosan? Mit az egyes csúcsok és hullámvölgyek képviselnek? 

KÖZÖNSÉG: [hallható] DAVID MALAN: Valóban. És még szórakoztatóan, isten ments, tartunk egy előadást a péntek elején a félév, ez az, amit látni történni. Így ma, amikor veszünk egy kicsit többet adatszerkezeteket. És, hogy még több szilárd mentális modellt problémák öt, ami most ki. Hibát, ahol fogunk kézzel egy szöveges fájlt valamilyen 100000 plusz angol szavak, és Ön megy, hogy hogy kitaláljuk, hogyan lehet ügyesen betöltésére a memóriába, a RAM-ba, a néhány adat szerkezet, amelyet választott. 

Most az egyik ilyen adat struktúra is, de talán nem kell, A meglehetősen egyszerű láncolt lista, amit be utoljára. És egy láncolt lista volt legalább egyik előnye tömb. Mi az az egyik előnye, hogy láncolt lista vitathatatlanul? 

KÖZÖNSÉG: beillesztése. 

DAVID MALAN: beillesztése. Mit jelent ez? 

KÖZÖNSÉG: Bárhol mentén A lista [hallható]. 

DAVID MALAN: Jó. Szóval lehet beszúrni egy elemet, ahol azt szeretné, a közepén a lista anélkül, hogy shuffle semmit, amely arra a következtetésre jutottunk, hogy a válogatás viták, nem feltétlenül jó dolog, mert időt vesz igénybe, hogy valóban mozog az összes ilyen emberre balra vagy jobbra. És így egy láncolt lista, akkor csak osztja a malloc, egy új csomópont, majd frissítse pár pointers-- kettő, három művelet max-- és képesek vagyunk slot valaki bárhol a listában. 

Mi más volt előnyös egy láncolt lista? Igen? 

KÖZÖNSÉG: [hallható] DAVID MALAN: Tökéletes. Tökéletes. Nagyon dinamikus. És, hogy te nem követnek, előre, bizonyos rögzített mérettel darab memória, mint akkor kellett volna hogy egy sor, a fejjel, amely hogy meg lehet kiosztani csomópontok csak kereslet ezáltal kizárólag annyi helyet ahogy valójában szüksége van. Ezzel szemben egy sor, lehet, hogy véletlenül osztja túl kevés. És akkor ez csak megy hogy a fájdalom a nyak átcsoportosítása egy új, nagyobb tömb, másolja minden felett, szabad a régi tömb, majd mozgassa a dolgára. Vagy ami még rosszabb, lehet, hogy osztja út több memóriát, mint amennyire valóban szükség van, és így fogsz egy nagyon gyéren lakott tömb, hogy úgy mondjam. 

Így a kapcsolt listát ad e előnyei dinamizmus és rugalmasság A beszúrások és törlések. De biztosan kell lennie egy árat fizetett. Sőt, az egyik témája tárni kvíz nulla volt egy pár a kompromisszumok láttunk eddig. Tehát mi az a kifizetett ár vagy a hátránya, a láncolt lista? Igen. 

KÖZÖNSÉG: Nem véletlen hozzáférés. 

DAVID MALAN: Nem véletlen hozzáférés. De kit érdekel? Véletlen hozzáférés nem hangzik meggyőző. 

KÖZÖNSÉG: [hallható] DAVID MALAN: Pontosan. Ha azt szeretné, hogy egy bizonyos algorithm-- és hadd valójában javasol bináris keresés különösen, ami az egyik általunk használt jó bit-- ha nincs közvetlen elérésű, Ön nem tudja, hogy egyszerű számtani találni, mint a középső elem és ugrás jobbra hozzá. Meg kell kezdeni, hanem az első elem és lineárisan kereshetőek bal jobbra, ha meg akarja találni a középső vagy bármely más elemet. 

KÖZÖNSÉG: Valószínűleg ez több tárhelyet. 

DAVID MALAN: úgy több memóriát. Hol van az a kiegészítő költség jön a memória? 

KÖZÖNSÉG: [hallható] DAVID MALAN: Pontosan. Ebben az esetben itt, mi volt láncolt lista egészek, és mégis mi duplázás a memória mennyisége szükségünk van az is tárolja ezeket a mutatókat. Most kisebb a nagy üzlet, mint A struktúrákat kap nagyobb és te tárolása nem szám, hanem talán egy diák, vagy valamilyen más tárgy. De a lényeg biztosan marad. És így számos műveletek A kapcsolt listák hívták voltak nagy O n-- lineáris. Dolgok, mint a beillesztés vagy keresés vagy törlés esetén egy elem történetesen a legvégén A lista legyen az rendezve, vagy sem. 

Néha lehet, hogy szerencsés és így alacsonyabb korlátokat e műveletek is lehet konstans időt, ha te vagy mindig néztem az első elem, például. De végül is, megígértük hogy elérjék a Szent Grál adatstruktúrák, vagy néhány közelítés cikkére, útján konstans idő. Találunk elemek vagy add elemek vagy elemek eltávolításához a listából? Meglátjuk, elég hamar. És kiderül, hogy az egyik A mechanizmusok vagyunk fog kezdeni használni ma, évi felhasználás p meg öt, valójában nagyon ismerős. Például, ha ez egy csomó A vizsgálat könyvek, amelyek mindegyike egy hallgató az első Keresztnév és vezetéknév rajta, és én értük tól a végén egy vizsga, és ezek mind nagyon sok véletlenszerű sorrendben, és azt akarjuk, hogy megy a válogatás ezeket a vizsgákat úgy, hogy ha osztályozni ez csak egy sokkal könnyebb és gyorsabban átadja nekik vissza a diákok betűrendben. Milyen lenne az ösztönök lesz egy halom vizsgák, mint ez? 

Nos, ha te, mint én, akkor Lehet látni, hogy ez m, így fogom egyfajta E szándék, ha ez az asztalra vagy a padlóra, ahol a Én terjed dolgok out-- vagy a tömb really-- Talán fel minden asszony ott. Oh. Itt egy A. Szóval talán fel a Mivel itt. Oh. Itt egy újabb A. megyek tenni, hogy itt van. Itt egy Z. Itt egy másik, M. és így Lehet kezdeni a kupac, mint ez. És akkor talán megyek később és valami nagyon nitpicky-ly sort az egyes cölöpök. De a lényeg az, hogy én nézne A bemenet, hogy én vagyok balkezes és azt, hogy néhány kiszámítása határozat alapján, hogy a bemeneti. Ha kezdődik, tedd oda. Ha kezdődik Z, tedd át ott, és minden között. 

Tehát ez egy olyan technika, ami általánosan ismert hashing-- H-A-S-H-- ami általában azt jelenti, hogy a bemenet és használ, hogy input kiszámítása egy értéket, általában egy számot, és hogy szám a mutató egy tároló konténer, mint egy tömb. Más szóval, talán van egy hash függvény, mint én a fejemben, hogy ha látom, valaki név aki kezdődik A, Fogom feltérképezni, hogy a nullára a fejemben. És ha látom, hogy valaki a Z, én vagyok majd feltérképezni, hogy a 25 a fejemben majd tegye, hogy a Az utolsó nagy halom. 

Most, ha úgy gondolja, hogy nem az agyam hanem egy C program, milyen számokat tudott támaszkodik annak elérése, hogy ugyanazt az eredményt? Más szóval, ha volt az ASCII karakter A, Hogyan határozzák meg mit vödröt tedd? Valószínűleg nem akar tedd be 65 vödör, ami lenne, mint ott minden ok nélkül. Hol akarod, hogy egy tekintve ASCII érték? Hol akarod tenni annak ASCII érték, hogy dolgozzon ki egy intelligensebb vödör hogy betette? 

KÖZÖNSÉG: Mínusz A. 

DAVID MALAN: Igen. Tehát mínusz A mínusz különösen, ha ez a 65 a főváros A. Or 98 ha ez egy kisbetűs a. És így, amely lehetővé teszi számunkra, hogy nagyon egyszerűen és nagyon egyszerű számtani tenni valamit egy vödörbe, mint ezt. Így kiderül, valójában nem ezt is még a vetélkedők. 

Szóval lehet, hogy emlékszem te köröztek a tanítás fickó nevét a borítón. És a TF nevét szerveztek ezekbe oszlopok betűrendben, nos, akár hiszed, akár nem, amikor mind a 80 plusz nekünk összejöttünk a másik éjszaka fokozat, az utolsó lépés a mi osztályozó folyamat az, hogy a hash vetélkedők egy nagy hely a padló, a [hallható] és a laikus mindenki vetélkedők ki pontosan sorrendben TF nevek a fedelet, mert akkor sokkal könnyebb számunkra keresgélni, hogy a lineáris keresés vagy valamilyen okosság a TF, hogy megtalálja a vagy diákjai "vetélkedők. 

Szóval ez az ötlet, hasítás hogy látni fogja az elég erős valójában elég közhely és nagyon intuitív, hasonlóan talán felosztani és uralkodj volt hét nulla. Azt várom, hogy a gyors hackathon Egy pár évvel ezelőtt. Ez Zamyla és egy pár egyéb személyzet üdvözlő diákok ahogy jöttek. És volt egy csomó összecsukható táblázatokban névcímkékkel. És mi volt a neve szervezett címkék és mint a mint ott és a Zs ott. És így az egyik a TF nagyon okosan írta ezt az utasítást a nap. És a 12. héten a félév e minden tökéletesen érthető és mindenki tudta, mit kell tennie. De akkor már bármikor sorban áll ugyanúgy, te végrehajtása ugyanezt az elvet a hash. Szóval hivatalossá, hogy egy kicsit. Itt van egy tömb. Ez húzott, hogy egy kicsit széles csak ábrázolni, vizuálisan, hogy talán fel húrok valami ilyesmi. És ez tömb nyilvánvalóan teljes mérete 26. És a dolog az úgynevezett táblázat önkényesen. De ez csak egy művész kiadatás amit egy hash tábla lehet. 

Tehát egy hash tábla most fog egy magasabb szintű adatszerkezet. Végén a nap vagyunk arról, hogy látni, hogy végre tudják hajtani a hash tábla, amely sokkal, mint a check-in sorban egy hackathon hasonlóan ez táblázat a rendezés vizsga könyveket. De egy hash tábla fajta ez a magas szintű koncepció, hogy jönne egy tömböt a motorháztető alatt hajtják végre, vagy jönne egy hosszú listát, vagy akár talán más adatszerkezeteket. És most, hogy a vevő theme-- néhány ilyen alapvető összetevők mint egy tömb, és az épület blokk most hossza lista és látta, hogy mit tudunk építeni a tetején e, mint összetevők egy recept, így egyre több és több érdekes és hasznos a végleges eredmények. 

Tehát a hash tábla talán végrehajtása memória képileg, mint ez, de hogyan lehet valójában kódolva fel? Nos, talán csak ez. Ha a kapacitást minden sapkák, csak néhány constant-- például 26, 26 betűi alphabet-- Lehet hívni a változó asztal, és talán azt állítják, hogy megyek tedd char csillagok ott, vagy string. Szóval ez olyan egyszerű, mint ez, ha szeretnénk végrehajtani a hash tábla. És mégis, ez tényleg csak egy tömb. De ismétlem, a hash táblázat most mit fogunk hívni egy absztrakt adattípus ez csak egyfajta fogalmi rétegezés tetejére valami több világi most, mint egy tömb. 

Most, hogy megyünk körülbelül problémák megoldása? Nos, korábban az volt a luxus Az, hogy elég hely van asztal így tudtam tenni a vetélkedők bárhol akartam. Ahogy az így megy itt. Zs is megy itt. Ms is megy itt. Aztán volt egy kis extra helyet. De ez egy kicsit cheat jog most, mert ez a táblázat, ha én tényleg gondolt rá, mint egy sor, csak lesz a bizonyos rögzített mérettel. 

Szóval technikailag, ha kihúzom egy másik diák kvíz és nézd meg, ó, ez a személy neve kezdődik egy A is, Valahogy szeretnék tedd oda. De amint én tettem oda, ha ez a táblázat valóban tömbjét képviseli, Megyek is érvényesítendő vagy felülírás aki ezt diák kvíz. Jobb? Ha ez egy tömb, csak egy dolog lehet megy minden ilyen sejtek vagy elemekkel. És én ilyen van válogathat. 

Most korábban valahogy csalt és tette ezt vagy azt csak egyfajta egymásra őket egymás felett. De ez nem fog repülni kódot. Szóval, ha tudtam tenni a második hallgató, akinek a neve az A, ha minden volt ez álló asztal hely? És én is használtam három slot, és úgy néz ki, mintha csak egy pár mások. Mit lehet tenni? KÖZÖNSÉG: [hallható] DAVID MALAN: Igen. Lehet, hogy most csak tartsa egyszerű. Jobb? Ez nem illik, ahol szeretnék, hogy tedd. Így fogok tenni, hogy technikailag ahol a B menne. Most, persze, kezdek festeni magam egy sarokba. Ha kapok egy diák akinek a neve valójában B, B most fog mozgatni egy kicsit előre, mivel megtörténhet, igen, ha ez a B, most már megy itt. 

És ez nagyon gyorsan veszélyessé váló, de ez egy technika, amely ténylegesen nevezik lineáris tapintás, amely csak úgy a tömb, hogy a vonal mentén. És csak ilyen szonda vagy vizsgáljuk meg az elérhető elemek keres egy szabad hely. És amint megtalálni az egyik, akkor dobja el oda. 

Most, az ár fordítottak mert ez a megoldás, az mi? Van egy fix méretű tömb, és behelyezésekor nevek bele, legalábbis kezdetben, mi a menetideje behelyezés hozataláért a diákok vetélkedők a megfelelő kanalak? Big O, mi? 

KÖZÖNSÉG: n. DAVID MALAN: Azt hallottam, nagy O n. Nem igaz. De majd ugratni egymástól miért csak egy pillanat. Mi más lehet? 

KÖZÖNSÉG: [hallható] DAVID MALAN És hadd csinálni vizuálisan. Tegyük fel, hogy ez a levél S. 

KÖZÖNSÉG: Ez az egyik. DAVID MALAN: Ez az egyik. Jobb? Ez egy tömb, amely azt jelenti, hogy van véletlen hozzáféréssel. És ha arra gondolunk, ez a nulla legyen, és ezt a 25, és rájövünk arra, Ó, itt van a bemenet S, Én biztosan konvertálni S egy ASCII karakter, a megfelelő számot nulla és 25 majd azonnal tedd, ahova tartozik. 

Persze, amint jutok el a második személy, aki neve A, B vagy C végül, ha én is használtam a lineáris tapintás, mint a megoldás, a menetideje behelyezése a legrosszabb esetben valóban fog ruházni abba, hogy mi? És én hallottam itt helyesen korán. KÖZÖNSÉG: [hallható] DAVID MALAN: Tehát n valóban egyszer van egy elég nagy adathalmaz. Így, egyrészt, ha A tömb elég nagy és az adatok kevés elég, hogy ezt a gyönyörű időben állandó. De amint elkezd egyre több és több elemet, és csak statisztikailag kapsz több embert a levél A mint a neve vagy a levél B, a potenciálisan ruházzák át valami lineáris. Így nem egészen tökéletes. Így tudnánk jobban csinálni? 

Nos, mi volt a megoldás, amikor hazafelé szeretné, hogy több mint dinamizmus olyasmi, mint egy tömb megengedett? KÖZÖNSÉG: [hallható] DAVID MALAN: Mit mutatunk be? Igen. Tehát a láncolt lista. Nos, lássuk, mi a kapcsolt lista talán nem nekünk helyette. Nos, hadd javaslom, hogy felhívni a kép az alábbiak szerint. Most ez egy másik kép egy példa egy másik szöveget, valójában, hogy valójában a tömb mérete 31. És ez csak a szerző úgy döntött, hogy hash húrok nem a személy nevét, de alapján születésnapok. Függetlenül attól, hogy a hónap, azt gondoltam ha született az első olyan hónap vagy a 31 havi, a szerző majd hash alapuló érték, annak érdekében, hogy terjed a nevek egy kicsit több, mint 26 foltok is lehetővé teszik. És talán ez egy kicsit egységesebb mint megy abc betűk, mert persze ott talán több ember a világon, nevét hogy kezdődik A mint biztosan más az ábécé. Szóval lehet, hogy ez egy kicsit egységesebb, feltételezve, egyenletes eloszlás A babák az egész egy hónap. 

De, persze, ez még mindig nem tökéletes. Jobb? Mi tekintettel ütközések. Több ember ebben a adatstruktúra még amelyek azonos születési legalább te függetlenül a hónap. De mi a szerző tenni? Nos, úgy néz ki, mint van egy tömb a bal oldali húzott függőlegesen, de ez csak egy művész kiadatás. Nem számít, milyen irányba felhívni egy tömb, ez még mindig egy tömb. Mi ez a tömb látszólag? 

KÖZÖNSÉG: láncolt lista. 

DAVID MALAN: Igen. Úgy néz ki, hogy ez egy tömb láncolt lista. Tehát ismét, hogy ezen a ponton a fajta Az ezen adatok struktúrákat most összetevőként több Érdekes megoldás, akkor feltétlenül, hogy egy alapvető, mint egy tömb, majd vegye valami érdekes, mint a láncolt lista és még összekapcsolják őket egy még További érdekes adat struktúrát. És valóban, ez is lenne nevezhető hash tábla, ahol a tömb valóban a hash tábla, de a hash tábla láncok, hogy úgy mondjam, amely képes növekedni, vagy zsugorodás alapján elemek száma a beszúrni kívánt. 

Most, ennek megfelelően mi a futási idő most? Ha szeretné szúrni valakit akinek születésnapját október 31 hol ő megy? Rendben van. Legalul, ahol azt mondja 31. És ez tökéletes. Ez volt konstans idő. De mi van, ha talál valaki mást akinek születésnapja van, lássuk, Október, november, december 31? Hol van ő fog menni? Ugyanaz a dolog. Két lépés mégis. Ez állandó, bár nem igaz? Rendben van. Abban a pillanatban, amikor az. De az általános esetben, A több ember hozzátesszük, véletlenszerűen, megyünk hogy egyre több és több ütközés. 

Most ez egy kicsit jobb, mert technikailag most a láncok lehetne A legrosszabb esetben, meddig? Ha illessze n az embereket ebbe a több kifinomult adatstruktúra, n emberek, A legrosszabb esetben lesz n. Miért? 

KÖZÖNSÉG: Mert ha mindenki ugyanaz a születésnapja, ők lesznek egy sort. DAVID MALAN: Tökéletes. Lehet, hogy egy kicsit kitalált, de valóban a legrosszabb esetben, ha mindenkinek ugyanaz születésnapja, tekintettel a bemenő adatokra van, fogsz egy masszívan hosszú láncban. És így, akkor ez egy hash-tábla, de tényleg ez a Csak egy hatalmas összefüggő listát egy csomó elvesztegetett hely. De általában, ha feltételezzük, hogy legalább születésnapok uniform-- és ez valószínűleg nem. Én így, hogy akár. De ha feltételezzük, a a vita kedvéért hogy azok, akkor elméletileg, ha ez a függőleges képviselet a tömb, nos akkor remélhetőleg te fog kapni láncok, tudod, nagyjából azonos hosszúságú, ahol az egyes ezek jelentése egy nap a hónapban. 

Na most, ha van 31 nap a hónapban, azt jelenti, hogy a működési idő nagyon nagy O-n több mint 31, ami jobban érzi magát, mint a lineáris. De mi volt az egyik kötelezettségvállalások egy pár hétig ezelőtt, amikor jött a kifejező a futás idejét egy algoritmus? Csak csak nézd meg a nagy rend kifejezést. Jobb? 31. határozottan hasznos. De ez még mindig nagy O n. De az egyik téma A probléma meg öt lesz, hogy elismerik, hogy teljesen, aszimptotikusan, elméletileg adatstruktúrát nem jobb, mint egy hatalmas láncolt lista. És valóban, a legrosszabb esetben ez a hash tábla lehet ruházni abba. 

De a valós világban, nálunk az emberek hogy a saját Mac vagy PC, vagy bármi és futnak valós szoftver valós adatok amely algoritmus mész szívesebben? Az egyik, hogy úgy célból lépések vagy a az egyik, hogy tudomásul n osztva 31 fokozatban hogy néhány adatot vagy kikeresni valamilyen információt? Úgy értem, teljesen a 31 teszi a különbség a valós világban. Ez 31-szor gyorsabb. És mi emberek biztosan fogja értékelni azt. 

Így észre a kettősség ott között valójában beszél dolgok elméletileg és aszimptotikusan amely határozottan értékes amint láttuk, de a való világban, ha érdekel csak, hogy a ember boldog általános bemenet, Ön is nagyon jól akar elfogadni az a tény, hogy igen, ez lineáris, de 31-szer gyorsabb mint a lineáris lehet. És még jobb, nem csak azt kell nem valami önkényes, mint a születésnap, tudtuk eltölteni egy kis több időt és okosság és arra gondolok, mit lehet csinálni, adott személy nevét és talán a születési össze azokat összetevők kitalálni valamit hogy valóban több egységes és kevésbé csipkézett, hogy úgy mondjam, mint ezt a képet jelenleg azt javasolja lehet. Hogyan lehetne végrehajtani ezt a kódot? Nos, hadd javaslom, hogy csak kölcsön néhány szintaktikai voltunk használt egy-két alkalommal eddig. És én fogom meghatározni egy csomópont, amely ismét egy általános kifejezés csak néhány konténer néhány adatszerkezet. Fogom javasolni, hogy egy string megy oda. De megyünk elkezdi e képzés kerekek le most. 

Nincs több CS50 könyvtár Tényleg, ha nem akar használni a végső projekt, ami rendben van, de most megyünk, hogy húzza vissza a függöny és azt mondják, ez csak egy char csillag. A szó tehát ott lesz a személy nevét kérdéses. És most van egy link Itt a következő csomópont annak érdekében, hogy ezek képviselik az egyes csomópontok a láncban, potenciálisan A láncolt lista. 

És most hogyan Kijelentem a hash tábla maga? Hogyan Kijelentem, az egész szerkezet? Nos, tényleg, nagyon, mint régen egy mutatót hogy csak az első eleme a lista előtt, hasonlóan tudok csak mondani Csak kell egy csomó mutatók kell ez az egész hash tábla. Megyek, hogy egy tömb hívott táblázat hash tábla. Ez lesz a méret kapacitás. Így sok elem elfér benne. És minden egyes ilyen elem ebben tömb lesz a csomópont csillag. Miért? Nos, egy ezt a képet, amit én végrehajtása hash táblázat hatékonyan az elején csak ezt a tömböt, hogy már húzott függőlegesen, elrendezve, ennek négyzetek jelentése mutató. Ez pedig, hogy perjeleket rajtuk keresztül csak null. És az is, hogy nyilak majd jobbra tényleges mutatók tényleges csomópontok, ergo a kezdete egy láncolt lista. 

Tehát itt, tehát az, hogy hogyan lehet, hogy végre egy hash tábla végre külön láncolás. Most már mi a jobb? Rendben Megígértem utoljára tudtunk elérni konstans idő. És valahogy adtam konstans idő itt, de aztán azt mondta, nem igazán konstans időt, mert még mindig függ az összes elemek száma te bevitelére a az adatszerkezet. De tegyük fel, hogy ezt tette. Hadd menjek vissza a képernyőre itt. Hadd vetíteni ezt itt, világos a képernyőn, és tegyük fel, én tettem ezt. Tegyük fel akartam beilleszteni a nevét Daven az az én adatszerkezet. 

Szóval azt akarom, hogy helyezzen be egy húr Daven az adatszerkezet. Mi történik, ha nem használja a hash-tábla, de én használni valami, ami több, mint a fa, mint egy családfát, ahol van néhány gyökér a felső, majd csomópontok és a levelek hogy megy lefelé és kifelé. Tegyük fel, hogy én szeretné szúrni a Daven a mi jelenleg egy üres lista. Fogok csinálni a következő: Én létre fog hozni egy node ebben a családban fa-szerű szerkezet adat úgy néz ki, Egy kis, mint ez, amelyek mindegyike téglalapok már, mondjuk, A most 26 elem benne. És az egyes sejtek ebben tömb lesz hogy képviselje a levél az ábécé. 

Konkrétan fogom kezelni ez A, majd a B, majd a C, majd D, ezt itt. Szóval ez lesz a hatékony képviseli a levél D. De helyezze összes Daven által nevét kell tennem egy kicsit. Szóval először fog hash, hogy úgy mondjam. Megyek nézni az első betű a Daven azon ami nyilvánvalóan a D, és fogok kiosztani olyan csomópont, amely úgy néz ki, mint egy nagy téglalap this-- nagy ahhoz, hogy elférjen az egész ábécét. 

Most D történik. Most A. D-A-V-E-N a cél. Szóval, most mit fogok csinálni ez. Amint elkezdtem D nyilatkozat nincs mutató ott. Ez szemét értékeket abban a pillanatban, vagy talán inicializálás null. De hadd folyamatosan megy ezt az ötletet épület fa. Hadd osztja egy másik ilyen csomópontok 26 elem benne. 

És tudod mit? Ha ez csak egy csomópont a memóriában Én létrehozott malloc, egy struct ahogy azt hamarosan látni, Fogok csinálni this-- Fogok felhívni egy nyilat a dolog, hogy a képviselt D le az új csomópont. És most, először a következő levél Daven nevét, V-- D-A-V-- fogok menni előre és felhívni egy másik csomópont, mint ez, amely a V elem van, amely fogjuk felhívni instance-- Hoppá. Mi nem készít ott. Ez fog menni itt. 

Aztán megyünk úgy, hogy ez az V. És akkor ide megyünk index le V-mit fogunk vizsgálni E. És akkor innen megyünk megy egy ilyen csomópont van. És most van egy kérdés megválaszolására. Meg kell valahogy azt jelzi, hogy mi vagyunk a végén a húr Daven. Így tudtam csak hagyja null. 

De mi van, ha van a Daven teljes név is, amely van, ahogy mondtam, Davenport? Mi van, ha a Daven valójában részkarakterláncként, előtagot egy sokkal hosszabb húr? Mi nem csak a tartósan mondjuk semmi sem megy hogy ott, mert tudtuk soha be egy szót, mint Davenport ebbe adatok Szerkezet 

Szóval, mit tehetünk helyette van kezelni az ilyen elemek mindegyike mivel talán, hogy két elemek belsejében őket. Az egyik egy mutató, sőt, ahogy én csináltam. Így minden ilyen dobozok nem csak egy cella. De mi van, ha a felső one-- az alsó a lesz nulla, mert nincs Davenport csak még. Mi van, ha az első egy valami különleges érték? És ez lesz egy kicsit nehéz kihúzni ezt a méretet. De tegyük fel, ez csak egy pipa. Ellenőrizze. D-A-V-E-N egy string ebben adatszerkezet. 

Közben, ha lenne több hely itt, amit tehettem P-O-R-T, és én sodorhatják ellenőrzés a csomópont amely a T betű a legvégén. Tehát ez egy masszívan összetett megjelenésű adatszerkezet. És a kézírás biztosan nem segít. De ha akartam valamit beszúrni más, átgondolni, hogy mi tennénk. Ha akartuk, hogy Dávid, mi lenne ugyanezt a logikát, a D-A-V, de most szeretném mutatni a következő elem nem az E, de I-től D Tehát lesz több csomópont a fán. Mi lesz, hogy hívás malloc tovább. De én nem akarom, hogy egy teljes káosz kép. Szóval ahelyett, nézd meg egy hogy a már előre megfogalmazott mint ezt nem pont, pont, pontok, de csak rövidített tömbök. De minden csomópont a fán itt jelentése azonos thing-- tömb Ray a mérete 26. 

Vagy ha azt akarjuk, hogy nagyon helyes most, mi ha valakinek a nevét egy aposztróf, hadd Feltételezzük, hogy minden csomópont valójában mint 27-indexek is, nem csak a 26. Szóval ez most lesz egy adat szerkezet úgynevezett trie-- T-R-I-E. A Trie, ami állítólag történelmileg okos név egy fa ami optimalizált visszakeresés, ami természetesen, van írva egy I-E így Trie. De ez a történelem a Trie. 

Tehát egy Trie ez a fa-szerű adat szerkezet, mint egy családfa hogy végül úgy viselkedik, mint azt. És itt is csak egy példa a csomó más ember nevét. De a kérdés most kéznél, ami van nyertünk bevezetésével vitathatatlanul egy bonyolult adatstruktúra, és egy, őszintén, hogy használ sok memóriát. 

Mert annak ellenére, abban a pillanatban, én csak a D és pointer A V és Es és Ns, Én pazarlás fene sok memóriát. De hol töltök egy forrás, Én inkább ezt vissza szerezni a másik. Tehát, ha költök több helyet, mi talán a remény? Hogy én kevesebbet költenek, mi? KÖZÖNSÉG: Kevesebb idő. DAVID MALAN: Time. Most miért lenne az? Nos, mi a beillesztés idő, tekintve a nagy O most, Egy név, mint a Daven vagy Davenport vagy David? Nos, Daven volt öt lépésben. Davenport lesz kilenc lépésben, így lenne egy pár lépést. Dávid öt lépésben is. Tehát ezek konkrét számok, de biztosan van egy felső határt a hossza valakinek a nevét. És valóban, a probléma egyenként öt specifikáció, fogunk javasolni hogy ez valami ez mintegy 40-furcsa karakterek. 

Reálisan, senki sem végtelenül hosszú nevet, ami azt jelenti, hogy a hossza egy nevét vagy a karakterlánc hosszát mi talán bizonyos az állam struktúra vitathatatlanul mi? Ez állandó. Jobb? Lehet, hogy egy nagy konstans, mint a 40-valamit, de ez állandó. És ez nem függőség, hogy hány más nevek ebben adatszerkezet. Más szóval, ha akart most beilleszteni Colton vagy Gabriel vagy Rob vagy Zamyla vagy Alison vagy Belinda vagy bármely más nevek A személyzet ebbe adat szerkezet, az a futási idő beillesztése más nevek lesz egyáltalán hatással hány további elemek az adatstruktúrában már? Ez nem az. Jobb? Mert mi eredményesen ez többrétegű hash tábla. És a menetideje E műveletek nem függ a számát elemek, amelyek az adatstruktúra vagy amelyek végül fog helye az adatstruktúra, de a hossza pontosan mit? 

A szöveg pedig ki, amely nem teszi ez aszimptotikusan konstans time-- nagy O egy. És őszintén szólva, csak a valós világban, ez azt behelyezése Daven nevét veszi mint öt lépés, vagy Davenport kilenc lépések, vagy David öt lépésben. Ez átkozottul kicsi üzemidő. És valóban, ez egy nagyon jó dolog, különösen, ha ez nem függ a teljes számú elem van benne. Szóval, hogyan lehet azt végrehajtani ezt fajta szerkezet kódot? Ez egy kicsit bonyolult, de még mindig ez a csak egy alkalmazása alapvető építőkövei. Megyek újra minket csomópont az alábbiak szerint: bool nevű word-- és ez nevezhetnénk semmit. De a bool jelentése amit rajzoltam, mint a pipa. Igen. Ez a vége a húr ebben adatszerkezet. 

És, természetesen, a csomópont csillag van a gyermekek. És valóban, csak tetszik egy családfát, akkor tartaná a csomópontok hogy lóg ki az alján néhány szülő elem, hogy a gyermekek. És így a gyerekek fog hogy egy sor 27, 27 egy csak, hogy az aposztróf. Megyünk rendezni különleges eset. Így bizonyos nevek aposztróf. Talán még kötőjel kellene menj oda, de akkor lásd p készlet 5 csak gondozás körülbelül betűk és aposztrófok. 

És akkor hogyan képviselt Az adatstruktúra maga? Hogyan képviselik a gyökér E Trie, hogy úgy mondjam? Nos, csak, mint a láncolt lista, akkor kell egy mutatót az első elemet. Egy Trie akkor csak meg kell egy mutatót az alapja ennek a Trie. És onnan lehet hash végig mélyebbre és mélyebbre minden más csomópont a szerkezetben. Így csak ezzel lehet képviseljük, hogy a struktúra. 

Most Meanwhile-- Oh, kérdés. 

KÖZÖNSÉG: Mi bool szó? 

DAVID MALAN: Bool szó Csak ez a C megtestesülés Az, amit leírtam ebbe a mezőbe itt, amikor Elkezdtem felosztása az egyes tömb elemeit két részre. Az egyik egy mutató a következő csomópont. A másik kell lennie olyasmi, mint egy jelölőnégyzetet mondani, hogy igen, van egy szó Daven, hogy véget ér itt, mert nem akarjuk, abban a pillanatban, Dave. 

Annak ellenére, hogy Dave lesz a jogos szó, ő nem a Trie még. És D nem egy szó. És D-A nem egy szó vagy egy nevet. Így a pipa jelzi, csak akkor, ha hit ez a csomópont korábbi útvonal karakterek tulajdonképpen egy string, hogy már ki. Szóval ez a bool ott tesz értünk. 

Minden más kérdésre próbál? Igen. 

KÖZÖNSÉG: Mi az átfedés? Mi van, ha van egy Dave és a Daven? DAVID MALAN: Tökéletes. Mi van, ha van egy Dave és a Daven? Tehát, ha azt beilleszteni, mondjuk egy becenév, A David-- Dave-- a D-A-V-E? Ez tulajdonképpen szuper egyszerű. Szóval csak megy, hogy négy lépést. D-A-V-E. És mit kell csinálni, ha én hit, hogy a negyedik csomópont? Csak fogja ellenőrizni. Mi már jó menni. Kész. Négy lépésben. Állandó idő aszimptotikusan. És most már azt jelezte, hogy a két Dave és Daven vannak húrok a szerkezet. Így nem jelent problémát. És észre, hogy a jelen A Daven nem teszi vesz több időt, vagy kevésbé ideje Dave és fordítva. 

Szóval, mit tehetünk most csinálni? Már használta ezt a metaforát előtt A tálcák képviselő valamit. De kiderül, hogy a halom tálcák valójában demonstratív másik absztrakt adat type-- magasabb szintű adatszerkezetet hogy a végén a nap csak mint egy tömb vagy láncolt lista vagy valami több világi. De ez egy sokkal érdekesebb fogalmi fogalom. A halom, mint ezek tálcák itt Mather, általában az úgynevezett csak hogy-- verem. 

És az ilyen típusú adatstruktúra van két operations-- Van egy úgynevezett push hozzátéve valamit a verem, olyan, mintha egy másik tálca vissza a tetején a verem. És akkor pop, ami azt jelenti, hogy hogy a legfelső tálca ki. De mi kulcs egy halom, hogy az ez van ez a furcsa jellemző. Mivel az étkezőben személyzet átrendezése a tálcákat a következő étkezés, mi lesz igaz, hogy a diákok kölcsönhatásba adatstruktúrát? KÖZÖNSÉG: fognak pop egyszeri. DAVID MALAN: fognak pop egyszeri, remélhetőleg a tetején. Egyébként ez csak ilyen hülye menni egészen az aljára. Jobb? Az adatok szerkezete nem igazán teszi lehetővé hogy megragad az alsó tálca legalább könnyen. Szóval van ez a furcsa ingatlan egy halom hogy az utolsó tétel is lesz az első ki. És a számítógépes tudósok ez LIFO-- utolsóként, first out. És ez tényleg nem volna érdekes alkalmazásokat. Ez nem feltétlenül annyira nyilvánvaló, mint egyes mások, de lehet, sőt, hasznos lehet, és azt is, sőt, végre kell hajtani egy pár különböző módon. 

Tehát az egyik, és valóban, hadd , hogy ne merüljön bele. Csináljuk ezt helyette. Nézzük meg az egyik, hogy szinte az Ugyanez a gondolat, de ez egy kicsit igazságosabb. Jobb? Ha egy ilyen rajongó fiúk vagy lányok, nagyon szereti az Apple termékek és akkor ébredt fel 03:00 sorakoznak néhány bolt hogy a legújabb iPhone, akkor Lehet, hogy sorban állnak, mint ez. 

Most egy sor nagyon tudatosan neve. Ez egy sor, mert ott van néhány méltányosság hozzá. Jobb? Ez a fajta szar, ha már ért oda először az Apple Store de gyakorlatilag a legalsó tálca mert az Apple alkalmazottai akkor pop az utolsó ember, aki tényleg beállt a sorba. Így stack és sorokat, bár funkcionálisan ők milyen a same-- ez csak a gyűjtemény a források, ami fog növekedni, és ott van shrink-- ezt méltányosság szempont, hogy azt, legalábbis a valós világban, ahol a műveletek edz alapvetően eltérő. A stack-- sorban rather-- azt mondta, hogy két művelet: n sor és d sor. Vagy hívhatjuk őket tetszőleges számú dolog. De csak azt, hogy elfog az elképzelés, hogy az egyik hozzáadása és végül egy kivonva. 

Most a motorháztető alatt, mind a verem és a sor lehet valósítani, hogyan? Mi nem megyünk bele a kódját mert a magasabb szint ötlet valami sokkal nyilvánvalóbb. Úgy értem, az emberek mit csinál? Ha én vagyok az első, aki az Apple Tárolja és ez a bejárati ajtó, Tudod, én fogok itt állni. És a következő személy fog állni itt. És a következő személy fog állni itt. Tehát mi adatstruktúra alkalmas arra, hogy a sorban? 

KÖZÖNSÉG: A sor. DAVID MALAN: Nos, a sorban. Persze. Mi más? 

KÖZÖNSÉG: A láncolt lista. 

DAVID MALAN: A kapcsolt bejegyzés tudna megvalósítani. És egy láncolt lista hasznos, mert akkor nőhet önkényesen hosszú, szemben hogy miután néhány fix szám az emberek a boltban. De talán egy meghatározott számú helyek jogos. Mert ha csak mint a 20 iPhone az első napon, talán csak meg kell egy tömb mérete 20. képviseli a sort, amely csak mondani most ha egyszer elkezd beszélni ezekről a magasabb szintű problémák akkor végre azt bármilyen számos módon. És talán csak fog egy kompromisszum a térben és időben vagy csak a saját kódját összetettségét. 

Mi a helyzet a stack? Nos, egy halom, láttuk is Lehet, hogy csak ezek a tálcákat. És akkor végre ezt a tömböt. De egy bizonyos ponton, ha használja egy sor, mi fog történni, hogy a tálcák akarsz letenni? Rendben van. Te csak akkor fog tud menni olyan magas. És azt hiszem, a Mather ők valójában süllyesztve, hogy a nyitás. Szóval valóban, ez majdnem mint Mather használ tömb rögzített méretű, mert akkor csak illik annyi tálcák hogy nyitás a fal lent emberek térde. És hogy lehet azt mondta, hogy egy tömb, de minden bizonnyal végre, hogy a általában egy láncolt lista. 

Nos, mi a helyzet a másik adatszerkezet? Hadd húzza fel egy másik vizuális itt. Valami ilyesmi hogyan körülbelül ez itt? Miért lehet ez hasznos, hogy nem valami olyan divatos, mint a Trie, amely láttuk már ezeket a nagyon széles csomópontok, amelyek mindegyike egy tömb? De mi van, ha nem teszünk valamit még egyszerűen, mint egy régi iskola családfa, mindegyik, melynek csúcsai itt csak tárolja a számot. Ahelyett, hogy egy név vagy egy leszármazott csak tárolja a számot, mint ez. 

Nos, a zsargon, amit használni adatszerkezetek egyszerre próbál és a fák, ahol a Trie, újra, Csak akinek csomópontok tömbök, még, amit esetleg használni iskolában ha tett egy család tree-- levelek és a gyökér A fa és a gyermekek, a szülő és a testvérek cikke. És talán végre egy fa, például, mivel egyszerűen, mint ez. A fa, mint ha ez a csomópont, az egyik Ezekben a körökben, hogy van egy szám, ez nem megy, hogy egy mutató, hanem kettő. És amint hozzá Egy másik mutató, akkor valójában most, hogy sort A két-dimenziós adat struktúrákat a memóriában. Sok, mint egy két dimenziós tömb, akkor van a fajta két-dimenziós kapcsolódó listák hanem azok, hogy követik a mintát ahol nincs ciklus. Ez valóban egy fa egy nagyszülő egészen ide, majd néhány szülő és gyermek unokák és dédunokája. és így tovább. 

De ami igazán ügyes erről is, Csak ugratni egy kis kódot, visszahívás rekurzió -tól egy kicsit vissza, amely írsz egy függvényt, amely saját magát hívja meg. Ez egy csodás lehetőség végrehajtani valamit mint rekurzió, mert úgy ez. 

Ez egy fa. És én már egy kicsit, hogy hogyan anális Tettem az egész az utcára. Olyannyira, hogy van egy különleges name-- bináris kereső fába. Most hallottam a bináris keresés, de te is visszafelé ebből a dolog nevét? Mi az a minta, hogyan ki az egész ebbe a fát? Ez nem önkényes. Van néhány mintát. Igen. 

KÖZÖNSÉG: kisebb a bal oldalon. 

DAVID MALAN: Igen. Kisebbek a bal oldalon. Nagyobbak, a jobb oldalon. Úgy, hogy igaz az állítás a szülő nagyobb, mint a bal fia, de kisebb, mint a jobb fia. És ez önmagában még rekurzív verbális definíció mert akkor lehet alkalmazni, hogy Ugyanez a logika, hogy minden csomópont és csak fenéktermék ki, a bázis esetben, ha azt lesz, ha bejön az egyik a levelek, hogy úgy mondjam, ahol a szabadság nem a gyerekek tovább. 

Most hogyan lehet megtalálni a szám a 44? Akkor indulna meg a gyökér, és azt mondják, hm. 55. nem 44. Tehát nem akarok menni jobbra vagy akarom, hogy menjen balra? Nos, nyilvánvalóan akarsz menni balra. És ez így olyan, mint a telefon könyv például a bináris keresés általában. De mi azt végrehajtó most egy kicsit dinamikusabban mint egy tömböt is lehetővé teszik. És valóban, ha meg akarom nézni A kód első pillantásra biztos. Úgy néz ki, mint egy csomó vonalak. De ez csodálatosan egyszerű. Ha azt szeretnénk, hogy végre egy függvény hívott keresés melynek célja az életben hogy keressen egy érték mint n egy egész szám, és te telt el egy pointer-- a mutatót a csomópont a gyökér, inkább az a fa, amely elérheti minden mást, észre, hogy egyenesen akkor végre a logika. Ha a fa null, nyilvánvalóan nincs ott. Nézzük csak vissza hamis. Jobb? Ha adja le semmit, nincs ott semmi. 

Más, ha n értéke kisebb, mint fa arrow n-- most nyíl n, emlékszem mi vezetett szuper röviden a minap, és ez csak azt jelenti, de a hivatkozás mutató, és nézd meg a területen az úgynevezett n. Tehát ez azt jelenti, hogy ott és nézd meg a területen az úgynevezett n. Tehát, ha n értéke maga adott, kevésbé mint az érték a fák egész, ahol akarsz menni? Balra. 

Így észre a rekurziót. Én returning-- nem igaz. Nem hamis. Én vissza függetlenül a válasz ez egy felhívás a magam, múló egy n újra, ami felesleges, de mi most kicsit más? Hogy vagyok, hogy a probléma kisebb? Én halad, mint a második érv, nem a gyökér a fa, de a bal gyermek ebben az esetben. Szóval halad a bal oldali gyermek. 

Közben, ha n értéke nagyobb, mint a csomópont Én jelenleg vizsgálja, Keresem a jobb oldalon. Különben, ha a fa nem nulla, és ha az elem nem balra és ez nem az a helyes, mi csodálatosan a helyzet? Már valóban megtalálható a csomópont kérdés, és ezért vissza igaz. 

Így már csak karcos a felület most néhány ilyen adatszerkezetek. A probléma meg öt te fogsz vizsgálja ezeket még tovább, és akkor meg kell adni a tervezési választás, hogyan szeretné ezt. Azt szeretném, hogy megállapítsa, csak egy 30 másodperces teaser mi vár a jövő héten, és azon túl. 

Ahogy begin-- szerencsére lehet, hogy think-- az átmenet lassan a világ a C és az alacsonyabb szintű végrehajtásának részleteit, Egy olyan világban, ahol tudunk venni a biztosra, hogy valaki másnak végül végre ezeket az adatokat struktúrák nekünk, és kezdjük megérteni a valós olyan végrehajtási webes programok és weboldalak általában és az is nagyon biztonsági látszat, hogy mi már csak megkezdte a felszínét. Itt van, mi vár ránk a napokban. 

[VIDEO LEJÁTSZÁS] 

-Ő Jött egy üzenet, a jegyzőkönyv minden saját. Azért jött, hogy a világ a kegyetlen tűzfalak, útválasztók nemtörődöm, és veszélyek sokkal rosszabb, mint a halál. Ő gyors. Ő erős. Ő TCP / IP, és van neki a címet. "Warriors of a neten." [END VIDEO LEJÁTSZÁS] DAVID MALAN: jön a jövő héten. Majd meglátjuk, akkor majd. [VIDEO LEJÁTSZÁS] -És Most, "Deep Thoughts" a Daven Farnham. -David Mindig indul előadást, "Rendben." Miért ne, "Itt a megoldás hogy ezen a héten a probléma set " vagy "Mi így mindannyian egy A?" [Nevet] [END VIDEO LEJÁTSZÁS]