1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID Malan: U redu. 3 00:00:12,250 --> 00:00:13,860 Dobrodošli natrag u CS50. 4 00:00:13,860 --> 00:00:16,190 Ovo je početak tjedna 8.. 5 00:00:16,190 --> 00:00:21,320 I sjećam taj problem set završio 5. s malo izazov. 6 00:00:21,320 --> 00:00:25,210 Dakle, uz pretpostavku da oporavio sve vaše nastavnih Fellows i tvrtke CA fotografije 7 00:00:25,210 --> 00:00:30,480 u card.raw datoteke, imate pravo Sada se nalaze svi ti ljudi, i 8 00:00:30,480 --> 00:00:34,510 jedan sretan dobitnik će hodati s jednom od ovih stvari, skok motion 9 00:00:34,510 --> 00:00:37,450 uređaj koji možete koristiti za konačni projekte, na primjer. 10 00:00:37,450 --> 00:00:39,860 >> To, svake godine, dovodi do malo creepiness. 11 00:00:39,860 --> 00:00:43,480 I tako ono što sam mislio da ću učiniti je podijeliti s vama neke od obveza koje 12 00:00:43,480 --> 00:00:47,370 otišao natrag i naprijed preko Osoblje popis kasno. 13 00:00:47,370 --> 00:00:51,110 Primjerice, samo prošle noći, citat Citat završen, iz jednog od osoblja 14 00:00:51,110 --> 00:00:55,000 Članovi: "Upravo sam imao studentsku kucanje na mojim vratima da biste snimili fotografiju sa mnom. 15 00:00:55,000 --> 00:00:59,020 Stalkers, kažem vam. "Započeli prilično opisno i onda smo se preselili 16 00:00:59,020 --> 00:01:02,830 na, sat vremena kasnije, "morao sam Student me čeka nakon sekciji 17 00:01:02,830 --> 00:01:06,080 i on je imao sve naše imenima i fotografijama na neke listove papira. "U redu. 18 00:01:06,080 --> 00:01:09,230 Dakle, organizirao, ali ne sve to jezivo još. 19 00:01:09,230 --> 00:01:12,520 >> Zatim, "bio sam izvan grada ovaj vikend, i kad sam se vratio, bio je jedan u 20 00:01:12,520 --> 00:01:12,630 moj 21 00:01:12,630 --> 00:01:16,740 spavaća soba. "[smijeh] 22 00:01:16,740 --> 00:01:20,410 DAVID Malan: Sljedeći citat je iz osoblja Član, "student došao u moju kuću, na 23 00:01:20,410 --> 00:01:25,330 Somerville u 4:00 jutros. "Sljedeća osoblja, "dobio sam u moj hotel u San 24 00:01:25,330 --> 00:01:30,016 Francisco i student je čekao ja u predvorju s tri DSLR. " 25 00:01:30,016 --> 00:01:31,510 Tip kamere. 26 00:01:31,510 --> 00:01:34,980 "Ja nisam ni na osoblje ovaj semestar, , ali učenik je provalio u moju kuću ovo 27 00:01:34,980 --> 00:01:40,480 ujutro i snimio cijelu stvar sa Google stakla. "I onda na kraju, 28 00:01:40,480 --> 00:01:43,650 "Najmanje 12 ljudi željno čeka na mene kad sam dobio iz moje 29 00:01:43,650 --> 00:01:44,800 limo, a onda se 30 00:01:44,800 --> 00:01:46,970 probudio. "U redu. 31 00:01:46,970 --> 00:01:57,690 Tako među fotografijama, kao što svibanj Podsjetimo, taj momak se ovdje, tko si 32 00:01:57,690 --> 00:02:01,850 Možda znate što Mila Banana, koji živi s Lauren Carvalho, naše glave 33 00:02:01,850 --> 00:02:02,905 demonstrator. 34 00:02:02,905 --> 00:02:05,170 Milo Milo, dođi ovamo dječaka. 35 00:02:05,170 --> 00:02:06,320 Milo. 36 00:02:06,320 --> 00:02:08,650 Milo. 37 00:02:08,650 --> 00:02:12,230 Da se podsjetimo, on je nosio Google Glass, tako mi ćemo vam pokazati sve to poslije. 38 00:02:12,230 --> 00:02:16,190 Dakle, ovo je Milo ako bi željeli fotografirati s njim nakon toga. 39 00:02:16,190 --> 00:02:18,240 Ako želite paziti na publiku tamo. 40 00:02:18,240 --> 00:02:19,430 OK. 41 00:02:19,430 --> 00:02:20,200 To je dobra snimka. 42 00:02:20,200 --> 00:02:22,556 Pa, Milo Banana. 43 00:02:22,556 --> 00:02:23,941 Oh, ne radite to. 44 00:02:23,941 --> 00:02:29,020 >> [Smijeh] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 Dakle, riječ onda o tome što je pred nama, jer kao što smo početi tranziciju, 47 00:02:34,550 --> 00:02:38,410 ovaj tjedan konkretno, iz C u naredbenog retka okruženje za PHP i 48 00:02:38,410 --> 00:02:42,720 JavaScript i SQL i HTML i CSS u web-based okruženju, mi ćemo biti u 49 00:02:42,720 --> 00:02:44,490 te opremanje sa svim više znanja za 50 00:02:44,490 --> 00:02:46,010 potencijalni konačne projekte. 51 00:02:46,010 --> 00:02:49,240 Prema tom cilju, kolegij ima tradicija održavanja seminara koji 52 00:02:49,240 --> 00:02:50,950 su na tangencijalno teme u tijeku. 53 00:02:50,950 --> 00:02:54,330 Jako puno se odnose na programiranje i na app razvoj i tako dalje, ali 54 00:02:54,330 --> 00:02:57,010 ne nužno istražiti tijek vlastiti nastavni plan i program. 55 00:02:57,010 --> 00:03:00,250 >> Dakle, ako ste možda zainteresirani za jedan ili više od ovogodišnjih seminara, 56 00:03:00,250 --> 00:03:02,530 Registrirajte se na cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Postoje stariji seminari na cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 I na određeno dosadašnjem za ovu godinu Nevjerojatne su Web Apps s Ruby na 59 00:03:10,620 --> 00:03:13,580 Tračnice, što je alternativa jezik za PHP. 60 00:03:13,580 --> 00:03:14,900 Računalno jezikoslovlje. 61 00:03:14,900 --> 00:03:18,710 Uvod u IOS, što je platforme koja se koristi za iPhone, a 62 00:03:18,710 --> 00:03:19,850 iPad razvoj. 63 00:03:19,850 --> 00:03:22,890 JavaScript za Web Apps, mi ćemo pokriti da, ali u ovom seminaru, vi ćete ići 64 00:03:22,890 --> 00:03:24,070 u više detalja. 65 00:03:24,070 --> 00:03:27,390 >> Leap Motion, tako da smo zapravo ćete imati neke od naših prijatelja iz Leap Motion, 66 00:03:27,390 --> 00:03:29,160 Sama tvrtka, pridružite nam se. 67 00:03:29,160 --> 00:03:31,800 Sutra, u stvari, pružiti kazaljka-na seminaru, ako 68 00:03:31,800 --> 00:03:33,320 od interesa za vas. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, alternativna tehnika za Ne koristite JavaScript u pregledniku 70 00:03:38,770 --> 00:03:39,970 ali na poslužitelju. 71 00:03:39,970 --> 00:03:42,110 Node.js, što je jako puno U tom smislu, kao dobro. 72 00:03:42,110 --> 00:03:43,650 Elegantan dizajn Android. 73 00:03:43,650 --> 00:03:46,990 Android se vrlo popularna alternativa za iOS i Windows Phone 74 00:03:46,990 --> 00:03:48,790 i druge mobilne platforme. 75 00:03:48,790 --> 00:03:51,180 I Web Security aktivnu obranu. 76 00:03:51,180 --> 00:03:54,590 >> Dakle, u stvari, ako želite da se uključe u to, neka mi 77 00:03:54,590 --> 00:03:55,840 zabilježite ovo. 78 00:03:55,840 --> 00:03:57,790 Mi smo jako sretni reći da našim prijateljima u Leap 79 00:03:57,790 --> 00:03:59,140 Gibanja, što je početak - 80 00:03:59,140 --> 00:04:01,300 ovaj uređaj zapravo samo došao od prije nekoliko mjeseci - 81 00:04:01,300 --> 00:04:05,960 je velikodušno donirao 30 takvih uređaja u klasi za što više studenata, ukoliko 82 00:04:05,960 --> 00:04:08,670 što bih posuditi hardvera prema semestra kraja i koristiti ga za 83 00:04:08,670 --> 00:04:10,390 Stvarni konačni projekt. 84 00:04:10,390 --> 00:04:11,890 Oni podržavaju brojne jezike. 85 00:04:11,890 --> 00:04:16,040 Nitko od njih C, nitko od njih nije PHP, tako da napraviti jedan ili više od tih seminara 86 00:04:16,040 --> 00:04:16,899 moglo pokazati interes. 87 00:04:16,899 --> 00:04:19,730 I svi će biti sniman u događaj koji niste u mogućnosti 88 00:04:19,730 --> 00:04:21,380 osobno prisustvovati. 89 00:04:21,380 --> 00:04:25,000 Raspored biti objavljen putem e kako smo se zgusnuo sobe. 90 00:04:25,000 --> 00:04:28,460 >> I na kraju, ako idete u projects.cs.50.net, ovo je web stranica 91 00:04:28,460 --> 00:04:31,450 Držimo da je svake godine pozivamo ljudi iz zajednice, fakulteta, 92 00:04:31,450 --> 00:04:36,420 odjela, osoblje, i oba u izvan CS50 na 93 00:04:36,420 --> 00:04:37,730 predlaže projektne ideje. 94 00:04:37,730 --> 00:04:39,050 Stvari od interesa za studentske grupe. 95 00:04:39,050 --> 00:04:40,600 Stvari od interesa za odjela. 96 00:04:40,600 --> 00:04:43,990 Dakle, ne pojaviti tamo, ako ste bore s nesigurnošću o tome što ste 97 00:04:43,990 --> 00:04:46,700 sebi bih se borila. 98 00:04:46,700 --> 00:04:51,760 >> Dakle, zadnji put smo uveli nedvojbeno složenije strukture podataka nego što bih 99 00:04:51,760 --> 00:04:53,300 vidio u posljednjih nekoliko tjedana. 100 00:04:53,300 --> 00:04:56,550 Mi bi bili pomoću polja lijepa sretno kao korisno ako 101 00:04:56,550 --> 00:04:58,160 jednostavna struktura podataka. 102 00:04:58,160 --> 00:05:00,570 Onda smo uveli to, što Naravno povezane liste. 103 00:05:00,570 --> 00:05:05,470 A što je bio jedan od motiva za uvođenjem ovog strukturu podataka? 104 00:05:05,470 --> 00:05:06,930 Da? 105 00:05:06,930 --> 00:05:07,250 Što je to? 106 00:05:07,250 --> 00:05:08,080 >> PUBLIKA: Dinamički Veličina. 107 00:05:08,080 --> 00:05:09,040 >> DAVID Malan: Dinamički Veličina. 108 00:05:09,040 --> 00:05:11,890 Dakle, dok je u polju, morate znate svoju veličinu prije kad 109 00:05:11,890 --> 00:05:12,740 što ga izdvojiti. 110 00:05:12,740 --> 00:05:14,380 U povezana popisu, ne znaš Morate znati da. 111 00:05:14,380 --> 00:05:17,610 Možete jednostavno malloc, ili općenitije, izdvojiti dodatna 112 00:05:17,610 --> 00:05:20,720 čvora, takoreći, svaki put kad želite umetnuti više podataka. 113 00:05:20,720 --> 00:05:22,670 I čvor nema unaprijed određenih značenja. 114 00:05:22,670 --> 00:05:25,580 To je samo generički pojam koji opisuje nekakav kontejner koji smo 115 00:05:25,580 --> 00:05:29,610 koriste u našem strukturu podataka za pohranu Neki predmet interesa, koji je u to 116 00:05:29,610 --> 00:05:31,750 Slučaj se dogoditi da se cijeli brojevi. 117 00:05:31,750 --> 00:05:33,160 >> No, tu je uvijek tradeoff. 118 00:05:33,160 --> 00:05:38,070 Tako smo dobili dinamičke veličine podataka struktura, ali ono što mi platiti cijenu? 119 00:05:38,070 --> 00:05:40,040 Što je downside povezane liste? 120 00:05:40,040 --> 00:05:41,006 Da? 121 00:05:41,006 --> 00:05:41,980 >> PUBLIKA: zahtijeva više memorije. 122 00:05:41,980 --> 00:05:44,240 >> DAVID Malan: To zahtijeva više memorije, kako točno? 123 00:05:44,240 --> 00:05:46,440 >> PUBLIKA: [nečujno]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID Malan: Točno. 125 00:05:47,050 --> 00:05:50,460 Dakle, sada smo pokazivače uzimam Dodatna memorija koje smo prethodno 126 00:05:50,460 --> 00:05:53,040 nije potrebno, jer je prednost od niza, naravno, da je 127 00:05:53,040 --> 00:05:54,860 sve što je granično, vratiti se natrag na leđa, što 128 00:05:54,860 --> 00:05:56,380 daje vam slučajni pristup. 129 00:05:56,380 --> 00:06:00,710 Jer samo pomoću uglata zagrada oznake, ili više tehnički pokazivač 130 00:06:00,710 --> 00:06:03,580 aritmetika, vrlo jednostavan dodatak, možete pristupiti bilo 131 00:06:03,580 --> 00:06:05,700 elementi u stalnom vrijeme. 132 00:06:05,700 --> 00:06:08,975 A u stvari, to je vrsta aludirati na još jedna cijena koju smo plaćati s 133 00:06:08,975 --> 00:06:09,760 povezani popis. 134 00:06:09,760 --> 00:06:13,890 >> Što se događa u trajanju od nešto poput pretraživanja, ako želim 135 00:06:13,890 --> 00:06:17,270 pronašli neke vrijednosti i iznutra povezanog popisa? 136 00:06:17,270 --> 00:06:20,290 Što znači moje trčanje vrijeme postali? 137 00:06:20,290 --> 00:06:21,560 Big O n. 138 00:06:21,560 --> 00:06:24,060 Ako je to riješeno u? 139 00:06:24,060 --> 00:06:25,440 Što ako struktura podataka je riješeno? 140 00:06:25,440 --> 00:06:28,640 Mogu li to učiniti bolje od big O n za traženje? 141 00:06:28,640 --> 00:06:31,700 Ne, jer u najgorem slučaju to bi moglo vrlo dobro biti riješeno, ali je broj 142 00:06:31,700 --> 00:06:32,950 tražiš moglo biti velika. 143 00:06:32,950 --> 00:06:35,370 To bi moglo biti broj 100, koji moglo se dogoditi da se sve 144 00:06:35,370 --> 00:06:36,410 je na kraju. 145 00:06:36,410 --> 00:06:39,950 I zato možete pristupiti jedino linked Popis u ovom provedbe od strane 146 00:06:39,950 --> 00:06:42,690 način svom prvom čvoru, ti si još uvijek vrsta od sreće. 147 00:06:42,690 --> 00:06:47,450 Morate proći cijelu stvar od prve do posljednje kako bi se pronašli 148 00:06:47,450 --> 00:06:49,150 da je velika vrijednost kao 100.. 149 00:06:49,150 --> 00:06:51,350 Ili kako bi se utvrdilo je li to Nije ni tamo. 150 00:06:51,350 --> 00:06:55,960 >> Dakle, ne možemo učiniti ono algoritma u podacima struktura koja izgleda ovako? 151 00:06:55,960 --> 00:06:59,460 Mi ne možemo učiniti binarna, jer binary search potrebna da smo imali 152 00:06:59,460 --> 00:07:00,740 s izravnim pristupom. 153 00:07:00,740 --> 00:07:04,500 Mi smo samo mogli skok od mjesta do Mjesto bez slijediti 154 00:07:04,500 --> 00:07:07,080 ove krušne mrvice u obliku od svih tih pokazivače. 155 00:07:07,080 --> 00:07:08,300 >> Sada, kako smo to provesti? 156 00:07:08,300 --> 00:07:12,830 Pa, ako ćemo ići na zaslonu ovdje, ako možemo brzo reimplement ove podatke 157 00:07:12,830 --> 00:07:13,440 Struktura - 158 00:07:13,440 --> 00:07:15,670 moj rukopis nije sve što je lijepo ovdje, ali pokušat ćemo. 159 00:07:15,670 --> 00:07:22,030 Dakle typedef rekonstruirati i što sam želite nazvati ovu stvar ovdje? 160 00:07:22,030 --> 00:07:22,960 Čvora. 161 00:07:22,960 --> 00:07:24,580 Tako ću počnemo. 162 00:07:24,580 --> 00:07:27,860 A sada, ono što treba da bude unutar struktura podataka za koje pojedinačno 163 00:07:27,860 --> 00:07:28,430 povezani popis? 164 00:07:28,430 --> 00:07:29,950 Koliko stavke? 165 00:07:29,950 --> 00:07:30,450 >> Dakle, dva. 166 00:07:30,450 --> 00:07:31,570 Jedan je prilično jednostavan. 167 00:07:31,570 --> 00:07:33,050 Dakle, int n. 168 00:07:33,050 --> 00:07:35,930 A mogli bismo nazvati n sve što želimo, ali to bi trebao biti int, ako smo 169 00:07:35,930 --> 00:07:37,660 provedbi povezane popis za Ints. 170 00:07:37,660 --> 00:07:41,920 A sada što se drugi Polje moraju biti? 171 00:07:41,920 --> 00:07:43,460 Struct čvor *. 172 00:07:43,460 --> 00:07:50,570 Dakle, ako mi je činiti struct čvor *, a onda sam mogu staviti i što god želim, 173 00:07:50,570 --> 00:07:53,510 ali samo da bude jasno da ću zvati Sljedeći je, kao što smo radili. 174 00:07:53,510 --> 00:07:55,270 A onda ću zatvorim vitičastim zagradama. 175 00:07:55,270 --> 00:08:00,700 >> I sada, kao i zadnji put, Stavio sam čvor ovdje. 176 00:08:00,700 --> 00:08:03,830 Ali ako sam izjavljujući kako je to čvora, zašto se uopće trudim se tako 177 00:08:03,830 --> 00:08:07,320 verbose ovdje u izjavi struct čvora * iduće, za razliku od 178 00:08:07,320 --> 00:08:09,210 na samo čvora * sljedeći? 179 00:08:09,210 --> 00:08:09,904 Da? 180 00:08:09,904 --> 00:08:12,810 >> PUBLIKA: [nečujno]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID Malan: Točno. 182 00:08:14,050 --> 00:08:14,530 Točno. 183 00:08:14,530 --> 00:08:18,320 Zbog C stvarno vam se doslovno i vidi samo definiciju čvora 184 00:08:18,320 --> 00:08:21,230 put ovdje, ne možete odnosi se na to ovdje. 185 00:08:21,230 --> 00:08:24,760 Dakle, imamo ovu vrstu preventivni Izjava ovdje, što je doduše 186 00:08:24,760 --> 00:08:25,390 mnogo opširnije. 187 00:08:25,390 --> 00:08:27,810 Struct čvor, to znači da sada možemo pristupiti 188 00:08:27,810 --> 00:08:29,760 unutar strukture podataka. 189 00:08:29,760 --> 00:08:33,370 >> I kao na stranu, jer je to postaje malo više subjektivna sada, 190 00:08:33,370 --> 00:08:36,230 star tehnički može ići ovdje, to može ići ovdje, to može 191 00:08:36,230 --> 00:08:37,179 čak i ići u sredini. 192 00:08:37,179 --> 00:08:39,890 Mi smo usvojili, u stilu vodič za Tečaj, Konvencija o stavljanju 193 00:08:39,890 --> 00:08:42,299 Zvijezda tik do podataka Vrsta, koja je u ovom slučaju, 194 00:08:42,299 --> 00:08:43,460 bi se rekonstruirati čvor. 195 00:08:43,460 --> 00:08:46,620 Ali shvatite u puno udžbenika i online reference, možda je doista 196 00:08:46,620 --> 00:08:48,450 vidjeti na drugoj strani. 197 00:08:48,450 --> 00:08:52,200 No, samo shvatiti da će oba zapravo rad i jednostavno bi trebao biti 198 00:08:52,200 --> 00:08:52,970 dosljedni. 199 00:08:52,970 --> 00:08:53,580 >> U redu. 200 00:08:53,580 --> 00:08:55,630 Dakle, to je bio naš izjava od struct čvor. 201 00:08:55,630 --> 00:08:59,430 Ali onda smo počeli raditi više sofisticirane stvari. 202 00:08:59,430 --> 00:09:03,410 Na primjer, odlučili smo uvesti nešto kao hash tablicu. 203 00:09:03,410 --> 00:09:08,160 Dakle, ovdje je hash tablicu veličine n, indeksirane od 0 na gornjem lijevom do n 204 00:09:08,160 --> 00:09:09,690 minus 1 na dnu lijevo. 205 00:09:09,690 --> 00:09:11,640 To bi mogao biti hash stol za ništa. 206 00:09:11,640 --> 00:09:15,340 No, ono što vrste stvari koje smo razgovarati o korištenju hash tablicu? 207 00:09:15,340 --> 00:09:18,370 Pohranjivanje što? 208 00:09:18,370 --> 00:09:18,800 >> Imena. 209 00:09:18,800 --> 00:09:20,870 Mogli bismo napraviti imena kao što su smo prošli put. 210 00:09:20,870 --> 00:09:22,200 I doista, možete pohraniti ništa. 211 00:09:22,200 --> 00:09:24,640 A mi ćemo to opet vidjeti u PHP i JavaScript. 212 00:09:24,640 --> 00:09:28,550 Hash tablica je lijepa vrsta Švicarski Vojska nož koji vam omogućuje pohranu 213 00:09:28,550 --> 00:09:33,690 skoro sve što želite unutar to pridružujući tipke s vrijednostima. 214 00:09:33,690 --> 00:09:34,770 Tipke sa vrijednostima. 215 00:09:34,770 --> 00:09:37,800 >> Sada u ovom jednostavnom slučaju, naš Tipke su samo brojevi. 216 00:09:37,800 --> 00:09:40,380 Mi smo provedbi hash Tablica kao polje. 217 00:09:40,380 --> 00:09:43,500 I tako su tipke 0, 1, 2, i tako dalje. 218 00:09:43,500 --> 00:09:47,200 I tako smo, kao ljudi, odlučio je prošlog tjedan da znate što, ako smo 219 00:09:47,200 --> 00:09:50,410 ide za pohranu imena, hajdemo proizvoljno, ali prilično razumno, 220 00:09:50,410 --> 00:09:54,680 Pretpostavljam da je Alice, ime, Samo će se indeksiraju u 0. 221 00:09:54,680 --> 00:09:58,030 I Bob, B ime, bit će indeksirana u 1, i tako dalje. 222 00:09:58,030 --> 00:10:02,490 Tako smo imali mapiranje između inputa, koji su nizovi i hash 223 00:10:02,490 --> 00:10:04,560 mjesta, koje su brojevi. 224 00:10:04,560 --> 00:10:07,740 >> Tako da je proces općenito je poznat kao hash funkcija, a možete istinski 225 00:10:07,740 --> 00:10:09,130 implementirati ga u kodu. 226 00:10:09,130 --> 00:10:12,080 Ako sam htjela provesti hash funkcije koji radi upravo ono što smo 227 00:10:12,080 --> 00:10:17,070 Upravo opisani na posljednji put, mogao bih proglasiti funkciju koja uzima, kao 228 00:10:17,070 --> 00:10:18,330 ulaz za primjer - 229 00:10:18,330 --> 00:10:22,190 i neka je to učiniti na ovaj Zaslon ovamo. 230 00:10:22,190 --> 00:10:26,180 Ako sam htjela provesti hash funkcija, mogao bih reći 231 00:10:26,180 --> 00:10:27,410 nešto poput ovoga. 232 00:10:27,410 --> 00:10:29,030 >> To će se vratiti int. 233 00:10:29,030 --> 00:10:33,600 To će se zvati mljeveno meso, i to je će prihvatiti kao argument u 234 00:10:33,600 --> 00:10:38,920 string, ili možemo biti pravilno sada, i reći char *, nazvat ćemo ga s. 235 00:10:38,920 --> 00:10:43,840 I onda sve to ima funkciju učiniti, u konačnici, je vratiti int. 236 00:10:43,840 --> 00:10:45,990 Sada, kako se to radi da bi mogli Nije se tako jasno. 237 00:10:45,990 --> 00:10:49,510 Ja ću provesti to bez bilo oblik kontrole pogrešaka upravo sada. 238 00:10:49,510 --> 00:10:55,740 Samo ću reći da se slijepo, vratite sve što je na konzoli s 0, minus, 239 00:10:55,740 --> 00:10:58,850 recimo, grad-zarezom. 240 00:10:58,850 --> 00:10:59,960 >> Totalno slomljena. 241 00:10:59,960 --> 00:11:02,620 To nije idealno, jer jedan, što ako je null? 242 00:11:02,620 --> 00:11:04,000 Loše stvari će se dogoditi. 243 00:11:04,000 --> 00:11:07,940 Dvije, što ako prvo slovo u ovom ime nije slovo? 244 00:11:07,940 --> 00:11:09,860 To se neće pretvoriti iz dobro bilo. 245 00:11:09,860 --> 00:11:11,970 To bi moglo biti malo slovo ili ne pismo na sve. 246 00:11:11,970 --> 00:11:15,520 Dakle, potpuno prostora za poboljšanje ovdje, ali to je osnovna ideja. 247 00:11:15,520 --> 00:11:19,010 >> Ono što smo prošlog tjedna opisao kao verbalno Upravo proces mapiranje Alice se 248 00:11:19,010 --> 00:11:23,360 0 Bob i do 1 može se izraziti sigurno više formulaically kao C 249 00:11:23,360 --> 00:11:24,320 funkcionirala. 250 00:11:24,320 --> 00:11:28,630 Nazvan ponovno hash, ima niz kao ulaza, a onda nekako čini nešto 251 00:11:28,630 --> 00:11:31,020 s tim input za proizvodnju izlaz. 252 00:11:31,020 --> 00:11:34,130 Nije za razliku od naše crne kutije opisa da smo dugo ste učinili. 253 00:11:34,130 --> 00:11:36,550 Ja ne znam kako bi to moglo biti rade ispod poklopca motora. 254 00:11:36,550 --> 00:11:40,120 >> Za problema set 6, jedan od izazova je za vas da odlučite što 255 00:11:40,120 --> 00:11:41,920 će vaš hash funkcija biti? 256 00:11:41,920 --> 00:11:45,760 Što se događa da se unutar tako crno box, i vjerojatno, to će biti 257 00:11:45,760 --> 00:11:50,380 malo zanimljivije od ove, i definitivno više skloni pogrešci 258 00:11:50,380 --> 00:11:53,180 ček od toga posebno Provedba. 259 00:11:53,180 --> 00:11:54,580 >> No, problemi mogu nastati, zar ne? 260 00:11:54,580 --> 00:11:57,760 Ako imamo strukturu podataka kao što je to jedan, što je jedan od problema 261 00:11:57,760 --> 00:12:01,600 možete izvoditi u tijekom vremena kao što ste umetnuli sve više i više imena u 262 00:12:01,600 --> 00:12:02,880 hash tablicu? 263 00:12:02,880 --> 00:12:04,630 Vi se sudari, zar ne? 264 00:12:04,630 --> 00:12:07,560 Što ako imate Alice i Arona, Dvije osobe čija imena se dogodilo 265 00:12:07,560 --> 00:12:08,190 za početak? 266 00:12:08,190 --> 00:12:11,660 To postavlja pitanje, gdje se staviti drugi takav naziv? 267 00:12:11,660 --> 00:12:15,050 >> Pa, što naivno možda samo ga stavi Bob kojoj pripada, ali onda je Branimir 268 00:12:15,050 --> 00:12:17,300 vrsta pijan ako pokušate ubacite svoje ime, a sljedeći 269 00:12:17,300 --> 00:12:18,240 nema mjesta za njega. 270 00:12:18,240 --> 00:12:21,400 Dakle, možda mu Boba gdje je Charlie, a možete zamisliti vrlo brzo 271 00:12:21,400 --> 00:12:23,020 devolving u malo nered. 272 00:12:23,020 --> 00:12:25,600 Nešto linearno na kraju, gdje se Samo morate tražiti cijelu stvar 273 00:12:25,600 --> 00:12:28,190 u potrazi za Alice ili Bob ili Aaron ili Charlie. 274 00:12:28,190 --> 00:12:33,230 >> Dakle, umjesto da smo predložili, umjesto da samo linearno sondiranje za otvorene prostore 275 00:12:33,230 --> 00:12:36,450 i plopping imena postoji, mi predložio ljubitelj pristup. 276 00:12:36,450 --> 00:12:41,740 Hash tablicu provodi još uvijek s Niz indeksa, ali Tip podataka 277 00:12:41,740 --> 00:12:44,500 ti indeksi sada su pokazivače. 278 00:12:44,500 --> 00:12:47,360 Kazaljke na što? 279 00:12:47,360 --> 00:12:48,730 Kazaljke na povezane liste. 280 00:12:48,730 --> 00:12:53,330 >> Budući da je opoziv vezan popis zapravo samo pointer na čvoru, a 281 00:12:53,330 --> 00:12:57,110 čvor ima sljedeće polje i na taj čvor ima sljedeći polje, i tako dalje. 282 00:12:57,110 --> 00:13:00,690 Dakle, sada možete misliti na ovom polju lijeva strana od hash tablicu kao i 283 00:13:00,690 --> 00:13:01,820 što dovodi do povezane popisa. 284 00:13:01,820 --> 00:13:07,000 Prednost što je, ako dobijete sudara između Alice i Arona, 285 00:13:07,000 --> 00:13:09,300 Što ćete učiniti s Druga takva osoba? 286 00:13:09,300 --> 00:13:14,150 Vi samo ga spojiti ili joj na kraju, ili čak početak 287 00:13:14,150 --> 00:13:15,490 te povezane liste. 288 00:13:15,490 --> 00:13:17,340 >> I doista, neka je samo kroz rezance da je samo na sekundu. 289 00:13:17,340 --> 00:13:18,640 Gdje bi najviše smisla? 290 00:13:18,640 --> 00:13:22,060 Ako ubacim Alice i ona završi u prvo mjesto, onda ću pokušati 291 00:13:22,060 --> 00:13:25,310 umetnite Aronov ime, a tu je Očito sudara, trebao sam staviti 292 00:13:25,310 --> 00:13:27,400 ga je na početku vezanog popisu? 293 00:13:27,400 --> 00:13:30,944 To je u tom prvom mjestu, ili na kraju? 294 00:13:30,944 --> 00:13:31,440 >> PUBLIKA: [nečujno]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID Malan: OK. 296 00:13:31,990 --> 00:13:32,490 Čuo sam počinjao. 297 00:13:32,490 --> 00:13:33,903 Zašto na početku? 298 00:13:33,903 --> 00:13:34,750 >> PUBLIKA: [nečujno]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID Malan: OK. 300 00:13:34,940 --> 00:13:36,520 To je po abecedi, tako da je lijepo. 301 00:13:36,520 --> 00:13:37,330 To je dobro svojstvo. 302 00:13:37,330 --> 00:13:39,335 To će uštedjeti me neko vrijeme potencijalno. 303 00:13:39,335 --> 00:13:43,290 Neće mi dopustiti binarna, ali ja možda barem biti u mogućnosti to break out 304 00:13:43,290 --> 00:13:47,340 od petlje ako shvaćam, dobro, ja sam smjer Posljednjih su Aron bi se u ovo 305 00:13:47,340 --> 00:13:48,310 razvrstani povezanu popis. 306 00:13:48,310 --> 00:13:50,360 Ja ne moram gubiti svoje vrijeme u potrazi sve do kraja. 307 00:13:50,360 --> 00:13:51,530 Dakle, to je razumno. 308 00:13:51,530 --> 00:13:54,710 Zašto bi inače možda želite umetnuti sudaraju ime po 309 00:13:54,710 --> 00:13:56,660 počevši od popisa? 310 00:13:56,660 --> 00:13:57,397 Što je to? 311 00:13:57,397 --> 00:13:58,680 >> PUBLIKA: [nečujno]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID Malan: To bi moglo potrajati dugo vremena da bi se na kraju popisa. 313 00:14:00,820 --> 00:14:02,490 A u stvari, sve dulje i dulje. 314 00:14:02,490 --> 00:14:04,920 Što više imena ulažete kako početi s, više ne da 315 00:14:04,920 --> 00:14:06,280 Lanac će doći. 316 00:14:06,280 --> 00:14:07,890 Duže da povezana Popis će doći. 317 00:14:07,890 --> 00:14:09,420 Pa ti si zapravo samo troši svoje vrijeme. 318 00:14:09,420 --> 00:14:14,070 Možda ste bolji od održavanju konstantna umetanja vrijeme, big O od 1, 319 00:14:14,070 --> 00:14:18,470 strane uvijek stavljajući u sudaru na ime početak povezanoj popisu 320 00:14:18,470 --> 00:14:21,230 a ne brinući se koliko o razvrstavanje. 321 00:14:21,230 --> 00:14:22,600 >> Koji je najbolji odgovor? 322 00:14:22,600 --> 00:14:23,320 To je nejasno. 323 00:14:23,320 --> 00:14:26,140 To je vrsta ovisi o tome što distribucija, ono što je obrazac 324 00:14:26,140 --> 00:14:27,850 od imena što su umetanja. 325 00:14:27,850 --> 00:14:29,430 To nije nužno Očigledan odgovor. 326 00:14:29,430 --> 00:14:33,100 No, ovdje se, opet, Dizajn priliku. 327 00:14:33,100 --> 00:14:37,220 >> Pa smo zatim pogleda na tu stvar, koja stvarno druga velika prilika 328 00:14:37,220 --> 00:14:38,180 za p-set 6. 329 00:14:38,180 --> 00:14:41,770 I shvatite, ako već niste, Zamyla uranja u obje ove, hash 330 00:14:41,770 --> 00:14:43,260 Stolovi i napad, u više detalja. 331 00:14:43,260 --> 00:14:45,630 I videoupute je ugrađen u p-set spec.. 332 00:14:45,630 --> 00:14:46,590 Ovo je trie - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. I ono što je zanimljivo kod to je da se trajanje 334 00:14:51,670 --> 00:14:59,510 u potrazi za ime, kao što je Maxwell zadnji put, bio je veliki O čega? 335 00:14:59,510 --> 00:15:01,040 Što je to? 336 00:15:01,040 --> 00:15:01,920 >> PUBLIKA: broj pisama. 337 00:15:01,920 --> 00:15:02,550 >> DAVID Malan: Broj slova. 338 00:15:02,550 --> 00:15:03,210 Čuo sam dvije stvari. 339 00:15:03,210 --> 00:15:04,630 Broj pisama i stalne vrijeme. 340 00:15:04,630 --> 00:15:05,540 Dakle, idemo s tim prvi put. 341 00:15:05,540 --> 00:15:06,410 Broj pisama. 342 00:15:06,410 --> 00:15:10,195 Pa, ova struktura podataka, podsjetimo, je poput stabla, obiteljsko stablo, svaki od 343 00:15:10,195 --> 00:15:12,860 čiji čvorovi su sastavljene od polja. 344 00:15:12,860 --> 00:15:16,300 I oni su nizovi pokazivači ostali takvi čvorovi, ili druge kao što 345 00:15:16,300 --> 00:15:17,670 nizovi u stablo. 346 00:15:17,670 --> 00:15:22,890 >> Dakle, ako smo htjeli onda odrediti Maxwell je li ovdje, mogao bih otići 347 00:15:22,890 --> 00:15:26,890 u prvi niz, na samom vrhu stabla, tzv korijena, vrh 348 00:15:26,890 --> 00:15:30,521 trie, a zatim će slijediti pokazivač m, zatim pokazivač, a zatim x, 349 00:15:30,521 --> 00:15:31,710 w, e, l, l. 350 00:15:31,710 --> 00:15:34,910 I onda kad vidim neki posebni simbol, označava se kao trokut. 351 00:15:34,910 --> 00:15:38,480 U kodu vidjet ćete predlažemo da implementiran kao bool, samo kaže da 352 00:15:38,480 --> 00:15:40,540 ili ne, riječ prestaje ovdje. 353 00:15:40,540 --> 00:15:45,270 >> Pa, kad smo otišli na M-A-X-W-E-L-L, osjeća kao sedam, možda 354 00:15:45,270 --> 00:15:48,910 osam ako idemo jedan mimo njega osam koraka kako pronaći Maxwell. 355 00:15:48,910 --> 00:15:53,050 Ili nazovimo ga K. Ali sjećam posljednja Tada sam tvrdio da, ako postoji 356 00:15:53,050 --> 00:15:57,540 realno Maksimalna duljina na Riječ, kao što je 40-neke-ak likova, 357 00:15:57,540 --> 00:16:00,810 Maksimalna duljina podrazumijeva konstantna vrijednost. 358 00:16:00,810 --> 00:16:05,770 Pa stvarno, da, to je veliki tehnički O od 8 ili 7, odnosno uistinu velikom izlaznom K. But 359 00:16:05,770 --> 00:16:09,420 ako postoji konačna kapu na ono što K može biti, to je konstanta. 360 00:16:09,420 --> 00:16:12,080 I to je velika O od 1 na kraju dana. 361 00:16:12,080 --> 00:16:13,040 >> Nije u stvarnom svijetu. 362 00:16:13,040 --> 00:16:15,960 Ne kada zapravo početi gledati vaš sat kao svoga programa trčanja. 363 00:16:15,960 --> 00:16:20,690 To apsolutno će biti malo sporije nego što doista konstantna 364 00:16:20,690 --> 00:16:21,840 vrijeme s jednim korakom. 365 00:16:21,840 --> 00:16:25,540 To će biti sedam ili osam koraka, ali još uvijek je to puno, puno bolje 366 00:16:25,540 --> 00:16:30,080 od algoritma poput velikog O n te ovisi o veličini ono što je u 367 00:16:30,080 --> 00:16:31,220 struktura podataka. 368 00:16:31,220 --> 00:16:34,970 >> Obavijest upside ovdje možemo ubaciti milijun više imena u to 369 00:16:34,970 --> 00:16:38,170 struktura podataka, no koliko još koraka je li će nas odvesti pronaći 370 00:16:38,170 --> 00:16:40,480 Maxwell je u tom slučaju? 371 00:16:40,480 --> 00:16:40,780 Nitko. 372 00:16:40,780 --> 00:16:41,820 On je nepromijenjen. 373 00:16:41,820 --> 00:16:45,480 I do sada, ja ne mislim da smo vidjeli Primjer podataka strukture ili 374 00:16:45,480 --> 00:16:48,560 algoritam koji je bio kompletno nepromijenjen prema vanjskim 375 00:16:48,560 --> 00:16:50,040 ponašanja kao što je to. 376 00:16:50,040 --> 00:16:51,160 No, to ne može biti nevjerojatna. 377 00:16:51,160 --> 00:16:52,900 To ne može biti jedino rješenje za p-set 378 00:16:52,900 --> 00:16:53,570 >> I to nije. 379 00:16:53,570 --> 00:16:55,980 To nije nužno podatke Struktura trebali težiti ka, 380 00:16:55,980 --> 00:16:58,220 jer kao što je hash tablica, tradeoff. 381 00:16:58,220 --> 00:17:00,500 Koja je cijena koju plaćaju ovdje? 382 00:17:00,500 --> 00:17:00,940 Memorije. 383 00:17:00,940 --> 00:17:02,890 Mislim, ovo je grozno količinu memorije. 384 00:17:02,890 --> 00:17:05,569 I ne mogu sasvim ga vidjeti ovdje, jer Autor ove slike 385 00:17:05,569 --> 00:17:09,420 očito odrezan sve polja, i mi ne vidimo puno ih i 386 00:17:09,420 --> 00:17:12,700 B-a i C-ih i Qa i Y-a i Z-ih u tim polja. 387 00:17:12,700 --> 00:17:13,630 No, oni su tu. 388 00:17:13,630 --> 00:17:17,660 >> Svaka od tih čvorova je cijeli niz nekih 26 ili više bajtova, svaki od 389 00:17:17,660 --> 00:17:19,170 što predstavlja pismo. 390 00:17:19,170 --> 00:17:22,920 27 u našem slučaju, tako da možemo podržati apostrofe u setu problema. 391 00:17:22,920 --> 00:17:27,030 Dakle, ovo je stvarno struktura podataka, jako gusta i široka. 392 00:17:27,030 --> 00:17:30,880 I to samo može završiti usporavanje stvari dolje, ili barem da košta 393 00:17:30,880 --> 00:17:32,240 puno više prostora. 394 00:17:32,240 --> 00:17:34,020 Ali opet, možemo izvući Usporedbe ovdje. 395 00:17:34,020 --> 00:17:39,190 >> Podsjetimo, a leđa, postigli smo mnogo više uzbudljivo vrijeme rada u rješavanju 396 00:17:39,190 --> 00:17:42,880 kada koristimo spajanje vrsta, ali cijena platili smo za postizanje n log n za spajanje 397 00:17:42,880 --> 00:17:46,930 sortiranje zahtijeva da trošimo više što je resurs? 398 00:17:46,930 --> 00:17:47,690 Više prostora. 399 00:17:47,690 --> 00:17:50,530 Trebali smo srednju polje za kopirati ljudi u, baš kao i 400 00:17:50,530 --> 00:17:51,620 jesmo ovdje na pozornici. 401 00:17:51,620 --> 00:17:55,880 Pa opet, nema jasnih pobjednika, ali samo subjektivni design 402 00:17:55,880 --> 00:17:57,710 odluke donose. 403 00:17:57,710 --> 00:17:58,060 >> U redu. 404 00:17:58,060 --> 00:17:59,130 Pa kako o tome? 405 00:17:59,130 --> 00:18:02,050 Svatko prepoznaje koji D-Hall? 406 00:18:02,050 --> 00:18:02,440 OK. 407 00:18:02,440 --> 00:18:03,170 Dakle, tri od nas učiniti. 408 00:18:03,170 --> 00:18:03,750 Mather House. 409 00:18:03,750 --> 00:18:05,070 Dakle, ovo je za Mather je blagovanje. 410 00:18:05,070 --> 00:18:09,650 Kladim se da svi imaju blagovaonice hrpe ladicama ovako. 411 00:18:09,650 --> 00:18:11,950 A to je zapravo prikazuje nečega što smo 412 00:18:11,950 --> 00:18:13,050 Očito već vidjeli. 413 00:18:13,050 --> 00:18:14,850 Mi ga zove doslovno hrpu. 414 00:18:14,850 --> 00:18:18,970 I stog, u smislu svoje memorije računala, gdje podaci ide 415 00:18:18,970 --> 00:18:20,460 dok je funkcija se zove. 416 00:18:20,460 --> 00:18:23,410 >> Na primjer, ono što vrste stvari idu na stog u odnosu na 417 00:18:23,410 --> 00:18:27,420 Raspored memorije smo razgovarali u posljednjih nekoliko tjedana? 418 00:18:27,420 --> 00:18:28,736 Što je to? 419 00:18:28,736 --> 00:18:29,670 >> PUBLIKA: Pozivi na funkcijama. 420 00:18:29,670 --> 00:18:30,260 >> DAVID Malan: Žao mi je. 421 00:18:30,260 --> 00:18:31,210 >> PUBLIKA: Pozivi na funkcijama. 422 00:18:31,210 --> 00:18:33,590 >> DAVID Malan: Pozivi na funkcijama, ali Naime, ono što je unutar svake od 423 00:18:33,590 --> 00:18:35,340 ti okviri? 424 00:18:35,340 --> 00:18:37,220 Koje vrste stvari? 425 00:18:37,220 --> 00:18:37,460 Da. 426 00:18:37,460 --> 00:18:38,500 Dakle lokalnim varijablama. 427 00:18:38,500 --> 00:18:43,080 Bilo mi je potrebno neko lokalnu pohranu, kao argument, ili sam int, int ili 428 00:18:43,080 --> 00:18:45,940 temp, ili što god lokalnim varijabla, mi smo bili 429 00:18:45,940 --> 00:18:47,210 stavljanjem na stog. 430 00:18:47,210 --> 00:18:49,610 I mi to zovemo, jer stog tog raslojavanje ideje. 431 00:18:49,610 --> 00:18:52,940 Samo vrsta utakmice sa stvarnošću, Koncept tome. 432 00:18:52,940 --> 00:18:56,650 >> No, ispostavilo se da je snop također mogu se vidjeti kao strukture podataka, 433 00:18:56,650 --> 00:19:00,110 alternativa niz, alternativna povezanog popisa. 434 00:19:00,110 --> 00:19:02,770 Nešto konceptualno zanimljiviji da još uvijek može biti 435 00:19:02,770 --> 00:19:06,030 provodi ili pomoću onih stvari, ali to je drugačiji tip 436 00:19:06,030 --> 00:19:09,140 struktura podataka podržava, uistinu, samo dvije operacije. 437 00:19:09,140 --> 00:19:11,000 No, možete dodati na fancier obilježja od tih. 438 00:19:11,000 --> 00:19:12,180 No, to su osnove - 439 00:19:12,180 --> 00:19:13,510 push i pop. 440 00:19:13,510 --> 00:19:19,240 >> A ideja s hrpom je da ako sam ima ovdje, sa ili bez uzivo 441 00:19:19,240 --> 00:19:22,880 znajući, pladanj iz susjedstva s brojem 9 na njemu. 442 00:19:22,880 --> 00:19:23,870 Dakle, samo int. 443 00:19:23,870 --> 00:19:26,990 I želim gurnuti ovo na podacima struktura, koja trenutno je prazna. 444 00:19:26,990 --> 00:19:28,790 Razmotrite ovo dno stoga. 445 00:19:28,790 --> 00:19:33,150 Ja bi gurnuti taj broj 9 na stog, a sada je tamo. 446 00:19:33,150 --> 00:19:36,040 >> Ali zanimljiva stvar o hrpi je da ako ja sada želim gurati 447 00:19:36,040 --> 00:19:40,210 neke druge vrijednosti, kao što su 17, a ja sam gurati ovo na stog, ja ću učiniti 448 00:19:40,210 --> 00:19:43,290 Samo intuitivno stvar, samo ću Da bi se to upravo tamo gdje mi ljudi 449 00:19:43,290 --> 00:19:45,180 će biti skloni da ga stavite na vrh. 450 00:19:45,180 --> 00:19:48,850 No, ono što je zanimljivo sada je, kako mogu dobiti na 9? 451 00:19:48,850 --> 00:19:50,670 Znate, ja to ne bez nekog napora. 452 00:19:50,670 --> 00:19:54,070 >> Dakle, ono što je zanimljivo kod stog je da je po dizajnu, 453 00:19:54,070 --> 00:19:56,330 to je struktura LIFO podataka. 454 00:19:56,330 --> 00:19:59,680 Glup način opisuje posljednja u, prvi van. 455 00:19:59,680 --> 00:20:03,280 Dakle, zadnji broj u u to vrijeme imao 17 godina. 456 00:20:03,280 --> 00:20:07,540 Dakle, ako želim nešto pop off iz dimnjaka, to može biti samo 17. 457 00:20:07,540 --> 00:20:11,890 Dakle, postoji obvezni redoslijed operacija ovdje, gdje je zadnja stavka 458 00:20:11,890 --> 00:20:14,260 u mora biti prvi van. 459 00:20:14,260 --> 00:20:16,440 Dakle akronim, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Pa zašto bi to bilo korisno? 461 00:20:19,160 --> 00:20:22,690 Jesu li njihove situacije u kojima bih Želite strukturu podataka kao što je ovaj? 462 00:20:22,690 --> 00:20:24,810 Pa, sigurno je bio koristan unutar računala. 463 00:20:24,810 --> 00:20:29,050 Dakle, operativni sustavi očito koristite ovu vrsta podataka strukture za dimnjake. 464 00:20:29,050 --> 00:20:32,800 Također ćemo vidjeti istu ideju kada je u pitanju web stranica. 465 00:20:32,800 --> 00:20:35,890 Dakle, ovaj tjedan i sljedeći tjedan i izvan nje, i kao što ste početi provoditi weba 466 00:20:35,890 --> 00:20:39,490 stranice u jeziku zove HTML, možete zapravo koristiti podatkovnu strukturu kao 467 00:20:39,490 --> 00:20:42,690 ovo bi se utvrdilo je li stranica pravilno formatiran. 468 00:20:42,690 --> 00:20:47,170 Budući da ćemo vidjeti sve web stranice pratite vrst hijerarhije, udubljenje 469 00:20:47,170 --> 00:20:52,030 da će se, na kraju dana, se Stablo struktura ispod haube. 470 00:20:52,030 --> 00:20:53,620 Dakle, više o tome u samo malo. 471 00:20:53,620 --> 00:20:56,560 >> Ali za sada, neka je predloži za Trenutak, kako bismo mogli ići o 472 00:20:56,560 --> 00:20:58,830 predstavlja ono što je stog? 473 00:20:58,830 --> 00:21:03,370 Dopustite mi predložiti da realiziramo stog s kodom kao što je ovaj. 474 00:21:03,370 --> 00:21:07,990 Dakle, stog će imati unutar nje dvije stvari, Array, nazivaju pladnjevi, 475 00:21:07,990 --> 00:21:09,510 Samo treba biti u skladu s demo. 476 00:21:09,510 --> 00:21:12,660 A svaki od stavke u tom polju će biti tipa int. 477 00:21:12,660 --> 00:21:14,740 A kapacitet je valjda ono? 478 00:21:14,740 --> 00:21:18,796 Budući da sam nije zapisano puna definicija ovdje. 479 00:21:18,796 --> 00:21:21,535 >> To je vjerojatno najveća Veličina polja. 480 00:21:21,535 --> 00:21:25,150 I to je vjerojatno proglašen oštra definirati na vrhu datoteke, neki 481 00:21:25,150 --> 00:21:28,450 vrsta konstante kao implicira Sama kapitalizacije. 482 00:21:28,450 --> 00:21:32,250 Dakle, negdje kapacitet definira kao najveću moguću veličinu. 483 00:21:32,250 --> 00:21:35,590 U međuvremenu, unutar strukture podataka poznat kao stog postoji volja 484 00:21:35,590 --> 00:21:38,630 biti cijeli samo poznat jednostavno kao veličinu. 485 00:21:38,630 --> 00:21:43,400 >> Dakle, ako mi je ovo sada predstavljaju slikovito, pretpostavimo da je to 486 00:21:43,400 --> 00:21:48,070 Cijeli crna kutija predstavlja moju hrpu. 487 00:21:48,070 --> 00:21:50,070 Unutar nje je dvije varijable. 488 00:21:50,070 --> 00:21:54,780 Tako ću se izvući Prvi su veličine. 489 00:21:54,780 --> 00:21:57,420 I drugi ću crtati kao polje. 490 00:21:57,420 --> 00:22:01,060 >> No, samo da bi stvari uredno, normalno ja bi privući niz poput 491 00:22:01,060 --> 00:22:04,910 to, ali to je vrsta lijepo ako mi odgovarati stvarnosti, ili 492 00:22:04,910 --> 00:22:06,230 odgovarati mentalni model. 493 00:22:06,230 --> 00:22:12,880 Pa neka mi umjesto nacrtati niz vertikalno, što je samo, opet, 494 00:22:12,880 --> 00:22:13,840 umjetničko tumačenje. 495 00:22:13,840 --> 00:22:16,610 Da li stvarno ne smeta što se ispod poklopca motora. 496 00:22:16,610 --> 00:22:20,350 A mi ćemo reći da je, po defaultu, Kapacitet će biti tri. 497 00:22:20,350 --> 00:22:23,480 Dakle, ovo će biti location 0, ovo će biti mjesto 1, ova 498 00:22:23,480 --> 00:22:25,740 će se 2. Mjesto. 499 00:22:25,740 --> 00:22:29,330 >> Ako sam podmititi sa stresom loptu, bi netko kao da se i pokrenite 500 00:22:29,330 --> 00:22:30,870 ukrcaju ovdje samo na trenutak? 501 00:22:30,870 --> 00:22:31,960 OK, vidjela tvoja ruka prvi. 502 00:22:31,960 --> 00:22:33,950 Dođi gore. 503 00:22:33,950 --> 00:22:36,500 U redu. 504 00:22:36,500 --> 00:22:38,760 Dakle, ja vjerujem da je Steven. 505 00:22:38,760 --> 00:22:40,035 Dođi gore. 506 00:22:40,035 --> 00:22:40,770 U redu. 507 00:22:40,770 --> 00:22:46,760 >> Ali sada pretpostavimo da premotati na početno stanje svijeta u kojem sam 508 00:22:46,760 --> 00:22:52,180 Samo su proglasili hrpu, a to je će biti kapaciteta tri. 509 00:22:52,180 --> 00:22:54,470 No, veličina još nije utvrđena. 510 00:22:54,470 --> 00:22:56,100 Posude još nije utvrđena. 511 00:22:56,100 --> 00:22:57,300 Dakle, nekoliko pitanja na prvom mjestu. 512 00:22:57,300 --> 00:23:01,310 I neka mi vam mikrofon tako da možete aktivnije sudjelovati u tome. 513 00:23:01,310 --> 00:23:05,190 >> Dakle, ono što je unutar veličine u ovom trenutku u vremenu ako sve sam učinio je 514 00:23:05,190 --> 00:23:09,340 proglašen stog s jedna linija koda? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: Ne mnogo. 516 00:23:10,100 --> 00:23:12,080 >> DAVID Malan: OK, nije puno. 517 00:23:12,080 --> 00:23:14,410 Znamo li što je unutar dimenzija, Ne znamo što je unutra 518 00:23:14,410 --> 00:23:16,330 ovog polja ovdje? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Samo slučajni broj, zar ne? 520 00:23:18,630 --> 00:23:20,220 Samo - 521 00:23:20,220 --> 00:23:23,230 >> DAVID Malan: Da, idem nazvati broj, ali slučajni - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Stvari. 523 00:23:23,820 --> 00:23:28,290 >> DAVID Malan: Stvari kao slučajna 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: Bits. 525 00:23:28,870 --> 00:23:29,530 >> DAVID Malan: Bits, zar ne? 526 00:23:29,530 --> 00:23:31,190 Dakle smeće vrijednosti, zar ne? 527 00:23:31,190 --> 00:23:33,470 Dakle permutacije od 0-a i 1-a. 528 00:23:33,470 --> 00:23:35,920 Ostaci prethodne uzance ove memorije. 529 00:23:35,920 --> 00:23:38,150 I mi zapravo ne znaju što su vrijednosti su, pa smo obično ih privući 530 00:23:38,150 --> 00:23:38,930 kao upitnicima. 531 00:23:38,930 --> 00:23:41,990 >> Dakle, prva stvar koju smo valjda će se želite učiniti ovdje - 532 00:23:41,990 --> 00:23:46,630 i neka mi daju ovo polje unutar odatle naziv - ladice. 533 00:23:46,630 --> 00:23:49,540 Što bi mi vjerojatno započeti Veličina se, ako želimo 534 00:23:49,540 --> 00:23:51,040 početi koristiti ovu hrpu? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Ladica je pod 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID Malan: Pa, OK. 537 00:23:53,910 --> 00:23:56,710 Da bude jasno, kapaciteti se proglasio drugdje tri. 538 00:23:56,710 --> 00:23:58,570 I to je ono što sam koristiti kako bi se alocirao niz. 539 00:23:58,570 --> 00:24:03,535 Veličina se događa da se odnosi na koliko je ladice su trenutno na stog. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Zero. 541 00:24:03,880 --> 00:24:04,460 >> DAVID Malan: Pa to bi trebalo biti nula. 542 00:24:04,460 --> 00:24:07,760 Dakle, ići naprijed, i sa bilo prstom, povući nulu u veličini. 543 00:24:07,760 --> 00:24:08,440 U redu. 544 00:24:08,440 --> 00:24:10,920 Tako sada, što je unutar ove ovdje, mi ne znamo. 545 00:24:10,920 --> 00:24:12,160 To su zapravo samo smeće vrijednosti. 546 00:24:12,160 --> 00:24:14,800 Tako smo mogli izvući upitnike, ali neka je zadržati odbora za sada čisto 547 00:24:14,800 --> 00:24:16,300 jer to nije važno što je tamo. 548 00:24:16,300 --> 00:24:19,130 Ne trebamo li pokrenuti niz na bilo što, jer ako znamo da je 549 00:24:19,130 --> 00:24:23,100 veličina stog je nula, pa, Ne treba se gleda bilo što u 550 00:24:23,100 --> 00:24:25,590 Taj niz svejedno, na ove točke u vremenu. 551 00:24:25,590 --> 00:24:29,970 >> Dakle, pretpostavimo da sada sam gurati broj 9 na stog. 552 00:24:29,970 --> 00:24:33,750 Kako bismo trebali ažurirati strukturu podataka unutar ove crne kutije? 553 00:24:33,750 --> 00:24:35,540 Koje vrijednosti treba promijeniti? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: U - 555 00:24:36,200 --> 00:24:37,400 Veličina? 556 00:24:37,400 --> 00:24:37,650 >> DAVID Malan: OK. 557 00:24:37,650 --> 00:24:38,770 Veličina trebao postati ono? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Veličina bi biti jedan. 559 00:24:39,580 --> 00:24:39,870 >> DAVID Malan: OK. 560 00:24:39,870 --> 00:24:41,110 Dakle, veličina trebala bi postati jedan. 561 00:24:41,110 --> 00:24:42,540 Dakle, možete to učiniti na nekoliko načina. 562 00:24:42,540 --> 00:24:46,920 Dopustite mi da vam dati, sada vaša Prst je gumica. 563 00:24:46,920 --> 00:24:47,260 U redu. 564 00:24:47,260 --> 00:24:49,960 Tada je sada prst je četkica. 565 00:24:49,960 --> 00:24:50,330 U redu. 566 00:24:50,330 --> 00:24:52,820 I sad ono što drugi ne mora mijenjati, Očito, u strukturi podataka? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Idemo na dna do 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID Malan: 9. 569 00:24:57,760 --> 00:24:58,420 OK, dobro. 570 00:24:58,420 --> 00:25:01,550 Dakle, još uvijek ne smeta što je na Mjesto na jedan ili dva, jer oni su 571 00:25:01,550 --> 00:25:04,520 Kante vrijednosti, ali mi ne bi trebali zamarati upravo tamo, jer je veličina 572 00:25:04,520 --> 00:25:07,540 nam govori da je samo prvi element je zapravo legitimna. 573 00:25:07,540 --> 00:25:10,400 Dakle, sada sam gurati 17 na popisu. 574 00:25:10,400 --> 00:25:11,830 Što se događa s ovom slikom? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: Dakle, veličina će ići u dva. 576 00:25:14,720 --> 00:25:15,300 >> DAVID Malan: OK. 577 00:25:15,300 --> 00:25:16,070 Ti si gumicu - 578 00:25:16,070 --> 00:25:16,810 Ups. 579 00:25:16,810 --> 00:25:18,026 Ti si gumicu. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Eraser. 581 00:25:18,840 --> 00:25:19,720 >> DAVID Malan: Ti si četkica. 582 00:25:19,720 --> 00:25:20,560 >> STEVEN: Četka. 583 00:25:20,560 --> 00:25:20,920 >> DAVID Malan: OK. 584 00:25:20,920 --> 00:25:21,600 A što drugo? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: I onda mi - 586 00:25:22,600 --> 00:25:22,915 >> DAVID Malan: Mi gurnula 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Držimo 17 na vrhu, tako da - 588 00:25:24,760 --> 00:25:25,710 >> DAVID Malan: OK, dobro. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN: - to pasti. 590 00:25:27,040 --> 00:25:27,530 >> DAVID Malan: U redu. 591 00:25:27,530 --> 00:25:27,940 To je sve lako. 592 00:25:27,940 --> 00:25:29,300 Neću vam pomoći da ovaj put. 593 00:25:29,300 --> 00:25:30,510 Push 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Done. 595 00:25:31,720 --> 00:25:34,870 Postati gumicu. 596 00:25:34,870 --> 00:25:37,340 Ja sam sve četke. 597 00:25:37,340 --> 00:25:39,340 A onda sam stavljajući 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID Malan: 22. 599 00:25:40,100 --> 00:25:40,620 Izvrsno. 600 00:25:40,620 --> 00:25:41,380 Dakle, još jednom. 601 00:25:41,380 --> 00:25:44,280 Ja sad idem na guranje na stog 26. 602 00:25:44,280 --> 00:25:46,350 >> STEVEN: Ooh. 603 00:25:46,350 --> 00:25:50,278 Oh Bože. 604 00:25:50,278 --> 00:25:52,520 Stvarno mi je uhvaćen off straže. 605 00:25:52,520 --> 00:25:53,703 >> DAVID Malan: Nije ti vidjeti ovaj dolazak? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: Nisam vidio ovaj dolazak. 607 00:25:55,930 --> 00:25:58,756 Možemo ponovno Početni kapacitet? 608 00:25:58,756 --> 00:25:59,790 >> DAVID Malan: To je dobro pitanje. 609 00:25:59,790 --> 00:26:02,360 Tako smo vrsta sebe naslikao u kutu ovdje. 610 00:26:02,360 --> 00:26:06,740 Zapravo ne postoji dobra strana za Stjepana jer smo dodijeljen ovaj niz 611 00:26:06,740 --> 00:26:09,130 statički, da se tako izrazim, unutar strukture podataka. 612 00:26:09,130 --> 00:26:12,170 I mi smo u biti teško kodirano da bude od veličine tri. 613 00:26:12,170 --> 00:26:14,170 Dakle, ne možemo ga preraspodijeliti. 614 00:26:14,170 --> 00:26:20,020 >> Mogli bismo, ako smo se vratili u, mi redefinirati ladice da se pokazivač koji 615 00:26:20,020 --> 00:26:22,300 smo zatim koristiti malloc u ruku memorije. 616 00:26:22,300 --> 00:26:25,050 Jer ako mi je sjećanje na heap putem malloc, mi 617 00:26:25,050 --> 00:26:26,430 mogao zatim ga osloboditi. 618 00:26:26,430 --> 00:26:29,630 No, prije nego što ga oslobađa, što smo mogli preraspodijeliti veći komad memorije, 619 00:26:29,630 --> 00:26:31,330 ažurirali pokazivač, i tako dalje. 620 00:26:31,330 --> 00:26:33,500 Ali za sada, ovo je stvarno najbolje što možemo učiniti. 621 00:26:33,500 --> 00:26:36,360 Push i pop vjerojatno se ide se moraju signalizirati neke pogreške. 622 00:26:36,360 --> 00:26:40,270 >> Tako, primjerice, ostvarenju push mogao vratiti bool koji 623 00:26:40,270 --> 00:26:42,390 prije vratio istina, istina, istina. 624 00:26:42,390 --> 00:26:48,390 No, četvrti put, to će imati vratiti false, primjerice. 625 00:26:48,390 --> 00:26:48,540 U redu. 626 00:26:48,540 --> 00:26:49,540 Vrlo dobro učinio. 627 00:26:49,540 --> 00:26:50,060 Čestitamo. 628 00:26:50,060 --> 00:26:52,160 Vi ste zaradili svoj stres loptu i danas. 629 00:26:52,160 --> 00:26:53,110 >> [PLJESAK] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Hvala vam. 631 00:26:54,382 --> 00:26:55,680 >> DAVID Malan: Hvala vam. 632 00:26:55,680 --> 00:26:59,740 U redu, tako da to izgleda kao da se nije puno od korak naprijed, zar ne? 633 00:26:59,740 --> 00:27:01,410 Mi opisao ovu strukturu podataka. 634 00:27:01,410 --> 00:27:02,320 To je bio uvjerljiv, zar ne? 635 00:27:02,320 --> 00:27:03,200 Operacijski sustavi se svidjeti. 636 00:27:03,200 --> 00:27:06,360 Navodno web može iskoristiti ovu, i druge aplikacije još uvijek. 637 00:27:06,360 --> 00:27:10,870 No, ono glupo ograničenje da smo natrag na svojevrsni tjedan dvije granice 638 00:27:10,870 --> 00:27:12,880 gdje smo fiksne veličine polja. 639 00:27:12,880 --> 00:27:15,010 >> Dakle, zbilja postoji par načina možemo riješiti ovo. 640 00:27:15,010 --> 00:27:18,750 Mi dinamički mogao dodijeliti niz, ne tvrdi to kodiranja kao što sam 641 00:27:18,750 --> 00:27:22,600 obaviti ovdje, ali umjesto toga ponovno izjavljuje ovo, samo da bude jasno, kao 642 00:27:22,600 --> 00:27:23,830 nešto poput ovoga. 643 00:27:23,830 --> 00:27:29,040 Int * ladice, ne odluči na kapacitetom još. 644 00:27:29,040 --> 00:27:35,460 Ali kad sam proglasiti stog negdje drugdje u mom kodu, onda sam mogao nazvati malloc, 645 00:27:35,460 --> 00:27:38,250 dobiti adresu od sitna memorije, i ja mogao dodijeliti 646 00:27:38,250 --> 00:27:39,980 koji se odnose na pladnjevima. 647 00:27:39,980 --> 00:27:43,340 >> A onda, jer to je samo komad memorije, mogao sam nastaviti koristiti trgu 648 00:27:43,340 --> 00:27:45,450 Nosač zapis na uobičajeni način. 649 00:27:45,450 --> 00:27:49,020 Jer opet, postoji neka vrsta ove funkcionalni ekvivalent polja i 650 00:27:49,020 --> 00:27:50,820 komadi sjećanja koje dolaze natrag na malloc. 651 00:27:50,820 --> 00:27:53,090 Mi možemo tretirati kao jedan drugi pomoću pokazivača aritmetike ili 652 00:27:53,090 --> 00:27:54,440 uglata zagrada zapis. 653 00:27:54,440 --> 00:27:55,660 Dakle, to je jedan pristup. 654 00:27:55,660 --> 00:28:00,120 >> No, kako se drugi možda smo implementirati ovaj ista struktura podataka, potencijalno? 655 00:28:00,120 --> 00:28:00,280 Točno? 656 00:28:00,280 --> 00:28:04,530 Osjećam se kao da smo upravo riješili ove problem kao što je prije tjedan dana. 657 00:28:04,530 --> 00:28:08,860 Što je rješenje za ovaj problem da je Steven naletjeli? 658 00:28:08,860 --> 00:28:10,370 Dakle povezane liste, desno. 659 00:28:10,370 --> 00:28:13,410 >> Ako je problem što smo slikanja sami u kutu dodjelom 660 00:28:13,410 --> 00:28:17,580 unaprijed premalo memorije koja smo onda su na neki način bave, dobro, 661 00:28:17,580 --> 00:28:19,880 Zato ne samo da bi se izbjeglo izdati uopce? 662 00:28:19,880 --> 00:28:26,170 Zašto ne samo izjaviti da se ladice pokazivač na čvor, Ergo povezani popis, 663 00:28:26,170 --> 00:28:30,740 i onda jednostavno izdvojiti novih čvorova svaki put Steven potrebno da stane 664 00:28:30,740 --> 00:28:32,400 Broj u strukturu podataka. 665 00:28:32,400 --> 00:28:34,200 >> Dakle, slika će morati promijeniti. 666 00:28:34,200 --> 00:28:38,220 To neće biti čist i kao jednostavan kao samo niz od tri Ints. 667 00:28:38,220 --> 00:28:42,970 Sada će biti pokazivač rekonstruirati, te da će se rekonstruirati 668 00:28:42,970 --> 00:28:44,830 imate int i pored upustvo. 669 00:28:44,830 --> 00:28:47,670 To će dovesti, preko tog pokazivača na neko drugo takvo struct se 670 00:28:47,670 --> 00:28:48,600 Još jedan takav rekonstruirati. 671 00:28:48,600 --> 00:28:50,560 Dakle, slika bi zapravo dobiti Messier bitni. 672 00:28:50,560 --> 00:28:52,950 I mi bismo strelice vezanje sve zajedno. 673 00:28:52,950 --> 00:28:55,280 >> Ali to je u redu, zar ne, jer se Vidjeli smo kako to učiniti. 674 00:28:55,280 --> 00:28:58,180 I jednom kada se udobno provedbi nešto poput linked 675 00:28:58,180 --> 00:29:01,450 Popis, koji ćete morati učiniti ako odlučite provesti hash tablicu s 676 00:29:01,450 --> 00:29:05,120 odvojeni ulančavanje za p-set 6, možete ga koristiti kao građevinski blok, ili na 677 00:29:05,120 --> 00:29:08,870 sastojak, ili u nule govoriti, Postupak, nešto što ste stavili, ti 678 00:29:08,870 --> 00:29:12,560 stvorili svoj vlastiti slagalice koji onda možete ponovno koristiti. 679 00:29:12,560 --> 00:29:17,090 Dakle kompromise, ali mogućih rješenja da smo zapravo prije nisam vidjela. 680 00:29:17,090 --> 00:29:20,560 >> Dakle, vrlo često, vidiš ovo svaki godinu ili dvije kad Apple releases 681 00:29:20,560 --> 00:29:23,060 nešto novo, a svi su ludi ljudi ravnini izvan Apple 682 00:29:23,060 --> 00:29:27,050 pohraniti kupiti njihov marginalni nadogradnju na hardveru. 683 00:29:27,050 --> 00:29:30,420 Kažem to, to je u redu, jer je Ja sam jedan od tih ljudi. 684 00:29:30,420 --> 00:29:35,140 Pa kakav strukture podataka moglo predstavljati ovu stvarnost? 685 00:29:35,140 --> 00:29:36,980 >> Pa, nazovimo je red, red. 686 00:29:36,980 --> 00:29:40,270 Tako će Britanci zovu obično red svejedno, tako da je lijepo ime. 687 00:29:40,270 --> 00:29:44,960 A dvije operacije koje queue će podržati ćemo pozvati enqueue 688 00:29:44,960 --> 00:29:48,900 rad i dequeue operacije, koje su slične u 689 00:29:48,900 --> 00:29:50,120 Duh gurati i pop. 690 00:29:50,120 --> 00:29:54,060 To je samo neka vrsta razlikuje u Konvencija, što mi to zove. 691 00:29:54,060 --> 00:29:57,680 No, kako bi enqueue nešto znači dodati ili ga stavite na strukturu podataka. 692 00:29:57,680 --> 00:29:59,570 Za dequeue znači da biste ga uklonili. 693 00:29:59,570 --> 00:30:05,170 No, dok je snop LIFO podataka struktura, red je prvo u, 694 00:30:05,170 --> 00:30:06,740 Prvi iz strukture podataka. 695 00:30:06,740 --> 00:30:10,050 >> Ako ste prva osoba u liniji, što će biti prva osoba koja se 696 00:30:10,050 --> 00:30:12,420 iz linije i kupiti novi uređaj. 697 00:30:12,420 --> 00:30:18,070 Zamislite koliko je uzrujan ti ljudi bi se ako Apple umjesto da se koristi snop, za 698 00:30:18,070 --> 00:30:21,250 Primjerice, za provedbu te preuzimaju do vašeg novom igračkom. 699 00:30:21,250 --> 00:30:24,310 Dakle redovi smisla, svakako, i možemo sjetiti svih vrsta 700 00:30:24,310 --> 00:30:27,480 aplikacija, vjerojatno, za redove, pogotovo kada želite pravičnost. 701 00:30:27,480 --> 00:30:30,040 Dakle, kako bismo mogli provesti te kao struktura podataka? 702 00:30:30,040 --> 00:30:33,680 >> Pa, predlažem da bismo mogli trebate napraviti na ovaj način. 703 00:30:33,680 --> 00:30:35,225 Tako da ću sada imati brojeve. 704 00:30:35,225 --> 00:30:38,190 Tako ćemo zadržati jednostavan i ne nužno govoriti u smislu ladice. 705 00:30:38,190 --> 00:30:40,220 Samo brojevi koji narod stečen. 706 00:30:40,220 --> 00:30:43,760 Kapacitet će se, opet, riješiti Ukupan broj ljudi koji mogu biti u 707 00:30:43,760 --> 00:30:46,900 ova linija, tri ili god druga vrijednost. 708 00:30:46,900 --> 00:30:50,760 >> No, predlažem da moram pratiti ne samo na veličinu 709 00:30:50,760 --> 00:30:52,370 red, koliko su stvari u njemu. 710 00:30:52,370 --> 00:30:56,310 Dakle, veličina je trenutna veličina, kapacitet je maksimalna veličina. 711 00:30:56,310 --> 00:30:58,540 Samo jednom, nomenklatura po konvenciji. 712 00:30:58,540 --> 00:31:03,680 Zašto mi je potrebna dodatna int unutar o redu za pratiti tko je u 713 00:31:03,680 --> 00:31:05,365 ispred linije? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Zašto trebam to učiniti u ovom slučaju? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Pa, kako je ova slika će se promijeniti? 718 00:31:16,190 --> 00:31:19,280 Ja vjerojatno može ponovno najviše ove slike. 719 00:31:19,280 --> 00:31:21,480 Dopustite mi da ide naprijed i izbrisati ono što je ovdje. 720 00:31:21,480 --> 00:31:24,580 Mi ćemo dati to malo drugačije ime ovdje. 721 00:31:24,580 --> 00:31:28,930 Da biste dobili osloboditi od 17, neka riješi od 9., idemo dobiti osloboditi od tri. 722 00:31:28,930 --> 00:31:30,410 I dodajmo još jednu stvar. 723 00:31:30,410 --> 00:31:34,710 Predlažem da moram pratiti Prednji dio popisa, što je samo 724 00:31:34,710 --> 00:31:35,570 će biti int, kao dobro. 725 00:31:35,570 --> 00:31:36,550 I mi ćemo ga zadržati jednostavan. 726 00:31:36,550 --> 00:31:37,740 Nema povezani popis za sada. 727 00:31:37,740 --> 00:31:40,900 >> Mi ćemo priznati da smo idući u naletjeti na ove granice. 728 00:31:40,900 --> 00:31:43,720 No, ono što želim vidjeti dogoditi ovaj put? 729 00:31:43,720 --> 00:31:47,240 Dakle, pretpostavimo da idem naprijed i prva Osoba dolazi u liniji, a 730 00:31:47,240 --> 00:31:48,560 to je broj 9. 731 00:31:48,560 --> 00:31:49,680 Mi nemamo stres loptice. 732 00:31:49,680 --> 00:31:51,330 Mogu li kradu, recimo, dvije ili tri osobe? 733 00:31:51,330 --> 00:31:52,690 Jedan, dva, tri? 734 00:31:52,690 --> 00:31:53,120 Dođi gore. 735 00:31:53,120 --> 00:31:56,022 Desno sprijeda, jer ćemo napraviti ovo brzo. 736 00:31:56,022 --> 00:31:59,415 >> Svaki od vas sada će biti fan Dječak u redu na Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Nećete biti primanje Apple hardvera na kraju ove ipak. 739 00:32:06,210 --> 00:32:06,500 U redu. 740 00:32:06,500 --> 00:32:09,430 Dakle, ti si broj 9, ti si broj 17, broj 22. 741 00:32:09,430 --> 00:32:12,130 To su proizvoljne brojeve, kao što su studentske iskaznice ili sitnica. 742 00:32:12,130 --> 00:32:14,550 I u samo trenutak, započnimo za početak dodajući stvari. 743 00:32:14,550 --> 00:32:16,000 I ja ću pokrenuti matičnu ovdje ovaj put. 744 00:32:16,000 --> 00:32:19,570 >> Dakle, u ovom slučaju, ja sam inicijalizacije Prednji se - 745 00:32:19,570 --> 00:32:22,380 Ja sam zapravo stvarno ne briga što Prednji je, jer je veličina nula. 746 00:32:22,380 --> 00:32:24,480 Dakle, to možda i samo se Upitnik. 747 00:32:24,480 --> 00:32:26,170 To su sve upitnika. 748 00:32:26,170 --> 00:32:29,880 Dakle, sada ćemo početi vidjeti neke stvari ljudi podstava gore u trgovini. 749 00:32:29,880 --> 00:32:33,320 >> Dakle, ako je broj 9, ti si prvi tamo u 05:00, ići naprijed i postroje, 750 00:32:33,320 --> 00:32:34,210 ili večer prije. 751 00:32:34,210 --> 00:32:34,580 OK. 752 00:32:34,580 --> 00:32:35,940 Tako sada 9 je ovdje. 753 00:32:35,940 --> 00:32:37,940 Tako 9 je u prednjem dijelu popisa. 754 00:32:37,940 --> 00:32:41,440 Dakle, ja ću ići naprijed i ažurirati Veličina ovog aktualnih podataka 755 00:32:41,440 --> 00:32:44,740 struktura ne bi se više 0, , ali da se 1. 756 00:32:44,740 --> 00:32:47,630 Ja ću staviti na 9 Prednji dio popisa. 757 00:32:47,630 --> 00:32:51,020 Dopustite mi da ide naprijed i prebacivati ​​zaslon tako možemo vidjeti kraj nas ovdje. 758 00:32:51,020 --> 00:32:53,220 >> A sada što želim staviti na prednjoj strani? 759 00:32:53,220 --> 00:32:56,240 Ja ću pratiti da Pročelje red sada 760 00:32:56,240 --> 00:32:58,570 nalazi se na mjestu 0. 761 00:32:58,570 --> 00:33:00,510 Zato što je sljedeće što će se dogoditi? 762 00:33:00,510 --> 00:33:03,000 Pa, recimo sad sam enqueue 17, kao dobro. 763 00:33:03,000 --> 00:33:04,510 Dakle hop u skladu tamo. 764 00:33:04,510 --> 00:33:07,060 I opet, vrsta vrata Trgovina će biti ovdje. 765 00:33:07,060 --> 00:33:08,700 Dakle, sada sam dodao 17. 766 00:33:08,700 --> 00:33:10,810 I iako ti dečki su blokiranja zaslon, to je u redu, 767 00:33:10,810 --> 00:33:12,300 jer ga možemo vidjeti ovdje. 768 00:33:12,300 --> 00:33:12,910 Žao nam je. 769 00:33:12,910 --> 00:33:13,810 >> PUBLIKA: Možemo se - 770 00:33:13,810 --> 00:33:14,660 >> DAVID Malan: Ne, to je u redu. 771 00:33:14,660 --> 00:33:16,000 To je ogromna gore. 772 00:33:16,000 --> 00:33:18,580 Dakle, 17 je sada unutar reda. 773 00:33:18,580 --> 00:33:21,332 Trebam li ažurirati koja Polja sada ipak? 774 00:33:21,332 --> 00:33:23,210 OK, definitivno veličina. 775 00:33:23,210 --> 00:33:26,430 A što je ispred? 776 00:33:26,430 --> 00:33:27,040 OK, nema. 777 00:33:27,040 --> 00:33:30,200 Prednji ne bi trebalo mijenjati, jer za razliku od hrpe, mi 778 00:33:30,200 --> 00:33:31,370 Želite održavati pravičnosti. 779 00:33:31,370 --> 00:33:35,150 Dakle, ako je 9 osvojilo prvo, želimo 9 biti prvi iz reda 780 00:33:35,150 --> 00:33:36,420 te u trgovini. 781 00:33:36,420 --> 00:33:37,220 >> U stvari, da vidimo kako. 782 00:33:37,220 --> 00:33:42,235 Prije nego što stavite 22, hajdemo ići naprijed i dequeue 9. 783 00:33:42,235 --> 00:33:42,970 Koje je vaše ime? 784 00:33:42,970 --> 00:33:43,680 >> PUBLIKA: Jake. 785 00:33:43,680 --> 00:33:45,440 >> DAVID Malan: Jake ide da se dequeued sada. 786 00:33:45,440 --> 00:33:48,050 Tako ćete dobiti hodati u dućan. 787 00:33:48,050 --> 00:33:49,880 I praviti se da trgovine je tamo. 788 00:33:49,880 --> 00:33:51,970 I što sad treba - dit-dit-dit! 789 00:33:51,970 --> 00:33:53,400 Što se treba dogoditi sada? 790 00:33:53,400 --> 00:33:54,490 Dizajn odluka. 791 00:33:54,490 --> 00:33:56,825 Pa nije loša instinkt, ali - ono zoveš? 792 00:33:56,825 --> 00:33:57,090 >> PUBLIKA: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID Malan: David. 794 00:33:57,500 --> 00:33:58,810 Dakle, što je David učiniti? 795 00:33:58,810 --> 00:34:02,590 Pokušavao je svojevrsni popraviti podatke Struktura i premjestiti iz svoje mjesto 796 00:34:02,590 --> 00:34:04,100 u Jakeovo bivše mjesto. 797 00:34:04,100 --> 00:34:06,740 I to je u redu, ako smo spremni prihvatiti da je kao 798 00:34:06,740 --> 00:34:08,199 Provedba detalja. 799 00:34:08,199 --> 00:34:11,100 Ali prvo, neka je ažurirati podatke strukturu prije nego što to učinimo. 800 00:34:11,100 --> 00:34:14,139 Jer ja ne sviđa ideja o svima narod kreće u toj liniji. 801 00:34:14,139 --> 00:34:17,360 >> To nije velika stvar, ako je David to čini s jedan korak, ali opet, sjetim 802 00:34:17,360 --> 00:34:20,360 kada smo imali osam volontera na pozornici, a mi smo radili, ubacivanje 803 00:34:20,360 --> 00:34:22,600 sortiranje, gdje smo morali početi kreće svima okolo. 804 00:34:22,600 --> 00:34:23,790 To ih je skupo, zar ne? 805 00:34:23,790 --> 00:34:28,330 To čini mi dodvoravanje o velikim O n, veliki O n kvadrat ponovno. 806 00:34:28,330 --> 00:34:30,650 To se ne osjeća kao idealno ishod. 807 00:34:30,650 --> 00:34:32,080 >> Pa neka je samo ažurirati taj. 808 00:34:32,080 --> 00:34:35,120 Dakle, veličina red više nije 2. 809 00:34:35,120 --> 00:34:37,090 Sada je jednostavno 1. 810 00:34:37,090 --> 00:34:40,360 Ali ja sad mogu ažurirati nešto Nisam ažuriraju prije, 811 00:34:40,360 --> 00:34:41,130 Prednji dio popisa. 812 00:34:41,130 --> 00:34:45,420 Ja samo mogu reći, da je mjesto 1? 813 00:34:45,420 --> 00:34:49,770 Tako sada imamo smeće vrijednost ovdje, Vrijednost ovog smeća, a David u 814 00:34:49,770 --> 00:34:51,469 Sredinom ovog smeća. 815 00:34:51,469 --> 00:34:54,980 No, struktura podataka je još uvijek netaknut. 816 00:34:54,980 --> 00:34:58,540 >> A u stvari, ja uopće ne trebaju Jake promijeniti bivši broj 817 00:34:58,540 --> 00:35:00,460 9, jer koga briga. 818 00:35:00,460 --> 00:35:04,470 Imam dovoljno informacija sada u Veličina Znam da postoji jedna osoba koja je u 819 00:35:04,470 --> 00:35:05,030 ovaj red. 820 00:35:05,030 --> 00:35:08,340 I znam da je ta osoba nalazi se na mjestu 1, a ne 0. 821 00:35:08,340 --> 00:35:09,760 Ja se ne brojim. 822 00:35:09,760 --> 00:35:11,300 Dakle 1, kao dobro. 823 00:35:11,300 --> 00:35:13,410 Dakle, struktura podataka je još uvijek u redu. 824 00:35:13,410 --> 00:35:14,330 >> Pa, što se događa sljedeće? 825 00:35:14,330 --> 00:35:15,010 Idemo Postavi u red - 826 00:35:15,010 --> 00:35:15,370 kako se ti zoveš? 827 00:35:15,370 --> 00:35:16,160 >> PUBLIKA: Callen. 828 00:35:16,160 --> 00:35:16,580 >> DAVID Malan: Callen. 829 00:35:16,580 --> 00:35:20,770 Idemo enqueue je Callen, i 22 je sada u redu. 830 00:35:20,770 --> 00:35:22,300 Dakle, ono što se sada mora promijeniti ovdje? 831 00:35:22,300 --> 00:35:24,380 Prednji se neće promijeniti, očito. 832 00:35:24,380 --> 00:35:27,160 Veličina će se promijeniti da bude 2 ponovno. 833 00:35:27,160 --> 00:35:31,590 I 22 završi ovdje, 9 je još uvijek prisutna, ali to je učinkovitije 834 00:35:31,590 --> 00:35:32,600 smeća vrijednost sada. 835 00:35:32,600 --> 00:35:35,910 To je samo ostatak prošlosti Jake. 836 00:35:35,910 --> 00:35:39,200 >> Dakle, sada što će se dogoditi ako se Ja dequeue Davida? 837 00:35:39,200 --> 00:35:41,560 Jedan posljednja operacija, dequeue David. 838 00:35:41,560 --> 00:35:46,070 Mogli bismo pomak, ali predlažem neka se učinite što manje posla što je više moguće. 839 00:35:46,070 --> 00:35:50,280 Sada mi je struktura podataka prolazi natrag u veličini 2-1. 840 00:35:50,280 --> 00:35:53,730 No, prednji red Sada postaje 2. 841 00:35:53,730 --> 00:35:56,640 Ne trebate promijeniti te brojeve samo još, jer su 842 00:35:56,640 --> 00:35:58,230 samo smeće vrijednosti. 843 00:35:58,230 --> 00:35:59,720 >> Ali sada što se događa? 844 00:35:59,720 --> 00:36:03,280 Pretpostavimo da sam enqueue, 26? 845 00:36:03,280 --> 00:36:05,890 Osjećam se kao da pripadam ovdje. 846 00:36:05,890 --> 00:36:06,890 Tako sam se enqueued. 847 00:36:06,890 --> 00:36:08,760 Tako nekako sam pripadam ovdje. 848 00:36:08,760 --> 00:36:11,300 A čak i ako to nije dosta Cijenim to vizualno na pozornici, 849 00:36:11,300 --> 00:36:15,075 jer imamo dosta prostora, trebao bih Ne mogu stajati ovdje, zašto? 850 00:36:15,075 --> 00:36:16,290 >> PUBLIKA: Ti si izvan granica. 851 00:36:16,290 --> 00:36:16,370 >> DAVID Malan: Točno. 852 00:36:16,370 --> 00:36:16,940 Ja sam izvan granica igrališta. 853 00:36:16,940 --> 00:36:19,330 Ja sam indeksirane izvan Granica u ovom polju. 854 00:36:19,330 --> 00:36:23,420 Stvarno bi trebali biti u jednom od tri moguće lokacije. 855 00:36:23,420 --> 00:36:25,150 Sada, gdje je najprirodnije ići? 856 00:36:25,150 --> 00:36:27,760 Predlažem da utjecati Tjedan je jedan trik. 857 00:36:27,760 --> 00:36:30,150 Mod operatera, postotak. 858 00:36:30,150 --> 00:36:36,850 Jer ja stojim na tehnički Mjesto na 3, ali ja to 3 mod sposobnosti, 859 00:36:36,850 --> 00:36:40,250 pa 3, znak za postotak, 3 - 860 00:36:40,250 --> 00:36:40,970 kapacitet je 3. 861 00:36:40,970 --> 00:36:41,720 Što je to? 862 00:36:41,720 --> 00:36:43,700 Što je ostatak pri podijelite 3 za 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Tako da me stavlja su Jake je, što je zapravo dobro. 865 00:36:48,140 --> 00:36:50,370 Tako sada implementacije za to što se događa s 866 00:36:50,370 --> 00:36:51,250 biti malo glavobolje. 867 00:36:51,250 --> 00:36:53,740 To je zapravo samo jedna linija glavobolje, koda. 868 00:36:53,740 --> 00:36:56,580 Ali barem sada postoji smeća Vrijednost ovog mjesta, ali ima dvije 869 00:36:56,580 --> 00:36:57,910 legitimne Ints ovdje. 870 00:36:57,910 --> 00:37:04,160 A ja tvrdim da je sada smo učinili upravo ono što trebamo učiniti tako dugo dok 871 00:37:04,160 --> 00:37:08,600 možemo promijeniti ono Jake vrijednosti biti 26. 872 00:37:08,600 --> 00:37:12,110 >> Mi sada imamo dovoljno informacija dalje održavanje integriteta 873 00:37:12,110 --> 00:37:13,060 ove strukture podataka. 874 00:37:13,060 --> 00:37:17,160 Mi smo još uvijek vrsta od sreće kad smo želite umetnuti četiri ili više ukupno 875 00:37:17,160 --> 00:37:20,740 elementi, ali mogu barem napraviti lijepa učinkovito korištenje ove konstantna 876 00:37:20,740 --> 00:37:21,740 Vrijeme, u stvari. 877 00:37:21,740 --> 00:37:27,150 Ne morate brinuti o tome prebacuje svatko, kao Davidova sklonosti bio. 878 00:37:27,150 --> 00:37:30,816 >> Bilo kakva pitanja na hrpe, ili ovaj red? 879 00:37:30,816 --> 00:37:32,184 >> PUBLIKA: Je li razlog morate veličinu tako da znate 880 00:37:32,184 --> 00:37:34,010 gdje je imati osobu? 881 00:37:34,010 --> 00:37:34,770 >> DAVID Malan: Točno. 882 00:37:34,770 --> 00:37:38,230 Moram znati veličinu polja jer moram znati točno kako 883 00:37:38,230 --> 00:37:41,940 mnogi od tih vrijednosti su legitimna, i tako da mogu naći gdje staviti 884 00:37:41,940 --> 00:37:42,800 Sljedeća osoba. 885 00:37:42,800 --> 00:37:43,300 Točno. 886 00:37:43,300 --> 00:37:44,580 Veličina je - 887 00:37:44,580 --> 00:37:46,360 Zapravo, nismo ažurirali ovaj još. 888 00:37:46,360 --> 00:37:48,380 Ja sam dodao na 26. 889 00:37:48,380 --> 00:37:51,760 Veličina je sada, a ne 1, nego 2. 890 00:37:51,760 --> 00:37:57,780 Dakle, sada je to doista pomaže mi da nađem Glava lista, koji nije 0, a ne 891 00:37:57,780 --> 00:37:59,250 1, ali je 2. 892 00:37:59,250 --> 00:38:01,665 Prednji dio popisa je doista broj 22. 893 00:38:01,665 --> 00:38:05,120 Jer on je došao u prvi, tako da je on trebao biti dopušteno u trgovini prije mene, 894 00:38:05,120 --> 00:38:08,780 iako vizualno stojim bliže u trgovini. 895 00:38:08,780 --> 00:38:09,220 >> U redu? 896 00:38:09,220 --> 00:38:12,410 Pljesak za ove dečke a mi ćemo ih pustiti van. 897 00:38:12,410 --> 00:38:17,090 >> [PLJESAK] 898 00:38:17,090 --> 00:38:18,150 >> DAVID Malan: Mogao bih neka držite ladicu. 899 00:38:18,150 --> 00:38:20,760 Mogli smo vidjeti što će se dogoditi ako se želite, ali možda i nije. 900 00:38:20,760 --> 00:38:21,590 U redu. 901 00:38:21,590 --> 00:38:25,380 I što sad to nam preostaje? 902 00:38:25,380 --> 00:38:28,900 Pa, neka mi predlažemo da postoji Nekoliko druge strukture podataka mogli bismo 903 00:38:28,900 --> 00:38:33,810 početi dodajući da naš paket alata koji će zapravo biti vrlo, vrlo relevantni kao 904 00:38:33,810 --> 00:38:35,270 smo zaroniti u web stvari. 905 00:38:35,270 --> 00:38:38,150 Koji opet, ima neku vrstu priključka na stabla u obliku 906 00:38:38,150 --> 00:38:40,550 nešto što se zove DOM, dokument objektni model. 907 00:38:40,550 --> 00:38:42,370 No, vidjet ćemo više da ne zadugo. 908 00:38:42,370 --> 00:38:46,260 >> Dopustite mi predlažemo da smo preko definicija nazovite stablo sada ono što možda znate, kao 909 00:38:46,260 --> 00:38:48,820 Više od obiteljskog stabla, gdje se imaju neki predak u 910 00:38:48,820 --> 00:38:49,790 korijenje stabla. 911 00:38:49,790 --> 00:38:54,480 Patrijarhalnih ili matrijarh u samom vrhu stabla. 912 00:38:54,480 --> 00:38:56,700 Bez svog bračnog druga, u ovom slučaju. 913 00:38:56,700 --> 00:39:00,940 No, mi sada imamo ono što ćemo nazvati Djeca, koja su čvorovi koji vise 914 00:39:00,940 --> 00:39:05,480 off na lijevoj ili desnoj dijete dijete, strelice kao što je prikazano ovdje. 915 00:39:05,480 --> 00:39:10,490 >> Drugim riječima, u strukturi stabla podataka u računalo, stablo ima nulu 916 00:39:10,490 --> 00:39:11,480 ili više čvorova. 917 00:39:11,480 --> 00:39:13,500 Ako je barem jedan čvor to se zove korijen. 918 00:39:13,500 --> 00:39:15,700 To su stvari koje vizualno skrećemo na vrhu. 919 00:39:15,700 --> 00:39:20,280 I to čvora, kao i svaki drugi čvor, može imaju nula, jedan ili dva, ili tri, 920 00:39:20,280 --> 00:39:23,600 ili ipak mnogo djece struktura podataka podržava. 921 00:39:23,600 --> 00:39:29,150 U ovom slučaju, korijen, spremanje Vrijednost jednog, ima dvoje djece, 2 i 3, 922 00:39:29,150 --> 00:39:33,020 tako da mi općenito zovemo dvije lijeve Dijete i 3. pravo dijete. 923 00:39:33,020 --> 00:39:36,940 >> I onda kad dođemo do 5., 6., i 7, 6 bi se moglo nazvati srednje dijete. 924 00:39:36,940 --> 00:39:38,940 Ako imate četvero djece, to dobiva zbunjujuće. 925 00:39:38,940 --> 00:39:42,260 Tako ćemo prestati koristiti tu vrstu od prečac usmeno. 926 00:39:42,260 --> 00:39:44,580 Ali to je zapravo samo obiteljsko stablo. 927 00:39:44,580 --> 00:39:48,880 I lišće ovdje su čvorovi koji i sami nemaju djece. 928 00:39:48,880 --> 00:39:52,540 Oni družiti s dna stabla. 929 00:39:52,540 --> 00:39:56,940 >> Dakle, kako bismo mogli provesti taj stablo ima samo dvoje djece maksimalno? 930 00:39:56,940 --> 00:39:58,410 Zvat ćemo je binarno stablo. 931 00:39:58,410 --> 00:40:00,960 Bi opet znači dvije, u ovom slučaj, kao što je s binarnim. 932 00:40:00,960 --> 00:40:04,830 I tako to može imati nula, jedan, ili dvoje djece najvi. 933 00:40:04,830 --> 00:40:08,650 >> Ja ću predložiti da se implementirati čvor za tu strukturu s int n, 934 00:40:08,650 --> 00:40:11,910 a zatim dva pokazivače, jedan se zove lijevo, jedan se zove pravo. 935 00:40:11,910 --> 00:40:14,830 No, to su samo lijepo proizvoljne konvencije. 936 00:40:14,830 --> 00:40:18,170 A što je lijepo sada, pogotovo ako vrsta borili s konceptualno 937 00:40:18,170 --> 00:40:21,300 rekurzija, ili misli da nije Stvarno rješenje za bilo što, 938 00:40:21,300 --> 00:40:23,120 pogotovo ako bi ponestane memorije. 939 00:40:23,120 --> 00:40:26,600 Sada kada govorimo o podacima strukture i algoritmi koji omogućuju 940 00:40:26,600 --> 00:40:31,030 nas poprijeko i njima manipulirati, Ispada da je rekurzija vrati u 941 00:40:31,030 --> 00:40:34,240 mnogo uvjerljiviji ako ne i lijep način. 942 00:40:34,240 --> 00:40:38,670 >> Dakle, to predlažem je provedba od Search funkciju. 943 00:40:38,670 --> 00:40:39,870 S obzirom dva ulaza - 944 00:40:39,870 --> 00:40:41,570 tako da mislim ovo kao crnu kutiju. 945 00:40:41,570 --> 00:40:46,560 Dati dva ulaza, n, int i pointer na stablu, pokazivač 946 00:40:46,560 --> 00:40:50,020 čvora, ili stvarno korijen stabla, sam tvrdnja da je ova funkcija može vratiti 947 00:40:50,020 --> 00:40:53,530 Istina ili laž, da je vrijednost n je unutar ovog stabla. 948 00:40:53,530 --> 00:40:55,210 >> Ono što je unutar ove crne kutije? 949 00:40:55,210 --> 00:40:57,440 Pa, četiri grane. 950 00:40:57,440 --> 00:40:58,385 Prvi upravo provjerava. 951 00:40:58,385 --> 00:41:00,490 Ako stablo je null, samo povratak false. 952 00:41:00,490 --> 00:41:04,580 Ako nema čvora, nema n, ne postoji broj, samo povratak false. 953 00:41:04,580 --> 00:41:12,330 Ako ipak, n, vrijednost koju tražite za, je manje od stabla strelice n i 954 00:41:12,330 --> 00:41:15,180 samo da bude jasno, što to znači kada se Pišem stablo, a zatim strelicu 955 00:41:15,180 --> 00:41:18,150 zapis, n? 956 00:41:18,150 --> 00:41:18,690 Točno. 957 00:41:18,690 --> 00:41:21,970 To znači da je dereference Pokazivač se zove stablo. 958 00:41:21,970 --> 00:41:26,750 Idi tamo, a zatim ući u to čvora i dobiti svoje područje pod nazivom n. 959 00:41:26,750 --> 00:41:30,810 A onda usporedite stvarni n koji je bio prešao u pretraživanju protiv njega. 960 00:41:30,810 --> 00:41:35,390 >> Dakle, ako je n manji od, n vrijednosti u čvor stabla sama, dobro, 961 00:41:35,390 --> 00:41:36,720 Što to znači? 962 00:41:36,720 --> 00:41:40,690 To znači ništa na prvi pogled. 963 00:41:40,690 --> 00:41:40,900 Točno? 964 00:41:40,900 --> 00:41:45,560 Baš kao kad imate niz Vrijednosti, možda bih se prijaviti binarni 965 00:41:45,560 --> 00:41:48,290 pretraživanje kao oblik podjele i osvajanje. 966 00:41:48,290 --> 00:41:51,790 No, ono što je pretpostavka moramo napraviti za binary search uopće raditi 967 00:41:51,790 --> 00:41:54,510 u telefonskom imeniku i raniji primjeri? 968 00:41:54,510 --> 00:41:55,530 >> Kako biti riješeno. 969 00:41:55,530 --> 00:41:59,490 Tako ćemo precizirati definiciju stabla Ovdje ne da se samo stablo, što može 970 00:41:59,490 --> 00:42:00,880 imati bilo koji broj djece. 971 00:42:00,880 --> 00:42:04,700 Ne samo binarno stablo, što može imaju 0, 1, ili 2 maksimalno. 972 00:42:04,700 --> 00:42:09,700 Ali kao binarni pretraživanje stabla, ili BST, koji je samo fancy način govoreći: 973 00:42:09,700 --> 00:42:15,430 binarna stabla tako da svaki čvor lijevo dijete, ako je prisutan, je 974 00:42:15,430 --> 00:42:16,830 manje od čvora. 975 00:42:16,830 --> 00:42:20,170 I Svaki čvor je pravo dijete, ako je prisutan, je veći 976 00:42:20,170 --> 00:42:21,740 od čvora sama. 977 00:42:21,740 --> 00:42:25,200 >> Dakle, drugim riječima, ako ste bili na izvlačenje Stablo se, svi brojevi su 978 00:42:25,200 --> 00:42:30,620 Pažljivo uravnotežena ovako, tako da ako imate 55 kao korijen, 33 može ići 979 00:42:30,620 --> 00:42:33,090 na svojoj lijevoj strani, jer to je manje od 55 godina. 980 00:42:33,090 --> 00:42:36,430 77 može ići u svom pravu jer to je veća od 55 godina. 981 00:42:36,430 --> 00:42:40,750 Ali sada primjetiti, istu definiciju, to je rekurzivna definicija verbalno, 982 00:42:40,750 --> 00:42:42,600 mora podnijeti zahtjev za 33. 983 00:42:42,600 --> 00:42:47,610 33 je lijevo dijete mora biti manji od njega, , a 33 je pravo dijete, 44, moraju biti 984 00:42:47,610 --> 00:42:48,580 veći od njega. 985 00:42:48,580 --> 00:42:51,670 >> Dakle, ovo je binarna stabla, i Predlažem, koristite malo 986 00:42:51,670 --> 00:42:53,910 rekurzija, sada možemo naći n. 987 00:42:53,910 --> 00:42:59,160 Dakle, ako je n manji od vrijednosti n koji je trenutni čvor, ja ću otići 988 00:42:59,160 --> 00:43:04,090 naprijed i čamac, da tako kažemo, i samo vratite god odgovor je 989 00:43:04,090 --> 00:43:08,470 potrazi za n na Stablo lijevo dijete. 990 00:43:08,470 --> 00:43:11,370 Obavijest opet, ova funkcija jednostavno očekuje čvor zvijezda, 991 00:43:11,370 --> 00:43:12,780 pokazivač na čvor. 992 00:43:12,780 --> 00:43:17,360 Pa evo, ja samo mogu napraviti stablo Strelica ulijevo, što će dovesti 993 00:43:17,360 --> 00:43:18,400 ja na drugi čvor. 994 00:43:18,400 --> 00:43:19,480 No, ono što je taj čvor? 995 00:43:19,480 --> 00:43:22,820 >> Pa, prema ovoj izjavi, lijeva je samo pokazivač, tako da je samo 996 00:43:22,820 --> 00:43:27,090 znači da sam prolazi na funkciju pretraživanja drugačija pointer, naime 997 00:43:27,090 --> 00:43:30,750 onaj koji predstavlja Moje lijevo djeteta stabla. 998 00:43:30,750 --> 00:43:36,040 Dakle, u ovom slučaju, kazaljka na 33, ako je ovo je naš uzorak ulazna U međuvremenu, ako je 999 00:43:36,040 --> 00:43:40,740 n je veći od vrijednosti n u trenutni čvor u stablu, onda sam 1000 00:43:40,740 --> 00:43:43,370 ići naprijed i čamac u drugi Smjer i samo reći, ja ne 1001 00:43:43,370 --> 00:43:47,280 znam je li ova vrijednost je n u stablu, ali znam ako je to, to je dolje my 1002 00:43:47,280 --> 00:43:49,090 desnim krakom, da se tako izrazim. 1003 00:43:49,090 --> 00:43:53,120 Pa neka mi rekurzivno poziva traženje, položenog n opet, ali prolaze 1004 00:43:53,120 --> 00:43:54,580 pokazivač na desnoj djeteta. 1005 00:43:54,580 --> 00:44:00,020 >> Drugim riječima, ako sam trenutno na 55 i ja sam u potrazi za 99, znam da 99 1006 00:44:00,020 --> 00:44:04,270 je veći od 55, tako da baš kao što sam poderao telefonskog imenika tjedana, a mi 1007 00:44:04,270 --> 00:44:07,140 otišao desno, slično smo mi ići ovdje. 1008 00:44:07,140 --> 00:44:11,960 I ne znam je li to kod mene prava djeteta, a to nije, 77 je tu, ali 1009 00:44:11,960 --> 00:44:13,210 Znam da je u tom smjeru. 1010 00:44:13,210 --> 00:44:18,770 Dakle, pozivam pretraživanje na mom desnom djeteta, 77, i neka pretragu lik iz 1011 00:44:18,770 --> 00:44:24,950 postoji li 99 u to proizvoljno Primjer je zapravo tamo. 1012 00:44:24,950 --> 00:44:26,900 >> Inače, ono što je konačno slučaj? 1013 00:44:26,900 --> 00:44:28,620 Ako je stablo null je jedan slučaj. 1014 00:44:28,620 --> 00:44:31,890 Ako je n manji od struje čvora Vrijednost je još jedan slučaj. 1015 00:44:31,890 --> 00:44:35,120 Ako je n veći od struje čvora vrijednost je treći slučaj. 1016 00:44:35,120 --> 00:44:38,250 Što je četvrti i posljednji slučaj? 1017 00:44:38,250 --> 00:44:39,480 Mislim da smo od slučajeva, zar ne? 1018 00:44:39,480 --> 00:44:44,690 Bit će da n je trenutni čvor da sam na. 1019 00:44:44,690 --> 00:44:49,640 >> Dakle, ako sam u potrazi za 55 u ovom trenutku u priči, da je grana 1020 00:44:49,640 --> 00:44:51,780 Stablo će se vratiti točno. 1021 00:44:51,780 --> 00:44:55,380 Dakle, ono što je zanimljivo je da smo Zapravo, za razliku od tjedna prošlosti, onda smo 1022 00:44:55,380 --> 00:44:56,740 mjesta imaju dva osnovna scenarija. 1023 00:44:56,740 --> 00:44:58,300 A oni ne moraju biti sve na vrhu. 1024 00:44:58,300 --> 00:45:01,390 Najbolje je osnovni scenarij, jer ako Stablo je nula, nema ništa učiniti. 1025 00:45:01,390 --> 00:45:03,410 Samo se vratili tvrdi kodirani vrijednost false. 1026 00:45:03,410 --> 00:45:07,400 >> Dno grana vrsta default, pri čemu se ako smo provjeriti za 1027 00:45:07,400 --> 00:45:11,550 null, mi smo provjeriti da li bi trebao biti lijevo, ali to ne bi trebalo biti, mi smo 1028 00:45:11,550 --> 00:45:14,640 provjeriti da li bi trebao biti u pravu, ali to Ne bi trebalo biti, jasno da mora biti 1029 00:45:14,640 --> 00:45:15,870 tu gdje smo. 1030 00:45:15,870 --> 00:45:16,780 To je osnovni scenarij. 1031 00:45:16,780 --> 00:45:19,920 Dakle, postoje dvije rekurzivni slučajevi sendviču ovdje u sredini. 1032 00:45:19,920 --> 00:45:21,630 Ali sam mogao pisati to u bilo kojem redoslijedu. 1033 00:45:21,630 --> 00:45:24,520 Samo sam mislio to vrsta, prirodno prvo provjeriti za moguće pogreške, 1034 00:45:24,520 --> 00:45:28,340 zatim provjerite lijevo, a zatim provjerite desno, a zatim Pretpostavljamo da ste na čvoru 1035 00:45:28,340 --> 00:45:30,630 što zapravo tražite. 1036 00:45:30,630 --> 00:45:36,240 >> Pa zašto bi to bilo korisno? 1037 00:45:36,240 --> 00:45:37,910 Tako ispada - 1038 00:45:37,910 --> 00:45:42,110 i neka mi skočiti na zadirkivač Ovdje je to na webu. 1039 00:45:42,110 --> 00:45:44,920 Mi ćemo početi koristiti ne programskog jezika, na prvi pogled, ali 1040 00:45:44,920 --> 00:45:46,030 Markup Language. 1041 00:45:46,030 --> 00:45:48,740 Jezik za bitak onaj koji je slični u duhu programiranje 1042 00:45:48,740 --> 00:45:51,715 jezik, ali to vam ne daje Sposobnost da se izraze logično. 1043 00:45:51,715 --> 00:45:55,070 To samo da daje vam mogućnost da izraziti sebe strukturalno. 1044 00:45:55,070 --> 00:45:57,960 >> Gdje želiš staviti nešto na stranici, web stranica? 1045 00:45:57,960 --> 00:45:59,200 Koje je boje želite to učiniti? 1046 00:45:59,200 --> 00:46:00,950 Što veličinu fonta želite to učiniti? 1047 00:46:00,950 --> 00:46:02,970 Koje riječi ti to zapravo Želite na web stranici? 1048 00:46:02,970 --> 00:46:04,060 Dakle, to je jezik za označavanje. 1049 00:46:04,060 --> 00:46:07,690 No, onda ćemo vrlo brzo uvesti JavaScripta, što je punopravni 1050 00:46:07,690 --> 00:46:08,560 programskom jeziku. 1051 00:46:08,560 --> 00:46:12,530 Vrlo slično sintaktički u izgledu do C, ali to će imati neke 1052 00:46:12,530 --> 00:46:15,200 Lijepo, snažnije, više user friendly značajke. 1053 00:46:15,200 --> 00:46:18,050 >> A jedan od frustracije na ovaj točka u semestru je da ćemo 1054 00:46:18,050 --> 00:46:22,065 Uskoro provedbu Speller u daleko manje linija koda koriste druge jezike 1055 00:46:22,065 --> 00:46:25,580 od C sama dopušta, ali razlog je uskoro ćemo shvatiti. 1056 00:46:25,580 --> 00:46:27,750 To će biti prva takva web stranica. 1057 00:46:27,750 --> 00:46:30,120 To će biti potpuno underwhelming, Prvi smo napraviti. 1058 00:46:30,120 --> 00:46:31,400 Ona će jednostavno reći, Hello World. 1059 00:46:31,400 --> 00:46:34,010 Ali, ako ste nikada nije vidio prije, ovo je HTML, 1060 00:46:34,010 --> 00:46:35,670 HyperText Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> Ako idete na određenu opciju izbornika u najviše bilo kojeg preglednika, na bilo koju web stranicu na 1062 00:46:39,310 --> 00:46:43,160 internet, možete vidjeti HTML da su neki ljudi pisali 1063 00:46:43,160 --> 00:46:44,400 stvorili tu web stranicu. 1064 00:46:44,400 --> 00:46:47,850 I to vjerojatno ne izgleda kao kratki ili kao uredan kao i ovaj. 1065 00:46:47,850 --> 00:46:51,400 No, to će slijediti obrazac njih otvorene zagrade i kose crte i 1066 00:46:51,400 --> 00:46:53,660 slova i potencijalno brojevi. 1067 00:46:53,660 --> 00:46:56,770 >> Mislio sam da bih vam teaser o tome što ćete biti u mogućnosti to učiniti 1068 00:46:56,770 --> 00:46:57,950 nakon uzimanja CS50. 1069 00:46:57,950 --> 00:47:02,620 Pusti me da cs.harvard.edu / opljačkati, Naš vlastiti Rob Bowden je internetska stranica. 1070 00:47:02,620 --> 00:47:06,080 Bio je to za nas. 1071 00:47:06,080 --> 00:47:07,490 Tako ćete uskoro biti u mogućnosti to učiniti. 1072 00:47:07,490 --> 00:47:10,660 I također, ono što ste čuli Jutros - 1073 00:47:10,660 --> 00:47:12,480 ono što ste čuli jutros - 1074 00:47:12,480 --> 00:47:13,780 >> [Hrčak DANCE MUSIC] 1075 00:47:13,780 --> 00:47:15,702 >> - You'll biti u mogućnosti kako bi se to. 1076 00:47:15,702 --> 00:47:16,790 To nas čeka u srijedu. 1077 00:47:16,790 --> 00:47:17,791 Vidjet ćemo se tada. 1078 00:47:17,791 --> 00:47:22,950 >> [Hrčak DANCE MUSIC] 1079 00:47:22,950 --> 00:47:24,300 DAVID Malan: Na sljedećem CS50 - 1080 00:47:24,300 --> 00:47:31,670