1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:11,137 [Přehrávání hudby] 3 00:00:11,137 --> 00:00:12,220 David J. Malan: Dobře. 4 00:00:12,220 --> 00:00:13,950 To je CS50. 5 00:00:13,950 --> 00:00:18,560 To je týden pět pokračuje, a my nějaké dobré zprávy a špatné zprávy. 6 00:00:18,560 --> 00:00:21,140 Takže dobrá zpráva je, že CS50 zahajuje tento pátek. 7 00:00:21,140 --> 00:00:24,430 Máte-li zájem se k nám připojit, zamiřte do obvyklé adrese zde. 8 00:00:24,430 --> 00:00:28,670 Ještě lepší zpráva, ne přednáška letos v pondělí 13.. 9 00:00:28,670 --> 00:00:31,970 O něco méně lepší zprávy, kvíz nula je příští středu. 10 00:00:31,970 --> 00:00:33,840 Více informací může být naleznete na této adrese zde. 11 00:00:33,840 --> 00:00:36,340 A v příštích pár dní budeme vyplňovat prázdná místa 12 00:00:36,340 --> 00:00:39,234 s ohledem na pokojích že budeme mít vyhrazena. 13 00:00:39,234 --> 00:00:41,400 Lepší zprávou je, že tam budu být přezkum samozřejmě celé 14 00:00:41,400 --> 00:00:43,570 Zasedání letos Pondělí ve večerních hodinách. 15 00:00:43,570 --> 00:00:46,270 Zůstaňte naladěni na kurzu je Internetové stránky pro umístění a podrobnosti. 16 00:00:46,270 --> 00:00:49,290 Sekce, a to i když se jedná o dovolená, zobrazí se také setkat také. 17 00:00:49,290 --> 00:00:50,490 18 00:00:50,490 --> 00:00:52,940 Nejlepší novinky, přednáška příští pátek. 19 00:00:52,940 --> 00:00:56,220 Tak to je tradice nám mají podle osnov. 20 00:00:56,220 --> 00:00:58,100 Jen--, že to bude úžasné. 21 00:00:58,100 --> 00:01:02,510 Uvidíte věci, jako je datové struktury konstantní časové 22 00:01:02,510 --> 00:01:04,730 a hashovací tabulky a stromy a snaží se. 23 00:01:04,730 --> 00:01:07,150 A budeme mluvit o problémech narozenin. 24 00:01:07,150 --> 00:01:09,440 Celá parta věcí čeká příští pátek. 25 00:01:09,440 --> 00:01:11,212 26 00:01:11,212 --> 00:01:12,200 OK. 27 00:01:12,200 --> 00:01:13,190 Tak či onak. 28 00:01:13,190 --> 00:01:17,080 >> Takže připomenout, že jsme byli se zaměřením na obrázku o tom, co je 29 00:01:17,080 --> 00:01:18,980 vnitřní paměti našeho počítače. 30 00:01:18,980 --> 00:01:22,875 Takže je paměť RAM, nebo tam, kde programy existuje, když jste jim běží. 31 00:01:22,875 --> 00:01:25,215 Pokud poklepete na ikonu spustit nějaký program, 32 00:01:25,215 --> 00:01:27,520 nebo poklepejte na icon otevřít některé soubory, 33 00:01:27,520 --> 00:01:30,430 je nabitá z vašeho pevného disk nebo jednotku SSD 34 00:01:30,430 --> 00:01:34,190 do paměti RAM, Random Access Memory, kde žije, dokud se nevypne napájení, 35 00:01:34,190 --> 00:01:36,700 víko notebooku se zavře, nebo ukončení programu. 36 00:01:36,700 --> 00:01:38,960 >> Nyní, paměť, z které pravděpodobně máte 37 00:01:38,960 --> 00:01:41,950 1 GB v těchto dnech, 2 GB, nebo dokonce mnohem více, 38 00:01:41,950 --> 00:01:44,420 je obecně stanoveno pro daný program 39 00:01:44,420 --> 00:01:47,170 v tomto druhu pravoúhlého konceptuální model 40 00:01:47,170 --> 00:01:50,860 čímž máme zásobníku ve spodní části a spoustu dalších věcí, na vrcholu. 41 00:01:50,860 --> 00:01:53,140 Jde o to, na samém vrcholu jsme viděli na obrázku 42 00:01:53,140 --> 00:01:55,670 dříve, ale nikdy nemluvil o je takzvaný textu segmentu. 43 00:01:55,670 --> 00:01:58,419 Text segment je jen ozdobný způsob, jak říkat nuly a ty, které 44 00:01:58,419 --> 00:02:01,150 vytvořte aktuální zkompilovaný program. 45 00:02:01,150 --> 00:02:03,910 >> Takže když poklepete Microsoft Word v počítači Mac nebo PC, 46 00:02:03,910 --> 00:02:08,030 nebo při spuštění tečka lomítko Mario na Linux počítač v okně vašeho terminálu, 47 00:02:08,030 --> 00:02:12,460 nuly a ty, které se skládají Word a Mario jsou dočasně uloženy 48 00:02:12,460 --> 00:02:16,610 v paměti RAM počítače v takzvané Text segmentu pro konkrétní program. 49 00:02:16,610 --> 00:02:19,080 Pod tím jde inicializován a neinicializovaná údaje. 50 00:02:19,080 --> 00:02:22,655 To je věc jako globální proměnné, že jsme nepoužívá mnoho, 51 00:02:22,655 --> 00:02:24,910 ale občas máme měl globální proměnné 52 00:02:24,910 --> 00:02:28,819 nebo staticky definované řetězce, které je pevný kódované slova jako "ahoj" 53 00:02:28,819 --> 00:02:31,860 které nejsou přijata od uživatele , které jsou pevně do svého programu. 54 00:02:31,860 --> 00:02:34,230 >> Nyní, se ve spodní části jsme mají takzvaný stack. 55 00:02:34,230 --> 00:02:37,665 A stack, dosud jsme byli použitím, jaké druhy účely? 56 00:02:37,665 --> 00:02:39,706 57 00:02:39,706 --> 00:02:40,997 Co zásobník se používá? 58 00:02:40,997 --> 00:02:41,160 Jo? 59 00:02:41,160 --> 00:02:42,070 >> Diváků: Funkce. 60 00:02:42,070 --> 00:02:43,320 >> David J. Malan: Pro funkce? 61 00:02:43,320 --> 00:02:44,980 V jakém smyslu pro funkce? 62 00:02:44,980 --> 00:02:48,660 >> Diváků: Při volání funkce, argumenty jsou zkopírovány do zásobníku. 63 00:02:48,660 --> 00:02:49,660 >> David J. Malan: Přesně tak. 64 00:02:49,660 --> 00:02:52,650 Při volání funkce, její argumenty jsou zkopírovány do zásobníku. 65 00:02:52,650 --> 00:02:56,330 Takže nějaké X nebo Y či či B je že jste přechází do funkce 66 00:02:56,330 --> 00:02:58,680 jsou dočasně kladen na takzvaný zásobník, 67 00:02:58,680 --> 00:03:02,000 stejně jako jeden z Annenberg jídelna podnosy, a také věci, 68 00:03:02,000 --> 00:03:03,190 jako lokální proměnné. 69 00:03:03,190 --> 00:03:06,290 Pokud váš foo funkce nebo odkládacího funkce mají lokální proměnné, 70 00:03:06,290 --> 00:03:08,602 jako je teplota, ti dva skončit na zásobníku. 71 00:03:08,602 --> 00:03:11,560 Nyní budeme moc nemluvila o ně, ale tyto proměnné prostředí 72 00:03:11,560 --> 00:03:15,690 v dolní části jsme viděli před chvílí, když Byl jsem futzing na klávesnici jeden den 73 00:03:15,690 --> 00:03:20,050 a začal jsem přístup k věci jako argv 100 nebo argv 1000, 74 00:03:20,050 --> 00:03:22,320 Jen elements-- jsem zapomněl numbers-- ale, že 75 00:03:22,320 --> 00:03:24,330 neměli být přístupné mnou. 76 00:03:24,330 --> 00:03:26,581 Začali jsme vidět některé funky symboly na obrazovce. 77 00:03:26,581 --> 00:03:28,330 Byly to takzvané proměnné prostředí 78 00:03:28,330 --> 00:03:32,390 jako globální nastavení pro můj programu nebo pro svůj počítač, ne 79 00:03:32,390 --> 00:03:37,090 nesouvisí s poslední chyba, že jsme se bavili, 80 00:03:37,090 --> 00:03:39,670 Shellshock, že to bylo trápí poměrně málo počítačů. 81 00:03:39,670 --> 00:03:42,960 >> Nyní konečně, v dnešní zaměření budeme nakonec mít na haldě. 82 00:03:42,960 --> 00:03:44,864 Jedná se o další kus paměti. 83 00:03:44,864 --> 00:03:47,030 A v podstatě vše paměť je samé. 84 00:03:47,030 --> 00:03:48,040 Je to stejný hardware. 85 00:03:48,040 --> 00:03:49,956 Jsme jen trochu léčení různých klastrů 86 00:03:49,956 --> 00:03:51,460 bajtů pro různé účely. 87 00:03:51,460 --> 00:03:56,540 Haldy bude také tam, kde proměnné a paměti, které požadujete 88 00:03:56,540 --> 00:03:58,810 z operačního systému jsou dočasně uloženy. 89 00:03:58,810 --> 00:04:01,890 >> Ale je to trochu problém zde, stejně jako obraz znamená. 90 00:04:01,890 --> 00:04:05,261 Máme druh má dva lodě se srazit. 91 00:04:05,261 --> 00:04:08,010 Protože pokud budete používat více a více ze zásobníku, a jak vidíme dnes 92 00:04:08,010 --> 00:04:11,800 kupředu, pokud budete používat více a více haldy, jistě špatné věci se může stát. 93 00:04:11,800 --> 00:04:15,054 A skutečně, můžeme vyvolat, že úmyslně nebo neúmyslně. 94 00:04:15,054 --> 00:04:16,970 Takže cliffhanger posledního čas byl tento program, 95 00:04:16,970 --> 00:04:20,570 které neměly sloužit nějaký funkční účel jiný než ukázat 96 00:04:20,570 --> 00:04:24,750 jak jste jako zloduch může skutečně trvat Výhodou chyb v něčí programu 97 00:04:24,750 --> 00:04:28,460 a převzít program nebo dokonce Celý počítačový systém nebo server. 98 00:04:28,460 --> 00:04:31,660 Takže stačí, aby se podíval krátce vás Všimněte si, že nejdůležitější na dně 99 00:04:31,660 --> 00:04:34,510 se v příkazovém řádku argumenty, dle argv. 100 00:04:34,510 --> 00:04:38,480 A to je volání funkce f, v podstatě bezejmenná funkce nazvaná 101 00:04:38,480 --> 00:04:40,250 f, a to předáním argv [1]. 102 00:04:40,250 --> 00:04:43,960 >> Takže bez ohledu na slovo, že uživatel zadá na řádku za jménem tohoto programu, 103 00:04:43,960 --> 00:04:49,310 a pak libovolná funkce nahoru top, f, se v řetězci, AKA char *, 104 00:04:49,310 --> 00:04:51,720 jak jsme začali diskutovat, a to jen nazývá "bar". 105 00:04:51,720 --> 00:04:53,310 Ale my jsme to mohli nazvat cokoliv. 106 00:04:53,310 --> 00:04:57,470 A pak prohlašuje, uvnitř f, pole znaků 107 00:04:57,470 --> 00:04:59,930 volal C-- 12 těchto znaků. 108 00:04:59,930 --> 00:05:03,580 >> Nyní, podle příběhu, který jsem říkal před chvílí, kdy v paměti 109 00:05:03,580 --> 00:05:06,720 je c, nebo jsou ty 12 znaků skončí? 110 00:05:06,720 --> 00:05:07,570 Jen aby bylo jasno. 111 00:05:07,570 --> 00:05:08,070 Jo? 112 00:05:08,070 --> 00:05:08,590 >> Diváků: Na zásobníku. 113 00:05:08,590 --> 00:05:09,420 >> David J. Malan: Na zásobníku. 114 00:05:09,420 --> 00:05:10,720 Takže c je lokální proměnná. 115 00:05:10,720 --> 00:05:14,079 Ptáme se na 12 znaků nebo 12 bajtů. 116 00:05:14,079 --> 00:05:16,120 Ti, kteří se skončí na takzvané zásobníku. 117 00:05:16,120 --> 00:05:18,530 Teď konečně je to jiná funkce to je vlastně docela užitečné, 118 00:05:18,530 --> 00:05:20,571 ale my jsme opravdu použít to sami, strncopy. 119 00:05:20,571 --> 00:05:21,550 120 00:05:21,550 --> 00:05:25,200 To znamená, že řetězec kopii, ale pouze n dopisy, n znaků. 121 00:05:25,200 --> 00:05:31,990 Tak n znaky budou kopírovat z baru do cca. 122 00:05:31,990 --> 00:05:32,980 A kolik? 123 00:05:32,980 --> 00:05:34,110 Délka tyče. 124 00:05:34,110 --> 00:05:36,330 Takže jinými slovy, že jeden řádek, strncopy, 125 00:05:36,330 --> 00:05:39,500 bude kopírovat účinně bar do cca. 126 00:05:39,500 --> 00:05:42,340 >> Nyní, jen trochu předvídat Ponaučení z tohoto příběhu, 127 00:05:42,340 --> 00:05:44,750 to, co je zde potenciálně problematické? 128 00:05:44,750 --> 00:05:49,710 I když jsme zkontrolovat délku tyče a její předání do strncopy, 129 00:05:49,710 --> 00:05:53,145 Jaký je váš gut říkáš, je stále zlomený o tomto programu? 130 00:05:53,145 --> 00:05:54,410 131 00:05:54,410 --> 00:05:55,220 Jo? 132 00:05:55,220 --> 00:05:57,491 >> Diváků: Nezahrnuje prostor pro nulový znak. 133 00:05:57,491 --> 00:05:59,990 David J. Malan: Nezahrnuje prostor pro nulový znak. 134 00:05:59,990 --> 00:06:02,073 Potenciálně, na rozdíl od v běžná minulá praxe my ani 135 00:06:02,073 --> 00:06:04,810 mít tolik jako plus 1 na ubytovat, že znakem null. 136 00:06:04,810 --> 00:06:06,649 Ale je to ještě horší, než to. 137 00:06:06,649 --> 00:06:07,940 Co jiného jsme nedaří dělat? 138 00:06:07,940 --> 00:06:08,432 Jo? 139 00:06:08,432 --> 00:06:09,307 >> Diváků: [neslyšitelné] 140 00:06:09,307 --> 00:06:15,440 141 00:06:15,440 --> 00:06:16,440 David J. Malan: Perfect. 142 00:06:16,440 --> 00:06:18,490 Jsme pevně dáno 12 dost libovolně. 143 00:06:18,490 --> 00:06:19,497 144 00:06:19,497 --> 00:06:21,330 To není tak moc problém, ale skutečnost, 145 00:06:21,330 --> 00:06:25,630 že jsme ani kontrolovat, zda Délka tyče je menší než 12, 146 00:06:25,630 --> 00:06:28,530 v tom případě to bude bezpečné, aby to do paměti 147 00:06:28,530 --> 00:06:30,260 volal c, že ​​jsme přiděleny. 148 00:06:30,260 --> 00:06:32,960 Ve skutečnosti, pokud je jako bar 20 znaků, 149 00:06:32,960 --> 00:06:39,010 Zobrazí se tato funkce se kopírování 20 znaků z baru do C, čímž se 150 00:06:39,010 --> 00:06:41,310 přičemž alespoň 8 bajtů že by nemělo být. 151 00:06:41,310 --> 00:06:42,690 To je důsledek tady. 152 00:06:42,690 --> 00:06:44,347 >> Takže ve zkratce, rozbité programu. 153 00:06:44,347 --> 00:06:45,180 Není tak velký problém. 154 00:06:45,180 --> 00:06:46,360 Možná, že máte chybu segmentace. 155 00:06:46,360 --> 00:06:47,651 Všichni jsme měli chyby v programech. 156 00:06:47,651 --> 00:06:50,196 My všichni mohou mít chyby programů právě teď. 157 00:06:50,196 --> 00:06:51,320 Ale co je důsledek? 158 00:06:51,320 --> 00:06:54,390 No, tady je zvětšené verze že obraz paměti mého počítače. 159 00:06:54,390 --> 00:06:56,230 Jedná se o spodní část mého stacku. 160 00:06:56,230 --> 00:06:59,644 A skutečně, na samém dně je to, co je volal rodič rutina zásobník, ozdobný způsob, jak 161 00:06:59,644 --> 00:07:00,560 říct, že je to hlavní. 162 00:07:00,560 --> 00:07:03,772 Tak, že ten, kdo nazývá funkce f, že mluvíme o. 163 00:07:03,772 --> 00:07:05,230 Tak tohle je dno zásobníku. 164 00:07:05,230 --> 00:07:06,640 Zpáteční adresa je něco nového. 165 00:07:06,640 --> 00:07:08,810 Je to vždy tam, vždy v tomto obrázku. 166 00:07:08,810 --> 00:07:10,440 Právě jsme se nikdy obrátil pozornost k tomu. 167 00:07:10,440 --> 00:07:15,290 Vzhledem k tomu, že ukáže, že způsob, jakým funguje, je c , že když jeden volání funkce druhého, 168 00:07:15,290 --> 00:07:18,780 nejen že tvrzení, podle které Funkce tlačil do fronty, 169 00:07:18,780 --> 00:07:22,470 nejen že funkce je místní proměnné tlačil do fronty, 170 00:07:22,470 --> 00:07:26,820 něco jako zpáteční adresa získá také dát do zásobníku. 171 00:07:26,820 --> 00:07:33,330 Konkrétně, pokud hlavní volá foo, hlavní je vlastní adresu v paměti, vůl něco, 172 00:07:33,330 --> 00:07:38,240 efektivně dostane dát do zásobníku tak, že je-li f provádí spuštěním 173 00:07:38,240 --> 00:07:43,630 ví, kam skočit zpět do textu segmentu, aby mohl pokračovat provádění. 174 00:07:43,630 --> 00:07:47,760 >> Takže když jsme tady koncepčně, V hlavní, pak f volána. 175 00:07:47,760 --> 00:07:50,200 Jak se f vědět, kdo na ruční ovládání zpět? 176 00:07:50,200 --> 00:07:52,020 No, tento malý strouhanka v červené tady, 177 00:07:52,020 --> 00:07:54,978 volal zpáteční adresa, to prostě kontroly, co je to zpáteční adresa? 178 00:07:54,978 --> 00:07:57,039 Oh, nech mě skočit zpět na hlavní zde. 179 00:07:57,039 --> 00:07:59,080 A to je trochu jako zjednodušující, 180 00:07:59,080 --> 00:08:00,750 protože nul a jedniček Pro Main jsou technicky 181 00:08:00,750 --> 00:08:01,967 tady v tech segmentu. 182 00:08:01,967 --> 00:08:03,800 Ale to je nápad. f prostě musí vědět, co 183 00:08:03,800 --> 00:08:06,680 tam, kde řízení nakonec se vrátí. 184 00:08:06,680 --> 00:08:09,790 >> Ale způsob, jakým počítače již dlouho stanoveno věci 185 00:08:09,790 --> 00:08:12,320 jako lokální proměnné a argumenty jako je tato. 186 00:08:12,320 --> 00:08:17,180 Takže v horní části obrázku v modrá je stack frame pro f, takže vše 187 00:08:17,180 --> 00:08:19,630 na paměti, že f konkrétně je používáte. 188 00:08:19,630 --> 00:08:22,990 Tak tedy, všimněte si, že Bar je na tomto obrázku. 189 00:08:22,990 --> 00:08:23,980 Bar byl jeho argument. 190 00:08:23,980 --> 00:08:27,240 A tvrdí, že argumenty Funkce tlačil do zásobníku. 191 00:08:27,240 --> 00:08:29,910 A c, samozřejmě, je Také na tomto obrázku. 192 00:08:29,910 --> 00:08:33,520 >> A jen pro Značky účely, Všimněte si, v levém horním rohu 193 00:08:33,520 --> 00:08:37,020 je to, co by c držáku 0 a pak mírně vpravo dolů 194 00:08:37,020 --> 00:08:38,220 je c držák 11. 195 00:08:38,220 --> 00:08:41,240 Takže jinými slovy, ktere si lze predstavit že tam je mřížka z bytů 196 00:08:41,240 --> 00:08:44,380 tam, z nichž první je vlevo nahoře, dole, z nichž 197 00:08:44,380 --> 00:08:48,360 je poslední z těchto 12 bytů. 198 00:08:48,360 --> 00:08:49,930 >> Ale teď se snaží rychle vpřed. 199 00:08:49,930 --> 00:08:55,580 Co se má stát, pokud jsme se projít v řetězci baru, který je delší než c? 200 00:08:55,580 --> 00:08:59,130 A my nejsme kontrole, zda je to opravdu déle než 12 let. 201 00:08:59,130 --> 00:09:03,146 Která část obrázku bude přepsány po bajtech 0, 1, 2, 3, 202 00:09:03,146 --> 00:09:07,890 dot dot dot, 11, a pak se špatný, 12, 13 až 19? 203 00:09:07,890 --> 00:09:11,820 Co se bude dít tady, pokud vyvodit z objednání 204 00:09:11,820 --> 00:09:14,790 že držák c 0 je na vrcholu c držák 11 je trochu dolů 205 00:09:14,790 --> 00:09:15,812 k pořádku? 206 00:09:15,812 --> 00:09:16,796 Jo? 207 00:09:16,796 --> 00:09:19,260 >> DIVÁKŮ: No, to se děje přepsat char * bar. 208 00:09:19,260 --> 00:09:22,260 >> David J. Malan: Jo, vypadá to, že budete přepsat char * bar. 209 00:09:22,260 --> 00:09:26,245 A co je horší, pokud jste poslali opravdu dlouho řetězec, můžete dokonce přepsat, co? 210 00:09:26,245 --> 00:09:27,460 211 00:09:27,460 --> 00:09:28,570 Zpáteční adresa. 212 00:09:28,570 --> 00:09:31,380 Což je opět stejně jako strouhanka říci programu, kde 213 00:09:31,380 --> 00:09:34,060 se vrátit, když f se provádí volána. 214 00:09:34,060 --> 00:09:37,140 >> Takže to, co protivníci obvykle do je v případě, že narazí na program 215 00:09:37,140 --> 00:09:41,290 , že jsou zvědaví, zda je využívání, buggy takovým způsobem, 216 00:09:41,290 --> 00:09:43,550 že on nebo ona může mít Výhodou této chybě, 217 00:09:43,550 --> 00:09:45,720 většinou se jim nedostává to hned napoprvé. 218 00:09:45,720 --> 00:09:48,590 Prostě začít vysílat, například, náhodné řetězce do svého programu, 219 00:09:48,590 --> 00:09:50,260 zda na klávesnici, nebo řečeno, že pravděpodobně 220 00:09:50,260 --> 00:09:52,740 napsat malý program, jen automaticky generovat řetězce, 221 00:09:52,740 --> 00:09:55,430 a začít bušit na programu odeslání v mnoha různých vstupů 222 00:09:55,430 --> 00:09:56,340 v různých délkách. 223 00:09:56,340 --> 00:09:58,990 >> Jakmile vaše zhroucení programu, to je úžasná věc. 224 00:09:58,990 --> 00:10:01,020 Protože to znamená, že nebo ona zjistila, 225 00:10:01,020 --> 00:10:02,660 co je asi opravdu chyba. 226 00:10:02,660 --> 00:10:05,830 A pak se můžete dostat chytřejší a začít soustředit úžeji 227 00:10:05,830 --> 00:10:07,420 o tom, jak využít tuto chybu. 228 00:10:07,420 --> 00:10:11,480 Konkrétně, co se on nebo ona by mohla udělat, je poslat, v nejlepším případě, ahoj. 229 00:10:11,480 --> 00:10:12,210 Žádný velký problém. 230 00:10:12,210 --> 00:10:14,750 Je to řetězec, který je dostatečně krátký. 231 00:10:14,750 --> 00:10:18,100 Ale co když on nebo ona pošle, a my zobecnit jako, 232 00:10:18,100 --> 00:10:20,890 Útok code-- tak nulami a ty, které se dělat věci, 233 00:10:20,890 --> 00:10:25,150 jako rm-rf, že odstraní vše z pevného disku nebo rozesílání spamu 234 00:10:25,150 --> 00:10:27,000 nebo nějak napadnout počítač? 235 00:10:27,000 --> 00:10:29,570 >> Takže v případě, každý z nich písmena A právě představuje 236 00:10:29,570 --> 00:10:32,380 koncepčně, útok, útok, útok, útok, nějaký špatný kód 237 00:10:32,380 --> 00:10:36,410 že někdo jiný napsal, ale pokud tato osoba je dost chytrý, 238 00:10:36,410 --> 00:10:40,790 nejen zahrnovat všechny z těch RM-RFS, ale také 239 00:10:40,790 --> 00:10:46,100 mít jeho nebo její poslední pár bajtů je číslo, které odpovídá 240 00:10:46,100 --> 00:10:50,540 na adresu jeho nebo její vlastní útok kód 241 00:10:50,540 --> 00:10:53,820 že on nebo ona prošla v několika tím, že ji na výzvu, 242 00:10:53,820 --> 00:10:58,760 můžete efektivně trik počítač do všímat, když je f provádí provádění, 243 00:10:58,760 --> 00:11:02,400 oh, to je čas, abych se skákat zpět na červenou zpáteční adresu. 244 00:11:02,400 --> 00:11:06,070 Ale protože on nebo ona má nějak překrývaly, že zpáteční adresu 245 00:11:06,070 --> 00:11:09,602 s vlastním číslem, a oni jsou dost chytří na to 246 00:11:09,602 --> 00:11:11,560 aby jste nakonfigurovali, že číslo, které chcete odkazovat, jako vy 247 00:11:11,560 --> 00:11:13,740 viz v super nahoru levá tam koutek, 248 00:11:13,740 --> 00:11:18,020 skutečná adresa počítače Vzpomínka na některé jejich útoku kódu, 249 00:11:18,020 --> 00:11:21,740 špatný člověk může oklamat počítač k vykonání své vlastní kód. 250 00:11:21,740 --> 00:11:23,700 >> A ten kód znovu, může to být cokoliv. 251 00:11:23,700 --> 00:11:26,120 To je obecně nazýván shell kód, který je právě 252 00:11:26,120 --> 00:11:29,030 způsob, jak říct, že to není obecně něco tak jednoduchého jako rm-rf. 253 00:11:29,030 --> 00:11:32,340 Je to vlastně něco jako Bash, nebo skutečný program, který mu dává 254 00:11:32,340 --> 00:11:37,230 nebo její programové řízení k provedení cokoli jiného, ​​co chtějí. 255 00:11:37,230 --> 00:11:40,210 Takže ve zkratce, to vše pochází z prosté skutečnosti, 256 00:11:40,210 --> 00:11:44,490 že tato chyba se netýkala kontrolu hranice svého pole. 257 00:11:44,490 --> 00:11:47,250 A proto, že na cestě počítače práce je to, že 258 00:11:47,250 --> 00:11:49,430 použít zásobník z efektivně, koncepčně, 259 00:11:49,430 --> 00:11:54,830 Spodní nahoru, ale pak se prvky zatlačíte do zásobníku roste shora dolů, 260 00:11:54,830 --> 00:11:56,624 To je neuvěřitelně problematické. 261 00:11:56,624 --> 00:11:58,290 Nyní existují způsoby, jak obejít to. 262 00:11:58,290 --> 00:12:00,800 A upřímně řečeno, tam jsou jazyky s níž se tento problém vyřešit. 263 00:12:00,800 --> 00:12:03,100 Java je imunní, například, k této konkrétní otázce. 264 00:12:03,100 --> 00:12:04,110 Vzhledem k tomu, že vám nedávají odkazy. 265 00:12:04,110 --> 00:12:05,943 Oni vám nedávají přímé adresy paměti. 266 00:12:05,943 --> 00:12:08,560 Tak s tímto výkonem, že máme na nic sahat do paměti 267 00:12:08,560 --> 00:12:11,580 chceme, je sice velké riziko. 268 00:12:11,580 --> 00:12:12,430 >> Takže dávat pozor. 269 00:12:12,430 --> 00:12:14,596 Pokud je, upřímně řečeno, v měsících nebo let přijít, kdykoliv 270 00:12:14,596 --> 00:12:17,740 budete číst o nějakém zneužívání programu nebo serveru, 271 00:12:17,740 --> 00:12:22,370 Pokud jste někdy vidět náznak něčeho jako útok přetečení vyrovnávací paměti, 272 00:12:22,370 --> 00:12:25,390 nebo přetečení zásobníku je jiný typ útoku, podobně jako v duchu, 273 00:12:25,390 --> 00:12:28,770 stejně jako inspiruje webové stránky jméno, pokud ho znáte, 274 00:12:28,770 --> 00:12:33,170 je to všechno mluví jen o přetékání velikost nějakého znaku 275 00:12:33,170 --> 00:12:36,200 pole nebo některá pole obecněji. 276 00:12:36,200 --> 00:12:38,822 Jakékoliv dotazy, pak, o tom myslíte? 277 00:12:38,822 --> 00:12:39,780 Nezkoušejte to doma. 278 00:12:39,780 --> 00:12:41,620 279 00:12:41,620 --> 00:12:42,300 >> V pořádku. 280 00:12:42,300 --> 00:12:47,270 Takže malloc dosud byla naše nová přítel v tom, že můžeme přidělit paměť 281 00:12:47,270 --> 00:12:50,540 že nemusí nutně vědět, předem, že chceme, abychom nemuseli mít 282 00:12:50,540 --> 00:12:52,920 na pevný kód do našich čísla programů, jako je 12 let. 283 00:12:52,920 --> 00:12:55,550 Jakmile uživatel nám říká, kolik Data on nebo ona chce na vstup, 284 00:12:55,550 --> 00:12:58,000 můžeme malloc tolik paměti. 285 00:12:58,000 --> 00:13:01,484 >> Takže malloc to dopadá, na míry jsme se ji používat, 286 00:13:01,484 --> 00:13:03,900 výslovně naposledy, a pak vy jste se používat 287 00:13:03,900 --> 00:13:08,160 pro getString nevědomky pro několik týdnů, všechny paměti malloc je 288 00:13:08,160 --> 00:13:09,820 pochází z takzvaného haldy. 289 00:13:09,820 --> 00:13:13,852 A to je důvod, proč getString, například, může alokovat paměť dynamicky 290 00:13:13,852 --> 00:13:16,060 aniž by věděl, co jste bude psát v předstihu, 291 00:13:16,060 --> 00:13:21,520 předat zpět ukazatel na paměti, že, a že paměť je stále na vás, aby, 292 00:13:21,520 --> 00:13:24,080 i po getString vrátí. 293 00:13:24,080 --> 00:13:27,450 Protože odvolání po tom všem Zásobník je neustále jít nahoru a dolů, 294 00:13:27,450 --> 00:13:27,950 nahoru a dolů. 295 00:13:27,950 --> 00:13:30,230 A jakmile to jde dolů, to znamená, že jakýkoli paměť 296 00:13:30,230 --> 00:13:33,030 tato funkce použita, neměl být používán někým jiným. 297 00:13:33,030 --> 00:13:34,570 Je to hodnoty odpadky teď. 298 00:13:34,570 --> 00:13:36,120 >> Ale hromada je tady. 299 00:13:36,120 --> 00:13:39,360 A co je hezké o malloc je to, že když malloc přiděluje paměť tady, 300 00:13:39,360 --> 00:13:42,070 to není ovlivněn, protože z větší části tím, že v zásobníku. 301 00:13:42,070 --> 00:13:46,000 A tak nějaká funkce přístup paměť, která byla malloc'd, 302 00:13:46,000 --> 00:13:49,120 ani funkce jako je getString, i poté, co se vrátí. 303 00:13:49,120 --> 00:13:51,700 >> Nyní hovořit malloc je zdarma. 304 00:13:51,700 --> 00:13:53,900 A skutečně, na pravidlo, které je třeba začít přijetí 305 00:13:53,900 --> 00:13:58,950 je nějaký, některý, nějaký čas používat malloc musíte sami používat zdarma, případně, 306 00:13:58,950 --> 00:14:00,280 na stejném ukazateli. 307 00:14:00,280 --> 00:14:03,289 Celou tu dobu jsme se psát buggy, buggy kód, z mnoha důvodů. 308 00:14:03,289 --> 00:14:05,580 Ale jeden z nich byl pomocí knihovny CS50, které 309 00:14:05,580 --> 00:14:09,010 sama o sobě je záměrně buggy, to nevrací paměť. 310 00:14:09,010 --> 00:14:11,410 Pokaždé, když jsem volal getString během posledních několika týdnů 311 00:14:11,410 --> 00:14:13,870 ptáme se provozní systém, Linux, pro paměť. 312 00:14:13,870 --> 00:14:15,780 A vy jste ani jednou ho dal zpátky. 313 00:14:15,780 --> 00:14:17,730 A to není, v praxe, dobrá věc. 314 00:14:17,730 --> 00:14:20,330 >> A Valgrind, jeden z nástroje zavedené v pset 4, 315 00:14:20,330 --> 00:14:22,900 je především o který vám pomůže nyní najít chyby, jako že. 316 00:14:22,900 --> 00:14:27,060 Ale naštěstí pro pset 4 nepotřebujete pouze v CS50 knihovnu nebo getString. 317 00:14:27,060 --> 00:14:31,220 Takže nějaké chyby spojené s pamětí jsou nakonec bude váš vlastní. 318 00:14:31,220 --> 00:14:34,060 >> Takže malloc je více než jen vhodné pro tento účel. 319 00:14:34,060 --> 00:14:37,420 Můžeme vlastně teď řešit zásadně odlišné problémy, 320 00:14:37,420 --> 00:14:41,640 a zásadně řešit problémy více efektivně, jako za týden nula slibu. 321 00:14:41,640 --> 00:14:44,720 Až potud je to sexy struktura dat jsme měli. 322 00:14:44,720 --> 00:14:47,804 A datové struktury jsem na mysli způsob konceptualizace paměti 323 00:14:47,804 --> 00:14:50,720 způsobem, který přesahuje jen říkám, to je int, to je char. 324 00:14:50,720 --> 00:14:52,930 Můžeme začít clusteru věci dohromady. 325 00:14:52,930 --> 00:14:54,460 >> Takže pole vypadal takto. 326 00:14:54,460 --> 00:14:57,270 A co je klíčem k Pole je, že vám dává 327 00:14:57,270 --> 00:14:59,724 back-to-back kusy paměti, z nichž každá 328 00:14:59,724 --> 00:15:02,765 bude stejného typu, int, int, int, int nebo char, char, char, 329 00:15:02,765 --> 00:15:03,330 char. 330 00:15:03,330 --> 00:15:04,496 Ale je tu několik stinné stránky. 331 00:15:04,496 --> 00:15:06,570 To například, je pole o velikosti šest. 332 00:15:06,570 --> 00:15:10,650 Představte si, že vyplnění tohoto pole se šesti čísla a potom, z jakéhokoli důvodu, 333 00:15:10,650 --> 00:15:13,187 Vaše uživatelské chce dát jste sedmina číslo. 334 00:15:13,187 --> 00:15:14,020 Kde si dát? 335 00:15:14,020 --> 00:15:15,490 336 00:15:15,490 --> 00:15:18,990 >> Jaké je řešení, pokud máte vytvořil řadu na zásobníku, 337 00:15:18,990 --> 00:15:22,030 Například, pouze s týden dvě notace, že jsme uvedli, 338 00:15:22,030 --> 00:15:23,730 hranatých závorek s číslem uvnitř? 339 00:15:23,730 --> 00:15:25,160 340 00:15:25,160 --> 00:15:27,260 No, máš šest Čísla v těchto krabicích. 341 00:15:27,260 --> 00:15:28,530 Co by vaše instinkty být? 342 00:15:28,530 --> 00:15:29,973 Kam byste chtěli dát? 343 00:15:29,973 --> 00:15:30,860 >> Diváků: [neslyšitelné] 344 00:15:30,860 --> 00:15:31,315 >> David J. Malan: Sorry? 345 00:15:31,315 --> 00:15:32,380 >> Diváků: Dejte ji na konci. 346 00:15:32,380 --> 00:15:33,796 >> David J. Malan: Dejte ji na konci. 347 00:15:33,796 --> 00:15:35,880 Tak jen něco málo přes doprava, mimo tento box. 348 00:15:35,880 --> 00:15:38,710 Což by bylo hezké, ale je to Ukazuje se, můžete to udělat. 349 00:15:38,710 --> 00:15:41,350 Protože pokud jste nepožádal pro tento kus paměti, 350 00:15:41,350 --> 00:15:44,490 mohlo by to být náhodou, že tento se používá nějaké jiné proměnné 351 00:15:44,490 --> 00:15:45,030 úplně. 352 00:15:45,030 --> 00:15:49,210 Vzpomeňte si týden nebo tak, když jsme položili z Zamyla a DaviN a Gabe je jmény 353 00:15:49,210 --> 00:15:49,930 v paměti. 354 00:15:49,930 --> 00:15:51,638 Byli doslova zády k sobě k sobě. 355 00:15:51,638 --> 00:15:53,550 Takže nemůžeme být nutně věřím, že cokoliv je 356 00:15:53,550 --> 00:15:55,800 tady je k dispozici pro mě použití. 357 00:15:55,800 --> 00:15:56,990 >> Takže co jiného můžete dělat? 358 00:15:56,990 --> 00:16:00,282 No, jakmile si uvědomil, vás Potřebujete pole o velikosti sedm, 359 00:16:00,282 --> 00:16:02,490 můžete jen vytvořit pole o velikosti sedm pak použijte 360 00:16:02,490 --> 00:16:05,950 cyklu for nebo while, zkopírujte jej do nového pole, 361 00:16:05,950 --> 00:16:09,680 a pak nějak prostě zbavit Toto pole nebo prostě přestaňte jej používat. 362 00:16:09,680 --> 00:16:12,130 Ale to není příliš efektivní. 363 00:16:12,130 --> 00:16:15,340 Stručně řečeno, pole nenechte dynamicky měnit velikost. 364 00:16:15,340 --> 00:16:17,900 >> Takže na jedné straně se dostanete náhodný přístup, což je úžasné. 365 00:16:17,900 --> 00:16:20,108 Vzhledem k tomu, že nám umožňuje dělat věci, jako rozděl a panuj, 366 00:16:20,108 --> 00:16:23,100 binární vyhledávání, všichni máme mluvil o na obrazovce zde. 367 00:16:23,100 --> 00:16:24,950 Ale ty barvy se do kouta. 368 00:16:24,950 --> 00:16:27,810 Jakmile stisknete konec tvého pole, 369 00:16:27,810 --> 00:16:29,980 co musíte udělat velmi drahý provoz 370 00:16:29,980 --> 00:16:33,910 nebo napsat spoustu kódu aby se vypořádat s tímto problémem. 371 00:16:33,910 --> 00:16:36,680 >> Co když místo toho jsme měli něco jako seznam, 372 00:16:36,680 --> 00:16:38,820 nebo spojový seznam se konkrétně jedná? 373 00:16:38,820 --> 00:16:41,930 Co když místo toho, aby obdélníky zády k sobě k sobě, 374 00:16:41,930 --> 00:16:45,730 máme obdélníky, které opustí malý trochu manévrovací prostor mezi nimi? 375 00:16:45,730 --> 00:16:49,670 A i když jsem se vyvodit tento obrazu nebo přizpůsobit tento obrázek 376 00:16:49,670 --> 00:16:54,696 z jednoho z textů, zde se vrátí do zády k sobě velmi spořádaně, ve skutečnosti, 377 00:16:54,696 --> 00:16:56,820 jeden z těchto obdélníků by mohl být tady v paměti. 378 00:16:56,820 --> 00:16:58,028 Jedním z nich by mohl být tady. 379 00:16:58,028 --> 00:17:00,420 Jedním z nich by mohla být tady, sem, a tak dále. 380 00:17:00,420 --> 00:17:02,910 >> Ale co když jsme vycházeli, v tomto případě, šipky 381 00:17:02,910 --> 00:17:05,650 to nějak propojit je obdélníky dohromady? 382 00:17:05,650 --> 00:17:08,170 Skutečně jsme viděli technický ztělesnění šipkou. 383 00:17:08,170 --> 00:17:09,839 384 00:17:09,839 --> 00:17:13,710 Co jsme v poslední dny, že pod kapotou, 385 00:17:13,710 --> 00:17:15,210 vyjadřující šipky? 386 00:17:15,210 --> 00:17:16,290 387 00:17:16,290 --> 00:17:17,349 Ukazatel, že jo? 388 00:17:17,349 --> 00:17:19,780 >> Co když místo jen uložení čísla, 389 00:17:19,780 --> 00:17:23,130 jako 9, 17, 22, 26, 34, co kdybychom neukládá 390 00:17:23,130 --> 00:17:27,079 pouze číslo, ale ukazatel u každé takové číslo? 391 00:17:27,079 --> 00:17:30,690 Tak, že podobně jako byste závit jehlu přes spoustu látky, 392 00:17:30,690 --> 00:17:32,950 nějak vázání věci společně, podobně mohou 393 00:17:32,950 --> 00:17:35,550 jsme se s ukazateli, jako je inkarnoval šipkami zde 394 00:17:35,550 --> 00:17:38,550 druh tkát spolu tyto jednotlivé obdélníky 395 00:17:38,550 --> 00:17:41,780 tím, že účinně pomocí ukazatele vedle každého čísla, které 396 00:17:41,780 --> 00:17:46,065 poukazuje na některé další číslo, které poukazuje na zase nějaký další číslo? 397 00:17:46,065 --> 00:17:47,940 Takže jinými slovy, to, co Pokud bychom skutečně chtěli 398 00:17:47,940 --> 00:17:49,820 realizovat něco takového? 399 00:17:49,820 --> 00:17:53,610 Tak bohužel, tyto obdélníky Aspoň že ten s 9, 17, 22, 400 00:17:53,610 --> 00:17:57,040 a tak dále, to jsou již pěkné náměstí s jednotlivými čísly. 401 00:17:57,040 --> 00:17:59,960 Spodní, obdélník pod 9, například, 402 00:17:59,960 --> 00:18:04,330 představuje to, co by mělo být ukazatel, 32 bitů. 403 00:18:04,330 --> 00:18:09,460 Teď jsem ještě neví jakýkoliv datový typ v jazyce C, které vám umožní nejen int 404 00:18:09,460 --> 00:18:11,630 ale ukazatel úplně. 405 00:18:11,630 --> 00:18:15,020 >> Takže jaké je řešení, pokud chceme vymyslet vlastní odpověď na to? 406 00:18:15,020 --> 00:18:15,760 Jo? 407 00:18:15,760 --> 00:18:16,640 >> Diváků: [neslyšitelné] 408 00:18:16,640 --> 00:18:17,360 >> David J. Malan: Co je to? 409 00:18:17,360 --> 00:18:17,880 >> Diváků: Nová struktura. 410 00:18:17,880 --> 00:18:19,590 >> David J. Malan: Jo, tak proč Co kdybychom vytvořit novou strukturu, 411 00:18:19,590 --> 00:18:20,920 nebo C, struct? 412 00:18:20,920 --> 00:18:25,990 Viděli jsme structs dříve, pokud krátce, kde jsme se zabývali strukturou studentů 413 00:18:25,990 --> 00:18:27,780 takhle, který měl jméno a domu. 414 00:18:27,780 --> 00:18:31,980 V pset 3 útěk, kterou jste použili celý banda structs-- GRect a GOvals 415 00:18:31,980 --> 00:18:34,810 že Stanford vytvořen klastr informace dohromady. 416 00:18:34,810 --> 00:18:38,580 Tak co, vezmeme-li stejný nápad klíčová slova "typedef" a "struct", 417 00:18:38,580 --> 00:18:42,890 a pak nějaký student-specifické věci, a vyvíjet se to do následujících: 418 00:18:42,890 --> 00:18:46,210 typedef struct node-- a uzel je jen velmi obecný produkt počítačové vědy 419 00:18:46,210 --> 00:18:49,980 termín pro něco, co v datové struktuře, Kontejner v datové struktuře. 420 00:18:49,980 --> 00:18:53,900 Uzel Tvrdím, bude mít int n, naprosto jednoduché, 421 00:18:53,900 --> 00:18:58,810 a pak se trochu záhadně, Tento druhý řádek, struct uzel * další. 422 00:18:58,810 --> 00:19:01,300 Ale méně z technického hlediska, co je to druhý řádek 423 00:19:01,300 --> 00:19:02,980 kódu uvnitř složených závorek? 424 00:19:02,980 --> 00:19:03,737 Jo? 425 00:19:03,737 --> 00:19:04,851 >> Diváků: [neslyšitelné] 426 00:19:04,851 --> 00:19:06,600 David J. Malan: ukazatel do jiného uzlu. 427 00:19:06,600 --> 00:19:09,910 Takže sice syntaxe trochu záhadné. 428 00:19:09,910 --> 00:19:13,250 Ale pokud budete číst doslova, Další je název proměnné. 429 00:19:13,250 --> 00:19:14,410 Jaký je její datový typ? 430 00:19:14,410 --> 00:19:18,206 Je to trochu upovídaný tentokrát, ale to je typu struct uzel *. 431 00:19:18,206 --> 00:19:22,960 Kdykoliv jsme viděli něco hvězdu, která znamená, že je ukazatel na tento typ dat. 432 00:19:22,960 --> 00:19:26,810 Takže další je zřejmě ukazatel na struct uzel. 433 00:19:26,810 --> 00:19:28,310 >> A teď, co je uzel struct? 434 00:19:28,310 --> 00:19:31,044 Dobře si všimněte, vidíš ty, Stejná slova v pravém horním rohu. 435 00:19:31,044 --> 00:19:33,960 A skutečně, můžete také vidět slovo "Uzel" tady dole v levém dolním rohu. 436 00:19:33,960 --> 00:19:35,640 A to je vlastně jen pohodlí. 437 00:19:35,640 --> 00:19:39,930 Všimněte si, že v naší definici studenta je tu slovo "žák" pouze jednou. 438 00:19:39,930 --> 00:19:42,510 A to proto, že student Objekt nebyl zcela evidentní. 439 00:19:42,510 --> 00:19:45,340 Není nic uvnitř studenta že je třeba, aby ukazoval na jiný student, 440 00:19:45,340 --> 00:19:45,610 persay. 441 00:19:45,610 --> 00:19:47,630 To by bylo trochu divný v reálném světě. 442 00:19:47,630 --> 00:19:50,880 >> Ale s uzlem ve spojen seznam, my chceme uzel 443 00:19:50,880 --> 00:19:53,970 jako referenční k podobným předmětem. 444 00:19:53,970 --> 00:19:57,900 A tak zjistíte zde změna není jen to, co je uvnitř složených závorek. 445 00:19:57,900 --> 00:20:00,800 Ale přidat slovo "uzel" v horní části, jakož i 446 00:20:00,800 --> 00:20:02,930 přidáním na dno namísto "studenta." 447 00:20:02,930 --> 00:20:06,000 A to je jen technický detail tak, že, opět Vaše datová struktura 448 00:20:06,000 --> 00:20:11,380 může být samo-referenční, takže uzel může ukazovat na jiného takového uzlu. 449 00:20:11,380 --> 00:20:13,840 >> Takže to, co je v konečném důsledku bude znamenat pro nás? 450 00:20:13,840 --> 00:20:17,560 No, jeden, tohle dovnitř je obsah našeho uzlu. 451 00:20:17,560 --> 00:20:19,360 To, co tady, vpravo nahoře, je tak 452 00:20:19,360 --> 00:20:20,860 že opět můžeme odkazovat na sebe. 453 00:20:20,860 --> 00:20:23,401 A pak vnější věci, i když uzel je nový termín, 454 00:20:23,401 --> 00:20:25,500 Možná, že je to stále stejně jako studenti, a co 455 00:20:25,500 --> 00:20:27,520 byl pod kapotou v SPL. 456 00:20:27,520 --> 00:20:31,095 >> Takže pokud bychom se chtěli začít provádění tohoto propojeného seznamu, 457 00:20:31,095 --> 00:20:33,220 Jak bychom mohli přeložit něco takového se kód? 458 00:20:33,220 --> 00:20:35,350 No, řekněme, viz Příklad programu, který 459 00:20:35,350 --> 00:20:36,840 ve skutečnosti používá spojový seznam. 460 00:20:36,840 --> 00:20:40,870 Mezi dnešní distribuční kódu je program, nazvaný seznam nula. 461 00:20:40,870 --> 00:20:44,980 A když jsem spustit tento jsem vytvořil super jednoduché GUI, Graphical User Interface, 462 00:20:44,980 --> 00:20:46,460 ale je to opravdu jen printf. 463 00:20:46,460 --> 00:20:50,930 A teď jsem vzhledem k tomu sám pár nabídku options-- Delete, Insert, vyhledávání, 464 00:20:50,930 --> 00:20:51,750 a Traverse. 465 00:20:51,750 --> 00:20:52,630 A ukončete. 466 00:20:52,630 --> 00:20:55,970 To jsou jen běžné operace datové struktury známé jako seznam odkazů. 467 00:20:55,970 --> 00:20:58,409 >> Nyní, Delete se chystá Vymazání čísla ze seznamu. 468 00:20:58,409 --> 00:21:00,200 Vložte jde přidat číslo v seznamu. 469 00:21:00,200 --> 00:21:02,181 Vyhledávání bude vypadat na číslo v seznamu. 470 00:21:02,181 --> 00:21:04,930 A traverz je jen ozdobný způsob, jak říkat, projít seznamu 471 00:21:04,930 --> 00:21:06,245 vytisknout, ale to je vše. 472 00:21:06,245 --> 00:21:07,720 Neměňte ho žádným způsobem. 473 00:21:07,720 --> 00:21:08,570 >> Takže zkusme to. 474 00:21:08,570 --> 00:21:10,160 Pojďme dál a typ 2. 475 00:21:10,160 --> 00:21:12,710 A pak budu vložte číslo, řekněme 9. 476 00:21:12,710 --> 00:21:13,620 Enter. 477 00:21:13,620 --> 00:21:17,480 A teď můj program je prostě naprogramován tak, aby říct, seznam je nyní devět. 478 00:21:17,480 --> 00:21:20,190 Teď, když jsem se do toho pusťte a Vložte si znovu, ať 479 00:21:20,190 --> 00:21:23,680 mě jít napřed a oddálení a zadejte 17. 480 00:21:23,680 --> 00:21:25,770 Teď můj seznam je 9, pak 17. 481 00:21:25,770 --> 00:21:27,750 Pokud se mi vložit znovu, pojďme přeskočit jeden. 482 00:21:27,750 --> 00:21:32,400 Namísto 22, podle obrázku máme se při pohledu na tu, dovolte mi, abych náskok 483 00:21:32,400 --> 00:21:34,630 a vložte 26 další. 484 00:21:34,630 --> 00:21:36,230 Takže budu psát 26. 485 00:21:36,230 --> 00:21:37,755 Tento seznam je, jak jsem očekávat. 486 00:21:37,755 --> 00:21:40,630 Ale teď, jen aby zjistil, jestli tento kód bude flexibilní, dovolte mi, abych se 487 00:21:40,630 --> 00:21:43,520 typ 22, který alespoň koncepčně, když jsme 488 00:21:43,520 --> 00:21:46,520 Udržet tento řazeny, což je opravdu bude dalším cílem právě teď, 489 00:21:46,520 --> 00:21:48,690 by měl jít mezi 17 a 26 let. 490 00:21:48,690 --> 00:21:50,270 Tak jsem stiskněte klávesu Enter. 491 00:21:50,270 --> 00:21:51,380 Ve skutečnosti, to funguje. 492 00:21:51,380 --> 00:21:54,950 A tak teď mi dovolte vložit Poslední, na obrázku, 34. 493 00:21:54,950 --> 00:21:55,450 >> V pořádku. 494 00:21:55,450 --> 00:21:58,980 Takže teď mi dovolte stanoví, že Odstranit a Traverse a hledání dělat, 495 00:21:58,980 --> 00:21:59,760 ve skutečnosti, pracovat. 496 00:21:59,760 --> 00:22:04,180 Ve skutečnosti, když se mi spustit vyhledávání, pojďme vyhledat číslo 22, Enter. 497 00:22:04,180 --> 00:22:05,010 Bylo zjištěno 22. 498 00:22:05,010 --> 00:22:07,580 Takže to je to, co tento Program Seznam Zero dělá. 499 00:22:07,580 --> 00:22:10,230 >> Ale co se vlastně děje na který implementuje to? 500 00:22:10,230 --> 00:22:14,530 No, nejdřív bych mohl mít, a skutečně Musím, soubor s názvem list0.h. 501 00:22:14,530 --> 00:22:16,540 502 00:22:16,540 --> 00:22:20,690 A někde tam je to linka, typedef struct uzel, 503 00:22:20,690 --> 00:22:24,850 pak mám složené závorky, int n, a pak struct-- co bylo definice? 504 00:22:24,850 --> 00:22:26,530 505 00:22:26,530 --> 00:22:28,545 Struct uzel další. 506 00:22:28,545 --> 00:22:29,920 507 00:22:29,920 --> 00:22:31,045 Takže potřebujeme hvězdu. 508 00:22:31,045 --> 00:22:33,420 Teď technicky jsme se dostali do zvyk kreslení zde. 509 00:22:33,420 --> 00:22:35,670 Můžete vidět učebnice a on-line odkazy na to tam. 510 00:22:35,670 --> 00:22:36,660 Je to funkčně ekvivalentní. 511 00:22:36,660 --> 00:22:37,980 Ve skutečnosti, je to trochu typické. 512 00:22:37,980 --> 00:22:40,563 Ale budu v souladu s čím jsme minule a to. 513 00:22:40,563 --> 00:22:42,350 A pak konečně, budu to dělat. 514 00:22:42,350 --> 00:22:45,550 >> Takže v hlavičkovém souboru někde v list0.h 515 00:22:45,550 --> 00:22:49,200 dnes je tato definice struct, a možná některé další věci. 516 00:22:49,200 --> 00:22:52,580 Zatím v list0c tu bude pár věcí. 517 00:22:52,580 --> 00:22:54,740 Ale budeme jen start a ne dokončit. 518 00:22:54,740 --> 00:22:59,690 List0.h je soubor chci zařadit do mého C soubor. 519 00:22:59,690 --> 00:23:03,910 A pak se v určitém okamžiku jsem bude mít int, hlavní, neplatné. 520 00:23:03,910 --> 00:23:06,530 A pak budu mít některé úkolů je tady. 521 00:23:06,530 --> 00:23:10,620 Taky budu mít prototyp, jako neplatné, vyhledávání, int, 522 00:23:10,620 --> 00:23:13,610 n, jejichž smyslem života je hledat elementu. 523 00:23:13,610 --> 00:23:18,310 A pak se tady tvrdí, v Dnešní kód, void, hledání, int n, 524 00:23:18,310 --> 00:23:21,020 ne středník, ale otevřené složené závorky. 525 00:23:21,020 --> 00:23:25,049 A teď chci nějak vyhledávání prvku v tomto seznamu. 526 00:23:25,049 --> 00:23:27,340 Ale nemáme dost informace na obrazovce ještě. 527 00:23:27,340 --> 00:23:29,800 Nemám vlastně představovaly samotný seznam. 528 00:23:29,800 --> 00:23:33,070 Takže jeden způsob, jak bychom mohli realizovat spojový seznam v programu 529 00:23:33,070 --> 00:23:37,520 je, že jsem trochu udělat něco jako prohlásit, spojový seznam tady. 530 00:23:37,520 --> 00:23:40,520 Pro jednoduchost budu dělat tento globální, i když v Obecně 531 00:23:40,520 --> 00:23:41,645 neměli dělat to příliš mnoho. 532 00:23:41,645 --> 00:23:43,260 Ale to bude zjednodušení tento příklad. 533 00:23:43,260 --> 00:23:45,890 Tak jsem chtěl deklarovat spojový seznam tady. 534 00:23:45,890 --> 00:23:47,010 Nyní, jak by to dělal? 535 00:23:47,010 --> 00:23:48,810 536 00:23:48,810 --> 00:23:50,750 >> Zde je obrázek propojeného seznamu. 537 00:23:50,750 --> 00:23:53,030 A já opravdu nemám vědět, v okamžiku, kdy jak 538 00:23:53,030 --> 00:23:56,710 Chystám se jít o zastupování tolik věcí, které se jen jeden 539 00:23:56,710 --> 00:23:58,040 proměnná v paměti. 540 00:23:58,040 --> 00:23:59,160 Ale vzpomínám na okamžik. 541 00:23:59,160 --> 00:24:00,830 Celou tu dobu jsme měli řetězce, které pak 542 00:24:00,830 --> 00:24:02,913 odhalil, že je pole pro znaky, které pak 543 00:24:02,913 --> 00:24:05,740 odhalen být jen ukazatel na první znak 544 00:24:05,740 --> 00:24:08,890 v poli znaků , který je ukončen nulovým znakem. 545 00:24:08,890 --> 00:24:13,530 Takže podle této logiky, a s tím obrázek druh setí své myšlenky, 546 00:24:13,530 --> 00:24:17,964 K čemu nám vlastně napsat v naší kód představuje spojový seznam? 547 00:24:17,964 --> 00:24:21,130 Kolik z těchto informací potřebujeme zachytit v C kódu, řekli byste? 548 00:24:21,130 --> 00:24:22,654 549 00:24:22,654 --> 00:24:23,154 Jo? 550 00:24:23,154 --> 00:24:24,738 >> Diváků: Potřebujeme ukazatel na uzel. 551 00:24:24,738 --> 00:24:26,237 David J. Malan: ukazatel na uzel. 552 00:24:26,237 --> 00:24:29,320 Zejména, který uzel by byl váš instinkty se udržet ukazatel? 553 00:24:29,320 --> 00:24:30,026 >> Diváků: první uzel. 554 00:24:30,026 --> 00:24:31,942 >> David J. Malan: Ano, asi jen ten první. 555 00:24:31,942 --> 00:24:34,030 A všimněte si, první Uzel je odlišný tvar. 556 00:24:34,030 --> 00:24:37,690 Je to jen poloviční velikost struct, protože je to opravdu jen ukazatel. 557 00:24:37,690 --> 00:24:44,650 Takže to, co můžete opravdu udělat, je vyhlásit spojový seznam být typu uzlu *. 558 00:24:44,650 --> 00:24:47,780 A řekněme první nazvat a inicializovat ji na hodnotu null. 559 00:24:47,780 --> 00:24:49,910 Takže null, je opět přichází na obrázku zde. 560 00:24:49,910 --> 00:24:53,620 Nejen, že je null používán jako například speciální Návratová hodnota pro věci, jako getString 561 00:24:53,620 --> 00:24:57,770 a malloc, null je rovněž nulová ukazatel, nedostatek ukazatele, 562 00:24:57,770 --> 00:24:58,430 chcete-li. 563 00:24:58,430 --> 00:25:00,309 To prostě znamená, že nic, co je ještě tady. 564 00:25:00,309 --> 00:25:02,100 Nyní poprvé, mohl jsem volal to cokoliv. 565 00:25:02,100 --> 00:25:04,200 Mohl jsem to nazval "seznam" nebo libovolný počet dalších věcí. 566 00:25:04,200 --> 00:25:06,960 Ale já jsem volat to "první", takže , aby se ocitl obrázku. 567 00:25:06,960 --> 00:25:10,280 Tak jako řetězec může být reprezentován s adresou svého prvního bytu, 568 00:25:10,280 --> 00:25:11,280 takže může spojový seznam. 569 00:25:11,280 --> 00:25:13,480 A uvidíme další data konstrukce je zastoupena 570 00:25:13,480 --> 00:25:16,700 pouze s jedním ukazatelem, 32-bit šipka směřující 571 00:25:16,700 --> 00:25:18,740 v prvním uzlu ve struktuře. 572 00:25:18,740 --> 00:25:20,340 >> Ale teď pojďme předpokládat problém. 573 00:25:20,340 --> 00:25:23,230 Pokud jsem jen vzpomínání v mém programu adresy 574 00:25:23,230 --> 00:25:27,220 z prvního uzlu, nejdříve obdélník v této datové struktuře, 575 00:25:27,220 --> 00:25:31,760 co bylo lepší být případ o Realizace zbytek mého seznamu? 576 00:25:31,760 --> 00:25:35,820 Co je to klíčový detail, co se děje zajistit, že toto skutečně funguje? 577 00:25:35,820 --> 00:25:39,250 A tím "skutečně funguje" I Tedy, podobně jako řetězec, 578 00:25:39,250 --> 00:25:42,180 nám umožňuje přejít od prvního znaku v Davin jménem na druhé, 579 00:25:42,180 --> 00:25:44,755 na třetí, na čtvrtý, až do samého konce, 580 00:25:44,755 --> 00:25:47,880 jak víme, když jsme na konci propojeného seznamu, který vypadá takhle? 581 00:25:47,880 --> 00:25:50,035 582 00:25:50,035 --> 00:25:50,660 Když je null. 583 00:25:50,660 --> 00:25:53,640 A já jsem představoval tento druh jako jako elektrický inženýr silou, 584 00:25:53,640 --> 00:25:56,420 s malou uzemnění symbol, druhů. 585 00:25:56,420 --> 00:25:58,246 Ale to jen znamená, null v tomto případě. 586 00:25:58,246 --> 00:26:00,370 Můžete nakreslit libovolný počet způsoby, ale tento autor 587 00:26:00,370 --> 00:26:02,800 Stalo se zde používat tento symbol. 588 00:26:02,800 --> 00:26:06,260 >> Tak dlouho, jak budeme navlékat všech těchto uzlů společně, 589 00:26:06,260 --> 00:26:08,600 zapamatování pouze v případě, První z nich je, tak dlouho 590 00:26:08,600 --> 00:26:11,760 jak vložit speciální symbol na úplně poslední uzel v seznamu, 591 00:26:11,760 --> 00:26:15,130 a budeme používat hodnotu null, protože to je to, co máme k dispozici pro nás, 592 00:26:15,130 --> 00:26:16,480 Tento seznam je kompletní. 593 00:26:16,480 --> 00:26:20,190 A i když jsem jen dát ukazatel na první prvek, ty, programátor, 594 00:26:20,190 --> 00:26:22,486 určitě přístup zbytek. 595 00:26:22,486 --> 00:26:24,360 Ale pojďme se nechat svou mysl bloudit trochu, 596 00:26:24,360 --> 00:26:26,140 v případě, že nejsou již docela wandered-- co je 597 00:26:26,140 --> 00:26:28,723 bude doba běhu najít něco v tomto seznamu? 598 00:26:28,723 --> 00:26:30,450 599 00:26:30,450 --> 00:26:33,470 Sakra, je to velké O n, což není špatné, v spravedlnosti. 600 00:26:33,470 --> 00:26:34,800 Ale je to lineární. 601 00:26:34,800 --> 00:26:37,980 Vzdali jsme to, co funkce polí přesunutím více 602 00:26:37,980 --> 00:26:43,130 k tomuto obrázku dynamicky tkané společně nebo propojeny uzly? 603 00:26:43,130 --> 00:26:44,970 604 00:26:44,970 --> 00:26:46,687 Dali jsme si náhodný přístup. 605 00:26:46,687 --> 00:26:48,770 Pole je pěkné, protože matematicky vše 606 00:26:48,770 --> 00:26:50,340 je zády k sobě k sobě k sobě. 607 00:26:50,340 --> 00:26:52,370 I když tento obrázek vypadá pěkně, a dokonce i 608 00:26:52,370 --> 00:26:55,830 i když to vypadá, že tyto uzly jsou pěkně od sebe, ve skutečnosti 609 00:26:55,830 --> 00:26:56,830 by mohly být kdekoliv. 610 00:26:56,830 --> 00:27:01,590 OX1, Ox50, Ox123, Ox99, tito uzly by mohly být kdekoliv. 611 00:27:01,590 --> 00:27:05,960 Vzhledem k tomu, malloc dělá alokovat paměť z haldy, ale kdekoliv v haldě. 612 00:27:05,960 --> 00:27:09,080 Nemusíte nutně vědět, že je bude zády k sobě k sobě. 613 00:27:09,080 --> 00:27:12,460 A tak to registrace do reality je to bude docela to hezká. 614 00:27:12,460 --> 00:27:16,140 >> Takže to bude trvat trochu pracovat na provádění této funkce. 615 00:27:16,140 --> 00:27:17,880 Takže pojďme realizovat Hledat. 616 00:27:17,880 --> 00:27:20,250 A uvidíme, druh chytrý způsob, jak to udělat. 617 00:27:20,250 --> 00:27:24,660 Takže když jsem vyhledávací funkce a Já jsem vzhledem k proměnné, číslo N 618 00:27:24,660 --> 00:27:28,490 hledat, musím vědět, Nová syntaxe hledá uvnitř 619 00:27:28,490 --> 00:27:32,400 struktury, která je ukázal, najít n. 620 00:27:32,400 --> 00:27:33,210 Tak pojďme na to. 621 00:27:33,210 --> 00:27:36,030 >> Takže nejprve jsem jít dopředu a prohlásit uzel *. 622 00:27:36,030 --> 00:27:39,400 A budu to říkat ukazatel, jen konvencí. 623 00:27:39,400 --> 00:27:41,710 A já se inicializovat ji jako první. 624 00:27:41,710 --> 00:27:43,770 A teď můžu udělat v mnoha ohledech. 625 00:27:43,770 --> 00:27:45,436 Ale budu mít společný přístup. 626 00:27:45,436 --> 00:27:50,180 Zatímco ukazatel není rovno null, a to je platné syntaxe. 627 00:27:50,180 --> 00:27:54,550 A to prostě znamená, že následující kód, takže pokud nejste ukázal na nic. 628 00:27:54,550 --> 00:27:55,800 Co chcete dělat? 629 00:27:55,800 --> 00:28:01,939 >> Pokud se ukazatel tečka n, dovolte mi, abych se vrátil k tomu, equals-- rovná co? 630 00:28:01,939 --> 00:28:03,105 Jaké hodnoty mám hledat? 631 00:28:03,105 --> 00:28:04,920 632 00:28:04,920 --> 00:28:06,590 Skutečná n, který byl schválen v. 633 00:28:06,590 --> 00:28:09,020 Tak tady je další vlastnost, o C a mnoha jazyků. 634 00:28:09,020 --> 00:28:13,705 I když uzel struktury zvané má hodnotu n, zcela legitimní 635 00:28:13,705 --> 00:28:17,530 také mít místní argumentu nebo proměnné s názvem n. 636 00:28:17,530 --> 00:28:20,085 Protože i my, s lidské oko může rozlišit 637 00:28:20,085 --> 00:28:22,087 že toto n je pravděpodobně odlišný od tohoto n. 638 00:28:22,087 --> 00:28:23,420 Vzhledem k tomu, syntaxe je odlišná. 639 00:28:23,420 --> 00:28:26,211 Máš tečku a ukazatel, že tato jedna nemá žádnou takovou věc. 640 00:28:26,211 --> 00:28:27,290 Takže to je v pořádku. 641 00:28:27,290 --> 00:28:29,120 To je v pořádku, aby jim říkat stejné věci. 642 00:28:29,120 --> 00:28:32,380 >> Mám-li se vám najít to, já jsem bude chtít něco udělat 643 00:28:32,380 --> 00:28:35,000 jako oznamujeme, že jsme našli n. 644 00:28:35,000 --> 00:28:37,930 A necháme to jako komentář nebo pseudokód kód. 645 00:28:37,930 --> 00:28:40,190 Else, a tady je Zajímavostí, co 646 00:28:40,190 --> 00:28:47,320 nechci dělat, když aktuálního uzlu není obsahující n, že mi záleží? 647 00:28:47,320 --> 00:28:50,700 Jak mohu dosáhnout následující? 648 00:28:50,700 --> 00:28:53,710 Pokud se můj prst na moment je PTR, a to je 649 00:28:53,710 --> 00:28:55,920 ukázal na cokoliv První ukazuje na, 650 00:28:55,920 --> 00:28:59,290 jak se mohu pohnout prstem k dalšímu uzlu v kódu? 651 00:28:59,290 --> 00:29:01,915 No, co je strouhanka jsme bude následovat v tomto případě? 652 00:29:01,915 --> 00:29:03,464 653 00:29:03,464 --> 00:29:04,380 Diváků: [neslyšitelné]. 654 00:29:04,380 --> 00:29:05,630 David J. Malan: Jo, tak příště. 655 00:29:05,630 --> 00:29:06,640 656 00:29:06,640 --> 00:29:09,824 Takže když se vrátím k mému Kód tady, opravdu, já jsem 657 00:29:09,824 --> 00:29:12,990 jít dál a říct ukazatel, který je to jen dočasné proměnná-- je to 658 00:29:12,990 --> 00:29:15,320 divný název, ptr, ale Je to jako temp-- 659 00:29:15,320 --> 00:29:19,234 Chystám se nastavit ukazatel rovná jakéhokoli ukazatele je-- 660 00:29:19,234 --> 00:29:22,150 a znovu, to bude malý kočárek pro moment-- tečkou. 661 00:29:22,150 --> 00:29:23,551 662 00:29:23,551 --> 00:29:26,550 Jinými slovy, já vezmu můj prst, který se ukázal v tomto uzlu 663 00:29:26,550 --> 00:29:31,247 tady a budu říkat, víte, co, podívejte se na další pole 664 00:29:31,247 --> 00:29:33,330 a pohybem prstu bez ohledu na to ukazují. 665 00:29:33,330 --> 00:29:35,163 A to bude opakovat, opakovat, opakovat. 666 00:29:35,163 --> 00:29:37,630 Ale když se dělá můj prst přestat dělat vůbec nic? 667 00:29:37,630 --> 00:29:40,095 Jakmile se to, co řádek kódu kopy v? 668 00:29:40,095 --> 00:29:40,970 Diváků: [neslyšitelné] 669 00:29:40,970 --> 00:29:43,060 David J. Malan: Je-li bod, zatímco ukazatel není rovno null. 670 00:29:43,060 --> 00:29:44,900 Na nějakém místě můj prst je bude ukazovat na null 671 00:29:44,900 --> 00:29:47,070 a budu si uvědomit, to je konec tohoto seznamu. 672 00:29:47,070 --> 00:29:48,910 Nyní, to je malý lež pro jednoduchost. 673 00:29:48,910 --> 00:29:51,580 Ukazuje se, že i když jsme se dozvěděl tuto tečkové notace 674 00:29:51,580 --> 00:29:55,220 pro stavby, ukazatel není struct. 675 00:29:55,220 --> 00:29:56,580 ptr je co? 676 00:29:56,580 --> 00:29:58,350 Stačí, aby se více nitpicky. 677 00:29:58,350 --> 00:29:59,720 678 00:29:59,720 --> 00:30:01,360 Je to ukazatel na uzel. 679 00:30:01,360 --> 00:30:03,120 Není to uzel sám. 680 00:30:03,120 --> 00:30:06,650 Kdybych neměl hvězdu zde, ukazatel absolutely-- je to uzel. 681 00:30:06,650 --> 00:30:08,650 To je jako týden jedno deklarace proměnné, 682 00:30:08,650 --> 00:30:10,120 i když slovo "uzel" je nový. 683 00:30:10,120 --> 00:30:13,860 >> Ale jakmile jsme zavedli hvězda, to je teď ukazatel na uzel. 684 00:30:13,860 --> 00:30:17,960 A bohužel nelze použít tečka zápis pro ukazatel. 685 00:30:17,960 --> 00:30:21,070 Musíte použít šipky zápis, který, překvapivě, 686 00:30:21,070 --> 00:30:23,470 Je to poprvé, kdy nějaký kus syntaxe vypadá intuitivní. 687 00:30:23,470 --> 00:30:25,245 Tento doslova vypadá jako šíp. 688 00:30:25,245 --> 00:30:26,370 A tak to je dobrá věc. 689 00:30:26,370 --> 00:30:28,995 A tady doslova Vypadá jako šíp. 690 00:30:28,995 --> 00:30:31,870 Takže si myslím, že je to la-- vůbec se mi nelíbí myslím, že jsem příliš spáchání tady-- I 691 00:30:31,870 --> 00:30:34,120 si myslí, že je to poslední nový kus syntaxe budeme vidět. 692 00:30:34,120 --> 00:30:36,500 A díkybohu, že je to opravdu trochu více intuitivní. 693 00:30:36,500 --> 00:30:40,090 >> Teď, pro ty z vás, kteří by raději postaru, 694 00:30:40,090 --> 00:30:42,550 můžete stále používat tečkové notace. 695 00:30:42,550 --> 00:30:45,380 Ale podle pondělního rozhovor, nejprve 696 00:30:45,380 --> 00:30:50,530 je třeba jít tam, jděte na to řešit, a pak přístup k poli. 697 00:30:50,530 --> 00:30:51,897 Tak to je také v pořádku. 698 00:30:51,897 --> 00:30:53,730 A upřímně řečeno, je to trochu pedantský. 699 00:30:53,730 --> 00:30:56,530 Ty doslova říká, dereference ukazatel a tam. 700 00:30:56,530 --> 00:30:59,320 Pak si n, pole s názvem n. 701 00:30:59,320 --> 00:31:01,370 Ale upřímně řečeno, nikdo nechce psát nebo číst. 702 00:31:01,370 --> 00:31:03,620 A tak svět vynalezl notace šipky, které 703 00:31:03,620 --> 00:31:06,980 je ekvivalentní, totožné, je to jen syntaktický cukr. 704 00:31:06,980 --> 00:31:10,570 Takže ozdobný způsob, jak říkat to vypadá lépe, nebo vypadá jednodušší. 705 00:31:10,570 --> 00:31:12,296 >> Takže teď budu dělat jednu věc. 706 00:31:12,296 --> 00:31:15,420 Budu říkat "pauzu", jakmile jsem Zjistili, že je tak nemám udržet ji hledají. 707 00:31:15,420 --> 00:31:17,620 Ale to je podstata vyhledávací funkce. 708 00:31:17,620 --> 00:31:21,710 Ale je to mnohem jednodušší, v konec, a ne projít kód. 709 00:31:21,710 --> 00:31:25,570 To je skutečně formální realizace hledání v dnešní distribuce kódu. 710 00:31:25,570 --> 00:31:30,530 Troufám si říci, že vložka není zvláště zábavné projít 711 00:31:30,530 --> 00:31:33,180 vizuálně, ani je mazat, a to i i když na konci dne 712 00:31:33,180 --> 00:31:35,460 se redukuje na poměrně jednoduché heuristiky. 713 00:31:35,460 --> 00:31:36,330 >> Tak pojďme na to. 714 00:31:36,330 --> 00:31:39,250 Pokud budete humor mě tady, jsem přináší spoustu stresu koule. 715 00:31:39,250 --> 00:31:40,620 Přinesl jsem spoustu čísel. 716 00:31:40,620 --> 00:31:46,562 A mohli bychom získat jen několik dobrovolníků reprezentovat 9, 17, 20, 22, 29, a 34? 717 00:31:46,562 --> 00:31:48,270 Takže v podstatě každý kdo je tady dnes. 718 00:31:48,270 --> 00:31:50,170 719 00:31:50,170 --> 00:31:52,760 To byl jeden, dva, tři, čtyři, pět, šest lidí. 720 00:31:52,760 --> 00:31:55,740 A já jsem byl požádán, aby jít-- vidět, no jeden na zadní straně zvyšuje své ruce. 721 00:31:55,740 --> 00:32:01,910 OK, jeden, dva, tři, čtyři, five-- dovolte mi načte balance-- šest. 722 00:32:01,910 --> 00:32:03,051 OK, šest pojď nahoru. 723 00:32:03,051 --> 00:32:04,050 Budeme potřebovat další lidi. 724 00:32:04,050 --> 00:32:05,460 Přinesli jsme další stres koule. 725 00:32:05,460 --> 00:32:08,200 A pokud byste mohl, pro jen na chvíli, linka 726 00:32:08,200 --> 00:32:10,490 Sami si prostě líbí tento obrázek zde. 727 00:32:10,490 --> 00:32:15,200 728 00:32:15,200 --> 00:32:15,959 >> V pořádku. 729 00:32:15,959 --> 00:32:17,125 Pojďme se podívat, Jak se jmenujete? 730 00:32:17,125 --> 00:32:17,550 >> DIVÁKŮ: Andrew. 731 00:32:17,550 --> 00:32:18,800 >> David J. Malan: Andrew, jste číslo 9. 732 00:32:18,800 --> 00:32:19,540 Těší mě. 733 00:32:19,540 --> 00:32:20,400 Tady to máš. 734 00:32:20,400 --> 00:32:21,593 735 00:32:21,593 --> 00:32:22,176 DIVÁKŮ: Jen. 736 00:32:22,176 --> 00:32:22,662 David J. Malan: Jen. 737 00:32:22,662 --> 00:32:23,162 David. 738 00:32:23,162 --> 00:32:23,765 Číslo 17. 739 00:32:23,765 --> 00:32:24,950 740 00:32:24,950 --> 00:32:25,450 Ano? 741 00:32:25,450 --> 00:32:26,400 >> Diváků: Jsem Julia. 742 00:32:26,400 --> 00:32:26,980 >> David J. Malan: Julia, David. 743 00:32:26,980 --> 00:32:27,545 Číslo 20. 744 00:32:27,545 --> 00:32:28,507 745 00:32:28,507 --> 00:32:29,340 DIVÁKŮ: Christian. 746 00:32:29,340 --> 00:32:30,715 David J. Malan: Christian, David. 747 00:32:30,715 --> 00:32:31,541 Číslo 22. 748 00:32:31,541 --> 00:32:32,040 A? 749 00:32:32,040 --> 00:32:32,649 >> DIVÁKŮ: JP. 750 00:32:32,649 --> 00:32:33,440 David J. Malan: JP. 751 00:32:33,440 --> 00:32:34,880 Číslo 29. 752 00:32:34,880 --> 00:32:37,080 Takže jděte do toho a dostat v-- Uh oh. 753 00:32:37,080 --> 00:32:38,486 754 00:32:38,486 --> 00:32:38,985 Uh oh. 755 00:32:38,985 --> 00:32:39,650 756 00:32:39,650 --> 00:32:40,150 Standby. 757 00:32:40,150 --> 00:32:41,360 758 00:32:41,360 --> 00:32:42,390 20. 759 00:32:42,390 --> 00:32:43,682 Má někdo značku? 760 00:32:43,682 --> 00:32:44,890 Diváků: Mám Sharpie. 761 00:32:44,890 --> 00:32:45,660 David J. Malan: Máš Sharpie? 762 00:32:45,660 --> 00:32:46,159 OK. 763 00:32:46,159 --> 00:32:47,577 764 00:32:47,577 --> 00:32:49,160 A má někdo kus papíru? 765 00:32:49,160 --> 00:32:51,562 766 00:32:51,562 --> 00:32:52,270 Uložit přednášku. 767 00:32:52,270 --> 00:32:53,810 768 00:32:53,810 --> 00:32:55,362 Pojď. 769 00:32:55,362 --> 00:32:56,320 Diváků: Máme to. 770 00:32:56,320 --> 00:32:57,600 David J. Malan: Máme to? 771 00:32:57,600 --> 00:32:58,577 Dobře, děkuji. 772 00:32:58,577 --> 00:33:01,380 773 00:33:01,380 --> 00:33:02,520 Jdeme na to. 774 00:33:02,520 --> 00:33:03,582 Bylo to od vás? 775 00:33:03,582 --> 00:33:04,540 Právě jste zachránil den. 776 00:33:04,540 --> 00:33:05,670 777 00:33:05,670 --> 00:33:07,220 Tak 29. 778 00:33:07,220 --> 00:33:10,510 779 00:33:10,510 --> 00:33:11,110 V pořádku. 780 00:33:11,110 --> 00:33:13,360 781 00:33:13,360 --> 00:33:14,890 I chybně 29, ale OK. 782 00:33:14,890 --> 00:33:15,720 Jen do toho. 783 00:33:15,720 --> 00:33:18,114 Dobře, dám vám pero zpět na okamžik. 784 00:33:18,114 --> 00:33:19,280 Takže máme tyto lidi tady. 785 00:33:19,280 --> 00:33:20,330 Pojďme se jeden druhého. 786 00:33:20,330 --> 00:33:23,750 Gabe, chceš hrát první prvek tady? 787 00:33:23,750 --> 00:33:25,705 Musíme vás upozornit v těchto jemných lidí. 788 00:33:25,705 --> 00:33:26,930 789 00:33:26,930 --> 00:33:31,030 Takže 9, 17, 20, 22, třídit z 29, a pak 34. 790 00:33:31,030 --> 00:33:32,160 791 00:33:32,160 --> 00:33:33,325 Jsme ztratili někoho? 792 00:33:33,325 --> 00:33:33,950 Mám 34. 793 00:33:33,950 --> 00:33:36,730 Kde udělal-- OK, kdo chce být 34? 794 00:33:36,730 --> 00:33:37,605 OK, pojď nahoru, 34. 795 00:33:37,605 --> 00:33:39,280 796 00:33:39,280 --> 00:33:41,220 Tak jo, to bude stojí za vyvrcholení. 797 00:33:41,220 --> 00:33:41,550 Jak se jmenujete? 798 00:33:41,550 --> 00:33:42,040 >> DIVÁKŮ: Peter. 799 00:33:42,040 --> 00:33:43,456 >> David J. Malan: Peter, pojď nahoru. 800 00:33:43,456 --> 00:33:46,810 Dobře, takže tady je Celá parta uzlů. 801 00:33:46,810 --> 00:33:49,060 Každý z vás představuje jeden z těchto obdélníků. 802 00:33:49,060 --> 00:33:51,930 A Gabe, trochu zvláštní člověk se představuje jako první. 803 00:33:51,930 --> 00:33:54,850 Takže jeho ukazatel je o něco menší na obrazovce, než všichni ostatní. 804 00:33:54,850 --> 00:33:58,120 A v tomto případě, každý po levé straně ruce, bude buď směřovat dolů, 805 00:33:58,120 --> 00:34:01,085 v důsledku čehož se null, tak jen absence ukazatele, 806 00:34:01,085 --> 00:34:03,210 nebo to bude ukazovat v uzlu vedle vás. 807 00:34:03,210 --> 00:34:05,440 >> Takže teď, když se zdobí sami jako na obrázku 808 00:34:05,440 --> 00:34:07,585 tu, jděte do toho a bod na sebe, s Gabe 809 00:34:07,585 --> 00:34:11,030 zejména ukazuje na číslo 9 reprezentovat seznam. 810 00:34:11,030 --> 00:34:14,050 OK, a číslo 34, vaše levá ruka by měla být jen ukázal na podlahu. 811 00:34:14,050 --> 00:34:15,750 >> OK, takže to je provázaný seznam. 812 00:34:15,750 --> 00:34:17,580 Tak tohle je scénář v pochybnost. 813 00:34:17,580 --> 00:34:20,210 A skutečně, to je reprezentativní třídy problémů 814 00:34:20,210 --> 00:34:21,929 , že by se mohli pokusit řešit s kódem. 815 00:34:21,929 --> 00:34:25,020 Chcete-li nakonec vložit nový prvek do seznamu. 816 00:34:25,020 --> 00:34:27,494 V tomto případě budeme zkuste vložit číslo 55. 817 00:34:27,494 --> 00:34:28,500 818 00:34:28,500 --> 00:34:30,860 Ale tam to bude různé případy, aby zvážila. 819 00:34:30,860 --> 00:34:34,409 A skutečně, to bude jeden z big-obraz takeaways tady, je, 820 00:34:34,409 --> 00:34:35,659 Jaké jsou různé případy. 821 00:34:35,659 --> 00:34:39,120 Jaké jsou různé, pokud podmínky, nebo větve, které váš program mohl mít? 822 00:34:39,120 --> 00:34:42,024 >> No, číslo se snažíte vložka, která dnes už víme, že je 55, 823 00:34:42,024 --> 00:34:44,650 ale pokud jste nevěděli, v předstihu, troufám si tvrdit, 824 00:34:44,650 --> 00:34:47,840 spadá do nejméně tří možné situace. 825 00:34:47,840 --> 00:34:49,717 Tam, kde by mohl být nový prvek? 826 00:34:49,717 --> 00:34:51,050 Diváků: A konec nebo střed. 827 00:34:51,050 --> 00:34:54,150 David J. Malan: Na konci, v střední, nebo na začátku. 828 00:34:54,150 --> 00:34:56,650 Tak jsem se tvrdí, že je alespoň tři problémy musíme řešit. 829 00:34:56,650 --> 00:34:58,691 Pojďme si vybrat, co je třeba pravděpodobně nejjednodušší 830 00:34:58,691 --> 00:35:01,090 jeden, kde nový prvek patří na začátku. 831 00:35:01,090 --> 00:35:04,040 Takže budu mít kód zcela jako je vyhledávání, které jsem napsal. 832 00:35:04,040 --> 00:35:07,670 A já budu mít ptr, které Budu reprezentovat tady s mým prstem, 833 00:35:07,670 --> 00:35:08,370 jako obvykle. 834 00:35:08,370 --> 00:35:12,430 >> A pamatujte si, jakou hodnotu jsme inicializovat ptr na? 835 00:35:12,430 --> 00:35:15,300 Tak jsme se inicializuje ji zpočátku null. 836 00:35:15,300 --> 00:35:16,410 837 00:35:16,410 --> 00:35:19,770 Ale to, co jsme udělali, jakmile jsme byly v naší funkci vyhledávání? 838 00:35:19,770 --> 00:35:20,940 839 00:35:20,940 --> 00:35:24,870 Vydali jsme se rovná první, což neznamená, že dělá. 840 00:35:24,870 --> 00:35:25,890 841 00:35:25,890 --> 00:35:30,570 Mám-li nastavit první ptr rovnou, co by moje ruka opravdu ukazuje na? 842 00:35:30,570 --> 00:35:31,070 Přesně tak. 843 00:35:31,070 --> 00:35:33,290 Takže pokud Gabe a já se chystáte být stejné hodnoty zde 844 00:35:33,290 --> 00:35:34,760 Potřebujeme jak bodu číslo 9. 845 00:35:34,760 --> 00:35:36,420 >> Tak tohle byl začátek našeho příběhu. 846 00:35:36,420 --> 00:35:38,700 A teď je to jen jednoduchý, i když syntaxe je nového. 847 00:35:38,700 --> 00:35:40,580 Koncepčně je to jen lineární hledání. 848 00:35:40,580 --> 00:35:42,750 Je 55 rovná 9? 849 00:35:42,750 --> 00:35:45,559 Nebo spíš, řekněme, méně než 9. 850 00:35:45,559 --> 00:35:47,600 Protože se snažím přijít na to, kam umístit 55. 851 00:35:47,600 --> 00:35:51,270 Méně než 9, méně než 17, méně než 20, méně než 22, méně než 29, 852 00:35:51,270 --> 00:35:52,510 méně než 34, ne. 853 00:35:52,510 --> 00:35:55,080 Takže teď jsme v případě jeden z nejméně tří. 854 00:35:55,080 --> 00:35:59,910 >> Pokud chci vložit 55 sem, co řádky kódu třeba se dostat popraven? 855 00:35:59,910 --> 00:36:01,890 Jak to obrázek lidé potřebují změnit? 856 00:36:01,890 --> 00:36:03,181 Co mám dělat s mou levou ruku? 857 00:36:03,181 --> 00:36:04,530 858 00:36:04,530 --> 00:36:07,360 To by mělo být null zpočátku, proto, že jsem na konci seznamu. 859 00:36:07,360 --> 00:36:09,318 A co by se stalo, tady s Petrem, že? 860 00:36:09,318 --> 00:36:10,520 861 00:36:10,520 --> 00:36:12,430 Očividně bude ukazovat na mě. 862 00:36:12,430 --> 00:36:15,580 Takže tvrdím, že je to nejméně dva řádky kódu v ukázkovém kódu ode dneška 863 00:36:15,580 --> 00:36:18,570 že to bude k provedení tohoto Scénář přidání 55 na ocasu. 864 00:36:18,570 --> 00:36:20,950 A mohl bych mít někoho hop a právě představuje 55? 865 00:36:20,950 --> 00:36:22,200 Dobře, že jste nový 55. 866 00:36:22,200 --> 00:36:23,580 867 00:36:23,580 --> 00:36:27,054 >> Takže teď, co když další scénář přijde, 868 00:36:27,054 --> 00:36:29,720 a chceme vložit na na začátku nebo na čele tohoto seznamu? 869 00:36:29,720 --> 00:36:31,100 A jaké je vaše jméno, číslo 55? 870 00:36:31,100 --> 00:36:31,420 >> DIVÁKŮ: Jack. 871 00:36:31,420 --> 00:36:32,295 >> David J. Malan: Jack? 872 00:36:32,295 --> 00:36:33,585 OK, rád tě poznávám. 873 00:36:33,585 --> 00:36:34,210 Vítejte na palubě. 874 00:36:34,210 --> 00:36:36,640 Takže teď budeme vložit, řekněme, číslo 5. 875 00:36:36,640 --> 00:36:39,840 Zde je druhý případ tři jsme přišli s před. 876 00:36:39,840 --> 00:36:43,050 Takže v případě, 5 patří na začátku, pojďme se podívat, jak jsme zjistili, že ven. 877 00:36:43,050 --> 00:36:46,310 I inicializovat svůj ptr ukazatel opět číslo 9. 878 00:36:46,310 --> 00:36:49,140 A uvědomil jsem si, oh, 5 je menší než 9. 879 00:36:49,140 --> 00:36:50,880 Takže opravit tento obrázek pro nás. 880 00:36:50,880 --> 00:36:54,820 Čí ruce, Gabe či Davida nebo--, co je číslo devět jméno? 881 00:36:54,820 --> 00:36:55,740 >> DIVÁKŮ: Jen. 882 00:36:55,740 --> 00:36:58,406 >> David J. Malan: Jenin hands-- které v našich rukou je třeba změnit? 883 00:36:58,406 --> 00:36:58,905 884 00:36:58,905 --> 00:37:00,970 OK, takže Gabe poukazuje na to, co teď? 885 00:37:00,970 --> 00:37:01,640 Na mě. 886 00:37:01,640 --> 00:37:02,750 Jsem nový uzel. 887 00:37:02,750 --> 00:37:04,870 Tak jsem si jen trochu pohybu zde vidět vizuálně. 888 00:37:04,870 --> 00:37:06,435 A mezitím co jsem zdůraznit, že? 889 00:37:06,435 --> 00:37:07,910 890 00:37:07,910 --> 00:37:09,020 Přesto, kde jsem ukázal. 891 00:37:09,020 --> 00:37:10,000 Tak takhle to je. 892 00:37:10,000 --> 00:37:13,717 Takže opravdu jen jeden řádek kódu opravy tento konkrétní problém, by se mohlo zdát. 893 00:37:13,717 --> 00:37:14,800 Dobře, takže to je dobré. 894 00:37:14,800 --> 00:37:17,580 A může někdo být zástupný symbol pro 5? 895 00:37:17,580 --> 00:37:18,080 Pojď nahoru. 896 00:37:18,080 --> 00:37:20,270 897 00:37:20,270 --> 00:37:21,320 Budeme vám příště. 898 00:37:21,320 --> 00:37:24,280 >> Dobře, takže teď-- a Mimochodem, názvy 899 00:37:24,280 --> 00:37:28,510 Nebudu dělat explicitní zmínku o právu Nyní, pred ukazatel, předchůdce ukazatel 900 00:37:28,510 --> 00:37:31,260 a nový ukazatel, který je vzhledem k tomu jen jména 901 00:37:31,260 --> 00:37:35,280 v ukázkovém kódu na ukazateli nebo ruce, že to trochu polohovací kolem. 902 00:37:35,280 --> 00:37:36,060 Jak se jmenujete? 903 00:37:36,060 --> 00:37:36,700 >> DIVÁKŮ: Christine. 904 00:37:36,700 --> 00:37:37,100 >> David J. Malan: Christine. 905 00:37:37,100 --> 00:37:38,090 Vítejte na palubě. 906 00:37:38,090 --> 00:37:42,180 Dobře, takže uvažujme nyní poněkud nepříjemné scénář, 907 00:37:42,180 --> 00:37:46,350 čímž Chci vložit něco jako 26 do toho. 908 00:37:46,350 --> 00:37:47,090 20? 909 00:37:47,090 --> 00:37:47,590 Co je? 910 00:37:47,590 --> 00:37:50,510 Tyto jsou-- dobrou věc máme tohle pero. 911 00:37:50,510 --> 00:37:51,955 V pořádku, 20. 912 00:37:51,955 --> 00:37:53,640 913 00:37:53,640 --> 00:37:57,570 Pokud se někdo mohl dostat ještě kousek papír připravený, jen case-- v pořádku. 914 00:37:57,570 --> 00:37:58,370 Oh, zajímavé. 915 00:37:58,370 --> 00:37:59,760 916 00:37:59,760 --> 00:38:02,390 No to je příklad přednáškového chyby. 917 00:38:02,390 --> 00:38:03,894 OK, takže to, co se jmenuješ? 918 00:38:03,894 --> 00:38:04,560 DIVÁKŮ: Julia. 919 00:38:04,560 --> 00:38:07,559 David J. Malan: Julia, můžete pop , a předstírat, že jsi nikdy nebyl? 920 00:38:07,559 --> 00:38:09,040 OK, to se nikdy nestalo. 921 00:38:09,040 --> 00:38:09,680 Děkuji vám. 922 00:38:09,680 --> 00:38:12,180 Takže předpokládám, že chceme vložit Julia do tohoto propojeného seznamu. 923 00:38:12,180 --> 00:38:13,780 Je číslo 20. 924 00:38:13,780 --> 00:38:15,530 A samozřejmě, že je bude patřit k 925 00:38:15,530 --> 00:38:17,521 begin-- neukazují na nic zatím. 926 00:38:17,521 --> 00:38:20,020 Takže vaše ruka může být trochu dolů null nebo nějaké odpadky hodnotu. 927 00:38:20,020 --> 00:38:21,210 Pojďme říct, rychlý příběh. 928 00:38:21,210 --> 00:38:22,980 Jsem ukázal na číslo 5 této době. 929 00:38:22,980 --> 00:38:23,880 Pak jsem zkontrolovat 9. 930 00:38:23,880 --> 00:38:25,130 Pak jsem zkontrolovat 17. 931 00:38:25,130 --> 00:38:26,247 Pak jsem zkontrolovat 22. 932 00:38:26,247 --> 00:38:27,650 933 00:38:27,650 --> 00:38:32,485 A já si uvědomuji, ooh, Julia musí jít před 22. 934 00:38:32,485 --> 00:38:33,580 935 00:38:33,580 --> 00:38:34,660 Takže to, co se musí stát? 936 00:38:34,660 --> 00:38:35,786 937 00:38:35,786 --> 00:38:36,910 Čí ruce je třeba změnit? 938 00:38:36,910 --> 00:38:38,360 Julie, moje, nebo-- co se jmenuješ? 939 00:38:38,360 --> 00:38:39,230 >> DIVÁKŮ: Christian. 940 00:38:39,230 --> 00:38:40,060 >> David J. Malan: Christian, nebo? 941 00:38:40,060 --> 00:38:40,560 >> DIVÁKŮ: Andy. 942 00:38:40,560 --> 00:38:40,905 >> David J. Malan: Andy. 943 00:38:40,905 --> 00:38:41,654 Christian, nebo Andy? 944 00:38:41,654 --> 00:38:44,280 945 00:38:44,280 --> 00:38:45,690 Andy je třeba poukázat na? 946 00:38:45,690 --> 00:38:46,780 947 00:38:46,780 --> 00:38:47,341 Julia. 948 00:38:47,341 --> 00:38:47,840 V pořádku. 949 00:38:47,840 --> 00:38:48,960 Tak Andy, chceš ukázat na Julia? 950 00:38:48,960 --> 00:38:50,120 Ale počkejte chvilku. 951 00:38:50,120 --> 00:38:53,260 V příběhu tak daleko, Já jsem tak nějak jedno 952 00:38:53,260 --> 00:38:56,800 na starosti, v tom smyslu, že ukazatel je věc, která je 953 00:38:56,800 --> 00:38:57,850 pohybující se v seznamu. 954 00:38:57,850 --> 00:39:00,800 Mohli bychom mít název pro Andyho, ale není proměnná s názvem Andy. 955 00:39:00,800 --> 00:39:04,320 Pouze jiné proměnné máme, je První, kdo zastupuje Gabe. 956 00:39:04,320 --> 00:39:07,690 >> Takže to je vlastně důvod, proč se tak Zatím jsme to potřebovali to. 957 00:39:07,690 --> 00:39:10,846 Ale teď na obrazovce je znovu zmínit o pred ukazatele. 958 00:39:10,846 --> 00:39:11,970 Tak nech mě být konkrétnější. 959 00:39:11,970 --> 00:39:14,820 Pokud je to ukazatel, měl jsem lepší trochu inteligentnější 960 00:39:14,820 --> 00:39:15,950 o mém iteraci. 961 00:39:15,950 --> 00:39:19,580 Pokud vám nevadí, že můj prochází zde opět ukázal zde, ukazuje zde. 962 00:39:19,580 --> 00:39:22,500 Ale dovolte mi mít pred ukazatel, předchůdce ukazatel, který je 963 00:39:22,500 --> 00:39:24,740 druh ukazuje na element jsem byla na. 964 00:39:24,740 --> 00:39:27,330 Takže když jdu tady a teď Moje levá ruka aktualizace. 965 00:39:27,330 --> 00:39:29,370 Když jdu tady moje levá aktualizace ručně. 966 00:39:29,370 --> 00:39:33,090 A teď mám nejen ukazatel prvek, který jde po Julii, 967 00:39:33,090 --> 00:39:36,300 Stále mám ukazatel Andy, prvek před. 968 00:39:36,300 --> 00:39:39,430 Takže budete mít přístup, v podstatě, strouhanka, chcete-li, 969 00:39:39,430 --> 00:39:41,500 na všech potřebných ukazatelů. 970 00:39:41,500 --> 00:39:43,710 >> Takže když jsem ukázal na Andy a já jsem také ukázal 971 00:39:43,710 --> 00:39:47,105 u křesťana, jehož ruce by nyní měla být zdůrazněno jinde? 972 00:39:47,105 --> 00:39:48,770 973 00:39:48,770 --> 00:39:51,960 Takže Andy nyní lze poukázat na Julii. 974 00:39:51,960 --> 00:39:54,460 Julia se nyní poukázat na Christiana. 975 00:39:54,460 --> 00:39:56,950 Vzhledem k tomu, že můžete kopírovat moje pravá ruka je ukazatel. 976 00:39:56,950 --> 00:40:00,044 A to vám účinně přenáší zpět na toto místo zde. 977 00:40:00,044 --> 00:40:02,460 Takže stručně řečeno, i když toto nás bere druh navždy 978 00:40:02,460 --> 00:40:04,510 skutečně aktualizovat spojový seznam, realizovat 979 00:40:04,510 --> 00:40:06,580 že operace jsou relativně jednoduché. 980 00:40:06,580 --> 00:40:10,030 Je to z jednoho, dva, tři řádků kódu nakonec. 981 00:40:10,030 --> 00:40:12,780 Ale omotal kolem těch řádků kódu pravděpodobně 982 00:40:12,780 --> 00:40:16,350 je trochu logiky, která účinně klade otázku, kde to jsme? 983 00:40:16,350 --> 00:40:18,970 Jsme na začátku, střední, nebo konec? 984 00:40:18,970 --> 00:40:21,890 >> Nyní, tam jsou určitě jiné operace můžeme realizovat. 985 00:40:21,890 --> 00:40:24,880 A tyhle fotky zde jen popsat to, co jsme právě dělali s lidmi. 986 00:40:24,880 --> 00:40:26,080 Co je odstranění? 987 00:40:26,080 --> 00:40:30,650 Pokud chci, například, odebrat číslo 34 nebo 55, 988 00:40:30,650 --> 00:40:34,680 Možná mám stejný druh kódu, ale budu potřebovat jeden nebo dva kroky. 989 00:40:34,680 --> 00:40:36,110 Vzhledem k tomu, co je nového? 990 00:40:36,110 --> 00:40:40,460 Mám-li odstranit někoho, kdo na konci, jako číslo 55 a 34, 991 00:40:40,460 --> 00:40:42,995 co má také změnit, jak to udělat? 992 00:40:42,995 --> 00:40:44,870 Musím se evict-- co se jmenuješ? 993 00:40:44,870 --> 00:40:45,380 >> DIVÁKŮ: Jack. 994 00:40:45,380 --> 00:40:46,255 >> David J. Malan: Jack. 995 00:40:46,255 --> 00:40:49,770 Musím nejen evict-- zdarma Jack, tak doslova Volejte zdarma Jack, nebo alespoň 996 00:40:49,770 --> 00:40:53,530 tam ukazatel taky, ale teď to, co se musí změnit s Petrem? 997 00:40:53,530 --> 00:40:55,510 Jeho ruka lepší start směrem dolů. 998 00:40:55,510 --> 00:40:59,300 Protože jakmile jsem volat zdarma na Jacku, jestli Peter je stále ukazuje na Jacka 999 00:40:59,300 --> 00:41:02,530 a proto, aby křížení Seznam a přístup tohoto ukazatele, 1000 00:41:02,530 --> 00:41:05,650 to je, když náš starý přítel segmentace Porucha může skutečně kopat do. 1001 00:41:05,650 --> 00:41:07,860 Vzhledem k tomu, že jsme s ohledem na paměť zpět na Jacka. 1002 00:41:07,860 --> 00:41:10,760 >> Můžete tam zůstat nešikovně jen na chvíli. 1003 00:41:10,760 --> 00:41:13,410 Protože máme jen pár finální operace, aby zvážila. 1004 00:41:13,410 --> 00:41:15,600 Odstranění hlavy seznamu, nebo beginning-- a ten je 1005 00:41:15,600 --> 00:41:16,349 trochu nepříjemné. 1006 00:41:16,349 --> 00:41:19,640 Vzhledem k tomu, musíme vědět, že Gabe je tak trochu zvláštní v tomto programu. 1007 00:41:19,640 --> 00:41:21,440 Protože ve skutečnosti, má vlastní ukazatel. 1008 00:41:21,440 --> 00:41:24,860 On není jen se ukázal na, stejně jako téměř všichni ostatní tady. 1009 00:41:24,860 --> 00:41:28,112 >> Takže když v čele seznamu je odstraněna, jehož ruce je třeba změnit právě teď? 1010 00:41:28,112 --> 00:41:29,070 Jak se jmenuješ? 1011 00:41:29,070 --> 00:41:29,450 >> DIVÁKŮ: Christine. 1012 00:41:29,450 --> 00:41:31,408 >> David J. Malan: Jsem hrozný na jména, zřejmě. 1013 00:41:31,408 --> 00:41:34,011 Takže Christine a Gabe, jehož ruce je třeba změnit 1014 00:41:34,011 --> 00:41:36,510 kdy se snažíme odstranit Christine, číslo 5, z obrázku? 1015 00:41:36,510 --> 00:41:37,550 1016 00:41:37,550 --> 00:41:38,820 OK, tak se pojďme dělat Gabe. 1017 00:41:38,820 --> 00:41:40,950 Gabe se děje na bod, Lze předpokládat, že u čísla 9. 1018 00:41:40,950 --> 00:41:42,230 1019 00:41:42,230 --> 00:41:44,642 Ale co další by se mělo stát? 1020 00:41:44,642 --> 00:41:46,600 Diváků: Christine by být null [neslyšitelné]. 1021 00:41:46,600 --> 00:41:50,244 David J. Malan: OK, měli bychom asi make-- Slyšel jsem, "null" někde jinde. 1022 00:41:50,244 --> 00:41:51,410 Diváků: Null a osvobodit ji. 1023 00:41:51,410 --> 00:41:51,855 David J. Malan: Null co? 1024 00:41:51,855 --> 00:41:53,074 Diváků: Null a osvobodit ji. 1025 00:41:53,074 --> 00:41:54,490 David J. Malan: Null a osvobodit ji. 1026 00:41:54,490 --> 00:41:55,422 Takže je to velmi jednoduché. 1027 00:41:55,422 --> 00:41:58,380 A je to perfektní, že jsi teď nějak ze tam stál, která nepatří. 1028 00:41:58,380 --> 00:42:00,430 Vzhledem k tomu, že jste byl oddělena od seznamu. 1029 00:42:00,430 --> 00:42:02,820 Vy jste skutečně byli osiřel ze seznamu. 1030 00:42:02,820 --> 00:42:07,770 A tak jsme měli lepší volat zdarma nyní Christine, aby tu vzpomínku zpět. 1031 00:42:07,770 --> 00:42:10,240 Jinak pokaždé, když odstranit uzel ze seznamu 1032 00:42:10,240 --> 00:42:14,230 bychom mohli být dělat seznam kratší, ale ne ve skutečnosti snižuje 1033 00:42:14,230 --> 00:42:15,096 velikost v paměti. 1034 00:42:15,096 --> 00:42:17,720 A tak, pokud budeme držet přidávání a přidávat, přidávat věci do seznamu, 1035 00:42:17,720 --> 00:42:19,280 Můj počítač se může dostat pomalejší a pomalejší a pomalejší, 1036 00:42:19,280 --> 00:42:21,740 protože běžím z paměť, i když nejsem ve skutečnosti 1037 00:42:21,740 --> 00:42:25,580 pomocí Christine bajtů paměti ještě. 1038 00:42:25,580 --> 00:42:28,500 >> Takže na konci jsou jiné scénáře, z course-- odstranění 1039 00:42:28,500 --> 00:42:30,640 ve středu, odstranění Na konci, jak jsme viděli. 1040 00:42:30,640 --> 00:42:32,348 Ale ještě zajímavější Nyní je 1041 00:42:32,348 --> 00:42:34,770 bude uvažovat přesně co je doba chodu je. 1042 00:42:34,770 --> 00:42:36,640 Takže nejen můžete nechat kousky papíru, v případě, Gabe, 1043 00:42:36,640 --> 00:42:38,640 by vám nevadilo dát každý stres míček. 1044 00:42:38,640 --> 00:42:42,100 Děkuji moc našeho propojeného seznamu dobrovolníků tady, kdybys mohl. 1045 00:42:42,100 --> 00:42:45,320 >> [APPLAUSE] 1046 00:42:45,320 --> 00:42:46,700 >> David J. Malan: Dobře. 1047 00:42:46,700 --> 00:42:51,110 Takže pár analytické otázek, pak, kdybych mohl. 1048 00:42:51,110 --> 00:42:59,670 Jsme viděl tento zápis, velké O a omega, horní hranice 1049 00:42:59,670 --> 00:43:02,520 a dolní hranice na doba chodu nějakého algoritmu. 1050 00:43:02,520 --> 00:43:04,950 Takže uvažujme jen pár otázek. 1051 00:43:04,950 --> 00:43:07,090 >> Jednou, a to řekl, že jsme předtím, co je běh 1052 00:43:07,090 --> 00:43:10,647 Doba hledání seznam, pokud jde o velké O? 1053 00:43:10,647 --> 00:43:13,480 Co je to horní mez na provoz Doba hledání spojový seznam 1054 00:43:13,480 --> 00:43:16,340 jak realizovat naše dobrovolníky tady? 1055 00:43:16,340 --> 00:43:17,820 Je to velký O n, lineární. 1056 00:43:17,820 --> 00:43:20,630 Vzhledem k tomu, v nejhorším případě, prvek, jako je 55, 1057 00:43:20,630 --> 00:43:23,830 můžeme hledat, kde by mohla být Jack, úplně na konci. 1058 00:43:23,830 --> 00:43:28,250 A bohužel, na rozdíl od řady nemůžeme dostat chuť tentokrát. 1059 00:43:28,250 --> 00:43:31,820 I přesto, že všichni naši lidé byli řazeny od malých prvků, 5, 1060 00:43:31,820 --> 00:43:35,900 celou cestu až do většího prvku, 55, je to obvykle dobrá věc. 1061 00:43:35,900 --> 00:43:38,815 Ale to, co dělá tento předpoklad už nám umožňují dělat? 1062 00:43:38,815 --> 00:43:39,775 1063 00:43:39,775 --> 00:43:40,650 Diváků: [neslyšitelné] 1064 00:43:40,650 --> 00:43:40,920 David J. Malan: znovu, řekni? 1065 00:43:40,920 --> 00:43:41,800 Diváků: Random přístup. 1066 00:43:41,800 --> 00:43:43,049 David J. Malan: s náhodným přístupem. 1067 00:43:43,049 --> 00:43:46,330 A zase to znamená, že můžeme bez dále používat slabý nuly, intuice, 1068 00:43:46,330 --> 00:43:49,365 a samozřejmost použití binární vyhledávání a rozděl a panuj. 1069 00:43:49,365 --> 00:43:51,240 Vzhledem k tomu, i když jsme lidé mohli samozřejmě 1070 00:43:51,240 --> 00:43:54,610 vidět, že Andy a Christian byli zhruba v polovině seznamu, 1071 00:43:54,610 --> 00:43:57,670 Víme jen, že jako Počítač sbíráním na seznam 1072 00:43:57,670 --> 00:43:59,029 od samého začátku. 1073 00:43:59,029 --> 00:44:00,570 Tak jsme se vzdali, že náhodný přístup. 1074 00:44:00,570 --> 00:44:04,380 >> Tak velký O n je nyní horní vázané na našeho vyhledávacího času. 1075 00:44:04,380 --> 00:44:07,920 Co omega našeho vyhledávání? 1076 00:44:07,920 --> 00:44:11,535 Co je dolní mez na vyhledávání pro nějaké číslo v tomto seznamu? 1077 00:44:11,535 --> 00:44:12,410 Diváků: [neslyšitelné] 1078 00:44:12,410 --> 00:44:13,040 David J. Malan: znovu, řekni? 1079 00:44:13,040 --> 00:44:13,420 DIVÁKŮ: One. 1080 00:44:13,420 --> 00:44:13,800 David J. Malan: One. 1081 00:44:13,800 --> 00:44:14,760 Takže časová konstanta. 1082 00:44:14,760 --> 00:44:17,020 V nejlepším případě, Christine opravdu na začátku seznamu. 1083 00:44:17,020 --> 00:44:19,020 A my hledáme číslo 5, takže jsme ji našli. 1084 00:44:19,020 --> 00:44:19,787 Takže žádný velký problém. 1085 00:44:19,787 --> 00:44:22,370 Ale to musí být na začátku seznamu v tomto případě. 1086 00:44:22,370 --> 00:44:23,745 Co asi něco jako Delete? 1087 00:44:23,745 --> 00:44:24,717 1088 00:44:24,717 --> 00:44:26,300 Co když chcete smazat prvek? 1089 00:44:26,300 --> 00:44:29,200 Co je horní mez a dolní mez o smazání něco z spojena 1090 00:44:29,200 --> 00:44:29,699 Seznam? 1091 00:44:29,699 --> 00:44:35,195 1092 00:44:35,195 --> 00:44:36,070 Diváků: [neslyšitelné] 1093 00:44:36,070 --> 00:44:36,420 David J. Malan: znovu, řekni? 1094 00:44:36,420 --> 00:44:37,067 DIVÁKŮ: n. 1095 00:44:37,067 --> 00:44:38,900 David J. Malan: n je opravdu horní mez. 1096 00:44:38,900 --> 00:44:41,700 Vzhledem k tomu, v nejhorším případě se snažíme odstranit Jacka, jako jsme to udělal. 1097 00:44:41,700 --> 00:44:43,050 Je to úplně na konci. 1098 00:44:43,050 --> 00:44:45,419 Nám trvá celou věčnost, nebo n kroky, aby ho našli. 1099 00:44:45,419 --> 00:44:46,460 Tak to je horní hranice. 1100 00:44:46,460 --> 00:44:47,430 To je lineární, jistě. 1101 00:44:47,430 --> 00:44:50,970 A v nejlepším případě doba chodu nebo dolní hranice v nejlepším případě 1102 00:44:50,970 --> 00:44:51,975 by být konstantní čas. 1103 00:44:51,975 --> 00:44:54,600 Vzhledem k tomu, že bychom se snaží odstranit Christine, a my jen mít štěstí 1104 00:44:54,600 --> 00:44:55,558 ona je na začátku. 1105 00:44:55,558 --> 00:44:56,350 Nyní počkejte chvilku. 1106 00:44:56,350 --> 00:44:59,370 Gabe byl také na začátku, a také jsme museli aktualizovat Gabe. 1107 00:44:59,370 --> 00:45:01,150 Takže to nebyl jen jeden krok. 1108 00:45:01,150 --> 00:45:04,210 Tak to je opravdu konstantní Doba, v nejlepším případě, 1109 00:45:04,210 --> 00:45:06,345 k odstranění nejmenší prvek? 1110 00:45:06,345 --> 00:45:07,360 1111 00:45:07,360 --> 00:45:10,960 To znamená, že i když to může být dvě, tři, nebo dokonce sto řádků kódu, 1112 00:45:10,960 --> 00:45:14,000 jestli je to stejný počet linky, ne v nějaké smyčce, 1113 00:45:14,000 --> 00:45:16,577 a nezávisí na velikosti seznamu, absolutně. 1114 00:45:16,577 --> 00:45:18,660 Odstranění prvku na začátek seznamu, 1115 00:45:18,660 --> 00:45:21,940 i když máme co do činění s Gabe, je stále konstantní čas. 1116 00:45:21,940 --> 00:45:24,220 >> Takže to vypadá, masivní krok zpět. 1117 00:45:24,220 --> 00:45:27,000 A co je ztráta času v případě, v jednom týdnu a týden 1118 00:45:27,000 --> 00:45:30,250 nula jsme měli nejen pseudokód kód, ale skutečný kód 1119 00:45:30,250 --> 00:45:35,780 realizovat něco, co deník base n, nebo přihláste spíše n, základ 2, 1120 00:45:35,780 --> 00:45:37,150 pokud jde o jeho provozu. 1121 00:45:37,150 --> 00:45:40,710 Tak proč sakra bychom chtěli začít používat něco jako propojeného seznamu? 1122 00:45:40,710 --> 00:45:41,517 Jo. 1123 00:45:41,517 --> 00:45:44,022 >> Diváků: Takže můžete přidat prvky do pole. 1124 00:45:44,022 --> 00:45:46,230 David J. Malan:, takže můžete přidat prvky do pole. 1125 00:45:46,230 --> 00:45:47,550 I to je tematická. 1126 00:45:47,550 --> 00:45:49,740 A budeme i nadále vidět by tento trade-off, hodně 1127 00:45:49,740 --> 00:45:51,573 jak jsme viděli, trade-off s slučovací druhu. 1128 00:45:51,573 --> 00:45:54,606 Opravdu by se urychlit vyhledávání nebo třídění, spíše 1129 00:45:54,606 --> 00:45:57,480 pokud bychom strávit trochu více prostoru a mají další kus paměti 1130 00:45:57,480 --> 00:45:58,760 nebo pole pro sloučení druhu. 1131 00:45:58,760 --> 00:46:01,270 Ale trávíme více prostor, ale šetří čas. 1132 00:46:01,270 --> 00:46:04,820 V tomto případě jsme vzdát se času, ale my jsme 1133 00:46:04,820 --> 00:46:08,170 získání flexibility, dynamika chcete-li, 1134 00:46:08,170 --> 00:46:10,280 což je pravděpodobně pozitivní vlastnost. 1135 00:46:10,280 --> 00:46:11,520 >> Jsme také výdaje prostor. 1136 00:46:11,520 --> 00:46:13,710 V jakém smyslu je spojen Seznam dražší 1137 00:46:13,710 --> 00:46:15,700 z hlediska prostoru, než pole? 1138 00:46:15,700 --> 00:46:18,379 1139 00:46:18,379 --> 00:46:19,920 Pokud je prostor navíc přichází? 1140 00:46:19,920 --> 00:46:20,460 Jo? 1141 00:46:20,460 --> 00:46:21,800 >> Diváků: [neslyšitelné] ukazatel. 1142 00:46:21,800 --> 00:46:23,310 >> David J. Malan: Jo, to jsme mají také ukazatel. 1143 00:46:23,310 --> 00:46:25,560 Tak tohle je minorly nepříjemné v tom, že už jsem 1144 00:46:25,560 --> 00:46:27,780 I ukládání jen int reprezentovat int. 1145 00:46:27,780 --> 00:46:30,990 Jsem uložení int a A ukazatel, který je také 32 bitů. 1146 00:46:30,990 --> 00:46:33,470 Takže jsem doslova zdvojnásobí množství prostoru podílet. 1147 00:46:33,470 --> 00:46:36,040 Takže je to kompromis, ale to je v případě int. 1148 00:46:36,040 --> 00:46:39,580 Předpokládejme, že si nejste ukládání int, ale předpokládám, že každý z těchto obdélníků 1149 00:46:39,580 --> 00:46:43,290 nebo každý z těchto lidí byla představující slovo, anglické slovo, které 1150 00:46:43,290 --> 00:46:46,430 může mít pět znaků, 10 postavy, možná i víc. 1151 00:46:46,430 --> 00:46:49,940 Pak se přidá pouze 32 více bitů může být méně velký problém. 1152 00:46:49,940 --> 00:46:52,160 >> Co když každý ze studentů na demonstraci 1153 00:46:52,160 --> 00:46:55,107 doslova studentské structs že mají jména a domy a možná 1154 00:46:55,107 --> 00:46:57,065 telefonní čísla a Twitter zpracovává a podobně. 1155 00:46:57,065 --> 00:46:59,564 Takže všechna pole jsme začali mluví o jiný den, 1156 00:46:59,564 --> 00:47:02,410 mnohem méně velký problém, jak naše uzly dostat mnohem zajímavější 1157 00:47:02,410 --> 00:47:05,972 a velké utratit, co, další ukazatel jen jejich propojení. 1158 00:47:05,972 --> 00:47:07,180 Ale opravdu, je to kompromis. 1159 00:47:07,180 --> 00:47:09,560 A skutečně, je kód složitější, jak budete 1160 00:47:09,560 --> 00:47:11,770 viz sbíráním prostřednictvím že konkrétní příklad. 1161 00:47:11,770 --> 00:47:14,302 Ale co v případě, že byly nějaký svatý grál zde. 1162 00:47:14,302 --> 00:47:17,010 Co když nebudeme brát krok dozadu, ale masivní krok vpřed 1163 00:47:17,010 --> 00:47:19,180 a implementaci dat Struktura přes kterou 1164 00:47:19,180 --> 00:47:22,870 můžete najít prvky, jako je Jack, nebo Christine nebo jakékoli jiné prvky 1165 00:47:22,870 --> 00:47:25,870 v tomto poli v pravém konstantním čase? 1166 00:47:25,870 --> 00:47:26,920 Vyhledávání je konstantní. 1167 00:47:26,920 --> 00:47:28,320 Odstranit je konstantní. 1168 00:47:28,320 --> 00:47:29,570 Vložte je konstantní. 1169 00:47:29,570 --> 00:47:32,260 Všechny tyto operace jsou konstantní. 1170 00:47:32,260 --> 00:47:33,750 To by nám svatý grál. 1171 00:47:33,750 --> 00:47:36,690 A to je místo, kde jsme se zvedne příště. 1172 00:47:36,690 --> 00:47:38,600 Uvidíme se pak. 1173 00:47:38,600 --> 00:47:39,371