[Powered by Google Translate] [4-я неделя] [David J. Малан] [Harvard University] [Это CS50.] [CS50.TV] 

Все правильно, это CS50, и это начало недели 4, и это одна из самых медленных возможные алгоритмы сортировки. Какой это был, что мы просто смотрели туда? Это было пузырьковой сортировки, для того, большая O (N ^ 2) + сумма, да и мы не единственные в этом мире, чтобы, кажется, знают что пузырь сортировки или время его работы. Действительно, это было интервью с Эриком Шмидтом из Google и бывший сенатор Барак Обама всего лишь несколько лет назад. 

Теперь, сенатор, вы здесь, в Google, и мне нравится думать президентства, как собеседование. Теперь, трудно устроиться на работу в качестве президента, и вы собираетесь через суровые сейчас. Это также трудно устроиться на работу в Google. У нас есть вопросы, и мы просим наших кандидатов вопросы, и это одна из Ларри Швиммер. Вы, ребята, думаете, я шучу? Это прямо здесь. Какой самый эффективный способ сортировки миллионов 32-разрядных целых чисел? [Смех] Ну- Мне очень жаль. >> Нет, нет, нет, нет. Я думаю, что пузырьковой сортировки бы неправильный путь. 

Ну, кто сказал ему об этом? На прошлой неделе помните, мы взяли перерыв с кодом, по крайней мере, на один день, и начал упором на более высоком уровне идей и решения проблем в более общем в контексте поиска и сортировки, и мы ввели то, что мы не шлепать это имя на прошлой неделе, но асимптотические обозначения, Big O, Большой Omega, , а иногда и большую обозначения Theta, и они были просто способы описания времени работы алгоритмов, Сколько времени требуется для алгоритма для запуска. 

А вы помните, что вы говорили о времени работы с точки зрения размера на входе, который мы обычно называем п, что проблема может быть, где п-количество людей в комнате, Количество страниц в телефонной книге, и мы начали писать вещи как O (N ^ 2) или O (п) или O (п § п), и даже когда математика не совсем выработать так прекрасно и это был п ² - п / 2 или что-то вроде того вместо этого мы будем просто выбросить некоторые из младших членов, и мотивация есть то, что мы действительно хотим рода объективный способ оценки выполнение программы или выполнение алгоритмов что в конце дня не имеет ничего общего, например, со скоростью компьютера сегодня. 

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

Мы приступили к п § п, и снова, Напомним, что журнал п как правило, относится к тому, что растет медленнее, чем я, так что п § п до сих пор было хорошо потому что это было меньше, чем ² н. Но для достижения п п войти с сортировки слиянием то, что было основной росток идея, что мы должны были использовать что мы также использовала еще в недели 0? Как мы будем решать задачи сортировки умно с сортировки слиянием? Что было ключевым пониманием, что ли? Любой вообще. Хорошо, давайте сделаем шаг назад. Опишите сортировки слиянием в свои слова. Как это работает? Хорошо, мы будем грести обратно в неделю 0. Хорошо, да. [Неразборчиво-студент] Ладно, хорошо, так что мы разделили массив чисел на 2 части. Мы отсортировали каждой из этих частей, и тогда мы объединили их, и мы видели эту идею до принятия Проблема вот эта большая и измельчение его в проблему, вот эта большая или это большое. 

Напомним, например, телефонную книгу. Напомним, самостоятельного подсчета алгоритм из недели назад, так сортировки слиянием были подведены итоги этого псевдокод здесь. Когда вам дают п элементов, сначала это была проверка исправности. Если п <2, то ничего не делаем на всех потому что, если п <2, то п, очевидно, 0 или 1, и поэтому, если это 0 или 1 нет ничего, чтобы отсортировать. Вы сделали. Ваш список уже тривиально отсортированы. Но в противном случае, если у вас есть 2 или более элементов, идти вперед и разделить их на 2 половины, слева и справа. Сортировка каждой из этих половин, а затем объединить отсортированы половины. Но проблема здесь в том, что на первый взгляд это выглядит, как будто мы понтировавшего. Это круговая определения в том, что, если я попросил вас разобраться этих п элементов и ты говоришь мне "Ладно, хорошо, мы разберемся тех, п / 2 и тех, п / 2 элементов" Затем мой следующий вопрос будет "Хорошо, как вы сортировать п / 2 элементов?" 

Но из-за структуры этой программы, потому что это базовый вариант, так сказать, это особый случай, который говорит, что если п <некоторое фиксированное значение, как 2 возвращение немедленно. Не отвечать с той же круговой ответ. Этот процесс, эта цикличность в конечном счете закончится. Если я спрошу тебя "Сортировка этих п элементов", и вы говорите: "Хорошо, отсортировать п / 2" Затем вы говорите: "Хорошо, род этих п / 4, п / 8, n/16" в конечном итоге вы будете делить на достаточно большое число что вы будете иметь только 1 элемент влево, и в этот момент можно сказать, "Вот, вот отсортированы одного элемента." Тогда блеск этого алгоритма здесь является вывод из того факта, что, как только у Вас есть все эти отсортирован списки, все из которых имеют размер 1, который, кажется, бесполезно, как только вы начинаете их слияние и объединение их Вы сформируете, наконец, как Роб сделал в видео, наконец, отсортированный список. 

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

Давайте посмотрим, если мы можем сделать простой, банальный пример, скажем, 3 человека со мной здесь, на сцене, если кто-то это удобно. 1, давай вверх, 2 и 3. Если вам 3 хотят приехать сюда. Если вы хотите стоять рядом со мной здесь, в линию, предположим, что проблема под рукой очень тривиально подсчитать количество людей, которые находятся здесь. Но, откровенно говоря, я устал от всех этих подсчета примеров. Это займет некоторое время, 1, 2, и точка, точка, точка. Это будет длиться вечно. Я бы предпочел просто Пунт этой проблемы в целом с помощью, как тебя зовут? Сара. >> Сара, все в порядке. Келли. >> Келли и? 

Вилли. >> Вилли, Сара, Келли, и Вилли. Сейчас я задал вопрос кто-то сколько людей на этом этапе, и я понятия не имею. Это очень длинный список, и поэтому вместо этого я буду делать этот трюк. Я собираюсь попросить человека рядом со мной, чтобы сделать большую часть работы, и как только она делается делают большую часть работы Я собираюсь сделать наименьшее количество работ можно и просто добавить 1 к тому, что ее ответ, так что здесь мы идем. Я спросил, как много людей на сцене. Сколько человек на сцену, чтобы слева от вас? Слева от меня? >> Хорошо, но не обманывают. Это хорошо, это правильно, но если мы хотим продолжить эту логику Давайте предположим, что вы так же хотите, чтобы выбивать из рук эту проблему слева от вас, Таким образом, вместо ответа напрямую идти вперед и просто сваливать. Ах, как много людей находятся слева от меня? Сколько людей налево? 1. [Смех] Итак, 0, так что теперь Вилли сделал это ты вернулся ваш ответ этому направлению говоря 0. Итак, что вы должны сделать? >> 1. Итак, вы 1, так вы говорите: "Ладно, я собираюсь добавить 1 к тому, что количество Вилли было ", так что 1 + 0. Вы сейчас 1 так что ваш ответ на правом теперь- 1. >> А моя будет 2. Хорошо, так вы принимаете предыдущий ответ 1, добавив минимальное количество работы, которую вы хотите сделать, что является +1. Теперь у вас есть 2, а затем вы передать мне, какое значение? 3, я имею в виду, извините, 2. Хорошо. 

Ну, у нас было от 0 до левого. Тогда у нас была 1, а затем мы добавляем 2, и теперь вы вручая мне номер 2, и поэтому я говорю, ладно, +1, 3. Там в самом деле 3 человек стоял рядом со мной на этой сцене, таким образом, мы могли бы, очевидно, сделал это очень линейно, очень очевидным образом, но что мы действительно делаем? Мы взяли проблеме размером 3 на начальном этапе. Затем мы сломали его на проблеме размер 2, Затем проблема размер 1, и, наконец, базовый сценарий действительно, ой, там никого нет, в этот момент Вилли вернулся эффективно жестко ответить пару раз, , а второй затем пропускают до пузырьками, вверх, вверх пузырьками, , а затем, добавив в этот дополнительный 1 мы реализовали эту основную идею рекурсии. 

Теперь, в данном случае это действительно не решить проблему любой более эффективно то, что мы видели до сих пор. Но думать об алгоритмах мы сделали на сцене до сих пор. У нас было 8 листов бумаги на доске, на видео, когда Шон искал номер 7, и что он реально сделать? Ну, он не делал любые разделяй и властвуй. Он не сделал любой рекурсии. Скорее, он просто сделал это линейный алгоритм. Но когда мы предложили идею отсортированы номера на сцене живут на прошлой неделе Затем у нас был этот инстинкт собирается к середине, в этот момент у нас было меньше списке размере 4 или другой список размере 4, а потом у нас была точно такая же проблема, поэтому мы повторили, повторяется, повторяется. Другими словами, мы рекурсия. Большое спасибо нашему 3 добровольцев здесь для демонстрации рекурсии с нами. 

Давайте посмотрим, если мы не можем сделать этого сейчас немного более конкретным, решения проблемы, что опять мы могли бы сделать довольно легко, но мы будем использовать его как трамплин для осуществления этой основной идеи. Если я хочу, чтобы вычислить суммированием кучу цифр, Например, если вы проходите в число 3, Я хочу дать вам значение сигма-3, так что сумма 3 + 2 + 1 + 0. Я хочу получить обратно ответ 6, таким образом, мы будем реализовывать эту функцию сигма, эта функция суммирования что, опять же, берет на входе, а затем возвращает суммирования из этого числа вплоть до 0. Мы могли бы сделать это довольно просто, не так ли? Мы могли бы сделать это с какой-то цикл структуры, так что позвольте мне идти вперед и получить эту работу. 

Включить stdio.h. Позвольте мне получить себе в основную работу с здесь. Давайте сохраним это как sigma.c. Тогда я пойду сюда, и я собираюсь объявить Int N, и я собираюсь сделать следующее, пока пользователь не сотрудничают. Пока пользователь не дал мне положительного числа Позвольте мне идти вперед и побудить их к GetInt п =, и позвольте мне дать им инструкции относительно того, что делать, так что Е ("Положительное целое, пожалуйста»). Просто что-то относительно простое, как это так, что к тому времени мы попали линия 14 у нас теперь есть натуральное число, вероятно, в с. 

Теперь давайте что-то делать с этим. Позвольте мне идти вперед и вычислить суммы, так Int сумма = сигма (п). Sigma просто суммирование, так что я просто пишу это в причудливые пути. Мы просто называем это сигма там. Это сумма, и теперь я собираюсь распечатать результат, Е ("Сумма% г \ п", сумма). И тогда я буду возвращать 0 для хорошей мерой. Мы сделали все, что эта программа требует, кроме интересной части, которая является на самом деле реализации сигма функции. 

Отпусти меня сюда на дно, и позвольте мне объявить функцию сигма. Это должно принимать переменное, что это типа целое число, и какой тип данных, я хочу, чтобы вернуться предположительно от Sigma? Int, потому что я хочу, чтобы соответствовать моим ожиданиям по линии 15. В здесь, позвольте мне пойти дальше и реализовать эту В довольно простым способом. 

Давайте пойдем дальше и сказать Int сумма = 0, и теперь я собираюсь немного цикла здесь что собирается сказать что-то вроде этого, для (INT = 0; I <= номер, я + +) Сумма + = я. А потом я собираюсь вернуть сумму. Я мог бы осуществляться этом в любом количестве способами. Я мог бы использовать цикл. Я мог бы пропустить с помощью суммы переменной, если я действительно хотел, но в общем, мы просто есть функция, которая, если я не лох заявляет сумма равна 0. Затем он перебирает от 0 на вверх через номер, и на каждой итерации он добавляет, что текущее значение суммы, а затем возвращает сумму. 

Так вот, есть небольшая оптимизация здесь. Это, наверное, зря шаг, но пусть будет так. Это хорошо на данный момент. Мы по крайней мере быть тщательным и собирался 0 все пути вверх. Не очень жесткий и довольно проста, но оказывается, что с помощью функции сигма мы имеем те же возможности как мы сделали здесь, на сцене. На сцене мы просто посчитал, сколько людей было рядом со мной, но вместо этого, если мы хотим подсчитать число 3 + 2 + 1 на до 0, мы могли аналогичным плоскодонки к функции что я буду описывать, а не как рекурсивные. Вот давайте сделаем быстро здравомыслие проверить и убедиться, что я не лох. 

Я знаю, что есть по крайней мере одна вещь в этой программе, что я сделал неправильно. Когда я попала ввести я собираюсь получить любую кричать на меня? Что мне будет кричать на о? Да, я забыл прототип, поэтому я использую функцию под названием Sigma в строке 15, но это не объявлены, пока линия 22, так что я лучший активно идут сюда и объявить прототип, и я скажу Int сигма (внутр номер), вот и все. Он реализован в нижней части. 

Или другой способ я могу решить эту проблему, Я мог бы переместить функцию там, наверху, который не плох, но по крайней мере, когда ваши программы начинают получать длинный, откровенно говоря, Я думаю, что есть некоторое значение в всегда с основными в верхнем так что вы у читателя может открыть файл, а затем сразу же увидеть то, что делает программа, без необходимости искать через него ищет, что основной функцией. Пойдем в мой окне терминала здесь, попробуйте сделать сигма сделать сигма, и я облажался здесь. Неявная декларация функции GetInt означает, что я забыл сделать то, что еще? [Неразборчиво-студент] Хорошо, таким образом, по-видимому распространенная ошибка, так давайте это здесь, cs50.h, а теперь давайте вернемся к моему окне терминала. 

Я буду очистить экран, и я буду повторно сделать сигма. Мне кажется, собрали. Позвольте мне теперь работать сигма. Я введите номер 3, и я получить 6, так что не строгая проверка, но по крайней мере, кажется, работает на первый взгляд, но теперь давай рвать его на части, и давайте на самом деле опираются на идею рекурсии, опять же, В очень простых условий, с тем, что в течение нескольких недель когда мы начинаем изучать любитель структур данных, чем массивы у нас есть еще один инструмент в инструментарии, с которым манипулировать этими данными структурами, как мы увидим. Это итеративный подход, цикл подхода. 

Позвольте мне вместо этого теперь сделать это. Позвольте мне сказать, что вместо суммирования числа на до 0 на самом деле то же самое, Число + сигма (количество - 1). Другими словами, так же, как на сцене, я плыла по течению, чтобы каждый из людей рядом со мной, а они, в свою очередь, держали понтировавшего, пока мы, наконец, дна на Вилли, , которые должны были вернуться жестко ответить, как 0. Вот теперь мы так же понтировавшего сигма те же функции, изначально называлась, но ключ понимания здесь то, что мы не призываем сигма одинаково. Мы не проходящая на русском языке. Мы четко проходящей в номер - 1, так что немного меньше проблем, немного меньше проблем. 

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

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

Исправление в том, что мы не можем просто слепо вернуться сигма, Число + сигма немного меньше проблем. Мы должны иметь какое-то основание в данном случае, и что должно базовый вариант, вероятно, будет? [Неразборчиво-студент] Итак, если число является положительным, мы фактически должны вернуть это, или, другими словами, если число, скажем, <= 0, Вы знаете, что я буду идти вперед и возвращать 0, так же, как Вилли сделал, и еще, я собираюсь идти вперед и вернуть эту, так что это не то, что намного короче, чем итерационные версии, что мы на скорую руку сначала с помощью цикла, но обратите внимание, что есть такая элегантность к нему. Вместо возвращения некоторого числа и выполнения всей этой математике и добавление вещи с локальными переменными Вы вместо того, говоря: "Хорошо, если это супер легкая задача, как число <0, позвольте мне немедленно вернуть 0 ". 

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

Другими словами, есть способ в настоящее время перевода это реальная конструкция мира, это более высокий уровень конструкции разделяй и властвуй и делать что-то снова и снова В коде, так это то, что мы увидим снова в течение долгого времени. Теперь, как и в сторону, если вы новичок в рекурсии вы должны по крайней мере, понять сейчас почему это смешно. Я собираюсь пойти на google.com, и я буду искать какие-то советы и рекомендации по рекурсию, введите. Расскажите человек рядом с вами, если они не смеялись только сейчас. Вы имели в виду рекурсии? Вы имели в виду-а-а, вот так. Хорошо, теперь вот остальные каждого. Немного пасхальное яйцо встроенных где-то там, в Google. Как в сторону, одной из ссылок мы ставим на сайте курса на сегодняшний день является только эта сетка различных алгоритмов сортировки, некоторые из которых мы посмотрели на прошлой неделе, но то, что хорошо об этом визуализация как вы пытаетесь обернуть ваш разум вокруг различных вещей, связанных с алгоритмами знаю, что вы можете очень легко начинать с различными типами входов. Входы все вспять, входы основном сортируется, случайные входы и так далее. Как вы пытаетесь, опять же, различать эти вещи в своем уме понимаю, что это URL на веб-сайте курса на лекции страницу может помочь вам причину через некоторые из них. 

Сегодня мы, наконец, получить, чтобы решить эту проблему некоторое время назад, которых было то, что эта функция подкачки просто не работает, и то, что основная проблема с этой функцией подкачки, целью которой было, опять же, для обмена значение здесь и здесь такое, что это происходит? Это на самом деле не работают. Почему? Да. [Неразборчиво-студент] Точно, объяснение этому грубых ошибок Просто потому, что когда вы вызываете функции в C и эти функции принимают аргументы, как и б здесь, Вы передаете в копии какое бы значение вы предоставляете к этой функции. Вы не предоставления исходных значений себе, таким образом, мы видели это в контексте buggyc, buggy3.c, который выглядел немного что-то вроде этого. 

Напомним, что у нас было х и у инициализируются 1 и 2, соответственно. Затем распечатать то, что они были. Я тогда утверждал, что я был заменяя их по телефону своп х, у. Но проблема в том, что замена работал, но только в рамках своп самой функции. Как только мы попали линия 40 местами эти значения были выброшены на свалку, а так ничего В исходной функции основного был на самом деле изменилась, поэтому, если вы считаете, тогда как, в какой это выглядит с точки зрения нашей памяти если это левая сторона платы представляет собой- и я сделаю все возможное, чтобы все видели это, если это левая сторона платы представляет, скажем, ваша память и стек будет расти на эту образом, и мы вызываем функцию как основного, а главное есть 2 локальные переменные х и у, Давайте описывать их как х здесь, и опишем, как у этих здесь, и давайте в значения 1 и 2, так что здесь главный, и когда основной вызывает функцию подкачки операционной системы дает функцию подкачки свою полосу памяти в стеке, своих кадров в стеке, так сказать. Он также выделяет 32 бит для этих целыми. Это происходит называть их А и Б, но это совершенно произвольными. Это могло бы назвал их, что хочет, но то, что происходит, когда основной звонки своп он принимает это 1, помещает копию там, помещает копию там. 

Существует 1 другие локальные переменные в подкачки, однако, то, что называется? >> Tmp. Tmp, поэтому позвольте мне дать себе еще 32 бита здесь, и что же мне делать в этой функции? Я сказал Int TMP получает, таким образом, имеет 1, так что я сделал это, когда мы в последний раз играли с этим примером. Тогда б получает, таким образом, б = 2, так что теперь это становится 2, и теперь б получает временный, так что температура равна 1, так что теперь это становится б. Это здорово. Это сработало. Но тогда, как только функция возвращает памяти свопа эффективно исчезает, так что его можно использовать повторно некоторые другие функции в будущем, а главное, очевидно, совершенно не изменился. Нам нужен способ принципиально решить эту проблему, и сегодня мы, наконец, есть способ сделать это посредством чего мы можем ввести так называемый указатель. Получается, что мы можем решить эту проблему Не переходя в копии х и у но вместо этого, передав в чем, как вы думаете, в своп функции? Да, насчет адреса? Мы еще не говорили об адресах очень подробно, но если эта доска представляет памяти моего компьютера Мы, безусловно, может начать нумерацию байт в моей памяти и говорят, что это байт № 1, это байт № 2, № 3 байта, № 4 байта, байт # ... 2 миллиардов, если у меня есть 2 гигабайта оперативной памяти, таким образом, мы, безусловно, может выступить с некоторыми произвольной схемы нумерации для всех отдельных байтов в памяти моего компьютера. 

Что, если вместо этого, когда я называю своп , а не пропуск в копии х и у почему бы мне не пройти, а не в адрес х здесь, адрес у здесь, по существу, почтовый адрес, х и у, потому что тогда поменяться, если он проинформировал адреса в память о х и у, Затем поменяться, если мы обучили его немного, Он потенциально может ездить по этому адресу, так сказать, х, и изменить номер есть, то ехать в адрес у, изменить номер есть, даже если на самом деле не получает копии этих значений себе, так что даже если мы об этом говорили как основной памяти в и это как своп-памяти мощная и опасная часть C является то, что любая функция может коснуться памяти где-нибудь в компьютер, и это мощный в том, что вы можете сделать очень модные вещи с компьютерными программами на языке C. Это опасно, потому что вы можете испортить очень легко. В самом деле, одним из наиболее распространенных способов для программ, в эти дни быть использованы по-прежнему является для программиста, чтобы не понимать что он или она разрешает данных быть написаны на место в памяти, которая не была предназначена. 

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

В самом деле, когда веб-сайты в эти дни эксплуатируется и скомпрометирован и данные просочились и пароли были украдены это очень часто связано с плохим управлением своей памяти, или, в случае баз данных, неспособность предвидеть состязательности вход, так что больше на том, что в ближайшие недели, а сейчас просто предварительный просмотр рода ущерб, который вы можете сделать , не совсем понимая, как все это работает под капотом. Давайте идти о понимая, почему это не работает с инструментом, который будет становиться все более и более полезными как наши программы становятся все более сложными. До сих пор, когда у вас была ошибка в вашей программе как вы ушли об отладке это? Что ваши методы были до сих пор, учил ли ваша TF или просто самоучка? [Студент] Printf. Printf, так Printf, вероятно, был вашим другом в том, что если вы хотите увидеть что происходит внутри вашей программы вы просто положить Printf здесь, Printf здесь, Printf здесь. Тогда вы запустите его, и вы получите целую кучу вещей на экране , которые можно использовать, чтобы затем определить, что на самом деле происходит не так в вашей программе. 

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

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

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

Вместо этого позвольте мне сделать это. В этой строке GDB позвольте мне вместо введите перерыва, ввести. Это не то, что я имел в виду, чтобы напечатать. Давайте вместо этого ввести перерыв основной. Другими словами, я хочу установить так называемый останова, которую назвали потому, что он сломается или паузы выполнение программы в этом конкретном месте. Главное это имя моей функции. Обратите внимание, что GDB является довольно умная. Он выяснил, что основная происходит, чтобы начать примерно на линии 18 из buggy3.c, а затем заметить здесь, в левом верхнем B + расположен рядом с линией 18. Это напоминает мне, что я поставил точку останова на строке 18. Это время, когда я печатаю перспективе, я собираюсь запустить мою программу До она попадает, что останова, так что программа будет приостановлена ​​для меня в строке 18. Здесь мы идем, бежать. Ничто, кажется, случилось, но обратите внимание на левый нижний начиная программу, buggy3, останова 1 в основной buggy3.c на линии 18. Что я могу сделать сейчас? 

Обратите внимание, я могу начать печатать такие вещи, как печать, Не Printf, печать х, и сейчас это странно. $ 1 это просто любопытство, как мы увидим каждый раз, когда вы печатаете то, что вы получите новый $ значение. Вот, так что вы можете вернуться к предыдущим значениям на всякий случай, но сейчас то, что печать говорит мне, что значение х в этот момент в истории видимо 134514032. Что? Где, что даже взялся? [Неразборчиво-студент] В самом деле, это то, что мы называем мусором значение, и мы не говорили по этому поводу, но причина, что вы инициализация переменных Очевидно, так что они имеют некоторое значение, которое вы хотите их иметь. Но улов напомнить, что вы можете объявлять переменные как я минуту назад в моем примере сигма , фактически не давая им значения. Напомним, что я сделал здесь, в сигма. Я заявил, п, но какое значение я дать ему? Нет, потому что я знал, что в ближайшие несколько строк GetInt будет заботиться о проблеме положить значение внутри н. 

Но в этот момент в истории строке 11 и 12 линией и линией 13 и строка 14 в течение этих нескольких строках то, что значение п? В C Вы просто не знаю. Это вообще какая-то фигня значение, некоторые совершенно случайное число что остается за главным образом из некоторых предыдущих функций будучи работать, так как ваша программа работает Напомним, что функция получает функции, функции, функции. Все эти кадры получить положить на память, а затем эти функции возвращают, и так же, как я предложил, с ластиком их памяти, в конечном счете повторно. Ну, так уж случилось, что эта переменная х в этой программе по-видимому, содержит некоторые мусора значение, как 134514032 от некоторых предыдущих функции, а не тот, который я написал. Это может быть что-то, что приходит эффективно с операционной системой, некоторые функции под капотом. 

Ладно, это хорошо, но давайте теперь перейти к следующей строке. Если я типа "Следующий" на GDB мои строки, и я ударил войти, заметить, что выделение движется вниз к линии 19, но логический подразумевается, что строка 18 В настоящее время закончил работу, так что если я еще раз введите "печать х" Я должен появиться 1, и, действительно, я делаю. Опять же, $ вещей является способом GDB напоминать вам что история отпечатки, что вы сделали. Теперь позвольте мне идти вперед и распечатать у, и, действительно, у есть некоторые сумасшедшие значения, а также, но не большая проблема, потому что в строке 19 мы собираемся назначить его значение 2, так что позвольте мне ввести "Следующий" еще раз. И сейчас мы находимся на Printf линии. Позвольте мне сделать печать х. Позвольте мне сделать печать у. Честно говоря, я уже немного устал от этой печати. Позвольте мне вместо этого ввести "дисплей X" и "Y Дисплей", и теперь каждый раз, когда я введите команду в будущем Я буду напомнил о том, что это х и у, что х и у, что х и у. 

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

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

Теперь я обратно в строке 18. Теперь обратите внимание х и у мусорных значения снова. Следующий, следующий, следующий, следующий. Если я получаю скучно я могу просто введите п для следующего. Вы можете сократить его в кратчайшие последовательность символов. Сменный теперь сломана. Давайте погрузимся в, так что вместо того, чтобы печатать дальше, Теперь я собираюсь ввести шагом, так что я активизации внутри этой функции так что я могу пройти через это, так что я ударил шаг, а затем ввести. Обратите внимание, что выделение скачки вниз ниже в моей программе линии 36. Теперь то, что являются локальные переменные? Информация местные жители. Ничто не просто еще и потому, что мы не дошли до этой строки, так что давайте идти вперед и сказать: "Следующий". Теперь мы, кажется, TMP, печать TMP. Мусор значение, не так ли? Я так думаю. Как насчет печать, печать б, 1 и 2? В момент, как только я набираю следующий раз TMP будет принимать значение 1, мы надеемся, TMP, потому что собирается быть присвоено значение. 

Теперь давайте сделаем печать, печать б, но теперь печати TMP, и это действительно 1. Позвольте мне делать дальше. Позвольте мне делать дальше. Я закончил своп функции. Я все еще внутри него в строке 40, так что позвольте мне печать, б печати, и я не волнует, что TMP есть. Похоже, что своп правильно, когда дело доходит до замены и б. Но если я сейчас введите следующую, я чтобы вернуться к строке 25, и, конечно, если я типа х и печати у они по-прежнему без изменений, так что мы не решили проблему. Но диагностически сейчас, пожалуй, с этой программой GDB Мы по крайней мере, получил один шаг ближе к пониманию что происходит не так, не засорять наш код, поставив Printf здесь, Printf здесь, Printf здесь, а затем запустить его снова и снова пытается выяснить, что происходит не так. 

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

Там есть видео, которое мы просили, что вы следите за проблемы устанавливает 3 , в котором Nate покрывает некоторые из тонкостей GDB, и это одна из тех вещей, честно говоря, где некоторые нетривиальные процент вы никогда не коснется GDB, и это будет плохо потому что буквально вы будете в конечном итоге тратят больше времени в этом семестре гоняться за ошибки, то вы бы, если бы вы положили в том, что полчаса / час На этой неделе и в следующем обучения, чтобы освоиться с GDB. Printf был вашим другом. GDB должен теперь быть вашим другом. 

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

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

Сейчас я вернулся в основной, и я могу печатать х, и я могу напечатать у, но я не могу распечатать или б. Но я могу, если я скажу: «Хорошо, подождите минутку. Где был своп?" Позвольте мне идти вперед и сказать: "кадр 0". Сейчас я там, где я хочу быть, и в сторону, есть другие команды тоже, как если бы вы действительно скучно набрав следующий, следующий, следующий, следующий, Вы можете вообще сказать что-то вроде "следующие 10", и что уйдет в течение следующих 10 строк. Вы также можете написать "продолжить", когда вы действительно устаете от пошагового он. Продолжайте будет запустить программу без перерыва, пока не встретит другую точку останова, будь то в петлю или ниже в вашу программу. 

В этом случае мы продолжали до конца, и программа нормально завершился. Это причудливый способ, уступает процесса. Просто ваша программа нормально завершился. Подробнее об этом в видео и в отладке сессий в будущем. Это было много. Давайте возьмем наш 5-минутный перерыв здесь, и мы вернемся с структурам и файлов. 

Если вы нырнули в PSET на этой неделе уже Вы будете знать, что мы используем в распределении код, исходный код, который мы предоставляем вам в качестве отправной точки, некоторые новые методы. В частности, мы ввели это новое ключевое слово называется структура, для структуры, так что мы можем создавать пользовательские переменные сортов. Мы также ввели понятие файла I / O, файлового ввода и вывода, и это так, что мы можем сохранить состояние Вашей Scramble платы в файл на диске так что обучение стипендиатов и я могу понять что происходит внутри вашей программы без необходимости вручную играть десятки игр Scramble. Мы можем сделать это более automatedly. 

Эта идея структуры решает довольно убедительные проблемы. Предположим, что мы хотим реализовать некоторые программы что каким-то образом отслеживает информацию о студентах, и студенты могли бы иметь, например, ID, имя, и дом в таком месте, как Гарвард, поэтому эти 3 части информации мы хотим, чтобы вокруг, так что позвольте мне идти вперед и начать писать небольшую программу здесь, включает stdio.h. Позвольте мне сделать включать cs50.h. А потом начать свою основную функцию. Я не буду с любыми аргументами командной строки, и вот я хочу, чтобы студент, так что я собираюсь сказать, Студент имеет имя, так что я собираюсь сказать "строка имя". Тогда я собирался сказать студент также имеет идентификатор, так Int Идентификатор, и студент имеет дом, поэтому я также хотел сказать "строка дом". Тогда я закажу эти немного более аккуратно, как это. Хорошо, теперь у меня есть 3 переменные, с которыми представляют студента, так что "студент". 

А теперь я хочу, чтобы заполнить эти ценности, так что позвольте мне идти вперед и сказать что-то вроде: "ID = 123". Имя собирается получить Давида. Скажем, дом собирается получить Mather, , а затем я собираюсь сделать что-то произвольно, как Е ("% S, с идентификатором% D,% проживает в с. А теперь, что я хочу подключить сюда, один за другим? Имя, идентификатор, дом, возвращается 0. Хорошо, если я облажался где-то здесь Я думаю, что у нас есть довольно хорошая программа, которая хранит один студент. Конечно, это не все, что интересно. Что делать, если я хочу иметь 2 студента? Это не большая проблема. Я могу поддерживать 2 человек. Позвольте мне пойти дальше и выделить это и спуститься сюда, и я могу сказать "ID = 456" для кого-то, как Роб, который живет в Kirkland. 

Ладно, подожди, но я не могу назвать это то же самое, и, похоже, я буду иметь, чтобы скопировать это, так что позвольте мне сказать, что это будут переменные Давида, и позвольте мне получить копии этих Роба. Мы называем эти Роба, но это не будет работать сейчас потому что я-подождите, давайте изменим меня id1, name1 и House1. Роб будет 2, 2. Я должен изменить это здесь, здесь, здесь, здесь, здесь, здесь. Подождите, а как же Томми? Давайте сделаем это снова. Очевидно, что если вы все еще думаете, что это хороший способ сделать это, это не так, так копировать / вставить плохо. Но мы решили эту неделю назад. 

Что это было наше решение, когда мы хотели иметь несколько экземпляров одного и того же типа данных? [Студенты] массива. Массива, так что позвольте мне попытаться очистить это. Позвольте мне сделать несколько номеров для себя на вершине, и позвольте мне вместо этого здесь. Мы называем этих людей, а вместо этого я собираюсь сказать "Int идентификаторы" и я собираюсь поддержать 3 из нас в настоящее время. Я собираюсь сказать "строка имен", и я буду поддерживать 3 из нас, и тогда я буду говорить "строка дома", и я буду поддерживать 3 из нас. Теперь здесь вместо Давида получать свои локальные переменные Мы можем избавиться от них. Это чувствует себя хорошо, что мы очистка это. Затем я могу сказать Дэвид будет [0] и имен [0] и дома [0]. А потом Роб аналогично можно сэкономить на этом. Давайте поставим это здесь, так что он собирается быть произвольно идентификаторов [1]. Он собирается быть имена [1], , а затем, наконец, дома [1]. 

Еще немного утомительно, и теперь у меня есть, чтобы понять это, так скажем, "имена [0], ID [0], дома [0], и давайте множественном числе это. Идентификаторы, идентификаторы, идентификаторы. И опять же, я делаю это, так снова, я уже прибегая к копировать / вставить снова, так что шансы есть другое решение здесь. Я, вероятно, может очистить это далее с петлей или что-то вроде этого, Короче говоря, это немного лучше, но все еще чувствует себя Я прибегая к копировать / вставить, но даже это, я утверждаю, на самом деле не принципиально правильное решение, потому что Что делать, если когда-нибудь мы решим вы знаете, что? Мы действительно должны были хранения адресов электронной почты для Дэвида и Роб и все остальное в этой программе. Мы должны также сохранять телефонные номера. Мы должны также сохранять номера экстренной связи. У нас есть все эти фрагменты данных, которые мы хотим сохранить, так как вы идете для этого сделать? 

Вы объявляете другой массив в верхней части, а затем вручную добавить адрес электронной почты [0], адрес электронной почты [1] для Дэвида и Роб и так далее. Но на самом деле всего лишь предположение, лежащие в основе этой конструкции что я использую системе чести знать, что [I] в каждом из нескольких массивов Просто так случилось, чтобы обратиться к тем же лицом, так [0] в идентификаторами это номер 123, и я буду считать, что имена [0] такое же имя человека и дома [0] является домом того же самого человека и так далее для всех различных массивов, которые я создаю. Но обратите внимание, что нет никаких фундаментальных связей Среди этих 3 частей информации, номер, имя и дом, даже если лицо мы пытаемся модель в этой программе не массивы. Массивы являются именно этот программный способ сделать это. То, что мы действительно хотим, чтобы смоделировать в нашей программе это человек, как Давид, человек, как Роб, внутри которого или инкапсуляции это имя и ID и дома. 

Можем ли мы как-то выразить эту идею инкапсуляции , при котором человек имеет идентификатор, название и дом и не прибегать к действительности этот хак которой мы только что верить, что что-то кронштейн относится к той же человеческой сущности в каждом из этих разрозненных массивов? Мы можем реально сделать это. Позвольте мне пойти выше основного на данный момент, и позвольте мне создать свой собственный тип данных на самом деле в первый раз. Мы использовали эту технику в Scramble, но здесь я собираюсь пойти дальше и создать тип данных, и вы знаете, что я собираюсь называть это студент или человек, и я собираюсь использовать ЬурейеЕ для определения типа. Я хочу сказать, что это структура, а затем эта структура будет иметь тип студента, мы будем говорить, хотя это немного датированы теперь для меня. Мы говорим "Int Идентификатор». Мы говорим "строку имя". Тогда мы говорим "Строка дом" так что теперь до конца эти несколько строк кода Я только что учил лязг, что существует Тип данных, кроме целых чисел, кроме строк, кроме того, в два раза, кроме того, поплавки. 

По состоянию на данный момент времени строка 11, в настоящее время новый тип данных, который называется студентов, и теперь я могу объявить переменную любой студент я хочу, так что позвольте мне прокрутите вниз для людей. Теперь я могу избавиться от этого, и я могу вернуться вниз к Давиду здесь, и для Дэвида я могу реально сказать, что Давид, можно буквально назвать переменной после себя, будет тип студента. Это может показаться немного странным, но это не все, что отличается от объявления что-то в виде целого числа или строки или с плавающей точкой. Просто так случилось, будет называться студентом сейчас, и если я хочу поставить что-то внутри этой структуры У меня теперь есть использовать новую часть синтаксиса, но это довольно просто, david.id = 123, david.name = "Давид" в столице D, и david.house = "Mather," и теперь я могу избавиться от этой вещи здесь. Обратите внимание, сейчас мы переработали наши программы действительно намного лучше в том, что теперь наша программа отражает реальный мир. 

Там в реальном мире понятие человека или студента. Здесь мы имеем сейчас версии C лица или, более конкретно студента. Внутри этого человека эти соответствующие характеристики, ID, имя и дом, так что Роб сути становится то же самое здесь, так ограбить студента, а теперь rob.id = 456, rob.name = "Боб". Тот факт, что переменная называется Rob является своего рода бессмысленными. Мы могли бы назвал это х или у, или г. Мы только что назвал его Роб быть семантически последовательным, но на самом деле зовут внутри этого самого поля, так что теперь у меня есть. Это тоже не похоже на лучший дизайн в том, что я жестко Давида. Я жестко Роб. И я все еще вынуждены прибегать к некоторым скопируйте и вставьте каждый раз, когда я хочу новых переменных. Кроме того, я должен по-видимому дать каждой из этих переменных имя, хотя я бы предпочел описать эти переменные  в более общем плане, как студенты. 

Теперь мы можем объединить идеи, которые работают хорошо для нас и вместо этого сказал: "Знаешь что, дай мне переменную называемую студентов, и пусть вас это будет размером 3 ", так что теперь я могу уточнить это дальше, избавиться от ручного заявил Давид, и я могу, а сказать что-то вроде студентов [0] здесь. Затем я могу сказать студентов [0] здесь, Студенты [0] Здесь и так далее, и я могу ходить и чистый, что для Роба. Я мог бы также идти об теперь, возможно, добавление петли и использование GetString и GetInt на самом деле получить эти значения от пользователя. Я мог бы идти о добавлении постоянной, потому что это вообще плохая практика на жесткий код некоторые произвольные числа, как 3 прямо здесь , а затем просто помните, что вы должны поставить не более 3 студентов в нем. Вероятно, было бы лучше использовать # определить в верхней части моего файла и фактор, который, таким образом, действительно, дай мне пойти дальше и обобщить это. 

Позвольте мне открыть примеру, что среди сегодняшних Примеры заранее, structs1. Это более полная программа, которая использует # определить здесь и говорит, что мы собираемся иметь 3 студентов по умолчанию. Здесь я объявлении класса стоит студентов, так классе студентов, и теперь я с помощью цикла только, чтобы сделать код немного более элегантно, заполнить класс с участием пользователя, так итерации с I = 0 на до студентов, что на 3. И тогда я предложить пользователю в этой версии  Что ID студента, и я получаю его с GetInt. Что имя студента, а потом получить его с GetString. Что доме студента? Я получаю его с GetString. А затем в нижней здесь я просто решил изменить как я печатаю эти, и на самом деле использовать цикл, И кто я печатью? В соответствии с комментарием я печатаю никому в Mather, и вот именно поэтому Роб и Томми и так далее, на самом деле Томми в Mather. Томми и Дэвид будут напечатаны в этом случае, но как это работает? Мы не видели эту функцию раньше, но сделать предположение о том, что это делает. Сравнивает строки. 

Это немного неочевидным, как он сравнивает строки, потому что оказывается, если она возвращает 0, что означает, что строки равны. Если она возвращает -1, что означает, что человек приходит в алфавитном порядке перед другими, и если она возвращает +1, что означает слово приходит другой в алфавитном порядке перед другими, и вы можете смотреть онлайн или в справочную страницу , чтобы увидеть, какой именно способ которую, но все это сейчас делает это говорит если [I]. Дом равно "Мазер" затем пойти дальше и распечатать так и так находится в Mather. Но вот то, что мы раньше не видели, и мы вернемся к этому. Я не помню, никогда не имея для этого ни в одной из моих программ. Бесплатные видимо ссылкой на память, освобождая оперативную память, но то, что память я видимо освобождение в этом цикле в нижней части этой программы? Похоже, я освобождая имя человека и дом человека, но зачем это? 

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

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

Мы вернемся, когда и почему вы могли бы назвать свободным, Но давайте идти вперед только для хорошей мерой и попробуйте запустить эту конкретную программу. Это называется structs1, введите. Позвольте мне идти вперед и работать structs1, 123, David Mather, 456, Rob Kirkland, 789, Томми Mather, и мы видим Давида в Mather, Томми в Mather. Это всего лишь маленькая проверка вменяемости, что программа работает. Сейчас, к сожалению, эта программа является немного расстраивает в том, что Я сделал все, что работа, я набрал в 9 различных строк, нажмите ввод, сказали, кто был в Mather, но, очевидно, я не знал, кто был в Mather уже потому, что я набрал его. Было бы по меньшей мере неплохо, если бы эта программа больше похожа на базу данных и он действительно помнит, что я набрал в так что я никогда больше не придется вводить эти записи студентов. Может быть, это как registrarial системы. 

Мы можем сделать это с помощью этого метода, известного как файловый ввод / вывод, файлового ввода и вывода, Очень общий способ сказать, что в любое время вы хотите читать файлы или записать файлы Вы можете сделать это с определенным набором функций. Позвольте мне идти вперед и открыть этот пример structs2.c, которые почти идентичны, но давайте посмотрим, что он сейчас делает. В верхней части файла я объявить класс студентов. Я тогда заполнения класса с пользовательским вводом, так что те строки кода так же, как и раньше. Тогда, если я прокрутите вниз здесь я печатаю все, кто находится в Mather произвольно, как и раньше, Но это интересная новая функция. Эти строки кода являются новыми, и они вносят что-то здесь, FILE, все заглавные, и она имеет * здесь также. Позвольте мне перенести этот сюда, * здесь также. 

Эта функция, которую мы раньше не видели, Еореп, но это означает открытие файла, так что давайте бегло этим, и это то, что мы вернемся в будущем psets, но эта линия здесь по существу открывает файл с именем базы данных, и это определенно открывает его таким образом, что он может делать все, что с ним? [Неразборчиво-студент] Право, таким образом, "W" означает лишь то это говорит операционной системы открыть этот файл таким образом, что я могу написать к нему. Я не хочу, чтобы прочитать его. Я не хочу, чтобы просто посмотреть на нее. Я хочу изменить и добавить материал потенциально к нему, и файл будет называться базой данных. Это можно назвать что угодно. Это может быть database.txt. Это могло бы быть. Дб. Это может быть слово, как Foo, но я произвольно выбрал имя файла базы данных. Это немного проверку вменяемости, что мы вернемся к очень подробно с течением времени, Если FP, для указателя файла, не равно NULL, что означает, что все хорошо. 

Короче говоря, такие функции, как Еореп иногда терпят неудачу. Возможно, файл не существует. Может быть, вы из дискового пространства. Может быть, вы не имеете прав доступа к этой папке, так что если Еореп возвращает нулевое что-то плохое случилось. И наоборот, если Еореп не возвращает нулевое все хорошо и я могу начать писать в этот файл. Вот новый трюк. Это цикл который итерации по каждому из моих студентов, и это выглядит так похожи на то, что мы делали раньше, но эта функция является двоюродным братом Printf называется Fprintf для файла Printf, и заметите, что он отличается только 2 пути. Во-первых, он начинается с F вместо р, но тогда ее первым аргументом является то, что видимо? [Студенты] файла. >> Это файл. Это то, что называется FP, который мы в конце концов дразнят друг от друга, что файл указателя, но сейчас FP представляет собой просто файл, который я открыл, так Fprintf здесь говорят распечатать ID этого пользователя к файлу, а не на экран. Распечатать имя пользователя в файл, а не на экран, Дом в файл, а не на экране, а затем здесь, очевидно, закрыть файл, а затем сюда бесплатный памяти. 

Единственная разница между этой версии 2 и версии 1 является введение Еореп и это файл с расширением * и это понятие Fprintf, так что давайте посмотрим, что конечный результат. Отпустите меня в моем окне терминала. Позвольте мне выполнить structs2, введите. Похоже, все будет хорошо. Давайте повторно structs2. 123, David Mather, 456, Rob Kirkland, 789, Томми Mather, введите. Похоже, он вел себя так же, но если я сейчас делаю Ls заметите, что файл находится здесь среди всех мой код, базы данных, так давайте откроем, что Gedit базы данных, и смотреть на это. Это не самый сексуальный форматов файлов. Это на самом деле одна часть данных линии на линию за линией, но те из вас, кто использует Excel или CSV файлов, значения, разделенные запятыми, Я мог бы, конечно, использовать Fprintf вместо этого, может быть, сделать что-то вроде этого так что я мог фактически создать эквивалент файл Excel путем отделения вещи с запятыми, а не только новых линий. 

В этом случае, если бы вместо этого использовать запятые вместо новых линий Я мог буквально открыть этот файл базы данных в Excel, если я вместо этого сделал его похожим на это. Короче говоря, теперь, когда у нас есть силы, чтобы писать файлы Теперь мы можем начать сохранения данных, сохраняя его на диск вокруг так что мы можем хранить информацию вокруг снова и снова. Обратите внимание на несколько других вещей, которые сейчас немного более знакомо. В верхней части этого файла C мы имеем ЬурейеЕ потому что мы хотели создать тип данных, который представляет собой слово, так что этот тип называется словом, а внутри этой структуры это немного любитель сейчас. Почему слово состоит из видимому массива? Что такое слово просто интуитивно? 

Это массив символов. Это последовательность символов, спина к спине к спине. ПИСЬМА заглавными буквами, случается, мы сколь угодно говорить максимальной длины любое слово в словарь, который мы используем для Scramble. Почему я +1? Нулевой символ. Напомним, когда мы делали например Bananagrams мы должны особое значение В конце слово для того, чтобы отслеживать , где слова на самом деле закончились, и как спецификация проблема набора говорит Здесь мы общения с данным словом логическое значение, Флаг, так сказать, истинным или ложным. Нашли ли вы это слово уже, потому что мы понимаем, мы действительно нуждаемся способ запоминания не только то, что слово есть в Scramble но вы или нет, человека, нашли его так что если вы найдете слово "" Вы не можете просто ввести, вводить, вводить, введите и получите 3 балла, 3 балла, 3 балла, 3 балла. Мы хотим иметь возможность в черный список, что слово, установив логическое истинно, если вы уже нашли его, и именно поэтому мы инкапсулированные его в эту структуру. 

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

Что это в конечном итоге позволит нам делать? Позвольте мне вернуться в, скажем так, более простой пример из более простых времен, и позвольте мне открыть, скажем, compare1.c. Проблема здесь в руках на самом деле отогните слой строку и начать взлет этих учебных колесах потому что получается, что строка все это время является, как мы и обещали в неделю 1 действительно только прозвище, Синоним от CS50 библиотеки за то, что выглядит немного более загадочным, символ *, и мы видели эту звезду раньше. Мы видели это в контексте файлы. 

Давайте посмотрим, почему мы скрывали эту деталь в течение некоторого времени. Вот файл с именем compare1.c, и он, очевидно, предлагает пользователю на 2 строки, с и т, а затем он пытается сравнить эти строки равенства в строке 26, и если они равны она говорит: "Вы набрали одно и то же», и если они не равны она говорит: "Вы ввели разные вещи". Позвольте мне идти вперед и запустить эту программу. Отпустите меня в мой исходный каталог, сделать compare1. Он составлен в порядке. Позвольте мне выполнить compare1. Я буду увеличивать, введите. Скажи что-нибудь. HELLO. Я скажу что-то снова. HELLO. Я определенно не вводить разные вещи. 

Позвольте мне попробовать это снова. BYE BYE. Определенно не отличается, так что здесь происходит? Ну, то, что действительно по сравнению в строке 26? [Неразборчиво-студент] Да, так получается, что строка, тип данных, это своего рода ложь во спасение. Строка символов *, но то, что символ *? Символ *, как говорят, является указателем, и указатель эффективно адрес, Сумма место в памяти, и, если вам случится ввели в слово, как HELLO, Напомним прошлых обсуждений строк это похоже на слово HELLO. Помните, что слово, как ПРИВЕТ могут быть представлены как массив символов, как это а затем с помощью специального символа в конце называемый нулевой символ, как \ обозначает. Что на самом деле является строкой? Заметим, что это несколько участков памяти, и в самом деле, конец известно только, если посмотреть всю строку ищет особый характер нулевой. Но если это кусок памяти из моего компьютера, Давайте произвольно сказать, что эта строка просто повезло, и он, были устроены в самом начале оперативной памяти моего компьютера. Это байт 0, 1, 2, 3, 4, 5, 6 ... 

Когда я говорю что-то вроде GetString и я строка S = GetString что на самом деле возвращаются? За эти последние несколько недель, что на самом деле хранится в ы Не эта строка сама по себе, но в данном случае то, что хранится является число 0, так что на самом деле делает GetString оно физически не возвращать строку. Это даже не реально сделать концептуальном смысле. Что она делает возвращение числа. Это число является адресом ПРИВЕТ в памяти, и строка с потом, если мы отогните этот слой, строка на самом деле не существует. Это всего лишь упрощение CS50 библиотеки. 

Это действительно то, что называется символ *. Char имеет смысл, потому что слово, как Алло? Ну, это серия символов, набор символов. Char * означает, что адрес характера, так что это значит для возврата строки? Хороший, простой способ возвращения строки есть, а не пытаться выяснить, как я возвращаюсь в 5 или 6 различных байтов Позвольте мне вернуться в адрес которого байт? Первый. Иными словами, позвольте мне дать вам адрес символа в памяти. Вот что символ * представляет собой, по адресу одного символа в памяти. Вызовите эту переменную с. Хранить в частности, что с адреса, который я условно сказал равен 0, только, чтобы держать вещи простыми, но на самом деле это вообще большие числа. 

Подождите минуту. Если вы только что дали мне адрес первого символа, как я знаю, что адрес второй персонаж, третий, четвертый и пятый? [Неразборчиво-студент] Вы только знаете, где в конце строки через этот удобный трюк, поэтому, когда вы используете что-то вроде Printf, что Printf буквально берет в качестве аргумента, Напомним, что мы используем заполнитель% с этим, а потом перейти в переменной, которая хранения строки. То, что вы действительно проходящей это адрес первого символа этой строки. Printf затем используется для цикла или время цикла при получении этому адресу, Например, 0, так что позвольте мне сделать это сейчас, Е ("% с \ п", с); Когда я называю Е ("% с \ п", с); что я действительно предоставлении Printf с это адрес первого символа в S, которое в этом случае является произвольным H. 

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

Профессор Ник Parlante в Стэнфорде сделали этот замечательный видеоряд от всех видов различных языков, которые ввели эта маленькая Бинки характер Claymation. Голос вы услышите всего несколько секунд просмотра подхалима является то, что профессор Стэнфорда, и вы получаете Только 5 или 6 секунд это прямо сейчас, Но это к сведению, на которых мы закончим сегодня и начать в среду. Я даю вам Указатель Fun с Бинки, предварительный просмотр. [♪ Музыка ♪] [Профессор Parlante] Эй, Бинки. Проснись. Это время для указателя весело. [Бинки] Что это? Узнать о указателей? О, сентиментальный! 

Мы будем видеть Вас в среду. [CS50.TV]