ЈАСОН Хирсцххорн: Велцоме свима на Одсеку Севен. Ми смо у недељу седам курса. И овај предстојећи четвртак Ноћ вештица је тако сам ја обучена као бундева. Нисам могао да се савије преко и ставити на моје ципеле, тако да је то разлог зашто сам само носи чарапе. Ја такође не носи ништа испод ово, па не могу да је скинем, ако је то ометајуће за вас. Извињавам се унапред због тога. Не морате да се замислите шта се дешава. Ја носим боксерице. Тако да је све добро. 

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

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

ПУБЛИКА: Проверава за меморијске цурења? 

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

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

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

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

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

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

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

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

ЈАСОН Хирсцххорн: То је потпуно тачно. Дот значи приступити Тхе Н Део овог новог чвора. Ова линија поред шта ради? Мајкл. 

ПУБЛИКА: То ствара још један чвор који ће указати на нови чвор. 

ЈАСОН Хирсцххорн: Дакле, то није случај креирате нови чвор. То ствара шта? 

ПУБЛИКА: показивач. 

ЈАСОН Хирсцххорн: показивач на чвор, као што је назначено у овом чвор * овде. Тако се ствара показивач на чвор. А који је то чвор показује да, Мајкл? 

ПУБЛИКА: Нови чвор? 

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

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

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

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

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

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

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

ПУБЛИКА: Цалл показивача на следећи чвор. 

ЈАСОН Хирсцххорн: А зашто идемо на следећу? 

ПУБЛИКА: Зато што је то следећи чвор у листи. А ми само знамо да је друго место. 

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

Пет је већи од четири. Тако ћемо да наставимо. И сада смо на шест. И шта видимо у шест? Да, Карлос? 

ПУБЛИКА: Шест је већи од пет. 

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

ПУБЛИКА: Два. 

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

ПУБЛИКА: Морао би добити ту нулл тачку. Уместо нулл тачку коју би имао да додате елемент и онда имају она указује на девет. 

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

ПУБЛИКА: Стицк га у почетак или крај. 

ЈАСОН ХИРСЦХОРН: да штап у почетак или крај. Која треба да радимо? Боби? Зашто крај? 

ПУБЛИКА: Пошто почетак је већ испуњен. 

ЈАСОН ХИРСЦХОРН: У реду. Почетак је већ попуњена. Ко жели да се расправљају против Бобија. Маркус. 

ПУБЛИКА: Па вероватно желите да држимо га на почетку, јер иначе ако га ставите у крај ти ћеш морати да пролазе целу листу. 

ЈАСОН ХИРСЦХОРН: Управо тако. Дакле, ако размишљамо о рунтиме, рунтиме убацивања на крају би н, величина овога. Шта је Биг О рунтиме од убацивања на почетку? Константна време. Дакле, ако вам није стало до чувања нешто поредани, много боље да само убаците на почетку ове листе. А то може да се уради у сталном времену. 

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

ПУБЛИКА: Повратак лажан? 

ЈАСОН ХИРСЦХОРН: Повратак лажна. Нисмо га пронашли. Ако до краја листе и нисте пронашли број који сте тражи, она није тамо. Сва питања у вези наћи? Ако је ово био сортиран списак, шта би бити различит за наш претраживање? Да. 

ПУБЛИКА: Било би пронашли прву вредност то је већи од оног тражите и затим ретурн фалсе. 

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

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

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

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

ЈАСОН ХИРСЦХОРН: Ако желите да ослободите нешто што је потпуно тачно и ви маллоцед га. Реци ми желели да се врате ову вредност. Могли бисмо се вратити шест и онда бесплатно овај чвор и позив бесплатно на њему. Или вероватно бисмо назвати бесплатно прво а затим се врати шест. 

У реду. Дакле, хајде да пређемо на праксу кодирања. Идемо да код три функције. Први се зове инсерт_ноде. Дакле, имате код који сам вам е-поштом, а ако гледаш ово касније можете да приступите код у линкед.ц на сајту ЦС50. Али у линкед.ц, постоји неки скелет код који је већ је писано за тебе. А ту је и пар функције морате да напишете. 

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

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

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

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

Почнимо са писањем неке Псеудокод на табли. Ко може да ми да прву линију Псеудокод за овај програм? За ову функцију, а - инсерт_ноде. Алден? 

ПУБЛИКА: Дакле, прва ствар коју сам урадио је креирате нови показивач на чвор и ја инитиализед то указује на исти Оно што је листа указује на. 

ЈАСОН ХИРСЦХОРН: У реду. Дакле, правите нову показивач на листи, не на чвору. 

ПУБЛИКА: Тачно. Да. 

ЈАСОН ХИРСЦХОРН: У реду. И онда шта желимо да урадимо? Шта је после тога? Шта је чвор? Ми немамо чвор. Ми само имамо вредност. Ако желимо да убаците чвор, шта радимо Потребно је да прво урадите пре него што чак може мислите о га убаците? 

ПУБЛИКА: Ох, извините. морамо да маллоц простор за чвор. 

ЈАСОН ХИРСЦХОРН: Одлично. Хајде да урадимо - У реду. Не могу да постигну толико високо. У реду. Идемо да иде доле, а затим ми користимо две колоне. Ја не могу да идем да - У реду. Креирајте нови чвор. Можете да креирате други показивач на листу или можете једноставно да користите листу као што постоји. Ти стварно не треба да урадите то. 

Зато смо креирали нову чвор. Сјајно. То је оно што ми прво урадити. Шта је следеће? 

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

ЈАСОН ХИРСЦХОРН: Добро питање. Хајде да задржите то за касније, јер већину времена ми ћемо бити стварање нови чвор. Тако ћемо задржати тај овде. Али то је добро питање. Ако га створити и ми нађемо дупликат, шта треба радимо пре повратка? 

ПУБЛИКА: Ослободи га. 

ЈАСОН ХИРСЦХОРН: Да. Вероватно га ослободи. У реду. Шта да радимо након што креирате нови чвор? Ени? 

ПУБЛИКА: Ми смо ставили број у чвор? 

ЈАСОН ХИРСЦХОРН: Управо тако. Ставили смо број - ми маллоц простор. Ја ћу да оставим да сви као једна линија. Али у праву си. Маллоц смо простор, а затим ставимо број унутра Ми чак да подесите показивач део тога на нулл. То је потпуно тачно. И онда шта после тога? Ми нацртао ову слику на табли. Па шта да радимо? 

ПУБЛИКА: Ми идемо кроз листу. 

ЈАСОН ХИРСЦХОРН: Идите кроз листу. У реду. А шта ћемо проверити за сваки чвор. Курт, шта ћемо проверити за сваки чвор? 

ПУБЛИКА: Погледајте да ли Н вредност да је чвор је већа од вредности н наше чвора. 

ЈАСОН ХИРСЦХОРН: У реду. Ја ћу да урадим - Да, у реду. Дакле, то је н - Ја ћу рећи ако је вредност већа од овог чвора, онда шта да радимо? 

ПУБЛИКА: Па, онда ћемо убацити ствар у праву пре тога. 

ЈАСОН ХИРСЦХОРН: У реду. Дакле, ако је већа од ове, онда желимо да убаците. Али ми желимо да га убаците непосредно пре јер ми такође би требало да буде праћење, а затим, онога што је било раније. Дакле, пре него што убаците. Дакле, ми смо вероватно пропустили нешто раније. Вероватно Морамо да се чување колосек шта се дешава. Али, ми ћемо се вратити тамо. Дакле, шта је вредност мања од? Курт, шта ћемо да радимо ако вредност је мања од? 

ПУБЛИКА: Онда само настави осим ако је то последњи. 

ЈАСОН ХИРСЦХОРН: Свиђа ми се. Дакле, идите на следећи чвор. Осим ако је то последњи - вероватно Проверавамо за то у смислу стања. Али да, следећи чвор. И то је превише низак, па ћемо да пређемо овде. Али ако - могу сви да виде ово? Ако смо једнаки шта да радимо? Ако вредност покушавамо да убаците једнака је вредности овог нода? Да? 

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

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

ПУБЛИКА: Мислим да бих ишао након креирате нови чвор. 

ЈАСОН ХИРСЦХОРН: У реду. Дакле, на почетку ћемо вероватно - Да, можемо створити показивач на ново чвор, као претходног чвора показивача и струја чвор показивач. Дакле, хајде да убаците то овде. Креирање струја и претходна показивачи на чворова. Али када ми подесити те тројке? Где ћемо урадити у коду? Џеф? 

ПУБЛИКА: - услови вредност? 

ЈАСОН ХИРСЦХОРН: Која један у посебно? 

ПУБЛИКА: Само сам збуњена. Ако је вредност већа од овог чвора, не значи да желите да одете на следећи чвор? 

ЈАСОН Хирсцххорн: Дакле, ако је наша вредност већа од вредности овог чвора. 

ПУБЛИКА: Да, онда би хтео да ићи даље низ линију, зар не? 

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

ПУБЛИКА: Чекај, који је овај чвор и који је вредност? 

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

ПУБЛИКА: Ако је вредност већа од овог чвора. 

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

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

У реду. Почнимо. Асам, како да направите нову чвор? 

ПУБЛИКА: Ти ну *. 

ЈАСОН Хирсцххорн: Тако ми има да се овде. Ох, извините. Говорио си струцт *. 

ПУБЛИКА: А онда [? врста?] чвор или ц чвор. 

ЈАСОН Хирсцххорн: У реду. Ја ћу да га зовем нев_ноде тако да можемо да останемо доследни. 

ПУБЛИКА: И ви желите да подесите да на челу, први чвор. 

ЈАСОН Хирсцххорн: У реду. Дакле, сада ово показивање да - па ово још увек није направио нови чвор. Ово је само указује на Први чвор у листи. Како да направим нови чвор? Ако треба простор да креирате нови чвор. Маллоц. А колики? 

ПУБЛИКА: Величина струцт. 

ЈАСОН Хирсцххорн: величина Струцт. А шта струцт зове? 

ПУБЛИКА: Ноде? 

ЈАСОН Хирсцххорн: чвор. Дакле маллоц (сизеоф (чвор)); даје нам простор. И да ли је то линија - једна ствар је нетачно на овој линији. Да ли нев_ноде показивач на структуру? То је генеричко име. Шта је то - чвор, тачно. То је чвор *. А шта да радимо после ми маллоц нешто, Асан? Шта је прва ствар коју радимо? Шта ако не ради? 

ПУБЛИКА: О, проверите да ли указује на чвору? 

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

ПУБЛИКА: Ти би имати да урадите чвор *. Морао би направити једну не за нев_ноде али за чворови већ имамо. 

ЈАСОН Хирсцххорн: У реду. Дакле, тренутни чвор смо. Зваћу те Цурр. У реду. Ми смо одлучили да желе да задрже два јер морамо да знамо шта је пре њега. Шта они се иницијализује на? 

ПУБЛИКА: Њихова вредност у нашем листу. 

ЈАСОН Хирсцххорн: Па шта је Прва ствар на нашем списку? Или како да знамо где почетак наше листе је? 

ПУБЛИКА: Зар није прошао у функцију? 

ЈАСОН Хирсцххорн: Тачно. Донет је у праву овде. Дакле, ако је то прошло у функцију, почетак листе, што би требало да сет струја једнака? 

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

ЈАСОН Хирсцххорн: Листа. То је потпуно тачно. Сада има адресу почетак наше листе. А шта је претходна? 

ПУБЛИКА: Листа минус један? 

ЈАСОН Хирсцххорн: Нема ништа пре тога. Дакле, шта можемо да урадимо да означи ништа? 

ПУБЛИКА: Нулл. 

ЈАСОН Хирсцххорн: Да. То звучи као добра идеја. Савршено. Хвала. Идите кроз листу. Константин, колико дуго ћемо да иде кроз листу? 

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

ЈАСОН Хирсцххорн: У реду. Дакле, ако, док, за петљу. Шта ми радимо? 

ПУБЛИКА: Можда за петљу? 

ЈАСОН Хирсцххорн: Хајде да урадимо за петљу. У реду. 

ПУБЛИКА: И ми кажемо за - док текућа показивача није једнако нулл. 

ЈАСОН Хирсцххорн: Дакле, ако знамо стање, како можемо написати петљу заснован на том стању. Какав петље треба да користимо? 

ПУБЛИКА: Док. 

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

ПУБЛИКА: Ако струја-> н н мање од вредности. Или да преокрене. Свитцх то носач. 

ЈАСОН Хирсцххорн: Извини. 

ПУБЛИКА: Промените држач. 

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

ПУБЛИКА: Да ли је то још увек ја? 

ЈАСОН Хирсцххорн: Да. 

ПУБЛИКА: Ви - нев_ноде-> следећи. 

ЈАСОН Хирсцххорн: Па шта је који ће износити? 

ПУБЛИКА: То ће једнаку струју. 

ЈАСОН Хирсцххорн: Управо тако. И тако други - Шта још треба да ажурирате? 

ПУБЛИКА: Проверите да ли прошлост једнако нула. 

ЈАСОН Хирсцххорн: Ако прев - па ако предходна једнако нула. 

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

ЈАСОН Хирсцххорн: То значи то је постало глава. Па шта онда да радимо? 

ПУБЛИКА: Ми радимо главом једнако нев_ноде. 

ЈАСОН Хирсцххорн: Шеф једнако нев_ноде. А зашто глава овде, не наводе? 

ПУБЛИКА: Јер глава је глобална променљива, што је почетни место. 

ЈАСОН Хирсцххорн: Слатко. У реду. И - 

ПУБЛИКА: Онда ти још прев-> следећи једнако нев_ноде. А онда се вратите тачно. 

ЈАСОН Хирсцххорн: Где смо поставили нев_ноде крај? 

ПУБЛИКА: Ја бих - Кренуо сам да на почетку. 

ЈАСОН Хирсцххорн: Па шта линија? 

ПУБЛИКА: Након ако изјава проверу да ли се зна. 

ЈАСОН Хирсцххорн: Овде? 

ПУБЛИКА: Ја бих нев_ноде-> н једнака вредности. 

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

ПУБЛИКА: Ако је вредност већа него Цурр-> н - 

ЈАСОН Хирсцххорн: Како идемо на следећи чвор? 

ПУБЛИКА: Цурр-> н једнак нев_ноде. 

ЈАСОН Хирсцххорн: Тако је н шта део струцт? Цео број. И нев_ноде је показивач на чвор. Дакле, шта део Цурр треба да ажурирате? Ако не н, онда шта је други део? Ноа, шта је други део. 

ПУБЛИКА: О, следећи. 

ЈАСОН Хирсцххорн: Даље, тачно. Тачно. Даље је у праву један. И шта још морамо ажурирати, Ноах? 

ПУБЛИКА: Тхе показивачи. 

ЈАСОН Хирсцххорн: Па ми ажуриран струје. 

ПУБЛИКА: Претходна-> следећи. 

ЈАСОН Хирсцххорн: Да. У реду, ми ћемо паузирати. Ко може да нам помогне овде? Ману, шта да радимо? 

ПУБЛИКА: Мораш да подесите је једнак Цурр-> Нект. Али да ли то пре претходне линије. 

ЈАСОН Хирсцххорн: У реду. Још нешто? Аксхар. 

ПУБЛИКА: Не мислим да си значило да промените Цурр-> Нект. Мислим да треба да урадимо Цурр екуалс Цурр-> поред идите на следећи чвор. 

ЈАСОН Хирсцххорн: Жао ми је, где? На шта линија? Ова линија? 

ПУБЛИКА: Да. Направите Цурр једнако Цурр-> следећи. 

ЈАСОН Хирсцххорн: Дакле, то је тачно јер је струја показивач на чвор. И желимо да укажемо на следећа чвор онога Постаје тренутно указао на. Сама Цурр има следећи. Али, ако смо били да ажурирате цурр.нект, ми би се ажурирање стварног напомену Сама, не где је овај Показивач је показујући. Шта о овој линији, мада. Ави? 

ПУБЛИКА: Претходна-> поред једнако Цурр. 

ЈАСОН Хирсцххорн: Па опет, ако је претходни показивач на чвор, пред-> следећи је Стварна показивач у чвору. Дакле, ово би се ажурирање поинтер на чвор на Пост. Ми не желимо да ажурирате показивач у чвору. Желимо да ажурирате претходну. Па како то да урадимо? 

ПУБЛИКА: баш би то бити прев. 

ЈАСОН Хирсцххорн: Тачно. Претходна је показивач на чвор. Сада смо га мењају на нови показивач на чвор. ОК Идемо даље доле. Коначно, овај последњи услов. Џеф, шта ми овде радимо? 

ПУБЛИКА: Ако је вредност једнак Цурр-> н. 

ЈАСОН Хирсцххорн: Извини. О мој боже. Шта? Вредност == Цурр-> н. Шта да радимо? 

ПУБЛИКА: Ти би ослободили нашу нев_ноде, а онда ћеш се вратити фалсе. 

ЈАСОН Хирсцххорн: То је оно што смо до сада написао. Да ли неко има нешто да додате пре него што направите? У реду. Хајде да покушамо. Контрола може до краја о не-воид функцију. Ави, шта се дешава? 

ПУБЛИКА: Да ли би требало да се стави повратак истина ван вхиле петље? 

ЈАСОН Хирсцххорн: Ја не знам. Да ли ме желиш? 

ПУБЛИКА: Нема везе. Не. 

ЈАСОН Хирсцххорн: Аксхар? 

ПУБЛИКА: Мислим да треба да ставити ретурн на крају од вхиле петље. 

ЈАСОН Хирсцххорн: Па где да ли желиш да одем? 

ПУБЛИКА: Као ван вхиле петље. Дакле, ако сте изашли из вхиле то значи да сте стигли до краја и ништа није десило. 

ЈАСОН Хирсцххорн: У реду. Па шта да радимо овде? 

ПУБЛИКА: Ви ретурн ту као добро. 

ЈАСОН Хирсцххорн: О, ми урадите то на оба места? 

ПУБЛИКА: Да. 

ЈАСОН Хирсцххорн: У реду. Хоћемо ли? О мој боже. Жао ми је. Извињавам се на екрану. То је врста одлепио на нас. Дакле, изабрати опцију. Нула, по коду, затвара програм. Један убацује нешто. Хајде да убаците три. Уметак није била успешна. Идем да одштампате. Немам ништа. У реду. Можда је то била само случајност. Убаците једну. Не успе. У реду. Хајде да пролазе кроз ГДБ стварно брзо да проверите шта се дешава. 

Запамтите гдб. / Име вашег Програм нас добија у ГДБ. Да ли је то много за руковање? Трепери? Вероватно. Затворите очи и узети неки дубоко дише ако се уморите гледања на то. Ја сам ГДБ. Шта је прва ствар коју урадим ГДБ? Морамо да смислимо шта се овде дешава. Хајде да видимо. Имамо шест минута да схвати шта се дешава. Бреак главни. И онда, шта да радим? Карлос? Покрени. У реду. Хајде да одаберете опцију. И шта Н радим? Даље. Да. 

ПУБЛИКА: Зар нисте поменули - нисте рекли да глава, било је иницијализована на нулл на почетку. Али мислио сам да си рекао да је то у реду. 

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

ПУБЛИКА: Ох, умро. 

ЈАСОН Хирсцххорн: Ја само извукао га напоље. У реду. 

ПУБЛИКА: Можда је Други крај жице. 

ЈАСОН Хирсцххорн: Вау. Дакле, доња линија - шта си рекао? 

ПУБЛИКА: Рекао сам иронија техничке тешкоће у овој класи. 

ЈАСОН Хирсцххорн: Знам. Ако само ја имао контролу над тим делом. [ИНАУДИБЛЕ] То звучи сјајно. Зашто ви не почнете да размишљате о шта смо могли урадити лоше, и ми ћемо се вратити у 90 секунди. 

Авица, ја ћу да вас питам како то иде унутра инсерт_ноде да га дебуг. Дакле, ово је место где смо стали прошле. Како да идем унутра инсерт_ноде, Авица, да испита шта се дешава? Шта ГДБ команда? Пауза не би ме унутра. Да ли Маркиза зна? 

ПУБЛИКА: Шта? 

ЈАСОН Хирсцххорн: Шта команда ГДБ Ја користим да одем у ову функцију? 

ПУБЛИКА: Степ? 

ЈАСОН Хирсцххорн: Корак преко С То ме води унутра. У реду. Нев_ноде маллоцинг мало простора. То све изгледа као да је одлазак. Хајде да испитамо нев_ноде. Он је добио неку меморијску адресу. Хајде да проверимо - то је све тачно. Дакле, све овде изгледа бити исправно ради. 

ПУБЛИКА: Која је разлика између П и екрана? 

ЈАСОН Хирсцххорн: П стоји за штампање. И тако питате шта је разлика између тога и ово? У овом случају, ништа. Али генерално постоје неке разлике. И ви би требало да изгледа у ГДБ приручнику. Али у овом случају, ништа. Ми смо склони да користе отисак, ипак, јер ми не треба да се уради много више него принт једну вредност. 

У реду. Дакле, ми смо на линији 80 нашег кода, постављање чвора * Цурр једнако листи. Дозволите нам да одштампате Цурр. То једнако листу. Слатко. Чекај. То једнако нешто. То није у реду не. Тамо идемо. То је зато што у ГДБ, десно, ако то је линија сте на њему још није извршена. Тако да је потребно да се заправо куцате поред изврши линију пре виде своје резултате. Дакле, ту смо. Управо смо погубили ову линију, претходна једнако нула. Па опет, ако штампате претходна нећемо видети ништа чудно. Али ако заиста извршити да линија, онда ћемо видети да та линија радила. 

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

ПУБЛИКА: Не 

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

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

ПУБЛИКА: Па, ако је потребно да изврши више пута, само промените га у до-вхиле петље. 

ЈАСОН Хирсцххорн: У реду. Хоће да реши наш проблем, иако? 

ПУБЛИКА: У овом случају не ради чињеница да је листа празна. Па онда вероватно само треба да додате изјава да ако петље излазе онда морате да будете на крају листа, у којој вам тачка могу само да убаците. 

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

ПУБЛИКА: Ако сте већ добили чвор маллоцед, можете само да кажете нев_ноде-> поред једнако нула јер она мора да буде на крају. Или нев_ноде-> поред једнако нула. 

ЈАСОН Хирсцххорн: У реду. Извините. Нев_ноде-> следећи једнако нула јер смо на крају. То не га ставите унутра Како ћемо то ставити на листу? Право. То је само постављање једнака. Не како радимо ствари стави га на листи? Шта указује на крај листе? 

ПУБЛИКА: Глава. 

ЈАСОН Хирсцххорн: Извините? 

ПУБЛИКА: Шеф указује до краја листе. 

ЈАСОН Хирсцххорн: Ако нема ништа у листа, глава се указује на крај листе. Тако да ћу радити за Прво уметање. Шта ако постоји пар ствари на листи? Него ми не желимо да подесите главу једнака нев_ноде. Шта желимо да тамо радим? Да? Вероватно претходни. Хоће да раде? Подсетимо се да је само претходни показивач на чвор. И претходни је локална променљива. Дакле, ова линија ће поставити локалне променљиве, претходни, једнака или указујући на овом новом чвору. То неће заправо га ставите у нашем листу, мада. Како ћемо то ставити на нашем списку? Акцхар? 

ПУБЛИКА: Мислим да би ти урадите тренутни-> Нект. 

ЈАСОН Хирсцххорн: У реду. Цурр-> следећи. Дакле, опет, једини разлог смо доле Овде је, шта ради струја једнаки? 

ПУБЛИКА: Једнако нулл. 

ЈАСОН Хирсцххорн: И шта дешава ако радимо нулл-> следеци? Шта ћемо добити? Ми ћемо добити сегментације грешку. 

ПУБЛИКА: До Цурр једнако нула. 

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

ПУБЛИКА: Претходни-> следећи? 

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

ПУБЛИКА: То ће вратити лажно у овом случају? 

ЈАСОН Хирсцххорн: О, је је ће вратити фалсе. Али постоји још једна буба. Зато ћемо морати да се стави у повратку истинском. 

ПУБЛИКА: Да ли још увек претходни једнаки нулл на врху листе? 

ЈАСОН Хирсцххорн: Па претходна даље једнако нула на самом почетку. Дакле, како можемо добити преко тога? Да? 

ПУБЛИКА: Мислим да можете да урадите проверу пре док петља да види да ли је то празна листа. 

ЈАСОН Хирсцххорн: У реду. Дакле, идемо одавде. Да ли чек. Ако - 

ПУБЛИКА: Дакле, ако глава једнако једнако нулл. 

ЈАСОН Хирсцххорн: Ако глава једнако једнако нулл - који ће нам рећи да ли је празна листа. 

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

ЈАСОН Хирсцххорн: Шеф једнако нев_ноде? И шта још треба да урадимо? 

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

ЈАСОН Хирсцххорн: Не баш. Недостаје нам један корак. 

ПУБЛИКА: Нев_ноде следећа мора да укаже на нулл. 

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

ПУБЛИКА: Да. 

ЈАСОН Хирсцххорн: Да. И шта нам је потребно да се то промени на? Истина. Да ли то звучи добро свима до сада? Има ли било који - Ави, да ли имате нешто да додате? 

ПУБЛИКА: Не 

ЈАСОН Хирсцххорн: У реду. Тако смо направили неколико промена. Направили смо ову проверу пре ми отишао у за празну листу. Тако смо збринути празан листе. И ту смо се побринуо за убацивање нешто на крају листе. Тако да изгледа као овај док петље узимање брига о стварима између, негде на листи ако постоји су ствари на листи. 

У реду. Хајде да покренете овај програм поново. Не успе. 

ПУБЛИКА: Ниси га направи. 

ЈАСОН Хирсцххорн: О, Нисам га направити. Добра поента, Мајкл. Хајде да додате марка везана. Линија 87 има грешка. Линија 87. Алден, ово је линија коју си ми дала. Шта није у реду? 

ПУБЛИКА: То мора да буде на нулл. 

ЈАСОН Хирсцххорн: Одлично. Тачно у праву. То би требало да буде нула. Идемо поново направити. Цомпиле. У реду. Хајде да убаците три. Уметак је био успешан. Хајде да га одштампате. О, ако само можемо да проверимо. Али нисмо урадили принт још функцију. Хајде да унесете нешто друго. Шта би требало да улазимо? 

ПУБЛИКА: Седам. 

ЈАСОН Хирсцххорн: Седам? 

ПУБЛИКА: Да. 

ЈАСОН Хирсцххорн: Имамо СЕГ грешку. Тако смо добили једну, али ми је јасно не могу да добију две. То је 5:07. Тако смо могли да дебуг ово за три минута. Али ја ћу да нас оставити овде и прешли на хасх табеле. Али опет, одговори за овај код Ја ћу га пошаљи на вас у мало. Веома смо близу тога. Ја високо вам и да схватим шта се овде дешава и то поправити. Па ја ћу вам пошаљи овај код као добро, плус решење - вероватно решење касније. Прво овај код. 

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

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

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

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

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

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

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

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

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

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

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

ПУБЛИКА: То може наћи индекс у сталном времену? 

ЈАСОН Хирсцххорн: То није шта то значи. Али то је добра претпоставка. Још неко има претпоставку шта то значи? То је добра хасх функција је детерминистички? Ени? 

ПУБЛИКА: То кључ може да се мапира само на једном месту у хасх табели. 

ЈАСОН Хирсцххорн: То је потпуно тачно. Сваки пут када ставите у бундеву, увек враћа нулу. Ако сте ставили у вашем бундевом и хашиш Функција враћа нулу, али има вероватноћа повратка нешто друго већа од нуле - па можда може да се врати један понекад или два пута - да није добар хасх функција. Тотално си у праву. Ваш хасх функција треба да врати исти прецизан цео број, у овом случају, за исти тачан низ. 

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

У реду. Друга ствар је да је враћа валидне индексе. Донели смо се да раније. Ова хасх функција - Ох бои - хасх функција треба врати валидне индексе. Тако кажу - хајде да се вратимо на овом примеру. Мој хасх функција пребројава горе слова у речи. То је хасх функција. И то враћа цео број. Дакле, ако ја имам реч А, то је ће да се врати један. И то ће да стави овде. Шта ако сам ставио у речи палицом? То ће да се врати три. Где ићи палицом? 

То се не уклапа. Али то мора да иде негде. Ово је мој хеш табела после свега, и све мора да иде негде. Па где би требало да иду палицом? Било која мисли? Нагађања? Добри нагађања? 

ПУБЛИКА: Нула. 

ЈАСОН Хирсцххорн: Зашто нула? 

ПУБЛИКА: Због три модулу три је нула? 

ЈАСОН Хирсцххорн: Три модулу три је нула. То је велика претпоставка, и то је тачно. Дакле, у овом случају то би требало вероватно ићи на нулу. Дакле, добар начин да се осигура да ова тараба Функција враћа само валидне индекса се да је модулу величином табеле. Ако по модулу шта год то враћа по три, увек ћете добити нешто између нуле, један, и два. А ако то увек враћа седам, а увек по модулу по три, ти си увек ће добити исту ствар. 

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

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

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

Тако сам ставио у бундеву. То враћа нулу. И ја ставио овде бундеву. Онда сам ставио на - шта је још једна Ноћ вештица тематске-ствар? 

ПУБЛИКА: Цанди. 

ЈАСОН Хирсцххорн: Цанди! То је велики један. Ставио сам у слаткиша, бомбона и такође ми даје нулу. Шта да радим? Нека идеја? Зато што сте сви некако знају шта је одвојено Уланчавање. Дакле, никакве идеје шта да радим? Да. 

ПУБЛИКА: Стављање тетиве заправо у хасх табели. 

ЈАСОН Хирсцххорн: Значи идемо у извући добру идеју овде. У реду. 

ПУБЛИКА: Да ли су Хасхтабле [ИНАУДИБЛЕ] показивач који указује на почетак листе. А онда су бундева бити прва вредност у тој повезаној листи и слаткиша бити друга вредност у тој повезаној листи. 

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

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

ПУБЛИКА: показивачи на - 

ЈАСОН Хирсцххорн: Зато што вам рекао је повезана листа, тако - 

ПУБЛИКА: Чвор показивачи? 

ЈАСОН Хирсцххорн: Чвор показивачи. Ако се ствари у наш повезан листа су чворови онда они би требало да буде чворова показивачи. А шта су они у почетку равно? 

ПУБЛИКА: Нулл. 

ЈАСОН Хирсцххорн: Нула. Дакле, ту је наша ствар празна. Бундева враћа нулу. Шта да радимо? Шетња ми кроз њега? Заправо, Маркус већ ми је дао. Неко други ме је ходати кроз њу. Шта радимо када смо - ово изгледа веома слично оно што смо управо радили. Ави. 

ПУБЛИКА: Идем да нагађамо. Дакле, када се бомбона. 

ЈАСОН Хирсцххорн: Да. Па, имамо бундевице. Хајде да наш први. Имамо бундеву. 

ПУБЛИКА: У реду. Бундева враћа нулу. Дакле, ви га ставите у то. Или заправо, ви га ставите у повезаној листи. 

ЈАСОН Хирсцххорн: Како ми радимо стави га у повезаној листи? 

ПУБЛИКА: О, стварна синтакса? 

ЈАСОН Хирсцххорн: Само ходај - кажу више. Шта да радимо? 

ПУБЛИКА: Само убаците она као први чвор. 

ЈАСОН Хирсцххорн: У реду. Дакле, имамо чвор, бундеву. И сад како да га убаците? 

ПУБЛИКА: Можете доделити је на показивачу. 

ЈАСОН Хирсцххорн: Које показивач? 

ПУБЛИКА: показивач на нули. 

ЈАСОН Хирсцххорн: Па где зар ово ствар? 

ПУБЛИКА: За сада нулл. 

ЈАСОН Хирсцххорн: Па, то указује на нулл. Али ја стављам у бундеву. Па где би требало да укаже? 

ПУБЛИКА: За пумпкин. 

ЈАСОН Хирсцххорн: За бундеву. Тачно. Дакле, ово указује на бундеву. А где то ради показивач у тачки бундеве? До 

ПУБЛИКА: Нулл. 

ЈАСОН Хирсцххорн: За нулл. Тачно. Дакле, ми смо само убаци нешто у повезаној листи. Ми само написао овај код да се то уради. Скоро смо га скоро добили потпуно испуцала. Сада смо убацили слаткише. Наш бомбона такође иде на нулу. Па шта да радимо са бомбона? 

ПУБЛИКА: То зависи од тога да ли или не покушавамо да га сортирају. 

ЈАСОН Хирсцххорн: То је потпуно тачно. То зависи од тога да ли или не ми покушавамо да га сортирају. Претпоставимо да нисмо ће то средити. 

ПУБЛИКА: Па онда, као што смо разговарали пре, то је најједноставније само да га стави одмах на почетку, тако да се показивач од нула поена до слаткиша. 

ЈАСОН Хирсцххорн: У реду. Држи се. Дозволите ми да створи слаткише овде. Дакле, ово показивач - 

ПУБЛИКА: Да, требало би сада се указује на бомбоне. Затим имамо показивач из бомбона тачка на бундеву. 

ЈАСОН Хирсцххорн: Овако? И кажу да имамо још један ствар да мапира на нулу? 

ПУБЛИКА: Па, ви само раде исту ствар? 

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

У реду. Сва питања у вези посебном цхаининг? Како то функционише? Молимо питајте их сада. Ја стварно желим да се уверим да сви разумети пре него што кренемо. 

ПУБЛИКА: Зашто сте ставили бундеве и бомбона у исти део хасх табеле? 

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

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

У реду. Карлос. Линеарни прескок би подразумевало - ако смо судар на нули, ми ће изгледати у следећем месту да види да ли било је отворено и стави га тамо. И онда гледамо у наредном спорту и види да ли је то било отворено и стави га тамо. Дакле, налазимо следећи доступан отворено место и стави га тамо. Има ли још питања? Да, Ави. 

ПУБЛИКА: Као наставак тога, шта мислите до следећег спот? У хасх табеле или у повезаној листи. 

ЈАСОН Хирсцххорн: За линеарне програмирање, но повезане листе. Следећи место на хасх табеле. 

ПУБЛИКА: У реду. Дакле хасх табела ће бити иницијализована величини - као што је број стрингова да сте уметања? 

ЈАСОН Хирсцххорн: Би Желим да то буде заиста велики. Да. Овде је слика онога што смо само нацртао на табли. Опет, имамо судар овде. на 152. И видећете смо креирали повезана листа ван ње. Опет, хеш табела одвојена Уланчавање приступ није она коју морати да подесите за проблеме шест али је онај који много студенти имају тенденцију да преузме. Дакле, у том смислу, нека нам укратко разговарамо пре него што кренете о проблему шест, а онда ћу поделити са вама причу. Имамо три минута. 

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

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

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

И коначно величина. Величина треба спровести. Ако не спроведе величину - Ја ћу то рећи овако. Ако не спроведе величину у тачно једна линија кода, укључујући врати изјаву, ви сте ради величину погрешно. Тако да проверите величину, за пуну дизајн поена, то радите у тачно један линија кода, укључујући повратак изјава. 

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