[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 різних рядків, натисніть Enter,
сказали, хто був у 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]