1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:05,120 [Prehrávanie hudby] 3 00:00:05,120 --> 00:00:12,026 4 00:00:12,026 --> 00:00:12,900 SPEAKER 1: V poriadku. 5 00:00:12,900 --> 00:00:14,600 Všetci vitajte späť do kategórie. 6 00:00:14,600 --> 00:00:18,660 Dúfam, že ste všetci úspešne späť z vášho testu 7 00:00:18,660 --> 00:00:19,510 z minulého týždňa. 8 00:00:19,510 --> 00:00:22,564 Viem, že je trochu blázon občas. 9 00:00:22,564 --> 00:00:25,230 Ako som hovoril predtým, ak ste v rámci štandardnej odchýlky, 10 00:00:25,230 --> 00:00:28,188 nemáte naozaj starať o to, a to najmä pre menej pohodlné úseku. 11 00:00:28,188 --> 00:00:30,230 To je o tom, kde by ste mali byť. 12 00:00:30,230 --> 00:00:32,850 >> Ak ste si skvele, potom úžasné. 13 00:00:32,850 --> 00:00:33,650 Sláva tebe. 14 00:00:33,650 --> 00:00:36,149 A ak máte pocit, že musíte trochu viac pomôcť, prosím 15 00:00:36,149 --> 00:00:38,140 neváhajte osloviť z niektorého z TFS. 16 00:00:38,140 --> 00:00:40,030 Všetci sme tu na pomoc. 17 00:00:40,030 --> 00:00:40,960 >> To je dôvod, prečo sme sa učiť. 18 00:00:40,960 --> 00:00:44,550 To je dôvod, prečo som tu každý pondelok pre vás chlapci a v kancelárii hodín vo štvrtok. 19 00:00:44,550 --> 00:00:48,130 Tak neváhajte a dajte mi vedieť, Ak máte obavy o ničom 20 00:00:48,130 --> 00:00:52,450 alebo v prípade, že je niečo v kvíze že by ste naozaj chceli riešiť. 21 00:00:52,450 --> 00:00:56,940 >> Takže agenda pre dnešok je všetko o dátových štruktúr. 22 00:00:56,940 --> 00:01:01,520 Niektoré z nich sú proste bude len aby sa vám zoznámil s týmito. 23 00:01:01,520 --> 00:01:04,870 Nesmiete nikdy realizovať je v tejto triede. 24 00:01:04,870 --> 00:01:08,690 Niektoré z nich si vyskúšate, ako pre pravopisu pset. 25 00:01:08,690 --> 00:01:11,380 >> Budete mať svoj výber medzi stoly mriežky a pokusov. 26 00:01:11,380 --> 00:01:13,680 Takže sme určite ísť cez tie. 27 00:01:13,680 --> 00:01:18,690 Bude to mať rozhodne viac druhov vysokej úrovni úseku dnes, aj keď, 28 00:01:18,690 --> 00:01:22,630 pretože existuje veľa z nich, a ak sme išli do podrobností implementácie 29 00:01:22,630 --> 00:01:26,490 na všetkých z nich, neboli by sme dokonca prejsť spojových zoznamov 30 00:01:26,490 --> 00:01:28,520 a možno trochu hash tabuľky. 31 00:01:28,520 --> 00:01:31,200 >> Takže majte so mnou. 32 00:01:31,200 --> 00:01:33,530 Nebudeme sa robí až kódovanie tentoraz. 33 00:01:33,530 --> 00:01:36,870 Ak máte nejaké otázky o tom alebo ak chcete vidieť, že realizovať 34 00:01:36,870 --> 00:01:39,260 alebo sa pokúsiť si to pre seba, Určite odporúčam 35 00:01:39,260 --> 00:01:44,250 bude study.cs50.net, ktoré má príklady všetkých z nich. 36 00:01:44,250 --> 00:01:46,400 To bude mať svoje powerpoints s poznámkami, ktoré sme 37 00:01:46,400 --> 00:01:50,860 majú tendenciu používať aj trochou programovania cvičenie, predovšetkým na veci, 38 00:01:50,860 --> 00:01:55,250 ako prepojených zoznamov a binárne stromy komíny a narážky. 39 00:01:55,250 --> 00:01:59,590 Tak trochu na vysokej úrovni, ktoré by mohlo byť pekné pre vás. 40 00:01:59,590 --> 00:02:01,320 >> Takže s tým, budeme začať. 41 00:02:01,320 --> 00:02:03,060 A tiež, yes-- kvízy. 42 00:02:03,060 --> 00:02:06,550 Myslím si, že väčšina z vás, ktorí sú v moja časť má svoje kvízy, 43 00:02:06,550 --> 00:02:12,060 ale každý, kto príde, alebo z nejakého dôvodu nie, sú tu v prednej časti. 44 00:02:12,060 --> 00:02:12,740 >> Tak spojových zoznamov. 45 00:02:12,740 --> 00:02:15,650 Viem, že tento druh ide zálohovať pred kvíz. 46 00:02:15,650 --> 00:02:17,940 To bolo pred týždňom že sme sa dozvedeli o tom. 47 00:02:17,940 --> 00:02:21,040 Ale v tomto prípade, budeme len ísť trochu viac do hĺbky. 48 00:02:21,040 --> 00:02:25,900 >> Tak prečo by sme mohli vybrať spájať zoznam cez pole? 49 00:02:25,900 --> 00:02:27,130 Čo ich odlišuje? 50 00:02:27,130 --> 00:02:27,630 Áno? 51 00:02:27,630 --> 00:02:30,464 >> Divákov: môžete tiež rozšíriť spojené Zoznam oproti Array pevnú veľkosť. 52 00:02:30,464 --> 00:02:31,171 SPEAKER 1: Správne. 53 00:02:31,171 --> 00:02:33,970 Pole má pevnú veľkosť vzhľadom k tomu, spájať zoznam má premennú veľkosť. 54 00:02:33,970 --> 00:02:36,970 Takže ak nevieme, ako moc chceme uložiť, 55 00:02:36,970 --> 00:02:39,880 spájať zoznam nám dáva veľký spôsob, ako to urobiť, pretože my môžeme len 56 00:02:39,880 --> 00:02:43,730 pridať na inom uzle a pridať na iný uzol a pridať na inom uzle. 57 00:02:43,730 --> 00:02:45,750 Ale to, čo by mohlo byť trade-off? 58 00:02:45,750 --> 00:02:49,521 Pamätá si niekto na trade-off medzi poľami a spojových zoznamov? 59 00:02:49,521 --> 00:02:50,020 Mmhmm? 60 00:02:50,020 --> 00:02:51,460 >> Divákov: Musíte prejsť celú cestu 61 00:02:51,460 --> 00:02:53,738 prostredníctvom prepojeného zoznamu nájsť prvok v zozname. 62 00:02:53,738 --> 00:02:55,570 V poli, môžete len nájsť prvok. 63 00:02:55,570 --> 00:02:56,278 >> SPEAKER 1: Správne. 64 00:02:56,278 --> 00:02:57,120 Tak s arrays-- 65 00:02:57,120 --> 00:02:58,500 >> Divákov: [nepočuteľné]. 66 00:02:58,500 --> 00:03:01,090 >> SPEAKER 1: S poľom, máme čo sa nazýva náhodný prístup. 67 00:03:01,090 --> 00:03:04,820 Znamená to, že ak chceme, aby to, čo je niekedy piaty bod zoznamu 68 00:03:04,820 --> 00:03:07,230 alebo piaty bod nášho pole, môžeme len chytiť ju. 69 00:03:07,230 --> 00:03:10,440 Ak je to spájať zoznam, máme iterovat, že jo? 70 00:03:10,440 --> 00:03:14,020 Tak prístup k prvku v pole je konštantný čas, 71 00:03:14,020 --> 00:03:19,530 zatiaľ čo v prepojenom zozname, že by s najväčšou pravdepodobnosťou bude lineárny čas, pretože možno 72 00:03:19,530 --> 00:03:21,370 naša prvkom je úplne na konci. 73 00:03:21,370 --> 00:03:23,446 Musíme prehľadať všetko. 74 00:03:23,446 --> 00:03:25,320 Takže sa všetkými týmito údajmi štruktúry pôjdeme 75 00:03:25,320 --> 00:03:29,330 sa stráviť trochu viac času na, Aké sú plusy a zápory. 76 00:03:29,330 --> 00:03:31,480 Keď by sme mohli chcieť použite jeden cez druhého? 77 00:03:31,480 --> 00:03:34,970 A to je druh väčšia vec odniesť. 78 00:03:34,970 --> 00:03:40,140 >> Takže máme tu definícia uzla. 79 00:03:40,140 --> 00:03:43,040 Je to ako jeden prvok v náš spájať zoznam, nie? 80 00:03:43,040 --> 00:03:46,180 Takže sme všetci oboznámení s našimi typedef structs, 81 00:03:46,180 --> 00:03:47,980 ktoré sme prešli v recenzii naposledy. 82 00:03:47,980 --> 00:03:53,180 Bolo to v podstate len vytvorením iný dátový typ, ktorý by sme mohli použiť. 83 00:03:53,180 --> 00:03:57,930 >> A v tomto prípade, je to nejaký uzol že bude mať nejaké číslo v. 84 00:03:57,930 --> 00:04:00,210 A čo potom je druhá časť tu? 85 00:04:00,210 --> 00:04:03,192 86 00:04:03,192 --> 00:04:05,677 Každý, kto? 87 00:04:05,677 --> 00:04:06,680 >> Divákov: [nepočuteľné]. 88 00:04:06,680 --> 00:04:07,020 >> SPEAKER 1: Jo. 89 00:04:07,020 --> 00:04:08,400 Je to ukazovateľ na ďalší uzol. 90 00:04:08,400 --> 00:04:12,610 Takže by to malo byť skutočne tu. 91 00:04:12,610 --> 00:04:18,790 To je ukazovateľ typu uzla na ďalšiu vec. 92 00:04:18,790 --> 00:04:22,410 A to je to, čo zahŕňa náš uzol. 93 00:04:22,410 --> 00:04:24,060 V pohode. 94 00:04:24,060 --> 00:04:29,390 >> Dobre, tak s hľadaním, ako sme boli len hovorím, do ruky, ak ste 95 00:04:29,390 --> 00:04:31,840 bude prehľadávať, Máte skutočne iterovat 96 00:04:31,840 --> 00:04:33,660 prostredníctvom prepojeného zoznamu. 97 00:04:33,660 --> 00:04:38,530 Takže ak sa pozeráme na počet 9 by sme začať na našej hlave 98 00:04:38,530 --> 00:04:41,520 a že nás upozorňuje na začiatku nášho prepojeného zoznamu, nie? 99 00:04:41,520 --> 00:04:44,600 A my hovoríme, OK, to robí uzol obsahovať číslo 9? 100 00:04:44,600 --> 00:04:45,690 Nie? 101 00:04:45,690 --> 00:04:47,500 >> V poriadku, prejdite na ďalší jeden. 102 00:04:47,500 --> 00:04:48,312 Nasledujte ho. 103 00:04:48,312 --> 00:04:49,520 Má obsahovať číslo 9? 104 00:04:49,520 --> 00:04:50,570 Nie. 105 00:04:50,570 --> 00:04:51,550 Sledujte ďalšie. 106 00:04:51,550 --> 00:04:55,490 >> Takže máme skutočne iterovat prostredníctvom našej prepojeného zoznamu. 107 00:04:55,490 --> 00:05:00,070 Nemôžeme jednoducho ísť priamo na miesto, kde 9. 108 00:05:00,070 --> 00:05:05,860 A ak vy vlastne chcete vidieť nejaký pseudo-kódu tam hore. 109 00:05:05,860 --> 00:05:10,420 Máme nejakú funkciu vyhľadávanie tu ktorý berie in-- čo to prijať? 110 00:05:10,420 --> 00:05:13,110 111 00:05:13,110 --> 00:05:14,320 Čo si myslíte? 112 00:05:14,320 --> 00:05:15,960 Tak ľahké. 113 00:05:15,960 --> 00:05:17,784 Čo je to? 114 00:05:17,784 --> 00:05:18,700 Divákov: [nepočuteľné]. 115 00:05:18,700 --> 00:05:20,366 SPEAKER 1: Počet hľadáme. 116 00:05:20,366 --> 00:05:20,980 Je to tak? 117 00:05:20,980 --> 00:05:22,875 A čo by to odpovedať? 118 00:05:22,875 --> 00:05:25,020 Je to ukazovateľ? 119 00:05:25,020 --> 00:05:26,000 >> Divákov: uzol. 120 00:05:26,000 --> 00:05:28,980 >> SPEAKER 1: uzol do zoznamu že sa pozeráme, je to tak? 121 00:05:28,980 --> 00:05:33,700 Takže máme niektoré uzly sú ukazovateľ tu. 122 00:05:33,700 --> 00:05:37,240 To je bod, ktorý sa bude vlastne iterovat našom zozname. 123 00:05:37,240 --> 00:05:39,630 Vydali sme sa rovná zoznam pretože to je to 124 00:05:39,630 --> 00:05:44,380 Nastavenie je rovné spustenie nášho prepojeného zoznamu. 125 00:05:44,380 --> 00:05:50,660 >> A aj keď to nie je NULL, zatiaľ čo stále máme veci v našom zozname, 126 00:05:50,660 --> 00:05:55,580 skontrolujte, či tento uzol má počet hľadáme. 127 00:05:55,580 --> 00:05:57,740 Return true. 128 00:05:57,740 --> 00:06:01,070 V opačnom prípade, aktualizovať, nie? 129 00:06:01,070 --> 00:06:04,870 >> Ak je NULL, my ukončiť naše while a return false 130 00:06:04,870 --> 00:06:08,340 pretože to znamená, že sme sa našli. 131 00:06:08,340 --> 00:06:11,048 Má každý si, ako 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ženie, budete majú tri rôzne spôsoby. 135 00:06:20,260 --> 00:06:25,250 Môžete predradiť, môžete pripojiť a môžete vložiť do roztriedený. 136 00:06:25,250 --> 00:06:28,215 V tomto prípade sme robiť predradeným. 137 00:06:28,215 --> 00:06:33,380 Vie niekto, ako tie, tri prípadov môže líšiť? 138 00:06:33,380 --> 00:06:36,920 >> Tak prepend znamená, že môžete dať je v prednej časti vášho zoznamu. 139 00:06:36,920 --> 00:06:39,770 Takže by znamenalo, že bez ohľadu na aké sú vaše uzol je, bez ohľadu na to, 140 00:06:39,770 --> 00:06:43,160 čo je hodnota, budete aby to tu vpredu, OK? 141 00:06:43,160 --> 00:06:45,160 Bude to prvý prvok v zozname. 142 00:06:45,160 --> 00:06:49,510 >> Ak ho pripojiť, bude to ísť na zadnej časti vášho zoznamu. 143 00:06:49,510 --> 00:06:54,010 A vložiť do najrôznejších znamená, že ste dám skutočne do miesta 144 00:06:54,010 --> 00:06:57,700 kde sa udržuje spájať zoznam zoradený. 145 00:06:57,700 --> 00:07:00,810 Opäť, ako použiť ty, a pri použití 146 00:07:00,810 --> 00:07:02,530 im bude líšiť v závislosti na vašom prípade. 147 00:07:02,530 --> 00:07:05,834 148 00:07:05,834 --> 00:07:07,750 Pokiaľ to nie je nutné, aby triediť, prepend inklinuje 149 00:07:07,750 --> 00:07:10,460 byť to, čo si väčšina ľudí použiť, pretože nemáte 150 00:07:10,460 --> 00:07:15,680 musí prejsť celý zoznam nájsť koniec pridajte ju, nie? 151 00:07:15,680 --> 00:07:17,720 Stačí si len držať ju priamo. 152 00:07:17,720 --> 00:07:21,930 >> Tak sme sa prejsť Vloženie 1 práve teraz. 153 00:07:21,930 --> 00:07:26,360 Takže jedna vec, ktorú budem Vrelo odporúčam na tomto pset 154 00:07:26,360 --> 00:07:29,820 je k tomu veci, ako vždy. 155 00:07:29,820 --> 00:07:35,130 Je veľmi dôležité, aby ste aktualizovať Vaše ukazovatele v správnom poradí 156 00:07:35,130 --> 00:07:38,620 pretože ak je aktualizovať trochu mimo prevádzku, 157 00:07:38,620 --> 00:07:42,210 budete skončiť strate časti zoznamu. 158 00:07:42,210 --> 00:07:49,680 >> Tak napríklad, v tomto prípade sme hovorí šéf len bod 1. 159 00:07:49,680 --> 00:07:56,070 Ak sa nám jednoducho, že bez uloženia tejto 1, 160 00:07:56,070 --> 00:07:58,570 nemáme poňatia, čo 1 by mali smerovať do súčasnosti 161 00:07:58,570 --> 00:08:02,490 preto, že sme stratili to, čo hlavy ukázal na. 162 00:08:02,490 --> 00:08:05,530 Takže jedna vec na zapamätanie keď robíte predradeným 163 00:08:05,530 --> 00:08:09,630 je zachrániť to, čo sa hlava ukazuje na prvý, 164 00:08:09,630 --> 00:08:15,210 potom priradiť, a potom aktualizovať čo váš nový uzol by mal ukazovať na. 165 00:08:15,210 --> 00:08:20,870 166 00:08:20,870 --> 00:08:22,560 V tomto prípade, je to jediný spôsob, ako to urobiť. 167 00:08:22,560 --> 00:08:25,440 >> Takže ak sme urobili to takto kde sme práve prevelený hlavu, 168 00:08:25,440 --> 00:08:30,320 strácame v podstate otázky Celý zoznam, jo? 169 00:08:30,320 --> 00:08:38,000 Jeden spôsob, ako to urobiť, je mať 1 bod ďalší, a potom si hlavu bod 1. 170 00:08:38,000 --> 00:08:42,650 Alebo si môžete urobiť niečo ako dočasné uskladnenie, čo som hovoril o. 171 00:08:42,650 --> 00:08:45,670 >> Ale priradenie vlastné meno ukazovatele v správnom poradí 172 00:08:45,670 --> 00:08:48,750 bude veľmi, veľmi dôležité, aby tento pset. 173 00:08:48,750 --> 00:08:53,140 V opačnom prípade budete mať hash tabuľky alebo pokus, ktorý je len bude 174 00:08:53,140 --> 00:08:56,014 len časť slova, ktoré ste chcú, a potom you're-- mmhmm? 175 00:08:56,014 --> 00:08:58,930 Divákov: Aký bol dočasný skladovanie vec, ktorú hovorili? 176 00:08:58,930 --> 00:09:00,305 SPEAKER 1: dočasné uskladnenie. 177 00:09:00,305 --> 00:09:02,760 Takže v podstate ďalšie spôsob, ako by to mohlo robiť 178 00:09:02,760 --> 00:09:07,650 je uložiť hlavu niečoho, ako je uložiť mu dočasné premenné. 179 00:09:07,650 --> 00:09:11,250 Priradiť ju na hodnotu 1 a aktualizovať 1 bod 180 00:09:11,250 --> 00:09:13,830 na čo hlava používa poukázať na. 181 00:09:13,830 --> 00:09:16,920 Týmto spôsobom je samozrejme viac elegantný, pretože vás 182 00:09:16,920 --> 00:09:20,770 Nemusíte dočasnú hodnotu, ale len ponúka iný spôsob, ako to urobiť. 183 00:09:20,770 --> 00:09:23,999 184 00:09:23,999 --> 00:09:25,790 A my vlastne majú nejaký kód na to. 185 00:09:25,790 --> 00:09:28,080 Takže pre spájať zoznam, sme skutočne nejaký 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 prvá vec, ktorú musíte vytvoriť nový uzol, samozrejme, 189 00:09:38,820 --> 00:09:40,790 a skontrolujte, či NULL. 190 00:09:40,790 --> 00:09:43,250 Vždy dobré. 191 00:09:43,250 --> 00:09:47,840 A potom je treba priradiť hodnoty. 192 00:09:47,840 --> 00:09:51,260 Vždy, keď vytvoríte nový uzol, vás Neviem, čo to ukazuje na ďalší, 193 00:09:51,260 --> 00:09:54,560 takže chcete inicializovať na hodnotu NULL. 194 00:09:54,560 --> 00:09:58,760 Ak to skončí ukázal na niečo, čo iného, ​​dostane pridelený a je to v poriadku. 195 00:09:58,760 --> 00:10:00,740 Ak je to prvá vec, v zozname, je potrebné 196 00:10:00,740 --> 00:10:04,270 poukázať na NULL, pretože to je koniec zoznamu. 197 00:10:04,270 --> 00:10:12,410 >> Tak to vložiť, vidíme tu sa priradí ďalšiu hodnotu našej uzla 198 00:10:12,410 --> 00:10:17,380 byť čo hlava, čo je to, čo sme tu mali. 199 00:10:17,380 --> 00:10:19,930 To je to, čo sme práve urobili. 200 00:10:19,930 --> 00:10:25,820 A potom sme priradenie hlavy až k bodu nášho nového uzla, pretože nezabudnite, 201 00:10:25,820 --> 00:10:31,090 Nová je nejaký ukazovateľ na uzol, a to je presne to, čo hlava. 202 00:10:31,090 --> 00:10:34,370 To je presne dôvod, prečo sme túto šípku prístupový. 203 00:10:34,370 --> 00:10:37,030 204 00:10:37,030 --> 00:10:37,530 V pohode? 205 00:10:37,530 --> 00:10:38,130 Mmhmm? 206 00:10:38,130 --> 00:10:41,100 >> Divákov: Musíme inicializovať novú Ďalšie NULL ako prvý, 207 00:10:41,100 --> 00:10:44,240 alebo môžeme len inicializovať na hlavu? 208 00:10:44,240 --> 00:10:48,210 >> SPEAKER 1: New ďalší musí byť NULL začať 209 00:10:48,210 --> 00:10:53,760 pretože neviete, kde to bude. 210 00:10:53,760 --> 00:10:56,100 Aj tento druh je rovnako ako paradigma. 211 00:10:56,100 --> 00:10:59,900 Môžete nastaviť ju na hodnotu NULL, len aby Uistite sa, že všetky vaše základne sú pokryté 212 00:10:59,900 --> 00:11:04,070 ako tak urobíte, že akékoľvek preradenie ste vždy zaručené, že to bude 213 00:11:04,070 --> 00:11:08,880 ukazovať na konkrétnu hodnotu proti ako hodnotu odpadky. 214 00:11:08,880 --> 00:11:12,210 Vzhľadom k tomu, jo, priradíme nové ďalšie automaticky, 215 00:11:12,210 --> 00:11:15,420 ale je to viac, rovnako ako dobrej praxe k inicializácii 216 00:11:15,420 --> 00:11:19,270 týmto spôsobom a potom priradiť. 217 00:11:19,270 --> 00:11:23,420 >> OK, tak dvojnásobne spojových zoznamov teraz. 218 00:11:23,420 --> 00:11:24,601 Čo si myslíme? 219 00:11:24,601 --> 00:11:26,350 To, čo je s dvojnásobne spojené zoznamy? 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 zoznamov, môžeme pohybovať len v jednom smere, nie? 222 00:11:34,300 --> 00:11:35,270 Máme len ďalej. 223 00:11:35,270 --> 00:11:36,760 Môžeme ísť len dopredu. 224 00:11:36,760 --> 00:11:40,300 >> S dvojnásobne spájať zoznam, môžeme tiež presunúť späť. 225 00:11:40,300 --> 00:11:44,810 Takže máme nielen Číslo, ktoré chceme uložiť, 226 00:11:44,810 --> 00:11:50,110 máme tam, kde poukazuje na ďalšie a tam, kde sme práve prišli. 227 00:11:50,110 --> 00:11:52,865 Takže to umožňuje niektoré lepšie priechod. 228 00:11:52,865 --> 00:11:56,620 229 00:11:56,620 --> 00:12:01,240 >> Tak dvojnásobne spojené uzly, veľmi podobné, nie? 230 00:12:01,240 --> 00:12:05,000 Jediným rozdielom je teraz majú ďalšie a predchádzajúce. 231 00:12:05,000 --> 00:12:06,235 To je jediný rozdiel. 232 00:12:06,235 --> 00:12:09,570 233 00:12:09,570 --> 00:12:14,790 >> Takže ak by sme mali predradiť alebo append-- sme nemajú žiadny kód pre tento up here-- 234 00:12:14,790 --> 00:12:17,830 ale ak ste boli, aby sa pokúsila vložte ju na dôležitú vec 235 00:12:17,830 --> 00:12:19,980 je potrebné, aby že ste priradenie 236 00:12:19,980 --> 00:12:23,360 ako vaše predchádzajúce a vaše ďalší ukazovateľ správne. 237 00:12:23,360 --> 00:12:29,010 Takže v tomto prípade by ste nielen inicializovať ďalšie, 238 00:12:29,010 --> 00:12:31,820 inicializáciu predchádzajúce. 239 00:12:31,820 --> 00:12:36,960 Ak sme v čele zoznamu sme by hlava rovná novej nielen, 240 00:12:36,960 --> 00:12:41,750 ale náš nový predchádzajúcej mal poukazujú na hlavu, nie? 241 00:12:41,750 --> 00:12:43,380 >> To je jediný rozdiel. 242 00:12:43,380 --> 00:12:47,200 A ak budete chcieť viac praxe s je s spojových zoznamov, s vložením, 243 00:12:47,200 --> 00:12:49,900 s mazaním, s vložkou do triedeného zoznamu 244 00:12:49,900 --> 00:12:52,670 prosím, pozrite sa study.cs50.net. 245 00:12:52,670 --> 00:12:54,870 Je tu veľa skvelých cvičení. 246 00:12:54,870 --> 00:12:55,870 Vrelo odporúčam je. 247 00:12:55,870 --> 00:12:59,210 Prial by som si, aby sme mali čas ísť cez ne ale je tu veľa dátových štruktúr 248 00:12:59,210 --> 00:13:01,530 prejsť. 249 00:13:01,530 --> 00:13:02,650 >> OK, tak hash tabuľky. 250 00:13:02,650 --> 00:13:07,070 Toto je pravdepodobne najviac užitočné bit pre pset 251 00:13:07,070 --> 00:13:11,090 tu, pretože budete mať realizáciu jedného z nich, alebo skúsiť. 252 00:13:11,090 --> 00:13:12,200 Moc sa mi páči hash tabuľky. 253 00:13:12,200 --> 00:13:13,110 Sú to celkom v pohode. 254 00:13:13,110 --> 00:13:17,080 >> Takže v podstate to, čo sa stane, je hash tabuľka 255 00:13:17,080 --> 00:13:22,050 je, keď naozaj potrebujete rýchle vkladanie, mazanie a vyhľadávanie. 256 00:13:22,050 --> 00:13:25,010 To sú veci, ktoré sme priorít v hash tabuľke. 257 00:13:25,010 --> 00:13:29,500 Môžu sa dostať docela veľký, ale ako uvidíme sa pokusoch, 258 00:13:29,500 --> 00:13:33,040 tam sú veci, ktoré sú oveľa väčšie. 259 00:13:33,040 --> 00:13:38,330 >> Ale v podstate, všetky hash Tabuľka je hašovacej funkcie 260 00:13:38,330 --> 00:13:47,215 že vám povie, ktoré vedro, aby každý vašich dát, každý z vašich prvkov. 261 00:13:47,215 --> 00:13:51,140 Jednoduchý spôsob, ako myslieť na hash tabuľky je, že je to len vedierka vecí, 262 00:13:51,140 --> 00:13:51,770 že jo? 263 00:13:51,770 --> 00:13:59,720 Takže keď sa triedenie vecí podľa rovnako ako prvé písmeno svojho mena, 264 00:13:59,720 --> 00:14:01,820 to je niečo ako hash tabuľky. 265 00:14:01,820 --> 00:14:06,180 >> Takže vy, keby som skupiny je do skupín, kto začína meno 266 00:14:06,180 --> 00:14:11,670 sa tu, alebo ten, kto má narodeniny v januári, februári, marci, 267 00:14:11,670 --> 00:14:15,220 čo, že je účinne vytvorenie hash tabuľky. 268 00:14:15,220 --> 00:14:18,120 Je to len vytváranie vedierka, že môžete triediť elementy do 269 00:14:18,120 --> 00:14:19,520 takže si môžete nájsť je jednoduchšie. 270 00:14:19,520 --> 00:14:22,300 Takže týmto spôsobom, keď som služieb nájsť jeden z vás, 271 00:14:22,300 --> 00:14:24,680 Nemám na vyhľadávanie cez každého z vašich mien. 272 00:14:24,680 --> 00:14:29,490 Môžem byť rád, oh, ja viem, že Danielle má narodeniny in-- 273 00:14:29,490 --> 00:14:30,240 Divákov: --April. 274 00:14:30,240 --> 00:14:30,948 Reproduktor 1: apríl. 275 00:14:30,948 --> 00:14:33,120 Tak som sa pozrieť do môjho apríl vedro, a s trochou šťastia 276 00:14:33,120 --> 00:14:38,270 že bude iba jeden tam a môj čas bol konštantný v tom zmysle, 277 00:14:38,270 --> 00:14:41,230 vzhľadom k tomu, keď som sa pozrieť cez veľa ľudí, 278 00:14:41,230 --> 00:14:43,090 že to bude trvať oveľa dlhšie. 279 00:14:43,090 --> 00:14:45,830 Takže hash tabuľky sú naozaj len lopaty. 280 00:14:45,830 --> 00:14:48,630 Jednoduchý spôsob, ako si o nich myslíte. 281 00:14:48,630 --> 00:14:52,930 >> Takže veľmi dôležitá vec, o hash tabuľka je hašovacej funkcie. 282 00:14:52,930 --> 00:14:58,140 Takže veci, ktoré som práve hovoril, ako vaše prvé písmeno vášho mena 283 00:14:58,140 --> 00:15:01,450 alebo vaše narodeniny mesiac sú to myšlienky, ktoré 284 00:15:01,450 --> 00:15:03,070 Naozaj koreláciu s haš funkcie. 285 00:15:03,070 --> 00:15:08,900 Je to len spôsob, ako rozhodnúť, ktoré vedro Si element ide do, OK? 286 00:15:08,900 --> 00:15:14,850 Takže pre tento pset, môžete sa pozrieť na skoro žiadne funkcie hash chcete. 287 00:15:14,850 --> 00:15:16,030 >> Nemusí to byť vaše vlastné. 288 00:15:16,030 --> 00:15:21,140 Tam sú niektoré z nich naozaj cool out tam, že robiť všetky druhy bláznivé matematiky. 289 00:15:21,140 --> 00:15:25,170 A ak chcete, aby sa vaše Kontrola pravopisu super rýchly, 290 00:15:25,170 --> 00:15:27,620 Ja by som určite pozrite sa do jednej z nich. 291 00:15:27,620 --> 00:15:32,390 >> Ale sú tu aj jednoduchých, ako je výpočtovo 292 00:15:32,390 --> 00:15:39,010 súčet slov, ako je každé písmeno má číslo. 293 00:15:39,010 --> 00:15:39,940 Vypočítajte súčet. 294 00:15:39,940 --> 00:15:42,230 Ktorý určuje vedro. 295 00:15:42,230 --> 00:15:45,430 Majú tiež tie jednoduché, že sú rovnako ako všetky je tu, 296 00:15:45,430 --> 00:15:47,050 všetky B je tu. 297 00:15:47,050 --> 00:15:48,920 Každý jeden z nich. 298 00:15:48,920 --> 00:15:55,770 >> V podstate je to len vám povie, ktoré index poľa Váš element by mal ísť do. 299 00:15:55,770 --> 00:15:58,690 Len rozhodovanie o bucket-- je to všetko funkcia hash. 300 00:15:58,690 --> 00:16:04,180 Takže tu máme príklad, ktorý je len prvé písmeno reťazca 301 00:16:04,180 --> 00:16:05,900 že som práve hovoril. 302 00:16:05,900 --> 00:16:11,900 >> Takže máte nejaké hash, ktorý je práve prvé písmeno vášho reťazca mínus, 303 00:16:11,900 --> 00:16:16,090 ktorá vám dá niektoré číslo medzi 0 a 25. 304 00:16:16,090 --> 00:16:20,790 A to, čo chcete urobiť, je uistite sa, že sa jedná 305 00:16:20,790 --> 00:16:24,110 veľkosť vášho hash table-- koľko vedierka sú. 306 00:16:24,110 --> 00:16:25,860 S mnohými z nich hashovacie funkcie, sú 307 00:16:25,860 --> 00:16:31,630 bude vracať hodnoty, ktoré by mohli je oveľa väčší ako počet segmentov 308 00:16:31,630 --> 00:16:33,610 že ste skutočne v hash tabuľke, 309 00:16:33,610 --> 00:16:37,240 preto je potrebné, aby Uistite sa, a mod tí. 310 00:16:37,240 --> 00:16:42,190 V opačnom prípade to bude hovoriť, oh, mal by byť v vedre 5000 311 00:16:42,190 --> 00:16:46,040 ale máte len 30 vedierka vo vašom hash tabuľky. 312 00:16:46,040 --> 00:16:49,360 A samozrejme, všetci vieme, že je to bude mať za následok v niektorých šialených chýb. 313 00:16:49,360 --> 00:16:52,870 Takže sa uistite, mod od Veľkosť vášho hash tabuľky. 314 00:16:52,870 --> 00:16:58,430 315 00:16:58,430 --> 00:16:58,930 V pohode. 316 00:16:58,930 --> 00:17:00,506 Tak kolízií. 317 00:17:00,506 --> 00:17:02,620 Je každý dobrý tak ďaleko? 318 00:17:02,620 --> 00:17:03,120 Mmhmm? 319 00:17:03,120 --> 00:17:05,900 >> Divákov: Prečo by to vrátiť sa tak masívne hodnotu? 320 00:17:05,900 --> 00:17:09,210 >> SPEAKER 1: V závislosti na algoritme že hash funkcia využíva. 321 00:17:09,210 --> 00:17:12,270 Niektoré z nich budú robiť blázon násobenie. 322 00:17:12,270 --> 00:17:16,270 A to je všetko, ako dostať rovnomerné rozdelenie, 323 00:17:16,270 --> 00:17:18,490 tak to robia niektoré naozaj bláznivé veci, niekedy. 324 00:17:18,490 --> 00:17:20,960 To je všetko. 325 00:17:20,960 --> 00:17:22,140 Ešte niečo? 326 00:17:22,140 --> 00:17:22,829 OK. 327 00:17:22,829 --> 00:17:24,480 >> Tak kolízií. 328 00:17:24,480 --> 00:17:29,270 V podstate, ako som už povedal, v najlepšom prípade, 329 00:17:29,270 --> 00:17:32,040 akýkoľvek vedro sa pozerám do je bude mať jednu vec, 330 00:17:32,040 --> 00:17:34,160 takže nemám pozerať na všetky, že jo? 331 00:17:34,160 --> 00:17:37,040 Ja viem, že buď tam, alebo je to nie, a to je to, čo naozaj chceme. 332 00:17:37,040 --> 00:17:43,960 Ale ak máme desiatky tisíc dátových bodov a menej než tento počet 333 00:17:43,960 --> 00:17:48,700 lopát, budeme mať kolízie, kde nakoniec niečo 334 00:17:48,700 --> 00:17:54,210 bude musieť skončiť v vedierko, ktorý už má prvok. 335 00:17:54,210 --> 00:17:57,390 >> Takže otázka je, čo budeme robiť v tomto prípade? 336 00:17:57,390 --> 00:17:58,480 Čo budeme robiť? 337 00:17:58,480 --> 00:17:59,300 Už sme tam niečo mať? 338 00:17:59,300 --> 00:18:00,060 Máme len vyhodiť? 339 00:18:00,060 --> 00:18:00,700 >> Nie. 340 00:18:00,700 --> 00:18:01,980 Musíme mať na oboch z nich. 341 00:18:01,980 --> 00:18:06,400 Tak tak, že sme zvyčajne to urobiť je to, čo? 342 00:18:06,400 --> 00:18:08,400 Čo je dátová štruktúra sme práve hovorili? 343 00:18:08,400 --> 00:18:09,316 Divákov: spájať zoznam. 344 00:18:09,316 --> 00:18:10,500 SPEAKER 1: spájať zoznam. 345 00:18:10,500 --> 00:18:16,640 Takže teraz, namiesto toho, každá z nich vedierka len mať jeden prvok, 346 00:18:16,640 --> 00:18:24,020 to bude obsahovať prepojený zoznam prvky, ktoré boli zatriedená do neho. 347 00:18:24,020 --> 00:18:27,588 OK, to každý druh si túto myšlienku? 348 00:18:27,588 --> 00:18:30,546 Pretože sme nemohli mať pole pretože nevieme, ako veľa vecí, 349 00:18:30,546 --> 00:18:31,730 sa bude tam. 350 00:18:31,730 --> 00:18:36,540 Spájať zoznam nám umožňuje máme len presný počet, ktorý 351 00:18:36,540 --> 00:18:38,465 sú zatriedená do tohto vedra, nie? 352 00:18:38,465 --> 00:18:42,260 353 00:18:42,260 --> 00:18:50,500 >> Takže lineárne sondovania je v podstate to idea-- 354 00:18:50,500 --> 00:18:52,300 to je jeden spôsob, ako sa vysporiadať s bočnom náraze. 355 00:18:52,300 --> 00:18:58,010 Čo môžete urobiť, je, ak v tomto prípad, bobuľové bola zatriedená do 1 356 00:18:58,010 --> 00:19:01,130 a už máme niečo, čo tam jednoducho 357 00:19:01,130 --> 00:19:04,840 ďalej, kým nájdete na prázdnu pozíciu. 358 00:19:04,840 --> 00:19:06,370 To je jediný spôsob, ako s ňou zaobchádzať. 359 00:19:06,370 --> 00:19:09,020 Druhý spôsob, ako zvládnuť je to s tým, čo sme práve 360 00:19:09,020 --> 00:19:12,280 called-- spojené zoznam sa nazýva zreťazenie. 361 00:19:12,280 --> 00:19:20,510 >> Takže táto myšlienka funguje, ak vaše hash tabuľky si myslíte 362 00:19:20,510 --> 00:19:24,150 je oveľa väčšia, než Vaše údaje nastaviť alebo ak vás 363 00:19:24,150 --> 00:19:28,870 skúsiť a minimalizovať reťazenie kým je to nevyhnutne potrebné. 364 00:19:28,870 --> 00:19:34,050 Takže jedna vec je lineárny sondovania samozrejme znamená, 365 00:19:34,050 --> 00:19:37,290 že vaše hash funkcie nie je tak užitočný 366 00:19:37,290 --> 00:19:42,200 pretože budete skončiť s použitím vaše hash funkcie, dostať do bodu, 367 00:19:42,200 --> 00:19:46,400 ste LINEAR sondy až do nejaké miesto, ktoré je k dispozícii. 368 00:19:46,400 --> 00:19:49,670 Ale teraz, samozrejme, čokoľvek iný, že skončí tam, 369 00:19:49,670 --> 00:19:52,050 budete musieť hľadať ešte ďalej. 370 00:19:52,050 --> 00:19:55,650 >> A je tu oveľa viac Hľadanie náklady, ktoré 371 00:19:55,650 --> 00:19:59,820 ide do zadania prvok v hash tabuľke, nie? 372 00:19:59,820 --> 00:20:05,640 A teraz, keď idete a pokúsiť sa nájsť berry znova, budete to hash, 373 00:20:05,640 --> 00:20:07,742 a to bude hovoriť, oh, pozrite sa do vedra 1, 374 00:20:07,742 --> 00:20:09,700 a to nebude v vedre 1, takže ste 375 00:20:09,700 --> 00:20:11,970 bude musieť prejsť cez zvyšok z nich. 376 00:20:11,970 --> 00:20:17,720 Tak to je niekedy užitočná, ale vo väčšine prípadov, 377 00:20:17,720 --> 00:20:22,660 budeme hovoriť, že reťazenie je to, čo chcete robiť. 378 00:20:22,660 --> 00:20:25,520 >> Tak sme o tom hovorili skôr. 379 00:20:25,520 --> 00:20:27,812 Dostal som kúsok pred seba. 380 00:20:27,812 --> 00:20:33,560 Ale reťazenie je v podstate, že každý vedierko v hash tabuľke 381 00:20:33,560 --> 00:20:36,120 je len spájať zoznam. 382 00:20:36,120 --> 00:20:39,660 >> Takže ďalší spôsob, alebo viac technických spôsobom, myslieť na hash tabuľky 383 00:20:39,660 --> 00:20:44,490 je to, že je to len pole spojových zoznamov, ktoré 384 00:20:44,490 --> 00:20:49,330 keď ste písanie slovník a vy sa snažíte načítať, 385 00:20:49,330 --> 00:20:52,070 myslieť na to, ako pole spojových zoznamov 386 00:20:52,070 --> 00:20:54,390 bude to oveľa jednoduchšie pre vás inicializovať. 387 00:20:54,390 --> 00:20:57,680 >> Divákov: Tak hash tabuľka má vopred určenú veľkosť, 388 00:20:57,680 --> 00:20:58,980 ako [nepočuteľné] lopát? 389 00:20:58,980 --> 00:20:59,220 >> SPEAKER 1: Správne. 390 00:20:59,220 --> 00:21:01,655 Tak to má stanovený počet vedierka, že ste determine-- 391 00:21:01,655 --> 00:21:03,530 ktoré ste chlapci mali pokojne hrať. 392 00:21:03,530 --> 00:21:05,269 To môže byť docela v pohode aby videli, čo sa stane, 393 00:21:05,269 --> 00:21:06,810 ako si zmeniť počet segmentov. 394 00:21:06,810 --> 00:21:09,410 395 00:21:09,410 --> 00:21:11,510 Ale jo, to má nastaviť počet segmentov. 396 00:21:11,510 --> 00:21:15,360 Čo umožňuje, aby sa zmestili ako mnoho prvkov, ako budete potrebovať 397 00:21:15,360 --> 00:21:19,350 je oddelený reťazenie, kde vás spojili zoznamy v každom segmente. 398 00:21:19,350 --> 00:21:22,850 To znamená, že vaše hash tabuľky bude presne veľkosť 399 00:21:22,850 --> 00:21:25,440 že ju musí byť, nie? 400 00:21:25,440 --> 00:21:27,358 To je celý zmysel spojových zoznamov. 401 00:21:27,358 --> 00:21:30,850 402 00:21:30,850 --> 00:21:32,480 V pohode. 403 00:21:32,480 --> 00:21:38,780 >> Takže tam všetci v poriadku? 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 Čo sa stalo? 407 00:21:41,860 --> 00:21:42,960 Naozaj teraz. 408 00:21:42,960 --> 00:21:45,250 Hádajte, niekto ma zabíja. 409 00:21:45,250 --> 00:21:52,060 >> OK budeme ísť do pokusov, ktoré sú trochu blázon. 410 00:21:52,060 --> 00:21:53,140 Mám rád hash tabuľky. 411 00:21:53,140 --> 00:21:54,460 Myslím, že sú naozaj cool. 412 00:21:54,460 --> 00:21:56,710 Pokusy sú v pohode, taky. 413 00:21:56,710 --> 00:21:59,590 >> Takže má niekto spomenúť, čo to skúsiť je? 414 00:21:59,590 --> 00:22:01,740 Mali ste prešli stručne v prednáške? 415 00:22:01,740 --> 00:22:04,570 416 00:22:04,570 --> 00:22:06,377 Spomínate si druh, ako to funguje? 417 00:22:06,377 --> 00:22:08,460 Divákov: Len som kývol že sme sa ísť cez neho. 418 00:22:08,460 --> 00:22:09,626 SPEAKER 1: Nemáme ísť cez neho. 419 00:22:09,626 --> 00:22:13,100 OK, sme naozaj ísť nad ňou je teraz to, čo hovoríme. 420 00:22:13,100 --> 00:22:14,860 >> Divákov: To je pre vyhľadá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ískavanie strom. 423 00:22:16,196 --> 00:22:16,960 Úžasné. 424 00:22:16,960 --> 00:22:23,610 Takže jedna vec je si všimnúť je, že sme sú pri pohľade na jednotlivé znaky 425 00:22:23,610 --> 00:22:24,480 tu, že jo? 426 00:22:24,480 --> 00:22:29,710 >> Takže pred našou hash funkcií, sme sa pozerali na slová ako celku, 427 00:22:29,710 --> 00:22:32,270 a teraz sa pozeráme viac na znaky, nie? 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 podstate try-- spôsob, ako myslieť o tom, že každý stupeň je tu 430 00:22:47,840 --> 00:22:49,000 je rad písmen. 431 00:22:49,000 --> 00:22:53,310 432 00:22:53,310 --> 00:22:55,790 Takže toto je váš koreňový uzol tu, že jo? 433 00:22:55,790 --> 00:23:01,980 To má všetky znaky abeceda na začiatku každého slova. 434 00:23:01,980 --> 00:23:06,480 >> A to, čo chcete urobiť, je povedzme, OK, máme nejaké M slovo. 435 00:23:06,480 --> 00:23:10,590 Ideme sa pozrieť na Maxwell, tak ideme do M. a M bodov na celý 436 00:23:10,590 --> 00:23:14,800 ďalšie pole, kde každý slovo, ak tam 437 00:23:14,800 --> 00:23:17,044 je slovo, ktoré má ako druhé písmeno, 438 00:23:17,044 --> 00:23:19,460 ako dlho ako tam je to slovo, ktoré má B ako druhé písmeno, 439 00:23:19,460 --> 00:23:24,630 bude mať ukazovateľ bude nejaké ďalšie pole. 440 00:23:24,630 --> 00:23:29,290 >> Je tu asi nie je slovo, ktoré MP niečo, 441 00:23:29,290 --> 00:23:32,980 takže v polohe P v tejto polia, bolo by to jednoducho byť NULL. 442 00:23:32,980 --> 00:23:38,840 To by povedal, OK, nie je slovo ktorý M nasledované P, OK? 443 00:23:38,840 --> 00:23:43,100 Takže ak si myslíme, že o tom, každý jeden z týchto menších vecí 444 00:23:43,100 --> 00:23:47,990 je v skutočnosti jedna z nich veľké pole od A po Z. 445 00:23:47,990 --> 00:23:55,064 Takže to, čo by mohlo byť jednou z vecí, že je tak trochu navrátení skúsiť? 446 00:23:55,064 --> 00:23:56,500 >> Divákov: veľa pamäte. 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 blokov tu predstavuje 26 miest, 26 prvkov poľa. 449 00:24:08,750 --> 00:24:13,680 Takže sa snaží dostať neuveriteľne priestor ťažké. 450 00:24:13,680 --> 00:24:17,100 >> Ale oni sú veľmi rýchle. 451 00:24:17,100 --> 00:24:22,540 Tak neuveriteľne rýchlo, ale Naozaj priestor neefektívne. 452 00:24:22,540 --> 00:24:24,810 Druh prísť ktorý z nich chcete. 453 00:24:24,810 --> 00:24:29,470 Jedná sa o naozaj cool pre pset, ale oni zaberajú veľa pamäte, 454 00:24:29,470 --> 00:24:30,290 takže si privlastniť. 455 00:24:30,290 --> 00:24:31,480 Jo? 456 00:24:31,480 --> 00:24:34,300 >> Divákov: Bolo by možné nastaviť vyskúšať a potom sa 457 00:24:34,300 --> 00:24:37,967 Akonáhle budete mať všetky údaje v ňom, že ste need-- 458 00:24:37,967 --> 00:24:39,550 Ja neviem, či to bude mať zmysel. 459 00:24:39,550 --> 00:24:42,200 Bol som ako sa zbaviť všetkých Znaky NULL, ale potom 460 00:24:42,200 --> 00:24:42,910 nebudete môcť indexu them-- 461 00:24:42,910 --> 00:24:43,275 >> SPEAKER 1: Stále potrebujú. 462 00:24:43,275 --> 00:24:44,854 >> Divákov: - rovnakým spôsobom zakaždým. 463 00:24:44,854 --> 00:24:45,520 SPEAKER 1: Jo. 464 00:24:45,520 --> 00:24:50,460 Musíte sa znaky NULL, aby ak viete, že to nie je tam slovo. 465 00:24:50,460 --> 00:24:52,040 Ben sa máte niečo, čo chcete? 466 00:24:52,040 --> 00:24:52,540 OK. 467 00:24:52,540 --> 00:24:54,581 Tak jo, ideme ísť trochu viac 468 00:24:54,581 --> 00:24:58,920 do technických podrobností za snažiť a pracovať na príklade. 469 00:24:58,920 --> 00:25:01,490 >> OK, tak je to to isté. 470 00:25:01,490 --> 00:25:06,290 Vzhľadom k tomu, v prepojenom zozname, naše hlavné druh of-- čo je to slovo, ktoré som chcel? - 471 00:25:06,290 --> 00:25:08,350 ako stavebný blok bol uzol. 472 00:25:08,350 --> 00:25:12,280 V pokuse, máme tiež uzol, ale je to definované inak. 473 00:25:12,280 --> 00:25:17,000 >> Takže máme nejaký bool, že znamená, či slová skutočne 474 00:25:17,000 --> 00:25:23,530 existuje na tomto mieste, a potom máme nejaké pole here-- alebo skôr, 475 00:25:23,530 --> 00:25:27,840 To je ukazovateľ na Polia 27 znakov. 476 00:25:27,840 --> 00:25:33,339 A to je pre, v tomto prípade, to 27-- Som si istý, všetci z vás sú ako, počkajte, 477 00:25:33,339 --> 00:25:34,880 tam je 26 písmen v abecede. 478 00:25:34,880 --> 00:25:36,010 Prečo máme 27? 479 00:25:36,010 --> 00:25:37,870 >> Takže v závislosti na spôsob, ako realizovať to, 480 00:25:37,870 --> 00:25:43,240 To je z pset, že povolené apostrofy. 481 00:25:43,240 --> 00:25:46,010 Takže to je dôvod, prečo navyše jeden. 482 00:25:46,010 --> 00:25:50,500 Budete mať tiež v niektorých prípady null terminačných 483 00:25:50,500 --> 00:25:53,230 je zahrnutá ako jeden z znaky, že to nemá byť, 484 00:25:53,230 --> 00:25:56,120 a to je to, ako skontrolovať, zistiť, či je to koniec slova. 485 00:25:56,120 --> 00:26:01,340 Ak máte záujem, pozrite sa Kevin video na study.cs50, 486 00:26:01,340 --> 00:26:04,790 ako aj Wikipedia má niektoré dobré zdroje tam. 487 00:26:04,790 --> 00:26:09,000 >> Ale my ideme prejsť len tak o tom, ako môžete pracovať na pokus 488 00:26:09,000 --> 00:26:11,010 ak ste dal dnes. 489 00:26:11,010 --> 00:26:16,230 Takže tu máme super jednoduchá tu, že má slová "BAT" a "zoom" v nich. 490 00:26:16,230 --> 00:26:18,920 A ako vidíme tu, tento malý priestor tu 491 00:26:18,920 --> 00:26:22,560 reprezentuje našu bool, že hovorí, áno, je to slovo. 492 00:26:22,560 --> 00:26:27,060 A potom to má našu pole znakov, nie? 493 00:26:27,060 --> 00:26:33,480 >> Tak sme sa ísť cez hľadania "BAT" v tomto pokuse. 494 00:26:33,480 --> 00:26:38,340 Takže začať hore, nie? 495 00:26:38,340 --> 00:26:46,290 A my vieme, že b zodpovedá druhý index, druhý prvok 496 00:26:46,290 --> 00:26:47,840 V tomto poli, pretože a b. 497 00:26:47,840 --> 00:26:51,340 Takže približne druhý. 498 00:26:51,340 --> 00:26:58,820 >> A hovorí, OK, v pohode, z toho, že do ďalšie pole, pretože keď si spomenieme, 499 00:26:58,820 --> 00:27:02,160 je to tak, že každý z nich v skutočnosti obsahuje prvok. 500 00:27:02,160 --> 00:27:07,110 Každý jeden z týchto polí obsahuje ukazovateľ, že jo? 501 00:27:07,110 --> 00:27:10,030 To je dôležitý rozdiel, aby sa. 502 00:27:10,030 --> 00:27:13,450 >> Viem, že to bude be-- snaží sa naozaj ťažké sa dostať na prvýkrát, 503 00:27:13,450 --> 00:27:15,241 takže aj keď je to druhý alebo tretí čas 504 00:27:15,241 --> 00:27:18,370 a je to stále trochu zo zdanlivo ťažké, 505 00:27:18,370 --> 00:27:21,199 Sľubujem, že keď idete na hodinky zajtra krátky znova, 506 00:27:21,199 --> 00:27:22,740 to bude asi robiť oveľa väčší zmysel. 507 00:27:22,740 --> 00:27:23,890 To trvá veľa tráviť. 508 00:27:23,890 --> 00:27:27,800 Ja ešte niekedy som ako, počkaj, čo je to vyskúšať? 509 00:27:27,800 --> 00:27:29,080 Ako mám použiť? 510 00:27:29,080 --> 00:27:33,880 >> Preto sme B v tomto prípade, ktorý je naším druhým index. 511 00:27:33,880 --> 00:27:40,240 Keby sme mali, povedzme, c alebo d alebo iné písmeno, 512 00:27:40,240 --> 00:27:45,810 musíme zmapovať to späť do indexu nášho poľa, ktoré, ktoré zodpovedá. 513 00:27:45,810 --> 00:27:56,930 Tak by sme brať ako rchar a my sme odpočítať off mapovať do 0 do 25. 514 00:27:56,930 --> 00:27:58,728 Všetci dobre, ako Mapa naše postavy? 515 00:27:58,728 --> 00:28:00,440 OK. 516 00:28:00,440 --> 00:28:05,980 >> Tak ideme na druhú a my vidieť, že, áno, to nie je NULL. 517 00:28:05,980 --> 00:28:07,780 Môžeme prejsť k tomuto ďalšiemu poli. 518 00:28:07,780 --> 00:28:12,300 Tak ideme na tejto ďalšie pole tu. 519 00:28:12,300 --> 00:28:15,500 >> A my hovoríme, OK, teraz je potrebné zistiť, či je tu. 520 00:28:15,500 --> 00:28:18,590 Je null alebo to robí vlastne vpred? 521 00:28:18,590 --> 00:28:21,880 Tak vlastne pohybuje odovzdal v tomto poli. 522 00:28:21,880 --> 00:28:24,570 A my hovoríme, OK, t je náš posledné písmeno. 523 00:28:24,570 --> 00:28:27,580 Tak sme sa ísť do t na indexe. 524 00:28:27,580 --> 00:28:30,120 A potom sme sa dopredu pretože je tu ešte jeden. 525 00:28:30,120 --> 00:28:38,340 A toto hovorí v podstate to, že áno, sa hovorí, že je slovo here-- 526 00:28:38,340 --> 00:28:41,750 že ak budete postupovať podľa tohto cesta, ste dorazili 527 00:28:41,750 --> 00:28:43,210 na slová, ktoré ako vieme, je "bat". 528 00:28:43,210 --> 00:28:43,800 Áno? 529 00:28:43,800 --> 00:28:46,770 >> Divákov: Je štandardné, aby toto ako index 0 a potom akúsi na 1 530 00:28:46,770 --> 00:28:47,660 alebo mať na konci? 531 00:28:47,660 --> 00:28:48,243 >> SPEAKER 1: Nie 532 00:28:48,243 --> 00:28:55,360 Takže ak sa pozrieme späť na našej Vyhlásenie tu, je to bool, 533 00:28:55,360 --> 00:28:59,490 tak je to jeho vlastný element v uzle. 534 00:28:59,490 --> 00:29:03,331 Takže to nie je súčasťou poľa. 535 00:29:03,331 --> 00:29:03,830 V pohode. 536 00:29:03,830 --> 00:29:08,370 Takže keď sme dokončiť naše slovo a my sme na tomto poli, to, čo chceme robiť 537 00:29:08,370 --> 00:29:12,807 je vykonať kontrolu na toto slovo. 538 00:29:12,807 --> 00:29:14,390 A v tomto prípade by to vrátiť áno. 539 00:29:14,390 --> 00:29:17,220 540 00:29:17,220 --> 00:29:24,090 >> Takže v takom prípade, vieme, že "zoo" - poznáme ako človeka, ktorý "zoo" je slovo, 541 00:29:24,090 --> 00:29:24,820 že jo? 542 00:29:24,820 --> 00:29:28,990 Ale skúsiť by tu hovoria, nie, to nie. 543 00:29:28,990 --> 00:29:33,980 A to by som povedal, že preto, že sme neboli označené ako slovo tu. 544 00:29:33,980 --> 00:29:40,440 Aj napriek tomu, že môžeme prejsť až do tohto poľa, 545 00:29:40,440 --> 00:29:43,890 Tento pokus by povedal, že nie, zoo nie je v slovníku 546 00:29:43,890 --> 00:29:47,070 pretože nemáme označené ako také. 547 00:29:47,070 --> 00:29:52,870 >> Takže jeden spôsob, ako to urobiť that-- oh, sorry, toto. 548 00:29:52,870 --> 00:29:59,450 Takže v tomto prípade, "zoo" nie je slovo, ale to je v našom pokuse. 549 00:29:59,450 --> 00:30:05,690 Ale v tomto jednom, že by sme si to želajú predstaviť slovo "kúpele", čo sa 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 Sme v tomto poli, a ideme hľadať h. 552 00:30:11,820 --> 00:30:15,220 >> V tomto prípade, kedy sa pozrieť na ukazovateľ 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 ak je to výslovne ukázal na iné pole, 555 00:30:20,780 --> 00:30:25,000 predpokladať, že všetky ukazovatele V tomto poli sa ukazuje na hodnotu null. 556 00:30:25,000 --> 00:30:28,270 Takže v tomto prípade, h sa ukazuje na hodnotu null, takže nemôžeme nič robiť, 557 00:30:28,270 --> 00:30:31,540 tak to by tiež vrátiť false, "kúpeľ" nie je tu. 558 00:30:31,540 --> 00:30:34,102 559 00:30:34,102 --> 00:30:35,810 Takže teraz sme vlastne ísť cez 560 00:30:35,810 --> 00:30:39,790 ako by sme vlastne povedať, že "zoo" má v našom pokuse. 561 00:30:39,790 --> 00:30:42,920 Ako môžeme vložiť "zoo" do nášho pokusu? 562 00:30:42,920 --> 00:30:47,810 Takže rovnakým spôsobom, ako sme začali náš spájať zoznam, začneme pri koreni. 563 00:30:47,810 --> 00:30:50,600 Ak ste na pochybách, začnite koreň z týchto vecí. 564 00:30:50,600 --> 00:30:53,330 >> A budeme hovoriť, OK, z. 565 00:30:53,330 --> 00:30:55,650 z existuje v tejto, a to robí. 566 00:30:55,650 --> 00:30:58,370 Takže ste sa presťahovali na váš ďalší polia, OK? 567 00:30:58,370 --> 00:31:01,482 A potom na ďalšie, hovoríme, OK, to o existuje? 568 00:31:01,482 --> 00:31:03,000 To robí. 569 00:31:03,000 --> 00:31:04,330 To znova. 570 00:31:04,330 --> 00:31:08,670 >> A tak sa na našej ďalšej, sme povedali, OK, "zoo" už tu existuje. 571 00:31:08,670 --> 00:31:12,440 Všetko, čo musíme urobiť, je nastaviť to rovná na pravda, že je tam slovo. 572 00:31:12,440 --> 00:31:15,260 Ak ste sledoval všetko až do tohto bodu, 573 00:31:15,260 --> 00:31:17,030 je to slovo, tak len nastavte ju na hodnotu, napr. 574 00:31:17,030 --> 00:31:17,530 Áno? 575 00:31:17,530 --> 00:31:22,550 >> Divákov: Tak to robí znamená, že "ba" je slovo, ktoré tiež? 576 00:31:22,550 --> 00:31:24,120 >> SPEAKER 1: Nie 577 00:31:24,120 --> 00:31:28,870 Takže v tomto prípade, "ba" by sme sa dostali Tu by sme povedať, je to slovo, 578 00:31:28,870 --> 00:31:31,590 a stále by byť. 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ákov: Takže akonáhle je to slovo, a vy hovoríte áno, potom to 582 00:31:36,360 --> 00:31:38,380 bude obsahovať ísť do m? 583 00:31:38,380 --> 00:31:42,260 >> SPEAKER 1: Tak to má čo do činenia with-- ste načítava to v. 584 00:31:42,260 --> 00:31:43,640 Hovoríte, že "zoo" je slovo. 585 00:31:43,640 --> 00:31:47,020 Keď idete do check-- ako, že chcete povedať, 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 Ste len bude hľadať "zoo" a potom skontrolujte, či je to slovo. 588 00:31:54,200 --> 00:31:57,291 Vy ste nikdy pohybovať až m, pretože to nie je 589 00:31:57,291 --> 00:31:58,290 to, čo hľadáte. 590 00:31:58,290 --> 00:32:02,690 591 00:32:02,690 --> 00:32:08,070 >> Ak teda vlastne chcel pridať "kúpeľ" v tomto pokuse, 592 00:32:08,070 --> 00:32:11,390 budeme robiť to isté ako sme to urobili s "zoo" 593 00:32:11,390 --> 00:32:15,380 s výnimkou by sme vidieť, že keď sme pokúsiť sa dostať h, to neexistuje. 594 00:32:15,380 --> 00:32:20,090 Takže si môžete myslieť na to, ako sa snaží pre pridanie nového uzla do prepojeného zoznamu 595 00:32:20,090 --> 00:32:27,210 tak by sme museli pridať ďalšie jeden z týchto polí, ako tak. 596 00:32:27,210 --> 00:32:35,670 A potom to, čo robíme, je jednoducho nastaviť h prvok tohto poľa ukazuje na to. 597 00:32:35,670 --> 00:32:39,430 >> A potom to, čo by chcel robiť? 598 00:32:39,430 --> 00:32:43,110 Pridať sa rovná pravda pretože je to slovo. 599 00:32:43,110 --> 00:32:46,350 600 00:32:46,350 --> 00:32:48,150 V pohode. 601 00:32:48,150 --> 00:32:48,700 Ja viem. 602 00:32:48,700 --> 00:32:51,170 Pokusy nie sú najviac vzrušujúce. 603 00:32:51,170 --> 00:32:54,250 Ver mi, ja viem. 604 00:32:54,250 --> 00:32:58,040 >> Takže jedna vec je si uvedomiť, s pokusoch, Povedal som, že sú veľmi efektívne. 605 00:32:58,040 --> 00:33:00,080 Preto sme, videli zaberajú veľa miesta. 606 00:33:00,080 --> 00:33:01,370 Sú to trochu mätúce. 607 00:33:01,370 --> 00:33:03,367 Tak prečo by sme vôbec používať tieto? 608 00:33:03,367 --> 00:33:05,450 Používame tieto, pretože sú neuveriteľne efektívna. 609 00:33:05,450 --> 00:33:08,130 >> Takže ak ste niekedy hľadáte up slová, ste len 610 00:33:08,130 --> 00:33:10,450 ohraničené dĺžkou slova. 611 00:33:10,450 --> 00:33:15,210 Takže ak hľadáte slovo, ktoré je v dĺžke piatich, 612 00:33:15,210 --> 00:33:20,940 ste len niekedy musieť aby u väčšiny piatich porovnaniach, OK? 613 00:33:20,940 --> 00:33:25,780 Takže je to v podstate konštantný. 614 00:33:25,780 --> 00:33:29,150 Rovnako ako vkladanie a vyhľadávanie sú v podstate konštantné čas. 615 00:33:29,150 --> 00:33:33,750 >> Takže ak môžete niekedy niečo v konštantnom čase, 616 00:33:33,750 --> 00:33:35,150 je to tak dobré, ako to dostane. 617 00:33:35,150 --> 00:33:37,990 Nemôžete lepší ako konštantný čas na tieto veci. 618 00:33:37,990 --> 00:33:43,150 Tak, že je jedným z obrovské plusy pokusov. 619 00:33:43,150 --> 00:33:46,780 >> Ale je to veľa priestoru. 620 00:33:46,780 --> 00:33:50,380 Takže tak nejako sa rozhodnúť, čo je pre vás dôležitejšie. 621 00:33:50,380 --> 00:33:54,700 A na dnešných počítačoch, priestor, ktorý pokus môže trvať až 622 00:33:54,700 --> 00:33:57,740 Možno, že nemá vplyv na si, že veľa, ale možno 623 00:33:57,740 --> 00:34:01,350 máte čo do činenia s niečím ktorá má ďaleko, ďaleko viac vecí, 624 00:34:01,350 --> 00:34:02,810 a pokus jednoducho nie je rozumné. 625 00:34:02,810 --> 00:34:03,000 Áno? 626 00:34:03,000 --> 00:34:05,610 >> Publikum: Počkaj, takže budete mať 26 písmená jedného 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 nejaký je slovo, značka a potom Máte 26 ukazovateľov v každom jednom. 630 00:34:16,984 --> 00:34:17,775 A oni point-- 631 00:34:17,775 --> 00:34:20,280 >> Divákov: A každý 26, že každý z nich má 26? 632 00:34:20,280 --> 00:34:21,500 >> SPEAKER 1: Áno. 633 00:34:21,500 --> 00:34:27,460 A to je dôvod, prečo, ako môžete vidieť, že sa rozširuje veľmi rýchlo. 634 00:34:27,460 --> 00:34:28,130 Dobrá. 635 00:34:28,130 --> 00:34:32,524 Takže budeme sa dostať do stromov, ktoré Mám pocit, že je jednoduchšie a pravdepodobne 636 00:34:32,524 --> 00:34:36,150 je pekný malý odklad z pokusov tam. 637 00:34:36,150 --> 00:34:39,620 Takže dúfajme, že väčšina z vás ktoré videl strom. 638 00:34:39,620 --> 00:34:41,820 Nie ako celkom Tie mimo, ktoré som 639 00:34:41,820 --> 00:34:44,340 ak nie sú niekto vedieť šiel vonku v poslednej dobe. 640 00:34:44,340 --> 00:34:49,230 Išiel som jablko vychystávanie tento víkend a oh môj bože, to bolo krásne. 641 00:34:49,230 --> 00:34:52,250 Nevedel som, že listy môže vyzerať, že dosť. 642 00:34:52,250 --> 00:34:53,610 >> Takže je to len strom, nie? 643 00:34:53,610 --> 00:34:56,790 Je to len nejaký uzol, a to poukazuje na veľa ďalších uzlov. 644 00:34:56,790 --> 00:34:59,570 Ako vidíte tu, je to druh opakujúce sa téma. 645 00:34:59,570 --> 00:35:03,720 Uzly ukazujúci uzlov je druh Podstatou mnohých dátových štruktúr. 646 00:35:03,720 --> 00:35:06,670 Záleží len na tom, ako nechať upozorniť na seba 647 00:35:06,670 --> 00:35:08,600 a ako sme sa prejsť skrze ne a ako 648 00:35:08,600 --> 00:35:14,500 vložiť veci, ktoré určuje ich odlišné charakteristiky. 649 00:35:14,500 --> 00:35:17,600 >> Takže len niektoré pojmy, ktorý som používal predtým. 650 00:35:17,600 --> 00:35:20,010 Tak root je to, čo je na samom vrchole. 651 00:35:20,010 --> 00:35:21,200 to je miesto, kde sme sa vždy začať. 652 00:35:21,200 --> 00:35:23,610 Môžete si ju predstaviť ako hlavy tiež. 653 00:35:23,610 --> 00:35:28,750 Ale stromy, máme tendenciu odkazujú na to ako root. 654 00:35:28,750 --> 00:35:32,820 >> Čokoľvek na spodnej here-- na veľmi, veľmi bottom-- 655 00:35:32,820 --> 00:35:34,500 sú považované za listy. 656 00:35:34,500 --> 00:35:37,210 Tak to ide ruka v ruke s Celý strom vec, nie? 657 00:35:37,210 --> 00:35:39,860 Listy sú pri okrajoch stromu. 658 00:35:39,860 --> 00:35:45,820 >> A potom máme tiež pár Podmienky hovoriť o uzloch vo vzťahu 659 00:35:45,820 --> 00:35:46,680 k sebe navzájom. 660 00:35:46,680 --> 00:35:49,700 Takže máme rodičia, deti a súrodenci. 661 00:35:49,700 --> 00:35:56,260 Takže v tomto prípade, je 3 rodič 5, 6 a 7. 662 00:35:56,260 --> 00:36:00,370 Takže rodič, čo je o krok vyššie, čo ste 663 00:36:00,370 --> 00:36:02,940 s odkazom na to, tak jednoducho ako rodokmeň. 664 00:36:02,940 --> 00:36:07,090 Dúfajme, že je to všetko trochu trochu viac intuitívne než pokusov. 665 00:36:07,090 --> 00:36:10,970 >> Súrodenci sú všetky, ktoré majú tá istá materská, nie? 666 00:36:10,970 --> 00:36:13,470 Sú na rovnakej úrovni tu. 667 00:36:13,470 --> 00:36:16,960 A potom, keď som bol hovorí, deti sú len 668 00:36:16,960 --> 00:36:22,630 čo je jeden krok ďalej uzol v otázke, OK? 669 00:36:22,630 --> 00:36:23,470 V pohode. 670 00:36:23,470 --> 00:36:25,610 Tak binárny strom. 671 00:36:25,610 --> 00:36:31,450 Môže niekto hádať, na jednom z vlastnosti binárneho stromu? 672 00:36:31,450 --> 00:36:32,770 >> Divákov: Max dva lístky. 673 00:36:32,770 --> 00:36:33,478 >> SPEAKER 1: Správne. 674 00:36:33,478 --> 00:36:34,640 Takže max dvoch listov. 675 00:36:34,640 --> 00:36:39,730 Takže v tomto jednom skôr, mali sme tento ktorá mala tri, ale v binárnom strome, 676 00:36:39,730 --> 00:36:45,000 Máte-max dvoch detí na rodičov, že jo? 677 00:36:45,000 --> 00:36:46,970 Je tu ďalší zaujímavá vlastnosť. 678 00:36:46,970 --> 00:36:51,550 Vie niekto, že? 679 00:36:51,550 --> 00:36:52,620 Binárny strom. 680 00:36:52,620 --> 00:37:00,350 >> Takže binárny strom bude mať všetko na the-- toto nie je sorted-- 681 00:37:00,350 --> 00:37:05,320 ale v zoradené binárneho stromu, všetko na pravej strane 682 00:37:05,320 --> 00:37:08,530 je väčšia ako pôvodná, a všetko, čo na ľavej strane 683 00:37:08,530 --> 00:37:10,035 je menšia než rodičia. 684 00:37:10,035 --> 00:37:15,690 A to bol kvíz Otázka pred, tak dobré to vedieť. 685 00:37:15,690 --> 00:37:19,500 Takže spôsob, ako definovať to, opäť máme ďalší uzol. 686 00:37:19,500 --> 00:37:21,880 To vyzerá veľmi podobne ako čo? 687 00:37:21,880 --> 00:37:28,336 688 00:37:28,336 --> 00:37:28,836 Dvojnásobne 689 00:37:28,836 --> 00:37:29,320 >> Divákov: spojových zoznamov 690 00:37:29,320 --> 00:37:31,100 >> SPEAKER 1: dvojitý spájať zoznam, nie? 691 00:37:31,100 --> 00:37:33,690 Ak teda nahradiť tento s predchádzajúcou a nasledujúce, 692 00:37:33,690 --> 00:37:35,670 by to bolo dvojnásobne spájať zoznam. 693 00:37:35,670 --> 00:37:40,125 Ale v tomto prípade sme sa vlastne sú vľavo a vpravo, a je to. 694 00:37:40,125 --> 00:37:41,500 Inak je to úplne rovnaké. 695 00:37:41,500 --> 00:37:43,374 Stále máme prvok hľadáte, 696 00:37:43,374 --> 00:37:45,988 a stačia dva ukazovatele bude, čo bude ďalej. 697 00:37:45,988 --> 00:37:49,210 698 00:37:49,210 --> 00:37:51,870 Jo, tak binárny vyhľadávací strom. 699 00:37:51,870 --> 00:37:57,665 Ak sme si všimli, všetko na tu je väčší than-- 700 00:37:57,665 --> 00:37:59,850 alebo všetko ihneď aby tu 701 00:37:59,850 --> 00:38:02,840 je väčšia než, všetko Tu je menšia ako. 702 00:38:02,840 --> 00:38:06,980 703 00:38:06,980 --> 00:38:14,000 >> Takže, ak by sme mali prehľadávať, by mal vyzerať veľmi blízko k binárne vyhľadávanie 704 00:38:14,000 --> 00:38:14,910 tu, že jo? 705 00:38:14,910 --> 00:38:17,640 Okrem namiesto hľadania na polovicu poľa, 706 00:38:17,640 --> 00:38:21,720 sme sa len pri pohľade na ľavú strane alebo na pravej strane stromu. 707 00:38:21,720 --> 00:38:24,850 Tak to je trochu jednoduchšie, myslím. 708 00:38:24,850 --> 00:38:29,300 >> Takže ak vaša koreň je NULL, samozrejme je to len falošná. 709 00:38:29,300 --> 00:38:33,470 A ak to tam je, samozrejme, že je to pravda. 710 00:38:33,470 --> 00:38:35,320 Ak je to menej, než sme sa hľadať vľavo. 711 00:38:35,320 --> 00:38:37,070 Ak je väčší ako hľadáme právo. 712 00:38:37,070 --> 00:38:39,890 Je to presne ako binárne vyhľadávanie, len odlišná štruktúra dát 713 00:38:39,890 --> 00:38:40,600 že sme použili. 714 00:38:40,600 --> 00:38:42,790 Miesto poľa, je to len binárny 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 tiež to vyzerá, že my môže mať trochu času. 718 00:38:51,550 --> 00:38:54,460 Ak sa tak stane, som rád, že ísť cez toto všetko znova. 719 00:38:54,460 --> 00:38:56,856 OK, tak komíny. 720 00:38:56,856 --> 00:39:02,695 Pamätá si niekto, čo stacks-- všetky charakteristiky zásobníka? 721 00:39:02,695 --> 00:39:05,550 722 00:39:05,550 --> 00:39:10,400 >> OK, takže väčšina z nás, myslím, jesť v jedálni halls-- 723 00:39:10,400 --> 00:39:13,100 čo môžeme neradi. 724 00:39:13,100 --> 00:39:16,900 Ale samozrejme, môžete myslieť na zásobníku doslova len ako hromadu zásobníkov 725 00:39:16,900 --> 00:39:18,460 alebo hromadu vecí. 726 00:39:18,460 --> 00:39:21,820 A čo je dôležité si uvedomiť, že je to 727 00:39:21,820 --> 00:39:26,850 something-- charakteristika že hovoríme, že by-- je LIFO. 728 00:39:26,850 --> 00:39:28,450 Vie niekto, čo to znamená? 729 00:39:28,450 --> 00:39:29,070 Mmhmm? 730 00:39:29,070 --> 00:39:30,650 >> DIVÁKOV: Posledné dnu, prvý von. 731 00:39:30,650 --> 00:39:32,250 >> SPEAKER 1: Dobre, posledný dnu, prvý von. 732 00:39:32,250 --> 00:39:36,585 Takže ak vieme, či sme stohovanie veci up, najjednoduchšie chytiť off-- 733 00:39:36,585 --> 00:39:39,570 a snáď jediné, čo môžeme chytiť vypne, ak náš stack je veľký enough-- 734 00:39:39,570 --> 00:39:40,850 je to, že horný prvok. 735 00:39:40,850 --> 00:39:43,460 Takže bez ohľadu bol kladený na last-- ako vidíme tu, 736 00:39:43,460 --> 00:39:46,370 čo bol zatlačený na väčšine recently-- je 737 00:39:46,370 --> 00:39:51,160 bude prvý vec, že ​​sme pop off, OK? 738 00:39:51,160 --> 00:39:56,324 >> Takže to, čo tu máme, je ďalšie typedef struct. 739 00:39:56,324 --> 00:39:58,740 To je naozaj len rád rýchlokurz v dátovej štruktúre, 740 00:39:58,740 --> 00:40:01,650 takže je tu veľa hodená na vás chlapci. 741 00:40:01,650 --> 00:40:02,540 Ja viem. 742 00:40:02,540 --> 00:40:04,970 Takže ďalší Struct. 743 00:40:04,970 --> 00:40:06,740 Yay pre stavby. 744 00:40:06,740 --> 00:40:16,660 >> A v tomto prípade, je to nejaký ukazovateľ na pole, ktoré má určitú kapacitu. 745 00:40:16,660 --> 00:40:20,830 Takže to predstavuje náš stack Tu, rovnako ako našej aktuálnej pole 746 00:40:20,830 --> 00:40:22,520 ktoré držia naše prvkov. 747 00:40:22,520 --> 00:40:24,850 A potom tu máme nejaké veľkosti. 748 00:40:24,850 --> 00:40:31,170 >> A zvyčajne, chcete, aby track o tom, aký veľký je váš stack 749 00:40:31,170 --> 00:40:36,180 pretože to, čo sa deje, aby môžete urobiť, je, ak viete, že veľkosť, 750 00:40:36,180 --> 00:40:39,170 to vám umožní povedať, OK, som na plný výkon? 751 00:40:39,170 --> 00:40:40,570 Môžem pridať niečo viac? 752 00:40:40,570 --> 00:40:44,650 A tiež vám povie, kde horná časť zásobníka 753 00:40:44,650 --> 00:40:48,180 tak viete, čo ste môže skutočne vzlietnuť. 754 00:40:48,180 --> 00:40:51,760 A to vlastne bude tu trochu jasnejšie. 755 00:40:51,760 --> 00:40:57,350 >> Takže pre stisk, jednu vec, ak máte bol vždy realizovať tlačiť, 756 00:40:57,350 --> 00:41:01,330 ako som práve povedal, vaše zásobník má obmedzenú veľkosť, je to tak? 757 00:41:01,330 --> 00:41:03,990 Naše pole mal nejakú 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é veľkosti, takže je potrebné, aby Uistite sa, že nie sme uvedení viac 760 00:41:08,930 --> 00:41:11,950 do nášho poľa, než sme skutočne priestor pre. 761 00:41:11,950 --> 00:41:16,900 >> Takže, keď budete vytvárať tlak funkcie, prvá vec, ktorú urobiť, je povedať, OK, 762 00:41:16,900 --> 00:41:18,570 mám miesto vo svojom stacku? 763 00:41:18,570 --> 00:41:23,330 Pretože keď to neurobím, prepáč, Nemôžem uložiť prvok. 764 00:41:23,330 --> 00:41:28,980 Keď to urobím, potom budete chcieť uložiť je na vrchole zásobníka, je to tak? 765 00:41:28,980 --> 00:41:31,325 >> A to je dôvod, prečo máme sledovať našej veľkosti. 766 00:41:31,325 --> 00:41:35,290 Ak nebudeme mať prehľad o našej veľkosti, nevieme, kam to dať. 767 00:41:35,290 --> 00:41:39,035 Nevieme, ako veľa vecí, sú v našom poli už. 768 00:41:39,035 --> 00:41:41,410 Ako samozrejme existujú spôsoby, ako že možno by ste mohli urobiť. 769 00:41:41,410 --> 00:41:44,610 Dalo by sa inicializovať všetko NULL a potom skontrolujte, či máte najnovšiu verziu NULL, 770 00:41:44,610 --> 00:41:47,950 ale oveľa jednoduchšie vec je jednoducho povedať, OK, sledovať veľkosti. 771 00:41:47,950 --> 00:41:51,840 Rovnako ako viem, že mám štyri prvky v mojom poli, takže ďalšia vec, 772 00:41:51,840 --> 00:41:55,930 že sme dali na, sme bude ukladať na indexe 4. 773 00:41:55,930 --> 00:42:00,940 A potom, samozrejme, to znamená, že ste úspešne tlačil niečo 774 00:42:00,940 --> 00:42:03,320 na stacku, ste chcete zvýšiť veľkosť 775 00:42:03,320 --> 00:42:08,880 takže viete, kde ste tak že môžete tlačiť viac vecí na. 776 00:42:08,880 --> 00:42:12,730 >> Takže ak sa snažíme pop niečo z kôpky, 777 00:42:12,730 --> 00:42:16,072 čo by mohlo byť prvá vec, že chceme skontrolovať? 778 00:42:16,072 --> 00:42:18,030 Snažíte sa vziať niečo z vášho stacku. 779 00:42:18,030 --> 00:42:21,710 780 00:42:21,710 --> 00:42:24,781 Ste si istý, že je to niečo v zásobníku? 781 00:42:24,781 --> 00:42:25,280 Nie. 782 00:42:25,280 --> 00:42:26,894 Takže to, čo by sme mohli chcieť skontrolovať? 783 00:42:26,894 --> 00:42:27,810 >> Divákov: [nepočuteľné]. 784 00:42:27,810 --> 00:42:29,880 SPEAKER 1: Skontrolujte, či veľkosť? 785 00:42:29,880 --> 00:42:31,840 Veľkosť. 786 00:42:31,840 --> 00:42:38,520 Takže chceme skontrolovať, či Naša veľkosť je väčšia ako 0, OK? 787 00:42:38,520 --> 00:42:44,970 A ak áno, potom chceme znížiť Naše veľkosť od 0 a vrátiť to. 788 00:42:44,970 --> 00:42:45,840 Prečo? 789 00:42:45,840 --> 00:42:49,950 >> V prvom z nich sme boli tlačenie, to tlačil nás 790 00:42:49,950 --> 00:42:52,460 na veľkosti a potom priebežne aktualizovaným veľkosti. 791 00:42:52,460 --> 00:42:57,850 V tomto prípade sme dekrementování veľkosť a potom ju zložil, šklbanie ju 792 00:42:57,850 --> 00:42:58,952 z našej rady. 793 00:42:58,952 --> 00:42:59,826 Prečo by sme mohli urobiť, že? 794 00:42:59,826 --> 00:43:04,800 795 00:43:04,800 --> 00:43:11,811 Takže ak mám jednu vec na mojom stacku, Čo by bola moja veľkosť v tomto mieste? 796 00:43:11,811 --> 00:43:13,140 1. 797 00:43:13,140 --> 00:43:15,180 >> A kde je prvok 1 uložené? 798 00:43:15,180 --> 00:43:17,621 Na čo 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 prípade sme Vždy je potrebné vykonať sure-- 802 00:43:22,800 --> 00:43:27,630 miesto vrátenia veľkosť mínus 1, pretože sme 803 00:43:27,630 --> 00:43:31,730 vieme, že naša prvok je bude uložený na 1 menej 804 00:43:31,730 --> 00:43:34,705 bez ohľadu na našu veľkosť je, toto len sa o to postarám. 805 00:43:34,705 --> 00:43:36,080 Je to o niečo viac elegantný spôsob. 806 00:43:36,080 --> 00:43:41,220 A my len decrement otázky veľkosť a potom sa vrátiť veľkosť. 807 00:43:41,220 --> 00:43:42,330 Mmhmm? 808 00:43:42,330 --> 00:43:45,300 >> Divákov: Myslím, že len všeobecne, prečo by to dátová štruktúra 809 00:43:45,300 --> 00:43:47,800 byť výhodné? 810 00:43:47,800 --> 00:43:50,660 >> SPEAKER 1: Záleží na vašom kontextu. 811 00:43:50,660 --> 00:43:57,420 Tak pre niektoré z teórie, ak pracujete with-- OK, 812 00:43:57,420 --> 00:44:02,750 dovoľte mi, aby som zistil, či je prospešné jeden ktorá je prospešná pre viac ako vonku 813 00:44:02,750 --> 00:44:05,420 ČS. 814 00:44:05,420 --> 00:44:15,780 U komínov, kedykoľvek budete potrebovať sledovať niečo, čo 815 00:44:15,780 --> 00:44:20,456 sa naposledy pridaný je, keď budete chcieť použiť zásobník. 816 00:44:20,456 --> 00:44:24,770 >> A ja si nemyslím, že je dobrý Príkladom, že práve teraz. 817 00:44:24,770 --> 00:44:29,955 Ale kedykoľvek posledná čo je pre vás najdôležitejšie, 818 00:44:29,955 --> 00:44:31,705 to je, keď stack bude užitočné. 819 00:44:31,705 --> 00:44:35,797 820 00:44:35,797 --> 00:44:39,330 Snažím sa, že ak tam je dobrý pre to. 821 00:44:39,330 --> 00:44:43,720 Ak by som myslieť na dobrý príklad v ďalšej 20 minút a to sa určite povedať. 822 00:44:43,720 --> 00:44:49,455 >> Ale celkovo, či je niečo, ako som povedal, že väčšina, kde posledná 823 00:44:49,455 --> 00:44:52,470 Najdôležitejšie je, že sa kde balík vstúpi do hry. 824 00:44:52,470 --> 00:44:58,860 Vzhľadom k tomu, fronty sú trochu naopak. 825 00:44:58,860 --> 00:44:59,870 A všetky tie malé psy. 826 00:44:59,870 --> 00:45:00,890 Nie je to skvelé, že jo? 827 00:45:00,890 --> 00:45:03,299 Mám pocit, ako by som mal len mať zajačik videá 828 00:45:03,299 --> 00:45:05,090 priamo v centre Sekcia pre vás 829 00:45:05,090 --> 00:45:08,870 pretože sa jedná o intenzívny časť. 830 00:45:08,870 --> 00:45:10,480 >> Tak front. 831 00:45:10,480 --> 00:45:12,710 V podstate front je ako línia. 832 00:45:12,710 --> 00:45:15,780 Vy Som si istý, použitie tejto každodenné, rovnako ako v našich jedálňach. 833 00:45:15,780 --> 00:45:18,160 Takže musíme ísť a dostať naše zásobníky, som 834 00:45:18,160 --> 00:45:21,260 že máte čakať vo fronte Presunutie alebo dostať svoje jedlo. 835 00:45:21,260 --> 00:45:24,650 >> Tak tu je rozdiel je to, že toto je FIFO. 836 00:45:24,650 --> 00:45:30,090 Takže ak LIFO bola naposledy v prvom out, FIFO je first in, first out. 837 00:45:30,090 --> 00:45:33,400 Tak toto je miesto, kde čo si dať Na prvý je vaša najdôležitejšia. 838 00:45:33,400 --> 00:45:35,540 Takže ak ste čakali v line-- môžete 839 00:45:35,540 --> 00:45:39,130 Predstavte si, že ste šiel do choď na nový iPhone 840 00:45:39,130 --> 00:45:42,800 a to bolo stack, kde posledná osoba v súlade ju dostal ako prvý, 841 00:45:42,800 --> 00:45:44,160 ľudia by sa navzájom zabíjali. 842 00:45:44,160 --> 00:45:49,800 >> Takže FIFO, sme všetci veľmi dobre sa tu v reálnom svete, 843 00:45:49,800 --> 00:45:54,930 a to všetko má čo do činenia s naozaj druh obnovovať celý tento riadok 844 00:45:54,930 --> 00:45:56,900 a fronty štruktúru. 845 00:45:56,900 --> 00:46:02,390 Takže zatiaľ čo v zásobníku, máme tlačiť a pop. 846 00:46:02,390 --> 00:46:06,440 S fronty, máme Pridať do zoznamu a dequeue. 847 00:46:06,440 --> 00:46:10,910 Pridať do zoznamu tak v podstate znamená, dať na chrbát, 848 00:46:10,910 --> 00:46:13,680 a Dequeue prostriedky vziať off spredu. 849 00:46:13,680 --> 00:46:18,680 Takže naša dátová štruktúra je trochu zložitejšie. 850 00:46:18,680 --> 00:46:21,060 Máme druhú vec, ako sledovať. 851 00:46:21,060 --> 00:46:25,950 >> Takže bez hlavy, to je presne to, zásobník, nie? 852 00:46:25,950 --> 00:46:27,900 To je rovnakej konštrukcie ako zásobník. 853 00:46:27,900 --> 00:46:32,480 Jediné, čo teraz iné je, že sme túto hlavu, ktorá to, čo si myslíte, že 854 00:46:32,480 --> 00:46:34,272 bude sledovať? 855 00:46:34,272 --> 00:46:35,510 >> Divákov: prvý z nich. 856 00:46:35,510 --> 00:46:38,685 >> SPEAKER 1: Správne, Prvá vec, ktorú sme dali v. 857 00:46:38,685 --> 00:46:41,130 Hlava našej fronty. 858 00:46:41,130 --> 00:46:42,240 Ten, kto je v prvej línii. 859 00:46:42,240 --> 00:46:45,300 860 00:46:45,300 --> 00:46:49,420 Dobre, takže ak urobíme zaradenie do fronty. 861 00:46:49,420 --> 00:46:52,720 862 00:46:52,720 --> 00:46:55,920 Opäť platí, že sa niektorý z Tieto dátové štruktúry, 863 00:46:55,920 --> 00:46:59,760 pretože máme čo do činenia s radom, musíme skontrolovať, či máme priestor. 864 00:46:59,760 --> 00:47:03,290 >> To je niečo ako ja, hovorí vy, ak otvoríte súbor, 865 00:47:03,290 --> 00:47:04,760 je potrebné skontrolovať na null. 866 00:47:04,760 --> 00:47:08,330 S niektorou z týchto komínov a fronty, budete potrebovať 867 00:47:08,330 --> 00:47:13,420 zistiť, či tam je priestor, pretože sme rokovania s pevnou veľkosťou poľa, 868 00:47:13,420 --> 00:47:16,030 ako vidíme here-- 0, 1 všetko až 5. 869 00:47:16,030 --> 00:47:20,690 Takže to, čo robíme v tomto prípade je kontrola aby zistil, či ešte máme priestor. 870 00:47:20,690 --> 00:47:23,110 Je naša veľkosť menšia ako kapacita? 871 00:47:23,110 --> 00:47:28,480 >> Ak tomu tak je, musíme uložiť na chvost a obnovujeme našu veľkosť. 872 00:47:28,480 --> 00:47:30,250 Takže to, čo je možné, že chvost je v tomto prípade? 873 00:47:30,250 --> 00:47:32,360 To nie je výslovne napísané. 874 00:47:32,360 --> 00:47:33,380 Ako by sme to uložiť? 875 00:47:33,380 --> 00:47:34,928 Čo by chvost byť? 876 00:47:34,928 --> 00:47:38,600 877 00:47:38,600 --> 00:47:40,190 >> Takže poďme sa prejsť tento príklad. 878 00:47:40,190 --> 00:47:44,590 Tak toto je pole o veľkosti 6, nie? 879 00:47:44,590 --> 00:47:49,220 A máme teraz, naša veľkosť je 5. 880 00:47:49,220 --> 00:47:55,240 A keď sme sa dať do, bude to ísť do piateho indexu, nie? 881 00:47:55,240 --> 00:47:57,030 Tak skladuje v chvosta. 882 00:47:57,030 --> 00:48:05,600 >> Ďalším spôsobom, ako napísať chvost by len naše pole v indexe veľkosti, nie? 883 00:48:05,600 --> 00:48:07,560 To je veľkosť 5. 884 00:48:07,560 --> 00:48:11,490 Ďalšia vec je ísť do 5. 885 00:48:11,490 --> 00:48:12,296 V pohode? 886 00:48:12,296 --> 00:48:13,290 OK. 887 00:48:13,290 --> 00:48:16,350 Je to trochu zložitejšie dostane keď začneme hrať s hlavou. 888 00:48:16,350 --> 00:48:17,060 Áno? 889 00:48:17,060 --> 00:48:20,090 >> Divákov: Znamená to, že sme by deklarovali pole, ktoré 890 00:48:20,090 --> 00:48:23,880 bolo päť prvkov dlhá a potom budeme pridávať na neho? 891 00:48:23,880 --> 00:48:24,730 >> SPEAKER 1: Nie 892 00:48:24,730 --> 00:48:27,560 Takže v tomto prípade sa jedná o zásobník. 893 00:48:27,560 --> 00:48:31,760 To by byť vyhlásený za ako pole o veľkosti 6. 894 00:48:31,760 --> 00:48:37,120 A v tomto prípade sme stačí jedno voľné miesto. 895 00:48:37,120 --> 00:48:42,720 >> OK, takže jedna vec je v tomto prípade, ak je naša hlava je na 0, 896 00:48:42,720 --> 00:48:45,270 potom stačí ho pridať na veľkosti. 897 00:48:45,270 --> 00:48:51,020 Ale to dostane trochu zložitejšie pretože v skutočnosti, že 898 00:48:51,020 --> 00:48:52,840 nemajú snímku za to, takže budem 899 00:48:52,840 --> 00:48:56,670 k tomu jedno, pretože to nie je tak jednoduché, akonáhle sa 900 00:48:56,670 --> 00:48:59,230 začať, ako sa zbaviť vecí. 901 00:48:59,230 --> 00:49:03,920 A tak vzhľadom k tomu, so zásobníkom si len niekedy 902 00:49:03,920 --> 00:49:08,920 sa starať o to, čo je veľkosť keď pridávate niečo ďalej, 903 00:49:08,920 --> 00:49:15,710 s frontu je tiež nutné, aby sa Uistite sa, že vaša hlava sa účtuje, 904 00:49:15,710 --> 00:49:20,760 pretože super vec o frontoch je, že ak nie ste na plný výkon, 905 00:49:20,760 --> 00:49:23,040 môžete skutočne robiť to sa zalomia okolo. 906 00:49:23,040 --> 00:49:28,810 >> OK, tak jeden thing-- oh, to je hrozné krieda. 907 00:49:28,810 --> 00:49:31,815 Jedna vec, aby zvážila, je to tak. 908 00:49:31,815 --> 00:49:35,514 909 00:49:35,514 --> 00:49:37,140 Budeme jednoducho päť. 910 00:49:37,140 --> 00:49:41,810 OK, takže budeme tvrdí, že hlava je tu. 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, veci v nich. 913 00:49:54,210 --> 00:49:58,340 A chceme pridať niečo, že jo? 914 00:49:58,340 --> 00:50:01,170 Takže to, čo potrebujeme viem, je, že hlava je vždy 915 00:50:01,170 --> 00:50:05,620 bude sa pohybovať sem a potom spätnej slučky okolo, OK? 916 00:50:05,620 --> 00:50:10,190 >> Tak toto front má priestor, nie? 917 00:50:10,190 --> 00:50:13,950 Má priestor na samom počiatku, druh opak toho. 918 00:50:13,950 --> 00:50:17,920 Takže to, čo musíme urobiť, je, že sme je potrebné vypočítať chvost. 919 00:50:17,920 --> 00:50:20,530 Ak viete, že vaše hlava nepohybuje, chvost 920 00:50:20,530 --> 00:50:24,630 je len vaša poľa na index veľkosti. 921 00:50:24,630 --> 00:50:30,000 >> Ale v skutočnosti, ak používate front, vaša hlava je pravdepodobne aktualizovaný. 922 00:50:30,000 --> 00:50:33,890 Takže to, čo musíte urobiť, je vlastne výpočet chvost. 923 00:50:33,890 --> 00:50:39,990 Takže to, čo robíme, je to vzorec tú, ktorú som ťa nechať 924 00:50:39,990 --> 00:50:42,680 vy myslíte o, a potom budeme o tom hovoriť. 925 00:50:42,680 --> 00:50:49,567 926 00:50:49,567 --> 00:50:50,400 Tak toto je kapacita. 927 00:50:50,400 --> 00:50:55,890 928 00:50:55,890 --> 00:50:59,660 >> Takže to bude v skutočnosti vám, ako to urobiť. 929 00:50:59,660 --> 00:51:03,205 930 00:51:03,205 --> 00:51:04,330 Pretože v tomto prípade, čo? 931 00:51:04,330 --> 00:51:09,205 Naša hlava je na 1, naša veľkosť je 4. 932 00:51:09,205 --> 00:51:11,760 933 00:51:11,760 --> 00:51:18,490 Ak by sme mod, že 5, dostaneme 0, čo je miesto, kde by sme mali vstup za to. 934 00:51:18,490 --> 00:51:23,320 935 00:51:23,320 --> 00:51:26,080 >> A tak v ďalšom prípade, keby sme k tomu, 936 00:51:26,080 --> 00:51:33,390 hovoríme, OK, poďme dequeue niečo. 937 00:51:33,390 --> 00:51:34,390 Sme dequeue to. 938 00:51:34,390 --> 00:51:37,740 Berieme sa tento prvok, je to tak? 939 00:51:37,740 --> 00:51:47,930 >> A teraz naša hlava smeruje tu a chceme pridať ďalšie veci. 940 00:51:47,930 --> 00:51:52,470 To je v podstate späť na našej línii, nie? 941 00:51:52,470 --> 00:51:55,450 Fronty môžu obaliť okolo poľa. 942 00:51:55,450 --> 00:51:57,310 To je jeden z hlavných rozdielov. 943 00:51:57,310 --> 00:51:58,780 Komíny, môžete to urobiť. 944 00:51:58,780 --> 00:52:01,140 >> S front, môžete pretože všetko, na čom záleží 945 00:52:01,140 --> 00:52:03,940 je to, že viete, čo bol naposledy pridaný. 946 00:52:03,940 --> 00:52:10,650 Vzhľadom k tomu, všetko sa bude pridaný do Tento doľava smer, v tomto prípade, 947 00:52:10,650 --> 00:52:16,480 a potom zabaliť okolo, môžete pokračovať v zavádzaní nových prvkov 948 00:52:16,480 --> 00:52:18,830 v prednej časti poľa pretože to nie je naozaj 949 00:52:18,830 --> 00:52:20,640 predné poľa už. 950 00:52:20,640 --> 00:52:26,320 Môžete myslieť na začiatku pole ako, kde sa vaša hlava je v skutočnosti. 951 00:52:26,320 --> 00:52:29,710 >> Takže tento vzorec je, ako môžete vypočítať chvost. 952 00:52:29,710 --> 00:52:32,780 953 00:52:32,780 --> 00:52:35,610 Má to zmysel? 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 potom vy máte 10 minút 957 00:52:44,040 --> 00:52:48,840 aby sa ma nejaké objasňovať otázky Chcete, pretože viem, že je to šialené. 958 00:52:48,840 --> 00:52:51,980 >> V poriadku, takže v rovnakom way-- Ja neviem, či si chlapci všimli, 959 00:52:51,980 --> 00:52:53,450 ale SK je o vzory. 960 00:52:53,450 --> 00:52:57,370 Veci sú do značnej miery To isté, len s malými vylepší. 961 00:52:57,370 --> 00:52:58,950 Tak to isté tu. 962 00:52:58,950 --> 00:53:04,040 Musíme zistiť, či je skutočne mať niečo v našej fronte, nie? 963 00:53:04,040 --> 00:53:05,960 Povedať, OK, je naša veľkosť väčšia ako 0? 964 00:53:05,960 --> 00:53:06,730 V pohode. 965 00:53:06,730 --> 00:53:10,690 >> Ak sa tak stane, potom sa presunieme našu hlavu, ktorá je to, čo som tu práve preukázal. 966 00:53:10,690 --> 00:53:13,870 Aktualizujeme našu hlavu, aby sa ešte raz. 967 00:53:13,870 --> 00:53:18,390 A potom sme decrement naše Veľkosť a vráti prvok. 968 00:53:18,390 --> 00:53:21,000 969 00:53:21,000 --> 00:53:26,250 >> Tam je oveľa konkrétnejšie kód na study.cs50.net, 970 00:53:26,250 --> 00:53:29,440 a vrelo odporúčam ísť cez to, ak budete mať čas, 971 00:53:29,440 --> 00:53:30,980 aj keď je to len pseudo-kódu. 972 00:53:30,980 --> 00:53:35,980 A ak vy chcete hovoriť cez že so mnou jeden na jedného, ​​dajte mi prosím 973 00:53:35,980 --> 00:53:37,500 vedieť. 974 00:53:37,500 --> 00:53:38,770 Ja by som rád. 975 00:53:38,770 --> 00:53:42,720 Dátové štruktúry, ak budete mať CS 124, budete 976 00:53:42,720 --> 00:53:47,830 viem, že dátové štruktúry dostať veľmi sranda, a to je len začiatok. 977 00:53:47,830 --> 00:53:50,350 >> Takže viem, že je to ťažké. 978 00:53:50,350 --> 00:53:51,300 To je v poriadku. 979 00:53:51,300 --> 00:53:52,410 Bojujeme. 980 00:53:52,410 --> 00:53:53,630 Stále robím. 981 00:53:53,630 --> 00:53:56,660 Takže sa nemusíte príliš starať o to. 982 00:53:56,660 --> 00:54:02,390 >> Ale to je v podstate Vašimi rýchlokurz v dátových štruktúrach. 983 00:54:02,390 --> 00:54:03,400 Viem, že je to veľa. 984 00:54:03,400 --> 00:54:06,860 Je tu niečo, čo nám by som ísť znova? 985 00:54:06,860 --> 00:54:09,400 Čokoľvek chceme prebrať? 986 00:54:09,400 --> 00:54:10,060 Áno? 987 00:54:10,060 --> 00:54:16,525 >> Divákov: Pre tento príklad, tak nový chvost je na 0 cez to? 988 00:54:16,525 --> 00:54:17,150 SPEAKER 1: Áno. 989 00:54:17,150 --> 00:54:18,230 Divákov: OK. 990 00:54:18,230 --> 00:54:24,220 Takže prechádza, budeš mať 1 a 4 nebo-- 991 00:54:24,220 --> 00:54:27,671 >> SPEAKER 1: Takže ste hovorila, keď chceme ísť to urobiť znova? 992 00:54:27,671 --> 00:54:28,296 Divákov: Jo. 993 00:54:28,296 --> 00:54:38,290 Takže ak ste sa prísť na out--, kde sú budete výpočet chvost z v tom, že? 994 00:54:38,290 --> 00:54:44,260 >> SPEAKER 1: Takže chvost Bol in-- zmenil som to. 995 00:54:44,260 --> 00:54:52,010 Takže v tomto prípade tu, to bolo polia sa pozeráme, OK? 996 00:54:52,010 --> 00:54:54,670 Takže máme veci v 1, 2, 3 a 4. 997 00:54:54,670 --> 00:55:05,850 Takže máme naša hlava je rovná 1 na tento bod, a naša veľkosť je rovná 4 998 00:55:05,850 --> 00:55:07,050 na tomto mieste, že jo? 999 00:55:07,050 --> 00:55:08,960 >> Vy všetci sa zhodujú, že je to tak? 1000 00:55:08,960 --> 00:55:14,620 Takže robíme hlavu plus veľkosť, ktorá nám dáva 5, a potom sme mod o 5. 1001 00:55:14,620 --> 00:55:20,690 Dostávame 0, čo nám hovorí, že 0 je kde je náš chvost, kde máme priestor. 1002 00:55:20,690 --> 00:55:22,010 >> Divákov: Čo je čiapka? 1003 00:55:22,010 --> 00:55:23,520 >> SPEAKER 1: kapacita. 1004 00:55:23,520 --> 00:55:24,020 Prepáčte. 1005 00:55:24,020 --> 00:55:29,640 Tak to je veľkosť vášho poľa. 1006 00:55:29,640 --> 00:55:35,210 1007 00:55:35,210 --> 00:55:36,047 Áno? 1008 00:55:36,047 --> 00:55:39,210 >> Divákov: [nepočuteľné] pred vrátime prvok? 1009 00:55:39,210 --> 00:55:46,270 >> SPEAKER 1: Takže sa pohybujeme hlavou alebo sa vrátiť v okamihu, kedy? 1010 00:55:46,270 --> 00:55:52,680 Ak teda presunúť jeden, decrement veľkosť? 1011 00:55:52,680 --> 00:55:54,150 Vydrž. 1012 00:55:54,150 --> 00:55:55,770 Rozhodne som zabudol ďalšie. 1013 00:55:55,770 --> 00:56:00,646 1014 00:56:00,646 --> 00:56:01,990 To nič. 1015 00:56:01,990 --> 00:56:04,980 Nie je iný vzorec. 1016 00:56:04,980 --> 00:56:09,980 Jo, by sa chcete vrátiť hlava a potom ju vrátiť späť. 1017 00:56:09,980 --> 00:56:13,270 >> Publikum: OK, pretože v tomto bod, hlava bola na 0, 1018 00:56:13,270 --> 00:56:18,452 a potom sa chcete vrátiť index 0 a potom sa hlava 1? 1019 00:56:18,452 --> 00:56:19,870 >> SPEAKER 1: Správne. 1020 00:56:19,870 --> 00:56:22,820 Myslím, že je tu ďalší vzorec niečo ako toto. 1021 00:56:22,820 --> 00:56:26,970 Nemám ju na vrchole mojej hlavy, ako Nechcem, aby vám ten zlý. 1022 00:56:26,970 --> 00:56:35,470 Ale myslím, že je to úplne v poriadku, aby povedzme, OK uložte túto element-- čokoľvek 1023 00:56:35,470 --> 00:56:40,759 element hlava je je-- decrement vaše veľkosť, pohybovať hlavou nad a návrat 1024 00:56:40,759 --> 00:56:41,800 čo to je element. 1025 00:56:41,800 --> 00:56:44,760 To je úplne v poriadku. 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 nie je ako most-- nie ste 1029 00:56:53,560 --> 00:56:55,740 ísť pešo odtiaľto ako, áno, ja viem pokusov. 1030 00:56:55,740 --> 00:56:56,880 Mám to všetko. 1031 00:56:56,880 --> 00:56:57,670 To je v poriadku. 1032 00:56:57,670 --> 00:57:00,200 Sľubujem. 1033 00:57:00,200 --> 00:57:05,240 Ale dátové štruktúry sú niečo, čo to trvá veľa času si zvyknúť. 1034 00:57:05,240 --> 00:57:10,010 Pravdepodobne jeden z najťažších veci, myslím, že v priebehu. 1035 00:57:10,010 --> 00:57:15,330 >> Tak to určite má opakovanie a pri pohľade at-- I 1036 00:57:15,330 --> 00:57:20,050 to naozaj neviem previazané zoznamy kým som urobil príliš veľa s nimi, 1037 00:57:20,050 --> 00:57:22,550 rovnakým spôsobom, že som to neurobil naozaj pochopiť ukazovatele 1038 00:57:22,550 --> 00:57:27,040 kým som sa musel učiť pre dvoch rokov a robiť svoje vlastné psets s ním. 1039 00:57:27,040 --> 00:57:28,990 To si vyžaduje veľa zdôraznenie a času. 1040 00:57:28,990 --> 00:57:32,600 A nakoniec, bude to trochu na tlačidlo. 1041 00:57:32,600 --> 00:57:36,320 >> Ale do tej doby, pokiaľ máte typ porozumenie na vysokej úrovni, čo 1042 00:57:36,320 --> 00:57:39,321 Tieto robiť, ich výhody a cons-- čo je to, čo 1043 00:57:39,321 --> 00:57:41,820 naozaj sa snažia zdôrazniť, najmä v úvodnej kurze. 1044 00:57:41,820 --> 00:57:45,511 Rovnako ako, prečo by sme použiť skúste cez pole? 1045 00:57:45,511 --> 00:57:48,010 Rovnako ako to, čo sú pozitíva a zápory každého z nich? 1046 00:57:48,010 --> 00:57:51,610 >> A pochopenie kompromisy Medzi každou z týchto štruktúr 1047 00:57:51,610 --> 00:57:54,910 je to, čo je oveľa dôležitejšie práve teraz. 1048 00:57:54,910 --> 00:57:58,140 Tu môže byť jeden blázon otázka alebo dva, ktoré je 1049 00:57:58,140 --> 00:58:03,710 bude vás žiadať, aby ste implementovať tlačiť alebo realizovať pop alebo zaradenie do fronty a Dequeue. 1050 00:58:03,710 --> 00:58:07,340 Avšak vo väčšine prípadov, že majú vyššiu úroveň porozumenia a viac 1051 00:58:07,340 --> 00:58:09,710 na intuitívne pochopenie je oveľa dôležitejšie, než v skutočnosti 1052 00:58:09,710 --> 00:58:11,250 budú môcť na jeho vykonanie. 1053 00:58:11,250 --> 00:58:14,880 >> To by bolo naozaj úžasné, keby ste všetci mohol ísť von a ísť realizovať vyskúšať, 1054 00:58:14,880 --> 00:58:19,720 ale chápeme, že to nemusí byť nutne najrozumnejšie vec, ktorú práve teraz. 1055 00:58:19,720 --> 00:58:23,370 Ale môžete v pset, ak chcete na, a potom budete mať prax, 1056 00:58:23,370 --> 00:58:27,200 a potom možno budete naozaj pochopiť. 1057 00:58:27,200 --> 00:58:27,940 Áno? 1058 00:58:27,940 --> 00:58:30,440 >> Publikum: OK, tak tie, ktoré sú sme chcel použiť v pset? 1059 00:58:30,440 --> 00:58:31,916 Musím použiť jeden z nich? 1060 00:58:31,916 --> 00:58:32,540 SPEAKER 1: Áno. 1061 00:58:32,540 --> 00:58:34,199 Takže máte na výber. 1062 00:58:34,199 --> 00:58:36,740 Myslím, že v tomto prípade môžeme hovoriť o pset trochu 1063 00:58:36,740 --> 00:58:40,480 pretože som bežal cez tieto. 1064 00:58:40,480 --> 00:58:47,779 Takže vo vašom pset, nemáte výber pokusov alebo hash tabuľky. 1065 00:58:47,779 --> 00:58:49,570 Niektorí ľudia sa budú snažiť a použitie bloom filtre, 1066 00:58:49,570 --> 00:58:51,840 ale tie technicky nie sú správne. 1067 00:58:51,840 --> 00:58:55,804 Vzhľadom na ich pravdepodobnostné charakter, dávajú niekedy falošne pozitívne. 1068 00:58:55,804 --> 00:58:57,095 Sú v pohode pohľad do, hoci. 1069 00:58:57,095 --> 00:58:59,030 Veľmi odporúčam hľadať na ne minimálne. 1070 00:58:59,030 --> 00:59:03,260 Ale máte možnosť voľby medzi hash tabuľky a pokus. 1071 00:59:03,260 --> 00:59:06,660 A to bude kedy vložíte do slovníka. 1072 00:59:06,660 --> 00:59:09,230 >> A budete musieť vybrať vaše hash funkcie, 1073 00:59:09,230 --> 00:59:13,420 budete musieť zvoliť, koľko lopaty máte, a to sa bude líšiť. 1074 00:59:13,420 --> 00:59:17,440 Ako keď máte viac vedierka, Možno, že to bude rýchlejšie. 1075 00:59:17,440 --> 00:59:22,790 Ale možno, že strácate Veľa priestoru, ktorý tak či onak, hoci. 1076 00:59:22,790 --> 00:59:26,320 Musíte na to prísť. 1077 00:59:26,320 --> 00:59:27,140 Mmhmm? 1078 00:59:27,140 --> 00:59:29,875 >> Divákov: Hovoril ste, že pred tým môžeme použiť aj iné hašovacej funkcie, 1079 00:59:29,875 --> 00:59:31,750 že nemusíme vytvoriť hash funkcie? 1080 00:59:31,750 --> 00:59:32,666 >> SPEAKER 1: Áno, správne. 1081 00:59:32,666 --> 00:59:38,150 Takže doslova pre hash funkciu, ako google "hash funkcie" 1082 00:59:38,150 --> 00:59:40,770 a pozrite sa na niektoré tie chladné. 1083 00:59:40,770 --> 00:59:43,250 Nie ste Očakáva sa, že stavať vlastné hash funkcie. 1084 00:59:43,250 --> 00:59:46,100 Ľudia trávia svoj práca na týchto veciach. 1085 00:59:46,100 --> 00:59:50,250 >> Takže sa nemusíte starať o budovanie svojej vlastnej. 1086 00:59:50,250 --> 00:59:53,350 Nájsť jednu on-line pre začiatok. 1087 00:59:53,350 --> 00:59:56,120 Niektoré z nich budete musieť manipulovať trochu 1088 00:59:56,120 --> 00:59:59,430 aby sa ubezpečil, návratové typy zhodovať a kto vie čo ešte, takže na začiatku, 1089 00:59:59,430 --> 01:00:02,420 Odporučil by som používať niečo rýchle, že možno práve 1090 01:00:02,420 --> 01:00:04,680 hash na prvé písmeno. 1091 01:00:04,680 --> 01:00:08,760 A potom, až budete mať, že práca, zahŕňajúce chladnejšie hash funkcie. 1092 01:00:08,760 --> 01:00:09,260 Mmhmm? 1093 01:00:09,260 --> 01:00:13,020 >> Divákov: Bude skúste byť alebo efektívne, ale len ťažšie, like-- 1094 01:00:13,020 --> 01:00:15,880 >> SPEAKER 1: Takže skúsiť, myslím, je intuitívne ťažko realizovať 1095 01:00:15,880 --> 01:00:18,310 ale je veľmi rýchly. 1096 01:00:18,310 --> 01:00:20,620 Avšak, zaberá viac miesta. 1097 01:00:20,620 --> 01:00:25,270 Opäť platí, že môžete optimalizovať obe tie rôzne spôsoby, a existujú spôsoby, ako to-- 1098 01:00:25,270 --> 01:00:26,770 Divákov: Ako sme triedi 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 ste sa stupňom normálnym spôsobom. 1101 01:00:29,164 --> 01:00:31,330 Budeš sa triedi na dizajn. 1102 01:00:31,330 --> 01:00:36,020 Podľa toho, ako to urobíte, budete chcieť, aby uistite sa, že je to tak elegantné, ako to môže byť 1103 01:00:36,020 --> 01:00:38,610 a tak účinný, ako to môže byť. 1104 01:00:38,610 --> 01:00:41,950 Ale ak sa rozhodnete vyskúšať alebo hash Tabuľka, tak dlho, ako to funguje, 1105 01:00:41,950 --> 01:00:45,350 sme radi, s tým. 1106 01:00:45,350 --> 01:00:48,370 A ak používate niečo, čo hash na prvé písmeno, to je v poriadku, 1107 01:00:48,370 --> 01:00:51,410 Trebárs ako jeho dizajnu. 1108 01:00:51,410 --> 01:00:53,410 Sme tiež dosiahnuť bod v tomto semester-- 1109 01:00:53,410 --> 01:00:55,340 Ja neviem, či vás chlapci noticed-- ak ste 1110 01:00:55,340 --> 01:00:58,780 pset stupňa klesať trochu vzhľadom k designu a ktovie čo ešte, 1111 01:00:58,780 --> 01:00:59,900 to je úplne v poriadku. 1112 01:00:59,900 --> 01:01:02,960 Začína to do bodu, kde sa vaše programy sú stále zložitejšie. 1113 01:01:02,960 --> 01:01:04,830 Existuje viac miesta môžete zlepšiť. 1114 01:01:04,830 --> 01:01:06,370 >> Takže je to úplne normálne. 1115 01:01:06,370 --> 01:01:08,810 To neznamená, že ste horšie, na vašom pset. 1116 01:01:08,810 --> 01:01:11,885 Je to len my je ťažšie na vás teraz. 1117 01:01:11,885 --> 01:01:13,732 Takže všetci cítia to. 1118 01:01:13,732 --> 01:01:14,940 Len som sa triedi všetky vaše psets. 1119 01:01:14,940 --> 01:01:16,490 Viem, že každý sa cíti to. 1120 01:01:16,490 --> 01:01:19,600 >> Takže sa nemusíte obávať, že. 1121 01:01:19,600 --> 01:01:23,580 A ak máte akékoľvek otázky týkajúce sa predchádzajúce psets alebo spôsoby, ako môžete zlepšiť, 1122 01:01:23,580 --> 01:01:27,760 Snažím sa a komentovať konkrétne miesta, ale niekedy je to neskoro 1123 01:01:27,760 --> 01:01:30,840 a ja som unavený. 1124 01:01:30,840 --> 01:01:34,885 Existujú aj iné veci, o dátové štruktúry? 1125 01:01:34,885 --> 01:01:37,510 Som si istý, že chlapci naozaj chceš hovoriť o nich už, 1126 01:01:37,510 --> 01:01:42,650 ale ak tam sú, som rád, že ísť cez ne, rovnako ako čokoľvek 1127 01:01:42,650 --> 01:01:45,580 z prednášky tento rok týždeň alebo minulý týždeň. 1128 01:01:45,580 --> 01:01:51,580 >> Viem, že minulý týždeň bol celý preskúmanie, tak Možno sme preskočil nejakú recenziu 1129 01:01:51,580 --> 01:01:54,190 z prednášky. 1130 01:01:54,190 --> 01:01:58,230 Akékoľvek ďalšie otázky môžem odpovedať? 1131 01:01:58,230 --> 01:01:59,350 OK, v poriadku. 1132 01:01:59,350 --> 01:02:02,400 No, vy dostanete sa 15 minút skôr. 1133 01:02:02,400 --> 01:02:08,370 >> Dúfam, že to bolo čiastočne užitočné aspoň a ja uvidíte chalani budúci týždeň, 1134 01:02:08,370 --> 01:02:12,150 alebo vo štvrtok úradné hodiny. 1135 01:02:12,150 --> 01:02:15,285 Existujú žiadosti o občerstvenie na budúci týždeň, to je vec? 1136 01:02:15,285 --> 01:02:17,459 Pretože som zabudol cukroví dnes. 1137 01:02:17,459 --> 01:02:19,750 A ja som priniesol cukroví posledné týždeň, ale bolo to Columbus Day, 1138 01:02:19,750 --> 01:02:25,400 tak tam bolo tak šesť ľudí, ktorí sa mal štyri vrecia cukroví pre seba. 1139 01:02:25,400 --> 01:02:28,820 Môžem priniesť starburst znova, ak sa vám páči. 1140 01:02:28,820 --> 01:02:29,580 Starburst? 1141 01:02:29,580 --> 01:02:32,250 OK, to znie dobre. 1142 01:02:32,250 --> 01:02:35,050 Majú veľký deň, chlapci. 1143 01:02:35,050 --> 01:02:39,510