[МУЗИКА ГРАЄ] David J. Малан: Добре. Це CS50. Це п'ять тижні продовжував, і ми є хороші новини і погані новини. Так Доброю новиною є те, що CS50 запускає в цю п'ятницю. Якщо ви хотіли б приєднатися до нас, попрямувати у звичайній URL тут. НЕ Навіть найкращі новини, що не лекція майбутній понеділок 13-го. Трохи менш кращої новини, вікторина нуля в наступну середу. Детальніше можна знайшов за цією адресою тут. І в найближчі пару днів ми будемо заповнюючи прогалини з відносно номерів що ми зарезервували. Краще новина полягає в тому, що буду бути курс всієї відгук сесія в найближчу Понеділок ввечері. Залишайтеся з нами, щоб Курсу сайт для розміщення та деталей. Розділи, навіть якщо він є свято, також зустрінеться також. Кращий новини, лекції в наступну п'ятницю. Так що це традиція, яку ми Тобто, відповідно до навчальної програмі. Просто-- це буде дивно. Ви побачите речі, як структури даних постійної часу та хеш-таблиці, дерева і намагається. І ми будемо говорити про проблеми дня народження. Ціла купа речей чекає в наступну п'ятницю. Добре. У всякому разі. Так нагадаємо, що ми були упором на цій картині те, що всередині пам'яті нашого комп'ютера. Так пам'яті або оперативної пам'яті, де програми існують в той час як ви працюєте їх. Якщо ви двічі клацніть значок, щоб запустити деякі програми або двічі клацніть значок, щоб відкрити файл, він завантажений з жорсткого диск або твердотільний накопичувач в оперативній пам'яті, пам'яті довільного доступу, де він живе, поки харчування не відключиться, кришка ноутбука закривається, або виході з програми. Тепер, коли пам'ять, з які ви, ймовірно, 1 гігабайт в ці дні, 2 гігабайт, або навіть набагато більше, як правило, викладені за заданою програмою в цьому виді прямокутної Концептуальна модель в результаті чого ми маємо стек на дні і купу інших речей на самому верху. Справа на самому верху ми бачили на цій картинці раніше, але не говорив про це так званий текстовий сегмент. Сегмент тексту просто химерний спосіб сказати нулі і ті, які скласти свій фактичний скомпільовану програму. Отже, коли ви двічі клацніть Microsoft Word на Mac або ПК, або при запуску точку слеш Маріо на Linux комп'ютер у вашому вікні терміналу, нулі й одиниці, які складають Слово або Маріо тимчасово зберігаються в оперативній пам'яті комп'ютера в так званий текстовий сегмент для конкретної програми. Нижче, що йде ініціалізація і неініціалізовані дані. Це такі речі, як глобальні змінні, що ми не використали багато, але іноді ми в мав глобальні змінні або статично визначений рядка, закодована такі слова, як "привіт" , Які не прийняті в від користувача які жорстко в вашу програму. Тепер, на дні ми є так званий стеком. І стек, до цих пір, ми були використовуючи для яких видів цілей? Що стек використовується для? Да? Аудиторія: Функції. David J. Малан: Для функцій? В якому сенсі для функцій? АУДИТОРІЯ: Коли ви викликаєте функцію, Аргументи копіюються в стек. David J. Малан: Точно. При виконанні функції, її Аргументи копіюються в стек. Тому будь-які ікси або Y сайт або сайт або B, що ви передаєте в функцію тимчасово поставити на так званий стеком, як одного з Анненберг Їдальня лотки, а також речі, як локальних змінних. Якщо ваша функція Foo або підкачки Функція мати локальні змінні, як темп, ті два в кінцевому підсумку в стеці. Тепер, ми не будемо надто багато говорити про їм, але ці змінні оточення внизу ми побачили якийсь час назад, коли Я був возитися з клавіатури один день і я почав доступу речі як агду 100 або агду 1000, просто elements-- я забуваю numbers-- але що не повинні були бути доступні мені. Ми почали бачити деякі фанки символи на екрані. Це були так звані змінні оточення як глобальних параметрів для особистих Програма або для мого комп'ютера, а не пов'язані з недавньою помилка, що ми обговорювали, Контузія, що було жітья досить багато комп'ютерів. Тепер, нарешті, в сучасному центрі уваги ми в кінцевому рахунку бути в купі. Це ще один шматок пам'яті. І принципово все це пам'ять той же самий матеріал. Це те ж саме обладнання. Ми тільки вид лікування різних кластерів байтів для різних цілей. Куча також буде де змінні і пам'яті, що ви питаєте від операційної системи тимчасово зберігається. Але є свого роду проблеми тут, як і картина припускає. Ми-то є два кораблі близько стикатися. Тому що, як ви використовуєте все більше і більше стека, і, як ми бачимо сьогодні, вперед, як ви використовуєте все більше і більше купа, безумовно, погані речі можуть трапитися. І справді, ми можемо викликати, що навмисно або ненавмисно. Так в кульмінації останнього раз був ця програма, які не служать будь-яка функціональна Мета крім продемонструвати як вам, як поганий хлопець дійсно може прийняти Перевага помилок в чужій програмі і взяти на себе програму або навіть Весь комп'ютерна система або сервер. Так що просто заглянути ненадовго, вам помітити, що основні внизу приймає в командному рядку Аргументи, як за ARGV. І це має виклик функції F, істотно безіменний функція називається е, і це проходження в ARGV [1]. Тому, що б слово користувач вводить в на виводиться після імені цієї програми, а потім ця довільна функція до зверху, е, займає в рядку, AKA символ *, як ми почали обговорювати, і він просто називає його "бар". Але ми могли б називати його інакше. А потім він заявляє, всередині з F, масив символів називається c-- 12 таких символів. Тепер, з історії, яку я розповідав хвилину тому, коли в пам'яті є с, або ті, 12 символи буде в кінцевому підсумку? Просто щоб бути ясно. Да? АУДИТОРІЯ: На стеці. David J. Малан: На ​​стеці. Так з є локальною змінною. Ми просимо 12 символів або 12 байт. Ті збираються в кінцевому підсумку на так званому стеці. Тепер, нарешті, це інша функція що насправді дуже корисно, але ми насправді не використовується це самі, strncopy. Це означає рядок копію, але тільки російські букви, п символів. Так п символів буде копіюється з бару в с. А скільки? Довжина панелі. Таким чином, іншими словами, що одна лінія, strncopy, збирається копіювати офіційно заборонити і в. Тепер, просто вид передбачити Мораль цієї історії, що потенційно проблематично тут? Навіть при тому, що ми перевіряємо довжину з бару, і передаючи її в strncopy, що ваші кишки говорю вам це ще зламано про цю програму? Да? АУДИТОРІЯ: Чи не включає кімната для нульового символу. David J. Малан: Чи не включає кімната для нульового символу. Потенційно, на відміну від Колишня практика, ми навіть не є так багато як плюс 1 до розмістити цю нульовою символ. Але це ще гірше, ніж це. Що ще ми не в змозі зробити? Да? АУДИТОРІЯ: [нерозбірливо] David J. Малан: Прекрасно. Ми жорстко 12 досить довільно. Це не так багато проблема, але той факт, що ми навіть не перевіряючи, якщо довжина панелі менше 12, в цьому випадку він буде безпечно покласти його в пам'яті називається с, що ми виділено. Дійсно, якщо бар як 20 символів, Ця функція мабуть, копіювання 20 символів з бару в С, тим самим приймати, щонайменше 8 байтів що це не повинно бути. Ось підтекст тут. Таким чином, в короткостроковій, зламаною програми. Чи не така вже велика справа. Може бути, ви отримаєте помилку сегментації. Ми всі були помилки в програмах. Ми всі могли б мати помилки в програмах прямо зараз. Але те, що мається на увазі? Ну, ось в масштабі у версії що картина пам'яті мого комп'ютера. Це дно моєї стека. І дійсно, в самому низу це те, що називається батьком рутина стек, химерний спосіб сказати, що це основний. Так що той, хто називається функцією е, що ми говоримо про. Таким чином, це в нижній частині стопки. Зворотна адреса щось нове. Це завжди було там, завжди був у цій картині. Ми просто ніколи не звертав увагу на неї. Тому що виходить, то, як з роботи є що, коли одна функція викликає іншу, не тільки зробити, щоб аргументи, що Функція отримати в стек, не тільки зробити місцеві функція сайт Змінні отримати в стек, те, що називається зворотну адресу також отримує покласти в стек. Зокрема, якщо основні виклики Фу, основні сайт власну адресу в пам'яті, бик-то, ефективно отримує покласти в стек так що, коли е робиться виконання якого знає, де переходити туди, в тексті сегмент для того, щоб продовжити виконання. Так що, якщо ми тут концептуально, в основний, то F викликається. Як е знаю, хто в ручний контроль задньої? Ну, це трохи крихта в червоному тут, називається зворотну адресу, він просто перевіряє, що це за адреса повернення? О, дозвольте мені перейти назад на головну тут. І це трохи з спрощенням, тому нулів та одиниць для магістралі технічно тут в технічному сегменті. Але це ідея. е просто повинен знати, що туди, де контроль зрештою бере. Але те, як комп'ютери вже давно викладені речі як локальних змінних і Аргументи, як це. Таким чином, у верхній частині цієї картини в синій кадр стека для F, так що все з пам'яті, що F спеціально використовує. Так, відповідно, помітити, що Бар в цій картині. Бар був його аргумент. І ми стверджували, що аргументи Функції отримати в стек. І з, звичайно, Також в цій картині. І тільки для позначень цілей, помітити у верхньому лівому кутку то, що було б з кронштейном 0 і потім злегка вниз, вправо є з кронштейна 11. Отже, іншими словами, ви можете собі уявити що є сітка байт Тобто, перший з яких верхній лівий, нижній з яких останній з цих 12 байт. Але тепер спробуйте для швидкого перемотування вперед. Що має статися, якщо ми передамо в струнної барі, це більше, ніж з? І ми не перевірка, якщо це дійсно більше, ніж 12. Яка частина цієї картини збирається втрачено байт 0, 1, 2, 3, точка точка точка, 11, а потім погано, 12, 13 через 19? Що станеться тут, якщо ви вивести із замовлення що з кронштейн 0 знаходиться на вершині і з кронштейн 11 є свого роду вниз в порядку? Да? АУДИТОРІЯ: Ну, це буде перезаписати символ * бар. David J. Малан: Так, це виглядає як Ви збираєтеся перезаписати символ * бар. І що ще гірше, якщо ви відправляєте справді довго Рядок, ви могли б навіть переписати те, що? В якості зворотної адреси. Що ще раз, так само, як крихта сказати програмі, де повернутися до того, коли F робиться при виклику. Так що погані хлопці, як правило, роблять , Якщо вони приходять через програми що вони цікаво чи для використання, баггі таким чином що він або вона може приймати Перевага цієї помилки, як правило, вони не отримують це правильно з першого разу. Вони просто почати передачу, наприклад, випадкові рядки у вашій програмі, Чи на клавіатурі, або відверто вони, ймовірно, написати невелику програму для всього автоматично генерувати рядка, і почати стукати по вашій програми, відправка у великій кількості різних входів на різних довжинах. Як тільки ваші збої програм, що дивовижна річ. Бо це означає, що він або вона виявила , Що, ймовірно, дійсно помилка. І тоді вони можуть отримати більш розумний і почати фокусування більш вузько про те, як використовувати цю помилку. Зокрема, те, що він або вона могли б зробити, це відправити, в кращому випадку, привіт. Нічого страшного. Це рядок, це досить коротким. Але що, якщо він або вона посилає, і ми будемо узагальнювати його як, Напад code-- так нулів і ті, які роблять речі як RM-РФ, що видалити всі з жорсткого диска або розсилки спаму чи інакше атакувати машину? Таким чином, якщо кожен з них Листи просто представляє, концептуально, атака, атака, атака, атака, деякі погані код що хтось написав, але якщо ця особа досить розумний, щоб не тільки включати в себе всі з тих RM-RFS, а й є свої останні кілька байт бути число, яке відповідає на адресу його або її власний код атака що він або вона пройшла в тільки шляхом надання йому в командному рядку, Ви можете ефективно обдурити комп'ютер в помічаючи при е робиться виконання, о, це час для мене, щоб перейти назад до червоного зворотної адреси. Але так як він чи вона має так чи інакше перекриваються, що зворотну адресу з їх власним числом, і вони достатньо розумні, щоб налаштували, що число для позначення, як ви см в супер верхньої лівий кут там, Фактична адреса в комп'ютерній років Пам'ять про деякі з їх шкідливий код, поганий хлопець може обдурити комп'ютер у виконанні його або її власний код. І, що код, знову ж таки, може бути що завгодно. Це зазвичай називається Оболонка код, який є тільки спосіб сказати, що це не як правило, така проста річ, як RM-РФ. Це насправді-то як Bash, або фактичне програма, яка дає йому або її програмний контроль, щоб виконати все інше, що вони хочуть. Коротше кажучи, все це походить від того простого факту, що ця помилка участь не перевіряючи кордони вашого масиву. І тому, що шляхи Комп'ютери робота в тому, що вони використовують стек від ефективно, концептуально, Нижня далі вгору, але то елементи Ви натискаєте на стек рости зверху вниз, це неймовірно проблематично. Тепер, є способи обійти це. І, чесно кажучи, є мови з якою обійти це. Java має імунітет, наприклад, до цього конкретного питання. Тому що вони не дають вам покажчики. Вони не дають вам прямі адреси пам'яті. Так що з цією владою, що у нас до чого торкатися в пам'яті ми хочемо приходить, за загальним визнанням, великий ризик. Так що стежте. Якщо, чесно кажучи, протягом декількох місяців або років, щоб прийти в будь-який час Ви читаєте про деякі експлуатації програми або сервера, якщо ви ніколи не побачить натяк-то як атаки переповнення буфера, або переповнення стека і інший тип атаки, близького по духу, скільки вселяє сайту назвати, якщо ви його знаєте, це все говорю про просто переповнені розмір деяким характером масив або деякий масив в цілому. Будь-які питання, то, з цього приводу? Не намагайтеся повторити це вдома. Добре. Так Танос досі був наш новий Друг в тому, що ми можемо виділити пам'ять що ми не обов'язково знати, в заздалегідь, що ми хочемо, щоб ми не повинні на жорсткий код в нашу номера програм, як 12. Як тільки користувач говорить нам, скільки Дані він або вона хоче, щоб вхід, ми можемо Malloc що багато пам'яті. Так Танос виявляється, щоб Ступінь ми використовували його, явно востаннє, а потім ви, хлопці вже використовують його для GetString неусвідомлено для кілька тижнів, все пам'яті Malloc в виходить з так званої динамічної пам'яті. І ось чому GetString, наприклад, може виділити пам'ять динамічно не знаючи, що ви збирається ввести заздалегідь, вручити Вам покажчик на цю пам'ять, і що пам'ять ще ваш тримати, навіть після GetString віддачу. Тому нагадаємо, в кінці кінців, що стек постійно йде вгору і вниз, вгору і вниз. І як тільки вона йде вниз, що означає будь-яку пам'ять ця функція використовується повинні же не бути використаний в інших місцях. Це значення сміттєві зараз. Але купа тут. І, що приємно про Танос є те, що коли Танос виділяє пам'ять тут, це не вплинуло, для Більша частина, стеком. І тому будь-яка функція може отримати доступ пам'яті, яка була malloc'd, навіть на функцію як GetString, навіть після того, як він буде повернутий. Тепер, зворотне Танос безкоштовно. І справді, це правило вам потрібно, щоб почати прийняття це будь-який, будь-який, в будь-який час ви використовуєте Танос ви самі повинні використовувати безкоштовно, в кінці кінців, в той же покажчик. Весь цей час ми писали баггі, код помилки, з багатьох причин. Але один з яких був з використанням бібліотеки CS50, який Сам навмисно баггі, це витоків пам'яті. Щоразу, коли ви назвали GetString протягом останніх кількох тижнів ми просимо операційні Система, Linux, на пам'ять. І ви жодного разу не дали його назад. І це не в практикувати, хороша річ. І Valgrind, один з інструменти, введені в Pset 4, це все про допомагаючи вам Тепер знайти помилки, як, що. Але, на щастя для Pset 4 вам не потрібно використовувати бібліотеку CS50 або GetString. Тому будь-які помилки, пов'язані з пам'яттю є в кінцевому рахунку, буде свій власний. Так Танос більше, ніж просто зручна для цієї мети. Ми можемо насправді зараз вирішити принципово різні проблеми, і принципово вирішити проблеми більш ефективно, як за тиждень нуля обіцянку. До цих пір це найсексуальніша Структура даних у нас були. І за структурою даних я просто маю на увазі спосіб концептуалізації пам'яті таким чином, що виходить за рамки просто говорю, Це Int, це символ. Ми можемо почати кластера речей разом. Так масив виглядає наступним чином. І те, що було ключовим у про Масив є те, що вона дає вам спина до спини шматки пам'яті, кожен з яких буде того ж типу, Int, Int, Int, Int, або символ, символ, символ, символ. Але є кілька недоліків. Це, наприклад, це масив розміром шість. Припустимо, що ви заповните цей масив з шістьма числа і потім, з тих чи інших причин, ваш користувач хоче дати Ви сьомий номер. Де ви поклали? Який же вихід, якщо у вас є створили масив в стеці, наприклад, тільки з тиждень два позначення, що ми ввели, квадратних дужок з низкою всередині? Ну, у вас є шість Цифри в цих коробках. Що б ваші інстинкти бути? Де б ви хотіли сказати? АУДИТОРІЯ: [нерозбірливо] David J. Малан: Вибачте? АУДИТОРІЯ: Покладіть його на кінці. David J. Малан: Покладіть його на кінці. Так що просто на правий, поза цією рамкою. Який би добре, але це Виявляється, ви не можете зробити це. Тому що, якщо ви не запитали Для цього блоку пам'яті, це може бути збігом той це в даний час використовується деякої іншої змінної в цілому. Згадайте тиждень або близько того, коли ми заклали з імен Zamyla і Девін і Гейба в пам'яті. Вони були буквально спина до спини до спини. Таким чином, ми не можемо обов'язково довіряти, що б не було тут доступна для мене, щоб використовувати. Так, що ще ви могли б зробити? Ну, раз розуміючи вас потрібен масив розміром сім, ви могли б просто створити масив розміром сім потім використовувати цикл або час циклу, скопіювати його в новий масив, і потім якось просто позбутися цей масив або просто відмовитися від його використання. Але це не дуже ефективно. Коротше кажучи, масиви не дозволяють динамічно змінювати розмір. Отже, з одного боку, ви отримуєте довільного доступу, що дивно. Тому що це дозволяє нам робити те, як розділяй і володарюй, бінарний пошук, всі з яких ми в говорили про на екрані тут. Але ви малюєте себе в кут. Як тільки ви натиснете кінець вашого масиву, що вам потрібно зробити дуже дорога операція або написати цілу купу коду щоб тепер мати справу з цією проблемою. Так що, якщо замість того, щоб у нас були те, що називається список, або пов'язаний список, зокрема ,? Що робити, якщо замість того, прямокутники спина до спини до спини, у нас є прямокутники, які залишають трохи трохи маневру між ними? І хоча я намалював це зображення або адаптувати цю картинку від одного з текстів тут, щоб повернутися до спина до спини дуже організовано, насправді, один з цих прямокутників може бути тут в пам'яті. Один з них може бути тут. Один з них може бути тут, тут і так далі. Але що, якщо ми малювали, в цьому випадку, стрілки що так чи інакше пов'язати їх прямокутники разом? Дійсно, ми бачили технічна втілення стрілкою. Що ми використовували останнім часом днів, що, під капотом, є представником стрілкою? Покажчик, чи не так? Так що, якщо замість просто зберігати номери, як 9, 17, 22, 26, 34, що, якщо ми не зберігається тільки номер, але покажчик поруч із кожною такою числа? Так що так само, як ви б нитка голку через цілу купу тканини, так чи інакше пов'язуючи речі разом, так само може ми з покажчиками, як втілився стрілками тут, вид ткати разом ці окремі прямокутники шляхом ефективного використання покажчика Поруч з кожним номером, який вказує на деякий наступного числа, що вказує на, в свою чергу, деякі наступний номер? Отже, іншими словами, те, що якщо ми насправді хотіли реалізувати щось подібне? Ну, на жаль, ці прямокутники, Принаймні, один з 9, 17, 22, не й для так далі, вони більше не хороші квадрати з окремих номерів. Дно, прямокутник Нижче 9, наприклад, представляє, що повинно бути дороговказом, 32 біта. Тепер, я ще не в курсі будь-якого типу даних в С, що дає не тільки Int але покажчик в цілому. Так у чому ж рішення, якщо ми хочемо щоб винаходити власну відповідь на цей? Да? АУДИТОРІЯ: [нерозбірливо] David J. Малан: Що це? АУДИТОРІЯ: Нова структура. David J. Малан: Так, так чому не ми створюємо нову структуру, або в С, структури? Ми бачили структур і раніше, якщо коротко, де ми мали справу зі студентської структури як це, хто мав ім'я і будинок. В Pset 3 прорив ви використовували цілий купа structs-- GRect і GOvals , Що Стенфорд створив в Кластер інформація разом. Так що, якщо ми візьмемо цю ж ідею ключові слова "оголошень типів" і "структурою," а потім деякі студент-конкретні речі, і розвиватися це в наступному: ЬурейеЕ структури node-- і вузол тільки дуже загальне інформатика Термін-то в структурі даних, Контейнер в структурі даних. Вузол я стверджую, матиме Int N, дуже простий ,, а потім ще трохи загадково, це друга лінія, структура вузла * наступний. Але в менш технічних термінів, що це за друга лінія коду в фігурних дужках? Да? АУДИТОРІЯ: [нерозбірливо] David J. Малан: покажчик на інший вузол. Так за загальним визнанням, синтаксис трохи загадковим. Але якщо ви читаєте це буквально, Наступний це ім'я змінної. Що таке тип даних? Це трохи багатослівний на цей раз, але це тип структура вузла *. Щоразу, коли ми бачили щось зірку, що означає, що це покажчик на цього типу даних. Так що наступного, мабуть покажчик в структурі вузла. Тепер, що це структура вузла? Ну, помітили ви бачите тих, ті ж слова в правому верхньому куті. І справді, ви також бачите слово "Вузол" сюди в лівому нижньому кутку. І це насправді просто зручність. Зверніть увагу, що в нашому визначенні студентської є слово "студент" тільки один раз. І це тому, що студент об'єкт не був самоссилающіеся. Там немає нічого всередині студента що потрібно, щоб вказати на іншого студента, persay. Це було б свого роду дивно в реальному світі. Але з вузлом в пов'язаний Список, ми робимо хочете вузол бути посилальної до подібного об'єкта. І так помітити зміну тут не тільки те, що всередині фігурних дужок. Але ми додаємо слово «вузол» вгорі, а також додавши його на дно замість "студента". І це лише технічна деталь таким чином, що, знову ж таки, ваша структура даних, може бути самоссилающіеся, так що Вузол може вказувати на інший такий вузол. Так що ж це, в кінцевому рахунку означатиме для нас? Ну, один, цей матеріал всередині це зміст нашого вузла. Ця річ тут, вгорі праворуч, це просто так що, знову ж таки, ми можемо звернутися до себе. А потім зовнішній матеріал, навіть при тому, що вузол є новий термін, можливо, це все ще ж, як студент і що був під капотом в SPL. Так що, якщо ми зараз хотіли почати реалізації цього зв'язаний список, як ми могли б перевести як то так, щоб кодувати? Ну, давайте просто подивимося, Прикладом програми, які фактично використовує зв'язаний список. Серед сьогоднішніх коду розподілу є програма під назвою Список нульовий. І якщо я запускаю це я створив супер простий графічний інтерфейс, графічний інтерфейс користувача, але це дійсно просто PRINTF. І тепер я дав собі кілька меню options-- Видалити, Вставити, Пошук, і Traverse. І Quit. Такими є лише загальні операції по Структура даних відомі як список посилань. Тепер, Видалити збирається видалити номер зі списку. Вставте збирається додати число в список. Пошук виглядатиме числа в списку. І траверс тільки химерний спосіб сказати, ходити по списку, роздрукувати його, але це так. Не міняйте його в будь-якому випадку. Так давайте спробуємо це. Давайте підемо далі і ввести 2. А потім я збираюся введіть номер, кажуть 9. Enter. І тепер моя програма просто запрограмований сказати, список тепер 9. Тепер, якщо я піду вперед і у Вставте знову, нехай мені йти вперед і зменшення масштабу і введіть в 17. Тепер мій список 9, потім 17. Якщо я вставити знову, давайте пропустимо один. Замість 22, як за картини ми в дивився на тут, дозвольте мені перейти вперед і вставити 26 наступна. Так що я збираюся набрати 26. Цей список, як я очікую. Але зараз, просто щоб подивитися, якщо цього коду збирається бути гнучким, дозвольте мені тепер Тип 22, яка, щонайменше концептуально, якщо ми Маючи це сортуються, які дійсно буде інша мета прямо зараз, повинні піти в період з 17 по 26. Так я потрапив Enter. Справді, що працює. І ось тепер дозвольте мені вставити нарешті, за картини, 34. Добре. Так що на даний дозвольте мені передбачають, що Видалити і Traverse і пошук зробити, Справді, працювати. Насправді, якщо я запустити пошук, давайте пошук по номеру 22, Enter. Було встановлено, 22. Так що те, що це Програма Список Нуль робить. Але що насправді відбувається на який реалізує це? Ну, спочатку я, можливо, доведеться, і справді У мене є, файл з ім'ям list0.h. І десь там це лінія, ЬурейеЕ, структура вузла, то у мене є фігурні дужки, Int N, і потім struct-- що було визначення? Структура, вузол поряд. Так що ми повинні зірку. Тепер технічно ми потрапляємо в звичка малюнок його тут. Ви можете побачити підручники та онлайн посилання зробити це там. Це функціонально еквівалентні. Насправді, це трохи більш типовим. Але я буду послідовний з чим ми зробили в минулий раз і зробити це. І тоді, нарешті, я збираюся зробити це. Так у файлі заголовка де, в list0.h сьогодні це визначення структури, і, можливо, деякі інші речі. Між тим в list0c є буде кілька речей. Але ми збираємося просто почати і не закінчити це. List0.h це файл я хочу включити в моїй C файл. А потім в певний момент я доведеться Int, головна, анулюванню. А потім я збираюся є деякі до справи тут. Я також збираюся мати Прототип, як пустот, пошук, INT, н, чия мета в житті шукати елемента. А потім сюди я стверджую в сьогоднішня код, недійсними, пошук, Int, н, немає коми, але відкриті фігурні дужки. А тепер я хочу, щоб так чи інакше шукати для елемента в цьому списку. Але ми не маємо достатньо інформація на екрані ще. У мене насправді не представляв сам список. Так один із способів ми могли б реалізувати зв'язаний список в програмі буде я начебто хочу робити те, як декларують пов'язано список тут. Для простоти я збираюся зробити ця глобальна, хоча в цілому ми не повинні робити цього занадто багато. Але це спростить цей приклад. Тому я хочу заявити зв'язаний список тут. Тепер, як я міг би це зробити? Ось картина пов'язаного списку. І я дійсно не відомо на даний момент хау Я збираюся йти про що представляють так багато речей, тільки з одним змінна в пам'яті. Але згадайте момент. Весь цей час у нас було рядка, які потім показав, що масиви символів, які ми потім показали, щоб бути просто покажчик на перший символ в масив символів який нулем. Так за цією логікою, і з цим фото вид посіву ваші думки, На що нам насправді писати в наш Код для подання зв'язаний список? Скільки з цієї інформації нам потрібно захопити в C код, ви можете сказати? Да? АУДИТОРІЯ: Нам потрібен покажчик на вузол. David J. Малан: покажчик на вузол. Зокрема, який вузол б ваша інстинкти б зберігати покажчик на? АУДИТОРІЯ: Перший вузол. David J. Малан: Так, ймовірно, тільки перший. І зверніть увагу, перший вузол іншу форму. Це тільки половина розмір структури, тому що це дійсно тільки покажчик. Так що ви дійсно можете зробити, це оголосити зв'язаний список, щоб мати тип вузла *. І давайте просто називати його першим і ініціалізувати його до нуля. Так нуль, знову ж таки, йде в картину тут. Мало того, що використовується як нуль, як спеціальна Значення, що повертається для того, як GetString і Танос, нуль також нульова покажчик, відсутність покажчика, якщо ви будете. Це просто означає, ніщо не згадано тут. Тепер перший, я міг би назвав це нічого. Я міг би назвати його "список" або будь-яку кількість інших речей. Але я дзвоню його "першим", так що він вибудовується в лінію з цієї картини. Так само, як струни може бути представлено з адресою його першого байта, так може зв'язаний список. І ми побачимо інші дані структури можна представити тільки з одним покажчиком, 32-розрядна стрілка, вказуючи на першому вузлі в структурі. Але тепер давайте передбачити проблему. Якщо я тільки згадавши в моїй програмі адресної з першого вузла, перший прямокутник в цій структурі даних, що краще бути справа про Реалізація решти моєму списку? Що ключовою деталлю, що відбувається забезпечити це насправді працює? І "насправді працює" я значить, так само, як рядки, дозволяє нам перейти від першого символу в імені Давіна до другого, в третіх, четвертий, до самого кінця, як ми знаємо, коли ми перебуваємо в кінці пов'язаного списку, який виглядає наступним? Коли це нуль. І я уявляв цей вид як як інженер-електрик мощі, з маленьким заземлення символ, свого роду. Але це просто означає, нуль в цьому випадку. Ви можете намалювати його будь-яку кількість способів, але цей автор відбулося використовувати цей символ тут. Поки ми нанизуючи всі ці вузли разом, тільки згадуючи, де Перший, до тих пір, як ми ставимо спеціальний символ на найостанніший вузол у списку, і ми будемо використовувати нуль, тому що це те, що ми маємо в розпорядженні, щоб нас, цей список буде завершена. І навіть якби я тільки дати вам покажчик перший елемент, ви, програміст, безумовно, може отримати доступ до решти його. Але давайте нехай ваші уми побродити небагато, якщо вони не вже досить wandered-- що буде час роботи знайшовши нічого в цьому списку? Чорт візьми, це велика O н, що не погано, справедливості заради. Але це є лінійним. Ми відмовилися від того, що функція масивів шляхом переміщення більш до цієї картини динамічно переплітаються або пов'язані вузли? Ми відмовилися від випадкового доступу. Масив приємно, тому що математично все є спина до спини до спини до спини. Навіть при тому, що цій картині виглядає красиво, і навіть хоча це виглядає як цих вузлів красиво рознесені, в реальності вони можуть бути де завгодно. Ox1, Ox50, Ox123, Ox99, ці вузли можуть бути де завгодно. Тому Танос робить виділити пам'ять з купи, але в будь-якому місці в купі. Вам не обов'язково знати, що це буде спина до спини до спини. І так ця картина в Реальності не збирається бути настільки значною. Так він збирається зайняти трохи працювати над реалізацією цієї функції. Так давайте реалізуємо пошук зараз. І ми побачимо роду розумний спосіб зробити це. Так що, якщо я функція пошуку і Я дав змінної, число п шукати, мені потрібно знати, Новий синтаксис для пошуку всередині структури, це вказав на, щоб знайти н. Так давайте зробимо це. Отже, спочатку я піду вперед і оголосити вузол *. І я буду називати його покажчик, тільки за угодою. І я збираюся, щоб підготувати його до першого. І тепер я можу це зробити В декількома способами. Але я збираюся прийняти загальний підхід. У той час як курсор не дорівнює нуль, і це допустимий синтаксис. І це саме означає, виконайте наступні дії, так Поки ви не вказуючи ні перед чим. Що я хочу зробити? Якщо покажчик точка п, дозвольте мені повернутися в тому, що, equals-- одно що? Яке значення я шукаю? Фактична п, який був прийнятий в. Так от ще одна особливість С і багато мов. Навіть при тому, що структури називається вузлом має значення п, повністю законною також є місцевий аргумент або змінна називається н. Тому що навіть ми, з людські очі, можна виділити що це п-видимому відрізняється від цього п. Оскільки синтаксис відрізняється. У вас є точка і покажчик, в той час як цей не має нічого подібного. Так що це в порядку. Це нормально, щоб називати їх ті ж самі речі. Якщо я вам знайти це, я захоче зробити щось як повідомити, що ми знайшли н. І ми залишимо це як коментувати або псевдокод код. Останнє, і ось цікава частина, що я хочу робити, якщо поточний вузол який не містить п, що я дбаю про? Як мені добитися наступне? Якщо мій палець на момент PTR, і це вказуючи на те, що Перший вказуючи на, як я можу поворухнути пальцем на наступний вузол в коді? Ну, що крихта ми збирається слідувати в цьому випадку? АУДИТОРІЯ: [нерозбірливо]. David J. Малан: Так, так що наступного. Так що, якщо я повернуся в мій Код тут, дійсно, я збираюся йти вперед і сказати, покажчик, який це лише тимчасове переменная-- це дивне ім'я, PTR, але це просто як temp-- Я збираюся встановити покажчик одно який покажчика is-- і знову ж таки, це буде невеликий дитячий візочок для moment-- точкою наступного. Іншими словами, я збираюся прийняти мої палець, який, вказуючи на цьому вузлі тут, і я збираюся сказати, ви знаєте, що, погляньте на наступне поле і перемістити палець в там воно вказуючи на. І це буде Повторюю, повторювати, повторювати. Але коли робить свій палець припинити робити взагалі нічого? Як щойно рядок коду ударів в? АУДИТОРІЯ: [нерозбірливо] David J. Малан: Якщо точка а покажчик не дорівнює нулю. У якийсь момент мій пальця буде вказуючи на нуль і я збираюся реалізувати це кінець цього списку. Тепер, це трохи брехня для простоти. Виходить, що навіть при тому, що ми тільки що дізнався цю точкову нотацію для структур, покажчик не структура. PTR є що? Просто, щоб бути більш nitpicky. Це покажчик на вузол. Це не сам вузол. Якщо у мене не було зіркою тут, покажчик absolutely-- це вузол. Це як тижні один Декларація змінної, хоча слово «вузол» є новим. Але як тільки ми вводимо зірка, то тепер це покажчик на вузол. І, на жаль, ви не можете використовувати точкової нотації для покажчика. Ви повинні використовувати стрілку позначення, які, разюче, Вперше будь-який шматок синтаксису виглядає інтуїтивно зрозумілим. Це буквально виглядає як стріла. І так, що це хороша річ. І тут буквально виглядає, як стріла. Так що я думаю, що це la-- я не думаю, що я більш-вчинення здесь-- Я думаю, що це останній новий шматок синтаксису ми збираємося, щоб побачити. І на щастя, це дійсно трохи більш інтуїтивним. Тепер, для тих з вас, хто можливо, віддадуть перевагу по-старому, Ви все ще можете використовувати точкової нотації. Але відповідно до понеділка Розмова, ми спочатку повинні піти туди, йти до того, що рішення, а потім перейти в поле. Так що це теж правильно. І, чесно кажучи, це трохи більше педантичним. Ти буквально кажучи, разименовать покажчик і піти туди. Потім беремо .n, поле називається н. Але, відверто кажучи, ніхто не хоче ввести або прочитати це. І тому світ придумав позначення стрілка, яка еквівалентно, ідентичні, це просто синтаксичний цукор. Так химерний спосіб сказати це виглядає краще, або виглядає простіше. Так що тепер я збираюся зробити ще одну річ. Я збираюся сказати "перерва" Як тільки я виявили, що це так, я не продовжувати шукати для нього. Але це суть функції пошуку. Але це набагато легше, в кінець, не ходити через код. Це дійсно формальне виконання пошуку в сьогоднішньому коді розподілу. Насмілюся сказати, що вставка НЕ особливо цікаво йти через візуально, ні видалити, навіть при тому, що в кінці дня вони зводяться до досить прості евристики. Так давайте зробимо це. Якщо ви будете гумор мене тут, я зробив принести купу стресових куль. Я приніс купу цифр. І ми могли б отримати тільки кілька добровольців представляти 9, 17, 20, 22, 29 і 34? Так по суті всі хто тут сьогодні. Це був один, два, три, чотири, п'ять, шість чоловік. І я попросив go-- побачити, немає один в спину піднімає свої руки. ОК, раз, два, три, чотири, five-- дозвольте мені завантажити balance-- шість. ОК, ви шість давай до. Ми потрібні інші люди. Ми принесли додаткові кулі стрес. І якби ви могли, для тільки на мить, лінія самі до всього любите цю фотографію тут. Добре. Давайте подивимося, як тебе звуть? АУДИТОРІЯ: Андрей. David J. Малан: Андрій, ви номер 9. Приємно познайомитися. Тримай. АУДИТОРІЯ: Джен. David J. Малан: Джен. Девід. Номер 17. Да? АУДИТОРІЯ: Я Юля. David J. Малан: Юлія, Девід. Кількість 20. АУДИТОРІЯ: Крістіан. David J. Малан: Крістіан, Девід. Кількість 22. І? АУДИТОРІЯ: JP. David J. Малан: JP. Кількість 29. Так йти вперед і отримати В- Ой-ой. Ой-ой. В режимі очікування. 20. Хто-небудь є маркер? АУДИТОРІЯ: У мене є Шулера. David J. Малан: Ви отримали шулера? Добре. І хто-небудь є листок паперу? Збережіть лекцію. Підійди. АУДИТОРІЯ: У нас є його. David J. Малан: Ми отримали його? Добре, дякую. Тут ми йдемо. Чи був цей від вас? Ви просто врятували день. Так 29. Добре. Я неправильно 29, але добре. Продовжуй. Добре, я дам вам Ваш перо назад на мить. Тому у нас є ці люди тут. Давайте один інший. Гейб, ти хочеш грати Перший елемент тут? Ми потребуємо вас, щоб вказати на цих прекрасних людей. Так 9, 17, 20, 22, отсортируйте з 29, а потім 34. Хіба ми втрачаємо кого? У мене є 34. Де did-- ОК, хто хоче бути 34? ОК, давай до, 34. Гаразд, це буде варто кульмінація. Як тебе звуть? АУДИТОРІЯ: Пітер. David J. Малан: Питер, давай до. Добре, так ось ціла купа вузлів. Кожен з вас, хлопці, являє один з цих прямокутників. І Гейб, трохи дивний людина з, представляє перший. Таким чином, його покажчик трохи менше на екрані, ніж всі інші. І в цьому випадку, кожен з вашої лівої руки збирається або направлені вниз, тим самим представляючи нуль, так тільки відсутність покажчика, або це збирається бути вказуючи в вузлі поруч з вами. Так що зараз, якщо ви прикрашають будьте подібні картинці тут, йти вперед і крапка один на одного, з Gabe зокрема, вказуючи на номер 9 для подання списку. ОК, і число 34, ліва рука треба просто вказуючи на підлозі. ОК, так що це зв'язаний список. Так що це сценарій під питанням. І справді, це представник з одного класу задач що ви могли б спробувати вирішити з кодом. Ви хочете, щоб в кінцевому рахунку вставити новий елемент в список. В цьому випадку, ми збираємося спробуйте вставити число 55. Але є буде різні випадки розглянути. І справді, це буде один з великої картини їжі додому тут, є, які різні випадки. Які існують умови або філіали, що ваша програма може бути? Ну, номер, який ви намагаєтеся вставка, який ми тепер знаємо, 55, але якщо ви не знаєте, заздалегідь, я насмілюся сказати, потрапляє в принаймні трьох можливі ситуації. Де може новий елемент бути? АУДИТОРІЯ: І кінець або середину. David J. Малан: Наприкінці, в середній, або на початку. Так я стверджую, що є принаймні три проблеми, які ми повинні вирішити. Давайте вибирати, що, можливо, можливо найпростіший один, де новий елемент належить на початку. Так що я буду мати код досить як шукати, що я тільки що написав. І я буду мати PTR, які Я уявляю пальцем, як звичайно. І пам'ятайте, яке значення ж ми инициализировать покажчик на? Таким чином, ми инициализировать його обнулити спочатку. Але тоді що ж ми робимо, як тільки ми були в нашому функції пошуку? Покладемо його рівним першому, що не означає робити це. Якщо я встановлюю PTR рівну першої, що повинні моя рука дійсно вказуючи на? Право. Так що, якщо Гейб і я збираємося бути рівні значення тут, ми повинні як точки, в число 9. Так що це був початок нашої історії. А тепер це просто прямий, незважаючи на те, що синтаксис є новим. Концептуально це тільки лінійний пошук. Є 55 дорівнює 9? Вірніше, скажімо менше 9. Тому що я намагаюся з'ясувати, де поставити 55. Менше 9, менше 17, менше ніж 20, менше 22, менше 29, менше 34, немає. Так що тепер ми в разі один із щонайменше трьох. Якщо я хочу, щоб вставити 55 над тут, що рядків коду необхідності отримати виконаний? Як це картину люди повинні змінити? Що мені робити з моєю лівою рукою? Це повинно бути нульовим, спочатку, бо я в кінці списку. А що має статися, тут з Петром, це було? Він, очевидно, збирається вказувати на мене. Так я стверджую, що є принаймні дві лінії коду в прикладі коду з сьогоднішнього дня що збирається здійснити це Сценарій додавання 55 в хвості. І може мене хтось-хоп і просто представляють 55? Гаразд, ви новий 55. Так що тепер, якщо наступна сценарій приходить, і ми хочемо, щоб вставити в починаючи або керівник цього списку? І те, що ваше ім'я, номер 55? АУДИТОРІЯ: Джек. David J. Малан: Джек? ОК, приємно познайомитися. Ласкаво просимо на борт. Так що тепер ми збираємося вставити, скажімо, число 5. Ось другий випадок три ми придумали раніше. Так що якщо 5 належить на початку, давайте подивимося, як ми бачимо, що з. Я инициализировать мій PTR покажчик на номер 9 знову. І я зрозумів ,, о, 5 менше 9. Так виправити цю картинку для нас. Чиї руки, Гейба або Давида ілі-- що номер 9 в назву? АУДИТОРІЯ: Джен. David J. Малан: hands-- Джен які з наших рук потрібно змінити? Отже, Гейб вказує на що тепер? У мене. Я новий вузол. Так що я просто вид ходу тут, щоб подивитися його візуально. А між тим, що я вказати, що? Проте, коли я вказую. Так ось воно що. Так що просто дійсно одна рядок коду виправлення це конкретне питання, здавалося б. Гаразд, так що це добре. А може хто б це місце для 5? Піднімайтеся. Ми тебе наступного разу. Гаразд, так now-- і Як осторонь, імена Я не роблю прямої згадки права Тепер, před покажчик, покажчик попередник і новий покажчик, це тільки імена дали в прикладі коду до покажчиків або мої руки, це частково вказують навколо. Як тебе звуть? АУДИТОРІЯ: Христина. David J. Малан: Христина. Ласкаво просимо на борт. Гаразд, так що давайте розглянемо зараз трохи більше дратує сценарій, в результаті чого я хочу, щоб вставити щось на зразок 26 в цьому. 20? Що? Ці are-- хороша річ у нас є цю ручку. Гаразд, 20. Якщо хтось може отримати ще один шматок папір готова, тільки в case-- все в порядку. О, цікаво. Ну це приклад лекційного помилки. Добре, таким чином, що тебе звуть? АУДИТОРІЯ: Юлія. David J. Малан: Юлія, ви можете поп , І вдаючи, що ви ніколи не були там? ОК, це ніколи не відбувалося. Спасибо. Так що ми хочемо вставити Юлія в цей пов'язаного списку. Вона є число 20. І, звичайно, вона збирається належать на begin-- не вказують ні на що ще. Так що ваша рука може почасти бути вниз нуль або деяке значення сміття. Давайте говорити коротку історію. Я вказую на 5 цього разу. Тоді я перевіряю 9. Тоді я перевіряю 17. Тоді я перевіряю 22. І я розумію ,, ох, Юля повинен йти до 22. Так що має статися? Чиї руки потрібно змінити? Джулія, шахта, ілі-- як тебе звуть? АУДИТОРІЯ: Крістіан. David J. Малан: християнин або? АУДИТОРІЯ: Енді. David J. Малан: Енді. Крістіан або Енді? Енді повинен вказати на? Юлія. Добре. Так Енді, ти хочеш, щоб вказати на Джулію? Але почекайте хвилину. В історії досі, Я-то один відповідає, в тому сенсі, що покажчик є річ, яка переміщення за списком. Ми можемо мати ім'я для Енді, але немає змінна називається Енді. Єдиний інший змінної у нас є, перший, хто представлений Гейба. Так що це насправді, чому таким чином Поки ми не потребували цього. Але тепер на екрані є ще раз відзначити, з před покажчика. Отже, дозвольте мені бути більш явним. Якщо це покажчик, я повинен був краще отримати трохи розумніший про моє ітерації. Якщо ви не проти, що я збираюся через тут знову, вказуючи тут, вказуючи тут. Але дозвольте мені є před покажчик, покажчик попередник, це вид вказуючи на елемент я був просто в. Тому, коли я йду сюди, зараз Моя ліва рука оновлення. Коли я йду тут мої ліві поновлення вручну. І тепер у мене є не тільки покажчик елемент, який йде після Джулії, Я до сих пір є вказівник на Енді, елемент раніше. Так у вас є доступ, по суті, панірувальних сухарів, якщо хочете, для всіх необхідних покажчиків. Так що, якщо я, вказуючи на Енді і я також вказуючи на Крістіана, чиї руки повинні тепер відзначити в іншому місці? Так Енді тепер можуть вказати на Джулію. Тепер Юлія може вказувати на християнина. Тому що вона може скопіювати мій покажчик правої руки. І, що ефективно ставить вас назад в цьому місці тут. Таким чином, загалом, хоча це веде нас начебто назавжди насправді поновлення пов'язаний список, реалізувати що операції відносно прості. Це з одного, двох, трьох рядків коду, в кінцевому рахунку. Але обгорнуті навколо тих, рядків коду імовірно трохи логіки, які ефективно задає питання, де ми знаходимося? Невже ми на самому початку, середній, або кінець? Тепер, є, звичайно, деякі інші Операції, які ми могли б реалізувати. І ці фотографії тут просто зобразити те, що ми тільки що зробили з людьми. А як щодо видалення? Якщо я хочу, наприклад, видалити номер 34 або 55, Я міг би мати такий же код, але я буду мати потребу в один або два етапи. Тому що нового? Якщо я видалю кого в кінці, як числа 55, а потім 34, що також має змінитися, як мені це зробити? Я повинен не evict-- як тебе звуть? АУДИТОРІЯ: Джек. David J. Малан: Джек. Я повинен не тільки evict-- безкоштовно Джек, так буквально назвати безкоштовний Джек, або, принаймні, покажчик там же, але тепер що необхідно змінити з Петром? Його рука краще почати вниз. Тому що, як тільки я дзвонити безкоштовно на Джек, якщо ще вказує Петра на Джека і я тому тримайте обході список і доступ цей покажчик, от коли наш старий друг сегментація звинуватити дійсно може померти. Тому що ми дали пам'яті назад до Джеку. Ви можете залишитися там ніяково на мить. Тому що у нас всього пару заключні операції розглянути. Зняття голову списку, або beginning-- і цей сайт трохи дратує. Тому що ми повинні знати, що Гейб це свого роду спеціальне в цій програмі. Тому що насправді, у нього є своя покажчик. Він не просто на яку посилаються ,, як майже всі інші тут. Тому, коли глава списку видалені, чиї руки повинні змінити зараз? Як тебе звуть знову? АУДИТОРІЯ: Христина. David J. Малан: Я жахливо на імена, очевидно. Так Христина та Гейб, чиї руки необхідно змінити коли ми намагаємося видалити Крістіну, число 5, від картини? Отже, давайте зробимо Гейб. Гейб збирається вказати, імовірно, в будинку номер 9. Але що наступний повинен відбутися? АУДИТОРІЯ: Христина повинна бути порожнім [нерозбірливо]. David J. Малан: Добре, ми повинні, ймовірно, make-- я почув "нульовий" де. АУДИТОРІЯ: Null і звільнити її. David J. Малан: Null що? АУДИТОРІЯ: Null і звільнити її. David J. Малан: Null і звільнити її. Так що це дуже легко. І це прекрасно, що ти зараз роду стояти там, які не належать. Тому що ви були відділений від списку. Ви ефективно було сиротами зі списку. І таким чином, ми краще зателефонувати безкоштовно зараз на Крістін, щоб дати цю пам'ять тому. Інакше кожен раз, коли ми видалити вузол зі списку ми могли б робити список коротше, але насправді не зменшується розмір в пам'яті. І тому, якщо ми продовжуємо додавати і додавши, додавання елементів у списку, мій комп'ютер стає менш ефективним і все повільніше і повільніше, бо я біжу з пам'яті, навіть якщо я насправді не використовуючи байт Крістіни пам'яті більше. Так, в кінці є й інші сценарії, з course-- видалення у середній, видалення в кінці, як ми бачили. Але тим цікавіше Зараз завдання полягає в буде розглядати саме що час роботи є. Так що не тільки ви можете зберегти ваш папірців, якщо, Гейб, ви не заперечуєте даючи кожен м'яч стрес. Величезне спасибі нашому пов'язаного списку добровольців тут, якби ви могли. [Оплески] David J. Малан: Добре. Так пару аналітична питання потім, якщо я міг. Ми бачили це позначення раніше, Big O і омега, верхні межі та нижні межі час роботи від деякого алгоритму. Отже, давайте розглянемо тільки пару питань. Один, і ми сказали, це перш, ніж же працює час пошуку Список по великій O? Що верхню межу працюючому Час пошуку зв'язаний список як здійснюється нашими волонтерами тут? Це великий O н, лінійний. Тому що в гіршому випадку, елемент, як 55, ми могли б шукати може бути там, де Джек був, всю дорогу в кінці. І, на жаль, на відміну від масиву ми не можемо отримати фантазії на цей раз. Навіть при тому, що всі наші люди були відсортовані від невеликих елементів, 5, все, аж до більшого елемента, 55, що, як правило, хороша річ. Але те, що робить це припущення більше не дозволяють нам робити? АУДИТОРІЯ: [нерозбірливо] David J. Малан: знову сказати? АУДИТОРІЯ: Довільний доступ. David J. Малан: Довільний доступ. І в свою чергу це означає, що ми можемо не більше використовувати слабкий нулі, інтуїцію, і очевидність використовуючи двійковий пошук і розділяй і володарюй. Тому що навіть при тому, що ми люди могли, очевидно, бачити, що Енді чи християнин були приблизно в середині списку, відомо лише, що, як комп'ютер шляхом зняття верхнього шару список з самого початку. Таким чином, ми відмовилися, що довільний доступ. Настільки великий O п тепер це верхня межа нашого часу пошуку. Як щодо омега нашого пошуку? Що нижня межа з пошуку протягом деякого числа в цьому списку? АУДИТОРІЯ: [нерозбірливо] David J. Малан: знову сказати? АУДИТОРІЯ: Один. David J. Малан: Один. Так постійна часу. В кращому випадку, Крістіна Справді на початку списку. І ми шукаємо число 5, так що ми знайшли її. Так немає нічого складного. Але у неї є, щоб бути в початок списку в цьому випадку. Що про щось як Видалити? Що робити, якщо ви хочете видалити елемент? Що верхня межа і нижня межа на видаленні чого від пов'язані перерахувати? АУДИТОРІЯ: [нерозбірливо] David J. Малан: знову сказати? АУДИТОРІЯ: н. David J. Малан: п дійсно верхня межа. Тому що в гіршому випадку ми намагаємося видалити Джек, як ми тільки що зробили. Він всю дорогу в кінці. Приймає від нас назавжди, або п кроків, щоб знайти його. Так от верхня межа. Це лінійна, впевнений. І в кращому випадку час роботи, або нижні межі в кращому випадку буде постійна часу. Бо, може бути, ми намагаємося видалити Крістін, і ми просто повезти вона на початку. Тепер почекайте хвилину. Гейб також на початку, і ми також повинні були оновити Гейб. Так що не було ще один етап. Так це дійсно постійної Час, в кращому випадку, видалити найменший елемент? Це, незважаючи на те, що може бути два, три або навіть 100 рядків коду, якщо це те ж саме кількість лінії, не в деякій петлі, і не залежить від розміру зі списку, абсолютно. Видалення елемента в початок списку, навіть якщо ми маємо справу з Гейб, ще постійна часу. Так це здається масивний крок назад. І те, що це марна трата часу якщо, на тиждень один і тижня нулю, ми повинні були не тільки Код псевдокод але фактичний код реалізувати те, що це журнал база н, або увійдіть, швидше, з п, база 2, з точки зору його часу роботи. Так чому, чорт візьми, ми хотіли б почати використовуючи щось на кшталт пов'язаного списку? Так. АУДИТОРІЯ: Таким чином, ви можете додати елементи в масив. David J. Малан: Таким чином, ви можете додавати елементи в масив. І це теж є тематичним. І ми будемо продовжувати бачити це, це компроміс, набагато як ми бачили Компроміс з сортування злиттям. Ми могли б реально прискорити пошук або сортування, а, якщо ми витрачаємо трохи більше місця і мати додатковий шматок пам'яті або масив для сортування злиттям. Але ми проводимо більше простір, але ми економимо час. В цьому випадку, ми відмовившись від часу, але ми забезпечення гнучкості, Динамізм, якщо хочете, які, можливо, позитивна риса. Ми також проводити простір. В якому сенсі пов'язані перерахувати дорожче з точки зору простору, ніж масив? Де додатковий простір приходять? Да? АУДИТОРІЯ: [нерозбірливо] покажчик. David J. Малан: Так, ми також є вказівник. Так що це minorly дратує в тому, що більше не є Я зберігання просто Int для представлення Int. Я запам'ятовування Int і а покажчик, який також 32 біт. Так що я буквально подвоюючи участь обсяг простору. Так ось компроміс, але от у випадку междунар. Припустимо, що ви не зберігання Int, але припустимо, що кожен з цих прямокутників або кожен з цих людей представляв слово, англійське слово, яке може містити п'ять знаків, 10 символи, може бути, навіть більше. Тоді додавши всього 32 більше бітів може бути менш великої угоди. Що робити, якщо кожен із студентів в демонстрації були буквально студентські Структури, які мають імена і будинків і, можливо, телефонів і Twitter ручки тощо. Так все поля ми почали говоримо про другий день, набагато менш великої угоди, як наші вузли стають більш цікавими і великий, щоб провести, а, додатковий покажчик просто зв'язати їх разом. Але насправді, це компроміс. І справді, код складніше, як ви будете см по побіжно що конкретний приклад. Але що, якщо було деякі Святий Грааль тут. Що робити, якщо ми не зробимо крок назад, але масивний крок вперед і впровадити дані Структура, через який ми може знайти елементи, такі як Джек або Christine або будь-які інші елементи в цьому масиві в істинно постійного часу? Пошук постійна. Видалити постійна. Вставка постійна. Всі ці операції є постійними. Це було б нашим святим Граалем. І що це, де ми підберуть наступний раз. Побачимося.