Малан ДАВИД: У реду. Добродошли назад у ЦС50. Ово је почетак недеље 8. И сећам се да је проблем скуп завршен 5 са мало изазов. Дакле, под претпоставком да сте пронашли све своје Стипендисти наставних и ЦА фотографијама у цард.рав датотеци, имате право на до сада је све те људе, и један срећни добитник ће ићи кући са једним од ових ствари, скок кретање уређај који можете да користите за финале пројекте, на пример. 

Ова, сваке године, доводи до мало цреепинесс. И оно што сам мислио да урадим је удео са вама неке од бележака које су отишао напред и назад преко списак запослених у последње време. На пример, прошле ноћи, цитатом Крај цитата, из једне од особља чланова, "само сам имао студентски куцање на моја врата да бисте снимили фотографију са мном. Манијаци ја вам кажем "кренули. прилично описно, а онда смо се преселили о да, после сат времена, "Имао Студент ме чека после секцији и он је имао све наше имена и фотографије на неким листовима "У реду.. Тако организована, али не све то језиво још. 

Затим, "Био сам ван града овог викенда, и када сам се вратио, био је један у мој Спаваћа соба "[смех]. ДАВИД Малан: Следећи цитат особља члан, "ученик дошао у моју кућу у Сомервил у 4 сата јутрос "Нект. особље, "Ја сам у мој хотел у Сан Франциско и студент сам чекао ми у холу са три ДСЛР. " Тип фотоапарата. "Нисам чак ни на особље овог семестра, али ученик је провалио у моју кућу ово јутро и снимио целу ствар Гоогле Гласс ", а онда на крају., "Најмање 12 људи је радо чека за мене када сам изашао из моје лимо, а онда сам пробудио "У реду.. Дакле, међу фотографијама, као што можда сећам, овај момак је овде, ко си можда зна како Мила Банана, који живи са Лаурен Царвалхо, наша глава асистент. Мило, Мило, дођи овамо дечко. Мило. Мило. Пазите, он носи Гоогле Гласс, тако ми ћемо вам показати све ово после. Дакле, ово је Мило ако желите да узети фотографију са њим после тога. Ако желите да пази у публику тамо. ОК. То је добар снимак. Па, Мило банана. О, немој то да радиш. 

[Смех] 

ОК. Дакле, реч онда о томе шта се налази испред, јер као што смо почели да транзицији, ове недеље конкретно, из Ц у командна линија окружење за ПХП и Јава и СКЛ и ХТМЛ и ЦСС у окружењу базираном на Вебу, бићемо опремање те са свим више знања за потенцијалних крајњих пројеката. У том циљу, курс има Традиција одржавања семинара које су на периферним темама на курс. Веома много се односе на програмирање и Апп за развој и тако даље, али не нужно истражио Наставни план и програм курса сопствене екипе. 

Дакле, ако сте могли бити заинтересовани у једном или више семинара овогодишњих, региструју на цс50.нет/семинар. Постоје старији семинари у цс50.нет/семинарс. А на списку до сада за ову годину Изненађујуће су Веб Аппс са Руби он Шина, што је алтернатива језик на ПХП. Рачунарске лингвистике. Увод у иОС, што је платформа која се користи и за иПхоне иПад развој. ЈаваСцрипт за Веб Аппс, ми ћемо покрити да, али у овом семинару, прећи ћете у више детаља. 

Леап Мотион, тако да стварно би мало од наших пријатеља из Леап Мотион, Сама компанија, придружите нам се. Сутра, у ствари, да се обезбеди руке на семинару, ако од интереса за вас. Метеор.јс, алтернативна техника за Не користите ЈаваСцрипт у прегледачу, али на серверу. Ноде.јс, што је веома у том духу, као добро. Елегантан дизајн Андроид. Андроид као веома популарна алтернатива на иОС и Виндовс Пхоне и друге мобилне платформе. А Веб Сецурити активну одбрану. 

Тако у ствари, ако желите да се укључе у ово, нека ме запишите то. Веома смо срећни да кажем да наши пријатељи на скок Захтев, који је покретање - Овај уређај је заиста само од пре неколико месеци - је великодушно поклонио 30 таквих уређаја у класи за што већи број ученика, ако желите да позајми хардвер пред крај семестра и користити га за стварна финална пројекат. Они подржавају велики број језика. Нико од њих Ц, нико од њих ПХП, тако оствари једну или више од ових семинара могу бити од интереса. И сви они ће бити снимљен у догађај који ви нисте у стању да лично присуствују. Распоред бити објављен путем пошаљи као што смо учврсти собе. 

И на крају, ако одете у пројецтс.цс.50.нет, ово је сајт одржавамо сваке године да позивамо људи из заједнице, факултет, одељења, особље, и оба у ван ЦС50 у предлаже пројектне идеје. Ствари од интереса за студентских група. Ствари од интереса за одељења. Дакле, да ли постоји укључите ако боре уз несигурност шта сте се жели да се бави. 

Дакле, последњи пут смо увели вероватно сложенија структура података него што бих види у протеклих недеља. Ми бисмо били прилично помоћу низова срећно као користан ако поједностављено структура података. Онда смо увели ове, који наравно да су повезане листе. И оно што је био један од мотива за увођење ове структуре података? Да? Шта је то? 

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

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

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

ПУБЛИКА: Захтева више меморије. 

Малан ДАВИД: То захтева више меморије, како тачно? 

ПУБЛИКА: [ИНАУДИБЛЕ]. 

ДАВИД Малан: Управо тако. Дакле, сада смо показивачи заузимају Додатна меморија које смо раније није било потребно, јер је предност од низа, наравно, јесте да је све заразне, вратио враћа се назад, што вам даје случајан приступ. Јер само помоћу угласте заграде нотација, или више технички показивач аритметика, врло једноставан додатак, можете приступити било елементи у константном времену. А у ствари, то је врста истичући друга цена коју плаћамо са повезана листа. 

Шта се дешава са времена извршава нешто попут претраге, ако желим да наћи неку вредност и изнутра од повезане листе? Шта је мој пут узастопно постали? Велико О н. Ако је сортирани? Шта ако је структура података поредани? Да ли могу да урадим боље од велике О од н за претрагу? Не, јер у најгорем случају могао Веома добро се редају, али је број што тражите може бити велика. То може бити број 100, који може се десити да се све Начин на крају. И зато што можете да приступите повезана Списак у овој реализацији по начин њеног првог чвора, ти си још мало среће. Морате да пролазе целу ствар од првог до последњег, како би се пронашли да велика вредност као 100. Или, да се утврди да ли је чак ни тамо. 

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

Сада, како смо то спровести? Па, ако идемо на екран овде, ако брже можемо реимплемент ове податке структура - мој рукопис није све што супер овде, али ми ћемо покушати. Дакле типедеф струцт, и шта ја желите да позовете ову ствар овде? Ноде. Тако да ће нас почела. И сад, шта треба да се унутар структура података за то појединачно повезани листу? Колико поља? 

Дакле, два. Један од њих је прилично лако. Дакле, инт н. И ми смо могли назвати н шта хоћемо, али то би требало да буде инт ако смо спровођење повезану листу за интс. И сад шта други поље мора да буде? Струцт ноде *. Дакле, ако ја струцт чвор *, а онда сам можемо назвати и шта год хоћу, али само да буде јасно зваћу је следећи, као што смо радили. А онда ћу затворити своје витичасте заграде. 

И сада, као и прошли пут, Ставио сам чвор овде. Али, ако сам проглашавајући то је као чвор, зашто сам био толико сметало опсирније овде у изјављујући струцт * Следећи чвор, за разлику да само следећи чвор *? Да? 

ПУБЛИКА: [ИНАУДИБЛЕ]. 

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

И као по страни, јер је ово постаје мало субјективан сада, звезда може технички иде овде, Овде може да иде, она може чак и да иде у средини. Ми смо усвојили, у водичу за стил Наравно, конвенција стављања звезда поред података типа, што у овом случају, би струцт чвор. Али схватају у много уџбеника и Онлине референце, ви заиста можда види се на другој страни. Али обоје схватају да ће заправо раде и да једноставно треба да буде доследан. 

У реду. Дакле, то је био наш декларација од струцт ноде. Али онда смо почели да радимо више софистициране ствари. На пример, ми смо одлучили да представимо нешто као хеш табели. Дакле, овде је хеш табела величине н, индексиран од 0 у горњем левом до н минус 1 на дну лево. Ово би могао да буде хасх сто за било шта. Али, шта свашта смо причали у вези са коришћењем хеш табели за? Чување шта? 

Имена. Ми смо могли да урадимо имена попут смо прошли пут. И заиста, можете да сачувате нешто. И ми видимо ово поново ПХП и ЈаваСцрипт-у. Хасх табела је лепа врста Швајцарске Војни нож који вам омогућава да сачувате прилично шта год желите унутар је удруживањем тастере са вредностима. Тастери са вредностима. 

Сада у овом једноставном случају, наш Тастери су само бројеви. Ми спровођење хасх Књига као низ. И тако су кључеви 0, 1, 2, и тако даље. И тако смо, као људи, одлучио је прошле недеље да знаш шта, ако смо ће да меморишете имена, хајде да произвољно, али прилично разумно, Претпостављам да Алиса, име, Само ће бити индексиран у 0. И Боба, Б назив, ће бити индексиране у 1, и тако даље. Тако смо имали мапирање између улаза, које су ниске, и хасх локацијама које су бројеви. 

Дакле, тај процес је опште познато као хасх функција, а ви заиста можете да имплементира у коду. Да сам хтео да спроведе хасх функцију који ради управо оно што смо управо описао од прошлог пута, могао бих прогласи функцију која узима, као Улаз на пример - и урадимо то на ово Екран овде. Да сам хтео да спроведе хасх функција, могу рећи нешто овако. 

То ће да врати инт. То ће да се зове хеш, а то је ће прихватити као аргумент за ниска, или можемо бити правилно сада, и кажу цхар *, зваћемо га с. И онда све то има везе функција, на крају, се врати инт. Сада, како се то ради да би могао не буде тако јасна. Ја ћу да остваре ово без Форма за проверу грешке сада. Само ћу рећи да слепо, вратите све што је у с носачем 0, минус, рецимо, капитал и зарезом. 

Потпуно сломљен. Није савршен, јер један, а шта ако је нулл? Лоше ствари ће се десити. Друго, шта ако је прво слово у ово име није велико слово? То неће да се окрену се добро било. Можда је мало слово или писмо уопште. Дакле, потпуно простора за побољшање овде, али то је основна идеја. 

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

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

Међутим, проблеми могу настати, зар не? Ако имамо структуру података, као што су то један, што је један од проблема можете да наиђете на временом као што убаците све више и више имена у хеш табела? Добијате сударе, зар не? Шта ако имате Алиса и Арона, две особе чија имена се догодило за почетак? То намеће питање, где сте ставио други такав име? 

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

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

Јер Подсетимо да је повезана листа заиста само показивач на чвор, и чвор има следеће поље, и тај чвор има следеће поље, и тако даље. Тако да сада могу да се сетим овог низа на лева страна хеш табели, као што доводи до повезане листе. Предност је што ако се Колизија Алице и Арону шта да се ради са Друга таква особа? Само га прикључите или њу да крај, или чак почетак тог повезане листе. 

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

ПУБЛИКА: [ИНАУДИБЛЕ]. 

Малан ДАВИД: У реду. Чуо сам почетак. Зашто на почетку? 

ПУБЛИКА: [ИНАУДИБЛЕ]. 

Малан ДАВИД: У реду. То је азбучни, тако да је то лепо. То је добар имовине. То ће ми уштедети мало времена потенцијално. То ми не дозвољава да урадим бинарну претрагу, али ја можда бар моћи да се пробије напоље од петље ако сам схватио, добро, ја сам начин прошлости били Арон би у овом поредани повезану листу. Ја не морам да губим време гледајући све до краја. Дакле, то је разумно. Зашто би иначе можда желите да уметнете судара на име почетку листе? Шта је то? 

ПУБЛИКА: [ИНАУДИБЛЕ]. 

ДАВИД Малан: Могло би се дуго времена да се до краја листе. А у ствари, дуже и дуже. Што више имена умећете да почетак, да дуже ланац ће добити. Дуже да повезан списак ће добити. Значи ти си у ствари само губите време. Можда сте боље одржавање константно убацивање време, Биг О 1, тако увек стављањем сударају на име почетак повезане листе, и не забрињава толико о сортирање. 

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

Онда смо гледали ову ствар, која је заиста друга велика прилика за П-СЕТ 6. И схватите, ако већ нисте, Замила понире у оба ова, хасх столови и покушава, у више детаља. А видео је проход уграђен у П-СЕТ спец. То је био Трие - Т-Р-сам-е. А шта је занимљиво у вези то је да време извршавања трагања за име, као што је Маквелл последњи пут, био је велики О чега? Шта је то? 

ПУБЛИКА: број слова. 

ДАВИД Малан: Број слова. Чуо сам две ствари. Број слова и константно време. Идемо прво са тим. Број слова. Па, ова структура података, подсетимо, је као дрво, породично стабло, сваки од чији чворови се састоје од низова. А ти низови су показивачи на други такви чворови, или неко друго Низови у дрвету. 

Дакле, ако смо хтели да онда одреди да ли Маквелл је овде, ја могу да идем на први низ, на самом врху дрво, такозвани корен, врх Трие, а затим пратите м показивач, онда показивач, затим к, в, е, ја, ја. И онда кад видим неки посебан симбол, означава овде као троугао. У коду видећете предлажемо да имплементира као инт, рекавши само да или не, реч престаје овде. 

Па, када смо отишли ​​на М-А-Кс-В-Е-Л-Л, осећа као седам, можда осам ако идемо један поред њега, осам тражила Максвел. Или назовимо га К. Али сећам прошле пут, тврдио сам да ако постоји реално максимална дужина на реч, као што је 40-неки-ак ликова, Максимална дужина подразумева константна вредност. Па стварно, да, то је технички Биг О од 8 или 7, или заиста Биг О К. Али ако постоји коначан капу на шта К. може бити, то је константа. Тако да је Биг О 1 у Крај дана. 

Не у стварном свету. Не када ствари почнете да гледате Ваш сат као трчање вашег програма. То апсолутно ће бити мало спорије него заиста константан Време једним кораком. То ће бити седам или осам корака, али ипак то је много, много боље од алгоритма као Биг О од н тог зависи од величине онога што је у структура података. 

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

И није. То не мора обавезно податке структура треба да гравитирају, јер као хеш табеле, компромис. Која је цена коју плаћате овде? Меморија. Мислим, ово је грозан количина меморије. И не могу да га видим овде, јер аутор ове слике очигледно скраћена све низове, и ми не видимо много је и Б и Ц је и К и И је и З је у овим низовима. Али, они су ту. 

Сваки од ових чворова је читав низ неких 26 или више бајтова, сваки од који представља писмо. 27 у нашем случају, тако да можемо да подржи апострофа у проблем сету. Дакле, ово је заиста структура података, заиста густа и широк. И то само може завршити успорава ствари доле, или барем да кошта много више простора. Али, опет, може се извући поређења овде. 

Подсетимо се мало уназад, ми смо много постигли више узбудљиво време рада у сортирању када користимо неку врсту стапања, али цена смо платили за постизање н лог н за стапање Сортирај потребно да трошимо шта више ресурса? Више простора. Био нам је потребан низ за секундарну копирате људе у, баш као и смо урадили на сцени. Па опет, нема јасних победника, али само субјективна дизајн одлуке доносе. 

У реду. Дакле, шта кажете на ово? Свако ко препозна који Д-сала? ОК. Дакле, нас тројица радимо. Матхер кућа. Дакле, ово је за ручавање Матхер-а. Кладим се да сви имају трпезаријама гомиле каблова овако. И то је заправо представник за нешто што смо очигледно већ видели. Ми смо то звали буквално гомилу. И стека, у погледу свог Меморија рачунара, је место где подаци иду а функције се зову. 

На пример, какве ствари иду на стек у односу на Распоред меморије смо разговарали у протеклих недеља? Шта је то? 

ПУБЛИКА: Позиви на функцијама. 

ДАВИД Малан: Жао ми је. 

ПУБЛИКА: Позиви на функцијама. 

ДАВИД Малан: Позиви на функцијама, али конкретно, шта је унутар сваког од те оквире? Какве ствари? Да. Дакле, локалне променљиве. Кад год ми је требало мало локалном складишту као аргумент, или инт, инт или темп, или шта год локалне променљива, били смо стављајући да је на стек. И ми називамо стек јер наношења слојева те идеје. Само некако поклапа са стварношћу, концепт о томе. 

Али испоставља се да стек може такође може посматрати као структуре података, алтернатива низ, алтернатива на повезане листе. Нешто више концептуално занимљив да и даље може да буде реализован коришћењем било оних ствари, али то је другачија врста структура података подржава, заиста, само две операције. Али, можете да додате на одгајивача карактеристике од ових. Али ово су основе - пусх и поп. 

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

Али занимљива ствар у вези гомиле је да ако ја сада желим да гура другу вредност, као што су 17, а ја гурнути ово на гомилу, ја ћу да урадим једина ствар интуитиван, ја ћу да га ставите тамо где смо људи били склони да га ставите, на врху. Али оно што је интересантно сада је, како могу добити на 9? Знате, ја не без неког напора. 

Дакле, оно што је занимљиво у вези стек који по дизајну, то је ЛИФО структура података. Силли начин за описивање последњи у, први напоље. Дакле, последњи број у у овом тренутку је 17 година. Дакле, ако желим да нешто са поп на стек, може бити само 17. Дакле, ту је обавезан редослед операције овде, где последња ставка у мора да буде први напоље. Дакле акроним, ЛИФО. 

Дакле, зашто би ово могло бити корисно? Да ли су њихове околности у којима бих вам Желим структуру података као што је овај? Па, то је свакако било корисно унутар рачунара. Дакле, јасно оперативни системи користе овај врста структуре података за гомиле. Такође ћемо видети исту идеју када је у питању веб страница. Дакле, ове и следеће недеље и шире, и као што сте почети спровођење веб Странице на језику зове ХТМЛ, можете да заправо користите структуру података као то да се утврди да ли је страна је правилно форматирана. Зато што ћемо видети све веб странице прате врста хијерархије, увлачење која ће, на крају крајева, бити структуре стабла испод хаубе. Дакле, више о томе у само мало. 

Али за сада, хајде да предложи за тренутак, како идемо о представља оно што је стек? Дозволите ми да предложи да се спроводи стек са кодом овако. Дакле, стек ће имати у њему две ствари, низ, звани тацне, Само да буде у складу са демо. И свака од ставки у том низу ће бити типа инт. А капацитет је вероватно оно? Зато што сам написао не пуна дефиниција овде. 

То је вероватно максимум величина низа. И то је вероватно прогласила као оштар дефинишу на врху датотеке, неки врсту константа је и чињеница само капитализације. Дакле, негде капацитет је дефинисан као максимално могуће величине. У међувремену, унутар структуре података познат као стека тамо ће бити само цео број познат једноставно као величине. 

Дакле, ако би требало да заступа ово сада сликовито, хајде да претпоставимо да је ово Цела црна кутија представља моје штос. Унутар тога је две варијабле. Зато ћу да скренем Прво као величине. И други идем извући као низ. 

Али, само да ствари уредно, нормално Скрећем низ као ово, али то је некако лепо ако ми одговара стварности, или одговара ментални модел. Па да, уместо скрене низ вертикално, што је само, опет, уметниково излагање. Заиста није битно шта је је испод хаубе. А ми ћемо рећи да је, подразумевано, Капацитет ће бити три. Дакле, ово ће бити локација 0, то ће бити локација 1, то ће бити локација 2. 

Ако сам подмити са стрес лопта, би Неко као да се попне и покрените укрца овде за тренутак? Ок, видела прво руку. Хајде горе. У реду. Тако да верујем да је Стивен. Хајде горе. У реду. 

Али претпоставимо сада смо уназад на почетни стање света где сам су управо објавио гомилу, и то је ће бити три капацитета. Али величина још није одређен. Касете још није одређен. Дакле, прво пар питања. И дозволите ми да вам дати микрофон, тако да можете активније учествују у томе. 

Дакле, шта је унутра од величине у овом тренутку на време, ако све што сам урадио је прогласио стек са једна линија кода? 

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

Малан ДАВИД: У реду, не много. Да ли знамо шта је унутра од величине, Не знамо шта је унутра овог низа овде? 

Стевен: Само случајни број, зар не? Само - 

Малан ДАВИД: Да, ја ћу да зову код, али случајан - 

Стевен: Ствари. 

ДАВИД Малан: Ствари као случајни 

Стевен: Битс. 

ДАВИД Малан: Битс, зар не? Дакле смеће вредности, зар не? Дакле, пермутација је 0 и 1 је. Остаци ранијих обичаја ове меморије. А ми не знамо шта су вредности су, па смо обично их извући као питање марака. 

Дакле, прва ствар коју смо вероватно ће желети да овде раде - и дозволите ми да ову област у одатле назив - тацне. Шта би требало да покрене свој прилици величина да ако желимо да почнете да користите овај штос? 

Стевен: Траи је под 3.. 

Малан ДАВИД: Па, у реду. Да буде јасно, капацитет је декларисан другде као три. И то је оно што сам користио да издвоји низ. Величина ће да се односи на колико касете су тренутно на стек. 

Стевен: Зеро. 

Малан ДАВИД: Тако да би требало да буде нула. Зато само напред, и са било којим прстом, нацртајте нулу у величини. У реду. И сад, шта је унутар овог овде, не знамо. То су заиста само смеће вредности. Тако да смо могли извући упитнике, али нека ово остане чист одбор за сада јер није битно шта је тамо. Не треба да покрене низ на било шта, јер ако знамо да величина стека је нула, па, не треба да се гледа било шта у Овај низ у сваком случају овом тренутку. 

Сада претпоставимо да сам гурнути број 9 на стек. Како да ажурирате структуру података унутар ове црне кутије? Које вредности треба да се промени? 

Стевен: Унутар - величина? 

Малан ДАВИД: У реду. Величина треба да постане шта? 

Стевен: Величина ће бити један. 

Малан ДАВИД: У реду. Зато величина треба да постане један. Дакле, можете да урадите на неколико начина. Дозволите ми да вам дам, сада ваш Прст је Ерасер. У реду. Онда сада ваш прст је четка. У реду. А сада шта још мора да се промени, очигледно, у структури података? 

Стевен: Идемо из одоздо до 9. 

ДАВИД Малан: 9. ОК, добро. Дакле, још увек није битно шта је на локација један или два, јер су они смеће вредности, али не би требало да смета управо тамо, јер је величина говорећи нам да је само први елемент је заправо легитиман. Тако да сам сада гурнути 17 на листи. Шта се дешава на овој слици? 

Стевен: Дакле, величина ће ићи на два. 

Малан ДАВИД: У реду. Ти си гумица - Упс. Ти си гумицу. 

Стевен: Ерасер. 

Малан ДАВИД: Ти си четка. 

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

Малан ДАВИД: У реду. И шта још? 

Стевен: И онда - 

ДАВИД Малан: Ми гурнуо 17. 

Стевен: Ми се држимо 17 на врху, тако да - 

ДАВИД Малан: Добро, добро. 

Стевен: - спустите доле. 

Малан ДАВИД: У реду. Постаје лако. Нећу да вам помогне овај пут. Пусх 22. 

Стевен: Доне. Постати гумица. Ја постајем четка. И онда ја стављам 22. 

ДАВИД Малан: 22. Одлично. Дакле, још једном. Сада ћу да гура на стеку 26. 

Стевен: Оох. О Боже. Стварно си ме неспремног. 

Малан ДАВИД: Ти ниси види ово долази? 

Стевен: Нисам видео ово долази. Можемо поново Почетни капацитет? 

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

Могли смо да ако смо се вратили у, ми смо редефинисане тацне да се показивач који смо тада користили маллоц за руке сећања на. Јер ако имамо памћење хеап преко маллоц, ми онда би га ослободили. Али, пре него што га ослобађа, можемо прерасподели већи комад меморије, ажурира показивач, и тако даље. Али за сада, ово је заиста Најбоље што можемо да урадимо. Пусх и поп се вероватно дешава да да сигнал на грешку. 

Тако на пример, наше спровођење могао да се врати на притисак који боол раније вратио истина, истина, истина. Али, четврти пут, то ће имати да се врати фалсе, на пример. У реду. Врло добро урађено. Честитам. Ви сте зарадили свој стрес лопта данас. 

[Апплаусе] 

Стевен: Хвала. 

ДАВИД Малан: Хвала. У реду, тако да изгледа да није много за корак напред, зар не? Ми смо описали ову структуру података. Прошло је убедљиво, зар не? Оперативни систем се допада. Очигледно интернет може да користи ово, и друге апликације и даље. Али шта глупо ограничење да смо назад на врсту две недеље ограничава где смо низове фиксне величине. 

Дакле, заиста постоји неколико начини на које може да реши ово. Ми смо могли динамички алоцира низ, није тако тешко да је кодирање као што сам ради овде, али уместо тога поново изјављујући то, само да буде јасно, као нешто овако. Инт * тацне, не одлучујући на капацитет још. Али када сам изјављујем другде наслагани у мом коду, ја онда могу назвати маллоц, добити адресу комад меморије, а ја могу доделити та адреса на носачима. 

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

Али, како би још могао да спроведе ову Иста структура података, потенцијално? Зар не? Осећам се као да смо управо решили овај Проблем као пре недељу дана. Шта је решење овог проблема Стивен је налетео? Тако повезане листе, у праву. 

Ако је проблем што ми слика сами у углу додељујући Унапред премало меморије да онда су се некако баве, добро, Зато не само да се избегне издаје заједно? Зашто не само да се изјасни тацне показивач на чвор, ерго повезану листу, а затим једноставно доделити нових чворова сваки пут Стивен потребно да се уклопе број у структуру података. 

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

Али, то је у реду, зар не, јер Видели смо како се то ради. И када се удобно спровођење нешто као повезана листа, који ћете морати да урадите ако одлучите да спроведе хеш табелу са одвојено Уланчавање за П-СЕТ 6, можете користите је као грађевински блок, или састојак, или у нуле говори, поступак, нешто што сте ставили, те створио своју слагалицу које затим могу поново. Дакле компромиси, али могућих решења да смо заправо видели. 

Тако да често, ви видети сваког годину или две када је Аппле представио нешто ново, а сви лудаци построје ван Аппле продавницу да купи маргинални упграде на хардверу. Ја кажем, да је то у реду, јер Ја сам један од тих људи. Дакле, какве структуре података може представљати ову реалност? 

Па, назовимо то ред, ред. Тако британски бих га обично ред у сваком случају, тако да је лепо име. А две операције које куеуе ће подржати ћемо позвати енкуеуе рад и декуеуе операција, који су слични у дух да гура и поп. То је само некако другачије у конвенција, оно што ми зовемо ове. Али енкуеуе нешто значи додавање или га убаците у структури података. Да декуеуе значи да га уклоните. Али, док је ЛИФО стек података структура, ред је први у, Први од структуре података. 

Ако сте прва особа у реду, ви ћете бити прва особа која се од линије и купите свој нови уређај. Замислите како би узнемирен би ти људи били ако Аппле уместо тога користио гомилу, за пример, да спроведе бербе до вашег новом играчком. Дакле редови смисла, свакако, и можемо мислити свих врста апликације, вероватно, због редова, нарочито када желите правичност. Дакле, како бисмо могли да примене их као структура података? 

Па, ја предлажем да би могли да треба да то овако. Зато ћу сада имати бројеве. Дакле, ми ћемо наставити да га једноставно и не обавезно разговарати у смислу тацне. Само бројеви који људи стечен. Капацитет ће, опет, поправи укупан број људи који могу да буду у Ова линија, као и три или све друге вредности. 

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

Па, како је то слика ће се променити? Вероватно могу поново користити највише ове слике. Дозволите ми да иде напред и избрисати оно што је овде. Ми ћемо дати ово мало друго име овде. Хајде да се ослободимо 17, хајде да се отараси од 9, хајде да се отараси 3. И да додам једну другу ствар. Ја предлажем да треба да пратите предњи део листе, што је само ће бити инт као добро. И ми ћемо да га једноставно. Нема повезана листа за сада. 

Ми ћемо признати да ћемо налетети на ове границе. Али шта ја желим да видим десити овај пут? Тако да претпостављам да иде напред и први особа долази у линији, а то је број 9.. Ми немамо муда стреса. Да ли могу да краду, кажем, две или три особе? Један, два, три? Хајде горе. Право са фронта, јер направићемо ово брзо. 

Свако од вас ће сада бити вентилатор дечак у реду на Аппле. Нећете добијати Аппле хардвера на крају ове ипак. У реду. Дакле, ти си број 9, ти си број 17, број 22. То су произвољне бројеве, као што је Студент ИД-ови или ситница. А у само једном тренутку, почнимо да бисте додали ствари. А ја ћу покренути таблу овде овај пут. 

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

Дакле, ако је број 9, ти си први тамо у 5 ујутру, само напред и да се построје, или ноћи. ОК. Дакле, сада је овде 9. Дакле, 9 је у предњем делу листе. Дакле, ја ћу да наставим и ажурирање Величина овог актуелним подацима структура да не буде више 0, али да буде 1. Ја ћу да ставим у 9 испред листе. Дозволите ми да иде напред и пребаците екран тако да можемо да видимо овде поред нас. 

И сада шта желим да стави на фронту? Ја ћу пратити да испред реда одмах је на локацији 0. Јер шта је следеће ће се десити? Па, претпостављам да сада ја енкуеуе 17, као добро. Дакле, хоп у складу тамо. А опет, некако врата за продавница ће бити овде. Зато сам додао 17. И мада су ови момци блокирају екрану, то је у реду, зато можемо да га видимо овде. Извините. 

ПУБЛИКА: Можемо да идемо - 

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

У ствари, да видимо то. Пре него што убаците 22, хајде да само напред и декуеуе 9. Како се зовеш? 

ПУБЛИКА: Јаке. 

ДАВИД Малан: Џејк ће да се сада декуеуед. Тако сте добили да хода у продавницу. И да се претварам продавница је тамо. Шта сада треба - дит-дит-дит! Оно што треба да се деси? Дизајн одлука. Дакле, није лоше инстинкт, али - како ти је име? 

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

ДАВИД Малан: Дејвид. Дакле, шта је Дејвид урадио? Он је покушавао да некако поправи података структура и покрет од његовог места Јаке у бившој локацији. И то је у реду, ако смо вољни да прихвате као имплементациони детаљ. Али прво, хајде да ажурирају податке структуре него што то урадимо. Зато што ја не допада идеја свих људи померања у овој линији. 

То је велика ствар ако Давид то ради са један корак, али опет, мислим да се вратио када смо имали осам волонтера на фази и што смо урадили као убацивања врста, где смо морали да почну све се креће око. То сам скупо, зар не? То се тргнем о великом О од н, Биг О од н на квадрат поново. Она не осећа као идеалан исход. 

Дакле, хајде да ажурирате ово. Дакле, величина реда више није 2. Сада је једноставно 1. Али, ја сада могу ажурирати нешто Нисам раније ажурира, испред листе. Ја само могу рећи, јесте да је локација 1? Тако да сада имамо овде смеће вредност, смеће вредности овде, а Давид у средином овог смећа. Међутим, структура података је још увек нетакнут. 

А у ствари, не морате чак ни да променити Јаке бивши број 9, јер кога је брига. Имам довољно информација сада у величина да знам да постоји једна особа у овај ред. А ја знам да је та особа је на локацији 1, а не 0.. Ја не рачунам. Дакле 1, као добро. Дакле, структура података је још увек у реду. 

Па, шта се даље дешава? Хајде да енкуеуе - како ти је име? 

ПУБЛИКА: Цаллен. 

ДАВИД Малан: Цаллен. Хајде да се енкуеуе Цаллен, и 22 је сада у реду. Шта сада треба да промени овде? Предњи неће променити, очигледно. Величина ће се променити да буде 2 поново. И 22 завршава овде, 9 је и даље присутан, али то је ефикасно смеће вредност сада. То је само остатак прошлости Јаке. 

Па сад шта се дешава ако Ја декуеуе Давида? Још једна операција, декуеуе Дејвид. Могли би да се мењају, али ја предлажем хајде урадите мало рада могуће. Сада ми је структура података иде Назад у величини од 2 до 1. Али, испред реда Сада постаје 2. Не треба да се промени ове бројеве још увек, зато што су само смеће вредности. 

Али сада шта се дешава? Рецимо да сам се енкуеуе, 26? Осећам се као да припадам овде. Тако сам се енкуеуед. Тако сам некако припада овде. А чак и ако не сасвим Ценим то визуелно на сцени, јер имамо довољно простора, да би требало није стајао овде, зашто? 

ПУБЛИКА: Ви сте у ауту. 

Малан ДАВИД: Тако је. Ја сам у ауту. Ја сам индексиране изван границе овог низа. Стварно би требало да буде у једној од три могуће локације. Сада, где је најприродније да иду? Предлажем да левериџом недељу један трик. Мод оператер, проценат. Зато ја стојим на технички Локација 3, али ја 3 мод капацитета, па 3, знак за проценат, 3 - капацитет је 3. Шта је то? Шта је остатак када ви поделите 3 за 3? 0. 

Тако да ме ставља се Џејк је, што је заправо добро. Дакле, сада имплементација ове ствари ће се бити мало главобоље. То је заиста само једна линија главобоље, кода. Али барем сада има за смеће ту вредност, али има две легитимне интс овде. А ја тврдим да сада смо урадили управо оно што ми треба да урадимо све док можемо променити оно што Џејка вредност је требало да буде 26.. 

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

Сва питања на стек, или овај ред? 

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

ДАВИД Малан: Управо тако. Морам да знам величину низа јер морам да знам тачно како многи од ових вредности су легитимни, и тако да ја могу да нађем где да стави следећу особу. Тачно. Величина је - у ствари, нисмо ажурирали ово још. Ја сам додао на 26. Величина је сада, не 1, него 2. Дакле, сада је то заиста помаже ми да пронађем носилац листе, што није 0, не 1, али је 2. Предњи део листе је заиста број 22. Зато што је дошао у први, тако да треба бити дозвољено у продавницу пре мене, иако визуелно стојим ближе продавницу. 

У реду? Аплауз за ове момке а ми ћемо их пустити напоље. 

[Апплаусе] 

Малан ДАВИД: Ја могу да задржите лежиште. Могли смо да видимо шта ће се десити ако желите, али можда не. У реду. И шта сад нас то води? Па, дозволите ми да предложи да постоји Неколико других структуре података смо могли бисте додали нашем комплет алата који ће заправо бити сасвим, сасвим релевантан да зароне у веб ствари. Што опет, има неку врсту везе на дрвећу у облику нешто што се зове ДОМ, документ објектни модел. Али, видећемо више да је пре дуго. 

Дозволите ми дефиницији предлажем да позовите дрво сада оно што можда знате како више породичног стабла, где сте има неки предак у Корени дрвета. Патријархална или матријарх на самом врху дрвета. Без супружника, у овом случају. Али, ми сада имамо оно што ћемо назвати Деца, која су чворови који виси ван левом или десном дете дете, стрелице као што је представљено овде. 

Другим речима, у структури стабла података на рачунару, дрво има нулу или више чворова. Ако има бар један чвор, то се зове корен. То су ствари које визуелно скрећемо на врху. И тај чвор, као и сваки други чвор, може имати нула, један, или два, или три, или међутим многа деца структура података подржава. У овом случају, корен, чување вредност један, има двоје деце, 2 и 3, тако да смо углавном зову 2 леви 3. дете и право дете. 

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

Дакле, како бисмо могли спровести тај дрво има само двоје деце максимално? Зваћемо га бинарно стабло. Би опет значи, два, у овом случај, као са бинарни. И тако она може имати нула, један, или двоје деце максимално. 

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

Тако да ја предлажем је имплементација од функција претраге. Имајући у виду два улаза - тако да мислим да је ово као црну кутију. Имајући у виду два улаза, н, инт, и показивач на дрвету, показивач чвор, или заиста корен дрвета, ја Тврдња да се ова функција вратити тачно или нетачно, да вредност н је унутар овог дрвета. 

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

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

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

Другим речима, ако сте били да скрене дрво се, све ове цифре су пажљиво избалансирана овако, тако да ако имате 55 као корен, 33 може да иде своје леве стране, јер је то мање од 55 година. 77 могу да иду у своје право, зато што то је већи од 55. Али сада приметио, исту дефиницију, то је вербално рекурзивна дефиниција, Пријава за 33. 33 је лево дете мора да буде мањи од њега, и 33 је у праву дете, 44, мора да буде већи од њега. 

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

Па, према овој декларацији, лево је само показивач, тако да само знаци да сам пролази за претрагу функцију показивач другачији, односно који представља Моја лева детета дрво. Дакле, у овом случају, показивач на 33, ако ово је наш узорак улаз међувремену, ако н веће вредности брзине тренутни чвор у дрвету, па сам ићи напред и фунта у другом правац и само да кажем, ја не знам знам да ли је то вредност н на дрвету, али ја знам да је то, то је моја доле Право грана, да тако кажем. Тако да ме позива рекурзивно претрагу, пролазећи опет н, али у пролазу показивач на десну детету. 

Другим речима, ако Ја сам тренутно на 55 и ја сам у потрази за 99, ја знам да је 99 је већи од 55, па као што сам поцепао именику недеља пре и ми смо је у праву, ми смо на сличан ићи овде. И не знам да ли је то у мојој десној дете, а то није, 77 је ту, али Знам да је у том правцу. Тако да ја зовем претрагу на десну дете, 77, и нека цифра за претрагу из постоји ако је ово 99 у произвољно Пример је заиста постојала. 

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

Дакле, ако сам у потрази за 55 у овом тренутку у причи, да је огранак Дрво ће се вратити истина. Дакле, оно што је занимљиво је то што смо у ствари, за разлику од недеље прошлост, ми смо некако у два случаја базу. И не морају да бити све на врху. Врх је основни случај, јер ако Дрво је нулл, нема шта да се уради. Само се вратите фиксирана вредност фалсе. 

Доњи грана је врста подразумевани, при чему, ако смо проверили за нулл, ми смо проверили да ли је то требало да буде отишао, али то не би требало да буде, ми смо проверава да ли је требало да буде у праву, али то не би требало да буде, јасно је да мора да буде тамо где смо. То је основни случај. Дакле, постоје два случаја рекурзивне сендвичу у средини. Али ја могао написати ово у било ком редоследу. Само сам мислио да некако осећао природно да прво проверите могуће грешке, затим проверите лево, а затим проверите десно, онда Претпостављам да сте на чвору Ви у ствари тражите. 

Дакле, зашто би ово могло бити корисно? Тако испада - и пусти ме да скочите на задиркивање Овде је то у Интернету. Идемо да почнете да користите не програмски језик у почетку, али Маркуп Лангуаге. Маркерски језик био онај који је сличне по духу програма језик, али то ти не даје способност да се логички изрази. То само вам даје могућност да изражавају се структурално. 

Где желите да ставите нешто на страници, веб страница? Које боје желите да га направи? Шта величину желите да га направи? Шта речи и ти заправо Желим на веб страници? Дакле, то је језик за означавање. Али, онда ћемо врло брзо увести Јава, која је пуноправни програмског језика. Врло слично синтаксички у изгледу на Ц, али то ће имати неке лепо, моћнији, више корисник пријатан изглед. 

А једна од фрустрација на овај тачка у семестру је да ћемо ускоро спровести Спеллер у далеко мање линија кода које користе друге језике од Ц дозвољава себи, али је из разлога ускоро ћемо разумети. То ће бити први такав веб страница. То ће бити потпуно ундервхелминг, Први правимо. То је једноставно ће рећи, здраво свет. Али, ако никада нисте видели пре, ово је ХТМЛ, ХиперТект Маркуп Лангуаге. 

Ако одете до одређеног опцију менија у највише било који бровсер, на било којој страници на Интернет, можете видети ХТМЛ да неки људи писали да креирати ту страницу. И то вероватно не изгледа као кратак или као уредан и ово. Али, то ће следити модел ових отворене заграде и црте и слова и бројеве потенцијално. 

Мислио сам да ти дам задиркивање онога што ћете бити у стању да уради након узимања ЦС50. Пусти ме да цс.харвард.еду / Роб, нашим сопственим Роб Бовден страница. Он је ово за нас. Дакле, ускоро ћете бити у могућности да то урадимо. И, шта сте чули јутрос - оно што сте чули јутрос - 

[ХАМСТЕР ДАНЦЕ МУСИЦ] 

- Бићеш у стању да направи ово. То нас очекује у среду. Ми ћемо се онда. 

[ХАМСТЕР ДАНЦЕ МУСИЦ] ДАВИД Малан: На ​​следећем ЦС50 -