[Грає музика] 

[ВІДТВОРЕННЯ ВІДЕО] 

-Він Бреше. 

-Про що? 

-Не знаю. 

-Так Що ми знаємо? 

-Це У 9:15, Рей Сантойо був в банкоматі. -Так. Таким чином, питання, що він робить у 9:16? 

-Зйомка 9-міліметрового на щось. Може бути, він побачив снайпера. 

-Чи Працював з ним. 

Почекай. Повернення на один. 

-Що ти бачиш? 

-Bring Його горілиць повному екрані. 

-Його Окуляри. 

-Є Це відображення. 

-Це Бейсбольної команди Nuevitas. Це їх логотип. 

-А Він розмовляє з хто носить цю куртку. 

[КІНЕЦЬ ПЕРЕГЛЯДУ] 

Девід Малан: Гаразд. Це CS50 і це трохи більш з [нерозбірливо], з якою ви втручаються з проблемою встановити чотири. Сьогодні ми починаємо виглядати трохи більш глибоко в цих речах, званих покажчиків, який, хоча це досить таємницею тема, Виявляється, що він збирається бути засобом, за допомогою якого ми може почати будівництво та монтаж набагато більш складні програми. Але ми зробили це в останню середу допомогою деякого claymation першою. Так що це, нагадаємо, є Бінки, і ми використовували його щоб поглянути на програму, яка не дійсно що-небудь цікаве, але він розкрити кілька проблем. Таким чином, щоб почати сьогодні, чому ми не ходити швидко через кілька з цих кроків, спробуйте, щоб відігнати в умовах людський в саме те, що тут відбувається і чому це погано, а потім перейти на а насправді почати будувати щось з цією технікою? Так що це були перші дві лінії цієї програми і з точки зору непрофесіонала, те, що які ці дві лінії роблять? Хтось, хто досить комфортно з тим, що заявив на екрані? Які ці дві лінії роблять? Це не все, що відрізняється від тижня один, але є деякі нові спеціальні символи. Так? Повернутися там. 

АУДИТОРІЯ: Оголошення покажчики? Девід Малан: раз сказати? АУДИТОРІЯ: Оголошення покажчики? Девід Малан: Оголошення покажчики та давайте уточнити його трохи більше. АУДИТОРІЯ: [нерозбірливо] адресу, а потім х у. Девід Малан: А потім звернутися. Так що конкретно ми робимо що ми оголошуємо дві змінні. Ці змінні, хоча, збираються до типу INT зірки, більш конкретно означає вони збираються зберігати адреса з Int, відповідно, х та у. Тепер є які-небудь цінності? Чи є якісь фактична адреси в них дві змінні в даний момент? Немає. Це просто так називається значення сміття. Якщо ви насправді не призначати Змінна, все, що було в пам'яті раніше збирається заповнити нулями і ті, обидва з цих змінних. Але ми ще не знаємо, які вони є, і це буде ключем до чому Binky втратив голову минулого тижня. 

Так що це був claymation Втілення цього в результаті чого у вас є тільки дві змінні, маленькі кругові частини глини, який може зберігати змінні, але, як обгорнутих стрілки запропонувати, вони насправді не вказуючи в будь-яку точку по собі відомі. Отже, ми мали цю лінію, і це була новою минулого тижня, Танос на пам'ять розподіл, який є тільки химерний спосіб розповідати операційну систему Linux, або Mac OS або Windows, Центр агов, дайте мені пам'ять, і все, що ви повинні сказати операційна система це те, що, коли його просять на пам'ять. Це не збирається піклуватися, що Ви збираєтеся з ним робити, але ви повинні сказати операційної Система, що шляхом Танос. Так? 

АУДИТОРІЯ: Скільки? Девід Малан: Скільки? Наскільки в байтах, а це так, то, знову ж таки, надуманий приклад, просто кажучи, дати мені розмір в міжнар. Тепер, розміром з Int чотири байти або 32 біта. Так що це просто спосіб кажучи, гей, операційна система, дайте мені чотири байти пам'яті що я можу використовувати в моєму розпорядженні, і, зокрема, те, що робить Танос повернення по в цьому фрагменті з чотирьох байтів? АУДИТОРІЯ: Адреса? Девід Малан: Адреса. Адреса цієї порції з чотирьох байтів. Точно. І ось що в кінцевому рахунку зберігається х, і тому ми дійсно не все одно, що кількість, що адреса, будь то OX1 або OX2 або деякі загадкові адреса шістнадцятковій. Ми просто дбаємо графічно що змінна х зараз вказуючи на те шматок пам'яті. Таким чином, стрілка являє собою покажчик або Більш конкретно, адреса пам'яті. Але, знову ж, ми зазвичай не піклуються що ці фактичні адреси. Тепер, каже, що це лінія те, що з точки зору непрофесіонала? Зірка х отримує 42 з комою. Що це значить? Ти хочеш піти? Не подряпати вашу шию. 

Аудиторія: адреса х знаходиться в 42. 

Девід Малан: Адреса х знаходиться в 42. Не зовсім. Так близько, але не зовсім, бо є зірка, яка, випереджаючи цей х. Таким чином, ми повинні налаштувати небагато. Так? 

АУДИТОРІЯ: Значення, яке Покажчик х вказуючи на це 42. Девід Малан: ОК. Значення, покажчик х вказуючи на, скажімо, буде 42, або іншими словами, зірки х каже, перейдіть до будь-яку адресу в х, будь то 1 Оксфорд Вулиця або 33 Оксфорд-стріт або OX1 або ox33, незалежно що числове адреса, зірковий х є разименованія х. Так що за цією адресою і Потім покласти туди число 42. Так що було б Еквівалентний спосіб сказати, що. Так що все нормально, а потім ми представлятиме картину наступним, де ми додали 42 до цього шматок чотирьох байти на правій стороні, але Ця лінія була, де все пішло шкереберть і глава Бінки вискочив від в цій точці, бо погані речі трапляються, коли Ви разименованія значення для сміття або ви разименованія недійсним покажчики, і я кажу недійсним тому що в даний момент в історія, те, що знаходиться всередині у? Що значення у на основі на останні кілька кроків? Так? Що це? 

АУДИТОРІЯ: адресу. Девід Малан: адреса. Це має бути адреса але я її ініціалізації? Так що у мене ще немає. Так що, як відомо, там? Це просто деяке значення сміття. Це може бути будь адресу від нуля до 2 млрд, якщо у вас є два гігабайтами оперативної пам'яті, або від нуля до 4 млрд якщо у Вас є отримав чотири гігабайти оперативної пам'яті. Це деяке значення сміття, але проблема в тому, що в операційній системі, якщо він не дав вам що частина пам'яті спеціально що ви намагаєтеся йти, це взагалі буде викликати що ми бачили, як помилки сегментації. Таким чином, справді, кожен з вас, хто боровся на проблеми в робочий час або в проблемах, які більше як правило, в спробі з'ясувати, помилки сегментації, що зазвичай означає, ти торкаєшся сегмент пам'яті, що ви не повинні бути. Ви торкаючись пам'яті, операційна система не має дозволив вам доторкнутися, будь то по заходить занадто далеко у вашому масиві або починаючи з сьогоднішнього дня, будь це тому, що ти торкаєшся пам'яті, просто деяке значення сміття. 

Так роблять зірки х тут зразок невизначеного поведінки. Ви ніколи не повинні робити це, тому що шанси які, програма просто буде крах, тому що ви говорите, перейти на цю адресу і ви поняття не маю, де що адреса насправді. Таким чином, операційна система, швидше за все, збирається до краху програми в результаті і справді, що це що там сталося на Бінки. Так в кінцевому рахунку, Бінки фіксованою ця проблема з цим. Так цієї програми сам був зіпсований. Але якщо ви як би просуватися вперед і виконати цей рядок замість у дорівнює х просто означає те, що адреса є х, також покласти його в у. 

І так наочно, ми представлені в цьому з двома стрілками від х і від у вказуючи в те ж місце. Так семантично, х дорівнює щоб у тому що обидва з них зберігайте той же адреса, отже, вказуючи на 42, і тепер, коли ви говорите, зірки у, перейти за адресою в у, це має цікавий побічний ефект. Таким чином, адреса в у є Те ж саме, як адреса в х. Так що, якщо ви говорите, йти за адресою в у і змініть значення на 13, хто ще впливає? Х, точка D, так би мовити, повинні бути порушені також. 

І справді, як Нік звернув цю картину в claymation саме це. Навіть якщо ми будемо слідувати покажчик у, ми опинилися в тому ж місці, і тому, якщо ми повинні були роздрукувати з х або pointee Y, в то ми побачили б значення 13. Тепер, я говорю pointee бути відповідно до відео. Програмісти, на мій знання, насправді ніколи не кажуть слово pointee, що є гострим в, але для послідовності з відео, розуміють, це все, що було означало в такій ситуації. Так які-небудь питання по claymation або покажчики або Танос тільки поки? Немає? Добре. 

Так що без подальшого шуму, давайте поглянемо в якому це має насправді були використані протягом деякого часу. Таким чином, ми мали цю бібліотеку CS50 що є всі ці функції. Ми використовували GetInt багато, GetString, ймовірно, GetLongLong раніше в моєму Pset один або так, але що насправді відбувається? Ну, давайте поглянемо під капотом на програму, яка надихає тому ми даємо вам CS50 бібліотека, і справді, як минулого тижня, ми почали приймати тих, навчальні колеса від. Так що це тепер упорядковано з того, що посмертних має вже на в бібліотеці CS50, навіть якщо ми тепер почне рухатися від нього для більшості програм. 

Так що це програма називається зсапЕ 0. Це супер короткий. Це просто є ці рядки, але це вводить функцію називають зсапЕ що ми насправді відбувається, щоб бачити в момент усередині бібліотеки CS50, хоча і в дещо іншій формі. Так що це програма на лінії 16 оголошує змінну х. То дайте мені чотири байти для Int. Це було розповідати користувачеві, Кількість будь ласка, а потім це цікаво, що лінія насправді пов'язує минулого тижня і це. Scanf, і зверніть увагу на те, що займає Рядок формату, як Printf, % Я означає Int, а потім вона займає Другий аргумент, який виглядає трохи фанки. Це амперсанд х, і згадати, ми бачили тільки один раз минулого тижня. Що амперсанд х представляють? Що робити в амперсанд C? Так? 

Аудиторія: адреса. Девід Малан: Адреса. Так це навпаки зоряного оператора, в той час як зірка оператор говорить, перейдіть до цю адресу, амперсанд оператор говорить, з'ясувати адресу цієї змінної, і таким чином це є ключовим, тому що Мета Scanf в житті це для сканування користувача ввести з клавіатури, залежно від все, що він або вона типи, а потім читати введення даного користувача в змінну, але ми бачили в останні два тижні що ця функція підкачки, що ми намагався зусиль для реалізації просто розбиті. Нагадаємо, що з функцією підкачки, якщо ми тільки що оголосили А і В, цілих чисел, ми дійсно успішно своп дві змінні всередині своп просто подобається з молоком і OJ, але як тільки повернувся підкачки, який був результат по х і в, оригінальні значення? Нічого. Так. Нічого не сталося, що час, тому що свопи змінити тільки свої локальні копії, який повинен сказати, все на цей раз, щоразу, коли ми в були передаючи аргументів до функцій, ми просто проходячи копії цих аргументів. Ви можете робити з цим що ви хочете з ними, але вони збираються мати НЕ Вплив на вихідні значення. Так що це проблематично, якщо вам хочете мати функцію, як зсапЕ в житті, мета якого полягає в скануванні вхід користувача з клавіатури а потім заповнити прогалини, так кажуть, що це, дають змінну х, як значення, тому що, якби я був просто передати х в Scanf, якщо ви вважаєте, логіку в минулому тиждень, зсапЕ може робити все, що він хоче з копією х, але вона не могла назавжди змінити х, якщо ми не дамо Scanf карту скарбів, так би мовити, де х позначає місце, в результаті чого ми проходимо на адресу х, так що зсапЕ можете піти туди і фактично зміна значення х. І так дійсно, все що ця програма робить якщо я зсапЕ 0, на мій джерела Каталог 5м, зробити зсапЕ 0, точка слеш зсапЕ, номер будь ласка, 50, спасибі за 50. 

Так що це не все, що цікаво, Але те, що дійсно відбувається є те, що, як тільки я називаю Scanf тут, значення х в даний час постійно змінюється. Тепер, це, здається, хороший і добре, а насправді, це Схоже, ми дійсно не потрібно бібліотека CS50 взагалі більше. Наприклад, давайте працювати це ще раз тут. Дозвольте мені відкрити його протягом секунди. Давайте спробуємо номер, будь ласка, і замість того щоб сказати 50, як раніше, давайте просто сказати ні. ОК, це трохи дивно. ДОБРЕ. І лише деякі дурниця тут. Так що, здається, не обробляти помилкові ситуації. Таким чином, ми повинні мінімально старт додавши деякі перевірки помилок щоб переконатися, що користувач має надрукована в фактична кількість як 50, тому що очевидно набравши слів не виявлено проблематичним, але це, ймовірно, повинно бути. 

Давайте подивимося на цю версію тепер це моя спроба перевизначити GetString. Якщо зсапЕ все це має Функціональність вбудована, чому ми були з ними балуватися навчальні диски, як GetString? Ну, ось, мабуть, моя власна проста версія GetString в результаті чого тиждень тому, я б сказав дати мені рядок і називають це буфер. Сьогодні, я збираюся почати тільки кажучи сЬаг зірки, який, нагадаємо, це просто синоніми. Це виглядає страшніше, але це точно така ж річ. То дайте мені змінної називається буфер що збирається зберігати рядок, скажіть будь ласка, рядок користувача, а потім, як і колись, давайте спробуємо зайняти цей урок зсапЕ % S цей час, а потім передати в буфері. Тепер, швидка перевірка розсудливість. Чому я не кажу, амперсанд буфер на цей раз? Висновок з попереднього прикладу. АУДИТОРІЯ: Чар зірка покажчик. Девід Малан: Рівне, бо це час, гольця зірка вже покажчик, адреса, за визначенням цієї зірки бути там. І якщо зсапЕ очікує адреса, достатньо лише пройти в буфері. Мені не потрібно, щоб сказати, амперсанд буфер. Для цікавих, ви могли б зробити щось на зразок цього. Це матиме інше значення. Це дасть вам покажчик на покажчик, який насправді дійсний річ в C, але для Тепер, давайте тримати його проста і тримати історію відповідно. Я просто хочу, щоб передати в буфер і це правильно. Проблема, однак, полягає в наступному. Дозвольте мені йти вперед і працювати в цьому Програма після компіляції. Зробити зсапЕ 1. Чорт візьми, мій компілятора ловити свою помилку. Дайте мені одну секунду. Clang. Скажімо Scanf-1.c. ДОБРЕ. Там ми йдемо. Мені це потрібно. CS50 ID має різні Параметри конфігурації що захистить вас від себе. Мені потрібно відключити ті, по працює брязкіт вручну в цей раз. Так рядок ласка. Я збираюся йти вперед і ввести в моєму улюбленому світі привіт. ОК, нуль. Це не те, що я набрав. Так що це свідчить про то помилитися. Дозвольте мені йти вперед і ввести справді довгого рядка. Подяка за нуль, і я не знаю, якщо я збираюся бути в змозі розбити його. Давайте спробуємо трохи копію вставити і подивитися, якщо це допомагає. Просто вставте багато що з цього. Це, безумовно, більше Рядок, ніж зазвичай. Давайте просто дійсно написати його. Немає. Блін. Команда не знайдена. Так от не пов'язані. Це тому, що я вставив деякі погані персонажі, але це виявляється не працюватиме. 

Давайте спробуємо це ще раз, тому що це більш цікаво, якщо ми насправді крах його. Давайте друкую це, і тепер, я збирається копіювати дійсно довгий рядок а тепер давайте подивимося, якщо ми може призвести до збою цю річ. Зверніть увагу, я опустив простору і нові лінії і крапки з комою і всі незрозумілі символи. Enter. І тепер в мережі просто бути повільним. Я тримав вниз Command-V занадто довго, ясно. Блін! Команда не знайдена. 

ДОБРЕ. Ну, справа в тому, тим не менше, після. Так що насправді відбувається з цією декларацією Чар зірок буфера на лінії 16? Так що я отримую Коли я оголошую покажчик? Все, що я отримую значення байта чотирьох звана буферна, але те, що всередині нього на даний момент? Це просто деяке значення сміття. Тому будь-який час ви оголошуєте змінну в C, це просто деяке значення сміття, і ми починаємо Поїздка по цій реальності. Тепер, коли я говорю зсапЕ, перейти на цю адресу і покласти всі типи користувачів в. Якщо користувач в привіт Світ, ну, куди я поклав його? Буфер значення сміття. 

Так що начебто як стріла який, вказуючи, хто знає, де. Може бути, це вказує прямо тут, в моїй пам'яті. І тому, коли користувач типи в світі, здравствулте! програма намагається поставити Рядок привіт світ зворотний слеш 0 в цьому шматку пам'яті. Але з великою часткою ймовірності, але явно не 100% ймовірність, комп'ютер буде крах, то Програма, тому що це не пам'яті змушений бути дозволено доторкнутися. Коротше кажучи, ця програма недоліки саме з цієї причини. Я принципово не робить? Які кроки я опущені, як ми опустили з першого прикладу Бінки? Так? 

АУДИТОРІЯ: розподіл пам'яті? 

Девід Малан: розподіл пам'яті. Я насправді не виділені будь-яка пам'ять для цього рядка. Таким чином, ми можемо виправити це в кілька способів. Один з них, ми можемо зберегти його простим і справді, тепер ти збирається почати бачити розмивання ліній між тим, що Масив, те, що рядок є, те, що символ зірка, яка масив символів є. Ось другий приклад за участю струнних і повідомлення Все, що я зробив на лінії 16, замість того щоб сказати що буфер буде символ зірка, покажчик на шматок пам'яті, Я збираюся дуже активно дають сам буфер 16 символів, і справді, якщо ви знайомі з терміном буферизації, ймовірно, зі світу відео, де відео буферизації, буферизація, буферизації. Ну, яка зв'язок тут? Ну, всередині YouTube і всередині відеоплеєрів як правило, являє собою масив це більше, ніж 16 років. Це може бути масив розміру одного мегабайт, може бути, 10 мегабайт, і в цьому масиві робить ваш браузер скачати цілу купу байтів, ціла купа мегабайт відео, і відео-плеєр, YouTube, або хто б не, починається читати байти з цього масиву, і в будь-який час ви бачите Слово буферизації, буферизація, це означає, що гравець має дійшли до кінця масиву. Мережа настільки повільно, що це не має наповнив масив з більш байт і так ви з бітів для відображення користувачеві. 

Так буфера є вдалий термін тут у тому, це просто масив, шматок пам'яті. І це буде виправити бо це виявляється що ви можете звертатися масиви, як ніби вони адреси, навіть якщо буфер це просто символ, це послідовність символів, буфер це корисно для мене, програміст, Ви можете передати своє ім'я навколо як якщо б це були покажчик, як би це були також адреса шматок пам'яті для 16 символів. Так от, щоб сказати, що я можу пройти зсапЕ саме це слово і тепер, якщо я цю програму, зробити зсапЕ 2, точка слеш зсапЕ 2, і введіть в привіт світ, Введіть, що time-- 

Хм, що трапилося? Рядок ласка. Що я зробив не так? Привіт світ, буфер. Привіт Світ. Ах, я знаю, що він робить. ДОБРЕ. Так що читає до до першого пропуску. Так що давайте обдурити на мить і сказати, що я просто хотів, щоб щось типу дійсно довго, як це довге речення це одна, дві, три, чотири, п'ять, шість, сім, вісім, дев'ять, 10, 11, 12, 13, 14, 15, 16. ДОБРЕ. Це дійсно довге речення. Таким чином, ця пропозиція є більше, ніж 16 символів і тому, коли я вдарив Enter, що станеться? Ну, в цьому випадку з історія, я оголосив буфер насправді є масив з 16 символи готовий до роботи. Так один, два, три, чотири, п'ять, шість, сім, вісім, дев'ять, 10, 11, 12, 13, 14, 15, 16. Так 16 символів, і тепер, коли я читати щось, як це довго Вирок, що станеться в що я збираюся читати в це довго S-Е-Н-Т-Е-Н-С-Е, пропозицію. 

Так що це навмисно погано, що я продовжувати писати за межами Межі моєї масиву, за межами мого буфера. Я міг би отримати пощастило, і програма буде продовжувати працювати і не хвилює, але, взагалі кажучи, це дійсно крах мою програму, і це помилка в моєму код момент, коли я крок за кордону з цього масиву, тому що я не знаю, якщо це обов'язково вріжеться або якщо я просто хочу, щоб повезти. Так що це проблематично, тому що в цей випадок, він, здається, працюють і давайте спокушати долю тут, хоча інтегрована середа, здається, терпіти зовсім небагато of-- 

Там ми йдемо. Нарешті. Так що я єдиний, хто може це побачити. Так що я просто було багато веселощів, набравши з дуже довгий фактичної фразу що це, звичайно, перевищила 16 байт, тому що я набрали в цьому божевільному тривалого мульти-лінії Фраза, і зверніть увагу на те, що сталося. Програма намагалася його друку а потім отримав помилку сегментації і помилки сегментації, коли щось подібне і операційна система говорить ні, не можуть доторкнутися до пам'яті. Ми збираємося, щоб убити Програма в цілому. 

Таким чином, це видається проблематичним. Я поліпшив програму, за допомогою якої принаймні, є пам'ять, але це, здавалося б обмежитися функція GetString, щоб отримати струни деякої кінцевої довжини 16. Так що, якщо ви хочете підтримувати більше вироки, ніж 16 символів, що ти робиш? Ну, ви можете збільшити Розмір цього буфера до 32 або, що здається почасти коротким. Чому б нам не просто зробити це 1000, але відсунути. Що відповідь інтуїтивно з просто уникнути цієї проблеми шляхом мій буфер більше, як 1000 символів? Реалізуючи GetString цей шлях. Те, що добре чи погано тут? Так? АУДИТОРІЯ: Якщо ви пов'язувати багато простору, і ви не використовуєте його, то ви не можете перерозподілити цей простір. Девід Малан: Абсолютно вірно. Це марнотратно, оскільки, якщо ви не насправді потрібно 900 байт з цих і ще ви просите 1000 в цілому в будь-якому випадку, ви просто споживати більше пам'яті на комп'ютер користувача, ніж потрібно, і врешті-решт, деякі з Ви вже зустрічалися в житті, що, коли ви працює безліч програм і що вони їдять до багато пам'яті, це дійсно може вплинути на продуктивність і досвід користувача на комп'ютері. Так що начебто ледачий рішення, напевно, і, навпаки, це не тільки марнотратно, те, що проблема як і раніше залишається, навіть якщо я можу зробити мій буфера 1000? Так? 

Аудиторія: рядок довжиною 1,001. Девід Малан: Точно. Якщо рядок довжиною 1001, у вас є точно такою ж проблемою, і мій аргумент, я б тільки потім зробити його +2000 але ви не знаєте, в заздалегідь, наскільки великий це повинно бути, і все ж, я повинен зібрати свою програму перш ніж дати людям використовувати і завантажити це. Так що це саме те, речі, які бібліотека намагається CS50 щоб допомогти нам з, і ми будемо тільки погляд на деякі з базової реалізації тут, але це CS50 точка С. Це це файл, який був на CS50 IDE всі ці тижні, що ви використовуєте. Це попередньо складений і у Вас є використовує його автоматично за характером, що має тире L CS50 прапор з брязкотом, але якщо я перейдіть вниз через всі ці функції, ось GetString, і просто щоб дати вам смак того, що відбувається, давайте швидкий погляд на відносну складність. Це не супер довго Функція, але ми не зробили повинні думаю, що всі важко про як йти про отримання рядків. 

Отже, ось мій буфер, і я мабуть, його ініціалізації до нуля. Це, звичайно, є Те ж саме, як напівкоксу зірки, але я вирішив в реалізації бібліотеки CS50 що якщо ми збираємося повністю динамічний, Я не знаю, заздалегідь, наскільки велика в рядок користувачі будуть хочете отримати. Так що я збираюся почати тільки з порожнім рядком і я збираюся побудувати стільки пам'яті, як мені потрібно, щоб відповідати рядок користувача і якщо я не достатньо, я попрошу операційна система для отримання додаткової пам'яті. Я збираюся перемістити їх рядок в більший шматок пам'яті і я збираюся випустити або звільнити недостатньо великий шматок пам'яті і ми тільки збираємося зробити це багаторазово. 

Таким чином, швидкий погляд, от тільки змінної з якою я йду, щоб відстежувати ємності моєї буфера. Скільки байт я можу відповідати? Ось змінна п з який я буду тримати трек скільки байт насправді в буфер, або що користувач ввів. Якщо ви не бачили це раніше, вам можна вказати, що змінна, як Int без знака, який, як випливає з назви, означає, що це не-негативним, а чому б Я коли-небудь хотів турбувати уточненням що INT це не просто INT, але це беззнаковое INT? Це неотрицательная Int. Що означає [нерозбірливо] на увазі? 

АУДИТОРІЯ: Це описі кількість пам'яті, який може бути [нерозбірливо]. 

Девід Малан: Так. Так що, якщо я говорю без знака, це насправді даючи вам один біт додаткової пам'яті і, здається, безглуздо, але якщо ви є один біт додаткової пам'яті, що означає, що ви повинні в два рази більше значення можна уявити, тому що це може бути 0 або 1. Так, за замовчуванням, цілочисельне може бути приблизно негативне 2 млрд весь шлях до позитивного 2 млрд. Ті великі діапазони, але він як і раніше вид марнотратно якщо ви тільки піклуватися про розміри, які просто інтуїтивно не повинні бути негативними або позитивне або 0, ну а потім, чому ви витрачаєте 2 млрд Можливі значення для негативних чисел якщо ви ніколи не збираєтеся їх використовувати? Так, говорячи без знака, тепер моя Int може бути між 0 і приблизно 4 млрд. 

Так от просто INT C з причин, ми не зможемо отримати в зараз, як чому це цілочисельне замість з гольця, але от суть того, що відбувається на, і деякі з вас можуть використовувати, наприклад, fgetc функція навіть в чотири Pset або після того, що ми побачимо його знову в задачі встановити п'ять, fgetc приємно, тому що, як ім'я вигляд, начебто arcanely припускає, це функція, яка отримує характер і тому, що принципово відрізняється про те, що ми робимо в GetString це ми не використовуємо зсапЕ таким же чином. Ми просто повзе крок за кроком протягом будь-якого користувач ввів в, тому що ми завжди можемо виділити один символ, і таким чином, ми завжди можемо сміливо дивитися в одну гольця в той час, і магія починає відбуватися тут. Я збираюся Прокрутіть вниз до середина цієї функції просто коротко представити цю функцію. Багато чого, як є Функція Танос, є функція Realloc де Realloc дозволяє вам перерозподілити частину пам'яті і зробити його більше або менше. Так Коротше кажучи, і з хвиля мого боку на сьогоднішній день, знаю, що GetString робить це свого роду магічно росте або скорочується буфер як користувач типи в його або її рядка. 

Так що, якщо користувач вводить Короткий рядок, цей код тільки виділяє достатньо пам'яті, щоб відповідати рядок. Якщо користувач зберігає введення як я зробив це знову і знову і знову, і, якщо буфера спочатку цей великий і програма реалізує, щоб постривай, я з космосу, це збирається подвоїти розмір буфера і потім два рази розмір буфера і код, який робить подвоєння, якщо ми подивимося на нього тут, це тільки ця розумна одна вкладиш. Ви, можливо, не бачив цей синтаксис раніше, але якщо ви говорите, зірки дорівнює, це те ж саме, кажучи раз Місткість 2. Так він просто продовжує подвоєння ємність буфера а потім розповідати Realloc дати Сам, що набагато більше пам'яті. 

Тепер, як в сторону, там інші функції в тут що ми не будемо дивитися в деталі крім як показати в GetInt, ми використовуємо GetString в GetInt. Ми перевіряємо, що це не NULL, який, нагадаємо, це спеціальне значення, що означає щось пішло не так. Ми з пам'яті. Краще перевірити це. І ми повертаємо значення дозорного. Але я відкласти на коментарі щодо того, чому, а потім ми використовуємо цю двоюрідний брат зсапЕ називається sscanf і виходить, що sscanf, або рядок зсапЕ, дозволяє вам поглянути на лінії, користувач ввів в вас, і нехай проаналізувати його по суті і те, що я робимо тут, я кажу sscanf, проаналізувати всі користувач набрали в і переконайтеся,% I, існує ціле число в ньому, і ми не будемо потрапити в сьогодні точно, чому є також A% C тут, але в двох словах дозволяє нам виявити, якщо користувач ввів в чомусь фіктивні після номера. Так що причина, що GetInt і GetString сказати вам, щоб повторити спробу, повторіть, повторіть спробу з-за всіх що код, який ми написали, це свого роду погляд на вході користувача в переконавшись, що він повністю цифрова Це або це реальна плаваючою значення точки і т.п., в залежності від того, якої величини функціонувати ви використовуєте. 

Ось так. ДОБРЕ. Це був ковток але справа тут що причина у нас було ці навчальні диски по в тому, що на найнижчому рівні, Є тільки так багато речей, які може піти не так, що ми хотіли превентивно обробляти ці речі, звичайно, в Перші тижні класу, але тепер з Pset чотири і п'ять, і Pset за ви побачите, що це більше до Ви, але і ви більш здатні вирішення цих проблем види самостійно. Будь-які питання по GetString або GetInt? Так? 

АУДИТОРІЯ: Чому б вам подвоїти ємність буфера а не просто збільшення це по точної суми? 

Девід Малан: Хороший вопрос. Чому ми вдвічі ємність буфера, на відміну просто збільшуючи його деякої постійної величини? Це було дизайнерське рішення. Ми просто вирішили, що, тому що це, як правило, бути трохи дорожче часу мудро запитати операційна система на пам'ять, ми не хочете в кінцевому підсумку отримати в ситуація для великих рядків що ми просили ОС знову і знову і знову, і знову в Швидка зміна на пам'ять. Таким чином, ми просто вирішили, кілька довільно, але ми сподіваємося, що розумно, що, ви знаєте, що, давайте спробувати отримати попереду себе і просто продовжувати подвоювати його так, що ми мінімізуємо кількість разів ми повинні називати Танос або Realloc, але в цілому суд назвати в відсутність знаючи те, що користувачі, можливо, захочете, щоб ввести в. Обидва способи можуть бути спірним. Можливо добре. 

Отже, давайте поглянемо на пару інших побічних ефектів пам'яті, речі, які можуть піти не так і інструменти, які ви можете використовувати, щоб зловити ці види помилок. Виявляється всі з вас, навіть якщо check50 не сказав вам, як багато, пишу баггі Код, оскільки тижні один, навіть якщо всі тести є check50 пройшло, і навіть якщо ви і ваш TF супер впевнені, що Ваш код працює, як передбачалося. Ваш код був баггі або недоліки в тому, що всі з вас, за допомогою бібліотеки CS50, були витоку пам'яті. Ти питав операційну систему на пам'ять в більшості програм Ви написали, але ви ніколи не повернула його. Ви назвали GetString і GetInt і GetFloat, але з GetString, ви, ніколи не називав unGetString або Дайте Рядок Назад або т.п., але ми бачили, що робить GetString виділити пам'ять шляхом Танос або це Функція Realloc, який знаходиться всього дуже схожі по духу, і все ж, ми були просити операційну систему для пам'ять і пам'ять знову і знову але ніколи не даючи його назад. 

Тепер, як в сторону, то виходить, що коли програма завершує роботу, вся пам'ять автоматично звільняється. Таким чином, це не було величезну справу. Це не збирається зламати IDE або повільно речі вниз, Але коли програми не як правило, витік пам'яті і вони працюють протягом тривалого часу. Якщо ви коли-небудь бачили дурна маленька пляжний м'яч в Mac OS або пісочний годинник У Windows, де це вид уповільнення або думати або думати або просто дійсно починає щоб сповільнитися, дуже можливо, може бути результатом витоку пам'яті. Програмісти, які писали програмне забезпечення ви використовуєте просити операційну систему для пам'яті кожні кілька хвилин, щогодини. Але якщо ви виконавши Програмне забезпечення, навіть якщо це звести до мінімуму у вашому комп'ютері протягом декількох годин або днів поспіль, Ви могли б просити більше і більше пам'яті і ніколи не використовувати його насправді і так що ваш код може бути, або програми можуть бути витік пам'яті, і якщо ви починаєте витік пам'яті, їсти менше пам'яті для інших програм, і ефект в уповільнити все вниз. 

Тепер, це, безумовно, один з Найбільш жорстокі програми Ви будете мати можливість працювати в тій CS50 а його вихід ще більш езотерична, ніж брязкіт Або зробити або будь-якої команди Програми лінії ми запускаємо раніше, але На щастя, вбудовані в його виході це деякі супер корисні поради, що буде корисна як для Pset чотирьох або, звичайно, Pset п'ять. Так Valgrind є інструментом який може бути використаний, щоб подивитися витоків пам'яті у вашій програмі. Це відносно просто працювати. Ви запускаєте Valgrind, а потім, навіть хоча це трохи багатослівний, тире перевірка витік тире дорівнює повній, а потім точка слеш і ім'я вашої програми. Так Valgrind буде запустити програму і в самому кінці своєї програми працює, перш ніж він іде і дає вам ще підкажіть, він збирається для аналізу Програма поки вона бігла і сказати, що ти ви витік будь-яка пам'ять і ще краще, ти Touch Memory, що не належить вам? Він не може зловити всі, але це дуже добре при лові більшість речей. 

Так ось приклад моєї пробігши ця програма, пробігши Valgrind, на програму під назвою пам'яті, і я збираюся виділити рядки, які в кінцевому рахунку, представляє для нас інтерес. Так що ще більше відволікатися що я видалений з слайда. Але давайте подивимося, що це Програма здатна сказати нам. Він здатний розповідати нам речі як недійсним запису розміром 4. Іншими словами, якщо ви торкаєтеся пам'ять, зокрема 4 байт пам'яті що ви не повинні мати, Valgrind можу сказати вам, що. Невірний записи розміром 4. Ви торкнулися чотири байти що ви не повинні мати. Де ти це зробив? Це краса. Точка пам'яті з лінії 21, де вас облажались, і саме тому це корисно. Багато чого, як GDB, він може допомогти вказати вам на помилки фактичного. 

Тепер, цей трохи більше багатослівний, якщо не плутаю. 40 байт 1 блоків, безумовно, втратили у втраті записи 1 з 1. Що це означає? Ну, це просто означає, що ви просили 40 байт і ти ніколи не дав його назад. Ви назвали Танос або ви назвати GetString і операційна система не дав вам 40 байт, але ви ніколи не звільнені або звільнені, що пам'ять, і бути справедливими, ми ніколи не показуємо Ви, як віддати пам'ять. Виявляється, є супер проста функція називається вільним. Приймає один аргумент, річ Ви хочете, щоб звільнити або віддати, але 40 байт, мабуть, у цій програмі були втрачені в рядку 20 пам'яті точка гр. 

Отже, давайте подивимося цю програму. Це супер марно. Це тільки демонструє це конкретна помилка. Отже, давайте поглянемо. Ось основні і головні, повідомлення, дзвінки функція називається F, а потім повертається. Так що не все, що цікаво. Що е робити? Зверніть увагу, я не став з прототипом. Я хотів, щоб зберегти код якомога менше. Так що я поклав п вище основної і це нормально, звичайно, для коротких програм, як це. Так е нічого не повертає і робить не взяти що-небудь, але це зробити. Це заявляє, подібно в прикладі Binky, покажчик називається х, що відбувається зберігати адресу в міжнар. Так от ліва сторона. В англійській мові, що є Права робити? Хто-небудь? Що це робить для нас? Так? 

АУДИТОРІЯ: [нерозбірливо] разів розмір з Int що в 10 разів більше, ніж [нерозбірливо] Девід Малан: Добре, і дозвольте мені підвести підсумок. Так виділити достатньо місця для 10 чисел або 10, що розміром з Int, це чотири байти, тому в 10 разів 4 40, так що з правого боку, що я виділений це дати мені 40 байт і зберегти адресу першого байта в х. А тепер, нарешті, і ось, де ця програма глючить, що так з лінії 21 на основі цієї логіки? Що сталося з лінією 21? Так? АУДИТОРІЯ: Ви не можете індекс у х [нерозбірливо]. Девід Малан: Так. Я не повинен індекс в х, як, що. Так синтаксично, це нормально. Що приємно, так само, як вам може відноситися до імені масиву як ніби це покажчик, аналогічно Ви можете лікувати покажчик як ніби це масив, і тому я можу синтаксично говорять щось х кронштейн, кронштейн х я, але 10 є проблематичним. Чому? 

АУДИТОРІЯ: Тому що це не всередині. 

Девід Малан: Це не всередині цього шматка пам'яті. Що найбільше значення я повинен класти в цих квадратних дужках? До 9 9, 0. Через нульовий індексації. Так від 0 до 9 буде в порядку. Кронштейн 10 не хорошо, і але, нагадаємо, однак, кожен раз, Я, здається, щоб спробувати зробити CS50 IDE аварії, набравши в фіктивних цінностей, це не завжди співпрацювати, і, дійсно, часто пощастить тільки тому, що Операційна система не Ви помітите, що трохи пройти деякий шматок пам'яті, тому що ви залишилися в технічно Ваш сегмент, але про це в класі операційних систем, і так щось на зразок цього може дуже легко залишитися непоміченими. Ваша програма ніколи не буде врізатися послідовно, але, можливо один раз на деякий час. 

І так давайте спробуємо Valgrind на це, і ось де ми перевантажені по виході на мить. Так що перевірку на витік пам'яті Valgrind дорівнює повній пам'яті точка слеш. І ось чому я обіцяю це розтрощити. Ось те, що Valgrind, ось що програміст, кілька років ago- вирішив, що це буде хороша ідея, для виходу виглядати. Отже, давайте розібратися в цьому. Так всю дорогу на лівій сторона без поважної причини ідентифікатор процесу програми ми просто запустити, унікальний ідентифікатор для програми ми просто бігли. Ми видалили, що з слайд, але це деяка корисна інформація тут. 

Давайте прокрутки до самого верху. Ось де ми почали. Так що це не все, що багато чого вихід. Ось, що пишуть недійсним розмір 4 на лінії 21. Ну, те, що було 21 лінія? Лінія 21 була точно це і є сенс що я перебуваю в валідності писати 4 байта, тому що я намагаються поставити цей ціле, який може бути що завгодно, це просто відбувається, щоб бути нулю, але я намагаюся покласти його на місці що не належить мені. Більше того, тут, 40 байт в одному блоки, безумовно, втратив у запису 1. Це тому, що, коли я називаю Танос тут, я ніколи не звільнить пам'ять. 

Так як ми можемо це виправити? Дозвольте мені йти вперед і бути трохи безпечніше і робити там 9, і нехай мене тут безкоштовно X. Це нова функція на сьогоднішній день. Якщо зараз я повторно зробити точковий пам'яті межу, давайте працювати Valgrind на нього знову, збільшити моє вікно і натисніть Enter. Тепер, це добре. Вони ховають хороші новини всього цього виходу. Всі блоки купи були вільні. Ми повернемося до того, що купи є, але ніяких витоків не можливо. Так що це просто ще один інструмент для вашого набору інструментів з якою ви можете почати зараз знайти помилки, як, що. 

Але давайте подивимося, що більше може піти не так тут. Давайте перехід зараз насправді вирішити проблему. Як осторонь, якщо це позбавить трохи плутанини або напруженості, тепер це смішно. Так. Це дуже добре. Тому що покажчики адреси та адреси як правило, за угодою написано шістнадцятковому вигляді. Ха-ха, це смішно сьогодні. У всякому разі, так що давайте прямо зараз насправді вирішити проблему. Це було супер, супер низького рівня досі, і ми можемо насправді корисно речі з цих низькорівневих деталей. 

Таким чином, ми ввели кілька тижнів тому поняття масиву. Масив був хороший, тому що важко очистити наш код тому що, якщо ми хотіли, щоб написати Програма з декількома студентами або кілька імен і вдома, і гуртожитку і коледжів, і все, що, ми могли б зберігати все більш чисто всередині масиву. Але запропонувати один недолік масиву досі. Навіть якщо ви не страждали самі в програмі, просто інстинктивно, те, що це погано про масиві, може бути? Я чув деякі шуми. АУДИТОРІЯ: Це складно змінити розмір. Девід Малан: Важко змінити розмір. Ви не можете змінити розмір масиву, насправді, як такі в C. Ви можете виділити ще один масив, перемістити всі від старого в нове, і в даний час є якийсь додатковий простір, але це не як мова, як Java або Python або будь-яку кількість інших мови, з якими деякі з вас може бути знаком де ви можна просто продовжувати додавати речі нудоти до кінця масиву. Якщо у вас є масив Розмір 6, тобто його розмір, і так багато, як раніше ідея мають буфер певного розміру, ви повинні здогадатися з воріт який розмір ви хочете бути? Якщо ви вгадаєте занадто великий, ви витрачаєте простір. Якщо ви вгадаєте занадто малий, вам не може зберігати ці дані, принаймні, без багато роботи. 

Таким чином, сьогодні завдяки покажчиків, ми можемо почати шити разом наш власний звичай структури даних, і в Те, тут щось що виглядає трохи більше загадкові на перший погляд, але це те, що ми називаємо пов'язані Список, і його ім'я роду підсумовує це. Це список чисел, або в цей випадок, список номерів, але це може бути список що-небудь, але це пов'язано разом шляхом стрілок, і просто зробити припущення з тим, що техніка ми збираємося, щоб мати можливість зшити разом, зразок попкорна з різьбленням, пов'язаний списки прямокутники тут? Його номери? Що функція основна мова? 

АУДИТОРІЯ: Покажчик. 

Девід Малан: Покажчик. Таким чином, кожен з цих стріл тут представляє покажчик або просто адресу. Отже, іншими словами, якщо я хочу зберігати список номерів, Я не можу просто зберігати його, якщо я хочу здатність збільшуватися і зменшуватися мій структура даних в масиві. Тому мені потрібно, щоб мати трохи більш вишуканість, але помітити, що це картина вид припускає що якщо ви тільки що отримали маленькі теми підключення всі разом, ймовірно, це не так складно зробити простір між двома цими прямокутниками або два з цих вузлів, як ми почнемо називаючи їх, покласти в новий вузол, а потім з якоїсь нової нитки, просто канаву три вузли разом, перший, останній, і той, що ви тільки що вставили в середину. 

І дійсно зв'язаний список, на відміну від масиву, є динамічним. Він може рости і може скорочуватися і ви не повинні знати, або відходу заздалегідь, як багато даних ви збираєтеся бути зберігання, але, виявляється, ми повинні бути трохи обережні про те, як здійснити це. Отже, спочатку давайте розглянемо, як ми реалізуємо один з цих маленьких прямокутників. Це легко реалізувати Int. Ви просто говорите Int N, а потім Ви отримуєте 4 байта для Int, але як я можу отримати Int, назвемо його N, а потім покажчик, давайте називати його поруч. Ми могли б назвати це речі усе, що ми хочемо але мені потрібно структуру даних користувача. Так? 

АУДИТОРІЯ: Амперсанд [нерозбірливо]. 

Девід Малан: Так амперсанд ми будемо використовувати для отримати адресу вузла потенційно. Але нам потрібен ще Функція С в порядок щоб дати мені можливість створювати цей звичай прямокутник, цей звичай Мінлива, якщо хочете, в пам'яті. Залу: структура. Девід Малан: а структурою. Нагадаємо, минулого тижня, ми ввели структура, це відносно просте ключове слово, що дозволяє нам зробити такі речі, як це. З не прийшов з даними Структура називається студента. Він поставляється з Int і плавати і гольця і наприклад, але він не приходить зі студентами, але ми можемо створити тип даних студентом, студент структура, з цим синтаксисом тут. І ви побачите, що це знову і знову. Так що не турбуйтеся про запам'ятовування слів, але ключове слово, що це важливо, тільки той факт, що ми сказали, структура і тоді ми називали це студент і всередині студента було ім'я і будинок або загальний номер або тому подібне. 

І так ось сьогодні, давайте пропонувати це. Я додав кілька слів, але якщо я хочу здійснити цей прямокутник, що це отримав одночасно Int і А покажчик, ви знаєте, що я збирається оголосити на структуру під назвою вузол. Я також, всередині нього, хочу сказати, що вузол, цей прямокутник, має Int і ми будемо називати його п і вона має наступний покажчик. І це трохи багатослівний, але якщо ви думаєте про це, стрілки, які були на зображенні момент назад, якого типу даних? Де кожен з цих стрілок вказує який тип структури даних? Це не вказуючи тільки на міжнар на собі. Це вказує на Вся прямокутна річ і що прямокутна річ, ми сказали, називається вузлом. І таким чином, ми частково повинні рекурсивно визначити це таке що вузол, ми будемо говорити, буде містити Int під назвою п і покажчик називається поруч і тип структури даних, до яких що покажчик вказує, мабуть буде структура вузла. 

Так що це прикро, багатослівним і просто бути педантичним, причина, чому ми не можемо просто сказати, що це, що, чесно кажучи виглядає набагато більш читабельним, тому, що нагадаємо, що C читання речі зверху вниз, зліва направо. Це не поки ми не отримаємо крапку з комою що вузол ключове слово насправді існує. Так що, якщо ми хочемо мати таку циклічний посилання всередині даних Структура, що ми повинні зробити це, коли ми говоримо структури вузла у верхній частині, яка дає нам довгий шлях опису цього річ, то всередині ми говоримо структури вузла, а потім в самий останній лінії ми говоримо, все гаразд, С, до речі, просто зателефонуйте весь цей проклятий що вузол і зупинити використовуючи ключове слово-структуру в цілому. Так що це просто свого роду синтаксичний Хитрість в кінцевому рахунку, дозволяє, що нам створити те, що виглядає так само, як це. 

Так що, якщо ми припустимо тепер, ми можемо реалізувати цю річ в C, Як ми насправді почати обхід цього? Ну, справді, все, що ми повинні зробити, це ітерації зліва направо і просто вид вставити вузли або видаляти вузли або шукати речі там, де ми хочемо, але щоб зробити це, давайте йти вперед і зробити речі трохи більш реальним, тому що це був супер низького рівня досі. Хто буквально хотіли б бути першим? ДОБРЕ. Давай до. Як вас звати? 

Девід: Девід. Девід Малан: Девід. Приємно познайомитись. Я також. Добре. І нам знадобиться ряд 9. Не так добре, як по-перше, можливо. ОК, номер 9. Ряд 17, будь ласка. Дозвольте мені повернутися трохи далі. Кількість 22, будь ласка, і як про далі назад якщо я бачу будь-яких руки з усіма світла чи ні. Хтось зголосився бути прямо там. Ви хочете, щоб придумати? Ваше передпліччя примусово йде вгору. ОК, 17. 22. 26 спускається. Хтось ще хотіли б forcefully-- Давай до. Фактичний громадських засадах. 

Так дуже швидко, якщо ви, хлопці, могли б організувати самі просто хотів вузли на екрані. Дякую. І ви будете 26. Всі правильні і швидкі введення. Так що я Девід, і ви також? Девід: Девід. Девід Малан: А ви? Джейк: Джейк. ГУП: Сью. АЛЕКС: Алекс. РАФАЕЛЬ: Рафаель. Тейлор: Тейлор. Девід Малан: Тейлор. Відмінно. Таким чином, ці наші волонтери сьогодні і йти вперед і зрушення мало що шлях, і просто йти вперед і тримати проведення ваші номери, як ви чи ваші Перша ознака і лівою рукою, йти вперед і просто реалізувати ці стрілки, тільки так що ваша ліва рука буквально вказуючи на те, що ви повинні вказати на, і дати собі деяку кімнату так, що ми можемо наочно побачити ваші руки насправді вказуючи, і ви можете просто вказати роду на землю в порядку. 

Так от у нас є зв'язаний список одного, два, три, чотири, п'ять вузлів на початковому етапі, і зверніть увагу, у нас є ця спеціальна покажчик на початок, хто ключовим, тому що ми повинні відслідковувати з усього списку довжини якимось чином. Ці хлопці, навіть якщо вони залишаються направо, спиною до спини в пам'яті, вони дійсно можуть бути в будь-якому місці в пам'яті комп'ютера. Таким чином, ці хлопці могли б бути стоячи на будь-якому етапі і це нормально, так довго, як вони насправді, вказуючи один на одного, але тримати речі чистий і простий, ми будемо просто звернути їх зліва направо, як це, але не може бути масивні проміжки між цими вузлами. 

Тепер, якщо я хочу насправді вставити деякі нове значення, давайте йти вперед і робити це. У нас є можливість в даний час вибрати інший вузол. Скажіть давайте почнемо з mallocing 55. Чи буде хтось проти того Танос? ОК, давай до. Як вас звати? ВЕСЕЛКА: Радуга. Девід Малан: Радуга? Добре. Маллок Веселка. Давай до. Так що тепер ми повинні запитати себе, алгоритмічно, де ми можемо поставити 55. Таким чином, всі ми знаємо ,, очевидно, де вона, ймовірно, належить, якщо ми намагаємося щоб ця упорядковано і якщо ви, хлопці, може прийняти одне крок назад, тому ми не впасти етап, що було б здорово. Так насправді, Веселка, розпочати тут зі мною, тому що ми, як комп'ютер тепер може побачити тільки одну змінну одночасно. Таким чином, якщо це перший вузол. Зверніть увагу, що він не є вузлом, він просто покажчик, і ось чому він звертається, щоб бути тільки розмір покажчика, а не один з тих повних прямокутників. Отже, ми збираємося, щоб перевірити один на ітерація 55 менше, ніж 9? Немає. Є 55 менше 17? Немає. Менш 22? Менш 26? Менш 34? І ось тепер, очевидно, Веселка належить в кінці. Таким чином, щоб було ясно, і те, що був ваше ім'я, Тейлор? 

Тейлор: Тейлор. Девід Малан: Так серед Тейлор ліва рука і руки веселки тут, Чия рука повинна вказувати на те, що в Щоб вставити 55 в цьому списку? Що нам потрібно робити? Так? 

АУДИТОРІЯ: ручна Тейлора потрібно вказати лівої. 

Девід Малан: Точно. Так вставці вузла в кінці списку досить просто, тому що Тейлор просто повинен вказувати, а не на землі або ми будемо називати його порожнім, нуль є свого роду відсутність покажчика або спеціальний нульовий покажчик, ви будемо показувати з лівої руку на Веселка Веселка, а потім, де, якщо ваш лівий рука, ймовірно, вказують? Вниз Це не добре, якщо її рука начебто указувати тут або від свого роду будь яким чином. Це буде розглядатися значення сміття, але якщо вона вказує на деякі відомі значення, ми будемо називають його нуля або нульовою, це нормально тому що у нас в цьому термін і ми знаємо, що список в даний час завершена. 

Так що ще один відносно простий випадок? Чи можемо ми Танос 5? Давай до. Як вас звати? Тіффані: Тіффані. Девід Малан: Я вибачаюся? Тіффані: Тіффані. Девід Малан: Тіффані. Добре. Тіффані була malloced зі значенням 5. Давай до. Цей порівняно легко занадто, але давайте розглянемо порядок операцій в даний час. Це було досить легко з Тейлором в кінці. Номер 5, звичайно, менше, ніж 9, і тому ми повинні Давида, у нас є Тіффані, і те, що було ваше ім'я? 

Джейк: Джейк. 

Девід Малан: Джейк. Тіффані, Джейк, і Девід. Чия рука має бути оновлена ​​в першу чергу? Що ви хочете зробити тут? Там є пара можливих шляхів, але є також один або більше неправильні способи. 

АУДИТОРІЯ: Почніть з крайнього лівого. 

Девід Малан: Почніть з крайнього лівого. Хто крайній лівий тут тоді? АУДИТОРІЯ: По-перше. 

Девід Малан: ОК. Так що почніть з першої і де ви хочете оновити руки Давида, щоб бути? АУДИТОРІЯ: До 5. Девід Малан: ОК. Давид, точка, в п'яти або Тіффані тут, а зараз? 

АУДИТОРІЯ: Тіффані вказує на 9? Девід Малан: Совершенно, за винятком того, Бінки Глава тільки вид впав, чи не так? Тому що те, що трапилося з ця картина буквально? АУДИТОРІЯ: Ніщо не вказує. Девід Малан: Ніщо не є вказуючи на Джейка в даний час. Ми буквально осиротів 9 і 17, і ми буквально витік вся ця пам'ять, бо поновлення руку Давида перше, це в порядку, оскільки це правильно вказуючи на Тіффані зараз, але якщо ніхто не мав завбачливо вказують на Джейка, Потім ми втратили Сукупність цього списку. Отже, давайте скасувати. Так що це хороша річ, щоб спіткнутися, але давайте виправимо справжнє. Те, що ми повинні зробити в першу чергу, а? Так? 

АУДИТОРІЯ: Тіффані повинна вказувати на 9? Девід Малан: я не можу отримати так близько до вас. Хто повинен вказати на 9? 

АУДИТОРІЯ: Тіффані. 

Девід Малан: Гаразд. Так Тіффані повинна перша точка на 9. Так Тіффані повинні прийняти на однаковим значенням Давиду, який, здається, зайвим на мить, але це нормально, тому що тепер, по-друге крок, ми можемо оновити руку Давида щоб вказати на Тіффані, а потім, якщо ми тільки частково очистити речі як ніби це свого роду весни-як, ось це правильний вставки. Так відмінно. Так що тепер ми майже там. Давайте вставити один фінал значення як значення 20. Якби ми могли Танос одна заключний добровольцем? Давай до. Так що це одне трохи складніше. Але насправді, код ми писати, хоча і в усній формі, це все одно, що купу з, якщо умови зараз, вірно? Ми мали стан перевірки, якщо він належить Зрештою, може бути, з самого початку. Ми повинні якийсь цикл в знайти місце в середині. Так давайте зробимо це з тим, що ваше ім'я? 

ЕРІК: Ерік. 

Девід Малан: Ерік? Ерік. Приємно познайомитись. Отже, ми маємо 20. Менше п'яти? Немає. Менше дев'яти? Немає. Менш 17? Немає. ДОБРЕ. Він належить тут і Ваші імена знову є? ГУП: Сью. Девід Малан: Сью. АЛЕКС: Алекс. Девід Малан: Сью, Алекс, а? ЕРІК: Ерік. Девід Малан: Ерік. Чиї руки повинні отримати оновлення в першу чергу? 

АУДИТОРІЯ: Ерік. ДОБРЕ. Так Ерік повинен вказати на те, де? У 22. Добре. А тепер, що буде далі? Сью може вказувати на Еріка і тепер, якщо ви, хлопці, просто потіснитися, який прекрасний візуально, тепер ми зробили вставку. Так нехай тепер розглянемо питання, але спасибі так багато для наших волонтерів. Дуже добре зроблено. Ви можете зберегти ті, якщо вам подобається. І у нас є прекрасний подарунок, якщо прощальний ви кожен хотів взяти стрес м'яч. Дозвольте мені передати це вниз. Так що винос це? Це, здається, дивно оскільки ми маємо зараз представила альтернативою Масив, який не так обмежені на масив деякого фіксованого розміру. Вони можуть рости динамічно. 

Але так само, як ми бачили протягом декількох тижнів минуле, ми ніколи не отримаємо нічого безкоштовно, як, безумовно, є компроміс тут. Так з потенціалом зростання пов'язаний Список, це динамізм? Ця здатність рости і, чесно кажучи, ми могли б зробити видалення і ми могли б стиснути в міру необхідності. Яку ціну ми платимо? У два рази більше простору, в першу чергу. Якщо ви подивитеся на картину, більше не я зберігати список цілих чисел. Я зберігання списку цілі плюс покажчики. Так що я подвоєння кількості простору. Тепер, може бути, це не така велику справу 4 байта, 8 байт, але це, безумовно, може додати на великих наборів даних. Що інший недолік? Так? 

АУДИТОРІЯ: Ми повинні пройти їх один за одним. Девід Малан: Так. Ми повинні пройти їх один за одним. Ви знаєте, що ми відмовилися від цієї супер зручна функція квадратного кронштейна позначення, більш правильно відомий як довільного доступу, де ми можемо просто стрибнути до окремого елементу але тепер, якщо я досі мої добровольці тут, якби я хотів, щоб знайти № 22, я не можу просто перейти до кронштейн-то что-то. Я повинен дивитися на список, багато як наші приклади пошуку лінійно, щоб знайти номер 22. Таким чином, ми, здається, заплатили ціну там. Але, тим не менш, ми можемо вирішити інші проблеми. 

Насправді, дозвольте мені представити тільки пару візуальні ефекти. Так що, якщо ви були до Їдальня Mather недавно, ви пам'ятаєте, що їх стеки підносів, як це, ми запозичили їх з Анненберг перед класом. Таким чином, це стос тарілок, хоча, є представником насправді структури даних комп'ютерної науки. Існує структура даних в інформатиці Відомо, як стек, який дуже красиво піддається саме це візуально. Таким чином, якщо кожен з цих літаків НЕ лоток, але, як і ряд, і я хотів для зберігання номера, я може поставити один тут, і я міг би поставити інший сюди, і продовжити укладку число на верхній частині один одного, і те, що потенційно корисним про це це те, що це мається на увазі цієї структури даних? Яке число я можу витягнути в першу чергу найбільш зручно? Найбільш недавно висловився один там. 

Так що це те, що ми називаємо в інформатика структура даних ЛІФО. Останній прийшов, перший. І ми побачимо, незабаром, чому що може бути корисним, але зараз, просто розглянути власність. І це частково нерозумно, якщо ви думаєте, про те, як їдальня це робить. Кожен раз, коли вони чисті лотки і покласти свіжі з них на вершині, ви могли б раніше чистий але зрештою дуже брудний і запорошений лоток на самому дні якщо ви насправді ніколи не потрапити в нижній частині, що стек, тому що ви просто тримати покласти новий і чисті ті, на вершині цього. Те ж саме може статися в супермаркеті теж. Якщо у вас є вітрину молока і кожен раз CVS або той, хто отримує більше молока, ви просто засунути молоко у вас вже є на спині і Ви ставите нові попереду, Ви будете мати деякі досить огидно Молоко в кінці структури даних, тому що це завжди на дні або що те ж саме, це завжди на спині. 

Але є ще один спосіб думати про шикуються даних і, наприклад, цей. Якщо ви один з тих людей, хто любить вибудовуватися за межами Apple, магазини коли новий продукт поставляється з, ви, ймовірно, не використовуючи дані стека Структура, тому що ви відштовхне всіх, хто знаходиться шикуються, щоб купити деякі нові іграшки. Швидше за все, ви, ймовірно, з використанням які структури даних або яка система в реальному світі? Сподіваюся, це лінія, або більш правильно або більше британський, як, черги. І виходить, чергу також Структура даних в інформатиці, але черга має дуже відрізняється властивість. Це не ЛІФО. Останній прийшов, перший. Боже упаси. Це замість того, щоб FIFO. По-перше, першим пішов. І це добре Справедливості заради звичайно, коли ви шикуються до супер рано вранці. Якщо ви там спочатку, Ви хочете, щоб вийти спочатку в якості добре. 

І так всі ці дані структури, черги і стеки і грона інших, виявляється вас може думати про це, як тільки що масив. Це масив, може бути, фіксований розмір 4, але це було б бути свого роду добре, якщо ми могли б просто купа Лотки майже нескінченно високий, якщо ми є, що багато підноси або цифри. Так, може бути, ми хочемо, щоб використовувати зв'язаний список тут, але компроміс буде потенційно, що нам потрібно більше пам'яті, займає трохи більше часу, але ми не обмежують висоту стопки, так само, як вітрині Мазера може обмежити розмір стека, і таким чином, вони проектні рішення або варіанти, доступні для нас в кінцевому рахунку. Так що з цими даними структури, ми почали бачачи нові верхні межі потенційно на те, що раніше було супер швидко і де ми залишимо від сьогодні і де ми сподіваємося отримати в на середовище, ми будемо почати дивитися на даних Структура, що дозволяє нам шукати через дані в кінці часу журналу знову. І ми побачили, що, пам'ятаю, в нульовій тижня і один з бінарного пошуку або розриву і володарюй. Це повертається, і ще краще, Святий Грааль для цього середовище буде придумати з структура даних, яка працює дійсно або теоретично Постійна часу, в результаті чого це не має значення, скільки мільйони чи мільярди речей ми маємо в структурі даних, це буде взяти нас постійний час, може бути, один крок або два кроки або 10 кроків, але постійні числа кроків шукати в цій структурі даних. Це дійсно буде Святий Грааль але про це в середу. Побачимося тоді. 

[Грає музика]