1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID Malan: Добре. 3 00:00:12,250 --> 00:00:13,860 Добре дошли отново в CS50. 4 00:00:13,860 --> 00:00:16,190 Това е началото на 8-та седмица. 5 00:00:16,190 --> 00:00:21,320 И припомни, че проблемът набор пет приключи с малко по-голямо предизвикателство. 6 00:00:21,320 --> 00:00:25,210 Така че стига да върна всичко на вашия преподаване стипендианти и фотографии СО 7 00:00:25,210 --> 00:00:30,480 във файла card.raw, имате право до сега, че всички тези хора, и 8 00:00:30,480 --> 00:00:34,510 един щастливец победител ще си тръгнете с една от тези неща, скок движение 9 00:00:34,510 --> 00:00:37,450 устройство, което можете да използвате за окончателно проекти, например. 10 00:00:37,450 --> 00:00:39,860 >> Това, всяка година, води до малко зловещо. 11 00:00:39,860 --> 00:00:43,480 И това, което мислех, че ще направите, е акция с вас някои от бележките, които имат 12 00:00:43,480 --> 00:00:47,370 отиде назад и напред над персонала списък на късно. 13 00:00:47,370 --> 00:00:51,110 Например едва снощи, цитат във файловите, от един от персонала 14 00:00:51,110 --> 00:00:55,000 членове, "Просто имах студент чук на вратата ми за да направите снимка с мен. 15 00:00:55,000 --> 00:00:59,020 Stalkers, казвам ти. "Започна, доста описателна и след това се преместихме 16 00:00:59,020 --> 00:01:02,830 към, около час по-късно, "Имах студент ме чака след точка 17 00:01:02,830 --> 00:01:06,080 и трябваше всички наши имена и снимки относно някои листа хартия. "Добре. 18 00:01:06,080 --> 00:01:09,230 Така организиран, но не всичко, което страховито все още. 19 00:01:09,230 --> 00:01:12,520 >> След това, "Аз бях извън града този уикенд, и когато се върнах, имаше един в 20 00:01:12,520 --> 00:01:12,630 мой 21 00:01:12,630 --> 00:01:16,740 спалня. "[СМЯХ] 22 00:01:16,740 --> 00:01:20,410 DAVID Malan: Next цитат от персонала член, "студент дойде в къщата ми в 23 00:01:20,410 --> 00:01:25,330 Somerville в 4 часа тази сутрин. "Next персонал, "Трябва да ми хотел в San 24 00:01:25,330 --> 00:01:30,016 Francisco и студент чакаше ми в лоби с три огледално-рефлексни фотоапарати. " 25 00:01:30,016 --> 00:01:31,510 Тип на камерата. 26 00:01:31,510 --> 00:01:34,980 "Аз не съм дори и на персонала този семестър, но един студент с взлом в къщата ми тази 27 00:01:34,980 --> 00:01:40,480 сутрин и се записва цялата работа Стъкло с Google. "И тогава на последно място, 28 00:01:40,480 --> 00:01:43,650 "Най-малко 12 души бяха нетърпение очакване за мен, когато излязох от моя 29 00:01:43,650 --> 00:01:44,800 лимузината, а след това 30 00:01:44,800 --> 00:01:46,970 Събудих се. "Добре. 31 00:01:46,970 --> 00:01:57,690 Така сред снимките, тъй като може да спомняте, са този човек тук, който ви 32 00:01:57,690 --> 00:02:01,850 може да знае като Milo Banana, който живее с Лорън Carvalho, главата ни 33 00:02:01,850 --> 00:02:02,905 преподаване сътрудник. 34 00:02:02,905 --> 00:02:05,170 Мило, Мило, ела тук момче. 35 00:02:05,170 --> 00:02:06,320 Мило. 36 00:02:06,320 --> 00:02:08,650 Мило. 37 00:02:08,650 --> 00:02:12,230 Гледай ти, той е облечен Google Glass, така че ние ще ви покажем всичко това след. 38 00:02:12,230 --> 00:02:16,190 Така че това е Milo, ако искате да се снимат с него след това. 39 00:02:16,190 --> 00:02:18,240 Ако искате да се грижа към публиката там. 40 00:02:18,240 --> 00:02:19,430 OK. 41 00:02:19,430 --> 00:02:20,200 Това е добре кадри. 42 00:02:20,200 --> 00:02:22,556 Е, Milo Banana. 43 00:02:22,556 --> 00:02:23,941 О, не прави това. 44 00:02:23,941 --> 00:02:29,020 >> [СМЯХ] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 Така че една дума тогава за това, което предстои, тъй като ние започваме да прехода, 47 00:02:34,550 --> 00:02:38,410 тази седмица специално от С в среда командния ред за PHP и 48 00:02:38,410 --> 00:02:42,720 JavaScript и SQL и HTML и CSS в уеб-базирана среда, ще бъде 49 00:02:42,720 --> 00:02:44,490 оборудване на вас с всички повече знания за 50 00:02:44,490 --> 00:02:46,010 потенциалните крайни проекти. 51 00:02:46,010 --> 00:02:49,240 Към този момент, курсът има традиция за провеждане на семинари, които 52 00:02:49,240 --> 00:02:50,950 са на тангенциални теми в дисциплината. 53 00:02:50,950 --> 00:02:54,330 Много, свързани с програмирането и да App развитие и така нататък, но 54 00:02:54,330 --> 00:02:57,010 не е задължително да изследват от собствена хода на учебната програма. 55 00:02:57,010 --> 00:03:00,250 >> Така че, ако може да се интересуват един или повече от семинари за тази година, 56 00:03:00,250 --> 00:03:02,530 се регистрира в cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Има големи семинари в cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 И на списък досега за тази година са невероятни Web Apps, с Руби на 59 00:03:10,620 --> 00:03:13,580 Релси, която е алтернатива език PHP. 60 00:03:13,580 --> 00:03:14,900 Компютърна лингвистика. 61 00:03:14,900 --> 00:03:18,710 Въведение в IOS, който е платформа, която се използва за iPhone и 62 00:03:18,710 --> 00:03:19,850 IPAD развитие. 63 00:03:19,850 --> 00:03:22,890 JavaScript за Apps Web, ще разгледаме това, но в този семинар, ще се отвори 64 00:03:22,890 --> 00:03:24,070 по-подробно. 65 00:03:24,070 --> 00:03:27,390 >> Leap Motion, така че ние действително ще има някои на нашите приятели от Leap Motion, 66 00:03:27,390 --> 00:03:29,160 самата компания, присъединете се към нас. 67 00:03:29,160 --> 00:03:31,800 Утре, в действителност, да се осигури практически на семинар, ако 68 00:03:31,800 --> 00:03:33,320 от интерес за вас. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, алтернативна техника за използване на JavaScript не в браузъра, 70 00:03:38,770 --> 00:03:39,970 но на предприятието на сървъра. 71 00:03:39,970 --> 00:03:42,110 Node.js, което е много в този дух, както добре. 72 00:03:42,110 --> 00:03:43,650 Елегантен Android Design. 73 00:03:43,650 --> 00:03:46,990 Android е много популярна алтернатива до IOS и Windows Phone 74 00:03:46,990 --> 00:03:48,790 и други мобилни платформи. 75 00:03:48,790 --> 00:03:51,180 И Security Web активна отбрана. 76 00:03:51,180 --> 00:03:54,590 >> Така че в действителност, ако искате да се включат в тази, нека 77 00:03:54,590 --> 00:03:55,840 обърнете внимание на това. 78 00:03:55,840 --> 00:03:57,790 Ние сме много щастливи да се каже, че Приятелите ни Leap 79 00:03:57,790 --> 00:03:59,140 Предложение, което е стартиране - 80 00:03:59,140 --> 00:04:01,300 това устройство наистина просто дойде от преди няколко месеца - 81 00:04:01,300 --> 00:04:05,960 любезно дарени 30 такива устройства на класа за колкото се може повече ученици, ако 82 00:04:05,960 --> 00:04:08,670 искате да се заемат на хардуер към края семестър и да я използва за 83 00:04:08,670 --> 00:04:10,390 действително окончателен проект. 84 00:04:10,390 --> 00:04:11,890 Те поддържат няколко езика. 85 00:04:11,890 --> 00:04:16,040 Никой от тях С, никой от тях не PHP, така че реализират един или повече от тези семинари 86 00:04:16,040 --> 00:04:16,899 може да се окаже от значение. 87 00:04:16,899 --> 00:04:19,730 И всички те ще бъдат заснети в случай, че не сте в състояние 88 00:04:19,730 --> 00:04:21,380 да присъства лично. 89 00:04:21,380 --> 00:04:25,000 Графикът се обявява чрез приятел, тъй като ние се втвърди стаи. 90 00:04:25,000 --> 00:04:28,460 >> И накрая, ако отидете на projects.cs.50.net, това е сайт 91 00:04:28,460 --> 00:04:31,450 ние поддържаме, че всяка година каним хора от общността, факултет, 92 00:04:31,450 --> 00:04:36,420 отдели, служители и двете в извън CS50 да 93 00:04:36,420 --> 00:04:37,730 предложат идеи за проекти. 94 00:04:37,730 --> 00:04:39,050 Неща, които представляват интерес за студентски групи. 95 00:04:39,050 --> 00:04:40,600 Неща, които представляват интерес за службите. 96 00:04:40,600 --> 00:04:43,990 Така се обръщат там, ако се борите с несигурност по отношение на това, което 97 00:04:43,990 --> 00:04:46,700 себе си би искал да се справи. 98 00:04:46,700 --> 00:04:51,760 >> Така че последният път, когато въведе може би по-сложна структура от данни, отколкото ни се 99 00:04:51,760 --> 00:04:53,300 виждал в последните седмици. 100 00:04:53,300 --> 00:04:56,550 Бихме били употребата на масиви доста щастливо като полезно, ако 101 00:04:56,550 --> 00:04:58,160 опростена структура на данните. 102 00:04:58,160 --> 00:05:00,570 След това ние въведохме тези, които разбира се са свързани списъци. 103 00:05:00,570 --> 00:05:05,470 И това, което е един от мотивите за въвеждане на тази структура от данни? 104 00:05:05,470 --> 00:05:06,930 Да? 105 00:05:06,930 --> 00:05:07,250 Какво е това? 106 00:05:07,250 --> 00:05:08,080 >> Публика: Dynamic размер. 107 00:05:08,080 --> 00:05:09,040 >> DAVID Malan: Dynamic размер. 108 00:05:09,040 --> 00:05:11,890 Така докато в масив, трябва да знаете размера си предварително, когато 109 00:05:11,890 --> 00:05:12,740 да го разпредели. 110 00:05:12,740 --> 00:05:14,380 В свързан списък, не трябва Трябва да знаете, че. 111 00:05:14,380 --> 00:05:17,610 Можете просто изчистване, или по-общо, предоставяне на допълнителна 112 00:05:17,610 --> 00:05:20,720 възел, така да се каже, всеки път, когато искате да вмъкнете повече данни. 113 00:05:20,720 --> 00:05:22,670 И възел е не предварително определено значение. 114 00:05:22,670 --> 00:05:25,580 Това е просто един общ термин, описващ някакъв вид контейнер, който сме 115 00:05:25,580 --> 00:05:29,610 използване в нашата структура от данни за съхраняване някои точка на интерес, което в този 116 00:05:29,610 --> 00:05:31,750 случай се случи да бъде цели числа. 117 00:05:31,750 --> 00:05:33,160 >> Но винаги има компромис. 118 00:05:33,160 --> 00:05:38,070 Така получаваме динамични размери на данни структура, но каква цена плащаме? 119 00:05:38,070 --> 00:05:40,040 Какво е в неблагоприятна посока на свързани списъци? 120 00:05:40,040 --> 00:05:41,006 Да? 121 00:05:41,006 --> 00:05:41,980 >> Публика: изисква повече памет. 122 00:05:41,980 --> 00:05:44,240 >> DAVID Malan: Тя изисква по- памет, как по-точно? 123 00:05:44,240 --> 00:05:46,440 >> Публиката: [недоловим]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID Malan: Точно така. 125 00:05:47,050 --> 00:05:50,460 Така че сега ние сме указатели предприемането допълнителна памет, че ние по-рано 126 00:05:50,460 --> 00:05:53,040 не е необходимо, тъй като предимство на масив, разбира се, е, че 127 00:05:53,040 --> 00:05:54,860 всичко е тези, обратно да Насрещен, които 128 00:05:54,860 --> 00:05:56,380 ви дава свободен достъп. 129 00:05:56,380 --> 00:06:00,710 Защото само с помощта на квадратна скоба нотация, или повече технически показалеца 130 00:06:00,710 --> 00:06:03,580 аритметика, много просто допълнение, можете да получите достъп всеки 131 00:06:03,580 --> 00:06:05,700 елементи в константно време. 132 00:06:05,700 --> 00:06:08,975 И всъщност, това е нещо намекваше друга цена, която ние плащаме с 133 00:06:08,975 --> 00:06:09,760 свързан списък. 134 00:06:09,760 --> 00:06:13,890 >> Какво се случва с времето на работа нещо като търсене, ако искам да 135 00:06:13,890 --> 00:06:17,270 намери някаква стойност и вътре на свързан списък? 136 00:06:17,270 --> 00:06:20,290 Какво ми времето за работа стане? 137 00:06:20,290 --> 00:06:21,560 Big O от п. 138 00:06:21,560 --> 00:06:24,060 Ако това е сортирано да? 139 00:06:24,060 --> 00:06:25,440 Какво става, ако структурата на данните е подредени? 140 00:06:25,440 --> 00:06:28,640 Мога ли да направя по-добре от голяма О п за търсене? 141 00:06:28,640 --> 00:06:31,700 Не, защото в най-лошия случай това може много добре да се сортира, но броят 142 00:06:31,700 --> 00:06:32,950 , което търсите може да е голям. 143 00:06:32,950 --> 00:06:35,370 Тя може да бъде броят 100, които може да се случи да бъде всичко 144 00:06:35,370 --> 00:06:36,410 Между другото в края. 145 00:06:36,410 --> 00:06:39,950 И тъй като можете да получите достъп до свързания списъка в този прилагането от 146 00:06:39,950 --> 00:06:42,690 начин на първото му възел, ти си все още вид на късмет. 147 00:06:42,690 --> 00:06:47,450 Трябва да се пресече всичко от началото до края, за да открие 148 00:06:47,450 --> 00:06:49,150 че голяма стойност, като 100. 149 00:06:49,150 --> 00:06:51,350 Или за да се определи дали това е дори не е там. 150 00:06:51,350 --> 00:06:55,960 >> Така че не можем да направим това, което алгоритъм за данни, структура, която изглежда по този начин? 151 00:06:55,960 --> 00:06:59,460 Не можем да направим двоично търсене, защото двоично търсене изисква, че имаме 152 00:06:59,460 --> 00:07:00,740 произволен достъп. 153 00:07:00,740 --> 00:07:04,500 Можем просто да скочи от място на място, без да се налага да следват 154 00:07:04,500 --> 00:07:07,080 тези трохи под формата на всички тези насоки. 155 00:07:07,080 --> 00:07:08,300 >> Сега, как ние прилагаме това? 156 00:07:08,300 --> 00:07:12,830 Е, ако се върнем към екрана тук, ако можем бързо reimplement тези данни 157 00:07:12,830 --> 00:07:13,440 структура - 158 00:07:13,440 --> 00:07:15,670 почерка ми не е всичко, че страхотно тук, но ние ще се опитаме. 159 00:07:15,670 --> 00:07:22,030 Така typedef структура, и какво съм искам да се обадя на това нещо тук? 160 00:07:22,030 --> 00:07:22,960 Node. 161 00:07:22,960 --> 00:07:24,580 Така че ще ни започна. 162 00:07:24,580 --> 00:07:27,860 И сега, какво трябва да бъде вътре в структурата на данните за тази поотделно 163 00:07:27,860 --> 00:07:28,430 свързан списък? 164 00:07:28,430 --> 00:07:29,950 Колко полета? 165 00:07:29,950 --> 00:07:30,450 >> Така две. 166 00:07:30,450 --> 00:07:31,570 Един от тях е доста лесно. 167 00:07:31,570 --> 00:07:33,050 Така Int п. 168 00:07:33,050 --> 00:07:35,930 И ние може да се нарече н всичко, което искате, но тя трябва да бъде едно цяло число, ако сме 169 00:07:35,930 --> 00:07:37,660 прилагане на свързан списък за цели числа. 170 00:07:37,660 --> 00:07:41,920 И сега какво прави втора областта трябва да бъде? 171 00:07:41,920 --> 00:07:43,460 Struct възел *. 172 00:07:43,460 --> 00:07:50,570 Така че, ако го направя структура възел *, а след това може да наричат ​​това също каквото си искам, 173 00:07:50,570 --> 00:07:53,510 но само за да бъде ясно, ще се обадя то следващата, тъй като ние сме били прави. 174 00:07:53,510 --> 00:07:55,270 И тогава аз ще затворя фигурни скоби. 175 00:07:55,270 --> 00:08:00,700 >> И сега, както последния път, Сложих възел тук. 176 00:08:00,700 --> 00:08:03,830 Но ако аз съм обявява това е като възел, защо се притеснява толкова 177 00:08:03,830 --> 00:08:07,320 многословно тук, като обявил, структура възел * След това, за разлика 178 00:08:07,320 --> 00:08:09,210 просто възел * следващия? 179 00:08:09,210 --> 00:08:09,904 Да? 180 00:08:09,904 --> 00:08:12,810 >> Публиката: [недоловим]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID Malan: Точно така. 182 00:08:14,050 --> 00:08:14,530 Точно така. 183 00:08:14,530 --> 00:08:18,320 Защото C наистина ще ви отведе буквално и вижда само определяне на възел 184 00:08:18,320 --> 00:08:21,230 чак дотук, не можеш се отнасят към него тук. 185 00:08:21,230 --> 00:08:24,760 Така че ние имаме този вид превантивна декларация тук, което е несъмнено 186 00:08:24,760 --> 00:08:25,390 по-многословен. 187 00:08:25,390 --> 00:08:27,810 Struct възлова точка, това означава, че сега можем да го достъп 188 00:08:27,810 --> 00:08:29,760 вътрешността на структурата на данните. 189 00:08:29,760 --> 00:08:33,370 >> И като настрана, защото това е да стане малко по-субективни сега, 190 00:08:33,370 --> 00:08:36,230 звездата технически може да отидете тук, тя може да отидете тук, тя може да 191 00:08:36,230 --> 00:08:37,179 дори да отидете в центъра. 192 00:08:37,179 --> 00:08:39,890 Ние сме приели в стил ръководство за хода, Конвенцията на пускане 193 00:08:39,890 --> 00:08:42,299 звездата в непосредствена близост до данните тип, което в този случай, 194 00:08:42,299 --> 00:08:43,460 би било възел структура. 195 00:08:43,460 --> 00:08:46,620 Но реализират в много учебници и онлайн препратки, може би наистина 196 00:08:46,620 --> 00:08:48,450 Вижте къде се намира от другата страна. 197 00:08:48,450 --> 00:08:52,200 Но просто осъзнават, че така всъщност ще се работят и просто трябва да бъде 198 00:08:52,200 --> 00:08:52,970 съвместими. 199 00:08:52,970 --> 00:08:53,580 >> Добре. 200 00:08:53,580 --> 00:08:55,630 Така че това е нашата декларация на структурата на възел. 201 00:08:55,630 --> 00:08:59,430 Но след това започнах да се занимавам повече сложни неща. 202 00:08:59,430 --> 00:09:03,410 Например, ние решихме да представим нещо като хеш таблица. 203 00:09:03,410 --> 00:09:08,160 Така че тук е хеш таблица с размер М, индексирани от 0 в горния ляв ъгъл на п 204 00:09:08,160 --> 00:09:09,690 минус 1 в долния ляв ъгъл. 205 00:09:09,690 --> 00:09:11,640 Това може да бъде хеш маса за нищо. 206 00:09:11,640 --> 00:09:15,340 Но какви неща си говорим за използване на хеш-таблица за? 207 00:09:15,340 --> 00:09:18,370 Съхраняване на какво? 208 00:09:18,370 --> 00:09:18,800 >> Имена. 209 00:09:18,800 --> 00:09:20,870 Можем да го направим имена като направихме миналия път. 210 00:09:20,870 --> 00:09:22,200 И наистина, можете да съхранявате всичко. 211 00:09:22,200 --> 00:09:24,640 И ще видим отново в PHP и JavaScript. 212 00:09:24,640 --> 00:09:28,550 A хеш таблица е хубаво нещо Swiss Армия нож, който ви позволява да съхранявате 213 00:09:28,550 --> 00:09:33,690 почти каквото искате вътре тя, като се комбинират клавишите със стойности. 214 00:09:33,690 --> 00:09:34,770 Клавиши със стойности. 215 00:09:34,770 --> 00:09:37,800 >> Сега в този прост случай, нашата Ключовете са просто числа. 216 00:09:37,800 --> 00:09:40,380 Ние сме за прилагане на хеш маса като масив. 217 00:09:40,380 --> 00:09:43,500 И така, ключовете са 0, 1, 2, и така нататък. 218 00:09:43,500 --> 00:09:47,200 И така, ние, като хора, реши миналата седмица, че знаете какво, ако сме 219 00:09:47,200 --> 00:09:50,410 Ще Магазин имена, нека просто произволно, но доста разумно, 220 00:09:50,410 --> 00:09:54,680 приемем, че Alice, А името, просто ще бъдат индексирани в 0. 221 00:09:54,680 --> 00:09:58,030 И Боб, име, B, ще бъдат индексирани в 1, и така нататък. 222 00:09:58,030 --> 00:10:02,490 Така че имахме картографиране между входовете, които са струни, и хашиш 223 00:10:02,490 --> 00:10:04,560 места, които са числа. 224 00:10:04,560 --> 00:10:07,740 >> Така че този процес е известен като хеш функция, а вие може наистина 225 00:10:07,740 --> 00:10:09,130 въведе в кода. 226 00:10:09,130 --> 00:10:12,080 Ако исках да се приложи функцията за сегментиране че прави точно това, което ние 227 00:10:12,080 --> 00:10:17,070 току-що описаното от последния път, мога да обяви функция, която използва като 228 00:10:17,070 --> 00:10:18,330 въвеждане например - 229 00:10:18,330 --> 00:10:22,190 и да го направим по този екрана тук. 230 00:10:22,190 --> 00:10:26,180 Ако исках да приложи хеш функция, мога да кажа 231 00:10:26,180 --> 00:10:27,410 нещо като това. 232 00:10:27,410 --> 00:10:29,030 >> Това ще върне вътр. 233 00:10:29,030 --> 00:10:33,600 Това ще се нарича хеш, и това е ще приеме като аргумент на 234 00:10:33,600 --> 00:10:38,920 низ, или можем да бъдем по-правилното сега, и да кажа, Чар *, ще го наричат ​​лидер. 235 00:10:38,920 --> 00:10:43,840 И тогава всички тази функция трябва да се направи, в крайна сметка, се връща Int. 236 00:10:43,840 --> 00:10:45,990 Сега, как го прави, които биха могли не е толкова ясно. 237 00:10:45,990 --> 00:10:49,510 Отивам за прилагане на настоящия без формират за проверка на грешките в момента. 238 00:10:49,510 --> 00:10:55,740 Аз съм просто ще сляпо кажа, върнете каквото е и конзола 0, минус, 239 00:10:55,740 --> 00:10:58,850 да речем, капитал и запетая. 240 00:10:58,850 --> 00:10:59,960 >> Totally счупен. 241 00:10:59,960 --> 00:11:02,620 Това не е добра, защото един, ами ако S е нула? 242 00:11:02,620 --> 00:11:04,000 Лоши неща ще се случат. 243 00:11:04,000 --> 00:11:07,940 Второ, какво ще стане ако първата буква в тази Името не е главна буква? 244 00:11:07,940 --> 00:11:09,860 Това няма да се превърне навън и от двамата. 245 00:11:09,860 --> 00:11:11,970 Може да е малка буква или не писмо на всички. 246 00:11:11,970 --> 00:11:15,520 Така че напълно за подобрение тук но това е основната идея. 247 00:11:15,520 --> 00:11:19,010 >> Това, което е описано като миналата седмица устно само на процеса на нанасяне на Alice 248 00:11:19,010 --> 00:11:23,360 0 и Боб до 1 може да се изрази със сигурност по-formulaically като C 249 00:11:23,360 --> 00:11:24,320 функционират тук. 250 00:11:24,320 --> 00:11:28,630 Наречен отново хашиш, отнема низ като вход, а след това по някакъв начин прави нещо 251 00:11:28,630 --> 00:11:31,020 с това суровини за производството на изход. 252 00:11:31,020 --> 00:11:34,130 Не е за разлика от нашата черна кутия описание че сме отдавна направено. 253 00:11:34,130 --> 00:11:36,550 Не знам как това може да бъде работа под предния капак. 254 00:11:36,550 --> 00:11:40,120 >> За проблема набор шест, едно от предизвикателствата е за вас да решите какво 255 00:11:40,120 --> 00:11:41,920 ще ви хеш функция да бъде? 256 00:11:41,920 --> 00:11:45,760 Какво ще е вътре в тази черна кутия, и вероятно, това ще бъде 257 00:11:45,760 --> 00:11:50,380 малко по-интересно от това, и определено по-податливи на грешка 258 00:11:50,380 --> 00:11:53,180 проверка от този конкретен изпълнение. 259 00:11:53,180 --> 00:11:54,580 >> Но проблеми могат да възникнат, нали? 260 00:11:54,580 --> 00:11:57,760 Ако има структурата на данните, като тази едно, което е един от проблемите, 261 00:11:57,760 --> 00:12:01,600 можете да се сблъскате с течение на времето като поставите все повече и повече имена в 262 00:12:01,600 --> 00:12:02,880 хеш-таблица? 263 00:12:02,880 --> 00:12:04,630 Можете да получите сблъсъци, нали? 264 00:12:04,630 --> 00:12:07,560 Какво става, ако имате Alice и Аарон, двама души, чиито имена случи 265 00:12:07,560 --> 00:12:08,190 да се започне с? 266 00:12:08,190 --> 00:12:11,660 Това повдига въпроса, къде си вкара второто такова име? 267 00:12:11,660 --> 00:12:15,050 >> Е, може би наивно просто го сложи където Боб принадлежи, но след това е Bob 268 00:12:15,050 --> 00:12:17,300 вид прецакани, ако се опитате да въведете името му и следващия 269 00:12:17,300 --> 00:12:18,240 няма място за него. 270 00:12:18,240 --> 00:12:21,400 Така че може да сложи Bob когато Чарли е, и можете да си представите това много бързо 271 00:12:21,400 --> 00:12:23,020 прехвърлени в доста голяма бъркотия. 272 00:12:23,020 --> 00:12:25,600 Нещо линейна в края, където можете Просто трябва да се търсят в цялата работа 273 00:12:25,600 --> 00:12:28,190 търси Алис или Боб или Aaron или Чарли. 274 00:12:28,190 --> 00:12:33,230 >> Така че, вместо ние предложихме, а не само линейно сондиране за открити пространства 275 00:12:33,230 --> 00:12:36,450 и цопване имената там, предлага красиви подход. 276 00:12:36,450 --> 00:12:41,740 A хеш таблица изпълнени още с набор от индекси, но типът на данните 277 00:12:41,740 --> 00:12:44,500 тези индекси сега са указатели. 278 00:12:44,500 --> 00:12:47,360 Указатели към какво? 279 00:12:47,360 --> 00:12:48,730 Указатели към свързани списъци. 280 00:12:48,730 --> 00:12:53,330 >> Тъй като припомнят, че на свързан списък е наистина само указател към възела, и 281 00:12:53,330 --> 00:12:57,110 възел има следващото поле, и че възловата точка има следващото поле, и така нататък. 282 00:12:57,110 --> 00:13:00,690 Така че сега можете да мислите за този масив на от лявата страна на хеш таблица като 283 00:13:00,690 --> 00:13:01,820 което води до свързан списък. 284 00:13:01,820 --> 00:13:07,000 Предимството на което е, ако получите сблъсък между Алис и Аарон, 285 00:13:07,000 --> 00:13:09,300 какво ще правиш с второ такова лице? 286 00:13:09,300 --> 00:13:14,150 Можете просто да го прикачите или си в края, или дори в началото 287 00:13:14,150 --> 00:13:15,490 на този свързан списък. 288 00:13:15,490 --> 00:13:17,340 >> И всъщност, нека просто юфка чрез че само за секунда. 289 00:13:17,340 --> 00:13:18,640 Къде щеше да е най-подходящ? 290 00:13:18,640 --> 00:13:22,060 Ако вмъкнете Алис и тя стига до първото място, а след това се опитвам да 291 00:13:22,060 --> 00:13:25,310 посочете името на Аарон, а има и очевидно сблъсък, трябва да сложа 292 00:13:25,310 --> 00:13:27,400 него в началото на свързан списък? 293 00:13:27,400 --> 00:13:30,944 Това е на първо място, че, или в края? 294 00:13:30,944 --> 00:13:31,440 >> Публиката: [недоловим]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID Malan: OK. 296 00:13:31,990 --> 00:13:32,490 Чух, че в началото си. 297 00:13:32,490 --> 00:13:33,903 Защо в началото? 298 00:13:33,903 --> 00:13:34,750 >> Публиката: [недоловим]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID Malan: OK. 300 00:13:34,940 --> 00:13:36,520 Това е азбучен, така че е хубаво. 301 00:13:36,520 --> 00:13:37,330 Това е добър имот. 302 00:13:37,330 --> 00:13:39,335 Това ще ми спести малко време потенциално. 303 00:13:39,335 --> 00:13:43,290 Той няма да ме остави да двоично търсене, но може поне да могат да се измъкнат 304 00:13:43,290 --> 00:13:47,340 на една линия, ако осъзнавам, добре, аз съм така миналото са Аарон ще бъде в тази 305 00:13:47,340 --> 00:13:48,310 сортирани свързан списък. 306 00:13:48,310 --> 00:13:50,360 Не е нужно да губя време в търсене по целия път до края. 307 00:13:50,360 --> 00:13:51,530 Така че това е разумно. 308 00:13:51,530 --> 00:13:54,710 Защо иначе може да искате да вмъкнете на сблъсък името на 309 00:13:54,710 --> 00:13:56,660 началото на списъка? 310 00:13:56,660 --> 00:13:57,397 Какво е това? 311 00:13:57,397 --> 00:13:58,680 >> Публиката: [недоловим]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID Malan: Тя може да отнеме много време за да стигнем до края на списъка. 313 00:14:00,820 --> 00:14:02,490 И в действителност, по-дълго и по-дълго. 314 00:14:02,490 --> 00:14:04,920 Колкото повече имена, които вмъквате, че Започнете с по-дълго, че 315 00:14:04,920 --> 00:14:06,280 веригата ще получите. 316 00:14:06,280 --> 00:14:07,890 Колкото по-дълго, отколкото свързан Списъкът ще получите. 317 00:14:07,890 --> 00:14:09,420 Значи вие сте наистина само Губите си времето. 318 00:14:09,420 --> 00:14:14,070 Може би вие сте по-добре поддържане постоянно вмъкване време, голяма O на 1, 319 00:14:14,070 --> 00:14:18,470 , като винаги извеждането на сблъсък името на началото на свързан списък, 320 00:14:18,470 --> 00:14:21,230 и да не се притеснявате толкова, за сортиране. 321 00:14:21,230 --> 00:14:22,600 >> Какво е най-добрият отговор? 322 00:14:22,600 --> 00:14:23,320 Не е ясно. 323 00:14:23,320 --> 00:14:26,140 Тя вид зависи от това, което разпределение е, това, което схемата е 324 00:14:26,140 --> 00:14:27,850 от имената, които поставяте. 325 00:14:27,850 --> 00:14:29,430 Това не е задължително очевиден отговор. 326 00:14:29,430 --> 00:14:33,100 Но тук отново е дизайн възможност. 327 00:14:33,100 --> 00:14:37,220 >> Така че ние после погледна това нещо, което наистина е друга голяма възможност 328 00:14:37,220 --> 00:14:38,180 за р-комплект 6. 329 00:14:38,180 --> 00:14:41,770 И осъзнавам, ако не сте го направили, Zamyla се врязва в двете от тях, хеш 330 00:14:41,770 --> 00:14:43,260 таблици и се опитва, по-подробно. 331 00:14:43,260 --> 00:14:45,630 И видео репетиция е вградени в р-набор спекулация. 332 00:14:45,630 --> 00:14:46,590 Това беше Trie - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. И това, което е интересно за това е, че времето за работа 334 00:14:51,670 --> 00:14:59,510 на търсене на името, като Maxwell Последният път, беше голяма O на какво? 335 00:14:59,510 --> 00:15:01,040 Какво е това? 336 00:15:01,040 --> 00:15:01,920 >> Публика: Броят на буквите. 337 00:15:01,920 --> 00:15:02,550 >> DAVID Malan: Брой букви. 338 00:15:02,550 --> 00:15:03,210 Чух две неща. 339 00:15:03,210 --> 00:15:04,630 Брой на писма и константно време. 340 00:15:04,630 --> 00:15:05,540 Така че нека да отида с това първо. 341 00:15:05,540 --> 00:15:06,410 Броят на буквите. 342 00:15:06,410 --> 00:15:10,195 Е, тази структура от данни, изземване, е като дърво, с родословно дърво, всяка от 343 00:15:10,195 --> 00:15:12,860 чиито възли са съставени от масиви. 344 00:15:12,860 --> 00:15:16,300 И тези масиви са указатели към други такива възли, или други такива 345 00:15:16,300 --> 00:15:17,670 масиви в дървото. 346 00:15:17,670 --> 00:15:22,890 >> Така че, ако искаме да се определи след това дали Максуел е тук, мога да отида 347 00:15:22,890 --> 00:15:26,890 на първия масив, на самия връх на дървото, така наречената корен, горната част на 348 00:15:26,890 --> 00:15:30,521 на Trie и следвайте показалеца m, след това на показалеца, то х, 349 00:15:30,521 --> 00:15:31,710 w, д, л, л. 350 00:15:31,710 --> 00:15:34,910 И тогава, когато виждам някой специален символ, обозначен тук като триъгълник. 351 00:15:34,910 --> 00:15:38,480 В кода ще видите предлагаме ви реализирана като булев, просто казвам да 352 00:15:38,480 --> 00:15:40,540 или не, една дума спира тук. 353 00:15:40,540 --> 00:15:45,270 >> Е, след като сме преминали към M-A-X-W-E-L-L, чувства като седем, може би 354 00:15:45,270 --> 00:15:48,910 осем ако отидем едно миналото, осем стъпки за намирането на Максуел. 355 00:15:48,910 --> 00:15:53,050 Или нека го наречем К. Но припомни последния време, твърди, че ако има 356 00:15:53,050 --> 00:15:57,540 реалистично максимална дължина на думата, като 40-някои по-странни герои, а 357 00:15:57,540 --> 00:16:00,810 Максималната дължина предполага постоянна стойност. 358 00:16:00,810 --> 00:16:05,770 Така че, наистина, да, това е технически голяма O от 8 или 7, или наистина голям O на K. Но 359 00:16:05,770 --> 00:16:09,420 ако има краен горна граница на това, което K може да бъде, това е константа. 360 00:16:09,420 --> 00:16:12,080 И така, това е голяма O от 1 на края на деня. 361 00:16:12,080 --> 00:16:13,040 >> Не и в реалния свят. 362 00:16:13,040 --> 00:16:15,960 Не и когато действително започнете да гледате си часовник като бягане на вашата програма. 363 00:16:15,960 --> 00:16:20,690 Това е абсолютно ще бъде малко по-бавно от наистина постоянно 364 00:16:20,690 --> 00:16:21,840 времето с една стъпка. 365 00:16:21,840 --> 00:16:25,540 Това ще бъде седем-осем стъпки, но все пак това е много, много по-добре 366 00:16:25,540 --> 00:16:30,080 от алгоритъм, като голяма O на N че зависи от размера на това, което е в 367 00:16:30,080 --> 00:16:31,220 структурата на данните. 368 00:16:31,220 --> 00:16:34,970 >> Обърнете внимание на главата тук е, че можете да поставите един милион повече имена в тази 369 00:16:34,970 --> 00:16:38,170 структурата на данните, но колко още стъпки Дали тя ще ни отнеме да се намери 370 00:16:38,170 --> 00:16:40,480 Максуел в този случай? 371 00:16:40,480 --> 00:16:40,780 Няма. 372 00:16:40,780 --> 00:16:41,820 Той е незасегната. 373 00:16:41,820 --> 00:16:45,480 И към днешна дата, не мисля, че сме виждали пример за структурата на данните или 374 00:16:45,480 --> 00:16:48,560 алгоритъм, който е напълно незасегнати от външната 375 00:16:48,560 --> 00:16:50,040 поведение като това. 376 00:16:50,040 --> 00:16:51,160 Но това не може да бъде невероятно. 377 00:16:51,160 --> 00:16:52,900 Това не може да бъде единственото решение за р-комплект 378 00:16:52,900 --> 00:16:53,570 >> И това не е всичко. 379 00:16:53,570 --> 00:16:55,980 Това не е задължително данните структура трябва да гравитират към, 380 00:16:55,980 --> 00:16:58,220 тъй като хеш таблици, компромис. 381 00:16:58,220 --> 00:17:00,500 Каква е цената, която плащате тук? 382 00:17:00,500 --> 00:17:00,940 Memory. 383 00:17:00,940 --> 00:17:02,890 Искам да кажа, това е брутално размера на паметта. 384 00:17:02,890 --> 00:17:05,569 И не мога да си го видя тук, защото автор на тази снимка 385 00:17:05,569 --> 00:17:09,420 Очевидно пресечен всички масиви, и ние не виждаме много A и 386 00:17:09,420 --> 00:17:12,700 B и C и Q и Y е и Z в тези масиви. 387 00:17:12,700 --> 00:17:13,630 Но те са там. 388 00:17:13,630 --> 00:17:17,660 >> Всеки от тези възли е цяла поредица на около 26 или повече байта, всеки от 389 00:17:17,660 --> 00:17:19,170 което представлява писмо. 390 00:17:19,170 --> 00:17:22,920 27 в нашия случай, така че можем да подкрепим апостроф в проблем сет. 391 00:17:22,920 --> 00:17:27,030 Така че това структурата на данните е много, наистина гъста и широка. 392 00:17:27,030 --> 00:17:30,880 И това само може да свърши забавя нещата, или поне да ви струва 393 00:17:30,880 --> 00:17:32,240 много повече пространство. 394 00:17:32,240 --> 00:17:34,020 Но пак, може да се направи сравнения тук. 395 00:17:34,020 --> 00:17:39,190 >> Спомнете си преди време, ние постигнахме много по-вълнуващо за време в сортиране 396 00:17:39,190 --> 00:17:42,880 когато ние използваме обединяването вид, но цената платихме за постигане на п влезте N за сливане 397 00:17:42,880 --> 00:17:46,930 подреди изисква прекарваме по какъв ресурс? 398 00:17:46,930 --> 00:17:47,690 Повече пространство. 399 00:17:47,690 --> 00:17:50,530 Имахме нужда от вторичен масив копирате хората в, точно като 400 00:17:50,530 --> 00:17:51,620 което направихме тук, на сцената. 401 00:17:51,620 --> 00:17:55,880 Така че, отново, няма ясни победителите, но просто субективно дизайн 402 00:17:55,880 --> 00:17:57,710 да се вземат решения. 403 00:17:57,710 --> 00:17:58,060 >> Добре. 404 00:17:58,060 --> 00:17:59,130 Така че какво ще кажеш за това? 405 00:17:59,130 --> 00:18:02,050 Всеки, който признава D-Hall? 406 00:18:02,050 --> 00:18:02,440 OK. 407 00:18:02,440 --> 00:18:03,170 Така че три от нас. 408 00:18:03,170 --> 00:18:03,750 Mather House. 409 00:18:03,750 --> 00:18:05,070 Така че това е за хранене на Mather. 410 00:18:05,070 --> 00:18:09,650 Обзалагам се, всички зали за хранене имат купища тави така. 411 00:18:09,650 --> 00:18:11,950 И това всъщност е представител на нещо, което съм 412 00:18:11,950 --> 00:18:13,050 очевидно вижда вече. 413 00:18:13,050 --> 00:18:14,850 Ние го нарича буквално купчина. 414 00:18:14,850 --> 00:18:18,970 И комин, от гледна точка на вашия паметта на компютъра, е мястото, където отива данни 415 00:18:18,970 --> 00:18:20,460 докато функции са призовани. 416 00:18:20,460 --> 00:18:23,410 >> Например, какви видове на нещата на стека по отношение на 417 00:18:23,410 --> 00:18:27,420 памет оформление говорихме в последните седмици? 418 00:18:27,420 --> 00:18:28,736 Какво е това? 419 00:18:28,736 --> 00:18:29,670 >> Публика: Разговори към функции. 420 00:18:29,670 --> 00:18:30,260 >> DAVID Malan: Съжалявам. 421 00:18:30,260 --> 00:18:31,210 >> Публика: Разговори към функции. 422 00:18:31,210 --> 00:18:33,590 >> DAVID Malan: Разговори към функции, но конкретно, какво има вътре на всяка от 423 00:18:33,590 --> 00:18:35,340 тези рамки? 424 00:18:35,340 --> 00:18:37,220 Какви неща? 425 00:18:37,220 --> 00:18:37,460 Да. 426 00:18:37,460 --> 00:18:38,500 Така локални променливи. 427 00:18:38,500 --> 00:18:43,080 Всеки път, когато имахме нужда някой местен съхранение, като аргумент, или Int I, или Int 428 00:18:43,080 --> 00:18:45,940 температура, или каквото и местната променлива се, ние сме били 429 00:18:45,940 --> 00:18:47,210 пускането, че в стека. 430 00:18:47,210 --> 00:18:49,610 И ние го наричаме купчина, защото на това покритие идея. 431 00:18:49,610 --> 00:18:52,940 Просто вид съвпада с реалността, понятието него. 432 00:18:52,940 --> 00:18:56,650 >> Но се оказва, че купчина може също да се разглежда като структурата на данните, за 433 00:18:56,650 --> 00:19:00,110 алтернатива на масив, който е алтернативен в свързан списък. 434 00:19:00,110 --> 00:19:02,770 Нещо по-интересно концептуално че все още може да бъде 435 00:19:02,770 --> 00:19:06,030 осъществява чрез използване на една от тези неща, но това е различен вид 436 00:19:06,030 --> 00:19:09,140 структурата на данните на подкрепа, наистина, само две операции. 437 00:19:09,140 --> 00:19:11,000 Но можете да добавите красиви функции, отколкото тези. 438 00:19:11,000 --> 00:19:12,180 Но това са основните неща - 439 00:19:12,180 --> 00:19:13,510 натиснете и поп. 440 00:19:13,510 --> 00:19:19,240 >> И идеята с комин е, че ако аз имаме тук, със или без Annenberg 441 00:19:19,240 --> 00:19:22,880 знаейки, поднос от съседната с номер 9 върху него. 442 00:19:22,880 --> 00:19:23,870 Така че просто едно цяло число. 443 00:19:23,870 --> 00:19:26,990 И аз искам да го отложа върху данните структура, която в момента е празна. 444 00:19:26,990 --> 00:19:28,790 Помислете за това на дъното на купчина. 445 00:19:28,790 --> 00:19:33,150 Аз ще настоява този номер девет върху стека, а сега е точно там. 446 00:19:33,150 --> 00:19:36,040 >> Но интересното за комин е, че ако сега искате да бутнете 447 00:19:36,040 --> 00:19:40,210 някаква друга стойност, както и 17, и натисна това върху стека, аз ще направя 448 00:19:40,210 --> 00:19:43,290 единственото нещо, което интуитивно, просто ще за привеждането му точно там, където ние, хората, 449 00:19:43,290 --> 00:19:45,180 биха били склонни да го пуснат, на върха. 450 00:19:45,180 --> 00:19:48,850 Но това, което е интересно сега е, как мога да стигна до 9? 451 00:19:48,850 --> 00:19:50,670 Знаеш ли, аз не без известно усилие. 452 00:19:50,670 --> 00:19:54,070 >> Така че това, което е интересно за комин е, че още при проектирането, 453 00:19:54,070 --> 00:19:56,330 това е данни LIFO структура. 454 00:19:56,330 --> 00:19:59,680 Silly начин да се опише последен влязъл, първи излязъл. 455 00:19:59,680 --> 00:20:03,280 Така последните номер в по това време е на 17. 456 00:20:03,280 --> 00:20:07,540 Така че, ако аз искам да изскочи нещо от на комина, той може да бъде само 17. 457 00:20:07,540 --> 00:20:11,890 Така че има задължителна цел на операции тук, където последния елемент 458 00:20:11,890 --> 00:20:14,260 в трябва да бъде първият един. 459 00:20:14,260 --> 00:20:16,440 Оттук и съкращение, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Така че, защо може това да е полезно? 461 00:20:19,160 --> 00:20:22,690 Техните контекст, в който искате искате структурата на данните по този начин? 462 00:20:22,690 --> 00:20:24,810 Е, със сигурност това е било полезно вътрешността на компютъра. 463 00:20:24,810 --> 00:20:29,050 Така че операционните системи ясно използвате тази вид на структурата на данните за стакове. 464 00:20:29,050 --> 00:20:32,800 Ще видите също и съща идея когато става въпрос за уеб страници. 465 00:20:32,800 --> 00:20:35,890 Така че тази седмица и следващата седмица и след това, и като започнете прилагането на уеб 466 00:20:35,890 --> 00:20:39,490 страници на език, наречен HTML, можете да всъщност използват структурата на данните като 467 00:20:39,490 --> 00:20:42,690 това, за да се определи дали страница е правилно форматиран. 468 00:20:42,690 --> 00:20:47,170 Защото ние ще видите всички уеб страници следват нещо като йерархия, идентификационен 469 00:20:47,170 --> 00:20:52,030 , която ще се в края на деня, да бъде дървовидна структура, намираща се под капака. 470 00:20:52,030 --> 00:20:53,620 Така че повече за това малко. 471 00:20:53,620 --> 00:20:56,560 >> Но за сега, нека да предложи за момент, как бихме могли да отидат за 472 00:20:56,560 --> 00:20:58,830 представляващи какво комин е? 473 00:20:58,830 --> 00:21:03,370 Позволете ми да предложа да прилагат комин с код, подобен на този. 474 00:21:03,370 --> 00:21:07,990 Така комин ще има вътре в него две неща, масив, наречени подноси, 475 00:21:07,990 --> 00:21:09,510 само за да бъде в съответствие с демо. 476 00:21:09,510 --> 00:21:12,660 И всеки един от елементите в този масив ще бъде Int тип. 477 00:21:12,660 --> 00:21:14,740 И капацитет е вероятно това, което? 478 00:21:14,740 --> 00:21:18,796 Защото аз не съм писал на пълното определение тук. 479 00:21:18,796 --> 00:21:21,535 >> Вероятно това е максималната дължината на масива. 480 00:21:21,535 --> 00:21:25,150 И това вероятно е деклариран с остър определят в началото на файла, някои 481 00:21:25,150 --> 00:21:28,450 вид постоянна, подразбираща се от самият капитализация. 482 00:21:28,450 --> 00:21:32,250 Така че някъде капацитет се определя като максималния възможен размер. 483 00:21:32,250 --> 00:21:35,590 В същото време, в рамките на структурата на данните известен като пакет ще има 484 00:21:35,590 --> 00:21:38,630 да е цяло число само известен просто като размер. 485 00:21:38,630 --> 00:21:43,400 >> Така че ако трябва да представлява това сега картинно, нека предположим, че това 486 00:21:43,400 --> 00:21:48,070 цялата черна кутия представлява стака си. 487 00:21:48,070 --> 00:21:50,070 Вътре е две променливи. 488 00:21:50,070 --> 00:21:54,780 Така че аз отивам да се привлече Първият и размер. 489 00:21:54,780 --> 00:21:57,420 И второто, което ми предстои да изготви като масив. 490 00:21:57,420 --> 00:22:01,060 >> Но само за да пазят нещата подреден, Обикновено аз би желал да обърне масив като 491 00:22:01,060 --> 00:22:04,910 , но това е нещо хубаво ако отговарят на действителността, или 492 00:22:04,910 --> 00:22:06,230 съответства на мисловен модел. 493 00:22:06,230 --> 00:22:12,880 Нека вместо това привлече масив вертикално, което е просто, отново, 494 00:22:12,880 --> 00:22:13,840 художника предаване. 495 00:22:13,840 --> 00:22:16,610 Няма значение какво е се намира под предния капак. 496 00:22:16,610 --> 00:22:20,350 И ние ще кажем, че по подразбиране, капацитет ще бъде три. 497 00:22:20,350 --> 00:22:23,480 Така че това ще бъде място 0, това ще бъде местоположение 1, тази 498 00:22:23,480 --> 00:22:25,740 ще бъде местоположение 2. 499 00:22:25,740 --> 00:22:29,330 >> Ако аз подкупи със стрес топката, би някой искал да излезе и да стартирате 500 00:22:29,330 --> 00:22:30,870 качат тук, само за момент? 501 00:22:30,870 --> 00:22:31,960 OK, видял ръката си пръв. 502 00:22:31,960 --> 00:22:33,950 Хайде нагоре. 503 00:22:33,950 --> 00:22:36,500 Добре. 504 00:22:36,500 --> 00:22:38,760 Така че аз вярвам, че е Steven. 505 00:22:38,760 --> 00:22:40,035 Хайде нагоре. 506 00:22:40,035 --> 00:22:40,770 Добре. 507 00:22:40,770 --> 00:22:46,760 >> Но да предположим, сега сме назад към първоначалното състоянието на света, където I 508 00:22:46,760 --> 00:22:52,180 току-що обявен за комин, и това е ще бъде на капацитет три. 509 00:22:52,180 --> 00:22:54,470 Но размер все още не е определена. 510 00:22:54,470 --> 00:22:56,100 Тави все още не е определена. 511 00:22:56,100 --> 00:22:57,300 Така няколко въпроса първо. 512 00:22:57,300 --> 00:23:01,310 И нека да ви дам микрофон, така че може участват по-активно в тази посока. 513 00:23:01,310 --> 00:23:05,190 >> Така че това, което е вътре в размер в този момент във времето, ако всичко, което са направили, е 514 00:23:05,190 --> 00:23:09,340 обявен за стека с един ред код? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: Не много. 516 00:23:10,100 --> 00:23:12,080 >> DAVID Malan: OK, не много. 517 00:23:12,080 --> 00:23:14,410 Знаем ли какво е вътре в размер, знаем какво има вътре 518 00:23:14,410 --> 00:23:16,330 на този масив тук? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Just случаен код, нали? 520 00:23:18,630 --> 00:23:20,220 Просто - 521 00:23:20,220 --> 00:23:23,230 >> DAVID Malan: Да, аз ще Наричат ​​го кода, но случайна - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: неща. 523 00:23:23,820 --> 00:23:28,290 >> DAVID Malan: Неща като случайна 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: Bits. 525 00:23:28,870 --> 00:23:29,530 >> DAVID Malan: Bits, нали? 526 00:23:29,530 --> 00:23:31,190 Така боклук стойности, нали? 527 00:23:31,190 --> 00:23:33,470 Така пермутации на 0 и 1 на. 528 00:23:33,470 --> 00:23:35,920 Останки от предишните обичаи на тази памет. 529 00:23:35,920 --> 00:23:38,150 И ние наистина не знам какви стойности са, така че ние обикновено ги въвлече 530 00:23:38,150 --> 00:23:38,930 като въпросителни знаци. 531 00:23:38,930 --> 00:23:41,990 >> Така че първото нещо, което ние сме вероятно ще искам да направя тук - 532 00:23:41,990 --> 00:23:46,630 и нека ми даде тази област в от там на име - тави. 533 00:23:46,630 --> 00:23:49,540 Какво трябва да се предполага инициализира размер, ако искаме да 534 00:23:49,540 --> 00:23:51,040 започнете да използвате това стак? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Тава е под 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID Malan: Така че, OK. 537 00:23:53,910 --> 00:23:56,710 За да бъде ясно, капацитет се декларира навсякъде другаде, три. 538 00:23:56,710 --> 00:23:58,570 И това е, което аз съм използвал да се разпределят на масива. 539 00:23:58,570 --> 00:24:03,535 Размер ще се отнасят до колко тави момента са в стека. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: нула. 541 00:24:03,880 --> 00:24:04,460 >> DAVID Malan: Така че това трябва да е нула. 542 00:24:04,460 --> 00:24:07,760 Така че продължавайте напред и с всеки пръст, направи нула по размер. 543 00:24:07,760 --> 00:24:08,440 Добре. 544 00:24:08,440 --> 00:24:10,920 Така че сега, това, което е вътре в тази тук, ние не знаем. 545 00:24:10,920 --> 00:24:12,160 Това са наистина само боклук стойности. 546 00:24:12,160 --> 00:24:14,800 Така че може да се направи въпросителни знаци, но нека да се запази борда чисти за сега 547 00:24:14,800 --> 00:24:16,300 защото това няма значение какво има там. 548 00:24:16,300 --> 00:24:19,130 Ние не трябва да се инициализира масив за нищо, защото ако ние знаем, че 549 00:24:19,130 --> 00:24:23,100 размера на стека е нула, Е, не трябва да се гледа нищо в 550 00:24:23,100 --> 00:24:25,590 този масив или иначе в този момент. 551 00:24:25,590 --> 00:24:29,970 >> Така че сега, предполагам, че аз натиснете номер 9 на стека. 552 00:24:29,970 --> 00:24:33,750 Как трябва да се актуализира структурата данни вътре в тази черна кутия? 553 00:24:33,750 --> 00:24:35,540 Какви стойности трябва да се промени? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: Within - 555 00:24:36,200 --> 00:24:37,400 размера? 556 00:24:37,400 --> 00:24:37,650 >> DAVID Malan: OK. 557 00:24:37,650 --> 00:24:38,770 Размер трябва да стане това? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Размер ще бъде един. 559 00:24:39,580 --> 00:24:39,870 >> DAVID Malan: OK. 560 00:24:39,870 --> 00:24:41,110 Така размер трябва да се превърне в един. 561 00:24:41,110 --> 00:24:42,540 Така че можете да направите това по няколко начина. 562 00:24:42,540 --> 00:24:46,920 Нека ви дам, сега си пръст е една гума. 563 00:24:46,920 --> 00:24:47,260 Добре. 564 00:24:47,260 --> 00:24:49,960 Тогава сега пръста си е четка. 565 00:24:49,960 --> 00:24:50,330 Добре. 566 00:24:50,330 --> 00:24:52,820 И сега какво друго трябва да се промени, Очевидно е, че в структурата на данните? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Отиваме от дъното до 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 Така че все още не е от значение какъв е място един или два, защото те са 571 00:25:01,550 --> 00:25:04,520 боклук стойности, но не трябва да се притеснява търси там, защото е размерът 572 00:25:04,520 --> 00:25:07,540 ни казва, че само първият елемент всъщност е законен. 573 00:25:07,540 --> 00:25:10,400 Така че сега бутнете 17 на списъка. 574 00:25:10,400 --> 00:25:11,830 Какво се случва с тази картина? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: Така размер ще отидете на две. 576 00:25:14,720 --> 00:25:15,300 >> DAVID Malan: OK. 577 00:25:15,300 --> 00:25:16,070 Ти си гумичка - 578 00:25:16,070 --> 00:25:16,810 Извинете. 579 00:25:16,810 --> 00:25:18,026 Ти си една гума. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Eraser. 581 00:25:18,840 --> 00:25:19,720 >> DAVID Malan: Ти си четка. 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 И какво още? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: И след това - 586 00:25:22,600 --> 00:25:22,915 >> DAVID Malan: Ние избута 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Ние се придържаме 17 на върха, така че - 588 00:25:24,760 --> 00:25:25,710 >> DAVID Malan: Добре, добре. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN: - да го пуснете надолу. 590 00:25:27,040 --> 00:25:27,530 >> DAVID Malan: Добре. 591 00:25:27,530 --> 00:25:27,940 Става все по-лесно. 592 00:25:27,940 --> 00:25:29,300 Аз няма да ти помогна този път. 593 00:25:29,300 --> 00:25:30,510 Натиснете 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Готово. 595 00:25:31,720 --> 00:25:34,870 Ставайки гумичка. 596 00:25:34,870 --> 00:25:37,340 Ставам четка. 597 00:25:37,340 --> 00:25:39,340 И тогава аз съм пускането 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID Malan: 22. 599 00:25:40,100 --> 00:25:40,620 Excellent. 600 00:25:40,620 --> 00:25:41,380 Така че още един път. 601 00:25:41,380 --> 00:25:44,280 Аз съм сега ще наложи на върху купчина 26. 602 00:25:44,280 --> 00:25:46,350 >> STEVEN: Ооо. 603 00:25:46,350 --> 00:25:50,278 О, Боже. 604 00:25:50,278 --> 00:25:52,520 Вие наистина ме хвана неподготвен. 605 00:25:52,520 --> 00:25:53,703 >> DAVID Malan: Не си виж този смешен? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: Аз не виждам този смешен. 607 00:25:55,930 --> 00:25:58,756 Може ние отново първоначален капацитет? 608 00:25:58,756 --> 00:25:59,790 >> DAVID Malan: Това е добър въпрос. 609 00:25:59,790 --> 00:26:02,360 Така че ние сме нещо като себе си боядисани в ъгъла тук. 610 00:26:02,360 --> 00:26:06,740 Там наистина не е добре в продължение Steven защото сме разпределят този масив 611 00:26:06,740 --> 00:26:09,130 статично, така да се каже, вътре на структурата на данните. 612 00:26:09,130 --> 00:26:12,170 И ние по същество твърди кодирани да бъде с размер три. 613 00:26:12,170 --> 00:26:14,170 Така че ние наистина не може да го преразпредели. 614 00:26:14,170 --> 00:26:20,020 >> Бихме могли, ако се върна в, ние предефинирани тави за показалка, че 615 00:26:20,020 --> 00:26:22,300 ние след това използвайте изчистване на ръка памет. 616 00:26:22,300 --> 00:26:25,050 Защото, ако ние имаме памет от купчината чрез изчистване, ние 617 00:26:25,050 --> 00:26:26,430 може след това да го освободи. 618 00:26:26,430 --> 00:26:29,630 Но преди да го освободи, бихме могли да преразпределят по-голяма парче от паметта, 619 00:26:29,630 --> 00:26:31,330 актуализиране на показалеца, и така нататък. 620 00:26:31,330 --> 00:26:33,500 Но за сега, това е наистина най-доброто което можем да направим. 621 00:26:33,500 --> 00:26:36,360 Натиснете и поп се предполага, че ще трябва да се набележат някои грешки. 622 00:26:36,360 --> 00:26:40,270 >> Така например, нашата изпълнението тласък може да се върне на булев които 623 00:26:40,270 --> 00:26:42,390 преди това се върна вярно, вярно, вярно. 624 00:26:42,390 --> 00:26:48,390 Но за четвърти път, че ще има за връщане фалшиви, например. 625 00:26:48,390 --> 00:26:48,540 Добре. 626 00:26:48,540 --> 00:26:49,540 Много добре направено. 627 00:26:49,540 --> 00:26:50,060 Поздравления. 628 00:26:50,060 --> 00:26:52,160 Вие сте спечелили стреса топката днес. 629 00:26:52,160 --> 00:26:53,110 >> [APPLAUSE] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Благодаря ви. 631 00:26:54,382 --> 00:26:55,680 >> DAVID Malan: Благодаря ви. 632 00:26:55,680 --> 00:26:59,740 ОК, така че това не изглежда много по- на крачка напред, нали? 633 00:26:59,740 --> 00:27:01,410 Ние описана тази структура от данни. 634 00:27:01,410 --> 00:27:02,320 Той е бил непреодолим, нали? 635 00:27:02,320 --> 00:27:03,200 Операционни системи харесва. 636 00:27:03,200 --> 00:27:06,360 Очевидно в интернет могат да се възползват от това, и други приложения на едно място. 637 00:27:06,360 --> 00:27:10,870 Но каква глупава ограничение, че сме назад, за да подреди на седмица две граници 638 00:27:10,870 --> 00:27:12,880 където сме фиксиран размер масиви. 639 00:27:12,880 --> 00:27:15,010 >> Така че наистина е имало няколко начините, по които би могла да реши този въпрос. 640 00:27:15,010 --> 00:27:18,750 Бихме могли да разпределя динамично масива, не по трудно кодиране както съм 641 00:27:18,750 --> 00:27:22,600 направено тук, но вместо отново да обявява това, само за да бъде ясно, като 642 00:27:22,600 --> 00:27:23,830 нещо като това. 643 00:27:23,830 --> 00:27:29,040 Int * тави не, решавайки на капацитет, все още. 644 00:27:29,040 --> 00:27:35,460 Но когато се декларират стека другаде в моя код, мога да се обадя след това изчистване, 645 00:27:35,460 --> 00:27:38,250 получите адрес на парче памет, и можех да присвоите 646 00:27:38,250 --> 00:27:39,980 този адрес да тави. 647 00:27:39,980 --> 00:27:43,340 >> И след това, защото това е просто парче памет, можех да продължат да използват площада 648 00:27:43,340 --> 00:27:45,450 скоба нотация по обичайния начин. 649 00:27:45,450 --> 00:27:49,020 Защото пак, има нещо като това функционален еквивалент на масиви и 650 00:27:49,020 --> 00:27:50,820 блокове памет, които идват обратно от изчистване. 651 00:27:50,820 --> 00:27:53,090 Ние можем да се отнасяме един към друг, тъй като използвате показалеца аритметична или 652 00:27:53,090 --> 00:27:54,440 квадратна скоба нотация. 653 00:27:54,440 --> 00:27:55,660 Така че това е един подход. 654 00:27:55,660 --> 00:28:00,120 >> Но как иначе може да се приложи тази същата структура на данните, потенциално? 655 00:28:00,120 --> 00:28:00,280 Така ли е? 656 00:28:00,280 --> 00:28:04,530 Имам чувството, че току-що решила този проблем като преди седмица. 657 00:28:04,530 --> 00:28:08,860 Какво е решението на този проблем че Стивън се блъсна в? 658 00:28:08,860 --> 00:28:10,370 Така че, свързани списъци, нали. 659 00:28:10,370 --> 00:28:13,410 >> Ако проблемът е, че ние сме боядисване себе си в ъгъла чрез разпределяне 660 00:28:13,410 --> 00:28:17,580 предварително твърде малко памет, която ние след това трябва да по някакъв начин се справят с, добре, 661 00:28:17,580 --> 00:28:19,880 Защо просто не се избегне, че издават напълно? 662 00:28:19,880 --> 00:28:26,170 Защо просто не декларират тавите да бъде указател към възела, значи е свързан списък, 663 00:28:26,170 --> 00:28:30,740 и след това просто да разпределят нови възли всеки път, когато Стивън е необходимо да се вмести в 664 00:28:30,740 --> 00:28:32,400 номер в структурата на данните. 665 00:28:32,400 --> 00:28:34,200 >> Така че на снимката ще трябва да се промени. 666 00:28:34,200 --> 00:28:38,220 Тя няма да бъде толкова чист и като просто, колкото само един набор от три цели числа. 667 00:28:38,220 --> 00:28:42,970 Сега тя ще бъде указател към структура, и че структурата ще 668 00:28:42,970 --> 00:28:44,830 имат средно и следващия показалеца. 669 00:28:44,830 --> 00:28:47,670 Това ще доведе направо, че показалеца в друга такава структура да 670 00:28:47,670 --> 00:28:48,600 друга подобна структура. 671 00:28:48,600 --> 00:28:50,560 Така че на снимката всъщност ще получите Месие малко. 672 00:28:50,560 --> 00:28:52,950 И щяхме да стрелките обвързване всичко заедно. 673 00:28:52,950 --> 00:28:55,280 >> Но това е добре, нали, защото сме виждали как се прави това. 674 00:28:55,280 --> 00:28:58,180 И след като се удобно прилагане на нещо като свързан 675 00:28:58,180 --> 00:29:01,450 списък, който ще трябва да направите, ако да изберат да изпълняват хеш таблица с 676 00:29:01,450 --> 00:29:05,120 отделни верижното за р-комплект 6, можете да Използвайте го като градивен елемент, или 677 00:29:05,120 --> 00:29:08,870 съставка, или в Scratch каже, процедура, нещо, което казано, 678 00:29:08,870 --> 00:29:12,560 създава своето собствено парче пъзел , че ще можете да повторна употреба. 679 00:29:12,560 --> 00:29:17,090 Така че компромиси, но възможните решения че всъщност сме виждали преди. 680 00:29:17,090 --> 00:29:20,560 >> Така че доста често, ще видите това всеки година или две, когато Apple пресата 681 00:29:20,560 --> 00:29:23,060 нещо ново, и всички луди хора извън състава на Apple 682 00:29:23,060 --> 00:29:27,050 магазина да купя тяхната пределна ъпгрейд на хардуера. 683 00:29:27,050 --> 00:29:30,420 Казвам това, това е ОК, защото Аз съм един от тези хора. 684 00:29:30,420 --> 00:29:35,140 Така че, какъв вид данни структура може да представлява тази реалност? 685 00:29:35,140 --> 00:29:36,980 >> Ами, нека да го наречем опашката, на ред. 686 00:29:36,980 --> 00:29:40,270 Така че British бих го нарекъл типично опашката така или иначе, така че е хубаво име. 687 00:29:40,270 --> 00:29:44,960 И двете операции, които опашка подкрепя ние ще наричаме Enqueue 688 00:29:44,960 --> 00:29:48,900 работа и dequeue операция , които са сходни по 689 00:29:48,900 --> 00:29:50,120 дух да прокара и поп. 690 00:29:50,120 --> 00:29:54,060 Това е просто нещо различно в Конвенцията, това, което ние се обаждате тях. 691 00:29:54,060 --> 00:29:57,680 Но да Enqueue нещо означава да добавите или го поставете на структурата на данните. 692 00:29:57,680 --> 00:29:59,570 За да dequeue означава да го премахнете. 693 00:29:59,570 --> 00:30:05,170 Но докато комин е данни LIFO структура, а опашката е на първо място в, 694 00:30:05,170 --> 00:30:06,740 първо от структурата на данните. 695 00:30:06,740 --> 00:30:10,050 >> Ако вие сте първият човек на опашката, ще бъде първият човек, за да получите 696 00:30:10,050 --> 00:30:12,420 от линия и си купите ново устройство. 697 00:30:12,420 --> 00:30:18,070 Представете си колко разстроен тези хора би било ако Apple използва вместо комин, за 698 00:30:18,070 --> 00:30:21,250 Така например, за прилагане на бране на новата си играчка. 699 00:30:21,250 --> 00:30:24,310 Така че опашки има смисъл, разбира се, и можем да мислим за всички видове 700 00:30:24,310 --> 00:30:27,480 приложения, вероятно, за опашки, особено когато искате справедливост. 701 00:30:27,480 --> 00:30:30,040 Е, как може ние прилагаме тези като структурата на данните? 702 00:30:30,040 --> 00:30:33,680 >> Е, аз предлагам да можем да Трябва да го направя по този начин. 703 00:30:33,680 --> 00:30:35,225 Така че аз ще вече имат номера. 704 00:30:35,225 --> 00:30:38,190 Така че ние ще продължаваме да го прости и не непременно говорим от гледна точка на тави. 705 00:30:38,190 --> 00:30:40,220 Само номера, че хората от намерила. 706 00:30:40,220 --> 00:30:43,760 Капацитет ще отново определи Общият брой на хората, които могат да бъдат в 707 00:30:43,760 --> 00:30:46,900 тази линия, като три или каквото и друга стойност. 708 00:30:46,900 --> 00:30:50,760 >> Но аз предлагам, че имам нужда, за да следите не само от размера на 709 00:30:50,760 --> 00:30:52,370 опашката, колко много неща са в него. 710 00:30:52,370 --> 00:30:56,310 Така размерът е текущия размер, капацитет е максималният размер. 711 00:30:56,310 --> 00:30:58,540 Просто отново номенклатура от Конвенцията. 712 00:30:58,540 --> 00:31:03,680 Защо ми е необходим допълнителен Int вътре на опашка, за да следите кой е в 713 00:31:03,680 --> 00:31:05,365 предната част на линията? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Защо въобще трябва да се направи, че в този случай? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Е, как е тази картина няма да се промени? 718 00:31:16,190 --> 00:31:19,280 Вероятно мога да повторно най- на тази снимка. 719 00:31:19,280 --> 00:31:21,480 Позволете ми да отида напред и да изтриете това, което е тук. 720 00:31:21,480 --> 00:31:24,580 Ще дам малко друго име тук. 721 00:31:24,580 --> 00:31:28,930 Да се ​​отървем от 17, да се отървете на 9, да се отървете от 3. 722 00:31:28,930 --> 00:31:30,410 И нека добавим още нещо. 723 00:31:30,410 --> 00:31:34,710 Аз предлагам, че имам нужда, за да следите предната част на списъка, който е само 724 00:31:34,710 --> 00:31:35,570 ще бъде едно цяло число, както добре. 725 00:31:35,570 --> 00:31:36,550 И ние ще продължим да го прости. 726 00:31:36,550 --> 00:31:37,740 Не свързан списък за сега. 727 00:31:37,740 --> 00:31:40,900 >> Ще призная, че ние ще блъскам леко в този лимит. 728 00:31:40,900 --> 00:31:43,720 Но това, което искам да видя се случи този път? 729 00:31:43,720 --> 00:31:47,240 Така че предполагам, че вървим напред и първата човек идва в линия, и 730 00:31:47,240 --> 00:31:48,560 това е номер 9. 731 00:31:48,560 --> 00:31:49,680 Имаме стрес топки. 732 00:31:49,680 --> 00:31:51,330 Мога ли да крадат, да речем, двама или трима души? 733 00:31:51,330 --> 00:31:52,690 Едно, две, три? 734 00:31:52,690 --> 00:31:53,120 Хайде нагоре. 735 00:31:53,120 --> 00:31:56,022 Още от предния, защото ние ще направим това бързо. 736 00:31:56,022 --> 00:31:59,415 >> Всеки от вас сега ще бъде Фен момче на опашка в Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Вие няма да бъдете получаване Apple хардуер в края на този все пак. 739 00:32:06,210 --> 00:32:06,500 Добре. 740 00:32:06,500 --> 00:32:09,430 Значи ти си номер 9, ти си номер 17, номер 22. 741 00:32:09,430 --> 00:32:12,130 Това са произволни числа, като Студент IDs или какво ли не. 742 00:32:12,130 --> 00:32:14,550 И в един момент, нека да започнем да започнете да добавяте неща. 743 00:32:14,550 --> 00:32:16,000 И аз ще тичам борда тук този път. 744 00:32:16,000 --> 00:32:19,570 >> Така че в този случай, аз инициализира предната да бъде - 745 00:32:19,570 --> 00:32:22,380 Аз всъщност не ми пука какво Предните, тъй като размерът е нула. 746 00:32:22,380 --> 00:32:24,480 Така че това може и просто да въпросителен знак. 747 00:32:24,480 --> 00:32:26,170 Това са всички въпросителни знаци. 748 00:32:26,170 --> 00:32:29,880 Така че сега ще започнем действително да видите някои хората се редят на опашка в магазина. 749 00:32:29,880 --> 00:32:33,320 >> Така че, ако номер 9, ти си първият там в 5 часа сутринта, давай напред и да се подредят, 750 00:32:33,320 --> 00:32:34,210 или предишната вечер. 751 00:32:34,210 --> 00:32:34,580 OK. 752 00:32:34,580 --> 00:32:35,940 Така че сега 9 е тук. 753 00:32:35,940 --> 00:32:37,940 Така че 9 е в предната част на списъка. 754 00:32:37,940 --> 00:32:41,440 Така че аз ще отида напред и да актуализира Размерът на тази текущите данни 755 00:32:41,440 --> 00:32:44,740 структура не е вече 0, а да бъде 1. 756 00:32:44,740 --> 00:32:47,630 Отивам да се сложи 9 на предната част на списъка. 757 00:32:47,630 --> 00:32:51,020 Позволете ми да отида напред и да превключите на екрана да можем да видим миналото ни тук. 758 00:32:51,020 --> 00:32:53,220 >> И сега какво искам да постави най-отпред? 759 00:32:53,220 --> 00:32:56,240 Отивам, за да следите, че отпред на опашката, точно сега 760 00:32:56,240 --> 00:32:58,570 е на място 0. 761 00:32:58,570 --> 00:33:00,510 Защото това, което е следващата ще се случи? 762 00:33:00,510 --> 00:33:03,000 Е, предполагам, сега Enqueue 17, както добре. 763 00:33:03,000 --> 00:33:04,510 Така хоп в съответствие там. 764 00:33:04,510 --> 00:33:07,060 И отново, нещо като врата към магазин ще бъде тук. 765 00:33:07,060 --> 00:33:08,700 Така че сега сте добавили 17. 766 00:33:08,700 --> 00:33:10,810 И въпреки, че тези момчета са блокиране на екрана, това е ОК, 767 00:33:10,810 --> 00:33:12,300 защото можем да я видите тук. 768 00:33:12,300 --> 00:33:12,910 Извинете. 769 00:33:12,910 --> 00:33:13,810 >> Публика: Ние може да се движи - 770 00:33:13,810 --> 00:33:14,660 >> DAVID Malan: Не, това е ОК. 771 00:33:14,660 --> 00:33:16,000 Това е огромен там. 772 00:33:16,000 --> 00:33:18,580 Така 17 сега вътрешността на опашката. 773 00:33:18,580 --> 00:33:21,332 Аз трябва да се актуализира, които полета сега все пак? 774 00:33:21,332 --> 00:33:23,210 OK, определено размер. 775 00:33:23,210 --> 00:33:26,430 А какво ще кажеш за отпред? 776 00:33:26,430 --> 00:33:27,040 OK, не. 777 00:33:27,040 --> 00:33:30,200 Front не трябва да се промени, защото За разлика от стека, ние 778 00:33:30,200 --> 00:33:31,370 искат да запазят справедливост. 779 00:33:31,370 --> 00:33:35,150 Така че, ако 9 дойде в първата, искаме 9 да бъде първият от линията 780 00:33:35,150 --> 00:33:36,420 и в магазина. 781 00:33:36,420 --> 00:33:37,220 >> Всъщност, нека да видим това. 782 00:33:37,220 --> 00:33:42,235 Преди да вмъкнете 22, да отидете напред и да dequeue 9. 783 00:33:42,235 --> 00:33:42,970 Какъв ти е името? 784 00:33:42,970 --> 00:33:43,680 >> Публика: Джейк. 785 00:33:43,680 --> 00:33:45,440 >> DAVID Malan: Джейк ще се насочва към предприятието. 786 00:33:45,440 --> 00:33:48,050 Така че можете да влезете в магазина. 787 00:33:48,050 --> 00:33:49,880 И да се преструвам, че в магазина е там. 788 00:33:49,880 --> 00:33:51,970 Така че сега това, което трябва - ДИТ-DIT-DIT! 789 00:33:51,970 --> 00:33:53,400 Какво трябва да се случи сега? 790 00:33:53,400 --> 00:33:54,490 Design решение. 791 00:33:54,490 --> 00:33:56,825 Така че не е лошо инстинкт, но - какво ти беше името? 792 00:33:56,825 --> 00:33:57,090 >> Публика: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID Malan: David. 794 00:33:57,500 --> 00:33:58,810 И какво направи Давид направя? 795 00:33:58,810 --> 00:34:02,590 Той се опитваше да сортирате определят данните структура и да се премести от своето място 796 00:34:02,590 --> 00:34:04,100 в предишно местоположение на Джейк. 797 00:34:04,100 --> 00:34:06,740 И това е добре, ако сте готови да приеме, че като 798 00:34:06,740 --> 00:34:08,199 изпълнението детайл. 799 00:34:08,199 --> 00:34:11,100 Но първо, нека да актуализира данните, структура, преди да го направя. 800 00:34:11,100 --> 00:34:14,139 Защото няма да хареса идеята за всички хората изместване в този ред. 801 00:34:14,139 --> 00:34:17,360 >> Това не е голяма работа, ако Давид го прави с една стъпка, но отново, мисля обратно 802 00:34:17,360 --> 00:34:20,360 когато сме имали осем доброволци на сцена и ние сме направили като вмъкване 803 00:34:20,360 --> 00:34:22,600 подреди, където трябваше да започне се движат всички наоколо. 804 00:34:22,600 --> 00:34:23,790 Това привлече скъпо, нали? 805 00:34:23,790 --> 00:34:28,330 Това ме кара да се свият за голям O М, Н голяма от п изправи отново. 806 00:34:28,330 --> 00:34:30,650 Той не се чувства като идеална резултат. 807 00:34:30,650 --> 00:34:32,080 >> Така че нека просто да актуализира този. 808 00:34:32,080 --> 00:34:35,120 Така размерът на опашката вече не е 2. 809 00:34:35,120 --> 00:34:37,090 Сега е просто един. 810 00:34:37,090 --> 00:34:40,360 Но сега мога да актуализира нещо Аз не актуализира по-рано, 811 00:34:40,360 --> 00:34:41,130 предната част на списъка. 812 00:34:41,130 --> 00:34:45,420 Мога просто да кажа, е, че едно място? 813 00:34:45,420 --> 00:34:49,770 Така че сега ние имаме боклук стойност тук, боклук стойност тук, и Дейвид в 814 00:34:49,770 --> 00:34:51,469 средата на този боклук. 815 00:34:51,469 --> 00:34:54,980 Но структурата на данните е все още непокътнати. 816 00:34:54,980 --> 00:34:58,540 >> И всъщност, аз дори не трябва да промените бившия номер на Джейк 817 00:34:58,540 --> 00:35:00,460 9, защото на кого му пука. 818 00:35:00,460 --> 00:35:04,470 Имам достатъчно информация сега в размер Знам, че има един човек в 819 00:35:04,470 --> 00:35:05,030 тази опашка. 820 00:35:05,030 --> 00:35:08,340 И аз знам, че това лице е на разположение 1 не 0. 821 00:35:08,340 --> 00:35:09,760 Аз не разчитам. 822 00:35:09,760 --> 00:35:11,300 Така един, както добре. 823 00:35:11,300 --> 00:35:13,410 Така структурата на данните все още е OK. 824 00:35:13,410 --> 00:35:14,330 >> Е, какво се случва след това? 825 00:35:14,330 --> 00:35:15,010 Да Enqueue - 826 00:35:15,010 --> 00:35:15,370 как ти е името? 827 00:35:15,370 --> 00:35:16,160 >> Публика: Калън. 828 00:35:16,160 --> 00:35:16,580 >> DAVID Malan: Калън. 829 00:35:16,580 --> 00:35:20,770 Нека Enqueue на Калън, и 22 вече е в опашката. 830 00:35:20,770 --> 00:35:22,300 И сега какво трябва да се промени тук? 831 00:35:22,300 --> 00:35:24,380 Front няма да промените, очевидно. 832 00:35:24,380 --> 00:35:27,160 Размер няма да се промени за 2 отново. 833 00:35:27,160 --> 00:35:31,590 И 22 озовава тук, девет все още съществува, но това е ефективно на 834 00:35:31,590 --> 00:35:32,600 боклук стойност сега. 835 00:35:32,600 --> 00:35:35,910 Това е просто един остатък от миналото Джейк. 836 00:35:35,910 --> 00:35:39,200 >> И сега какво ще стане, ако I dequeue Дейвид? 837 00:35:39,200 --> 00:35:41,560 One последната операция, dequeue David. 838 00:35:41,560 --> 00:35:46,070 Ние може да се измести, но аз предлагам нека направете малко работа колкото е възможно. 839 00:35:46,070 --> 00:35:50,280 Сега ми данни структура отива резервно по размер от 2 на 1. 840 00:35:50,280 --> 00:35:53,730 Но отпред на опашката сега става 2. 841 00:35:53,730 --> 00:35:56,640 Не е нужно да променяте тези номера просто все още, защото те са 842 00:35:56,640 --> 00:35:58,230 само боклук стойности. 843 00:35:58,230 --> 00:35:59,720 >> Но сега какво се случва? 844 00:35:59,720 --> 00:36:03,280 Да предположим, че се Enqueue, 26? 845 00:36:03,280 --> 00:36:05,890 Имам чувството, че принадлежа тук. 846 00:36:05,890 --> 00:36:06,890 Така че аз съм се enqueued. 847 00:36:06,890 --> 00:36:08,760 Така че аз вид е мястото тук. 848 00:36:08,760 --> 00:36:11,300 И въпреки че не съвсем Оценявам това визуално на сцената, 849 00:36:11,300 --> 00:36:15,075 защото имаме много място, бих не да стоя тук, защо? 850 00:36:15,075 --> 00:36:16,290 >> Публика: Ти си извън границите. 851 00:36:16,290 --> 00:36:16,370 >> DAVID Malan: Точно така. 852 00:36:16,370 --> 00:36:16,940 Аз съм извън границите. 853 00:36:16,940 --> 00:36:19,330 Аз бях индексира отвъд границите на този масив. 854 00:36:19,330 --> 00:36:23,420 Аз наистина трябва да бъде в една от най- три възможни места. 855 00:36:23,420 --> 00:36:25,150 Сега, къде е най-естествено да отидете? 856 00:36:25,150 --> 00:36:27,760 Предлагам да ливъридж една седмица един трик. 857 00:36:27,760 --> 00:36:30,150 Министерството на отбраната на оператор, процент. 858 00:36:30,150 --> 00:36:36,850 Защото аз съм технически стоящ 3 място, но аз правя 3 мод капацитет, 859 00:36:36,850 --> 00:36:40,250 така 3, знак за процент, 3 - 860 00:36:40,250 --> 00:36:40,970 капацитет е 3. 861 00:36:40,970 --> 00:36:41,720 Какво е това? 862 00:36:41,720 --> 00:36:43,700 Какво е остатъкът при разделяте 3 от 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Така че това ме поставя се Джейк беше, което всъщност е добре. 865 00:36:48,140 --> 00:36:50,370 Така че сега изпълнението на това нещо ще 866 00:36:50,370 --> 00:36:51,250 да бъде малко на главоболие. 867 00:36:51,250 --> 00:36:53,740 Това е наистина само една линия от главоболие, на код. 868 00:36:53,740 --> 00:36:56,580 Но поне сега има боклук стойност тук, но има два 869 00:36:56,580 --> 00:36:57,910 законни цели числа тук. 870 00:36:57,910 --> 00:37:04,160 И аз твърдя, че сега сме направили точно това, което трябва да направите, докато 871 00:37:04,160 --> 00:37:08,600 да променим това, което Джейк стойност е трябвало да бъде 26. 872 00:37:08,600 --> 00:37:12,110 >> Сега разполагаме с достатъчно информация, все още да се запази целостта 873 00:37:12,110 --> 00:37:13,060 на структурата на данните. 874 00:37:13,060 --> 00:37:17,160 Все още сме вид на късмет, когато ние искате да вмъкнете четири или повече общо 875 00:37:17,160 --> 00:37:20,740 елементи, но може поне да направи доста ефективно използване на тази константа 876 00:37:20,740 --> 00:37:21,740 време, в действителност. 877 00:37:21,740 --> 00:37:27,150 Не е нужно да се притеснявате за преместване Всеки човек, като наклона на Давид беше. 878 00:37:27,150 --> 00:37:30,816 >> Всякакви въпроси за стакове, или тази опашка? 879 00:37:30,816 --> 00:37:32,184 >> Публика: е причината, поради трябва размер, така че знам 880 00:37:32,184 --> 00:37:34,010 , където да има човек? 881 00:37:34,010 --> 00:37:34,770 >> DAVID Malan: Точно така. 882 00:37:34,770 --> 00:37:38,230 Трябва да се знае размера на масива защото трябва да се знае точно как 883 00:37:38,230 --> 00:37:41,940 много от тези стойности са законни, и така, че мога да намеря къде да се постави 884 00:37:41,940 --> 00:37:42,800 на следващия човек. 885 00:37:42,800 --> 00:37:43,300 Точно така. 886 00:37:43,300 --> 00:37:44,580 Размерът е - 887 00:37:44,580 --> 00:37:46,360 Всъщност, ние не актуализира това. 888 00:37:46,360 --> 00:37:48,380 Аз се добавя в 26. 889 00:37:48,380 --> 00:37:51,760 Размерът е сега, а не един, а два. 890 00:37:51,760 --> 00:37:57,780 Така че сега това наистина ми помага да намерите началото на списъка, което не е 0, а не 891 00:37:57,780 --> 00:37:59,250 1, но е 2. 892 00:37:59,250 --> 00:38:01,665 Предната част на списъка наистина е номер 22. 893 00:38:01,665 --> 00:38:05,120 Защото той дойде в първия, така че той трябва да да се разреши в магазина пред мен, 894 00:38:05,120 --> 00:38:08,780 въпреки че визуално Стоя по-близо до магазина. 895 00:38:08,780 --> 00:38:09,220 >> Ясно ли е? 896 00:38:09,220 --> 00:38:12,410 A аплодисменти за тези момчета и ще ги пусна от там. 897 00:38:12,410 --> 00:38:17,090 >> [APPLAUSE] 898 00:38:17,090 --> 00:38:18,150 >> DAVID Malan: Можех да държите на тавата. 899 00:38:18,150 --> 00:38:20,760 Можем да видим какво ще стане, ако искате, но може би не. 900 00:38:20,760 --> 00:38:21,590 Добре. 901 00:38:21,590 --> 00:38:25,380 Така че това, което сега ни води това? 902 00:38:25,380 --> 00:38:28,900 Е, нека да предложи, че има няколко други структури от данни можем да 903 00:38:28,900 --> 00:38:33,810 започнете да добавяте към нашия комплект инструменти, които ще всъщност да бъде доста, доста значими, тъй като 904 00:38:33,810 --> 00:38:35,270 ние се потопите в Мрежата неща. 905 00:38:35,270 --> 00:38:38,150 Което отново има някаква връзка да дърветата под формата на 906 00:38:38,150 --> 00:38:40,550 нещо, наречено DOM, документ обектния модел. 907 00:38:40,550 --> 00:38:42,370 Но ще видим повече от че не след дълго. 908 00:38:42,370 --> 00:38:46,260 >> Позволете ми предложи definitionally, че ние наричаме дърво сега какво може да знае като 909 00:38:46,260 --> 00:38:48,820 повече на родословно дърво, където можете има някои прародител на 910 00:38:48,820 --> 00:38:49,790 корените на дървото. 911 00:38:49,790 --> 00:38:54,480 A патриархалната или матриарх на На самия връх на дървото. 912 00:38:54,480 --> 00:38:56,700 Без техните съпрузи, в този случай. 913 00:38:56,700 --> 00:39:00,940 Но сега ние имаме това, което ние ще се обадя деца, които са възли, които висят 914 00:39:00,940 --> 00:39:05,480 разстояние отляво дете или правото дете, стрели, както е изобразено тук. 915 00:39:05,480 --> 00:39:10,490 >> С други думи, в дървовидна структура данни в компютъра, а дървото има нула 916 00:39:10,490 --> 00:39:11,480 или повече възли. 917 00:39:11,480 --> 00:39:13,500 Ако има най-малко един възел, Това се нарича корен. 918 00:39:13,500 --> 00:39:15,700 Това са неща, които визуално рисуваме на върха. 919 00:39:15,700 --> 00:39:20,280 И този възел, като всеки друг възел, може имат нула, едно, или две, или три, 920 00:39:20,280 --> 00:39:23,600 или както много деца на структурата на данните подкрепя. 921 00:39:23,600 --> 00:39:29,150 В този случай, корен, съхраняване на стойност един, има две деца, 2 и 3, 922 00:39:29,150 --> 00:39:33,020 така че ние обикновено наричаме две в ляво дете и 3 отдясно дете. 923 00:39:33,020 --> 00:39:36,940 >> И тогава, когато стигнем до 5, 6, и 7, 6, може да се нарича средата дете. 924 00:39:36,940 --> 00:39:38,940 Ако имате четири деца, става объркващо. 925 00:39:38,940 --> 00:39:42,260 Така че спрете да използвате този вид от контекстното устно. 926 00:39:42,260 --> 00:39:44,580 Но това е наистина само на родословно дърво. 927 00:39:44,580 --> 00:39:48,880 И листата тук са възли, които себе си нямат деца. 928 00:39:48,880 --> 00:39:52,540 Те висят от дъното на дървото. 929 00:39:52,540 --> 00:39:56,940 >> Е, как може да реализираме едно дърво, което има само две деца максимално? 930 00:39:56,940 --> 00:39:58,410 Ще го наречем двоичен дърво. 931 00:39:58,410 --> 00:40:00,960 Bi отново смисъл, две, в това случай, като с двоичен. 932 00:40:00,960 --> 00:40:04,830 И така, той може да има нула, едно, или две деца максимално. 933 00:40:04,830 --> 00:40:08,650 >> Ще предложа да прилагат на възела за тази конструкция с едно цяло число N, 934 00:40:08,650 --> 00:40:11,910 и след две насоки, една наречена наляво, един наречен право. 935 00:40:11,910 --> 00:40:14,830 Но това са само хубаво произволни конвенции. 936 00:40:14,830 --> 00:40:18,170 И това, което е хубаво сега, особено ако вид концептуално бореше с 937 00:40:18,170 --> 00:40:21,300 рекурсия, или мислех, че не е наистина на решение за нищо, 938 00:40:21,300 --> 00:40:23,120 особено ако можеш изчерпване на паметта. 939 00:40:23,120 --> 00:40:26,600 Сега, че ние не говорим за данни структури и алгоритми, които позволяват 940 00:40:26,600 --> 00:40:31,030 ни да пресече и да ги манипулират, Оказва се, че рекурсия се върне в 941 00:40:31,030 --> 00:40:34,240 много по-убедителна ако не е красив начин. 942 00:40:34,240 --> 00:40:38,670 >> Така че това предлагам, е прилагането на функция за търсене. 943 00:40:38,670 --> 00:40:39,870 Като се има предвид два входа - 944 00:40:39,870 --> 00:40:41,570 така че мислете за това като една черна кутия. 945 00:40:41,570 --> 00:40:46,560 Като се има предвид два входа, N, едно цяло число, и указател към едно дърво, показалец към 946 00:40:46,560 --> 00:40:50,020 възел, или наистина корените на едно дърво, I Твърдението, че тази функция може да се върне 947 00:40:50,020 --> 00:40:53,530 вярно или невярно, че стойността н е в рамките на това дърво. 948 00:40:53,530 --> 00:40:55,210 >> Какво е вътре в тази черна кутия? 949 00:40:55,210 --> 00:40:57,440 Е, четири клона. 950 00:40:57,440 --> 00:40:58,385 Първият просто проверява. 951 00:40:58,385 --> 00:41:00,490 Ако дървото е нула, просто връщане фалшиви. 952 00:41:00,490 --> 00:41:04,580 Ако няма възел, няма N, че няма номер, просто връщане фалшиви. 953 00:41:04,580 --> 00:41:12,330 Ако все пак, п, стойността, което търсите за, е по-малко от дърво стрелка п и 954 00:41:12,330 --> 00:41:15,180 само за да бъде ясно, какво означава, когато Пиша дърво и след това върху стрелката 955 00:41:15,180 --> 00:41:18,150 нотация, п? 956 00:41:18,150 --> 00:41:18,690 Точно така. 957 00:41:18,690 --> 00:41:21,970 Това означава, че и сочен показалеца нарича дърво. 958 00:41:21,970 --> 00:41:26,750 Отиди там, и след това влезе вътре на тази възел и да получите своята област нарича п. 959 00:41:26,750 --> 00:41:30,810 И след това сравнява актуалната N, че е премина в търсене против него. 960 00:41:30,810 --> 00:41:35,390 >> Така че, ако п е по-малък от стойността на п в дървото самия възел, добре, 961 00:41:35,390 --> 00:41:36,720 Какво означава това? 962 00:41:36,720 --> 00:41:40,690 Това не означава нищо на пръв поглед. 963 00:41:40,690 --> 00:41:40,900 Така ли е? 964 00:41:40,900 --> 00:41:45,560 Точно както когато имате набор от стойности, може би искате да се прилагат двоичен 965 00:41:45,560 --> 00:41:48,290 търсите като форма на разделение и владей. 966 00:41:48,290 --> 00:41:51,790 Но това, което предположение е, че трябва да направи за търсене в едномерен да работи на всички 967 00:41:51,790 --> 00:41:54,510 в телефонния указател и ранни примери? 968 00:41:54,510 --> 00:41:55,530 >> Как да се сортират. 969 00:41:55,530 --> 00:41:59,490 Така че нека да усъвършенства определението за дърво тук не да бъде само едно дърво, което може да 970 00:41:59,490 --> 00:42:00,880 има ли броя на децата. 971 00:42:00,880 --> 00:42:04,700 Не просто двоично дърво, което може да има 0, 1 или 2 максимално. 972 00:42:04,700 --> 00:42:09,700 Но като двоични дървета за търсене, или BST, която е само на луксозен начин на казвайки на 973 00:42:09,700 --> 00:42:15,430 двоични дървета, така че всяка възлова точка ляво дете, ако присъства, е 974 00:42:15,430 --> 00:42:16,830 по-малко от възловата точка. 975 00:42:16,830 --> 00:42:20,170 И правото на всеки възел на детето, ако присъства, е по-голяма 976 00:42:20,170 --> 00:42:21,740 от самия възел. 977 00:42:21,740 --> 00:42:25,200 >> Така че с други думи, ако ви се налага да изготвя дървото се, всички номера са 978 00:42:25,200 --> 00:42:30,620 внимателно балансирани, подобен на този, така че ако имате 55 като корен, 33 може да отиде 979 00:42:30,620 --> 00:42:33,090 неговото ляво, защото е по-малко от 55. 980 00:42:33,090 --> 00:42:36,430 77 могат да отидат в правото си, защото това е по-голямо от 55. 981 00:42:36,430 --> 00:42:40,750 Но сега забелязвам, същото определение, това е рекурсивна дефиниция устно, 982 00:42:40,750 --> 00:42:42,600 трябва да се прилагат за 33. 983 00:42:42,600 --> 00:42:47,610 33 на ляво детето трябва да бъде по-малко от това, и право дете на 33, 44, трябва да бъде 984 00:42:47,610 --> 00:42:48,580 по-голяма от нея. 985 00:42:48,580 --> 00:42:51,670 >> Така че това е двоичен дърво за търсене, и Аз предлагам, като се използва малко 986 00:42:51,670 --> 00:42:53,910 рекурсия, сега можем да намерим п. 987 00:42:53,910 --> 00:42:59,160 Така че, ако н е по-малко от стойността N, че е текущия възел, аз ще отида 988 00:42:59,160 --> 00:43:04,090 напред и шута, така да се каже, и само върне каквото и отговорът е на 989 00:43:04,090 --> 00:43:08,470 търсене на N на ляво дървото дете. 990 00:43:08,470 --> 00:43:11,370 Забележете отново, тази функция само очаква възел звезда, 991 00:43:11,370 --> 00:43:12,780 указател към възела. 992 00:43:12,780 --> 00:43:17,360 Така че със сигурност аз просто може да направи дърво стрелка наляво, което ще доведе 993 00:43:17,360 --> 00:43:18,400 ме на друг възел. 994 00:43:18,400 --> 00:43:19,480 Но какъв е този възел? 995 00:43:19,480 --> 00:43:22,820 >> Ами, според тази декларация, ляво е само на показалеца, така че просто 996 00:43:22,820 --> 00:43:27,090 означава, че аз съм се премине към функцията за търсене различен показалеца, а именно 997 00:43:27,090 --> 00:43:30,750 този, който представлява лявата ми детето дърво. 998 00:43:30,750 --> 00:43:36,040 Така че в този случай, на показалеца към 33, ако това е нашата извадка вход същото време, ако 999 00:43:36,040 --> 00:43:40,740 п е по-голяма от стойността на п текущия възел в дървото, тогава аз съм 1000 00:43:40,740 --> 00:43:43,370 ще вървим напред и шута в другата посока и просто да кажа, аз не 1001 00:43:43,370 --> 00:43:47,280 знам дали тази стойност п е в дървото, но знам, че ако е така, ще му е моя 1002 00:43:47,280 --> 00:43:49,090 Дясното разклонение, така да се каже. 1003 00:43:49,090 --> 00:43:53,120 Така че нека да ми се обади рекурсивно търсене, полагане на п отново, но преминава в 1004 00:43:53,120 --> 00:43:54,580 показалеца на дясната си дете. 1005 00:43:54,580 --> 00:44:00,020 >> С други думи, ако съм в момента при 55 и аз търся 99, знам, че 99 1006 00:44:00,020 --> 00:44:04,270 е по-голямо от 55, така че точно както аз разкъса телефонните седмици преди книгата и ние 1007 00:44:04,270 --> 00:44:07,140 отиде право, по същия начин ние сме ще отиде точно тук. 1008 00:44:07,140 --> 00:44:11,960 И аз не знам дали това е най-дясната ми дете, и това не е, 77 е там, но 1009 00:44:11,960 --> 00:44:13,210 Знам, че е в тази посока. 1010 00:44:13,210 --> 00:44:18,770 Така че аз наричам търсене в дясната детето ми, 77, и нека фигура търсене из 1011 00:44:18,770 --> 00:44:24,950 ако има 99 в произволна Пример за това е действително там. 1012 00:44:24,950 --> 00:44:26,900 >> Иначе, това, което е крайния случай? 1013 00:44:26,900 --> 00:44:28,620 Ако дървото е нищожна е един случай. 1014 00:44:28,620 --> 00:44:31,890 Ако п е по-малко от текущия възел е стойност е друг случай. 1015 00:44:31,890 --> 00:44:35,120 Ако п е по-голямо от настоящото стойност възел е трети случай. 1016 00:44:35,120 --> 00:44:38,250 Каква е четвъртият и последен случай? 1017 00:44:38,250 --> 00:44:39,480 Мисля, че сме от случаите, нали? 1018 00:44:39,480 --> 00:44:44,690 Тя трябва да бъде, че п е в текущия възел, че аз съм за. 1019 00:44:44,690 --> 00:44:49,640 >> Така че, ако аз съм търсене на 55 в този момент в историята, която е клон на 1020 00:44:49,640 --> 00:44:51,780 дърво ще върне истина. 1021 00:44:51,780 --> 00:44:55,380 Така че това, което е интересно тук е, че ние Всъщност, за разлика седмици миналото, ние вид 1022 00:44:55,380 --> 00:44:56,740 на имат две основни случаи. 1023 00:44:56,740 --> 00:44:58,300 И те не трябва да бъде всичко най-отгоре. 1024 00:44:58,300 --> 00:45:01,390 Горната е базовия модел, защото ако Дървото е нула, няма какво да се направи. 1025 00:45:01,390 --> 00:45:03,410 Просто се върнете твърд кодирани стойност на невярна. 1026 00:45:03,410 --> 00:45:07,400 >> Долният клон е нещо като подразбиране, при което, ако сме проверявани за 1027 00:45:07,400 --> 00:45:11,550 нищожна, ние проверихме, ако тя трябва да бъде напусна, но това не трябва да бъде, ние сме 1028 00:45:11,550 --> 00:45:14,640 контролира, дали трябва да е точно, но не трябва да бъде, ясно трябва да е 1029 00:45:14,640 --> 00:45:15,870 точно там, където сме. 1030 00:45:15,870 --> 00:45:16,780 Това е основния случай. 1031 00:45:16,780 --> 00:45:19,920 Така че има две рекурсивни случаи поставен там в средата. 1032 00:45:19,920 --> 00:45:21,630 Но би могъл да напише това в произволен ред. 1033 00:45:21,630 --> 00:45:24,520 Просто мислех, че нещо се струват естествени първо да проверите за евентуална грешка, 1034 00:45:24,520 --> 00:45:28,340 след това проверете наляво, после провери Добре, тогава предположим, че вие ​​сте на възел 1035 00:45:28,340 --> 00:45:30,630 вие всъщност търсите. 1036 00:45:30,630 --> 00:45:36,240 >> Така че, защо може това да е полезно? 1037 00:45:36,240 --> 00:45:37,910 Така се оказва, - 1038 00:45:37,910 --> 00:45:42,110 и ме остави да скочи до закачка тук това е в интернет. 1039 00:45:42,110 --> 00:45:44,920 Ще започнете да използвате не е език за програмиране в началото, но с 1040 00:45:44,920 --> 00:45:46,030 език за маркиране. 1041 00:45:46,030 --> 00:45:48,740 Маркиращ език е този, който е подобни по дух на програмиране 1042 00:45:48,740 --> 00:45:51,715 език, но това не ви дава способността да изразиш себе си логично. 1043 00:45:51,715 --> 00:45:55,070 Той само ви дава възможност да Изразете себе си структурно. 1044 00:45:55,070 --> 00:45:57,960 >> Къде искате да сложите нещо на страницата, на уеб страницата? 1045 00:45:57,960 --> 00:45:59,200 Какъв цвят искате да го направите? 1046 00:45:59,200 --> 00:46:00,950 Какво шрифта искате да го направите? 1047 00:46:00,950 --> 00:46:02,970 Какви думи да направя всъщност искат на уеб страница? 1048 00:46:02,970 --> 00:46:04,060 Така че това е език за маркиране. 1049 00:46:04,060 --> 00:46:07,690 Но след това ще въведе много бързо JavaScript, който е пълноправен 1050 00:46:07,690 --> 00:46:08,560 език за програмиране. 1051 00:46:08,560 --> 00:46:12,530 Много подобни синтактично на външен вид до C, но ще има някои 1052 00:46:12,530 --> 00:46:15,200 хубаво, по-мощен, по- удобен за потребителя функции. 1053 00:46:15,200 --> 00:46:18,050 >> И един от отчаянието на този точка в семестър е, че ние ще 1054 00:46:18,050 --> 00:46:22,065 скоро изпълнение правопис в далеч по-малко реда код, които използват други езици 1055 00:46:22,065 --> 00:46:25,580 от C самата позволява, но и за разума скоро ще се разбере. 1056 00:46:25,580 --> 00:46:27,750 Това ще бъде първата подобна уеб страница. 1057 00:46:27,750 --> 00:46:30,120 Тя ще бъде напълно underwhelming, първият правим. 1058 00:46:30,120 --> 00:46:31,400 Той просто ще кажа, здравей свят. 1059 00:46:31,400 --> 00:46:34,010 Но ако никога не сте го виждали преди, това е HTML, 1060 00:46:34,010 --> 00:46:35,670 HyperText Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> Ако отидете до определена опция от менюто в Най-всеки браузър, на всяка уеб страница на 1062 00:46:39,310 --> 00:46:43,160 в интернет, можете да видите на HTML че някои хора пише на 1063 00:46:43,160 --> 00:46:44,400 създаване, че уеб страница. 1064 00:46:44,400 --> 00:46:47,850 И това може би не изглежда толкова Накратко, или като чист, тъй като това. 1065 00:46:47,850 --> 00:46:51,400 Но това ще следват модела на тези отворени скоби и наклонени черти и 1066 00:46:51,400 --> 00:46:53,660 писма и евентуално номера. 1067 00:46:53,660 --> 00:46:56,770 >> Мислех, че ще ви дам един тийзър от това, което ще бъде в състояние да направи 1068 00:46:56,770 --> 00:46:57,950 след като CS50. 1069 00:46:57,950 --> 00:47:02,620 Пуснете ме да cs.harvard.edu / Роб, начална страница със собствена Rob Боудън. 1070 00:47:02,620 --> 00:47:06,080 Той направи това за нас. 1071 00:47:06,080 --> 00:47:07,490 Така че скоро ще бъде в състояние да направи това. 1072 00:47:07,490 --> 00:47:10,660 И също така, това, което сте чули тази сутрин - 1073 00:47:10,660 --> 00:47:12,480 това, което чух тази сутрин - 1074 00:47:12,480 --> 00:47:13,780 >> [HAMSTER DANCE MUSIC] 1075 00:47:13,780 --> 00:47:15,702 >> - You'Ll бъде в състояние да направи това. 1076 00:47:15,702 --> 00:47:16,790 Това ни очаква в сряда. 1077 00:47:16,790 --> 00:47:17,791 Ще се видим тогава. 1078 00:47:17,791 --> 00:47:22,950 >> [HAMSTER DANCE MUSIC] 1079 00:47:22,950 --> 00:47:24,300 DAVID Malan: На следващото CS50 - 1080 00:47:24,300 --> 00:47:31,670