[МУЗЫКА ИГРАЕТ] David J. МАЛАН: Хорошо. Это CS50. Это пять неделе продолжал, и мы есть хорошие новости и плохие новости. Так Хорошей новостью является то, что CS50 запускает в эту пятницу. Если вы хотели бы присоединиться к нам, направиться в обычной URL здесь. не Даже лучшие новости, не лекция предстоящий понедельник 13-го. Чуть менее лучшего новости, викторина нуля в следующую среду. Подробнее можно нашел по этому адресу здесь. И в ближайшие пару дней мы будем заполняя пробелы с относительно номеров что мы зарезервировали. Лучше новость заключается в том, что буду быть курс всей отзыв сессия в ближайшую Понедельник вечером. Оставайтесь с нами, чтобы Курса сайт для размещения и деталей. Разделы, даже если он является праздник, также встретится также. Лучший новости, лекции в следующую пятницу. Так что это традиция, которую мы есть, в соответствии с учебной программе. Просто-- это будет удивительно. Вы увидите вещи, как структуры данных постоянной времени и хэш-таблицы, деревья и пытается. И мы будем говорить о проблемах дня рождения. Целая куча вещей ждет в следующую пятницу. Хорошо. Во всяком случае. Так напомним, что мы были упором на этой картине то, что внутри памяти нашего компьютера. Так памяти или оперативной памяти, где программы существуют в то время как вы работаете их. Если вы дважды щелкните значок, чтобы запустить некоторые программы или дважды щелкните значок, чтобы открыть файл, он загружен с жесткого диск или твердотельный накопитель в оперативной памяти, памяти произвольного доступа, где он живет, пока питание не отключится, крышка ноутбука закрывается, или выходе из программы. 

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

Итак, когда вы дважды щелкните Microsoft Word на Mac или ПК, или при запуске точку слэш Марио на Linux компьютер в вашем окне терминала, нули и единицы, которые составляют Слово или Марио временно хранятся в оперативной памяти компьютера в так называемый текстовый сегмент для конкретной программы. Ниже, что идет инициализация и неинициализированные данные. Это такие вещи, как глобальные переменные, что мы не использовали многие, но иногда мы в имел глобальные переменные или статически определен строки, закодирована такие слова, как "привет" , которые не приняты в от пользователя которые жестко в вашу программу. 

Теперь, на дне мы есть так называемый стеком. И стек, до сих пор, мы были используя для каких видов целей? Что стек используется для? Да? 

Аудитория: Функции. 

David J. МАЛАН: Для функций? В каком смысле для функций? 

АУДИТОРИЯ: Когда вы вызываете функцию, Аргументы копируются в стек. 

David J. МАЛАН: Точно. При вызове функции, ее Аргументы копируются в стек. Поэтому любые иксы или Y сайт или сайт или B, что вы передаете в функцию временно поставить на так называемый стеком, как одного из Анненберг Столовая лотки, а также вещи, как локальных переменных. Если ваша функция Foo или подкачки Функция иметь локальные переменные, как темп, те два в конечном итоге в стеке. Теперь, мы не будем слишком много говорить о им, но эти переменные окружения внизу мы увидели некоторое время назад, когда Я был возиться с клавиатуры один день и я начал доступа вещи как агду 100 или агду 1000, просто elements-- я забываю numbers-- но что не должны были быть доступны мне. Мы начали видеть некоторые фанки символы на экране. Это были так называемые переменные окружения как глобальных параметров для личных Программа или для моего компьютера, а не связаны с недавней ошибка, что мы обсуждали, Контузия, что было житья довольно много компьютеров. 

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

Но есть своего рода проблемы здесь, как и картина предполагает. Мы-то есть два корабли около сталкиваться. Потому что, как вы используете все больше и больше стека, и, как мы видим сегодня, вперед, как вы используете все больше и больше куча, безусловно, плохие вещи могут случиться. И в самом деле, мы можем вызвать, что намеренно или ненамеренно. Так в кульминации последнего раз был эта программа, которые не служат любая функциональная Цель кроме продемонстрировать как вам, как плохой парень действительно может принять Преимущество ошибок в чужой программе и взять на себя программу или даже Весь компьютерная система или сервер. Так что просто заглянуть ненадолго, вам заметить, что основные внизу принимает в командной строке Аргументы, как за ARGV. И это имеет вызов функции F, существенно безымянный функция называется е, и это прохождение в ARGV [1]. 

Поэтому, что бы слово пользователь вводит в на выводится после имени этой программы, а затем эта произвольная функция до сверху, е, занимает в строке, AKA символ *, как мы начали обсуждать, и он просто называет его "бар". Но мы могли бы называть его иначе. А потом он заявляет, внутри из F, массив символов называется c-- 12 таких символов. 

Теперь, по истории, которую я рассказывал минуту назад, когда в памяти является с, или те, 12 символы будет в конечном итоге? Просто чтобы быть ясно. Да? 

АУДИТОРИЯ: На стеке. 

David J. МАЛАН: На стеке. Так с является локальной переменной. Мы просим 12 символов или 12 байт. Те собираются в конечном итоге на так называемом стеке. Теперь, наконец, это другая функция что на самом деле очень полезно, но мы на самом деле не используется это сами, strncopy. Это означает строку копию, но только русские буквы, п символов. Так п символов будет копируется из бара в с. А сколько? Длина панели. Таким образом, другими словами, что одна линия, strncopy, собирается копировать официально запретить и в. 

Теперь, просто вид предвидеть Мораль этой истории, что потенциально проблематично здесь? Даже при том, что мы проверяем длину из бара, и передавая ее в strncopy, что ваши кишки говорю вам это еще сломано об этой программе? Да? 

АУДИТОРИЯ: Не включает комната для нулевого символа. David J. МАЛАН: Не включает комната для нулевого символа. Потенциально, в отличие от Прежняя практика, мы даже не есть так много как плюс 1 к разместить эту нулевой символ. Но это еще хуже, чем это. Что еще мы не в состоянии сделать? Да? 

АУДИТОРИЯ: [неразборчиво] David J. МАЛАН: Прекрасно. Мы жестко 12 довольно произвольно. Это не так много проблема, но тот факт, что мы даже не проверяя, если длина панели меньше 12, в этом случае он будет безопасно положить его в памяти называется с, что мы выделено. Действительно, если бар как 20 символов, Эта функция по-видимому, копирование 20 символов из бара в С, тем самым принимать, по меньшей мере 8 байтов что это не должно быть. Вот подтекст здесь. 

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

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

Но то, как компьютеры уже давно выложены вещи как локальных переменных и Аргументы, как это. Таким образом, в верхней части этой картины в синий кадр стека для F, так что все из памяти, что F специально использует. Так, соответственно, заметить, что Бар в этой картине. Бар был его аргумент. И мы утверждали, что аргументы Функции получить в стек. И с, конечно, Также в этой картине. 

И только для обозначений целей, заметить в верхнем левом углу то, что было бы с кронштейном 0 и затем слегка вниз, вправо является с кронштейна 11. Итак, другими словами, вы можете себе представить что есть сетка байт есть, первый из которых верхний левый, нижний из которых последний из этих 12 байт. 

Но теперь попробуйте для быстрой перемотки вперед. Что должно произойти, если мы передадим в струнной баре, это больше, чем с? И мы не проверка, если это действительно больше, чем 12. Какая часть этой картины собирается потерян байт 0, 1, 2, 3, точка точка точка, 11, а затем плохо, 12, 13 через 19? Что произойдет здесь, если вы вывести из заказа что с кронштейн 0 находится на вершине и с кронштейн 11 является своего рода вниз в порядке? Да? 

АУДИТОРИЯ: Ну, это будет перезаписать символ * бар. 

David J. МАЛАН: Да, это выглядит как Вы собираетесь перезаписать символ * бар. И что еще хуже, если вы отправляете в самом деле долго Строка, вы могли бы даже переписать то, что? В качестве обратного адреса. Что еще раз, так же, как крошка сказать программе, где вернуться к тому, когда F делается при вызове. 

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

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

Таким образом, если каждый из них Письма просто представляет, концептуально, атака, атака, атака, атака, некоторые плохие код что кто-то написал, но если это лицо достаточно умен, чтобы не только включать в себя все из тех RM-RFS, но и есть свои последние несколько байт быть число, которое соответствует в адрес его или ее собственный код атака что он или она прошла в только путем предоставления ему в командной строке, Вы можете эффективно обмануть компьютер в замечая при е делается выполнения, о, это время для меня, чтобы перейти назад к красному обратного адреса. Но так как он или она имеет так или иначе перекрываются, что обратный адрес с их собственным числом, и они достаточно умны, чтобы настроили, что число для обозначения, как вы см в супер верхней левый угол там, Фактический адрес в компьютерной годов Память о некоторых из их вредоносный код, плохой парень может обмануть компьютер в выполнении его или ее собственный код. 

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

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

Хорошо. Так таНос до сих пор был наш новый Друг в том, что мы можем выделить память что мы не обязательно знать, в заранее, что мы хотим, чтобы мы не должны на жесткий код в нашу номера программ, как 12. Как только пользователь говорит нам, сколько Данные он или она хочет, чтобы вход, мы можем Malloc что много памяти. 

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

Но куча здесь. И, что приятно об таНос является то, что когда таНос выделяет память здесь, это не повлияло, для Большая часть, стеком. И поэтому любая функция может получить доступ памяти, которая была malloc'd, даже на функцию как GetString, даже после того, как он будет возвращен. 

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

И Valgrind, один из инструменты, введенные в Pset 4, это все о помогая вам Теперь найти ошибки, как, что. Но, к счастью для Pset 4 вам не нужно использовать библиотеку CS50 или GetString. Поэтому любые ошибки, связанные с памятью являются в конечном счете, будет свой собственный. 

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

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

Какой же выход, если у вас есть создали массив в стеке, например, только с неделю два обозначения, что мы ввели, квадратных скобок с рядом внутри? Ну, у вас есть шесть Цифры в этих коробках. Что бы ваши инстинкты быть? Где бы вы хотели сказать? 

АУДИТОРИЯ: [неразборчиво] 

David J. МАЛАН: Извините? 

АУДИТОРИЯ: Положите его на конце. 

David J. МАЛАН: Положите его на конце. Так что просто на правый, вне этой рамки. Какой бы хорошо, но это Оказывается, вы не можете сделать это. Потому что, если вы не спросили Для этого блока памяти, это может быть совпадением тот это в настоящее время используется некоторой другой переменной в целом. Вспомните неделю или около того, когда мы заложили из имен Zamyla и Дэвин и Гейба в памяти. Они были буквально спина к спине к спине. Таким образом, мы не можем обязательно доверять, что бы ни было здесь доступна для меня, чтобы использовать. 

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

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

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

Но что, если мы рисовали, в этом случае, стрелки что так или иначе связать их прямоугольники вместе? Действительно, мы видели техническая воплощение стрелкой. Что мы использовали в последнее время дней, что, под капотом, является представителем стрелкой? Указатель, не так ли? 

Так что, если вместо просто хранить номера, как 9, 17, 22, 26, 34, что, если мы не сохраняется только номер, но указатель рядом с каждой такой числа? Так что так же, как вы бы нить иглу через целую кучу ткани, так или иначе связывая вещи вместе, так же может мы с указателями, как воплотился стрелками здесь, вид ткать вместе эти отдельные прямоугольники путем эффективного использования указателя Рядом с каждым номером, который указывает на некоторое следующего числа, что указывает на, в свою очередь, некоторые следующий номер? Итак, другими словами, то, что если мы на самом деле хотели реализовать нечто подобное? Ну, к сожалению, эти прямоугольники, По крайней мере, один с 9, 17, 22, не и так далее, они больше не хорошие квадраты с отдельных номеров. Дно, прямоугольник Ниже 9, например, представляет, что должно быть указателем, 32 бита. Теперь, я еще не в курсе любого типа данных в С, что дает не только Int но указатель в целом. 

Так в чем же решение, если мы хотим чтобы изобретать собственный ответ на этот? Да? 

АУДИТОРИЯ: [неразборчиво] 

David J. МАЛАН: Что это? 

АУДИТОРИЯ: Новая структура. 

David J. МАЛАН: Да, так почему не мы создаем новую структуру, или в С, структуры? Мы видели структур и раньше, если кратко, где мы имели дело со студенческой структуры как это, кто имел имя и дом. В Pset 3 прорыв вы использовали целый куча structs-- GRect и GOvals , что Стэнфорд создал в Кластер информация вместе. Так что, если мы возьмем эту же идею ключевые слова "объявлений типов" и "структурой," а затем некоторые студент-конкретные вещи, и развиваться это в следующем: ЬурейеЕ структуры node-- и узел только очень общее информатика Термин-то в структуре данных, Контейнер в структуре данных. Узел я утверждаю, будет иметь Int N, очень простой,, а затем еще немного загадочно, это вторая линия, структура узла * следующий. Но в менее технических терминов, что это за вторая линия кода в фигурных скобках? Да? 

АУДИТОРИЯ: [неразборчиво] David J. МАЛАН: указатель на другой узел. Так по общему признанию, синтаксис немного загадочным. Но если вы читаете это буквально, Следующий это имя переменной. Что такое тип данных? Это немного многословен на этот раз, но это тип структура узла *. Каждый раз, когда мы видели нечто звезду, что означает, что это указатель на этого типа данных. Так что в следующий, по-видимому указатель в структуре узла. 

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

Но с узлом в связан Список, мы делаем хотите узел быть ссылочной к подобного объекта. И так заметить изменение здесь не только то, что внутри фигурных скобок. Но мы добавляем слово «узел» вверху, а также добавив его на дно вместо "студента". И это только техническая деталь таким образом, что, опять же, ваша структура данных, может быть самоссылающиеся, так что Узел может указывать на другой такой узел. 

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

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

Теперь, Удалить собирается удалить номер из списка. Вставьте собирается добавить число в список. Поиск будет выглядеть числа в списке. И траверс только причудливый способ сказать, ходить по списку, распечатать его, но это так. Не меняйте его в любом случае. 

Так давайте попробуем это. Давайте пойдем дальше и ввести 2. А потом я собираюсь введите номер, говорят 9. Enter. И теперь моя программа просто запрограммирован сказать, список теперь 9. Теперь, если я пойду вперед и у Вставьте снова, пусть мне идти вперед и уменьшения масштаба и введите в 17. Теперь мой список 9, затем 17. Если я вставить снова, давайте пропустим один. Вместо 22, как за картины мы в смотрел на здесь, позвольте мне перейти вперед и вставить 26 следующая. Так что я собираюсь набрать 26. Этот список, как я ожидаю. Но сейчас, просто чтобы посмотреть, если этого кода собирается быть гибким, позвольте мне теперь Тип 22, которая, по меньшей мере концептуально, если мы Имея это сортируются, которые действительно будет другая цель прямо сейчас, должны пойти в период с 17 по 26. Так я попал Enter. В самом деле, что работает. И вот теперь позвольте мне вставить наконец, за картины, 34. 

Хорошо. Так что на данный позвольте мне предусматривают, что Удалить и Traverse и поиск сделать, В самом деле, работать. На самом деле, если я запустить поиск, давайте поиск по номеру 22, Enter. Было установлено, 22. Так что то, что это Программа Список Ноль делает. 

Но что на самом деле происходит на который реализует это? Ну, сначала я, возможно, придется, и в самом деле У меня есть, файл с именем list0.h. И где-то там это линия, ЬурейеЕ, структура узла, то у меня есть фигурные скобки, Int N, и затем struct-- что было определение? Структура, узел рядом. Так что мы должны звезду. Теперь технически мы попадаем в привычка рисунок его здесь. Вы можете увидеть учебники и онлайн ссылки сделать это там. Это функционально эквивалентны. На самом деле, это немного более типичным. Но я буду последователен с чем мы сделали в прошлый раз и сделать это. И тогда, наконец, я собираюсь сделать это. 

Так в файле заголовка где, в list0.h сегодня это определение структуры, и, возможно, некоторые другие вещи. Между тем в list0c есть будет несколько вещей. Но мы собираемся просто начать и не закончить это. List0.h это файл я хочу включить в моей C файл. А потом в определенный момент я придется Int, главная, аннулированию. А потом я собираюсь есть некоторые к делу здесь. Я также собираюсь иметь Прототип, как пустот, поиск, INT, н, чья цель в жизни искать элемента. А потом сюда я утверждаю в сегодняшняя код, недействительными, поиск, Int, н, нет запятой, но открытые фигурные скобки. А теперь я хочу, чтобы так или иначе искать для элемента в этом списке. Но мы не имеем достаточно информация на экране еще. У меня на самом деле не представлял сам список. Так один из способов мы могли бы реализовать связанный список в программе будет я вроде хочу делать то, как декларируют связано список здесь. Для простоты я собираюсь сделать эта глобальная, хотя в целом мы не должны делать этого слишком много. Но это упростит этот пример. Поэтому я хочу заявить связанный список здесь. Теперь, как я мог бы это сделать? 

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

АУДИТОРИЯ: Нам нужен указатель на узел. David J. МАЛАН: указатель на узел. В частности, какой узел бы ваша инстинкты бы хранить указатель на? 

АУДИТОРИЯ: Первый узел. 

David J. МАЛАН: Да, вероятно, только первый. И обратите внимание, первый узел другую форму. Это только половина размер структуры, потому что это действительно только указатель. Так что вы действительно можете сделать, это объявить связанный список, чтобы иметь тип узла *. И давайте просто называть его первым и инициализировать его до нуля. Так нуль, опять же, идет в картину здесь. Мало того, что используется в качестве нуль, как специальная Возвращаемое значение для того, как GetString и таНос, нуль также нулевая указатель, отсутствие указателя, если вы будете. Это просто означает, ничто не упомянут тут. Теперь первый, я мог бы назвал это ничего. Я мог бы назвать его "список" или любое количество других вещей. Но я звоню его "первым", так что он выстраивается в линию с этой картины. Так же, как струны может быть представлено с адресом его первого байта, так может связанный список. И мы увидим другие данные структуры можно представить только с одним указателем, 32-разрядная стрелка, указывая на первом узле в структуре. 

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

Пока мы нанизывая все эти узлы вместе, только вспоминая, где Первый, до тех пор, как мы ставим специальный символ на самый последний узел в списке, и мы будем использовать нуль, потому что это то, что мы имеем в распоряжении, чтобы нас, этот список будет завершена. И даже если бы я только дать вам указатель первый элемент, вы, программист, безусловно, может получить доступ к остальным его. Но давайте пусть ваши умы побродить немного, если они не уже довольно wandered-- что будет время работы найдя ничего в этом списке? Черт возьми, это большая O н, что не плохо, справедливости ради. Но это является линейным. Мы отказались от того, что функция массивов путем перемещения более к этой картине динамически переплетаются или связаны узлы? Мы отказались от случайного доступа. Массив приятно, потому что математически все является спина к спине к спине к спине. Даже при том, что этой картине выглядит красиво, и даже хотя это выглядит как этих узлов красиво разнесены, в реальности они могут быть где угодно. Ox1, Ox50, Ox123, Ox99, эти узлы могут быть где угодно. Потому таНос делает выделить память из кучи, но в любом месте в куче. Вам не обязательно знать, что это будет спина к спине к спине. И так эта картина в Реальности не собирается быть столь значительной. 

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

Итак, сначала я пойду вперед и объявить узел *. И я буду называть его указатель, только по соглашению. И я собираюсь, чтобы подготовить его к первому. И теперь я могу это сделать В несколькими способами. Но я собираюсь принять общий подход. В то время как указатель не равен нуль, и это допустимый синтаксис. И это как раз означает, выполните следующие действия, так Пока вы не указывая ни перед чем. Что я хочу сделать? 

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

Если я вам найти это, я захочет сделать что-то как сообщить, что мы нашли н. И мы оставим это как комментировать или псевдокод код. Остальное, и вот интересная часть, что я хочу делать, если текущий узел не содержащий п, что я забочусь о? Как мне добиться следующее? Если мой палец на момент PTR, и это указывая на то, что Первый указывая на, как я могу пошевелить пальцем на следующий узел в коде? Ну, что крошка мы собирается следовать в этом случае? АУДИТОРИЯ: [неразборчиво]. David J. МАЛАН: Да, так что в следующий. Так что, если я вернусь в мой Код здесь, действительно, я собираюсь идти вперед и сказать, указатель, который это лишь временное переменная-- это странное имя, PTR, но это просто как temp-- Я собираюсь установить указатель равно какой указателя is-- и опять же, это будет небольшая детская коляска для moment-- точкой следующего. Другими словами, я собираюсь принять мои палец, который, указывая на этом узле здесь, и я собираюсь сказать, вы знаете, что, взгляните на следующее поле и переместить палец в там оно указывая на. И это будет Повторяю, повторять, повторять. Но когда делает свой палец прекратить делать вообще ничего? Как только что строка кода ударов в? АУДИТОРИЯ: [неразборчиво] David J. МАЛАН: Если точка а указатель не равен нулю. В какой-то момент мой пальца будет указывая на нуль и я собираюсь реализовать это конец этого списка. Теперь, это немного ложь для простоты. Получается, что даже при том, что мы только что узнал эту точечную нотацию для структур, указатель не структура. PTR есть что? Просто, чтобы быть более nitpicky. Это указатель на узел. Это не сам узел. Если у меня не было звездой здесь, указатель absolutely-- это узел. Это как недели один Декларация переменной, хотя слово «узел» является новым. 

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

Теперь, для тех из вас, кто возможно, предпочтут по-старому, Вы все еще можете использовать точечной нотации. Но в соответствии с понедельника Разговор, мы сначала должны пойти туда, идти к тому, что решения, а затем перейти в поле. Так что это тоже правильно. И, честно говоря, это немного больше педантичным. Ты буквально говоря, разыменовать указатель и пойти туда. Затем берем .n, поле называется н. Но, откровенно говоря, никто не хочет ввести или прочитать это. И поэтому мир придумал обозначение стрелка, которая эквивалентно, идентичны, это просто синтаксический сахар. Так причудливый способ сказать это выглядит лучше, или выглядит проще. 

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

Так давайте сделаем это. Если вы будете юмор меня здесь, я сделал принести кучу стрессовых шаров. Я принес кучу цифр. И мы могли бы получить только несколько добровольцев представлять 9, 17, 20, 22, 29 и 34? Так по существу все кто здесь сегодня. Это был один, два, три, четыре, пять, шесть человек. И я попросил go-- увидеть, нет один в спину поднимает свои руки. ОК, раз, два, три, четыре, five-- позвольте мне загрузить balance-- шесть. ОК, вы шесть давай до. Мы нужны другие люди. Мы принесли дополнительные шары стресс. И если бы вы могли, для только на мгновение, линия сами до всего любите эту фотографию здесь. 

Хорошо. Давайте посмотрим, как тебя зовут? 

АУДИТОРИЯ: Андрей. 

David J. МАЛАН: Андрей, вы номер 9. Приятно познакомиться. Держи. АУДИТОРИЯ: Джен. David J. МАЛАН: Джен. Дэвид. Номер 17. Да? 

АУДИТОРИЯ: Я Юля. 

David J. МАЛАН: Юлия, Дэвид. Количество 20. АУДИТОРИЯ: Кристиан. David J. МАЛАН: Кристиан, Дэвид. Количество 22. И? 

АУДИТОРИЯ: JP. David J. МАЛАН: JP. Количество 29. Так идти вперед и получить в-- Ой-ой. Ой-ой. В режиме ожидания. 20. Кто-нибудь есть маркер? АУДИТОРИЯ: У меня есть Шулера. David J. МАЛАН: Вы получили шулера? Хорошо. И кто-нибудь есть листок бумаги? Сохраните лекцию. Подойди. АУДИТОРИЯ: У нас есть его. David J. МАЛАН: Мы получили его? Хорошо, спасибо. Здесь мы идем. Был ли этот от вас? Вы просто спасли день. Так 29. Хорошо. Я неправильно 29, но хорошо. Продолжай. Хорошо, я дам вам Ваш перо обратно на мгновение. Поэтому у нас есть эти люди здесь. Давайте один другой. Гейб, ты хочешь играть Первый элемент здесь? Мы нуждаемся в вас, чтобы указать на этих прекрасных людей. Так 9, 17, 20, 22, отсортируйте из 29, а затем 34. Разве мы теряем кого? У меня есть 34. Где did-- ОК, кто хочет быть 34? ОК, давай до, 34. Ладно, это будет стоит кульминация. Как тебя зовут? 

АУДИТОРИЯ: Питер. 

David J. МАЛАН: Питер, давай до. Хорошо, так вот целая куча узлов. Каждый из вас, ребята, представляет один из этих прямоугольников. И Гейб, немного странный человек из, представляет первый. Таким образом, его указатель немного меньше на экране, чем все остальные. И в этом случае, каждый из вашей левой руки собирается либо направлены вниз, тем самым представляя нуль, так только отсутствие указателя, или это собирается быть указывая в узле рядом с вами. 

Так что сейчас, если вы украшают будьте подобны картинке здесь, идти вперед и точка друг на друга, с Gabe в частности, указывая на номер 9 для представления списка. ОК, и число 34, левая рука надо просто указывая на полу. 

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

Ну, номер, который вы пытаетесь вставка, который мы теперь знаем, 55, но если вы не знаете, заранее, я осмелюсь сказать, попадает в по крайней мере трех возможные ситуации. Где может новый элемент быть? АУДИТОРИЯ: И конец или середину. David J. МАЛАН: В конце, в средний, или в начале. Так я утверждаю, что есть по крайней мере три проблемы, которые мы должны решить. Давайте выбирать, что, возможно, возможно простейший один, где новый элемент принадлежит в начале. Так что я буду иметь код довольно как искать, что я только что написал. И я буду иметь PTR, которые Я представляю пальцем, как обычно. 

И помните, какое значение же мы инициализировать указатель на? Таким образом, мы инициализировать его обнулить изначально. Но тогда что же мы делаем, как только мы были в нашем функции поиска? Положим его равным первому, что не означает делать это. Если я устанавливаю PTR равную первой, что должны моя рука действительно указывая на? Право. Так что, если Гейб и я собираемся быть равные значения здесь, мы должны как точки, в число 9. 

Так что это было начало нашей истории. А теперь это просто прямой, несмотря на то, что синтаксис является новым. Концептуально это только линейный поиск. Является 55 равен 9? Вернее, скажем менее 9. Потому что я пытаюсь выяснить, где поставить 55. Менее 9, меньше 17, меньше чем 20, менее 22, менее 29, менее 34, нет. Так что теперь мы в случае один из по меньшей мере трех. 

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

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

АУДИТОРИЯ: Джек. 

David J. МАЛАН: Джек? ОК, приятно познакомиться. Добро пожаловать на борт. Так что теперь мы собираемся вставить, скажем, число 5. Вот второй случай три мы придумали раньше. Так что если 5 принадлежит в начале, давайте посмотрим, как мы видим, что из. Я инициализировать мой PTR указатель на номер 9 снова. И я понял,, о, 5 меньше 9. Так исправить эту картинку для нас. Чьи руки, Гейба или Давида или-- что номер 9 в название? 

АУДИТОРИЯ: Джен. 

David J. МАЛАН: hands-- Джен какие из наших рук нужно изменить? Итак, Гейб указывает на что теперь? У меня. Я новый узел. Так что я просто вид ходу здесь, чтобы посмотреть его визуально. А между тем, что я указать, что? Тем не менее, когда я указываю. Так вот оно что. Так что просто действительно одна строка кода исправления это конкретный вопрос, казалось бы. Ладно, так что это хорошо. А может кто бы это место для 5? Поднимайтесь. Мы тебя в следующий раз. 

Ладно, так now-- и Как в стороне, имена Я не делаю прямого упоминания права Теперь, před указатель, указатель предшественник и новый указатель, это только имена дали в примере кода к указателей или мои руки, это отчасти указывающие вокруг. Как тебя зовут? 

АУДИТОРИЯ: Кристина. 

David J. МАЛАН: Кристина. Добро пожаловать на борт. Ладно, так что давайте рассмотрим сейчас немного больше раздражает сценарий, в результате чего я хочу, чтобы вставить что-то вроде 26 в этом. 20? Что? Эти are-- хорошая вещь у нас есть эту ручку. Ладно, 20. Если кто-то может получить еще один кусок бумага готова, только в case-- все в порядке. О, интересно. Ну это пример лекционного ошибки. Хорошо, таким образом, что тебя зовут? АУДИТОРИЯ: Юлия. David J. МАЛАН: Юлия, вы можете поп , и притворитесь, что вы никогда не были там? ОК, это никогда не происходило. Спасибо. Так что мы хотим вставить Юлия в этот связанного списка. Она является число 20. И, конечно, она собирается принадлежат на begin-- не указывают ни на что еще. Так что ваша рука может отчасти быть вниз нуль или некоторое значение мусора. Давайте говорить короткую историю. Я указываю на 5 на этот раз. Тогда я проверяю 9. Тогда я проверяю 17. Тогда я проверяю 22. И я понимаю,, ох, Юля должен идти до 22. Так что должно произойти? Чьи руки нужно изменить? Джулия, шахта, или-- как тебя зовут? 

АУДИТОРИЯ: Кристиан. 

David J. МАЛАН: христианин или? 

АУДИТОРИЯ: Энди. 

David J. МАЛАН: Энди. Кристиан или Энди? Энди должен указать на? Юлия. Хорошо. Так Энди, ты хочешь, чтобы указать на Джулию? Но подождите минуту. В истории до сих пор, Я-то один отвечает, в том смысле, что указатель является вещь, которая перемещение по списку. Мы можем иметь имя для Энди, но нет переменная называется Энди. Единственный другой переменной у нас есть, первый, кто представлен Гейба. 

Так что это на самом деле, почему таким образом Пока мы не нуждались в этом. Но теперь на экране есть еще раз отметить, из před указателя. Итак, позвольте мне быть более явным. Если это указатель, я должен был лучше получить немного умнее о моем итерации. Если вы не против, что я собираюсь через здесь снова, указывая здесь, указывая здесь. Но позвольте мне есть před указатель, указатель предшественник, это вид указывая на элемент я был просто в. Поэтому, когда я иду сюда, сейчас Моя левая рука обновления. Когда я иду здесь мои левые обновления вручную. И теперь у меня есть не только указатель элемент, который идет после Джулии, Я до сих пор есть указатель на Энди, элемент раньше. Так у вас есть доступ, по существу, панировочных сухарей, если хотите, для всех необходимых указателей. 

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

Теперь, есть, конечно, некоторые другие Операции, которые мы могли бы реализовать. И эти фотографии здесь просто изобразить то, что мы только что сделали с людьми. А как насчет удаления? Если я хочу, например, удалить номер 34 или 55, Я мог бы иметь такой же код, но я буду нуждаться в один или два этапа. Потому что нового? Если я удалю кого в конце, как числа 55, а затем 34, что также должно измениться, как мне это сделать? Я должен не evict-- как тебя зовут? 

АУДИТОРИЯ: Джек. 

David J. МАЛАН: Джек. Я должен не только evict-- бесплатно Джек, так буквально назвать бесплатный Джек, или, по крайней мере, указатель там же, но теперь что необходимо изменить с Петром? Его рука лучше начать вниз. Потому что, как только я звонить бесплатно на Джек, если еще указывает Петра на Джека и я поэтому держите обходе список и доступ этот указатель, вот когда наш старый друг сегментация обвинить действительно может умереть. Потому что мы дали памяти обратно к Джеку. 

Вы можете остаться там неловко на мгновение. Потому что у нас всего пару заключительные операции рассмотреть. Снятие голову списка, или beginning-- и этот сайт немного раздражает. Потому что мы должны знать, что Гейб это своего рода специальное в этой программе. Потому что на самом деле, у него есть своя указатель. Он не просто на которую ссылаются,, как почти все остальные здесь. 

Поэтому, когда глава списка удалены, чьи руки должны изменить сейчас? Как тебя зовут снова? 

АУДИТОРИЯ: Кристина. 

David J. МАЛАН: Я ужасно на имена, по-видимому. Так Кристина и Гейб, чьи руки необходимо изменить когда мы пытаемся удалить Кристину, число 5, от картины? Итак, давайте сделаем Гейб. Гейб собирается указать, предположительно, в доме номер 9. Но что следующий должен произойти? АУДИТОРИЯ: Кристина должна быть пустым [неразборчиво]. David J. МАЛАН: Хорошо, мы должны, вероятно, make-- я услышал "нулевой" где. АУДИТОРИЯ: Null и освободить ее. David J. МАЛАН: Null что? АУДИТОРИЯ: Null и освободить ее. David J. МАЛАН: Null и освободить ее. Так что это очень легко. И это прекрасно, что ты сейчас рода стоять там, не принадлежащие. Потому что вы были отделен от списка. Вы эффективно было сиротами из списка. И таким образом, мы лучше позвонить бесплатно сейчас на Кристин, чтобы дать эту память назад. В противном случае каждый раз, когда мы удалить узел из списка мы могли бы делать список короче, но на самом деле не уменьшается размер в памяти. И поэтому, если мы продолжаем добавлять и добавив, добавление элементов в списке, мой компьютер становится менее эффективным и все медленнее и медленнее, потому что я бегу из памяти, даже если я на самом деле не используя байт Кристины памяти больше. 

Так, в конце есть и другие сценарии, из course-- удаления в средней, удаления в конце, как мы видели. Но тем интереснее Сейчас задача заключается в будет рассматривать именно что время работы является. Так что не только вы можете сохранить ваш бумажек, если, Гейб, вы не возражаете давая каждый мяч стресс. Огромное спасибо нашему связанного списка добровольцев здесь, если бы вы могли. 

[Аплодисменты] 

David J. МАЛАН: Хорошо. Так пару аналитическая вопросы потом, если я мог. Мы видели это обозначение раньше, Big O и омега, верхние границы и нижние границы время работы от некоторого алгоритма. Итак, давайте рассмотрим только пару вопросов. 

Один, и мы сказали, это прежде, чем же работает время поиска Список по большой O? Что верхнюю границу работающем Время поиска связанный список как осуществляется нашими волонтерами здесь? Это большой O н, линейный. Потому что в худшем случае, элемент, как 55, мы могли бы искать может быть там, где Джек был, всю дорогу в конце. И, к сожалению, в отличие от массива мы не можем получить фантазии на этот раз. Даже при том, что все наши люди были отсортированы от небольших элементов, 5, все, вплоть до большего элемента, 55, что, как правило, хорошая вещь. Но то, что делает это предположение больше не позволяют нам делать? АУДИТОРИЯ: [неразборчиво] David J. МАЛАН: снова сказать? АУДИТОРИЯ: Произвольный доступ. David J. МАЛАН: Произвольный доступ. И в свою очередь это означает, что мы можем не больше использовать слабый нули, интуицию, и очевидность используя двоичный поиск и разделяй и властвуй. Потому что даже при том, что мы люди могли, очевидно, видеть, что Энди или христианин были примерно в середине списка, известно лишь, что, как компьютер путем снятия верхнего слоя список с самого начала. Таким образом, мы отказались, что произвольный доступ. 

Настолько большой O п теперь это верхняя граница нашего времени поиска. Как насчет омега нашего поиска? Что нижняя граница по поиску в течение некоторого числа в этом списке? АУДИТОРИЯ: [неразборчиво] David J. МАЛАН: снова сказать? АУДИТОРИЯ: Один. David J. МАЛАН: Один. Так постоянная времени. В лучшем случае, Кристина В самом деле в начале списка. И мы ищем число 5, так что мы нашли ее. Так нет ничего сложного. Но у нее есть, чтобы быть в начало списка в этом случае. Что о чем-то как Удалить? Что делать, если вы хотите удалить элемент? Что верхняя граница и нижняя граница на удалении чего от связаны перечислить? АУДИТОРИЯ: [неразборчиво] David J. МАЛАН: снова сказать? АУДИТОРИЯ: н. David J. МАЛАН: п действительно верхняя граница. Потому что в худшем случае мы стараемся удалить Джек, как мы только что сделали. Он всю дорогу в конце. Принимает от нас навсегда, или п шагов, чтобы найти его. Так вот верхняя граница. Это линейная, уверен. И в лучшем случае время работы, или нижние границы в лучшем случае будет постоянная времени. Потому что, может быть, мы пытаемся удалить Кристин, и мы просто повезти она в начале. Теперь подождите минуту. Гейб также в начале, и мы также должны были обновить Гейб. Так что не было еще один этап. Так это действительно постоянной Время, в лучшем случае, удалить наименьший элемент? Это, несмотря на то, что может быть два, три или даже 100 строк кода, если это то же самое количество линии, не в некоторой петли, и не зависит от размера из списка, абсолютно. Удаление элемента в начало списка, даже если мы имеем дело с Гейб, еще постоянная времени. 

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

АУДИТОРИЯ: Таким образом, вы можете добавить элементы в массив. David J. МАЛАН: Таким образом, вы можете добавлять элементы в массив. И это тоже является тематическим. И мы будем продолжать видеть это, это компромисс, гораздо как мы видели Компромисс с сортировки слиянием. Мы могли бы реально ускорить поиск или сортировки, а, если мы тратим немного больше места и иметь дополнительный кусок памяти или массив для сортировки слиянием. Но мы проводим больше пространство, но мы экономим время. В этом случае, мы отказавшись от времени, но мы обеспечение гибкости, Динамизм, если хотите, которые, возможно, положительная черта. 

Мы также проводить пространство. В каком смысле связаны перечислить дороже с точки зрения пространства, чем массив? Где дополнительное пространство приходят? Да? 

АУДИТОРИЯ: [неразборчиво] указатель. 

David J. МАЛАН: Да, мы также есть указатель. Так что это minorly раздражает в том, что больше не являюсь Я хранения просто Int для представления Int. Я запоминания Int и а указатель, который также 32 бит. Так что я буквально удваивая участие объем пространства. Так вот компромисс, но вот в случае междунар. Предположим, что вы не хранения Int, но предположим, что каждый из этих прямоугольников или каждый из этих людей представлял слово, английское слово, которое может содержать пять знаков, 10 символы, может быть, даже больше. Тогда добавив всего 32 больше битов может быть менее крупной сделки. 

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