[Мусиц плаиинг] Анди Пенг: Добродошли у недељу 6. члана. Одступио смо од нашег стандарда секција време уторак дан ове дивне недељу ујутро. Хвала вам за све који придружио ме данас, али озбиљно, Велики аплауз. То је прилично велики напор. Скоро нисам ни успети у времену, али то је у реду. Дакле, знам да сви ви Управо сам стигао до квизу. Пре свега, добродошли у друга страна о томе. Друго, ми ћемо разговарати о томе. Причаћемо о квизу. Причаћемо о томе како радите у класи. Бићеш добро. Имам своје квизове за ви на крају овде, па ако хоћете да погледам, потпуно у реду. Тако брзо пре него што почнемо, Тхе програм за данас је следећи. Као што можете видети, ми смо у основи брз печења кроз гомила структуре података стварно, стварно, стварно брзо. Дакле, као што је, неће бити Супер интерактивни данас. То ће бити нека врста виче ми ствари које ви, и ако те збуни, ако идем пребрзо, јави ми. Они су само различите податке структуре, ау оквиру Ваше псет за ово Предстојећа недеља, ви ћете бити затражено да спроведе једну од њих, можда два њих-- две од њих у вашем псет. У реду, тако да ћу да почнем са неким најавама. Идемо преко гомиле и редовима више у Дубина него што смо радили пре квизу. Идемо преко повезан лист поново, поново, више у дубину него што смо имали пре квизу. А онда ћемо причати о хасх столови, дрвеће и покушава, који сви су прилично потребно за ваше псет. А онда ћемо ићи преко неке корисни савети о псет5. У реду, тако квиз 0. Просечна је био 58%. Било је врло ниска, па ви све јесте веома, веома добро у складу с тим. Прилично, правило је да ако сте унутар стандардна девијација средине нарочито јер смо у мање удобно секција, ти си потпуно у реду. Ви сте на правом путу. Живот је добар. Знам да је страшно мислити да Добио сам као 40% на овом квизу. Ја ћу успети овај предмет. Обећавам ти, ниси успети класу. Ти си потпуно у реду. За оне од вас који су добили преко средња, импресивна, импресивно, као, озбиљно добро урађено. Имам их са собом. Слободно доћи да их на крају одељку. Јавите ми ако имате било питања, питања са њима. Ако се томе дода свој резултат у праву, јавите нам. У реду, тако да псет5, ово је стварно чудно недеље за Иале у смислу да је наша псет је због Среда у подне, укључујући покојни дан, тако да заправо теоретски због уторак у подне. Вероватно нико завршен у уторак у подне. То је потпуно у реду. Ми ћемо имати радног времена вечерас као у понедељак увече. И све од секција ове недеље ће заправо бити претворена у радионицама, тако да слободно поп у свака секција желите, и они ће бити нека врста мини псет радионице за помоћ у вези са тим. Дакле, као што је, ово је једини део где смо наставни материјал. Сви други делови ће се усредсредити искључиво на помоћ за псет. Да? ПУБЛИКА: Где су радно време? Анди Пенг: Радно време вечерас Ох, добро питање. Мислим да је радно време вечерас су у Теал или на Цоммонс. Ако сте проверили онлајн ЦС50 а ви идите на радног времена, треба да постоји распоред који вам говори где су сви од њих су. Ја знам ни вечерас или сутра је тиркизна, и мислим да имамо Цоммонс за друге ноћи. Нисам сигуран. Добро питање. Проверите на ЦС50. Цоол, питања у вези са распоред за следећи слично три дана? Обећавам момци попут Давида рекао је, ово је врх брда. Ви сте готово тамо. Само још три дана. Иди тамо, и онда ћемо сви доћи. Имаћемо леп ЦС-фрее паузу. Добродошли назад. Ми ћемо зарони у веб програмирање и развој, ствари које су врло забавно поређењу на неке друге псетс. И то ће бити хладан и ћемо имати пуно забаве. Имаћемо више бомбона. Извините за слаткише. Заборавио сам слаткише. То је био тежак дан. Дакле, ви сте скоро тамо, и заиста сам поносан на вас. У реду, тако да гомила. Ко је волео питање о Јацк и његова одећа на квизу? Нико? У реду, то је у реду. Дакле, у суштини као што можете слика Џек, овај момак овде, воли да одећу из врха стека, и он га ставља назад на стек Након што је урађено. Дакле, на овај начин, никада није Изгледа да добити до дну стацк у својој одећи. Дакле, ова врста описује основна структура података како се имплементира стек. У суштини, мислим олуја са стацк као и сваки стек објеката где сте ставили ствари на врху, и онда их искочити из врха. Дакле, ЛИФО је акроним волимо да Користи, Ласт ин, фирст оут. И тако трајати у на врху стек је прва која излази. И тако два термина ми волимо да се друже са тим се зове гурај и поп. Када притиснете нешто на стацк, и ви то поп назад. И тако претпостављам да је ово нека врста апстрактан појам за оне од вас који желе да виде Лике Ан Имплементација ове у стварном свету. Колико сте написали есеј можда као сат пре него што је због, а ти случајно избрисане велики комад од тога, као случајно? А шта онда раде контрола користимо да га вратим? Контрола З, зар не? Цонтрол-З, тако да износ времена да контрола-З је спасао живот, је спасао дупе, сваки пут који је реализован кроз гомиле. У суштини све информације то је на Ворд документ, бива гура и убацио по вољи. И тако у суштини кад вас делете ништа, ти то поп назад. И онда ако вам је потребна вратио, хвала пусх ит, то је оно што контрола-Ц нема. И тако стварно функција свет како једноставне структуре података може да помогне у вашем свакодневном животу. Дакле, струцт је начин на који Ми смо заправо створити гомилу. Ми дефинишемо тип градитеља, а затим зовемо се слажу на дну. И у стеку, имамо два параметра да смо у суштини може да манипулише, тако да имамо цхар стар стрингс капацитета. Све што се ради ствара низ да може да складишти шта год желиш које можемо одредити своје капацитете. Капацитет је само највећа количина ставке можемо ставити у овај низ. Инт величина је бројач који држи прати колико предмета су тренутно у стеку. Онда можемо пратити, А, и колика је стварна стек, и Б, колико те стека смо пунили јер не желимо да преплавити шта је наш капацитет је. Тако, на пример, овај диван питање је на квизу. У суштини како да наставимо на врху гомиле. Прилично једноставно. Ако погледате, ћемо проћи кроз ово. Ако [неразумљиво] сизе-- запамтите, кад год желите да приступите било параметар у оквиру струцт, ти име струцт.параметер. У овом случају, с је име нашег стека. Желимо да приступите величину о томе, тако да радимо с.сизе. Дакле, докле год величина није једнак капацитету или онолико дуго као што је мање од капацитета, или ће радити овде. Ви желите да приступите унутрашњости Ваше стека, тако с.стрингс, и ти ћеш да се тај нови број да желите да убаците у тамо. Рецимо да ће желети да убаците инт н на стек, можемо да урадимо с.стрингс, држачи, с.сизе једнако н. Пошто је величина где смо Тренутно су у стеку ако ћемо да гура да, ми само приступ где год величина је, тренутна пуноћа стека, а ми гурните инт н на њега. И онда желите да се уверите да Такође смо се увецава величину н, тако да можемо пратити имамо додао још један ствар стека. Сада имамо веће величине. Да ли ово овде смисла сви, како логички то ради? Било је брзо. ПУБЛИКА: Да ли идете преко су с.стрингсс.стрингс [с.сизе] опет? Анди Пенг: Наравно, па шта с.сизе тренутно нам дати? ПУБЛИКА: То је тренутна величина. Анди Пенг: Тачно, тако да је тренутна индекс који наша величина је у, па желимо да стави нову цео да желимо да убаците у с.сизе. Да ли то има смисла? Зато што с.стрингс, све то је је име низа. Све што је је Приступање Арраи у нашем струцт, па ако желимо да поставите н у том индексу, можемо само да јој приступе користе заграде с.сизе. Кул. У реду, поп га Псеудокод сам за вас, али сличан концепт. Да ли то има смисла? Ако је величина већа од нуле, онда сте знам да желите да нешто јер ако се величина није већи од нуле, онда Немам ништа у димњак. Дакле, желите само да извршите овај код, може само да поп ако постоји нешто да поп. Дакле, ако је величина већа од 0, што минус величина. Смањите смо величину и онда се вратити оно што је у њему, јер од поппинг, желимо да Приступ год се складишти у индексу на врху гомиле. Све смисла? Ако сам ви пишете ово, би момци моћи да га напишем? У реду, ви можете да играте са њом. Без бриге ако не капирам. Немамо времена за индекс то се данас, јер смо Има пуно тих структура проћи кроз, али у суштини Псеудокод, веома, веома сличан гурати. Само пратите логику. Уверите се да приступате све Вашег струцт исправно. Да? ПУБЛИКА: Хоће ли ови слајдови и цела ова ствар бити до данас-иш? Анди Пенг: Увек, да. Ја ћу покушати да стави ово као сат после. Ја ћу емаил Давида, Давид ће покушати да стави га као сат после овога. У реду, па онда можемо да пређемо на ово друго дивно структура података се зове ред. Као ви можете видети овде, а ред, за Британце међу нама, све што је је линија. Дакле, супротно ономе што мислиш да гомила је, Ред је управо то логично мислите да јесте. То је држали правила ФИФО, који је први у, први од. Ако сте први једна у низу, ти си први који је излази из линије. Дакле, оно што ми називамо ово је декуеуеинг и енкуеуеинг. Ако желимо нешто да дода у нашем реду, енкуеуе смо. Ако желимо да декуеуе, или да Нешто даље, декуеуе смо. Дакле, исти осећај да смо некако стварање фиксне величине елементе које смо може похранити сигурно ствари, али можемо промените где смо постављање параметри унутар њих На основу онога што врсти функционалност желимо. Тако гомиле, желели смо последњи један, Н да буде први напоље. Ред је да хоћемо да је прва ствар у да буде прва ствар напоље. Тако је струцт типа дефинишу, као што видите, то је мало другачија од онога што је било стек јер не само да морамо наставити колосек где је величина је тренутно, Такође желимо да пратите главе као и где тренутно смо. Тако да мислим да је лакше ако сам нацртао горе. Дакле, хајде да замислимо да имамо ред, Рецимо глава је овде. Шеф линије, хајдемо само да кажем да је тренутно тамо, и желимо да убаците нешто у реду. Ја ћу да зовем величину суштински је иста ствар као репа, крај где год ваш ред је. Рецимо да је величина је овде. Дакле, како се један феасибли убаците нешто у реду за? Оно индекс желимо да поставите где желимо да убаците у. Ако је ово на почетку свог куеуе и ово је крај или величини тога, где и ми желите да додате следећи објекат? ПУБЛИКА: [неразумљиво] Анди Пенг: Тачно, желите да додате то зависи од сте га написали. Или је ово празно, или да је празно. Дакле, желите да га додате вероватно Овде јер ако је величина је-- ако су сви пуни, хоћеш да га додате овде, зар не? И то је, док је веома, веома једноставно, не баш увијек тачно јер је главна разлика између ред и стацк је да је ред може заправо може манипулисати тако да су промене главе у зависности од тога где желите почетак вашег правом да почне. И као резултат тога, ваш реп такође ће се променити. И тако погледај ово сада код. Како ви је такође тражено да написати на квизу, енкуеуе. Можда ћемо причати кроз зашто одговор је био оно што је било. Нисам могао сасвим стане ову линију на једној, али у суштини овај део кода треба да буде на једној линији. Проведите као 30 секунди. Погледајте и уверите се зашто ово је начин на који је то. Врло, врло слична струцт, веома, веома Слична структура као претходна стацк осим можда једна линија кода. И то једну линију кода одређује функционалност. И заиста разликује Ред је из гомиле. Свако ко жели да се убод на објашњавајући зашто си Има ту компликовану ствар овде? Видимо повратак нашег диван пријатељ модул. Као што ви ће ускоро доћи препознати у програмирању, Скоро кад год треба нешто да заврши око било чега, модул ће бити начин да се то уради. Тако знајући да, да ли неко жели покушати објашњавајући ту линију кода? Да, сви одговори су прихваћено и добродошло. ПУБЛИКА: Аре иоу талкинг то ме? Анди Пенг: Да. ПУБЛИКА: Ох, не извини. Анди Пенг: У реду, хајде да шетња кроз овај код. Дакле, када покушавате да додати нешто на реду за, у дивној случају да глава се дешава да будем овде, то је врло лако за нас да само идем до краја убаците нешто, зар не? Али поента је ред је да глава може заправо динамички мењати у зависности од тога где смо Желим почетак нашег к да буде, и као такав, репа такође ће се променити. И тако замислите да то није било куеуе, већ је то био ред. Рецимо глава је овде. Рецимо наш ред изгледао овако. Ако бисмо хтели да пребаце где почетак линије је, рецимо да помера главу на овај начин и величине овде. Сада желимо да додамо нешто ово ред, али ви можете видети, то није тако једноставно као да само додати све што је након величини јер онда понестало границе наше стварне низа. Где желимо да заиста додати овде. То је љепота реду је то да нам је визуелно Изгледа да је линија иде овако, али када чувају у структури података, они дати као као циклус. То некако обавија око на фронт на исти начин да линија може умотати око зависности где год вас Желим да поцетку линије да буде. И тако ако узмемо гледај доле, хајде да кажу желели смо да створимо функција названа енкуеуе. Желели смо да додамо инт н у тај к. Ако к.сизе к-- ћемо позвати да наше податке струцтуре-- ако наш куеуе.сизе не једнак капацитету или ако то је мање од капацитета, к.стрингс је низ у нашој к. Ми ћемо поставити да једнако к.хеадс, који је овде, плус к.сизе Модул од капацитета који врап нас поново овде. Дакле, у овом примеру, индекс главе је 1, зар не? Индекс величине је 0, 1, 2, 3, 4. Дакле, можемо да урадимо 1 плус 4 модул наш капацитет који је 5. Шта нам то даје? Шта је индекс који излази из овога? ПУБЛИКА: 0. Анди Пенг: 0, што случајно овде, па желимо да будемо у стању да убаците у овде. И тако ова једначина овде некако да само ради са свим бројевима у зависности од тога где је ваш глава и твоја величина су. Ако знате шта они ствари су, знате тачно тамо где желите да убаците шта год да је после чекања. Да ли то има смисла свима? Знам врсту мозга теасер поготово јер дошао као последица вашег квизу. Али, надамо се сви Сада може да разуме Зашто ово решење или ово Функција је начин на који је то. Свако мало нејасно о томе? ОК. И сада, ако вас желео да декуеуе, ово је место где би наша глава се помера јер ако бисмо декуеуе, не скинути крај к. Желимо да скинем главу, зар не? Дакле, као резултат, глава ће се променити, и то је разлог зашто када енкуеуе, мораш да пратиш где главу и величина треба да буду способни за уметање у исправан положај. И тако кад декуеуе, Такође је Псеудокод напоље. Слободно ако желите да покушамо кодирања ово. Желиш да померите главу, зар не? Да сам хтео да декуеуе, ја би померили главу изнад. То би био на челу. А наша тренутна величина би одузмите зато што више не има четири елемента у низу. Имамо само три, а онда желимо да се врати оно што је враћен у главе јер желимо да ово вредност од толико сличан стека. Само узимате из другог места, и морате да пренесете показивач да друго место као резултат. Логично, сви следе? Велики. У реду, тако да ћемо да причамо мало више у дубину око повезаних листи јер ће бити веома, веома драгоцен за вас у току ове седмице је псетс. Повезаних листи, као момци могу да се сетим, све су су чворови који су чворови сигурно вредности и као вредност и показивач који су међусобно повезани они показивачима. И тако Струцт како стварамо чвор овде је има инт н, што је год вредност у продавници или стринг н или шта год желите да зову, угљенисани звезда бр. Струцт ноде звезда, која је показивач да ли желите да имате у сваком чвору, ћеш имати да показивач тачка према следећи. Имаћете главу од повезане листе који је да укаже на остатак вредности тако даље и тако даље све док не коначно до краја. И овај последњи чвор је само да нема показивач. То ће да укаже на ништаван, а то је кад знаш да си погодио крај твоје листе повезане је када ваш последњи показивач не указују ни на шта. Тако ћемо да идемо мало више Дубина о томе како један евентуално би сеарцх повезану листу. Сетите се шта су неки од недостаци повезаних листи стихови низ претреса у вези. Низ можете бинарна претрага, али зашто не можеш да урадиш да је у повезане листе? ПУБЛИКА: Зато што су сви они повезани, али не сасвим знам гдје [Неразумљиво]. Анди Пенг: Да, управо тако се сетим да је сјај на низ била је чињеница да смо имали меморија директног приступа где ако сам желео вредност од индекса шест, ја само могу рећи индекса шест, дај ми ту вредност. А то је зато што низови су поредани у сусједном простору меморије на једном месту, док је врста повезаних листи су насумице смењују свуда, а једини начин можете наћи један је кроз показивачем који вам говори адреса где је следећи чвор је. И тако као резултат тога, једини начин за претраживање преко повезане листе је линеарна претрага. Јер ја не знам где 12. вредност у повезане листи је, Морам да пролазе кроз целину те повезане листе један један од главе до првог чвора, у другу чвор, до трећег чвора, скроз доле док коначно добијем где је чвор тражим је. И тако у том смислу, претрага на повезане листе је увек бр. Увек је бр. Увек је у линеарном времену. И тако код у коме спроводимо ово и ово је мало ново за вас од када сте момци су стварно говорио о или никад сеен показивачи како да претраживати показивачима, тако да ћемо проћи кроз Ово је врло, врло споро. Тако инт претрага, зар не, замислимо желимо да створи функцију под називом претрага да врати истина Ако сте пронашли вредност унутар повезан лист, и враћа иначе фалсе. Чвор звезда листа тренутно само показивач на прву ставку на листи повезана. инт је вредност да сте у потрази за у тој листи. Дакле, чвор са показивач једнака листу. То значи да смо постављање и стварање показивач на први чвор унутар листе. Свако са мном? Дакле, ако смо да идемо овде, ја имам инитиализед показивач који указује на шеф год да листа. И онда када се овде, док је показивач није једнако нула, тако да је то петља у којем смо ће накнадно бити прелазећи остатак нашој листи јер оно што се дешава када показивач једнако нула? Знамо да смо бих-- ПУБЛИКА: [неразумљиво] Анди Пенг: Тачно, тако да знамо да смо стигли до краја листе, зар не? Ако се вратимо овде, сваки чвор треба указујући на други чвор и тако даље и тако даље док се на крају погодио реп на вашој листи повезане, која има показивач да само не указује нигде осим бр. И тако у суштини знате да васа листа је још увек тамо док показивач није једнако нула, јер кад се једнако нула, знаш да нема више ствари. Дакле, то је петља у којој смо ће имати стварну претрагу. А ако поинтер-- да ли видите такав стрелице функције тамо? Дакле, ако показивач указује на н, ако показивач на н једнако једнако Н, То значи да ако показивач да сте траже на крају сваког чвор је заправо једнак вредности тражиш, онда желите да се вратите истина. У основи, ако сте у чвор који има вредност коју тражите, знате да сте били у стању да успешно претрагу. У супротном, желите да поставите показивач на следећи чвор. То је оно што ради та линија овде. Показивач једнака показивач следећи. Свако види како се то ради? И у суштини ти ћеш само пролазе целину листе, ресетовање показивач сваки пут до ви на крају погодио крај листе. И знате да не постоје више чворова за претраживање преко, и онда можете ретурн фалсе јер ви знате да, ох, добро, ако сам био у могућности да претражујете кроз целини листе. Ако у овом примеру, ако сам желео да траже вредности од 10, и ја почети на челу, и Трагам скроз доле, и на крају сам добио ово, што показивач који указује на нулл, Знам то, срање, претпостављам 10 није у ова листа јер нисам могао да га нађем. И ја сам на крају листе. И у ком случају знаш Ја ћу да се вратим лажна. Нека то упије мало. Ово ће бити прилично важно за вашу псет. Логика Врло је једноставно, можда синтаксички само спроводи. Ви желите да се сигурни да сте разумели. Кул. У реду, како бисмо били уметање чворова, зар не, у листу, јер се сетим шта су предности које оно да имају повезану листу односу читав низ у смислу меморије? ПУБЛИКА: То је динамичан, тако да је лакше да-- Анди Пенг: Тачно, тако да је динамична, која значи да може проширити и скупља у зависности од потреба корисника. И тако, у том смислу, ми не треба трошити непотребно меморија јер ја ако ја не знам колико вредности Желим да продавници, то нема смисла за мене да створи низ сљедећих разлога ако желите да сачувате 10 вредности и ја створити низ 1.000, то је много изгубљеног памћења, доделио. Зато желимо да користи повезани Листа да бисте могли да динамички промени или смањити нашу величину. И то чини убацивање мало компликованије. Пошто не можемо насумице приступити елементе начин на који бисмо низа. Ако желите да унесете елемент у седмом индекса, Могу само да га убаците у седмом индекса. На повезане листе, не значи доста раде тако лако, па ако смо хтели да убаците она овде у повезане листе, визуелно, врло је лако видети. Ми само желимо да га убаците тамо, одмах на почетку листе, одмах након глави. Али начин на који морамо да пренесете показивачи се мало замршена или, логично, има смисла, али желите да се уверите да сте га потпуно пао јер последња ствар коју желите је да пренесете показивач начин на који ми радимо овде. Ако вас дереференце поинтер од главе до 1, онда све изненада остатак листе повезане је изгубио зато што нису стварно створио привремену ништа. То је указао на 2. Ако пренесете показивач, затим Остатак вашој листи је потпуно изгубљена. Дакле, желите да будете врло, врло опрезан овде прво доделите показивач од Вхатевер Иоу желите да унесете у где год желите, а затим вас могу дереференце до краја листе. Дакле, ово важи и за где год покушавате да убаците у. Ако желите да убаците На глава, ако желите да одговорите овде, Ако желите да унесете у крај, добро, на крају сам Претпостављам да би само Немам показивач, али Желим да се уверите да сте не губе остатак листе. Увек желите да се уверите Ваш нови чвор се указује према све што желите да унесете у, а затим можете додати цхаининг на. Свако јасно? Ово ће бити један од правих проблема. Један од већине главних питања ти ћеш имати на псет је да ћемо покушати да створе повезане листе и убаците ствари али онда само изгуби остатак листе повезане. И ти ћеш бити као ја Не знам зашто се ово дешава? И то је бол проћи кроз и претражите све ваше показивача. И гарантујем ти на овом псет, писање и цртање те чворове од ће бити веома, веома корисно. Дакле, можете у потпуности да пратите где сви ваши показивачи су, шта није у реду, где сви ваши чворови су, оно што треба да урадите да бисте приступили или убаците или брисање или било ко од њих. Свако добро са тим? Кул. Дакле, ако смо желели да погледамо код? Ох, не знам да ли смо можете видети који-- ОК, тако на врху све што је је функција по имену уметак где желимо да убаците инт н у повезане листе. Ми ћемо проћи кроз ово. То је много кода, много нових синтаксе. Ми ћемо бити у реду. Дакле, горе на врху, кад год желимо да створимо нешто шта треба да урадимо, поготово ако желимо да неће бити ускладиштен на стеку али у гомили? Идемо на маллоц, зар не? Тако ћемо створити показивач. Ноде, показивач, нове једнаки Маллоц величине чвора јер желимо да чвор да се направи. Желимо количину меморија која чвор заузима да се додељене за стварање новог чвора. А онда ћемо да проверимо да видим да нови равноправни једнако нула. Сећаш се шта смо рекли? Шта год вам маллоц, шта треба да увек? Увек морате да проверите да без обзира да ли је то нула. На пример, ако је ваш оперативни Систем је потпуно пуна, ако није имао више меморије на све и покушавате да маллоц, да ће се вратити нула за вас. И тако ако покушате да га користите када је указивање на нулл, нећеш моћи да да приступите ту информацију. И тако, као што су, желели смо да направимо сигуран да кад год сте маллоцинг, ви увек проверава да ли да је меморија које вам је нулл. А ако није, онда можемо да пређемо на са остатком нашег кода. Тако ћемо покрене нови чвор. Ми ћемо да урадимо нови н једнако н. А онда ћемо да радимо поставио нови показивач на ново да нулл јер сада не знамо желим ништа за то да укаже на. Немамо појма где то ће вас, а онда, ако желимо да убаците га у главу, онда можемо доделити показивач у главу. Да ли сви следе логику где она се дешава? Све што радимо је креирање нове чвор, постављање показивач на НУЛЛ, и онда пренамене је у главу ако ми знам желимо да га убаците у главу. А онда је глава ће указују тог новог чвора. Свако у реду са тим? Дакле, то је процес у два корака. Мораш да Прво доделите шта год да правите. Сет који показивач на референца, а затим вас могу некако Дереференце први поентер и усмерите га према новом чвору. Где год желите да га убаците, да логика иде да важи. То је нешто попут додељивања привремене променљиве. Запамтите, имаш да се уверите да вас не губи траг ако замене. Ви желите да се уверите да имате привремена варијабла која врста води колосек где је та ствар се чува тако да не губе никакву вредност у току Као зезали са њим. У реду, тако да код ће бити овде. Момци погледајте након делу. То ће бити тамо. Претпостављам како се ово се разликују ако желимо да убаците у средини или на крају? Да ли неко има идеју о томе шта је Псеудокод као логичан референце да узмемо ако желимо да га убаците у средини? Дакле, ако смо хтели да га убаците На глава, све што урадите је да направите нови чвор. Поставили смо показивач тога нови чвор на било глави, а онда смо поставили главу са новим чвор, зар не? Ако бисмо хтели да га убаците у средини листе, што би ми треба да урадимо? ПУБЛИКА: И даље би бити сличан процес Као додељивања показивач и онда доделе тог показивач, али ми би морали да тамо лоцирају. Анди Пенг: Тачно, тако тачно исти процес, осим тебе треба да лоцира где сте тачно Желим да нова показивач да иду у, па ако желите да унесете у средина повезана лист-- реду, рецимо да је наш повезана листа. Ако желимо да га убаците овде, ћемо да створимо нови чвор. Идемо у маллоц. Идемо да креирате нови чвор. Идемо да доделите показивач овог чвора овде. Али проблем који се разликује одакле је глава је да смо тачно знао где је глава. То је било на први, зар не? Али овде морамо да пратимо где смо га убаците у. Ако стављате наше чвор овде, имамо да се уверите да је један претходни овом чвору је онај који распореди показивач. Па онда морате некако пратити две ствари. Ако сте пратили где је чвор тренутно је убацивање у. Такође морате да пратите где претходна чвор који гледате је такође био тамо. Свако добро са тим? ОК. Како убацивање у крају? Да сам хтео да га додате овдје-- ако сам желео да бисте додали нови чвор на крај листе, Како могу да то урадили? ПУБЛИКА: Па тренутно је последњи је указао на нулл. Анди Пенг: Да. Управо, тако да је ово један Тренутно је истакао да зна, па претпостављам, у том смислу, то је врло лако додати на крај листе. Све што треба да урадите је да га поставити једнак нулл, а онда бум. Тамо, веома лако. Врло једноставно. Врло сличан хеад, али логично вас желите да се уверите да су кораци узмете у правцу радите било шта од овога, ви после заједно. То је врло лако, у средини вашег кода, ухвате се на, Ох, имам толико савета. Ја не знам где шта је указујући на. Ја не знам ни који чвор Ја сам. Шта се дешава? Опусти се, смири се, удахни дубоко. Драв своју листу повезан. Ако кажете, ја знам где тачно Морам да убаците ово у и ја тачно знам како да пренесете моје показивачи, много, много лакше замислити оут-- много, много лакше да не изгубити се у бубе у вашем коду. Свако у реду са тим? ОК. Претпостављам концепт који нисмо Заиста је говорио о до сада, и ја вас претпостављам вероватно неће наићи на много иет-- то је нека врста напредног цонцепт-- је да ми заправо имамо податке Структура зове двоструко повезану листу. Дакле, као ви можете видети, све што радимо је креирање стварна вредност, екстра Показивач се сваки од наших чворишта који такође указује на претходни чвор. Дакле, не само да имамо своје чворови указују на следећу. Они такође указују на претходну годину. Идем одмах да игнорише ову двојицу. Дакле, онда имате ланац да може да се креће у оба смера, и онда је мало лакше логички пратите. Као овде, уместо праћење, ох, морају да знају да је ово чвор је онај који морам да пренесете, Могу да одем овде и само повуците претходни. Онда знам тачно где то јест, и онда те не морају да пролазе кроз Целина повезане листе. То је мало лакше. Међутим као таква, ви дупло имате износ показивача, То је двоструко више од количине меморије. То је много казаљки да пратите. То је мало сложенији, али је мало више усер фриендли зависности на оно што покушавате да постигнете. Дакле, овај тип података структура потпуно постоји, и структура за веома, веома једноставна осим све имаш је, уместо само показивач на следећи, имате и показивач на претходну. То је све разлика била. Свако добро са тим? Кул. У реду, сад сам ја заиста потрошити вјероватно као 15 до 20 минута или булк остатка времена у одељку говоримо о хеш табеле. Колико вас Прочитао сам псет5 спец? Добро, добро. То је већи од 50% нормално. У реду је. Дакле, као што ви ћете видети, ви сте изазов у ​​псет5 ће бити да спроведе речник где сте учитати преко 140.000 речи да вам дамо и Спелл Цхецк то против свих текста. Даћемо вам случајно комада литературе. Ми ћемо вам дати Одисеју. Ми ћемо вам дати Илијади. Ми ћемо вам дати Аустин Поверс. А твој изазов ће бити Спелл Цхецк Свака реч у свим тих речника у суштини са нашим правописа. И тако има неколико делова стварања овог псет, Први желите да будете у стању да заиста лоад све речи у ваше рјечник, а онда вас желе да буду у могућности да спелл ​​цхецк свима њима. И тако, као што је, идете да захтевају структура података који могу да урадим ово брзо и ефикасно и динамично. Претпостављам најлакше начин да се ово, хвала би вероватно створити низ, зар не? Најлакши начин складиштења те је може створити низ 140.000 речи и све их само поставимо тамо и а затим их пребаците до бинарном потрази или селекције или нисам-- жао што је сортирање. Можете их сортира и онда прећи их од бинарног претреса или само линеарно потрази и само завршни речи, али да узима огромну количину меморије, и то није врло ефикасан. И тако ћемо почети говоримо о начинима израде наше време ради ефикасније. А наш циљ је да се константа време где то је скоро као низова, где имате тренутни приступ. Да сам хтео да тражи било шта, Желим да будем у стању да само, бум, финд ит тачно, и извуците га. И тако структуру у којој ћемо постати веома близу да би могли да приступе константа време, овај свети грал у програмирање константа Време се зове хеш табеле. И тако Дејвид је раније споменуто [Неразумљиво] мало у предавању, али ћемо стварно роњење у дубоким ове недеље на комад који је у вези како хасх табела ради. Дакле, на начин на који хасх табле радови, на пример, ако сам хтео да сачувате гомилу речима, гомила речи у енглеском језику, Могао бих теоретски пут банана, јабука, киви, манго, пар, и диња све на само низ. Могли би сви стати у и да се пронађу. То би било некако бол у претраживати и приступа, али лакши начин да то урадите је да можемо заправо створити структура који се зове хеш табела у којој смо хасх. Ми смо покренули све наше тастера преко хасх функција, једначина, да их све претвара у нека врста вредности да онда може похранити на у суштини низ повезане листе. И ево, ако желимо да сачувате енглеске речи, можемо само потенцијално, не знам знам, окрените све прва слова у неку врсту великог броја. И тако, на пример, ако сам желео Да је синониман са аппле-- или са индексом од 0, и Б бити синоним са 1, можемо имати 26 ставке то само може да складишти све словима писмо да ћемо почети са. А онда можемо да имамо јабука на индекс 0. Можемо имати банану у индексу 1, диња на индекс 2, и тако даље и тако даље. И тако, ако сам хтео да претражујете мој хасх табела и приступ јабука, Знам јабука почиње са типа А, и ја тачно знам да то мора бити и тараба сто у индексу 0 јер функције претходно добио. Тако да ја не знам, ми смо корисник програм у коме ћете бити оптужен за арбитрарили-- не произвољно, са покушава да замишљено Мислим добрих једначина да би могли да шире од све своје вредности на начин на који лако да приступите је касније са једначине као Јеси ли то ти, сами, знам. Дакле, у смислу да ли желим да идем у Манго, знам, ох, почиње са м. То мора да буде на индекс 12. Немам тражити кроз било шта. Знам екацтли-- сам да одем у индекс 12 и извуците то. Свако јасно како хасх функција сто је ради? То је нека врста само сложеније низ. То је све што је. ОК. Претпостављам да налетимо ово питање шта ће се десити ако имате више ствари да вам дају исти индекс? Тако кажу нашу функцију, сви га да ли је то узети прво слово и да га у један одговарајућа 0 кроз 25 индекса. То је потпуно у реду ако имате само један од сваког. Али друга почнете има више, ти си ће имати оно што се зове судар. Дакле, ако покушам да убаците закопа у хасх Табела која већ има банану на њега, шта ће се догодити када покушате да убаците то? Лоше ствари јер банане већ постоји у индексу да желите да га сачувате у. Бери врста је као, Ах, шта да радим? Ја не знам где да идем. Како решити ово? И тако ви це некако Видим да урадимо ову ствар лукав где можемо некако стварно створити повезану листу у нашим низова. И тако је најлакше да размишљам о томе, све хасх табела је низ повезаних листама. И тако, у том смислу, имате овај прелепи низ показивача, и онда сваки показивач у та вредност, у том индексу, заправо може указати на друге ствари. И тако имате све ове одвојене ланци долазе са једног великог низа. И ево, ако ја желео да убаците берри, Знам, у реду, ја ћу да улаз је кроз моје хасх функцију. Ја ћу да завршим са индексом 1, а онда ћу моћи да само мањи део ове гигант 140.000 речи речник. А онда сам Можете погледати кроз 1/26 тога. И онда могу само да убаците Берри било пре или после банана у овом случају? После, зар не? И тако ћеш желети да убаците овај чвор после банана, па ћеш да убаците на репу те повезане листе. Идем да се вратим на овај претходни слајд, тако да ви можете видети како хасх функција ради. Тако хасх функција је ова једначина да сте покренули врсту ваш унос до добити све индекса желите да га доделите ка. И тако, у овом примеру, сви смо хтели да одведем прво писмо, претворити у индекс, онда може да складишти да у нашој хеш функције. Све што радимо овде је да смо претварање прво писмо. Дакле, кеикеи [0] је само прво слово од свега низ имамо, ми пролази. Ми смо претварање да се горњи и ми одузимамо од великим словима А, тако да све то ради нам даје низ у којима можемо хасх наше вредности на. А онда ћемо врати хасх МОДУЛУС величине. Будите врло, врло опрезни јер, теоретски, овде Ваш хасх вредност може бити бесконачна. Само да наставим да и даље и даље. То може бити неки стварно, заиста велике вредности, већ зато што иоур хасх табели која сте направили има само 26 индекса, желите да се уверите ваш модулусинг тако да не рун-- је то исто ствар као своју куеуе-- тако да не нестане из дну хеш функције. Желиш да прекине вратити око на исти начин у [неразумљиво] када Имао си веома, веома велико слово, ви није желео да да Само побегли крај. Иста ствар овде, желите да се уверите не побегне крај обавијањем около до врха табеле. Дакле, ово је само врло једноставна хасх функција. Све то урадила је узети први писмо било наше улаз био и да га у индекс који могли бисмо да ставимо у наш хасх табели. Да, па као што сам већ рекао, начин на који смо решили сударе у нашем хасх табеле имају, оно што ми зовемо, цхаининг. Дакле, ако покушате да унесете вишеструке речи које почињу са исте ствари, ћеш имати једну хасх вредност. Авокадо и јабука, ако сте покрените га кроз наше хеш функције, ће вам дати Исти број, број 0. И тако је начин на који смо решили да је да ми заправо можемо некако да их повеже заједно преко повезаних листи. И тако у том смислу, момци могу некако видим како структуре података које смо претходно подешавање А Раисин као повезана листу врсте од може доћи заједно у једну. А онда можете да креирате сада ефикасније структуре података који може да обави веће количине података, која динамично величину зависности о вашим потребама. Свако јасно? Свако нека врста јасно о томе шта се овде дешава? Да сам хтео да инсерт-- шта је воће које почиње са, не знам, Б осим бобице, банане. ПУБЛИКА Блацкберри. Анди Пенг: Купина, купина. Где купина иде овде? Па, ми у ствари не сортира ово још, али теоретски ако желимо да имамо ово по абецедном реду, где би блацкберри иде? ПУБЛИКА: [неразумљиво] Анди Пенг: Тачно, после овде, зар не? Али, пошто је веома тешко реордер-- Претпостављам да је до вас. Момци могу потпуно имплементирати шта год хоћеш. Ефикаснији начин да се то уради, можда био би да се сортирају ваш повезан лист у абецедном реду, па кад сте убацивања ствари, хоћеш да би били сигурни да их убаците у абецедном реду тако да онда када си покушавајући да их потражите, не морате да прођу све. Ви знате тачно где је, и то је лакше. Али ако имате мало ствари смењују случајно, и даље ћеш имати да је прелазак у сваком случају. И тако, ако сам хтео да само инсерт купина овде и ја сам хтјела да тражи да, знам, о, купина мора почети са индексом 1, тако да сам знам тренутно само тражи на 1. И онда ја могу некако пролазе кроз повезану листу док не дођете до блацкберри, И онда да? ПУБЛИКА: Ако покушавате да цреате-- Претпостављам да је ово веома једноставан хасх Функција. И ако смо хтели да урадимо вишеструки слојеви који воле, У реду, ми желимо да се одвоје у као и сви словима абецеде и онда поново да волим другу сет од словима абецеде у оквиру које, стављамо као хасх сто у хеш табели, или као функција у функцији? Или је то-- Анди Пенг: Дакле, ваша хасх фунцтион-- свој хасх табелу може бити велики као желите да. Дакле, у том смислу, мислио сам било је веома лако, веома једноставно за мене да некако заснива о словима прве речи. И тако је само 26 опција. Ја само могу добити 26 опције из 0 до 25, јер они само могу почети од А до З. Али Ако желиш да додам, можда, сложеност или брже покретање време у својој хеш табеле, апсолутно може да уради свашта. Можете направити свој једначина која вам даје више дистрибуција у вашем речи, онда када претражујете, то ће бити бржи. То је потпуно до вас како желите да то применимо. Мислите о томе као само кашикама. Да сам хтео да имам 26 кашике, идем да средим ствари у тим кашикама. Али ја ћу имати гомилу ствари у сваком кофу, Дакле, ако желите да се направи брже и ефикасније, дај ми сто кашике. Али онда морате да смисли начин да средим ствари тако да су у одговарајуће кофи би требало да буду унутра. Али онда стварно кад Желим да погледате ту канту, То је много брже, јер постоји мање ствари у сваком кофу. И тако, да, то је у ствари трик за вас у псет5 је да ћете бити изазов да створи само оно што је најефикаснији Функција можете да замислите да буде у стању да сачувате и провери ове вредности. Тотално до вас како год хоћете да то уради, али то је стварно добра ствар. То је врста логике сте Желим да почнете да размишљате о је, добро, зашто не бих се више кофе. И онда морам тражити мање ствари, а онда можда и имају другачију функцију хасх. Да, постоји много начина да то урадите псет, неки су брже од других. Тотално сам да само видите како брзо је био најбржи момци ће бити у стању да се ваше функције на посао. ОК, сви добро на Ланчани и хасх табеле? То је заправо је као веома једноставан концепт, ако мислите о томе. Све што је је одвајање год Ваши улази у канте, их сортирање, а затим претресају наводи да је повезан са. Кул. У реду, сада имамо другачију врсту структуре података које се зове дрво. Идемо даље и разговарати о покушаја које су изразито различити, али у истој категорији. У суштини, све је дрво је уместо организовања података у линеарном путу да вас хасх табела доес-- Знате, то има топ и дно и онда некако повезати офф тога-- а дрво има врхунски које ви називате корен, а онда има листове све око њега. И тако све имате овде је само врх чвор који указује на друге чворова, који бодова на више чворова, и тако даље и тако даље. И тако да само треба резачи гране. То је само другачији начин организовања података, и зато што је дрво зову, ви само-- само по узору се да изгледам као дрво. Зато ми то зовемо дрвеће. Хасх табела изгледа као табеле. Дрво баш изгледа као дрво. Све то је одвојени начин организовања чворова зависно од тога шта су ваше потребе. Дакле, имате корен и онда имате лишћа. Начин на који смо посебно може мислим о томе је бинарно стабло, бинарни дрво је само специфична врста дрвета где сваки чвор само тачке да, при мак, друга два чворови. И тако овде имате посебан симетрија у вашем дрвету да олакшава врста гледати шта вредности си јер онда има увек лево или десно. Никада није је као леви трећине од лево или четврти са леве стране. То је само имате лево и десно и можете да потражите било који од њих двојице. А зашто је то корисно? Начин на који је ово корисно је ако гледате за претраживање преко вредности, зар не? Уместо спровођење бинарни претрага у низу грешака, ако желите да бисте могли да убаците чворова и одузети чворишта по вољи, као и сачувати претрагу капацитети бинарном претрагом. Дакле, на овај начин, ми смо некако трицкинг-- се кад смо рекао је повезана листе не могу бинарни претрагу? Некако смо стварање структуре података да трикове да у радни. И зато што повезани листе су линеарни, они само повезати једну за другом. Можемо врста има друга врста показивача које указују на различитим чворовима који могу да нам помогну у потрази. И ево, ако желим да имају бинарно стабло претраге, Знам да моје средње, ако 55. Ја ћу само да створи да као мој средини, као мој корен, а онда ћу имати Вредности спин офф од тога. Дакле, овде, ако ћу тражити вредност 66, могу да се крећу од 55. То је 66 више од 55? Да је то тако знам да мус претрагу И н право показивач овог дрвета. Идем до 77. У реду је 66 мање или веће од 77? То је мање него, да знате, о, то мора да буде лево чвор. И тако овде смо некако очувања све велике ствари у вези низова, па као динамичког промену величине објеката, као у стању да убаците и брисање по вољи, без бриге о фиксна Количина простора. Ми смо још увек чувају све те дивне ствари док су истовремено да сачувају лог и тражење време бинарне претраге да смо били само раније у могућности да фразу. Цоол структура података, врста комплексна за имплементацију, чвор. Као што можете видети, све што је струцт чвора је да имате лево и право показивач. То је све што је. Дакле, уместо да који има к или претходни. Имате лево или десно, а затим можете некако да их повезују Међутим тако изабрати. У реду, ми заправо догађа само да потраје пар минута. Тако ћемо се вратити овде. Као што сам раније рекао, Некако сам објаснио логика Хов Ве би тражити кроз ово. Ми ћемо покушати псеудоцодинг ово да видим ако можемо некако применити Иста логика бинарног потрази на другачијој врсти структуре података. Ако ви желите да се као пар минута да размисли о томе. ОК. У реду, ја ћу уствари само вам дати то-- не, ћемо говорити о псеудокоду први. Дакле, да ли неко жели да се добије убод шта Прва ствар коју желите да урадите када ви почињете претраживање је? Ако тражимо вредност 66, што је Прва ствар коју желимо да урадимо ако желимо да бинарних тражење ово дрво? ПУБЛИКА: Желите да изгледа добро и тражити лево и види [неразумљиво] већи број. Анди Пенг: Да, управо тако. Тако ћеш да погледате вашу корену. Постоји много начина можете позивати да, ваши људи родитељ чворова кажу. Ја волим да кажем, јер корен то је као корен дрвета. Идеш да погледате твој корен чвор, а ти си ћете видети већи је 66 од или мање од 55. И ако је већи од, па, то је већи од, где желимо да погледамо? Где желимо да сада претрагу, зар не? Желимо да сеарцх десна половина овог дрвета. Тако имамо, повољно, А показивач који указује на десно. И онда можемо поставити наш нови корен да буде 77. Можемо само отићи где год показивач показује. Па, ох, овде почињемо на 77, а ми једноставно не могу ово рекурзивно опет и опет. На овај начин, љубазан од имају функцију. Имате начин тражења то ти могу само да поновим изнова и изнова и изнова, у зависности од тога где желите да погледате док се на крају доћи до вредности да тражите. Има смисла? Ја ћу да ти покажем стварни број, и много је кода. Нема потребе да одлепим. Причаћемо кроз њега. Заправо, не. То је био само Псеудокод. ОК, то је само Псеудокод, која је мало сложен, али то је потпуно у реду. Свако следеће заједно овде? Ако је корен нулл, повратак лажно јер то значи не чак ни тамо ништа. Ако корен н вредност, па ако је то деси да буде једна гледате, онда ћеш ретурн труе јер знаш да га нашао. Али, ако је вредност мања од корена н, ти си ће тражити лево дете или лево лист, год желите да га назовете. А ако је вредност већа од корена, идете да потражите праву дрво, онда само покрените функцију кроз претрагу поново. А ако корен нулл, да је значи да сте стигли до краја? То значи да немате више више листова за претрагу, онда знате, ох, Претпостављам да није ту јер после сам погледао кроз цела ствар и није овде, само можда неће бити овде. Да ли то има смисла свима? Дакле, то је као бинарни потрази очувања Могућности повезаних листи. Цоол, па други тип од вас структура података момака можете покушати имплементацији на псет, имате само да изаберете једну методу. Али, можда алтернатива начин да хасх табела је оно што ми зовемо трие. Све што је трие је специфична врста дрвета који има вредности који иду у друге вредности. Дакле, уместо да бинарни дрво у смислу да само једна што може да укаже на два, можете имати једна ствар тачка за многе, многе ствари. Ви у основи имају низове унутар којих чувате показивачи који указују на друге низова. Дакле, чвор Хов Ве би дефинисали ТРИЕ је желимо да имамо Булова ц реч, зар не? Дакле, чвор је Булова као тачно или нетачно, пре свега на челу да арраи је ово реч? Друго, желите да имате савете да без обзира на остали су. Мало комплекс, мало апстрактно, али Ја ћу објаснити шта то свим средствима. Па ево, на врху, ако вас има низ прогласио је већ, чвор где имате Боолеан Вредност складиштени на фронту да каже да је ово реч? Зар то није реч? И онда имати остатак низа који заправо чува све могућности шта би то могло бити. Тако, на пример, као на врху имате прва ствар која говори истина или лажна, да или не, ово је реч. И онда имате 0 до 26 од писма које можете похранити. Да сам хтео да овде тражење за палицом, идем на врх и ја тражити Б. налазим Б у мом Арраи, па ја знам, у реду, јесте Б реч? Б није реч, па стога Морам да настави да тражиш. Идем из Б, а ја изгледам до показивач да Б указује на и видим још један низ информација, иста структура која смо раније имали. И овде-- Ох, следећи писмо у [неразумљиво] је А. Дакле, гледамо у том низу. Налазимо осми вредност, и онда тражимо да видимо, о, Хеј, да ли је то реч, је Б-А, реч? То није реч. Морамо да настави да гледаш. И онда гледамо гдје показивач на А поена, и указује на други начин у што имамо више вредности чувају. И на крају, долазимо до Б-А-Т, који је реч. И тако се следећи пут изгледаш, идеш да ту проверу, да, ово Булова функција је истина. И тако у том смислу смо некако смо поседовања дрво са низовима. Онда можете некако претрагу доле. Уместо хасхинг функцију и додељивање вредности од повезане листе, можете једноставно спровести трие да тражи довнвордс. Заиста, заиста компликовано ствари. Није лако размишљати о, јер сам као пљује толико структуре података од на тебе, али се сви некако разумијем како логика ово ради? OK kul. Со Б-А-Т, а онда идете да потражите. Следећи пут идете да видим, ох, хеј, то је истина, тако знам да ово мора бити реч. Иста ствар за зоолошки врт. Дакле, овде је ствар сада, ако желео да тражи зоо, сада, Тренутно зоолошки врт није реч у нашем речнику јер, како ви можете да видите, Прво место да имамо Боолеан ретурн труе је на крају зума. Ми имамо З-О-О-м. И ево, ми уствари не имате реч, зоолошки врт, у нашем речнику јер то цхецк бок није проверио. Дакле, рачунар не знам да је зоолошки врт је реч јер начин на који имамо чувати га, само зум овде заправо има Боолеан вредност која је била претворена истина. Дакле, ако желимо да убаците Реч, зоолошки врт, у нашем речнику, Како бисмо то урадили? Шта треба да урадимо да се уверите наш Компјутер зна да З-О-О је реч а не прва реч је З-О-О-м? ПУБЛИКА: [неразумљиво] Анди Пенг: Управо смо желите да се уверите да је ово овде, да Булова вредност Проверио гола која је то истина. З-о-о, онда ћемо да проверимо да, тако да знамо тачно, хеј, зоолошки врт је реч. Ја ћу рећи рачунар који је реч тако да када се рачунар провере, зна да зоолошки врт је реч. Пошто се сетим свих ових података структуре, то је врло лако за нас да кажем, ох, слепи миш је реч. Зоолошки врт је реч. Зум је реч. Али кад га граде, рачунар нема појма. Дакле, морате да га рећи тачно у ком тренутку је ово реч? У ком тренутку није реч? И у ком тренутку Да ли треба тражити ствари, и на ком тренутку не морам да идем следећи? Свако јасно тога? Кул. И онда долази Проблем како би го о убацивању нешто То је заправо не постоји? Дакле, рецимо да желите да унесете реч, купатило, у нашем Трие. Као што људи могу видети као тренутно све што сада имамо је Б-А, Т, и ова нова структура података тамо имали пиво да указао на нулл, јер претпостављамо да, ох, ево нема речи након Б-А-Т, Зашто морамо имати има ствари после тог Т. Али проблем настаје ако и ти желе да имају реч која долази после Т-а. Ако имате каду, ти си да зелим Х право. И тако начин на који ћемо да урадимо то је ћемо створити посебан чвор. Нисмо додели било који износ меморије за ову нев Арраи, а ми ћемо распоредити савете. Идемо да доделите Х Пре свега, ово нулл идемо да се отараси. Ми ћемо имати Х окренут на доле. Ако видимо Х, ми то желимо да иде негде другде. Овде, онда можете да проверите са да. Ако погодите Х после Т, О, онда знамо да је ово реч. Логичка ће да се врати истина. Свако јасно како се то догодило? ОК. У суштини, сви ове структуре података да смо прешли данас, ја сам отишао преко њих стварно, стварно брзо а не у много детаљ, а то је у реду. Када почнете да петљају са њим, ти ћеш бити праћење где сви показивачи су, шта се дешава у вашем структуре података, и тако даље. Они ће бити веома корисно, и то је на вама момци потпуно схватити како желите да спроведе ствари. И тако псет4, од 5-- ох, то је погрешно. Псет5 је грешке. Као што сам раније рекао, ти ћеш, једном Опет, преузмите изворни код од нас. Ту ће бити три главна ствари које ће бити преузимање. Ти ћеш преузети речнике, керс, и текстови. Све те ствари су се или речници речи да желимо да проверите или тест информација да желимо да Спелл Цхецк. И тако је речници дајемо ћеш да вам дам стварне речи које желимо да некако чува на начин који је ефикаснија од низа. А онда су текстови Биће оно што смо вас пита да правопис проверите да ли све речи постоје реалне речи. И тако су три блока програми који даћемо вам се зову дицтионари.ц, дицтионари.х, и спеллер.ц. И тако све дицтионари.ц ради се оно што се од вас тражи да спроведе. То учитава речи. То спелл ​​проверава их и чини сигурно да је све правилно убачена. дицтион.х је само библиотека фајл да објављује све те функције. И спеллер.ц, идемо да ти дам. Не морате да измените ништа од тога. Све спеллер.ц чини јесте да је, оптерећења га, проверава брзину тога, тестира мерило Свиђа ми се како брзо сте у стању да уради ствари. То је спеловала. Само се не зајебавај са њим, али да Сигурно сте разумели шта ради. Ми користимо функцију која се зове гетрусаге да тестира перформансе вашег спелл Цхецкер. Све што ради је у основи тестирамо Време свега у вашем речнику, тако проверите да ли сте схватити. Будите опрезни да не неред са њим или елсе ствари неће радити исправно. И највећи део овог изазова је за момци стварно измени дицтионари.ц. Ми ћемо вам дати 140.000 речи у речнику. Ми ћемо вам дати текст фајл који има те речи, и желимо да будете у стању да организују их у хасх табелу или Трие јер када смо вас да спелл цхецк-- замислите да сте правописа проверу као Хомерове Одисеје. То је као овај велики, огроман тест. Замислите да сваки реч коју су били само неми кроз низ 140.000 вредности. То би трајати заувек за ваш уређај за покретање. Зато желимо да организујемо наш података у ефикаснијих структура података као што је хеш табели или Трие. И онда ви можете некако од када тражите приступ много лакше и брже ствари. И зато будите пажљиви да реши судара. Ти ћеш добити гомилу од речи које почињу са А. Ти ћеш добити гомилу речи да почну са Б. На вама момци како желите да се реши. Можда има више ефикасан хасх функција него само првог слова нешто, па то је на вама момци да се некако ради шта год хоћеш. Можда желите да додате сва писма заједно. Можда желите да урадите воле чудне ствари на рачун број писама, шта год. До вама како желите да урадите. Ако желите да урадите хасх табелу, ако вас Желим да покушам да трие, потпуно зависи од вас. Ја ћу вас упозорити пре времена да је трие је обично мало теже само зато што има много више показивачи да прате. Али тотално до вас. То је далеко ефикаснији у већини случајева. Желиш да заиста бити у стању да задржи колосек све ваше показивача. Као уради исту ствар да радим овде. Када покушавате да убаците вредности у хеш табели или брисање, уверите се да сте Стварно праћење где је све због то је стварно лако ако сам Покушавам да убаците као реч, Анди. Рецимо да је то права реч, реч анди у огромни списак А ​​речи. Ако сам се деси да пренесете показивач погрешно, упс, оде целину остатак мог повезане листе. Сада је једина реч коју има је Енди, а сада све друге речи у рјечник су изгубљени. И тако желите да проверите да ли сте пратити све ваше показивача иначе ћеш добити огромни проблеми у вашем коду. Драв ствари пажљиво корак по корак. То га чини много лакше замислити. И на крају, желите да будете у стању да тестирате своје перформансе вашег програма на великој табли. Ако ви потрајати погледај ЦС50 сада, имамо оно што се назива велика табла. То је листица од најбржих спелл ​​цхецкинг пута целој ЦС50 сада, мислим да је врх као 10 Мислим пута осам од њих су запослени. Ми заиста желимо да нам ви тукли. Сви смо били покушава да спроведе најбрже кода могуће. Желимо вас да покуша да оспори нас и спроводи брже од свих нас могу. И то је заиста први пут да смо тражи се момци да урадимо да псет заиста можете урадити у било ком методу желите. Ја увек кажем, ово је сличније у стварном животу решење, зар не? Ја кажем, хеј, морам да урадим ово. Направите програм који је направио ово за мене. Уради то како год желите. Ја само знам да желим да посте. То је твој изазов за ову недељу. Ви, идемо да ти дам задатак. Ми ћемо вам дати изазов. А онда је до вас да се потпуно само схватим Који је најбржи и најбољи ефикасан начин да се спроведе ова. Да? ПУБЛИКА: Да ли је дозвољено да ако вантед за истраживање брже начине да урадите хасх табела на мрежи, можемо да урадимо да и наводе код туђи? Анди Пенг: Да, потпуно у реду. Дакле, ако сте прочитали спец постоји линија у спец да каже момци су потпуно слободни да истражи хасх Функције о томе шта су неки од најбржих хеш функције да покренете ствари кроз што док наводе да код. Дакле, неки људи су већ схватио брзе путеве да ради правописа даме, брзог начина чувања података. Тотално до вас, ако вас Желим да узми то, зар не? Уверите се да сте позивајући се. Заиста Изазов овде да покушавамо да тестирамо чини сигурни да знате Ваш обрнуто показивачи. Што се тиче приликом имплементације стварни хасх функција и долази са сличним математика за то, ви можете истражити шта год Методе мрежи хоћете. Да? ПУБЛИКА: Можемо ли навести помоћу [неразумљиво]? Анди Пенг: Да. Можете само, у вашем коментару, можете навести као, ох, преузет из бла, бла, бла, хасх функција. Свако има било каквих питања? Ми смо заправо Бреезед через раздел данас. Ја ћу бити овде да одговорити на питања као добро. Такође, као што сам рекао, канцеларија сати вечерас и сутра. Спец ове недеље је заправо супер лако и супер кратак да прочита. Предложио бих узимање поглед, само прочитајте целини њега. И Замила заправо вас води кроз сваки од функција треба да спроведе, па је веома, веома јасно како се то све. Само да се уверим да си праћење показивача. Ово је веома изазовна псет. То не оспоравам, јер као, Ох, концепти су много више тешко, или морате да научите толико нова синтакса начин да сте у последње псет. Ово је тешко, јер псет има толико показивачи, и онда је врло, врло лако једном имате грешку у коду неће моћи да пронађу где је Буба је. И тако потпуни вера у вама момци бити у стању да победи нашег [неразумљиво] изговора. Ја сам заправо немам никакав писмени мине још, али сам хтео да напишем моје. Дакле, док пишеш твоје, ја ћу писати моје. Ја ћу покушати да направи Рудник брже од твог. Видећемо ко има најбржи један. И да, ја ћу видети све момци овде у уторак. Ја ћу покренути неку врсту попут псет радионице. Све ово секција недеља су псет радионице, па ви имате пуно прилика за помоћ, радно време као и увек, и заиста се радујем читање сви код твојих момака. Имам квизове овде ако вама момци желе да дођем по њих. То је све.