Джейсон Хиршхорн: Приветствую всех в разделе Seven. Мы находимся в неделю семь курса. И предстоящий четверг Хэллоуин, так что я одеты как тыква. Я не мог наклониться и положить на мои ботинки, так вот почему я просто носить носки. Я также ничего не носить под это, поэтому я не могу снять его, если это отвлекая к вам. Заранее прошу прощения за это. Вам не нужно представить что происходит. Я ношу боксеров. Так что все хорошо. У меня есть длинный рассказ о том, почему я одет как тыквы, но я собираюсь кроме того, что позднее в этом разделе потому что я хочу, чтобы начать работу. У нас есть много интересных вещей, перейти на этой неделе. Большинство из них имеют непосредственное отношение к этому неделе проблема набор, опечатками. Мы собираемся идти по связаны списки и хэш-таблицы для всей секции. Я положил этот список каждую неделю, список ресурсы для вас, чтобы помочь вам материал на этом курсе. Если в убыток или если завожусь больше информации, проверить один из эти ресурсы. Опять же, pset6 является опечатками, PSET на этой неделе. И это также призывает вас, и я рекомендуем вам, чтобы использовать некоторые другие ресурсы специально для этой PSet. В частности, три у меня есть перечислены на экране - GDB, который мы были знакомы с и использовали на некоторое время теперь, является будет очень полезно на этой неделе. Так что я положил, что здесь. Но всякий раз, когда вы работаете с C, вы всегда должны использовать GDB для отладки программ. На этой неделе также Valgrind. Кто-нибудь знает, что Valgrind делает? АУДИТОРИЯ: Он проверяет утечек памяти? Джейсон Хиршхорн: Valgrind проверяет утечки памяти. Так что если вы таНос что-то в вашем Программа, вы просите памяти. В конце программы, у вас есть написать бесплатно на все, что вы malloced дать память обратно. Если вы не пишете бесплатно в конце и ваша программа приходит к выводу, все автоматически быть освобождены. А для небольших программ, это не так уж страшно. Но если вы пишете длинный ход программа, которая не выйдет, обязательно, в течение нескольких минут или пару секунд, затем утечки памяти может стать огромная сделка. Таким образом, для pset6, ожидается, что вы будете иметь утечек нулевые памяти с ваша программа. Для проверки утечки памяти, запустите Valgrind и она будет давать вам некоторые интересные Выход давая вам знать ли или не все было бесплатно. Мы будем практиковать с этим позже сегодня, с надеждой. Наконец, команда разн.. Вы что-то похожее на него используется в pset5 с инструментом быстрого взгляда. Разрешено вам заглянуть внутрь. Вы также используется дифференциал тоже за проблема установить спец. Но в позволил вам сравнения двух файлов. Вы можете сравнить файл растрового изображения и Информация заголовки раствора персонала и Ваше решение в pset5 если вы решили использовать его. Разница позволит вам сделать это, а также. Вы можете сравнить правильный ответ для Проблема этой неделе установить на свой ответ и посмотреть, если он выстраивается в линию или см. где ошибки. Итак, это три хороших инструментов, которые Вы должны использовать в течение этой недели, и обязательно проверить вашу программу с этими тремя инструментами перед включением его дюйма Опять же, как я уже упоминал каждую неделю, если у вас есть обратная связь для меня - как позитивным и конструктивным - не стесняйтесь, чтобы возглавить на сайт в нижней части этого слайда и ввести его там. Я очень ценю любое и все с обратной связью. И если вы дадите мне конкретные вещи, которые Что я могу сделать, чтобы улучшить или, что я все хорошо, что вы хотели, чтобы я продолжить, я беру это близко к сердцу и действительно очень стараются слушать ваши отзывы. Я не могу пообещать, что я собираюсь сделать все, хотя, как носить тыква костюм каждую неделю. Итак, мы собираемся провести большую часть раздел, как я уже говорил, речь идет о связанные списки и хэш-таблицы, которые будет непосредственно применимы к Проблема установить на этой неделе. Связанные списки мы пойдем на относительно быстро, потому что мы потратили справедливый бит времени собирается над ней в разделе. И поэтому мы получить прямо в кодирования проблемы для связанных списков. А потом в конце мы поговорим о хеши и как они применяются к этому Проблема неделе установить. Вы видели этот код раньше. Это структура, и это определение что-то новое называется узлом. А внутри узла существует целое прямо здесь и есть указатель на другой узел. Мы видели это прежде. Это было придумывать для пару недель сейчас. Она сочетает в себе указатели, которые мы посещали работы с, и структуры, которые позволяют нам объединить два различных вещи в один тип данных. Там очень много происходит на экране. Но все это должно быть относительно знакомы с вами. На первой линии, мы объявить новый узел. А потом внутри этой нового узла, я поставил целое число в этом узле к одному. Мы видим, на следующей строке я делаю Е команда, но я серым цветом команда Е, потому что на самом деле Важной частью является эта линия здесь - new_node.n. Что точка в виду? АУДИТОРИЯ: Перейдите в узел и оценить стоимость н для него. Джейсон Хиршхорн: Это Совершенно верно. Dot означает перехода к северная часть этого нового узла. В следующей строке что делает? Майкл. АУДИТОРИЯ: Создается еще один узел что будет указывать на новый узел. Джейсон Хиршхорн: Так это не создать новый узел. Он создает то, что? АУДИТОРИЯ: Указатель. Джейсон Хиршхорн: указатель на узел, как указано этом узел * здесь. Таким образом, это создает указатель на узел. И какой узел он указывая чтобы, Майкл? АУДИТОРИЯ: Новый узел? Джейсон Хиршхорн: Новый узел. И это указывает там, потому что мы дал ему адрес нового узла. И теперь в этой линии мы видим два различных способа выражая то же самое. И я хотел бы отметить, как эти две вещи одинаковы. В первой строке мы разыменовать указатель. Так мы идем к узлу. Это то, что эта звезда означает. Мы видели, что перед с указателями. К этому узлу. Вот в скобках. А потом доступ через оператора точки н элементом этого узла. Так что берет синтаксис мы увидели прямо здесь и сейчас использовать его с указателем. Конечно, он получает немного занят, если вы пишете эти скобки - что звезда и что точка. Это становится немного занят. Поэтому у нас есть некоторые синтаксический сахар. И эта линия прямо здесь - ptr_node-> п. Это делает точно такой же вещи. Так что те две строки кода эквивалентны и будет делать та же самая вещь. Но я хотел бы отметить тех, перед мы пойдем дальше, чтобы вы понимаете что действительно эта вещь прямо здесь является просто синтаксический сахар для разыменования указатель, а затем собирается н частью этой структуры. Любые вопросы о этом слайде? ОК. Так что мы собираемся пройти через пару операций, которые вы можете сделать на связанные списки. Связанный список, напомним, представляет собой серию узлов, которые указывают на другом. И мы обычно начинают с указателем называется глава, как правило,, что указывает на первое, что в списке. Так на первой линии здесь, мы есть наш первоначальный L в первую очередь. Так что, что вы можете думать - это текст прямо здесь вы можете думать о качестве просто указатель мы сохранили где-то, что точки на первый элемент. И в этом связанного списка у нас есть четыре узла. Каждый узел представляет собой большой ящик. Чем больше коробка внутри большой коробка целая часть. И тогда у нас есть указатель участие. Эти коробки не тянет шкала потому, насколько велика собой целое число в байтах? Насколько велика сейчас? Четыре. И, насколько большой это указатель? Четыре. Так на самом деле, если мы должны были сделать это в масштабе обе коробки будет такой же размер. В этом случае, мы хотим, чтобы вставить что-то в связанном списке. Таким образом, вы можете видеть здесь мы вставки пять Мы пройти через связанный список, найти, где пять идет, а затем вставьте его. Давайте разберем, что вниз и идти немного медленнее. Я собираюсь указать на борту. Так у нас есть узел пять, что мы создали в mallocs. Почему все смеются? Шучу. ОК. Таким образом, мы malloced пять. Мы создали этот узел где-то в другом месте. У нас есть это готовы пойти. Мы начинаем в передней части наш список с двумя. И мы хотим, чтобы вставить в отсортированном моды. Так что, если мы видим два, и мы хотим, чтобы положить в пять, что же нам делать, когда мы видим, что-то меньше, чем мы? Что? Мы хотим, чтобы вставить пять в это связанный список, сохраняя его сортировать. Мы видим, номер два. Так что же нам делать? Маркус? АУДИТОРИЯ: Позвоните указатель к следующему узлу. Джейсон Хиршхорн: И почему мы идем к следующему? АУДИТОРИЯ: Потому что это Следующий узел в списке. И мы знаем только, что другое место. Джейсон Хиршхорн: И пять больше, чем два, в частности. Потому что мы хотим, чтобы держать его отсортированный. Так пять больше двух. Таким образом, мы перейдем к следующему. И теперь мы достигнем четыре. И что происходит, когда мы достигаем четыре? Пять больше четырех. Так мы продолжаем. И теперь мы в шесть. И что же мы видим в шесть? Да, Карлос? АУДИТОРИЯ: Шесть больше пяти. Джейсон Хиршхорн: Шесть является больше пяти. Так вот где мы хотим вставить пять. Однако, имейте в виду, что если мы есть только один указатель здесь - это наша дополнительная указатель вот обходе по списку. И мы указываем до шести. Мы потеряли след того, что приходит раньше шести. Так что, если мы хотим, чтобы вставить что-то в этот список держать его сортируют, мы вероятно, нужно, как много указателей? АУДИТОРИЯ: Два. Джейсон Хиршхорн: Два. Один отслеживать тока один и один, чтобы отслеживать предыдущий. Это только однонаправленный список. Это только идет в одном направлении. Если бы мы имели двусвязный список, где все было указывая на вещи после него и вещи до него, то мы не должны были бы сделать это. Но в данном случае мы не хотим потерять трек, что было до нас, в случае мы должны вставить пять где-то в середине. Скажем, у нас были вставки девять. Что произойдет, когда мы добрались до восьми? АУДИТОРИЯ: Вы должны были бы получить, что пустую точку. Вместо того, нулевую точку, которую вы должны были бы добавить элемент, а затем есть он указывал на девяти. Джейсон Хиршхорн: Совершенно верно. Итак, мы получаем восемь. Мы дойдете до конца списка, потому что это указывает на нуль. И теперь, вместо того, он указывал на нуль у нас он указывал на наш новый узел. И мы установить указатель в наш новый узел на нуль. Кто-нибудь есть какие-либо вопросы о вставке? Что, если я не заботятся о сохраняя список сортируются? АУДИТОРИЯ: Придерживайтесь его на начале или в конце. Джейсон Хиршхорн: Придерживайтесь его на начало или конец. Какой мы должны делать? Бобби? Почему конец? АУДИТОРИЯ: Потому что начало уже заполнен. Джейсон Хиршхорн: ОК. Начало уже заполнена. Кто хочет спорить с Бобби. Маркус. АУДИТОРИЯ: Ну вы, вероятно, хотите придерживаться его в начале, потому что в противном случае, если вы кладете его на конец вам придется пройти весь список. Джейсон Хиршхорн: Совершенно верно. Так что, если мы думаем о выполнения, Время работы, включив в конце бы н, размер этого. Что такое большое O выполнения вставки в начале? Постоянное время. Так что, если вы не заботитесь о сохранении что-то сортируются, гораздо лучше просто вставить в начале этого списка. И это может быть сделано за постоянное время. ОК. Следующая операция найти, что другой - мы формулировке это как категории. Но мы будем смотреть через связанный список в течение некоторого объекта. Вы, ребята, видели код для поиск прежде в лекции. Но мы вроде только что сделал это с вставить, или по крайней мере вставки что-то отсортированы. Вы просматриваете, собирается узла к узлу, пока вы не найдете номер, что вы ищу. Что произойдет, если вы достигнете конец списка? Скажи я ищу девяти и I дойдете до конца списка. Что нам делать? АУДИТОРИЯ: Вернуться ложь? Джейсон Хиршхорн: Вернуться ложным. Мы не нашли его. Если вы дойдете до конца списка и Вы не нашли номер, который вы находитесь ищу, это не там. Любые вопросы о найти? Если бы это было отсортированный список, что бы быть различными для нашего поиска? Да. АУДИТОРИЯ: Было бы найти первое значение вот больше того, вы ищете и затем вернуться ложным. Джейсон Хиршхорн: Совершенно верно. Так что, если это отсортированный список, если мы доберемся до что-то, что это больше, чем то, что мы ищем, мы не должны продолжать идти в конец списка. Мы можем в этой точке вернуться ложным потому что мы не собираемся, чтобы найти его. Вопрос теперь, мы говорили о сохраняя связанные списки сортируются, держать их без сортировки. Это будет то, что вы находитесь , вероятно, придется думать о когда проблема кодирования установить пять, если вы выбрать хэш-таблицу с отдельной цепочки подход, который мы поговорим чуть позже. Но стоит ли это того, чтобы сохранить список отсортированный и затем иметь возможность, может быть, есть быстрее результаты? Или лучше, чтобы быстро вставить что-то в постоянном выполнения, но тогда есть больше поиске? Это компромисс тут же, что вам самим решать, что является более целесообразным для вашей конкретной проблемы. И есть не обязательно один абсолютно правильный ответ. Но это, безусловно, решение, которое вы получаете сделать, и, вероятно, хорошо, чтобы защитить что, скажем, комментарий или два, почему вы выбрали один над другим. Наконец, удаление. Мы видели удаления. Это похоже на поиск. Мы ищем элемента. Скажите, что мы пытаемся удалить шесть. Так мы находим шесть прямо здесь. Дело в том, что мы должны убедиться, что мы делать то, что все, что указывает на шесть - как мы видим в действии два вниз здесь - что бы ни указывая на шести потребностей в пропустить шесть сейчас и быть изменен на все шесть указывает на. Мы не хотим, чтобы когда-нибудь сиротам остальную часть наш список, забыв установить, что предыдущая указатель. А потом иногда, в зависимости по программе, они просто удалить этот узел целиком. Иногда вы хотите, чтобы вернуться значение, которое находится в этом узле. Так вот, как удаление работ. Любые вопросы по удалить? АУДИТОРИЯ: Так что, если вы собираетесь удалить это, вы бы просто использовать бесплатно, потому что предположительно было malloced? Джейсон Хиршхорн: Если вы хотите, чтобы освободить то, что совершенно верно, и вы malloced его. Скажем мы хотели вернуться это значение. Мы могли бы вернуться шесть, а затем бесплатно этот узел и вызов бесплатно на него. Или мы, вероятно, звонить бесплатно первый , а затем вернуться шесть. ОК. Так давайте перейдем к практике кодирования. Мы собираемся, чтобы закодировать три функции. Первый из них называется insert_node. Так у вас есть код, который я послал по электронной почте вам, и если вы смотрите это позже Вы можете получить доступ к коду в linked.c на сайте CS50. Но в linked.c, есть некоторые скелет код, который уже была написана для вас. А тут еще пару ФУНКЦИИ вам нужно написать. Сначала мы собираемся написать insert_node. А что insert_node делает есть вставляет целое. И вы даете целое число в связный список. И в частности, необходимо сохранить список, отсортированный от меньшего к большему. Кроме того, вы не хотите, чтобы вставить все дубликаты. Наконец, как вы можете видеть insert_node возвращает логическое значение. Таким образом, вы, как предполагается, чтобы пользователь знал, или нет вставка была успешным, возвращая истинным или ложным. В конце этой программы - и для этой стадии вам не нужно беспокоиться об освобождении ничего. Так что все, что вы делаете это взятия целой и вставки его в список. Это то, что я прошу вас сделать сейчас. Опять же, в linked.c, которые вы у всех есть, это код скелет. И вы должны увидеть в нижней Объявление функции образца. Тем не менее, прежде чем в его кодирования в С, я настоятельно рекомендую вам пойти через ряд шагов, мы были практикующих каждую неделю. Мы уже прошли через картина этого. Таким образом, вы должны иметь некоторое представление , как это работает. Но я хотел бы призвать вас, чтобы написать некоторые псевдокод, прежде чем погрузиться дюйма И мы собираемся перейти на псевдокод как группа. А потом, как только вы написали псевдокод, и как только мы написали наш псевдокод как группа, вы можете идти в кодирования его в С. Как один на один, функция insert_node Вероятно, самая сложная из три мы собираемся написать, потому что я добавлены некоторые дополнительные ограничения на Ваш программирование, в частности, что вы не собираетесь вставить любой дубликатов и, что список должны оставаться отсортированный. Так что это нетривиальная программа что вы должны кодировать. И почему бы вам не взять 6:55 минут только, чтобы получить работу на псевдокод и код. А потом мы начнем собирается в качестве группы. Опять же, если у вас есть какие-либо вопросы, просто поднимите руку, и я приду вокруг. . Мы также в целом сделать это - или я не явно говорят вам может работать с людьми. Но очевидно, что я настоятельно рекомендую Вам, если у вас есть вопросы, спросить сосед сидит рядом с вами или даже работать с кем-то еще, если вы хотите. Это не должно быть индивидуальным молчание деятельности. Давайте начнем с написания некоторых псевдокод на доске. Кто может дать мне первую линию псевдокод для этой программы? Для этой функции, а - insert_node. Олден? АУДИТОРИЯ: Поэтому первое, что я сделал, было создать новый указатель на узел и I инициализации он указывая на то же самое вещь, которая список указывает на. Джейсон Хиршхорн: ОК. Так вы создаете новый указатель в список, а не к узлу. АУДИТОРИЯ: Верно. Да. Джейсон Хиршхорн: ОК. А потом что мы хотим сделать? Что после этого? А как насчет узла? У нас нет узла. Мы просто иметь значение. Если мы хотим, чтобы вставить узел, что мы нужно сделать, прежде чем мы можем даже думать о вставив его? АУДИТОРИЯ: Ой, простите. мы должны Malloc пространство для узла. Джейсон Хиршхорн: Отлично. Давайте сделаем - ОК. Не можете достичь этого максимума. ОК. Мы собираемся идти вниз, а затем мы используем два столбца. Я не могу пойти, что - ОК. Создайте новый узел. Вы можете создать еще один указатель на список или вы можете просто использовать список, как она существует. Вы действительно не нужно этого делать. Так мы создаем новый узел. Великий. Это то, что мы делаем в первую очередь. Что дальше? АУДИТОРИЯ: Подождите. Должны ли мы создать новый узел сейчас или мы должны ждать, чтобы убедиться, что нет никаких дубликатов узла в списке, прежде чем мы его создать? Джейсон Хиршхорн: Хороший вопрос. Давайте проведем это на потом, потому что Большую часть времени мы будем создавать новый узел. Так мы будем держать это здесь. Но это хороший вопрос. Если мы создаем его, и мы находим дубликат, что должно мы делаем, прежде чем вернуться? АУДИТОРИЯ: Освободите его. Джейсон Хиршхорн: Да. Наверное освободить его. ОК. Что мы делаем после того как мы создать новый узел? Энни? АУДИТОРИЯ: Ставим число в узле? Джейсон Хиршхорн: Совершенно верно. Мы, число - мы Malloc пространство. Я собираюсь оставить это все как одна строка. Но вы правы. Мы Malloc пробел, а затем мы ставим номер дюйма Мы можем даже установить указатель часть ее до нуля. Вот именно. И то что говорить о после этого? Мы нарисовал эту картину на доске. Так что же нам делать? АУДИТОРИЯ: Мы идем по списку. Джейсон Хиршхорн: Пройтись по списку. ОК. И что же мы проверяем для каждого узла. Курт, что же мы проверяем для каждого узла? АУДИТОРИЯ: Смотрите ли н значение что узел больше, чем п значением нашего узла. Джейсон Хиршхорн: ОК. Я собираюсь сделать - да, хорошо. Так что это п - Я собираюсь сказать, если значение больше чем этот узел, то что же нам делать? АУДИТОРИЯ: Ну, тогда мы вставляем вещь прямо перед этим. Джейсон Хиршхорн: ОК. Таким образом, если это больше, чем эта, то мы хотим вставить. Но мы хотим, чтобы вставить его прямо перед потому что мы также должны были бы быть отслеживание, то, из того, что было раньше. Так вставить раньше. Таким образом, мы, вероятно, что-то пропустил ранее. Мы, вероятно, должны быть сохраняя трек, что происходит. Но мы вернемся туда. Так что значение меньше? Курт, что мы будем делать, если значение меньше? АУДИТОРИЯ: Тогда вам просто продолжать идти если это не последний. Джейсон Хиршхорн: Мне это нравится. Так что к следующему узлу. Если это не последний - мы, вероятно, проверяя, что в терминах состояния. Но да, следующий узел. И это становится слишком низким, так что мы будем двигаться здесь. Но если - может все это видишь? Если мы равны, что мы делаем? Если значение мы пытаемся вставить равна стоимости этого узла? Да? АУДИТОРИЯ: [неразборчиво]. Джейсон Хиршхорн: Да. Учитывая это - Маркус прав. Мы могли бы, может быть, сделано что-то другое. Но, учитывая, что мы создали его, здесь мы должны освободить, а затем вернуться. О мальчик. Так лучше? Как это? ОК. Бесплатный и то что мы вернуться, [неразборчиво]? ОК. Мы не написали ничего? Так куда мы отслеживание предшествующего узла? Зала: Я думаю, что это пойдет после создания нового узла. Джейсон Хиршхорн: ОК. Поэтому в начале мы, наверное, - да, мы можем создать указатель на новый узел, как предыдущий указатель узла и текущий указатель узла. Так что давайте вставить, что здесь. Создание текущий и предыдущий указатели на узлах. Но когда мы настроить эти указатели? Где же нам делать, что в коде? Джефф? АУДИТОРИЯ: - условия значение? Джейсон Хиршхорн: Какие один, в частности? АУДИТОРИЯ: Я просто в замешательстве. Если значение больше этого узла, не значит ли это, что вы хотите пойти на следующий узел? Джейсон Хиршхорн: Так что, если наша значение больше, чем значение этого узла. АУДИТОРИЯ: Да, то вы хотели бы идти дальше по линии, не так ли? Джейсон Хиршхорн: Верно. Таким образом, мы не вставляйте его здесь. Если значение меньше этого узла, то мы идем к следующему узлу - или тогда мы вставить раньше. АУДИТОРИЯ: Подождите, что это узел и что значение? Джейсон Хиршхорн: Хороший вопрос. Значение за этим определением функции это то, что нам дают. Так значение является числом нам дают. Таким образом, если значение меньше, чем это узел, нам нужно время, чтобы вставить. Если значение больше этого узла, мы идем к следующему узлу. И вернуться к первоначальному вопросу, хотя, где - АУДИТОРИЯ: Если значение больше чем этого узла. Джейсон Хиршхорн: И так что нам делать здесь? Сладкий. Это верно. Я просто собираюсь написать изменение указатели. Но да, с текущей вы бы обновить ее до указывают на следующей. Все остальное мы пропустили? Так что я собираюсь ввести этот код в Gedit. И в то время я делаю это, вы можете иметь Еще пара минут, чтобы работать по кодированию это в С. Так что я свой вклад псевдокод. Небольшое примечание прежде чем мы начнем. Мы не можем быть в состоянии полностью закончить это всего три из этих функций. Существует правильные пути их решения что я буду по электронной почте к вам, ребята после раздела, и он будет будут размещены на CS50.net. Так что я не призываю вас пойти посмотреть на секциях. Я призываю вас, чтобы попытаться их на ваш владеть, а затем использовать практику проблемы, чтобы проверить свои ответы. Все они были разработаны, чтобы тесно относятся к и придерживаться того, что что вам нужно сделать на множестве проблем. Так что я призываю вас к практике это по своему усмотрению, а затем использовать код для проверить свои ответы. Потому что я хочу, чтобы двигаться дальше, чтобы прояснить столы в какой-то момент в разделе. Таким образом, мы не могли бы получить через все это. Но мы сделаем столько, сколько мы можем сейчас. ОК. Начнем. Асам, как мы создаем новый узел? АУДИТОРИЯ: Вы структуры *. Джейсон Хиршхорн: Таким образом, мы есть, что здесь. Ой, простите. Вы говорили структуру *. АУДИТОРИЯ: А потом [? вид?] узел или с узлом. Джейсон Хиршхорн: ОК. Я буду называть его new_node так что мы можем оставаться последовательным. АУДИТОРИЯ: И вы хотите установить, что возглавить, первый узел. Джейсон Хиршхорн: ОК. Так что теперь это, указывающий на - так это не создал новый узел еще. Это просто указывая на Первый узел в списке. Как создать новый узел? Если мне нужно пространство, чтобы создать новый узел. Malloc. И насколько большой? АУДИТОРИЯ: Размер структуры. Джейсон Хиршхорн: размер структуры. И что структура называется? АУДИТОРИЯ: Узел? Джейсон Хиршхорн: Узел. Так таНос (SizeOf (узел)); дает нам пространство. И эта линия - одно неправильное на этой линии. Является new_node указатель на структуру? Это общее название. Что это - узел, точно. Это узел *. И что же нам делать сразу после мы Malloc что-то, Асан? Что первое, что мы делаем? Что делать, если он не работает? АУДИТОРИЯ: О, проверить, если он указывает на узле? Джейсон Хиршхорн: Совершенно верно. Так что если вы new_node равна равных нуль, что же нам делать? Это возвращает логическое значение, эту функцию. Именно так. Выглядит хорошо. Все, что добавить туда? Мы добавим вещи в конце. Но что до сих пор выглядит хорошо. Создание текущие и предыдущие указатели. Майкл, как я могу это сделать? АУДИТОРИЯ: Вы должны были бы сделать узел *. Вы должны были бы сделать один не для new_node но для узлы у нас уже есть. Джейсон Хиршхорн: ОК. Таким образом, текущий узел мы на. Я позвоню, что ин. Хорошо. Мы решили, что мы хотим сохранить два, потому что мы должны знать что перед ним. Что они инициализируются? АУДИТОРИЯ: Их ценность в нашем списке. Джейсон Хиршхорн: Так в чем же Первое, что в нашем списке? Или как мы знаем, где начало нашем списке есть? АУДИТОРИЯ: Разве это не прошло в функцию? Джейсон Хиршхорн: Верно. Он был принят в прямо здесь. Так что, если он передается в функцию, начало списка, что мы должны установить ток, равный? АУДИТОРИЯ: Список. Джейсон Хиршхорн: Список. Вот именно. Теперь он имеет адрес начало нашего списка. А как насчет предыдущий? АУДИТОРИЯ: Список минус одна? Джейсон Хиршхорн: Там в ничего перед ним. Так что мы можем сделать, чтобы показать, ничего? АУДИТОРИЯ: Null. Джейсон Хиршхорн: Да. Это звучит как хорошая идея. Прекрасно. Спасибо. Пройтись по списку. Константин, как долго мы будем идти по списку? АУДИТОРИЯ: пока мы не достигнем нулевой. Джейсон Хиршхорн: ОК. Так что если, в то время, в течение цикла. Что мы делаем? АУДИТОРИЯ: Может быть, для цикла? Джейсон Хиршхорн: Давайте сделаем цикл. ОК. АУДИТОРИЯ: И мы говорим на - до текущего указателя не равен NULL. Джейсон Хиршхорн: Так что, если мы знаем, что состояние, как мы можем написать цикл основаны от этого условия. Какие цикле мы должны использовать? АУДИТОРИЯ: В то время как. Джейсон Хиршхорн: Да. Это имеет больше смысла, основанную от того, что вы сказали. Если мы просто хотим, чтобы войти в мы это было бы просто знаю, что вещь, было бы смысл делать какое-то время цикла. В то время как ток не равен NULL, если значение меньше этого узла. Akshar, дай мне эту линию. АУДИТОРИЯ: Если ток-> п н менее стоимости. Или обратная что. Переключатель что кронштейн. Джейсон Хиршхорн: Извините. АУДИТОРИЯ: Измените кронштейн. Джейсон Хиршхорн: Так что, если это больше, чем значение. Потому что это заблуждение с выше комментарий, я собираюсь это сделать. Но да. Если наша ценность меньше, чем это узел, что же нам делать? О. У меня есть его прямо здесь. Вставьте раньше. ОК. Как мы это делаем? АУДИТОРИЯ: Это все еще я? Джейсон Хиршхорн: Да. АУДИТОРИЯ: Вы - new_node-> следующая. Джейсон Хиршхорн: Так в чем что собирается равняться? АУДИТОРИЯ: Это будет равной тока. Джейсон Хиршхорн: Совершенно верно. И так с другой - что еще нужно для обновления? АУДИТОРИЯ: Убедитесь, что мимо равна нулю. Джейсон Хиршхорн: Если предыдущая - так что если пред равна нулю. АУДИТОРИЯ: Это означает, что он собирается стать главой. Джейсон Хиршхорн: Это означает это стать главой. Итак, что же нам делать? АУДИТОРИЯ: Мы делаем голову равно new_node. Джейсон Хиршхорн: Руководитель равна new_node. И почему возглавить здесь, не перечислить? АУДИТОРИЯ: Потому что голова является мировым переменная, которая является отправной точкой. Джейсон Хиршхорн: Сладкий. ОК. И - АУДИТОРИЯ: Тогда вы еще пред-> Следующий равно new_node. А потом вы вернетесь правда. Джейсон Хиршхорн: Куда мы устанавливаем new_node конец? Зала: Я - Я установил, что в начале. Джейсон Хиршхорн: Так что линия? АУДИТОРИЯ: После того, как если заявление проверки, если он известен. Джейсон Хиршхорн: Прямо здесь? АУДИТОРИЯ: я сделаю new_node-> п равна стоимости. Джейсон Хиршхорн: Звучит хорошо. Наверное, имеет смысл - мы не делаем должны знать, что список мы на потому что мы имеем дело только с одного списка. Так лучше объявление функции для это просто, чтобы избавиться от этого целиком и просто вставить значение в голову. Мы даже не должны знать, что список мы дюйма Но я буду держать его на данный момент и затем изменить его по модернизации слайды и код. Так что хорошо выглядит на данный момент. Если значение - кто может сделать эту линию? Если - что нам делать здесь, Ной. АУДИТОРИЯ: Если значение больше чем вал-> п - Джейсон Хиршхорн: Как сделать мы идем к следующему узлу? АУДИТОРИЯ: Керр-> п равна new_node. Джейсон Хиршхорн: Так п какая часть структуры? Целое. И new_node является указателем на узел. Так что часть тек мы должны обновить? Если не я, то что другая часть? Ной, что другая часть. АУДИТОРИЯ: О, в следующий. Джейсон Хиршхорн: Далее, точно. Именно так. Следующая является правильным. А что еще нужно обновить, Ной? АУДИТОРИЯ: Указатели. Джейсон Хиршхорн: Так мы обновили ток. АУДИТОРИЯ: Предыдущая-> следующая. Джейсон Хиршхорн: Да. Хорошо, мы паузу. Кто может помочь нам здесь? Ману, что мы должны делать? АУДИТОРИЯ: Вы должны установить его равным тек-> следующий. Но сделать это прежде, чем в предыдущей строке. Джейсон Хиршхорн: ОК. Что-нибудь еще? Akshar. АУДИТОРИЯ: Я не думаю, что ты означало изменить Curr-> следующий. Я думаю, вы в виду, чтобы сделать вал равных вал-> Далее для перехода к следующему узлу. Джейсон Хиршхорн: Так жаль, где? На какой линии? Эта линия? АУДИТОРИЯ: Да. Сделать вал равна вал-> следующая. Джейсон Хиршхорн: Так вот правильно поскольку в настоящее время является указатель к узлу. И мы хотим, чтобы она указывала на следующий узел, что становится в настоящее время указал на. Сам Керр имеет следующий. Но если бы мы должны были обновить curr.next, мы будет обновлять фактические сведению сама не там, где это указатель указывал. А как насчет этой линии, хотя. Ави? АУДИТОРИЯ: Предыдущая-> следующая равна ин. Джейсон Хиршхорн: Итак, еще раз, если пред является указатель на узел, пред-> следующий является Фактический указатель в узле. Так что это будет обновление указатель в узле к Curr. Мы не хотим, чтобы обновить указатель на узел. Мы хотим, чтобы обновить предыдущий. Так как же нам это сделать? АУДИТОРИЯ: Было бы просто быть пред. Джейсон Хиршхорн: Верно. Предыдущая является указателем на узел. Теперь мы меняем его на Новый указатель на узел. ОК Давайте двигаться вниз. Наконец, последнее условие. Джефф, что мы делаем здесь? АУДИТОРИЯ: Если значение равна вал-> п. Джейсон Хиршхорн: Извините. О боже мой. Что? Значение == вал-> п. Что нам делать? АУДИТОРИЯ: Вы бы освободить нашу new_node, и тогда вы бы вернуться ложным. Джейсон Хиршхорн: Это то, что мы написали до сих пор. Кто-нибудь есть ничего добавить, прежде чем сделать? ОК. Давайте попробуем. Контроль может дойти до конца из не-пустота функции. Ави, что происходит? АУДИТОРИЯ: Вы должны поставить возвращение правда за пределами время цикла? Джейсон Хиршхорн: Я не знаю. Вы хотите, чтобы я? АУДИТОРИЯ: Не берите в голову. Нет. Джейсон Хиршхорн: Akshar? Зала: Я думаю, что вы предназначены для положить возвращение ложным в конце из то время цикла. Джейсон Хиршхорн: Так где Вы хотите, чтобы это пошло? АУДИТОРИЯ: Как за то время цикла. Так что, если вы выходите из то время как цикл Это означает, что что вы дошли до конца и ничего не случилось. Джейсон Хиршхорн: ОК. Так что же нам делать здесь? АУДИТОРИЯ: Вы вернуться ложным там же. Джейсон Хиршхорн: О, мы сделать это в обоих местах? АУДИТОРИЯ: Да. Джейсон Хиршхорн: ОК. Если мы идем? О боже мой. Мне очень жаль. Я прошу прощения за экрана. Это своего рода бесконтрольного поведения на нас. Так что выбирайте опцию. Ноль, в соответствии с кодом, выходит из программы. Один вставляет что-то. Давайте вставить три. Вставка не была успешной. Я собираюсь распечатать. Я не имею ничего. ОК. Может быть, это была просто случайность. Вставьте один. Не успешным. ОК. Давайте рассмотрим GDB очень быстро чтобы проверить, что происходит. Запомнить GDB. / Имя вашего Программа получает нас в GDB. Много это или мало, чтобы справиться? Мигает? Наверное. Закройте глаза и сделайте несколько глубоких дышит, если вы устаете смотреть на это. Я в GDB. Что первое, что я делаю в GDB? Мы должны выяснить, что происходит здесь. Давайте посмотрим. У нас есть шесть минут, чтобы понять , что происходит. Перерыв основной. А потом что мне делать? Карлос? Запустите. ОК. Давайте выберем опцию. И что N делать? Следующая. Да. АУДИТОРИЯ: Вы не упомянули - ты не сказал, что глава, это было инициализируется нулем в начале. Но я думал, вы сказали, что было в порядке. Джейсон Хиршхорн: Поехали - давайте посмотрим в GDB, а затем мы вернемся. Но это звучит как у вас уже есть некоторые идеи о том, что происходит. Поэтому мы хотим, чтобы вставить что-то. ОК. Мы вставить. Пожалуйста, введите Int. Мы вставить три. А потом я на этой линии. Как я могу идти начать отладку вставка известно функцию? О боже мой. Это много. Разве что волнуюсь много? АУДИТОРИЯ: О, это умер. Джейсон Хиршхорн: Я просто вытащил его. ОК. АУДИТОРИЯ: Может быть, это Другой конец проволоки. Джейсон Хиршхорн: Ничего себе. Так суть - что ты сказал? Зала: Я сказал, что ирония техническая Трудности в этом классе. Джейсон Хиршхорн: Я знаю. Если бы только я имел контроль над этой частью. [Неразборчиво] Это звучит здорово. Почему бы вам не начать думать о то, что мы могли бы сделать так, и мы вернемся в 90 секунд. Avica, я собираюсь спросить вас, как идти внутри insert_node отладить его. Так что это, где мы в последний раз остановились. Как я могу идти внутри insert_node, Avica, изучить, что происходит? Какая команда GDB? Перерыв не возьмет меня внутри. Знает ли маркиза? АУДИТОРИЯ: Что? Джейсон Хиршхорн: Какая команда GDB Я использую, чтобы зайти внутрь этой функции? АУДИТОРИЯ: Шаг? Джейсон Хиршхорн: Шаг через С. Это берет меня внутри. ОК. New_node mallocing некоторое пространство. Это все выглядит как его собираются. Давайте рассмотрим new_node. Он получил некоторую адрес памяти. Давайте проверим - это все правильно. Так что все здесь, кажется, работает правильно. АУДИТОРИЯ: В чем разница между Р и дисплея? Джейсон Хиршхорн: Р обозначает для печати. И так вы спрашиваете в чем Разница между этим и этим? В этом случае, ничего. Но в целом есть некоторые различия. И вы должны смотреть в руководстве GDB. Но в данном случае, ничего. Мы склонны использовать печать, хотя, потому что нам не нужно делать гораздо больше, чем распечатать одно значение. ОК. Таким образом, мы находимся на линии 80 нашего кода, установка узла * Curr равную списка. Давайте распечатать ин. Она равна список. Сладкий. Подождите. Она равна что-то. Это не кажется правильным. Там мы идем. Это потому, что в GDB, справа, если это линия ты на нем еще не выполнена. Так что вам нужно на самом деле тип Следующий выполнить линию прежде, чем видеть его результаты. И вот мы. Мы только что выполнили эту линию, предыдущая равна нулю. Итак, еще раз, если мы печатаем предыдущая мы не увидим ничего странного. Но если мы на самом деле выполнить, что линия, то мы увидим, что эта линия работала. Поэтому у нас есть ин. Те, оба хороши. Не так ли? Сейчас мы находимся на этой линии прямо здесь. В то время как вал не равен NULL. Ну, что делает вал равны? Мы только что видели он равнялся нулю. Мы напечатали его. Я распечатать его снова. Так что пока петля будет выполнять? АУДИТОРИЯ: Нет. Джейсон Хиршхорн: Так что, когда я набрал, что линия, вы видите, мы вскочили на всем пути вниз к основанию, вернуться ложным. А потом мы собираемся вернуться ложным и вернуться к нашей программе и в конечном итоге распечатать, как мы видели, вставка не была успешной. Так, у кого-то есть какие-то идеи о том, что мы должны сделать, чтобы это исправить? Я собираюсь ждать, пока я не вижу пару рук вверх. Мы не выполнить это. Имейте в виду, это был первый что мы делали. Я не собираюсь сделать пару. Я собираюсь сделать несколько. Потому что пару означает два. Я буду ждать более двух. Первый вставка, вал, по умолчанию равна нулю. И этот цикл выполняется только если вал не является нулевым. Так как я могу обойти это? Я вижу три руки. Я буду ждать более трех. Маркус, что ты думаешь? АУДИТОРИЯ: Ну, если вам это нужно, чтобы выполнить более одного раза, вы просто изменить его на сделай время цикла. Джейсон Хиршхорн: ОК. Будет ли это решить нашу проблему, хотя? не AUDIENCE: В этом случае нет из-за тот факт, что список пуст. Так то вы, вероятно, просто нужно добавить заявление, что если цикл завершается то вы должны быть в конце список, после чего вас можно просто вставить ее. Джейсон Хиршхорн: Мне это нравится. Это имеет смысл. Если цикл выходит - потому что это будет возвращение ложным здесь. Так что, если цикл завершается, то мы на конец списка, или, может быть начало списка, если нет ничего в это, которое является таким же, как в конце. Так что теперь мы хотим, чтобы вставить что-то здесь. Так как же этот код искать, Маркус? АУДИТОРИЯ: Если у вас уже есть узел malloced, вы могли бы просто сказать, new_node-> следующая равна нуль, потому что он должен быть в конце. Или new_node-> следующая равна нулю. Джейсон Хиршхорн: ОК. Извините. New_node-> следующая равно нуль , потому что мы находимся в конце. Это не положить его дюйма Как мы положить его в списке? Верно. Вот только положив ее равной. Нет, как же мы на самом деле положить его в списке? Что указывая на конец списка? АУДИТОРИЯ: зав. Джейсон Хиршхорн: Извините? АУДИТОРИЯ: руководитель указывает в конце списка. Джейсон Хиршхорн: Если нет ничего в список, голова указывая на конец списка. Так что буду работать на Первый вставки. Что, если есть несколько вещи в списке? Чем мы не хотим, чтобы установить возглавить равно new_node. Что мы хотим, чтобы там делать? Да? Наверное предыдущий. Будет ли это работать? Напомним, что предыдущая просто указатель на узел. И предыдущая является локальной переменной. Так эта линия будет установлена ​​локальная переменная, предыдущий, равной или указывая на этом новом узле. Это не будет на самом деле положил его в нашем списке, хотя. Как мы положить его в нашем списке? Akchar? Зала: Я думаю, что вы сделать текущий-> Next. Джейсон Хиршхорн: ОК. вал-> следующая. Итак, еще раз, единственная причина, мы вниз вот, что значит ток, равный? АУДИТОРИЯ: Равно нулю. Джейсон Хиршхорн: И так, что произойдет, если мы делаем нуль-> дальше? Что мы собираемся получить? Мы получим ошибку сегментации. АУДИТОРИЯ: Do вал равна нулю. Джейсон Хиршхорн: Это то же самое, как предыдущая, хотя, потому что есть локальная переменная мы устанавливаем равным этому новому узлу. Давайте вернемся к нашей картине вставки что-то. Скажите, что мы, включив в конце из списка, так прямо здесь. У нас есть текущий указатель Это указывая на нуль и предыдущий пункт который, указывая на 8. Так что же нам нужно обновить, Ави? АУДИТОРИЯ: Предыдущий-> дальше? Джейсон Хиршхорн: Предыдущий-> следующая является то, что мы хотим обновить, потому что на самом деле вставить его в конец списка. У нас еще есть одна ошибка, тем не менее, что мы собираемся запустить в. Что это ошибка? Да? АУДИТОРИЯ: Это собирается вернуться ложь в этом случае? Джейсон Хиршхорн: О, это будет собирается вернуться ложным. Но есть и другая ошибка. Поэтому мы должны поставить взамен истинного. АУДИТОРИЯ: Есть ли предыдущая прежнему равна нуль в верхней части списка? Джейсон Хиршхорн: Так предыдущая еще равна нуль в самом начале. Так как мы можем преодолеть это? Да? Зала: Я думаю, что вы можете сделать чек до в то время как цикл, чтобы убедиться, что это пустой список. Джейсон Хиршхорн: ОК. Так что давайте идти сюда. У чек. Если - АУДИТОРИЯ: Так что, если руководитель равна равна нулю. Джейсон Хиршхорн: Если голова равна равна нуль - что нам скажет, если это пустой список. АУДИТОРИЯ: И тогда вы сделать глава равно новая. Джейсон Хиршхорн: Руководитель равна new_node? А что еще нужно сделать? АУДИТОРИЯ: А потом вы вернетесь правда. Джейсон Хиршхорн: Не совсем. Мы не хватает на один шаг. АУДИТОРИЯ: new_node рядом должен указывать на нуль. Джейсон Хиршхорн: Точно, Олден. И тогда мы сможем вернуться верно. ОК. Но это все еще хорошая идея, чтобы делать вещи, в конце списка, не так ли? Хорошо. Мы по-прежнему может на самом деле получить в конце списка. Так это код прекрасно, если мы на конец списка и есть некоторые вещи в списке? Не так ли? Потому что у нас еще есть идея Маркуса. Мы могли бы выйти из этого цикла, потому что мы в конце списка. Так что мы по-прежнему хотим, чтобы этот код здесь? АУДИТОРИЯ: Да. Джейсон Хиршхорн: Да. И то, что нам нужно изменить это? Правда. Это звучит хорошо всем до сих пор? Кто-нибудь есть любая - Ави, у вас есть, что добавить? АУДИТОРИЯ: Нет. Джейсон Хиршхорн: ОК. Таким образом, мы сделали несколько изменений. Мы сделали эту проверку прежде, чем мы занимался пустой список. Таким образом, мы позаботились о пустой список. И вот мы позаботились о вставке что-то в конце списка. Так что, похоже, как это в то время как петли взятия уход за вещами между ними, где-то в списке, если есть вещи в списке. ОК. Давайте запустить эту программу еще раз. Не успешным. АУДИТОРИЯ: Вы не сделали это. Джейсон Хиршхорн: О, Я не делал это. Хороший вопрос, Майкл. Давайте добавим марку связаны между собой. Линия 87 есть ошибка. Линия 87. Олден, это была линия вы мне дали. Что не так? АУДИТОРИЯ: Она должна быть на нуль. Джейсон Хиршхорн: Отлично. Совершенно верно. Он должен быть нулевым. Давайте сделаем снова. Компиляция. ОК. Давайте вставить три. Вставка была успешной. Давайте распечатать его. О, если бы мы могли проверить. Но мы еще не сделали распечатать функцию еще. Давайте введем что-то еще. Что мы должны ввести? АУДИТОРИЯ: Семь. Джейсон Хиршхорн: Семь? АУДИТОРИЯ: Да. Джейсон Хиршхорн: У нас есть неисправность сегм. Таким образом, мы получили один, но мы четко не может получить два. Это 5:07. Таким образом, мы могли отладить этот в течение трех минут. Но я собираюсь оставить нас здесь и двигаться дальше на хеши. Но, опять же, ответы на этот код Я буду отправить его к вам в немного. Мы очень близки к нему. Я настоятельно рекомендую вам, чтобы выяснить, что происходит здесь и исправить ее. Так что я буду вам по электронной почте этот код, как хорошо плюс решение - вероятно, решение позже. Впервые этот код. Другая вещь, что я хочу сделать, прежде чем мы отделка мы не освободили ничего. Так что я хочу показать вам, что Valgrind выглядит. Если мы запустим границы Valgrind на нашей программе,. / связаны между собой. Опять же, в соответствии с этим слайде, мы должен работать Valgrind с некоторым типом вариант, в данном случае - Утечка проверка = полный. Так давайте напишем Valgrind - Утечка проверка = полный. Так что это будет работать Valgrind на нашей программе. А теперь программа на самом деле работает. Так что мы собираемся запустить его так же, как прежде, положить что-то дюйма Я собираюсь поставить в трех. Это работает. Я не собираюсь, чтобы попытаться положить в чем-то еще, потому что мы собираемся получить сегм ложным в этом случае. Так что я просто хочу, чтобы бросить курить. И теперь вы видите здесь утечки и резюме куча. Это хорошие вещи, которые Вы хотите, чтобы проверить. Таким образом, резюме куча - это говорит, в использовании на выходе - восемь байт в одном блоке. Это один блок является узел мы malloced. Майкл, ты уже говорил узел восемь укусы, поскольку он имеет целое и указатель. Так вот наш узел. А потом говорит, что мы использовали таНос семь раз, и мы освободили что-то в шесть раз. Но мы никогда не называется свободным, так что я не Идея, что это говорит. Но достаточно сказать, что, когда ваш программа запускается, таНос в настоящее время называется в некоторых других местах, которые мы не нужно беспокоиться. Так таНос, вероятно, называется в некоторых местах. Нам не нужно беспокоиться, где. Но это действительно нам. Это первая линия это мы. Мы оставили этот блок. И вы видите, что здесь в резюме утечки. Тем не менее добраться - восемь байт в одном блоке. Это означает, что память - мы просочились, что память. Определенно потерял - что-то теряется навсегда. Как правило, вы не будете вижу ничего там. Тем не менее добраться, как правило, где вы увидите вещи, где вы хотите, смотреть, чтобы увидеть, какой код должен Вы освободили, но Вы забыли освободить. И потом, если это было не так, если бы мы сделали бесплатный все, мы можем проверить, что. Давайте просто запустить программу не ставя ни во что. Вы увидите здесь, в использовании на выходе - нулевые байты в нулевых блоков. Это означает, что мы ничего не осталось когда вышел эта программа. Так, прежде чем включать в pset6, запустите Valgrind и убедитесь, что у вас нет просачивается любая память в вашей программе. Если у вас есть любые вопросы с Valgrind, не стесняйтесь обратиться. Но это, как вы его используете. Очень просто - посмотреть, если вы есть в использовании на выходе - любые байт любых блоков. Так мы работали над вставки узла. У меня было два других функций здесь - распечатать узлов и бесплатные узлы. Опять же, эти функции, которые будет хорошо для вас на практике потому что они помогут вам не только с эти примеры упражнений, но и по проблеме установить. Они карту на довольно близко к вещам вы собираетесь нужно сделать в Проблема установить. Но я хочу, чтобы убедиться, мы коснемся всего. И хэш-таблицы также имеют решающее значение для что мы делаем в разделе этой неделю - или в наборе проблемы. Так что мы собираемся закончить раздел говорить о хэш-таблицы. Если вы заметите, что я сделал немного хэш-таблицы. То есть не то, что мы говорим о, однако. Мы говорим о другой тип хэш-таблицы. И по своей сути, хэш-таблицу не что иное, Массив плюс хэш-функция. Мы собираемся говорить на немного просто убедитесь, что все понимают, что такое хэш-функция есть. И я говорю вам сейчас, что это не более, чем двух вещей - массив и хэш-функция. И вот шаги по который в этом работает. Там в наш массив. Там наша функция. В частности, хэш-функции должны сделать несколько вещей с этим. Я собираюсь говорить конкретно о эта проблема установить. Это, вероятно, будет принять в строке. И то, что он собирается вернуться? Какой тип данных? Олден? Ваш хэш-функция возврата? Целое. Так что это то, что хэш Таблица состоит из - таблица в виде массива и хэш-функция. Как это работает? Он работает в три этапа. Мы даем ему ключ. В этом случае, мы дадим ему строку. Мы называем хеш-функцию на первом этапе на ключе, и мы получаем значение. В частности, мы будем говорить мы получаем целое. Это целое число, есть очень специфическая пределы того, что, что целое может быть. В этом примере, наш массив имеет размер три. Так что цифры могут, что целое быть. Каков диапазон допустимых значений для что целое, возвращаемый тип это хэш-функция? Ноль, один и два. Дело в хэш-функции является выяснить место в массиве где наш ключ будет. Есть только три возможных места здесь - ноль, один или два. Так эта функция более высокий доход ноль, один или два. Некоторые действует Indice в этом массиве. А потом в зависимости от того, где он возвращает, Вы можете увидеть там множество открыт скобки значение. Вот где мы разместили ключ. Так мы бросаем в тыкве, мы выходим нулю. В массиве кронштейна 0, положим тыкву. Кидаем в кошек, мы получаем одну. Ставим кошку в одном. Ставим в паука. Мы выходим два. Ставим паука на массив кронштейна два. Это было бы так хорошо, если он работал в этом роде. Но, к сожалению, как мы увидим, это немного сложнее. Прежде чем мы перейдем туда, на любые вопросы об этом базовая наладка хэш-таблице? Это изображение точно то, что мы обратили на доске. Но так как мы обратили его на доске, я я не собираюсь идти в нее дальше. По существу ключи, магия черного ящика - или в данном случае, чирок коробка - из хэш-функция помещает их в ведра. И в этом примере мы не поставив имя. Мы положить соответствующий телефон число имени в ведре. Но вы могли бы очень хорошо просто поставить имя в ведре. Это всего лишь картина того, что мы обратили на доске. У нас есть потенциальные ловушки, однако. И есть два в частности скользит, что я хочу, чтобы перейти. Первый о хэш-функция. Поэтому я задал вопрос, что делает хорошая хеш-функция? Я даю два ответа. Во-первых, это детерминировано. В контексте хэш-функций, что это значит? Да? АУДИТОРИЯ: Он может найти индекс за постоянное время? Джейсон Хиршхорн: Это не то, что это значит. Но это хорошее предположение. Кто-нибудь еще есть предположение к тому, что это означает? Это хорошая хеш-функция детерминирована? Энни? АУДИТОРИЯ: Это ключевой можно сопоставить только в одном месте в хэш-таблице. Джейсон Хиршхорн: Это Совершенно верно. Каждый раз, когда вы кладете в тыквы, она всегда возвращает ноль. Если вы положите в тыкву и вашей хэш Функция возвращает ноль, но имеет вероятность возвращения что-то еще больше нуля - поэтому возможно, это может вернуть одно иногда или два других раза - что это не очень хорошая хеш-функция. Вы совершенно правы. Ваш хэш-функция должна возвращать точно такой же целое число, в данном случае, для точно такой же строкой. Может быть, она возвращает ту же самую точную целое по той же точной строки независимо от капитализации. Но в таком случае он по-прежнему детерминированной, так как несколько вещей отображаются на то же значение. Это нормально. Пока есть только один выход для данного входа. ОК. Второе, что то, что это возвращает действительные показатели. Мы воспитаны, что раньше. Это хэш-функция - о мальчик - хэш-функция должна вернуться допустимые показатели. Так сказать - давайте вернемся к этому примеру. Мой хэш-функция подсчитывает буквы в слове. Это хэш-функция. И возвращает, что целое число. Так что, если у меня есть слово А, это собирается вернуться один. И это будет поставить прямо здесь. Что делать, если я ставлю в слове битой? Это собирается вернуться три. Где летучая мышь идти? Это не подходит. Но для этого нужно пойти куда-нибудь. Это мой хэш-таблицы в конце концов, и все должно пойти куда-нибудь. Так где должны летучая мышь идти? Любые мысли? Угадываем? Хорошие предположения? АУДИТОРИЯ: Ноль. Джейсон Хиршхорн: Почему нулю? АУДИТОРИЯ: Потому что три модулю три равна нулю? Джейсон Хиршхорн: Три модулю три равна нулю. Это большая догадка, и это правильно. Таким образом, в этом случае он должен вероятно, пойти на нуле. Так что хороший способ гарантировать, что этот хэш Функция возвращает только допустимые показатели в к модулю его размеров таблицы. Если вы по модулю Что бы это ни прибыли за счет три, вы всегда собираетесь получить нечто среднее между ноль, один и два. И если это всегда возвращает семь, и вы всегда модулю на три, вы всегда собираетесь получить то же самое. Так что это еще детерминированным если вы по модулю. Но, что будет гарантировать, что вам никогда не получить что-то - инвалид промышленности. Как правило, что по модулю должно произойти внутри хэш-функции. Так что вам не нужно беспокоиться об этом. Вы просто можете гарантировать, что это правильный Indice. Есть вопросы по этому потенциальная ловушка? ОК. И там мы идем. Следующая потенциальная ловушка, и это большой. Что делать, если две клавиши карту в то же значение? Таким образом, есть два способа справиться с этим. Первый называется линейным зондирования, который я не собираюсь перейти на. Но вы должны быть знакомы с тем, как что работает, а что это такое. Второй я собираюсь перейти на потому что это тот, который многие люди, вероятно, в конечном итоге решить, использовать в своей проблеме набора. Конечно, вы не должны. Но для множества проблем, многих людей как правило, выбирают для создания хэш-таблицу с раздельного связывания реализации их словарь. Так что мы собираемся перейти на то, что это означает, создать хэш-таблицу с отдельный цепочки. Так что я положил в тыкву. Это возвращает ноль. И я положил тыкву здесь. Тогда я положил в - что еще один Хэллоуин-тематический вещь? АУДИТОРИЯ: Конфеты. Джейсон Хиршхорн: Конфеты! Это отличное. Я положил в конфеты, и конфеты также дает мне нулю. Что мне делать? Есть идеи? Потому что все, что вы вроде знаю что отдельные цепочки является. Так любые идеи, что делать? Да. АУДИТОРИЯ: Ввод строку на самом деле в хэш-таблице. Джейсон Хиршхорн: Таким образом, мы собираемся привлечь хорошую идею здесь. ОК. АУДИТОРИЯ: Есть хэш-таблице [Неразборчиво] указатель, который указывает на начало списка. А затем тыква быть первое значение в этом связанном списке и конфеты быть второе значение в этой связанного списка. Джейсон Хиршхорн: ОК. Маркус, который был замечательным. Я собираюсь разрушить это. Маркус говорю, не перезаписать тыкву. Это было бы плохо. Не ставьте конфеты где-то в другом месте. Мы собираемся поставить их обоих на нуле. Но мы собираемся иметь дело с положить их в нуле создание списка на нуле. И мы собираемся создать список все, что отображается на ноль. И лучший способ мы научились создавать список, который может увеличиваться и уменьшаться динамически не находится в пределах другой массив. Так не многомерный массив. Но просто создать связанный список. Так что он предложил - Я собираюсь получения новой - это создать массив с указателями, массив указателей. ОК. Любая идея или намек, что тип этого указателей должно быть? Маркус? АУДИТОРИЯ: Указатели на - Джейсон Хиршхорн: Потому что вам сказал связанный список, а значит - АУДИТОРИЯ: Node указатели? Джейсон Хиршхорн: Node указатели. Если вещи в наш связаны Список узлы, то они должны быть указатели узлов. И что же они равны изначально? АУДИТОРИЯ: Null. Джейсон Хиршхорн: Null. Так что наш пустой вещью. Тыквенные возвращает ноль. Что нам делать? Прогулка меня через него? На самом деле, Маркус уже дал мне. Кто-то еще погулять я через него. Что мы делаем, когда мы - это выглядит очень похоже на то, что мы просто делали. Ави. АУДИТОРИЯ: Я собираюсь сделать предположение. Поэтому, когда вы получаете конфеты. Джейсон Хиршхорн: Да. Ну, мы получили тыкву. Давайте наш первый. Мы получили тыкву. АУДИТОРИЯ: ОК. Тыквенные возвращает ноль. Таким образом, вы положите его в том, что. Или на самом деле, вы положили его в связанном списке. Джейсон Хиршхорн: Как мы положить его в связанном списке? АУДИТОРИЯ: О, фактический синтаксис? Джейсон Хиршхорн: Просто ходить - сказать больше. Что нам делать? АУДИТОРИЯ: Вы просто вставить это как первый узел. Джейсон Хиршхорн: ОК. Таким образом, мы имеем нашу узла, тыква. А теперь, как я ввожу его? АУДИТОРИЯ: Вы назначаете это к указателю. Джейсон Хиршхорн: Какие указатель? АУДИТОРИЯ: Указатель на нуле. Джейсон Хиршхорн: Так где делает это смысл? АУДИТОРИЯ: Чтобы обнулить прямо сейчас. Джейсон Хиршхорн: Ну, это указывает на нуль. Но я ставлю в тыкву. Так где он должен указывать? АУДИТОРИЯ: Чтобы тыква. Джейсон Хиршхорн: Для тыквы. Именно так. Так что это указывает на тыкву. А причем тут этот указатель в тыквы точки? К АУДИТОРИЯ: Null. Джейсон Хиршхорн: Чтобы обнулить. Именно так. Так что мы просто вставляется что-то в связанном списке. Мы только что написал этот код, чтобы сделать это. Почти мы почти получилось полностью трещины. Теперь мы вставляем конфеты. Наша конфеты также стремится к нулю. Так что же нам делать с конфетами? АУДИТОРИЯ: Это зависит от того, не мы пытаемся уладить его. Джейсон Хиршхорн: Это Совершенно верно. Это зависит от наличия или отсутствия мы пытаемся уладить его. Давайте предположим, что мы не собирается уладить его. АУДИТОРИЯ: Ну что ж, как мы обсуждали раньше, то проще просто поставить его в самом начале так указатель от нуля указывает на конфеты. Джейсон Хиршхорн: ОК. Держись. Позвольте мне создать конфеты прямо здесь. Так этот указатель - АУДИТОРИЯ: Да, надо сейчас быть указывая на конфеты. Тогда есть указатель от конфеты указывают на тыкву. Джейсон Хиршхорн: Как что? И сказать, что мы получили еще один что нужно сопоставить с нуля? АУДИТОРИЯ: Ну, вы просто сделать то же самое? Джейсон Хиршхорн: Сделайте то же самое. Таким образом, в этом случае, если мы не будем хотите сохранить это уладил его Звучит довольно просто. Возьмем указатель в Indice дается нашей хэш-функции. У нас есть, что точка в наш новый узел. И тогда все, что было указывая ранее - в этом случае нуль, в Второй случай тыквы - что, как там оно указывая на ранее, мы добавляем в ближайших наш новый узел. Мы вставки что-то в самом начале. На самом деле это намного проще, чем пытаясь сохранить список, отсортированный. Но, опять же, поиск будет Чем сложнее здесь. Мы всегда придется идти до конца. ОК. Любые вопросы о раздельного связывания? Как это работает? Пожалуйста, попросите их сейчас. Я очень хочу, чтобы убедиться, что вы все понять это прежде, чем мы кочан. Зал: А почему вы поставить тыкву и конфеты в то же самое часть хэш-таблицы? Джейсон Хиршхорн: Хороший вопрос. Почему мы ставим их в то же самое часть хэш-таблицы? Ну, в этом случае наша хэш-функция возвращает ноль для них обоих. Таким образом, они должны пойти на нуле Indice потому что там мы собираемся смотреть на них, если мы когда-либо хочу посмотреть их. Опять же, с линейной зондирования подход мы бы не положить их обоих в нуле. Но в отдельном подходе цепи, мы собираемся поставить их обоих в нуле а затем создать список с нуля. И мы не хотим, чтобы перезаписать тыкву просто для этого, потому что тогда мы будем Предположим, что тыква была никогда не вставляется. Если мы просто держать одну вещь в место, которое было бы плохо. Тогда не было бы шанс из нас когда-либо - если мы когда-либо имели дубликат, то мы просто стереть нашу начальное значение. Так вот почему мы делаем этот подход. Или вот почему мы выбрали - но опять же, мы выбрал отдельный подход цепных, которых есть много других подходов можно было выбрать. Я ответил на ваш вопрос? ОК. Карлос. Линейный зондирования будет включать - если мы нашли столкновения в нуле, будет выглядеть в следующем месте, чтобы увидеть, если она была открыта и положил его там. А потом мы посмотрим в следующем спорта и посмотреть, если это было открыто, и положил его туда. Таким образом, мы находим следующий доступный открытое место и положил его там. Любые другие вопросы? Да, Ави. АУДИТОРИЯ: В продолжение к этому, что вы имеете в виду следующее место? В хэш-таблице или в связанном списке. Джейсон Хиршхорн: Для линейных программирование, не связанные списки. На следующий пятно на хэш-таблице. АУДИТОРИЯ: ОК. Таким образом, хэш-таблица будет инициализирован размером - как число строк что вы были вставки? Джейсон Хиршхорн: Вы бы хочу, чтобы это действительно большой. Да. Вот картина того, что мы просто обратил на доске. Опять же, у нас есть столкновения прямо здесь. на 152. И вы увидите, мы создали связанный список с него. Опять же, хэш-таблицы отдельный цепочки подход не тот, который вы должны принять для проблемы установите шесть, но это тот, который много студенты, как правило, чтобы взять. Так на этой ноте, давайте кратко поговорим прежде, чем мы кочан о проблеме шесть, а затем я поделюсь с вами историей. У нас есть три минуты. Архив задач шесть. У вас есть четыре функции - нагрузка, проверьте, размер и выгрузки. Нагрузка - хорошо, мы шли над нагрузкой только сейчас. Мы обратили нагрузку на доске. И мы даже начали кодирования много вставки в связанном списке. Так нагрузка не намного больше, чем что мы только что делали. Проверить это, как только вы что-то загружен. Это тот же самый процесс, как этот. Те же первые две части, где вы бросаете что-то в хэш-функции и получить его значение. Но сейчас мы не вставляя его. Сейчас мы ищем для него. Я образец кода, написанного для нахождения что-то в связанном списке. Я призываю вас, чтобы практиковать это. Но интуитивно найти что-то будет довольно похоже на вставку что-то. В самом деле, мы нарисовали картину нахождения что-то в связанном списке, двигаясь через, пока не добрались до конца. И если вы добрались до конца так и не смогли найти его, то это не есть. Так вот проверка, по существу. Далее идет размер. Давай пропустим размер. Наконец вы выгрузить. Разгрузка является одним мы не тянет на доске или закодированы еще. Но я призываю вас, чтобы попробовать его кодирования в нашем примере, связанного, например списка. Но выгрузить интуитивно похож на бесплатно - или я имею в виду похож на проверить. Для теперь каждый раз, когда вы собираетесь исключением через, вы не просто проверять, увидеть, если у вас есть свой значение там. Но вы принимаете этот узел и освобождая его, по существу. Это то, что выгрузка просит вас сделать. Бесплатный все, что вы malloced. Так что вы собираетесь через весь список снова, проходя через весь хэш Таблица снова. На этот раз не проверять чтобы посмотреть, что там. Просто скачать, что там. И, наконец размер. Размер должен быть реализован. Если вы не реализуете размер - Я скажу это, как это. Если вы не реализуете размер в точности одной строки кода в том числе вернуться заявление, вы делает размер неправильно. Поэтому убедитесь размер, для полного дизайна точки, вы делаете это в точности один строка кода, в том числе оператор возврата. И не собраться еще, Akchar. Стремясь бобра. Я хотел сказать спасибо вам, ребята за то, чтобы разделе. Имейте Happy Halloween. Это мой костюм. Я буду носить это в четверг если я вижу вас в рабочее время. И если вам интересно, о некоторых более фон, чтобы этого костюма, чувствую можете проверить 2011 раздел для истории о том, почему я носить тыквы костюм. И это печальная история. Поэтому убедитесь, что у вас есть некоторые ткани поблизости. Но на этом, если у вас есть какие-либо вопросы, я буду придерживаться вокруг снаружи после раздела. Удачи на проблемы установить шесть. И как всегда, если у вас есть какие-либо вопросы, дайте мне знать.