1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID MALAN: All right. 3 00:00:12,250 --> 00:00:13,860 Velkommen tilbake til CS50. 4 00:00:13,860 --> 00:00:16,190 Dette er starten på uke 8. 5 00:00:16,190 --> 00:00:21,320 Og husker at oppgavesettet fem endte med litt av en utfordring. 6 00:00:21,320 --> 00:00:25,210 Så forutsatt at du gjenopprettet alle dine undervisning Fellows og CAs fotografier 7 00:00:25,210 --> 00:00:30,480 i card.raw fil, er du kvalifisert til nå finne alle disse menneskene, og 8 00:00:30,480 --> 00:00:34,510 en heldig vinner vil gå hjem med en av disse tingene, spranget bevegelse 9 00:00:34,510 --> 00:00:37,450 enhet som du kan bruke for endelig prosjekter, for eksempel. 10 00:00:37,450 --> 00:00:39,860 >> Dette, hvert år, fører til litt av creepiness. 11 00:00:39,860 --> 00:00:43,480 Og så det jeg trodde jeg ville gjøre er å dele med deg noen av notatene som har 12 00:00:43,480 --> 00:00:47,370 gått frem og tilbake over de ansatte liste over sent. 13 00:00:47,370 --> 00:00:51,110 For eksempel, bare i går kveld, sitat unquote, fra en av de ansatte 14 00:00:51,110 --> 00:00:55,000 medlemmer, "Jeg hadde bare en student knock på døren min for å ta et bilde med meg. 15 00:00:55,000 --> 00:00:59,020 Stalkers, sier jeg deg. "Begynte ganske beskrivende og da vi flyttet 16 00:00:59,020 --> 00:01:02,830 på, en time eller så senere: «Jeg hadde en student venter på meg etter avsnitt 17 00:01:02,830 --> 00:01:06,080 og han hadde alle våre navn og bilder på noen ark. "All right. 18 00:01:06,080 --> 00:01:09,230 Så organisert, men ikke alt det skumle ennå. 19 00:01:09,230 --> 00:01:12,520 >> Da, "jeg var ute av byen denne helgen, og da jeg kom tilbake, var det en i 20 00:01:12,520 --> 00:01:12,630 min 21 00:01:12,630 --> 00:01:16,740 soverom. "[Latter] 22 00:01:16,740 --> 00:01:20,410 DAVID MALAN: Neste sitat fra en stab medlem ", en student kom til huset mitt på 23 00:01:20,410 --> 00:01:25,330 Somerville på 4 AM i morges. "Next ansatte, "Jeg kom til hotellet mitt i San 24 00:01:25,330 --> 00:01:30,016 Francisco og en student var ventet på meg i lobbyen med tre speilreflekskameraer. " 25 00:01:30,016 --> 00:01:31,510 Type kamera. 26 00:01:31,510 --> 00:01:34,980 "Jeg er ikke engang i staben dette semesteret, men en student brøt seg inn i huset mitt denne 27 00:01:34,980 --> 00:01:40,480 morgen og spilte inn hele greia med Google Glass. "Og så til slutt, 28 00:01:40,480 --> 00:01:43,650 "Minst 12 mennesker var ivrig venter for meg da jeg kom ut av min 29 00:01:43,650 --> 00:01:44,800 limo, og da jeg 30 00:01:44,800 --> 00:01:46,970 våknet. "All right. 31 00:01:46,970 --> 00:01:57,690 Så blant bildene, som du kan husker, er denne karen her, som du 32 00:01:57,690 --> 00:02:01,850 kanskje kjenner som Milo Banana, som bor med Lauren Carvalho, vårt hode 33 00:02:01,850 --> 00:02:02,905 undervisning Fellow. 34 00:02:02,905 --> 00:02:05,170 Milo, Milo, kom hit gutt. 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 Mind du, han iført Google Glass, så Vi skal vise deg alt dette etter. 38 00:02:12,230 --> 00:02:16,190 Så dette er Milo hvis du ønsker å ta et bilde med ham etterpå. 39 00:02:16,190 --> 00:02:18,240 Hvis du ønsker å se ut på publikum der. 40 00:02:18,240 --> 00:02:19,430 OK. 41 00:02:19,430 --> 00:02:20,200 Det er bra opptakene. 42 00:02:20,200 --> 00:02:22,556 Vel, Milo Banana. 43 00:02:22,556 --> 00:02:23,941 Oh, ikke gjør det. 44 00:02:23,941 --> 00:02:29,020 >> [Latter] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 Så et ord da på hva som ligger foran, fordi når vi begynner å gå over, 47 00:02:34,550 --> 00:02:38,410 denne uke spesifikt, fra C i en kommandolinje miljø til PHP og 48 00:02:38,410 --> 00:02:42,720 JavaScript og SQL og HTML og CSS i en web-basert miljø, vil vi være 49 00:02:42,720 --> 00:02:44,490 utstyre deg med all den mer kunnskap for 50 00:02:44,490 --> 00:02:46,010 potensielle endelige prosjekter. 51 00:02:46,010 --> 00:02:49,240 Mot dette målet, har banen et tradisjon for å holde seminarer som 52 00:02:49,240 --> 00:02:50,950 er på tangentiale emner til kurset. 53 00:02:50,950 --> 00:02:54,330 Veldig mye relatert til programmering og til app utvikling og så videre, men 54 00:02:54,330 --> 00:02:57,010 ikke nødvendigvis utforsket av kursets egen pensum. 55 00:02:57,010 --> 00:03:00,250 >> Så hvis du kan være interessert i en eller flere av årets seminarer, 56 00:03:00,250 --> 00:03:02,530 registrer deg på cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Det er eldre seminarer på cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 Og på vaktliste så langt i år er Amazing Web Apps med Ruby on 59 00:03:10,620 --> 00:03:13,580 Rails, som er et alternativ språk til PHP. 60 00:03:13,580 --> 00:03:14,900 Datalingvistikk. 61 00:03:14,900 --> 00:03:18,710 Innføring i iOS, som er plattform som brukes for iPhone og 62 00:03:18,710 --> 00:03:19,850 iPad utvikling. 63 00:03:19,850 --> 00:03:22,890 JavaScript for Web Apps, vil vi dekke det, men i dette seminaret vil du gå 64 00:03:22,890 --> 00:03:24,070 i mer detalj. 65 00:03:24,070 --> 00:03:27,390 >> Leap Motion, så vi vil faktisk ha noen av våre venner fra Leap Motion, 66 00:03:27,390 --> 00:03:29,160 selskapet selv, bli med oss. 67 00:03:29,160 --> 00:03:31,800 I morgen, faktisk, for å gi en hands-on seminar, hvis 68 00:03:31,800 --> 00:03:33,320 av interesse for deg. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, en alternativ teknikk for bruker JavaScript ikke i en nettleser, 70 00:03:38,770 --> 00:03:39,970 men på en server. 71 00:03:39,970 --> 00:03:42,110 Node.js, som er veldig mye Av den grunn også. 72 00:03:42,110 --> 00:03:43,650 Slank Android Design. 73 00:03:43,650 --> 00:03:46,990 Android er et svært populært alternativ til iOS og Windows Phone 74 00:03:46,990 --> 00:03:48,790 og andre mobile plattformer. 75 00:03:48,790 --> 00:03:51,180 Og Web Security Active Defense. 76 00:03:51,180 --> 00:03:54,590 >> Så faktisk, hvis du ønsker å engasjere seg i dette, la meg 77 00:03:54,590 --> 00:03:55,840 gjøre oppmerksom på dette. 78 00:03:55,840 --> 00:03:57,790 Vi er veldig glad for å si at våre venner på Leap 79 00:03:57,790 --> 00:03:59,140 Motion, som er en oppstart - 80 00:03:59,140 --> 00:04:01,300 denne enheten egentlig bare kom ut for noen måneder siden - 81 00:04:01,300 --> 00:04:05,960 har velvillig donert 30 slike enheter til klassen for så mange studenter, hvis 82 00:04:05,960 --> 00:04:08,670 du ønsker å låne maskinvaren mot semesters slutt og bruke den til 83 00:04:08,670 --> 00:04:10,390 en faktisk endelige prosjektet. 84 00:04:10,390 --> 00:04:11,890 De støtter en rekke språk. 85 00:04:11,890 --> 00:04:16,040 Ingen av dem C, ingen av dem PHP, så realisere ett eller flere av disse seminarene 86 00:04:16,040 --> 00:04:16,899 kan vise interesse. 87 00:04:16,899 --> 00:04:19,730 Og alle av dem vil bli filmet i tilfelle at du ikke er i stand 88 00:04:19,730 --> 00:04:21,380 å møte personlig. 89 00:04:21,380 --> 00:04:25,000 Planen bli annonsert via e-post som vi stivne rom. 90 00:04:25,000 --> 00:04:28,460 >> Og til slutt, hvis du går til projects.cs.50.net, er dette en nettside 91 00:04:28,460 --> 00:04:31,450 vi opprettholder hvert år at vi inviterer folk fra lokalsamfunnet, fakultet, 92 00:04:31,450 --> 00:04:36,420 avdelinger, ansatte og begge i en utenfor av CS50 til 93 00:04:36,420 --> 00:04:37,730 foreslå prosjektideer. 94 00:04:37,730 --> 00:04:39,050 Ting av interesse for studentgrupper. 95 00:04:39,050 --> 00:04:40,600 Ting av interesse for avdelinger. 96 00:04:40,600 --> 00:04:43,990 Så snur det hvis du sliter med usikkerhet med hensyn til hva du 97 00:04:43,990 --> 00:04:46,700 selv ønsker å takle. 98 00:04:46,700 --> 00:04:51,760 >> Så sist gang vi innførte en kanskje mer kompleks datastruktur enn vi hadde 99 00:04:51,760 --> 00:04:53,300 sett i uker tidligere. 100 00:04:53,300 --> 00:04:56,550 Vi hadde brukt matriser pen lykkelig som en nyttig hvis 101 00:04:56,550 --> 00:04:58,160 forenklede datastruktur. 102 00:04:58,160 --> 00:05:00,570 Da vi innførte disse, som selvfølgelig er knyttet lister. 103 00:05:00,570 --> 00:05:05,470 Og hva var en av motivasjonene for innføre dette datastruktur? 104 00:05:05,470 --> 00:05:06,930 Yeah? 105 00:05:06,930 --> 00:05:07,250 Hva er det? 106 00:05:07,250 --> 00:05:08,080 >> PUBLIKUM: Dynamisk størrelse. 107 00:05:08,080 --> 00:05:09,040 >> DAVID MALAN: Dynamisk størrelse. 108 00:05:09,040 --> 00:05:11,890 Så mens i array, må du vet størrelsen på forhånd når 109 00:05:11,890 --> 00:05:12,740 du fordele den. 110 00:05:12,740 --> 00:05:14,380 I lenket liste, trenger du ikke må vite det. 111 00:05:14,380 --> 00:05:17,610 Du kan bare malloc, eller mer generelt, bevilge ytterligere 112 00:05:17,610 --> 00:05:20,720 node, så å si, når du vil sette inn flere data. 113 00:05:20,720 --> 00:05:22,670 Og node har ingen forhåndsbestemt mening. 114 00:05:22,670 --> 00:05:25,580 Det er bare en fellesbetegnelse som beskriver en slags beholder som vi er 115 00:05:25,580 --> 00:05:29,610 ved hjelp av i vår datastruktur for å lagre enkelte element av interesse, som i denne 116 00:05:29,610 --> 00:05:31,750 tilfelle skje for å være heltall. 117 00:05:31,750 --> 00:05:33,160 >> Men det er alltid en avveining. 118 00:05:33,160 --> 00:05:38,070 Så vi får dynamiske størrelser av data struktur, men hvilken pris vi betaler? 119 00:05:38,070 --> 00:05:40,040 Hva er ulempen med koblede lister? 120 00:05:40,040 --> 00:05:41,006 Yeah? 121 00:05:41,006 --> 00:05:41,980 >> PUBLIKUM: Krever mer minne. 122 00:05:41,980 --> 00:05:44,240 >> DAVID MALAN: Det krever mer minne, hvordan akkurat? 123 00:05:44,240 --> 00:05:46,440 >> PUBLIKUM: [uhørlig]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID MALAN: Nettopp. 125 00:05:47,050 --> 00:05:50,460 Så nå har vi pekere tar opp ekstra minne som vi tidligere 126 00:05:50,460 --> 00:05:53,040 trenger ikke, fordi den fordel av en matrise, er selvfølgelig at 127 00:05:53,040 --> 00:05:54,860 alt er sammenhengende, tilbake til tilbake til ryggen, som 128 00:05:54,860 --> 00:05:56,380 gir deg direkte tilgang. 129 00:05:56,380 --> 00:06:00,710 Fordi bare ved å bruke hakeparentes notasjon, eller mer teknisk pekeren 130 00:06:00,710 --> 00:06:03,580 aritmetikk, veldig enkel addisjon, kan du få tilgang til alle 131 00:06:03,580 --> 00:06:05,700 elementer i konstant tid. 132 00:06:05,700 --> 00:06:08,975 Og faktisk, er den slags antyde en annen pris som vi betaler med en 133 00:06:08,975 --> 00:06:09,760 lenket liste. 134 00:06:09,760 --> 00:06:13,890 >> Hva skjer med kjøretiden noe som Søk, hvis jeg vil 135 00:06:13,890 --> 00:06:17,270 finne noen verdi og inne av en lenket liste? 136 00:06:17,270 --> 00:06:20,290 Hva min kjøretid bli? 137 00:06:20,290 --> 00:06:21,560 Big O n. 138 00:06:21,560 --> 00:06:24,060 Hvis det er sortert til? 139 00:06:24,060 --> 00:06:25,440 Hva om datastruktur er sortert? 140 00:06:25,440 --> 00:06:28,640 Kan jeg gjøre det bedre enn store O av n for å søke? 141 00:06:28,640 --> 00:06:31,700 Nei, fordi i verste fall kan det meget vel være sortert, men antallet 142 00:06:31,700 --> 00:06:32,950 du leter etter kan være stor. 143 00:06:32,950 --> 00:06:35,370 Det kan være det nummer 100, hvilken kan skje for å være alt 144 00:06:35,370 --> 00:06:36,410 den måte på slutten. 145 00:06:36,410 --> 00:06:39,950 Og fordi du bare kan få tilgang til en koblet listen i denne implementeringen ved 146 00:06:39,950 --> 00:06:42,690 måte av sin første noden, er du fortsatt slags ute av lykken. 147 00:06:42,690 --> 00:06:47,450 Du må bla gjennom hele greia fra først til sist for å finne 148 00:06:47,450 --> 00:06:49,150 den store verdien som 100. 149 00:06:49,150 --> 00:06:51,350 Eller for å fastslå om det er ikke engang der. 150 00:06:51,350 --> 00:06:55,960 >> Så vi kan ikke gjøre hva algoritmen i en data struktur som ser ut som dette? 151 00:06:55,960 --> 00:06:59,460 Vi kan ikke gjøre binære søk, fordi binære søk krevde at vi hadde 152 00:06:59,460 --> 00:07:00,740 random access. 153 00:07:00,740 --> 00:07:04,500 Vi kunne bare hoppe fra sted til sted uten å måtte følge 154 00:07:04,500 --> 00:07:07,080 disse brødsmuler i form av alle disse pekerne. 155 00:07:07,080 --> 00:07:08,300 >> Nå, hvordan vi gjennomføre dette? 156 00:07:08,300 --> 00:07:12,830 Vel, hvis vi går til skjermen her, hvis Vi kan raskt reimplement disse dataene 157 00:07:12,830 --> 00:07:13,440 struktur - 158 00:07:13,440 --> 00:07:15,670 min håndskrift er ikke alle som flott her, men vi skal prøve. 159 00:07:15,670 --> 00:07:22,030 Så typedef struct, og hva gjorde jeg ønsker å kalle denne tingen her oppe? 160 00:07:22,030 --> 00:07:22,960 Node. 161 00:07:22,960 --> 00:07:24,580 Så jeg skal få oss i gang. 162 00:07:24,580 --> 00:07:27,860 Og nå, hva må være inne i datastrukturen for det enkeltvis 163 00:07:27,860 --> 00:07:28,430 lenket liste? 164 00:07:28,430 --> 00:07:29,950 Hvor mange felt? 165 00:07:29,950 --> 00:07:30,450 >> Så to. 166 00:07:30,450 --> 00:07:31,570 Er ganske enkelt. 167 00:07:31,570 --> 00:07:33,050 Så int n. 168 00:07:33,050 --> 00:07:35,930 Og vi kan kalle n noe vi ønsker, men det bør være en int hvis vi er 169 00:07:35,930 --> 00:07:37,660 implementere en lenket liste for ints. 170 00:07:37,660 --> 00:07:41,920 Og nå hva gjør andre Feltet må være? 171 00:07:41,920 --> 00:07:43,460 Struct node *. 172 00:07:43,460 --> 00:07:50,570 Så hvis jeg gjør struct node *, og da jeg kan kalle dette også hva jeg vil, 173 00:07:50,570 --> 00:07:53,510 men bare for å være klart jeg ringer det neste, som vi har gjort. 174 00:07:53,510 --> 00:07:55,270 Og så skal jeg lukke mine klammeparentes. 175 00:07:55,270 --> 00:08:00,700 >> Og nå, som sist, Jeg satte node ned her. 176 00:08:00,700 --> 00:08:03,830 Men hvis jeg erklære dette er som en node, hvorfor jeg gidder å være så 177 00:08:03,830 --> 00:08:07,320 ordrik her i å erklære struct node * ved siden av, i motsetning 178 00:08:07,320 --> 00:08:09,210 å bare node * neste? 179 00:08:09,210 --> 00:08:09,904 Yeah? 180 00:08:09,904 --> 00:08:12,810 >> PUBLIKUM: [uhørlig]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID MALAN: Nettopp. 182 00:08:14,050 --> 00:08:14,530 Nettopp. 183 00:08:14,530 --> 00:08:18,320 Fordi C virkelig tar deg bokstavelig og bare ser definisjonen av node 184 00:08:18,320 --> 00:08:21,230 helt ned her, kan du ikke referere til det her oppe. 185 00:08:21,230 --> 00:08:24,760 Så vi har denne typen preemptive erklæring her, som er riktignok 186 00:08:24,760 --> 00:08:25,390 mer ordrik. 187 00:08:25,390 --> 00:08:27,810 Struct node, som betyr Vi kan nå få tilgang til det 188 00:08:27,810 --> 00:08:29,760 innsiden av datastrukturen. 189 00:08:29,760 --> 00:08:33,370 >> Og som en side, fordi dette er bli litt mer subjektiv nå, 190 00:08:33,370 --> 00:08:36,230 stjernen kan teknisk gå her, det kan gå her, kan det 191 00:08:36,230 --> 00:08:37,179 selv gå i midten. 192 00:08:37,179 --> 00:08:39,890 Vi har vedtatt, i stilen guide for kurset, konvensjonen om å sette 193 00:08:39,890 --> 00:08:42,299 stjernen rett ved siden av data type, som i dette tilfellet 194 00:08:42,299 --> 00:08:43,460 ville være struct node. 195 00:08:43,460 --> 00:08:46,620 Men innser i en rekke lærebøker og online referanser, kanskje du faktisk 196 00:08:46,620 --> 00:08:48,450 ser det på den andre siden. 197 00:08:48,450 --> 00:08:52,200 Men bare innse at begge faktisk vil fungere, og du bør rett og slett være 198 00:08:52,200 --> 00:08:52,970 konsekvent. 199 00:08:52,970 --> 00:08:53,580 >> OK. 200 00:08:53,580 --> 00:08:55,630 Så det var vår erklæring av struct node. 201 00:08:55,630 --> 00:08:59,430 Men da vi begynte å gjøre mer sofistikerte ting. 202 00:08:59,430 --> 00:09:03,410 For eksempel, har vi besluttet å innføre noe som en hash table. 203 00:09:03,410 --> 00:09:08,160 Så her er en hash table av størrelse n, indeksert fra 0 øverst til venstre for å n 204 00:09:08,160 --> 00:09:09,690 minus 1 på bunnen igjen. 205 00:09:09,690 --> 00:09:11,640 Dette kan være en hash tabell for noe. 206 00:09:11,640 --> 00:09:15,340 Men hva slags ting vi snakke om å bruke en hash tabell for? 207 00:09:15,340 --> 00:09:18,370 Lagring av hva? 208 00:09:18,370 --> 00:09:18,800 >> Navn. 209 00:09:18,800 --> 00:09:20,870 Vi kunne gjøre navn som vi gjorde forrige gang. 210 00:09:20,870 --> 00:09:22,200 Og egentlig, kan du lagre noe. 211 00:09:22,200 --> 00:09:24,640 Og vi vil se dette igjen i PHP og JavaScript. 212 00:09:24,640 --> 00:09:28,550 En hash table er en fin form for Swiss Army kniv som lar deg lagre 213 00:09:28,550 --> 00:09:33,690 ganske mye hva du vil innsiden av det ved å knytte taster med verdier. 214 00:09:33,690 --> 00:09:34,770 Taster med verdier. 215 00:09:34,770 --> 00:09:37,800 >> Nå i denne enkle saken, vår tastene er bare tall. 216 00:09:37,800 --> 00:09:40,380 Vi implementere en hash tabell som en matrise. 217 00:09:40,380 --> 00:09:43,500 Og så tastene er 0, 1, 2 og så videre. 218 00:09:43,500 --> 00:09:47,200 Og så vi, som mennesker, besluttet sist uke at du vet hva, hvis vi er 219 00:09:47,200 --> 00:09:50,410 kommer til å lagre navn, la oss bare vilkårlig, men ganske rimelig, 220 00:09:50,410 --> 00:09:54,680 anta at Alice, en A navn, vil bare bli indeksert i 0. 221 00:09:54,680 --> 00:09:58,030 Og Bob, en B navn, vil bli indeksert inn i en, og så videre. 222 00:09:58,030 --> 00:10:02,490 Så vi hadde en mapping mellom innganger, som er strenger, og hash 223 00:10:02,490 --> 00:10:04,560 steder, som er tall. 224 00:10:04,560 --> 00:10:07,740 >> For at prosessen er generelt kjent som en hash-funksjon, og du kan virkelig 225 00:10:07,740 --> 00:10:09,130 implementere det i koden. 226 00:10:09,130 --> 00:10:12,080 Hvis jeg ønsket å gjennomføre en hash-funksjon som gjør akkurat det vi 227 00:10:12,080 --> 00:10:17,070 bare beskrevet fra forrige gang, kanskje jeg erklære en funksjon som tar, som 228 00:10:17,070 --> 00:10:18,330 inngang for eksempel - 229 00:10:18,330 --> 00:10:22,190 og la oss gjøre dette på denne skjermen over her. 230 00:10:22,190 --> 00:10:26,180 Hvis jeg ønsket å gjennomføre en hash funksjon, kan jeg si 231 00:10:26,180 --> 00:10:27,410 noe sånt som dette. 232 00:10:27,410 --> 00:10:29,030 >> Det kommer til å returnere en int. 233 00:10:29,030 --> 00:10:33,600 Det kommer til å bli kalt hasj, og det er kommer til å godta som et argument en 234 00:10:33,600 --> 00:10:38,920 string, eller vi kan være mer riktig nå, og si char *, vi kaller det er. 235 00:10:38,920 --> 00:10:43,840 Og så all denne funksjonen har å gjøre, slutt, er returnere en int. 236 00:10:43,840 --> 00:10:45,990 Nå, hvordan det som kanskje ikke være så tydelige. 237 00:10:45,990 --> 00:10:49,510 Jeg kommer til å gjennomføre dette uten form for feilsjekking akkurat nå. 238 00:10:49,510 --> 00:10:55,740 Jeg skal bare blindt si, tilbake hva er på s brakett 0, minus, 239 00:10:55,740 --> 00:10:58,850 la oss si, kapital semikolon. 240 00:10:58,850 --> 00:10:59,960 >> Helt ødelagt. 241 00:10:59,960 --> 00:11:02,620 Det er ikke perfekt fordi en, hva hvis s er null? 242 00:11:02,620 --> 00:11:04,000 Dårlige ting kommer til å skje. 243 00:11:04,000 --> 00:11:07,940 To, hva om den første bokstaven i dette Navnet er ikke en stor bokstav? 244 00:11:07,940 --> 00:11:09,860 Som ikke kommer til å snu godt ut heller. 245 00:11:09,860 --> 00:11:11,970 Det kan være en liten bokstav eller ikke en bokstav i det hele tatt. 246 00:11:11,970 --> 00:11:15,520 Så helt rom for forbedring her, men dette er den grunnleggende ideen. 247 00:11:15,520 --> 00:11:19,010 >> Hva vi beskrev i forrige uke verbalt som bare en prosess for å kartlegge Alice til 248 00:11:19,010 --> 00:11:23,360 0 til 1 og Bob kan uttrykkes sikkert mer formulaically som en C 249 00:11:23,360 --> 00:11:24,320 fungere her. 250 00:11:24,320 --> 00:11:28,630 Ringte igjen hasj, tar en streng som input, og deretter gjør liksom noe 251 00:11:28,630 --> 00:11:31,020 med den inngang for å produsere en utgang. 252 00:11:31,020 --> 00:11:34,130 Ikke ulikt vår black box beskrivelse at vi har lenge gjort. 253 00:11:34,130 --> 00:11:36,550 Jeg vet ikke hvordan dette kan være arbeider under panseret. 254 00:11:36,550 --> 00:11:40,120 >> For oppgavesettet 6, en av utfordringene er for deg å bestemme hva 255 00:11:40,120 --> 00:11:41,920 vil hash-funksjon være? 256 00:11:41,920 --> 00:11:45,760 Hva kommer til å være inne i det svarte boks, og antagelig vil det være en 257 00:11:45,760 --> 00:11:50,380 litt mer interessant enn dette, og definitivt mer utsatt for feil 258 00:11:50,380 --> 00:11:53,180 sjekker enn dette gjennomføring. 259 00:11:53,180 --> 00:11:54,580 >> Men problemer kan oppstå, ikke sant? 260 00:11:54,580 --> 00:11:57,760 Hvis vi har en datastruktur slik som denne en, hva som er et av problemene 261 00:11:57,760 --> 00:12:01,600 du kan kjøre inn over tid som du setter inn flere og flere navnene inn i 262 00:12:01,600 --> 00:12:02,880 hash table? 263 00:12:02,880 --> 00:12:04,630 Du får kollisjoner, ikke sant? 264 00:12:04,630 --> 00:12:07,560 Hva hvis du har Alice og Aron, to personer som har navn som skjedde 265 00:12:07,560 --> 00:12:08,190 å starte med A? 266 00:12:08,190 --> 00:12:11,660 Det må da spørre hvor du sette den andre et slikt navn? 267 00:12:11,660 --> 00:12:15,050 >> Vel, kanskje du naivt bare sette den hvor Bob hører hjemme, men da Bob er 268 00:12:15,050 --> 00:12:17,300 slags skrudd hvis du prøver å sette navnet hans neste og 269 00:12:17,300 --> 00:12:18,240 det er ikke rom for ham. 270 00:12:18,240 --> 00:12:21,400 Så du kan sette Bob der Charlie er, og du kan forestille deg dette svært raskt 271 00:12:21,400 --> 00:12:23,020 devolving inn litt av et rot. 272 00:12:23,020 --> 00:12:25,600 Noe lineær i slutten, hvor du bare å søke på hele greia 273 00:12:25,600 --> 00:12:28,190 på jakt etter Alice eller Bob eller Aaron eller Charlie. 274 00:12:28,190 --> 00:12:33,230 >> Så i stedet vi foreslo, i stedet for bare lineært sondering for åpne plasser 275 00:12:33,230 --> 00:12:36,450 og plopping navnene der, vi foreslått en mer avansert tilnærming. 276 00:12:36,450 --> 00:12:41,740 En hash table implementert fortsatt med en rekke indekser, men dataene type 277 00:12:41,740 --> 00:12:44,500 disse indeksene nå var pekere. 278 00:12:44,500 --> 00:12:47,360 Pekere til hva? 279 00:12:47,360 --> 00:12:48,730 Pekere til lenkede lister. 280 00:12:48,730 --> 00:12:53,330 >> Fordi huske at en lenket liste er egentlig bare en peker til en node, og 281 00:12:53,330 --> 00:12:57,110 noden har en neste felt, og at noden har en neste felt, og så videre. 282 00:12:57,110 --> 00:13:00,690 Så du kan nå tenke på dette array på den venstre side av en hash tabell som 283 00:13:00,690 --> 00:13:01,820 fører til en lenket liste. 284 00:13:01,820 --> 00:13:07,000 Fordelen med noe som er hvis du får en kollisjon mellom Alice og Aron, 285 00:13:07,000 --> 00:13:09,300 hva gjør du med andre slik person? 286 00:13:09,300 --> 00:13:14,150 Du må bare legge ham eller henne til slutten av eller til og med begynnelsen 287 00:13:14,150 --> 00:13:15,490 av at lenket liste. 288 00:13:15,490 --> 00:13:17,340 >> Og faktisk, la oss bare noodle gjennom at bare et sekund. 289 00:13:17,340 --> 00:13:18,640 Hvor ville gjøre det mest fornuftig? 290 00:13:18,640 --> 00:13:22,060 Hvis jeg setter Alice og hun ender opp på den første plasseringen, så jeg prøver å 291 00:13:22,060 --> 00:13:25,310 sette Aaron navn, og det er åpenbart en kollisjon, skal jeg sette 292 00:13:25,310 --> 00:13:27,400 seg ved begynnelsen av lenket liste? 293 00:13:27,400 --> 00:13:30,944 Det er på den første plasseringen, eller på slutten? 294 00:13:30,944 --> 00:13:31,440 >> PUBLIKUM: [uhørlig]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID MALAN: OK. 296 00:13:31,990 --> 00:13:32,490 Jeg hørte begynnelsen. 297 00:13:32,490 --> 00:13:33,903 Hvorfor i begynnelsen? 298 00:13:33,903 --> 00:13:34,750 >> PUBLIKUM: [uhørlig]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID MALAN: OK. 300 00:13:34,940 --> 00:13:36,520 Det er alfabetisk, så det er fint. 301 00:13:36,520 --> 00:13:37,330 Det er en god egenskap. 302 00:13:37,330 --> 00:13:39,335 Det vil spare meg litt tid potensielt. 303 00:13:39,335 --> 00:13:43,290 Det vil ikke la meg gjøre binære søk, men jeg kan i det minste være i stand til å bryte ut 304 00:13:43,290 --> 00:13:47,340 av en loop hvis jeg skjønner, vel, jeg er måten fortiden var Aaron ville være i denne 305 00:13:47,340 --> 00:13:48,310 sortert lenket liste. 306 00:13:48,310 --> 00:13:50,360 Jeg trenger ikke å kaste bort min tid på å lete hele veien til enden. 307 00:13:50,360 --> 00:13:51,530 Så det er rimelig. 308 00:13:51,530 --> 00:13:54,710 Hvorfor ellers vil du kanskje sette inn den kolliderer navnet på 309 00:13:54,710 --> 00:13:56,660 begynnelsen av listen? 310 00:13:56,660 --> 00:13:57,397 Hva er det? 311 00:13:57,397 --> 00:13:58,680 >> PUBLIKUM: [uhørlig]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID MALAN: Det kan ta lang tid for å komme til enden av listen. 313 00:14:00,820 --> 00:14:02,490 Og faktisk, lengre og lengre. 314 00:14:02,490 --> 00:14:04,920 Jo flere navn du setter det starter med A, jo lenger at 315 00:14:04,920 --> 00:14:06,280 kjeden kommer til å få. 316 00:14:06,280 --> 00:14:07,890 Jo lenger som knyttet Listen kommer til å få. 317 00:14:07,890 --> 00:14:09,420 Så du er egentlig bare kaste bort tiden din. 318 00:14:09,420 --> 00:14:14,070 Kanskje du er bedre å opprettholde konstant tidspunktet for innsetting, av en stor O, 319 00:14:14,070 --> 00:14:18,470 ved alltid å sette kollidere navnet på begynnelsen av lenket liste, 320 00:14:18,470 --> 00:14:21,230 og ikke bekymre seg så mye om sortering. 321 00:14:21,230 --> 00:14:22,600 >> Hva er det beste svaret? 322 00:14:22,600 --> 00:14:23,320 Det er uklart. 323 00:14:23,320 --> 00:14:26,140 Den slags avhenger av hva fordelingen er, hva mønsteret er 324 00:14:26,140 --> 00:14:27,850 av navnene du setter inn. 325 00:14:27,850 --> 00:14:29,430 Det er ikke nødvendigvis et opplagt svar. 326 00:14:29,430 --> 00:14:33,100 Men her, igjen, er et design anledning. 327 00:14:33,100 --> 00:14:37,220 >> Så vi deretter så på denne tingen, som er egentlig den andre store mulighet 328 00:14:37,220 --> 00:14:38,180 for p-set seks. 329 00:14:38,180 --> 00:14:41,770 Og skjønner, hvis du ikke allerede har gjort, Zamyla dykk inn begge disse, hash 330 00:14:41,770 --> 00:14:43,260 bord og prøver, i mer detalj. 331 00:14:43,260 --> 00:14:45,630 Og videogjennomgang er innebygd i p-set spec. 332 00:14:45,630 --> 00:14:46,590 Dette var en trie - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. Og det interessante dette var at kjøretiden 334 00:14:51,670 --> 00:14:59,510 å søke etter et navn, som Maxwell siste gang, var stor O av hva? 335 00:14:59,510 --> 00:15:01,040 Hva er det? 336 00:15:01,040 --> 00:15:01,920 >> PUBLIKUM: Antall bokstaver. 337 00:15:01,920 --> 00:15:02,550 >> DAVID MALAN: Antall brev. 338 00:15:02,550 --> 00:15:03,210 Jeg hørte to ting. 339 00:15:03,210 --> 00:15:04,630 Antall bokstaver og konstant tid. 340 00:15:04,630 --> 00:15:05,540 Så la oss gå med det første. 341 00:15:05,540 --> 00:15:06,410 Det antall bokstaver. 342 00:15:06,410 --> 00:15:10,195 Vel, dette er data struktur, husker, liker et tre, et familietre, hver av 343 00:15:10,195 --> 00:15:12,860 som noder består av arrays. 344 00:15:12,860 --> 00:15:16,300 Og disse arrays er pekere til andre slike noder, eller andre slike 345 00:15:16,300 --> 00:15:17,670 arrays i treet. 346 00:15:17,670 --> 00:15:22,890 >> Så hvis vi ønsket å deretter bestemme enten Maxwell er her, kan jeg gå 347 00:15:22,890 --> 00:15:26,890 til den første array, helt på toppen av treet, den såkalte rot, oppå 348 00:15:26,890 --> 00:15:30,521 den trie, og følg deretter m pekeren, deretter en peker, deretter x, 349 00:15:30,521 --> 00:15:31,710 w, e, l, l. 350 00:15:31,710 --> 00:15:34,910 Og så når jeg ser noen spesiell symbol, betegnes her som en trekant. 351 00:15:34,910 --> 00:15:38,480 I koden ser du foreslår vi at du implementert som en bool, bare si ja 352 00:15:38,480 --> 00:15:40,540 eller nei, stopper et ord her. 353 00:15:40,540 --> 00:15:45,270 >> Vel, når vi har gått til M-A-X-W-E-L-L, føles som sju, kanskje 354 00:15:45,270 --> 00:15:48,910 åtte hvis vi går en forbi den, åtte fremgangsmåten for å finne Maxwell. 355 00:15:48,910 --> 00:15:53,050 Eller la oss kalle det K. Men husker sist tid, hevdet jeg at hvis det er 356 00:15:53,050 --> 00:15:57,540 realistisk en maksimal lengde på en ord, som 40-some-odd tegn, en 357 00:15:57,540 --> 00:16:00,810 Maksimal lengde innebærer en konstant verdi. 358 00:16:00,810 --> 00:16:05,770 Så egentlig, ja, det er teknisk big O 8 eller 7, eller virkelig store O av K. Men 359 00:16:05,770 --> 00:16:09,420 hvis det er et endelig tak på hva K kan være, er det en konstant. 360 00:16:09,420 --> 00:16:12,080 Og så det er big O av en på slutten av dagen. 361 00:16:12,080 --> 00:16:13,040 >> Ikke i den virkelige verden. 362 00:16:13,040 --> 00:16:15,960 Ikke når du faktisk begynne å se din klokke som programmet kjører. 363 00:16:15,960 --> 00:16:20,690 Det er absolutt kommer til å være litt tregere enn virkelig konstant 364 00:16:20,690 --> 00:16:21,840 tid med ett trinn. 365 00:16:21,840 --> 00:16:25,540 Det kommer til å være syv eller åtte trinn, men likevel det er mye, mye bedre 366 00:16:25,540 --> 00:16:30,080 enn en algoritme som big O n som avhenger av størrelsen på hva som er i 367 00:16:30,080 --> 00:16:31,220 datastruktur. 368 00:16:31,220 --> 00:16:34,970 >> Legg merke oppsiden her er at vi kan sette inn en million flere navn i denne 369 00:16:34,970 --> 00:16:38,170 datastruktur, men hvor mange flere trinn går det å ta oss til å finne 370 00:16:38,170 --> 00:16:40,480 Maxwell i så fall? 371 00:16:40,480 --> 00:16:40,780 Ingen. 372 00:16:40,780 --> 00:16:41,820 Han er upåvirket. 373 00:16:41,820 --> 00:16:45,480 Og til dags dato, tror jeg ikke vi har sett et eksempel på en datastruktur eller et 374 00:16:45,480 --> 00:16:48,560 algoritme som var helt upåvirket av ytre 375 00:16:48,560 --> 00:16:50,040 atferd sånn. 376 00:16:50,040 --> 00:16:51,160 Men dette kan ikke være fantastisk. 377 00:16:51,160 --> 00:16:52,900 Dette kan ikke være den eneste løsningen for P-set 378 00:16:52,900 --> 00:16:53,570 >> Og det er ikke. 379 00:16:53,570 --> 00:16:55,980 Dette er ikke nødvendigvis de data struktur bør du bevege til, 380 00:16:55,980 --> 00:16:58,220 fordi som hash tabeller, byttehandel. 381 00:16:58,220 --> 00:17:00,500 Hva er prisen du betaler her? 382 00:17:00,500 --> 00:17:00,940 Minne. 383 00:17:00,940 --> 00:17:02,890 Jeg mener, dette er en fryktelig mye minne. 384 00:17:02,890 --> 00:17:05,569 Og du kan ikke helt se det her fordi forfatteren av dette bildet 385 00:17:05,569 --> 00:17:09,420 åpenbart avkortet alle matriser og vi ikke ser mye av A og 386 00:17:09,420 --> 00:17:12,700 B og C-er og Q og Y og Z er i disse arrays. 387 00:17:12,700 --> 00:17:13,630 Men de er der. 388 00:17:13,630 --> 00:17:17,660 >> Hver av disse noder er en hel rekke av enkelte 26 eller flere byte, hver av 389 00:17:17,660 --> 00:17:19,170 som representerer en bokstav. 390 00:17:19,170 --> 00:17:22,920 27 i vårt tilfelle, slik at vi kan støtte apostrofer i oppgavesettet. 391 00:17:22,920 --> 00:17:27,030 Så dette datastruktur er virkelig, virkelig tett og bred. 392 00:17:27,030 --> 00:17:30,880 Og det alene kan ende opp med å bremse ting ned, eller i det minste koste deg 393 00:17:30,880 --> 00:17:32,240 mye mer plass. 394 00:17:32,240 --> 00:17:34,020 Men igjen, kan vi trekke sammenligninger her. 395 00:17:34,020 --> 00:17:39,190 >> Huske en stund tilbake, har vi oppnådd mye mer spennende kjøretid i sortering 396 00:17:39,190 --> 00:17:42,880 når vi bruker merge slag, men prisen vi betalte for å oppnå n log n for flettingen 397 00:17:42,880 --> 00:17:46,930 sortere nødvendig at vi bruker mer hva ressurs? 398 00:17:46,930 --> 00:17:47,690 Mer plass. 399 00:17:47,690 --> 00:17:50,530 Vi trengte en sekundær array til kopiere folk inn, akkurat som 400 00:17:50,530 --> 00:17:51,620 vi gjorde her på scenen. 401 00:17:51,620 --> 00:17:55,880 Så igjen, ingen klare vinnere, men bare subjektive utforming 402 00:17:55,880 --> 00:17:57,710 beslutninger skal gjøres. 403 00:17:57,710 --> 00:17:58,060 >> OK. 404 00:17:58,060 --> 00:17:59,130 Så hva med denne? 405 00:17:59,130 --> 00:18:02,050 Noen som gjenkjenner som D-Hall? 406 00:18:02,050 --> 00:18:02,440 OK. 407 00:18:02,440 --> 00:18:03,170 Så tre av oss gjør. 408 00:18:03,170 --> 00:18:03,750 Mather House. 409 00:18:03,750 --> 00:18:05,070 Så dette er for Mather spisesalen. 410 00:18:05,070 --> 00:18:09,650 Jeg vedder alle spisesaler har stabler av skuffer som dette. 411 00:18:09,650 --> 00:18:11,950 Og dette er faktisk representative av noe vi har 412 00:18:11,950 --> 00:18:13,050 åpenbart sett allerede. 413 00:18:13,050 --> 00:18:14,850 Vi kalte det bokstavelig talt en stabel. 414 00:18:14,850 --> 00:18:18,970 Og bunken, i form av din datamaskinens minne, er hvor data går 415 00:18:18,970 --> 00:18:20,460 mens funksjoner blir kalt. 416 00:18:20,460 --> 00:18:23,410 >> For eksempel, hva slags ting går på stabelen med hensyn til 417 00:18:23,410 --> 00:18:27,420 minne layout vi har diskutert i uker tidligere? 418 00:18:27,420 --> 00:18:28,736 Hva er det? 419 00:18:28,736 --> 00:18:29,670 >> PUBLIKUM: Samtaler til funksjoner. 420 00:18:29,670 --> 00:18:30,260 >> DAVID MALAN: Jeg beklager. 421 00:18:30,260 --> 00:18:31,210 >> PUBLIKUM: Samtaler til funksjoner. 422 00:18:31,210 --> 00:18:33,590 >> DAVID MALAN: Anrop til funksjoner, men spesifikt, hva som er inni hver av 423 00:18:33,590 --> 00:18:35,340 disse rammer? 424 00:18:35,340 --> 00:18:37,220 Hva slags ting? 425 00:18:37,220 --> 00:18:37,460 Yeah. 426 00:18:37,460 --> 00:18:38,500 Så lokale variabler. 427 00:18:38,500 --> 00:18:43,080 Når som helst vi trengte litt lokal lagring, som et argument, eller int jeg, eller int 428 00:18:43,080 --> 00:18:45,940 temp, eller hva det lokale variabelen, har vi vært 429 00:18:45,940 --> 00:18:47,210 sette det på stakken. 430 00:18:47,210 --> 00:18:49,610 Og vi kaller det en stabel fordi av at lagdeling idé. 431 00:18:49,610 --> 00:18:52,940 Bare slags kamper opp med virkeligheten, begrepet derav. 432 00:18:52,940 --> 00:18:56,650 >> Men det viser seg at en stabel kan også bli sett på som en datastruktur, en 433 00:18:56,650 --> 00:19:00,110 alternativ til en matrise, et alternativ til en lenket liste. 434 00:19:00,110 --> 00:19:02,770 Noe konseptuelt mer interessant som fortsatt kan være 435 00:19:02,770 --> 00:19:06,030 implementert ved hjelp av noen av disse ting, men det er en annen type 436 00:19:06,030 --> 00:19:09,140 datastruktur støtte, egentlig, bare to operasjoner. 437 00:19:09,140 --> 00:19:11,000 Men du kan legge på mer avansert funksjoner enn disse. 438 00:19:11,000 --> 00:19:12,180 Men disse er det grunnleggende - 439 00:19:12,180 --> 00:19:13,510 presse og pop. 440 00:19:13,510 --> 00:19:19,240 >> Og ideen med en stabel er at hvis jeg har her, med eller uten Annenberg 441 00:19:19,240 --> 00:19:22,880 vite, et brett fra naboen med tallet 9 på den. 442 00:19:22,880 --> 00:19:23,870 Så bare en int. 443 00:19:23,870 --> 00:19:26,990 Og jeg ønsker å presse dette på dataene struktur, som for tiden er tom. 444 00:19:26,990 --> 00:19:28,790 Betrakt dette nederst i stabelen. 445 00:19:28,790 --> 00:19:33,150 Jeg ville presse dette tallet 9 på stable, og nå er det akkurat det. 446 00:19:33,150 --> 00:19:36,040 >> Men det interessante ting om en stabel er at hvis jeg nå ønsker å presse 447 00:19:36,040 --> 00:19:40,210 en annen verdi, 17, ut og jeg presse dette på stakken, jeg kommer til å gjøre 448 00:19:40,210 --> 00:19:43,290 den eneste intuitive ting, jeg bare kommer å sette den akkurat der vi mennesker 449 00:19:43,290 --> 00:19:45,180 ville være tilbøyelig til å si det, på toppen. 450 00:19:45,180 --> 00:19:48,850 Men det som er interessant nå er, hvordan får jeg på 9? 451 00:19:48,850 --> 00:19:50,670 Vet du, jeg tror ikke uten litt innsats. 452 00:19:50,670 --> 00:19:54,070 >> Så hva er interessant om en stabel er at ved design, 453 00:19:54,070 --> 00:19:56,330 det er en LIFO datastruktur. 454 00:19:56,330 --> 00:19:59,680 Silly måte å beskrive sist inn, først ut. 455 00:19:59,680 --> 00:20:03,280 Så det siste nummeret i på dette tidspunktet var 17 år. 456 00:20:03,280 --> 00:20:07,540 Så hvis jeg ønsker å komme noe av av stabelen, kan det bare være 17. 457 00:20:07,540 --> 00:20:11,890 Så det er en obligatorisk rekkefølge operasjoner her, hvor det siste elementet 458 00:20:11,890 --> 00:20:14,260 i må være den første ut. 459 00:20:14,260 --> 00:20:16,440 Derav forkortelsen, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Så hvorfor kan dette være nyttig? 461 00:20:19,160 --> 00:20:22,690 Er deres sammenhenger der du hadde vil ha en datastruktur som dette? 462 00:20:22,690 --> 00:20:24,810 Vel, det er sikkert vært nyttig innsiden av en datamaskin. 463 00:20:24,810 --> 00:20:29,050 Så operativsystemer klart bruke dette type datastruktur for stabler. 464 00:20:29,050 --> 00:20:32,800 Vi vil også se den samme ideen når det kommer til web-sider. 465 00:20:32,800 --> 00:20:35,890 Så denne uken og neste uke og utover, og som du begynner å implementere web 466 00:20:35,890 --> 00:20:39,490 sider i et språk som heter HTML, kan du faktisk bruke en datastruktur som 467 00:20:39,490 --> 00:20:42,690 dette for å bestemme om siden er riktig formatert. 468 00:20:42,690 --> 00:20:47,170 Fordi vi vil se alle websider følger et slags hierarki, et innrykk 469 00:20:47,170 --> 00:20:52,030 som vil, ved slutten av dagen, være en trestruktur under panseret. 470 00:20:52,030 --> 00:20:53,620 Så mer om det i bare litt. 471 00:20:53,620 --> 00:20:56,560 >> Men for nå, la oss foreslå for en øyeblikk, hvordan kunne vi gå om 472 00:20:56,560 --> 00:20:58,830 representerer hva en stabel er? 473 00:20:58,830 --> 00:21:03,370 La meg foreslå at vi implementerer en stabel med kode som dette. 474 00:21:03,370 --> 00:21:07,990 Så en stabel kommer til å ha på innsiden av det to ting, en rekke, kalt skuffer, 475 00:21:07,990 --> 00:21:09,510 bare for å være i samsvar med demoen. 476 00:21:09,510 --> 00:21:12,660 Og hvert av elementene i denne matrisen kommer til å være en type int. 477 00:21:12,660 --> 00:21:14,740 Og kapasitet er formodentlig hva? 478 00:21:14,740 --> 00:21:18,796 Fordi jeg ikke har skrevet fullstendig definisjon her. 479 00:21:18,796 --> 00:21:21,535 >> Det er trolig det maksimale størrelsen på matrisen. 480 00:21:21,535 --> 00:21:25,150 Og det er sannsynligvis erklært som en skarp definere på toppen av filen, noen 481 00:21:25,150 --> 00:21:28,450 slags konstant som følger av den bare store bokstaver. 482 00:21:28,450 --> 00:21:32,250 Så et sted kapasitet er definert som maksimal mulig størrelse. 483 00:21:32,250 --> 00:21:35,590 I mellomtiden innsiden av datastrukturen kjent som en stabel vil det 484 00:21:35,590 --> 00:21:38,630 være et heltall bare kjent bare som størrelse. 485 00:21:38,630 --> 00:21:43,400 >> Så hvis jeg skulle representere dette nå pictorially, la oss anta at dette 486 00:21:43,400 --> 00:21:48,070 Hele svart boks representerer min stack. 487 00:21:48,070 --> 00:21:50,070 Innsiden av det er to variabler. 488 00:21:50,070 --> 00:21:54,780 Så jeg kommer til å trekke første som størrelse. 489 00:21:54,780 --> 00:21:57,420 Og den andre jeg kommer å trekke som en matrise. 490 00:21:57,420 --> 00:22:01,060 >> Men bare for å holde ting ryddig, normalt ville jeg trekke en matrise som 491 00:22:01,060 --> 00:22:04,910 dette, men det er litt fint hvis vi samsvarer med virkeligheten, eller 492 00:22:04,910 --> 00:22:06,230 matche den mentale modellen. 493 00:22:06,230 --> 00:22:12,880 Så la meg i stedet trekke matrisen vertikalt, er der bare igjen, 494 00:22:12,880 --> 00:22:13,840 kunstnerens gjengivelse. 495 00:22:13,840 --> 00:22:16,610 Spiller egentlig ingen rolle hva det er under panseret. 496 00:22:16,610 --> 00:22:20,350 Og vi vil si at, som standard, kapasitet kommer til å bli tre. 497 00:22:20,350 --> 00:22:23,480 Så dette vil være 0 beliggenhet, dette vil være plassering 1, dette 498 00:22:23,480 --> 00:22:25,740 vil være plassering to. 499 00:22:25,740 --> 00:22:29,330 >> Hvis jeg bestikke med en stress ball, ville noen liker å komme opp og kjøre 500 00:22:29,330 --> 00:22:30,870 borde her for bare et øyeblikk? 501 00:22:30,870 --> 00:22:31,960 OK, så hånden først. 502 00:22:31,960 --> 00:22:33,950 Kom opp. 503 00:22:33,950 --> 00:22:36,500 OK. 504 00:22:36,500 --> 00:22:38,760 Så jeg tror det er Steven. 505 00:22:38,760 --> 00:22:40,035 Kom opp. 506 00:22:40,035 --> 00:22:40,770 OK. 507 00:22:40,770 --> 00:22:46,760 >> Men anta nå vi spole tilbake til den opprinnelige tilstanden i verden hvor jeg 508 00:22:46,760 --> 00:22:52,180 har nettopp erklært en stabel, og det er kommer til å være av kapasiteten tre. 509 00:22:52,180 --> 00:22:54,470 Men størrelse er ennå ikke bestemt. 510 00:22:54,470 --> 00:22:56,100 Skuffer er ennå ikke bestemt. 511 00:22:56,100 --> 00:22:57,300 Så et par spørsmål først. 512 00:22:57,300 --> 00:23:01,310 Og la meg gi deg mic slik at du kan delta mer aktivt i dette. 513 00:23:01,310 --> 00:23:05,190 >> Så hva er inne i størrelse i dette øyeblikk i tid hvis alt jeg har gjort er 514 00:23:05,190 --> 00:23:09,340 erklærte en stabel med en linje med kode? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: Ikke mye. 516 00:23:10,100 --> 00:23:12,080 >> DAVID MALAN: OK, ikke mye. 517 00:23:12,080 --> 00:23:14,410 Vet vi hva som er inne i størrelse, vet vi hva som er inni 518 00:23:14,410 --> 00:23:16,330 i denne tabellen her? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Bare tilfeldig kode, ikke sant? 520 00:23:18,630 --> 00:23:20,220 Just - 521 00:23:20,220 --> 00:23:23,230 >> DAVID MALAN: Ja, jeg kommer til å kaller det koden, men tilfeldig - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Things. 523 00:23:23,820 --> 00:23:28,290 >> DAVID MALAN: Ting som tilfeldig 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: Bits. 525 00:23:28,870 --> 00:23:29,530 >> DAVID MALAN: Bits, ikke sant? 526 00:23:29,530 --> 00:23:31,190 Så søppel verdier, ikke sant? 527 00:23:31,190 --> 00:23:33,470 Så permutasjoner av 0 og 1-ere. 528 00:23:33,470 --> 00:23:35,920 Rester av tidligere bruksområder av denne hukommelse. 529 00:23:35,920 --> 00:23:38,150 Og vi vet egentlig ikke hva verdiene er, slik vi vanligvis trekke dem 530 00:23:38,150 --> 00:23:38,930 som spørsmålstegn. 531 00:23:38,930 --> 00:23:41,990 >> Så det første vi er formodentlig kommer til å ønske å gjøre her - 532 00:23:41,990 --> 00:23:46,630 og la meg gi dette feltet inne av det et navn - skuffer. 533 00:23:46,630 --> 00:23:49,540 Hva bør vi antagelig starte størrelse til hvis vi ønsker å 534 00:23:49,540 --> 00:23:51,040 begynne å bruke denne bunken? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Skuff er sub 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID MALAN: Så, OK. 537 00:23:53,910 --> 00:23:56,710 Å være klar, er kapasiteten erklært andre steder som tre. 538 00:23:56,710 --> 00:23:58,570 Og det er det jeg har brukt å fordele array. 539 00:23:58,570 --> 00:24:03,535 Størrelse kommer til å referere til hvor mange skuffer er for tiden på stakken. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Zero. 541 00:24:03,880 --> 00:24:04,460 >> DAVID MALAN: Så det burde være null. 542 00:24:04,460 --> 00:24:07,760 Så gå videre, og med noen finger, tegner en null i størrelse. 543 00:24:07,760 --> 00:24:08,440 OK. 544 00:24:08,440 --> 00:24:10,920 Så nå, hva som er inni denne her, vet vi ikke. 545 00:24:10,920 --> 00:24:12,160 Dette er egentlig bare søppel verdier. 546 00:24:12,160 --> 00:24:14,800 Slik at vi kunne trekke spørsmålstegn, men la oss holde styret ren for nå 547 00:24:14,800 --> 00:24:16,300 fordi det spiller ingen rolle hva som er der. 548 00:24:16,300 --> 00:24:19,130 Vi trenger ikke å initialisere tabellen til noe, fordi hvis vi vet at 549 00:24:19,130 --> 00:24:23,100 størrelsen av stabelen er null, vel, vi bør ikke være å se på noe i 550 00:24:23,100 --> 00:24:25,590 denne matrisen allikevel på dette tidspunktet. 551 00:24:25,590 --> 00:24:29,970 >> Så nå anta at jeg skyver nummer 9 på bunken. 552 00:24:29,970 --> 00:24:33,750 Hvordan skal vi oppdatere datastruktur innsiden av denne svarte boksen? 553 00:24:33,750 --> 00:24:35,540 Hvilke verdier må endre? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: Innen - 555 00:24:36,200 --> 00:24:37,400 størrelsen? 556 00:24:37,400 --> 00:24:37,650 >> DAVID MALAN: OK. 557 00:24:37,650 --> 00:24:38,770 Størrelse bør bli det? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Størrelse skulle være ett. 559 00:24:39,580 --> 00:24:39,870 >> DAVID MALAN: OK. 560 00:24:39,870 --> 00:24:41,110 Så størrelse bør bli ett. 561 00:24:41,110 --> 00:24:42,540 Så du kan gjøre dette i et par måter. 562 00:24:42,540 --> 00:24:46,920 La meg gi deg, nå er din finger er et viskelær. 563 00:24:46,920 --> 00:24:47,260 OK. 564 00:24:47,260 --> 00:24:49,960 Så nå fingeren er en pensel. 565 00:24:49,960 --> 00:24:50,330 OK. 566 00:24:50,330 --> 00:24:52,820 Og nå hva andre har å endre, Selvfølgelig, i datastrukturen? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Vi går fra bunnen opp til ni. 568 00:24:57,060 --> 00:24:57,760 >> DAVID MALAN: 9. 569 00:24:57,760 --> 00:24:58,420 OK, Bra. 570 00:24:58,420 --> 00:25:01,550 Så fortsatt ingen rolle hva som står på beliggenhet én eller to fordi de er 571 00:25:01,550 --> 00:25:04,520 søppel verdier, men vi bør ikke bry ser det fordi størrelsen er 572 00:25:04,520 --> 00:25:07,540 forteller oss at bare det første elementet er faktisk legitimt. 573 00:25:07,540 --> 00:25:10,400 Så nå skal jeg presse 17 på listen. 574 00:25:10,400 --> 00:25:11,830 Hva skjer med dette bildet? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: Så størrelsen kommer til å gå til to. 576 00:25:14,720 --> 00:25:15,300 >> DAVID MALAN: OK. 577 00:25:15,300 --> 00:25:16,070 Du er viskelær - 578 00:25:16,070 --> 00:25:16,810 oops. 579 00:25:16,810 --> 00:25:18,026 Du er et viskelær. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Eraser. 581 00:25:18,840 --> 00:25:19,720 >> DAVID MALAN: Du er en børste. 582 00:25:19,720 --> 00:25:20,560 >> STEVEN: Brush. 583 00:25:20,560 --> 00:25:20,920 >> DAVID MALAN: OK. 584 00:25:20,920 --> 00:25:21,600 Og hva annet? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: Og da er vi - 586 00:25:22,600 --> 00:25:22,915 >> DAVID MALAN: Vi presset 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Vi holder 17 på topp, så - 588 00:25:24,760 --> 00:25:25,710 >> DAVID MALAN: OK, bra. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN: - slippe den ned. 590 00:25:27,040 --> 00:25:27,530 >> DAVID MALAN: All right. 591 00:25:27,530 --> 00:25:27,940 Det begynner å bli lett. 592 00:25:27,940 --> 00:25:29,300 Jeg kommer ikke til å hjelpe deg denne gangen. 593 00:25:29,300 --> 00:25:30,510 Push 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Ferdig. 595 00:25:31,720 --> 00:25:34,870 Å bli et viskelær. 596 00:25:34,870 --> 00:25:37,340 Jeg blir en børste. 597 00:25:37,340 --> 00:25:39,340 Og så jeg setter 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID MALAN: 22. 599 00:25:40,100 --> 00:25:40,620 Utmerket. 600 00:25:40,620 --> 00:25:41,380 Så en gang til. 601 00:25:41,380 --> 00:25:44,280 Jeg er nå kommer til å presse på stabelen 26.. 602 00:25:44,280 --> 00:25:46,350 >> STEVEN: Ooh. 603 00:25:46,350 --> 00:25:50,278 Oh gosh. 604 00:25:50,278 --> 00:25:52,520 Du virkelig fanget meg av vakt. 605 00:25:52,520 --> 00:25:53,703 >> DAVID MALAN: Du gjorde ikke se dette komme? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: Jeg så ikke dette komme. 607 00:25:55,930 --> 00:25:58,756 Kunne vi re-initial kapasitet? 608 00:25:58,756 --> 00:25:59,790 >> DAVID MALAN: Det er et godt spørsmål. 609 00:25:59,790 --> 00:26:02,360 Så vi har litt malt oss selv i et hjørne her. 610 00:26:02,360 --> 00:26:06,740 Det er egentlig ingen god ut for Steven fordi vi har tildelt denne tabellen 611 00:26:06,740 --> 00:26:09,130 statisk, så å si, inni av datastrukturen. 612 00:26:09,130 --> 00:26:12,170 Og vi har egentlig hardkodet det å være av størrelsen tre. 613 00:26:12,170 --> 00:26:14,170 Så vi kan ikke egentlig omfordele det. 614 00:26:14,170 --> 00:26:20,020 >> Vi kunne hvis vi gikk inn igjen, vi omdefinert skuffer å være en peker som 615 00:26:20,020 --> 00:26:22,300 vi da bruke malloc for hånden minne til. 616 00:26:22,300 --> 00:26:25,050 Fordi hvis vi fikk minnet fra haugen via malloc, vi 617 00:26:25,050 --> 00:26:26,430 kan da frigjøre den. 618 00:26:26,430 --> 00:26:29,630 Men før frigjør det, kunne vi omdisponere en større mengde minne, 619 00:26:29,630 --> 00:26:31,330 oppdatere pekeren, og så videre. 620 00:26:31,330 --> 00:26:33,500 Men for nå, er dette virkelig det beste vi kan gjøre. 621 00:26:33,500 --> 00:26:36,360 Presse og pop er antagelig kommer til å signalisere noen feil. 622 00:26:36,360 --> 00:26:40,270 >> Så for eksempel, vår gjennomføring av presse kunne returnere en bool som 623 00:26:40,270 --> 00:26:42,390 tidligere returnert true, true, true. 624 00:26:42,390 --> 00:26:48,390 Men fjerde gang, det kommer til å ha for return false, for eksempel. 625 00:26:48,390 --> 00:26:48,540 OK. 626 00:26:48,540 --> 00:26:49,540 Veldig godt gjort. 627 00:26:49,540 --> 00:26:50,060 Gratulerer. 628 00:26:50,060 --> 00:26:52,160 Du har fortjent stress ball i dag. 629 00:26:52,160 --> 00:26:53,110 >> [APPLAUSE] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Takk. 631 00:26:54,382 --> 00:26:55,680 >> DAVID MALAN: Takk. 632 00:26:55,680 --> 00:26:59,740 OK, så dette synes å være ikke mye av et skritt fremover, ikke sant? 633 00:26:59,740 --> 00:27:01,410 Vi beskrev dette datastruktur. 634 00:27:01,410 --> 00:27:02,320 Det har vært overbevisende, ikke sant? 635 00:27:02,320 --> 00:27:03,200 Operativsystemer liker det. 636 00:27:03,200 --> 00:27:06,360 Angivelig nettet kan gjøre bruk av dette, og andre programmer fremdeles. 637 00:27:06,360 --> 00:27:10,870 Men hva en dum begrensning som vi er tilbake til slags uke to grenser 638 00:27:10,870 --> 00:27:12,880 der vi har fast størrelse arrays. 639 00:27:12,880 --> 00:27:15,010 >> Så det er faktisk et par måter vi kan løse dette. 640 00:27:15,010 --> 00:27:18,750 Vi kunne dynamisk allokere array, ikke ved hardt koding det som jeg har 641 00:27:18,750 --> 00:27:22,600 gjort her, men i stedet re-erklærte dette, å bare være klart, som 642 00:27:22,600 --> 00:27:23,830 noe sånt som dette. 643 00:27:23,830 --> 00:27:29,040 Int * skuffer ikke bestemme på en kapasitet ennå. 644 00:27:29,040 --> 00:27:35,460 Men når jeg erklærer stabelen andre steder i koden min, kan jeg da kalle malloc, 645 00:27:35,460 --> 00:27:38,250 få adressen til en del av minne, og jeg kunne tildele 646 00:27:38,250 --> 00:27:39,980 den adressen til skuffene. 647 00:27:39,980 --> 00:27:43,340 >> Og så, fordi det er bare en del av minne, kan jeg fortsette å bruke plassen 648 00:27:43,340 --> 00:27:45,450 brakett notasjon på vanlig måte. 649 00:27:45,450 --> 00:27:49,020 Fordi igjen, det er liksom dette funksjonell ekvivalent av matriser og 650 00:27:49,020 --> 00:27:50,820 biter av minne som kommer tilbake fra malloc. 651 00:27:50,820 --> 00:27:53,090 Vi kan behandle en som de andre bruke pekeren aritmetisk eller 652 00:27:53,090 --> 00:27:54,440 hakeparentes notasjon. 653 00:27:54,440 --> 00:27:55,660 Så det er en tilnærming. 654 00:27:55,660 --> 00:28:00,120 >> Men hvordan ellers kan vi gjennomføre dette samme datastruktur, potensielt? 655 00:28:00,120 --> 00:28:00,280 Høyre? 656 00:28:00,280 --> 00:28:04,530 Jeg føler at vi bare løst dette problem som for en uke siden. 657 00:28:04,530 --> 00:28:08,860 Hva var løsningen på dette problemet at Steven kjørte inn? 658 00:28:08,860 --> 00:28:10,370 Så lenkede lister, høyre. 659 00:28:10,370 --> 00:28:13,410 >> Hvis problemet er at vi male oss selv inn i et hjørne ved å allokere 660 00:28:13,410 --> 00:28:17,580 på forhånd for lite minne som vi deretter har å liksom forholde seg til, vel, 661 00:28:17,580 --> 00:28:19,880 hvorfor ikke bare unngå at utstede helt? 662 00:28:19,880 --> 00:28:26,170 Hvorfor ikke bare erklære skuffer å være en peker til en node, ergo en lenket liste, 663 00:28:26,170 --> 00:28:30,740 og så bare tildele nye noder hver gang Steven nødvendig for å passe til en 664 00:28:30,740 --> 00:28:32,400 nummer i datastruktur. 665 00:28:32,400 --> 00:28:34,200 >> Slik at bildet måtte endre. 666 00:28:34,200 --> 00:28:38,220 Det kommer ikke til å være så ren og som enkelt som bare et utvalg av tre ints. 667 00:28:38,220 --> 00:28:42,970 Nå det kommer til å være en peker til en struct, og at struct kommer til å 668 00:28:42,970 --> 00:28:44,830 har en int og en neste pekeren. 669 00:28:44,830 --> 00:28:47,670 Det kommer til å lede via denne pekeren til en annen slik struct til 670 00:28:47,670 --> 00:28:48,600 en annen slik struct. 671 00:28:48,600 --> 00:28:50,560 Slik at bildet ville faktisk få litt Messier. 672 00:28:50,560 --> 00:28:52,950 Og vi ville ha piler binde alt sammen. 673 00:28:52,950 --> 00:28:55,280 >> Men det er greit, ikke sant, fordi Vi har sett hvordan du gjør dette. 674 00:28:55,280 --> 00:28:58,180 Og når du blir komfortabel gjennomføre noe sånt som en koblet 675 00:28:58,180 --> 00:29:01,450 liste, som du må gjøre hvis du velger å gjennomføre en hash tabell med 676 00:29:01,450 --> 00:29:05,120 separat kjeding for p-set 6, kan du bruke den som en byggekloss, eller en 677 00:29:05,120 --> 00:29:08,870 ingrediens, eller i Scratch snakke, en prosedyre, noe som du putter, du 678 00:29:08,870 --> 00:29:12,560 opprettet din egen puslespill brikke som du deretter kan bruke. 679 00:29:12,560 --> 00:29:17,090 Så avveininger, men mulige løsninger at vi faktisk har sett før. 680 00:29:17,090 --> 00:29:20,560 >> Så ganske ofte, ser du dette hver år eller to når Apple utgivelser 681 00:29:20,560 --> 00:29:23,060 noe nytt, og alle de gale menneskene linje opp utenfor Apple 682 00:29:23,060 --> 00:29:27,050 butikken for å kjøpe deres marginale oppgradere på maskinvare. 683 00:29:27,050 --> 00:29:30,420 Jeg sier dette, er det OK, fordi Jeg er en av dem. 684 00:29:30,420 --> 00:29:35,140 Så hva slags datastruktur kan representere denne virkeligheten? 685 00:29:35,140 --> 00:29:36,980 >> Vel, la oss kalle det en kø, en linje. 686 00:29:36,980 --> 00:29:40,270 Så britisk vil kalle det vanligvis en køen uansett, så det er et fint navn. 687 00:29:40,270 --> 00:29:44,960 Og de to operasjonene som en kø skal støtte vi kaller en enqueue 688 00:29:44,960 --> 00:29:48,900 drift og en dequeue drift, som er like i 689 00:29:48,900 --> 00:29:50,120 ånd å presse og pop. 690 00:29:50,120 --> 00:29:54,060 Det er bare en slags annerledes i konvensjon, hva vi kaller disse. 691 00:29:54,060 --> 00:29:57,680 Men for å Enqueue noe betyr å legge eller sette den til datastruktur. 692 00:29:57,680 --> 00:29:59,570 Å dequeue betyr å fjerne det. 693 00:29:59,570 --> 00:30:05,170 Men mens en stabel var en LIFO data struktur, er en kø et først inn, 694 00:30:05,170 --> 00:30:06,740 først ut datastruktur. 695 00:30:06,740 --> 00:30:10,050 >> Hvis du er den første personen i kø, vil du være den første personen til å få 696 00:30:10,050 --> 00:30:12,420 ut av linjen og kjøpe den nye enheten. 697 00:30:12,420 --> 00:30:18,070 Tenk deg hvor opprørt disse menneskene ville være hvis Apple i stedet brukt en stabel, for 698 00:30:18,070 --> 00:30:21,250 eksempel, å gjennomføre plukking opp av din nye leketøy. 699 00:30:21,250 --> 00:30:24,310 Så køer fornuftig, i hvert fall, og vi kan tenke på alle slags 700 00:30:24,310 --> 00:30:27,480 applikasjoner, antagelig, for køer, spesielt når du ønsker rettferdighet. 701 00:30:27,480 --> 00:30:30,040 Så hvordan kan vi gjennomføre disse som en datastruktur? 702 00:30:30,040 --> 00:30:33,680 >> Vel, foreslår jeg at vi kan trenger å gjøre det på denne måten. 703 00:30:33,680 --> 00:30:35,225 Så jeg kommer til å nå ha tall. 704 00:30:35,225 --> 00:30:38,190 Så vi vil holde det enkelt og ikke nødvendigvis snakker i form av skuffer. 705 00:30:38,190 --> 00:30:40,220 Bare tall som folk har fått. 706 00:30:40,220 --> 00:30:43,760 Kapasiteten skal, igjen, fikse totale antall personer som kan være i 707 00:30:43,760 --> 00:30:46,900 denne linjen, som tre eller hva andre verdi. 708 00:30:46,900 --> 00:30:50,760 >> Men jeg foreslår at jeg trenger å holde styr ikke bare av størrelsen på den 709 00:30:50,760 --> 00:30:52,370 kø, hvor mange ting er i den. 710 00:30:52,370 --> 00:30:56,310 Så størrelsen er den nåværende størrelse, kapasitet er den maksimale størrelse. 711 00:30:56,310 --> 00:30:58,540 Bare igjen, nomenklatur etter konvensjonen. 712 00:30:58,540 --> 00:31:03,680 Hvorfor trenger jeg en ekstra int inne av en kø for å holde styr på hvem som er i 713 00:31:03,680 --> 00:31:05,365 foran linjen? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Hvorfor trenger jeg å gjøre det i dette tilfellet? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Vel, hvordan er dette bildet kommer til å forandre seg? 718 00:31:16,190 --> 00:31:19,280 Jeg kan sikkert bruke mest av dette bildet. 719 00:31:19,280 --> 00:31:21,480 La meg gå videre og slette innholdet her. 720 00:31:21,480 --> 00:31:24,580 Vi gir dette en litt annet navn her oppe. 721 00:31:24,580 --> 00:31:28,930 La oss bli kvitt den 17, la oss bli kvitt av ni, la oss bli kvitt den 3. 722 00:31:28,930 --> 00:31:30,410 Og la oss legge til en annen ting. 723 00:31:30,410 --> 00:31:34,710 Jeg foreslår at jeg trenger å holde styr på forsiden av listen, i hvilken bare 724 00:31:34,710 --> 00:31:35,570 kommer til å være en int også. 725 00:31:35,570 --> 00:31:36,550 Og vi kommer til å holde det enkelt. 726 00:31:36,550 --> 00:31:37,740 Ingen lenket liste for nå. 727 00:31:37,740 --> 00:31:40,900 >> Vi skal innrømme at vi kommer til å bump opp mot denne grensen. 728 00:31:40,900 --> 00:31:43,720 Men hva ønsker jeg å se skje denne gangen? 729 00:31:43,720 --> 00:31:47,240 Så antar jeg gå videre og den første person kommer opp i kø, og 730 00:31:47,240 --> 00:31:48,560 det er nummer ni. 731 00:31:48,560 --> 00:31:49,680 Vi har stress baller. 732 00:31:49,680 --> 00:31:51,330 Kan jeg stjele, sier, to eller tre personer? 733 00:31:51,330 --> 00:31:52,690 En, to, tre? 734 00:31:52,690 --> 00:31:53,120 Kom opp. 735 00:31:53,120 --> 00:31:56,022 Rett forfra, fordi vi vil gjøre dette til en rask. 736 00:31:56,022 --> 00:31:59,415 >> Hver av dere nå kommer til å være en fan gutt i kø på Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Du vil ikke motta Apple-maskinvare på slutten av dette selv. 739 00:32:06,210 --> 00:32:06,500 OK. 740 00:32:06,500 --> 00:32:09,430 Så du er nummer 9, er du nummer 17, nummer 22. 741 00:32:09,430 --> 00:32:12,130 Dette er vilkårlige tall, som student-ID eller whatnot. 742 00:32:12,130 --> 00:32:14,550 Og om en liten stund, la oss begynne å begynne å legge ting. 743 00:32:14,550 --> 00:32:16,000 Og jeg skal kjøre brettet her denne gangen. 744 00:32:16,000 --> 00:32:19,570 >> Så i dette tilfellet, har jeg initialisert foran å være - 745 00:32:19,570 --> 00:32:22,380 Jeg faktisk ikke egentlig bryr seg hva foran er, fordi størrelsen er null. 746 00:32:22,380 --> 00:32:24,480 Så dette kan like godt bare være et spørsmålstegn. 747 00:32:24,480 --> 00:32:26,170 Disse er alle spørsmålstegn. 748 00:32:26,170 --> 00:32:29,880 Så nå skal vi begynne å faktisk se noen folk i kø i butikken. 749 00:32:29,880 --> 00:32:33,320 >> Så hvis nummer 9, er du den første der på 5 AM, gå videre og stille opp, 750 00:32:33,320 --> 00:32:34,210 eller kvelden før. 751 00:32:34,210 --> 00:32:34,580 OK. 752 00:32:34,580 --> 00:32:35,940 Så nå ni er her. 753 00:32:35,940 --> 00:32:37,940 Så 9 er på forsiden av listen. 754 00:32:37,940 --> 00:32:41,440 Så jeg kommer til å gå videre og oppdatere Størrelsen på denne aktuelle data 755 00:32:41,440 --> 00:32:44,740 struktur for å ikke være 0 lenger, men for å være en. 756 00:32:44,740 --> 00:32:47,630 Jeg kommer til å sette 9 på forsiden av listen. 757 00:32:47,630 --> 00:32:51,020 La meg gå videre og slå på skjermen slik at vi kan se forbi oss her. 758 00:32:51,020 --> 00:32:53,220 >> Og nå hva jeg vil å sette på forsiden? 759 00:32:53,220 --> 00:32:56,240 Jeg kommer til å holde styr på at foran i køen akkurat nå 760 00:32:56,240 --> 00:32:58,570 er på stedet 0. 761 00:32:58,570 --> 00:33:00,510 Fordi hva er neste kommer til å skje? 762 00:33:00,510 --> 00:33:03,000 Vel, vel nå jeg Enqueue 17 i tillegg. 763 00:33:03,000 --> 00:33:04,510 Så hoppe på linje der. 764 00:33:04,510 --> 00:33:07,060 Og igjen, den slags døren til butikken kommer til å være her. 765 00:33:07,060 --> 00:33:08,700 Så nå har jeg lagt 17. 766 00:33:08,700 --> 00:33:10,810 Og selv om disse gutta blokkerer skjermen, det er OK, 767 00:33:10,810 --> 00:33:12,300 fordi vi kan se det her oppe. 768 00:33:12,300 --> 00:33:12,910 Unnskyld. 769 00:33:12,910 --> 00:33:13,810 >> PUBLIKUM: Vi kan flytte - 770 00:33:13,810 --> 00:33:14,660 >> DAVID MALAN: Nei, det er OK. 771 00:33:14,660 --> 00:33:16,000 Det er stor der oppe. 772 00:33:16,000 --> 00:33:18,580 Så 17 er nå inne i køen. 773 00:33:18,580 --> 00:33:21,332 Jeg trenger å oppdatere som felt nå skjønt? 774 00:33:21,332 --> 00:33:23,210 OK, absolutt størrelse. 775 00:33:23,210 --> 00:33:26,430 Og hva med fronten? 776 00:33:26,430 --> 00:33:27,040 OK, nei. 777 00:33:27,040 --> 00:33:30,200 Foran bør ikke endre, fordi i motsetning til en stabel, vi 778 00:33:30,200 --> 00:33:31,370 ønsker å opprettholde rettferdighet. 779 00:33:31,370 --> 00:33:35,150 Så hvis 9 kom i første, vil vi 9 å være den første ut av linjen 780 00:33:35,150 --> 00:33:36,420 og inn i butikken. 781 00:33:36,420 --> 00:33:37,220 >> Faktisk, la oss se det. 782 00:33:37,220 --> 00:33:42,235 Før vi setter 22, la oss gå videre og dequeue ni. 783 00:33:42,235 --> 00:33:42,970 Hva er navnet ditt igjen? 784 00:33:42,970 --> 00:33:43,680 >> PUBLIKUM: Jake. 785 00:33:43,680 --> 00:33:45,440 >> DAVID MALAN: Jake kommer å bli dequeued nå. 786 00:33:45,440 --> 00:33:48,050 Så du kommer til å gå inn i butikken. 787 00:33:48,050 --> 00:33:49,880 Og late som at butikken er der borte. 788 00:33:49,880 --> 00:33:51,970 Så nå hva trenger - dit-dit-dit! 789 00:33:51,970 --> 00:33:53,400 Hva må skje nå? 790 00:33:53,400 --> 00:33:54,490 Design beslutning. 791 00:33:54,490 --> 00:33:56,825 Så ikke en dårlig instinkt, men - hva heter du igjen? 792 00:33:56,825 --> 00:33:57,090 >> PUBLIKUM: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID MALAN: David. 794 00:33:57,500 --> 00:33:58,810 Så hva gjorde David? 795 00:33:58,810 --> 00:34:02,590 Han prøvde å liksom fikse data struktur og flytte fra stedet hans 796 00:34:02,590 --> 00:34:04,100 til Jakes tidligere plassering. 797 00:34:04,100 --> 00:34:06,740 Og det er fint hvis vi er villige å akseptere at som en 798 00:34:06,740 --> 00:34:08,199 implementering detaljer. 799 00:34:08,199 --> 00:34:11,100 Men først, la oss oppdatere dataene strukturen før vi gjør det. 800 00:34:11,100 --> 00:34:14,139 Fordi jeg ikke er fornøyd med tanken på alt folk skiftende i denne linjen. 801 00:34:14,139 --> 00:34:17,360 >> Det er ingen big deal om David gjør det med ett trinn, men igjen, tenker tilbake til 802 00:34:17,360 --> 00:34:20,360 når vi har hatt åtte frivillige på scenen og vi har gjort som innsetting 803 00:34:20,360 --> 00:34:22,600 sortere, hvor vi måtte starte flytte alle rundt. 804 00:34:22,600 --> 00:34:23,790 Som fikk dyrt, ikke sant? 805 00:34:23,790 --> 00:34:28,330 Det gjør meg flau om big O av N, kvadrerte stor O for n på nytt. 806 00:34:28,330 --> 00:34:30,650 Det er ikke følelsen som en ideell utfall. 807 00:34:30,650 --> 00:34:32,080 >> Så la oss bare oppdatere denne. 808 00:34:32,080 --> 00:34:35,120 Slik at størrelsen av køen ikke lenger er to. 809 00:34:35,120 --> 00:34:37,090 Det er nå bare en. 810 00:34:37,090 --> 00:34:40,360 Men jeg kan nå oppdatere noe Jeg fikk ikke oppdatere før, den 811 00:34:40,360 --> 00:34:41,130 forsiden av listen. 812 00:34:41,130 --> 00:34:45,420 Jeg kunne bare si, er at stedet en? 813 00:34:45,420 --> 00:34:49,770 Så nå har vi søppel verdi her, søppel verdi her, og David i 814 00:34:49,770 --> 00:34:51,469 Midt i dette søppel. 815 00:34:51,469 --> 00:34:54,980 Men datastrukturen er fortsatt intakt. 816 00:34:54,980 --> 00:34:58,540 >> Og faktisk, jeg trenger ikke engang å endre Jakes tidligere nummer 817 00:34:58,540 --> 00:35:00,460 9, fordi hvem bryr seg. 818 00:35:00,460 --> 00:35:04,470 Jeg har nok informasjon nå i størrelse som jeg vet det er én person i 819 00:35:04,470 --> 00:35:05,030 denne køen. 820 00:35:05,030 --> 00:35:08,340 Og jeg vet at den personen er på en plassering, ikke 0. 821 00:35:08,340 --> 00:35:09,760 Jeg er ikke telle. 822 00:35:09,760 --> 00:35:11,300 So 1 tillegg. 823 00:35:11,300 --> 00:35:13,410 Så datastrukturen er fortsatt OK. 824 00:35:13,410 --> 00:35:14,330 >> Vel, hva skjer videre? 825 00:35:14,330 --> 00:35:15,010 La oss enqueue - 826 00:35:15,010 --> 00:35:15,370 hva heter du? 827 00:35:15,370 --> 00:35:16,160 >> PUBLIKUM: Callen. 828 00:35:16,160 --> 00:35:16,580 >> DAVID MALAN: Callen. 829 00:35:16,580 --> 00:35:20,770 La oss Enqueue en Callen, og 22 er nå i køen. 830 00:35:20,770 --> 00:35:22,300 Så hva nå må endre her? 831 00:35:22,300 --> 00:35:24,380 Foran er ikke til å endre, selvsagt. 832 00:35:24,380 --> 00:35:27,160 Størrelse kommer til å endre til å være to igjen. 833 00:35:27,160 --> 00:35:31,590 Og 22 ender opp her, er ni fortsatt er til stede, men det er effektivt en 834 00:35:31,590 --> 00:35:32,600 søppel verdi nå. 835 00:35:32,600 --> 00:35:35,910 Det er bare en rest av Jake fortiden. 836 00:35:35,910 --> 00:35:39,200 >> Så nå hva skjer hvis Jeg dequeue David? 837 00:35:39,200 --> 00:35:41,560 En siste operasjon, dequeue David. 838 00:35:41,560 --> 00:35:46,070 Vi kunne skifte, men jeg foreslår la oss gjøre så lite arbeid som mulig. 839 00:35:46,070 --> 00:35:50,280 Nå er min datastruktur går tilbake i størrelse 2-1. 840 00:35:50,280 --> 00:35:53,730 Men den foran i køen nå blir to. 841 00:35:53,730 --> 00:35:56,640 Jeg trenger ikke å endre disse tallene ennå, fordi de er 842 00:35:56,640 --> 00:35:58,230 bare søppel verdier. 843 00:35:58,230 --> 00:35:59,720 >> Men nå hva skjer? 844 00:35:59,720 --> 00:36:03,280 Antar jeg Enqueue meg selv, 26? 845 00:36:03,280 --> 00:36:05,890 Jeg føler at jeg hører hjemme her borte. 846 00:36:05,890 --> 00:36:06,890 Så jeg blir enqueued. 847 00:36:06,890 --> 00:36:08,760 Så jeg slags hører hjemme her. 848 00:36:08,760 --> 00:36:11,300 Og selv om du ikke helt setter pris på dette visuelt på scenen, 849 00:36:11,300 --> 00:36:15,075 fordi vi har god plass, skulle jeg ikke bli stående her, hvorfor? 850 00:36:15,075 --> 00:36:16,290 >> PUBLIKUM: Du er utenfor banen. 851 00:36:16,290 --> 00:36:16,370 >> DAVID MALAN: Høyre. 852 00:36:16,370 --> 00:36:16,940 Jeg er utenfor banen. 853 00:36:16,940 --> 00:36:19,330 Jeg har indeksert utover rammene av denne tabellen. 854 00:36:19,330 --> 00:36:23,420 Jeg burde virkelig være i en av de tre mulige steder. 855 00:36:23,420 --> 00:36:25,150 Nå, hvor er mest naturlig å gå? 856 00:36:25,150 --> 00:36:27,760 Jeg foreslår vi leveraged en uke ett triks. 857 00:36:27,760 --> 00:36:30,150 Mod operatør, prosent. 858 00:36:30,150 --> 00:36:36,850 Fordi jeg er teknisk sett stående på 3 plassering, men jeg gjør 3 mod kapasitet, 859 00:36:36,850 --> 00:36:40,250 så 3, en prosent tegn, 3 - 860 00:36:40,250 --> 00:36:40,970 kapasitet er tre. 861 00:36:40,970 --> 00:36:41,720 Hva er det? 862 00:36:41,720 --> 00:36:43,700 Hva er resten når du dele tre av tre? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Så det setter meg var Jake var, som faktisk er bra. 865 00:36:48,140 --> 00:36:50,370 Så nå gjennomføringen av denne saken kommer til å 866 00:36:50,370 --> 00:36:51,250 være litt av en hodepine. 867 00:36:51,250 --> 00:36:53,740 Det er egentlig bare én linje hodepine, med kode. 868 00:36:53,740 --> 00:36:56,580 Men i det minste nå er det søppel verdi her, men det er to 869 00:36:56,580 --> 00:36:57,910 legitime ints her. 870 00:36:57,910 --> 00:37:04,160 Og jeg hevder at vi nå har gjort akkurat hva vi trenger å gjøre så lenge 871 00:37:04,160 --> 00:37:08,600 vi endre hva Jake Verdien var å være 26.. 872 00:37:08,600 --> 00:37:12,110 >> Vi har nå nok informasjon fortsatt for å opprettholde integriteten 873 00:37:12,110 --> 00:37:13,060 av dette datastruktur. 874 00:37:13,060 --> 00:37:17,160 Vi er fortsatt litt ute av lykken når vi vil sette inn fire eller flere total 875 00:37:17,160 --> 00:37:20,740 elementer, men jeg kan i det minste gjøre ganske effektiv bruk av denne konstante 876 00:37:20,740 --> 00:37:21,740 tid, faktisk. 877 00:37:21,740 --> 00:37:27,150 Jeg trenger ikke å bekymre deg for å skifte alle, som Davids tilbøyelighet var. 878 00:37:27,150 --> 00:37:30,816 >> Eventuelle spørsmål om stabler, eller denne køen? 879 00:37:30,816 --> 00:37:32,184 >> PUBLIKUM: Er grunnen du trenger størrelse slik at du vet 880 00:37:32,184 --> 00:37:34,010 hvor du skal ha en person? 881 00:37:34,010 --> 00:37:34,770 >> DAVID MALAN: Nettopp. 882 00:37:34,770 --> 00:37:38,230 Jeg trenger å vite størrelsen på array fordi jeg trenger å vite nøyaktig hvordan 883 00:37:38,230 --> 00:37:41,940 mange av disse verdiene er legitime, og slik at jeg kan finne hvor du skal sette 884 00:37:41,940 --> 00:37:42,800 neste person. 885 00:37:42,800 --> 00:37:43,300 Nettopp. 886 00:37:43,300 --> 00:37:44,580 Størrelsen er - 887 00:37:44,580 --> 00:37:46,360 faktisk, det gjorde vi ikke oppdatere dette ennå. 888 00:37:46,360 --> 00:37:48,380 Jeg har lagt meg selv på 26.. 889 00:37:48,380 --> 00:37:51,760 Størrelsen er nå, ikke en, men to. 890 00:37:51,760 --> 00:37:57,780 Så nå dette hjelper faktisk meg å finne begynnelsen av listen, som ikke er 0, ikke 891 00:37:57,780 --> 00:37:59,250 1, men er 2.. 892 00:37:59,250 --> 00:38:01,665 Fronten av listen er faktisk nummer 22. 893 00:38:01,665 --> 00:38:05,120 Fordi han kom i første, så han burde tillates inn i butikken før meg, 894 00:38:05,120 --> 00:38:08,780 selv om visuelt jeg står nærmere til butikken. 895 00:38:08,780 --> 00:38:09,220 >> Greit? 896 00:38:09,220 --> 00:38:12,410 En runde med applaus for disse gutta og vi vil la dem ut av det. 897 00:38:12,410 --> 00:38:17,090 >> [APPLAUSE] 898 00:38:17,090 --> 00:38:18,150 >> DAVID MALAN: jeg kunne la du holder skuffen. 899 00:38:18,150 --> 00:38:20,760 Vi kunne se hva som skjer hvis du vil, men kanskje ikke. 900 00:38:20,760 --> 00:38:21,590 OK. 901 00:38:21,590 --> 00:38:25,380 Så hva nå etterlater det oss? 902 00:38:25,380 --> 00:38:28,900 Vel, la meg foreslå at det er en få andre datastrukturer vi kunne 903 00:38:28,900 --> 00:38:33,810 begynne å legge til vår verktøykasse som vil faktisk være ganske, ganske relevant som 904 00:38:33,810 --> 00:38:35,270 vi dykke inn i web ting. 905 00:38:35,270 --> 00:38:38,150 Som igjen har en eller annen tilknytning til trær i form av 906 00:38:38,150 --> 00:38:40,550 noe som kalles DOM, dokument objekt-modellen. 907 00:38:40,550 --> 00:38:42,370 Men vi får se mer av som før lenge. 908 00:38:42,370 --> 00:38:46,260 >> La meg foreslå definitionally at vi kaller treet nå hva du kanskje kjenner som 909 00:38:46,260 --> 00:38:48,820 mer av et familietre, der du har noen stamfar på 910 00:38:48,820 --> 00:38:49,790 røttene til treet. 911 00:38:49,790 --> 00:38:54,480 En patriarkalsk eller en matriark på toppen av treet. 912 00:38:54,480 --> 00:38:56,700 Uten sin ektefelle, i dette tilfellet. 913 00:38:56,700 --> 00:39:00,940 Men nå har vi det vi kaller barn, som er noder som henger 914 00:39:00,940 --> 00:39:05,480 av venstre barn eller høyre barn, piler som avbildet her. 915 00:39:05,480 --> 00:39:10,490 >> Med andre ord, i et tre datastruktur i maskinen, har et tre null 916 00:39:10,490 --> 00:39:11,480 eller flere noder. 917 00:39:11,480 --> 00:39:13,500 Hvis den har minst en node, Det kalles roten. 918 00:39:13,500 --> 00:39:15,700 Det er de tingene visuelt at vi trekke på toppen. 919 00:39:15,700 --> 00:39:20,280 Og at node, som enhver annen node, kan har null, én eller to, eller tre, 920 00:39:20,280 --> 00:39:23,600 eller imidlertid mange barn datastruktur støtter. 921 00:39:23,600 --> 00:39:29,150 I dette tilfellet, roten, lagrer verdi en, har to barn, to og tre, 922 00:39:29,150 --> 00:39:33,020 så vi vanligvis kaller to til venstre barn og 3 den rette barnet. 923 00:39:33,020 --> 00:39:36,940 >> Og så når vi kommer ned til 5, 6, og 7, 6 som kan kalles den mellomste barnet. 924 00:39:36,940 --> 00:39:38,940 Hvis du har fire barn, det blir forvirrende. 925 00:39:38,940 --> 00:39:42,260 Så vi slutte å bruke den slags av snarvei verbalt. 926 00:39:42,260 --> 00:39:44,580 Men det er egentlig bare et familietre. 927 00:39:44,580 --> 00:39:48,880 Og bladene her er nodene som seg selv har ingen barn. 928 00:39:48,880 --> 00:39:52,540 De henger av bunnen av treet. 929 00:39:52,540 --> 00:39:56,940 >> Så hvordan kan vi gjennomføre et tre som har bare to barn maksimalt? 930 00:39:56,940 --> 00:39:58,410 Vi kaller det et binært tre. 931 00:39:58,410 --> 00:40:00,960 Bi igjen betyr to, i denne tilfelle, som med binær. 932 00:40:00,960 --> 00:40:04,830 Og så det kan ha null, én, eller to barn maksimalt. 933 00:40:04,830 --> 00:40:08,650 >> Jeg vil foreslå at vi implementere node for at strukturen med et int n, 934 00:40:08,650 --> 00:40:11,910 og deretter to pekere, kalt en igjen, en som heter rett. 935 00:40:11,910 --> 00:40:14,830 Men de er bare hyggelig vilkårlige konvensjoner. 936 00:40:14,830 --> 00:40:18,170 Og hva er fint nå, spesielt hvis du slags slet konseptuelt med 937 00:40:18,170 --> 00:40:21,300 rekursjon, eller trodde at det ikke var virkelig en løsning på noe, 938 00:40:21,300 --> 00:40:23,120 spesielt hvis du kunne går tom for minne. 939 00:40:23,120 --> 00:40:26,600 Nå som vi snakker om data strukturer og algoritmer som gjør at 940 00:40:26,600 --> 00:40:31,030 oss å traversere og manipulere dem, viser seg at rekursjon kommer tilbake i 941 00:40:31,030 --> 00:40:34,240 en mye mer overbevisende hvis ikke vakker måte. 942 00:40:34,240 --> 00:40:38,670 >> Så dette jeg foreslår er gjennomføringen av en søkefunksjon. 943 00:40:38,670 --> 00:40:39,870 Gitt to innganger - 944 00:40:39,870 --> 00:40:41,570 så tenk på dette som en svart boks. 945 00:40:41,570 --> 00:40:46,560 Gitt to innganger, n, en int, og en pekeren til et tre, en peker til en 946 00:40:46,560 --> 00:40:50,020 node, eller egentlig roten av et tre, jeg hevder at denne funksjonen kan returnere 947 00:40:50,020 --> 00:40:53,530 sant eller usant, at verdien n er inne i dette treet. 948 00:40:53,530 --> 00:40:55,210 >> Hva er inni denne svarte boksen? 949 00:40:55,210 --> 00:40:57,440 Vel, fire grener. 950 00:40:57,440 --> 00:40:58,385 Den første bare sjekker. 951 00:40:58,385 --> 00:41:00,490 Hvis treet er null, bare return false. 952 00:41:00,490 --> 00:41:04,580 Hvis det er ingen node, er det ingen n, det er ingen tall, bare return false. 953 00:41:04,580 --> 00:41:12,330 Hvis skjønt, n, verdien du leter for, er mindre enn tre pilen n, og 954 00:41:12,330 --> 00:41:15,180 bare for å være klar, hva betyr det når Jeg skriver treet og deretter pilen 955 00:41:15,180 --> 00:41:18,150 notasjon, n? 956 00:41:18,150 --> 00:41:18,690 Nettopp. 957 00:41:18,690 --> 00:41:21,970 Det betyr dereference at pekeren kalt treet. 958 00:41:21,970 --> 00:41:26,750 Gå dit, og deretter få innsiden av det node og få sitt felt kalt n. 959 00:41:26,750 --> 00:41:30,810 Og deretter sammenligne den faktiske n som var gått inn Søk mot den. 960 00:41:30,810 --> 00:41:35,390 >> Så hvis n er mindre enn verdien n i treet node selv, vel, 961 00:41:35,390 --> 00:41:36,720 hva betyr det? 962 00:41:36,720 --> 00:41:40,690 Det betyr ingenting ved første øyekast. 963 00:41:40,690 --> 00:41:40,900 Høyre? 964 00:41:40,900 --> 00:41:45,560 Akkurat som når du har en rekke verdier, kan du liker å bruke binær 965 00:41:45,560 --> 00:41:48,290 søke på som en form for splitt og hersk. 966 00:41:48,290 --> 00:41:51,790 Men hva antagelsen vi må gjøre for binære søk for å jobbe i det hele tatt 967 00:41:51,790 --> 00:41:54,510 i telefonboken og tidligere eksempler? 968 00:41:54,510 --> 00:41:55,530 >> Hvordan skal sorteres. 969 00:41:55,530 --> 00:41:59,490 Så la oss avgrense definisjonen av treet her ikke å være bare et tre, som kan 970 00:41:59,490 --> 00:42:00,880 ha en rekke barn. 971 00:42:00,880 --> 00:42:04,700 Ikke bare et binært tre, noe som kan har 0, 1 eller 2 maksimalt. 972 00:42:04,700 --> 00:42:09,700 Men som et binært søketre, eller BST, som er bare en fancy måte å si en 973 00:42:09,700 --> 00:42:15,430 binært tre slik at hver node venstre barn, hvis de finnes, er 974 00:42:15,430 --> 00:42:16,830 mindre enn noden. 975 00:42:16,830 --> 00:42:20,170 Og hver node rett barn, hvis de finnes, er større 976 00:42:20,170 --> 00:42:21,740 enn noden selv. 977 00:42:21,740 --> 00:42:25,200 >> Så med andre ord, om du skulle tegne ut treet, alle tall er 978 00:42:25,200 --> 00:42:30,620 nøye balansert som dette slik at hvis du har 55 som root, kan 33 gå 979 00:42:30,620 --> 00:42:33,090 til venstre for den fordi det er mindre enn 55 år. 980 00:42:33,090 --> 00:42:36,430 77 kan gå til sin rett fordi den er større enn 55. 981 00:42:36,430 --> 00:42:40,750 Men nå legger merke til, den samme definisjonen, det er en rekursiv definisjon verbalt, 982 00:42:40,750 --> 00:42:42,600 må søke om 33. 983 00:42:42,600 --> 00:42:47,610 33 venstre barnet må være mindre enn det, og 33 er rette barnet, 44, må være 984 00:42:47,610 --> 00:42:48,580 større enn den. 985 00:42:48,580 --> 00:42:51,670 >> Så dette er et binært søketre, og Jeg foreslår, ved hjelp av en liten bit av 986 00:42:51,670 --> 00:42:53,910 rekursjon, kan vi nå finne n. 987 00:42:53,910 --> 00:42:59,160 Så hvis n er mindre enn den verdi som er n gjeldende node, jeg kommer til å gå 988 00:42:59,160 --> 00:43:04,090 fremover og punt, så å si, og bare returnere det Svaret er 989 00:43:04,090 --> 00:43:08,470 søker etter n på treets venstre barn. 990 00:43:08,470 --> 00:43:11,370 Legg merke til igjen, denne funksjonen bare forventer en node stjerne, en 991 00:43:11,370 --> 00:43:12,780 peker til en node. 992 00:43:12,780 --> 00:43:17,360 Så sikkert jeg bare kan gjøre tre pil venstre, noe som vil føre 993 00:43:17,360 --> 00:43:18,400 meg til en annen node. 994 00:43:18,400 --> 00:43:19,480 Men hva er det node? 995 00:43:19,480 --> 00:43:22,820 >> Vel, i henhold til denne erklæringen, venstre er bare en peker, slik at bare 996 00:43:22,820 --> 00:43:27,090 betyr at jeg har bestått til søkefunksjonen en annen peker, nemlig 997 00:43:27,090 --> 00:43:30,750 den som representerer min venstre barns treet. 998 00:43:30,750 --> 00:43:36,040 Så i dette tilfellet pekeren til 33, hvis Dette er vårt utvalg innspill mellomtiden, hvis 999 00:43:36,040 --> 00:43:40,740 n er større enn verdien n i gjeldende node i treet, da er jeg 1000 00:43:40,740 --> 00:43:43,370 kommer til å gå videre og punt i den andre retning og bare si, vet jeg ikke 1001 00:43:43,370 --> 00:43:47,280 vite om denne verdien n er i treet, men jeg vet ikke om det er, er det ned min 1002 00:43:47,280 --> 00:43:49,090 høyre gren, så å si. 1003 00:43:49,090 --> 00:43:53,120 Så la meg kalle rekursivt søke, passerer en n igjen, men går i en 1004 00:43:53,120 --> 00:43:54,580 pekeren til høyre for meg barn. 1005 00:43:54,580 --> 00:44:00,020 >> Med andre ord, hvis jeg er for tiden på 55 og jeg ser for 99, vet jeg at 99 1006 00:44:00,020 --> 00:44:04,270 er større enn 55, så akkurat som jeg rev telefonboken uker siden, og vi 1007 00:44:04,270 --> 00:44:07,140 gikk rett, på samme måte er vi kommer til å gå her. 1008 00:44:07,140 --> 00:44:11,960 Og jeg vet ikke om det er ved min høyre barn, og det er ikke, er 77 der, men 1009 00:44:11,960 --> 00:44:13,210 Jeg vet det er i den retningen. 1010 00:44:13,210 --> 00:44:18,770 Så jeg kaller søk på min høyre barn, 77, og la søk figur ut fra 1011 00:44:18,770 --> 00:44:24,950 der hvis 99 i denne vilkårlig eksempel er faktisk der. 1012 00:44:24,950 --> 00:44:26,900 >> Else, hva er den siste saken? 1013 00:44:26,900 --> 00:44:28,620 Hvis treet er null er én sak. 1014 00:44:28,620 --> 00:44:31,890 Hvis n er mindre enn den gjeldende nodens verdien er en annen sak. 1015 00:44:31,890 --> 00:44:35,120 Hvis n er større enn dagens node verdi er et tredje tilfelle. 1016 00:44:35,120 --> 00:44:38,250 Hva er den fjerde og siste saken? 1017 00:44:38,250 --> 00:44:39,480 Jeg tror vi er ute av tilfellene, ikke sant? 1018 00:44:39,480 --> 00:44:44,690 Det må være at n er i gjeldende node at jeg er på. 1019 00:44:44,690 --> 00:44:49,640 >> Så hvis jeg søker etter 55 på dette punktet i historien, den grenen av 1020 00:44:49,640 --> 00:44:51,780 treet ville returnere true. 1021 00:44:51,780 --> 00:44:55,380 Så hva er interessant her er at vi faktisk, i motsetning til uker tidligere, typen vi 1022 00:44:55,380 --> 00:44:56,740 av har to basen tilfeller. 1023 00:44:56,740 --> 00:44:58,300 Og de trenger ikke å alle være på toppen. 1024 00:44:58,300 --> 00:45:01,390 Toppen er en base tilfelle fordi dersom treet er null, det er ingenting å gjøre. 1025 00:45:01,390 --> 00:45:03,410 Bare returnere en hard kodet Verdien av falsk. 1026 00:45:03,410 --> 00:45:07,400 >> Den nederste grenen er liksom den standard, der hvis vi har sjekket for 1027 00:45:07,400 --> 00:45:11,550 null, har vi sjekket om det bør være igjen, men det bør ikke være, har vi 1028 00:45:11,550 --> 00:45:14,640 sjekket om det skulle være riktig, men det bør ikke være, klart at det må være 1029 00:45:14,640 --> 00:45:15,870 akkurat der vi er. 1030 00:45:15,870 --> 00:45:16,780 Det er en base case. 1031 00:45:16,780 --> 00:45:19,920 Så det er to rekursive tilfeller klemt der i midten. 1032 00:45:19,920 --> 00:45:21,630 Men jeg kunne ha skrevet dette i hvilken som helst rekkefølge. 1033 00:45:21,630 --> 00:45:24,520 Jeg tenkte bare at det føltes slags naturlig å først se etter en mulig feil, 1034 00:45:24,520 --> 00:45:28,340 så sjekk igjen, så sjekk høyre, deretter anta at du er på noden 1035 00:45:28,340 --> 00:45:30,630 du faktisk leter etter. 1036 00:45:30,630 --> 00:45:36,240 >> Så hvorfor kan dette være nyttig? 1037 00:45:36,240 --> 00:45:37,910 Så det viser seg - 1038 00:45:37,910 --> 00:45:42,110 og la meg hoppe til en teaser her som er i nettet. 1039 00:45:42,110 --> 00:45:44,920 Vi kommer til å begynne å bruke ikke en programmeringsspråk i starten, men en 1040 00:45:44,920 --> 00:45:46,030 kodespråk. 1041 00:45:46,030 --> 00:45:48,740 Et kodespråk være en som er ligner i ånden til programmering 1042 00:45:48,740 --> 00:45:51,715 språk, men det gir deg ikke den evne til å uttrykke deg logisk. 1043 00:45:51,715 --> 00:45:55,070 Det gir deg bare muligheten til å uttrykke deg strukturelt. 1044 00:45:55,070 --> 00:45:57,960 >> Hvor vil du sette noe på siden, nettsiden? 1045 00:45:57,960 --> 00:45:59,200 Hvilken farge ønsker du å gjøre det? 1046 00:45:59,200 --> 00:46:00,950 Hva skriftstørrelsen ønsker du å gjøre det? 1047 00:46:00,950 --> 00:46:02,970 Hvilke ord har du faktisk ønsker på nettsiden? 1048 00:46:02,970 --> 00:46:04,060 Så det er et kodespråk. 1049 00:46:04,060 --> 00:46:07,690 Men så får vi svært raskt introdusere JavaScript, som er en fullverdig 1050 00:46:07,690 --> 00:46:08,560 programmeringsspråk. 1051 00:46:08,560 --> 00:46:12,530 Svært lik syntaktisk i utseende til C, men det vil ha noen 1052 00:46:12,530 --> 00:46:15,200 nice, kraftigere, mer brukervennlige funksjoner. 1053 00:46:15,200 --> 00:46:18,050 >> Og en av de frustrasjoner på dette punkt i semesteret er at vi vil 1054 00:46:18,050 --> 00:46:22,065 snart gjennomføre stavekontroll i langt færre linjer med kode som bruker andre språk 1055 00:46:22,065 --> 00:46:25,580 enn C i seg selv gjør, men på grunn av for oss vi vil snart forstå. 1056 00:46:25,580 --> 00:46:27,750 Dette vil være den første slike nettside. 1057 00:46:27,750 --> 00:46:30,120 Det vil være helt underwhelming, det første vi gjør. 1058 00:46:30,120 --> 00:46:31,400 Det vil rett og slett si, hallo verden. 1059 00:46:31,400 --> 00:46:34,010 Men hvis du aldri har sett det før, er dette HTML, 1060 00:46:34,010 --> 00:46:35,670 HyperText Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> Hvis du går til en viss menyvalg i mest alle nettlesere, på en nettside på 1062 00:46:39,310 --> 00:46:43,160 internett, kan du se HTML at noen mennesker skrev til 1063 00:46:43,160 --> 00:46:44,400 lage denne websiden. 1064 00:46:44,400 --> 00:46:47,850 Og det sannsynligvis ikke se ut som kort eller så godt som dette. 1065 00:46:47,850 --> 00:46:51,400 Men det vil følge mønsteret av disse åpne braketter og flenger og 1066 00:46:51,400 --> 00:46:53,660 bokstaver og potensielt tall. 1067 00:46:53,660 --> 00:46:56,770 >> Jeg tenkte jeg skulle gi dere en teaser av hva du vil være i stand til å gjøre 1068 00:46:56,770 --> 00:46:57,950 etter å ha tatt CS50. 1069 00:46:57,950 --> 00:47:02,620 La meg gå til cs.harvard.edu / rane, vår egen Rob Bowden hjemmeside. 1070 00:47:02,620 --> 00:47:06,080 Han gjorde dette for oss. 1071 00:47:06,080 --> 00:47:07,490 Så du vil snart være i stand til å gjøre det. 1072 00:47:07,490 --> 00:47:10,660 Og også, hva du har hørt denne morgenen - 1073 00:47:10,660 --> 00:47:12,480 hva du har hørt denne morgenen - 1074 00:47:12,480 --> 00:47:13,780 >> [HAMSTER DANCE MUSIC] 1075 00:47:13,780 --> 00:47:15,702 >> - Vil du være i stand til å gjøre dette. 1076 00:47:15,702 --> 00:47:16,790 Som venter oss på onsdag. 1077 00:47:16,790 --> 00:47:17,791 Vi vil se deg da. 1078 00:47:17,791 --> 00:47:22,950 >> [HAMSTER DANCE MUSIC] 1079 00:47:22,950 --> 00:47:24,300 DAVID MALAN: Ved neste CS50 - 1080 00:47:24,300 --> 00:47:31,670