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

АУДИТОРІЯ: Ми можемо динамічно змінити її розмір. 

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

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

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

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

АУДИТОРІЯ: Це змушує його рухатися по одному. 

СПІКЕР 1: змушує його рухатися по одному. І якщо бути більш точним, він буде зберігати адреса вузла, який призначається, щоб бути семантично поруч з ним, вірно? Так що не збирається обов'язково рухатися нічого. Це просто буде зберігати значення, яке буде адреса якогось іншого вузла, і ось чому ми сказали структура вузол зірка, зірка, що позначає покажчик або адресу. ОК, так що тепер якщо припустити, що ми маємо це N доступні для нас, і давайте Припустимо, що хтось ще вставляється цілу купу цілих чисел у зв'язаному списку. І, що пов'язано список вказує якийсь момент змінна називається список, що це пройшов тут у якості параметра, як я можу йти про лінії 14 здійсненні пошуку? Іншими словами, якщо я реалізую Функція, мета якого в житті це прийняти Int і потім початок пов'язаного списку, що покажчик на зв'язаний список. Як перші, хто я думаю, Девід був наш волонтер в понеділок, він, вказуючи на вся зв'язаний список, Це як якщо б ми передаємо Девід, як наш аргумент тут. Як ми можемо йти про проходження цей список? Що ж, виявляється, що, хоча покажчики є відносно новими в даний час для нас, ми можемо зробити це відносно прямо. 

Я збираюся йти вперед і оголосити тимчасову змінну, що за угодою тільки збирається щоб назвати покажчик, або PTR, але ви могли б назвати це все, що ви хочете. І я збираюся ініціалізації це на початку списку. Таким чином, ви можете б думаю це а мені вчителі днях, вид, вказуючи на когось серед наших людей в якості добровольців. Так що я тимчасову змінну, що це просто вказуючи на те ж саме що наш збігом імені Робота на громадських засадах Давид вказував. Тепер у той час як покажчик не нульовий, бо відгук що нульова деякі особливе значення сторожового розмежовує кінець списку, так що поки я не вказуючи на земля, як наш останній волонтер було, давайте йти вперед і виконайте такі дії. Якщо pointer-- і тепер я як би хочу робити те, що ми зробили з учнем structure-- якщо покажчик точка поруч equals-- швидше, якщо покажчик точка N дорівнює дорівнює змінна N, то Аргумент, який був прийнятий в, то я хочу, щоб йти вперед і сказати, повернутися правда. Я знайшов номер N всередині один з вузлів мого пов'язаного списку. Але більше крапка не працює в даному контексті, бо покажчик, PTR, це дійсно покажчик, адреса, ми насправді можемо чудово використовувати нарешті шматок синтаксису що вигляд робить інтуїтивне відчуття, а насправді використовувати стрілку тут, що означає, йдуть від що звернення до цілого там в. Так що це дуже схоже на дух оператора точка, а тому, що покажчик не є покажчиком і сам по собі не фактичний структура, ми просто використовувати стрілку. 

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

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

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

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

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

АУДИТОРІЯ: Далекий право. 

СПІКЕР 1: Далекий право. Існує в даний час 25% шанс гадати правильно. Так що буде насправді буде в порядку. За угодою, я скажу з масивом, ми, як правило, починають з лівої, але ми, безумовно, може почати з правої. Таким чином, спойлер тут буде я ймовірно, збирається залучити його ліворуч, Як і в звичайному масиві де Я почати рухатися зліва направо. Але якщо ви можете привернути арифметичне, відмінно. Це просто не звичайний. ОК, мені потрібно, щоб зробити один більше змін, хоча. Тепер, коли я штовхнув щось стек, що далі? 

Гаразд, у мене є, щоб збільшити розмір. Отже, дозвольте мені йти вперед і просто оновити це, який дорівнював нулю. І замість того, в даний час, я йду покласти в вартості одного. А тепер припустимо, я натискаю іншу Кількість в стек, як 51. Ну, я повинен зробити ще один зміна, яка до розміру двох. А потім думаю, я натискаю ще один Кількість в стек, як 61, Тепер мені потрібно, щоб оновити ще один розмір час і отримати значення 3 в якості розміру. І тепер, я називаю поп-музики. Тепер поп, за угодою, не брати аргумент. Зі стеком, вся точка метафори лоток є те, що ви не на свій розсуд піти отримати цей лоток, все можна зробити поп верхній один з стек, тільки тому, що. Це те, що ця структура даних робить. 

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

Почекай, я згадуючи другого тижня коли ми почали говорити про масиви, де це місце нульовий, це було місце одне, це було місце два, це розташування три, чотири, це виглядає як взаємозв'язок між розміром і елемент, який я хочу, щоб видалити з масиву, здається, просто що? Розмір мінус один. І ось як, як люди ми знаємо, 61 на першому місці. Як це комп'ютер буде знати? Коли ваш код, де ви, ймовірно хочу зробити розмір мінус один, так трьох мінус один дорівнює двом, і що означає, що ми хочемо, щоб позбутися від 61. І тоді ми дійсно можемо оновити розмір так, щоб розмір в даний час йде від трьох до двох. І тільки, щоб бути педантичним, я збираюся припустити, що я зробив, вірно? Ви інтуїтивно запропонував правильно я повинен позбутися 61. Але не я начебто начебто позбулися 61? Я забув ефективно що це насправді є. І згадайте PSET4, якщо ви читали стаття про судово-медичної експертизи, то у форматі PDF що у нас, ви, хлопці читати, або ви читатиме на цьому тижні PSET4. Нагадаємо, що це насправді доречні для вся ідея комп'ютерної експертизи. Що комп'ютер взагалі робить це він просто забуває, де щось, але це не пішли і, як спробувати подряпати його або перевизначення ці біти з нулів і одиниць або деякий інший випадковим чином якщо ви самі не роблять це свідомо. Так ваша інтуїція була Добре, давайте позбутися 61. Але насправді, ми не повинні турбуватися. Нам просто потрібно забувати, що це там, змінивши наш розмір. 

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

Тепер, чому це? Тепер ми просто повинні бути комфортно з той факт, що, коли працює мій програми, Я, ймовірно, збирається повинні запитати людину, скільки номерів ви хочете зберегти? Таким чином, вхід повинен звідкись. Але як тільки я знаю, що число, то я можу тільки використовувати те, що працювати, щоб дати мені шматок пам'яті? Я можу використовувати Танос. І я можу сказати, будь-яку кількість байт я хочу повернутися на ці Nths. І все, що потрібно зберігати в цифрах Мінлива тут всередині цієї структури повинно бути що? Що насправді відбувається в Цифри в цьому випадку? Так, це покажчик на перший байт цього шматка пам'яті, або, більш конкретно, адреса з перших з цих байт. Не має значення, якщо це один байт або байт, млрд Мені просто потрібно, щоб піклуватися про першу. Тому що те, що Танос гарантії і мої операційної системи гарантій, є те, що шматок пам'яті I отримати, він збирається бути суміжними. Там не буде прогалин. Так що, якщо я попросив 50 байт або 1000 байт, вони все буде спина до спини до спини. І так довго, як я пам'ятаю, як великий, як багато я попросив, все мені потрібно знати перший такий адресу. 

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

Чому це не достатньо мати тільки розмір? Ну, давайте штовхати ці ж цифри на. Так що я pushed-- я в чергу, або штовхнув. Тепер я в чергу 50, а потім 51, а потім 61, і крапка точка точка. Так от поставити в чергу. Я в черзі 50, то 51, то 61. І, що виглядає ідентично в стек досі, крім мені потрібно зробити одна зміна. Мені потрібно, щоб оновити цей розмір, так що я йду від нуля до одиниці до двох-трьох Тепер. Як з черги? Що відбувається з DEQUEUE? Хто повинен прийти з цього списку в першу чергу якщо це лінія на Apple Store? Так 50. Так що це свого роду складніше цього разу. У той час як останній раз це було супер просто, щоб просто робити розмір мінус один, Я до кінця мого масиву ефективно де цифри, це знімає 61. Але я не хочу, щоб видалити 61. Я хочу взяти 50, які був там в 5:00 вибудовуватися для Новий iPhone або ще багато чого. І так, щоб позбутися від 50, я не можете просто зробити це, чи не так? Я можу викреслити 50. Але ми тільки що сказали, ми не повинні бути настільки анальний щоб видряпати або приховати дані. Ми можемо просто забути, де вона є. 

Але якщо я можу змінити мій розмір тепер два, це достатньо інформації щоб знати, що відбувається в моєму черзі? Не зовсім. Як мій розмір в два, але де ж черзі починають, особливо якщо я досі ті ж номери в пам'яті. 50, 51, 61. Тому мені потрібно пам'ятати, Тепер, коли фронт. І таким чином, я запропонував до там, ми тільки що називається N-й фронт, чий початковий Значення має бути що? Нуль, тільки початок списку. Але тепер на додаток до зменшуючи розмір, ми просто збільшуємо фронт. Тепер ось інша проблема. Тому, як тільки я весь час. Припустимо, що це число як 121, 124, а потім, чорт візьми, Я з космосу. Але зачекайте хвилину, я не є. Таким чином, на даний момент в історії, Припустимо, що розмір одного, двох, три, чотири, так що припустимо, що розмір чотирьох, передня одна, так 51 на фронті. Я хочу поставити ще один номер тут, але, чорт візьми, я з космосу. Але я не дуже, чи не так? Де я можу поставити деякі додаткова вартість, як 171? Так, я міг тільки частково повернутися туди, вірно? А потім закреслити 50, або просто переписати його з 171. І якщо вам цікаво, чому наші номери отримав так випадково, вони зазвичай прийнято комп'ютер наука курси в Гарварді після CS50. Але це був хороший оптимізація, тому що тепер я не витрачати простір. Я досі повинні пам'ятати, наскільки велика ця річ спільна. Це п'ять всього. Тому що я не хочу, щоб почати перезапис 51. Так що тепер я як і раніше з космосу, так само проблема, що й раніше. Але ви можете побачити, як в даний час в коді, ви, ймовірно, потрібно написати трохи більше Складність, щоб це відбулося. І справді, те, що оператор в С, ймовірно, дозволяє Ви чарівним зробити це округлість? Та оператор по модулю, знак відсотка. Так що круто про черги, хоча ми зберегти малюнок масиви як ці, як прямих, якщо ви вид думаю про це, як вигину навколо, як коло, то просто інтуїтивно вид роботи розумово Я думаю, що трохи чистішим. Ви все одно доведеться здійснювати що ментальна модель в коді. Так що не так уже й важко, в кінцевому рахунку, реалізації, але ми як і раніше втрачають размер-- скоріше, Можливість змінювати розмір, якщо ми не зробимо це. 

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

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

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

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

Тоді він сказав, тепер Джек, наприкінці день, покласти одяг зліва коли ви кладете їх. Тоді завтра вранці, коли вам см сонцем, отримати одяг на право, з кінця рядка. Хіба ви не бачите? сказав Лу. Це буде так приємно. Ви будете носити все відразу перш ніж ви носите щось в два рази. І з усім в чергах в шафі і шельфу, Джек почав відчувати досить впевнений у собі. Все завдяки Лу і його чудовий черги. СПІКЕР 1: Гаразд, це чудово. Так що було насправді відбувається на під капотом тепер? Що ми маємо покажчики, що у нас є Танос, що у нас є можливість створити шматки пам'яті для себе динамічно. Так що це картина, яку ми побачив лише днями. Ми дійсно не зупинятися на ньому, але ця картина має вже на під капот вже кілька тижнів. І так це представляє, просто прямокутник, який ми намалювали, пам'яті комп'ютера. І, можливо, ваш комп'ютер або CS50 ID, має гігабайт оперативної пам'яті або пам'яті або два гігабайти або чотири. Це дійсно не має значення. Ваша операційна система Вікна або Mac OS або Linux, по суті дозволяє вашої програми думати, що він має доступ до всієї пам'яті комп'ютера, навіть якщо ви могли б бути запущений кілька програм відразу. Таким чином, насправді, що насправді не працює. Але це свого роду ілюзія враховуючи всі ваші програми. Так що, якщо у вас є два гігабайтами оперативної пам'яті, це як комп'ютер може думати про це. 

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

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

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

І виходить, що поганий хлопець, люди, які особливо добре з програмуванням, і намагається зламати комп'ютери, можуть використовувати цю реальність. Справді, давайте розглянемо трохи фрагмент. Таким чином, це є прикладом ви можете прочитати про більш докладно у Вікіпедії. Ми вкажу вам на Стаття якщо цікаво. Але є напад в цілому відомий як переповнення буфера, що існує до тих пір, як люди мали можливість маніпулювати пам'яті комп'ютера, особливо на C. Так що це дуже довільна програма, але давайте читати знизу вгору. Головна в ARGC символ зірки ARGV. Так що це програма, яка приймає Аргументи командного рядка. І все ж головна, мабуть, виклик функція, назвемо його для простоти F. І це проходить в чому? ARGV одного. Так вона переходить в F всі слово те, що користувач ввів в рядку після того, Назва програми взагалі. Так само, як Цезар або Vigenere, який Ви могли б пригадати, робить з ARGV. 

Так що F? F подає в рядку в якості єдиного аргументу, АКА напівкоксу зірка, ж річ, як рядок. І це називається як завгодно бар в цьому прикладі. І тоді символ з 12 тільки з точки зору непрофесіонала, що символ з дужка 12 робить для нас? Що він робить? Виділення пам'яті, спеціально 12 байта для 12 символів. Точно. І тоді останній рядок, перемішати і копія, ви, ймовірно, не бачив. Це рядок копія Функція, мета якого в житті це скопіювати його другий аргумент в якості першого аргументу, але тільки до Певна кількість байтів. Таким чином, третій аргумент говорить, скільки байт необхідно скопіювати? Довжина панелі, всі користувач вводить в. І зміст бар, цей рядок, є скопійовані в пам'ять вказав на точці С. 

Так що це, здається, свого роду нерозумно, і це. Це надуманий приклад, але це представник класу векторів атаки, спосіб нападу на програму. Все добре і чудово, якщо користувач типи в слова, що це 11 символів або менше, плюс зворотний слеш нулю. Що робити, якщо користувач в більш ніж 11 або 12 або 20 або 50 символів? Що ця програма буде робити? Потенційно SEG вина. Це відбувається сліпо копіювати все в барі до його довжині, яка буквально все в барі, на адресу вказав на С. Але З тільки превентивно дається як 12 байт. Але немає додаткової перевірки. Там, якщо умовах це немає. Там немає перевірки помилок тут. 

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

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

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

Іншими словами, якщо те, Користувач друкує в командному рядку, це не тільки те, безневинно, як привіт, але насправді це код, який еквівалентно видалити всі файли цього користувача? Або напишіть свій пароль мені? Або почати запис їх натиснення клавіш, вірно? Існує спосіб, давайте передбачають сьогодні, що вони могли б запровадити не лише в привіт світ або їх назву, вони могли істотно перейти в код, нулів і ті, що комп'ютер помилки для коду та адреси. Так нехай і дещо абстрактно, якщо користувач в досить змагальності коду що ми будемо узагальнювати тут А. А напад чи супротивники. Так що погані речі. Ми не дбаємо про номера або нулі чи одиниці сьогодні, наприклад, що ви в кінцевому підсумку перезапису, що червоний розділ, зауважити, що послідовність байт. Про 835 З нуля восьмій нулів. А тепер, як стаття Вікіпедії тут запропонував, якщо ви зараз насправді почати маркування байти в комп'ютері років пам'яті, що стаття Вікіпедії пропоную, що, те, що, якщо адреса цієї верхньому лівому байта 80 С 0 3508. 

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

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

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

Так що приємно в бінарне дерево пошуку, це що один, ми можемо реалізувати його з структури, як це. І хоча ми кидали багато структур, у вашому вони дещо Тепер, сподіваюся, інтуїтивно. Синтаксис ще таємницею напевно, але вміст вузла в цьому context--, і ми продовжуємо використовуючи слово вузол, чи є це прямокутник на екрані або круга, це лише деякі загальні контейнер, У цьому випадку дерева, як той, ми бачили, ми повинні ціле в кожному з вузлів а потім мені потрібно дві покажчики, що вказують на лівому дитини і правої дитини, відповідно. Так от, як ми могли б здійснити, що в структури. І як я міг би реалізувати це в коді? Ну, давайте швидко подивитися на цьому крихітному наприклад. Це не працює, але я скопіювати і вставити цю структуру. І якщо моя функція для бінарних Пошук дерево називається пошук, і це приймає два аргументи, ціле число N і покажчик до вузла, так що покажчик на дерево або покажчик на корінь дерева, як я можу йти про пошук N? Ну, по-перше, тому, що я справу з покажчиками, Я збираюся зробити перевірку осудності. Якщо дерево одно дорівнює нулю, є N в цьому дереві чи ні в цьому дереві? Це не може бути, чи не так? Якщо я повз нуль, немає нічого. Я міг би також просто сліпо сказати повернутися помилковим. Якщо ви не дають мені нічого, я, звичайно, не можу знайти число N. Так що ще я міг би Перевір зараз? Я хочу сказати, добре ще, якщо п менше, ніж те, що знаходиться у вузлі дерева що я був переданий значення N. Іншими словами, якщо число Я шукаєте, N, менше, ніж вузол що я дивлюся на. І вузол Я шукаю в називається дерево, і згадати з попереднього прикладу щоб дістатися до значення в покажчик, Я використовую позначення зі стрілкою. Так що, якщо N менше, ніж дерево стрілки N, я хочу, щоб концептуально йдіть наліво. Як я висловлюю пошуку залишилося? Щоб було ясно, якщо це картина в питанні, і я був прийнятий, що верхній стрілка, який спрямований вниз. Це моя покажчик дерево. Я вказую на корені дерева. І я з нетерпінням скажімо, число 44, довільно. 44 менше або більше, ніж 55, очевидно? Так це менше, ніж. І так це, якщо умова поширюється. Так концептуально, те, що я хочу, щоб пошук в наступному, якщо я шукаю 44? Так? 

Точно, я хочу пошук ліву дитини, або вліво суб-дерево цієї картини. І справді, хай мене через картина тут на мить, так як Я не можу подряпати це. Якщо я почну тут в 55, і Я знаю, що значення 44 Я шукаю, щоб ліва, це свого роду з, як розриваючи телефонну книгу в половина або розриваючи дерево навпіл. Я більше не доведеться піклуватися про весь цей половина дерева. І все ж, як не дивно, в термінах Структура, ця річ тут, що починається з 33, що саме по собі це бінарне дерево пошуку. Я сказав слово рекурсивний раніше, тому що Дійсно, це структура даних, за визначенням є рекурсивним. Ви, можливо, дерево, в цьому великий, але кожен з його дітей являє собою дерево просто трохи менше. Замість цього бути дідуся чи бабуся, тепер це просто мама ілі-- я не можу say-- не мама або тато, що було б дивно. Замість двоє дітей там буде як брат і брат. Нове покоління в родоводу. Але структурно, це та ж сама ідея. А то виходить, у мене є функція з якою я можу шукати бінарний пошук дерево. Це називається пошук. Я шукаю N в дереві зліва стрілки інше, якщо п більше, ніж значення що я в даний час. 55 в історії момент тому. У мене є функція під назвою Пошук, що я можу просто пройти N це і рекурсивний пошук суб-дерево і просто повернення все, що відповіддю. Інакше я отримав деякі підсумковий базовий випадок тут. 

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

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

Там така неефективність тут. Як би ви інтуїтивно стискати німецький прапор якщо її реалізації у вигляді файлу? Подобається те, що інформація ми не можемо турбувати зберігання на диску для того, щоб зменшити нашу розмір файлу з, як мегабайт в кілобайт, то менше? У чому полягає надмірність тут, щоб бути зрозуміло? Що ви могли б зробити? Так? Точно. Чому б не згадати, чим колір кожного пікселя штопати так само, як ви робите в PSET4 с Формат графічного файлу, чому б вам просто не уявляють ліва колонка пікселів, наприклад купа чорних пікселів, купа червоний, і купа жовтий, а потім просто якимось чином кодувати Ідея повторити цей 100 раз або повторити це в 1000 разів? Де 100 або 1000 є просто ціле число, так що ви може зійти з рук тільки один номер замість сотень або тисяч додаткових пікселів. І справді, ось як ми може стискати німецький прапор. І Тепер те, що про французьким прапором? І трохи свого роду розумовий вправу, що прапор можуть бути стислі більш на диску? Німецький прапор або французький Прапор, якщо ми візьмемо такий підхід? Німецький прапор, тому що є більш горизонтального резервування. І по дизайну, багато графічний файл Формати дійсно працювати, як сканування ліній горизонталі. Вони могли б працювати вертикально, просто людство вирішили років тому, що ми будемо як правило, думати про речі, ряд по рядках, а не по стовпцях. Так, якщо б ви були подивитися на файл розмір німецьким прапором та французькою мовами Прапор, поки дозвіл те ж саме, такої ж ширини і висота, на цей раз тут буде більше, тому що ви доведеться повторити себе три рази. Ви повинні вказати, повторення синій самостійно, білий, повторюватися, червоний, повторюватися. Ви не можете просто піти всі шлях до правої. І, як в сторону, щоб зробити очистити стиск скрізь, якщо це чотири кадри з video-- ви Нагадаю, що фільм або відео, як правило, як 29 або 30 кадрів в секунду. Це як маленький фліп книги, де вас просто побачити зображення, зображення, зображення, зображення, Зображення просто супер швидко, так що, схоже, актори на екрані рухаються. Ось джміль на Верх букетом квітів. І хоча це може бути вид важко зрозуміти, на перший погляд, єдине рух в цей фільм бджола. 

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

Але як ви стиснути текст? Як ви йти про стиснення тексту? Ну, кожен з персонажів Ascii один байт, чи вісім біт. І це свого роду німий, чи не так? Тому що ви, ймовірно, введіть A і Е, я і виводу і U багато частіше, ніж, як W або Q або Z, залежно від мови, якою Ви пишете, звичайно ,. І так, чому ми за допомогою восьмій бітів для кожного листа, в тому числі не менше популярні букви, вірно? Чому б не використовувати меншу кількість біт для супер популярні літери, як Е, то, думаю, ви перший в Колесо Фортуни, і використовувати більше бітів для менш популярні літери? Чому? Тому що ми тільки збираємося використовувати їх рідше. 

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

Я? Я? Або те, що about-- чи я? Може бути, це було всього лише два прямо Е? Так що ця проблема з декодіруемой з Морзе Код, в результаті чого, якщо тільки людина, який посилає вам повідомлення насправді робить паузу, щоб ви могли сортувати бачити або чути пропуски між буквами, це не досить просто відправити потік нулів і одиниць, або точки і тире, бо є двозначність. Е є одна точка, так що якщо вам побачити дві точки або почути дві точки, може бути, це два E-то або, може бути, це один І. Так що ми повинні систему, що це трохи розумніші, ніж це. Таким чином, людина на ім'я Хаффмана років тому вигадав саме це. Таким чином, ми просто збираємося взяти швидкий погляд на те, як дерева доречні для цього. Припустимо, що це який- нерозумно повідомлення ви хочете відправити, складається тільки з A, B, C в D's і Е х, але є багато надмірності тут. Це не означало, щоб бути англійська. Це не шифрується. Це просто нерозумно повідомлення з великою кількістю повторень. Так що, якщо ви насправді відраховувати всі А-х, Б, С-х, D's, і E-х, ось частота. 20% з букв А-х, 45% з букв є E, і три інші частоти. Ми нарахували там вручну і просто зробив математику. 

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

Які два вузли я комбінувати далі? Це трохи неоднозначним. Так є деякі випадки, в кутові розглянути, але тримати речі досить, Я збираюся вибрати 20% - Тепер я ігнорувати дітей. Я збираюся вибрати 20%, а 15% і намалюйте два нові ребра. А тепер які два вузли я логічно об'єднати? Ігнорувати всі діти, все онуки, просто подивіться на коріння Тепер. Які два вузли я зв'язати разом? Другий пункт і 0,35. Отже, дозвольте мені зробити два нових ребер. І потім, я тільки отримав один залишився. Так от дерево. І це було звернено навмисно дивитися вигляд досить, але зауважив, що ребра мають Також були помічені нуля і один. Таким чином, всі з лівого країв дорівнюють нулю довільно, але послідовно. Усі праві краю є ті. 

І так, що Хоффман запропонував є, якщо ви хочете, щоб представляти B, а не являють собою кількість, як 66 ASCII, котрий вісім цілі біт, ви знаєте, що тільки магазин зразок нуль, нуль, нуль, нулю, тому що це шлях від мого дерева, дерево Хаффмана г, до аркуша від кореня. Якщо ви хочете зберегти Е, навпаки, не відправити восьмій біт, які представляють Е. Замість цього, відправити який набір бітів? Один. І, що приємно про це є що Е є найпопулярнішим лист, і ви за допомогою короткий код для нього. Наступним найбільш популярним Лист виглядає вона був А. І так, скільки біт він пропонується використовувати для цього? Нуль, один. 

І тому, що він реалізований як це дерево, в даний час дозвольте мені передбачають є немає неоднозначності, як в Морзе Код, бо всі з Листи ви дбаєте про в кінці цих країв. Так це тільки один Застосування дерева. Це is-- і я хвиля моя рука на це, як ви може здійснити це в C структури. Ми просто повинні об'єднати символ, як гольця, і частота в лівий і правий. Але давайте подивимося на два Остаточні приклади, які ви отримати добре знайомі з після Тест нулю в проблемі встановити п'ять. 

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

Тепер стеки були зростає, що навмисне дизайн річ тут. Але що ще я міг би зробити? Тому насправді тут ми маємо купа старих книг школи іспит. Припустимо, що купу студенти імена тут. Ось більше хеш-таблиці. Замість чотирьох відер, Я, скажімо, 26. І ми не хочемо йти займати 26 речі з поза [? Анненберг?], Так що ось п'ять, які представляють А до Z. І якщо я см студента, чиє ім'я починається з А, Я збираюся поставити його або її вікторини там. Якщо хтось починає з C, там, A-- насправді, не хочуть, щоб зробити це. У іде сюди. Так що я отримав А і В і С. А Тепер ось ще студент. Але якщо це хеш-таблиці реалізовані з масивом, Я начебто угвинчується на даний момент, чи не так? Я начебто повинні покласти це десь. 

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

Але ми вже бачили більш розумні рішення тут, вірно? Що б ви зробили, замість якщо у вас є зіткнення? Якщо дві людини мають назву А, що б були розумнішими або інтуїтивне рішення, ніж просто Приміщення, де D, як передбачається, буде? Чому я не можу просто піти поза [? Анненберг?], як Танос, інший вузол, поставити його тут, а потім покласти, що студент тут. Так що я по суті є яка з масиву, або, може бути, більш елегантно, як ми починаємо бачити зв'язаний список. 

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

Так що це свого роду дурні, зухвалим жарти років тому. У CS50 рубати-а-марафон, коли студенти перевірити в, деякі TF або Каліфорнія щороку думає, що це смішно, миритися знак, як це, де це тільки означає, що якщо ваше ім'я починається з А, йти по цьому шляху. Якщо починається ваше ім'я з В, перейти this-- ОК, це смішно, може бути, пізніше в семестр. Але є ще один спосіб зробити це, теж. Вернись до цього. 

Так що ця структура. І це наша остання Структура на сьогоднішній день, щось називається Trie. Т-Р-И-Е, який чомусь не вистачає для пошуку, але це називається Trie. Так Trie ще один цікавий амальгама багато цих ідей. Це дерево, яке ми бачили раніше. Це не бінарне дерево пошуку. Це дерево з будь-якою кількістю дітей, але кожен з дітей у синтаксичного дерева є масивом. Масив розміром, припустимо, 26 або, може бути 27 якщо ви хочете, щоб підтримати дефіс імена або апострофи в іменах людей. 

І так це структури даних. І якщо ви подивитеся зверху вниз, як якби вас подивіться на верхній вузол там, М, вказуючи на крайню ліву речі там, який потім A, X, W, E, L, L. Це просто структура даних, яка довільно є збереження імен людей. І Максвелл зберігається тільки після це шлях масиву масиву на масив. Але що дивно близько Trie є що, в той час як зв'язаний список, і навіть масив, найкраще, що ми коли-небудь отримували це лінійний час або логарифмічне час шукаєте хто до. У цьому структури даних синтаксичного дерева, якщо мій структура даних має один ім'я в ньому і Я шукаю Максвелла, я збираюся знайти його досить швидко. Я просто дивлюся на М-А-Х-W-E-L-L. Якщо Ця структура даних, навпаки, Якщо N є млн, якщо є мільйон імена в цій структурі даних, Максвелл ще буде виявити вже через М-А-Х-Ш-Е-Л-Ь кроки. І David-- Д-А-В-Я-D кроки. Іншими словами, шляхом створення структура даних, що це отримав всі ці масивів, кожен з яких Самі підтримувати довільний доступ, Я можу почати дивлячись народних назвати, використовуючи кількість часу, що'S пропорційна не кількості речей в структурі даних, як мільйон існуючі імена. Кількість часу, який потрібен, щоб знайти мене М-А-Х-Ш-Е-Л-Л в цій структурі даних є пропорційна НЕ Розмір структури даних, але з довжиною імені. І реалістично Імена ми дивлячись ніколи не буде з розуму довго. Можливо, хтось має 10 характер ім'я, ім'я персонажа 20. Це, звичайно, звичайно, не так? Існує людини на Землі, який має максимально можливий ім'я, але це ім'я є константою значення довжини, вірно? Це не змінюється в будь-якому сенсі. Таким чином, в цьому випадку, ми досягнуті структурою даних що постійна часу погляд вгору. Це займе кілька кроків в залежності від довжини входу, але не число імені в структурі даних. Так що, якщо ми подвоїмо кількість імен в наступному році з мільярда до двох мільярдів, висновок Максвелла збирається взяти точно такий же кількість сім кроків щоб знайти його. І таким чином, ми, здається, досягли наш святий Грааль час роботи. 

Таким чином, пара швидких оголошень. Вікторина нуль вигадувати. Докладніше про те, що на веб-сайті Курсу протягом найближчих декількох днів. Понеділок lecture-- Це свято тут в Гарварді в понеділок. Це не в Нью-Хейвені, таким чином, ми беремо клас в Нью-Гейвен для лекції в понеділок. Все буде знятий і транслюватиметься в прямому ефірі, як звичайно, але давайте в кінцевому сьогодні з другим затиском 30 звані "глибокі думки" по Daven Фарн, який був натхненний торік у суботу "Думки" Deep Night Live в Джек Хенді, який Тепер слід розібратися. 

ФІЛЬМ: А тепер, "Глибоке Думки "по Daven Фарн. Хеш-таблиці. 

СПІКЕР 1: Гаразд, що вона в даний час. Ми будемо бачити Вас на наступному тижні. 

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

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

УПА: Гей, гей, гей, вирізати, вирізати, вирізати, вирізати. Дуг, ти не можеш просто я-так, я-так, я-так, ваш шлях через сортування злиттям. 

Даг: Я тільки що зробив. Все добре. Ми добре йти. Давайте просто тримати прокатки. Так чи інакше, 

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

УПА: Я знаю. І ми не можемо просто я-так, я-так, я-так, через весь процес. Ви повинні пояснити, як Сторони зливаються разом. 

ДАГ: Але ми вже пояснив, як два sides-- 

УПА: Ви тільки що показали їх масив злиття. Даг: Вони знають процес. Вони в порядку. Ми пішли на нього в десять разів. 

УПА: Ви тільки що пропустив прямо над нею. Ми повертаємося до одного, ви ви не можете я-так, я-так над ним. Гаразд, до одного. 

Даг: Я повинен повернутися через всі слайди? Боже. Це як в шостий раз, Ian. Все добре. 

УПА: Гаразд. Ви готові? Відмінно. Дія.