1 00:00:00,000 --> 00:00:11,860 2 00:00:11,860 --> 00:00:13,120 >> SPEAKER 1: Dobře, takže jsme zpátky. 3 00:00:13,120 --> 00:00:14,480 Vítejte na CS50. 4 00:00:14,480 --> 00:00:16,510 To je konec týdne sedm. 5 00:00:16,510 --> 00:00:20,200 Takže připomenout, že minule jsme začali při pohledu na něco propracovanější 6 00:00:20,200 --> 00:00:21,100 datové struktury. 7 00:00:21,100 --> 00:00:25,110 Vzhledem k tomu, až do teď, jsme měli opravdu máme k dispozici to bylo, pole. 8 00:00:25,110 --> 00:00:29,340 >> Ale dříve, než jsme se zbavit pole tak, že vše zajímavé, což opravdu to 9 00:00:29,340 --> 00:00:33,570 ve skutečnosti je, jaké jsou některé z klady tohoto jednoduchého dat 10 00:00:33,570 --> 00:00:34,560 struktura tak daleko? 11 00:00:34,560 --> 00:00:36,110 Co je to dobrý? 12 00:00:36,110 --> 00:00:39,450 Zatím, jak jsme viděli? 13 00:00:39,450 --> 00:00:42,540 Co to máš? 14 00:00:42,540 --> 00:00:44,028 Nic. 15 00:00:44,028 --> 00:00:45,020 >> STUDENT: [neslyšitelné]. 16 00:00:45,020 --> 00:00:45,395 >> SPEAKER 1: Co je to? 17 00:00:45,395 --> 00:00:46,410 >> STUDENT: [neslyšitelné]. 18 00:00:46,410 --> 00:00:47,000 >> SPEAKER 1: Pevná velikost. 19 00:00:47,000 --> 00:00:51,260 OK, tak proč je pevnou velikost dobrý i když? 20 00:00:51,260 --> 00:00:53,180 >> STUDENT: [neslyšitelné]. 21 00:00:53,180 --> 00:00:56,240 >> SPEAKER 1: OK, takže je to efektivní pocit, že můžete přidělovat 22 00:00:56,240 --> 00:01:00,070 pevná částka z vesmíru, což snad je přesně tolik, kolik 23 00:01:00,070 --> 00:01:01,180 prostor tak, jak chcete. 24 00:01:01,180 --> 00:01:02,720 Takže to může být naprosto plus. 25 00:01:02,720 --> 00:01:06,530 >> Co jiného se strana pole? 26 00:01:06,530 --> 00:01:07,610 Jo? 27 00:01:07,610 --> 00:01:08,750 >> STUDENT: [neslyšitelné]. 28 00:01:08,750 --> 00:01:09,550 >> SPEAKER 1: All - Cože? 29 00:01:09,550 --> 00:01:11,270 >> STUDENT: [neslyšitelné]. 30 00:01:11,270 --> 00:01:13,620 >> SPEAKER 1: Všechny boxy v paměti nebo vedle sebe. 31 00:01:13,620 --> 00:01:15,220 A to je užitečné - proč? 32 00:01:15,220 --> 00:01:15,970 To je docela pravda. 33 00:01:15,970 --> 00:01:18,611 Ale jak můžeme využít, že pravdu? 34 00:01:18,611 --> 00:01:21,500 >> STUDENT: [neslyšitelné]. 35 00:01:21,500 --> 00:01:24,490 >> SPEAKER 1: Přesně tak, můžeme sledovat kde je vše jen na základě znalosti 36 00:01:24,490 --> 00:01:28,560 jednu adresu, a to na adresu první byte tohoto bloku paměti. 37 00:01:28,560 --> 00:01:30,420 Nebo v případě, že řetězec, adresa první 38 00:01:30,420 --> 00:01:31,460 char v tomto řetězci. 39 00:01:31,460 --> 00:01:33,330 A odtud můžeme nalézt konec řetězce. 40 00:01:33,330 --> 00:01:35,710 Najdeme zde Druhý prvek, Třetí část, a tak dále. 41 00:01:35,710 --> 00:01:38,740 >> A tak fantastický způsob, jak to popsat je, že pole nám 42 00:01:38,740 --> 00:01:40,020 náhodný přístup. 43 00:01:40,020 --> 00:01:44,330 Jen pomocí hranatou závorkou zápis a číslo, můžete přeskočit na 44 00:01:44,330 --> 00:01:48,070 specifický prvek v poli v konstantním čase, velké O 45 00:01:48,070 --> 00:01:49,810 jednoho, abych tak řekl. 46 00:01:49,810 --> 00:01:51,080 >> Ale tam bylo nějaké stinné stránky. 47 00:01:51,080 --> 00:01:53,110 Co pole neudělal velmi snadno? 48 00:01:53,110 --> 00:01:55,810 49 00:01:55,810 --> 00:01:57,170 Co je to vůbec dobré? 50 00:01:57,170 --> 00:01:58,810 >> STUDENT: [neslyšitelné]. 51 00:01:58,810 --> 00:01:59,860 >> SPEAKER 1: Co je to? 52 00:01:59,860 --> 00:02:00,530 >> STUDENT: [neslyšitelné]. 53 00:02:00,530 --> 00:02:01,460 >> Reproduktor 1: Rozšíření ve velikosti. 54 00:02:01,460 --> 00:02:04,800 Takže stinné pole jsou přesně opak toho, co 55 00:02:04,800 --> 00:02:05,540 upsides jsou. 56 00:02:05,540 --> 00:02:07,610 Takže jedna z nevýhod je že je to pevnou velikost. 57 00:02:07,610 --> 00:02:09,400 Takže si můžete opravdu ji pěstovat. 58 00:02:09,400 --> 00:02:13,510 Můžete přidělit větší kus paměť, a pak se přesunout staré prvky 59 00:02:13,510 --> 00:02:14,460 do nového pole. 60 00:02:14,460 --> 00:02:18,060 A pak bez stará pole, pro instance, pomocí malloc nebo podobný 61 00:02:18,060 --> 00:02:21,180 funkce je volána realloc, které realokuje paměť. 62 00:02:21,180 --> 00:02:25,490 >> Realloc, jako stranou, se snaží, aby vám paměť, která je vedle pole 63 00:02:25,490 --> 00:02:26,610 že již máte. 64 00:02:26,610 --> 00:02:28,740 Ale to by se věci pohnuly asi úplně. 65 00:02:28,740 --> 00:02:30,710 Ale ve zkratce, je to drahé, ne? 66 00:02:30,710 --> 00:02:33,440 Protože pokud máte kus paměti této velikosti, ale opravdu chci 67 00:02:33,440 --> 00:02:36,710 této velikosti, a chcete zachovat zachovány původní prvky, budete muset 68 00:02:36,710 --> 00:02:40,510 zhruba lineární čas Proces kopírování že je třeba, aby se stalo od 69 00:02:40,510 --> 00:02:41,900 staré na nové pole. 70 00:02:41,900 --> 00:02:44,630 A realita se ptá provozní systém znovu a znovu a 71 00:02:44,630 --> 00:02:48,340 opět velké kusy paměti může začít stát nějaký čas stejně. 72 00:02:48,340 --> 00:02:52,250 Takže je to požehnáním i prokletím v zastírat, že tato pole 73 00:02:52,250 --> 00:02:53,860 jsou pevné délky. 74 00:02:53,860 --> 00:02:56,790 Ale když si představíme něco místo takhle, kterou nazývá propojený 75 00:02:56,790 --> 00:03:00,580 seznam, dostaneme několik upsides a několik stinné i zde. 76 00:03:00,580 --> 00:03:05,780 >> Takže spojový seznam je prostě dat struktura tvořena structs C v tomto 77 00:03:05,780 --> 00:03:09,850 případ, kdy struct, odvolání, je jen kontejner pro jeden nebo více specifických 78 00:03:09,850 --> 00:03:11,100 typy proměnných. 79 00:03:11,100 --> 00:03:16,110 V tomto případě, co si datové typy Zdá se, že uvnitř struct, který 80 00:03:16,110 --> 00:03:17,600 naposledy jsme nazývaný uzel? 81 00:03:17,600 --> 00:03:19,380 Každý z těchto obdélníků je uzel. 82 00:03:19,380 --> 00:03:22,660 A každý z menších obdélníků uvnitř ní je datový typ. 83 00:03:22,660 --> 00:03:25,300 Jaké typy si říkáme byli v pondělí? 84 00:03:25,300 --> 00:03:26,478 Jo? 85 00:03:26,478 --> 00:03:27,870 >> STUDENT: [neslyšitelné]. 86 00:03:27,870 --> 00:03:30,721 >> SPEAKER 1: variabilní a ukazatel nebo Přesněji řečeno, int, pro N, 87 00:03:30,721 --> 00:03:32,180 a ukazatel v dolní části. 88 00:03:32,180 --> 00:03:35,360 Oba ti stalo, že 32 bitů na alespoň na počítači, jako je tento CS50 89 00:03:35,360 --> 00:03:37,980 Zařízení, a tak jsou tažené stejně ve velikosti. 90 00:03:37,980 --> 00:03:42,260 >> Takže to, co používáte ukazatel když za zjevně? 91 00:03:42,260 --> 00:03:47,690 Proč přidat na tuto šipku teď, když pole bylo tak pěkné a čisté a jednoduché? 92 00:03:47,690 --> 00:03:50,460 Co dělá ukazatel pro nás v každé z těchto uzlů? 93 00:03:50,460 --> 00:03:52,160 >> STUDENT: [neslyšitelné]. 94 00:03:52,160 --> 00:03:52,465 >> SPEAKER 1: Přesně tak. 95 00:03:52,465 --> 00:03:54,120 Je to řekne, kde další je. 96 00:03:54,120 --> 00:03:57,350 Tak nějak jsem použít analogii pomocí vlákno nějak 97 00:03:57,350 --> 00:03:59,180 nit těchto uzlů dohromady. 98 00:03:59,180 --> 00:04:01,760 A to je přesně to, co děláme s ukazatele, protože každý z nich 99 00:04:01,760 --> 00:04:06,360 kousky paměti může, ale nemusí být souvislé, zády k sobě k sobě 100 00:04:06,360 --> 00:04:09,500 v paměti RAM, protože pokaždé, když se volání malloc řekl, dej mi dost 101 00:04:09,500 --> 00:04:12,510 bajtů pro nový uzel, mohlo by to tu, nebo by to mohlo být. 102 00:04:12,510 --> 00:04:13,120 Mohlo by to být tady. 103 00:04:13,120 --> 00:04:13,730 Mohlo by to být tady. 104 00:04:13,730 --> 00:04:14,640 Prostě nevím. 105 00:04:14,640 --> 00:04:17,880 >> Ale s použitím ukazatele na adresy ty uzly, můžete steh je 106 00:04:17,880 --> 00:04:22,370 společně tak, že vypadá vizuálně jako seznam, i když tyto věci jsou 107 00:04:22,370 --> 00:04:26,770 vše rozprostřené v celém jednom nebo vaše dvě nebo čtyři gigabajty vaše RAM 108 00:04:26,770 --> 00:04:28,760 uvnitř vašeho vlastního počítače. 109 00:04:28,760 --> 00:04:33,230 >> Tak nevýhodou, pak, spojový seznam je co? 110 00:04:33,230 --> 00:04:34,670 Co je to cena, kterou jsme zřejmě platit? 111 00:04:34,670 --> 00:04:36,010 >> STUDENT: [neslyšitelné]. 112 00:04:36,010 --> 00:04:36,920 >> SPEAKER 1: Více prostoru, ne? 113 00:04:36,920 --> 00:04:39,340 My jsme v tomto případě, zdvojnásobil množství prostoru, protože jsme šli 114 00:04:39,340 --> 00:04:43,500 z 32 bitů pro každý uzel, pro každou int, takže teď 64 bitů, protože musíme 115 00:04:43,500 --> 00:04:45,050 držet kolem ukazatel stejně. 116 00:04:45,050 --> 00:04:48,860 Získáte větší účinnost, pokud váš struct je větší než tato jednoduchá věc. 117 00:04:48,860 --> 00:04:52,020 Pokud jste skutečně studenta uvnitř z nichž je několik stringů 118 00:04:52,020 --> 00:04:55,430 jméno a dům, možná číslo, možná některých dalších oborů dohromady. 119 00:04:55,430 --> 00:04:59,000 >> Takže pokud máte dostatečně velký struct, pak možná cena ukazatel je 120 00:04:59,000 --> 00:05:00,010 není tak velký problém. 121 00:05:00,010 --> 00:05:03,570 Toto je trochu rohové případu v tom, že jsme ukládání takový jednoduchý primitivní 122 00:05:03,570 --> 00:05:04,760 uvnitř propojeného seznamu. 123 00:05:04,760 --> 00:05:05,790 Ale jde o to samé. 124 00:05:05,790 --> 00:05:08,230 Ty určitě trávit více paměť, ale vy jste stále 125 00:05:08,230 --> 00:05:08,990 flexibilita. 126 00:05:08,990 --> 00:05:12,280 Protože teď, když chci přidat prvek na začátku tohoto seznamu, 127 00:05:12,280 --> 00:05:14,340 Musím přidělit nový uzel. 128 00:05:14,340 --> 00:05:17,180 A já mám jen ty aktualizace šipky jaksi jen pohybující 129 00:05:17,180 --> 00:05:17,980 několik rad kolem. 130 00:05:17,980 --> 00:05:20,580 >> Pokud chci vložit něco do uprostřed seznamu, nemám na 131 00:05:20,580 --> 00:05:24,410 tlačit všechny stranou, jako tomu bylo v minulost týdnů s našimi dobrovolníky, kteří 132 00:05:24,410 --> 00:05:25,700 představovala pole. 133 00:05:25,700 --> 00:05:29,470 Dovedu si vyhradit nový uzel a pak stačí poukázat na šipky v 134 00:05:29,470 --> 00:05:32,290 různé směry, protože to není musí zůstat v aktuální 135 00:05:32,290 --> 00:05:35,670 paměť pravda, linka, jako bych vypracovány je to tady na obrazovce. 136 00:05:35,670 --> 00:05:38,400 >> A pak konečně, pokud chcete vložit něco na konec seznamu, je 137 00:05:38,400 --> 00:05:39,210 ještě jednodušší. 138 00:05:39,210 --> 00:05:43,320 To je trochu libovolného notaci, ale 34 je ukazatel, hádejte. 139 00:05:43,320 --> 00:05:46,710 Jaká je hodnota jeho ukazatel nejvíce pravděpodobně vyvodit něco jako starý 140 00:05:46,710 --> 00:05:47,700 Škola anténa tam? 141 00:05:47,700 --> 00:05:48,920 >> STUDENT: [neslyšitelné]. 142 00:05:48,920 --> 00:05:49,900 >> SPEAKER 1: Je to asi null. 143 00:05:49,900 --> 00:05:52,710 A opravdu to je jedna autora zastoupení null. 144 00:05:52,710 --> 00:05:56,310 A to je null, protože jste naprosto Potřebujete vědět, kde je konec spojového 145 00:05:56,310 --> 00:06:00,050 seznam, jinak budete mít následující a sledování a po těchto šipek 146 00:06:00,050 --> 00:06:01,170 do určité hodnoty odpadky. 147 00:06:01,170 --> 00:06:06,230 Takže null bude znamenat, že neexistuje více uzlů napravo od čísla 34, 148 00:06:06,230 --> 00:06:07,200 v tomto případě. 149 00:06:07,200 --> 00:06:10,270 >> Takže navrhujeme, že můžeme realizovat tento uzel v kódu. 150 00:06:10,270 --> 00:06:12,130 A my jsme viděli tento druh syntaxe před. 151 00:06:12,130 --> 00:06:15,090 Typedef jen definuje nový typ nám, nám dává jako synonymum 152 00:06:15,090 --> 00:06:17,100 string byl pro char *. 153 00:06:17,100 --> 00:06:21,030 V tomto případě to bude, aby nám zkrácený zápis tak, že struct uzel 154 00:06:21,030 --> 00:06:24,010 Místo toho můžete být jen zapsat jako uzel, který je mnohem čistší. 155 00:06:24,010 --> 00:06:25,360 Je to mnohem méně upovídaný. 156 00:06:25,360 --> 00:06:30,080 >> Uvnitř uzlu je zřejmě int tzv. n, a pak struct node * 157 00:06:30,080 --> 00:06:34,670 což znamená, že přesně to, co jsme chtěli šipky znamená, ukazatel na další 158 00:06:34,670 --> 00:06:36,940 uzel přesně stejného typu. 159 00:06:36,940 --> 00:06:40,300 A já navrhuji, abychom mohli realizovat vyhledávací funkce jako je tento, který v 160 00:06:40,300 --> 00:06:41,890 první pohled by se mohlo zdát trochu složitější. 161 00:06:41,890 --> 00:06:43,330 Ale podívejme se, že v kontextu. 162 00:06:43,330 --> 00:06:45,480 >> Nech mě jít přes spotřebiče tady. 163 00:06:45,480 --> 00:06:48,460 Dovolte mi otevřít soubor s názvem Seznam nulový bod h. 164 00:06:48,460 --> 00:06:53,950 A že obsahuje pouze definici my právě viděl před chvílí na tato data 165 00:06:53,950 --> 00:06:55,390 typ nazývaný uzel. 166 00:06:55,390 --> 00:06:57,350 Takže jsme dali, že do souboru dot hodin. 167 00:06:57,350 --> 00:07:01,430 >> A jak je stranou, i když to program, který se chystáte vidět, je 168 00:07:01,430 --> 00:07:05,410 není tak složité, je to ve skutečnosti Konvence při psaní programu 169 00:07:05,410 --> 00:07:10,270 dát věci jako datové typy, táhnout konstanty někdy uvnitř vašeho 170 00:07:10,270 --> 00:07:13,210 hlavičkový soubor a ne nutně v Váš soubor C, jistě, když si 171 00:07:13,210 --> 00:07:17,370 Programy se větší a větší, takže víte, kde hledat a to jak pro 172 00:07:17,370 --> 00:07:20,840 dokumentace v některých případech, nebo pro základy, jako je toto, 173 00:07:20,840 --> 00:07:22,360 Definice některých typů. 174 00:07:22,360 --> 00:07:25,680 >> Kdybych se tak otevírá seznam nulovou tečku c, všimněte si pár věcí. 175 00:07:25,680 --> 00:07:29,090 Obsahuje několik hlavičkové soubory, většina které jsme ještě neviděli. 176 00:07:29,090 --> 00:07:31,980 Obsahuje vlastní hlavičkový soubor. 177 00:07:31,980 --> 00:07:35,200 >> A stranou, proč je to dvakrát cituje zde, na rozdíl od úhlu 178 00:07:35,200 --> 00:07:38,340 držáky na trati, která Jsem zdůraznil, že? 179 00:07:38,340 --> 00:07:39,180 >> STUDENT: [neslyšitelné]. 180 00:07:39,180 --> 00:07:40,460 >> SPEAKER 1: Jo, tak to je místní soubor. 181 00:07:40,460 --> 00:07:44,300 Takže jestli je to místní soubor z vašich vlastních zde na lince 15, například, můžete použít 182 00:07:44,300 --> 00:07:46,570 uvozovky místo z šikmých závorkách. 183 00:07:46,570 --> 00:07:48,270 >> Teď je to docela zajímavé. 184 00:07:48,270 --> 00:07:51,830 Všimněte si, že jsem prohlásil, globální proměnnou v tomto programu na řádku 18 185 00:07:51,830 --> 00:07:55,910 tzv. první, myšlenka je to bude ukazatel na první 186 00:07:55,910 --> 00:07:59,190 uzel v mém propojeného seznamu, a já jsem inicializována, na hodnotu null, protože jsem 187 00:07:59,190 --> 00:08:02,310 není přiděleno žádné skutečné uzly jen zatím. 188 00:08:02,310 --> 00:08:07,570 >> Takže to znamená, obrazově, co jsme viděl před chvílí na obrázku jako 189 00:08:07,570 --> 00:08:10,090 že ukazatel na daleko levé straně. 190 00:08:10,090 --> 00:08:12,260 Takže teď, že ukazatel nemá šipku. 191 00:08:12,260 --> 00:08:14,590 Je to místo je jen null. 192 00:08:14,590 --> 00:08:17,880 Ale představuje to, co bude adresa první skutečný 193 00:08:17,880 --> 00:08:19,480 uzel v tomto seznamu. 194 00:08:19,480 --> 00:08:22,120 Tak jsem se provádění je globální protože, jak uvidíte, to vše 195 00:08:22,120 --> 00:08:25,310 Program se v životě realizovat spojový seznam pro mě. 196 00:08:25,310 --> 00:08:27,050 >> Teď mám několik prototypů zde. 197 00:08:27,050 --> 00:08:31,190 Rozhodl jsem se implementovat funkce, jako je mazání, vkládání, vyhledávání a 198 00:08:31,190 --> 00:08:31,740 průchod - 199 00:08:31,740 --> 00:08:35,210 poslední být jen pěšky přes seznam, vytištění jeho prvky. 200 00:08:35,210 --> 00:08:36,750 A teď je můj hlavní rutina. 201 00:08:36,750 --> 00:08:39,890 A nebudeme trávit příliš mnoho času na to, protože to je něco, doufejme 202 00:08:39,890 --> 00:08:41,780 starý klobouk nyní. 203 00:08:41,780 --> 00:08:45,370 >> Chystám se udělat následující, zatímco uživatel spolupracuje. 204 00:08:45,370 --> 00:08:47,300 Takže jedno, já jdu k tisku z tohoto menu. 205 00:08:47,300 --> 00:08:49,420 A já jsem ho formátovat jako čistě, jak jsem mohl. 206 00:08:49,420 --> 00:08:52,240 Pokud uživatel zadá v jednom, to znamená, že které chcete odstranit něco. 207 00:08:52,240 --> 00:08:54,560 Pokud uživatel zadá ve dvou, to znamená, že které chcete vložit něco. 208 00:08:54,560 --> 00:08:55,930 A tak dále. 209 00:08:55,930 --> 00:08:58,270 Chystám se poté vás vyzve pak na příkaz. 210 00:08:58,270 --> 00:08:59,300 A pak budu používat GetInt. 211 00:08:59,300 --> 00:09:02,790 >> Tak to je opravdu jednoduché menuing interface, kde stačí zadat 212 00:09:02,790 --> 00:09:05,270 číslo mapování na jeden z těchto příkazů. 213 00:09:05,270 --> 00:09:08,730 A teď mám pěkný čistý vypínač prohlášení, že se to zapnout 214 00:09:08,730 --> 00:09:10,090 co uživatel napsal palců 215 00:09:10,090 --> 00:09:12,180 A když napsal jeden, já zavolejte odstranit a rozbít. 216 00:09:12,180 --> 00:09:14,380 Pokud zadali dva, já zavolejte vložit a zlomit. 217 00:09:14,380 --> 00:09:16,490 >> A teď Povšimněte si, že jsem dal každý z nich na stejném řádku. 218 00:09:16,490 --> 00:09:18,360 Je to jen stylistické rozhodnutí. 219 00:09:18,360 --> 00:09:20,210 Obvykle jsme viděli něco takhle. 220 00:09:20,210 --> 00:09:23,260 Ale já jsem se rozhodl, upřímně řečeno, můj program Podíval čitelnější, protože 221 00:09:23,260 --> 00:09:25,980 to bylo jen čtyři případy, na vypsalo to takhle. 222 00:09:25,980 --> 00:09:28,360 Zcela legitimní použití stylu. 223 00:09:28,360 --> 00:09:31,480 A já budu dělat to tak dlouho, dokud uživatel nezadali nulu, což jsem 224 00:09:31,480 --> 00:09:33,910 rozhodl, bude znamenat, že chtějí s kouřením přestat. 225 00:09:33,910 --> 00:09:36,630 >> Takže teď upozornění, co jsem dělat tady. 226 00:09:36,630 --> 00:09:38,650 Chystám se uvolnit seznamu zdánlivě. 227 00:09:38,650 --> 00:09:40,230 Ale o tom až za chvíli. 228 00:09:40,230 --> 00:09:41,640 Pojďme si nejprve tento program spustit. 229 00:09:41,640 --> 00:09:45,250 Takže mi dovolte větší terminál okna, tečka lomítko list 0. 230 00:09:45,250 --> 00:09:49,510 Chystám se jít dopředu a vložit, psaní dva, jako je číslo 50, a nyní 231 00:09:49,510 --> 00:09:51,590 uvidíte seznam je nyní 50. 232 00:09:51,590 --> 00:09:53,380 A můj textu jen posouvat se trochu. 233 00:09:53,380 --> 00:09:55,940 Takže teď všimnete seznam obsahuje číslo 50. 234 00:09:55,940 --> 00:09:58,220 >> Pojďme udělat další vložku tím, že dva. 235 00:09:58,220 --> 00:10:01,630 Pojďme zadejte číslo jako jeden. 236 00:10:01,630 --> 00:10:03,940 List je nyní jeden, následuje 50. 237 00:10:03,940 --> 00:10:06,020 Takže je to jen textová reprezentace seznamu. 238 00:10:06,020 --> 00:10:10,550 A pojďme vložit ještě jedno číslo jako číslo 42, což je snad 239 00:10:10,550 --> 00:10:14,620 chystá skončit ve středu, protože Tento program v jednotlivých druhů se 240 00:10:14,620 --> 00:10:16,320 prvky, jak to vloží nimi. 241 00:10:16,320 --> 00:10:17,220 Takže tady to máme. 242 00:10:17,220 --> 00:10:20,730 Super jednoduchý program, který by absolutně použili celou řadu, ale já 243 00:10:20,730 --> 00:10:23,280 stalo, že se pomocí propojeného seznamu jen tak mohu dynamicky 244 00:10:23,280 --> 00:10:24,610 zvětšit a zmenšit ji. 245 00:10:24,610 --> 00:10:28,470 >> Takže pojďme se podívat pro vyhledávání, když jsem spustit příkaz tři, Chci vyhledávat 246 00:10:28,470 --> 00:10:31,040 pro, řekněme, číslem 43.. 247 00:10:31,040 --> 00:10:34,190 A nic se zřejmě našel, protože jsem se vrátil žádnou odpověď. 248 00:10:34,190 --> 00:10:35,010 Tak jdeme na to znovu. 249 00:10:35,010 --> 00:10:35,690 Hledat. 250 00:10:35,690 --> 00:10:39,520 Pojďme hledání 50, nebo spíše hledání na 42, což je pěkný 251 00:10:39,520 --> 00:10:40,850 Trochu jemnější význam. 252 00:10:40,850 --> 00:10:42,610 A já jsem našel smysl života tam. 253 00:10:42,610 --> 00:10:44,990 Číslo 42, pokud nevíte, reference, Google jej. 254 00:10:44,990 --> 00:10:45,350 Dobrá. 255 00:10:45,350 --> 00:10:47,130 Takže to, co tento program pro mě udělal? 256 00:10:47,130 --> 00:10:50,660 Je to jen mi dovolil vložit tak daleko a hledání prvků. 257 00:10:50,660 --> 00:10:53,650 >> Pojďme rychle vpřed, pak se že funkce se podíval na 258 00:10:53,650 --> 00:10:55,360 v pondělí jako ukázku. 259 00:10:55,360 --> 00:10:59,620 Takže tuto funkci, tvrdím, hledá element v seznamu jako první 260 00:10:59,620 --> 00:11:03,830 jeden, upozornění uživatele a volání GetInt získat aktuální int 261 00:11:03,830 --> 00:11:05,060 které chcete vyhledat. 262 00:11:05,060 --> 00:11:06,460 >> Pak nevšiml. 263 00:11:06,460 --> 00:11:10,690 Chystám se vytvořit dočasnou proměnnou v souladu s názvem 188 ukazatel - 264 00:11:10,690 --> 00:11:11,270 PTR - 265 00:11:11,270 --> 00:11:12,440 mohla zavolat tomu nic. 266 00:11:12,440 --> 00:11:16,140 A je to ukazatel na uzel protože jsem řekl, že uzel *. 267 00:11:16,140 --> 00:11:19,900 A já inicializace je rovná nejprve tak, že jsem skutečně mít svou 268 00:11:19,900 --> 00:11:22,860 prstem, abych tak řekl, na velmi První prvek seznamu. 269 00:11:22,860 --> 00:11:27,460 Takže pokud moje pravá ruka je zde PTR jsem ukazuje na stejnou věc, že ​​první 270 00:11:27,460 --> 00:11:28,670 ukazuje na. 271 00:11:28,670 --> 00:11:31,430 >> Takže teď zpátky v kódu, co se bude dít dál - 272 00:11:31,430 --> 00:11:35,070 je to společný vzor, ​​když iterace přes struktury, jako 273 00:11:35,070 --> 00:11:35,970 spojový seznam. 274 00:11:35,970 --> 00:11:40,410 Chystám se udělat následující, zatímco ukazatel není rovno null Takže zatímco 275 00:11:40,410 --> 00:11:47,530 můj prst neukazuje na nějaké null hodnota, pokud je ukazatel šipka n se rovná n. 276 00:11:47,530 --> 00:11:52,290 Jsme si všimnete jako první, že n je to, co Uživatel napsal v přepočtu GetInts zavolat tady. 277 00:11:52,290 --> 00:11:54,280 >> A ukazatel šipka n rozumí co? 278 00:11:54,280 --> 00:11:59,020 No, pokud se vrátíme k obrázku zde když mám prst ukazující na 279 00:11:59,020 --> 00:12:02,960 že první uzel obsahuje devět, Šipka v podstatě znamená, že jít do 280 00:12:02,960 --> 00:12:08,860 uzel a chytit hodnotu při umístění n, V tomto případě jsou data pole s názvem n. 281 00:12:08,860 --> 00:12:14,120 >> Jako stranou - a viděli jsme to ještě před pár týdny, když se někdo zeptal - 282 00:12:14,120 --> 00:12:18,840 tato syntaxe je nový, ale to není nám síly, které jsme 283 00:12:18,840 --> 00:12:20,040 už nemělo. 284 00:12:20,040 --> 00:12:25,325 Co to bylo za výraz ekvivalentní k použití tečka zápis a hvězda pár 285 00:12:25,325 --> 00:12:29,490 týdny, když jsme sloupnout tato vrstva trochu předčasně? 286 00:12:29,490 --> 00:12:31,780 >> STUDENT: [neslyšitelné]. 287 00:12:31,780 --> 00:12:38,880 >> SPEAKER 1: Přesně tak, je to hvězda, a pak je to hvězda tečka n, s 288 00:12:38,880 --> 00:12:41,930 závorky zde, který vypadá, Upřímně řečeno, myslím, že spousta 289 00:12:41,930 --> 00:12:43,320 více tajemné číst. 290 00:12:43,320 --> 00:12:46,270 Ale hvězda ukazatel, jako vždy, znamená jít. 291 00:12:46,270 --> 00:12:49,090 A jakmile jste tam, jaké údaje Pole chceš přístup? 292 00:12:49,090 --> 00:12:52,730 No použít tečka notaci pro přístup struct datové pole, a já 293 00:12:52,730 --> 00:12:54,140 konkrétně chcete n. 294 00:12:54,140 --> 00:12:56,240 >> Upřímně řečeno, řekl bych to je prostě těžší číst. 295 00:12:56,240 --> 00:12:58,080 Je to těžší si vzpomenout, kde se závorky jdou, 296 00:12:58,080 --> 00:12:59,030 hvězda a to všechno. 297 00:12:59,030 --> 00:13:02,150 Aby celý svět přijal některé syntaktické cukr, abych tak řekl. 298 00:13:02,150 --> 00:13:04,740 Jen sexy způsob, jak říct, To je ekvivalentní, a 299 00:13:04,740 --> 00:13:05,970 možná více intuitivní. 300 00:13:05,970 --> 00:13:09,600 Je-li ukazatel je skutečně ukazatel, znamená notace šipky jít a najít 301 00:13:09,600 --> 00:13:11,890 pole je v tomto případě tzv. n. 302 00:13:11,890 --> 00:13:13,660 >> Takže pokud ji najdu, všimněte si, co dělám. 303 00:13:13,660 --> 00:13:17,430 Prostě vytisknout, našel jsem procent ia zapojíte hodnotou pro daný int. 304 00:13:17,430 --> 00:13:20,730 Nazval jsem spát po dobu jedné sekundy, jen aby druhu pauzy věcí na obrazovce 305 00:13:20,730 --> 00:13:22,900 poskytují uživateli druhé absorbovat co se právě stalo. 306 00:13:22,900 --> 00:13:24,290 A pak jsem se zlomit. 307 00:13:24,290 --> 00:13:26,330 Jinak, co mám dělat? 308 00:13:26,330 --> 00:13:30,960 Aktualizovat ukazatele rovna ukazatel šipku vedle. 309 00:13:30,960 --> 00:13:35,840 >> Tak aby bylo jasno, to znamená jít tam přes můj old-school notace. 310 00:13:35,840 --> 00:13:39,580 Takže to znamená jen jít do čehokoliv jste ukázal na, které velmi 311 00:13:39,580 --> 00:13:43,660 Prvním případem je, že jsem ukázal na struct s devíti v něm. 312 00:13:43,660 --> 00:13:44,510 Tak jsem šel tam. 313 00:13:44,510 --> 00:13:47,880 A pak tečka notace znamená, získat hodnotu na další. 314 00:13:47,880 --> 00:13:50,470 >> Ale hodnota, a to i když je čerpány jako úzký, jen číslo. 315 00:13:50,470 --> 00:13:51,720 Je to číselná adresa. 316 00:13:51,720 --> 00:13:55,670 Takže tento jeden řádek kódu, ať již napsal takhle víc složitější 317 00:13:55,670 --> 00:14:00,190 způsobem, nebo jako je to, o něco více intuitivní způsob, prostě znamená pohnout rukou 318 00:14:00,190 --> 00:14:03,460 z prvního uzlu na další, a pak další, a potom 319 00:14:03,460 --> 00:14:05,320 další, a tak dále. 320 00:14:05,320 --> 00:14:09,920 >> Takže nebudeme bydlet na straně druhé implementace vkládání a mazání 321 00:14:09,920 --> 00:14:14,030 a průchod, z nichž první dva které jsou poměrně zapojit. 322 00:14:14,030 --> 00:14:17,010 A myslím, že je to docela snadné se dostat ztratil, když dělá to ústně. 323 00:14:17,010 --> 00:14:19,890 Ale to, co můžeme udělat, je zde pokusu o stanovení 324 00:14:19,890 --> 00:14:21,640 nejlepší udělat to vizuálně. 325 00:14:21,640 --> 00:14:24,800 Protože bych navrhoval, že pokud bychom Chci vložit prvky do tohoto 326 00:14:24,800 --> 00:14:26,680 Stávající seznam, který má pět základních prvků - 327 00:14:26,680 --> 00:14:29,530 9, 17, 22, 26, a 33 - 328 00:14:29,530 --> 00:14:33,300 Kdybych měl jít k provedení tohoto v kód, musím zvážit, jak jít 329 00:14:33,300 --> 00:14:34,160 asi dělá. 330 00:14:34,160 --> 00:14:37,720 >> A já bych navrhnout, přičemž dítě kroky přičemž v tomto případě mám na mysli, jaké jsou 331 00:14:37,720 --> 00:14:41,090 možných scénářů, které jsme setkat obecně? 332 00:14:41,090 --> 00:14:44,120 Při provádění vložka pro propojenou seznam, to je náhodou 333 00:14:44,120 --> 00:14:46,090 Konkrétním příkladem velikosti pět. 334 00:14:46,090 --> 00:14:50,420 No, pokud chcete vložit číslo, rádi říkají, že číslo jedna, a 335 00:14:50,420 --> 00:14:53,380 udržování seřazeny objednávky, kde samozřejmě dělá číslo jedna je třeba 336 00:14:53,380 --> 00:14:55,686 jít v tomto konkrétním příkladu? 337 00:14:55,686 --> 00:14:56,840 Stejně jako na začátku. 338 00:14:56,840 --> 00:15:00,030 >> Ale co je zajímavé je, že Chcete-li vložit jeden do toho 339 00:15:00,030 --> 00:15:04,100 seznam, co potřebuje speciální ukazatel aktualizovat zřejmě? 340 00:15:04,100 --> 00:15:04,610 První. 341 00:15:04,610 --> 00:15:07,830 Takže bych si dovolil tvrdit, toto je první případ že bychom mohli chtít, aby zvážila, 342 00:15:07,830 --> 00:15:11,140 scénář zahrnující vkládání na na začátku seznamu. 343 00:15:11,140 --> 00:15:15,400 >> Pojďme trhat off možná tak jednoduché, nebo dokonce jednodušší případ, relativně vzato. 344 00:15:15,400 --> 00:15:18,110 Předpokládejme Chci vložit číslo 35 v seřazeném pořadí. 345 00:15:18,110 --> 00:15:20,600 To samozřejmě patří tam. 346 00:15:20,600 --> 00:15:25,320 Takže to, co ukazatel zřejmě bude musí být aktualizovány v tomto případě? 347 00:15:25,320 --> 00:15:30,060 34 je ukazatel stále není null ale adresa struct 348 00:15:30,060 --> 00:15:31,800 obsahující číslo 35. 349 00:15:31,800 --> 00:15:32,750 Tak to je případ dvou. 350 00:15:32,750 --> 00:15:36,190 Tak už jsem trochu kvantizace kolik práce musím udělat tady. 351 00:15:36,190 --> 00:15:39,880 >> A konečně zřejmé, prostřední případ opravdu, ve středu, když chci 352 00:15:39,880 --> 00:15:45,870 vložit něco jako, řekněme 23, která vede mezi 23 a 26, ale 353 00:15:45,870 --> 00:15:48,680 nyní se věci trochu víc podílí protože to, co 354 00:15:48,680 --> 00:15:52,800 ukazatele je třeba změnit? 355 00:15:52,800 --> 00:15:56,680 22 tak samozřejmě je třeba změnit protože nemůže odkazovat na 26 už ne. 356 00:15:56,680 --> 00:16:00,320 Že je třeba, aby odkazoval na nový uzel, který Budu se muset rozdělit na telefonním čísle 357 00:16:00,320 --> 00:16:01,770 malloc nebo jiným ekvivalentním. 358 00:16:01,770 --> 00:16:05,990 >> Ale pak jsem také potřebovat nový uzel, 23 V tomto případě, aby se její ukazatel 359 00:16:05,990 --> 00:16:07,870 ukázal na koho? 360 00:16:07,870 --> 00:16:08,560 26. 361 00:16:08,560 --> 00:16:10,380 A tam to bude pořadí úkonů zde. 362 00:16:10,380 --> 00:16:13,410 Protože když jsem to hloupě a já například od začátku roku 363 00:16:13,410 --> 00:16:16,040 seznam, a mým cílem je, vložit 23. 364 00:16:16,040 --> 00:16:18,610 A já jsem zkontrolovat, to patří Zde, v blízkosti devíti? 365 00:16:18,610 --> 00:16:18,950 Ne. 366 00:16:18,950 --> 00:16:20,670 Znamená to sem patří, vedle 17? 367 00:16:20,670 --> 00:16:20,940 Ne. 368 00:16:20,940 --> 00:16:22,530 Má to sem patří vedle 22? 369 00:16:22,530 --> 00:16:23,300 Ano. 370 00:16:23,300 --> 00:16:26,400 >> Teď, když jsem hloupý tady, a ne myslí si, až bych mohl 371 00:16:26,400 --> 00:16:28,320 přidělit můj nový uzel pro 23 let. 372 00:16:28,320 --> 00:16:32,080 Bych mohl aktualizovat ukazatel z uzel s názvem 22, směřující 373 00:16:32,080 --> 00:16:33,080 že na nový uzel. 374 00:16:33,080 --> 00:16:36,140 A pak to, co mám aktualizovat Nový uzel je ukazatel, že? 375 00:16:36,140 --> 00:16:38,120 >> STUDENT: [neslyšitelné]. 376 00:16:38,120 --> 00:16:38,385 >> SPEAKER 1: Přesně tak. 377 00:16:38,385 --> 00:16:39,710 Ukázal na 26 let. 378 00:16:39,710 --> 00:16:45,590 Ale dammit kdybych neměl již aktualizovat 22 je ukazatel ukazovat na toho chlapa, a 379 00:16:45,590 --> 00:16:48,260 teď mám sirotky, zbytek seznamu, abych tak řekl. 380 00:16:48,260 --> 00:16:52,140 Takže pořadí operací zde bude důležité. 381 00:16:52,140 --> 00:16:55,100 >> K tomu jsem mohl ukrást, řekněme, šest dobrovolníků. 382 00:16:55,100 --> 00:16:57,650 A uvidíme, jestli můžeme to udělat vizuálně namísto kódu ručiček. 383 00:16:57,650 --> 00:16:59,330 A máme nějaké krásné stres míče pro vás dnes. 384 00:16:59,330 --> 00:17:02,510 OK, jak se o jeden, dva, ve zpět - na konci tam. 385 00:17:02,510 --> 00:17:04,530 tři, čtyři, oba kluci na konci. 386 00:17:04,530 --> 00:17:05,579 A pět, šest. 387 00:17:05,579 --> 00:17:05,839 Jistě. 388 00:17:05,839 --> 00:17:06,450 Pět a šest. 389 00:17:06,450 --> 00:17:08,390 Dobře a my se na vás příště. 390 00:17:08,390 --> 00:17:09,640 Dobře, pojď nahoru. 391 00:17:09,640 --> 00:17:12,010 392 00:17:12,010 --> 00:17:14,819 >> Dobře, když už jsi tady poprvé, byste chtěli být tím, kdo nešikovně 393 00:17:14,819 --> 00:17:16,119 ve skle Google tady? 394 00:17:16,119 --> 00:17:19,075 Dobře, takže OK, sklo, videozáznam. 395 00:17:19,075 --> 00:17:22,720 396 00:17:22,720 --> 00:17:24,589 OK, máte dobré jít. 397 00:17:24,589 --> 00:17:27,950 >> Dobře, takže pokud vy můžete přijít tady jsem předem připravené 398 00:17:27,950 --> 00:17:30,110 některá čísla. 399 00:17:30,110 --> 00:17:31,240 Dobře, pojď sem. 400 00:17:31,240 --> 00:17:33,440 A proč nejdeš trochu dále tímto způsobem. 401 00:17:33,440 --> 00:17:35,520 A podívejme se, jak se jmenuješ, se skleněným Google? 402 00:17:35,520 --> 00:17:35,910 >> STUDENT: Ben. 403 00:17:35,910 --> 00:17:36,230 >> SPEAKER 1: Ben? 404 00:17:36,230 --> 00:17:38,380 OK, Bene, budete první, a to doslova. 405 00:17:38,380 --> 00:17:40,580 Takže budeme posílat do konce období. 406 00:17:40,580 --> 00:17:41,670 Dobře, a vaše jméno? 407 00:17:41,670 --> 00:17:41,990 >> STUDENT: Jason. 408 00:17:41,990 --> 00:17:44,530 >> SPEAKER 1: Jason, OK budete být číslo devět. 409 00:17:44,530 --> 00:17:46,700 Takže pokud budete chtít sledovat Ben tímto způsobem. 410 00:17:46,700 --> 00:17:47,010 >> STUDENT: Jill. 411 00:17:47,010 --> 00:17:49,630 >> SPEAKER 1: Jill, budete mít 17, která, pokud bych to udělal více 412 00:17:49,630 --> 00:17:51,260 inteligentně, musel bych začal na druhém konci. 413 00:17:51,260 --> 00:17:52,370 Můžete jít tudy. 414 00:17:52,370 --> 00:17:53,030 22. 415 00:17:53,030 --> 00:17:53,670 A vy jste? 416 00:17:53,670 --> 00:17:53,980 >> STUDENT: Mary. 417 00:17:53,980 --> 00:17:56,130 >> SPEAKER 1: Mary, budete 22. 418 00:17:56,130 --> 00:17:58,420 A vaše jméno? 419 00:17:58,420 --> 00:17:58,810 >> STUDENT: Chris. 420 00:17:58,810 --> 00:18:00,100 >> SPEAKER 1: Chris, budete 26. 421 00:18:00,100 --> 00:18:00,740 A pak konečně. 422 00:18:00,740 --> 00:18:01,400 >> STUDENT: Diana. 423 00:18:01,400 --> 00:18:02,670 >> SPEAKER 1: Diana, budete 34. 424 00:18:02,670 --> 00:18:03,920 Takže si pojď sem. 425 00:18:03,920 --> 00:18:06,360 >> Dobře, takže perfektní řazeny objednat již. 426 00:18:06,360 --> 00:18:09,600 A pojďme dál, a to takže můžeme opravdu - 427 00:18:09,600 --> 00:18:11,720 Ben jsi jen trochu hledat ven nikde tam. 428 00:18:11,720 --> 00:18:15,670 OK, takže pojďme dál, a líčí to použití zbraně, stejně jako já, přesně, 429 00:18:15,670 --> 00:18:16,250 co se děje. 430 00:18:16,250 --> 00:18:19,540 Takže jděte do toho a dát sami si noha nebo dva mezi sebou. 431 00:18:19,540 --> 00:18:22,900 A jděte do toho a přitom s jednou rukou na ten, kdo byste měli směřovat na 432 00:18:22,900 --> 00:18:23,470 na základě tohoto. 433 00:18:23,470 --> 00:18:25,890 A pokud jste null jen bod přímo na podlahu. 434 00:18:25,890 --> 00:18:27,690 OK, tak dobře. 435 00:18:27,690 --> 00:18:32,290 >> Takže teď máme propojený seznam, a dovolte mi, abych navrhnout, že budu hrát roli 436 00:18:32,290 --> 00:18:35,110 PTR, tak jsem se neobtěžoval provádění tohoto okolí. 437 00:18:35,110 --> 00:18:37,830 A pak - někdo hloupý konvence - můžete volat to, co chcete - 438 00:18:37,830 --> 00:18:39,800 předchůdce ukazatel, pred ukazatel - 439 00:18:39,800 --> 00:18:43,930 je to jen přezdívka jsme dali v náš ukázkový kód k mé levé ruce. 440 00:18:43,930 --> 00:18:47,240 Na druhé straně, která bude udržovat sledovat, kdo je kdo v 441 00:18:47,240 --> 00:18:48,400 následující scénáře. 442 00:18:48,400 --> 00:18:52,390 >> Takže předpokládám, nejprve chci utrhnout pryč , že první příklad vkládání, řekněme 443 00:18:52,390 --> 00:18:54,330 20, do seznamu. 444 00:18:54,330 --> 00:18:57,160 Takže budu potřebovat někoho, kdo by ztělesňují číslo 20 pro nás. 445 00:18:57,160 --> 00:18:58,950 Tak jsem třeba někoho malloc z publika. 446 00:18:58,950 --> 00:18:59,380 Pojď nahoru. 447 00:18:59,380 --> 00:19:00,340 Jak se jmenujete? 448 00:19:00,340 --> 00:19:01,300 >> STUDENT: Brian. 449 00:19:01,300 --> 00:19:05,270 >> SPEAKER 1: Brian, v pořádku, takže musí být uzel obsahující 20. 450 00:19:05,270 --> 00:19:06,810 Dobře, pojď sem. 451 00:19:06,810 --> 00:19:10,025 A samozřejmě, pokud Brian se patří? 452 00:19:10,025 --> 00:19:12,190 Tak, ve středu - ve skutečnosti, počkej. 453 00:19:12,190 --> 00:19:13,420 Děláme to mimo pořadí. 454 00:19:13,420 --> 00:19:17,170 Děláme to mnohem těžší než je třeba, aby se na prvním místě. 455 00:19:17,170 --> 00:19:21,210 OK, jdeme na volný Brian a realloc Brian jak pět. 456 00:19:21,210 --> 00:19:23,680 >> OK, tak teď chceme vložit Brian jak pět. 457 00:19:23,680 --> 00:19:25,960 Tak pojď sem vedle Ben na chvíli. 458 00:19:25,960 --> 00:19:28,250 A můžete říct, pravděpodobně kde tento příběh bude. 459 00:19:28,250 --> 00:19:30,500 Ale pojďme pečlivě promyslet, pořadí úkonů. 460 00:19:30,500 --> 00:19:32,880 A je to právě tato vizuální že se to seřadí 461 00:19:32,880 --> 00:19:34,080 s tímto ukázkový kód. 462 00:19:34,080 --> 00:19:40,120 Tak tady jsem PTR ukázal nejprve není na Bena, samo o sobě, ale bez ohledu na 463 00:19:40,120 --> 00:19:43,245 cení, že obsahuje, což je v tomto případě je - jak se jmenuje? 464 00:19:43,245 --> 00:19:43,670 >> STUDENT: Jason. 465 00:19:43,670 --> 00:19:47,350 >> SPEAKER 1: Jason, tak jak Ben a já jsme ukázal na Jasona v tomto okamžiku. 466 00:19:47,350 --> 00:19:49,700 Takže teď musím zjistit, kde se Brian patří? 467 00:19:49,700 --> 00:19:53,500 Takže jediné, co mám přístup k Právě teď je jeho n datová položka. 468 00:19:53,500 --> 00:19:58,280 Takže budu kontrolovat, je Brian méně než Jasona? 469 00:19:58,280 --> 00:19:59,770 Odpověď je pravda. 470 00:19:59,770 --> 00:20:03,680 >> Tak co teď musí stát, ve správném pořadí? 471 00:20:03,680 --> 00:20:07,120 Musím aktualizovat, kolik ukazatelů celkem v tomto příběhu? 472 00:20:07,120 --> 00:20:10,720 Kde je moje ruka stále ukazuje na Jason a vaše ruce - chcete-li 473 00:20:10,720 --> 00:20:12,930 dát ruku jako, tak nějak jsem nevím, otazník. 474 00:20:12,930 --> 00:20:14,070 OK, dobře. 475 00:20:14,070 --> 00:20:15,670 >> Dobře, takže máte několik kandidátů. 476 00:20:15,670 --> 00:20:20,500 Buď Ben nebo já nebo Brian nebo Jason nebo všichni ostatní, které 477 00:20:20,500 --> 00:20:21,370 ukazatele je třeba změnit? 478 00:20:21,370 --> 00:20:23,260 Kolik celkem? 479 00:20:23,260 --> 00:20:24,080 >> OK, tak dva. 480 00:20:24,080 --> 00:20:27,090 Můj ukazatel nezáleží už protože jsem jen dočasné. 481 00:20:27,090 --> 00:20:31,370 Takže je to tihle dva, pravděpodobně, jak Ben a Brian. 482 00:20:31,370 --> 00:20:34,410 Takže mi dovolte navrhnout, abychom aktualizace Ben, protože je to poprvé. 483 00:20:34,410 --> 00:20:36,350 První prvek tohoto seznamu se nyní bude Brian. 484 00:20:36,350 --> 00:20:38,070 Takže Ben bod na Briana. 485 00:20:38,070 --> 00:20:39,320 OK, co teď? 486 00:20:39,320 --> 00:20:41,950 487 00:20:41,950 --> 00:20:43,460 >> Kdo dostane ukázal na koho? 488 00:20:43,460 --> 00:20:44,710 >> STUDENT: [neslyšitelné]. 489 00:20:44,710 --> 00:20:46,180 >> SPEAKER 1: OK, takže Brian má ukázat na Jasona. 490 00:20:46,180 --> 00:20:48,360 Ale už jsem ztratil přehled o tomto ukazatel? 491 00:20:48,360 --> 00:20:49,980 Vím, kde je Jason? 492 00:20:49,980 --> 00:20:50,790 >> STUDENT: [neslyšitelné]. 493 00:20:50,790 --> 00:20:52,620 >> SPEAKER 1: já, protože jsem dočasný ukazatel. 494 00:20:52,620 --> 00:20:55,110 A pravděpodobně jsem se nezměnil ukázat na nový uzel. 495 00:20:55,110 --> 00:20:58,300 Takže můžeme jednoduše Brian bod na toho, kdo mi ukázal na. 496 00:20:58,300 --> 00:20:59,000 A jsme hotovi. 497 00:20:59,000 --> 00:21:01,890 Tak jeden případ, ve vložení na začátku seznamu. 498 00:21:01,890 --> 00:21:02,950 Tam byly dva hlavní kroky. 499 00:21:02,950 --> 00:21:06,750 Za prvé, musíme aktualizovat Bena, a pak musíme rovněž aktualizovat Briana. 500 00:21:06,750 --> 00:21:09,230 A pak nemám obtěžovat traipsing přes zbytek 501 00:21:09,230 --> 00:21:12,680 seznam, protože jsme již našli jeho umístění, protože patřil k 502 00:21:12,680 --> 00:21:14,080 vlevo od prvního prvku. 503 00:21:14,080 --> 00:21:15,400 >> Dobře, takže docela jednoduché. 504 00:21:15,400 --> 00:21:18,110 Ve skutečnosti, pocit, že jsme skoro takže to příliš složité. 505 00:21:18,110 --> 00:21:20,240 Takže pojďme se utrhnout z konce seznamu, a zjistit, kde 506 00:21:20,240 --> 00:21:21,380 složitost začíná. 507 00:21:21,380 --> 00:21:24,560 Takže když teď jsem alloc z publika. 508 00:21:24,560 --> 00:21:25,540 Každý, kdo chce hrát 55? 509 00:21:25,540 --> 00:21:26,700 Tak jo, viděl jsem svou ruku jako první. 510 00:21:26,700 --> 00:21:29,620 Pojď nahoru. 511 00:21:29,620 --> 00:21:30,030 Jo. 512 00:21:30,030 --> 00:21:31,177 Jak se jmenujete? 513 00:21:31,177 --> 00:21:32,310 >> STUDENT: [neslyšitelné]. 514 00:21:32,310 --> 00:21:33,240 >> SPEAKER 1: Habata. 515 00:21:33,240 --> 00:21:33,890 OK, pojď nahoru. 516 00:21:33,890 --> 00:21:35,730 Budete mít číslo 55. 517 00:21:35,730 --> 00:21:37,820 Takže vy, samozřejmě, patří na konci seznamu. 518 00:21:37,820 --> 00:21:41,850 Takže pojďme přehrát simulaci se mnou bytí PTR jen na chvíli. 519 00:21:41,850 --> 00:21:44,050 Tak jsem poprvé bude ukazovat na bez ohledu na to Ben ukázal na. 520 00:21:44,050 --> 00:21:45,900 Oba jsme ukazuje nyní na Briana. 521 00:21:45,900 --> 00:21:48,420 Takže 55 je ne méně než pět. 522 00:21:48,420 --> 00:21:52,510 Takže budu aktualizovat tím, že jsem ukázal na další ukazatel Brianovi, který 523 00:21:52,510 --> 00:21:54,450 Nyní je samozřejmě Jasona. 524 00:21:54,450 --> 00:21:57,310 55 je menší než devět, takže Chystám se aktualizovat PTR. 525 00:21:57,310 --> 00:21:58,890 Chystám se aktualizovat PTR. 526 00:21:58,890 --> 00:22:02,290 Chystám se aktualizovat PTR Budu aktualizovat PTR. 527 00:22:02,290 --> 00:22:05,060 A já jdu - hmm, co je Vaše jméno znovu? 528 00:22:05,060 --> 00:22:05,560 >> STUDENT: Diana. 529 00:22:05,560 --> 00:22:09,190 >> SPEAKER 1: Diana ukazuje, samozřejmě, při nulovém s levou rukou. 530 00:22:09,190 --> 00:22:13,030 Takže tam, kde se skutečně Habata patří jasně? 531 00:22:13,030 --> 00:22:15,050 Na levé straně, zde. 532 00:22:15,050 --> 00:22:19,460 Tak jak mám vědět, že ji zde Myslím, že jsem to podělal. 533 00:22:19,460 --> 00:22:22,420 Protože to, co je umění PTR tento okamžik v čase? 534 00:22:22,420 --> 00:22:23,240 Null. 535 00:22:23,240 --> 00:22:25,580 Takže i když vizuálně, můžeme samozřejmě vidět všechny z nich 536 00:22:25,580 --> 00:22:26,610 kluci tady na jevišti. 537 00:22:26,610 --> 00:22:29,680 Já jsem to sledoval z předchozí osoba v seznamu. 538 00:22:29,680 --> 00:22:33,210 Nemám prst ukazující ven, V tomto případě, uzel číslo 34. 539 00:22:33,210 --> 00:22:34,760 >> Takže pojďme skutečně začít to znovu. 540 00:22:34,760 --> 00:22:37,560 Takže teď vlastně nepotřebujete Druhý lokální proměnná. 541 00:22:37,560 --> 00:22:40,980 A to je to, co uvidíte v Skutečný vzorek C kód, kde, jak jsem jít, 542 00:22:40,980 --> 00:22:45,860 když jsem aktualizovat pravou ruku k bodu Jason, přičemž je nutno Brian zezadu, jsem 543 00:22:45,860 --> 00:22:51,440 lepší začít používat levou ruku k aktualizovat, kde jsem byl, takže, jak jsem jít 544 00:22:51,440 --> 00:22:52,700 pomocí tohoto seznamu - 545 00:22:52,700 --> 00:22:55,040 více rozpačitě, než jsem chtěl teď tady vizuálně - 546 00:22:55,040 --> 00:22:56,740 Chystám se dostat do konec seznamu. 547 00:22:56,740 --> 00:23:00,020 >> Tato ruka je stále nulový, což je docela zbytečné, pouze ukazují 548 00:23:00,020 --> 00:23:02,980 Jsem jednoznačně na konci seznamu, ale teď aspoň to mám 549 00:23:02,980 --> 00:23:08,270 předchůdce ukazovatel tady, tak Co teď předává a jaké ukazatele musí 550 00:23:08,270 --> 00:23:10,150 aktualizovat? 551 00:23:10,150 --> 00:23:13,214 Čí ruka chceš překonfigurovat první? 552 00:23:13,214 --> 00:23:15,190 >> STUDENT: [neslyšitelné]. 553 00:23:15,190 --> 00:23:16,220 >> SPEAKER 1: OK, tak Dianin. 554 00:23:16,220 --> 00:23:21,110 Kam chcete nasměrovat Dianin levý ukazatel na? 555 00:23:21,110 --> 00:23:23,620 Na 55, pravděpodobně, aby jsme tam vložit. 556 00:23:23,620 --> 00:23:25,560 A kde by 55 ukazatel jít? 557 00:23:25,560 --> 00:23:27,000 Dolů, což null. 558 00:23:27,000 --> 00:23:28,890 A moje ruce, v tomto bodě, ne jedno, protože oni byli jen 559 00:23:28,890 --> 00:23:30,070 dočasné proměnné. 560 00:23:30,070 --> 00:23:31,030 Takže teď jsme hotovi. 561 00:23:31,030 --> 00:23:34,650 >> Takže další složitosti tam - a že to není tak těžké zavést, 562 00:23:34,650 --> 00:23:38,660 ale potřebujeme sekundární proměnnou, aby se jistý, že předtím, než jsem se pohnout právo 563 00:23:38,660 --> 00:23:42,140 ruka, jsem aktualizovat hodnotu mé levici ruka, pred ukazatel v tomto případě, tak 564 00:23:42,140 --> 00:23:45,860 že mám koncové ukazatele sledovat, kde jsem byl. 565 00:23:45,860 --> 00:23:49,360 Nyní, jak stranou, pokud si myslíte tohle přes to pocit, že je to 566 00:23:49,360 --> 00:23:51,490 Trochu nepříjemné mít na sledování tohoto levé ruky. 567 00:23:51,490 --> 00:23:54,015 >> Co by jiné řešení tohoto problému byly? 568 00:23:54,015 --> 00:23:56,500 Pokud jste se dostali k redesign data Struktura mluvíme 569 00:23:56,500 --> 00:23:59,630 až teď? 570 00:23:59,630 --> 00:24:02,690 Pokud je to jen trochu cítí trochu nepříjemné mít ráda, dva ukazatele 571 00:24:02,690 --> 00:24:08,430 prochází seznam, kdo by mohl jinak se, v ideálním světě, udržovány 572 00:24:08,430 --> 00:24:10,160 Informace, které potřebujete? 573 00:24:10,160 --> 00:24:11,360 Jo? 574 00:24:11,360 --> 00:24:12,610 >> STUDENT: [neslyšitelné]. 575 00:24:12,610 --> 00:24:15,160 576 00:24:15,160 --> 00:24:16,150 >> SPEAKER 1: Přesně tak. 577 00:24:16,150 --> 00:24:19,130 Pravá takže je to vlastně zajímavý zárodek nápadu. 578 00:24:19,130 --> 00:24:22,470 A tato myšlenka na předchozí ukazatel, ukazuje na předchozí prvek. 579 00:24:22,470 --> 00:24:25,580 Co když jsem ztělesněný, že v seznamu sám? 580 00:24:25,580 --> 00:24:27,810 A to bude těžké si představit, to bez všech papíru 581 00:24:27,810 --> 00:24:28,830 pádu na zem. 582 00:24:28,830 --> 00:24:31,860 Ale předpokládejme, že tito lidé používají jak jejich rukou mít předchozí 583 00:24:31,860 --> 00:24:35,950 ukazatel, a další ukazatel, čímž realizuje to, co budeme říkat dvakrát 584 00:24:35,950 --> 00:24:36,830 spojový seznam. 585 00:24:36,830 --> 00:24:41,090 To by mi dovolte, abych nějak vzad mnohem snadněji, aniž by mě, 586 00:24:41,090 --> 00:24:43,800 programátor, musela držet sledovat ručně - 587 00:24:43,800 --> 00:24:44,980 skutečně ručně - 588 00:24:44,980 --> 00:24:47,280 , kde jsem byl předtím v seznamu. 589 00:24:47,280 --> 00:24:48,110 Takže nebudeme dělat. 590 00:24:48,110 --> 00:24:50,950 Budeme držet to jednoduchý, protože to je přijde za cenu, což je dvakrát 591 00:24:50,950 --> 00:24:53,450 mnoho prostoru pro ukazatele, chcete-li druhou. 592 00:24:53,450 --> 00:24:55,760 Ale to je opravdu společný datové struktury známé jako 593 00:24:55,760 --> 00:24:57,410 dvojnásobně spojový seznam. 594 00:24:57,410 --> 00:25:01,310 >> Pojďme udělat poslední příklad zde a dal tihle kluci z jejich utrpení. 595 00:25:01,310 --> 00:25:03,270 Tak malloc 20. 596 00:25:03,270 --> 00:25:05,320 Pojď nahoru od uličky tam. 597 00:25:05,320 --> 00:25:06,280 Dobře, Jak se jmenujete? 598 00:25:06,280 --> 00:25:07,440 >> STUDENT: [neslyšitelné]. 599 00:25:07,440 --> 00:25:07,855 >> SPEAKER 1: Je nám líto? 600 00:25:07,855 --> 00:25:08,480 >> STUDENT: [neslyšitelné]. 601 00:25:08,480 --> 00:25:09,410 >> SPEAKER 1: Demeron? 602 00:25:09,410 --> 00:25:10,230 OK pojď nahoru. 603 00:25:10,230 --> 00:25:11,910 Ty musí být 20. 604 00:25:11,910 --> 00:25:14,720 Ty samozřejmě budou Patří mezi 17 a 22. 605 00:25:14,720 --> 00:25:16,150 Takže dovolte mi učit mé lekci. 606 00:25:16,150 --> 00:25:18,150 Chystám se začít ukazatel ukázal na Briana. 607 00:25:18,150 --> 00:25:21,190 A já budu mít levou ruku aktualizovat pouze k Brianovi, jak jsem se přesunout na 608 00:25:21,190 --> 00:25:23,600 Jason, kontrola dělá 20 méně než devět? 609 00:25:23,600 --> 00:25:24,060 Ne. 610 00:25:24,060 --> 00:25:25,430 Je o 20 méně než 17? 611 00:25:25,430 --> 00:25:25,880 Ne. 612 00:25:25,880 --> 00:25:27,450 Je o 20 méně než 22? 613 00:25:27,450 --> 00:25:28,440 Ano. 614 00:25:28,440 --> 00:25:34,070 Takže to, co ukazovátka nebo ruce je třeba změnit kde to ukazuje teď? 615 00:25:34,070 --> 00:25:37,070 >> Takže, co můžeme udělat 17 ukazuje na 20 let. 616 00:25:37,070 --> 00:25:37,860 Tak to je v pořádku. 617 00:25:37,860 --> 00:25:40,080 Kde chceme upozornit ukazatel myši teď? 618 00:25:40,080 --> 00:25:41,330 Ve 22. 619 00:25:41,330 --> 00:25:45,410 A my víme, kde 22 je opět díky k mému dočasné ukazatele. 620 00:25:45,410 --> 00:25:46,760 Tak to je v pořádku tam. 621 00:25:46,760 --> 00:25:49,440 Takže kvůli této dočasné skladování Nechal jsem sledovat, kde se všichni. 622 00:25:49,440 --> 00:25:55,055 A teď můžete jít do vizuálně, kde patříte, a teď potřebujeme 1, 2, 3, 623 00:25:55,055 --> 00:25:58,410 4, 5, 6, 7, 8, 9 stres míče, a potlesk pro 624 00:25:58,410 --> 00:25:59,770 tihle kluci, kdybychom mohli. 625 00:25:59,770 --> 00:26:00,410 Dobrá práce. 626 00:26:00,410 --> 00:26:05,320 >> [APPLAUSE] 627 00:26:05,320 --> 00:26:06,330 >> SPEAKER 1: Dobře. 628 00:26:06,330 --> 00:26:09,860 A můžete držet kusy papíru jako památku. 629 00:26:09,860 --> 00:26:15,930 >> Dobře, takže, věřte mi, je to hodně jednodušší projít, aby se 630 00:26:15,930 --> 00:26:17,680 lidé, než je tomu u skutečného kódu. 631 00:26:17,680 --> 00:26:22,690 Ale to, co najdete za chvíli teď, je to stejné - ach, děkuji. 632 00:26:22,690 --> 00:26:23,630 Děkuji - 633 00:26:23,630 --> 00:26:29,360 je, že zjistíte, že stejné údaje struktura, spojový seznam, může ve skutečnosti 634 00:26:29,360 --> 00:26:33,200 být použity jako stavební blok k ještě sofistikované datové struktury. 635 00:26:33,200 --> 00:26:37,620 >> A uvědomit si taky téma zde je, že jsme absolutně představil více 636 00:26:37,620 --> 00:26:40,060 složitost do provádění tohoto algoritmu. 637 00:26:40,060 --> 00:26:43,940 Vložení, a když jsme šli přes to, výmaz a vyhledávání, je trochu 638 00:26:43,940 --> 00:26:46,660 komplikovanější, než se byl s řadou. 639 00:26:46,660 --> 00:26:48,040 Ale získat nějaké dynamiku. 640 00:26:48,040 --> 00:26:50,180 Dostáváme adaptivní strukturu dat. 641 00:26:50,180 --> 00:26:54,010 >> Ale opět platíme cenu, že některé další složitost, a to jak v 642 00:26:54,010 --> 00:26:54,910 provádění. 643 00:26:54,910 --> 00:26:56,750 A my jsme se vzdali náhodný přístup. 644 00:26:56,750 --> 00:27:00,450 A abych byl upřímný, že to není nějaký pěkný čištění snímek můžu dát, že 645 00:27:00,450 --> 00:27:03,120 říká, že je zde důvod, proč spojový seznam je lepší než pole. 646 00:27:03,120 --> 00:27:04,100 A nechat to tak. 647 00:27:04,100 --> 00:27:07,520 Protože téma znovu objevuje nyní, i více v nadcházejících týdnech, je 648 00:27:07,520 --> 00:27:10,200 že to nemusí být nutně správná odpověď. 649 00:27:10,200 --> 00:27:13,830 >> To je důvod, proč máme samostatnou osu designu pro základní problémové okruhy. 650 00:27:13,830 --> 00:27:17,700 Bude to velmi kontextová zda chcete tato data použít 651 00:27:17,700 --> 00:27:21,750 struktura nebo že jeden, a to bude závisí na to, co je pro vás z hlediska 652 00:27:21,750 --> 00:27:24,620 zdrojů a složitosti. 653 00:27:24,620 --> 00:27:28,830 >> Ale dovolte mi navrhnout, aby byla ideální údajů struktura, Svatý grál, bude 654 00:27:28,830 --> 00:27:32,200 něco, co je konstantní čas bez ohledu na to, kolik věcí je 655 00:27:32,200 --> 00:27:36,940 uvnitř, nebylo by úžasné, kdyby datová struktura se vrátil v odpovědi 656 00:27:36,940 --> 00:27:37,920 konstantní čas. 657 00:27:37,920 --> 00:27:38,330 Ano. 658 00:27:38,330 --> 00:27:40,110 Toto slovo je v obrovské slovníku. 659 00:27:40,110 --> 00:27:41,550 Nebo ne, to slovo není. 660 00:27:41,550 --> 00:27:43,270 Nebo nějaký takový problém. 661 00:27:43,270 --> 00:27:46,360 No uvidíme, jestli můžeme alespoň ne krok směrem k tomuto. 662 00:27:46,360 --> 00:27:50,190 >> Dovolte mi navrhnout novou datovou strukturu, která mohou být použity pro různé věci, 663 00:27:50,190 --> 00:27:52,260 v tomto případě nazývá hash tabulky. 664 00:27:52,260 --> 00:27:55,590 A tak jsme vlastně zpět pohledem na poli, v tomto případě, a 665 00:27:55,590 --> 00:28:00,550 trochu uměle, já jsem to vypracovány hash tabulky jako pole s druhem 666 00:28:00,550 --> 00:28:02,810 dvourozměrné pole - 667 00:28:02,810 --> 00:28:05,410 nebo spíše to zde zobrazen jako dva rozměrné pole - ale je to jen 668 00:28:05,410 --> 00:28:10,770 pole o velikosti 26, tak, že pokud se zavolejte pole, stolní držák 669 00:28:10,770 --> 00:28:12,440 nula je obdélník v horní části. 670 00:28:12,440 --> 00:28:15,090 Stolní držák 25 je obdélník v dolní části. 671 00:28:15,090 --> 00:28:18,620 A to je, jak bych mohl nakreslit dat struktura, ve které chci uložit 672 00:28:18,620 --> 00:28:19,790 Jména lidí. 673 00:28:19,790 --> 00:28:24,370 >> Tak například, a nebudu kreslit Celá věc tady na stropě, když jsem 674 00:28:24,370 --> 00:28:29,160 měl toto pole, které jsem teď bude volání hash tabulky, a to je opět 675 00:28:29,160 --> 00:28:31,360 umístění nula. 676 00:28:31,360 --> 00:28:34,840 Tohle je místo jeden, a tak dále. 677 00:28:34,840 --> 00:28:37,880 Tvrdím, že chci použít tato data struktura, v zájmu diskuse 678 00:28:37,880 --> 00:28:42,600 Uložení jmen lidí, Alice a Bob a Charlie a další podobné názvy. 679 00:28:42,600 --> 00:28:46,110 Takže myslíte, že o tom dnes stejně jako začátky , řekněme, ve slovníku 680 00:28:46,110 --> 00:28:47,520 se spoustou slov. 681 00:28:47,520 --> 00:28:49,435 Oni stalo, že se jména v našem příkladu zde. 682 00:28:49,435 --> 00:28:52,560 A to je příliš germane, snad, aby provádí kontrolu pravopisu, jako my 683 00:28:52,560 --> 00:28:54,400 Mohou to být problém nastavit šest. 684 00:28:54,400 --> 00:28:59,300 >> Takže pokud máme řadu celkové velikosti 26 tak, že je to místo 25. 685 00:28:59,300 --> 00:29:03,390 na dně, a tvrdím, že je Alice první slovo ve slovníku 686 00:29:03,390 --> 00:29:07,260 Názvy, které chci vložit do paměti RAM, do tohoto datové struktury, kde jsou 687 00:29:07,260 --> 00:29:12,480 instinkt říká, že Alice je Název by měl jít v tomto poli? 688 00:29:12,480 --> 00:29:13,510 >> Máme 26 možností. 689 00:29:13,510 --> 00:29:14,990 Pokud chceme ji? 690 00:29:14,990 --> 00:29:16,200 Chceme ji v závorce nula, ne? 691 00:29:16,200 --> 00:29:18,280 A pro Alici, řekněme, že nula. 692 00:29:18,280 --> 00:29:20,110 A B bude jeden, a C budou dva. 693 00:29:20,110 --> 00:29:22,600 Takže budeme psát Alicin jméno tady. 694 00:29:22,600 --> 00:29:24,890 Pokud se poté vložte Bob, jeho název půjde zde. 695 00:29:24,890 --> 00:29:27,280 Charlie naleznete zde. 696 00:29:27,280 --> 00:29:30,500 A tak dále dolů Tato datová struktura. 697 00:29:30,500 --> 00:29:32,090 >> Je to nádherná struktura dat. 698 00:29:32,090 --> 00:29:32,730 Proč? 699 00:29:32,730 --> 00:29:37,460 No to je doba chodu vložením lidského jméno do tohoto 700 00:29:37,460 --> 00:29:39,850 struktura dat právě teď? 701 00:29:39,850 --> 00:29:43,702 Vzhledem k tomu, že tato tabulka je implementována, opravdu jako pole. 702 00:29:43,702 --> 00:29:44,940 No, je to konstantní čas. 703 00:29:44,940 --> 00:29:45,800 To je cílem jednoho. 704 00:29:45,800 --> 00:29:46,360 Proč? 705 00:29:46,360 --> 00:29:48,630 >> Tak, jak si zjistit, kde Alice patří? 706 00:29:48,630 --> 00:29:51,000 Když se podíváte na které písmeno jejího jména? 707 00:29:51,000 --> 00:29:51,490 První. 708 00:29:51,490 --> 00:29:54,350 A můžete se tam dostat, když je to řetězec, jen o pohledu na provázku 709 00:29:54,350 --> 00:29:55,200 držák nula. 710 00:29:55,200 --> 00:29:57,110 Takže nultý znak řetězce. 711 00:29:57,110 --> 00:29:57,610 To je jednoduché. 712 00:29:57,610 --> 00:30:00,350 To jsme udělali v crypto přiřazení týdny. 713 00:30:00,350 --> 00:30:05,310 A pak ještě jednou víte, že Alice písmeno velké, můžeme odečíst 714 00:30:05,310 --> 00:30:08,160 off 65 nebo kapitálu je sám, že nám dává nulu. 715 00:30:08,160 --> 00:30:10,940 Takže nyní víme, že Alice patří v místě nulové. 716 00:30:10,940 --> 00:30:14,240 >> A vzhledem k tomu ukazatel k těmto údajům struktura, nějakého druhu, jak dlouho trvá 717 00:30:14,240 --> 00:30:18,840 to se mi najít místo nula v poli? 718 00:30:18,840 --> 00:30:22,080 Jen jeden krok, že je to konstantní čas protože s libovolným přístupem se 719 00:30:22,080 --> 00:30:23,780 Navrhovaný byl charakterizován pole. 720 00:30:23,780 --> 00:30:28,570 Takže ve zkratce, zjišťuje, co index Alice je název, který je v 721 00:30:28,570 --> 00:30:32,610 V tomto případě je, nebo ať to prostě řešit že k nule, kde B je jedna a C je 722 00:30:32,610 --> 00:30:34,900 dva, zjišťuje, že z je konstantní čas. 723 00:30:34,900 --> 00:30:38,510 Musím se podívat na její první dopis, přijít na to, kde je nula 724 00:30:38,510 --> 00:30:40,460 Pole je také konstantní čas. 725 00:30:40,460 --> 00:30:42,140 Takže technicky to jako dva kroky nyní. 726 00:30:42,140 --> 00:30:43,330 Ale to je stále konstantní. 727 00:30:43,330 --> 00:30:46,880 Takže říkáme, že velký O jedné, takže jsme vložena Alici do této tabulky v 728 00:30:46,880 --> 00:30:48,440 konstantní čas. 729 00:30:48,440 --> 00:30:50,960 >> Ale samozřejmě, já jsem byl naivní, ne? 730 00:30:50,960 --> 00:30:53,240 Co když tam Aaron ve třídě? 731 00:30:53,240 --> 00:30:53,990 Nebo Alicia? 732 00:30:53,990 --> 00:30:57,230 Nebo jakékoliv jiné názvy začínající A. Kam jdeme dát 733 00:30:57,230 --> 00:31:00,800 že člověk, ne? 734 00:31:00,800 --> 00:31:03,420 Myslím, že právě teď je tu jen tři Lidé na stole, takže možná jsme 735 00:31:03,420 --> 00:31:07,490 měli dát Aaron v místě nula jedna dva tři. 736 00:31:07,490 --> 00:31:09,480 >> Jasně, mohl jsem tady. 737 00:31:09,480 --> 00:31:13,350 Ale pak, když se snažíme vložit do Davida tento seznam, kde se David jít? 738 00:31:13,350 --> 00:31:15,170 Nyní náš systém spustí vypínací dolů, ne? 739 00:31:15,170 --> 00:31:19,210 Protože teď David skončí tady pokud Aaron je ve skutečnosti zde. 740 00:31:19,210 --> 00:31:23,060 A tak se celá tahle představa, že čistá datová struktura, která nám dává 741 00:31:23,060 --> 00:31:28,010 konstantním čase vložky již není konstantní čas, protože musím 742 00:31:28,010 --> 00:31:31,240 zjistit, oh, sakra, někdo to již v místě Alice. 743 00:31:31,240 --> 00:31:35,320 >> Dovolte mi, abych prozkoumat zbytek těchto údajů struktura, hledat místo dát 744 00:31:35,320 --> 00:31:37,130 někdo jako jméno Aaron. 745 00:31:37,130 --> 00:31:39,390 A tak to taky začíná aby se lineární čas. 746 00:31:39,390 --> 00:31:42,710 Navíc, pokud se chcete vyhledat Aaron v této datové struktuře, a 747 00:31:42,710 --> 00:31:45,430 zkontrolovat, a Áronova jméno tu není. 748 00:31:45,430 --> 00:31:47,960 V ideálním případě by jste právě řekl Aronovi není v datové struktuře. 749 00:31:47,960 --> 00:31:51,530 Ale pokud si začnete dělat prostor pro Aaron tam, kde by byly D 750 00:31:51,530 --> 00:31:55,600 nebo E, ty, v nejhorším případě, je nutné zkontrolovat Celá struktura dat, ve 751 00:31:55,600 --> 00:31:59,480 takovém případě přejde do něčeho lineární ve velikosti tabulky. 752 00:31:59,480 --> 00:32:00,920 >> Takže v pořádku, já to opravit. 753 00:32:00,920 --> 00:32:04,200 Problém je, že jsem měl 26 prvků v tomto poli. 754 00:32:04,200 --> 00:32:05,000 Dovolte mi, abych ji změnit. 755 00:32:05,000 --> 00:32:06,010 Jejda. 756 00:32:06,010 --> 00:32:10,600 Dovolte mi, abych ho změnit tak, že místo bytí velikost 26 celkem, všimněte si na dno 757 00:32:10,600 --> 00:32:12,720 index se změní na n mínus jedna. 758 00:32:12,720 --> 00:32:16,610 Pokud 26 je zjevně příliš malá pro člověka " jména, protože tam jsou tisíce 759 00:32:16,610 --> 00:32:20,830 jména na světě, prostě dělat na 100 nebo 1000 nebo 10000. 760 00:32:20,830 --> 00:32:22,960 Řekněme přidělit mnohem více prostoru. 761 00:32:22,960 --> 00:32:27,230 >> Dobře, že nemusí nutně snížit pravděpodobnost, že nebudeme mít dva 762 00:32:27,230 --> 00:32:31,510 lidé s názvy začínající a tak jsi to zkusit dát 763 00:32:31,510 --> 00:32:33,120 jména na umístění nulu stále. 764 00:32:33,120 --> 00:32:36,850 Pořád bude srazí, což znamená, že stále potřebujeme řešení, aby 765 00:32:36,850 --> 00:32:41,020 Alice a Árona a Alicia a další Jména začínající A jinde. 766 00:32:41,020 --> 00:32:43,460 Ale jak velký problém to je? 767 00:32:43,460 --> 00:32:46,870 Co je to pravděpodobnost, že si mají kolize v datovém 768 00:32:46,870 --> 00:32:48,240 Struktura takhle? 769 00:32:48,240 --> 00:32:52,570 >> No, dovolte mi, abych - vrátíme se na tuto otázku zde. 770 00:32:52,570 --> 00:32:55,530 A podívejte se na to, jak bychom mohli řešit jako první. 771 00:32:55,530 --> 00:32:58,480 Dovolte mi, abych vytáhnout tento návrh zde. 772 00:32:58,480 --> 00:33:02,020 To, co jsme právě popsal, je algoritmus, heuristický tzv. lineární 773 00:33:02,020 --> 00:33:05,030 snímání, kdy, pokud jste se pokusili vložit něco, co zde v těchto údajů 774 00:33:05,030 --> 00:33:08,920 struktura, která se nazývá hash tabulky, a neexistuje žádný prostor tam, 775 00:33:08,920 --> 00:33:12,000 skutečně zkoumat strukturu dat kontrola, je to k dispozici? 776 00:33:12,000 --> 00:33:13,430 Je to k dispozici, je to k dispozici? 777 00:33:13,430 --> 00:33:13,980 Je to k dispozici? 778 00:33:13,980 --> 00:33:17,550 A když konečně je vložíte jméno, které jste původně zamýšlel 779 00:33:17,550 --> 00:33:19,370 jinde v tomto místě. 780 00:33:19,370 --> 00:33:23,360 Ale v nejhorším případě pouze bod může být velmi spodní údajů 781 00:33:23,360 --> 00:33:25,090 struktura, velmi konec pole. 782 00:33:25,090 --> 00:33:30,130 >> Takže lineární sondy, v nejhorším případě, přejde do lineární algoritmus, kde 783 00:33:30,130 --> 00:33:34,500 Aaron, když se stane být vložen poslední v této datové struktuře, mohl by 784 00:33:34,500 --> 00:33:39,540 kolidovat s tímto prvním místě, ale pak konec smůla v samém závěru. 785 00:33:39,540 --> 00:33:43,940 Takže to není konstantní Doba svatý grál pro nás. 786 00:33:43,940 --> 00:33:47,650 Tento přístup, vkládání prvků do datová struktura nazývá hash 787 00:33:47,650 --> 00:33:52,050 tabulka se nezdá být konstantní čas alespoň ne v obecném případě. 788 00:33:52,050 --> 00:33:54,000 To může přejít do něčeho lineární. 789 00:33:54,000 --> 00:33:56,970 >> Takže co kdybychom vyřešit kolize poněkud jinak? 790 00:33:56,970 --> 00:34:00,740 Tak tady je to složitější přiblížit to, co je ještě 791 00:34:00,740 --> 00:34:02,800 tzv. hash tabulky. 792 00:34:02,800 --> 00:34:05,890 A hash, jako stranou, co Mám na mysli, je index, který 793 00:34:05,890 --> 00:34:07,070 Jsem se zmínil dříve. 794 00:34:07,070 --> 00:34:09,810 Chcete-li něco hash může být myšlenka jako slovesa. 795 00:34:09,810 --> 00:34:13,690 >> Takže pokud hash Alice je jméno, hašovací funkce, abych tak řekl, 796 00:34:13,690 --> 00:34:14,710 by měla vrátit číslo. 797 00:34:14,710 --> 00:34:18,199 V tomto případě je nula, pokud se patří na umístění nula, jedna, pokud se patří na 798 00:34:18,199 --> 00:34:20,000 polohy na jedné, a tak dále. 799 00:34:20,000 --> 00:34:24,360 Takže moje hashovací funkce bylo dosud Super jednoduché, jen při pohledu na 800 00:34:24,360 --> 00:34:26,159 První písmeno v něčí jméno. 801 00:34:26,159 --> 00:34:29,090 Ale hašovací funkce bere jako vstup některých údaj, 802 00:34:29,090 --> 00:34:30,210 string, int, cokoliv. 803 00:34:30,210 --> 00:34:32,239 A to vyplivne typicky číslo. 804 00:34:32,239 --> 00:34:35,739 A to číslo je, že data, kdy element patří do datové struktury 805 00:34:35,739 --> 00:34:37,800 známý zde jako tabulky hash. 806 00:34:37,800 --> 00:34:41,400 >> Tak jen intuitivně, to je mírně odlišný kontext. 807 00:34:41,400 --> 00:34:44,170 Toto vlastně odkazuje na příklad zahrnující narozeniny, kde 808 00:34:44,170 --> 00:34:46,850 zde může být tolik, kolik 31 dnů v měsíci. 809 00:34:46,850 --> 00:34:52,239 Ale co se to člověk rozhodnout, dělat v případě nehody? 810 00:34:52,239 --> 00:34:55,304 Kontext teď být, ne kolizi jména, ale kolize narozenin, 811 00:34:55,304 --> 00:35:00,760 když se dva lidé mají narozeniny ve stejný den na 2. října, například. 812 00:35:00,760 --> 00:35:02,120 >> STUDENT: [neslyšitelné]. 813 00:35:02,120 --> 00:35:05,010 >> Reproduktor 1: Jo, tak tady máme využití propojených seznamů. 814 00:35:05,010 --> 00:35:07,830 Takže to vypadá trochu jinak než jsme nakreslil dříve. 815 00:35:07,830 --> 00:35:10,790 Ale zdá se, že na pole na levé straně. 816 00:35:10,790 --> 00:35:13,230 To je jeden index, a to bez zvláštní důvod. 817 00:35:13,230 --> 00:35:14,630 Ale je to pořád pole. 818 00:35:14,630 --> 00:35:16,160 Je to pole ukazatelů. 819 00:35:16,160 --> 00:35:20,670 A každý z těchto prvků, z nichž každý z Tyto kruhy nebo lomítka - slash 820 00:35:20,670 --> 00:35:23,970 představuje null - každá z těchto ukazatele se zřejmě ukazuje na 821 00:35:23,970 --> 00:35:25,730 co datová struktura? 822 00:35:25,730 --> 00:35:26,890 Spojový seznam. 823 00:35:26,890 --> 00:35:30,530 >> Takže teď máme schopnost pevný kód do našeho programu 824 00:35:30,530 --> 00:35:32,010 velikost tabulky. 825 00:35:32,010 --> 00:35:35,360 V tomto případě víme, že nikdy více než 31 dnů v měsíci. 826 00:35:35,360 --> 00:35:38,480 Tak těžké kódování hodnoty, jako je 31 rozumné v tomto kontextu. 827 00:35:38,480 --> 00:35:42,700 V souvislosti s názvy, pevný kódování 26 není od věci, že lidé to 828 00:35:42,700 --> 00:35:46,340 pouze názvy začínají, například, abeceda zapojení do Z. 829 00:35:46,340 --> 00:35:50,180 >> Můžeme se nacpat je všechny do těchto údajů struktura tak dlouho, jak když jsme si 830 00:35:50,180 --> 00:35:55,330 kolize, nemáme dát jména zde, namísto toho, že z těchto buněk 831 00:35:55,330 --> 00:36:00,270 ne jako řetězce samotné, ale ukazatele na, například, Alice. 832 00:36:00,270 --> 00:36:03,660 A pak Alice může mít jiný ukazatel na jiný název začíná 833 00:36:03,660 --> 00:36:06,150 A. A Bob se vlastně děje tady. 834 00:36:06,150 --> 00:36:10,850 >> A pokud je tu další jméno začínající pomocí B, on skončí tady. 835 00:36:10,850 --> 00:36:15,070 A tak každý z prvků tohoto stolní dva, když jsme navrhli tento 836 00:36:15,070 --> 00:36:17,350 trochu víc chytře - 837 00:36:17,350 --> 00:36:18,125 no - 838 00:36:18,125 --> 00:36:22,950 když jsme navrhli to trochu víc chytře, se nyní stává adaptivní údajů 839 00:36:22,950 --> 00:36:27,720 struktura, kde neexistuje žádný pevný limit na tom, kolik prvků můžete vložit 840 00:36:27,720 --> 00:36:30,700 do ní, protože pokud máte kolize, to je v pořádku. 841 00:36:30,700 --> 00:36:34,690 Jen do toho pusťte a připojit ji ke co jsme viděli trochu byl ještě před 842 00:36:34,690 --> 00:36:38,290 známý jako propojeného seznamu. 843 00:36:38,290 --> 00:36:39,690 >> Tak pojďme pauzu jen na chvíli. 844 00:36:39,690 --> 00:36:42,570 Co je pravděpodobnost kolize na prvním místě? 845 00:36:42,570 --> 00:36:45,480 Dobře, možná jsem přemýšlel nad, možná Jsem na inženýrské tento problém, 846 00:36:45,480 --> 00:36:46,370 protože víte co? 847 00:36:46,370 --> 00:36:49,070 Ano, mohu přijít s libovolnou Příklady z vrcholu mé hlavy, jako je 848 00:36:49,070 --> 00:36:52,870 Allison a Aaron, ale ve skutečnosti, vzhledem k rovnoměrné rozložení 849 00:36:52,870 --> 00:36:56,990 vstupy, to je nějaký náhodný vkládání do datové struktury, co je opravdu 850 00:36:56,990 --> 00:36:58,580 pravděpodobnost kolize? 851 00:36:58,580 --> 00:37:01,670 Tak se ukázalo, že je to vlastně Super vysoká. 852 00:37:01,670 --> 00:37:03,850 Dovolte mi, abych zobecnit Problém je v tom, jak to. 853 00:37:03,850 --> 00:37:08,890 >> Takže v místnosti n CS50 studenti, co je pravděpodobnost, že alespoň 854 00:37:08,890 --> 00:37:11,010 dva studenti v místnosti mají narozeniny ve stejný den? 855 00:37:11,010 --> 00:37:13,346 Takže to, co. několik Hund - 856 00:37:13,346 --> 00:37:16,790 200, 300 lidí tady a několik set lidí doma dnes. 857 00:37:16,790 --> 00:37:20,670 Takže pokud jste se chtěl zeptat sami sebe, co je pravděpodobnost dvou lidí 858 00:37:20,670 --> 00:37:23,930 v této místnosti má narozeniny ve stejný den, můžeme přijít na to. 859 00:37:23,930 --> 00:37:26,250 A tvrdím, ve skutečnosti existují dva lidé se stejným narozeniny. 860 00:37:26,250 --> 00:37:29,560 >> Například, má někdo má dnes narozeniny? 861 00:37:29,560 --> 00:37:31,340 Včera? 862 00:37:31,340 --> 00:37:32,590 Zítra? 863 00:37:32,590 --> 00:37:35,980 Dobře, takže to vypadá, budu muset udělat 363 nebo tak více 864 00:37:35,980 --> 00:37:39,500 Časy skutečně zjistit, pokud máme kolizi. 865 00:37:39,500 --> 00:37:42,350 Nebo bychom to mohli udělat matematicky spíše než zdlouhavě 866 00:37:42,350 --> 00:37:43,200 jak to udělat. 867 00:37:43,200 --> 00:37:44,500 A navrhuji následující. 868 00:37:44,500 --> 00:37:48,740 >> Takže navrhuji, abychom mohli modelovat pravděpodobnost, že dvě osoby, které mají 869 00:37:48,740 --> 00:37:55,320 narozeniny ve stejný den jako pravděpodobnost 1 minus pravděpodobnost nikdo s 870 00:37:55,320 --> 00:37:56,290 stejně nejlepší. 871 00:37:56,290 --> 00:37:59,960 Takže si to, a to je jen ozdobný způsob, jak psát to, pro 872 00:37:59,960 --> 00:38:03,090 první osoba v pokoji, on nebo ona může mít jeden z možných 873 00:38:03,090 --> 00:38:07,370 narozeniny za předpokladu, že 365 dnů v roce, s omluvou osobám s 874 00:38:07,370 --> 00:38:08,760 29.února narozeniny. 875 00:38:08,760 --> 00:38:13,470 >> Takže první člověk v této místnosti je zdarma mít libovolný počet narozeniny 876 00:38:13,470 --> 00:38:18,280 ze 365 možností tak, že budeme to dělat 365 děleno 365, 877 00:38:18,280 --> 00:38:18,990 což je jedna. 878 00:38:18,990 --> 00:38:22,700 Další osoba v místnosti, v případě, že cílem je, aby se zabránilo kolizi, může jen 879 00:38:22,700 --> 00:38:26,460 mají jeho životnímu jubileu, jak mnoho různých možných dní? 880 00:38:26,460 --> 00:38:27,610 364. 881 00:38:27,610 --> 00:38:31,430 Takže druhý termín v tomto výrazu je v podstatě tím, že matematiku pro nás 882 00:38:31,430 --> 00:38:33,460 odečtením off jeden možný den. 883 00:38:33,460 --> 00:38:36,390 A pak další den, další den, Následující den se na celkovém počtu 884 00:38:36,390 --> 00:38:38,100 lidí v místnosti. 885 00:38:38,100 --> 00:38:41,290 >> A když jsme pak zváží, co pak je pravděpodobnost, ne každý má 886 00:38:41,290 --> 00:38:45,265 Unikátní narozenin, ale opět mínus 1 to, co dostaneme, je výrazem 887 00:38:45,265 --> 00:38:47,810 které mohou velmi fancifully vypadat takto. 888 00:38:47,810 --> 00:38:50,330 Ale je to mnohem zajímavější podívat se na vizuálně. 889 00:38:50,330 --> 00:38:55,120 Toto je tabulka, kde na ose x je počet lidí v místnosti, 890 00:38:55,120 --> 00:38:56,180 počet narozenin. 891 00:38:56,180 --> 00:38:59,840 Na ose y je pravděpodobnost, kolize, dva lidé 892 00:38:59,840 --> 00:39:01,230 mají narozeniny ve stejný den. 893 00:39:01,230 --> 00:39:05,020 >> A stánek s jídlem z této křivky je že jakmile se dostanete do líbí 40 894 00:39:05,020 --> 00:39:11,110 studenti, že jste se na 90% pravděpodobností combinatorically dvou 895 00:39:11,110 --> 00:39:13,550 osoby nebo více, které mají narozeniny ve stejný den. 896 00:39:13,550 --> 00:39:18,600 A jakmile se dostanete líbí 58 lidem, že je to téměř 100% šance dvou 897 00:39:18,600 --> 00:39:21,310 lidé v místnosti se bude muset narozeniny ve stejný den, i když je 898 00:39:21,310 --> 00:39:26,650 365 nebo 366 možných kbelíky a Pouze 58 lidí v místnosti. 899 00:39:26,650 --> 00:39:29,900 Jen statisticky budete pravděpodobně se kolizím, což ve zkratce 900 00:39:29,900 --> 00:39:31,810 motivuje tuto diskusi. 901 00:39:31,810 --> 00:39:35,890 Že i když se dostaneme fantazie tady, a začít s těmito řetězy, jsme stále 902 00:39:35,890 --> 00:39:36,950 bude mít kolize. 903 00:39:36,950 --> 00:39:42,710 >> Tak to vyvolává otázku, co je Náklady dělá inserce a delece 904 00:39:42,710 --> 00:39:44,850 do datové struktury, jako je tento? 905 00:39:44,850 --> 00:39:46,630 Tak mi dovolte navrhnout, - 906 00:39:46,630 --> 00:39:51,570 a nech mě jít zpět na obrazovku přes zde - pokud jsme n prvky 907 00:39:51,570 --> 00:39:56,330 seznam, takže pokud se snažíme vložit n prvků, a máme 908 00:39:56,330 --> 00:39:58,050 kolik celkem lopaty? 909 00:39:58,050 --> 00:40:03,450 Řekněme, že celkem 31 věder v případě narozenin. 910 00:40:03,450 --> 00:40:09,240 Jaká je maximální délka jednoho z těchto řetězců potenciálně? 911 00:40:09,240 --> 00:40:12,670 >> Pokud opět tam 31 možné narozeniny v daném měsíci. 912 00:40:12,670 --> 00:40:14,580 A my jsme jen hrudkující všechny - 913 00:40:14,580 --> 00:40:15,580 ve skutečnosti, že je to hloupý příklad. 914 00:40:15,580 --> 00:40:16,960 Jdem na 26 místo. 915 00:40:16,960 --> 00:40:20,890 Takže pokud skutečně lidé, jejichž jména začít s A až Z, čímž 916 00:40:20,890 --> 00:40:22,780 nás 26 možností. 917 00:40:22,780 --> 00:40:25,920 A my jsme pomocí datové struktury, jako ten jsme právě viděli, čímž máme 918 00:40:25,920 --> 00:40:30,210 pole ukazatelů, z nichž každá poukazuje na připojeném seznamu, kde se 919 00:40:30,210 --> 00:40:32,360 První seznam je každý s názvem Alice. 920 00:40:32,360 --> 00:40:35,770 Druhý seznam je každý s jméno začínající, počínaje 921 00:40:35,770 --> 00:40:36,980 s B, a tak dále. 922 00:40:36,980 --> 00:40:41,020 >> To, co je pravděpodobné, že délka každé z tyto seznamy když budeme předpokládat, pěkný čistý 923 00:40:41,020 --> 00:40:45,410 Rozdělení jmen A až Z v celé datové struktury? 924 00:40:45,410 --> 00:40:50,210 K dispozici je n lidí v datové struktuře děleno 26, pokud jsou dobře 925 00:40:50,210 --> 00:40:52,110 rozprostřeny po celé datové struktury. 926 00:40:52,110 --> 00:40:54,970 Takže délka každé z těchto řetězce je n děleno 26. 927 00:40:54,970 --> 00:40:57,380 Ale ve velkém notace, co to je? 928 00:40:57,380 --> 00:41:00,100 929 00:41:00,100 --> 00:41:02,440 Co je to doopravdy? 930 00:41:02,440 --> 00:41:04,150 Takže je to opravdu jen n, ne? 931 00:41:04,150 --> 00:41:06,620 Protože jsme řekli v minulosti, že fuj vydělte 26. 932 00:41:06,620 --> 00:41:08,710 Ano, ve skutečnosti je to rychlejší. 933 00:41:08,710 --> 00:41:12,720 Ale teoreticky, to není zásadně všechno rychleji. 934 00:41:12,720 --> 00:41:16,040 >> Tak jsme se nezdají být až tak moc blíže k tomuto svatého grálu. 935 00:41:16,040 --> 00:41:17,750 V podstatě je to jen lineární dobu. 936 00:41:17,750 --> 00:41:20,790 Sakra, na tomto místě, tak proč ne my stačí použít jeden obrovský spojový seznam? 937 00:41:20,790 --> 00:41:23,510 Proč ne my stačí použít jeden velký Pole pro ukládání názvů 938 00:41:23,510 --> 00:41:25,010 všichni v místnosti? 939 00:41:25,010 --> 00:41:28,280 No, je tu ještě něco, co přesvědčivá tabulky hash? 940 00:41:28,280 --> 00:41:30,810 Je tu ještě něco, co přesvědčivé o datové struktuře 941 00:41:30,810 --> 00:41:33,940 to vypadá takhle? 942 00:41:33,940 --> 00:41:35,182 Toto. 943 00:41:35,182 --> 00:41:37,050 >> STUDENT: [neslyšitelné]. 944 00:41:37,050 --> 00:41:39,840 >> SPEAKER 1: Jasně, a znovu když je to jen lineární algoritmus, a 945 00:41:39,840 --> 00:41:42,780 lineární čas datová struktura, proč ne já jen ukládat každého název velké 946 00:41:42,780 --> 00:41:44,210 pole, nebo ve velkém propojeného seznamu? 947 00:41:44,210 --> 00:41:47,010 A přestaň dělat UO tak mnohem těžší než je třeba, aby se? 948 00:41:47,010 --> 00:41:49,600 949 00:41:49,600 --> 00:41:53,190 Co je přesvědčivá, byť i když jsem škrábal ven? 950 00:41:53,190 --> 00:41:54,930 >> STUDENT: [neslyšitelné]. 951 00:41:54,930 --> 00:41:57,040 >> SPEAKER 1: Insertions nejsou? 952 00:41:57,040 --> 00:41:58,140 Drahé už ne. 953 00:41:58,140 --> 00:42:03,390 Takže vložky potenciálně mohli i nadále být konstantní čas, i když data 954 00:42:03,390 --> 00:42:07,910 Struktura vypadá to, řadu ukazatele, z nichž každý ukazuje na 955 00:42:07,910 --> 00:42:09,550 potenciálně spojové seznamy. 956 00:42:09,550 --> 00:42:15,220 Jak byste mohli dosáhnout konstantní čas vložení jména? 957 00:42:15,220 --> 00:42:16,280 Držet ji v přední části, ne? 958 00:42:16,280 --> 00:42:19,290 >> Pokud bychom obětovat cíl návrhu od dříve, kde jsme chtěli udržet 959 00:42:19,290 --> 00:42:22,650 každého název, například, třídění, nebo všechna čísla na scéně řazeny, 960 00:42:22,650 --> 00:42:25,020 Předpokládejme, že máme netříděného spojový seznam. 961 00:42:25,020 --> 00:42:29,960 To jen nás stojí jeden nebo dva kroky, jako v případě Bena a Brianem 962 00:42:29,960 --> 00:42:32,750 dříve, vložit prvek na na začátku seznamu. 963 00:42:32,750 --> 00:42:36,090 Takže pokud se nechcete starat o třídění všechny jmen začínajících nebo všechny 964 00:42:36,090 --> 00:42:39,660 jména začínající na B, můžeme stále dosáhnout konstantní čas vložení. 965 00:42:39,660 --> 00:42:43,900 Nyní vzhlédl Alice nebo Bob nebo jakýkoli název obecně je stále co? 966 00:42:43,900 --> 00:42:48,100 Je to velký O n děleno 26, v ideální případ, kdy jsou všichni jednotně 967 00:42:48,100 --> 00:42:51,190 distribuovány, kde je tolik, kolik je protože jsou to Z, což je pravděpodobně 968 00:42:51,190 --> 00:42:52,220 nereálné. 969 00:42:52,220 --> 00:42:53,880 Ale to je stále lineární. 970 00:42:53,880 --> 00:42:57,120 >> Ale tady jsme se vrátit k bodu z asymptotické notace bytí 971 00:42:57,120 --> 00:42:58,600 teoreticky pravda. 972 00:42:58,600 --> 00:43:02,960 Ale v reálném světě, když tvrdí, že můj program něco udělat 26 krát 973 00:43:02,960 --> 00:43:06,210 rychleji než ty, jejichž program, budete raději používáte? 974 00:43:06,210 --> 00:43:09,660 S pozdravem a dolu, což je 26 krát rychlejší? 975 00:43:09,660 --> 00:43:14,320 Realisticky, osoba, která je o 26 krát rychlejší, i když je to teoreticky 976 00:43:14,320 --> 00:43:18,790 naše algoritmy spustit ve stejném asymptotická době jeho běhu. 977 00:43:18,790 --> 00:43:20,940 >> Dovolte mi navrhnout jiný řešení vůbec. 978 00:43:20,940 --> 00:43:24,380 A pokud to nebude foukat vaši mysl, jsme z datových struktur. 979 00:43:24,380 --> 00:43:27,420 Tak to je trie - 980 00:43:27,420 --> 00:43:28,520 druh hloupé jméno. 981 00:43:28,520 --> 00:43:32,880 Pochází z rešerší, a slovo se píše trie, t-r-i-e, protože 982 00:43:32,880 --> 00:43:34,450 Kurz vyhledávání zní jako trie. 983 00:43:34,450 --> 00:43:36,580 Ale to je historie na slovo trie. 984 00:43:36,580 --> 00:43:40,980 >> Takže trie je opravdu nějaký druh stromu, a je to také hra na dané slovo. 985 00:43:40,980 --> 00:43:46,330 A i když nemůžete docela vidět s touto vizualizací, trie je 986 00:43:46,330 --> 00:43:50,790 strom strukturován jako rodokmenu s jeden předek nahoře a mnoho 987 00:43:50,790 --> 00:43:54,530 vnoučat a velkých vnoučata jako listy na dně. 988 00:43:54,530 --> 00:43:58,100 Ale každý uzel trie je pole. 989 00:43:58,100 --> 00:44:00,680 A to je v poli - a pojďme zjednodušovat na chvíli - je to 990 00:44:00,680 --> 00:44:04,600 pole, v tomto případě o velikosti 26, kde každý uzel je opět pole o velikosti 991 00:44:04,600 --> 00:44:09,000 26, kde je v tom, že nultý prvek pole představuje, a poslední 992 00:44:09,000 --> 00:44:11,810 element v každé takové Pole představuje Z. 993 00:44:11,810 --> 00:44:15,520 >> Takže navrhuji tedy, aby tato data struktury, známé jako trie, může být 994 00:44:15,520 --> 00:44:17,600 použít i pro ukládání slova. 995 00:44:17,600 --> 00:44:21,740 Viděli jsme před chvílí, jak bychom mohli uložit slova, nebo v tomto případě jména, a my 996 00:44:21,740 --> 00:44:25,440 již viděli, jak můžeme uložit čísla, ale pokud se zaměříme na názvy nebo řetězce 997 00:44:25,440 --> 00:44:27,460 Zde si všimněte, co je zajímavé. 998 00:44:27,460 --> 00:44:32,210 Tvrdím, že název je Maxwell v této datové struktury. 999 00:44:32,210 --> 00:44:33,730 Kde vidíte Maxwell? 1000 00:44:33,730 --> 00:44:35,140 >> STUDENT: [neslyšitelné]. 1001 00:44:35,140 --> 00:44:36,240 >> SPEAKER 1: Na levé straně. 1002 00:44:36,240 --> 00:44:39,910 Takže to, co je zajímavé, s těmito daty struktura je spíše než obchod se 1003 00:44:39,910 --> 00:44:46,200 řetězec M-A-X-W-E-L-L lomítko nula, všechny souvislý, co můžete udělat, místo toho 1004 00:44:46,200 --> 00:44:46,890 je následující. 1005 00:44:46,890 --> 00:44:50,510 Pokud se jedná o trie jako datové struktury, každý jehož uzlech je opět pole, 1006 00:44:50,510 --> 00:44:54,650 a chcete uložit Maxwell, musíte nejprve index, a tak v kořenovém uzlu, takže 1007 00:44:54,650 --> 00:44:57,810 mluvit, nejhořejší uzel, na umístění M, vpravo, tak 1008 00:44:57,810 --> 00:44:59,160 zhruba do středu. 1009 00:44:59,160 --> 00:45:03,740 A pak odtud, postupujte ukazatel na podřízené uzly, abych tak řekl. 1010 00:45:03,740 --> 00:45:06,150 Takže v rodokmenu smyslu, budete postupovat směrem dolů. 1011 00:45:06,150 --> 00:45:09,030 A, které vás dovedou do jiného uzlu Vlevo, který je 1012 00:45:09,030 --> 00:45:10,540 jen další pole. 1013 00:45:10,540 --> 00:45:14,710 >> A pak, pokud chcete uložit Maxwell, najdete ukazatel, který představuje 1014 00:45:14,710 --> 00:45:16,430 A, což je toto zde. 1015 00:45:16,430 --> 00:45:17,840 Pak můžete jít na další uzel. 1016 00:45:17,840 --> 00:45:20,100 A upozornění - to je důvod, proč je obraz trochu klame - 1017 00:45:20,100 --> 00:45:21,990 Tento uzel vypadat Super malý. 1018 00:45:21,990 --> 00:45:26,050 Ale na pravé straně je Y a Z. Je to jen autor zkrácen 1019 00:45:26,050 --> 00:45:27,630 obraz tak, že jste skutečně vidět věci. 1020 00:45:27,630 --> 00:45:30,400 Jinak tento obrázek by bylo velmi široké. 1021 00:45:30,400 --> 00:45:36,180 Takže teď si index do umístění X, pak W, pak E, pak L, pak L. Tak co je 1022 00:45:36,180 --> 00:45:37,380 to zvědavost? 1023 00:45:37,380 --> 00:45:41,250 >> No, pokud budeme používat tento druh nový se o tom, jak ukládat řetězec 1024 00:45:41,250 --> 00:45:44,500 datová struktura, stále musíte v podstatě zaškrtnout v datech 1025 00:45:44,500 --> 00:45:47,250 struktura, která slovo zde končí. 1026 00:45:47,250 --> 00:45:50,830 Jinými slovy, každý z těchto uzlů nějak musí pamatovat, že jsme 1027 00:45:50,830 --> 00:45:53,500 vlastně následoval všech těchto ukazatelů a odcházejí trochu 1028 00:45:53,500 --> 00:45:58,370 chléb drobky ve spodní části zde v této Struktura pro označení M-A-X-W-E-L-L 1029 00:45:58,370 --> 00:46:00,230 ve skutečnosti v této datové struktury. 1030 00:46:00,230 --> 00:46:02,040 >> Tak bychom mohli postupovat takto. 1031 00:46:02,040 --> 00:46:06,810 Každý z uzlů v obraze jsme jen Pila má jeden, pole o velikosti 27. 1032 00:46:06,810 --> 00:46:10,550 A to je v současné době 27, protože v p nastavit šest, budeme ve skutečnosti vám apostrof, 1033 00:46:10,550 --> 00:46:13,590 takže můžeme mít jména jako O'Reilly a jiní s apostrofy. 1034 00:46:13,590 --> 00:46:14,820 Ale stejný nápad. 1035 00:46:14,820 --> 00:46:17,710 Každý z těchto prvků v pole poukazuje na struct 1036 00:46:17,710 --> 00:46:19,320 uzel, tak jen uzel. 1037 00:46:19,320 --> 00:46:21,430 Tak to je velmi připomínající našeho propojeného seznamu. 1038 00:46:21,430 --> 00:46:24,550 >> A pak jsem si Boolean, který budu zavolejte slovo, které je jen bude 1039 00:46:24,550 --> 00:46:29,120 true, pokud slovo končí na to uzel ve stromu. 1040 00:46:29,120 --> 00:46:32,870 Je to skutečně představuje malý trojúhelník jsme viděli před chvílí. 1041 00:46:32,870 --> 00:46:37,190 Takže pokud slovo končí v tomto uzlu strom, bude to slovo pole je pravda, 1042 00:46:37,190 --> 00:46:41,990 který je koncepčně zaškrtnutím nebo jsme kreslíte tohoto trojúhelníku, ano, tam 1043 00:46:41,990 --> 00:46:44,080 je slovo zde. 1044 00:46:44,080 --> 00:46:45,120 >> Tak to je trie. 1045 00:46:45,120 --> 00:46:48,540 A teď je otázka, co je jeho doba chodu? 1046 00:46:48,540 --> 00:46:49,930 Je to velký O n? 1047 00:46:49,930 --> 00:46:51,410 Je to něco jiného? 1048 00:46:51,410 --> 00:46:57,330 No, pokud jste n názvy těchto údajů struktura, Maxwell je pouze jedním z 1049 00:46:57,330 --> 00:47:02,330 je, jaká je doba chodu vkládání nebo zjištění Maxwell? 1050 00:47:02,330 --> 00:47:06,230 1051 00:47:06,230 --> 00:47:09,050 Co je to doba chodu vložení Maxwell? 1052 00:47:09,050 --> 00:47:11,740 Pokud existuje n jiná jména již v tabulce? 1053 00:47:11,740 --> 00:47:12,507 Jo? 1054 00:47:12,507 --> 00:47:15,429 >> STUDENT: [neslyšitelné]. 1055 00:47:15,429 --> 00:47:17,550 >> SPEAKER 1: Jo, je to délka jména, ne? 1056 00:47:17,550 --> 00:47:24,420 Tak M-a-x-w-e-l-l, takže to je takto algoritmus je velký O sedm. 1057 00:47:24,420 --> 00:47:26,580 Nyní, samozřejmě, název mají různou délku. 1058 00:47:26,580 --> 00:47:27,380 Možná je to krátký název. 1059 00:47:27,380 --> 00:47:28,600 Třeba je to delší jména. 1060 00:47:28,600 --> 00:47:33,390 Ale co je klíčové je to, že je to neustálý číslo. 1061 00:47:33,390 --> 00:47:36,810 A možná to opravdu není konstantní, Ale Bůh, když realisticky, v 1062 00:47:36,810 --> 00:47:41,570 slovník, je to asi nějaká hranice, Na počtem písmen ve 1063 00:47:41,570 --> 00:47:43,820 jméno osoby v dané zemi. 1064 00:47:43,820 --> 00:47:46,940 >> A tak můžeme předpokládat, že hodnota je konstantní. 1065 00:47:46,940 --> 00:47:47,750 Nevím, co to je. 1066 00:47:47,750 --> 00:47:50,440 Je to pravděpodobně větší než si myslíme, že je. 1067 00:47:50,440 --> 00:47:52,720 Protože tam je vždy nějaký roh pouzdro s crazy dlouhým názvem. 1068 00:47:52,720 --> 00:47:56,360 Takže řekněme, že k, ale je to stále konstantní pravděpodobně, protože každý 1069 00:47:56,360 --> 00:48:00,190 jméno ve světě, alespoň v Zejména země, je to, že délka nebo 1070 00:48:00,190 --> 00:48:01,780 kratší, takže je konstantní. 1071 00:48:01,780 --> 00:48:04,490 Ale když jsme řekli, že je něco velké O konstantní hodnoty, co je to 1072 00:48:04,490 --> 00:48:07,760 skutečně odpovídá? 1073 00:48:07,760 --> 00:48:10,420 To je opravdu to samé jak říká konstantní čas. 1074 00:48:10,420 --> 00:48:11,530 >> Teď jsme trochu podvádění, ne? 1075 00:48:11,530 --> 00:48:15,340 Jsme druh využití teorii, zde říci, že dobře, aby součinitele je 1076 00:48:15,340 --> 00:48:17,450 opravdu jen řádově jedné, a to je konstantní čas. 1077 00:48:17,450 --> 00:48:18,200 Ale ve skutečnosti je. 1078 00:48:18,200 --> 00:48:22,550 Vzhledem k tomu, Klíčovou myšlenkou je, že pokud jsme n jména již v tomto 1079 00:48:22,550 --> 00:48:26,010 datové struktury, a vložíme Maxwell, je množství času, které nás zavede do 1080 00:48:26,010 --> 00:48:29,530 vložit Maxwell vůbec postižené tím, kolik dalších lidí 1081 00:48:29,530 --> 00:48:31,100 jsou v datové struktuře? 1082 00:48:31,100 --> 00:48:31,670 Nezdá se, že být. 1083 00:48:31,670 --> 00:48:36,280 Kdybych měl miliardu více prvků této trie a vložte Maxwell, je 1084 00:48:36,280 --> 00:48:38,650 se vůbec týká? 1085 00:48:38,650 --> 00:48:39,050 Ne. 1086 00:48:39,050 --> 00:48:42,950 A to je na rozdíl od některého z denních dat struktury jsme viděli doposud, kdy 1087 00:48:42,950 --> 00:48:46,820 doba chodu algoritmu je zcela nezávisle na tom, jak moc 1088 00:48:46,820 --> 00:48:51,430 věc je nebo není již v této datové struktury. 1089 00:48:51,430 --> 00:48:54,650 >> A tak s tím poskytuje nyní je příležitost pro p sadu šesti, která bude 1090 00:48:54,650 --> 00:48:58,310 opět zahrnovat realizaci vlastní Kontrola pravopisu, čtení v 150000 1091 00:48:58,310 --> 00:49:01,050 slova, jak nejlépe uložit, že není nutně zřejmé. 1092 00:49:01,050 --> 00:49:04,030 A když jsem usiloval, aby si Svatý grál, vůbec se mi nelíbí 1093 00:49:04,030 --> 00:49:05,330 tvrdí, že je trie. 1094 00:49:05,330 --> 00:49:09,810 Ve skutečnosti může být hašovací tabulka velmi dobře ukáže být mnohem efektivnější. 1095 00:49:09,810 --> 00:49:10,830 Ale to jsou jen - 1096 00:49:10,830 --> 00:49:14,620 to je jen jedna z rozhodnutí o návrhu budete muset udělat. 1097 00:49:14,620 --> 00:49:18,920 >> Ale při uzavírání pojďme 50 nebo tak sekund se podívat na to, co je 1098 00:49:18,920 --> 00:49:22,190 před příští týden a my po přechodu z tohoto příkazového řádku 1099 00:49:22,190 --> 00:49:26,220 světě, pokud C programy k věcem web založené a jazyky jako PHP a 1100 00:49:26,220 --> 00:49:30,350 JavaScript a internet sám, protokoly jako HTTP, kterou jste 1101 00:49:30,350 --> 00:49:32,870 brát za samozřejmost let teď, a napsal většinu každý 1102 00:49:32,870 --> 00:49:34,440 den, možná, nebo vidět. 1103 00:49:34,440 --> 00:49:37,420 A začneme oloupejte vrstvy, co je internet. 1104 00:49:37,420 --> 00:49:40,650 A co je kód, který tvoří základ dnešní nástroje. 1105 00:49:40,650 --> 00:49:43,230 Takže 50 sekund tohoto ukázku zde. 1106 00:49:43,230 --> 00:49:46,570 Dám vám Bojovníci sítě. 1107 00:49:46,570 --> 00:49:51,370 >> [PŘEHRÁVÁNÍ] 1108 00:49:51,370 --> 00:49:56,764 >> -Přišel se zprávou. 1109 00:49:56,764 --> 00:50:00,687 S protokolem všichni jeho vlastní. 1110 00:50:00,687 --> 00:50:13,370 1111 00:50:13,370 --> 00:50:19,780 Přišel na svět krutých firewallů, bezcitný routery a nebezpečí daleko 1112 00:50:19,780 --> 00:50:22,600 horší než smrt. 1113 00:50:22,600 --> 00:50:23,590 Je rychlý. 1114 00:50:23,590 --> 00:50:25,300 Je silný. 1115 00:50:25,300 --> 00:50:27,700 Je TCPIP. 1116 00:50:27,700 --> 00:50:30,420 A má svou adresu. 1117 00:50:30,420 --> 00:50:32,920 1118 00:50:32,920 --> 00:50:34,590 Válečníci sítě. 1119 00:50:34,590 --> 00:50:35,290 >> [END PŘEHRÁVÁNÍ] 1120 00:50:35,290 --> 00:50:38,070 >> SPEAKER 1: To je, jak internet musí pracovat od příštího týdne. 1121 00:50:38,070 --> 00:50:40,406