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