1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [Prehrávanie hudby] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID Malan: To je CS50. 5 00:00:14,010 --> 00:00:18,090 A to je ako začiatok a end-- ako literally-- takmer do konca 6 00:00:18,090 --> 00:00:18,825 týždňa šesť. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Myslel som, že by som zdieľať trochu zábavné skutočnosti. 9 00:00:22,640 --> 00:00:25,370 Som vytiahol to až z nastaviť údaje minulého semestra. 10 00:00:25,370 --> 00:00:29,710 Možno si spomeniete, že sme sa vás opýtať na každom p set formulár, ak ste sledovali on-line 11 00:00:29,710 --> 00:00:31,580 alebo ak ste sa zúčastnili osobne. 12 00:00:31,580 --> 00:00:33,020 A tu je v dátach. 13 00:00:33,020 --> 00:00:34,710 Takže dnes bol veľmi predvídateľný. 14 00:00:34,710 --> 00:00:37,126 Ale my sme chceli stráviť trochu času s vami však. 15 00:00:37,126 --> 00:00:40,599 Chcel by niekto dohadu, prečo sa to graf je tak Jaggy, hore dole, hore dole, 16 00:00:40,599 --> 00:00:41,265 tak dôsledne? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Čo každý z vrcholov a žľaby predstavujú? 19 00:00:45,130 --> 00:00:46,005 >> Divákov: [nepočuteľné] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID Malan: Naozaj. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 A viac zábavne, nedaj bože, máme jednu prednášku v piatok 24 00:00:55,480 --> 00:00:58,960 na začiatku semestra, že to, čo vidíme, sa stalo. 25 00:00:58,960 --> 00:01:03,430 Takže dnes sme sa zapojiť do trochu Ďalšie informácie o dátových štruktúrach. 26 00:01:03,430 --> 00:01:06,660 A dať vám viac pevnej látky mentálny model pre problémy v päť, 27 00:01:06,660 --> 00:01:07,450 ktorý je teraz von. 28 00:01:07,450 --> 00:01:10,817 Pravopisné chyby, kde budeme odovzdať vám textový súbor niektorí 100.000 29 00:01:10,817 --> 00:01:12,650 a anglické slová, a budete mať 30 00:01:12,650 --> 00:01:17,770 prísť na to, ako šikovne ich načítať do pamäte, do pamäte RAM, pomocou niektoré údaje 31 00:01:17,770 --> 00:01:19,330 Štruktúra vášho výberu. 32 00:01:19,330 --> 00:01:22,470 >> Práve jedna taká dátová štruktúra by mohla byť, ale pravdepodobne by nemala byť, 33 00:01:22,470 --> 00:01:25,630 pomerne zjednodušujúce spájať zoznam, ktoré sme uviedli minule. 34 00:01:25,630 --> 00:01:29,220 A spájať zoznam mal aspoň jedna výhoda oproti maticu. 35 00:01:29,220 --> 00:01:32,096 Čo je jedna z výhod spájať zoznam pravdepodobne? 36 00:01:32,096 --> 00:01:32,950 >> Divákov: Vloženie. 37 00:01:32,950 --> 00:01:33,908 >> DAVID Malan: Vloženie. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Čo tým myslíš? 40 00:01:35,196 --> 00:01:37,872 >> Divákov: Anywhere spolu zoznam [nepočuteľné]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID Malan: Dobrý. 42 00:01:38,770 --> 00:01:42,090 Takže môžete vložiť prvok, kdekoľvek Chcete uprostred zoznamu 43 00:01:42,090 --> 00:01:45,490 bez toho aby museli zamiešať čokoľvek, ktoré sme uzavreli v našom triedenie 44 00:01:45,490 --> 00:01:47,630 diskusie, nie je nutne dobrá vec, 45 00:01:47,630 --> 00:01:51,200 pretože to si vyžaduje určitý čas, aby skutočne pohybovať všetkých tých ľudí vľavo alebo vpravo. 46 00:01:51,200 --> 00:01:55,540 A tak sa spájať zoznam, môžete len prideliť s malloc, nový uzol, 47 00:01:55,540 --> 00:01:58,385 a potom aktualizovať pár pointers-- dva, tri operácie max-- 48 00:01:58,385 --> 00:02:01,480 a sme schopní slot niekoho kdekoľvek do zoznamu. 49 00:02:01,480 --> 00:02:03,550 >> Čo iného bolo výhodné o prepojenom zoznamu? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Jo? 52 00:02:05,659 --> 00:02:06,534 >> Divákov: [nepočuteľné] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID Malan: Perfect. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Perfect. 57 00:02:11,090 --> 00:02:12,070 Je to naozaj dynamický. 58 00:02:12,070 --> 00:02:15,100 A že nie ste spáchanie, dopredu, do určitej pevnej veľkosti 59 00:02:15,100 --> 00:02:18,750 kus pamäti, ako by ste mať sa s poľa, inflačné ktoré 60 00:02:18,750 --> 00:02:22,455 je, že môžete prideľovať uzly iba na dopyt a tým používať len toľko miesta 61 00:02:22,455 --> 00:02:23,330 ako skutočne potrebujete. 62 00:02:23,330 --> 00:02:26,830 Na rozdiel od poľa, môžete náhodne rozdeliť príliš málo. 63 00:02:26,830 --> 00:02:28,871 A potom je to len bude byť bolesť v krku 64 00:02:28,871 --> 00:02:32,440 prerozdeliť nové väčšie pole, skopírujte všetko skončí, uvoľniť staré polia, 65 00:02:32,440 --> 00:02:33,990 a potom sa presunúť o vašej firme. 66 00:02:33,990 --> 00:02:37,479 Alebo ešte horšie, môžete prideliť cestu viac pamäte, než skutočne potrebujete, 67 00:02:37,479 --> 00:02:40,520 a tak budete mať veľmi riedko osídlené poľa, aby som tak povedal. 68 00:02:40,520 --> 00:02:44,350 >> Takže spájať zoznam vám tieto Výhody dynamiky a flexibility 69 00:02:44,350 --> 00:02:46,080 s inzerciou a deléciou. 70 00:02:46,080 --> 00:02:48,000 Ale určite tam musí byť zaplatená cena. 71 00:02:48,000 --> 00:02:50,000 V skutočnosti, jednou z tém preskúmať testu nulovej 72 00:02:50,000 --> 00:02:52,430 bol pár z kompromisov sme videli doteraz. 73 00:02:52,430 --> 00:02:56,161 Takže to, čo je cena, ktorú zaplatil alebo Nevýhodou prepojeného zoznamu? 74 00:02:56,161 --> 00:02:56,660 Jo. 75 00:02:56,660 --> 00:02:57,560 >> Divákov: Nie náhodný prístup. 76 00:02:57,560 --> 00:02:58,809 >> DAVID Malan: No náhodný prístup. 77 00:02:58,809 --> 00:02:59,540 Ale koho to zaujíma? 78 00:02:59,540 --> 00:03:01,546 Náhodný prístup neznie presvedčivé. 79 00:03:01,546 --> 00:03:02,421 >> Divákov: [nepočuteľné] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID Malan: Presne tak. 82 00:03:05,740 --> 00:03:07,580 Ak chcete mať určitej algorithm-- 83 00:03:07,580 --> 00:03:10,170 a dovoľte mi, aby som v skutočnosti navrhnúť binárne vyhľadávanie, najmä, čo 84 00:03:10,170 --> 00:03:12,600 je tá, ktorú sme použili celkom bit-- ak nemáte náhodný prístup, 85 00:03:12,600 --> 00:03:15,516 môžete to urobiť jednoduchú aritmetiku nájdenie ako prostredný prvok 86 00:03:15,516 --> 00:03:16,530 a skákanie na neho právo. 87 00:03:16,530 --> 00:03:20,239 Namiesto toho budete musieť začať v prvej element a lineárne vyhľadávania zľava 88 00:03:20,239 --> 00:03:22,780 doprava, ak chcete nájsť stredná alebo akýkoľvek iný prvok. 89 00:03:22,780 --> 00:03:24,410 >> Divákov: Asi potrebuje viac pamäte. 90 00:03:24,410 --> 00:03:25,040 >> DAVID Malan: berie viac pamäte. 91 00:03:25,040 --> 00:03:27,464 Kde je ten ďalší náklady prichádzajúce z pamäti? 92 00:03:27,464 --> 00:03:28,339 >> Divákov: [nepočuteľné] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID Malan: Presne tak. 95 00:03:33,440 --> 00:03:35,679 V tomto prípade je tu, mali sme spájať zoznam pre celé čísla, 96 00:03:35,679 --> 00:03:37,470 a napriek tomu sme zdvojnásobenie množstvo pamäte 97 00:03:37,470 --> 00:03:39,680 musíme tým, že tiež uloženie týchto ukazovateľov. 98 00:03:39,680 --> 00:03:42,090 Teraz menej veľký problém, ako Vaša structs sa zväčší 99 00:03:42,090 --> 00:03:45,320 a vy ste ukladanie nie je číslo, ale Možno študent alebo nejaký iný predmet. 100 00:03:45,320 --> 00:03:46,880 Ale ide samozrejme zostáva. 101 00:03:46,880 --> 00:03:49,421 A tak počet operácií na spojových zoznamov boli povolaní 102 00:03:49,421 --> 00:03:50,570 Boli veľké-O n- lineárne. 103 00:03:50,570 --> 00:03:54,730 Veci ako vloženie alebo hľadanie alebo delécie v prípade, že prvok 104 00:03:54,730 --> 00:03:57,720 sa stalo, že na samom konci Zoznam či už je to triedeného alebo nie. 105 00:03:57,720 --> 00:04:01,167 >> Niekedy môžete mať šťastie a takže spodnej medze týchto operácií 106 00:04:01,167 --> 00:04:04,250 môže byť tiež konštantný čas, ak ste vždy pri pohľade na prvý prvok, 107 00:04:04,250 --> 00:04:05,070 napríklad. 108 00:04:05,070 --> 00:04:09,360 Ale nakoniec sme sľúbili k dosiahnutiu svätý grál 109 00:04:09,360 --> 00:04:12,630 dátových štruktúr, alebo niektoré aproximácie tejto zmluvy, 110 00:04:12,630 --> 00:04:14,290 prostredníctvom konštantnom čase. 111 00:04:14,290 --> 00:04:17,579 Môžeme nájsť prvky, alebo pridať prvky alebo odstránenie prvkov zo zoznamu? 112 00:04:17,579 --> 00:04:19,059 Uvidíme už čoskoro. 113 00:04:19,059 --> 00:04:21,100 A ukázalo sa, že jeden mechanizmov sme 114 00:04:21,100 --> 00:04:23,464 začnú používať dnes, ročná spotreba v p nastaviť päť, 115 00:04:23,464 --> 00:04:24,630 je vlastne celkom známe. 116 00:04:24,630 --> 00:04:27,430 Napríklad, ak je to banda skúšky kníh, z ktorých každý 117 00:04:27,430 --> 00:04:29,660 má študent je prvá Meno a priezvisko na tom, 118 00:04:29,660 --> 00:04:31,820 a ja som vyzdvihnúť z ich na konci testu, 119 00:04:31,820 --> 00:04:33,746 a všetci sú dosť veľa v náhodnom poradí, 120 00:04:33,746 --> 00:04:36,370 a chceme ísť o triedení Tieto skúšky tak, že akonáhle sa stupňom 121 00:04:36,370 --> 00:04:38,661 je to proste oveľa jednoduchšie a rýchlejšie odovzdať je späť 122 00:04:38,661 --> 00:04:40,030 študentom abecedy. 123 00:04:40,030 --> 00:04:42,770 Čo by vaše inštinkty sa na hromadu skúšok, ako je tento? 124 00:04:42,770 --> 00:04:45,019 >> No, ak ste ako ja, môže vidieť, že sa jedná m, 125 00:04:45,019 --> 00:04:48,505 tak budem nejako dať to do, ak je to môj stôl alebo môj poschodia, kde 126 00:04:48,505 --> 00:04:50,650 Som šíri veci out-- alebo moje pole really-- 127 00:04:50,650 --> 00:04:52,210 Mohol by som dať všetky Ms tam. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Tu je A. Takže by som mohol dať ako tu. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Tu je ďalší A. idem dať to sem. 132 00:04:57,980 --> 00:05:02,490 Tu je Z. Tu je ďalší M. A tak Mohol by som začať robiť pilotov, ako je tento. 133 00:05:02,490 --> 00:05:06,620 A potom možno by som ísť neskôr a druh veľmi nitpicky-ly sort 134 00:05:06,620 --> 00:05:07,710 jednotlivé pilóty. 135 00:05:07,710 --> 00:05:11,300 Ale ide o to by som sa na vstupe, že som rukou 136 00:05:11,300 --> 00:05:14,016 a ja by som sa niektoré vypočíta rozhodnutia založené na tomto vstupe. 137 00:05:14,016 --> 00:05:15,640 Ak sa začína, dať to tam. 138 00:05:15,640 --> 00:05:18,980 Ak sa začne s Z, dal ju tam, a všetko medzi tým. 139 00:05:18,980 --> 00:05:22,730 >> Takže to je technika, ktorá je všeobecne známe ako hashing-- H-A-S-H- 140 00:05:22,730 --> 00:05:26,550 čo všeobecne znamená, že ako vstup a pomocou tohto vstupu pre výpočet 141 00:05:26,550 --> 00:05:30,940 hodnotu, zvyčajne číslo, a že číslo je index do skladu 142 00:05:30,940 --> 00:05:32,260 Nádoba, ako pole. 143 00:05:32,260 --> 00:05:35,490 Takže inými slovami, mohol by som mať hash funkcie, ako ja v mojej hlave, 144 00:05:35,490 --> 00:05:37,940 že keď vidím niekoho to Názov, ktorý sa začína, 145 00:05:37,940 --> 00:05:40,190 Chystám sa mapa, ktorá na nulu v mojej hlave. 146 00:05:40,190 --> 00:05:44,160 A keď vidím niekoho s Z, som bude mapovať, že až 25 v mojej hlave 147 00:05:44,160 --> 00:05:46,220 a potom to dať do posledná najviac hromada. 148 00:05:46,220 --> 00:05:50,990 >> Teraz, keď sa nad tým zamyslíte nie je môj mozog ale program v jazyku C, ktoré čísla by mohla 149 00:05:50,990 --> 00:05:53,170 sa spoľahnúť na dosiahnutie tohto rovnakého výsledku? 150 00:05:53,170 --> 00:05:55,594 Inými slovami, ak máte mal ASCII znak A, 151 00:05:55,594 --> 00:05:57,510 Ako zistíte, čo vedro, aby to v? 152 00:05:57,510 --> 00:05:59,801 Pravdepodobne nebudete chcieť dať do vedra 65, ktorý 153 00:05:59,801 --> 00:06:01,840 by bolo ako tam bez dobrého dôvodu. 154 00:06:01,840 --> 00:06:04,320 Kde chcete dať pokiaľ ide o jeho ASCII hodnota? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Kam chceš urobiť, aby jeho ASCII hodnota prísť s múdrejší vedra 157 00:06:08,920 --> 00:06:09,480 aby ju v? 158 00:06:09,480 --> 00:06:10,206 >> Divákov: Mínus A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID Malan: Jo. 160 00:06:10,956 --> 00:06:13,190 Takže mínus alebo mínus konkrétne 65, ak je to 161 00:06:13,190 --> 00:06:18,240 kapitál A. Alebo 98, ak je to malé. 162 00:06:18,240 --> 00:06:21,300 A tak, že by nám umožňujú veľmi jednoducho a veľmi aritmeticky, 163 00:06:21,300 --> 00:06:23,260 dať niečo do vedra takhle. 164 00:06:23,260 --> 00:06:26,010 Tak to dopadá, že sme vlastne robiť to rovnako aj s kvízy. 165 00:06:26,010 --> 00:06:29,051 >> Takže si možno pamätáte si krúžil vaše Názov Výučba Kolegovia sa na obálke. 166 00:06:29,051 --> 00:06:32,270 A boli organizované mená TF sa do týchto stĺpcov podľa abecedy, 167 00:06:32,270 --> 00:06:34,400 No, verte tomu alebo nie, keď všetci 80 a nás 168 00:06:34,400 --> 00:06:37,800 sa dali dohromady v noci do platovej triedy, posledný krok v našom procese triedenia, 169 00:06:37,800 --> 00:06:41,830 je hash kvízy do veľkej priestor podlahy na [nepočuteľné] 170 00:06:41,830 --> 00:06:45,110 a položiť kvízy Každý by presne poradí ich TF rokov 171 00:06:45,110 --> 00:06:47,700 mená na obálke, pretože potom je to oveľa jednoduchšie pre nás 172 00:06:47,700 --> 00:06:51,290 prehľadávať že pomocou lineárnej vyhľadávanie alebo nejaký chytrosti 173 00:06:51,290 --> 00:06:54,050 pre TF nájsť jeho alebo kvízy svojich študentov. 174 00:06:54,050 --> 00:06:56,060 >> Takže táto myšlienka z hash ktoré uvidíte, je 175 00:06:56,060 --> 00:07:00,520 celkom silný je vlastne celkom samozrejmosťou a veľmi intuitívne, 176 00:07:00,520 --> 00:07:03,000 podobne ako napríklad rozdeliť a dobytie bolo v týždni nula. 177 00:07:03,000 --> 00:07:05,250 Aj rýchlo vpred na hackathon pred pár rokmi. 178 00:07:05,250 --> 00:07:08,040 To bol Zamyla a pár Ostatní zamestnanci pozdrav študenti 179 00:07:08,040 --> 00:07:09,030 ako prišli. 180 00:07:09,030 --> 00:07:12,680 A mali sme veľa skladanie Stoly s menovkami. 181 00:07:12,680 --> 00:07:15,380 A my sme mali menovky organizovanej sa ako ako cez tú 182 00:07:15,380 --> 00:07:16,690 a Zs tam. 183 00:07:16,690 --> 00:07:20,350 A tak jedným z TFS veľmi šikovne písal to ako návod 184 00:07:20,350 --> 00:07:21,030 na deň. 185 00:07:21,030 --> 00:07:24,480 A v 12. týždni semestra tohto všetko dávalo zmysel a všetky 186 00:07:24,480 --> 00:07:25,310 vedel, čo má robiť. 187 00:07:25,310 --> 00:07:27,900 Ale kedykoľvek som fronte rovnakým spôsobom, 188 00:07:27,900 --> 00:07:30,272 budete sa vykonáva Rovnaký pojem hash. 189 00:07:30,272 --> 00:07:31,730 Takže poďme formalizovať to trochu. 190 00:07:31,730 --> 00:07:32,890 Tu je pole. 191 00:07:32,890 --> 00:07:36,820 Je vypracovaný, aby sa trochu široký len líčiť, vizuálne, 192 00:07:36,820 --> 00:07:38,920 že by sme mohli dať reťazca v niečom, ako je toto. 193 00:07:38,920 --> 00:07:41,970 A toto pole je zjavne veľkosť 26 celkom. 194 00:07:41,970 --> 00:07:43,935 A vec sa nazýva Tabuľka ľubovoľne. 195 00:07:43,935 --> 00:07:48,930 Ale to je len umelca stvárnenie o tom, čo by mohlo byť hash tabuľky. 196 00:07:48,930 --> 00:07:52,799 >> Takže hash tabuľka teraz sa chystá byť vyššia štruktúru dát na úrovni. 197 00:07:52,799 --> 00:07:54,840 Koniec koncov chystáme vidieť, že vás 198 00:07:54,840 --> 00:07:58,700 môžu implementovať hash tabuľku, ktorá je podobne ako check-v súlade 199 00:07:58,700 --> 00:08:02,059 na hackathon podobne ako tento Tabuľka slúži k triedenie skúšku kníh. 200 00:08:02,059 --> 00:08:03,850 Ale hash tabuľka druh tejto vysokej úrovni 201 00:08:03,850 --> 00:08:08,250 koncept, ktorý by mohol použiť pole pod kryt na jeho vykonanie, 202 00:08:08,250 --> 00:08:11,890 alebo použiť zoznam dĺžky, alebo dokonca možno niektoré ďalšie dátové štruktúry. 203 00:08:11,890 --> 00:08:15,590 A teraz to theme-- prevzatia niektoré z týchto základných zložiek 204 00:08:15,590 --> 00:08:18,310 ako pole a budovy Blokovať teraz zo zoznamu dĺžky 205 00:08:18,310 --> 00:08:21,740 a vidieť, čo ešte môžeme stavať nad tie, ako prísady 206 00:08:21,740 --> 00:08:26,550 na recept, takže stále viac a viac zaujímavé a užitočné konečné výsledky. 207 00:08:26,550 --> 00:08:28,680 >> Tak s hash tabuľky môžeme ho zaviesť 208 00:08:28,680 --> 00:08:32,540 v pamäti obrazovo takto, ale ako by to vlastne byť kódované up? 209 00:08:32,540 --> 00:08:33,789 No, možno, pretože jednoducho je to. 210 00:08:33,789 --> 00:08:38,270 Ak KAPACITA vo všetkých veľkých písmenách, je len niektorí constant-- napríklad 26, 211 00:08:38,270 --> 00:08:42,030 26 písmen alphabet-- Mohol by som zavolať svojej variabilný stôl, 212 00:08:42,030 --> 00:08:45,630 a mohol by som tvrdiť, že budem dať char hviezdy tam, alebo reťazec. 213 00:08:45,630 --> 00:08:49,880 Takže je to tak jednoduché, ako to, ak chcú zaviesť hash tabuľky. 214 00:08:49,880 --> 00:08:51,490 A napriek tomu, je to naozaj len pole. 215 00:08:51,490 --> 00:08:53,198 Ale opäť, hash Tabuľka je teraz, čo budeme 216 00:08:53,198 --> 00:08:57,470 zavolajte abstraktné dátový typ, ktorý je rovnako druh koncepčného vrstvenie na vrchole 217 00:08:57,470 --> 00:09:00,780 niečo viac svetského Teraz mi poľa. 218 00:09:00,780 --> 00:09:02,960 >> A teraz, ako máme ísť o riešenie problémov? 219 00:09:02,960 --> 00:09:06,980 No, skôr som mal luxus mať dostatok tabuľkový priestor tu 220 00:09:06,980 --> 00:09:09,460 tak, že by som mohol dať kvízy nikde som chcel. 221 00:09:09,460 --> 00:09:10,620 Tak, aby mohla ísť sem. 222 00:09:10,620 --> 00:09:12,100 Zs môže ísť sem. 223 00:09:12,100 --> 00:09:13,230 Pani môže ísť sem. 224 00:09:13,230 --> 00:09:14,740 A potom som mal nejaké extra priestor. 225 00:09:14,740 --> 00:09:18,740 Ale to je trochu cheat práva teraz, pretože tejto tabuľke, či som naozaj 226 00:09:18,740 --> 00:09:22,720 myslel na to ako pole, je len bude nejaké pevné veľkosti. 227 00:09:22,720 --> 00:09:25,380 >> Takže technicky, keď som vytiahnuť do iného študenta kvíz 228 00:09:25,380 --> 00:09:28,490 a vidieť, oh, táto osoba je Názov začína príliš, 229 00:09:28,490 --> 00:09:30,980 Tak nejako som chcel dať to tam. 230 00:09:30,980 --> 00:09:34,740 Ale akonáhle som to tam dal, ak je táto tabuľka skutočne predstavuje pole, 231 00:09:34,740 --> 00:09:37,840 Chystám sa byť prevažujúci alebo prepisovanie kto tento študent kvíz je. 232 00:09:37,840 --> 00:09:38,340 Je to tak? 233 00:09:38,340 --> 00:09:41,972 Pokiaľ sa jedná o pole, len jedna vec môže ísť v každej z týchto buniek alebo prvkov. 234 00:09:41,972 --> 00:09:43,680 A tak nejako som sa vybrať a zvoliť. 235 00:09:43,680 --> 00:09:45,735 >> Teraz skôr som tak trochu podvádzal a robil to alebo I 236 00:09:45,735 --> 00:09:47,526 len tak na seba je nad sebou. 237 00:09:47,526 --> 00:09:49,170 Ale to nebude lietať v kóde. 238 00:09:49,170 --> 00:09:52,260 Tak, kde som mohol dať Druhý študent, ktorého meno 239 00:09:52,260 --> 00:09:54,964 Ak je všetko, čo som mal, je to k dispozícii tabuľkový priestor? 240 00:09:54,964 --> 00:09:57,880 A ja som použil tri sloty a to vyzerá to, že je to len niekoľko ďalších. 241 00:09:57,880 --> 00:09:58,959 Čo si to mohol urobiť? 242 00:09:58,959 --> 00:09:59,834 Divákov: [nepočuteľné] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID Malan: Jo. 245 00:10:01,315 --> 00:10:02,370 Možno, povedzme, aby to jednoduché. 246 00:10:02,370 --> 00:10:02,660 Je to tak? 247 00:10:02,660 --> 00:10:04,243 To sa nehodí tam, kde chcem, aby to. 248 00:10:04,243 --> 00:10:07,450 Takže idem dať technicky kde by B ísť. 249 00:10:07,450 --> 00:10:09,932 Teraz, samozrejme, ja začínam maľovať sám seba do kúta. 250 00:10:09,932 --> 00:10:11,890 Ak sa dostanem na študenta ktorého meno je vlastne B, 251 00:10:11,890 --> 00:10:14,840 Teraz B bude pohybovať trochu dopredu, ako by sa mohlo stať, jo, 252 00:10:14,840 --> 00:10:17,530 ak je to B, teraz to musí ísť sem. 253 00:10:17,530 --> 00:10:20,180 >> A tak sa veľmi rýchlo by sa mohlo stať problematickým, 254 00:10:20,180 --> 00:10:23,850 ale je to technika, ktorá v skutočnosti je označovaný ako lineárne snímanie, 255 00:10:23,850 --> 00:10:26,650 kedy stačí zvážiť svoje polia, že pozdĺž čiary. 256 00:10:26,650 --> 00:10:29,680 A práve typ snímača, alebo skontrolujte každú dostupné prvok 257 00:10:29,680 --> 00:10:31,360 hľadá k dispozícii na mieste. 258 00:10:31,360 --> 00:10:34,010 A akonáhle zistíte, jedno, čo si len kvapka tam. 259 00:10:34,010 --> 00:10:38,390 >> Teraz je cena v dnešnej dobe venované pre toto riešenie je to, čo? 260 00:10:38,390 --> 00:10:41,300 Máme pevnú veľkosť poľa, a pri vložení mena 261 00:10:41,300 --> 00:10:44,059 do neho, aspoň spočiatku, čo je doba chodu vloženie 262 00:10:44,059 --> 00:10:46,350 pre uvedenie študentov " kvízy na správnych vedierka? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O čo? 265 00:10:50,002 --> 00:10:51,147 >> Divákov: n. 266 00:10:51,147 --> 00:10:52,480 DAVID Malan: Počul som, že veľký O n. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 To nie je pravda. 269 00:10:54,300 --> 00:10:56,490 Ale budeme dráždiť seba prečo za chvíľu. 270 00:10:56,490 --> 00:10:57,702 Čo iné by to mohlo byť? 271 00:10:57,702 --> 00:10:58,755 >> Divákov: [nepočuteľné] 272 00:10:58,755 --> 00:11:00,380 DAVID Malan: A dovoľte mi, aby som to vizuálne. 273 00:11:00,380 --> 00:11:04,720 Takže predpokladám, že je to písmeno S. 274 00:11:04,720 --> 00:11:05,604 >> Divákov: Je to jedna. 275 00:11:05,604 --> 00:11:06,520 DAVID Malan: Je to jedno. 276 00:11:06,520 --> 00:11:06,710 Je to tak? 277 00:11:06,710 --> 00:11:08,950 To je pole, ktoré znamená, že máme náhodný prístup. 278 00:11:08,950 --> 00:11:11,790 A ak si myslíme, že to na nulu a to až 25, 279 00:11:11,790 --> 00:11:13,800 a my sme si uvedomili, že, oh, tu je môj vstup S, 280 00:11:13,800 --> 00:11:16,350 Ja určite previesť S, znak ASCII, 281 00:11:16,350 --> 00:11:18,540 do zodpovedajúceho počtu medzi nulou a 25 282 00:11:18,540 --> 00:11:20,910 a potom sa okamžite dať tam, kam patrí. 283 00:11:20,910 --> 00:11:26,120 >> Ale samozrejme, akonáhle sa dostanem do Druhá osoba, ktorá sa volá A alebo B alebo C 284 00:11:26,120 --> 00:11:29,300 nakoniec, ak som použil lineárne snímanie ako moje riešenie, 285 00:11:29,300 --> 00:11:31,360 Doba chodu vloženie v najhoršom prípade 286 00:11:31,360 --> 00:11:33,120 bude skutočne preniesť do čoho? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 A ja som počul tu správne čoskoro. 289 00:11:36,045 --> 00:11:36,920 Divákov: [nepočuteľné] 290 00:11:36,920 --> 00:11:41,620 DAVID Malan: Tak to je naozaj n raz máte dostatočne veľký súbor dát. 291 00:11:41,620 --> 00:11:44,410 Tak, na jednej strane, ak vaše pole je dostatočne veľký 292 00:11:44,410 --> 00:11:48,287 a vaše dáta je riedke dosť, vy si tento krásny konštantný čas. 293 00:11:48,287 --> 00:11:50,620 Ale akonáhle začnete stále viac a viac prvkov, 294 00:11:50,620 --> 00:11:53,200 a len štatisticky dostanete viac ľudí s písmenom 295 00:11:53,200 --> 00:11:56,030 Ako ich meno alebo písmeno B, mohlo by to potenciálne 296 00:11:56,030 --> 00:11:57,900 prejsť na niečo viac lineárny. 297 00:11:57,900 --> 00:11:59,640 Takže nie je úplne dokonalá. 298 00:11:59,640 --> 00:12:00,690 Tak by sme mohli robiť lepšie? 299 00:12:00,690 --> 00:12:03,210 >> No, čo bolo naše riešenie, ako keď sme sa 300 00:12:03,210 --> 00:12:06,820 Chcete mať väčšiu dynamiku ako niečo ako pole dovolené? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 Divákov: [nepočuteľné] 303 00:12:08,960 --> 00:12:10,030 DAVID Malan: Čo sme predstaviť? 304 00:12:10,030 --> 00:12:10,530 Jo. 305 00:12:10,530 --> 00:12:11,430 Takže spájať zoznam. 306 00:12:11,430 --> 00:12:14,430 No, uvidíme, čo súvisí Zoznam môže urobiť pre nás miesto. 307 00:12:14,430 --> 00:12:17,630 No, dovoľte mi, aby som navrhujem, aby sme nakresliť obrázok takto. 308 00:12:17,630 --> 00:12:19,620 Teraz je to iná obrázok z príkladu 309 00:12:19,620 --> 00:12:24,750 z iného textu, v skutočnosti, že je v skutočnosti pomocou poľa veľkosti 31. 310 00:12:24,750 --> 00:12:28,220 A to autor jednoducho rozhodol hash reťazca 311 00:12:28,220 --> 00:12:32,430 nie sú založené na mená tejto osoby, ale na základe ich narodeniny. 312 00:12:32,430 --> 00:12:35,680 Bez ohľadu na mesiace, ale prišiel ak ste sa narodil na prvý mesiac 313 00:12:35,680 --> 00:12:39,580 alebo 31. v mesiaci, autor hash bude na základe tejto hodnoty, 314 00:12:39,580 --> 00:12:44,154 tak, aby sa rozšírila mená sa trochu viac než len 26 miest, by mohli umožniť. 315 00:12:44,154 --> 00:12:47,320 A možno je to trochu jednotnejší ako ísť s písmenami abecedy, 316 00:12:47,320 --> 00:12:50,236 pretože samozrejme je to asi viac ľudí na celom svete sa menami 317 00:12:50,236 --> 00:12:54,020 ktoré začínajú ako iste niektoré ďalšie písmená abecedy. 318 00:12:54,020 --> 00:12:56,380 Takže možno je to trochu jednotnejší, za predpokladu, že 319 00:12:56,380 --> 00:12:58,640 rovnomerné rozloženie dojčiat po celé mesiace. 320 00:12:58,640 --> 00:12:59,990 >> Ale, samozrejme, je to stále nedokonalé. 321 00:12:59,990 --> 00:13:00,370 Je to tak? 322 00:13:00,370 --> 00:13:01,370 Budeme mať kolízie. 323 00:13:01,370 --> 00:13:04,680 Viac ľudí v tejto dátové štruktúry sú stále 324 00:13:04,680 --> 00:13:08,432 majú rovnaký dátum narodenia najmenej ste bez ohľadu na mesiac. 325 00:13:08,432 --> 00:13:09,640 Ale čo sa autor urobil? 326 00:13:09,640 --> 00:13:13,427 No, vyzerá to, že máme celý rad na ľavej strane ťahané vertikálne, 327 00:13:13,427 --> 00:13:15,010 ale to je len umelca stvárnenie. 328 00:13:15,010 --> 00:13:18,009 Nezáleží na tom, akým smerom sa vás čerpať rad, je to ešte pole. 329 00:13:18,009 --> 00:13:20,225 Čo je to pole zdanlivo? 330 00:13:20,225 --> 00:13:21,500 >> Divákov: spájať zoznam. 331 00:13:21,500 --> 00:13:21,650 >> DAVID Malan: Jo. 332 00:13:21,650 --> 00:13:23,490 Vyzerá to, ako by to polia prepojeného zoznamu. 333 00:13:23,490 --> 00:13:26,490 Takže znova, do tohto bodu druhu použitie týchto dátových štruktúr teraz 334 00:13:26,490 --> 00:13:28,550 ako prísady do viacerých zaujímavé riešenie, 335 00:13:28,550 --> 00:13:30,862 môžete mať úplne Základné, rovnako ako pole, 336 00:13:30,862 --> 00:13:33,320 a potom niečo viac zaujímavé ako spájať zoznam 337 00:13:33,320 --> 00:13:36,660 a dokonca spojiť ich do ešte zaujímavejšie dátové štruktúry. 338 00:13:36,660 --> 00:13:39,630 A skutočne, taky by to sa nazýva hash tabuľky, 339 00:13:39,630 --> 00:13:42,610 pričom pole je naozaj hash tabuľka, 340 00:13:42,610 --> 00:13:45,600 ale to hash tabuľka reťaze, aby som tak povedal, 341 00:13:45,600 --> 00:13:50,220 že môže rásť alebo zmenšiť na základe počet prvkov, ktorý chcete vložiť. 342 00:13:50,220 --> 00:13:52,990 >> Teraz teda, čo je doba chodu teraz? 343 00:13:52,990 --> 00:13:58,030 Ak chcem vložiť niekoho ktorého narodeniny 31. októbra, 344 00:13:58,030 --> 00:13:59,040 kde sa on alebo ona ísť? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Dobrá. 347 00:14:01,030 --> 00:14:02,819 Na samom dne, kde sa hovorí, že 31. 348 00:14:02,819 --> 00:14:03,610 A to je perfektné. 349 00:14:03,610 --> 00:14:05,060 To bolo konštantný čas. 350 00:14:05,060 --> 00:14:08,760 Ale čo keď nájdeme niekoho iného ktorého narodeniny, poďme sa pozrieť, 351 00:14:08,760 --> 00:14:10,950 Október, november k 31? 352 00:14:10,950 --> 00:14:12,790 Ak sa on alebo ona ísť? 353 00:14:12,790 --> 00:14:13,290 To isté. 354 00:14:13,290 --> 00:14:13,970 Dvojstupňová hoci. 355 00:14:13,970 --> 00:14:15,303 To je konštantná aj keď je to tak? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Dobrá. 358 00:14:16,860 --> 00:14:17,840 V súčasnej dobe to je. 359 00:14:17,840 --> 00:14:20,570 Ale vo všeobecnom prípade, čím viac ľudí pridáme, 360 00:14:20,570 --> 00:14:23,790 pravdepodobnostne, ideme aby sa viac a viac ku kolíziám. 361 00:14:23,790 --> 00:14:26,820 >> Teraz je to trochu lepšie, pretože technicky 362 00:14:26,820 --> 00:14:34,580 teraz moje reťaze môžu byť v v najhoršom prípade, ako dlho? 363 00:14:34,580 --> 00:14:38,890 Ak mám vložiť n ľudí do toho viac sofistikované dátové štruktúry, n ľudí, 364 00:14:38,890 --> 00:14:41,080 V najhoršom prípade to bude n. 365 00:14:41,080 --> 00:14:41,815 Prečo? 366 00:14:41,815 --> 00:14:43,332 >> Divákov: Pretože keby každý má narodeniny v rovnaký deň, 367 00:14:43,332 --> 00:14:44,545 že budeš jeden riadok. 368 00:14:44,545 --> 00:14:45,420 DAVID Malan: Perfect. 369 00:14:45,420 --> 00:14:47,480 To by mohlo byť trochu neprirodzený, ale skutočne v najhoršom prípade, 370 00:14:47,480 --> 00:14:50,117 ak každý má narodeniny v rovnaký deň, s ohľadom na vstupy máte, 371 00:14:50,117 --> 00:14:51,950 budete mať masívne dlhým reťazcom. 372 00:14:51,950 --> 00:14:54,241 A áno, môžete ho hovoru hash tabuľky, ale v skutočnosti je to 373 00:14:54,241 --> 00:14:56,810 len masívne spájať zoznam s veľa nevyužitého miesta. 374 00:14:56,810 --> 00:15:00,460 Ale všeobecne, ak budeme predpokladať, že aspoň narodeniny sú uniform-- 375 00:15:00,460 --> 00:15:01,750 a to asi nie je. 376 00:15:01,750 --> 00:15:02,587 Robím, že až. 377 00:15:02,587 --> 00:15:04,420 Ale ak budeme predpokladať, pre Z dôvodu diskusia 378 00:15:04,420 --> 00:15:07,717 že sú, potom teoreticky, ak To je vertikálny reprezentácia 379 00:15:07,717 --> 00:15:11,050 matice, no a potom dúfajme, že ste dostane reťazcov, ktoré sú, ako viete, 380 00:15:11,050 --> 00:15:15,880 zhruba rovnakú dĺžku, kde každý z to predstavuje deň v mesiaci. 381 00:15:15,880 --> 00:15:19,930 >> Teraz, keď je tam 31 dní v mesiaci, to znamená, že moja doba chodu naozaj 382 00:15:19,930 --> 00:15:25,230 je veľký O n viac ako 31, čo cíti lepšie ako lineárny. 383 00:15:25,230 --> 00:15:27,950 Ale to, čo bol jeden z našich Záväzky pár týždňov 384 00:15:27,950 --> 00:15:31,145 Pred keď to prišlo k vyjadrovaniu doba chodu algoritmu? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Stačí len pozrieť na vysokú objednávky termíne. 387 00:15:35,190 --> 00:15:35,690 Je to tak? 388 00:15:35,690 --> 00:15:37,400 31 je určite užitočné. 389 00:15:37,400 --> 00:15:39,610 Ale je to stále veľký O n. 390 00:15:39,610 --> 00:15:41,730 Ale jedným z tém o problém nastaviť päť 391 00:15:41,730 --> 00:15:43,950 bude na na vedomie, že absolútne, 392 00:15:43,950 --> 00:15:47,320 asymptoticky, teoreticky Táto dátová štruktúra 393 00:15:47,320 --> 00:15:50,470 nie je o nič lepší, než len jeden masívny spájať zoznam. 394 00:15:50,470 --> 00:15:53,550 A skutočne, v najhoršom prípade to hash tabuľka môže prejsť do toho. 395 00:15:53,550 --> 00:15:57,620 >> Ale v reálnom svete, s nami ľudia že vlastné Macintosha alebo PC, alebo čokoľvek 396 00:15:57,620 --> 00:16:01,240 a beží v reálnom svete softvér z reálnych dát, 397 00:16:01,240 --> 00:16:03,260 ktoré algoritmus budete preferovať? 398 00:16:03,260 --> 00:16:09,180 Ten, ktorý má koncové kroky alebo ten, ktorý trvá n deleno 31 stupňov 399 00:16:09,180 --> 00:16:12,900 nájsť nejakú časť dát alebo vyhľadať nejaké informácie? 400 00:16:12,900 --> 00:16:16,580 Myslím, že absolútne 31 značiek rozdiel v reálnom svete. 401 00:16:16,580 --> 00:16:18,540 To je 31 krát rýchlejšie. 402 00:16:18,540 --> 00:16:20,880 A my ľudia sú určite ísť si uvedomiť, že. 403 00:16:20,880 --> 00:16:23,004 >> Takže si uvedomiť rozpor tam medzi skutočne 404 00:16:23,004 --> 00:16:25,920 hovorí o tom, čo teoreticky a asymptoticky, ktoré rozhodne 405 00:16:25,920 --> 00:16:28,760 má hodnotu, ako sme videli, ale v reálnom svete, 406 00:16:28,760 --> 00:16:32,930 ak vám záleží len robiť človek šťastný pre všeobecné vstupy, 407 00:16:32,930 --> 00:16:36,010 môžete veľmi dobre chcete prijať skutočnosť, že áno, je to lineárny, 408 00:16:36,010 --> 00:16:38,360 ale to je 31 krát rýchlejší ako môže byť lineárny. 409 00:16:38,360 --> 00:16:41,610 A ešte lepšie, nebudeme musieť niečo ľubovoľného ako dátum narodenia, 410 00:16:41,610 --> 00:16:44,030 by sme mohli stráviť trochu viac času a chytrosť 411 00:16:44,030 --> 00:16:47,140 a premýšľať o tom, čo by sme mohli urobiť, krstné meno človeka, a možno 412 00:16:47,140 --> 00:16:50,130 Ich dátum narodenia kombinovať tie, zložky na niečo vymyslíme 413 00:16:50,130 --> 00:16:52,720 je to naozaj viac jednotná a menej Jaggy, 414 00:16:52,720 --> 00:16:56,250 aby som tak povedal, než tento obrázok V súčasnej dobe naznačuje, že by mohlo byť. 415 00:16:56,250 --> 00:16:57,750 Ako by sme mohli realizovať to v kóde? 416 00:16:57,750 --> 00:17:00,280 No, dovoľte mi, aby som navrhujem, aby sme len požičať nejaké syntax sme 417 00:17:00,280 --> 00:17:01,799 použitý párkrát tak ďaleko. 418 00:17:01,799 --> 00:17:03,590 A ja budem definovať uzol, ktorý opäť 419 00:17:03,590 --> 00:17:06,812 je všeobecný termín pre len niektoré Kontajner pre niektoré dátové štruktúry. 420 00:17:06,812 --> 00:17:09,020 Chystám sa navrhnúť, aby reťazec sa deje tam. 421 00:17:09,020 --> 00:17:11,369 Ale budeme začnete tých koliesok off teraz. 422 00:17:11,369 --> 00:17:13,230 >> Žiadne ďalšie CS50 knižnica Naozaj, ak budete chcieť 423 00:17:13,230 --> 00:17:15,230 ho použiť pre finále Projekt, ktorý je v poriadku, 424 00:17:15,230 --> 00:17:18,569 ale teraz budeme ťahať späť záclony a hovoria, že je to len znak hviezda. 425 00:17:18,569 --> 00:17:22,069 Takže slovo sa bude meno osoby v otázke. 426 00:17:22,069 --> 00:17:25,079 A teraz mám odkaz tu k ďalšiemu uzlu 427 00:17:25,079 --> 00:17:28,170 tak, že tieto predstavujú Každý z uzlov 428 00:17:28,170 --> 00:17:30,950 v reťazci, prípadne, prepojeného zoznamu. 429 00:17:30,950 --> 00:17:34,090 >> A teraz ako sa Vyhlasujem hash tabuľka sám? 430 00:17:34,090 --> 00:17:36,660 Ako môžem vyhlásiť celú túto štruktúru? 431 00:17:36,660 --> 00:17:40,960 No, naozaj, rovnako ako som použila ukazovateľ sa iba prvý prvok zoznamu 432 00:17:40,960 --> 00:17:44,510 predtým, podobne môžem len povedať, Proste potrebujem veľa ukazovateľov 433 00:17:44,510 --> 00:17:46,270 realizovať celý tento hash tabuľky. 434 00:17:46,270 --> 00:17:49,484 Budem mať celý rad volal tabuľka hash tabuľky. 435 00:17:49,484 --> 00:17:50,900 Bude to mať veľkosť kapacity. 436 00:17:50,900 --> 00:17:52,525 To je to, koľko prvkov sa vojde do neho. 437 00:17:52,525 --> 00:17:56,180 A každý z týchto prvkov v tomto pole bude uzol hviezda. 438 00:17:56,180 --> 00:17:56,810 Prečo? 439 00:17:56,810 --> 00:18:00,160 No, na obrázku je to, čo som vykonávanie hash tabuľku ako 440 00:18:00,160 --> 00:18:04,330 účinne na začiatku je len Toto pole, ktoré sme vypracovaný vo zvislom smere, 441 00:18:04,330 --> 00:18:06,820 každý z ktorého námestí predstavuje ukazovateľ. 442 00:18:06,820 --> 00:18:09,170 Že tie, ktoré majú lomítka medzi nimi sú len null. 443 00:18:09,170 --> 00:18:11,410 A tie, ktoré majú šípky idú doprava 444 00:18:11,410 --> 00:18:16,140 sú skutočné ukazovatele na skutočných uzlov, ergo začiatok spojovaceho zoznamu. 445 00:18:16,140 --> 00:18:19,050 >> Tak tu teda je, ako by sme mohli realizovať hash tabuľku, ktorá 446 00:18:19,050 --> 00:18:21,580 implementuje samostatný reťazenie. 447 00:18:21,580 --> 00:18:22,840 Teraz môžeme robiť lepšie? 448 00:18:22,840 --> 00:18:25,632 V poriadku som sľúbil minule, že by sme mohli dosiahnuť konštantný čas. 449 00:18:25,632 --> 00:18:27,381 A nejako som ti dal konštantný čas tu, 450 00:18:27,381 --> 00:18:29,850 ale potom povedal, že naozaj konštantný čas, pretože je to stále 451 00:18:29,850 --> 00:18:31,890 v závislosti na celkovej počet prvkov 452 00:18:31,890 --> 00:18:34,500 ste vklad do dátová štruktúra. 453 00:18:34,500 --> 00:18:35,980 Ale predpokladajme, že sme to urobili. 454 00:18:35,980 --> 00:18:39,550 Dovoľte mi, aby som sa vrátiť na obrazovku sem. 455 00:18:39,550 --> 00:18:44,520 Dovoľte mi, aby som tiež premietať to tu, jasné, obrazovky, a predpokladám, že som to urobil. 456 00:18:44,520 --> 00:18:49,300 Dajme tomu, že som chcel vložiť meno Daven v do mojej dátovej štruktúry. 457 00:18:49,300 --> 00:18:52,100 >> Tak som chcel vložiť reťazec Daven do dátovej štruktúry. 458 00:18:52,100 --> 00:18:54,370 Čo keď nemám používať hash tabuľky, ale ja používam 459 00:18:54,370 --> 00:18:56,980 niečo, čo je viac stromová ako rodokmeň, kde 460 00:18:56,980 --> 00:18:59,670 máte nejaké korene na Horné a potom uzly a listy 461 00:18:59,670 --> 00:19:01,440 ktoré idú dole a von. 462 00:19:01,440 --> 00:19:04,450 Predpokladajme teda, že ja chcete vložiť Daven je 463 00:19:04,450 --> 00:19:06,430 na to, čo je v súčasnej dobe prázdny zoznam. 464 00:19:06,430 --> 00:19:09,780 Chystám sa vykonať nasledujúce kroky: Ja som bude vytvárať uzol v tejto rodine 465 00:19:09,780 --> 00:19:15,170 stromová dátová štruktúra, ktorá vyzerá trochu ako je tento, z ktorých každý 466 00:19:15,170 --> 00:19:19,640 obdĺžniky sa, povedzme, Pre túto chvíľu 26 prvkov v ňom. 467 00:19:19,640 --> 00:19:21,650 A každý z buniek V tomto poli sa deje 468 00:19:21,650 --> 00:19:23,470 reprezentovať písmeno abecedy. 469 00:19:23,470 --> 00:19:28,190 >> Konkrétne sa budem liečiť to je, potom B, potom C, potom D, 470 00:19:28,190 --> 00:19:29,310 toto tu. 471 00:19:29,310 --> 00:19:32,940 Takže to bude účinne predstavujú písmeno D. 472 00:19:32,940 --> 00:19:36,040 Ale vložiť všetky Daven je meno musím urobiť trochu viac. 473 00:19:36,040 --> 00:19:37,840 Takže som prvýkrát bude hash, aby som tak povedal. 474 00:19:37,840 --> 00:19:41,049 Idem sa pozrieť na prvé písmeno v Daven je, čo je zrejme D, 475 00:19:41,049 --> 00:19:42,840 a budem prideliť uzol, ktorý vyzerá 476 00:19:42,840 --> 00:19:45,570 ako tohle-- veľký obdĺžnik veľký tak, aby sa zmestili na celú abecedu. 477 00:19:45,570 --> 00:19:47,140 >> Teraz D je hotovo. 478 00:19:47,140 --> 00:19:49,720 Teraz A. D-A-E-V-N je cieľ. 479 00:19:49,720 --> 00:19:51,220 Takže čo teraz budem robiť, je to. 480 00:19:51,220 --> 00:19:54,027 Akonáhle som začal D oznámenia Je tam žiadny ukazovateľ. 481 00:19:54,027 --> 00:19:56,860 Je to nezmyselné hodnoty v okamihu, alebo by som mohol inicializovať na hodnotu null. 482 00:19:56,860 --> 00:19:59,630 Ale dovoľte mi, aby som ďalej s Táto myšlienka vybudovania stromu. 483 00:19:59,630 --> 00:20:04,260 Dovoľte mi, aby som prideliť ďalšie z nich uzly, ktoré má 26 prvkov v nej. 484 00:20:04,260 --> 00:20:05,150 >> A viete čo? 485 00:20:05,150 --> 00:20:09,130 Ak je to len uzol v pamäti, že Vytvoril som s malloc pomocou struct 486 00:20:09,130 --> 00:20:11,240 ako čoskoro uvidíte, Chystám sa robiť tohle-- 487 00:20:11,240 --> 00:20:14,450 Budem čerpať šípku z to, čo reprezentoval D dole 488 00:20:14,450 --> 00:20:15,860 do tohto nového uzla. 489 00:20:15,860 --> 00:20:19,240 A teraz, najprv ďalšie písmeno Daven menom, 490 00:20:19,240 --> 00:20:24,150 V- D-A-V- Chystám sa ísť dopredu a čerpať ďalšie uzol takto, 491 00:20:24,150 --> 00:20:30,150 pričom sú tu prvky V, ktoré budeme čerpať pre instance-- Ups. 492 00:20:30,150 --> 00:20:31,020 Nebudeme tam kresliť. 493 00:20:31,020 --> 00:20:31,936 Bude to nájdete tu. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Potom ideme do Považujeme to za V. 496 00:20:35,712 --> 00:20:44,920 A potom tu budeme indexu dole z V na to, čo budeme považovať E. 497 00:20:44,920 --> 00:20:50,100 A potom tu budeme ísť jeden z týchto uzlov tu. 498 00:20:50,100 --> 00:20:52,930 A teraz tu máme otázku odpovedať. 499 00:20:52,930 --> 00:20:57,840 Musím nejako vyplýva, že sme na konci reťazca Daven. 500 00:20:57,840 --> 00:20:59,490 Takže som mohol len nechať null. 501 00:20:59,490 --> 00:21:02,670 >> Ale čo keď máme Daven je celé meno tiež, čo 502 00:21:02,670 --> 00:21:04,280 je, ako sme povedali, Davenport? 503 00:21:04,280 --> 00:21:06,970 Takže čo keď je Daven vlastne podreťazec, 504 00:21:06,970 --> 00:21:08,960 prefix oveľa dlhší reťazec? 505 00:21:08,960 --> 00:21:11,450 Nemôžeme len trvalo hovoria, nič sa deje 506 00:21:11,450 --> 00:21:14,410 tam ísť, pretože sme mohli Nikdy nevkladajte slovo ako Davenport 507 00:21:14,410 --> 00:21:15,840 do tejto dátovej štruktúry 508 00:21:15,840 --> 00:21:19,560 >> Takže to, čo by sme mohli urobiť, namiesto toho je zaobchádzať s každým z týchto prvkov 509 00:21:19,560 --> 00:21:22,170 ako možno mať dva prvky vo vnútri nich. 510 00:21:22,170 --> 00:21:24,810 Jedným z nich je ukazovateľ, naozaj, ako som robil. 511 00:21:24,810 --> 00:21:27,100 Takže každá z týchto krabíc nie je len jedna bunka. 512 00:21:27,100 --> 00:21:29,855 Ale čo v prípade, že horná one-- spodnej niečí 513 00:21:29,855 --> 00:21:32,230 bude nulový, pretože nie Davenport ešte nie. 514 00:21:32,230 --> 00:21:34,197 Čo v prípade, že jeden vrchol je nejaký zvláštny hodnota? 515 00:21:34,197 --> 00:21:36,530 A to bude trochu ťažké stanoviť, že táto veľkosť. 516 00:21:36,530 --> 00:21:38,130 Ale predpokladám, že je to len značka začiarknutia. 517 00:21:38,130 --> 00:21:38,920 Pozrite sa. 518 00:21:38,920 --> 00:21:44,230 D-E-V-N-je reťazec V tejto dátovej štruktúry. 519 00:21:44,230 --> 00:21:48,350 >> Medzitým, keby som mal viac priestoru tu som mohol robiť P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 a ja som mohol dať šek v uzle ktorý má na písmeno T na samom konci. 521 00:21:52,650 --> 00:21:55,460 Tak toto je masívne komplexné vyzerajúce štruktúru dát. 522 00:21:55,460 --> 00:21:57,210 A môj rukopis rozhodne nepomôže. 523 00:21:57,210 --> 00:22:00,043 Ale keď som chcel vložiť niečo iný, zvážte, čo budeme robiť. 524 00:22:00,043 --> 00:22:03,370 Ak by sme chceli, aby Dávida, by sme nasledovať rovnakú logiku, D-A-V, 525 00:22:03,370 --> 00:22:08,802 ale teraz by som upozorniť na ďalšie prvok, ktorý z E, ale od I do D. 526 00:22:08,802 --> 00:22:10,760 Takže tam to bude viac uzly tohto stromu. 527 00:22:10,760 --> 00:22:12,325 Budeme mať volania malloc viac. 528 00:22:12,325 --> 00:22:14,700 Ale ja nechcem, aby sa úplný zmätok obrázku. 529 00:22:14,700 --> 00:22:17,710 Takže poďme sa pozrieť na miesto jedného ktorá bola vopred formulovaná 530 00:22:17,710 --> 00:22:21,810 takto sa nie je bodka, bodka, bodky, ale len skrátene pole. 531 00:22:21,810 --> 00:22:23,950 Avšak každý z uzlov v tomto tu stromu hore 532 00:22:23,950 --> 00:22:26,700 predstavuje rovnaký thing-- pole Ray veľkosti 26. 533 00:22:26,700 --> 00:22:28,860 >> Alebo ak chceme byť naozaj správne teraz, čo 534 00:22:28,860 --> 00:22:30,790 ak niekto názov, apostrof, poďme 535 00:22:30,790 --> 00:22:35,560 Predpokladajme, že každý uzol má v skutočnosti ako 27 indexy v ňom, nie len 26 rokov. 536 00:22:35,560 --> 00:22:42,020 Tak to teraz bude dát Štruktúra nazýva trie-- T-R-I-E. 537 00:22:42,020 --> 00:22:46,120 Trie, ktorá je údajne historicky šikovný názov pre drevo 538 00:22:46,120 --> 00:22:49,040 , Ktorý je optimalizovaný pre vyhľadávanie, čo samozrejme, 539 00:22:49,040 --> 00:22:50,870 sa píše s I-E, takže je to trie. 540 00:22:50,870 --> 00:22:52,710 Ale to je história trie. 541 00:22:52,710 --> 00:22:55,860 >> Takže trie je to stromová údaje štruktúra ako rodinný strom 542 00:22:55,860 --> 00:22:57,510 že nakoniec sa chová takto. 543 00:22:57,510 --> 00:23:00,890 A tu je len ďalším príkladom toho, celá partia mien iných ľudí. 544 00:23:00,890 --> 00:23:03,540 Ale otázka teraz na dosah ruky je to, čo majú 545 00:23:03,540 --> 00:23:08,070 sme získali zavedením pravdepodobne viac zložitá štruktúra dát, a jeden, 546 00:23:08,070 --> 00:23:09,870 úprimne, že používa veľa pamäte. 547 00:23:09,870 --> 00:23:11,703 >> Vzhľadom k tomu, aj keď, v túto chvíľu, ja som len 548 00:23:11,703 --> 00:23:15,050 pomocou D je ukazovateľ a A V a Es a Ns, 549 00:23:15,050 --> 00:23:16,700 Som plytvanie sakra veľa pamäte. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Ale tam, kde som strávil jeden zdroj, Mám vo zvyku sa získať späť ďalšie. 552 00:23:22,660 --> 00:23:26,020 Takže keď som tráviť viac priestoru, čo je asi nádeje? 553 00:23:26,020 --> 00:23:27,407 Že som strávil menej čo? 554 00:23:27,407 --> 00:23:28,240 Divákov: Menej času. 555 00:23:28,240 --> 00:23:28,990 DAVID Malan: Čas. 556 00:23:28,990 --> 00:23:30,320 A prečo by to mohlo byť? 557 00:23:30,320 --> 00:23:33,880 No, a čo je vloženie čas, ak ide o veľký O teraz, 558 00:23:33,880 --> 00:23:37,660 mená, ako je Daven alebo Davenport alebo David? 559 00:23:37,660 --> 00:23:39,340 No, Daven bol päť krokov. 560 00:23:39,340 --> 00:23:42,350 Davenport by deväť krokov, tak to by bolo ešte niekoľko krokov. 561 00:23:42,350 --> 00:23:44,250 David by bol päť krokov rovnako. 562 00:23:44,250 --> 00:23:47,230 To sú konkrétne čísla, ale určite je tu 563 00:23:47,230 --> 00:23:49,550 horná medza Dĺžka niečí meno. 564 00:23:49,550 --> 00:23:52,240 A skutočne, v probléme sady piatich špecifikácia, 565 00:23:52,240 --> 00:23:54,050 budeme navrhovať že je to niečo, 566 00:23:54,050 --> 00:23:55,470 to je 40-niektoré-nepárne znaky. 567 00:23:55,470 --> 00:23:58,180 >> Realisticky, nikto nemá nekonečne dlhý názov, 568 00:23:58,180 --> 00:24:01,542 čo znamená, že dĺžka meno alebo dĺžka reťazca by sme mohli 569 00:24:01,542 --> 00:24:03,750 majú určitý stav Štruktúra je pravdepodobne to, čo? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Je to konštantná. 572 00:24:06,250 --> 00:24:06,430 Je to tak? 573 00:24:06,430 --> 00:24:09,310 Mohlo by to byť veľký ako konštantný 40-niečo, ale to je konštantná. 574 00:24:09,310 --> 00:24:13,752 A to nemá závislosti na tom, koľko Ostatné názvy v tejto dátovej štruktúre. 575 00:24:13,752 --> 00:24:15,460 Inými slovami, keď som chcel teraz vložiť 576 00:24:15,460 --> 00:24:20,540 Colton alebo Gabriel alebo Rob alebo Zamyla alebo Alison alebo Belinda alebo iné názvy 577 00:24:20,540 --> 00:24:23,940 z radov zamestnancov do týchto údajov štruktúra, je doba chodu 578 00:24:23,940 --> 00:24:26,750 vloženie ďalšie mená bude vôbec ovplyvnené 579 00:24:26,750 --> 00:24:30,220 podľa toho, ako mnoho ďalších prvkov, sú v dátovej štruktúre už? 580 00:24:30,220 --> 00:24:31,040 To nie. 581 00:24:31,040 --> 00:24:31,540 Je to tak? 582 00:24:31,540 --> 00:24:36,150 Vzhľadom k tomu, že sme efektívne používať Tento multi-layer hash tabuľky. 583 00:24:36,150 --> 00:24:38,280 A beží čas Niektoré z týchto operácií 584 00:24:38,280 --> 00:24:41,510 nezávisí od počtu prvky, ktoré sú v dátovej štruktúre 585 00:24:41,510 --> 00:24:43,090 alebo že sa nakoniec bude byť v dátovej štruktúre, 586 00:24:43,090 --> 00:24:44,714 ale na dĺžke čo konkrétne? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> Reťazec je vložená, ktorý predsa robí 589 00:24:49,200 --> 00:24:52,580 tento asymptoticky konštantný time-- veľký O jednej. 590 00:24:52,580 --> 00:24:54,720 A úprimne povedané, práve v reálnom svete, to 591 00:24:54,720 --> 00:24:58,380 znamená vloženie Daven meno sa ako piatich krokoch, alebo Davenport deväť 592 00:24:58,380 --> 00:25:00,100 kroky, alebo David päť krokov. 593 00:25:00,100 --> 00:25:03,071 To je sakramentsky malá prevádzkovej doby. 594 00:25:03,071 --> 00:25:05,320 A naozaj, je to veľmi dobrá vec, najmä keď 595 00:25:05,320 --> 00:25:08,126 to nie je závislé na celkovej počet prvkov v tam. 596 00:25:08,126 --> 00:25:10,500 Tak ako môžeme realizovať tento druh štruktúry v kóde? 597 00:25:10,500 --> 00:25:12,900 Je to trochu viac zložité, ale napriek tomu je to 598 00:25:12,900 --> 00:25:15,050 len aplikácie základné stavebné kamene. 599 00:25:15,050 --> 00:25:17,830 Chystám sa znovu definovať nás uzol takto: 600 00:25:17,830 --> 00:25:21,100 bool volal word--, a to by sa dalo nazvať čokoľvek. 601 00:25:21,100 --> 00:25:23,970 Ale bool predstavuje to, čo som nakreslil ako začiarknutie. 602 00:25:23,970 --> 00:25:24,490 Áno. 603 00:25:24,490 --> 00:25:26,720 To je koniec reťazca V tejto dátovej štruktúry. 604 00:25:26,720 --> 00:25:30,702 >> A samozrejme, uzol hviezda sa odkazuje na deti. 605 00:25:30,702 --> 00:25:32,410 A naozaj, rovnako ako rodokmeň, budete 606 00:25:32,410 --> 00:25:34,370 by zvážiť uzly ktoré visí 607 00:25:34,370 --> 00:25:36,920 dna niektorých rodičia element byť deti. 608 00:25:36,920 --> 00:25:40,510 A tak sa deti sa chystá byť pole 27, 27. jedna 609 00:25:40,510 --> 00:25:41,680 byť len pre apostrof. 610 00:25:41,680 --> 00:25:43,390 Budeme triediť o osobitný prípad, že. 611 00:25:43,390 --> 00:25:45,400 Takže môžete mať isté mená s apostrofmi. 612 00:25:45,400 --> 00:25:47,399 Možno aj pomlčkou musia tam ísť, ale budete 613 00:25:47,399 --> 00:25:50,330 viď str sade 5 my len starostlivosť o listov a apostrofy. 614 00:25:50,330 --> 00:25:52,990 >> A potom ako si predstavujú dátová štruktúra sama o sebe? 615 00:25:52,990 --> 00:25:56,454 Ako si predstavujú koreň tohto trie, aby som tak povedal? 616 00:25:56,454 --> 00:25:59,620 No, rovnako ako s prepojeného zoznamu, vždy ho potrebujú ukazovateľ na prvý prvok. 617 00:25:59,620 --> 00:26:04,270 S trie stačí jeden ukazovateľ na koreň tohto trie. 618 00:26:04,270 --> 00:26:07,290 A odtiaľ môžete hash vaša cesta dole hlbšie a hlbšie 619 00:26:07,290 --> 00:26:10,460 pre každý uzol v štruktúre. 620 00:26:10,460 --> 00:26:13,440 Tak jednoducho sa to môže predstavujeme, že struct. 621 00:26:13,440 --> 00:26:15,877 >> Teraz Meanwhile-- Oh, otázku. 622 00:26:15,877 --> 00:26:17,220 >> Divákov: Čo je bool slovo? 623 00:26:17,220 --> 00:26:20,490 >> DAVID Malan: BOOL slovo práve táto inkarnácia C 624 00:26:20,490 --> 00:26:22,920 z toho, čo som popísal V tomto boxe tu, keď 625 00:26:22,920 --> 00:26:26,000 Začal som rozdelenie každého z prvky poľa do dvoch častí. 626 00:26:26,000 --> 00:26:27,600 Jedným z nich je ukazovateľ na ďalší uzol. 627 00:26:27,600 --> 00:26:30,280 Iný musí byť niečo ako zaškrtávacie políčko 628 00:26:30,280 --> 00:26:33,770 povedať, že áno, je tu Slovo Daven, že tu končí, 629 00:26:33,770 --> 00:26:35,610 pretože nechceme, v okamihu, Dave. 630 00:26:35,610 --> 00:26:39,320 >> Aj keď Dave bude legitímne slovo, že to nie je v trie 631 00:26:39,320 --> 00:26:39,830 ešte. 632 00:26:39,830 --> 00:26:40,950 A D nie je ani slovo. 633 00:26:40,950 --> 00:26:42,770 A D-nie je slovo alebo meno. 634 00:26:42,770 --> 00:26:45,020 Takže začiarknutie označuje iba raz vás 635 00:26:45,020 --> 00:26:48,190 hit tento uzol predchádzajúca cesta znakov 636 00:26:48,190 --> 00:26:50,700 vlastne reťazec, ktorý ste vložili. 637 00:26:50,700 --> 00:26:53,660 Tak to je všetko bool tam robí pre nás. 638 00:26:53,660 --> 00:26:55,500 >> Akékoľvek ďalšie otázky týkajúce sa pokusov? 639 00:26:55,500 --> 00:26:56,215 Jo. 640 00:26:56,215 --> 00:26:58,035 >> Divákov: Čo je presah? 641 00:26:58,035 --> 00:26:59,945 Čo keď máte Dave a Daven? 642 00:26:59,945 --> 00:27:00,820 DAVID Malan: Perfect. 643 00:27:00,820 --> 00:27:02,580 Čo keď máte Dave a Daven? 644 00:27:02,580 --> 00:27:06,240 Pokiaľ teda vložíte, povedzme prezývku, pre David-- Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 To je vlastne super jednoduché. 647 00:27:08,700 --> 00:27:10,325 Takže sme len bude trvať štyri kroky. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-E. A čo mám robiť, až som narazila, že štvrtý uzol? 650 00:27:15,847 --> 00:27:16,680 Len tak pre kontrolu. 651 00:27:16,680 --> 00:27:18,000 Už sme dobré ísť. 652 00:27:18,000 --> 00:27:18,840 Hotovo. 653 00:27:18,840 --> 00:27:19,750 Štyri kroky. 654 00:27:19,750 --> 00:27:21,590 Konštantný čas asymptoticky. 655 00:27:21,590 --> 00:27:26,300 A teraz sme ukázali, že obaja Dave a Daven sú reťazce v štruktúre. 656 00:27:26,300 --> 00:27:27,710 Takže nie je problém. 657 00:27:27,710 --> 00:27:30,200 A všimnite si, ako prítomnosť z Daven to nezvládli 658 00:27:30,200 --> 00:27:34,750 mať viac času, alebo menej čas pre Dave a naopak. 659 00:27:34,750 --> 00:27:36,000 >> Takže čo iného môžeme teraz robiť? 660 00:27:36,000 --> 00:27:40,680 Použili sme túto metaforu pred zásobníkov predstavuje niečo. 661 00:27:40,680 --> 00:27:43,380 Ale ukazuje sa, že stĺpec podložiek je vlastne 662 00:27:43,380 --> 00:27:47,187 demonštratívny iného abstraktné údajov type-- vyššiu dátovú štruktúru úrovne 663 00:27:47,187 --> 00:27:49,770 že na konci dňa je len ako pole alebo spojovaceho zoznamu 664 00:27:49,770 --> 00:27:50,970 alebo niečo prozaickejšia. 665 00:27:50,970 --> 00:27:53,270 Ale je to oveľa zaujímavejšie koncepčné poňatie. 666 00:27:53,270 --> 00:27:56,440 Stack, ako sú tieto žľaby tu v Mather, 667 00:27:56,440 --> 00:27:58,750 sa všeobecne nazývajú len that-- stoh. 668 00:27:58,750 --> 00:28:02,540 >> A v tomto type dátovej štruktúry Máte dve operations-- 669 00:28:02,540 --> 00:28:05,880 máte jednu s názvom Push pre pridať niečo do zásobníka, 670 00:28:05,880 --> 00:28:08,320 ako dávať iný zásobník Späť na vrchol zásobníka. 671 00:28:08,320 --> 00:28:11,350 A potom pop, ktorý vás znamená vziať najvrchnejšiu zásobníka off. 672 00:28:11,350 --> 00:28:16,210 Ale to, čo je kľúčom k stack je, že to dostal túto kuriózne vlastnosť. 673 00:28:16,210 --> 00:28:19,560 Ako zamestnanci jedálne sú preskupiť zásobníky na ďalšie jedlo, 674 00:28:19,560 --> 00:28:21,380 čo sa bude pravda o tom, ako študenti 675 00:28:21,380 --> 00:28:22,856 interagujú s touto dátovou štruktúrou? 676 00:28:22,856 --> 00:28:24,480 Divákov: Chystajú sa pop jednorazové. 677 00:28:24,480 --> 00:28:26,550 DAVID Malan: Chystajú sa pop jednorazové, dúfajme, že na vrchol. 678 00:28:26,550 --> 00:28:28,910 V opačnom prípade je to len trochu hlúpy ísť celú cestu až na dno. 679 00:28:28,910 --> 00:28:29,070 Je to tak? 680 00:28:29,070 --> 00:28:31,620 Dátová štruktúra nie je v skutočnosti umožňuje uchopiť spodný zásobník aspoň 681 00:28:31,620 --> 00:28:32,520 ľahko. 682 00:28:32,520 --> 00:28:35,040 Takže tam je to zvedavý vlastnosť stohu 683 00:28:35,040 --> 00:28:39,730 že posledná položka je bude prvý von. 684 00:28:39,730 --> 00:28:43,400 A počítačoví odborníci hovoria tento LIFO-- posledný dnu, prvý von. 685 00:28:43,400 --> 00:28:45,540 A to v skutočnosti nemá mať zaujímavé aplikácie. 686 00:28:45,540 --> 00:28:50,090 To nie je nevyhnutne tak zrejmé, ako niektorí iní, ale môže skutočne byť užitočné, 687 00:28:50,090 --> 00:28:54,040 a môže skutočne byť vykonaná v niekoľkými rôznymi spôsobmi. 688 00:28:54,040 --> 00:28:58,550 >> Takže človek, a v skutočnosti, nech ma nie sa ponoriť do toho. 689 00:28:58,550 --> 00:28:59,860 Ideme na to miesto. 690 00:28:59,860 --> 00:29:03,700 Poďme sa pozrieť na ten, ktorý je takmer Rovnaký nápad, ale je to trochu spravodlivejší. 691 00:29:03,700 --> 00:29:04,200 Je to tak? 692 00:29:04,200 --> 00:29:07,560 Ak ste niektorý z týchto ventilátorov chlapčenské alebo dievčatá, ktoré naozaj rád Apple produkty 693 00:29:07,560 --> 00:29:10,130 a prebudil vo 3:00 sa zoradia v nejakom obchode 694 00:29:10,130 --> 00:29:14,150 získať najnovšie iPhone, budete mohol fronte takhle. 695 00:29:14,150 --> 00:29:15,800 >> Teraz fronta je veľmi zámerne menovaný. 696 00:29:15,800 --> 00:29:18,190 Je to čiara, pretože tam je niektoré spravodlivosť k nemu. 697 00:29:18,190 --> 00:29:18,690 Je to tak? 698 00:29:18,690 --> 00:29:21,690 Bolo by trochu nasáva, ak ste tam dostal najprv na Apple Store 699 00:29:21,690 --> 00:29:25,700 ale vy ste skutočne najspodnejšej zásobník, pretože zamestnanci Apple potom 700 00:29:25,700 --> 00:29:28,189 pop posledná osoba, ktorá vlastne dostal do vedenia. 701 00:29:28,189 --> 00:29:31,230 Tak komíny a frontu, aj keď funkčne sú druh na same-- 702 00:29:31,230 --> 00:29:33,105 je to práve táto kolekcia zdrojov, ktoré je 703 00:29:33,105 --> 00:29:36,210 tam bude rásť a shrink-- sa Táto spravodlivosť aspekt k tomu, 704 00:29:36,210 --> 00:29:39,634 aspoň v reálnom svete, kde tieto operácie cvičíte 705 00:29:39,634 --> 00:29:40,800 sú zásadne odlišné. 706 00:29:40,800 --> 00:29:43,360 Stack-- front rather-- je povedal, aby mal 707 00:29:43,360 --> 00:29:45,320 dve operácie: n frontu a d frontu. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Alebo ich môžete volať ľubovoľný počet vecí. 710 00:29:48,090 --> 00:29:50,770 Ale len chcete zachytiť Predstava, že človek je pridanie 711 00:29:50,770 --> 00:29:53,230 a jeden je nakoniec odpočítaním. 712 00:29:53,230 --> 00:29:58,840 >> Teraz pod pokrievku, ako stack a front by mohla byť vykonávaná ako na to? 713 00:29:58,840 --> 00:30:01,390 Nebudeme zachádzať do kódu to preto, že vyššia úroveň 714 00:30:01,390 --> 00:30:03,387 nápad je trochu viac zrejmé. 715 00:30:03,387 --> 00:30:04,470 Chcem povedať, čo ľudia robia? 716 00:30:04,470 --> 00:30:07,030 Ak som prvý človek na Apple Uložte a to je predné dvere, 717 00:30:07,030 --> 00:30:08,130 vieš, ja budem stáť tu. 718 00:30:08,130 --> 00:30:09,750 A ďalšie osoby bude tu stáť. 719 00:30:09,750 --> 00:30:11,500 A ďalšie osoby bude tu stáť. 720 00:30:11,500 --> 00:30:13,792 Takže to, čo dátová štruktúra je možné uplatniť na fronte? 721 00:30:13,792 --> 00:30:14,542 >> Divákov: front. 722 00:30:14,542 --> 00:30:15,667 DAVID Malan: No, front. 723 00:30:15,667 --> 00:30:16,390 Iste. 724 00:30:16,390 --> 00:30:16,920 Čo ešte? 725 00:30:16,920 --> 00:30:17,600 >> Divákov: spájať zoznam. 726 00:30:17,600 --> 00:30:18,990 >> DAVID Malan: súvisí zoznam, ktorý by mohol realizovať. 727 00:30:18,990 --> 00:30:22,500 A spájať zoznam je pekné, pretože potom môže rásť ľubovoľne dlho, na rozdiel 728 00:30:22,500 --> 00:30:24,880 sa mať nejaký pevný počet ľudí v obchode. 729 00:30:24,880 --> 00:30:27,030 Ale možno, že pevne stanovený počet miest je legitímne. 730 00:30:27,030 --> 00:30:30,350 Vzhľadom k tomu, ak majú len ako 20 iPhone prvý deň, možno 731 00:30:30,350 --> 00:30:33,930 oni len potrebujú rad veľkostí 20 predstavujú, že front, ktorá 732 00:30:33,930 --> 00:30:37,070 je len povedať teraz, akonáhle začneme hovoriť o týchto problémoch vyššej úrovni, 733 00:30:37,070 --> 00:30:38,890 môžete ju implementovať v mnohých rôznymi spôsobmi. 734 00:30:38,890 --> 00:30:42,030 A je to asi len tak byť kompromis v priestore a čase 735 00:30:42,030 --> 00:30:43,950 alebo len vo svojom vlastnom kóde zložitosti. 736 00:30:43,950 --> 00:30:45,380 >> Čo stohu? 737 00:30:45,380 --> 00:30:48,190 No, zásobník, sme videli príliš môže byť len tieto zásobníky. 738 00:30:48,190 --> 00:30:50,007 A tie by mohli realizovať toto pole. 739 00:30:50,007 --> 00:30:53,090 Ale v určitom okamihu, ak používate polia, čo sa bude diať na zásobníky 740 00:30:53,090 --> 00:30:54,173 sa snažíte dať dole? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Dobrá. 743 00:30:55,670 --> 00:30:57,490 Budeš len môcť ísť tak vysoko. 744 00:30:57,490 --> 00:31:00,156 A myslím, že v Mather, že sú skutočne zapustené v tomto otvore. 745 00:31:00,156 --> 00:31:01,950 Takže v skutočnosti, to je takmer ako Mather používa 746 00:31:01,950 --> 00:31:03,783 pole pevnej veľkosti, pretože môžete len 747 00:31:03,783 --> 00:31:08,302 zmestí toľko zásobníky v tomto otvore v steny dole pod kolená ľudí. 748 00:31:08,302 --> 00:31:10,010 A tak, aby mohla byť hovorí, že je pole, 749 00:31:10,010 --> 00:31:14,300 ale mohli by sme iste realizovať, že všeobecnejšie s prepojeného zoznamu. 750 00:31:14,300 --> 00:31:16,390 >> No, čo iné dátové štruktúry? 751 00:31:16,390 --> 00:31:18,760 Dovoľte mi, aby som vytiahnuť jeden iný vizuálny tu. 752 00:31:18,760 --> 00:31:24,710 Niečo ako, ako o tomto tu? 753 00:31:24,710 --> 00:31:28,920 Prečo by mohlo byť užitočné mať nie niečo tak nóbl ako trie, ktorá 754 00:31:28,920 --> 00:31:32,370 videli sme mali tieto veľmi široké uzly, z ktorých každý je v poli? 755 00:31:32,370 --> 00:31:35,740 Ale čo keď urobíme niečo viac jednoducho, ako starej školy rodokmeni, 756 00:31:35,740 --> 00:31:38,110 ktorých jednotlivé uzly tu práve ukladanie čísiel. 757 00:31:38,110 --> 00:31:42,180 Namiesto názvu alebo potomka práve ukladanie čísel, ako je tento. 758 00:31:42,180 --> 00:31:45,250 >> No, žargón používame v dátové štruktúry je obaja snažia 759 00:31:45,250 --> 00:31:49,510 a stromy, kde Trie, opäť, je len ten, ktorého uzly sú polia, 760 00:31:49,510 --> 00:31:51,680 je stále to, čo by mohlo používať od základnej škole 761 00:31:51,680 --> 00:31:53,860 keď ste sa rodina tree-- listy a koreň 762 00:31:53,860 --> 00:31:57,250 stromu a deti materská a ich súrodenci. 763 00:31:57,250 --> 00:32:03,670 A my by sme mohli realizovať strom, napríklad, ako jednoducho ako to. 764 00:32:03,670 --> 00:32:07,420 Strom, ak to ako uzol, jeden z Tieto kruhy, ktoré má číslo, 765 00:32:07,420 --> 00:32:09,947 že to nebude mať jeden ukazovateľ, ale dva. 766 00:32:09,947 --> 00:32:11,780 A akonáhle pridáte Druhý ukazovateľ, môžete 767 00:32:11,780 --> 00:32:13,905 teraz môžu skutočne urobiť trochu dvojrozmerného údajov 768 00:32:13,905 --> 00:32:14,780 štruktúry v pamäti. 769 00:32:14,780 --> 00:32:16,660 Rovnako ako dvojrozmerný poľa, môžete 770 00:32:16,660 --> 00:32:18,904 mať takú dvoch-dimenzionální spojové zoznamy, ale tie 771 00:32:18,904 --> 00:32:20,820 že nasledovať vzor tam, kde je žiadne cykly. 772 00:32:20,820 --> 00:32:24,487 Je to naozaj strom s jedným prarodič až sem a potom 773 00:32:24,487 --> 00:32:27,320 niektorí rodičia a deti a vnúčatá a pravnúčatá. 774 00:32:27,320 --> 00:32:28,370 a tak ďalej. 775 00:32:28,370 --> 00:32:32,390 >> Ale čo je naozaj pekné o tom taky, len preto, aby ťa podpichovať s trochou kódu, 776 00:32:32,390 --> 00:32:35,370 odvolanie rekurzia od chvíľu späť, pričom 777 00:32:35,370 --> 00:32:38,220 môžete napísať funkciu, ktorá volá sama seba. 778 00:32:38,220 --> 00:32:41,140 To je krásna príležitosť vykonávať niečo 779 00:32:41,140 --> 00:32:42,920 ako rekurzie, pretože to považujú. 780 00:32:42,920 --> 00:32:43,860 >> Jedná sa o strom. 781 00:32:43,860 --> 00:32:48,040 A bol som trochu análny s tým, ako Dal som celé čísla na ulici. 782 00:32:48,040 --> 00:32:51,020 Natoľko, že to má zvláštne name-- binárny vyhľadávací strom. 783 00:32:51,020 --> 00:32:53,460 Teraz sme počuli o binárny hľadať, ale môžete 784 00:32:53,460 --> 00:32:55,180 pospiatky z mena tá vec je? 785 00:32:55,180 --> 00:32:59,280 Čo je vzor, ​​ako som vložená celé čísla do tohto stromu? 786 00:32:59,280 --> 00:33:00,696 To nie je ľubovoľná. 787 00:33:00,696 --> 00:33:01,570 Tam je nejaký vzor. 788 00:33:01,570 --> 00:33:02,090 Jo. 789 00:33:02,090 --> 00:33:03,370 >> Divákov: menšie na ľavej strane. 790 00:33:03,370 --> 00:33:03,690 >> DAVID Malan: Jo. 791 00:33:03,690 --> 00:33:05,062 Menšie sú na ľavej strane. 792 00:33:05,062 --> 00:33:06,270 Tie väčšie sú na pravej strane. 793 00:33:06,270 --> 00:33:12,940 Tak, že pravdivé tvrdenie je rodič je väčší než jeho ľavej dieťa, 794 00:33:12,940 --> 00:33:14,850 ale menej než pravom dieťa. 795 00:33:14,850 --> 00:33:17,750 A to samo o sebe je ešte rekurzívne slovné definície 796 00:33:17,750 --> 00:33:20,500 pretože môžete použiť, že Rovnaká logika sa ku každému uzlu 797 00:33:20,500 --> 00:33:23,080 a to len dna out, referenčný prípad, ak vás 798 00:33:23,080 --> 00:33:25,740 bude, keď narazí jeden z listy, aby som tak povedal, 799 00:33:25,740 --> 00:33:28,580 kde má dovolenka žiadne deti ďalej. 800 00:33:28,580 --> 00:33:30,614 >> Teraz, ako môžete nájsť číslo 44? 801 00:33:30,614 --> 00:33:32,280 Tie by začať pri koreni a povedať, hm. 802 00:33:32,280 --> 00:33:35,690 55 nie je 44 Tak to ja chcem ísť právo alebo nechcem ísť doľava? 803 00:33:35,690 --> 00:33:37,190 No, samozrejme budete chcieť ísť doľava. 804 00:33:37,190 --> 00:33:40,060 A tak je to rovnako ako telefón Kniha príklad v binárnej vyhľadávania 805 00:33:40,060 --> 00:33:41,099 všeobecnejšie. 806 00:33:41,099 --> 00:33:43,390 Ale my sme jeho vykonávanie Teraz trochu viac dynamicky 807 00:33:43,390 --> 00:33:45,339 ako pole môže dovoliť. 808 00:33:45,339 --> 00:33:48,130 A v skutočnosti, ak sa chcete pozrieť na kód, na prvý pohľad iste. 809 00:33:48,130 --> 00:33:49,671 Vyzerá to, že veľa liniek. 810 00:33:49,671 --> 00:33:51,220 Ale je to krásne jednoduché. 811 00:33:51,220 --> 00:33:54,490 Ak chcete implementovať funkciu volal hľadanie, ktorého zmysel života 812 00:33:54,490 --> 00:33:57,290 je hľadať hodnotu ako je N, celé číslo, 813 00:33:57,290 --> 00:34:01,756 a ty si prešiel v jednom pointer-- ukazovateľ na uzol koreňov, 814 00:34:01,756 --> 00:34:04,380 skôr z toho stromu, z ktorého môžete pristupovať všetko ostatné, 815 00:34:04,380 --> 00:34:08,850 Všimnite si, ako priamočiaro môžete implementovať logiku. 816 00:34:08,850 --> 00:34:10,880 Ak je strom je null, samozrejme, že to tam nie je. 817 00:34:10,880 --> 00:34:11,880 Povedzme, vráti false. 818 00:34:11,880 --> 00:34:12,000 Je to tak? 819 00:34:12,000 --> 00:34:14,040 Ak to ruky nič, tam nič nie je. 820 00:34:14,040 --> 00:34:17,900 >> Inak, ak n je menšia než strom šípka n- teraz šípka n, 821 00:34:17,900 --> 00:34:20,670 spomínam sme zaviedli Super Krátko na druhý deň, 822 00:34:20,670 --> 00:34:25,100 a to len znamená, že de-referencie ukazovateľ a pozrite sa na polia s názvom n. 823 00:34:25,100 --> 00:34:27,690 Takže to znamená, tam a pozrite sa na polia s názvom n. 824 00:34:27,690 --> 00:34:33,810 Takže ak n, hodnota, ktorú ste daný, je menej ako hodnota v korunách stromov číslo, 825 00:34:33,810 --> 00:34:35,449 kam chcete ísť? 826 00:34:35,449 --> 00:34:36,389 Doľava. 827 00:34:36,389 --> 00:34:37,780 >> Takže si všimnúť rekurziu. 828 00:34:37,780 --> 00:34:39,860 Ja returning-- nie je pravda. 829 00:34:39,860 --> 00:34:40,989 Nie false. 830 00:34:40,989 --> 00:34:45,670 Vraciam sa bez ohľadu na odpoveď je z volanie seba, okolo 831 00:34:45,670 --> 00:34:50,100 opäť n, ktorá je nadbytočná, ale to, čo je teraz trochu inak? 832 00:34:50,100 --> 00:34:51,989 Ako mám robiť problém menšie? 833 00:34:51,989 --> 00:34:54,920 Som odovzdaním ako druhý Tvrdenie nie je koreň stromu, 834 00:34:54,920 --> 00:34:59,616 ale ľavá dieťa v tomto prípade. 835 00:34:59,616 --> 00:35:00,990 Takže som okolo v ľavom dieťaťa. 836 00:35:00,990 --> 00:35:04,720 >> Medzitým, ak n je väčšie ako uzol Som v súčasnosti pri pohľade na, 837 00:35:04,720 --> 00:35:06,690 Som hľadať na pravej strane. 838 00:35:06,690 --> 00:35:10,880 Inak, v prípade, že strom nie je null, a V prípade, že prvok nie je doľava 839 00:35:10,880 --> 00:35:13,240 a nie je to na pravej strane, čo je nádherne prípad? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Sme skutočne našli uzol v otázka, a tak sme sa vrátiť true. 842 00:35:18,440 --> 00:35:21,490 >> Tak sme práve poškriabaný povrch teraz niektoré z týchto dátových štruktúr. 843 00:35:21,490 --> 00:35:24,370 V problém nastaviť päť budete preskúmať tieto ešte ďalej, 844 00:35:24,370 --> 00:35:27,250 a budete mať váš návrh Voľba, ako ísť o to. 845 00:35:27,250 --> 00:35:30,250 Čo by som chcel na záver o je len 30 sekúnd teaser 846 00:35:30,250 --> 00:35:32,080 o tom, čo čaká budúci týždeň a mimo nej. 847 00:35:32,080 --> 00:35:35,390 >> Ako sme begin-- našťastie by ste mohli think-- náš prechod pomaly 848 00:35:35,390 --> 00:35:38,680 zo sveta C a nižšej detaily implementácie na úrovni, 849 00:35:38,680 --> 00:35:42,090 do sveta, v ktorom si môžeme pre samozrejmé, že niekto iný má konečne 850 00:35:42,090 --> 00:35:44,010 realizované tieto údaje štruktúry pre nás, 851 00:35:44,010 --> 00:35:47,570 a začneme chápať reálny svet prostredníctvom vykonávacích 852 00:35:47,570 --> 00:35:50,560 web-based programy a Webové stránky všeobecne 853 00:35:50,560 --> 00:35:52,910 a tiež veľmi bezpečnostné dôsledky, ktoré sme len 854 00:35:52,910 --> 00:35:54,850 začal poškriabať povrch. 855 00:35:54,850 --> 00:35:57,320 Tu je to, čo nás čaká v najbližších dňoch. 856 00:35:57,320 --> 00:36:00,480 >> [VIDEO PREHRÁVANIE] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -Je Prišiel so správou, s protokolom všetci jeho vlastné. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Prišiel na svet krutý firewally, routery, bezcitný 861 00:36:30,894 --> 00:36:33,368 a nebezpečenstvo ďaleko horšie ako smrť. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Je rýchly. 864 00:36:36,236 --> 00:36:37,980 On je silný. 865 00:36:37,980 --> 00:36:42,830 Je to TCP / IP, a on má svoju adresu. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Bojovníci siete." 868 00:36:48,074 --> 00:36:49,660 [END Videoprehrávanie] 869 00:36:49,660 --> 00:36:50,910 DAVID Malan: Už budúci týždeň. 870 00:36:50,910 --> 00:36:51,880 Uvidíme sa potom. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [VIDEO PREHRÁVANIE] 873 00:36:56,060 --> 00:36:59,240 -A Teraz, "hlboké myšlienky" od Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Vždy začína prednášky sa, "v poriadku." 876 00:37:05,820 --> 00:37:08,750 Prečo nie, "Tu je riešenie na tento týždeň problém set " 877 00:37:08,750 --> 00:37:12,180 alebo "Dávame všetky z vás?" 878 00:37:12,180 --> 00:37:13,380 [Smiech] 879 00:37:13,380 --> 00:37:15,530 [END Videoprehrávanie]