1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID MALAN: Okej. 3 00:00:12,250 --> 00:00:13,860 Välkommen tillbaka till CS50. 4 00:00:13,860 --> 00:00:16,190 Detta är början på vecka 8. 5 00:00:16,190 --> 00:00:21,320 Och minns att problemet set 5 slutade med lite av en utmaning. 6 00:00:21,320 --> 00:00:25,210 Så antar att du återhämtat alla dina Undervisning Fellows och CA: s fotografier 7 00:00:25,210 --> 00:00:30,480 i card.raw filen, har du rätt att nu hitta alla dessa människor, och 8 00:00:30,480 --> 00:00:34,510 en lycklig vinnare kommer att gå hem med en av dessa saker, språnget rörelse 9 00:00:34,510 --> 00:00:37,450 enhet som du kan använda för final projekt, till exempel. 10 00:00:37,450 --> 00:00:39,860 >> Detta, varje år, leder till en bit av creepiness. 11 00:00:39,860 --> 00:00:43,480 Och så vad jag trodde jag skulle göra är att dela med dig några av de anmärkningar som har 12 00:00:43,480 --> 00:00:47,370 gått fram och tillbaka över personalen listan över sent. 13 00:00:47,370 --> 00:00:51,110 Till exempel, bara i går kväll, citat unquote, från en av personalen 14 00:00:51,110 --> 00:00:55,000 medlemmar, "Jag hade bara en elev knock på min dörr för att ta ett foto med mig. 15 00:00:55,000 --> 00:00:59,020 Stalkers, säger jag. "Började ganska beskrivande och sedan vi flyttade 16 00:00:59,020 --> 00:01:02,830 till, en timme eller så senare, "Jag hade en studenten väntar på mig efter avsnitt 17 00:01:02,830 --> 00:01:06,080 och han hade alla våra namn och foton på några pappersark. "Okej. 18 00:01:06,080 --> 00:01:09,230 Så organiseras, men inte allt som obehagligt ännu. 19 00:01:09,230 --> 00:01:12,520 >> Sedan, "jag var ute på stan i helgen, och när jag kom tillbaka, det var en i 20 00:01:12,520 --> 00:01:12,630 min 21 00:01:12,630 --> 00:01:16,740 sovrummet. "[SKRATT] 22 00:01:16,740 --> 00:01:20,410 DAVID MALAN: Nästa citat från en personal ledamot, "en elev kom till mitt hus på 23 00:01:20,410 --> 00:01:25,330 Somerville klockan 4 i morse. "Next personal, "jag fick till mitt hotell i San 24 00:01:25,330 --> 00:01:30,016 Francisco och en student väntade mig i lobbyn med tre digitala systemkameror. " 25 00:01:30,016 --> 00:01:31,510 Typ av kamera. 26 00:01:31,510 --> 00:01:34,980 "Jag är inte ens på personal här terminen, men en student bröt sig in i mitt hus här 27 00:01:34,980 --> 00:01:40,480 morgon och spelade in alltihop med Google Glass. "Och sedan sist, 28 00:01:40,480 --> 00:01:43,650 "Minst 12 människor var ivrigt väntar på mig när jag kom ut ur min 29 00:01:43,650 --> 00:01:44,800 limo, och sedan jag 30 00:01:44,800 --> 00:01:46,970 vaknade. "Okej. 31 00:01:46,970 --> 00:01:57,690 Så bland fotografierna, som ni kanske minns, är denna karl här, vem du 32 00:01:57,690 --> 00:02:01,850 kanske vet så Milo Banana, som bor med Lauren Carvalho, vårt huvud 33 00:02:01,850 --> 00:02:02,905 undervisning Fellow. 34 00:02:02,905 --> 00:02:05,170 Milo, Milo, kom hit pojken. 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 Märk väl, han bär Google Glass, så Vi ska visa dig allt detta efter. 38 00:02:12,230 --> 00:02:16,190 Så det här är Milo om du vill ta ett foto med honom efteråt. 39 00:02:16,190 --> 00:02:18,240 Om du vill titta ut på publiken där. 40 00:02:18,240 --> 00:02:19,430 OK. 41 00:02:19,430 --> 00:02:20,200 Det är bra tagning. 42 00:02:20,200 --> 00:02:22,556 Tja, Milo Banana. 43 00:02:22,556 --> 00:02:23,941 Åh, gör inte det. 44 00:02:23,941 --> 00:02:29,020 >> [SKRATT] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 Så ett ord och sedan på vad som väntar, för som vi börjar övergången, 47 00:02:34,550 --> 00:02:38,410 denna vecka specifikt, från C i en kommandoraden miljö till PHP och 48 00:02:38,410 --> 00:02:42,720 JavaScript och SQL och HTML och CSS i en webbaserad miljö, vi ska vara 49 00:02:42,720 --> 00:02:44,490 utrusta dig med all mer kunskap för 50 00:02:44,490 --> 00:02:46,010 potentiella slutliga projekt. 51 00:02:46,010 --> 00:02:49,240 Mot detta har naturligtvis en traditionen att hålla seminarier som 52 00:02:49,240 --> 00:02:50,950 är på tangentiella ämnen till kursen. 53 00:02:50,950 --> 00:02:54,330 Mycket relaterade till programmering och applikationsutveckling och så vidare, men 54 00:02:54,330 --> 00:02:57,010 inte nödvändigtvis utforskas genom kursens egen kursplan. 55 00:02:57,010 --> 00:03:00,250 >> Så om du kan vara intresserad av en eller mer av årets seminarier, 56 00:03:00,250 --> 00:03:02,530 registrera dig på cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Det finns äldre seminarier vid cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 Och på deltagarlistan hittills i år är fantastiska Web Apps med Ruby on 59 00:03:10,620 --> 00:03:13,580 Skenor, som är ett alternativ språk till PHP. 60 00:03:13,580 --> 00:03:14,900 Datorlingvistik. 61 00:03:14,900 --> 00:03:18,710 Introduktion till iOS, som är den plattform som används för iPhone och 62 00:03:18,710 --> 00:03:19,850 iPad utveckling. 63 00:03:19,850 --> 00:03:22,890 JavaScript för Web Apps kommer vi att täcka det, men i detta seminarium kommer du att gå 64 00:03:22,890 --> 00:03:24,070 in mer i detalj. 65 00:03:24,070 --> 00:03:27,390 >> Leap Motion, så vi ska faktiskt ha lite av våra vänner från Leap Motion, 66 00:03:27,390 --> 00:03:29,160 företaget självt, ansluta sig till oss. 67 00:03:29,160 --> 00:03:31,800 I morgon, i själva verket, för att ge en hands-on seminarium om 68 00:03:31,800 --> 00:03:33,320 av intresse för dig. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, en alternativ teknik för med hjälp av JavaScript inte i en webbläsare, 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 är mycket i samma anda som väl. 72 00:03:42,110 --> 00:03:43,650 Sleek Android Design. 73 00:03:43,650 --> 00:03:46,990 Android är ett mycket populärt alternativ till iOS och Windows Phone 74 00:03:46,990 --> 00:03:48,790 och andra mobila plattformar. 75 00:03:48,790 --> 00:03:51,180 Och Web Security Active Defense. 76 00:03:51,180 --> 00:03:54,590 >> Så i själva verket, om du vill att engagera sig i detta, låt mig 77 00:03:54,590 --> 00:03:55,840 anteckna detta. 78 00:03:55,840 --> 00:03:57,790 Vi är mycket glada att kunna säga att våra vänner på Leap 79 00:03:57,790 --> 00:03:59,140 Motion, vilket är en start - 80 00:03:59,140 --> 00:04:01,300 denna enhet egentligen bara kom ut för några månader sedan - 81 00:04:01,300 --> 00:04:05,960 har artigt donerat 30 sådana anordningar till klassen för så många studenter, om 82 00:04:05,960 --> 00:04:08,670 du vill låna hårdvaran mot terminen slut och använda den för 83 00:04:08,670 --> 00:04:10,390 en verklig slutprojekt. 84 00:04:10,390 --> 00:04:11,890 De stöder ett antal olika språk. 85 00:04:11,890 --> 00:04:16,040 Ingen av dem C, ingen av dem PHP, så förverkliga ett eller flera av dessa seminarier 86 00:04:16,040 --> 00:04:16,899 kan visa sig intressant. 87 00:04:16,899 --> 00:04:19,730 Och alla av dem kommer att filmas i Om du inte kan 88 00:04:19,730 --> 00:04:21,380 att närvara personligen. 89 00:04:21,380 --> 00:04:25,000 Schemat meddelas via e-post som vi stelna rum. 90 00:04:25,000 --> 00:04:28,460 >> Och slutligen, om du går till projects.cs.50.net, detta är en webbplats 91 00:04:28,460 --> 00:04:31,450 vi underhåller varje år som vi inbjuder folk från gemenskapen, fakultet, 92 00:04:31,450 --> 00:04:36,420 avdelningar, personal och båda i en utsida av CS50 till 93 00:04:36,420 --> 00:04:37,730 föreslå projektidéer. 94 00:04:37,730 --> 00:04:39,050 Saker av intresse för studentgrupper. 95 00:04:39,050 --> 00:04:40,600 Saker av intresse för avdelningar. 96 00:04:40,600 --> 00:04:43,990 Så vänder det om du kämpar med osäkerhet om vad du 97 00:04:43,990 --> 00:04:46,700 själv skulle vilja angripa. 98 00:04:46,700 --> 00:04:51,760 >> Så förra gången vi införde en tvekan mer komplex datastruktur än vi skulle 99 00:04:51,760 --> 00:04:53,300 ses i veckor tidigare. 100 00:04:53,300 --> 00:04:56,550 Vi hade använt arrayer ganska glatt som ett användbart om 101 00:04:56,550 --> 00:04:58,160 simplistic datastruktur. 102 00:04:58,160 --> 00:05:00,570 Sedan vi införde dessa, vilket givetvis är länkade listor. 103 00:05:00,570 --> 00:05:05,470 Och vad som var ett av motiven för införa denna datastruktur? 104 00:05:05,470 --> 00:05:06,930 Yeah? 105 00:05:06,930 --> 00:05:07,250 Vad är det? 106 00:05:07,250 --> 00:05:08,080 >> Publik: Dynamisk storlek. 107 00:05:08,080 --> 00:05:09,040 >> DAVID MALAN: Dynamisk storlek. 108 00:05:09,040 --> 00:05:11,890 Så medan array, måste du vet dess storlek i förväg när 109 00:05:11,890 --> 00:05:12,740 du fördela det. 110 00:05:12,740 --> 00:05:14,380 I länkad lista, gör du inte måste veta det. 111 00:05:14,380 --> 00:05:17,610 Du kan bara malloc, eller mer generellt, allokera ytterligare 112 00:05:17,610 --> 00:05:20,720 nod, så att säga, varje gång du vill infoga mer data. 113 00:05:20,720 --> 00:05:22,670 Och noden har ingen förutbestämd mening. 114 00:05:22,670 --> 00:05:25,580 Det är bara en allmän term som beskriver någon form av behållare som vi är 115 00:05:25,580 --> 00:05:29,610 användning i vår datastruktur för att lagra vissa objekt av intresse, vilket i detta 116 00:05:29,610 --> 00:05:31,750 fall råkar vara heltal. 117 00:05:31,750 --> 00:05:33,160 >> Men det finns alltid en avvägning. 118 00:05:33,160 --> 00:05:38,070 Så vi får dynamiska storlekar av data struktur, men vilket pris ska vi betala? 119 00:05:38,070 --> 00:05:40,040 Vad är nackdelen med länkade listor? 120 00:05:40,040 --> 00:05:41,006 Yeah? 121 00:05:41,006 --> 00:05:41,980 >> Publik: Kräver mer minne. 122 00:05:41,980 --> 00:05:44,240 >> DAVID MALAN: Det krävs mer minne, exakt hur? 123 00:05:44,240 --> 00:05:46,440 >> Publik: [OHÖRBAR]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID MALAN: Exakt. 125 00:05:47,050 --> 00:05:50,460 Så nu har vi pekare tar upp extra minne som vi tidigare 126 00:05:50,460 --> 00:05:53,040 inte behöver, eftersom fördelen av en matris, naturligtvis, är att 127 00:05:53,040 --> 00:05:54,860 allt är sammanhängande, rygg att rygg mot rygg, vilket 128 00:05:54,860 --> 00:05:56,380 ger dig direktåtkomst. 129 00:05:56,380 --> 00:06:00,710 Eftersom bara genom att använda klammer notation, eller mer tekniskt pekare 130 00:06:00,710 --> 00:06:03,580 aritmetik, mycket enkel addition, kan du komma åt alla 131 00:06:03,580 --> 00:06:05,700 element i konstant tid. 132 00:06:05,700 --> 00:06:08,975 Och i själva verket är den sortens antyda annat pris som vi betalar med en 133 00:06:08,975 --> 00:06:09,760 länkad lista. 134 00:06:09,760 --> 00:06:13,890 >> Vad händer med gångtiden något liknande Search, om jag vill 135 00:06:13,890 --> 00:06:17,270 hitta något värde och inne av en länkad lista? 136 00:06:17,270 --> 00:06:20,290 Vad min gångtid bli? 137 00:06:20,290 --> 00:06:21,560 Big O n. 138 00:06:21,560 --> 00:06:24,060 Om det sorteras? 139 00:06:24,060 --> 00:06:25,440 Vad händer om den datastruktur är sorterade? 140 00:06:25,440 --> 00:06:28,640 Kan jag göra bättre än stora O n för att söka? 141 00:06:28,640 --> 00:06:31,700 Nej, eftersom det i värsta fall kan det mycket väl ska sorteras, men antalet 142 00:06:31,700 --> 00:06:32,950 du letar efter kan vara stort. 143 00:06:32,950 --> 00:06:35,370 Det kan vara numret 100, vilket kanske råkar vara alla 144 00:06:35,370 --> 00:06:36,410 vägen i slutet. 145 00:06:36,410 --> 00:06:39,950 Och eftersom du kan bara få en länkad Listan i denna implementering av 146 00:06:39,950 --> 00:06:42,690 vägen för dess första noden, du fortfarande lite av lycka. 147 00:06:42,690 --> 00:06:47,450 Du måste korsa hela från första till sista för att finna 148 00:06:47,450 --> 00:06:49,150 det stora värde som 100. 149 00:06:49,150 --> 00:06:51,350 Eller för att avgöra om det är inte ens där. 150 00:06:51,350 --> 00:06:55,960 >> Så vi kan inte göra vad algoritmen i en data struktur som ser ut så här? 151 00:06:55,960 --> 00:06:59,460 Vi kan inte göra binär sökning, eftersom binär sökning krävs att vi hade 152 00:06:59,460 --> 00:07:00,740 random access. 153 00:07:00,740 --> 00:07:04,500 Vi kunde bara hoppa från plats till plats utan att behöva följa 154 00:07:04,500 --> 00:07:07,080 dessa brödsmulor i form av alla dessa tips. 155 00:07:07,080 --> 00:07:08,300 >> Nu, hur vi genomför detta? 156 00:07:08,300 --> 00:07:12,830 Tja, om vi går till skärmen här, om Vi kan snabbt reimplement dessa data 157 00:07:12,830 --> 00:07:13,440 struktur - 158 00:07:13,440 --> 00:07:15,670 min handstil är inte så stor här, men vi ska försöka. 159 00:07:15,670 --> 00:07:22,030 Så typedef struct, och vad gjorde jag vill kalla den här saken här uppe? 160 00:07:22,030 --> 00:07:22,960 Nod. 161 00:07:22,960 --> 00:07:24,580 Så jag ska komma igång. 162 00:07:24,580 --> 00:07:27,860 Och nu, vad som behöver vara inne i datastrukturen för att var för sig 163 00:07:27,860 --> 00:07:28,430 länkad lista? 164 00:07:28,430 --> 00:07:29,950 Hur många områden? 165 00:07:29,950 --> 00:07:30,450 >> Så två. 166 00:07:30,450 --> 00:07:31,570 Man är ganska lätt. 167 00:07:31,570 --> 00:07:33,050 Så int n. 168 00:07:33,050 --> 00:07:35,930 Och vi kan kalla n vad vi vill, men det bör vara en int om vi 169 00:07:35,930 --> 00:07:37,660 genomföra en länkad lista för ints. 170 00:07:37,660 --> 00:07:41,920 Och nu vad gör den andra fältet måste vara? 171 00:07:41,920 --> 00:07:43,460 Struct nod *. 172 00:07:43,460 --> 00:07:50,570 Så om jag gör struct node *, och sedan jag kan kalla detta också vad jag vill, 173 00:07:50,570 --> 00:07:53,510 men bara för att vara tydlig jag ringer det nästa, som vi har gjort. 174 00:07:53,510 --> 00:07:55,270 Och sedan ska jag stänga mina klammerparenteser. 175 00:07:55,270 --> 00:08:00,700 >> Och nu, som förra gången, Jag satte nod här nere. 176 00:08:00,700 --> 00:08:03,830 Men om jag förklara detta är som en nod, varför jag bry vara så 177 00:08:03,830 --> 00:08:07,320 verbose här förklara struct nod * nästa, i motsats 178 00:08:07,320 --> 00:08:09,210 att bara nod * nästa? 179 00:08:09,210 --> 00:08:09,904 Yeah? 180 00:08:09,904 --> 00:08:12,810 >> Publik: [OHÖRBAR]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID MALAN: Exakt. 182 00:08:14,050 --> 00:08:14,530 Exakt. 183 00:08:14,530 --> 00:08:18,320 Eftersom C tar verkligen du bokstavligen och bara ser definitionen av noden 184 00:08:18,320 --> 00:08:21,230 vägen ner hit, kan du inte hänvisa till det här uppe. 185 00:08:21,230 --> 00:08:24,760 Så vi har denna typ av förebyggande förklaring här, vilket är visserligen 186 00:08:24,760 --> 00:08:25,390 mer mångordig. 187 00:08:25,390 --> 00:08:27,810 Struct nod, det betyder Vi kan nu komma åt det 188 00:08:27,810 --> 00:08:29,760 insidan av datastruktur. 189 00:08:29,760 --> 00:08:33,370 >> Och som en parentes, eftersom detta är blir lite mer subjektiv nu, 190 00:08:33,370 --> 00:08:36,230 stjärnan kan tekniskt gå hit, det kan gå här, kan det 191 00:08:36,230 --> 00:08:37,179 ens gå i mitten. 192 00:08:37,179 --> 00:08:39,890 Vi har antagit, i stil guide för kursen, konventionen för att sätta 193 00:08:39,890 --> 00:08:42,299 stjärnan bredvid datan typ, som i detta fall, 194 00:08:42,299 --> 00:08:43,460 skulle vara struct nod. 195 00:08:43,460 --> 00:08:46,620 Men inser i många läroböcker och online referenser, kanske du faktiskt 196 00:08:46,620 --> 00:08:48,450 se det på den andra sidan. 197 00:08:48,450 --> 00:08:52,200 Men bara att inse att båda kommer faktiskt arbete och du bör helt enkelt vara 198 00:08:52,200 --> 00:08:52,970 konsekvent. 199 00:08:52,970 --> 00:08:53,580 >> Okej. 200 00:08:53,580 --> 00:08:55,630 Så det var vår deklaration av struct nod. 201 00:08:55,630 --> 00:08:59,430 Men sedan vi började göra mer sofistikerade saker. 202 00:08:59,430 --> 00:09:03,410 Till exempel, beslutade vi att införa något som liknar en hash-tabell. 203 00:09:03,410 --> 00:09:08,160 Så här är en hash tabell av storlek n, indexeras från 0 uppe till vänster till n 204 00:09:08,160 --> 00:09:09,690 minus 1 längst ned till vänster. 205 00:09:09,690 --> 00:09:11,640 Detta kan vara en hash bord för någonting. 206 00:09:11,640 --> 00:09:15,340 Men vilka typer av saker vi pratar om att använda en hash-tabell för? 207 00:09:15,340 --> 00:09:18,370 Lagra vad? 208 00:09:18,370 --> 00:09:18,800 >> Names. 209 00:09:18,800 --> 00:09:20,870 Vi kunde göra namn som vi gjorde förra gången. 210 00:09:20,870 --> 00:09:22,200 Och egentligen, kan du lagra något. 211 00:09:22,200 --> 00:09:24,640 Och vi får se detta igen PHP och JavaScript. 212 00:09:24,640 --> 00:09:28,550 En hash-tabell är en trevlig slags schweiziska Armékniv som låter dig lagra 213 00:09:28,550 --> 00:09:33,690 ganska mycket vad du vill inne i det genom att associera tangenter med värden. 214 00:09:33,690 --> 00:09:34,770 Nycklar med värden. 215 00:09:34,770 --> 00:09:37,800 >> Nu i detta enkla fall, vår nycklar är bara siffror. 216 00:09:37,800 --> 00:09:40,380 Vi genomför en hash bord som en matris. 217 00:09:40,380 --> 00:09:43,500 Och så är tangenterna 0, 1, 2, och så vidare. 218 00:09:43,500 --> 00:09:47,200 Och så vi, som människor, beslutade förra vecka som ni vet vad, om vi är 219 00:09:47,200 --> 00:09:50,410 går att lagra namn, låt oss bara godtyckligt, men ganska rimligt, 220 00:09:50,410 --> 00:09:54,680 anta att Alice, en Ett namn, kommer bara att indexeras i 0. 221 00:09:54,680 --> 00:09:58,030 Och Bob, ett B-namn, kommer att indexeras till 1, och så vidare. 222 00:09:58,030 --> 00:10:02,490 Så vi hade en mappning mellan ingångar, som är strängar, och hash 223 00:10:02,490 --> 00:10:04,560 platser, vilket är siffror. 224 00:10:04,560 --> 00:10:07,740 >> Så att processen är allmänt känd som en hashfunktion, och du kan verkligen 225 00:10:07,740 --> 00:10:09,130 genomföra det i koden. 226 00:10:09,130 --> 00:10:12,080 Om jag ville genomföra en hashfunktion som gör exakt vad vi 227 00:10:12,080 --> 00:10:17,070 just beskrivits från förra gången, kan jag deklarera en funktion som tar, som 228 00:10:17,070 --> 00:10:18,330 ingång till exempel - 229 00:10:18,330 --> 00:10:22,190 och låt oss göra detta på detta Skärmen hit. 230 00:10:22,190 --> 00:10:26,180 Om jag ville genomföra en hash funktion, kan jag säga 231 00:10:26,180 --> 00:10:27,410 ungefär så här. 232 00:10:27,410 --> 00:10:29,030 >> Det kommer att returnera en int. 233 00:10:29,030 --> 00:10:33,600 Det kommer att kallas hash, och det är kommer att acceptera som argument en 234 00:10:33,600 --> 00:10:38,920 sträng, eller vi kan vara mer rätt nu, och säger char *, ska vi kalla det är. 235 00:10:38,920 --> 00:10:43,840 Och så all denna funktion har att göra, Ytterst är tillbaka en int. 236 00:10:43,840 --> 00:10:45,990 Nu, hur det skulle kunna inte vara så tydlig. 237 00:10:45,990 --> 00:10:49,510 Jag kommer att genomföra detta utan form av felkontroll just nu. 238 00:10:49,510 --> 00:10:55,740 Jag kommer bara att blint säga, tillbaka vad är er konsol 0, minus, 239 00:10:55,740 --> 00:10:58,850 låt oss säga, huvudstad semikolon. 240 00:10:58,850 --> 00:10:59,960 >> Helt trasig. 241 00:10:59,960 --> 00:11:02,620 Det är inte perfekt eftersom en, tänk om s är null? 242 00:11:02,620 --> 00:11:04,000 Dåliga saker kommer att hända. 243 00:11:04,000 --> 00:11:07,940 Två, vad händer om den första bokstaven i det här Namnet är inte stor bokstav? 244 00:11:07,940 --> 00:11:09,860 Det kommer inte att vända väl ut heller. 245 00:11:09,860 --> 00:11:11,970 Det kan vara en liten bokstav eller inte en bokstav alls. 246 00:11:11,970 --> 00:11:15,520 Så helt utrymme för förbättringar, men detta är den grundläggande idén. 247 00:11:15,520 --> 00:11:19,010 >> Vad vi beskrivit förra veckan muntligt som bara en process för att kartlägga Alice till 248 00:11:19,010 --> 00:11:23,360 0 och Bob till 1 kan uttryckas säkert mer formulaically som en C 249 00:11:23,360 --> 00:11:24,320 fungera här. 250 00:11:24,320 --> 00:11:28,630 Ringde igen hash, tar en sträng som ingång, och sedan på något sätt gör något 251 00:11:28,630 --> 00:11:31,020 med den ingången för att producera en utsignal. 252 00:11:31,020 --> 00:11:34,130 Inte olikt vårt svarta lådan beskrivning att vi har länge gjort. 253 00:11:34,130 --> 00:11:36,550 Jag vet inte hur detta kan vara arbetar under huven. 254 00:11:36,550 --> 00:11:40,120 >> För problem 6 set, en av utmaningarna är för dig att bestämma vad 255 00:11:40,120 --> 00:11:41,920 kommer din hashfunktion vara? 256 00:11:41,920 --> 00:11:45,760 Vad kommer att vara inne i det svarta box, och förmodligen kommer det att bli en 257 00:11:45,760 --> 00:11:50,380 lite mer intressant än detta, och definitivt mer benägna att fel 258 00:11:50,380 --> 00:11:53,180 kontroll än detta genomförande. 259 00:11:53,180 --> 00:11:54,580 >> Men problem kan uppstå, eller hur? 260 00:11:54,580 --> 00:11:57,760 Om vi ​​har en datastruktur som denna en, vad är ett av de problem som 261 00:11:57,760 --> 00:12:01,600 du kan stöta på under tiden som du sätter fler och fler namn till 262 00:12:01,600 --> 00:12:02,880 hash table? 263 00:12:02,880 --> 00:12:04,630 Du får kollisioner, rätt? 264 00:12:04,630 --> 00:12:07,560 Vad händer om du har Alice och Aron, två personer vars namn hände 265 00:12:07,560 --> 00:12:08,190 att börja med A? 266 00:12:08,190 --> 00:12:11,660 Detta väcker frågan, där du sätta den andra ett sådant namn? 267 00:12:11,660 --> 00:12:15,050 >> Tja, kanske du naivt bara lägga den där Bob hör hemma, men då Bob är 268 00:12:15,050 --> 00:12:17,300 sorts skruvas om du försöker sätta sitt namn bredvid och 269 00:12:17,300 --> 00:12:18,240 det finns ingen plats för honom. 270 00:12:18,240 --> 00:12:21,400 Så du kan sätta Bob där Charlie är, och ni kan föreställa er detta mycket snabbt 271 00:12:21,400 --> 00:12:23,020 delegera till en bit av en enda röra. 272 00:12:23,020 --> 00:12:25,600 Något linjär i slutet, där du bara att söka på hela 273 00:12:25,600 --> 00:12:28,190 letar efter Alice eller Bob eller Aaron eller Charlie. 274 00:12:28,190 --> 00:12:33,230 >> Så istället vi föreslog, i stället för bara linjärt sondering för öppna ytor 275 00:12:33,230 --> 00:12:36,450 och plopping namnen där, vi föreslagit ett snyggare tillvägagångssätt. 276 00:12:36,450 --> 00:12:41,740 En hash table genomförs fortfarande med en samling av index, men datatypen för 277 00:12:41,740 --> 00:12:44,500 dessa index var nu pekare. 278 00:12:44,500 --> 00:12:47,360 Pekare till vad? 279 00:12:47,360 --> 00:12:48,730 Pekare till länkade listor. 280 00:12:48,730 --> 00:12:53,330 >> Därför minns att en länkad lista är egentligen bara en pekare till en nod, och 281 00:12:53,330 --> 00:12:57,110 noden har en nästa fält, och den noden har en nästa fält, och så vidare. 282 00:12:57,110 --> 00:13:00,690 Så du kan nu tänka på denna array på den vänstra sidan av en hash-tabell som 283 00:13:00,690 --> 00:13:01,820 vilket leder till en länkad lista. 284 00:13:01,820 --> 00:13:07,000 Den fördelen är om du får ett kollision mellan Alice och Aron, 285 00:13:07,000 --> 00:13:09,300 vad gör du med den andra personen? 286 00:13:09,300 --> 00:13:14,150 Du fäster bara honom eller henne till ände eller ens början 287 00:13:14,150 --> 00:13:15,490 av den länkade listan. 288 00:13:15,490 --> 00:13:17,340 >> Och faktiskt, låt oss bara nudel genom som för bara en sekund. 289 00:13:17,340 --> 00:13:18,640 Vart skulle göra det bästa bemärkelse? 290 00:13:18,640 --> 00:13:22,060 Om jag sätter Alice och hon hamnar på den första platsen, så jag försöker 291 00:13:22,060 --> 00:13:25,310 infoga Arons namn, och det finns uppenbarligen en kollision, ska jag sätta 292 00:13:25,310 --> 00:13:27,400 honom i början av den länkade listan? 293 00:13:27,400 --> 00:13:30,944 Det är på den första platsen, eller i slutet? 294 00:13:30,944 --> 00:13:31,440 >> Publik: [OHÖRBAR]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID MALAN: OK. 296 00:13:31,990 --> 00:13:32,490 Jag hörde början. 297 00:13:32,490 --> 00:13:33,903 Varför i början? 298 00:13:33,903 --> 00:13:34,750 >> Publik: [OHÖRBAR]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID MALAN: OK. 300 00:13:34,940 --> 00:13:36,520 Det är alfabetiskt, så det är trevligt. 301 00:13:36,520 --> 00:13:37,330 Det är en bra egenskap. 302 00:13:37,330 --> 00:13:39,335 Det kommer att spara mig lite tid potentiellt. 303 00:13:39,335 --> 00:13:43,290 Det kommer inte låta mig göra binär sökning, men jag skulle åtminstone kunna bryta ut 304 00:13:43,290 --> 00:13:47,340 av en loop om jag inser, ja, jag är långt Tidigare var Aaron skulle vara i detta 305 00:13:47,340 --> 00:13:48,310 sorterade länkad lista. 306 00:13:48,310 --> 00:13:50,360 Jag behöver inte slösa min tid på att leta hela vägen till slutet. 307 00:13:50,360 --> 00:13:51,530 Så det är rimligt. 308 00:13:51,530 --> 00:13:54,710 Varför annars kanske du vill infoga det krockande namnet på 309 00:13:54,710 --> 00:13:56,660 början av listan? 310 00:13:56,660 --> 00:13:57,397 Vad är det? 311 00:13:57,397 --> 00:13:58,680 >> Publik: [OHÖRBAR]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID MALAN: Det kan ta lång tid att komma till slutet av listan. 313 00:14:00,820 --> 00:14:02,490 Och i själva verket, längre och längre. 314 00:14:02,490 --> 00:14:04,920 Ju fler namn som du infogar att börja med A, ju längre 315 00:14:04,920 --> 00:14:06,280 kedjan kommer att få. 316 00:14:06,280 --> 00:14:07,890 Ju längre det länkade Listan kommer att få. 317 00:14:07,890 --> 00:14:09,420 Så du är egentligen bara slösar bort din tid. 318 00:14:09,420 --> 00:14:14,070 Kanske är du bättre bevara konstant isättning tid, big O 1, 319 00:14:14,070 --> 00:14:18,470 genom att alltid sätta kolliderande namn på början av den länkade listan, 320 00:14:18,470 --> 00:14:21,230 och inte oroa så mycket om sortering. 321 00:14:21,230 --> 00:14:22,600 >> Vad är det bästa svaret? 322 00:14:22,600 --> 00:14:23,320 Det är oklart. 323 00:14:23,320 --> 00:14:26,140 Den typ av beror på vad distributionen är, vad mönstret är 324 00:14:26,140 --> 00:14:27,850 av de namn du sätter. 325 00:14:27,850 --> 00:14:29,430 Det är inte nödvändigtvis ett självklart svar. 326 00:14:29,430 --> 00:14:33,100 Men här, igen, är en design tillfälle. 327 00:14:33,100 --> 00:14:37,220 >> Så vi sedan tittade på den här saken, som är egentligen den andra stora chans 328 00:14:37,220 --> 00:14:38,180 för p-set 6. 329 00:14:38,180 --> 00:14:41,770 Och inse, om du inte redan har gjort, Zamyla dyker ner i båda dessa, hash 330 00:14:41,770 --> 00:14:43,260 bord och försöker, i mer detalj. 331 00:14:43,260 --> 00:14:45,630 Och video genomgång är inbäddade i p-set spec. 332 00:14:45,630 --> 00:14:46,590 Detta var en trie - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. Och vad var intressant detta var att gångtid 334 00:14:51,670 --> 00:14:59,510 att söka efter ett namn, som Maxwell förra gången, var stort O vad? 335 00:14:59,510 --> 00:15:01,040 Vad är det? 336 00:15:01,040 --> 00:15:01,920 >> Målgrupp: Antalet bokstäver. 337 00:15:01,920 --> 00:15:02,550 >> DAVID MALAN: Antal bokstäver. 338 00:15:02,550 --> 00:15:03,210 Jag hörde två saker. 339 00:15:03,210 --> 00:15:04,630 Antal bokstäver och konstant tid. 340 00:15:04,630 --> 00:15:05,540 Så låt oss gå med det första. 341 00:15:05,540 --> 00:15:06,410 Antalet bokstäver. 342 00:15:06,410 --> 00:15:10,195 Nåväl, detta är datastruktur, återkallelse, som ett träd, ett släktträd, vart och ett av 343 00:15:10,195 --> 00:15:12,860 vars noder består av matriser. 344 00:15:12,860 --> 00:15:16,300 Och dessa matriser är pekare till andra sådana noder, eller andra sådana 345 00:15:16,300 --> 00:15:17,670 arrayer i trädet. 346 00:15:17,670 --> 00:15:22,890 >> Så om vi ville sedan bestämma om Maxwell är här, kan jag gå 347 00:15:22,890 --> 00:15:26,890 till den första gruppen, högst upp på trädet, den så kallade roten, toppen av 348 00:15:26,890 --> 00:15:30,521 den trie och följ sedan m pekaren, sedan en pekare, då x, 349 00:15:30,521 --> 00:15:31,710 w, e, l, l. 350 00:15:31,710 --> 00:15:34,910 Och sen när jag ser någon speciell symbol, betecknas här som en triangel. 351 00:15:34,910 --> 00:15:38,480 I koden ser du föreslår vi att du implementeras som en bool, bara säga ja 352 00:15:38,480 --> 00:15:40,540 eller nej, stannar ett ord här. 353 00:15:40,540 --> 00:15:45,270 >> Nåväl, när vi har gått till M-A-X-W-E-L-L, känns som sju, kanske 354 00:15:45,270 --> 00:15:48,910 åtta om vi går en förbi, åtta åtgärder för att hitta Maxwell. 355 00:15:48,910 --> 00:15:53,050 Eller låt oss kalla det K. Men minns förra tid, hävdade jag att om det finns 356 00:15:53,050 --> 00:15:57,540 realistiskt en maximal längd på en ord, liksom 40-del-udda karaktärer, en 357 00:15:57,540 --> 00:16:00,810 maximala längden innebär ett konstant värde. 358 00:16:00,810 --> 00:16:05,770 Så egentligen, ja, det är tekniskt Big O av 8 7 eller, eller riktigt stora O K. Men 359 00:16:05,770 --> 00:16:09,420 om det finns en ändlig tak för vad K kan vara, det är en konstant. 360 00:16:09,420 --> 00:16:12,080 Och så det är stor O av 1 vid slutet av dagen. 361 00:16:12,080 --> 00:16:13,040 >> Inte i den verkliga världen. 362 00:16:13,040 --> 00:16:15,960 Inte när du börjar faktiskt titta din klocka som ditt program körs. 363 00:16:15,960 --> 00:16:20,690 Det kommer absolut att bli lite långsammare än verkligt konstant 364 00:16:20,690 --> 00:16:21,840 tid med ett steg. 365 00:16:21,840 --> 00:16:25,540 Det kommer att bli sju eller åtta steg, men ändå det är mycket, mycket bättre 366 00:16:25,540 --> 00:16:30,080 än en algoritm som Big O n som beror på storleken på vad som finns i 367 00:16:30,080 --> 00:16:31,220 datastruktur. 368 00:16:31,220 --> 00:16:34,970 >> Lägg märke till upp här är att vi kan sätta in en miljon fler namn i detta 369 00:16:34,970 --> 00:16:38,170 datastruktur, men hur många fler steg det kommer att ta oss att hitta 370 00:16:38,170 --> 00:16:40,480 Maxwell i så fall? 371 00:16:40,480 --> 00:16:40,780 Inga. 372 00:16:40,780 --> 00:16:41,820 Han är opåverkad. 373 00:16:41,820 --> 00:16:45,480 Och hittills, jag tror inte vi har sett ett exempel på en datastruktur eller 374 00:16:45,480 --> 00:16:48,560 algoritm som var helt opåverkad av externa 375 00:16:48,560 --> 00:16:50,040 beteenden som. 376 00:16:50,040 --> 00:16:51,160 Men detta kan inte vara fantastiskt. 377 00:16:51,160 --> 00:16:52,900 Detta kan inte vara den enda lösningen för p-set 378 00:16:52,900 --> 00:16:53,570 >> Och det är inte. 379 00:16:53,570 --> 00:16:55,980 Detta är inte nödvändigtvis de uppgifter struktur bör du dras till, 380 00:16:55,980 --> 00:16:58,220 eftersom som hashtabeller, avvägning. 381 00:16:58,220 --> 00:17:00,500 Vad är det pris du betalar här? 382 00:17:00,500 --> 00:17:00,940 Minne. 383 00:17:00,940 --> 00:17:02,890 Jag menar, är detta en avskyvärd mängd minne. 384 00:17:02,890 --> 00:17:05,569 Och du kan inte riktigt se det här eftersom författare till den här bilden 385 00:17:05,569 --> 00:17:09,420 uppenbarligen stympad alla matriser, och vi inte ser massor av A: s och 386 00:17:09,420 --> 00:17:12,700 B: s och C: s och Q: s och Y: s och Z är i dessa matriser. 387 00:17:12,700 --> 00:17:13,630 Men de är där. 388 00:17:13,630 --> 00:17:17,660 >> Var och en av dessa noder är en hel rad vissa 26 eller fler bytes, vilka 389 00:17:17,660 --> 00:17:19,170 som representerar en bokstav. 390 00:17:19,170 --> 00:17:22,920 27 i vårt fall, så att vi kan stödja apostrofer i problembild. 391 00:17:22,920 --> 00:17:27,030 Så här datastruktur är riktigt, riktigt tät och bred. 392 00:17:27,030 --> 00:17:30,880 Och det ensamt kan sluta att sakta ner saker, eller åtminstone kostar dig en 393 00:17:30,880 --> 00:17:32,240 mycket mer utrymme. 394 00:17:32,240 --> 00:17:34,020 Men återigen, kan vi dra jämförelser här. 395 00:17:34,020 --> 00:17:39,190 >> Minns en tid tillbaka har vi uppnått mycket mer spännande drifttid i sortering 396 00:17:39,190 --> 00:17:42,880 när vi använder merge sort, men priset Vi betalade för att uppnå n log n för sammanfogningen 397 00:17:42,880 --> 00:17:46,930 Sortera krävs att vi spenderar mer vilken resurs? 398 00:17:46,930 --> 00:17:47,690 Mer utrymme. 399 00:17:47,690 --> 00:17:50,530 Vi behövde en sekundär array till kopiera folk in, precis som 400 00:17:50,530 --> 00:17:51,620 vi gjorde här på scenen. 401 00:17:51,620 --> 00:17:55,880 Så återigen, inga tydliga vinnare, men bara subjektiv utformning 402 00:17:55,880 --> 00:17:57,710 beslut som ska fattas. 403 00:17:57,710 --> 00:17:58,060 >> Okej. 404 00:17:58,060 --> 00:17:59,130 Så vad sägs om det här? 405 00:17:59,130 --> 00:18:02,050 Någon känner igen 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 gör. 408 00:18:03,170 --> 00:18:03,750 Mather House. 409 00:18:03,750 --> 00:18:05,070 Så det här är för Mather s matsal. 410 00:18:05,070 --> 00:18:09,650 Jag slår vad alla matsalarna har högar av brickor som denna. 411 00:18:09,650 --> 00:18:11,950 Och detta är verkligen representativt av något vi har 412 00:18:11,950 --> 00:18:13,050 uppenbarligen redan sett. 413 00:18:13,050 --> 00:18:14,850 Vi kallade det bokstavligen en stapel. 414 00:18:14,850 --> 00:18:18,970 Och stapeln, i termer av din datorns minne, är där data går 415 00:18:18,970 --> 00:18:20,460 medan funktioner som anropas. 416 00:18:20,460 --> 00:18:23,410 >> Till exempel vilka typer av saker går på stacken med avseende på den 417 00:18:23,410 --> 00:18:27,420 minne layout vi har diskuterat i veckor tidigare? 418 00:18:27,420 --> 00:18:28,736 Vad är det? 419 00:18:28,736 --> 00:18:29,670 >> Målgrupp: Samtal till funktioner. 420 00:18:29,670 --> 00:18:30,260 >> DAVID MALAN: Jag är ledsen. 421 00:18:30,260 --> 00:18:31,210 >> Målgrupp: Samtal till funktioner. 422 00:18:31,210 --> 00:18:33,590 >> DAVID MALAN: Samtal till funktioner, men specifikt, vad som finns inuti var och en av 423 00:18:33,590 --> 00:18:35,340 dessa ramar? 424 00:18:35,340 --> 00:18:37,220 Vilka typer av saker? 425 00:18:37,220 --> 00:18:37,460 Yeah. 426 00:18:37,460 --> 00:18:38,500 Så lokala variabler. 427 00:18:38,500 --> 00:18:43,080 När som helst vi behövde någon lokal lagring, som ett argument, eller int jag, eller int 428 00:18:43,080 --> 00:18:45,940 temp, eller vad den lokala variabeln, vi har varit 429 00:18:45,940 --> 00:18:47,210 sätta det på stacken. 430 00:18:47,210 --> 00:18:49,610 Och vi kallar det en bunt eftersom av denna skiktning idé. 431 00:18:49,610 --> 00:18:52,940 Bara typ av matcher med verkligheten, konceptet därav. 432 00:18:52,940 --> 00:18:56,650 >> Men det visar sig att en stapel kan också ses som en datastruktur, en 433 00:18:56,650 --> 00:19:00,110 alternativ till en matris, ett alternativ till en länkad lista. 434 00:19:00,110 --> 00:19:02,770 Något begreppsmässigt mer intressant som fortfarande kan vara 435 00:19:02,770 --> 00:19:06,030 genomföras med hjälp av någon av de saker, men det är en annan typ av 436 00:19:06,030 --> 00:19:09,140 datastruktur stödjande, verkligen, endast två operationer. 437 00:19:09,140 --> 00:19:11,000 Men du kan lägga på snyggare funktioner än dessa. 438 00:19:11,000 --> 00:19:12,180 Men dessa är grunderna - 439 00:19:12,180 --> 00:19:13,510 driva och pop. 440 00:19:13,510 --> 00:19:19,240 >> Och idén med en stack är att om jag har här, med eller utan Annenberg 441 00:19:19,240 --> 00:19:22,880 vetskap, en bricka från nästa dörr med nummer 9 på den. 442 00:19:22,880 --> 00:19:23,870 Så bara en int. 443 00:19:23,870 --> 00:19:26,990 Och jag vill driva detta på uppgifterna struktur, som för närvarande är tom. 444 00:19:26,990 --> 00:19:28,790 Tänk på detta i botten av stapeln. 445 00:19:28,790 --> 00:19:33,150 Jag skulle driva detta nummer 9 på stapla, och nu är det rätt där. 446 00:19:33,150 --> 00:19:36,040 >> Men det intressanta med en stack är att om jag nu vill driva 447 00:19:36,040 --> 00:19:40,210 något annat värde, 17 gillar, och jag trycker detta på stacken, kommer jag att göra 448 00:19:40,210 --> 00:19:43,290 det enda intuitiva sak, jag ska bara att sätta det rätt där vi människor 449 00:19:43,290 --> 00:19:45,180 skulle vara benägna att lägga den på toppen. 450 00:19:45,180 --> 00:19:48,850 Men vad som är intressant nu är, hur får jag vid 9? 451 00:19:48,850 --> 00:19:50,670 Du vet, det gör jag inte utan viss ansträngning. 452 00:19:50,670 --> 00:19:54,070 >> Så vad är intressant en skorsten är att genom design, 453 00:19:54,070 --> 00:19:56,330 det är en LIFO datastruktur. 454 00:19:56,330 --> 00:19:59,680 Silly sätt att beskriva sist in, först ut. 455 00:19:59,680 --> 00:20:03,280 Så det sista numret i vid denna tid var 17. 456 00:20:03,280 --> 00:20:07,540 Så om jag vill smälla något utanför av stapeln, kan det bara 17. 457 00:20:07,540 --> 00:20:11,890 Så det finns en obligatorisk ordning Operationerna här, där den sista posten 458 00:20:11,890 --> 00:20:14,260 i måste vara först ut. 459 00:20:14,260 --> 00:20:16,440 Därav förkortningen, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Så varför skulle detta vara användbart? 461 00:20:19,160 --> 00:20:22,690 Är deras sammanhang där du vill vill ha en datastruktur som denna? 462 00:20:22,690 --> 00:20:24,810 Tja, är det verkligen varit till nytta insidan av en dator. 463 00:20:24,810 --> 00:20:29,050 Så operativsystem använder tydligt detta typ av datastruktur för stackar. 464 00:20:29,050 --> 00:20:32,800 Vi ser också samma idé när det gäller webbsidor. 465 00:20:32,800 --> 00:20:35,890 Så den här veckan och nästa vecka och utanför, och när du börjar genomföra webben 466 00:20:35,890 --> 00:20:39,490 sidor på ett språk som kallas HTML, kan du faktiskt använda en datastruktur som 467 00:20:39,490 --> 00:20:42,690 detta för att avgöra om sidan är korrekt formaterad. 468 00:20:42,690 --> 00:20:47,170 Eftersom vi ser alla webbsidor följer ett slags hierarki, en fördjupning 469 00:20:47,170 --> 00:20:52,030 som kommer i slutet av dagen, vara en trädstruktur under huven. 470 00:20:52,030 --> 00:20:53,620 Så mer om att på bara en bit. 471 00:20:53,620 --> 00:20:56,560 >> Men för nu, låt oss föreslå ett ögonblick, hur skulle vi gå om 472 00:20:56,560 --> 00:20:58,830 representerar vad en stapel är? 473 00:20:58,830 --> 00:21:03,370 Låt mig föreslå att vi genomför en bunt med koden så här. 474 00:21:03,370 --> 00:21:07,990 Så en stapel kommer att ha inne i det två saker, en array, som kallas brickor, 475 00:21:07,990 --> 00:21:09,510 bara för att vara förenligt med demo. 476 00:21:09,510 --> 00:21:12,660 Och var och en av punkterna i denna matris kommer att bli en typ int. 477 00:21:12,660 --> 00:21:14,740 Och kapaciteten är förmodligen vad? 478 00:21:14,740 --> 00:21:18,796 Eftersom jag inte har skrivit fullständig definition här. 479 00:21:18,796 --> 00:21:21,535 >> Det är förmodligen den största storleken på matrisen. 480 00:21:21,535 --> 00:21:25,150 Och det är förmodligen förklaras som en skarp definiera på toppen av filen, vissa 481 00:21:25,150 --> 00:21:28,450 slags konstant underförstådda som genom enbart versaler. 482 00:21:28,450 --> 00:21:32,250 Så någonstans kapaciteten definieras som i största möjliga storlek. 483 00:21:32,250 --> 00:21:35,590 Samtidigt, inne i datastrukturen känd som en stapel kommer det 484 00:21:35,590 --> 00:21:38,630 vara ett heltal bara kända helt enkelt som storlek. 485 00:21:38,630 --> 00:21:43,400 >> Så om jag skulle representera detta nu bildmässigt, låt oss anta att detta 486 00:21:43,400 --> 00:21:48,070 Hela svarta lådan representerar min stack. 487 00:21:48,070 --> 00:21:50,070 Inuti är det två variabler. 488 00:21:50,070 --> 00:21:54,780 Så jag kommer att dra första som storlek. 489 00:21:54,780 --> 00:21:57,420 Och den andra ska jag att dra som en matris. 490 00:21:57,420 --> 00:22:01,060 >> Men bara för att hålla saker ordnad, Normalt skulle jag rita en array som 491 00:22:01,060 --> 00:22:04,910 detta, men det är typ av trevligt Om vi ​​matchar verkligheten, eller 492 00:22:04,910 --> 00:22:06,230 matcha den mentala modellen. 493 00:22:06,230 --> 00:22:12,880 Så låt mig istället dra array vertikalt, är som just, återigen, 494 00:22:12,880 --> 00:22:13,840 konstnärs tolkning. 495 00:22:13,840 --> 00:22:16,610 Spelar egentligen ingen roll vad det är under huven. 496 00:22:16,610 --> 00:22:20,350 Och vi säger att, som standard, kapacitet kommer att bli tre. 497 00:22:20,350 --> 00:22:23,480 Så detta kommer att vara platsen 0, detta kommer att vara plats 1, detta 498 00:22:23,480 --> 00:22:25,740 kommer att vara plats 2. 499 00:22:25,740 --> 00:22:29,330 >> Om jag muta med en stress boll, skulle någon vilja komma upp och köra 500 00:22:29,330 --> 00:22:30,870 styrelsen här för bara en stund? 501 00:22:30,870 --> 00:22:31,960 OK, såg din hand först. 502 00:22:31,960 --> 00:22:33,950 Kom upp. 503 00:22:33,950 --> 00:22:36,500 Okej. 504 00:22:36,500 --> 00:22:38,760 Så jag tror att det är Steven. 505 00:22:38,760 --> 00:22:40,035 Kom upp. 506 00:22:40,035 --> 00:22:40,770 Okej. 507 00:22:40,770 --> 00:22:46,760 >> Men antag nu vi spola tillbaka till den ursprungliga tillståndet i världen där jag 508 00:22:46,760 --> 00:22:52,180 har precis förklarat en stapel, och det är kommer att vara av kapaciteten tre. 509 00:22:52,180 --> 00:22:54,470 Men storleken har ännu inte bestämts. 510 00:22:54,470 --> 00:22:56,100 Brickor har ännu inte fastställts. 511 00:22:56,100 --> 00:22:57,300 Så ett par frågor först. 512 00:22:57,300 --> 00:23:01,310 Och låt mig ge dig mikrofonen så att du kan delta mer aktivt i detta. 513 00:23:01,310 --> 00:23:05,190 >> Så vad är inne i storlek i denna stund i tid om allt jag har gjort är 514 00:23:05,190 --> 00:23:09,340 förklarade en bunt med en rad kod? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: Inte mycket. 516 00:23:10,100 --> 00:23:12,080 >> DAVID MALAN: OK, inte mycket. 517 00:23:12,080 --> 00:23:14,410 Vet vi vad som finns inne i storlek, vet vi vad som finns inuti 518 00:23:14,410 --> 00:23:16,330 av denna array här? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Bara slumpvis kod, eller hur? 520 00:23:18,630 --> 00:23:20,220 Just - 521 00:23:20,220 --> 00:23:23,230 >> DAVID MALAN: Ja, jag ska kalla det kod, men random - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Saker. 523 00:23:23,820 --> 00:23:28,290 >> DAVID MALAN: Saker som slumpvis 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: Bits. 525 00:23:28,870 --> 00:23:29,530 >> DAVID MALAN: Bits, rätt? 526 00:23:29,530 --> 00:23:31,190 Så sopor värden, rätt? 527 00:23:31,190 --> 00:23:33,470 Så permutationer av 0 s och 1 s. 528 00:23:33,470 --> 00:23:35,920 Rester av tidigare användningar av detta minne. 529 00:23:35,920 --> 00:23:38,150 Och vi vet inte riktigt vad de värden är, så vi drar oftast dem 530 00:23:38,150 --> 00:23:38,930 som frågetecken. 531 00:23:38,930 --> 00:23:41,990 >> Så det första vi förmodligen kommer att vilja göra här - 532 00:23:41,990 --> 00:23:46,630 och låt mig ge detta fält inuti av det ett namn - brickor. 533 00:23:46,630 --> 00:23:49,540 Vad ska vi initiera förmodligen storlek att om vi vill 534 00:23:49,540 --> 00:23:51,040 börja använda denna stack? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Tray är sub 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID MALAN: Så, OK. 537 00:23:53,910 --> 00:23:56,710 För att vara tydlig, är kapaciteten förklaras håll som tre. 538 00:23:56,710 --> 00:23:58,570 Och det är vad jag har använt att allokera arrayen. 539 00:23:58,570 --> 00:24:03,535 Storlek kommer att hänvisa till hur många brickor finns för närvarande på stacken. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Zero. 541 00:24:03,880 --> 00:24:04,460 >> DAVID MALAN: Så det borde vara noll. 542 00:24:04,460 --> 00:24:07,760 Så sätt igång, och varje finger, rita en nolla i storlek. 543 00:24:07,760 --> 00:24:08,440 Okej. 544 00:24:08,440 --> 00:24:10,920 Så nu, vad som finns inuti denna här, vet vi inte. 545 00:24:10,920 --> 00:24:12,160 Dessa är egentligen bara skräp värden. 546 00:24:12,160 --> 00:24:14,800 Så kunde vi rita frågetecken, men Låt oss hålla styrelsen ren för nu 547 00:24:14,800 --> 00:24:16,300 eftersom det inte spelar någon roll vad som finns där. 548 00:24:16,300 --> 00:24:19,130 Vi behöver inte initiera arrayen till någonting, för om vi vet att 549 00:24:19,130 --> 00:24:23,100 storleken på stapeln är noll, väl, vi bör inte titta på någonting i 550 00:24:23,100 --> 00:24:25,590 denna array ändå på denna tidpunkt. 551 00:24:25,590 --> 00:24:29,970 >> Så nu antar att jag trycker på nummer 9 på stacken. 552 00:24:29,970 --> 00:24:33,750 Hur ska vi uppdaterar datastrukturen insidan av denna svarta låda? 553 00:24:33,750 --> 00:24:35,540 Vilka värden behöver ändra? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: Inom - 555 00:24:36,200 --> 00:24:37,400 storleken? 556 00:24:37,400 --> 00:24:37,650 >> DAVID MALAN: OK. 557 00:24:37,650 --> 00:24:38,770 Storleken ska bli vad? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Storlek skulle vara en. 559 00:24:39,580 --> 00:24:39,870 >> DAVID MALAN: OK. 560 00:24:39,870 --> 00:24:41,110 Så storlek ska bli en. 561 00:24:41,110 --> 00:24:42,540 Så du kan göra detta på ett par olika sätt. 562 00:24:42,540 --> 00:24:46,920 Låt mig ge er, nu din fingret är ett radergummi. 563 00:24:46,920 --> 00:24:47,260 Okej. 564 00:24:47,260 --> 00:24:49,960 Då nu fingret är en borste. 565 00:24:49,960 --> 00:24:50,330 Okej. 566 00:24:50,330 --> 00:24:52,820 Och nu vad måste förändras, självklart, i datastrukturen? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Vi kommer från botten upp till 9. 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å fortfarande ingen roll vad som finns på plats en eller två eftersom de är 571 00:25:01,550 --> 00:25:04,520 sopor värden, men vi ska inte bry ser det eftersom storleken är 572 00:25:04,520 --> 00:25:07,540 säger oss att bara det första elementet är faktiskt legitimt. 573 00:25:07,540 --> 00:25:10,400 Så nu jag skjuta 17 på listan. 574 00:25:10,400 --> 00:25:11,830 Vad händer med den här bilden? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: Så storlek kommer att gå till två. 576 00:25:14,720 --> 00:25:15,300 >> DAVID MALAN: OK. 577 00:25:15,300 --> 00:25:16,070 Du är suddgummi - 578 00:25:16,070 --> 00:25:16,810 oops. 579 00:25:16,810 --> 00:25:18,026 Du är ett suddgummi. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Eraser. 581 00:25:18,840 --> 00:25:19,720 >> DAVID MALAN: Du är en borste. 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 Och vad mer? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: Och sedan vi - 586 00:25:22,600 --> 00:25:22,915 >> DAVID MALAN: Vi sköt 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Vi håller 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: - släpp ner den. 590 00:25:27,040 --> 00:25:27,530 >> DAVID MALAN: Okej. 591 00:25:27,530 --> 00:25:27,940 Det blir lätt. 592 00:25:27,940 --> 00:25:29,300 Jag tänker inte hjälpa dig den här gången. 593 00:25:29,300 --> 00:25:30,510 Push 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Klar. 595 00:25:31,720 --> 00:25:34,870 Att bli ett suddgummi. 596 00:25:34,870 --> 00:25:37,340 Jag blir en borste. 597 00:25:37,340 --> 00:25:39,340 Och då är jag sätta 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID MALAN: 22. 599 00:25:40,100 --> 00:25:40,620 Utmärkt. 600 00:25:40,620 --> 00:25:41,380 Så en gång till. 601 00:25:41,380 --> 00:25:44,280 Jag kommer nu att driva på stacken 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 fångade mig verkligen off guard. 605 00:25:52,520 --> 00:25:53,703 >> DAVID MALAN: Du gjorde inte se detta komma? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: Jag såg inte detta komma. 607 00:25:55,930 --> 00:25:58,756 Kan vi åter initial kapacitet? 608 00:25:58,756 --> 00:25:59,790 >> DAVID MALAN: Det är en bra fråga. 609 00:25:59,790 --> 00:26:02,360 Så vi har typ av målat oss i ett hörn här. 610 00:26:02,360 --> 00:26:06,740 Det finns egentligen inget bra ut för Steven eftersom vi har tilldelats denna array 611 00:26:06,740 --> 00:26:09,130 statiskt, så att säga, inuti av datastruktur. 612 00:26:09,130 --> 00:26:12,170 Och vi har väsentligen hårdkodade att det är av storlek tre. 613 00:26:12,170 --> 00:26:14,170 Så vi kan inte riktigt omfördela dem. 614 00:26:14,170 --> 00:26:20,020 >> Vi kunde om vi gick tillbaka, vi omdefinierade facken att vara en pekare som 615 00:26:20,020 --> 00:26:22,300 Vi använder sedan malloc till hands minne. 616 00:26:22,300 --> 00:26:25,050 För om vi fick minnet från högen via malloc, vi 617 00:26:25,050 --> 00:26:26,430 kunde därefter frigöra den. 618 00:26:26,430 --> 00:26:29,630 Men innan befria det, kan vi omfördela en större bit av minnet, 619 00:26:29,630 --> 00:26:31,330 uppdatera pekaren, och så vidare. 620 00:26:31,330 --> 00:26:33,500 Men för nu, är detta verkligen det bästa vi kan göra. 621 00:26:33,500 --> 00:26:36,360 Push och pop är förmodligen kommer att behöva signalera något fel. 622 00:26:36,360 --> 00:26:40,270 >> Så till exempel, vårt genomförande push kunde återvända en bool som 623 00:26:40,270 --> 00:26:42,390 tidigare returneras true, true, true. 624 00:26:42,390 --> 00:26:48,390 Men den fjärde gången, det kommer att ha att returnera false, till exempel. 625 00:26:48,390 --> 00:26:48,540 Okej. 626 00:26:48,540 --> 00:26:49,540 Mycket bra gjort. 627 00:26:49,540 --> 00:26:50,060 Grattis. 628 00:26:50,060 --> 00:26:52,160 Du har förtjänat din stress boll idag. 629 00:26:52,160 --> 00:26:53,110 >> [Applåder] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Tack. 631 00:26:54,382 --> 00:26:55,680 >> DAVID MALAN: Tack. 632 00:26:55,680 --> 00:26:59,740 OK, så detta verkar vara inte mycket ett steg framåt, eller hur? 633 00:26:59,740 --> 00:27:01,410 Vi beskrev denna datastruktur. 634 00:27:01,410 --> 00:27:02,320 Det har varit spännande, eller hur? 635 00:27:02,320 --> 00:27:03,200 Operativsystem gillar det. 636 00:27:03,200 --> 00:27:06,360 Tydligen webben kan utnyttja detta, och andra program fortfarande. 637 00:27:06,360 --> 00:27:10,870 Men vad en dum begränsning som vi är tillbaka till typ av vecka två gränser 638 00:27:10,870 --> 00:27:12,880 där vi har fast storlek matriser. 639 00:27:12,880 --> 00:27:15,010 >> Så det finns faktiskt ett par hur vi skulle kunna lösa detta. 640 00:27:15,010 --> 00:27:18,750 Vi kunde dynamiskt allokera arrayen, inte genom hårt kodning det som jag har 641 00:27:18,750 --> 00:27:22,600 gjort här, utan i stället på nytt förklara detta, att bara vara tydlig, eftersom 642 00:27:22,600 --> 00:27:23,830 ungefär så här. 643 00:27:23,830 --> 00:27:29,040 Int * brickor, inte besluta på en kapacitet än. 644 00:27:29,040 --> 00:27:35,460 Men när jag förklarar stapeln på annat håll i min kod, kan jag ringa då malloc, 645 00:27:35,460 --> 00:27:38,250 få adressen till en bit av minne, och jag kunde ge 646 00:27:38,250 --> 00:27:39,980 den adressen till brickor. 647 00:27:39,980 --> 00:27:43,340 >> Och sedan, eftersom det är bara en bit av minne, skulle jag fortsätta att använda torget 648 00:27:43,340 --> 00:27:45,450 hakparenteser på vanligt sätt. 649 00:27:45,450 --> 00:27:49,020 Eftersom igen, det är typ av detta funktionell ekvivalent av matriser och 650 00:27:49,020 --> 00:27:50,820 bitar av minne som kommer tillbaka från malloc. 651 00:27:50,820 --> 00:27:53,090 Vi kan behandla en som de andra hjälp pekararitmetik eller 652 00:27:53,090 --> 00:27:54,440 klammer notation. 653 00:27:54,440 --> 00:27:55,660 Så det är en strategi. 654 00:27:55,660 --> 00:28:00,120 >> Men hur annars kan vi genomföra detta samma datastruktur, potentiellt? 655 00:28:00,120 --> 00:28:00,280 Rätt? 656 00:28:00,280 --> 00:28:04,530 Jag tycker vi just löst detta problem som för en vecka sedan. 657 00:28:04,530 --> 00:28:08,860 Vad var lösningen på detta problem att Steven sprang in? 658 00:28:08,860 --> 00:28:10,370 Så länkade listor, höger. 659 00:28:10,370 --> 00:28:13,410 >> Om problemet är att vi målar in oss i ett hörn genom att allokera 660 00:28:13,410 --> 00:28:17,580 i förväg för lite minne som vi därefter har att på något sätt ta itu med, väl, 661 00:28:17,580 --> 00:28:19,880 varför inte bara undvika att emittera sammanlagt? 662 00:28:19,880 --> 00:28:26,170 Varför inte bara förklara brickor för att vara en pekare till en nod, ergo en länkad lista, 663 00:28:26,170 --> 00:28:30,740 och sedan helt enkelt tilldela nya noder varje gång Steven behövs för att passa en 664 00:28:30,740 --> 00:28:32,400 nummer i datastrukturen. 665 00:28:32,400 --> 00:28:34,200 >> Så bilden måste förändras. 666 00:28:34,200 --> 00:28:38,220 Det kommer inte att vara så rena och som enkelt som att bara en samling av tre ints. 667 00:28:38,220 --> 00:28:42,970 Nu kommer det att vara en pekare till en struct, och att struct kommer att 668 00:28:42,970 --> 00:28:44,830 har en int och en nästa pekare. 669 00:28:44,830 --> 00:28:47,670 Det kommer att leda via denna pekare till en annan sådan struct till 670 00:28:47,670 --> 00:28:48,600 en annan sådan strukt. 671 00:28:48,600 --> 00:28:50,560 Så bilden skulle faktiskt få lite stökigare. 672 00:28:50,560 --> 00:28:52,950 Och vi skulle ha pilar knyta allt tillsammans. 673 00:28:52,950 --> 00:28:55,280 >> Men det är bra, rätt, eftersom Vi har sett hur man gör detta. 674 00:28:55,280 --> 00:28:58,180 Och när du får bekväm genomföra något som en länkad 675 00:28:58,180 --> 00:29:01,450 listan, vilket du måste göra om du välja att genomföra en hash-tabell med 676 00:29:01,450 --> 00:29:05,120 separat kedja för p-set 6, kan du använda den som en byggsten, eller 677 00:29:05,120 --> 00:29:08,870 ingrediens, eller i Scratch tala, en förfarande, något som du lägger, du 678 00:29:08,870 --> 00:29:12,560 skapat en egen pusselbit som du sedan kan återanvända. 679 00:29:12,560 --> 00:29:17,090 Så kompromisser, men potentiella lösningar att vi har faktiskt sett förut. 680 00:29:17,090 --> 00:29:20,560 >> Så ganska ofta, ser du detta varje år eller två när Apple släpper 681 00:29:20,560 --> 00:29:23,060 något nytt, och alla galna människor line up utanför Apple 682 00:29:23,060 --> 00:29:27,050 butik för att köpa deras marginella uppgradera på hårdvara. 683 00:29:27,050 --> 00:29:30,420 Jag säger detta, det är OK, eftersom Jag är en av dem. 684 00:29:30,420 --> 00:29:35,140 Så vilken typ av datastruktur kan representera denna verklighet? 685 00:29:35,140 --> 00:29:36,980 >> Nåväl, låt oss kalla det en kö, en linje. 686 00:29:36,980 --> 00:29:40,270 Så britterna skulle kalla det normalt en kö ändå, så det är ett fint namn. 687 00:29:40,270 --> 00:29:44,960 Och de två operationer som en kö ska stödja vi kallar en enqueue 688 00:29:44,960 --> 00:29:48,900 drift och en dequeue operation, som är liknande i 689 00:29:48,900 --> 00:29:50,120 ande att driva och pop. 690 00:29:50,120 --> 00:29:54,060 Det är bara typ av annorlunda i konvention, vad vi kallar dem. 691 00:29:54,060 --> 00:29:57,680 Men att köa något sätt att lägga eller sätt den till datastruktur. 692 00:29:57,680 --> 00:29:59,570 Att avköa innebär att ta bort den. 693 00:29:59,570 --> 00:30:05,170 Men medan en stapel var en LIFO uppgifter struktur, är en kö en först in- 694 00:30:05,170 --> 00:30:06,740 först ut-datastruktur. 695 00:30:06,740 --> 00:30:10,050 >> Om du är den första personen i raden, du kommer att vara den första personen att få 696 00:30:10,050 --> 00:30:12,420 ut ur linjen och köpa din nya enhet. 697 00:30:12,420 --> 00:30:18,070 Föreställ dig hur upprörd dessa människor skulle vara Om Apple istället använde en stapel för 698 00:30:18,070 --> 00:30:21,250 Exempelvis, för att genomföra plockning upp på din nya leksak. 699 00:30:21,250 --> 00:30:24,310 Så köer vettigt, förvisso, och Vi kan tänka på alla möjliga 700 00:30:24,310 --> 00:30:27,480 applikationer, förmodligen, för köer, speciellt när du vill ha rättvisa. 701 00:30:27,480 --> 00:30:30,040 Så hur kan vi genomföra dessa som en datastruktur? 702 00:30:30,040 --> 00:30:33,680 >> Tja, föreslår jag att vi kanske behöver göra det här sättet. 703 00:30:33,680 --> 00:30:35,225 Så jag ska nu ha siffror. 704 00:30:35,225 --> 00:30:38,190 Så vi ska hålla det enkelt och inte nödvändigtvis tala i termer av brickor. 705 00:30:38,190 --> 00:30:40,220 Bara siffror som folk fått. 706 00:30:40,220 --> 00:30:43,760 Kapaciteten kommer att, återigen, fixera totala antalet personer som kan vara i 707 00:30:43,760 --> 00:30:46,900 denna linje, som tre eller vad annat värde. 708 00:30:46,900 --> 00:30:50,760 >> Men jag föreslår att jag måste hålla koll inte bara av storleken på 709 00:30:50,760 --> 00:30:52,370 kö, hur många saker är i det. 710 00:30:52,370 --> 00:30:56,310 Så storleken är den nuvarande storlek, kapacitet är den maximala storleken. 711 00:30:56,310 --> 00:30:58,540 Bara igen, nomenklatur enligt praxis. 712 00:30:58,540 --> 00:31:03,680 Varför behöver jag en extra int inne av en kö för att hålla reda på vem som är i 713 00:31:03,680 --> 00:31:05,365 framsidan av linjen? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Varför behöver jag göra det i det här fallet? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Nå, hur är detta bilden kommer att förändras? 718 00:31:16,190 --> 00:31:19,280 Jag kan nog återanvända mest av denna bild. 719 00:31:19,280 --> 00:31:21,480 Låt mig gå vidare och radera det som finns här. 720 00:31:21,480 --> 00:31:24,580 Vi ska ge detta en något annat namn här uppe. 721 00:31:24,580 --> 00:31:28,930 Låt oss bli av med 17, låt oss bli av 9, låt oss bli av med 3. 722 00:31:28,930 --> 00:31:30,410 Och låt oss lägga en annan sak. 723 00:31:30,410 --> 00:31:34,710 Jag föreslår att jag måste hålla reda på framsidan av listan, som just 724 00:31:34,710 --> 00:31:35,570 kommer att vara en int liksom. 725 00:31:35,570 --> 00:31:36,550 Och vi kommer att hålla det enkelt. 726 00:31:36,550 --> 00:31:37,740 Ingen länkad lista för nu. 727 00:31:37,740 --> 00:31:40,900 >> Vi ska erkänna att vi ska stöta upp mot denna gräns. 728 00:31:40,900 --> 00:31:43,720 Men vad jag vill se hända den här gången? 729 00:31:43,720 --> 00:31:47,240 Så antar jag gå vidare och den första personen kommer upp i linje, och 730 00:31:47,240 --> 00:31:48,560 det är nummer 9. 731 00:31:48,560 --> 00:31:49,680 Vi har stress bollar. 732 00:31:49,680 --> 00:31:51,330 Kan jag stjäla, säg, två eller tre personer? 733 00:31:51,330 --> 00:31:52,690 Ett, två, tre? 734 00:31:52,690 --> 00:31:53,120 Kom upp. 735 00:31:53,120 --> 00:31:56,022 Höger framifrån, eftersom Vi ska göra det här snabbt. 736 00:31:56,022 --> 00:31:59,415 >> Var och en av er kommer nu att vara en fläkt pojke i rad vid Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Du kommer inte att ta emot Apple-maskinvara i slutet av detta dock. 739 00:32:06,210 --> 00:32:06,500 Okej. 740 00:32:06,500 --> 00:32:09,430 Så du är nummer 9, är du nummer 17, nummer 22. 741 00:32:09,430 --> 00:32:12,130 Dessa är godtyckliga tal, liksom student-ID eller whatnot. 742 00:32:12,130 --> 00:32:14,550 Och på bara ett ögonblick, låt oss börja att börja lägga till saker. 743 00:32:14,550 --> 00:32:16,000 Och jag ska köra styrelsen här den här gången. 744 00:32:16,000 --> 00:32:19,570 >> Så i det här fallet har jag initieras fronten för att vara - 745 00:32:19,570 --> 00:32:22,380 Jag faktiskt inte riktigt bryr sig om vad front är, eftersom storleken är noll. 746 00:32:22,380 --> 00:32:24,480 Så det här kan lika gärna vara ett frågetecken. 747 00:32:24,480 --> 00:32:26,170 Dessa är alla frågetecken. 748 00:32:26,170 --> 00:32:29,880 Så nu ska vi börja att faktiskt se några folk köar i butiken. 749 00:32:29,880 --> 00:32:33,320 >> Så om nummer 9, är du den första där kl 5, gå vidare och rada upp, 750 00:32:33,320 --> 00:32:34,210 eller kvällen innan. 751 00:32:34,210 --> 00:32:34,580 OK. 752 00:32:34,580 --> 00:32:35,940 Så nu 9 är här. 753 00:32:35,940 --> 00:32:37,940 Så 9 är på framsidan av listan. 754 00:32:37,940 --> 00:32:41,440 Så jag kommer att gå vidare och uppdatera storleken på denna aktuella data 755 00:32:41,440 --> 00:32:44,740 struktur för att inte vara 0 anymore, men för att vara 1. 756 00:32:44,740 --> 00:32:47,630 Jag kommer att sätta 9 vid framsidan av listan. 757 00:32:47,630 --> 00:32:51,020 Låt mig gå vidare och växla skärmen så att vi kan se förbi oss här. 758 00:32:51,020 --> 00:32:53,220 >> Och nu vad vill jag att sätta på framsidan? 759 00:32:53,220 --> 00:32:56,240 Jag kommer att hålla koll på att fram i kön just nu 760 00:32:56,240 --> 00:32:58,570 är i position 0. 761 00:32:58,570 --> 00:33:00,510 För vad är nästa kommer att hända? 762 00:33:00,510 --> 00:33:03,000 Tja, antar jag nu köa 17 liksom. 763 00:33:03,000 --> 00:33:04,510 Så hoppa i linje där. 764 00:33:04,510 --> 00:33:07,060 Och vidare den typ av dörren till Butiken kommer att vara här. 765 00:33:07,060 --> 00:33:08,700 Så nu har jag lagt 17. 766 00:33:08,700 --> 00:33:10,810 Och även om dessa killar blockerar skärmen, det är OK, 767 00:33:10,810 --> 00:33:12,300 eftersom vi kan se det här uppe. 768 00:33:12,300 --> 00:33:12,910 Ursäkta. 769 00:33:12,910 --> 00:33:13,810 >> Publik: Vi kan flytta - 770 00:33:13,810 --> 00:33:14,660 >> DAVID MALAN: Nej, det är OK. 771 00:33:14,660 --> 00:33:16,000 Det är enormt där uppe. 772 00:33:16,000 --> 00:33:18,580 Så 17 är nu inne i kön. 773 00:33:18,580 --> 00:33:21,332 Jag behöver uppdatera vilka fält nu dock? 774 00:33:21,332 --> 00:33:23,210 OK, definitivt storlek. 775 00:33:23,210 --> 00:33:26,430 Och vad sägs om fronten? 776 00:33:26,430 --> 00:33:27,040 OK, ingen. 777 00:33:27,040 --> 00:33:30,200 Fram bör inte förändras, eftersom till skillnad från en stapel, vi 778 00:33:30,200 --> 00:33:31,370 vill upprätthålla rättvisa. 779 00:33:31,370 --> 00:33:35,150 Så om 9 kom i första, vill vi 9 att vara den första av linjen 780 00:33:35,150 --> 00:33:36,420 och in i affären. 781 00:33:36,420 --> 00:33:37,220 >> I själva verket, låt oss se det. 782 00:33:37,220 --> 00:33:42,235 Innan vi sätter 22, låt oss gå vidare och dequeue 9. 783 00:33:42,235 --> 00:33:42,970 Vad är ditt namn igen? 784 00:33:42,970 --> 00:33:43,680 >> Publiken: Jake. 785 00:33:43,680 --> 00:33:45,440 >> DAVID MALAN: Jake går att ur kön nu. 786 00:33:45,440 --> 00:33:48,050 Så du får gå in i butiken. 787 00:33:48,050 --> 00:33:49,880 Och låtsas att butiken är borta. 788 00:33:49,880 --> 00:33:51,970 Så nu vad som behöver - dit-dit-dit! 789 00:33:51,970 --> 00:33:53,400 Vad måste hända nu? 790 00:33:53,400 --> 00:33:54,490 Design beslut. 791 00:33:54,490 --> 00:33:56,825 Så inte en dålig instinkt, men - vad heter du nu igen? 792 00:33:56,825 --> 00:33:57,090 >> Publiken: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID MALAN: David. 794 00:33:57,500 --> 00:33:58,810 Så vad gjorde David göra? 795 00:33:58,810 --> 00:34:02,590 Han försökte att sortera fastställa vilka uppgifter struktur och flytta från sin plats 796 00:34:02,590 --> 00:34:04,100 i Jakes tidigare platsen. 797 00:34:04,100 --> 00:34:06,740 Och det är bra om vi är villiga att acceptera det som en 798 00:34:06,740 --> 00:34:08,199 implementeringsdetalj. 799 00:34:08,199 --> 00:34:11,100 Men först, låt oss uppdatera data struktur innan vi gör det. 800 00:34:11,100 --> 00:34:14,139 Eftersom jag inte gillar tanken på allt folket skiftar i denna linje. 801 00:34:14,139 --> 00:34:17,360 >> Det är ingen stor sak om David gör det med ett steg, men igen, tänker tillbaka på 802 00:34:17,360 --> 00:34:20,360 när vi har haft åtta volontärer på skede och vi har gjort liknande insättning 803 00:34:20,360 --> 00:34:22,600 Sortera, där vi var tvungna att börja flytta alla runt omkring. 804 00:34:22,600 --> 00:34:23,790 Det blev dyrt, eller hur? 805 00:34:23,790 --> 00:34:28,330 Det gör mig hukar om Big O n, kvadrat stort O n igen. 806 00:34:28,330 --> 00:34:30,650 Det är inte känslan som ett perfekt resultat. 807 00:34:30,650 --> 00:34:32,080 >> Så låt oss bara uppdatera denna. 808 00:34:32,080 --> 00:34:35,120 Så storleken på kön är inte längre två. 809 00:34:35,120 --> 00:34:37,090 Det är nu bara 1. 810 00:34:37,090 --> 00:34:40,360 Men jag kan nu uppdatera något Jag har inte uppdaterat tidigare, 811 00:34:40,360 --> 00:34:41,130 framsidan av listan. 812 00:34:41,130 --> 00:34:45,420 Jag kunde bara säga, är den platsen 1? 813 00:34:45,420 --> 00:34:49,770 Så nu har vi skräp värde här, Garbage värde här, och David i 814 00:34:49,770 --> 00:34:51,469 mitten av detta skräp. 815 00:34:51,469 --> 00:34:54,980 Men den datastruktur är fortfarande intakt. 816 00:34:54,980 --> 00:34:58,540 >> Och i själva verket har jag inte ens behöver ändra Jake tidigare nummer 817 00:34:58,540 --> 00:35:00,460 9, för vem bryr sig. 818 00:35:00,460 --> 00:35:04,470 Jag har tillräckligt med information nu i storlek som jag vet att det finns en person i 819 00:35:04,470 --> 00:35:05,030 denna kö. 820 00:35:05,030 --> 00:35:08,340 Och jag vet att den personen är på plats 1, inte 0. 821 00:35:08,340 --> 00:35:09,760 Jag räknar inte. 822 00:35:09,760 --> 00:35:11,300 Så 1 liksom. 823 00:35:11,300 --> 00:35:13,410 Så den datastruktur är fortfarande OK. 824 00:35:13,410 --> 00:35:14,330 >> Tja, vad händer härnäst? 825 00:35:14,330 --> 00:35:15,010 Låt oss enqueue - 826 00:35:15,010 --> 00:35:15,370 vad är ditt namn? 827 00:35:15,370 --> 00:35:16,160 >> Publiken: Callen. 828 00:35:16,160 --> 00:35:16,580 >> DAVID MALAN: Callen. 829 00:35:16,580 --> 00:35:20,770 Låt oss köa en Callen, och 22 är nu i kön. 830 00:35:20,770 --> 00:35:22,300 Så nu vad som måste förändras här? 831 00:35:22,300 --> 00:35:24,380 Fram kommer inte att ändra, uppenbarligen. 832 00:35:24,380 --> 00:35:27,160 Storlek kommer att förändras för att vara 2 igen. 833 00:35:27,160 --> 00:35:31,590 Och 22 slutar här, är 9 kvar, men det är effektivt en 834 00:35:31,590 --> 00:35:32,600 Garbage värde nu. 835 00:35:32,600 --> 00:35:35,910 Det är bara en kvarleva av Jake förflutna. 836 00:35:35,910 --> 00:35:39,200 >> Så nu vad som händer om Jag avköa David? 837 00:35:39,200 --> 00:35:41,560 En sista operationen, dequeue David. 838 00:35:41,560 --> 00:35:46,070 Vi kunde skifta, men jag föreslår låt oss göra så lite arbete som möjligt. 839 00:35:46,070 --> 00:35:50,280 Nu är min datastruktur går bak i storlek från 2 till 1. 840 00:35:50,280 --> 00:35:53,730 Men fram i kön nu blir 2. 841 00:35:53,730 --> 00:35:56,640 Jag behöver inte ändra dessa siffror ännu, eftersom de är 842 00:35:56,640 --> 00:35:58,230 bara skräp värden. 843 00:35:58,230 --> 00:35:59,720 >> Men nu vad händer? 844 00:35:59,720 --> 00:36:03,280 Anta att jag köa mig själv, 26? 845 00:36:03,280 --> 00:36:05,890 Jag känner att jag hör hemma här. 846 00:36:05,890 --> 00:36:06,890 Så jag blir kö. 847 00:36:06,890 --> 00:36:08,760 Så jag slags hör hemma här. 848 00:36:08,760 --> 00:36:11,300 Och även om du inte riktigt uppskatta detta visuellt på scenen, 849 00:36:11,300 --> 00:36:15,075 eftersom vi har gott om utrymme, skulle jag inte stå här, varför? 850 00:36:15,075 --> 00:36:16,290 >> Publik: Du är out of bounds. 851 00:36:16,290 --> 00:36:16,370 >> DAVID MALAN: Höger. 852 00:36:16,370 --> 00:36:16,940 Jag är out of bounds. 853 00:36:16,940 --> 00:36:19,330 Jag har indexerat bortom gränserna för denna grupp. 854 00:36:19,330 --> 00:36:23,420 Jag borde verkligen vara i en av de tre möjliga lägen. 855 00:36:23,420 --> 00:36:25,150 Nu, var är mest naturligt att gå? 856 00:36:25,150 --> 00:36:27,760 Jag föreslår att vi belånade en vecka ett trick. 857 00:36:27,760 --> 00:36:30,150 Det mod operatör, procent. 858 00:36:30,150 --> 00:36:36,850 Eftersom jag tekniskt står vid Plats 3, men jag gör 3 mod kapacitet, 859 00:36:36,850 --> 00:36:40,250 så 3, ett procenttecken, 3 - 860 00:36:40,250 --> 00:36:40,970 kapacitet är 3. 861 00:36:40,970 --> 00:36:41,720 Vad är det? 862 00:36:41,720 --> 00:36:43,700 Vad är resten då du dela upp 3 av 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Så det sätter mig var Jake var, som är faktiskt bra. 865 00:36:48,140 --> 00:36:50,370 Så nu genomförandet av denna sak kommer att 866 00:36:50,370 --> 00:36:51,250 vara lite av en huvudvärk. 867 00:36:51,250 --> 00:36:53,740 Det är egentligen bara en rad av huvudvärk, av koden. 868 00:36:53,740 --> 00:36:56,580 Men åtminstone nu finns sopor värde här, men det finns två 869 00:36:56,580 --> 00:36:57,910 legitima ints här. 870 00:36:57,910 --> 00:37:04,160 Och jag hävdar att vi nu har gjort precis vad vi behöver göra, så länge 871 00:37:04,160 --> 00:37:08,600 vi ändrar vad Jakes Värdet var att vara 26. 872 00:37:08,600 --> 00:37:12,110 >> Vi har nu tillräckligt med information fortfarande att bibehålla integriteten 873 00:37:12,110 --> 00:37:13,060 av denna datastruktur. 874 00:37:13,060 --> 00:37:17,160 Vi är fortfarande lite av lycka när vi vill infoga fyra eller fler totalt 875 00:37:17,160 --> 00:37:20,740 element, men jag kan åtminstone göra ganska effektiv användning av denna konstant 876 00:37:20,740 --> 00:37:21,740 tid, faktiskt. 877 00:37:21,740 --> 00:37:27,150 Jag behöver inte oroa sig för att flytta alla, som Davids lutning var. 878 00:37:27,150 --> 00:37:30,816 >> Eventuella frågor om stackar, eller denna kö? 879 00:37:30,816 --> 00:37:32,184 >> Publik: Är anledningen du behöver storlek så att du vet 880 00:37:32,184 --> 00:37:34,010 var att ha en person? 881 00:37:34,010 --> 00:37:34,770 >> DAVID MALAN: Exakt. 882 00:37:34,770 --> 00:37:38,230 Jag behöver veta storleken på arrayen eftersom jag vill veta exakt hur 883 00:37:38,230 --> 00:37:41,940 många av dessa värden är legitima, och så att jag kan hitta var att sätta 884 00:37:41,940 --> 00:37:42,800 nästa person. 885 00:37:42,800 --> 00:37:43,300 Exakt. 886 00:37:43,300 --> 00:37:44,580 Storleken är - 887 00:37:44,580 --> 00:37:46,360 faktiskt, vi uppdaterar inte här ännu. 888 00:37:46,360 --> 00:37:48,380 Jag la mig vid 26. 889 00:37:48,380 --> 00:37:51,760 Storleken är nu, inte en, utan två. 890 00:37:51,760 --> 00:37:57,780 Så nu detta hjälper faktiskt mig att hitta av listan, vilket inte är 0, inte 891 00:37:57,780 --> 00:37:59,250 1, men är 2. 892 00:37:59,250 --> 00:38:01,665 Framsidan av listan är verkligen nummer 22. 893 00:38:01,665 --> 00:38:05,120 Eftersom han kom in först, så han borde släppas in i butiken innan mig, 894 00:38:05,120 --> 00:38:08,780 trots att visuellt står jag närmare till butiken. 895 00:38:08,780 --> 00:38:09,220 >> Okej? 896 00:38:09,220 --> 00:38:12,410 En applåd för killarna och vi låter dem därifrån. 897 00:38:12,410 --> 00:38:17,090 >> [Applåder] 898 00:38:17,090 --> 00:38:18,150 >> DAVID MALAN: jag kunde låta du håller facket. 899 00:38:18,150 --> 00:38:20,760 Vi kunde se vad som händer om du vill, men kanske inte. 900 00:38:20,760 --> 00:38:21,590 Okej. 901 00:38:21,590 --> 00:38:25,380 Så vad händer nu lämnar det oss? 902 00:38:25,380 --> 00:38:28,900 Nåväl, låt mig föreslå att det finns en några andra datastrukturer vi kunde 903 00:38:28,900 --> 00:38:33,810 börja lägga till vår verktygslåda som kommer faktiskt vara ganska, ganska relevant som 904 00:38:33,810 --> 00:38:35,270 Vi dyker in web grejer. 905 00:38:35,270 --> 00:38:38,150 Som återigen, har någon form av anslutning till träd i form av 906 00:38:38,150 --> 00:38:40,550 något som kallas DOM, dokument objektmodellen. 907 00:38:40,550 --> 00:38:42,370 Men vi får se mer av att innan lång. 908 00:38:42,370 --> 00:38:46,260 >> Låt mig föreslå definitionally att vi ringa träd nu vad ni kanske vet så 909 00:38:46,260 --> 00:38:48,820 mer av ett släktträd, där du har någon förfader på 910 00:38:48,820 --> 00:38:49,790 rötterna på trädet. 911 00:38:49,790 --> 00:38:54,480 En patriarkalisk eller en matriark på högst upp i trädet. 912 00:38:54,480 --> 00:38:56,700 Utan sin make, i det här fallet. 913 00:38:56,700 --> 00:39:00,940 Men vi har nu vad vi kallar barn, vilka är noder som hänger 914 00:39:00,940 --> 00:39:05,480 utanför den vänstra underordnade eller högra underordnade behandlingselementet, pilar som avbildas här. 915 00:39:05,480 --> 00:39:10,490 >> Med andra ord, i en träddatastruktur i datorn, har ett träd noll 916 00:39:10,490 --> 00:39:11,480 eller fler noder. 917 00:39:11,480 --> 00:39:13,500 Om den har åtminstone en nod, som kallas roten. 918 00:39:13,500 --> 00:39:15,700 Det är de saker visuellt att vi drar på toppen. 919 00:39:15,700 --> 00:39:20,280 Och den noden, som alla andra noder, kan ha noll, en eller två, eller tre, 920 00:39:20,280 --> 00:39:23,600 eller hur många barn de datastruktur stöder. 921 00:39:23,600 --> 00:39:29,150 I detta fall, roten, lagra värdet ett, har två barn, 2 och 3, 922 00:39:29,150 --> 00:39:33,020 så vi kallar generellt 2 vänster barn och 3 rätt barnet. 923 00:39:33,020 --> 00:39:36,940 >> Och sedan när vi kommer ner till 5, 6, och 7, 6 skulle kunna kallas mitt barn. 924 00:39:36,940 --> 00:39:38,940 Om du har fyra barn, det blir förvirrande. 925 00:39:38,940 --> 00:39:42,260 Så vi slutar använda denna typ av genvägen verbalt. 926 00:39:42,260 --> 00:39:44,580 Men det är egentligen bara ett släktträd. 927 00:39:44,580 --> 00:39:48,880 Och bladen här är de noder som själva har inga barn. 928 00:39:48,880 --> 00:39:52,540 De hänger ut längst ned i trädet. 929 00:39:52,540 --> 00:39:56,940 >> Så hur kan vi implementera ett träd som har bara två barn maximalt? 930 00:39:56,940 --> 00:39:58,410 Vi kallar det ett binärt träd. 931 00:39:58,410 --> 00:40:00,960 Bi betyder återigen två, i detta fall, som med binär. 932 00:40:00,960 --> 00:40:04,830 Och så den kan ha noll, en, eller två barn maximalt. 933 00:40:04,830 --> 00:40:08,650 >> Jag föreslår att vi genomför noden för denna struktur med en int n, 934 00:40:08,650 --> 00:40:11,910 och därefter två pekare, som kallas en vänster, en som heter rätt. 935 00:40:11,910 --> 00:40:14,830 Men de är bara trevligt godtyckliga konventioner. 936 00:40:14,830 --> 00:40:18,170 Och vad är bra nu, speciellt om du slags kämpade konceptuellt med 937 00:40:18,170 --> 00:40:21,300 rekursion, eller trodde att det inte var verkligen en lösning på någonting, 938 00:40:21,300 --> 00:40:23,120 speciellt om du kunde slut på minne. 939 00:40:23,120 --> 00:40:26,600 Nu när vi pratar om uppgifter strukturer och algoritmer som gör det möjligt 940 00:40:26,600 --> 00:40:31,030 oss att korsa och manipulera dem, visar sig att rekursion kommer tillbaka i 941 00:40:31,030 --> 00:40:34,240 en mycket mer övertygande om inte vackert sätt. 942 00:40:34,240 --> 00:40:38,670 >> Så här jag föreslår är att genomföra av en sökfunktion. 943 00:40:38,670 --> 00:40:39,870 Givet två ingångar - 944 00:40:39,870 --> 00:40:41,570 så se det som en svart låda. 945 00:40:41,570 --> 00:40:46,560 Givet två ingångar, n, en int, och en pekare till ett träd, en pekare till en 946 00:40:46,560 --> 00:40:50,020 nod, eller egentligen roten av ett träd, jag hävdar att denna funktion kan återvända 947 00:40:50,020 --> 00:40:53,530 sant eller falskt, det värde n är inne i det här trädet. 948 00:40:53,530 --> 00:40:55,210 >> Vad finns inuti denna svarta låda? 949 00:40:55,210 --> 00:40:57,440 Tja, fyra grenar. 950 00:40:57,440 --> 00:40:58,385 Den första bara kollar. 951 00:40:58,385 --> 00:41:00,490 Om trädet är null, bara returnera false. 952 00:41:00,490 --> 00:41:04,580 Om det inte finns någon nod, det finns ingen n, det finns inget nummer, bara returnera false. 953 00:41:04,580 --> 00:41:12,330 Om dock, n, värdet du söker för, är mindre än träd arrow N, och 954 00:41:12,330 --> 00:41:15,180 bara för att vara tydlig, vad betyder det när Jag skriver trädet och sedan pilen 955 00:41:15,180 --> 00:41:18,150 notation, n? 956 00:41:18,150 --> 00:41:18,690 Exakt. 957 00:41:18,690 --> 00:41:21,970 Det betyder avreferera att pekare kallas träd. 958 00:41:21,970 --> 00:41:26,750 Gå dit, och sedan komma in i det nod och få sitt område kallas n. 959 00:41:26,750 --> 00:41:30,810 Och sedan jämföra den faktiska n som var passerat in Sök mot den. 960 00:41:30,810 --> 00:41:35,390 >> Så om n är mindre än, värdet n i trädet noden själv, ja, 961 00:41:35,390 --> 00:41:36,720 vad betyder det? 962 00:41:36,720 --> 00:41:40,690 Det betyder ingenting vid första anblicken. 963 00:41:40,690 --> 00:41:40,900 Rätt? 964 00:41:40,900 --> 00:41:45,560 Precis som när du har en samling av värden, kanske du vill använda binära 965 00:41:45,560 --> 00:41:48,290 söka som en form av klyftan och erövra. 966 00:41:48,290 --> 00:41:51,790 Men vad antagandet behövde vi göra för binär sökning till fungerar alls 967 00:41:51,790 --> 00:41:54,510 i telefonboken och tidigare exempel? 968 00:41:54,510 --> 00:41:55,530 >> Hur ska sorteras. 969 00:41:55,530 --> 00:41:59,490 Så låt oss förfina definitionen av trädet här inte bara vara ett träd, vilket kan 970 00:41:59,490 --> 00:42:00,880 ha valfritt antal barn. 971 00:42:00,880 --> 00:42:04,700 Inte bara ett binärt träd, vilket kan har 0, 1, eller 2 maximalt. 972 00:42:04,700 --> 00:42:09,700 Men som ett binärt sökträd, eller BST, vilket är bara ett finare sätt att säga en 973 00:42:09,700 --> 00:42:15,430 binärt träd, så att varje nods vänstra barnet, om sådan finns, är 974 00:42:15,430 --> 00:42:16,830 mindre än noden. 975 00:42:16,830 --> 00:42:20,170 Och varje nods högra barn, om den är närvarande, är större 976 00:42:20,170 --> 00:42:21,740 än själva noden. 977 00:42:21,740 --> 00:42:25,200 >> Så med andra ord, om du skulle rita trädet ut, alla nummer är 978 00:42:25,200 --> 00:42:30,620 omsorgsfullt balanseras så här så att om du har 55 som root, kan 33 gå 979 00:42:30,620 --> 00:42:33,090 till vänster eftersom det är mindre än 55. 980 00:42:33,090 --> 00:42:36,430 77 kan gå till sin rätt eftersom det är större än 55. 981 00:42:36,430 --> 00:42:40,750 Men nu märker, samma definition, det är en rekursiv definition verbalt, 982 00:42:40,750 --> 00:42:42,600 måste ansöka om 33. 983 00:42:42,600 --> 00:42:47,610 33 vänstra barnet måste vara mindre än det, och 33 rätt barn, 44, måste vara 984 00:42:47,610 --> 00:42:48,580 större än den. 985 00:42:48,580 --> 00:42:51,670 >> Så detta är ett binärt sökträd, och Jag föreslår, med hjälp av en liten bit av 986 00:42:51,670 --> 00:42:53,910 rekursion, kan vi nu hitta n. 987 00:42:53,910 --> 00:42:59,160 Så om n är mindre än värdet n som är aktuella noden, jag ska gå 988 00:42:59,160 --> 00:43:04,090 framåt och punt, så att säga, och bara tillbaka vad svaret är på 989 00:43:04,090 --> 00:43:08,470 söka för n på trädets vänstra barn. 990 00:43:08,470 --> 00:43:11,370 Lägg märke igen, denna funktion bara förväntar sig en nod stjärna, en 991 00:43:11,370 --> 00:43:12,780 pekare till en nod. 992 00:43:12,780 --> 00:43:17,360 Så väl jag bara kan göra träd pil vänster, vilket kommer att leda 993 00:43:17,360 --> 00:43:18,400 mig till en annan nod. 994 00:43:18,400 --> 00:43:19,480 Men vad är denna nod? 995 00:43:19,480 --> 00:43:22,820 >> Tja, enligt denna förklaring, vänster är bara en pekare, så att bara 996 00:43:22,820 --> 00:43:27,090 betyder att jag går till sökfunktionen en annan pekare, nämligen 997 00:43:27,090 --> 00:43:30,750 den som representerar min vänstra barns träd. 998 00:43:30,750 --> 00:43:36,040 Så i detta fall, pekaren till 33, om Detta är vårt urval ingång tiden, om 999 00:43:36,040 --> 00:43:40,740 n är större än värdet n vid aktuella noden i trädet, då är jag 1000 00:43:40,740 --> 00:43:43,370 kommer att gå vidare och punt i andra riktning och bara säga, gör jag inte 1001 00:43:43,370 --> 00:43:47,280 vet om detta värde n är i trädet, men jag vet om det är, det är ner min 1002 00:43:47,280 --> 00:43:49,090 högra grenen, så att säga. 1003 00:43:49,090 --> 00:43:53,120 Så låt mig rekursivt ringa Sök, passerar en n igen, men passerar i en 1004 00:43:53,120 --> 00:43:54,580 pekare till min högra barn. 1005 00:43:54,580 --> 00:44:00,020 >> Med andra ord, om jag är närvarande vid 55 och jag letar efter 99, jag vet att 99 1006 00:44:00,020 --> 00:44:04,270 är större än 55, så precis som jag slet telefonboksinställningar veckor sedan och vi 1007 00:44:04,270 --> 00:44:07,140 gick rätt, på samma sätt är vi kommer att gå här. 1008 00:44:07,140 --> 00:44:11,960 Och jag vet inte om det är på min högra barn, och det är inte, är 77 där, men 1009 00:44:11,960 --> 00:44:13,210 Jag vet att det är i den riktningen. 1010 00:44:13,210 --> 00:44:18,770 Så jag kallar sökning på min högra barn, 77, och låt sökning figur ut från 1011 00:44:18,770 --> 00:44:24,950 där om 99 i denna godtyckliga exempel är faktiskt där. 1012 00:44:24,950 --> 00:44:26,900 >> Else, vad är det slutliga målet? 1013 00:44:26,900 --> 00:44:28,620 Om trädet är null är ett fall. 1014 00:44:28,620 --> 00:44:31,890 Om n är mindre än den aktuella nodens värde är ett annat fall. 1015 00:44:31,890 --> 00:44:35,120 Om n är större än den aktuella nodens värde är ett tredje fall. 1016 00:44:35,120 --> 00:44:38,250 Vad är den fjärde och sista målet? 1017 00:44:38,250 --> 00:44:39,480 Jag tror att vi är ute på ärenden, eller hur? 1018 00:44:39,480 --> 00:44:44,690 Det måste vara att n är i nuvarande nod som jag är på. 1019 00:44:44,690 --> 00:44:49,640 >> Så om jag söker efter 55 på denna punkt i berättelsen, den gren av 1020 00:44:49,640 --> 00:44:51,780 träd skulle återvända sant. 1021 00:44:51,780 --> 00:44:55,380 Så vad är intressant här är att vi faktiskt, till skillnad veckor tidigare, typ vi 1022 00:44:55,380 --> 00:44:56,740 av har två basfallen. 1023 00:44:56,740 --> 00:44:58,300 Och de behöver inte vara allt på toppen. 1024 00:44:58,300 --> 00:45:01,390 Toppen är ett basfall för om träd är null, det finns inget att göra. 1025 00:45:01,390 --> 00:45:03,410 Bara returnera en hård kodad värdet false. 1026 00:45:03,410 --> 00:45:07,400 >> Den nedersta grenen är typ av standard, vilket om vi har kontrollerat för 1027 00:45:07,400 --> 00:45:11,550 null, har vi kontrollerat om det skulle vara kvar, men det borde inte vara, har vi 1028 00:45:11,550 --> 00:45:14,640 kontrolleras om det skulle vara rätt, men det inte bör vara, tydligt att det måste vara 1029 00:45:14,640 --> 00:45:15,870 precis där vi är. 1030 00:45:15,870 --> 00:45:16,780 Det är ett basfall. 1031 00:45:16,780 --> 00:45:19,920 Så det finns två rekursiva fall inklämt där i mitten. 1032 00:45:19,920 --> 00:45:21,630 Men jag kunde ha skrivit detta i valfri ordning. 1033 00:45:21,630 --> 00:45:24,520 Jag tyckte bara det kändes slags naturlig att först kontrollera om ett eventuellt fel, 1034 00:45:24,520 --> 00:45:28,340 så kolla vänster, så kolla till höger, sedan antar att du är på noden 1035 00:45:28,340 --> 00:45:30,630 du är faktiskt ute efter. 1036 00:45:30,630 --> 00:45:36,240 >> Så varför skulle detta vara användbart? 1037 00:45:36,240 --> 00:45:37,910 Så visar det sig - 1038 00:45:37,910 --> 00:45:42,110 och låt mig hoppa till en teaser här som är i nätet. 1039 00:45:42,110 --> 00:45:44,920 Vi kommer att börja använda inte en programmeringsspråk vid första, men en 1040 00:45:44,920 --> 00:45:46,030 märkningsspråk. 1041 00:45:46,030 --> 00:45:48,740 Ett märkspråk är en som är i samma anda som programmering 1042 00:45:48,740 --> 00:45:51,715 språk, men det ger inte dig förmåga att uttrycka dig logiskt. 1043 00:45:51,715 --> 00:45:55,070 Det ger bara dig möjlighet att uttrycka dig strukturellt. 1044 00:45:55,070 --> 00:45:57,960 >> Vart vill du sätta något på sidan, på webbsidan? 1045 00:45:57,960 --> 00:45:59,200 Vilken färg vill du göra det? 1046 00:45:59,200 --> 00:46:00,950 Vilken textstorlek vill du göra det? 1047 00:46:00,950 --> 00:46:02,970 Vilka ord vill du verkligen vill på webbsidan? 1048 00:46:02,970 --> 00:46:04,060 Så det är ett märkspråk. 1049 00:46:04,060 --> 00:46:07,690 Men sedan kommer vi mycket snabbt införa JavaScript, vilket är en fullfjädrad 1050 00:46:07,690 --> 00:46:08,560 programmeringsspråk. 1051 00:46:08,560 --> 00:46:12,530 Mycket lik syntaktiskt i utseende till C, men det tar lite 1052 00:46:12,530 --> 00:46:15,200 trevligt, mer kraftfull, mer användarvänliga funktioner. 1053 00:46:15,200 --> 00:46:18,050 >> Och en av de frustrationer på detta punkt i terminen är att vi ska 1054 00:46:18,050 --> 00:46:22,065 snart genomföra speller i betydligt färre rader kod som använder andra språk 1055 00:46:22,065 --> 00:46:25,580 än C själv medger, men för förnuftets Vi kommer snart att förstå. 1056 00:46:25,580 --> 00:46:27,750 Detta kommer att bli den första webbsidan. 1057 00:46:27,750 --> 00:46:30,120 Det kommer att vara helt underwhelming, det första vi gör. 1058 00:46:30,120 --> 00:46:31,400 Det kommer helt enkelt att säga, hej världen. 1059 00:46:31,400 --> 00:46:34,010 Men om du aldrig har sett den tidigare, är denna HTML, 1060 00:46:34,010 --> 00:46:35,670 HyperText Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> Om du går till en viss menyalternativ i mest alla webbläsare, på en webbsida på 1062 00:46:39,310 --> 00:46:43,160 Internet, kan du se HTML att vissa människor skrev till 1063 00:46:43,160 --> 00:46:44,400 skapa den webbsidan. 1064 00:46:44,400 --> 00:46:47,850 Och det är förmodligen inte ser så kort eller så snyggt som det här. 1065 00:46:47,850 --> 00:46:51,400 Men det kommer att följa mönstret i dessa öppna fästen och snedstreck och 1066 00:46:51,400 --> 00:46:53,660 bokstäver och potentiellt siffror. 1067 00:46:53,660 --> 00:46:56,770 >> Jag trodde jag skulle ge dig en teaser av vad du kommer att kunna göra 1068 00:46:56,770 --> 00:46:57,950 efter att ha tagit CS50. 1069 00:46:57,950 --> 00:47:02,620 Låt mig gå till cs.harvard.edu / rob, vår egen Rob Bowden hemsida. 1070 00:47:02,620 --> 00:47:06,080 Han gjorde detta för oss. 1071 00:47:06,080 --> 00:47:07,490 Så du kommer snart att kunna göra det. 1072 00:47:07,490 --> 00:47:10,660 Och dessutom, vad du hört i morse - 1073 00:47:10,660 --> 00:47:12,480 vad du hörde i morse - 1074 00:47:12,480 --> 00:47:13,780 >> [HAMSTER Dansmusik] 1075 00:47:13,780 --> 00:47:15,702 >> - Du ska kunna göra detta. 1076 00:47:15,702 --> 00:47:16,790 Som väntar oss på onsdag. 1077 00:47:16,790 --> 00:47:17,791 Vi kommer att se dig då. 1078 00:47:17,791 --> 00:47:22,950 >> [HAMSTER Dansmusik] 1079 00:47:22,950 --> 00:47:24,300 DAVID MALAN: Vid nästa CS50 - 1080 00:47:24,300 --> 00:47:31,670