DAVID J. Malan: Добре. Така че, добре дошли в първата по рода си CS50 аутопсия за тест. Ние смятахме, че ще се сложи началото тази традиция тази година. И това ще бъде възможност да преминете през решения на теста. И ние ще се ускори или забави базирани относно интереса на тези тук. 

Така че, вие вероятно сте тук, защото вие сте интересуват от това как бихте могли да имат или е трябвало да отговори на някои на тези проблеми. Така че защо да не можем да разгледаме в този раздел на първо място? Така че все струни. Това ще ви даде три различни версии на програма, която е, в крайна сметка, означаваше да се получи низ от потребителя. Дали не го е направил, че е наляво, за да можете да се определи. 

И ние попита Въпрос 0, Предполагам, че тази версия е едно съставен и се изпълнява. Защо може segfault програмата? На пръв поглед, някакви предложения , защо? Да. 

ПУБЛИКАТА: Така Спомням си тази в предишна например за разглеждане на Чар * е и виждането на сканирането на S и виждайки, защото това е една показалка, как го засяга това, което сканира? Дали това е или адреса на е? 

DAVID J. Malan: OK. Добре. Така че, в крайна сметка, източникът на всеки проблем се предполага, че ще се намали за тази променлива и. И това е наистина една променлива. Типът данни на тази променлива е Чар *, което означава, че ще съдържа адреса на герой. И в това е прозрението. Тя ще съдържа адреса на характер или, по-общо казано, адрес на първия знак в цял блок от символи. 

Но уловката е, че и сканиране, цел в живот, се дава един адрес и предвид код формат, като% S, прочетете низ в парчето памет на този адрес. Но тъй като има знак за равенство не преди че точка и запетая на първия ред с код, защото ние всъщност не разпредели всяко памет с изчистване, защото тя всъщност не разпределят масив от някои размери, всички , което правиш е четене на потребителя клавиатура вход в някаква пълна стойност на боклука, който е в а по подразбиране. Така че шансовете са ти започваш да segfault ако този адрес не просто така се случи, да бъде на стойност, която можете, в действителност, пишете на. Така че лошо да не се разпределя паметта си там. 

Така че в един въпрос, ние попита, Предполагам, че е версия 2 съставен и се изпълнява. Защо може segfault тази програма? Така че това е един по-малко бъги. И там е наистина само една очевиден начин, където можете да предизвика segfault тук. И това е тематична. Всеки път, когато използвате в в паметта, което може ли да направите, за да предизвика segfault с версия 2? 

ПУБЛИКАТА: Ако използвате този вход в низ, който е по-дълъг от 49 символа. 

DAVID J. Malan: Точно така. Всеки път, когато видите нещо, с фиксирана дължина когато става въпрос за масив, вашият радар трябва да изгасне, че това би могло да бъде проблематично, ако не сте проверка на граници на масив. И това е проблемът тук. Ние все още използвате scanf. Ние все още използвате% S, което означава, опитайте да се чете низ от потребителя. Това ще се чете в S, който, в този момент, е ефективно адрес на парче памет или това е еквивалентно. Това е името на масива на символа на паметта. 

Но точно това, ако прочетете низ това е по-дълъг от 49 символа, 49 защото имате нужда от място за наклонената черта 0, ти започваш да се прелее че буфер. И вие може да се късметлия и да бъде в състояние да напиши 51ва характер, 52ри, 53-та. Но в един момент, операционната система ще кажа, не. Това определено не е памет ти е позволено да се докоснат. И програмата ще segfault. 

Така че, евристичния трябва да има никакви време имаш определена дължина, трябва да сте сигурни, че проверка на дължината на каквото и да е, което се опитвам да се чете в него. 

ПУБЛИКАТА: Така че да се реши, че бихте могли да са имали изявление проверка всъщност е по-голяма дължина от или по-малко от? 

DAVID J. Malan: Абсолютно. Вие просто имате състояние който казва, ако - или по-скоро, че не е задължително да знаете предварително колко знака на потребител ще напишете, защото имате пиле и яйцето. Не и докато не съм го прочете с scanf Може ли да разбера колко дълго е то. Но в този момент, че е твърде късно, защото вече сте го прочетете в някои блок на паметта. Така Като настрана, избягва CS50 библиотечни този въпрос изобщо, отзоваване с помощта fgetc. И тя гласи един символ в даден момент, пристъпват на пръсти заедно, знаейки, че сте не може да прелива с характер, ако четете една в даден момент. 

Уловът е с getstring отзоваване е че ние трябва постоянно повторно размер това парче на паметта, която е само болка. Това е много линии на код, за да направи това. Така че друг подход би бил да се всъщност използват един братовчед, така че да се каже, на scanf. Съществуват варианти на много от тези функции, които всъщност проверяват дължина на колко знака можете да прочетете максимално. И вие може да се уточни, не се чете повече от 50 символа. Така че това ще бъде друг подход, но по-малко сговорчива на по-големи входове. 

Така че въпрос 2 пита, да предположим, че версия 3 се компилира и изпълнява. Защо може segfault тази програма? Така че това е всъщност същото отговоря, въпреки че изглежда малко по-красиви. Ние използваме изчистване, което се чувства като ние сме се дава повече опции. И тогава ние сме освобождавайки че памет в края. Тя все още е само на 50 байта памет. Така че ние все още може да се опита да се чете в 51, 52, 1000 байта. Това ще segfault за точно същата причина. 

Но има и друга причина също. Какво друго може да изчистване връщане освен адреса на парче памет? Той може да се върне нулев. И тъй като ние не сме проверка за , че ние може да се прави нещо глупав и по друга причина, а именно, че ние може да се казва, scanf, прочетете въвеждане на потребителя от клавиатурата в 0 местоположение, AKA нищожна. И това също определено ще предизвика segfault. Така че за целта на теста, ние ще са приели нито един от тези, като основателна причина. Един от тях е идентичен. Един от тях е малко по-нюансирана. 

На последно място, по отношение на програмата използване на памет, как версия 2 и версия 3 се различава? Така че за какво си струва, видяхме привидно безкраен запас от възможно отговори на това. И сред отговорите на хората, това, което бяхме надявайки се, но ние приехме друга неща, беше известно споменаване на Всъщност тази версия 2 използва така наречените стека. Версия 3 е с помощта на куп. И функционално, това не прави наистина направи всичко, че голяма част от разликата. В края на деня, ние все още сме само за да се 50 байта памет. 

Но това е един от възможните отговори че ние гледахме. Но ще видите, както можете да си викторини обратно от TFS, че сме направили приемат други обсъждания на тяхната коренно различни употреби на паметта, както добре. Но стека купчина и би било един лесен отговор да отида с. Някакви въпроси? Аз ви давам Роб. 

ROB BOWDEN: Значи проблем 4. Това е една, където трябваше да се запълни в броя на байтовете от всички тези различни видове използвани. Така че първото нещо, което виждаме. Да приемем, 32-битова архитектура, като този CS50 уред. Така че едно от основните неща за 32-битови архитектури, които ни разказва колко голям е точно показалка ще да бъде в архитектурата. 

Така че веднага, ние знаем, че всяко показалка тип е 32-бита или 4 байта. Така че гледам на тази маса, а възел * е тип указател. Това ще бъде 4 байта. Struct възел *, това е буквално идентичен с възел звезда. И така, това ще е 4 байта. String, така че да не изглежда като показалеца все още, но typedef, A низ е просто знак *, който е тип показалка. Така че ще е 4 байта. 

Така че тези три са всички четири байта. Сега, възли и ученик са малко по-сложно. Така че гледам възел и студент, ние виждаме, възел като цяло и показалеца. И студент е два показалки вътре в него. Така че поне за нашия случай тук, начинът че края на изчисляване на размера на тази структура е просто да добавите всичко това е вътре в структурата. 

Така възел, имаме число, което е 4 байта. Ние разполагаме с показалка, която е 4 байта. И така, един възел ще да отнеме до 8 байта. И по същия начин за студент, ние имаме указател, който е 4 байта и друг указател, който е 4 байта. Така че това ще се сложи край сметка е 8 байта. Така възел и ученик са 8 байта. И тези три са всички четири байта. Въпроси за това? Да. 

ПУБЛИКАТА: Дали това е 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. Така че, хей, вие всъщност искате това. 

DAVID J. Malan: Това е парче, което каза , че дадохме вие ​​пренасочване функция, която използва функцията на горния които, от своя страна, отпечатани място, дебелото черво, и след това адреса на който желаете да отхвърляте потребителя. Въпреки, че не виждам 302 изрично там, това е, което PHP магически ще вмъкнете като хедъра казва точно това, което каза Rob там - намерен. Но отидете тук, вместо. 

ROB BOWDEN: OK. Така че какво да кажем за 403 забранено? 

ПУБЛИКАТА: Мисля, че това е, че сървърът е основно казва, че клиентът Не мога да вляза в началната страница. 

ROB BOWDEN: Така че, да. Е, типичното Отговорът бяхме Очаквах е нещо от рода на файловете не са chmodded подходящо. Това вероятно е при какви обстоятелства си ги видял. Но има една причина, че клиентът може да бъде виновен тук. Там всъщност е друг код на състоянието - 401. Така че те са много сходни. 

401 е неразрешен. А 403 е забранено. И така неразрешен, специално за Вас получите, ако не сте влезли в профила си Но може да означава да влезете в че сте упълномощени. Но ако вече сте влезли в и вие все още не разполагат с разрешение, след това можете да получите също и забранено. Така че, ако сте влезли в системата и нямат разрешение, забранено е също нещо, което може да получи. 

DAVID J. Malan: И механизмът, чрез което тези проблеми са обикновено решен на сървъра чрез каква команда? CHMOD, ако това е наистина е разрешения издава на файла или директорията. 

ROB BOWDEN: 404 Тогава не е намерен. Да. Така че, за разлика от 302, където това не е точно където питаш но тя знае какво искате, това, тя просто има никаква идея какво искаш. И не се иска нещо валиден. 418 Аз съм чайник и след това 500 вътрешен сървър. Така че, защо да ви се получи това? 

Така segfault - Аз всъщност не знам, че окачествяването стандарт за това. Но ако вашият PHP код има нещо нередно в него, на теория, то би могло всъщност segfault, като в този случай, това 500 вътрешна грешка в сървъра, нещо не е наред с вашия сървър конфигурация. Или има синтактична грешка във вашата PHP код. Или нещо лошо се случва. 

DAVID J. Malan: Ние видяхме segfault сред отговори на няколко хора. И технически, тя може да се случи. Но това би било PHP, програмата написани от други хора, всъщност segfaulted, които само ако тези хора прецаках и пише бъги код в техния преводач би Самият PHP segfault. Така че, въпреки че 500 е като segfault по дух, това е почти винаги резултат на издаване на конфигурационен файл с вашия уеб сървър или, както каза Роб, синтактична грешка, като теб не го е затворило един цитат. Или сте загубили точка и запетая някъде. 

ПУБЛИКАТА: Така че за Shuttle PSET, I мисля, че когато аз го направих веднъж Натиснах браузър, но нищо не излезе, това, което те наричат ​​бяла страница. Но това е така, защото на кода. Мисля, че това е JavaScript, нали? 

ROB BOWDEN: Да. 

ПУБЛИКАТА: Бихте тази грешка все още да се качиш? 

ROB BOWDEN: Значи ти би не са придобили тази грешка, защото всичко, от гледна точка на уеб сървъра е напълно наред. Но ти поиска index.html. Заявили сте shuttle.js и service.js. И това беше в състояние успешно да се завърнат за всички онези неща, които - 200. OK. Тя е само, когато вашия браузър се опита да тълкува кода на JavaScript, че Това е като, чакай, това не е валиден грешка JavaScript. Някакви други въпроси? Добре. 

DAVID J. Malan: Така че следващия нагоре беше номер 11. А 11 беше най-страшното за много хора. Така че най-важното нещо е да се отбележи тук е, че това е наистина, за двойно свързан списък. Но това не е същото като миналата година списък двойно свързан проблем, които не ви дават уговорката, че списъка може, в действителност, е сортиран. 

Така че фактът, че списъкът е сортиран и факта, че тази дума е подчерта там е трябвало да се предадат че това е действително опростяване на това, което иначе би било по-голямо предизвикателство проблем и по-дълъг. Така често срещана грешка тук е трябвало да сложи миналогодишното решение на вашия милион пейджър и след това просто копирайте сляпо, че надолу като отговор, който е правото отговори на друг въпрос подобни по дух. Но тънкостите тук са, както следва. 

Така че едно, ние сме обявен възел и определена по обичайния начин тук. Тогава ние определен списък на бъде глобален показалка инициализира с нула. Тогава очевидно, има две функции имаме прототипи за тук, вложка и го извадете. И тогава имаме някакъв примерен код тук за правене на куп вмъквания. И тогава ние ви молим да попълните изпълнение на въвеждане долу по такъв начин, че да въвежда п в списъка в константно време, също така подчерта, дори и ако вече е налице. 

Така че красотата е в състояние да вмъкнете в константно време е, че предполага че трябва да поставите новата възела, където? В предната част. Така че тя елиминира, за щастие, най-малко един от случаите, които използват, за да изиска още повече реда код, като го е направил миналата година и дори в клас, когато ние говорил чрез този вид на нещо, с хора и с някои вербална псевдо код. Така че в разтвора тук, нека да прескачам да, че само за да имат визуален контакт екрана. 

Забележете, че ние правим следното. И също така да забележите друга опростяването е, че дори ако е вече е налице, така че това означава, че дори ако броят им е вече там, можете да просто сляпо поставете друг копие от него. И това също е трябвало да бъде опростяване, така че бихте могли да съсредоточи върху, наистина, някои от по- интелектуално интересна част и а не само някои допълнителни проверки за грешки като се има предвид ограниченото време. 

Така че в този разтвор на пробата, който заделяме показалеца на лявата страна другата тук на една възлова точка. Сега осъзнавам, че показалеца, като Роб каза, е само на 32 бита. И в действителност не съдържа адрес, докато не присвояване на адрес. И ние правим това от дясната страна страна чрез изчистване. Като добър гражданин, ние се провери дали изчистване не е, в действителност, нула, така че ние не случайно се създаде а segfault тук. И всеки път, когато използвате изчистване в живота, Трябва да се проверява за нищожна, за да не имате коварен бъг. 

Тогава ние се инициализира, че нищожна от възлагане н и предишния и следващия. И в този случай тук, аз инициализира преди нищожна, тъй като тази нова възел ще бъде новият в началото на списъка ми. Така че там ще бъде нищо преди него. И аз искам да се добави по същество съществуващ списък към новата възела, като създаване следващия равна на себе си списък. Но аз просто все още не съм свършил. Така че, ако самата списъка вече е съществувал, и има най-малко един възел вече на място, ако това е списъкът тук и аз вмъкнете нов възел тук, I Трябва да се уверите, че бившият ми възел изтъква назад към моя нов възел, защото това е отново двойно свързан списък. 

Така че ние правим проверка здрав разум. Ако списъкът не е нула, ако има вече един или повече възли там, тогава добавя, че обратно препратка така да се каже. И тогава най-последното нещо, което трябва да направите, е всъщност актуализира глобалното самата променлива списък, за да се отбележи на този нов възел. Да. 

ПУБЛИКАТА: В показалка стрелката [Недоловим] се равнява на нула, прави това се справят със списъка, защото списъкът е нула? 

DAVID J. Malan: Nope. Това е просто ми е активно Внимавайте, в която, ако това е моят Оригинален списък с може би някои повече възли тук и аз съм вмъкване ми нов възел тук, там ще да бъде нищо повече от тук. И аз искам да улови тази идея чрез определяне на предишния да нула на новия възел. И вероятно, ако ми код е правилен и няма друг начин да се вмъкнете възли, различни от тази функция, Предполага се, че дори и ако вече има списък един или повече възли в нея, вероятно на списък на първия възел, ще имат предишния показалеца на самата нула. 

ПУБЛИКАТА: И точно проследяване. Причината поставите показалеца следващите равни списък се правиш на показалеца преди списък с това, че се посочи към следващата, предполагам - Аз не - просто изброява? 

DAVID J. Malan: Точно така. И така, нека всъщност разгледа две дела тук наистина, въпреки че поръчка, ние ще ги разглеждаме не е съвсем същото като на кода. Но на високо ниво, ако това представлява списък и това е 32-битов показалка, най-простият сценарий е че това е нищожна по подразбиране. И предполагам, че искате да вмъкнете номер 50 е първият номер. Така че аз ще отида напред и да се разпределят възел, който ще съдържа три области - н, предишния и следващия. 

Отивам да сложа номер 50 тук, тъй като това ще бъде п. Това ще бъде следващата. И това ще бъде предишния. И така, какво мога да направя в този случай? Е, аз току-що направихте линия 1 тук. Pointer п получава п. Аз след това казва, предишна трябва да получи нула. Така че това ще бъде нула. Тогава аз ще кажа следващия ще получите списък. 

И това просто работи по добре. Това е нищожна. И така, аз казвам, новият възел е следващият област трябва да получите каквото е това. Така че това поставя друг нула там. И тогава последното нещо, Правя, е да проверите тук. Ако списъкът не е равна на нула, но това е равна на нула, така че ние пропуснем напълно. И така, всичко, което правя е следващия списък получава показалка, която води до по-картинно снимка подобно. Така че това е един сценарий. 

И този, който се пита за специално е в ситуация като тази, където вече имаме списък с един възел. И ако се върна в оригинала изявление проблем, Сега ще вмъкнете да речем е 34, само за на името на дискусия. Така че аз съм просто ще се удобно изготвя, че тук. Току-що malloced. Нека приемем, че аз съм проверка за нищожна. 

Сега, аз отивам да се инициализира п да бъде 34. И това ще бъде п. Това ще бъде следващата. И това ще бъде предишния. Нека се уверим, че не го направих получи това назад. Предишна идва първо в дефиницията. Позволете ми да се определи това. Това е предишния. Това е следващата. Въпреки че те са идентични, нека си го запази последователна. 

Previous. Това е следващата. Така че аз съм просто malloced бележката ми, проверих за нула, определен в 34 възела. Предишна получава нищожна. Така че това ми дава това. Следваща получава списък. Така списък е това. Така че това е същата сега, както и изготвяне това стрелка, така че да сочи към едно в същото. И тогава аз съм проверка, ако списък не е равно на нула. И това не е този път. Тогава аз ще направя списък предишния получава показалка. 

Така се изброят предишния получава PTR. Така че това има ефект на пускането графичен стрелка тук. И това става все по-малко вълниста, линиите. И тогава, накрая, аз се актуализира Списък, за да сочи към показалеца. Така че сега това говори за този човек. И сега, нека да направим един бърз проверка здрав разум. 

Тук е списъка, който е глобалната променлива. Първият възел е, всъщност, 34, защото Аз съм след стрелка. И това е правилно, защото искам да поставете в началото на списъка всички нови възли. Следващият му поле ме води до това момче. Ако продължавам, аз удари следващия е нищожна. Така че няма повече списък. Ако аз хит предишния, получавам Там, откъдето аз очаквам. 

Така че все още има няколко насоки, Очевидно е, че да се манипулира. Но фактът, че ви е било казано да се направи това в постоянен път, когато означава само има краен брой неща ти е позволено да правя. И какъв е този номер? То може да бъде една стъпка. Тя може да бъде два. Тя може да е 1000 стъпки. Но това е крайно, което означава, че не можеш са всякакъв вид на примка става тук, не рекурсия, без контури. Тя просто трябва да бъде трудно кодирани линии на код, тъй като ние имаме в тази извадка. 

Така че следващия проблем 12 ни помоли да завърши изпълнението на премахване долу по такъв начин, че да премахва п от списъка за линейно време. Така че ще трябва малко повече мърдам стая. Може да се предположи, че N, ако е наличен в списъка, ще присъства не повече от веднъж. И това също е писано да бъде тест-базирани опростяване предположение, така че ако намерите номер 50 някъде в списъка, не трябва също така да трябва да се притеснявате за да продължи да обхождане, търсене на всички възможни Копие от 50, които просто ще прехвърли в някои дреболии в ограничен период от време. 

Така че с премахване, това определено беше по-голямо предизвикателство и повече код, за да пиша. Но на пръв поглед, честно казано, тя може да изглежда непоносимо и като нещо, няма начин бихте могли да имат излезе с по викторина. Но ако ние се фокусираме върху отделните стъпки, надявам се, това ще стане внезапно те поразява, че всеки един от тези индивидуални стъпки прави очевиден смисъл в ретроспекция. Така че нека хвърлим един поглед. 

Така че, на първо място, ние се инициализира показалка да се изброят. Защото искам линейното време, това означава, Отивам да има някаква връзка. И често срещан начин за обхождане на възли в структура списък или всякакъв вид на структура итеративно е да се вземат указател към предната част на данните структура и след това просто да започнат да актуализират то и ходи си път чрез структурата на данните. Така че аз ще направя точно това. 

Докато показалеца, моята временна променлива, не е равно на нула, нека отидете напред и да се провери. Аз ли се късметлия? Дали областта на N в възел Аз съм в момента търси в равна на брой търся? И ако е така, нека да направим нещо. Сега, ако забележите това състояние обхваща цялата следните редове код. Това е единственото нещо, което ме интересува - намиране на номер в въпрос. Така че няма друго, което опростява неща концептуално малко. 

Но сега, аз осъзнах, и може да се наложи само осъзна това след като мислене него чрез малко, има всъщност два случая тук. Един от тях е, когато възелът е на началото на списъка, който е малко досадно, защото това е специален случай, защото трябва да се справим с това нещо, което е само аномалия. Навсякъде другаде в списъка, това е едно и също нещо. Има предишна възел и следващия възел, възел предишния, следващия възел. Но този човек е малко по-специален ако той е в началото. 

Така че, ако показалецът е равен на списъка себе си, така че ако аз съм в началото на списъка и аз не съм намерил N, имам нужда да направите няколко неща. Едно, че трябва да променя списъка на точка на следващото поле, 50. Така че предполагам, че аз се опитвам да се премахне 34. Така че този човек трябва да тръгвам далеч в един момент. 

Така че аз отивам да се каже, списък получава показалеца следващия. Е, това е показалеца. Следваща сочи насам. Така че това се променя това с дясната стрелка сега, за да сочи към този човек тук. Сега, не забравяйте, ние имаме временна променлива. Така че ние не са сираци всички възли, защото аз също имам този човек в моя изпълнение на премахване. Така че сега, ако самия списък не е нула, Аз трябва да се определи нещо. 

Трябва да се уверите, че тази стрелка, който предварително е насочена 50-34, това трябва да си отиде, защото, ако аз се опитвам да се отървете от 34, 50 е по-добре да не поддържа нито вид на гърба препратка към него като стрелка предложи. Така че аз просто направих тази линия. Така че след като свърша. Това дело всъщност е доста лесно. Рязане на разстояние от главата на списъка е относително проста. 

За съжаление, там е това досадно друг блок. Така че сега, аз трябва да разгледа делото когато има нещо по средата. Но това не е твърде ужасно, с изключение на за синтаксис като този. Така че, ако аз не съм в началото на списък, аз съм някъде по средата. И тази линия тук се казва, старт По какъвто възел сте у. Отиди до следващото поле предходната възела и посочи, че в показалеца. 

Нека да направим това картинно. Това ставаше все по-сложно. Така че, ако имам предишните полета тук - нека да направим това - следващите полета тук. Отивам да се опрости ми указатели скоро отколкото се направи цял куп нещата назад и напред, кръстосващи всеки друг. И сега, нека просто кажем, че това е едно, две, 3 от съображения за обсъждане, дори макар че не е изравнена с въпросният проблем. 

Така че тук е моят свързан списък. Аз съм се опитва да премахне две в тази конкретна версия на историята. Така че аз съм актуализиран указател към се сочи към този човек. Така че това е PTR. Той посочи тук. Това е списък, който съществува в световен мащаб, както и преди. И той посочи тук, без значение какво. И сега, аз съм се опитва да премахне две. 

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

И какво от това, че ред код, има само направено е малко от това. И сега, това се гледа като стъпка в правилната посока. Ние по същество иска да клъцна 2 на средата на 1 и 3. Така че има смисъл, че ние искаме да маршрут този указател около него. Така че това следващия ред се извърши проверка дали показалка следващия не е нула, има наистина някой, който да правото на две, това означава, че ние също трябва да направим малко парченце тук. 

Така че сега трябва да следват този указател и актуализиране на предишния показалеца върху този човек, за да се направи малко на заобиколно тук въпросът тук. И сега, визуално, това е хубаво. Това е малко разхвърлян, в които има никой не посочи към два вече. 2 сочи наляво. И две сочи надясно. Но той може да прави каквото си иска, защото той е на път да се освободи. И няма значение какво тези стойности са вече. 

Важното е, че останалите момчета са маршрутизирането по-горе и под него. И наистина, това е, което ние правим по-нататък. Ние безплатно показалка, което означава, да кажем на операционна система, вие сте добре дошли да си върнем това. И тогава най-накрая, да се върнем. Else имплицитно, ако ние все още не са върнати, ние трябва да продължим да търсим. Така че показалеца е равна показалка следващия просто означава движи този човек тук. Преместете този човек тук. Преместете този човек тук, ако в действителност, ние не намери броя търсим още. 

Така че, честно казано, това изглежда напълно изумителен, мисля, на първо поглед, особено ако сте се бореше с това по време на теста и след това вижте нещо като това. И ти потупване сами по гърба. Е, няма начин мога да имам излезе с, че на теста. Но бих казал, можете, ако нарушите го надолу в тези индивидуални случаи и само пеша през него внимателно, макар, разбира се, под стресиращи обстоятелства. 

За щастие, на снимката направена всичко по-щастливи. Може да се направи това в произволен брой начини. Не е нужно да се направи, кръстосващи нещо тук. Можете да го направите с прав подобни на тези редове. Но същността на този проблем, в Като цяло, е да осъзнаем, че картина в края на краищата трябва да изглежда малко нещо подобно, защото константно време намекна, че продължаваш заглушаване и заглушаване и заглушаване на нови възли в началото на списъка. Някакви въпроси? Вероятно най-голямото предизвикателство на сигурност на въпросите за кодиране. 

ПУБЛИКАТА: Така е списък, подобен на глава предишните примери. 

DAVID J. Malan: Точно така, точно така. Просто друго име за глобална променлива. В световен мащаб какво? 

ROB BOWDEN: OK. Така че това е една, където можете трябваше да се напише параграфа. Някои хора пишат есета за този въпрос. Но просто трябва да се използват тези шест условия да се опише това, което се случва, когато се опитате да се свържете с 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 в тази машина. Е как няма да го стигнем до тази машина? Е, искането отива от рутер за рутер подскачащи. Не забравяйте примера в клас, където ние всъщност видях маршрута, по който пакети се появиха, когато ние се опитахме да общуват. Видяхме го да скочи над Атлантическия океан Ocean в един момент или нещо такова. 

Така последният срок пристанището. Така че това сега е на вашия компютър. Можете да имате няколко неща в момента комуникация с интернет. Така че може да се работи, да речем, Skype. I може да има уеб браузър с отворен. Може и да имам нещо, което torrenting файлове. Така че всички тези неща са Комуникация с интернет по някакъв начин. 

Така че, когато компютърът ви получава някои данни от интернет, как го прави знам какво приложение всъщност иска данните? Как не го знае дали този конкретен данни са предназначени за torrenting заявление за разлика към уеб браузъра? Така че това е целта на пристанища в които всички тези приложения трябва твърди порт на вашия компютър. Така че вашия уеб браузър казва, хей, Аз съм за слушане на порт 1000. И си torrenting програма се казва, Аз съм за слушане на порт 3000. И Skype казва, аз съм с порт 4000. 

Така че, когато можете да получите някои данни, че принадлежи до едно от тези приложения, данните се маркира с кой порт действително трябва да бъде изпратена заедно с. Така че това казва, о, аз принадлежа към порт 1000. Знам, че след това трябва да предаде настоящата заедно с моя уеб браузър. Така че причината за това е от значение тук е, че уеб сървъри са склонни да слушате на порт 80. Така че, когато се свържете с Facebook.com, аз съм комуникация с някои машина. Но аз трябва да кажа, кой порт на тази машина искам да комуникирам с. И уеб сървъри са склонни да бъдат слушане на порт 80. 

Ако те искаха, те биха могли да го настроите така тя изброява като на порт 7000. И след това в уеб браузър, можех ръчно въведете Facebook.com: 7000 изпрати искане до порт 7000 на уеб сървър на Facebook. 

DAVID J. Malan: И в този случай, дори въпреки че ние не изисква хора Споменавам това, в този случай, какво пристанище би искането всъщност отидете? Опитайте отново. Точно така. Не търси това, но финес че е там никой последният. 

ROB BOWDEN: Така HTTPS, тъй като това е слушане специално за криптирани, че е на порт 4430. 

Публика: и имейли са 25, нали? 

DAVID J. Malan: Изходящ имейли, 25, да. 

ROB BOWDEN: Аз дори не знам повечето от - всичко на по-ниските от тях са склонни да бъдат запазено за нещата. Мисля, че всичко е под 1024 е запазено. 

ПУБЛИКАТА: Защо казахте 3 е грешен номер? 

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

DAVID J. Malan: Но това глупаво клип от - е CSI, където те имат номер, който е твърде голям за IP адреса. 

ROB BOWDEN: Всякакви въпроси за тази? На следващия един, толкова пълна промяна в тема, но ние имаме това PHP масив за къщите в четириядрени. И ние имаме един неподреден списък. И ние искаме да отпечатате всеки елемент от списъка просто съдържащ името на къщата. Така че ние имаме един foreach цикъл. Така че не забравяйте, синтаксисът е foreach масив като елемент в масива. Така през всяка итерация на цикъла, къща ще отнеме на една от стойности вътре в масива. 

На първата итерация, къщата ще бъде Cabot House. На втора итерация, къщата ще бъде Courier House и така нататък. Така че за всеки четириядрен като къща, ние сме просто ще се отпечата - Вие също може да повтори - елемента списък и след това името на къщата и след това затворете елемента от списъка. Фигурните скоби, не са задължителни тук. 

И тогава ние също заяви във въпроса себе си, не забравяйте да затворите неподреден списък маркер. Така че ние трябва да излезете от режим на PHP За да направите това. Или бихме могли да се повтори затворете неподреден списък маркер. 

DAVID J. Malan: Също така добре тук, ще бил да се използва старото училище за линия с $ I = 0 0 и използване на броя на разбера дължината на лъча. Totally добре също, просто малко wordier. 

ПУБЛИКАТА: Така че, ако сте били ще [Недоловим], щяхте да направите - Забравям какво [недоловим] е на линия. Бихте ли $ четириядрени скоба аз? 

DAVID J. Malan: Точно така. Да, точно така. 

ROB BOWDEN: Нещо друго? 

DAVID J. Malan: Добре. Компромиси. Така че имаше букети от отговори възможно за всеки от тях. Бяхме наистина просто търсите нещо непреодолими за главата и един недостатък. И номер 16 попита, валидиране на потребителите " въвеждане от страна на клиента, както и с JavaScript, вместо от страна на сървъра, както и с PHP. Така че това, което е с главата на прави от страна на клиента? 

Е, едно от нещата, които предложихме е че да намалите латентност, защото не трябва да се притеснява се свържат с сървър, който може да отнеме няколко милисекунди или дори няколко секунди чрез избягване на това и просто валидиране на потребителите вход от страна на клиента от задействане на по-представи манипулатор и Само проверявам, да не те вида нещо за името? Дали те въведете нещо в за имейл адрес? Знаете те избират общежитието от от падащото меню? 

Можете да ги даде моментална обратна връзка използване на гигахерца компютъра или каквото и те са, че е всъщност на бюрото си. Така че това е просто по-добър потребителски изпитате обикновено. Но един недостатък на това от страна на клиента валидиране, ако го направя, без да прави от страна на сървъра валидиране е, че Най-всеки, излизащ от CS50 знае , че може просто да изпрати всички данни, които искате към сървър произволен брой начини. Честно казано, в повечето всеки браузър, можете да кликнете наоколо в настройките и просто изключите JavaScript, което, ако Следователно, забранете всяка форма на валидиране. 

Но вие също може да се припомни, че дори и аз Направих някои тайнствени неща в клас с помощта на Telnet и всъщност се представя за да бъде браузър чрез изпращане GET заявки към сървъра. И това със сигурност не е с използване на JavaScript. Това е просто ми пишете команди на клавиатура. Така че наистина, всеки програмист в рамките на достатъчно комфорт с интернет и HTTP може да изпрати каквото и данни, той или тя иска към сървър без валидиране. И ако вашият сървър не е също и проверка, е те да ми даде име, е това всъщност е валиден имейл адрес, направих те избират общежитието, може да се свърши до поставяне фалшива или просто празен данни във вашата база данни, която вероятно няма да бъде нещо добро, ако сте се предполага, че е там. 

Така че това е едно досадно реалност. Но като цяло, от страна на клиента валидиране е страхотно. Но това означава два пъти повече работа. Въпреки че правим съществуват различни библиотеки, JavaScript библиотеки за например, които правят толкова много, много по-малко от главоболие. И вие може да използва част от кода от страна на сървъра, от страна на клиента. Но не осъзнават, че това е типично допълнителна работа. Да. 

ПУБЛИКАТА: Така че, ако ние просто каза по-малко сигурен - 

DAVID J. Malan: [смее се] Уф. Тези, които са винаги по-трудно такива да се произнесе. 

ROB BOWDEN: Това би са били приети. 

DAVID J. Malan: Какво? 

ROB BOWDEN: съм създал този проблем. Това щеше да бъде приет. 

DAVID J. Malan: Да. 

ПУБЛИКАТА: Cool. 

ROB BOWDEN: Но ние не приемаме за първи едно - Е, това, което търсим, е нещо подобно, че не е нужно да се комуникира със сървъра. Ние не приемаме само по-бързо. 

ПУБЛИКАТА: Какво ще кажете за не презареди страницата? 

ROB BOWDEN: Да. Това беше приет отговор. 

DAVID J. Malan: нещо, когато ние се чувствахме че е по-вероятно, отколкото не е вероятно че ти знаеше това, което бяха казвайки, който е труден линия, за да се направи понякога. С помощта на свързан списък вместо на масива да се поддържа сортирано списък от цели числа. Така че с главата ние често се цитират с свързан списъци, които мотивират тяхната цялост въвеждането е да получите динамика. Те могат да растат. Те могат да се свие. Така че не е нужно да скочи през обръчите действително да се създаде повече памет с масив. Или не е нужно просто да кажа, съжалявам, ръководство. Масивът е изпълнен. Така динамичен растеж на списъка. Недостатък обаче на свързани списъци? 

ПУБЛИКАТА: Това е линейна. Търсене на свързан списък е линейна вместо това, когато влезете инча 

DAVID J. Malan: Точно така. Търсене на свързан списък е линейна, дори ако това е сортирана, защото можете да само следвайте тези галета, те указатели, от началото на списъка до края. Вие не можете да се наберат произволен достъп, и по този начин, двоично търсене, дори ако това е подредени, че бихте могли да общо с масив. А има и друга цена. Да. 

ПУБЛИКАТА: Memory неефективно? 

DAVID J. Malan: Да. Е, не е задължително да казват неефективна. Но тя не ви струва повече памет, защото имате нужда от 32 бита за всеки възел за допълнително показалеца, в Поне за единично свързан списък. Сега, ако сте само съхраняване на числа и добавяте показалеца, това е всъщност вид на не-тривиално. Това удвояване на размера на паметта. Но в действителност, ако сте съхраняване на свързан списък на structs които биха могли да имат 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, но супер проста, където колоните са просто demarked със запетаи вътре на иначе текстов файл. И с помощта на SQL база данни е малко по-убедителна. Това е главата, защото можете да получите неща като изберете и вмъквате и изтривате. И вие получавате, Предполага се, индекси, които MySQL и други бази данни, като Oracle, изгради за вас в паметта, която означава, че вашият избор вероятно не е ще бъде линейна горе до долу. Това всъщност ще бъде нещо като двоично търсене или нещо подобни по дух. Така че те са като цяло по-бързо. 

Но един недостатък е, че това е просто повече работа. Това е повече усилия. Трябва да разберете, бази данни. Вие трябва да го изправи. Имате нужда от сървър, за да стартирате тази база данни на. Трябва да се разбере как да я конфигурирате. Така че това са само тези видове компромиси. Като има предвид, CSV файл, можете да го създаде с Gedit. И вие сте добре да тръгвам. Няма никаква сложност отвъд това. 

Използването на Trie вместо на хеш таблица с отделен верижното да съхранявате речник от думи, напомнящи на pset5. Така че се опитва с главата, на теория най-малко, е какво? Constant време, най-малко, ако сте хеширане на всеки от отделните буквите в една дума, като теб Може да се наложи за pset5. Това може да е пет, шест хешове хешове ако има пет или шест буквите в думата. И това е доста добро. И ако има горна граница за това как дълго думите ти биха могли да бъдат, това е наистина асимптотично константно време. 

Като има предвид, хеш таблица с отделен верижното, проблемът там с тази вид на структура данни е, че изпълнение на своите алгоритми обикновено зависи от броя на нещата вече в структурата на данните. И това определено е случаят с вериги, с което още нещо, което поставяте в хеш таблица, колкото по-дълго тези вериги отиват, което означава в най-лошото случай, нещо, което може да се търси е чак в края на един на тези вериги, които ефективно преминава в нещо линейна. 

Сега, на практика, то би могло абсолютно се окаже, че хеш таблица с вериги е по-бързо от съответния изпълнение Trie. Но това е, по различни причини, сред която се опитва да използват един куп памет, която може в действителност, бавни неща надолу, защото те не получават хубаво ползи от нещо, наречено кеширане, където нещата, които са близо един до друг в паметта може да бъде достъпен често по-бързо. И понякога може да излезе с една наистина добра хеш функция. Дори ако имате да губите малко памет, може да, наистина, да бъде в състояние да намерите неща, бързо и не толкова зле, колкото линейно. 

Така че по-кратко, там не беше задължително с всеки един от тях или дори два специфични неща, които са били търсите. Наистина нищо убедителен като главата и недостатък обикновено хвана окото ни. 

ROB BOWDEN: Така че за посока нагоре, което направихме Не приемам за своя "по-бързо." Ви Трябваше да каже нещо по въпроса. Дори ако ти каза теоретично по-бързо, ние знаехме, че някак си се разбира че е 0 на 1. И хеш таблица, на теория, не е 0, 1. Споменаването нищо по време на работа обикновено имаш точките. Но "бързо", повечето от решенията на големия борд, които са били опити бяха обективно бавно от решения които бяха хеш таблици. Така че по-бързо и на себе си всъщност не е вярно. 

DAVID J. Malan: Dom де дом дом. Аз съм може би единственият, който осъзнава, Ето как, че е трябвало да да се произнася, нали? 

ROB BOWDEN: Имах всъщност нямат представа. 

DAVID J. Malan: Накара смисъл в главата ми. 

ROB BOWDEN: Правя това едно. OK. Така че това е една, където трябваше да се изготви диаграмата, подобен на вас може видяхме на последните изпити. Така че нека просто да погледнете това. Така че от HTML възел, имаме две деца, на главата и тялото. Така че ние клон - главата и тялото. Главата има етикет заглавие. Така че ние имаме заглавие. 

Сега, едно нещо, което много хора забравили е, че тези текстови възли са елементи в това дърво. Така че тук ние се случи да ги привлече като овали за разграничаването им от тези видове възли. Но забележете също така тук имаме отгоре, средната и долната крайна сметка ще бъде текстови възли. Така че тези, забравяйки е малко на обща грешка. 

Тялото има три деца - тези три Divs. Така Разделения, Div, дивизия и след това текста деца възел на тези Divs. Това е доста много за това, че на въпроса. 

DAVID J. Malan: И си струва да се отбележи, въпреки че ние не се спирам на тях детайли във времето, което прекарваме на JavaScript, че заповедта е така, в Всъщност, технически въпрос. Така че, ако главата идва преди тялото в HTML, след това трябва да се появи към останало от тялото в действителната DOM. Това си е, като цяло, просто FYI, нещо, наречено документ с цел, когато това има значение. И ако сте били прилагане на анализатор, програма, която чете HTML в сграда на дървото в паметта, за да бъда честен, това е интуитивно вероятно това, което ви направя така или иначе - отгоре до долу, от ляво на дясно. 

ROB BOWDEN: Въпроси за това? Трябва ли да се направи следващата? 

DAVID J. Malan: Разбира се. 

ROB BOWDEN: OK. Така че това е най-буфер превишен атака въпрос. Основното, което да се признае, тук е, Е, как може един трик противник тази програма в изпълняващата произволен код? Така argv1, първият команден ред аргумент за тази програма, която може да бъде произволно дълго. Но тук ние използваме memcpy да копирате argv1, които тук се намира бар. Ще го прехвърляха като аргумент. И така, това е като в лентата за името. 

Така че ние сме memcpying бар в този буфер в. Колко байта сме копиране? Е обаче много байта бар се случва да се използва, дължината на този довод. Но с е широк само 12 байта. Така че, ако ние въведете аргумент на командния ред това е по-дълъг от 12 байта, ние сме ще прелее тази специално буфер. Сега, как може да излъже противник на програмирате в изпълнение на произволен код? 

Така че не забравяйте, че тук Основната се обажда Foo. И така, след това основните разговори Foo. Да се ​​направи това. Така че ние имаме нашия стак. И главната има стак кадър в дъното. В един момент, основните разговори Foo. Е, веднага, основните разговори Foo. И така Foo получава своята собствена стека рамка. 

Сега, в някакъв момент, Foo няма да се върне. И отиде Foo възвръщаемост, ние трябва да знаем при какъв ред код вътре в основната ние са били с цел да се знае къде ние трябва да се възобнови в основния. Ние можем да наричаме Foo от цяло китка на различни места. Откъде да знаем, къде да се връщат? Е, ние трябва да се съхранява, че някъде. 

Така че някъде точно около тук, ние съхраняваме където трябва да се върнем още веднъж Foo възвръщаемост. И това е адреса на подателя. Е, как противник може да се възползва за това е фактът, че Този буфер се съхранява в, нека да се каже, точно тук е в. Така че ние имаме 12 байта за хим. Това е в. И това е комин пръстен на Foo. Така че, ако злонамерен потребител влиза повече байтове, отколкото 12 или те въведете командата аргумент линия, която е по-дълъг от 12 герои, а след това ние ще прелее този буфер. 

Ние можем да продължим. И в един момент, отиваме далеч достатъчно, че да започнем презаписване на този обратен адрес. Така че след като ние презапишете адреса на подателя, това означава, че когато Foo възвръщаемост, ние сме се завръщат в накъдето злонамерен потребител се обяснява това с каквото и стойност е влязла, независимо с какви символи въведени от потребителя. И така, ако злонамерен потребител се особено умен, той може да има този върнете към някъде в printDef функция или някъде в изчистване функция, просто навсякъде произволно. 

Но още по-умно е това, което, ако той има потребителят се върне към точно тук. И след това да започнете да изпълнява тези като реда код. Така че в този момент, потребителят може да влезе каквото си иска в този регион. И той има пълен контрол над вашата програма. Въпроси за това? Така че следващият въпрос е завършено новото привеждане на Foo по такъв начин, че вече не е уязвим. 

Така че има няколко начина ти би могъл да направи това. Ние все още имаме само в е с дължина 12. Може да са се променили тази като част от вашето решение. Ние също така добави, проверка, за да се направи сигурен бар не е нищожна. Въпреки, че не се нуждае от че за пълен кредит. Така че ние сме първата проверка на низ дължина на бар. Ако тя е по-голяма от 12, тогава всъщност не направи копие. Така че това е един от начините за това определяне. 

Друг начин за определяне е вместо като в само с дължина 12, трябва да го да бъде с дължина strlen (бар). Друг начин за определяне е всъщност просто се върнете. Така че, ако току-що се отърва от всички това, ако току-що изтрити всички реда код, ще са придобили пълен кредит, тъй като тази функция всъщност не се постигне нищо. Това е копиране на командния ред аргумент в някакъв масив в неин местен стека рамка. И тогава нещо се завръща. И каквото и да е талантлив е отишъл. Така че завръщането е също достатъчно начин за получаване на пълен кредит. 

DAVID J. Malan: Не е съвсем в духа на въпроса, но приемлив според спец. все пак. 

ROB BOWDEN: Въпроси за някой от това? Единственото нещо, което най-малко необходимо, за да са съставяне код. Така че, въпреки че технически не сте уязвими, ако вашият код не събира, ние не приемам това. Няма въпроси? OK. 

DAVID J. Malan: Искате ли да се каже, това заглавие? 

ROB BOWDEN: Не. 

DAVID J. Malan: Така че в този един, този е или добра новина или лоша новина. Това е буквално същия проблем като на първата викторина. И това е почти същото проблем, тъй като pset1. Но това е умишлено опростена, за да бъде опростена пирамида, която може да бъде решен с малко опростена итерация. И наистина, това, което сме били получаване на тук не е толкова много на логиката, защото най-вероятно, от този момент, вие сте по-удобно, отколкото са били в една седмица с вериги за или защо примки, но наистина да дразни, освен че сте малко удобно с представа, че PHP не е само за това, което програмиране. Тя може действително да се използва като език да пишат програми командния ред. 

И наистина, това е, което ние се опитвахме да привлека вниманието ви към. Това е програма за команден ред PHP. Така C код тук, докато правилното в C не коригира за PHP. Но код наистина е същото. Ако сравните решения за Quiz 0 срещу Quiz 1, вие ще откриете, че това е почти идентичен, с изключение на някои доларови знаци, както и за отсъствие на тип данни. По-специално, ако можем да разгледаме тук, ще видите, че ние обхождане, в това случай, от 1 до до 7. 

Бихме могли да го направи 0 индекс. Но понякога, мисля, че това е просто умствено по-лесно да се мисли за неща, 1-7. Ако искате един блок, а след това два блокове, след това три, тогава точка, точка, точка, седем. Ние сме J се инициализира с 1 и след това се разчита на до аз. И тук всичко е иначе идентична. Но заслужават внимание са няколко неща. Ние ви даваме тези две линии, този първи един, goofily име като вертеп за остър взрив. И това само определя пътя, по папка, в която програмата може да бъде установено, че искате да използвате да тълкува този файл. 

И тогава линията след това, на разбира се, означава, въведете PHP режим. И линията на самото дъно означава излизане PHP режим. И това работи, като цяло, с тълкува езици. Това е нещо досадно, ако ти напиша програма във файл, наречен foo.php. И тогава вашите потребители имат само Спомням си, OK, за да стартирате тази програма, аз трябва да напишете "PHP пространство foo.php." Вид досадно, ако не друго. И тя също така разкрива, че вашата програма е написан на PHP, който не е всичко че светещата за потребителя. 

Така че можете да премахнете. PHP напълно припомнят от лекция. И всъщност можете да направите. / Foo ако сте го chmodded, като я прави изпълним. Така коригирате а + х Foo би направил това. И ако прибавим и отиде по дяволите тук. Но наистина, проблемът ставаше в отпечатване на нещо подобно. Не HTML, не C-код със сигурност, само някои PHP. Така че след това се върна в Milo проблем 25. И в 25, които са ти дадени по-долу скелет код, който е бил доста проста уеб страница. И сочна част HTML-мъдър е намалял тук, където имаме вътре в тялото форма, която има уникален ID на входа вътрешността на който е два входа, един с идея за име, една с една идея на бутон. 

Първият е вид текст, на вторият тип изпратете. И така, ние ви даде, всъщност, по- съставки, отколкото са необходими, просто така момчета са имали възможности, с които за решаване на този проблем. Вие не трябва строго всички тези идентификатори. Но тя ви позволява да решите това по различни начини. И нагоре към върха, забележите, че Целта е да се предизвика прозорец като този - Здравейте, Майло! - да изскочи в браузъра с използване на супер простите, ако не грозен, функция за известяване. И така, в крайна сметка, това се свежда концептуално по някакъв начин да слушам за подаване на формуляра от страна на клиента , А не от страната на сървъра, някак си в отговор на това твърдение от вземете стойността, която потребителят въвели в областта на името, и след това я излагат в тялото на сигнал. 

Така че един от начините, можете да направите това е с Jquery, което изглежда малко синтактично сложен на първо време. Можете да направите това с чиста DOM код - document.getelement от ID. Но нека да погледнем в тази версия. Имам няколко важен линии на първо място. Така че едно, ние имаме тази линия, която е идентично с това, което може би сте виждали , аз вярвам, form2.html от клас в 9 седмица. И това е просто казвам, изпълнява следния код, когато документът е готов. Това е важно, само защото HTML страници се четат отгоре отдолу, отляво на дясно. 

И затова, ако се опитате да направите нещо в кода си тук, за да някои DOM елемент, някои HTML тагове, че е надолу тук, вие го правите твърде скоро, защото това не е дори прочетено в паметта. Така че, като казва това document.ready линия, което казваме, тук е някакъв код, браузър. Но не се изпълни това, докато цялата документ е готово, че е DOM съществува дърво в паметта. Това е по-малко ясна, ако синтактично на малко по-различно, когато казвам, вземете на HTML елемент, чийто уникален идентификатор е входове. Това е, което етикет хеш означава, уникалният идентификатор. И тогава аз се обаждам. Представя. 

So. Представя тук е функция, в противен случай известен като метод, който е във вътрешността на обекта от лявата страна страна там, че аз не се подчертае. Така че, ако мислите, че на входа като обект в паметта - и наистина е така. Това е възел в едно дърво - . Представи средства, когато с тази форма е подадено това ID, изпълнява следния код. Не ме интересува какво е името на функция е, че аз съм изпълнение. Така че тук аз съм с помощта, както и преди, какво е извикахме функцията ламбда или анонимна функция. Това не е всичко интелектуално интересно, различно от това няма име, което е добре, ако сте само никога няма да го наричат ​​веднъж. И вътре има Аз всъщност се справят подаване на формуляра. За първи път декларира променлива нарича стойност. И тогава какъв е ефектът от това подчерта част тук сега? Какво означава, че правя по- високо ниво за мен? 

ПУБЛИКАТА: Той получава стойността, която Потребителят все още не е направил в HTML-долу. Той получава това име и след това установи стойността на него. 

DAVID J. Malan: Точно така. Тя грабва възел, чийто уникален идентификатор е името. Той получава стойността в него, които е, вероятно, това, което потребителят него или себе си написали. И след това го съхранява, че в променлива, наречена стойност. Като настрана, бихте могли да имат също направи това малко по-различно. Напълно приемливо, като направите нещо лъжа VAR стойност получава document.getElementById. И това е причината, че е малко досадно да не се използва JQuery. "Име" стойност.. Така че напълно приемливо. Различни начини да направите това. Jquery просто има тенденция да бъде малко по-кратка и Определено по-популярни сред програмистите. 

Сега, аз правя малко на здравия разум проверите, защото в проблема декларация ние изрично каза, ако потребител все още не е въвел своето име, не показват сигнали за тревога. Но можете да проверите за това, като просто проверка за празен низ за в кавички, ако има всъщност нищо там. Но ако това не е равно на кавички, Искам да се обадя на сигнали. И интересното тук е, че ние използваме оператора на плюс, който какво прави в JavaScript? Свързвам. Така че това е като PHPs точка оператор. Същата идея, малко по-различен синтаксис. И аз съм просто създаване на низа, че те видях на екрана изстрел - Здравейте, така и така. 

И тогава най-малката подробност е това. Защо ми е връщане фалшиви вътре на тази анонимна функция? 

ПУБЛИКАТА: Няма никаква стойност. Можете да я тури във форма. Тя просто казва, ако стойността не е равна на празно, след това го направи. Имаше празно в това твърдение. 

DAVID J. Malan: OK. Все пак внимавайте. Няма никой друг тук. И това връщане невярно е извън на, ако условията. Така че това подчерта линия, връщане фалшиви, изпълнява, без значение какво, когато формулярът е подаден. Какво означава връщане фалшиви вътре в този манипулатор на събитие, както се нарича, въпросното събитие е представянето? 

ПУБЛИКАТА: Защото се случва само веднъж. 

DAVID J. Malan: Само се случва веднъж. Не съвсем. Да? 

ПУБЛИКАТА: Тя не позволява формата от подаване на поведението по подразбиране, което би направило презаредите страницата. 

DAVID J. Malan: Точно така. Така че аз съм претоварване терминът представя тук, защото аз казвам, формата е да бъде представена. Но, както ви предлагам, тя всъщност не е е подадено в истинския HTTP начин. Когато кликнете върху Изпращане, защото на нашата onSubmit манипулатор, ние сме прихващане че формулярът за участие, така да се каже. Ние тогава вършим нещо с JavaScript код. Но аз умишлено връщането невярна, защото това, което не искам да се случи част от секундата по-късно е за цялото формата себе си да бъде представен в интернет сървър с двойки ключови стойности, като промените адреса да бъде нещо като Q = котки или каквото и да е направил, например, в клас. Аз не искам това да се случи, защото не съществува на сървъра слушане за това Формуляр за участие. Това е чисто направено в JavaScript код. И това е защо аз не дори да има действие атрибут на формата ми, защото аз нямам намерение за това, за да някога отидете до сървъра. 

Така че, това е да бъде представена. Но ние сме прихващане тази форма подаване и предотвратяване на по подразбиране поведение, което е действително извървим целия път до сървъра. 

ПУБЛИКАТА: Така да бъдат пазени от страна на клиента. 

DAVID J. Malan: Поддържане то от страна на клиента. Точно така. Следващата ми беше ох MySQL. 

ROB BOWDEN: OK. Така че този първи въпрос е по принцип груб за хората. Въпреки, че по-късните отидоха по-добри. Така че трябваше да избирам правилните данни видове за двете колони. И двете от тях имат някаква неща за тях, които направи избор трудно. Така Int не е валиден въведете за брой. Причината е 12-цифрен акаунт брой, едно цяло число не е достатъчно голям, за да съхраните общите цифри. Така валиден избор би бил голям INT, ако се случи да се знае това. Друг избор би могъл да бъде поле Чар дължина 12. Така че нито един от тези, които биха работили. Int не би. 

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

DAVID J. Malan: Cash. 

ROB BOWDEN: Cash. Ние използвахме десетични за съхраняване на сумата на пари в брой, които потребителят разполага в момента. Така че причината да се направи това е защото, не забравяйте, плавници. Има плаваща запетая в точност. Тя не може точно да се съхранява парите ценности като искаме тук. Така десетични е в състояние точно да магазин нещо, да речем, два знака след десетичната запетая. Ето защо баланс, ние го искаме да бъде десетични и не плува. 

DAVID J. Malan: И също така, също, въпреки че той може да е бил умен в друга контекст, за да мислят, може би това е шанс за вътр. Аз просто ще следим нещата с пари. Защото ние изрично показа по подразбиране стойност е 100.00, че означава, че той може да бъде само едно цяло число. И още един финес прекалено с номер беше, че тя не е била предназначена да бъде подвеждащ въпрос. Но припомни, че едно цяло число в MySQL, като в C, най-малко в уред, е 32-битова. И въпреки, че ние не очакваме да знам точно колко цифри, които средства, си спомням, че най-голям брой Вие може да представлява потенциално с 32-битово число е приблизително какво? 

Какъв номер да казваме винаги? От 2 до 32, което е това, приблизително? Не е нужно да се знае точно. Но горе-долу е полезно в живота. Това е приблизително 4 млрд. евро. Така че ние сме каза, че няколко пъти. Знам, че мога да кажа, че няколко пъти. И това е приблизително 4 млрд. евро. И това е едно добро правило на палеца да се знае. Ако имате 8 бита, 256 е магическо число. Ако имате 32 бита, 4 милиарда даде или отнеме. Така че, ако просто напишете надолу 4 млрд. евро, ще видите, че това е по-малко цифри, отколкото 12, което означава, че явно не е достатъчно изразителност да заснемете 12-цифрен номер на сметка. 

ROB BOWDEN: OK. Така че на останалите отидоха по-добри. Така че предполагам, че банката налага 20 $ месечно Такса поддръжка на всички сметки. С какво SQL заявка може банката приспадане на $ 20 от всеки брой, дори ако тя води до някои отрицателни салда? Така че основно, има четири Основните видове заявки - вмъкнете, изберете, обновяване и изтриване. Така че това, което си мислим, че сме Ще използвам тук? Update. 

Така че нека хвърлим един поглед. Така че тук ние сме актуализиране. Какво маса сме актуализиране на сметки? Така актуализиране сметки. И тогава синтаксиса казва, какво в сметки сме актуализиране? Е, ние сме настройка на баланса равен на текущата стойност на баланса минус 20. Така че това ще актуализира всички редове на сметките, изваждане Двадесет милиона щатски долара от баланса. 

DAVID J. Malan: Често срещана грешка тук, въпреки че понякога го простил, беше да се действително да има PHP код тук извикване на функцията заявка или пускането кавички около всичко, което не трябва да бъде там. 

ROB BOWDEN: Не забравяйте, че MySQL е отделен език от PHP. Ние се случи да се пише MySQL в PHP. И PHP след това да го изпратите над към MySQL сървъра. Но не е нужно PHP, за да се комуникират с MySQL сървър. 

DAVID J. Malan: Точно така. Така че без променливи с доларови знаци трябва да бъде в този контекст. Той може просто да направите всичко по математика в самата база данни. 

ROB BOWDEN: OK. Така че следващия един. Това ли е следващата? Да. Така че с това, което SQL заявка може банката изтегли номерата на сметките на неговата най-богатите клиенти, тези, с баланси по-големи от 1000? Така коя от четирите основни вида отиваме да искам тук? Изберете. Така че ние искаме да изберете. Какво искаме да изберете? Какво колона искаме да изберете? Ние специално ще искате , за да изберете номер. Но ако ти каза, звезда, ние Също така се приема, че. 

Така че изберете номер от какво маса? Accounts. И след това състоянието, което искаме? Когато баланс по-голямо от 1000. Ние също приема по-голяма от или равен. Последно едно. С какво SQL заявка може банката близо, т.е., да изтриете всеки има предвид, че има баланс от $ 0? Така че кой от четиримата сме ще искате да използвате? Изтрий. Така че синтаксиса за това? Изтрий от какво маса? Accounts. И тогава условието на която ние искаме да изтриете - където баланс се равнява на нула. Така изтриете всички редове от сметки когато балансът е нула. Въпросите за всеки от тях? Искате ли да се редят на опашки? 

DAVID J. Malan: Queue ръководство. Така че в този един, ние ви даде малко по- запознати структура, която ние проучени малко в клас заедно на structs, което е данни свързани с дух структура. Разликата макар и с опашка е че ние трябваше по някакъв начин да си спомня кой беше най-отпред на опашката, в голяма част, така че бихме могли да направим повече ефективно използване на паметта, най-малко ако сме използвали масив. 

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

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

Така че по някакъв начин трябва да се следи за размер на нея, или наистина в края на това и след това, когато началото на това е. Така че ние предлагаме, че вие ​​декларирате една такава опашка, призвание той Q, просто една буква. След това ние предлагаме, че отпред е инициализира с нула и че размерът да се инициализира с нула. 

Така че точно сега, няма нищо във вътрешността на тази опашка. И ние ви молим да попълните изпълнение на Enqueue долу в такъв начин, че функцията добавя п да края на Q и след това се връща истина. Но ако р е пълен или отрицателно, функция трябва вместо връщане фалшиви. И ви дадохме няколко на предположения. Но те не са наистина функционално уместно, съществува само, че булев, защото, технически, булев не съществува в C, освен ако не се включи определен файл заглавието. Така че просто се уверете, че има бяха не е този трик въпрос вид на нещо. 

Така Enqueue, ние предложихме в извадката решения за изпълнение, както следва. One, ние първо проверете лекотата, на ниско висящите плодове. Ако опашката е пълна или номера, който Вие се опитвате да вмъкнете е по-малко от нула, което се казва в спецификация на проблема трябва не се допуска, защото ние само искаме неотрицателни стойности, тогава трябва да се просто връщане фалшиви веднага. Така че някои сравнително лесно проверка за грешки. Ако все пак искате да се добави, че действителната число, което трябваше да направя малко на мислене тук. И това е мястото, където това е малко досадно психически, защото трябва да се разбера как да се справят с обгръщащ. 

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

Така че ние можем да го запази относително проста. Ние трябва да помним, че ние просто прибавя Int към опашката. И тогава ние просто връщане вярно. Междувременно, в dequeue, попитахме можете да направите следното. Го приложи по такъв начин, че тя dequeues, че е премахва и се връща, на INT в предната част на опашката. За да премахнете ПНА, е достатъчно да го забравя. Не е необходимо да подменяте нейното малко. Така че тя все още е в действителност там. Точно като на данни на твърдия диск, ние просто се игнорира факта, че това е вече там. И ако р е празен, ние трябва да вместо да се върне отрицателен 1. Така че това се чувства произволно. Защо се върне отрицателен 1 вместо фалшива? Да. 

ПУБЛИКАТА: Q е съхраняване положителни стойности. Тъй като вие се съхранява само положителни стойности в Q, отрицателен е грешка. 

DAVID J. Malan: Добре, вярно. Така че, тъй като ние сме само съхраняване на положителна стойности или нула, а след това е добре да се върне отрицателна стойност като часовой стойност, специален символ. Но ти пренаписване на историята там, поради причината, че сме само връщане на не-отрицателни стойности е така, защото ние искаме да имат стойност Sentinel. Така че, по-конкретно, защо просто не връщане фалшиви в случаи на грешки? Да. 

Публика: Ти се провали да връща цяло число. 

DAVID J. Malan: Точно така. И това е мястото, където C получава доста ограничаващо. Ако искаш да кажеш, че отиваш за да се върнете едно цяло число, имаш за да се върнете на вътр. Вие не можете да получите фантазия и да започне връщане един булев или с плаваща запетая или канап или нещо подобно. Сега, междувременно, JavaScript и PHP и някои други езици, може, в действителност, са ви връщат различен видове ценности. И действително, че може да бъде полезно, когато бихте могли да се върнете положителни цели числа, нули, отрицателни цели числа, или невярна или нула дори и да означава грешка. Но ние не разполагат с тази гъвкавост в C. 

Така че с dequeue, това, което ние предлагам да направите, е - 

ROB BOWDEN: Можете да се върнете фалшива. Това е просто, че е фалшива хеш дефинира фалшива до нула. Така че, ако се върне фалшиви, сте връщане нула. А нулата е нещо валидно в нашата опашка, докато негативният един не е, ако невярно случи да бъде отрицателен 1. Но вие дори не трябва да Трябва да знаете, че. 

DAVID J. Malan: Това е Затова не исках да го кажа. 

ROB BOWDEN: Но това не е вярно че не може да се върне фалшиви. 

DAVID J. Malan: Разбира се. Така dequeue, забележете, ние приемаме анулира като аргумент му. И това е така, защото ние не сме минаваща нищо инча Ние просто искаме да се премахне елементът в предната част на опашката. И така, как бихме могли да го направим? Ами, на първо място, нека да направим това бърза проверка здрав разум. Ако размерът на опашката е 0, има никаква работа да се свърши. Връщане отрицателен 1. Готово. Така че това е на няколко линии на моята програма. Така само четири линии остават. 

Така че тук аз решавам да декрементира на размера. И ефективно намаляващи размера означава, че аз съм се забравя нещо е там. Но също така трябва да се актуализира, когато е предната част на цифрите са. Така че, за да направи това, имам нужда да направите две неща. Аз първо трябва да се помни това, което броят е в предната част на опашката, защото имам нужда да се върне това нещо. Така че аз не искам да случайно забравите за него и след това да го замените. Отивам да си спомня в едно цяло число. 

И сега, аз искам да се актуализира q.front да бъде q.front +1. Така че, ако това е първият човек в линия, сега, аз искам да направя плюс 1 до точка в следващия човек в линия. Но аз трябва да се справиш с това обгръщащ. И ако капацитетът е глобална константа, че няма да ми позволи да се уверите, като I точка до последния човек в линия, операцията по модул ще донесе ме върна почти до нула в предната част на опашката. И който обработва Маншетът тук. И след това да продължа да се върнат п. 

Сега, строго погледнато, не съм трябва да декларират п. Аз не трябва да го вземете и да го съхранява временно, тъй като стойността е все още там. Така че аз може просто да направи правилното аритметиката да върне бившия шеф на опашката. Но аз просто чувствах, че това е по-ясно действително да вземете ПНА, да я тури в N, и след това се връща, че заради яснота, но не е строго необходимо. 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 п. Имаме нужда от показалеца на лявата детето и показалеца на дясната детето. Така тя ще изглежда по този начин. И това всъщност ще изглежда, преди когато съм на двойно-свързан Списък с неща, така известие - Ще трябва да преминете през цялото обратния път надолу до проблем 11. 

Така че забележите изглежда идентичен с този, освен ние просто се случи да се обадя тези различни имена. Ние все още имаме цяло число стойност и две насоки. Това е просто, че вместо за лечение на указатели като сочеше към следващото нещо и предишния нещо, ние сме лечение стрелките, за да сочат към лявата дете и дясно дете. OK. Така че това е нашата структура възел. И сега, единствената функция трябва да приведе в действие за това е траверс, който ние искаме да отидем на дърво, отпечатването ценностите на дървото в ред. 

Така че търсите тук, ние ще искате да отпечатате от 20, 34, 36, 52, 59 и 106. Как можем да постигнем това? Така че това е доста сходен. Ако сте видели през последната изпита проблема че искате да отпечатате цялото дърво със запетаи между всичко, това беше всъщност дори лесно от това. Така че тук е решението. Това е значително по-лесно ако ти го направи рекурсивно. Аз не знам дали някой се опитва да го направя итеративно. 

Но първо, ние имаме нашата база случай. Какво става, ако коренът е нула? Тогава ние просто ще се върне. Ние не искаме да отпечатате нещо. Иначе отиваме да прекосяват рекурсивно надолу. Печат на цялата лява поддърво. Така отпечатате всичко по-малко от сегашната си стойност. И тогава аз отивам да си отпечатате. И тогава аз ще самоизвиква надолу ми Цялата полето поддърво, така че всичко по-голяма от моята стойност. И това се случва, за да отпечатате всичко в ред. Въпроси за това как това всъщност постига това? 

ПУБЛИКАТА: Аз имам един въпрос на [недоловим]. 

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

Така че, имайки предвид, че това може да печата 20, 34, и другият може да печата 52, 59, 108, всичко, което трябва да бъде в състояние да направите, е печат бъдем себе си в средата на това. Така отпечатате всичко пред нас. Печат бъдем себе си, така че текущата възел печат 36, редовен ФОРМАТ, а след това отпечатате всичко след нас. 

DAVID J. Malan: Това е мястото, където рекурсия става наистина красива. Това е този невероятен скок на вярата, където , което правите най-малката малко работа. И тогава нека някой друг да свърши останалото. И че някой друг е, по ирония на съдбата, ти. Така че за сериозни сладки точки, ако превъртите нагоре по въпросите - 

ROB BOWDEN: На въпросите? 

DAVID J. Malan: И малко по-надолу, за да цифрите, Някой знае ли къде тези числа идват от? 

ROB BOWDEN: Имам буквално никаква представа. 

DAVID J. Malan: Те се появяват цялата викторина. 

ПУБЛИКАТА: същите номера са те? 

DAVID J. Malan: Тези числа. Малко великденско яйце. Така че за тези от вас, гледане онлайн на у дома, ако можете да ни кажете по електронната поща на heads@CS50.net какво значимостта на тези повтарящи се шест числа са цялата Quiz 1, ние ще ви потопи с невероятно внимание към финала лекция и стрес топка. Nice, коварен. 

ROB Боудън: Някакви последни въпроси за нищо на теста?