>> DAVID МАЛАН: Хорошо.
Добро пожаловать обратно в CS50.
Это начало 8-й недели.
И напомнить, что проблема набора 5 закончившийся с немного сложной задачей.
Так что если вы восстановить все ваши обучения стипендиатов и фотографии СА
в файле card.raw, Вы имеете право Теперь, чтобы найти все эти люди, и
один счастливый победитель будет ходить домой с одним из этих вещей, скачок движения
устройство, которое можно использовать для окончательной проектов, например.
>> Это, каждый год приводит к немного жуткий.
И так, что я думал, что сделать, это поделиться с вами некоторыми из нот, которые имеют
туда и обратно в течение штатное расписание поздно.
Например, только вчера вечером, цитаты конец цитаты, от одного из персонала
Члены "Я просто был студент стук в мою дверь, чтобы сделать снимок со мной.
Сталкеры, скажу я вам. "Начался достаточным описанием, а затем мы переехали
на, час или чуть позже, "У меня было студент ждет меня после раздела
и у него были все наши имена и фотографии на несколько листов бумаги. "Хорошо.
Так организовано, но не все, что жуткое еще.
>> Затем: "Я был за городом, в эти выходные, и когда я вернулся, было один в
мое
спальню. "[смеется]
DAVID МАЛАН: Следующая цитата из персонала пользователя ", студент пришел ко мне домой на
Сомервилла в 4 утра сегодня утром. "Далее персонала ", я добрался до гостиницы в Сан-
Франциско и студент ждал меня в лобби с тремя зеркалок ".
Тип камеры.
"Я даже не на персонал в этом семестре, но студент ворвался в мой дом это
утром и записал все это со стеклом Google. "И тогда, наконец,
"По крайней мере 12 человек были с нетерпением ждет меня, когда я вышел из своего
лимузина, а потом я
проснулся. "Хорошо.
Так что среди фотографий, как вы Напомним, что в этот парень здесь, кто вы
могли бы знать, как Мило банан, который живет с Лорен Карвалью, наши головы
преподавании Fellow.
Мило, Мило, иди сюда мальчик.
Майло.
Имейте в виду, что он носит Google стекла, так что мы покажем вам все это после.
Так что это Мило, если вы хотели бы сфотографироваться с ним позже.
Если вы хотите, чтобы высматривать на аудиторию там.
ОК.
Это хорошие кадры.
Ну, Мило банан.
О, не делайте этого.
>> [Смеется]
>> ОК.
Так слово, то о том, что ждет впереди, потому что, как мы начинаем переход,
На этой неделе В частности, из С в командной строки среды и PHP
JavaScript и SQL и HTML и CSS в веб-среде, мы будем
оснащения вам все больше знаний для
потенциальных окончательного проектов.
С этой целью, конечно, имеет Традиция проведения семинаров, которые
находятся на тангенциальном темы к курсу.
Очень, связанных с программированием и разработки приложений и так далее, но
не обязательно изучены собственного курса учебной программе.
>> Так что если вы могли бы быть заинтересованы в одном или несколько семинаров в этом году,
зарегистрироваться на cs50.net/seminar.
Есть старший семинары на cs50.net/seminars.
И в реестр до сих пор в этом году Восхитительные веб-приложений с Рубином на
Рельсы, который является альтернативой языка PHP.
Компьютерная лингвистика.
Введение в IOS, которая является платформе, которая используется для iPhone и
Ipad развития.
JavaScript для веб-приложений, мы рассмотрим , но в этом семинаре, вы перейдете
более подробно.
>> Прыжок движения, так что мы на самом деле есть наших друзей из Leap движения,
самой компании, присоединяйтесь к нам.
Завтра, по сути, обеспечить практический семинар, если
представлять интерес для Вас.
Meteor.js, альтернативный прием Использование JavaScript не в браузере,
а на сервере.
Node.js, который очень в том же духе, а также.
Гладкий дизайн Android.
Android Будучи очень популярным альтернативным Телефон для IOS и Windows
и других мобильных платформ.
И веб активной обороне.
>> Таким образом, в самом деле, если вы хотите принять участие в этом, позвольте мне
сделать это к сведению.
Мы очень рады сообщить, что наши друзья в Leap
Движение, которое является запуск -
это устройство действительно просто пришел из несколько месяцев назад -
любезно пожертвовал 30 таких устройств классу столько студентов, если
Вы хотели бы заимствовать аппаратных к концу семестра и использовать его для
фактического конечного проекта.
Они поддерживают несколько языков.
Никто из них не C, ни один из них PHP, так реализовать один или несколько из этих семинары
может оказаться интересов.
И все они будут сняты в том случае, если вы не в состоянии
лично присутствовать на заседании.
Расписание будет объявлено через электронной почты, как мы укрепить номеров.
>> И, наконец, если вы идете в projects.cs.50.net, это веб-сайт
мы поддерживаем каждый год, что мы приглашаем Люди из сообщества, преподавателей
ведомств, персонала, и обе в пределах CS50 к
предложить проектные идеи.
Вещи, представляющие интерес для студенческих групп.
Вещи, представляющие интерес для отделов.
Так что свою очередь, есть, если вы боретесь с неопределенностью относительно того, что вы
сами хотели бы заняться.
>> Так последний раз мы ввели возможно более сложную структуру данных, чем мы
видели в прошлые недели.
Мы были довольно использовании массивов счастливо, как полезно, если
упрощенные структуры данных.
Тогда мы ввели эти, которые Конечно это связные списки.
И то, что было одним из мотивов для введения этой структуры данных?
Да?
Что это?
>> АУДИТОРИЯ: динамические размеры.
>> DAVID МАЛАН: динамические размеры.
Так в то время как в массиве, вы должны знаю его размер заранее, когда
Вы передать его.
В связанном списке, вы не должны знать, что.
Вы можете просто Malloc или, более общо, выделить дополнительно
узла, так сказать, в любое время вы вставить дополнительные данные.
И не узел без предварительно смысл.
Это всего лишь общий термин, описывающий своего рода контейнер, который мы
использование в нашей структура данных для хранения некоторый пункт интереса, который в этом
случае, оказывается, целых чисел.
>> Но всегда есть компромисс.
Итак, мы получаем динамические размеры данных структуры, но какую цену мы платим?
Чем недостаток связанных списков?
Да?
>> АУДИТОРИЯ: требуется больше памяти.
>> DAVID МАЛАН: она требует больше памяти, как именно?
>> АУДИТОРИЯ: [неразборчиво].
>> DAVID МАЛАН: Совершенно верно.
Так что теперь мы указателей занимая дополнительную память, что мы ранее
не нужны, потому что преимущество массива, конечно, является то, что
все в смежных, спины чтобы спина к спине, которая
дает произвольным доступом.
Потому что только с помощью квадратных скобок обозначения, или более технически указатель
арифметика, очень простая того, Вы можете получить доступ к любому
элементов в постоянное время.
И в самом деле, это своего рода намек на другая цена, которую мы платим с
связанный список.
>> Что происходит с время работы что-то вроде поиска, если я хочу
Приведите пример и внутри связанного списка?
Что значит мой время работы стал?
Big O н.
Если он сортируется?
Что делать, если структура данных разбираются?
Могу ли я сделать лучше, чем большие О п для поиска?
Нет, потому что в худшем случае он может очень хорошо быть отсортированы, но количество
Вы ищете может быть большим.
Это может быть номер 100, которая может случиться, что все
пути в конце.
И потому что вы можете получить доступ только к связанным Список в этом осуществлением
пути ее первый узел, ты все еще отчасти не повезло.
Вы должны пройти все это от первого до последнего, чтобы найти
что большое значение, как 100.
Или определить, если это даже не было.
>> Поэтому мы не можем делать то, что алгоритм в данных структуру, которая выглядит следующим?
Мы не можем сделать бинарный поиск, потому что бинарный поиск требует, чтобы у нас были
произвольным доступом.
Мы могли бы просто прыгнуть с места на месте без последующей
эти хлебные крошки в виде всех этих указателей.
>> Теперь, как мы осуществить это?
Ну, если мы идем на экран при этом, если мы можем быстро переопределить эти данные
Структура -
мой почерк не все, что отличная здесь, но мы постараемся.
Так ЬурейеЕ структуры, и что я хочу, чтобы эта вещь здесь?
Node.
Так что я буду приступить к нам.
А теперь, то, что должно быть внутри Структура данных для этого отдельно
связанный список?
Сколько полей?
>> Так два.
Один из них довольно легко.
Так Int N.
И мы могли бы назвать N, что мы хотим, но она должна быть Целочисленное если мы
реализации связанного списка для целых чисел.
А теперь что же второй поля должны быть?
Struct узла *.
Поэтому, если я структуру узла *, а потом я можно назвать это также то, что хочу,
но только быть ясно, что я буду называть его рядом, как мы делали.
И тогда я закрою фигурные скобки.
>> И теперь, как в прошлый раз, Я положил узел здесь.
Но если я объявляю это как узла, почему я беспокоить быть таким
подробный здесь в объявлении структуры * следующий узел, в отличие
просто узел * следующий?
Да?
>> АУДИТОРИЯ: [неразборчиво].
>> DAVID МАЛАН: Совершенно верно.
Именно так.
Поскольку C действительно приведет вас в прямом и видит только определение узла
пути сюда, вы не можете ссылаться на него здесь.
Таким образом, мы имеем такую ​​преимущественного Объявление здесь, которые по общему признанию
более подробный.
Struct узел, то есть теперь мы можем получить доступ к нему
внутренней структуры данных.
>> И, как в стороне, потому что это становится чуть более субъективный сейчас,
звезды технически может пойти сюда, он может пойти здесь, он может
даже пойти в середине.
Мы приняли, в стиле руководства для Конечно, Конвенция сдачи
звезды рядом с данными тип, который в данном случае
будет структура узла.
Но поймите, во многих учебниках и онлайн ссылки, вы, возможно, действительно
увидеть его на другой стороне.
Но так же, как понимают, что будет на самом деле работать, и вы должны быть просто
последовательным.
>> Хорошо.
Так, чтобы было наше заявление из структуры узла.
Затем мы начали делать больше сложные вещи.
Например, мы решили ввести что-то вроде хэш-таблице.
Так вот хэш-таблицу размером N, индексируется от 0 в левом верхнем углу, чтобы н
минус 1 в левом нижнем углу.
Это может быть хэш таблица на все.
Но какие вещи мы разговаривали об использовании хэш-таблицу для?
Хранение Что?
>> Имена.
Мы могли бы сделать имена, как мы сделали в прошлый раз.
И в самом деле, вы можете хранить все что угодно.
И мы увидим это снова PHP и JavaScript.
Хэш-таблицы является хорошим рода швейцарских Армейский нож, что позволяет хранить
почти все, что вы хотите внутри , связывая его со значениями ключей.
Ключи с ценностями.
>> Сейчас в этом простом случае, наши Ключи просто цифры.
Мы реализации хэш таблице в виде массива.
И так ключи 0, 1, 2, и так далее.
И поэтому мы, как люди, решил в прошлом недели, что вы знаете, что, если мы
собираетесь хранить имена, давайте просто произвольно, но довольно разумно,
Предположим, что Алиса, имя, просто быть проиндексированы на 0.
И Боб, имя B, будут индексироваться в 1, и так далее.
Так у нас было соответствие между входами, которые являются строками, и хэш
местах, которые являются числами.
>> Таким образом, этот процесс обычно называют хэш-функции, и вы действительно можете
реализовать его в коде.
Если бы я хотел реализовать хэш-функции , который делает именно то, что мы
только что описал в прошлый раз, я мог бы объявить функцию, которая принимает в качестве
входного например -
и давайте сделаем это на этом Экран здесь.
Если бы я хотел реализовать хэш Функция, я мог бы сказать
что-то вроде этого.
>> Это собирается вернуться Int.
Это будет называться хэш, и это собирается принять в качестве аргумента
строка, или мы можем быть более надлежащего сейчас, и сказать, символ *, мы будем называть его с.
И тогда вся эта функция должна делать, В конечном счете, это вернуть Int.
Теперь, как он это делает, что может Не будь так ясно.
Я собираюсь реализовать это без любого форма проверки ошибок прямо сейчас.
Я просто собираюсь слепо сказать, вернуться что есть под кронштейн с 0, минус,
скажем, в столице запятой.
>> Полностью нарушена.
Это не идеально, потому что Один из них, что, если с является недействительным?
Плохие вещи будут происходить.
Два, что, если первая буква в этом имя не буквы?
Это не собирается превратить из хорошо также.
Это может быть строчной буквы или нет письмо вообще.
Так полностью возможности для улучшения, но это основная идея.
>> То, что мы на прошлой неделе описал устной форме просто процесс картирования Алиса
0 и Боба 1 могут быть выражены конечно, более formulaically как C
Здесь действуют.
Зашел еще хэш, принимает строку как ввод, а затем каким-то образом делает что-то
с этого входа для получения выходного.
Не в отличие от нашего черного поле Описание что мы давно сделали.
Я не знаю, как это могло бы быть работ под капотом.
>> Для задачи набор 6, одна из проблем, для вас, чтобы решить, что
Будет ли ваш хэш-функция может быть?
Что будет внутри этого черного рамки, и, предположительно, это будет
немного более интересно, чем это, и безусловно, более склонны к ошибкам
проверок, чем данный осуществление.
>> Но могут возникнуть проблемы, не так ли?
Если есть структура данных, таких как это Один из них, что одна из проблем
вы можете столкнуться с течением времени, как вы вставляете все больше и больше имен в
хэш-таблицы?
Вы получаете столкновений, не так ли?
Что делать, если у вас есть Алиса и Аарон, два человека, имена которых произошло
начать с?
То возникает вопрос, где вы положить второй такое название?
>> Ну, вы можете наивно просто положить его где Боб принадлежит, но потом Боб
виды резьбовых, если вы попытаетесь вставить его имя рядом и
там нет места для него.
Так что вы можете положить Боб где Чарли, и вы можете себе представить, это очень быстро
возложенных в немного беспорядок.
Что-то линейной в конце концов, где вы просто придется искать все это
ищет Алису или Боба или Аарона или Чарли.
>> Так вместо этого мы предложили, а не просто линейно зондирования для открытых пространств
и шлепаясь имена там, мы предложил необычный подход.
Хэш-таблицы по-прежнему осуществляться с массив индексов, но тип данных
Сейчас эти показатели были указатели.
Указатели на что?
Указатели на связанные списки.
>> Потому напомним, что связанный список действительно только указатель на узел и
узел имеет следующее поле, и узел имеет следующее поле, и так далее.
Так что вы можете думать об этом массиве на левой стороне хэш-таблицу в качестве
ведущие на связанный список.
Преимущество который, если вы получите столкновения между Алисой и Аарон,
что вы будете делать с второго такого человека?
Вы просто прикрепить его или ее конце, или даже начало
этого связанный список.
>> А на самом деле, давайте просто лапши через , что только на одну секунду.
Где бы лучше всего подходят?
Если я вставляю Алиса и она заканчивается на первого места, то я стараюсь
вставить имя Аарона, и есть Очевидно, столкновения, я должен положить
его в начале связанного списка?
Вот на этом первом месте, или в конце?
>> АУДИТОРИЯ: [неразборчиво].
>> DAVID МАЛАН: OK.
Я слышал начинается.
Почему в самом начале?
>> АУДИТОРИЯ: [неразборчиво].
>> DAVID МАЛАН: OK.
Это алфавитный, так что это хорошо.
Это хороший собственности.
Это сэкономит мне некоторое время потенциально.
Она не позволит мне сделать бинарный поиск, но я может по крайней мере быть в состоянии вырваться из
из цикла, если я понимаю, ну, я кстати Аарон прошлом были бы в таком
отсортированный связанный список.
Я не придется тратить свое время, смотря весь путь до конца.
Так, что это разумно.
Почему еще может вы хотите вставить сталкивающихся имя в
начало списка?
Что это?
>> АУДИТОРИЯ: [неразборчиво].
>> DAVID МАЛАН: Это может занять много времени, чтобы получить в конце списка.
И в самом деле, больше и больше.
Чем больше имен, что вы вставляете начать с, тем больше, что
Цепь собираетесь получить.
Чем дольше, что связано Список собираетесь получить.
Значит, вы действительно просто тратите свое время.
Может быть, вам лучше поддержание постоянное время вставки, Big O 1,
, всегда положив сталкивающихся на имя начале связанного списка,
а не беспокоиться столько о сортировке.
>> Какой самый лучший ответ?
Непонятно.
Это отчасти зависит от того, распределение, что картина
из имен вы вставляете.
Это не обязательно Очевидный ответ.
Но вот, опять же, Дизайн возможность.
>> Таким образом, мы тогда смотрели на эту вещь, которая действительно другие большие возможности
для р-набор 6.
И поймите, если вы еще не сделали, Zamyla ныряет в обе эти, хэш
таблиц и попыток, более подробно.
И видео пошаговое руководство встроенные в р-набор спец.
Это было синтаксического дерева -
Т-Р-И-Е. И то, что было интересно это было, что время работы
поиска имя, как Максвелл в прошлый раз, было большим O чего?
Что это?
>> Аудитории: количество букв.
>> DAVID МАЛАН: Количество букв.
Я слышал о двух вещах.
Количество писем и постоянное время.
Так что давайте идти с этим в первую очередь.
Количество букв.
Ну, эта структура данных, напомним, является как дерево, генеалогическое дерево, каждая из
узлы которого состоят из массивов.
А те массивы указателей на других подобных узлов или других подобных
массивов в дереве.
>> Так что, если мы хотели затем определить ли Максвелл находится здесь, я мог бы пойти
в первом массиве, на самом верху дерева, так называемый корень, верхней части
дерева, а затем следовать за указателем м, Затем указатель, то х,
W, E, L, L.
А потом, когда я вижу некоторые специальные символы, обозначается здесь как треугольник.
В коде вы увидите, что мы предлагаем Вам реализован как логический, просто говорю, что да
или нет, слово заканчивается.
>> Ну, раз мы пошли в M-A-X-W-E-L-L, чувствует, как семь, может быть,
восемь, если мы сделаем еще один мимо него, восемь шаги, чтобы найти Максвелла.
Или назовем его К. Но вспомним последний время, я утверждал, что, если есть
реально максимальной длиной по Словом, как 40 с лишним персонажей,
Максимальная длина подразумевает постоянное значение.
Так на самом деле, да, это технически Big O 8 или 7, или действительно большой O К. Но
если есть конечная крышка на то, что K может быть, это константа.
И так это большое О от 1 на конце дня.
>> Не в реальном мире.
Не тогда, когда вы на самом деле начать смотреть ваши часы, как работает ваша программы.
Это абсолютно будет немного медленнее, чем действительно постоянной
Время с одного шага.
Это будет семь или восемь шагов, но все же это гораздо, гораздо лучше
, чем алгоритм, как Big O п, что зависит от размера того, что в
структуре данных.
>> Обратите внимание на вверх здесь мы можем вставить еще миллион имен в этой
Структура данных, но сколько еще шагов он собирается взять нас найти
Максвелл в таком случае?
Ни один.
Он не влияет.
И на сегодняшний день, я не думаю, что мы видели Пример структуры данных, либо
Алгоритм, который был полностью не зависит от внешних
поведения, как, что.
Но это не может быть удивительным.
Это не может быть единственным решением для р-набор
>> И это не так.
Это не обязательно данные структуру вы должны тяготеть к,
потому что, как хэш-таблицы, компромисс.
Какой ценой вы платите здесь?
Памяти.
Я имею в виду, это зверское объем памяти.
И вы не можете достаточно увидеть его здесь, потому что Автор этого снимка
Очевидно, усеченный всех массивов и мы не видим много и
B и C и Q и Y в и Z в этих массивах.
Но они там.
>> Каждый из этих узлов целый ряд от около 26 или более байтов, каждый из
которая представляет собой букву.
27 в нашем случае, так что мы можем поддержать апострофа в задаче набора.
Так что эта структура данных действительно, действительно плотная и широкая.
И уже одно это может в конечном итоге замедление вещи вниз, или по крайней мере стоить вам
намного больше места.
Но, опять же, можно сделать сравнения здесь.
>> Напомним, некоторое время назад, мы добились многого более захватывающее время работы в сортировке
когда мы используем сортировки слиянием, но цена мы заплатили, чтобы достичь N § п о слиянии
Сортировать требует, чтобы мы тратим больше, что ресурс?
Больше места.
Мы нуждались в массив вторичных скопировать людей в, так же, как
мы сделали здесь на сцене.
Итак, еще раз, нет явных победителей, но просто субъективные дизайна
принимать решения.
>> Хорошо.
Так как насчет этого?
Любой признает которых D-Hall?
ОК.
Так три из нас.
Mather дом.
Так что это для столовой Мазера.
Бьюсь об заклад, все залы столовой есть стеки лотки, как это.
И это на самом деле представитель в то, что мы
очевидно, уже видели.
Мы назвали ее буквально стек.
И в стек, с точки зрения вашего памяти компьютера, где данные идут
в то время как функции при вызове.
>> Например, какие вещи идут в стеке по отношению к
Разметка памяти мы обсуждали недель в прошлом?
Что это?
>> АУДИТОРИЯ: вызовы функций.
>> DAVID МАЛАН: Мне очень жаль.
>> АУДИТОРИЯ: вызовы функций.
>> DAVID МАЛАН: вызовы функций, но В частности, то, что внутри каждого
эти кадры?
Какие вещи?
Да.
Так что локальные переменные.
В любое время мы нуждались в некотором локальном хранилище, как аргумент, или INT I, или десятичного
Temp, или любой другой местный переменная, мы были
положить, что в стеке.
И мы называем это стек, потому что этого наслоения идея.
Просто вид матчей с реальностью, Концепция их.
>> Но оказывается, что стек может также рассматриваться как структура данных,
Альтернативой массиве, альтернативные на связанный список.
Что-то концептуально более интересным что все еще может быть
реализованы с использованием любой из этих вещи, но это другой тип
Данные структуры поддержки, на самом деле, только две операции.
Но вы можете добавить на любителя возможностей, чем эти.
Но эти основы -
толкать и поп-музыки.
>> А идея со стеком в том, что если имеем здесь, с или без Анненберга
зная, поднос из соседнего дома с номером 9 на нем.
Так что просто Int.
И я хочу, чтобы нажать на эту данными Структура, которая в настоящее время является пустым.
Рассмотрим в нижней части стопки.
Я бы подтолкнуть этот номер 9 на стек, а теперь это прямо там.
>> Но самое интересное о стеке том, что если сейчас я хочу, чтобы подтолкнуть
другое значение, как и 17, и я толкаю этого в стек, я собираюсь сделать
только интуитивно вещь, я просто хочу, поставить его именно там, где мы, люди,
был бы склонен выразился, на вершине.
Но что интересно сейчас в том, как я могу получить в 9?
Вы знаете, я не без некоторого усилия.
>> Так что интересно стек в том, что дизайн,
это структура данных ЛИФО.
Глупый способ описания последний вошел, первый вышел.
Таким образом, последнее число в в это время было 17 лет.
Так что, если я хочу что-то от поп стопки, он может быть только 17.
Таким образом, есть обязательный порядок операций здесь, где последний элемент
В должен быть первым одного из них.
Следовательно акроним, ЛИФО.
>> Так почему это могло бы быть полезным?
Являются ли их контекста, в котором нужно хотят структуру данных, как это?
Ну, это, безусловно, полезно внутри компьютера.
Так операционных систем четко использовать эту вид структуры данных для стеков.
Мы также увидим ту же идею когда дело доходит до веб-страниц.
Так на этой неделе и на следующей неделе и за ее пределами, и, как вы приступить к реализации веб-
страниц на языке, называемом HTML, Вы можете фактически использовать структуру данных, как
это определить, является ли страница правильно отформатирован.
Потому что мы увидим все веб-страницы следует своего рода иерархию, отступы
который, в конце концов, быть древовидной структуры под капотом.
Так об этом чуть позже.
>> Но сейчас, давайте предлагать для момента, как мы могли бы идти о
представляющие, что стек?
Позвольте мне предложить, чтобы мы осуществили стек с такой код.
Так стек будет иметь внутри него две вещи, массив, называемый поддоны
просто чтобы быть в соответствии с демо.
И каждый из элементов в этом массиве будет типа Int.
И мощности, по-видимому, что?
Потому что я не написал Полное определение здесь.
>> Это, пожалуй, максимально размер массива.
И это, вероятно, объявлен как резкое определяют в верхней части файла, некоторые
вид постоянной, как следует из просто капитализации.
Таким образом, где-то мощность определяется в качестве максимального размера.
Между тем, внутри структуры данных известного как стек там будет
быть целым числом только известны просто как размер.
>> Так что, если бы я должен был представить это сейчас графически, давайте предположим, что это
весь черный прямоугольник представляет свой стек.
Внутри это двумя переменными.
Так что я собираюсь сделать Первый, как размер.
А второй я собираюсь привлечь в виде массива.
>> Но только, чтобы держать вещи упорядоченно, Обычно я хотел бы обратить массив как
это, но это отчасти хорошо если мы соответствует действительности, или
соответствует ментальной модели.
Итак, позвольте мне сделать вместо массива вертикально, который находится всего, опять же,
художника исполнения.
На самом деле не важно, что это находится под капотом.
И мы будем говорить, что, по умолчанию, мощность будет три.
Так что это будет расположение 0, то это будет номером 1, это
будет расположен в 2.
>> Если бы я с подкупить стресс мяч, не так кто-то хотел, чтобы придумать и запустить
борту здесь на мгновение?
Хорошо, видел вашу руку первым.
Поднимайся.
Хорошо.
Так что я считаю, что это Стивен.
Поднимайся.
Хорошо.
>> Но предположим, что теперь мы перемотать на начальном состояние мира, где я
только что объявил стека, и это будет мощностью три.
Однако размер еще не определен.
Лотки еще не был определен.
Таким образом, несколько вопросов в первую очередь.
И позвольте мне дать вам микрофон, чтобы вы могли более активное участие в этом.
>> Так что же находится внутри размер в данный момент в срок, если все, что я сделал,
заявил стек с одной строки кода?
>> Стивен: Не так много.
>> DAVID МАЛАН: Хорошо, не так много.
Знаем ли мы, что внутри размер, мы знаем, что внутри
этого массива здесь?
>> Стивен: Просто случайный код, верно?
Просто -
>> DAVID МАЛАН: Да, я собираюсь называют это код, но случайных -
>> Стивен: Вещей.
>> DAVID МАЛАН: Такие вещи, как случайная
>> Стивен: бит.
>> DAVID МАЛАН: биты, да?
Так мусор значения, верно?
Так перестановки из 0 и 1 в.
Остатки предыдущих случаях использования этой памяти.
И мы действительно не знаем, какие именно значения которые, таким образом, мы, как правило привлечь их
в виде знаков вопроса.
>> Поэтому первое, что мы по-видимому собирается хотите сделать здесь -
и позвольте мне дать это поле внутри оттуда название - лотки.
Что мы должны предположительно инициализации размер, если мы хотим
начать использовать этот стек?
>> Стивен: Лоток 3 к югу.
>> DAVID МАЛАН: Так, хорошо.
Чтобы было ясно, мощностью объявлен в другом месте, как три.
И вот что я использовал выделить массива.
Размер собирается обратиться к сколько Лотки данный момент в стеке.
>> Стивен: Ноль.
>> DAVID МАЛАН: Так оно и должно быть равно нулю.
Так что вперед, и с любым пальцем, нарисовать нуля в размерах.
Хорошо.
Так что теперь, что внутри этого здесь, мы не знаем.
Это действительно просто значения мусор.
Так мы смогли привлечь вопросительные знаки, но Давайте держать совет чистыми пока
потому что это не имеет значения что там.
Нам не нужно для инициализации массива ни к чему, потому что, если мы знаем, что
размер стека равен нулю, а мы Не следует смотреть на что-либо в
этот массив во всяком случае у данный момент времени.
>> Теперь предположим, что я нажимаю 9 числа в стек.
Как мы должны обновить структуру данных внутри этого черного ящика?
Какие ценности нужно изменить?
>> Стивен: В -
размер?
>> DAVID МАЛАН: OK.
Размер должно стать то, что?
>> Стивен: размер должен быть один.
>> DAVID МАЛАН: OK.
Так что размер должен стать одним.
Таким образом, вы можете сделать это в несколько способов.
Позвольте мне дать вам, теперь ваша палец ластик.
Хорошо.
Тогда сейчас пальца кисти.
Хорошо.
А теперь, что еще должно измениться, очевидно, что в структуре данных?
>> Стивен: Мы собираемся от снизу вверх до 9.
>> DAVID МАЛАН: 9.
ОК, хорошо.
Так до сих пор не имеет значения, что поставлено на местоположение одного или двух, потому что они
мусор значения, но мы не должны беспокоиться ищет там, потому что размер
говорит нам, что только первый элемент на самом деле законно.
Так что теперь я нажимаю на 17 списка.
Что происходит с этой картиной?
>> Стивен: Так размер будет идти до двух.
>> DAVID МАЛАН: OK.
Ты ластик -
Ой.
Ты ластик.
>> Стивен: Eraser.
>> DAVID МАЛАН: Ты кисти.
>> Стивен: Brush.
>> DAVID МАЛАН: OK.
А что еще?
>> Стивен: И тогда мы -
>> DAVID МАЛАН: Мы выдвинули 17.
>> Стивен: Мы придерживаемся 17 сверху, а значит -
>> DAVID МАЛАН: Хорошо, хорошо.
>> Стивен: - поместите его вниз.
>> DAVID МАЛАН: Хорошо.
Это становится легко.
Я не собираюсь, чтобы помочь вам в этот раз.
Нажмите 22.
>> Стивен: Готово.
Стать ластик.
Я становлюсь кисти.
И тогда я ставлю 22.
>> DAVID МАЛАН: 22.
Отлично.
Так что еще раз.
Я теперь собираюсь нажать стек 26.
>> Стивен: Ох.
О, черт возьми.
Вы действительно застало меня врасплох.
>> DAVID МАЛАН: Вы не сделали это предвидеть?
>> Стивен: Я не видел этого ждать.
Можем ли мы повторно Первоначальная мощность?
>> DAVID МАЛАН: Это хороший вопрос.
Итак, у нас вид окрашены себя в углу здесь.
Там действительно ничего хорошего за Стивен потому что у нас выделено в этом массиве
статически, так сказать, внутри структуры данных.
И мы по существу жестко это будет размером три.
Так что мы не можем освободить его.
>> Мы могли бы, если бы мы вернулись, мы пересмотрел лотки быть указатель, который
затем мы используем Malloc в руки памяти.
Потому что, если мы получили от памяти через кучу Malloc, мы
могли бы освободить его.
Но перед освобождением, мы могли бы перераспределить больший кусок памяти,
обновить указатель, и так далее.
Но на сегодняшний день, это действительно что мы можем сделать.
Нажмите и поп, предположительно, собирался иметь, чтобы сигнализировать некоторые ошибки.
>> Так, например, наша реализация толчок может вернуться BOOL которые
возвращенный ранее правда, правда, правда.
Но в четвертый раз, он будет иметь вернуться ложным, например.
Хорошо.
Очень хорошо сделано.
Поздравляю.
Вы заработали свой стресс мяч сегодня.
>> [Аплодисменты]
>> Стивен: Спасибо.
>> DAVID МАЛАН: Спасибо.
Итак, это, кажется, не так много из шаг вперед, не так ли?
Мы описали эту структуру данных.
Это было убедительным, не так ли?
Операционные системы нравится.
Видимо в Интернете может воспользоваться этим, и других приложений на месте.
Но то, что глупые ограничения, что мы вернуться к рода неделе два предела
где мы зафиксировали размер массивов.
>> Таким образом, есть действительно пара способы, которыми мы могли бы решить эту.
Мы могли динамически выделять массив, не жесткое кодирование это, как я
сделано здесь, но вместо повторного объявления это, просто чтобы было ясно, как
что-то вроде этого.
Лотки Int *, не решаясь на работоспособность еще.
Но когда я заявляю стека в другом месте в моем коде, я мог бы назвать Malloc,
получить адрес кусок памяти, и я мог назначить
этот адрес лотков.
>> И потом, потому что это просто кусок памяти, я мог бы продолжать использовать квадратные
скобок в обычном порядке.
Потому что опять же, вроде этого функциональный эквивалент массивы и
участки памяти, которые приходят назад от Malloc.
Мы можем относиться друг, как и другие использованием арифметики указателей или
квадратных обозначения кронштейна.
Так что это один подход.
>> Но как еще мы можем реализовать эту ту же структуру данных, потенциально?
Верно?
Я чувствую, что мы просто решили эту проблемы, как неделю назад.
То, что было решение этой проблемы что Стивен столкнулся?
Так связанные списки, правы.
>> Если проблема в том, что мы красим себя в угол, выделив
Заранее слишком мало памяти, что мы тогда придется как-то иметь дело с, ну,
Почему бы просто не избежать вопрос вообще?
Почему бы просто не объявить лотки быть указатель на узел, ERGO связанный список,
и потом выделить новые узлы каждый раз, когда Стивен необходимы, чтобы соответствовать
число в структуру данных.
>> Таким образом, картина должна измениться.
Это не будет так чисто и, как просто, как только массив из трех целых чисел.
Теперь это будет указатель на структуры, и что структура собирается
есть Целочисленное и следующий указатель.
Это будет вести через этот указатель в другую такую ​​структуру, чтобы
другой такой структуры.
Таким образом, картина была бы на самом деле получить немного грязнее.
И мы бы стрелки связывая все вместе.
>> Но это нормально, правильно, потому что мы видели, как это сделать.
И как только вы освоитесь создаете что-то вроде связанного
список, который вы должны будете сделать, если Вы выбрать для реализации хэш-таблицу с
раздельное связывание для р-набор 6, вы можете использовать его в качестве строительного блока, либо
ингредиента или в царапинам говорят, процедуры, то, что вы положили, вы
создали свой собственный кусочек паззла , который затем можно использовать повторно.
Так компромиссы, но потенциальные решения что мы на самом деле видел раньше.
>> Так довольно часто, вы видите это каждый год или два, когда Apple выпустила
что-то новое, и все сумасшедшие люди линия за пределами Apple,
магазин, чтобы купить их предельные обновить на оборудовании.
Я говорю об этом, это нормально, потому что Я один из тех людей.
Так какие структуры данных может представлять эту реальность?
>> Ну, давайте назовем это очереди, линия.
Так англичане называют это обычно Очередь в любом случае, так что это хорошее имя.
И две операции, которые очередь должна поддерживать мы будем называть Enqueue
операции и операции из очереди, которые похожи по
духа нажать и поп-музыки.
Это просто как бы в различных Конвенции, то, что мы называем этим.
Но для постановки в очередь что-то означает, добавить или вставить его в структуре данных.
Чтобы из очереди означает, чтобы удалить его.
Но в то время был стек данных LIFO структуре очереди в первой,
первый из структуры данных.
>> Если вы первый человек в очереди, Вы будете первым человеком, чтобы получить
из линии и купить новое устройство.
Представьте себе, как расстройство эти люди были бы Если Apple, вместо этого использовали стек, для
Например, для осуществления выбора до вашей новой игрушкой.
Так очередей смысла, конечно, и мы можем думать о всяких
приложений, по-видимому, для очередей, особенно если вы хотите справедливости.
Итак, как мы могли бы реализовать эти в качестве структуры данных?
>> Ну, я предлагаю, чтобы мы могли нужно сделать это таким образом.
Так что я собираюсь сейчас имеют номера.
Таким образом, мы будем держать его простым и не обязательно говорить с точки зрения лотков.
Просто числа, которые народ получил.
Емкость собирается, опять же, исправить общее число людей, которые могут быть в
этой линии, а три или любые другие значения.
>> Но я предлагаю, что мне нужно, чтобы отслеживать не только размер
Очередь, как многие вещи в нем.
Поэтому размер текущего размера, мощности это максимальный размер.
Просто еще раз, номенклатура В соответствии с соглашением.
Зачем мне нужен дополнительный десятичного внутри очереди, чтобы отслеживать, кто находится в
передней линии?
Почему я должен это делать в этом случае?
>> Ну, как эта картина собираюсь менять?
Я, вероятно, может повторно наиболее этой картины.
Позвольте мне идти вперед и стереть то, что здесь.
Мы дадим этим немного другое имя здесь.
Давайте избавиться от 17, давайте избавимся из 9, давайте избавляться от 3.
И давайте добавим еще одну вещь.
Я полагаю, что мне нужно следить за передней части списка, который является только
будет ИНТАС хорошо.
И мы собираемся сделать его простым.
Нет связанного списка на данный момент.
>> Мы признаем, что мы собираемся натыкаются на это ограничение.
Но то, что я хочу видеть на сей раз?
Итак, пусть я иду вперед и первым Человек приходит в линию, а
это число 9.
У нас есть стресс шаров.
Могу ли я украсть, скажем, два или три человека?
Один, два, три?
Поднимайся.
Прямо с фронта, потому что мы будем делать это одним быстрым.
>> Каждый из вас теперь будет Вентилятор мальчика в очереди в Apple.
Вы не будете получать Apple Hardware В конце этого же.
Хорошо.
Значит, ты номер 9, вы № 17, № 22.
Эти произвольные числа, например, Студент идентификаторы и еще много чего.
И через минуту, давайте начнем , чтобы начать добавлять вещей.
И я побегу борту здесь на этот раз.
>> Так что в этом случае я инициализировать передней быть -
Я на самом деле не все равно, что фронт, так как размер равен нулю.
Так что это может также просто быть знаком вопроса.
Все эти знаки вопроса.
Так что теперь мы начнем реально увидеть некоторые люди выстраиваются в очередь в магазине.
>> Таким образом, если число 9, ты первая там в 5 утра, идти вперед и выстраиваются в очередь,
или накануне вечером.
ОК.
Так что теперь здесь 9.
Так 9 находится в начале списка.
Так что я собираюсь идти вперед и обновления Размер этого текущие данные
структуры, чтобы не быть больше 0, но равным 1.
Я собираюсь поставить на 9 перед списком.
Позвольте мне идти вперед и переключения экрана так что мы можем видеть прошлое с нами здесь.
>> А теперь что я хочу поставить на фронт?
Я буду отслеживать, что начале очереди сейчас
находится в местоположении 0.
Потому что дальше будет?
Ну, предположим, что теперь я поставить в очередь 17, а.
Так что прыгать в линию там.
И опять же, вроде дверь Магазин будет здесь.
Так что теперь я добавил 17.
И хотя эти парни блокируют экрана, это нормально,
потому что мы видим это здесь.
Извините.
>> АУДИТОРИЯ: Мы можем двигаться -
>> DAVID МАЛАН: Нет, это нормально.
Это огромный там.
Так 17 теперь внутри очереди.
Мне нужно обновление, которое полей сейчас, хотя?
Хорошо, определенно размера.
А как насчет фронта?
ОК, нет.
Передняя не должна измениться, так как В отличие от стека, мы
хотят сохранить справедливость.
Так что если 9 вышел на первое, мы хотим, 9 быть первой из линии
и в магазин.
>> В самом деле, давайте посмотрим, что.
Перед тем, как вставить 22, давайте идти вперед и Dequeue 9.
Как тебя зовут?
>> АУДИТОРИЯ: Джейк.
>> DAVID МАЛАН: Джейк собирается быть удалена из очереди сейчас.
Таким образом, вы добираетесь, чтобы идти в магазин.
И делать вид, что в магазине вон там.
Так что теперь нужно, - ДИТ-ДИТ-дит!
Что должно произойти сейчас?
Дизайн решения.
Так не плохой инстинкт, но - как тебя зовут?
>> АУДИТОРИЯ: Дэвид.
>> DAVID МАЛАН: Дэвид.
Итак, что сделал Давид?
Он пытался исправить сортировать данные Структура и перейти от его расположения
в прежнем месте Джейка.
И это прекрасно, если мы готовы признать, что, как
деталь реализации.
Но сначала, давайте обновим данные структуры, прежде чем делать это.
Потому что я не нравится идея всех люди сдвиг в этой линии.
>> Это не страшно, если Дэвид делает это с один шаг, но опять же, вспомните
, когда у нас было восемь добровольцев по этапе, и мы сделали, как вставки
Сортировка, где мы должны были начать перемещение всех вокруг.
То есть дороги, не так ли?
Это заставляет меня съежиться о Big O п, Big O п квадрат снова.
Это не чувство, как идеальный результат.
>> Так что давайте просто обновлять это.
Таким образом, размер очереди больше не является 2.
Это теперь просто 1.
Но теперь я могу что-то обновить Я не обновлялась раньше,
перед списком.
Я мог бы просто сказать, что расположение 1?
Так что теперь у нас есть мусор ценность здесь, мусора значение здесь, и Дэвид в
середине этого мусора.
Однако структура данных по-прежнему нетронутыми.
>> И в самом деле, я даже не нужно изменить прежний номер Джейка
9, потому что, кто заботится.
У меня есть достаточно информации, в настоящее время в размера, что я знаю, что есть один человек в
этой очереди.
И я знаю, что этот человек находится в местоположении 1, а не 0.
Я не рассчитываю.
Таким образом, 1, а также.
Так что данные структуры все еще хорошо.
>> Ну, а что будет дальше?
Давайте Enqueue -
Как тебя зовут?
>> АУДИТОРИЯ: Каллен.
>> DAVID МАЛАН: Каллен.
Давайте постановки в очередь Каллен, и 22 в настоящее время в очереди.
Так что теперь должен изменить здесь?
Передняя не собирается изменить, это очевидно.
Размер будет меняться, чтобы быть 2 снова.
И 22 заканчивается здесь, 9 по-прежнему присутствует, но это эффективно
мусора значение сейчас.
Это просто пережиток прошлого Джейком.
>> Так что теперь, что произойдет, если Я из очереди Дэвид?
Одна последняя операция, Dequeue Давида.
Мы могли бы перейти, но я предлагаю давайте сделать так мало работы, сколько возможно.
Теперь моя структура данных идет Резервное в размере от 2 до 1.
Но впереди очереди теперь становится 2.
Мне не нужно, чтобы изменить это число Пока еще нет, потому что они
просто значения мусор.
>> Но теперь то, что происходит?
Предположим, что я себя поставить в очередь, 26?
Я чувствую, что я принадлежу здесь.
Так что я быть установлены в очередь.
Так что я как бы к нам присоединиться.
И даже если вы не совсем визуально оценить это на сцене,
потому что у нас много места, я должен Не стоять здесь, то почему?
>> Зала: Вы находитесь за пределами поля.
>> DAVID МАЛАН: Верно.
Я вне закона.
Я проиндексированы за рамках данного массива.
Я действительно должен быть в одном из три возможных местах.
Итак, где наиболее естественным пойти?
Я предлагаю заемных средств неделе один трюк.
Оператор Mod, в процентах.
Потому что я стоял на технически Расположение 3, но у меня 3 мод мощности,
SO 3, знак процента, 3 -
емкость 3.
Что это?
Какой остаток при Вы делите 3 на 3?
0.
>> Так что это ставит меня были Джейк был, который на самом деле хорошо.
Так что в настоящее время осуществление этой вещи собирается
быть немного головной боли.
Это действительно просто одна строка головной боли, кода.
Но по крайней мере теперь есть мусор Значение здесь, но есть два
законных целыми здесь.
И я утверждаю, что сейчас мы сделали именно то, что нам нужно сделать, так долго, как
изменить то, что мы Джейка Значение должно было быть 26.
>> Теперь у нас есть достаточно информации по-прежнему для поддержания целостности
этой структуры данных.
Мы все еще отчасти не повезло, когда мы вставить четыре или более общей
элементы, но я могу по крайней мере сделать довольно эффективное использование этой константы
время, на самом деле.
Я не придется беспокоиться о переносе Каждый человек, как наклон Давида была.
>> Любые вопросы по стеки, или эта очередь?
>> Зала: причина, почему Вам нужен размер, чтобы вы знали
Где есть человек?
>> DAVID МАЛАН: Совершенно верно.
Мне нужно знать размер массива потому что мне нужно точно знать, как
многие из этих значений являются законными, и так, что я могу найти, где поставить
следующий человек.
Именно так.
Размер -
На самом деле, мы не обновляли это пока.
Я добавил себя в 26.
Размер в настоящее время, а не один, а два.
Так что теперь это действительно помогает мне найти главе списка, который не равен 0, не
1, но 2.
Перед списком на самом деле число 22.
Потому что он пришел первым, поэтому он должен пустят в магазине передо мной,
хотя визуально я стою ближе к магазину.
>> Все в порядке?
Аплодисментов для этих парней , и мы сообщим их оттуда.
>> [Аплодисменты]
>> DAVID МАЛАН: Я мог позволить Вы держите лоток.
Мы могли видеть, что происходит, если Вы хотите, но может и нет.
Хорошо.
И что теперь что нам остается?
Ну, позвольте мне предложить, что есть Несколько другие структуры данных, мы могли
начать добавлять к нашему набор инструментов, который будет действительно может быть очень, весьма актуальна, как
мы погрузимся в материал Интернета.
Что опять же, есть какая-то связь к деревьям в виде
то, что называется DOM, документ объектной модели.
Но мы увидим больше что в скором времени.
>> Позвольте мне предложить, что мы definitionally дерево вызовов теперь то, что вы знаете, как
больше семейного дерева, где вы есть предком
Корни дерева.
Патриархальной или матриархат в самой вершине дерева.
Без их супругов, в этом случае.
Но теперь мы имеем то, что мы будем называть детей, которые являются узлами, которые висят
за левым ребенком или право ребенка, стрелки, как показано здесь.
>> Другими словами, в структуре данных дерева в компьютер, дерево имеет нулевую
или более узлов.
Если у него есть хотя бы один узел, Это называется корнем.
Это вещи, что визуально мы обращаем на самом верху.
И этот узел, как и любой другой узел, может иметь ноль, один или два, или три,
или сколько детей Структура данных поддерживает.
В этом случае, корень, хранение Значение одного, имеет двоих детей, 2 и 3,
поэтому мы обычно называем 2 левых ребенка и 3 правом ребенка.
>> А потом, когда мы приступим к 5, 6, и 7, 6 можно назвать средним ребенком.
Если у вас есть четверо детей, это сбивает с толку.
Таким образом, мы прекратить использование такого сочетаний в устной форме.
Но это действительно только генеалогическое дерево.
И листья здесь узлы, которые сами по себе не имеют детей.
Они висят от нижней части дерева.
>> Так как мы можем реализовать дерево, имеет только две детям максимально?
Мы назовем это бинарное дерево.
Би снова означает два, в этом случае, как и с бинарными.
И поэтому он может иметь ноль, один, или двух детей максимально.
>> Я предлагаю, чтобы мы осуществили узла для этой структуры с Int N,
а затем два указателя, одна называется оставили, одна называется правом.
Но это просто приятно произвольные соглашения.
И то, что приятно сейчас, особенно, если вы вид боролся концептуально
рекурсии, или думал, что это не было Решение действительно ни к чему,
Особенно если бы вы могли запустить из памяти.
Теперь, когда мы говорим о данных структуры и алгоритмы, которые позволяют
нам, чтобы пройти их и манипулировать ими, Оказывается, что рекурсия возвращается в
гораздо более убедительной если не красивым способом.
>> Так что я предлагаю, является реализация из функции поиска.
Учитывая два входа -
поэтому думайте об этом как черный ящик.
Учитывая два входа, N, целое и указатель на дереве, указатель на
узла, или действительно корень дерева, я утверждают, что эта функция может возвращать
истинным или ложным, что значение N внутри этого дерева.
>> Что внутри этого черного ящика?
Ну, четыре ветви.
Сначала просто проверяет.
Если дерево является пустым, просто вернуть ложное.
Если нет узла, нет N, нет числа, как раз возвращает ложное.
Если хоть, N, значение, которое вы ищете для, меньше дерева стрелку N, и
просто чтобы было ясно, что это значит, когда Я пишу дерева, а затем стрелка
обозначение, п?
Именно так.
Это означает, что разыменования Указатель называется деревом.
Отправляйтесь туда, а затем попасть внутрь, что узла и получить его поле, названное N.
А потом сравнить фактические N, которая была перешла в поиск против него.
>> Таким образом, если N меньше, значение N в узле дерева сам, ну,
Что это значит?
Это ничего не значит на первый взгляд.
Верно?
Как и когда вы есть массив Значения, которые Вы хотели бы применить двоичный
искать как форма разрыва и властвуй.
Но то, что сделал предположение мы должны сделать для бинарного поиска работает вообще
в телефонной книге и более ранние примеры?
>> Как быть отсортированы.
Так что давайте уточнить определение дерева Здесь, чтобы не быть просто дерево, которое может
иметь любое количество детей.
Не только бинарное дерево, которое может иметь 0, 1 или 2 максимально.
Но, как бинарное дерево поиска или BST, , которая является просто причудливый способ сказать
бинарное дерево так, что каждый узла левый ребенка, если он присутствует,
менее узла.
И право каждого узла ребенком, если они присутствуют, больше
кроме самого узла.
>> Итак, другими словами, если вы должны были сделать дерева из все цифры
тщательно сбалансированы, как это так, что если у вас есть 55 в качестве корневого, 33 может пойти
слева от него, потому что это меньше, чем 55.
77 может пойти в своем праве, потому что это больше, чем 55.
Но теперь заметили, то же определение, это рекурсивное определение в устной форме,
должен направить заявку на 33.
33 в левой ребенок должен быть меньше его, права ребенка и в 33, 44, должны быть
больше, чем он.
>> Так что это бинарное дерево поиска, а Я предлагаю, используя немного
рекурсию, сейчас мы можем найти N.
Таким образом, если N меньше, чем значение N это текущего узла, я пойду
вперед и выбивать из рук, так сказать, и просто возвращая то, что ответ на этот вопрос из
поиск п от левого дерева ребенка.
Еще раз обратите внимание, эта функция просто ожидает узла звезды,
указатель на узел.
Так что, конечно, я просто могу сделать дерево стрелка влево, что приводит
мне на другой узел.
Но что это за узел?
>> Ну, в соответствии с этой декларацией, Слева только указатель, так что только
означает, что я переходя к функции поиска различных указателей, а именно
один, который представляет моя левая ребенка дерева.
Таким образом, в этом случае указатель 33, если это наш пример ввода Между тем, если
п больше значение п при текущего узла в дереве, то я
собираюсь идти вперед и выбивать из рук в другие Направление и просто сказать, я не
знаю, если это значение п в дереве, но я знаю, если это так, это по моему
Правая ветвь, так сказать.
Итак, позвольте мне рекурсивно искать, проходящий N раз, но переходящая в
указатель на моем правом ребенка.
>> Другими словами, если я в настоящее время нахожусь на 55 и я ищу 99, я знаю, что 99
больше 55, так же, как я разорвал недель телефонную книгу назад, и мы
пошел прямо, как и мы собираюсь идти прямо здесь.
И я не знаю, будет ли это на мое право ребенка, а это не так, 77 есть, но
Я знаю, что в этом направлении.
Поэтому я называю поиска справа от меня ребенка, 77, и пусть поиск фигуры из
там, если 99 в этом произвольном Примером является на самом деле.
>> В противном случае, то, что последний случай?
Если дерево является недействительным один случай.
Если п меньше текущего узла значение еще один случай.
Если п больше, чем текущий Значение узла третий случай.
Что четвертом и последнем случае?
Я думаю, что мы из случаев, не так ли?
Должно быть, п ​​в текущего узла, что я на.
>> Так что, если Я ищу 55 на данный момент в этой истории, что филиал
Дерево будет возвращена истина.
Так что здесь интересно то, что мы на самом деле, в отличие от прошлых недель, мы как-то
из двух случаев есть основания.
И они не должны все будет на самом верху.
Верхняя часть базового варианта, потому что если Дерево является недействительным, нет ничего общего.
Просто вернуть жестко заданы Значение ложным.
>> Нижняя ветвь рода по умолчанию, согласно которому, если мы проверили для
нулевым, мы проверили, если она должна быть осталось, но оно не должно быть, у нас
проверяется, если это должно быть правильно, но это не должно быть, очевидно, что оно должно быть
там, где мы есть.
Это базовый вариант.
Таким образом, есть два рекурсивных случаев зажата там в середине.
Но я мог бы написать это в любом порядке.
Я просто думал, что это как бы чувствовал, природные сначала проверить на возможную ошибку,
затем проверить налево, затем проверить прямо, то Предположим, что вы находитесь в узле
на самом деле вы ищете.
>> Так почему это могло бы быть полезным?
Вот и получается -
и позвольте мне перейти к тизер здесь, это в Сети.
Мы собираемся, чтобы начать использовать не язык программирования на первый, но
язык разметки.
Язык разметки является одним это близки по духу к программированию
языка, но это не дает вам Возможность выразить себя логично.
Это только дает вам возможность выразить себя структурно.
>> Где Вы хотите, чтобы положить что-то на странице, веб-страница?
Какой цвет вы хотите это сделать?
Какой размер шрифта вы хотите это сделать?
Какие слова вы на самом деле хотите на веб-страницу?
Так что это язык разметки.
Но тогда мы очень быстро ввести JavaScript, который является полноценным
языка программирования.
Очень похож по внешнему виду синтаксически С, но это будет иметь некоторые
хорошо, более мощная, более удобных для пользователя характеристик.
>> И одним из разочарований в это точка в семестр, что мы будем
скоро в реализации спеллер гораздо меньше строк кода с использованием других языках
C чем сама позволяет, но для разума мы скоро поняли.
Это будет первый такой веб-страницы.
Он будет полностью в восторг, Первое мы делаем.
Он просто скажет: привет мир.
Но если вы никогда не видели его раньше, это HTML,
Язык разметки гипертекста.
>> Если вы идете в определенный пункт меню в Наиболее любом браузере, на любой веб-странице
Интернет, вы можете увидеть HTML что некоторые люди написали
создать эту веб-страницу.
И это, вероятно, выглядит не так краткая или же аккуратно, как этот.
Но это будет по той же схеме этих открытые скобки и косая черта и
Письма и потенциально чисел.
>> Я думал, что дам вам тизер того, что вы будете в состоянии сделать
после приема CS50.
Пустите меня к cs.harvard.edu / грабить, Домашняя страница нашей собственной Роб Боудена.
Он сделал это для нас.
Таким образом, вы скоро будете в состоянии сделать это.
А также, что вы слышали Сегодня утром -
то, что вы слышали сегодня утром -
>> [HAMSTER Танцевальная музыка]
>> - Вы будете иметь возможность сделать это.
Что ждет нас в среду.
Мы будем видеть вас тогда.
>> [HAMSTER Танцевальная музыка]
DAVID МАЛАН: На следующей CS50 -