[Играет музыка] 

ANDI Пэн: Добро пожаловать в неделю 6 раздела. Мы отклонились от нашего стандарта раздел время во вторник днем, чтобы этот прекрасный воскресенье утром. Спасибо за всем, что присоединился ко мне сегодня, но серьезно, аплодисменты. 

Это довольно большое усилие. Я почти не даже сделать его в то время, но это было в порядке. Так что я знаю, что все вы только что сделали его в викторине. Прежде всего, добро пожаловать в оборотная сторона этого. 

Во-вторых, мы поговорим об этом. Мы поговорим о викторине. Мы поговорим о том, как Вы делаете в классе. Вам будет хорошо. У меня есть свои викторины для Вы в конце здесь, так что если вы, ребята, хотите, чтобы принять Взгляд на него, совершенно нормально. 

Так быстро прежде чем мы начнем, то Повестка дня на сегодня выглядит следующим образом. Как вы можете видеть, мы в основном быстрое увольнение через целую кучу структур данных действительно, действительно, действительно быстро. Так как таковое, оно не будет супер интерактивная сегодня. Это будет просто мне вроде кричать вещи, которые вы, и если я путаю вас, если я иду слишком быстро, дайте мне знать. Они просто различные данные структуры, а также в рамках Вашей PSET для этого Предстоящая неделя, вы будете будет предложено реализовать один из них, возможно, два из them-- два из них в PSET. ОК, так что я просто хочу, чтобы начать с некоторых объявлений. Мы пойдем по стеков и очередей в более Глубина, чем то, что мы делали раньше викторины. Мы пойдем по связаны список снова, снова, более подробно, чем то, что мы имели до викторины. И тогда мы будем говорить о хеш столы, деревья и пытается, которые все довольно необходимо для вашего PSET. И тогда мы будем идти над некоторыми Полезные советы для pset5. 

Итак, викторина 0. Средняя был 58%. Это была очень низкой, и так вы, ребята, все сделал очень, очень хорошо в соответствии с этим. 

Довольно много, правило, если вы в стандартном отклонении от среднего особенно, так как мы находимся в менее удобные раздел, вы совершенно нормально. Вы на верном пути. Жизнь хороша. 

Я знаю, что это страшно думать, что Я получил, как 40% на этом конкурсе. Я собираюсь на провал этого класса. Я обещаю вам, вы не происходит сбой класс. Ты совершенно нормально. 

Для тех из вас, кто получил более среднее, впечатляет, впечатляет, как серьезно хорошо сделано. Я их со мной. Не стесняйтесь, получить их В конце раздела. Позвольте мне знать, если у вас есть вопросы, вопросы с ними. Если мы добавим ваш счет так, дайте нам знать. 

Итак, pset5, это действительно странно неделю Йельском университете в смысле что наша PSET связано В среду в полдень в том числе конце дня, так что на самом деле Теоретически из-за вторник в полдень. Наверное, никто не закончил на вторник в полдень. Это совершенно нормально. Мы собираемся, чтобы иметь приемные часы сегодня, а также в понедельник вечером. И все разделы этой неделе будет фактически превратился в мастерских, так что не стесняйтесь поп любое сечение хотите, и они будут своего рода мини-PSET семинары для помощи в этом. Так как таковое, это единственный раздел, где мы учебный материал. Все другие разделы будут фокусировки исключительно на помощь для PSET. Да? 

АУДИТОРИЯ: Где рабочие часы? 

ANDI Пэн: Часы tonight-- о, хороший вопрос. Я думаю, что сегодня вечером офис часов в Teal или общин. Если вы посмотрите онлайн CS50 и вы идете к офисной часов, должен быть график, что говорит вам, где все из них. 

Я знаю, как сегодня или завтра чирок, и я думаю, что мы, возможно, фонда для другой ночи. Я не уверен. Хороший вопрос. Проверьте CS50. 

Прохладные, любые вопросы, касающиеся График на следующий, как три дня? Я обещаю вам, ребята, как Давида сказал, что это вершина холма. Вы, ребята, почти нет. Всего три более дней. Получить там, а затем мы все сойдет. Мы будем иметь хороший CS-бесплатный перерыв. Добро пожаловать назад. Мы в сети нырять программирование и разработка, вещи, которые очень весело сравнению в некоторых других psets. И это будет холод и мы будем иметь много веселья. Мы будем иметь больше конфет. К сожалению для конфет. Я забыл конфеты. Это был грубый утром. Таким образом, вы, ребята, почти там, и я очень горжусь вами, ребята. 

ОК, так что стеки. Кто любил вопрос о Джеке и его одежда на викторине? Никто? ОК, это нормально. 

Так по существу, как вы можете фото Джек, этот парень здесь, любит принимать одежду из верхней части стека, и он кладет его обратно на стек после того как он сделал. Так что в этом пути, он никогда кажется, становится в нижней части укладывают в его одежде. Так что это своего рода описывает основная структура данных как стек реализован. 

По сути, думать о стек, как любой стек объектов где вы положили вещи на вершине, и то вы поп их сверху. Так ЛИФО является аббревиатурой нам нравится чтобы use-- Последнее вошел, первым вышел. И так, чтобы продолжаться в верхней части стек первым, который выходит. И так два члена мы хотели бы связать с, что называется толчок и поп-музыки. Когда вы нажимаете на то стек, и вы поп его обратно. 

И поэтому я думаю, это своего рода абстрактное понятие для тех из вас, кто хочет видеть, как практическая реализация в реальном мире. Как многие из вас написали эссе может быть, как час, прежде чем он был из-за, и вы случайно удалили огромный кусок ней, как случайно? И тогда то, что управление делаю мы используем, чтобы положить его обратно? Control-Z, да? Control-Z, так что количество времени что Control-Z спас мою жизнь, спас мою задницу, каждый раз, который реализуется через стек. 

По существу вся информация что на вашем документе Word, он получает толкнул и выскочил на волю. И так всякий раз, когда вам существенно удалить что-нибудь, вы поп его обратно. И потом, если вам это нужно снова, вам толкать его, что это то, что Ctrl + C делает. И так реальный мир функция о том, как простой структуры данных может помочь с вашей повседневной жизни. 

Таким образом, структура является способом, которым мы на самом деле создать стек. Набираем определить-структуру, а затем мы называем это стек на дне. И в стеке, у нас есть два параметра что мы можем по существу манипулировать, так что мы должны сЬаг звезды строк мощности. 

Все, что он делает создает массив что мы можем хранить все, что вы хотите которые мы можем определить его емкость. Емкость находится всего макс количество предметы можно положить в этом массиве. Размер INT это счетчик, который держит отслеживать, сколько элементов в настоящее время в стеке. Итак, мы можем отслеживать, А, и, как большая фактическая стек, и, В, сколько этого стека мы заполнили, потому что мы не хотим, переполнение над тем, что наши возможности. 

Так, например, этот прекрасный Вопрос был на викторине. По сути, как мы толкать на верх стека. Довольно просто. Если вы посмотрите на него, мы будем идти через это. Если [неразборчиво] размер-- помните, когда вы хотите получить доступ к любой Параметр в структуры, вы имя struct.parameter. 

В этом случае, с вне имя нашего стека. Мы хотим, чтобы открыть размер это, поэтому мы делаем s.size. Так что, пока размер не равна мощности или до тех пор, а это меньше, чем емкость, либо будет работать здесь. 

Вы хотите получить доступ к внутренней вашего стека, так s.strings, и вы собираетесь положить, что новый номер что вы хотите вставить в там. Давайте просто скажем, мы хотим, чтобы вставьте Int N в стек, мы могли бы сделать s.strings, кронштейны, s.size равен п. Потому что размер где мы в настоящее время в стеке если мы собираемся, чтобы подтолкнуть это, мы просто доступ там, где размер, тем ток полнота стека, и мы нажимаем Int N на него. А потом мы хотим, чтобы убедиться, что мы также увеличивая размер п, так что мы можем отслеживать мы в добавили дополнительный предмет в стек. Теперь у нас есть больший размер. Значит ли это, здесь смысл все, как логически это работает? Это был своего рода быстро. АУДИТОРИЯ: Можете ли вы перейти в s.stringss.strings [s.size] еще раз? ANDI Пэн: Конечно, так, что делает s.size настоящее время нам дает? АУДИТОРИЯ: Это текущий размер. ANDI Пэн: Ровно, поэтому текущий индекс, что наш размер на, и поэтому мы хотим, чтобы поставить новый целое число что мы хотим, чтобы вставить в s.size. Имеет ли это смысл? Потому s.strings, все, что это является имя массива. Все это обращается к Массив в нашей структуры, и поэтому, если мы хотим, чтобы разместить п в этом индексе, мы можем просто открыть его с помощью кронштейнов s.size. Круто. 

Ладно, поп, я псевдокод его для вас, ребята, но аналогичной концепции. Имеет ли это смысл? Если размер больше, нуля, то вы знаю, что вы хотите взять что-то из-за, если размер не больше нуля, то вы не имеют ничего в стеке. 

Итак, вы хотите только выполнять этот код, он может только поп, если есть что-то, чтобы поп-музыки. Таким образом, если размер больше чем 0, то минус размер. Мы уменьшаем размер, а затем вернуться все, что внутри него, потому что суя, мы хотим, чтобы Доступ все, что хранится в индексе вершины стека. Все смысл? Если бы я сделал, вы, ребята написать это, вы, ребята, будет иметь возможность записать его? ОК, вы, ребята, можете поиграть с ним. Не беспокойтесь, если вы не получите его. Мы не успели закодировать это сегодня, потому что мы есть много этих структур чтобы пройти, но по существу псевдокод, очень, очень похожи, чтобы подтолкнуть. Просто следуйте вдоль логики. Убедитесь, что вы обращаетесь все особенности вашей структуры правильно. Да? 

АУДИТОРИЯ: Будут ли эти слайды и Вся эта вещь будет до сегодня-иш? ANDI Пэн: Всегда, да. Я собираюсь попробовать поставить это до, как через час после. Я электронной почте Давида, Дэвид будет пытаться положить его, как через час после этого. 

ОК, так что потом мы перейдем в этот другой прекрасный структура данных, называемая очередь. Как вы, ребята, можете посмотреть здесь, А Очередь, для англичан среди нас, Все это представляет собой линию. Так вопреки тому, что Вы думаете, что стек, очередь именно то, что логически вы думаете. Он проводится по правилам FIFO, который является первым вошел, первым вышел. Если вы первый один в линии, вы первое, что выходит из линии. 

Итак, что мы хотели бы назвать это в освобождении пакета из очереди и enqueueing. Если мы хотим что-то добавить в нашей очереди, мы в очередь. Если мы хотим, чтобы из очереди, или взять то прочь, мы из очереди. 

Так же смысл, что мы вроде создания элементов фиксированного размера, что мы может хранить определенное вещи, но мы можем также изменить, где мы размещения Параметры внутри них на основе того, какой тип Функциональность мы хотим. Так стеков, мы хотели последний Один из них, N, чтобы быть первым из. Очередь мы хотим первое и быть первое, что. 

Так в структуры типа определить, как вы можете видеть, это немного отличается от того, что стэк потому что мы не только должны иметь трек, где в настоящее время размер, мы также хотим, чтобы отслеживать голову как и где мы в настоящее время. Так что я думаю, что это проще если я рисую это. Итак, давайте представим, что у нас есть очередь, так скажем, голова прямо здесь. Глава линии, давайте просто сказать, что это в настоящее время, и мы хотим, чтобы вставить то в очереди. Я собираюсь позвонить размер существенно это то же самое, как хвост, конец, где ваш очереди. Давайте просто скажем, размер прямо здесь. 

Так как же реально вставить что-то в очереди? Что индекс мы хотим разместить где мы хотим вставить в. Если это начало вашей очереди, и это в конце его или размер его, где мы Чтобы добавить следующий объект? 

АУДИТОРИЯ: [неразборчиво] ANDI Пэн: Ровно, вы хотите, чтобы добавить это в зависимости от вы написали это. Либо это пустой или пустой. Итак, вы хотите, чтобы добавить его, вероятно, здесь, потому что, если размер is-- если они все полны, вы хотите чтобы добавить его прямо здесь, прямо? 

И так вот, в то время как очень, очень просто, не совсем всегда правильно потому что основное различие между очереди и стека является то, что очередь может на самом деле манипулировать так что изменения главные в зависимости от того, где вы хотите начало вашего кия, чтобы начать. И в результате, твой хвост Также изменится. И так взглянуть на этот код прямо сейчас. Как вы, ребята, было также предложено написать на викторине, поставить в очередь. Может быть, мы поговорим через почему ответ был, что это было. 

Я не мог соответствовать этой линии на один, но по сути это кусок кода должны находиться на одной линии. Проведите как 30 секунд. Взгляните, и понять, почему это путь, что это. 

Очень, очень похожи структура, очень, очень Подобная структура, как и предыдущий стек для, возможно, за исключением того, одной строки кода. И, что одной строки кода определяет функциональность. И это действительно отличает очередь из стопки. 

Кто-нибудь хочет принять удар на объяснение, почему вы получил эту сложную вещь в здесь? Мы видим возвращение нашего замечательный друг модуль. Как вы, ребята, скоро придет признать в программировании, почти в любое время нужно что-то обернуть вокруг ничего, модуль будет путь, чтобы сделать это. Так, зная, что, кто-нибудь хочет попробовать объясняя, что строки кода? Да, все ответы принимаются и одобряются. АУДИТОРИЯ: Вы говорите мне? ANDI Пэн: Да. АУДИТОРИЯ: О, нет извините. ANDI Пэн: ОК, так что давайте ходить через этот код. Поэтому, когда вы пытаетесь что-то добавить на очереди, в прекрасном случае, что глава случается чтобы быть здесь, это очень легко для нас просто идти до конца вставить что-то, верно? Но вся суть в очереди что глава может на самом деле динамически меняться в зависимости от где хотите начало нашего ц быть, и, как таковой, хвост Также изменится. 

И так представить, что это не было очереди, а это было очереди. Скажем, голова прямо здесь. Скажем, наша очередь посмотрел, как это. Если бы мы хотели, чтобы переложить, где начало линии, давайте говорить, что мы перешли голову таким образом, и здесь размеры. 

Теперь мы хотим, чтобы добавить что-то эта очередь, но, как вы, ребята, можете видеть, это не так просто, как просто добавить все, что после размера потому что тогда мы бежим из Границы нашего фактического массива. Где мы хотим, чтобы действительно добавить здесь. Это красота очереди является то, что для нас, визуально Похоже, что линия идет, как это, но при хранении в структуре данных, они дают его в качестве как цикл. Это своего рода обтекает к фронту таким же образом что линия может также обернуть вокруг в зависимости от везде, где вас хочу начале строки, чтобы быть. И поэтому, если мы берем искать здесь, давайте что мы хотим, чтобы создать Функция называется Добавляет. Мы хотели, чтобы добавить Int N в этой д. Если q.size q-- мы называем это наши данные structure-- если наша queue.size не равно мощности или если это меньше, чем емкость, q.strings это массив в нашей ц. Мы собираемся установить что равно q.heads, что прямо здесь, плюс q.size Модуль емкостью, которая обернуть нас здесь. 

Таким образом, в этом примере, индекс главы 1, верно? Индекс размера 0, 1, 2, 3, 4. Таким образом, мы можем сделать 1 плюс 4 модуля нашей способности, которая 5. Что это нам дает? Что такое индекс, который выходит из этого? 

АУДИТОРИЯ: 0. 

ANDI Пэн: 0, бывает здесь, и поэтому мы хотим, чтобы иметь возможность вставить в прямо здесь. И так это уравнение здесь вид просто работает с любыми номерами в зависимости от того, где ваш голова и ваш размер есть. Если вы знаете, что те, вещи, вы знаете, именно там, где вы хотите вставить все, что после очереди. Имеет ли это смысл для всех? 

Я знаю, вроде мозга тизер особенно, так как это пришли в после вашего теста. Но, надеюсь, все Теперь можно понять Поэтому это решение или это функция так, что это такое. Любой немного неясно по этому поводу? ХОРОШО. 

И вот теперь, если вы хотел из очереди, это где наша голова будет переход потому что, если мы должны были из очереди, мы не снять конец д. Мы хотим, чтобы с головы, верно? Так что в итоге, голова изменится, и поэтому, когда вы в очередь, Вы должны следить за где ваша голова и ваш размер должны иметь возможность вставить в правильное положение. 

И поэтому, когда вы из очереди, Я также псевдокод его. Не стесняйтесь, если вы хотите попытаться кодирования это. Вы хотите, чтобы переместить голову, верно? Если бы я хотел, чтобы из очереди, я будет двигаться голову над. Это будет голова. 

И наша текущий размер будет вычесть, потому что мы больше не четыре элемента в матрице. У нас есть только три, а потом мы хотим вернуться все было хранить внутри главы, потому что мы хотим, чтобы это Значение так, очень похожа на стек. Просто вы принимаете из другого места, и у вас есть, чтобы передать свою указатель в другом месте в качестве результата. Логично, каждый следовать? Отлично. 

ОК, так что мы собираемся немного поговорить более подробно о связанных списков потому что они очень, очень ценный для вас в ходе этой неделе psets. Связанные списки, как вы, ребята, помню, они все являются узлами, которые узлы уверен значения как значения и указатель которые связаны друг с другом по этим указателям. И поэтому от того, как структура мы создаем узел здесь мы есть Int N, который является то, что значение в магазине или струнного п или что вы хотите, чтобы это называют, полукокс звезда н. Структура, узел звезда, которая является указателем что вы хотите, чтобы в каждом узле, Вы будете иметь, что точка указатель к следующему. Вы будете иметь голову из связанного списка, что это собирается указывают на остальной значения так далее, и так далее пока вы в конечном итоге не дойдете до конца. И это последний узел просто происходит, чтобы не иметь указатель. Это будет указывать на NULL, и что, когда вы знаете, что ударил конец вашей связанного списка когда ваш последний указатель не указывает ни на что. 

Так что мы собираемся идти немного больше в Глубина о том, как одно, возможно, поиск связанный список. Помните, что некоторые из Недостатками связанных списков стихи массив относительно поисков. Массив можно бинарный поиск, но почему вы не можете сделать это в связанном списке? 

АУДИТОРИЯ: Потому что они все связаны, но вы совершенно не знаю, где [Неразборчиво]. 

ANDI Пэн: Да, именно так помню что блеск массива было то, что у нас было оперативное запоминающее устройство, где если бы я хотел значение из индекса шесть, я мог просто сказать индекс шесть, дайте мне это значение. И это потому, что массивы сортируются в непрерывном пространстве памяти в одном месте, в то время как вид связанных списков случайно перемежаются всему, и единственный способ вы можете найти один через указатель, который говорит вам, адрес, где, что в следующем узел. 

И так, в результате, единственный способ искать в связанном списке это линейный поиск. Потому что я точно не знаю, где 12-й значение в связанном списке, Я должен пройти полноту этого связанный список одного один от головы до первого узла, ко второму узлу, третьему узлу, весь путь вниз, пока я, наконец, не получают где этот узел, я смотрю на это. И поэтому в этом смысле, поиск на связанный список всегда п. Это всегда п. Это всегда в линейном времени. 

И поэтому код, в котором мы реализуем это, и это немного нового для вас, ребята, так как вы Ребята на самом деле не говорил о или когда-либо просмотрено указатели в том, как поиск с помощью указателей, таким образом, мы будем идти через это очень, очень медленно. Так поиск логический, право, давайте представим, что мы хотим создать функцию с именем Поиск, который возвращает истинное если вы нашли значение внутри связанный список, и возвращает ложное в противном случае. Узел звезда список В настоящее время только указатель к первому пункту в вашем связанного списка. INT п значение, что вы поиск в этом списке. 

Так узел звезда указатель равен список. Это означает, что мы устанавливаем и создание указатель к этому первому узлу внутри списка. Все со мной? Так что, если мы должны были пойти сюда, я бы инициализации указатель, который указывает на глава независимо, что список. 

И то, как только вы получите здесь, в то время как указатель не равен нулю, так что это петля, в которой мы будет впоследствии прохождения остальные нашем списке, потому что то, что происходит, когда указатель равен NULL? Мы знаем, что have-- 

АУДИТОРИЯ: [неразборчиво] 

ANDI Пэн: Ровно, поэтому мы знаем, что мы достигли конца списка, верно? Если вы идете сюда, каждый узел должен быть направлен на другой узел и так далее и тому подобное пока вы не нажмете в конечном итоге хвост вашего связанного списка, который имеет указатель, который просто не указывают, чем в любом другом нет. И так вы знаете, что в основном Ваш список есть еще до до указателя не делает не равны нуль, потому что когда-то он равен нулю, Вы знаете, что нет больше материала. 

Так что это петля, в которой мы будет иметь реальную поиска. И если pointer-- вы видите что вид функции стрелка там? Так что, если указатель указывает п, если указатель на п равен равен п, так, что означает, что если указатель, что вы поиске на конце каждого узел фактически равно значению Вы ищете, то Вы хотите, чтобы вернуться правда. Так в основном, если вы находитесь на узле, который имеет значение, что вы ищете, Вы знаете, что вы были в состоянии успешно искать. 

В противном случае, вы хотите установить указатель на следующий узел. Это то, что эта линия здесь делает. Указатель равна указатель рядом. Все видеть, как это работает? 

И по существу, вы собираетесь просто пройти полноту списка, сброс указатель каждый раз до Вы в конечном счете попал в конце списка. И вы не знаете, что есть не больше узлов для поиска по, а затем вы можете вернуться ложным потому что вы знаете, что, ну, хорошо, если я был в состоянии искать через полностью списка. Если в этом примере, если бы я хотел искать значения 10, и я начинаю в голове, и Я ищу всю дорогу вниз, и я в конце концов получил на это, что указатель, который указывает на NULL, Я знаю, что, дерьмо, я думаю, 10 не находится в этот список, потому что я не мог найти его. И я в конце списка. И в этом случае вы знаете, Я собираюсь вернуться ложным. 

Пусть это замочить в для немного. Это будет довольно важно для вашего PSET. Логика очень проста, возможно синтаксически только его реализации. Вы, ребята, хотите, чтобы Убедитесь, что вы понимаете. Круто. 

Итак, как мы бы вставки узлов, право, в списке, потому что помню, каковы то, что преимущества иметь связанный список против массив с точки зрения хранения? 

АУДИТОРИЯ: Это динамичный, так легче, целью которых 

ANDI Пэн: Ровно, так что это динамичный, который означает, что он может расширяться и сжиматься в зависимости от потребностей пользователя. И так, в этом смысле, мы не должны тратить ненужного память, потому что я если я не знаю, сколько я хочу значения в магазине, это не имеет смысла для меня создать массив, потому что если я хочу, чтобы хранить 10 значений и создать массив 1000, это много впустую память, выделено. Вот почему мы хотим использовать связанный Список, чтобы иметь возможность динамически изменить или уменьшить размер нашей. 

И так, что делает вставку немного более сложным. Поскольку мы не можем произвольно обращаться к элементам так, что мы массива. Если я хочу, чтобы вставить элемент в седьмой индекса, Я просто не могу вставить в седьмой индекса. На связанном списке, это не довольно легко работать, как, и поэтому, если мы хотели, чтобы вставить один здесь, в связанном списке, визуально, это очень легко увидеть. Мы просто хотим, чтобы вставить его прямо там, в самом начале списка, сразу после головы. 

Но то, каким образом мы должны переназначить указатели это немного запутанным или, по логике, это имеет смысл, но Вы хотите, чтобы убедиться, что у вас есть полностью вниз, потому что последнее, что вы хотите это переназначить указки так, что мы здесь делаем. Если вы разыменовать указатель с головы до 1, то все вдруг остальная часть вашего связанного списка теряется, потому что у вас есть на самом деле не создано временное ничего. Вот указал на 2. При передаче указателя, то Остальные свой список полностью потеряны. Итак, вы хотите быть очень, очень осторожны сначала назначить Указатель с какой вам вставить в там, где Вы хотите, и тогда вы может разыменовать остальной список. 

Таким образом, это относится и к везде, где Вы пытаетесь вставить в. Если вы хотите, чтобы вставить на голова, если вы хотите, чтобы ответить здесь, если вы хотите вставить в конец, ну, конец я думаю, вы бы просто нет указатель, но вы хотите, чтобы убедиться, что вы не потерять остальные вашего списка. Вы всегда хотите, чтобы убедиться, Ваш новый узел указывая к все, что вы вставить в, а затем вы можете добавить цепочку дальше. Все ясно? 

Это будет один из реальных проблем. Один из самых главных вопросов Вы будете иметь на вашем PSET является то, что вы собираетесь, чтобы попытаться создать связанный список и добавить вещи, но потом просто потерять остальная часть вашего связанного списка. И вы будете, как я Не знаю, почему это происходит? И это боль, чтобы пройти через и искать все ваши указатели. 

И я гарантирую вам на этом PSET, писать и рисовать эти узлы из будет очень, очень полезно. Таким образом, вы можете полностью отслеживать где все ваши указатели, что происходит не так, где все ваши узлы, то, что вы должны сделать, чтобы получить доступ к или вставить или удалить или любого из них. Все хорошо с этим? Круто. 

Так что, если мы хотели посмотреть на код? О, я не знаю, если мы можно увидеть the-- OK, так в верхней все это является функцией имени вставка, где мы хотим вставить Int N в связанном списке. Мы собираемся пройти через это. Это много кода, много нового синтаксиса. Мы в порядке. 

Так на вершине, когда мы хотим, чтобы создать что-нибудь что нам нужно сделать, особенно если вы Хотите его нельзя хранить в стеке но в куче? Мы идем в таНос, верно? Итак, мы собираемся создать указатель. Узел, указатель, новые равно таНос размер узла потому что мы хотим, что узел будет создан. Мы хотим, чтобы количество памяти, что узел занимает чтобы быть отведено для Создание нового узла. 

А потом мы собираемся, чтобы проверить, увидеть, если новые равно равна нулю. Помните, что мы говорили? Что бы вы ни таНос, Что необходимо всегда делать? Вы всегда должны проверить, чтобы увидеть или нет, что это NULL. 

Например, если ваша операционная система была полностью заполнена, если вы не имели больше памяти на все, и вы пытаетесь таНос, это вернется NULL для вас. И поэтому, если вы пытаетесь использовать его когда он был направлен на нуль, вы не собираетесь, чтобы в состоянии для доступа к этой информации. И так, как, например, мы хотели сделать Убедитесь, что всякий раз, когда вы mallocing, Вы всегда проверять, если что память дано вам является недействительным. А если это не так, то мы можем двигаться на с остальной частью нашего кода. 

Итак, мы собираемся, чтобы инициализировать новый узел. Мы собираемся сделать новый п равен п. И тогда мы будем делать установить новый указатель на новый в нуль, потому что сейчас мы не хочу что-нибудь для того, чтобы указать на. Мы не имеем ни малейшего понятия где он собирается поставить вас, а затем, если мы хотим, чтобы вставьте его в голове, то мы можем передать указатель на голову. Все следовать логике ли где, что происходит? 

Все, что мы делаем, создавая новый узел, установив указатель на NULL, а затем переназначение это в голове, если мы знаю, что мы хотим, чтобы вставить его в голову. А потом голова будет указывают на то нового узла. Все в порядке с этим? 

Так что это двухступенчатый процесс. Вы должны сначала назначить все, что вы создаёте. Установлено, что указатель на справка, а затем вам может рода разыменования первый указатель и указать его к новому узлу. Где вы хотите, чтобы вставить его, что логика собирается провести верно. 

Это вроде как присвоение временные переменные. Помните, у вас есть чтобы убедиться, что вас не терять, если вы подкачки. Вы хотите, чтобы убедиться, что у вас есть временная переменная, что вид сохраняет трек где этой вещи хранится, так что вы не теряют любое значение в ходе из, как возиться с ним. 

ОК, так что код будет здесь. Вы, ребята, взгляните после раздела. Это будет там. 

Так что я думаю, как делает это отличается, если мы хотели вставить в середине или в конце? Кто-нибудь есть идея о том, что это псевдокод, как логическое ссылкой что мы бы хотели, если мы чтобы вставить его в середине? Так что, если мы хотели, чтобы вставить ее на голова, все, что мы сделать, это создать новый узел. Мы устанавливаем указатель, что Новый узел какой голове, а затем мы устанавливаем голову с новым узлом, правильно? Если бы мы хотели, чтобы вставить его в середине из списка, что бы мы должны делать? 

АУДИТОРИЯ: Это будет по-прежнему быть аналогичный процесс из, как присвоение и указатель то назначение этого указателя, но мы должны найти там. 

ANDI Пэн: Ровно, так точно тот же самый процесс, кроме вас должны найти, где именно вы хочу, чтобы новый указатель, чтобы пойти в, так что если я хочу, чтобы вставить в середина связаны list-- ОК, давайте говорить, что наш связанный список. Если мы хотим, чтобы вставить ее прямо здесь, мы собираемся создать новый узел. Мы собираемся таНос. Мы собираемся создать новый узел. Мы собираемся назначить указатель этого узла здесь. 

Но проблема, которая отличается откуда голова является то, что мы точно знали, где голова. Это было прямо на первой, не так ли? Но здесь мы должны отслеживать где мы вставив его в. Если мы вставляем наш узел здесь, у нас есть чтобы убедиться, что одним предыдущая к этому узлу это тот, который присваивает указатель. Итак, вы должны вид отслеживать две вещи. Если вам отслеживать, где это узел в настоящее время вставки в. Вы также должны отслеживать, где предыдущий узел, который вы смотрите на Также там. Все хорошо с этим? ХОРОШО. 

Как насчет вставки в конце концов? Если бы я хотел, чтобы добавить его here-- если я хотел чтобы добавить новый узел в конец списка, как я мог бы идти о том, что делать? АУДИТОРИЯ: Так себе, то последний указали на нуль. ANDI Пэн: Да. Точно, так что это одно В настоящее время отмечается знать, и поэтому я думаю, в этом смысле, это очень легко добавить к концу списка. Все, что вам нужно сделать, это установить его равен нулю, а затем бум. Прямо там, очень легко. Очень просто. 

Очень похож на голову, но логически вас хотите, чтобы убедиться, что шаги, вы берете к делать все это, вы следуете. Это очень легко, в середине ваш код, увязнуть в, ой, у меня так много указателей. Я не знаю, где что-либо, указывая на. Я даже не знаю, какой узел я на. Что происходит? 

Расслабьтесь, успокойтесь, сделайте глубокий вдох. Нарисуйте свой связанный список. Если вы говорите, я знать, где именно Мне нужно вставить это в и я точно знаю, как передать мой указатели, гораздо, гораздо легче представить out-- гораздо проще не заблудиться в багов в коде. Все в порядке с этим? ХОРОШО. 

Поэтому я думаю, понятие, что мы не действительно говорили о до сих пор, и я думаю, вы, вероятно, не встретите много yet-- это своего рода передовой concept-- является то, что мы на самом деле есть данные Структура называется вдвойне связанный список. Итак, как вы, ребята, можете видеть, все, что мы делаем, создавая фактическое значение, дополнительный указатель на каждый из наших узлов что также указывает на предыдущий узел. Так мы не только имеем нашу узлы указывают на следующий. Они также указывают на предыдущий. Я собираюсь игнорировать эти два прямо сейчас. 

Итак у вас есть цепочка что может двигаться в обоих направлениях, и тогда это немного легче логически следовать. Как здесь, а отслеживания, о, я должны знать, что этот узел тот, который я должен передать, Я могу просто пойти здесь и просто вытащить предыдущий. Тогда я точно знаю, где то есть, а потом вас не должны пересекать Совокупность связанного списка. Это немного легче. 

Но таким образом, вы должны вдвойне количество указателей, это в два раза больше памяти. Это много указателей, чтобы отслеживать. Это немного более сложным, но это немного более дружественным к пользователю в зависимости о том, что вы пытаетесь достичь. 

Таким образом, это тип данных, Структура полностью существует, и структура для очень, очень просто, за исключением все, что вы имея это, а не просто указатель на следующий, у вас также есть указатель на предыдущий. Вот и вся разница была. Все хорошо с этим? Круто. 

Ладно, так что теперь я действительно потратить, наверное, как от 15 до 20 минут или навалом в остальное время в разделе говорить о хеш-таблицах. Как многие из вас, ребята, прочитал pset5 спецификации? Ладно, хорошо. Это выше, чем 50%, как правило. Это нормально. 

Итак, как вы, ребята, увидите, Вы задача в pset5 будет реализовать словарь где вы загрузить более 140000 слов что мы даем вам и проверка орфографии это против всего текста. Мы дадим вам случайных шт литературы. Мы дадим вам Одиссея. Мы дадим вам Илиаду. Мы дадим вам Остин Пауэрс. 

И ваша задача будет проверка орфографии каждое слово всего из тех словарей по существу, с нашей орфографии. И так есть несколько частей создания этой PSET, Сначала вы хотите быть в состоянии фактически загрузить все слова в ваш словарь, а затем вам хочу, чтобы иметь возможность орфографии и все из них. И так, как, например, вы собираетесь требовать структура данных, которая может сделать это быстро и эффективно и динамично. 

Поэтому я полагаю, самый простой способ сделать это, вам вероятно создать массив, верно? Самый простой способ хранения вас можно создать массив 140000 слов и просто разместить их там, и все затем пройти их бинарного поиска или выборов или не-- жаль, что это сортировка. Вы можете сортировать их, а затем пройти их двоичный поиск или просто линейный поиск и только окончательные слова, но занимает огромное количество памяти, и это не очень эффективно. 

И таким образом мы собираемся начать говорить о способах изготовления наша продолжительность более эффективным. И наша цель, чтобы получить постоянная времени, где это почти как массивы, где у вас есть мгновенный доступ. Если бы я хотел, чтобы искать что-нибудь, Я хочу, чтобы иметь возможность просто, бум, найти его точно, и вытащить его. И так структура, в которой мы будем становится очень близко чтобы быть в состоянии получить доступ к постоянным Время, это Святой Грааль в программировании постоянного время называется хеш-таблицы. И так Дэвид упоминалось ранее [Неразборчиво] немного в лекции, но мы собираемся, чтобы действительно погружение в глубокий этой неделе на кусок, который относительно как хэш-таблица работает. 

Так образом, что хэш таблица работы, например, если бы я хотел, чтобы сохранить кучу словами, куча слов в английском языке, Я теоретически может поместить банан, яблоко, киви, манго, пара, и дыня все только на массиве. Все они могли вписаться и быть найти. Это было бы своего рода боли поиск и доступ через, но простой способ сделать это состоит в что мы можем создать на самом деле структура называется хеш-таблица, где мы хэш. Мы бежим все наши ключи через хэш-функция, уравнение, Получается, что их все в какая-то ценность что тогда мы можем хранить на существу массив связанного списка. 

И вот, если мы хотим для хранения английские слова, мы могли потенциально просто, я не знаете, превратить все первые буквы в какой-то номер. И поэтому, например, если бы я хотел А быть синонимом apple-- или с индексом 0, а В синонимом 1, мы можем иметь 26 записей что может просто хранить все буквы алфавит, что мы начнем с. И тогда мы можем иметь яблоко на индексом 0. Мы можем иметь банан индекса 1, дыня в индексе 2, и так далее и тому подобное. И таким образом, если я хотел, чтобы поиск мой хэш-таблица и доступ яблоко, Я знаю, яблоко начинается с Л-и я точно знаю, что она должна быть и хэш Таблица с индексом 0, потому что функции, присвоенные. 

Так что я не знаю, мы программа пользователя, где Вы будете платить с arbitrarily-- не произвольно, в попытке задумчиво думать о хорошем уравнений чтобы иметь возможность распространяться все ваши значений таким образом, они могут легко получить доступ к это позже с как уравнения что вы, сами, знаете. Таким образом, в смысле, если я хотел, чтобы перейти к манго, я знаю, о, это начинается с м. Она должна быть в индексе 12. Я не придется искать во всем. Я знаю, exactly-- я мог бы просто пойти в индекс 12 и тянуть это. 

Все ясно, как Функция Hash Table работает? Это своего рода просто более сложный массив. Это все, что есть. ХОРОШО. 

Так что я думаю, что мы столкнулись с этот вопрос, что произойдет, если у вас есть несколько вещей, которые дают вам тот же индекс? Так сказать, нашу функцию, все это сделал считать, что первое письмо и превратить это в Соответствующий 0 до 25 Индекс. Это совершенно нормально, если есть только один из каждого. Но второй вы начинаете имеющие более, вы будет иметь то, что называется столкновение. 

Так что, если я пытаюсь вставить похоронить в хэш таблица, уже банан на нем, что произойдет, когда Вы пытаетесь вставить, что? Плохие вещи, потому что банан уже существует в индексе что вы хотите, чтобы хранить его в. Берри рода, как, ах, что же мне делать? Я не знаю, куда идти. Как решить эту проблему? 

И так вы, ребята, будет своего рода видеть, что мы делаем это сложная вещь где мы можем на самом деле вид создать связанный список в наших массивов. И так самый простой способ думать об этом, все хэш-таблицы является массив связанных списков. И так, в этом смысле, у вас есть Этот красивый массив указателей, а затем каждый указатель в что значение, в этом индексе, может на самом деле указывать на другие вещи. И так у вас есть все эти отдельные цепи сходит одном большом массиве. 

И вот, если я хотел вставить ягоду, Я знаю, ладно, я собираюсь ввести это через мой хэш-функции. Я собираюсь закончить с индексом 1, а затем я собираюсь быть в состоянии иметь просто меньше подмножество этого гигант словарь 140,000 слово. И тогда я могу просто посмотреть через 1/26, что. 

И так, то я могу просто вставить ягоды либо до, либо после того, как банан в этом случае? После, правда? И так вы будете хотеть, чтобы вставить этот узел после банана, и таким образом Вы собираетесь вставить в хвосте этой связанного списка. Я собираюсь вернуться в этом предыдущем слайде, так что вы, ребята, можете увидеть, как Хэш функция работает. 

Так хэш функция это уравнение что вы работаете вид вашего входа через, чтобы получить все индекс Вы хотите, чтобы назначить его к. И так, в этом примере, все мы хотели нужно было взять первую букву, свою очередь, что в индекс, то может хранить, что в нашей хэш-функции. Все, что мы делаем здесь мы преобразовании первую букву. Так KeyKey [0] только первая буква всего, что строка мы с, мы передаем в. Мы преобразования, что верхний и мы вычитая заглавными А, поэтому все, что делает дает нам ряд в которых мы можем хэш наши ценности на. 

А потом мы собираемся вернуться хэш модуль РАЗМЕР. Будьте очень, очень осторожны, потому, теоретически, здесь Ваш хэш-значение может быть бесконечным. Это может быть просто пойти дальше и дальше и дальше. Это может быть некоторые действительно, действительно большое значение, а потому, что ваш хэш-таблицы, что Вы создали только имеет 26 индексов, Вы хотите, чтобы убедиться, что ваш modulusing, так что вы не run-- это то же самое что в качестве queue-- так что вы не сошли с Дно Вашей хэш-функции. 

Вы хотите, чтобы обернуть его назад вокруг так же, как в [неразборчиво], когда у вас, как очень, очень большая буква, вы не хочу, чтобы просто бежать конец. То же самое здесь, вы хотите, чтобы убедиться, что он не работает с конца, накладываясь вокруг верхней части таблицы. Так что это просто очень просто хэш функция. Все, что сделал первый взять Письмо какой нашем входе был и превратить это в индекс, мы могли бы поставить в нашу хэш-таблицы. 

Да, и так, как я сказал раньше, так, что мы разрешения коллизий в нашей хэш таблицы, имеющие, что мы называем, цепочки. Так что, если вы пытаетесь вставить несколько слова, которые начинаются с той же вещи, Вы будете иметь один хэш-значение. Авокадо и яблоко, если у Вас есть запустить его через нашу хэш-функции, собираются, чтобы дать вам такое же количество, количество 0. И так как мы решить это что мы можем на самом деле вид связать их вместе с помощью связанных списков. 

И поэтому в этом смысле, вы, ребята, можете увидеть вид как структуры данных, мы были настройки, ранее как изюм связаны список рода из можете прийти вместе в один. И тогда вы можете создать еще более эффективные структуры данных которые могут обрабатывать большие объемы Данные, которые динамически изменять размер в зависимости от ваших потребностей. Все ясно? Все вроде ясно, на то, что происходит здесь? 

Если бы я хотел, чтобы insert--, что это фрукты, который начинается с, я не знаю B, кроме ягод, банан. 

АУДИТОРИЯ: Ежевика. 

ANDI Пэн: Blackberry, ежевика. Где ежевики идти сюда? Ну, мы на самом деле не сортируются это еще, но теоретически если бы мы хотели, чтобы это в алфавитном порядке, где должны BlackBerry идти? 

АУДИТОРИЯ: [неразборчиво] 

ANDI Пэн: Ровно, после здесь, верно? Но так как это очень сложно reorder-- Я думаю, это до вас, ребята. Вы, ребята, можете полностью осуществить все, что вы хотите. Чем больше эффективный способ делать это, возможно, будет сортировать ваш связан список в алфавитном порядке, и поэтому, когда вы вставки вещи, вы хотите чтобы убедиться, что вставить их в алфавитном порядке так что потом, когда вы пытаются искать их, Вы не должны пройти все. Вы точно знаете, где она есть, и это проще. 

Но если вы вроде есть вещи перемежаются случайно, Вы по-прежнему будете иметь пройти его в любом случае. И поэтому, если я хотел, чтобы просто вставьте ежевики здесь и я хотел, чтобы искать это, знаю, ох, ежевика должны начать с индексом 1, так что я знаю, мгновенно просто искать на 1. И тогда я могу рода пройти связанный список пока я не получить к BlackBerry, и then-- да? 

АУДИТОРИЯ: Если вы пытаетесь create-- Я думаю, как это очень простой хэш функция. И если мы хотим, чтобы сделать несколько слоев, что, как, ОК, мы хотим, чтобы отделить в как и все алфавитно а потом снова хотел другой набор из букв алфавита в течение, что, мы положить как хэш таблица в хэш-таблице, или как функции внутри функции? Или that-- 

ANDI Пэн: Так ваш хэш function-- свой хэш-таблицу может быть как большой, как вы хотите. Таким образом, в этом смысле, я думал, это было очень легко, очень просто для меня, чтобы просто вроде основе на буквы первого слова. И так есть только 26 вариантов. Я могу получить только 26 вариантов из 0 до 25, потому что они могут только начать от А до Z. Но если вы хотите добавить, пожалуй, больше сложности или быстрее бежать к вашему времени хеш-таблица, вы абсолютно может сделать все виды вещей. Вы можете сделать свой собственный Уравнение, которое дает вам более рассылки в слов, то при поиске, это будет быстрее. 

Это полностью зависит от вас, ребята как вы хотите, чтобы осуществить это. Думайте об этом как только ведрами. Если бы я хотел, чтобы иметь 26 ведра, я собираюсь сортировать вещи в этих ведрах. Но я собираюсь иметь кучу вещи в каждом ведре, так что если вы хотите, чтобы сделать его быстрее и эффективнее, дайте мне сто ведер. 

Но тогда вы должны выяснить способ сортировки вещи так, чтобы они в надлежащем ведро они должны быть в. Но потом, когда вы на самом деле хочу посмотреть на этого ведра, это намного быстрее, потому что есть меньше вещи в каждом ведре. И так, да, это на самом деле трюк для вас, ребята в pset5 является то, что вы будете вызов просто создать все, что является наиболее эффективным Функция Вы можете думать, чтобы быть возможность хранения и проверки этих значений. 

Всего до вас, ребята Однако вы хотите, чтобы это сделать, но это действительно хорошая точка. То, что такая логика вы хочу, чтобы начать думать о , ну, почему я не сделать больше ведра. И тогда я должен искать меньше вещей, и тогда, возможно, я имеют различную хэш-функцию. 

Да, есть много способов сделать это PSET, некоторые быстрее, чем другие. Я полностью собираюсь просто посмотреть, как быстро стал самым быстрым вы, ребята, быть в состоянии получить ваши функции на работу. ОК, все хорошо на Иерархии серверов и хэш-таблицы? Это на самом деле, как очень простой понятие, если вы думаете об этом. Все это является разделение все Ваши входы в ведра, сортируя их, а затем ищут в список, что там связано с. 

Круто. Ладно, теперь у нас есть разного рода структуры данных, которая называется деревом. Давайте идти дальше и говорить о попытках которые существенно отличаются, но в той же категории. По сути, все дерево вместо этого организации данных в линейном образом что хэш-таблица does-- вас Знаете, он получил верх и низ а затем вы вроде ссылаются прочь it-- в Дерево имеет верхний, что вы называете корень, и то он имеет листья все вокруг него. 

А так все у вас здесь это только верхний узел который указывает на другие узлы, что точки чтобы более узлов, и так далее и тому подобное. И так вы просто расщепление ветвей. Это просто другой способ организации Данные, и потому что мы называем это дерево, вы, ребята, просто-- это просто моделируется, чтобы смотреть, как дерево. Вот почему мы называем его деревья. 

Хэш таблица выглядит как таблица. Дерево выглядит как дерево. Все это является отдельным способ организации узлов в зависимости от того, что ваши потребности. 

Так у вас есть корни и то у вас есть листья. Таким образом, что мы можем особенно думаю о нем бинарное дерево, бинарное дерево просто Конкретный тип дерева где каждый узел только точки чтобы, при макс, два других узлов. И вот у вас есть отличный Симметрия в дереве что делает его легче своего рода выглядеть на какие ценности вы, потому что тогда вы всегда слева или право. Там никогда не как левой трети от левая или четвертый слева. Это просто у вас есть левый и правый и вы можете искать либо из этих двух. И так, почему это полезно? Таким образом, что это полезна, если вы ищете искать через значения, верно? Вместо реализации двоичный поиск в массиве ошибок, если вы хотите, чтобы иметь возможность вставить узлы и забрать узлы по желанию, а также сохранить поиск мощности двоичного поиска. Таким образом, в этом случае, мы вроде tricking-- помню, когда мы сказал связанные списки не могут бинарный поиск? Мы вроде создания структуры данных что приемы, которые в рабочее. 

И это потому, что связанные списки являются линейными, они только ссылаются один за другим. Мы можем иметь вид разного рода указателей которые указывают на разных узлах что может помочь нам в поиске. И вот, если бы я хотел, чтобы есть дерево двоичного поиска, Я знаю, что моего середине, если 55 лет. Я просто хочу, чтобы создать что как мой середине, как мой корень, и тогда я буду иметь Значения выделении из него. 

Так вот, если я собираюсь искать значение 66, я могу начать в 55 лет. Это больше, чем 66 55? Да, это, так что я знаю, что я муз поиск я н право указатель этого дерева. Я иду до 77. ОК, это меньше, чем 66 или больше, чем 77? Это меньше, чем, так что вы знаете, о, который должен быть слева узел. 

И вот мы вроде сохранения все великие вещи о массивах, так как динамическое изменение размера объектов, будучи возможность вставлять и удалять по желанию, без того, чтобы беспокоиться о фиксированной объем пространства. Мы по-прежнему сохраняют все эти замечательные вещи в то же время быть в состоянии сохранить войти и поиск время бинарного поиска что мы были только ранее возможность получить фразу. 

Прохладный структура данных, вроде Комплекс для реализации, узел. Как вы можете видеть, все это это структура узла является то, что у вас есть левый и право указателем. Это все, что есть. Таким образом, вместо просто имеющий х или предыдущий. Вы должны налево или направо, а затем Вы можете вид связать их вместе Однако вы того пожелаете. 

Хорошо, мы на самом деле происходит просто взять несколько минут. Итак, мы собираемся, чтобы вернуться сюда. Как я уже говорил, Я вроде пояснил логика, как мы будет искать через это. Мы собираемся, чтобы попытаться pseudocoding этот, чтобы увидеть если мы можем рода применить Та же логика бинарного поиска на другой тип структуры данных. Если вы, ребята, хотите, чтобы принять как пара минут, чтобы просто думать об этом. ХОРОШО. Ладно, я собираюсь на самом деле просто не даст вам the-- нет, мы будем говорить о псевдокоде первым. Так кто-нибудь хочет дать удар на то, что первое, что вы хотите делать, когда Вы начинаете поиск по? Если мы ищем значение 66, что Первое, что мы хотим делать, если мы хотим, чтобы этот бинарный поиск дерево? 

АУДИТОРИЯ: Вы хотите, чтобы смотреть прямо и посмотрите налево и увидите [неразборчиво] большее число. 

ANDI Пэн: Да, именно так. Таким образом, вы будете смотреть на корне. Там много способов вы можете позвонить это, ваши родитель узла люди говорят. Я хотел бы сказать, потому что корень это как корень дерева. Вы собираетесь смотреть на Ваш корневой узел, и вы увидите 66 больше или меньше, чем 55. И если это больше, чем, ну, это больше, чем, где мы хотим, чтобы посмотреть? Куда мы хотим искать сейчас, правда? Мы хотим, чтобы поиск в Правая половина этого дерева. 

Итак, мы имеем, удобно, А указатель, который указывает на право. И так, то мы можем установить наш новый корень, чтобы быть 77. Мы можем просто пойти туда, где указатель указывает. Ну, ну, здесь мы начинаем на 77, и мы можем только сделать это рекурсивно снова и снова. Таким образом, вы вроде от того, имеют функцию. У вас есть способ поиска, что вы можно просто повторять снова и снова и снова, в зависимости от того, где вы хотите, чтобы посмотреть пока вы в конечном итоге не получить к значению что вы ищете. Сделайте чувство? 

Я собираюсь показать Вам фактический Код, и это много кода. Нет необходимости волноваться. Мы будем говорить через него. 

Вообще-то, нет. Это было просто псевдокод. ОК, это было просто псевдокод, который является немного сложным, но это совершенно нормально. Каждый следующий по здесь? Если корень нуль, возвращение ложь, потому что это означает, что Вы даже не имеют ничего там. 

Если корень п значение, поэтому, если он случается, тот, который вы смотрите, то вы будете возвращаться правда потому что вы знаете вы его нашли. Но если значение меньше чем корень п, вы будет искать левого ребенок или левая лист, все, что вы хотите назвать это. И если значение больше, чем корень, Вы собираетесь искать нужное дерево, Затем просто запустите функцию через поиск снова. 

А если корень пустой, что это означает, что вы дошли до конца? Это означает, что у вас есть не более больше листьев для поиска, то вы знаете, о, я думаю, это не здесь потому что после того как я посмотрел через все это, и это не здесь, он просто не может быть здесь. 

Имеет ли это смысл для всех? Так как бинарный поиск, сохраняющих Возможности связанных списков. Холодный, и так второй тип структуры данных вы, ребята может попробовать реализовать на PSET, у вас есть только один способ выбрать. Но, возможно, альтернативный метод хэш-таблица является то, что мы называем синтаксического дерева. 

Все, Trie это является Конкретный тип дерева, имеет значения, которые выходят на другие значения. Таким образом, вместо того, двоичный дерево в том смысле, что только один что может указывать на двоих, вы можете иметь Одно дело точка многих, многих вещей. Вы по существу есть массивы внутри которого вы храните указатели, которые указывают на другие массивы. 

Таким образом, узел, как мы будет определять синтаксического дерева что мы хотим, чтобы иметь Логическое, с слово, верно? Таким образом, узел Логический как истинное или ложное, в первую очередь в голову что массив, это слово? Во-вторых, вы хотите, чтобы указатели к тому, что остальные из них. Немного сложный, немного абстрактно, но Я объясню, что это все средства. 

Так вот, в верхней, если вы есть массив, объявленный уже узел, где у вас есть логическое Значение, сохраненное в передней что говорит вам это слово? Разве это не слово? И тогда у вас есть Остальные массиве, что на самом деле хранит все Возможности, что это может быть. Так, например, как в верхней вас есть Первое, что говорит правда или ложь, да или нет, это слово. 

И тогда у вас есть от 0 до 26 письма, которые вы можете хранить. Если бы я хотел, чтобы поиск для летучей мыши, я иду к вершине и я смотрю на В. Я нахожу в моем B массив, так что я знаю, хорошо, это B слово? В это не то слово, так, таким образом, Я должен продолжать поиски. Я иду от B, и я с нетерпением к указатель, который указывает на B и я вижу еще один массив информации, та же структура, что у нас было раньше. 

И here-- ой, следующий Письмо в [неразборчиво] это А. Таким образом, мы с нетерпением в этом массиве. Мы находим восьмой значение, и тогда мы посмотрите, ох, эй, это то, что словом, это В-А слово? Это не слова. Мы должны продолжать поиски. 

И так, то мы смотрим, где указатель А точек, и это указывает на один способ, которые у нас есть больше значения сохраняются. И в конце концов, мы получаем В-А-Т, которая является слово. И поэтому в следующий раз Вы посмотрите, что вы собираетесь иметь, что проверку, да, это булева функция является правдой. И так в том смысле, мы вроде наличия дерево с массивами. 

Так, то вы можете рода поиск вниз. Вместо того, чтобы хэширования функцию и присвоение значения, связанного списка, вы можете просто реализовать Trie, что поиск downwords. Действительно, действительно сложной вещи. Не легко думать о, потому что я, как плевки так много структур данных из у вас, но делает все рода понять, как логика это работает? 

Ладно, круто. Так B-A-T, а затем Вы собираетесь искать. В следующий раз вы собираетесь чтобы видеть, о, эй, это правда, Таким образом, я знаю, что это должно быть слово. 

То же самое для зоопарка. Так вот в чем дело прямо сейчас, если мы хотел искать зоопарке, прямо сейчас, В настоящее время зоопарк не слово в нашем словаре потому что, как вы, ребята, можете видеть, Первое место, что мы имеем логическое возвращает истину в конце масштабирования. У нас есть Z-O-O-M. 

И вот, мы на самом деле не имеют слово, зоопарк, в нашем словаре потому что этот флажок не установлен. Таким образом, компьютер не знаю, что зоопарк это слово потому что путь, который мы хранить его, только зум здесь на самом деле имеет логическое значение который был превращен правда. Так что, если мы хотим, чтобы вставить Слово, зоопарк, в нашем словаре, как бы мы идти о том, что делать? Что мы должны сделать, чтобы убедиться, что наши компьютер знает, что Z-О-О слово а не первое слово Z-О-О-М? 

АУДИТОРИЯ: [неразборчиво] 

ANDI Пэн: Ровно, мы хотите, чтобы убедиться, что это вот, что Логическое значение галочка, что это правда. Z-О-О, то мы собираемся проверить, что так мы точно знаем, эй, зоопарк является слово. Я собираюсь рассказать компьютер, что это слово так что, когда компьютер проверяет, он знает, что зоопарк это слово. 

Потому что помню все эти данные структуры, это очень легко для нас сказать, ой, летучая мышь это слово. Зоопарк это слово. Увеличить это слово. Но когда вы строите его, компьютер не имеет понятия. 

Таким образом, вы должны сказать это точно в какой момент это слово? В какой момент это не слово? И в какой момент я нужно искать вещи, и в какой момент мне нужно идти дальше? Все ясно, из этого? Круто. 

И так потом приходит Проблема как бы мы идти о вставке то что на самом деле нет? Так что давайте просто сказать, что мы хотим, чтобы вставить слово, ванна, в нашей синтаксического дерева. Как вы, ребята, можете увидеть, как в настоящее время все, что мы имеем сейчас, это В-А-Т, и эта новая структура данных есть имел пинту, что указал на нуль, потому что мы считаем, что, ох, нет никаких слов, после B-A-T, почему мы должны держать имея вещи после этого Т. 

Но проблема возникает, если мы делаем вам хотите иметь слово, которое приходит после Т-х. Если у вас есть ванна, вы собирается хотите H права. И так как мы собираемся сделать это мы собираемся создать отдельный узел. Мы не выделить любую сумму памяти для этой новой массива, и мы собираемся переназначить указатели. 

Мы собираемся назначить Н, В первую очередь, это нулевой, мы собираемся избавиться. Мы собираемся, чтобы иметь Н точка вниз. Если мы видим H, мы хотим его идти куда-то еще. 

Здесь, мы можем проверить с да. Если мы попали в H после Т, о, то мы знаем, что это слово. Логическое собирается вернуться правда. Все ясно, как это произошло? ХОРОШО. 

Так, по существу, все эти структуры данных что мы перешли сегодня, у меня пошел на них очень, очень быстро а не в гораздо подробно, и это нормально. Как только вы начинаете возиться с ним, вы будете отслеживать, где все указатели, что происходит в вашей структуры данных, и так далее. Они будут очень полезны, и это до вас, ребята, чтобы полностью понять, как вы хотите реализовать вещи. 

И так pset4, из 5-- ой, что это неправильно. Pset5 является опечатками. Как я уже говорил раньше, вы будете, когда-то снова, скачать исходный код из нас. Там будет три основных вещи, которые вы будете загружать. Вы скачать словари, KERS, и тексты. 

Все эти вещи являются либо словари слов что мы хотим, чтобы вы проверить или испытание информации что мы хотим, чтобы вы проверка орфографии. И так словари мы даем вам собираемся чтобы дать вам конкретные слова, которые мы хотим хранить как-то в способе, которым это более эффективным, чем массив. И тогда тексты будет то, что мы прошу вас проверить правописание, чтобы убедиться, все слова есть реальные слова. 

И так три блока программы, которые мы дадим вам называются dictionary.c, dictionary.h и speller.c. А так все делает, dictionary.c то, что вы просили реализовать. Он загружает слова. Это заклинание проверяет их, и это гарантирует, что все правильно вставлен. 

diction.h это просто файл библиотеки который объявляет все эти функции. И speller.c, мы собираемся дать вам. Вам не нужно изменять любой из него. Все speller.c делает это принять, что загружает его, проверяет скорость его, тестирует отметку в вроде как быстро вы сможете сделать вещи. 

Это пишущий. Только не связывайтесь с ним, но сделать что вы понимаете, что он делает. Мы используем функцию под названием getrusage, что тестирует производительность вашего заклинания проверки. Все это делает в основном протестировать Время все в словаре, поэтому убедитесь, что вы понимаете, что. Будьте осторожны, чтобы не связываться с ним или остальное все не будет работать должным образом. 

И большая часть этой проблемы является для вы, ребята, действительно изменить dictionary.c. Мы собираемся дать вам 140000 слов в словаре. Мы собираемся дать вам текст файл, который имеет те слова, и мы хотим, чтобы вы могли организовать их в хэш-таблице или синтаксического дерева потому что, когда мы просим вас заклинание check-- представьте себе, если вы заклинание проверки, как Одиссея Гомера. Это как этого огромной, огромной теста. 

Представьте себе, если каждый Слово, которое вы должны были искать через массив 140000 значений. Это будет длиться вечно для вашей машины, чтобы бежать. Именно поэтому мы хотим, чтобы организовать наши данные в более эффективных структур данных таких как хэш-таблицы или синтаксического дерева. И тогда вы, ребята, можете вид когда вы искать доступ вещи более легко и более быстро. 

И поэтому будьте осторожны, чтобы решить столкновений. Вы собираетесь получить кучу слов, которые начинаются с А. Вы собираетесь получить кучу слов которые начинаются с В. до вас ребята, как вы хотите, чтобы решить ее. Может быть, есть более эффективность хэш-функция чем просто первой букве и то, и так, что до вас ребята вроде делать все, что вы хотите. 

Может быть, вы хотите, чтобы добавить все буквы вместе. Может быть, вы хотите, чтобы сделать нравится странные вещи к ответственности ряд писем, без разницы. До вас, ребята, как вы хотите сделать. Если вы хотите сделать хэш-таблицу, если вы хочу попробовать синтаксического дерева, полностью зависит от вас. Я предупреждаю вас заранее, что Trie, как правило, немного сложнее только потому, что есть много больше указатели отслеживать. Но полностью до вас, ребята. Это гораздо более эффективно, в большинстве случаев. Вы хотите, чтобы действительно быть в состоянии держать трек всех ваших указателей. Как сделать то же самое что я здесь делаю. Когда вы пытаетесь вставить значения в хэш-таблицу или удалить, убедитесь, что вы действительно отслеживания где все, потому что это действительно легко, если я пытаюсь вставить, как слово, Энди. Давайте просто скажем, что это реальное слово, слово, Энди, в гигантский список из слов. 

Если я просто случайно переназначить указатель так, ой, там идет полноту остальные моего связанного списка. Теперь единственное слово я есть Энди, и в настоящее время все Другими словами в Словари были потеряны. И поэтому вы хотите, чтобы убедиться, что вы отслеживать все ваши указатели иначе вы собираетесь получить огромные проблемы в коде. Нарисуйте вещи тщательно, шаг за шагом. Это делает его гораздо легче думать. 

И, наконец, вы хотите, чтобы иметь возможность проверить производительность вашей программы на большой доске. Если вы, ребята, взять посмотреть на CS50 прямо сейчас, у нас есть то, что называется большой совет. Это оценка лист самый быстрый Проверка орфографии раз по всем CS50 Прямо сейчас, я думаю, что верх как 10 Я думаю, что раз восемь из них являются сотрудниками. Мы действительно хочу вас, ребята, чтобы бить нас. 

Все из нас пытались реализовать быстрый код, насколько это возможно. Мы хотим, чтобы вы, ребята, чтобы попытаться оспорить нам и осуществить быстрее, чем всех нас Можно. И так это действительно первый раз, что мы прошу вас, ребята, чтобы сделать PSET, что Вы действительно можете сделать в любой метод вы хотите. 

Я всегда говорю, что это больше похоже к решению реальных, верно? Я говорю, эй, ты мне нужен, чтобы сделать это. Построить программу, которая делает это для меня. Сделайте это, как вы. Я просто знаю, что я хочу, чтобы поститься. Это ваша задача на этой неделе. Вы, ребята, мы идем чтобы дать вам задание. Мы собираемся дать вам вызов. И тогда это до вас, ребята полностью только выяснить что самый быстрый и самый эффективный способ осуществить это. Да? 

АУДИТОРИЯ: Мы позволили, если хотел исследовать быстрые способы сделать хеш-таблицы на сайте, мы можем сделать что и цитировать код чужое? ANDI Пэн: Да, совершенно нормально. Так что, если вы, ребята, читать спецификации, есть линия в спецификации сказано, что вы, ребята полностью свободны исследовать хэш функции на то, что некоторые из быстрых хэш-функций вести дела через в Пока вы привести этот код. Таким образом, некоторые люди уже выяснили быстрых способов делать проверку орфографии, быстрого способы хранения информации. Всего до вас, ребята, если вам хочу просто взять, да? Убедитесь, что вы цитирования. Задача здесь действительно что мы пытаемся проверить убедившись, что вы знаете, Ваш путь вокруг указатели. Как далеко, как вы реализации фактический хэш-функция и, подойдя с подобным математика, чтобы сделать это, вы, ребята, можете исследовать все методы онлайн вы, ребята, хотите. Да? 

АУДИТОРИЯ: Можем ли мы Приведу лишь с помощью [неразборчиво]? 

ANDI Пэн: Да. Вы можете просто в свой комментарий, Вы можете цитировать, как, ну, взяты из болтовня, болтовня, йада, хэш-функция. Кто-нибудь есть какие-либо вопросы? Мы на самом деле веял через раздел и сегодня. Я буду сюда, чтобы ответить на вопросы, а также. 

Кроме того, как я сказал, офис часов сегодня вечером и завтра. Спецификация этой неделе на самом деле супер просто и супер короткие читать. Я хотел бы предложить взглянуть, просто прочитать полностью от него. 

И на самом деле Zamyla проведет вас через каждую из функций необходимо реализовать, и поэтому очень, очень ясно, как все. Просто убедитесь, что вы отслеживание указателей. Это очень сложная PSET. 

Это не вызов, потому что, как, о, понятия гораздо больше трудно, или у вас есть, чтобы узнать, столько нового синтаксиса путь что вы сделали за последний PSET. Это PSET трудно, потому что Есть так много указателей, и то это очень, очень легко сразу у вас есть ошибка в коде не сможет чтобы найти, где что ошибка есть. 

И так полное и абсолютное вера в вас ребята, чтобы иметь возможность победить нашу [неразборчиво] Написание. Я на самом деле не какой-либо письменное шахту пока нет, но я собираюсь написать мой. Поэтому, когда вы пишете твое, я буду писать мои. Я собираюсь попытаться сделать мой быстрее, чем ваша. Мы увидим, кто имеет самый быстрый один. 

И да, я буду видеть все вы, ребята, здесь во вторник. Я побегу вид вроде мастерской Pset. Все это разделах неделе, Pset семинары, так что вы, ребята, есть много возможностей за помощью, часы работы, как всегда, и я действительно с нетерпением жду читать весь код ваши ребята. У меня есть тесты здесь если вы ребята, хотите приехать получить те. Вот и все.