[Музыка, играющая]
СПИКЕР 1: Ладно.
Все добро пожаловать в раздел.
Я надеюсь, что вы все успешно оправился от вашей викторины
с прошлой недели.
Я знаю, что это немного сумасшедшие в разы.
Как я уже говорил ранее, если вы в пределах стандартного отклонения,
на самом деле не беспокоиться об этом, особенно для менее комфортной разделе.
Вот о том, где вы должны быть.
>> Если вы сделали большой, то удивительным.
Слава вам.
И если вы чувствуете, как вам нужно немного больше помощи, пожалуйста,
не стесняйтесь, чтобы достичь к любой из TFS.
Мы все здесь, чтобы помочь.
>> Вот почему мы учим.
Вот почему я здесь каждый понедельник для вас Ребята и в офисе часов по четвергам.
Поэтому, пожалуйста, не стесняйтесь, дайте мне знать, если вы беспокоитесь о чем-либо
или если что-нибудь на викторине что вы действительно хотели бы обратиться.
>> Так повестка дня на сегодня все о структурах данных.
Некоторые из них просто будет просто чтобы вы ознакомились с ними.
Вы никогда не можете реализовать им в этом классе.
Некоторые из них вы, как для вашего SPELLER PSET.
>> Вы будете иметь выбор между хэш-таблиц и попыток.
Таким образом, мы будем определенно над теми.
Это будет определенно больше вида из раздела высокий уровень сегодня, хотя,
потому что есть многие из них, и если мы пошли в детали реализации
на все из них, мы не были бы даже пройти через связанные списки
и, может быть, немного хэш-таблицы.
>> Так, медведь со мной.
Мы не собираемся делать столько кодирования на этот раз.
Если у вас есть какие-либо вопросы по этому поводу или вы хотите увидеть это реализуется
или попробовать его на себе, Я определенно рекомендую
собирается study.cs50.net, которые есть примеры всех из них.
Это будет иметь свои PowerPoints с примечаниями, которые мы
как правило, используют, а также некоторые программирования упражнения, особенно для вещей
как связанные списки и бинарные деревья стеки и подсказки.
Так немного больше высокий уровень, который могло бы быть хорошо для вас, ребята.
>> Так с этим, мы начнем.
А также, yes-- викторины.
Я думаю, что большинство из вас, кто в мой раздел есть свои викторины,
но кто приходит в или какой-то причине вы нет, они прямо здесь, в передней.
>> Так связные списки.
Я знаю этот вид идет для резервного перед вашей викторины.
Это было за неделю до что мы узнали об этом.
Но в этом случае, мы просто пойти немного более подробно.
>> Так почему мы могли бы выбрать связан список по массиву?
Что отличает их?
Да?
>> АУДИТОРИЯ: Вы можете расширить связаны список по сравнению с фиксированным размером массива в.
СПИКЕР 1: Право.
Массив имеет фиксированный размер в то время как Связанный список имеет переменный размер.
Так что, если мы не знаем, как много мы хотим сохранить,
Связанный список дает нам отличный способ сделать это, потому что мы можем просто
добавить на другом узле, и добавить на другой узел и добавить на другом узле.
Но что может быть компромисс?
Кто-нибудь помнит компромисс между массивами и связанные списки?
Mmhmm?
>> АУДИТОРИЯ: Вы должны пройти через все пути
через связанный список найти элемент в списке.
В массиве, вы можете просто найти элемент.
>> СПИКЕР 1: Право.
Так с arrays--
>> АУДИТОРИЯ: [неразборчиво].
>> СПИКЕР 1: С массивами, у нас есть то, что называется произвольным доступом.
Означает, что если мы хотим что либо пятая точка из списка
или пятая точка нашего Массив, мы можем просто взять его.
Если это связанный список, у нас есть для перебора, не так ли?
Так доступ к элементу в Массив является постоянная времени,
в то время как со связанным списком было бы скорее всего, будет линейное время, потому что, может быть,
наш элемент полностью в конце.
Мы должны искать через все.
Так со всеми этими данными структуры, которые мы собираемся
чтобы тратить немного больше времени на, каковы плюсы и минусы.
Когда может мы хотим использовать один над другим?
И это отчасти больше, что нужно забрать.
>> Таким образом, мы имеем здесь Определение узла.
Это как один из элементов наш связанный список, не так ли?
Таким образом, мы все знакомы с нашими ЬурейеЕ структур,
которые мы рассмотрели в обзоре последний раз.
Это была в основном просто создание другой тип данных, которые мы могли бы использовать.
>> И в этом случае, это какая-то узел что проведет некоторое целое число в.
И тогда то, что вторая часть здесь?
Любой?
>> АУДИТОРИЯ: [неразборчиво].
>> СПИКЕР 1: Да.
Это указатель на следующий узел.
Таким образом, это должно быть на самом деле здесь.
Это указатель типа узел к следующей вещи.
И вот что они охватывает нашу узел.
Прохладный.
>> Ладно, так с поиском, как мы были просто говорю, прежде чем руки, если вы
будет искать через, у вас есть на самом деле итерации
через связанный список.
Так что, если мы ищем числа 9, мы бы начать в нашей голове
и что указывает нам в начале нашей связанного списка, не так ли?
И мы говорим: хорошо, делает это узел содержит число 9?
Нет?
>> Ладно, иди к следующему.
Следуйте его.
Содержит ли она число 9?
Нет.
Следуйте следующий.
>> Так что мы должны на самом деле итерации через нашу связанного списка.
Мы не можем просто пойти прямо туда, где 9.
И если вы, ребята, на самом деле хотите, чтобы увидеть некоторые псевдо-код там.
У нас есть функция поиска здесь что берет in-- что же нужно в?
Что ты думаешь?
Так легким.
Что это?
АУДИТОРИЯ: [неразборчиво].
СПИКЕР 1: мы ищем число.
Не так ли?
И что бы это соответствовать?
Это указатель на?
>> АУДИТОРИЯ: узел.
>> СПИКЕР 1: узел в список что мы смотрим на, не так ли?
Поэтому у нас есть некоторые узлы указатель здесь.
Это точка, что собирается на самом деле перебора нашем списке.
Мы устанавливаем его равным список потому что это просто
полагая его равным начать нашего связанного списка.
>> И в то время как это не NULL, в то время как у нас еще есть вещи в нашем списке,
проверьте, если этот узел имеет число мы ищем.
Вернуться правда.
В противном случае, обновите его, не так ли?
>> Если это NULL, мы выходим из нашего в то время как цикл и вернуться ложным
потому что это означает, что мы не нашли его.
Все ли получить, как это работает?
Хорошо.
>> Так с вставки, вы есть три различных способа.
Вы можете предварять, вы можете добавить и вы можете вставить в ассорти.
В этом случае, мы собираюсь делать препендом.
Кто-нибудь знает, как те, три случая могут отличаться?
>> Так перед именем означает, что вы положили это в передней части вашего списка.
Так что это будет означать, что независимо от того, что ваш узел, независимо от того,
что значение, что вы собираетесь поставить его прямо здесь, перед, ОК?
Это будет первый элемент в списке.
>> Если вы добавляете его, это будет идти к задней части списка.
И вставить в ассорти означает, что вы собирается поставить на самом деле в то место,
где он держит ваш связанный список отсортирован.
Опять же, как вы используете те, и когда вы используете
им будет варьироваться в зависимости от вашего случая.
Если это не нужно сортировать, перед именем, как правило,
быть тем, что большинство людей использовать, потому что вы не
должны пройти через весь список чтобы найти конец, чтобы добавить его на, не так ли?
Вы можете просто придерживаться его прямо в.
>> Так что мы будем проходить через вставка 1 прямо сейчас.
Так что то, что я собираюсь очень рекомендую на этом PSET
является привлечение вещи, как всегда.
Это очень важно, что вы обновляете Ваши указатели в правильном порядке
потому что, если вы обновляете их немного не в порядке,
Вы будете в конечном итоге потери части вашего списка.
>> Так, например, в данном случае, мы говорит руководитель просто навести на 1.
Если мы просто делаем, что без сохранения этого 1,
мы понятия не имеем, что 1 следует указать на сейчас
потому что мы потеряли то, что Глава указал на.
Так одно дело помнить когда вы делаете препендом
это, чтобы спасти то, что голова указывает на первый,
затем переназначить его, а затем обновить что ваш новый узел должен указывать на.
В этом случае, это один из способов сделать это.
>> Так что, если бы мы сделали это таким образом где мы просто переназначены голову,
мы теряем в основном наша Весь список, не так ли?
Один из способов сделать это, чтобы иметь 1 пункт до Далее, а затем головки точку 1.
Или вы можете сделать вид, как временного хранения, которые я говорил о.
>> Но переназначение программы Your указатели в правильном порядке
будет очень, очень важно для этой PSET.
В противном случае, вы будете иметь хэш таблицы или попробовать что просто будет
только часть слова, которые вы хочу и то you're-- mmhmm?
АУДИТОРИЯ: Что было временное хранения, что вы говорили?
СПИКЕР 1: временное хранение.
Поэтому в основном другой как вы могли бы сделать это
будет хранить главу то, как хранить ему временную переменную.
Назначают его по 1 и затем обновить 1 к точке
к тому, что глава используется, чтобы указать на.
Таким образом, очевидно, более элегантным, потому что вас
не нужно временное значение, но просто предлагая еще один способ сделать это.
И мы, действительно есть некоторый код для этого.
Так что для связанного списка, мы на самом деле есть некоторый код.
Так, перенесите сюда, это предваряя.
Так что это входит в его в голове.
>> Так первая вещь, вы должны создать новый узел, конечно,
и проверить на NULL.
Всегда хорошо.
И тогда вам нужно присвоить значения.
Всякий раз, когда вы создаете новый узел, вам не знаю, что это, указывая на следующий,
так что вы хотите, чтобы инициализировать его, чтобы NULL.
Если это в конечном итоге указывая на что-то еще, он получает переназначен, и это прекрасно.
Если это первое, что в списке, он должен
указывать на NULL, потому что что это конец списка.
>> Итак, чтобы вставить его, мы видим здесь мы присваиваем следующий ценность нашего узла
быть все, что голова, которая является то, что мы имели здесь.
Это то, что мы только что сделали.
И тогда мы присваиваем голову к точке на наш новый узел, потому что помню,
Новый некоторое указатель на узел, и это именно то, что голова.
Именно поэтому мы есть эта стрелка аксессор.
Прохладный?
Mmhmm?
>> АУДИТОРИЯ: Есть ли у нас в инициализировать новый Далее, чтобы NULL-первых,
или мы можем просто инициализировать его возглавить?
>> СПИКЕР 1: Новая следующий должен быть NULL, чтобы начать
потому что вы не знаете, где он будет.
Кроме того, это своего рода точно так же как парадигму.
Вы можете установить его равным NULL просто сделать Убедитесь, что все ваши базы покрыты
прежде чем делать какие-либо переназначение так, что Вы всегда гарантируется, что это будет
указывать на определенное значение против, как ценности мусора.
Потому что, да, мы присваиваем Новая следующий автоматически,
но это больше, как хорошая практика, чтобы инициализировать его
таким образом, и затем передать.
>> Итак, двусвязного списки сейчас.
Что мы думаем?
Что изменилось с двусвязного списки?
>> Таким образом, в наших связанных списков, мы можем двигаться только в одном направлении, не так ли?
У нас есть только рядом.
Мы можем идти только вперед.
>> С двунаправленный список, мы можем также двигаться в обратном направлении.
Таким образом, мы имеем не только число, которое мы хотим сохранить,
у нас есть, где он указывает на следующий и где мы только пришли.
Таким образом, это позволяет некоторые лучше обхода.
>> Так вдвойне связанные узлы, очень похожи, не так ли?
Только разница в том, теперь мы есть рядом и предыдущая.
Это единственное различие.
>> Так что, если бы мы должны были предварять или append-- мы не имеют никакого кода для этого до here--
но если бы вы были, чтобы попытаться вставьте его, важную вещь
это вы должны сделать что вы присвоения
как ваш предыдущий и ваши следующий указатель правильно.
Таким образом, в этом случае, вы бы не только инициализировать рядом,
инициализации предыдущая.
Если мы находимся в начале списка, мы будет не только сделать глава равно новый,
но наш новый предыдущая должны указывают на голове, не так ли?
>> Вот и вся разница.
И если вы хотите больше практики с они со связанными списками, с вставки,
с удалением, со вставкой в сборных списка,
пожалуйста, ознакомьтесь с study.cs50.net.
Там куча великих учений.
Я очень рекомендую их.
Я желаю, чтобы мы успели пройти через них но есть много структур данных
чтобы пройти.
>> Итак, хэш-таблицы.
Это, пожалуй, наиболее полезно немного для PSET
здесь, потому что вы собираетесь быть реализации одного из них, или попытку.
Мне очень нравится, хэш-таблицы.
Они довольно прохладно.
>> Поэтому в основном то, что происходит это хэш-таблица
когда нам действительно нужно быстрое вставка, удаление, и поиск.
Те вещи, которые мы приоритетности в хэш-таблице.
Они могут получить довольно большой, но, как мы увидим с попыток,
Есть вещи, которые намного больше.
>> Но в принципе, все хеш таблица хэш-функция
что говорит вам, какие ведро положить друг Ваших данных, каждый из ваших элементов в.
Простой способ думать о хэш-таблице является то, что это всего лишь ведра вещей,
не так ли?
Итак, когда вы сортировки вещи как первую букву своего имени,
что вроде как хэш-таблицу.
>> Так что, если бы я был в группе, вы, ребята, это в группах, кто начинает имени
с здесь, или тот, кто день рождения в январе, феврале, марте,
независимо, то есть эффективно создание хэш-таблицу.
Это просто создание ведра, что Вы сортировки элементов в
так что вы можете найти их легче.
Так Таким образом, когда мне нужно чтобы найти один из вас,
У меня нет к поиску через каждый из ваших имен.
Я могу быть, как, ну, я знаю, что День рождения Даниэль является in--
АУДИТОРИЯ: --April.
СПИКЕР 1: Апрель.
Так я смотрю на мой апреля ведро, и если повезет,
она будет единственным в там и мое время был постоянным в этом смысле,
в то время как, если я должен смотреть через целую кучу людей,
это займет гораздо больше времени.
Так хэш-таблицы действительно всего ведра.
Легкий способ думать о них.
>> Так очень важная вещь о Хеш-таблица представляет собой хэш-функция.
Так о чем я только что говорил о, как Ваше первое письмо от вашего имени
или твой день рождения месяц, это идеи, которые
действительно коррелирует с хэш-функции.
Это просто способ решить, какие ведро Ты элемент попадает в, ОК?
Таким образом, для этой PSET, вы можете посмотреть почти любой хеш-функция вы хотите.
>> Не надо быть вашим собственным.
Есть некоторые действительно классные те из есть что делать всякие сумасшедшие математике.
И если вы хотите, чтобы ваш проверка орфографии супер быстрый,
Я бы определенно искать в одном из тех.
>> Но существуют и простые, как вычислительных
сумма словами, как каждая буква имеет свой номер.
Вычислить сумму.
Это определяет ведро.
Они также имеют полегче, что такие же, как все здесь,
все B здесь.
Любой из них.
>> В основном, это просто говорит вам, какие Индекс массива ваш элемент должен перейти в.
Просто решая bucket-- это все хеш-функция.
Так вот у нас есть пример, который просто первая буква строки
что я только что говорил о.
>> Так у вас есть хэш, это только Первая буква вашего струнного минус,
который даст вам некоторые число от 0 до 25.
И то, что вы хотите сделать, это убедитесь, что это представляет
размер вашей хэш table-- сколько есть ведра.
Со многими из них хеш-функции, они
собирается возвращаться значения, которые могли бы быть намного выше числа ковшей
что вы на самом деле есть в хэш-таблице,
так что вам нужно сделать уверен и мода на них.
В противном случае, он собирается сказать, ой, она должна быть в ведре 5000
но у вас есть только 30 ведра в ваш хэш-таблицы.
И, конечно, мы все знаем, что это собирается привести в некоторых сумасшедших ошибок.
Поэтому убедитесь, что мода на Размер вашего хэш-таблицы.
Прохладный.
Так столкновений.
Все ли хорошо до сих пор?
Mmhmm?
>> АУДИТОРИЯ: С чего бы это вернуть такую ​​массивную значение?
>> СПИКЕР 1: В зависимости от алгоритма что ваш хэш-функция использует.
Некоторые из них будут делать сумасшедший умножения.
И это все о получении равномерное распределение,
так они делают некоторые действительно сумасшедшие вещи иногда.
Это все.
Что-нибудь еще?
Хорошо.
>> Так столкновений.
В основном, как я уже говорил, в лучшем случае,
любое ведро я смотрю в это будет иметь одно,
так что я не должен смотреть на все, не так ли?
Я либо знаю, что там или это не, и это то, что мы действительно хотим.
Но если у нас есть десятки тысяч точки данных и меньше этого числа
ковшей, мы собираемся иметь Столкновения где в конце концов что-то
будет иметь в конечном итоге в Ведро, что уже есть элемент.
>> Таким образом, вопрос, что мы делаем в этом случае?
Что мы делаем?
У нас уже есть что-то там?
Есть ли у нас просто выбросить его?
>> Нет.
Мы должны держать их обоих.
Поэтому путь, который мы как правило, сделать это будет что?
Какова структура данных мы только что говорили о?
АУДИТОРИЯ: связанный список.
СПИКЕР 1: связанный список.
Так что теперь, вместо того, чтобы каждый из них Ведра только имея один элемент,
он собирается содержать связанный список элементы, которые были HASHED в него.
ОК, все ли вид это взяли?
Потому что мы не могли иметь массив потому что мы не знаем, как много вещей
собираются быть там.
Связанный список позволяет есть только точное число, что
хэшируются в этом ведре, не так ли?
>> Так линейного зондирования является в основном это idea--
это один из способов борьбы с столкновении.
Что вы можете сделать, это если в этот Дело, ягода была хэшируется в 1
и у нас уже есть что-то там, вы просто
продолжать идти вниз до тех пор, Вы найти свободный слот.
Это один из способов справиться с этим.
Другой способ справиться это с тем, что мы просто
called-- связаны список называется цепочки.
>> Так эта идея работает, если Ваш хеш-таблицы вы думаете
значительно больше, чем установить ваши данные, или если вам
хочу попробовать и минимизировать цепочки пока это не абсолютно необходимо.
Так одно линейное зондирования, очевидно, означает,
что ваш хэш-функции это не совсем так полезно
потому что вы будете в конечном итоге с помощью Ваш хэш-функция, попадая в точку,
Вы линейный датчик до какое-то место, что доступно.
Но сейчас, конечно, что-нибудь еще, что заканчивается там,
Вы будете иметь, чтобы поиск еще дальше вниз.
>> И есть намного больше Поиск расходы, которые
переходит в вводе элемент в хэш-таблице сейчас, не так ли?
И теперь, когда вы идете, и попытаться найти ягодка опять, вы собираетесь, чтобы прояснить его,
и он собирается сказать, ой, смотрите в ведро 1,
и это не будет в ведро 1, так что вы
придется пройти через остальные из них.
Так что иногда полезно, но в большинстве случаев,
мы собираемся сказать, что цепочки является то, что вы хотите сделать.
>> Таким образом, мы говорили об этом раньше.
Я немного забегаю вперед.
Но цепочки в основном, что каждый ведро в хэш-таблице
это просто связанный список.
>> Так еще один способ, или более технический способ, чтобы думать о хэш-таблице
является то, что это просто массив связанных списков, которые
когда вы пишете свой словарь и вы пытаетесь загрузить его,
думать о нем, как массив связанных списков
будет сделать это намного проще для вас, чтобы инициализировать.
>> АУДИТОРИЯ: Так хеш-таблицы имеет заранее определенный размер,
как [неразборчиво] ведер?
>> СПИКЕР 1: Право.
Так что имеет определенное количество Ковши, что вы determine--
которые вы, ребята, должны не стесняйтесь играть с.
Это может быть довольно прохладно чтобы посмотреть, что происходит
как вы измените свое количество сегментов.
Но да, это имеет установить количество ковшей.
Что позволяет соответствовать как многие элементы, как вам нужно
это отдельный цепочки, где вас связали списки в каждом ведре.
Это означает, что ваш хэш-таблицу будет точно размер
что вам это нужно, чтобы быть, не так ли?
Вот и вся точка связанных списков.
Прохладный.
>> Так что все там в порядке?
Хорошо.
Ах.
Что только что произошло?
Действительно сейчас.
Угадайте, кто-то убивает меня.
>> ОК, мы собираемся пойти в нах, которые немного сумасшедшим.
Мне нравится хэш-таблицы.
Я думаю, что они действительно здорово.
Пытается это круто, слишком.
>> Так кто-нибудь помнит, что попытка это?
Вы должны перешли это кратко в лекции?
Помнишь рода, как это работает?
АУДИТОРИЯ: Я просто кивая что мы действительно шли по ней.
СПИКЕР 1: Мы действительно идут по нему.
Хорошо, мы действительно собираемся идти за это теперь является то, что мы говорим.
>> АУДИТОРИЯ: Вот для поиска дерева.
>> СПИКЕР 1: Да.
Это поисковая дерево.
Удивительный.
Так что, одно заметить здесь, что мы смотрим на отдельных персонажей
здесь, не так ли?
>> Поэтому, прежде чем с нашим хэш-функции, мы смотрели на словах, как в целом,
и теперь мы смотрим более на персонажей, не так ли?
Поэтому у нас есть Максвелла сюда и Мендель.
Поэтому в основном try-- способ думать о том, что каждый уровень здесь
представляет собой массив из букв.
Так что это ваш корневой узел здесь, не так ли?
Это все символы алфавит для начала каждого слова.
>> И то, что вы хотите сделать, это скажем, в порядке, у нас есть некоторые M слово.
Мы собираемся искать Максвелла, так мы идем к М. и М точек в целом
другой массив, в котором каждый Слово, пока существует
это слово, которое имеет в качестве второго письма,
при условии, что есть слово, которое есть B в качестве второго письма,
он будет иметь указатель происходит в какой-то следующий массив.
>> Там, наверное, не Слово, которое MP-то,
так в P позиции в этом Массив, что это просто будет NULL.
Это бы сказал, хорошо, там нет ни слова что M последующим P, ОК?
Так что, если мы думаем о ней, каждый один из этих более мелких вещей
на самом деле один из них крупные массивы из A до Z.
Так что может быть одной из вещей, что это своего рода недостатком попробовать?
>> АУДИТОРИЯ: Много памяти.
>> СПИКЕР 1: Это тонна памяти, не так ли?
Каждый из этих блоков здесь представляет 26 места, 26 массив элементов.
Так пытается получить невероятно пространство тяжелым.
>> Но они очень быстро.
Так невероятно быстро, но действительно пространство неэффективно.
Вид должен выяснить из какой вы хотите.
Это действительно здорово для вашего PSET, но они занимают много памяти,
так что вы компромисс.
Да?
>> АУДИТОРИЯ: Можно ли будет настроить попытку, а затем
когда у вас есть все Данные в нем, что вы need--
Я не знаю, если это будет иметь смысл.
Я был избавиться от всех NULL символы, но затем
Вы не смогли бы индекс them--
>> СПИКЕР 1: Вы по-прежнему в них нуждается.
>> АУДИТОРИЯ: - точно так же каждый раз.
СПИКЕР 1: Да.
Вы нужны нулевые символы, чтобы Вы знаете, если есть не слово есть.
Бен у вас было что-то вы хотите?
Хорошо.
Ладно, так что мы собираемся идти немного более
в технических деталях позади попытаться работать через пример.
>> ОК, так что это одно и то же.
В то время как в связанном списке, наш главный вид of-- что слово, которое я хочу? -
как строить блок был узел.
В попытке, у нас также есть узел, но это определяется по-разному.
>> Таким образом, мы имеем некоторую Ьоо что представляет ли слово в действительности
существует в этом месте, а затем у нас есть некоторые массив here-- вернее,
это указатель на Массив состоит из 27 символов.
А это для, в данном случае, это 27-- Я уверен, что все вы, как, ждать,
есть 26 буквы алфавита.
Почему у нас 27?
>> Поэтому в зависимости от как вы это реализовать,
это от PSET, что разрешено для апострофы.
Так вот почему дополнительный один.
Вы также будете иметь в некоторые случаи нулевой терминатор
включен в качестве одного из персонажи, что это разрешено быть,
и вот как они проверяют, чтобы увидеть, если это конец слова.
Если вы заинтересованы, проверить Видео Кевина на study.cs50,
а также Википедии есть некоторые хорошие ресурсы там.
>> Но мы собираемся пройти через только отчасти о том, как вы могли бы работать через попытки
если вы дали один.
Поэтому у нас есть супер простой один здесь, что нет слов "летучая мышь" и "зум" в них.
И, как мы видим здесь, это мало места здесь
представляет нашу Ьоо что говорит, да, это слово.
А потом это пользуется нашим массивы символов, не так ли?
>> Итак, мы собираемся пройти через найти "битой" в этом попытки.
Так начинаются в верхней части, не так ли?
И мы знаем, что б соответствует второй индекс, второй элемент
в этом массиве, потому что и б.
Так примерно вторая.
>> И это говорит, в порядке, круто, следует, что в следующий массив, потому что, если мы помним,
это не что каждая из них фактически содержит элемент.
Каждый из этих массивов содержит указатель, не так ли?
Это важное различие, чтобы сделать.
>> Я знаю, что это будет be-- пытается являются очень трудно получить на первый раз,
поэтому, даже если это второй или третий раз
и он по-прежнему вид кажущейся трудно,
Я обещаю, если вы идете часы Короче завтра,
это, наверное, сделать намного больше смысла.
Это занимает очень много, чтобы переварить.
Я до сих пор иногда я как, ждать, что это попытка?
Как я могу использовать это?
>> Таким образом, мы б и в этом случае, которая является нашим вторым показателем.
Если бы мы имели, скажем, с или d или любой другой буквой,
мы должны отобразить эту спиной к индексу нашего массива, который соответствует.
Таким образом, мы бы как rchar, и мы просто вычесть от сопоставить его в 0 до 25.
Все хорошо, как мы Карта наших героев?
Хорошо.
>> Так мы идем ко второму и мы видеть, что, да, это не NULL.
Мы можем перейти к следующем массиве.
Таким образом, мы перейдем к этой следующей массива здесь.
>> И мы говорим: хорошо, теперь мы нужно ли это здесь.
Является нулевым или делает это на самом деле двигаться вперед?
Так на самом деле движется вперед в этом массиве.
И мы говорим: хорошо, т наша последняя буква.
Так мы идем в т в индексе.
А потом мы движемся вперед потому что есть еще один.
И это говорят в основном, что, да, он говорит, что есть слово here--
что если вы будете следовать этим Путь, вы приехали
при слове, которое мы знаем, "Летучая мышь".
Да?
>> АУДИТОРИЯ: Это стандартная иметь что как индекс 0, а затем есть своего рода в 1
или иметь в конце?
>> СПИКЕР 1: Нет.
Так что, если мы оглянемся на наш Декларация здесь, это логический,
так что это его собственный элемент в узле.
Так что это не часть массива.
Прохладный.
Так что, когда мы закончим наше слово, и мы в этом массиве, то, что мы хотим сделать
это сделать чек на это слово.
И в этом случае, он вернется да.
>> Так на этой ноте, мы знаем, что "зоопарк" - мы знаем, как люди, которые "зоопарк" это слово,
не так ли?
Но будут пытаться здесь будет говорят, нет, это не так.
И было бы сказать, что, потому что мы не обозначены как слова здесь.
Даже при том, что мы можем пройти до этого массива,
это попытка могла сказать, что, нет, зоопарк не в словаре
потому что у нас не обозначив его как таковой.
>> Так один из способов сделать that-- ой, извините, это один.
Таким образом, в данном случае, "зоопарк" не Слово, но это в нашей попытки.
Но в этом, сказать, что мы хотим его ввести слово "баня", то, что происходит
это мы следуем through-- B, A, т.
Мы в этом массиве, и мы идем искать ч.
>> В этом случае, когда мы посмотрите на указатель на час,
это указывает на NULL, ОК?
Так, если это не явно указывая на другого массива,
Вы предполагаете, что все указатели в этом массиве указывая на нуль.
Таким образом, в этом случае, ч указывает обнулить поэтому мы ничего не можем сделать,
так оно и вернется ложным, "баня" не здесь.
Так что теперь мы на самом деле собираюсь пройти через
как бы мы на самом деле сказать, что "зоопарк" находится в нашей попытки.
Как мы вставляем "зоопарк" в нашей попытки?
Таким образом, в одной и той же способом, что мы начали с наш связанный список, мы стартуем из корня.
Если вы сомневаетесь, начните с корень этих вещей.
>> И мы будем говорить, хорошо, г.
г существует в этом, и он делает.
Таким образом, вы, как перейти к Ваш следующий массив, ОК?
А потом на следующий, мы говорим, хорошо, действительно о существуют?
Он делает.
Это еще раз.
>> И так на нашем следующем, мы уже говорили, ОК, "зоопарк" уже существует здесь.
Все, что нужно сделать, это установить это равно истинно, что есть слово там.
Если вы следовали все до перед той точкой,
это слово, так что просто установить его равным такие.
Да?
>> АУДИТОРИЯ: Итак делает, что означает, что "ба" это слово также?
>> СПИКЕР 1: Нет.
Таким образом, в данном случае, "ба", мы получим здесь, мы бы сказали, это слово,
не, и это все равно будет не.
Хорошо?
Mmhmm?
>> АУДИТОРИЯ: Поэтому, как только вы это Слово и вы говорите, да, то это
будет содержать пойти в м?
>> СПИКЕР 1: Так что это имеет отношение к with-- вы загружаете это.
Вы говорите, "зоопарк" это слово.
Когда вы идете в check-- как, скажем, вы хотите сказать,,
значит "зоопарк" существуют в этом словаре?
Вы только собираетесь искать "зоопарк" а затем проверить, если это слово.
Вы никогда не собираетесь переехать до м, потому что это не
то, что вы ищете.
>> Так что, если мы на самом деле хотели добавить "ванну" в этой попытке,
мы будем делать то же самое как мы это делали с "зоопарком"
кроме мы увидим, что, когда мы попытаться добраться до ч, его не существует.
Таким образом, вы можете думать об этом как пытаются чтобы добавить новый узел в связанном списке,
таким образом, мы должны были бы добавить еще один один из этих массивов, как и.
И тогда то, что мы делаем, мы просто установить час элемент этого массива, указывающих на это.
>> И тогда то, что мы хотели бы сделать здесь?
Добавить это равно справедливо потому что это слово.
Прохладный.
Я знаю.
Пытается не самая захватывающая.
Поверьте мне, я знаю.
>> Так одно дело понимать, с попыток, Я сказал, что они очень эффективны.
Таким образом, мы видели они занять до тонну пространства.
Они вроде запутанной.
Так почему бы нам когда-либо использовать их?
Мы используем их, потому что они невероятно эффективен.
>> Так что если вы когда-либо ищете до Словом, вы только
ограничены по длине слова.
Так что если вы ищете Слово, которое имеет длину пять,
Вы только когда-либо придется сделать в большинстве пять сравнений, ОК?
Таким образом, это делает его в основном постоянной.
Как вставки и поиска в основном постоянная времени.
>> Так что если вы можете когда-либо получить что-то в постоянном времени,
это так же хорошо, как он получает.
Вы не можете поправиться, чем Постоянная времени для этих вещей.
Так, что является одним из Огромные плюсы попыток.
>> Но это много места.
Таким образом, вы вроде должны решить, что для вас важнее.
И на современных компьютерах, пространство, что попытка может занять до
может быть, не влияет Вы так много, но, может быть,
Вы имеете дело с чем-то что имеет гораздо, гораздо больше вещей,
и попробовать просто не разумно.
Да?
>> АУДИТОРИЯ: Подождите, так у вас есть 26 Буквы в каждом один?
>> СПИКЕР 1: Mmhmm.
Да, у вас есть 26.
У вас есть какой-то есть слово маркер, а затем у вас есть 26 указателей в каждом из.
И они point--
>> АУДИТОРИЯ: И каждый 26, они друг у 26?
>> СПИКЕР 1: Да.
И вот почему, как вы можете см, она расширяется довольно быстро.
Хорошо.
Таким образом, мы собираемся, чтобы получить в деревья, которые Я чувствую, что это проще и, вероятно,
быть миленький отсрочка от попыток есть.
Будем надеяться, что большинство из вас видели дерево раньше.
Не так, как довольно те, за пределами, которые я
не знаю, если кто- пошел на открытом воздухе в последнее время.
Я пошел сбор яблок в эти выходные, и о, черт возьми, это было красиво.
Я не знал, листья может выглядеть, что довольно.
>> Так что это просто дерево, не так ли?
Это лишь некоторые узел, и он указывает на кучу других узлов.
Как вы видите здесь, это вид повторяющейся темой.
Узлы, указывающий на узлах является своего рода Сущность многих структур данных.
Все зависит от того, как мы чтобы они указывают друг с другом
и как мы пересекаем через них и, как мы
вставить то, что определяет их различные характеристики.
>> Так что некоторые термины, которые я использовал раньше.
Так корень все, что находится на самом верху.
это где мы всегда начинаем.
Вы можете думать об этом как глава также.
Но для деревьев, мы, как правило, относятся к нему как корень.
>> Все в нижней here-- в очень, очень bottom--
считаются листья.
Так что идет вместе с все дерево, что, не так ли?
Листья по краям дереве.
>> И тогда у нас также есть несколько Условия говорить о узлах связи
друг к другу.
Поэтому у нас есть родитель, дети, братья и сестры.
Таким образом, в данном случае, является 3 Родитель 5, 6, и 7.
Так родитель все, что один шаг выше, что вы находитесь
со ссылкой на, так что просто как родословной.
Будем надеяться, что это все немного немного более понятным, чем попыток.
>> Братья и сестры являются любые, которые имеют то же самое родитель, не так ли?
Они на том же уровне, здесь.
А потом, как я был говоря, дети просто
все, что на один шаг ниже данный узел, ОК?
Прохладный.
Так бинарное дерево.
Может кто-нибудь догадку на одном из характеристики бинарного дерева?
>> АУДИТОРИЯ: Макс два листа.
>> СПИКЕР 1: Право.
Так макс двух листьев.
Таким образом, в этот прежде, у нас был этот один что было три, но в бинарном дереве,
у вас есть макс двух детей на родителей, не так ли?
Там другая Интересной особенностью.
Кто-нибудь знает, что?
Бинарное дерево.
>> Так бинарное дерево будет иметь все на the-- этот не sorted--
но в отсортированный бинарного дерева, все справа
больше, чем родителей, и все слева
меньше, чем родителей.
И что было викторина Вопрос прежде, так хорошо знать.
Так как мы определяем это, снова, у нас есть еще один узел.
Это выглядит очень похоже на что?
Вдвойне
>> Аудитория: Связанные списки
>> СПИКЕР 1: двойной связанный список, не так ли?
Так что, если мы заменим этот с предыдущим и следующим,
это было бы вдвойне связанный список.
Но в данном случае, мы на самом деле есть левый и правый, и этим все сказано.
В противном случае, это точно так же.
У нас еще есть элемент Вы ищете,
и вы просто должны два указателя собирается все, что будет дальше.
Да, так бинарное дерево.
Если мы замечаем, все на здесь больше than--
или все сразу чтобы прямо здесь
больше, чем все, здесь меньше.
>> Так что, если бы мы должны были искать через, его должен выглядеть очень близко к бинарного поиска
здесь, не так ли?
Кроме вместо того чтобы искать на половине массива,
мы просто глядя на любом слева сторона или правая сторона дерева.
Так он получает немного проще, я думаю.
>> Так что если ваш корень NULL, Очевидно, что это просто ложь.
И если это есть, очевидно, что это правда.
Если это меньше, чем, мы ищем левого.
Если это больше, чем, мы ищем право.
Это так же, как бинарный поиск, просто другая структура данных
что мы используем.
Вместо массива, это просто бинарное дерево.
>> ОК, стеки.
А также, похоже, что мы может иметь немного времени.
Если мы это сделаем, я счастлив пойти за все это снова.
Итак, стеки.
Кто-нибудь помнит, что stacks-- любые характеристики стека?
>> Итак, большинство из нас, я думаю, что, едят в столовой halls--
столько, сколько мы, возможно, не нравится.
Но очевидно, что вы можете думать о стеке буквально только в виде стопки лотков
или стопка вещей.
И, что важно чтобы понять, что это
something-- характеристика что мы называем это по-- является ЛИФО.
Кто-нибудь знает, что это означает?
Mmhmm?
>> АУДИТОРИЯ: последним пришел, первым из.
>> СПИКЕР 1: справа, последним пришел, первым из.
Так что, если мы знаем, если мы укладка вещей до, проще всего захватить off--
и, может быть, единственное, что мы можем захватить , если бы наш стек большой enough--
является то, что верхний элемент.
Поэтому, что бы было поставить на last-- как мы видим здесь,
что было толкнул на наиболее recently-- является
будет первым вещь, которую мы палить, ОК?
>> Итак, что мы имеем здесь дело другой ЬурейеЕ структура.
Это на самом деле просто хотел Crash Course в структуре данных,
так что есть много брошены на вас, ребята.
Я знаю.
Так еще один структура.
Ура для структур.
>> И в этом случае, это какая-то указатель в массив, который имеет определенный потенциал.
Таким образом, это представляет наш стек здесь, как и наш фактический массив
что держит наши элементы.
А потом здесь у нас есть некоторые размеры.
>> И, как правило, вы хотите, чтобы сохранить трек, насколько большой ваш стек
потому, что он собирается, чтобы позволить Вы сделать это, если вы знаете размер,
это позволяет сказать, ОК, я на полную мощность?
Могу ли я добавить ничего больше?
И это также говорит вам, где в верхней части вашего стека
так вы знаете, что вы может на самом деле снять.
И что на самом деле происходит в быть немного более ясно.
>> Таким образом, для толчка, С одной стороны, если вас были когда-либо реализовать толчок,
как я только что говорил, ваша Стек имеет ограниченный размер, не так ли?
Наш массив был некоторый потенциал.
Это массив.
Это фиксированный размер, так что нам нужно убедиться, что мы не ставили больше
в нашем массиве, чем мы на самом деле есть место для.
>> Так что, когда вы создаете толчок Функция, первое, что вам сделать, это скажем, в порядке,
у меня есть место в моей стека?
Потому что, если я не делаю, извините, Я не могу хранить элемент.
Если я, то вы хотите сохранить это на вершине стека, не так ли?
>> И именно поэтому у нас есть отслеживать нашего размера.
Если мы не отслеживать нашего размера, мы не знаем, куда его положить.
Мы не знаем, как много вещей в нашем массиве уже.
Как очевидно, есть способы что, может быть, вы могли бы сделать это.
Вы можете инициализировать все, чтобы NULL а затем проверить наличие последней NULL,
но гораздо проще вещь просто сказать, в порядке, отслеживать размер.
Как я знаю, у меня есть четыре элемента в моем массиве, так следующая вещь
что мы ставим на, мы собираетесь хранить в индексе 4.
И тогда, конечно, это означает, что Вы успешно толкнул что-то
на свой стек, вы хочу увеличить размер
так что вы знаете, где вы находитесь, так что вы можете нажать больше вещей на.
>> Так что, если мы пытаемся поп что-то из стека,
что может быть в первую очередь что мы хотим, чтобы проверить?
Ты пытаешься взять что-то от вашего стека.
Вы уверены, что есть что-то в вашем стеке?
Нет.
Так что, возможно, мы хотим проверить?
>> АУДИТОРИЯ: [неразборчиво].
СПИКЕР 1: Проверьте размер?
Размер.
Поэтому мы хотим, чтобы проверить, если наш размер больше 0, ОК?
И если это так, то мы хотим, чтобы уменьшить наш размер 0 и вернуть это.
Почему?
>> В первом из них мы были толкая, мы выдвинули его
на размер и затем обновленной размера.
В этом случае, мы уменьшая размер и то, принимая его, выщипывание его
из нашего массива.
Почему мы можем это сделать?
Так что, если у меня есть одна вещь, на мой стек, что бы мой размер на тот момент?
1.
>> А где элемент 1 хранится?
На то, что индекс?
АУДИТОРИЯ: 0.
СПИКЕР 1: 0.
Таким образом, в данном случае, мы всегда нужно делать sure--
вместо того чтобы вернуться размер минус 1, потому что мы
знаем, что наш элемент будут храниться на 1 меньше
все наш размер, это просто заботится о нем.
Это немного более элегантный способ.
И мы просто уменьшить OUR Размер, а затем вернуть размер.
Mmhmm?
>> Аудитория: Я думаю, просто в целом, зачем эта структура данных
быть полезным?
>> СПИКЕР 1: Это зависит от контекста.
Таким образом, для некоторых из теории, если вы работаете with-- ОК,
дайте мне посмотреть, есть ли выгодно один что является полезным для более, чем снаружи
из CS.
С стеков, в любое время вам нужно отслеживать то, что
является наиболее недавно добавленного, когда Вы собираетесь хотите использовать стек.
>> И я не могу думать о хорошем пример, что сейчас.
Но всякий раз, когда самая последняя Дело в том, наиболее важны для вас,
вот когда стек будет полезно.
Я пытаюсь думать, если есть хороший вариантом.
Если я думаю о хорошем, например, в следующем 20 минут, я, безусловно, скажу вам.
>> Но в целом, если есть что-нибудь, как я сказал, что большинство, где последняя
самое главное, что это где стопка вступает в игру.
В то время как очереди являются своего рода противоположность.
И все маленькие собаки.
Разве это не здорово, не так ли?
Я чувствую, что должен просто есть кролик видео
прямо в середине раздел для вас, ребята
потому что это является интенсивным раздел.
>> Так очереди.
В основном очереди как линия.
Вы, ребята, я уверен, что использование этого каждый день, точно так же как в наших столовых.
Таким образом, мы должны пойти в и получить в свои лотки, я
что у вас есть, чтобы стоять в очереди салфетки или получить вашу еду.
>> Таким образом, разница здесь в том, что это FIFO.
Так что, если ЛИФО последний раз был в первую вне, FIFO является первым пришел, первым ушел.
Так что это, где все, что вы положили на первый ваш самый важный.
Так что, если вы ждали в line-- могу вас
Представьте себе, если вы пошли в пойти получить новый iPhone
и это был стек, где последний человек в линии получил его первым,
люди будут убивать друг друга.
>> Так FIFO, мы все хорошо знакомы с в реальном мире здесь,
и все это имеет отношение к действительности вид воссоздания всю эту линию
и очередей структуру.
Так в то время как со стеком, у нас есть толчок и поп-музыки.
С очередь, мы имеем поставить в очередь и удаления из очереди.
Так поставить в очередь в основном означает, положить его на спину,
и вывода из средств взять от с фронта.
Таким образом, наша структура данных немного сложнее.
У нас есть второе, для отслеживания.
>> Так что без головы, это именно стек, не так ли?
Это то же самое строение, как стек.
Единственное отличие в настоящее время является у нас есть эта голова, которая, что вы думаете
собирается отслеживать?
>> АУДИТОРИЯ: Первый.
>> СПИКЕР 1: справа, Первое, что мы вкладываем в.
Глава нашего очереди.
Тот, кто это первый в очереди.
Ладно, так что если мы делаем в очередь.
Опять же, с любым из эти структуры данных,
так как мы имеем дело с массивом, мы должны проверить, если у нас есть пространство.
>> Это вроде как мне рассказывал ребята, если вы открываете файл,
Вы должны проверить на нуль.
С любой из этих стеков и очереди, вам нужно
чтобы увидеть, если есть свободное место, потому что мы дело с массивом фиксированного размера,
как мы видим, here-- 0, 1 всего до 5.
Так, что мы делаем в этом случае является проверка чтобы увидеть, если у нас еще есть пространство.
Является ли наша размер меньше мощности?
>> Если это так, мы должны хранить его в хвост, и мы обновим наш размер.
Так что, возможно, хвост будет в этом случае?
Это явно не выписаны.
Как бы мы храним это?
Что бы хвост быть?
>> Так что давайте идти через этот пример.
Так что это массив размером 6, не так ли?
И у нас есть сейчас, наш размер 5.
И когда мы ставим его в, он собирается идти в пятом индекса, не так ли?
Так хранить в хвосте.
>> Еще один способ написать хвост бы просто быть наш массив с индексом размера, не так ли?
Это размер 5.
Следующая вещь, которую собирается пойти в 5.
Прохладный?
Хорошо.
Это становится немного сложнее, когда мы начинаем баловаться с головой.
Да?
>> АУДИТОРИЯ: Означает ли это, что мы объявил бы массив,
было давно пять элементов и Затем мы добавляем на него?
>> СПИКЕР 1: Нет.
Таким образом, в данном случае, это стек.
Это будет объявлен в виде массива размером 6.
И в этом случае мы есть только один космический влево.
>> Итак, одно дело находится в этом так, если наша голова на 0,
Затем мы просто можете добавить его в размерах.
Но это становится немного сложнее потому что на самом деле, они
нет слайд для этого, так что я собираюсь
чтобы сделать один, потому что это не так просто, как только вы
начать избавление от вещей.
Так в то время как со стеком Вы только когда-либо
беспокоиться о том, что размер когда вы добавляете что-то на,
с очередью вы также должны убедиться, Убедитесь, что ваша голова приходилось,
потому что здорово, что об очередях является то, что, если вы не на полную мощность,
вы можете сделать это обернуть вокруг.
>> Итак, один thing-- о, это ужасно мел.
Одна вещь, чтобы рассмотреть это дело.
Мы просто делаем пять.
Итак, мы собираемся говорят голова здесь.
Это означает 0, 1, 2, 3, 4.
>> Глава там, и пожалуйста, что в них.
И мы хотим, чтобы добавить что-то в, не так ли?
Так, что мы должны знаю, что голова всегда
будет двигаться этим путем и Затем цикл назад вокруг, ОК?
>> Так эта очередь имеет место, не так ли?
В нем есть место в самом начале, вид противоположности это.
Так что нам нужно сделать, это мы нужно рассчитать хвост.
Если вы знаете, что ваш голова не переехал, хвост
просто ваш массив в Индекс размера.
>> Но на самом деле, если вы используете очередь, Ваша голова, вероятно, обновляется.
Так что вам нужно сделать, это на самом деле вычислить хвост.
Так что мы делаем, это формула здесь, которые я собираюсь дать вам
ребята, думаете о, и тогда мы будем говорить об этом.
Так что это мощность.
>> Так что это будет на самом деле дать вам способ сделать это.
Потому что в этом случае, то, что?
Наша голова на 1, наш размер 4.
Если мы мод, что на 5, получаем 0, который является, где мы должны ввести его.
>> Так то в следующем случае, если мы должны были сделать это,
мы говорим, хорошо, давайте из очереди что-то.
Мы из очереди это.
Вынимаем этот элемент, не так ли?
>> И теперь наша голова указывая здесь, и мы хотим добавить в другом.
Это, в основном назад от нашей линии, не так ли?
Очереди могут обернуть вокруг массива.
Это одна из основных отличий.
Стопки, вы не можете сделать это.
>> С очередями, вы можете потому что все, что имеет значение
является то, что вы знаете, что совсем недавно был добавлен.
Поскольку все будет добавлен в это направление влево, в этом случае,
а затем обернуть вокруг, вы можете продолжить ввод новых элементов
в передней части массива потому что это не действительно
передняя часть массива больше.
Вы можете думать о начале Массив как где ваша голова на самом деле.
>> Так эта формула, как Вы рассчитать свой хвост.
Значит ли это, имеет смысл?
Хорошо.
ОК, из очереди, а затем вы, ребята, есть 10 минут
задавать мне любые уточняющие вопросы Вы хотите, потому что я знаю, что это сумасшедший.
>> Ладно, так в том же way-- Я не знаю, если вы, ребята заметили,
но CS это все о узорами.
Вещи довольно много же, только с крошечными ухищрений.
Так же и здесь.
Нам нужно проверить, чтобы увидеть, если мы на самом деле есть что-то в нашей очереди, верно?
Скажем, в порядке, наша размер больше 0?
Прохладный.
>> Если мы это сделаем, то мы перенесем наше голову, которая это то, что я только что продемонстрировал здесь.
Мы обновляем нашу голову еще одна.
А потом мы уменьшаем наши Размер и возвращает элемент.
>> Существует гораздо больше бетона Код на study.cs50.net,
и я очень рекомендую движение через него, если у вас есть время,
даже если это всего лишь псевдо-код.
И если вы, ребята, хотите поговорить через что со мной один на один, пожалуйста, сообщите мне,
знаю.
Я был бы счастлив.
Структуры данных, если вы берете CS 124, вы будете
знаю, что структуры данных получить очень весело и это только начало.
>> Так что я знаю, это трудно.
Это нормально.
Мы боремся.
Я до сих пор.
Так что не беспокойтесь об этом слишком много.
>> Но это в основном программы Your Crash Course в структурах данных.
Я знаю, что это много.
Есть что-нибудь, что мы хотел бы пойти снова?
Все, что мы хотим поговорить через?
Да?
>> АУДИТОРИЯ: Для этого, например, так новый хвост на 0 над этим?
СПИКЕР 1: Да.
АУДИТОРИЯ: ОК.
Итак переживает, Вы должны были бы 1 плюс 4 или--
>> СПИКЕР 1: Итак, вы говорили, когда мы хотим пойти и сделать это снова?
АУДИТОРИЯ: Да.
Так что, если вы были выяснить out-- где Вы расчете хвост из в том, что?
>> СПИКЕР 1: Так хвост был in-- я изменил это.
Таким образом, в этом примере здесь, это было массив, мы смотрим на, ОК?
Поэтому у нас есть вещи, в 1, 2, 3, и 4.
Поэтому у нас есть наша голова равна 1 на эта точка, и наш размер равен 4
на данный момент, не так ли?
>> Вы все согласны, что это так?
Так мы делаем голову плюс размер, который дает нам 5, а затем мы мод на 5.
Мы получаем 0, которая говорит нам, что 0 является где наша хвост, где у нас есть пространство.
>> АУДИТОРИЯ: Что шапка?
>> СПИКЕР 1: Емкость.
Извините.
Так что это размер вашего массива.
Да?
>> АУДИТОРИЯ: [неразборчиво], прежде чем мы возвращает элемент?
>> СПИКЕР 1: Так мы движемся возглавить или вернуть время?
Так что, если мы перейдем один, уменьшить размер?
Удерживать.
Я определенно забыл еще один.
Ничего.
Существует не одна формула.
Да, вы хотели бы, чтобы вернуться глава, а затем вернуть его обратно.
>> АУДИТОРИЯ: ОК, потому что в это Точка, голова была на 0,
а затем вы хотите, чтобы вернуться Индекс 0, а затем сделать головной 1?
>> СПИКЕР 1: Право.
Я думаю, что есть еще один Формула вроде как это.
У меня нет его на верхней голову, как Я не хочу, чтобы дать вам не тот.
Но я думаю, что это вполне допустимо, чтобы скажем, в порядке, хранить эту element-- все
элемент голова is-- уменьшить ваш размер, перемещать голову над, и возвращение
все, что элемент.
Это совершенно справедливо.
Хорошо.
Я чувствую, что это не как most-- вы не
собирается выйти отсюда как, да, я знаю попыток.
Я получил все это.
Это хорошо.
Я обещаю.
Но структуры данных являются чем-то, что она занимает много времени, чтобы привыкнуть.
Вероятно, это один из самых сложных вещи, я думаю, что, в курсе.
>> Так что, безусловно, занимает Повторение и глядя at-- I
на самом деле не знаю, связные списки пока я не сделал слишком много с ними,
таким же образом, что не сделал действительно понять указатели
пока у меня не было, чтобы научить его на двоих лет и сделать свои собственные psets с ним.
Это занимает много повторения и время.
И в конце концов, это будет своего рода нажмите.
>> Но в то же время, если у вас есть вид из глубокого знакомства с того, что
это сделать, их плюсы и cons-- что и
мы действительно, как правило, подчеркивают, особенно в интро конечно.
Мол, зачем нам использовать попробуйте над массивом?
Мол, то, что положительные стороны и негативы каждого из них?
>> И понимание компромиссов между каждой из этих структур
является то, что гораздо более важно сейчас.
Там может быть один сумасшедший Вопрос или два это
попрошу вас, чтобы реализовать толчок или осуществить поп или поставить в очередь и удаления из очереди.
Но по большей части, имеющие, что выше понимание уровня и более
из интуитивное понимание является важнее, чем на самом деле
будучи в состоянии его реализовать.
>> Это было бы действительно здорово, если вы все могли выйти и пойти реализовать попытку,
но мы понимаем, что это не обязательно самое разумное сейчас.
Но вы можете в PSET, если вы хотите на, а затем вы получите практику,
и тогда, возможно, вы будете действительно понимаю.
Да?
>> АУДИТОРИЯ: ОК, так, какие из них мы хотели использовать в PSET?
Нужно ли использовать одну из них?
СПИКЕР 1: Да.
Так у вас есть выбор.
Я думаю, в этом случае, мы можем говорить о PSET немного
потому что я пробежал эти.
Так что в вашем PSET, у вас есть свой Выбор попыток или хэш-таблицы.
Некоторые люди будут пытаться и использовать цветения фильтры,
но те, технически не правильно.
Из-за их вероятностный характер, они дают ложные срабатывания иногда.
Они холодный взгляд в, хотя.
Очень рекомендую глядя на них, по крайней мере.
Но у вас есть выбор между хэш-таблицу и попробовать.
И что будет, когда Вы загружаете в словаре.
>> И вы должны будете выбрать Ваш хэш-функция,
Вы должны будете выбрать, сколько Ведра у вас есть, и она будет меняться.
Как если у вас есть больше ведра, может быть, он будет работать быстрее.
Но, может быть, вы зря много места, что путь, хотя.
Вы должны понять это.
Mmhmm?
>> АУДИТОРИЯ: Вы говорили, что мы можем использовать другие хэш-функций,
что мы не должны создать хэш-функции?
>> СПИКЕР 1: Да, верно.
Так буквально за хэш-функции, Как и Google "хэш функция"
и искать какие-то новых и прикольных.
Вы не предполагается построить Ваши собственные хэш-функции.
Люди тратят их тезисы о этих вещах.
>> Так что не беспокойтесь о строительстве самостоятельно.
Найти одно онлайн, чтобы начать с.
Некоторые из них вы должны манипулировать немного
чтобы убедиться, что возвращаемые типы совпадают и еще много чего, так что в начале,
Я бы рекомендовал использовать что-то очень легко, что, может быть, просто
хэши по первой букве.
А потом, как только у вас есть, что работу, включения кулер хеш-функции.
Mmhmm?
>> АУДИТОРИЯ: бы попробовать быть или эффективным, но только сложнее, like--
>> СПИКЕР 1: Так попробовать, я думаю, Интуитивно трудно реализовать
но очень быстро.
Тем не менее, занимает больше места.
Опять же, вы можете оптимизировать и тех, кто в различные способы и есть способы to--
АУДИТОРИЯ: Как мы оцениваются по этому поводу?
Значит ли это matter--
>> СПИКЕР 1: Итак, вы оцениваются обычным способом.
Вы собираетесь оцениваются по дизайну.
Какой бы путь вы ни делали, вы хотите, чтобы убедитесь, что это так элегантно, как это может быть
и так эффективно, как это может быть.
Но если вы выбираете попытку или хэш Таблица тех пор, пока он работает,
мы довольны, что.
А если вы используете что-то, что хэши по первой букве, это нормально,
как, может быть, как дизайн-мудрым.
Мы также достижения Точка в этом semester--
Я не знаю, если вы Ребята noticed-- если вы
Pset сорта снижаться немного из-за дизайна и еще много чего,
это прекрасно.
Это становится в точку, где ваш Программы становятся все более сложными.
Есть еще места Вы можете улучшить.
>> Так что это совершенно нормально.
Это не то, что вы делает хуже на PSET.
Это просто мы быть сильнее на вас сейчас.
Таким образом, каждый чувствует это.
Я просто оцениваются все ваши psets.
Я знаю, что все чувствуют это.
>> Так что не беспокойтесь об этом.
И если у вас есть какие-либо вопросы Предыдущие psets или способов, вы можете улучшить,
Я стараюсь и комментировать конкретные места, но иногда это поздно
и я устаю.
Есть ли другие вещи около структуры данных?
Я уверен, что вы, ребята, не очень хочу поговорить о них больше,
но если есть, я счастлив идти по ним, а также что-нибудь
Из лекции в минувшую неделю или на прошлой неделе.
>> Я знаю, на прошлой неделе было все обзор, так мы, возможно, пропустили в течение некоторого пересмотра
от лекции.
Любые другие вопросы я могу ответить?
ОК, все в порядке.
Ну, вы, ребята, выходите 15 минут раньше.
>> Я надеюсь, что это был полу-полезными, по крайней мере, и я буду видеть вас, ребята на следующей неделе,
или четверг рабочие часы.
Есть просит для закусок на следующей неделе, это-то и дело?
Потому что я забыл конфеты сегодня.
И я принес конфеты последний неделю, но это был День Колумба,
таким образом, было как шесть человек, которые было четыре мешка конфет к себе.
Я могу привести Starbursts снова, если вам нравится.
Starbursts?
Хорошо, хорошо звучит.
Имейте большой день, ребята.