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

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

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

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

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

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

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

Так чому ми могли б вибрати пов'язаний список по масиву? Що відрізняє їх? Да? 

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

АУДИТОРІЯ: Ви повинні пройти через всі шляхи через зв'язаний список знайти елемент у списку. В масиві, ви можете просто знайти елемент. 

СПІКЕР 1: Право. Так з arrays-- 

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

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

Таким чином, ми маємо тут Визначення вузла. Це як один з елементів наш зв'язаний список, чи не так? Таким чином, ми всі знайомі з нашими ЬурейеЕ структур, які ми розглянули в огляді востаннє. Це була в основному просто створення другий тип даних, які ми могли б використовувати. 

І в цьому випадку, це якась вузол що проведе деякий ціле число в. І тоді те, що друга частина тут? Будь? 

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

СПІКЕР 1: Так. Це покажчик на наступний вузол. Таким чином, це має бути насправді тут. Це покажчик типу вузол до наступної речі. І ось що вони охоплює нашу вузол. Прохолодний. 

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

Гаразд, іди до наступного. Дотримуйтесь його. Містить вона число 9? Ні. Слідуйте наступний. 

Так що ми повинні насправді ітерації через нашу пов'язаного списку. Ми не можемо просто піти прямо туди, де 9. І якщо ви, хлопці, насправді хочете, щоб побачити деякі псевдо-код там. У нас є функція пошуку тут що бере in-- що ж потрібно в? Що ти думаєш? Так легким. Що це? АУДИТОРІЯ: [нерозбірливо]. СПІКЕР 1: ми шукаємо число. Чи не так? І що б це відповідати? Це покажчик на? 

АУДИТОРІЯ: вузол. 

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

І в той час як це не NULL, тоді як у нас ще є речі в нашому списку, перевірте, якщо цей вузол має число ми шукаємо. Повернутися правда. В іншому випадку, відновите його, чи не так? 

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

Так з вставки, ви є три різні способи. Ви можете випереджати, ви можете додати і ви можете вставити в асорті. В цьому випадку, ми збираюся робити препендом. Хто-небудь знає, як ті, три випадки можуть відрізнятися? 

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

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

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

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

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

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

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

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

АУДИТОРІЯ: Чи є у нас в инициализировать новий Далі, щоб NULL-перше, або ми можемо просто инициализировать його очолити? 

СПІКЕР 1: Нова наступний повинен бути NULL, щоб почати тому що ви не знаєте, де він буде. Крім того, це свого роду точно так само як парадигму. Ви можете встановити його рівним NULL просто зробити Переконайтеся, що всі ваші бази покриті перш ніж робити які-небудь перепризначення так, що Ви завжди гарантується, що це буде вказувати на певне значення проти, як цінності сміття. Тому що, так, ми присвоюємо Нова наступний автоматично, але це більше, як хороша практика, щоб ініціалізувати його таким чином, і потім передати. 

Отже, двусвязного списки зараз. Що ми думаємо? Що змінилося з двусвязного списки? 

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

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

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

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

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

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

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

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

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

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

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

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

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

Так у вас є хеш, це тільки Перша буква вашого струнного мінус, який дасть вам деякі число від 0 до 25. І те, що ви хочете зробити, це переконайтеся, що це являє розмір вашої хеш table-- скільки є відра. З багатьма з них хеш-функції, вони збирається повертатися значення, які могли б бути набагато вище числа ковшів що ви насправді є в хеш-таблиці, так що вам потрібно зробити упевнений і мода на них. В іншому випадку, він збирається сказати, ой, вона повинна бути в відрі 5000 але у вас є тільки 30 відра в ваш хеш-таблиці. І, звичайно, ми всі знаємо, що це збирається привести в деяких божевільних помилок. Тому переконайтеся, що мода на Розмір вашого хеш-таблиці. Прохолодний. Так зіткнень. Чи всі добре дотепер? Mmhmm? 

АУДИТОРІЯ: З чого б це повернути таку масивну значення? 

СПІКЕР 1: Залежно від алгоритму що ваш хеш-функція використовує. Деякі з них будуть робити божевільний множення. І це все про отримання рівномірний розподіл, так вони роблять деякі дійсно божевільні речі іноді. Це все. Що-небудь ще? Добре. 

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

Таким чином, питання, що ми робимо в цьому випадку? Що ми робимо? У нас вже є щось там? Чи є у нас просто викинути його? 

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

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

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

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

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

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

АУДИТОРІЯ: Так хеш-таблиці має заздалегідь визначений розмір, як [нерозбірливо] відер? 

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

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

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

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

АУДИТОРІЯ: Ось для пошуку дерева. 

СПІКЕР 1: Так. Це пошукова дерево. Дивовижний. Так що, одне зауважити тут, що ми дивимося на окремих персонажів тут, чи не так? 

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

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

Там, напевно, не Слово, яке MP-то, так в P позиції в цьому Масив, що це просто буде NULL. Це б сказав, добре, там немає ні слова що M подальшим P, ОК? Так що, якщо ми думаємо про неї, кожен один з цих більш дрібних речей насправді один з них великі масиви з A до Z. Так що може бути однією з речей, що це свого роду недоліком спробувати? 

АУДИТОРІЯ: Багато пам'яті. 

СПІКЕР 1: Це тонна пам'яті, чи не так? Кожен з цих блоків тут представляє 26 місця, 26 масив елементів. Так намагається отримати неймовірно простір важким. 

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

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

СПІКЕР 1: Ви як і раніше в них потребує. 

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

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

Таким чином, ми маємо деяку Ьоо що чи представляє слово в дійсності існує в цьому місці, а потім у нас є деякі масив here-- вірніше, це покажчик на Масив складається з 27 символів. А це для, в даному випадку, це 27-- Я впевнений, що всі ви, як, чекати, є 26 літери алфавіту. Чому у нас 27? 

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

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

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

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

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

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

Так ми йдемо до другого і ми бачити, що, так, це не NULL. Ми можемо перейти до наступного масиві. Таким чином, ми перейдемо до цієї наступній масиву тут. 

І ми говоримо: добре, тепер ми чи потрібно це тут. Є нульовим або робить це насправді рухатися вперед? Так насправді рухається вперед в цьому масиві. І ми говоримо: добре, т наша остання буква. Так ми йдемо в т в індексі. А потім ми рухаємося вперед бо є ще один. І це говорять в основному, що, так, він каже, що є слово here-- що якщо ви будете слідувати цим Шлях, ви приїхали при слові, яке ми знаємо, "Летюча миша". Да? 

АУДИТОРІЯ: Це стандартна мати що як індекс 0, а потім є свого роду в 1 або мати в кінці? 

СПІКЕР 1: Ні. Так що, якщо ми оглянемося на наш Декларація тут, це логічний, так що це його власний елемент в вузлі. Так що це не частина масиву. Прохолодний. Так що, коли ми закінчимо наше слово, і ми в цьому масиві, то, що ми хочемо зробити це зробити чек на це слово. І в цьому випадку, він повернеться так. 

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

Так один із способів зробити that-- ой, вибачте, це один. Таким чином, в даному випадку, "зоопарк» не Слово, але це в нашій спроби. Але в цьому, сказати, що ми хочемо його ввести слово "баня", те, що відбувається це ми слідуємо through-- B, A, т. Ми в цьому масиві, і ми йдемо шукати ч. 

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

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

І так на нашому наступному, ми вже говорили, ОК, "зоопарк" вже існує тут. Все, що потрібно зробити, це встановити це дорівнює істинно, що є слово там. Якщо ви слідували все до перед тією точкою, це слово, так що просто встановити його рівним такі. Да? 

АУДИТОРІЯ: Отже робить, що означає, що "ба" це слово також? 

СПІКЕР 1: Ні. Таким чином, в даному випадку, "ба", ми отримаємо тут, ми б сказали, це слово, ні, і це все одно буде не. Добре? Mmhmm? 

АУДИТОРІЯ: Тому, як тільки ви це Слово і ви говорите, да, то це міститиме піти в м? 

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

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

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

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

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

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

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

АУДИТОРІЯ: Почекайте, так у вас є 26 Букви в кожному один? 

СПІКЕР 1: Mmhmm. Так, у вас є 26. У вас є якийсь є слово маркер, а потім у вас є 26 покажчиків в кожному з. І вони point-- 

АУДИТОРІЯ: І кожен 26, вони один у 26? 

СПІКЕР 1: Так. І ось чому, як ви можете см, вона розширюється досить швидко. Добре. Таким чином, ми збираємося, щоб отримати в дерева, які Я відчуваю, що це простіше і, ймовірно, бути миленький відстрочка від спроб є. Будемо сподіватися, що більшість з вас бачили дерево раніше. Не так, як досить ті, за межами, які я не знаю, якщо хто- пішов на відкритому повітрі в останній час. Я пішов збір яблук в ці вихідні, і о, чорт візьми, це було красиво. Я не знав, листя може виглядати, що досить. 

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

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

Все в нижній here-- в дуже, дуже bottom-- вважаються листя. Так що йде разом з все дерево, що, не так? Листя по краях дереві. 

І тоді у нас також є кілька Умови говорити про вузлах зв'язку один до одного. Тому у нас є батько, діти, брати і сестри. Таким чином, в даному випадку, є 3 Батько 5, 6, і 7. Так батько все, що один крок вище, що ви перебуваєте з посиланням на, так що просто як родоводу. Будемо сподіватися, що це все трохи трохи більш зрозумілим, ніж спроб. 

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

АУДИТОРІЯ: Макс два листа. 

СПІКЕР 1: Право. Так макс двох листків. Таким чином, в цей перш, у нас був цей один що було три, але в бінарному дереві, у вас є макс двох дітей на батьків, чи не так? Там інша Цікавою особливістю. Хто-небудь знає, що? Бінарне дерево. 

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

Аудиторія: Пов'язані списки 

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

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

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

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

Отже, більшість з нас, я думаю, що, їдять в їдальні halls-- стільки, скільки ми, можливо, не подобається. Але очевидно, що ви можете думати про стек буквально тільки у вигляді стопки лотків або стопка речей. І, що важливо щоб зрозуміти, що це something-- характеристика що ми називаємо це по-- є ЛІФО. Хто-небудь знає, що це означає? Mmhmm? 

АУДИТОРІЯ: останнім прийшов, першим з. 

СПІКЕР 1: праворуч, останнім прийшов, першим з. Так що, якщо ми знаємо, якщо ми укладка речей до, найпростіше захопити off-- і, можливо, єдине, що ми можемо захопити , Якби наш стек великий enough-- є те, що верхній елемент. Тому, що б було поставити на last-- як ми бачимо тут, що було штовхнув на найбільш recently-- є буде першим річ, яку ми палити, ОК? 

Отже, що ми маємо тут справу другий ЬурейеЕ структура. Це насправді просто хотів Crash Course в структурі даних, так що є багато кинуті на вас, хлопці. Я знаю. Так ще один структура. Ура для структур. 

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

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

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

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

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

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

АУДИТОРІЯ: [нерозбірливо]. СПІКЕР 1: Перевірте розмір? Розмір. Тому ми хочемо, щоб перевірити, якщо наш розмір більше 0, ОК? І якщо це так, то ми хочемо, щоб зменшити наш розмір 0 і повернути це. Чому? 

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

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

Аудиторія: Я думаю, просто в цілому, навіщо ця структура даних бути корисним? 

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

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

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

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

Таким чином, різниця тут в тому, що це FIFO. Так що, якщо ЛІФО востаннє був в першу поза, FIFO є першим прийшов, першим пішов. Так що це, де все, що ви поклали на перший ваш найважливіший. Так що, якщо ви чекали в line-- можу вас Уявіть собі, якщо ви пішли в піти отримати новий iPhone і це був стек, де остання людина в лінії отримав його першим, люди будуть вбивати один одного. 

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

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

АУДИТОРІЯ: Перший. 

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

Це ніби як мені розповідав хлопці, якщо ви відкриваєте файл, Ви повинні перевірити на нуль. З будь-якої з цих стеків і черги, вам потрібно щоб побачити, якщо є вільне місце, тому що ми справу з масивом фіксованого розміру, як ми бачимо, here-- 0, 1 всього до 5. Так, що ми робимо в цьому випадку є перевірка щоб побачити, якщо у нас ще є простір. Чи є наша розмір менше потужності? 

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

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

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

АУДИТОРІЯ: Чи означає це, що ми оголосив би масив, було давно п'ять елементів і Потім ми додаємо на нього? 

СПІКЕР 1: Ні. Таким чином, в даному випадку, це стек. Це буде оголошений у вигляді масиву розміром 6. І в цьому випадку ми є тільки один космічний вліво. 

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

Отже, один thing-- о, це жахливо крейда. Одна річ, щоб розглянути цю справу. Ми просто робимо п'ять. Отже, ми збираємося кажуть голова тут. Це означає 0, 1, 2, 3, 4. 

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

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

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

Так що це буде насправді дати вам спосіб зробити це. Тому що в цьому випадку, то, що? Наша голова на 1, наш розмір 4. Якщо ми мод, що на 5, отримуємо 0, який є, де ми повинні ввести його. 

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

І тепер наша голова вказуючи тут, і ми хочемо додати в іншому. Це, в основному назад від нашої лінії, чи не так? Черги можуть обернути навколо масиву. Це одна з основних відмінностей. Стопки, ви не можете зробити це. 

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

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

Гаразд, так в тому ж way-- Я не знаю, якщо ви, хлопці помітили, але CS це все про візерунками. Речі досить багато же, тільки з крихітними хитрувань. Так само і тут. Нам потрібно перевірити, щоб побачити, якщо ми насправді є щось в нашій черзі, вірно? Скажімо, в порядку, наша розмір більше 0? Прохолодний. 

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

Існує набагато більше бетону Код на study.cs50.net, і я дуже рекомендую рух через нього, якщо у вас є час, навіть якщо це всього лише псевдо-код. І якщо ви, хлопці, хочете поговорити через що зі мною один на один, будь ласка, повідомте мені, знаю. Я був би щасливий. Структури даних, якщо ви берете CS 124, ви будете знаю, що структури даних отримати дуже весело і це тільки початок. 

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

Але це в основному програми Your Crash Course в структурах даних. Я знаю, що це багато. Є що-небудь, що ми хотів би піти знову? Все, що ми хочемо поговорити через? Да? 

АУДИТОРІЯ: Для цього, наприклад, так новий хвіст на 0 над цим? СПІКЕР 1: Так. АУДИТОРІЯ: ОК. Отже переживає, Ви повинні були б 1 плюс 4 ілі-- 

СПІКЕР 1: Отже, ви говорили, коли ми хочемо піти і зробити це знову? АУДИТОРІЯ: Так. Так що, якщо ви були з'ясувати out-- де Ви розрахунку хвіст з в тому, що? 

СПІКЕР 1: Так хвіст був in-- я змінив це. Таким чином, в цьому прикладі тут, це було масив, ми дивимося на, ОК? Тому у нас є речі, в 1, 2, 3, і 4. Тому у нас є наша голова дорівнює 1 на ця точка, і наш розмір дорівнює 4 на даний момент, чи не так? 

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

АУДИТОРІЯ: Що шапка? 

СПІКЕР 1: Ємність. Вибачте. Так що це розмір вашого масиву. Да? 

АУДИТОРІЯ: [нерозбірливо], перш ніж ми повертає елемент? 

СПІКЕР 1: Так ми рухаємося очолити або повернути час? Так що, якщо ми перейдемо один, зменшити розмір? Утримувати. Я безумовно забув ще один. Нічого. Існує не одна формула. Так, ви хотіли б, щоб повернутися глава, а потім повернути його назад. 

АУДИТОРІЯ: ОК, тому що в цей Точка, голова була на 0, а потім ви хочете, щоб повернутися Індекс 0, а потім зробити головний 1? 

СПІКЕР 1: Право. Я думаю, що є ще один Формула ніби як це. У мене немає його на верхній голову, як Я не хочу, щоб дати вам не той. Але я думаю, що це цілком допустимо, щоб скажімо, в порядку, зберігати цю element-- все елемент голова is-- зменшити ваш розмір, переміщати голову над, і повернення все, що елемент. Це абсолютно справедливо. Добре. Я відчуваю, що це не як most-- ви не збирається вийти звідси як, да, я знаю спроб. Я отримав все це. Це добре. Я обіцяю. Але структури даних є чимось, що вона займає багато часу, щоб звикнути. Ймовірно, це один з найскладніших речі, я думаю, що, в курсі. 

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

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

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

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

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

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

АУДИТОРІЯ: Ви говорили, що ми можемо використовувати інші хеш-функцій, що ми не повинні створити хеш-функції? 

СПІКЕР 1: Так, вірно. Так буквально за хеш-функції, Як і Google "хеш функція" і шукати якісь нових і прикольних. Ви не передбачається побудувати Ваші власні хеш-функції. Люди витрачають їх тези про ці речі. 

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

АУДИТОРІЯ: б спробувати бути або ефективним, але тільки складніше, like-- 

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

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

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

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

Я знаю, минулого тижня було все огляд, так ми, можливо, пропустили протягом деякого перегляду від лекції. Будь-які інші питання я можу відповісти? ОК, все в порядку. Ну, ви, хлопці, виходьте 15 хвилин раніше. 

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