Дејвид MALAN: Во ред. Добредојде назад кон CS50. Ова е почеток на недела 8. И се сети дека проблемот сет 5 завршила со малку од предизвик. Значи под претпоставка дека ги обнови сите вашите наставата соработници и фотографии издавачот на сертификати во датотеката card.raw, имате право до сега се најдат сите оние луѓе, и еден среќен добитник ќе одиме дома со еден на овие работи, скок движење уред кој можете да го користите за конечна проекти, на пример. 

Ова, секоја година, доведува до малку морничавост. И така она што мислев јас би го сторила е удел со вас некои од забелешките кои имаат качил напред и назад во текот на персоналот листа на крајот. На пример, само минатата ноќ, цитат unquote, од еден на персоналот членови, "Јас само имаше еден студент тропаат на мојата врата да се слика со мене. Stalkers, ќе ти кажам. "Го започна натпреварот прилично описни и потоа се пресели за да, еден час или па подоцна ", имав една Студентот ме чека по секција и тој имаше сите наши имиња и фотографии на некои листови хартија. "Сите во право. Така организирани, но не сето тоа гаден уште. 

Потоа, ", бев надвор од градот овој викенд, и кога се вратив, имаше еден во мојата спалната соба. "[Смеа] Дејвид MALAN: Следна цитат од на персоналот член ", дојде еден студент во мојата куќа на Самервил на 04:00 ова утро. "Напред персонал, "Јас имам на мојот хотел во Сан Франциско и студент е на чекање за мене во фоајето со три DSLRs. " Тип на камера. "Јас не сум дури и врз вработените овој семестар, но еден студент провалил во мојата куќа наутро и се евидентираат целата работа со Google стакло. "И тогаш на крај, "Најмалку 12 лица беа со нетрпение чека за мене кога ја добив од мојата лимузина, а потоа јас разбудил. "Сите во право. Па меѓу фотографии, како што може потсетиме, се овој човек тука, кој ќе би можеле да знаат како Мило Банана, кој живее со Lauren Карваљо, нашата глава настава соработник. Мило, Мило, дојди овде момче. Мило. Мило. Иначе, тој носи на Google стакло, па ние ќе ви покаже сето ова после. Па ова е Мило, ако би сакал да да фотографира со него потоа. Ако сакате да внимавате на публиката таму. OK. Тоа е добро снимката. Па, Мило Банана. Ох, не го правам тоа. 

[Смеа] 

OK. Па еден збор, тогаш на она што се наоѓа напред, бидејќи, како што ние почнат да се транзиција, оваа недела конкретно, од C во командната линија на животната средина за PHP и Вклучите Javascript-и SQL и HTML и CSS во веб-базирана средина, ќе биде опремување на вас со сите повеќе знаење за потенцијални крајни проекти. Кон таа цел, се разбира има Традицијата на одржување на семинари кои се на површни теми на курсот. Многу поврзана со програмирање и да стан развој и така натаму, но не мора да посегнуваат на курсот е наставната програма. 

Па ако може да бидат заинтересирани во една или повеќе од семинари оваа година, регистрирам cs50.net/seminar. Постојат постари семинари на cs50.net/seminars. И на списокот досега за оваа година се неверојатни веб апликации со Ruby on Шини, која е алтернатива јазик во PHP. Компјутерска лингвистика. Воведувањето на iOS, кој е платформа која се користи за iPhone и iPad развој. JavaScript за веб апликации, ние ќе ги покрие тоа, но во овој семинар, ќе одам во повеќе детали. 

Скок движење, па ние всушност ќе имаме некои на нашите пријатели од скок движење, на самата компанија, да ни се придружат. Утре, всушност, да обезбеди рацете на семинарот, ако од интерес за вас. Meteor.js, алтернативна техника за користејќи го вклучите Javascript не во прелистувачот, но на серверот. Node.js, што е многу многу Во таа смисла, како и. Елегантен Андроид дизајн. Андроид да се биде многу популарна алтернатива на iOS и Windows Телефон и други мобилни платформи. И веб безбедност активна одбрана. 

Така, всушност, ако би сакал да се вклучат во тоа, нека ме направи забелешка на тоа. Ние сме многу среќни да се каже дека нашите пријатели во скок Движење, што е стартување - овој уред навистина само што дојде надвор пред неколку месеци - нема грациозно донираа 30 такви уреди на класата за онолку студенти, доколку сакате да ги позајмите хардвер кон крајот семестар и го користат за вистински конечниот проект. Тие ги поддржуваат голем број на јазици. Никој од нив Ц, никој од нив не PHP, така сфатат една или повеќе од овие семинари може да се покаже на интерес. И сите од нив ќе се снима во случај дека не сте во можност да присуствува во лице. Распоредот бидат објавени преку e-mail, како што се зацврсти соби. 

И на крај, ако одите на projects.cs.50.net, ова е веб-сајт ние одржување секоја година дека ние покани луѓе од заедницата, факултет, одделенија, персонал, и двете во надвор од CS50 да предложи проектни идеи. Работите од интерес за студентски групи. Работите од интерес за оддели. Па се претвори таму ако сте се борат со несигурност за тоа што себе би сакале да се справи. 

Па последен пат воведе веројатно повеќе комплексна структура на податоци отколку што би гледа во недели минатото. Ние би биле користење на низи прилично среќно како корисно ако симплистички податоци структура. Тогаш ние воведе овие, кои се разбира се поврзани листи. И она што беше еден од мотивите за воведување на оваа податочна структура? Да? Што е тоа? 

ПУБЛИКАТА: Динамички големина. 

Дејвид MALAN: Динамички големина. Значи додека во низа, што треба да знаат нејзината големина однапред кога ќе ја распредели. Во поврзана листа, вие не Треба да знаете дека. Можете да само Примерок, или поопшто, распредели дополнителен јазол, така да се каже, секој пат кога ќе сакате да го вметнете повеќе податоци. И јазол не предодредено значење. Тоа е само генерички поим опишувајќи некој вид на сад, дека ние сме користење во нашата структура на податоци за чување некој предмет на интерес, кој во овој случај да се случи да бидат цели броеви. 

Но секогаш постои Губитокот. Па да добиеме динамичен големини на податоци структура, но која цена ние плаќаат? Она што е во надолна линија на поврзани листи? Да? 

ПУБЛИКАТА: Потребна повеќе меморија. 

Дејвид MALAN: Се бара повеќе меморија, како точно? 

ПУБЛИКАТА: [нечујни]. 

Дејвид MALAN: Токму така. Така, сега имаме совети преземањето дополнителна меморија што ние претходно не се потребни, бидејќи предност на низа, се разбира, е тоа што сè е соседни, назад да се врати да се врати, кои ви дава случаен пристап. Затоа што само со помош квадратни загради нотација, или повеќе технички покажувачот аритметика, многу едноставна Покрај тоа, можете да пристапите на некој елементи во постојана време. И во Всушност, тоа е вид на алудирајќи на друга цена, дека ние сме плаќаат со поврзана листа. 

Што се случува со трчање време на нешто како пребарување, ако сакам да најдете некои вредност и во внатрешноста на поврзана листа? Што значи моето трчање време стана? Биг О од n. Ако тоа е сортирана да? Што ако на податочна структура е сортирана? Можам да го направи подобро од големите О на n за пребарување? Не, затоа што во најлош случај тоа би можело да многу добро да бидат подредени, но бројот сте во потрага за да биде голема. Тоа би можело да биде број 100, која може да се случи да биде на сите начинот на кој на крајот. И затоа што може само да пристапите на поврзан листа во оваа имплементација од страна на начин на својот прв јазол, ти си уште вид на надвор од среќа. Ќе мора да напречни целата работа од прво до последно, со цел да се најде дека голема вредност како 100. Или да се утврди дали тоа е дури и не постојат. 

Па не можеме да го направи она што алгоритам во податоците структура што личи ова? Не можеме да правиме бинарни пребарување, бидејќи бинарни пребарување потребно дека имавме случаен пристап. Ние може само да се фрлиш од локација за локација, без да ги следат овие трошки од леб во форма на сите овие совети. 

Сега, како сме спроведување на оваа? Па, ако ние одиме на екранот тука, ако ние брзо може да reimplement овие податоци структура - мојот ракопис не е сето она што голем тука, но ние ќе се обидеме. Па typedef struct, и што правел јас сакате да го повикате ова нешто овде? Јазол. Па јас ќе добиете ни почнати. И сега, она што треба да бидат внатре на на податочна структура за која одделно поврзана листа? Колку полиња? 

Па две. Една од нив е прилично лесно. Па int n. И ние може да се нарече n ништо сакаме, но тоа треба да биде цел број, ако ние сме спроведување на поврзана листа за ints. И сега што го прави вториот поле треба да биде? Struct јазол *. Значи, ако го направам struct јазол *, а потоа јас да го наречеме овој, исто така, она што сакам, но само да биде јасно Ќе му се јавам тоа следната, како што ние си правеле. И тогаш Јас ќе ја затворам мојата кадрава загради. 

И сега, како минатиот пат, Ја ставив јазол овде долу. Но, ако јас сум прогласување ова е како јазол, зошто јас се мачам да биде толку опширниот тука во декларирањето struct јазол * следната, како што се противат само јазол * следно? Да? 

ПУБЛИКАТА: [нечујни]. 

Дејвид MALAN: Токму така. Токму така. Бидејќи C навистина ќе ве однесе буквално и само гледа дефиницијата на јазол патот надолу тука, не можете да се однесува на тоа тука горе. Значи ние треба овој вид на превентивна декларација тука, што е значително повеќе опширниот. Struct јазол, тоа значи дека ние сега може да го пристап внатрешноста на податочна структура. 

И како настрана, бидејќи ова е станува малку повеќе субјективен сега, ѕвездата технички може да оди тука, тоа може да оди тука, може да дури и одат во средината. Ние сме донесени, во стилот водич за на курсот, на конвенцијата на ставање ѕвездата веднаш до податоци тип, кој во овој случај, ќе биде struct јазол. Но сфати во многу учебници и онлајн референци, можеби навистина види тоа на другата страна. Но само сфатат дека и двете ќе всушност се работат и можете едноставно треба да биде доследни. 

Сите во право. Така што беше нашата декларација на struct јазол. Но потоа почнавме прави повеќе софистицирани нешта. На пример, решивме да се воведе нешто како хаш табелата. Па овде е хаш табелата на големина n, индексирани од 0 на горниот лев агол на n минус 1 на дното лево. Ова може да биде хаш маса за ништо. Но, она што видови на работите си зборуваме за користење на хаш табелата за? Складирање на што? 

Имиња. Можеме да направиме имиња како ние го сторивме последен пат. И навистина, може да складира ништо. И ние ќе го гледаат ова повторно во PHP и во JavaScript. А хаш табелата е убав вид на Швајцарската Војнички нож кој ви овозможува да ги чувате доста она што го сакате во внатрешноста на тоа со асоцирањето клучеви со вредности. Копчињата со вредности. 

Сега, во овој едноставен случај, нашите копчињата се само бројки. Ние сме за воведување на хаш маса како низа. И така на копчињата се 0, 1, 2, и така натаму. И така ние, како луѓе, одлучи минатата недела дека знаете што, ако ние сме ќе продавница имиња, ајде да арбитрарно, туку прилично разумно, претпостави дека Алис, А името, само ќе бидат индексирани во 0. И Боб, име Б, ќе бидат индексирани во 1, и така натаму. Па моравме мапирање помеѓу влезови, кои се стрингови, и хаш локации, кои се бројки. 

Така што процесот е општо познато како хаш функција, и можете да навистина се спроведе тоа во кодот. Ако сакав да се спроведе hash функција кои го прави токму она што го само што е опишано од последниот пат, би можел да прогласи функција која зема, како влез за пример - и ајде да го направите тоа на овој екранот овде. Ако сакав да се спроведе хаш функција, би можел да кажам нешто како ова. 

Тоа се случува да се врати int. Тоа се случува да се нарече хаш, а тоа е ќе го прифати како аргумент за стринг, или можеме да бидеме повеќе соодветна сега, и да каже char *, ние ќе го наречеме s. А потоа сите оваа функција треба да се направи, во крајна линија, е се врати int. Сега, како го прави тоа што би можело да Не биди толку јасни. Одам да се спроведе оваа без никакви форма на проверка на грешка моментов. Јас сум само ќе слепо се каже, да се вратите она што е во е заградата 0, минус, да речеме, капитал-запирка. 

Целосно скршен. Тоа не е совршен, бидејќи еден, што ако s е нула? Лоши работи се случува да се случи. Две, што ако првата буква во оваа името не е голема буква? Тоа не се случува да се сврти добро или. Тоа би можело да биде мали букви или не писмо на сите. Така целосно простор за подобрување тука, но ова е основната идеја. 

Она што ние го опиша минатата недела вербално само процесот на мапирање Алис да 0 и Боб до 1 може да се изрази сигурно повеќе formulaically како C функционира тука. Повика повторно хаш, потребно е стринг како влез, а потоа некако не нешто со што влезот за да се произведе излез. Не за разлика од нашите црна кутија опис дека ние сме одамна направено. Не знам како ова може да биде работат под хауба. 

За проблемот сет 6, еден од предизвиците е за вас да се одлучи што Вашиот хаш функција ќе биде? Она што се случува за да биде внатре во тоа црно кутија, и веројатно, тоа ќе биде малку поинтересно од оваа, и дефинитивно повеќе склони кон грешки проверка од овој особено имплементација. 

Но проблеми можат да настанат, нели? Ако имаме податочна структура, како што тоа еден, што е еден од проблемите можете да го извршите во текот на времето како ќе го вметнете се повеќе и повеќе имиња во хаш табелата? Ќе добиете судири, нели? Што ако имате Алис и Арон, две лица чии имиња се случи да се започне со? Кој моли на прашањето, каде што стави втората такво име? 

Добро, можеби наивно само да го стави каде Боб припаѓа, но потоа Боб е вид на зезнав ако се обидете да вметнете неговото име следната и нема простор за него. Така што може да се стави Боб каде што Чарли е, и можете да замислите оваа многу брзо пренесени во малку неред. Нешто линеарно на крајот, каде што едноставно мора да пребарувате на целата работа во потрага по Алис или Боб или Арон или Чарли. 

Така, наместо ние предложи, наместо само линеарно љубопитство за отворени простори и plopping имињата таму, ние предложи познавач пристап. А хаш табелата спроведува уште со низа на индексите, но податоците тип на оние индекси сега се покажувачи. Покажувачи на што? Покажувачи на поврзани листи. 

Бидејќи се потсетиме дека поврзана листа е навистина само покажувач на еден јазол, и јазол има следните поле, и тој јазол има следниот поле, и така натаму. Значи сега ќе можете да размислувате на оваа низа на на левата страна од хаш табелата како што доведува до поврзана листа. Предноста на кој е ако добиете судир меѓу Алис и Арон, што правиш со втор таков човек? Вие само го закачите или неа да крајот, или дури и на почетокот на тој поврзана листа. 

А всушност, ајде само глупак преку дека за само една секунда. Каде што ќе направи најмногу смисла? Ако јас внесете Алис и таа завршува на првата локација, тогаш јас се обидувам да внесете име на Aaron, и има очигледно судир, јас треба да се стави него на почетокот на поврзана листа? Тоа е во тоа прва локација, или на крајот? 

ПУБЛИКАТА: [нечујни]. 

Дејвид MALAN: OK. Слушнав почеток. Зошто на почетокот? 

ПУБЛИКАТА: [нечујни]. 

Дејвид MALAN: OK. Тоа е азбучен, па тоа е убаво. Тоа е добра имотот. Тоа ќе ме спаси некое време потенцијално. Тоа нема да ми дозволи да направи бинарни пребарување, но јас најмалку би можело да биде во можност да се пробие на јамка ако Сфаќам, добро, јас сум начин минатото биле Арон да биде во оваа сортирани поврзаните листа. Јас не треба да отпад моето време бараат по целиот пат до крај. Па тоа е разумно. Зошто друго можеби ќе сакате да го вметнете на судирање име на почетокот на листа? Што е тоа? 

ПУБЛИКАТА: [нечујни]. 

Дејвид MALAN: Тоа би можело да трае долго време да се дојде до крајот на листата. И всушност, подолго и подолго. На повеќе имиња ќе го вметнете дека Започнете со, на подолг дека синџир се случува да се добие. На подолг дека се поврзани листа ќе добиете. Па ти си навистина само трошат вашето време. Можеби ти си подобро одржување постојана вметнување време, голем О од 1, од секогаш ставање на судир името на почетокот на поврзана листа, и не се грижам колку за сортирање. 

Кој е најдобар одговор? Тоа е јасно. Тој вид на зависи од тоа што дистрибуција е, она што моделот е од имињата што се вметнување. Тоа не е нужно очигледен одговор. Но тука за да, пак, е дизајн можност. 

Па ние потоа погледна во оваа работа, која е навистина другата голема можност за p-сет 6. И ќе сфати, ако веќе не сте, Zamyla нурка во двете од овие, хеш маси и неуспешни обиди, во повеќе детали. И видео Walkthrough е вградени во спецификации п-сет. Ова беше Trie - Т-Р-И-Е. И она што беше интересно за ова беше тоа што трчање време на потрага по име, како Максвел последен пат, беше големо O на што? Што е тоа? 

ПУБЛИКАТА: Бројот на букви. 

Дејвид MALAN: Број на букви. Слушнав две работи. Број на букви и постојана време. Па ајде да одиме со тоа во прв план. Бројот на букви. Па, ова податочна структура, се потсетиме, е како дрво, семејство дрво, секоја од чии јазли се составени од низи. И оние низи се покажувачи на други такви јазли, или други слични низи на дрвото. 

Значи, ако сакавме да потоа да одреди дали Максвел е овде, би можел да одам на првата низа, во самиот врв на на дрво, т.н. корен, врвот на на Trie, а потоа следат покажувачот метри, тогаш покажувач, а потоа X, W, E, ј, л. А потоа кога ќе видам некои посебни симбол, означувал тука како триаголник. Во кодот ќе видите ние предлагаме дека спроведува како bool, само велејќи да или не, збор запира тука. 

Па, откако ќе си отиде со М-А-Х-З-Е-Л-L, се чувствува како седум, можеби осум ако одиме еден покрај тоа, осум чекори да се најде Максвел. Или ајде да го наречеме К Но потсетиме минатата време, јас тврдеше дека ако има реално максимална должина на збор, како 40-некои чудни карактери, Максималната должина подразбира константна вредност. Значи, навистина, да, тоа е технички големо O од 8 или 7, или навистина голема О на К Но, ако има конечен капа на она што К би можело да биде, тоа е константа. И така тоа е голема О од 1 на На крајот на денот. 

Не во реалниот свет. Не кога ќе всушност почнете гледајќи Вашиот часовник што се трчање вашата програма. Тоа е апсолутно случува да биде малку побавно отколку вистински постојана време со еден чекор. Тоа се случува да биде седум или осум чекори, но сепак тоа е многу, многу подобро од алгоритам како големо O на n дека зависи од големината на она што е во податочна структура. 

Забележите наопаку тука е што може да се вметне еден милион повеќе имиња во оваа податочна структура, но колку повеќе чекори е тоа ќе не однесе да се најде Максвел во тој случај? Нема. Тој е непроменета. И до денес, јас не мислам дека ние сме виделе пример за податочна структура или алгоритам кој беше целосно под влијание на надворешни однесувања како што. Но, ова не може да биде неверојатна. Ова не може да биде единствено решение за п-сет 

И тоа не е. Ова не е нужно на податоци структура треба да гравитираат кон, бидејќи како хеш табели, Губитокот. Она што е цената што ја плаќате тука? Меморија. Мислам, ова е крволочен количина на меморија. А вие не сосема да го видите тука, бидејќи авторот на оваа слика очигледно скратена сите низи, и ние не гледате многу А и Б и Ц и П, а на Y и Z во овие низи. Но тие се таму. 

Секој од овие јазли е цела низа на некои 26 или повеќе бајти, секоја од што претставува едно писмо. 27 во нашиот случај, така што ние може да ги поддржи апострофи во проблемот сет. Па оваа податочна структура е навистина, навистина густа и широка. И дека сам може да заврши забавува нешта долу, или барем ве чини многу повеќе простор. Но, повторно, можеме да извлечеме споредби тука. 

Потсетиме некое време наназад, ние остваривме многу повеќе возбудлив трчање време во сортирање кога ние ги користиме спојат вид, но цената ја плативме за да се постигне n најавите n за спојување вид потребно, ние трошиме повеќе она ресурс? Повеќе простор. Ни е потребно средно низа да се копирате луѓе во, исто како и ние го сторивме тука на сцената. Значи, повторно, не постојат јасни победници, но само субјективни дизајн одлуките да се носат. 

Сите во право. Па, како во врска со ова? Секој препознае кои Д-сала? OK. Па три од нас го прават. Mather куќа. Па ова е за јадење Mather е. Ќе залог сите јадење сали имаат Купишта на коцки како оваа. И ова е всушност претставник на нешто што сум очигледно се гледа веќе. Ние го нарече буквално оџак. И на магацинот, во однос на вашиот меморија на компјутерот, е местото каде податоците оди додека функции се нарекува. 

За пример, она што видови на работите одат на магацинот во однос на меморија распоред сме разговараа во недели минатото? Што е тоа? 

ПУБЛИКАТА: Повиците на функции. 

Дејвид MALAN: Жал ми е. 

ПУБЛИКАТА: Повиците на функции. 

Дејвид MALAN: Повиците на функции, но Поточно, она што е внатре на секоја од тие рамки? Какви видови на нештата? Да. Па локални променливи. Во секое време ни е потребно некои локални складирање, како аргумент, или int i, или int Temp, или што и локалната променлива, ние сме ставање дека на магацинот. И ние ја нарекуваме оџак, бидејќи на таа дели идеја. Само вид на натпревари со реалноста, концептот него. 

Но излегува дека оџакот може исто така да да се гледа како на податоци структура, алтернатива низа, алтернатива на поврзана листа. Нешто концептуално поинтересна што се 'уште може да биде спроведува со користење или на оние работите, но тоа е друг тип на податочна структура поддршка, навистина, само две операции. Но можете да додадете на познавач функции од овие. Но, овие се основите - им помогнам и поп музиката. 

А идејата со магацинот е дека ако јас имаме овде, со или без Annenberg знаејќи, послужавник од следната врата со бројот 9 на неа. Па само Инт. И сакам да им помогнам на оваа излез на податоци структура, која во моментов е празна. Сметаат дека ова дното на магацинот. Јас ќе им помогнам овој број 9 врз магацинот, а сега тоа е право таму. 

Но интересна работа во врска оџак е дека ако јас сега сакаат да им помогнам на некои други вредност, како 17, и јас им помогнам на ова врз оџакот, јас ќе одам да направите само интуитивно работа, јас сум само ќе да го стави десно каде што ние, луѓето ќе бидат склони да го стави, на врвот. Но она што е интересно сега е, како можам да добијам на 9? Знаете, јас не направи без некои напори. 

Значи она што е интересно за магацинот е дека од страна на дизајнот, тоа е податоци LIFO структура. Глупо начин на опишување на последен во, прво од. Па во последните број во во тоа време беше 17. Значи, ако јас сакам да pop нешто надвор на магацинот, тоа може да биде само 17. Па постои задолжително цел на операции тука, каде што последната ставка во мора да биде првиот надвор. Оттука акроним, LIFO. 

Па зошто ова може да биде корисно? Дали нивните контексти во кои вие би сакате податочна структура, како тоа? Па, тоа е сигурно е корисно внатрешноста на компјутерот. Па оперативни системи јасно го користите овој вид на структура на податоци за Купишта. Ние, исто така, ќе се види на истата идеја кога станува збор за веб страници. Така оваа недела и следната недела и пошироко, и како што ќе почнете спроведување на веб- страници на јазик наречен HTML, можете да всушност употреба на податоци структура како ова за да се утврди дали страница е правилно форматиран. Затоа што ние ќе видиме сите веб страници следат еден вид на хиерархија, кратер кои, на крајот на денот, да биде дрво структура под хауба. Толку повеќе за тоа во само малку. 

Но, за сега, ајде да предложи за моментот, како би можеле да се обратите за претставуваат она што магацинот е? Дозволете ми да предложи дека ние се имплементираат магацинот со кодот вака. Па магацинот се случува да имаат во него две работи, низа, наречен пепелниците, само за да бидат во согласност со демо. И секоја од точките во таа низа се случува да биде тип int. И капацитет е веројатно она што? Бидејќи јас не сум напишал на целосна дефиниција тука. 

Тоа е веројатно максимум големината на низата. И тоа е веројатно декларирани како остар дефинирање на врвот на датотеката, некои вид на постојана како имплицирани од самиот капитализација. Па некаде капацитет се дефинира како максимална можна големина. Во меѓувреме, во внатрешноста на податочната структура познат како оџак ќе има да биде цел број само познат едноставно како големина. 

Значи, ако јас требаше да ја претставува оваа сега сликовито, да претпоставиме дека оваа Целиот црна кутија претставува мојот оџак. Во него е две променливи. Па ќе одам да се подготви на првиот како големина. А вториот Одам да се подготви како низа. 

Но само да го задржи нешта уредно, нормално јас ќе привлече низа како ова, но тоа е вид на убаво ако ние одговараат на реалноста, или одговара на ментална модел. Па да ми наместо исцртување на низа вертикално, што е само, повторно, уметникот препевот. Не е важно она што го е под хауба. А ние ќе се каже дека, по дифолт, капацитет ќе биде три. Па ова ќе биде локација 0, овој ќе биде локација 1, овој ќе биде локација 2. 

Ако јас ги поткупат со стрес топчето, би Некој како да се излезе и да ја стартувате качи тука за само еден миг? Добро, видов вашата рака во прв план. Ајде горе. Сите во право. Па јас верувам дека тоа е Стивен. Ајде горе. Сите во право. 

Но, да претпоставиме сега ние ја премотам касетата на почетна состојбата на светот каде што имате само прогласи магацинот, а тоа е ќе биде на капацитетот три. Но, големината се уште не е утврден. Пепелниците се уште не е утврден. Па неколку прашања во прв план. И дозволете ми да ви даде микрофон за да можете да причестуваат поактивно во ова. 

Значи она што е внатре големина во овој момент во времето кога сите што го сторив е прогласи магацинот со една линија код? 

Стивен: Не многу. 

Дејвид MALAN: Добро, не многу. Знаеме што е внатре на големината, знаеме што е внатре на оваа низа тука? 

Стивен: Само случаен кодот, нели? Само - 

Дејвид MALAN: Да, јас ќе одам да го нарекуваат код, но случајни - 

Стивен: Работи што треба. 

Дејвид MALAN: Работи како случаен 

Стивен: битови. 

Дејвид MALAN: битови, нели? Па ѓубре вредности, нели? Па пермутации на 0 и 1 е. Остатоци од претходната примени на оваа меморија. И ние навистина не знаат што вредности се, па ние обично ги привлече како прашалници. 

Така првото нешто ние сме веројатно ќе сакате да го направите тука - и дозволете ми даде ова поле внатре од таму името - пепелниците. Она што треба ние веројатно се иницијализира Големината да ако сакаме да започнат со користење на оваа оџакот? 

Стивен: носачот е под 3. 

Дејвид MALAN: Значи, ОК. Да биде јасно, капацитет е прогласена друго место како што три. И тоа е она што јас сум користел за да се распредели низа. Големината се случува да се однесува на тоа колку пепелниците се во моментов на магацинот. 

Стивен: Нулта. 

Дејвид MALAN: Така треба да биде нула. Така одат напред и со било кој прст, подготви нула во големина. Сите во право. Па сега, она што е внатре на овој тука, ние не знаеме. Овие се навистина само ѓубре вредности. Па ние би можеле да подготви прашалници, но ајде да се задржи одбор чисти сега за сега затоа што тоа не е важно она што е таму. Ние не треба да се иницијализира на низа на ништо, бидејќи ако знаеме дека големината на оџакот е нула, добро, ние не треба да се гледа во нешто во оваа низа сепак на овој момент во времето. 

Па сега да претпоставиме дека сум им помогнам на број 9 врз оџакот. Колку ние треба да се ажурира на податоци структура во внатрешноста на оваа црна кутија? Кои вредности треба да се промени? 

Стивен: Во текот на - големината? 

Дејвид MALAN: OK. Големина треба да стане она? 

Стивен: Големина ќе биде една. 

Дејвид MALAN: OK. Па големината треба да стане еден. Па можете да го направите тоа во неколку начини. Дозволете ми да ви даде, сега вашиот прст е гума за бришење. Сите во право. Тогаш сега вашиот прст е четка. Сите во право. И сега што друго има да се промени, очигледно, во податочна структура? 

Стивен: Ние ќе од дното до 9. 

Дејвид MALAN: 9. Добро, добро. Па се уште не е важно она што е во локација една или две, бидејќи тие се ѓубре вредности, но ние не треба да пречи бараат таму, бидејќи големината е да ни кажува дека само првиот елемент е, всушност, легитимна. Па сега јас им помогнам 17 кон листата. Што се случува со оваа слика? 

Стивен: Значи големина се случува да одат на две. 

Дејвид MALAN: OK. Ти си Бришачот - Упс. Ти си гума за бришење. 

Стивен: Гума за бришење. 

Дејвид MALAN: Ти си четка. 

Стивен: Четка. 

Дејвид MALAN: OK. И што друго? 

Стивен: И тогаш - 

Дејвид MALAN: Ние се наметнува 17. 

Стивен: Ние се држиме 17 на врвот, па - 

Дејвид MALAN: Добро, добро. 

Стивен: - тоа паѓачкото. 

Дејвид MALAN: Во ред. Станува лесно. Јас не одам за да ви помогнат тоа време. Притисни 22. 

Стивен: Done. Станува гума за бришење. Јас сум да стане четка. И тогаш јас сум ставање 22. 

Дејвид MALAN: 22. Одличен. Значи уште еднаш. Јас сум сега ќе да им помогнам на врз оџакот 26. 

Стивен: Ooh. Ох боже. Вие навистина ме фати исклучи стража. 

Дејвид MALAN: Вие не види ова доаѓа? 

Стивен: Јас не го гледаат ова што доаѓаат. Да можеме повторно почетен капацитет? 

Дејвид MALAN: Тоа е добро прашање. Па ние сме вид на се насликани во некој ќош тука. Тука навистина не е добро надвор за Стивен затоа што ние сме распределени оваа низа статички, така да се каже, во внатрешноста на податочна структура. И ние во суштина хард кодирани таа да биде со големина од три. Па ние навистина не може да го пренамени. 

Ние би можеле да ако се вративме во, ние редефинира коцки да биде показател дека ние потоа користете Примерок на рака меморија за да се. Затоа што ако добивме меморија од грамада преку Примерок, ние тогаш би можеле да го ослободи. Но, пред ослободувањето на тоа, ние би можеле пренамени поголем парче на меморија, ажурирање на покажувач, и така натаму. Но, за сега, ова е навистина најдоброто што може да се направи. Им помогнам и поп се претпоставува дека ќе мора да сигнализираат некои грешка. 

Така на пример, нашата институција на притисни може да се врати на bool кои претходно се врати вистина, вистина, вистина. Но по четврти пат, тоа се случува да имаат за да се вратите лажна, на пример. Сите во право. Многу добро направено. Алал да му е. Сте заработени вашиот стрес топчето денес. 

[Аплауз] 

Стивен: Ви благодариме. 

Дејвид MALAN: Ви благодариме. Добро, па се чини дека ова не е многу на еден чекор напред, нели? Што е опишано оваа податочна структура. Тоа е огромна, нели? Оперативни системи се допаѓа. Очигледно на интернет може да се направи употреба на ова, и други апликации се уште. Но она што е глупаво ограничување дека ние сме се врати да се вид на недела две граници каде што имаме фиксна големина на низи. 

Па така постојат навистина неколку начините на кои може да го реши ова. Ние динамички може да ги распредели низа, не со тешко кодирање како што сум направено овде, но наместо повторно прогласување ова, само за да бидат јасни, како нешто како ова. Int * пепелниците не, одлучувајќи на капацитет уште. Но, кога ќе го прогласи магацинот на друго место во мојот код, јас тогаш може да се нарече Примерок, ја добиете адресата на парче меморија, и можев да доделите таа адреса да пепелниците. 

А потоа, бидејќи тоа е само еден дел од меморија, би можел да продолжи да го користи плоштад заградата нотација на вообичаениот начин. Затоа што еднаш, таму е еден вид на овој функционален еквивалент на низи и делови од меморијата кои доаѓаат се врати од Примерок. Ние можеме да се третираат како и другите користење на покажувачот аритметички или квадратни загради нотација. Значи тоа е еден пристап. 

Но како поинаку би можеле да ја имплементираат оваа истата податочна структура, потенцијално? Нели? Се чувствувам како ние едноставно се реши овој проблем како пред една недела. Она што беше на решение за овој проблем дека Стивен налетав? Така поврзани листи, нели. 

Ако проблемот е во тоа што ние сме сликарство се во ќошот со распределба однапред премалку меморија дека ние потоа ја некако да се справи со, добро, зошто да не само се избегне тоа издаде заедно? Зошто да не само прогласи коцки да биде покажувачот на еден јазол, ergo е поврзана листа, и потоа едноставно алоцирање на нови јазли секој пат Стивен потребни за да се вклопи со број во податочна структура. 

Па сликата ќе треба да се промени. Тоа нема да биде толку чист и како едноставно како што само низа од три ints. Сега тоа се случува да биде покажувач кон struct, и дека struct се случува да се имаат int и следната покажувач. Тоа се случува да доведат преку кој покажувачот на друг како struct да друга таква struct. Па сликата ќе всушност се добие малку Messier. И ние би го стрели врзување сето заедно. 

Но тоа е во ред, нели, затоа што видовме како да го направите тоа. И штом еднаш ќе се чувствуваме удобно спроведување на нешто како поврзани листа, која ќе треба да направите ако изберете да се спроведе хаш табелата со посебна врзувањето за P-сет 6, можете да користат како градење на блок, или состојка, или во Скреч имено, постапка, нешто што ќе се стави, можете креирано свој загатка парче што потоа може да повторна употреба. Па размени, но потенцијални решенија дека ние сме всушност видел. 

Па доста често, ќе видите ова секој година или две кога Епл изданија нешто ново, и сите луди луѓе линија надвор од Епл продавница за да купи нивниот маргинален надградба на хардверот. Ова го велам, тоа е во ред, затоа што Јас сум еден од оние луѓе. Значи каков вид на податоци структура може да ја претставува оваа реалност? 

Добро, ајде да го наречеме дното, на линија. Па Британците би го нарекол тоа обично редот и онака, па тоа е убаво име. И двете операции кои редица ќе ги поддржи ние ќе го нарекуваат Стави во ред операција и dequeue операција, кои се слични во дух да им помогнам и поп музиката. Тоа е само вид на различен во конвенција, она што ние сме повикување на овие. Но да Стави во ред нешто значи да додадете или вметнете ја до податоците структура. Да dequeue значи да го отстраните. Но со оглед на тоа оџакот беше на податоци LIFO структура, задачата е прв во, Првиот надвор податочна структура. 

Ако сте првата личност во линија, ќе биде првата личност да се добие надвор од линијата и да купам вашиот нов уред. Замислете колку вознемирени овие луѓе ќе биде ако Apple наместо да се користи оџак, за пример, за спроведување на Бране up на својата нова играчка. Па редици се направи смисла, секако, и можеме да размислуваме за сите видови на апликации, веројатно, за редици, особено кога сакате праведност. Па како да ги имплементираат овие како податочна структура? 

Па, јас предложи дека ние би можеле да треба да го направи тоа на овој начин. Па јас ќе одам да сега имаат броеви. Па ние ќе ја задржиш едноставен и не мора да зборуваме во однос на коцки. Само броеви кои луѓето од добивано. Капацитет ќе се, повторно, да утврдат на вкупниот број на луѓе кои можат да бидат во оваа линија, како три или без оглед на друга вредност. 

Но јас предложи дека јас треба да ги пратите не само на големината на на дното, колку многу нешта се во неа. Значи големина е сегашната големина, капацитет е максималната големина. Само еднаш, номенклатура со конвенција. Зошто ми е потребен дополнителен int внатре на дното да ги пратите на кој е во предниот дел на линија? Зошто воопшто морам да го сторат тоа во овој случај? 

Па, како е ова слика ќе се промени? Јас веројатно може да повторна употреба повеќето од оваа слика. Дозволете ми да оди напред и да ги избрише она што е овде. Ние ќе им даде на овој малку друго име тука горе. Ајде да се ослободи од 17, да се ослободи на 9, ајде да се ослободи од 3. И ајде да додадете една друга работа. Јас предложи дека јас треба да ги пратите на на предниот дел на листата, која е само нема да биде int, како и. И ние ќе го чувам едноставна. Не поврзана листа за сега. 

Ние ќе признаам дека ние ќе судрат против оваа граница. Но, она што сакам да го видам се случи овој пат? Па претпоставувам дека одиме напред и првиот лице доаѓа во линија, и тоа е број 9. Ние немаме стрес топки. Јас може да украде, да речеме, две или три лица? Еден, два, три? Ајде горе. Право од фронтот, бидејќи ние ќе направи ова е еден брз. 

Секој од вас сега ќе биде Навивач момче во линија на Apple. Вие нема да се примаат Apple хардвер на крајот од ова, секако. Сите во право. Па ти си број 9, ти си број 17, број 22. Овие се произволни броеви, како студент ИД или какво ли не. И во само еден момент, ајде да започне за да започне додавајќи нешта. И јас ќе се кандидира на одборот тука тоа време. 

Значи во овој случај, јас сум иницијализира пред да биде - Јас всушност навистина не се грижат што Предниот дел е, бидејќи големината е нула. Па ова би можело, како и само биде знак прашалник. Овие се сите прашалници. Па сега ние ќе почнат да всушност гледаат некои луѓе обидел во продавницата. 

Значи, ако бројот 9, ти си првиот таму во 5:00, оди напред и да се редат, или ноќта пред тоа. OK. Па сега 9 е тука. Значи 9 е во предниот дел на листата. Па јас ќе одам да се оди напред и да се ажурира големината на овој тековните податоци структура не да биде 0 повеќе, но за да биде 1. Одам да се стави 9 на пред листа. Дозволете ми да оди напред и да ја префрлате на екранот па може да се види минатото нас овде. 

И сега што сакам да се стави на предната? Одам да ги пратите дека редот на чекање во моментов е на локација 0. Затоа што она што следната ќе се случи? Па, претпоставувам сега јас Стави во ред 17, како и. Значи хоп во линија таму. И повторно, вид на вратата на продавница ќе биде тука. Па сега јас додадов 17. И иако овие момци се блокира на екранот, тоа е во ред, затоа што ние може да се види тука. Жал. 

ПУБЛИКАТА: Ние може да се движи - 

Дејвид MALAN: Не, тоа е во ред. Тоа е огромна таму горе. Па 17 е сега во внатрешноста на задачата. Јас треба да се ажурира кои полиња сега иако? Добро, дефинитивно големина. И како за пред? Добро, нема. Напред, не треба да се менува, затоа што за разлика од оџакот, ние сакаат да го задржат праведност. Па ако 9 дојде во првата, сакаме 9 да биде првиот надвор од линија и во продавница. 

Всушност, ајде да видиме тоа. Пред да ја вметнете 22, ајде да повелете и dequeue 9. Како се викаш повторно? 

ПУБЛИКАТА: Џејк. 

Дејвид MALAN: Џејк се случува да се dequeued сега. Па ќе го добиете да одиме во продавница. И да се преправам дека во продавницата е таму. Па сега она што треба - dit-dit-dit! Што треба да се случи сега? Дизајн одлука. Па не е лоша инстинкт, но - Како се викаш повторно? 

ПУБЛИКАТА: Дејвид. 

Дејвид MALAN: Дејвид. Значи она што не Дејвид направам? Тој се обидува да најде решение за поправат податоци структура и се движат од неговата локација во поранешната локација на Jake. И тоа е во ред, ако ние сме подготвени да прифатат дека како имплементација детали. Но, прво, ајде да ажурирање на податоците структура, пред да го направите тоа. Бидејќи јас не сум вкусот на идеја на сите на луѓето менувањето во оваа линија. 

Тоа не е голема работа ако Дејвид тоа го прави со еден чекор, но повторно, се сетам на кога имавме осум волонтери на фаза и ние го направивме како вметнување вид, каде што моравме да почне се движат сите околу. Кој доби скап, нели? Што ме прави раболепнича за големи О на n, големо O на n квадрат повторно. Тоа не се чувствува како идеална исход. 

Па да ја ажурирате оваа. Па од големината на редот не е повеќе 2. Тоа е сега едноставно 1. Но јас сега може да се ажурира нешто Јас не ажурирање порано, пред листа. Јас само може да се каже, е таа локација 1? Така, сега имаме ѓубре вредност тука, ѓубре вредност тука, и Дејвид во средината на оваа ѓубре. Но податоците структура е сеуште недопрена. 

И во Всушност, јас дури и не треба да се промена поранешниот број на Jake 9, затоа што оној кој се грижи. Имам доволно информации сега во големина што знам има едно лице во оваа задача. И знам дека тоа лице е во локација 1 не, 0. Јас не сум броење. Па 1, како и. Па податочна структура е се уште во ред. 

Па, она што се случува следно? Ајде Стави во ред - Што е вашето име? 

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

Дејвид MALAN: Callen. Ајде да Стави во ред со Callen, и 22 е сега во редот. Па сега што мора да се смени тука? Напред, не се случува да се промени, очигледно. Големина ќе се промени за да биде 2 повторно. И 22 завршува тука, 9 се уште е присутна, но тоа е ефикасно ѓубре вредност сега. Тоа е само остаток од Џејк минатото. 

Па сега што ќе се случи ако Јас dequeue Давид? Едно последно операција, dequeue Давид. Ние би можеле да ја префрлат, но јас предложи ајде направите како што е малку работа како е можно. Сега, мојот податочна структура оди се врати во големина 2-1. Но пред редот сега станува 2. Јас не треба да ги промените овие броеви само уште, затоа што тие се само ѓубре вредности. 

Но, сега што се случува? Претпоставувам дека си Стави во ред, 26? Се чувствувам како да припаѓаат овде. Па јас сум се enqueued. Па јас вид на припаѓам овде. И иако не сосема го ценат тоа визуелно на сцената, бидејќи имаме многу простор, јас треба да не се стои тука, зошто? 

ПУБЛИКАТА: Ти си надвор од границите. 

Дејвид MALAN: Право. Јас сум надвор од границите. Сум индексирани надвор од границите на оваа низа. Јас навистина треба да биде во една од три можни локации. Сега, каде е најприродната да одиме? Предлагам ние балон една недела еден трик. МО оператор, процент. Бидејќи јас сум технички стои во локација 3, но јас не 3 современи капацитети, толку 3, знакот за процент, 3 - капацитет е 3. Што е тоа? Она што е остатокот кога ќе делат 3 од 3? 0. 

Така што ме става беа Џејк беше, кој е всушност добро. Па сега на имплементација на ова нешто се случува да да биде малку главоболка. Тоа е навистина само една линија на главоболка, на код. Но барем сега има ѓубре вредност тука, но има две легитимни ints тука. И тврдам дека сега ние сме го направиле токму она што ние треба да направите толку долго како ние се промени она што на Jake вредност требаше да биде 26. 

Сега имаме доволно информации сé уште да се задржи интегритет на овој податочна структура. Ние сме се уште вид на надвор од среќа кога ќе сакате да вметнете четири или повеќе вкупните елементи, но можам да се направи барем прилично ефикасно користење на оваа постојана време, во факт. Јас не мора да се грижите за менувањето сите, како склоност Давид беше. 

Било какви прашања во Купишта, или оваа задача? 

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

Дејвид MALAN: Токму така. Јас треба да се знае големината на низата затоа што треба да знаат точно како многу од овие вредности се легитимни, и така што ќе можам да најдам каде да се стави следниот лице. Токму така. Големината е - всушност, ние не ја ажурирате оваа уште. Јас додадени на 26. Големината е сега, не е 1, но 2. Па сега ова навистина ми помага да се најдат на шеф на листата, која не е 0, не 1, но е 2. На предниот дел на листа е навистина бројот 22. Бидејќи тој дојде во прв, па затоа тој треба да биде дозволено во продавница пред мене, иако визуелно Стојам поблиску до продавница. 

Сите нели? А аплауз за овие момци а ние ќе ги пуштам од таму. 

[Аплауз] 

Дејвид MALAN: не можев да да ги задржи на послужавник. Можевме да видиме што ќе се случи ако што сакате, но можеби не. Сите во право. И сега што, дали тоа ни остави? Па, дозволете ми предложи дека има неколку други структури на податоци би можеле да започне додавајќи до нашата алатка комплет кој ќе всушност ќе биде доста, доста релевантни како ние се нурне во веб нешта. Кои, повторно, има некој вид на врска за дрва во форма на нешто што се нарекува ДОМ, документ објект модел. Но ќе видиме повеќе од дека пред долго. 

Дозволете ми да предложи definitionally дека ние јавете дрво сега она што би можеле да знаат како повеќе од семејно стебло, каде што имаат некој предок на корењата на дрвото. А патријархални или матриарх на на самиот врв на дрво. Без нивниот брачен другар, во овој случај. Но сега имаме она што ќе го наречеме деца, што се јазли кои висат надвор од левата дете или право дете, стрели како што е прикажано тука. 

Со други зборови, во дрво структура на податоци во компјутерот, едно дрво има нула или повеќе лимфни јазли. Ако има најмалку еден јазол, што се вика коренот. Тоа е она визуелно дека цртаме на врвот. И тој јазол, како и секој друг јазол, може да имаат нула, еден, или два, или три, или сепак многу деца на податочна структура поддржува. Во овој случај, коренот, чување на вредност еден, има две деца, 2 и 3, па ние обично се јавите 2 левата дете и 3 на десната дете. 

А потоа кога ќе се фаќате за 5, 6 и 7, 6 може да се нарече средината дете. Ако имате четири деца, станува збунувачки. Значи ние да престане со користење таков вид на кратенка вербално. Но тоа е навистина само семејно стебло. А лисјата тука се јазли кои самите немаат деца. Тие висат надвор од дното на дрвото. 

Па како да се спроведе дрво кое има само две деца максимално? Ние ќе го наречеме бинарен дрво. Bi повторно значи два, во овој случај, како и со бинарни. И така тоа може да има нула, еден, или две деца максимално. 

Јас ќе предложи дека ние спроведување на јазол за таа структура со int n, а потоа две покажувачи, една што се вика лево, една што се вика во право. Но тие се само убаво произволни конвенции. И она што е убаво сега, особено ако вид на се бореше концептуално со рекурзија, или мисли дека тоа не е навистина решение за ништо, особено ако може снема меморија. Сега дека ние зборуваме за податоци структури и алгоритми кои им овозможуваат на ни за напречни и манипулираат со нив, Излегува дека рекурзија се враќа во многу повеќе привлечни Ако не е убава начин. 

Значи ова го предлагам е спроведувањето на функцијата за пребарување. Дадени два влеза - па мислам на ова како црна кутија. Дадени два елемента, n, на број, и покажувачот за дрво, покажувач кон јазол, или навистина во коренот на дрвото, јас тврдат дека оваа функција може да се врати лажни или вистинити, дека n вредност е во внатрешноста на ова дрво. 

Она што е внатре на оваа црна кутија? Па, четири гранки. Првиот само проверки. Ако дрвото е null, само враќање false. Ако нема јазол, нема n, нема број, само враќање false. Ако сепак, n, вредноста сте во потрага за, е помала од дрво стрелките на n и само за да бидат јасни, што значи тоа кога Јас пишувам дрво, а потоа на стрелката нотација, n? Токму така. Тоа значи dereference дека покажувач кој се нарекува дрво. Оди таму, а потоа се добие во внатрешноста на таа јазол и да добијат своето поле нарекува n. А потоа се споредат реалните n тоа беше донесен во Барај против тоа. 

Па ако n е помала n вредност во дрво јазол себе, добро, Што значи тоа? Што не значи ништо на прв поглед. Нели? Исто како кога ќе имаат низа на вредности, можеби ќе сакате да се применуваат бинарни пребарување како форма на поделба и освојување. Но, она што претпоставка не ни треба да се направи за бинарни пребарување за да работат на сите во телефонот книга и претходните примери? 

Како да се подредени. Па ајде да ја прилагодите на дефиниција на дрвото тука да не биде само едно дрво, што може да има неограничен број на деца. Не само бинарно дрво, што може да имаат 0, 1 или 2 максимално. Но како бинарен за пребарување дрво, или БСТ, која е само фенси начин да се каже на бинарно дрво таква што секој јазол левата дете, доколку се присутни, е помалку од јазол. И секој јазол е во право дете, ако се присутни, е поголем од јазол себе. 

Значи со други зборови, ако сте во ситуација да се подготви дрво надвор, сите на броеви се внимателно избалансирани вака, така што ако имате 55 како root, 33 можат да одат да неговата лева, бидејќи тоа е помалку од 55. 77 може да оди на своето право, бидејќи тоа е поголема од 55. Но сега забележите, истата дефиниција, тоа е рекурзивен дефиниција вербално, мора да аплицираат за 33. 33 го напушти детето мора да биде помало од тоа, и правото на детето 33 е 44, мора да биде поголем од него. 

Значи ова е бинарно пребарување дрво, и Јас предложи, со користење на малку на рекурзија, ние сега може да се најде n. Значи, ако n е помала од вредноста n тоа е тековната јазол, јас ќе одам да си напред и залог, така да се каже, и само се врати она што одговорот е на во потрага по n на левата дрвото дете. Забележите повторно, оваа функција само очекува јазол ѕвезда, покажувач кон јазол. Па сигурно јас само може да се направи дрво стрелка лево, што ќе доведе ме до друг јазол. Но она што е тој јазол? 

Па, според оваа декларација, лево е само покажувач, така што само значи јас сум поминува до функцијата за пребарување различни покажувач, имено оној што претставува мојата лева дете дрво. Значи во овој случај, на покажувачот до 33, ако ова е нашиот примерок влез меѓувреме, ако n е поголема од вредноста n на тековната јазол во стеблото, тогаш јас сум ќе одиме напред и залог во други насока и само велат, јас не знам дали оваа вредност n е во дрво, но знам ако е така, тоа е по моите право гранка, така да се каже. Па ајде мене повик рекурзивно пребарување, поминува еден n повторно, но поминува во покажувачот на моето право дете. 

Со други зборови, ако јас сум моментално на 55 и јас барам за 99, знам дека 99 е поголем од 55, па онака како што раскина на телефонот книга недели и ние отиде право, слично сме ние одам да си во право тука. И јас не знам дали тоа е во мојата десна дете, и тоа не е, 77 е таму, но Знам дека е во таа насока. Па јас го нарекувам пребарување на моето право дете, 77, и нека пребарување дознаам од таму ако 99 во оваа произволна Пример за ова е всушност таму. 

Друго, она што е конечниот случај? Ако дрвото е null е еден случај. Ако n е помалку од сегашната јазол вредност е друг случај. Ако n е поголема од тековната вредност јазол е трет случај. Што е четвртиот и последен случај? Мислам дека ние сме надвор од случаите, нели? Тоа мора да биде дека n е во тековната јазол дека јас сум на. 

Значи, ако јас сум во потрага по 55 во овој момент во приказната, таа гранка на дрво ќе се врати вистина. Значи она што е интересно овде е дека ние всушност, за разлика недели минатото, ние вид на имаат два база случаи. И тие не мора да се биде на врвот. На врвот е база случај, бидејќи ако дрво е нула, нема ништо да се направи. Само се вратат на хард кодирани вредноста на неточно. 

На дното гранка е вид на Стандардно, при што ако ние Сум проверил за нула, ние Сум проверил дали тоа треба да биде лево, но тоа не треба да биде, ние сме проверува дали тој треба да биде во право, но тоа не треба да биде, јасно е дека мора да биде право, каде сме. Тоа е база случај. Значи има две рекурзивен случаи сендвич таму во средината. Но можев да го имаат напишано ова во секој ред. Јас само мислев дека вид на се чувствува природно прво да се провери за можна грешка, тогаш проверете остави, тогаш проверете во право, тогаш Претпоставуваме дека сте на јазол ти си, всушност барате. 

Па зошто ова може да биде корисно? Така што се испоставува - и дозволете ми да скокнат до закачка тука тоа е во мрежата. Ние ќе треба да почнат да го користат не програмскиот јазик во прво време, но Селектирај јазик. А јазик за Селектирај е оној кој е слични во духот со програмирање јазик, но тоа не ви даде способност да се изразат логично. Тоа само ви дава можност да се изразат себе си структурно. 

Каде сакате да се стави нешто на оваа страница, веб-страница? Каква боја сакаш да се направи тоа? Што големина на фонт сакаш да се направи тоа? Она што зборовите ќе го направите, всушност, сакате на веб страната? Така што е маркап јазик. Но, тогаш ние многу брзо ќе се воведе JavaScript, која е полноправна членка на програмски јазик. Многу слични синтаксички во изгледот на C, но тоа ќе има некои убаво, помоќен, корисник пријателски особини. 

И еден од фрустрации во овој точка во семестар е дека ние ќе наскоро спроведе правопис во далеку помалку линии на код со употреба на други јазици од C себе дозволува, туку и за причина за ние наскоро ќе се разбере. Ова ќе биде прв ваков веб-страница. Таа ќе биде целосно underwhelming, првиот правиме. Тоа едноставно ќе се каже, Здраво светот. Но ако никогаш не сум го видел пред, ова е HTML, HyperText Markup Language. 

Ако одите до одреден опција од менито во повеќето секој интернет пребарувач, на било кој веб-страница на на интернет, можете да видите на HTML дека некои луѓе му напиша писмо на создаде таа веб страница. И тоа најверојатно не изгледа како кратка или како уредни како оваа. Но, тоа ќе го следат моделот на овие отворен загради и засеци и писма и потенцијално броеви. 

Мислев дека ќе ви даде краток вовед од она што ќе биде во можност да го стори по преземањето CS50. Дозволете ми да одат на cs.harvard.edu / одземеш, почетната страница од пребарувачот нашите сопствени Роб Бауден. Тој го направи тоа за нас. Па дека наскоро ќе биде во можност да го стори тоа. И, исто така, она што го слушнав ова утро - она што го слушнав ова утро - 

[Хрчак денс музиката] 

- You'Ll да биде во можност да се направи ова. Што не чека во средата. Ние ќе се видиме тогаш. 

[Хрчак денс музиката] Дејвид MALAN: На следниот CS50 -