>> Выступающий 1: Все в порядке, так что мы вернулись.
Добро пожаловать в CS50.
Это конец недели семь.
Поэтому напомним, что в прошлый раз, мы начали глядя на несколько более сложно
структур данных.
Так как до сих пор, все, что мы были действительно В нашем распоряжении было этого, массив.
>> Но прежде чем отбросить массив как не все, что интересно, что это действительно так
на самом деле, то, что некоторые из Плюсы этого простого данных
структуры до сих пор?
Каково это хорошо?
До сих пор, как мы видели?
Что у тебя?
Ничего.
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Что это?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: фиксированный размер.
Итак, почему фиксированный размер хороший, хотя?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Хорошо, так что это эффективно в том смысле, что вы можете выделить
Фиксированная сумма в пространстве, которое, мы надеемся, Именно столько
пространства, как вы хотите.
Так что может быть абсолютно плюс.
>> Что еще по одной стороне массива?
Да?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Все - Простите?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Все коробки в памяти или рядом друг с другом.
И это полезно - почему?
Совершенно верно.
Но как мы можем использовать это правда?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Точно, мы можем отслеживать , где все просто, зная,
один адрес, а именно, адреса Первый байт, что блок памяти.
Или в случае строки, адрес первого
символ в этой строке.
А оттуда, мы можем найти конца строки.
Мы можем найти второй элемент, третий элемент, и так далее.
>> И таким причудливым способом описания, что особенность в том, что массивы дают нам
произвольным доступом.
Просто с помощью квадратных скобок обозначения и номера, вы можете перейти к
конкретного элемента в массиве за постоянное время, Big O
одного, так сказать.
>> Но есть некоторые минусы.
Что массив не делать очень легко?
Что это не очень хорошо?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Что это?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Расширение в размерах.
Таким образом, недостатки массива точно противоположное тому, что
расквитаться есть.
Поэтому одним из недостатков является что это фиксированный размер.
Таким образом, вы не можете реально вырастить его.
Вы можете перераспределить больший кусок памяти, а затем переместите старый элементы
в новый массив.
, А затем освободить старого массива, для Например, при использовании таНос или аналогичного
Функция называется Realloc, которая перераспределяет память.
>> Realloc, как в сторону, пытается дать вам памяти, что это рядом с массивом
что вы уже имеете.
Но это может перемещать предметы вокруг в целом.
Но в общем, что дорого, не так ли?
Потому что, если у вас есть кусок памяти такого размера, но вы действительно хотите один
такого размера, и вы хотите сохранить оригинальные элементы, у вас есть
примерно линейный процесс копирования время что должно произойти от
старого массива на новый.
А реальность такова просят операционной Система снова и снова и
снова на большие куски памяти может начаться стоить вам некоторое время, а также.
Так что это как благословение и проклятие в замаскировать тот факт, что эти массивы
имеют фиксированный размер.
Но если ввести вместо что-то как это, которое мы назвали связанного
список, мы получаем несколько плюсы и несколько недостатков и здесь.
>> Так связанный список просто данные структура, состоящая из структур C в этом
случае, когда структура, напомним, является просто контейнер для одного или более конкретных
типы переменных.
В этом случае, что же типы данных видимому, внутри структуры, который
Последний раз мы называется узлом?
Каждый из этих прямоугольников узла.
И каждый из меньших прямоугольников Внутри это тип данных.
Какие же тогда мы говорили они были в понедельник?
Да?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: переменные и указатель, или точнее, целое для N,
и указатель на дне.
Оба эти, оказывается, 32 бита, по крайней мере на компьютере, как это CS50
Appliance, и поэтому они обращается одинаково в размере.
>> Так что с помощью указателя хотя для по-видимому?
Зачем добавлять эту стрелку теперь, когда массивы, были так хорошо и чисто и просто?
Что делаете для указателя нами в каждом из этих узлов?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Совершенно верно.
Это говорит вам, где далее идет.
Так что я, конечно, использовать аналогию использованием потока к виду
нить эти узлы вместе.
И это именно то, что мы делаем с указателей, поскольку каждый из этих
участков памяти может или не может быть смежные, спина к спине к спине
внутри оперативной памяти, потому что каждый раз, когда вы позвоните Malloc говорят: дай мне достаточно
байтов для нового узла, он может быть здесь, или он может быть здесь.
Это могло бы быть здесь.
Вы просто не знаю.
>> Но с помощью указателей в адресах эти узлы, вы можете сшить их
вместе таким образом, что визуально выглядит как список, даже если эти вещи
все распространены на протяжении всего одного или Ваши два или ваши четыре гигабайта оперативной памяти
внутри вашего собственного компьютера.
>> Таким образом, недостаток, то, Связанный список есть что?
Что такое цена, что мы видимо платить?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Больше места, не так ли?
Мы, в данном случае, удвоил сумму пространства, потому что мы прошли
с 32 бит для каждого узла, для каждого Интеллект, так что теперь 64 бита, потому что мы должны
держать вокруг указателя, а также.
Вы получаете больше эффективности, если вашей структуры больше, чем эта простая вещь.
Если у вас действительно есть внутри студента из которых представляет собой пару строк для
имя и дом, может быть, номер удостоверения личности, возможно, некоторые другие области в целом.
>> Так что если у вас есть достаточно большая структура, то, возможно, стоимость указатель
Не такое уж большое дело.
Это немного из угла в этом случае мы сохраняем такие простые примитивные
внутрь связанного списка.
Но суть та же.
Вы определенно тратить больше памяти, но вы получаете
гибкость.
Потому что теперь, если я хочу добавить элемент В начале этого списка,
Я должен выделить новый узел.
И я должен просто обновить эти Стрелки как-то просто перемещение
некоторые указатели вокруг.
>> Если я хочу, чтобы вставить что-то в середине списка, я не придется
толкать в сторону все, что мы сделали в недель прошлое с нашим добровольцам, которые
представлена ​​массивом.
Я могу просто выделить новый узел и Затем просто указать стрелками на
разных направлениях, поскольку она не должны оставаться в фактическом
памяти истинных линии, как я нарисовал его здесь на экране.
>> А потом, наконец, если вы хотите вставить то в конце списка, это
еще проще.
Это своего рода произвольные обозначения, но в 34 указателей, сделать предположение.
Что такое значение его указателя наиболее вероятно, обращается вроде как старые
школе есть антенна?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Это, вероятно, нулевым.
И в самом деле, что является одним автора представление нулевой.
И это нуль, потому что вы абсолютно нужно знать, где к концу связанного
список, чтобы вы продолжаете после и после и после этих стрелок
некоторым мусором значения.
Так нулевых не будет означать, что нет никакой более узлов справа от числа 34,
в этом случае.
>> Поэтому мы полагаем, что мы можем реализовать этот узел в коде.
И мы видели такую синтаксиса раньше.
Typedef просто определяет новый тип для нас, дает нам как синоним
Строка была для символ *.
В этом случае, он собирается дать нам сокращенную запись, так что структура узла
Вместо этого можно просто быть записана в виде узел, который является намного более чистой.
Это гораздо менее многословным.
>> Внутри узла видимому Целочисленное называется п, а затем структуры узла *
что означает именно то, что мы хотели Стрелки в виду, указатель на другой
узел точно такой же тип данных.
И я предлагаю, чтобы мы могли реализовать Функция поиска, как это, которое в
первый взгляд может показаться, немного сложным.
Но давайте посмотрим его в контексте.
>> Позвольте мне перейти к прибору здесь.
Позвольте мне открыть файл с именем Список нулю точка ч.
И что только содержит определение мы только что видели минуту назад для этих данных
тип называется узлом.
Поэтому мы ввели, что в файл точка ч.
>> И, как в стороне, хотя это программа, которую вы собираетесь, чтобы увидеть это
не все, что комплекс, это действительно Конвенции при написании программы
положить вещи, как типы данных, тянуть Константы иногда, внутри вашего
заголовок файла, а не обязательно в С вашего файла, конечно же, когда ваш
программ получить больше и больше, так что Вы знаете, где искать, как для
документации в некоторых случаях или для основы, как это,
определение некоторого типа.
>> Если бы я сейчас открыть список нулю точка C, заметить несколько вещей.
Она включает в себя несколько файлов заголовка, большинство которого мы видели раньше.
Она включает в себя свой собственный файл заголовка.
>> И, как в стороне, почему это двойная котировки здесь, в отличие от угла
кронштейны на линии, которая Я выделил там?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Да, так что это локальный файл.
Так что, если это локальный файл собственного здесь на линии 15, например, вы используете
двойные кавычки вместо в угловые скобки.
>> Теперь это отчасти интересно.
Обратите внимание, что я объявил глобальную переменной в этой программе в строке 18
называется первой, идея в том, что это будет указатель на первый
узел в моем связанный список, а я инициализировать его к нулю, потому, что я
не выделяется каких-либо фактических узлы только пока.
>> Так что это представляет, графически, то, что мы увидел минуту назад на картинке как
что указатель на Дальнем с левой стороны.
Так что сейчас, что указатель не имеет стрелки.
Вместо этого он просто нулевой.
Но он представляет, какой будет адрес первого фактического
узла в этом списке.
Так я реализовал это глобальная потому что, как вы увидите, все это
Программа делает в жизни, это реализовать связанный список для меня.
>> Теперь у меня есть несколько прототипов здесь.
Я решил реализовать функции, такие как делеции, вставки, поиска и
обхода -
Последний просто быть прогулка через Список, распечатав ее элементов.
А теперь вот мой основной программе.
И мы не будем тратить слишком много времени на это, так как это является своего рода, мы надеемся,
старая шляпа к настоящему времени.
>> Я собираюсь сделать следующее, в то время как пользователь взаимодействует.
Так что, я собираюсь печатать из этого меню.
И я отформатировал его в качестве чисто, как я мог.
Если пользователь вводит в одном, то есть они хотят, чтобы удалить что-нибудь.
Если пользователь введет в двух, это означает, что они хотят, чтобы вставить что-то.
И так далее.
Я собираюсь потом подскажут Тогда для команды.
А потом я собираюсь использовать GetInt.
>> Так что это действительно просто menuing интерфейс, где вы просто должны ввести
число отображение одного из этих команд.
И теперь у меня есть хорошая чистая переключатель заявление, что собирается включить
любой пользователь ввели дюйма
И если они набрали одно, я буду вызове удаления и ломаться.
Если они ввели два, я буду позвоните вставить и ломаться.
>> А теперь обратите внимание я поместил каждого из них на той же линии.
Это всего лишь стилистическое решение.
Обычно мы видели что-то как это.
Но я просто решил, честно говоря, моя программа выглядел более для чтения, так
это было только четыре случая просто перечислить это так.
Полностью законное использование стиля.
И я буду делать это так долго, как Пользователь не набрала нулю, что я
решено будет означать, что они хотят бросить курить.
>> Так что теперь замечаю, что я будем делать здесь.
Я собираюсь освободить списке по-видимому.
Но об этом через минуту.
Давайте сначала запустить эту программу.
Итак, позвольте мне сделать больший терминал окна, точка слэш список 0.
Я собираюсь идти вперед и вставляйте их набрав два, как число 50, а теперь
Вы увидите список теперь на 50.
И мой текст, просто прокручивается немного.
Так что теперь Обратите внимание на список содержит число 50.
>> Давайте еще вставкой, взяв два.
Давайте введите номер, как один.
Список является одной, а затем 50.
Так что это просто текстовое представление списка.
И давайте вставим еще один номер, как номер 42, который с надеждой
будет в конечном итоге в середине, потому что этой программы, в частности, сортирует его
элементы, как он вставляет их.
Так что у нас это есть.
Супер просто программу, которая может Абсолютно использовали множество, но я
, случается, используют связанный список именно так я могу динамически
увеличиваются и уменьшаются его.
>> Итак, давайте взглянем на поиски, если я запустить команду три, я хочу поиску
, скажем, числа 43.
И ничего не было найдено по-видимому, потому что я не вернулся без ответа.
Итак, давайте сделаем это снова.
Поиск.
Давайте искать для 50, или, скорее, поиск для 42, у которого есть хорошая
почти неуловимая смысл.
И я нашел смысл жизни там.
Число 42, если вы не знаете, ссылки Поиск в Интернете.
Хорошо.
Так, что эта программа для меня сделал?
Это просто позволил мне вставить таким образом, далеко и поиск элементов.
>> Давай вперед, то, чтобы функции, мы взглянул на
в понедельник, как дразнилка.
Так что эта функция, я утверждаю, ищет элемента в списке по первым
одна, предлагая пользователю с последующим вызовом GetInt, чтобы получить фактические десятичного
что вы хотите найти.
>> Потом заметил этого.
Я собираюсь создать временную переменную В линии 188 называется указателем -
PTR -
мог бы назвать ее как угодно.
И это указатель на узле потому что Я сказал узла * там.
И я инициализации равным первый, так что я эффективно мое
пальца, так сказать, на самом Первый элемент списка.
Так что, если моя правая рука здесь PTR Я указывая на то же самое, что первый
указывает на.
>> Так что теперь еще в коде, что будет дальше -
это общая парадигма при переборе по структуре, как
связанный список.
Я собираюсь сделать следующее в то время как указатель не равен нулю Таким образом, хотя
мой палец не указывает на некоторые нулевым стоимости, если стрелка указателя N равно N.
Мы заметили, что первые N является то, что пользователь вводит в GetInts называю здесь.
>> И стрелка указателя N означает, что?
Ну, если мы вернемся к картины здесь, есть ли у меня пальцем, указывая на
что первый узел, содержащий девять, стрелки по существу означает, что перейти к
узла и захватить значение в точке N, В этом случае, поле данных называется н.
>> Как в сторону - и мы увидели эту пару недель назад, когда кто-то спросил -
этот синтаксис является новой, но это не так дать нам силы, которые мы
уже не было.
Что это за фраза эквивалентно использованию точечной нотации и звезда пара
недель назад, когда мы очищенные назад этот слой немного преждевременно?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Точно, это была звезда, и тогда это была звезда точкой N, с
Здесь скобки, который выглядит, честно говоря, я думаю, что много
более загадочные читать.
Но указатель звезды, как всегда, средства идут туда.
И как только вы там, какие данные поля вы хотите получить доступ?
Ну вы используют точку доступа к поля структур данных, и я
специально хотят н.
>> Честно говоря, я бы сказал, это просто трудно читать.
Это сложнее вспомнить, где сделать скобках идти,
звезда и все такое.
Таким образом, мир принял некоторые синтаксические сахар, так сказать.
Просто сексуально способ сказать, это эквивалентно, а также
возможно, более интуитивным.
Если указатель действительно является указателем, средств стрелки обозначения пойти туда и найти
поля в этом случае называются N.
>> Так что, если я нахожу это, заметьте, что я делаю.
Я просто распечатать, я обнаружил, я процентов, подключение значение для этого Int.
Я называю спать в течение одной секунды просто вид паузы вещи на экране, чтобы
дать пользователю второй поглощать что только что произошло.
И тогда я нарушу.
В противном случае, что мне делать?
Обновить указатель на равных указателя стрелки рядом.
>> Так что просто чтобы быть ясным, это означает пойти там, с помощью моей старой школы обозначений.
Так что это просто означает, идти к тому, что Вы указываете на, который в самом
Первый случай я указывая на Структура с девятью в нем.
Так что я пошел туда.
И тогда точечной нотации означает, получить значение в следующем.
>> Но ценность, хотя он рисуется как узкие, просто номер.
Это адрес в числовой.
Так что это одна строка кода, будь то написано, как это, более скрытом
пути, или, как это, несколько более интуитивно понятным способом, просто означает, пошевелить рукой
от первого узла к следующему, а затем следующий, а затем
следующей, и так далее.
>> Таким образом, мы не будем останавливаться на других реализаций вставлять и удалять
и обхода, первые два из которые являются достаточно сложной.
И я думаю, что это довольно легко получить потерял, когда делают это в устной форме.
Но что мы можем сделать здесь Попробуйте определить, как
Лучше делать это визуально.
Потому что я хотел бы предложить, что если мы хотите вставить элементы в этой
существующий список, который состоит из пяти элементов -
9, 17, 22, 26 и 33 -
Если бы я собирался осуществить это в код, мне нужно подумать, как идти
об этом.
>> И я хотел бы предложить шаги ребенка которой, в данном случае я имею в виду, каковы
возможных сценариев, которые мы могут возникнуть в целом?
При реализации вставки для связанного списке, это только, случается,
Конкретным примером размер пять.
Ну, если вы хотите вставить цифру, как, скажем, номер один, и
поддержание порядке сортировки, где , очевидно, номер один нужно
идти в этом конкретном примере?
Например, в начале.
>> Но что интересно, есть то, что Если Вы хотите вставить одну в эту
список, что нужно специальный указатель обновить очевидно?
Первая.
Так что я бы сказал, что это первый случай что мы могли бы хотеть рассмотреть,
сценарий, включающий введение, по начале списка.
>> Давайте обрывать, может быть, так легко, или даже простой случай, условно говоря.
Предположим, я хочу, чтобы вставить 35 числа в порядке сортировки.
Это, очевидно, принадлежит там.
Так что, очевидно, указатель будет должны быть обновлены в этом сценарии?
34 в указатель становится NOT NULL но адрес структуры
содержащий номер 35.
Так вот случай два.
Так что уже, я вроде квантования сколько работы я должен сделать здесь.
>> И, наконец, очевидный случай середина Действительно, в середине, если я хочу
вставлять нечто вроде говорят 23, который идет между 23 и 26, но
Теперь все становится немного более участвует, потому что
указатели должны быть изменены?
22 Так, безусловно, должна быть изменена потому что он не может указать на 26 больше.
Ему нужно, чтобы он указывал на новый узел, Мне придется выделить по телефону
Malloc или некоторый эквивалент.
>> Но потом я также нужно, чтобы новый узел, 23 В этом случае, чтобы иметь свой указатель
указывая на кого?
26.
И там будет Порядок операций здесь.
Потому что если я сделаю это глупо и я Например начала в начале
списке, и моя цель, чтобы вставить 23.
И я проверял, оно принадлежит здесь, около девяти?
Нет.
Имеет ли место здесь, рядом с 17?
Нет.
Имеет ли она принадлежит здесь рядом с 22?
Да.
>> Теперь, если я глуп здесь, и не думая, что это до конца, я мог бы
выделить мой новый узел 23.
Я мог бы обновить указатель из узел, который называется 22, указывая
его на новый узел.
И что тогда мне придется обновлять указатель на новый узел, чтобы быть?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Совершенно верно.
Указывая на 26.
Но, черт возьми, если бы я уже не обновлять Указатель 22, чтобы она указывала на этого парня, и
теперь у меня есть сироты, остальные списка, так сказать.
Так что порядок операций здесь будет важно.
>> Для этого я мог украсть, скажем, шесть добровольцев.
И давайте посмотрим, если мы не можем сделать этого визуально вместо кода-мудрым.
И у нас есть некоторые прекрасные стресса шары для вас сегодня.
Хорошо, а как об одном, двух, в Назад - в конце там.
три, четыре, вы оба Парни на конце.
И пять, шесть.
Конечно.
Пять и шесть.
Ладно, и мы приедем чтобы вы, ребята, в следующий раз.
Ладно, поднимайся.
>> Ладно, раз уж ты здесь, во-первых, Вы хотели бы быть тем, неловко
Стекло в Google здесь?
Ладно, ладно, стекло, Запись видео.
Хорошо, вы хорошо идти.
>> Ладно, так что если вы, ребята, можете приехать Здесь, я подготовил заранее
некоторые цифры.
Ладно, иди сюда.
А почему бы вам не пойти немного далее, что путь.
И посмотрим, как тебя зовут, Стекло с Google?
>> СТУДЕНТ: Бен.
>> Выступающий 1: Бен?
ОК, Бен, ты будешь первым, буквально.
Итак, мы собираемся отправить вам в конце стадии.
Ладно, и ваше имя?
>> СТУДЕНТ: Джейсон.
>> Выступающий 1: Джейсон, OK вы будете быть номером девять.
Так что, если вы хотите следовать Бен таким образом.
>> СТУДЕНТ: Джилл.
>> Выступающий 1: Джилл, вы собираетесь быть 17, который, если бы я сделал это более
разумно, я бы началось на другом конце.
Вы идти по этому пути.
22.
А вы кто?
>> СТУДЕНТ: Марии.
>> Выступающий 1: Мария, вы будете 22.
А ваше имя?
>> СТУДЕНТ: Крис.
>> Выступающий 1: Крис, вы будете 26.
А потом, наконец.
>> СТУДЕНТ: Дианы.
>> Выступающий 1: Диана, вы будете 34.
Таким образом, вы иди сюда.
>> Ладно, настолько совершенен отсортированный Заказать уже.
И давайте идти вперед и делать это так что мы можем на самом деле -
Бен, ты просто вид глядя из в никуда там.
Итак, давайте пойдем дальше и изображают эту применением оружия, так же, как я был, собственно,
что происходит.
Так что идти вперед и дать себе фут или два между собой.
И идти вперед и отметить с одной стороны, кто бы ты должен быть направлен на
на основе этого.
И если вы просто указать нулевой прямо вниз к полу.
Хорошо, так хорошо.
>> Так что теперь у нас есть связанный список, и позвольте мне предлагаю, что я буду играть роль
PTR, так что я не буду беспокоиться проведение этого вокруг.
А потом - кто-то глуп Конвенции - Вы можете называть это все, что угодно -
предшественника указатель, указатель PRED -
это просто прозвище мы дали в наш образец кода для моей левой руке.
С другой стороны, что будет сохранение отслеживать, кто есть кто в
Следующие сценарии.
>> Итак, пусть, во-первых, я хочу обрывать что первый пример вставки, скажем
20 в списке.
Так что я собираюсь нужно, чтобы кто-то воплощают в себе число 20 для нас.
Так что мне нужно кого-то Malloc от аудитории.
Поднимайся.
Как тебя зовут?
>> СТУДЕНТ: Брайан.
>> Выступающий 1: Брайан, все в порядке, так что вы должен быть узел, содержащий 20.
Ладно, иди сюда.
И очевидно, что, где Брайан действительно принадлежите?
Таким образом, в середине - собственно, подожди минутку.
Мы делаем это не в порядке.
Мы делаем это намного сложнее , чем она должна быть в первую очередь.
Хорошо, мы собираемся бесплатно Брайан Брайан и Realloc как пять.
>> Итак, теперь мы хотим, чтобы вставить Брайан, как пять.
Так иди сюда рядом с Бен на мгновение.
И вы, вероятно, может сказать где эта история идет.
Но давайте тщательно обдумайте порядок выполнения операций.
И это именно это визуальное что происходит, чтобы выстроиться
с этот образец кода.
Так вот я PTR первоначально указывая Не на Бена, как таковой, но на любом
оценивают он содержит, который в данном случае - что тебя зовут?
>> СТУДЕНТ: Джейсон.
>> Выступающий 1: Джейсон, так как Бен и я указывая на Джейсона в этот момент.
Так что теперь у меня есть, чтобы определить, где же Брайан принадлежите?
Поэтому единственное, что я имею доступ к Прямо сейчас его N элемента данных.
Так что я собираюсь проверить, является Брайан меньше Джейсон?
Ответ на этот вопрос так.
>> Так что сейчас должно произойти, в правильном порядке?
Мне нужно уточнить, сколько указателей Всего в этой истории?
Где моя рука все еще указывая на Джейсон, и ваша рука - если вы хотите
положить руку, как, вроде, я Не знаю, знаком вопроса.
Хорошо, хорошо.
>> Ладно, так что вы должны несколько кандидатов.
Либо Бен или я или Джейсон Брайан или или все остальные, которые
указатели нужно изменить?
Сколько всего?
>> Итак, два.
Мой указатель на самом деле не имеет никакого значения потому что я только временно.
Так что эти два парня, по-видимому, как Бен и Брайана.
Итак, позвольте мне предложить, что мы обновляем Бен, так как он в первую очередь.
Первым элементом этого списка Теперь будет Брайан.
Так Бен точки на Брайана.
Хорошо, что теперь?
>> Кто получает указал на кого?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Хорошо, таким образом Брайан чтобы указать на Джейсона.
Но я потерял этот указатель?
Знаю ли я, где Джейсон?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: я делаю, так как я временный указатель.
И по-видимому, я не изменил , чтобы указать на новый узел.
Так что мы можем просто Брайан точки тот, кто на меня указывая на.
И мы сделали.
Таким случаем, вставка на начало списка.
Были два ключевых шага.
Во-первых, мы должны обновить Бена, а затем Мы также должны обновить Брайан.
И тогда я не придется беспокоиться тащась через остальную
список, потому что мы уже нашли его расположение, потому что он принадлежал к
слева от первого элемента.
>> Ладно, довольно проста.
В самом деле, кажется, что мы уже почти делает это слишком сложно.
Итак, давайте обрывать конца списка, и увидеть, где
Сложность начинается.
Так что если сейчас, я Alloc от аудитории.
Любой хочет играть 55?
Ладно, я видел вашу руку первым.
Поднимайся.
Да.
Как тебя зовут?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Habata.
ОК, давай вверх.
Вы будете номером 55.
Таким образом, вы, конечно, принадлежат в конце списка.
Так что давайте переиграть моделирования со мной будучи PTR на мгновение.
Так что я собираюсь первым, чтобы указать на все, что Бена указывая на.
Мы оба теперь, указывая на Брайана.
Так 55 не меньше, чем пять.
Так что я собираюсь обновить себя, указывая на следующий указатель Брайана, который
Сейчас, конечно, Джейсон.
55 составляет не менее девяти, так Я собираюсь обновить PTR.
Я собираюсь обновить PTR Я собираюсь обновить PTR.
И я собираюсь - Хм, что это тебя зовут?
>> СТУДЕНТ: Дианы.
>> Выступающий 1: Диана указывает, конечно, при нулевом левой рукой.
Так где же на самом деле Habata принадлежат ясно?
С левой стороны, здесь.
Так как я знаю, поставить ее здесь Я думаю, что я облажался.
Ведь что такое искусство PTR данный момент времени?
Null.
Так что, хотя, визуально, мы можем Очевидно, все эти
ребята здесь на сцене.
Я не следил за предыдущими человек в списке.
У меня нет пальцем указывая, В этом случае номер узла 34.
>> Так что давайте на самом деле начать над этим.
Так что теперь я на самом деле нужно Вторая локальной переменной.
И это то, что вы увидите в Сам образец кода C, где, как я иду,
когда я обновляю мою правую руку, чтобы указать Джейсон, тем самым оставляя Брайана позади, я
лучше начать использовать мою левую руку, чтобы обновления, где я был, так что, как я иду
через этот список -
более неловко, чем хотел Теперь вот визуально -
Я иду, чтобы добраться до конце списка.
>> Эта рука по-прежнему нулевой, который является довольно бесполезным, кроме указывать
Я ясно в конце списка но теперь по крайней мере, у меня есть эта
предшественника указатель, указывающий здесь, так что Теперь то, что руки и то, что нужно указатели
в обновлении?
Чья рука вы хотите перенастроить в первую очередь?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Итак, Дианы.
Где Вы хотите, чтобы указать Левая Дианы указатель в?
На 55, по-видимому, с тем чтобы мы вставили туда.
А где должны 55 указателя идти?
Вниз, представляющая нулевой.
И мои руки, на данный момент, не значения, потому что они были просто
временных переменных.
Так что теперь мы закончим.
>> Таким образом, дополнительные сложности там - и это не так сложно реализовать,
но нам нужна вторая переменная, чтобы сделать уверен, что прежде, чем я могу двигать правой
стороны, я обновить значение моей левой стороны, ПРЕД указатель в этом случае, так
что у меня есть задний указатель отслеживать, где я был.
Теперь, как в стороне, если вы думаете, что это через это чувство, что это
немного раздражает, чтобы сохранить след этого левой рукой.
>> Что бы другое решение этой проблемы были?
Если у вас есть, чтобы перепроектировать данных структуры мы говорим
через прямо сейчас?
Если это только отчасти чувствует себя немного раздражающим, вроде бы, два указателя
собирается по списку, кто еще мог были, в идеальном мире, поддерживается
информацию, которая нам нужна?
Да?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Совершенно верно.
Право так есть на самом деле интересное зародыш идеи.
И эта идея предыдущего указателя, указывая на предыдущий элемент.
Что делать, если я просто воплощением этого внутри самого списка?
И это будет трудно визуализировать Все это без бумаги
падения на пол.
Но предположим, что эти парни использоваться как их руки, чтобы иметь предыдущие
указатель, и следующий указатель, тем самым реализовать то, что мы назовем вдвойне
связанный список.
Которая позволила бы мне, чтобы разобраться перемотки, гораздо легче без меня,
программист, необходимости держать отслеживать вручную -
действительно вручную -
от того, где я был ранее в списке.
Поэтому мы не будем этого делать.
Мы будем держать его просто, потому что это собирается прийти в цене, в два раза
много места для указателей, если вы хотите вторую.
Но это действительно общий Структура данных известных как
дважды связанный список.
>> Давайте сделаем последний пример здесь и положить эти ребята из их страдания.
Так Malloc 20.
Поднимайтесь из прохода там.
Ладно, как тебя зовут?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Простите?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Demeron?
ОК поднимайся.
Вы должны быть 20.
Вы, очевидно, собираются принадлежат от 17 до 22.
Итак, позвольте мне узнать свой урок.
Я собираюсь начать указатель указывая на Брайана.
И я буду иметь мою левую руку обновлять только с Брайаном, как я переехать в
Джейсон, 20 проверка делает менее девяти?
Нет.
На 20 меньше, чем 17?
Нет.
На 20 меньше, чем 22?
Да.
Так что указатели или рук нужно изменить где они указывая сейчас?
>> Так что мы можем сделать, указывая на 17 20.
Так что это нормально.
Куда мы хотим, чтобы указать указатель сейчас?
В 22.
И мы знаем, где 22, опять же благодаря на мой временный указатель.
Таким образом, мы все в порядке там.
Так из-за этого временного хранения Я следил, где все.
И теперь вы можете визуально вдаваться в котором Вы принадлежите, и теперь нам нужно 1, 2, 3,
4, 5, 6, 7, 8, 9 шаров стресс, и аплодисменты для
эти ребята, если мы могли.
Красиво сделано.
>> [Аплодисменты]
>> Выступающий 1: Хорошо.
И вы можете держать части бумаги на память.
>> Ладно, так что, поверьте мне, это намного легче идти через это с
людей, чем с фактическим кодом.
Но то, что вы найдете в мгновение Теперь, то, что же - о, спасибо.
Спасибо -
является то, что вы увидите, что те же данные структуры, связанный список, может на самом деле
использоваться в качестве строительного блока, чтобы еще больше сложных структур данных.
>> И поймите, слишком тема здесь является то, что мы абсолютно ввели более
Сложность в реализации этого алгоритма.
Вставки, и если мы прошли через это, удаление и поиск, немного
сложнее, чем был с массивом.
Но мы получить некоторую динамику.
Мы получаем адаптивную структуру данных.
>> Но опять же, мы платим цену наличием некоторых дополнительные сложности, как в
его осуществлении.
И мы отказались от случайного доступа.
И, честно говоря, нет некоторых хороших чистое предметное я могу дать вам, что
говорит вот почему связанный список лучше, чем массив.
И оставить все как есть.
Потому что тема повторения теперь, даже более, что в ближайшие недели, является
что есть не обязательно правильный ответ.
>> Вот почему у нас есть отдельные оси дизайна для домашних заданий.
Это будет очень контекстно-зависимых хотите ли вы использовать эти данные
структуру или, что одно и оно будет зависит от того, что для вас важно в плане
ресурсов и сложности.
>> Но позвольте мне предложить, что идеальные данные Структура, Святой Грааль, были бы
то, что постоянная времени, независимо от того, сколько материал
внутри нее, не было бы удивительно, если структура данных, возвращаемая ответы
постоянное время.
Да.
Это слово в вашем огромном словаре.
Или нет, это слово не является.
Или любая такая проблема.
Ну давайте посмотрим, если мы не можем по крайней мере, сделать шаг на этом пути.
>> Позвольте мне предложить новую структуру данных, которая могут быть использованы для разных целей,
В этом случае называют хэш-таблице.
И вот мы на самом деле вернуться к взглянув в массиве, и в этом случае, а также
несколько произвольно, я нарисовал эту хэш-таблицы в виде массива рода
двумерный массив -
или, скорее, он изображен здесь как два одномерный массив - но это только
массив размером 26, так что, если мы называют массивом, настольный кронштейн
нуля прямоугольника в верхней части.
Таблица 25 кронштейн представляет собой прямоугольник в нижней части.
И это, как я мог бы нарисовать данные структура, в которой я хочу сохранить
имена людей.
>> Так, например, и я не буду рисовать Все это здесь, на накладные расходы, если я
было это массив, который я сейчас собираюсь называют хэш-таблицу, и это опять же
Расположение нулю.
Это вот расположение , и так далее.
Я утверждаю, что я хочу использовать эти данные Структура, ради обсуждения,
сохранять имена людей, Алиса и Боб и Чарли и другие подобные имена.
Так что думать об этом сейчас, когда начал , скажем, словарь
с большим количеством слов.
Они, оказывается, имена В нашем примере.
И все это слишком уместны, пожалуй, осуществление проверки орфографии, как мы
может для проблемных установить шесть.
>> Так что, если у нас есть массив от общего размера 26 так что это 25-й расположение
в нижней части, и я утверждаю, что Алиса Первое слово в словаре
имена, которые я хочу вставить в оперативную память, в эту структуру данных, где
инстинкты говорят вам, что Алисы имя должно идти в этом массиве?
>> У нас есть 26 вариантов.
Где мы хотим поставить ее?
Мы хотим ее в кронштейн нулю, не так ли?
Для Алисы, давайте назовем что нулю.
И B будет одной и С будут два.
Итак, мы собираемся писать Алиса имя здесь.
Если мы затем вставьте Боб, его Название пойду сюда.
Чарли пойду сюда.
И так далее вниз через этой структуры данных.
>> Это прекрасная структуры данных.
Почему?
Ну то, что время работы вставка имя человека в эту
Структура данных прямо сейчас?
Учитывая, что эта таблица будет реализован, действительно, как массив.
Ну, это постоянное время.
Это порядка единицы.
Почему?
>> Ну как вы определяете, Где Alice принадлежит?
Ты смотришь на какую букву ее имени?
Первое.
И вы можете получить там, если это строка, просто глядя на строку
Кронштейн нулю.
Таким образом, нулевой символ строки.
Это легко.
Мы сделали это в Crypto Назначение недели назад.
И то, как только вы знаете, что Алисы Письмо капитала, мы можем вычесть
от 65 лет и сам капитал, , что дает нам нулю.
Таким образом, мы теперь знаем, что Алиса принадлежит по месту нахождения нуля.
>> А если учесть, указатель на эти данные структуры, какой-то, как долго
мне потребуется, чтобы найти расположение нулю в массив?
Всего лишь один шаг, правая Это постоянное время из-за случайного доступа мы
Предлагаемый было особенностью массива.
Короче говоря, выяснить, что индекс имени Алисы, которая, по
этом случае, или давайте просто решать что к нулю, где B является одним и С
два, полагая, что из постоянная времени.
Я просто смотреть на нее первое письмо, выясняя, где ноль
массив также постоянное время.
Так что технически это как теперь два шага.
Но это все равно постоянно.
Так мы называем это Big O одного Таким образом мы вставлены Алиса в эту таблицу в
постоянное время.
>> Но, конечно, я веду себя наивная, да?
Что делать, если есть Аарона в классе?
Или Алисия?
Или любые другие имена, начинающиеся с А. Куда мы собираемся поставить
что человек, не так ли?
Я имею в виду, прямо сейчас есть только три люди на стол, поэтому возможно, мы
Аарон должен положить по месту нахождения ноль один два три.
>> Право, я мог бы поставить здесь.
Но тогда, если мы пытаемся вставить Давиду в этого списка, где же Давид идти?
Теперь наша система начинает нарушения вниз, вправо?
Потому что теперь Дэвид заканчивает здесь Если на самом деле Аарон здесь.
И вот теперь вся эта идея с чистая структура данных, которая дает нам
вставок постоянного времени уже не постоянное время, потому что я должен
проверить, о, черт возьми, кто-то уже по месту нахождения Алисы.
>> Позвольте мне исследовать остальную часть этого данные Структура, ища место, чтобы положить
кто-то, как имя Аарона.
И так, что тоже начинает принять линейное время.
Более того, если вы сейчас хотите найти Аарон в этой структуре данных, и вы
проверить и имя Аарона здесь нет.
В идеале, вы просто сказали бы Аарона не в структуре данных.
Но если вы начинаете освобождая место для Аарон, где должно было быть D
или E, вы, худшем случае, придется проверить Вся структура данных, в
этом случае она переходит в нечто линейный в размер таблицы.
>> Так что все в порядке, я буду это исправить.
Проблема здесь в том, что у меня было 26 элементов в этом массиве.
Позвольте мне изменить.
К сожалению.
Позвольте мне изменить его так, что вместо бытия размер 26 в общей сложности, обратите внимание на нижнюю
Индекс будет меняться к N минус 1.
Если 26 явно слишком мал для людей " имена, потому что есть тысячи
имена мира, давайте просто делать в 100 или 1000 или 10000.
Давайте просто выделить намного больше места.
>> Ну, что вовсе не обязательно снижает вероятность того, что мы не будем иметь два
люди с именами, начинающимися с, и Итак, вы собираетесь, чтобы попытаться положить
имена по месту нахождения нуля до сих пор.
Они все еще собираемся сталкиваются, которая означает, что мы все еще нужно решение, чтобы положить
Алиса и Аарона и Алисия и другие имена, начинающиеся с в другом месте.
Но как большая проблема это?
Какая вероятность того, что вы могут возникать конфликты в данных
структуры, как это?
>> Ну, позвольте мне - мы вернемся На этот вопрос здесь.
И посмотрите, как мы могли бы решить в первую очередь.
Позвольте мне подтянуть это предложение здесь.
То, что мы только что описали алгоритм, эвристические называются линейными
зондирования которой, если бы вы попытались вставить что-то здесь, в этом данные
Структура, которая называется хэш-таблицу, и там нет места там, вы
действительно исследовать структуры данных проверки, это доступно?
Является ли это доступно это доступно?
Является ли это доступно?
И когда он, наконец, вы вставьте имя, которое вы изначально
в других местах в этом месте.
Но в худшем случае, единственное место, может быть в самом низу данных
Структура, в самом конце массива.
>> Так линейного зондирования, в худшем случае, превратится в линейный алгоритм, где
Аарона, если он произойдет, будет вставлен последний В этой структуре данных, он может
сталкиваться с этой первой месте, но Затем закончиться неудачей в самом конце.
Так что это не постоянная время святой Грааль для нас.
Этот подход вставки элементов в структуру данных, называемую хэш
Таблица не кажется, постоянное время по крайней мере, в общем случае.
Это может превратится в нечто линейной.
>> Так что, если мы разрешения коллизий несколько по-другому?
Итак, вот более сложные подходить к тому, что до сих пор
называемый хэш-таблицу.
И хэш, а в сторону, что Я имею в виду, что индекс
Котором я говорил раньше.
Для хэш что-то может быть рассматривать как глагол.
>> Так что если вы хэш Алисы имя, хеш-функции, так сказать,
должна возвращать число.
В этом случае равно нулю, если она принадлежит на нулевом месте, один, если она принадлежит на
местоположение, и так далее.
Так что мой хэш-функции до сих пор было супер просто, только глядя на
Первая буква в чье-то имя.
Но хэш-функция принимает в качестве ввести некоторые части данных,
строка, целое все.
И он выплевывает обычно число.
И это число, где, что данные элемент принадлежит в структуре данных
известный здесь как хэш-таблицу.
>> Так что просто интуитивно, это несколько ином контексте.
Это фактически имеет в виду пример с участием дни рождения, где
там может быть столько, сколько 31 дней в месяце.
Но то, что этому человеку решить делать в случае столкновения?
Контекст в настоящее время, а не столкновение имена, но столкновение дни рождения,
если два человека имеют одинаковый день рождения 2-го октября, например.
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Да, так что здесь мы имеем более эффективного использования связанных списков.
Так это выглядит немного по-другому чем мы обратили его ранее.
Но мы, кажется, есть в массив на левой стороне.
В этом нет одного индекса, для не особой причины.
Но это все еще массиве.
Это массив указателей.
И каждый из тех элементов, каждый из эти круги или косая черта - слэш
представляющий нулевой - каждая из этих указателей по-видимому, указывающие на
какие данные структуры?
Связанный список.
>> Так что теперь у нас есть возможность жесткий код в нашей программе
Размер таблицы.
В этом случае, мы знаем, никогда нет более 31 дней в месяц.
Так жесткое кодирование значения, как 31 разумное в этом контексте.
В контексте имен, жесткого кодирования 26 не является необоснованным его людей
только имена начинаются с, например, алфавита с участием до Z.
>> Мы можем втиснуть их все в этих данных Структура пока, когда мы получаем
столкновения, мы не ставим здесь имена, мы вместо этого думать об этих клетках
а не как строки себя, но в качестве указателей, например, Элис.
И тогда Алиса может иметь другой указатель в другое имя, начинающееся с
А. и Боб на самом деле идет сюда.
>> И, если есть другой имя, начинающееся с В, он заканчивается здесь.
И поэтому каждый из элементов этой Таблица два, если мы разработали эту
немного умнее -
Давай, -
если мы разработали это немного больше умнее, теперь становится адаптивами
структура, в которой нет жесткого ограничения от того, сколько элементов вы можете вставить
в это, потому что если у вас есть столкновения, это нормально.
Просто идти вперед и добавить его в что мы видели немного назад было
известный как связанный список.
>> Ну давайте паузу на мгновение.
Какова вероятность столкновения в первую очередь?
Право, может быть, я по думал, может быть, Я на инженерных эту проблему,
потому что вы знаете, что?
Да, я могу придумать произвольное Примеры с верхней части моей головы, как
Allison и Аарона, но в действительности, задано равномерное распределение
входов, то есть некоторые случайные вставки в структуру данных, что на самом деле
Вероятность столкновения?
Хорошо получается, это на самом деле супер высокой.
Позвольте мне обобщить эту Проблема, как этот.
>> Таким образом, в комнате N CS50 студентов, что вероятность того, что по крайней мере
Два студента в комнате имеют одинаковый день рождения?
Так что есть что. Несколько Hund -
200, 300 людей здесь и несколько сотни людей у ​​себя дома сегодня.
Так что если вы хотели спросить себя, что это вероятность два человека
В этом номере, имеющем тот же день рождения, мы можем понять это.
И я утверждаю, на самом деле есть два людей с такими же день рождения.
>> Например, кто-нибудь имеют сегодня день рождения?
Вчера?
Завтра?
Все в порядке, поэтому он чувствует себя, как я собираюсь чтобы сделать это 363 или около того больше
раз на самом деле выяснить, Если у нас есть столкновения.
Или мы могли бы просто сделать это математически а не утомительно
делать это.
И предлагаю следующее.
>> Поэтому я предлагаю, чтобы мы могли моделировать Вероятность двух людей с
же день рождения, как и вероятность 1 минус вероятность не имеющий
тот же день рождения.
Таким образом, чтобы получить это, и это только причудливый способ написания этого, для
Первый человек в комнате, он или она может иметь любую одну из возможных
Дни рождения предполагая, 365 дней в году, с извинениями для лиц с
Февральская 29 лет.
>> Таким образом, первый человек в этом номере бесплатный иметь любое количество рождений
из 365 возможностей так, чтобы мы сделаем это 365 разделить на 365,
который является одним.
Следующий человек в комнате, если цель , чтобы избежать столкновения, можно только
его или ее день рождения о том, как много различных возможных дней?
364.
Таким образом, второе слагаемое в этом выражении по существу делают, что математика для нас
путем вычитания от одного возможный день.
А потом на следующий день, на следующий день, на следующий день до общего количества
людей в комнате.
>> И если мы, то рассмотрим, что же тогда есть вероятность не каждый имеющий
уникальные дни рождения, но опять же минус 1 что, что мы получаем выражение
, что может очень причудливо выглядеть следующим образом.
Но это более интересно смотреть на визуально.
Это график, где по оси абсцисс представляет Количество человек в комнате,
количество рождений.
На оси ординат вероятность столкновения, два человека
имеющие тот же день рождения.
>> И еду на дом от этой кривой что, как только вы получите как 40
студенты, твоя очередь на 90% вероятности комбинаторно двух
человек или больше имеющей тот же день рождения.
И как только вы получите 58 человек нравится это почти 100% шанс двух
людей в комнате собираются иметь же день рождения, хотя есть
365 или 366 возможных ведра, и Только 58 человек в комнате.
Просто статистически вы, вероятно, получить столкновений, которая в короткие
мотивирует это обсуждение.
Что даже если мы получить фантазии здесь, и начать с этих цепей, мы все еще
придется столкновений.
>> Так что возникает вопрос, что такое затраты на ведение операции вставки и удаления
в структуру данных, как это?
Ну позвольте мне предложить -
и позвольте мне вернуться к экрану над здесь - если мы п элементов в
список, так что если мы пытаемся вставить N элементов, и у нас есть
сколько всего ведра?
Скажем, 31 всего ведра в случае рождения.
Какая максимальная длина одного этих цепей потенциально?
>> Если снова есть 31 возможных Дни рождения в данном месяце.
А ведь это только слипания всех -
на самом деле это глупый пример.
Давайте делать, а не 26.
Так что, если на самом деле есть люди, чьи имена Начните с через Z, тем самым давая
нам 26 возможностей.
И мы, используя структуру данных, как тот, который мы только что видели, в результате чего мы имеем
массив указателей, каждый из которых указывает на связанный список, где
Первый список все с именем Элис.
Второй список с каждым имя, начинающееся с, начиная
с В, и так далее.
>> Какая вероятность длина каждого из эти списки, если предположить, хороший чистый
Распределение имен через Z по всей структуре данных?
Там в русских людей в структуре данных деленное на 26, если они красиво
распространиться по всей структуре данных.
Таким образом, длина каждого из этих цепей п деленное на 26.
Но в больших обозначение О, что это?
Что это на самом деле?
Так что это действительно просто п, не так ли?
Потому что мы говорили в прошлом, тьфу, что вы разделите на 26.
Да, на самом деле это быстрее.
Но в теории, это не принципиально все, что быстрее.
>> Таким образом, мы, кажется, не так уж много ближе к этой Святой Грааль.
На самом деле, это всего лишь линейное время.
Черт возьми, в этот момент, почему бы нам не Разместите один огромный связанный список?
Почему бы нам не использовать только один огромный массив для хранения имен
все в комнате?
Ну, есть еще что-то убедительным о хэш-таблицы?
Есть ли еще что-то убедительных о структуре данных
, который выглядит, как это?
Это.
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Да, и еще раз, если это просто линейный алгоритм времени и
линейное время структура данных, почему бы мне не просто хранить имя каждого в большой
массиве или в большом связанный список?
И прекратите делать CS намного труднее , чем она должна быть?
Что является убедительным по этому поводу, даже хотя я поцарапал его?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: заказчику не?
Дорогие больше.
Так вставками потенциально могли еще постоянной времени, даже если ваши данные
структура выглядит следующим образом, массив указателей, каждый из которых указывает на
потенциально связанный список.
Как вы могли бы достичь постоянной Время введения имена?
Приклейте наклейку на фронте, не так ли?
>> Если мы жертвуем дизайн гол ранее, где мы хотели сохранить
всех по именам, например, сортируют, или все цифры на этапе отсортированы,
Предположим, что у нас есть несортированный связанный список.
Это только стоит нам один или два этапа, Как и в случае с Беном и Брайан
ранее, вставить элемент в начале списка.
Так что, если мы не заботимся о сортировке все из имен, начиная с или все
имена, начинающиеся с B, мы все еще можем достижения постоянной время вставки.
Теперь глядя Алисы или Боба или любое имя в целом все еще что?
Это большое О от N деленное на 26, в идеальном случае, когда все это равномерно
распределены, где есть столько автора как есть Z, который, вероятно,
нереально.
Но это по-прежнему линейно.
>> Но и здесь мы возвращаемся к точке асимптотической обозначения бытия
Теоретически верно.
Но в реальном мире, если я утверждаю, что моя программа может сделать что-то 26 раз
быстрее, чем ваша, чья программа Вы собираетесь предпочитаете использовать?
Ваша или моя, которая в 26 раз быстрее?
Реально, лица, составляет 26 раза быстрее, даже если теоретически
наши алгоритмы работают в том же асимптотическое время.
>> Позвольте мне предложить другую Решение в целом.
И если этого не сразит вас наповал, мы из структур данных.
Так это он, синтаксического дерева -
вид глупое имя.
Оно происходит от извлечений, и слово пишется синтаксического дерева, т-р-и-е, из-за
Конечно поиска звучит как синтаксического дерева.
Но это история слова синтаксического дерева.
>> Так синтаксического дерева действительно своего рода дерево, и это также игра на это слово.
И хотя вы не можете достаточно увидеть его с этой визуализации, синтаксического дерева является
дерева структурированы, как семья дерево с одним предком наверху и много
из внуков и правнуков как оставляет на дне.
Но каждому узлу в виде дерева является массивом.
И это в массиве - и давай упрощать на мгновение - это
массив, в этом случае, размер 26, где каждый узел снова массив размера
26, где нулевой элемент в этом Массив представляет, а последний
элемент в каждом таком Массив представляет Z.
>> Так что я предлагаю, то, что эти данные структуре, известной как виде дерева, может быть
использоваться также для хранения слов.
Мы видели, как минуту назад, мы могли сохранить словами, или в данном случае имена, и мы
видели ранее, как мы можем хранить числа, но если мы ориентируемся на имена или строки
заметьте, что интересно.
Я утверждаю, что имя Максвелла Внутри этой структуры данных.
Где вы видите Максвелла?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: на левой стороне.
Так что интересно, с этими данными структура, а не магазин
Строка M-A-X-W-E-L-L обратной косой черты нулю, все непрерывно, а не то, что вы делаете
состоит в следующем.
Если это так синтаксического дерева структуры данных, каждый из которых узлов снова массива
и вы хотите сохранить Максвелла, сначала индекс и так корня узла, так что
сказать, верхний узел, в положении М, вправо, так
примерно в середине.
, А затем оттуда, вы будете следовать указателя на дочерние узлы, так сказать.
Таким образом, в том смысле, дерево семьи, вы будете следовать его вниз.
И это приведет вас к другому узлу На левой стороне, которая является
просто еще один массив.
>> И потом, если вы хотите сохранить Максвелл, вы найдете указатель, который представляет
, Которая является этот здесь.
Тогда вы идете к следующему узлу.
И обратите внимание - именно поэтому картины немного обманывает -
этот узел выглядеть супер крошечные.
Но право это Y и Z. Это просто автор усеченной
снимок так, чтобы вы на самом деле видеть вещи.
В противном случае это фото бы чрезвычайно широк.
Итак, теперь вы индекса в ячейку X, то W, то Е, то L, то L. Тогда в чем
это любопытство?
>> Ну, если мы используем этот вид новых взять на себя, как хранить строку в
структуры данных, вам все равно придется существенно галочку в данных
структуры, что слово заканчивается.
Другими словами, каждый из этих узлов так или иначе нужно помнить, что мы
фактически выполнили все эти указатели и уезжают немного
хлебных крошек на дне здесь этого Структура, чтобы указать, M-A-X-W-E-L-L представляет
действительно, в этой структуре данных.
>> Таким образом, можно сделать следующим образом.
Каждый из узлов на картинке мы просто пила имеет один, массив размером 27.
И это сейчас 27, так как в P установить шесть, мы фактически дают вам апостроф,
чтобы мы могли иметь имена, как O'Reilly и другие с апострофа.
Но та же идея.
Каждый из этих элементов в массива указывает на структуру
узел, так что просто узлом.
Так что это очень напоминает нашей связанного списка.
>> А то у меня логическое, который я называю слово, которое просто будет
верно, если слово заканчивается на этом узел в дереве.
Это по сути, есть немного треугольника мы видели несколько минут назад.
Так что, если слово заканчивается в этом узле в Дерево, это слово поле будет правдой,
который концептуально галочки, или мы рисуем этот треугольник, да там
это слово здесь.
>> Так что это синтаксического дерева.
А теперь вопрос в том, что является время его работы?
Он большой O п?
Это что-то еще?
Ну, если вы п имена в этих данных Структура, Максвелл всего лишь один из
них, что время работы вставки или найти Максвелла?
Что время работы вставки Максвелла?
Если есть другие названия N уже в таблице?
Да?
>> СТУДЕНТ: [неразборчиво].
>> Выступающий 1: Да, это длина имени, не так ли?
Так М-а-х-З-е-л-л поэтому он чувствует себя, как это Алгоритм Big O семи.
Теперь, конечно, имя будет варьироваться в длину.
Может быть, это краткое имя.
Может быть, это длинное имя.
Но то, что ключевым здесь является то, что это постоянное число.
А может быть, это не совсем постоянное, но Бог, если реально, в
словарь, там, наверное, некоторый предел на количество букв в
имя человека в конкретной стране.
>> И таким образом, мы можем предположить, что значение является постоянным.
Я не знаю, что это такое.
Это, наверное, больше, чем мы думаем, что это такое.
Потому что всегда есть какой-нибудь угол случае с сумасшедшим длинное имя.
Так что давайте называть это К, но она по-прежнему постоянная предположительно, потому что каждый
назвать в мире, по крайней мере конкретной страны, является то, что длина или
короче, так что это постоянно.
Но когда мы сказали что-то большое O постоянного значения, что это такое
действительно эквивалентны?
Это действительно одно и то же как говорят постоянное время.
>> Сейчас мы вроде обмана, верно?
Мы вроде используя некоторые теории здесь, чтобы сказать, что хорошо, порядка К
действительно только порядка одной, и это постоянное время.
Но это на самом деле.
Поскольку ключевое понимание в том, что если мы имеем п имена уже в этом
структуру данных, и мы вставляем Максвелл, это количество времени, которое требуется нам
вставить Максвелла на всех пострадавших по тому, как много других людей
в структуре данных?
Не похоже, чтобы быть.
Если бы я был миллиард больше элементов в этой дерева, а затем вставить Максвеллом
Он на всех пострадавших?
Нет.
И это в отличие от любого дня данные структур, которые мы видели до сих пор, где
время работы вашего алгоритма совершенно не зависит от того, сколько
материал или еще не был В этой структуре данных.
>> И так с этим дает вам сейчас возможность установить шесть р, которая будет
снова связано с осуществлением собственного проверка орфографии, чтения в 150 000
словами, как лучше сохранить эту не обязательно является очевидным.
И хотя я стремился найти Святой Грааль, я не
утверждают, что это синтаксического дерева.
В самом деле, Хеш-таблицу можно очень хорошо оказаться гораздо более эффективным.
Но это только -
это только одна из проектных решений Вы должны сделать.
>> Но в заключение давайте 50 или около того секунды, чтобы взглянуть на то, что лежит
впереди на следующей неделе и далее мы переходим из этой командной строки
С миром, если на веб-программы вещей основан и языков, как PHP и
JavaScript и сам Интернет, протоколов, таких как HTTP, которые у вас есть
само собой разумеющимся, в течение многих лет сейчас, и каждый набрал больше
день, пожалуй, и не видел.
И мы начнем отогните слоях Что такое Интернет.
А что это за код, который лежит в основе сегодняшней инструментов.
Так 50 секунд этот тизер здесь.
Я даю вам Воины Сети.
>> [ВОСПРОИЗВЕДЕНИЕ ВИДЕО]
>> -Он пришел с сообщением.
С протоколом все свое.
Он пришел в мир жестоких брандмауэров, безразличными маршрутизаторы, и опасности далеко
хуже, чем смерть.
Он быстр.
Он сильный.
Он TCPIP.
И у него есть ваш адрес.
Воины в Сети.
>> [КОНЕЦ ВИДЕОВОСПРОИЗВЕДЕНИЕ]
>> Выступающий 1: То есть, как в интернете будем работать на следующей неделе.