1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [Zenelejátszó] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID MALAN: Ez CS50. 5 00:00:14,010 --> 00:00:18,090 És ez mind a kezdő és a end-- mint literally-- majdnem vége 6 00:00:18,090 --> 00:00:18,825 A hét hat. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Azt gondoltam megosztani a kicsit a móka tény. 9 00:00:22,640 --> 00:00:25,370 Én ezt húzta fel a Az elmúlt félév adatai beállítva. 10 00:00:25,370 --> 00:00:29,710 Talán emlékeznek, hogy arra kérünk, minden p szereplő űrlapot, ha már figyelte az interneten 11 00:00:29,710 --> 00:00:31,580 vagy ha már részt vesz. 12 00:00:31,580 --> 00:00:33,020 És itt van az adat. 13 00:00:33,020 --> 00:00:34,710 Szóval ma nagyon is kiszámítható. 14 00:00:34,710 --> 00:00:37,126 De azt akartuk, hogy kiad egy kicsit Az idő veled mégis. 15 00:00:37,126 --> 00:00:40,599 Bárki szeretné sejtjük, hogy miért ezt a gráf olyan csipkézett, akár lefelé, akár lefelé, 16 00:00:40,599 --> 00:00:41,265 így folyamatosan? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Mit az egyes csúcsok és hullámvölgyek képviselnek? 19 00:00:45,130 --> 00:00:46,005 >> KÖZÖNSÉG: [hallható] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID MALAN: Valóban. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 És még szórakoztatóan, isten ments, tartunk egy előadást a péntek 24 00:00:55,480 --> 00:00:58,960 elején a félév, ez az, amit látni történni. 25 00:00:58,960 --> 00:01:03,430 Így ma, amikor veszünk egy kicsit többet adatszerkezeteket. 26 00:01:03,430 --> 00:01:06,660 És, hogy még több szilárd mentális modellt problémák öt, 27 00:01:06,660 --> 00:01:07,450 ami most ki. 28 00:01:07,450 --> 00:01:10,817 Hibát, ahol fogunk kézzel egy szöveges fájlt valamilyen 100000 29 00:01:10,817 --> 00:01:12,650 plusz angol szavak, és Ön megy, hogy 30 00:01:12,650 --> 00:01:17,770 hogy kitaláljuk, hogyan lehet ügyesen betöltésére a memóriába, a RAM-ba, a néhány adat 31 00:01:17,770 --> 00:01:19,330 szerkezet, amelyet választott. 32 00:01:19,330 --> 00:01:22,470 >> Most az egyik ilyen adat struktúra is, de talán nem kell, 33 00:01:22,470 --> 00:01:25,630 A meglehetősen egyszerű láncolt lista, amit be utoljára. 34 00:01:25,630 --> 00:01:29,220 És egy láncolt lista volt legalább egyik előnye tömb. 35 00:01:29,220 --> 00:01:32,096 Mi az az egyik előnye, hogy láncolt lista vitathatatlanul? 36 00:01:32,096 --> 00:01:32,950 >> KÖZÖNSÉG: beillesztése. 37 00:01:32,950 --> 00:01:33,908 >> DAVID MALAN: beillesztése. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Mit jelent ez? 40 00:01:35,196 --> 00:01:37,872 >> KÖZÖNSÉG: Bárhol mentén A lista [hallható]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID MALAN: Jó. 42 00:01:38,770 --> 00:01:42,090 Szóval lehet beszúrni egy elemet, ahol azt szeretné, a közepén a lista 43 00:01:42,090 --> 00:01:45,490 anélkül, hogy shuffle semmit, amely arra a következtetésre jutottunk, hogy a válogatás 44 00:01:45,490 --> 00:01:47,630 viták, nem feltétlenül jó dolog, 45 00:01:47,630 --> 00:01:51,200 mert időt vesz igénybe, hogy valóban mozog az összes ilyen emberre balra vagy jobbra. 46 00:01:51,200 --> 00:01:55,540 És így egy láncolt lista, akkor csak osztja a malloc, egy új csomópont, 47 00:01:55,540 --> 00:01:58,385 majd frissítse pár pointers-- kettő, három művelet max-- 48 00:01:58,385 --> 00:02:01,480 és képesek vagyunk slot valaki bárhol a listában. 49 00:02:01,480 --> 00:02:03,550 >> Mi más volt előnyös egy láncolt lista? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Igen? 52 00:02:05,659 --> 00:02:06,534 >> KÖZÖNSÉG: [hallható] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID MALAN: Tökéletes. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Tökéletes. 57 00:02:11,090 --> 00:02:12,070 Nagyon dinamikus. 58 00:02:12,070 --> 00:02:15,100 És, hogy te nem követnek, előre, bizonyos rögzített mérettel 59 00:02:15,100 --> 00:02:18,750 darab memória, mint akkor kellett volna hogy egy sor, a fejjel, amely 60 00:02:18,750 --> 00:02:22,455 hogy meg lehet kiosztani csomópontok csak kereslet ezáltal kizárólag annyi helyet 61 00:02:22,455 --> 00:02:23,330 ahogy valójában szüksége van. 62 00:02:23,330 --> 00:02:26,830 Ezzel szemben egy sor, lehet, hogy véletlenül osztja túl kevés. 63 00:02:26,830 --> 00:02:28,871 És akkor ez csak megy hogy a fájdalom a nyak 64 00:02:28,871 --> 00:02:32,440 átcsoportosítása egy új, nagyobb tömb, másolja minden felett, szabad a régi tömb, 65 00:02:32,440 --> 00:02:33,990 majd mozgassa a dolgára. 66 00:02:33,990 --> 00:02:37,479 Vagy ami még rosszabb, lehet, hogy osztja út több memóriát, mint amennyire valóban szükség van, 67 00:02:37,479 --> 00:02:40,520 és így fogsz egy nagyon gyéren lakott tömb, hogy úgy mondjam. 68 00:02:40,520 --> 00:02:44,350 >> Így a kapcsolt listát ad e előnyei dinamizmus és rugalmasság 69 00:02:44,350 --> 00:02:46,080 A beszúrások és törlések. 70 00:02:46,080 --> 00:02:48,000 De biztosan kell lennie egy árat fizetett. 71 00:02:48,000 --> 00:02:50,000 Sőt, az egyik témája tárni kvíz nulla 72 00:02:50,000 --> 00:02:52,430 volt egy pár a kompromisszumok láttunk eddig. 73 00:02:52,430 --> 00:02:56,161 Tehát mi az a kifizetett ár vagy a hátránya, a láncolt lista? 74 00:02:56,161 --> 00:02:56,660 Igen. 75 00:02:56,660 --> 00:02:57,560 >> KÖZÖNSÉG: Nem véletlen hozzáférés. 76 00:02:57,560 --> 00:02:58,809 >> DAVID MALAN: Nem véletlen hozzáférés. 77 00:02:58,809 --> 00:02:59,540 De kit érdekel? 78 00:02:59,540 --> 00:03:01,546 Véletlen hozzáférés nem hangzik meggyőző. 79 00:03:01,546 --> 00:03:02,421 >> KÖZÖNSÉG: [hallható] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID MALAN: Pontosan. 82 00:03:05,740 --> 00:03:07,580 Ha azt szeretné, hogy egy bizonyos algorithm-- 83 00:03:07,580 --> 00:03:10,170 és hadd valójában javasol bináris keresés különösen, ami 84 00:03:10,170 --> 00:03:12,600 az egyik általunk használt jó bit-- ha nincs közvetlen elérésű, 85 00:03:12,600 --> 00:03:15,516 Ön nem tudja, hogy egyszerű számtani találni, mint a középső elem 86 00:03:15,516 --> 00:03:16,530 és ugrás jobbra hozzá. 87 00:03:16,530 --> 00:03:20,239 Meg kell kezdeni, hanem az első elem és lineárisan kereshetőek bal 88 00:03:20,239 --> 00:03:22,780 jobbra, ha meg akarja találni a középső vagy bármely más elemet. 89 00:03:22,780 --> 00:03:24,410 >> KÖZÖNSÉG: Valószínűleg ez több tárhelyet. 90 00:03:24,410 --> 00:03:25,040 >> DAVID MALAN: úgy több memóriát. 91 00:03:25,040 --> 00:03:27,464 Hol van az a kiegészítő költség jön a memória? 92 00:03:27,464 --> 00:03:28,339 >> KÖZÖNSÉG: [hallható] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID MALAN: Pontosan. 95 00:03:33,440 --> 00:03:35,679 Ebben az esetben itt, mi volt láncolt lista egészek, 96 00:03:35,679 --> 00:03:37,470 és mégis mi duplázás a memória mennyisége 97 00:03:37,470 --> 00:03:39,680 szükségünk van az is tárolja ezeket a mutatókat. 98 00:03:39,680 --> 00:03:42,090 Most kisebb a nagy üzlet, mint A struktúrákat kap nagyobb 99 00:03:42,090 --> 00:03:45,320 és te tárolása nem szám, hanem talán egy diák, vagy valamilyen más tárgy. 100 00:03:45,320 --> 00:03:46,880 De a lényeg biztosan marad. 101 00:03:46,880 --> 00:03:49,421 És így számos műveletek A kapcsolt listák hívták 102 00:03:49,421 --> 00:03:50,570 voltak nagy O n-- lineáris. 103 00:03:50,570 --> 00:03:54,730 Dolgok, mint a beillesztés vagy keresés vagy törlés esetén egy elem 104 00:03:54,730 --> 00:03:57,720 történetesen a legvégén A lista legyen az rendezve, vagy sem. 105 00:03:57,720 --> 00:04:01,167 >> Néha lehet, hogy szerencsés és így alacsonyabb korlátokat e műveletek 106 00:04:01,167 --> 00:04:04,250 is lehet konstans időt, ha te vagy mindig néztem az első elem, 107 00:04:04,250 --> 00:04:05,070 például. 108 00:04:05,070 --> 00:04:09,360 De végül is, megígértük hogy elérjék a Szent Grál 109 00:04:09,360 --> 00:04:12,630 adatstruktúrák, vagy néhány közelítés cikkére, 110 00:04:12,630 --> 00:04:14,290 útján konstans idő. 111 00:04:14,290 --> 00:04:17,579 Találunk elemek vagy add elemek vagy elemek eltávolításához a listából? 112 00:04:17,579 --> 00:04:19,059 Meglátjuk, elég hamar. 113 00:04:19,059 --> 00:04:21,100 És kiderül, hogy az egyik A mechanizmusok vagyunk 114 00:04:21,100 --> 00:04:23,464 fog kezdeni használni ma, évi felhasználás p meg öt, 115 00:04:23,464 --> 00:04:24,630 valójában nagyon ismerős. 116 00:04:24,630 --> 00:04:27,430 Például, ha ez egy csomó A vizsgálat könyvek, amelyek mindegyike 117 00:04:27,430 --> 00:04:29,660 egy hallgató az első Keresztnév és vezetéknév rajta, 118 00:04:29,660 --> 00:04:31,820 és én értük tól a végén egy vizsga, 119 00:04:31,820 --> 00:04:33,746 és ezek mind nagyon sok véletlenszerű sorrendben, 120 00:04:33,746 --> 00:04:36,370 és azt akarjuk, hogy megy a válogatás ezeket a vizsgákat úgy, hogy ha osztályozni 121 00:04:36,370 --> 00:04:38,661 ez csak egy sokkal könnyebb és gyorsabban átadja nekik vissza 122 00:04:38,661 --> 00:04:40,030 a diákok betűrendben. 123 00:04:40,030 --> 00:04:42,770 Milyen lenne az ösztönök lesz egy halom vizsgák, mint ez? 124 00:04:42,770 --> 00:04:45,019 >> Nos, ha te, mint én, akkor Lehet látni, hogy ez m, 125 00:04:45,019 --> 00:04:48,505 így fogom egyfajta E szándék, ha ez az asztalra vagy a padlóra, ahol a 126 00:04:48,505 --> 00:04:50,650 Én terjed dolgok out-- vagy a tömb really-- 127 00:04:50,650 --> 00:04:52,210 Talán fel minden asszony ott. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Itt egy A. Szóval talán fel a Mivel itt. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Itt egy újabb A. megyek tenni, hogy itt van. 132 00:04:57,980 --> 00:05:02,490 Itt egy Z. Itt egy másik, M. és így Lehet kezdeni a kupac, mint ez. 133 00:05:02,490 --> 00:05:06,620 És akkor talán megyek később és valami nagyon nitpicky-ly sort 134 00:05:06,620 --> 00:05:07,710 az egyes cölöpök. 135 00:05:07,710 --> 00:05:11,300 De a lényeg az, hogy én nézne A bemenet, hogy én vagyok balkezes 136 00:05:11,300 --> 00:05:14,016 és azt, hogy néhány kiszámítása határozat alapján, hogy a bemeneti. 137 00:05:14,016 --> 00:05:15,640 Ha kezdődik, tedd oda. 138 00:05:15,640 --> 00:05:18,980 Ha kezdődik Z, tedd át ott, és minden között. 139 00:05:18,980 --> 00:05:22,730 >> Tehát ez egy olyan technika, ami általánosan ismert hashing-- H-A-S-H-- 140 00:05:22,730 --> 00:05:26,550 ami általában azt jelenti, hogy a bemenet és használ, hogy input kiszámítása 141 00:05:26,550 --> 00:05:30,940 egy értéket, általában egy számot, és hogy szám a mutató egy tároló 142 00:05:30,940 --> 00:05:32,260 konténer, mint egy tömb. 143 00:05:32,260 --> 00:05:35,490 Más szóval, talán van egy hash függvény, mint én a fejemben, 144 00:05:35,490 --> 00:05:37,940 hogy ha látom, valaki név aki kezdődik A, 145 00:05:37,940 --> 00:05:40,190 Fogom feltérképezni, hogy a nullára a fejemben. 146 00:05:40,190 --> 00:05:44,160 És ha látom, hogy valaki a Z, én vagyok majd feltérképezni, hogy a 25 a fejemben 147 00:05:44,160 --> 00:05:46,220 majd tegye, hogy a Az utolsó nagy halom. 148 00:05:46,220 --> 00:05:50,990 >> Most, ha úgy gondolja, hogy nem az agyam hanem egy C program, milyen számokat tudott 149 00:05:50,990 --> 00:05:53,170 támaszkodik annak elérése, hogy ugyanazt az eredményt? 150 00:05:53,170 --> 00:05:55,594 Más szóval, ha volt az ASCII karakter A, 151 00:05:55,594 --> 00:05:57,510 Hogyan határozzák meg mit vödröt tedd? 152 00:05:57,510 --> 00:05:59,801 Valószínűleg nem akar tedd be 65 vödör, ami 153 00:05:59,801 --> 00:06:01,840 lenne, mint ott minden ok nélkül. 154 00:06:01,840 --> 00:06:04,320 Hol akarod, hogy egy tekintve ASCII érték? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Hol akarod tenni annak ASCII érték, hogy dolgozzon ki egy intelligensebb vödör 157 00:06:08,920 --> 00:06:09,480 hogy betette? 158 00:06:09,480 --> 00:06:10,206 >> KÖZÖNSÉG: Mínusz A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID MALAN: Igen. 160 00:06:10,956 --> 00:06:13,190 Tehát mínusz A mínusz különösen, ha ez a 65 161 00:06:13,190 --> 00:06:18,240 a főváros A. Or 98 ha ez egy kisbetűs a. 162 00:06:18,240 --> 00:06:21,300 És így, amely lehetővé teszi számunkra, hogy nagyon egyszerűen és nagyon egyszerű számtani 163 00:06:21,300 --> 00:06:23,260 tenni valamit egy vödörbe, mint ezt. 164 00:06:23,260 --> 00:06:26,010 Így kiderül, valójában nem ezt is még a vetélkedők. 165 00:06:26,010 --> 00:06:29,051 >> Szóval lehet, hogy emlékszem te köröztek a tanítás fickó nevét a borítón. 166 00:06:29,051 --> 00:06:32,270 És a TF nevét szerveztek ezekbe oszlopok betűrendben, 167 00:06:32,270 --> 00:06:34,400 nos, akár hiszed, akár nem, amikor mind a 80 plusz nekünk 168 00:06:34,400 --> 00:06:37,800 összejöttünk a másik éjszaka fokozat, az utolsó lépés a mi osztályozó folyamat 169 00:06:37,800 --> 00:06:41,830 az, hogy a hash vetélkedők egy nagy hely a padló, a [hallható] 170 00:06:41,830 --> 00:06:45,110 és a laikus mindenki vetélkedők ki pontosan sorrendben TF 171 00:06:45,110 --> 00:06:47,700 nevek a fedelet, mert akkor sokkal könnyebb számunkra 172 00:06:47,700 --> 00:06:51,290 keresgélni, hogy a lineáris keresés vagy valamilyen okosság 173 00:06:51,290 --> 00:06:54,050 a TF, hogy megtalálja a vagy diákjai "vetélkedők. 174 00:06:54,050 --> 00:06:56,060 >> Szóval ez az ötlet, hasítás hogy látni fogja az 175 00:06:56,060 --> 00:07:00,520 elég erős valójában elég közhely és nagyon intuitív, 176 00:07:00,520 --> 00:07:03,000 hasonlóan talán felosztani és uralkodj volt hét nulla. 177 00:07:03,000 --> 00:07:05,250 Azt várom, hogy a gyors hackathon Egy pár évvel ezelőtt. 178 00:07:05,250 --> 00:07:08,040 Ez Zamyla és egy pár egyéb személyzet üdvözlő diákok 179 00:07:08,040 --> 00:07:09,030 ahogy jöttek. 180 00:07:09,030 --> 00:07:12,680 És volt egy csomó összecsukható táblázatokban névcímkékkel. 181 00:07:12,680 --> 00:07:15,380 És mi volt a neve szervezett címkék és mint a mint ott 182 00:07:15,380 --> 00:07:16,690 és a Zs ott. 183 00:07:16,690 --> 00:07:20,350 És így az egyik a TF nagyon okosan írta ezt az utasítást 184 00:07:20,350 --> 00:07:21,030 a nap. 185 00:07:21,030 --> 00:07:24,480 És a 12. héten a félév e minden tökéletesen érthető és mindenki 186 00:07:24,480 --> 00:07:25,310 tudta, mit kell tennie. 187 00:07:25,310 --> 00:07:27,900 De akkor már bármikor sorban áll ugyanúgy, 188 00:07:27,900 --> 00:07:30,272 te végrehajtása ugyanezt az elvet a hash. 189 00:07:30,272 --> 00:07:31,730 Szóval hivatalossá, hogy egy kicsit. 190 00:07:31,730 --> 00:07:32,890 Itt van egy tömb. 191 00:07:32,890 --> 00:07:36,820 Ez húzott, hogy egy kicsit széles csak ábrázolni, vizuálisan, 192 00:07:36,820 --> 00:07:38,920 hogy talán fel húrok valami ilyesmi. 193 00:07:38,920 --> 00:07:41,970 És ez tömb nyilvánvalóan teljes mérete 26. 194 00:07:41,970 --> 00:07:43,935 És a dolog az úgynevezett táblázat önkényesen. 195 00:07:43,935 --> 00:07:48,930 De ez csak egy művész kiadatás amit egy hash tábla lehet. 196 00:07:48,930 --> 00:07:52,799 >> Tehát egy hash tábla most fog egy magasabb szintű adatszerkezet. 197 00:07:52,799 --> 00:07:54,840 Végén a nap vagyunk arról, hogy látni, hogy 198 00:07:54,840 --> 00:07:58,700 végre tudják hajtani a hash tábla, amely sokkal, mint a check-in sorban 199 00:07:58,700 --> 00:08:02,059 egy hackathon hasonlóan ez táblázat a rendezés vizsga könyveket. 200 00:08:02,059 --> 00:08:03,850 De egy hash tábla fajta ez a magas szintű 201 00:08:03,850 --> 00:08:08,250 koncepció, hogy jönne egy tömböt a motorháztető alatt hajtják végre, 202 00:08:08,250 --> 00:08:11,890 vagy jönne egy hosszú listát, vagy akár talán más adatszerkezeteket. 203 00:08:11,890 --> 00:08:15,590 És most, hogy a vevő theme-- néhány ilyen alapvető összetevők 204 00:08:15,590 --> 00:08:18,310 mint egy tömb, és az épület blokk most hossza lista 205 00:08:18,310 --> 00:08:21,740 és látta, hogy mit tudunk építeni a tetején e, mint összetevők 206 00:08:21,740 --> 00:08:26,550 egy recept, így egyre több és több érdekes és hasznos a végleges eredmények. 207 00:08:26,550 --> 00:08:28,680 >> Tehát a hash tábla talán végrehajtása 208 00:08:28,680 --> 00:08:32,540 memória képileg, mint ez, de hogyan lehet valójában kódolva fel? 209 00:08:32,540 --> 00:08:33,789 Nos, talán csak ez. 210 00:08:33,789 --> 00:08:38,270 Ha a kapacitást minden sapkák, csak néhány constant-- például 26, 211 00:08:38,270 --> 00:08:42,030 26 betűi alphabet-- Lehet hívni a változó asztal, 212 00:08:42,030 --> 00:08:45,630 és talán azt állítják, hogy megyek tedd char csillagok ott, vagy string. 213 00:08:45,630 --> 00:08:49,880 Szóval ez olyan egyszerű, mint ez, ha szeretnénk végrehajtani a hash tábla. 214 00:08:49,880 --> 00:08:51,490 És mégis, ez tényleg csak egy tömb. 215 00:08:51,490 --> 00:08:53,198 De ismétlem, a hash táblázat most mit fogunk 216 00:08:53,198 --> 00:08:57,470 hívni egy absztrakt adattípus ez csak egyfajta fogalmi rétegezés tetejére 217 00:08:57,470 --> 00:09:00,780 valami több világi most, mint egy tömb. 218 00:09:00,780 --> 00:09:02,960 >> Most, hogy megyünk körülbelül problémák megoldása? 219 00:09:02,960 --> 00:09:06,980 Nos, korábban az volt a luxus Az, hogy elég hely van asztal 220 00:09:06,980 --> 00:09:09,460 így tudtam tenni a vetélkedők bárhol akartam. 221 00:09:09,460 --> 00:09:10,620 Ahogy az így megy itt. 222 00:09:10,620 --> 00:09:12,100 Zs is megy itt. 223 00:09:12,100 --> 00:09:13,230 Ms is megy itt. 224 00:09:13,230 --> 00:09:14,740 Aztán volt egy kis extra helyet. 225 00:09:14,740 --> 00:09:18,740 De ez egy kicsit cheat jog most, mert ez a táblázat, ha én tényleg 226 00:09:18,740 --> 00:09:22,720 gondolt rá, mint egy sor, csak lesz a bizonyos rögzített mérettel. 227 00:09:22,720 --> 00:09:25,380 >> Szóval technikailag, ha kihúzom egy másik diák kvíz 228 00:09:25,380 --> 00:09:28,490 és nézd meg, ó, ez a személy neve kezdődik egy A is, 229 00:09:28,490 --> 00:09:30,980 Valahogy szeretnék tedd oda. 230 00:09:30,980 --> 00:09:34,740 De amint én tettem oda, ha ez a táblázat valóban tömbjét képviseli, 231 00:09:34,740 --> 00:09:37,840 Megyek is érvényesítendő vagy felülírás aki ezt diák kvíz. 232 00:09:37,840 --> 00:09:38,340 Jobb? 233 00:09:38,340 --> 00:09:41,972 Ha ez egy tömb, csak egy dolog lehet megy minden ilyen sejtek vagy elemekkel. 234 00:09:41,972 --> 00:09:43,680 És én ilyen van válogathat. 235 00:09:43,680 --> 00:09:45,735 >> Most korábban valahogy csalt és tette ezt vagy azt 236 00:09:45,735 --> 00:09:47,526 csak egyfajta egymásra őket egymás felett. 237 00:09:47,526 --> 00:09:49,170 De ez nem fog repülni kódot. 238 00:09:49,170 --> 00:09:52,260 Szóval, ha tudtam tenni a második hallgató, akinek a neve 239 00:09:52,260 --> 00:09:54,964 az A, ha minden volt ez álló asztal hely? 240 00:09:54,964 --> 00:09:57,880 És én is használtam három slot, és úgy néz ki, mintha csak egy pár mások. 241 00:09:57,880 --> 00:09:58,959 Mit lehet tenni? 242 00:09:58,959 --> 00:09:59,834 KÖZÖNSÉG: [hallható] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID MALAN: Igen. 245 00:10:01,315 --> 00:10:02,370 Lehet, hogy most csak tartsa egyszerű. 246 00:10:02,370 --> 00:10:02,660 Jobb? 247 00:10:02,660 --> 00:10:04,243 Ez nem illik, ahol szeretnék, hogy tedd. 248 00:10:04,243 --> 00:10:07,450 Így fogok tenni, hogy technikailag ahol a B menne. 249 00:10:07,450 --> 00:10:09,932 Most, persze, kezdek festeni magam egy sarokba. 250 00:10:09,932 --> 00:10:11,890 Ha kapok egy diák akinek a neve valójában B, 251 00:10:11,890 --> 00:10:14,840 B most fog mozgatni egy kicsit előre, mivel megtörténhet, igen, 252 00:10:14,840 --> 00:10:17,530 ha ez a B, most már megy itt. 253 00:10:17,530 --> 00:10:20,180 >> És ez nagyon gyorsan veszélyessé váló, 254 00:10:20,180 --> 00:10:23,850 de ez egy technika, amely ténylegesen nevezik lineáris tapintás, 255 00:10:23,850 --> 00:10:26,650 amely csak úgy a tömb, hogy a vonal mentén. 256 00:10:26,650 --> 00:10:29,680 És csak ilyen szonda vagy vizsgáljuk meg az elérhető elemek 257 00:10:29,680 --> 00:10:31,360 keres egy szabad hely. 258 00:10:31,360 --> 00:10:34,010 És amint megtalálni az egyik, akkor dobja el oda. 259 00:10:34,010 --> 00:10:38,390 >> Most, az ár fordítottak mert ez a megoldás, az mi? 260 00:10:38,390 --> 00:10:41,300 Van egy fix méretű tömb, és behelyezésekor nevek 261 00:10:41,300 --> 00:10:44,059 bele, legalábbis kezdetben, mi a menetideje behelyezés 262 00:10:44,059 --> 00:10:46,350 hozataláért a diákok vetélkedők a megfelelő kanalak? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O, mi? 265 00:10:50,002 --> 00:10:51,147 >> KÖZÖNSÉG: n. 266 00:10:51,147 --> 00:10:52,480 DAVID MALAN: Azt hallottam, nagy O n. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Nem igaz. 269 00:10:54,300 --> 00:10:56,490 De majd ugratni egymástól miért csak egy pillanat. 270 00:10:56,490 --> 00:10:57,702 Mi más lehet? 271 00:10:57,702 --> 00:10:58,755 >> KÖZÖNSÉG: [hallható] 272 00:10:58,755 --> 00:11:00,380 DAVID MALAN És hadd csinálni vizuálisan. 273 00:11:00,380 --> 00:11:04,720 Tegyük fel, hogy ez a levél S. 274 00:11:04,720 --> 00:11:05,604 >> KÖZÖNSÉG: Ez az egyik. 275 00:11:05,604 --> 00:11:06,520 DAVID MALAN: Ez az egyik. 276 00:11:06,520 --> 00:11:06,710 Jobb? 277 00:11:06,710 --> 00:11:08,950 Ez egy tömb, amely azt jelenti, hogy van véletlen hozzáféréssel. 278 00:11:08,950 --> 00:11:11,790 És ha arra gondolunk, ez a nulla legyen, és ezt a 25, 279 00:11:11,790 --> 00:11:13,800 és rájövünk arra, Ó, itt van a bemenet S, 280 00:11:13,800 --> 00:11:16,350 Én biztosan konvertálni S egy ASCII karakter, 281 00:11:16,350 --> 00:11:18,540 a megfelelő számot nulla és 25 282 00:11:18,540 --> 00:11:20,910 majd azonnal tedd, ahova tartozik. 283 00:11:20,910 --> 00:11:26,120 >> Persze, amint jutok el a második személy, aki neve A, B vagy C 284 00:11:26,120 --> 00:11:29,300 végül, ha én is használtam a lineáris tapintás, mint a megoldás, 285 00:11:29,300 --> 00:11:31,360 a menetideje behelyezése a legrosszabb esetben 286 00:11:31,360 --> 00:11:33,120 valóban fog ruházni abba, hogy mi? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 És én hallottam itt helyesen korán. 289 00:11:36,045 --> 00:11:36,920 KÖZÖNSÉG: [hallható] 290 00:11:36,920 --> 00:11:41,620 DAVID MALAN: Tehát n valóban egyszer van egy elég nagy adathalmaz. 291 00:11:41,620 --> 00:11:44,410 Így, egyrészt, ha A tömb elég nagy 292 00:11:44,410 --> 00:11:48,287 és az adatok kevés elég, hogy ezt a gyönyörű időben állandó. 293 00:11:48,287 --> 00:11:50,620 De amint elkezd egyre több és több elemet, 294 00:11:50,620 --> 00:11:53,200 és csak statisztikailag kapsz több embert a levél 295 00:11:53,200 --> 00:11:56,030 A mint a neve vagy a levél B, a potenciálisan 296 00:11:56,030 --> 00:11:57,900 ruházzák át valami lineáris. 297 00:11:57,900 --> 00:11:59,640 Így nem egészen tökéletes. 298 00:11:59,640 --> 00:12:00,690 Így tudnánk jobban csinálni? 299 00:12:00,690 --> 00:12:03,210 >> Nos, mi volt a megoldás, amikor hazafelé 300 00:12:03,210 --> 00:12:06,820 szeretné, hogy több mint dinamizmus olyasmi, mint egy tömb megengedett? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 KÖZÖNSÉG: [hallható] 303 00:12:08,960 --> 00:12:10,030 DAVID MALAN: Mit mutatunk be? 304 00:12:10,030 --> 00:12:10,530 Igen. 305 00:12:10,530 --> 00:12:11,430 Tehát a láncolt lista. 306 00:12:11,430 --> 00:12:14,430 Nos, lássuk, mi a kapcsolt lista talán nem nekünk helyette. 307 00:12:14,430 --> 00:12:17,630 Nos, hadd javaslom, hogy felhívni a kép az alábbiak szerint. 308 00:12:17,630 --> 00:12:19,620 Most ez egy másik kép egy példa 309 00:12:19,620 --> 00:12:24,750 egy másik szöveget, valójában, hogy valójában a tömb mérete 31. 310 00:12:24,750 --> 00:12:28,220 És ez csak a szerző úgy döntött, hogy hash húrok 311 00:12:28,220 --> 00:12:32,430 nem a személy nevét, de alapján születésnapok. 312 00:12:32,430 --> 00:12:35,680 Függetlenül attól, hogy a hónap, azt gondoltam ha született az első olyan hónap 313 00:12:35,680 --> 00:12:39,580 vagy a 31 havi, a szerző majd hash alapuló érték, 314 00:12:39,580 --> 00:12:44,154 annak érdekében, hogy terjed a nevek egy kicsit több, mint 26 foltok is lehetővé teszik. 315 00:12:44,154 --> 00:12:47,320 És talán ez egy kicsit egységesebb mint megy abc betűk, 316 00:12:47,320 --> 00:12:50,236 mert persze ott talán több ember a világon, nevét 317 00:12:50,236 --> 00:12:54,020 hogy kezdődik A mint biztosan más az ábécé. 318 00:12:54,020 --> 00:12:56,380 Szóval lehet, hogy ez egy kicsit egységesebb, feltételezve, 319 00:12:56,380 --> 00:12:58,640 egyenletes eloszlás A babák az egész egy hónap. 320 00:12:58,640 --> 00:12:59,990 >> De, persze, ez még mindig nem tökéletes. 321 00:12:59,990 --> 00:13:00,370 Jobb? 322 00:13:00,370 --> 00:13:01,370 Mi tekintettel ütközések. 323 00:13:01,370 --> 00:13:04,680 Több ember ebben a adatstruktúra még 324 00:13:04,680 --> 00:13:08,432 amelyek azonos születési legalább te függetlenül a hónap. 325 00:13:08,432 --> 00:13:09,640 De mi a szerző tenni? 326 00:13:09,640 --> 00:13:13,427 Nos, úgy néz ki, mint van egy tömb a bal oldali húzott függőlegesen, 327 00:13:13,427 --> 00:13:15,010 de ez csak egy művész kiadatás. 328 00:13:15,010 --> 00:13:18,009 Nem számít, milyen irányba felhívni egy tömb, ez még mindig egy tömb. 329 00:13:18,009 --> 00:13:20,225 Mi ez a tömb látszólag? 330 00:13:20,225 --> 00:13:21,500 >> KÖZÖNSÉG: láncolt lista. 331 00:13:21,500 --> 00:13:21,650 >> DAVID MALAN: Igen. 332 00:13:21,650 --> 00:13:23,490 Úgy néz ki, hogy ez egy tömb láncolt lista. 333 00:13:23,490 --> 00:13:26,490 Tehát ismét, hogy ezen a ponton a fajta Az ezen adatok struktúrákat most 334 00:13:26,490 --> 00:13:28,550 összetevőként több Érdekes megoldás, 335 00:13:28,550 --> 00:13:30,862 akkor feltétlenül, hogy egy alapvető, mint egy tömb, 336 00:13:30,862 --> 00:13:33,320 majd vegye valami érdekes, mint a láncolt lista 337 00:13:33,320 --> 00:13:36,660 és még összekapcsolják őket egy még További érdekes adat struktúrát. 338 00:13:36,660 --> 00:13:39,630 És valóban, ez is lenne nevezhető hash tábla, 339 00:13:39,630 --> 00:13:42,610 ahol a tömb valóban a hash tábla, 340 00:13:42,610 --> 00:13:45,600 de a hash tábla láncok, hogy úgy mondjam, 341 00:13:45,600 --> 00:13:50,220 amely képes növekedni, vagy zsugorodás alapján elemek száma a beszúrni kívánt. 342 00:13:50,220 --> 00:13:52,990 >> Most, ennek megfelelően mi a futási idő most? 343 00:13:52,990 --> 00:13:58,030 Ha szeretné szúrni valakit akinek születésnapját október 31 344 00:13:58,030 --> 00:13:59,040 hol ő megy? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Rendben van. 347 00:14:01,030 --> 00:14:02,819 Legalul, ahol azt mondja 31. 348 00:14:02,819 --> 00:14:03,610 És ez tökéletes. 349 00:14:03,610 --> 00:14:05,060 Ez volt konstans idő. 350 00:14:05,060 --> 00:14:08,760 De mi van, ha talál valaki mást akinek születésnapja van, lássuk, 351 00:14:08,760 --> 00:14:10,950 Október, november, december 31? 352 00:14:10,950 --> 00:14:12,790 Hol van ő fog menni? 353 00:14:12,790 --> 00:14:13,290 Ugyanaz a dolog. 354 00:14:13,290 --> 00:14:13,970 Két lépés mégis. 355 00:14:13,970 --> 00:14:15,303 Ez állandó, bár nem igaz? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Rendben van. 358 00:14:16,860 --> 00:14:17,840 Abban a pillanatban, amikor az. 359 00:14:17,840 --> 00:14:20,570 De az általános esetben, A több ember hozzátesszük, 360 00:14:20,570 --> 00:14:23,790 véletlenszerűen, megyünk hogy egyre több és több ütközés. 361 00:14:23,790 --> 00:14:26,820 >> Most ez egy kicsit jobb, mert technikailag 362 00:14:26,820 --> 00:14:34,580 most a láncok lehetne A legrosszabb esetben, meddig? 363 00:14:34,580 --> 00:14:38,890 Ha illessze n az embereket ebbe a több kifinomult adatstruktúra, n emberek, 364 00:14:38,890 --> 00:14:41,080 A legrosszabb esetben lesz n. 365 00:14:41,080 --> 00:14:41,815 Miért? 366 00:14:41,815 --> 00:14:43,332 >> KÖZÖNSÉG: Mert ha mindenki ugyanaz a születésnapja, 367 00:14:43,332 --> 00:14:44,545 ők lesznek egy sort. 368 00:14:44,545 --> 00:14:45,420 DAVID MALAN: Tökéletes. 369 00:14:45,420 --> 00:14:47,480 Lehet, hogy egy kicsit kitalált, de valóban a legrosszabb esetben, 370 00:14:47,480 --> 00:14:50,117 ha mindenkinek ugyanaz születésnapja, tekintettel a bemenő adatokra van, 371 00:14:50,117 --> 00:14:51,950 fogsz egy masszívan hosszú láncban. 372 00:14:51,950 --> 00:14:54,241 És így, akkor ez egy hash-tábla, de tényleg ez a 373 00:14:54,241 --> 00:14:56,810 Csak egy hatalmas összefüggő listát egy csomó elvesztegetett hely. 374 00:14:56,810 --> 00:15:00,460 De általában, ha feltételezzük, hogy legalább születésnapok uniform-- 375 00:15:00,460 --> 00:15:01,750 és ez valószínűleg nem. 376 00:15:01,750 --> 00:15:02,587 Én így, hogy akár. 377 00:15:02,587 --> 00:15:04,420 De ha feltételezzük, a a vita kedvéért 378 00:15:04,420 --> 00:15:07,717 hogy azok, akkor elméletileg, ha ez a függőleges képviselet 379 00:15:07,717 --> 00:15:11,050 a tömb, nos akkor remélhetőleg te fog kapni láncok, tudod, 380 00:15:11,050 --> 00:15:15,880 nagyjából azonos hosszúságú, ahol az egyes ezek jelentése egy nap a hónapban. 381 00:15:15,880 --> 00:15:19,930 >> Na most, ha van 31 nap a hónapban, azt jelenti, hogy a működési idő nagyon 382 00:15:19,930 --> 00:15:25,230 nagy O-n több mint 31, ami jobban érzi magát, mint a lineáris. 383 00:15:25,230 --> 00:15:27,950 De mi volt az egyik kötelezettségvállalások egy pár hétig 384 00:15:27,950 --> 00:15:31,145 ezelőtt, amikor jött a kifejező a futás idejét egy algoritmus? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Csak csak nézd meg a nagy rend kifejezést. 387 00:15:35,190 --> 00:15:35,690 Jobb? 388 00:15:35,690 --> 00:15:37,400 31. határozottan hasznos. 389 00:15:37,400 --> 00:15:39,610 De ez még mindig nagy O n. 390 00:15:39,610 --> 00:15:41,730 De az egyik téma A probléma meg öt 391 00:15:41,730 --> 00:15:43,950 lesz, hogy elismerik, hogy teljesen, 392 00:15:43,950 --> 00:15:47,320 aszimptotikusan, elméletileg adatstruktúrát 393 00:15:47,320 --> 00:15:50,470 nem jobb, mint egy hatalmas láncolt lista. 394 00:15:50,470 --> 00:15:53,550 És valóban, a legrosszabb esetben ez a hash tábla lehet ruházni abba. 395 00:15:53,550 --> 00:15:57,620 >> De a valós világban, nálunk az emberek hogy a saját Mac vagy PC, vagy bármi 396 00:15:57,620 --> 00:16:01,240 és futnak valós szoftver valós adatok 397 00:16:01,240 --> 00:16:03,260 amely algoritmus mész szívesebben? 398 00:16:03,260 --> 00:16:09,180 Az egyik, hogy úgy célból lépések vagy a az egyik, hogy tudomásul n osztva 31 fokozatban 399 00:16:09,180 --> 00:16:12,900 hogy néhány adatot vagy kikeresni valamilyen információt? 400 00:16:12,900 --> 00:16:16,580 Úgy értem, teljesen a 31 teszi a különbség a valós világban. 401 00:16:16,580 --> 00:16:18,540 Ez 31-szor gyorsabb. 402 00:16:18,540 --> 00:16:20,880 És mi emberek biztosan fogja értékelni azt. 403 00:16:20,880 --> 00:16:23,004 >> Így észre a kettősség ott között valójában 404 00:16:23,004 --> 00:16:25,920 beszél dolgok elméletileg és aszimptotikusan amely határozottan 405 00:16:25,920 --> 00:16:28,760 értékes amint láttuk, de a való világban, 406 00:16:28,760 --> 00:16:32,930 ha érdekel csak, hogy a ember boldog általános bemenet, 407 00:16:32,930 --> 00:16:36,010 Ön is nagyon jól akar elfogadni az a tény, hogy igen, ez lineáris, 408 00:16:36,010 --> 00:16:38,360 de 31-szer gyorsabb mint a lineáris lehet. 409 00:16:38,360 --> 00:16:41,610 És még jobb, nem csak azt kell nem valami önkényes, mint a születésnap, 410 00:16:41,610 --> 00:16:44,030 tudtuk eltölteni egy kis több időt és okosság 411 00:16:44,030 --> 00:16:47,140 és arra gondolok, mit lehet csinálni, adott személy nevét és talán 412 00:16:47,140 --> 00:16:50,130 a születési össze azokat összetevők kitalálni valamit 413 00:16:50,130 --> 00:16:52,720 hogy valóban több egységes és kevésbé csipkézett, 414 00:16:52,720 --> 00:16:56,250 hogy úgy mondjam, mint ezt a képet jelenleg azt javasolja lehet. 415 00:16:56,250 --> 00:16:57,750 Hogyan lehetne végrehajtani ezt a kódot? 416 00:16:57,750 --> 00:17:00,280 Nos, hadd javaslom, hogy csak kölcsön néhány szintaktikai voltunk 417 00:17:00,280 --> 00:17:01,799 használt egy-két alkalommal eddig. 418 00:17:01,799 --> 00:17:03,590 És én fogom meghatározni egy csomópont, amely ismét 419 00:17:03,590 --> 00:17:06,812 egy általános kifejezés csak néhány konténer néhány adatszerkezet. 420 00:17:06,812 --> 00:17:09,020 Fogom javasolni, hogy egy string megy oda. 421 00:17:09,020 --> 00:17:11,369 De megyünk elkezdi e képzés kerekek le most. 422 00:17:11,369 --> 00:17:13,230 >> Nincs több CS50 könyvtár Tényleg, ha nem akar 423 00:17:13,230 --> 00:17:15,230 használni a végső projekt, ami rendben van, 424 00:17:15,230 --> 00:17:18,569 de most megyünk, hogy húzza vissza a függöny és azt mondják, ez csak egy char csillag. 425 00:17:18,569 --> 00:17:22,069 A szó tehát ott lesz a személy nevét kérdéses. 426 00:17:22,069 --> 00:17:25,079 És most van egy link Itt a következő csomópont 427 00:17:25,079 --> 00:17:28,170 annak érdekében, hogy ezek képviselik az egyes csomópontok 428 00:17:28,170 --> 00:17:30,950 a láncban, potenciálisan A láncolt lista. 429 00:17:30,950 --> 00:17:34,090 >> És most hogyan Kijelentem a hash tábla maga? 430 00:17:34,090 --> 00:17:36,660 Hogyan Kijelentem, az egész szerkezet? 431 00:17:36,660 --> 00:17:40,960 Nos, tényleg, nagyon, mint régen egy mutatót hogy csak az első eleme a lista 432 00:17:40,960 --> 00:17:44,510 előtt, hasonlóan tudok csak mondani Csak kell egy csomó mutatók 433 00:17:44,510 --> 00:17:46,270 kell ez az egész hash tábla. 434 00:17:46,270 --> 00:17:49,484 Megyek, hogy egy tömb hívott táblázat hash tábla. 435 00:17:49,484 --> 00:17:50,900 Ez lesz a méret kapacitás. 436 00:17:50,900 --> 00:17:52,525 Így sok elem elfér benne. 437 00:17:52,525 --> 00:17:56,180 És minden egyes ilyen elem ebben tömb lesz a csomópont csillag. 438 00:17:56,180 --> 00:17:56,810 Miért? 439 00:17:56,810 --> 00:18:00,160 Nos, egy ezt a képet, amit én végrehajtása hash táblázat 440 00:18:00,160 --> 00:18:04,330 hatékonyan az elején csak ezt a tömböt, hogy már húzott függőlegesen, 441 00:18:04,330 --> 00:18:06,820 elrendezve, ennek négyzetek jelentése mutató. 442 00:18:06,820 --> 00:18:09,170 Ez pedig, hogy perjeleket rajtuk keresztül csak null. 443 00:18:09,170 --> 00:18:11,410 És az is, hogy nyilak majd jobbra 444 00:18:11,410 --> 00:18:16,140 tényleges mutatók tényleges csomópontok, ergo a kezdete egy láncolt lista. 445 00:18:16,140 --> 00:18:19,050 >> Tehát itt, tehát az, hogy hogyan lehet, hogy végre egy hash tábla 446 00:18:19,050 --> 00:18:21,580 végre külön láncolás. 447 00:18:21,580 --> 00:18:22,840 Most már mi a jobb? 448 00:18:22,840 --> 00:18:25,632 Rendben Megígértem utoljára tudtunk elérni konstans idő. 449 00:18:25,632 --> 00:18:27,381 És valahogy adtam konstans idő itt, 450 00:18:27,381 --> 00:18:29,850 de aztán azt mondta, nem igazán konstans időt, mert még mindig 451 00:18:29,850 --> 00:18:31,890 függ az összes elemek száma 452 00:18:31,890 --> 00:18:34,500 te bevitelére a az adatszerkezet. 453 00:18:34,500 --> 00:18:35,980 De tegyük fel, hogy ezt tette. 454 00:18:35,980 --> 00:18:39,550 Hadd menjek vissza a képernyőre itt. 455 00:18:39,550 --> 00:18:44,520 Hadd vetíteni ezt itt, világos a képernyőn, és tegyük fel, én tettem ezt. 456 00:18:44,520 --> 00:18:49,300 Tegyük fel akartam beilleszteni a nevét Daven az az én adatszerkezet. 457 00:18:49,300 --> 00:18:52,100 >> Szóval azt akarom, hogy helyezzen be egy húr Daven az adatszerkezet. 458 00:18:52,100 --> 00:18:54,370 Mi történik, ha nem használja a hash-tábla, de én használni 459 00:18:54,370 --> 00:18:56,980 valami, ami több, mint a fa, mint egy családfát, ahol 460 00:18:56,980 --> 00:18:59,670 van néhány gyökér a felső, majd csomópontok és a levelek 461 00:18:59,670 --> 00:19:01,440 hogy megy lefelé és kifelé. 462 00:19:01,440 --> 00:19:04,450 Tegyük fel, hogy én szeretné szúrni a Daven 463 00:19:04,450 --> 00:19:06,430 a mi jelenleg egy üres lista. 464 00:19:06,430 --> 00:19:09,780 Fogok csinálni a következő: Én létre fog hozni egy node ebben a családban 465 00:19:09,780 --> 00:19:15,170 fa-szerű szerkezet adat úgy néz ki, Egy kis, mint ez, amelyek mindegyike 466 00:19:15,170 --> 00:19:19,640 téglalapok már, mondjuk, A most 26 elem benne. 467 00:19:19,640 --> 00:19:21,650 És az egyes sejtek ebben tömb lesz 468 00:19:21,650 --> 00:19:23,470 hogy képviselje a levél az ábécé. 469 00:19:23,470 --> 00:19:28,190 >> Konkrétan fogom kezelni ez A, majd a B, majd a C, majd D, 470 00:19:28,190 --> 00:19:29,310 ezt itt. 471 00:19:29,310 --> 00:19:32,940 Szóval ez lesz a hatékony képviseli a levél D. 472 00:19:32,940 --> 00:19:36,040 De helyezze összes Daven által nevét kell tennem egy kicsit. 473 00:19:36,040 --> 00:19:37,840 Szóval először fog hash, hogy úgy mondjam. 474 00:19:37,840 --> 00:19:41,049 Megyek nézni az első betű a Daven azon ami nyilvánvalóan a D, 475 00:19:41,049 --> 00:19:42,840 és fogok kiosztani olyan csomópont, amely úgy néz ki, 476 00:19:42,840 --> 00:19:45,570 mint egy nagy téglalap this-- nagy ahhoz, hogy elférjen az egész ábécét. 477 00:19:45,570 --> 00:19:47,140 >> Most D történik. 478 00:19:47,140 --> 00:19:49,720 Most A. D-A-V-E-N a cél. 479 00:19:49,720 --> 00:19:51,220 Szóval, most mit fogok csinálni ez. 480 00:19:51,220 --> 00:19:54,027 Amint elkezdtem D nyilatkozat nincs mutató ott. 481 00:19:54,027 --> 00:19:56,860 Ez szemét értékeket abban a pillanatban, vagy talán inicializálás null. 482 00:19:56,860 --> 00:19:59,630 De hadd folyamatosan megy ezt az ötletet épület fa. 483 00:19:59,630 --> 00:20:04,260 Hadd osztja egy másik ilyen csomópontok 26 elem benne. 484 00:20:04,260 --> 00:20:05,150 >> És tudod mit? 485 00:20:05,150 --> 00:20:09,130 Ha ez csak egy csomópont a memóriában Én létrehozott malloc, egy struct 486 00:20:09,130 --> 00:20:11,240 ahogy azt hamarosan látni, Fogok csinálni this-- 487 00:20:11,240 --> 00:20:14,450 Fogok felhívni egy nyilat a dolog, hogy a képviselt D le 488 00:20:14,450 --> 00:20:15,860 az új csomópont. 489 00:20:15,860 --> 00:20:19,240 És most, először a következő levél Daven nevét, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- fogok menni előre és felhívni egy másik csomópont, mint ez, 491 00:20:24,150 --> 00:20:30,150 amely a V elem van, amely fogjuk felhívni instance-- Hoppá. 492 00:20:30,150 --> 00:20:31,020 Mi nem készít ott. 493 00:20:31,020 --> 00:20:31,936 Ez fog menni itt. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Aztán megyünk úgy, hogy ez az V. 496 00:20:35,712 --> 00:20:44,920 És akkor ide megyünk index le V-mit fogunk vizsgálni E. 497 00:20:44,920 --> 00:20:50,100 És akkor innen megyünk megy egy ilyen csomópont van. 498 00:20:50,100 --> 00:20:52,930 És most van egy kérdés megválaszolására. 499 00:20:52,930 --> 00:20:57,840 Meg kell valahogy azt jelzi, hogy mi vagyunk a végén a húr Daven. 500 00:20:57,840 --> 00:20:59,490 Így tudtam csak hagyja null. 501 00:20:59,490 --> 00:21:02,670 >> De mi van, ha van a Daven teljes név is, amely 502 00:21:02,670 --> 00:21:04,280 van, ahogy mondtam, Davenport? 503 00:21:04,280 --> 00:21:06,970 Mi van, ha a Daven valójában részkarakterláncként, 504 00:21:06,970 --> 00:21:08,960 előtagot egy sokkal hosszabb húr? 505 00:21:08,960 --> 00:21:11,450 Mi nem csak a tartósan mondjuk semmi sem megy 506 00:21:11,450 --> 00:21:14,410 hogy ott, mert tudtuk soha be egy szót, mint Davenport 507 00:21:14,410 --> 00:21:15,840 ebbe adatok Szerkezet 508 00:21:15,840 --> 00:21:19,560 >> Szóval, mit tehetünk helyette van kezelni az ilyen elemek mindegyike 509 00:21:19,560 --> 00:21:22,170 mivel talán, hogy két elemek belsejében őket. 510 00:21:22,170 --> 00:21:24,810 Az egyik egy mutató, sőt, ahogy én csináltam. 511 00:21:24,810 --> 00:21:27,100 Így minden ilyen dobozok nem csak egy cella. 512 00:21:27,100 --> 00:21:29,855 De mi van, ha a felső one-- az alsó a 513 00:21:29,855 --> 00:21:32,230 lesz nulla, mert nincs Davenport csak még. 514 00:21:32,230 --> 00:21:34,197 Mi van, ha az első egy valami különleges érték? 515 00:21:34,197 --> 00:21:36,530 És ez lesz egy kicsit nehéz kihúzni ezt a méretet. 516 00:21:36,530 --> 00:21:38,130 De tegyük fel, ez csak egy pipa. 517 00:21:38,130 --> 00:21:38,920 Ellenőrizze. 518 00:21:38,920 --> 00:21:44,230 D-A-V-E-N egy string ebben adatszerkezet. 519 00:21:44,230 --> 00:21:48,350 >> Közben, ha lenne több hely itt, amit tehettem P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 és én sodorhatják ellenőrzés a csomópont amely a T betű a legvégén. 521 00:21:52,650 --> 00:21:55,460 Tehát ez egy masszívan összetett megjelenésű adatszerkezet. 522 00:21:55,460 --> 00:21:57,210 És a kézírás biztosan nem segít. 523 00:21:57,210 --> 00:22:00,043 De ha akartam valamit beszúrni más, átgondolni, hogy mi tennénk. 524 00:22:00,043 --> 00:22:03,370 Ha akartuk, hogy Dávid, mi lenne ugyanezt a logikát, a D-A-V, 525 00:22:03,370 --> 00:22:08,802 de most szeretném mutatni a következő elem nem az E, de I-től D 526 00:22:08,802 --> 00:22:10,760 Tehát lesz több csomópont a fán. 527 00:22:10,760 --> 00:22:12,325 Mi lesz, hogy hívás malloc tovább. 528 00:22:12,325 --> 00:22:14,700 De én nem akarom, hogy egy teljes káosz kép. 529 00:22:14,700 --> 00:22:17,710 Szóval ahelyett, nézd meg egy hogy a már előre megfogalmazott 530 00:22:17,710 --> 00:22:21,810 mint ezt nem pont, pont, pontok, de csak rövidített tömbök. 531 00:22:21,810 --> 00:22:23,950 De minden csomópont a fán itt 532 00:22:23,950 --> 00:22:26,700 jelentése azonos thing-- tömb Ray a mérete 26. 533 00:22:26,700 --> 00:22:28,860 >> Vagy ha azt akarjuk, hogy nagyon helyes most, mi 534 00:22:28,860 --> 00:22:30,790 ha valakinek a nevét egy aposztróf, hadd 535 00:22:30,790 --> 00:22:35,560 Feltételezzük, hogy minden csomópont valójában mint 27-indexek is, nem csak a 26. 536 00:22:35,560 --> 00:22:42,020 Szóval ez most lesz egy adat szerkezet úgynevezett trie-- T-R-I-E. 537 00:22:42,020 --> 00:22:46,120 A Trie, ami állítólag történelmileg okos név egy fa 538 00:22:46,120 --> 00:22:49,040 ami optimalizált visszakeresés, ami természetesen, 539 00:22:49,040 --> 00:22:50,870 van írva egy I-E így Trie. 540 00:22:50,870 --> 00:22:52,710 De ez a történelem a Trie. 541 00:22:52,710 --> 00:22:55,860 >> Tehát egy Trie ez a fa-szerű adat szerkezet, mint egy családfa 542 00:22:55,860 --> 00:22:57,510 hogy végül úgy viselkedik, mint azt. 543 00:22:57,510 --> 00:23:00,890 És itt is csak egy példa a csomó más ember nevét. 544 00:23:00,890 --> 00:23:03,540 De a kérdés most kéznél, ami van 545 00:23:03,540 --> 00:23:08,070 nyertünk bevezetésével vitathatatlanul egy bonyolult adatstruktúra, és egy, 546 00:23:08,070 --> 00:23:09,870 őszintén, hogy használ sok memóriát. 547 00:23:09,870 --> 00:23:11,703 >> Mert annak ellenére, abban a pillanatban, én csak 548 00:23:11,703 --> 00:23:15,050 a D és pointer A V és Es és Ns, 549 00:23:15,050 --> 00:23:16,700 Én pazarlás fene sok memóriát. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 De hol töltök egy forrás, Én inkább ezt vissza szerezni a másik. 552 00:23:22,660 --> 00:23:26,020 Tehát, ha költök több helyet, mi talán a remény? 553 00:23:26,020 --> 00:23:27,407 Hogy én kevesebbet költenek, mi? 554 00:23:27,407 --> 00:23:28,240 KÖZÖNSÉG: Kevesebb idő. 555 00:23:28,240 --> 00:23:28,990 DAVID MALAN: Time. 556 00:23:28,990 --> 00:23:30,320 Most miért lenne az? 557 00:23:30,320 --> 00:23:33,880 Nos, mi a beillesztés idő, tekintve a nagy O most, 558 00:23:33,880 --> 00:23:37,660 Egy név, mint a Daven vagy Davenport vagy David? 559 00:23:37,660 --> 00:23:39,340 Nos, Daven volt öt lépésben. 560 00:23:39,340 --> 00:23:42,350 Davenport lesz kilenc lépésben, így lenne egy pár lépést. 561 00:23:42,350 --> 00:23:44,250 Dávid öt lépésben is. 562 00:23:44,250 --> 00:23:47,230 Tehát ezek konkrét számok, de biztosan van 563 00:23:47,230 --> 00:23:49,550 egy felső határt a hossza valakinek a nevét. 564 00:23:49,550 --> 00:23:52,240 És valóban, a probléma egyenként öt specifikáció, 565 00:23:52,240 --> 00:23:54,050 fogunk javasolni hogy ez valami 566 00:23:54,050 --> 00:23:55,470 ez mintegy 40-furcsa karakterek. 567 00:23:55,470 --> 00:23:58,180 >> Reálisan, senki sem végtelenül hosszú nevet, 568 00:23:58,180 --> 00:24:01,542 ami azt jelenti, hogy a hossza egy nevét vagy a karakterlánc hosszát mi talán 569 00:24:01,542 --> 00:24:03,750 bizonyos az állam struktúra vitathatatlanul mi? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Ez állandó. 572 00:24:06,250 --> 00:24:06,430 Jobb? 573 00:24:06,430 --> 00:24:09,310 Lehet, hogy egy nagy konstans, mint a 40-valamit, de ez állandó. 574 00:24:09,310 --> 00:24:13,752 És ez nem függőség, hogy hány más nevek ebben adatszerkezet. 575 00:24:13,752 --> 00:24:15,460 Más szóval, ha akart most beilleszteni 576 00:24:15,460 --> 00:24:20,540 Colton vagy Gabriel vagy Rob vagy Zamyla vagy Alison vagy Belinda vagy bármely más nevek 577 00:24:20,540 --> 00:24:23,940 A személyzet ebbe adat szerkezet, az a futási idő 578 00:24:23,940 --> 00:24:26,750 beillesztése más nevek lesz egyáltalán hatással 579 00:24:26,750 --> 00:24:30,220 hány további elemek az adatstruktúrában már? 580 00:24:30,220 --> 00:24:31,040 Ez nem az. 581 00:24:31,040 --> 00:24:31,540 Jobb? 582 00:24:31,540 --> 00:24:36,150 Mert mi eredményesen ez többrétegű hash tábla. 583 00:24:36,150 --> 00:24:38,280 És a menetideje E műveletek 584 00:24:38,280 --> 00:24:41,510 nem függ a számát elemek, amelyek az adatstruktúra 585 00:24:41,510 --> 00:24:43,090 vagy amelyek végül fog helye az adatstruktúra, 586 00:24:43,090 --> 00:24:44,714 de a hossza pontosan mit? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> A szöveg pedig ki, amely nem teszi 589 00:24:49,200 --> 00:24:52,580 ez aszimptotikusan konstans time-- nagy O egy. 590 00:24:52,580 --> 00:24:54,720 És őszintén szólva, csak a valós világban, ez 591 00:24:54,720 --> 00:24:58,380 azt behelyezése Daven nevét veszi mint öt lépés, vagy Davenport kilenc 592 00:24:58,380 --> 00:25:00,100 lépések, vagy David öt lépésben. 593 00:25:00,100 --> 00:25:03,071 Ez átkozottul kicsi üzemidő. 594 00:25:03,071 --> 00:25:05,320 És valóban, ez egy nagyon jó dolog, különösen, ha 595 00:25:05,320 --> 00:25:08,126 ez nem függ a teljes számú elem van benne. 596 00:25:08,126 --> 00:25:10,500 Szóval, hogyan lehet azt végrehajtani ezt fajta szerkezet kódot? 597 00:25:10,500 --> 00:25:12,900 Ez egy kicsit bonyolult, de még mindig ez a 598 00:25:12,900 --> 00:25:15,050 csak egy alkalmazása alapvető építőkövei. 599 00:25:15,050 --> 00:25:17,830 Megyek újra minket csomópont az alábbiak szerint: 600 00:25:17,830 --> 00:25:21,100 bool nevű word-- és ez nevezhetnénk semmit. 601 00:25:21,100 --> 00:25:23,970 De a bool jelentése amit rajzoltam, mint a pipa. 602 00:25:23,970 --> 00:25:24,490 Igen. 603 00:25:24,490 --> 00:25:26,720 Ez a vége a húr ebben adatszerkezet. 604 00:25:26,720 --> 00:25:30,702 >> És, természetesen, a csomópont csillag van a gyermekek. 605 00:25:30,702 --> 00:25:32,410 És valóban, csak tetszik egy családfát, akkor 606 00:25:32,410 --> 00:25:34,370 tartaná a csomópontok hogy lóg ki 607 00:25:34,370 --> 00:25:36,920 az alján néhány szülő elem, hogy a gyermekek. 608 00:25:36,920 --> 00:25:40,510 És így a gyerekek fog hogy egy sor 27, 27 egy 609 00:25:40,510 --> 00:25:41,680 csak, hogy az aposztróf. 610 00:25:41,680 --> 00:25:43,390 Megyünk rendezni különleges eset. 611 00:25:43,390 --> 00:25:45,400 Így bizonyos nevek aposztróf. 612 00:25:45,400 --> 00:25:47,399 Talán még kötőjel kellene menj oda, de akkor 613 00:25:47,399 --> 00:25:50,330 lásd p készlet 5 csak gondozás körülbelül betűk és aposztrófok. 614 00:25:50,330 --> 00:25:52,990 >> És akkor hogyan képviselt Az adatstruktúra maga? 615 00:25:52,990 --> 00:25:56,454 Hogyan képviselik a gyökér E Trie, hogy úgy mondjam? 616 00:25:56,454 --> 00:25:59,620 Nos, csak, mint a láncolt lista, akkor kell egy mutatót az első elemet. 617 00:25:59,620 --> 00:26:04,270 Egy Trie akkor csak meg kell egy mutatót az alapja ennek a Trie. 618 00:26:04,270 --> 00:26:07,290 És onnan lehet hash végig mélyebbre és mélyebbre 619 00:26:07,290 --> 00:26:10,460 minden más csomópont a szerkezetben. 620 00:26:10,460 --> 00:26:13,440 Így csak ezzel lehet képviseljük, hogy a struktúra. 621 00:26:13,440 --> 00:26:15,877 >> Most Meanwhile-- Oh, kérdés. 622 00:26:15,877 --> 00:26:17,220 >> KÖZÖNSÉG: Mi bool szó? 623 00:26:17,220 --> 00:26:20,490 >> DAVID MALAN: Bool szó Csak ez a C megtestesülés 624 00:26:20,490 --> 00:26:22,920 Az, amit leírtam ebbe a mezőbe itt, amikor 625 00:26:22,920 --> 00:26:26,000 Elkezdtem felosztása az egyes tömb elemeit két részre. 626 00:26:26,000 --> 00:26:27,600 Az egyik egy mutató a következő csomópont. 627 00:26:27,600 --> 00:26:30,280 A másik kell lennie olyasmi, mint egy jelölőnégyzetet 628 00:26:30,280 --> 00:26:33,770 mondani, hogy igen, van egy szó Daven, hogy véget ér itt, 629 00:26:33,770 --> 00:26:35,610 mert nem akarjuk, abban a pillanatban, Dave. 630 00:26:35,610 --> 00:26:39,320 >> Annak ellenére, hogy Dave lesz a jogos szó, ő nem a Trie 631 00:26:39,320 --> 00:26:39,830 még. 632 00:26:39,830 --> 00:26:40,950 És D nem egy szó. 633 00:26:40,950 --> 00:26:42,770 És D-A nem egy szó vagy egy nevet. 634 00:26:42,770 --> 00:26:45,020 Így a pipa jelzi, csak akkor, ha 635 00:26:45,020 --> 00:26:48,190 hit ez a csomópont korábbi útvonal karakterek 636 00:26:48,190 --> 00:26:50,700 tulajdonképpen egy string, hogy már ki. 637 00:26:50,700 --> 00:26:53,660 Szóval ez a bool ott tesz értünk. 638 00:26:53,660 --> 00:26:55,500 >> Minden más kérdésre próbál? 639 00:26:55,500 --> 00:26:56,215 Igen. 640 00:26:56,215 --> 00:26:58,035 >> KÖZÖNSÉG: Mi az átfedés? 641 00:26:58,035 --> 00:26:59,945 Mi van, ha van egy Dave és a Daven? 642 00:26:59,945 --> 00:27:00,820 DAVID MALAN: Tökéletes. 643 00:27:00,820 --> 00:27:02,580 Mi van, ha van egy Dave és a Daven? 644 00:27:02,580 --> 00:27:06,240 Tehát, ha azt beilleszteni, mondjuk egy becenév, A David-- Dave-- a D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Ez tulajdonképpen szuper egyszerű. 647 00:27:08,700 --> 00:27:10,325 Szóval csak megy, hogy négy lépést. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-E. És mit kell csinálni, ha én hit, hogy a negyedik csomópont? 650 00:27:15,847 --> 00:27:16,680 Csak fogja ellenőrizni. 651 00:27:16,680 --> 00:27:18,000 Mi már jó menni. 652 00:27:18,000 --> 00:27:18,840 Kész. 653 00:27:18,840 --> 00:27:19,750 Négy lépésben. 654 00:27:19,750 --> 00:27:21,590 Állandó idő aszimptotikusan. 655 00:27:21,590 --> 00:27:26,300 És most már azt jelezte, hogy a két Dave és Daven vannak húrok a szerkezet. 656 00:27:26,300 --> 00:27:27,710 Így nem jelent problémát. 657 00:27:27,710 --> 00:27:30,200 És észre, hogy a jelen A Daven nem teszi 658 00:27:30,200 --> 00:27:34,750 vesz több időt, vagy kevésbé ideje Dave és fordítva. 659 00:27:34,750 --> 00:27:36,000 >> Szóval, mit tehetünk most csinálni? 660 00:27:36,000 --> 00:27:40,680 Már használta ezt a metaforát előtt A tálcák képviselő valamit. 661 00:27:40,680 --> 00:27:43,380 De kiderül, hogy a halom tálcák valójában 662 00:27:43,380 --> 00:27:47,187 demonstratív másik absztrakt adat type-- magasabb szintű adatszerkezetet 663 00:27:47,187 --> 00:27:49,770 hogy a végén a nap csak mint egy tömb vagy láncolt lista 664 00:27:49,770 --> 00:27:50,970 vagy valami több világi. 665 00:27:50,970 --> 00:27:53,270 De ez egy sokkal érdekesebb fogalmi fogalom. 666 00:27:53,270 --> 00:27:56,440 A halom, mint ezek tálcák itt Mather, 667 00:27:56,440 --> 00:27:58,750 általában az úgynevezett csak hogy-- verem. 668 00:27:58,750 --> 00:28:02,540 >> És az ilyen típusú adatstruktúra van két operations-- 669 00:28:02,540 --> 00:28:05,880 Van egy úgynevezett push hozzátéve valamit a verem, 670 00:28:05,880 --> 00:28:08,320 olyan, mintha egy másik tálca vissza a tetején a verem. 671 00:28:08,320 --> 00:28:11,350 És akkor pop, ami azt jelenti, hogy hogy a legfelső tálca ki. 672 00:28:11,350 --> 00:28:16,210 De mi kulcs egy halom, hogy az ez van ez a furcsa jellemző. 673 00:28:16,210 --> 00:28:19,560 Mivel az étkezőben személyzet átrendezése a tálcákat a következő étkezés, 674 00:28:19,560 --> 00:28:21,380 mi lesz igaz, hogy a diákok 675 00:28:21,380 --> 00:28:22,856 kölcsönhatásba adatstruktúrát? 676 00:28:22,856 --> 00:28:24,480 KÖZÖNSÉG: fognak pop egyszeri. 677 00:28:24,480 --> 00:28:26,550 DAVID MALAN: fognak pop egyszeri, remélhetőleg a tetején. 678 00:28:26,550 --> 00:28:28,910 Egyébként ez csak ilyen hülye menni egészen az aljára. 679 00:28:28,910 --> 00:28:29,070 Jobb? 680 00:28:29,070 --> 00:28:31,620 Az adatok szerkezete nem igazán teszi lehetővé hogy megragad az alsó tálca legalább 681 00:28:31,620 --> 00:28:32,520 könnyen. 682 00:28:32,520 --> 00:28:35,040 Szóval van ez a furcsa ingatlan egy halom 683 00:28:35,040 --> 00:28:39,730 hogy az utolsó tétel is lesz az első ki. 684 00:28:39,730 --> 00:28:43,400 És a számítógépes tudósok ez LIFO-- utolsóként, first out. 685 00:28:43,400 --> 00:28:45,540 És ez tényleg nem volna érdekes alkalmazásokat. 686 00:28:45,540 --> 00:28:50,090 Ez nem feltétlenül annyira nyilvánvaló, mint egyes mások, de lehet, sőt, hasznos lehet, 687 00:28:50,090 --> 00:28:54,040 és azt is, sőt, végre kell hajtani egy pár különböző módon. 688 00:28:54,040 --> 00:28:58,550 >> Tehát az egyik, és valóban, hadd , hogy ne merüljön bele. 689 00:28:58,550 --> 00:28:59,860 Csináljuk ezt helyette. 690 00:28:59,860 --> 00:29:03,700 Nézzük meg az egyik, hogy szinte az Ugyanez a gondolat, de ez egy kicsit igazságosabb. 691 00:29:03,700 --> 00:29:04,200 Jobb? 692 00:29:04,200 --> 00:29:07,560 Ha egy ilyen rajongó fiúk vagy lányok, nagyon szereti az Apple termékek 693 00:29:07,560 --> 00:29:10,130 és akkor ébredt fel 03:00 sorakoznak néhány bolt 694 00:29:10,130 --> 00:29:14,150 hogy a legújabb iPhone, akkor Lehet, hogy sorban állnak, mint ez. 695 00:29:14,150 --> 00:29:15,800 >> Most egy sor nagyon tudatosan neve. 696 00:29:15,800 --> 00:29:18,190 Ez egy sor, mert ott van néhány méltányosság hozzá. 697 00:29:18,190 --> 00:29:18,690 Jobb? 698 00:29:18,690 --> 00:29:21,690 Ez a fajta szar, ha már ért oda először az Apple Store 699 00:29:21,690 --> 00:29:25,700 de gyakorlatilag a legalsó tálca mert az Apple alkalmazottai akkor 700 00:29:25,700 --> 00:29:28,189 pop az utolsó ember, aki tényleg beállt a sorba. 701 00:29:28,189 --> 00:29:31,230 Így stack és sorokat, bár funkcionálisan ők milyen a same-- 702 00:29:31,230 --> 00:29:33,105 ez csak a gyűjtemény a források, ami 703 00:29:33,105 --> 00:29:36,210 fog növekedni, és ott van shrink-- ezt méltányosság szempont, hogy azt, 704 00:29:36,210 --> 00:29:39,634 legalábbis a valós világban, ahol a műveletek edz 705 00:29:39,634 --> 00:29:40,800 alapvetően eltérő. 706 00:29:40,800 --> 00:29:43,360 A stack-- sorban rather-- azt mondta, hogy 707 00:29:43,360 --> 00:29:45,320 két művelet: n sor és d sor. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Vagy hívhatjuk őket tetszőleges számú dolog. 710 00:29:48,090 --> 00:29:50,770 De csak azt, hogy elfog az elképzelés, hogy az egyik hozzáadása 711 00:29:50,770 --> 00:29:53,230 és végül egy kivonva. 712 00:29:53,230 --> 00:29:58,840 >> Most a motorháztető alatt, mind a verem és a sor lehet valósítani, hogyan? 713 00:29:58,840 --> 00:30:01,390 Mi nem megyünk bele a kódját mert a magasabb szint 714 00:30:01,390 --> 00:30:03,387 ötlet valami sokkal nyilvánvalóbb. 715 00:30:03,387 --> 00:30:04,470 Úgy értem, az emberek mit csinál? 716 00:30:04,470 --> 00:30:07,030 Ha én vagyok az első, aki az Apple Tárolja és ez a bejárati ajtó, 717 00:30:07,030 --> 00:30:08,130 Tudod, én fogok itt állni. 718 00:30:08,130 --> 00:30:09,750 És a következő személy fog állni itt. 719 00:30:09,750 --> 00:30:11,500 És a következő személy fog állni itt. 720 00:30:11,500 --> 00:30:13,792 Tehát mi adatstruktúra alkalmas arra, hogy a sorban? 721 00:30:13,792 --> 00:30:14,542 >> KÖZÖNSÉG: A sor. 722 00:30:14,542 --> 00:30:15,667 DAVID MALAN: Nos, a sorban. 723 00:30:15,667 --> 00:30:16,390 Persze. 724 00:30:16,390 --> 00:30:16,920 Mi más? 725 00:30:16,920 --> 00:30:17,600 >> KÖZÖNSÉG: A láncolt lista. 726 00:30:17,600 --> 00:30:18,990 >> DAVID MALAN: A kapcsolt bejegyzés tudna megvalósítani. 727 00:30:18,990 --> 00:30:22,500 És egy láncolt lista hasznos, mert akkor nőhet önkényesen hosszú, szemben 728 00:30:22,500 --> 00:30:24,880 hogy miután néhány fix szám az emberek a boltban. 729 00:30:24,880 --> 00:30:27,030 De talán egy meghatározott számú helyek jogos. 730 00:30:27,030 --> 00:30:30,350 Mert ha csak mint a 20 iPhone az első napon, talán 731 00:30:30,350 --> 00:30:33,930 csak meg kell egy tömb mérete 20. képviseli a sort, amely 732 00:30:33,930 --> 00:30:37,070 csak mondani most ha egyszer elkezd beszélni ezekről a magasabb szintű problémák 733 00:30:37,070 --> 00:30:38,890 akkor végre azt bármilyen számos módon. 734 00:30:38,890 --> 00:30:42,030 És talán csak fog egy kompromisszum a térben és időben 735 00:30:42,030 --> 00:30:43,950 vagy csak a saját kódját összetettségét. 736 00:30:43,950 --> 00:30:45,380 >> Mi a helyzet a stack? 737 00:30:45,380 --> 00:30:48,190 Nos, egy halom, láttuk is Lehet, hogy csak ezek a tálcákat. 738 00:30:48,190 --> 00:30:50,007 És akkor végre ezt a tömböt. 739 00:30:50,007 --> 00:30:53,090 De egy bizonyos ponton, ha használja egy sor, mi fog történni, hogy a tálcák 740 00:30:53,090 --> 00:30:54,173 akarsz letenni? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Rendben van. 743 00:30:55,670 --> 00:30:57,490 Te csak akkor fog tud menni olyan magas. 744 00:30:57,490 --> 00:31:00,156 És azt hiszem, a Mather ők valójában süllyesztve, hogy a nyitás. 745 00:31:00,156 --> 00:31:01,950 Szóval valóban, ez majdnem mint Mather használ 746 00:31:01,950 --> 00:31:03,783 tömb rögzített méretű, mert akkor csak 747 00:31:03,783 --> 00:31:08,302 illik annyi tálcák hogy nyitás a fal lent emberek térde. 748 00:31:08,302 --> 00:31:10,010 És hogy lehet azt mondta, hogy egy tömb, 749 00:31:10,010 --> 00:31:14,300 de minden bizonnyal végre, hogy a általában egy láncolt lista. 750 00:31:14,300 --> 00:31:16,390 >> Nos, mi a helyzet a másik adatszerkezet? 751 00:31:16,390 --> 00:31:18,760 Hadd húzza fel egy másik vizuális itt. 752 00:31:18,760 --> 00:31:24,710 Valami ilyesmi hogyan körülbelül ez itt? 753 00:31:24,710 --> 00:31:28,920 Miért lehet ez hasznos, hogy nem valami olyan divatos, mint a Trie, amely 754 00:31:28,920 --> 00:31:32,370 láttuk már ezeket a nagyon széles csomópontok, amelyek mindegyike egy tömb? 755 00:31:32,370 --> 00:31:35,740 De mi van, ha nem teszünk valamit még egyszerűen, mint egy régi iskola családfa, 756 00:31:35,740 --> 00:31:38,110 mindegyik, melynek csúcsai itt csak tárolja a számot. 757 00:31:38,110 --> 00:31:42,180 Ahelyett, hogy egy név vagy egy leszármazott csak tárolja a számot, mint ez. 758 00:31:42,180 --> 00:31:45,250 >> Nos, a zsargon, amit használni adatszerkezetek egyszerre próbál 759 00:31:45,250 --> 00:31:49,510 és a fák, ahol a Trie, újra, Csak akinek csomópontok tömbök, 760 00:31:49,510 --> 00:31:51,680 még, amit esetleg használni iskolában 761 00:31:51,680 --> 00:31:53,860 ha tett egy család tree-- levelek és a gyökér 762 00:31:53,860 --> 00:31:57,250 A fa és a gyermekek, a szülő és a testvérek cikke. 763 00:31:57,250 --> 00:32:03,670 És talán végre egy fa, például, mivel egyszerűen, mint ez. 764 00:32:03,670 --> 00:32:07,420 A fa, mint ha ez a csomópont, az egyik Ezekben a körökben, hogy van egy szám, 765 00:32:07,420 --> 00:32:09,947 ez nem megy, hogy egy mutató, hanem kettő. 766 00:32:09,947 --> 00:32:11,780 És amint hozzá Egy másik mutató, akkor 767 00:32:11,780 --> 00:32:13,905 valójában most, hogy sort A két-dimenziós adat 768 00:32:13,905 --> 00:32:14,780 struktúrákat a memóriában. 769 00:32:14,780 --> 00:32:16,660 Sok, mint egy két dimenziós tömb, akkor 770 00:32:16,660 --> 00:32:18,904 van a fajta két-dimenziós kapcsolódó listák hanem azok, 771 00:32:18,904 --> 00:32:20,820 hogy követik a mintát ahol nincs ciklus. 772 00:32:20,820 --> 00:32:24,487 Ez valóban egy fa egy nagyszülő egészen ide, majd 773 00:32:24,487 --> 00:32:27,320 néhány szülő és gyermek unokák és dédunokája. 774 00:32:27,320 --> 00:32:28,370 és így tovább. 775 00:32:28,370 --> 00:32:32,390 >> De ami igazán ügyes erről is, Csak ugratni egy kis kódot, 776 00:32:32,390 --> 00:32:35,370 visszahívás rekurzió -tól egy kicsit vissza, amely 777 00:32:35,370 --> 00:32:38,220 írsz egy függvényt, amely saját magát hívja meg. 778 00:32:38,220 --> 00:32:41,140 Ez egy csodás lehetőség végrehajtani valamit 779 00:32:41,140 --> 00:32:42,920 mint rekurzió, mert úgy ez. 780 00:32:42,920 --> 00:32:43,860 >> Ez egy fa. 781 00:32:43,860 --> 00:32:48,040 És én már egy kicsit, hogy hogyan anális Tettem az egész az utcára. 782 00:32:48,040 --> 00:32:51,020 Olyannyira, hogy van egy különleges name-- bináris kereső fába. 783 00:32:51,020 --> 00:32:53,460 Most hallottam a bináris keresés, de te is 784 00:32:53,460 --> 00:32:55,180 visszafelé ebből a dolog nevét? 785 00:32:55,180 --> 00:32:59,280 Mi az a minta, hogyan ki az egész ebbe a fát? 786 00:32:59,280 --> 00:33:00,696 Ez nem önkényes. 787 00:33:00,696 --> 00:33:01,570 Van néhány mintát. 788 00:33:01,570 --> 00:33:02,090 Igen. 789 00:33:02,090 --> 00:33:03,370 >> KÖZÖNSÉG: kisebb a bal oldalon. 790 00:33:03,370 --> 00:33:03,690 >> DAVID MALAN: Igen. 791 00:33:03,690 --> 00:33:05,062 Kisebbek a bal oldalon. 792 00:33:05,062 --> 00:33:06,270 Nagyobbak, a jobb oldalon. 793 00:33:06,270 --> 00:33:12,940 Úgy, hogy igaz az állítás a szülő nagyobb, mint a bal fia, 794 00:33:12,940 --> 00:33:14,850 de kisebb, mint a jobb fia. 795 00:33:14,850 --> 00:33:17,750 És ez önmagában még rekurzív verbális definíció 796 00:33:17,750 --> 00:33:20,500 mert akkor lehet alkalmazni, hogy Ugyanez a logika, hogy minden csomópont 797 00:33:20,500 --> 00:33:23,080 és csak fenéktermék ki, a bázis esetben, ha azt 798 00:33:23,080 --> 00:33:25,740 lesz, ha bejön az egyik a levelek, hogy úgy mondjam, 799 00:33:25,740 --> 00:33:28,580 ahol a szabadság nem a gyerekek tovább. 800 00:33:28,580 --> 00:33:30,614 >> Most hogyan lehet megtalálni a szám a 44? 801 00:33:30,614 --> 00:33:32,280 Akkor indulna meg a gyökér, és azt mondják, hm. 802 00:33:32,280 --> 00:33:35,690 55. nem 44. Tehát nem akarok menni jobbra vagy akarom, hogy menjen balra? 803 00:33:35,690 --> 00:33:37,190 Nos, nyilvánvalóan akarsz menni balra. 804 00:33:37,190 --> 00:33:40,060 És ez így olyan, mint a telefon könyv például a bináris keresés 805 00:33:40,060 --> 00:33:41,099 általában. 806 00:33:41,099 --> 00:33:43,390 De mi azt végrehajtó most egy kicsit dinamikusabban 807 00:33:43,390 --> 00:33:45,339 mint egy tömböt is lehetővé teszik. 808 00:33:45,339 --> 00:33:48,130 És valóban, ha meg akarom nézni A kód első pillantásra biztos. 809 00:33:48,130 --> 00:33:49,671 Úgy néz ki, mint egy csomó vonalak. 810 00:33:49,671 --> 00:33:51,220 De ez csodálatosan egyszerű. 811 00:33:51,220 --> 00:33:54,490 Ha azt szeretnénk, hogy végre egy függvény hívott keresés melynek célja az életben 812 00:33:54,490 --> 00:33:57,290 hogy keressen egy érték mint n egy egész szám, 813 00:33:57,290 --> 00:34:01,756 és te telt el egy pointer-- a mutatót a csomópont a gyökér, 814 00:34:01,756 --> 00:34:04,380 inkább az a fa, amely elérheti minden mást, 815 00:34:04,380 --> 00:34:08,850 észre, hogy egyenesen akkor végre a logika. 816 00:34:08,850 --> 00:34:10,880 Ha a fa null, nyilvánvalóan nincs ott. 817 00:34:10,880 --> 00:34:11,880 Nézzük csak vissza hamis. 818 00:34:11,880 --> 00:34:12,000 Jobb? 819 00:34:12,000 --> 00:34:14,040 Ha adja le semmit, nincs ott semmi. 820 00:34:14,040 --> 00:34:17,900 >> Más, ha n értéke kisebb, mint fa arrow n-- most nyíl n, 821 00:34:17,900 --> 00:34:20,670 emlékszem mi vezetett szuper röviden a minap, 822 00:34:20,670 --> 00:34:25,100 és ez csak azt jelenti, de a hivatkozás mutató, és nézd meg a területen az úgynevezett n. 823 00:34:25,100 --> 00:34:27,690 Tehát ez azt jelenti, hogy ott és nézd meg a területen az úgynevezett n. 824 00:34:27,690 --> 00:34:33,810 Tehát, ha n értéke maga adott, kevésbé mint az érték a fák egész, 825 00:34:33,810 --> 00:34:35,449 ahol akarsz menni? 826 00:34:35,449 --> 00:34:36,389 Balra. 827 00:34:36,389 --> 00:34:37,780 >> Így észre a rekurziót. 828 00:34:37,780 --> 00:34:39,860 Én returning-- nem igaz. 829 00:34:39,860 --> 00:34:40,989 Nem hamis. 830 00:34:40,989 --> 00:34:45,670 Én vissza függetlenül a válasz ez egy felhívás a magam, múló 831 00:34:45,670 --> 00:34:50,100 egy n újra, ami felesleges, de mi most kicsit más? 832 00:34:50,100 --> 00:34:51,989 Hogy vagyok, hogy a probléma kisebb? 833 00:34:51,989 --> 00:34:54,920 Én halad, mint a második érv, nem a gyökér a fa, 834 00:34:54,920 --> 00:34:59,616 de a bal gyermek ebben az esetben. 835 00:34:59,616 --> 00:35:00,990 Szóval halad a bal oldali gyermek. 836 00:35:00,990 --> 00:35:04,720 >> Közben, ha n értéke nagyobb, mint a csomópont Én jelenleg vizsgálja, 837 00:35:04,720 --> 00:35:06,690 Keresem a jobb oldalon. 838 00:35:06,690 --> 00:35:10,880 Különben, ha a fa nem nulla, és ha az elem nem balra 839 00:35:10,880 --> 00:35:13,240 és ez nem az a helyes, mi csodálatosan a helyzet? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Már valóban megtalálható a csomópont kérdés, és ezért vissza igaz. 842 00:35:18,440 --> 00:35:21,490 >> Így már csak karcos a felület most néhány ilyen adatszerkezetek. 843 00:35:21,490 --> 00:35:24,370 A probléma meg öt te fogsz vizsgálja ezeket még tovább, 844 00:35:24,370 --> 00:35:27,250 és akkor meg kell adni a tervezési választás, hogyan szeretné ezt. 845 00:35:27,250 --> 00:35:30,250 Azt szeretném, hogy megállapítsa, csak egy 30 másodperces teaser 846 00:35:30,250 --> 00:35:32,080 mi vár a jövő héten, és azon túl. 847 00:35:32,080 --> 00:35:35,390 >> Ahogy begin-- szerencsére lehet, hogy think-- az átmenet lassan 848 00:35:35,390 --> 00:35:38,680 a világ a C és az alacsonyabb szintű végrehajtásának részleteit, 849 00:35:38,680 --> 00:35:42,090 Egy olyan világban, ahol tudunk venni a biztosra, hogy valaki másnak végül 850 00:35:42,090 --> 00:35:44,010 végre ezeket az adatokat struktúrák nekünk, 851 00:35:44,010 --> 00:35:47,570 és kezdjük megérteni a valós olyan végrehajtási 852 00:35:47,570 --> 00:35:50,560 webes programok és weboldalak általában 853 00:35:50,560 --> 00:35:52,910 és az is nagyon biztonsági látszat, hogy mi már csak 854 00:35:52,910 --> 00:35:54,850 megkezdte a felszínét. 855 00:35:54,850 --> 00:35:57,320 Itt van, mi vár ránk a napokban. 856 00:35:57,320 --> 00:36:00,480 >> [VIDEO LEJÁTSZÁS] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -Ő Jött egy üzenet, a jegyzőkönyv minden saját. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Azért jött, hogy a világ a kegyetlen tűzfalak, útválasztók nemtörődöm, 861 00:36:30,894 --> 00:36:33,368 és veszélyek sokkal rosszabb, mint a halál. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Ő gyors. 864 00:36:36,236 --> 00:36:37,980 Ő erős. 865 00:36:37,980 --> 00:36:42,830 Ő TCP / IP, és van neki a címet. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Warriors of a neten." 868 00:36:48,074 --> 00:36:49,660 [END VIDEO LEJÁTSZÁS] 869 00:36:49,660 --> 00:36:50,910 DAVID MALAN: jön a jövő héten. 870 00:36:50,910 --> 00:36:51,880 Majd meglátjuk, akkor majd. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [VIDEO LEJÁTSZÁS] 873 00:36:56,060 --> 00:36:59,240 -És Most, "Deep Thoughts" a Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Mindig indul előadást, "Rendben." 876 00:37:05,820 --> 00:37:08,750 Miért ne, "Itt a megoldás hogy ezen a héten a probléma set " 877 00:37:08,750 --> 00:37:12,180 vagy "Mi így mindannyian egy A?" 878 00:37:12,180 --> 00:37:13,380 [Nevet] 879 00:37:13,380 --> 00:37:15,530 [END VIDEO LEJÁTSZÁS]