[Мусиц плаиинг] ДАВИД Малан: Ово је ЦС50. А ово је и почетак и енд-- као литералли-- скоро крај од недеље шест. 

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

ПУБЛИКА: [неразумљиво] ДАВИД Малан: Заиста. И још забавно, не дај Боже, држимо једно предавање у петак на почетку семестра, то је оно што смо видели да се дешава. Тако да данас, ми учествују у мало више о структурама података. И да вам више добар ментални модел за проблеме у пет, која је сада ван. Грешке, при чему, ћемо рука коју текстуалну датотеку око 100.000 Плус енглеске речи, и ћеш имати да смислим како да паметно их учита у меморију, у РАМ, користећи неке податке Структура по вашем избору. 

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

ПУБЛИКА: Уношење. 

ДАВИД Малан: Уношење. Шта сте под тим мислили? 

ПУБЛИКА: било где дуж Листа [неразумљиво]. 

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

Шта друго је предност о повезане листе? Да? 

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

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

ПУБЛИКА: Не директног приступа. 

ДАВИД Малан: Нема директног приступа. Али кога је брига? Рандом аццесс не звучи убедљиво. 

ПУБЛИКА: [неразумљиво] ДАВИД Малан: Тачно. Ако желите да имате одређена алгоритхм-- и пусти ме заправо предлаже бинарни претрага посебно, којој је једна смо користили доста бит-- Ако немате случајан приступ, Ви не можете то урадити Једноставна математика налажења попут средњег елемента и скакање право на њу. Уместо тога морају да почну у прва елемент и линеарно претраживање од лева на десно ако желите да пронађете средње или било који други елемент. 

ПУБЛИКА: Вероватно се више меморије. 

ДАВИД Малан: потребно је више меморије. Где је тај додатни коштају из меморије? 

ПУБЛИКА: [неразумљиво] ДАВИД Малан: Тачно. У том случају овде, имали смо повезана листа за целих бројева, а ипак смо дуплирање количина меморије морамо по и чување ових савета. Сада мање велику ствар као Ваши Структуре гет већи а ви чување није број, али Можда студент или неки други предмет. Али поента сигурно остаје. И тако број операција на повезаним листама су се звали били Биг О на н-- линеарни. Ствари као што су убацивање или претреса или брисање у случају елемент Десило се да на самом крају списак било да је сортирана или не. 

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

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

Дакле, ово је техника која је генерално познати као хасхинг-- Х-А-С-Х-- који обично значи узимање у улаз и коришћење ИНПУТ израчунати вредност, генерално број и то број је индекс у складиште контејнер, као низа. Другим речима, ја можда има хасх функција, као ја у мојој глави, да ако видим да је неко Назив који почиње, Ја ћу се карта која на нулу у мојој глави. И ако видим некога са З, ја сам ће карта која до 25. у мојој глави а затим ставити у последњи највише гомила. 

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

ПУБЛИКА: Минус А. 

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

Дакле, можда се сећате сте заокружили ваше Име демонстратор је на насловној страни. И имена ТФ биле су организоване у ове колоне по абецедном реду, Па, веровали или не, када сви 80 ПЛУС нас окупили друга ноћ разред, последњи корак у нашем процесу оцењивања је да се емитују квизове у велики простор пода на [неразумљиво] и да постави свачијим квизове се у потпуно налогу својих ТФ-их Имена на поклопцу, јер онда је много лакше за нас да тражи кроз тај користећи линеарну претраживање или нека врста интелигенције за ТФ да нађете њену или својих ученика тестовима. 

Дакле, та идеја о хеширање да ћете видети је веома моћан је заправо прилично уобичајена и веома интуитиван, слично можда деле и цонкуер је у недељу нула. Ја брзо напред у Хацкатхон Пре пар година. То је био и Замила пар Остали студенти особље греетинг како су дошли. И ми смо имали гомилу савијања столови постоје са именима. А имали смо име ознаке организовани са као и преко тамо а Зс тамо. И тако један од веома паметно Поздрав ово написао као упутства за дан. И у 12. недељи семестра ове све је савршено логично и свима знао шта да радим. Али кад год сам куеуед на исти начин, сте имплементацију Исти појам хашиша. Па хајде да га мало озваничи. Ево низ. Је привукло да буде мало широка само да прикаже, визуелно, да би ми ставили жице у овако нешто. А ово је низ јасно величине 26 укупно. А ствар се зове Табела произвољно. Али ово је само уметника излагање шта може бити хасх табела. 

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

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

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

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

Сада раније некако варао и урадио ово или ја некако сложен њих изнад другога. Али то неће летети у коду. Па где сам могао ставити Други ученик чије име је да све што сам имала је ово доступно Табела простор? И ја сам користио три слота и ИТ Изгледа као да је само неколико других. Шта би ти урадио? ПУБЛИКА: [неразумљиво] ДАВИД Малан: Да. Можда хајде да буде једноставно. Зар не? То не одговара где желим да га ставим. Дакле, ја ћу да га ставим Технички где Б ће ићи. Сада, наравно, ја почињем да се сликам у ћошак. Ако дођем до студента чије име је заправо Б, Сада Б биће померен мало напред, као што се може догодити, Иеп, ако је Б, сада мора да иде овде. 

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

Сада, цена се сада плаћа за ово решење је шта? Имамо одређену величину низ, а кад убаците имена у њега, бар у почетку, што је руннинг време убацивања за стављање ученичких квизови у правим кашике? Биг О чега? 

ПУБЛИКА: н. ДАВИД Малан: Чуо сам Биг О н. Није истина. Али ми ћемо задиркују Апарт Зашто се само тренутак. Шта друго може да буде? 

ПУБЛИКА: [неразумљиво] ДАВИД Малан: И дозволите ми да то урадим визуелно. Претпостављам да је ово писмо С. 

ПУБЛИКА: То је један. ДАВИД Малан: То је један. Зар не? То је низ, који значи да имамо случајан приступ. И ако мислимо ово као нуле и то као 25, и ми схватамо да, Ох, овде је мој улаз С, Ја свакако могу претворити С, АСЦИИ знак, на одговарајућим бројем између нула и 25 и онда одмах ставите га тамо где припада. 

Али, наравно, чим стигнем у Друга особа која се зове или Б или Ц на крају, ако сам се користи линеарни прескок као мој решење, руннинг време убацивање у најгорем случају заправо ће да се пренесе у шта? И ја сам чуо овде правилно рано. ПУБЛИКА: [неразумљиво] ДАВИД Малан: Дакле, то је заиста једном н имате довољно велики скуп података. Дакле, с једне стране, ако Ваш низ је довољно велики и ваши подаци су ретки довољно, добили прелепу сталну пут. Али чим почнете све више и више елемената, и само статистички добијате више људи са словом Као њихово име или слово Б, то потенцијално могао пренесе у нешто линеарно. Дакле, не баш савршен. Тако да смо могли боље? 

Па, шта је наш решење пре Вхен Ве Желим да имају више од динамичности нешто попут низа дозвољено? ПУБЛИКА: [неразумљиво] ДАВИД Малан: Шта смо представити? Да. Дакле, повезана листа. Па, хајде да видимо шта повезан Листа може да уради за нас, уместо. Па, дозволите ми да предлажем да нацртати слику на следећи начин. Сада је ово другачије Слика од примера из другог текста, заправо, да се је заправо користи низ величине 31. И овај аутор једноставно одлучили да размотре жице а не на основу имена те особе, али на основу њихових Биртхдатес. Без обзира на месецу, они схватили Ако сте рођени на први месец или 31. у месецу, аутор ће хасх основу те вредности, како би проширила имена напоље мало више од 26 тачака може да дозволи. И можда је мало више униформа него иде са словима абецеде, јер наравно, вероватно постоји више људи у свету са именима које почињу са него сигурно неки други слова азбуке. Дакле, можда је мало равномерније, претпостављајући равномернија беба широм месец дана. 

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

ПУБЛИКА: повезане листе. 

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

Сада, у складу са тим, шта је време ради сада? Ако желим да убаците неког чији рођендан је 31. октобар, где се он или она оде? У реду. На самом дну, где пише 31. И то је савршено. То је био константан време. Али, шта ако нађемо неког другог чији је рођендан, хајде да видимо, Октобар, новембар, децембар 31? Где је он или она ће ићи? Иста ствар. Тво Степ ипак. То је константна мада, зар не? У реду. У овом тренутку је. Али у општем случају, Што више људи саберемо, пробабилистицалли, идемо да се све више судара. 

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

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

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

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

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

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

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

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

Зато желим да убаците стринг Давен у структуру података. Шта ако ја не користим хасх табеле, али ја користим нешто што је више налик дрво као породично стабло, где имате неки корен у врха и потом чворови и лишће да иду доле и споља. Претпоставимо онда, да сам Желим да убаците Давен с у оно што је тренутно празна листа. Ја ћу да урадите следеће: Ја сам ће створити чвор у овој породици Трее налик структура података која изгледа као мали овога, сваки од којих правоугаоника је, рецимо, за сада 26 елемената у њему. И сваки од ћелија у овом низу иде да представља слово абецеде. 

Конкретно, ја ћу третирати Ово је, затим Б, па Ц, затим Д, овај овде. Дакле, ово ће ефикасно представљају слово Д. Али да убаците све Давен је име морам да урадим нешто. Тако да прво идем да размотре, да се тако изразим. Идем да погледам прво слово у Давен с којима је очигледно Д, и ја ћу да издвоји чвор који изгледа овако-- велику правоугаоник велики Довољно да се опреми целу абецеду. 

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

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

Онда ћемо Сматрамо да је ово В. А онда овде ћемо индексу доле из В у шта ћемо размотрити Е. А онда одатле ћемо иди имати један од ових чворова овде. А сада имамо одговорити на то питање. Морам да некако указује на то да смо на крају низа Давен. Тако да сам могао вратити га на НУЛЛ. 

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

Дакле, шта можемо да урадимо уместо је третира сваки од ових елемената као можда има два елементи у њима. Један је показивач, заиста, као што сам радила. Тако да сваки од тих кутија није само једна ћелија. Али, шта ако врх --виберите-- дно један је ће бити нула, јер је нема Девенпорт још. Шта ако неко врх је нека посебна вредност? И то ће бити мало тешко је ово величина драв. Али, претпоставимо да је само ознака потврде. Проверите. Д--В-Е-Н је стринг у овој структури података. 

У међувремену, ако бих имала више простора овде, ја могу да урадим П-О-Р-Т, и ја могла ставити чек у чвор која има слово Т на самом крају. Дакле, ово је масовно комплекс изгледају структуре података. И мој рукопис свакако не помаже. Али, ако сам хтео да убаците нешто друго, размотримо шта ћемо урадити. Ако бисмо желели да стави Давида у, ћемо пратити исту логику, Д-А-В, али сада морам да кажем у следећа Не елеменат из Е, али од И до Д. Тако да ће бити више чворова у овом дрвету. Ми ћемо имати више позива маллоц. Али ја не желим да збрка изображениа. Па хајде да погледамо, уместо једном који је био пре-формулисана овако са не тачка, тачка, тачке, али само скраћени низови. Али сваки од чворова на овом дрвету овде представља исти ствар-- низ Реј величине 26. 

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

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

Јер иако, у овом тренутку, ја сам само коришћењем Д'с показивач и И В и Ес и НС, Губим се паклени много меморије. Али, где проводим једног ресурса, Склон сам да не добију неки други. Дакле, ако сам проводим више простора, шта је вероватно нада? Да ја проводим мање шта? ПУБЛИКА: Мање времена. ДАВИД Малан: Време. Зашто би то било? Па, шта је уметање време, у смислу сада Биг О, од имена као Давен или Давенпорт или Давид? Па, Давен је пет корака. Давенпорт би девет корака, тако да би било још неколико корака. Давид би бити пет корака као добро. Дакле, то су бетон бројеви, али сигурно има горња граница дужина нечијег имена. И заиста, у проблему комплета пет спецификације, ћемо предложити да је то нешто То је 40-ак-нека карактера. 

Реално, нико нема бескрајно дуго име, што ће рећи да је дужина име или дужина низа бисмо могли имају одређени стање Структура је вероватно шта? То је константа. Зар не? То може бити велика као константа 40-нешто, али је константан. И то нема зависност колико друга имена су у тој структури података. Другим речима, ако Желео сам да убаците Колтон или Габријел или Роб или Замила или Алисон или Белинда или било којим другим имена од запослених у овом података Структура је руннинг тиме убацивања друга имена ће бити на свим угроженим по томе колико и друге елементе У структури података Већ? Није. Зар не? Јер смо ефикасно користимо Овај вишеслојни хасх табела. А руннинг време било који од ових операција не зависи од броја елементи који су у структури података или да се евентуално ће бити у структури података, али на дужини шта конкретно? 

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

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

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

Сада Меанвхиле-- О, питање. 

ПУБЛИКА: Шта је боол реч? 

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

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

Има ли још питања на покушаја? Да. 

ПУБЛИКА: Шта је преклапања? Шта ако имате Дејв и Давен? ДАВИД Малан: Савршено. Шта ако имате Дејв и Давен? Дакле, ако смо убацили, кажу надимак, фор Давид-- Даве-- Д-А-В-Е? То је заправо супер једноставна. Тако да само ћемо предузети четири корака. Д-А-В-Е. И шта ја имам да радим кад сам ударио ту четврту чвор? Само да проверим. Већ смо да кренемо. Доне. Четири корака. Константна време асимптотски. И сада смо рекли да оба Даве и Давен су жице у структури. Дакле, није проблем. И приметили како присуство од Давен није успео предузме више времена или мање Време за Дејв и обрнуто. 

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

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

Дакле један, и заправо, нека ми не да зарони у то. Хајде да уместо тога ово. Погледајмо онај који је скоро Иста идеја, али то је мало праведније. Зар не? Ако сте један од тих навијачких дечака или девојке које стварно воли Аппле Продуцтс Пробудили сте се и у 3:00 да се построје у некој продавници да бисте добили најновију иПхоне, ти можда чекању овако. 

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

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

ПУБЛИКА: ред. ДАВИД Малан: Па, ред. Наравно. Шта друго? 

ПУБЛИКА: линкед лист. 

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

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

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

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

Али оно што је заиста згодно о томе превише, Само да вас задиркује са мало кода, рецалл рецурсион од неко време назад, при чему пишете функцију која се зове. Ово је лепа прилика да спроведе нешто као рекурзије, јер сматрам да. 

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

ПУБЛИКА: мањих лево. 

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

Сада како да нађете број 44? Ти би почети у корену и кажу, хм. 55 није 44 Зато желим да идем Право или да Желим да идем лево? Па, очигледно хоћеш да идеш лево. Па то је као на телефону Књига пример у бинарном потрази уопште. Али ми њено спровођење Сада мало динамички него низ може да дозволи. И, у ствари, ако желите да погледате у коду, на први поглед сигуран. Изгледа као гомила линија. Али то је дивно једноставно. Ако желите да спроведе функције позвао претрага чија је сврха у животу је да тражи вредност попут н, цео број, а ви прошли у једном поинтер-- показивач на чвор корена, Уместо тога, од тог дрвета из којих можете да приступите све друго, приметили како искрено можете имплементирати логику. Ако дрво нулл, очигледно није ту. Хајде само ретурн. Зар не? Ако га предате ништа, тамо нема ништа. 

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

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

У међувремену, ако је н већи од чвор Ја тренутно гледам, Ја претраживање десне стране. Елсе, ако дрво није нулл, и ако елемент није лево а није у праву, што је предивно случај? Ми смо заправо смо нашли у чвор питање, па се враћамо истина. 

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

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

[ВИДЕО РЕПРОДУКЦИЈА] 

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