1 00:00:00,000 --> 00:00:11,860 2 00:00:11,860 --> 00:00:13,120 >> SPEAKER 1: Dobre, takže sme späť. 3 00:00:13,120 --> 00:00:14,480 Vitajte na CS50. 4 00:00:14,480 --> 00:00:16,510 To je koniec týždňa sedem. 5 00:00:16,510 --> 00:00:20,200 Takže pripomenúť, že minule sme začali pri pohľade na niečo sofistikovanejšie 6 00:00:20,200 --> 00:00:21,100 dátové štruktúry. 7 00:00:21,100 --> 00:00:25,110 Vzhľadom k tomu, až do teraz, sme mali naozaj máme k dispozícii to bolo, pole. 8 00:00:25,110 --> 00:00:29,340 >> Ale skôr, než sme sa zbaviť poľa tak, že všetko zaujímavé, čo naozaj to 9 00:00:29,340 --> 00:00:33,570 v skutočnosti je, aké sú niektoré z klady tohto jednoduchého dát 10 00:00:33,570 --> 00:00:34,560 štruktúra tak ďaleko? 11 00:00:34,560 --> 00:00:36,110 Čo je to dobrý? 12 00:00:36,110 --> 00:00:39,450 Zatiaľ, ako sme videli? 13 00:00:39,450 --> 00:00:42,540 Čo to máš? 14 00:00:42,540 --> 00:00:44,028 Nič. 15 00:00:44,028 --> 00:00:45,020 >> STUDENT: [nepočuteľné]. 16 00:00:45,020 --> 00:00:45,395 >> SPEAKER 1: Čo je to? 17 00:00:45,395 --> 00:00:46,410 >> STUDENT: [nepočuteľné]. 18 00:00:46,410 --> 00:00:47,000 >> SPEAKER 1: Pevná veľkosť. 19 00:00:47,000 --> 00:00:51,260 OK, tak prečo je pevnou veľkosť dobrý aj keď? 20 00:00:51,260 --> 00:00:53,180 >> STUDENT: [nepočuteľné]. 21 00:00:53,180 --> 00:00:56,240 >> SPEAKER 1: OK, takže je to efektívna pocit, že môžete prideľovať 22 00:00:56,240 --> 00:01:00,070 pevná suma z vesmíru, čo snáď je presne toľko, koľko 23 00:01:00,070 --> 00:01:01,180 priestor tak, ako chcete. 24 00:01:01,180 --> 00:01:02,720 Takže to môže byť absolútne plus. 25 00:01:02,720 --> 00:01:06,530 >> Čo iného sa strana pole? 26 00:01:06,530 --> 00:01:07,610 Jo? 27 00:01:07,610 --> 00:01:08,750 >> STUDENT: [nepočuteľné]. 28 00:01:08,750 --> 00:01:09,550 >> SPEAKER 1: All - Čože? 29 00:01:09,550 --> 00:01:11,270 >> STUDENT: [nepočuteľné]. 30 00:01:11,270 --> 00:01:13,620 >> SPEAKER 1: Všetky boxy v pamäti alebo vedľa seba. 31 00:01:13,620 --> 00:01:15,220 A to je užitočné - prečo? 32 00:01:15,220 --> 00:01:15,970 To je celkom pravda. 33 00:01:15,970 --> 00:01:18,611 Ale ako môžeme využiť, že pravdu? 34 00:01:18,611 --> 00:01:21,500 >> STUDENT: [nepočuteľné]. 35 00:01:21,500 --> 00:01:24,490 >> SPEAKER 1: Presne tak, môžeme sledovať kde je všetko len na základe znalosti 36 00:01:24,490 --> 00:01:28,560 jednu adresu, a to na adresu prvý bajt tohto bloku pamäte. 37 00:01:28,560 --> 00:01:30,420 Alebo v prípade, že reťazec, adresa prvý 38 00:01:30,420 --> 00:01:31,460 char v tomto reťazci. 39 00:01:31,460 --> 00:01:33,330 A odtiaľ môžeme nájsť koniec reťazca. 40 00:01:33,330 --> 00:01:35,710 Nájdeme tu Druhý prvok, Tretia časť, a tak ďalej. 41 00:01:35,710 --> 00:01:38,740 >> A tak fantastický spôsob, ako to opísať rysom je, že pole nám 42 00:01:38,740 --> 00:01:40,020 náhodný prístup. 43 00:01:40,020 --> 00:01:44,330 Len pomocou hranatou zátvorkou zápis a číslo, môžete preskočiť na 44 00:01:44,330 --> 00:01:48,070 špecifický prvok v poli v konštantnom čase, veľké O 45 00:01:48,070 --> 00:01:49,810 jedného, ​​aby som tak povedal. 46 00:01:49,810 --> 00:01:51,080 >> Ale tam bolo nejaké tienisté stránky. 47 00:01:51,080 --> 00:01:53,110 Čo pole neurobil veľmi ľahko? 48 00:01:53,110 --> 00:01:55,810 49 00:01:55,810 --> 00:01:57,170 Čo je to vôbec dobré? 50 00:01:57,170 --> 00:01:58,810 >> STUDENT: [nepočuteľné]. 51 00:01:58,810 --> 00:01:59,860 >> SPEAKER 1: Čo je to? 52 00:01:59,860 --> 00:02:00,530 >> STUDENT: [nepočuteľné]. 53 00:02:00,530 --> 00:02:01,460 >> Reproduktor 1: Rozšírenie vo veľkosti. 54 00:02:01,460 --> 00:02:04,800 Takže tienisté polia sú presne opak toho, čo 55 00:02:04,800 --> 00:02:05,540 upsides sú. 56 00:02:05,540 --> 00:02:07,610 Takže jedna z nevýhod je že je to pevnú veľkosť. 57 00:02:07,610 --> 00:02:09,400 Takže si môžete naozaj ju pestovať. 58 00:02:09,400 --> 00:02:13,510 Môžete prideliť väčší kus pamäť, a potom sa presunúť staré prvky 59 00:02:13,510 --> 00:02:14,460 do nového poľa. 60 00:02:14,460 --> 00:02:18,060 A potom bez stará pole, pre inštancie, pomocou malloc alebo podobný 61 00:02:18,060 --> 00:02:21,180 funkcia je volaná realloc, ktoré realokuje pamäť. 62 00:02:21,180 --> 00:02:25,490 >> Realloc, ako stranou, sa snaží, aby vám pamäť, ktorá je vedľa poľa 63 00:02:25,490 --> 00:02:26,610 že už máte. 64 00:02:26,610 --> 00:02:28,740 Ale to by sa veci pohli asi úplne. 65 00:02:28,740 --> 00:02:30,710 Ale v skratke, je to drahé, nie? 66 00:02:30,710 --> 00:02:33,440 Pretože ak máte kus pamäti tejto veľkosti, ale naozaj chcem 67 00:02:33,440 --> 00:02:36,710 tejto veľkosti, a chcete zachovať zachované pôvodné prvky, budete musieť 68 00:02:36,710 --> 00:02:40,510 približne lineárny čas Proces kopírovania že je potrebné, aby sa 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 sa pýta prevádzkové systém znovu a znovu a 71 00:02:44,630 --> 00:02:48,340 opäť veľké kusy pamäte môže začať stáť nejaký čas rovnako. 72 00:02:48,340 --> 00:02:52,250 Takže je to požehnaním i prekliatím v zastierať, že tieto polia 73 00:02:52,250 --> 00:02:53,860 sú pevné dĺžky. 74 00:02:53,860 --> 00:02:56,790 Ale keď si predstavíme niečo miesto takto, ktorú nazýva prepojený 75 00:02:56,790 --> 00:03:00,580 zoznam, dostaneme niekoľko upsides a niekoľko tienisté i tu. 76 00:03:00,580 --> 00:03:05,780 >> Takže spájať zoznam je jednoducho dát štruktúra tvorená structs C v tomto 77 00:03:05,780 --> 00:03:09,850 prípad, kedy struct, odvolanie, je len kontajner pre jeden alebo viac špecifických 78 00:03:09,850 --> 00:03:11,100 typy premenných. 79 00:03:11,100 --> 00:03:16,110 V tomto prípade, čo si dátové typy Zdá sa, že vo vnútri struct, ktorý 80 00:03:16,110 --> 00:03:17,600 Naposledy sme nazývaný uzol? 81 00:03:17,600 --> 00:03:19,380 Každý z týchto obdĺžnikov je uzol. 82 00:03:19,380 --> 00:03:22,660 A každý z menších obdĺžnikov vnútri nej je dátový typ. 83 00:03:22,660 --> 00:03:25,300 Aké typy si hovoríme boli v pondelok? 84 00:03:25,300 --> 00:03:26,478 Jo? 85 00:03:26,478 --> 00:03:27,870 >> STUDENT: [nepočuteľné]. 86 00:03:27,870 --> 00:03:30,721 >> SPEAKER 1: variabilné a ukazovateľ alebo Presnejšie povedané, int, pre N, 87 00:03:30,721 --> 00:03:32,180 a ukazovateľ v dolnej časti. 88 00:03:32,180 --> 00:03:35,360 Obaja ti stalo, že 32 bitov na aspoň na počítači, ako je tento CS50 89 00:03:35,360 --> 00:03:37,980 Zariadení, a tak sú ťahané rovnako vo veľkosti. 90 00:03:37,980 --> 00:03:42,260 >> Takže to, čo používate ukazovateľ keď za zjavne? 91 00:03:42,260 --> 00:03:47,690 Prečo pridať na túto šípku teraz, keď pole bolo tak pekné a čisté a jednoduché? 92 00:03:47,690 --> 00:03:50,460 Čo je to ukazovateľ robí pre nás v každej z týchto uzlov? 93 00:03:50,460 --> 00:03:52,160 >> STUDENT: [nepočuteľné]. 94 00:03:52,160 --> 00:03:52,465 >> SPEAKER 1: Presne tak. 95 00:03:52,465 --> 00:03:54,120 Je to povie, kde Ďalšie nikto. 96 00:03:54,120 --> 00:03:57,350 Tak nejako som použiť analógiu pomocou vlákno nejako 97 00:03:57,350 --> 00:03:59,180 niť týchto uzlov dohromady. 98 00:03:59,180 --> 00:04:01,760 A to je presne to, čo robíme s ukazovatele, pretože každý z nich 99 00:04:01,760 --> 00:04:06,360 kúsky pamäti môže, ale nemusí byť súvislé, chrbtom k sebe k sebe 100 00:04:06,360 --> 00:04:09,500 v pamäti RAM, pretože zakaždým, keď sa volania malloc povedal, daj mi dosť 101 00:04:09,500 --> 00:04:12,510 bajtov pre nový uzol, mohlo by to tú, alebo by to mohlo byť. 102 00:04:12,510 --> 00:04:13,120 Mohlo by to byť tu. 103 00:04:13,120 --> 00:04:13,730 Mohlo by to byť tu. 104 00:04:13,730 --> 00:04:14,640 Proste neviem. 105 00:04:14,640 --> 00:04:17,880 >> Ale s použitím ukazovateľa na adresy ty uzly, môžete steh je 106 00:04:17,880 --> 00:04:22,370 spoločne tak, že vyzerá vizuálne ako zoznam, aj keď tieto veci sú 107 00:04:22,370 --> 00:04:26,770 všetko rozprestreté v celom jednom alebo vaše dve alebo štyri gigabajty vaše RAM 108 00:04:26,770 --> 00:04:28,760 vnútri vášho vlastného počítača. 109 00:04:28,760 --> 00:04:33,230 >> Tak nevýhodou, potom, spájať zoznam je čo? 110 00:04:33,230 --> 00:04:34,670 Čo je to cena, ktorú sme zrejme platiť? 111 00:04:34,670 --> 00:04:36,010 >> STUDENT: [nepočuteľné]. 112 00:04:36,010 --> 00:04:36,920 >> SPEAKER 1: Viac miesta, že jo? 113 00:04:36,920 --> 00:04:39,340 Sme v tomto prípade, zdvojnásobil množstvo priestoru, pretože sme šli 114 00:04:39,340 --> 00:04:43,500 z 32 bitov pre každý uzol, pre každú int, takže teraz 64 bitov, pretože musíme 115 00:04:43,500 --> 00:04:45,050 držať okolo ukazovateľ rovnako. 116 00:04:45,050 --> 00:04:48,860 Získate väčšiu účinnosť, ak váš struct je väčšia ako táto jednoduchá vec. 117 00:04:48,860 --> 00:04:52,020 Ak ste skutočne študenta vnútri z ktorých je niekoľko stringov 118 00:04:52,020 --> 00:04:55,430 meno a dom, možno číslo, možno niektorých ďalších odborov dohromady. 119 00:04:55,430 --> 00:04:59,000 >> Takže ak máte dostatočne veľký struct, potom možno cena ukazovateľ je 120 00:04:59,000 --> 00:05:00,010 nie je tak veľký problém. 121 00:05:00,010 --> 00:05:03,570 Toto je trochu rohové prípadu v tom, že sme ukladanie taký jednoduchý primitívne 122 00:05:03,570 --> 00:05:04,760 vnútri prepojeného zoznamu. 123 00:05:04,760 --> 00:05:05,790 Ale ide o to isté. 124 00:05:05,790 --> 00:05:08,230 Tie určite tráviť viac pamäť, ale vy ste stále 125 00:05:08,230 --> 00:05:08,990 flexibilita. 126 00:05:08,990 --> 00:05:12,280 Pretože teraz, keď chcem pridať prvok na začiatku tohto zoznamu, 127 00:05:12,280 --> 00:05:14,340 Musím prideliť nový uzol. 128 00:05:14,340 --> 00:05:17,180 A ja mám len tie aktualizácie šípky akosi len pohybujúce 129 00:05:17,180 --> 00:05:17,980 niekoľko rád okolo. 130 00:05:17,980 --> 00:05:20,580 >> Ak chcem vložiť niečo do uprostred zoznamu, nemám na 131 00:05:20,580 --> 00:05:24,410 tlačiť všetky stranou, ako tomu bolo v minulosť týždňov s našimi dobrovoľníkmi, ktorí 132 00:05:24,410 --> 00:05:25,700 predstavovala pole. 133 00:05:25,700 --> 00:05:29,470 Môžem len prideliť nový uzol a potom stačí poukázať na šípky v 134 00:05:29,470 --> 00:05:32,290 rôzne smery, pretože to nie je musí zostať v aktuálnej 135 00:05:32,290 --> 00:05:35,670 pamäť pravda, linka, ako by som vypracované je to tu na obrazovke. 136 00:05:35,670 --> 00:05:38,400 >> A potom napokon, ak chcete vložiť niečo na koniec zoznamu, je 137 00:05:38,400 --> 00:05:39,210 ešte jednoduchšie. 138 00:05:39,210 --> 00:05:43,320 To je niečo svojvoľného notáciu, ale 34 je ukazovateľ, hádajte. 139 00:05:43,320 --> 00:05:46,710 Aká je hodnota jeho ukazovateľ najviac pravdepodobne vyvodiť niečo ako starý 140 00:05:46,710 --> 00:05:47,700 Škola anténa tam? 141 00:05:47,700 --> 00:05:48,920 >> STUDENT: [nepočuteľné]. 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 naozaj to je jedna autora zastúpenie null. 144 00:05:52,710 --> 00:05:56,310 A to je null, pretože ste úplne Potrebujete vedieť, kde je koniec spojovaceho 145 00:05:56,310 --> 00:06:00,050 zoznam, inak budete mať nasledujúce a sledovanie a po týchto šípok 146 00:06:00,050 --> 00:06:01,170 do určitej hodnoty odpadky. 147 00:06:01,170 --> 00:06:06,230 Takže null bude znamenať, že neexistuje viac uzlov napravo od čísla 34, 148 00:06:06,230 --> 00:06:07,200 v tomto prípade. 149 00:06:07,200 --> 00:06:10,270 >> Takže navrhujeme, že môžeme realizovať tento uzol v kóde. 150 00:06:10,270 --> 00:06:12,130 A my sme videli tento druh syntaxe pred. 151 00:06:12,130 --> 00:06:15,090 Typedef len definuje nový typ nám, nám dáva ako synonymum 152 00:06:15,090 --> 00:06:17,100 string bol pre char *. 153 00:06:17,100 --> 00:06:21,030 V tomto prípade to bude, aby nám skrátený zápis tak, že struct uzol 154 00:06:21,030 --> 00:06:24,010 Namiesto toho môžete byť len zapísať ako uzol, ktorý je oveľa čistejšie. 155 00:06:24,010 --> 00:06:25,360 Je to oveľa menej ukecaný. 156 00:06:25,360 --> 00:06:30,080 >> Vnútri uzla je zrejme int tzv n, a potom struct node * 157 00:06:30,080 --> 00:06:34,670 čo znamená, že presne to, čo sme chceli šípky znamená, ukazovateľ na ďalšie 158 00:06:34,670 --> 00:06:36,940 uzol presne rovnakého typu. 159 00:06:36,940 --> 00:06:40,300 A ja navrhujem, aby sme mohli realizovať vyhľadávacie funkcie ako je tento, ktorý v 160 00:06:40,300 --> 00:06:41,890 prvý pohľad by sa mohlo zdať trochu zložitejšie. 161 00:06:41,890 --> 00:06:43,330 Ale pozrime sa, že v kontexte. 162 00:06:43,330 --> 00:06:45,480 >> Nechaj ma ísť cez spotrebiče tady. 163 00:06:45,480 --> 00:06:48,460 Dovoľte mi otvoriť súbor s názvom Zoznam nulový bod h 164 00:06:48,460 --> 00:06:53,950 A že obsahuje iba definíciu my práve videl pred chvíľou na tieto dáta 165 00:06:53,950 --> 00:06:55,390 typ nazývaný uzol. 166 00:06:55,390 --> 00:06:57,350 Takže sme dali, že do súboru dot hodín. 167 00:06:57,350 --> 00:07:01,430 >> A ako stranou, aj keď to program, ktorý sa chystáte vidieť, je 168 00:07:01,430 --> 00:07:05,410 nie je tak zložité, je to v skutočnosti Konvencie pri písaní programu 169 00:07:05,410 --> 00:07:10,270 dať veci ako dátové typy, ťahať konštanty niekedy vnútri vášho 170 00:07:10,270 --> 00:07:13,210 hlavičkový súbor a nie nevyhnutne v Váš súbor C, iste, keď si 171 00:07:13,210 --> 00:07:17,370 Programy sa väčšie a väčšie, takže viete, kde hľadať a to ako pre 172 00:07:17,370 --> 00:07:20,840 dokumentácia v niektorých prípadoch, alebo pre základy, ako je toto, 173 00:07:20,840 --> 00:07:22,360 Definície niektorých typov. 174 00:07:22,360 --> 00:07:25,680 >> Keby som sa tak otvára zoznam nulovú bodku c, všimnite si pár vecí. 175 00:07:25,680 --> 00:07:29,090 Obsahuje niekoľko hlavičkové súbory, väčšina ktoré sme ešte nevideli. 176 00:07:29,090 --> 00:07:31,980 Obsahuje vlastný hlavičkový súbor. 177 00:07:31,980 --> 00:07:35,200 >> A stranou, prečo je to dvakrát cituje tu, na rozdiel od uhla 178 00:07:35,200 --> 00:07:38,340 držiaky na trati, ktorá Som zdôraznil, že? 179 00:07:38,340 --> 00:07:39,180 >> STUDENT: [nepočuteľné]. 180 00:07:39,180 --> 00:07:40,460 >> SPEAKER 1: Jo, tak to je miestna súbor. 181 00:07:40,460 --> 00:07:44,300 Takže či je to miestna súbor z vašich vlastných tu na linke 15, napríklad, môžete použiť 182 00:07:44,300 --> 00:07:46,570 úvodzovky miesto z šikmých zátvorkách. 183 00:07:46,570 --> 00:07:48,270 >> Teraz je to celkom zaujímavé. 184 00:07:48,270 --> 00:07:51,830 Všimnite si, že som vyhlásil, globálne premennou v tomto programe na riadku 18 185 00:07:51,830 --> 00:07:55,910 tzv prvé, myšlienka je to bude ukazovateľ na prvý 186 00:07:55,910 --> 00:07:59,190 uzol v mojom prepojeného zoznamu, a ja som inicializovaná, na hodnotu null, pretože som 187 00:07:59,190 --> 00:08:02,310 nie je pridelené žiadne skutočné uzly len zatiaľ. 188 00:08:02,310 --> 00:08:07,570 >> Takže to znamená, obrazovo, čo sme videl pred chvíľou na obrázku ako 189 00:08:07,570 --> 00:08:10,090 že ukazovateľ na ďaleko ľavej strane. 190 00:08:10,090 --> 00:08:12,260 Takže teraz, že ukazovateľ nemá šípku. 191 00:08:12,260 --> 00:08:14,590 Je to miesto je len null. 192 00:08:14,590 --> 00:08:17,880 Ale to znamená, čo bude adresa prvý skutočný 193 00:08:17,880 --> 00:08:19,480 uzol v tomto zozname. 194 00:08:19,480 --> 00:08:22,120 Tak som sa implementácie je globálna pretože, ako uvidíte, to všetko 195 00:08:22,120 --> 00:08:25,310 Program sa v živote realizovať spájať zoznam pre mňa. 196 00:08:25,310 --> 00:08:27,050 >> Teraz mám niekoľko prototypov tu. 197 00:08:27,050 --> 00:08:31,190 Rozhodol som sa implementovať funkcie, ako je mazanie, vkladanie, vyhľadávanie a 198 00:08:31,190 --> 00:08:31,740 priechod - 199 00:08:31,740 --> 00:08:35,210 posledný byť len pešo cez zoznam, vytlačenie jeho prvky. 200 00:08:35,210 --> 00:08:36,750 A teraz je môj hlavný rutina. 201 00:08:36,750 --> 00:08:39,890 A nebudeme tráviť príliš veľa času na to, pretože to je niečo, dúfajme 202 00:08:39,890 --> 00:08:41,780 starý klobúk teraz. 203 00:08:41,780 --> 00:08:45,370 >> Chystám sa urobiť nasledovné, zatiaľ čo používateľ spolupracuje. 204 00:08:45,370 --> 00:08:47,300 Takže jedno, ja idem k tlači z tohto menu. 205 00:08:47,300 --> 00:08:49,420 A ja som ho formátovať ako čisto, ako som mohol. 206 00:08:49,420 --> 00:08:52,240 Ak používateľ zadá v jednom, to znamená, že ktoré chcete odstrániť niečo. 207 00:08:52,240 --> 00:08:54,560 V prípade, že užívateľ zadá vo dvoch, to znamená, že ktoré chcete vložiť niečo. 208 00:08:54,560 --> 00:08:55,930 A tak ďalej. 209 00:08:55,930 --> 00:08:58,270 Chystám sa potom vás vyzve potom na príkaz. 210 00:08:58,270 --> 00:08:59,300 A potom budem používať GetInt. 211 00:08:59,300 --> 00:09:02,790 >> Tak to je naozaj jednoduché menuing rozhranie, kde stačí zadať 212 00:09:02,790 --> 00:09:05,270 číslo mapovanie na jeden z týchto príkazov. 213 00:09:05,270 --> 00:09:08,730 A teraz mám pekný čistý vypínač vyhlásenie, že sa to zapnúť 214 00:09:08,730 --> 00:09:10,090 čo užívateľ napísal palcov 215 00:09:10,090 --> 00:09:12,180 A keď napísal jeden, ja zavolajte odstrániť a rozbiť. 216 00:09:12,180 --> 00:09:14,380 Ak zadali dva, ja zavolajte vložiť a zlomiť. 217 00:09:14,380 --> 00:09:16,490 >> A teraz Všimnite si, že som dal každý z nich na rovnakom riadku. 218 00:09:16,490 --> 00:09:18,360 Je to len štylistické rozhodnutia. 219 00:09:18,360 --> 00:09:20,210 Zvyčajne sme videli niečo takhle. 220 00:09:20,210 --> 00:09:23,260 Ale ja som sa rozhodol, úprimne povedané, môj program Pozrel čitateľnejší, pretože 221 00:09:23,260 --> 00:09:25,980 to bolo len štyri prípady, na vypísalo to takto. 222 00:09:25,980 --> 00:09:28,360 Úplne legitímne použitie štýlu. 223 00:09:28,360 --> 00:09:31,480 A ja budem robiť to tak dlho, kým užívateľ nezadali nulu, čo som 224 00:09:31,480 --> 00:09:33,910 rozhodol, bude znamenať, že chcú s fajčením prestať. 225 00:09:33,910 --> 00:09:36,630 >> Takže teraz upozornenie, čo som robiť tu. 226 00:09:36,630 --> 00:09:38,650 Chystám sa uvoľniť zoznamu zdanlivo. 227 00:09:38,650 --> 00:09:40,230 Ale o tom až za chvíľu. 228 00:09:40,230 --> 00:09:41,640 Poďme si najprv spustiť tento program. 229 00:09:41,640 --> 00:09:45,250 Takže mi dovoľte väčší terminál okná, bodka lomítko list 0. 230 00:09:45,250 --> 00:09:49,510 Chystám sa ísť dopredu a vložiť, písanie dva, ako je číslo 50, a teraz 231 00:09:49,510 --> 00:09:51,590 uvidíte zoznam je teraz 50. 232 00:09:51,590 --> 00:09:53,380 A môj texte len posúvať sa trochu. 233 00:09:53,380 --> 00:09:55,940 Takže teraz všimnúť zoznam obsahuje číslo 50. 234 00:09:55,940 --> 00:09:58,220 >> Poďme urobiť ďalšie vložku tým, že dvaja. 235 00:09:58,220 --> 00:10:01,630 Poďme zadajte číslo ako jeden. 236 00:10:01,630 --> 00:10:03,940 List je teraz jeden, nasleduje 50. 237 00:10:03,940 --> 00:10:06,020 Tak to je len textová reprezentácia zoznamu. 238 00:10:06,020 --> 00:10:10,550 A poďme vložiť ešte jedno číslo ako číslo 42, čo je snáď 239 00:10:10,550 --> 00:10:14,620 chystá skončiť v stredu, pretože Tento program v jednotlivých druhov sa 240 00:10:14,620 --> 00:10:16,320 prvky, ako to vloží je. 241 00:10:16,320 --> 00:10:17,220 Takže tu to máme. 242 00:10:17,220 --> 00:10:20,730 Super jednoduchý program, ktorý by absolútne použili celý rad, ale ja 243 00:10:20,730 --> 00:10:23,280 stalo, že sa pomocou prepojeného zoznamu len tak môžem dynamicky 244 00:10:23,280 --> 00:10:24,610 zväčšiť a zmenšiť ju. 245 00:10:24,610 --> 00:10:28,470 >> Takže poďme sa pozrieť pre vyhľadávanie, keď som spustiť príkaz tri, Chcem vyhľadávať 246 00:10:28,470 --> 00:10:31,040 pre, povedzme, číslom 43.. 247 00:10:31,040 --> 00:10:34,190 A nič sa zrejme našiel, pretože som sa vrátil žiadnu odpoveď. 248 00:10:34,190 --> 00:10:35,010 Tak ideme na to znova. 249 00:10:35,010 --> 00:10:35,690 Hľadať. 250 00:10:35,690 --> 00:10:39,520 Poďme hľadania 50, alebo skôr hľadanie na 42, čo je pekný 251 00:10:39,520 --> 00:10:40,850 Trochu jemnejší význam. 252 00:10:40,850 --> 00:10:42,610 A ja som našiel zmysel života tam. 253 00:10:42,610 --> 00:10:44,990 Číslo 42, pokiaľ neviete, referencie, Google ho. 254 00:10:44,990 --> 00:10:45,350 Dobrá. 255 00:10:45,350 --> 00:10:47,130 Takže to, čo tento program pre mňa urobil? 256 00:10:47,130 --> 00:10:50,660 Je to len mi dovolil vložiť tak ďaleko a hľadanie prvkov. 257 00:10:50,660 --> 00:10:53,650 >> Poďme rýchlo vpred, potom sa že funkcia sa pozrel na 258 00:10:53,650 --> 00:10:55,360 v pondelok ako ukážku. 259 00:10:55,360 --> 00:10:59,620 Takže túto funkciu, tvrdím, hľadá element v zozname ako prvé 260 00:10:59,620 --> 00:11:03,830 jeden, upozornenia užívateľa a volanie GetInt získať aktuálne int 261 00:11:03,830 --> 00:11:05,060 ktoré chcete vyhľadať. 262 00:11:05,060 --> 00:11:06,460 >> Potom nevšimol. 263 00:11:06,460 --> 00:11:10,690 Chystám sa vytvoriť dočasnú premennú v súlade s názvom 188 ukazovateľ - 264 00:11:10,690 --> 00:11:11,270 PTR - 265 00:11:11,270 --> 00:11:12,440 mohla zavolať tomu nič. 266 00:11:12,440 --> 00:11:16,140 A je to ukazovateľ na uzol pretože som povedal, že uzol *. 267 00:11:16,140 --> 00:11:19,900 A ja inicializácia je rovná najprv tak, že som skutočne mať svoju 268 00:11:19,900 --> 00:11:22,860 prstom, aby som tak povedal, na veľmi Prvý prvok zoznamu. 269 00:11:22,860 --> 00:11:27,460 Takže ak moja pravá ruka je tu PTR som ukazuje na rovnakú vec, že ​​prvý 270 00:11:27,460 --> 00:11:28,670 ukazuje na. 271 00:11:28,670 --> 00:11:31,430 >> Takže teraz späť v kóde, čo sa bude diať ďalej - 272 00:11:31,430 --> 00:11:35,070 je to spoločný vzor, ​​keď iterácie cez štruktúry, ako 273 00:11:35,070 --> 00:11:35,970 spájať zoznam. 274 00:11:35,970 --> 00:11:40,410 Chystám sa urobiť nasledovné, zatiaľ čo ukazovateľ nie je rovné null Takže zatiaľ čo 275 00:11:40,410 --> 00:11:47,530 môj prst neukazuje na nejaké null hodnota, ak je ukazovateľ šípka n sa rovná n 276 00:11:47,530 --> 00:11:52,290 Sme si všimnete ako prvé, že n je to, čo Užívateľ napísal v prepočte GetInts zavolať tady. 277 00:11:52,290 --> 00:11:54,280 >> A ukazovateľ šípka n znamená čo? 278 00:11:54,280 --> 00:11:59,020 No, ak sa vrátime k obrázku tu keď mám prst ukazujúci na 279 00:11:59,020 --> 00:12:02,960 že prvý uzol obsahuje deväť, Šípka v podstate znamená, že ísť do 280 00:12:02,960 --> 00:12:08,860 uzol a chytiť hodnotu pri umiestnení n, V tomto prípade sú dáta poľa s názvom n 281 00:12:08,860 --> 00:12:14,120 >> Ako stranou - a videli sme to ešte pred pár týždne, keď sa niekto opýtal - 282 00:12:14,120 --> 00:12:18,840 táto syntax je nový, ale to nie je nám sily, ktoré sme 283 00:12:18,840 --> 00:12:20,040 už nemalo. 284 00:12:20,040 --> 00:12:25,325 Čo to bolo za výraz ekvivalentná k použitie bodka zápis a hviezda pár 285 00:12:25,325 --> 00:12:29,490 týždne, keď sme zlúpnuť táto vrstva trochu predčasne? 286 00:12:29,490 --> 00:12:31,780 >> STUDENT: [nepočuteľné]. 287 00:12:31,780 --> 00:12:38,880 >> SPEAKER 1: Presne tak, je to hviezda, a potom je to hviezda bodka n, s 288 00:12:38,880 --> 00:12:41,930 zátvorky tu, ktorý vyzerá, Úprimne povedané, myslím, že veľa 289 00:12:41,930 --> 00:12:43,320 viac tajomné čítať. 290 00:12:43,320 --> 00:12:46,270 Ale hviezda ukazovateľ, ako vždy, znamená ísť. 291 00:12:46,270 --> 00:12:49,090 A akonáhle ste tam, aké údaje Pole chceš prístup? 292 00:12:49,090 --> 00:12:52,730 No použiť bodka notáciu pre prístup struct dátové polia, a ja 293 00:12:52,730 --> 00:12:54,140 konkrétne chcete n 294 00:12:54,140 --> 00:12:56,240 >> Úprimne povedané, povedal by som to je jednoducho ťažšie čítať. 295 00:12:56,240 --> 00:12:58,080 Je to ťažšie si spomenúť, kde sa zátvorky idú, 296 00:12:58,080 --> 00:12:59,030 hviezda a to všetko. 297 00:12:59,030 --> 00:13:02,150 Aby celý svet prijal niektoré syntaktické cukor, aby som tak povedal. 298 00:13:02,150 --> 00:13:04,740 Len sexy spôsob, ako povedať, To je ekvivalentné, a 299 00:13:04,740 --> 00:13:05,970 možno viac intuitívne. 300 00:13:05,970 --> 00:13:09,600 Je-li ukazovateľ je skutočne ukazovateľ, znamená notácie šípky ísť a nájsť 301 00:13:09,600 --> 00:13:11,890 pole je v tomto prípade tzv n 302 00:13:11,890 --> 00:13:13,660 >> Takže ak ju nájdem, všimnite si, čo robím. 303 00:13:13,660 --> 00:13:17,430 Jednoducho vytlačiť, našiel som percent ia zapojíte hodnotou pre daný int. 304 00:13:17,430 --> 00:13:20,730 Nazval som spať po dobu jednej sekundy, len aby druhu pauzy vecí na obrazovke 305 00:13:20,730 --> 00:13:22,900 poskytujú užívateľovi druhej absorbovať čo sa práve stalo. 306 00:13:22,900 --> 00:13:24,290 A potom som sa zlomiť. 307 00:13:24,290 --> 00:13:26,330 Inak, čo mám robiť? 308 00:13:26,330 --> 00:13:30,960 Aktualizovať ukazovatele rovná ukazovateľ šípku vedľa. 309 00:13:30,960 --> 00:13:35,840 >> Tak aby bolo jasno, to znamená ísť tam cez môj old-school notácie. 310 00:13:35,840 --> 00:13:39,580 Takže to znamená len ísť do čohokoľvek ste ukázal na, ktoré veľmi 311 00:13:39,580 --> 00:13:43,660 Prvým prípadom je, že som ukázal na struct s deviatimi v ňom. 312 00:13:43,660 --> 00:13:44,510 Tak som šiel tam. 313 00:13:44,510 --> 00:13:47,880 A potom bodka notácie znamená, získať hodnotu na ďalšie. 314 00:13:47,880 --> 00:13:50,470 >> Ale hodnota, a to aj keď je čerpané ako úzky, len čí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 riadok kódu, či už napísal takhle viac zložitejšie 317 00:13:55,670 --> 00:14:00,190 spôsobom, alebo ako je to, o niečo viac intuitívny spôsob, jednoducho znamená pohnúť rukou 318 00:14:00,190 --> 00:14:03,460 z prvého uzla na ďalšie, a potom ďalší, a potom 319 00:14:03,460 --> 00:14:05,320 ďalšie, a tak ďalej. 320 00:14:05,320 --> 00:14:09,920 >> Takže nebudeme bývať na strane druhej implementácia vkladanie a mazanie 321 00:14:09,920 --> 00:14:14,030 a priechod, z ktorých prvé dva ktoré sú pomerne zapojiť. 322 00:14:14,030 --> 00:14:17,010 A myslím, že je to celkom jednoduché sa dostať stratil, keď robí to ústne. 323 00:14:17,010 --> 00:14:19,890 Ale to, čo môžeme urobiť, je tu pokusu o stanovenie 324 00:14:19,890 --> 00:14:21,640 najlepšie urobiť to vizuálne. 325 00:14:21,640 --> 00:14:24,800 Pretože by som navrhoval, že ak by sme Chcem vložiť prvky do tohto 326 00:14:24,800 --> 00:14:26,680 Existujúci zoznam, ktorý má päť prvkov - 327 00:14:26,680 --> 00:14:29,530 9, 17, 22, 26, a 33 - 328 00:14:29,530 --> 00:14:33,300 Keby som mal ísť na vykonanie tohto v kód, musím zvážiť, ako ísť 329 00:14:33,300 --> 00:14:34,160 o robiť. 330 00:14:34,160 --> 00:14:37,720 >> A ja by som navrhnúť, pričom dieťa kroky pričom v tomto prípade mám na mysli, aké sú 331 00:14:37,720 --> 00:14:41,090 možných scenárov, ktoré sme stretnúť všeobecne? 332 00:14:41,090 --> 00:14:44,120 Pri vykonávaní vložka pre prepojenú zoznam, to je náhodou 333 00:14:44,120 --> 00:14:46,090 Konkrétnym príkladom veľkosti päť. 334 00:14:46,090 --> 00:14:50,420 No, ak chcete vložiť číslo, radi hovoria, že číslo jedna, a 335 00:14:50,420 --> 00:14:53,380 udržiavanie zoradené objednávky, kde samozrejme robí číslo jedna potreba 336 00:14:53,380 --> 00:14:55,686 ísť v tomto konkrétnom príklade? 337 00:14:55,686 --> 00:14:56,840 Rovnako ako na začiatku. 338 00:14:56,840 --> 00:15:00,030 >> Ale čo je zaujímavé je, že Ak chcete vložiť jeden do toho 339 00:15:00,030 --> 00:15:04,100 zoznam, čo potrebuje špeciálny ukazovateľ aktualizovať zrejme? 340 00:15:04,100 --> 00:15:04,610 Prvý. 341 00:15:04,610 --> 00:15:07,830 Takže by som si dovolil tvrdiť, toto je prvý prípad že by sme mohli chcieť, aby zvážila, 342 00:15:07,830 --> 00:15:11,140 scenár zahŕňajúci vkladanie na na začiatku zoznamu. 343 00:15:11,140 --> 00:15:15,400 >> Poďme trhať off možno tak jednoduché, alebo dokonca jednoduchší prípad, relatívne vzaté. 344 00:15:15,400 --> 00:15:18,110 Dajme tomu, že chcete vložiť číslo 35 v zoradení poradí. 345 00:15:18,110 --> 00:15:20,600 To samozrejme patrí tam. 346 00:15:20,600 --> 00:15:25,320 Takže to, čo ukazovateľ zrejme bude musia byť aktualizované v tomto prípade? 347 00:15:25,320 --> 00:15:30,060 34 je ukazovateľ stále nie je null ale adresa struct 348 00:15:30,060 --> 00:15:31,800 obsahujúce číslo 35. 349 00:15:31,800 --> 00:15:32,750 Tak to je prípad dvoch. 350 00:15:32,750 --> 00:15:36,190 Tak už som trochu kvantizácia koľko práce musím urobiť tu. 351 00:15:36,190 --> 00:15:39,880 >> A konečne zrejmé, prostredný prípad naozaj, v stredu, keď chcem 352 00:15:39,880 --> 00:15:45,870 vložiť niečo ako, povedzme 23, ktorá vedie medzi 23 a 26, ale 353 00:15:45,870 --> 00:15:48,680 teraz sa veci trochu viac podieľa pretože to, čo 354 00:15:48,680 --> 00:15:52,800 ukazovateľa je treba zmeniť? 355 00:15:52,800 --> 00:15:56,680 Tak 22 samozrejme je potrebné zmeniť pretože nemôže odkazovať na 26 už nie. 356 00:15:56,680 --> 00:16:00,320 Že je potrebné, aby odkazoval na nový uzol, ktorý Budem sa musieť rozdeliť na telefónnom čísle 357 00:16:00,320 --> 00:16:01,770 malloc alebo iným ekvivalentným. 358 00:16:01,770 --> 00:16:05,990 >> Ale potom som tiež potrebovať nový uzol, 23 V tomto prípade, aby sa jej ukazovateľ 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 poradí úkonov tu. 362 00:16:10,380 --> 00:16:13,410 Pretože keď som to hlúpo a ja napríklad od začiatku roka 363 00:16:13,410 --> 00:16:16,040 zoznam, a mojím cieľom je, vložiť 23. 364 00:16:16,040 --> 00:16:18,610 A ja som skontrolovať, to patrí Tu, v blízkosti deviatich? 365 00:16:18,610 --> 00:16:18,950 Nie. 366 00:16:18,950 --> 00:16:20,670 Znamená to sem patrí, popri 17? 367 00:16:20,670 --> 00:16:20,940 Nie. 368 00:16:20,940 --> 00:16:22,530 Má to sem patrí popri 22? 369 00:16:22,530 --> 00:16:23,300 Áno. 370 00:16:23,300 --> 00:16:26,400 >> Teraz, keď som hlúpy tu, a nie myslí si, až by som mohol 371 00:16:26,400 --> 00:16:28,320 prideliť môj nový uzol 23. 372 00:16:28,320 --> 00:16:32,080 By som mohol aktualizovať ukazovateľ z uzol s názvom 22, smerujúce 373 00:16:32,080 --> 00:16:33,080 že na nový uzol. 374 00:16:33,080 --> 00:16:36,140 A potom to, čo mám aktualizovať Nový uzol je ukazovateľ, že? 375 00:16:36,140 --> 00:16:38,120 >> STUDENT: [nepočuteľné]. 376 00:16:38,120 --> 00:16:38,385 >> SPEAKER 1: Presne tak. 377 00:16:38,385 --> 00:16:39,710 Ukázal na 26 rokov. 378 00:16:39,710 --> 00:16:45,590 Ale Dammit keby som nemal už aktualizovať 22 je ukazovateľ ukazovať na toho chlapa, a 379 00:16:45,590 --> 00:16:48,260 teraz mám siroty, zvyšok zoznamu, aby som tak povedal. 380 00:16:48,260 --> 00:16:52,140 Takže poradí operácií tu bude dôležité. 381 00:16:52,140 --> 00:16:55,100 >> K tomu by som mohol ukradnúť, povedzme, šesť dobrovoľníkov. 382 00:16:55,100 --> 00:16:57,650 A uvidíme, či môžeme to urobiť vizuálne namiesto kódu ručičiek. 383 00:16:57,650 --> 00:16:59,330 A máme nejaké krásne stres lopty pre vás dnes. 384 00:16:59,330 --> 00:17:02,510 OK, ako sa o jeden, dva, vo späť - na konci tam. 385 00:17:02,510 --> 00:17:04,530 tri, štyri, obaja chlapci na konci. 386 00:17:04,530 --> 00:17:05,579 A päť, šesť. 387 00:17:05,579 --> 00:17:05,839 Iste. 388 00:17:05,839 --> 00:17:06,450 Päť a šesť. 389 00:17:06,450 --> 00:17:08,390 Dobre a my sa na vás nabudúce. 390 00:17:08,390 --> 00:17:09,640 Dobre, poď hore. 391 00:17:09,640 --> 00:17:12,010 392 00:17:12,010 --> 00:17:14,819 >> Dobre, keď už si tu prvýkrát, by ste chceli byť tým, kto nešikovne 393 00:17:14,819 --> 00:17:16,119 v skle Google tu? 394 00:17:16,119 --> 00:17:19,075 Dobre, 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é ísť. 397 00:17:24,589 --> 00:17:27,950 >> Dobre, takže ak vy môžete prísť tu som vopred pripravené 398 00:17:27,950 --> 00:17:30,110 niektoré čísla. 399 00:17:30,110 --> 00:17:31,240 Dobre, poď sem. 400 00:17:31,240 --> 00:17:33,440 A prečo nejdeš trochu ďalej týmto spôsobom. 401 00:17:33,440 --> 00:17:35,520 A pozrime sa, ako sa voláš, so sklenený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 prvý, a to doslova. 405 00:17:38,380 --> 00:17:40,580 Takže budeme posielať do konca obdobia. 406 00:17:40,580 --> 00:17:41,670 Dobre, a vaše meno? 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 byť číslo deväť. 409 00:17:44,530 --> 00:17:46,700 Takže ak budete chcieť sledovať Ben týmto spôsobom. 410 00:17:46,700 --> 00:17:47,010 >> STUDENT: Jill. 411 00:17:47,010 --> 00:17:49,630 >> SPEAKER 1: Jill, budete mať 17, ktorá, ak by som to urobil viac 412 00:17:49,630 --> 00:17:51,260 inteligentne, musel by som začal na druhom konci. 413 00:17:51,260 --> 00:17:52,370 Môžete ísť tadiaľ. 414 00:17:52,370 --> 00:17:53,030 22. 415 00:17:53,030 --> 00:17:53,670 A vy ste? 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 meno? 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 potom konečne. 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 poď sem. 425 00:18:03,920 --> 00:18:06,360 >> Dobre, takže perfektné radené objednať už. 426 00:18:06,360 --> 00:18:09,600 A poďme ďalej, a to takže môžeme naozaj - 427 00:18:09,600 --> 00:18:11,720 Ben si len trochu hľadať von nikde tam. 428 00:18:11,720 --> 00:18:15,670 OK, takže poďme ďalej, a líči to použitie zbrane, rovnako ako ja, presne, 429 00:18:15,670 --> 00:18:16,250 čo sa deje. 430 00:18:16,250 --> 00:18:19,540 Takže choďte do toho a dať sami si noha alebo dva medzi sebou. 431 00:18:19,540 --> 00:18:22,900 A choďte do toho a pritom s jednou rukou na ktokoľvek, mali by ste sa ukázal na 432 00:18:22,900 --> 00:18:23,470 na základe tohto. 433 00:18:23,470 --> 00:18:25,890 A ak ste null len bod priamo na podlahu. 434 00:18:25,890 --> 00:18:27,690 OK, tak dobre. 435 00:18:27,690 --> 00:18:32,290 >> Takže teraz máme prepojený zoznam, a dovoľte mi, aby som navrhnúť, že budem hrať rolu 436 00:18:32,290 --> 00:18:35,110 PTR, tak som sa neobťažoval vykonávanie tohto okolia. 437 00:18:35,110 --> 00:18:37,830 A potom - niekto hlúpy konvencie - môžete volať to, čo chcete - 438 00:18:37,830 --> 00:18:39,800 predchodca ukazovateľ, pred ukazovateľ - 439 00:18:39,800 --> 00:18:43,930 je to len prezývka sme dali v náš ukážkový kód k mojej ľavej ruke. 440 00:18:43,930 --> 00:18:47,240 Na druhej strane, ktorá bude udržiavať sledovať, kto je kto v 441 00:18:47,240 --> 00:18:48,400 nasledujúce scenáre. 442 00:18:48,400 --> 00:18:52,390 >> Takže predpokladám, najprv chcem trhať off , Že prvý príklad vkladanie, povedzme 443 00:18:52,390 --> 00:18:54,330 20, do zoznamu. 444 00:18:54,330 --> 00:18:57,160 Takže budem potrebovať niekoho, kto by stelesňujú číslo 20 pre nás. 445 00:18:57,160 --> 00:18:58,950 Tak som potrebné niekoho malloc z publika. 446 00:18:58,950 --> 00:18:59,380 Poď hore. 447 00:18:59,380 --> 00:19:00,340 Ako sa voláte? 448 00:19:00,340 --> 00:19:01,300 >> STUDENT: Brian. 449 00:19:01,300 --> 00:19:05,270 >> SPEAKER 1: Brian, v poriadku, takže musí byť uzol obsahujúci 20. 450 00:19:05,270 --> 00:19:06,810 Dobre, poď sem. 451 00:19:06,810 --> 00:19:10,025 A samozrejme, ak Brian sa patrí? 452 00:19:10,025 --> 00:19:12,190 Tak, v stredu - v skutočnosti, počkaj. 453 00:19:12,190 --> 00:19:13,420 Robíme to mimo poradia. 454 00:19:13,420 --> 00:19:17,170 Robíme to oveľa ťažšie než je potrebné, aby sa na prvom mieste. 455 00:19:17,170 --> 00:19:21,210 OK, ideme na voľný Brian a realloc Brian ako päť. 456 00:19:21,210 --> 00:19:23,680 >> OK, tak teraz chceme vložiť Brian ako päť. 457 00:19:23,680 --> 00:19:25,960 Tak poď sem vedľa Ben na chvíľu. 458 00:19:25,960 --> 00:19:28,250 A môžete povedať, pravdepodobne kde tento príbeh bude. 459 00:19:28,250 --> 00:19:30,500 Ale poďme starostlivo premyslieť, poradí úkonov. 460 00:19:30,500 --> 00:19:32,880 A je to práve táto vizuálna že sa to zoradia 461 00:19:32,880 --> 00:19:34,080 s týmto ukážkový kód. 462 00:19:34,080 --> 00:19:40,120 Tak tu som PTR ukázal najprv nie je na Bena, samo o sebe, ale bez ohľadu na 463 00:19:40,120 --> 00:19:43,245 cení, že obsahuje, čo je v tomto prípade je - ako sa volá? 464 00:19:43,245 --> 00:19:43,670 >> STUDENT: Jason. 465 00:19:43,670 --> 00:19:47,350 >> SPEAKER 1: Jason, tak ako Ben a ja sme ukázal na Jasona v tomto okamihu. 466 00:19:47,350 --> 00:19:49,700 Takže teraz musím zistiť, kde sa Brian patrí? 467 00:19:49,700 --> 00:19:53,500 Takže jediné, čo mám prístup k Práve teraz je jeho n údajová položka. 468 00:19:53,500 --> 00:19:58,280 Takže budem kontrolovať, je Brian menej než Jasona? 469 00:19:58,280 --> 00:19:59,770 Odpoveď je pravda. 470 00:19:59,770 --> 00:20:03,680 >> Tak čo teraz musí stať, v správnom poradí? 471 00:20:03,680 --> 00:20:07,120 Musím aktualizovať, koľko ukazovateľov celkom v tomto príbehu? 472 00:20:07,120 --> 00:20:10,720 Kde je moja ruka stále ukazuje na Jason a vaše ruky - ak chcete 473 00:20:10,720 --> 00:20:12,930 dať ruku ako, tak nejako som neviem, otáznik. 474 00:20:12,930 --> 00:20:14,070 OK, dobre. 475 00:20:14,070 --> 00:20:15,670 >> Dobre, takže máte niekoľko kandidátov. 476 00:20:15,670 --> 00:20:20,500 Buď Ben alebo ja alebo Brian alebo Jason alebo všetci ostatní, ktoré 477 00:20:20,500 --> 00:20:21,370 ukazovateľa je treba zmeniť? 478 00:20:21,370 --> 00:20:23,260 Koľko celkom? 479 00:20:23,260 --> 00:20:24,080 >> OK, tak dva. 480 00:20:24,080 --> 00:20:27,090 Môj ukazovateľ nezáleží už pretože som len dočasné. 481 00:20:27,090 --> 00:20:31,370 Takže je to títo dvaja, pravdepodobne, ako Ben a Brian. 482 00:20:31,370 --> 00:20:34,410 Takže mi dovoľte navrhnúť, aby sme aktualizácie Ben, pretože je to prvýkrát. 483 00:20:34,410 --> 00:20:36,350 Prvý prvok tohto zoznamu sa teraz 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, čo teraz? 486 00:20:39,320 --> 00:20:41,950 487 00:20:41,950 --> 00:20:43,460 >> Kto dostane ukázal na koho? 488 00:20:43,460 --> 00:20:44,710 >> STUDENT: [nepočuteľné]. 489 00:20:44,710 --> 00:20:46,180 >> SPEAKER 1: OK, takže Brian má ukázať na Jasona. 490 00:20:46,180 --> 00:20:48,360 Ale už som stratil prehľad o tomto ukazovateľ? 491 00:20:48,360 --> 00:20:49,980 Viem, kde je Jason? 492 00:20:49,980 --> 00:20:50,790 >> STUDENT: [nepočuteľné]. 493 00:20:50,790 --> 00:20:52,620 >> SPEAKER 1: ja, pretože som dočasný ukazovateľ. 494 00:20:52,620 --> 00:20:55,110 A pravdepodobne som sa nezmenil ukázať na nový uzol. 495 00:20:55,110 --> 00:20:58,300 Takže môžeme jednoducho Brian bod na toho, kto mi ukázal na. 496 00:20:58,300 --> 00:20:59,000 A sme hotoví. 497 00:20:59,000 --> 00:21:01,890 Tak jeden prípad, vo vloženie na začiatku zoznamu. 498 00:21:01,890 --> 00:21:02,950 Tam boli dva hlavné kroky. 499 00:21:02,950 --> 00:21:06,750 Po prvé, musíme aktualizovať Bena, a potom musíme tiež aktualizovať Briana. 500 00:21:06,750 --> 00:21:09,230 A potom nemám obťažovať traipsing cez zvyšok 501 00:21:09,230 --> 00:21:12,680 zoznam, pretože sme už našli jeho umiestnenie, pretože patril k 502 00:21:12,680 --> 00:21:14,080 vľavo od prvého prvku. 503 00:21:14,080 --> 00:21:15,400 >> Dobre, takže celkom jednoduché. 504 00:21:15,400 --> 00:21:18,110 V skutočnosti, pocit, že sme skoro takže to príliš zložité. 505 00:21:18,110 --> 00:21:20,240 Takže poďme sa odtrhnúť z konca zoznamu, a zistiť, kde 506 00:21:20,240 --> 00:21:21,380 zložitosť začína. 507 00:21:21,380 --> 00:21:24,560 Takže keď teraz som Alloc z publika. 508 00:21:24,560 --> 00:21:25,540 Každý, kto chce hrať 55? 509 00:21:25,540 --> 00:21:26,700 Tak jo, videl som svoju ruku ako prvý. 510 00:21:26,700 --> 00:21:29,620 Poď hore. 511 00:21:29,620 --> 00:21:30,030 Jo. 512 00:21:30,030 --> 00:21:31,177 Ako sa voláte? 513 00:21:31,177 --> 00:21:32,310 >> STUDENT: [nepočuteľné]. 514 00:21:32,310 --> 00:21:33,240 >> SPEAKER 1: Habata. 515 00:21:33,240 --> 00:21:33,890 OK, poď hore. 516 00:21:33,890 --> 00:21:35,730 Budete mať číslo 55. 517 00:21:35,730 --> 00:21:37,820 Takže vy, samozrejme, patrí na konci zoznamu. 518 00:21:37,820 --> 00:21:41,850 Takže poďme prehrať simuláciu so mnou bytia PTR len na chvíľu. 519 00:21:41,850 --> 00:21:44,050 Tak som prvýkrát bude ukazovať na bez ohľadu na to Ben ukázal na. 520 00:21:44,050 --> 00:21:45,900 Obaja sme ukazuje teraz na Briana. 521 00:21:45,900 --> 00:21:48,420 Takže 55 je nie menej ako päť. 522 00:21:48,420 --> 00:21:52,510 Takže budem aktualizovať tým, že som ukázal na ďalší ukazovateľ Brianovi, ktorý 523 00:21:52,510 --> 00:21:54,450 Teraz je samozrejme Jasona. 524 00:21:54,450 --> 00:21:57,310 55 je menšia ako deväť, takže Chystám sa aktualizovať PTR. 525 00:21:57,310 --> 00:21:58,890 Chystám sa aktualizovať PTR. 526 00:21:58,890 --> 00:22:02,290 Chystám sa aktualizovať PTR Budem aktualizovať PTR. 527 00:22:02,290 --> 00:22:05,060 A ja idem - hmm, čo je Vaše meno znova? 528 00:22:05,060 --> 00:22:05,560 >> STUDENT: Diana. 529 00:22:05,560 --> 00:22:09,190 >> SPEAKER 1: Diana ukazuje, samozrejme, pri nulovom s ľavou rukou. 530 00:22:09,190 --> 00:22:13,030 Takže tam, kde sa skutočne Habata patrí jasne? 531 00:22:13,030 --> 00:22:15,050 Na ľavej strane, tu. 532 00:22:15,050 --> 00:22:19,460 Tak ako mám vedieť, že ju tu Myslím, že som to pokašľal. 533 00:22:19,460 --> 00:22:22,420 Pretože to, čo je umenie PTR tento okamih v čase? 534 00:22:22,420 --> 00:22:23,240 Null. 535 00:22:23,240 --> 00:22:25,580 Takže aj keď vizuálne, môžeme samozrejme vidieť všetky z nich 536 00:22:25,580 --> 00:22:26,610 chalani tu na javisku. 537 00:22:26,610 --> 00:22:29,680 Ja som to sledoval z predchádzajúcej osoba v zozname. 538 00:22:29,680 --> 00:22:33,210 Nemám prst ukazujúci von, V tomto prípade, uzol číslo 34. 539 00:22:33,210 --> 00:22:34,760 >> Takže poďme skutočne začať to znova. 540 00:22:34,760 --> 00:22:37,560 Takže teraz vlastne nepotrebujete Druhý lokálna premenná. 541 00:22:37,560 --> 00:22:40,980 A to je to, čo uvidíte v Skutočný vzorka C kód, kde, ako som ísť, 542 00:22:40,980 --> 00:22:45,860 keď som aktualizovať pravú ruku k bodu Jason, pričom je nutné Brian zozadu, som 543 00:22:45,860 --> 00:22:51,440 lepšie začať používať ľavú ruku k aktualizovať, kde som bol, takže, ako som ísť 544 00:22:51,440 --> 00:22:52,700 pomocou tohto zoznamu - 545 00:22:52,700 --> 00:22:55,040 viac rozpačito, ako som chcel teraz tu vizuálne - 546 00:22:55,040 --> 00:22:56,740 Chystám sa dostať do koniec zoznamu. 547 00:22:56,740 --> 00:23:00,020 >> Táto ruka je ešte stále nulový, čo je celkom zbytočné, iba ukazujú 548 00:23:00,020 --> 00:23:02,980 Som jednoznačne na konci zoznamu, ale teraz aspoň to mám 549 00:23:02,980 --> 00:23:08,270 predchodca ukazovateľ tu, tak Čo teraz odovzdáva a aké ukazovatele musia 550 00:23:08,270 --> 00:23:10,150 aktualizovať? 551 00:23:10,150 --> 00:23:13,214 Čí ruka chceš prekonfigurovať prvý? 552 00:23:13,214 --> 00:23:15,190 >> STUDENT: [nepočuteľné]. 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 nasmerovať Dianin ľavý ukazovateľ na? 555 00:23:21,110 --> 00:23:23,620 Na 55, pravdepodobne tak, že sme tam vložiť. 556 00:23:23,620 --> 00:23:25,560 A kde by 55 ukazovateľ ísť? 557 00:23:25,560 --> 00:23:27,000 Nadol, čo null. 558 00:23:27,000 --> 00:23:28,890 A moje ruky, v tomto bode, nie jedno, pretože oni boli len 559 00:23:28,890 --> 00:23:30,070 dočasné premenné. 560 00:23:30,070 --> 00:23:31,030 Takže teraz sme hotoví. 561 00:23:31,030 --> 00:23:34,650 >> Takže ďalšie zložitosti tam - a že to nie je tak ťažké zaviesť, 562 00:23:34,650 --> 00:23:38,660 ale potrebujeme sekundárnu premennú, aby sa istý, že predtým, než som sa pohnúť právo 563 00:23:38,660 --> 00:23:42,140 ruka, som aktualizovať hodnotu mojej ľavici ruka, pred ukazovateľ v tomto prípade, tak 564 00:23:42,140 --> 00:23:45,860 že mám koncové ukazovatele sledovať, kde som bol. 565 00:23:45,860 --> 00:23:49,360 Teraz, ako stranou, ak si myslíte tohle cez to pocit, že je to 566 00:23:49,360 --> 00:23:51,490 Trochu nepríjemné mať na sledovanie tohto ľavej ruky. 567 00:23:51,490 --> 00:23:54,015 >> Čo by iné riešenie tohto problému boli? 568 00:23:54,015 --> 00:23:56,500 Ak ste sa dostali k redesign dáta Štruktúra hovoríme 569 00:23:56,500 --> 00:23:59,630 až teraz? 570 00:23:59,630 --> 00:24:02,690 Ak je to len trochu cíti trochu nepríjemné mať rada, dva ukazovatele 571 00:24:02,690 --> 00:24:08,430 prechádza zoznam, kto by mohol inak sa, v ideálnom svete, udržiavané 572 00:24:08,430 --> 00:24:10,160 Informácie, ktoré potrebujete? 573 00:24:10,160 --> 00:24:11,360 Jo? 574 00:24:11,360 --> 00:24:12,610 >> STUDENT: [nepočuteľné]. 575 00:24:12,610 --> 00:24:15,160 576 00:24:15,160 --> 00:24:16,150 >> SPEAKER 1: Presne tak. 577 00:24:16,150 --> 00:24:19,130 Pravá takže je to vlastne zaujímavý zárodok nápadu. 578 00:24:19,130 --> 00:24:22,470 A táto myšlienka na predchádzajúcu ukazovateľ, ukazuje na predchádzajúci prvok. 579 00:24:22,470 --> 00:24:25,580 Čo keď som stelesnený, že v zozname sám? 580 00:24:25,580 --> 00:24:27,810 A to bude ťažké si predstaviť, to bez všetkých papiera 581 00:24:27,810 --> 00:24:28,830 pádu na zem. 582 00:24:28,830 --> 00:24:31,860 Ale predpokladajme, že títo ľudia používajú ako ich rúk mať predchádzajúce 583 00:24:31,860 --> 00:24:35,950 ukazovateľ, a ďalší ukazovateľ, čím realizuje to, čo budeme hovoriť dvakrát 584 00:24:35,950 --> 00:24:36,830 spájať zoznam. 585 00:24:36,830 --> 00:24:41,090 To by mi dovoľte, aby som nejako vzad oveľa ľahšie, bez toho by ma, 586 00:24:41,090 --> 00:24:43,800 programátor, musela držať sledovať ručne - 587 00:24:43,800 --> 00:24:44,980 skutočne ručne - 588 00:24:44,980 --> 00:24:47,280 , Kde som bol predtým v zozname. 589 00:24:47,280 --> 00:24:48,110 Takže nebudeme robiť. 590 00:24:48,110 --> 00:24:50,950 Budeme držať to jednoduchý, pretože to je príde za cenu, čo je dvakrát 591 00:24:50,950 --> 00:24:53,450 veľa priestoru pre ukazovatele, ak chcete druhú. 592 00:24:53,450 --> 00:24:55,760 Ale to je naozaj spoločný dátové štruktúry známej ako 593 00:24:55,760 --> 00:24:57,410 dvojnásobne spájať zoznam. 594 00:24:57,410 --> 00:25:01,310 >> Poďme urobiť posledný príklad tu a dal títo chlapci z ich utrpenia. 595 00:25:01,310 --> 00:25:03,270 Tak malloc 20. 596 00:25:03,270 --> 00:25:05,320 Poď sa z uličky tam. 597 00:25:05,320 --> 00:25:06,280 Dobre, Ako sa voláte? 598 00:25:06,280 --> 00:25:07,440 >> STUDENT: [nepočuteľné]. 599 00:25:07,440 --> 00:25:07,855 >> SPEAKER 1: Je nám ľúto? 600 00:25:07,855 --> 00:25:08,480 >> STUDENT: [nepočuteľné]. 601 00:25:08,480 --> 00:25:09,410 >> SPEAKER 1: Demeron? 602 00:25:09,410 --> 00:25:10,230 OK poď hore. 603 00:25:10,230 --> 00:25:11,910 Tie musia byť 20. 604 00:25:11,910 --> 00:25:14,720 Tie samozrejme budú Patrí medzi 17 a 22. 605 00:25:14,720 --> 00:25:16,150 Takže dovoľte mi učiť moje lekciu. 606 00:25:16,150 --> 00:25:18,150 Chystám sa začať ukazovateľ ukázal na Briana. 607 00:25:18,150 --> 00:25:21,190 A ja budem mať ľavú ruku aktualizovať iba k Brianovi, ako som sa presunúť na 608 00:25:21,190 --> 00:25:23,600 Jason, kontrola robí 20 menej ako deväť? 609 00:25:23,600 --> 00:25:24,060 Nie. 610 00:25:24,060 --> 00:25:25,430 Je o 20 menej ako 17? 611 00:25:25,430 --> 00:25:25,880 Nie. 612 00:25:25,880 --> 00:25:27,450 Je o 20 menej ako 22? 613 00:25:27,450 --> 00:25:28,440 Áno. 614 00:25:28,440 --> 00:25:34,070 Takže to, čo ukazovátka alebo ruky je potrebné zmeniť kde to ukazuje teraz? 615 00:25:34,070 --> 00:25:37,070 >> Takže, čo môžeme urobiť 17 ukazuje na 20 rokov. 616 00:25:37,070 --> 00:25:37,860 Tak to je v poriadku. 617 00:25:37,860 --> 00:25:40,080 Kde chceme upozorniť ukazovateľ myši teraz? 618 00:25:40,080 --> 00:25:41,330 V 22. 619 00:25:41,330 --> 00:25:45,410 A my vieme, kde 22 je opäť vďaka k môjmu dočasné ukazovatele. 620 00:25:45,410 --> 00:25:46,760 Tak to je v poriadku tam. 621 00:25:46,760 --> 00:25:49,440 Takže kvôli tejto dočasné skladovanie Nechal som sledovať, kde sa všetci. 622 00:25:49,440 --> 00:25:55,055 A teraz môžete ísť do vizuálne, kde patríte, a teraz potrebujeme 1, 2, 3, 623 00:25:55,055 --> 00:25:58,410 4, 5, 6, 7, 8, 9 stres lopty, a potlesk pre 624 00:25:58,410 --> 00:25:59,770 títo chlapci, keby sme mohli. 625 00:25:59,770 --> 00:26:00,410 Dobrá práca. 626 00:26:00,410 --> 00:26:05,320 >> [APPLAUSE] 627 00:26:05,320 --> 00:26:06,330 >> SPEAKER 1: Dobre. 628 00:26:06,330 --> 00:26:09,860 A môžete držať kusy papiera ako pamiatku. 629 00:26:09,860 --> 00:26:15,930 >> Dobre, takže, verte mi, je to veľa jednoduchšie prejsť, aby sa 630 00:26:15,930 --> 00:26:17,680 ľudia, než je tomu u skutočného kódu. 631 00:26:17,680 --> 00:26:22,690 Ale to, čo nájdete za chvíľu teraz, je to rovnaké - ach, ďakujem. 632 00:26:22,690 --> 00:26:23,630 Ďakujem - 633 00:26:23,630 --> 00:26:29,360 je, že zistíte, že rovnaké údaje štruktúra, komunikačné zoznam, môže v skutočnosti 634 00:26:29,360 --> 00:26:33,200 byť použité ako stavebný blok k ešte sofistikované dátové štruktúry. 635 00:26:33,200 --> 00:26:37,620 >> A uvedomiť si taky tému tu je, že sme absolútne predstavil viac 636 00:26:37,620 --> 00:26:40,060 zložitosť do realizácie tohto algoritmu. 637 00:26:40,060 --> 00:26:43,940 Vloženie, a keď sme išli cez to, vymazanie a vyhľadávanie, je trochu 638 00:26:43,940 --> 00:26:46,660 komplikovanejšia, než sa bol s radom. 639 00:26:46,660 --> 00:26:48,040 Ale získať nejaké dynamiku. 640 00:26:48,040 --> 00:26:50,180 Dostávame adaptívne štruktúru dát. 641 00:26:50,180 --> 00:26:54,010 >> Ale opäť platíme cenu, že niektoré ďalšie zložitosť, a to ako v 642 00:26:54,010 --> 00:26:54,910 vykonávanie. 643 00:26:54,910 --> 00:26:56,750 A my sme sa vzdali náhodný prístup. 644 00:26:56,750 --> 00:27:00,450 A aby som bol úprimný, že to nie je nejaké pekné čistenie snímku môžem dať, že 645 00:27:00,450 --> 00:27:03,120 hovorí, že je tu dôvod, prečo spájať zoznam je lepšia ako pole. 646 00:27:03,120 --> 00:27:04,100 A nechať to tak. 647 00:27:04,100 --> 00:27:07,520 Pretože téma znovu objavuje teraz, aj viac v nadchádzajúcich týždňoch, je 648 00:27:07,520 --> 00:27:10,200 že to nemusí byť nutne správna odpoveď. 649 00:27:10,200 --> 00:27:13,830 >> To je dôvod, prečo máme samostatnú os dizajnu pre základné problémové okruhy. 650 00:27:13,830 --> 00:27:17,700 Bude to veľmi kontextová či chcete tieto dáta použiť 651 00:27:17,700 --> 00:27:21,750 štruktúra alebo že jeden, a to bude závisí na to, čo je pre vás z hľadiska 652 00:27:21,750 --> 00:27:24,620 zdrojov a zložitosti. 653 00:27:24,620 --> 00:27:28,830 >> Ale dovoľte mi navrhnúť, aby bola ideálna údajov štruktúra, Svätý grál, bude 654 00:27:28,830 --> 00:27:32,200 niečo, čo je konštantný čas, bez ohľadu na to, koľko vecí je 655 00:27:32,200 --> 00:27:36,940 vnútri, nebolo by úžasné, keby dátová štruktúra sa vrátil v odpovedi 656 00:27:36,940 --> 00:27:37,920 konštantný čas. 657 00:27:37,920 --> 00:27:38,330 Áno. 658 00:27:38,330 --> 00:27:40,110 Toto slovo je v obrovskej slovníka. 659 00:27:40,110 --> 00:27:41,550 Alebo nie, to slovo nie je. 660 00:27:41,550 --> 00:27:43,270 Alebo akýkoľvek taký problém tam. 661 00:27:43,270 --> 00:27:46,360 No uvidíme, či môžeme aspoň nie krok smerom k tomuto. 662 00:27:46,360 --> 00:27:50,190 >> Dovoľte mi skoncipovať novú dátovú štruktúru, ktorá môžu byť použité pre rôzne veci, 663 00:27:50,190 --> 00:27:52,260 v tomto prípade nazýva hash tabuľky. 664 00:27:52,260 --> 00:27:55,590 A tak sme vlastne späť pohľadom na poli, v tomto prípade, a 665 00:27:55,590 --> 00:28:00,550 trochu umelo, ja som to vypracované hash tabuľky ako polia s druhom 666 00:28:00,550 --> 00:28:02,810 dvojrozmerné pole - 667 00:28:02,810 --> 00:28:05,410 alebo skôr to tu zobrazený ako dva rozmerné pole - ale to je len 668 00:28:05,410 --> 00:28:10,770 pole o veľkosti 26, tak, že ak sa zavolajte pole, stolný držiak 669 00:28:10,770 --> 00:28:12,440 nula je obdĺžnik v hornej časti. 670 00:28:12,440 --> 00:28:15,090 Stolný držiak 25 je obdĺžnik v spodnej časti. 671 00:28:15,090 --> 00:28:18,620 A to je, ako by som mohol nakresliť dát štruktúra, v ktorej chcem uložiť 672 00:28:18,620 --> 00:28:19,790 Mená ľudí. 673 00:28:19,790 --> 00:28:24,370 >> Tak napríklad, a nebudem kresliť Celá vec tu na strope, keď som 674 00:28:24,370 --> 00:28:29,160 mal toto pole, ktoré som teraz bude volanie hash tabuľky, a to je opäť 675 00:28:29,160 --> 00:28:31,360 umiestnenie nula. 676 00:28:31,360 --> 00:28:34,840 Tohle je miesto jeden, a tak ďalej. 677 00:28:34,840 --> 00:28:37,880 Tvrdím, že chcem použiť tieto dáta štruktúra, v záujme diskusie 678 00:28:37,880 --> 00:28:42,600 Uloženie mien ľudí, Alice a Bob a Charlie a ďalšie podobné názvy. 679 00:28:42,600 --> 00:28:46,110 Takže myslíte, že o tom dnes rovnako ako začiatky , Povedzme, v slovníku 680 00:28:46,110 --> 00:28:47,520 s množstvom slov. 681 00:28:47,520 --> 00:28:49,435 Oni stalo, že sa mená v našom príklade tu. 682 00:28:49,435 --> 00:28:52,560 A to je príliš Germany, snáď, aby vykonáva kontrolu pravopisu, ako my 683 00:28:52,560 --> 00:28:54,400 Môžu to byť problémom nastaviť šesť. 684 00:28:54,400 --> 00:28:59,300 >> Takže ak máme rad celkovej veľkosti 26 tak, že sa jedná o umiestnenie 25. 685 00:28:59,300 --> 00:29:03,390 na dne, a tvrdím, že je Alice prvé slovo v slovníku 686 00:29:03,390 --> 00:29:07,260 Názvy, ktorých chcem vložiť do pamäte RAM, do tejto dátové štruktúry, kde sú 687 00:29:07,260 --> 00:29:12,480 inštinkt hovorí, že Alice je Názov by mal ísť 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 Ak chceme ju? 690 00:29:14,990 --> 00:29:16,200 Chceme ju v zátvorke nula, nie? 691 00:29:16,200 --> 00:29:18,280 A pre Alicu, povedzme, že nula. 692 00:29:18,280 --> 00:29:20,110 A B bude jeden, a C budú dva. 693 00:29:20,110 --> 00:29:22,600 Takže budeme písať Alicin meno tu. 694 00:29:22,600 --> 00:29:24,890 Ak sa potom vložte Bob, jeho názov pôjde tu. 695 00:29:24,890 --> 00:29:27,280 Charlie pôjde tu. 696 00:29:27,280 --> 00:29:30,500 A tak ďalej nadol Táto dátová štruktúra. 697 00:29:30,500 --> 00:29:32,090 >> Je to nádherná štruktúra dát. 698 00:29:32,090 --> 00:29:32,730 Prečo? 699 00:29:32,730 --> 00:29:37,460 No čo je časová zložitosť vložením ľudského meno do tohto 700 00:29:37,460 --> 00:29:39,850 štruktúra dát práve teraz? 701 00:29:39,850 --> 00:29:43,702 Vzhľadom k tomu, že táto tabuľka je implementovaná, naozaj ako pole. 702 00:29:43,702 --> 00:29:44,940 No, je to konštantný čas. 703 00:29:44,940 --> 00:29:45,800 To je cieľom jedného. 704 00:29:45,800 --> 00:29:46,360 Prečo? 705 00:29:46,360 --> 00:29:48,630 >> Tak, ako si zistiť, kde Alice patrí? 706 00:29:48,630 --> 00:29:51,000 Keď sa pozriete na ktoré písmeno jej mena? 707 00:29:51,000 --> 00:29:51,490 Prvý. 708 00:29:51,490 --> 00:29:54,350 A môžete sa tam dostať, keď je to reťazec, len o pohľade na povrázku 709 00:29:54,350 --> 00:29:55,200 držiak nula. 710 00:29:55,200 --> 00:29:57,110 Takže nultý znak reťazca. 711 00:29:57,110 --> 00:29:57,610 To je jednoduché. 712 00:29:57,610 --> 00:30:00,350 To sme urobili v crypto priradenie týždne. 713 00:30:00,350 --> 00:30:05,310 A potom ešte raz viete, že Alice písmeno veľké, môžeme odčítať 714 00:30:05,310 --> 00:30:08,160 off 65 alebo kapitálu je sám, že nám dáva nulu. 715 00:30:08,160 --> 00:30:10,940 Takže teraz vieme, že patrí Alice v mieste nulové. 716 00:30:10,940 --> 00:30:14,240 >> A vzhľadom k tomu ukazovateľ k týmto údajom štruktúra, nejakého druhu, ako dlho trvá 717 00:30:14,240 --> 00:30:18,840 to sa mi nájsť miesto nula v poli? 718 00:30:18,840 --> 00:30:22,080 Len jeden krok, že je to konštantná čas pretože s ľubovoľným prístupom sa 719 00:30:22,080 --> 00:30:23,780 Navrhované bol rys poľa. 720 00:30:23,780 --> 00:30:28,570 Takže v skratke, zisťuje, čo index Alice je názov, ktorý je v 721 00:30:28,570 --> 00:30:32,610 V tomto prípade je, alebo nech to jednoducho riešiť že k nule, kde B je jedna a C je 722 00:30:32,610 --> 00:30:34,900 dva, zisťuje, že z je konštantný čas. 723 00:30:34,900 --> 00:30:38,510 Musím sa pozrieť na jej prvý list, prísť na to, kde je nula 724 00:30:38,510 --> 00:30:40,460 Pole je tiež konštantná dobu. 725 00:30:40,460 --> 00:30:42,140 Takže technicky to ako dva kroky teraz. 726 00:30:42,140 --> 00:30:43,330 Ale to je stále konštantná. 727 00:30:43,330 --> 00:30:46,880 Takže hovoríme, že veľký O jednej, takže sme vložená Alicu do tejto tabuľky v 728 00:30:46,880 --> 00:30:48,440 konštantný čas. 729 00:30:48,440 --> 00:30:50,960 >> Ale samozrejme, ja som bol naivné, nie? 730 00:30:50,960 --> 00:30:53,240 Čo keď tam Aaron v triede? 731 00:30:53,240 --> 00:30:53,990 Alebo Alicia? 732 00:30:53,990 --> 00:30:57,230 Alebo nejaké iné názvy začínajúce na A. Kam ideme dať 733 00:30:57,230 --> 00:31:00,800 že človek, nie? 734 00:31:00,800 --> 00:31:03,420 Chcem povedať, teraz je tu len tri Ľudia na stole, takže možno sme 735 00:31:03,420 --> 00:31:07,490 mali dať Aaron v mieste nula jedna dva tri. 736 00:31:07,490 --> 00:31:09,480 >> Jasne, mohol som tu. 737 00:31:09,480 --> 00:31:13,350 Ale potom, keď sa snažíme vložiť do Davida tento zoznam, kde sa Dávid ísť? 738 00:31:13,350 --> 00:31:15,170 Teraz náš systém spustí vypínací nadol, nie? 739 00:31:15,170 --> 00:31:19,210 Pretože teraz David skončí tu ak Aaron je v skutočnosti tu. 740 00:31:19,210 --> 00:31:23,060 A tak sa celá táto predstava, že čistá dátová štruktúra, ktorá nám dáva 741 00:31:23,060 --> 00:31:28,010 konštantnom čase vložky už nie je konštantný čas, pretože musím 742 00:31:28,010 --> 00:31:31,240 zistiť, oh, sakra, niekto to už v mieste Alice. 743 00:31:31,240 --> 00:31:35,320 >> Dovoľte mi, aby som preskúmať zvyšok týchto údajov štruktúra, hľadať miesto dať 744 00:31:35,320 --> 00:31:37,130 niekto ako meno Aaron. 745 00:31:37,130 --> 00:31:39,390 A tak to taky začína aby sa lineárny čas. 746 00:31:39,390 --> 00:31:42,710 Navyše, ak sa chcete vyhľadať Aaron v tejto dátovej štruktúre, a 747 00:31:42,710 --> 00:31:45,430 skontrolovať, a Áronova meno tú nie. 748 00:31:45,430 --> 00:31:47,960 V ideálnom prípade by ste práve povedal Áronovi nie je v dátovej štruktúre. 749 00:31:47,960 --> 00:31:51,530 Ale ak si začnete robiť priestor pre Aaron tam, kde by boli D 750 00:31:51,530 --> 00:31:55,600 alebo E, tie, v najhoršom prípade, je nutné skontrolovať Celá štruktúra dát, vo 751 00:31:55,600 --> 00:31:59,480 takom prípade prejde do niečoho lineárne vo veľkosti tabuľky. 752 00:31:59,480 --> 00:32:00,920 >> Takže v poriadku, ja to opraviť. 753 00:32:00,920 --> 00:32:04,200 Problém je, že som mal 26 prvkov v tomto poli. 754 00:32:04,200 --> 00:32:05,000 Dovoľte mi, aby som ju zmeniť. 755 00:32:05,000 --> 00:32:06,010 Jejda. 756 00:32:06,010 --> 00:32:10,600 Dovoľte mi, aby som ho zmeniť tak, že namiesto bytia veľkosť 26 celkom, všimnite si na dno 757 00:32:10,600 --> 00:32:12,720 index sa zmení na n mínus jedna. 758 00:32:12,720 --> 00:32:16,610 Ak 26 je zjavne príliš malá pre človeka " mená, pretože tam sú tisíce 759 00:32:16,610 --> 00:32:20,830 mená na svete, jednoducho robiť na 100 alebo 1000 alebo 10000. 760 00:32:20,830 --> 00:32:22,960 Povedzme prideliť oveľa viac priestoru. 761 00:32:22,960 --> 00:32:27,230 >> Dobre, že nemusí nevyhnutne znížiť pravdepodobnosť, že nebudeme mať dva 762 00:32:27,230 --> 00:32:31,510 ľudia s názvami začínajúci a tak si to skúsiť dať 763 00:32:31,510 --> 00:32:33,120 mená na umiestnení nulu stále. 764 00:32:33,120 --> 00:32:36,850 Stále bude zrazí, čo znamená, že stále potrebujeme riešenia, aby 765 00:32:36,850 --> 00:32:41,020 Alice a Árona a Alicia a ďalšie Mená začínajúce A inde. 766 00:32:41,020 --> 00:32:43,460 Ale aký veľký problém to je? 767 00:32:43,460 --> 00:32:46,870 Čo je to pravdepodobnosť, že si majú kolízie v dátovom 768 00:32:46,870 --> 00:32:48,240 Štruktúra takto? 769 00:32:48,240 --> 00:32:52,570 >> No, dovoľte mi, aby som - vrátime sa na túto otázku tu. 770 00:32:52,570 --> 00:32:55,530 A pozrite sa na to, ako by sme mohli riešiť ako prvé. 771 00:32:55,530 --> 00:32:58,480 Dovoľte mi, aby som vytiahnuť tento návrh tu. 772 00:32:58,480 --> 00:33:02,020 To, čo sme práve popísal, je algoritmus, heuristický tzv lineárne 773 00:33:02,020 --> 00:33:05,030 snímanie, kedy, ak ste sa pokúsili vložiť niečo, čo tu v týchto údajov 774 00:33:05,030 --> 00:33:08,920 štruktúra, ktorá sa nazýva hash tabuľky, a neexistuje žiadny priestor tam, 775 00:33:08,920 --> 00:33:12,000 skutočne skúmať štruktúru dát kontrola, je to k dispozícii? 776 00:33:12,000 --> 00:33:13,430 Je to k dispozícii, je to k dispozícii? 777 00:33:13,430 --> 00:33:13,980 Je to k dispozícii? 778 00:33:13,980 --> 00:33:17,550 A keď konečne je vložíte meno, ktoré ste pôvodne zamýšľal 779 00:33:17,550 --> 00:33:19,370 inde v tomto mieste. 780 00:33:19,370 --> 00:33:23,360 Ale v najhoršom prípade iba bod môže byť veľmi spodné údajov 781 00:33:23,360 --> 00:33:25,090 štruktúra, veľmi koniec poľa. 782 00:33:25,090 --> 00:33:30,130 >> Takže lineárne sondy, v najhoršom prípade, prejde do lineárny algoritmus, kde 783 00:33:30,130 --> 00:33:34,500 Aaron, keď sa stane byť vložený posledný v tejto dátovej štruktúre, mohol by 784 00:33:34,500 --> 00:33:39,540 kolidovať s týmto prvom mieste, ale potom koniec smola v samom závere. 785 00:33:39,540 --> 00:33:43,940 Takže to nie je konštantná Doba svätý grál pre nás. 786 00:33:43,940 --> 00:33:47,650 Tento prístup, vkladanie prvkov do dátová štruktúra nazýva hash 787 00:33:47,650 --> 00:33:52,050 tabuľka sa nezdá byť konštantný čas aspoň nie vo všeobecnom prípade. 788 00:33:52,050 --> 00:33:54,000 To môže prejsť do niečoho lineárne. 789 00:33:54,000 --> 00:33:56,970 >> Takže čo keby sme vyriešiť kolízie trochu inak? 790 00:33:56,970 --> 00:34:00,740 Tak tu je to zložitejšie priblížiť to, čo je ešte 791 00:34:00,740 --> 00:34:02,800 tzv hash tabuľky. 792 00:34:02,800 --> 00:34:05,890 A hash, ako stranou, čo Mám na mysli, je index, ktorý 793 00:34:05,890 --> 00:34:07,070 Som sa zmienil predtým. 794 00:34:07,070 --> 00:34:09,810 Ak chcete niečo hash môže byť myšlienka ako slovesá. 795 00:34:09,810 --> 00:34:13,690 >> Takže ak hash Alice je meno, hašovacej funkcie, aby som tak povedal, 796 00:34:13,690 --> 00:34:14,710 by mala vrátiť číslo. 797 00:34:14,710 --> 00:34:18,199 V tomto prípade je nula, ak sa patrí na umiestnenie nula, jedna, ak sa patrí na 798 00:34:18,199 --> 00:34:20,000 polohy na jednej, a tak ďalej. 799 00:34:20,000 --> 00:34:24,360 Takže moja hashovacie funkcie bolo doteraz Super jednoduché, len pri pohľade na 800 00:34:24,360 --> 00:34:26,159 Prvé písmeno v niečí meno. 801 00:34:26,159 --> 00:34:29,090 Ale hašovacej funkcie berie ako vstup niektorých údaj, 802 00:34:29,090 --> 00:34:30,210 string, int, čokoľvek. 803 00:34:30,210 --> 00:34:32,239 A to vypľuje typicky číslo. 804 00:34:32,239 --> 00:34:35,739 A to číslo je, že dáta, kedy element patrí do dátovej štruktúry 805 00:34:35,739 --> 00:34:37,800 známy tu ako tabuľky hash. 806 00:34:37,800 --> 00:34:41,400 >> Tak len intuitívne, to je mierne odlišný kontext. 807 00:34:41,400 --> 00:34:44,170 Toto vlastne odvoláva na príklad zahŕňajúce narodeniny, kde 808 00:34:44,170 --> 00:34:46,850 tu môže byť toľko, koľko 31 dní v mesiaci. 809 00:34:46,850 --> 00:34:52,239 Ale čo sa táto osoba rozhodne robiť v prípade nehody? 810 00:34:52,239 --> 00:34:55,304 Kontext teraz byť, nie kolízii mená, ale kolízie narodenín, 811 00:34:55,304 --> 00:35:00,760 keď sa dvaja ľudia majú narodeniny v rovnaký deň na 2. októbra, napríklad. 812 00:35:00,760 --> 00:35:02,120 >> STUDENT: [nepočuteľné]. 813 00:35:02,120 --> 00:35:05,010 >> Reproduktor 1: Jo, tak tu máme využitie prepojených zoznamov. 814 00:35:05,010 --> 00:35:07,830 Takže to vyzerá trochu inak než sme nakreslil predtým. 815 00:35:07,830 --> 00:35:10,790 Ale zdá sa, že na pole na ľavej strane. 816 00:35:10,790 --> 00:35:13,230 To je jeden index, a to bez osobitný dôvod. 817 00:35:13,230 --> 00:35:14,630 Ale je to stále poľa. 818 00:35:14,630 --> 00:35:16,160 Je to pole ukazovateľov. 819 00:35:16,160 --> 00:35:20,670 A každý z týchto prvkov, z ktorých každý z Tieto kruhy alebo lomky - slash 820 00:35:20,670 --> 00:35:23,970 predstavuje null - každá z týchto ukazovatele sa zrejme ukazuje na 821 00:35:23,970 --> 00:35:25,730 čo dátová štruktúra? 822 00:35:25,730 --> 00:35:26,890 Spájať zoznam. 823 00:35:26,890 --> 00:35:30,530 >> Takže teraz máme schopnosť pevný kód do nášho programu 824 00:35:30,530 --> 00:35:32,010 veľkosť tabuľky. 825 00:35:32,010 --> 00:35:35,360 V tomto prípade vieme, že nikdy viac ako 31 dní v mesiaci. 826 00:35:35,360 --> 00:35:38,480 Tak ťažké kódovanie hodnoty, ako je 31 rozumné v tomto kontexte. 827 00:35:38,480 --> 00:35:42,700 V súvislosti s názvami, pevný kódovanie 26 nie je od veci, že ľudia to 828 00:35:42,700 --> 00:35:46,340 iba názvy začínajú, napríklad, abeceda zapojenie do Z. 829 00:35:46,340 --> 00:35:50,180 >> Môžeme sa napchať ich všetky do týchto údajov štruktúra tak dlho, ako keď sme si 830 00:35:50,180 --> 00:35:55,330 kolízie, nemáme dať mená tu, namiesto toho, že z týchto buniek 831 00:35:55,330 --> 00:36:00,270 nie ako reťazce samotné, ale odkazy na, napríklad, Alice. 832 00:36:00,270 --> 00:36:03,660 A potom Alice môže mať iný ukazovateľ na iný názov začína 833 00:36:03,660 --> 00:36:06,150 A. A Bob sa vlastne deje tu. 834 00:36:06,150 --> 00:36:10,850 >> A ak je tu ďalší meno začínajúce pomocou B, on skončí tu. 835 00:36:10,850 --> 00:36:15,070 A tak každý z prvkov tohto stolný dva, keď sme navrhli tento 836 00:36:15,070 --> 00:36:17,350 trochu viac chytro - 837 00:36:17,350 --> 00:36:18,125 no - 838 00:36:18,125 --> 00:36:22,950 keď sme navrhli to trochu viac chytro, sa teraz stáva adaptívne údajov 839 00:36:22,950 --> 00:36:27,720 štruktúra, kde neexistuje žiadny pevný limit na tom, koľko prvkov môžete vložiť 840 00:36:27,720 --> 00:36:30,700 do nej, pretože ak máte kolízie, to je v poriadku. 841 00:36:30,700 --> 00:36:34,690 Len do toho pustite a pripojiť ju ku čo sme videli trochu bol ešte pred 842 00:36:34,690 --> 00:36:38,290 známy ako prepojeného zoznamu. 843 00:36:38,290 --> 00:36:39,690 >> Tak poďme pauzu len na chvíľu. 844 00:36:39,690 --> 00:36:42,570 Čo je pravdepodobnosť kolízie na prvom mieste? 845 00:36:42,570 --> 00:36:45,480 Dobre, možno som premýšľal nad, možno Som na inžinierske tento problém, 846 00:36:45,480 --> 00:36:46,370 pretože viete čo? 847 00:36:46,370 --> 00:36:49,070 Áno, môžem prísť s ľubovoľnou Príklady z vrcholu mojej hlavy, ako je 848 00:36:49,070 --> 00:36:52,870 Allison a Aaron, ale v skutočnosti, vzhľadom k rovnomerné rozloženie 849 00:36:52,870 --> 00:36:56,990 vstupy, to je nejaký náhodný vkladanie do dátovej štruktúry, čo je naozaj 850 00:36:56,990 --> 00:36:58,580 pravdepodobnosť kolízie? 851 00:36:58,580 --> 00:37:01,670 Tak sa ukázalo, že je to vlastne Super vysoká. 852 00:37:01,670 --> 00:37:03,850 Dovoľte mi, aby som zovšeobecniť Problém je v tom, ako to. 853 00:37:03,850 --> 00:37:08,890 >> Tak v miestnosti n CS50 študenti, čo je pravdepodobnosť, že aspoň 854 00:37:08,890 --> 00:37:11,010 dvaja študenti v miestnosti majú narodeniny v rovnaký deň? 855 00:37:11,010 --> 00:37:13,346 Takže to, čo. niekoľko Hund - 856 00:37:13,346 --> 00:37:16,790 200, 300 ľudí tu a niekoľko stoviek ľudí doma dnes. 857 00:37:16,790 --> 00:37:20,670 Takže ak ste sa chcel spýtať sami seba, čo je pravdepodobnosť, že dve osoby 858 00:37:20,670 --> 00:37:23,930 v tejto miestnosti má narodeniny v rovnaký deň, môžeme to vyriešiť. 859 00:37:23,930 --> 00:37:26,250 A tvrdím, v skutočnosti existujú dva ľudia s rovnakým narodeniny. 860 00:37:26,250 --> 00:37:29,560 >> Napríklad, má niekto má dnes narodeniny? 861 00:37:29,560 --> 00:37:31,340 Včera? 862 00:37:31,340 --> 00:37:32,590 Zajtra? 863 00:37:32,590 --> 00:37:35,980 Dobre, takže to vyzerá, budem musieť urobiť 363 alebo tak viac 864 00:37:35,980 --> 00:37:39,500 Časy skutočne zistiť, ak máme kolízii. 865 00:37:39,500 --> 00:37:42,350 Alebo by sme to mohli urobiť matematicky skôr než zdĺhavo 866 00:37:42,350 --> 00:37:43,200 ako to urobiť. 867 00:37:43,200 --> 00:37:44,500 A navrhujem nasledovné. 868 00:37:44,500 --> 00:37:48,740 >> Takže navrhujem, že by sme mohli modelovať pravdepodobnosť, že dve osoby, ktoré majú 869 00:37:48,740 --> 00:37:55,320 narodeniny v rovnaký deň ako pravdepodobnosť 1 mínus pravdepodobnosť nikto s 870 00:37:55,320 --> 00:37:56,290 narodeniny v rovnaký deň. 871 00:37:56,290 --> 00:37:59,960 Takže si to, a je to len ozdobný spôsob, ako písať to, pre 872 00:37:59,960 --> 00:38:03,090 prvá osoba v izbe, on alebo ona môže mať jeden z možných 873 00:38:03,090 --> 00:38:07,370 narodeniny za predpokladu, že 365 dní v roku, s ospravedlnením osobám s 874 00:38:07,370 --> 00:38:08,760 29.února najlepšie. 875 00:38:08,760 --> 00:38:13,470 >> Takže prvý človek v tejto miestnosti je zadarmo mať ľubovoľný počet narodeniny 876 00:38:13,470 --> 00:38:18,280 zo 365 možností tak, že budeme to robiť 365 delené 365, 877 00:38:18,280 --> 00:38:18,990 čo je jedna. 878 00:38:18,990 --> 00:38:22,700 Ďalšia osoba v miestnosti, ak je cieľom je, aby sa zabránilo kolízii, môže len 879 00:38:22,700 --> 00:38:26,460 majú jeho životnému jubileu, ako mnoho rôznych 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ýraze je v podstate tým, že matematiku pre nás 882 00:38:31,430 --> 00:38:33,460 odpočítaním off jeden možný deň. 883 00:38:33,460 --> 00:38:36,390 A potom ďalší deň, ďalší deň, Nasledujúci deň sa na celkovom počte 884 00:38:36,390 --> 00:38:38,100 ľudí v miestnosti. 885 00:38:38,100 --> 00:38:41,290 >> A keď sme potom zváži, čo potom je pravdepodobnosť, nie každý má 886 00:38:41,290 --> 00:38:45,265 Unikátny narodenín, ale opäť mínus 1 to, čo dostaneme, je výrazom 887 00:38:45,265 --> 00:38:47,810 ktoré môžu veľmi fancifully vyzerať takto. 888 00:38:47,810 --> 00:38:50,330 Ale je to oveľa zaujímavejšie pozrieť sa na vizuálne. 889 00:38:50,330 --> 00:38:55,120 Toto je tabuľka, kde na osi x je počet ľudí v miestnosti, 890 00:38:55,120 --> 00:38:56,180 počet narodenín. 891 00:38:56,180 --> 00:38:59,840 Na osi y je pravdepodobnosť, kolízie, dvaja ľudia 892 00:38:59,840 --> 00:39:01,230 majú narodeniny v rovnaký deň. 893 00:39:01,230 --> 00:39:05,020 >> A stánok s jedlom z tejto krivky je že akonáhle sa dostanete do páči 40 894 00:39:05,020 --> 00:39:11,110 študenti, že ste sa na 90% pravdepodobnosťou combinatorically dvoch 895 00:39:11,110 --> 00:39:13,550 osoby alebo viac, ktoré majú rovnako najlepší. 896 00:39:13,550 --> 00:39:18,600 A akonáhle sa dostanete páči 58 ľuďom, že je to takmer 100% šanca dvoch 897 00:39:18,600 --> 00:39:21,310 ľudia v miestnosti sa bude musieť narodeniny v rovnaký deň, aj keď je 898 00:39:21,310 --> 00:39:26,650 365 alebo 366 možných vedierka a Iba 58 ľudí v miestnosti. 899 00:39:26,650 --> 00:39:29,900 Len štatisticky budete pravdepodobne sa kolíziám, čo v skratke 900 00:39:29,900 --> 00:39:31,810 motivuje túto diskusiu. 901 00:39:31,810 --> 00:39:35,890 Že aj keď sa dostaneme fantázie tu, a začať s takýmito reťazami, sme stále 902 00:39:35,890 --> 00:39:36,950 bude mať kolízie. 903 00:39:36,950 --> 00:39:42,710 >> Tak to vyvoláva otázku, čo je Náklady robí inserce a delécie 904 00:39:42,710 --> 00:39:44,850 do dátovej štruktúry, ako je tento? 905 00:39:44,850 --> 00:39:46,630 No dovoľte mi navrhnúť - 906 00:39:46,630 --> 00:39:51,570 a nechaj ma ísť späť na obrazovku cez tu - ak sme n prvkami 907 00:39:51,570 --> 00:39:56,330 zoznam, takže ak sa snažíme vložiť n prvkov, a máme 908 00:39:56,330 --> 00:39:58,050 koľko celkom lopaty? 909 00:39:58,050 --> 00:40:03,450 Povedzme, že celkom 31 vedier v prípade narodenín. 910 00:40:03,450 --> 00:40:09,240 Aká je maximálna dĺžka jedného z týchto reťazcov potenciálne? 911 00:40:09,240 --> 00:40:12,670 >> Ak opäť tam 31 možné narodeniny v danom mesiaci. 912 00:40:12,670 --> 00:40:14,580 A my sme len hrudkujúce všetky - 913 00:40:14,580 --> 00:40:15,580 v skutočnosti je to hlúpy príklad. 914 00:40:15,580 --> 00:40:16,960 Jdem na 26 miesto. 915 00:40:16,960 --> 00:40:20,890 Takže ak skutočne ľudia, ktorých mená začať 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 sme pomocou dátovej štruktúry, ako tá, ktorú sme práve videli, kedy máme 918 00:40:25,920 --> 00:40:30,210 pole ukazovateľov, z ktorých každá poukazuje na pripojenom zozname, kde sa 919 00:40:30,210 --> 00:40:32,360 Prvý zoznam je každý s názvom Alice. 920 00:40:32,360 --> 00:40:35,770 Druhý zoznam je každý s meno začínajúci, počnúc 921 00:40:35,770 --> 00:40:36,980 s B, a tak ďalej. 922 00:40:36,980 --> 00:40:41,020 >> To, čo je pravdepodobné, že dĺžka každej z tieto zoznamy keď budeme predpokladať, pekný čistý 923 00:40:41,020 --> 00:40:45,410 Rozdelenie mien A až Z v celej dátovej štruktúry? 924 00:40:45,410 --> 00:40:50,210 K dispozícii je n ľudí v dátovej štruktúre delené 26, ak sú dobre 925 00:40:50,210 --> 00:40:52,110 rozprestreté po celej dátové štruktúry. 926 00:40:52,110 --> 00:40:54,970 Takže dĺžka každej z týchto reťazca je n delené 26. 927 00:40:54,970 --> 00:40:57,380 Ale vo veľkom notácie, čo to je? 928 00:40:57,380 --> 00:41:00,100 929 00:41:00,100 --> 00:41:02,440 Čo je to naozaj? 930 00:41:02,440 --> 00:41:04,150 Takže je to naozaj len n, nie? 931 00:41:04,150 --> 00:41:06,620 Pretože sme povedal v minulosti, že fuj vydeľte 26. 932 00:41:06,620 --> 00:41:08,710 Áno, v skutočnosti je to rýchlejšie. 933 00:41:08,710 --> 00:41:12,720 Ale teoreticky, to nie je zásadne všetko rýchlejšie. 934 00:41:12,720 --> 00:41:16,040 >> Tak sme sa nezdajú byť až tak moc bližšie k tomuto Svätého grálu. 935 00:41:16,040 --> 00:41:17,750 V skutočnosti, je to len lineárny čas. 936 00:41:17,750 --> 00:41:20,790 Sakra, na tomto mieste, tak prečo nie my stačí použiť jeden obrovský komunikačné zoznam? 937 00:41:20,790 --> 00:41:23,510 Prečo nie my stačí použiť jeden veľký Pole pre ukladanie názvov 938 00:41:23,510 --> 00:41:25,010 všetci v miestnosti? 939 00:41:25,010 --> 00:41:28,280 No, je tu ešte niečo, čo presvedčivá tabuľky hash? 940 00:41:28,280 --> 00:41:30,810 Je tu ešte niečo, čo presvedčivé o dátovej štruktúre 941 00:41:30,810 --> 00:41:33,940 to vyzerá takto? 942 00:41:33,940 --> 00:41:35,182 Toto. 943 00:41:35,182 --> 00:41:37,050 >> STUDENT: [nepočuteľné]. 944 00:41:37,050 --> 00:41:39,840 >> SPEAKER 1: Jasne, a znovu keď je to len lineárny algoritmus, a 945 00:41:39,840 --> 00:41:42,780 lineárny čas dátová štruktúra, prečo nie ja len ukladať každého názov veľké 946 00:41:42,780 --> 00:41:44,210 pole, alebo vo veľkom prepojeného zoznamu? 947 00:41:44,210 --> 00:41:47,010 A prestaň robiť UO tak oveľa ťažšie než je potrebné, aby sa? 948 00:41:47,010 --> 00:41:49,600 949 00:41:49,600 --> 00:41:53,190 Čo je presvedčivá, hoci aj keď som škriabal von? 950 00:41:53,190 --> 00:41:54,930 >> STUDENT: [nepočuteľné]. 951 00:41:54,930 --> 00:41:57,040 >> SPEAKER 1: Insertions nie sú? 952 00:41:57,040 --> 00:41:58,140 Drahé už nie. 953 00:41:58,140 --> 00:42:03,390 Takže vložky potenciálne mohli aj naďalej byť konštantný čas, aj keď dáta 954 00:42:03,390 --> 00:42:07,910 Štruktúra vyzerá to, rad ukazovatele, z ktorých každý ukazuje na 955 00:42:07,910 --> 00:42:09,550 potenciálne spojové zoznamy. 956 00:42:09,550 --> 00:42:15,220 Ako by ste mohli dosiahnuť konštantná čas vloženia mená? 957 00:42:15,220 --> 00:42:16,280 Držať ju v prednej časti, nie? 958 00:42:16,280 --> 00:42:19,290 >> Ak by sme obetovať cieľ návrhu od skôr, kde sme chceli udržať 959 00:42:19,290 --> 00:42:22,650 každého názov, napríklad, triedenie, alebo všetky čísla na scéne radené, 960 00:42:22,650 --> 00:42:25,020 Predpokladajme, že máme netriedeného spájať zoznam. 961 00:42:25,020 --> 00:42:29,960 To len nás stojí jeden alebo dva kroky, ako v prípade Bena a Brianom 962 00:42:29,960 --> 00:42:32,750 skôr, vložiť prvok na na začiatku zoznamu. 963 00:42:32,750 --> 00:42:36,090 Takže ak sa nechcete starať o triedení všetky mien začínajúcich alebo všetky 964 00:42:36,090 --> 00:42:39,660 mená začínajúce na B, môžeme stále dosiahnuť konštantný čas vloženia. 965 00:42:39,660 --> 00:42:43,900 Teraz vzhliadol Alice alebo Bob alebo akýkoľvek názov všeobecne je stále čo? 966 00:42:43,900 --> 00:42:48,100 Je to veľký O n delené 26, v ideálny prípad, kedy sú všetci jednotne 967 00:42:48,100 --> 00:42:51,190 distribuované, kde je toľko, koľko je pretože sú to Z, čo je pravdepodobne 968 00:42:51,190 --> 00:42:52,220 nereálne. 969 00:42:52,220 --> 00:42:53,880 Ale to je stále lineárna. 970 00:42:53,880 --> 00:42:57,120 >> Ale tu sa dostávame späť do bodu z asymptotickej notácie bytia 971 00:42:57,120 --> 00:42:58,600 teoreticky pravda. 972 00:42:58,600 --> 00:43:02,960 Ale v reálnom svete, keď tvrdí, že môj program niečo urobiť 26 krát 973 00:43:02,960 --> 00:43:06,210 rýchlejšie než tie, ktorých program, budete radšej používate? 974 00:43:06,210 --> 00:43:09,660 S pozdravom a bane, čo je 26 krát rýchlejší? 975 00:43:09,660 --> 00:43:14,320 Realisticky, osoba, ktorá je o 26 krát rýchlejšie, aj keď je to teoreticky 976 00:43:14,320 --> 00:43:18,790 naše algoritmy spustiť v rovnakom Asymptotická dobe jeho behu. 977 00:43:18,790 --> 00:43:20,940 >> Dovoľte mi navrhnúť iný riešenie vôbec. 978 00:43:20,940 --> 00:43:24,380 A ak to nebude fúkať vašu myseľ, sme z dátových štruktúr. 979 00:43:24,380 --> 00:43:27,420 Tak to je trie - 980 00:43:27,420 --> 00:43:28,520 druh hlúpe meno. 981 00:43:28,520 --> 00:43:32,880 Pochádza z rešerší, a slovo sa píše trie, t-r-i-e, pretože 982 00:43:32,880 --> 00:43:34,450 Kurz vyhľadávanie znie ako trie. 983 00:43:34,450 --> 00:43:36,580 Ale to je história zo slova trie. 984 00:43:36,580 --> 00:43:40,980 >> Takže trie je naozaj nejaký druh stromu, a je to aj hra na dané slovo. 985 00:43:40,980 --> 00:43:46,330 A aj keď nemôžete celkom vidieť s touto vizualizáciou, trie je 986 00:43:46,330 --> 00:43:50,790 strom štruktúrovaný ako rodokmeni s jeden predok hore a mnoho 987 00:43:50,790 --> 00:43:54,530 vnúčat a veľkých vnúčatá ako listy na dne. 988 00:43:54,530 --> 00:43:58,100 Ale každý uzol trie je pole. 989 00:43:58,100 --> 00:44:00,680 A to je v poli - a poďme zjednodušovať na chvíľu - je to 990 00:44:00,680 --> 00:44:04,600 pole, v tomto prípade o veľkosti 26, kde každý uzol je opäť poľa veľkosti 991 00:44:04,600 --> 00:44:09,000 26, kde je v tom, že nultý prvok pole predstavuje, a posledná 992 00:44:09,000 --> 00:44:11,810 element v každej takej Pole predstavuje Z. 993 00:44:11,810 --> 00:44:15,520 >> Takže navrhujem teda, že tieto dáta štruktúry, známej ako trie, môže byť 994 00:44:15,520 --> 00:44:17,600 použiť aj pre ukladanie slová. 995 00:44:17,600 --> 00:44:21,740 Videli sme pred chvíľou, ako by sme mohli uložiť slová, alebo v tomto prípade mena, a my 996 00:44:21,740 --> 00:44:25,440 už videli, ako môžeme uložiť čísla, ale ak sa zameriame na názvy alebo reťazca 997 00:44:25,440 --> 00:44:27,460 Tu si všimnite, čo je zaujímavé. 998 00:44:27,460 --> 00:44:32,210 Tvrdím, že názov je Maxwell v tejto dátovej štruktúry. 999 00:44:32,210 --> 00:44:33,730 Kde vidíte Maxwell? 1000 00:44:33,730 --> 00:44:35,140 >> STUDENT: [nepočuteľné]. 1001 00:44:35,140 --> 00:44:36,240 >> SPEAKER 1: Na ľavej strane. 1002 00:44:36,240 --> 00:44:39,910 Takže to, čo je zaujímavé, s týmito dátami štruktúra je skôr než obchod so 1003 00:44:39,910 --> 00:44:46,200 reťazec M-A-X-W-E-L-L lomka nula, všetky súvislý, čo môžete urobiť, namiesto toho 1004 00:44:46,200 --> 00:44:46,890 je nasledujúci. 1005 00:44:46,890 --> 00:44:50,510 Pokiaľ sa jedná o trie ako dátové štruktúry, každý ktorého uzloch je opäť pole, 1006 00:44:50,510 --> 00:44:54,650 a chcete uložiť Maxwell, musíte najprv index, a tak v koreňovom uzle, takže 1007 00:44:54,650 --> 00:44:57,810 hovoriť, najhornejšia uzol, na umiestnenie M, vpravo, tak 1008 00:44:57,810 --> 00:44:59,160 zhruba do stredu. 1009 00:44:59,160 --> 00:45:03,740 A potom odtiaľ, postupujte ukazovateľ na podriadené uzly, aby som tak povedal. 1010 00:45:03,740 --> 00:45:06,150 Takže v rodokmeni zmysle, budete postupovať smerom nadol. 1011 00:45:06,150 --> 00:45:09,030 A, ktoré vás dovedú do iného uzla Vľavo, ktorý je 1012 00:45:09,030 --> 00:45:10,540 len ďalšie polia. 1013 00:45:10,540 --> 00:45:14,710 >> A potom, ak chcete uložiť Maxwell, nájdete ukazovateľ, ktorý predstavuje 1014 00:45:14,710 --> 00:45:16,430 A, čo je toto tu. 1015 00:45:16,430 --> 00:45:17,840 Potom môžete ísť na ďalšiu uzol. 1016 00:45:17,840 --> 00:45:20,100 A upozornenie - to je dôvod, prečo je obraz trochu klame - 1017 00:45:20,100 --> 00:45:21,990 Tento uzol vyzerať Super malý. 1018 00:45:21,990 --> 00:45:26,050 Ale na pravej strane je Y a Z. Je to len autor skrátený 1019 00:45:26,050 --> 00:45:27,630 obraz tak, že ste skutočne vidieť veci. 1020 00:45:27,630 --> 00:45:30,400 Inak tento obrázok by bolo veľmi široké. 1021 00:45:30,400 --> 00:45:36,180 Takže teraz si index do umiestnenia X, potom W, potom E, potom L, potom L. Tak čo je 1022 00:45:36,180 --> 00:45:37,380 to zvedavosť? 1023 00:45:37,380 --> 00:45:41,250 >> No, ak budeme používať tento druh nový sa o tom, ako ukladať reťazec 1024 00:45:41,250 --> 00:45:44,500 dátová štruktúra, stále musíte v podstate zaškrtnúť v dátach 1025 00:45:44,500 --> 00:45:47,250 štruktúra, ktorá slovo tu končí. 1026 00:45:47,250 --> 00:45:50,830 Inými slovami, každý z týchto uzlov nejako musí pamätať, že sme 1027 00:45:50,830 --> 00:45:53,500 vlastne nasledoval všetkých týchto ukazovateľov a odchádzajú trochu 1028 00:45:53,500 --> 00:45:58,370 chlieb omrvinky v spodnej časti tu v tejto Štruktúra pre označenie M-A-X-W-E-L-L 1029 00:45:58,370 --> 00:46:00,230 v skutočnosti v tejto dátovej štruktúry. 1030 00:46:00,230 --> 00:46:02,040 >> Tak by sme mohli postupovať takto. 1031 00:46:02,040 --> 00:46:06,810 Každý z uzlov v obraze sme len Píla má jeden, poľa veľkosti 27. 1032 00:46:06,810 --> 00:46:10,550 A to je v súčasnej dobe 27, pretože v p nastaviť šesť, budeme v skutočnosti vám apostrof, 1033 00:46:10,550 --> 00:46:13,590 takže môžeme mať mená ako O'Reilly a iní s apostrofy. 1034 00:46:13,590 --> 00:46:14,820 Ale rovnaký nápad. 1035 00:46:14,820 --> 00:46:17,710 Každý z týchto prvkov v poľa poukazuje na struct 1036 00:46:17,710 --> 00:46:19,320 uzol, tak len uzol. 1037 00:46:19,320 --> 00:46:21,430 Tak to je veľmi pripomínajúci nášho prepojeného zoznamu. 1038 00:46:21,430 --> 00:46:24,550 >> A potom som si Boolean, ktorý budem zavolajte slovo, ktoré je len bude 1039 00:46:24,550 --> 00:46:29,120 true, ak slovo končí na to uzol v strome. 1040 00:46:29,120 --> 00:46:32,870 Je to skutočne predstavuje malý trojuholník sme videli pred chvíľou. 1041 00:46:32,870 --> 00:46:37,190 Takže ak slovo končí v tomto uzle strom, bude to slovo pole je pravda, 1042 00:46:37,190 --> 00:46:41,990 ktorý je koncepčne zaškrtnutím alebo sme kreslíte tohto trojuholníka, áno, tam 1043 00:46:41,990 --> 00:46:44,080 je slovo tu. 1044 00:46:44,080 --> 00:46:45,120 >> Tak to je trie. 1045 00:46:45,120 --> 00:46:48,540 A teraz je otázka, čo je jeho doba chodu? 1046 00:46:48,540 --> 00:46:49,930 Je to veľký O n? 1047 00:46:49,930 --> 00:46:51,410 Je to niečo iné? 1048 00:46:51,410 --> 00:46:57,330 No, ak ste n názvy týchto údajov štruktúra, Maxwell je iba jedným z 1049 00:46:57,330 --> 00:47:02,330 je, aká je doba chodu vkladanie alebo zistenie Maxwell? 1050 00:47:02,330 --> 00:47:06,230 1051 00:47:06,230 --> 00:47:09,050 Čo je to doba chodu vloženie Maxwell? 1052 00:47:09,050 --> 00:47:11,740 Ak existuje n iné mená už v tabuľke? 1053 00:47:11,740 --> 00:47:12,507 Jo? 1054 00:47:12,507 --> 00:47:15,429 >> STUDENT: [nepočuteľné]. 1055 00:47:15,429 --> 00:47:17,550 >> SPEAKER 1: Jo, je to dĺžka mená, nie? 1056 00:47:17,550 --> 00:47:24,420 Tak M-a-X-w-e-l-l, takže to je takto algoritmus je veľký O sedem. 1057 00:47:24,420 --> 00:47:26,580 Teraz, samozrejme, názov majú rôznu dĺžku. 1058 00:47:26,580 --> 00:47:27,380 Možno je to krátky názov. 1059 00:47:27,380 --> 00:47:28,600 Možno je to dlhší názov. 1060 00:47:28,600 --> 00:47:33,390 Ale čo je kľúčové je to, že je to neustály číslo. 1061 00:47:33,390 --> 00:47:36,810 A možno to naozaj nie je konštantná, Ale Boh, keď realisticky, v 1062 00:47:36,810 --> 00:47:41,570 slovník, je to asi nejaká hranica, na počte písmen 1063 00:47:41,570 --> 00:47:43,820 meno osoby v danej krajine. 1064 00:47:43,820 --> 00:47:46,940 >> A tak môžeme predpokladať, že hodnota je konštantná. 1065 00:47:46,940 --> 00:47:47,750 Neviem, čo to je. 1066 00:47:47,750 --> 00:47:50,440 Je to pravdepodobne väčšie než si myslíme, že je. 1067 00:47:50,440 --> 00:47:52,720 Pretože tam je vždy nejaký roh puzdro s crazy dlhým názvom. 1068 00:47:52,720 --> 00:47:56,360 Takže povedzme, že k, ale je to stále konštantný pravdepodobne, pretože každý 1069 00:47:56,360 --> 00:48:00,190 meno vo svete, aspoň v Najmä krajiny, je to, že dĺžka alebo 1070 00:48:00,190 --> 00:48:01,780 kratšie, takže je konštantná. 1071 00:48:01,780 --> 00:48:04,490 Ale keď sme povedali, že je niečo veľké O konštantné hodnoty, čo je to 1072 00:48:04,490 --> 00:48:07,760 skutočne zodpovedá? 1073 00:48:07,760 --> 00:48:10,420 To je naozaj to isté ako hovorí konštantný čas. 1074 00:48:10,420 --> 00:48:11,530 >> Teraz sme trochu podvádzanie, nie? 1075 00:48:11,530 --> 00:48:15,340 Sme druh využitia teóriu, tu, aby som povedal, že dobre, aby koeficient sa 1076 00:48:15,340 --> 00:48:17,450 naozaj iba rádovo jednej, a to je konštantný čas. 1077 00:48:17,450 --> 00:48:18,200 Ale v skutočnosti je. 1078 00:48:18,200 --> 00:48:22,550 Vzhľadom k tomu, Kľúčovou myšlienkou je, že ak sme n mená už v tomto 1079 00:48:22,550 --> 00:48:26,010 dátové štruktúry, a vložíme Maxwell, je množstvo času, ktoré nás zavedie do 1080 00:48:26,010 --> 00:48:29,530 vložiť Maxwell vôbec postihnuté tým, koľko ďalších ľudí 1081 00:48:29,530 --> 00:48:31,100 sú v dátovej štruktúre? 1082 00:48:31,100 --> 00:48:31,670 Nezdá sa, že byť. 1083 00:48:31,670 --> 00:48:36,280 Keby som mal miliardu viac prvkov tejto trie a vložte Maxwell, je 1084 00:48:36,280 --> 00:48:38,650 sa vôbec týka? 1085 00:48:38,650 --> 00:48:39,050 Nie. 1086 00:48:39,050 --> 00:48:42,950 A to je na rozdiel od niektorého z denných dát štruktúry sme videli doteraz, kedy 1087 00:48:42,950 --> 00:48:46,820 doba chodu algoritmu je úplne nezávisle na tom, ako moc 1088 00:48:46,820 --> 00:48:51,430 vec je alebo nie je už v tejto dátovej štruktúry. 1089 00:48:51,430 --> 00:48:54,650 >> A tak s tým poskytuje teraz je príležitosť pre p sadu šiestich, ktorá bude 1090 00:48:54,650 --> 00:48:58,310 opäť zahŕňať realizáciu vlastnej Kontrola pravopisu, čítanie v 150000 1091 00:48:58,310 --> 00:49:01,050 slová, ako najlepšie uložiť, že nie je nutne zrejmé. 1092 00:49:01,050 --> 00:49:04,030 A keď som sa usiloval nájsť Svätý grál, vôbec sa mi nepáči 1093 00:49:04,030 --> 00:49:05,330 tvrdí, že je trie. 1094 00:49:05,330 --> 00:49:09,810 V skutočnosti môže byť hašovacia tabuľka veľmi dobre ukáže byť oveľa efektívnejšie. 1095 00:49:09,810 --> 00:49:10,830 Ale to sú len - 1096 00:49:10,830 --> 00:49:14,620 to je len jedna z rozhodnutia o návrhu budete musieť urobiť. 1097 00:49:14,620 --> 00:49:18,920 >> Ale pri uzatváraní poďme 50 alebo tak sekúnd sa pozrieť na to, čo je 1098 00:49:18,920 --> 00:49:22,190 pred budúci týždeň a my po prechode z tohto príkazového riadku 1099 00:49:22,190 --> 00:49:26,220 svete, ak C programy k veciam web založené a jazyky ako PHP a 1100 00:49:26,220 --> 00:49:30,350 JavaScript a internet sám protokoly ako HTTP, ktorú ste 1101 00:49:30,350 --> 00:49:32,870 brať za samozrejmosť rokov teraz, a napísal väčšinu každý 1102 00:49:32,870 --> 00:49:34,440 deň, možno, alebo vidieť. 1103 00:49:34,440 --> 00:49:37,420 A začneme olúpte vrstvy, čo je internet. 1104 00:49:37,420 --> 00:49:40,650 A čo je kód, ktorý tvorí základ dnešnej nástroja. 1105 00:49:40,650 --> 00:49:43,230 Takže 50 sekúnd tohto ukážku tu. 1106 00:49:43,230 --> 00:49:46,570 Dám vám Bojovníci siete. 1107 00:49:46,570 --> 00:49:51,370 >> [PLAYBACK] 1108 00:49:51,370 --> 00:49:56,764 >> -Prišiel so správou. 1109 00:49:56,764 --> 00:50:00,687 S protokolom všetci jeho vlastné. 1110 00:50:00,687 --> 00:50:13,370 1111 00:50:13,370 --> 00:50:19,780 Prišiel na svet krutých firewallov, bezcitný routery a nebezpečenstvo ďaleko 1112 00:50:19,780 --> 00:50:22,600 horšie ako smrť. 1113 00:50:22,600 --> 00:50:23,590 Je rýchly. 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á svoju adresu. 1117 00:50:30,420 --> 00:50:32,920 1118 00:50:32,920 --> 00:50:34,590 Bojovníci siete. 1119 00:50:34,590 --> 00:50:35,290 >> [END PLAYBACK] 1120 00:50:35,290 --> 00:50:38,070 >> SPEAKER 1: To je, ako internet musia pracovať od budúceho týždňa. 1121 00:50:38,070 --> 00:50:40,406