1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:05,120 [Přehrávání hudby] 3 00:00:05,120 --> 00:00:12,026 4 00:00:12,026 --> 00:00:12,900 SPEAKER 1: V pořádku. 5 00:00:12,900 --> 00:00:14,600 Všichni vítejte zpět do kategorie. 6 00:00:14,600 --> 00:00:18,660 Doufám, že jste všichni úspěšně zpět z vašeho testu 7 00:00:18,660 --> 00:00:19,510 z minulého týdne. 8 00:00:19,510 --> 00:00:22,564 Vím, že je trochu blázen občas. 9 00:00:22,564 --> 00:00:25,230 Jak jsem říkal předtím, pokud jste v rámci směrodatné odchylky, 10 00:00:25,230 --> 00:00:28,188 nemáte opravdu starat o to, a to zejména pro méně pohodlné úseku. 11 00:00:28,188 --> 00:00:30,230 To je o tom, kde byste měli být. 12 00:00:30,230 --> 00:00:32,850 >> Pokud jste si skvěle, pak úžasné. 13 00:00:32,850 --> 00:00:33,650 Sláva tobě. 14 00:00:33,650 --> 00:00:36,149 A pokud máte pocit, že musíte trochu více pomoci, prosím 15 00:00:36,149 --> 00:00:38,140 neváhejte oslovit z některého z TFS. 16 00:00:38,140 --> 00:00:40,030 Všichni jsme tady na pomoc. 17 00:00:40,030 --> 00:00:40,960 >> To je důvod, proč jsme se učit. 18 00:00:40,960 --> 00:00:44,550 To je důvod, proč jsem tady každé pondělí pro vás kluci a v kanceláři hodin ve čtvrtek. 19 00:00:44,550 --> 00:00:48,130 Tak neváhejte a dejte mi vědět, Pokud máte obavy o ničem 20 00:00:48,130 --> 00:00:52,450 nebo v případě, že je něco v kvízu že byste opravdu chtěli řešit. 21 00:00:52,450 --> 00:00:56,940 >> Takže agenda pro dnešek je vše o datových struktur. 22 00:00:56,940 --> 00:01:01,520 Některé z nich jsou prostě bude jen aby se vám seznámil s těmito. 23 00:01:01,520 --> 00:01:04,870 Nesmíte nikdy realizovat je v této třídě. 24 00:01:04,870 --> 00:01:08,690 Některé z nich si vyzkoušíte, jako pro pravopisu pset. 25 00:01:08,690 --> 00:01:11,380 >> Budete mít svůj výběr mezi stoly mřížky a pokusů. 26 00:01:11,380 --> 00:01:13,680 Takže jsme určitě jít přes ty. 27 00:01:13,680 --> 00:01:18,690 Bude to mít rozhodně více druhů vysoké úrovni úseku dnes, i když, 28 00:01:18,690 --> 00:01:22,630 protože existuje mnoho z nich, a pokud jsme šli do podrobností implementace 29 00:01:22,630 --> 00:01:26,490 na všech z nich, nebyli bychom dokonce projít spojových seznamů 30 00:01:26,490 --> 00:01:28,520 a možná trochu hash tabulky. 31 00:01:28,520 --> 00:01:31,200 >> Takže mějte se mnou. 32 00:01:31,200 --> 00:01:33,530 Nebudeme se dělá až kódování tentokrát. 33 00:01:33,530 --> 00:01:36,870 Máte-li nějaké otázky o tom nebo chcete-li vidět, že realizovat 34 00:01:36,870 --> 00:01:39,260 nebo se pokusit si to pro sebe, Určitě doporučuji 35 00:01:39,260 --> 00:01:44,250 bude study.cs50.net, které má příklady všech z nich. 36 00:01:44,250 --> 00:01:46,400 To bude mít své powerpoints s poznámkami, které jsme 37 00:01:46,400 --> 00:01:50,860 mají tendenci používat i trochou programování cvičení, především na věci, 38 00:01:50,860 --> 00:01:55,250 jako propojených seznamů a binární stromy komíny a narážky. 39 00:01:55,250 --> 00:01:59,590 Tak trochu na vysoké úrovni, které by mohlo být pěkné pro vás. 40 00:01:59,590 --> 00:02:01,320 >> Takže s tím, budeme začít. 41 00:02:01,320 --> 00:02:03,060 A také, yes-- kvízy. 42 00:02:03,060 --> 00:02:06,550 Myslím si, že většina z vás, kteří jsou v moje část má své kvízy, 43 00:02:06,550 --> 00:02:12,060 ale každý, kdo přijde, nebo z nějakého důvodu ne, jsou tady v přední části. 44 00:02:12,060 --> 00:02:12,740 >> Tak spojových seznamů. 45 00:02:12,740 --> 00:02:15,650 Vím, že tento druh jde zálohovat před kvíz. 46 00:02:15,650 --> 00:02:17,940 To bylo před týdnem že jsme se dozvěděli o tom. 47 00:02:17,940 --> 00:02:21,040 Ale v tomto případě, budeme jen jít trochu více do hloubky. 48 00:02:21,040 --> 00:02:25,900 >> Tak proč bychom mohli vybrat spojový seznam přes pole? 49 00:02:25,900 --> 00:02:27,130 Co je odlišuje? 50 00:02:27,130 --> 00:02:27,630 Ano? 51 00:02:27,630 --> 00:02:30,464 >> Diváků: můžete též rozšířit spojené Seznam oproti Array pevnou velikost. 52 00:02:30,464 --> 00:02:31,171 SPEAKER 1: Správně. 53 00:02:31,171 --> 00:02:33,970 Pole má pevnou velikost vzhledem k tomu, spojový seznam má proměnnou velikost. 54 00:02:33,970 --> 00:02:36,970 Takže pokud nevíme, jak moc chceme uložit, 55 00:02:36,970 --> 00:02:39,880 spojový seznam nám dává velký způsob, jak to udělat, protože my můžeme jen 56 00:02:39,880 --> 00:02:43,730 přidat na jiném uzlu a přidat na jiný uzel a přidat na jiném uzlu. 57 00:02:43,730 --> 00:02:45,750 Ale to, co by mohlo být trade-off? 58 00:02:45,750 --> 00:02:49,521 Pamatuje si někdo na trade-off mezi poli a spojových seznamů? 59 00:02:49,521 --> 00:02:50,020 Mmhmm? 60 00:02:50,020 --> 00:02:51,460 >> Diváků: Musíte projít celou cestu 61 00:02:51,460 --> 00:02:53,738 prostřednictvím propojeného seznamu najít prvek v seznamu. 62 00:02:53,738 --> 00:02:55,570 V poli, můžete jen najít prvek. 63 00:02:55,570 --> 00:02:56,278 >> SPEAKER 1: Správně. 64 00:02:56,278 --> 00:02:57,120 Tak s arrays-- 65 00:02:57,120 --> 00:02:58,500 >> Diváků: [neslyšitelné]. 66 00:02:58,500 --> 00:03:01,090 >> SPEAKER 1: S polem, máme co se nazývá náhodný přístup. 67 00:03:01,090 --> 00:03:04,820 Znamená to, že pokud chceme, aby to, co je někdy pátý bod seznamu 68 00:03:04,820 --> 00:03:07,230 nebo pátý bod našeho pole, můžeme jen chytit ji. 69 00:03:07,230 --> 00:03:10,440 Pokud je to spojový seznam, máme iterovat, že jo? 70 00:03:10,440 --> 00:03:14,020 Tak přístup k prvku v pole je konstantní čas, 71 00:03:14,020 --> 00:03:19,530 zatímco v propojeném seznamu, že by s největší pravděpodobností bude lineární čas, protože možná 72 00:03:19,530 --> 00:03:21,370 naše prvkem je úplně na konci. 73 00:03:21,370 --> 00:03:23,446 Musíme prohledat všechno. 74 00:03:23,446 --> 00:03:25,320 Takže se všemi těmito údaji struktury pojedeme 75 00:03:25,320 --> 00:03:29,330 se strávit trochu více času na, Jaké jsou plusy a zápory. 76 00:03:29,330 --> 00:03:31,480 Když bychom mohli chtít použijte jeden přes druhého? 77 00:03:31,480 --> 00:03:34,970 A to je druh větší věc odnést. 78 00:03:34,970 --> 00:03:40,140 >> Takže máme tady definice uzlu. 79 00:03:40,140 --> 00:03:43,040 Je to jako jeden prvek v náš spojový seznam, ne? 80 00:03:43,040 --> 00:03:46,180 Takže jsme všichni obeznámeni s našimi typedef structs, 81 00:03:46,180 --> 00:03:47,980 které jsme přešli v recenzi naposledy. 82 00:03:47,980 --> 00:03:53,180 Bylo to v podstatě jen vytvořením jiný datový typ, který bychom mohli použít. 83 00:03:53,180 --> 00:03:57,930 >> A v tomto případě, je to nějaký uzel že bude mít nějaké číslo v. 84 00:03:57,930 --> 00:04:00,210 A co pak je druhá část tady? 85 00:04:00,210 --> 00:04:03,192 86 00:04:03,192 --> 00:04:05,677 Každý, kdo? 87 00:04:05,677 --> 00:04:06,680 >> Diváků: [neslyšitelné]. 88 00:04:06,680 --> 00:04:07,020 >> SPEAKER 1: Jo. 89 00:04:07,020 --> 00:04:08,400 Je to ukazatel na další uzel. 90 00:04:08,400 --> 00:04:12,610 Takže by to mělo být skutečně tady. 91 00:04:12,610 --> 00:04:18,790 To je ukazatel typu uzlu na další věc. 92 00:04:18,790 --> 00:04:22,410 A to je to, co zahrnuje náš uzel. 93 00:04:22,410 --> 00:04:24,060 V pohodě. 94 00:04:24,060 --> 00:04:29,390 >> Dobře, tak s hledáním, jak jsme byli jen říkám, do ruky, pokud jste 95 00:04:29,390 --> 00:04:31,840 bude prohledávat, Máte skutečně iterovat 96 00:04:31,840 --> 00:04:33,660 prostřednictvím propojeného seznamu. 97 00:04:33,660 --> 00:04:38,530 Takže pokud se díváme na počet 9 bychom začít na naší hlavě 98 00:04:38,530 --> 00:04:41,520 a že nás upozorňuje na začátku našeho propojeného seznamu, ne? 99 00:04:41,520 --> 00:04:44,600 A my říkáme, OK, to dělá uzel obsahovat číslo 9? 100 00:04:44,600 --> 00:04:45,690 Ne? 101 00:04:45,690 --> 00:04:47,500 >> V pořádku, přejděte na další jeden. 102 00:04:47,500 --> 00:04:48,312 Následujte ho. 103 00:04:48,312 --> 00:04:49,520 Má obsahovat číslo 9? 104 00:04:49,520 --> 00:04:50,570 Ne. 105 00:04:50,570 --> 00:04:51,550 Sledujte další. 106 00:04:51,550 --> 00:04:55,490 >> Takže máme skutečně iterovat prostřednictvím naší propojeného seznamu. 107 00:04:55,490 --> 00:05:00,070 Nemůžeme prostě jít přímo na místo, kde 9. 108 00:05:00,070 --> 00:05:05,860 A pokud vy vlastně chcete vidět nějaký pseudo-kódu tam nahoře. 109 00:05:05,860 --> 00:05:10,420 Máme nějakou funkci vyhledávání zde který bere in-- co to přijmout? 110 00:05:10,420 --> 00:05:13,110 111 00:05:13,110 --> 00:05:14,320 Co si myslíte? 112 00:05:14,320 --> 00:05:15,960 Tak snadné. 113 00:05:15,960 --> 00:05:17,784 Co je to? 114 00:05:17,784 --> 00:05:18,700 Diváků: [neslyšitelné]. 115 00:05:18,700 --> 00:05:20,366 SPEAKER 1: Počet hledáme. 116 00:05:20,366 --> 00:05:20,980 Je to tak? 117 00:05:20,980 --> 00:05:22,875 A co by to odpovídat? 118 00:05:22,875 --> 00:05:25,020 Je to ukazatel? 119 00:05:25,020 --> 00:05:26,000 >> Diváků: uzel. 120 00:05:26,000 --> 00:05:28,980 >> SPEAKER 1: uzel do seznamu že se díváme, je to tak? 121 00:05:28,980 --> 00:05:33,700 Takže máme některé uzly jsou ukazatel zde. 122 00:05:33,700 --> 00:05:37,240 To je bod, který se bude vlastně iterovat našem seznamu. 123 00:05:37,240 --> 00:05:39,630 Vydali jsme se rovná seznam protože to je to 124 00:05:39,630 --> 00:05:44,380 Nastavení je rovno spuštění našeho propojeného seznamu. 125 00:05:44,380 --> 00:05:50,660 >> A i když to není NULL, zatímco stále máme věci v našem seznamu, 126 00:05:50,660 --> 00:05:55,580 zkontrolujte, zda tento uzel má počet hledáme. 127 00:05:55,580 --> 00:05:57,740 Return true. 128 00:05:57,740 --> 00:06:01,070 V opačném případě, aktualizovat, ne? 129 00:06:01,070 --> 00:06:04,870 >> Pokud je NULL, my ukončit naše while a return false 130 00:06:04,870 --> 00:06:08,340 protože to znamená, že jsme se našli. 131 00:06:08,340 --> 00:06:11,048 Má každý si, jak to funguje? 132 00:06:11,048 --> 00:06:11,548 OK. 133 00:06:11,548 --> 00:06:14,940 134 00:06:14,940 --> 00:06:20,260 >> Tak s vložení, budete mají tři různé způsoby. 135 00:06:20,260 --> 00:06:25,250 Můžete předřadit, můžete připojit a můžete vložit do roztříděný. 136 00:06:25,250 --> 00:06:28,215 V tomto případě jsme dělat předřazeným. 137 00:06:28,215 --> 00:06:33,380 Ví někdo, jak ty, tři případů může lišit? 138 00:06:33,380 --> 00:06:36,920 >> Tak prepend znamená, že můžete dát je v přední části vašeho seznamu. 139 00:06:36,920 --> 00:06:39,770 Takže by znamenalo, že bez ohledu na jaké jsou vaše uzel je, bez ohledu na to, 140 00:06:39,770 --> 00:06:43,160 co je hodnota, budete aby to tady vpředu, OK? 141 00:06:43,160 --> 00:06:45,160 Bude to první prvek v seznamu. 142 00:06:45,160 --> 00:06:49,510 >> Pokud jej připojit, bude to jít na zadní části vašeho seznamu. 143 00:06:49,510 --> 00:06:54,010 A vložit do nejrůznějších znamená, že jste dám skutečně do místa 144 00:06:54,010 --> 00:06:57,700 kde se udržuje spojový seznam seřazen. 145 00:06:57,700 --> 00:07:00,810 Opět, jak použít ty, a při použití 146 00:07:00,810 --> 00:07:02,530 jim bude lišit v závislosti na vašem případě. 147 00:07:02,530 --> 00:07:05,834 148 00:07:05,834 --> 00:07:07,750 Pokud to není nutné, aby třídit, prepend inklinuje 149 00:07:07,750 --> 00:07:10,460 být to, co si většina lidí použít, protože nemáte 150 00:07:10,460 --> 00:07:15,680 musí projít celý seznam najít konec přidejte ji, ne? 151 00:07:15,680 --> 00:07:17,720 Stačí si jen držet ji přímo. 152 00:07:17,720 --> 00:07:21,930 >> Tak jsme se projít Vložení 1 právě teď. 153 00:07:21,930 --> 00:07:26,360 Takže jedna věc, kterou budu Vřele doporučuji na tomto pset 154 00:07:26,360 --> 00:07:29,820 je k tomu věci, jako vždy. 155 00:07:29,820 --> 00:07:35,130 Je velmi důležité, abyste aktualizovat Vaše ukazatele ve správném pořadí 156 00:07:35,130 --> 00:07:38,620 protože pokud je aktualizovat trochu mimo provoz, 157 00:07:38,620 --> 00:07:42,210 budete skončit ztrátě části seznamu. 158 00:07:42,210 --> 00:07:49,680 >> Tak například, v tomto případě jsme říká šéf jen bod 1. 159 00:07:49,680 --> 00:07:56,070 Pokud se nám prostě, že bez uložení této 1, 160 00:07:56,070 --> 00:07:58,570 nemáme ponětí, co 1 by měly směřovat do současnosti 161 00:07:58,570 --> 00:08:02,490 proto, že jsme ztratili to, co hlavy ukázal na. 162 00:08:02,490 --> 00:08:05,530 Takže jedna věc k zapamatování když děláte předřazeným 163 00:08:05,530 --> 00:08:09,630 je zachránit to, co se hlava ukazuje na první, 164 00:08:09,630 --> 00:08:15,210 pak přiřadit, a pak aktualizovat co váš nový uzel by měl ukazovat na. 165 00:08:15,210 --> 00:08:20,870 166 00:08:20,870 --> 00:08:22,560 V tomto případě, je to jediný způsob, jak to udělat. 167 00:08:22,560 --> 00:08:25,440 >> Takže pokud jsme udělali to takhle kde jsme právě převelen hlavu, 168 00:08:25,440 --> 00:08:30,320 ztrácíme v podstatě dotazy Celý seznam, jo? 169 00:08:30,320 --> 00:08:38,000 Jeden způsob, jak to udělat, je mít 1 bod další, a pak si hlavu bod 1. 170 00:08:38,000 --> 00:08:42,650 Nebo si můžete udělat něco jako dočasné uskladnění, což jsem mluvil o. 171 00:08:42,650 --> 00:08:45,670 >> Ale přiřazení vlastní jméno ukazatele ve správném pořadí 172 00:08:45,670 --> 00:08:48,750 bude velmi, velmi důležité, aby tento pset. 173 00:08:48,750 --> 00:08:53,140 V opačném případě budete mít hash tabulky nebo pokus, který je jen bude 174 00:08:53,140 --> 00:08:56,014 pouze část slova, které jste chtějí, a pak you're-- mmhmm? 175 00:08:56,014 --> 00:08:58,930 Diváků: Jaký byl dočasný skladování věc, kterou mluvili? 176 00:08:58,930 --> 00:09:00,305 SPEAKER 1: dočasné uskladnění. 177 00:09:00,305 --> 00:09:02,760 Takže v podstatě další způsob, jak by to mohlo dělat 178 00:09:02,760 --> 00:09:07,650 je uložit hlavu něčeho, jako je uložit mu dočasné proměnné. 179 00:09:07,650 --> 00:09:11,250 Přiřadit ji na hodnotu 1 a aktualizovat 1 bod 180 00:09:11,250 --> 00:09:13,830 na co hlava používá poukázat na. 181 00:09:13,830 --> 00:09:16,920 Tímto způsobem je samozřejmě více elegantní, protože vás 182 00:09:16,920 --> 00:09:20,770 Nemusíte dočasnou hodnotu, ale jen nabízí jiný způsob, jak to udělat. 183 00:09:20,770 --> 00:09:23,999 184 00:09:23,999 --> 00:09:25,790 A my vlastně mají nějaký kód na to. 185 00:09:25,790 --> 00:09:28,080 Takže pro spojový seznam, jsme skutečně nějaký kód. 186 00:09:28,080 --> 00:09:31,930 Tak Sem vložte, je to prepending. 187 00:09:31,930 --> 00:09:34,290 Takže to zadá v čele. 188 00:09:34,290 --> 00:09:38,820 >> Takže první věc, kterou musíte vytvořit nový uzel, samozřejmě, 189 00:09:38,820 --> 00:09:40,790 a zkontrolujte, zda NULL. 190 00:09:40,790 --> 00:09:43,250 Vždy dobré. 191 00:09:43,250 --> 00:09:47,840 A pak je třeba přiřadit hodnoty. 192 00:09:47,840 --> 00:09:51,260 Vždy, když vytvoříte nový uzel, vás Nevím, co to ukazuje na další, 193 00:09:51,260 --> 00:09:54,560 takže chcete inicializovat na hodnotu NULL. 194 00:09:54,560 --> 00:09:58,760 Pokud to skončí ukázal na něco, co jiného, ​​dostane přidělen a je to v pořádku. 195 00:09:58,760 --> 00:10:00,740 Pokud je to první věc, v seznamu, je třeba 196 00:10:00,740 --> 00:10:04,270 poukázat na NULL, protože to je konec seznamu. 197 00:10:04,270 --> 00:10:12,410 >> Tak to vložit, vidíme tady se přiřadí další hodnotu naší uzlu 198 00:10:12,410 --> 00:10:17,380 být co hlava, což je to, co jsme tady měli. 199 00:10:17,380 --> 00:10:19,930 To je to, co jsme právě udělali. 200 00:10:19,930 --> 00:10:25,820 A pak jsme přiřazení hlavy až k bodu našeho nového uzlu, protože nezapomeňte, 201 00:10:25,820 --> 00:10:31,090 Nová je nějaký ukazatel na uzel, a to je přesně to, co hlava. 202 00:10:31,090 --> 00:10:34,370 To je přesně důvod, proč jsme tuto šipku přístupový. 203 00:10:34,370 --> 00:10:37,030 204 00:10:37,030 --> 00:10:37,530 V pohodě? 205 00:10:37,530 --> 00:10:38,130 Mmhmm? 206 00:10:38,130 --> 00:10:41,100 >> Diváků: Musíme inicializovat novou Další NULL jako první, 207 00:10:41,100 --> 00:10:44,240 nebo můžeme jen inicializovat na hlavu? 208 00:10:44,240 --> 00:10:48,210 >> SPEAKER 1: New další musí být NULL začít 209 00:10:48,210 --> 00:10:53,760 protože nevíte, kde to bude. 210 00:10:53,760 --> 00:10:56,100 Také tento druh je stejně jako paradigma. 211 00:10:56,100 --> 00:10:59,900 Můžete nastavit ji na hodnotu NULL, jen aby Ujistěte se, že všechny vaše základny jsou pokryty 212 00:10:59,900 --> 00:11:04,070 než tak učiníte, že jakékoliv přeřazení jste vždy zaručeno, že to bude 213 00:11:04,070 --> 00:11:08,880 ukazovat na konkrétní hodnotu proti jako hodnotu odpadky. 214 00:11:08,880 --> 00:11:12,210 Vzhledem k tomu, jo, přiřadíme nové další automaticky, 215 00:11:12,210 --> 00:11:15,420 ale je to více, stejně jako dobré praxe k inicializaci 216 00:11:15,420 --> 00:11:19,270 tímto způsobem a pak přiřadit. 217 00:11:19,270 --> 00:11:23,420 >> OK, tak dvojnásob spojových seznamů teď. 218 00:11:23,420 --> 00:11:24,601 Co si myslíme? 219 00:11:24,601 --> 00:11:26,350 To, co je s dvojnásobně spojené seznamy? 220 00:11:26,350 --> 00:11:30,750 221 00:11:30,750 --> 00:11:34,300 >> Takže v našich spojových seznamů, můžeme pohybovat pouze v jednom směru, ne? 222 00:11:34,300 --> 00:11:35,270 Máme jen dál. 223 00:11:35,270 --> 00:11:36,760 Můžeme jít jen dopředu. 224 00:11:36,760 --> 00:11:40,300 >> S dvojnásobně spojový seznam, můžeme také přesunout zpět. 225 00:11:40,300 --> 00:11:44,810 Takže máme nejen Číslo, které chceme uložit, 226 00:11:44,810 --> 00:11:50,110 máme tam, kde poukazuje na další a tam, kde jsme právě přišli. 227 00:11:50,110 --> 00:11:52,865 Takže to umožňuje některé lepší průchod. 228 00:11:52,865 --> 00:11:56,620 229 00:11:56,620 --> 00:12:01,240 >> Tak dvojnásobně spojené uzly, velmi podobné, ne? 230 00:12:01,240 --> 00:12:05,000 Jediným rozdílem je teď mají další a předchozí. 231 00:12:05,000 --> 00:12:06,235 To je jediný rozdíl. 232 00:12:06,235 --> 00:12:09,570 233 00:12:09,570 --> 00:12:14,790 >> Takže pokud bychom měli předřadit nebo append-- jsme nemají žádný kód pro tento up here-- 234 00:12:14,790 --> 00:12:17,830 ale pokud jste byli, aby se pokusila vložte ji na důležitou věc 235 00:12:17,830 --> 00:12:19,980 je třeba, aby že jste přiřazení 236 00:12:19,980 --> 00:12:23,360 jak vaše předchozí a vaše další ukazatel správně. 237 00:12:23,360 --> 00:12:29,010 Takže v tomto případě byste nejen inicializovat další, 238 00:12:29,010 --> 00:12:31,820 inicializaci předchozí. 239 00:12:31,820 --> 00:12:36,960 Pokud jsme v čele seznamu jsme by hlava rovná nové nejen, 240 00:12:36,960 --> 00:12:41,750 ale náš nový předchozí měl poukazují na hlavu, ne? 241 00:12:41,750 --> 00:12:43,380 >> To je jediný rozdíl. 242 00:12:43,380 --> 00:12:47,200 A pokud budete chtít více praxe s je s spojových seznamů, s vložením, 243 00:12:47,200 --> 00:12:49,900 s mazáním, s vložkou do tříděného seznamu 244 00:12:49,900 --> 00:12:52,670 prosím, podívejte se study.cs50.net. 245 00:12:52,670 --> 00:12:54,870 Je tu spousta skvělých cvičení. 246 00:12:54,870 --> 00:12:55,870 Vřele doporučuji je. 247 00:12:55,870 --> 00:12:59,210 Přál bych si, abychom měli čas jít přes ně ale je tu spousta datových struktur 248 00:12:59,210 --> 00:13:01,530 projít. 249 00:13:01,530 --> 00:13:02,650 >> OK, tak hash tabulky. 250 00:13:02,650 --> 00:13:07,070 Toto je pravděpodobně nejvíce užitečné bit pro pset 251 00:13:07,070 --> 00:13:11,090 tady, protože budete mít realizaci jednoho z nich, nebo zkusit. 252 00:13:11,090 --> 00:13:12,200 Moc se mi líbí hash tabulky. 253 00:13:12,200 --> 00:13:13,110 Jsou to docela v pohodě. 254 00:13:13,110 --> 00:13:17,080 >> Takže v podstatě to, co se stane, je hash tabulka 255 00:13:17,080 --> 00:13:22,050 je, když opravdu potřebujete rychlé vkládání, mazání a vyhledávání. 256 00:13:22,050 --> 00:13:25,010 To jsou věci, které jsme priorit v hash tabulce. 257 00:13:25,010 --> 00:13:29,500 Mohou se dostat docela velký, ale jak uvidíme se pokusech, 258 00:13:29,500 --> 00:13:33,040 tam jsou věci, které jsou mnohem větší. 259 00:13:33,040 --> 00:13:38,330 >> Ale v podstatě, všechny hash Tabulka je hašovací funkce 260 00:13:38,330 --> 00:13:47,215 že vám řekne, které kbelík, aby každý vašich dat, každý z vašich prvků. 261 00:13:47,215 --> 00:13:51,140 Jednoduchý způsob, jak myslet na hash tabulky je, že je to jen kbelíky věcí, 262 00:13:51,140 --> 00:13:51,770 že jo? 263 00:13:51,770 --> 00:13:59,720 Takže když se třídění věcí podle stejně jako první písmeno svého jména, 264 00:13:59,720 --> 00:14:01,820 to je něco jako hash tabulky. 265 00:14:01,820 --> 00:14:06,180 >> Takže vy, kdybych skupiny je do skupin, kdo začíná jméno 266 00:14:06,180 --> 00:14:11,670 se tady, nebo ten, kdo má narozeniny v lednu, únoru, březnu, 267 00:14:11,670 --> 00:14:15,220 co, že je účinně vytvoření hash tabulky. 268 00:14:15,220 --> 00:14:18,120 Je to jen vytváření kbelíky, že můžete třídit elementy do 269 00:14:18,120 --> 00:14:19,520 takže si můžete najít je jednodušší. 270 00:14:19,520 --> 00:14:22,300 Takže tímto způsobem, když jsem služeb najít jeden z vás, 271 00:14:22,300 --> 00:14:24,680 Nemám na vyhledávání přes každého z vašich jmen. 272 00:14:24,680 --> 00:14:29,490 Můžu být rád, oh, já vím, že Danielle má narozeniny in-- 273 00:14:29,490 --> 00:14:30,240 Diváků: --April. 274 00:14:30,240 --> 00:14:30,948 Reproduktor 1: duben. 275 00:14:30,948 --> 00:14:33,120 Tak jsem se podívat do mého duben kbelík, a s trochou štěstí 276 00:14:33,120 --> 00:14:38,270 že bude pouze jeden tam a můj čas byl konstantní v tom smyslu, 277 00:14:38,270 --> 00:14:41,230 vzhledem k tomu, když jsem se podívat přes spoustu lidí, 278 00:14:41,230 --> 00:14:43,090 že to bude trvat mnohem déle. 279 00:14:43,090 --> 00:14:45,830 Takže hash tabulky jsou opravdu jen lopaty. 280 00:14:45,830 --> 00:14:48,630 Snadný způsob, jak si o nich myslíte. 281 00:14:48,630 --> 00:14:52,930 >> Takže velmi důležitá věc, o hash tabulka je hašovací funkce. 282 00:14:52,930 --> 00:14:58,140 Takže věci, které jsem právě mluvil, jako vaše první písmeno vašeho jména 283 00:14:58,140 --> 00:15:01,450 nebo vaše narozeniny měsíc jsou to myšlenky, které 284 00:15:01,450 --> 00:15:03,070 Opravdu korelaci s hashovací funkce. 285 00:15:03,070 --> 00:15:08,900 Je to jen způsob, jak rozhodnout, které vědro Jsi element jde do, OK? 286 00:15:08,900 --> 00:15:14,850 Takže pro tento pset, můžete se podívat na skoro žádné funkce hash chcete. 287 00:15:14,850 --> 00:15:16,030 >> Nemusí to být vaše vlastní. 288 00:15:16,030 --> 00:15:21,140 Tam jsou některé z nich opravdu cool out tam, že dělat všechny druhy bláznivé matematiky. 289 00:15:21,140 --> 00:15:25,170 A pokud chcete, aby se vaše Kontrola pravopisu super rychlý, 290 00:15:25,170 --> 00:15:27,620 Já bych určitě podívejte se do jedné z nich. 291 00:15:27,620 --> 00:15:32,390 >> Ale jsou tu i jednoduchých, jako je výpočetně 292 00:15:32,390 --> 00:15:39,010 součet slov, jako je každé písmeno má číslo. 293 00:15:39,010 --> 00:15:39,940 Vypočtěte součet. 294 00:15:39,940 --> 00:15:42,230 Který určuje kbelík. 295 00:15:42,230 --> 00:15:45,430 Mají také ty jednoduché, že jsou stejně jako všechny je tady, 296 00:15:45,430 --> 00:15:47,050 všechny B je tady. 297 00:15:47,050 --> 00:15:48,920 Každý jeden z nich. 298 00:15:48,920 --> 00:15:55,770 >> V podstatě je to jen vám řekne, které index pole Váš element by měl jít do. 299 00:15:55,770 --> 00:15:58,690 Jen rozhodování o bucket-- je to všechno funkce hash. 300 00:15:58,690 --> 00:16:04,180 Takže tady máme příklad, který je jen první písmeno řetězce 301 00:16:04,180 --> 00:16:05,900 že jsem právě mluvil. 302 00:16:05,900 --> 00:16:11,900 >> Takže máte nějaké hash, který je právě první písmeno vašeho řetězce minus, 303 00:16:11,900 --> 00:16:16,090 která vám dá některé číslo mezi 0 a 25. 304 00:16:16,090 --> 00:16:20,790 A to, co chcete udělat, je ujistěte se, že se jedná 305 00:16:20,790 --> 00:16:24,110 velikost vašeho hash table-- kolik kbelíky jsou. 306 00:16:24,110 --> 00:16:25,860 S mnoha z nich hashovací funkce, jsou 307 00:16:25,860 --> 00:16:31,630 bude vracet hodnoty, které by mohly je daleko vyšší než počet segmentů 308 00:16:31,630 --> 00:16:33,610 že jste skutečně v hash tabulce, 309 00:16:33,610 --> 00:16:37,240 proto je třeba, aby Ujistěte se, a mod ti. 310 00:16:37,240 --> 00:16:42,190 V opačném případě to bude říkat, oh, měl by být v kbelíku 5000 311 00:16:42,190 --> 00:16:46,040 ale máte jen 30 kbelíky ve vašem hash tabulky. 312 00:16:46,040 --> 00:16:49,360 A samozřejmě, všichni víme, že je to bude mít za následek v některých šílených chyb. 313 00:16:49,360 --> 00:16:52,870 Takže se ujistěte, mod od Velikost vašeho hash tabulky. 314 00:16:52,870 --> 00:16:58,430 315 00:16:58,430 --> 00:16:58,930 V pohodě. 316 00:16:58,930 --> 00:17:00,506 Tak kolizí. 317 00:17:00,506 --> 00:17:02,620 Je každý dobrý tak daleko? 318 00:17:02,620 --> 00:17:03,120 Mmhmm? 319 00:17:03,120 --> 00:17:05,900 >> Diváků: Proč by to vrátit se tak masivní hodnotu? 320 00:17:05,900 --> 00:17:09,210 >> SPEAKER 1: V závislosti na algoritmu že hash funkce využívá. 321 00:17:09,210 --> 00:17:12,270 Některé z nich budou dělat blázen násobení. 322 00:17:12,270 --> 00:17:16,270 A to je vše, jak dostat rovnoměrné rozdělení, 323 00:17:16,270 --> 00:17:18,490 tak to dělají některé opravdu bláznivé věci, někdy. 324 00:17:18,490 --> 00:17:20,960 To je všechno. 325 00:17:20,960 --> 00:17:22,140 Ještě něco? 326 00:17:22,140 --> 00:17:22,829 OK. 327 00:17:22,829 --> 00:17:24,480 >> Tak kolizí. 328 00:17:24,480 --> 00:17:29,270 V podstatě, jak jsem již řekl, v nejlepším případě, 329 00:17:29,270 --> 00:17:32,040 jakýkoliv kbelík se dívám do je bude mít jednu věc, 330 00:17:32,040 --> 00:17:34,160 takže nemám dívat na všechny, že jo? 331 00:17:34,160 --> 00:17:37,040 Já vím, že buď tam, nebo je to ne, a to je to, co opravdu chceme. 332 00:17:37,040 --> 00:17:43,960 Ale máme-li desítky tisíc datových bodů a méně než tento počet 333 00:17:43,960 --> 00:17:48,700 lopat, budeme mít kolize, kde nakonec něco 334 00:17:48,700 --> 00:17:54,210 bude muset skončit v kbelík, který již má prvek. 335 00:17:54,210 --> 00:17:57,390 >> Takže otázka je, co budeme dělat v tomto případě? 336 00:17:57,390 --> 00:17:58,480 Co budeme dělat? 337 00:17:58,480 --> 00:17:59,300 Už jsme tam něco mít? 338 00:17:59,300 --> 00:18:00,060 Máme jen vyhodit? 339 00:18:00,060 --> 00:18:00,700 >> Ne. 340 00:18:00,700 --> 00:18:01,980 Musíme mít na obou z nich. 341 00:18:01,980 --> 00:18:06,400 Tak tak, že jsme obvykle to udělat je to, co? 342 00:18:06,400 --> 00:18:08,400 Co je datová struktura jsme právě mluvili? 343 00:18:08,400 --> 00:18:09,316 Diváků: spojový seznam. 344 00:18:09,316 --> 00:18:10,500 SPEAKER 1: spojový seznam. 345 00:18:10,500 --> 00:18:16,640 Takže teď, místo toho, každá z nich kbelíky jen mít jeden prvek, 346 00:18:16,640 --> 00:18:24,020 to bude obsahovat propojený seznam prvky, které byly zatříděna do něj. 347 00:18:24,020 --> 00:18:27,588 OK, to každý druh si tuto myšlenku? 348 00:18:27,588 --> 00:18:30,546 Protože jsme nemohli mít pole protože nevíme, jak mnoho věcí, 349 00:18:30,546 --> 00:18:31,730 se bude tam. 350 00:18:31,730 --> 00:18:36,540 Spojový seznam nám umožňuje máme jen přesný počet, který 351 00:18:36,540 --> 00:18:38,465 jsou zatříděna do tohoto kbelíku, ne? 352 00:18:38,465 --> 00:18:42,260 353 00:18:42,260 --> 00:18:50,500 >> Takže lineární sondování je v podstatě to idea-- 354 00:18:50,500 --> 00:18:52,300 to je jeden způsob, jak se vypořádat s bočním nárazu. 355 00:18:52,300 --> 00:18:58,010 Co můžete udělat, je, pokud v tomto případ, bobulové byla zatříděna do 1 356 00:18:58,010 --> 00:19:01,130 a už máme něco, co tam prostě 357 00:19:01,130 --> 00:19:04,840 dál, dokud najdete na prázdnou pozici. 358 00:19:04,840 --> 00:19:06,370 To je jediný způsob, jak s ní zacházet. 359 00:19:06,370 --> 00:19:09,020 Druhý způsob, jak zvládnout je to s tím, co jsme právě 360 00:19:09,020 --> 00:19:12,280 called-- spojené seznam se nazývá zřetězení. 361 00:19:12,280 --> 00:19:20,510 >> Takže tato myšlenka funguje, pokud vaše hash tabulky si myslíte 362 00:19:20,510 --> 00:19:24,150 je mnohem větší, než Vaše údaje nastavit nebo pokud vás 363 00:19:24,150 --> 00:19:28,870 zkusit a minimalizovat řetězení dokud je to nezbytně nutné. 364 00:19:28,870 --> 00:19:34,050 Takže jedna věc je lineární sondování samozřejmě znamená, 365 00:19:34,050 --> 00:19:37,290 že vaše hash funkce není tak užitečný 366 00:19:37,290 --> 00:19:42,200 protože budete skončit s použitím vaše hash funkce, dostat do bodu, 367 00:19:42,200 --> 00:19:46,400 jste LINEAR sondy až do nějaké místo, které je k dispozici. 368 00:19:46,400 --> 00:19:49,670 Ale teď, samozřejmě, cokoliv jiný, že skončí tam, 369 00:19:49,670 --> 00:19:52,050 budete muset hledat ještě dál. 370 00:19:52,050 --> 00:19:55,650 >> A je tu mnohem víc Hledání náklady, které 371 00:19:55,650 --> 00:19:59,820 jde do zadání prvek v hash tabulce, ne? 372 00:19:59,820 --> 00:20:05,640 A teď, když jdete a pokusit se najít berry znovu, budete to hash, 373 00:20:05,640 --> 00:20:07,742 a to bude říkat, oh, podívejte se do kbelíku 1, 374 00:20:07,742 --> 00:20:09,700 a to nebude v kbelíku 1, takže jste 375 00:20:09,700 --> 00:20:11,970 bude muset projít přes zbytek z nich. 376 00:20:11,970 --> 00:20:17,720 Tak to je někdy užitečná, ale ve většině případů, 377 00:20:17,720 --> 00:20:22,660 budeme říkat, že řetězení je to, co chcete dělat. 378 00:20:22,660 --> 00:20:25,520 >> Tak jsme o tom mluvili dříve. 379 00:20:25,520 --> 00:20:27,812 Dostal jsem kousek před sebe. 380 00:20:27,812 --> 00:20:33,560 Ale řetězení je v podstatě, že každý kbelík v hash tabulce 381 00:20:33,560 --> 00:20:36,120 je jen spojový seznam. 382 00:20:36,120 --> 00:20:39,660 >> Takže další způsob, nebo více technických způsobem, myslet na hash tabulky 383 00:20:39,660 --> 00:20:44,490 je to, že je to jen pole spojových seznamů, které 384 00:20:44,490 --> 00:20:49,330 když jste psaní slovník a vy se snažíte načíst, 385 00:20:49,330 --> 00:20:52,070 myslet na to, jak pole spojových seznamů 386 00:20:52,070 --> 00:20:54,390 bude to mnohem jednodušší pro vás inicializovat. 387 00:20:54,390 --> 00:20:57,680 >> Diváků: Tak hash tabulka má předem určenou velikost, 388 00:20:57,680 --> 00:20:58,980 jako [neslyšitelné] lopat? 389 00:20:58,980 --> 00:20:59,220 >> SPEAKER 1: Správně. 390 00:20:59,220 --> 00:21:01,655 Tak to má stanovený počet kbelíky, že jste determine-- 391 00:21:01,655 --> 00:21:03,530 které jste kluci měli klidně hrát. 392 00:21:03,530 --> 00:21:05,269 To může být docela v pohodě aby viděli, co se stane, 393 00:21:05,269 --> 00:21:06,810 jak si změnit počet segmentů. 394 00:21:06,810 --> 00:21:09,410 395 00:21:09,410 --> 00:21:11,510 Ale jo, to má nastavit počet segmentů. 396 00:21:11,510 --> 00:21:15,360 Co umožňuje, aby se vešly jako mnoho prvků, jak budete potřebovat 397 00:21:15,360 --> 00:21:19,350 je oddělen řetězení, kde vás spojili seznamy v každém segmentu. 398 00:21:19,350 --> 00:21:22,850 To znamená, že vaše hash tabulky bude přesně velikost 399 00:21:22,850 --> 00:21:25,440 že ji musí být, ne? 400 00:21:25,440 --> 00:21:27,358 To je celý smysl spojových seznamů. 401 00:21:27,358 --> 00:21:30,850 402 00:21:30,850 --> 00:21:32,480 V pohodě. 403 00:21:32,480 --> 00:21:38,780 >> Takže tam všichni v pořádku? 404 00:21:38,780 --> 00:21:39,801 Dobrá. 405 00:21:39,801 --> 00:21:40,300 Ah. 406 00:21:40,300 --> 00:21:41,860 Co se stalo? 407 00:21:41,860 --> 00:21:42,960 Opravdu teď. 408 00:21:42,960 --> 00:21:45,250 Hádejte, někdo mě zabíjí. 409 00:21:45,250 --> 00:21:52,060 >> OK budeme jít do pokusů, které jsou trochu blázen. 410 00:21:52,060 --> 00:21:53,140 Mám rád hash tabulky. 411 00:21:53,140 --> 00:21:54,460 Myslím, že jsou opravdu cool. 412 00:21:54,460 --> 00:21:56,710 Pokusy jsou v pohodě, taky. 413 00:21:56,710 --> 00:21:59,590 >> Takže má někdo vzpomenout, co to zkusit je? 414 00:21:59,590 --> 00:22:01,740 Měli jste přešli stručně v přednášce? 415 00:22:01,740 --> 00:22:04,570 416 00:22:04,570 --> 00:22:06,377 Vzpomínáte si druh, jak to funguje? 417 00:22:06,377 --> 00:22:08,460 Diváků: Jen jsem kývl že jsme se jít přes něj. 418 00:22:08,460 --> 00:22:09,626 SPEAKER 1: Nemáme jít přes něj. 419 00:22:09,626 --> 00:22:13,100 OK, jsme opravdu jít nad ní je nyní to, co říkáme. 420 00:22:13,100 --> 00:22:14,860 >> Diváků: To je pro vyhledávacím stromu. 421 00:22:14,860 --> 00:22:15,280 >> SPEAKER 1: Jo. 422 00:22:15,280 --> 00:22:16,196 Je to získávání strom. 423 00:22:16,196 --> 00:22:16,960 Úžasné. 424 00:22:16,960 --> 00:22:23,610 Takže jedna věc je si všimnout je, že jsme jsou při pohledu na jednotlivé znaky 425 00:22:23,610 --> 00:22:24,480 tady, že jo? 426 00:22:24,480 --> 00:22:29,710 >> Takže před naší hash funkcí, jsme se dívali na slova jako celku, 427 00:22:29,710 --> 00:22:32,270 a teď se díváme více na znaky, ne? 428 00:22:32,270 --> 00:22:38,380 Takže máme Maxwell sem a Mendel. 429 00:22:38,380 --> 00:22:47,840 Takže v podstatě try-- způsob, jak myslet o tom, že každý stupeň je zde 430 00:22:47,840 --> 00:22:49,000 je řada písmen. 431 00:22:49,000 --> 00:22:53,310 432 00:22:53,310 --> 00:22:55,790 Takže tohle je váš kořenový uzel tady, že jo? 433 00:22:55,790 --> 00:23:01,980 To má všechny znaky abeceda na začátku každého slova. 434 00:23:01,980 --> 00:23:06,480 >> A to, co chcete udělat, je řekněme, OK, máme nějaké M slovo. 435 00:23:06,480 --> 00:23:10,590 Jedeme se podívat na Maxwell, tak jedeme do M. a M bodů na celý 436 00:23:10,590 --> 00:23:14,800 další pole, kde každý slovo, pokud tam 437 00:23:14,800 --> 00:23:17,044 je slovo, které má jako druhé písmeno, 438 00:23:17,044 --> 00:23:19,460 jak dlouho jak tam je to slovo, které má B jako druhé písmeno, 439 00:23:19,460 --> 00:23:24,630 bude mít ukazatel bude nějaké další pole. 440 00:23:24,630 --> 00:23:29,290 >> Je tu asi není slovo, které MP něco, 441 00:23:29,290 --> 00:23:32,980 takže v poloze P v této pole, bylo by to prostě být NULL. 442 00:23:32,980 --> 00:23:38,840 To by řekl, OK, není slovo který M následované P, OK? 443 00:23:38,840 --> 00:23:43,100 Takže pokud si myslíme, že o tom, každý jeden z těchto menších věcí 444 00:23:43,100 --> 00:23:47,990 je ve skutečnosti jedna z nich velké pole od A až Z. 445 00:23:47,990 --> 00:23:55,064 Takže to, co by mohlo být jednou z věcí, že je tak trochu navracení zkusit? 446 00:23:55,064 --> 00:23:56,500 >> Diváků: hodně paměti. 447 00:23:56,500 --> 00:23:59,940 >> SPEAKER 1: Je to ton paměti, že jo? 448 00:23:59,940 --> 00:24:08,750 Každý z těchto bloků zde představuje 26 míst, 26 prvků pole. 449 00:24:08,750 --> 00:24:13,680 Takže se snaží dostat neuvěřitelně prostor těžké. 450 00:24:13,680 --> 00:24:17,100 >> Ale oni jsou velmi rychlé. 451 00:24:17,100 --> 00:24:22,540 Tak neuvěřitelně rychle, ale Opravdu prostor neefektivní. 452 00:24:22,540 --> 00:24:24,810 Druh přijít který z nich chcete. 453 00:24:24,810 --> 00:24:29,470 Jedná se o opravdu cool pro pset, ale oni zabírají hodně paměti, 454 00:24:29,470 --> 00:24:30,290 takže si přivlastnit. 455 00:24:30,290 --> 00:24:31,480 Jo? 456 00:24:31,480 --> 00:24:34,300 >> Diváků: Bylo by možné nastavit vyzkoušet a pak se 457 00:24:34,300 --> 00:24:37,967 Jakmile budete mít všechny údaje v něm, že jste need-- 458 00:24:37,967 --> 00:24:39,550 Já nevím, jestli to bude mít smysl. 459 00:24:39,550 --> 00:24:42,200 Byl jsem jak se zbavit všech Znaky NULL, ale pak 460 00:24:42,200 --> 00:24:42,910 nebudete moci indexu them-- 461 00:24:42,910 --> 00:24:43,275 >> SPEAKER 1: Stále potřebují. 462 00:24:43,275 --> 00:24:44,854 >> Diváků: - stejným způsobem pokaždé. 463 00:24:44,854 --> 00:24:45,520 SPEAKER 1: Jo. 464 00:24:45,520 --> 00:24:50,460 Musíte se znaky NULL, aby víte-li, že to není tam slovo. 465 00:24:50,460 --> 00:24:52,040 Ben se máte něco, co chcete? 466 00:24:52,040 --> 00:24:52,540 OK. 467 00:24:52,540 --> 00:24:54,581 Tak jo, jdeme jít trochu více 468 00:24:54,581 --> 00:24:58,920 do technických podrobností za snažit a pracovat na příkladu. 469 00:24:58,920 --> 00:25:01,490 >> OK, tak je to to samé. 470 00:25:01,490 --> 00:25:06,290 Vzhledem k tomu, v propojeném seznamu, naše hlavní druh of-- co je to slovo, které jsem chtěl? - 471 00:25:06,290 --> 00:25:08,350 jako stavební blok byl uzel. 472 00:25:08,350 --> 00:25:12,280 V pokusu, máme také uzel, ale je to definováno jinak. 473 00:25:12,280 --> 00:25:17,000 >> Takže máme nějaký bool, že znamená, zda slova skutečně 474 00:25:17,000 --> 00:25:23,530 existuje na tomto místě, a pak máme nějaké pole here-- nebo spíše, 475 00:25:23,530 --> 00:25:27,840 To je ukazatel na Pole 27 znaků. 476 00:25:27,840 --> 00:25:33,339 A to je pro, v tomto případě, to 27-- Jsem si jist, všichni z vás jsou jako, počkejte, 477 00:25:33,339 --> 00:25:34,880 tam je 26 písmen v abecedě. 478 00:25:34,880 --> 00:25:36,010 Proč máme 27? 479 00:25:36,010 --> 00:25:37,870 >> Takže v závislosti na způsob, jak realizovat to, 480 00:25:37,870 --> 00:25:43,240 To je z pset, že povoleno apostrofy. 481 00:25:43,240 --> 00:25:46,010 Takže to je důvod, proč navíc jeden. 482 00:25:46,010 --> 00:25:50,500 Budete mít také v některých případy null terminačních 483 00:25:50,500 --> 00:25:53,230 je zahrnuta jako jeden z znaky, že to nemá být, 484 00:25:53,230 --> 00:25:56,120 a to je to, jak zkontrolovat, zjistit, jestli je to konec slova. 485 00:25:56,120 --> 00:26:01,340 Máte-li zájem, podívejte se Kevin video na study.cs50, 486 00:26:01,340 --> 00:26:04,790 jakož i Wikipedia má některé dobré zdroje tam. 487 00:26:04,790 --> 00:26:09,000 >> Ale my jdeme projít jen tak o tom, jak můžete pracovat na pokus 488 00:26:09,000 --> 00:26:11,010 pokud jste dal dnes. 489 00:26:11,010 --> 00:26:16,230 Takže tu máme super jednoduchá tady, že má slova "BAT" a "zoom" v nich. 490 00:26:16,230 --> 00:26:18,920 A jak vidíme tady, tento malý prostor zde 491 00:26:18,920 --> 00:26:22,560 reprezentuje naši bool, že říká, ano, je to slovo. 492 00:26:22,560 --> 00:26:27,060 A pak to má naši pole znaků, ne? 493 00:26:27,060 --> 00:26:33,480 >> Tak jsme se jít přes hledání "BAT" v tomto pokusu. 494 00:26:33,480 --> 00:26:38,340 Takže začít nahoře, ne? 495 00:26:38,340 --> 00:26:46,290 A my víme, že b odpovídá druhý index, druhý prvek 496 00:26:46,290 --> 00:26:47,840 V tomto poli, protože a b. 497 00:26:47,840 --> 00:26:51,340 Takže přibližně druhý. 498 00:26:51,340 --> 00:26:58,820 >> A říká, OK, v pohodě, z toho, že do další pole, protože když si vzpomeneme, 499 00:26:58,820 --> 00:27:02,160 je to tak, že každý z nich ve skutečnosti obsahuje prvek. 500 00:27:02,160 --> 00:27:07,110 Každý jeden z těchto polí obsahuje ukazatel, že jo? 501 00:27:07,110 --> 00:27:10,030 To je důležitý rozdíl, aby se. 502 00:27:10,030 --> 00:27:13,450 >> Vím, že to bude be-- snaží se opravdu těžké se dostat na poprvé, 503 00:27:13,450 --> 00:27:15,241 takže i když je to druhý nebo třetí čas 504 00:27:15,241 --> 00:27:18,370 a je to stále trochu ze zdánlivě obtížné, 505 00:27:18,370 --> 00:27:21,199 Slibuji, že když jdete na hodinky zítra krátký znovu, 506 00:27:21,199 --> 00:27:22,740 to bude asi dělat mnohem větší smysl. 507 00:27:22,740 --> 00:27:23,890 To trvá hodně trávit. 508 00:27:23,890 --> 00:27:27,800 Já ještě někdy jsem jako, počkej, co je to vyzkoušet? 509 00:27:27,800 --> 00:27:29,080 Jak mám použít? 510 00:27:29,080 --> 00:27:33,880 >> Proto jsme B v tomto případě, který je naším druhým index. 511 00:27:33,880 --> 00:27:40,240 Kdybychom měli, řekněme, c nebo d nebo jiné písmeno, 512 00:27:40,240 --> 00:27:45,810 musíme zmapovat to zpátky do indexu našeho pole, které, které odpovídá. 513 00:27:45,810 --> 00:27:56,930 Tak bychom brát jako rchar a my jsme odečíst off mapovat do 0 do 25. 514 00:27:56,930 --> 00:27:58,728 Všichni dobře, jak Mapa naše postavy? 515 00:27:58,728 --> 00:28:00,440 OK. 516 00:28:00,440 --> 00:28:05,980 >> Tak jdeme na druhou a my vidět, že, ano, to není NULL. 517 00:28:05,980 --> 00:28:07,780 Můžeme přejít k tomuto dalšímu poli. 518 00:28:07,780 --> 00:28:12,300 Tak jdeme na této další pole zde. 519 00:28:12,300 --> 00:28:15,500 >> A my říkáme, OK, teď je třeba zjistit, jestli je tady. 520 00:28:15,500 --> 00:28:18,590 Je null nebo to dělá vlastně vpřed? 521 00:28:18,590 --> 00:28:21,880 Tak vlastně pohybuje předal v tomto poli. 522 00:28:21,880 --> 00:28:24,570 A my říkáme, OK, t je náš poslední písmeno. 523 00:28:24,570 --> 00:28:27,580 Tak jsme se jít do t na indexu. 524 00:28:27,580 --> 00:28:30,120 A pak jsme se kupředu protože je tu ještě jeden. 525 00:28:30,120 --> 00:28:38,340 A tohle říká v podstatě to, že ano, se říká, že je slovo here-- 526 00:28:38,340 --> 00:28:41,750 že pokud budete postupovat podle tohoto cesta, jste dorazili 527 00:28:41,750 --> 00:28:43,210 na slova, která jak víme, je "bat". 528 00:28:43,210 --> 00:28:43,800 Ano? 529 00:28:43,800 --> 00:28:46,770 >> Diváků: Je standardní, aby toto jako index 0 a pak jakousi na 1 530 00:28:46,770 --> 00:28:47,660 nebo mít na konci? 531 00:28:47,660 --> 00:28:48,243 >> SPEAKER 1: Ne 532 00:28:48,243 --> 00:28:55,360 Takže pokud se podíváme zpět na naší Prohlášení tady, je to bool, 533 00:28:55,360 --> 00:28:59,490 tak je to jeho vlastní element v uzlu. 534 00:28:59,490 --> 00:29:03,331 Takže to není součástí pole. 535 00:29:03,331 --> 00:29:03,830 V pohodě. 536 00:29:03,830 --> 00:29:08,370 Takže když jsme dokončit naše slovo a my jsme na tomto poli, to, co chceme dělat 537 00:29:08,370 --> 00:29:12,807 je provést kontrolu na toto slovo. 538 00:29:12,807 --> 00:29:14,390 A v tomto případě by to vrátit ano. 539 00:29:14,390 --> 00:29:17,220 540 00:29:17,220 --> 00:29:24,090 >> Takže v takovém případě, víme, že "zoo" - známe jako člověka, který "zoo" je slovo, 541 00:29:24,090 --> 00:29:24,820 že jo? 542 00:29:24,820 --> 00:29:28,990 Ale zkusit by zde říkají, ne, to ne. 543 00:29:28,990 --> 00:29:33,980 A to bych řekl, že proto, že jsme nebyly označeny jako slovo zde. 544 00:29:33,980 --> 00:29:40,440 I přesto, že můžeme přejít až do tohoto pole, 545 00:29:40,440 --> 00:29:43,890 Tento pokus by řekl, že ne, zoo není ve slovníku 546 00:29:43,890 --> 00:29:47,070 protože nemáme označeny jako takové. 547 00:29:47,070 --> 00:29:52,870 >> Takže jeden způsob, jak to udělat that-- oh, sorry, tohle. 548 00:29:52,870 --> 00:29:59,450 Takže v tomto případě, "zoo" není slovo, ale to je v našem pokusu. 549 00:29:59,450 --> 00:30:05,690 Ale v tomto jednom, že bychom si to přejí představit slovo "lázně", co se stane, 550 00:30:05,690 --> 00:30:08,260 je sledujeme through-- B, A, t. 551 00:30:08,260 --> 00:30:11,820 Jsme v tomto poli, a jdeme hledat h. 552 00:30:11,820 --> 00:30:15,220 >> V tomto případě, kdy se podívat na ukazatel na h, 553 00:30:15,220 --> 00:30:17,890 to ukazuje na NULL, OK? 554 00:30:17,890 --> 00:30:20,780 Takže pokud je to výslovně ukázal na jiné pole, 555 00:30:20,780 --> 00:30:25,000 předpokládat, že všechny ukazatele V tomto poli se ukazuje na hodnotu null. 556 00:30:25,000 --> 00:30:28,270 Takže v tomto případě, h se ukazuje na hodnotu null, takže nemůžeme nic dělat, 557 00:30:28,270 --> 00:30:31,540 tak to by také vrátit false, "koupel" není tady. 558 00:30:31,540 --> 00:30:34,102 559 00:30:34,102 --> 00:30:35,810 Takže teď jsme vlastně jít přes 560 00:30:35,810 --> 00:30:39,790 jak bychom vlastně říci, že "zoo" má v našem pokusu. 561 00:30:39,790 --> 00:30:42,920 Jak můžeme vložit "zoo" do našeho pokusu? 562 00:30:42,920 --> 00:30:47,810 Takže stejným způsobem, jako jsme začali náš spojový seznam, začneme u kořene. 563 00:30:47,810 --> 00:30:50,600 Pokud jste na pochybách, začněte kořen z těchto věcí. 564 00:30:50,600 --> 00:30:53,330 >> A budeme říkat, OK, z. 565 00:30:53,330 --> 00:30:55,650 z existuje v této, a to dělá. 566 00:30:55,650 --> 00:30:58,370 Takže jste se přestěhovali na váš další pole, OK? 567 00:30:58,370 --> 00:31:01,482 A pak na další, říkáme, OK, to o existuje? 568 00:31:01,482 --> 00:31:03,000 To dělá. 569 00:31:03,000 --> 00:31:04,330 To znovu. 570 00:31:04,330 --> 00:31:08,670 >> A tak se na naší další, jsme řekli, OK, "zoo" už tady existuje. 571 00:31:08,670 --> 00:31:12,440 Vše, co musíme udělat, je nastavit to rovná na pravda, že je tam slovo. 572 00:31:12,440 --> 00:31:15,260 Pokud jste sledoval všechno až do tohoto bodu, 573 00:31:15,260 --> 00:31:17,030 je to slovo, tak jen nastavte ji na hodnotu, např. 574 00:31:17,030 --> 00:31:17,530 Ano? 575 00:31:17,530 --> 00:31:22,550 >> Diváků: Tak to dělá znamená, že "ba" je slovo, které také? 576 00:31:22,550 --> 00:31:24,120 >> SPEAKER 1: Ne 577 00:31:24,120 --> 00:31:28,870 Takže v tomto případě, "ba" bychom se dostali Zde bychom říci, je to slovo, 578 00:31:28,870 --> 00:31:31,590 a stále by být. 579 00:31:31,590 --> 00:31:32,822 OK? 580 00:31:32,822 --> 00:31:33,740 Mmhmm? 581 00:31:33,740 --> 00:31:36,360 >> Diváků: Takže jakmile je to slovo, a vy říkáte ano, pak to 582 00:31:36,360 --> 00:31:38,380 bude obsahovat jít do m? 583 00:31:38,380 --> 00:31:42,260 >> SPEAKER 1: Tak to má co do činění with-- jste načítá to v. 584 00:31:42,260 --> 00:31:43,640 Říkáte, že "zoo" je slovo. 585 00:31:43,640 --> 00:31:47,020 Když jdete do check-- jako, že chcete říct, 586 00:31:47,020 --> 00:31:49,400 znamená "zoo" existují v tomto slovníku? 587 00:31:49,400 --> 00:31:54,200 Jste jen bude hledat "zoo" a pak zkontrolujte, zda je to slovo. 588 00:31:54,200 --> 00:31:57,291 Vy jste nikdy pohybovat až m, protože to není 589 00:31:57,291 --> 00:31:58,290 to, co hledáte. 590 00:31:58,290 --> 00:32:02,690 591 00:32:02,690 --> 00:32:08,070 >> Pokud tedy vlastně chtěl přidat "koupel" v tomto pokusu, 592 00:32:08,070 --> 00:32:11,390 budeme dělat totéž jako jsme to udělali s "zoo" 593 00:32:11,390 --> 00:32:15,380 s výjimkou bychom vidět, že když jsme pokusit se dostat h, to neexistuje. 594 00:32:15,380 --> 00:32:20,090 Takže si můžete myslet na to, jak se snaží pro přidání nového uzlu do propojeného seznamu 595 00:32:20,090 --> 00:32:27,210 tak bychom museli přidat další jeden z těchto polí, jako tak. 596 00:32:27,210 --> 00:32:35,670 A pak to, co děláme, je prostě nastavit h prvek tohoto pole ukazuje na to. 597 00:32:35,670 --> 00:32:39,430 >> A pak to, co by chtěl dělat? 598 00:32:39,430 --> 00:32:43,110 Přidat se rovná pravda protože je to slovo. 599 00:32:43,110 --> 00:32:46,350 600 00:32:46,350 --> 00:32:48,150 V pohodě. 601 00:32:48,150 --> 00:32:48,700 Já vím. 602 00:32:48,700 --> 00:32:51,170 Pokusy nejsou nejvíce vzrušující. 603 00:32:51,170 --> 00:32:54,250 Věř mi, já vím. 604 00:32:54,250 --> 00:32:58,040 >> Takže jedna věc je si uvědomit, s pokusech, Řekl jsem, že jsou velmi efektivní. 605 00:32:58,040 --> 00:33:00,080 Proto jsme, viděli zabírají spoustu místa. 606 00:33:00,080 --> 00:33:01,370 Jsou to trochu matoucí. 607 00:33:01,370 --> 00:33:03,367 Tak proč bychom vůbec používat tyto? 608 00:33:03,367 --> 00:33:05,450 Používáme tyto, protože jsou neuvěřitelně efektivní. 609 00:33:05,450 --> 00:33:08,130 >> Takže pokud jste někdy hledáte up slova, jste jen 610 00:33:08,130 --> 00:33:10,450 ohraničené délkou slova. 611 00:33:10,450 --> 00:33:15,210 Takže pokud hledáte slovo, které je v délce pěti, 612 00:33:15,210 --> 00:33:20,940 jste jen někdy muset aby u většiny pěti srovnáních, OK? 613 00:33:20,940 --> 00:33:25,780 Takže je to v podstatě konstantní. 614 00:33:25,780 --> 00:33:29,150 Stejně jako vkládání a vyhledávání jsou v podstatě konstantní čas. 615 00:33:29,150 --> 00:33:33,750 >> Takže pokud můžete někdy něco v konstantním čase, 616 00:33:33,750 --> 00:33:35,150 je to tak dobré, jak to dostane. 617 00:33:35,150 --> 00:33:37,990 Nemůžete lepší než konstantní čas na tyto věci. 618 00:33:37,990 --> 00:33:43,150 Tak, že je jedním z obrovské plusy pokusů. 619 00:33:43,150 --> 00:33:46,780 >> Ale je to hodně prostoru. 620 00:33:46,780 --> 00:33:50,380 Takže tak nějak se rozhodnout, co je pro vás důležitější. 621 00:33:50,380 --> 00:33:54,700 A na dnešních počítačích, prostor, který pokus může trvat až 622 00:33:54,700 --> 00:33:57,740 Možná, že nemá vliv na si, že hodně, ale možná 623 00:33:57,740 --> 00:34:01,350 máte co do činění s něčím která má daleko, daleko více věcí, 624 00:34:01,350 --> 00:34:02,810 a pokus prostě není rozumné. 625 00:34:02,810 --> 00:34:03,000 Ano? 626 00:34:03,000 --> 00:34:05,610 >> Publikum: Počkej, takže budete mít 26 písmena jednoho každého? 627 00:34:05,610 --> 00:34:07,440 >> SPEAKER 1: Mmhmm. 628 00:34:07,440 --> 00:34:08,570 Jo, máte 26. 629 00:34:08,570 --> 00:34:16,984 Máte nějaký je slovo, značka a pak Máte 26 ukazatelů v každém jednom. 630 00:34:16,984 --> 00:34:17,775 A oni point-- 631 00:34:17,775 --> 00:34:20,280 >> Diváků: A každý 26, že každý z nich má 26? 632 00:34:20,280 --> 00:34:21,500 >> SPEAKER 1: Ano. 633 00:34:21,500 --> 00:34:27,460 A to je důvod, proč, jak můžete vidět, že se rozšiřuje velmi rychle. 634 00:34:27,460 --> 00:34:28,130 Dobrá. 635 00:34:28,130 --> 00:34:32,524 Takže budeme se dostat do stromů, které Mám pocit, že je jednodušší a pravděpodobně 636 00:34:32,524 --> 00:34:36,150 je pěkný malý odklad z pokusů tam. 637 00:34:36,150 --> 00:34:39,620 Takže doufejme, že většina z vás které viděl strom. 638 00:34:39,620 --> 00:34:41,820 Ne jako docela Ty mimo, které jsem 639 00:34:41,820 --> 00:34:44,340 nejsou-li někdo vědět šel venku v poslední době. 640 00:34:44,340 --> 00:34:49,230 Šel jsem jablko vychystávání tento víkend a oh můj bože, to bylo krásné. 641 00:34:49,230 --> 00:34:52,250 Nevěděl jsem, že listy může vypadat, že dost. 642 00:34:52,250 --> 00:34:53,610 >> Takže je to jen strom, ne? 643 00:34:53,610 --> 00:34:56,790 Je to jen nějaký uzel, a to poukazuje na spoustu dalších uzlů. 644 00:34:56,790 --> 00:34:59,570 Jak vidíte tady, je to druh opakující se téma. 645 00:34:59,570 --> 00:35:03,720 Uzly ukazující uzlů je druh Podstatou mnoha datových struktur. 646 00:35:03,720 --> 00:35:06,670 Záleží jen na tom, jak nechat upozornit na sebe 647 00:35:06,670 --> 00:35:08,600 a jak jsme se projít skrze ně a jak 648 00:35:08,600 --> 00:35:14,500 vložit věci, které určuje jejich odlišné charakteristiky. 649 00:35:14,500 --> 00:35:17,600 >> Takže jen některé pojmy, který jsem používal předtím. 650 00:35:17,600 --> 00:35:20,010 Tak root je to, co je na samém vrcholu. 651 00:35:20,010 --> 00:35:21,200 to je místo, kde jsme se vždy začít. 652 00:35:21,200 --> 00:35:23,610 Můžete si ji představit jako hlavy také. 653 00:35:23,610 --> 00:35:28,750 Ale stromy, máme tendenci odkazují na to jako root. 654 00:35:28,750 --> 00:35:32,820 >> Cokoliv na spodní here-- na velmi, velmi bottom-- 655 00:35:32,820 --> 00:35:34,500 jsou považovány za listy. 656 00:35:34,500 --> 00:35:37,210 Tak to jde ruku v ruce s Celý strom věc, ne? 657 00:35:37,210 --> 00:35:39,860 Listy jsou při okrajích stromu. 658 00:35:39,860 --> 00:35:45,820 >> A pak máme také pár Podmínky mluvit o uzlech ve vztahu 659 00:35:45,820 --> 00:35:46,680 k sobě navzájem. 660 00:35:46,680 --> 00:35:49,700 Takže máme rodiče, děti a sourozenci. 661 00:35:49,700 --> 00:35:56,260 Takže v tomto případě, je 3 rodič 5, 6 a 7. 662 00:35:56,260 --> 00:36:00,370 Takže rodič, co je o krok výše, co jste 663 00:36:00,370 --> 00:36:02,940 s odkazem na to, tak prostě jako rodokmen. 664 00:36:02,940 --> 00:36:07,090 Doufejme, že je to všechno trochu trochu více intuitivní než pokusů. 665 00:36:07,090 --> 00:36:10,970 >> Sourozenci jsou všechny, které mají stejná mateřská, ne? 666 00:36:10,970 --> 00:36:13,470 Jsou na stejné úrovni zde. 667 00:36:13,470 --> 00:36:16,960 A pak, když jsem byl říká, děti jsou jen 668 00:36:16,960 --> 00:36:22,630 co je jeden krok dále uzel v otázce, OK? 669 00:36:22,630 --> 00:36:23,470 V pohodě. 670 00:36:23,470 --> 00:36:25,610 Tak binární strom. 671 00:36:25,610 --> 00:36:31,450 Může někdo hádat, na jednom z vlastnosti binárního stromu? 672 00:36:31,450 --> 00:36:32,770 >> Diváků: Max dva lístky. 673 00:36:32,770 --> 00:36:33,478 >> SPEAKER 1: Správně. 674 00:36:33,478 --> 00:36:34,640 Takže max dvou listů. 675 00:36:34,640 --> 00:36:39,730 Takže v tomto jednom dříve, měli jsme tenhle která měla tři, ale v binárním stromu, 676 00:36:39,730 --> 00:36:45,000 Máte-max dvou dětí na rodiče, že jo? 677 00:36:45,000 --> 00:36:46,970 Je tu další zajímavá vlastnost. 678 00:36:46,970 --> 00:36:51,550 Ví někdo, že? 679 00:36:51,550 --> 00:36:52,620 Binární strom. 680 00:36:52,620 --> 00:37:00,350 >> Takže binární strom bude mít vše na the-- tohle není sorted-- 681 00:37:00,350 --> 00:37:05,320 ale v seřazené binárního stromu, vše na pravé straně 682 00:37:05,320 --> 00:37:08,530 je větší než původní, a vše, co na levé straně 683 00:37:08,530 --> 00:37:10,035 je menší než rodiče. 684 00:37:10,035 --> 00:37:15,690 A to byl kvíz Otázka před, tak dobré to vědět. 685 00:37:15,690 --> 00:37:19,500 Takže způsob, jak definovat to, opět máme další uzel. 686 00:37:19,500 --> 00:37:21,880 To vypadá velmi podobně jako co? 687 00:37:21,880 --> 00:37:28,336 688 00:37:28,336 --> 00:37:28,836 Dvojnásobně 689 00:37:28,836 --> 00:37:29,320 >> Diváků: spojových seznamů 690 00:37:29,320 --> 00:37:31,100 >> SPEAKER 1: dvojitý spojový seznam, ne? 691 00:37:31,100 --> 00:37:33,690 Pokud tedy nahradit tento s předchozí a následující, 692 00:37:33,690 --> 00:37:35,670 by to bylo dvojnásobně spojový seznam. 693 00:37:35,670 --> 00:37:40,125 Ale v tomto případě jsme se vlastně jsou vlevo a vpravo, a je to. 694 00:37:40,125 --> 00:37:41,500 Jinak je to úplně stejné. 695 00:37:41,500 --> 00:37:43,374 Stále máme prvek hledáte, 696 00:37:43,374 --> 00:37:45,988 a stačí dva ukazatele bude, co bude dál. 697 00:37:45,988 --> 00:37:49,210 698 00:37:49,210 --> 00:37:51,870 Jo, tak binární vyhledávací strom. 699 00:37:51,870 --> 00:37:57,665 Pokud jsme si všimli, vše na tady je větší than-- 700 00:37:57,665 --> 00:37:59,850 nebo vše ihned aby tady 701 00:37:59,850 --> 00:38:02,840 je větší než, všechno Zde je menší než. 702 00:38:02,840 --> 00:38:06,980 703 00:38:06,980 --> 00:38:14,000 >> Takže, pokud bychom měli prohledávat, by měl vypadat velmi blízko k binární vyhledávání 704 00:38:14,000 --> 00:38:14,910 tady, že jo? 705 00:38:14,910 --> 00:38:17,640 Kromě namísto hledání na polovinu pole, 706 00:38:17,640 --> 00:38:21,720 jsme se jen při pohledu na levou straně nebo na pravé straně stromu. 707 00:38:21,720 --> 00:38:24,850 Tak to je trochu jednodušší, myslím. 708 00:38:24,850 --> 00:38:29,300 >> Takže pokud vaše kořen je NULL, samozřejmě je to jen falešná. 709 00:38:29,300 --> 00:38:33,470 A pokud to tam je, samozřejmě, že je to pravda. 710 00:38:33,470 --> 00:38:35,320 Pokud je to méně, než jsme se hledat vlevo. 711 00:38:35,320 --> 00:38:37,070 Pokud je větší než hledáme právo. 712 00:38:37,070 --> 00:38:39,890 Je to přesně jako binární vyhledávání, jen odlišná struktura dat 713 00:38:39,890 --> 00:38:40,600 že jsme použili. 714 00:38:40,600 --> 00:38:42,790 Místo pole, je to jen binární strom. 715 00:38:42,790 --> 00:38:45,820 716 00:38:45,820 --> 00:38:48,090 >> OK, komíny. 717 00:38:48,090 --> 00:38:51,550 A také to vypadá, že my může mít trochu času. 718 00:38:51,550 --> 00:38:54,460 Pokud se tak stane, jsem rád, že jít přes tohle všechno znovu. 719 00:38:54,460 --> 00:38:56,856 OK, tak komíny. 720 00:38:56,856 --> 00:39:02,695 Pamatuje si někdo, co stacks-- všechny charakteristiky zásobníku? 721 00:39:02,695 --> 00:39:05,550 722 00:39:05,550 --> 00:39:10,400 >> OK, takže většina z nás, myslím, jíst v jídelně halls-- 723 00:39:10,400 --> 00:39:13,100 co můžeme neradi. 724 00:39:13,100 --> 00:39:16,900 Ale samozřejmě, můžete myslet na zásobníku doslova jen jako hromadu zásobníků 725 00:39:16,900 --> 00:39:18,460 nebo hromadu věcí. 726 00:39:18,460 --> 00:39:21,820 A co je důležité si uvědomit, že je to 727 00:39:21,820 --> 00:39:26,850 something-- charakteristika že říkáme, že by-- je LIFO. 728 00:39:26,850 --> 00:39:28,450 Ví někdo, co to znamená? 729 00:39:28,450 --> 00:39:29,070 Mmhmm? 730 00:39:29,070 --> 00:39:30,650 >> DIVÁKŮ: Poslední dovnitř, první ven. 731 00:39:30,650 --> 00:39:32,250 >> SPEAKER 1: Dobře, poslední dovnitř, první ven. 732 00:39:32,250 --> 00:39:36,585 Takže pokud víme, jestli jsme stohování věci up, nejjednodušší chytit off-- 733 00:39:36,585 --> 00:39:39,570 a snad jediné, co můžeme chytit vypne, pokud náš stack je velký enough-- 734 00:39:39,570 --> 00:39:40,850 je to, že horní prvek. 735 00:39:40,850 --> 00:39:43,460 Takže bez ohledu byl kladen na last-- jak vidíme zde, 736 00:39:43,460 --> 00:39:46,370 co byl tlačen na většině recently-- je 737 00:39:46,370 --> 00:39:51,160 bude první věc, že ​​jsme pop off, OK? 738 00:39:51,160 --> 00:39:56,324 >> Takže to, co tu máme, je další typedef struct. 739 00:39:56,324 --> 00:39:58,740 To je opravdu jen rád rychlokurz v datové struktuře, 740 00:39:58,740 --> 00:40:01,650 takže je tu spousta hozen na vás kluci. 741 00:40:01,650 --> 00:40:02,540 Já vím. 742 00:40:02,540 --> 00:40:04,970 Takže další Struct. 743 00:40:04,970 --> 00:40:06,740 Yay pro stavby. 744 00:40:06,740 --> 00:40:16,660 >> A v tomto případě, je to nějaký ukazatel na pole, které má určitou kapacitu. 745 00:40:16,660 --> 00:40:20,830 Takže to představuje náš stack Zde, stejně jako naší aktuální pole 746 00:40:20,830 --> 00:40:22,520 které drží naše prvků. 747 00:40:22,520 --> 00:40:24,850 A pak tady máme nějaké velikosti. 748 00:40:24,850 --> 00:40:31,170 >> A obvykle, chcete, aby track o tom, jak velký je váš stack 749 00:40:31,170 --> 00:40:36,180 protože to, co se děje, aby můžete udělat, je, pokud víte, že velikost, 750 00:40:36,180 --> 00:40:39,170 to vám umožní říci, OK, jsem na plný výkon? 751 00:40:39,170 --> 00:40:40,570 Mohu přidat něco víc? 752 00:40:40,570 --> 00:40:44,650 A také vám řekne, kde horní část zásobníku 753 00:40:44,650 --> 00:40:48,180 tak víte, co jste může skutečně vzlétnout. 754 00:40:48,180 --> 00:40:51,760 A to vlastně bude tady trochu jasnější. 755 00:40:51,760 --> 00:40:57,350 >> Takže pro stisk, jednu věc, pokud máte byl vždy realizovat tlačit, 756 00:40:57,350 --> 00:41:01,330 jak jsem právě řekl, vaše zásobník má omezenou velikost, je to tak? 757 00:41:01,330 --> 00:41:03,990 Naše pole měl nějakou kapacitu. 758 00:41:03,990 --> 00:41:04,910 Je to pole. 759 00:41:04,910 --> 00:41:08,930 Je to pevné velikosti, takže je třeba, aby Ujistěte se, že nejsme uvedení více 760 00:41:08,930 --> 00:41:11,950 do našeho pole, než jsme skutečně prostor pro. 761 00:41:11,950 --> 00:41:16,900 >> Takže, když budete vytvářet tlak funkce, první věc, kterou udělat, je říci, OK, 762 00:41:16,900 --> 00:41:18,570 mám místo ve svém stacku? 763 00:41:18,570 --> 00:41:23,330 Protože když to neudělám, promiň, Nemohu uložit prvek. 764 00:41:23,330 --> 00:41:28,980 Když to udělám, pak budete chtít uložit je na vrcholu zásobníku, je to tak? 765 00:41:28,980 --> 00:41:31,325 >> A to je důvod, proč máme sledovat naší velikosti. 766 00:41:31,325 --> 00:41:35,290 Nebudeme-li mít přehled o naší velikosti, nevíme, kam to dát. 767 00:41:35,290 --> 00:41:39,035 Nevíme, jak mnoho věcí, jsou v našem poli již. 768 00:41:39,035 --> 00:41:41,410 Jako samozřejmě existují způsoby, jak že možná byste mohli udělat. 769 00:41:41,410 --> 00:41:44,610 Dalo by se inicializovat vše NULL a pak zkontrolujte, zda máte nejnovější verzi NULL, 770 00:41:44,610 --> 00:41:47,950 ale mnohem jednodušší věc je prostě říct, OK, sledovat velikosti. 771 00:41:47,950 --> 00:41:51,840 Stejně jako vím, že mám čtyři prvky v mém poli, takže další věc, 772 00:41:51,840 --> 00:41:55,930 že jsme dali na, jsme bude ukládat na indexu 4. 773 00:41:55,930 --> 00:42:00,940 A pak, samozřejmě, to znamená, že jste úspěšně tlačil něco 774 00:42:00,940 --> 00:42:03,320 na stacku, jste chcete zvýšit velikost 775 00:42:03,320 --> 00:42:08,880 takže víte, kde jste tak že můžete tlačit více věcí na. 776 00:42:08,880 --> 00:42:12,730 >> Takže pokud se snažíme pop něco z hromádky, 777 00:42:12,730 --> 00:42:16,072 co by mohlo být první věc, že chceme zkontrolovat? 778 00:42:16,072 --> 00:42:18,030 Snažíte se vzít něco z vašeho stacku. 779 00:42:18,030 --> 00:42:21,710 780 00:42:21,710 --> 00:42:24,781 Jste si jistý, že je to něco v zásobníku? 781 00:42:24,781 --> 00:42:25,280 Ne. 782 00:42:25,280 --> 00:42:26,894 Takže to, co bychom mohli chtít zkontrolovat? 783 00:42:26,894 --> 00:42:27,810 >> Diváků: [neslyšitelné]. 784 00:42:27,810 --> 00:42:29,880 SPEAKER 1: Zkontrolujte, zda velikost? 785 00:42:29,880 --> 00:42:31,840 Velikost. 786 00:42:31,840 --> 00:42:38,520 Takže chceme zkontrolovat, zda Naše velikost je větší než 0, OK? 787 00:42:38,520 --> 00:42:44,970 A pokud ano, pak chceme snížit Naše velikost od 0 a vrátit to. 788 00:42:44,970 --> 00:42:45,840 Proč? 789 00:42:45,840 --> 00:42:49,950 >> V prvním z nich jsme byli tlačení, to tlačil nás 790 00:42:49,950 --> 00:42:52,460 na velikosti a poté průběžně aktualizovaným velikosti. 791 00:42:52,460 --> 00:42:57,850 V tomto případě jsme dekrementování velikost a pak ji sundal, škubání ji 792 00:42:57,850 --> 00:42:58,952 z naší řady. 793 00:42:58,952 --> 00:42:59,826 Proč bychom mohli udělat, že? 794 00:42:59,826 --> 00:43:04,800 795 00:43:04,800 --> 00:43:11,811 Takže pokud mám jednu věc na mém stacku, Co by byla moje velikost v tomto místě? 796 00:43:11,811 --> 00:43:13,140 1. 797 00:43:13,140 --> 00:43:15,180 >> A kde je prvek 1 uloženo? 798 00:43:15,180 --> 00:43:17,621 Na co index? 799 00:43:17,621 --> 00:43:18,120 Publikum: 0. 800 00:43:18,120 --> 00:43:19,060 SPEAKER 1: 0. 801 00:43:19,060 --> 00:43:22,800 Takže v tomto případě jsme Vždy je třeba provést sure-- 802 00:43:22,800 --> 00:43:27,630 místo vrácení velikost minus 1, protože jsme 803 00:43:27,630 --> 00:43:31,730 víme, že naše prvek je bude uložen na 1 méně 804 00:43:31,730 --> 00:43:34,705 bez ohledu na naši velikost je, toto jen se o to postarám. 805 00:43:34,705 --> 00:43:36,080 Je to o něco více elegantní způsob. 806 00:43:36,080 --> 00:43:41,220 A my jen decrement dotazy velikost a pak se vrátit velikost. 807 00:43:41,220 --> 00:43:42,330 Mmhmm? 808 00:43:42,330 --> 00:43:45,300 >> Diváků: Myslím, že jen obecně, proč by to datová struktura 809 00:43:45,300 --> 00:43:47,800 být výhodné? 810 00:43:47,800 --> 00:43:50,660 >> SPEAKER 1: Záleží na vašem kontextu. 811 00:43:50,660 --> 00:43:57,420 Tak pro některé z teorie, pokud pracujete with-- OK, 812 00:43:57,420 --> 00:44:02,750 dovolte mi, abych zjistil, jestli je prospěšné jeden která je prospěšná pro více než venku 813 00:44:02,750 --> 00:44:05,420 ČS. 814 00:44:05,420 --> 00:44:15,780 U komínů, kdykoliv budete potřebovat sledovat něco, co 815 00:44:15,780 --> 00:44:20,456 se naposledy přidán je, když budete chtít použít zásobník. 816 00:44:20,456 --> 00:44:24,770 >> A já si nemyslím, že je dobrý Příkladem, že právě teď. 817 00:44:24,770 --> 00:44:29,955 Ale kdykoli poslední co je pro vás nejdůležitější, 818 00:44:29,955 --> 00:44:31,705 to je, když stack bude užitečné. 819 00:44:31,705 --> 00:44:35,797 820 00:44:35,797 --> 00:44:39,330 Snažím se, že pokud tam je dobrý pro to. 821 00:44:39,330 --> 00:44:43,720 Pokud bych myslet na dobrý příklad v další 20 minut a to se určitě říct. 822 00:44:43,720 --> 00:44:49,455 >> Ale celkově, jestli je něco, jak jsem řekl, že většina, kde poslední 823 00:44:49,455 --> 00:44:52,470 Nejdůležitější je, že se kde balík vstoupí do hry. 824 00:44:52,470 --> 00:44:58,860 Vzhledem k tomu, fronty jsou trochu naopak. 825 00:44:58,860 --> 00:44:59,870 A všechny ty malé psy. 826 00:44:59,870 --> 00:45:00,890 Není to skvělé, že jo? 827 00:45:00,890 --> 00:45:03,299 Mám pocit, jako bych měl jen mít zajíček videa 828 00:45:03,299 --> 00:45:05,090 přímo v centru Sekce pro vás 829 00:45:05,090 --> 00:45:08,870 protože se jedná o intenzivní část. 830 00:45:08,870 --> 00:45:10,480 >> Tak fronta. 831 00:45:10,480 --> 00:45:12,710 V podstatě fronta je jako linie. 832 00:45:12,710 --> 00:45:15,780 Vy Jsem si jistý, použití této každodenní, stejně jako v našich jídelnách. 833 00:45:15,780 --> 00:45:18,160 Takže musíme jít a dostat naše zásobníky, jsem 834 00:45:18,160 --> 00:45:21,260 že máte čekat ve frontě Přesunutí nebo dostat své jídlo. 835 00:45:21,260 --> 00:45:24,650 >> Tak tady je rozdíl je to, že toto je FIFO. 836 00:45:24,650 --> 00:45:30,090 Takže pokud LIFO byla naposledy v prvním out, FIFO je first in, first out. 837 00:45:30,090 --> 00:45:33,400 Tak tohle je místo, kde co si dát Na první je vaše nejdůležitější. 838 00:45:33,400 --> 00:45:35,540 Takže pokud jste čekali v line-- můžete 839 00:45:35,540 --> 00:45:39,130 Představte si, že jste šel do jdi na nový iPhone 840 00:45:39,130 --> 00:45:42,800 a to bylo stack, kde poslední osoba v souladu ji dostal jako první, 841 00:45:42,800 --> 00:45:44,160 lidé by se navzájem zabíjeli. 842 00:45:44,160 --> 00:45:49,800 >> Takže FIFO, jsme všichni velmi dobře se zde v reálném světě, 843 00:45:49,800 --> 00:45:54,930 a to všechno má co do činění s opravdu druh obnovovat celý tento řádek 844 00:45:54,930 --> 00:45:56,900 a fronty strukturu. 845 00:45:56,900 --> 00:46:02,390 Takže zatímco v zásobníku, máme tlačit a pop. 846 00:46:02,390 --> 00:46:06,440 S fronty, máme Přidat do seznamu a dequeue. 847 00:46:06,440 --> 00:46:10,910 Přidat do seznamu tak v podstatě znamená, dát na záda, 848 00:46:10,910 --> 00:46:13,680 a Dequeue prostředky vzít off zepředu. 849 00:46:13,680 --> 00:46:18,680 Takže naše datová struktura je trochu složitější. 850 00:46:18,680 --> 00:46:21,060 Máme druhou věc, jak sledovat. 851 00:46:21,060 --> 00:46:25,950 >> Takže bez hlavy, to je přesně to, zásobník, ne? 852 00:46:25,950 --> 00:46:27,900 To je stejné konstrukce jako zásobník. 853 00:46:27,900 --> 00:46:32,480 Jediné, co teď jiné je, že jsme tuto hlavu, která to, co si myslíte, že 854 00:46:32,480 --> 00:46:34,272 bude sledovat? 855 00:46:34,272 --> 00:46:35,510 >> Diváků: první z nich. 856 00:46:35,510 --> 00:46:38,685 >> SPEAKER 1: Správně, První věc, kterou jsme dali v. 857 00:46:38,685 --> 00:46:41,130 Hlava naší fronty. 858 00:46:41,130 --> 00:46:42,240 Ten, kdo je v první linii. 859 00:46:42,240 --> 00:46:45,300 860 00:46:45,300 --> 00:46:49,420 Dobře, takže pokud uděláme zařazení do fronty. 861 00:46:49,420 --> 00:46:52,720 862 00:46:52,720 --> 00:46:55,920 Opět platí, že se některý z Tyto datové struktury, 863 00:46:55,920 --> 00:46:59,760 protože máme co do činění s řadou, musíme zkontrolovat, jestli máme prostor. 864 00:46:59,760 --> 00:47:03,290 >> To je něco jako já, říká vy, pokud otevřete soubor, 865 00:47:03,290 --> 00:47:04,760 je třeba zkontrolovat na null. 866 00:47:04,760 --> 00:47:08,330 S některou z těchto komínů a fronty, budete potřebovat 867 00:47:08,330 --> 00:47:13,420 zjistit, jestli tam je prostor, protože jsme jednání s pevnou velikostí pole, 868 00:47:13,420 --> 00:47:16,030 jak vidíme here-- 0, 1 vše až 5. 869 00:47:16,030 --> 00:47:20,690 Takže to, co děláme v tomto případě je kontrola aby zjistil, jestli ještě máme prostor. 870 00:47:20,690 --> 00:47:23,110 Je naše velikost menší než kapacita? 871 00:47:23,110 --> 00:47:28,480 >> Pokud tomu tak je, musíme uložit na ocas a obnovujeme naši velikost. 872 00:47:28,480 --> 00:47:30,250 Takže to, co je možné, že ocas je v tomto případě? 873 00:47:30,250 --> 00:47:32,360 To není výslovně napsané. 874 00:47:32,360 --> 00:47:33,380 Jak bychom to uložit? 875 00:47:33,380 --> 00:47:34,928 Co by ocas být? 876 00:47:34,928 --> 00:47:38,600 877 00:47:38,600 --> 00:47:40,190 >> Takže pojďme se projít tento příklad. 878 00:47:40,190 --> 00:47:44,590 Tak tohle je pole o velikosti 6, ne? 879 00:47:44,590 --> 00:47:49,220 A máme teď, naše velikost je 5. 880 00:47:49,220 --> 00:47:55,240 A když jsme se dát do, bude to jít do pátého indexu, ne? 881 00:47:55,240 --> 00:47:57,030 Tak skladuje v ocasu. 882 00:47:57,030 --> 00:48:05,600 >> Dalším způsobem, jak napsat ocas by jen naše pole v indexu velikosti, ne? 883 00:48:05,600 --> 00:48:07,560 To je velikost 5. 884 00:48:07,560 --> 00:48:11,490 Další věc je jít do 5. 885 00:48:11,490 --> 00:48:12,296 V pohodě? 886 00:48:12,296 --> 00:48:13,290 OK. 887 00:48:13,290 --> 00:48:16,350 Je to poněkud složitější dostane když začneme hrát s hlavou. 888 00:48:16,350 --> 00:48:17,060 Ano? 889 00:48:17,060 --> 00:48:20,090 >> Diváků: Znamená to, že jsme by deklarovali pole, které 890 00:48:20,090 --> 00:48:23,880 bylo pět prvků dlouhá a pak budeme přidávat na něj? 891 00:48:23,880 --> 00:48:24,730 >> SPEAKER 1: Ne 892 00:48:24,730 --> 00:48:27,560 Takže v tomto případě se jedná o zásobník. 893 00:48:27,560 --> 00:48:31,760 To by být prohlášen za jako pole o velikosti 6. 894 00:48:31,760 --> 00:48:37,120 A v tomto případě jsme stačí jedno volné místo. 895 00:48:37,120 --> 00:48:42,720 >> OK, takže jedna věc je v tomto případě, je-li naše hlava je na 0, 896 00:48:42,720 --> 00:48:45,270 pak stačí jej přidat na velikosti. 897 00:48:45,270 --> 00:48:51,020 Ale to dostane trochu složitější protože ve skutečnosti, že 898 00:48:51,020 --> 00:48:52,840 nemají snímek za to, takže budu 899 00:48:52,840 --> 00:48:56,670 k tomu jedno, protože to není tak jednoduché, jakmile se 900 00:48:56,670 --> 00:48:59,230 začít, jak se zbavit věcí. 901 00:48:59,230 --> 00:49:03,920 A tak vzhledem k tomu, se zásobníkem si jen někdy 902 00:49:03,920 --> 00:49:08,920 se starat o to, co je velikost když přidáváte něco dál, 903 00:49:08,920 --> 00:49:15,710 s fronty je také nutné, aby se Ujistěte se, že vaše hlava se účtuje, 904 00:49:15,710 --> 00:49:20,760 protože super věc o frontách je, že pokud nejste na plný výkon, 905 00:49:20,760 --> 00:49:23,040 můžete skutečně dělat to se zalomí kolem. 906 00:49:23,040 --> 00:49:28,810 >> OK, tak jeden thing-- oh, to je hrozné křída. 907 00:49:28,810 --> 00:49:31,815 Jedna věc, aby zvážila, je tomu tak. 908 00:49:31,815 --> 00:49:35,514 909 00:49:35,514 --> 00:49:37,140 Budeme prostě pět. 910 00:49:37,140 --> 00:49:41,810 OK, takže budeme tvrdí, že hlava je tady. 911 00:49:41,810 --> 00:49:46,140 To je 0, 1, 2, 3, 4. 912 00:49:46,140 --> 00:49:54,210 >> Hlava je tam, a prosím, věci v nich. 913 00:49:54,210 --> 00:49:58,340 A chceme přidat něco, že jo? 914 00:49:58,340 --> 00:50:01,170 Takže to, co potřebujeme vím, je, že hlava je vždy 915 00:50:01,170 --> 00:50:05,620 bude se pohybovat sem a pak zpětné smyčky kolem, OK? 916 00:50:05,620 --> 00:50:10,190 >> Tak tohle fronta má prostor, ne? 917 00:50:10,190 --> 00:50:13,950 Má prostor na samém počátku, druh opak toho. 918 00:50:13,950 --> 00:50:17,920 Takže to, co musíme udělat, je, že jsme je třeba vypočítat ocas. 919 00:50:17,920 --> 00:50:20,530 Pokud víte, že vaše hlava nepohybuje, ocas 920 00:50:20,530 --> 00:50:24,630 je jen vaše pole na index velikosti. 921 00:50:24,630 --> 00:50:30,000 >> Ale ve skutečnosti, pokud používáte frontu, vaše hlava je pravděpodobně aktualizován. 922 00:50:30,000 --> 00:50:33,890 Takže to, co musíte udělat, je vlastně výpočet ocas. 923 00:50:33,890 --> 00:50:39,990 Takže to, co děláme, je to vzorec tu, kterou jsem tě nechat 924 00:50:39,990 --> 00:50:42,680 vy myslíte o, a pak budeme o tom mluvit. 925 00:50:42,680 --> 00:50:49,567 926 00:50:49,567 --> 00:50:50,400 Tak tohle je kapacita. 927 00:50:50,400 --> 00:50:55,890 928 00:50:55,890 --> 00:50:59,660 >> Takže to bude ve skutečnosti vám, jak to udělat. 929 00:50:59,660 --> 00:51:03,205 930 00:51:03,205 --> 00:51:04,330 Protože v tomto případě, co? 931 00:51:04,330 --> 00:51:09,205 Naše hlava je na 1, naše velikost je 4. 932 00:51:09,205 --> 00:51:11,760 933 00:51:11,760 --> 00:51:18,490 Pokud bychom mod, že 5, dostaneme 0, což je místo, kde bychom měli vstup za to. 934 00:51:18,490 --> 00:51:23,320 935 00:51:23,320 --> 00:51:26,080 >> A tak v dalším případě, kdybychom k tomu, 936 00:51:26,080 --> 00:51:33,390 říkáme, OK, pojďme dequeue něco. 937 00:51:33,390 --> 00:51:34,390 Jsme dequeue to. 938 00:51:34,390 --> 00:51:37,740 Bereme se tento prvek, je to tak? 939 00:51:37,740 --> 00:51:47,930 >> A teď naše hlava směřuje zde a chceme přidat další věci. 940 00:51:47,930 --> 00:51:52,470 To je v podstatě zpět na naší linii, ne? 941 00:51:52,470 --> 00:51:55,450 Fronty mohou obalit kolem pole. 942 00:51:55,450 --> 00:51:57,310 To je jeden z hlavních rozdílů. 943 00:51:57,310 --> 00:51:58,780 Komíny, můžete to udělat. 944 00:51:58,780 --> 00:52:01,140 >> S front, můžete protože všechno, na čem záleží 945 00:52:01,140 --> 00:52:03,940 je to, že víte, co byl naposledy přidán. 946 00:52:03,940 --> 00:52:10,650 Vzhledem k tomu, vše se bude přidán do Tento doleva směr, v tomto případě, 947 00:52:10,650 --> 00:52:16,480 a pak zabalit kolem, můžete pokračovat v zavádění nových prvků 948 00:52:16,480 --> 00:52:18,830 v přední části pole protože to není opravdu 949 00:52:18,830 --> 00:52:20,640 přední pole už. 950 00:52:20,640 --> 00:52:26,320 Můžete myslet na začátku pole jako, kde se vaše hlava je ve skutečnosti. 951 00:52:26,320 --> 00:52:29,710 >> Takže tento vzorec je, jak můžete vypočítat ocas. 952 00:52:29,710 --> 00:52:32,780 953 00:52:32,780 --> 00:52:35,610 Má to smysl? 954 00:52:35,610 --> 00:52:36,110 OK. 955 00:52:36,110 --> 00:52:39,400 956 00:52:39,400 --> 00:52:44,040 OK, dequeue, a pak vy máte 10 minut 957 00:52:44,040 --> 00:52:48,840 aby se mě nějaké objasňovat otázky Chcete, protože vím, že je to šílené. 958 00:52:48,840 --> 00:52:51,980 >> V pořádku, takže ve stejném way-- Já nevím, jestli si kluci všimli, 959 00:52:51,980 --> 00:52:53,450 ale CS je o vzory. 960 00:52:53,450 --> 00:52:57,370 Věci jsou do značné míry Totéž, jen s malými vylepší. 961 00:52:57,370 --> 00:52:58,950 Tak to samé zde. 962 00:52:58,950 --> 00:53:04,040 Musíme zjistit, zda je skutečně mít něco v naší frontě, ne? 963 00:53:04,040 --> 00:53:05,960 Říci, OK, je naše velikost větší než 0? 964 00:53:05,960 --> 00:53:06,730 V pohodě. 965 00:53:06,730 --> 00:53:10,690 >> Pokud se tak stane, pak se přesuneme naši hlavu, která je to, co jsem tu právě prokázal. 966 00:53:10,690 --> 00:53:13,870 Aktualizujeme naši hlavu, aby se ještě jednou. 967 00:53:13,870 --> 00:53:18,390 A pak jsme decrement naše Velikost a vrátí prvek. 968 00:53:18,390 --> 00:53:21,000 969 00:53:21,000 --> 00:53:26,250 >> Tam je mnohem konkrétnější kód na study.cs50.net, 970 00:53:26,250 --> 00:53:29,440 a vřele doporučuji jít přes to, pokud budete mít čas, 971 00:53:29,440 --> 00:53:30,980 i když je to jen pseudo-kódu. 972 00:53:30,980 --> 00:53:35,980 A pokud vy chcete mluvit přes že se mnou jeden na jednoho, dejte mi prosím 973 00:53:35,980 --> 00:53:37,500 vědět. 974 00:53:37,500 --> 00:53:38,770 Já bych rád. 975 00:53:38,770 --> 00:53:42,720 Datové struktury, pokud budete mít CS 124, budete 976 00:53:42,720 --> 00:53:47,830 vím, že datové struktury dostat velmi legrace, a to je jen začátek. 977 00:53:47,830 --> 00:53:50,350 >> Takže vím, že je to těžké. 978 00:53:50,350 --> 00:53:51,300 To je v pořádku. 979 00:53:51,300 --> 00:53:52,410 Bojujeme. 980 00:53:52,410 --> 00:53:53,630 Stále dělám. 981 00:53:53,630 --> 00:53:56,660 Takže se nemusíte příliš starat o to. 982 00:53:56,660 --> 00:54:02,390 >> Ale to je v podstatě Vašimi rychlokurz v datových strukturách. 983 00:54:02,390 --> 00:54:03,400 Vím, že je to hodně. 984 00:54:03,400 --> 00:54:06,860 Je tu něco, co nám bych jít znovu? 985 00:54:06,860 --> 00:54:09,400 Cokoliv chceme probrat? 986 00:54:09,400 --> 00:54:10,060 Ano? 987 00:54:10,060 --> 00:54:16,525 >> Diváků: Pro tento příklad, tak nový ocas je na 0 přes to? 988 00:54:16,525 --> 00:54:17,150 SPEAKER 1: Ano. 989 00:54:17,150 --> 00:54:18,230 Diváků: OK. 990 00:54:18,230 --> 00:54:24,220 Takže prochází, budeš mít 1 a 4 nebo-- 991 00:54:24,220 --> 00:54:27,671 >> SPEAKER 1: Takže jste říkala, když chceme jít to udělat znovu? 992 00:54:27,671 --> 00:54:28,296 Diváků: Jo. 993 00:54:28,296 --> 00:54:38,290 Takže pokud jste se přijít na out--, kde jsou budete výpočet ocas z v tom, že? 994 00:54:38,290 --> 00:54:44,260 >> SPEAKER 1: Takže ocas Byl in-- změnil jsem to. 995 00:54:44,260 --> 00:54:52,010 Takže v tomto případě tady, to bylo pole se díváme, OK? 996 00:54:52,010 --> 00:54:54,670 Takže máme věci v 1, 2, 3 a 4. 997 00:54:54,670 --> 00:55:05,850 Takže máme naše hlava je rovna 1 na tento bod, a naše velikost je rovna 4 998 00:55:05,850 --> 00:55:07,050 na tomto místě, že jo? 999 00:55:07,050 --> 00:55:08,960 >> Vy všichni se shodují, že je to tak? 1000 00:55:08,960 --> 00:55:14,620 Takže děláme hlavu plus velikost, která nám dává 5, a pak jsme mod o 5. 1001 00:55:14,620 --> 00:55:20,690 Dostáváme 0, což nám říká, že 0 je kde je náš ocas, kde máme prostor. 1002 00:55:20,690 --> 00:55:22,010 >> Diváků: Co je čepice? 1003 00:55:22,010 --> 00:55:23,520 >> SPEAKER 1: kapacita. 1004 00:55:23,520 --> 00:55:24,020 Promiňte. 1005 00:55:24,020 --> 00:55:29,640 Tak to je velikost vašeho pole. 1006 00:55:29,640 --> 00:55:35,210 1007 00:55:35,210 --> 00:55:36,047 Ano? 1008 00:55:36,047 --> 00:55:39,210 >> Diváků: [neslyšitelné] před vrátíme prvek? 1009 00:55:39,210 --> 00:55:46,270 >> SPEAKER 1: Takže se pohybujeme hlavou nebo se vrátit v okamžiku, kdy? 1010 00:55:46,270 --> 00:55:52,680 Pokud tedy přesunout jeden, decrement velikost? 1011 00:55:52,680 --> 00:55:54,150 Vydrž. 1012 00:55:54,150 --> 00:55:55,770 Rozhodně jsem zapomněl další. 1013 00:55:55,770 --> 00:56:00,646 1014 00:56:00,646 --> 00:56:01,990 To nic. 1015 00:56:01,990 --> 00:56:04,980 Není jiný vzorec. 1016 00:56:04,980 --> 00:56:09,980 Jo, by se chcete vrátit hlava a pak ji vrátit zpět. 1017 00:56:09,980 --> 00:56:13,270 >> Publikum: OK, protože v tomto bod, hlava byla na 0, 1018 00:56:13,270 --> 00:56:18,452 a pak se chcete vrátit index 0 a pak se hlava 1? 1019 00:56:18,452 --> 00:56:19,870 >> SPEAKER 1: Správně. 1020 00:56:19,870 --> 00:56:22,820 Myslím, že je tu další vzorec něco jako tohle. 1021 00:56:22,820 --> 00:56:26,970 Nemám ji na vrcholu mé hlavy, jak Nechci, aby vám ten špatný. 1022 00:56:26,970 --> 00:56:35,470 Ale myslím, že je to naprosto v pořádku, aby řekněme, OK uložte tuto element-- cokoliv 1023 00:56:35,470 --> 00:56:40,759 element hlava je je-- decrement vaše velikost, pohybovat hlavou nad a návrat 1024 00:56:40,759 --> 00:56:41,800 co to je element. 1025 00:56:41,800 --> 00:56:44,760 To je naprosto v pořádku. 1026 00:56:44,760 --> 00:56:45,260 OK. 1027 00:56:45,260 --> 00:56:48,360 1028 00:56:48,360 --> 00:56:53,560 Mám pocit, že to není jako most-- nejste 1029 00:56:53,560 --> 00:56:55,740 jít pěšky odsud jako, ano, já vím pokusů. 1030 00:56:55,740 --> 00:56:56,880 Mám to všechno. 1031 00:56:56,880 --> 00:56:57,670 To je v pořádku. 1032 00:56:57,670 --> 00:57:00,200 Slibuji. 1033 00:57:00,200 --> 00:57:05,240 Ale datové struktury jsou něco, co to trvá hodně času si zvyknout. 1034 00:57:05,240 --> 00:57:10,010 Pravděpodobně jeden z nejtěžších věci, myslím, že v průběhu. 1035 00:57:10,010 --> 00:57:15,330 >> Tak to určitě má opakování a při pohledu at-- I 1036 00:57:15,330 --> 00:57:20,050 to opravdu nevím provázané seznamy dokud jsem udělal příliš mnoho s nimi, 1037 00:57:20,050 --> 00:57:22,550 stejným způsobem, že jsem to neudělal opravdu pochopit ukazatele 1038 00:57:22,550 --> 00:57:27,040 dokud jsem se musel učit pro dva let a dělat své vlastní psets s ním. 1039 00:57:27,040 --> 00:57:28,990 To vyžaduje hodně zdůraznění a času. 1040 00:57:28,990 --> 00:57:32,600 A nakonec, bude to trochu na tlačítko. 1041 00:57:32,600 --> 00:57:36,320 >> Ale do té doby, pokud máte typ porozumění na vysoké úrovni, co 1042 00:57:36,320 --> 00:57:39,321 Tyto dělat, jejich výhody a cons-- což je to, co 1043 00:57:39,321 --> 00:57:41,820 opravdu se snaží zdůraznit, zejména v úvodní kurzu. 1044 00:57:41,820 --> 00:57:45,511 Stejně jako, proč bychom použít zkuste přes pole? 1045 00:57:45,511 --> 00:57:48,010 Stejně jako to, co jsou pozitiva a zápory každého z nich? 1046 00:57:48,010 --> 00:57:51,610 >> A pochopení kompromisy Mezi každou z těchto struktur 1047 00:57:51,610 --> 00:57:54,910 je to, co je mnohem důležitější právě teď. 1048 00:57:54,910 --> 00:57:58,140 Zde může být jeden blázen otázka nebo dva, které je 1049 00:57:58,140 --> 00:58:03,710 bude vás žádat, abyste implementovat tlačit nebo realizovat pop nebo zařazení do fronty a Dequeue. 1050 00:58:03,710 --> 00:58:07,340 Avšak ve většině případů, že mají vyšší úroveň porozumění a více 1051 00:58:07,340 --> 00:58:09,710 na intuitivní pochopení je mnohem důležitější, než ve skutečnosti 1052 00:58:09,710 --> 00:58:11,250 budou moci k jeho provedení. 1053 00:58:11,250 --> 00:58:14,880 >> To by bylo opravdu úžasné, kdybyste všichni mohl jít ven a jít realizovat vyzkoušet, 1054 00:58:14,880 --> 00:58:19,720 ale chápeme, že to nemusí být nutně nejrozumnější věc, kterou právě teď. 1055 00:58:19,720 --> 00:58:23,370 Ale můžete v pset, chcete-li na, a pak budete mít praxi, 1056 00:58:23,370 --> 00:58:27,200 a pak možná budete opravdu pochopit. 1057 00:58:27,200 --> 00:58:27,940 Ano? 1058 00:58:27,940 --> 00:58:30,440 >> Publikum: OK, tak ty, které jsou jsme chtěl použít v pset? 1059 00:58:30,440 --> 00:58:31,916 Musím použít jeden z nich? 1060 00:58:31,916 --> 00:58:32,540 SPEAKER 1: Ano. 1061 00:58:32,540 --> 00:58:34,199 Takže máte na výběr. 1062 00:58:34,199 --> 00:58:36,740 Myslím, že v tomto případě můžeme mluvit o pset trochu 1063 00:58:36,740 --> 00:58:40,480 protože jsem běžel přes tyto. 1064 00:58:40,480 --> 00:58:47,779 Takže ve vašem pset, nemáte výběr pokusů nebo hash tabulky. 1065 00:58:47,779 --> 00:58:49,570 Někteří lidé se budou snažit a použití bloom filtry, 1066 00:58:49,570 --> 00:58:51,840 ale ty technicky nejsou správné. 1067 00:58:51,840 --> 00:58:55,804 Vzhledem k jejich pravděpodobnostní povahu, dávají někdy falešně pozitivní. 1068 00:58:55,804 --> 00:58:57,095 Jsou v pohodě pohled do, ačkoli. 1069 00:58:57,095 --> 00:58:59,030 Velmi doporučuji hledat na ně minimálně. 1070 00:58:59,030 --> 00:59:03,260 Ale máte možnost volby mezi hash tabulky a pokus. 1071 00:59:03,260 --> 00:59:06,660 A to bude kdy vložíte do slovníku. 1072 00:59:06,660 --> 00:59:09,230 >> A budete muset vybrat vaše hash funkce, 1073 00:59:09,230 --> 00:59:13,420 budete muset zvolit, kolik lopaty máte, a to se bude lišit. 1074 00:59:13,420 --> 00:59:17,440 Jako když máte více kbelíky, Možná, že to bude rychlejší. 1075 00:59:17,440 --> 00:59:22,790 Ale možná, že ztrácíte Spousta prostoru, který tak či onak, ačkoli. 1076 00:59:22,790 --> 00:59:26,320 Musíte na to přijít. 1077 00:59:26,320 --> 00:59:27,140 Mmhmm? 1078 00:59:27,140 --> 00:59:29,875 >> Diváků: Říkal jste, že před tím můžeme použít i jiné hašovací funkce, 1079 00:59:29,875 --> 00:59:31,750 že nemusíme vytvořit hash funkce? 1080 00:59:31,750 --> 00:59:32,666 >> SPEAKER 1: Ano, správně. 1081 00:59:32,666 --> 00:59:38,150 Takže doslova pro hash funkci, jako google "hash funkce" 1082 00:59:38,150 --> 00:59:40,770 a podívejte se na některé ty chladné. 1083 00:59:40,770 --> 00:59:43,250 Nejste Očekává se, že stavět vlastní hash funkce. 1084 00:59:43,250 --> 00:59:46,100 Lidé tráví svůj práce na těchto věcech. 1085 00:59:46,100 --> 00:59:50,250 >> Takže se nemusíte starat o budování své vlastní. 1086 00:59:50,250 --> 00:59:53,350 Najít jednu on-line pro začátek. 1087 00:59:53,350 --> 00:59:56,120 Některé z nich budete muset manipulovat trochu 1088 00:59:56,120 --> 00:59:59,430 aby se ujistil, návratové typy shodovat a kdo ví co ještě, takže na začátku, 1089 00:59:59,430 --> 01:00:02,420 Doporučil bych používat něco rychlé, že možná právě 1090 01:00:02,420 --> 01:00:04,680 hash na první písmeno. 1091 01:00:04,680 --> 01:00:08,760 A pak, až budete mít, že práce, zahrnující chladnější hash funkce. 1092 01:00:08,760 --> 01:00:09,260 Mmhmm? 1093 01:00:09,260 --> 01:00:13,020 >> Diváků: Bude zkuste být nebo efektivní, ale jen těžší, like-- 1094 01:00:13,020 --> 01:00:15,880 >> SPEAKER 1: Takže zkusit, myslím, je intuitivně těžko realizovat 1095 01:00:15,880 --> 01:00:18,310 ale je velmi rychlý. 1096 01:00:18,310 --> 01:00:20,620 Nicméně, zabírá více místa. 1097 01:00:20,620 --> 01:00:25,270 Opět platí, že můžete optimalizovat obě ty různé způsoby, a existují způsoby, jak to-- 1098 01:00:25,270 --> 01:00:26,770 Diváků: Jak jsme třídí na to? 1099 01:00:26,770 --> 01:00:27,540 Má matter-- 1100 01:00:27,540 --> 01:00:29,164 >> SPEAKER 1: Takže jste se stupněm normálním způsobem. 1101 01:00:29,164 --> 01:00:31,330 Budeš se třídí na design. 1102 01:00:31,330 --> 01:00:36,020 Podle toho, jak to uděláte, budete chtít, aby ujistěte se, že je to tak elegantní, jak to může být 1103 01:00:36,020 --> 01:00:38,610 a tak účinný, jak to může být. 1104 01:00:38,610 --> 01:00:41,950 Ale pokud se rozhodnete vyzkoušet nebo hash Tabulka, tak dlouho, jak to funguje, 1105 01:00:41,950 --> 01:00:45,350 jsme rádi, s tím. 1106 01:00:45,350 --> 01:00:48,370 A pokud používáte něco, co hash na první písmeno, to je v pořádku, 1107 01:00:48,370 --> 01:00:51,410 Třeba jako jeho designu. 1108 01:00:51,410 --> 01:00:53,410 Jsme také dosáhnout bod v tomto semester-- 1109 01:00:53,410 --> 01:00:55,340 Já nevím, jestli vás kluci noticed-- pokud jste 1110 01:00:55,340 --> 01:00:58,780 pset stupně klesat trochu vzhledem k designu a kdoví co ještě, 1111 01:00:58,780 --> 01:00:59,900 to je naprosto v pořádku. 1112 01:00:59,900 --> 01:01:02,960 Začíná to do bodu, kde se vaše programy jsou stále složitější. 1113 01:01:02,960 --> 01:01:04,830 Existuje více místa můžete zlepšit. 1114 01:01:04,830 --> 01:01:06,370 >> Takže je to naprosto normální. 1115 01:01:06,370 --> 01:01:08,810 To neznamená, že jste horší, na vašem pset. 1116 01:01:08,810 --> 01:01:11,885 Je to jen my je těžší na vás teď. 1117 01:01:11,885 --> 01:01:13,732 Takže všichni cítí to. 1118 01:01:13,732 --> 01:01:14,940 Jen jsem se třídí všechny vaše psets. 1119 01:01:14,940 --> 01:01:16,490 Vím, že každý se cítí to. 1120 01:01:16,490 --> 01:01:19,600 >> Takže se nemusíte obávat, že. 1121 01:01:19,600 --> 01:01:23,580 A pokud máte jakékoliv dotazy týkající se předchozí psets nebo způsoby, jak můžete zlepšit, 1122 01:01:23,580 --> 01:01:27,760 Snažím se a komentovat konkrétní místa, ale někdy je to pozdě 1123 01:01:27,760 --> 01:01:30,840 a já jsem unavený. 1124 01:01:30,840 --> 01:01:34,885 Existují i ​​jiné věci, o datové struktury? 1125 01:01:34,885 --> 01:01:37,510 Jsem si jistý, že kluci opravdu chceš mluvit o nich už, 1126 01:01:37,510 --> 01:01:42,650 ale pokud tam jsou, jsem rád, že jít přes ně, stejně jako cokoliv 1127 01:01:42,650 --> 01:01:45,580 z přednášky letos týden nebo minulý týden. 1128 01:01:45,580 --> 01:01:51,580 >> Vím, že minulý týden byl celý přezkum, tak Možná jsme přeskočil nějakou recenzi 1129 01:01:51,580 --> 01:01:54,190 z přednášky. 1130 01:01:54,190 --> 01:01:58,230 Jakékoliv další dotazy mohu odpovědět? 1131 01:01:58,230 --> 01:01:59,350 OK, v pořádku. 1132 01:01:59,350 --> 01:02:02,400 No, vy dostanete se 15 minut dříve. 1133 01:02:02,400 --> 01:02:08,370 >> Doufám, že to bylo částečně užitečné alespoň a já uvidíte kluci příští týden, 1134 01:02:08,370 --> 01:02:12,150 nebo ve čtvrtek úřední hodiny. 1135 01:02:12,150 --> 01:02:15,285 Existují žádosti o občerstvení na příští týden, to je věc? 1136 01:02:15,285 --> 01:02:17,459 Protože jsem zapomněl cukroví dnes. 1137 01:02:17,459 --> 01:02:19,750 A já jsem přinesl cukroví poslední týden, ale bylo to Columbus Day, 1138 01:02:19,750 --> 01:02:25,400 tak tam bylo tak šest lidí, kteří se měl čtyři pytle cukroví pro sebe. 1139 01:02:25,400 --> 01:02:28,820 Můžu přinést starburst znovu, pokud se vám líbí. 1140 01:02:28,820 --> 01:02:29,580 Starburst? 1141 01:02:29,580 --> 01:02:32,250 OK, to zní dobře. 1142 01:02:32,250 --> 01:02:35,050 Mají velký den, kluci. 1143 01:02:35,050 --> 01:02:39,510