СПИКЕР 1: Ладно, так что это CS50 Это конец пятой неделе. И напомним, что в прошлый раз мы начал искать в данных любитель структуры, которые начали решать проблемы, которые начали вводить новые проблемы, но ключом к этому был своего рода резьбы, что мы начал делать от узла к узлу. Так что это, конечно, однократно связанный список. И односвязанны, Я имею в виду есть только один нить между каждым из этих узлов. Оказывается, можно сделать любитель вещи, как дважды связанные списки в результате чего у вас есть стрелка происходит в обоих направлениях, что может помочь с некоторыми эффективности. Но это решить проблему? Какие проблемы это решить так? Почему мы заботимся в понедельник? Почему, в теории, так и мы заботимся в понедельник? Что оно делает? 

АУДИТОРИЯ: Мы можем динамически изменить ее размер. 

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

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

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

Так что это лишь некоторые С-код, даже не полная программа что я действительно быстро соорудил. Это не онлайн в распределении Код, потому что он не будет реально работать. Но обратите внимание, Я только с комментарием сказал, точка точка точка, есть что-то там, точка точка точка, что-то там. И давайте просто посмотрим на то, что сочные части. Так что на третьей линии, Напомним, что это теперь Мы предложили объявить узел последний Время, один из тех прямоугольных объектов. Он имеет Int, что мы назовем N, но мы могли бы назвать это что-нибудь, а затем структура узла звезда называется рядом. И только, чтобы быть ясным, что во втором линия, на шестой строке, что это такое? Что он делает для нас? Потому что, конечно, выглядит более загадочными, чем наши обычные переменные. 

АУДИТОРИЯ: Это заставляет его двигаться по одному. 

СПИКЕР 1: заставляет его двигаться по одному. И если быть более точным, он будет хранить адрес узла, который предназначается, чтобы быть семантически рядом с ним, верно? Так что не собирается обязательно двигаться ничего. Это просто будет хранить значение, которое будет адрес какого-то другого узла, и вот почему мы сказали структура узел звезда, звезда, обозначающий указатель или адрес. ОК, так что теперь если предположить, что мы имеем это N доступны для нас, и давайте Предположим, что кто-то еще вставляется целую кучу целых чисел в связанном списке. И, что связано список указывает какой-то момент переменная называется список, что это прошел здесь в качестве параметра, как я могу идти о линии 14 осуществлении поиска? Другими словами, если я реализую Функция, цель которого в жизни это принять Int и затем начало связанного списка, что указатель на связанный список. Как первые, кто я думаю, Дэвид был наш волонтер в понедельник, он, указывая на вся связанный список, Это как если бы мы передаем Дэвид, как наш аргумент здесь. Как мы можем идти о прохождении этот список? Что ж, оказывается, что, хотя указатели являются относительно новыми в настоящее время для нас, мы можем сделать это относительно прямо. 

Я собираюсь идти вперед и объявить временную переменную, что по соглашению только собирается чтобы назвать указатель, или PTR, но вы могли бы назвать это все, что вы хотите. И я собираюсь инициализации это в начале списка. Таким образом, вы можете бы думаю это а мне учителя днях, вид, указывая на кого-то среди наших людей в качестве добровольцев. Так что я временную переменную, что это просто указывая на то же самое что наш совпадению имени Работа на общественных началах Давид указывал. Теперь в то время как указатель не нулевой, потому что отзыв что нулевая некоторые особое значение сторожевого разграничивает конец списка, так что пока я не указывая на земля, как наш последний волонтер было, давайте идти вперед и выполните следующие действия. Если pointer-- и теперь я как бы хочу делать то, что мы сделали с учеником structure-- если указатель точка рядом equals-- скорее, если указатель точка N равен равна переменная N, то Аргумент, который был принят в, то я хочу, чтобы идти вперед и сказать, вернуться правда. Я нашел номер N внутри один из узлов моего связанного списка. Но больше точка не работает в данном контексте, потому что указатель, PTR, это действительно указатель, адрес, мы на самом деле можем чудесно использовать наконец кусок синтаксиса что вид делает интуитивное чувство, а на самом деле использовать стрелку здесь, что означает, идут от что обращение к целому там в. Так что это очень похоже на дух оператора точка, а потому, что указатель не является указателем и сам по себе не фактический структура, мы просто использовать стрелку. 

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

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

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

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

Так что, если я хочу, чтобы подтолкнуть то в стек, Полагаю, я вызвать функцию толчок, и Я говорю нажать 50, как и число 50, где вы могли бы предложить Я рисую его в этом массиве? Там в пять различных возможных ответов. Где вы хотите, чтобы подтолкнуть число 50? Если цель здесь, опять же, называем Функция толчок, проходят в качестве аргумента 50, где я положил его? Пять possible-- 20% шанс гадать правильно. Да? 

АУДИТОРИЯ: Дальний право. 

СПИКЕР 1: Дальний право. Существует в настоящее время 25% шанс гадать правильно. Так что будет на самом деле будет в порядке. По соглашению, я скажу с массивом, мы, как правило, начинают с левой, но мы, безусловно, может начать с правой. Таким образом, спойлер здесь будет я вероятно, собирается привлечь его слева, Как и в обычном массиве где Я начать двигаться слева направо. Но если вы можете перевернуть арифметическое, отлично. Это просто не обычный. ОК, мне нужно, чтобы сделать один больше изменений, хотя. Теперь, когда я толкнул что-то стек, что дальше? 

Ладно, у меня есть, чтобы увеличить размер. Итак, позвольте мне идти вперед и просто обновить это, который был равен нулю. И вместо того, в настоящее время, я иду положить в стоимости одного. А теперь предположим, я нажимаю другую Количество в стек, как 51. Ну, я должен сделать еще один изменение, которое до размера двух. А потом думаю, я нажимаю еще один Количество в стек, как 61, Теперь мне нужно, чтобы обновить еще один размер время и получить значение 3 в качестве размера. И теперь, я называю поп-музыки. Теперь поп, по соглашению, не принимать аргумент. Со стеком, вся точка метафоры лоток является то, что вы не по своему усмотрению пойти получить этот лоток, все можно сделать поп верхний один из стек, только потому, что. Это то, что эта структура данных делает. 

Итак, этой логике, если я говорят поп, то, что приходит от? Так 61. Так что на самом деле компьютер собираемся делать в памяти? Что мой код нужно сделать? Что вы могли бы предложить мы меняем на экране? Что должно измениться? Сожалею? Так мы избавимся от 61. Так что я могу определенно сделать. И я могу избавиться от 61. И тогда то, что другие изменение должно произойти? Размер, вероятно, имеет вернуться к двум. И так, что все в порядке. Но подождите минуту, размер Минуту назад было три. Давайте просто сделать быструю проверку вменяемости. Как мы знаем, что мы хотел, чтобы избавиться от 61? Потому что мы появляться. И поэтому у меня есть этот второй размер собственности. 

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

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

Теперь, почему это? Теперь мы просто должны быть комфортно с тот факт, что, когда работает мой программы, Я, вероятно, собирается должны спросить человека, сколько номеров вы хотите сохранить? Таким образом, вход должен откуда-то. Но как только я знаю, что число, то я могу только использовать то, что работать, чтобы дать мне кусок памяти? Я могу использовать таНос. И я могу сказать, любое количество байт я хочу вернуться на эти Nths. И все, что нужно хранить в цифрах Переменная здесь внутри этой структуры должно быть что? Что на самом деле происходит в Цифры в этом случае? Да, это указатель на первый байт этого куска памяти, или, более конкретно, адрес из первых из этих байт. Не имеет значения, если это один байт или байт, млрд Мне просто нужно, чтобы заботиться о первой. Потому что то, что таНос гарантии и мои операционной системы гарантий, является то, что кусок памяти I получить, он собирается быть смежными. Там не будет пробелов. Так что, если я попросил 50 байт или 1000 байт, они все будет спина к спине к спине. И так долго, как я помню, как большой, как много я попросил, все мне нужно знать первый такой адрес. 

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

Почему это не достаточно иметь только размер? Ну, давайте толкать эти же цифры на. Так что я pushed-- я в очередь, или толкнул. Теперь я в очередь 50, а затем 51, а затем 61, и точка точка точка. Так вот поставить в очередь. Я в очереди 50, то 51, то 61. И, что выглядит идентично в стек до сих пор, кроме мне нужно сделать одно изменение. Мне нужно, чтобы обновить этот размер, так что я иду от нуля до единицы до двух-трех Теперь. Как из очереди? Что происходит с DEQUEUE? Кто должен прийти из этого списка в первую очередь если это линия на Apple Store? Так 50. Так что это своего рода сложнее в этот раз. В то время как последний раз это было супер просто, чтобы просто делать размер минус один, Я до конца моей массива эффективно где цифры, это снимает 61. Но я не хочу, чтобы удалить 61. Я хочу взять 50, которые был там в 5:00 выстраиваться для Новый iPhone или еще много чего. И так, чтобы избавиться от 50, я не можете просто сделать это, не так ли? Я могу вычеркнуть 50. Но мы только что сказали, мы не должны быть настолько анальный чтобы выцарапать или скрыть данные. Мы можем просто забыть, где она есть. 

Но если я могу изменить мой размер теперь два, это достаточно информации чтобы знать, что происходит в моей очереди? На самом деле, нет. Как мой размер в два, но где же очереди начинают, особенно если я до сих пор те же номера в памяти. 50, 51, 61. Поэтому мне нужно помнить, Теперь, когда фронт. И таким образом, я предложил до там, мы только что называется N-й фронт, чей первоначальный Значение должно быть что? Ноль, только начало списка. Но теперь в дополнение к уменьшая размер, мы просто увеличиваем фронт. Теперь вот другая проблема. Поэтому, как только я все время. Предположим, что это число как 121, 124, а затем, черт возьми, Я из космоса. Но подождите минуту, я не являюсь. Таким образом, на данный момент в истории, Предположим, что размер одного, двух, три, четыре, так что предположим, что размер четыре, передняя одна, так 51 на фронте. Я хочу поставить еще один номер здесь, но, черт возьми, я из космоса. Но я не очень, не так ли? Где я могу поставить некоторые дополнительная стоимость, как 171? Да, я мог только отчасти вернуться туда, верно? А потом зачеркнуть 50, или просто переписать его с 171. И если вам интересно, почему наши номера получил так случайно, они обычно принято компьютер наука курсы в Гарварде после CS50. Но это был хороший оптимизация, потому что теперь я не тратить пространство. Я до сих пор должны помнить, насколько велика эта вещь общая. Это пять всего. Потому что я не хочу начать перезапись 51. Так что теперь я по-прежнему из космоса, так же проблема, что и раньше. Но вы можете увидеть, как в настоящее время в коде, вы, вероятно, нужно написать немного больше Сложность, чтобы это произошло. И в самом деле, то, что оператор в С, вероятно, позволяет Вы волшебным сделать это округлость? Да оператор по модулю, знак процента. Так что круто о очереди, хотя мы сохранить рисунок массивы как эти, как прямых, если вы вид думаю об этом, как изгиба вокруг, как круг, то просто интуитивно вид работы умственно Я думаю, что немного чище. Вы все равно придется осуществлять что ментальная модель в коде. Так что не так уж трудно, в конечном счете, реализации, но мы по-прежнему теряют размер-- скорее, Возможность изменять размер, если мы не сделаем это. 

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

Так короткий фильм, если вы будете. Анимация, что некоторые Люди в другом университете собрать, что мы приспособлены для этой дискуссии. Она включает в себя Джек обучения Факты о очередей и статистики. 

ФИЛЬМ: Давным-давно, был парень по имени Джек. Когда дело дошло до принятия друзьями, Джек не имеют сноровки. Так Джек пошел поговорить с Наиболее популярный парень знал. Он пошел к Лу и спросила, что мне делать? Лу увидел, что его друг был действительно расстроен. Ну, он начал, только посмотрите, как вы одеты. Нет ли у вас какие-либо одежду с другой вид? Да, сказал Джек. Я уверен, что делать. Приходите в мой дом и Я покажу их вам. Таким образом, они отправились в Джека. И Джек показал Лу окно где он хранил все свои рубашки, и штаны, и носки. Лу сказал, я вижу, у вас есть все ваши одежды в кучу. Почему бы вам не носить некоторые другие раз в некоторое время? 

Джек сказал, хорошо, когда я удалить одежду и носки, Я мыть их и положить им далеко в поле. Затем наступает следующий утром, и до я прыгаю. Я иду в поле и получить моя одежда с верхней. Лу быстро понял, проблема с Джеком. Он продолжал одежда, CD, и книги в стеке. Когда он потянулся за то читать или носить, он выбрать верхнюю книгу или нижнее белье. Потом, когда он был сделан, он будет положить его обратно. Вернуться она будет идти на вершине стека. Я знаю, что решение, сказал торжествующий Громко. Вы должны научиться начать использовать очереди. Лу взял одежду Джека и повесил в шкаф. И когда он опустошил коробка, он просто бросил ее. 

Тогда он сказал, теперь Джек, в конце день, положить одежду слева когда вы кладете их. Тогда завтра утром, когда вам см солнцем, получить одежду на право, с конца строки. Разве вы не видите? сказал Лу. Это будет так приятно. Вы будете носить все сразу прежде чем вы носите что-то в два раза. И со всем в очередях в шкафу и шельфа, Джек начал чувствовать достаточно уверен в себе. Все благодаря Лу и его замечательный очереди. СПИКЕР 1: Ладно, это восхитительно. Так что было на самом деле происходит на под капотом теперь? Что мы имеем указатели, что у нас есть таНос, что у нас есть возможность создать куски памяти для себя динамически. Так что это картина, которую мы увидел только на днях. Мы действительно не останавливаться на нем, но эта картина имеет уже на под капот уже несколько недель. И так это представляет, просто прямоугольник, который мы нарисовали, памяти компьютера. И, возможно, ваш компьютер или CS50 ID, имеет гигабайт оперативной памяти или памяти или два гигабайта или четыре. Это действительно не имеет значения. Ваша операционная система Окна или Mac OS или Linux, по существу позволяет вашей программы думать, что он имеет доступ ко всей памяти компьютера, даже если вы могли бы быть запущен несколько программ сразу. Таким образом, в действительности, что на самом деле не работает. Но это своего рода иллюзия учитывая все ваши программы. Так что, если у вас есть два гигабайтами оперативной памяти, это как компьютер может думать об этом. 

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

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

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

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

Так что F? F подает в строке в качестве единственного аргумента, АКА полукокса звезда, же вещь, как строку. И это называется как угодно бар в этом примере. И тогда символ с 12 только с точки зрения непрофессионала, что символ с скобка 12 делает для нас? Что он делает? Выделение памяти, специально 12 байта для 12 символов. В точку. И тогда последняя строка, перемешать и копия, вы, вероятно, не видел. Это строка копия Функция, цель которого в жизни это скопировать его второй аргумент в качестве первого аргумента, но только до Определенное количество байтов. Таким образом, третий аргумент говорит, сколько байт необходимо скопировать? Длина панели, все пользователь вводит в. И содержание бар, эту строку, являются скопированы в память указал на точке С. 

Так что это, кажется, своего рода глупо, и это. Это надуманный пример, но это представитель класса векторов атаки, способ нападения на программу. Все хорошо и прекрасно, если пользователь типы в слова, что это 11 символов или меньше, плюс обратный слеш нулю. Что делать, если пользователь в более чем 11 или 12 или 20 или 50 символов? Что эта программа будет делать? Потенциально SEG вина. Это будет слепо копировать все в баре до его длине, которая буквально все в баре, в адрес указал на С. Но С только превентивно дается как 12 байт. Но нет дополнительной проверки. Там, если условиях это нет. Там нет проверки ошибок здесь. 

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

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

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

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

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

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

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

Так что приятно в бинарное дерево поиска, это что один, мы можем реализовать его с структуры, как это. И хотя мы бросали много структур, в вашем они несколько Теперь, надеюсь, интуитивно. Синтаксис еще тайной наверняка, но содержимое узла в этом context--, и мы продолжаем используя слово узел, является ли это прямоугольник на экране или круга, это лишь некоторые общие контейнер, В этом случае дерева, как тот, мы видели, мы должны целое в каждом из узлов а затем мне нужно два указатели, указывающие на левом ребенка и правой ребенка, соответственно. Так вот, как мы могли бы осуществить, что в структуры. И как я мог бы реализовать это в коде? Ну, давайте быстро посмотреть на этом крошечном например. Это не работает, но я скопировать и вставить эту структуру. И если моя функция для бинарных Поиск дерево называется поиск, и это принимает два аргумента, целое число N и указатель к узлу, так что указатель на дерево или указатель на корень дерева, как я могу идти о поиске N? Ну, во-первых, потому, что я дело с указателями, Я собираюсь сделать проверку вменяемости. Если дерево равно равна нулю, является N в этом дереве или нет в этом дереве? Это не может быть, не так ли? Если я мимо нуль, там ничего нет. Я мог бы также просто слепо сказать вернуться ложным. Если вы не дают мне ничего, я, конечно, не могу найти число N. Так что еще я мог бы Проверь сейчас? Я хочу сказать, хорошо еще, если п меньше, чем то, что находится в узле дерева что я был передан значение N. Другими словами, если число Я ищете, N, меньше, чем узел что я смотрю на. И узел Я ищу в называется дерево, и вспомнить из предыдущего примера чтобы добраться до значения в указатель, Я использую обозначения со стрелкой. Так что, если N меньше, чем дерево стрелки N, я хочу, чтобы концептуально идите налево. Как я выражаю поиске осталось? Чтобы было ясно, если это картина в вопросе, и я был принят, что верхний стрелка, который направлен вниз. Это моя указатель дерево. Я указываю на корне дерева. И я с нетерпением скажем, число 44, произвольно. 44 меньше или больше, чем 55, очевидно? Так это меньше, чем. И так это, если условие распространяется. Так концептуально, то, что я хочу, чтобы поиск в следующем, если я ищу 44? Да? 

Точно, я хочу поиск левую ребенка, или влево суб-дерево этой картины. И в самом деле, пусть меня через картина здесь на мгновение, так как Я не могу поцарапать это. Если я начну здесь в 55, и Я знаю, что значение 44 Я ищу, чтобы левая, это своего рода из, как разрывая телефонную книгу в половина или разрывая дерево пополам. Я больше не придется заботиться о весь этот половина дерева. И все же, как ни странно, в терминах Структура, эта вещь здесь, что начинается с 33, что само по себе это бинарное дерево поиска. Я сказал слово рекурсивный раньше, потому что Действительно, это структура данных, по определению является рекурсивным. Вы, возможно, дерево, в этом большой, но каждый из его детей представляет собой дерево просто немного меньше. Вместо этого быть дедушку или бабушка, теперь это просто мама или-- я не могу say-- не мама или папа, что было бы странно. Вместо двое детей там будет как брат и брат. Новое поколение в родословной. Но структурно, это та же самая идея. А то получается, у меня есть функция с которой я могу искать бинарный поиск дерево. Это называется поиск. Я ищу N в дереве слева стрелки остальное, если п больше, чем значение что я в настоящее время. 55 в истории момент назад. У меня есть функция под названием Поиск, что я могу просто пройти N это и рекурсивный поиск суб-дерево и просто возвращение все, что ответом. Иначе я получил некоторые итоговый базовый случай здесь. 

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

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

Там такая неэффективность здесь. Как бы вы интуитивно сжимать немецкий флаг если ее реализации в виде файла? Нравится то, что информация мы не можем беспокоить хранения на диске для того, чтобы уменьшить нашу размер файла из, как мегабайт в килобайт, то меньше? В чем заключается избыточность здесь, чтобы быть понятно? Что вы могли бы сделать? Да? В точку. Почему бы не вспомнить, чем цвет каждого пикселя штопать так же, как вы делаете в PSET4 с Формат графического файла, почему бы вам просто не представляют левая колонка пикселей, например куча черных пикселей, куча красный, и куча желтый, а потом просто каким-то образом кодировать Идея повторить этот 100 раз или повторить это в 1000 раз? Где 100 или 1000 является просто целое число, так что вы может сойти с рук только один номер вместо сотен или тысяч дополнительных пикселей. И в самом деле, вот как мы может сжимать немецкий флаг. А Теперь то, что о французским флагом? И немного своего рода умственное упражнение, что флаг могут быть сжаты более на диске? Немецкий флаг или французский Флаг, если мы возьмем такой подход? Немецкий флаг, потому что есть более горизонтального резервирования. И по дизайну, многие графический файл Форматы действительно работать, как сканирования линий горизонтально. Они могли бы работать вертикально, просто человечество решили лет назад, что мы будем как правило, думать о вещах, ряд по строкам, а не по столбцам. Так, если бы вы были посмотреть на файл размер немецким флагом и французском языках Флаг, пока разрешение то же самое, такой же ширины и высота, на этот раз здесь будет больше, потому что вы придется повторить себя три раза. Вы должны указать, повторение синий самостоятельно, белый, повторяться, красный, повторяться. Вы не можете просто пойти все путь к правой. И, как в сторону, чтобы сделать очистить сжатие везде, если это четыре кадра из video-- вы Напомню, что фильм или видео, как правило, как 29 или 30 кадров в секунду. Это как маленький флип книги, где вас просто увидеть изображения, изображение, изображение, изображение, Изображение просто супер быстро, так что, похоже, актеры на экране движутся. Вот шмель на Верх букетом цветов. И хотя это может быть вид трудно понять, на первый взгляд, единственное движение в этот фильм пчела. 

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

Но как вы сжать текст? Как вы идти о сжатии текста? Ну, каждый из персонажей Ascii один байт, или восемь бит. И это своего рода немой, не так ли? Потому что вы, вероятно, введите A и Е, я и вывода и U много чаще, чем, как W или Q или Z, в зависимости от языка, на котором Вы пишете, конечно,. И так, почему мы с помощью восемь битов для каждого письма, в том числе не менее популярные буквы, верно? Почему бы не использовать меньшее количество бит для супер популярные буквы, как Е, то, думаю, вы первый в Колесо Фортуны, и использовать больше битов для менее популярные буквы? Зачем? Потому что мы только собираемся использовать их реже. 

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

Я? Я? Или то, что about-- или я? Может быть, это было всего лишь два прямо Э? Так что эта проблема из декодируемости с Морзе Код, в результате чего, если только человек, посылающий вам сообщение на самом деле делает паузу, чтобы вы могли сортировать видеть или слышать пробелы между буквами, это не достаточно просто отправить поток нулей и единиц, или точки и тире, потому что есть двусмысленность. Е является одна точка, так что если вам увидеть две точки или услышать две точки, может быть, это два E-то или, может быть, это один И. Так что мы должны систему, что это немного умнее, чем это. Таким образом, человек по имени Хаффмана лет назад придумал именно это. Таким образом, мы просто собираемся взять быстрый взгляд на то, как деревья уместны для этого. Предположим, что это какой- глупо сообщение вы хотите отправить, состоит только из A, B, C в D's и Е х, но есть много избыточности здесь. Это не означало, чтобы быть английский. Это не шифруется. Это просто глупо сообщение с большим количеством повторений. Так что, если вы на самом деле отсчитывать все А-х, Б, С-х, D's, и E-х, вот Частота. 20% из букв А-х, 45% из букв являются E, и три другие частоты. Мы насчитали там вручную и просто сделал математику. 

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

Какие два узлы я комбинировать дальше? Это немного неоднозначным. Так есть некоторые случаи, в угловые рассмотреть, но держать вещи довольно, Я собираюсь выбрать 20% - Теперь я игнорировать детей. Я собираюсь выбрать 20%, а 15% и нарисуйте два новых ребра. А теперь какие два узла я логически объединить? Игнорировать все дети, все внуки, просто посмотрите на корни Теперь. Какие два узлы я связать вместе? Второй пункт и 0,35. Итак, позвольте мне сделать два новых ребер. И потом, я только получил один остался. Так вот дерево. И это было обращено намеренно смотреть вид довольно, но заметил, что ребра имеют Также были помечены нуля и один. Таким образом, все из левого краев равны нулю произвольно, но последовательно. Все правые края являются те. 

И так, что Хоффман предложил есть, если вы хотите, чтобы представлять B, а не представляют собой количество, как 66 ASCII, который восемь целые бит, вы знаете, что только магазин образец ноль, ноль, ноль, нулю, потому что это путь от моего дерева, дерево Хаффмана г, к листу от корня. Если вы хотите сохранить Е, напротив, не отправить восемь бит, которые представляют Е. Вместо этого, отправить какой набор битов? Один. И, что приятно об этом является что Е является самым популярным письмо, и вы с помощью короткий код для него. Следующим наиболее популярным Письмо выглядит она был А. И так, сколько бит он предлагается использовать для этого? Ноль, один. 

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

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

Теперь стеки были растет, что преднамеренное дизайн вещь здесь. Но что еще я мог бы сделать? Поэтому на самом деле здесь мы имеем куча старых книг школы экзамен. Предположим, что кучу студенты имена здесь. Вот больше хеш-таблицы. Вместо четырех ведер, Я, скажем, 26. И мы не хотим идти занимать 26 вещи из вне [? Анненберга?], Так что вот пять, которые представляют А до Z. И если я см студента, чье имя начинается с А, Я собираюсь поставить его или ее викторины там. Если кто-то начинает с C, там, A-- самом деле, не хотят, чтобы сделать это. В идет сюда. Так что я получил А и В и С. А Теперь вот еще студент. Но если это хэш-таблицы реализованы с массивом, Я вроде ввинчивается на данный момент, не так ли? Я вроде должны положить это где-то. 

Так один способ я могу решить это, все право, занят, занят В, С занят. Я собираюсь поставить его в D. Таким образом, в Сначала я есть случайное мгновенный доступ к каждому из ковшей для студентов. Но теперь это вроде переданы во что-то линейных, потому что, если я хочу, чтобы искать кого- чье имя начинается с А, я проверяю здесь. Но если это не А студент Я ищу, Я вроде должны начать проверку ведра, потому что то, что я сделал был своего рода линейно исследовать структуру данных. Глупый способ сказать просто посмотреть для первой доступной открытия, и поставить в план Б, так сказать, или план разработки в этом случае, значение в этом месте вместо этого. Это просто так, что если вы получил 26 места и не студенты с именем Q или Z, или что-то вроде что, по крайней мере, вы используете пространство. 

Но мы уже видели более умные решения здесь, верно? Что бы вы сделали, вместо если у вас есть столкновение? Если два человека имеют название А, что бы были умнее или интуитивное решение, чем просто Помещение, где D, как предполагается, будет? Почему я не могу просто пойти за пределами [? Анненберга?], как таНос, другой узел, поставить его здесь, а затем положить, что студент здесь. Так что я по сути есть какая из массива, или, может быть, более элегантно, как мы начинаем видеть связанный список. 

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

Так что это своего рода глупые, вызывающим шутки лет назад. В CS50 рубить-а-марафон, когда студенты проверить в, некоторые TF или Калифорния каждый год думает, что это смешно, мириться знак, как это, где это только означает, что если ваше имя начинается с А, идти по этому пути. Если начинается ваше имя с В, перейти this-- ОК, это смешно, может быть, позже в семестр. Но есть еще один способ сделать это, тоже. Вернись к этому. 

Так что эта структура. И это наша последняя Структура на сегодняшний день, что-то называется Trie. Т-Р-И-Е, который почему-то не хватает для поиска, но это называется Trie. Так Trie еще один интересный амальгама много этих идей. Это дерево, которое мы видели раньше. Это не бинарное дерево поиска. Это дерево с любым количеством детей, но каждый из детей в синтаксического дерева является массивом. Массив размером, допустим, 26 или, может быть 27 если вы хотите, чтобы поддержать дефис имена или апострофы в именах людей. 

И так это структуры данных. И если вы посмотрите сверху вниз, как если бы вас посмотрите на верхний узел там, М, указывая на крайнюю левую вещи там, который затем A, X, W, E, L, L. Это просто структура данных, которая произвольно является сохранение имен людей. И Максвелл хранится только после это путь массива массива на массив. Но что удивительно около Trie является что, в то время как связанный список, и даже массив, лучшее, что мы когда-либо получали это линейное время или логарифмическое время ищете кто до. В этом структуры данных синтаксического дерева, если мой структура данных имеет один имя в нем и Я ищу Максвелла, я собираюсь найти его довольно быстро. Я просто смотрю на М-А-Х-W-E-L-L. Если Эта структура данных, напротив, Если N является млн, если есть миллион имена в этой структуре данных, Максвелл еще будет обнаружить уже через М-А-Х-Ш-Е-Л-Ь шаги. И David-- Д-А-В-Я-D шаги. Другими словами, путем создания структура данных, что это получил все эти массивов, каждый из которых Сами поддерживать произвольный доступ, Я могу начать глядя народных назвать, используя количество времени, что'S пропорциональна не количеству вещей в структуре данных, как миллион существующие имена. Количество времени, которое требуется, чтобы найти меня М-А-Х-Ш-Е-Л-Л в этой структуре данных является пропорциональна не Размер структуры данных, но с длиной имени. И реалистично Имена мы глядя никогда не будет с ума долго. Может быть, кто-то имеет 10 характер имя, имя персонажа 20. Это, конечно, конечно, не так ли? Существует человека на Земле, который имеет максимально возможный имя, но это имя является константой значение длины, верно? Это не меняется в любом смысле. Таким образом, в этом случае, мы достигнуты структурой данных что постоянная времени взгляд вверх. Это займет несколько шагов в зависимости от длины входа, но не число имени в структуре данных. Так что, если мы удвоим количество имен в следующем году из миллиарда до двух миллиардов, вывод Максвелла собирается взять точно такой же количество семь шагов чтобы найти его. И таким образом, мы, кажется, достигли наш святой Грааль время работы. 

Таким образом, пара быстрых объявлений. Викторина ноль придумывать. Подробнее о том, что на веб-сайте Курса в течение ближайших нескольких дней. Понедельник lecture-- Это праздник здесь в Гарварде в понедельник. Это не в Нью-Хейвене, таким образом, мы берем класс в Нью-Хейвен для лекции в понедельник. Все будет снят и транслироваться в прямом эфире, как обычно, но давайте в конечном сегодня со вторым зажимом 30 называемые "глубокие мысли" по Daven Фарнем, который был вдохновлен в прошлом году в субботу "Мысли" Deep Night Live в Джек Хэнди, который Теперь следует разобраться. 

ФИЛЬМ: А теперь, "Глубокое Мысли "по Daven Фарнем. Хеш-таблица. 

СПИКЕР 1: Ладно, что она в настоящее время. Мы будем видеть Вас на следующей неделе. 

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

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

УПА: Эй, эй, эй, вырезать, вырезать, вырезать, вырезать. Дуг, ты не можешь просто я-да, я-да, я-да, ваш путь через сортировки слиянием. 

Даг: Я только что сделал. Все нормально. Мы хорошо идти. Давайте просто держать прокатки. В общем, как бы то ни было, 

УПА: Вы должны объяснить это более полно, чем это. Вот только не хватает. Даг: Ян, мы не нужно вернуться к одному. Все нормально. Так или иначе, если мы будем продолжать с merge-- Ян, мы находимся в середине съемок. 

УПА: Я знаю. И мы не можем просто я-да, я-да, я-да, через весь процесс. Вы должны объяснить, как Стороны сливаются вместе. 

ДАГ: Но мы уже объяснил, как два sides-- 

УПА: Вы только что показали их массив слияния. Даг: Они знают процесс. Они в порядке. Мы пошли на него в десять раз. 

УПА: Вы только что пропустил прямо над ней. Мы возвращаемся к одному, вы вы не можете я-да, я-да над ним. Ладно, к одному. 

Даг: Я должен вернуться через все слайды? Боже мой. Это как в шестой раз, Ian. Все нормально. 

УПА: Ладно. Вы готовы? Отлично. Действие.