[Играет музыка] [ПРОИГРЫВАНИЕ ВИДЕО] -Он лжет. -О чем? -Я не знаю. -Так Что мы знаем? -Это В 9:15, Рэй Сантойя был в банкомате. -Да. Таким образом, вопрос, что он делает в 9:16? -Съемки 9-миллиметрового на что-то. Может быть, он увидел снайпера. -Или Работал с ним. Подожди. Возврат на один. -Что ты видишь? -Bring Его лицом вверх полном экране. -Его Очки. -Есть Это отражение. -Это Бейсбольной команды Nuevitas. Это их логотип. -А Он разговаривает с кто носит эту куртку. [КОНЕЦ ПРОСМОТРА] Дэвид Малан: Ладно. Это CS50 и это немного более из [неразборчиво], с которой вы вмешиваются с проблемой установить четыре. Сегодня мы начинаем выглядеть немного более глубоко в этих вещах, называемых указателей, который, хотя это довольно тайной тема, Оказывается, что он собирается быть средством, с помощью которого мы может начать строительство и монтаж гораздо более сложные программы. Но мы сделали это в последнюю среду посредством некоторого claymation первой. Так что это, напомним, является Бинки, и мы использовали его чтобы взглянуть на программу, которая не действительно что-нибудь интересное, но он раскрыть несколько проблем. Таким образом, чтобы начать сегодня, почему мы не ходить быстро через несколько из этих шагов, попробуйте, чтобы отогнать в условиях человеческий в именно то, что здесь происходит и почему это плохо, а затем перейти на а на самом деле начать строить что-то с этой техникой? Так что это были первый две линии этой программы и с точки зрения непрофессионала, то, что которые эти две линии делают? Кто-то, кто достаточно комфортно с тем, что заявил на экране? Каковы эти две линии делают? Это не все, что отличается от недели один, но есть некоторые новые специальные символы. Да? Вернуться там. АУДИТОРИЯ: Объявление указатели? Дэвид Малан: раз сказать? АУДИТОРИЯ: Объявление указатели? Дэвид Малан: Объявление указатели и давайте уточнить его немного больше. АУДИТОРИЯ: [неразборчиво] адрес, а затем х у. Дэвид Малан: А потом обратиться. Так что конкретно мы делаем что мы объявляем две переменные. Эти переменные, хотя, собираются к типу INT звезды, более конкретно означает они собираются хранить адрес из Int, соответственно, х и у. Теперь есть какие-либо ценности? Есть ли какие-фактический адреса в них две переменные в данный момент? Нет. Это просто так называется значения мусора. Если вы на самом деле не назначать Переменная, все, что было в памяти ранее собирается заполнить нулями и те, оба из этих переменных. Но мы еще не знаем, какие они есть, и это будет ключом к почему Binky потерял голову на прошлой неделе. Так что это был claymation Воплощение этого в результате чего у вас есть только две переменные, маленькие круговые части глины, который может хранить переменные, но, как обернутых стрелки предложить, они на самом деле не указывая в любую точку по себе известны. Итак, мы имели эту линию, и это была новой на прошлой неделе, таНос на память распределение, который является только причудливый способ рассказывать операционную систему Linux, или Mac OS или Windows, Центр эй, дайте мне память, и все, что вы должны сказать операционная система это то, что, когда его просят на память. Это не собирается заботиться, что Вы собираетесь с ним делать, но вы должны сказать операционной Система, что путем таНос. Да? АУДИТОРИЯ: Сколько? Дэвид Малан: Сколько? Насколько в байтах, а это так, то, опять же, надуманный пример, просто говоря, дать мне размер в междунар. Теперь, размером с Int четыре байта или 32 бита. Так что это просто способ говоря, эй, операционная система, дайте мне четыре байта памяти что я могу использовать в моем распоряжении, и, в частности, то, что делает таНос возврат по в этом фрагменте из четырех байтов? АУДИТОРИЯ: Адрес? Дэвид Малан: Адрес. Адрес этой порции из четырех байтов. В точку. И вот что в конечном счете хранится х, и поэтому мы действительно не все равно, что количество, что адрес, будь то OX1 или OX2 или некоторые загадочные адрес шестнадцатеричной. Мы просто заботимся графически что переменная х сейчас указывая на то кусок памяти. Таким образом, стрелка представляет собой указатель или Более конкретно, адрес памяти. Но, опять же, мы обычно не заботятся что эти фактические адреса. Теперь, говорит, что это линия то, что с точки зрения непрофессионала? Звезда х получает 42 с запятой. Что это значит? Ты хочешь идти? Не поцарапать вашу шею. Аудитория: адрес х находится в 42. Дэвид Малан: Адрес х находится в 42. Не совсем. Так близко, но не совсем, потому что есть звезда, которая, предваряя этот х. Таким образом, мы должны настроить немного. Да? АУДИТОРИЯ: Значение, которое Указатель х указывая на это 42. Дэвид Малан: ОК. Значение, указатель х указывая на, скажем, будет 42, или другими словами, звезды х говорит, перейдите к любой адрес в х, будь то 1 Оксфорд Улица или 33 Оксфорд-стрит или OX1 или ox33, независимо что числовое адрес, звездочный х является разыменования х. Так что по этому адресу и Затем положить туда число 42. Так что было бы Эквивалентный способ сказать, что. Так что все нормально, а затем мы будет представлять картину следующим, где мы добавили 42 к этому кусок четырех байты на правой стороне, но Эта линия была, где все пошло наперекосяк и глава Бинки выскочил от в этой точке, потому что плохие вещи случаются, когда Вы разыменования значения для мусора или вы разыменования недействительным указатели, и я говорю недействительным потому что в данный момент в история, то, что находится внутри у? Что значение у на основе на последние несколько шагов? Да? Что это? АУДИТОРИЯ: адрес. Дэвид Малан: адрес. Это должен быть адрес но я ее инициализации? Так что у меня еще нет. Так что, как известно, там? Это просто некоторое значение мусора. Это может быть любой адрес от нуля до 2 млрд, если у вас есть два гигабайтами оперативной памяти, или от нуля до 4 млрд если у Вас есть получил четыре гигабайта оперативной памяти. Это некоторое значение мусора, но проблема в том, что в операционной системе, если он не дал вам что часть памяти специально что вы пытаетесь идти, это вообще будет вызывать что мы видели, как ошибки сегментации. Таким образом, в самом деле, любой из вас, кто боролся на проблемы в рабочее время или в проблемах, которые больше как правило, в попытке выяснить, ошибки сегментации, что обычно означает, ты прикасаешься сегмент памяти, что вы не должны быть. Вы касаясь памяти, операционная система не имеет позволил вам прикоснуться, будь то по заходит слишком далеко в вашем массиве или начиная с сегодняшнего дня, будь это потому, что ты прикасаешься памяти, просто некоторое значение мусора. Так делают звезды х здесь вроде неопределенного поведения. Вы никогда не должны делать это, потому что шансы которые, программа просто будет крах, потому что вы говорите, перейти на этот адрес и вы понятия не имею, где что адрес на самом деле. Таким образом, операционная система, скорее всего, собирается к краху программы в результате и в самом деле, что это что там произошло на Бинки. Так в конечном счете, Бинки фиксированной эта проблема с этим. Так этой программы сам был испорчен. Но если вы как бы продвигаться вперед и выполнить эту строку вместо у равен х просто означает то, что адрес является х, также положить его в у. И так наглядно, мы представлены в этом с двумя стрелками от х и от у указывая в то же место. Так семантически, х равен чтобы у потому что оба из них храните тот же адрес, следовательно, указывая на 42, и теперь, когда вы говорите, звезды у, перейти по адресу в у, это имеет интересный побочный эффект. Таким образом, адрес в у является То же самое, как адрес в х. Так что, если вы говорите, идти по адресу в у и измените значение на 13, кто еще влияет? Х, точка D, так сказать, должны быть затронуты также. И в самом деле, как Ник обратил эту картину в claymation именно это. Даже если мы будем следовать указатель у, мы оказались в том же месте, и поэтому, если мы должны были распечатать из х или pointee Y, в то мы увидели бы значение 13. Теперь, я говорю pointee быть в соответствии с видео. Программисты, на мой знание, на самом деле никогда не говорят слово pointee, что является острым в, но для последовательности с видео, понимают, это все, что было означало в такой ситуации. Так какие-либо вопросы по claymation или указатели или таНос только пока? Нет? Все в порядке. Так что без дальнейшего шума, давайте взглянем в котором это имеет на самом деле были использованы в течение некоторого времени. Таким образом, мы имели эту библиотеку CS50 что есть все эти функции. Мы использовали GetInt много, GetString, вероятно, GetLongLong ранее в моем Pset один или так, но что на самом деле происходит? Ну, давайте взглянем под капотом на программу, которая вдохновляет поэтому мы даем вам CS50 библиотека, и в самом деле, как на прошлой неделе, мы начали принимать тех, учебные колеса от. Так что это теперь сортируются из того, что посмертных имеет уже на в библиотеке CS50, даже если мы теперь начнет двигаться от него для большинства программ. Так что это программа называется зсапЕ 0. Это супер короткий. Это просто есть эти строки, но это вводит функцию называют зсапЕ что мы на самом деле происходит, чтобы видеть в момент внутри библиотеки CS50, хотя и в несколько иной форме. Так что это программа на линии 16 объявляет переменную х. Так дайте мне четыре байта для Int. Это было рассказывать пользователю, Количество пожалуйста, а затем это интересно, что линия на самом деле связывает прошлой неделе и это. Scanf, и обратите внимание на то, что занимает Строка формата, как Printf, % я означает Int, а затем она занимает Второй аргумент, который выглядит немного фанки. Это амперсанд х, и вспомнить, мы видели только один раз на прошлой неделе. Что амперсанд х представляют? Что делать в амперсанд C? Да? Аудитория: адрес. Дэвид Малан: Адрес. Так это наоборот звездного оператора, в то время как звезда оператор говорит, перейдите к этот адрес, амперсанд оператор говорит, выяснить адрес этой переменной, и таким образом это является ключевым, потому что Цель Scanf в жизни это для сканирования пользователя ввести с клавиатуры, в зависимости от все, что он или она типы, а затем читать ввод данного пользователя в переменную, но мы видели в последние две недели что эта функция подкачки, что мы пытался усилий для реализации просто разбиты. Напомним, что с функцией подкачки, если мы только что объявили А и В, целых чисел, мы действительно успешно своп две переменные внутри своп просто нравится с молоком и OJ, но как только вернулся подкачки, какой был результат по х и у, оригинальные значения? Ничего. Да. Ничего не произошло, что время, потому что свопы изменить только свои локальные копии, который должен сказать, все на этот раз, всякий раз, когда мы в были передавая аргументов к функциям, мы просто проходя копии этих аргументов. Вы можете делать с этим что вы хотите с ними, но они собираются иметь не Влияние на исходные значения. Так что это проблематично, если вам хотите иметь функцию, как зсапЕ в жизни, цель которого состоит в сканировании вход пользователя с клавиатуры а затем заполнить пробелы, так говорят, что это, дают переменную х, как значение, потому что, если бы я был просто передать х в Scanf, если вы считаете, логику в прошлом неделю, зсапЕ может делать все, что он хочет с копией х, но она не могла навсегда изменить х, если мы не дадим Scanf карту сокровищ, так сказать, где х обозначает место, в результате чего мы проходим в адрес х, так что зсапЕ можете пойти туда и фактически изменение значение х. И так действительно, все что эта программа делает если я зсапЕ 0, на мой источника Каталог 5м, сделать зсапЕ 0, точка слэш зсапЕ, номер пожалуйста, 50, спасибо за 50. Так что это не все, что интересно, Но то, что действительно происходит является то, что, как только я называю Scanf здесь, значение х в настоящее время постоянно изменяется. Теперь, это, кажется, хороший и хорошо, а на самом деле, это Похоже, мы действительно не нужно библиотека CS50 вообще больше. Например, давайте работать это еще раз здесь. Позвольте мне открыть его в течение секунды. Давайте попробуем номер, пожалуйста, и вместо того чтобы сказать 50, как раньше, давайте просто сказать нет. ОК, это немного странно. ХОРОШО. И лишь некоторые ерунда здесь. Так что, кажется, не обрабатывать ошибочные ситуации. Таким образом, мы должны минимально старт добавив некоторые проверки ошибок чтобы убедиться, что пользователь имеет напечатана в фактическое количество как 50, потому что очевидно набрав слов не обнаружено проблематичным, но это, вероятно, должно быть. Давайте посмотрим на эту версию теперь это моя попытка переопределить GetString. Если зсапЕ все это имеет Функциональность встроенная, почему мы были с ними баловаться учебные диски, как GetString? Ну, вот, пожалуй, моя собственная простая версия GetString в результате чего неделю назад, я бы сказал дать мне строку и называют это буфер. Сегодня, я собираюсь начать только говоря сЬаг звезды, который, напомним, это просто синонимы. Это выглядит страшнее, но это точно такая же вещь. Так дайте мне переменной называется буфер что собирается хранить строку, скажите пожалуйста, строку пользователя, а затем, как и прежде, давайте попробуем занять этот урок зсапЕ % s это время, а затем передать в буфере. Теперь, быстрая проверка здравомыслие. Почему я не говорю, амперсанд буфер на этот раз? Вывод из предыдущего примера. АУДИТОРИЯ: Чар звезда указатель. Дэвид Малан: Ровно, потому что это время, гольца звезда уже указатель, адрес, по определению этой звезды быть там. И если зсапЕ ожидает адрес, достаточно лишь пройти в буфере. Мне не нужно, чтобы сказать, амперсанд буфер. Для любопытных, вы могли бы сделать что-то вроде этого. Это будет иметь другое значение. Это даст вам указатель на указатель, который на самом деле действительный вещь в C, но для Теперь, давайте держать его проста и держать историю в соответствии. Я просто хочу, чтобы передать в буфер и это правильно. Проблема, однако, заключается в следующем. Позвольте мне идти вперед и работать в этом Программа после компиляции. Сделать зсапЕ 1. Черт возьми, мой компилятора ловить свою ошибку. Дайте мне одну секунду. Clang. Скажем Scanf-1.c. ХОРОШО. Там мы идем. Мне это нужно. CS50 ID имеет различные Параметры конфигурации что защитит вас от себя. Мне нужно отключить те, по работает лязг вручную в этот раз. Так строка пожалуйста. Я собираюсь идти вперед и ввести в моем любимом мире привет. ОК, нуль. Это не то, что я набрал. Так что это свидетельствует о то ошибиться. Позвольте мне идти вперед и ввести в самом деле длинной строки. Благодарность за нуль, и я не знаю, если я собираюсь быть в состоянии разбить его. Давайте попробуем немного копию вставить и посмотреть, если это помогает. Просто вставьте многое из этого. Это, безусловно, больше Строка, чем обычно. Давайте просто действительно написать его. Нет. Блин. Команда не найдена. Так вот не связаны. Это потому, что я вставил некоторые плохие персонажи, но это оказывается не будет работать. Давайте попробуем это еще раз, потому что это более интересно, если мы на самом деле крах его. Давайте печатаю это, и теперь, я собирается копировать действительно длинную строку а теперь давайте посмотрим, если мы может привести к сбою эту вещь. Обратите внимание, я опустил пространства и новые линии и точки с запятой и все непонятные символы. Войти. И теперь в сети просто быть медленным. Я держал вниз Command-V слишком долго, ясно. Блин! Команда не найдена. ХОРОШО. Ну, дело в том, тем не менее, после. Так что на самом деле происходит с этой декларацией Чар звезд буфера на линии 16? Так что я получаю Когда я объявляю указатель? Все, что я получаю значение байта четыре называемая буферная, но то, что внутри него в данный момент? Это просто некоторое значение мусора. Потому любое время вы объявляете переменную в C, это просто некоторое значение мусора, и мы начинаем Поездка по этой реальности. Теперь, когда я говорю зсапЕ, перейти на этот адрес и положить все типы пользователей в. Если пользователь в привет Мир, ну, куда я положил его? Буфер значение мусора. Так что вроде как стрела который, указывая, кто знает, где. Может быть, это указывает прямо здесь, в моей памяти. И поэтому, когда пользователь типы в мире, здравствулте! программа пытается поставить Строка привет мир обратный слеш 0 в этом куске памяти. Но с большой долей вероятности, но явно не 100% вероятность, компьютер будет крах, то Программа, потому что это не памяти я должен быть позволено прикоснуться. Короче говоря, эта программа недостатки именно по этой причине. Я принципиально не делает? Какие шаги я опущены, как мы опустили с первого примера Бинки? Да? АУДИТОРИЯ: распределение памяти? Дэвид Малан: распределение памяти. Я на самом деле не выделены любая память для этой строки. Таким образом, мы можем исправить это в несколько способов. Один из них, мы можем сохранить его простым и в самом деле, теперь ты собирается начать видеть размывание линий между тем, что Массив, то, что строка является, то, что символ звезда, какая массив символов является. Вот второй пример с участием струнных и уведомления Все, что я сделал на линии 16, вместо того чтобы сказать что буфер будет символ звезда, указатель на кусок памяти, Я собираюсь очень активно дают сам буфер 16 символов, и в самом деле, если вы знакомы с термином буферизации, вероятно, из мира видео, где видео буферизации, буферизация, буферизации. Ну, какая связь здесь? Ну, внутри YouTube и внутри видеоплееров как правило, представляет собой массив это больше, чем 16 лет. Это может быть массив размера одного мегабайт, может быть, 10 мегабайт, и в этом массиве делает ваш браузер скачать целую кучу байтов, целая куча мегабайт видео, и видео-плеер, YouTube, или кто бы ни, начинается читать байты из этого массива, и в любое время вы видите Слово буферизации, буферизация, это означает, что игрок имеет дошли до конца массива. Сеть настолько медленно, что это не имеет наполнил массив с более байт и так вы из битов для отображения пользователю. Так буфера является удачный термин здесь в том, это просто массив, кусок памяти. И это будет исправить потому что это оказывается что вы можете обращаться массивы, как будто они адреса, даже если буфер это просто символ, это последовательность символов, буфер это полезно для меня, программист, Вы можете передать свое имя вокруг как если бы это были указатель, как бы это были также адрес кусок памяти для 16 символов. Так вот, чтобы сказать, что я могу пройти зсапЕ именно это слово и теперь, если я эту программу, сделать зсапЕ 2, точка слэш зсапЕ 2, и введите в привет мир, Введите, что time-- Хм, что случилось? Строка пожалуйста. Что я сделал не так? Привет мир, буфер. Привет мир. Ах, я знаю, что он делает. ХОРОШО. Так что читает до до первого пробела. Так что давайте обмануть на мгновение и сказать, что я просто хотел, чтобы что-то типа действительно долго, как это длинное предложение это одна, две, три, четыре, пять, шесть, семь, восемь, девять, 10, 11, 12, 13, 14, 15, 16. ХОРОШО. Это действительно длинное предложение. Таким образом, это предложение является больше, чем 16 символов и поэтому, когда я ударил Enter, Что должно случиться? Ну, в этом случае из история, я объявил буфер на самом деле является массив с 16 символы готов к работе. Так один, два, три, четыре, пять, шесть, семь, восемь, девять, 10, 11, 12, 13, 14, 15, 16. Так 16 символов, и теперь, когда я читать что-то, как это долго Приговор, что произойдет в что я собираюсь читать в это долго S-Е-Н-Т-Е-Н-С-Е, предложение. Так что это намеренно плохо, что я продолжать писать за пределами Границы моего массива, за пределами моего буфера. Я мог бы получить повезло, и программа будет продолжать работать и не волнует, но, вообще говоря, это действительно крах мою программу, и это ошибка в моем код момент, когда я шаг за границы из этого массива, потому что я не знаю, если это обязательно врежется или если я просто хочу, чтобы повезти. Так что это проблематично, потому что в этот случай, он, кажется, работают и давайте искушать судьбу здесь, хотя интегрированная среда, кажется, терпеть совсем немного of-- Там мы идем. В заключение. Так что я единственный, кто может это увидеть. Так что я просто было много веселья, набрав из очень долгое фактической фразу что это, конечно, превысило 16 байт, потому что я набрали в этом сумасшедшем длительного мульти-линии Фраза, и обратите внимание на то, что произошло. Программа пыталась его печати а затем получил ошибку сегментации и ошибки сегментации, когда что-то подобное и операционная система говорит нет, не могут прикоснуться к памяти. Мы собираемся, чтобы убить Программа в целом. Таким образом, это представляется проблематичным. Я улучшил программу, посредством которой по крайней мере, есть память, но это, казалось бы ограничиться функция GetString, чтобы получить струны некоторой конечной длины 16. Так что, если вы хотите поддерживать больше приговоры, чем 16 символов, чем занимаешься? Ну, вы можете увеличить Размер этого буфера до 32 или, что кажется отчасти коротким. Почему бы нам не просто сделать это 1000, но отодвинуть. Что ответ интуитивно из просто избежать этой проблемы путем мой буфер больше, как 1000 символов? Реализуя GetString этот путь. То, что хорошо или плохо здесь? Да? АУДИТОРИЯ: Если вы связывать много пространства, и вы не используете его, то вы не можете перераспределить это пространство. Дэвид Малан: Совершенно верно. Это расточительно, поскольку, если вы не на самом деле нужно 900 байт из этих и еще вы просите 1000 в общей сложности в любом случае, вы просто потреблять больше памяти на компьютер пользователя, чем нужно, и в конце концов, некоторые из Вы уже встречались в жизни, что, когда вы работает множество программ и что они едят до много памяти, это действительно может повлиять на производительность и опыт пользователя на компьютере. Так что вроде ленивый решение, наверняка, и, наоборот, это не только расточительно, то, что проблема по-прежнему остается, даже если я могу сделать мой буфера 1000? Да? Аудитория: строка длиной 1,001. Дэвид Малан: Точно. Если строка длиной 1001, у вас есть точно такой же проблемой, и мой аргумент, я бы только затем сделать его 2000 но вы не знаете, в заранее, насколько большой это должно быть, и все же, я должен собрать свою программу прежде чем дать людям использовать и скачать Это. Так что это именно то, вещи, которые библиотека пытается CS50 чтобы помочь нам с, и мы будем только взгляд на некоторые из базовой реализации здесь, но это CS50 точка С. Это это файл, который был на CS50 IDE все эти недели, что вы используете. Это предварительно составлен и у Вас есть использует его автоматически по характеру, имеющий тире L CS50 флаг с лязгом, но если я прокрутите вниз через все эти функции, вот GetString, и просто чтобы дать вам вкус того, что происходит, давайте быстрый взгляд на относительную сложность. Это не супер долго Функция, но мы не сделали должны думаю, что все трудно о как идти о получении строк. Итак, вот мой буфер, и я по-видимому, его инициализации до нуля. Это, конечно, является То же самое, как полукокса звезды, но я решил в реализации библиотеки CS50 что если мы собираемся полностью динамический, Я не знаю, заранее, насколько велика в строка пользователи будут хотите получить. Так что я собираюсь начать только с пустой строкой и я собираюсь построить столько памяти, как мне нужно, чтобы соответствовать строку пользователя и если я не достаточно, я попрошу операционная система для получения дополнительной памяти. Я собираюсь переместить их строку в больший кусок памяти и я собираюсь выпустить или освободить недостаточно большой кусок памяти и мы только собираемся сделать это многократно. Таким образом, быстрый взгляд, вот только переменной с которой я иду, чтобы отслеживать емкости моей буфера. Сколько байт я могу соответствовать? Вот переменная п с который я буду держать трек сколько байт на самом деле в буфер, или что пользователь ввел. Если вы не видели это раньше, вам можно указать, что переменная, как Int без знака, который, как следует из названия, означает, что это не-отрицательным, а почему бы Я когда-либо хотел беспокоить уточнением что INT это не просто INT, но это беззнаковое INT? Это неотрицательная Int. Что означает [неразборчиво] в виду? АУДИТОРИЯ: Это описании количество памяти, который может быть [неразборчиво]. Дэвид Малан: Да. Так что, если я говорю без знака, это на самом деле давая вам один бит дополнительной памяти и, кажется, глупо, но если вы есть один бит дополнительной памяти, что означает, что вы должны в два раза больше значения можно представить, потому что это может быть 0 или 1. Так, по умолчанию, целочисленное может быть примерно отрицательное 2 млрд весь путь до положительного 2 млрд. Те большие диапазоны, но он по-прежнему вид расточительно если вы только заботиться о размеры, которые просто интуитивно не должны быть отрицательными или положительное или 0, ну а потом, почему вы тратите 2 млрд Возможные значения для отрицательных чисел если вы никогда не собираетесь их использовать? Так, говоря без знака, теперь моя Int может быть между 0 и примерно 4 млрд. Так вот просто INT C по причинам, мы не сможем получить в сейчас, как почему это целочисленное вместо из гольца, но вот суть того, что происходит на, и некоторые из вас могут использовать, например, fgetc функция даже в четыре Pset или после того, что мы увидим его снова в задаче установить пять, fgetc приятно, потому что, как имя вид, вроде arcanely предполагает, это функция, которая получает характер и поэтому, что принципиально отличается о том, что мы делаем в GetString это мы не используем зсапЕ таким же образом. Мы просто ползет шаг за шагом в течение любого пользователь ввел в, потому что мы всегда можем выделить один символ, и таким образом, мы всегда можем смело смотреть в одну гольца в то время, и магия начинает происходить здесь. Я собираюсь прокрутите вниз до середина этой функции просто кратко представить эту функцию. Многое, как есть Функция таНос, есть функция Realloc где Realloc позволяет вам перераспределить часть памяти и сделать его больше или меньше. Так Короче говоря, и с волна моей стороны на сегодняшний день, знаю, что GetString делает это своего рода магически растет или сокращается буфер как пользователь типы в его или ее строки. Так что, если пользователь вводит Короткая строка, этот код только выделяет достаточно памяти, чтобы соответствовать строку. Если пользователь хранит ввод как я сделал это снова и снова и снова, и, если буфера первоначально этот большой и программа реализует, чтобы погоди, я из космоса, это собирается удвоить размер буфера и затем два раза размер буфера и код, который делает удвоение, если мы посмотрим на него здесь, это только эта умная один вкладыш. Вы, возможно, не видел этот синтаксис раньше, но если вы говорите, звезды равна, это то же самое, говоря раз Вместимость 2. Так он просто продолжает удвоение емкость буфера а затем рассказывать Realloc дать Сам, что гораздо больше памяти. Теперь, как в сторону, там другие функции в здесь что мы не будем смотреть в детали кроме как показать в GetInt, мы используем GetString в GetInt. Мы проверяем, что это не NULL, который, напомним, это специальное значение, что означает что-то пошло не так. Мы из памяти. Лучше проверить это. И мы возвращаем значение дозорного. Но я отложить на комментарии относительно того, почему, а затем мы используем эту двоюродный брат зсапЕ называется sscanf и получается, что sscanf, или строка зсапЕ, позволяет вам взглянуть на линии, пользователь ввел в вас, и пусть проанализировать его по существу и то, что я делаем здесь, я говорю sscanf, проанализировать все пользователь набрали в и убедитесь,% I, существует целое число в нем, и мы не будем попасть в сегодня точно, почему есть также A% C здесь, но в двух словах позволяет нам обнаружить, если пользователь ввел в чем-то фиктивные после номера. Так что причина, что GetInt и GetString сказать вам, чтобы повторить попытку, повторите, повторите попытку из-за всех что код, который мы написали, это своего рода взгляд на входе пользователя в убедившись, что он полностью цифровая Это или это реальная плавающей значение точки и т.п., в зависимости от того, какой величины функционировать вы используете. Вот так. ХОРОШО. Это был глоток но дело здесь что причина у нас было эти учебные диски по в том, что на самом низком уровне, Есть только так много вещей, которые может пойти не так, что мы хотели превентивно обрабатывать эти вещи, конечно, в Первые недели класса, но теперь с Pset четыре и пять, и Pset за вы увидите, что это больше к Вы, но и вы более способны решения этих проблем виды сам. Любые вопросы по GetString или GetInt? Да? АУДИТОРИЯ: Почему бы вам удвоить емкость буфера а не просто увеличение это по точной суммы? Дэвид Малан: Хороший вопрос. Почему мы вдвое емкость буфера, в отличие просто увеличивая его некоторой постоянной величины? Это было дизайнерское решение. Мы просто решили, что, потому что это, как правило, быть немного дороже времени мудро спросить операционная система на память, мы не хотите в конечном итоге получить в ситуация для больших строк что мы просили ОС снова и снова и снова, и снова в Быстрая смена на память. Таким образом, мы просто решили, несколько произвольно, но мы надеемся, что разумно, что, вы знаете, что, давайте попытаться получить впереди себя и просто продолжать удваивать его так, что мы минимизируем количество раз мы должны называть таНос или Realloc, но в общей сложности суд назвать в отсутствие зная то, что пользователи, возможно, захотите, чтобы ввести в. Оба способа могут быть спорным. Возможно хорошо. Итак, давайте взглянем на пару других побочных эффектов памяти, вещи, которые могут пойти не так и инструменты, которые вы можете использовать, чтобы поймать эти виды ошибок. Оказывается все из вас, даже если check50 не сказал вам, как много, пишу багги Код, поскольку недели один, даже если все тесты являются check50 прошло, и даже если вы и ваш TF супер уверены, что Ваш код работает, как предполагалось. Ваш код был багги или недостатки в том, что все из вас, при помощи библиотеки CS50, были утечки памяти. Ты спрашивал операционную систему на память в большинстве программ Вы написали, но вы никогда не возвратила его. Вы назвали GetString и GetInt и GetFloat, но с GetString, вы, никогда не называл unGetString или Дайте Строка Назад или т.п., но мы видели, что делает GetString выделить память путем таНос или это Функция Realloc, который находится всего очень похожи по духу, и все же, мы были просить операционную систему для память и память снова и снова но никогда не давая его обратно. Теперь, как в сторону, то получается, что когда программа завершает работу, вся память автоматически освобождается. Таким образом, это не было огромное дело. Это не собирается сломать IDE или медленно вещи вниз, Но когда программы не как правило, утечка памяти и они работают в течение длительного времени. Если вы когда-либо видели глупая маленькая пляжный мяч в Mac OS или песочные часы В Windows, где это вид замедление или думать или думать или просто действительно начинает чтобы замедлиться, очень возможно, может быть результатом утечки памяти. Программисты, которые писали программное обеспечение вы используете просить операционную систему для памяти каждые несколько минут, каждый час. Но если вы выполнив Программное обеспечение, даже если это свести к минимуму в вашем компьютере в течение нескольких часов или дней подряд, Вы могли бы просить больше и больше памяти и никогда не использовать его на самом деле и так что ваш код может быть, или программы могут быть утечка памяти, и если вы начинаете утечка памяти, есть меньше памяти для других программ, и эффект в замедлить все вниз. Теперь, это, безусловно, один из Наиболее жестокие программы Вы будете иметь возможность работать в той CS50 а его выход еще более эзотерическая, чем лязг Или сделать или любой команды Программы линии мы запускаем раньше, но К счастью, встроенные в его выходе это некоторые супер полезные советы, что будет полезна как для Pset четыре или, конечно, Pset пять. Так Valgrind является инструментом который может быть использован, чтобы посмотреть утечек памяти в вашей программе. Это относительно просто работать. Вы запускаете Valgrind, а затем, даже хотя это немного многословен, тире проверка утечка тире равна полной, а затем точка слэш и имя вашей программы. Так Valgrind будет запустить программу и в самом конце своей программы работает, прежде чем он уходит и дает вам еще подскажите, он собирается для анализа Программа пока она бежала и сказать, что ты вы утечка любая память и еще лучше, ты Touch Memory, что не принадлежит вам? Он не может поймать все, но это очень хорошо при ловле большинство вещей. Так вот пример моей пробежав эта программа, пробежав Valgrind, на программу под названием памяти, и я собираюсь выделить строки, которые в конечном счете, представляет для нас интерес. Так что еще больше отвлекаться что я удален из слайда. Но давайте посмотрим, что это Программа способна сказать нам. Он способен рассказывать нам вещи как недействительной записи размером 4. Другими словами, если вы касаетесь память, в частности 4 байт памяти что вы не должны иметь, Valgrind могу сказать вам, что. Неверный записи размером 4. Вы затронули четыре байта что вы не должны иметь. Где ты это сделал? Это красота. Точка памяти с линии 21, где вас облажались, и именно поэтому это полезно. Многое, как GDB, он может помочь указать вам на ошибки фактического. Теперь, этот немного больше многословен, если не путаю. 40 байт 1 блоков, безусловно, потеряли в потере записи 1 из 1. Что это значит? Ну, это просто означает, что вы просили 40 байт и ты никогда не дал его обратно. Вы назвали таНос или вы назвать GetString и операционная система не дал вам 40 байт, но вы никогда не освобождены или освобождены, что память, и быть справедливыми, мы никогда не показываем Вы, как отдать память. Оказывается, есть супер простая функция называется свободным. Принимает один аргумент, вещь Вы хотите, чтобы освободить или отдать, но 40 байт, по-видимому, в этой программе были потеряны в строке 20 памяти точка гр. Итак, давайте посмотрим эту программу. Это супер бесполезно. Это только демонстрирует это конкретная ошибка. Итак, давайте взглянем. Вот основные и главные, уведомление, звонки функция называется F, а затем возвращается. Так что не все, что интересно. Что е делать? Обратите внимание, я не стал с прототипом. Я хотел, чтобы сохранить код как можно меньше. Так что я положил п выше основной и это нормально, конечно, для коротких программ, как это. Так е ничего не возвращает и делает не взять что-нибудь, но это сделать. Это заявляет, подобно в примере Binky, указатель называется х, что происходит хранить адрес в междунар. Так вот левая сторона. В английском языке, что является Правая делать? Кто угодно? Что это делает для нас? Да? АУДИТОРИЯ: [неразборчиво] раз размер с Int что в 10 раз больше, чем [неразборчиво] Дэвид Малан: Хорошо, и позвольте мне подвести итог. Так выделить достаточно места для 10 чисел или 10, что размером с Int, это четыре байта, поэтому в 10 раз 4 40, так что с правой стороны, что я выделенный это дать мне 40 байт и сохранить адрес первого байта в х. А теперь, наконец, и вот, где эта программа глючит, что так с линии 21 на основе этой логики? Что случилось с линией 21? Да? АУДИТОРИЯ: Вы не можете индекс в х [неразборчиво]. Дэвид Малан: Да. Я не должен индекс в х, как, что. Так синтаксически, это нормально. Что приятно, так же, как вам может относиться к имени массива как будто это указатель, аналогично Вы можете лечить указатель как будто это массив, и поэтому я могу синтаксически говорят что-то х кронштейн, кронштейн х я, но 10 является проблематичным. Зачем? АУДИТОРИЯ: Потому что это не внутри. Дэвид Малан: Это не внутри этого куска памяти. Что наибольшее значение я должен класть в этих квадратных скобках? До 9 9, 0. Из-за нулевой индексации. Так от 0 до 9 будет в порядке. Кронштейн 10 не хорошо, и но, напомним, однако, каждый раз, Я, кажется, чтобы попытаться сделать CS50 IDE аварии, набрав в фиктивных ценностей, это не всегда сотрудничать, и, действительно, часто повезет только потому, что Операционная система не Вы заметите, что чуть-чуть пройти некоторое кусок памяти, потому что вы остались в технически Ваш сегмент, но об этом в классе операционных систем, и так что-то вроде этого может очень легко остаться незамеченными. Ваша программа никогда не будет врезаться последовательно, но, возможно один раз в некоторое время. И так давайте попробуем Valgrind на это, и вот где мы перегружены по выходе на мгновение. Так что проверку на утечку памяти Valgrind равна полной памяти точка слэш. И вот почему я обещаю это сокрушить. Вот то, что Valgrind, вот что программист, несколько лет ago- решил, что это будет хорошая идея, для выхода выглядеть. Итак, давайте разобраться в этом. Так всю дорогу на левой сторона без уважительной причины идентификатор процесса программы мы просто запустить, уникальный идентификатор для программы мы просто бежали. Мы удалили, что с слайд, но это некоторая полезная информация здесь. Давайте прокрутки до самого верха. Вот где мы начали. Так что это не все, что многое выход. Вот, что пишут недействительным размер 4 на линии 21. Ну, то, что было 21 линия? Линия 21 была точно это и есть смысл что я нахожусь в валидно писать 4 байта, потому что я пытаются поставить этот целое, который может быть что угодно, это просто происходит, чтобы быть нулю, но я пытаюсь положить его на месте что не принадлежит мне. Более того, здесь, 40 байт в одном блоки, безусловно, потерял в записи 1. Это потому, что, когда я называю таНос здесь, я никогда не освободит память. Так как мы можем это исправить? Позвольте мне идти вперед и быть немного безопаснее и делать там 9, и пусть меня здесь бесплатно X. Это новая функция на сегодняшний день. Если сейчас я повторно сделать точечный памяти черту, давайте работать Valgrind на него снова, увеличить мое окно и нажмите Enter. Теперь, это хорошо. Они хоронят хорошие новости всего этого выхода. Все блоки кучи были свободны. Мы вернемся к тому, что кучи есть, но никаких утечек не возможно. Так что это просто еще один инструмент для вашего набора инструментов с которой вы можете начать сейчас найти ошибки, как, что. Но давайте посмотрим, что более может пойти не так здесь. Давайте переход сейчас на самом деле решить проблему. Как в стороне, если это избавит немного путаницы или напряженности, теперь это смешно. Да. Это очень хорошо. Потому что указатели адреса и адреса как правило, по соглашению написано шестнадцатеричном виде. Ха-ха, это смешно сегодня. Во всяком случае, так что давайте прямо сейчас на самом деле решить проблему. Это было супер, супер низкого уровня до сих пор, и мы можем на самом деле полезно вещи с этих низкоуровневых деталей. Таким образом, мы ввели несколько недель назад понятие массива. Массив был хорош, потому что трудно очистить наш код потому что, если мы хотели, чтобы написать Программа с несколькими студентами или несколько имен и дома, и общежития и колледжей, и все, что, мы могли бы хранить все более чисто внутри массива. Но предложить один недостаток массива до сих пор. Даже если вы не страдали сами в программе, просто инстинктивно, то, что это плохо о массиве, может быть? Я слышал некоторые шумы. АУДИТОРИЯ: Это сложно изменить размер. Дэвид Малан: Трудно изменить размер. Вы не можете изменить размер массива, на самом деле, как таковые в C. Вы можете выделить еще один массив, переместить все от старого в новое, и в настоящее время есть некоторое дополнительное пространство, но это не как язык, как Java или Python или любое количество других языки, с которыми некоторые из вас может быть знаком где вы можно просто продолжать добавлять вещи тошноты до конца массива. Если у вас есть массив Размер 6, то есть его размер, и так много, как раньше идея имеющие буфер определенного размера, вы должны догадаться из ворот какой размер вы хотите быть? Если вы угадаете слишком большой, вы тратите пространство. Если вы угадаете слишком мал, вам не может хранить эти данные, по крайней мере, без много работы. Таким образом, сегодня благодаря указателей, мы можем начать шить вместе наш собственный обычай структуры данных, и в То, здесь что-то что выглядит немного больше загадочные на первый взгляд, но это то, что мы называем связаны Список, и его имя рода суммирует Это. Это список чисел, или в этот случай, список номеров, но это может быть список что-нибудь, но это связано вместе путем стрелок, и просто сделать предположение с тем, что техника мы собираемся, чтобы иметь возможность сшить вместе, вроде попкорна с резьбой, связанный списки прямоугольники здесь? Его номера? Что функция основной язык? АУДИТОРИЯ: Указатель. Дэвид Малан: Указатель. Таким образом, каждый из этих стрел здесь представляет указатель или просто адрес. Итак, другими словами, если я хочу хранить список номеров, Я не могу просто хранить его, если я хочу способность увеличиваться и уменьшаться мой структура данных в массиве. Поэтому мне нужно, чтобы иметь немного более изысканность, но заметить, что это картина вид предполагает что если вы только что получили маленькие темы подключения все вместе, вероятно, это не так сложно сделать пространство между двумя этими прямоугольниками или два из этих узлов, как мы начнем называя их, положить в новый узел, а затем с какой-то новой нити, просто канаву три узла вместе, первый, последний, и тот, что вы только что вставили в середину. И действительно связанный список, в отличие от массива, является динамическим. Он может расти и может сокращаться и вы не должны знать, или ухода заранее, как много данных вы собираетесь быть хранения, но, оказывается, мы должны быть немного осторожны о том, как осуществить это. Итак, сначала давайте рассмотрим, как мы реализуем один из этих маленьких прямоугольников. Это легко реализовать Int. Вы просто говорите Int N, а затем Вы получаете 4 байта для Int, но как я могу получить Int, назовем его N, а затем указатель, давайте называть его рядом. Мы могли бы назвать это вещи все, что мы хотим но мне нужно структуру пользовательских данных. Да? АУДИТОРИЯ: Амперсанд [неразборчиво]. Дэвид Малан: Так амперсанд мы будем использовать для получить адрес узла потенциально. Но нам нужен еще Функция С в порядок чтобы дать мне возможность создавать этот обычай прямоугольник, этот обычай Переменная, если хотите, в памяти. Зала: структура. Дэвид Малан: а структурой. Напомним, на прошлой неделе, мы ввели структура, это относительно простое ключевое слово, что позволяет нам сделать такие вещи, как это. С не пришел с данным Структура называется студента. Он поставляется с Int и плавать и гольца и например, но он не приходит со студентами, но мы можем создать тип данных студентом, студент структура, с этим синтаксисом Вот. И вы увидите, что это снова и снова. Так что не беспокойтесь о запоминания слов, но ключевое слово, что это важно, только тот факт, что мы сказали, структура и тогда мы называли это студент и внутри студента было имя и дом или общий номер или тому подобное. И так вот сегодня, давайте предлагать это. Я добавил несколько слов, но если я хочу осуществить этот прямоугольник, что это получил одновременно Int и А указатель, вы знаете, что я собирается объявить на структуру под названием узел. Я также, внутри него, хочу сказать, что узел, этот прямоугольник, имеет Int и мы будем называть его п и она имеет следующий указатель. И это немного многословен, но если вы думаете об этом, стрелки, которые были на картинке момент назад, какого типа данных? Где каждый из этих стрелок указывает какой тип структуры данных? Это не указывая только на междунар на себе. Это указывает на Вся прямоугольная вещь и что прямоугольная вещь, мы сказали, называется узлом. И таким образом, мы отчасти должны рекурсивно определить это такое что узел, мы будем говорить, будет содержать Int под названием п и указатель называется рядом и тип структуры данных, к которым что указатель указывает, по-видимому будет структура узла. Так что это досадно, многословным и просто быть педантичным, причина, почему мы не можем просто сказать, что это, что, честно говоря выглядит намного более читаемым, потому, что напомним, что C чтения вещи сверху вниз, слева направо. Это не пока мы не получим точку с запятой что узел ключевое слово на самом деле существует. Так что, если мы хотим иметь такую циклический ссылки внутри данных Структура, что мы должны сделать это, когда мы говорим структуры узла в верхней части, которая дает нам длинный путь описания этого вещь, то внутри мы говорим структуры узла, а затем в самый последний линии мы говорим, все в порядке, С, кстати, просто позвоните весь этот проклятый что узел и остановить используя ключевое слово-структуру в целом. Так что это просто своего рода синтаксический Хитрость в конечном счете, позволяет, что нам создать то, что выглядит так же, как это. Так что, если мы предположим теперь, мы можем реализовать эту вещь в C, Как мы на самом деле начать обход этого? Ну, в самом деле, все, что мы должны сделать, это итерации слева направо и просто вид вставить узлы или удалять узлы или искать вещи там, где мы хотим, но чтобы сделать это, давайте идти вперед и сделать вещи немного более реальным, потому что это был супер низкого уровня до сих пор. Кто буквально хотели бы быть первым? ХОРОШО. Давай до. Как тебя зовут? Дэвид: Дэвид. Дэвид Малан: Дэвид. Приятно познакомиться. Я тоже. Все в порядке. И нам понадобится ряд 9. Не так хорошо, как во-первых, возможно. ОК, номер 9. Ряд 17, пожалуйста. Позвольте мне вернуться немного дальше. Количество 22, пожалуйста, и как о дальше назад если я вижу каких-либо руки со всеми света или нет. Кто-то вызвался быть прямо там. Вы хотите, чтобы придумать? Ваше предплечье принудительно идет вверх. ОК, 17. 22. 26 спускается. Кто-то еще хотели бы forcefully-- Давай до. Фактический общественных началах. Так очень быстро, если вы, ребята, могли бы организовать сами просто хотел узлы на экране. Спасибо. И вы будете 26. Все правильные и быстрые введения. Так что я Дэвид, и вы также? Дэвид: Дэвид. Дэвид Малан: А вы? Джейк: Джейк. ГУП: Сью. АЛЕКС: Алекс. РАФАЭЛЬ: Рафаэль. Тейлор: Тейлор. Дэвид Малан: Тейлор. Отлично. Таким образом, эти наши волонтеры сегодня и идти вперед и сдвиг мало что путь, и просто идти вперед и держать проведение ваши номера, как вы или ваши Первый признак и левой рукой, идти вперед и просто реализовать эти стрелки, только так что ваша левая рука буквально указывая на то, что вы должны указать на, и дать себе некоторую комнату так, что мы можем наглядно увидеть ваши руки на самом деле указывая, и вы можете просто указать рода на землю в порядке. Так вот у нас есть связанный список одного, два, три, четыре, пять узлов на начальном этапе, и обратите внимание, у нас есть эта специальная указатель на начало, кто ключевым, потому что мы должны отслеживать из всего списка длины каким-то образом. Эти ребята, даже если они остаются направо, спиной к спине в памяти, они действительно могут быть в любом месте в памяти компьютера. Таким образом, эти ребята могли бы быть стоя на любом этапе и это нормально, так долго, как они на самом деле, указывая друг на друга, но держать вещи чистый и простой, мы будем просто обратить их слева направо, как это, но не может быть массивные промежутки между этими узлами. Теперь, если я хочу на самом деле вставить некоторые новое значение, давайте идти вперед и делать это. У нас есть возможность в настоящее время выбрать другой узел. Скажите давайте начнем с mallocing 55. Будет ли кто-против того таНос? ОК, давай до. Как тебя зовут? РАДУГА: Радуга. Дэвид Малан: Радуга? Все в порядке. Маллок Радуга. Давай до. Так что теперь мы должны спросить себя, алгоритмически, где мы можем поставить 55. Таким образом, все мы знаем,, очевидно, где она, вероятно, принадлежит, если мы пытаемся чтобы эта сортируются и если вы, ребята, может принять одно шаг назад, поэтому мы не упасть этап, что было бы здорово. Так на самом деле, Радуга, начать здесь со мной, потому что мы, как компьютер теперь может увидеть только одну переменную одновременно. Таким образом, если это первый узел. Обратите внимание, что он не является узлом, он просто указатель, и вот почему он обращается, чтобы быть только размер указателя, а не один из тех полных прямоугольников. Итак, мы собираемся, чтобы проверить друг на итерация 55 меньше, чем 9? Нет. Есть 55 меньше 17? Нет. Менее 22? Менее 26? Менее 34? И вот теперь, очевидно, Радуга принадлежит в конце. Таким образом, чтобы было ясно, и то, что был ваше имя, Тейлор? Тейлор: Тейлор. Дэвид Малан: Так среди Тейлор левая рука и руки радуги здесь, Чья рука должна указывать на то, что в Чтобы вставить 55 в этом списке? Что нам нужно сделать? Да? АУДИТОРИЯ: ручная Тейлора нужно указать левой. Дэвид Малан: Точно. Так вставке узла в конце списка довольно просто, потому что Тейлор просто должен указывать, а не на земле или мы будем называть его пустым, нуль является своего рода отсутствие указателя или специальный нулевой указатель, вы будем показывать с левой руку на Радуга Радуга, а затем, где, если ваш левый рука, вероятно, указывают? Вниз. Это не хорошо, если ее рука вроде указывать здесь или от своего рода любой каким образом. Это будет рассматриваться значение мусора, но если она указывает на некоторые известные значение, мы будем называют его нулю или нулевой, это нормально потому что у нас в этом термин и мы знаем, что список в настоящее время завершена. Так что еще один относительно простой случай? Можем ли мы таНос 5? Давай до. Как тебя зовут? Тиффани: Тиффани. Дэвид Малан: Я извиняюсь? Тиффани: Тиффани. Дэвид Малан: Тиффани. Все в порядке. Тиффани была malloced со значением 5. Давай до. Этот сравнительно легко слишком, но давайте рассмотрим порядок операций в настоящее время. Это было довольно легко с Тейлором в конце. Номер 5, конечно, меньше, чем 9, и поэтому мы должны Давида, у нас есть Тиффани, и то, что было ваше имя? Джейк: Джейк. Дэвид Малан: Джейк. Тиффани, Джейк, и Дэвид. Чья рука должна быть обновлена ​​в первую очередь? Что вы хотите сделать здесь? Там есть пара возможных путей, но есть также один или более неправильные способы. АУДИТОРИЯ: Начните с крайнего левого. Дэвид Малан: Начните с крайнего левого. Кто крайний левый здесь тогда? АУДИТОРИЯ: Во-первых. Дэвид Малан: ОК. Так что начните с первой и где вы хотите обновить руки Давида, чтобы быть? АУДИТОРИЯ: К 5. Дэвид Малан: ОК. Давид, точка, в пяти или Тиффани здесь, а сейчас? АУДИТОРИЯ: Тиффани указывает на 9? Дэвид Малан: Совершенно, за исключением того, Бинки Глава только вид упал, не так ли? Потому что то, что случилось с эта картина буквально? АУДИТОРИЯ: Ничто не указывает. Дэвид Малан: Ничто не является указывая на Джейка в настоящее время. Мы буквально осиротел 9 и 17, и мы буквально утечка вся эта память, потому что обновления руку Давида первых, это в порядке, поскольку это правильно указывая на Тиффани сейчас, но если никто не имел предусмотрительно указывают на Джейка, Затем мы потеряли Совокупность этого списка. Итак, давайте отменить. Так что это хорошая вещь, чтобы споткнуться, но давайте исправим настоящее. То, что мы должны сделать в первую очередь, а? Да? АУДИТОРИЯ: Тиффани должна указывать на 9? Дэвид Малан: я не могу получить так близко к вам. Кто должен указать на 9? АУДИТОРИЯ: Тиффани. Дэвид Малан: Ладно. Так Тиффани должна первая точка на 9. Так Тиффани должны принять на одинаковым значением Давиду, который, кажется, излишним на мгновение, но это нормально, потому что теперь, во-вторых шаг, мы можем обновить руку Давида чтобы указать на Тиффани, а затем, если мы только отчасти очистить вещи как будто это своего рода весны-как, вот это правильный вставки. Так отлично. Так что теперь мы почти там. Давайте вставить один финал значение как значение 20. Если бы мы могли таНос один заключительный добровольцем? Давай до. Так что это одно немного сложнее. Но на самом деле, код мы писать, хотя и в устной форме, это все равно, что кучу из, если условия сейчас, верно? Мы имели состояние проверки, если он принадлежит В конце концов, может быть, с самого начала. Мы должны некий цикл в найти место в середине. Так давайте сделаем это с тем, что ваше имя? ЭРИК: Эрик. Дэвид Малан: Эрик? Эрик. Приятно познакомиться. Итак, мы имеем 20. Менее пяти? Нет. Менее девяти? Нет. Менее 17? Нет. ХОРОШО. Он принадлежит здесь и Ваши имена снова есть? ГУП: Сью. Дэвид Малан: Сью. АЛЕКС: Алекс. Дэвид Малан: Сью, Алекс, а? ЭРИК: Эрик. Дэвид Малан: Эрик. Чьи руки должны получить обновление в первую очередь? АУДИТОРИЯ: Эрик. ХОРОШО. Так Эрик должен указать на то, где? В 22. Хорошо. А теперь, что будет дальше? Сью может указывать на Эрика и теперь, если вы, ребята, просто потесниться, который прекрасен визуально, теперь мы сделали вставку. Так пусть теперь рассмотрим вопрос, но спасибо так много для наших волонтеров. Очень хорошо сделано. Вы можете сохранить те, если вам нравится. И у нас есть прекрасный подарок, если прощальный вы каждый хотел взять стресс мяч. Позвольте мне передать это вниз. Так что вынос это? Это, кажется, удивительно поскольку мы имеем сейчас представила альтернативой Массив, который не так ограничены на массив некоторого фиксированного размера. Они могут расти динамически. Но так же, как мы видели в течение нескольких недель прошлое, мы никогда не получим ничего бесплатно, как, безусловно, есть компромисс здесь. Так с потенциалом роста связанный Список, это динамизм? Эта способность расти и, честно говоря, мы могли бы сделать удаления и мы могли бы сжать по мере необходимости. Какую цену мы платим? В два раза больше пространства, в первую очередь. Если вы посмотрите на картину, больше не я хранить список целых чисел. Я хранения списка целые плюс указатели. Так что я удвоение количества пространства. Теперь, может быть, это не такая большое дело 4 байта, 8 байт, но это, безусловно, может добавить на больших наборов данных. Что другой недостаток? Да? АУДИТОРИЯ: Мы должны пройти их один за одним. Дэвид Малан: Да. Мы должны пройти их один за одним. Вы знаете, что мы отказались от этой супер удобная функция квадратного кронштейна обозначения, более правильно известный как произвольного доступа, где мы можем просто прыгнуть к отдельному элементу но теперь, если я до сих пор мои добровольцы здесь, если бы я хотел, чтобы найти № 22, я не могу просто перейти к кронштейн-то что-то. Я должен смотреть на список, много как наши примеры поиска линейно, чтобы найти номер 22. Таким образом, мы, кажется, заплатили цену там. Но, тем не менее, мы можем решить другие проблемы. На самом деле, позвольте мне представить только пару визуальные эффекты. Так что, если вы были до Столовая Mather недавно, вы помните, что их стеки подносов, как это, мы позаимствовали их из Анненберга перед классом. Таким образом, это стопка тарелок, хотя, является представителем на самом деле структуры данных компьютерной науки. Существует структура данных в информатике Известно, как стек, который очень красиво поддается именно это визуально. Таким образом, если каждый из этих лотков не лоток, но, как и ряд, и я хотел для хранения номера, я может поставить один здесь, и я мог бы поставить другой сюда, и продолжить укладку число на верхней части друг друга, и то, что потенциально полезным об этом это то, что это подразумевается этой структуры данных? Какое число я могу вытащить в первую очередь наиболее удобно? Наиболее недавно выразился один там. Так что это то, что мы называем в информатика структура данных ЛИФО. Последний пришел, первый. И мы увидим, в скором времени, почему что может быть полезным, но сейчас, просто рассмотреть собственность. И это отчасти глупо, если вы думаете, о том, как столовая это делает. Каждый раз, когда они чистые лотки и положить свежие из них на вершине, вы могли бы ранее чистая но в конце концов очень грязный и пыльный лоток на самом дне если вы на самом деле никогда не попасть в нижней части, что стек, потому что вы просто держать положить новый и чистые те, на вершине этого. То же самое может случиться в супермаркете тоже. Если у вас есть витрину молока и каждый раз CVS или тот, кто получает больше молока, вы просто засунуть молоко у вас уже есть на спине и Вы помещаете новые впереди, Вы будете иметь некоторые довольно противно Молоко в конце структуры данных, потому что это всегда на дне или что то же самое, это всегда на спине. Но есть еще один способ думать о выстраиваются данных и, например, этот. Если вы один из тех людей, кто любит выстраиваться за пределами Apple, магазины когда новый продукт поставляется из, вы, вероятно, не используя данные стека Структура, потому что вы оттолкнет всех, кто находится выстраиваются, чтобы купить некоторые новые игрушки. Скорее всего, вы, вероятно, с использованием какие структуры данных или какая система в реальном мире? Надеюсь, это линия, или более правильно или более британский, как, очереди. И получается, очередь также Структура данных в информатике, но очередь имеет очень отличается свойство. Это не ЛИФО. Последний пришел, первый. Не дай Бог. Это вместо того, чтобы FIFO. Первым прибыл, первым обслужен. И это хорошо Справедливости ради конечно, когда вы выстраиваются до супер рано утром. Если вы там сначала, Вы хотите, чтобы выйти сначала в качестве хорошо. И так все эти данные структуры, очереди и стеки и гроздья других, оказывается вас может думать об этом, как только что массив. Это массив, может быть, фиксированный размер 4, но это было бы быть своего рода хорошо, если мы могли бы просто куча Лотки почти бесконечно высокий, если мы есть, что многие подносы или цифры. Так, может быть, мы хотим, чтобы использовать связанный список здесь, но компромисс будет потенциально, что нам нужно больше памяти, занимает немного больше времени, но мы не ограничивают высоту стопки, так же, как витрине Мазера может ограничить размер стека, и таким образом, они проектные решения или варианты, доступные для нас в конечном счете. Так что с этими данными структуры, мы начали видя новые верхние границы потенциально на то, что ранее было супер быстро и где мы оставим от сегодня и где мы надеемся получить в на среду, мы будем начать смотреть на данных Структура, что позволяет нам искать через данные в конце времени журнала снова. И мы увидели, что, помню, в нулевой неделе и один с бинарного поиска или разрыва и властвуй. Это возвращается, и еще лучше, Святой Грааль для этого среду будет придумать с структура данных, которая работает действительно или теоретически Постоянная времени, в результате чего это не имеет значения, сколько миллионы или миллиарды вещей мы имеем в структуре данных, это будет взять нас постоянное время, может быть, один шаг или два шага или 10 шагов, но постоянные числа шагов искать в этой структуре данных. Это действительно будет Святой Грааль но об этом в среду. Увидимся тогда. [Играет музыка]