>> DAVID Malan: Добре.
Добре дошли отново в CS50.
Това е началото на 8-та седмица.
И припомни, че проблемът набор пет приключи с малко по-голямо предизвикателство.
Така че стига да върна всичко на вашия преподаване стипендианти и фотографии СО
във файла card.raw, имате право до сега, че всички тези хора, и
един щастливец победител ще си тръгнете с една от тези неща, скок движение
устройство, което можете да използвате за окончателно проекти, например.
>> Това, всяка година, води до малко зловещо.
И това, което мислех, че ще направите, е акция с вас някои от бележките, които имат
отиде назад и напред над персонала списък на късно.
Например едва снощи, цитат във файловите, от един от персонала
членове, "Просто имах студент чук на вратата ми за да направите снимка с мен.
Stalkers, казвам ти. "Започна, доста описателна и след това се преместихме
към, около час по-късно, "Имах студент ме чака след точка
и трябваше всички наши имена и снимки относно някои листа хартия. "Добре.
Така организиран, но не всичко, което страховито все още.
>> След това, "Аз бях извън града този уикенд, и когато се върнах, имаше един в
мой
спалня. "[СМЯХ]
DAVID Malan: Next цитат от персонала член, "студент дойде в къщата ми в
Somerville в 4 часа тази сутрин. "Next персонал, "Трябва да ми хотел в San
Francisco и студент чакаше ми в лоби с три огледално-рефлексни фотоапарати. "
Тип на камерата.
"Аз не съм дори и на персонала този семестър, но един студент с взлом в къщата ми тази
сутрин и се записва цялата работа Стъкло с Google. "И тогава на последно място,
"Най-малко 12 души бяха нетърпение очакване за мен, когато излязох от моя
лимузината, а след това
Събудих се. "Добре.
Така сред снимките, тъй като може да спомняте, са този човек тук, който ви
може да знае като Milo Banana, който живее с Лорън Carvalho, главата ни
преподаване сътрудник.
Мило, Мило, ела тук момче.
Мило.
Гледай ти, той е облечен Google Glass, така че ние ще ви покажем всичко това след.
Така че това е Milo, ако искате да се снимат с него след това.
Ако искате да се грижа към публиката там.
OK.
Това е добре кадри.
Е, Milo Banana.
О, не прави това.
>> [СМЯХ]
>> OK.
Така че една дума тогава за това, което предстои, тъй като ние започваме да прехода,
тази седмица специално от С в среда командния ред за PHP и
JavaScript и SQL и HTML и CSS в уеб-базирана среда, ще бъде
оборудване на вас с всички повече знания за
потенциалните крайни проекти.
Към този момент, курсът има традиция за провеждане на семинари, които
са на тангенциални теми в дисциплината.
Много, свързани с програмирането и да App развитие и така нататък, но
не е задължително да изследват от собствена хода на учебната програма.
>> Така че, ако може да се интересуват един или повече от семинари за тази година,
се регистрира в cs50.net/seminar.
Има големи семинари в cs50.net/seminars.
И на списък досега за тази година са невероятни Web Apps, с Руби на
Релси, която е алтернатива език PHP.
Компютърна лингвистика.
Въведение в IOS, който е платформа, която се използва за iPhone и
IPAD развитие.
JavaScript за Apps Web, ще разгледаме това, но в този семинар, ще се отвори
по-подробно.
>> Leap Motion, така че ние действително ще има някои на нашите приятели от Leap Motion,
самата компания, присъединете се към нас.
Утре, в действителност, да се осигури практически на семинар, ако
от интерес за вас.
Meteor.js, алтернативна техника за използване на JavaScript не в браузъра,
но на предприятието на сървъра.
Node.js, което е много в този дух, както добре.
Елегантен Android Design.
Android е много популярна алтернатива до IOS и Windows Phone
и други мобилни платформи.
И Security Web активна отбрана.
>> Така че в действителност, ако искате да се включат в тази, нека
обърнете внимание на това.
Ние сме много щастливи да се каже, че Приятелите ни Leap
Предложение, което е стартиране -
това устройство наистина просто дойде от преди няколко месеца -
любезно дарени 30 такива устройства на класа за колкото се може повече ученици, ако
искате да се заемат на хардуер към края семестър и да я използва за
действително окончателен проект.
Те поддържат няколко езика.
Никой от тях С, никой от тях не PHP, така че реализират един или повече от тези семинари
може да се окаже от значение.
И всички те ще бъдат заснети в случай, че не сте в състояние
да присъства лично.
Графикът се обявява чрез приятел, тъй като ние се втвърди стаи.
>> И накрая, ако отидете на projects.cs.50.net, това е сайт
ние поддържаме, че всяка година каним хора от общността, факултет,
отдели, служители и двете в извън CS50 да
предложат идеи за проекти.
Неща, които представляват интерес за студентски групи.
Неща, които представляват интерес за службите.
Така се обръщат там, ако се борите с несигурност по отношение на това, което
себе си би искал да се справи.
>> Така че последният път, когато въведе може би по-сложна структура от данни, отколкото ни се
виждал в последните седмици.
Бихме били употребата на масиви доста щастливо като полезно, ако
опростена структура на данните.
След това ние въведохме тези, които разбира се са свързани списъци.
И това, което е един от мотивите за въвеждане на тази структура от данни?
Да?
Какво е това?
>> Публика: Dynamic размер.
>> DAVID Malan: Dynamic размер.
Така докато в масив, трябва да знаете размера си предварително, когато
да го разпредели.
В свързан списък, не трябва Трябва да знаете, че.
Можете просто изчистване, или по-общо, предоставяне на допълнителна
възел, така да се каже, всеки път, когато искате да вмъкнете повече данни.
И възел е не предварително определено значение.
Това е просто един общ термин, описващ някакъв вид контейнер, който сме
използване в нашата структура от данни за съхраняване някои точка на интерес, което в този
случай се случи да бъде цели числа.
>> Но винаги има компромис.
Така получаваме динамични размери на данни структура, но каква цена плащаме?
Какво е в неблагоприятна посока на свързани списъци?
Да?
>> Публика: изисква повече памет.
>> DAVID Malan: Тя изисква по- памет, как по-точно?
>> Публиката: [недоловим].
>> DAVID Malan: Точно така.
Така че сега ние сме указатели предприемането допълнителна памет, че ние по-рано
не е необходимо, тъй като предимство на масив, разбира се, е, че
всичко е тези, обратно да Насрещен, които
ви дава свободен достъп.
Защото само с помощта на квадратна скоба нотация, или повече технически показалеца
аритметика, много просто допълнение, можете да получите достъп всеки
елементи в константно време.
И всъщност, това е нещо намекваше друга цена, която ние плащаме с
свързан списък.
>> Какво се случва с времето на работа нещо като търсене, ако искам да
намери някаква стойност и вътре на свързан списък?
Какво ми времето за работа стане?
Big O от п.
Ако това е сортирано да?
Какво става, ако структурата на данните е подредени?
Мога ли да направя по-добре от голяма О п за търсене?
Не, защото в най-лошия случай това може много добре да се сортира, но броят
, което търсите може да е голям.
Тя може да бъде броят 100, които може да се случи да бъде всичко
Между другото в края.
И тъй като можете да получите достъп до свързания списъка в този прилагането от
начин на първото му възел, ти си все още вид на късмет.
Трябва да се пресече всичко от началото до края, за да открие
че голяма стойност, като 100.
Или за да се определи дали това е дори не е там.
>> Така че не можем да направим това, което алгоритъм за данни, структура, която изглежда по този начин?
Не можем да направим двоично търсене, защото двоично търсене изисква, че имаме
произволен достъп.
Можем просто да скочи от място на място, без да се налага да следват
тези трохи под формата на всички тези насоки.
>> Сега, как ние прилагаме това?
Е, ако се върнем към екрана тук, ако можем бързо reimplement тези данни
структура -
почерка ми не е всичко, че страхотно тук, но ние ще се опитаме.
Така typedef структура, и какво съм искам да се обадя на това нещо тук?
Node.
Така че ще ни започна.
И сега, какво трябва да бъде вътре в структурата на данните за тази поотделно
свързан списък?
Колко полета?
>> Така две.
Един от тях е доста лесно.
Така Int п.
И ние може да се нарече н всичко, което искате, но тя трябва да бъде едно цяло число, ако сме
прилагане на свързан списък за цели числа.
И сега какво прави втора областта трябва да бъде?
Struct възел *.
Така че, ако го направя структура възел *, а след това може да наричат ​​това също каквото си искам,
но само за да бъде ясно, ще се обадя то следващата, тъй като ние сме били прави.
И тогава аз ще затворя фигурни скоби.
>> И сега, както последния път, Сложих възел тук.
Но ако аз съм обявява това е като възел, защо се притеснява толкова
многословно тук, като обявил, структура възел * След това, за разлика
просто възел * следващия?
Да?
>> Публиката: [недоловим].
>> DAVID Malan: Точно така.
Точно така.
Защото C наистина ще ви отведе буквално и вижда само определяне на възел
чак дотук, не можеш се отнасят към него тук.
Така че ние имаме този вид превантивна декларация тук, което е несъмнено
по-многословен.
Struct възлова точка, това означава, че сега можем да го достъп
вътрешността на структурата на данните.
>> И като настрана, защото това е да стане малко по-субективни сега,
звездата технически може да отидете тук, тя може да отидете тук, тя може да
дори да отидете в центъра.
Ние сме приели в стил ръководство за хода, Конвенцията на пускане
звездата в непосредствена близост до данните тип, което в този случай,
би било възел структура.
Но реализират в много учебници и онлайн препратки, може би наистина
Вижте къде се намира от другата страна.
Но просто осъзнават, че така всъщност ще се работят и просто трябва да бъде
съвместими.
>> Добре.
Така че това е нашата декларация на структурата на възел.
Но след това започнах да се занимавам повече сложни неща.
Например, ние решихме да представим нещо като хеш таблица.
Така че тук е хеш таблица с размер М, индексирани от 0 в горния ляв ъгъл на п
минус 1 в долния ляв ъгъл.
Това може да бъде хеш маса за нищо.
Но какви неща си говорим за използване на хеш-таблица за?
Съхраняване на какво?
>> Имена.
Можем да го направим имена като направихме миналия път.
И наистина, можете да съхранявате всичко.
И ще видим отново в PHP и JavaScript.
A хеш таблица е хубаво нещо Swiss Армия нож, който ви позволява да съхранявате
почти каквото искате вътре тя, като се комбинират клавишите със стойности.
Клавиши със стойности.
>> Сега в този прост случай, нашата Ключовете са просто числа.
Ние сме за прилагане на хеш маса като масив.
И така, ключовете са 0, 1, 2, и така нататък.
И така, ние, като хора, реши миналата седмица, че знаете какво, ако сме
Ще Магазин имена, нека просто произволно, но доста разумно,
приемем, че Alice, А името, просто ще бъдат индексирани в 0.
И Боб, име, B, ще бъдат индексирани в 1, и така нататък.
Така че имахме картографиране между входовете, които са струни, и хашиш
места, които са числа.
>> Така че този процес е известен като хеш функция, а вие може наистина
въведе в кода.
Ако исках да се приложи функцията за сегментиране че прави точно това, което ние
току-що описаното от последния път, мога да обяви функция, която използва като
въвеждане например -
и да го направим по този екрана тук.
Ако исках да приложи хеш функция, мога да кажа
нещо като това.
>> Това ще върне вътр.
Това ще се нарича хеш, и това е ще приеме като аргумент на
низ, или можем да бъдем по-правилното сега, и да кажа, Чар *, ще го наричат ​​лидер.
И тогава всички тази функция трябва да се направи, в крайна сметка, се връща Int.
Сега, как го прави, които биха могли не е толкова ясно.
Отивам за прилагане на настоящия без формират за проверка на грешките в момента.
Аз съм просто ще сляпо кажа, върнете каквото е и конзола 0, минус,
да речем, капитал и запетая.
>> Totally счупен.
Това не е добра, защото един, ами ако S е нула?
Лоши неща ще се случат.
Второ, какво ще стане ако първата буква в тази Името не е главна буква?
Това няма да се превърне навън и от двамата.
Може да е малка буква или не писмо на всички.
Така че напълно за подобрение тук но това е основната идея.
>> Това, което е описано като миналата седмица устно само на процеса на нанасяне на Alice
0 и Боб до 1 може да се изрази със сигурност по-formulaically като C
функционират тук.
Наречен отново хашиш, отнема низ като вход, а след това по някакъв начин прави нещо
с това суровини за производството на изход.
Не е за разлика от нашата черна кутия описание че сме отдавна направено.
Не знам как това може да бъде работа под предния капак.
>> За проблема набор шест, едно от предизвикателствата е за вас да решите какво
ще ви хеш функция да бъде?
Какво ще е вътре в тази черна кутия, и вероятно, това ще бъде
малко по-интересно от това, и определено по-податливи на грешка
проверка от този конкретен изпълнение.
>> Но проблеми могат да възникнат, нали?
Ако има структурата на данните, като тази едно, което е един от проблемите,
можете да се сблъскате с течение на времето като поставите все повече и повече имена в
хеш-таблица?
Можете да получите сблъсъци, нали?
Какво става, ако имате Alice и Аарон, двама души, чиито имена случи
да се започне с?
Това повдига въпроса, къде си вкара второто такова име?
>> Е, може би наивно просто го сложи където Боб принадлежи, но след това е Bob
вид прецакани, ако се опитате да въведете името му и следващия
няма място за него.
Така че може да сложи Bob когато Чарли е, и можете да си представите това много бързо
прехвърлени в доста голяма бъркотия.
Нещо линейна в края, където можете Просто трябва да се търсят в цялата работа
търси Алис или Боб или Aaron или Чарли.
>> Така че, вместо ние предложихме, а не само линейно сондиране за открити пространства
и цопване имената там, предлага красиви подход.
A хеш таблица изпълнени още с набор от индекси, но типът на данните
тези индекси сега са указатели.
Указатели към какво?
Указатели към свързани списъци.
>> Тъй като припомнят, че на свързан списък е наистина само указател към възела, и
възел има следващото поле, и че възловата точка има следващото поле, и така нататък.
Така че сега можете да мислите за този масив на от лявата страна на хеш таблица като
което води до свързан списък.
Предимството на което е, ако получите сблъсък между Алис и Аарон,
какво ще правиш с второ такова лице?
Можете просто да го прикачите или си в края, или дори в началото
на този свързан списък.
>> И всъщност, нека просто юфка чрез че само за секунда.
Къде щеше да е най-подходящ?
Ако вмъкнете Алис и тя стига до първото място, а след това се опитвам да
посочете името на Аарон, а има и очевидно сблъсък, трябва да сложа
него в началото на свързан списък?
Това е на първо място, че, или в края?
>> Публиката: [недоловим].
>> DAVID Malan: OK.
Чух, че в началото си.
Защо в началото?
>> Публиката: [недоловим].
>> DAVID Malan: OK.
Това е азбучен, така че е хубаво.
Това е добър имот.
Това ще ми спести малко време потенциално.
Той няма да ме остави да двоично търсене, но може поне да могат да се измъкнат
на една линия, ако осъзнавам, добре, аз съм така миналото са Аарон ще бъде в тази
сортирани свързан списък.
Не е нужно да губя време в търсене по целия път до края.
Така че това е разумно.
Защо иначе може да искате да вмъкнете на сблъсък името на
началото на списъка?
Какво е това?
>> Публиката: [недоловим].
>> DAVID Malan: Тя може да отнеме много време за да стигнем до края на списъка.
И в действителност, по-дълго и по-дълго.
Колкото повече имена, които вмъквате, че Започнете с по-дълго, че
веригата ще получите.
Колкото по-дълго, отколкото свързан Списъкът ще получите.
Значи вие сте наистина само Губите си времето.
Може би вие сте по-добре поддържане постоянно вмъкване време, голяма O на 1,
, като винаги извеждането на сблъсък името на началото на свързан списък,
и да не се притеснявате толкова, за сортиране.
>> Какво е най-добрият отговор?
Не е ясно.
Тя вид зависи от това, което разпределение е, това, което схемата е
от имената, които поставяте.
Това не е задължително очевиден отговор.
Но тук отново е дизайн възможност.
>> Така че ние после погледна това нещо, което наистина е друга голяма възможност
за р-комплект 6.
И осъзнавам, ако не сте го направили, Zamyla се врязва в двете от тях, хеш
таблици и се опитва, по-подробно.
И видео репетиция е вградени в р-набор спекулация.
Това беше Trie -
T-R-I-E. И това, което е интересно за това е, че времето за работа
на търсене на името, като Maxwell Последният път, беше голяма O на какво?
Какво е това?
>> Публика: Броят на буквите.
>> DAVID Malan: Брой букви.
Чух две неща.
Брой на писма и константно време.
Така че нека да отида с това първо.
Броят на буквите.
Е, тази структура от данни, изземване, е като дърво, с родословно дърво, всяка от
чиито възли са съставени от масиви.
И тези масиви са указатели към други такива възли, или други такива
масиви в дървото.
>> Така че, ако искаме да се определи след това дали Максуел е тук, мога да отида
на първия масив, на самия връх на дървото, така наречената корен, горната част на
на Trie и следвайте показалеца m, след това на показалеца, то х,
w, д, л, л.
И тогава, когато виждам някой специален символ, обозначен тук като триъгълник.
В кода ще видите предлагаме ви реализирана като булев, просто казвам да
или не, една дума спира тук.
>> Е, след като сме преминали към M-A-X-W-E-L-L, чувства като седем, може би
осем ако отидем едно миналото, осем стъпки за намирането на Максуел.
Или нека го наречем К. Но припомни последния време, твърди, че ако има
реалистично максимална дължина на думата, като 40-някои по-странни герои, а
Максималната дължина предполага постоянна стойност.
Така че, наистина, да, това е технически голяма O от 8 или 7, или наистина голям O на K. Но
ако има краен горна граница на това, което K може да бъде, това е константа.
И така, това е голяма O от 1 на края на деня.
>> Не и в реалния свят.
Не и когато действително започнете да гледате си часовник като бягане на вашата програма.
Това е абсолютно ще бъде малко по-бавно от наистина постоянно
времето с една стъпка.
Това ще бъде седем-осем стъпки, но все пак това е много, много по-добре
от алгоритъм, като голяма O на N че зависи от размера на това, което е в
структурата на данните.
>> Обърнете внимание на главата тук е, че можете да поставите един милион повече имена в тази
структурата на данните, но колко още стъпки Дали тя ще ни отнеме да се намери
Максуел в този случай?
Няма.
Той е незасегната.
И към днешна дата, не мисля, че сме виждали пример за структурата на данните или
алгоритъм, който е напълно незасегнати от външната
поведение като това.
Но това не може да бъде невероятно.
Това не може да бъде единственото решение за р-комплект
>> И това не е всичко.
Това не е задължително данните структура трябва да гравитират към,
тъй като хеш таблици, компромис.
Каква е цената, която плащате тук?
Memory.
Искам да кажа, това е брутално размера на паметта.
И не мога да си го видя тук, защото автор на тази снимка
Очевидно пресечен всички масиви, и ние не виждаме много A и
B и C и Q и Y е и Z в тези масиви.
Но те са там.
>> Всеки от тези възли е цяла поредица на около 26 или повече байта, всеки от
което представлява писмо.
27 в нашия случай, така че можем да подкрепим апостроф в проблем сет.
Така че това структурата на данните е много, наистина гъста и широка.
И това само може да свърши забавя нещата, или поне да ви струва
много повече пространство.
Но пак, може да се направи сравнения тук.
>> Спомнете си преди време, ние постигнахме много по-вълнуващо за време в сортиране
когато ние използваме обединяването вид, но цената платихме за постигане на п влезте N за сливане
подреди изисква прекарваме по какъв ресурс?
Повече пространство.
Имахме нужда от вторичен масив копирате хората в, точно като
което направихме тук, на сцената.
Така че, отново, няма ясни победителите, но просто субективно дизайн
да се вземат решения.
>> Добре.
Така че какво ще кажеш за това?
Всеки, който признава D-Hall?
OK.
Така че три от нас.
Mather House.
Така че това е за хранене на Mather.
Обзалагам се, всички зали за хранене имат купища тави така.
И това всъщност е представител на нещо, което съм
очевидно вижда вече.
Ние го нарича буквално купчина.
И комин, от гледна точка на вашия паметта на компютъра, е мястото, където отива данни
докато функции са призовани.
>> Например, какви видове на нещата на стека по отношение на
памет оформление говорихме в последните седмици?
Какво е това?
>> Публика: Разговори към функции.
>> DAVID Malan: Съжалявам.
>> Публика: Разговори към функции.
>> DAVID Malan: Разговори към функции, но конкретно, какво има вътре на всяка от
тези рамки?
Какви неща?
Да.
Така локални променливи.
Всеки път, когато имахме нужда някой местен съхранение, като аргумент, или Int I, или Int
температура, или каквото и местната променлива се, ние сме били
пускането, че в стека.
И ние го наричаме купчина, защото на това покритие идея.
Просто вид съвпада с реалността, понятието него.
>> Но се оказва, че купчина може също да се разглежда като структурата на данните, за
алтернатива на масив, който е алтернативен в свързан списък.
Нещо по-интересно концептуално че все още може да бъде
осъществява чрез използване на една от тези неща, но това е различен вид
структурата на данните на подкрепа, наистина, само две операции.
Но можете да добавите красиви функции, отколкото тези.
Но това са основните неща -
натиснете и поп.
>> И идеята с комин е, че ако аз имаме тук, със или без Annenberg
знаейки, поднос от съседната с номер 9 върху него.
Така че просто едно цяло число.
И аз искам да го отложа върху данните структура, която в момента е празна.
Помислете за това на дъното на купчина.
Аз ще настоява този номер девет върху стека, а сега е точно там.
>> Но интересното за комин е, че ако сега искате да бутнете
някаква друга стойност, както и 17, и натисна това върху стека, аз ще направя
единственото нещо, което интуитивно, просто ще за привеждането му точно там, където ние, хората,
биха били склонни да го пуснат, на върха.
Но това, което е интересно сега е, как мога да стигна до 9?
Знаеш ли, аз не без известно усилие.
>> Така че това, което е интересно за комин е, че още при проектирането,
това е данни LIFO структура.
Silly начин да се опише последен влязъл, първи излязъл.
Така последните номер в по това време е на 17.
Така че, ако аз искам да изскочи нещо от на комина, той може да бъде само 17.
Така че има задължителна цел на операции тук, където последния елемент
в трябва да бъде първият един.
Оттук и съкращение, LIFO.
>> Така че, защо може това да е полезно?
Техните контекст, в който искате искате структурата на данните по този начин?
Е, със сигурност това е било полезно вътрешността на компютъра.
Така че операционните системи ясно използвате тази вид на структурата на данните за стакове.
Ще видите също и съща идея когато става въпрос за уеб страници.
Така че тази седмица и следващата седмица и след това, и като започнете прилагането на уеб
страници на език, наречен HTML, можете да всъщност използват структурата на данните като
това, за да се определи дали страница е правилно форматиран.
Защото ние ще видите всички уеб страници следват нещо като йерархия, идентификационен
, която ще се в края на деня, да бъде дървовидна структура, намираща се под капака.
Така че повече за това малко.
>> Но за сега, нека да предложи за момент, как бихме могли да отидат за
представляващи какво комин е?
Позволете ми да предложа да прилагат комин с код, подобен на този.
Така комин ще има вътре в него две неща, масив, наречени подноси,
само за да бъде в съответствие с демо.
И всеки един от елементите в този масив ще бъде Int тип.
И капацитет е вероятно това, което?
Защото аз не съм писал на пълното определение тук.
>> Вероятно това е максималната дължината на масива.
И това вероятно е деклариран с остър определят в началото на файла, някои
вид постоянна, подразбираща се от самият капитализация.
Така че някъде капацитет се определя като максималния възможен размер.
В същото време, в рамките на структурата на данните известен като пакет ще има
да е цяло число само известен просто като размер.
>> Така че ако трябва да представлява това сега картинно, нека предположим, че това
цялата черна кутия представлява стака си.
Вътре е две променливи.
Така че аз отивам да се привлече Първият и размер.
И второто, което ми предстои да изготви като масив.
>> Но само за да пазят нещата подреден, Обикновено аз би желал да обърне масив като
, но това е нещо хубаво ако отговарят на действителността, или
съответства на мисловен модел.
Нека вместо това привлече масив вертикално, което е просто, отново,
художника предаване.
Няма значение какво е се намира под предния капак.
И ние ще кажем, че по подразбиране, капацитет ще бъде три.
Така че това ще бъде място 0, това ще бъде местоположение 1, тази
ще бъде местоположение 2.
>> Ако аз подкупи със стрес топката, би някой искал да излезе и да стартирате
качат тук, само за момент?
OK, видял ръката си пръв.
Хайде нагоре.
Добре.
Така че аз вярвам, че е Steven.
Хайде нагоре.
Добре.
>> Но да предположим, сега сме назад към първоначалното състоянието на света, където I
току-що обявен за комин, и това е ще бъде на капацитет три.
Но размер все още не е определена.
Тави все още не е определена.
Така няколко въпроса първо.
И нека да ви дам микрофон, така че може участват по-активно в тази посока.
>> Така че това, което е вътре в размер в този момент във времето, ако всичко, което са направили, е
обявен за стека с един ред код?
>> STEVEN: Не много.
>> DAVID Malan: OK, не много.
Знаем ли какво е вътре в размер, знаем какво има вътре
на този масив тук?
>> STEVEN: Just случаен код, нали?
Просто -
>> DAVID Malan: Да, аз ще Наричат ​​го кода, но случайна -
>> STEVEN: неща.
>> DAVID Malan: Неща като случайна
>> STEVEN: Bits.
>> DAVID Malan: Bits, нали?
Така боклук стойности, нали?
Така пермутации на 0 и 1 на.
Останки от предишните обичаи на тази памет.
И ние наистина не знам какви стойности са, така че ние обикновено ги въвлече
като въпросителни знаци.
>> Така че първото нещо, което ние сме вероятно ще искам да направя тук -
и нека ми даде тази област в от там на име - тави.
Какво трябва да се предполага инициализира размер, ако искаме да
започнете да използвате това стак?
>> STEVEN: Тава е под 3.
>> DAVID Malan: Така че, OK.
За да бъде ясно, капацитет се декларира навсякъде другаде, три.
И това е, което аз съм използвал да се разпределят на масива.
Размер ще се отнасят до колко тави момента са в стека.
>> STEVEN: нула.
>> DAVID Malan: Така че това трябва да е нула.
Така че продължавайте напред и с всеки пръст, направи нула по размер.
Добре.
Така че сега, това, което е вътре в тази тук, ние не знаем.
Това са наистина само боклук стойности.
Така че може да се направи въпросителни знаци, но нека да се запази борда чисти за сега
защото това няма значение какво има там.
Ние не трябва да се инициализира масив за нищо, защото ако ние знаем, че
размера на стека е нула, Е, не трябва да се гледа нищо в
този масив или иначе в този момент.
>> Така че сега, предполагам, че аз натиснете номер 9 на стека.
Как трябва да се актуализира структурата данни вътре в тази черна кутия?
Какви стойности трябва да се промени?
>> STEVEN: Within -
размера?
>> DAVID Malan: OK.
Размер трябва да стане това?
>> STEVEN: Размер ще бъде един.
>> DAVID Malan: OK.
Така размер трябва да се превърне в един.
Така че можете да направите това по няколко начина.
Нека ви дам, сега си пръст е една гума.
Добре.
Тогава сега пръста си е четка.
Добре.
И сега какво друго трябва да се промени, Очевидно е, че в структурата на данните?
>> STEVEN: Отиваме от дъното до 9.
>> DAVID Malan: 9.
OK, Good.
Така че все още не е от значение какъв е място един или два, защото те са
боклук стойности, но не трябва да се притеснява търси там, защото е размерът
ни казва, че само първият елемент всъщност е законен.
Така че сега бутнете 17 на списъка.
Какво се случва с тази картина?
>> STEVEN: Така размер ще отидете на две.
>> DAVID Malan: OK.
Ти си гумичка -
Извинете.
Ти си една гума.
>> STEVEN: Eraser.
>> DAVID Malan: Ти си четка.
>> STEVEN: Brush.
>> DAVID Malan: OK.
И какво още?
>> STEVEN: И след това -
>> DAVID Malan: Ние избута 17.
>> STEVEN: Ние се придържаме 17 на върха, така че -
>> DAVID Malan: Добре, добре.
>> STEVEN: - да го пуснете надолу.
>> DAVID Malan: Добре.
Става все по-лесно.
Аз няма да ти помогна този път.
Натиснете 22.
>> STEVEN: Готово.
Ставайки гумичка.
Ставам четка.
И тогава аз съм пускането 22.
>> DAVID Malan: 22.
Excellent.
Така че още един път.
Аз съм сега ще наложи на върху купчина 26.
>> STEVEN: Ооо.
О, Боже.
Вие наистина ме хвана неподготвен.
>> DAVID Malan: Не си виж този смешен?
>> STEVEN: Аз не виждам този смешен.
Може ние отново първоначален капацитет?
>> DAVID Malan: Това е добър въпрос.
Така че ние сме нещо като себе си боядисани в ъгъла тук.
Там наистина не е добре в продължение Steven защото сме разпределят този масив
статично, така да се каже, вътре на структурата на данните.
И ние по същество твърди кодирани да бъде с размер три.
Така че ние наистина не може да го преразпредели.
>> Бихме могли, ако се върна в, ние предефинирани тави за показалка, че
ние след това използвайте изчистване на ръка памет.
Защото, ако ние имаме памет от купчината чрез изчистване, ние
може след това да го освободи.
Но преди да го освободи, бихме могли да преразпределят по-голяма парче от паметта,
актуализиране на показалеца, и така нататък.
Но за сега, това е наистина най-доброто което можем да направим.
Натиснете и поп се предполага, че ще трябва да се набележат някои грешки.
>> Така например, нашата изпълнението тласък може да се върне на булев които
преди това се върна вярно, вярно, вярно.
Но за четвърти път, че ще има за връщане фалшиви, например.
Добре.
Много добре направено.
Поздравления.
Вие сте спечелили стреса топката днес.
>> [APPLAUSE]
>> STEVEN: Благодаря ви.
>> DAVID Malan: Благодаря ви.
ОК, така че това не изглежда много по- на крачка напред, нали?
Ние описана тази структура от данни.
Той е бил непреодолим, нали?
Операционни системи харесва.
Очевидно в интернет могат да се възползват от това, и други приложения на едно място.
Но каква глупава ограничение, че сме назад, за да подреди на седмица две граници
където сме фиксиран размер масиви.
>> Така че наистина е имало няколко начините, по които би могла да реши този въпрос.
Бихме могли да разпределя динамично масива, не по трудно кодиране както съм
направено тук, но вместо отново да обявява това, само за да бъде ясно, като
нещо като това.
Int * тави не, решавайки на капацитет, все още.
Но когато се декларират стека другаде в моя код, мога да се обадя след това изчистване,
получите адрес на парче памет, и можех да присвоите
този адрес да тави.
>> И след това, защото това е просто парче памет, можех да продължат да използват площада
скоба нотация по обичайния начин.
Защото пак, има нещо като това функционален еквивалент на масиви и
блокове памет, които идват обратно от изчистване.
Ние можем да се отнасяме един към друг, тъй като използвате показалеца аритметична или
квадратна скоба нотация.
Така че това е един подход.
>> Но как иначе може да се приложи тази същата структура на данните, потенциално?
Така ли е?
Имам чувството, че току-що решила този проблем като преди седмица.
Какво е решението на този проблем че Стивън се блъсна в?
Така че, свързани списъци, нали.
>> Ако проблемът е, че ние сме боядисване себе си в ъгъла чрез разпределяне
предварително твърде малко памет, която ние след това трябва да по някакъв начин се справят с, добре,
Защо просто не се избегне, че издават напълно?
Защо просто не декларират тавите да бъде указател към възела, значи е свързан списък,
и след това просто да разпределят нови възли всеки път, когато Стивън е необходимо да се вмести в
номер в структурата на данните.
>> Така че на снимката ще трябва да се промени.
Тя няма да бъде толкова чист и като просто, колкото само един набор от три цели числа.
Сега тя ще бъде указател към структура, и че структурата ще
имат средно и следващия показалеца.
Това ще доведе направо, че показалеца в друга такава структура да
друга подобна структура.
Така че на снимката всъщност ще получите Месие малко.
И щяхме да стрелките обвързване всичко заедно.
>> Но това е добре, нали, защото сме виждали как се прави това.
И след като се удобно прилагане на нещо като свързан
списък, който ще трябва да направите, ако да изберат да изпълняват хеш таблица с
отделни верижното за р-комплект 6, можете да Използвайте го като градивен елемент, или
съставка, или в Scratch каже, процедура, нещо, което казано,
създава своето собствено парче пъзел , че ще можете да повторна употреба.
Така че компромиси, но възможните решения че всъщност сме виждали преди.
>> Така че доста често, ще видите това всеки година или две, когато Apple пресата
нещо ново, и всички луди хора извън състава на Apple
магазина да купя тяхната пределна ъпгрейд на хардуера.
Казвам това, това е ОК, защото Аз съм един от тези хора.
Така че, какъв вид данни структура може да представлява тази реалност?
>> Ами, нека да го наречем опашката, на ред.
Така че British бих го нарекъл типично опашката така или иначе, така че е хубаво име.
И двете операции, които опашка подкрепя ние ще наричаме Enqueue
работа и dequeue операция , които са сходни по
дух да прокара и поп.
Това е просто нещо различно в Конвенцията, това, което ние се обаждате тях.
Но да Enqueue нещо означава да добавите или го поставете на структурата на данните.
За да dequeue означава да го премахнете.
Но докато комин е данни LIFO структура, а опашката е на първо място в,
първо от структурата на данните.
>> Ако вие сте първият човек на опашката, ще бъде първият човек, за да получите
от линия и си купите ново устройство.
Представете си колко разстроен тези хора би било ако Apple използва вместо комин, за
Така например, за прилагане на бране на новата си играчка.
Така че опашки има смисъл, разбира се, и можем да мислим за всички видове
приложения, вероятно, за опашки, особено когато искате справедливост.
Е, как може ние прилагаме тези като структурата на данните?
>> Е, аз предлагам да можем да Трябва да го направя по този начин.
Така че аз ще вече имат номера.
Така че ние ще продължаваме да го прости и не непременно говорим от гледна точка на тави.
Само номера, че хората от намерила.
Капацитет ще отново определи Общият брой на хората, които могат да бъдат в
тази линия, като три или каквото и друга стойност.
>> Но аз предлагам, че имам нужда, за да следите не само от размера на
опашката, колко много неща са в него.
Така размерът е текущия размер, капацитет е максималният размер.
Просто отново номенклатура от Конвенцията.
Защо ми е необходим допълнителен Int вътре на опашка, за да следите кой е в
предната част на линията?
Защо въобще трябва да се направи, че в този случай?
>> Е, как е тази картина няма да се промени?
Вероятно мога да повторно най- на тази снимка.
Позволете ми да отида напред и да изтриете това, което е тук.
Ще дам малко друго име тук.
Да се ​​отървем от 17, да се отървете на 9, да се отървете от 3.
И нека добавим още нещо.
Аз предлагам, че имам нужда, за да следите предната част на списъка, който е само
ще бъде едно цяло число, както добре.
И ние ще продължим да го прости.
Не свързан списък за сега.
>> Ще призная, че ние ще блъскам леко в този лимит.
Но това, което искам да видя се случи този път?
Така че предполагам, че вървим напред и първата човек идва в линия, и
това е номер 9.
Имаме стрес топки.
Мога ли да крадат, да речем, двама или трима души?
Едно, две, три?
Хайде нагоре.
Още от предния, защото ние ще направим това бързо.
>> Всеки от вас сега ще бъде Фен момче на опашка в Apple.
Вие няма да бъдете получаване Apple хардуер в края на този все пак.
Добре.
Значи ти си номер 9, ти си номер 17, номер 22.
Това са произволни числа, като Студент IDs или какво ли не.
И в един момент, нека да започнем да започнете да добавяте неща.
И аз ще тичам борда тук този път.
>> Така че в този случай, аз инициализира предната да бъде -
Аз всъщност не ми пука какво Предните, тъй като размерът е нула.
Така че това може и просто да въпросителен знак.
Това са всички въпросителни знаци.
Така че сега ще започнем действително да видите някои хората се редят на опашка в магазина.
>> Така че, ако номер 9, ти си първият там в 5 часа сутринта, давай напред и да се подредят,
или предишната вечер.
OK.
Така че сега 9 е тук.
Така че 9 е в предната част на списъка.
Така че аз ще отида напред и да актуализира Размерът на тази текущите данни
структура не е вече 0, а да бъде 1.
Отивам да се сложи 9 на предната част на списъка.
Позволете ми да отида напред и да превключите на екрана да можем да видим миналото ни тук.
>> И сега какво искам да постави най-отпред?
Отивам, за да следите, че отпред на опашката, точно сега
е на място 0.
Защото това, което е следващата ще се случи?
Е, предполагам, сега Enqueue 17, както добре.
Така хоп в съответствие там.
И отново, нещо като врата към магазин ще бъде тук.
Така че сега сте добавили 17.
И въпреки, че тези момчета са блокиране на екрана, това е ОК,
защото можем да я видите тук.
Извинете.
>> Публика: Ние може да се движи -
>> DAVID Malan: Не, това е ОК.
Това е огромен там.
Така 17 сега вътрешността на опашката.
Аз трябва да се актуализира, които полета сега все пак?
OK, определено размер.
А какво ще кажеш за отпред?
OK, не.
Front не трябва да се промени, защото За разлика от стека, ние
искат да запазят справедливост.
Така че, ако 9 дойде в първата, искаме 9 да бъде първият от линията
и в магазина.
>> Всъщност, нека да видим това.
Преди да вмъкнете 22, да отидете напред и да dequeue 9.
Какъв ти е името?
>> Публика: Джейк.
>> DAVID Malan: Джейк ще се насочва към предприятието.
Така че можете да влезете в магазина.
И да се преструвам, че в магазина е там.
Така че сега това, което трябва - ДИТ-DIT-DIT!
Какво трябва да се случи сега?
Design решение.
Така че не е лошо инстинкт, но - какво ти беше името?
>> Публика: David.
>> DAVID Malan: David.
И какво направи Давид направя?
Той се опитваше да сортирате определят данните структура и да се премести от своето място
в предишно местоположение на Джейк.
И това е добре, ако сте готови да приеме, че като
изпълнението детайл.
Но първо, нека да актуализира данните, структура, преди да го направя.
Защото няма да хареса идеята за всички хората изместване в този ред.
>> Това не е голяма работа, ако Давид го прави с една стъпка, но отново, мисля обратно
когато сме имали осем доброволци на сцена и ние сме направили като вмъкване
подреди, където трябваше да започне се движат всички наоколо.
Това привлече скъпо, нали?
Това ме кара да се свият за голям O М, Н голяма от п изправи отново.
Той не се чувства като идеална резултат.
>> Така че нека просто да актуализира този.
Така размерът на опашката вече не е 2.
Сега е просто един.
Но сега мога да актуализира нещо Аз не актуализира по-рано,
предната част на списъка.
Мога просто да кажа, е, че едно място?
Така че сега ние имаме боклук стойност тук, боклук стойност тук, и Дейвид в
средата на този боклук.
Но структурата на данните е все още непокътнати.
>> И всъщност, аз дори не трябва да промените бившия номер на Джейк
9, защото на кого му пука.
Имам достатъчно информация сега в размер Знам, че има един човек в
тази опашка.
И аз знам, че това лице е на разположение 1 не 0.
Аз не разчитам.
Така един, както добре.
Така структурата на данните все още е OK.
>> Е, какво се случва след това?
Да Enqueue -
как ти е името?
>> Публика: Калън.
>> DAVID Malan: Калън.
Нека Enqueue на Калън, и 22 вече е в опашката.
И сега какво трябва да се промени тук?
Front няма да промените, очевидно.
Размер няма да се промени за 2 отново.
И 22 озовава тук, девет все още съществува, но това е ефективно на
боклук стойност сега.
Това е просто един остатък от миналото Джейк.
>> И сега какво ще стане, ако I dequeue Дейвид?
One последната операция, dequeue David.
Ние може да се измести, но аз предлагам нека направете малко работа колкото е възможно.
Сега ми данни структура отива резервно по размер от 2 на 1.
Но отпред на опашката сега става 2.
Не е нужно да променяте тези номера просто все още, защото те са
само боклук стойности.
>> Но сега какво се случва?
Да предположим, че се Enqueue, 26?
Имам чувството, че принадлежа тук.
Така че аз съм се enqueued.
Така че аз вид е мястото тук.
И въпреки че не съвсем Оценявам това визуално на сцената,
защото имаме много място, бих не да стоя тук, защо?
>> Публика: Ти си извън границите.
>> DAVID Malan: Точно така.
Аз съм извън границите.
Аз бях индексира отвъд границите на този масив.
Аз наистина трябва да бъде в една от най- три възможни места.
Сега, къде е най-естествено да отидете?
Предлагам да ливъридж една седмица един трик.
Министерството на отбраната на оператор, процент.
Защото аз съм технически стоящ 3 място, но аз правя 3 мод капацитет,
така 3, знак за процент, 3 -
капацитет е 3.
Какво е това?
Какво е остатъкът при разделяте 3 от 3?
0.
>> Така че това ме поставя се Джейк беше, което всъщност е добре.
Така че сега изпълнението на това нещо ще
да бъде малко на главоболие.
Това е наистина само една линия от главоболие, на код.
Но поне сега има боклук стойност тук, но има два
законни цели числа тук.
И аз твърдя, че сега сме направили точно това, което трябва да направите, докато
да променим това, което Джейк стойност е трябвало да бъде 26.
>> Сега разполагаме с достатъчно информация, все още да се запази целостта
на структурата на данните.
Все още сме вид на късмет, когато ние искате да вмъкнете четири или повече общо
елементи, но може поне да направи доста ефективно използване на тази константа
време, в действителност.
Не е нужно да се притеснявате за преместване Всеки човек, като наклона на Давид беше.
>> Всякакви въпроси за стакове, или тази опашка?
>> Публика: е причината, поради трябва размер, така че знам
, където да има човек?
>> DAVID Malan: Точно така.
Трябва да се знае размера на масива защото трябва да се знае точно как
много от тези стойности са законни, и така, че мога да намеря къде да се постави
на следващия човек.
Точно така.
Размерът е -
Всъщност, ние не актуализира това.
Аз се добавя в 26.
Размерът е сега, а не един, а два.
Така че сега това наистина ми помага да намерите началото на списъка, което не е 0, а не
1, но е 2.
Предната част на списъка наистина е номер 22.
Защото той дойде в първия, така че той трябва да да се разреши в магазина пред мен,
въпреки че визуално Стоя по-близо до магазина.
>> Ясно ли е?
A аплодисменти за тези момчета и ще ги пусна от там.
>> [APPLAUSE]
>> DAVID Malan: Можех да държите на тавата.
Можем да видим какво ще стане, ако искате, но може би не.
Добре.
Така че това, което сега ни води това?
Е, нека да предложи, че има няколко други структури от данни можем да
започнете да добавяте към нашия комплект инструменти, които ще всъщност да бъде доста, доста значими, тъй като
ние се потопите в Мрежата неща.
Което отново има някаква връзка да дърветата под формата на
нещо, наречено DOM, документ обектния модел.
Но ще видим повече от че не след дълго.
>> Позволете ми предложи definitionally, че ние наричаме дърво сега какво може да знае като
повече на родословно дърво, където можете има някои прародител на
корените на дървото.
A патриархалната или матриарх на На самия връх на дървото.
Без техните съпрузи, в този случай.
Но сега ние имаме това, което ние ще се обадя деца, които са възли, които висят
разстояние отляво дете или правото дете, стрели, както е изобразено тук.
>> С други думи, в дървовидна структура данни в компютъра, а дървото има нула
или повече възли.
Ако има най-малко един възел, Това се нарича корен.
Това са неща, които визуално рисуваме на върха.
И този възел, като всеки друг възел, може имат нула, едно, или две, или три,
или както много деца на структурата на данните подкрепя.
В този случай, корен, съхраняване на стойност един, има две деца, 2 и 3,
така че ние обикновено наричаме две в ляво дете и 3 отдясно дете.
>> И тогава, когато стигнем до 5, 6, и 7, 6, може да се нарича средата дете.
Ако имате четири деца, става объркващо.
Така че спрете да използвате този вид от контекстното устно.
Но това е наистина само на родословно дърво.
И листата тук са възли, които себе си нямат деца.
Те висят от дъното на дървото.
>> Е, как може да реализираме едно дърво, което има само две деца максимално?
Ще го наречем двоичен дърво.
Bi отново смисъл, две, в това случай, като с двоичен.
И така, той може да има нула, едно, или две деца максимално.
>> Ще предложа да прилагат на възела за тази конструкция с едно цяло число N,
и след две насоки, една наречена наляво, един наречен право.
Но това са само хубаво произволни конвенции.
И това, което е хубаво сега, особено ако вид концептуално бореше с
рекурсия, или мислех, че не е наистина на решение за нищо,
особено ако можеш изчерпване на паметта.
Сега, че ние не говорим за данни структури и алгоритми, които позволяват
ни да пресече и да ги манипулират, Оказва се, че рекурсия се върне в
много по-убедителна ако не е красив начин.
>> Така че това предлагам, е прилагането на функция за търсене.
Като се има предвид два входа -
така че мислете за това като една черна кутия.
Като се има предвид два входа, N, едно цяло число, и указател към едно дърво, показалец към
възел, или наистина корените на едно дърво, I Твърдението, че тази функция може да се върне
вярно или невярно, че стойността н е в рамките на това дърво.
>> Какво е вътре в тази черна кутия?
Е, четири клона.
Първият просто проверява.
Ако дървото е нула, просто връщане фалшиви.
Ако няма възел, няма N, че няма номер, просто връщане фалшиви.
Ако все пак, п, стойността, което търсите за, е по-малко от дърво стрелка п и
само за да бъде ясно, какво означава, когато Пиша дърво и след това върху стрелката
нотация, п?
Точно така.
Това означава, че и сочен показалеца нарича дърво.
Отиди там, и след това влезе вътре на тази възел и да получите своята област нарича п.
И след това сравнява актуалната N, че е премина в търсене против него.
>> Така че, ако п е по-малък от стойността на п в дървото самия възел, добре,
Какво означава това?
Това не означава нищо на пръв поглед.
Така ли е?
Точно както когато имате набор от стойности, може би искате да се прилагат двоичен
търсите като форма на разделение и владей.
Но това, което предположение е, че трябва да направи за търсене в едномерен да работи на всички
в телефонния указател и ранни примери?
>> Как да се сортират.
Така че нека да усъвършенства определението за дърво тук не да бъде само едно дърво, което може да
има ли броя на децата.
Не просто двоично дърво, което може да има 0, 1 или 2 максимално.
Но като двоични дървета за търсене, или BST, която е само на луксозен начин на казвайки на
двоични дървета, така че всяка възлова точка ляво дете, ако присъства, е
по-малко от възловата точка.
И правото на всеки възел на детето, ако присъства, е по-голяма
от самия възел.
>> Така че с други думи, ако ви се налага да изготвя дървото се, всички номера са
внимателно балансирани, подобен на този, така че ако имате 55 като корен, 33 може да отиде
неговото ляво, защото е по-малко от 55.
77 могат да отидат в правото си, защото това е по-голямо от 55.
Но сега забелязвам, същото определение, това е рекурсивна дефиниция устно,
трябва да се прилагат за 33.
33 на ляво детето трябва да бъде по-малко от това, и право дете на 33, 44, трябва да бъде
по-голяма от нея.
>> Така че това е двоичен дърво за търсене, и Аз предлагам, като се използва малко
рекурсия, сега можем да намерим п.
Така че, ако н е по-малко от стойността N, че е текущия възел, аз ще отида
напред и шута, така да се каже, и само върне каквото и отговорът е на
търсене на N на ляво дървото дете.
Забележете отново, тази функция само очаква възел звезда,
указател към възела.
Така че със сигурност аз просто може да направи дърво стрелка наляво, което ще доведе
ме на друг възел.
Но какъв е този възел?
>> Ами, според тази декларация, ляво е само на показалеца, така че просто
означава, че аз съм се премине към функцията за търсене различен показалеца, а именно
този, който представлява лявата ми детето дърво.
Така че в този случай, на показалеца към 33, ако това е нашата извадка вход същото време, ако
п е по-голяма от стойността на п текущия възел в дървото, тогава аз съм
ще вървим напред и шута в другата посока и просто да кажа, аз не
знам дали тази стойност п е в дървото, но знам, че ако е така, ще му е моя
Дясното разклонение, така да се каже.
Така че нека да ми се обади рекурсивно търсене, полагане на п отново, но преминава в
показалеца на дясната си дете.
>> С други думи, ако съм в момента при 55 и аз търся 99, знам, че 99
е по-голямо от 55, така че точно както аз разкъса телефонните седмици преди книгата и ние
отиде право, по същия начин ние сме ще отиде точно тук.
И аз не знам дали това е най-дясната ми дете, и това не е, 77 е там, но
Знам, че е в тази посока.
Така че аз наричам търсене в дясната детето ми, 77, и нека фигура търсене из
ако има 99 в произволна Пример за това е действително там.
>> Иначе, това, което е крайния случай?
Ако дървото е нищожна е един случай.
Ако п е по-малко от текущия възел е стойност е друг случай.
Ако п е по-голямо от настоящото стойност възел е трети случай.
Каква е четвъртият и последен случай?
Мисля, че сме от случаите, нали?
Тя трябва да бъде, че п е в текущия възел, че аз съм за.
>> Така че, ако аз съм търсене на 55 в този момент в историята, която е клон на
дърво ще върне истина.
Така че това, което е интересно тук е, че ние Всъщност, за разлика седмици миналото, ние вид
на имат две основни случаи.
И те не трябва да бъде всичко най-отгоре.
Горната е базовия модел, защото ако Дървото е нула, няма какво да се направи.
Просто се върнете твърд кодирани стойност на невярна.
>> Долният клон е нещо като подразбиране, при което, ако сме проверявани за
нищожна, ние проверихме, ако тя трябва да бъде напусна, но това не трябва да бъде, ние сме
контролира, дали трябва да е точно, но не трябва да бъде, ясно трябва да е
точно там, където сме.
Това е основния случай.
Така че има две рекурсивни случаи поставен там в средата.
Но би могъл да напише това в произволен ред.
Просто мислех, че нещо се струват естествени първо да проверите за евентуална грешка,
след това проверете наляво, после провери Добре, тогава предположим, че вие ​​сте на възел
вие всъщност търсите.
>> Така че, защо може това да е полезно?
Така се оказва, -
и ме остави да скочи до закачка тук това е в интернет.
Ще започнете да използвате не е език за програмиране в началото, но с
език за маркиране.
Маркиращ език е този, който е подобни по дух на програмиране
език, но това не ви дава способността да изразиш себе си логично.
Той само ви дава възможност да Изразете себе си структурно.
>> Къде искате да сложите нещо на страницата, на уеб страницата?
Какъв цвят искате да го направите?
Какво шрифта искате да го направите?
Какви думи да направя всъщност искат на уеб страница?
Така че това е език за маркиране.
Но след това ще въведе много бързо JavaScript, който е пълноправен
език за програмиране.
Много подобни синтактично на външен вид до C, но ще има някои
хубаво, по-мощен, по- удобен за потребителя функции.
>> И един от отчаянието на този точка в семестър е, че ние ще
скоро изпълнение правопис в далеч по-малко реда код, които използват други езици
от C самата позволява, но и за разума скоро ще се разбере.
Това ще бъде първата подобна уеб страница.
Тя ще бъде напълно underwhelming, първият правим.
Той просто ще кажа, здравей свят.
Но ако никога не сте го виждали преди, това е HTML,
HyperText Markup Language.
>> Ако отидете до определена опция от менюто в Най-всеки браузър, на всяка уеб страница на
в интернет, можете да видите на HTML че някои хора пише на
създаване, че уеб страница.
И това може би не изглежда толкова Накратко, или като чист, тъй като това.
Но това ще следват модела на тези отворени скоби и наклонени черти и
писма и евентуално номера.
>> Мислех, че ще ви дам един тийзър от това, което ще бъде в състояние да направи
след като CS50.
Пуснете ме да cs.harvard.edu / Роб, начална страница със собствена Rob Боудън.
Той направи това за нас.
Така че скоро ще бъде в състояние да направи това.
И също така, това, което сте чули тази сутрин -
това, което чух тази сутрин -
>> [HAMSTER DANCE MUSIC]
>> - You'Ll бъде в състояние да направи това.
Това ни очаква в сряда.
Ще се видим тогава.
>> [HAMSTER DANCE MUSIC]
DAVID Malan: На следващото CS50 -