1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID МАЛАН: Хорошо. 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 И напомнить, что проблема набора 5 закончившийся с немного сложной задачей. 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 Сталкеры, скажу я вам. "Начался достаточным описанием, а затем мы переехали 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 МАЛАН: Следующая цитата из персонала пользователя ", студент пришел ко мне домой на 23 00:01:20,410 --> 00:01:25,330 Сомервилла в 4 утра сегодня утром. "Далее персонала ", я добрался до гостиницы в Сан- 24 00:01:25,330 --> 00:01:30,016 Франциско и студент ждал меня в лобби с тремя зеркалок ". 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 могли бы знать, как Мило банан, который живет с Лорен Карвалью, наши головы 33 00:02:01,850 --> 00:02:02,905 преподавании Fellow. 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 стекла, так что мы покажем вам все это после. 38 00:02:12,230 --> 00:02:16,190 Так что это Мило, если вы хотели бы сфотографироваться с ним позже. 39 00:02:16,190 --> 00:02:18,240 Если вы хотите, чтобы высматривать на аудиторию там. 40 00:02:18,240 --> 00:02:19,430 ОК. 41 00:02:19,430 --> 00:02:20,200 Это хорошие кадры. 42 00:02:20,200 --> 00:02:22,556 Ну, Мило банан. 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 >> ОК. 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 Очень, связанных с программированием и разработки приложений и так далее, но 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 И в реестр до сих пор в этом году Восхитительные веб-приложений с Рубином на 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 для веб-приложений, мы рассмотрим , но в этом семинаре, вы перейдете 64 00:03:22,890 --> 00:03:24,070 более подробно. 65 00:03:24,070 --> 00:03:27,390 >> Прыжок движения, так что мы на самом деле есть наших друзей из Leap движения, 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. 73 00:03:43,650 --> 00:03:46,990 Android Будучи очень популярным альтернативным Телефон для IOS и Windows 74 00:03:46,990 --> 00:03:48,790 и других мобильных платформ. 75 00:03:48,790 --> 00:03:51,180 И веб активной обороне. 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 Никто из них не C, ни один из них 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 >> АУДИТОРИЯ: динамические размеры. 107 00:05:08,080 --> 00:05:09,040 >> DAVID МАЛАН: динамические размеры. 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 Вы можете просто Malloc или, более общо, выделить дополнительно 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 МАЛАН: она требует больше памяти, как именно? 123 00:05:44,240 --> 00:05:46,440 >> АУДИТОРИЯ: [неразборчиво]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID МАЛАН: Совершенно верно. 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 Ну, если мы идем на экран при этом, если мы можем быстро переопределить эти данные 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 Так ЬурейеЕ структуры, и что я хочу, чтобы эта вещь здесь? 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 N. 168 00:07:33,050 --> 00:07:35,930 И мы могли бы назвать N, что мы хотим, но она должна быть Целочисленное если мы 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 МАЛАН: Совершенно верно. 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 Так вот хэш-таблицу размером N, индексируется от 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 Хэш-таблицы является хорошим рода швейцарских Армейский нож, что позволяет хранить 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 Предположим, что Алиса, имя, просто быть проиндексированы на 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 >> Это собирается вернуться Int. 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 >> Полностью нарушена. 241 00:10:59,960 --> 00:11:02,620 Это не идеально, потому что Один из них, что, если с является недействительным? 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 >> То, что мы на прошлой неделе описал устной форме просто процесс картирования Алиса 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 >> Для задачи набор 6, одна из проблем, для вас, чтобы решить, что 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 Что делать, если у вас есть Алиса и Аарон, два человека, имена которых произошло 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 >> Ну, вы можете наивно просто положить его где Боб принадлежит, но потом Боб 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 Так что вы можете положить Боб где Чарли, и вы можете себе представить, это очень быстро 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 ищет Алису или Боба или Аарона или Чарли. 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 Хэш-таблицы по-прежнему осуществляться с массив индексов, но тип данных 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 МАЛАН: 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 МАЛАН: 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 МАЛАН: Это может занять много времени, чтобы получить в конце списка. 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 Может быть, вам лучше поддержание постоянное время вставки, Big 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 Это было синтаксического дерева - 333 00:14:46,590 --> 00:14:51,670 Т-Р-И-Е. И то, что было интересно это было, что время работы 334 00:14:51,670 --> 00:14:59,510 поиска имя, как Максвелл в прошлый раз, было большим 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 МАЛАН: Количество букв. 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 дерева, а затем следовать за указателем м, Затем указатель, то х, 349 00:15:30,521 --> 00:15:31,710 W, E, L, L. 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 Так на самом деле, да, это технически Big O 8 или 7, или действительно большой O К. Но 359 00:16:05,770 --> 00:16:09,420 если есть конечная крышка на то, что K может быть, это константа. 360 00:16:09,420 --> 00:16:12,080 И так это большое О от 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 , чем алгоритм, как Big O п, что зависит от размера того, что в 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 Памяти. 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 Очевидно, усеченный всех массивов и мы не видим много и 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 ОК. 407 00:18:02,440 --> 00:18:03,170 Так три из нас. 408 00:18:03,170 --> 00:18:03,750 Mather дом. 409 00:18:03,750 --> 00:18:05,070 Так что это для столовой Мазера. 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 МАЛАН: Мне очень жаль. 421 00:18:30,260 --> 00:18:31,210 >> АУДИТОРИЯ: вызовы функций. 422 00:18:31,210 --> 00:18:33,590 >> DAVID МАЛАН: вызовы функций, но В частности, то, что внутри каждого 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, или десятичного 428 00:18:43,080 --> 00:18:45,940 Temp, или любой другой местный переменная, мы были 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 >> А идея со стеком в том, что если имеем здесь, с или без Анненберга 441 00:19:19,240 --> 00:19:22,880 зная, поднос из соседнего дома с номером 9 на нем. 442 00:19:22,880 --> 00:19:23,870 Так что просто Int. 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 Я бы подтолкнуть этот номер 9 на стек, а теперь это прямо там. 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 это структура данных ЛИФО. 454 00:19:56,330 --> 00:19:59,680 Глупый способ описания последний вошел, первый вышел. 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 Следовательно акроним, ЛИФО. 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 Хорошо, видел вашу руку первым. 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 Так что я считаю, что это Стивен. 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 >> Но предположим, что теперь мы перемотать на начальном состояние мира, где я 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 >> Стивен: Не так много. 516 00:23:10,100 --> 00:23:12,080 >> DAVID МАЛАН: Хорошо, не так много. 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 >> Стивен: Просто случайный код, верно? 520 00:23:18,630 --> 00:23:20,220 Просто - 521 00:23:20,220 --> 00:23:23,230 >> DAVID МАЛАН: Да, я собираюсь называют это код, но случайных - 522 00:23:23,230 --> 00:23:23,820 >> Стивен: Вещей. 523 00:23:23,820 --> 00:23:28,290 >> DAVID МАЛАН: Такие вещи, как случайная 524 00:23:28,290 --> 00:23:28,870 >> Стивен: бит. 525 00:23:28,870 --> 00:23:29,530 >> DAVID МАЛАН: биты, да? 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 >> Стивен: Лоток 3 к югу. 536 00:23:53,070 --> 00:23:53,910 >> DAVID МАЛАН: Так, хорошо. 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 >> Стивен: Ноль. 541 00:24:03,880 --> 00:24:04,460 >> DAVID МАЛАН: Так оно и должно быть равно нулю. 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 >> Стивен: В - 555 00:24:36,200 --> 00:24:37,400 размер? 556 00:24:37,400 --> 00:24:37,650 >> DAVID МАЛАН: OK. 557 00:24:37,650 --> 00:24:38,770 Размер должно стать то, что? 558 00:24:38,770 --> 00:24:39,580 >> Стивен: размер должен быть один. 559 00:24:39,580 --> 00:24:39,870 >> DAVID МАЛАН: 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 >> Стивен: Мы собираемся от снизу вверх до 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID МАЛАН: 9. 569 00:24:57,760 --> 00:24:58,420 ОК, хорошо. 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 >> Стивен: Так размер будет идти до двух. 576 00:25:14,720 --> 00:25:15,300 >> DAVID МАЛАН: 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 >> Стивен: Eraser. 581 00:25:18,840 --> 00:25:19,720 >> DAVID МАЛАН: Ты кисти. 582 00:25:19,720 --> 00:25:20,560 >> Стивен: Brush. 583 00:25:20,560 --> 00:25:20,920 >> DAVID МАЛАН: OK. 584 00:25:20,920 --> 00:25:21,600 А что еще? 585 00:25:21,600 --> 00:25:22,600 >> Стивен: И тогда мы - 586 00:25:22,600 --> 00:25:22,915 >> DAVID МАЛАН: Мы выдвинули 17. 587 00:25:22,915 --> 00:25:24,760 >> Стивен: Мы придерживаемся 17 сверху, а значит - 588 00:25:24,760 --> 00:25:25,710 >> DAVID МАЛАН: Хорошо, хорошо. 589 00:25:25,710 --> 00:25:27,040 >> Стивен: - поместите его вниз. 590 00:25:27,040 --> 00:25:27,530 >> DAVID МАЛАН: Хорошо. 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 >> Стивен: Готово. 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 МАЛАН: 22. 599 00:25:40,100 --> 00:25:40,620 Отлично. 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 >> Стивен: Ох. 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 МАЛАН: Вы не сделали это предвидеть? 606 00:25:53,703 --> 00:25:55,930 >> Стивен: Я не видел этого ждать. 607 00:25:55,930 --> 00:25:58,756 Можем ли мы повторно Первоначальная мощность? 608 00:25:58,756 --> 00:25:59,790 >> DAVID МАЛАН: Это хороший вопрос. 609 00:25:59,790 --> 00:26:02,360 Итак, у нас вид окрашены себя в углу здесь. 610 00:26:02,360 --> 00:26:06,740 Там действительно ничего хорошего за Стивен потому что у нас выделено в этом массиве 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 затем мы используем Malloc в руки памяти. 616 00:26:22,300 --> 00:26:25,050 Потому что, если мы получили от памяти через кучу Malloc, мы 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 >> Так, например, наша реализация толчок может вернуться BOOL которые 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 >> [Аплодисменты] 630 00:26:53,110 --> 00:26:54,382 >> Стивен: Спасибо. 631 00:26:54,382 --> 00:26:55,680 >> DAVID МАЛАН: Спасибо. 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 Но когда я заявляю стека в другом месте в моем коде, я мог бы назвать Malloc, 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 участки памяти, которые приходят назад от Malloc. 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 Почему бы просто не объявить лотки быть указатель на узел, ERGO связанный список, 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 ингредиента или в царапинам говорят, процедуры, то, что вы положили, вы 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 Так англичане называют это обычно Очередь в любом случае, так что это хорошее имя. 687 00:29:40,270 --> 00:29:44,960 И две операции, которые очередь должна поддерживать мы будем называть Enqueue 688 00:29:44,960 --> 00:29:48,900 операции и операции из очереди, которые похожи по 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 Но для постановки в очередь что-то означает, добавить или вставить его в структуре данных. 692 00:29:57,680 --> 00:29:59,570 Чтобы из очереди означает, чтобы удалить его. 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 Зачем мне нужен дополнительный десятичного внутри очереди, чтобы отслеживать, кто находится в 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 Hardware В конце этого же. 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 Эти произвольные числа, например, Студент идентификаторы и еще много чего. 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 ОК. 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 Ну, предположим, что теперь я поставить в очередь 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 МАЛАН: Нет, это нормально. 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 Хорошо, определенно размера. 775 00:33:23,210 --> 00:33:26,430 А как насчет фронта? 776 00:33:26,430 --> 00:33:27,040 ОК, нет. 777 00:33:27,040 --> 00:33:30,200 Передняя не должна измениться, так как В отличие от стека, мы 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 МАЛАН: Джейк собирается быть удалена из очереди сейчас. 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 Так что теперь нужно, - ДИТ-ДИТ-дит! 789 00:33:51,970 --> 00:33:53,400 Что должно произойти сейчас? 790 00:33:53,400 --> 00:33:54,490 Дизайн решения. 791 00:33:54,490 --> 00:33:56,825 Так не плохой инстинкт, но - как тебя зовут? 792 00:33:56,825 --> 00:33:57,090 >> АУДИТОРИЯ: Дэвид. 793 00:33:57,090 --> 00:33:57,500 >> 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 Это заставляет меня съежиться о Big O п, Big 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 Это теперь просто 1. 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 Я мог бы просто сказать, что расположение 1? 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 Таким образом, 1, а также. 823 00:35:11,300 --> 00:35:13,410 Так что данные структуры все еще хорошо. 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 МАЛАН: Каллен. 829 00:35:16,580 --> 00:35:20,770 Давайте постановки в очередь Каллен, и 22 в настоящее время в очереди. 830 00:35:20,770 --> 00:35:22,300 Так что теперь должен изменить здесь? 831 00:35:22,300 --> 00:35:24,380 Передняя не собирается изменить, это очевидно. 832 00:35:24,380 --> 00:35:27,160 Размер будет меняться, чтобы быть 2 снова. 833 00:35:27,160 --> 00:35:31,590 И 22 заканчивается здесь, 9 по-прежнему присутствует, но это эффективно 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 >> Так что теперь, что произойдет, если Я из очереди Дэвид? 837 00:35:39,200 --> 00:35:41,560 Одна последняя операция, Dequeue Давида. 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 Предположим, что я себя поставить в очередь, 26? 845 00:36:03,280 --> 00:36:05,890 Я чувствую, что я принадлежу здесь. 846 00:36:05,890 --> 00:36:06,890 Так что я быть установлены в очередь. 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 МАЛАН: Верно. 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 Оператор Mod, в процентах. 858 00:36:30,150 --> 00:36:36,850 Потому что я стоял на технически Расположение 3, но у меня 3 мод мощности, 859 00:36:36,850 --> 00:36:40,250 SO 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 МАЛАН: Совершенно верно. 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 Аплодисментов для этих парней , и мы сообщим их оттуда. 897 00:38:12,410 --> 00:38:17,090 >> [Аплодисменты] 898 00:38:17,090 --> 00:38:18,150 >> DAVID МАЛАН: Я мог позволить Вы держите лоток. 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 Патриархальной или матриархат в самой вершине дерева. 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 поэтому мы обычно называем 2 левых ребенка и 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 Би снова означает два, в этом случае, как и с бинарными. 932 00:40:00,960 --> 00:40:04,830 И поэтому он может иметь ноль, один, или двух детей максимально. 933 00:40:04,830 --> 00:40:08,650 >> Я предлагаю, чтобы мы осуществили узла для этой структуры с Int 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 узла, или действительно корень дерева, я утверждают, что эта функция может возвращать 947 00:40:50,020 --> 00:40:53,530 истинным или ложным, что значение N внутри этого дерева. 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 Если хоть, N, значение, которое вы ищете для, меньше дерева стрелку N, и 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 Отправляйтесь туда, а затем попасть внутрь, что узла и получить его поле, названное N. 959 00:41:26,750 --> 00:41:30,810 А потом сравнить фактические N, которая была перешла в поиск против него. 960 00:41:30,810 --> 00:41:35,390 >> Таким образом, если N меньше, значение N в узле дерева сам, ну, 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 рекурсию, сейчас мы можем найти N. 987 00:42:53,910 --> 00:42:59,160 Таким образом, если N меньше, чем значение N это текущего узла, я пойду 988 00:42:59,160 --> 00:43:04,090 вперед и выбивать из рук, так сказать, и просто возвращая то, что ответ на этот вопрос из 989 00:43:04,090 --> 00:43:08,470 поиск п от левого дерева ребенка. 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 Итак, позвольте мне рекурсивно искать, проходящий N раз, но переходящая в 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 Очень похож по внешнему виду синтаксически С, но это будет иметь некоторые 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 Он будет полностью в восторг, Первое мы делаем. 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 Язык разметки гипертекста. 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 / грабить, Домашняя страница нашей собственной Роб Боудена. 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 Танцевальная музыка] 1075 00:47:13,780 --> 00:47:15,702 >> - Вы будете иметь возможность сделать это. 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 Танцевальная музыка] 1079 00:47:22,950 --> 00:47:24,300 DAVID МАЛАН: На следующей CS50 - 1080 00:47:24,300 --> 00:47:31,670