Виступаючий 1: Все в порядку, так що ми повернулися. Ласкаво просимо до CS50. Це кінець тижня сім. Тому нагадаємо, що минулого разу, ми почали дивлячись на декілька більш складно структур даних. Так як досі, все, що ми були дійсно У нашому розпорядженні було цього, масив. 

Але перш ніж відкинути масив що не все, що цікаво, що це дійсно так насправді, те, що деякі з Плюси цього простого даних структури досі? Яке це добре? До цих пір, як ми бачили? Що у тебе? Нічого. 

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: Що це? 

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: фіксований розмір. Отже, чому фіксований розмір хороший, хоча? 

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: Добре, так що це ефективно в тому сенсі, що ви можете виділити Фіксована сума в просторі, який, ми сподіваємося, Саме стільки простору, як ви хочете. Так що може бути абсолютно плюс. 

Що ще по одній стороні масиву? Так? 

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: Все - Пробачте? 

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: Всі коробки в пам'яті або поруч один з одним. І це корисно - чому? Абсолютно вірно. Але як ми можемо використовувати це правда? 

СТУДЕНТ: [нерозбірливо]. 

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

І таким химерним способом опису, що особливість в тому, що масиви дають нам довільним доступом. Просто за допомогою квадратних дужок позначення і номери, ви можете перейти до конкретного елемента в масиві за постійний час, Big O одного, так би мовити. 

Але є деякі мінуси. Що масив не робити дуже легко? Що це не дуже добре? 

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: Що це? 

СТУДЕНТ: [нерозбірливо]. 

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

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

Так зв'язаний список просто дані структура, що складається зі структур C в цьому випадку, коли структура, нагадаємо, є просто контейнер для одного або більше конкретних типи змінних. У цьому випадку, що ж типи даних Мабуть, всередині структури, який Останній раз ми називається вузлом? Кожен з цих прямокутників вузла. І кожен з менших прямокутників Всередині це тип даних. Які ж тоді ми говорили вони були в понеділок? Так? 

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: змінні і покажчик, або точніше, ціле для N, і покажчик на дні. Обидва ці, виявляється, 32 біта, по крайней міру на комп'ютері, як це CS50 Appliance, і тому вони звертається однаково в розмірі. 

Так що з допомогою покажчика хоча для мабуть? Навіщо додавати цю стрілку тепер, коли масиви, були так добре і чисто і просто? Що робите для покажчика нами в кожному з цих вузлів? 

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: Абсолютно вірно. Це вам каже, де далі йде. Так що я, звичайно, використовувати аналогію використанням потоку до виду нитка ці вузли разом. І це саме те, що ми робимо з покажчиків, оскільки кожен з цих ділянок пам'яті може або не може бути суміжні, спина до спини до спини всередині оперативної пам'яті, тому що кожного разу, коли ви зателефонуйте Malloc кажуть: дай мені достатньо байтів для нового вузла, він може бути тут, або він може бути тут. Це могло б бути тут. Це могло б бути тут. Ви просто не знаю. 

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

Таким чином, недолік, то, Зв'язаний список є що? Що таке ціна, що ми мабуть платити? 

СТУДЕНТ: [нерозбірливо]. 

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

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

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

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

СТУДЕНТ: [нерозбірливо]. 

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

Тому ми вважаємо, що ми можемо реалізувати цей вузол в коді. І ми бачили таку синтаксису раніше. Typedef просто визначає новий тип для нас, дає нам як синонім Рядок була для символ *. У цьому випадку, він збирається дати нам скорочений запис, так що структура вузла Натомість можна просто бути записана у вигляді вузол, який є набагато більш чистою. Це набагато менш багатослівним. 

Усередині вузла мабуть Цілочисельне називається п, а потім структури вузла * що означає саме те, що ми хотіли Стрілки на увазі, покажчик на інший вузол точно такий же тип даних. І я пропоную, щоб ми могли реалізувати Функція пошуку, як це, яке в перший погляд може здатися, трохи складним. Але давайте подивимося його в контексті. 

Дозвольте мені перейти до приладу тут. Дозвольте мені відкрити файл з ім'ям Список нулю точка ч. І що тільки містить визначення ми тільки що бачили хвилину тому для цих даних тип називається вузлом. Тому ми ввели, що у файл точка ч. 

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

Якби я зараз відкрити список нулю точка C, помітити кілька речей. Вона включає в себе кілька файлів заголовка, більшість якого ми бачили раніше. Вона включає в себе свій власний файл заголовка. 

І, як осторонь, чому це подвійна котирування тут, в відміну від кута кронштейни на лінії, яка Я виділив там? 

СТУДЕНТ: [нерозбірливо]. 

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

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

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

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

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

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

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

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

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

Отже, давайте поглянемо на пошуки, якщо я запустити команду три, я хочу пошуку , Скажімо, числа 43. І нічого не було знайдено мабуть, тому що я не повернувся без відповіді. Отже, давайте зробимо це знову. Пошук. Давайте шукати для 50, або, скоріше, пошук для 42, у якого є гарна майже невловима зміст. І я знайшов сенс життя там. Число 42, якщо ви не знаєте, посилання Пошук в Інтернеті. Добре. Так, що ця програма для мене зробив? Це просто дозволив мені вставити таким чином, далеко і пошук елементів. 

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

Потім помітив цього. Я збираюся створити тимчасову змінну У лінії 188 називається покажчиком - PTR - міг би назвати її як завгодно. І це вказівник на вузлі бо Я сказав вузла * там. І я ініціалізації рівним перший, так що я ефективно моє пальця, так би мовити, на самому Перший елемент списку. Так що, якщо моя права рука тут PTR Я вказуючи на те ж саме, що перший вказує на. 

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

І стрілка покажчика N означає, що? Ну, якщо ми повернемося до картини тут, чи є у мене пальцем, вказуючи на що перший вузол, що містить дев'ять, стрілки по суті означає, що перейти до вузла і захопити значення в точці N, У цьому випадку, поле даних називається н. 

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

СТУДЕНТ: [нерозбірливо]. 

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

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

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

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

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

Таким чином, ми не будемо зупинятися на інших реалізацій вставляти і видаляти і обходу, перші два з які є достатньо складною. І я думаю, що це досить легко отримати втратив, коли роблять це в усній формі. Але що ми можемо зробити тут Спробуйте визначити, як Краще робити це візуально. Тому що я хотів би запропонувати, що якщо ми хочете вставити елементи в цій існуючий список, який складається з п'яти елементів - 9, 17, 22, 26 і 33 - Якби я збирався здійснити це в код, мені потрібно подумати, як йти про це. 

І я хотів би запропонувати кроки дитини якої, в даному випадку я маю на увазі, які можливих сценаріїв, які ми можуть виникнути в цілому? При реалізації вставки для пов'язаного списку, це тільки, трапляється, Конкретним прикладом розмір п'ять. Ну, якщо ви хочете вставити цифру, як, скажімо, номер один, і підтримання порядку сортування, де , Очевидно, номер один потрібно йти в цьому конкретному прикладі? Наприклад, на початку. 

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

Давайте обривати, може бути, так легко, або навіть простий випадок, умовно кажучи. Припустимо, я хочу, щоб вставити 35 числа в порядку сортування. Це, очевидно, належить там. Так що, очевидно, покажчик буде повинні бути оновлені в цьому сценарії? 34 в покажчик стає NOT NULL але адреса структури містить номер 35. Так от випадок два. Так що вже, я начебто квантування скільки роботи я повинен зробити тут. 

І, нарешті, очевидний випадок середина Дійсно, в середині, якщо я хочу вставляти щось на кшталт говорять 23, який йде між 23 і 26, але Тепер все стає трохи більш бере участь, тому що покажчики мають бути змінені? 22 Так, безумовно, має бути змінена тому що він не може вказати на 26 більше. Йому потрібно, щоб він вказував на новий вузол, Мені доведеться виділити по телефону Malloc або деякий еквівалент. 

Але потім я також потрібно, щоб новий вузол, 23 У цьому випадку, щоб мати свій покажчик вказуючи на кого? 26. І там буде Порядок операцій тут. Тому що якщо я зроблю це нерозумно і я Наприклад початку на початку списку, і моя мета, щоб вставити 23. І я перевіряв, воно належить тут, близько дев'яти? Ні. Чи має місце тут, поруч з 17? Ні. Чи має вона належить тут поруч з 22? Так. 

Тепер, якщо я дурний тут, і не думаючи, що це до кінця, я міг би виділити мій новий вузол 23. Я міг би оновити покажчик з вузол, який називається 22, вказуючи його на новий вузол. І що тоді мені доведеться оновлювати покажчик на новий вузол, щоб бути? 

СТУДЕНТ: [нерозбірливо]. 

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

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

Гаразд, якщо вже ти тут, по-перше, Ви хотіли б бути тим, ніяково Скло в Google тут? Гаразд, гаразд, скло, Запис відео. Добре, ви добре йти. 

Гаразд, так що якщо ви, хлопці, можете приїхати Тут, я підготував заздалегідь деякі цифри. Гаразд, іди сюди. А чому б вам не піти трохи далі, що шлях. І подивимося, як тебе звати, Скло з Google? 

СТУДЕНТ: Бен. 

Виступаючий 1: Бен? ОК, Бен, ти будеш першим, буквально. Отже, ми збираємося відправити вам в кінці стадії. Гаразд, і ваше ім'я? 

СТУДЕНТ: Джейсон. 

Виступаючий 1: Джейсон, OK ви будете бути номером дев'ять. Так що, якщо ви хочете слідувати Бен таким чином. 

СТУДЕНТ: Джилл. 

Виступаючий 1: Джилл, ви збираєтеся бути 17, який, якщо б я зробив це більш розумно, я б почалося на іншому кінці. Ви йти цим шляхом. 22. А ви хто? 

СТУДЕНТ: Марії. 

Виступаючий 1: Марія, ви будете 22. А ваше ім'я? 

СТУДЕНТ: Кріс. 

Виступаючий 1: Кріс, ви будете 26. А потім, нарешті. 

СТУДЕНТ: Діани. 

Виступаючий 1: Діана, ви будете 34. Таким чином, ви іди сюди. 

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

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

Отже, нехай, по-перше, я хочу обривати що перший приклад вставки, скажімо 20 в списку. Так що я збираюся потрібно, щоб хтось втілюють у собі число 20 для нас. Так що мені потрібно когось Malloc від аудиторії. Піднімайся. Як тебе звуть? 

СТУДЕНТ: Брайан. 

Виступаючий 1: Брайан, все гаразд, так що ви повинен бути вузол, що містить 20. Гаразд, іди сюди. І очевидно, що, де Брайан дійсно належите? Таким чином, в середині - власне, почекай хвилинку. Ми робимо це не в порядку. Ми робимо це набагато складніше , Чим вона повинна бути в першу чергу. Добре, ми збираємося безкоштовно Брайан Брайан і Realloc як п'ять. 

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

СТУДЕНТ: Джейсон. 

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

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

Гаразд, так що ви повинні кілька кандидатів. Або Бен або я або Джейсон Брайан або або всі інші, які покажчики потрібно змінити? Скільки всього? 

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

Хто отримує вказав на кого? 

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: Добре, таким чином Брайан щоб вказати на Джейсона. Але я втратив цей покажчик? Чи знаю я, де Джейсон? 

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: я роблю, так як я тимчасовий покажчик. І мабуть, я не змінив , Щоб вказати на новий вузол. Так що ми можемо просто Брайан точки той, хто на мене вказуючи на. І ми зробили. Таким випадком, вставка на початок списку. Були два ключових кроки. По-перше, ми повинні оновити Бена, а потім Ми також повинні оновити Брайан. І тоді я не доведеться турбуватися тащась через решту список, тому що ми вже знайшли його розташування, тому що він належав до ліворуч від першого елемента. 

Гаразд, досить проста. Справді, здається, що ми вже майже робить це занадто складно. Отже, давайте обривати кінця списку, і побачити, де Складність починається. Отже якщо зараз, я Alloc від аудиторії. Будь хоче грати 55? Гаразд, я бачив вашу руку першим. Піднімайся. Так. Як тебе звуть? 

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: Habata. ОК, давай вгору. Ви будете номером 55. Таким чином, ви, звичайно, належать в кінці списку. Так що давайте переграти моделювання зі мною будучи PTR на мить. Так що я збираюся першим, щоб вказати на все, що Бена вказуючи на. Ми обидва тепер, вказуючи на Брайана. Так 55 не менше, аніж п'ять. Так що я збираюся оновити себе, вказуючи на наступний покажчик Брайана, який Зараз, звичайно, Джейсон. 55 становить не менше дев'яти, так Я збираюся оновити PTR. Я збираюся оновити PTR. Я збираюся оновити PTR Я збираюся оновити PTR. І я збираюся - Хм, що це тебе звати? 

СТУДЕНТ: Діани. 

Виступаючий 1: Діана вказує, звичайно, при нульовому лівою рукою. То де ж насправді Habata належать ясно? З лівого боку, тут. Так як я знаю, поставити її тут Я думаю, що я облажався. Адже що таке мистецтво PTR даний момент часу? Null. Так що, хоча, візуально, ми можемо Очевидно, всі ці хлопці тут на сцені. Я не стежив за попередніми людина в списку. У мене немає пальцем вказуючи, У цьому випадку номер вузла 34. 

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

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

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: Отже, Діани. Де Ви хочете, щоб вказати Ліва Діани покажчик у? На 55, мабуть, з тим щоб ми вставили туди. А де повинні 55 покажчика йти? Вниз, що представляє нульовий. І мої руки, на даний момент, не значення, тому що вони були просто тимчасових змінних. Так що тепер ми закінчимо. 

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

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

СТУДЕНТ: [нерозбірливо]. 

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

Давайте зробимо останній приклад тут і покласти ці хлопці з їх страждання. Так Malloc 20. Піднімайтеся з проходу там. Гаразд, як тебе звати? 

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: Пробачте? 

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: Demeron? ОК піднімайся. Ви повинні бути 20. Ви, очевидно, збираються належать від 17 до 22. Отже, дозвольте мені дізнатися свій урок. Я збираюся почати покажчик вказуючи на Брайана. І я буду мати мою ліву руку оновлювати тільки з Брайаном, як я переїхати в Джейсон, 20 перевірка робить менше дев'яти? Ні. На 20 менше, ніж 17? Ні. На 20 менше, ніж 22? Так. Так що покажчики або рук потрібно змінити де вони вказуючи зараз? 

Так що ми можемо зробити, вказуючи на 17 20. Так що це нормально. Куди ми хочемо, щоб вказати покажчик зараз? У 22. І ми знаємо, де 22, знову ж таки завдяки на мій тимчасовий покажчик. Таким чином, ми все гаразд там. Так через це тимчасового зберігання Я стежив, де всі. І тепер ви можете візуально вдаватися в якому Ви належите, і тепер нам потрібно 1, 2, 3, 4, 5, 6, 7, 8, 9 куль стрес, і оплески для ці хлопці, якщо ми могли. Красиво зроблено. 

[Оплески] 

Виступаючий 1: Добре. І ви можете тримати частини папери на пам'ять. 

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

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

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

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

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

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

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

Так що, якщо у нас є масив від загального розміру 26 так що це 25-й розташування в нижній частині, і я стверджую, що Аліса Перше слово в словнику імена, які я хочу вкласти в оперативну пам'ять, в цю структуру даних, де інстинкти говорять вам, що Аліси ім'я має йти в цьому масиві? 

У нас є 26 варіантів. Де ми хочемо поставити її? Ми хочемо її в кронштейн нулю, чи не так? Для Аліси, давайте назвемо що нулю. І B буде однією і С будуть два. Отже, ми збираємося писати Аліса ім'я тут. Якщо ми потім вставте Боб, його Назва піду сюди. Чарлі піду сюди. І так далі вниз через цієї структури даних. 

Це прекрасна структури даних. Чому? Ну те, що час роботи вставка ім'я людини в цю Структура даних прямо зараз? Враховуючи, що ця таблиця буде реалізований, дійсно, як масив. Ну, це постійний час. Це порядку одиниці. Чому? 

Ну як ви визначаєте, Де Alice належить? Ти дивишся на яку букву її імені? Перше. І ви можете отримати там, якщо це рядок, просто дивлячись на рядок Кронштейн нулю. Таким чином, нульовий символ рядка. Це легко. Ми зробили це в Crypto Призначення тижні тому. І те, як тільки ви знаєте, що Аліси Лист капіталу, ми можемо відняти від 65 років і сам капітал, , Що дає нам нулю. Таким чином, ми тепер знаємо, що Аліса належить за місцем знаходження нуля. 

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

Але, звичайно, я поводжуся наївна, так? Що робити, якщо є Аарона в класі? Або Алісія? Або будь-які інші імена, що починаються з А. Куди ми збираємося поставити що людина, чи не так? Я маю на увазі, просто зараз є тільки три люди на стіл, тому можливо, ми Аарон повинен покласти за місцем знаходження нуль один два три. 

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

Дозвольте мені досліджувати решту цього дані Структура, шукаючи місце, щоб покласти хтось, як ім'я Аарона. І так, що теж починає прийняти лінійний час. Більше того, якщо ви зараз хочете знайти Аарон в цій структурі даних, і ви перевірити і ім'я Аарона тут немає. В ідеалі, ви просто сказали б Аарона не в структурі даних. Але якщо ви починаєте звільняючи місце для Аарон, де мало бути D або E, ви, гіршому випадку, доведеться перевірити Вся структура даних, у цьому випадку вона переходить у щось лінійний в розмір таблиці. 

Так що все в порядку, я буду це виправити. Проблема тут у тому, що у мене було 26 елементів в цьому масиві. Дозвольте мені змінити. На жаль. Дозвольте мені змінити його так, що замість буття розмір 26 в цілому, зверніть увагу на нижню Індекс змінюватиметься на N мінус 1. Якщо 26 явно замалий для людей " імена, тому що є тисячі імена світу, давайте просто робити в 100 або 1000 або 10000. Давайте просто виділити набагато більше місця. 

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

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

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

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

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

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

СТУДЕНТ: [нерозбірливо]. 

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

Так що тепер у нас є можливість жорсткий код у нашій програмі Розмір таблиці. У цьому разі, ми знаємо, ніколи немає більше 31 днів на місяць. Так жорстке кодування значення, як 31 розумне в цьому контексті. У контексті імен, жорсткого кодування 26 не є необгрунтованим його людей тільки імена починаються з, наприклад, алфавіту з участю до Z. 

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

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

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

Таким чином, в кімнаті N CS50 студентів, що ймовірність того, що принаймні Два студенти в кімнаті мають однаковий день народження? Так що є що. Кілька Hund - 200, 300 людей тут і кілька сотні людей у ​​себе вдома сьогодні. Так що якщо ви хотіли запитати себе, що це ймовірність дві людини У цьому номері, що має той же день народження, ми можемо зрозуміти це. І я стверджую, насправді є два людей з такими ж день народження. 

Наприклад, хто-небудь мають сьогодні день народження? Вчора? Завтра? Все в порядку, тому він відчуває себе, як я збираюся щоб зробити це 363 або близько того більше раз насправді з'ясувати, Якщо у нас є зіткнення. Або ми могли б просто зробити це математично а не втомлює робити це. І пропоную наступне. 

Тому я пропоную, щоб ми могли моделювати Ймовірність двох людей з ж день народження, як і ймовірність 1 мінус ймовірність не має Того ж дня народження. Таким чином, щоб отримати це, і це тільки химерний спосіб написання цього, для Перший чоловік у кімнаті, він або вона може мати будь-яку одну з можливих Дні народження припускаючи, 365 днів у році, з вибаченнями для осіб з Лютнева 29 років. 

Таким чином, перша людина в цьому номері безкоштовний мати будь-яку кількість народжень з 365 можливостей так, щоб ми зробимо це 365 розділити на 365, який є одним. Наступний чоловік у кімнаті, якщо мета , Щоб уникнути зіткнення, можна тільки його або її день народження про те, як багато різних можливих днів? 364. Таким чином, другий доданок в цьому виразі по суті роблять, що математика для нас шляхом вирахування від одного можливий день. А потім на наступний день, на наступний день, на наступний день до загальної кількості людей у ​​кімнаті. 

І якщо ми, то розглянемо, що ж тоді є ймовірність не кожен має унікальні дні народження, але знову ж мінус 1 що, що ми отримуємо вираз , Що може дуже химерно виглядати наступним чином. Але це більш цікаво дивитися на візуально. Це графік, де по осі абсцис являє Кількість осіб в кімнаті, кількість народжень. На осі ординат ймовірність зіткнення, дві людини що мають той же день народження. 

І їжу додому від цієї кривої що, як тільки ви отримаєте як 40 студенти, твоя черга на 90% ймовірності комбінаторно двох чоловік або більше має Того ж день народження. І як тільки ви отримаєте 58 людина подобається це майже 100% шанс двох людей у ​​кімнаті збираються мати ж дня народження, хоча є 365 або 366 можливих відра, і Тільки 58 осіб у кімнаті. Просто статистично ви, ймовірно, отримати зіткнень, яка в короткі мотивує це обговорення. Що навіть якщо ми отримати фантазії тут, і почати з цих ланцюгів, ми все ще доведеться зіткнень. 

Тож виникає питання, що таке витрати на ведення операції вставки і видалення в структуру даних, як це? Ну дозвольте мені запропонувати - і дозвольте мені повернутися до екрану над тут - якщо ми п елементів у список, так що якщо ми намагаємося вкласти N елементів, і у нас є скільки всього відра? Скажімо, 31 всього відра у разі народження. Яка максимальна довжина одного цих ланцюгів потенційно? 

Якщо знову є 31 можливих Дні народження в цьому місяці. Але ж це тільки злипання всіх - насправді це дурний приклад. Давайте робити, а не 26. Так що, якщо насправді є люди, чиї імена Почніть з через Z, тим самим даючи нам 26 можливостей. І ми, використовуючи структуру даних, як той, який ми тільки що бачили, в результаті чого ми маємо масив покажчиків, кожен з яких вказує на зв'язаний список, де Перший список всі з ім'ям Еліс. Другий список з кожним ім'я, що починається з, починаючи з В, і так далі. 

Яка імовірність довжина кожного з ці списки, якщо припустити, хороший чистий Розподіл імен через Z по всій структурі даних? Там у російських людей в структурі даних поділене на 26, якщо вони красиво поширитися по всій структурі даних. Таким чином, довжина кожного з цих ланцюгів п поділене на +26. Але у великих позначення О, що це? Що це насправді? Так що це дійсно просто п, чи не так? Тому що ми говорили в минулому, тьфу, що ви розділите на 26. Та, насправді це швидше. Але в теорії, це не принципово все, що швидше. 

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

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: Так, і ще раз, якщо це просто лінійний алгоритм часу і лінійний час структура даних, чому б мені не просто зберігати ім'я кожного у великій масиві або у великому зв'язаний список? І припиніть робити CS набагато важче , Чим вона повинна бути? Що є переконливим з цього приводу, навіть хоча я подряпав його? 

СТУДЕНТ: [нерозбірливо]. 

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

Якщо ми жертвуємо дизайн гол раніше, де ми хотіли зберегти всіх по іменах, наприклад, сортують, або всі цифри на етапі відсортовані, Припустимо, що у нас є несортоване зв'язаний список. Це тільки варто нам один або два етапи, Як і у випадку з Беном і Брайан раніше, вставити елемент у початку списку. Так що, якщо ми не дбаємо про сортування всі з імен, починаючи з або всі імена, що починаються з B, ми все ще можемо досягнення постійної час вставки. Тепер дивлячись Аліси або Боба чи будь-яке ім'я в цілому все ще що? Це велике О від N поділене на 26, в ідеальному випадку, коли все це рівномірно розподілені, де є стільки учасника як є Z, який, ймовірно, нереально. Але це як і раніше лінійно. 

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

Дозвольте мені запропонувати іншу Рішення в цілому. І якщо цього не уб'є вас наповал, ми зі структур даних. Так це він, синтаксичного дерева - вид дурне ім'я. Воно походить від витягів і слово пишеться синтаксичного дерева, т-р-і-е, через Звичайно пошуку звучить як синтаксичного дерева. Але це історія слова синтаксичного дерева. 

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

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

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: на лівій стороні. Так що цікаво, з цими даними структура, а не магазин Рядок M-A-X-W-E-L-L зворотного косою риси нулю, всі безперервно, а не те, що ви робите полягає в наступному. Якщо це так синтаксичного дерева структури даних, кожен з яких вузлів знову масиву і ви хочете зберегти Максвелла, спочатку індекс і так кореня вузла, так що сказати, верхній вузол, в положенні М, вправо, так приблизно в середині. , А потім звідти, ви будете слідувати покажчика на дочірні вузли, так би мовити. Таким чином, в тому сенсі, дерево родини, ви будете слідувати його вниз. І це приведе вас до іншого вузла На лівій стороні, яка є просто ще один масив. 

І потім, якщо ви хочете зберегти Максвелл, ви знайдете вказівник, який представляє , Яка є цей тут. Тоді ви йдете до наступного вузла. І зверніть увагу - саме тому картини трохи обманює - цей вузол виглядати супер крихітні. Але право це Y і Z. Це просто автор усіченої знімок так, щоб ви насправді бачити речі. В іншому випадку це фото б надзвичайно широкий. Отже, тепер ви індексу в клітинку X, то W, то Е, то L, то L. Тоді в чому це цікавість? 

Ну, якщо ми використовуємо цей вид нових взяти на себе, як зберігати рядок у структури даних, вам все одно доведеться істотно галочку в даних структури, що слово закінчується. Іншими словами, кожен з цих вузлів однак потрібно пам'ятати, що ми фактично виконали всі ці покажчики і виїжджають трохи хлібних крихт на дні тут цього Структура, щоб вказати, M-A-X-W-E-L-L являє дійсно, в цій структурі даних. 

Таким чином, можна зробити наступним чином. Кожен з вузлів на зображенні ми просто пила має один, масив розміром 27. І це зараз 27, тому що в P встановити шість, ми фактично дають вам апостроф, щоб ми могли матиме імена, як O'Reilly та інші з апострофа. Але та ж ідея. Кожен з цих елементів у масиву вказує на структуру вузол, так що просто вузлом. Так що це дуже нагадує нашої пов'язаного списку. 

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

Так що це синтаксичного дерева. А тепер питання в тому, що є час його роботи? Він великий O п? Це щось ще? Ну, якщо ви п імена в цих даних Структура, Максвелл всього лише один з них, що час роботи вставки або знайти Максвелла? Що час роботи вставки Максвелла? Якщо є інші назви N вже в таблиці? Так? 

СТУДЕНТ: [нерозбірливо]. 

Виступаючий 1: Так, це довжина імені, чи не так? Так М-а-х-З-е-л-л тому він відчуває себе, як це Алгоритм Big O семи. Тепер, звичайно, ім'я буде змінюватись в довжину. Може бути, це коротке ім'я. Може бути, це довге ім'я. Але те, що ключовим тут є те, що це постійне число. А може бути, це не зовсім постійну, але Бог, якщо реально, в словник, там, напевно, певний межа на кількість літер у ім'я людини в конкретній країні. 

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

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

І так з цим дає вам зараз можливість встановити шість р, яка буде знову пов'язано із здійсненням власного перевірка орфографії, читання в 150 000 словами, як краще зберегти цю не обов'язково є очевидним. І хоча я прагнув знайти Святий Грааль, я не стверджують, що це синтаксичного дерева. Справді, Хеш-таблицю можна дуже добре виявитися набагато більш ефективним. Але це тільки - це тільки одна з проектних рішень Ви повинні зробити. 

Але на закінчення давайте 50 або близько того секунди, щоб поглянути на те, що лежить попереду на наступному тижні і далі ми переходимо з цієї командного рядка З миром, якщо на веб-програми речей заснований і мов, як PHP і JavaScript і сам Інтернет, протоколів, таких як HTTP, які у вас є само собою зрозумілим, протягом багатьох років зараз, і кожен набрав більше день, мабуть, і не бачив. І ми почнемо відігніть шарах Що таке Інтернет. А що це за код, який лежить в основі сьогоднішньої інструментів. Так 50 секунд Цього тизер тут. Я даю вам Воїни Мережі. 

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

-Він прийшов із повідомленням. З протоколом все своє. Він прийшов у світ жорстоких брандмауерів, байдужими маршрутизатори, і небезпеки далеко гірше, ніж смерть. Він швидкий. Він сильний. Він TCPIP. І у нього є вашу адресу. Воїни в Мережі. 

[КІНЕЦЬ відеовідтворення] 

Виступаючий 1: Тобто, як в інтернеті будемо працювати наступного тижня.