>> Дэвид Дж. Малан: Хорошо.
Так что добро пожаловать первой в истории CS50 посмертное для викторины.
Мы думали, что открывать эта традиция в этом году.
И это будет возможность идти через
решения викторины.
И мы будем ускорить или замедлить основе на интересах тех, кто здесь.
>> Таким образом, вы, вероятно, здесь, потому что вы заинтересованы в том, как вы могли бы или
должны ответили некоторые из этих проблем.
Так почему бы нам не взглянуть в этом разделе в первую очередь?
Поэтому получение строк.
Это дало вам три различных версии программы, которая была, в конечном счете,
означало, чтобы получить строку от пользователя.
Или нет, это сделал, что было оставляется вам определить.
>> И мы попросили в вопросе 0, Предположим, что версия 1
скомпилирована и выполнена.
Почему может программа сегментации?
На первый взгляд, любые предложения , почему?
Да.
>> АУДИТОРИЯ: Так что я помню, это в Предыдущий пример смотреть на
символ * с и видя сканирование с и видя, потому что это указатель, как
это повлияло на то, что вы сканируется в?
Является это с или адрес с?
>> Дэвид Дж. Малан: ОК.
Хорошо.
Таким образом, в конечном счете, источник любой проблемы Предположительно собирается сократить
к этому переменной с.
И это действительно переменная.
Тип данных этой переменной является символ *, что означает, что это собирается
содержать адрес символа.
И в этом заключается понимание.
Это собирается содержать адрес символ или, более общо,
адрес первого символа в целый блок символов.
>> Но загвоздка в том, что сканирование с, цель в жизнь, дается адрес и с учетом
код формата, как% с, чтения строка в кусок
памяти по этому адресу.
Но поскольку нет знака равенства перед что точка с запятой на первый
строка кода, потому что мы на самом деле не выделяет памяти с
таНос, потому что это на самом деле не выделить массив какой-то размера, все
вы делаете читает пользователя ввод с клавиатуры в некоторых полной
значение мусора, которые находится в с по умолчанию.
Так шансы вы собираетесь к выпадению, если что адрес не просто так случиться
быть значение, которое вы можете, на самом деле, напишите.
Так плохо не выделить ваша память есть.
>> Таким образом, в вопросе 1, мы спросили, Предположим, что версия 2
скомпилирована и выполнена.
Почему может эта программа сегментации?
Так что это один меньше ошибок.
И есть действительно только один очевидный способ, где вы можете
вызвать сегментации здесь.
И это тематическая.
Каждый раз, когда мы используем с в памяти, что вы могли бы сделать, чтобы вызвать сегментации
с версии 2?
>> АУДИТОРИЯ: Если вы используете этот вход в строка это больше, чем 49
символов.
>> Дэвид Дж. Малан: Совершенно верно.
Каждый раз, когда вы видите что-то фиксированной длины когда дело доходит до массива, ваш
РЛС должна погаснуть, что это может быть проблематично, если вы не проверяя
Границы массива.
И это проблема.
Мы все еще используем зсапЕ.
Мы все еще используете% S, что означает, попробовать читать строку от пользователя.
Вот которые будут читать в с,, в этой точке, эффективно
адрес кусок памяти или это эквивалентно.
Это имя массива символов памяти.
>> Но именно это, если вы читаете строку это больше, чем 49 символов, 49
потому что вам нужно место для обратной косой черты 0, вы будете переполняться
что буфер.
И ты можешь стать счастливчиком и быть в состоянии написать 51-й характер, 52, 53.
Но в какой-то момент, ОС собирается сказать, нет.
Это определенно не памяти Вам разрешают трогать.
И программа будет к выпадению.
>> Так что, эвристика должно быть никаких Время у вас есть фиксированную длину, у вас есть
чтобы убедиться, что вы проверяете длину из то, что вы пытаетесь
читать в нее.
>> АУДИТОРИЯ: Таким образом, чтобы решить, что, вы могли бы имели о проверки на самом деле
длина больше или меньше?
>> Дэвид Дж. Малан: Совершенно верно.
Вы просто есть условие что говорит, если -
или, скорее, вам не обязательно знать, заранее, сколько символов
пользователь собирается ввести, потому что у вас есть курица и яйцо.
Не, пока вы не читали его с зсапЕ Вы можете выяснить, как долго это.
Но в тот момент, что это слишком поздно, потому что вы уже читали его в
некоторый блок памяти.
Так как в сторону, библиотека CS50 избегает этот вопрос в целом, напомним,
с помощью fgetc.
И он читает один символ за один раз, цыпочках вдоль, зная, что вам
не может переполниться характер, если Вы читаете по одному.
>> Загвоздка в том, с GetString отзыве является что мы должны постоянно изменять размеры
что часть памяти, которая это просто боль.
Это много линий Код этого делать.
Так что другой подход будет на самом деле использовать двоюродный брат, так
сказать, зсапЕ.
Существуют варианты Многие из этих функции, которые на самом деле проверить
длина, сколько символов Вы могли бы читать максимально.
А вы могли бы указать, не читайте более 50 символов.
Так что было бы другой подход, но менее любезным из больших входов.
>> Так вопрос 2 спрашивает, предположим, что версия 3 составляется и выполняется.
Почему же это программа сегментации?
Так что это один на самом деле то же самое ответить, хотя это
выглядит немного более необычным.
Мы используем таНос, который чувствует себя подобно мы даем себе больше возможностей.
А потом мы освобождая, что памяти в конце.
Он по-прежнему всего 50 байт памяти.
Таким образом, мы могли бы все еще пытаюсь читать в 51, 52, 1000 байт.
Это собирается к выпадению для точно так же причина.
>> Но есть и другая причина.
Что еще могло Malloc возвращение к тому же адрес кусок памяти?
Это может вернуть нулевой.
И потому, что мы не проверяя что мы могли бы делать что-то
глупо и по другой причине, которая является, что мы могли бы рассказывать зсапЕ, читать
ввод пользователя с клавиатуры в 0 месте, AKA нуль.
И это тоже, безусловно, вызвать сегментации.
Таким образом, для целей тест, мы бы приняли один из тех, как
веская причина.
Одним из них является идентичным.
Одним из них является немного больше нюансов.
>> Наконец, в отношении програмы использование памяти, как же версии 2 и
версия 3 отличаются?
Таким образом, для чего это стоит, мы видели казалось бы, бесконечное количество можно
Ответы на этот.
И среди ответов людей, то, что мы были надеясь на, но мы приняли другое
вещи, было некоторое упоминание о Дело в том, что версия 2 использует
так называемый стек.
Версия 3 использует кучу.
И функционально, это на самом деле не сделать все, что особой разницы.
В конце концов, мы все еще просто получить 50 байт памяти.
>> Но это был один из возможных ответов что мы смотрели.
Но вы увидите, как вы получите ваш викторины назад от ТФ, что мы сделали
принять другие обсуждения их разрозненные использования памяти, а также.
Но стек и куча бы простой ответ, чтобы пойти с.
Есть вопросы?
Я даю вам Роб.
>> ROB BOWDEN: Так проблема 4.
Это то место, где вы должны были заполнить в число байтов из всех
эти различные типы, используемые.
Так первое, что мы видим.
Предположим, 32-разрядную архитектуру, как этот CS50 прибора.
Таким образом, одна из основных вещей, о 32-битные архитектуры, который говорит нам,
точно, как большой указатель собирается находиться в архитектуре.
>> Так сразу, мы знаем, что любой указатель тип 32 бита или 4 байта.
Так, глядя на эту таблицу, узел * является указателем.
Это будет 4 байта.
Структура, узел *, вот буквально идентичен узла звезды.
И так, что это будет 4 байта.
Строка, так что не похож указатель пока нет, но ЬурейеЕ,
строка просто символ *, который является тип указателя.
Так что это будет 4 байта.
>> Таким образом, эти три все 4 байта.
Теперь, узел и ученик являются немного сложнее.
Так, глядя на узле и ученика, мы видим, узел в виде целого числа и указатель.
И студент два указателя внутри него.
Так по крайней мере в нашем случае здесь, то, как что мы в конечном итоге расчета размера
эта структура просто сложить все что находится внутри структуры.
>> Таким образом, для узла, у нас есть целое, который имеет размер 4 байта.
У нас есть указатель, который является 4 байта.
И так один узел собирается занять 8 байт.
И точно так же для студентов, у нас есть Указатель вот 4 байта, а другой
Указатель вот 4 байта.
Так что будет в конечном тем, что 8 байт.
Так узел и ученик 8 байт.
И эти три все 4 байта.
Вопросы по этому поводу?
Да.
>> Зала: это был 64-разрядный архитектура, хотел бы, чтобы
удвоить все из них?
>> ROB BOWDEN: Это не так удвоить все из них.
Так 64-разрядная архитектура, это, опять же, изменения, которые фундаментальная вещь, которая
Указатель Сейчас 64 бита.
Да.
Так указатель составляет 8 байт.
Таким образом, эти, что были 4 байта будут 8 байт.
Студент, который был два указателя, хорошо, теперь он собирается
быть 8 байт, 8 байт.
Это собирается сделать 16 байт.
>> Но узел еще 4 байта.
Так этот указатель будет чтобы быть 8 байтов.
Это 4 байта.
Так узел будет только быть 12 байт.
Любые другие вопросы о том, что один?
Таким образом, следующий, это коды состояния HTTP.
И у вас было бы описать обстоятельства , при которых они могли бы
Вам возвращены.
одна проблема, что я слышал, некоторые студенты есть то, что они попытались сделать
Ошибки быть на конце клиента.
Поэтому, когда мы пытаемся сделать запрос на сервер, что-то идет
неправильно с нашей стороны.
Но в целом, эти коды возвращается на сервере.
Поэтому мы хотим, чтобы выяснить, что происходит неправильно или прямо на сервере,
вызывает эти вещи должны быть возвращены.
Так почему могли бы через сервер возвращает Код состояния 200?
Любые мысли?
>> Да.
Так что-то успешно запрос прошел.
И они смогли вернуться все, что вы просили.
Так что все было прекрасно.
Что о 302 найдено?
Да.
>> АУДИТОРИЯ: Сервер искал за то, что вы просили.
Но это не мог найти его.
Таким образом, есть ошибка.
>> ROB BOWDEN: Так сервер был ищет то, что вы хотели.
Так что просто глядя здесь, 302 найдено, он был в состоянии найти его.
>> АУДИТОРИЯ: Мне очень жаль.
Найдено означает, что они нашли его.
Извините.
>> ROB BOWDEN: Так 302 найдено.
Сервер способен найти что вы хотели.
>> АУДИТОРИЯ: Но это не отображая его?
>> ROB BOWDEN: Разница между это 302 и 200 является то, что он
знает, что вы хотите.
Но это не точно, где вы хотели спросить.
Так 302 является типичным редирект.
Таким образом, вы запросили страницу.
Она знает, о, я хочу вернуться тебе это.
Но это в другом URL.
Так эй, вы на самом деле хотите этого.
>> Дэвид Дж. Малан: Это кусок, что сказал что мы дали вы, ребята редирект
функция, которая использовалась функция заголовка что, в свою очередь, распечатать местоположение,
толстой кишки, а затем URL, к которому Вы хотите, чтобы отклонить пользователя.
Даже если вы не видели 302 явно есть, это то, что РНР
волшебным вставить в качестве заголовка говоря, что именно сказал Роб там -
найдено.
Но идут сюда вместо этого.
>> ROB BOWDEN: ОК.
Так что о 403 запрещено?
>> Зала: Я думаю, что это то, что сервер в основном говорит, что клиент
не может получить доступ к домашней странице.
>> ROB BOWDEN: Так что, да.
Ну, типичный ответ мы были ожидая что-то подобное, файлы
не chmodded соответствующим образом.
Это, вероятно, при каких обстоятельствах вы видели их.
Но есть причина, что клиент может быть виноваты в этом.
Там на самом деле другой код состояния -
401.
Так что это очень похоже.
>> 401 является несанкционированным.
И 403 запрещено.
И так несанкционированного вы исключительно получить, если вы не прошли идентификацию
Но регистрация может означать что вы имеете право.
Но если вы уже зарегистрированы, и вы до сих пор не имеет разрешения, то
вы также можете получить запрещено.
Так что, если вы вошли в систему и не имеют разрешение, запрещено также
то, что вы можете получить.
>> Дэвид Дж. Малан: И механизм, с помощью которой эти проблемы, как правило
решается на сервере через то, что команда?
CHMOD, если это, действительно, прав выдавать на файл или каталог.
>> ROB BOWDEN: Тогда 404 не найден.
Да.
Так в отличие от 302, где это не было точно где вы спрашиваете, но он знает, что
вы хотите, это, он просто должен никакая идея, что вы хотите.
И вы не с просьбой что-то действует.
418 Я чайник, а затем 500 внутренний сервер.
Так почему может ты это взял?
>> Так сегментации -
Я на самом деле не знаю, градуировку стандарт для этого.
Но если ваш код PHP было что-то в этом плохого, в теории, это могло
фактически сегментации, в каком случае это 500 Внутренняя ошибка сервера, то,
не так с вашего сервера Конфигурация.
Или есть ошибка синтаксиса в коде PHP.
Или что-то плохое происходит.
>> Дэвид Дж. Малан: Мы действительно видели сегментации среди ответов в нескольких людей.
И технически, это может произойти.
Но это было бы PHP, программа написаны другими людьми, на самом деле
segfaulted, которые только если эти люди облажался и написал ошибка в программном коде в
их переводчик были бы Сам PHP сегментации.
Поэтому, даже если 500 подобен сегментации в духе, это почти всегда
результатом вопросу конфигурационного файла с вашего веб-сервера, или, как сказал Роб,
ошибка синтаксиса, как и вы не закрывал цитату.
Или вы потеряли точку с запятой где-то.
>> АУДИТОРИЯ: Таким образом, для Shuttle PSet, я думаю, когда я сделал это, как только я нажал
браузер, но ничего подошел, то, что они называют белым страницы.
Но это было, потому что часть кода.
Я думаю, что было JavaScript, верно?
>> ROB BOWDEN: Да.
>> АУДИТОРИЯ: о, если бы ошибка еще придумать?
>> ROB BOWDEN: Таким образом, вы бы не получили эта ошибка, потому что все
с точки зрения веб-сервера было абсолютно прекрасно.
Но вы просили index.html.
Вы просили shuttle.js и service.js.
И это было в состоянии успешно вернуться Вам всем из тех вещей -
200.
ОК.
И только когда ваш браузер пытался интерпретировать код JavaScript, что
Это как, подождите, это не действует ошибка JavaScript.
Любые другие вопросы?
Хорошо.
>> Дэвид Дж. Малан: Так что в следующий составил число 11.
И 11 было самым страшным для многих людей.
Таким образом, самое главное, чтобы отметить здесь было то, что это было, действительно, о
двусвязный список.
Но это не было так же, как в прошлом году двусвязного проблема список,
которые не дают вам оговоркой, что список можно, в самом деле, быть отсортированы.
>> Поэтому тот факт, что список был несортированный и тот факт, что это слово было
подчеркнутый там должен был передать что это на самом деле упрощение
о том, что в противном случае было бы более сложной проблемой
и более длинный.
Так распространенная ошибка здесь в том, чтобы поставили решение в прошлом году на одном
пейджер, а затем просто слепо копировать, что вниз в ответ, что право
ответить на другой вопрос близки по духу.
Но тонкости здесь были следующие.
>> Так что, мы узел объявлены и определяется обычным образом здесь.
После этого мы определили список быть глобальным указатель инициализируется на нуль.
Тогда, по-видимому, есть две функции у нас есть прототипы здесь, вставка
и удалить.
А то у нас некоторые примеры кода здесь делать кучу вставок.
И тогда мы просим Вас заполнить реализация вставки ниже в таких
образом, что он вставляет п в список за постоянное время, также подчеркнул,
даже если уже присутствует.
>> Так красота возможность вставить в постоянном времени является то, что он предполагает
что у вас есть, чтобы вставить новый узел, где?
В передней.
Так он устраняет, к счастью, по крайней мере, один из случаев, которые раньше требуют
еще больше строк кода, как это было в прошлом году и даже в классе, когда мы
говорили через такого рода вещи с людьми и с некоторыми
словесное псевдо-код.
Таким образом, в решении здесь, давайте пропустить к тому, что просто иметь визуальный контакт
экран.
>> Обратите внимание, что мы делаем следующее.
А также обратите внимание на другую упрощение было то, что даже если это
уже присутствует, это означает, даже если количество уже есть, вы можете
просто слепо вставить другой его копия.
И это тоже должно было быть упрощение, так что вы могли бы
сосредоточиться на, действительно, некоторые из более интеллектуально интересная часть и
не только некоторые дополнительные проверки ошибок учитывая ограниченное время.
>> Так что в этом примере решения, мы выделяем указатель на левой
сторону здесь к узлу.
Теперь понимаю, что указатель, как Роб сказал, только 32 бит.
И это на самом деле не содержат адрес до вас
присвоить ему адрес.
И мы делаем это на правой сторона через таНос.
Как добропорядочный гражданин, мы проверяем, что таНос не является, по сути, нулевой, так что
мы не случайно создать сегментации здесь.
И каждый раз при использовании таНос в жизни, вам должны быть проверки нуль, чтобы
у вас есть тонкий ошибка.
>> Тогда мы инициализировать эту нуль на присвоения п и предыдущий и следующий.
И в этом случае здесь, я инициализации предыдущая в нуль, потому что это новое
узел будет новый начало моего списка.
Так что это будет ничего перед ним.
И я хочу, чтобы существенно добавить существующий список в новый узел по
сидит рядом равна список себя.
Но я не сделал только пока.
Так что, если сам список уже существует, и было по крайней мере один узел
уже на месте, если это список здесь, и я вставить новый узел здесь, я
нужно убедиться, что мой бывший узел указывает назад, чтобы мой новый узел,
потому что это, опять же, двусвязный список.
>> Так мы делаем есть простой тест.
Если список не пуст, если есть уже один или более узлов там, тогда
добавить, что еще ссылку, так сказать.
И тогда очень Последнее, что нам нужно сделать, это на самом деле обновить глобальный
Список переменных сама указать к тому новому узлу.
Да.
>> АУДИТОРИЯ: В стрелкой указателя [Неразборчиво] равна нуль, значит ли это
дело со списком, потому что список пуст?
>> Дэвид Дж. Малан: Нет.
Это просто я, будучи активно осторожны, в том, что если это мое
первоначальный список с, возможно, некоторые более узлов здесь и я вставить мой
Новый узел сюда, там собирается не что иное сюда.
И я хочу, чтобы захватить эту идею , установив предшествующий
нуль на новом узле.
И надо полагать, если мой код правильный и нет никакого другого способа для вставки
кроме этой функции узлов, предположительно, даже если список уже есть
один или несколько узлов в нем, по-видимому, список, первый узел, будет иметь
предыдущая указатель самой нуль.
>> АУДИТОРИЯ: И просто продолжением.
Причина вы положили указатель следующая равно Список вы делаете указатель
перед список в том, что он, указывая к другому, я думаю, -
Я не -
просто перечисляет?
>> Дэвид Дж. Малан: Совершенно верно.
И поэтому давайте на самом деле рассмотреть два случая здесь действительно, несмотря на то,
Порядок мы будем учитывать их не совершенно так же, как код.
Но на высоком уровне, если это представляет список, и это 32-разрядная
указатель, самый простой сценарий что это нуль по умолчанию.
И предположим, что я хочу, чтобы вставить номер 50 был первым номером.
Так что я собираюсь идти вперед и выделить узел, который будет содержать
три поля -
п, предыдущей и следующей.
>> Я собираюсь поставить номер 50 здесь, потому что это будет н.
Это будет следующий.
И это будет предыдущая.
И так что же мне делать в этом случае?
Ну, я только что сделал линию 1 здесь.
Указатель н получает н.
Я тогда говорил, предыдущая должны получить нулевой.
Так что это будет нулевым.
Тогда я буду говорить дальше собирается получить список.
>> И это просто работает хорошо.
Это нуль.
И поэтому я говорю, нового узла рядом поле должно получить то, что это.
Так что ставит еще один нуль там.
И то последнее, что Я это проверить здесь.
Если список не равно NULL, но это равна нуль, поэтому мы пропускаем, что
в целом.
И так все, что я делать дальше, список становится указатель, который наглядно приводит к
картина так.
Так вот один сценарий.
>> И тот, который вы спрашивали о специально это ситуация, как это,
где у нас уже есть список с одним узлом.
И если я вернусь в оригинале постановка проблемы, на следующий мы будем
вставить скажем на 34, только для ради обсуждения.
Так что я собираюсь просто удобно привлечь, что здесь.
Я только что malloced.
Давайте предположим, я проверяю для нуль.
>> Теперь, я собираюсь инициализации н быть 34.
И это будет н.
Это будет следующий.
И это будет предыдущая.
Давайте убедиться, что я не сделал получить назад.
Предыдущий приходит первым в определении.
Позвольте мне исправить это.
Это предыдущая.
Это рядом.
Даже если они идентичны, давайте держать его последовательным.
>> Предыдущий.
Это рядом.
Так что я просто malloced мою записку, проверил для нуль, назначен 34 в узел.
Предыдущий получает нуль.
Так, что дает мне это.
Следующая получает список.
Так список это.
Так что это то же самое сейчас, как рисование это стрелка, так что они указывают на один
в то же самое.
А потом я проверяю, если список не равен NULL.
И это не в этот раз.
Тогда я собираюсь сделать список предыдущая получает указатель.
>> Так списку предыдущий получает PTR.
Таким образом, это имеет эффект ввода графическое стрелка здесь.
И это становится немного волнистые, линии.
А потом, наконец, обновить список, чтобы указать на указатель.
Так что теперь это указывает на этого парня.
А теперь, давайте сделаем краткий здравомыслие проверка.
>> Вот список, который является глобальная переменная.
Первый узел, действительно, 34, потому что Я слежу, что стрелку.
И это правильно, потому что я хочу вставить в начале списка
все новые узлы.
Его следующее поле приводит меня к этому парню.
Если я продолжаю, я ударил рядом является недействительным.
Так нет больше список.
Если бы я ударил предыдущий, я получаю туда, где я ожидаю.
>> Так что есть еще несколько советов, очевидно, манипулировать.
Но то, что вы сказали сделать это в постоянном времени означает, что вы только
имеют конечное число вещей Вам разрешают сделать.
И что это за число?
Это может быть на один шаг.
Это может быть два.
Это может быть 1000 шагов.
Но это конечная, а значит, вы не можете есть какой-либо петлеобразования происходит
здесь, не рекурсивно, без петель.
Это просто должно быть жестко-закодированных строк кода, как у нас в этом образце.
>> Так что в следующий Проблема 12 попросили нас завершить реализацию Удалить
Ниже таким образом, что она удаляет н из списка в линейное время.
Так у вас есть немного больше маневра сейчас.
Вы можете считать, что п, если он присутствует в списке, будет присутствовать
не более чем один раз.
И это тоже предназначается, чтобы быть викторина на основе упрощающее предположение, так
что, если вы найдете номер 50 где-то в списке, вы не также
придется беспокоиться о продолжая итерации, ищу все возможные
копия 50, что бы просто передавать в некоторых мелочах в ограниченное время.
>> Так что с удалить, этот был определенно более сложной и более
Код писать.
Но на первый взгляд, откровенно говоря, это могло бы искать подавляющее и как что-то
нет никакого способа, вы могли бы придумать на викторине.
Но если мы ориентируемся на отдельных этапов, Надеюсь, он будет внезапно
ударить вас, что каждый из этих индивидуальных шаги делает очевидным смысл
в ретроспективе.
Так что давайте взглянем.
>> Итак, сначала мы инициализируем указатель быть список себя.
Потому что я хочу линейное время, что средства Я собираюсь есть цикл.
И обычный способ для перебора узлы в структуре списка или любого вида
структуры многократно это взять указатель на передней части данных
Структура, а затем просто начать обновление это и идти свой путь
через структуру данных.
Так что я собираюсь сделать именно это.
>> В то время как указатель, моя временная переменная, не равно NULL, давайте
идти вперед и проверить.
Разве я повезет?
Является ли поле п в узле Я в настоящее время глядя на равной
число Я ищу?
И если да, то давайте что-то делать.
Теперь, обратите внимание это, если условие окружает весь
Следующие строки кода.
Это единственное, что меня волнует - найти номер в вопрос.
Так нет еще, что упрощает вещи концептуально немного.
>> Но теперь я понял, и вы, возможно, только понял это, подумав
это через некоторое время, есть на самом деле два случая здесь.
Одним из них является где узел находится на начало списка, который является
немного раздражает, потому что это особый случай, потому что вы должны иметь дело
с этой вещью, которая является единственным аномалия.
Всюду еще в списке, это то же самое.
Там в предыдущий узел и рядом узел, предыдущий узел, следующий узел.
Но этот парень стоит несколько особняком, если он в самом начале.
>> Таким образом, если указатель равен список Сам, так что если я в начале
список, и я нашел п, мне нужно сделать несколько вещей.
Один из них, мне нужно изменить список указывают на следующее поле, 50.
Так предположить, что я пытаюсь удалить 34.
Так этот парень должен идти далеко в мгновение.
>> Так что я собираюсь сказать, список получает указатель рядом.
Ну, это указатель.
Следующая указывает здесь.
Так эта ситуация меняется эту стрелку право Теперь, чтобы указать на этого парня здесь.
Теперь, помните, у нас есть временная переменная.
Таким образом, мы не осиротел любые узлы, потому что я также с этим парнем в моем
реализация удаляется.
Так что теперь, если сам список не является пустым, Мне нужно, чтобы исправить кое-что.
>> Мне нужно теперь убедиться, что эта стрелка, который предварительно указывая
от 50 до 34, это должно уйти, потому что если я пытаюсь избавиться
из 34, 50 лучше не поддерживать любой вид обратная ссылка на него как
стрелка предложил.
Так что я просто сделал эту линию.
Итак я сделал.
Это дело на самом деле довольно просто.
Отрубание головы списка относительно проста.
>> К сожалению, есть такой раздражает еще блок.
Так что теперь, я должен рассмотреть случай где есть что-то в середине.
Но это не так уж страшно, за исключением синтаксиса, как это.
Так что, если я не в начале Список, я где-то в середине.
И эта линия здесь говорит, старт на все, что узел вы находитесь.
Переход к следующему полю предыдущего узла и указывают, что на указатель.
>> Давайте сделаем это графически.
Это становилось сложнее.
Так что, если у меня есть предыдущие поля здесь - давайте сделаем это - здесь следующие поля.
Я собираюсь упростить мои указатели, а чем нарисовать целую кучу
вещи назад и вперед перекрещивающиеся друг к другу.
А теперь, давайте просто скажем, что это 1, 2, 3 ради обсуждения, даже
хотя это не совпадать с данная проблема.
>> Итак, вот мой связанный список.
Я пытаюсь удалить два в этом частности версия истории.
Так я обновил указатель быть указывая на этого парня.
Так что это PTR.
Он указывает здесь.
Это список, который существует глобально, как и раньше.
И он никогда указывая здесь ни на что.
И теперь, я пытаюсь удалить два.
>> Так что, если указатель направлен здесь, я будет следовать, по-видимому,
предыдущая указатель, который ставит меня в 1.
Я тогда хотел сказать, что следующий поле, которое приносит мне к этой
коробка здесь, собирается равна указатель напротив.
Так что, если этот указатель, это рядом.
Это означает, что эта стрелка потребности указать на этого парня.
>> Так что, что строка кода имеет только сделано немного об этом.
И теперь, это выглядит как шаг в правильном направлении.
Мы существенно хотите, чтобы отрезать 2 отъезде середины 1 и 3.
Так что имеет смысл, что мы хотим маршрут этот указатель вокруг него.
Так что это следующая строка проверки, если указатель следующая не является нулевым, есть
действительно кто-то справа от 2, это означает, что мы также должны сделать
немного СНиП здесь.
>> Так что я теперь должны следовать этот указатель и обновить предыдущий указатель на
этот парень, чтобы сделать немного обойти здесь точку здесь.
А теперь, визуально это приятно.
Это немного грязный в том, что есть никто не указывая на 2 больше.
2 указывает на левой стороне.
И 2 указывает вправо.
Но он может делать все, что он хочет, потому что он собирается получить свободу.
И не имеет значения, что эти значения больше.
>> Важно то, что оставшиеся ребята маршрутизации выше
и ниже него сейчас.
И в самом деле, это то, что мы будем делать дальше.
Мы бесплатно указатель, а это значит, мы говорим операционная система, вы можете
чтобы вернуть это.
А потом, наконец, мы вернемся.
Остальное неявно, если мы еще не вернулись,
мы должны продолжать поиски.
Так указатель равна указатель следующий раз означает двигаться этот парень здесь.
Перемещение этого парня здесь.
Перемещение этого парня здесь, если, по сути, мы не нашли номер
мы ищем еще.
>> Так откровенно говоря, это выглядит совершенно Подавляющее, я думаю, в первую очередь
взгляд, особенно если вы изо всех сил с этим в ходе викторины затем посмотреть,
что-то вроде этого.
И вы погладить себя по спине.
Ну, нет никакого способа, я мог бы придумать, что на викторине.
Но я бы сказал, вы можете, если вы нарушите это вниз, в эти индивидуальные
случаи и просто войти в нее тщательно, хотя, надо признать, в
стрессовые обстоятельства.
>> К счастью, картина сделана все счастливее.
Вы могли обратить на это в любое количество способов.
Вы не должны делать, пересекающих вещь здесь.
Вы можете сделать это с прямой линии, как это.
Но суть этой проблемы, в Вообще, было понимать, что
картина в конце должны немного что-то вроде этого, потому что
Постоянная времени подразумевает, что вы держите помех и помех и помех
новые узлы в начале из списка.
Есть вопросы?
Вероятно, наиболее сложной из конечно вопросы кодирования.
>> АУДИТОРИЯ: Так список похож на голову в предыдущих примерах.
>> Дэвид Дж. Малан: Точно, точно.
Просто другое имя для глобальная переменная.
Во всем мире и что?
>> ROB BOWDEN: ОК.
Так что это то место, где вы должен был написать этот пункт.
Некоторые люди писали эссе на этот вопрос.
Но нужно просто использовать эти шесть членов чтобы описать, что происходит, когда
Вы попробуйте связаться facebook.com.
Так что я буду просто говорить через процесс используя все эти термины.
Так в нашем браузере, мы набираем facebook.com и нажмите Ввод.
Таким образом, наш браузер собирается построить HTTP просить, чтобы он собирается отправить
через некоторое процесса в Facebook для Facebook, чтобы ответить на нас с
HTML его странице.
>> Так что это процесс, при какой запрос HTTP
на самом деле попадает в Facebook?
Итак, сначала мы должны перевести Facebook.com.
Так что просто дано имя Facebook.com, где на самом деле просить HTTP
нужно идти?
Так что мы должны перевести Facebook.com к IP адресу, который однозначно
идентифицирует, что машина у нас на самом деле хотите отправить запрос на.
Ваш ноутбук имеет IP-адрес.
Все, что подключены к Интернету имеет IP-адрес.
>> Так DNS, Domain Name System, то есть что происходит в обращении перевод
от facebook.com к IP-адреса, вы на самом деле хотите связаться.
Таким образом, мы связаться с DNS-серверов и скажем, что facebook.com?
Это говорит, о, это IP-адрес 190,212 что-то, что-то, что-то.
Хорошо.
Теперь, я знаю, что машина Я хочу связаться.
>> Тогда вы, отправьте запрос HTTP к этой машине.
Так, как это добраться до этой машины?
Ну, запрос идет от маршрутизатор к маршрутизатору подпрыгивая.
Помните пример в классе, где мы фактически видели маршрут, что
Пакеты взял, когда мы пытались общаться.
Мы видели это перепрыгнуть через Атлантику Океан в одной точке или любой другой.
>> Таким образом, последний член порт.
Так что это теперь на вашем компьютере.
Вы можете иметь несколько вещей в настоящее время общения с Интернетом.
Так что я могу быть запущен, скажем, Skype.
Я, возможно, веб-браузер с открытым.
Я мог бы иметь то, что torrenting файлы.
Так что все эти вещи общения с
Интернет в некотором роде.
>> Поэтому, когда ваш компьютер получает некоторые данные из Интернета, как делает это
знаю, что приложение на самом деле хочет данные?
Как это знаю, насколько это частности данные, предназначенные для
torrenting приложение в отличие в веб-браузере?
Так что это цель портов в том, что все эти приложения имеют
утверждал, порт на вашем компьютере.
Так что ваш веб-браузер говорит, эй, Я на порту 1000.
И ваша программа torrenting говорит, Я на порту 3000.
И Skype говорит, я использую порт 4000.
>> Поэтому, когда вы получаете некоторые данные, которые принадлежит к одному из этих приложений, данных
отмечен какой порт он на самом деле должны быть присланы вместе с.
Так что это говорит, о, я принадлежу к порту 1000.
Я знаю, то мне нужно направить этот вместе с моим веб-браузера.
Так что причина, что это отношение здесь является то, что веб-серверы, как правило,
порт 80.
Поэтому, когда я связаться Facebook.com, я общения с некоторой машины.
Но я должен сказать, какой порт, что машина Я хочу общаться с.
И веб-серверы, как правило, прослушивает порт 80.
>> Если бы они хотели, они могли установить его так, это показывает, как на порту 7000.
А потом в веб-браузере, я мог вручную ввести Facebook.com: 7000 в
отправить запрос на порт 7000 веб-сервер Facebook.
>> Дэвид Дж. Малан: И в этом случае, даже хотя мы не требовали, чтобы люди
говорю об этом, в данном случае, то, что порт будет запрос на самом деле пойти?
Попробуйте еще раз.
Именно так.
Не нуждаюсь в этом, но тонкость что не там ни последним.
>> ROB BOWDEN: Так HTTPS, так как это слушать специально для
зашифрован, это на порту 4430.
>> Аудитория: и электронные письма 25, не так ли?
>> Дэвид Дж. Малан: Исходящий трафик электронные письма, 25, да.
>> ROB BOWDEN: я даже не знаю, что большинство из - все нижние имеют тенденцию быть
зарезервированы для вещей.
Я думаю, что все под 1024 зарезервирован.
>> АУДИТОРИЯ: Почему вы говорите, 3 был неправильный номер?
>> ROB BOWDEN: Потому что в IP-адрес, есть четыре группировки цифр.
И они от 0 до 255.
Так 192.168.2.1 является общим Локальный IP-адрес сети.
Обратите внимание, все те, меньше, чем 255.
Поэтому, когда я начал с 300, что не мог иметь
был одним из чисел.
>> Дэвид Дж. Малан: Но это глупо клип от - это было CSI, где они должны были
число, которое было слишком большим для IP-адреса.
>> ROB BOWDEN: Все вопросы по этому поводу?
Следующий, так полное изменение тема, но у нас есть это PHP массив для
дома в четырехядерных.
И у нас есть неупорядоченный список.
И мы хотим, чтобы распечатать каждого элемента списка просто, содержащая имя дом.
Поэтому у нас есть цикл по каждому элементу.
Так что помните, синтаксис Еогеасп Массив как элемента массива.
Так через каждый итерации цикла, дом собирается взять на одном из
значения внутри массива.
>> На первой итерации, дом будет Кабот Дом.
На второй итерации, дом будет быть Курьер дома и так далее.
Таким образом, для каждого квадрата, как дома, мы просто в печать -
Вы также могли бы эхом -
элемент списка, а затем название дома в и закройте элемент списка.
Фигурные скобки являются необязательными здесь.
>> И тогда мы также сказал в вопросе Сам, не забудьте закрыть
неупорядоченный список тегов.
Так что мы должны выйти из режима PHP для того, чтобы сделать это.
Или мы могли бы вторит закрыть неупорядоченный список тег.
>> Дэвид Дж. Малан: Также хорошо здесь будет были использовать старую школу для
петля с $ I = 0 0 и используя рассчитывает на выяснить длину луча.
Полностью тоже хорошо, только немного wordier.
>> АУДИТОРИЯ: Так что, если вы собирались [Неразборчиво], вы могли бы сделать -
Я забыл, что петля [неразборчиво] есть.
Вы бы $ четырехъядерный кронштейн я?
>> Дэвид Дж. Малан: Совершенно верно.
Да, именно так.
>> ROB BOWDEN: Что-нибудь еще?
>> Дэвид Дж. Малан: Хорошо.
Компромиссы.
Так появились гроздья ответов возможно для каждого из них.
Мы действительно просто ищете что-то привлекательным для перевернутой и
и обратная сторона.
И число 16 спросил, проверка пользователи ' вход со стороны клиента, так как с JavaScript,
вместо стороне сервера, а с PHP.
Так в чем же потенциал роста делать на стороне клиента?
>> Ну, одна из вещей, мы предложили это что вы уменьшить время ожидания, потому что вы
не придется беспокоиться контакте сервер, который может занять несколько
миллисекунд или даже пару секунд избегая, что и просто
Проверка сведений, вводимых на стороне клиента пользователей по вызывая на-представить обработчик и
просто проверка, они типа что-то в качестве имени?
Разве они что-то типа в течение адрес электронной почты?
Разве они выбирают общежитие от выпадающее меню?
>> Вы можете дать им мгновенную обратную связь с помощью гигагерц компьютер
или что у них есть это фактически на столе.
Так что это просто лучше пользователь опыт обычно.
Но недостаток делать на стороне клиента Проверка, если вы делаете это без того,
делать проверку на стороне сервера является то, что Наиболее кто-то выходит из CS50 знает
что вы можете просто отправить любое данные, которые необходимо на сервере любое количество способов.
Честно говоря, в большинстве любом браузере, вы можете нажмите вокруг в настройках и просто
выключить наличие, которая бы, Поэтому, отключить любую форму
проверка.
>> Но вы также могли бы вспомнить, что даже я сделал некие замысловатые действия в классе, используя
Telnet и фактически делая вид, быть браузеру, отправив GET
запросы к серверу.
И это, конечно, не с помощью любого JavaScript.
Вот только мне ввода команд на клавиатуре.
Так на самом деле, любой программист в достаточно комфорт с веб-и HTTP-
может отправить все данные он или она хочет к серверу без проверки.
И если ваш сервер не также проверки, они дать мне имя, является
это на самом деле действительный адрес электронной почты, сделал они выбирают общежитие, то в конечном
до вставки поддельным или просто пустой данных в базу данных, которая, вероятно,
не будет хорошо, если Вы были предполагая, что это было.
>> Так что это досадная реальность.
Но в общем, на стороне клиента проверка велик.
Но это значит, в два раза больше работы.
Хотя существуют различные библиотеки, JavaScript библиотеки для
Экземпляр, которые делают это много, гораздо меньше головной боли.
И вы можете использовать часть кода на стороне сервера, на стороне клиента.
Но понимаю, что это, как правило, дополнительная работа.
Да.
>> АУДИТОРИЯ: Так что, если мы просто сказал менее безопасным -
>> Дэвид Дж. Малан: [смеется]
Тьфу.
Те, всегда труднее те, для рассмотрения.
>> ROB BOWDEN: Это было бы были приняты.
>> Дэвид Дж. Малан: Что?
>> ROB BOWDEN: Я создал эту проблему.
Это была бы принята.
>> Дэвид Дж. Малан: Да.
>> АУДИТОРИЯ: Круто.
>> ROB BOWDEN: Но мы не принимали для первого -
хорошо, что мы искали это что-то вроде вас не должны
связи с сервером.
Мы не принимаем только быстрее.
>> АУДИТОРИЯ: А как насчет не перегрузить страницу?
>> ROB BOWDEN: Да.
Это было принято отвечать.
>> Дэвид Дж. Малан: Все, где мы чувствовали, это было более вероятно, чем нет, скорее всего
что вы знали, что вы были говоря, что является жестким
линия обратить иногда.
Использование связанного списка, а не из массива для поддержания
сортируются список целых чисел.
Так с ног, мы часто цитируют с связаны списки, мотивированные всю свою
Введение был вы получаете динамизм.
Они могут расти.
Они могут сокращаться.
Так что вам не придется прыгать через обручи на самом деле создать больше памяти
с массивом.
Или вы не должны просто говорят, извините, пользователь.
Массив заполняется.
Так динамичный рост списке.
Нижняя сторона, хотя связанных списков?
>> АУДИТОРИЯ: Это линейная.
Поиск на связанный список линейна вместо того, что вы входите в
>> Дэвид Дж. Малан: Совершенно верно.
Поиск на связанный список является линейным, даже если это сортируется, потому что вы можете
только следующие хлебные крошки, эти указатели, от начала списка
до конца.
Вы не можете использовать произвольный доступ и, Таким образом, бинарный поиск, даже если это
сортируются, что вы могли бы сделать с массивом.
И есть еще одна стоимость.
Да.
>> АУДИТОРИЯ: Память неэффективно?
>> Дэвид Дж. Малан: Да.
Ну, я бы не стал обязательно сказать неэффективным.
Но это обойдется вам больше памяти, потому что вам нужно 32 бита за каждый
узел для дополнительного указателя, по крайней мере, для однонаправленного списка.
Теперь, если вы только способ хранения целочисленных и Вы добавляете указатель, это
на самом деле вид нетривиально.
Это удвоение объема памяти.
Но на самом деле, если вы храните связанный список структур, которые могли бы
8 байт, 16 байт, еще более Кроме этого, может быть, это меньше
маргинальной стоимости.
Но это стоимость, тем не менее.
Так что либо из тех бы уже было прекрасно, как недостатки.
>> 18.
Использование PHP вместо C написать Программа командной строки.
Так вот, это часто быстрее использовать язык, как PHP или Ruby, или Python.
Вы просто быстро открыть до текстовом редакторе.
У вас есть гораздо больше функций доступны для вас.
PHP имеет раковину функций, тогда как в C, вы
есть очень и очень мало.
На самом деле, ребята знают на собственном горьком опыте что у вас нет хэш-таблицы.
Вы не связали списки.
Если вы хотите, чтобы те, вы должны реализовать их самостоятельно.
>> Так что потенциал роста PHP или действительно любой интерпретировать язык является быстрота
с помощью которого можно писать код.
Но недостаток, мы видели это, когда я быстро на скорую руку misspeller
реализация в лекции с использованием PHP, является что использование интерпретируемого языка
как правило, медленнее.
И мы видели, что явно с увеличение времени от 0,3 секунды до 3
секунд, из-за интерпретации что происходит на самом деле.
>> Другой верх в том, что вам не обязательно собирать.
Так оно и ускоряет разработку кстати, потому что у вас нет
в два этапа запуска программы.
Вы просто есть.
И таким образом, это довольно убедительным, а также.
Использование базы данных SQL вместо файл в формате CSV для хранения данных.
Так SQL база данных используется для pset7.
CSV файлов, которые вы не использовали много.
Но вы использовали его косвенно в pset7 как хорошо, поговорив с Yahoo Finance.
>> Но CSV так же, как файл Excel, но супер просто, где столбцы
просто демаркированы запятыми внутри в противном случае из текстового файла.
И с использованием базы данных SQL является немного более убедительным.
Это положительная сторона, потому что вы получаете то, как выбрать и вставлять и удалять.
И вы получите, предположительно, индексы, MySQL и других баз данных, как
Oracle, построить для вас в памяти, что означает, что ваш выбор, вероятно, не
будет линейной сверху вниз.
Это на самом деле будет что-то как бинарный поиск или что-то
близки по духу.
Таким образом, они как правило, быстрее.
>> Но недостаток в том, что это просто больше работы.
Это больше усилий.
Вы должны понять, базы данных.
Вы должны установить его.
Вам нужен сервер для запуска что база данных по.
Вы должны понимать, как его настроить.
Так что это только эти виды компромиссов.
В то время как файл CSV, вы можете создать его с Gedit.
И вы хорошо идти.
Там нет сложности за рамки этого.
>> Использование синтаксического дерева вместо хэш-таблице с раздельного связывания для хранения
словарь слов, напоминающих из pset5.
Так пытается вверх, в теории по крайней мере, это то, что?
Постоянное время, по крайней мере, если вы хэширования на каждом из отдельных
буквы в слова, как и вы может иметь для pset5.
Это может быть пять хэши, шесть хэши, если есть пять или шесть
буквы в слове.
И это очень хорошо.
И если есть верхняя граница, как долго ваши слова могут быть, это
действительно асимптотически постоянная времени.
>> В то время как хэш-таблицу с отдельным цепочки, проблему там с, что
Такая структура данных является то, что выполнение ваших алгоритмов обычно
зависит от количества вещей уже в структуре данных.
И это, безусловно, в случае с цепи, в результате чего больше материала вы положили
в хэш-таблицу, тем дольше тех, цепи идти, что означает, в худшем
так, то, что вы могли бы искать все пути в конце один
из этих цепей, которые эффективно передает в чем-то линейной.
>> Теперь, на практике она может абсолютно быть так, что хэш-таблицу с
цепи быстрее, чем соответствующий Реализация синтаксического дерева.
Но это по разным причинам, среди которые пытается использовать всю серию
что память может, на самом деле, медленные вещи вниз, потому что вы не получаете хороший
Преимущества, что называется кэширование, где вещи, которые близко друг к другу
в памяти можно получить часто более быстро.
И иногда вы можете придумать действительно хороший хэш-функция.
Даже если вам придется тратить немного памяти, вы можете, конечно, быть в состоянии
найти вещи быстро и не так плохо, как линейно.
>> Короче говоря, есть не обязательно с любым из них один или даже два
конкретные вещи, которые мы искали.
Действительно ничего убедительным как вверх и недостатков
как правило, попался на глаза.
>> ROB BOWDEN: Так что для верху, мы сделали не принимает самостоятельно "быстрее". Вы
должен был сказать что-то об этом.
Даже если вы теоретически быстрее сказал, мы знали, что вы вроде понял
что это 0 1.
И хеш-таблицы, в теории, не 0 1.
Упоминание ничего выполнения как правило, получили вы точки.
Но "быстрее", большинство решений на большой совет, которые были отрасли были
объективно медленнее, чем решений что были хэш-таблицы.
Так быстрее и само по себе не совсем так.
>> Дэвид Дж. Малан: Дом де дом дом.
Я, наверное, единственный, который понимает, вот как, что, как предполагается,
произноситься, правильно?
>> ROB BOWDEN: у меня не было на самом деле не знаю,.
>> Дэвид Дж. Малан: Он сделал смысл в моей голове.
>> ROB BOWDEN: Я делаю это.
ОК.
Так что это то место, где вы должны были обратить диаграмма похожа на вас, возможно,
видели на прошлых экзаменов.
Так что давайте просто посмотрим на это.
Так что с HTML узла, у нас есть два дети, голова и тело.
Таким образом, мы расшириться - голову и тело.
Головка имеет тег заголовка.
Поэтому у нас есть название.
>> Теперь, одна вещь, много людей забыл, что эти текстовые узлы
элементы внутри этого дерева.
И вот мы, случается, привлечь их в виде овалов чтобы отличать их от них
типы узлов.
Но обратите внимание также здесь у нас есть вершины, средний, и нижний будет в конечном итоге
текстовые узлы.
Так забывая тех, была несколько общей ошибке.
>> Тело имеет троих детей - эти три дивы.
Так дел, дел, дел, а затем текст узел дети тех дивы.
Это в значительной степени это для этого вопросы.
>> Дэвид Дж. Малан: И стоит заметить,, хотя мы не будем останавливаться на них
детали в времени мы проводим на JavaScript, что порядок делает, в
Дело в том, независимо от того, в техническом плане.
Так что, если руководитель идет перед органом в HTML, то он должен появиться в
слева от тела в фактическом DOM.
Что его, в общем, просто FYI, то, что называется порядок документ, где
это имеет значение.
И если вы были реализации парсер, программа, которая читает HTML в здании
вверх по дереву в памяти, если честно, вот интуитивно вероятно, что вы
сделать в любом случае - сверху вниз, слева направо.
>> ROB BOWDEN: Вопросы по этому поводу?
Должен ли я сделать следующий?
>> Дэвид Дж. Малан: Конечно.
>> ROB BOWDEN: ОК.
Так что это переполнение буфера нападение вопрос.
Главное, чтобы признать здесь, ну, как могли бы противник трюк
эта программа в исполнении произвольного кода?
Так argv1, первый командной строки аргумент этой программы, которые могут быть
произвольной длины.
Но здесь мы используем тетсру скопировать argv1, которые здесь находится бар.
Мы передачи его в качестве аргумента.
И так это занимает на заводской бар.
>> Таким образом, мы memcpying бар в этой буферной в.
Сколько байт мы копирования?
Ну однако многие бар байт случается использовать, длину этого аргумента.
Но с составляет всего 12 байт в ширину.
Так что, если мы наберем аргумент командной строки это больше, чем 12 байт, мы
собирается переполняться это частности буфера.
Теперь, как может противник обмануть запрограммировать в выполнении произвольный код?
>> Поэтому помните, что здесь Основной зовет Foo.
И так, то основные вызовы Foo.
Давайте нарисуем это.
Так у нас есть стек.
А главное есть кадр стека в нижней части.
В какой-то момент, основные вызовы Foo.
Ну, сразу, основные вызовы Foo.
И так Foo получает собственный фрейм стека.
>> Теперь, в какой-то момент, Foo собирается вернуться.
И пошел Foo возвращения, мы должны знать, в что строка кода внутри главного мы
были для того, чтобы знать, где мы должны возобновить в основной.
Мы можем назвать Foo от в целом куча разных местах.
Как мы знаем, где, чтобы вернуться?
Ну, нам нужно сохранить, что где-то.
>> Так где-то прямо здесь, мы храним где мы должны вернуться, чтобы еще
Foo возвращается.
И это обратный адрес.
Так как противник может воспользоваться этого является тот факт, что
этот буфер с хранится, давайте сказать, прямо здесь с.
Итак, мы получили 12 байт для с.
Это с.
И это стек кольцо Foo в.
Таким образом, если злоумышленник входит более байт, чем 12 или они входят в команду
Аргумент строка, которая длиннее, чем 12 символов, то мы собираемся
переполнение этот буфер.
>> Мы можем продолжать идти.
И в какой-то момент, мы идем далеко Достаточно того, что мы начинаем
перезаписи этот обратный адрес.
Поэтому, как только мы перезаписать адрес возврата, Это означает, что когда Foo
возвращается, мы возвращаемся туда, где злоумышленник говорит его по
любое значение он вошел, каким бы символов пользователь ввел.
И поэтому, если злоумышленник в настоящее время особенно умен, он может иметь это
вернуться к где-то в PRINTDEF функция или где-то в таНос
Функция, где-нибудь произвольным.
>> Но еще более умный это то, что если у него есть пользователь вернуться к прямо здесь.
И тогда вы начинаете выполнение их как строк кода.
Так в этой точке, пользователь может ввести все, что он хочет в этом регионе.
И он имеет полный контроль над вашей программы.
Вопросы по этому поводу?
Так что в следующий вопрос завершения переписанной Foo таким образом
не, что это больше не уязвимы.
>> Таким образом, есть несколько способов, вы могли бы сделать это.
У нас еще есть с только быть длиной 12.
Вы, возможно, изменили это как часть вашего решения.
Мы также добавили проверку, чтобы сделать уверен бар не был пустым.
Хотя вам не нужно что за полный кредит.
Таким образом, мы проверки сначала длина строки бар.
Если это больше 12, то фактически не делают копию.
Так вот один из способов ее исправление.
>> Другой способ фиксации его есть вместо имея гр быть только длины 12, у меня
быть длины STRLEN (бар).
Другой способ фиксации его является на самом деле, только что вернулись.
Так что если вы только что избавился от всех это, если вы только что удалил все
строк кода, вы получили бы полный кредит, так как эту функцию
на самом деле не чего-то добиться.
Это копирования из командной строки Аргумент в некоторую массива в
его местный кадр стека.
И тогда, что возвращается.
И все, что он опытный ушел.
Так возвращение было также достаточно способ получить полный кредит.
>> Дэвид Дж. Малан: Не совсем дух вопрос, но приемлемый за
спецификации, тем не менее.
>> ROB BOWDEN: Вопросы по любой из этого?
Единственное, что вы по крайней мере нужно было компиляции кода.
Поэтому, даже если технически вы не уязвимыми, если ваш код не
компиляции, мы не согласиться с этим.
Нет вопросов?
ОК.
>> Дэвид Дж. Малан: Вы хотите сказать это название?
>> ROB BOWDEN: Нет.
>> Дэвид Дж. Малан: Так в этом, это была или хорошая это новость или плохая новость.
Это буквально та же проблема в качестве первого викторины.
И это почти то же самое Проблема, как pset1.
Но это было намеренно упрощена, чтобы быть проще пирамида, который может быть
решена со слегка проще итерации.
И в самом деле, что мы получали в здесь не столько логика,
потому, вероятно, к этому моменту, вы более комфортно, чем вы были
в неделю один с для петель или почему петель, но на самом деле, чтобы дразнить друг от друга, что
вы немного знакомы с Понятие, что PHP не только о том, что
программирования.
Это действительно может быть использован в качестве языка писать программы командной строки.
>> И в самом деле, это то, что мы пытались чтобы обратить ваше внимание на.
Это программа PHP командной строки.
Так C код здесь, в то время как правильное в С, не исправить для PHP.
Но код действительно одно и то же.
Если сравнить решения для викторины 0 против Викторина 1, вы обнаружите, что
это почти идентичны, за исключением некоторые знаки доллара и для
Отсутствие типа данных.
В частности, если мы взглянем здесь, вы увидите, что мы перебираем, в этом
случай, от 1 до до 7.
>> Мы могли бы сделать это 0 индекс.
Но иногда, я думаю, это просто мысленно легче думать о вещах,
от 1 до 7.
Если вы хотите один блок, потом два блоки, потом три, потом
точка, точка, точка семь.
Мы J инициализации до 1 а затем рассчитывает на до I.
И здесь все в противном случае идентичны.
Но следует назвать несколько вещей.
Мы даем вам эти две строки, это первое один, goofily назван как притон
для резкого взрыва.
И это только указывает путь, папка, в которой программа может быть
обнаружили, что вы хотите использовать интерпретировать этот файл.
>> И то линия после этого, из Конечно, означает войти в режим PHP.
А линия в самом низу означает выхода из режима PHP.
И это работает, в общем, с интерпретируемые языки.
Это своего рода раздражает, если вы пишете Программа в файле под названием foo.php.
И тогда ваши пользователи должны просто помните, ОК, чтобы запустить эту программу, я
должны ввести "PHP пространство foo.php." Вид раздражает, если ничего другого.
И это также показывает, что ваша программа написано в PHP, который не все
что освещения для пользователя.
>> Таким образом, вы можете удалить. PHP вообще Напомним, от лекции.
И вы реально можете сделать. / Foo если Вы chmodded его, сделав его
исполняемый.
Так CHMOD + х Foo сделал бы это.
И если вы также добавить притон здесь.
Но на самом деле, проблема клонит распечатав что-то вроде этого.
Нет HTML, нет C-код, конечно, лишь некоторые PHP.
Так Мило затем вернулся в задаче 25.
И в 25, вам дали следующие Код скелет, который был
довольно просто веб-страницы.
И сочная часть HTML-мудрый снизился здесь, где мы имеем внутри тела
форма, которая имеет уникальный идентификатор входа внутри которого было два входа, один
с идеей имя, один с идеей кнопки.
>> Первым был тип текста, Второй тип представляет.
И так, мы дали вам, на самом деле, более ингредиенты, чем вам нужно, просто так
вы, ребята, были варианты, с которыми чтобы решить эту проблему.
Вы не строго необходимо все эти идентификаторы.
Но это позволяет решить это по-разному.
И наверху, заметить, что Целью было вызвать
окно, как это -
Здравствуйте, Мило! -
появляться в браузере с помощью супер просто, если
не урод, оповещения функция.
И так, в конечном счете, это сводится концептуально как-то прослушивания
Доводы вида на стороне клиента , Не на стороне сервера, так или иначе
отвечая на этой представлению хватая значение, введенный пользователем
и поле имени, а затем отображая его в теле предупреждения.
>> Так один из способов сделать это с JQuery, который выглядит немного
синтаксически недоумение в первую очередь.
Вы можете сделать это с чистой кода DOM - document.getelement по ID.
Но давайте взглянем на этой версии.
У меня есть несколько важных линии в первую очередь.
Так что, у нас есть эта линия, которая является идентичен тому, что вы, возможно, видели
в, я считаю, form2.html от класса в неделю 9.
И это просто говорю, выполнить Следующий код, когда
документ готов.
Поскольку это важно только потому, что HTML страницы читаются сверху
снизу, слева направо.
>> И поэтому, если вы попытаетесь сделать что-то в коде здесь в какой-то DOM
элемент, некоторые HTML теги, это вниз здесь, вы делаете это слишком рано,
потому что это не имеет даже был прочитан в память.
Так, говоря эту document.ready линия, мы говорим,
Вот код, браузер.
Но не не выполнять это, пока в целом Документ готов, то есть DOM
дерево существует в памяти.
Это одна немного больше просто, если синтаксически
немного отличается, где я говорю, захват элемент HTML чьи уникальные
идентификатор входа.
Это то, что хэш-тег обозначает, уникальный идентификатор.
А потом я звоню. Представить.
>> Так. Представить здесь является функцией, в противном случае известен как способ, это
внутри объекта на левой сторона там, что я не выделить.
Так что если вы думаете, входов в качестве объекта в памяти - и это действительно так.
Это узел в дереве -
. Представить средства, когда эта форма с этот идентификатор представляется, выполнить
следующий код.
Мне все равно, как называется функция Я выполнения.
Так вот, я использую, как и прежде, что называется функцией лямбда или
анонимная функция.
Это вовсе не интеллектуально Интересно другое, чем это не имеет имени,
и это хорошо, если вы только когда-либо буду называть его один раз.
А внутри я на самом деле справиться представление формы.
Я сначала объявить переменную называется значение.
И то что эффект от этого подчеркнул часть здесь сейчас?
Что это делать в высокий уровень для меня?
>> АУДИТОРИЯ: Он получает значение, пользователь не ниже в HTML.
Он получает этот идентификатор, а затем обнаруживает, что значение его.
>> Дэвид Дж. Малан: Совершенно верно.
Она захватывает узел, чьи уникальные идентификатор имя.
Он получает значение в нем, которые это, по-видимому, что пользователь
набрали его или себя.
А потом он хранит, что в переменная с именем значение.
Как и в сторону, вы могли бы также сделал это немного по-другому.
Полностью приемлемым, делая что-то ложь значение переменной получает
document.getElementById.
И именно поэтому это немного утомительно, чтобы не использовать JQuery.
"Название" значение..
Так вполне приемлемо.
Различные способы сделать это. JQuery просто имеет тенденцию быть немного более кратким и
определенно более популярным среди программистов.
>> Теперь, я делаю немного здравомыслия проверить, потому что в задаче
заявление мы явно сказал, если Пользователь пока не набрали его или ее
назвать, не показывают предупреждений.
Но вы можете проверить на что, просто проверка на пустой строки для
цитата-конец цитаты, если есть ничего на самом деле.
Но если это не равно котировок конец цитаты, Я хочу позвонить оповещения.
И самое интересное в том, что мы с помощью оператора плюс, который
чем занимается в JavaScript?
Объединение.
Так что это, как PHPs оператора точки.
Та же самая идея, синтаксис немного другой.
И я просто создание строку, вы видели на скриншоте -
Здравствуйте, так и так.
>> И тогда последняя деталь заключается в следующем.
Почему я вернуться ложное внутри этой анонимной функции?
>> АУДИТОРИЯ: Там нет значение.
Вы ставите его в форме.
Это просто говорит, если значение не равно пустой, то сделайте это.
Был пробел в этой представления.
>> Дэвид Дж. Малан: ОК.
Осторожный, хотя.
Там нет никого здесь.
И, что возвращение ложным находится за пределами из, если условия.
Так что это подчеркнул линию, вернуться ложным, не выполняет ни на что, когда
формы.
Что возвращения ложное внутри этого обработчик события, как это называется,
рассматриваемое событие быть представление?
>> АУДИТОРИЯ: Потому что это происходит только один раз.
>> Дэвид Дж. Малан: только происходит один раз.
Не совсем.
Да?
>> АУДИТОРИЯ: Это предотвращает форму от представления к поведению по умолчанию,
который сделает перезагрузки страницы.
>> Дэвид Дж. Малан: Совершенно верно.
Так что я перегрузки термин представить здесь, потому что я говорю, форма
представляется.
Но, как вы говорите, на самом деле это не был представлен в истинной HTTP образом.
При нажатии кнопки Отправить, из-за нашего OnSubmit обработчик, мы перехвата
что форма представления, так сказать.
Мы тогда делать свое дело с кодом JavaScript.
Но я сознательно возвращения ложным, потому что я не хочу чтобы это произошло
долю секунды позже для всей форме Сам должен быть представлен в Интернете
сервер с пар ключ-значение, изменив URL, чтобы быть что-то вроде
д = кошки или то, что мы сделали, Например, в классе.
Я не хочу, чтобы это произошло, потому что нет слушающий сервер для этого
сформировать представление.
Это чисто сделано в коде JavaScript.
И именно поэтому я даже не имеют Действие атрибут моей форме, потому что я
не намерены, чтобы это когда-либо зайти на сервер.
>> Так что это представляется.
Но мы перехвата эту форму представление и предотвращения дефолта
поведение, которое является фактически пройти весь путь к серверу.
>> АУДИТОРИЯ: Так держать его на стороне клиента.
>> Дэвид Дж. Малан: Ведение это на стороне клиента.
Совершенно верно.
Затем был мой, о MySQL.
>> ROB BOWDEN: ОК.
Так что это первый вопрос был вообще грубо для людей.
Хотя более поздние пошли лучше.
Таким образом, вы должны были выбрать правильные данные типа для обоих этих столбцов.
И оба из них имеют некоторые вещи о них, что
сделать выбор трудно.
Так внутр не правильный введите числа.
Причина в том, 12-значный номер счета число, внутр не является достаточно большим, чтобы
хранить всего цифры.
Так действует выбор был бы большой Int, если вы не знаете, что.
Другой вариант мог бы быть поле символ длины 12.
Так что либо из тех, работал бы.
Int не будет.
>> Теперь, баланс, вспомните pset7.
Таким образом, мы специально использовали десятичные хранить стоимости акций или -
>> Дэвид Дж. Малан: Наличными.
>> ROB BOWDEN: Наличными.
Мы использовали десятичные для хранения количества денежных средств, которые пользователь в настоящее время имеет.
Так по этой причине мы сделать это потому что, помните, плавает.
Там в с плавающей точкой в ​​точности.
Он не может точно хранить деньги значения, как мы хотим здесь.
Так десятичной способен точно магазин что-то, скажем, два знака после запятой.
Вот почему баланс, мы хотим его десятичное, а не плавать.
>> Дэвид Дж. Малан: А также, тоже, хотя это могло бы быть умным и в других
контексты, чтобы думать, может быть, это это шанс для внутр.
Я просто отслеживать вещи в гроши.
Потому что мы явно показали по умолчанию Значение будучи 100.00, что
означает, что он может быть просто внутр.
И еще тонкость тоже с числа было то, что это не было предназначено
быть вопрос с подвохом.
Но напомним, что внутр в MySQL, как в С, по крайней мере
Прибор, является 32-разрядным.
И хотя мы не ожидаем Вас точно знать, сколько цифры, которые
средства, не вспомнить, что наибольшее количество Вы можете представлять потенциально
с 32-разрядного числа примерно то, что?
>> Какой номер у нас всегда говорю?
От 2 до 32, что и примерно?
Вы не должны знать точно.
Но примерно полезно в жизни.
Это примерно 4 миллиарда.
Таким образом, мы сказали, что несколько раз.
Я знаю, что сказал, что несколько раз.
И это примерно 4 миллиарда.
И это хорошее правило эмпирическое знать.
Если у вас есть 8 бит, 256 является магическим числом.
Если у вас есть 32 бита, 4 млрд. плюс-минус.
Так что если вы просто запишите 4000000000, вы увидите, что это меньше цифр, чем
12, что означает, что явно не достаточно выразительность захватить
12-значный номер счета.
>> ROB BOWDEN: ОК.
Таким образом, остальные пошли лучше.
Так предположить, что банк налагает $ 20 ежемесячно
плата за обслуживание по всем счетам.
С чем SQL запросов могли банк вычесть $ 20 с каждого счетчика, даже если
это приводит к некоторым отрицательным сальдо?
Так в основном, Есть четыре Основные типы запросов -
вставить, выберите, обновления и удаления.
Итак, что мы думаем, что мы собираетесь использовать здесь?
Обновление.
>> Так что давайте взглянем.
Так вот мы обновляем.
Какой стол мы обновлении счета?
Так обновлении счета.
И то синтаксис говорит, что на счетах мы обновлении?
Ну, мы устанавливаем баланс, равный текущее значение баланса минус 20.
Так что это будет обновить все строки счетов, вычитания
$ 20 с баланса.
>> Дэвид Дж. Малан: Распространенная ошибка здесь, хотя мы иногда простил его,
был на самом деле есть PHP код здесь вызова функции запроса или положить
Кавычки вокруг всего, что не должны быть там.
>> ROB BOWDEN: Помните, что MySQL является отдельный язык из PHP.
Мы, оказывается, писать MySQL в PHP.
И PHP затем отправить его к серверу MySQL.
Но вам не нужно PHP для того, чтобы связь с сервером MySQL.
>> Дэвид Дж. Малан: Совершенно верно.
Так никакие переменные со знаками доллара должно быть в данном контексте.
Он может просто сделать все математики в самой базе данных.
>> ROB BOWDEN: ОК.
Так что в следующий один.
Это следующий?
Да.
Так с тем, что SQL-запрос может банк извлечения из памяти номеров из-за его
богатые клиенты, те, с Остатки больше, чем 1000?
Так какой из четырех основных типов мы собираемся здесь нужно?
Выберите.
Поэтому мы хотим, чтобы выбрать.
Что мы хотим, чтобы выбрать?
Что колонка мы хотим, чтобы выбрать?
Мы специально хотим для выбора номера.
Но если вы сказали звезда, мы Также принято считать, что.
>> Так выбрать номер из какой таблицы?
Учетные записи.
И то условие мы хотим?
Где баланс превышает 1000.
Мы также приняли больше или равно.
Последнее один.
С чем SQL запросов могли банк близко, то есть удалить все счета, которые
имеет баланс $ 0?
Итак, какие из четырех мы захочет использовать?
Удалить.
Так синтаксис для этого?
Удалить из какой таблицы?
Учетные записи.
И то условие, на котором мы хотим, чтобы удалить -
где баланс равен нулю.
Так удалить все строки из счетов где баланс равен нулю.
Вопросы по любой из них?
Хотите очереди?
>> Дэвид Дж. Малан: Очередь руководство.
Так в этом, мы дали вам несколько знакомы структура, которую мы исследовали
немного в классе рядом с структурами, который был данные
структура, относящаяся по духу.
Разница хоть и с очереди что мы должны были как-то помню, кто
был в начале очереди, в большой часть, так что мы могли бы сделать больше
эффективное использование памяти, по крайней мере, если бы мы использовали массив.
>> Потому напомним, если у нас есть массив, если, например, это фронт
очередь, если я получаю в очередь здесь, а потом кто-то входит в линию
позади меня, у меня за спиной, у меня за спиной, и один человек выходит из линии, вы
мог, как мы видели некоторые из наших человека добровольцы в классе, есть у каждого
переложить этот путь.
Но в целом, то, все делают что-то не наилучшим образом использовать время
в программе, потому что это означает, что ваш Алгоритм работает в какой
асимптотическое время работы?
Это линейная.
>> И я чувствую, что это своего рода глупо.
Если следующий человек в очереди на следующий Человек, который должен лететь в
магазин, они не у всех есть двигаться вместе.
Просто позвольте, что человек будет рвал когда придет время, например.
Так что мы можем сэкономить немного времени там.
И так, чтобы сделать это, однако, что средства что глава очереди или
Передняя часть очереди будет постепенно двигаться глубже и глубже
в массиве и в конечном счете могли бы фактически обернуть вокруг, если мы используем
массив для хранения людей в этой очереди.
Таким образом, вы можете подумать, из Массив в виде круглого данных
структура в этом смысле.
>> Таким образом, вы так или иначе придется отслеживать размер его или действительно конец его
а затем, когда начало ней.
Таким образом, мы полагаем, что вы объявляете одним из таких очередей, призвание
это д, просто одна буква.
Тогда мы предлагаем, что передняя быть инициализировано равным нулю, и что размер
инициализировать нулю.
>> Поэтому в данный момент, нет ничего внутри этой очереди.
И мы просим вас заполнить реализация Enqueue ниже в
таким образом, чтобы функция добавляет п к конец д, а затем возвращает истину.
Но если д полон или отрицательным, функция должна вместо вернуться ложным.
И мы дали вам пару предположений.
Но они на самом деле не функционально отношение, просто BOOL существует,
потому что, технически, логический не существуют в C, если вы не включают
определенный файл заголовка.
Так что просто убедитесь, что не было это трюк
Вопрос рода вещи.
>> Так поставить в очередь, мы предложили в образце решения по реализации следующим образом.
Один из них, мы сначала проверяем легкость, низко висящие фрукты.
Если очередь заполнена или число, что Вы пытаетесь вставить меньше
нуля, что мы сказали в спецификация проблемы должны
не допускается, потому что мы только хотим неотрицательные значения, то вы должны
просто сразу вернуться ложным.
Таким образом, некоторые относительно легко Проверка ошибок.
Если бы вы хотите добавить, что фактическая число, что нужно было сделать немного
думаю здесь.
И это то, где это немного раздражает мысленно, потому что вы должны
выяснить, как обращаться циклического возврата.
>> Но зачаток идеи здесь, это из интерес для нас является то, что с запахом
часто подразумевает модульная арифметика и мод оператор, процент сторона,
где вы можете пойти от большего значения на ноль, а затем один и два и
три, а затем обратно к нулю, один и два и три и так далее
снова и снова.
Так как мы предлагаем сделать это что мы хотим в качестве индекса в
Массив называется чисел, где наши целые лежат.
Но чтобы попасть туда, мы сначала хотим сделать независимо от размера очереди всего лишь
затем добавить к этому то, что Передняя часть списка.
И эффект, что является, чтобы поставить нас в правильная позиция в очереди и
Не думайте, что первым человеком в линии находится в начале, что он или
она абсолютно может быть, если мы были также переход всех.
Но мы просто создаем работу для себя, если мы взяли
что особое путь.
>> Так что мы можем держать его относительно просто.
Мы должны помнить, что мы просто добавил Int в очередь.
А потом мы просто возвращаем правда.
Между тем, в Dequeue, мы попросили вам делать следующее.
Реализовать это таким образом, что она dequeues, то есть удаляет и возвращает,
Int в передней части очереди.
Чтобы снять Int, достаточно забыть его.
Вам не нужно переопределить свою лепту.
Так что это еще на самом деле.
Так же, как данные на жестком диске, мы просто игнорируя тот факт,
что теперь там.
И если д пуст, мы должны вместо этого возвращать отрицательное 1.
Так что это чувствует произвольным.
Почему вернуться отрицательный 1 вместо ложно?
Да.
>> АУДИТОРИЯ: Вопрос хранит положительные значения.
Так как вы только хранить положительные значения в д, отрицательный ошибка.
>> Дэвид Дж. Малан: Хорошо, правда.
Так, потому что мы только хранить положительным значения или равен нулю, то это прекрасно, чтобы
возвращать отрицательное значение в качестве дозорных значение, специальный символ.
Но вы переписывания истории там, потому что причина, что мы только
возвращение неотрицательные значения потому что мы хотим, чтобы
иметь значение дозорного.
Так, более конкретно, почему бы просто не вернуться ложным в случае ошибки?
Да.
>> АУДИТОРИЯ: Вы не смогли вернуться целое.
>> Дэвид Дж. Малан: Совершенно верно.
И это где С получает довольно сдерживающим.
Если вы говорите, что вы собираетесь вернуть Int, у вас есть
вернуть Int.
Вы не можете получить фантазии и начать возвращение BOOL или поплавок или
строка или что-то в этом роде.
Теперь, тем временем, JavaScript и PHP и некоторые другие языки может, в самом деле,
Вы возвращении отличается типы значений.
И это действительно может быть полезно, когда вы могли бы вернуться положительные INTS, нули,
отрицательные Интс, или ложь или нулевой даже для обозначения ошибку.
Но мы не имеем, что универсальность в С.
>> Так что с Dequeue, что мы предлагаю сделать это -
>> ROB BOWDEN: Вы можете вернуться ложным.
Это просто, что ложь является хэш определить ложь нулю.
Так что если вы вернуться ложным, вы вернулись к нулю.
И ноль является допустимым, что в нашей очереди, в то время как отрицательный 1 не, если
ложно случилось с отрицательным 1.
Но вы не должны даже должны знать, что.
>> Дэвид Дж. Малан: Это почему я не сказал этого.
>> ROB BOWDEN: Но это не так что вы не можете вернуться ложным.
>> Дэвид Дж. Малан: Конечно.
Так из очереди, заметить, что мы принимаем аннулированию в качестве аргумента.
И это потому, что мы не проходя ничего дюйма
Мы просто хотим, чтобы удалить элемент в начале очереди.
Итак, как мы могли бы идти об этом?
Ну, во-первых, давайте сделаем это Быстрая проверка здравомыслие.
Если размер очереди 0, есть нет работы предстоит сделать.
Вернуться отрицательный 1.
Готово.
Так вот несколько строк моей программы.
Так только четыре линии остаются.
>> Так вот я решил уменьшить размер.
И уменьшая размер эффективно означает, что я забыл
что-то там.
Но я также должен обновить где передняя из чисел являются.
Таким образом, чтобы сделать это, мне нужно сделать две вещи.
Я в первую очередь необходимо вспомнить, что количество находится в начале очереди,
потому что мне нужно вернуть эту вещь.
Так что я не хочу, чтобы случайно забыть об этом и затем перезаписать его.
Я просто хочу, чтобы помнить в междунар.
>> А теперь, я хочу, чтобы обновить q.front быть q.front 1.
Так что, если это был первый человек в линия, сейчас, я хочу сделать плюс 1 к
указать на следующий человек в линии.
Но я должен справиться с этим циклического возврата.
И если мощность составляет глобальная константа, что происходит, чтобы позволить мне убедиться
как я доказываю до самого последнего человека в линия, операция по модулю принесет
меня обратно к нулю при Передняя часть очереди.
И который обрабатывает запахом здесь.
А потом я продолжу вернуться н.
>> Теперь, собственно говоря, я не сделал должны объявить н.
У меня не было, чтобы схватить его и хранить его временно, потому что значение
еще там.
Так что я мог бы просто делать правильные арифметические вернуть бывшего главу
очереди.
Но я просто чувствовал, что это было более ясно, на самом деле захватить Int, положил его
на русском языке, а затем вернуться, что для ясности, но
не является строго необходимым.
Psst.
Они все произносимые в моей голове.
>> ROB BOWDEN: Так первый вопрос это проблема бинарное дерево.
Так первый вопрос, мы учитывая эти цифры.
И мы хотим, чтобы хоть как-то вставить их в эти узлы таким образом, что это
действует бинарное дерево.
Таким образом, одна вещь, чтобы помнить о бинарные деревья поиска является то, что это не
только то, что вещь, чтобы слева меньше и, что нужно
право больше.
Это должно быть то, что все дерево, чтобы левый меньше, и все дерево
вправо, что больше.
>> Так что если я ставлю 34 здесь в верхней части, а затем Я положил 20 здесь, так что это действительно так
далеко, потому что 34 здесь.
20 собирается слева.
Так вот меньше.
Но я не могу затем положить 59 здесь, потому что хотя 59 находится справа 20,
она по-прежнему слева от 34.
Так что с этого ограничения в виду, Самый простой способ, вероятно, решая этот
Проблема в том, чтобы только вид из этих чисел -
так 20, 34, 36, 52, 59, 106.
И затем вставьте тех, слева направо.
>> Так 20 идет здесь.
34 идет здесь.
36 идет здесь.
52, 59, 106.
И вы также могли бы разобрался с некоторые подключения и понимая,
ой, подождите, я не хватает номеров заполнить это в здесь.
Поэтому мне нужно reshift что мой маршрут примечание будет.
Но обратите внимание, что в конечном трех, если Вы читать слева направо, он находится в
порядке возрастания.
>> Так что теперь, мы хотим объявить, что структура будет для
узлы в этом дереве.
Так что же нам нужно в двоичном дереве?
Поэтому у нас есть значение типа внутр, поэтому некоторые внутр значение.
Я не знаю, что мы назвали это в растворе -
Int N.
Нам нужно указатель на левой ребенка и указатель на правой ребенка.
Так это будет выглядеть следующим образом.
И это будет на самом деле выглядят перед когда же двусвязный
Список материал, так уведомление -
Я собираюсь придется прокручивать все обратный путь до проблемы 11.
>> Так заметите, что он выглядит так же, это, кроме того что мы просто случайно называем эти
разные имена.
У нас еще есть целое значение и два указателя.
Это просто, что вместо лечения указатели как указывая на следующую вещь
а предыдущая вещь, мы лечения указатели, чтобы указать на левой ребенка
и право ребенка.
ОК.
Так вот наша структура узла.
А теперь, единственная функция, мы должны реализации этого является траверс, которые
мы хотим перейти на дереве, печать из значений дерева в порядке.
>> Так смотрит сюда, мы хотели бы, чтобы напечатать из 20, 34, 36, 52, 59 и 106.
Как мы добились этого?
Так что это очень похоже.
Если бы вы видели в прошлом экзамен проблема что вы хотели, чтобы распечатать
все дерево запятыми между все, это было на самом деле, даже
легче, чем это.
Так вот решение.
Это было значительно легче если вы сделали это рекурсивно.
Я не знаю, если кто-то пытался сделать это повторно.
>> Но, во-первых, у нас есть базовый вариант.
Что делать, если корень является недействительным?
Тогда мы только собираемся вернуться.
Мы не хотим, чтобы напечатать что-нибудь.
Остальное мы собираемся пройти рекурсивно вниз.
Распечатать весь левое поддерево.
Так печатать все меньше чем мой текущего значения.
А потом я собираюсь печатать сам.
А потом я собираюсь рекурсивно вниз мой Весь правое поддерево, поэтому все
больше, чем моя ценность.
И это в печать из все в порядке.
Вопросы о том, как это на самом деле Достигается это за?
>> АУДИТОРИЯ: У меня есть вопрос на [неразборчиво].
>> ROB BOWDEN: Так один из способов приближается любая рекурсивная проблема в том, чтобы просто думать
об этом, как вы должны думать обо всех угловые случаи.
Так считают, что мы хотим распечатать эту все дерево.
Так что все мы собираемся сосредоточиться на это конкретный узел -
36.
Рекурсивные вызовы, мы делаем вид, тех, кто только работать.
Так вот, это рекурсивный вызов траверс, мы, даже не задумываясь
об этом, просто пересекая левую три, представьте, что уже печатает 20
и 34 для нас.
А потом, когда мы в конечном счете рекурсивно позвонить траверс на
Хорошо, что будет правильно печатать 52, 59 и 106 для нас.
>> Таким образом, учитывая, что это может печатать 20, 34 и другой может печатать 52, 59, 108,
все, что мы должны быть в состоянии сделать, это печать , себя в середине этого.
Так распечатать все перед нами.
Распечатать OURSELF, поэтому текущий узел печати 36, регулярный Е, а затем
печатать все после нас.
>> Дэвид Дж. Малан: Это где рекурсия становится действительно красиво.
Это этот удивительный прыжок веры, где Вы делаете мельчайшие немного работы.
И тогда вы позволить кому-то еще все остальное.
И, что кто-то еще является, по иронии судьбы, вы.
Таким образом, для серьезных пунктов домового, если прокрутке на вопросы -
>> ROB BOWDEN: По вопросам?
>> Дэвид Дж. Малан: И немного вниз, чтобы цифры, кто-нибудь знает, где
эти цифры взялись?
>> ROB BOWDEN: У меня буквально ни малейшего представления.
>> Дэвид Дж. Малан: Они появляются по всей викторины.
>> АУДИТОРИЯ: Являются ли они те же номера?
>> Дэвид Дж. Малан: Эти цифры.
Немного Пасхальное яйцо.
Так что для тех из вас, наблюдая в Интернете по адресу домой, если вы можете сказать нам по электронной почте
heads@CS50.net какое значение этих повторяющихся шесть цифры
всей викторины 1, мы будем душ вас с удивительным вниманием в финале
Лекция и стресс мяч.
Хороший, тонкий.
>> ROB Боуден: Любой последние вопросы ни о чем на викторине?