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

ANDI Пен: Ласкаво просимо в тиждень 6 розділу. Ми відхилилися від нашого стандарту розділ час у вівторок днем, щоб цей прекрасний неділю вранці. Спасибі за всім, що приєднався до мене сьогодні, але серйозно, оплески. 

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

По-друге, ми поговоримо про це. Ми поговоримо про вікторину. Ми поговоримо про те, як Ви робите в класі. Ви будете в порядку. У мене є свої вікторини для Ви в кінці тут, так що якщо ви, хлопці, хочете, щоб прийняти Погляд на неї, абсолютно нормально. 

Так швидко перш ніж ми почнемо, то Порядок денний на сьогодні виглядає наступним чином. Як ви можете бачити, ми в основному швидке звільнення через цілу купу структур даних дійсно, дійсно, дійсно швидко. Так як таке воно не буде супер інтерактивна сьогодні. Це буде просто мені ніби кричати речі, які ви, і якщо я плутаю вас, якщо я йду занадто швидко, дайте мені знати. Вони просто різні дані структури, а також в рамках Вашої PSET для цього Майбутня тиждень, ви будете буде запропоновано реалізувати один з них, можливо, два з them-- два з них в PSET. ОК, так що я просто хочу, щоб почати з деяких оголошень. Ми підемо по стеків і черг в більш Глибина, ніж те, що ми робили раніше вікторини. Ми підемо по пов'язані список знову, знову, більш докладно, ніж те, що ми мали до вікторини. І тоді ми будемо говорити про хеш столи, дерева і намагається, які все досить необхідно для вашого PSET. І тоді ми будемо йти над деякими Корисні поради для pset5. 

Отже, вікторина 0. Середня був 58%. Це була дуже низькою, і так ви, хлопці, все зробив дуже, дуже добре відповідно З цим. 

Досить багато, правило, якщо ви в стандартному відхиленні від середнього особливо, оскільки ми знаходимося в менш зручні розділ, ви абсолютно нормально. Ви на вірному шляху. Життя чудове. 

Я знаю, що це страшно думати, що Я отримав, як 40% на цьому конкурсі. Я збираюся на провал цього класу. Я обіцяю вам, ви не відбувається збій клас. Ти абсолютно нормально. 

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

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

АУДИТОРІЯ: Де робочі години? 

ANDI Пен: Годинники tonight-- о, гарне питання. Я думаю, що сьогодні ввечері офіс годин в Teal або громад. Якщо ви подивитеся онлайн CS50 і ви йдете до офісної годин, повинен бути графік, що говорить вам, де всі з них. 

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

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

ОК, так що стеки. Хто любив питання про Джека і його одяг на вікторині? Ніхто? ОК, це нормально. 

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

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

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

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

Таким чином, структура є способом, яким ми насправді створити стек. Набираємо визначити-структуру, а потім ми називаємо це стек на дні. І в стеку, у нас є два параметри що ми можемо по суті маніпулювати, так що ми повинні сЬаг зірки рядків потужності. 

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

Так, наприклад, цей прекрасний Питання було на вікторині. По суті, як ми штовхати на верх стека. Досить просто. Якщо ви подивитеся на нього, ми будемо йти через це. Якщо [нерозбірливо] размер-- пам'ятаєте, коли ви хочете отримати доступ до будь Параметр в структури, ви ім'я struct.parameter. 

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

Ви хочете отримати доступ до внутрішньої вашого стека, так s.strings, і ви збираєтеся покласти, що новий номер що ви хочете вставити в там. Давайте просто скажемо, ми хочемо, щоб вставте Int N в стек, ми могли б зробити s.strings, кронштейни, s.size дорівнює п. Тому що розмір де ми в даний час в стеку якщо ми збираємося, щоб підштовхнути це, ми просто доступ там, де розмір, тим ток повнота стека, і ми натискаємо Int N на нього. А потім ми хочемо, щоб переконатися, що ми також збільшуючи розмір п, так що ми можемо відстежувати ми в додали додатковий предмет в стек. Тепер у нас є більший розмір. Чи означає це, тут сенс все, як логічно це працює? Це був свого роду швидко. АУДИТОРІЯ: Чи можете ви перейти в s.stringss.strings [s.size] ще раз? ANDI Пен: Звичайно, так, що робить s.size даний час нам дає? АУДИТОРІЯ: Це поточний розмір. ANDI Пен: Рівне, тому поточний індекс, що наш розмір на, і тому ми хочемо, щоб поставити новий ціле число що ми хочемо, щоб вставити в s.size. Чи має це сенс? Тому s.strings, все, що це є ім'я масиву. Все це звертається до Масив в нашої структури, і тому, якщо ми хочемо, щоб розмістити п в цьому індексі, ми можемо просто відкрити його за допомогою кронштейнів s.size. Прохолодний. 

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

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

АУДИТОРІЯ: Чи будуть ці слайди і Вся ця річ буде до сьогодні-іш? ANDI Пен: Завжди, так. Я збираюся спробувати поставити це до, як через годину після. Я електронній пошті Давида, Девід буде намагатися покласти його, як через годину після цього. 

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

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

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

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

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

АУДИТОРІЯ: [нерозбірливо] ANDI Пен: Рівне, ви хочете, щоб додати це в залежності від ви написали це. Або це порожній або порожній. Отже, ви хочете, щоб додати його, ймовірно, тут, тому що, якщо розмір is-- якщо вони все сповнені, ви хочете щоб додати його прямо тут, прямо? 

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

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

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

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

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

Тепер ми хочемо, щоб додати щось ця черга, але, як ви, хлопці, можете бачити, це не так просто, як просто додати все, що після розміру бо тоді ми біжимо з Межі нашого фактичного масиву. Де ми хочемо, щоб дійсно додати тут. Це краса черзі є те, що для нас, візуально Схоже, що лінія йде, як це, але при зберіганні в структурі даних, вони дають його в якості як цикл. Це свого роду обтікає до фронту таким же чином що лінія може також обернути навколо залежно від скрізь, де вас хочу початку рядка, щоб бути. І тому, якщо ми беремо шукати тут, давайте що ми хочемо, щоб створити Функція називається Додає. Ми хотіли, щоб додати Int N в цій д. Якщо q.size q-- ми називаємо це наші дані structure-- якщо наша queue.size НЕ дорівнює потужності або якщо це менше, ніж ємність, q.strings це масив в нашій ц. Ми збираємося встановити що одно q.heads, що прямо тут, плюс q.size Модуль ємністю, яка обернути нас тут. 

Таким чином, у цьому прикладі, індекс глави 1, вірно? Індекс розміру 0, 1, 2, 3, 4. Таким чином, ми можемо зробити 1 плюс 4 модуля нашої здатності, яка 5. Що це нам дає? Що таке індекс, який виходить з цього? 

АУДИТОРІЯ: 0. 

ANDI Пен: 0, буває тут, і тому ми хочемо, щоб мати можливість вставити в прямо тут. І так це рівняння тут вид просто працює з будь-якими номерами в залежності від того, де ваш голова і ваш розмір є. Якщо ви знаєте, що ті, речі, ви знаєте, саме там, де ви хочете вставити все, що після черги. Чи має це сенс для всіх? 

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

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

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

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

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

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

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

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

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

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

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

І те, як тільки ви отримаєте тут, в той час як покажчик не дорівнює нулю, так що це петля, в якій ми буде згодом проходження решта нашому списку, тому що те, що відбувається, коли покажчик дорівнює NULL? Ми знаємо, що have-- 

АУДИТОРІЯ: [нерозбірливо] 

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

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

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

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

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

Отже, як ми б вставки вузлів, право, в списку, бо пам'ятаю, які те, що переваги мати зв'язаний список проти масив з погляду зберігання? 

АУДИТОРІЯ: Це динамічний, так легше, метою яких 

ANDI Пен: Рівне, так що це динамічний, який означає, що він може розширюватися і стискатися в залежності від потреб користувача. І так, в цьому сенсі, ми не повинні витрачати непотрібного пам'ять, тому що я якщо я не знаю, скільки я хочу значення в магазині, це не має сенсу для мене створити масив, тому що якщо я хочу, щоб зберігати 10 значень і створити масив +1000, це багато даремно пам'ять, виділено. Ось чому ми хочемо використовувати пов'язаний Список, щоб мати можливість динамічно змінити або зменшити розмір нашої. 

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

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

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

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

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

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

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

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

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

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

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

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

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

ОК, так що код буде тут. Ви, хлопці, погляньте після розділу. Це буде там. 

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

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

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

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

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

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

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

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

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

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

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

Гаразд, так що тепер я дійсно витратити, напевно, як від 15 до 20 хвилин або навалом в решту часу в розділі говорити про хеш-таблицях. Як багато з вас, хлопці, прочитав pset5 специфікації? Гаразд, добре. Це вище, ніж 50%, як правило. Все добре. 

Отже, як ви, хлопці, побачите, Ви задача в pset5 буде реалізувати словник де ви завантажити більше 140000 слів що ми даємо вам і перевірка орфографії це проти всього тексту. Ми дамо вам випадкових шт літератури. Ми дамо вам Одіссея. Ми дамо вам Іліаду. Ми дамо вам Остін Пауерс. 

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

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

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

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

І ось, якщо ми хочемо для зберігання англійські слова, ми могли потенційно просто, я не знаєте, перетворити всі перші букви в якийсь номер. І тому, наприклад, якби я хотів А бути синонімом apple-- або з індексом 0, а У синонімом 1, ми можемо мати 26 записів що може просто зберігати всі букви алфавіт, що ми почнемо с. І тоді ми можемо мати яблуко на індексом 0. Ми можемо мати банан індексу 1, диня в індексі 2, і так далі, і так далі. І таким чином, якщо я хотів, щоб пошук мій хеш-таблиця і доступ яблуко, Я знаю, яблуко починається з Л-і я точно знаю, що вона повинна бути і хеш Таблиця з індексом 0, тому що функції, присвоєні. 

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

Все ясно, як Функція Hash Table працює? Це свого роду просто більш складний масив. Це все, що є. ДОБРЕ. 

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

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

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

І ось, якщо я хотів вставити ягоду, Я знаю, гаразд, я збираюся ввести це через мій хеш-функції. Я збираюся закінчити з індексом 1, а потім я збираюся бути в змозі мати просто менше підмножина цього гігант словник 140,000 слово. І тоді я можу просто подивитися через 1/26, що. 

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

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

А потім ми збираємося повернутися хеш модуль РОЗМІР. Будьте дуже, дуже обережні, тому, теоретично, тут Ваш хеш-значення може бути нескінченним. Це може бути просто піти далі і далі і далі. Це може бути деякі дійсно, дійсно велике значення, а тому, що ваш хеш-таблиці, що Ви створили тільки має 26 індексів, Ви хочете, щоб переконатися, що ваш modulusing, так що ви НЕ run-- це те ж саме що в якості queue-- так що ви не зійшли з Дно Вашої хеш-функції. 

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

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

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

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

АУДИТОРІЯ: Ожина. 

ANDI Пен: Blackberry, ожина. Де ожини йти сюди? Ну, ми насправді не сортуються це ще, але теоретично якби ми хотіли, щоб це в алфавітному порядку, де повинні BlackBerry йти? 

АУДИТОРІЯ: [нерозбірливо] 

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

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

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

ANDI Пен: Так ваш хеш function-- свій хеш-таблицю може бути як великою, як ви хочете. Таким чином, в цьому сенсі, я думав, це було дуже легко, дуже просто для мене, щоб просто зразок основі на літери першого слова. І так є тільки 26 варіантів. Я можу отримати тільки 26 варіантів з 0 до 25, тому що вони можуть тільки почати від А до Z. Але якщо ви хочете додати, мабуть, більше складності або швидше бігти до вашого часу хеш-таблиця, ви абсолютно може зробити всі види речей. Ви можете зробити свій власний Рівняння, яке дає вам більш розсилки в слів, то при пошуку, це буде швидше. 

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

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

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

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

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

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

Хеш таблиця виглядає як таблиця. Дерево виглядає як дерево. Все це є окремим спосіб організації вузлів залежно від того, що ваші потреби. 

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

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

Так от, якщо я збираюся шукати значення 66, я можу почати в 55 років. Це більше, ніж 66 55? Так, це, так що я знаю, що я муз пошук я н право покажчик цього дерева. Я йду до 77. ОК, це менше, ніж 66 або більше, ніж 77? Це менше, ніж, так що ви знаєте, про, який повинен бути зліва вузол. 

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

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

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

АУДИТОРІЯ: Ви хочете, щоб дивитися прямо і подивіться наліво і побачите [нерозбірливо] більше число. 

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

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

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

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

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

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

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

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

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

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

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

І here-- ой, наступний Лист в [нерозбірливо] це А. Таким чином, ми з нетерпінням в цьому масиві. Ми знаходимо восьмий значення, і тоді ми подивіться, ох, агов, це те, що словом, це В-А слово? Це не слова. Ми повинні продовжувати пошуки. 

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

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

ОК здорово. Так B-A-T, а потім Ви збираєтеся шукати. Наступного разу ви збираєтеся щоб бачити, о, агов, це правда, Таким чином, я знаю, що це має бути слово. 

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

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

АУДИТОРІЯ: [нерозбірливо] 

ANDI Пен: Рівне, ми хочете, щоб переконатися, що це ось, що Логічне значення галочка, що це правда. Z-О-О, то ми збираємося перевірити, що так ми точно знаємо, гей, зоопарк є слово. Я збираюся розповісти комп'ютер, що це слово так що, коли комп'ютер перевіряє, він знає, що зоопарк це слово. 

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

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

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

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

Ми збираємося призначити Н, В першу чергу, це нульовий, ми збираємося позбутися. Ми збираємося, щоб мати Н точка вниз. Якщо ми бачимо H, ми хочемо його йти кудись ще. 

Тут, ми можемо перевірити з да. Якщо ми потрапили в H після Т, о, то ми знаємо, що це слово. Логічне збирається повернутися правда. Все ясно, як це сталося? ДОБРЕ. 

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

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

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

І так три блоки програми, які ми дамо вам називаються dictionary.c, dictionary.h і speller.c. А так все робить, dictionary.c те, що ви просили реалізувати. Він завантажує слова. Це заклинання перевіряє їх, і це гарантує, що все правильно вставлений. 

diction.h це просто файл бібліотеки який оголошує всі ці функції. І speller.c, ми збираємося дати вам. Вам не потрібно змінювати кожній із нього. Всі speller.c робить це прийняти, що завантажує його, перевіряє швидкість його, тестує позначку в ніби як швидко ви зможете зробити речі. 

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

І велика частина цієї проблеми є для ви, хлопці, дійсно змінити dictionary.c. Ми збираємося дати вам 140000 слів у словнику. Ми збираємося дати вам текст файл, який має ті слова, і ми хочемо, щоб ви могли організувати їх у хеш-таблиці або синтаксичного дерева тому що, коли ми просимо вас заклинання check-- уявіть собі, якщо ви заклинання перевірки, як Одіссея Гомера. Це як цього величезною, величезною тесту. 

Уявіть собі, якщо кожен Слово, яке ви повинні були шукати через масив 140000 значень. Це буде тривати вічно для вашої машини, щоб бігти. Саме тому ми хочемо, щоб організувати наші дані в більш ефективних структур даних таких як хеш-таблиці або синтаксичного дерева. І тоді ви, хлопці, можете вид коли ви шукати доступ речі більш легко і більш швидко. 

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

Може бути, ви хочете, щоб додати всі букви разом. Може бути, ви хочете, щоб зробити подобається дивні речі до відповідальності ряд листів, все. До вас, хлопці, як ви хочете зробити. Якщо ви хочете зробити хеш-таблицю, якщо ви хочу спробувати синтаксичного дерева, повністю залежить від вас. Я попереджаю вас заздалегідь, що Trie, як правило, трохи складніше тільки тому, що є багато більше покажчики відстежувати. Але повністю до вас, хлопці. Це набагато більш ефективно, в більшості випадків. Ви хочете, щоб дійсно бути в змозі тримати трек всіх ваших покажчиків. Як зробити те ж саме що я тут роблю. Коли ви намагаєтеся вставити значення в хеш-таблицю або видалити, переконайтеся, що ви дійсно відстеження де всі, тому що це дійсно легко, якщо я намагаюся вставити, як слово, Енді. Давайте просто скажемо, що це реальне слово, слово, Енді, в гігантський список зі слів. 

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

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

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

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

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

АУДИТОРІЯ: Чи можемо ми Наведу лише за допомогою [нерозбірливо]? 

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

Крім того, як я сказав, офіс годин сьогодні ввечері і завтра. Специфікація цьому тижні насправді супер просто і супер короткі читати. Я хотів би запропонувати поглянути, просто прочитати повністю від нього. 

І насправді Zamyla проведе вас через кожну з функцій необхідно реалізувати, і тому дуже, дуже ясно, як усі. Просто переконайтеся, що ви відстеження покажчиків. Це дуже складна PSET. 

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

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

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