1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> David Malan: Alle reg. 3 00:00:12,250 --> 00:00:13,860 Welkom terug na CS50. 4 00:00:13,860 --> 00:00:16,190 Dit is die begin van die week 8. 5 00:00:16,190 --> 00:00:21,320 En onthou dat die probleem stel 5 geëindig met 'n bietjie van 'n uitdaging. 6 00:00:21,320 --> 00:00:25,210 So die veronderstelling dat jy herstel van al jou onderrig Fellows en GR se foto's 7 00:00:25,210 --> 00:00:30,480 in die card.raw lêer, kom jy in aanmerking nou vind al die mense, en 8 00:00:30,480 --> 00:00:34,510 een gelukkige wenner sal huis toe stap met een van hierdie dinge, die sprong beweging 9 00:00:34,510 --> 00:00:37,450 toestel wat jy kan gebruik vir die finale projekte, byvoorbeeld. 10 00:00:37,450 --> 00:00:39,860 >> Dit is elke jaar, lei tot 'n bietjie van creepiness. 11 00:00:39,860 --> 00:00:43,480 En so wat ek gedink ek wil doen, is deel met jou 'n paar van die note wat 12 00:00:43,480 --> 00:00:47,370 gegaan heen en weer oor die personeel lys van laat. 13 00:00:47,370 --> 00:00:51,110 Byvoorbeeld, net gisteraand, quote unquote, uit een van die personeel 14 00:00:51,110 --> 00:00:55,000 lede, "Ek het net 'n student klop aan my deur 'n foto met my te neem. 15 00:00:55,000 --> 00:00:59,020 Agtervolgers, sê ek jou "begin. redelik beskrywende en dan het ons verhuis 16 00:00:59,020 --> 00:01:02,830 aan, 'n uur of so later, "Ek het 'n student wag vir my na artikel 17 00:01:02,830 --> 00:01:06,080 en hy het al ons name en foto's op 'n paar velle papier "Alles reg.. 18 00:01:06,080 --> 00:01:09,230 So georganiseer, maar nie almal wat creepy nie. 19 00:01:09,230 --> 00:01:12,520 >> Dan, "Ek was uit die dorp die naweek, en toe ek terug was daar een in 20 00:01:12,520 --> 00:01:12,630 my 21 00:01:12,630 --> 00:01:16,740 slaapkamer ". [Gelag] 22 00:01:16,740 --> 00:01:20,410 David Malan: Volgende aanhaling uit 'n personeellid lid ", 'n student by my huis op 23 00:01:20,410 --> 00:01:25,330 Somerville by 04:00 vanoggend "Volgende. personeel, "Ek het na my hotel in San 24 00:01:25,330 --> 00:01:30,016 Francisco en 'n student was die wag vir my aan die gang met drie DSLRs. " 25 00:01:30,016 --> 00:01:31,510 Tipe kamera. 26 00:01:31,510 --> 00:01:34,980 "Ek is nie eens op die personeel van hierdie semester, maar 'n student het gebreek in my huis hierdie 27 00:01:34,980 --> 00:01:40,480 oggend en aangeteken om die hele ding met Google Glass "En dan is. Laastens, 28 00:01:40,480 --> 00:01:43,650 "Ten minste 12 mense is gretig wag vir my wanneer ek uit my 29 00:01:43,650 --> 00:01:44,800 limo, en dan het ek 30 00:01:44,800 --> 00:01:46,970 wakker "Alles reg.. 31 00:01:46,970 --> 00:01:57,690 So tussen die foto's, as jy kan onthou, is hierdie man hier, wat jy 32 00:01:57,690 --> 00:02:01,850 kan weet as Milo Banana, wat woon met Lauren Carvalho, ons kop 33 00:02:01,850 --> 00:02:02,905 Mede-onderrig. 34 00:02:02,905 --> 00:02:05,170 Milo, Milo, hier kom seuntjie. 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 u, hy dra Google Glass, so ons sal jou wys al hierdie na. 38 00:02:12,230 --> 00:02:16,190 So is dit Milo as jy wil neem 'n foto saam met hom daarna. 39 00:02:16,190 --> 00:02:18,240 As jy wil om te kyk uit aan die gehoor daar. 40 00:02:18,240 --> 00:02:19,430 OK. 41 00:02:19,430 --> 00:02:20,200 Dit is 'n goeie footage. 42 00:02:20,200 --> 00:02:22,556 Wel, Milo piesang. 43 00:02:22,556 --> 00:02:23,941 O ja, dit nie doen nie. 44 00:02:23,941 --> 00:02:29,020 >> [Gelag] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 So 'n woord dan oor wat voorlê, want as ons begin met die oorgang, 47 00:02:34,550 --> 00:02:38,410 hierdie week spesifiek, van C in 'n command line omgewing te PHP en 48 00:02:38,410 --> 00:02:42,720 JavaScript en SQL en HTML en CSS in 'n web-gebaseerde omgewing, sal ons 49 00:02:42,720 --> 00:02:44,490 toe te rus met al die meer kennis vir 50 00:02:44,490 --> 00:02:46,010 potensiaal finale projekte. 51 00:02:46,010 --> 00:02:49,240 In die rigting van die einde, die kursus het 'n tradisie van die hou van seminare wat 52 00:02:49,240 --> 00:02:50,950 is op tangensiaal onderwerpe tot die kursus. 53 00:02:50,950 --> 00:02:54,330 Baie verband hou met ontwikkeling en app ontwikkeling en so meer, maar 54 00:02:54,330 --> 00:02:57,010 nie noodwendig ondersoek deur die kursus se eie leerplan. 55 00:02:57,010 --> 00:03:00,250 >> So as jy dalk belangstel in 'n of meer van hierdie jaar se seminare, 56 00:03:00,250 --> 00:03:02,530 registreer op cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Daar is ouer seminare by cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 En op die rooster tot dusver vir hierdie jaar is Amazing Web Apps met Ruby on 59 00:03:10,620 --> 00:03:13,580 Relings, wat is 'n alternatief taal te PHP. 60 00:03:13,580 --> 00:03:14,900 Rekenaarlinguistiek. 61 00:03:14,900 --> 00:03:18,710 Inleiding tot IOS, wat die platform vir die iPhone wat gebruik is en 62 00:03:18,710 --> 00:03:19,850 iPad ontwikkeling. 63 00:03:19,850 --> 00:03:22,890 JavaScript vir Web Apps, sal ons dek dit nie, maar in hierdie seminaar, sal jy gaan 64 00:03:22,890 --> 00:03:24,070 in meer detail. 65 00:03:24,070 --> 00:03:27,390 >> Spring Motion, so ons sal eintlik 'n paar van ons vriende van die sprong Motion, 66 00:03:27,390 --> 00:03:29,160 die maatskappy self, by ons aansluit. 67 00:03:29,160 --> 00:03:31,800 Môre, in werklikheid, te verskaf 'n hands-on seminaar, indien 68 00:03:31,800 --> 00:03:33,320 van belang is vir jou. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, 'n alternatiewe tegniek vir met behulp van JavaScript nie in 'n leser, 70 00:03:38,770 --> 00:03:39,970 maar op 'n bediener. 71 00:03:39,970 --> 00:03:42,110 Node.js, wat baie in dié trant as well. 72 00:03:42,110 --> 00:03:43,650 Glad Android Design. 73 00:03:43,650 --> 00:03:46,990 Android 'n baie gewilde alternatief te IOS en Windows Phone 74 00:03:46,990 --> 00:03:48,790 en ander mobiele platforms. 75 00:03:48,790 --> 00:03:51,180 En Web Security Active verdediging. 76 00:03:51,180 --> 00:03:54,590 >> So in werklikheid, as jy wil om betrokke te raak in hierdie, laat my 77 00:03:54,590 --> 00:03:55,840 maak hiervan kennis. 78 00:03:55,840 --> 00:03:57,790 Ons is baie bly om te sê dat ons vriende by Leap 79 00:03:57,790 --> 00:03:59,140 Beweging, wat is 'n begin - 80 00:03:59,140 --> 00:04:01,300 hierdie toestel regtig net gekom 'n paar maande gelede - 81 00:04:01,300 --> 00:04:05,960 uit genade geskenk het 30 sulke toestelle na die klas vir soveel studente as 82 00:04:05,960 --> 00:04:08,670 jy wil die hardeware te leen teenoor semester se einde en dit gebruik vir 83 00:04:08,670 --> 00:04:10,390 'n werklike finale projek. 84 00:04:10,390 --> 00:04:11,890 Hulle ondersteun 'n aantal tale. 85 00:04:11,890 --> 00:04:16,040 Nie een van hulle C, nie een van hulle PHP, so besef een of meer van die seminare 86 00:04:16,040 --> 00:04:16,899 kan bewys van belang. 87 00:04:16,899 --> 00:04:19,730 En almal van hulle sal verfilm word in die geval dat jy nie in staat is om 88 00:04:19,730 --> 00:04:21,380 persoonlik by te woon. 89 00:04:21,380 --> 00:04:25,000 Die skedule aangekondig word via e-pos as ons stol kamers. 90 00:04:25,000 --> 00:04:28,460 >> En laastens, as jy gaan na projects.cs.50.net, dit is 'n webwerf 91 00:04:28,460 --> 00:04:31,450 Ons hou elke jaar wat ons nooi mense uit die gemeenskap, die fakulteit, 92 00:04:31,450 --> 00:04:36,420 departemente, personeel en beide in 'n buite CS50 te 93 00:04:36,420 --> 00:04:37,730 stel projek idees. 94 00:04:37,730 --> 00:04:39,050 Dinge van belang is vir student groepe. 95 00:04:39,050 --> 00:04:40,600 Dinge van belang is vir departemente. 96 00:04:40,600 --> 00:04:43,990 So draai daar nie as jy sukkel met onsekerheid oor wat jy 97 00:04:43,990 --> 00:04:46,700 jouself wil graag aan te pak. 98 00:04:46,700 --> 00:04:51,760 >> So laaste keer dat ons 'n waarskynlik meer komplekse data struktuur as wat ons wil 99 00:04:51,760 --> 00:04:53,300 gesien in weke verlede. 100 00:04:53,300 --> 00:04:56,550 Ons wil al met behulp van skikkings mooi gelukkig as 'n nuttige indien 101 00:04:56,550 --> 00:04:58,160 eenvoudige data struktuur. 102 00:04:58,160 --> 00:05:00,570 Daarna het ons het dié wat natuurlik gekoppel lyste. 103 00:05:00,570 --> 00:05:05,470 En wat was een van die motivering vir bekendstelling van hierdie data struktuur? 104 00:05:05,470 --> 00:05:06,930 Ja? 105 00:05:06,930 --> 00:05:07,250 Wat is dit? 106 00:05:07,250 --> 00:05:08,080 >> GEHOOR: Dynamic grootte. 107 00:05:08,080 --> 00:05:09,040 >> David Malan: Dynamic grootte. 108 00:05:09,040 --> 00:05:11,890 So terwyl dit in skikking, wat jy hoef te weet sy grootte vooruit 109 00:05:11,890 --> 00:05:12,740 jy ken dit. 110 00:05:12,740 --> 00:05:14,380 In gekoppel lys, wat jy doen nie het om te weet dat. 111 00:05:14,380 --> 00:05:17,610 Jy kan nie net malloc, of meer algemeen, Ken 'n addisionele 112 00:05:17,610 --> 00:05:20,720 knoop, om so te praat, enige tyd wat jy wil meer inligting by te voeg. 113 00:05:20,720 --> 00:05:22,670 En node het geen voorafbepaalde betekenis. 114 00:05:22,670 --> 00:05:25,580 Dit is net 'n generiese term wat 'n soort van houer wat ons is 115 00:05:25,580 --> 00:05:29,610 gebruik in ons data struktuur te stoor 'n item van belang, wat in hierdie 116 00:05:29,610 --> 00:05:31,750 geval gebeur om te wees heelgetalle. 117 00:05:31,750 --> 00:05:33,160 >> Maar daar is altyd 'n nadeel. 118 00:05:33,160 --> 00:05:38,070 So kry ons dinamiese groottes van die data struktuur, maar watter prys betaal ons? 119 00:05:38,070 --> 00:05:40,040 Wat is die negatiewe kant van geskakelde lyste? 120 00:05:40,040 --> 00:05:41,006 Ja? 121 00:05:41,006 --> 00:05:41,980 >> GEHOOR: vereis meer geheue. 122 00:05:41,980 --> 00:05:44,240 >> David Malan: Dit vereis meer geheue, hoe presies? 123 00:05:44,240 --> 00:05:46,440 >> GEHOOR: [onhoorbaar]. 124 00:05:46,440 --> 00:05:47,050 >> David Malan: Presies. 125 00:05:47,050 --> 00:05:50,460 So nou het ons wenke neem addisionele geheue wat ons voorheen 126 00:05:50,460 --> 00:05:53,040 het nie nodig nie, omdat die voordeel van 'n skikking, natuurlik, is dat 127 00:05:53,040 --> 00:05:54,860 alles is aangrensend, terug om terug te rug, wat 128 00:05:54,860 --> 00:05:56,380 gee jou ewekansige toegang. 129 00:05:56,380 --> 00:06:00,710 Want net deur die gebruik van vierkante hakies notasie, of meer tegnies wyser 130 00:06:00,710 --> 00:06:03,580 rekenkundige, baie eenvoudige Daarbenewens, kan jy toegang tot enige 131 00:06:03,580 --> 00:06:05,700 elemente in konstante tyd. 132 00:06:05,700 --> 00:06:08,975 En in waarheid te sê, dit is soort van sinspeel op 'n ander prys wat ons betaal met 'n 133 00:06:08,975 --> 00:06:09,760 gekoppel lys. 134 00:06:09,760 --> 00:06:13,890 >> Wat gebeur met die loop van die tyd van iets soos Search, as ek wil 135 00:06:13,890 --> 00:06:17,270 'n paar waarde en binne van 'n geskakelde lys? 136 00:06:17,270 --> 00:06:20,290 Wat beteken my loop tyd geword het? 137 00:06:20,290 --> 00:06:21,560 Big O van n. 138 00:06:21,560 --> 00:06:24,060 As dit gesorteer? 139 00:06:24,060 --> 00:06:25,440 Wat as die data struktuur is gesorteer? 140 00:06:25,440 --> 00:06:28,640 Kan ek doen beter as groot O van n soek? 141 00:06:28,640 --> 00:06:31,700 Nee, want in die ergste geval is dit dalk baie goed gesorteer word, maar die aantal 142 00:06:31,700 --> 00:06:32,950 jy soek dalk groot wees. 143 00:06:32,950 --> 00:06:35,370 Dit mag dalk die getal 100, wat wees kan gebeur om te wees al 144 00:06:35,370 --> 00:06:36,410 die pad aan die einde. 145 00:06:36,410 --> 00:06:39,950 En omdat jy kan net toegang tot 'n gekoppelde lys in die implementering van hierdie deur 146 00:06:39,950 --> 00:06:42,690 weg van sy eerste knoop, jy nog soort van uit van geluk. 147 00:06:42,690 --> 00:06:47,450 Jy het die hele ding te deurkruis vanaf die eerste tot die laaste om uit te vind 148 00:06:47,450 --> 00:06:49,150 dat die groot waarde soos 100. 149 00:06:49,150 --> 00:06:51,350 Of om te bepaal of dit nie eens daar nie. 150 00:06:51,350 --> 00:06:55,960 >> So kan ons nie doen wat algoritme in 'n data struktuur wat lyk soos hierdie? 151 00:06:55,960 --> 00:06:59,460 Ons kan dit nie doen binêre soek, want binêre soek vereis dat ons 152 00:06:59,460 --> 00:07:00,740 ewekansige toegang. 153 00:07:00,740 --> 00:07:04,500 Ons kan net spring van plek tot plek sonder om te volg 154 00:07:04,500 --> 00:07:07,080 hierdie broodkrummels in die vorm van al hierdie wenke. 155 00:07:07,080 --> 00:07:08,300 >> Nou, hoe het ons hierdie? 156 00:07:08,300 --> 00:07:12,830 Wel, as ons na die skerm hier, indien ons kan vinnig reimplement hierdie data 157 00:07:12,830 --> 00:07:13,440 struktuur - 158 00:07:13,440 --> 00:07:15,670 my handskrif is nie al wat groot hier, maar ons sal probeer. 159 00:07:15,670 --> 00:07:22,030 So typedef struct, en wat het ek wil hierdie ding te noem hier? 160 00:07:22,030 --> 00:07:22,960 Knoop. 161 00:07:22,960 --> 00:07:24,580 So ek sal aan die gang kry. 162 00:07:24,580 --> 00:07:27,860 En nou, wat gedoen moet word binne die data struktuur wat afsonderlik 163 00:07:27,860 --> 00:07:28,430 gekoppel lys? 164 00:07:28,430 --> 00:07:29,950 Hoeveel velde? 165 00:07:29,950 --> 00:07:30,450 >> So twee. 166 00:07:30,450 --> 00:07:31,570 Een daarvan is redelik maklik. 167 00:07:31,570 --> 00:07:33,050 So int n. 168 00:07:33,050 --> 00:07:35,930 En ons kan noem n iets is wat ons wil hê, maar dit moet 'n int wees as ons 169 00:07:35,930 --> 00:07:37,660 die implementering van 'n gekoppelde lys vir ints. 170 00:07:37,660 --> 00:07:41,920 En nou wat doen die tweede veld te wees? 171 00:07:41,920 --> 00:07:43,460 Struct node *. 172 00:07:43,460 --> 00:07:50,570 So as ek dit doen struct node *, en dan het ek kan noem dit ook wat ek wil, 173 00:07:50,570 --> 00:07:53,510 Maar net om duidelik te wees Ek bel dit langs, soos ons het om te doen. 174 00:07:53,510 --> 00:07:55,270 En dan sal ek sluit my krullerige draadjies. 175 00:07:55,270 --> 00:08:00,700 >> En nou, as laaste tyd, Ek sit knoop hier. 176 00:08:00,700 --> 00:08:03,830 Maar as ek verklaar dat dit is as 'n knoop, hoekom het ek die moeite om so 177 00:08:03,830 --> 00:08:07,320 verbose hier in verklaar struct knoop * langs, in teenstelling 178 00:08:07,320 --> 00:08:09,210 om net te knoop * volgende? 179 00:08:09,210 --> 00:08:09,904 Ja? 180 00:08:09,904 --> 00:08:12,810 >> GEHOOR: [onhoorbaar]. 181 00:08:12,810 --> 00:08:14,050 >> David Malan: Presies. 182 00:08:14,050 --> 00:08:14,530 Presies. 183 00:08:14,530 --> 00:08:18,320 Omdat C neem jy regtig letterlik en kyk net die definisie van node 184 00:08:18,320 --> 00:08:21,230 pad af hier, jy kan nie verwys na dit hier. 185 00:08:21,230 --> 00:08:24,760 So ons het hierdie soort preventive verklaring hier, wat weliswaar 186 00:08:24,760 --> 00:08:25,390 meer verbose. 187 00:08:25,390 --> 00:08:27,810 Struct knoop, wat beteken Ons kan nou toegang tot die 188 00:08:27,810 --> 00:08:29,760 binnekant van die data struktuur. 189 00:08:29,760 --> 00:08:33,370 >> En as 'n eenkant, want dit is besig om 'n bietjie meer subjektiewe nou, 190 00:08:33,370 --> 00:08:36,230 die ster kan tegnies hier gaan, kan dit hier gaan, kan dit 191 00:08:36,230 --> 00:08:37,179 selfs gaan in die middel. 192 00:08:37,179 --> 00:08:39,890 Ons het aangeneem, in die styl gids vir die kursus, die konvensie van die plaas 193 00:08:39,890 --> 00:08:42,299 die ster reg langs die data tipe, wat in hierdie geval, 194 00:08:42,299 --> 00:08:43,460 sou struct node wees. 195 00:08:43,460 --> 00:08:46,620 Maar besef in 'n baie handboeke en aanlyn verwysings, dan kan jy inderdaad 196 00:08:46,620 --> 00:08:48,450 sien dit aan die ander kant. 197 00:08:48,450 --> 00:08:52,200 Maar net besef dat beide sal eintlik werk en jy moet eenvoudig wees 198 00:08:52,200 --> 00:08:52,970 konsekwent. 199 00:08:52,970 --> 00:08:53,580 >> Alle regte. 200 00:08:53,580 --> 00:08:55,630 So dit was ons verklaring van struct knoop. 201 00:08:55,630 --> 00:08:59,430 Maar dan moet ons begin om meer te doen gesofistikeerde dinge. 202 00:08:59,430 --> 00:09:03,410 Byvoorbeeld, het ons besluit om in te voer iets soos 'n hash tafel. 203 00:09:03,410 --> 00:09:08,160 So hier is 'n hash tafel van grootte n, geïndekseer vanaf 0 op die boonste links na n 204 00:09:08,160 --> 00:09:09,690 minus 1 op die links onder. 205 00:09:09,690 --> 00:09:11,640 Dit kan 'n gemors tafel vir enigiets. 206 00:09:11,640 --> 00:09:15,340 Maar watter soort dinge het ons praat oor die gebruik van 'n hash tafel? 207 00:09:15,340 --> 00:09:18,370 Stoor wat? 208 00:09:18,370 --> 00:09:18,800 >> Name. 209 00:09:18,800 --> 00:09:20,870 Ons kan doen name soos ons gedoen het die afgelope tyd. 210 00:09:20,870 --> 00:09:22,200 En regtig, kan jy dit stoor nie. 211 00:09:22,200 --> 00:09:24,640 En ons sal sien dit weer in PHP en in JavaScript. 212 00:09:24,640 --> 00:09:28,550 'N hash tafel is 'n lekker soort van Switserse Army mes wat dit moontlik maak om jou te slaan 213 00:09:28,550 --> 00:09:33,690 pretty much alles wat jy wil binne deur assosieer sleutels met waardes. 214 00:09:33,690 --> 00:09:34,770 Keys met waardes. 215 00:09:34,770 --> 00:09:37,800 >> Nou in hierdie eenvoudige geval, ons sleutels is net nommers. 216 00:09:37,800 --> 00:09:40,380 Ons is die implementering van 'n gemors tafel as 'n skikking. 217 00:09:40,380 --> 00:09:43,500 En so het die sleutels is 0, 1, 2, en so meer. 218 00:09:43,500 --> 00:09:47,200 En so het ons, as mense, het verlede week dat jy weet wat, as ons 219 00:09:47,200 --> 00:09:50,410 gaan om te slaan name, laat ons net arbitrêr, maar redelik redelik, 220 00:09:50,410 --> 00:09:54,680 aanvaar dat Alice, 'n A-naam, sal net geïndekseer word in 0. 221 00:09:54,680 --> 00:09:58,030 En Bob, 'n B naam, sal opgeneem word in 1, en so meer. 222 00:09:58,030 --> 00:10:02,490 So het ons 'n skakel tussen insette, wat stringe, en die hash 223 00:10:02,490 --> 00:10:04,560 plekke, wat is getalle. 224 00:10:04,560 --> 00:10:07,740 >> Sodat proses is algemeen bekend as 'n hash funksie, en jy kan werklik 225 00:10:07,740 --> 00:10:09,130 implementeer dit in die kode. 226 00:10:09,130 --> 00:10:12,080 As ek wou 'n hash funksie te implementeer wat nie presies wat ons 227 00:10:12,080 --> 00:10:17,070 net beskryf van die afgelope tyd, ek kan verklaar 'n funksie wat ', as 228 00:10:17,070 --> 00:10:18,330 insette byvoorbeeld - 229 00:10:18,330 --> 00:10:22,190 en laat ons doen dit op hierdie skerm hier. 230 00:10:22,190 --> 00:10:26,180 As ek wou 'n gemors te implementeer funksie, kan ek sê 231 00:10:26,180 --> 00:10:27,410 iets soos hierdie. 232 00:10:27,410 --> 00:10:29,030 >> Dit gaan 'n int om terug te keer. 233 00:10:29,030 --> 00:10:33,600 Dit gaan om genoem te word hash, en dit is gaan om te aanvaar as 'n argument 'n 234 00:10:33,600 --> 00:10:38,920 string, of kan ons meer behoorlike nou, en sê char *, sal ons noem dit s. 235 00:10:38,920 --> 00:10:43,840 En dan sal al hierdie funksie het om te doen, Uiteindelik is 'n terugkeer int. 236 00:10:43,840 --> 00:10:45,990 Nou, hoe is dit nie wat dalk nie so duidelik nie. 237 00:10:45,990 --> 00:10:49,510 Ek gaan om dit te voer sonder enige vorm van die fout kontrole nou. 238 00:10:49,510 --> 00:10:55,740 Ek gaan net om blindelings sê, terug alles wat op s bracket 0, minus, 239 00:10:55,740 --> 00:10:58,850 kom ons sê, die hoofstad 'n kommapunt. 240 00:10:58,850 --> 00:10:59,960 >> Heeltemal gebreek. 241 00:10:59,960 --> 00:11:02,620 Dit is nie volmaak nie, want een, wat as s is van nul? 242 00:11:02,620 --> 00:11:04,000 Slegte dinge gaan gebeur. 243 00:11:04,000 --> 00:11:07,940 Twee, wat as die eerste letter in hierdie naam is nie 'n hoofletter? 244 00:11:07,940 --> 00:11:09,860 Dit gaan nie om te draai goed uit nie. 245 00:11:09,860 --> 00:11:11,970 Dit mag dalk 'n klein letter wees of nie 'n brief nie. 246 00:11:11,970 --> 00:11:15,520 So totaal ruimte vir verbetering hier, maar dit is die basiese idee. 247 00:11:15,520 --> 00:11:19,010 >> Wat ons beskryf verlede week mondelings as net 'n proses van die kartering van Alice te 248 00:11:19,010 --> 00:11:23,360 0 en Bob tot 1 uitgedruk kan word beslis meer formulaically as 'n C 249 00:11:23,360 --> 00:11:24,320 funksioneer hier. 250 00:11:24,320 --> 00:11:28,630 Genoem weer hash, neem 'n string as insette, en dan nie een of ander manier iets 251 00:11:28,630 --> 00:11:31,020 met die insette 'n uitset te produseer. 252 00:11:31,020 --> 00:11:34,130 Nie in teenstelling met ons swart boks beskrywing dat ons het lank gedoen. 253 00:11:34,130 --> 00:11:36,550 Ek weet nie hoe dit kan wees werk onder die kap. 254 00:11:36,550 --> 00:11:40,120 >> Vir probleem set 6, een van die uitdagings is vir jou om te besluit wat 255 00:11:40,120 --> 00:11:41,920 sal jou hash funksie sal wees? 256 00:11:41,920 --> 00:11:45,760 Wat gaan aan die binnekant van die swart wees boks, en vermoedelik, sal dit 'n 257 00:11:45,760 --> 00:11:50,380 bietjie meer interessant as dit nie, en beslis meer geneig is om fout 258 00:11:50,380 --> 00:11:53,180 nagaan as hierdie spesifieke implementering. 259 00:11:53,180 --> 00:11:54,580 >> Maar probleme kan ontstaan, reg? 260 00:11:54,580 --> 00:11:57,760 As ons 'n data struktuur soos hierdie een, wat is een van die probleme 261 00:11:57,760 --> 00:12:01,600 jy kan hardloop in die verloop van tyd as jy voeg meer en meer name in die 262 00:12:01,600 --> 00:12:02,880 hash tafel? 263 00:12:02,880 --> 00:12:04,630 Jy botsings, reg? 264 00:12:04,630 --> 00:12:07,560 Wat gebeur as jy 'Alice en Aaron, twee mense wie se name gebeur 265 00:12:07,560 --> 00:12:08,190 om te begin met 'n? 266 00:12:08,190 --> 00:12:11,660 Dit lei tot die vraag, waar jy sit die tweede so 'n naam? 267 00:12:11,660 --> 00:12:15,050 >> Wel, kan jy dalk naïef net sit dit waar Bob behoort, maar dan is Bob 268 00:12:15,050 --> 00:12:17,300 soort geskroef as jy probeer om te voeg sy naam langs en 269 00:12:17,300 --> 00:12:18,240 daar is geen plek vir hom. 270 00:12:18,240 --> 00:12:21,400 Sodat jy kan sit Bob waar Charlie is, en jy kan dit baie vinnig dink 271 00:12:21,400 --> 00:12:23,020 wentel in 'n bietjie van 'n gemors. 272 00:12:23,020 --> 00:12:25,600 Iets lineêre in die einde, waar jy net die hele ding om te soek 273 00:12:25,600 --> 00:12:28,190 soek na Alice of Bob of Aaron of Charlie. 274 00:12:28,190 --> 00:12:33,230 >> So in plaas ons voorgestel het, in plaas van net lineêr indringende vir oop ruimtes 275 00:12:33,230 --> 00:12:36,450 en plop die name daar Ons voorgestel dat 'n liefhebber benadering. 276 00:12:36,450 --> 00:12:41,740 'N hash tafel geïmplementeer nog steeds met 'n verskeidenheid van indekse, maar die data tipe 277 00:12:41,740 --> 00:12:44,500 daardie indekse nou was wysers. 278 00:12:44,500 --> 00:12:47,360 Verwysings na wat? 279 00:12:47,360 --> 00:12:48,730 Verwysings na geskakelde lyste. 280 00:12:48,730 --> 00:12:53,330 >> Want onthou dat 'n geskakelde lys is eintlik net 'n verwysing na 'n knoop, en 281 00:12:53,330 --> 00:12:57,110 die knoop het 'n volgende veld, en dat node het 'n volgende veld, en so meer. 282 00:12:57,110 --> 00:13:00,690 So kan jy nou dink van hierdie reeks op die linkerkant van 'n hash tafel 283 00:13:00,690 --> 00:13:01,820 lei tot 'n geskakelde lys. 284 00:13:01,820 --> 00:13:07,000 Die voordeel van dit is as jy 'n botsing tussen Alice en Aaron, 285 00:13:07,000 --> 00:13:09,300 Wat doen jy met die tweede so 'n persoon? 286 00:13:09,300 --> 00:13:14,150 Jy moet net heg hom of haar aan die einde, of selfs die begin 287 00:13:14,150 --> 00:13:15,490 van wat gekoppel lys. 288 00:13:15,490 --> 00:13:17,340 >> En eintlik, laat ons net noodle deur wat vir 'n tweede. 289 00:13:17,340 --> 00:13:18,640 Waar sou maak die meeste sin maak? 290 00:13:18,640 --> 00:13:22,060 As ek voeg Alice en sy beland op die eerste plek, dan het ek probeer om te 291 00:13:22,060 --> 00:13:25,310 voeg Aaron se naam, en daar is natuurlik 'n botsing, moet ek 292 00:13:25,310 --> 00:13:27,400 hom aan die begin van die geskakelde lys? 293 00:13:27,400 --> 00:13:30,944 Dit is op daardie eerste plek, of aan die einde? 294 00:13:30,944 --> 00:13:31,440 >> GEHOOR: [onhoorbaar]. 295 00:13:31,440 --> 00:13:31,990 >> David Malan: OK. 296 00:13:31,990 --> 00:13:32,490 Ek het gehoor die begin. 297 00:13:32,490 --> 00:13:33,903 Waarom aan die begin? 298 00:13:33,903 --> 00:13:34,750 >> GEHOOR: [onhoorbaar]. 299 00:13:34,750 --> 00:13:34,940 >> David Malan: OK. 300 00:13:34,940 --> 00:13:36,520 Dit is alfabeties, so dit is lekker. 301 00:13:36,520 --> 00:13:37,330 Dit is 'n goeie eiendom. 302 00:13:37,330 --> 00:13:39,335 Dit sal red my 'n paar keer potensieel. 303 00:13:39,335 --> 00:13:43,290 Dit laat my nie doen binêre soek, maar ek kan ten minste in staat wees om weg te breek 304 00:13:43,290 --> 00:13:47,340 van 'n lus as ek besef dat, wel, ek is weg verlede was Aaron sal wees in hierdie 305 00:13:47,340 --> 00:13:48,310 gesorteer geskakelde lys. 306 00:13:48,310 --> 00:13:50,360 Ek het nie my tyd te mors op soek na al die pad na die einde. 307 00:13:50,360 --> 00:13:51,530 So dit is redelik. 308 00:13:51,530 --> 00:13:54,710 Hoekom anders wil jy dalk om in te voeg die botsing naam op die 309 00:13:54,710 --> 00:13:56,660 die begin van die lys? 310 00:13:56,660 --> 00:13:57,397 Wat is dit? 311 00:13:57,397 --> 00:13:58,680 >> GEHOOR: [onhoorbaar]. 312 00:13:58,680 --> 00:14:00,820 >> David Malan: Dit kan 'n lang tyd in beslag neem te kry om die einde van die lys. 313 00:14:00,820 --> 00:14:02,490 En in die feit, langer en langer. 314 00:14:02,490 --> 00:14:04,920 Hoe meer name wat jy voeg dat begin met A, die meer wat 315 00:14:04,920 --> 00:14:06,280 ketting gaan kry. 316 00:14:06,280 --> 00:14:07,890 Die meer wat gekoppel lys is die gang te kry. 317 00:14:07,890 --> 00:14:09,420 So jy is regtig net mors jou tyd. 318 00:14:09,420 --> 00:14:14,070 Miskien is jy beter af handhawing konstant te voeg, groot O van 1, 319 00:14:14,070 --> 00:14:18,470 deur altyd die botsing naam op die begin van die geskakelde lys, 320 00:14:18,470 --> 00:14:21,230 en nie bekommerd te wees soveel oor te sorteer. 321 00:14:21,230 --> 00:14:22,600 >> Wat is die beste antwoord? 322 00:14:22,600 --> 00:14:23,320 Dit is onduidelik. 323 00:14:23,320 --> 00:14:26,140 Dit soort van hang af van wat die verspreiding is, wat die patroon is 324 00:14:26,140 --> 00:14:27,850 van die name wat jy inbring. 325 00:14:27,850 --> 00:14:29,430 Dit is nie noodwendig 'n duidelike antwoord. 326 00:14:29,430 --> 00:14:33,100 Maar hier, weer, is 'n ontwerp geleentheid. 327 00:14:33,100 --> 00:14:37,220 >> So het ons dan kyk na hierdie ding, wat is werklik die ander groot geleentheid 328 00:14:37,220 --> 00:14:38,180 vir p-set 6. 329 00:14:38,180 --> 00:14:41,770 En besef, as jy nog nie het nie, Zamyla duik in beide van hierdie, hash 330 00:14:41,770 --> 00:14:43,260 tafels en drieë, in meer detail. 331 00:14:43,260 --> 00:14:45,630 En die video walkthrough is ingesluit in p-set spec. 332 00:14:45,630 --> 00:14:46,590 Dit was 'n Trie - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. En wat was interessant oor hierdie is dat die loop van die tyd 334 00:14:51,670 --> 00:14:59,510 van die soek na 'n naam, soos Maxwell laaste keer was groot O van wat? 335 00:14:59,510 --> 00:15:01,040 Wat is dit? 336 00:15:01,040 --> 00:15:01,920 >> Publiek: Die aantal letters. 337 00:15:01,920 --> 00:15:02,550 >> David Malan: Aantal letters. 338 00:15:02,550 --> 00:15:03,210 Ek het gehoor twee dinge. 339 00:15:03,210 --> 00:15:04,630 Aantal letters en konstante tyd. 340 00:15:04,630 --> 00:15:05,540 So laat ons gaan met die eerste. 341 00:15:05,540 --> 00:15:06,410 Die aantal letters. 342 00:15:06,410 --> 00:15:10,195 Wel, hierdie data struktuur, onthou, is soos 'n boom, 'n familie boom, elke 343 00:15:10,195 --> 00:15:12,860 wie se knope is gemaak van skikkings. 344 00:15:12,860 --> 00:15:16,300 En dié skikkings is verwysings na ander soos knope, of sodanige ander 345 00:15:16,300 --> 00:15:17,670 skikkings in die boom. 346 00:15:17,670 --> 00:15:22,890 >> So as ons wou bepaal dan of Maxwell is in hier, kan ek gaan 347 00:15:22,890 --> 00:15:26,890 na die eerste skikking, by die top van die boom, die sogenaamde wortel, bo- 348 00:15:26,890 --> 00:15:30,521 die tydstip waarop, en dan volg die m wyser, dan is die 'n wyser, dan is x, 349 00:15:30,521 --> 00:15:31,710 w, e, l, l. 350 00:15:31,710 --> 00:15:34,910 En dan wanneer ek sien 'n paar spesiale simbool, aangedui hier as 'n driehoek. 351 00:15:34,910 --> 00:15:38,480 In die kode wat jy sien ons voor dat u geïmplementeer as 'n Bool, net ja sê 352 00:15:38,480 --> 00:15:40,540 of nie, 'n woord stop hier. 353 00:15:40,540 --> 00:15:45,270 >> Wel, as ons gegaan het om M-A-X-W-E-L-L, voel soos sewe, miskien 354 00:15:45,270 --> 00:15:48,910 agt as ons gaan 'n verlede, agt stappe Maxwell te vind. 355 00:15:48,910 --> 00:15:53,050 Of kom ons noem dit K. Maar onthou verlede tyd, ek het aangevoer dat indien daar 356 00:15:53,050 --> 00:15:57,540 realisties 'n maksimum lengte op 'n woord, soos 40-paar-vreemd karakters, 'n 357 00:15:57,540 --> 00:16:00,810 maksimum lengte impliseer 'n konstante waarde. 358 00:16:00,810 --> 00:16:05,770 So regtig, ja, dit is tegnies groot O van 8 of 7, of baie groot O van K. Maar 359 00:16:05,770 --> 00:16:09,420 As daar is 'n beperkte pet op watter K kan wees, dit is 'n konstante. 360 00:16:09,420 --> 00:16:12,080 En so dit is groot O van 1 by die einde van die dag. 361 00:16:12,080 --> 00:16:13,040 >> Nie in die werklike wêreld. 362 00:16:13,040 --> 00:16:15,960 Nie wanneer jy eintlik begin kyk jou klok as jou program se bestuur. 363 00:16:15,960 --> 00:16:20,690 Dit is absoluut gaan 'n bietjie stadiger as werklik konstant 364 00:16:20,690 --> 00:16:21,840 tyd saam met 'n stap. 365 00:16:21,840 --> 00:16:25,540 Dit gaan wees sewe of agt stappe maar nog steeds dit is baie, baie beter 366 00:16:25,540 --> 00:16:30,080 as 'n algoritme soos 'n groot O van n wat hang af van die grootte van wat in die 367 00:16:30,080 --> 00:16:31,220 data struktuur. 368 00:16:31,220 --> 00:16:34,970 >> Let op die onderstebo hier is wat ons kan voeg 'n miljoen meer name in hierdie 369 00:16:34,970 --> 00:16:38,170 data struktuur, maar hoe baie meer stappe gaan dit om ons te neem om uit te vind 370 00:16:38,170 --> 00:16:40,480 Maxwell in so 'n geval? 371 00:16:40,480 --> 00:16:40,780 Geen. 372 00:16:40,780 --> 00:16:41,820 Hy is nie geraak nie. 373 00:16:41,820 --> 00:16:45,480 En tot op datum, ek dink nie ons het gesien 'n voorbeeld van 'n data struktuur of 'n 374 00:16:45,480 --> 00:16:48,560 algoritme wat was heeltemal onaangeraak deur eksterne 375 00:16:48,560 --> 00:16:50,040 gedrag soos dit. 376 00:16:50,040 --> 00:16:51,160 Maar dit kan nie wees amazing. 377 00:16:51,160 --> 00:16:52,900 Dit kan nie die enigste oplossing vir die p-reeks 378 00:16:52,900 --> 00:16:53,570 >> En dit is nie. 379 00:16:53,570 --> 00:16:55,980 Dit is nie noodwendig die data struktuur wat jy moet aangetrokke tot, 380 00:16:55,980 --> 00:16:58,220 want soos hash tabelle, nadeel. 381 00:16:58,220 --> 00:17:00,500 Wat is die prys wat jy betaal hier? 382 00:17:00,500 --> 00:17:00,940 Geheue. 383 00:17:00,940 --> 00:17:02,890 Ek bedoel, dit is 'n gruwelike bedrag van die geheue. 384 00:17:02,890 --> 00:17:05,569 En jy kan nie heeltemal sien dit hier omdat die skrywer van hierdie foto 385 00:17:05,569 --> 00:17:09,420 natuurlik afgekapte al die skikkings, en ons nie sien nie baie van die A's en 386 00:17:09,420 --> 00:17:12,700 B's en C's en Q's en Y se en Z's in hierdie skikkings. 387 00:17:12,700 --> 00:17:13,630 Maar hulle is daar. 388 00:17:13,630 --> 00:17:17,660 >> Elkeen van hierdie nodes is 'n hele reeks van sowat 26 of meer grepe, elk van 389 00:17:17,660 --> 00:17:19,170 wat 'n brief. 390 00:17:19,170 --> 00:17:22,920 27 In ons geval is, sodat ons kan ondersteun apostrofs in die probleem stel. 391 00:17:22,920 --> 00:17:27,030 So hierdie data struktuur is regtig, regtig dig en breed. 392 00:17:27,030 --> 00:17:30,880 En dit alleen kan uiteindelik stadiger dinge af, of ten minste kos jou 'n 393 00:17:30,880 --> 00:17:32,240 baie meer ruimte. 394 00:17:32,240 --> 00:17:34,020 Maar weereens, kan ons trek vergelykings hier. 395 00:17:34,020 --> 00:17:39,190 >> Onthou 'n rukkie terug, het ons baie bereik meer opwindende loop van die tyd in sortering 396 00:17:39,190 --> 00:17:42,880 wanneer ons saamsmelt soort, maar die prys Ons betaal te bereik n teken vir n saamsmelt 397 00:17:42,880 --> 00:17:46,930 soort nodig dat ons spandeer meer watter hulpbron? 398 00:17:46,930 --> 00:17:47,690 Meer ruimte. 399 00:17:47,690 --> 00:17:50,530 Ons moes 'n sekondêre skikking te kopieer mense in, net soos 400 00:17:50,530 --> 00:17:51,620 ons het hier op die verhoog. 401 00:17:51,620 --> 00:17:55,880 So weer, geen duidelike wenners, maar net subjektiewe ontwerp 402 00:17:55,880 --> 00:17:57,710 besluite gemaak moet word. 403 00:17:57,710 --> 00:17:58,060 >> Alle regte. 404 00:17:58,060 --> 00:17:59,130 So hoe oor dit? 405 00:17:59,130 --> 00:18:02,050 Enigiemand wat erken D-Hall? 406 00:18:02,050 --> 00:18:02,440 OK. 407 00:18:02,440 --> 00:18:03,170 So drie van ons doen. 408 00:18:03,170 --> 00:18:03,750 Mather House. 409 00:18:03,750 --> 00:18:05,070 So dit is vir Mather se eetkamer. 410 00:18:05,070 --> 00:18:09,650 Ek wed al die eetsale het stapels bak soos hierdie. 411 00:18:09,650 --> 00:18:11,950 En dit is eintlik verteenwoordiger van iets wat ons het 412 00:18:11,950 --> 00:18:13,050 duidelik gesien word reeds. 413 00:18:13,050 --> 00:18:14,850 Ons het dit letterlik 'n stapel. 414 00:18:14,850 --> 00:18:18,970 En die stapel, in terme van jou rekenaar se geheue, is waar die data gaan 415 00:18:18,970 --> 00:18:20,460 terwyl funksies word genoem. 416 00:18:20,460 --> 00:18:23,410 >> Byvoorbeeld, watter soort van dinge wat gaan op die stapel met betrekking tot die 417 00:18:23,410 --> 00:18:27,420 geheue uitleg ons bespreek in weke verlede? 418 00:18:27,420 --> 00:18:28,736 Wat is dit? 419 00:18:28,736 --> 00:18:29,670 >> GEHOOR: Oproepe na funksies. 420 00:18:29,670 --> 00:18:30,260 >> David Malan: Ek is jammer. 421 00:18:30,260 --> 00:18:31,210 >> GEHOOR: Oproepe na funksies. 422 00:18:31,210 --> 00:18:33,590 >> David Malan: Oproepe na funksies, maar spesifiek, wat binne in elkeen van 423 00:18:33,590 --> 00:18:35,340 diegene rame? 424 00:18:35,340 --> 00:18:37,220 Watter soort dinge? 425 00:18:37,220 --> 00:18:37,460 Ja. 426 00:18:37,460 --> 00:18:38,500 So plaaslike veranderlikes. 427 00:18:38,500 --> 00:18:43,080 Elke keer wat ons nodig het 'n paar plaaslike stoor, soos 'n argument, of int ek, of int 428 00:18:43,080 --> 00:18:45,940 Temp, of wat ook al die plaaslike veranderlike is, het ons al 429 00:18:45,940 --> 00:18:47,210 om dit op die stapel. 430 00:18:47,210 --> 00:18:49,610 En ons noem dit 'n stapel, want van daardie lae idee. 431 00:18:49,610 --> 00:18:52,940 Net soort van die wedstryde met die werklikheid, die konsep daarvan. 432 00:18:52,940 --> 00:18:56,650 >> Maar dit blyk dat 'n stapel kan ook gesien word as 'n data struktuur, 'n 433 00:18:56,650 --> 00:19:00,110 alternatief tot 'n skikking, 'n alternatiewe aan 'n gekoppelde lys. 434 00:19:00,110 --> 00:19:02,770 Iets konseptueel meer interessant wat nog kan wees 435 00:19:02,770 --> 00:19:06,030 uitgevoer met behulp van een van dié dinge, maar dit is 'n ander soort 436 00:19:06,030 --> 00:19:09,140 data struktuur ondersteun, regtig, slegs twee operasies. 437 00:19:09,140 --> 00:19:11,000 Maar jy kan byvoeg liefhebber funksies as dié nie. 438 00:19:11,000 --> 00:19:12,180 Maar dit is die basiese beginsels - 439 00:19:12,180 --> 00:19:13,510 stoot en pop. 440 00:19:13,510 --> 00:19:19,240 >> En die idee met 'n stapel is dat as ek hier het, met of sonder Annenberg 441 00:19:19,240 --> 00:19:22,880 weet, 'n skinkbord van langsaan met die nommer 9 op dit. 442 00:19:22,880 --> 00:19:23,870 Dus net 'n int. 443 00:19:23,870 --> 00:19:26,990 En ek wil om dit te stoot op die data struktuur, wat tans is leeg. 444 00:19:26,990 --> 00:19:28,790 Beskou dit as die onderkant van die stapel. 445 00:19:28,790 --> 00:19:33,150 Ek wil hierdie nommer 9 druk op die stapel, en nou is dit net daar. 446 00:19:33,150 --> 00:19:36,040 >> Maar die interessante ding oor 'n stapel is dat as ek nou wil stoot 447 00:19:36,040 --> 00:19:40,210 'n ander waarde, soos 17, en ek stoot hierdie op die stapel, ek gaan om dit te doen 448 00:19:40,210 --> 00:19:43,290 die enigste ding wat intuïtief, is ek net gaan dit reg te stel waar ons mense 449 00:19:43,290 --> 00:19:45,180 sou geneig wees om dit te sit, bo-op. 450 00:19:45,180 --> 00:19:48,850 Maar wat interessant is nou is, hoe kry ek op 9? 451 00:19:48,850 --> 00:19:50,670 Jy weet, ek doen nie sonder 'n poging. 452 00:19:50,670 --> 00:19:54,070 >> So, wat is interessant oor 'n stapel is dat deur die ontwerp, 453 00:19:54,070 --> 00:19:56,330 dit is 'n LIFO data struktuur. 454 00:19:56,330 --> 00:19:59,680 Dom manier om te beskryf laaste in, eerste uit. 455 00:19:59,680 --> 00:20:03,280 So het die laaste nommer in in hierdie tyd was 17. 456 00:20:03,280 --> 00:20:07,540 So as ek iets wil pop af van die stapel, kan dit net wees 17. 457 00:20:07,540 --> 00:20:11,890 So is daar 'n verpligte orde van bedrywighede hier, waar die laaste item 458 00:20:11,890 --> 00:20:14,260 in het aan die eerste een uit wees. 459 00:20:14,260 --> 00:20:16,440 Vandaar die akroniem, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> So hoekom kan dit nuttig wees? 461 00:20:19,160 --> 00:20:22,690 Is hulle konteks waarin jy wil wil 'n data struktuur soos hierdie? 462 00:20:22,690 --> 00:20:24,810 Wel, seker dit is nuttig binnekant van 'n rekenaar. 463 00:20:24,810 --> 00:20:29,050 So bedryfstelsels duidelik gebruik om hierdie soort data struktuur vir stapels. 464 00:20:29,050 --> 00:20:32,800 Ons sien ook die dieselfde idee wanneer dit kom by die web bladsye. 465 00:20:32,800 --> 00:20:35,890 So hierdie week en volgende week en verder, en as jy begin met die implementering web 466 00:20:35,890 --> 00:20:39,490 bladsye in 'n taal, die sogenaamde HTML, kan jy eintlik gebruik om 'n data struktuur soos 467 00:20:39,490 --> 00:20:42,690 hierdie om te bepaal of die bladsy is korrek geformateer. 468 00:20:42,690 --> 00:20:47,170 Omdat ons sal sien al die web bladsye volg 'n soort van 'n hiërargie, 'n inkeping 469 00:20:47,170 --> 00:20:52,030 wat aan die einde van die dag is, 'n boom struktuur onder die kap. 470 00:20:52,030 --> 00:20:53,620 So meer op wat in net 'n bietjie. 471 00:20:53,620 --> 00:20:56,560 >> Maar vir nou, laat ons voor te stel vir 'n oomblik, hoe kan ons gaan oor 472 00:20:56,560 --> 00:20:58,830 verteenwoordig wat 'n stapel is? 473 00:20:58,830 --> 00:21:03,370 Laat my voor dat ons implementeer 'n stapel met 'n kode soos hierdie. 474 00:21:03,370 --> 00:21:07,990 So 'n stapel gaan hê binnekant van dit twee dinge, 'n skikking, genaamd bak, 475 00:21:07,990 --> 00:21:09,510 net om te wees in ooreenstemming met die demo. 476 00:21:09,510 --> 00:21:12,660 En elk van die items in die skikking gaan 'n tipe int wees. 477 00:21:12,660 --> 00:21:14,740 En kapasiteit is vermoedelik wat? 478 00:21:14,740 --> 00:21:18,796 Want ek het nie geskryf die volledige definisie hier. 479 00:21:18,796 --> 00:21:21,535 >> Dit is waarskynlik die maksimum grootte van die skikking. 480 00:21:21,535 --> 00:21:25,150 En dit is waarskynlik verklaar as 'n skerp definieer aan die bokant van die lêer, sommige 481 00:21:25,150 --> 00:21:28,450 soort van 'n konstante soos geïmpliseer deur die blote kapitalisasie. 482 00:21:28,450 --> 00:21:32,250 So iewers kapasiteit word gedefinieer as die maksimum grootte. 483 00:21:32,250 --> 00:21:35,590 Intussen het die binnekant van die data struktuur bekend as 'n stapel sal daar 484 00:21:35,590 --> 00:21:38,630 'n heelgetal wees net bekend eenvoudig as grootte. 485 00:21:38,630 --> 00:21:43,400 >> So as ek was om dit te stel nou picturaal, laat ons veronderstel dat hierdie 486 00:21:43,400 --> 00:21:48,070 hele black box verteenwoordig my stapel. 487 00:21:48,070 --> 00:21:50,070 Binnekant van dit is twee veranderlikes. 488 00:21:50,070 --> 00:21:54,780 So ek gaan die te trek eerste een as grootte. 489 00:21:54,780 --> 00:21:57,420 En die tweede een wat ek gaan te trek as 'n skikking. 490 00:21:57,420 --> 00:22:01,060 >> Maar net om dinge te hou ordelike, Normaalweg sou ek 'n skikking trek soos 491 00:22:01,060 --> 00:22:04,910 , maar dit is soort van 'n mooi As ons ooreen met die werklikheid, of 492 00:22:04,910 --> 00:22:06,230 ooreenstem met die geestelike model. 493 00:22:06,230 --> 00:22:12,880 So laat my plaas trek die skikking vertikaal, wat net weer, 494 00:22:12,880 --> 00:22:13,840 kunstenaar se vertoning. 495 00:22:13,840 --> 00:22:16,610 Maak nie regtig saak wat dit is onder die enjinkap. 496 00:22:16,610 --> 00:22:20,350 En ons sal sê dat, by verstek, kapasiteit gaan word drie. 497 00:22:20,350 --> 00:22:23,480 So dit sal plek 0, hierdie sal plek 1, kan dit wees 498 00:22:23,480 --> 00:22:25,740 sal plek wees 2. 499 00:22:25,740 --> 00:22:29,330 >> As ek omkoop met 'n stress bal, sou iemand wil om te kom en die loop 500 00:22:29,330 --> 00:22:30,870 klim hier vir 'n oomblik? 501 00:22:30,870 --> 00:22:31,960 OK, sien jou hand eerste. 502 00:22:31,960 --> 00:22:33,950 Kom up. 503 00:22:33,950 --> 00:22:36,500 Alle regte. 504 00:22:36,500 --> 00:22:38,760 So ek glo dit is Steven. 505 00:22:38,760 --> 00:22:40,035 Kom up. 506 00:22:40,035 --> 00:22:40,770 Alle regte. 507 00:22:40,770 --> 00:22:46,760 >> Maar ons dink nou rewind na die aanvanklike toestand van die wêreld waar ek 508 00:22:46,760 --> 00:22:52,180 het nou net verklaar dat 'n stapel, en dit is gaan wees van kapasiteit drie. 509 00:22:52,180 --> 00:22:54,470 Maar grootte is nog nie bepaal. 510 00:22:54,470 --> 00:22:56,100 Bak het nog nie vasgestel nie. 511 00:22:56,100 --> 00:22:57,300 So 'n paar vrae eerste. 512 00:22:57,300 --> 00:23:01,310 En laat my gee u mic so jy kan deel meer aktief in hierdie. 513 00:23:01,310 --> 00:23:05,190 >> So, wat is die binnekant van grootte op hierdie oomblik in die tyd as al wat ek gedoen het, is 514 00:23:05,190 --> 00:23:09,340 verklaar 'n stapel met een lyn van kode? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: Nie veel nie. 516 00:23:10,100 --> 00:23:12,080 >> David Malan: OK, nie veel nie. 517 00:23:12,080 --> 00:23:14,410 Ons weet wat binne in grootte, ons weet wat is binne 518 00:23:14,410 --> 00:23:16,330 van hierdie reeks hier? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Slegs ewekansige kode, reg? 520 00:23:18,630 --> 00:23:20,220 Net - 521 00:23:20,220 --> 00:23:23,230 >> David Malan: Ja, ek gaan noem dit kode, maar ewekansige - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Dinge. 523 00:23:23,820 --> 00:23:28,290 >> David Malan: Dinge soos ewekansige 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: Bits. 525 00:23:28,870 --> 00:23:29,530 >> David Malan: Bits, reg? 526 00:23:29,530 --> 00:23:31,190 So vullis waardes, reg? 527 00:23:31,190 --> 00:23:33,470 So permutasies van 0's en 1's. 528 00:23:33,470 --> 00:23:35,920 Oorblyfsels van die vorige gebruike van die geheue. 529 00:23:35,920 --> 00:23:38,150 En ons weet nie regtig wat die waardes word, sodat ons gewoonlik trek hulle 530 00:23:38,150 --> 00:23:38,930 as vraagtekens. 531 00:23:38,930 --> 00:23:41,990 >> So die eerste ding wat ons is vermoedelik gaan hê om hier te doen nie - 532 00:23:41,990 --> 00:23:46,630 en laat my gee hierdie veld binne van daar 'n naam - bak. 533 00:23:46,630 --> 00:23:49,540 Wat moet ons vermoedelik inisialiseer grootte as ons wil 534 00:23:49,540 --> 00:23:51,040 begin met hierdie stapel? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Tray is sub 3. 536 00:23:53,070 --> 00:23:53,910 >> David Malan: So, OK. 537 00:23:53,910 --> 00:23:56,710 Om duidelik te wees, is kapasiteit verklaar elders as drie. 538 00:23:56,710 --> 00:23:58,570 En dit is wat ek gebruik die skikking toe te ken. 539 00:23:58,570 --> 00:24:03,535 Grootte gaan om te verwys na hoeveel bak is tans op die stapel. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Zero. 541 00:24:03,880 --> 00:24:04,460 >> David Malan: So dit moet wees nul. 542 00:24:04,460 --> 00:24:07,760 So gaan voort, en met 'n vinger, trek 'n nul in grootte. 543 00:24:07,760 --> 00:24:08,440 Alle regte. 544 00:24:08,440 --> 00:24:10,920 So nou, wat binne in hierdie hier, weet ons nie. 545 00:24:10,920 --> 00:24:12,160 Dit is regtig net vullis waardes. 546 00:24:12,160 --> 00:24:14,800 Sodat ons kan trek vraagtekens, maar Kom ons hou die direksie skoon vir nou 547 00:24:14,800 --> 00:24:16,300 want dit maak nie saak nie Wat is daar. 548 00:24:16,300 --> 00:24:19,130 Ons hoef nie die skikking te inisialiseer aan enigiets nie, want as ons weet dat 549 00:24:19,130 --> 00:24:23,100 die grootte van die stapel is nul, goed, ons moet nie kyk na enigiets in 550 00:24:23,100 --> 00:24:25,590 hierdie verskeidenheid in elk geval op hierdie punt in die tyd. 551 00:24:25,590 --> 00:24:29,970 >> So nou dink dat ek stoot die nommer 9 op die stapel. 552 00:24:29,970 --> 00:24:33,750 Hoe moet ons werk om die data struktuur binnekant van hierdie swart boks? 553 00:24:33,750 --> 00:24:35,540 Watter waardes nodig het om te verander? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: Binne - 555 00:24:36,200 --> 00:24:37,400 die grootte? 556 00:24:37,400 --> 00:24:37,650 >> David Malan: OK. 557 00:24:37,650 --> 00:24:38,770 Grootte moet word wat? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Grootte een sal wees. 559 00:24:39,580 --> 00:24:39,870 >> David Malan: OK. 560 00:24:39,870 --> 00:24:41,110 So grootte moet een word. 561 00:24:41,110 --> 00:24:42,540 So jy kan dit doen in 'n paar maniere. 562 00:24:42,540 --> 00:24:46,920 Kom ek gee jou nou jou vinger is 'n uitveër. 563 00:24:46,920 --> 00:24:47,260 Alle regte. 564 00:24:47,260 --> 00:24:49,960 Dan is dit nou jou vinger is 'n kwas. 565 00:24:49,960 --> 00:24:50,330 Alle regte. 566 00:24:50,330 --> 00:24:52,820 Maar nou, wat anders het om te verander, natuurlik, in die data struktuur? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Ons gaan uit bodem tot 9. 568 00:24:57,060 --> 00:24:57,760 >> David Malan: 9. 569 00:24:57,760 --> 00:24:58,420 OK, Good. 570 00:24:58,420 --> 00:25:01,550 So nog steeds maak nie saak wat is op plek een of twee, want hulle is 571 00:25:01,550 --> 00:25:04,520 vullis waardes, maar ons moet nie die moeite soek daar omdat grootte is 572 00:25:04,520 --> 00:25:07,540 om ons te vertel dat slegs die eerste element is eintlik wettig is. 573 00:25:07,540 --> 00:25:10,400 So nou is ek stoot 17 op die lys. 574 00:25:10,400 --> 00:25:11,830 Wat gebeur met hierdie prentjie? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: So grootte gaan om te gaan vir twee. 576 00:25:14,720 --> 00:25:15,300 >> David Malan: OK. 577 00:25:15,300 --> 00:25:16,070 Jy is uitveër - 578 00:25:16,070 --> 00:25:16,810 Oeps. 579 00:25:16,810 --> 00:25:18,026 Jy is 'n uitveër. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Eraser. 581 00:25:18,840 --> 00:25:19,720 >> David Malan: Jy is 'n kwas. 582 00:25:19,720 --> 00:25:20,560 >> STEVEN: Borsel. 583 00:25:20,560 --> 00:25:20,920 >> David Malan: OK. 584 00:25:20,920 --> 00:25:21,600 En wat anders? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: En dan moet ons - 586 00:25:22,600 --> 00:25:22,915 >> David Malan: Ons gestoot 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Ons bly op die top 17, so - 588 00:25:24,760 --> 00:25:25,710 >> David Malan: OK, goed. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN: - laat val dit neer. 590 00:25:27,040 --> 00:25:27,530 >> David Malan: Alle reg. 591 00:25:27,530 --> 00:25:27,940 Dit raak maklik nie. 592 00:25:27,940 --> 00:25:29,300 Ek gaan nie om jou te help om hierdie tyd. 593 00:25:29,300 --> 00:25:30,510 Druk 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: gebraai. 595 00:25:31,720 --> 00:25:34,870 Word 'n uitveër. 596 00:25:34,870 --> 00:25:37,340 Ek is besig om 'n kwas. 597 00:25:37,340 --> 00:25:39,340 En dan is ek om 22. 598 00:25:39,340 --> 00:25:40,100 >> David Malan: 22. 599 00:25:40,100 --> 00:25:40,620 Uitstekend. 600 00:25:40,620 --> 00:25:41,380 So een keer. 601 00:25:41,380 --> 00:25:44,280 Ek gaan nou te druk op die stapel 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 Jy moet regtig my onkant gevang. 605 00:25:52,520 --> 00:25:53,703 >> David Malan: Jy het nie sien kom? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: Ek het nie sien kom. 607 00:25:55,930 --> 00:25:58,756 Kan ons weer aanvanklike kapasiteit? 608 00:25:58,756 --> 00:25:59,790 >> David Malan: Dit is 'n goeie vraag. 609 00:25:59,790 --> 00:26:02,360 So het ons soort van geverf onsself in 'n hoek hier. 610 00:26:02,360 --> 00:26:06,740 Daar is regtig geen goeie uit vir Steven want ons het toegeken die verskeidenheid 611 00:26:06,740 --> 00:26:09,130 staties, om so te spreek, binne van die data struktuur. 612 00:26:09,130 --> 00:26:12,170 En ons het in wese hard gekodeer dit van groot drie. 613 00:26:12,170 --> 00:26:14,170 So kan ons regtig nie meer inzetten dit. 614 00:26:14,170 --> 00:26:20,020 >> Ons kan as ons gaan terug in ons geherdefinieer bak om 'n wyser wat wees 615 00:26:20,020 --> 00:26:22,300 Ons gebruik dan malloc om hand geheue. 616 00:26:22,300 --> 00:26:25,050 Want as ons het die geheue van die hoop via malloc, ons 617 00:26:25,050 --> 00:26:26,430 dan kan bevry. 618 00:26:26,430 --> 00:26:29,630 Maar voordat bevry het, kon ons hergebruik van 'n groter deel van die geheue, 619 00:26:29,630 --> 00:26:31,330 werk die wyser, en so meer. 620 00:26:31,330 --> 00:26:33,500 Maar vir nou, dit is regtig die beste wat ons kan doen. 621 00:26:33,500 --> 00:26:36,360 Stoot en pop is vermoedelik gaan het 'n paar foute aan te dui. 622 00:26:36,360 --> 00:26:40,270 >> So byvoorbeeld, ons implementering van die druk kon terugkeer 'n Bool wat 623 00:26:40,270 --> 00:26:42,390 voorheen teruggekeer waar, waar, waar is. 624 00:26:42,390 --> 00:26:48,390 Maar die vierde keer, dit gaan te hê om terug te keer vals is, byvoorbeeld. 625 00:26:48,390 --> 00:26:48,540 Alle regte. 626 00:26:48,540 --> 00:26:49,540 Baie goed gedoen. 627 00:26:49,540 --> 00:26:50,060 Baie geluk. 628 00:26:50,060 --> 00:26:52,160 Jy verdien jou stress ball vandag. 629 00:26:52,160 --> 00:26:53,110 >> [Applous] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Dankie. 631 00:26:54,382 --> 00:26:55,680 >> David Malan: Dankie. 632 00:26:55,680 --> 00:26:59,740 OK, so dit blyk te wees nie veel van 'n stap vorentoe, reg? 633 00:26:59,740 --> 00:27:01,410 Ons beskryf hierdie data struktuur. 634 00:27:01,410 --> 00:27:02,320 Dit was dwingende, reg? 635 00:27:02,320 --> 00:27:03,200 Bedryfstelsels soos dit. 636 00:27:03,200 --> 00:27:06,360 Blykbaar het die web kan gebruik maak van hierdie, en ander programme het nog steeds. 637 00:27:06,360 --> 00:27:10,870 Maar wat 'n dom beperking dat ons terug na die soort van week twee grense 638 00:27:10,870 --> 00:27:12,880 waar ons vaste grootte skikkings. 639 00:27:12,880 --> 00:27:15,010 >> So daar is wel 'n paar maniere waarop ons kan oplos nie. 640 00:27:15,010 --> 00:27:18,750 Ons kon dinamiese ken die skikking, nie deur harde kodering dit soos ek 641 00:27:18,750 --> 00:27:22,600 wat hier gedoen word nie, maar eerder weer verklaar hierdie, om net duidelik wees, soos 642 00:27:22,600 --> 00:27:23,830 iets soos hierdie. 643 00:27:23,830 --> 00:27:29,040 Int * bak, nie besluit op 'n kapasiteit nie. 644 00:27:29,040 --> 00:27:35,460 Maar toe ek verklaar dat die stapel elders in my kode, kon ek dan bel malloc, 645 00:27:35,460 --> 00:27:38,250 kry die adres van 'n stuk van geheue, en ek kon opdra 646 00:27:38,250 --> 00:27:39,980 daardie adres te bak. 647 00:27:39,980 --> 00:27:43,340 >> En dan, want dit is net 'n stuk van geheue, kan ek voortgaan om te gebruik vierkante 648 00:27:43,340 --> 00:27:45,450 hakienotasie in die gewone manier. 649 00:27:45,450 --> 00:27:49,020 Omdat weer, daar is soort van hierdie funksionele ekwivalent van skikkings en 650 00:27:49,020 --> 00:27:50,820 stukke van die geheue wat kom terug van malloc. 651 00:27:50,820 --> 00:27:53,090 Ons kan hanteer een as die ander gebruik wyser rekenkundige of 652 00:27:53,090 --> 00:27:54,440 vierkante hakienotasie. 653 00:27:54,440 --> 00:27:55,660 So dit is een benadering. 654 00:27:55,660 --> 00:28:00,120 >> Maar hoe anders kan ons hierdie dieselfde data struktuur, potensieel? 655 00:28:00,120 --> 00:28:00,280 Reg? 656 00:28:00,280 --> 00:28:04,530 Ek voel soos ons net hierdie opgelos probleem soos 'n week gelede. 657 00:28:04,530 --> 00:28:08,860 Wat was die oplossing vir die probleem dat Steven gehardloop in? 658 00:28:08,860 --> 00:28:10,370 So gekoppel lyste, reg. 659 00:28:10,370 --> 00:28:13,410 >> As die probleem is dat ons verf onsself in 'n hoek deur die toekenning 660 00:28:13,410 --> 00:28:17,580 vooruit te min geheue dat ons dan het een of ander manier om dit te hanteer, goed, 661 00:28:17,580 --> 00:28:19,880 Waarom nie net verhoed dat reik altesaam? 662 00:28:19,880 --> 00:28:26,170 Waarom nie net verklaar bak te wees om 'n wyser na 'n knoop, ergo 'n gekoppelde lys 663 00:28:26,170 --> 00:28:30,740 en dan net toeken nuwe nodes elke keer Steven nodig om 'n aan te pas 664 00:28:30,740 --> 00:28:32,400 nommer in die data struktuur. 665 00:28:32,400 --> 00:28:34,200 >> So het die prentjie sou hê om te verander. 666 00:28:34,200 --> 00:28:38,220 Dit gaan nie so skoon en as eenvoudig soos net 'n skikking van drie ints. 667 00:28:38,220 --> 00:28:42,970 Nou gaan dit 'n verwysing na 'n wees struct, en dat struct gaan 668 00:28:42,970 --> 00:28:44,830 het 'n int en 'n volgende wyser. 669 00:28:44,830 --> 00:28:47,670 Dit gaan lei via dat wyser om nog so 'n struct te 670 00:28:47,670 --> 00:28:48,600 nog so 'n struct. 671 00:28:48,600 --> 00:28:50,560 So het die prentjie sou eintlik kry 'n bietjie morsig. 672 00:28:50,560 --> 00:28:52,950 En ons wil pyle het vasmaak alles saam. 673 00:28:52,950 --> 00:28:55,280 >> Maar dit is goed, reg, want Ons het gesien hoe om dit te doen. 674 00:28:55,280 --> 00:28:58,180 En as jy gemaklik implementering van iets soos 'n gekoppelde 675 00:28:58,180 --> 00:29:01,450 lys, wat jy hoef te doen, as jy kies 'n hash tafel te implementeer met 676 00:29:01,450 --> 00:29:05,120 afsonderlike chaining vir p-set 6, kan jy gebruik dit as 'n boublok, of 'n 677 00:29:05,120 --> 00:29:08,870 bestanddeel, of in Scratch praat, 'n prosedure, iets wat jy het, het jy 678 00:29:08,870 --> 00:29:12,560 geskep jou eie legkaart stuk wat jy dan kan onthou. 679 00:29:12,560 --> 00:29:17,090 So werkinge, maar moontlike oplossings dat ons het eintlik gesien het nie. 680 00:29:17,090 --> 00:29:20,560 >> So dikwels, jy sien dit elke jaar of twee wanneer Apple uitgawes 681 00:29:20,560 --> 00:29:23,060 iets nuuts, en al die mal mense line-up buite die Apple 682 00:29:23,060 --> 00:29:27,050 slaan hul marginale te koop gradeer op die hardeware. 683 00:29:27,050 --> 00:29:30,420 Ek sê dit, dit is OK, want Ek is een van daardie mense. 684 00:29:30,420 --> 00:29:35,140 So watter soort data struktuur kan verteenwoordig dit die werklikheid? 685 00:29:35,140 --> 00:29:36,980 >> Wel, kom ons noem dit 'n tou, 'n lyn. 686 00:29:36,980 --> 00:29:40,270 So Britse noem dit tipies 'n ry in elk geval, so dit is 'n mooi naam. 687 00:29:40,270 --> 00:29:44,960 En die twee operasies wat 'n tou sal ondersteun ons sal 'n enqueue noem 688 00:29:44,960 --> 00:29:48,900 werking en 'n dequeue operasie, wat soortgelyk is in 689 00:29:48,900 --> 00:29:50,120 gees te stoot en pop. 690 00:29:50,120 --> 00:29:54,060 Dit is net soort van verskillende in konvensie, wat ons noem hierdie. 691 00:29:54,060 --> 00:29:57,680 Maar om iets te enqueue beteken om by te voeg of plaas dit aan die data struktuur. 692 00:29:57,680 --> 00:29:59,570 Om dequeue beteken om dit te verwyder. 693 00:29:59,570 --> 00:30:05,170 Maar dat 'n stapel was 'n LIFO data struktuur, 'n ry is 'n eerste in, 694 00:30:05,170 --> 00:30:06,740 eerste uit data struktuur. 695 00:30:06,740 --> 00:30:10,050 >> As jy die eerste persoon in die lyn, jy sal die eerste persoon te kry 696 00:30:10,050 --> 00:30:12,420 uit van die lyn en koop jou nuwe toestel. 697 00:30:12,420 --> 00:30:18,070 Stel jou voor hoe ontsteld hierdie mense sou wees As Apple plaas gebruik om 'n stapel, vir 698 00:30:18,070 --> 00:30:21,250 byvoorbeeld, te implementeer die pluk up van jou nuwe speelding. 699 00:30:21,250 --> 00:30:24,310 So toue sin maak, beslis, en ons kan dink van alle vorme van 700 00:30:24,310 --> 00:30:27,480 aansoeke, vermoedelik, vir toue, veral wanneer jy wil regverdigheid. 701 00:30:27,480 --> 00:30:30,040 So, hoe kan ons die uitvoering van hierdie as 'n data struktuur? 702 00:30:30,040 --> 00:30:33,680 >> Wel, ek stel voor dat ons dalk nodig het om te doen dit op hierdie manier. 703 00:30:33,680 --> 00:30:35,225 So ek gaan nou 'nommers. 704 00:30:35,225 --> 00:30:38,190 Dus sal ons hou dit eenvoudig en nie noodwendig praat in terme van bak. 705 00:30:38,190 --> 00:30:40,220 Net getalle wat mense van gekry. 706 00:30:40,220 --> 00:30:43,760 Kapasiteit gaan, weer, los die totale aantal mense wat gebruik kan word in 707 00:30:43,760 --> 00:30:46,900 hierdie lyn, as drie of enige ander waarde. 708 00:30:46,900 --> 00:30:50,760 >> Maar ek stel voor dat ek nodig het om tred te hou nie net van die grootte van die 709 00:30:50,760 --> 00:30:52,370 ry, hoe baie dinge in dit. 710 00:30:52,370 --> 00:30:56,310 So grootte is die huidige grootte, kapasiteit is die maksimum grootte. 711 00:30:56,310 --> 00:30:58,540 Net weer, naam deur konvensie. 712 00:30:58,540 --> 00:31:03,680 Hoekom moet ek 'n bykomende int binne van 'n tou om tred te hou van wat is in 713 00:31:03,680 --> 00:31:05,365 voorkant van die lyn? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Hoekom het ek nodig om dit te doen in hierdie geval? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Wel, hoe is hierdie foto gaan verander? 718 00:31:16,190 --> 00:31:19,280 Ek kan waarskynlik onthou van hierdie prentjie. 719 00:31:19,280 --> 00:31:21,480 Laat my gaan voort en vee wat hier is. 720 00:31:21,480 --> 00:31:24,580 Ons gee dit 'n bietjie verskillende name hier. 721 00:31:24,580 --> 00:31:28,930 Kom ons ontslae te raak van die 17, laat ons ontslae te raak van die 9, laat ons ontslae te raak van die 3. 722 00:31:28,930 --> 00:31:30,410 En laat ons voeg 'n ander ding. 723 00:31:30,410 --> 00:31:34,710 Ek stel voor dat ek nodig het om tred te hou van die voorkant van die lys, wat net 724 00:31:34,710 --> 00:31:35,570 gaan na 'n int so goed. 725 00:31:35,570 --> 00:31:36,550 En ons gaan dit eenvoudig te hou. 726 00:31:36,550 --> 00:31:37,740 Geen gekoppel lys vir nou. 727 00:31:37,740 --> 00:31:40,900 >> Ons sal erken dat ons gaan stamp teen hierdie limiet. 728 00:31:40,900 --> 00:31:43,720 Maar wat ek wil sien gebeur hierdie tyd? 729 00:31:43,720 --> 00:31:47,240 So dink ek gaan voort en die eerste persoon kom in lyn, en 730 00:31:47,240 --> 00:31:48,560 dit is die nommer 9. 731 00:31:48,560 --> 00:31:49,680 Ons het stres balle. 732 00:31:49,680 --> 00:31:51,330 Kan ek steel, sê, twee of drie mense? 733 00:31:51,330 --> 00:31:52,690 Een, twee, drie? 734 00:31:52,690 --> 00:31:53,120 Kom up. 735 00:31:53,120 --> 00:31:56,022 Reg van voor, want ons sal hierdie een vinnig. 736 00:31:56,022 --> 00:31:59,415 >> Elkeen van julle is nou gaan wees 'n fan seuntjie in die lyn by Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Jy sal nie ontvang word Apple hardeware aan die einde van hierdie al. 739 00:32:06,210 --> 00:32:06,500 Alle regte. 740 00:32:06,500 --> 00:32:09,430 So jy is die nommer 9 is, is jy nommer 17, nommer 22. 741 00:32:09,430 --> 00:32:12,130 Dit is arbitrêre syfers, soos student ID's of iets anders. 742 00:32:12,130 --> 00:32:14,550 En in 'n oomblik, laat ons begin om te begin om dinge. 743 00:32:14,550 --> 00:32:16,000 En ek sal die raad hier loop hierdie tyd. 744 00:32:16,000 --> 00:32:19,570 >> So in hierdie geval, het ek geïnisialiseer die front te wees - 745 00:32:19,570 --> 00:32:22,380 Ek het eintlik nie regtig omgee wat die Voor is, omdat die grootte is nul. 746 00:32:22,380 --> 00:32:24,480 So dit kan net sowel 'n vraagteken. 747 00:32:24,480 --> 00:32:26,170 Dit is al die vraagtekens. 748 00:32:26,170 --> 00:32:29,880 So nou gaan ons begin om werklik te sien dat sommige mense aantree by die winkel. 749 00:32:29,880 --> 00:32:33,320 >> So as nommer 9, jy is die eerste een daar op 05:00, gaan voort en line-up, 750 00:32:33,320 --> 00:32:34,210 of die nag voor. 751 00:32:34,210 --> 00:32:34,580 OK. 752 00:32:34,580 --> 00:32:35,940 So nou 9 is hier. 753 00:32:35,940 --> 00:32:37,940 So 9 is in die voorkant van die lys. 754 00:32:37,940 --> 00:32:41,440 So ek gaan om voort te gaan en werk die grootte van die huidige data 755 00:32:41,440 --> 00:32:44,740 struktuur nie 0 wees nie, maar om te wees 1. 756 00:32:44,740 --> 00:32:47,630 Ek gaan 9 te sit op die voorkant van die lys. 757 00:32:47,630 --> 00:32:51,020 Laat my gaan voort en skakel die skerm sodat ons kan sien verby ons hier. 758 00:32:51,020 --> 00:32:53,220 >> En nou wat ek wil te stel voor? 759 00:32:53,220 --> 00:32:56,240 Ek gaan om tred te hou dat die voorkant van die tou nou 760 00:32:56,240 --> 00:32:58,570 is by die plek 0. 761 00:32:58,570 --> 00:33:00,510 Want wat volgende gaan gebeur nie? 762 00:33:00,510 --> 00:33:03,000 Wel, dink ek nou enqueue 17 as well. 763 00:33:03,000 --> 00:33:04,510 So hop in lyn is daar. 764 00:33:04,510 --> 00:33:07,060 En weer, die soort van deur tot die winkel gaan om hier te wees. 765 00:33:07,060 --> 00:33:08,700 So nou het ek bygevoeg 17. 766 00:33:08,700 --> 00:33:10,810 En selfs al is hierdie ouens is die sluit die skerm, dit is OK, 767 00:33:10,810 --> 00:33:12,300 want ons kan dit sien hier. 768 00:33:12,300 --> 00:33:12,910 Jammer. 769 00:33:12,910 --> 00:33:13,810 >> Publiek: Ons kan beweeg - 770 00:33:13,810 --> 00:33:14,660 >> David Malan: Nee, dis OK. 771 00:33:14,660 --> 00:33:16,000 Dit is 'n groot daar. 772 00:33:16,000 --> 00:33:18,580 So 17 is nou binnekant van die tou. 773 00:33:18,580 --> 00:33:21,332 Ek nodig het wat om te werk gebied nou al is? 774 00:33:21,332 --> 00:33:23,210 OK, beslis grootte. 775 00:33:23,210 --> 00:33:26,430 En hoe oor die front? 776 00:33:26,430 --> 00:33:27,040 OK, no. 777 00:33:27,040 --> 00:33:30,200 Front moet nie verander nie, omdat In teenstelling met 'n stapel, ons 778 00:33:30,200 --> 00:33:31,370 wil regverdigheid in stand te hou. 779 00:33:31,370 --> 00:33:35,150 So as 9 gekom het in die eerste, ons wil 9 te wees van die eerste uit die lyn 780 00:33:35,150 --> 00:33:36,420 en in die winkel. 781 00:33:36,420 --> 00:33:37,220 >> In werklikheid, laat ons sien dat. 782 00:33:37,220 --> 00:33:42,235 Voordat ons plaas 22, laat gaan voort en dequeue 9. 783 00:33:42,235 --> 00:33:42,970 Wat is jou naam nou weer? 784 00:33:42,970 --> 00:33:43,680 >> Gehoor deur Jake. 785 00:33:43,680 --> 00:33:45,440 >> David Malan: Jake gaan word nou dequeued. 786 00:33:45,440 --> 00:33:48,050 So jy om te loop in die winkel. 787 00:33:48,050 --> 00:33:49,880 En voor te gee dat die winkel is daar. 788 00:33:49,880 --> 00:33:51,970 So nou wat nodig is - hierdie-dit-dit! 789 00:33:51,970 --> 00:33:53,400 Wat moet nou gebeur? 790 00:33:53,400 --> 00:33:54,490 Ontwerp besluit. 791 00:33:54,490 --> 00:33:56,825 Dus nie 'n slegte instink, maar - Wat is jou naam nou weer? 792 00:33:56,825 --> 00:33:57,090 >> GEHOOR: David. 793 00:33:57,090 --> 00:33:57,500 >> David Malan: David. 794 00:33:57,500 --> 00:33:58,810 So wat het Dawid doen? 795 00:33:58,810 --> 00:34:02,590 Hy het probeer om uit te sorteer los die data struktuur en beweeg van sy plek 796 00:34:02,590 --> 00:34:04,100 in Jake se voormalige plek. 797 00:34:04,100 --> 00:34:06,740 En dit is goed as ons bereid is om wat om te aanvaar as 'n 798 00:34:06,740 --> 00:34:08,199 implementering detail. 799 00:34:08,199 --> 00:34:11,100 Maar eers, laat se werk om die data struktuur voordat ons dit doen. 800 00:34:11,100 --> 00:34:14,139 Omdat ek nie hou van die idee van alle die mense verskuiwing in hierdie lyn. 801 00:34:14,139 --> 00:34:17,360 >> Dit is nie 'n groot deal as Dawid doen dit met 'n stap, maar weer, dink terug aan 802 00:34:17,360 --> 00:34:20,360 wanneer ons het agt vrywilligers op die stadium en ons het gedoen soos die inplanting 803 00:34:20,360 --> 00:34:22,600 soort, waar ons gehad het om te begin beweeg almal rondom. 804 00:34:22,600 --> 00:34:23,790 Dit het duur is, reg? 805 00:34:23,790 --> 00:34:28,330 Dit maak my ineenkrimp oor die groot O van N, groot O van n vierkant weer. 806 00:34:28,330 --> 00:34:30,650 Dit is nie gevoel soos 'n ideale uitkoms. 807 00:34:30,650 --> 00:34:32,080 >> So laat ons net werk hierdie. 808 00:34:32,080 --> 00:34:35,120 So het die grootte van die tou is nie meer 2. 809 00:34:35,120 --> 00:34:37,090 Dit is nou net 1. 810 00:34:37,090 --> 00:34:40,360 Maar ek kan nou by iets Ek het nie voor te werk, die 811 00:34:40,360 --> 00:34:41,130 voorkant van die lys. 812 00:34:41,130 --> 00:34:45,420 Ek kon net sê, is dat die plek 1? 813 00:34:45,420 --> 00:34:49,770 So nou het ons vullis waarde hier, vullis waarde hier, en Dawid in die 814 00:34:49,770 --> 00:34:51,469 middel van hierdie gemors. 815 00:34:51,469 --> 00:34:54,980 Maar die data struktuur is nog ongeskonde. 816 00:34:54,980 --> 00:34:58,540 >> En in waarheid te sê, ek het nie eens nodig het om te verander Jake se voormalige nommer 817 00:34:58,540 --> 00:35:00,460 9, omdat wat omgee. 818 00:35:00,460 --> 00:35:04,470 Ek het nie genoeg inligting nou in die grootte wat ek weet daar is een persoon in 819 00:35:04,470 --> 00:35:05,030 hierdie tou. 820 00:35:05,030 --> 00:35:08,340 En ek weet dat daardie persoon is by die plek 1 nie 0. 821 00:35:08,340 --> 00:35:09,760 Ek is nie die tel. 822 00:35:09,760 --> 00:35:11,300 So 1 as well. 823 00:35:11,300 --> 00:35:13,410 So het die data struktuur is nog OK. 824 00:35:13,410 --> 00:35:14,330 >> Wel, wat gebeur volgende? 825 00:35:14,330 --> 00:35:15,010 Let's enqueue - 826 00:35:15,010 --> 00:35:15,370 Wat is jou naam? 827 00:35:15,370 --> 00:35:16,160 >> GEHOOR: Callen. 828 00:35:16,160 --> 00:35:16,580 >> David Malan: Callen. 829 00:35:16,580 --> 00:35:20,770 Kom ons enqueue n Callen, en 22 is nou in die ry. 830 00:35:20,770 --> 00:35:22,300 So nou wat het hier te verander nie? 831 00:35:22,300 --> 00:35:24,380 Front is nie van plan om te verander, natuurlik. 832 00:35:24,380 --> 00:35:27,160 Grootte gaan verander om te wees 2. 833 00:35:27,160 --> 00:35:31,590 En 22 eindig hier, 9 is nog steeds teenwoordig is, maar dit is eintlik 'n 834 00:35:31,590 --> 00:35:32,600 vullis waarde nou. 835 00:35:32,600 --> 00:35:35,910 Dit is net 'n oorblyfsel van Jake verlede. 836 00:35:35,910 --> 00:35:39,200 >> So nou wat gebeur as Ek dequeue Dawid? 837 00:35:39,200 --> 00:35:41,560 Een laaste operasie, dequeue David. 838 00:35:41,560 --> 00:35:46,070 Ons kon skuif, maar ek stel voor laat se doen so min werk as moontlik. 839 00:35:46,070 --> 00:35:50,280 Nou is my data struktuur gaan terug in grootte 2-1. 840 00:35:50,280 --> 00:35:53,730 Maar die voorkant van die tou nou raak 2. 841 00:35:53,730 --> 00:35:56,640 Ek het nie nodig om hierdie getalle te verander net nog nie, want hulle is 842 00:35:56,640 --> 00:35:58,230 net vullis waardes. 843 00:35:58,230 --> 00:35:59,720 >> Maar nou wat gebeur? 844 00:35:59,720 --> 00:36:03,280 Dink ek enqueue myself, 26? 845 00:36:03,280 --> 00:36:05,890 Ek voel soos ek hoort hier. 846 00:36:05,890 --> 00:36:06,890 So word ek waglys. 847 00:36:06,890 --> 00:36:08,760 So ek soort van hier hoort nie. 848 00:36:08,760 --> 00:36:11,300 En selfs al is jy nie heeltemal waardeer dit visueel op die verhoog, 849 00:36:11,300 --> 00:36:15,075 want ons het baie van die kamer, ek moet nie hier staan, hoekom? 850 00:36:15,075 --> 00:36:16,290 >> Publiek: Jy is buite perke. 851 00:36:16,290 --> 00:36:16,370 >> David Malan: Right. 852 00:36:16,370 --> 00:36:16,940 Ek is buite perke. 853 00:36:16,940 --> 00:36:19,330 Ek het geïndekseer buite die grense van die skikking. 854 00:36:19,330 --> 00:36:23,420 Ek het regtig moet in een van die drie moontlike plekke. 855 00:36:23,420 --> 00:36:25,150 Nou, is waar die meeste natuurlike om te gaan? 856 00:36:25,150 --> 00:36:27,760 Ek stel voor ons aged 'n week 'n truuk. 857 00:36:27,760 --> 00:36:30,150 Die mod operateur, persentasie. 858 00:36:30,150 --> 00:36:36,850 Want ek is tegnies staan ​​by plek 3, maar ek doen 3 mod kapasiteit, 859 00:36:36,850 --> 00:36:40,250 so 3, 'n persent teken, 3 - 860 00:36:40,250 --> 00:36:40,970 kapasiteit is 3. 861 00:36:40,970 --> 00:36:41,720 Wat is dit? 862 00:36:41,720 --> 00:36:43,700 Wat is die res as jy deel 3 deur 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Sodat plaas my is Jake was, Dit is eintlik 'n goeie. 865 00:36:48,140 --> 00:36:50,370 So nou is die implementering van hierdie ding gaan 866 00:36:50,370 --> 00:36:51,250 wees om 'n bietjie van 'n hoofpyn. 867 00:36:51,250 --> 00:36:53,740 Dit is regtig net een lyn van hoofpyn, van die kode. 868 00:36:53,740 --> 00:36:56,580 Maar ten minste nou is daar vullis waarde hier, maar daar is twee 869 00:36:56,580 --> 00:36:57,910 wettige ints hier. 870 00:36:57,910 --> 00:37:04,160 En ek eis dat ons nou gedoen presies wat ons nodig het om so lank as wat dit doen 871 00:37:04,160 --> 00:37:08,600 ons verander wat Jake se waarde was om te wees 26. 872 00:37:08,600 --> 00:37:12,110 >> Ons het nou genoeg inligting steeds die integriteit te handhaaf 873 00:37:12,110 --> 00:37:13,060 van hierdie data struktuur. 874 00:37:13,060 --> 00:37:17,160 Ons is nog steeds soort van geluk wanneer ons wil vier of meer totale te voeg 875 00:37:17,160 --> 00:37:20,740 elemente, maar ek kan ten minste maak mooi doeltreffende gebruik van hierdie konstante 876 00:37:20,740 --> 00:37:21,740 tyd, in werklikheid. 877 00:37:21,740 --> 00:37:27,150 Ek hoef nie te bekommerd wees oor die verskuiwing almal, soos Dawid se neiging was. 878 00:37:27,150 --> 00:37:30,816 >> Enige vrae oor stapels, of die tou? 879 00:37:30,816 --> 00:37:32,184 >> GEHOOR: Is die rede waarom wat jy nodig grootte, sodat jy weet 880 00:37:32,184 --> 00:37:34,010 waar 'n persoon te hê? 881 00:37:34,010 --> 00:37:34,770 >> David Malan: Presies. 882 00:37:34,770 --> 00:37:38,230 Ek moet die grootte van die skikking te weet omdat ek nodig het om te weet presies hoe 883 00:37:38,230 --> 00:37:41,940 baie van hierdie waardes is wettig, en sodat ek kan vind waar om te sit 884 00:37:41,940 --> 00:37:42,800 die volgende persoon. 885 00:37:42,800 --> 00:37:43,300 Presies. 886 00:37:43,300 --> 00:37:44,580 Die grootte is - 887 00:37:44,580 --> 00:37:46,360 Eintlik het ons nie werk hierdie nie. 888 00:37:46,360 --> 00:37:48,380 Ek het ook myself op 26. 889 00:37:48,380 --> 00:37:51,760 Die grootte is nou, nie 1 nie, maar 2. 890 00:37:51,760 --> 00:37:57,780 So nou is dit help my werklik vind die hoof van die lys, wat nie 0 is nie, nie 891 00:37:57,780 --> 00:37:59,250 1, maar is 2. 892 00:37:59,250 --> 00:38:01,665 Die voorkant van die lys is inderdaad nommer 22. 893 00:38:01,665 --> 00:38:05,120 Want hy het in die eerste, so moet hy toegelaat word om in die winkel voor my, 894 00:38:05,120 --> 00:38:08,780 selfs al is visueel Ek staan nader aan die winkel. 895 00:38:08,780 --> 00:38:09,220 >> Alle reg? 896 00:38:09,220 --> 00:38:12,410 'N rondte van applous vir hierdie ouens en ons sal jou laat hulle daar uit. 897 00:38:12,410 --> 00:38:17,090 >> [Applous] 898 00:38:17,090 --> 00:38:18,150 >> David Malan: Ek kon laat jy hou die skinkbord. 899 00:38:18,150 --> 00:38:20,760 Ons kon sien wat gebeur as jy wil, maar miskien nie. 900 00:38:20,760 --> 00:38:21,590 Alle regte. 901 00:38:21,590 --> 00:38:25,380 So, wat nou laat dit ons? 902 00:38:25,380 --> 00:38:28,900 Wel, laat ek stel voor dat daar 'n n paar ander data strukture wat ons kon 903 00:38:28,900 --> 00:38:33,810 begin toe te voeg tot ons gereedskapskis wat eintlik baie, baie relevant wees 904 00:38:33,810 --> 00:38:35,270 ons duik in web dinge. 905 00:38:35,270 --> 00:38:38,150 Wat weer, het 'n soort van die verband aan bome in die vorm van 906 00:38:38,150 --> 00:38:40,550 iets genoem DOM, dokument voorwerp model. 907 00:38:40,550 --> 00:38:42,370 Maar ons sal sien meer van wat kort voor lank. 908 00:38:42,370 --> 00:38:46,260 >> Laat my definitionally stel voor dat ons noem boom nou wat jy dalk ken as 909 00:38:46,260 --> 00:38:48,820 meer van 'n stamboom, waar jy het 'n paar voorloper op die 910 00:38:48,820 --> 00:38:49,790 wortels van die boom. 911 00:38:49,790 --> 00:38:54,480 'N patriargale of 'n matriarg by die top van die boom. 912 00:38:54,480 --> 00:38:56,700 Sonder hul gade, in hierdie geval. 913 00:38:56,700 --> 00:39:00,940 Maar nou het ons wat ons bel kinders, wat nodes wat hang is 914 00:39:00,940 --> 00:39:05,480 af die linker kind of die regte kind, pyle soos aangedui hier. 915 00:39:05,480 --> 00:39:10,490 >> Met ander woorde, in 'n boom data struktuur in die rekenaar, 'n boom het 'n nul 916 00:39:10,490 --> 00:39:11,480 of meer nodes. 917 00:39:11,480 --> 00:39:13,500 As dit het ten minste een knoop, Dit is genoem die wortel. 918 00:39:13,500 --> 00:39:15,700 Dit is die dinge wat visueel ons trek aan die bokant. 919 00:39:15,700 --> 00:39:20,280 En dat knoop, soos enige ander node, kan nul, een, of twee, of drie, 920 00:39:20,280 --> 00:39:23,600 of hoeveel kinders die data struktuur ondersteun. 921 00:39:23,600 --> 00:39:29,150 In hierdie geval, die wortel, die stoor van die waarde een, het twee kinders, 2 en 3, 922 00:39:29,150 --> 00:39:33,020 sodat ons in die algemeen noem 2 links kind en 3 die regte kind. 923 00:39:33,020 --> 00:39:36,940 >> En dan wanneer ons tot 5, 6, en 7, 6 genoem kan word die middelste kind. 924 00:39:36,940 --> 00:39:38,940 As jy het vier kinders, dit raak verwarrend. 925 00:39:38,940 --> 00:39:42,260 So ons ophou om daardie soort van kortpad mondelings. 926 00:39:42,260 --> 00:39:44,580 Maar dit is eintlik net 'n stamboom. 927 00:39:44,580 --> 00:39:48,880 En die blare hier is die nodes wat self het nie kinders nie. 928 00:39:48,880 --> 00:39:52,540 Hulle hang af van die onderkant van die boom. 929 00:39:52,540 --> 00:39:56,940 >> So, hoe kan ons die uitvoering van 'n boom wat het net twee kinders maksimaal? 930 00:39:56,940 --> 00:39:58,410 Ons noem dit 'n binêre boom. 931 00:39:58,410 --> 00:40:00,960 Bi weer beteken dat twee, in hierdie geval, soos met die program nie. 932 00:40:00,960 --> 00:40:04,830 En so kan dit nul, een, of twee kinders maksimaal. 933 00:40:04,830 --> 00:40:08,650 >> Ek sal voorstel dat ons die uitvoering van die knoop vir daardie struktuur met 'n int n, 934 00:40:08,650 --> 00:40:11,910 en dan twee wysers, een wat geroep verlaat het, een wat geroep is reg. 935 00:40:11,910 --> 00:40:14,830 Maar dit is net mooi arbitrêre konvensies. 936 00:40:14,830 --> 00:40:18,170 En wat is nou lekker, veral as jy soort gesukkel konseptueel met 937 00:40:18,170 --> 00:40:21,300 rekursie, of het gedink dat dit was nie regtig 'n oplossing vir enigiets, 938 00:40:21,300 --> 00:40:23,120 veral as jy kon loop uit van die geheue. 939 00:40:23,120 --> 00:40:26,600 Nou dat ons praat oor data strukture en algoritmes wat toelaat 940 00:40:26,600 --> 00:40:31,030 om ons te loop en te manipuleer hulle blyk dat rekursie terug kom in 941 00:40:31,030 --> 00:40:34,240 'n baie meer dwingende Indien nie mooi manier. 942 00:40:34,240 --> 00:40:38,670 >> So het ek stel voor die implementering van 'n soek funksie. 943 00:40:38,670 --> 00:40:39,870 Gegewe twee insette - 944 00:40:39,870 --> 00:40:41,570 so dink van hierdie as 'n swart boks. 945 00:40:41,570 --> 00:40:46,560 Gegewe twee insette, n, 'n int, en 'n wyser aan 'n boom, 'n verwysing na 'n 946 00:40:46,560 --> 00:40:50,020 knoop, of eintlik die wortel van 'n boom, ek eis dat hierdie funksie kan terugkeer 947 00:40:50,020 --> 00:40:53,530 waar of vals is, wat waarde n is die binnekant van die boom. 948 00:40:53,530 --> 00:40:55,210 >> Wat is die binnekant van hierdie swart boks? 949 00:40:55,210 --> 00:40:57,440 Wel, vier takke. 950 00:40:57,440 --> 00:40:58,385 Die eerste net kontroleer. 951 00:40:58,385 --> 00:41:00,490 As boom is nul, net terug vals. 952 00:41:00,490 --> 00:41:04,580 As daar is geen knoop, is daar geen n, daar is geen nommer, net terug vals. 953 00:41:04,580 --> 00:41:12,330 As al is, n, die waarde wat jy op soek is na vir, is minder as boom pyl n, en 954 00:41:12,330 --> 00:41:15,180 net om duidelik te wees, wat beteken dit wanneer Ek skryf boom en dan die pyl 955 00:41:15,180 --> 00:41:18,150 notasie, n? 956 00:41:18,150 --> 00:41:18,690 Presies. 957 00:41:18,690 --> 00:41:21,970 Dit beteken dat dereference wyser genoem boom. 958 00:41:21,970 --> 00:41:26,750 Gaan daar, en dan kry binnekant van daardie knoop en kry sy gebied genoem n. 959 00:41:26,750 --> 00:41:30,810 En vergelyk dan die werklike n wat was geslaag het in Soek daarteen. 960 00:41:30,810 --> 00:41:35,390 >> So as n minder is as die n waarde in die boom knoop self, goed, 961 00:41:35,390 --> 00:41:36,720 wat beteken dit? 962 00:41:36,720 --> 00:41:40,690 Dit beteken niks met die eerste oogopslag. 963 00:41:40,690 --> 00:41:40,900 Reg? 964 00:41:40,900 --> 00:41:45,560 Net soos wanneer jy 'n verskeidenheid van waardes, kan jy wil binêre om aansoek te doen 965 00:41:45,560 --> 00:41:48,290 soek as 'n vorm van skeiding en oorwin. 966 00:41:48,290 --> 00:41:51,790 Maar wat aanname het ons nodig het om te maak vir binêre soektog te op alle werk 967 00:41:51,790 --> 00:41:54,510 in die telefoon boek en vroeër voorbeelde? 968 00:41:54,510 --> 00:41:55,530 >> Hoe om te sorteer word. 969 00:41:55,530 --> 00:41:59,490 So laat verfyn die definisie van die boom hier te wees nie net 'n boom, wat kan 970 00:41:59,490 --> 00:42:00,880 enige aantal kinders. 971 00:42:00,880 --> 00:42:04,700 Nie net 'n binêre boom, wat kan het 0, 1 of 2 maksimaal. 972 00:42:04,700 --> 00:42:09,700 Maar as 'n binêre soek boom, of BST, Dit is net 'n fancy manier om te sê 'n 973 00:42:09,700 --> 00:42:15,430 binêre boom sodanig dat elke node se links kind, indien teenwoordig, is 974 00:42:15,430 --> 00:42:16,830 minder as die knoop. 975 00:42:16,830 --> 00:42:20,170 En elke node se reg om kind, indien teenwoordig, is groter 976 00:42:20,170 --> 00:42:21,740 as die knoop self. 977 00:42:21,740 --> 00:42:25,200 >> So met ander woorde, as jy was om te trek die boom uit, al die getalle 978 00:42:25,200 --> 00:42:30,620 versigtig gebalanseer soos hierdie so dat indien jy het 55 as die wortel, kan 33 gaan 979 00:42:30,620 --> 00:42:33,090 aan die linkerkant, want dit is minder as 55. 980 00:42:33,090 --> 00:42:36,430 77 kan gaan na die reg, want dit is groter as 55. 981 00:42:36,430 --> 00:42:40,750 Maar nou sien, dieselfde definisie, dit is 'n rekursiewe definisie mondelings, 982 00:42:40,750 --> 00:42:42,600 het om aansoek te doen vir 33. 983 00:42:42,600 --> 00:42:47,610 33 se linker kind moet minder wees as dit, en 33 se reg om kind, 44, moet 984 00:42:47,610 --> 00:42:48,580 groter as dit. 985 00:42:48,580 --> 00:42:51,670 >> So dit is 'n binêre soek boom, en Ek stel voor, met behulp van 'n bietjie 986 00:42:51,670 --> 00:42:53,910 rekursie, ons kan nou n. 987 00:42:53,910 --> 00:42:59,160 So as n minder is as die waarde n dis knoop, ek gaan om te gaan 988 00:42:59,160 --> 00:43:04,090 voor en Punt, om so te praat, en net terug te keer wat die antwoord is 989 00:43:04,090 --> 00:43:08,470 soek na n op die boom se linker kind. 990 00:43:08,470 --> 00:43:11,370 Let weer op, hierdie funksie net verwag 'n knoop ster, 'n 991 00:43:11,370 --> 00:43:12,780 wyser na 'n knoop. 992 00:43:12,780 --> 00:43:17,360 So ja, ek kan net doen boom pyl links, wat sal lei 993 00:43:17,360 --> 00:43:18,400 my na 'n ander knoop. 994 00:43:18,400 --> 00:43:19,480 Maar wat is dit nodig? 995 00:43:19,480 --> 00:43:22,820 >> Wel, volgens hierdie verklaring, links is net 'n muis, sodat net 996 00:43:22,820 --> 00:43:27,090 beteken ek is verby die soek funksie 'n ander wyser, naamlik 997 00:43:27,090 --> 00:43:30,750 die een wat verteenwoordig my linker kind se boom. 998 00:43:30,750 --> 00:43:36,040 So in hierdie geval, die wyser na 33, indien dit is ons voorbeeld insette Intussen, as 999 00:43:36,040 --> 00:43:40,740 n groter is as die waarde n by die knoop in die boom, dan is ek 1000 00:43:40,740 --> 00:43:43,370 gaan voort en punt gaan in die ander rigting en net sê, ek doen nie 1001 00:43:43,370 --> 00:43:47,280 weet as hierdie waarde n is in die boom, maar ek weet nie of dit is, is dit in my 1002 00:43:47,280 --> 00:43:49,090 regte tak, om so te praat. 1003 00:43:49,090 --> 00:43:53,120 So laat my rekursief noem soek, verby 'n weer, maar die verbygaan in 'n 1004 00:43:53,120 --> 00:43:54,580 wyser na my reg kind. 1005 00:43:54,580 --> 00:44:00,020 >> Met ander woorde, as ek tans op 55 en ek is op soek na 99, ek weet dat 99 1006 00:44:00,020 --> 00:44:04,270 is groter as 55, so net soos ek skeur die telefoon boek weke gelede en ons 1007 00:44:04,270 --> 00:44:07,140 het reg, net soos ons is gaan hier gaan. 1008 00:44:07,140 --> 00:44:11,960 En ek weet nie of dit is op my reg kind, en dit is nie, 77 daar is nie, maar 1009 00:44:11,960 --> 00:44:13,210 Ek weet dit is in daardie rigting. 1010 00:44:13,210 --> 00:44:18,770 So ek noem soektog op my regte kind, 77, en laat soek figuur uit 1011 00:44:18,770 --> 00:44:24,950 is daar as 99 in hierdie arbitrêre voorbeeld is eintlik daar. 1012 00:44:24,950 --> 00:44:26,900 >> Anders, wat is die finale geval? 1013 00:44:26,900 --> 00:44:28,620 As boom is van nul is een geval. 1014 00:44:28,620 --> 00:44:31,890 As n minder is as die huidige knoop se waarde is 'n ander saak. 1015 00:44:31,890 --> 00:44:35,120 As n groter is as die huidige node se waarde is 'n derde geval nie. 1016 00:44:35,120 --> 00:44:38,250 Wat is die vierde en laaste geval? 1017 00:44:38,250 --> 00:44:39,480 Ek dink ons ​​is uit van die gevalle, reg? 1018 00:44:39,480 --> 00:44:44,690 Dit moet wees dat n is in die knoop dat ek op. 1019 00:44:44,690 --> 00:44:49,640 >> So as ek is op soek na 55 op hierdie punt in die storie, wat tak van die 1020 00:44:49,640 --> 00:44:51,780 boom sou terugkeer waar. 1021 00:44:51,780 --> 00:44:55,380 So, wat is interessant hier is dat ons eintlik, in teenstelling weke verlede, het ons soort 1022 00:44:55,380 --> 00:44:56,740 van twee basis gevalle. 1023 00:44:56,740 --> 00:44:58,300 En hulle het nie aan wees al aan die bokant. 1024 00:44:58,300 --> 00:45:01,390 Die top is 'n basis geval, want as die boom is nietig, daar is niks om te doen. 1025 00:45:01,390 --> 00:45:03,410 Gaan terug 'n harde gekodeerde waarde van vals. 1026 00:45:03,410 --> 00:45:07,400 >> Die onderste tak is 'n soort van die verstek, waardeur as ons nagegaan word vir 1027 00:45:07,400 --> 00:45:11,550 nul, het ons gekyk as wat dit moet wees gelaat, maar dit moet nie, het ons 1028 00:45:11,550 --> 00:45:14,640 nagegaan word of dit moet reg wees, maar dit moet wees nie, dit duidelik te wees 1029 00:45:14,640 --> 00:45:15,870 reg waar ons is. 1030 00:45:15,870 --> 00:45:16,780 Dit is 'n basis geval. 1031 00:45:16,780 --> 00:45:19,920 So is daar twee gevalle rekursiewe landgebonde daar in die middel. 1032 00:45:19,920 --> 00:45:21,630 Maar ek kon geskryf het dit in enige volgorde. 1033 00:45:21,630 --> 00:45:24,520 Ek het net gedink dit soort van gevoel natuurlike om eers vir 'n moontlike fout 1034 00:45:24,520 --> 00:45:28,340 dan gaan verlaat, dan regs gaan, dan aanvaar dat jy by die knoop 1035 00:45:28,340 --> 00:45:30,630 jy is eintlik op soek na. 1036 00:45:30,630 --> 00:45:36,240 >> So hoekom kan dit nuttig wees? 1037 00:45:36,240 --> 00:45:37,910 So dit blyk - 1038 00:45:37,910 --> 00:45:42,110 en laat my spring na 'n teaser hier wat in die web. 1039 00:45:42,110 --> 00:45:44,920 Ons gaan om te begin gebruik nie 'n programmeertaal op die eerste, maar 'n 1040 00:45:44,920 --> 00:45:46,030 opmaak taal. 1041 00:45:46,030 --> 00:45:48,740 'N opmaak taal as een wat soortgelyke in gees tot programmering 1042 00:45:48,740 --> 00:45:51,715 taal, maar dit gee jou nie die vermoë om jouself te logies uitdruk. 1043 00:45:51,715 --> 00:45:55,070 Dit gee net jy die vermoë om te druk jouself struktureel. 1044 00:45:55,070 --> 00:45:57,960 >> Waar wil jy iets om te sit op die bladsy, die webblad? 1045 00:45:57,960 --> 00:45:59,200 Wat is die kleur wil jy dit te maak? 1046 00:45:59,200 --> 00:46:00,950 Wat lettergrootte wil jy dit te maak? 1047 00:46:00,950 --> 00:46:02,970 Watter woorde doen jy eintlik wil op die webblad? 1048 00:46:02,970 --> 00:46:04,060 So dit is 'n opmaak taal. 1049 00:46:04,060 --> 00:46:07,690 Maar dan sal ons baie vinnig stel JavaScript, wat 'n volwaardige 1050 00:46:07,690 --> 00:46:08,560 programmeertaal. 1051 00:46:08,560 --> 00:46:12,530 Baie soortgelyk sintakties in voorkoms tot C, maar dit sal 'n paar 1052 00:46:12,530 --> 00:46:15,200 mooi, meer kragtige, meer gebruikers vriendelike kenmerke. 1053 00:46:15,200 --> 00:46:18,050 >> En een van die frustrasies op hierdie punt in die semester is dat ons sal 1054 00:46:18,050 --> 00:46:22,065 gou implementeer speller in veel minder reëls van die kode gebruik van ander tale 1055 00:46:22,065 --> 00:46:25,580 as C homself toelaat nie, maar vir die rede se Ons sal gou verstaan. 1056 00:46:25,580 --> 00:46:27,750 Dit sal die eerste sodanige webblad wees. 1057 00:46:27,750 --> 00:46:30,120 Dit sal heeltemal underwhelming, Die eerste een wat ons maak. 1058 00:46:30,120 --> 00:46:31,400 Dit sal net sê, hallo wêreld. 1059 00:46:31,400 --> 00:46:34,010 Maar as jy dit nog nooit gesien voor, dit is HTML, 1060 00:46:34,010 --> 00:46:35,670 HyperText Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> As jy na 'n sekere opsie in die meeste 'n leser, op 'n webblad op 1062 00:46:39,310 --> 00:46:43,160 die internet, kan jy sien die HTML dat sommige mense het om te 1063 00:46:43,160 --> 00:46:44,400 skep dat die webblad. 1064 00:46:44,400 --> 00:46:47,850 En dit is waarskynlik lyk nie kort of so netjies nie. 1065 00:46:47,850 --> 00:46:51,400 Maar dit sal die patroon van hierdie oop tussen hakies en houe en 1066 00:46:51,400 --> 00:46:53,660 letters en potensieel nommers. 1067 00:46:53,660 --> 00:46:56,770 >> Ek het gedink ek wil vir jou 'n teaser van wat jy sal in staat wees om te doen 1068 00:46:56,770 --> 00:46:57,950 nadat CS50. 1069 00:46:57,950 --> 00:47:02,620 Laat my gaan cs.harvard.edu / beroof, ons eie Rob Bowden se tuisblad. 1070 00:47:02,620 --> 00:47:06,080 Hy het dit vir ons. 1071 00:47:06,080 --> 00:47:07,490 So jy sal binnekort in staat wees om dit te doen. 1072 00:47:07,490 --> 00:47:10,660 En ook, wat jy hoor vanoggend - 1073 00:47:10,660 --> 00:47:12,480 wat jy gehoor het vanoggend - 1074 00:47:12,480 --> 00:47:13,780 >> [HAMSTER dansmusiek] 1075 00:47:13,780 --> 00:47:15,702 >> - You'll in staat wees om dit te maak. 1076 00:47:15,702 --> 00:47:16,790 Wat op ons wag op Woensdag. 1077 00:47:16,790 --> 00:47:17,791 Ons sal sien jy dan. 1078 00:47:17,791 --> 00:47:22,950 >> [HAMSTER dansmusiek] 1079 00:47:22,950 --> 00:47:24,300 David Malan: By die volgende CS50 - 1080 00:47:24,300 --> 00:47:31,670