[Powered by Google Translate] [Тиждень 6] [David J. Малан] [Harvard University] [Це CS50.] [CS50.TV] 

Це CS50, і це початок тижня 6, так що пару нових інструментів тепер доступні для вас, щоб скористатися перевагами, перша з яких називається CS50 стилю. Швидше за все, якщо ви схожі на мене чи будь-якого вчення хлопці, Ви, напевно, бачили програму, чий стиль виглядає трохи щось на зразок цього. Може бути, ви почнете різання деякі кути пізно вночі, або ви будете мати справу з ним пізніше, , А потім TF або CA приходить в робочий час. Тоді це важко для нас, щоб читати. Ну, цей код синтаксично правильні, і він буде компілювати, і вона буде реально працювати. Але це безумовно не 5 за стиль. 

Але тепер, якщо ми підемо в цей каталог тут- і зауважив, що у мене є conditions2.c- і я біжу цю нову команду, style50, на цей файл conditions2.c, Enter помітите, що він повідомив мені, що він був стилізований. Gedit зауважив, що файл був змінений на диску, і якщо я натискаю кнопку перезавантаження, всі ваші проблеми в даний час автоматизовані. [Оплески] Це одна з речей, які ми зробили в ці вихідні. Зрозумійте, що вона недосконала, тому що є певний код що він просто не зможе стилізувати відмінно, але розумію, що це зараз інструменту ви можете скористатися якщо тільки привести в порядок деякі з більш errantly розміщені фігурні дужки тощо. 

Але більш переконливим зараз CS50 перевірки. З CS50 перевірки, ви можете виконувати ті ж випробування коректності на свій власний код, що вчення хлопці здатні. Це утиліта командного рядка, яка йде зараз в прилад Як тільки ви update50 відповідно до PSET 4 специфікацій, а також використовувати його по суті, як це. Ви виконаєте команду check50. Потім ви передаєте в якості аргументу командного рядка, або більш відомий як комутатор або прапор. Як правило, речі, які мають дефіс називається перемикачем на програму командного рядка, так з вказуюче перевіряє, що ви хочете запустити. 

Тести, які ви хочете запустити визначені однозначно цей рядок, 2012/pset4/resize. Іншими словами, це просто довільне, але унікальна рядок , Які ми використовуємо, щоб однозначно ідентифікувати правильності PSET 4 в тестах. А потім ви задаєте пробіл список файлів, які ви хочете завантажити Перевірити, щоб CS50 для аналізу. Наприклад, якщо я йду на моє рішення тут Зміна розміру- Дозвольте мені відкрити великі вікна терміналу- і я йду вперед і запустити скажімо check50-з 2012/pset4/resize, а потім йти вперед і вказати імена файлів, Зміна розміру, а потім натисніть Enter, він стискає, Він завантажує, він перевіряє, і я просто не зміг цілу купу тестів. Той в червоному в лівому верхньому куті говорить, що Зміна розміру і BMP існує. Це був тест. Таке питання ми поставили. І це нещасні, тому що відповідь була помилковою. Білий текст нижче він говорить очікується bmp.h існувати, і це просто моя вина. Я забув, щоб завантажити його, так що мені потрібно завантажувати як файли, Зміна розміру і bmp.h. Але тепер помічаю всі інші тести в жовтий, тому що вони не працюють, і так смайлик вертикально, тому що він не є ні щасливим, ні сумно, але у нас є для усунення цього питання в червоному перед тими, інших перевірок буде працювати. 

Дозвольте мені виправити це. Дозвольте мені масштаб і повторіть це, на цей раз з bmp.h також в командному рядку, Enter, і тепер, якщо все піде добре, він збирається перевірити, а потім повертають результат, затримайте дихання- Все зелене, а це значить, що я роблю дуже добре на PSET 4 до цих пір. Ви можете бачити і вивести з описового тексту тут точно, що це ми перевірили. Ми протестували перший же файли існують? Ми тоді протестовані робить Зміна розміру компіляції? Потім ми перевірили це не розмір 1x1 піксель BMP, коли п, зміна розміру фактор, 1. Тепер, якщо ви не знаєте, що п, ви будете тільки ви зануритися в PSET 4, але це просто розсудливість перевірити, щоб переконатися, що ви не зміна розміру Зображення взагалі, якщо зміна розміру коефіцієнт дорівнює 1. Якщо ж, навпаки, він змінює 1x1 піксель в піксель 1x1 2x2 BMP, щоб правильно при п = 2, то аналогічно, мій формує відповідно. 

Коротше кажучи, це означало, один, приймати перетину пальців з рівняння право, перш ніж подати PSET. Ви будете точно знати, що ваш TF скоро дізнаємося коли ви йдете про відправку деяких з цих наборів проблеми, а також педагогічні мотивація дійсно поставити можливість перед вами, так що, коли ви знаєте, апріорно що є помилки в коді і тестах, які не пройшли, Ви можете помістити в більш ефективні часу попереду, щоб вирішити ці проблеми , А не втрачати очки, отримати зворотній зв'язок від ваших TF, , А потім йти, "Ах", як я зрозумів це. Тепер принаймні є інструмент, щоб допомогти вам знайти це. Це не збирається вказати, де помилка, але вона скаже вам, , Що є симптомом його. 

Тепер розумію, тести не є вичерпним. Просто тому, що ви отримуєте екран, повний зелених смайликів не означає, що ваш код є досконалою, але це не означає, що вона пройшла певні випробування, передбачені в специфікації. Іноді ми не випустимо перевірок. Наприклад, детективний роман, одним з аспектів PSET 4, це свого роду розчарування, якщо ми даємо вам відповідь на питання, що це таке, і є кілька способів, щоб показати хто ця людина в тому, що червоні шуму. У специфікації будуть завжди вказувати в майбутньому для PSET 5 уперед Які види контролю існують для вас. Ви помітите, що це за білі URL в нижній частині. На даний момент це всього лише діагностичний вихід. Якщо ви відвідаєте цю адресу, ви отримаєте цілу купу божевільних, загадкові повідомлення що ви можете переглядати, але це в основному для співробітників так що ми можемо діагностувати і налагоджувати помилки в check50 себе. 

Без церемоній, давайте перейдемо туди, де ми зупинилися. CS50 бібліотеці ми вважали само собою зрозумілим протягом декількох тижнів, але потім на минулому тижні, ми почали пілінг тому один з шарів його. Ми почали відклавши рядок на користь того, що замість цього? [Студенти] Char. Char *, який був символ * весь цей час, але тепер ми не повинні вдавати, що це фактичний тип даних рядок. Швидше, це був синонім роду для символів *, і рядок являє собою послідовність символів, Так чому це має сенс представляти рядки як символ * з? Що означає символ * представляє в контексті цієї концепції рядки? Так. >> [Студент] перший символ. Добре, перший символ, але не зовсім перший символ. Це-[Студенти] адресу. Добре, адреса першого символу. Все, що необхідно для подання рядків в пам'яті комп'ютера це просто унікальний адресу самого першого байта. Вам навіть не потрібно знати, як довго це тому що, як ви можете зрозуміти, що з динамічно? [Студент] довжина рядка. Ви можете зателефонувати довжина рядка, відмінно, але як робота довжину рядка? Що він робить? Так. [Студент] Продовжуйте, поки не отримаєте нульовий символ. Так, точно, він просто виконує ітерації з циклу, в той час як цикл, незалежно від * до кінця, і в кінці представлено на \ 0, так званої нульової символ, н, Не плутати з нульовим, який є дороговказом, який вступить в розмову знову сьогодні. 

Ми очищені назад шаром GetInt, і тоді ми поглянули на GetString, і нагадаємо, що обидві ці функції, або дійсно, GetString, було використання певних функцій насправді розібрати, тобто, читати і аналізувати, введених користувачем. І що це за нова функція? Scanf або Sscanf. Це насправді відбувається в кілька різних ароматів. Там в SCANF, є Sscanf, є fscanf. Зараз, однак, давайте зосередимося на один найбільш легко проілюструвати, і дозвольте мені йти вперед і відкрити в приладі Файл, як це, scanf1.c. Це супер проста програма, але що робить щось, що ми ніколи не робили без допомоги CS50 бібліотеки. Це стає Int від користувача. Як це працює? Ну, а в рядку 16 є, помітите, що ми заявляємо Int називається х, і в цей момент в історії, що таке значення х? [Нерозбірливо відповідь студента] [David M.] Право, хто знає, сміття значення потенційно, так і в 17, ми просто повідомити користувачеві дайте мені номер, будь ласка, і крок 18, де це стає цікавим. Scanf здається запозичувати ідеї з Printf в тому, що він використовує формат кодів в лапки. % D, звичайно, десяткове число. Але чому я проходить в & х, а не просто х? Колишній правильно. Так. [Нерозбірливо відповідь студента] Саме, якщо мета цієї програми, як і функція GetInt себе, , Щоб отримати ціле число від користувачів я можу передати функції всі змінні, я хочу, але якщо я не передавати їх по посиланню або за адресою або за вказівником, все синонімом для цілей сьогоднішньої, то ця функція не має можливості змінювати вміст цієї змінної. Це повинно передати в копії, як баггі версії своп що ми говорили про кілька разів тепер. 

Але замість цього, роблячи & х, я буквально проходить в чому? [Студент] адресу. >> Адресу х. Це схоже на малювання карти для функції називається SCANF і говорять тут, ці напрямки шматок пам'яті в комп'ютері що ви можете піти зберігати деяке ціле дюйма Для того, щоб Sscanf досі зробити це який оператор, що частина синтаксису цього доведеться використовувати навіть якщо ми не можемо бачити, тому що хтось інший написав цю функцію? Іншими словами - що це таке? [Студент] X читати. Там збирається бути деякий читання, але тільки у відношенні х тут. Якщо SCANF в даний час передається адреса х, Синтаксично, що оператор зобов'язаний існувати десь Усередині реалізації SCANF так, що SCANF дійсно може написати номер 2 за цією адресою? Так, так *. Нагадаємо, що * це наш оператор разименованія, яка по суті означає піти туди. 

Після того як ви передали адреси, як в даному випадку, SCANF, ймовірно, якщо ми насправді оглянув його вихідний код- робить * х або еквівалент насправді піти за цією адресою і покласти деяке значення там. Тепер, як і про те, як SCANF отримує введення з клавіатури, ми махаємо руками за сьогодні. Просто припустимо, що операційна система дозволяє Sscanf говорити з клавіатури користувачем, але на даний момент зараз в рядку 19, Коли ми просто роздрукувати х, це, здається, випадок що SCANF поставив Int х. Це точно, як SCANF працює, і згадати останній тиждень це точно, як GetString і GetInt та інших його сімейство функцій в кінцевому підсумку працює, хоча і з невеликим дисперсії, як Sscanf, що означає сканування рядків замість клавіатури. Але давайте поглянемо на невеликої різниці в цьому. У scanf2, я дійсно облажався. Що не так, і я сховаю коментар, що пояснює, як багато- що не так з цією програмою, версія 2? Будьте як технічні можливості на цей раз. Це виглядає досить добре. Це приємно відступу, але- Добре, а як щодо давайте скорочувати його до коротких запитань? Лінія 16. Що робити лінії 16 в точною, але технічний англійську мову? Отримання трохи ніяково. Так, Майкл. [Студент] Це вказує на перші літери рядків. 

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

Рядок 18 є своєрідною знайомий тепер в тому, що ми тільки що бачили дисперсія цього але з іншим кодом формату, так і в рядку 18, ми говоримо SCANF тут є адресою блоку пам'яті. Я хочу, щоб ти дзвонив в рядок, як це мається на увазі% З, але проблема в тому, що ми не зробили пару речей. Що одна з проблем? [Студент] Це спроба разименованія нульового покажчика. Добре, нульові або просто в іншому випадку невідомі покажчиків. Ви вручення SCANF адресу, але ви тільки що сказали хвилину тому , Що адреса сміття значення, тому що ми насправді не присвоїти йому ні до чого, і тому ви говорите SCANF ефективно йти покласти рядки тут, але ми не знаємо, де тут ще є, так що ми, власне, не виділеної пам'яті для буфера. Крім того, що ви теж навіть не кажу SCANF? Припустимо, що це був шматок пам'яті, і це не було сміття значення, але ви все ще не говорив SCANF щось важливе. [Студент] Де насправді, амперсанд. Амперсанд, тому в даному випадку, це нормально. Тому що буфер уже оголошений як покажчик з * частину синтаксису, ми не повинні використовувати амперсанд тому що це вже адресу, але я думаю, що я чув, це тут. [Студент] Як він великий? Добре, що ми не говоримо SCANF, наскільки великий цей буфер, який означає, що навіть якщо буфер був покажчик, Ми говоримо SCANF, покласти тут рядок, Але тут може бути 2 байти, це може бути 10 байт, він може бути мегабайт. Scanf поняття не має, а тому, що це шматок пам'яті Імовірно, це не рядок, поки немає. Це всього лише рядок, як тільки ви писати символи і \ 0 до цього шматок пам'яті. Тепер це лише деякі шматок пам'яті. Scanf не буде знати, коли перестати писати за цією адресою. 

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

Ось, я кажу SCANF ось шматок пам'яті. На цей раз, це насправді частина пам'яті, Але чому цієї програми досі вразливостям? Що сталося ще? Я вже говорив, дайте мені 16 байт, але- [Студент] Що робити, якщо вони друкують більш ніж в 16? Ось саме, що якщо користувач вводить 17 символів або 1700 символів? У самому справі, давайте подивимося, якщо ми не можемо спіткнутися цю помилку зараз. Це краще, але не ідеально. Дозвольте мені йти вперед і працювати scanf3 зробити для компіляції цієї програми. Дозвольте мені виконати scanf3, String ласка: привіт, і ми, здається, в порядку. Дозвольте мені спробувати трохи більше одного, привіт. Добре, давайте зробимо привіт, як справи, Enter. Отримання виду пощастило тут, скажімо, привіт як справи. Чорт візьми. Отже, нам пощастило. Давайте подивимося, якщо ми не можемо це виправити. Ні, вона не збирається дозволити мені скопіювати. Давайте спробуємо це знову. Гаразд, стояти осторонь. Ми побачимо, як довго я можу прикидатися, щоб зосередитися в той же час зробити це. Чорт візьми. Це досить необхідності, насправді. Там ми йдемо. Точка зробив. 

Це, ніяково, хоча воно і є, він також є одним з джерел більшу плутанину При написанні програм, які мають помилки, тому що вони проявляються Тільки раз в той час іноді. Реальність така, що навіть якщо ваш код повністю зламана, це може бути повністю зруйнована раз в той час тому що іноді, по суті, відбувається те, виділяє операційної системи трохи більше пам'яті, ніж вам дійсно потрібно по будь-якої причини, і так ніхто не використовує пам'ять відразу після шматок з 16 символів, так що якщо ви йдете в 17, 18, 19, незалежно, це не така велика проблема. Тепер, комп'ютер, навіть якщо вона не звалиться в той момент, в кінцевому підсумку може використовувати Байт номер 17 або 18, або 19 на щось інше, У цей момент ваші дані, які ви створили, хоча і надмірно довгими, буде втрачено потенційно деякі інші функції. Це не обов'язково залишиться недоторканим, але це не обов'язково викликати сегменті вина. Але в даному випадку, я, нарешті, надали достатньо символів що я суттєво перевищив мої сегмент пам'яті, і бац, Операційна система сказала: "Вибач, це не добре, помилки сегментації." 

І давайте подивимося тепер, якщо те, що залишається тут, в моєму каталогу помітив, що у мене є цей файл тут, ядро. Зверніть увагу, що це знову закликав дамп пам'яті. По суті, це файл, який містить вміст пам'яті програми в точці, в якій він розбився, і просто спробувати маленький приклад тут відпустити мене тут і запустити GDB на scanf3 а потім вказати третій аргумент називається ядром, і помітити тут, що якщо я перераховую код, ми зможемо, як звичайно, з GDB, щоб почати ходити через цю програму, і я можу запустити його, і як тільки я потрапив-як з кроком команди в GDB- Як тільки я потрапив в потенційно баггі лінії після введення в величезній рядку, Я зможу насправді визначити його тут. Детальніше про це, хоча, в розділі з точки зору дампи і т.п., так що ви можете копатися всередині дампа і подивитися, на якому рядку програми не ви. Будь-які питання, то на покажчики й на адреси? Тому що сьогодні, ми збираємося почати приймати як належне, що ці речі існують і ми точно знаємо, що вони є. Так. 

[Студент] Чому ви не повинні поставити амперсанд поруч з частини- Хороше питання. Чому у мене не було поставити амперсанд поруч з масив символів, як я зробив раніше з більшістю наших прикладах? Коротка відповідь полягає в масивах трохи особливим. Ви можете подумати, буфер, що насправді є адресою, і так уже сталося, щоб бути так, що площа позначення кронштейна є зручним, так що ми можемо піти в кронштейн 0, кронштейн 1, Кронштейн 2, не вдаючись до використання * позначень. Це трохи білого брехня, тому що масиви і покажчики , Насправді, трохи по-іншому, але вони можуть часто, але не завжди використовуються як взаємозамінні. Коротше кажучи, коли функція очікує покажчик на ділянку пам'яті, Ви можете або передати його адресу, який був повернутий Танос, і ми побачимо, Танос знову незабаром, або ви можете передати його ім'я масиву. Ви не повинні робити амперсанд з масивами, тому що вони вже істотно хотів адрес. Це один виняток. У квадратних дужках зробити їх особливими. 

Не могли б ви покласти амперсанд поруч з буфером? Не в цьому справа. Це не буде працювати, тому що, знову ж таки, цього куточка випадку де масиви насправді не зовсім адреси. Але ми, можливо, повернемося до цього незабаром з іншими прикладами. Давайте спробуємо вирішити проблему тут. У нас є структури даних, які ми використовували протягом деякого часу відомо як масив. Справа в точку, це те, що ми просто не було. Але масиви мають деякі плюси і мінуси. Масиви є хорошим чому? Що одна річ, яка вам подобається, в тій мірі, вам подобається масиви про масивах? Що зручно про них? Що переконливим? Чому ми введемо їх в першу чергу? Так. [Студент] Вони можуть зберігати великий обсяг даних, і вам не доведеться використовувати всю річ. Ви можете використовувати розділ. Добре, з масивом можна зберігати велику кількість даних, і вам не обов'язково використовувати все це, так що ви можете overallocate, що може бути зручно, якщо ви не знаєте заздалегідь, скільки чогось чекати. 

GetString є прекрасним прикладом. GetString, написані нами, поняття не має, скільки символів очікувати, Тому той факт, що ми можемо виділити шматки безперервної пам'яті це добре. Масиви також вирішити проблему, ми побачили пару тижнів тому, тепер , Де ваш код починає перетвориться на щось дуже погано розроблена. Нагадаємо, що Я створив студент на ім'я Девід структури, а потім, що було насправді альтернатива, хоча, до того змінної ім'я та іншу змінну, я думаю, будинки, і інша змінна ID, тому що в цій історії я тоді хотів представити щось інше Роб подобається в програмі, так що потім я вирішив почекати хвилину, Мені потрібно перейменувати ці змінні. Давайте називати моє name1, ID1, House1. Давайте назвемо Роба name2, house2, ID2. Але почекайте хвилинку, що про Томмі? Тоді у нас було ще три змінні. Ми ввели когось іншого, чотири набори змінних. Світ почав заплутатися дуже швидко, таким чином, ми ввели структури, і те, що переконливих про структуру? Що структуру C дозволити вам зробити? Це дуже незручно сьогодні. Що? >> [Нерозбірливо відповідь студента] Так, зокрема, ЬурейеЕ дозволяє створити новий тип даних, і структури, структури ключових слів, дозволяє інкапсулювати концептуально пов'язані елементи даних разом і після цього називати їх чимось на зразок студента. 

Це було добре, тому що тепер ми можемо змоделювати набагато більше роду концептуально відповідає поняттю студента в змінну , А не довільно мають один для рядка, по одному для ID, і так далі. Масиви приємно, тому що вони дозволяють почати прибирання нашого коду. Але те, що є і зворотна сторона тепер масиву? Що ви можете не робити? Так. [Студент] Ви повинні знати, наскільки вона велика. Ви повинні знати, наскільки він великий, так що це вид болю. Ті з вас, з досвідом програмування знаємо, що в багатьох мовах, як Java, ви можете попросити шматок пам'яті, зокрема масиву, наскільки великий ти, з довжиною, власність, так би мовити, і це дійсно зручно. У C, ви не можете навіть назвати StrLen на загальному масиві тому що StrLen, як слово має на увазі, тільки для рядків, і ви можете з'ясувати довжину рядка, тому що цю людину конвенції наявності \ 0, але масиві, в більш загальному, це просто шматок пам'яті. Якщо це масив цілих чисел, там не буде якийсь особливий характер В кінці вас чекає. Ви повинні пам'ятати, довжина масиву. Ще одним недоліком масиву підняв свою голову в GetString себе. Що ще одним недоліком масиву? Сер, тільки ти і я сьогодні. [Нерозбірливо відповідь студента] >> Це що? Він оголошений у стеці. Добре, заявив в стеці. Чому б вам не подобається? [Студент] Тому що він буде використовувати повторно. Він отримує повторно. Добре, якщо ви використовуєте масив для виділення пам'яті, Ви не можете, наприклад, повернутися, тому що це в стеці. Добре, що це недолік. А як щодо ще одного з масивом? Після того як ви виділите її, ти ніби п'яний, якщо вам потрібно більше місця , Ніж у масиву. 

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

Тепер, тільки заковика в тому, що це майже відчуває, як у мене цілий букет різних змінних. Це відчуває себе п'ять різних змінних потенційно. Але що, якщо ми вкрасти ідею з рядків яким ми якось пов'язати ці речі разом концептуально, а що, якщо я це зробив? Це мій дуже погано звертається стрілки. Але припустимо, що кожна з цих ділянок пам'яті вказав на одного, і цей хлопець, у якого немає брата, щоб його права, не має такого стрільця. Це насправді те, що називається пов'язаного списку. Це нова структура даних, яка дозволяє виділити шматок пам'яті, потім інша, потім ще, потім ще, в будь-який час ми хочемо під час виконання програми, і ми пам'ятаємо, що всі вони так чи інакше пов'язаних буквально ланцюжок їх разом, і ми зробили це наочно тут зі стрілкою. Але в коді, яким буде механізм, через який ви могли б якимось чином підключити, майже як Scratch, один шматок на інший шматок? Ми могли б використовувати покажчик, чи не так? Тому що насправді стрілка, яка походить з верхнього лівого квадрата, цей хлопець тут, щоб цю, може міститися всередині цього квадрата Не тільки деякі цілі, а не тільки деяких символів, але що, якщо я насправді виділив трохи додаткового простору, так що тепер, Кожен з моїх ділянок пам'яті, навіть якщо це коштуватиме мені, зараз виглядає трохи більш прямокутної, де одна з ділянок пам'яті Використовується для номер, як номер 1, а потім, якщо цей хлопець зберігає номер 2, ця інша частина пам'яті використовується для стрільця, або більш конкретно, покажчик. І нехай я зберігаю № 3 тут в той час як я використовую це, щоб вказати на того хлопця, і тепер цей хлопець, припустимо, я хочу тільки три таких ділянок пам'яті. Я намалюю лінію через які, із зазначенням нульовий. Існує ніякого додаткового характеру. 

Дійсно, це, як ми можемо йти про реалізацію те, що називається зв'язний список. Зв'язаний список нову структуру даних, і це сходинка до багато любителів структур даних, які починають вирішувати проблеми уздовж лінії Facebook тип проблеми і Google тип проблеми де у вас є величезні набори даних, і він більше не ріже зберігати всі безперервно і використовувати щось подібне лінійний пошук або навіть щось подібне до бінарного пошуку. Ви хочете ще краще працює рази. У самому справі, одна з Святої Grails ми поговоримо пізніше на цьому тижні або в наступному алгоритм, час виконання якої постійно. Іншими словами, вона завжди приймає стільки ж часу, незалежно від того, наскільки великий вхід, і дійсно було б переконливим, навіть більше, ніж те, логарифмічна. Що це на екрані тут? Кожен з прямокутників саме те, що я тільки що намалювали від руки. Але справа все шляху зліва спеціальної змінної. Це збирається бути одним покажчиком, тому що той Гоча з пов'язаного списку, так як ці речі називаються, є те, що у вас є, щоб повісити на один кінець пов'язаного списку. 

Так само, як з рядком, ви повинні знати адресу першого символу. Те ж угода для пов'язаних списків. Ви повинні знати адресу першого блоку пам'яті тому що звідти можна добратися до будь-якого іншого. Даунсайд. Яку ціну ми платимо за цю універсальність мають динамічне значну структуру даних, що якщо ми коли-небудь знадобиться більше пам'яті, штраф, просто виділити ще один шматок і намалюйте стрілки від старого до нового хвості списку? Так. [Студент] Це займає приблизно вдвічі більше простору. Вона займає вдвічі більше місця, так що це виразно недолік, і ми бачили це Компроміс, перш ніж між часом і простором і гнучкість де в даний час, нам не потрібно 32 біт для кожного з цих чисел. Нам дійсно потрібно 64, 32 числа і 32 для покажчика. Але почекайте, у мене є 2 гігабайти оперативної пам'яті. Додавання ще 32 біта тут і тут не здається, що великі угоди. Але для великих наборів даних, це безперечно додає буквально в два рази більше. Що ще одним недоліком зараз, або те, що функції ми здаватися, якщо ми уявимо списки речей з пов'язаного списку, а не масив? [Студент] Ви не можете пройти у зворотному напрямку. Ви не можете пройти у зворотному напрямку, так що ви вид різьбових якщо ви йдете зліва на право використання циклу або час циклу а потім розумієш: «О, я хочу повернутися в початок списку". Ви не можете, тому що ці покажчики йти тільки зліва направо, як стрілки показують. 

Тепер, ви могли згадати початок списку з іншої змінної, але це складність мати на увазі. Масивів, незалежно від того, як далеко ви підете, ви завжди можете зробити мінус, мінус, мінус, мінус і повернутися, звідки ви прийшли. Що ще одним недоліком тут? Так. [Нерозбірливо запитання студента] Можна, таким чином, ви дійсно тільки що запропонував структуру даних, звану двічі зв'язаний список, І дійсно, можна додати ще один покажчик на кожен з цих прямокутників , Який іде в іншому напрямку, потенціал зростання яких Тепер ви можете пройти туди і назад, Недоліком який в даний час ви використовуєте в три рази більше пам'яті, ніж ми звикли а також ускладнення з точки зору коду, ви повинні написати, щоб отримати це право. Але все це, можливо, дуже розумні компроміси, якщо звернення є більш важливим. Так. [Студент] Ви також не можете мати 2D пов'язаного списку. Добре, ви не можете дійсно є 2D зв'язаний список. Ви могли б. Це не так просто, як масив. Як і масив, ви відкриваюча дужка, закрита дужка, відкриваюча дужка, закрита дужка, , І ви отримаєте деякий 2-мірну структуру. Ви можете реалізувати 2-мірних зв'язаний список якщо ви робите доповнення, як ви запропонували, 1/3 покажчика на кожну з цих речей, і якщо ви думаєте про іншому списку приходить на вас 3D стиль з екрану всім нам, що це просто ще один ланцюжок якийсь. Ми могли б це зробити, але це не так просто, як друкувати відкритої дужки, квадратні дужки. Так. [Нерозбірливо запитання студента] Добре, так що це реальний футболіст. 

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

Знову ж таки, ми не вирішення всіх наших проблем. Ми представляємо нові, але це залежить від того, що ви намагаєтеся проектувати для. У плані реалізації цього, ми можемо запозичувати ідеї з цього студента структури. Синтаксис дуже схожий, тільки тепер, ідея трохи більш абстрактних ніж удома, назва і ID. Але я пропоную, щоб ми могли мати структуру даних в C що називається вузлом, так як останнє слово на слайд пропозиції, Усередині вузла і вузол просто загальний контейнер в комп'ютерній науці. Це звичайно зображується у вигляді кола або квадрата або прямокутника, як ми зробили. І в цій структурі даних, у нас є ціле число, N, так що це число я хочу зберегти. Але що це друга лінія, структура вузла * далі? Чому це правильно, або яку роль ця річ гри, хоча це трохи загадкове на перший погляд? Так. [Нерозбірливо відповідь студента] Саме, тому * роду трофеї, що це покажчик якийсь. Назва цього покажчика як завгодно інший, але ми могли б назвав це все, що ми хочемо, але те, що робить цей покажчик вказує на? [Студент] Інший вузол. >> Точно, він вказує на інший такий вузол. 

Тепер, це свого роду цікавість C. Нагадаємо, що C читається компілятором зверху вниз, зліва направо, що означає, якщо-це трохи відрізняється від того, що ми робили з учнем. Коли ми визначили студент, ми насправді не ставив слово там. Він просто сказав ЬурейеЕ. Тоді у нас була Int Ідентифікатор, ім'я рядки, рядки будинок, , А потім студентом в нижній частині структури. Ця заява трохи відрізняється, тому що, знову ж таки, компілятор це трохи безглуздо. Це тільки збирається читати зверху вниз, Таким чином, якщо воно досягає 2-ї лінії тут де поруч оголошений, і він бачить, ой, ось змінна наступному. Це покажчик на структуру вузла. Компілятор буде розуміти, що це структура вузла? Я ніколи не чув про цю річ раніше, тому що слово вузол не могли б з'явитися до дна, так що ця надмірність. Ви повинні сказати структури вузлів тут, які потім можна скоротити надалі Завдяки ЬурейеЕ тут, але це тому, що Ми посиланням на саму структуру всередині структури. Це той, Гоча там. 

Деякі цікаві проблеми будуть виникати. У нас є список номерів. Як ми вставляємо в нього? Як ми можемо шукати його? Як ми можемо видалити з нього? Особливо зараз, коли ми повинні управляти всіма цими покажчиками. Ви думали, покажчики були свого роду галюциногенний коли ви були одним з них просто намагаюся читати Int до нього. Тепер ми повинні маніпулювати вартістю всього списку. Чому б нам не взяти нашу 5-хвилинну перерву тут, а потім ми принесемо деякі люди на сцену, щоб зробити саме це. 

З набагато більше задоволення, коли вона розігрується. Хто б буквально хотів бути першим? Гаразд, давай вгору. Ви знаходитесь в першу чергу. Хто хотів би бути 9? Гаразд, 9. Як щодо 9? 17? Трохи кліка тут. 22 і 26 в цьому ряду. І потім, як про когось там, на яку посилаються. Ви 34. Ладно, 34, давай вгору. По-перше, це там. Гаразд, всі чотири з вас, хлопці. А хто ж ми говоримо на 9? Хто наш 9? Хто дійсно хоче бути 9? Гаразд, давай, бути 9. Тут ми йдемо. 34, ми зустрінемося з вами там. Перша частина являє собою зробити собі виглядати. 26, 22, 17, добре. Якщо ви можете стояти осторонь, тому що ми збираємося Malloc вас в даний момент. 

Добре, добре. Добре, відмінно, так що давайте задати пару питань тут. А насправді, як тебе звати? >> Аніта. Аніта, ладно, йди сюди. Аніта збирається допомогти нам начебто вирішити одне досить просте питання в першому, який, як ви вважаєте, чи є значення знаходиться в списку? Тепер зверніть увагу, що, по-перше, представлені тут Лукас, трохи відрізняється, і тому його папірець свідомо боком тому що це не так високий і не займає стільки бітів, хоча технічно він має такий же розмір паперу, просто повертається. Але він трохи відрізняється тим, що він всього лише 32 біт для покажчика, і всі ці хлопці є 64-бітними, половина з яких це число, половина з яких є покажчиком. Але покажчик не зображено, так що якщо ви, хлопці, могли б дещо незграбно використовувати ліву руку, щоб вказати на людину поруч з вами. І ти номер 34. Як тебе звуть? Арі. Арі, так що насправді, тримати папір в праву руку, а ліва рука йде вниз. Ви уявляєте нульовою зліва. 

Тепер наша людська картина дуже послідовні. Насправді це як покажчики працюють. І якщо ви спробуєте може трохи Таким чином, так що я не на вашому шляху. Аніта тут, знайти мені номер 22, але припустити, обмеження не люди, піднявши папірці, Але це список, і у вас є тільки Лукас з самого початку тому що він буквально перший покажчик. Припустимо, що ви самі покажчик, так що ви теж маєте можливість вказати на щось. Чому б вам не почати, вказуючи на те, що Лукас вказує на? Добре, і дозвольте мені взяти на це тут. Тільки заради обговорення, дозвольте мені підтягти порожню сторінку тут. Як пишеться ваше ім'я? >> Аніта. Гаразд, Аніта. Припустимо, вузол * Аніта = Лукас. Ну, ми не повинні називати вас Лукас. Ми повинні зателефонувати вам в першу чергу. Чому це насправді відповідає дійсності тут? Один, перший вже існує. Перше було виділено імовірно десь тут. Node * По-перше, і це було виділено списку якось. Я не знаю, як це сталося. Це сталося до початку класу. Це пов'язано список людей була створена. А тепер у цей момент в історії-це все відбувається на Facebook видимо пізніше на даний момент у цій історії, Аніта була ініціалізований рівній першої, але це не означає, що Аніта вказує на Лукаса. Швидше за все, вона вказує на те, що він вказує на тому що ту ж адресу, що знаходиться всередині 32 біт Лукас - 1, 2, 3 - Тепер і всередині 32 біт Аніта - 1, 2, 3. 

Тепер знайдіть 22. Як би ви про це? Що це? >> Точка завгодно. Навівши курсор на будь-який інший, так що йти вперед і діяти його як найкраще, що ви можете тут. Добре, добре, і тепер ви, вказуючи на те, що, як тебе звати з 22? Рамон. >> Рамон, так Рамон тримається 22. Ви вже зробили чек. Хіба Рамон == 22, і якщо так, наприклад, ми можемо повернутися вірно. Дозвольте мені, в той час як ці хлопці стоять тут трохи незграбно- Дозвольте мені зробити щось швидко, як BOOL знайти. Я збираюся йти вперед і говорити (список вузлів *, Int N). Я скоро повернуся з вами, хлопці. Мені просто потрібно написати код. А тепер я збираюся йти вперед і робити це, вузол * Аніта = списку. І я буду йти вперед і говорити в той час як (Аніта! = NULL). 

Метафора тут стає трохи розтягнуто, але в той час (Аніта! = NULL), що я хочу робити? Мені потрібно якимось чином посилання ціле число, Аніта вказує на. У минулому, коли ми мали структур, які вузла, Ми використовували позначення точки, і ми хотіли б сказати щось на кшталт: anita.n, але проблема в тому, що Аніта не є структурою як такої. Що вона? Вона покажчик, так що дійсно, якщо ми хочемо використати цю точкову нотацію- і це буде виглядати нарочито трохи загадково- Ми повинні зробити щось подібне переходу на лівій руці все, що Аніта вказує на , А потім отримати полю називається п. Аніта є покажчиком, але те, що * Аніта? Що ви знаходите, коли ви йдете до того, що Аніта вказує на? Структури, вузлів і вузлів, нагадаємо, має поле з назвою п тому що вона, нагадаємо, ці 2 поля, в наступному і п, , Який ми бачили кілька хвилин тому прямо тут. 

Щоб насправді імітувати це в коді, ми могли б зробити це і говорять, що якщо ((* Anita). == п п), п, що я шукав. Зверніть увагу, що функція була передана в кількості я дбаю. Тоді я можу йти вперед і робити щось подібне повернення правда. В іншому випадку, якщо це не так, що я хочу робити? Як перевести в код, що Аніта зробила це інтуїтивно, йдучи за списком? Що я повинен робити тут, щоб імітувати Аніта цього кроку вліво, що крок вліво? [Нерозбірливо відповідь студента] >> Що це таке? [Нерозбірливо відповідь студента] Добре, не погана ідея, але в минулому, коли ми зробили це, ми зробили Аніта + + тому що це було додати число від 1 до Аніти, які, як правило, вказують на наступний людина, як Рамон, або особою, поряд з ним або поруч із ним особою вниз лінію. Але це не зовсім добре тут, тому що це річ виглядати в пам'яті? Не те, щоб. Ми повинні відключити це. Схоже, що це в пам'яті, і, хоча я намалював 1 і 2 і 3 близькі один до одного, якщо ми дійсно імітації цього, ви, хлопці, в той же час вказуючи на ті ж люди, може, деякі з вас беруть випадкові крок назад, деякі з вас випадковий крок вперед? 

Ця чехарда і раніше пов'язаного списку, але ці хлопці можуть бути де завгодно в пам'яті, так що Аніта + + не буде працювати, чому? Що на місці Аніта + +? Хто його знає. Це деякі інші значення, просто так трапляється бути вставлений серед всіх цих вузлів випадково, тому що ми не використовуємо масив. Ми виділили кожному з цих вузлів окремо. Добре, якщо ви, хлопці, можете очистити себе назад. Дозвольте мені запропонувати, що замість Аніти + +, ми замість цього отримує Аніта- Ну, чому б нам не піти на будь Аніта вказує на те і робимо. Наступний? Іншими словами, ми йдемо до Рамон, який тримає номер 22, і потім. наступна неначе Аніта буде копіювати його лівий покажчик руку. Але вона не хотіла йти далі, ніж Ramon тому що ми знайшли 22. Але це була б ідея. Тепер, це бог-жахливий безлад. Чесно кажучи, ніхто ніколи не буде пам'ятати цей синтаксис, і тому, на щастя, це насправді небагато навмисному-ой, ви насправді не розумієте, що я написав. Це було б більш переконливим, якби могли. Voila! 

За лаштунками, я був вирішити проблему таким чином. Аніта, піти на цей крок вліво, По-перше, ми дійсно йдуть на адресу, яку Аніта вказує на і де вона знайде не тільки росіян, які ми тільки що перевірив для порівняння, але ви також знайдете наступну - у цьому випадку, Лівою рукою Рамона, вказуючи на наступний вузол в списку. Але це бог-жахливий безлад про які я говорив раніше, але виявляється, C дозволяє нам спростити це. Замість листа (* Anita), ми можемо замість цього просто написати Аніта-> п, і це одне і те ж функціонально, але це набагато більш зрозумілим, і це набагато більше узгоджується з картиною, яку ми залучали Весь цей час за допомогою стрілок. 

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

Тепер давайте спробуємо ще один. Аніта, ви хочете, щоб повернутися сюди? Чому б нам не піти далі і виділити одну людину з аудиторії? Malloc-як тебе звати? >> Ребекка. Ребекка. Ребекка була malloced від аудиторії, і тепер вона зберігається номер 55. І мета під рукою зараз для Аніти, щоб вставити Ребекка в зв'язаний список тут у відповідному місці. Давай сюди на хвилинку. Я зробив щось на зразок цього. Я зробив вузол *. А що тебе звуть? Ребекка. >> Ребекка, все в порядку. Ребекка отримує Танос (SizeOf (вузла)). Так само, як ми виділили такі речі, як студенти і ще багато чого в минулому, Ми потребуємо в розмірі вузла, так що тепер Ребекка вказує на те, що? Ребекка має два поля всередині неї, одним з яких є 55. Давайте робити те, що, Ребекка-> = 55. Але тоді Ребеку-> наступна повинна бути, як зараз, її рука це свого роду хто знає? Це вказує на деякий сміття значення, так чому б не для хорошої заходом Ми принаймні, зробити так, щоб ліва рука тепер на її боці. Тепер Аніта, візьми його звідси. Ви повинні Ребекка того, були виділені. Йдемо далі і знайти, де ми повинні поставити Ребекка. Добре, дуже добре. Гаразд, добре, і тепер ми потребуємо вас, щоб забезпечити трохи напрямок, так що ви досягли Арі. Його ліва рука є дійсним, але Ребекка, очевидно, належить право, Так як же ми повинні змінити це зв'язаний список для того, щоб вставити Ребекка у відповідному місці? Якщо б ви могли буквально рухати лівої руки людей по всьому міру необхідності, ми вирішити цю проблему таким чином. Гаразд, добре, а тим часом ліва рука Ребекка тепер на її боці. 

Це було занадто просто. Давайте спробуємо виділення-Ми майже закінчили, 20. Гаразд, давай вгору. 20 були виділені, так що дозвольте мені йти вперед і сказати знову тут ми тільки що зробили Саад вузол *. У нас є Танос (SizeOf (вузла)). Потім ми робимо точно такий же синтаксис, як ми робили раніше на 20, і я буду робити далі = NULL, і тепер справа за Анітою вставити вас у зв'язаному списку, якщо б ви могли грати, що точно таку ж роль. Виконати. Гаразд, добре. Тепер подумайте, перш ніж почати рух лівої руки навколо. Ви на сьогоднішній день отримали найбільш незручний роль сьогодні. Чия рука повинна бути перенесена в першу чергу? Гаразд, почекай, я чую деяких немає в. Якщо деякі люди хотіли б ввічливо, щоб допомогти вирішити незручну ситуацію тут. Чия лівою рукою необхідно спочатку оновити можливо? Так. [Студент] Саад автора. Добре, Саад, чому, правда? [Нерозбірливо відповідь студента] Добре, тому що якщо ми будемо рухатися, як тебе звати? >> Маршалл. Marshall, якщо ми будемо рухатися руку спочатку вниз до нуля, Тепер ми в буквальному сенсі сиротами чотирьох чоловік в цьому списку тому що він був єдиним, вказуючи на Рамона, і все вліво, так що оновлення вказівників перший був поганий. Давайте скасувати це. Добре, а тепер ідіть уперед і перемістити відповідні лівою рукою, вказуючи на Рамона. Це відчуває себе трохи зайвим. Тепер є дві людини, вказуючи на Рамона, але це нормально тому що тепер, як ще ми можемо оновити список? Що з іншого боку повинен рухатися? Чудово, тепер ми втратили пам'ять? Ні, так добре, давайте подивимося, якщо ми не можемо розірвати цей раз. 

Mallocing в останній раз, номер 5. Всю дорогу в спину, давай вниз. Це дуже цікаво. [Оплески] Як тебе звуть? >> Рон. Рон, ладно, ви malloced як номер 5. Ми тільки виконуваний код, який майже ідентичні ці тільки з іншою назвою. Відмінно. Тепер, Аніта, удачі вставки № 5 у списку наразі. Добре, а? Відмінно, так що це дійсно третій з трьох загального числа випадків. Спочатку був хтось, врешті-решт, Ребекка. У нас тоді був хтось в середині. Тепер у нас є хтось на самому початку, і в цьому прикладі, у нас тепер оновити Лукас вперше тому що перший елемент у списку наразі має вказувати на новий вузол, які, в свою чергу, вказує на номер вузла 9. 

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

Давайте речі в більш складних напрямку досі. Тепер у нас є поняття пов'язаного списку. У нас також є, завдяки пропозиції туди-двусвязний список, , Який виглядає майже так само, але тепер у нас є два покажчика всередині структури замість одного, і ми могли б, ймовірно, назвати ці покажчики попередньої і наступної або вліво або вправо, але ми, справді, потрібні два з них. Код буде трохи складніше. Аните довелося б робити більше роботи тут, на сцені. Але ми, безумовно, може здійснювати таку структуру. З точки зору часу роботи, однак, що було б час роботи Аніта для знаходження числа п у зв'язаному списку зараз? Тим не менш велика O п, так що це не краще, ніж лінійний пошук. Ми не можемо зробити бінарний пошук, хоча, знову ж. Чому це було так? Ви не можете стрибати. Хоча ми, очевидно, всі люди на сцені, і Аніта могла б eyeballed його і сказав: "Ось середині списку" вона не буде знати, що якщо вона комп'ютерної програми оскільки єдине, що їй довелося замкнутися на на початку сценарію був Лукас, який був першим покажчиком. Вона обов'язково повинна слідувати за тими посиланнями, вважаючи її шляху, поки не знайшла приблизно посередині, і навіть тоді, вона не буде знати, коли вона досягла середини якщо вона проходить весь шлях до кінця, щоб з'ясувати, скільки є, потім відступає, і, що теж було б важко, якщо ви не були двусвязний список якийсь. 

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

Тепер, будь-які сценарії приходять на розум, де, маючи стек структура даних, де у вас є, що власність останні увійшов, першим вийшов, насправді переконливим? Хіба це добре? Хіба це погано? Це, безумовно, погано, якщо лотків не були всі однакові і всі вони були спеціальним різних кольорів і ще багато чого, і колір ви хочете, всю дорогу внизу. Звичайно, ви не можете отримати, що без великих зусиль. Ви повинні почати з верхньої і працювати ваш шлях вниз. Точно так само, як якщо б ви були одним з цих вентиляторів хлопчиків хто чекає всю ніч, намагаючись отримати iPhone і ліній до в такому місці, як це? Хіба не було б здорово, якби в Apple Store були структуру стека даних? Ура? Мало того? Це тільки для людей, які з'являються в останньої хвилини , А потім отримати зірвав черзі. І справді, той факт, що я був так схильний говорити чергу насправді відповідає тому, що ми б назвали таку структуру даних, один в реальності, де порядок має значення, і ви хочете перший, щоб бути першою з якщо тільки заради людської справедливості. Ми зазвичай називаємо це структура даних черзі. 

Виявляється, крім пов'язаних списків, ми можемо почати використовувати ці ж основні ідеї і почати створювати нове і різні типи рішень проблем. Наприклад, у випадку стека, ми могли б являти собою стек , Використовуючи структуру даних, як це, я хотів би запропонувати. У цьому випадку, я оголосив структури, і я вже говорив всередині цієї структури являє собою масив чисел, а потім змінна розміром, і Я буду називати цю річ стека. Тепер, чому це дійсно працює? У разі стек, я міг би зробити це ефективно на екрані у вигляді масиву. Ось мій стек. Такі мої номери. І ми будемо малювати їх, як це, це, це, це, це. А то у мене деякі інші члени даних тут, яка називається розмір, так це розмір, і це числа, і колективно, всією Ipad тут являє собою один стек структури. Зараз, за ​​замовчуванням, розмір імовірно повинен бути ініціалізований до 0, і те, що всередині масиву чисел спочатку Коли я вперше виділити масив? Garbage. Хто знає? І це насправді не має значення. Це не має значення, якщо це 1, 2, 3, 4, 5, зовсім випадково на невезіння, що зберігаються в моїй структурі, тому що поки я знаю, що розмір стека дорівнює 0, то я знаю, програмним, не дивися на будь-який з елементів у масиві. Це не має значення, що там. Не дивися на них, як би наслідок розмірі 0. 

Але припустимо, що тепер я йду вперед і вставити щось у стек. Я хочу, щоб вставити номер 5, так що я поклав № 5 тут, і то що я можу поставити сюди? Зараз я б насправді поклав 1 для розміру, і в даний час стек має розмір 1. Що робити, якщо я йду вперед і вставити число, скажімо, 7 наст? Це те оновлюється до 2, а потім ми будемо робити 9, а потім ця оновлюється до 3. Але цікава особливість тепер цей стек є те, що Я повинен видалити елемент якого, якщо я хочу спливав щось з стека, так би мовити? 9 була б перше, що потрібно йти. Як випливає картина зміниться, якщо я хочу поп елемент з стека, хотілося лоток Mather? Так. >> [Студент] Встановити розмір до 2. Точно, все, що я зробити, це встановити розмір 2, і що мені робити з масивом? Я не маю нічого робити. Я міг би, просто щоб бути анальний, покласти 0 існує або -1 або щось означають, що це не законно значення, але це не має значення, тому що Я можу записувати за межами самого масиву, як довго це так що я знаю тільки подивіться на перші два елементи в цьому масиві. Тепер, якщо я піду і додайте номер 8 до цього масиву, яким чином картина зміниться наступним? Це стає 8, і це стає 3. Я різання декілька кутів тут. Тепер у нас є 5, 7, 8, і ми повернулися до розміру 3. Це досить простий в реалізації, Але коли ми будемо шкодувати про це дизайнерське рішення? Коли речі починають йти дуже, дуже неправильно? Так. [Нерозбірливо відповідь студента] Якщо ви хочете, щоб повернутися і отримати перший елемент, який вставив 

При цьому виявляється, навіть якщо стек являє собою масив під капотом, ці структури даних, ми почали говорити про також відомий як абстрактних структур даних, яким, як вони реалізуються повністю, крім точки. Структура даних, як стек передбачається додати підтримку операцій, таких як поштовх, який штовхає лоток в стек, і поп-музики, яка видаляє елемент з стека, і це все. Якби ви завантажите чужий код, який вже реалізований те, що називається стеком, що людина написала б тільки дві функції для вас, штовхати і поп-музики, чия єдина мета в житті було б зробити саме це. Ви або його або її, хто здійснював цю програму був би зовсім один, щоб вирішити, як реалізувати Семантика натискання і з'являються під капотом або функціональність натискання і з'являються. І я зробив кілька короткозорим рішенням тут шляхом реалізації свого стека з цією простою структурою даних, то чому? Коли ж цей розрив структури даних? У який момент я повинен повертати помилку, коли користувач викликає поштовх, наприклад? [Студент] Якщо немає більше місця. Саме, якщо немає більше місця, якщо я перевищив ємність, який усі великі літери, оскільки вона припускає, що це свого роду глобальна константа. Ну, тоді я просто хочу, щоб сказати: «Вибачте, я не можу висунути ще одне значення в стек ", як в Mather. 

У якийсь момент вони збираються потрапити у верхню частину цього маленького кабінету. Там немає більше місця або потужності в стеку, і в цей момент там якась помилка. Вони повинні поставити елемент десь в іншому місці, лоток десь в іншому місці, або взагалі нікуди. Тепер, з чергою, ми могли б реалізувати це трохи по-іншому. Черга трохи відрізняється тим, що під капотом, він може бути реалізований як масив, але чому, в такому випадку, я пропоную також є голова елемент, який представляє главу списку, Перед списку, перша людина в черзі в магазин Apple, на додаток до розміру? Навіщо потрібна додаткова порція даних тут? Згадайте, які номери є якщо я намалював його таким чином. Нехай це зараз черги замість того, щоб стік, різниця в тому, як Apple Store в черзі справедливо. Перша людина в черзі в початок списку, номер 5 в цьому випадку, він або вона буде давати в магазині в першу чергу. Давайте зробимо це. Припустимо, що це стан моєї черги в даний момент часу, і тепер в Apple Store відкривається, і перша особа, номер 5, направляється в магазин. Як я можу змінити картину тепер, коли я де-черзі першої особи на передній лінії? Що це? >> [Студент] Зміни в черзі. Зміна головою, так що 5 зникає. Насправді, це, ніби, як краще це зробити? Насправді, це як ніби цей хлопець зникає. Що б номер 7 робимо в реальному магазині? Вони б зробити великий крок вперед. 

Але що ми прийшли до розуміння, коли мова йде про масивах і переміщення речей навколо? Це свого роду марна трата часу, так? Чому ви повинні бути настільки анальний, щоб мати першої особи На початку лінії на фізичному початок блоку пам'яті? Це абсолютно не потрібно. Чому? Що може я просто пам'ятаю, а? >> [Нерозбірливо відповідь студента] Точно, я міг би просто пам'ятаю, з цієї додаткової головкою члена даних що тепер глава список не 0, що це було хвилину тому. Зараз це насправді номер 1. Таким чином, я отримую невелику оптимізацію. Просто тому, що я де-черзі хтось з лінії на початку лінії в Apple Store не означає, що кожен повинен зміщуватися, що нагадаємо, є лінійною операцією. Я можу замість цього проводити постійну часу тільки і досягнення, то набагато швидше відповідь. Але ціна, яку я плачу це те, що щоб отримати, що додаткова продуктивність і не мають перекласти всі? Так. >> [Нерозбірливо відповідь студента] Можна додати більше людей, добре, що проблема ортогональної з тим, що ми не перекладаючи людей навколо. Він як і раніше масиву, чи так ми перекласти всі або не- О, я бачу, що ви маєте на увазі, ладно. Насправді, я згоден з тим, що ви говорите, що він майже як якби Ми тепер ніколи не буде використовувати початку цього масиву більше тому що, якщо я видалю 5, то я можу видалити 7. Але я тільки поставити людей з правого боку. 

Він відчуває, як я витрачати простір, і в підсумку моя черга розпадається взагалі нічого, таким чином, ми могли б просто є люди, запахом, і ми могли думати про це масив дійсно як свого роду кругова структура, але ми використовуємо те, що оператор C, щоб робити такого роду запахом? [Нерозбірливо відповідь студента] >> оператора по модулю. Було б трохи дратує продумати, як ви будете робити з запахом, але ми могли б це зробити, і ми могли почати збирати людей на те, що раніше передній лінії, але ми просто пам'ятаємо з цією головою змінна які фактичного керівника лінія насправді. Що, якщо, замість цього, наша мета в кінцевому підсумку, однак, було шукати числа, як ми зробили тут, на сцені з Анітою, але ми дійсно хочемо найкращою з усіх цих світах? Ми хочемо більше складності, ніж масив дозволяє тому що ми хочемо можливість динамічно зростати структури даних. Але ми не хочемо вдаватися до того, що ми вказали, У першій лекції не був оптимальним алгоритмом, , Що лінійного пошуку. Виявляється, що можна, справді, досягнення або принаймні близько до постійної часу, в результаті чого хтось, як Аніта, якщо вона налаштовує її структуру даних, щоб не бути пов'язаним списком, щоб не бути стек, щоб не бути черг, може, справді, придумати структуру даних, яка дозволяє їй шукати речі, навіть слова, а не просто цифри, в тому, що ми будемо називати постійною часу. 

І справді, забігаючи вперед, одна з psets в цьому класі майже завжди здійснення перевірки правопису, в результаті чого ми даємо вам знову близько 150000 англійських слів і мета завантажити в пам'ять тих, і швидко зможе відповісти на питання про форму це слово написано правильно? І це було б дійсно смоктати, якщо вам довелося перебрати всі 150000 слів, щоб відповісти на це питання. Але, насправді, ми побачимо, що ми можемо зробити це в дуже, дуже швидкий час. І це буде включати здійснення так званих хеш-таблиці, І хоча на перший погляд це те, що називається хеш-таблиці буде Давайте досягнення цих супер швидкого реагування, Виявляється, що є насправді проблема. Коли приходить час для здійснення цього, що називається, знову ж таки, я роблю це знову. Я тільки тут. Коли приходить час для здійснення цієї речі, званої хеш-таблиці, ми будемо мати, щоб прийняти рішення. Яким повинен цю річ насправді бути? І коли ми починаємо вставки цифр в цій хеш-таблиці, як ми будемо зберігати їх таким чином, що ми можемо отримати їх назад так швидко, як ми отримали їх? Але ми побачимо незабаром, що це питання коли день народження кожної людини в класі буде цілком доречним. Виявляється, що в цій кімнаті, у нас є кілька сотень людей, так що ймовірність того, що два з нас є той же день народження, ймовірно, досить висока. Що, якщо там були тільки 40 з нас в цій кімнаті? Які шанси двох людей, які мають той же день народження? [Студенти] Понад 50%. Так, більш ніж на 50%. Насправді, я навіть приніс графік. Виявляється, і це насправді просто попередній перегляд- якщо є тільки 58 із нас у цьому залі, імовірність того, 2 з нас що має той же день народження є надзвичайно високим, майже 100%, і що збирається викликати цілий букет боляче для нас в середу. 

З урахуванням сказаного, давайте відкладемо тут. Ми будемо бачити Вас в середу. [Оплески] [CS50.TV]