1 00:00:00,000 --> 00:00:03,423 >> [Prehrávanie hudby] 2 00:00:03,423 --> 00:00:05,380 3 00:00:05,380 --> 00:00:08,210 >> ANDI PENG: Vitajte na týždeň 6 oddielu. 4 00:00:08,210 --> 00:00:11,620 Odklonili sme z nášho štandardu časť doba utorok 5 00:00:11,620 --> 00:00:14,130 popoludní na tejto krásnej nedeľné ráno. 6 00:00:14,130 --> 00:00:17,330 Ďakujem vám, že pre každého pripojil sa mi dnes, ale vážne, 7 00:00:17,330 --> 00:00:18,170 potlesk. 8 00:00:18,170 --> 00:00:20,600 >> To je dosť veľký úsilie. 9 00:00:20,600 --> 00:00:23,600 Skoro som nedostala ani práve včas, ale to bolo v poriadku. 10 00:00:23,600 --> 00:00:27,520 Takže viem, že každý z vás práve urobili to kvíz. 11 00:00:27,520 --> 00:00:30,370 Po prvé, vitajte odvrátenou stranou toho. 12 00:00:30,370 --> 00:00:32,917 >> Po druhé, budeme o tom hovoriť. 13 00:00:32,917 --> 00:00:34,000 Porozprávame sa o kvízu. 14 00:00:34,000 --> 00:00:35,700 Porozprávame sa o tom, ako robíte v triede. 15 00:00:35,700 --> 00:00:36,550 Budeš v poriadku. 16 00:00:36,550 --> 00:00:39,080 Mám svoje kvízy pre ste na konci tu, 17 00:00:39,080 --> 00:00:42,120 Takže ak si chlapci chcú, aby sa Pozrite sa na to, úplne v pohode. 18 00:00:42,120 --> 00:00:46,590 >> Tak rýchlo, ako začneme sa agenda pre dnešok je nasledujúci. 19 00:00:46,590 --> 00:00:48,430 Ako môžete vidieť, že sme v podstate rýchle paľby 20 00:00:48,430 --> 00:00:52,120 cez veľa dátových štruktúr naozaj, naozaj, naozaj rýchlo. 21 00:00:52,120 --> 00:00:54,380 Tak ako taký, to nebude Super interaktívne dnes. 22 00:00:54,380 --> 00:00:59,620 Bude to len ma trochu krik veci, ktoré vás, a keď som zmiasť, 23 00:00:59,620 --> 00:01:02,680 ak idem moc rýchlo, dajte mi vedieť. 24 00:01:02,680 --> 00:01:05,200 Sú to jednoducho rôzne údaje štruktúry, a ako súčasť 25 00:01:05,200 --> 00:01:07,070 vašej pset na to nadchádzajúci týždeň, budete 26 00:01:07,070 --> 00:01:10,340 vyzvaní na vykonanie jednej z nich, možno dve z them-- dvoch z nich 27 00:01:10,340 --> 00:01:12,319 v pset. 28 00:01:12,319 --> 00:01:14,610 OK, tak som len tak začať s niektorými oznámenia. 29 00:01:14,610 --> 00:01:19,070 Pôjdeme cez komíny a ďalšie v front hĺbka, než to, čo sme robili pred kvíz. 30 00:01:19,070 --> 00:01:20,990 Pôjdeme cez spojené Zoznam znova, ešte raz, 31 00:01:20,990 --> 00:01:23,899 viac do hĺbky, než to, čo sme mali predtým kvízu. 32 00:01:23,899 --> 00:01:26,440 A potom sa budeme baviť o hash stoly, stromy a snaží sa, ktoré 33 00:01:26,440 --> 00:01:28,890 sú všetky pekne nevyhnutné pre pset. 34 00:01:28,890 --> 00:01:32,925 A potom pôjdeme cez niektoré užitočné tipy pre pset5. 35 00:01:32,925 --> 00:01:37,360 >> OK, takže kvíz 0. 36 00:01:37,360 --> 00:01:41,090 Priemerná bol 58%. 37 00:01:41,090 --> 00:01:45,370 To bola veľmi nízka, a tak vy všetci robil veľmi, veľmi dobre v súlade 38 00:01:45,370 --> 00:01:46,510 s tým. 39 00:01:46,510 --> 00:01:49,970 >> Celkom veľa, pravidlom je, ak ste v rámci štandardnej odchýlkou ​​od priemernej hodnoty 40 00:01:49,970 --> 00:01:52,990 najmä preto, že sme v menej pohodlný úsek, ty si úplne v pohode. 41 00:01:52,990 --> 00:01:54,120 Ste na správnej ceste. 42 00:01:54,120 --> 00:01:55,190 Život je dobrý. 43 00:01:55,190 --> 00:01:58,952 >> Viem, že je to desivé si myslieť, že Dostal som sa ako 40% na tento kvíz. 44 00:01:58,952 --> 00:02:00,160 Idem na neúspech tejto triedy. 45 00:02:00,160 --> 00:02:02,243 Sľubujem vám, že nie ste bude zlyhanie triedu. 46 00:02:02,243 --> 00:02:03,680 Si úplne v pohode. 47 00:02:03,680 --> 00:02:06,850 >> Pre tých z vás, ktorí dostali viac ako stredná, impozantný, pôsobivý, 48 00:02:06,850 --> 00:02:08,780 ako, vážne dobre. 49 00:02:08,780 --> 00:02:09,689 Mám ich so sebou. 50 00:02:09,689 --> 00:02:11,730 Neváhajte a poďte si ich na konci sekcie. 51 00:02:11,730 --> 00:02:14,520 Dajte mi vedieť, ak máte nejaké problémy, otázky s nimi. 52 00:02:14,520 --> 00:02:17,204 Sčítame Ak vaše skóre zle, dajte nám vedieť. 53 00:02:17,204 --> 00:02:21,240 >> OK, takže pset5, to je v skutočnosti divný týždeň Yale v tom zmysle, 54 00:02:21,240 --> 00:02:24,240 že naše pset je kvôli V stredu na poludnie, vrátane 55 00:02:24,240 --> 00:02:27,317 neskoré deň, takže je to vlastne teoreticky kvôli utorok napoludnie. 56 00:02:27,317 --> 00:02:29,150 Asi nikto skončil v utorok napoludnie. 57 00:02:29,150 --> 00:02:30,830 To je úplne v poriadku. 58 00:02:30,830 --> 00:02:33,700 Budeme mať úradné hodiny Dnes večer rovnako ako v pondelok večer. 59 00:02:33,700 --> 00:02:36,810 A to všetko sekciách tento týždeň v skutočnosti byť otočený do dielní, 60 00:02:36,810 --> 00:02:38,800 tak neváhajte pop akákoľvek časť, ktorú chcete, 61 00:02:38,800 --> 00:02:42,810 a oni budú trochu mini-pset workshopy o pomoc na to. 62 00:02:42,810 --> 00:02:45,620 Tak ako taký, to je jediná sekcia kam máme výukový materiál. 63 00:02:45,620 --> 00:02:49,220 Všetky ostatné časti budú zameriavať výhradne na pomoc pre pset. 64 00:02:49,220 --> 00:02:50,146 Jo? 65 00:02:50,146 --> 00:02:52,000 >> Divákov: Kde sú úradné hodiny? 66 00:02:52,000 --> 00:02:56,120 >> ANDI PENG: Úradné hodiny tonight-- oh, dobrá otázka. 67 00:02:56,120 --> 00:03:00,580 Myslím si, že úradné hodiny dnes večer sú v Teal alebo na Commons. 68 00:03:00,580 --> 00:03:02,984 Ak zaškrtnete on-line CS50 a idete do úradných hodinách, 69 00:03:02,984 --> 00:03:05,650 by mal byť plán, ktorý vám povie, kde sú všetky z nich sú. 70 00:03:05,650 --> 00:03:07,954 >> Viem, že buď dnes večer alebo zajtra je modrozelený, 71 00:03:07,954 --> 00:03:10,120 a myslím, že môžeme mať commons pre druhé v noci. 72 00:03:10,120 --> 00:03:11,020 Nie som si istý. 73 00:03:11,020 --> 00:03:11,700 Dobrá otázka. 74 00:03:11,700 --> 00:03:14,430 Pozrite sa na CS50. 75 00:03:14,430 --> 00:03:18,780 >> Cool, nejaké otázky týkajúce sa harmonogram pre ďalšie ako tri dni? 76 00:03:18,780 --> 00:03:21,690 Sľubujem, že sa vám bude páčiť David povedal, to je vrchol kopca. 77 00:03:21,690 --> 00:03:23,050 Vy ste skoro tam. 78 00:03:23,050 --> 00:03:24,644 Len tri dni. 79 00:03:24,644 --> 00:03:26,310 Sa tam dostať, a potom budeme všetci zostúpi. 80 00:03:26,310 --> 00:03:28,114 Budeme mať pekný CS-voľné prestávku. 81 00:03:28,114 --> 00:03:28,780 Vrátime sa. 82 00:03:28,780 --> 00:03:30,779 Budeme ponoriť do webu programovanie a vývoj, 83 00:03:30,779 --> 00:03:35,150 veci, ktoré sú veľmi zábavné porovnanie na niektoré z ďalších psets. 84 00:03:35,150 --> 00:03:37,974 A bude to chill a budeme mať veľa zábavy. 85 00:03:37,974 --> 00:03:38,890 Budeme mať viac cukroví. 86 00:03:38,890 --> 00:03:39,730 Ospravedlňujeme sa za sladkosti. 87 00:03:39,730 --> 00:03:40,945 Zabudol som cukrovinky. 88 00:03:40,945 --> 00:03:43,310 Bolo to drsné ráno. 89 00:03:43,310 --> 00:03:46,340 Takže vy ste skoro tam, a ja som naozaj pyšný z vás. 90 00:03:46,340 --> 00:03:49,570 >> OK, tak komíny. 91 00:03:49,570 --> 00:03:53,331 Kto miluje na otázku o Jackovi a jeho oblečenie na kvíz? 92 00:03:53,331 --> 00:03:53,830 Nikto? 93 00:03:53,830 --> 00:03:56,500 OK, to je v poriadku. 94 00:03:56,500 --> 00:04:00,200 >> Takže v podstate, ako môžete obrázok Jack, tento chlapík tu, 95 00:04:00,200 --> 00:04:03,350 miluje vziať oblečenie z vrcholu zásobníku, 96 00:04:03,350 --> 00:04:05,750 a on hovorí späť na zásobníka potom, čo urobil. 97 00:04:05,750 --> 00:04:07,600 Takže týmto spôsobom, nikdy sa zdá byť stále 98 00:04:07,600 --> 00:04:10,090 do spodnej časti zásobník v jeho oblečení. 99 00:04:10,090 --> 00:04:12,600 Takže tento druh popisuje základná štruktúra dát 100 00:04:12,600 --> 00:04:16,610 o tom, ako je implementovaná zásobník. 101 00:04:16,610 --> 00:04:20,060 >> V podstate, myslieť na stack ako každý stoh objektov 102 00:04:20,060 --> 00:04:24,900 kam dať veci na vrchol, a potom vyskočí von z vrcholu. 103 00:04:24,900 --> 00:04:28,600 Takže LIFO je skratka máme radi na use-- posledný dnu, prvý von. 104 00:04:28,600 --> 00:04:32,480 A tak posledný sa do hornej časti stack je prvý, ktorý vyjde. 105 00:04:32,480 --> 00:04:34,260 A tak sa dva termíny chceme priradiť 106 00:04:34,260 --> 00:04:36,190 S tým sa nazývajú tlak a pop. 107 00:04:36,190 --> 00:04:39,790 Keď budete tlačiť niečo Na stack, a ty to pop späť hore. 108 00:04:39,790 --> 00:04:43,422 >> A tak myslím, že to je tak trochu abstraktný pojem pre tých z vás, 109 00:04:43,422 --> 00:04:45,630 ktorí chcú vidieť ako skutočnom vykonávaní tohto 110 00:04:45,630 --> 00:04:46,740 v reálnom svete. 111 00:04:46,740 --> 00:04:50,170 Ako mnohí z vás písali esej Možno ako hodiny, než to bolo spôsobené, 112 00:04:50,170 --> 00:04:54,510 a vy omylom zmazané obrovský kus z toho, ako náhodou? 113 00:04:54,510 --> 00:04:58,560 A čo potom kontrola robiť používame, aby ju späť? 114 00:04:58,560 --> 00:05:00,030 Riadenie-Z, jo? 115 00:05:00,030 --> 00:05:03,640 Control-Z, takže množstvo časov že Control-Z mi zachránil život, 116 00:05:03,640 --> 00:05:08,820 mi zachránil zadok, zakaždým ktorá je vykonávaná prostredníctvom zásobníka. 117 00:05:08,820 --> 00:05:13,020 >> V podstate všetky informácie že je na vašom dokumente programu Word, 118 00:05:13,020 --> 00:05:15,080 dostane tlačil a vyskočila na želanie. 119 00:05:15,080 --> 00:05:19,460 A tak sa v podstate vždy, keď vás vymazať všetko, čo si len pop naspäť hore. 120 00:05:19,460 --> 00:05:22,820 A potom, ak ju budete potrebovať znova zapnete, vás zatlačte ju, čo je to, čo Control-C robí. 121 00:05:22,820 --> 00:05:26,770 A tak skutočné funkcie svet o tom, ako jednoduché dátové štruktúry 122 00:05:26,770 --> 00:05:28,690 môžu pomôcť s vašou každodenný život. 123 00:05:28,690 --> 00:05:31,710 124 00:05:31,710 --> 00:05:40,150 >> Takže struct je cesta, ktorá sme vlastne vytvoriť zásobník. 125 00:05:40,150 --> 00:05:44,720 My typ definovať struct, a potom hovoríme, že zásobník na dne. 126 00:05:44,720 --> 00:05:47,440 A v rámci stohu, máme dva parametre 127 00:05:47,440 --> 00:05:51,580 že môže byť v podstate manipulovať, takže máme char hviezdy reťazcov kapacitu. 128 00:05:51,580 --> 00:05:55,150 >> Všetko, čo je robí je vytvorenie poľa 129 00:05:55,150 --> 00:05:58,835 že môžeme ukladať, čo chcete ktoré môžeme určiť jeho kapacitu. 130 00:05:58,835 --> 00:06:01,990 Kapacita je len maximálne množstvo položky môžeme dať do tohto poľa. 131 00:06:01,990 --> 00:06:05,660 veľkosť int je čítač, ktorý udržuje Trať o tom, ako mnohých položiek sú v súčasnej dobe 132 00:06:05,660 --> 00:06:07,850 v stohu. 133 00:06:07,850 --> 00:06:11,860 Takže potom môžeme sledovať, A, oboch, ako veľký skutočné stack je, 134 00:06:11,860 --> 00:06:14,850 a, B, koľko z tohto stohu sme naplnili pretože nechceme 135 00:06:14,850 --> 00:06:18,800 pretečeniu nad tým, čo naša kapacita je. 136 00:06:18,800 --> 00:06:24,340 >> Tak napríklad, tento krásny Otázka bola na kvíz. 137 00:06:24,340 --> 00:06:28,160 V podstate, ako máme tlačiť na hornej časti zásobníka. 138 00:06:28,160 --> 00:06:28,830 Celkom jednoduché. 139 00:06:28,830 --> 00:06:30,621 Keď sa pozriete na to, prejdeme to. 140 00:06:30,621 --> 00:06:32,640 Ak [nepočuteľných] size-- pamätajte, kedykoľvek budete 141 00:06:32,640 --> 00:06:35,300 chcú pristupovať k akýmkoľvek parameter v struct, 142 00:06:35,300 --> 00:06:40,320 robíte názov struct.parameter. 143 00:06:40,320 --> 00:06:42,720 >> V tomto prípade, s je meno našej zásobníka. 144 00:06:42,720 --> 00:06:46,230 Chceme, aby prístup k veľkosti z toho, takže robíme s.size. 145 00:06:46,230 --> 00:06:50,280 Tak, ak je veľkosť nie je rovnajúcu sa kapacity alebo tak dlho, 146 00:06:50,280 --> 00:06:52,940 ako je to menej ako kapacita, buď bude pracovať. 147 00:06:52,940 --> 00:06:57,180 >> Ak chcete získať prístup dovnútra vášho stacku, tak s.strings, 148 00:06:57,180 --> 00:07:00,790 a budete dal, že nové číslo ktoré chcete vložiť do tam. 149 00:07:00,790 --> 00:07:05,030 Povedzme, že budeme chcieť vložiť int n do zásobníka, 150 00:07:05,030 --> 00:07:08,905 by sme mohli urobiť s.strings, držiaky, s.size rovná n. 151 00:07:08,905 --> 00:07:11,030 Vzhľadom k tomu, veľkosť je miesto, kde sme V súčasnej dobe je v balíčku 152 00:07:11,030 --> 00:07:14,590 ak budeme tlačiť to ďalej, len sme prístup 153 00:07:14,590 --> 00:07:17,370 všade tam, kde je veľkosť, tým prúd plnosť zásobníku, 154 00:07:17,370 --> 00:07:21,729 a presunieme int n na neho. 155 00:07:21,729 --> 00:07:24,770 A potom chceme, aby sa uistil, že sme tiež zvyšovanie veľkosti n, 156 00:07:24,770 --> 00:07:27,436 takže môžeme sledovať máme pridal ďalšie vec, do stohu. 157 00:07:27,436 --> 00:07:29,660 Teraz máme väčšiu veľkosť. 158 00:07:29,660 --> 00:07:33,196 Znamená to tu zmysel všetci, ako logicky to funguje? 159 00:07:33,196 --> 00:07:34,160 Bolo to trochu rýchlo. 160 00:07:34,160 --> 00:07:39,535 161 00:07:39,535 --> 00:07:42,160 Divákov: Môžeš ísť cez sa s.stringss.strings [s.size] znova? 162 00:07:42,160 --> 00:07:45,808 ANDI PENG: Jasné, takže to, čo robí s.size v súčasnej dobe dať nám? 163 00:07:45,808 --> 00:07:47,440 Divákov: Je to aktuálnu veľkosť. 164 00:07:47,440 --> 00:07:50,890 ANDI PENG: Presne, takže Súčasný index, že naša veľkosť je, 165 00:07:50,890 --> 00:07:57,780 a tak chceme, aby sa nové číslo že chceme vložiť do s.size. 166 00:07:57,780 --> 00:07:58,760 Dáva to zmysel? 167 00:07:58,760 --> 00:08:01,110 Vzhľadom k tomu, s.strings, všetko, čo je je názov poľa. 168 00:08:01,110 --> 00:08:03,510 Všetko, čo to je, je prístupom do array v našom struct, 169 00:08:03,510 --> 00:08:06,030 a tak ak chceme miesto n do tohto indexu, 170 00:08:06,030 --> 00:08:09,651 môžeme len pristupovať pomocou konzoly s.size. 171 00:08:09,651 --> 00:08:10,150 Super. 172 00:08:10,150 --> 00:08:13,580 173 00:08:13,580 --> 00:08:18,916 >> Dobre, pop, pseudokód som to pre vás, ale podobným konceptom. 174 00:08:18,916 --> 00:08:19,790 Dáva to zmysel? 175 00:08:19,790 --> 00:08:22,310 Ak je veľkosť je väčšia ako nula, potom sa 176 00:08:22,310 --> 00:08:25,350 viete, že chcete, aby sa niečo , Pretože v prípade, že veľkosť nie je 177 00:08:25,350 --> 00:08:27,620 väčšie ako nula, potom sa nemá nič v zásobníku. 178 00:08:27,620 --> 00:08:29,840 >> Takže si len chcete spustiť tento kód, len to môže 179 00:08:29,840 --> 00:08:32,320 pop ak je niečo pop. 180 00:08:32,320 --> 00:08:35,830 Takže, ak je veľkosť je väčšia ako 0, sme mínus veľkosť. 181 00:08:35,830 --> 00:08:40,020 Decrement sme veľkosť a potom sa vrátiť čo je vo vnútri, pretože 182 00:08:40,020 --> 00:08:42,710 praskanie, chceme Prístup, čo je uložené 183 00:08:42,710 --> 00:08:45,694 v indexe vrcholu zásobníku. 184 00:08:45,694 --> 00:08:46,610 Všetko, čo zmysel? 185 00:08:46,610 --> 00:08:49,693 Keby som ťa chlapci písať na to, by vy môcť písať to? 186 00:08:49,693 --> 00:08:52,029 187 00:08:52,029 --> 00:08:53,570 OK, vy môžete hrať sa s ním. 188 00:08:53,570 --> 00:08:55,252 Žiadne starosti, ak nechcete dostať to. 189 00:08:55,252 --> 00:08:57,460 Nemáme čas na kód it out dnes, pretože máme 190 00:08:57,460 --> 00:08:59,959 mám veľa týchto štruktúr prejsť, ale v zásade 191 00:08:59,959 --> 00:09:02,214 pseudokód, veľmi, veľmi podobné, aby sa zasadila. 192 00:09:02,214 --> 00:09:03,380 Stačí sledovať spolu logiky. 193 00:09:03,380 --> 00:09:06,092 Uistite sa, že máte prístup všetky vlastnosti vášho struct správne. 194 00:09:06,092 --> 00:09:06,574 Jo? 195 00:09:06,574 --> 00:09:09,282 >> Divákov: budú tieto snímky a Celá táto vec byť až dnes ish? 196 00:09:09,282 --> 00:09:11,586 ANDI PENG: Vždy, jo. 197 00:09:11,586 --> 00:09:13,710 Budem sa snažiť dať toto hore ako hodinu potom. 198 00:09:13,710 --> 00:09:16,626 Budem email Davida, sa bude snažiť David dal ju ako hodinu po tejto. 199 00:09:16,626 --> 00:09:20,040 200 00:09:20,040 --> 00:09:25,470 >> OK, takže potom sme sa presťahovať do tá druhá pôvabný dátová štruktúra volal fronty. 201 00:09:25,470 --> 00:09:30,140 Ako vy môžete vidieť tu, je front, pre Britov medzi nami, 202 00:09:30,140 --> 00:09:32,010 všetko, čo je, je rad. 203 00:09:32,010 --> 00:09:34,680 Takže na rozdiel od toho, čo si myslíte, že zásobník je, 204 00:09:34,680 --> 00:09:37,750 front je presne to, čo logicky si myslíte, že je. 205 00:09:37,750 --> 00:09:41,914 Je držaný pravidiel FIFO, čo je prvý dovnútra, prvý von. 206 00:09:41,914 --> 00:09:43,705 Ak ste prvý raz v rade, ste 207 00:09:43,705 --> 00:09:46,230 prvý, ktorý vychádza z rady. 208 00:09:46,230 --> 00:09:49,680 >> Takže to, čo sme chceli volať toto je dequeueing a enqueueing. 209 00:09:49,680 --> 00:09:52,380 Ak chceme pridať niečo k našej fronte, my Zaradí. 210 00:09:52,380 --> 00:09:55,690 Ak chceme, aby dequeue, alebo sa niečo preč, my dequeue. 211 00:09:55,690 --> 00:10:03,350 >> Takže rovnaký pocit, že sme trochu vytvorenie pevnej veľkosti prvkov, ktoré sme 212 00:10:03,350 --> 00:10:06,500 je možné uložiť isté veci, ale môžeme tiež 213 00:10:06,500 --> 00:10:10,100 zmeniť miesto, kde sme umiestnením Parametre vnútri nich 214 00:10:10,100 --> 00:10:13,140 založené na tom, aký typ funkčnosť chceme. 215 00:10:13,140 --> 00:10:16,700 Takže komíny, chceli sme posledný jedným, N, že je prvý von. 216 00:10:16,700 --> 00:10:19,800 Fronta je chceme prvá vec, V byť prvá vec von. 217 00:10:19,800 --> 00:10:22,510 218 00:10:22,510 --> 00:10:26,710 >> Takže struct typu definovať, ako môžete vidieť, 219 00:10:26,710 --> 00:10:29,470 je to trochu inak z toho, čo bolo stack 220 00:10:29,470 --> 00:10:33,120 pretože nielen že sa musíme držať trať, kde v súčasnosti je veľkosť, 221 00:10:33,120 --> 00:10:37,420 tiež chceme sledovať hlavy rovnako ako, kde sme v súčasnej dobe sú. 222 00:10:37,420 --> 00:10:39,580 Takže si myslím, že je jednoduchšie ak kreslím to. 223 00:10:39,580 --> 00:10:53,270 Takže poďme si predstaviť, že máme front, takže povedzme, že hlava je tu. 224 00:10:53,270 --> 00:10:55,811 225 00:10:55,811 --> 00:10:58,310 V čele linky, poďme len povedať, že je to v súčasnej dobe, 226 00:10:58,310 --> 00:11:01,809 a chceme vložiť niečo, čo sa do fronty. 227 00:11:01,809 --> 00:11:04,350 Chystám sa zavolať veľkosti v podstate je to isté ako chvost, 228 00:11:04,350 --> 00:11:06,314 koniec všade tam, kde je vaša front. 229 00:11:06,314 --> 00:11:07,730 Povedzme, že veľkosť je práve tu. 230 00:11:07,730 --> 00:11:14,380 231 00:11:14,380 --> 00:11:18,400 >> Tak ako sa dá reálne vložiť niečo do fronty? 232 00:11:18,400 --> 00:11:21,000 233 00:11:21,000 --> 00:11:24,130 Čo index chceme umiestniť kam chceme vložiť do. 234 00:11:24,130 --> 00:11:29,320 Ak je to na začiatku svojho fronty a to je jej koniec 235 00:11:29,320 --> 00:11:31,860 alebo veľkosť tom, kde my chcete pridať ďalší objekt? 236 00:11:31,860 --> 00:11:32,920 >> Divákov: [Nepočuteľné] 237 00:11:32,920 --> 00:11:35,920 ANDI PENG: Presne tak, chcete pridať to v závislosti na ste to napísal. 238 00:11:35,920 --> 00:11:37,840 Buď je to prázdne, alebo že je prázdna. 239 00:11:37,840 --> 00:11:42,630 Takže chcete, aby ho pridať pravdepodobne tu, pretože v prípade, že veľkosť je-- 240 00:11:42,630 --> 00:11:50,540 ak sú všetky plné, chcete pridať tu, nie? 241 00:11:50,540 --> 00:11:57,150 >> A tak to je, keď veľmi, veľmi jednoduché, nie celkom vždy správne 242 00:11:57,150 --> 00:12:00,690 preto, že hlavný rozdiel medzi fronty a zásobníka 243 00:12:00,690 --> 00:12:04,350 je to, že sa front môže vlastne byť vykonávaný 244 00:12:04,350 --> 00:12:06,980 tak, že zmeny hlavové V závislosti na tom, kde chcete 245 00:12:06,980 --> 00:12:08,650 začiatok vašej povel k štartu. 246 00:12:08,650 --> 00:12:11,900 A ako výsledok, vaše chvost je tiež zmení. 247 00:12:11,900 --> 00:12:14,770 A tak sa pozrieť na Tento kód práve teraz. 248 00:12:14,770 --> 00:12:18,620 Ako vy ste boli požiadaní, aby vypísať na kvíz, Enqueue. 249 00:12:18,620 --> 00:12:22,580 Možno, že budeme hovoriť cez prečo odpoveď bola, čo to bolo. 250 00:12:22,580 --> 00:12:26,790 >> Nemohol som úplne fit tento riadok na jednom, ale v podstate tento kus kódu 251 00:12:26,790 --> 00:12:29,030 by mal byť na jednom riadku. 252 00:12:29,030 --> 00:12:30,140 Stráviť ako 30 sekúnd. 253 00:12:30,140 --> 00:12:33,000 Pozrite sa, a uvidíte, prečo to je tak, že to je. 254 00:12:33,000 --> 00:12:50,030 255 00:12:50,030 --> 00:12:55,420 >> Veľmi, veľmi podobný struct, veľmi, veľmi podobnej štruktúre ako pri predchádzajúcej 256 00:12:55,420 --> 00:12:58,090 stack s výnimkou snáď jeden riadok kódu. 257 00:12:58,090 --> 00:13:01,190 A že jeden riadok kódu určuje funkcie. 258 00:13:01,190 --> 00:13:03,900 A je to naozaj odlišuje fronty z komína. 259 00:13:03,900 --> 00:13:18,510 260 00:13:18,510 --> 00:13:22,010 >> Každý, kto chcú, aby sa stab vysvetliť, prečo nemáš 261 00:13:22,010 --> 00:13:24,980 dostal túto komplikovanú vec tu? 262 00:13:24,980 --> 00:13:27,845 Vidíme návrat nášho báječný kamarát modul. 263 00:13:27,845 --> 00:13:31,020 Ako vy čoskoro príde uznať v programovaní, 264 00:13:31,020 --> 00:13:34,910 takmer kedykoľvek budete potrebovať niečo zabaliť okolo čokoľvek, 265 00:13:34,910 --> 00:13:36,850 modul bude spôsob, ako to urobiť. 266 00:13:36,850 --> 00:13:40,510 Tak s vedomím, že niekto chce aby sa pokúsili vysvetliť tento riadok kódu? 267 00:13:40,510 --> 00:13:44,060 268 00:13:44,060 --> 00:13:47,507 Jo, sú všetky odpovede prijatí a vítaní. 269 00:13:47,507 --> 00:13:48,840 Divákov: Hovoríš so mnou? 270 00:13:48,840 --> 00:13:49,506 ANDI PENG: Jo. 271 00:13:49,506 --> 00:13:56,200 Publikum: Oh, nie ľúto. 272 00:13:56,200 --> 00:14:00,250 ANDI PENG: OK, tak sa poďme prejsť týmto kódom. 273 00:14:00,250 --> 00:14:03,642 Takže, keď sa snažíte pridať niečo na fronte, 274 00:14:03,642 --> 00:14:08,510 v krásnom prípade, že hlava sa stane byť tu, je to pre nás veľmi ľahké 275 00:14:08,510 --> 00:14:10,960 jednoducho ísť až do konca vložiť niečo, nie? 276 00:14:10,960 --> 00:14:14,690 Ale celý bod na fronte že hlava môže skutočne dynamicky 277 00:14:14,690 --> 00:14:17,280 mení v závislosti na tom, kde sme Chcete začiatku našej q byť, 278 00:14:17,280 --> 00:14:19,880 a ako taký, chvosta je tiež zmení. 279 00:14:19,880 --> 00:14:31,100 >> A tak si predstaviť, že to nie je fronty, ale skôr je to frontu. 280 00:14:31,100 --> 00:14:37,900 281 00:14:37,900 --> 00:14:39,330 Povedzme, že hlava je tu. 282 00:14:39,330 --> 00:14:54,900 283 00:14:54,900 --> 00:14:56,980 Povedzme, že naše front vyzerala takto. 284 00:14:56,980 --> 00:15:00,190 Ak by sme chceli posunúť kde na začiatku linky je, 285 00:15:00,190 --> 00:15:03,400 povedzme, že sme sa posunul hlavou Týmto spôsobom a tu veľkosti. 286 00:15:03,400 --> 00:15:07,100 >> Teraz chceme niečo pridať Táto fronta, ale ako vy môžete vidieť, 287 00:15:07,100 --> 00:15:11,150 to nie je tak jednoduché, ako len pridať to, čo je za veľkosťou 288 00:15:11,150 --> 00:15:13,630 pretože potom dôjdu medze našej aktuálnej poľa. 289 00:15:13,630 --> 00:15:16,190 Kam chceme naozaj pridať je tu. 290 00:15:16,190 --> 00:15:18,610 To je krása fronty je to, že pre nás, vizuálne 291 00:15:18,610 --> 00:15:22,380 vyzerá ako linka ide takto, ale ak sú uložené v dátovej štruktúre, 292 00:15:22,380 --> 00:15:29,370 dávajú to ako ako cyklus. 293 00:15:29,370 --> 00:15:32,360 Je to druh obaľuje na prednej strane rovnaký spôsobom 294 00:15:32,360 --> 00:15:34,780 že vedenie môže tiež zábal okolo závisí na všade tam, kde vás 295 00:15:34,780 --> 00:15:36,279 chcú začiatku riadku byť. 296 00:15:36,279 --> 00:15:38,630 A tak ak budeme trvať pozrite sa sem dole, poďme 297 00:15:38,630 --> 00:15:40,880 že sme chceli vytvoriť Funkcia tzv čakací. 298 00:15:40,880 --> 00:15:43,980 Chceli sme pridať int n do tohto q. 299 00:15:43,980 --> 00:15:49,250 Ak q.size q-- budeme hovoriť, že naše dáta structure-- keď náš queue.size nie je 300 00:15:49,250 --> 00:15:52,520 sa rovná kapacity, alebo ak je to menej ako kapacita, 301 00:15:52,520 --> 00:15:55,120 q.strings je pole v našom q. 302 00:15:55,120 --> 00:15:58,380 Budeme nastaviť rovnajúcu sa q.heads, 303 00:15:58,380 --> 00:16:02,730 ktorý je tu, a navyše q.size modul kapacitou, ktorý 304 00:16:02,730 --> 00:16:04,290 zábal nás naspäť tu. 305 00:16:04,290 --> 00:16:08,040 >> Takže v tomto príklade, index hlavy je 1, že jo? 306 00:16:08,040 --> 00:16:11,480 Index veľkosti je 0, 1, 2, 3, 4. 307 00:16:11,480 --> 00:16:19,500 Takže môžeme urobiť 1 plus 4 modul našej kapacity, ktorá je 5. 308 00:16:19,500 --> 00:16:20,920 Čo, že nám dá? 309 00:16:20,920 --> 00:16:23,270 Čo je index, ktorý vychádza z toho? 310 00:16:23,270 --> 00:16:24,080 >> Divákov: 0. 311 00:16:24,080 --> 00:16:27,870 >> ANDI PENG: 0, čo sa stane byť tu, 312 00:16:27,870 --> 00:16:30,640 a tak chceme byť schopní vložiť do práve tu. 313 00:16:30,640 --> 00:16:34,730 A tak táto rovnica tu druh z práve pracuje s číslami 314 00:16:34,730 --> 00:16:36,750 V závislosti na tom, kde vaše hlava a vaše veľkosť sú. 315 00:16:36,750 --> 00:16:38,541 Ak viete, čo tie, veci sú, viete, 316 00:16:38,541 --> 00:16:43,170 presne tam, kde chcete vložiť čo je po vašom frontu. 317 00:16:43,170 --> 00:16:44,640 Znamená to, že zmysel pre všetkých? 318 00:16:44,640 --> 00:16:48,560 >> Viem, že akýsi mozgu teaser najmä preto, že 319 00:16:48,560 --> 00:16:50,512 prišiel v dôsledku vášho kvíz. 320 00:16:50,512 --> 00:16:52,220 Ale dúfajme, že všetci Teraz môžete pochopiť, 321 00:16:52,220 --> 00:16:57,800 prečo toto riešenie, alebo to Funkcia je tak, že to je. 322 00:16:57,800 --> 00:16:59,840 Každý, kto trochu nejasné na to? 323 00:16:59,840 --> 00:17:03,471 324 00:17:03,471 --> 00:17:03,970 OK. 325 00:17:03,970 --> 00:17:07,109 326 00:17:07,109 --> 00:17:09,970 >> A tak teraz, ak ste chcel dequeue, to 327 00:17:09,970 --> 00:17:15,240 je miesto, kde by naša hlava sa presúva pretože ak by sme mali dequeue, 328 00:17:15,240 --> 00:17:17,030 neberieme z konca q. 329 00:17:17,030 --> 00:17:19,130 Chceme, aby sa z hlavy, že jo? 330 00:17:19,130 --> 00:17:24,260 Takže v dôsledku toho hlava sa zmení, a to je dôvod, prečo, keď sa Zaradí, 331 00:17:24,260 --> 00:17:26,800 musíš sledovať kde sa vaša hlava a vaše veľkosť 332 00:17:26,800 --> 00:17:29,450 sú, aby bolo možné vložiť do správnej polohy. 333 00:17:29,450 --> 00:17:32,740 >> A tak keď sa dequeue, Tiež som pseudokód to. 334 00:17:32,740 --> 00:17:35,480 Neváhajte a ak chcete, pokúsiť kódovanie to. 335 00:17:35,480 --> 00:17:36,980 Chcete presunúť hlavu, nie? 336 00:17:36,980 --> 00:17:39,320 Keby som chcel dequeue, I by sa posunúť hlavu nad. 337 00:17:39,320 --> 00:17:40,800 To by byť hlava. 338 00:17:40,800 --> 00:17:45,617 >> A náš súčasný veľkosť by odčítanie, pretože už nie je 339 00:17:45,617 --> 00:17:46,950 majú štyri prvky v poli. 340 00:17:46,950 --> 00:17:51,370 Máme len tri, a potom chceme vrátiť, čo bol uložený vo vnútri 341 00:17:51,370 --> 00:17:56,260 hlavy, pretože chceme, aby sa tento hodnota sa tak veľmi podobný zásobníku. 342 00:17:56,260 --> 00:17:58,010 Len ste pri z iného miesta, 343 00:17:58,010 --> 00:18:01,770 a vy budete musieť priradiť svoju ukazovateľ na inom mieste ako výsledok. 344 00:18:01,770 --> 00:18:03,890 Logicky, každý nasledovať? 345 00:18:03,890 --> 00:18:05,690 Skvelé. 346 00:18:05,690 --> 00:18:10,156 >> OK, takže budeme hovoriť trochu viac do hĺbky asi spojových zoznamoch 347 00:18:10,156 --> 00:18:13,280 pretože bude veľmi, veľmi cenná pre vás v priebehu roka tento týždeň 348 00:18:13,280 --> 00:18:14,964 psets. 349 00:18:14,964 --> 00:18:17,130 Spojové zoznamy, ako ste chlapci Pamätám si, všetko, čo sú 350 00:18:17,130 --> 00:18:22,570 sú uzly, ktoré sú uzly isté Hodnoty oboch hodnotu a ukazovateľ 351 00:18:22,570 --> 00:18:26,290 , Ktoré sú spojené dohromady týmito ukazovateľmi. 352 00:18:26,290 --> 00:18:29,880 A tak sa na to, ako struct sme sa vytvoriť uzol tu je, že sme 353 00:18:29,880 --> 00:18:33,569 majú int n, čo je čokoľvek hodnota v obchode alebo reťazca n 354 00:18:33,569 --> 00:18:35,610 alebo čo chcete hovoria, char hviezda n. 355 00:18:35,610 --> 00:18:41,482 Uzol struct hviezda, čo je ukazovateľ ktoré chcete mať v každom uzle, 356 00:18:41,482 --> 00:18:43,690 budete mať, že Ukazovateľ bod k ďalšej. 357 00:18:43,690 --> 00:18:48,207 358 00:18:48,207 --> 00:18:50,040 Budete mať hlavu prepojeného zoznamu, ktorý je 359 00:18:50,040 --> 00:18:53,140 bude poukázať na zvyšku hodnoty tak ďalej a tak ďalej 360 00:18:53,140 --> 00:18:55,290 kým sa nakoniec dostanete na koniec. 361 00:18:55,290 --> 00:18:58,040 A to je len posledný uzol bude to mať ukazovateľ. 362 00:18:58,040 --> 00:18:59,952 Bude to poukázať na null, a to je, keď 363 00:18:59,952 --> 00:19:01,910 viete, že ste hit koniec vášho zoznamu Google 364 00:19:01,910 --> 00:19:04,076 je, keď vaše posledný ukazovateľ neukazuje na nič. 365 00:19:04,076 --> 00:19:06,670 366 00:19:06,670 --> 00:19:10,990 >> Tak sme sa chystáte ísť trochu viac do hĺbka ohľadom toho, ako by človek možná 367 00:19:10,990 --> 00:19:12,400 vyhľadávať prepojeného zoznamu. 368 00:19:12,400 --> 00:19:15,460 Pamätajte si, aké sú niektoré z nevýhody prepojených zoznamov 369 00:19:15,460 --> 00:19:19,340 verše pole o vyhľadávanie. 370 00:19:19,340 --> 00:19:22,565 Pole môžete binárne vyhľadávanie, ale prečo nemôžete urobiť, že v Google zozname? 371 00:19:22,565 --> 00:19:26,834 372 00:19:26,834 --> 00:19:30,320 >> Divákov: Vzhľadom na to, že sú všetci pripojení, ale nemáte dosť vedieť, kde 373 00:19:30,320 --> 00:19:31,330 [Nepočuteľný]. 374 00:19:31,330 --> 00:19:34,600 >> ANDI PENG: Jo, presne tak si pamätajte: že brilancie pole 375 00:19:34,600 --> 00:19:37,190 bola skutočnosť, že sme mali pamäť s priamym prístupom, kde 376 00:19:37,190 --> 00:19:41,580 keby som chcel hodnotu z indexu šesť, mohol by som len povedať index šesť, 377 00:19:41,580 --> 00:19:42,407 daj mi túto hodnotu. 378 00:19:42,407 --> 00:19:45,240 A to preto, že pole sú radené v súvislom priestore pamäti 379 00:19:45,240 --> 00:19:48,020 na jednom mieste, vzhľadom k tomu, druh spojových zoznamov 380 00:19:48,020 --> 00:19:52,820 sú náhodne striedajú všade okolo, a jediný spôsob, ako môžete nájsť jeden 381 00:19:52,820 --> 00:19:56,890 je cez ukazovateľ, ktorý vám povie, adresa, kde, že budúci uzol je. 382 00:19:56,890 --> 00:20:00,290 >> A tak ako výsledok, jediný spôsob, ako prehľadávať prepojenom zoznamu 383 00:20:00,290 --> 00:20:01,560 je lineárna hľadanie. 384 00:20:01,560 --> 00:20:05,890 Pretože ja presne neviem, kde 12. hodnota v Google zozname je, 385 00:20:05,890 --> 00:20:08,780 Musím prejsť celistvosť tohto prepojeného zoznamu jeden 386 00:20:08,780 --> 00:20:12,450 jeden z hlavy do prvého uzla, do druhého uzla, na tretiu uzla, 387 00:20:12,450 --> 00:20:17,690 celú cestu dole, až som sa konečne dostanem kde uzol Zháňam je. 388 00:20:17,690 --> 00:20:22,110 A tak v tomto zmysle, hľadanie v Google zozname je vždy n. 389 00:20:22,110 --> 00:20:23,040 Je to vždy n. 390 00:20:23,040 --> 00:20:25,690 Je to vždy v lineárnom čase. 391 00:20:25,690 --> 00:20:28,470 >> A tak sa kód, v ktorom realizujeme to, a to 392 00:20:28,470 --> 00:20:32,620 je trochu nový pre vás, pretože ste chlapci sa naozaj hovorili, alebo vôbec 393 00:20:32,620 --> 00:20:35,000 ukazovatele vidieť v tom, ako sa prehľadávať ukazovateľov, 394 00:20:35,000 --> 00:20:37,670 takže budeme prechádzať táto veľmi, veľmi pomaly. 395 00:20:37,670 --> 00:20:40,200 Takže bool vyhľadávania, vpravo, poďme si predstaviť, chceme 396 00:20:40,200 --> 00:20:42,820 vytvoriť funkciu nazvanú Hľadania, ktorý vracia true 397 00:20:42,820 --> 00:20:46,820 ak ste našli hodnote vnútri spojené vypísať, a vracia false inak. 398 00:20:46,820 --> 00:20:50,030 Uzol hviezda zoznam je V súčasnej dobe len ukazovateľ 399 00:20:50,030 --> 00:20:52,960 na prvú položku vo vašom Google zozname. 400 00:20:52,960 --> 00:20:56,700 int n je hodnota, ktorú ste hľadanie v tomto zozname. 401 00:20:56,700 --> 00:20:58,770 >> Takže uzol hviezda ukazovateľ rovná zoznam. 402 00:20:58,770 --> 00:21:00,970 To znamená, že sme nastavenie a vytvorenie ukazovatele 403 00:21:00,970 --> 00:21:03,592 do tohto prvého uzla vnútri zoznamu. 404 00:21:03,592 --> 00:21:04,300 Každý, kto so mnou? 405 00:21:04,300 --> 00:21:06,530 Takže ak by sme mali ísť späť, musel by som 406 00:21:06,530 --> 00:21:13,850 inicializovať ukazovateľ, ktorý odkazuje na hlava, čo tento zoznam. 407 00:21:13,850 --> 00:21:18,600 >> A potom, akonáhle sa dostanete tu zatiaľ čo ukazovateľ nerovná null, 408 00:21:18,600 --> 00:21:22,160 tak, že je slučka, v ktorej sú bude následne kríženie 409 00:21:22,160 --> 00:21:25,940 zvyšok nášho zoznamu pretože to, čo sa stane, keď ukazovateľ rovná null? 410 00:21:25,940 --> 00:21:27,550 Vieme, že sme have-- 411 00:21:27,550 --> 00:21:28,450 >> Divákov: [Nepočuteľné] 412 00:21:28,450 --> 00:21:31,491 >> ANDI PENG: Presne, takže vieme, že sme došli na koniec zoznamu, je to tak? 413 00:21:31,491 --> 00:21:34,470 Ak sa vydáte späť, každý uzol musí smerovať do iného uzla 414 00:21:34,470 --> 00:21:36,550 a tak ďalej a tak ďalej kým nenarazíte nakoniec 415 00:21:36,550 --> 00:21:41,589 chvost vášho Google zoznamu, ktorý má ukazovateľ, ktorý práve 416 00:21:41,589 --> 00:21:43,130 neukazuje inde ako žiadny. 417 00:21:43,130 --> 00:21:47,510 A tak ste v podstate viete, že váš zoznam je tu stále hore 418 00:21:47,510 --> 00:21:50,900 kým ukazovateľ nerovná null, pretože akonáhle sa rovná null, 419 00:21:50,900 --> 00:21:53,310 viete, že nie je viac vecí. 420 00:21:53,310 --> 00:21:56,930 >> Tak, že je slučka, v ktorej sme bude mať aktuálne vyhľadávania. 421 00:21:56,930 --> 00:22:01,690 A v prípade, že pointer-- vidíš že druh šípky tam funkcie? 422 00:22:01,690 --> 00:22:06,930 Takže ak ukazovateľ ukazuje na n, ak ukazovateľ v n rovná sa rovná n, 423 00:22:06,930 --> 00:22:09,180 tak, že znamená, že pokiaľ ukazovateľ, že ste 424 00:22:09,180 --> 00:22:13,420 vyhľadávanie na konci každého Uzol je vlastne rovná hodnote 425 00:22:13,420 --> 00:22:15,990 hľadáte, potom sa chcete vrátiť hodnotu true. 426 00:22:15,990 --> 00:22:19,280 Takže v podstate, ak ste na uzle, ktorý má hodnotu, ktorú hľadáte, 427 00:22:19,280 --> 00:22:23,550 viete, že ste boli schopní úspešne vyhľadávať. 428 00:22:23,550 --> 00:22:27,150 >> V opačnom prípade, že chcete nastaviť ukazovateľ na ďalšie uzol. 429 00:22:27,150 --> 00:22:28,850 To je to, čo tento riadok je tu robí. 430 00:22:28,850 --> 00:22:31,750 Ukazovateľ sa rovná ukazovateľ ďalšie. 431 00:22:31,750 --> 00:22:33,360 Všetci vidieť, ako to funguje? 432 00:22:33,360 --> 00:22:36,580 >> A v podstate budete len prejsť celistvosť zoznamu, 433 00:22:36,580 --> 00:22:41,920 resetovanie ukazovateľ zakaždým, kým budete nakoniec narazí na koniec zoznamu. 434 00:22:41,920 --> 00:22:45,030 A viete, že neexistujú žiadne viac uzlov prehľadávať, 435 00:22:45,030 --> 00:22:47,999 a potom môžete return false pretože viete, že, oh, no, 436 00:22:47,999 --> 00:22:50,540 ak som bol schopný vyhľadávať cez celé zoznamu. 437 00:22:50,540 --> 00:22:54,530 Ak by v tomto príklade, keby som chcel hľadať na hodnotu 10, 438 00:22:54,530 --> 00:22:57,250 I a začať v čele, a Aj hľadanie celú cestu dole, 439 00:22:57,250 --> 00:23:00,550 a nakoniec som sa dostal k tomu, ktorý ukazovateľ, ktorý poukazuje na hodnotu null, 440 00:23:00,550 --> 00:23:04,415 Viem, že, blbosť, myslím, že 10 nie je v Tento zoznam preto, že som nemohol nájsť. 441 00:23:04,415 --> 00:23:06,520 A ja som sa na konci zoznamu. 442 00:23:06,520 --> 00:23:11,040 A v takom prípade viete, Chystám sa vrátiť false. 443 00:23:11,040 --> 00:23:12,900 >> Nech že máčať v pre trochu. 444 00:23:12,900 --> 00:23:17,350 To bude dosť dôležité pre vašu pset. 445 00:23:17,350 --> 00:23:21,140 Logika je to veľmi jednoduché, snáď syntakticky len jej vykonávaní. 446 00:23:21,140 --> 00:23:23,365 Vy chcete, aby Uistite sa, že rozumiete. 447 00:23:23,365 --> 00:23:25,870 448 00:23:25,870 --> 00:23:27,650 Super. 449 00:23:27,650 --> 00:23:32,560 >> OK, tak ako by sme boli vkladanie uzlov, vpravo, 450 00:23:32,560 --> 00:23:35,380 do zoznamu, pretože pamätať aké sú to, čo výhod 451 00:23:35,380 --> 00:23:39,230 mať prepojeného zoznamu oproti poľa, pokiaľ ide o skladovanie? 452 00:23:39,230 --> 00:23:41,110 >> Divákov: Je to dynamický, takže je to jednoduchšie, to-- 453 00:23:41,110 --> 00:23:43,180 >> ANDI PENG: Presne tak, tak je to dynamický, ktorý 454 00:23:43,180 --> 00:23:46,880 znamená, že sa môže rozšíriť a zmenšiť V závislosti na potrebách užívateľa. 455 00:23:46,880 --> 00:23:56,570 A tak, v tomto zmysle, nepotrebujeme strácať zbytočne pamäť, pretože som 456 00:23:56,570 --> 00:24:00,850 keď neviem, koľko hodnôt Chcem skladovať, to nemá zmysel pre mňa 457 00:24:00,850 --> 00:24:04,310 vytvoriť pole z nasledujúcich dôvodov keď chcem uložiť 10 hodnôt 458 00:24:04,310 --> 00:24:08,380 a ja sa vytvoriť rad 1000, to je veľa nevyužité pamäte, pridelené. 459 00:24:08,380 --> 00:24:11,180 To je dôvod, prečo chceme použiť prepojený zoznam, aby bolo možné dynamicky 460 00:24:11,180 --> 00:24:13,860 zmeniť alebo zmenšiť našu veľkosť. 461 00:24:13,860 --> 00:24:17,040 >> A tak to robí vkladanie trochu zložitejšie. 462 00:24:17,040 --> 00:24:20,810 Vzhľadom k tomu, nemôžeme náhodne prístup k prvkom tak, že by sme z poľa. 463 00:24:20,810 --> 00:24:24,270 Ak chcem vložiť prvok do siedmej indexu 464 00:24:24,270 --> 00:24:26,930 Len som si ju vložiť do siedmej indexu. 465 00:24:26,930 --> 00:24:30,020 V prepojenom zozname, to nie je pomerne pracovať tak ľahko, 466 00:24:30,020 --> 00:24:34,947 a tak ak by sme chceli vložiť ten tu v Google zozname, 467 00:24:34,947 --> 00:24:36,280 vizuálne, je to veľmi dobre vidieť. 468 00:24:36,280 --> 00:24:39,363 Chceme len, aby ho vložiť priamo tam, hneď na začiatku zoznamu, 469 00:24:39,363 --> 00:24:40,840 hneď po hlave. 470 00:24:40,840 --> 00:24:44,579 >> Ale spôsob, akým musíme preradiť Ukazovatele sa trochu spletitý 471 00:24:44,579 --> 00:24:47,620 alebo, logicky, to dáva zmysel, ale chcete, aby sa ubezpečil, že to máte 472 00:24:47,620 --> 00:24:50,250 úplne dole, pretože to posledné, čo chcete, 473 00:24:50,250 --> 00:24:52,990 je priradiť ukazovátka tak, že tu robíme. 474 00:24:52,990 --> 00:24:58,170 Ak vás dereferencia ukazovateľ od hlavy až k 1, 475 00:24:58,170 --> 00:25:01,086 potom zrazu The zvyšok vášho Google zoznamu 476 00:25:01,086 --> 00:25:04,680 je stratené, pretože ste nie je vlastne vytvorili dočasný čokoľvek. 477 00:25:04,680 --> 00:25:06,220 To ukázal na 2. 478 00:25:06,220 --> 00:25:10,080 Ak priradenie ukazovateľ, potom sa zvyšok vášho zoznamu je úplne stratený. 479 00:25:10,080 --> 00:25:13,310 Takže vy chcete byť veľmi, veľmi opatrný tu 480 00:25:13,310 --> 00:25:17,010 najprv priradiť ukazovateľ z akéhokoľvek vás 481 00:25:17,010 --> 00:25:20,150 chcete vložiť do kamkoľvek chceš, a potom vás 482 00:25:20,150 --> 00:25:22,710 môže dereferencia zvyšok vášho zoznamu. 483 00:25:22,710 --> 00:25:25,250 >> Tak to platí pre kdekoľvek snažíte vložiť do. 484 00:25:25,250 --> 00:25:27,520 Ak chcete vložiť u hlava, ak chcete odpovedať na tú, 485 00:25:27,520 --> 00:25:29,455 ak chcete vložiť na koniec, no, nakoniec som sa 486 00:25:29,455 --> 00:25:30,910 Asi by ste práve nemajú žiadny ukazovateľ, ale vy 487 00:25:30,910 --> 00:25:33,830 chcete, aby sa ubezpečil, že nemáte stratiť zvyšok zoznamu. 488 00:25:33,830 --> 00:25:36,640 Vždycky chcete byť istý, Váš nový uzol smeruje 489 00:25:36,640 --> 00:25:39,330 smerom k čo chcete vložiť do, 490 00:25:39,330 --> 00:25:42,170 a potom môžete pridať zreťazenie ďalej. 491 00:25:42,170 --> 00:25:43,330 Všetci jasné? 492 00:25:43,330 --> 00:25:45,427 >> To bude jeden zo skutočných problémov. 493 00:25:45,427 --> 00:25:48,010 Jedným z najviac hlavných problémov budete mať na svojom pset 494 00:25:48,010 --> 00:25:51,340 je to, že budete snažiť vytvoriť prepojený zoznam a vložiť veci 495 00:25:51,340 --> 00:25:53,340 ale potom len stratiť zvyšok svojho Google zoznamu. 496 00:25:53,340 --> 00:25:54,900 A ty budeš rád, ja Neviem, prečo sa to deje? 497 00:25:54,900 --> 00:25:58,040 A je to bolesť prejsť a hľadať všetky vaše ukazovateľov. 498 00:25:58,040 --> 00:26:02,100 >> A ja vám zaručiť, na tomto pset, písanie a kreslenie týchto uzlov out 499 00:26:02,100 --> 00:26:03,344 bude veľmi, veľmi užitočné. 500 00:26:03,344 --> 00:26:06,010 Takže si môžete úplne sledovať kde všetky vaše ukazovatele sú, 501 00:26:06,010 --> 00:26:08,540 čo sa deje zle, kde sa všetky vaše uzly sú, 502 00:26:08,540 --> 00:26:12,660 to, čo musíte urobiť, aby prístup alebo vložiť alebo odstrániť, alebo niektorý z nich. 503 00:26:12,660 --> 00:26:14,550 Všetci dobre s tým? 504 00:26:14,550 --> 00:26:15,050 Super. 505 00:26:15,050 --> 00:26:19,300 506 00:26:19,300 --> 00:26:22,600 >> Takže ak sme chceli pozrieť na kód? 507 00:26:22,600 --> 00:26:24,470 Oh, ja neviem, či my môžete vidieť the-- OK, tak 508 00:26:24,470 --> 00:26:27,940 V hornej rade je to je funkcia menoval vložka tam, kde chceme 509 00:26:27,940 --> 00:26:31,365 vložiť int n do prepojeného zoznamu. 510 00:26:31,365 --> 00:26:32,740 Chystáme sa prejsť to. 511 00:26:32,740 --> 00:26:34,770 Je to veľa kódu, veľa novú syntaxou. 512 00:26:34,770 --> 00:26:36,220 Budeme v poriadku. 513 00:26:36,220 --> 00:26:39,120 >> Tak sa v hornej časti, ak je to chceme vytvoriť niečo 514 00:26:39,120 --> 00:26:42,380 čo musíme urobiť, najmä ak ste chcete, aby to nemalo byť uložený v zásobníku 515 00:26:42,380 --> 00:26:43,920 ale v halde? 516 00:26:43,920 --> 00:26:45,460 Ideme do malloc, že ​​jo? 517 00:26:45,460 --> 00:26:48,240 Takže budeme vytvoriť ukazovateľ. 518 00:26:48,240 --> 00:26:52,074 Uzol, ukazovateľ, nové rovná malloc veľkosť uzla 519 00:26:52,074 --> 00:26:53,740 pretože chceme, aby uzol, ktorý bude vytvorený. 520 00:26:53,740 --> 00:26:56,720 Chceme, aby množstvo pamäť, ktorá uzol zaberá 521 00:26:56,720 --> 00:26:59,300 majú byť pridelené pre vytvorenie nového uzla. 522 00:26:59,300 --> 00:27:02,270 >> A potom budeme skontrolovať, uvidíme, či nová rovná sa rovná null. 523 00:27:02,270 --> 00:27:03,370 Spomeňte si, čo sme si povedali? 524 00:27:03,370 --> 00:27:06,470 Či už vás malloc, Čo musíte vždy urobiť? 525 00:27:06,470 --> 00:27:09,490 Vždy musíte skontrolovať, či to je null. 526 00:27:09,490 --> 00:27:13,620 >> Napríklad, ak váš operačný Systém bol úplne plný, 527 00:27:13,620 --> 00:27:17,060 ak ste mali na nie viac pamäte všetky a skúste malloc, 528 00:27:17,060 --> 00:27:18,410 že sa vráti null pre vás. 529 00:27:18,410 --> 00:27:21,094 A tak ak sa pokúsite použiť keď to bolo ukázal na null, 530 00:27:21,094 --> 00:27:23,260 vy nebudete schopní na prístup k týmto informáciám. 531 00:27:23,260 --> 00:27:27,010 A tak ako taký, chceli sme, aby sa istí, že vždy, keď ste mallocing, 532 00:27:27,010 --> 00:27:30,500 ste vždy skontrolovať, či že pamäť daný pre vás je null. 533 00:27:30,500 --> 00:27:33,670 A ak to tak nie je, potom sa môžeme presunúť so zvyškom nášho kódu. 534 00:27:33,670 --> 00:27:36,140 >> Takže budeme inicializovať nový uzol. 535 00:27:36,140 --> 00:27:39,050 Chystáme sa urobiť nový n sa rovná n. 536 00:27:39,050 --> 00:27:42,390 A potom budeme robiť nastaviť nový ukazovateľ na nové 537 00:27:42,390 --> 00:27:46,900 na NULL, pretože práve teraz my nie chcú niečo pre to, aby ukazoval na. 538 00:27:46,900 --> 00:27:48,755 Nemáme tušenie, kde to bude, aby vám, 539 00:27:48,755 --> 00:27:50,630 a ak chceme vložte ho v čele, 540 00:27:50,630 --> 00:27:53,820 potom môžeme priradiť ukazovateľ na hlave. 541 00:27:53,820 --> 00:27:58,530 Má každý sledovať logiku kde že sa to deje? 542 00:27:58,530 --> 00:28:02,502 >> Všetko, čo robíte, je vytvorenie nového uzol, nastavenie ukazovateľ na null, 543 00:28:02,502 --> 00:28:04,210 a potom priradenie to do hlavy, keby sme 544 00:28:04,210 --> 00:28:06,320 viete, chceme vložiť do čela. 545 00:28:06,320 --> 00:28:09,420 A potom hlava sa chystá ukazovať smerom k tomuto novému uzla. 546 00:28:09,420 --> 00:28:11,060 Každý, kto s tým OK? 547 00:28:11,060 --> 00:28:12,380 >> Takže je to dvojstupňový proces. 548 00:28:12,380 --> 00:28:14,760 Musíš Najprv priraďte čo budete vytvárať. 549 00:28:14,760 --> 00:28:18,260 Nastaviť že ukazovateľ odkazovať, a potom vás 550 00:28:18,260 --> 00:28:21,400 môže druh dereferencia prvý ukazovateľ 551 00:28:21,400 --> 00:28:22,972 a prejdite na nový uzol. 552 00:28:22,972 --> 00:28:25,680 Všade tam, kde ju chcete vložiť, že logika bude platiť. 553 00:28:25,680 --> 00:28:27,530 >> Je to niečo ako priradenie dočasné premenné. 554 00:28:27,530 --> 00:28:28,700 Pamätajte si, že máte aby sa uistil, že vás 555 00:28:28,700 --> 00:28:30,346 nestrácajú prehľad o ak ste swapovanie. 556 00:28:30,346 --> 00:28:33,470 Chcete, aby sa uistil, že máte dočasná premenná, ktorá druh udržuje 557 00:28:33,470 --> 00:28:35,620 sledovať, kde tej veci je uložená tak, že 558 00:28:35,620 --> 00:28:41,190 nestratili žiadnu hodnotu v priebehu ako sa pohrávate s ním. 559 00:28:41,190 --> 00:28:42,710 >> OK, takže tu bude kód. 560 00:28:42,710 --> 00:28:45,020 Vy sa pozrieť po bode. 561 00:28:45,020 --> 00:28:48,060 Bude to tam. 562 00:28:48,060 --> 00:28:50,280 >> Takže si myslím, ako sa to sa líši, ak by sme chceli 563 00:28:50,280 --> 00:28:52,300 vložiť do stredu alebo na konci? 564 00:28:52,300 --> 00:28:57,892 Má niekto má predstavu o tom, čo je to pseudokód ako logické referencie 565 00:28:57,892 --> 00:29:00,350 že by sme trvať, ak by sme chceli ho vložiť do stredu? 566 00:29:00,350 --> 00:29:03,391 Takže ak by sme chceli vložiť u hlava, všetko, čo urobiť, je vytvoriť nový uzol. 567 00:29:03,391 --> 00:29:06,311 Nastavili sme ukazovateľ, ktorý Nový uzol sa to bez ohľadu na hlave, 568 00:29:06,311 --> 00:29:08,310 a potom sme sa nastaviť hlavu do nového uzla, že jo? 569 00:29:08,310 --> 00:29:11,560 Ak by sme chceli vložiť do stredu zoznamu, čo by sa musíme urobiť? 570 00:29:11,560 --> 00:29:14,108 571 00:29:14,108 --> 00:29:16,110 >> Divákov: To by ešte byť podobný proces 572 00:29:16,110 --> 00:29:19,114 ako sa priradenie ukazovatele, potom priradí tento ukazovateľ, 573 00:29:19,114 --> 00:29:20,530 ale museli by sme tam nájsť. 574 00:29:20,530 --> 00:29:23,560 >> ANDI PENG: Presne tak, presne rovnaký proces okrem vás 575 00:29:23,560 --> 00:29:27,820 musieť nájsť, kde presne ste chcete, aby nový ukazovateľ ísť do, 576 00:29:27,820 --> 00:29:44,790 takže ak chcem vložiť do uprostred spojené list-- OK, 577 00:29:44,790 --> 00:29:46,370 povedzme, že je to naša previazaný zoznam. 578 00:29:46,370 --> 00:29:49,500 Ak chceme ho vložiť priamo tu, budeme vytvoriť nový uzol. 579 00:29:49,500 --> 00:29:50,520 Ideme do malloc. 580 00:29:50,520 --> 00:29:52,220 Chystáme sa vytvoriť nový uzol. 581 00:29:52,220 --> 00:29:55,940 Budeme priradiť ukazovateľ tohto uzla tu. 582 00:29:55,940 --> 00:29:58,335 >> Avšak problémom, ktorý sa líši od miesta, kde je hlava 583 00:29:58,335 --> 00:30:00,490 je, že sme presne vedeli, kde je hlava. 584 00:30:00,490 --> 00:30:01,930 To bolo hneď na začiatku, že jo? 585 00:30:01,930 --> 00:30:04,870 Ale tu musíme sledovať kde sme vložením do. 586 00:30:04,870 --> 00:30:07,930 Sme chcete vložiť naše uzol tu, máme 587 00:30:07,930 --> 00:30:12,270 aby sa uistil, že človek predchádzajúce do tohto uzla 588 00:30:12,270 --> 00:30:14,172 je ten, ktorý priraďuje ukazovateľ. 589 00:30:14,172 --> 00:30:16,380 Takže potom budete musieť trochu sledovať dve veci. 590 00:30:16,380 --> 00:30:19,420 Ak máte sledovať, kde to uzol je v súčasnej dobe vloženie do. 591 00:30:19,420 --> 00:30:23,280 Musíte tiež sledovať, kde predchádzajúci uzol, ktorý sa pozeráte 592 00:30:23,280 --> 00:30:24,340 bol tiež tam. 593 00:30:24,340 --> 00:30:25,830 Všetci dobre s tým? 594 00:30:25,830 --> 00:30:26,500 OK. 595 00:30:26,500 --> 00:30:28,000 >> Ako sa o vložení do konca? 596 00:30:28,000 --> 00:30:34,220 Keby som chcel pridať here-- keby som chcel pridať nový uzol na koniec zoznamu, 597 00:30:34,220 --> 00:30:37,009 Ako by som mohol ísť o tom, že? 598 00:30:37,009 --> 00:30:39,300 Publikum: Takže v súčasnej dobe je posledný, kto sa ukázal na null. 599 00:30:39,300 --> 00:30:40,960 ANDI PENG: Jo. 600 00:30:40,960 --> 00:30:43,560 Presne, takže tento raz V súčasnej dobe je orientované na vedieť, 601 00:30:43,560 --> 00:30:46,720 a tak myslím, že v tomto zmysle, že je to veľmi ľahko pridať na koniec zoznamu. 602 00:30:46,720 --> 00:30:51,810 Jediné, čo musíte urobiť, je nastaviť rovná null a potom boom. 603 00:30:51,810 --> 00:30:53,070 Presne tam, veľmi jednoduché. 604 00:30:53,070 --> 00:30:53,960 Veľmi jednoduché. 605 00:30:53,960 --> 00:30:56,430 >> Veľmi podobné hlava, ale logicky vás 606 00:30:56,430 --> 00:30:59,690 chcete, aby sa ubezpečil, že kroky užívate k robí niečo z toho, 607 00:30:59,690 --> 00:31:01,500 ste po pozdĺž. 608 00:31:01,500 --> 00:31:04,420 Je to veľmi jednoduché, v stredu vášho kódu, uviaznu na, 609 00:31:04,420 --> 00:31:05,671 oh, mám toľko ukazovateľov. 610 00:31:05,671 --> 00:31:07,461 Ja neviem, kde niečo ukazuje. 611 00:31:07,461 --> 00:31:09,170 Ja ani neviem, ktorý uzol, že som ďalej. 612 00:31:09,170 --> 00:31:11,490 Čo sa deje? 613 00:31:11,490 --> 00:31:13,620 >> Relax, upokoj sa, zhlboka sa nadýchnuť. 614 00:31:13,620 --> 00:31:15,530 Nakreslite si svoje prepojeného zoznamu. 615 00:31:15,530 --> 00:31:18,800 Ak poviete, ja viem, kde presne Musím vložiť to do 616 00:31:18,800 --> 00:31:22,970 a viem presne, ako zmeniť priradenie my ukazovatele, oveľa, oveľa jednoduchšie na obrázok 617 00:31:22,970 --> 00:31:27,200 out-- oveľa, oveľa jednoduchšie, že nebude stratiť v chybách v kóde. 618 00:31:27,200 --> 00:31:29,410 Každý, kto s tým OK? 619 00:31:29,410 --> 00:31:31,380 OK. 620 00:31:31,380 --> 00:31:35,120 >> Takže si myslím, koncept, že sme sa naozaj hovoril o skôr, 621 00:31:35,120 --> 00:31:38,131 a myslím, že vás najskôr nie je dôjde oveľa yet-- 622 00:31:38,131 --> 00:31:40,880 je to celkom pokročilé concept-- je to, že sme vlastne majú údaje 623 00:31:40,880 --> 00:31:43,900 štruktúra volal dvojnásobne prepojeného zoznamu. 624 00:31:43,900 --> 00:31:46,390 Tak ako vy môžete vidieť, všetko, čo robíte, je vytvorenie 625 00:31:46,390 --> 00:31:50,400 skutočné hodnoty, navyše Ukazovateľ na každej z našich uzlov 626 00:31:50,400 --> 00:31:52,660 ktorá tiež poukazuje na predchádzajúcu uzla. 627 00:31:52,660 --> 00:31:58,170 Takže nielen že máme svoje uzly poukazujú na ten budúci. 628 00:31:58,170 --> 00:32:01,430 Poukazujú tiež na predchádzajúce. 629 00:32:01,430 --> 00:32:04,310 Budem ignorovať aj týchto dvoch práve teraz. 630 00:32:04,310 --> 00:32:06,740 >> Takže máte reťaz ktoré sa môžu pohybovať oboma smermi, 631 00:32:06,740 --> 00:32:09,630 a potom je to trochu jednoduchšie logicky nasledovať. 632 00:32:09,630 --> 00:32:11,896 Rovnako ako tu, miesto sledovanie z, oh, ja 633 00:32:11,896 --> 00:32:14,520 musí vedieť, že tento uzol ten, ktorý mám k preradeniu, 634 00:32:14,520 --> 00:32:17,532 Môžem jednoducho ísť sem a stačí vytiahnuť predchádzajúce. 635 00:32:17,532 --> 00:32:19,490 Potom som presne vedieť, kde že je, a potom vás 636 00:32:19,490 --> 00:32:21,130 Nemusíte sa prejsť celistvosť Google zoznamu. 637 00:32:21,130 --> 00:32:22,180 Je to trochu jednoduchšie. 638 00:32:22,180 --> 00:32:24,960 >> Ale ako taký, budete mať dvojnásobne množstvo ukazovateľov, 639 00:32:24,960 --> 00:32:26,960 To je dvojnásobok pamäte. 640 00:32:26,960 --> 00:32:28,950 Je to veľa ukazovateľov sledovať. 641 00:32:28,950 --> 00:32:32,140 Je to trochu zložitejšie, ale je to trochu viac užívateľsky prívetivé závislosti 642 00:32:32,140 --> 00:32:34,080 na to, čo sa snažíte dosiahnuť. 643 00:32:34,080 --> 00:32:36,910 >> Takže tento druh údajov Štruktúra úplne existuje, 644 00:32:36,910 --> 00:32:40,280 a štruktúra je veľmi, veľmi jednoduché, s výnimkou všetko máte, je, 645 00:32:40,280 --> 00:32:43,850 namiesto iba ukazovateľ na ďalšie, máte tiež ukazovateľ na predchádzajúcu. 646 00:32:43,850 --> 00:32:45,940 To je všetko, bol rozdiel. 647 00:32:45,940 --> 00:32:47,740 Všetci dobre s tým? 648 00:32:47,740 --> 00:32:48,240 Super. 649 00:32:48,240 --> 00:32:50,940 650 00:32:50,940 --> 00:32:53,280 >> Dobre, takže teraz som naozaj stráviť pravdepodobne 651 00:32:53,280 --> 00:32:56,870 ako je 15 až 20 minút alebo objemu zvyšku času v sekcii 652 00:32:56,870 --> 00:32:58,360 hovorí o hash tabuliek. 653 00:32:58,360 --> 00:33:02,590 Koľko z vás Prečítal pset5 spec? 654 00:33:02,590 --> 00:33:03,620 Dobre, dobre. 655 00:33:03,620 --> 00:33:06,160 To je vyššia ako 50% za normálnych okolností. 656 00:33:06,160 --> 00:33:07,560 Je to v poriadku. 657 00:33:07,560 --> 00:33:10,345 >> Tak ako vy uvidíte, ste výzvou pset5 658 00:33:10,345 --> 00:33:16,790 bude vykonávanie slovník kde si nahrať cez 140.000 slov 659 00:33:16,790 --> 00:33:20,610 že sme vám kontrolu pravopisu to proti všetkým textu. 660 00:33:20,610 --> 00:33:22,580 Dáme vám náhodné kusy literatúry. 661 00:33:22,580 --> 00:33:23,520 Dáme vám Odyssea. 662 00:33:23,520 --> 00:33:24,561 Dáme vám Ilias. 663 00:33:24,561 --> 00:33:26,350 Dáme vám Austin Powers. 664 00:33:26,350 --> 00:33:28,220 >> A vaše výzva bude kontrolu pravopisu 665 00:33:28,220 --> 00:33:31,760 každé slovo vo všetkých z týchto slovníkov 666 00:33:31,760 --> 00:33:34,960 v podstate s našou kontrolou pravopisu. 667 00:33:34,960 --> 00:33:38,620 A tak je tu niekoľko dielov vytvorenie tohto pset, 668 00:33:38,620 --> 00:33:41,970 Prvý chcete byť schopný skutočne načítať 669 00:33:41,970 --> 00:33:43,970 všetky slová do vášho slovník, a potom vás 670 00:33:43,970 --> 00:33:45,530 chcú byť schopní pravopisu skontrolovať všetky z nich. 671 00:33:45,530 --> 00:33:48,780 A tak ako taký, budete požadovať dátová štruktúra, ktorá môže robiť to rýchlo 672 00:33:48,780 --> 00:33:50,790 a efektívne a dynamicky. 673 00:33:50,790 --> 00:33:52,900 >> Takže myslím, že najjednoduchšie spôsob, ako to urobiť, 674 00:33:52,900 --> 00:33:55,010 by pravdepodobne vytvorenie poľa, nie? 675 00:33:55,010 --> 00:33:58,910 Najjednoduchší spôsob skladovania je vám môže vytvoriť rad 140,000 slov 676 00:33:58,910 --> 00:34:03,400 a len ich všetky umiestniť tam a potom prejsť im binárne vyhľadávanie 677 00:34:03,400 --> 00:34:06,780 alebo výberov či ne-- Ospravedlňujem sa, že sa triedenie. 678 00:34:06,780 --> 00:34:10,729 Môžete ich triediť a potom prejsť je binárne vyhľadávanie, alebo len lineárne hľadanie 679 00:34:10,729 --> 00:34:13,730 a len záverečné slová, ale že berie obrovské množstvo pamäte, 680 00:34:13,730 --> 00:34:15,190 a to nie je príliš efektívne. 681 00:34:15,190 --> 00:34:18,350 >> A tak sme sa chystáte začať hovorí o spôsoboch, ktorými sa 682 00:34:18,350 --> 00:34:20,110 Naša doba chodu efektívnejšie. 683 00:34:20,110 --> 00:34:23,190 A naším cieľom je dostať konštantný doba, kedy 684 00:34:23,190 --> 00:34:25,810 je to skoro ako pole, kde máte okamžitý prístup. 685 00:34:25,810 --> 00:34:28,560 Keby som chcel hľadať čokoľvek, Chcem byť schopný len, 686 00:34:28,560 --> 00:34:30,810 boom, nájsť presne to, a vytiahnite ju von. 687 00:34:30,810 --> 00:34:34,100 A tak sa štruktúra, v ktorej budeme stále veľmi blízko 688 00:34:34,100 --> 00:34:37,569 aby bolo možné získať prístup konštantný čas, tento svätý grál 689 00:34:37,569 --> 00:34:41,370 v programovaní konštanty Čas sa nazýva hash tabuľky. 690 00:34:41,370 --> 00:34:45,370 A tak Dávid už skôr zmienil o [Nepočuteľný] trochu v prednáške, 691 00:34:45,370 --> 00:34:49,100 ale budeme skutočne ponor v hlbokej tento týždeň 692 00:34:49,100 --> 00:34:51,780 na kus, ktorý je, ak ide o ako hash tabuľky funguje. 693 00:34:51,780 --> 00:34:53,949 >> Tak tak, že hash tabuľka práce, napríklad, 694 00:34:53,949 --> 00:35:00,230 keby som chcel uložiť množstvo slovami, banda slov v anglickom jazyku, 695 00:35:00,230 --> 00:35:02,940 Mohol by som teoreticky dať banán, jablko, kivi, mango, pár, 696 00:35:02,940 --> 00:35:04,980 a cantaloupe všetko len na maticu. 697 00:35:04,980 --> 00:35:07,044 Všetky by mohli zapadnúť a bude nájsť. 698 00:35:07,044 --> 00:35:09,210 Bolo by druh bolesti prehľadávať a prístupu, 699 00:35:09,210 --> 00:35:12,920 ale jednoduchší spôsob, ako to dosiahnuť, je že môžeme vytvoriť vlastne štruktúra 700 00:35:12,920 --> 00:35:15,680 nazýva hash tabuľky, kde sme hash. 701 00:35:15,680 --> 00:35:19,880 Vedieme všetky naše kľúčov prostredníctvom funkcia hash, rovnice, 702 00:35:19,880 --> 00:35:22,600 že zmení ich všetky do nejaký hodnotu 703 00:35:22,600 --> 00:35:28,740 že potom môžeme ukladať na v podstate pole prepojeného zoznamu. 704 00:35:28,740 --> 00:35:32,570 >> A tak tu, ak by sme chceli ukladať anglické slová, 705 00:35:32,570 --> 00:35:37,250 sme mohli potenciálne jednoducho, ja nie Viete, vypnite všetky prvé písmená 706 00:35:37,250 --> 00:35:39,630 do nejakého druhu čísla. 707 00:35:39,630 --> 00:35:43,140 A tak napríklad, keď som chcel A byť synonymom apple-- 708 00:35:43,140 --> 00:35:47,460 alebo s indexom 0, a B synonymom s 1, 709 00:35:47,460 --> 00:35:51,030 môžeme mať 26 záznamov ktorý môže len uložiť 710 00:35:51,030 --> 00:35:53,610 všetky písmená abeceda, že začneme s. 711 00:35:53,610 --> 00:35:56,130 A potom môžeme mať apple v indexe od 0. 712 00:35:56,130 --> 00:35:59,160 Môžeme mať banán na indexe 1, ananásový melón na indexe 2, 713 00:35:59,160 --> 00:36:00,540 a tak ďalej a tak ďalej. 714 00:36:00,540 --> 00:36:04,460 A tak, keď som sa chcel vyhľadávať môj hash stôl a prístup jablko, 715 00:36:04,460 --> 00:36:07,560 Viem, že jablko začína à, a viem presne, 716 00:36:07,560 --> 00:36:10,860 že to musí byť a hash Tabuľka na indexe 0 Pretože je 717 00:36:10,860 --> 00:36:13,620 funkcie skôr priradená. 718 00:36:13,620 --> 00:36:16,572 >> Takže ja neviem, my sme užívateľský program, kde 719 00:36:16,572 --> 00:36:18,780 budete obvinený arbitrarily-- nebolo svojvoľne, 720 00:36:18,780 --> 00:36:22,530 sa snaží zamyslene myslieť na dobré rovníc 721 00:36:22,530 --> 00:36:25,460 aby bolo možné rozšíriť mimo všetky svoje hodnoty 722 00:36:25,460 --> 00:36:29,370 takým spôsobom, že môžu ľahko získať prístup to neskôr sa ako rovnica 723 00:36:29,370 --> 00:36:31,130 že vy, sami, vieš. 724 00:36:31,130 --> 00:36:35,210 Takže v tom zmysle, či by som chcel ísť do mango, ja viem, oh, začína m. 725 00:36:35,210 --> 00:36:37,134 To musí byť v indexe 12. 726 00:36:37,134 --> 00:36:38,800 Nemám prehľadávať čokoľvek. 727 00:36:38,800 --> 00:36:42,080 Viem, že exactly-- som mohol len ísť do index 12 a vytiahnite to von. 728 00:36:42,080 --> 00:36:45,520 >> Každý jasne o tom, ako hashovacie funkcie tabuľky funguje? 729 00:36:45,520 --> 00:36:48,380 Je to tak trochu len zložitejšie poľa. 730 00:36:48,380 --> 00:36:50,010 To je všetko, čo je. 731 00:36:50,010 --> 00:36:51,630 OK. 732 00:36:51,630 --> 00:36:57,690 >> Takže myslím, že narazíme táto otázka toho, čo 733 00:36:57,690 --> 00:37:06,390 sa stane, keď máte viac vecí že vám rovnaký index? 734 00:37:06,390 --> 00:37:10,570 Tak hovoria naši funkciu, všetci to urobil, bolo, prijať, že prvé písmeno 735 00:37:10,570 --> 00:37:14,490 a meniť na Príslušná 0 až 25 index. 736 00:37:14,490 --> 00:37:17,137 To je úplne v poriadku, ak máte iba jeden z každého z nich. 737 00:37:17,137 --> 00:37:18,970 Ale druhá začnete ktoré majú viac, že ​​ste 738 00:37:18,970 --> 00:37:20,910 bude mať, čo sa nazýva kolízie. 739 00:37:20,910 --> 00:37:25,580 >> Takže keď sa snažím vložiť pochovať do hash tabuľka, ktorá už má banán na tom, 740 00:37:25,580 --> 00:37:27,870 čo sa stane, keď pokusu o vloženie, že? 741 00:37:27,870 --> 00:37:30,930 Zlé veci preto, že banán Už v rámci indexu existuje 742 00:37:30,930 --> 00:37:33,800 že chcete uložiť ho do. 743 00:37:33,800 --> 00:37:35,560 Berry druh je ako, ehm, čo mám robiť? 744 00:37:35,560 --> 00:37:37,080 Neviem, kam ísť. 745 00:37:37,080 --> 00:37:38,410 Ako môžem vyriešiť? 746 00:37:38,410 --> 00:37:41,150 >> A tak si chlapci bude druh pozri robíme tejto chúlostivej veci 747 00:37:41,150 --> 00:37:44,810 kde môžeme trochu vlastne Vytvorenie prepojeného zoznamu v našich poliach. 748 00:37:44,810 --> 00:37:46,840 A tak najjednoduchší spôsob premýšľať o tom, 749 00:37:46,840 --> 00:37:50,830 všetky hash tabuľka je rad spojových zoznamov. 750 00:37:50,830 --> 00:37:55,670 A tak, v tomto zmysle, máte toto krásne pole ukazovateľov, 751 00:37:55,670 --> 00:37:58,740 a potom každý ukazovateľ v že hodnota tohto indexu, 752 00:37:58,740 --> 00:38:00,740 môže skutočne ukazovať na iné veci. 753 00:38:00,740 --> 00:38:05,720 A tak budete mať všetky tieto oddelené reťaze spadnutie jedného veľkého poľa. 754 00:38:05,720 --> 00:38:07,960 >> A tak tu, keď som chcel vložiť bobule, 755 00:38:07,960 --> 00:38:11,220 Ja viem, v poriadku, budem vstup to cez môj hash funkcie. 756 00:38:11,220 --> 00:38:15,070 Chystám sa skončiť s indexom 1, a potom budem mať možnosť 757 00:38:15,070 --> 00:38:20,410 len menšie podmnožina toto obrie 140000-slovo slovníka. 758 00:38:20,410 --> 00:38:24,220 A potom som si len pozerať prostredníctvom 1/26 toho. 759 00:38:24,220 --> 00:38:27,910 >> A tak som si len vložiť bobule buď pred alebo po banány 760 00:38:27,910 --> 00:38:28,820 v tomto prípade? 761 00:38:28,820 --> 00:38:29,700 Po, že jo? 762 00:38:29,700 --> 00:38:33,920 A tak budete chcieť vložiť tento uzol po banán, 763 00:38:33,920 --> 00:38:36,667 a tak budete vkladať na chvoste tohto prepojeného zoznamu. 764 00:38:36,667 --> 00:38:38,500 Chystám sa vrátiť späť k tomuto predchádzajúcemu snímky, 765 00:38:38,500 --> 00:38:40,680 tak vy môžete vidieť, ako hash funkcia pracuje. 766 00:38:40,680 --> 00:38:43,980 >> Takže hash funkcia je táto rovnica že vediete druh váš vstup 767 00:38:43,980 --> 00:38:46,940 až sa dostať čo index Ak chcete ju priradiť k. 768 00:38:46,940 --> 00:38:51,130 A tak, v tomto prípade všetko, čo sme chceli urobiť, bolo vziať prvé písmeno, 769 00:38:51,130 --> 00:38:55,890 obrátiť, že do indexu, potom sme možno uložiť, že v našom hash funkcie. 770 00:38:55,890 --> 00:39:00,160 Všetko, čo tu robíme, je, že sme konverziu prvé písmeno. 771 00:39:00,160 --> 00:39:04,770 Takže keykey [0] je len prvé písmeno akéhokoľvek string budeme mať, 772 00:39:04,770 --> 00:39:05,720 sme odovzdaním. 773 00:39:05,720 --> 00:39:09,740 Sme konverziu, že pre horný, a sme sa odpočíta od veľkými písmenami A, 774 00:39:09,740 --> 00:39:11,740 takže všetko, čo robí nám dáva číslo 775 00:39:11,740 --> 00:39:13,670 v ktorom môžeme hash naše hodnoty na. 776 00:39:13,670 --> 00:39:16,550 >> A potom budeme návrat hash modulu veľkosti. 777 00:39:16,550 --> 00:39:19,340 Buďte veľmi, veľmi opatrní preto, že teoreticky, tu 778 00:39:19,340 --> 00:39:21,870 Váš hash hodnota mohla byť nekonečná. 779 00:39:21,870 --> 00:39:23,660 Mohlo by to jednoducho ísť ďalej a ďalej a ďalej. 780 00:39:23,660 --> 00:39:26,080 Mohlo by to byť nejaké naozaj, Naozaj veľké hodnoty, 781 00:39:26,080 --> 00:39:29,849 ale preto, že vaše hash tabuľky, ktoré ste vytvorili má iba 26 indexy, 782 00:39:29,849 --> 00:39:31,890 chcete uistite sa, že modulusing takže 783 00:39:31,890 --> 00:39:33,848 nie run-- je to to isté vec ako queue-- 784 00:39:33,848 --> 00:39:36,320 takže nemusíte spúšťať off Spodná časť vášho hash funkcie. 785 00:39:36,320 --> 00:39:39,210 >> Chcete zabaliť späť okolo rovnakým spôsobom v [nepočuteľných], keď 786 00:39:39,210 --> 00:39:41,750 ste mal ako veľmi, veľmi veľké písmeno, vy 787 00:39:41,750 --> 00:39:43,740 nechcel, aby stačí spustiť až na koniec. 788 00:39:43,740 --> 00:39:46,948 To isté tu, chcete byť istý, nebeží z konca obalom 789 00:39:46,948 --> 00:39:48,330 okolo hornej časti tabuľky. 790 00:39:48,330 --> 00:39:50,530 Tak to je len veľmi jednoduchá funkcie hash. 791 00:39:50,530 --> 00:39:56,570 Všetko, čo urobila, bolo vziať ako prvý List z akéhokoľvek nášho vstupu bola 792 00:39:56,570 --> 00:40:01,660 a meniť na index, ktorý sme mohli dať do našej tabuľky hash. 793 00:40:01,660 --> 00:40:05,450 >> Jo, a tak ako som povedal predtým, tak, že sme sa vyriešiť kolízií 794 00:40:05,450 --> 00:40:09,330 v našej hash tabuliek majú, To, čomu hovoríme, reťazenie. 795 00:40:09,330 --> 00:40:13,860 Takže ak sa pokúsite vložiť viac slová, ktoré začínajú rovnakú vec, 796 00:40:13,860 --> 00:40:16,145 budete mať jednu hodnotu hash. 797 00:40:16,145 --> 00:40:18,770 Avokádo a jablko, ak ste spustite ho cez naše hash funkcie, 798 00:40:18,770 --> 00:40:21,450 Chystáte sa vám dať Rovnaké číslo, počet 0. 799 00:40:21,450 --> 00:40:24,550 A tak spôsob, ako vyriešiť to je že môžeme vlastne trochu prepojiť 800 00:40:24,550 --> 00:40:27,010 spoločne prostredníctvom spojových zoznamov. 801 00:40:27,010 --> 00:40:29,600 >> A tak v tomto zmysle, vy môžete vidieť druh 802 00:40:29,600 --> 00:40:32,640 o tom, ako dátové štruktúry, ktoré sme sa nastaviť skôr 803 00:40:32,640 --> 00:40:35,870 ako hrozienkami spojený so zoznamom druhu z môže prísť spoločne do jedného. 804 00:40:35,870 --> 00:40:38,860 A potom si môžete vytvoriť ďaleko účinnejšie dátové štruktúry 805 00:40:38,860 --> 00:40:43,350 ktorý zvládne väčšie množstvo Dáta, ktoré dynamicky meniť veľkosť v závislosti 806 00:40:43,350 --> 00:40:44,870 na vašich potrebách. 807 00:40:44,870 --> 00:40:45,620 Všetci jasné? 808 00:40:45,620 --> 00:40:47,580 Každý druh clear o tom, čo sa tu deje? 809 00:40:47,580 --> 00:40:52,110 >> Keby som chcel insert-- čo je to ovocie, ktoré začína, ja neviem, 810 00:40:52,110 --> 00:40:54,726 B, iné ako Berry, banán. 811 00:40:54,726 --> 00:40:55,710 >> Divákov: Blackberry. 812 00:40:55,710 --> 00:40:57,910 >> ANDI PENG: Blackberry, Blackberry. 813 00:40:57,910 --> 00:41:00,530 Kam blackberry ísť sem? 814 00:41:00,530 --> 00:41:04,251 No, my vlastne nie sú triedené to ešte, ale teoreticky 815 00:41:04,251 --> 00:41:06,250 Ak by sme chceli mať túto v abecednom poradí, 816 00:41:06,250 --> 00:41:07,944 kam by mal ísť BlackBerry? 817 00:41:07,944 --> 00:41:09,210 >> Divákov: [Nepočuteľné] 818 00:41:09,210 --> 00:41:11,100 >> ANDI PENG: Presne, po tú, že jo? 819 00:41:11,100 --> 00:41:14,950 Ale pretože je to veľmi ťažké reorder-- Myslím, že je to na vás chlapci. 820 00:41:14,950 --> 00:41:17,920 Vy môžete úplne implementovať, čo chcete. 821 00:41:17,920 --> 00:41:20,730 Čím viac účinný spôsob ako to urobiť snáď 822 00:41:20,730 --> 00:41:24,570 by bolo zoradiť spojené vypísať do abecednom poradí, 823 00:41:24,570 --> 00:41:26,520 a tak, keď ste vkladanie vecí, budete chcieť 824 00:41:26,520 --> 00:41:28,632 si byť istí, o ich zaradenie do abecednom poradí 825 00:41:28,632 --> 00:41:30,590 takže potom, keď ste snažia sa ich hľadať, 826 00:41:30,590 --> 00:41:32,410 nemusíte prejsť všetko. 827 00:41:32,410 --> 00:41:35,290 Viete presne, kde to je, a je to jednoduchšie. 828 00:41:35,290 --> 00:41:39,100 >> Ale ak máte trochu veci poprekladané náhodne, 829 00:41:39,100 --> 00:41:41,420 ste stále bude mať to prechádzať tak ako tak. 830 00:41:41,420 --> 00:41:44,990 A tak, keď som sa chcel len vložiť blackberry tu 831 00:41:44,990 --> 00:41:47,470 a ja som chcel hľadať to, ja viem, oh, ostružina 832 00:41:47,470 --> 00:41:52,012 musí začínať s indexom 1, a tak som viem, okamžite stačí hľadať na 1. 833 00:41:52,012 --> 00:41:53,970 A potom som si trochu prechádzať prepojeného zoznamu 834 00:41:53,970 --> 00:41:56,120 kým sa na BlackBerry, a then-- jo? 835 00:41:56,120 --> 00:41:59,550 >> Divákov: Ak sa snažíte create-- Myslím, že takto je to veľmi jednoduchý hash 836 00:41:59,550 --> 00:42:00,050 funkcie. 837 00:42:00,050 --> 00:42:02,835 A ak by sme chceli robiť viac vrstiev, ktorí radi, 838 00:42:02,835 --> 00:42:05,870 OK, chceme rozdeliť na rovnako ako všetky znaky abecedy 839 00:42:05,870 --> 00:42:09,040 a potom zase rád iný súbor abecedných písmen v rámci, ktorý, 840 00:42:09,040 --> 00:42:11,715 sme uvedenie ako hash Tabuľka v hash tabuľky, 841 00:42:11,715 --> 00:42:13,256 alebo ako funkcia v rámci funkcie? 842 00:42:13,256 --> 00:42:14,880 Alebo je that-- 843 00:42:14,880 --> 00:42:17,510 >> ANDI PENG: Takže vaše hash function-- vaše hash tabuľky 844 00:42:17,510 --> 00:42:19,360 môže byť tak veľký, ako chcete, aby to. 845 00:42:19,360 --> 00:42:21,930 Takže v tomto zmysle, myslel som, to bolo veľmi jednoduché, veľmi 846 00:42:21,930 --> 00:42:25,320 jednoduché pre mňa proste tak nejako na báze listov z prvé slovo. 847 00:42:25,320 --> 00:42:28,690 A tak je tu len 26 možností. 848 00:42:28,690 --> 00:42:32,650 Môžem len dostať 26 z možností 0 až 25, pretože sa môže iba 849 00:42:32,650 --> 00:42:36,510 začať od A do Z. Ale Ak by ste chceli pridať, možno viac zložitosti 850 00:42:36,510 --> 00:42:39,260 alebo rýchlejší beh času, aby svoj hash tabuľky, si absolútne 851 00:42:39,260 --> 00:42:40,760 môžete robiť všetky druhy vecí. 852 00:42:40,760 --> 00:42:43,330 Môžete si vytvoriť svoj vlastný rovnice, ktorá vám dáva 853 00:42:43,330 --> 00:42:48,000 viac rozdelenie vo vašom slová, potom pri vyhľadávaní, 854 00:42:48,000 --> 00:42:49,300 že to bude rýchlejšie. 855 00:42:49,300 --> 00:42:52,100 >> Je to úplne na vás chlapci ako chcete implementovať to. 856 00:42:52,100 --> 00:42:55,140 Myslite na to, ako len vedierka. 857 00:42:55,140 --> 00:42:57,376 Ak by som chcel mať 26 vedierka, idem 858 00:42:57,376 --> 00:42:59,420 triediť veci do týchto vedierka. 859 00:42:59,420 --> 00:43:02,980 Ale ja budem mať veľa vecí v každom vedre, 860 00:43:02,980 --> 00:43:05,890 takže ak chcete, aby to rýchlejšie a efektívnejšie, 861 00:43:05,890 --> 00:43:07,190 dovoľte mi, aby som sto vedierka. 862 00:43:07,190 --> 00:43:09,290 >> Ale potom budete musieť prísť na to, spôsob, nechajte tak, aby boli 863 00:43:09,290 --> 00:43:11,040 v správnom vedra, ktoré by mali byť v. 864 00:43:11,040 --> 00:43:13,331 Ale potom, keď ste vlastne Chcete sa pozrieť na tom vedierko, 865 00:43:13,331 --> 00:43:16,410 je to oveľa rýchlejšie, pretože tam je menej veci v každom segmente. 866 00:43:16,410 --> 00:43:20,250 A tak, jo, to je vlastne trik pre vás v pset5 867 00:43:20,250 --> 00:43:22,360 je to, že budete vyzvaní, aby len vytvoriť 868 00:43:22,360 --> 00:43:26,170 čo je najúčinnejší funkcie si môžete myslieť, že je 869 00:43:26,170 --> 00:43:28,520 schopná ukladať a kontrolovať tieto hodnoty. 870 00:43:28,520 --> 00:43:30,840 >> Úplne na vás chlapci však budete chcieť robiť to, 871 00:43:30,840 --> 00:43:32,229 ale to je naozaj dobrý bod. 872 00:43:32,229 --> 00:43:34,520 Že druh logiky vy chcú začať premýšľať o 873 00:43:34,520 --> 00:43:37,236 Je dobre, tak prečo nie ja robiť viac vedierka. 874 00:43:37,236 --> 00:43:39,527 A potom som musel hľadať menej vecí, a potom možno ja 875 00:43:39,527 --> 00:43:41,640 majú iný hash funkcie. 876 00:43:41,640 --> 00:43:45,500 >> Jo, je tu mnoho spôsobov, ako to dosiahnuť pset, niektoré sú rýchlejšie ako ostatné. 877 00:43:45,500 --> 00:43:50,630 Ja úplne bude len vidieť, ako rýchla bol najrýchlejší chlapci budú 878 00:43:50,630 --> 00:43:55,170 byť schopní dostať svoje funkcie do práce. 879 00:43:55,170 --> 00:43:58,176 OK, všetci dobre na PREPOJENIE ZÁSOB a hashovacie tabuľky? 880 00:43:58,176 --> 00:44:00,800 Je to vlastne ako veľmi jednoduchý koncept, ak si myslíte o tom. 881 00:44:00,800 --> 00:44:05,160 Všetko, čo to je, je oddeľovanie čokoľvek vaše vstupy sú do vedier, 882 00:44:05,160 --> 00:44:10,670 ich triedenie, a potom vyhľadávanie vo uvádza, že je spájaný s. 883 00:44:10,670 --> 00:44:11,852 >> Super. 884 00:44:11,852 --> 00:44:18,160 Dobre, teraz máme iný druh dátové štruktúry, ktoré sa hovorí strom. 885 00:44:18,160 --> 00:44:20,850 Poďme ďalej a hovorí o pokusoch , Ktoré sú zreteľne odlišné, 886 00:44:20,850 --> 00:44:22,330 ale v rovnakej kategórii. 887 00:44:22,330 --> 00:44:29,010 V podstate, všetci strom je miesto organizovanie dát v lineárne 888 00:44:29,010 --> 00:44:32,560 že hash tabuľka vám does-- viem, je to má hornú a spodnú časť 889 00:44:32,560 --> 00:44:37,900 a potom tak nejako prepojiť preč to-- na Strom má hornú ktorý nazývate koreň, 890 00:44:37,900 --> 00:44:40,220 a potom to má listy všetko okolo neho. 891 00:44:40,220 --> 00:44:42,390 >> A tak všetko, čo tu je len na najvyššej uzol 892 00:44:42,390 --> 00:44:45,980 , Ktorý odkazuje na iných uzlov, ktoré body na viac uzlov, a tak ďalej a tak ďalej. 893 00:44:45,980 --> 00:44:48,130 A tak stačí štiepanie vetiev. 894 00:44:48,130 --> 00:44:53,255 Je to len iný spôsob organizácie dát, a pretože sme to strom volanie, 895 00:44:53,255 --> 00:44:56,270 vy jen-- je to len modelovaný von vyzerať ako strom. 896 00:44:56,270 --> 00:44:57,670 To je dôvod, prečo hovoríme, že stromy. 897 00:44:57,670 --> 00:44:59,370 >> Hash tabuľka vyzerá ako tabuľky. 898 00:44:59,370 --> 00:45:01,310 Strom len vyzerá ako strom. 899 00:45:01,310 --> 00:45:03,300 Všetko, čo to je, je samostatná spôsob organizácie uzlov 900 00:45:03,300 --> 00:45:06,020 V závislosti na aké sú vaše potreby. 901 00:45:06,020 --> 00:45:11,810 >> Takže máte koreň a potom máte listy. 902 00:45:11,810 --> 00:45:15,380 Spôsob, akým môžeme obzvlášť premýšľať o tom, že je to binárny strom, 903 00:45:15,380 --> 00:45:18,150 binárny strom je len Špecifickým typom stromu 904 00:45:18,150 --> 00:45:22,450 kde každý uzol len body k, pri max, ďalšie dva uzly. 905 00:45:22,450 --> 00:45:25,434 A tak tu máte odlišný symetria vo vašom strome 906 00:45:25,434 --> 00:45:28,600 že uľahčuje druh vyzerať na aké hodnoty ste, pretože potom vás 907 00:45:28,600 --> 00:45:30,150 majú vždy ľavý alebo pravý. 908 00:45:30,150 --> 00:45:33,150 Tam je nikdy ako ľavé tretinu ľavá alebo štvrtiny z ľavej strany. 909 00:45:33,150 --> 00:45:36,358 Je to len máte doľava a právo a môžete vyhľadávať buď z týchto dvoch. 910 00:45:36,358 --> 00:45:38,980 A prečo je to užitočné? 911 00:45:38,980 --> 00:45:40,980 Spôsob, akým je užitočné, je ak hľadáte 912 00:45:40,980 --> 00:45:42,890 prehľadávať hodnotám, že jo? 913 00:45:42,890 --> 00:45:45,640 Skôr než sa vykonáva binárne hľadať v chybovej poli, 914 00:45:45,640 --> 00:45:49,260 ak by ste chceli mať možnosť vložiť uzly a odniesť uzly na vôli a tiež 915 00:45:49,260 --> 00:45:52,185 zachovať vyhľadávanie kapacity binárne vyhľadávanie. 916 00:45:52,185 --> 00:45:54,560 Takže týmto spôsobom, sme trochu Pamätám si, keď sme tricking-- 917 00:45:54,560 --> 00:45:56,530 povedal spojové zoznamy nemôžu binárne hľadanie? 918 00:45:56,530 --> 00:46:01,700 Sme trochu vytvorenie dátovej štruktúry že triky, ktoré do práce. 919 00:46:01,700 --> 00:46:05,034 >> A to preto, spojové zoznamy sú lineárne, oni len prepojiť jeden po druhom. 920 00:46:05,034 --> 00:46:06,950 Môžeme mať trochu iný druh ukazovateľov 921 00:46:06,950 --> 00:46:09,408 tento bod na rôzne uzly že nám môže pomôcť s vyhľadávaním. 922 00:46:09,408 --> 00:46:12,590 A tak tu, keby som chcel majú strom binárneho vyhľadávania, 923 00:46:12,590 --> 00:46:14,090 Viem, že moje druhé, ak 55. 924 00:46:14,090 --> 00:46:18,280 Ja som jednoducho ísť k vytvoreniu, že ako môj stredu, ako môj koreň, 925 00:46:18,280 --> 00:46:20,770 a potom budem mať Hodnoty spin off z toho. 926 00:46:20,770 --> 00:46:25,610 >> Tak tu, ak budem hľadať hodnotu 66, môžem začať na 55 rokov. 927 00:46:25,610 --> 00:46:27,310 To je 66 vyšší ako 55? 928 00:46:27,310 --> 00:46:30,970 Áno, je to, takže viem, že mus hľadať i n pravý ukazovateľ tohto stromu. 929 00:46:30,970 --> 00:46:32,440 Chodím do 77. 930 00:46:32,440 --> 00:46:35,367 OK, je menšia ako 66 alebo väčší ako 77? 931 00:46:35,367 --> 00:46:37,950 To je menej ako, takže viete, oh, , Ktorý má byť na ľavej strane uzla. 932 00:46:37,950 --> 00:46:41,410 >> A tak tu máme trochu konzervovanie všetky z veľkých vecí, o poli, 933 00:46:41,410 --> 00:46:44,420 tak ako dynamickú zmenu veľkosti objektov, pričom 934 00:46:44,420 --> 00:46:49,530 môcť vkladať a mazať na vôli, bez toho aby sa museli starať o fixné 935 00:46:49,530 --> 00:46:50,370 množstvo priestoru. 936 00:46:50,370 --> 00:46:52,820 Stále sme zachovať všetky tie úžasné veci 937 00:46:52,820 --> 00:46:57,140 a zároveň je schopný sa zachovala log a hľadanie času binárne vyhľadávanie 938 00:46:57,140 --> 00:47:00,450 že sme iba skôr možnosť získať frázu. 939 00:47:00,450 --> 00:47:06,310 >> Pohode dátová štruktúra, druh vykonávaní zložité, uzol. 940 00:47:06,310 --> 00:47:08,311 Ako môžete vidieť, všetky to je struct uzla 941 00:47:08,311 --> 00:47:10,143 je to, že máte vľavo a pravý ukazovateľ. 942 00:47:10,143 --> 00:47:11,044 To je všetko, čo je. 943 00:47:11,044 --> 00:47:12,960 Takže skôr než len majúci x alebo predchádzajúci. 944 00:47:12,960 --> 00:47:15,920 Máte doľava alebo doprava a môžete trochu prepojiť dohromady 945 00:47:15,920 --> 00:47:16,836 Avšak sa tak rozhodnete. 946 00:47:16,836 --> 00:47:21,080 947 00:47:21,080 --> 00:47:24,270 >> OK, sme vlastne bude len trvať niekoľko minút. 948 00:47:24,270 --> 00:47:25,790 Takže budeme vrátiť sa sem. 949 00:47:25,790 --> 00:47:28,270 Ako som už povedal skôr, Tak nejako som vysvetlil, 950 00:47:28,270 --> 00:47:31,520 logika, ako by sa hľadať cez to. 951 00:47:31,520 --> 00:47:33,860 Budeme sa snažiť pseudocoding na to vidieť, 952 00:47:33,860 --> 00:47:38,000 ak môžeme trochu použije Rovnaká logika binárneho vyhľadávania 953 00:47:38,000 --> 00:47:40,055 na iný typ dátové štruktúry. 954 00:47:40,055 --> 00:47:45,049 Ak si chlapci chcú, aby sa ako pár minút, len premýšľať o tom. 955 00:47:45,049 --> 00:48:45,927 956 00:48:45,927 --> 00:48:46,925 OK. 957 00:48:46,925 --> 00:48:51,407 Dobre, budem vlastne len aby vám the-- nie, 958 00:48:51,407 --> 00:48:52,990 budeme hovoriť o pseudocode ako prvý. 959 00:48:52,990 --> 00:48:56,580 Takže to niekto chcel dať stab na to, čo 960 00:48:56,580 --> 00:49:02,100 Prvá vec, ktorú chcete robiť, keď začínate z vyhľadávania? 961 00:49:02,100 --> 00:49:04,460 Ak hľadáme hodnota 66, čo je 962 00:49:04,460 --> 00:49:07,940 Prvá vec, ktorú chceme robiť, keď chceme binárne vyhľadávanie tento strom? 963 00:49:07,940 --> 00:49:10,760 >> Divákov: Chcete vyzerať správne a pozrieť sa vľavo a pozrite [nepočuteľný] 964 00:49:10,760 --> 00:49:11,230 väčší počet. 965 00:49:11,230 --> 00:49:12,271 >> ANDI PENG: Jo, presne tak. 966 00:49:12,271 --> 00:49:15,350 Takže budete pozrieť sa na svoj koreň. 967 00:49:15,350 --> 00:49:18,180 Je tu veľa spôsobov, ako môžete volať to, vaši rodič uzol ľudia hovoria. 968 00:49:18,180 --> 00:49:21,317 Páči sa mi povedať, pretože koreň to je ako koreň stromu. 969 00:49:21,317 --> 00:49:23,400 Budeš sa pozerať na koreňový uzol, a vy ste 970 00:49:23,400 --> 00:49:26,940 ide vidieť, je 66 vyšší alebo menšie ako 55. 971 00:49:26,940 --> 00:49:30,360 A ak je to väčšie ako, no, to je väčší než tam, kde chceme vyzerať? 972 00:49:30,360 --> 00:49:32,000 Kde chceme hľadať, nie? 973 00:49:32,000 --> 00:49:34,340 Chceme prehľadať Pravá polovica tohto stromu. 974 00:49:34,340 --> 00:49:38,390 >> Takže máme, pohodlne, je ukazovateľ, ktorý ukazuje na pravej strane. 975 00:49:38,390 --> 00:49:44,325 A tak potom môžeme nastaviť náš nový koreň byť 77. 976 00:49:44,325 --> 00:49:46,450 Môžeme jednoducho ísť kamkoľvek pointer ukazuje. 977 00:49:46,450 --> 00:49:49,100 No, oh, tu začíname na 77, a môžeme len 978 00:49:49,100 --> 00:49:51,172 to rekurzívne znova a znova. 979 00:49:51,172 --> 00:49:52,880 Týmto spôsobom, tak nejako o majú funkciu. 980 00:49:52,880 --> 00:49:57,430 Máte spôsob vyhľadávania, ktoré vás stačí opakovať znovu a znovu a znovu, 981 00:49:57,430 --> 00:50:02,720 podľa toho, kde sa chcete pozrieť až sa nakoniec dostal na hodnotu 982 00:50:02,720 --> 00:50:04,730 ktoré hľadáte. 983 00:50:04,730 --> 00:50:05,230 Dáva zmysel? 984 00:50:05,230 --> 00:50:07,800 >> Chystám sa vám ukázať skutočný kódu, a je to veľa kódu. 985 00:50:07,800 --> 00:50:08,674 Nie je potrebné šalieť. 986 00:50:08,674 --> 00:50:09,910 Porozprávame sa cez to. 987 00:50:09,910 --> 00:50:13,410 988 00:50:13,410 --> 00:50:14,020 >> V skutočnosti, no. 989 00:50:14,020 --> 00:50:15,061 To bol len pseudokód. 990 00:50:15,061 --> 00:50:17,860 OK, to bol len pseudokód, ktorý je trochu zložitejšie, 991 00:50:17,860 --> 00:50:19,751 ale je to úplne v poriadku. 992 00:50:19,751 --> 00:50:21,000 Každý, kto po pozdĺž tu? 993 00:50:21,000 --> 00:50:24,260 Ak je koreň je null, návrat false pretože to znamená 994 00:50:24,260 --> 00:50:26,850 vy ani nemusíte nič tam. 995 00:50:26,850 --> 00:50:31,376 >> Ak je koreň n je hodnota, takže ak je sa stane byť ten, že ste pri pohľade na, 996 00:50:31,376 --> 00:50:34,000 potom budete vráti hodnotu true pretože viete, že ste ju našli. 997 00:50:34,000 --> 00:50:36,250 Ale ak je táto hodnota nižšia než root n, ty si 998 00:50:36,250 --> 00:50:38,332 bude hľadať ľavý dieťa alebo ľavé krídlo, 999 00:50:38,332 --> 00:50:39,540 čo chcete hovoriť. 1000 00:50:39,540 --> 00:50:41,750 A ak je hodnota vyššia ako root, budete hľadať ten správny strom, 1001 00:50:41,750 --> 00:50:44,610 potom stačí spustiť funkciu pomocou vyhľadávania znova. 1002 00:50:44,610 --> 00:50:48,037 >> A ak koreň je null, že znamená, že ste prišli na koniec? 1003 00:50:48,037 --> 00:50:50,120 To znamená, že nemáte Viac odchádza hľadať, 1004 00:50:50,120 --> 00:50:52,230 potom viete, oh, ja Asi to nie je v tú 1005 00:50:52,230 --> 00:50:55,063 pretože po Díval som sa cez celá vec a nie je to tu, 1006 00:50:55,063 --> 00:50:56,930 to jednoducho nemusí byť tu. 1007 00:50:56,930 --> 00:50:58,350 >> Znamená to, že zmysel pre všetkých? 1008 00:50:58,350 --> 00:51:03,230 Takže je to ako binárny vyhľadávanie konzervačným Schopnosti prepojených zoznamov. 1009 00:51:03,230 --> 00:51:09,200 Cool, a tak druhý typ dátové štruktúry vy chlapci 1010 00:51:09,200 --> 00:51:13,180 môžu vyskúšať vykonávanie na pset, máte len vybrať jednu metódu. 1011 00:51:13,180 --> 00:51:19,430 Ale možno alternatívnou metódou hash tabuľka je to, čo nazývame trie. 1012 00:51:19,430 --> 00:51:24,080 >> Všetko, Trie je je Špecifickým typom stromu 1013 00:51:24,080 --> 00:51:28,600 má hodnoty, ktoré idú na iné hodnoty. 1014 00:51:28,600 --> 00:51:31,450 A tak namiesto toho, binárne strom v tom zmysle, že iba jedna 1015 00:51:31,450 --> 00:51:35,940 vec môže poukázať na dva, môžete mať jedna vec, prejdite na mnoho, mnoho vecí. 1016 00:51:35,940 --> 00:51:39,450 Tie majú v zásade pole vnútri ktoré ukladáte 1017 00:51:39,450 --> 00:51:41,790 ukazovatele, ktoré ukazujú na iné pole. 1018 00:51:41,790 --> 00:51:45,210 1019 00:51:45,210 --> 00:51:49,460 >> Takže uzol, ako by definoval trie 1020 00:51:49,460 --> 00:51:52,590 ich chceme mať Boolean, c slovo, že jo? 1021 00:51:52,590 --> 00:51:54,920 Takže uzol je Boolean ako pravdivé alebo nepravdivé, 1022 00:51:54,920 --> 00:51:58,490 v prvom rade na čele že pole, je to slovo? 1023 00:51:58,490 --> 00:52:03,620 Po druhé, chcete mať ukazovatele sa bez ohľadu na ostatné z nich sú. 1024 00:52:03,620 --> 00:52:07,470 Trochu zložitejšie, trochu abstraktné, ale Budem vysvetľovať, čo to všetky prostriedky. 1025 00:52:07,470 --> 00:52:13,800 >> Tak tu, na vrchole, ak ste majú celý rad deklaroval už, 1026 00:52:13,800 --> 00:52:17,040 uzol, kde máte Boolean hodnota uložená na prednej strane 1027 00:52:17,040 --> 00:52:19,490 ktorý vám povie, je to slovo? 1028 00:52:19,490 --> 00:52:20,520 Nie je to slovo? 1029 00:52:20,520 --> 00:52:23,240 A potom máte zvyšok vášho pole, ktoré 1030 00:52:23,240 --> 00:52:26,040 v skutočnosti ukladá všetky možnosti toho, čo by to mohlo byť. 1031 00:52:26,040 --> 00:52:28,660 Tak, napríklad, ako je hore máte 1032 00:52:28,660 --> 00:52:32,140 Prvá vec, ktorá hovorí, že pravda alebo false, áno alebo nie, to je slovo. 1033 00:52:32,140 --> 00:52:38,130 >> A potom máte 0 až 26 písmená, ktoré môžete uložiť. 1034 00:52:38,130 --> 00:52:42,790 Ak by som chcel hľadať tu pre bat, idem na vrchol 1035 00:52:42,790 --> 00:52:49,200 a ja sa pre B. nájdem B v mojom poľa, a tak viem, v poriadku, je B slovo? 1036 00:52:49,200 --> 00:52:53,010 B nie je slovo, takže sa tak Musím pokračovať v hľadaní. 1037 00:52:53,010 --> 00:52:56,410 Idem z B, a ja sa k ukazovateľ, ktorý ukazuje na B 1038 00:52:56,410 --> 00:53:00,900 a vidím iný rad informácií, rovnakú štruktúru, ktoré sme predtým. 1039 00:53:00,900 --> 00:53:05,240 >> A here-- oh, ďalšie List v [nepočuteľný] je A. 1040 00:53:05,240 --> 00:53:07,210 Takže sa pozrieme v tomto poli. 1041 00:53:07,210 --> 00:53:10,860 Nájdeme ôsmy hodnotu, a potom sa pozrieme vidieť, oh, 1042 00:53:10,860 --> 00:53:12,840 hej, je to jedným slovom, je B-A slovo? 1043 00:53:12,840 --> 00:53:13,807 Nejedná sa o slovo. 1044 00:53:13,807 --> 00:53:14,890 Musíme hľadať ďalej. 1045 00:53:14,890 --> 00:53:17,850 >> A tak potom sa pozrieme na miesto, kde ukazovateľ z A bodov, 1046 00:53:17,850 --> 00:53:21,130 a odkazuje na iný spôsob v ktorý máme väčšiu hodnotu uloží do pamäte. 1047 00:53:21,130 --> 00:53:24,150 A nakoniec sme sa dostať do B-A-T, čo je slovo. 1048 00:53:24,150 --> 00:53:25,970 A tak sa nabudúce vyzeráš, budete 1049 00:53:25,970 --> 00:53:30,850 mať tento kontrolu, áno, táto Boolean funkcie je pravda. 1050 00:53:30,850 --> 00:53:35,450 A tak sa v tom zmysle, že sme trochu mať strom s poli. 1051 00:53:35,450 --> 00:53:39,890 >> Takže môžete trochu hľadať nadol. 1052 00:53:39,890 --> 00:53:43,650 Skôr než hash funkcie a priradenie hodnôt Google zoznamu 1053 00:53:43,650 --> 00:53:49,190 môžete len implementovať Trie, ktorý prehľadáva downwords. 1054 00:53:49,190 --> 00:53:50,850 Naozaj, naozaj zložité veci. 1055 00:53:50,850 --> 00:53:54,060 Nie je ľahké si myslieť, o, pretože som rád pľuvať toľko dátových štruktúr out 1056 00:53:54,060 --> 00:53:58,710 na vás, ale robí každý druh pochopiť, ako logika to funguje? 1057 00:53:58,710 --> 00:54:01,920 >> OK v pohode. 1058 00:54:01,920 --> 00:54:05,600 A tak B-A-T, a potom sa budete hľadať. 1059 00:54:05,600 --> 00:54:07,940 Nabudúce ideš vidieť, oh, hej, to je pravda, 1060 00:54:07,940 --> 00:54:09,273 Viem, že to tak musí byť slovo. 1061 00:54:09,273 --> 00:54:12,030 1062 00:54:12,030 --> 00:54:13,770 >> To isté pre zoo. 1063 00:54:13,770 --> 00:54:17,960 Tak tu je to práve teraz, keď sme chcel hľadať zoo, práve teraz, 1064 00:54:17,960 --> 00:54:20,780 V súčasnej dobe zoo nie je slovo v našom slovníku 1065 00:54:20,780 --> 00:54:25,300 pretože, ako vy môžete vidieť, Prvé miesto, ktoré máme Boolean 1066 00:54:25,300 --> 00:54:28,590 vráti pravda, je na konci zoom. 1067 00:54:28,590 --> 00:54:30,430 Máme Z-O-O-M. 1068 00:54:30,430 --> 00:54:33,900 >> A tak tu, nemáme vlastne mať Slovo, zoo, v našom slovníku 1069 00:54:33,900 --> 00:54:36,070 preto, že toto políčko nie je začiarknuté. 1070 00:54:36,070 --> 00:54:39,540 Takže počítač nie je vedia, že zoo je slovo, 1071 00:54:39,540 --> 00:54:42,430 pretože tak, že máme uložil to, len zoom tu 1072 00:54:42,430 --> 00:54:44,920 v skutočnosti má logickú hodnotu , Ktorá bola obrátil pravda. 1073 00:54:44,920 --> 00:54:49,380 Takže ak chceme vložiť slovo, zoo, do nášho slovníka, 1074 00:54:49,380 --> 00:54:51,770 ako by sme ísť o tom, že? 1075 00:54:51,770 --> 00:54:55,960 Čo musíme urobiť, aby sa ubezpečil, naša počítač vie, že Z-O-O je slovo 1076 00:54:55,960 --> 00:54:58,130 a nie prvý slovo je Z-O-O-M? 1077 00:54:58,130 --> 00:54:59,360 >> Divákov: [Nepočuteľné] 1078 00:54:59,360 --> 00:55:01,450 >> ANDI PENG: Presne tak, my chcete, aby sa ubezpečil, že tento 1079 00:55:01,450 --> 00:55:07,890 tu, že logická hodnota odškrtnúť, že je to pravda. 1080 00:55:07,890 --> 00:55:13,297 Z-O-O, potom budeme kontrolovať, či, takže presne vieme, hej, zoo je slovo. 1081 00:55:13,297 --> 00:55:15,380 Chystám sa povedať, Počítač, ktorý je to slovo tak 1082 00:55:15,380 --> 00:55:18,000 že keď je počítač kontroly, vie, že zoo je slovo. 1083 00:55:18,000 --> 00:55:21,269 >> Vzhľadom k tomu, spomenúť na všetky tieto údaje štruktúry, je to pre nás veľmi ľahké 1084 00:55:21,269 --> 00:55:22,310 povedať, oh, netopier je to slovo. 1085 00:55:22,310 --> 00:55:22,851 Zoo je to slovo. 1086 00:55:22,851 --> 00:55:23,611 Priblížiť to slovo. 1087 00:55:23,611 --> 00:55:25,860 Ale keď ste ho stavia, počítač nemá ani poňatia. 1088 00:55:25,860 --> 00:55:28,619 >> Takže musíte to povedať presne na akom mieste je to slovo? 1089 00:55:28,619 --> 00:55:29,910 V akom okamihu nie je to slovo? 1090 00:55:29,910 --> 00:55:31,784 A na akom mieste robiť ja je potrebné hľadať veci, 1091 00:55:31,784 --> 00:55:34,000 a na akom mieste sa musím ísť ďalej? 1092 00:55:34,000 --> 00:55:37,010 Každý jasné, že? 1093 00:55:37,010 --> 00:55:39,540 Super. 1094 00:55:39,540 --> 00:55:42,530 >> A tak potom príde Problém, ako by sme sa 1095 00:55:42,530 --> 00:55:45,560 ísť o vloženie niečo že to vlastne nie je? 1096 00:55:45,560 --> 00:55:49,090 Takže povedzme, že chceme vložiť Slovo, kúpele, do nášho trie. 1097 00:55:49,090 --> 00:55:53,589 Ako vy môžete vidieť, ako v súčasnej dobe všetko, čo máme teraz, je B-A-T, 1098 00:55:53,589 --> 00:55:55,630 a táto nová štruktúra dát tam mal polliter, ktorý 1099 00:55:55,630 --> 00:55:59,740 poukázal na hodnotu null, pretože predpokladáme, že, oh, je tu po B-A-T žiadne slová, 1100 00:55:59,740 --> 00:56:02,530 prečo potrebujeme zachovať majú veci po tomto T. 1101 00:56:02,530 --> 00:56:06,581 >> Problém však nastáva, keď budeme robiť vás chcú mať slovo, ktoré prichádza po 1102 00:56:06,581 --> 00:56:07,080 T je. 1103 00:56:07,080 --> 00:56:09,500 Ak máte vaňu, ste bude chcieť H právo. 1104 00:56:09,500 --> 00:56:13,290 A tak spôsob, akým budeme k tomu, že je budeme vytvoriť samostatný uzol. 1105 00:56:13,290 --> 00:56:16,840 Nie sme prideliť bez ohľadu na čiastku, pamäte pre toto nové pole, 1106 00:56:16,840 --> 00:56:20,720 a budeme priradiť ukazovatele. 1107 00:56:20,720 --> 00:56:22,947 >> Budeme priradiť H, Po prvé, to null, 1108 00:56:22,947 --> 00:56:24,030 budeme zbaviť. 1109 00:56:24,030 --> 00:56:26,590 Budeme mať Bod H smerom nadol. 1110 00:56:26,590 --> 00:56:30,600 Ak vidíme H, chceme ho ísť niekam inam. 1111 00:56:30,600 --> 00:56:33,910 >> Tu, potom môžeme odškrtnúť áno. 1112 00:56:33,910 --> 00:56:38,170 Ak by sme hit H po T, oh, potom vieme, že sa jedná o slovo. 1113 00:56:38,170 --> 00:56:41,110 Boolean sa chystá vrátiť true. 1114 00:56:41,110 --> 00:56:42,950 Všetci jasné, o tom, ako sa to stalo? 1115 00:56:42,950 --> 00:56:45,110 OK. 1116 00:56:45,110 --> 00:56:47,214 >> Takže v podstate všetky Tieto dátové štruktúry 1117 00:56:47,214 --> 00:56:50,130 že sme prešli dnes, som naozaj, ale naozaj rýchlo preč nad nimi 1118 00:56:50,130 --> 00:56:52,192 a nie v oveľa detail, a to je v poriadku. 1119 00:56:52,192 --> 00:56:53,900 Akonáhle začnete umazávání s tým, budete 1120 00:56:53,900 --> 00:56:55,733 sledovanie, kde Všetky ukazovatele sú, 1121 00:56:55,733 --> 00:56:58,060 čo sa deje vo vašom dátové štruktúry, a tak ďalej. 1122 00:56:58,060 --> 00:56:59,810 Budú veľmi užitočné, a je len na vás, 1123 00:56:59,810 --> 00:57:03,890 chlapci úplne zistiť, ako Ak chcete implementovať veci. 1124 00:57:03,890 --> 00:57:07,650 >> A tak pset4, z 5-- oh, to je zlé. 1125 00:57:07,650 --> 00:57:10,140 Pset5 je preklepy. 1126 00:57:10,140 --> 00:57:13,710 Ako som už povedal skôr, budete, akonáhle Znova, stiahnite zdrojový kód od nás. 1127 00:57:13,710 --> 00:57:16,210 Tam to bude Tri hlavné veci, ktoré budete sťahovať. 1128 00:57:16,210 --> 00:57:18,470 Budete stiahnuť slovníky, KERS, a texty. 1129 00:57:18,470 --> 00:57:21,660 >> Všetky tieto veci sú, sú buď slovníky slov 1130 00:57:21,660 --> 00:57:25,190 že chceme, aby ste skontrolovať alebo test informácií 1131 00:57:25,190 --> 00:57:26,930 že chceme, aby ste kontrolu pravopisu. 1132 00:57:26,930 --> 00:57:29,670 A tak sa slovníky dáme idete 1133 00:57:29,670 --> 00:57:34,870 aby vám aktuálne slová, ktoré chceme ukladať nejako spôsobom, ktorý je 1134 00:57:34,870 --> 00:57:36,530 účinnejší ako pole. 1135 00:57:36,530 --> 00:57:38,470 A potom texty sú Bude to, čo sme 1136 00:57:38,470 --> 00:57:43,900 so žiadosťou o kontrolu pravopisu, aby sa uistil všetky slová existujú skutočné slová. 1137 00:57:43,900 --> 00:57:47,970 >> A tak tri bloky programy, ktoré dáme vám 1138 00:57:47,970 --> 00:57:51,130 sa nazývajú dictionary.c, dictionary.h, a speller.c. 1139 00:57:51,130 --> 00:57:56,500 A tak všetci dictionary.c robí, je čo ste vyzvaní k realizácii. 1140 00:57:56,500 --> 00:57:57,880 To načíta slová. 1141 00:57:57,880 --> 00:58:02,000 To kúzlo je skontroluje, a to je istý, že všetko je správne vložený. 1142 00:58:02,000 --> 00:58:05,180 >> diction.h je len súbor knižnice že deklaruje všetky tieto funkcie. 1143 00:58:05,180 --> 00:58:07,650 A speller.c, budeme dať. 1144 00:58:07,650 --> 00:58:09,290 Nemusíte meniť nič z toho. 1145 00:58:09,290 --> 00:58:14,290 Všetky speller.c robí, je vziať to, Zaťaženie to, kontroluje rýchlosť na to, 1146 00:58:14,290 --> 00:58:19,190 testuje meradlo ako ako rýchlo ste schopní robiť veci. 1147 00:58:19,190 --> 00:58:20,410 >> Je to Speller. 1148 00:58:20,410 --> 00:58:23,920 Jednoducho to nie je neporiadok s ním, ale urobiť sa, že ste pochopili, čo to robí. 1149 00:58:23,920 --> 00:58:28,090 Používame funkciu nazvanú getrusage že testuje výkon svojho kúzla 1150 00:58:28,090 --> 00:58:28,590 checker. 1151 00:58:28,590 --> 00:58:32,200 Všetko, čo to robí, je v podstate otestovanie Čas všetko vo vašom slovníku, 1152 00:58:32,200 --> 00:58:33,680 takže sa uistite, ste to pochopili. 1153 00:58:33,680 --> 00:58:36,660 Buďte opatrní, aby neporiadok s ním, alebo inde sa veci nebude fungovať správne. 1154 00:58:36,660 --> 00:58:39,740 1155 00:58:39,740 --> 00:58:44,170 >> A Prevažná časť tohto problému je pre vy naozaj zmeniť dictionary.c. 1156 00:58:44,170 --> 00:58:48,526 Budeme vám 140.000 slov v slovníku. 1157 00:58:48,526 --> 00:58:50,900 Budeme vám textu súbor, ktorý má tieto slová, 1158 00:58:50,900 --> 00:58:54,840 a chceme, aby ste boli schopní zorganizovať je do tabuľky hash alebo trie 1159 00:58:54,840 --> 00:58:58,140 pretože keď vás žiadame, aby bolo zrejmé check-- predstavte si, že ste kúzlo 1160 00:58:58,140 --> 00:59:00,690 kontrola ako Homerovi Odysseia. 1161 00:59:00,690 --> 00:59:03,010 Je to ako obrovský, obrovský tento test. 1162 00:59:03,010 --> 00:59:05,190 >> Predstavte si, že každý slovo, ktoré sa musel pozrieť 1163 00:59:05,190 --> 00:59:08,100 prostredníctvom série 140.000 hodnôt. 1164 00:59:08,100 --> 00:59:10,350 To by trvalo večnosť pre váš počítač spustiť. 1165 00:59:10,350 --> 00:59:14,490 To je dôvod, prečo chceme organizujeme dáta do efektívnejších dátových štruktúr 1166 00:59:14,490 --> 00:59:17,270 ako je napríklad hashovacie tabuľky alebo trie. 1167 00:59:17,270 --> 00:59:20,700 A potom vy môžete druh o pri hľadaní prístupe 1168 00:59:20,700 --> 00:59:22,570 veci ľahšie a rýchlejšie. 1169 00:59:22,570 --> 00:59:24,934 >> A tak buďte opatrní na riešenie kolízií. 1170 00:59:24,934 --> 00:59:27,350 Budeš mať veľa zo slov, ktoré začínajú A. 1171 00:59:27,350 --> 00:59:29,957 Budeš mať veľa slov že začať s B. Až do vás 1172 00:59:29,957 --> 00:59:31,290 chlapi, ako chcete ho riešiť. 1173 00:59:31,290 --> 00:59:34,144 Možno, že tam je viac efektívne funkcie hash 1174 00:59:34,144 --> 00:59:36,810 než len prvým písmenom niečo, a tak to je len na vás 1175 00:59:36,810 --> 00:59:38,190 chlapci druh robiť, čo chcete. 1176 00:59:38,190 --> 00:59:40,148 >> Možno chcete pridať všetky listy dohromady. 1177 00:59:40,148 --> 00:59:43,410 Možno chcete páčiť robiť divné veci na účet počtu písmen, 1178 00:59:43,410 --> 00:59:43,970 Hocičo. 1179 00:59:43,970 --> 00:59:45,386 Až vás chalani, ako chcete robiť. 1180 00:59:45,386 --> 00:59:49,262 Ak si chcete urobiť hash tabuľky, ak ste chcete pokúsiť o Trie, úplne na vás. 1181 00:59:49,262 --> 00:59:52,470 Budem vás varovať vopred, že Trie je zvyčajne o niečo zložitejšie 1182 00:59:52,470 --> 00:59:54,520 len preto, že je tu veľa ďalšie ukazovatele sledovať. 1183 00:59:54,520 --> 00:59:55,645 Ale úplne na vás chlapci. 1184 00:59:55,645 --> 00:59:58,742 Je to oveľa efektívnejšie vo väčšine prípadov. 1185 00:59:58,742 --> 01:00:01,450 Ak chcete byť naozaj schopná udržať prehľad o všetkých vašich ukazovateľov. 1186 01:00:01,450 --> 01:00:03,850 Ako urobiť to isté že som tu. 1187 01:00:03,850 --> 01:00:06,871 Keď sa snažíte vložiť Hodnoty do tabuľky hash alebo odstrániť, 1188 01:00:06,871 --> 01:00:08,620 uistite sa, že ste Naozaj sledovanie 1189 01:00:08,620 --> 01:00:11,860 kde je všetko preto, je to pre či som rýchle 1190 01:00:11,860 --> 01:00:14,727 pokúšate vložiť rád slovo, Andy. 1191 01:00:14,727 --> 01:00:16,810 Povedzme, že je to skutočné slovo, slovo, andy, 1192 01:00:16,810 --> 01:00:19,640 do obrie zozname A slov. 1193 01:00:19,640 --> 01:00:22,450 >> Keby som náhodou preradiť ukazovateľ zle, oops, 1194 01:00:22,450 --> 01:00:24,940 tam jede celistvosť zvyšok môjho Google zoznamu. 1195 01:00:24,940 --> 01:00:26,897 Teraz jediné slovo, ktoré som majú, je Andy, a teraz 1196 01:00:26,897 --> 01:00:29,230 všetky ostatné slová v Slovník boli stratené. 1197 01:00:29,230 --> 01:00:31,370 A tak sa chcete uistiť, že sledovať všetky vaše ukazovateľov 1198 01:00:31,370 --> 01:00:33,661 inak budete mať obrovské problémy v kóde. 1199 01:00:33,661 --> 01:00:35,840 Remíza veci starostlivo krok za krokom. 1200 01:00:35,840 --> 01:00:37,870 To robí to oveľa jednoduchšie myslieť. 1201 01:00:37,870 --> 01:00:40,910 >> A konečne, chcete byť schopní otestovať výkon vášho programu 1202 01:00:40,910 --> 01:00:41,618 na veľké doske. 1203 01:00:41,618 --> 01:00:43,710 Ak vy trvať pozrite sa na CS50 práve teraz, 1204 01:00:43,710 --> 01:00:45,210 máme to, čo sa nazýva veľký doska. 1205 01:00:45,210 --> 01:00:50,200 Je to skóre list najrýchlejší kúzlo časov kontrolné naprieč všetkými CS50 1206 01:00:50,200 --> 01:00:55,720 práve teraz, myslím, že na vrchol ako 10 Časy Myslím si, že osem z nich sú zamestnancami. 1207 01:00:55,720 --> 01:00:57,960 Naozaj chceme vy, aby nás porazil. 1208 01:00:57,960 --> 01:01:00,870 >> Každý z nás sa snaží realizovať najrýchlejší kód ako je to možné. 1209 01:01:00,870 --> 01:01:04,880 Chceme, aby si chlapci, aby sa pokúsili napadnúť nás a realizovať rýchlejšie, ako my všetci 1210 01:01:04,880 --> 01:01:05,550 môcť. 1211 01:01:05,550 --> 01:01:07,970 A tak to je naozaj to prvýkrát, čo sme 1212 01:01:07,970 --> 01:01:12,680 dotazom vám chalani urobiť pset ktorý si môžete naozaj robiť v akejkoľvek metóde 1213 01:01:12,680 --> 01:01:13,760 chceš. 1214 01:01:13,760 --> 01:01:17,730 >> Vždy hovorím, to je viac podobný do reálneho života riešenia, nie? 1215 01:01:17,730 --> 01:01:19,550 Ja hovorím, hej, musíš to urobiť. 1216 01:01:19,550 --> 01:01:21,380 Postaviť program, ktorý robí to pre mňa. 1217 01:01:21,380 --> 01:01:22,630 Urob to však budete chcieť. 1218 01:01:22,630 --> 01:01:24,271 Ja len viem, že chcem, aby rýchlo. 1219 01:01:24,271 --> 01:01:25,770 To je vaša výzva pre tento týždeň. 1220 01:01:25,770 --> 01:01:27,531 Vy chlapi, ideme aby vám úloha. 1221 01:01:27,531 --> 01:01:29,030 Budeme vám výzvu. 1222 01:01:29,030 --> 01:01:31,559 A potom je to na vás chlapci úplne len prísť na to, 1223 01:01:31,559 --> 01:01:34,100 čo je najrýchlejší a najviac účinný spôsob, ako realizovať to. 1224 01:01:34,100 --> 01:01:34,600 Jo? 1225 01:01:34,600 --> 01:01:37,476 >> Divákov: Sme dovolené, pokiaľ chcel vyhľadajte rýchlejšie spôsoby 1226 01:01:37,476 --> 01:01:40,821 robiť hash tabuľky on-line, môžeme to urobiť že a citujú kód niekoho iného? 1227 01:01:40,821 --> 01:01:42,070 ANDI PENG: Jo, úplne v pohode. 1228 01:01:42,070 --> 01:01:44,320 Takže ak vy prečítať spec, je tu rad 1229 01:01:44,320 --> 01:01:48,310 v spec, ktorý hovorí, že chlapci sú úplne zadarmo a vyhľadajte hash 1230 01:01:48,310 --> 01:01:51,070 funkcie na aké sú niektoré z rýchlejší hash funkcie 1231 01:01:51,070 --> 01:01:54,720 bežať veci skrze as dlho, ako vám citovať, že kód. 1232 01:01:54,720 --> 01:01:57,220 Takže niektorí ľudia už prišiel na to, rýchle postupy 1233 01:01:57,220 --> 01:02:00,250 robenie preklepov, rýchleho spôsoby ukladania informácií. 1234 01:02:00,250 --> 01:02:02,750 Úplne na vás chlapci, ak vás chcú len brať, že jo? 1235 01:02:02,750 --> 01:02:04,045 Uistite sa, že ste s odvolaním. 1236 01:02:04,045 --> 01:02:06,170 Výzvou tu naozaj že sa snažíme testovať 1237 01:02:06,170 --> 01:02:09,750 je uistiť sa, že viete, svoju cestu okolo ukazovatele. 1238 01:02:09,750 --> 01:02:12,700 Tak ďaleko, ako sa robí skutočné funkcie hash 1239 01:02:12,700 --> 01:02:15,070 a prichádza s podobne matematika k tomu, že, 1240 01:02:15,070 --> 01:02:17,570 vy môžete výskum čokoľvek metódy on-line chlapci chcú. 1241 01:02:17,570 --> 01:02:17,996 Jo? 1242 01:02:17,996 --> 01:02:19,700 >> Divákov: Môžeme uviesť len pomocou [nepočuteľných]? 1243 01:02:19,700 --> 01:02:20,120 >> ANDI PENG: Jo. 1244 01:02:20,120 --> 01:02:22,328 Stačí si len, vo váš komentár, môžete citovať ako, oh, 1245 01:02:22,328 --> 01:02:26,127 prevzaté z Yada, bla, bla, hashovacie funkcie. 1246 01:02:26,127 --> 01:02:27,210 Každý, kto má nejaké otázky? 1247 01:02:27,210 --> 01:02:29,694 Vlastne sme breezed úsekom dnes. 1248 01:02:29,694 --> 01:02:31,610 Budem sa sem odpovedať na otázky rovnako. 1249 01:02:31,610 --> 01:02:36,570 >> Tiež, ako som povedal, kancelárske hodín dnes večer a zajtra. 1250 01:02:36,570 --> 01:02:40,307 Spec tento týždeň je vlastne super ľahké a super krátky čítať. 1251 01:02:40,307 --> 01:02:43,140 Navrhoval by som, že pohľad, len prečítať celé to. 1252 01:02:43,140 --> 01:02:45,730 >> A Zamyla vás vlastne prechádzky cez každú z funkcií 1253 01:02:45,730 --> 01:02:49,796 budete musieť implementovať, a tak je to veľmi, veľmi jasné, ako to urobiť všetko. 1254 01:02:49,796 --> 01:02:51,920 Len aby sa ubezpečil, že ste sledovanie ukazovateľov. 1255 01:02:51,920 --> 01:02:53,650 Jedná sa o veľmi náročný pset. 1256 01:02:53,650 --> 01:02:56,744 >> Nie je to náročné, pretože rád, oh, pojmy sú tak oveľa viac 1257 01:02:56,744 --> 01:02:59,160 ťažké, musíte sa naučiť tak veľa nového syntaxe cesta 1258 01:02:59,160 --> 01:03:00,650 že ste na poslednú pset. 1259 01:03:00,650 --> 01:03:03,320 To pset je ťažké, pretože existuje toľko ukazovatele, 1260 01:03:03,320 --> 01:03:06,980 a potom je to veľmi, veľmi jednoduché, akonáhle máte chybu v kóde nebudú môcť 1261 01:03:06,980 --> 01:03:08,315 zistiť, kde, že chyba je. 1262 01:03:08,315 --> 01:03:13,200 >> A tak naprostý vieru vo vás chlapi, aby mohli poraziť našich [nepočuteľných] 1263 01:03:13,200 --> 01:03:13,700 hláskovanie. 1264 01:03:13,700 --> 01:03:16,640 Ja vlastne nemám žiadny písomný baňa ešte, ale ja som to písal ja. 1265 01:03:16,640 --> 01:03:19,070 Takže zatiaľ čo píšete vaše, budem písať moje. 1266 01:03:19,070 --> 01:03:21,070 Budem sa snažiť, aby moja rýchlejšie ako vaše. 1267 01:03:21,070 --> 01:03:23,940 Uvidíme, kto má najrýchlejší jeden. 1268 01:03:23,940 --> 01:03:27,340 >> A jo, budem vidieť všetky vy tu v utorok. 1269 01:03:27,340 --> 01:03:29,510 Budem spustiť akýsi sa ako pset dielni. 1270 01:03:29,510 --> 01:03:32,640 Všetky sekciách tohto týždeň sú pset dielne, 1271 01:03:32,640 --> 01:03:36,690 takže si chlapci majú veľa možností o pomoc, úradné hodiny ako vždy, 1272 01:03:36,690 --> 01:03:41,330 a ja sa naozaj teším na čítanie všetci kódu vašich chlapci. 1273 01:03:41,330 --> 01:03:44,160 Mám vypočúva tu, ak vás chlapci chcú ísť dostať tie. 1274 01:03:44,160 --> 01:03:45,880 To je všetko. 1275 01:03:45,880 --> 01:03:48,180