>> DAVID мала: Добре.
Ласкаво просимо назад в CS50.
Це початок 8-го тижня.
І нагадати, що проблема набору 5 закінчився з трохи складним завданням.
Так що якщо ви відновити всі ваші навчання стипендіатів і фотографії СА
у файлі card.raw, Ви маєте право Тепер, щоб знайти всі ці люди, і
один щасливий переможець буде ходити додому з одним з цих речей, стрибок руху
пристрій, який можна використовувати для остаточної проектів, наприклад.
>> Це, щороку призводить до трохи моторошний.
І так, що я думав, що зробити, це поділитися з вами деякими з нот, які мають
туди і назад протягом штатний розклад пізно.
Наприклад, тільки вчора ввечері, цитати кінець цитати, від одного з персоналу
Члени "Я просто був студент стукіт в мої двері, щоб зробити знімок зі мною.
Сталкери, скажу я вам. "Почався достатнім описом, а потім ми переїхали
на, годину або трохи пізніше, "У мене було студент чекає мене після розділу
і у нього були всі наші імена і фотографії на кілька аркушів паперу. "Добре.
Так організовано, але не все, що моторошне ще.
>> Потім: "Я був за містом, в ці вихідні, і коли я повернувся, було один в
моє
спальню. "[сміється]
DAVID мала: Наступна цитата з персоналу користувача ", студент прийшов до мене додому на
Сомервілль в 4 ранку сьогодні вранці. "Далі персоналу ", я добрався до готелі в Сан-
Франциско і студент чекав мене в лобі з трьома дзеркалок ".
Тип камери.
"Я навіть не на персонал в цьому семестрі, але студент увірвався в мій будинок це
вранці і записав все це зі склом Google. "І тоді, нарешті,
"Принаймні 12 людей були з нетерпінням чекає мене, коли я вийшов зі свого
лімузина, а потім я
прокинувся. "Добре.
Так що серед фотографій, як ви Нагадаємо, що в цей хлопець тут, хто ви
могли б знати, як Міло банан, який живе з Лорен Карвалью, наші голови
викладанні Fellow.
Міло, Міло, іди сюди хлопчик.
Майло.
Майте на увазі, що він носить Google скла, так що ми покажемо вам все це після.
Так що це Міло, якщо ви хотіли б сфотографуватися з ним пізніше.
Якщо ви хочете, щоб виглядати на аудиторію там.
ОК.
Це хороші кадри.
Ну, Міло банан.
О, не робіть цього.
>> [Сміється]
>> ОК.
Так слово, то про те, що чекає попереду, тому що, як ми починаємо перехід,
На цьому тижні Зокрема, з С в командного рядка середовища і PHP
JavaScript і SQL і HTML і CSS в веб-середовищі, ми будемо
оснащення вам все більше знань для
потенційних остаточного проектів.
З цією метою, звичайно, має Традиція проведення семінарів, які
знаходяться на тангенціальному теми до курсу.
Дуже, пов'язаних з програмуванням і розробки додатків і так далі, але
не обов'язково вивчені власного курсу навчальній програмі.
>> Так що якщо ви могли б бути зацікавлені в одному або кілька семінарів в цьому році,
зареєструватися на cs50.net/seminar.
Є старший семінари на cs50.net/seminars.
І в реєстр до цих пір в цьому році Чудовий веб-додатків з Рубіном на
Рейки, який є альтернативою мови PHP.
Комп'ютерна лінгвістика.
Введення в IOS, яка є платформі, яка використовується для iPhone і
Ipad розвитку.
JavaScript для веб-додатків, ми розглянемо , Але в цьому семінарі, ви перейдете
більш докладно.
>> Стрибок руху, так що ми насправді є наших друзів з Leap руху,
самої компанії, приєднуйтесь до нас.
Завтра, по суті, забезпечити практичний семінар, якщо
представляти інтерес для Вас.
Meteor.js, альтернативний прийом Використання JavaScript не в браузері,
а на сервері.
Node.js, який дуже в тому ж дусі, а також.
Гладкий дизайн Android.
Android Будучи дуже популярним альтернативним Телефон для IOS і Windows
та інших мобільних платформ.
І веб активної оборони.
>> Таким чином, справді, якщо ви хочете взяти участь у цьому, дозвольте мені
зробити це до відома.
Ми дуже раді повідомити, що наші друзі в Leap
Рух, який є запуск -
це пристрій дійсно просто прийшов з кілька місяців тому -
люб'язно пожертвував 30 таких пристроїв класу стільки студентів, якщо
Ви хотіли б запозичити апаратних до кінця семестру і використовувати його для
фактичного кінцевого проекту.
Вони підтримують декілька мов.
Ніхто з них не C, жоден з них PHP, так реалізувати один або декілька з цих семінари
може виявитися інтересів.
І всі вони будуть зняті у тому випадку, якщо ви не в змозі
особисто бути присутнім на засіданні.
Розклад буде оголошено через електронної пошти, як ми зміцнити номерів.
>> І, нарешті, якщо ви йдете в projects.cs.50.net, це веб-сайт
ми підтримуємо щороку, що ми запрошуємо Люди зі спільноти, викладачів
відомств, персоналу, і обидві в межах CS50 до
запропонувати проектні ідеї.
Речі, що представляють інтерес для студентських груп.
Речі, що представляють інтерес для відділів.
Так що свою чергу, є, якщо ви боретеся з невизначеністю щодо того, що ви
самі хотіли б зайнятися.
>> Так останній раз ми ввели можливо складнішу структуру даних, ніж ми
бачили в минулі тижні.
Ми були досить використанні масивів щасливо, як корисно, якщо
спрощені структури даних.
Тоді ми ввели ці, які Звичайно це зв'язкові списки.
І те, що було одним із мотивів для введення цієї структури даних?
Так?
Що це?
>> АУДИТОРІЯ: динамічні розміри.
>> DAVID мала: динамічні розміри.
Так у той час як в масиві, ви повинні знаю його розмір заздалегідь, коли
Ви передати його.
У зв'язаному списку, ви не повинні знати, що.
Ви можете просто Malloc або, більш загально, виділити додатково
вузла, так би мовити, в будь-який час ви вставити додаткові дані.
І не вузол без попередньо сенс.
Це всього лише загальний термін, що описує свого роду контейнер, який ми
використання в нашій структура даних для зберігання деякий пункт інтересу, який цього
випадку, виявляється, цілих чисел.
>> Але завжди є компроміс.
Отже, ми отримуємо динамічні розміри даних структури, але яку ціну ми платимо?
Чим недолік пов'язаних списків?
Так?
>> АУДИТОРІЯ: потрібно більше пам'яті.
>> DAVID мала: вона вимагає більше пам'яті, як саме?
>> АУДИТОРІЯ: [нерозбірливо].
>> DAVID мала: Абсолютно вірно.
Так що тепер ми покажчиків займаючи додаткову пам'ять, що ми раніше
не потрібні, тому що перевага масиву, звичайно, є те, що
все в суміжних, спини щоб спина до спини, яка
дає довільним доступом.
Тому що тільки за допомогою квадратних дужок позначення, або більш технічно покажчик
арифметика, дуже проста того, Ви можете отримати доступ до будь-якого
елементів у постійне час.
І справді, це свого роду натяк на інша ціна, яку ми платимо з
зв'язаний список.
>> Що відбувається з часом роботи щось на зразок пошуку, якщо я хочу
Наведіть приклад і всередині зв'язаного списку?
Що значить мій час роботи став?
Big O н.
Якщо він сортується?
Що робити, якщо структура даних розбираються?
Чи можу я зробити краще, ніж великі О п для пошуку?
Ні, тому що в гіршому випадку він може дуже добре бути відсортовані, але кількість
Ви шукаєте може бути більшим.
Це може бути номер 100, яка може статися, що всі
шляху в кінці.
І тому що ви можете отримати доступ тільки до пов'язаних Список цього здійсненням
шляхи її перший вузол, ти все ще почасти не пощастило.
Ви повинні пройти все це від першого до останнього, щоб знайти
що велике значення, як 100.
Або визначити, якщо це навіть не було.
>> Тому ми не можемо робити те, що алгоритм в даних структуру, яка виглядає наступним?
Ми не можемо зробити бінарний пошук, тому що бінарний пошук вимагає, щоб у нас були
довільним доступом.
Ми могли б просто стрибнути з місця на місці без подальшої
ці хлібні крихти у вигляді всіх цих покажчиків.
>> Тепер, як ми здійснити це?
Ну, якщо ми йдемо на екран при цьому, якщо ми можемо швидко перевизначити ці дані
Структура -
мій почерк не все, що відмінна тут, але ми постараємося.
Так ЬурейеЕ структури, і що я хочу, щоб ця річ тут?
Node.
Так що я буду приступити до нас.
А тепер, те, що повинно бути всередині Структура даних для цього окремо
зв'язаний список?
Скільки полів?
>> Так два.
Один з них досить легко.
Так Int N.
І ми могли б назвати N, що ми хочемо, але вона повинна бути Цілочисельне якщо ми
реалізації зв'язаного списку для цілих чисел.
А тепер що ж другий поля мають бути?
Struct вузла *.
Тому, якщо я структуру вузла *, а потім я можна назвати це також те, що хочу,
але тільки бути ясно, що я буду називати його поруч, як ми робили.
І тоді я закрию фігурні дужки.
>> І тепер, як минулого разу, Я поклав вузол тут.
Але якщо я оголошую це як вузла, чому я турбувати бути таким
детальний тут в оголошенні структури * Наступний вузол, на відміну
просто вузол * наступний?
Так?
>> АУДИТОРІЯ: [нерозбірливо].
>> DAVID мала: Абсолютно вірно.
Саме так.
Оскільки C дійсно приведе вас в прямому і бачить тільки визначення вузла
дорозі сюди, ви не можете посилатися на нього тут.
Таким чином, ми маємо таку переважного Оголошення тут, які за загальним визнанням
більш докладний.
Struct вузол, тобто тепер ми можемо отримати доступ до нього
внутрішньої структури даних.
>> І, як осторонь, тому що це стає трохи більше суб'єктивний зараз,
зірки технічно може піти сюди, він може піти тут, він може
навіть піти в середині.
Ми прийняли, в стилі керівництва для Звичайно, Конвенція здачі
зірки поруч з даними тип, який в даному випадку
буде структура вузла.
Але зрозумійте, в багатьох підручниках і онлайн посилання, ви, можливо, дійсно
побачити його на іншій стороні.
Але так само, як розуміють, що буде насправді працювати, і ви повинні бути просто
послідовним.
>> Добре.
Так, щоб було нашу заяву зі структури вузла.
Потім ми почали робити більше складні речі.
Наприклад, ми вирішили ввести щось на зразок хеш-таблиці.
Так от хеш-таблицю розміром N, індексується від 0 у лівому верхньому куті, щоб н
мінус 1 в лівому нижньому кутку.
Це може бути хеш таблиця на все.
Але які речі ми розмовляли про використання хеш-таблицю для?
Зберігання Що?
>> Імена.
Ми могли б зробити імена, як ми зробили минулого разу.
І справді, ви можете зберігати все що завгодно.
І ми побачимо це знову PHP і JavaScript.
Хеш-таблиці є хорошим роду швейцарських Армійський ніж, що дозволяє зберігати
майже все, що ви хочете всередині , Пов'язуючи його зі значеннями ключів.
Ключі з цінностями.
>> Зараз у цьому простому випадку, наші Ключі просто цифри.
Ми реалізації хеш таблиці у вигляді масиву.
І так ключі 0, 1, 2, і так далі.
І тому ми, як люди, вирішив у минулому тижня, що ви знаєте, що, якщо ми
збираєтеся зберігати імена, давайте просто довільно, але досить розумно,
Припустимо, що Аліса, ім'я, просто бути проіндексовані на 0.
І Боб, ім'я B, будуть індексуватися в 1, і так далі.
Так у нас була відповідність між входами, які є рядками, та хеш
місцях, які є числами.
>> Таким чином, цей процес зазвичай називають хеш-функції, і ви дійсно можете
реалізувати його в коді.
Якби я хотів реалізувати хеш-функції , Який робить саме те, що ми
щойно описав в минулий раз, я міг би оголосити функцію, яка приймає як
вхідного наприклад -
і давайте зробимо це на цьому Екран тут.
Якби я хотів реалізувати хеш Функція, я міг би сказати
щось на зразок цього.
>> Це збирається повернутися Int.
Це буде називатися хеш, і це збирається прийняти в якості аргументу
рядок, або ми можемо бути більш належного зараз, і сказати, символ *, ми будемо називати його с.
І тоді вся ця функція повинна робити, У кінцевому рахунку, це повернути Int.
Тепер, як він це робить, що може Не будь так ясно.
Я збираюся реалізувати це без будь-якого форма перевірки помилок прямо зараз.
Я просто збираюся сліпо сказати, повернутися що є під кронштейн з 0, мінус,
скажімо, в столиці коми.
>> Повністю порушена.
Це не ідеально, тому що Один з них, що, якщо з є недійсним?
Погані речі будуть відбуватися.
Два, що, якщо перша буква в цьому ім'я не букви?
Це не збирається перетворити з добре також.
Це може бути малої літери чи ні лист взагалі.
Так повністю можливості для поліпшення, але це основна ідея.
>> Те, що ми минулого тижня описав усній формі просто процес картування Аліса
0 і Боба 1 можуть бути виражені звичайно, більш formulaically як C
Тут діють.
Зайшов ще хеш, сприймає рядок як введення, а потім якимось чином робить щось
з цього входу для отримання вихідного.
Не в відміну від нашого чорного полі Опис що ми давно зробили.
Я не знаю, як це могло б бути робіт під капотом.
>> Для задачі набір 6, одна з проблем, для вас, щоб вирішити, що
Чи буде ваш хеш-функція може бути?
Що буде всередині цього чорного рамки, і, імовірно, це буде
трохи більш цікаво, ніж це, і безумовно, більш схильні до помилок
перевірок, ніж даний здійснення.
>> Але можуть виникнути проблеми, чи не так?
Якщо є структура даних, таких як це Один з них, що одна з проблем
ви можете зіткнутися з плином часу, як ви вставляєте все більше і більше імен в
хеш-таблиці?
Ви отримуєте зіткнень, чи не так?
Що робити, якщо у вас є Аліса і Аарон, дві людини, імена яких відбулося
почати з?
То виникає питання, де ви покласти другий таку назву?
>> Ну, ви можете наївно просто покласти його де Боб належить, але потім Боб
види різьбових, якщо ви спробуєте вставити його ім'я поруч і
там немає місця для нього.
Так що ви можете покласти Боб де Чарлі, і ви можете собі уявити, це дуже швидко
покладених в трохи безлад.
Щось лінійної зрештою, де ви просто доведеться шукати все це
шукає Алісу або Боба або Аарона або Чарлі.
>> Так замість цього ми запропонували, а не просто лінійно зондування для відкритих просторів
і шльоп імена там, ми запропонував незвичайний підхід.
Хеш-таблиці як і раніше здійснюватиметься з масив індексів, але тип даних
Зараз ці показники були покажчики.
Покажчики на що?
Покажчики на зв'язані списки.
>> Тому нагадаємо, що зв'язаний список дійсно тільки покажчик на вузол і
вузол має наступне поле, і вузол має наступне поле, і так далі.
Так що ви можете думати про це масиві на лівій стороні хеш-таблицю в якості
провідні на зв'язаний список.
Перевага який, якщо ви отримаєте зіткнення між Алісою та Аарон,
що ви будете робити з другої такої людини?
Ви просто прикріпити його або її Наприкінці, або навіть початок
цього зв'язаний список.
>> А насправді, давайте просто локшини через , Що лише на одну секунду.
Де б найкраще підходять?
Якщо я вставляю Аліса і вона закінчується на першого місця, то я намагаюся
вставити ім'я Аарона, і є Очевидно, зіткнення, я повинен покласти
його на початку зв'язаного списку?
Ось на цьому першому місці, або в кінці?
>> АУДИТОРІЯ: [нерозбірливо].
>> DAVID мала: OK.
Я чув починається.
Чому на самому початку?
>> АУДИТОРІЯ: [нерозбірливо].
>> DAVID мала: OK.
Це алфавітний, так що це добре.
Це хороший власності.
Це заощадить мені деякий час потенційно.
Вона не дозволить мені зробити бінарний пошук, але я може принаймні бути в змозі вирватися з
з циклу, якщо я розумію, ну, я до речі Аарон минулому були б у такому
відсортований зв'язаний список.
Я не доведеться витрачати свій час, дивлячись весь шлях до кінця.
Так, що це розумно.
Чому ще може ви хочете вставити зіштовхуються ім'я в
початок списку?
Що це?
>> АУДИТОРІЯ: [нерозбірливо].
>> DAVID мала: Це може зайняти багато часу, щоб отримати в кінці списку.
І справді, більше і більше.
Чим більше імен, що ви вставляєте почати з, тим більше, що
Ланцюг збираєтеся отримати.
Чим довше, що пов'язано Список збираєтеся отримати.
Значить, ви дійсно просто витрачаєте свій час.
Може бути, вам краще підтримання постійний час вставки, Big O 1,
, Завжди поклавши зіштовхуються на ім'я початку зв'язаного списку,
а не турбуватися стільки про сортування.
>> Який найкращий відповідь?
Незрозуміло.
Це частково залежить від того, розподіл, що картина
з імен ви вставляєте.
Це не обов'язково Очевидна відповідь.
Але ось, знову ж таки, Дизайн можливість.
>> Таким чином, ми тоді дивилися на цю річ, яка дійсно інші великі можливості
для р-набір 6.
І зрозумійте, якщо ви ще не зробили, Zamyla пірнає в обидві ці, хеш
таблиць і спроб, більш докладно.
І відео покрокове керівництво вбудовані в р-набір спец.
Це було синтаксичного дерева -
Т-Р-І-Е. І те, що було цікаво це було, що час роботи
пошуку ім'я, як Максвелл в минулий раз, було великим O чого?
Що це?
>> Аудиторії: кількість букв.
>> DAVID мала: Кількість букв.
Я чув про дві речі.
Кількість листів та постійний час.
Так що давайте йти з цим в першу чергу.
Кількість букв.
Ну, ця структура даних, нагадаємо, є як дерево, генеалогічне дерево, кожна з
вузли якого складаються з масивів.
А ті масиви покажчиків на інших подібних вузлів або інших подібних
масивів у дереві.
>> Так що, якщо ми хотіли потім визначити Чи Максвелл знаходиться тут, я міг би піти
у першому масиві, на самому верху дерева, так званий корінь, верхній частині
дерева, а потім слідувати за покажчиком м, Потім покажчик, то х,
W, E, L, L.
А потім, коли я бачу деякі спеціальні символи, позначається тут як трикутник.
У коді ви побачите, що ми пропонуємо Вам реалізований як логічний, просто кажу, що так
чи ні, слово закінчується.
>> Ну, раз ми пішли в M-A-X-W-E-L-L, відчуває, як сім, може бути,
вісім, якщо ми зробимо ще один повз нього, вісім кроки, щоб знайти Максвелла.
Або назвемо його К. Але згадаймо останній час, я стверджував, що, якщо є
реально максимальною довжиною по Словом, як 40 з гаком персонажів,
Максимальна довжина увазі постійне значення.
Так насправді, так, це технічно Big O 8 або 7, або дійсно великий O К. Але
якщо є кінцева кришка на те, що K може бути, це константа.
І так це велика О від 1 на кінці дня.
>> Не в реальному світі.
Не тоді, коли ви насправді почати дивитися ваш годинник, як працює ваша програми.
Це абсолютно буде трохи повільніше, ніж дійсно постійної
Час з одного кроку.
Це буде сім або вісім кроків, але все ж це набагато, набагато краще
, Ніж алгоритм, як Big O п, що залежить від розміру того, що в
структурі даних.
>> Зверніть увагу на вгору тут ми можемо вставити ще мільйон імен у цій
Структура даних, але скільки ще кроків він збирається взяти нас знайти
Максвелл в такому випадку?
Жоден.
Він не впливає.
І на сьогоднішній день, я не думаю, що ми бачили Приклад структури даних, або
Алгоритм, який був повністю не залежить від зовнішніх
поведінки, як, що.
Але це не може бути дивним.
Це не може бути єдиним рішенням для р-набір
>> І це не так.
Це не обов'язково дані структуру ви повинні тяжіти до,
тому що, як хеш-таблиці, компроміс.
Якою ціною ви платите тут?
Пам'яті.
Я маю на увазі, це звіряче обсяг пам'яті.
І ви не можете досить побачити його тут, бо Автор цього знімка
Очевидно, усічений всіх масивів і ми не бачимо багато і
B і C і Q і Y в і Z в цих масивах.
Але вони там.
>> Кожен з цих вузлів цілий ряд від близько 26 або більше байтів, кожен з
яка являє собою літеру.
27 у нашому випадку, так що ми можемо підтримати апострофа в задачі набору.
Так що ця структура даних дійсно, дійсно щільна і широка.
І вже одне це може в кінцевому підсумку уповільнення речі вниз, або принаймні коштувати вам
набагато більше місця.
Але, знову ж, можна зробити порівняння тут.
>> Нагадаємо, якийсь час назад, ми домоглися багато чого більш захоплююче час роботи в сортуванні
коли ми використовуємо сортування злиттям, але ціна ми заплатили, щоб досягти N § п про злиття
Сортувати вимагає, щоб ми витрачаємо більше, що ресурс?
Більше місця.
Ми потребували масив вторинних скопіювати людей у, так само, як
ми зробили тут на сцені.
Отже, ще раз, немає явних переможців, але просто суб'єктивні дизайну
приймати рішення.
>> Добре.
Так як щодо цього?
Будь визнає яких D-Hall?
ОК.
Так три з нас.
Mather будинок.
Так що це для їдальні Мазера.
Б'юся об заклад, всі зали їдальні є стеки лотки, як це.
І це насправді представник в те, що ми
очевидно, вже бачили.
Ми назвали її буквально стек.
І в стек, з точки зору вашого пам'яті комп'ютера, де дані йдуть
в той час як функції при виклику.
>> Наприклад, які речі йдуть в стеку по відношенню до
Розмітка пам'яті ми обговорювали тижнів у минулому?
Що це?
>> АУДИТОРІЯ: виклики функцій.
>> DAVID мала: Мені дуже шкода.
>> АУДИТОРІЯ: виклики функцій.
>> DAVID мала: виклики функцій, але Зокрема, те, що всередині кожного
ці кадри?
Які речі?
Так.
Так що локальні змінні.
У будь-який час ми потребували деякому локальному сховищі, як аргумент, або INT I, або десяткового
Temp, або будь-який інший місцевий змінна, ми були
покласти, що в стек.
І ми називаємо це стек, тому що цього нашарування ідея.
Просто вид матчів з реальністю, Концепція їх.
>> Але виявляється, що стек може також розглядатися як структура даних,
Альтернативою масиві, альтернативні на зв'язаний список.
Щось концептуально більш цікавим що все ще може бути
реалізовані з використанням будь-якої з цих речі, але це інший тип
Дані структури підтримки, насправді, тільки дві операції.
Але ви можете додати на любителя можливостей, ніж ці.
Але ці основи -
штовхати і поп-музики.
>> А ідея зі стеком в тому, що якщо маємо тут, з або без Анненберг
знаючи, піднос з сусіднього будинку з номером 9 на ньому.
Так що просто Int.
І я хочу, щоб натиснути на цю даними Структура, яка в даний час є порожнім.
Розглянемо в нижній частині стопки.
Я б підштовхнути цей номер 9 на стек, а тепер це прямо там.
>> Але найцікавіше про стек тому, що якщо зараз я хочу, щоб підштовхнути
інше значення, як і 17, і я штовхаю цього в стек, я збираюся зробити
тільки інтуїтивно річ, я просто хочу, поставити його саме там, де ми, люди,
був би схильний висловився, на вершині.
Але що цікаво зараз в тому, як я можу отримати в 9?
Ви знаєте, я не без деякого зусилля.
>> Так що цікаво стек в тому, що дизайн,
це структура даних ЛІФО.
Дурний спосіб опису останній увійшов, перший вийшов.
Таким чином, останнє число в в цей час було 17 років.
Так що, якщо я хочу щось від поп стопки, він може бути тільки 17.
Таким чином, є обов'язковий порядок операцій тут, де останній елемент
В повинен бути першим одного з них.
Отже акронім, ЛІФО.
>> Так чому це могло б бути корисним?
Чи є їх контексту, в якому потрібно хочуть структуру даних, як це?
Ну, це, безумовно, корисно всередині комп'ютера.
Так операційних систем чітко використовувати цю вид структури даних для стеків.
Ми також побачимо ту ж ідею коли справа доходить до веб-сторінок.
Так на цьому тижні і на наступному тижні і за її межами, і, як ви приступити до реалізації веб-
сторінок на мові, званому HTML, Ви можете фактично використовувати структуру даних, як
це визначити, чи є сторінка правильно відформатований.
Тому що ми побачимо всі веб-сторінки слід свого роду ієрархію, відступи
який, врешті-решт, бути деревовидної структури під капотом.
Так про це трохи пізніше.
>> Але зараз, давайте пропонувати для моменту, як ми могли б йти про
представляють, що стек?
Дозвольте мені запропонувати, щоб ми здійснили стек з такою код.
Так стек буде мати всередині нього дві речі, масив, званий піддони
просто щоб бути у відповідності з демо.
І кожен з елементів у цьому масиві буде типу Int.
І потужності, мабуть, що?
Тому що я не написав Повне визначення тут.
>> Це, мабуть, максимально розмір масиву.
І це, ймовірно, оголошений як різке визначають у верхній частині файлу, деякі
вид постійної, як випливає з просто капіталізації.
Таким чином, десь потужність визначається в якості максимального розміру.
Тим часом, всередині структури даних відомого як стек там буде
бути цілим числом тільки відомі просто як розмір.
>> Так що, якщо б я мав представити це зараз графічно, давайте припустимо, що це
весь чорний прямокутник представляє свій стек.
Всередині це двома змінними.
Так що я збираюся зробити Перший, як розмір.
А другий я збираюся залучити у вигляді масиву.
>> Але тільки, щоб тримати речі впорядковано, Зазвичай я хотів би звернути масив як
це, але це частково добре якщо ми відповідає дійсності, або
відповідає ментальної моделі.
Отже, дозвольте мені зробити замість масиву вертикально, який знаходиться всього, знову ж таки,
художника виконання.
Насправді не важливо, що це знаходиться під капотом.
І ми будемо говорити, що, за замовчуванням, потужність буде три.
Так що це буде розташування 0, то це буде номером 1, це
буде розташований в 2.
>> Якби я з підкупити стрес м'яч, не так хтось хотів, щоб придумати і запустити
борту тут на мить?
Добре, бачив вашу руку першим.
Піднімайся.
Добре.
Так що я вважаю, що це Стівен.
Піднімайся.
Добре.
>> Але припустимо, що тепер ми перемотати на початковому стан світу, де я
щойно оголосив стека, і це буде потужністю три.
Однак розмір ще не визначений.
Лотки ще не був визначений.
Таким чином, кілька питань у першу чергу.
І дозвольте мені дати вам мікрофон, щоб ви могли активнішу участь в цьому.
>> Так що ж знаходиться усередині розмір в даний момент в строк, якщо все, що я зробив,
заявив стек з одного рядка коду?
>> Стівен: Не так багато.
>> DAVID мала: Добре, не так багато.
Чи знаємо ми, що всередині розмір, ми знаємо, що всередині
цього масиву тут?
>> Стівен: Просто випадковий код, вірно?
Просто -
>> DAVID мала: Так, я збираюся називають це код, але випадкових -
>> Стівен: Речей.
>> DAVID мала: Такі речі, як випадкова
>> Стівен: біт.
>> DAVID мала: біти, так?
Так сміття значення, вірно?
Так перестановки з 0 і 1 в.
Залишки попередніх випадках використання цієї пам'яті.
І ми дійсно не знаємо, які саме значення які, таким чином, ми, як правило залучити їх
у вигляді знаків питання.
>> Тому перше, що ми мабуть збирається хочете зробити тут -
і дозвольте мені дати це поле всередині звідти назва - лотки.
Що ми повинні імовірно ініціалізації розмір, якщо ми хочемо
почати використовувати цей стек?
>> Стівен: Лоток 3 до півдня.
>> DAVID мала: Так, добре.
Щоб було ясно, потужністю оголошений в іншому місці, як три.
І ось що я використовував виділити масиву.
Розмір збирається звернутися до скільки Лотки даний момент в стек.
>> Стівен: Нуль.
>> DAVID мала: Так воно і має дорівнювати нулю.
Так що вперед, і з будь-яким пальцем, намалювати нуля в розмірах.
Добре.
Так що тепер, що всередині цього тут, ми не знаємо.
Це дійсно просто значення сміття.
Так ми змогли залучити знаки питання, але Давайте тримати раду чистими поки
тому що це не має значення що там.
Нам не потрібно для ініціалізації масиву ні до чого, тому що, якщо ми знаємо, що
розмір стека дорівнює нулю, а ми Не слід дивитися на що-небудь в
цей масив в усякому разі у даний момент часу.
>> Тепер припустимо, що я натискаю 9 числа в стек.
Як ми повинні оновити структуру даних всередині цього чорного ящика?
Які цінності потрібно змінити?
>> Стівен: В -
розмір?
>> DAVID мала: OK.
Розмір має стати те, що?
>> Стівен: розмір має бути один.
>> DAVID мала: OK.
Отже розмір повинен стати одним.
Таким чином, ви можете зробити це в кілька способів.
Дозвольте мені дати вам, тепер ваша палець ластик.
Добре.
Тоді зараз пальця кисті.
Добре.
А тепер, що ще має змінитися, очевидно, що в структурі даних?
>> Стівен: Ми збираємося від знизу вгору до 9.
>> DAVID мала: 9.
ОК, добре.
Так до сих пір не має значення, що поставлено на місце розташування одного або двох, тому що вони
сміття значення, але ми не повинні турбуватися шукає там, тому що розмір
говорить нам, що тільки перший елемент насправді законно.
Так що тепер я натискаю на 17 списку.
Що відбувається з цією картиною?
>> Стівен: Так розмір буде йти до двох.
>> DAVID мала: OK.
Ти ластик -
Ой.
Ти ластик.
>> Стівен: Eraser.
>> DAVID мала: Ти кисті.
>> Стівен: Brush.
>> DAVID мала: OK.
А що ще?
>> Стівен: І тоді ми -
>> DAVID мала: Ми висунули 17.
>> Стівен: Ми дотримуємося 17 зверху, а значить -
>> DAVID мала: Добре, добре.
>> Стівен: - помістіть його вниз.
>> DAVID мала: Добре.
Це стає легко.
Я не збираюся, щоб допомогти вам у цей раз.
Натисніть 22.
>> Стівен: Готово.
Стати ластик.
Я стаю кисті.
І тоді я ставлю 22.
>> DAVID мала: 22.
Відмінно.
Так що ще раз.
Я тепер збираюся натиснути стек 26.
>> Стівен: Ох.
О, чорт візьми.
Ви дійсно застало мене зненацька.
>> DAVID мала: Ви не зробили це передбачити?
>> Стівен: Я не бачив цього чекати.
Чи можемо ми повторно Первинна потужність?
>> DAVID мала: Це хороше запитання.
Отже, у нас вид пофарбовані себе в кутку тут.
Там дійсно нічого хорошого за Стівен тому що у нас виділено в цьому масиві
статично, так би мовити, всередині структури даних.
І ми по суті жорстко це буде розміром три.
Так що ми не можемо звільнити його.
>> Ми могли б, якби ми повернулися, ми переглянув лотки бути покажчик, який
потім ми використовуємо Malloc в руки пам'яті.
Тому що, якщо ми отримали від пам'яті через купу Malloc, ми
могли б звільнити його.
Але перед звільненням, ми могли б перерозподілити більший шматок пам'яті,
оновити покажчик, і так далі.
Але на сьогоднішній день, це дійсно що ми можемо зробити.
Натисніть і поп, імовірно, збирався мати, щоб сигналізувати деякі помилки.
>> Так, наприклад, наша реалізація поштовх може повернутися BOOL які
повернутий раніше правда, правда, правда.
Але в четвертий раз, він буде мати повернутися помилковим, наприклад.
Добре.
Дуже добре зроблено.
Поздравляю.
Ви заробили свій стрес м'яч сьогодні.
>> [Оплески]
>> Стівен: Спасибо.
>> DAVID мала: Спасибо.
Отже, це, здається, не так багато з крок вперед, чи не так?
Ми описали цю структуру даних.
Це було переконливим, чи не так?
Операційні системи подобається.
Мабуть в Інтернеті може скористатися цим, та інших програм на місці.
Але те, що дурні обмеження, що ми повернутися до роду тижня дві межі
де ми зафіксували розмір масивів.
>> Таким чином, є справді пара способи, якими ми могли б вирішити цю.
Ми могли динамічно виділяти масив, не жорстка кодування це, як я
зроблено тут, але замість повторного оголошення це, просто щоб було ясно, як
щось на зразок цього.
Лотки Int *, не наважуючись на працездатність ще.
Але коли я заявляю стека в іншому місці в моєму коді, я міг би назвати Malloc,
отримати адресу шматок пам'яті, і я міг призначити
ця адреса лотків.
>> І потім, тому що це просто шматок пам'яті, я міг би продовжувати використовувати квадратні
дужок у звичайному порядку.
Бо знову ж, на зразок цього функціональний еквівалент масиви і
ділянки пам'яті, які приходять назад від Malloc.
Ми можемо ставитися один, як і інші використанням арифметики покажчиків або
квадратних позначення кронштейна.
Так що це один підхід.
>> Але як ще ми можемо реалізувати цю ту ж структуру даних, потенційно?
Вірно?
Я відчуваю, що ми просто вирішили цю проблеми, як тиждень тому.
Те, що було рішення цієї проблеми що Стівен зіткнувся?
Так зв'язані списки, мають рацію.
>> Якщо проблема в тому, що ми фарбуємо себе в кут, виділивши
Заздалегідь занадто мало пам'яті, що ми тоді доведеться якось мати справу з, ну,
Чому б просто не уникнути питання взагалі?
Чому б просто не оголосити лотки бути покажчик на вузол, ERGO зв'язаний список,
і потім виділити нові вузли кожен раз, коли Стівен необхідні, щоб відповідати
число в структуру даних.
>> Таким чином, картина повинна змінитися.
Це не буде так чисто і, як просто, як тільки масив з трьох цілих чисел.
Тепер це буде вказівник на структури, і що структура збирається
є Цілочисельне і наступний покажчик.
Це буде вести через цей покажчик в іншу таку структуру, щоб
іншої такої структури.
Таким чином, картина була б насправді отримати трохи брудніше.
І ми б стрілки пов'язуючи всі разом.
>> Але це нормально, правильно, тому що ми бачили, як це зробити.
І як тільки ви звикнете створюєте щось на зразок пов'язаного
список, який ви повинні будете зробити, якщо Ви вибрати для реалізації хеш-таблицю з
роздільне зв'язування для р-набір 6, ви можете використовувати його в якості будівельного блоку, або
інгредієнта або в подряпин говорять, процедури, то, що ви поклали, ви
створили свій власний шматочок пазла , Який потім можна використовувати повторно.
Так компроміси, але потенційні рішення що ми насправді бачив раніше.
>> Так досить часто, ви бачите це кожен рік або два, коли Apple випустила
щось нове, і всі божевільні люди лінія за межами Apple,
магазин, щоб купити їх граничні оновити на обладнанні.
Я говорю про це, це нормально, тому що Я один з тих людей.
Так які структури даних може представляти цю реальність?
>> Ну, давайте назвемо це черги, лінія.
Так англійці називають це зазвичай Черга в кожному разі, так що це хороше ім'я.
І дві операції, які чергу повинна підтримувати ми будемо називати Enqueue
операції та операції з черги, які схожі за
духу натиснути і поп-музики.
Це просто як би в різних Конвенції, те, що ми називаємо цим.
Але для постановки в чергу щось означає, додати або вставити його в структурі даних.
Щоб з черги означає, щоб видалити його.
Але в той час був стек даних LIFO структурі черги в першій,
перший із структури даних.
>> Якщо ви перший чоловік у черзі, Ви будете першою людиною, щоб отримати
з лінії і купити новий пристрій.
Уявіть собі, як розлад ці люди були б Якщо Apple, замість цього використовували стек, для
Наприклад, для здійснення вибору до вашої нової іграшкою.
Так черг сенсу, звичайно, і ми можемо думати про всякі
додатків, мабуть, для черг, особливо якщо ви хочете справедливості.
Отже, як ми могли б реалізувати ці в якості структури даних?
>> Ну, я пропоную, щоб ми могли потрібно зробити це таким чином.
Так що я збираюся зараз мають номери.
Таким чином, ми будемо тримати його простим і не обов'язково говорити з точки зору лотків.
Просто числа, які народ отримав.
Ємність збирається, знову ж, виправити загальна кількість людей, які можуть бути в
цієї лінії, а три або будь-які інші значення.
>> Але я пропоную, що мені потрібно, щоб відстежувати не тільки розмір
Черга, як багато речей у ньому.
Тому розмір поточного розміру, потужності це максимальний розмір.
Просто ще раз, номенклатура Відповідно до угоди.
Навіщо мені потрібен додатковий десяткового всередині черзі, щоб відстежувати, хто знаходиться в
передній лінії?
Чому я повинен це робити в цьому випадку?
>> Ну, як ця картина збираюся міняти?
Я, ймовірно, може повторно найбільш цієї картини.
Дозвольте мені йти вперед і стерти те, що тут.
Ми дамо цим трохи інше ім'я тут.
Давайте позбутися 17, давайте позбудемося з 9, давайте позбавлятися від 3.
І давайте додамо ще одну річ.
Я вважаю, що мені потрібно стежити за передньої частини списку, який є тільки
буде ІНТАС добре.
І ми збираємося зробити його простим.
Немає пов'язаного списку на даний момент.
>> Ми визнаємо, що ми збираємося натикаються на це обмеження.
Але те, що я хочу бачити на цей раз?
Отже, нехай я йду вперед і першим Людина приходить в лінію, а
це число 9.
У нас є стрес куль.
Чи можу я вкрасти, скажімо, два або три людини?
Один, два, три?
Піднімайся.
Прямо з фронту, тому що ми будемо робити це одним швидким.
>> Кожен з вас тепер буде Вентилятор хлопчика в черзі в Apple.
Ви не будете отримувати Apple Hardware В кінці цього ж.
Добре.
Значить, ти номер 9, ви № 17, № 22.
Ці довільні числа, наприклад, Студент ідентифікатори і ще багато чого.
І через хвилину, давайте почнемо , Щоб почати додавати речей.
І я побіжу борту тут на цей раз.
>> Так що в цьому випадку я ініціалізувати передньої бути -
Я насправді не все одно, що фронт, так як розмір дорівнює нулю.
Так що це може також просто бути знаком питання.
Всі ці знаки питання.
Так що тепер ми почнемо реально побачити деякі люди шикуються в чергу в магазині.
>> Таким чином, якщо число 9, ти перша там в 5 ранку, йти вперед і шикуються в чергу,
або напередодні ввечері.
ОК.
Так що тепер тут 9.
Так 9 знаходиться на початку списку.
Так що я збираюся йти вперед і поновлення Розмір цього поточні дані
структури, щоб не бути більше 0, але рівним 1.
Я збираюся поставити на 9 перед списком.
Дозвольте мені йти вперед і перемикання екрану так що ми можемо бачити минуле з нами тут.
>> А тепер що я хочу поставити на фронт?
Я буду відслідковувати, що початку черги зараз
знаходиться в місці розташування 0.
Бо далі буде?
Ну, припустимо, що тепер я поставити в чергу 17, а.
Так що стрибати в лінію там.
І знову ж, начебто двері Магазин буде тут.
Так що тепер я додав 17.
І хоча ці хлопці блокують екрану, це нормально,
тому що ми бачимо це тут.
Вибачте.
>> АУДИТОРІЯ: Ми можемо рухатися -
>> DAVID мала: Ні, це нормально.
Це величезний там.
Так 17 тепер всередині черги.
Мені потрібно оновлення, яке полів зараз, хоча?
Добре, безумовно розміру.
А як щодо фронту?
ОК, немає.
Передня не повинна змінитися, оскільки На відміну від стека, ми
хочуть зберегти справедливість.
Так що якщо 9 вийшов на перше, ми хочемо, 9 бути першою з лінії
і в магазин.
>> Справді, давайте подивимося, що.
Перед тим, як вставити 22, давайте йти вперед і Dequeue 9.
Як тебе звуть?
>> АУДИТОРІЯ: Джейк.
>> DAVID мала: Джейк збирається бути видалена з черги зараз.
Таким чином, ви добираєтеся, щоб йти в магазин.
І робити вигляд, що в магазині он там.
Так що тепер потрібно, - ДІТ-ДІТ-дит!
Що має статися зараз?
Дизайн рішення.
Так не поганий інстинкт, але - як тебе звати?
>> АУДИТОРІЯ: Девід.
>> DAVID мала: Девід.
Отже, що зробив Давид?
Він намагався виправити сортувати дані Структура і перейти від його розташування
в колишньому місці Джейка.
І це прекрасно, якщо ми готові визнати, що, як
деталь реалізації.
Але спочатку, давайте оновимо дані структури, перш ніж робити це.
Тому що я не подобається ідея всіх люди зрушення в цій лінії.
>> Це не страшно, якщо Девід робить це з один крок, але знову ж, згадайте
, Коли у нас було вісім добровольців по етапі, і ми зробили, як вставки
Сортування, де ми повинні були почати переміщення всіх навколо.
Тобто дороги, чи не так?
Це змушує мене зіщулитися про Big O п, Big O п квадрат знову.
Це не почуття, як ідеальний результат.
>> Так що давайте просто оновлювати це.
Таким чином, розмір черги більше не є 2.
Це тепер просто 1.
Але тепер я можу щось оновити Я не оновлювалася раніше,
перед списком.
Я міг би просто сказати, що розташування 1?
Так що тепер у нас є сміття цінність тут, сміття значення тут, і Девід в
середині цього сміття.
Проте структура даних як і раніше недоторканими.
>> І справді, я навіть не потрібно змінити колишній номер Джейка
9, тому що, хто піклується.
У мене є достатньо інформації, в даний час в розміру, що я знаю, що є одна людина в
цієї черги.
І я знаю, що ця людина знаходиться в місці розташування 1, а не 0.
Я не розраховую.
Таким чином, 1, а також.
Так що дані структури все ще добре.
>> Ну, а що буде далі?
Давайте Enqueue -
Як тебе звуть?
>> АУДИТОРІЯ: Каллен.
>> DAVID мала: Каллен.
Давайте постановки в чергу Каллен, і 22 в даний час в черзі.
Так що тепер повинен змінити тут?
Передня не збирається змінити, це очевидно.
Розмір буде змінюватися, щоб бути 2 знову.
І 22 закінчується тут, 9 і раніше присутня, але це ефективно
сміття значення зараз.
Це просто пережиток минулого Джейком.
>> Так що тепер, що станеться, якщо Я з черги Девід?
Одна остання операція, Dequeue Давида.
Ми могли б перейти, але я пропоную давайте зробити так мало роботи, скільки можливо.
Тепер моя структура даних йде Резервне в розмірі від 2 до 1.
Але попереду черги тепер стає 2.
Мені не потрібно, щоб змінити це число Поки ще немає, тому що вони
просто значення сміття.
>> Але тепер те, що відбувається?
Припустимо, що я себе поставити в чергу, 26?
Я відчуваю, що я належу тут.
Так що я бути встановлені в чергу.
Так що я як би до нас приєднатися.
І навіть якщо ви не зовсім візуально оцінити це на сцені,
тому що у нас багато місця, я повинен Не стояти тут, то чому?
>> Зали: Ви перебуваєте за межами поля.
>> DAVID мала: Вірно.
Я поза законом.
Я проіндексовано за рамках даного масиву.
Я дійсно повинен бути в одному з три можливих місцях.
Отже, де найбільш природним піти?
Я пропоную позикових коштів тижня один трюк.
Оператор Mod, у відсотках.
Тому що я стояв на технічно Розміщення 3, але у мене 3 мод потужності,
SO 3, знак відсотка, 3 -
ємність 3.
Що це?
Який залишок при Ви ділите 3 на 3?
0.
>> Так що це ставить мене були Джейк був, який насправді добре.
Так що в даний час здійснення цієї речі збирається
бути трохи головного болю.
Це дійсно просто один рядок головного болю, коду.
Але принаймні тепер є сміття Значення тут, але є два
законних цілими тут.
І я стверджую, що зараз ми зробили саме те, що нам потрібно зробити, так довго, як
змінити те, що ми Джейка Значення мало бути 26.
>> Тепер у нас є достатньо інформації як і раніше для підтримки цілісності
цієї структури даних.
Ми все ще почасти не пощастило, коли ми вставити чотири або більш загальної
елементи, але я можу принаймні зробити досить ефективне використання цієї константи
час, насправді.
Я не доведеться турбуватися про перенесення Кожна людина, як нахил Давида була.
>> Будь-які питання по стеки, або ця черга?
>> Зали: причина, чому Вам потрібен розмір, щоб ви знали
Де є людина?
>> DAVID мала: Абсолютно вірно.
Мені потрібно знати розмір масиву тому що мені потрібно точно знати, як
багато з цих значень є законними, і так, що я можу знайти, де поставити
наступна людина.
Саме так.
Розмір -
Насправді, ми не оновлювали це поки що.
Я додав себе в 26.
Розмір в даний час, а не один, а два.
Так що тепер це дійсно допомагає мені знайти чолі списку, яка не дорівнює 0, чи не
1, але 2.
Перед списком насправді число 22.
Тому що він прийшов першим, тому він повинен пустять у магазині переді мною,
хоча візуально я стою ближче до магазину.
>> Все в порядку?
Оплесків для цих хлопців , І ми повідомимо їх звідти.
>> [Оплески]
>> DAVID мала: Я міг дозволити Ви тримаєте лоток.
Ми могли бачити, що відбувається, якщо Ви хочете, але може і ні.
Добре.
І що тепер що нам залишається?
Ну, дозвольте мені запропонувати, що є Кілька інші структури даних, ми могли
почати додавати до нашого набір інструментів, який буде дійсно може бути дуже, дуже актуальна, як
ми поринемо в матеріал Інтернету.
Що знову ж таки, є якийсь зв'язок до дерев у вигляді
те, що називається DOM, документ об'єктної моделі.
Але ми побачимо більше що незабаром.
>> Дозвольте мені запропонувати, що ми definitionally дерево викликів тепер те, що ви знаєте, як
більше сімейного дерева, де ви є предком
Коріння дерева.
Патріархальної або матріархат в самій вершині дерева.
Без їх подружжя, в цьому випадку.
Але тепер ми маємо те, що ми будемо називати дітей, які є вузлами, які висять
за лівим дитиною або право дитини, стрілки, як показано тут.
>> Іншими словами, в структурі даних дерева в комп'ютер, дерево має нульову
або більше вузлів.
Якщо у нього є хоча б один вузол, Це називається коренем.
Це речі, що візуально ми звертаємо на самому верху.
І цей вузол, як і будь-який інший вузол, може мати нуль, один або два, або три,
або скільки дітей Структура даних підтримує.
У цьому випадку, корінь, зберігання Значення одного, має двох дітей, 2 і 3,
тому ми зазвичай називаємо 2 лівих дитини і 3 правом дитини.
>> А потім, коли ми приступимо до 5, 6, і 7, 6 можна назвати середнім дитиною.
Якщо у вас є четверо дітей, це збиває з пантелику.
Таким чином, ми припинити використання такого поєднань в усній формі.
Але це дійсно тільки генеалогічне дерево.
І листя тут вузли, які самі по собі не мають дітей.
Вони висять від нижньої частини дерева.
>> Так як ми можемо реалізувати дерево, має тільки дві дітям максимально?
Ми назвемо це бінарне дерево.
Бі знову означає два, в цьому випадку, як і з бінарними.
І тому він може мати нуль, один, або двох дітей максимально.
>> Я пропоную, щоб ми здійснили вузла для цієї структури з Int N,
а потім два покажчика, одна називається залишили, одна називається правом.
Але це просто приємно довільні угоди.
І те, що приємно зараз, особливо, якщо ви вид боровся концептуально
рекурсії, або думав, що це не було Рішення дійсно ні до чого,
Особливо якщо б ви могли запустити з пам'яті.
Тепер, коли ми говоримо про дані структури і алгоритми, які дозволяють
нам, щоб пройти їх і маніпулювати ними, Виявляється, що рекурсія повертається в
набагато більш переконливою якщо не красивим способом.
>> Так що я пропоную, є реалізація з функції пошуку.
Враховуючи два входи -
тому думайте про це як чорний ящик.
Враховуючи два входи, N, ціле і покажчик на дереві, покажчик на
вузла, або дійсно корінь дерева, я стверджують, що ця функція може повертати
істинним або хибним, що значення N всередині цього дерева.
>> Що всередині цього чорного ящика?
Ну, чотири гілки.
Спочатку просто перевіряє.
Якщо дерево є порожнім, просто повернути помилкове.
Якщо ні вузла, немає N, немає числа, якраз повертає помилкове.
Якщо хоч, N, значення, яке ви шукаєте для, менше дерева стрілку N, і
просто щоб було ясно, що це означає, коли Я пишу дерева, а потім стрілка
позначення, п?
Саме так.
Це означає, що разименованія Покажчик називається деревом.
Відправляйтеся туди, а потім потрапити всередину, що вузла і отримати його полі, назване N.
А потім порівняти фактичні N, яка була перейшла в пошук проти нього.
>> Таким чином, якщо N менше, значення N у вузлі дерева сам, ну,
Що це означає?
Це нічого не значить на перший погляд.
Вірно?
Як і коли ви є масив Значення, які Ви хотіли б застосувати двійковий
шукати як форма розриву і володарюй.
Але те, що зробив припущення ми повинні зробити для бінарного пошуку працює взагалі
в телефонній книзі і більш ранні приклади?
>> Як бути відсортовані.
Так що давайте уточнити визначення дерева Тут, щоб не бути просто дерево, яке може
мати будь-яку кількість дітей.
Не тільки бінарне дерево, яке може мати 0, 1 або 2 максимально.
Але, як бінарне дерево пошуку або BST, , Яка є просто химерний спосіб сказати
бінарне дерево так, що кожен вузла лівий дитини, якщо він присутній,
менш вузла.
І право кожного вузла дитиною, якщо вони присутні, більше
крім самого вузла.
>> Отже, іншими словами, якщо ви повинні були зробити дерева з всі цифри
ретельно збалансовані, як це так, що якщо у вас є 55 в якості кореневого, 33 може піти
ліворуч від нього, тому що це менше, ніж 55.
77 може піти у своєму праві, тому що це більше, ніж 55.
Але тепер помітили, те ж визначення, це рекурсивне визначення в усній формі,
повинен направити заявку на 33.
33 в лівій дитина повинна бути менше його, права дитини і в 33, 44, повинні бути
більше, ніж він.
>> Так що це бінарне дерево пошуку, а Я пропоную, використовуючи трохи
рекурсію, зараз ми можемо знайти N.
Таким чином, якщо N менше, ніж значення N це поточного вузла, я піду
вперед і вибивати з рук, так би мовити, і просто повертаючи те, що відповідь на це питання з
пошук п від лівого дерева дитини.
Ще раз зверніть увагу, ця функція просто очікує вузла зірки,
покажчик на вузол.
Так що, звичайно, я просто можу зробити дерево стрілка вліво, що призводить
мені на інший вузол.
Але що це за вузол?
>> Ну, відповідно до цієї декларацією, Зліва тільки покажчик, так що тільки
означає, що я переходячи до функції пошуку різних покажчиків, а саме
один, який представляє моя ліва дитини дерева.
Таким чином, в цьому випадку покажчик 33, якщо це наш приклад введення Тим часом, якщо
п більше значення п при поточного вузла в дереві, то я
збираюся йти вперед і вибивати з рук в інші Напрямок та просто сказати, я не
знаю, якщо це значення п в дереві, але я знаю, якщо це так, це на мою
Права гілка, так би мовити.
Отже, дозвольте мені рекурсивно шукати, проходить N раз, але переходить у
покажчик на моєму правому дитини.
>> Іншими словами, якщо я в даний час перебуваю на 55 і я шукаю 99, я знаю, що 99
більше 55, так само, як я розірвав тижнів телефонну книгу тому, і ми
пішов прямо, як і ми збираюся йти прямо тут.
І я не знаю, чи буде це на моє право дитини, а це не так, 77 є, але
Я знаю, що в цьому напрямку.
Тому я називаю пошуку праворуч від мене дитину, 77, і нехай пошук фігури з
там, якщо 99 в цьому довільному Прикладом є насправді.
>> В іншому випадку, те, що останній випадок?
Якщо дерево є недійсним один випадок.
Якщо п менше поточного вузла значення ще один випадок.
Якщо п більше, ніж поточний Значення вузла третій випадок.
Що четвертому і останньому випадку?
Я думаю, що ми з випадків, чи не так?
Повинно бути, п о поточного вузла, що я на.
>> Так що, якщо Я шукаю 55 на даний момент в цій історії, що філія
Дерево буде повернута істина.
Так що тут цікаво те, що ми насправді, на відміну від минулих тижнів, ми якось
з двох випадків є підстави.
І вони не повинні все буде на самому верху.
Верхня частина базового варіанту, тому що якщо Дерево є недійсним, немає нічого спільного.
Просто повернути жорстко задані Значення хибним.
>> Нижня гілка роду за замовчуванням, згідно з яким, якщо ми перевірили для
нульовим, ми перевірили, якщо вона має бути залишилося, але воно не повинно бути, у нас
перевіряється, якщо це має бути правильно, але це не повинно бути, очевидно, що воно має бути
там, де ми є.
Це базовий варіант.
Таким чином, є два рекурсивних випадків затиснута там в середині.
Але я міг би написати це в будь-якому порядку.
Я просто думав, що це як би відчував, природні спочатку перевірити на можливу помилку,
потім перевірити наліво, потім перевірити прямо, то Припустимо, що ви перебуваєте у вузлі
насправді ви шукаєте.
>> Так чому це могло б бути корисним?
Ось і виходить -
і дозвольте мені перейти до тизер тут, це в Мережі.
Ми збираємося, щоб почати використовувати не мова програмування на перший, але
мова розмітки.
Мова розмітки є одним це близькі за духом до програмування
мови, але це не дає вам Можливість виразити себе логічно.
Це тільки дає вам можливість виразити себе структурно.
>> Де Ви хочете, щоб покласти щось на сторінці, веб-сторінка?
Який колір ви хочете це зробити?
Який розмір шрифту ви хочете це зробити?
Які слова ви насправді хочете на веб-сторінку?
Так що це мова розмітки.
Але тоді ми дуже швидко ввести JavaScript, який є повноцінним
мови програмування.
Дуже схожий за зовнішнім виглядом синтаксично С, але це буде мати деякі
добре, більш потужна, більш зручних для користувача характеристик.
>> І одним з розчарувань у це точка в семестр, що ми будемо
скоро в реалізації спеллер набагато менше рядків коду з використанням інших мовах
C ніж сама дозволяє, але для розуму ми скоро зрозуміли.
Це буде перший такий веб-сторінки.
Він буде повністю в захват, Перше ми робимо.
Він просто скаже: привіт світ.
Але якщо ви ніколи не бачили його раніше, це HTML,
Мова розмітки гіпертексту.
>> Якщо ви йдете в певний пункт меню в Найбільш будь-якому браузері, на будь-який веб-сторінці
Інтернет, ви можете побачити HTML що деякі люди написали
створити цю веб-сторінку.
І це, ймовірно, виглядає не так коротка або ж акуратно, як цей.
Але це буде за тією ж схемою цих відкриті дужки і коса риска і
Листи та потенційно чисел.
>> Я думав, що дам вам тизер того, що ви будете в змозі зробити
після прийому CS50.
Пустіть мене до cs.harvard.edu / грабувати, Домашня сторінка нашої власної Роб Боудена.
Він зробив це для нас.
Таким чином, ви скоро будете в змозі зробити це.
А також, що ви чули Сьогодні вранці -
те, що ви чули сьогодні вранці -
>> [HAMSTER Танцювальна музика]
>> - Ви будете мати можливість зробити це.
Що чекає нас у середу.
Ми будемо бачити вас тоді.
>> [HAMSTER Танцювальна музика]
DAVID Малай: Наступного CS50 -