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

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

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

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

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

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

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

АУДИТОРІЯ: Якщо ви використовуєте цей вхід в рядок це більше, ніж 49 символів. 

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

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

Так що, евристика повинно бути ніяких Час у вас є фіксовану довжину, у вас є щоб переконатися, що ви перевіряєте довжину з те, що ви намагаєтеся читати в неї. 

АУДИТОРІЯ: Таким чином, щоб вирішити, що, ви могли б мали про перевірки насправді довжина більше чи менше? 

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

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

Так питання 2 запитує, припустимо, що версія 3 складається і виконується. Чому ж це програма сегментації? Так що це один насправді те ж саме відповісти, хоча це виглядає трохи більш незвичайним. Ми використовуємо Танос, який відчуває себе подібно ми даємо собі більше можливостей. А потім ми звільняючи, що пам'яті в кінці. Він як і раніше всього 50 байт пам'яті. Таким чином, ми могли б все ще намагаюся читати в 51, 52, 1000 байт. Це збирається до випадання для точно так само причина. 

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

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

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

ROB BOWDEN: Так проблема 4. Це те місце, де ви повинні були заповнити в число байтів з усіх ці різні типи, використовувані. Так перше, що ми бачимо. Припустимо, 32-розрядну архітектуру, як цей CS50 приладу. Таким чином, одна з основних речей, про 32-бітові архітектури, який говорить нам, точно, як великий покажчик збирається знаходитися в архітектурі. 

Так відразу, ми знаємо, що будь покажчик тип 32 біта або 4 байти. Так, дивлячись на цю таблицю, вузол * є покажчиком. Це буде 4 байта. Структура, вузол *, ось буквально ідентичний вузла зірки. І так, що це буде 4 байта. Рядок, так що не схожий покажчик поки немає, але ЬурейеЕ, рядок просто символ *, який є тип покажчика. Так що це буде 4 байта. 

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

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

Зали: це був 64-розрядний архітектура, хотів би, щоб подвоїти всі з них? 

ROB BOWDEN: Це не так подвоїти всі з них. Так 64-розрядна архітектура, це, знову ж, зміни, які фундаментальна річ, яка Покажчик Зараз 64 біта. Так. Так покажчик становить 8 байт. Таким чином, ці, що були 4 байта будуть 8 байт. Студент, який був два покажчика, добре, тепер він збирається бути 8 байт, 8 байт. Це збирається зробити 16 байт. 

Але вузол ще 4 байта. Так цей покажчик буде щоб бути 8 байтів. Це 4 байта. Так вузол буде тільки бути 12 байт. Будь-які інші питання про те, що один? Таким чином, наступний, це коди стану HTTP. І у вас було б описати обставини , При яких вони могли б Вам повернуті. одна проблема, що я чув, деякі студенти є те, що вони спробували зробити Помилки бути на кінці клієнта. Тому, коли ми намагаємося зробити запит на сервер, щось іде неправильно з нашого боку. Але в цілому, ці коди повертається на сервері. Тому ми хочемо, щоб з'ясувати, що відбувається неправильно або прямо на сервері, викликає ці речі повинні бути повернені. Так чому могли б через сервер повертає Код стану 200? Будь-які думки? 

Так. Так щось успішно запит пройшов. І вони змогли повернутися все, що ви просили. Так що все було прекрасно. Що про 302 знайдено? Так. 

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

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

АУДИТОРІЯ: Мені дуже шкода. Знайдено означає, що вони знайшли його. Вибачте. 

ROB BOWDEN: Так 302 знайдено. Сервер здатний знайти що ви хотіли. 

АУДИТОРІЯ: Але це не відображаючи його? 

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

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

ROB BOWDEN: ОК. Так що про 403 заборонено? 

Зали: Я думаю, що це те, що сервер в основному говорить, що клієнт не може отримати доступ до домашньої сторінці. 

ROB BOWDEN: Так що, так. Ну, типова відповідь ми були очікуючи щось подібне, файли НЕ chmodded відповідним чином. Це, ймовірно, за яких обставин ви бачили їх. Але є причина, що клієнт може бути винні в цьому. Там насправді інший код стану - 401. Так що це дуже схоже. 

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

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

ROB BOWDEN: Тоді 404 не найден. Так. Так на відміну від 302, де це не було точно де ви питаєте, але він знає, що ви хочете, це, він просто повинен ніяка ідея, що ви хочете. І ви не з проханням щось діє. 418 Я чайник, а потім 500 внутрішній сервер. Так чому може ти це взяв? 

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

Девід Дж. Малан: Ми дійсно бачили сегментації серед відповідей в декількох людей. І технічно, це може статися. Але це було б PHP, програма написані іншими людьми, насправді segfaulted, які тільки якщо ці люди облажався і написав помилка в програмному коді в їх перекладач would Сам PHP сегментації. Тому, навіть якщо 500 подібний сегментації в дусі, це майже завжди результатом питання конфігураційного файлу з вашого веб-сервера, або, як сказав Роб, помилка синтаксису, як і ви не закривав цитату. Або ви втратили крапку з комою десь. 

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

ROB BOWDEN: Так. 

АУДИТОРІЯ: о, якби помилка ще придумати? 

ROB BOWDEN: Таким чином, ви б не отримали ця помилка, тому що всі з точки зору веб-сервера було абсолютно прекрасно. Але ви просили index.html. Ви просили shuttle.js і service.js. І це було в змозі успішно повернутися Вам всім з тих речей - 200. ОК. І тільки коли ваш браузер намагався інтерпретувати код JavaScript, що Це як, почекайте, це не діє помилка JavaScript. Будь-які інші питання? Добре. 

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

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

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

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

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

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

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

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

АУДИТОРІЯ: У стрілкою покажчика [Нерозбірливості] дорівнює нуль, чи означає це справу зі списком, бо список порожній? 

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

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

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

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

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

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

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

Попередній. Це поруч. Так що я просто malloced мою записку, перевірив для нуль, призначений 34 у вузол. Попередній отримує нуль. Так, що дає мені це. Наступна отримує список. Так список це. Так що це те ж саме зараз, як малювання це стрілка, так що вони вказують на один в те ж саме. А потім я перевіряю, якщо список НЕ дорівнює NULL. І це не цього разу. Тоді я збираюся зробити список попередня отримує покажчик. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Так що, що рядок коду має тільки зроблено трохи про це. І тепер, це виглядає як крок у правильному напрямку. Ми суттєво хочете, щоб відрізати 2 від'їзді середини 1 і 3. Так що має сенс, що ми хочемо маршрут цей покажчик навколо нього. Так що це наступна рядок перевірки, якщо покажчик наступний не є нульовим, є дійсно хтось праворуч від 2, це означає, що ми також повинні зробити трохи СНиП тут. 

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

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

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

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

АУДИТОРІЯ: Так список схожий на голову в попередніх прикладах. 

Девід Дж. Малан: Точно, точно. Просто інше ім'я для глобальна змінна. У всьому світі і що? 

ROB BOWDEN: ОК. Так що це те місце, де ви повинен був написати цей пункт. Деякі люди писали есе на це питання. Але потрібно просто використовувати ці шість членів щоб описати, що відбувається, коли Ви спробуйте зв'язатися facebook.com. Так що я буду просто говорити через процес використовуючи всі ці терміни. Так у нашому браузері, ми набираємо facebook.com та натисніть Enter. Таким чином, наш браузер збирається побудувати HTTP просити, щоб він збирається відправити через деякий процесу в Facebook для Facebook, щоб відповісти на нас з HTML його сторінці. 

Так що це процес, при який запит HTTP насправді потрапляє в Facebook? Отже, спочатку ми повинні перевести Facebook.com. Так що просто дано ім'я Facebook.com, де насправді просити HTTP потрібно йти? Так що ми повинні перевести Facebook.com до IP адресою, яка однозначно ідентифікує, що машина у нас насправді хочете відправити запит на. Ваш ноутбук має IP-адресу. Все, що підключені до Інтернету має IP-адресу. 

Так DNS, Domain Name System, тобто що відбувається в обігу переклад від facebook.com до IP-адреси, ви насправді хочете зв'язатися. Таким чином, ми зв'язатися з DNS-серверів і скажемо, що facebook.com? Це говорить, про, це IP-адреса 190,212 щось, щось, щось. Добре. Тепер, я знаю, що машина Я хочу зв'язатися. 

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

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

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

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

Якби вони хотіли, вони могли встановити його так, це показує, як на порту 7000. А потім в веб-браузері, я міг вручну ввести Facebook.com: 7000 в відправити запит на порт 7000 веб-сервер Facebook. 

Девід Дж. Малан: І в цьому випадку, навіть хоча ми не вимагали, щоб люди говорю про це, в даному випадку, те, що порт буде запит насправді піти? Спробуйте ще раз. Саме так. Не потребую цьому, але тонкість що не там ні останнім. 

ROB BOWDEN: Так HTTPS, так як це слухати спеціально для зашифрований, це на порту 4430. 

Аудиторія: та електронні листи 25, чи не так? 

Девід Дж. Малан: Вихідний трафік електронні листи, 25, так. 

ROB BOWDEN: я навіть не знаю, що більшість з - Всі нижні мають тенденцію бути зарезервовані для речей. Я думаю, що все під 1024 зарезервований. 

АУДИТОРІЯ: Чому ви говорите, 3 був неправильний номер? 

ROB BOWDEN: Тому що в IP-адресу, є чотири угруповання цифр. І вони від 0 до 255. Так 192.168.2.1 є загальним Локальний IP-адреса мережі. Зверніть увагу, всі ті, менше, ніж 255. Тому, коли я почав з 300, що не міг мати був одним з чисел. 

Девід Дж. Малан: Але це нерозумно кліп від - це було CSI, де вони повинні були число, яке було занадто великим для IP-адреси. 

ROB BOWDEN: Всі питання з цього приводу? Наступний, так повна зміна тема, але у нас є це PHP масив для будинки в чотириядерних. І у нас є невпорядкований список. І ми хочемо, щоб роздрукувати кожного елементу списку просто, що містить ім'я будинок. Тому у нас є цикл по кожному елементу. Так що пам'ятайте, синтаксис Еогеасп Масив як елемента масиву. Так через кожен ітерації циклу, будинок збирається взяти на одному з значення всередині масиву. 

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

І тоді ми також сказав в питанні Сам, не забудьте закрити невпорядкований список тегів. Так що ми повинні вийти з режиму PHP для того, щоб зробити це. Або ми могли би вторить закрити невпорядкований список тег. 

Девід Дж. Малан: Також добре тут буде були використовувати стару школу для петля з $ I = 0 0 і використовуючи розраховує на з'ясувати довжину променя. Повністю теж добре, тільки трохи wordier. 

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

Девід Дж. Малан: Абсолютно вірно. Так, саме так. 

ROB BOWDEN: Що-небудь ще? 

Девід Дж. Малан: Добре. Компроміси. Так з'явилися грона відповідей можливо для кожного з них. Ми дійсно просто шукаєте щось привабливим для перевернутої і і зворотна сторона. І число 16 запитав, перевірка користувачі ' вхід з боку клієнта, так як з JavaScript, замість стороні сервера, а з PHP. Так в чому ж потенціал зростання робити на стороні клієнта? 

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

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

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

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

АУДИТОРІЯ: Так що, якщо ми просто сказав менш безпечним - 

Девід Дж. Малан: [сміється] Тьху. Ті, завжди важче ті, для розгляду. 

ROB BOWDEN: Це було б були прийняті. 

Девід Дж. Малан: Що? 

ROB BOWDEN: Я створив цю проблему. Це була б прийнята. 

Девід Дж. Малан: Так. 

АУДИТОРІЯ: Круто. 

ROB BOWDEN: Але ми не приймали для першого - добре, що ми шукали це щось на зразок вас не повинні зв'язку з сервером. Ми не приймаємо тільки швидше. 

АУДИТОРІЯ: А як щодо не перевантажити сторінку? 

ROB BOWDEN: Так. Це було прийнято відповідати. 

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

АУДИТОРІЯ: Це лінійна. Пошук на зв'язаний список линейна замість того, що ви входите в 

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

АУДИТОРІЯ: Пам'ять неефективно? 

Девід Дж. Малан: Так. Ну, я б не став обов'язково сказати неефективним. Але це обійдеться вам більше пам'яті, тому що вам потрібно 32 біта за кожен вузол для додаткового покажчика, по крайней мере, для односпрямованого списку. Тепер, якщо ви тільки спосіб зберігання цілочисельних і Ви додаєте покажчик, це насправді вид нетривіально. Це подвоєння обсягу пам'яті. Але насправді, якщо ви зберігаєте зв'язаний список структур, які могли б 8 байт, 16 байт, ще більш Крім цього, може бути, це менше маргінальної вартості. Але це вартість, тим не менш. Так що або з тих б уже було прекрасно, як недоліки. 

18. Використання PHP замість C написати Програма командного рядка. Так от, це часто швидше використати мову, як PHP або Ruby, або Python. Ви просто швидко відкрити до текстовому редакторі. У вас є набагато більше функцій доступні для вас. PHP має раковину функцій, тоді як в C, ви є дуже і дуже мало. Насправді, хлопці знають на власному гіркому досвіді що у вас немає хеш-таблиці. Ви не зв'язали списки. Якщо ви хочете, щоб ті, ви повинні реалізувати їх самостійно. 

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

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

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

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

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

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

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

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

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

Девід Дж. Малан: Будинок де будинок будинок. Я, напевно, єдиний, який розуміє, от як, що, як передбачається, вимовлятися, правильно? 

ROB BOWDEN: у мене не було насправді не знаю,. 

Девід Дж. Малан: Він зробив сенс у моїй голові. 

ROB BOWDEN: Я роблю це. ОК. Так що це те місце, де ви повинні були звернути діаграма схожа на вас, можливо, бачили на минулих іспитів. Так що давайте просто подивимося на це. Так що з HTML вузла, у нас є два діти, голова і тіло. Таким чином, ми розширитися - голову і тіло. Головка має тег заголовка. Тому у нас є назва. 

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

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

Девід Дж. Малан: І варто зауважити,, хоча ми не будемо зупинятися на них деталі в часу ми проводимо на JavaScript, що порядок робить, в Справа в тому, незалежно від того, в технічному плані. Так що, якщо керівник йде перед органом в HTML, то він повинен з'явитися в зліва від тіла у фактичному DOM. Що його, загалом, просто FYI, те, що називається порядок документ, де це має значення. І якщо ви були реалізації парсер, програма, яка читає HTML в будівлі вгору по дереву в пам'яті, якщо чесно, ось інтуїтивно ймовірно, що ви зробити в будь-якому випадку - зверху вниз, зліва направо. 

ROB BOWDEN: Питання з цього приводу? Чи повинен я зробити наступний? 

Девід Дж. Малан: Звичайно. 

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

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

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

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

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

Ми можемо продовжувати йти. І в якийсь момент, ми йдемо далеко Досить того, що ми починаємо перезапису цей зворотну адресу. Тому, як тільки ми перезаписати адресу повернення, Це означає, що коли Foo повертається, ми повертаємося туди, де зловмисник говорить його по будь-яке значення він увійшов, яким би символів користувач ввів. І тому, якщо зловмисник в даний час особливо розумний, він може мати це повернутися до десь в PRINTDEF функція або десь в Танос Функція, де-небудь довільним. 

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

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

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

Девід Дж. Малан: Не зовсім дух питання, але прийнятний за специфікації, тим не менш. 

ROB BOWDEN: Питання по будь-якій з цього? Єдине, що ви принаймні потрібно було компіляції коду. Тому, навіть якщо технічно ви не уразливими, якщо ваш коду не компіляції, ми не погодитися з цим. Немає питань? ОК. 

Девід Дж. Малан: Ви хочете сказати це назва? 

ROB BOWDEN: Ні. 

Девід Дж. Малан: Так в цьому, це була чи хороша це новина чи погана новина. Це буквально та ж проблема в якості першого вікторини. І це майже те ж саме Проблема, як pset1. Але це було навмисно спрощена, щоб бути простіше піраміда, який може бути вирішена зі злегка простіше ітерації. І справді, що ми отримували в тут не стільки логіка, тому, ймовірно, до цього моменту, ви більш комфортно, ніж ви були на тиждень один з для петель або чому петель, але насправді, щоб дражнити один від одного, що ви трохи знайомі з Поняття, що PHP не тільки про те, що програмування. Це дійсно може бути використаний в якості мови писати програми командного рядка. 

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

Ми могли б зробити це 0 індекс. Але іноді, я думаю, це просто подумки легше думати про речі, від 1 до 7. Якщо ви хочете один блок, потім два блоки, потім три, потім точка, точка, точка сім. Ми J ініціалізації до 1 а потім розраховує на до I. І тут все в іншому випадку ідентичні. Але слід назвати кілька речей. Ми даємо вам ці два рядки, це перше один, goofily названий як притон для різкого вибуху. І це тільки вказує шлях, папка, в якій програма може бути виявили, що ви хочете використовувати інтерпретувати цей файл. 

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

Таким чином, ви можете видалити. PHP взагалі Нагадаємо, від лекції. І ви реально можете зробити. / Foo якщо Ви chmodded його, зробивши його виконуваний. Так CHMOD + х Foo зробив би це. І якщо ви також додати притон тут. Але насправді, проблема хилить роздрукувавши щось на зразок цього. Ні HTML, немає C-код, звичайно, лише деякі PHP. Так Міло потім повернувся в задачі 25. І в 25, вам дали наступні Код скелет, який був досить просто веб-сторінки. І соковита частина HTML-мудрий знизився тут, де ми маємо всередині тіла форма, яка має унікальний ідентифікатор входу усередині якого було два входи, один з ідеєю ім'я, один з ідеєю кнопки. 

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

Так один із способів зробити це з JQuery, який виглядає трохи синтаксично подив у першу чергу. Ви можете зробити це з чистою коду DOM - document.getelement по ID. Але давайте поглянемо на цій версії. У мене є кілька важливих лінії в першу чергу. Так що, у нас є ця лінія, яка є ідентичний тому, що ви, можливо, бачили в, я вважаю, form2.html від класу на тиждень 9. І це просто кажу, виконати Наступний код, коли документ готовий. Оскільки це важливо тільки тому, що HTML сторінки читаються зверху знизу, зліва направо. 

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

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

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

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

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

І тоді остання деталь полягає в наступному. Чому я повернутися помилкове всередині цієї анонімної функції? 

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

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

АУДИТОРІЯ: Тому що це відбувається тільки один раз. 

Девід Дж. Малан: тільки відбувається один раз. Не зовсім. Так? 

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

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

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

АУДИТОРІЯ: Так тримати його на стороні клієнта. 

Девід Дж. Малан: Ведення це на стороні клієнта. Абсолютно вірно. Потім був мій, про MySQL. 

ROB BOWDEN: ОК. Так що це перше питання було взагалі грубо для людей. Хоча пізніші пішли краще. Таким чином, ви повинні були вибрати правильні дані типу для обох цих стовпців. І обидва з них мають деякі речі про них, що зробити вибір важко. Так внутр не правильний введіть числа. Причина в тому, 12-значний номер рахунку число, внутр не є достатньо великим, щоб зберігати всього цифри. Так діє вибір був би великий Int, якщо ви не знаєте, що. Інший варіант міг би бути поле символ довжини 12. Так що або з тих, працював би. Int не буде. 

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

Девід Дж. Малан: Готівкою. 

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

Девід Дж. Малан: А також, теж, хоча це могло б бути розумним і в інших контексти, щоб думати, може бути, це це шанс для внутр. Я просто відстежувати речі в гроші. Тому що ми явно показали за замовчуванням Значення будучи 100.00, що означає, що він може бути просто внутр. І ще тонкість теж з числа було те, що це не було призначене бути питання з підступом. Але нагадаємо, що внутр в MySQL, як в С, принаймні Прилад, є 32-розрядних. І хоча ми не очікуємо Вас точно знати, скільки цифри, які кошти, не згадати, що найбільша кількість Ви можете представляти потенційно з 32-розрядного числа приблизно те, що? 

Який номер у нас завжди кажу? Від 2 до 32, що і приблизно? Ви не повинні знати точно. Але приблизно корисно в житті. Це приблизно 4 мільярди. Таким чином, ми сказали, що кілька разів. Я знаю, що сказав, що кілька разів. І це приблизно 4 мільярди. І це хороше правило емпіричне знати. Якщо у вас є 8 біт, 256 є магічним числом. Якщо у вас є 32 біта, 4 млрд. плюс-мінус. Так що якщо ви просто запишіть 4000000000, ви побачите, що це менше цифр, ніж 12, що означає, що явно не досить виразність захопити 12-значний номер рахунку. 

ROB BOWDEN: ОК. Таким чином, решта пішли краще. Так припустити, що банк накладає $ 20 щомісяця плата за обслуговування по всіх рахунках. З чим SQL запитів могли банк відняти $ 20 з кожного лічильника, навіть якщо це призводить до деяких негативним сальдо? Так в основному, Є чотири Основні типи запитів - вставити, виберіть, оновлення та видалення. Отже, що ми думаємо, що ми збираєтеся використовувати тут? Оновлення. 

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

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

ROB BOWDEN: Пам'ятайте, що MySQL є окрема мова з PHP. Ми, виявляється, писати MySQL в PHP. І PHP потім відправити його до сервера MySQL. Але вам не потрібно PHP для того, щоб зв'язок з сервером MySQL. 

Девід Дж. Малан: Абсолютно вірно. Так ніякі змінні зі знаками долара повинно бути в даному контексті. Він може просто зробити все математики в самій базі даних. 

ROB BOWDEN: ОК. Так що наступного один. Це наступний? Так. Так з тим, що SQL-запит може банк вилучення з пам'яті номерів через його багаті клієнти, ті, з Залишки більше, ніж 1000? То який з чотирьох основних типів ми збираємося тут потрібно? Виберіть. Тому ми хочемо, щоб вибрати. Що ми хочемо, щоб вибрати? Що колонка ми хочемо, щоб вибрати? Ми спеціально хочемо для вибору номера. Але якщо ви сказали зірка, ми Також прийнято вважати, що. 

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

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

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

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

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

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

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

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

Так що ми можемо тримати його відносно просто. Ми повинні пам'ятати, що ми просто додав Int в чергу. А потім ми просто повертаємо правда. Тим часом, в Dequeue, ми попросили вам робити наступне. Реалізувати це таким чином, що вона dequeues, тобто видаляє і повертає, Int в передній частині черги. Щоб зняти Int, достатньо забути його. Вам не потрібно перевизначити свою лепту. Так що це ще насправді. Так само, як дані на жорсткому диску, ми просто ігноруючи той факт, що тепер там. І якщо д порожній, ми повинні замість цього повертати від'ємне 1. Так що це відчуває довільним. Чому повернутися негативний 1 замість хибно? Так. 

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

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

АУДИТОРІЯ: Ви не змогли повернутися ціле. 

Девід Дж. Малан: Абсолютно вірно. І це де С отримує досить стримуючим. Якщо ви говорите, що ви збираєтеся повернути Int, у вас є повернути Int. Ви не можете отримати фантазії і почати повернення BOOL або поплавок або рядок або щось в цьому роді. Тепер, тим часом, JavaScript і PHP і деякі інші мови може, справді, Ви повернення відрізняється типи значень. І це дійсно може бути корисно, коли ви могли б повернутися позитивні INTS, нулі, негативні Інтс, чи брехня або нульовий навіть для позначення помилку. Але ми не маємо, що універсальність у С. 

Так що з Dequeue, що ми пропоную зробити це - 

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

Девід Дж. Малан: Це чому я не сказав цього. 

ROB BOWDEN: Але це не так що ви не можете повернутися помилковим. 

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

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

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

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

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

Так що якщо я ставлю 34 тут у верхній частині, а потім Я поклав 20 тут, так що це дійсно так далеко, тому що 34 тут. 20 збирається зліва. Так ось менше. Але я не можу потім покласти 59 тут, тому що хоча 59 знаходиться праворуч 20, вона як і раніше зліва від 34. Так що з цього обмеження на увазі, Найпростіший спосіб, ймовірно, вирішуючи цей Проблема в тому, щоб тільки вид з цих чисел - так 20, 34, 36, 52, 59, 106. І потім вставте тих, зліва направо. 

Так 20 йде тут. 34 йде тут. 36 йде тут. 52, 59, 106. І ви також могли б розібрався з деякі підключення і розуміючи, ой, почекайте, я не вистачає номерів заповнити це в тут. Тому мені потрібно reshift що мій маршрут примітка буде. Але зверніть увагу, що в кінцевому трьох, якщо Ви читати зліва направо, він знаходиться в порядку зростання. 

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

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

Так дивиться сюди, ми хотіли б, щоб надрукувати з 20, 34, 36, 52, 59 і 106. Як ми добилися цього? Так що це дуже схоже. Якби ви бачили в минулому іспит проблема що ви хотіли, щоб роздрукувати все дерево запитом між все, це було насправді, навіть легше, ніж це. Так от рішення. Це було значно легше якщо ви зробили це рекурсивно. Я не знаю, якщо хтось намагався зробити це повторно. 

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

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

ROB BOWDEN: Так один із способів наближається будь-яка рекурсивна проблема в тому, щоб просто думати про це, як ви повинні думати про всі кутові випадки. Так вважають, що ми хочемо роздрукувати цю все дерево. Так що всі ми збираємося зосередитися на це конкретний вузол - 36. Рекурсивні виклики, ми робимо вигляд, тих, хто тільки працювати. Так от, це рекурсивний виклик траверс, ми, навіть не замислюючись про це, просто перетинаючи ліву три, уявіть, що вже друкує 20 і 34 для нас. А потім, коли ми в кінцевому рахунку рекурсивно подзвонити траверс на Добре, що буде правильно друкувати 52, 59 і 106 для нас. 

Таким чином, враховуючи, що це може друкувати 20, 34 і інший може друкувати 52, 59, 108, все, що ми повинні бути в змозі зробити, це друк , Себе в середині цього. Так роздрукувати всі перед нами. Роздрукувати OURSELF, тому поточний вузол друку 36, регулярний Е, а потім друкувати все після нас. 

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

ROB BOWDEN: З питань? 

Девід Дж. Малан: І трохи вниз, щоб цифри, хто-небудь знає, де ці цифри взялися? 

ROB BOWDEN: У мене буквально ні найменшого уявлення. 

Девід Дж. Малан: Вони з'являються по всій вікторини. 

АУДИТОРІЯ: Чи є вони ті ж номери? 

Девід Дж. Малан: Ці цифри. Трохи Великоднє яйце. Так що для тих з вас, спостерігаючи в Інтернеті за адресою додому, якщо ви можете сказати нам по електронній пошті heads@CS50.net яке значення цих повторюваних шість цифри всій вікторини 1, ми будемо душ вас з дивовижним увагою у фіналі Лекція і стрес м'яч. Хороший, тонкий. 

ROB Боуден: Будь останні питання ні про що на вікторині?