1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [Muzikos grojimo] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID Malan: Tai CS50. 5 00:00:14,010 --> 00:00:18,090 Ir tai yra tiek pradžia ir end-- kaip literally-- beveik pabaigoje 6 00:00:18,090 --> 00:00:18,825 Šešių savaitę. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Aš maniau aš pasidalinti Šiek tiek įdomus faktas. 9 00:00:22,640 --> 00:00:25,370 Aš iškedentas tai iki iš praėjusių semestro duomenų rinkinys. 10 00:00:25,370 --> 00:00:29,710 Kaip Jūs tikriausiai žinote, kad mes prašome jus kiekvieną p Formą jei jūs stebėjo internete 11 00:00:29,710 --> 00:00:31,580 arba, jei jau dalyvavo asmeniškai. 12 00:00:31,580 --> 00:00:33,020 Ir čia yra duomenys. 13 00:00:33,020 --> 00:00:34,710 Taigi šiandien buvo labai nuspėjamas. 14 00:00:34,710 --> 00:00:37,126 Bet mes norėjome išleisti šiek tiek laiko su jumis vis. 15 00:00:37,126 --> 00:00:40,599 Gal kas norėtų spėlioti, kodėl šis grafikas yra toks nelygus, aukštyn žemyn, aukštyn žemyn, 16 00:00:40,599 --> 00:00:41,265 taip nuosekliai? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Ką kiekvienas smailių ir latakai atstovauti? 19 00:00:45,130 --> 00:00:46,005 >> AUDITORIJA: [nesigirdi] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID Malan: Iš tiesų. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 Ir daugiau Įdomiai, neduok Dieve, mes manome, vieną paskaitą penktadienį 24 00:00:55,480 --> 00:00:58,960 tuo semestro pradžios, kad tai, ką mes matome atsitikti. 25 00:00:58,960 --> 00:01:03,430 Taigi, šiandien mes įsitraukti truputį daugiau apie duomenų struktūras. 26 00:01:03,430 --> 00:01:06,660 Ir duoti jums daugiau kietas psichikos modelis problemų penkių, 27 00:01:06,660 --> 00:01:07,450 kuris jau nebegalioja. 28 00:01:07,450 --> 00:01:10,817 Karštieji klavišai, kuriame, mes jums ranka tekstinį failą kai 100.000 29 00:01:10,817 --> 00:01:12,650 plius Angliški žodžiai, ir jūs ketinate turėti 30 00:01:12,650 --> 00:01:17,770 išsiaiškinti, kaip protingai juos krauti į atmintį, į RAM, naudojant kai kuriuos duomenis 31 00:01:17,770 --> 00:01:19,330 struktūra pasirinkai. 32 00:01:19,330 --> 00:01:22,470 >> Dabar viena iš tokių duomenų struktūrą galima būti, bet tikriausiai neturėtų būti, 33 00:01:22,470 --> 00:01:25,630 gana paprasta susijęs sąrašas, kuriuos mes pristatė paskutinį kartą. 34 00:01:25,630 --> 00:01:29,220 Ir susijęs sąrašas turėjo bent vienas privalumas per masyvą. 35 00:01:29,220 --> 00:01:32,096 Kas vienas privalumas susijęs sąrašas, be abejo? 36 00:01:32,096 --> 00:01:32,950 >> AUDITORIJA: Insertion. 37 00:01:32,950 --> 00:01:33,908 >> DAVID Malan: Insertion. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Ką visa tai reiškia? 40 00:01:35,196 --> 00:01:37,872 >> AUDITORIJA: Visur kartu sąrašas [nesigirdi]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID Malan: Geras. 42 00:01:38,770 --> 00:01:42,090 Taigi jūs galite įterpti elementą, kur tai norite viduryje sąrašo 43 00:01:42,090 --> 00:01:45,490 nereikia maišyti nieko, kurį mes padarė išvadą, mūsų rūšiavimą 44 00:01:45,490 --> 00:01:47,630 diskusijos, nėra nebūtinai yra geras dalykas, 45 00:01:47,630 --> 00:01:51,200 nes tai užima daug laiko, kad iš tikrųjų juda visų šių žmonių į kairę arba į dešinę. 46 00:01:51,200 --> 00:01:55,540 Ir taip su susietą sąrašą, jūs galite tiesiog paskirstyti su malloc, naujas mazgas, 47 00:01:55,540 --> 00:01:58,385 ir tada atnaujinti porą pointers-- du, trys operacijos max-- 48 00:01:58,385 --> 00:02:01,480 ir mes galime lošimo žmogų visur į sąrašą. 49 00:02:01,480 --> 00:02:03,550 >> Ką dar buvo naudingas apie susietą sąrašą? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Taip? 52 00:02:05,659 --> 00:02:06,534 >> AUDITORIJA: [nesigirdi] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID Malan: Perfect. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Tobula. 57 00:02:11,090 --> 00:02:12,070 Tai tikrai dinamiškas. 58 00:02:12,070 --> 00:02:15,100 Ir kad jūs ne įsipareigojant, iš anksto, tam tikru fiksuoto dydžio 59 00:02:15,100 --> 00:02:18,750 riekė atminties, kaip norėtumėte, kad į su masyvo, nelyginant iš kurių 60 00:02:18,750 --> 00:02:22,455 yra tai, kad galite skirti mazgai tik paklausa taip naudojant tik tiek vietos, 61 00:02:22,455 --> 00:02:23,330 kaip jūs iš tikrųjų reikia. 62 00:02:23,330 --> 00:02:26,830 Priešingai masyvo, galite netyčia skirti per mažai. 63 00:02:26,830 --> 00:02:28,871 Ir tada jis tiesiog vyksta būti kaklo skausmas 64 00:02:28,871 --> 00:02:32,440 perskirstyti naują matysite, kopijuoti viskas baigėsi, nemokamai seną masyvą, 65 00:02:32,440 --> 00:02:33,990 ir tada pereiti apie savo verslą. 66 00:02:33,990 --> 00:02:37,479 Arba, dar blogiau, jums gali skirti kelią daugiau atminties, negu jūs iš tikrųjų reikia, 67 00:02:37,479 --> 00:02:40,520 ir taip jūs ketinate turėti labai retai apgyvendintos masyvą, taip sakant. 68 00:02:40,520 --> 00:02:44,350 >> Taigi susietas sąrašas suteikia jums tai privalumai dinamiškumo ir lankstumo 69 00:02:44,350 --> 00:02:46,080 su intarpais ir naikinimus. 70 00:02:46,080 --> 00:02:48,000 Bet tikrai turi būti sumokėta kaina. 71 00:02:48,000 --> 00:02:50,000 Tiesą sakant, viena iš temų, ištirti dėl viktorinos nulis 72 00:02:50,000 --> 00:02:52,430 buvo iš kompromisus pora mes matėme iki šiol. 73 00:02:52,430 --> 00:02:56,161 Taigi, kas yra kaina, sumokėta arba Smukimo susietą sąrašą? 74 00:02:56,161 --> 00:02:56,660 Taip. 75 00:02:56,660 --> 00:02:57,560 >> AUDITORIJA: Nėra operatyvioji. 76 00:02:57,560 --> 00:02:58,809 >> DAVID Malan: Nėra operatyvioji. 77 00:02:58,809 --> 00:02:59,540 Bet who cares? 78 00:02:59,540 --> 00:03:01,546 Operatyvioji neskamba įtikinamai. 79 00:03:01,546 --> 00:03:02,421 >> AUDITORIJA: [nesigirdi] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID Malan: Būtent. 82 00:03:05,740 --> 00:03:07,580 Jei norite, kad tikras algorithm-- 83 00:03:07,580 --> 00:03:10,170 ir leiskite man iš tikrųjų pasiūlyti dvejetainis paieška visų pirma, kuris 84 00:03:10,170 --> 00:03:12,600 yra vienas mes naudojo gana bit-- jei nenorite turėti laisvą prieigą, 85 00:03:12,600 --> 00:03:15,516 Jūs negalite padaryti, kad paprastas aritmetines rasti kaip vidurinį elementą 86 00:03:15,516 --> 00:03:16,530 ir šokinėja teisę jį. 87 00:03:16,530 --> 00:03:20,239 Jūs, o ne, turi pradėti nuo pradžių elementas ir tiesiškai ieškoti iš kairės 88 00:03:20,239 --> 00:03:22,780 į dešinę, jei norite rasti vidurys ar bet koks kitas elementas. 89 00:03:22,780 --> 00:03:24,410 >> AUDITORIJA: Tai tikriausiai užima daugiau atminties. 90 00:03:24,410 --> 00:03:25,040 >> DAVID Malan: reikia daugiau atminties. 91 00:03:25,040 --> 00:03:27,464 Kur yra tas, kad papildoma kaina iš atminties? 92 00:03:27,464 --> 00:03:28,339 >> AUDITORIJA: [nesigirdi] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID Malan: Būtent. 95 00:03:33,440 --> 00:03:35,679 Šiuo atveju čia, mes turėjome susijęs sąrašas sveikieji, 96 00:03:35,679 --> 00:03:37,470 ir dar mes dvigubai atminties kiekis 97 00:03:37,470 --> 00:03:39,680 mums reikia iki pat saugoti šiuos patarimus. 98 00:03:39,680 --> 00:03:42,090 Dabar mažiau baisi kaip Jūsų structs gauti didesni 99 00:03:42,090 --> 00:03:45,320 ir jūs saugoti ne skaičius, bet gal studentas ar kitu objektu. 100 00:03:45,320 --> 00:03:46,880 Bet esmė tikrai lieka. 101 00:03:46,880 --> 00:03:49,421 Ir taip iš operacijų skaičius susijusios su bendrais sąrašais buvo vadinami 102 00:03:49,421 --> 00:03:50,570 buvo didelis O n-- linijinių. 103 00:03:50,570 --> 00:03:54,730 Dalykų, pavyzdžiui, įterpiant ar paieškos arba išbraukta atveju elementas 104 00:03:54,730 --> 00:03:57,720 atsitiko pačioje pabaigoje sąrašas, ar jis rūšiuojami ar ne. 105 00:03:57,720 --> 00:04:01,167 >> Kartais jūs galite gauti pasisekė ir taip apatinės vertinimo šias operacijas 106 00:04:01,167 --> 00:04:04,250 Taip pat gali būti pastovus laikas, jei esate visada žiūri į pirmąjį elementą, 107 00:04:04,250 --> 00:04:05,070 pavyzdžiui. 108 00:04:05,070 --> 00:04:09,360 Tačiau, galiausiai, mes pažadėjome pasiekti Gralis 109 00:04:09,360 --> 00:04:12,630 Duomenų struktūrų, arba kai derinimas dalį, 110 00:04:12,630 --> 00:04:14,290 būdu pastovaus laiko. 111 00:04:14,290 --> 00:04:17,579 Mes galime rasti elementus arba pridėti elementų arba pašalinti elementus iš sąrašo? 112 00:04:17,579 --> 00:04:19,059 Pamatysime visai netrukus. 113 00:04:19,059 --> 00:04:21,100 Ir paaiškėja, kad vienas iš mechanizmų mes 114 00:04:21,100 --> 00:04:23,464 ketina pradėti naudoti šiandien, metinis naudojimas psl nustatyti penki, 115 00:04:23,464 --> 00:04:24,630 iš tiesų yra gana pažįstamas. 116 00:04:24,630 --> 00:04:27,430 Pavyzdžiui, jei tai yra krūva iš egzamino knygų, iš kurių kiekvienas 117 00:04:27,430 --> 00:04:29,660 turi studento pirmas vardas ir pavardė ant jo, 118 00:04:29,660 --> 00:04:31,820 ir aš juos pasiimti iš pasibaigus egzaminui pabaigoje 119 00:04:31,820 --> 00:04:33,746 ir jie visi yra gana daug atsitiktine tvarka, 120 00:04:33,746 --> 00:04:36,370 ir mes norime eiti apie rūšiavimą Šie egzaminai, kad kai skirstomi 121 00:04:36,370 --> 00:04:38,661 tai tik daug lengviau ir greičiau perduoti juos atgal 122 00:04:38,661 --> 00:04:40,030 studentams pagal abėcėlę. 123 00:04:40,030 --> 00:04:42,770 Kokie bus Jūsų instinktai būti už egzaminų, kaip šis krūva? 124 00:04:42,770 --> 00:04:45,019 >> Na, jei jūs panašus į mane, jūs galite pamatyti, kad tai yra m, 125 00:04:45,019 --> 00:04:48,505 todėl aš ruošiuosi tarsi pradėtas šis, jei tai yra mano stalo ar mano grindys kur 126 00:04:48,505 --> 00:04:50,650 Aš skleisti dalykus out-- ar mano masyvas really-- 127 00:04:50,650 --> 00:04:52,210 Galėčiau įdėti visas Ms ten. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Štai A. Taigi galėčiau įdėti As čia. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Štai dar vienas A. Aš ruošiuosi įdėti, kad čia. 132 00:04:57,980 --> 00:05:02,490 Štai Z. Štai dar vienas M. Ir taip Galėčiau pradėti uždirbti krūvas kaip šis. 133 00:05:02,490 --> 00:05:06,620 Ir tada gal aš eiti vėliau ir rūšiuoti labai nitpicky-ly rūšiuoti 134 00:05:06,620 --> 00:05:07,710 individualūs poliai. 135 00:05:07,710 --> 00:05:11,300 Bet yra man atrodytų įėjime, kad aš ranka 136 00:05:11,300 --> 00:05:14,016 ir aš norėčiau, kad kai kurie apskaičiuojami Sprendimas grindžiamas tuo įvesties. 137 00:05:14,016 --> 00:05:15,640 Jei jis prasideda, padėkite jį ten. 138 00:05:15,640 --> 00:05:18,980 Jei jis prasideda Z, padėkite jį ant ten, ir viskas tarp. 139 00:05:18,980 --> 00:05:22,730 >> Taigi tai yra technika, kuri yra paprastai žinomas kaip hashing-- H-A-S-H- 140 00:05:22,730 --> 00:05:26,550 kuris iš esmės reiškia, imant įvesties ir naudoja tą įvestį apskaičiuoti 141 00:05:26,550 --> 00:05:30,940 vertė, paprastai numeris ir kad skaičius puslapis į saugojimo 142 00:05:30,940 --> 00:05:32,260 konteineris, kaip masyvo. 143 00:05:32,260 --> 00:05:35,490 Taigi, kitaip tariant, aš gali turėti maišos funkcija, kaip aš, mano galva, 144 00:05:35,490 --> 00:05:37,940 kad jei matau kad žmogus vardas, kuris prasideda, 145 00:05:37,940 --> 00:05:40,190 Aš einu į žemėlapį, kad iki nulio, mano galva. 146 00:05:40,190 --> 00:05:44,160 Ir jei aš matau ką nors su Z, aš vyksta į žemėlapį, kad į 25 mano galva 147 00:05:44,160 --> 00:05:46,220 ir tada įdėti, kad į paskutinis dauguma krūva. 148 00:05:46,220 --> 00:05:50,990 >> Dabar, jei jūs manote apie ne mano smegenys bet C programa, ką numeriai galėtų 149 00:05:50,990 --> 00:05:53,170 Jūs remtis pasiekti tą patį rezultatą? 150 00:05:53,170 --> 00:05:55,594 Kitaip tariant, jei jūs turėjo ASCII simbolių A, 151 00:05:55,594 --> 00:05:57,510 kaip nustatyti kas kibiras, kad pagal ją? 152 00:05:57,510 --> 00:05:59,801 Jūs tikriausiai nenorite įdėti jį į kibirą 65, kuris 153 00:05:59,801 --> 00:06:01,840 Būtų kaip ten be priežasties. 154 00:06:01,840 --> 00:06:04,320 Kur jūs norite įdėti atsižvelgiant į jo ASCII vertės? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Kur jūs norite daryti su savo ASCII vertė sugalvoti protingesni kibirą 157 00:06:08,920 --> 00:06:09,480 įdėti ją į? 158 00:06:09,480 --> 00:06:10,206 >> AUDITORIJA: Minus A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID Malan: Taip. 160 00:06:10,956 --> 00:06:13,190 Taigi minus minus specialiai 65, jei tai 161 00:06:13,190 --> 00:06:18,240 kapitalas A. Arba 98, jeigu tai mažosiomis raidėmis. 162 00:06:18,240 --> 00:06:21,300 Ir taip, kad leistų mums, labai paprastai ir labai aritmetiškai 163 00:06:21,300 --> 00:06:23,260 įdėti kažką į panašaus kibirą. 164 00:06:23,260 --> 00:06:26,010 Taigi paaiškėja, mes iš tikrųjų tai taip pat net su viktorinos. 165 00:06:26,010 --> 00:06:29,051 >> Taigi jums gali prisiminti jums apibraukta jūsų Mokymo bendradarbis vardas ant viršelio. 166 00:06:29,051 --> 00:06:32,270 Buvo surengta TF vardai į šias skiltis abėcėlę, 167 00:06:32,270 --> 00:06:34,400 gerai, manau, tai ar ne, kai visi 80 plius mums 168 00:06:34,400 --> 00:06:37,800 susirinko kitų naktį laipsnio, Paskutinis žingsnis mūsų klasifikavimo procesą 169 00:06:37,800 --> 00:06:41,830 yra maišos viktorinos į big erdvė grindų ties [nesigirdi] 170 00:06:41,830 --> 00:06:45,110 ir nustatyti kiekvieno asmens viktorinos iš lygiai jų TF įsakymu 171 00:06:45,110 --> 00:06:47,700 pavadinimai ant viršelio, nes tada tai daug lengviau mus 172 00:06:47,700 --> 00:06:51,290 ieškoti per tą tiesiniu ieškoti arba kai sumanumas natūra 173 00:06:51,290 --> 00:06:54,050 už TF, norėdami surasti jo jos mokiniams "viktorinos. 174 00:06:54,050 --> 00:06:56,060 >> Taigi šis nurodykite domenų idėja kad jūs pamatysite, yra 175 00:06:56,060 --> 00:07:00,520 gana galinga iš tiesų yra gana banalumas ir labai intuityvus, 176 00:07:00,520 --> 00:07:03,000 panašiai kaip galbūt padalinti ir valdyk buvo nulinis savaitę. 177 00:07:03,000 --> 00:07:05,250 Aš pirmyn iki hackathon Prieš porą metų. 178 00:07:05,250 --> 00:07:08,040 Tai buvo iš Zamyla ir pora kiti darbuotojai sveikinimo studentams 179 00:07:08,040 --> 00:07:09,030 kaip jie atėjo. 180 00:07:09,030 --> 00:07:12,680 Ir mes turėjome visą ryšelyje lankstymo stalai ten su vardų žymomis. 181 00:07:12,680 --> 00:07:15,380 Ir mes turėjome žymos organizuotas su lyg per ten 182 00:07:15,380 --> 00:07:16,690 ir ten Zs. 183 00:07:16,690 --> 00:07:20,350 Ir taip vienas TFS labai gudriai rašė, kad tai instrukcijas 184 00:07:20,350 --> 00:07:21,030 už dieną. 185 00:07:21,030 --> 00:07:24,480 O semestro šio 12 savaitės pagaminti visiškai logiška ir visiem 186 00:07:24,480 --> 00:07:25,310 žinojo, ką daryti. 187 00:07:25,310 --> 00:07:27,900 Bet kuriuo metu jūs eilėje tuo pačiu būdu, 188 00:07:27,900 --> 00:07:30,272 jūs įgyvendinant pats samprata maišos. 189 00:07:30,272 --> 00:07:31,730 Taigi galime formalizuoti tai truputį. 190 00:07:31,730 --> 00:07:32,890 Čia yra masyvas. 191 00:07:32,890 --> 00:07:36,820 Jis sudarytas būti šiek tiek Platus tik vaizduoti, vizualiai, 192 00:07:36,820 --> 00:07:38,920 kad mes galime įdėti stygos kažką panašaus į tai. 193 00:07:38,920 --> 00:07:41,970 Ir tai masyvas Akivaizdu dydis 26 viso. 194 00:07:41,970 --> 00:07:43,935 Ir dalykas yra vadinamas stalo savavališkai. 195 00:07:43,935 --> 00:07:48,930 Bet tai tik menininko perdavimų kas maišos lentelės gali būti. 196 00:07:48,930 --> 00:07:52,799 >> Taigi maišos lentelės dabar ruošiasi būti aukštesnio lygio duomenų struktūra. 197 00:07:52,799 --> 00:07:54,840 Tuo dienos pabaigos mes pasiruošę žiūrėt kad jums 198 00:07:54,840 --> 00:07:58,700 gali įgyvendinti maišos lentelę, kuri yra labai panašus į registracijos vietą eilutėje 199 00:07:58,700 --> 00:08:02,059 ne hackathon panašiai kaip tai naudojamoje lentelėje rūšiavimas egzaminą knygų. 200 00:08:02,059 --> 00:08:03,850 Bet maišos lentelė rūšiuoti šios aukšto lygio 201 00:08:03,850 --> 00:08:08,250 koncepcija, kuri galėtų naudoti masyvą po gaubtu ją įgyvendinti, 202 00:08:08,250 --> 00:08:11,890 arba ji gali naudoti ilgis sąrašą, arba net galbūt kai kurių kitų duomenų struktūros. 203 00:08:11,890 --> 00:08:15,590 Ir dabar tai theme-- paėmimas kai kurios iš šių pagrindinių sudėtinių dalių 204 00:08:15,590 --> 00:08:18,310 kaip masyvo ir šio pastato blokuoti dabar jų ilgio sąrašą 205 00:08:18,310 --> 00:08:21,740 ir nematant kas mes galime sukurti ant tų, pavyzdžiui, sudedamųjų dalių, 206 00:08:21,740 --> 00:08:26,550 į receptą, todėl vis daugiau ir daugiau įdomių ir naudingų galutiniai rezultatai. 207 00:08:26,550 --> 00:08:28,680 >> Taigi su maišos lentelė mes galime ją įgyvendinti 208 00:08:28,680 --> 00:08:32,540 atmintyje pavaizduotomis piktogramo-, kaip šis, bet kaip gali iš tikrųjų būti koduojami iki? 209 00:08:32,540 --> 00:08:33,789 Na, gal taip tiesiog tai. 210 00:08:33,789 --> 00:08:38,270 Jei TALPA visais dangteliais, yra tik kai, pavyzdžiui, 26 constant--, 211 00:08:38,270 --> 00:08:42,030 už 26 raides alphabet-- Galėčiau paskambinti savo kintamas lentelę, 212 00:08:42,030 --> 00:08:45,630 ir galiu teigti, kad aš ruošiuosi įdėti char žvaigždes ten, arba eilutę. 213 00:08:45,630 --> 00:08:49,880 Taigi, tai taip paprasta, kaip tai, jei jūs nori įgyvendinti maišos lentelę. 214 00:08:49,880 --> 00:08:51,490 Ir dar, tai tikrai tik masyvas. 215 00:08:51,490 --> 00:08:53,198 Bet vėl, maišos Lentelėje yra dabar, ką mes 216 00:08:53,198 --> 00:08:57,470 skambinti abstraktų duomenų tipą, kad tai tik tarsi konceptualus sluoksniavimasis viršuje 217 00:08:57,470 --> 00:09:00,780 kažko daugiau kasdieniškas Dabar norėčiau masyvą. 218 00:09:00,780 --> 00:09:02,960 >> Dabar, kaip mes einame apie sprendžiant problemas? 219 00:09:02,960 --> 00:09:06,980 Na, anksčiau turėjau prabangą turėti pakankamai stalo erdvė čia 220 00:09:06,980 --> 00:09:09,460 kad galėčiau įdėti viktorinos bet aš norėjau. 221 00:09:09,460 --> 00:09:10,620 Taip gali eiti čia. 222 00:09:10,620 --> 00:09:12,100 Zs gali eiti čia. 223 00:09:12,100 --> 00:09:13,230 Ms gali eiti čia. 224 00:09:13,230 --> 00:09:14,740 Ir tada aš turėjo tam tikrą papildomą erdvę. 225 00:09:14,740 --> 00:09:18,740 Bet tai iš kodų bitų dešinėje dabar, nes šioje lentelėje, jei aš tikrai 226 00:09:18,740 --> 00:09:22,720 maniau apie tai, kaip masyvo, yra tik bus kai kurių fiksuoto dydžio. 227 00:09:22,720 --> 00:09:25,380 >> Techniškai, jei aš traukti iki kito studento viktorina 228 00:09:25,380 --> 00:09:28,490 ir pamatyti, oi, tai asmens vardas prasideda A irgi 229 00:09:28,490 --> 00:09:30,980 I rūšies norite jį ten. 230 00:09:30,980 --> 00:09:34,740 Bet kaip tik aš jį ten, jei ši lentelė tikrai atstovauja masyvą, 231 00:09:34,740 --> 00:09:37,840 Aš ruošiuosi būti svarbūs ar clobbering kas šio studento viktorina yra. 232 00:09:37,840 --> 00:09:38,340 Teisė? 233 00:09:38,340 --> 00:09:41,972 Jei tai yra masyvas, tik vienas dalykas gali eiti į kiekvieną iš šių ląstelių arba elementais. 234 00:09:41,972 --> 00:09:43,680 Ir taip aš tipo turi rinktis. 235 00:09:43,680 --> 00:09:45,735 >> Dabar anksčiau aš tipo apgaudinėjama ir padarė tą ar I 236 00:09:45,735 --> 00:09:47,526 tiesiog rūšies sudėti jiems vienas virš kito. 237 00:09:47,526 --> 00:09:49,170 Bet kad nesiruošia skristi kodą. 238 00:09:49,170 --> 00:09:52,260 Taigi, kur galėčiau įdėti Antroji studentas, kurio vardas 239 00:09:52,260 --> 00:09:54,964 yra, jei viskas, ką aš turėjo tai galima lentelės vietos? 240 00:09:54,964 --> 00:09:57,880 Ir aš naudojamas tris lizdus ir jį atrodo ten tik keletą kitų. 241 00:09:57,880 --> 00:09:58,959 Ką galėtumėte padaryti? 242 00:09:58,959 --> 00:09:59,834 AUDITORIJA: [nesigirdi] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID Malan: Taip. 245 00:10:01,315 --> 00:10:02,370 Gal galime tiesiog laikyti jį paprasta. 246 00:10:02,370 --> 00:10:02,660 Teisė? 247 00:10:02,660 --> 00:10:04,243 Jis netelpa, kur aš noriu jį. 248 00:10:04,243 --> 00:10:07,450 Taigi, aš ruošiuosi jį techniškai kur B būtų eiti. 249 00:10:07,450 --> 00:10:09,932 Dabar, žinoma, aš pradedu dažų save į kampą. 250 00:10:09,932 --> 00:10:11,890 Jei gaunu studentui kurio vardas tikrai B, 251 00:10:11,890 --> 00:10:14,840 dabar B ketina perkelti šiek tiek į priekį, kaip gali nutikti, yep, 252 00:10:14,840 --> 00:10:17,530 jei tai B, dabar jis turi eiti čia. 253 00:10:17,530 --> 00:10:20,180 >> Ir todėl tai labai greitai gali tapti problemiškas, 254 00:10:20,180 --> 00:10:23,850 bet tai technologija, kuri iš tikrųjų yra nurodytas kaip linijinis zondavimo, 255 00:10:23,850 --> 00:10:26,650 kuriuo jūs tiesiog laikyti savo masyvas būti išilgai geležinkelio linijos. 256 00:10:26,650 --> 00:10:29,680 Ir jūs tiesiog rūšies zondas arba apžiūrėkite kiekvieną turimą elementą 257 00:10:29,680 --> 00:10:31,360 ieško prieinamo vietoje. 258 00:10:31,360 --> 00:10:34,010 Ir kaip tik jūs rasite vienas, jūs palikite jį ten. 259 00:10:34,010 --> 00:10:38,390 >> Dabar kaina mokama dabar Šio sprendimo yra kas? 260 00:10:38,390 --> 00:10:41,300 Mes turime fiksuotą dydį masyvo, ir kai aš įdėti pavadinimus 261 00:10:41,300 --> 00:10:44,059 į jį, bent jau iš pradžių, o kas chronometražas įterpimą 262 00:10:44,059 --> 00:10:46,350 už išleidimą studentų pažangumą viktorinos į tinkamus kibirus? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O ką? 265 00:10:50,002 --> 00:10:51,147 >> AUDITORIJA: n. 266 00:10:51,147 --> 00:10:52,480 DAVID Malan: Girdėjau didelis O n. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Ne tiesa. 269 00:10:54,300 --> 00:10:56,490 Bet mes erzinti išskyrus kodėl vos akimirką. 270 00:10:56,490 --> 00:10:57,702 Ką dar gali būti? 271 00:10:57,702 --> 00:10:58,755 >> AUDITORIJA: [nesigirdi] 272 00:10:58,755 --> 00:11:00,380 DAVID Malan: Ir leiskite man tai padaryti vizualiai. 273 00:11:00,380 --> 00:11:04,720 Taigi tarkime tai yra raidė S. 274 00:11:04,720 --> 00:11:05,604 >> AUDITORIJA: Tai vienas. 275 00:11:05,604 --> 00:11:06,520 DAVID Malan: Tai vienas. 276 00:11:06,520 --> 00:11:06,710 Teisė? 277 00:11:06,710 --> 00:11:08,950 Tai masyvas, kuris reiškia, kad turime laisvą prieigą. 278 00:11:08,950 --> 00:11:11,790 Ir jei mes galvojame apie tai kaip nulio ir tai, kaip 25, 279 00:11:11,790 --> 00:11:13,800 ir mes suprantame, kad, oh, čia mano indėlis S, 280 00:11:13,800 --> 00:11:16,350 Aš tikrai gali konvertuoti S, ASCII simbolių, 281 00:11:16,350 --> 00:11:18,540 su atitinkamu numeriu nuo nulio iki 25 282 00:11:18,540 --> 00:11:20,910 ir tada iš karto padėkite jį, kur jis priklauso. 283 00:11:20,910 --> 00:11:26,120 >> Bet, žinoma, kaip tik aš gauti Antrasis asmuo vardas arba B arba C 284 00:11:26,120 --> 00:11:29,300 galiausiai, jei aš naudojamas linijinis zondavimo kaip mano sprendimas, 285 00:11:29,300 --> 00:11:31,360 chronometražas įterpimo blogiausiu atveju 286 00:11:31,360 --> 00:11:33,120 iš tikrųjų vyksta pavesti į ką? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 Ir aš išgirsti čia teisingai anksti. 289 00:11:36,045 --> 00:11:36,920 AUDITORIJA: [nesigirdi] 290 00:11:36,920 --> 00:11:41,620 DAVID Malan: Taigi n tiesų kartą turite pakankamai didelį duomenų rinkinį. 291 00:11:41,620 --> 00:11:44,410 Taigi, viena vertus, jei Jūsų masyvas yra pakankamai didelis 292 00:11:44,410 --> 00:11:48,287 ir jūsų duomenys yra tik keletas pakankamai, jūs gauti šią nuostabią pastovų laiką. 293 00:11:48,287 --> 00:11:50,620 Bet kaip tik jūs pradedate vis daugiau ir daugiau elementų, 294 00:11:50,620 --> 00:11:53,200 ir tik statistiškai gausite daugiau žmonių su raide 295 00:11:53,200 --> 00:11:56,030 Kaip jų pavadinimas arba raidė B, tai galėtų sąlygoti 296 00:11:56,030 --> 00:11:57,900 išsigimti į kažką daugiau linijinių. 297 00:11:57,900 --> 00:11:59,640 Taigi ne visai tobulas. 298 00:11:59,640 --> 00:12:00,690 Taigi galėtume padaryti geriau? 299 00:12:00,690 --> 00:12:03,210 >> Na, kas buvo mūsų sprendimas prieš kai mes 300 00:12:03,210 --> 00:12:06,820 nori turėti daugiau dinamiškumo, nei kažkas panašaus masyvo leidžiama? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 AUDITORIJA: [nesigirdi] 303 00:12:08,960 --> 00:12:10,030 DAVID Malan: Ką mes pristatome? 304 00:12:10,030 --> 00:12:10,530 Taip. 305 00:12:10,530 --> 00:12:11,430 Taigi susietas sąrašas. 306 00:12:11,430 --> 00:12:14,430 Na, pažiūrėkime, ką susieti sąrašas gali padaryti už mus, o ne. 307 00:12:14,430 --> 00:12:17,630 Na, leiskite man pasiūlyti, kad mes atkreipti paveikslėlį taip. 308 00:12:17,630 --> 00:12:19,620 Dabar tai yra kitoks Vaizdas iš pavyzdį 309 00:12:19,620 --> 00:12:24,750 iš skirtingų teksto, iš tikrųjų, kad iš tikrųjų, naudojant iš dydžio 31 masyvo. 310 00:12:24,750 --> 00:12:28,220 Ir tai autorius tiesiog nusprendė maišos stygos 311 00:12:28,220 --> 00:12:32,430 nėra pagrįstas to asmens vardų, bet remiantis jų gimtadienių. 312 00:12:32,430 --> 00:12:35,680 Nepriklausomai nuo to mėnesio, jie suprato jei jūs gimė pirmasis mėnuo 313 00:12:35,680 --> 00:12:39,580 arba visą mėnesį 31., autorius pradės koduoti remiantis tos vertės, 314 00:12:39,580 --> 00:12:44,154 taip išplito pavardes iš šiek tiek daugiau nei tik 26 taškus gali leisti. 315 00:12:44,154 --> 00:12:47,320 Ir galbūt tai šiek tiek daugiau vienodos nei eiti su abėcėlės raidėmis, 316 00:12:47,320 --> 00:12:50,236 nes, žinoma, tikriausiai daugiau žmonių pasaulyje su pavadinimais 317 00:12:50,236 --> 00:12:54,020 kurie prasideda ne tikrai kai kurios kitos abėcėlės raidės. 318 00:12:54,020 --> 00:12:56,380 Tai gal tai yra mažai vienodesnis, darant prielaidą, 319 00:12:56,380 --> 00:12:58,640 vienodas paskirstymas kūdikių apsaugai per mėnesį. 320 00:12:58,640 --> 00:12:59,990 >> Bet, žinoma, tai dar netobulas. 321 00:12:59,990 --> 00:13:00,370 Teisė? 322 00:13:00,370 --> 00:13:01,370 Kilo susidūrimų. 323 00:13:01,370 --> 00:13:04,680 Keli žmonės tai duomenų struktūra yra vis dar 324 00:13:04,680 --> 00:13:08,432 turintys tą pačią gimimo bent esate, nepriklausomai nuo mėnesio. 325 00:13:08,432 --> 00:13:09,640 Bet kuo čia dėtas autorius padarė? 326 00:13:09,640 --> 00:13:13,427 Na, atrodo, kad mes turime įvairių kairėje pusėje vertikaliai nubrėžtos, 327 00:13:13,427 --> 00:13:15,010 bet tai tik menininko perdavimų. 328 00:13:15,010 --> 00:13:18,009 Nesvarbu, kokia kryptimi jums atkreipti masyvą, ji vis dar masyvas. 329 00:13:18,009 --> 00:13:20,225 Kas tai yra ir, matyt, masyvas? 330 00:13:20,225 --> 00:13:21,500 >> AUDITORIJA: Susijęs sąrašas. 331 00:13:21,500 --> 00:13:21,650 >> DAVID Malan: Taip. 332 00:13:21,650 --> 00:13:23,490 Atrodo, kad tai masyvas susijęs sąrašą. 333 00:13:23,490 --> 00:13:26,490 Taigi dar kartą, prie šio punkto rūšiuoti naudojant šias duomenų struktūras dabar 334 00:13:26,490 --> 00:13:28,550 kaip ingredientų daugiau Įdomios sprendimai, 335 00:13:28,550 --> 00:13:30,862 galite visiškai imtis esminis, kaip ir masyvo 336 00:13:30,862 --> 00:13:33,320 ir tada imtis ko nors daugiau Įdomu kaip susijęs sąrašą 337 00:13:33,320 --> 00:13:36,660 ir net juos sujungti į netgi įdomiau duomenų struktūra. 338 00:13:36,660 --> 00:13:39,630 Ir iš tiesų, tai taip pat būtų vadinamas maišos lentelę, 339 00:13:39,630 --> 00:13:42,610 kuriuo masyvas tikrai maišos lentelės, 340 00:13:42,610 --> 00:13:45,600 bet kad maišos lentelė turi grandinės, taip sakant, 341 00:13:45,600 --> 00:13:50,220 kad gali augti arba trauktis remiantis skaičius elementų norite įterpti. 342 00:13:50,220 --> 00:13:52,990 >> Dabar, atitinkamai, kas veikimo laikas dabar? 343 00:13:52,990 --> 00:13:58,030 Jei aš noriu įdėti ką nors kurio gimtadienis yra spalio 31, 344 00:13:58,030 --> 00:13:59,040 Kur jis ar ji eiti? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Gerai. 347 00:14:01,030 --> 00:14:02,819 Pačioje apačioje, kur ji sako 31. 348 00:14:02,819 --> 00:14:03,610 Ir tai puikiai. 349 00:14:03,610 --> 00:14:05,060 Tai buvo pastovus laiko. 350 00:14:05,060 --> 00:14:08,760 Bet kas, jei mes pastebėjome, kad kas nors kurio gimtadienis, pažiūrėkime, 351 00:14:08,760 --> 00:14:10,950 Spalio, lapkričio, gruodis 31? 352 00:14:10,950 --> 00:14:12,790 Kur yra jis ar ji ketina eiti? 353 00:14:12,790 --> 00:14:13,290 Tas pats dalykas. 354 00:14:13,290 --> 00:14:13,970 Antras žingsnis, nors. 355 00:14:13,970 --> 00:14:15,303 Štai pastovus nors ar ne? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Gerai. 358 00:14:16,860 --> 00:14:17,840 Šiuo metu ji yra. 359 00:14:17,840 --> 00:14:20,570 Tačiau bendruoju atveju, kuo daugiau žmonių mes pridėti, 360 00:14:20,570 --> 00:14:23,790 probabilistically, mes ketiname gauti vis daugiau ir daugiau susidūrimų. 361 00:14:23,790 --> 00:14:26,820 >> Dabar tai yra mažai geriau, nes techniškai 362 00:14:26,820 --> 00:14:34,580 dabar mano grandinės gali būti blogiausiu atveju, kiek laiko? 363 00:14:34,580 --> 00:14:38,890 Jei aš įdėti n žmones į tai daugiau sudėtingos duomenų struktūros, n žmonių, 364 00:14:38,890 --> 00:14:41,080 blogiausiu atveju tai bus n. 365 00:14:41,080 --> 00:14:41,815 Kodėl? 366 00:14:41,815 --> 00:14:43,332 >> AUDITORIJA: Nes jei visi turi tą pačią gimtadienį, 367 00:14:43,332 --> 00:14:44,545 jie ketina būti viena eilutė. 368 00:14:44,545 --> 00:14:45,420 DAVID Malan: Perfect. 369 00:14:45,420 --> 00:14:47,480 Jis gali būti šiek tiek nenatūralu, bet tikrai, blogiausiu atveju, 370 00:14:47,480 --> 00:14:50,117 jei visi turi tą pačią gimtadienio, atsižvelgiant įėjimai turite, 371 00:14:50,117 --> 00:14:51,950 jūs ketinate turėti masiškai ilgos grandinės. 372 00:14:51,950 --> 00:14:54,241 Ir taip, gal ji yra skambinti maišos lentelę, bet tikrai tai 373 00:14:54,241 --> 00:14:56,810 tiesiog masinis susijęs sąrašas su visa partija sugaišto erdvėje. 374 00:14:56,810 --> 00:15:00,460 Bet apskritai, jei mes manome, kad bent gimtadieniai uniform-- 375 00:15:00,460 --> 00:15:01,750 ir tai tikriausiai yra ne. 376 00:15:01,750 --> 00:15:02,587 Aš padaryti, kad iki. 377 00:15:02,587 --> 00:15:04,420 Bet jei mes manome, už Diskutuojant 378 00:15:04,420 --> 00:15:07,717 , kad jie yra, tada Teoriškai, jei tai vertikalus atstovavimas 379 00:15:07,717 --> 00:15:11,050 masyvo, gerai tada tikiuosi jums ketina gauti grandines yra, jūs žinote, 380 00:15:11,050 --> 00:15:15,880 grubiai tas pats ilgis, kai kiekviena tai rodo mėnesio dieną. 381 00:15:15,880 --> 00:15:19,930 >> Dabar, jei yra 31 dienų per mėnesį, tai reiškia, kad mano važiavimo laikas tikrai 382 00:15:19,930 --> 00:15:25,230 yra didelis O n virš 31, kurie jaučiasi geriau nei linijinių. 383 00:15:25,230 --> 00:15:27,950 Bet kas buvo vienas iš mūsų įsipareigojimai porą savaičių 384 00:15:27,950 --> 00:15:31,145 prieš, kai ji atėjo į išreikšdami chronometražas algoritmą? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Tiesiog pažvelgti tik aukštos užsakymo laikotarpiu. 387 00:15:35,190 --> 00:15:35,690 Teisė? 388 00:15:35,690 --> 00:15:37,400 31 yra tikrai naudinga. 389 00:15:37,400 --> 00:15:39,610 Bet tai vis dar didelis O n. 390 00:15:39,610 --> 00:15:41,730 Bet viena iš temų, Problemos nustatyti penki 391 00:15:41,730 --> 00:15:43,950 bus į pripažinti, kad absoliučiai, 392 00:15:43,950 --> 00:15:47,320 asimptotiškai, teoriškai tai duomenų struktūra 393 00:15:47,320 --> 00:15:50,470 yra ne geriau nei tiesiog vienas masinis susijęs sąrašas. 394 00:15:50,470 --> 00:15:53,550 Ir iš tiesų, o blogiausiu atveju, tai maišos lentelė gali išsigimti į tai. 395 00:15:53,550 --> 00:15:57,620 >> Bet ir realiame pasaulyje, su mumis žmonės kad pačių Mac ar PC ar kas 396 00:15:57,620 --> 00:16:01,240 ir veikia realiame pasaulyje Programinė įranga realiais duomenimis, 397 00:16:01,240 --> 00:16:03,260 kuris algoritmas ketinate patinka? 398 00:16:03,260 --> 00:16:09,180 Vienas, kad mano klasės veiksmų ar vienas, kad mano n padalytą 31 žingsnių 399 00:16:09,180 --> 00:16:12,900 radote duomenų lapą arba ieškoti šiek tiek informacijos? 400 00:16:12,900 --> 00:16:16,580 Aš turiu galvoje, absoliučiai 31 markių realiame pasaulyje skirtumas. 401 00:16:16,580 --> 00:16:18,540 Tai 31 kartų greičiau. 402 00:16:18,540 --> 00:16:20,880 Ir mes, žmonės, esame tikrai ketina vertinu. 403 00:16:20,880 --> 00:16:23,004 >> Taigi realizuoti dichotomiją ten tarp tikrųjų 404 00:16:23,004 --> 00:16:25,920 kalbėti apie dalykus, teoriškai ir asimptotiškai, kurie tikrai 405 00:16:25,920 --> 00:16:28,760 turi vertę, kaip mes matėme, bet ir realiame pasaulyje, 406 00:16:28,760 --> 00:16:32,930 jei jums rūpi tik darau žmogaus laimingas bendrųjų sąnaudų, 407 00:16:32,930 --> 00:16:36,010 jums gali labai gerai norite priimti Aplinkybė, kad taip, tai yra linijinė, 408 00:16:36,010 --> 00:16:38,360 bet tai 31 kartų greičiau nei linijinis gali būti. 409 00:16:38,360 --> 00:16:41,610 Ir dar geriau, mes ne tik turime kažką daryti savavališkai kaip gimimo data, 410 00:16:41,610 --> 00:16:44,030 galėtume išleisti šiek tiek daugiau laiko ir sumanumas 411 00:16:44,030 --> 00:16:47,140 ir galvoti apie tai, ką mes galime padaryti, teikiama asmens vardas, o gal 412 00:16:47,140 --> 00:16:50,130 jų gimimo sujungti tuos ingredientai išsiaiškinti kažką 413 00:16:50,130 --> 00:16:52,720 kad tai tikrai daugiau vienodas ir mažiau nelygus, 414 00:16:52,720 --> 00:16:56,250 taip sakant, nei šioje nuotraukoje Šiuo metu rodo, kad gali būti. 415 00:16:56,250 --> 00:16:57,750 Kaip galėtume įgyvendinti šį kodą? 416 00:16:57,750 --> 00:17:00,280 Na, leiskite man pasiūlyti, kad mes tiesiog pasiskolinti sintaksę mes 417 00:17:00,280 --> 00:17:01,799 naudoti porą kartų iki šiol. 418 00:17:01,799 --> 00:17:03,590 Ir aš ruošiuosi apibrėžti mazgas, kuris vėl 419 00:17:03,590 --> 00:17:06,812 yra bendrinis terminas, tik kai konteineris tam tikrą duomenų struktūrą. 420 00:17:06,812 --> 00:17:09,020 Aš ruošiuosi pasiūlyti styginių vyksta ten. 421 00:17:09,020 --> 00:17:11,369 Bet mes ketiname pradėti vartoti tie mokymai ratams dabar. 422 00:17:11,369 --> 00:17:13,230 >> Ne daugiau CS50 biblioteka tikrai, nebent norite, kad 423 00:17:13,230 --> 00:17:15,230 jį naudoti savo galutinę Projektas, kuris yra gerai, 424 00:17:15,230 --> 00:17:18,569 bet dabar mes ketiname atsitraukti užuolaidų ir sako, kad tai tik char žvaigždė. 425 00:17:18,569 --> 00:17:22,069 Taigi žodžio ten bus asmens vardą atitinkama. 426 00:17:22,069 --> 00:17:25,079 Ir dabar aš turiu ryšį čia į kitą mazgą 427 00:17:25,079 --> 00:17:28,170 todėl, kad jie atstovauti kiekvienas mazgų 428 00:17:28,170 --> 00:17:30,950 grandinėje, potencialiai Susietos sąrašą. 429 00:17:30,950 --> 00:17:34,090 >> O dabar kaip man deklaruoti Pati maišos lentelės? 430 00:17:34,090 --> 00:17:36,660 Kaip man deklaruoti visą šią struktūrą? 431 00:17:36,660 --> 00:17:40,960 Na, tikrai, panašiai kaip aš rodyklę buvo skirta tik pirmojo elemento sąrašo 432 00:17:40,960 --> 00:17:44,510 prieš panašiai galiu tik pasakyti, Aš tiesiog reikia rodykles krūva 433 00:17:44,510 --> 00:17:46,270 įgyvendinti šią visa maišos lentelę. 434 00:17:46,270 --> 00:17:49,484 Aš ruošiuosi masyvą vadinama lentelė maišos lentelė. 435 00:17:49,484 --> 00:17:50,900 Ji ketina būti iš dydžio pajėgumo. 436 00:17:50,900 --> 00:17:52,525 Štai kiek elementų galite pritaikyti jį. 437 00:17:52,525 --> 00:17:56,180 Ir kiekvienas iš šių elementų šioje masyvas bus mazgas žvaigždė. 438 00:17:56,180 --> 00:17:56,810 Kodėl? 439 00:17:56,810 --> 00:18:00,160 Na, už šią nuotrauką, ką aš Įgyvendinant maišos lentelę kaip 440 00:18:00,160 --> 00:18:04,330 efektyviai pradžia yra tik tai masyvas, kad mes nupiešiamas vertikaliai, 441 00:18:04,330 --> 00:18:06,820 kiekvienas kurių kvadratų atstovauja rodyklę. 442 00:18:06,820 --> 00:18:09,170 Kad tie, kurie turi nerijos per juos tik null. 443 00:18:09,170 --> 00:18:11,410 Ir tie, kurie turi rodykles vyksta į dešinę 444 00:18:11,410 --> 00:18:16,140 yra tikrasis rodykles į faktines mazgų, ergo įgyvendinti susijusios sąrašo pradžią. 445 00:18:16,140 --> 00:18:19,050 >> Taigi čia, tada, kaip mes galime įgyvendinti maišos lentelę, 446 00:18:19,050 --> 00:18:21,580 įgyvendina atskira Grupavimo. 447 00:18:21,580 --> 00:18:22,840 Dabar mes galime padaryti geriau? 448 00:18:22,840 --> 00:18:25,632 Visos teisės žadėjau praėjusį kartą, kad galėtume pasiekti pastovų laiką. 449 00:18:25,632 --> 00:18:27,381 Ir I rūšies jums davė pastovus laikas čia, 450 00:18:27,381 --> 00:18:29,850 bet tada sakė tikrai ne pastovus laikas, nes jis vis dar 451 00:18:29,850 --> 00:18:31,890 priklauso nuo viso elementų skaičius 452 00:18:31,890 --> 00:18:34,500 jūs įvedusi į duomenų struktūra. 453 00:18:34,500 --> 00:18:35,980 Bet tarkime, mes tai padarėme. 454 00:18:35,980 --> 00:18:39,550 Leiskite grįžti prie ekrano daugiau čia. 455 00:18:39,550 --> 00:18:44,520 Leiskite man taip pat projektuoti tai čia, aišku, ekranas, ir tarkime, kad aš tai padariau. 456 00:18:44,520 --> 00:18:49,300 Tarkime aš norėjau įdėti pavadinimą Daven į į mano duomenų struktūra. 457 00:18:49,300 --> 00:18:52,100 >> Taigi noriu įterpti eilutę Daven į duomenų struktūrą. 458 00:18:52,100 --> 00:18:54,370 Ką daryti, jei aš ne naudoti maišos lentelę, bet aš naudoju 459 00:18:54,370 --> 00:18:56,980 kažkas, kad yra daugiau medžių, kaip kaip šeimos medį, kur 460 00:18:56,980 --> 00:18:59,670 jūs turite kai šakninio viršuje ir tada mazgai ir lapai 461 00:18:59,670 --> 00:19:01,440 kad eiti žemyn ir į išorę. 462 00:19:01,440 --> 00:19:04,450 Tarkim, kad aš norite įterpti Daven s 463 00:19:04,450 --> 00:19:06,430 į tai, kas šiuo metu tuščias sąrašas. 464 00:19:06,430 --> 00:19:09,780 Aš ruošiuosi daryti taip: aš tikiu, sukursime mazgas šios šeimos 465 00:19:09,780 --> 00:19:15,170 medis-kaip duomenų struktūra, kad atrodo mažai, kaip šis, iš kurių kiekvienas 466 00:19:15,170 --> 00:19:19,640 stačiakampiai yra, tarkim, Dabar 26 elementų jį. 467 00:19:19,640 --> 00:19:21,650 Ir kiekvienas iš ląstelių šiame masyve vyksta 468 00:19:21,650 --> 00:19:23,470 atstovauti abėcėlė laišką. 469 00:19:23,470 --> 00:19:28,190 >> Tiksliau, aš ruošiuosi laikyti tai, tada B, tada C, tada D, 470 00:19:28,190 --> 00:19:29,310 tai vienas čia. 471 00:19:29,310 --> 00:19:32,940 Taigi tai vyksta iš tikrųjų atstovauti laišką D. 472 00:19:32,940 --> 00:19:36,040 Bet įterpti visi Daven s pavadinimas, man reikia padaryti šiek tiek daugiau. 473 00:19:36,040 --> 00:19:37,840 Taigi, aš pirma nueiti į maišos, taip sakant. 474 00:19:37,840 --> 00:19:41,049 Aš einu žiūrėti pirmą raidę į Daven s, kurios yra akivaizdžiai D, 475 00:19:41,049 --> 00:19:42,840 ir aš ruošiuosi skirti mazgas, kuris atrodo 476 00:19:42,840 --> 00:19:45,570 kaip this-- didelį stačiakampį didelis kad tilptų visą abėcėlę. 477 00:19:45,570 --> 00:19:47,140 >> Dabar D daroma. 478 00:19:47,140 --> 00:19:49,720 Dabar A. D--V-E-N yra įvartis. 479 00:19:49,720 --> 00:19:51,220 Taigi, dabar, ką aš ruošiuosi padaryti tai. 480 00:19:51,220 --> 00:19:54,027 Kai tik aš pradėjau D pranešimą nėra žymeklis ten. 481 00:19:54,027 --> 00:19:56,860 Tai šiukšlių vertybes metu, ar galiu inicijuoti ją nuliui. 482 00:19:56,860 --> 00:19:59,630 Bet leiskite man nesustoti su šis pastatas medis idėja. 483 00:19:59,630 --> 00:20:04,260 Leiskite skirti dar vieną iš šių mazgai, kad turi 26 elementų į jį. 484 00:20:04,260 --> 00:20:05,150 >> Ir žinote ką? 485 00:20:05,150 --> 00:20:09,130 Jei tai tik atminties mazgas kad Aš sukūriau su malloc, naudojant konstrukto 486 00:20:09,130 --> 00:20:11,240 kaip mes netrukus pamatysite, Aš ruošiuosi daryti this-- 487 00:20:11,240 --> 00:20:14,450 Aš ruošiuosi daryti rodyklę nuo dalykas, kad atstovauja D žemyn 488 00:20:14,450 --> 00:20:15,860 į šią naują mazgas. 489 00:20:15,860 --> 00:20:19,240 Ir dabar, pirmą kartą šalia raidė Daven pavadinimas, 490 00:20:19,240 --> 00:20:24,150 V-- D--V-- aš ruošiuosi eiti į priekį ir atkreipti kito mazgo, kaip tai, 491 00:20:24,150 --> 00:20:30,150 pagal kurią, "V elementai čia, kuris mes burtai instance-- oi. 492 00:20:30,150 --> 00:20:31,020 Mes ne atkreipti ten. 493 00:20:31,020 --> 00:20:31,936 Jis ketina eiti čia. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Tada mes einame manau, kad toks V. 496 00:20:35,712 --> 00:20:44,920 Ir tada žemyn čia mes ketiname indekso žemyn iš V į ką mes atsižvelgsime E. 497 00:20:44,920 --> 00:20:50,100 Ir tada iš čia mes ketiname eiti į vieną iš šių mazgų čia. 498 00:20:50,100 --> 00:20:52,930 Ir dabar mes turime atsakyti į klausimą. 499 00:20:52,930 --> 00:20:57,840 Man reikia kažkaip nurodyti, kad mes į eilutės Daven pabaigoje. 500 00:20:57,840 --> 00:20:59,490 Kad galėčiau tiesiog palikite jį niekiniu. 501 00:20:59,490 --> 00:21:02,670 >> Bet kas, jei mes turime Daven s vardas, pavardė, taip pat, kuris 502 00:21:02,670 --> 00:21:04,280 yra, kaip mes sakė, Davenport? 503 00:21:04,280 --> 00:21:06,970 Taigi ką daryti, jei Daven yra realiai substring, 504 00:21:06,970 --> 00:21:08,960 kur kas ilgesnį prefiksą eilutes? 505 00:21:08,960 --> 00:21:11,450 Mes negalime tiesiog nuolat pasakyti nieko nevyksta 506 00:21:11,450 --> 00:21:14,410 ten, nes mes galime niekada įterpti kaip Davenport žodį 507 00:21:14,410 --> 00:21:15,840 į šią duomenų struktūrą 508 00:21:15,840 --> 00:21:19,560 >> Taigi, ką mes galime padaryti, o ne yra gydyti kiekvieno iš šių elementų 509 00:21:19,560 --> 00:21:22,170 kaip gal turintys du elementai viduje iš jų. 510 00:21:22,170 --> 00:21:24,810 Vienas iš jų yra žymeklis, iš tikrųjų, kaip aš darau. 511 00:21:24,810 --> 00:21:27,100 Taigi kiekvieną iš šių dėžučių yra ne tik viena ląstelė. 512 00:21:27,100 --> 00:21:29,855 Bet kas, jei top one-- Apatinė s 513 00:21:29,855 --> 00:21:32,230 bus niekinis, nes nėra Davenport tik dar. 514 00:21:32,230 --> 00:21:34,197 Ką daryti, jei viršutinis vienas yra keletas specialių vertės? 515 00:21:34,197 --> 00:21:36,530 Ir tai bus šiek tiek Sunkutikėtis tai šis dydis. 516 00:21:36,530 --> 00:21:38,130 Bet tarkime, kad tai tik varnele. 517 00:21:38,130 --> 00:21:38,920 Patikrinkite. 518 00:21:38,920 --> 00:21:44,230 D--V-E-N yra string Šioje duomenų struktūrą. 519 00:21:44,230 --> 00:21:48,350 >> Tuo tarpu, jei aš turėjo daugiau erdvės čia aš galėčiau padaryti P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 ir aš galėčiau įdėti čekį mazgas kad turi raidę "T pačioje pabaigoje. 521 00:21:52,650 --> 00:21:55,460 Taigi tai yra masiškai sudėtingas atrodantis duomenų struktūrą. 522 00:21:55,460 --> 00:21:57,210 Ir mano rašysena tikrai nepadeda. 523 00:21:57,210 --> 00:22:00,043 Bet jei aš norėjau įdėti kažką kita, apsvarstyti, ką darytume. 524 00:22:00,043 --> 00:22:03,370 Jei mes norime įdėti į Dovydo, mes norime laikytis tos pačios logikos, D-A-V, 525 00:22:03,370 --> 00:22:08,802 bet dabar norėčiau į kitą elementas ne iš E, bet iš I į D. 526 00:22:08,802 --> 00:22:10,760 Taigi tai bus daugiau mazgų šio medžio. 527 00:22:10,760 --> 00:22:12,325 Mes ketiname turėti skambučio malloc daugiau. 528 00:22:12,325 --> 00:22:14,700 Bet aš nenoriu, kad pilnas netvarka šia nuotrauka. 529 00:22:14,700 --> 00:22:17,710 Taigi galime vietoj pažvelgti į vieną kad buvo iš anksto suformuluota 530 00:22:17,710 --> 00:22:21,810 kaip tai su ne dot, dot, dots, bet tik sutrumpintus matricas. 531 00:22:21,810 --> 00:22:23,950 Tačiau kiekvienas iš mazgų Šioje medžio čia 532 00:22:23,950 --> 00:22:26,700 atstovauja patį thing-- masyvas Ray dydžio 26. 533 00:22:26,700 --> 00:22:28,860 >> Arba, jei norime būti tikrai teisingas dabar ką 534 00:22:28,860 --> 00:22:30,790 jei kažkieno pavadinimas Apostrofs, galime 535 00:22:30,790 --> 00:22:35,560 daroma prielaida, kad kiekvienas mazgas iš tikrųjų turi kaip 27 indeksų ja, o ne tik 26. 536 00:22:35,560 --> 00:22:42,020 Taigi tai dabar bus duomenys struktūra vadinama trie-- T-R-i-E. 537 00:22:42,020 --> 00:22:46,120 TRIE, kuris yra tariamai istoriškai protingas pavadinimas medį 538 00:22:46,120 --> 00:22:49,040 kad optimizuotas paieška, kuri, žinoma,, 539 00:22:49,040 --> 00:22:50,870 rašomas su I-E todėl TRIE. 540 00:22:50,870 --> 00:22:52,710 Bet tai yra TRIE istorija. 541 00:22:52,710 --> 00:22:55,860 >> Taigi TRIE tai medis-kaip duomenys struktūra kaip šeimos medį 542 00:22:55,860 --> 00:22:57,510 kad galiausiai elgiasi kaip kad. 543 00:22:57,510 --> 00:23:00,890 Ir čia yra tik dar vienas pavyzdys, visa krūva kitų žmonių vardus. 544 00:23:00,890 --> 00:23:03,540 Bet klausimas dabar po ranka, kas turi 545 00:23:03,540 --> 00:23:08,070 įgijome įvedant tikriausiai daugiau sudėtingas duomenų struktūra, ir vienas, 546 00:23:08,070 --> 00:23:09,870 tiesą sakant, kad naudoja daug atminties. 547 00:23:09,870 --> 00:23:11,703 >> Nes nors, Šiuo metu, aš tik 548 00:23:11,703 --> 00:23:15,050 naudojant apie D žymeklį ir Ir V ir Es ir Ns, 549 00:23:15,050 --> 00:23:16,700 Aš eikvoti daug atminties Heck. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Bet kur praleidžiu vienas šaltinis, Aš linkęs daryti įgyti atgal kitą. 552 00:23:22,660 --> 00:23:26,020 Taigi, jei aš išleisti daugiau vietos, kas tikriausiai viltis? 553 00:23:26,020 --> 00:23:27,407 Kad aš išleisti mažiau ką? 554 00:23:27,407 --> 00:23:28,240 AUDITORIJA: Mažiau laiko. 555 00:23:28,240 --> 00:23:28,990 DAVID Malan: Laikas. 556 00:23:28,990 --> 00:23:30,320 Dabar kodėl gali būti? 557 00:23:30,320 --> 00:23:33,880 Na, kas yra įtraukimas laikas, kalbant apie didįjį O dabar, 558 00:23:33,880 --> 00:23:37,660 panašaus Daven pavadinimas arba Davenport ar David? 559 00:23:37,660 --> 00:23:39,340 Na, Daven buvo penki žingsniai. 560 00:23:39,340 --> 00:23:42,350 Davenport būtų devyni žingsniai, todėl būtų dar kelis žingsnius. 561 00:23:42,350 --> 00:23:44,250 Davidas būtų penki žingsniai, kaip gerai. 562 00:23:44,250 --> 00:23:47,230 Taigi tie konkretūs numeriai, tačiau, be abejo, nėra 563 00:23:47,230 --> 00:23:49,550 viršutinė ant ilgis kažkieno vardą. 564 00:23:49,550 --> 00:23:52,240 Ir iš tiesų, su šia problema rinkiniai penkių specifikacijos, 565 00:23:52,240 --> 00:23:54,050 mes ketiname pasiūlyti kad tai kažkas 566 00:23:54,050 --> 00:23:55,470 tai 40-kai-nelyginis simbolių. 567 00:23:55,470 --> 00:23:58,180 >> Nereikėtų pamiršti, niekas neturi be galo ilgas vardas, 568 00:23:58,180 --> 00:24:01,542 kuri yra pasakyti, kad iš ilgis pavadinimas ar iš eilutės ilgis būtume 569 00:24:01,542 --> 00:24:03,750 turėti tam tikrą valstybinės struktūra yra neabejotinai ką? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Tai pastovus. 572 00:24:06,250 --> 00:24:06,430 Teisė? 573 00:24:06,430 --> 00:24:09,310 Tai gali būti didelis nuolatinis kaip 40-kažkas, bet jis yra pastovus. 574 00:24:09,310 --> 00:24:13,752 Ir jis neturi priklausomybės nuo kiek kiti pavadinimai yra šioje duomenų struktūra. 575 00:24:13,752 --> 00:24:15,460 Kitaip tariant, jei I norėjau dabar įterpti 576 00:24:15,460 --> 00:24:20,540 Colton arba Gabriel arba Rob arba Zamyla arba Alison arba Belinda ar kitus pavadinimus 577 00:24:20,540 --> 00:24:23,940 iš darbuotojų į šiuos duomenis struktūra, yra veikimo laikas 578 00:24:23,940 --> 00:24:26,750 įterpti kitų pavadinimų bus ne paveikė 579 00:24:26,750 --> 00:24:30,220 pagal tai, kaip ir daugelis kitų elementų duomenų jau struktūros? 580 00:24:30,220 --> 00:24:31,040 Tai ne. 581 00:24:31,040 --> 00:24:31,540 Teisė? 582 00:24:31,540 --> 00:24:36,150 Nes mes iš tikrųjų naudoti tai daugiasluoksnis maišos lentelė. 583 00:24:36,150 --> 00:24:38,280 Ir veikimo laikas bet kuris šių operacijų 584 00:24:38,280 --> 00:24:41,510 priklauso ne nuo skaičiaus elementai, kurie yra duomenų struktūros 585 00:24:41,510 --> 00:24:43,090 arba kad ilgainiui ketiname būti duomenų struktūros, 586 00:24:43,090 --> 00:24:44,714 bet apie tai, ką konkrečiai ilgio? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> Styginių yra įdėta, kuris tikrai daro 589 00:24:49,200 --> 00:24:52,580 tai asimptotiškai pastovus LAIKĄ_ didelis O vienas. 590 00:24:52,580 --> 00:24:54,720 Ir tiesą sakant, kaip tik realiame pasaulyje, tai 591 00:24:54,720 --> 00:24:58,380 reiškia įterpiant Daven vardas trunka kaip penkių etapų, arba Davenport devyni 592 00:24:58,380 --> 00:25:00,100 žingsniai, arba Davidas penki žingsniai. 593 00:25:00,100 --> 00:25:03,071 Tai gana adyti maži rodymo laiku. 594 00:25:03,071 --> 00:25:05,320 Ir, tiesą sakant, tai labai geras dalykas, ypač kai 595 00:25:05,320 --> 00:25:08,126 tai nepriklauso nuo viso skaičius elementų ten. 596 00:25:08,126 --> 00:25:10,500 Taigi, kaip gali mes įgyvendinti šį rūšies struktūros kodą? 597 00:25:10,500 --> 00:25:12,900 Tai šiek tiek daugiau sudėtingas, bet vis tiek tai 598 00:25:12,900 --> 00:25:15,050 tiesiog iš paraiškos pagrindiniai blokai. 599 00:25:15,050 --> 00:25:17,830 Aš einu iš naujo mums mazgas taip: 600 00:25:17,830 --> 00:25:21,100 bool vadinamas word-- ir tai būtų galima pavadinti nieko. 601 00:25:21,100 --> 00:25:23,970 Bet bool atstovauja ką aš patraukė kaip varnele. 602 00:25:23,970 --> 00:25:24,490 Taip. 603 00:25:24,490 --> 00:25:26,720 Tai virvele pabaiga Šioje duomenų struktūrą. 604 00:25:26,720 --> 00:25:30,702 >> Ir, žinoma, mazgas žvaigždė ten yra nuoroda į vaikus. 605 00:25:30,702 --> 00:25:32,410 Ir, tiesą sakant, kaip tik patinka šeimos medis, jūs 606 00:25:32,410 --> 00:25:34,370 būtų apsvarstyti mazgų kad kabo išjungti 607 00:25:34,370 --> 00:25:36,920 iš kai kurių tėvų apačioje elementas turi būti vaikai. 608 00:25:36,920 --> 00:25:40,510 Ir todėl vaikai ruošiasi būti 27 masyvas, 27. vienas 609 00:25:40,510 --> 00:25:41,680 tiesiog yra už kabutes. 610 00:25:41,680 --> 00:25:43,390 Mes ketiname rūšiuoti specialieji atvejai toje. 611 00:25:43,390 --> 00:25:45,400 Todėl jūs galite turėti tam tikrą vardus kabutes. 612 00:25:45,400 --> 00:25:47,399 Gal net brūkšnelis turėtų eiti ten, bet jūs 613 00:25:47,399 --> 00:25:50,330 matyti p rinkinys 5 mes tik priežiūros apie raidžių ir kabutes. 614 00:25:50,330 --> 00:25:52,990 >> Ir tada, kaip jūs atstovauti pati duomenų struktūra? 615 00:25:52,990 --> 00:25:56,454 Kaip jūs atstovauti šaknis Šio TRIE, taip sakant? 616 00:25:56,454 --> 00:25:59,620 Na, tiesiog norėčiau su susietą sąrašą, jūs reikia žymiklį į pirmąjį elementą. 617 00:25:59,620 --> 00:26:04,270 Su TRIE tereikia vieną rodyklę į šios TRIE šaknis. 618 00:26:04,270 --> 00:26:07,290 Ir iš ten galite koduoti jūsų kelią žemyn giliau ir giliau 619 00:26:07,290 --> 00:26:10,460 į kiekvieno kito mazgo konstrukcijos. 620 00:26:10,460 --> 00:26:13,440 Taigi tiesiog su tai gali mes, tą konstrukto. 621 00:26:13,440 --> 00:26:15,877 >> Dabar Meanwhile-- Oi, klausimą. 622 00:26:15,877 --> 00:26:17,220 >> AUDITORIJA: Kas bool žodis? 623 00:26:17,220 --> 00:26:20,490 >> DAVID Malan: bool žodis tiesiog tai C įsikūnijimas 624 00:26:20,490 --> 00:26:22,920 ką aprašiau čia, kai rėmelio 625 00:26:22,920 --> 00:26:26,000 Aš pradėjau padalijant kiekvienas Array jo elementus į dvi dalis. 626 00:26:26,000 --> 00:26:27,600 Vienas iš jų yra rodyklė į kitą mazgas. 627 00:26:27,600 --> 00:26:30,280 Kitas turi būti kažkas panašaus į langelį 628 00:26:30,280 --> 00:26:33,770 pasakyti taip, yra Žodis Daven kad baigiasi čia, 629 00:26:33,770 --> 00:26:35,610 nes mes nenorime, Šiuo metu Dave. 630 00:26:35,610 --> 00:26:39,320 >> Nors Dave bus teisėtas žodis, jis ne TRIE 631 00:26:39,320 --> 00:26:39,830 dar. 632 00:26:39,830 --> 00:26:40,950 Ir D yra ne žodis. 633 00:26:40,950 --> 00:26:42,770 Ir D-nėra žodis ar vardas. 634 00:26:42,770 --> 00:26:45,020 Taigi žymės rodo tik vieną kartą jums 635 00:26:45,020 --> 00:26:48,190 hit tai mazgas Ankstesnis takelis simbolių 636 00:26:48,190 --> 00:26:50,700 faktiškai seka, jūs įdėta. 637 00:26:50,700 --> 00:26:53,660 Kad viskas bool ten daro už mus. 638 00:26:53,660 --> 00:26:55,500 >> Bet kokie kiti klausimai bando? 639 00:26:55,500 --> 00:26:56,215 Taip. 640 00:26:56,215 --> 00:26:58,035 >> AUDITORIJA: Kas sutampa? 641 00:26:58,035 --> 00:26:59,945 Ką daryti, jei turite Dave ir Daven? 642 00:26:59,945 --> 00:27:00,820 DAVID Malan: Perfect. 643 00:27:00,820 --> 00:27:02,580 Ką daryti, jei turite Dave ir Daven? 644 00:27:02,580 --> 00:27:06,240 Taigi, jei mes įdėti, tarkim slapyvardį, už David-- Dave-- D-a-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Tai iš tikrųjų yra super paprasta. 647 00:27:08,700 --> 00:27:10,325 Taigi mes tik ketina imtis keturių veiksmų. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D--V-E. Ir ką aš turiu daryti, kai aš paspauskite, kad ketvirtą mazgas? 650 00:27:15,847 --> 00:27:16,680 Tik ketina patikrinti. 651 00:27:16,680 --> 00:27:18,000 Mes jau gerai eiti. 652 00:27:18,000 --> 00:27:18,840 Atlikta. 653 00:27:18,840 --> 00:27:19,750 Keturi žingsniai. 654 00:27:19,750 --> 00:27:21,590 Pastovus laikas asimptotiškai. 655 00:27:21,590 --> 00:27:26,300 Ir dabar mes nurodyta, kad Dave ir Daven raišteliai Struktūros. 656 00:27:26,300 --> 00:27:27,710 Taigi nėra problema. 657 00:27:27,710 --> 00:27:30,200 Ir atkreipkite dėmesį, kaip buvimą iš Daven nebespėjo 658 00:27:30,200 --> 00:27:34,750 imtis daugiau laiko ar mažiau laikas Dave ir atvirkščiai. 659 00:27:34,750 --> 00:27:36,000 >> Taigi, ką dar mes galime padaryti dabar? 660 00:27:36,000 --> 00:27:40,680 Mes naudojama ši metafora prieš iš dėklų atstovaujanti kažką. 661 00:27:40,680 --> 00:27:43,380 Tačiau paaiškėja, kad kamino padėklai iš tiesų yra 662 00:27:43,380 --> 00:27:47,187 demonstratyvus kitos abstrakčios duomenų type-- aukštesnio lygio duomenų struktūros 663 00:27:47,187 --> 00:27:49,770 kad pabaigoje diena yra tiesiog kaip masyvo ar susietą sąrašą 664 00:27:49,770 --> 00:27:50,970 ar kažkas daugiau kasdieniškas. 665 00:27:50,970 --> 00:27:53,270 Bet tai įdomiau konceptualus koncepcija. 666 00:27:53,270 --> 00:27:56,440 Kamino, kaip šie Dėklų čia Mather, 667 00:27:56,440 --> 00:27:58,750 paprastai vadinamas tiesiog that-- kamino. 668 00:27:58,750 --> 00:28:02,540 >> Ir šioje duomenų konstrukcijos tipo Jūs turite dvi operations-- 669 00:28:02,540 --> 00:28:05,880 turite vieną, pavadintą impulsą pridėti kažką į kaminą, 670 00:28:05,880 --> 00:28:08,320 kaip pradėti kitą dėklą atgal ant kamino viršaus. 671 00:28:08,320 --> 00:28:11,350 Ir tada pop, o tai reiškia, jums imtis Viršutinis dėklas off. 672 00:28:11,350 --> 00:28:16,210 Bet kas svarbiausia apie šūsnis kad jis gavo šį įdomų charakteristika. 673 00:28:16,210 --> 00:28:19,560 Kaip valgykloje darbuotojų yra pertvarkant padėklai kito valgio, 674 00:28:19,560 --> 00:28:21,380 kas bus tiesa apie tai, kaip studentai 675 00:28:21,380 --> 00:28:22,856 bendrauti su šios duomenų struktūros? 676 00:28:22,856 --> 00:28:24,480 AUDITORIJA: jie ketina pop vienkartinis. 677 00:28:24,480 --> 00:28:26,550 DAVID Malan: jie ketina pop vienkartinis ir, tikėkimės viršų. 678 00:28:26,550 --> 00:28:28,910 Kitaip tai tiesiog rūšies kvailas pereiti visą kelią į apačią. 679 00:28:28,910 --> 00:28:29,070 Teisė? 680 00:28:29,070 --> 00:28:31,620 Duomenų struktūra nėra tikrai leidžia Jūs patraukti apatinį dėklą bent 681 00:28:31,620 --> 00:28:32,520 lengvai. 682 00:28:32,520 --> 00:28:35,040 Todėl ten tai įdomu nuosavybė į rietuvę 683 00:28:35,040 --> 00:28:39,730 kad paskutinis elementas yra bus pirmasis iš. 684 00:28:39,730 --> 00:28:43,400 Ir kompiuterių mokslininkai vadina tai LIFO-- trukti in, first out. 685 00:28:43,400 --> 00:28:45,540 Ir jis iš tikrųjų neturi būti Įdomios programos. 686 00:28:45,540 --> 00:28:50,090 Tai nebūtinai tokia akivaizdi, kaip kai kiti, tačiau jis gali, iš tikrųjų, būti naudinga, 687 00:28:50,090 --> 00:28:54,040 ir ji iš tikrųjų gali būti įgyvendinta keliais skirtingais būdais pora. 688 00:28:54,040 --> 00:28:58,550 >> Taigi vienas, ir tikrai, tegul man ne pasinerti į tą. 689 00:28:58,550 --> 00:28:59,860 Leiskite tai padaryti vietoj. 690 00:28:59,860 --> 00:29:03,700 Leiskite pažvelgti į vieną, kad beveik pačią idėją, bet tai šiek tiek teisingiau. 691 00:29:03,700 --> 00:29:04,200 Teisė? 692 00:29:04,200 --> 00:29:07,560 Jei esate vienas iš šių ventiliatorių berniukams arba merginos, kad tikrai patinka Apple produktus 693 00:29:07,560 --> 00:29:10,130 ir jūs prabudau 03:00 išsirikiuoti tikru parduotuvėje 694 00:29:10,130 --> 00:29:14,150 gauti pačią naujausią "iPhone, jūs galėjo eilę, kaip šis. 695 00:29:14,150 --> 00:29:15,800 >> Dabar eilė labai sąmoningai pavadinta. 696 00:29:15,800 --> 00:29:18,190 Tai linija, nes ten kai teisingumas jai. 697 00:29:18,190 --> 00:29:18,690 Teisė? 698 00:29:18,690 --> 00:29:21,690 Būtų rūšies čiulpti jei jūs gavo ten pirmas ne Apple Store 699 00:29:21,690 --> 00:29:25,700 bet tai jūs Žemiausias dėklas, nes "Apple" darbuotojai tuomet 700 00:29:25,700 --> 00:29:28,189 pop paskutinis asmuo, kuris iš tikrųjų gavo į eilutę. 701 00:29:28,189 --> 00:29:31,230 Taigi kaminai ir eilėse, nors funkciškai jie Pirties same-- 702 00:29:31,230 --> 00:29:33,105 tai tik ši kolekcija išteklių, kad yra 703 00:29:33,105 --> 00:29:36,210 augs ir shrink-- ten tai teisingumas aspektas į ją, 704 00:29:36,210 --> 00:29:39,634 bent jau realiame pasaulyje, kai skrydžiai jūs naudotis 705 00:29:39,634 --> 00:29:40,800 iš esmės skiriasi. 706 00:29:40,800 --> 00:29:43,360 Stack-- eilė rather-- yra sakoma, kad 707 00:29:43,360 --> 00:29:45,320 dvi operacijos: n eilę ir d eilėje. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Arba galite skambinti bet daug dalykų. 710 00:29:48,090 --> 00:29:50,770 Bet jūs tiesiog norite fotografuoti Požiūris, kad vienas yra pridėti 711 00:29:50,770 --> 00:29:53,230 ir vienas galiausiai atimant. 712 00:29:53,230 --> 00:29:58,840 >> Dabar po kapotu, tiek kamino ir eilė gali būti įgyvendinta, kaip? 713 00:29:58,840 --> 00:30:01,390 Mes neisime į kodą tai todėl, kad aukštesnio lygio 714 00:30:01,390 --> 00:30:03,387 idėja yra tarsi labiau akivaizdu. 715 00:30:03,387 --> 00:30:04,470 Aš turiu galvoje, ką žmogui daryti? 716 00:30:04,470 --> 00:30:07,030 Jei aš pirmas žmogus į "Apple" Saugoti ir tai yra visą durys, 717 00:30:07,030 --> 00:30:08,130 žinote, aš čia stovėti. 718 00:30:08,130 --> 00:30:09,750 O kitą asmens vyksta čia stovėti. 719 00:30:09,750 --> 00:30:11,500 O kitą asmens vyksta čia stovėti. 720 00:30:11,500 --> 00:30:13,792 Taigi, kas duomenų struktūra skolina pati į eilę? 721 00:30:13,792 --> 00:30:14,542 >> AUDITORIJA: eilė. 722 00:30:14,542 --> 00:30:15,667 DAVID Malan: Na, eilė. 723 00:30:15,667 --> 00:30:16,390 Tikrai. 724 00:30:16,390 --> 00:30:16,920 Ką dar? 725 00:30:16,920 --> 00:30:17,600 >> AUDITORIJA: susijęs sąrašas. 726 00:30:17,600 --> 00:30:18,990 >> DAVID Malan: susijęs sąrašą galite įgyvendinti. 727 00:30:18,990 --> 00:30:22,500 Ir susijęs sąrašas yra gražus, nes tada jis gali augti savavališkai ilgas, palyginti 728 00:30:22,500 --> 00:30:24,880 į tam tikra fiksuotą skaičių žmonių parduotuvėje. 729 00:30:24,880 --> 00:30:27,030 Bet gal fiksuotas skaičius Vietų yra teisėtas. 730 00:30:27,030 --> 00:30:30,350 Nes jei jie turi tik kaip 20 iPhone, pirmą dieną, o gal 731 00:30:30,350 --> 00:30:33,930 jiems reikia tik jo dydis masyvo 20, tą eilę, kuri 732 00:30:33,930 --> 00:30:37,070 tik pasakyti dabar, kai mes pradedame kalbėti apie šių aukštesnio lygio problemos, 733 00:30:37,070 --> 00:30:38,890 galite ją įgyvendinti bet keliais būdais. 734 00:30:38,890 --> 00:30:42,030 Ir ten tikriausiai tik ketina būti kompromiso erdvėje ir laike 735 00:30:42,030 --> 00:30:43,950 arba tiesiog į savo kodą sudėtingumo. 736 00:30:43,950 --> 00:30:45,380 >> Ką apie kamino? 737 00:30:45,380 --> 00:30:48,190 Na, kamino, mes matėme per gali būti tik šie padėklai. 738 00:30:48,190 --> 00:30:50,007 Ir tu gali įgyvendinti tai masyvas. 739 00:30:50,007 --> 00:30:53,090 Bet tam tikru momentu, jei naudoti masyvą, kas nutiks su padėklai 740 00:30:53,090 --> 00:30:54,173 Jūs bandote pribaigti? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Gerai. 743 00:30:55,670 --> 00:30:57,490 Jūs tik ketina galėti eiti taip didelis. 744 00:30:57,490 --> 00:31:00,156 Ir manau, kad į Mather jie realiai potinkinis toje atidarymo. 745 00:31:00,156 --> 00:31:01,950 Taigi iš tikrųjų, tai beveik kaip Mather naudoja 746 00:31:01,950 --> 00:31:03,783 Fiksuoto dydžio masyvas, nes galite tik 747 00:31:03,783 --> 00:31:08,302 tilpti tiek daug padėklai toje atidarymo sienos žemyn žemiau žmonių kelio. 748 00:31:08,302 --> 00:31:10,010 Ir taip, kad galėtų būti Sakoma, kad masyvas, 749 00:31:10,010 --> 00:31:14,300 bet mes tikrai galėtų įgyvendinti, kad plačiau su susietą sąrašą. 750 00:31:14,300 --> 00:31:16,390 >> Na, ką galima pasakyti apie kitą duomenų struktūros? 751 00:31:16,390 --> 00:31:18,760 Leiskite atsigriebti vieną kitą vaizdinį čia. 752 00:31:18,760 --> 00:31:24,710 Kažkas panašaus, kaip apie šį vieną čia? 753 00:31:24,710 --> 00:31:28,920 Kodėl tai gali būti naudinga turėti ne kažkas kaip išgalvotas kaip TRIE, kuris 754 00:31:28,920 --> 00:31:32,370 matėme turėjo šiuos labai didelius mazgus, kiekvienas iš kurių yra masyve? 755 00:31:32,370 --> 00:31:35,740 Bet kas, jei mes darome ką nors daugiau tiesiog, kaip senosios mokyklos šeimos medį, 756 00:31:35,740 --> 00:31:38,110 kiekvieno iš jų mazgai čia tiesiog saugoti numerį. 757 00:31:38,110 --> 00:31:42,180 Vietoj vardo ar palikuonis tiesiog saugoti kaip šis numeris. 758 00:31:42,180 --> 00:31:45,250 >> Na, žargono mes naudojame duomenų struktūros yra tiek bando 759 00:31:45,250 --> 00:31:49,510 ir medžiai, kur TRIE vėlgi yra tik vienas, kurio mazgai yra matricos, 760 00:31:49,510 --> 00:31:51,680 dar ką galite naudoti nuo pradinėje mokykloje 761 00:31:51,680 --> 00:31:53,860 kai padarė šeimą tree-- lapai ir šaknys 762 00:31:53,860 --> 00:31:57,250 Medžio ir vaikams tėvų ir jų broliai ir seserys. 763 00:31:57,250 --> 00:32:03,670 Ir mes galime įgyvendinti medį, pavyzdžiui, kaip tiesiog kaip šis. 764 00:32:03,670 --> 00:32:07,420 Medis, jei jį kaip mazgas, vienas šie apskritimai, kurio numeris, 765 00:32:07,420 --> 00:32:09,947 jis nesiruošia turėti vienas žymeklis, bet du. 766 00:32:09,947 --> 00:32:11,780 Ir kuo greičiau jūs pridedate Antrasis žymeklis, jums 767 00:32:11,780 --> 00:32:13,905 iš tikrųjų gali dabar padaryti rūšiuoti iš dvimatis duomenų 768 00:32:13,905 --> 00:32:14,780 struktūros atmintyje. 769 00:32:14,780 --> 00:32:16,660 Panašiai kaip dvimatis masyvas, jūs galite 770 00:32:16,660 --> 00:32:18,904 turėti natūra dvimačių susiję sąrašus, o tie, 771 00:32:18,904 --> 00:32:20,820 kad galutinių schemas kur nėra jokių ciklų. 772 00:32:20,820 --> 00:32:24,487 Tai tikrai medis su vienu senelių būdas čia ir tada 773 00:32:24,487 --> 00:32:27,320 kai tėvai ir vaikai, ir vaikaičiams ir provaikaičiams. 774 00:32:27,320 --> 00:32:28,370 ir kt. 775 00:32:28,370 --> 00:32:32,390 >> Bet kas tikrai tvarkingas apie tai per daug, tiesiog erzinti jus su šiek tiek kodo, 776 00:32:32,390 --> 00:32:35,370 priminti rekursija iš Trumpam grįžo, kuriuo 777 00:32:35,370 --> 00:32:38,220 Rašydami funkciją, kuri vadina save. 778 00:32:38,220 --> 00:32:41,140 Tai gražus proga įgyvendinti kažką 779 00:32:41,140 --> 00:32:42,920 kaip rekursijos, nes mano, kad tai. 780 00:32:42,920 --> 00:32:43,860 >> Tai medis. 781 00:32:43,860 --> 00:32:48,040 Ir aš buvau šiek tiek analinis su tuo, kaip Aš įdėti skaičiais į gatvę. 782 00:32:48,040 --> 00:32:51,020 Tiek daug, kad ji turi ypatingą name-- dvejetainis paieškos medis. 783 00:32:51,020 --> 00:32:53,460 Dabar mes girdėjote apie dvejetainis ieškoti, bet jūs galite 784 00:32:53,460 --> 00:32:55,180 dirbti atgal nuo šio dalyko pavadinimas? 785 00:32:55,180 --> 00:32:59,280 Kas yra, kaip aš modelis Įterpiamas skaičiais į šio medžio? 786 00:32:59,280 --> 00:33:00,696 Tai ne savavališkai. 787 00:33:00,696 --> 00:33:01,570 Yra keletas modelis. 788 00:33:01,570 --> 00:33:02,090 Taip. 789 00:33:02,090 --> 00:33:03,370 >> AUDITORIJA: mažesnių kairėje. 790 00:33:03,370 --> 00:33:03,690 >> DAVID Malan: Taip. 791 00:33:03,690 --> 00:33:05,062 Mažesnių yra kairėje. 792 00:33:05,062 --> 00:33:06,270 Didesnės iš jų yra dešinėje. 793 00:33:06,270 --> 00:33:12,940 Toks, kad pareiškimas yra tiesa tėvų yra didesnė už jo kairiojo vaikui, 794 00:33:12,940 --> 00:33:14,850 bet mažesnis negu jo dešinės vaikui. 795 00:33:14,850 --> 00:33:17,750 Ir kad tik jis dar pakartotinė žodinis apibrėžimas 796 00:33:17,750 --> 00:33:20,500 nes galite kreiptis, kad Ta pati logika kiekvienas mazgas 797 00:33:20,500 --> 00:33:23,080 ir ji tik dugnai out, bazinį scenarijų, jei jums 798 00:33:23,080 --> 00:33:25,740 bus, kai paspausite vieną iš lapai, taip sakant, 799 00:33:25,740 --> 00:33:28,580 kur atostogos neturi vaikų dar. 800 00:33:28,580 --> 00:33:30,614 >> Dabar, kaip gali rasti skaičių 44? 801 00:33:30,614 --> 00:33:32,280 Galima būtų pradėti nuo šaknų ir pasakyti, HM. 802 00:33:32,280 --> 00:33:35,690 55 yra ne 44 Taigi aš noriu eiti teisė ar aš noriu eiti į kairę? 803 00:33:35,690 --> 00:33:37,190 Na, žinoma, jūs norite eiti į kairę. 804 00:33:37,190 --> 00:33:40,060 Ir todėl, kaip ir telefone knyga pavyzdys dvejetainėje paieškos 805 00:33:40,060 --> 00:33:41,099 plačiau. 806 00:33:41,099 --> 00:33:43,390 Bet mes ją įgyvendinti Dabar šiek tiek dinamiškiau 807 00:33:43,390 --> 00:33:45,339 nei masyvas gali leisti. 808 00:33:45,339 --> 00:33:48,130 Ir iš tiesų, jei norite ieškoti į kodą, iš pirmo žvilgsnio, tikrai. 809 00:33:48,130 --> 00:33:49,671 Atrodo, visa krūva linijų. 810 00:33:49,671 --> 00:33:51,220 Bet tai gražiai paprasta. 811 00:33:51,220 --> 00:33:54,490 Jei norite įdiegti funkciją vadinama paieška kurio gyvenimo tikslas 812 00:33:54,490 --> 00:33:57,290 yra ieškoti vertė kaip n, sveikasis skaičius, 813 00:33:57,290 --> 00:34:01,756 ir jūs išlaikė per vieną pointer-- rodyklė į šaknų mazgas, 814 00:34:01,756 --> 00:34:04,380 o, tos medžio, iš kurios Jūs galite patekti visa kita, 815 00:34:04,380 --> 00:34:08,850 pranešimas, kaip tiesmukai jūs galite įgyvendinti logika. 816 00:34:08,850 --> 00:34:10,880 Jei medis yra niekinis, žinoma, ji nėra ten. 817 00:34:10,880 --> 00:34:11,880 Tegul tik return false. 818 00:34:11,880 --> 00:34:12,000 Teisė? 819 00:34:12,000 --> 00:34:14,040 Jei vertus, nieko, nieko ten. 820 00:34:14,040 --> 00:34:17,900 >> Kitur, jei n yra mažesnis nei medis rodyklė n-- dabar arrow n, 821 00:34:17,900 --> 00:34:20,670 prisiminti įdiegėme super trumpai kitą dieną, 822 00:34:20,670 --> 00:34:25,100 ir kad tik reiškia, de-nuorodą žymeklis ir pažvelgti į lauką, vadinamą n. 823 00:34:25,100 --> 00:34:27,690 Taigi tai reiškia, ten ir pažvelgti į lauką, vadinamą n. 824 00:34:27,690 --> 00:34:33,810 Taigi, jei n, vertė jums suteikta, yra mažiau nei į medžius sveiko skaičiaus, 825 00:34:33,810 --> 00:34:35,449 kur tu nori eiti? 826 00:34:35,449 --> 00:34:36,389 Į kairę. 827 00:34:36,389 --> 00:34:37,780 >> Taigi pastebėsite rekursija. 828 00:34:37,780 --> 00:34:39,860 Aš returning-- netiesa. 829 00:34:39,860 --> 00:34:40,989 Nėra netikras. 830 00:34:40,989 --> 00:34:45,670 Aš grįžti nepriklausomai atsakymą iš pokalbio su savimi, einančios 831 00:34:45,670 --> 00:34:50,100 n vėl, kuris yra nereikalingas, bet tai, kas šiek tiek kitokia? 832 00:34:50,100 --> 00:34:51,989 Kaip aš padaryti problemą mažesnis? 833 00:34:51,989 --> 00:34:54,920 Aš einančios kaip antrą argumentas, ne iš medžio šaknis, 834 00:34:54,920 --> 00:34:59,616 bet liko vaikas šioje byloje. 835 00:34:59,616 --> 00:35:00,990 Taigi, aš artimųjų kairėje vaikui. 836 00:35:00,990 --> 00:35:04,720 >> Tuo tarpu, jei n yra didesnis nei mazgas Aš šiuo metu ieško, 837 00:35:04,720 --> 00:35:06,690 Ieškoti dešinės pusės. 838 00:35:06,690 --> 00:35:10,880 Kita, jei medis yra ne niekinis, ir jei elementas ne į kairę 839 00:35:10,880 --> 00:35:13,240 ir tai ne į dešinę, kas nuostabiai atvejis? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Mes iš tikrųjų nustatė, kad mazgas klausimas, ir todėl mes grąžina true. 842 00:35:18,440 --> 00:35:21,490 >> Taigi mes tiesiog subraižyti paviršių dabar kai kurie iš šių duomenų struktūras. 843 00:35:21,490 --> 00:35:24,370 Be problemų nustatyti penki jums ištirti jų dar toliau, 844 00:35:24,370 --> 00:35:27,250 ir jums bus suteikta jūsų dizainas pasirinkimas, kaip eiti apie tai. 845 00:35:27,250 --> 00:35:30,250 Ką aš norėčiau padaryti išvadą yra tik 30 antra kibinimas 846 00:35:30,250 --> 00:35:32,080 kas laukia kitą savaitę ir vėliau. 847 00:35:32,080 --> 00:35:35,390 >> Kaip mes begin-- laimei jums gali think-- mūsų perėjimą lėtai 848 00:35:35,390 --> 00:35:38,680 iš C ir mažesnė pasaulyje lygis įgyvendinimo informacija, 849 00:35:38,680 --> 00:35:42,090 į pasaulį, kuriame mes galime imtis už savaime suprantama, kad kažkas pagaliau 850 00:35:42,090 --> 00:35:44,010 įgyvendinti šiuos duomenis struktūros mus 851 00:35:44,010 --> 00:35:47,570 ir mes pradėsime suprasti realiame pasaulyje, priimdama įgyvendinimo 852 00:35:47,570 --> 00:35:50,560 interneto programos ir svetainės apskritai 853 00:35:50,560 --> 00:35:52,910 taip pat ir labai saugumas Poveikis kad mes tik 854 00:35:52,910 --> 00:35:54,850 pradėjo kapstyti paviršių. 855 00:35:54,850 --> 00:35:57,320 Štai kas mūsų laukia į dienų į priekį. 856 00:35:57,320 --> 00:36:00,480 >> [VIDEO PLAYBACK] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -Jis Atėjo su žinia, su protokolu visa savo. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Jis atėjo iš žiaurus pasaulis ugniasienės, negailestinga planeta maršrutizatoriai, 861 00:36:30,894 --> 00:36:33,368 ir pavojai daug blogesni nei mirtis. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Jis greitas. 864 00:36:36,236 --> 00:36:37,980 Jis stiprus. 865 00:36:37,980 --> 00:36:42,830 Jis TCP / IP, ir jis gavo savo adresą. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Warriors tinkle". 868 00:36:48,074 --> 00:36:49,660 [END VIDEO PLAYBACK] 869 00:36:49,660 --> 00:36:50,910 DAVID Malan: kitą savaitę. 870 00:36:50,910 --> 00:36:51,880 Pamatysime jums tada. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [VIDEO PLAYBACK] 873 00:36:56,060 --> 00:36:59,240 -O Dabar, "Deep Thoughts" iki Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Visada prasideda paskaitos, kurių: "Gerai." 876 00:37:05,820 --> 00:37:08,750 Kodėl gi ne, "Štai sprendimas į šią savaitę, problemą, " 877 00:37:08,750 --> 00:37:12,180 arba "Mes suteikiame jums visiems?" 878 00:37:12,180 --> 00:37:13,380 [Atsakyti] 879 00:37:13,380 --> 00:37:15,530 [END VIDEO PLAYBACK]