>> СПИКЕР 1: У реду, тако да смо се вратили.
Добродошли у ЦС50.
Ово је крај недеље седам.
Дакле, подсетити да последњи пут, почели смо гледа мало софистициранији
структуре података.
Пошто до сада, сви смо заиста имали на располагању је ово, низ.
>> Али пре него што је одбаците као низ не све то интересантно, што је заиста
заправо, шта су неки од плусева ове једноставне података
структура до сада?
Шта је то добро?
До сада, као што смо видели?
Шта имаш?
Ништа.
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Шта је то?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Фиксна величина.
У реду, па зашто је фиксна величина добра, иако?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: У реду, тако да је ефикасан у осећај да можете доделити
фиксни износ од простора, и надам се да Управо толико
простора колико желите.
Дакле, то би могао да буде апсолутно плус.
>> Оно што је још горе страна низа?
Да?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Сви - жао?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Све кутије у меморији или један поред другог.
И то је корисно - зашто?
То је сасвим тачно.
Али како можемо искористити ту истину?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Управо тако, можемо да пратимо где је све само знајући
једна адреса, односно адреса Први бајт тог меморију.
Или у случају ниске, адреса првог
Чар у том низу.
А одатле, можемо наћи крај низа.
Можемо наћи други елемент, Трећи елемент, и тако даље.
>> И тако фенси начин да се опише то карактеристика је да нам дају низови
директног приступа.
Само помоћу угласте заграде нотација и број, можете да пређете на
специфичан елемент у низу у сталном времену, Биг О
једног, да тако кажем.
>> Али ту је било и неки недостаци.
Шта низ не баш лако?
Оно што није добро?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Шта је то?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Проширење у величини.
Тако мана низу су управо супротно од онога што
позитивних су.
Дакле, једна од мана је да је фиксне величине.
Тако да стварно не могу да расте.
Можете да прерасподели већи комад меморије, а затим померите старе елементе
у нови низ.
А онда слободно стари низ, за пример, коришћењем маллоц или сличну
Функција се зове реаллоц, који поново додељује меморија.
>> Реаллоц, као страну, покушава да вам да меморија која је поред низа
које већ имате.
Али можда се ствари укупно око.
Али укратко, то је скупо, зар не?
Јер ако имате комад меморије ове величине, али ви стварно желите један
ове величине, а желите да сачувате оригинални елементи, имате
отприлике линеарно време процес удвајања то треба да се догоди из
старо за ново низ.
А реалност поставља радом систем поново и поново и
поново за велике комаде меморије може да почне да вас коштати мало времена и.
Тако да је и благослов и проклетство у прикрије, чињеницу да ови низови
су фиксне величине.
Али ако уместо тога увести нешто овако, коју смо назвали повезана
листа, добијамо неколико позитивних и неколико мана овде.
>> Тако повезана листа је једноставно података структура коју чине Ц Структуре у ово
случај, где струцт, подсетимо, је само контејнер за један или више специфичних
Типови променљивих.
У том случају, шта типове података Чини се да унутар структуре попунити да
Последњи пут када смо се зове чвор?
Сваки од ових правоугаоника је чвор.
И сваки од мањих правоугаоника у њему је тип података.
Које врсте смо рекли су у понедељак?
Да?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: променљива и показивач, или тачније, инт, за н,
и показивач на дну.
И оних десити да се 32 бита, на бар на рачунару као што је овај ЦС50
Апарата, и тако су извући једнако величине.
>> Дакле, шта се користи показивач мада за очигледно?
Зашто додали ово стрелицу сада када су низови тако лепо и чисто и једноставно?
Шта се ради показивач за нас у сваком од ових чворова?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Управо тако.
То вам је рекао где следећи је.
Тако да сам на неки начин користи аналогију користите конац да некако
провуците заједно ових чворова.
А то је управо оно што ми радимо са показивачи јер сваки од њих
комади меморије могу или не могу бити заразне, бацк то бацк то бацк
унутар РАМ, јер сваки пут када позовите маллоц говорећи, дај ми довољно
бајтова за нови чвор, да би могло бити овде, или можда овде.
Можда овде.
Ви једноставно не знам.
>> Али, користећи показиваче на адресама ти чворови, можете их бодом
заједно на начин који изгледа визуелно као листа, чак и ако се ове ствари
Све шири у целом једном или Ваши два или четири своје гигабајта РАМ-а
унутар свог рачунара.
>> Дакле мана, онда, повезана листа је шта?
Која је цена коју смо очигледно плаћају?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Више простора, зар не?
Ми смо, у овом слуцају, удвостручио износ простора, јер смо отишли
од 32 бита за сваки чвор, за сваки инт, тако да сада 64 бита, јер ми морамо да
држати око показивача, као добро.
Можете добити више ефикасности ако ваш Структ је већи од ове једноставне ствари.
Ако заиста имате ученика у од којих је неколико жица за
име и кућа, можда матични број, можда неким другим пољима укупно.
>> Дакле, ако имате довољно велики строги, онда можда цена је показивач
није тако велика ствар.
Ово је мало корнер предмета у који смо складиштење тако једноставна примитивни
унутар повезане листе.
Али поента је иста.
Ти си дефинитивно троши више меморије, али ви добијате
флексибилност.
Јер сад ако желим да додам елемент на почетку ове листе,
Морам да издвоји нови чвор.
И ја морам да ажурирате само оне Стрелице некако само од кретања
неколико смерница око.
>> Ако желим да убаците нешто у половини листе, ја не морам да
гурнути у страну све што смо радили у Последњих недеља "са нашим волонтерима који су
представља низ.
Ја само могу да издвоје нови чвор и онда само указују на стрелице у
различита правца, јер не морају да остану у стварни
меморија прави ред као да сам нацртао овде на екрану.
>> И онда на крају, ако желите да убаците нешто на крају листе, то је
још лакше.
То је врста произвољне нотацији, али 34 је показивач, Погоди.
Која је вредност њеног показивача већине вероватно извући нешто као стари
школа антена тамо?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: То је вероватно нула.
И заиста, то је за једног аутора представљање нулл.
А то је зато што апсолутно ништаван Треба да се зна где је крај повезана
Списак је, да не би и даље следе и пратећи и након ових стрелица
неком смеће вредности.
Дакле, нула ће значити да нема више чворова на десно од броја 34,
у овом случају.
>> Зато предлажемо да можемо имплементирати Овај чвор у коду.
А ми смо видели ову врсту синтаксе пре.
Типедеф само дефинише нови тип за нама, нам даје као синоним
ниска је за цхар *.
У овом случају, то ће нам дати стенографски запис тако да струцт чвор
може уместо тога само да се напише као чвор, што је много чистији.
То је много мање опсирнији.
>> Унутар чвор је очигледно инт позвао н, а затим струцт чвор *
што значи управо оно што смо желели стрелице да значи, показивач на други
чвор на потпуно исти тип података.
И ја предлажем да се спроведе функција претраге овако, што у
први поглед може да изгледа мало комплекс.
Али, хајде да видимо то у контексту.
>> Пусти ме да одем на уређај овде.
Дозволите ми да отворим фајл који се зове Листа нула тачка х.
И то само садржи Дефиниција коју Управо сам видео пре тренутак за овим подацима
Тип се зове чвор.
Дакле, ми смо ставили да у дот х датотеке.
>> И као по страни, иако је ово програм који сте видети је
није све тако сложен, то је заиста Конвенција приликом писања програма за
стави ствари као типове података, да се повуче константе понекад, унутар вашег
заглавље датотеке, а не нужно у Ваша датотека Ц, свакако када ваш
програми добијају све већи и већи, тако да знате где да погледате како за
документација у неким случајевима, или основе за овако,
дефиниција неке врсте.
>> Ако сад отворим листу нула тачка Ц, приметићете неколико ствари.
Садржи неколико заглавља датотеке, највише од које смо већ видели.
То укључује сопствени хеадер фајл.
>> И успут, зашто то је двоструко цитира овде, за разлику од угла
конзоле на линију која Сам тамо нагласио?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Да, па то је локални фајл.
Дакле, ако је овде фајл са своје на линији 15, на пример, користите
знакова навода уместо од Угаоне заграде.
>> Сада ово је веома интересантно.
Обратите пажњу да сам проглашена глобална променљиве у овом програму на линији 18
зове прво, идеја је ово ће бити показивач на први
чвор у мом повезаној листи, а ја сам иницијализују се нулл, јер сам
није додељена сваки стварни чворови још увек.
>> Дакле, ово представља, сликовито, шта смо Видео сам малопре на слици као
да показивач на далеко левој страни.
Управо сада, да показивач нема стрелу.
Уместо тога, она је само нулл.
Али, он представља оно што ће бити адреса први стварни
чвор на овој листи.
Тако сам спроведен је глобална јер, као што ћете видети, све ово
Програм се спроводи у животу је повезана листа за мене.
>> Сада имам неколико прототипова овде.
Одлучио сам да спроведе карактеристике као брисање, уметање, претраживање, и
траверсал -
последњи само што хода преко листа, штампање његове елементе.
А сада је моја главна рутина.
А ми не проводе превише времена на Ово јер је то врста, надам се
стари шешир до сада.
>> Ја ћу да урадите следеће, док корисник сарађује.
Зато је један, ја ћу да одштампате из овог менија.
И ја сам га форматиран као чисто што сам могао.
Ако корисник упише у једном, то значи желе нешто да избришете.
Ако корисник упише у два, то значи они желе да убаците нешто.
И тако даље.
Ја ћу вас онда питати затим на команду.
И онда ћу користити Затамњена.
>> Дакле, ово је веома једноставан менуинг интерфејс где само треба да унесете
мапирање број један ове команде.
И сада имам лепу чисту прекидач изјаву да ће да укључите
год корисник унесе
И ако су уписали једну, ја ћу позовите брисање и сломити.
Ако се откуца два, ја ћу позовите убаците и сломити.
>> Запазите сада сам сваки пут од њих на истој линији.
Ово је само стилска одлука.
Обично смо видели нешто овако.
Али сам одлучио, искрено, мој програм Погледао више читљиви, јер
било је само четири предмета у само списак је овако.
Потпуно легитимно коришћење стила.
И ја ћу да урадим ово све док члан није откуцао нулу, што сам
одлучили ће значити да желе да престану.
>> Сада обратите пажњу шта сам да радимо овде.
Идем да очигледно ослободи листу.
Али, више о томе на тренутак.
Хајде да прво покрене овај програм.
Дакле, дозволите ми да већи терминал прозор, тачка црта 0 листа.
Ја ћу ићи напред и убаците стране куцање два, број 50, и сада
видећете списак је сада 50.
И мој текст само помера се мало.
Дакле, сада приметити листа садржи број 50.
>> Хајде да урадимо још један уметак узимањем два.
Хајде да унети број као један.
Листа је сада једна, затим 50.
Дакле, ово је само текстуална репрезентација листе.
И да убаците још један број као број 42, који се надамо
ће се завршити у средини, јер Овај програм посебно сортирању
елементи јер их убацује.
Тако да га имамо.
Супер једноставан програм који би могао апсолутно су користили низ, али ја
буде користио повезану листу Само тако могу да динамички
расте и психијатар га.
>> Дакле, хајде да погледамо за претрагу, ако покрените команду три, желим да тражи
за, рецимо, број 43.
И ништа је очигледно пронашао, зато што сам се вратио никакав одговор.
Па хајде да поновимо ово.
Тражи.
Хајде да се потрага за 50, или пре претрагу за 42, што је леп
мало суптилније значење.
И нашао је смисао живота тамо.
Број 42, ако не знате референца, на Гооглеу.
У реду.
Дакле, шта је овај програм урадио за мене?
Је само дозвољено да на тај начин убаците далеко и трагање за елементима.
>> Хајде да брзо напред, онда, да та функција ми је погледао
у понедељак као тизер.
Дакле ове функције, ја тврдим, претраге за елемент у листи прво
један, пита корисника, а затим позива Затамњена да се стварни инт
коју желите да потражите.
>> Онда приметити.
Ја ћу створити привремену променљиву у складу назива показивач 188 -
ПТР -
Могао је то назвао ништа.
И то је показивач на чвор зато сам рекао чвор * тамо.
А ја иницијализација да буде једнака први, тако да ја имам своје ефективно
прст, да тако кажем, на веома први елемент листе.
Дакле, ако је моја десна рука овде је ПТР сам указујући на исту ствар да прво
указује на.
>> Дакле, сада је поново у коду, шта се даље дешава -
ово је заједничка парадигма када итератинг преко структура као
повезана листа.
Ја ћу да урадим следеће док показивач није једнако тако док нулл
мој прст не указује на неке НУЛЛ вредност, ако показивач стрелица Н једнака н.
Прво ћемо приметити да је оно што је н корисник откуцао на ГетИнтс зову овде.
>> И показивач стрелица н значи шта?
Па ако се вратимо на слици овде, ако имам прст показујући на
да први чвор који садржи девет, на стрелица у суштини значи да иду у
чвор и зграби вредност на локацију Н, у овом случају, подаци поље зове н.
>> Као страну - и ми смо видели тај пар недеља пре када неко питао -
Ова синтакса је нова, али то није то да нам дају овлашћења да
није већ имају.
Шта је ово еквивалентно са коришћењем фраза дот нотација и звезда пар
недеља пре када смо скинуле овај слој мало прерано?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Тачно, то је звезда, а онда је звезда тачка Н, са
заграде овде, што изгледа, искрено, ја мислим да је много
мање јасни за читање.
Али показивач звезда, као и увек, значи ићи тамо.
И када си тамо, који подаци поље желите да приступите?
Па ви користите тачка нотацију за приступ Структуре података поље, и ја
Желим посебно н.
>> Искрено, ја бих рекао ово теже је само за читање.
То је теже да се сетим где не иду заграде,
звезда и све то.
Дакле, свет донела неке синтаксичке шећер, да тако кажем.
Само секси начин да се каже, ово је еквивалент, и
можда више интуитивно.
Ако показивач заиста показивач, арров нотације средства иду тамо и наћи
поље у овом случају зове н.
>> Дакле, ако га не нађем, приметити шта радим.
Ја једноставно штампају, посто сам ја нашао, укључивања у вредности за тај инт.
Позивам спавам на тренутак само да натури паузе ствари на екрану да бисте
дају кориснику други да апсорбују што се управо догодило.
И онда сам сломити.
Иначе, шта да радим?
Ажурирам показивач на једнак показивач стрелицу поред.
>> Дакле, само да буде јасно, то значи да идемо тамо, користећи своје старе школе нотацију.
Дакле, то само значи да се на било упериш у, који је у веома
Први случај је да мислим на струцт са девет у њему.
Тако да сам тамо отишао.
И онда тачка нотација значи, се вредност на следећи.
>> Али вредност, иако је то привукло као уска, је само број.
То је нумеричка адреса.
Према томе, ова линија кода, да ли написано овако, мање јасни
начин, или овако, мало више интуитиван начин, само значи да померим руку
од првог чвора на следећи, а онда следећи, а затим
следећи, и тако даље.
>> Тако се нећемо задржавати на друге имплементације уметање и брисање
и траверсал, прва два од који су прилично укључени.
И ја мислим да је прилично лако добити изгубио када то раде вербално.
Али, оно што можемо да урадимо јесте покушати да утврди како
најбоље да се то уради визуелно.
Јер ја бих предложио да ако желите да убаците елемената у ово
постојећи списак, који има пет елемената -
9, 17, 22, 26, и 33 -
ако је требало да спроведе ово у код, треба да размотре како да се
да ће то урадити.
>> И ја бих предложио пужевим корацима при чему, у овом случају мислим, шта су
могуће сценарије које смо наићи уопште?
Приликом спровођења уметак за повезана листа, то се дешава само да буде
Конкретан пример за величине пет.
Па ако желите да унесете број, свиђа кажем број један, и
одржавање реда поређане, где очигледно не број један треба да
иди у овом конкретном примеру?
Као и на почетку.
>> Али, оно што је занимљиво је да Ако желите да убаците једну у ово
листа, шта треба посебан показивач очигледно да се ажурира?
Прва.
Дакле, рекао бих да је ово први случај да ћемо желети да размотрите,
Сценарио укључује убацивање у почетак листе.
>> Хајде да уберу искључен можда тако лако или чак лакше случају, релативно говорећи.
Рецимо да желите да убаците број 35 у сортираном редоследу.
Очигледно припада тамо.
Дакле, шта показивач очигледно ће морају да се ажурирају у том сценарију?
34 је показивач не постане нула али адреса струцт
садржи број 35.
Дакле, то је случај два.
Тако је већ, ја сам некако квантизирање колико посла морам да урадим овде.
>> И на крају, очигледно средњи случај заиста, у средини, ако желим да
убаците нешто као рецимо 23, који иде између 23 и 26, али
Сада се ствари мало више укључени зато што
показивачи треба да се промени?
Дакле, 22 очигледно треба да се промени јер он не може да укаже на 26. више.
Он треба да укаже на нови чвор који Ја ћу морати да издвоји позивом
маллоц или неки еквивалент.
>> Али, онда сам и треба ми тај нови чвор, 23 у овом случају, да има свој показивач
показујући на кога?
26.
И тамо ће бити редослед операција овде.
Јер ако урадим ово глупо, и ја на пример старт на почетку
листа, а мој циљ је да убаците 23.
И провери, да ли то припада Овде, близу девет?
Не.
Да ли овде припада, поред 17?
Не.
Да ли овде припада поред 22?
Да.
>> Сада, ако сам ја луд овде, а не размишљам о овоме, могао бих
издвојити мој нови чвор за 23..
Можда ажурирање показивача из чвор се зове 22, указујући
је у новом чвору.
И онда ста треба да ажурирате новог чвора показивач да буде?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Управо тако.
Указујући на 26.
Али даммит ако нисам већ ажурирали 22 је показивач да се укаже на овог момка, а
сада имам сирочади, остатак списка, да се тако изразим.
Дакле, редослед операција овде ће бити важна.
>> Да бисте то урадили могу да краду, кажу, шест добровољаца.
И хајде да видимо да ли можемо урадити визуелно уместо кода питању.
И ми имамо неке дивне стреса лопте за вас данас.
У реду, шта је са један, два, у назад - на крају тамо.
три, четири, обојица момци на крају.
И пет, шест.
Наравно.
Пет и шест.
Добро, и ми ћемо доћи да вас следећи пут.
У реду, идемо горе.
>> Добро, пошто си овде прво, желите да буде један незгодно
овде Гоогле стакла?
У реду, па, у реду, стакло, видео записа.
У реду, ви сте на добром путу.
>> У реду, тако да ако ви можете доћи овде, ја сам припремио унапред
неки бројеви.
У реду, хајде овамо.
А зашто не одеш мало даље тако.
И да видимо, како се зовеш, са Гоогле стакла?
>> СТУДЕНТ: Бен.
>> СПИКЕР 1: Бен?
У реду, Бен, ви ћете бити први, буквално.
Дакле, ми ћемо вам послати до краја фазе.
У реду, и ваше име?
>> СТУДЕНТ: Јасон.
>> СПИКЕР 1: Џејсон, ОК ти ћеш бити број девет.
Дакле, ако желите да пратите Бен тај начин.
>> СТУДЕНТ: Џил.
>> СПИКЕР 1: Џил, ти ћеш бити 17, који ако бих учинио више
интелигентно, ја бих почео на другом крају.
Ти иди тамо.
22.
А ти си?
>> СТУДЕНТ: Мери.
>> СПИКЕР 1: Мери, бићете 22.
А твоје име?
>> СТУДЕНТ: Крис.
>> СПИКЕР 1: Крис, бићеш 26.
И онда на крају.
>> СТУДЕНТ: Диана.
>> СПИКЕР 1: Диана, бићете 34.
Тако сте дошли овамо.
>> У реду, тако савршен сортиране нареди већ.
И идемо напред и урадите тако да заиста можемо -
Бен си само мало потрази Повратак у нигде.
У реду, тако да идемо напред и то описују употребе оружја, баш као да сам, тачно,
шта се дешава.
Дакле, само напред и да сам себи стопала или два између себе.
И само напред и укаже са једне стране, Ко год да треба бити усмерена на
на основу тога.
А ако си нула само упутити равно на под.
У реду, добро.
>> Дакле, сада имамо повезану листу, и пусти ме предлаже да ћу играти улогу
ПТР, па нећу гњавити ношење око овог.
А онда - неко глуп конвенција - можете назвати ово све што желите -
претходник показивач, пред показивач -
то је само надимак ми дали у наш узорак код за леву руку.
С друге стране да ће се чување евиденцију о томе ко је ко у
Следећи сценарији.
>> Претпостављам, прво, желим да се уберу искључен да је први пример убацивања, каже
20, у листу.
Зато ћу да треба неко да отелотворују број 20 за нас.
Зато морам да маллоц некоме из публике.
Хајде горе.
Како се зовеш?
>> СТУДЕНТ: Брајан.
>> СПИКЕР 1: Брајан, у реду, тако да ће бити чвор који садржи 20.
У реду, хајде овамо.
И очигледно, где Брајан се припада?
Дакле, у средини - у ствари, чекај мало.
Ми ово радимо из реда.
Радимо ово много теже него то треба да буде на првом месту.
У реду, идемо на слободан Бриан Брајан као и реаллоц пет.
>> У реду, тако да сада желимо да убаците Брајан и пет.
Па хајде овамо поред Бен за тренутак.
И ви сте, претпостављам да кажете где ова прича иде.
Али, хајде да добро размислите о редослед операција.
И управо је ово визуелно који ће се построје
са том примеру кода.
Дакле, овде сам ПТР указују на почетку не на Бена, пер се, него на било
вреднују он садржи, што у овом случају је - оно зовеш?
>> СТУДЕНТ: Јасон.
>> СПИКЕР 1: Џејсон, тако и Бен и ја смо показујући на Јасона у овом тренутку.
Тако да сада морам да се утврди, где се Брајан припада?
Дакле, једино што имам приступ сада је његов н податак.
Зато ћу да проверим, је Брајан мање него Јасон?
Одговор је истина.
>> Па шта сад треба да се догоди, у исправном стању?
Морам да ажурирате колико показиваче је укупно у овој причи?
Где ми је рука и даље показује на Џејсон, и руку - ако желите да
стави руку као, на неки начин, ја Не знам, знак питања.
У реду, добро.
>> У реду, тако да имате неколико кандидата.
Или Бен и ја и Брајан или Џејсон и сви остали, који
показивачи треба да се промени?
Колико укупно?
>> У реду, тако два.
Мој показивач није битно више јер ја сам само привремено.
Тако да је ова двојица, по свој прилици, и Бен и Брајан.
Тако да ме предлажем да ажурирате Бен, пошто је он први.
Први елемент ове листе сада ће бити Брајан.
Дакле, Бен тачка на Брајана.
Ок, шта сада?
>> Ко добија указао на кога?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: У реду, тако је Брајан да укаже на Јасона.
Али, да сам изгубила појам тог показивача?
Да ли знам где је Јасон?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: радим, јер сам привремено показивач.
И вероватно, нисам се променила да укаже на нови чвор.
Тако да једноставно имамо Бриан тачку на кога ја мислим на.
И ми смо готови.
Дакле један случај, убацивање у почетак листе.
Била су два кључна корака.
Један, морамо да ажурирате Бена, а затим морамо да ажурирате Брајана.
И онда ја не морам да се трудите траипсинг кроз остатак
списак, јер смо већ нашао локација, јер је припадао
лево од првог елемента.
>> У реду, тако да прилично јасно.
У ствари, изгледа као да смо скоро тако да је ово превише компликовано.
Па хајде да сада чупају искључен крај листе, а видите где
сложеност почиње.
Дакле, ако сада, ја Аллоц из публике.
Свако ко жели да игра 55?
У реду, видео сам прво руку.
Хајде горе.
Да.
Како се зовеш?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Хабата.
ОК, идемо горе.
Ти ћеш бити број 55.
Тако да, наравно, припада на крају листе.
Па хајде да играте симулације са мном као ПТР за тренутак.
Дакле, прво ћу да укаже на год Бенова показујући на.
Ми смо обоје указујући сада на Брајана.
Дакле, 55 је не мање од пет.
Дакле, ја ћу да се ажурира по указујући на следећи поинтер Брианову, који
Сада је, наравно, Јасон.
55 није мањи од девет, тако Идем да ажурирате ПТР.
Идем да ажурирате ПТР Ја ћу да ажурирате ПТР.
И ја ћу - хм, шта је зовеш?
>> СТУДЕНТ: Диана.
>> СПИКЕР 1: Диана показује, наравно, на нула са својом левом руком.
Дакле, где се заправо Хабата припадају јасно?
Лево, овде.
Па како да знам да је ту доспела Мислим да сам зезнуо.
Јер шта је уметност ПТР овај тренутак у времену?
Нулл.
Дакле, иако је, визуелно, можемо очигледно види све ово
момци овде на сцени.
Не сам пратила претходну особа на листи.
Немам прст који указује, у овом случају, број 34 чвора.
>> Па хајде да заиста почну овоме.
Дакле, сада сам стварно треба Друга локална променљива.
И то је оно што ћете видети у Стварни број узорак Ц, где је као ја идем,
када сам упдате моју десну руку до тачке Џејсон, остављајући за собом Брајане, ја
Боље почните да користите леву руку да ажурирање где сам био, тако да као да идем
кроз ове листе -
више него што сам намеравао неспретно сада овде визуелно -
Ја ћу доћи до крај листе.
>> Ова рука је и даље нула, што је прилично бескорисно, осим да укаже
Ја сам јасно на крају листе, али сада барем имам ово
претходник показивач показивање овде, па шта сада предаје и шта треба показивачи
да буде ажуриран?
Чија рука хоћеш за реконфигурацију први?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: У реду, тако Диана.
Где желите да покажете Диана показивач на лево?
На 55, по свој прилици, тако да сам тамо убацили смо.
А где би требало да показивач иде 55?
Доле, представља нулл.
И моје руке, у овом тренутку, не само због тога што су управо
привремене променљиве.
Дакле, сада смо урадили.
>> Дакле, додатна сложеност тамо - и није тако тешко спровести,
али ми треба секундарни променљиву да би да ли пре него што кренем своје право
рука, ја ажурирати вредност моје лево рука, пред показивач у овом случају, тако да
да имам пратећи показивач да пратите где сам био.
Сада као страну, ако мислиш ово путем, ово изгледа као да је
мало непријатно да треба да задржи пратите ове леве руке.
>> Шта би друго решење на овај проблем био?
Ако имаш да редизајнира податке Структура говоримо
до сада?
Ако је то само врста осећа мало непријатно да су, као, два показивача
пролази кроз листу, ко би други могао су, у идеалном свету, одржава
информације које нам је потребно?
Да?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Управо тако.
Право да заправо има занимљиво Клица идеје.
И ова идеја претходне показивача, показујући на претходни елемент.
Шта ако сам управо оличена да унутар саме листе?
И то ће бити тешко замислити то без свих папира
пада на под.
Али, претпоставимо да су ови момци и из њихових руку да претходни
показивач, и следећи показивач, тиме спровођење шта ћемо назвати двоструко
повезана листа.
То би омогућило да некако уназад, много лакше без мене,
програмер, морате да задржите трацк ручно -
заиста ручно -
где сам раније био на листи.
Тако да то неће урадити.
Ми ћемо наставити да то једноставно зато што је то ће доћи у цени, дупло
много простора за показивачи, ако желите једно друго.
Али то је заиста заједничка структура података позната као
двоструко повезане листе.
>> Хајде да урадимо последњи пример овде и ставио ови момци ван њихове беде.
Тако маллоц 20.
Хајде се из пролаза тамо.
У реду, како ти је име?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Молим?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Демерон?
Добро дошли на горе.
Ви треба да буде 20.
Ви очигледно ће припадају између 17 и 22.
Тако да ме науче своју лекцију.
Ја ћу почети показивач показујући на Брајана.
И ја ћу имати своју леву руку само упдате Бриану као што сам се пресели у
Џејсон, провера да ли 20 мање од девет?
Не.
Да ли је 20 мање од 17?
Не.
Да ли је 20 мање од 22?
Да.
Па шта показивачи или руке треба да промените где су они сада показује?
>> Тако да можемо да урадимо 17 указујући на 20.
Дакле, то је у реду.
Где желимо да истакнемо показивач сада?
На 22.
А знамо где је 22, опет хвала до мог привременог показивачу.
Дакле, ми смо у реду тамо.
Дакле, због овог привременог складиштења Ја сам стално пратите где су сви.
А сада можете визуелно да иде у којој ви припадате, а сада нам треба 1, 2, 3,
4, 5, 6, 7, 8, 9 стрес лоптице, и аплауз за
ови момци, ако можемо.
Лепо урађено.
>> [Апплаусе]
>> СПИКЕР 1: У реду.
И можете да задржите делове папира као успомена.
>> У реду, тако да, верујте ми то је много лакше да хода кроз то са
људи него што је то са стварним кодом.
Али, оно што ћете наћи у само једном тренутку Сада, то је иста - Ох, хвала.
Хвала -
је да ћете наћи да је исте податке структура, повезана листа, заправо могу
да се користи као грађевински блок за још софистициране структуре података.
>> А схватити и овде је тема која апсолутно ми смо увели више
комплексност у примени овог алгоритма.
Убацивања, па ако смо ишли кроз њега, брисање и претраживање, је мало
компликованије од тога је са низом.
Али, ми смо добили неку динамику.
Добијамо адаптивног структуру података.
>> Али опет, ми плаћамо цену да се одређени додатне сложености, како у
имплементација.
И ми смо одустали случајан приступ.
И да будем искрен, не постоји неки леп очистите слајд ја да ти дам
каже ево зашто повезана листа је бољи од низа.
И нека остане на томе.
Јер тема понавља сада, чак и више у наредних неколико недеља, је
да не постоји нужно тачан одговор.
>> То је разлог зашто имамо посебан осу решења за проблем поставе.
То ће бити веома контекст осетљиви да ли желите да користите ове податке
структуру или да је један, и то ће зависити од онога што је вама важно у смислу
ресурса и сложености.
>> Али, дозволите ми да предложи идеални подаци структура, свети грал, био би
нешто што је константа време, без обзира на то колико је ствари
унутар њега, не би било невероватно ако структура података вратио одговоре
константа време.
Да.
Ова реч је у великом речнику.
Или не, ова реч није.
Или било таквих проблема тамо.
Па да видимо, ако не можемо макар предузети корак ка томе.
>> Дозволите ми да предложи нову структуру података која се може користити за различите ствари,
у овом случају зове хеш табела.
И тако смо се вратили у ствари поглед у низу, у овом случају, и
нешто произвољно, ја сам нацртао ово хасх табела као низ са врстом
дводимензионални низ -
односно то је овде приказана као два димензионални низ - али то је само
низ величине 26, тако да ако се позовите сто низа, стони држач
нула је правоугаоник на врху.
Табела 25 носач је правоугаоник на дну.
А ово је како ја могу нацртати података Структура у којој желим да сачувате
Имена људи.
>> Тако на пример, а ја нећу извући Цела ствар овде на графоскоп, ако
имао овај низ, који сада ћу да позовите хеш табели, а то је опет
локација нула.
Ово овде је локација један, и тако даље.
Ја тврдим да ја желим да користите ове податке структура, ради расправе,
да меморишете имена људи, Алиса и Боб и Чарли и других таквих имена.
Дакле, мислим да је ово сада као почетке од, рецимо, речник
са много речи.
Они се деси да се називи у нашем примеру овде.
А ово је све сувише Германе, можда, да се спроводи контролу правописа, као што смо
Можда проблем за шест сет.
>> Дакле, ако имамо низ укупне величине 26 тако да је ово 25. место
на дну, а ја тврдим да је Алице прва реч у речнику
имена које желим да убаците у РАМ, у ову структуру података, где су
инстинкти који вам каже да је Алиса Име би требало да иде у том низу?
>> Имамо 26 опције.
Где желимо да је ставим?
Ми јој желимо у конзолу нула, зар не?
За Алице, назовимо да нулу.
И Б ће бити један, и Ц ће бити два.
Дакле, ми ћемо писати Алисин име овде.
Ако убаците Боба, његов име ће отићи овде.
Чарли ће отићи овде.
И тако даље доле кроз Ова структура података.
>> Ово је диван структура података.
Зашто?
Па шта је покренут време убацивање име људског на оваквом
структура података сада?
С обзиром да је ово сто се спроводи, заиста, као низ.
Па то је константа време.
То је поредак једне.
Зашто?
>> Па како да утврдите где је Алице припада?
Можете погледати на којој слово њеног имена?
Прва.
И можете да добијете, ако је ниска, само гледајући низ
носач нула.
Дакле нулте карактера ниске.
То је лако.
То смо урадили у крипто Пре додељивања недеља.
И онда када знате да Алисин Писмо је капитал, може се одузети
искључивање 65 или капитала сама по себи, То нам даје нулу.
Дакле, ми сада знамо да Алиса припада на локацији нула.
>> А с обзиром показивач на овим подацима структуре, неке врсте, колико дуго траје
је потребно да ме пронађе локацију нулу, у низу?
Само један корак, право је време константно због случајног приступа се
Предложена је карактеристика низа.
Дакле укратко, откријем шта индекс Алице се зове, која је, у
овом случају је, или хајде да реши да на нулу, где је Б и Ц је један
два, решио да се Време је константа.
Само треба да погледамо своје прво писмо, схватите где је нула
низ је такође константно време.
Дакле, то је технички као два корака уназад.
Али то је и даље константна.
Дакле, ми то зовемо Биг О једне, па смо убаци Алиса у овој табели у
константа време.
>> Али, наравно, ја сам био наиван овде, зар не?
Шта ако је Арон у класи?
Или Алициа?
Или било ког другог имена почињу са О: Где ћемо ставити
та особа, зар не?
Мислим, сада има само три људи на столу, тако да можда можемо
треба ставити на локацији Арона нула један два три.
>> Добро, ја могу ставити овде.
Али онда, ако покушамо да убаците у Давида ова листа, где се Дејвид иде?
Сада наш систем почиње разбијање доле, зар не?
Јер сада Дејвид завршава овде ако Арон је заправо овде.
И сада цела ова идеја има чиста структура података која нам даје
константно време уметања није више константа време, јер морам да
провери, ох, јебо те, неко је већ у Алисине локацији.
>> Дозволите ми да испитују остатак ових података структура, у потрази за место да стави
неко као име Арону.
И тако и то је полазна да линеарно време.
Осим тога, ако сада желите да пронађете Арон у ову структуру података, и ви
провери, и Аронов име није овде.
У идеалном случају, само би рекао Арону не у структури података.
Али ако почнете да зарађујете простора за Арон где би било Д
или Е, да, у најгорем случају, морам да проверим Цела структура података, у
ком случају се преноси у нешто линеарно од величине табеле.
>> Па добро, ја ћу то поправити.
Проблем је у томе што сам имао 26 елемената у овом низу.
Пусти ме да га промените.
Упс.
Дозволите ми да промени, тако да радије буду од Величина 26 укупно, приметио дно
Индекс ће се променити на минус 1 н.
26. Ако је очигледно сувише мали за људе " имена, јер има хиљаде
имена у свету, хајде да направи на 100, 1.000 или 10.000.
Хајде да издвоји много више простора.
>> Па то не мора да смањи вероватноћа да нећемо имати два
људи са именима почиње са, и тако, да ћеш покушати да стави
имена на локацију нули даље.
Још увек су на сударе, која значи да и даље треба да се стави решење
Алиса и Арон и Алиша и других имена почињу са А на другом месту.
Али колико је то проблем?
Која је вероватноћа да сте има сударе у дата
Структура овако?
>> Па, пусти ме - Вратићемо на то питање овде.
А погледајте како бисмо могли прво решити га.
Дозволите ми станите овде овај предлог.
Оно што смо управо описали је алгоритам, хеуристички зове линеарна
прескок где, ако сте покушали да убаците нешто овде у овим подацима
структуру, која се зове хеш табела, и нема места тамо, ви
заиста испитују структуру података провере, ово је на располагању?
Да ли је ово Доступно је то доступно?
Да ли је то доступно?
И када је коначно, убаците Име које сте првобитно намењен
на другом месту на тој локацији.
Али, у најгорем случају, једино место може да буде на самом дну података
структура, на самом крају низа.
>> Дакле линеарни прескок, у најгорем случају, прелази у линеарном алгоритма где
Арон, ако се деси да се убаци последњи у овој структури података, могао би
сударају са овом првом месту, али онда завршим пех на самом крају.
Дакле, ово није константа време свети грал за нас.
Овај приступ уметање елемената у Структура података који се зове хеш
сто не изгледа да буде константна време бар не у општем случају.
То може да пренесе у нешто линеарно.
>> Па шта ако смо решили судара нешто другачије?
Дакле, овде је софистициранији приступ томе шта је још
зове хеш табела.
И по хашиш, као на страну, шта Мислим да је индекс
Сам раније поменуо.
Да размотре нешто може бити мисли као глагол.
>> Дакле, ако сте хасх Алиса је име, хасх функција, да тако кажем,
треба да врати број.
У овом случају је нула, ако је она спада у Локација нула, један, ако она припада у
локација један, и тако даље.
Дакле, мој хасх функција до сада је супер једноставно, само гледајући
Прво слово нечијег имена.
Али хасх функција узима као улаз неки податак,
стринг, инт, шта год.
И избацује најчешће без броја.
И тај број је где да се подаци елеменат спада у структури података
познат овде као хеш табели.
>> Дакле, само интуитивно, ово је мало другачији контекст.
Ово је у ствари односи на пример укључују рођендани, где
можда постоји чак 31 дана у месецу.
Али шта је та особа одлучи да уради у случају судара?
Контекст сада бити, не судара имена, али је судар на рођендане,
ако двоје људи имају исти рођендан 2. октобра, на пример.
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Да, тако да овде имамо усклађивање повезаних листа.
Па изгледа мало другачије него што је нацртао раније.
Али изгледа да смо на низ на левој страни.
То је један показатељ, јер не посебног разлога.
Али, то је још увек низ.
То је низ показивача.
И сваки од тих елемената, сваки од ови кругови или косе црте - сласх
представља нулл - сваки од ових показивачи се очигледно указује на
шта структура података?
Повезана листа.
>> Дакле, сада имамо могућност да Тешко код у наш програм
величина табеле.
У овом случају, знамо да никада нема више од 31 дана у месецу.
Тако тешко кодирање вредности као што је 31. разумне у том контексту.
У контексту имена, тешко кодирање 26 није неразумно то народном
имена само почетак, на пример, писмо укључује преко З.
>> Можемо да их све стрпати у тим подацима структуре све док, када се
судара, овде не стави имена, ми уместо да мисле од ових ћелија
не као жице сами, већ као показивачи на, на пример, Алице.
А онда Алиса може имати још један показивач на друго име почиње са
О: И Боб заправо иде овамо.
>> И ако постоји други који почиње име са Б, он завршава овде.
И тако сваки од елемената ове Табела два, ако смо дизајнирали ово
мало паметно -
хајде -
ако смо дизајнирали ово мало паметно, сада постаје адаптивног податке
структура, где нема чврсто ограничење о томе колико елемената можете да уметнете
у њега, јер ако имате судара, то је у реду.
Само напред и додајте га у оно шта је било мало
познат као повезане листе.
>> Па хајде да застанемо на тренутак.
Која је вероватноћа судара на првом месту?
Добро, можда сам више размишљам, можда Ја сам преко инжењеринг овај проблем,
јер знате шта?
Да, ја могу доћи до произвољно Примери са врха моје главе као
Алисон и Арон, али у стварности, дао униформу дистрибуција
улаза, односно неки случајни уметања у структури података, оно што је стварно
вероватноћа судара?
Па испада, то је заправо Супер Хигх.
Дозволите ми да генерализујемо ово Проблем је што ово.
>> Дакле, у соби од н ЦС50 студената, што је вероватноћа да је најмање
два студента у соби имају исти рођендан?
Тако да је оно. неколико Хунд -
200, 300 и неколико људи овде стотина људи код куће данас.
Дакле, ако сте желели да се запитамо шта је вероватноћа двоје људи
у овој соби има исти рођендан, можемо да решимо ово.
А ја у ствари тврдим постоје два људи са истим рођендан.
>> На пример, да ли ико имају рођендан данас?
Јуче?
Сутра?
У реду, тако да изгледа као да идем морати да уради 363 или тако више
времена да се заиста схвати Ако имамо судар.
Или бисмо могли урадити математички него мукотрпно
радим ово.
И предлажу следеће.
>> Зато предлажем да се моделира вероватноћа двоје људи који имају
Исто рођендан као могућност 1 минус вероватноћа не има један
исти рођендан.
Тако да се ово, а то је само фенси начин писања овог, за
Прва особа у соби, он или она могу имати један од могућих
рођендани под претпоставком 365 дана у години, уз извињење особама са
фебруар 29. рођендан.
>> Дакле, прва особа у овој просторији је бесплатна да има било који број рођендана
од укупно 365 могућности, тако да ми ћемо то урадити 365 подељено са 365,
што је један.
Следећа особа у просторији, ако је циљ је да избегне судар, може само
имати свој рођендан на начин много различитих могућих дана?
364.
Дакле, други термин у овом изразу је у суштини раде да математика за нас
одузимањем искључен један могући дан.
А онда следећег дана, следећег дана, Сутрадан доле на укупан број
људи у просторији.
>> И ако онда размислите, шта је онда вероватноћа не поседовања свакога
јединствене рођендане, али опет минус 1 да, ми добијамо израз
да могу веома изванредном споју изгледа овако.
Међутим, веома је занимљиво да погледа визуелно.
Ово је табела у којој на к-оси је број људи у просторији,
Број на рођендане.
На и-оси је вероватноћа у судару, двоје људи
имају исти рођендан.
>> И понети из ове криве да чим ти се свиђа 40
студенти, ви сте се на 90% вероватноће цомбинаторицалли два
или више људи који имају исти рођендан.
А када дођете до 58 људи воле да је скоро 100% шансе два
људи у соби ће имати исти рођендан, иако постоји
365 или 366 могућих кашике, и Само 58 људи у соби.
Само статистички вероватно ћете се сударе, која укратко
мотивише ову дискусију.
То чак и ако добијемо фенси овде, и почети да се те ланце, још увек смо
ће имати судара.
>> Тако да отвара питање, шта је Трошкови ради уметања и брисања
у структури података као што је овај?
Па да предложи -
и да се вратимо на екран преко овде - ако имамо н елемената у
листа, па ако покушавамо да убаците н елемената, а ми имамо
Колико укупно кашике?
Рецимо 31 Укупно кашике у случају рођендана.
Која је максимална дужина једног од ових ланаца потенцијално?
>> Ако опет има 31 могуће рођендани у датом месецу.
И управо смо циркулише свима -
заправо то је глупа пример.
Хајде да уместо 26.
Дакле, ако заиста има људи чија имена почети до З, дајући на тај начин
нас 26 могућности.
И ми користимо структуру података као што коју смо управо видели, чиме смо
низ показивача, од којих сваки указује на повезаној листи, где је
Први списак је свако по имену Алиса.
Друга листа је сваки са име почиње са, почевши
са Б, и тако даље.
>> Шта ће дужина сваке од те листе ако претпоставимо леп чист
дистрибуција имена до З преко целе структуре података?
Има н људи у структури података подељено са 26, ако су лепо су
распоређено у току целе структура података.
Дакле, дужина сваког од њих ланци је н подељено са 26..
Али у великом О нотацији, шта је то?
Шта је то заправо?
Дакле, то је заиста само н, зар не?
Зато што смо рекли у прошлости, ух да ћете поделити по 26 година.
Да, у стварности то је брже.
Али у теорији, то није суштински све то брже.
>> Дакле, ми се не чини да је све то много ближи овом светим гралом.
У ствари, ово је само линеарно време.
Пакао, у овом тренутку, зашто не бисмо само користите једну велику повезану листу?
Зашто не бисмо користили један велики низ за смештање имена
сви у просторији?
Па, има ли још нешто убедљив о хеш табели?
Да ли постоји још нешто убедљив података о структури
да изгледа овако?
Ово.
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Добро, а опет ако је то само линеарно време алгоритам, а
линеарна структура података пут, зашто не бих Само име продавнице свима у велики
низ, или у великом повезане листе?
И престани да правиш ЦС толико много теже него то треба да буде?
Шта је убедљив о томе, чак и иако сам га огребе напоље?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Уметања не?
Скупо више.
Дакле уметци потенцијално могао даље бити константна време, чак и ако ваши подаци
структура изгледа овако, низ показивачи, од којих се указује на
потенцијално повезане листе.
Како си могао да постигне константна Време убацивање имена?
Стави га у напред, зар не?
>> Ако се жртвујемо гол дизајн из раније, где смо желели да
свачије име, на пример, сортирају, или свих бројева на сцени поредани,
претпоставимо да имамо некласификовани повезана листа.
То нас кошта само један или два корака, као у случају Бен и Брајан
раније, да убаците елемент у почетак листе.
Дакле, ако ми није стало сортирање свих од имена почињу или све
имена почињу са Б, још можемо оствари сталан Време убацивања.
Сада гледајући Алиса или Боб, или било које име уопште још шта?
То је велика О од н подељено са 26, у идеалан случај када су сви равномерно
дистрибуира, где има колико је као што постоје З, који је вероватно
нереално.
Али, то је још увек линеарно.
>> Али, овде морамо вратити до тачке од сада асимптотическој нотацији
теоретски тачно.
Али, у стварном свету, ако ја тврдим да мој програм може да уради нешто 26 пута
бржи од твог, чији програм ћеш радије користе?
Ваш или мој, који је 26 пута брже?
Реално, човек чија је 26 пута брже, чак и ако теоретски
наши алгоритми раде у истом асимптотско време извршавања.
>> Дозволите ми да предложи другачији решење заједно.
А ако то не одушевити, ми смо из структура података.
Дакле, ово је Трие -
некако глупо име.
Она долази из претраживања база података, а реч је написано Трие, Т-Р-и-е, због
Курс преузимање звучи као Трие.
Али то је историја речи Трие.
>> Дакле Трие је заиста нека врста дрвета, и то је такође игра на ту реч.
А чак и ако не могу да га виде са овим визуелизације, Трие је
дрво структуиран, попут породичног стабла са један предак на врху и још много
за унуке и праунуке као оставља на дну.
Али сваки чвор у Трие је низ.
И то је у низу - и хајде да поједностављују за тренутак - то је
низ, у овом случају, од величине 26, где сваки чвор поново је низ величине
26, где нулти елемент који представља низ, а последњи
елемент у сваки такав представља низ З.
>> Тако да ја предлажем, онда, да ови подаци структура, познат као Трие, може бити
Такође се користи за складиштење речи.
Видели смо малочас како бисмо могли да сачувате речи, или у овом случају имена, а ми
раније видели како можемо да сачувате бројеве, али ако се фокусирамо на имена или ниске
овде, шта је занимљиво приметити.
Ја тврдим да је име Максвел унутар ове структуре података.
Где видите Маквелл?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: На левој страни.
Дакле, оно што је занимљиво са овим подацима Структура је него у продавници
М-стринг-Кс-Ш-Е-Л-Л обрнута коса црта нула, све цонтигуоусли, шта ти уместо тога
прати.
Ако је ово Трие као структуре података, сваки од чворова чији је поново низ,
и желите да сачувате Маквелл, прво индекс и тако корен је чвор, тако
да говори, на највишем чвор, на локацију М, десно, тако
отприлике у средини.
А онда одатле, да пратите показивач детету чворова, да тако кажем.
Дакле, у смислу породичног стабла, ви га пратите на доле.
И то вас одвести у други чвор Са леве стране, што је
само још један низ.
>> А онда, ако желите да сачувате Маквелл, вам је показивач који представља
, Што је овај овде.
Онда идите на следећи чвор.
И обавештење - то је разлог зашто је слика мало варљива -
Овај чвор изгледају супер мали.
Али, са десне стране је И и З. То је само аутор је скраћени
слика, тако да заправо виде ствари.
Иначе ова слика ће бити веома широк.
Дакле, сада сте у индекс локацију Кс, онда Е, онда је Е, онда сам, па шта је онда Л
то радозналост?
>> Па, ако користимо ову врсту нове преузимају како да сачувате низ у
структура података, и даље треба да суштини провјерите у подацима
структура која реч завршава овде.
Другим речима, сваки од ових чворова некако мора да се сетим да смо
заправо пратили све ове показивача и одлазе мало
презла на дну ове овде структуре да укаже М-А-Кс-В-Е-Л-Л
заиста у овом структуром података.
>> Тако смо могли урадити на следећи начин.
Сваки од чворова у слици смо управо тестера има једну, низ величине 27.
А сада је 27, јер у п сет шест, ми заправо ћемо вам дати апостроф,
тако да можемо имати имена као О'Реилли и други с апострофа.
Али, иста идеја.
Сваки од ових елемената у низ указује на структуру
чвор, па само чвор.
Дакле, ово је веома подсећа наше повезаној листи.
>> И онда имам Боолеан, што ћу позовите реч, која це једноставно бити
ако је тачно реч завршава на тај чвор у стаблу.
То практично представља мали троугао смо видели малопре.
Дакле, ако је реч завршава на тај чвор у дрво, да реч поље ће бити истина,
који је концептуално проверу искључен, или смо цртање овај троугао, да тамо
је овде реч.
>> Дакле, ово је Трие.
А сада питање је, шта је његово време ради?
Да ли је велики О од н?
Да ли је то нешто друго?
Па, ако сте н имена тих података структура, Максвел само је једна од
их, што је покренут време убацивање или проналажење Маквелл?
Шта је време извршавања убацивања Маквелл?
Ако постоји н друга имена Већ у табели?
Да?
>> СТУДЕНТ: [ИНАУДИБЛЕ].
>> СПИКЕР 1: Да, то је дужина назива, зар не?
Дакле, М--к-Ш-Е-ја-ја тако да изгледа овако алгоритам је велики о седам.
Сада, наравно, име ће варирати у дужини.
Можда је то кратко име.
Можда је име дуже.
Али, оно што је кључно је да је овде то је исти број.
А можда то није баш константна, Али Бог, ако је реално, у
речник, вероватно постоји нека граница о броју слова у
име особе у одређеној земљи.
>> И тако можемо претпоставити да вредност је константна.
Ја не знам шта је то.
То је вероватно већи од мислимо да јесте.
Јер увек постоји неки кутак случај са лудом дуго име.
Дакле, назовимо је К, али је и даље константа вероватно, јер сваки
име у свету, барем у одређене земље, или је то дужина
краћи, тако да је константан.
Али, када смо рекли да је нешто велико О константне вредности, шта је то
заиста одговара?
То је заправо иста ствар како наводи константно време.
>> Сада смо некако вара, зар не?
Некако смо усклађивање неку теорију овде да кажем да је добро, ред је к
заиста само наредби, и то је константа време.
Али, то је стварно.
Пошто кључни увид овде је да ако смо н имена већ у ово
структура података, а ми убаците Максвел, је количина времена које је потребно да нас
убаците Маквелл уопште погођени по томе колико других људи
су у структури података?
Не изгледа да буде.
Да сам имао више од милијарду елементе за ову Трие, а затим убаците Маквелл, је
утицала је на све?
Не.
И то је за разлику од свих дневних података структуре које смо видели до сада, где
време рада вашег алгоритма је потпуно независно од тога колико
ствари јесте или није већ у тој структури података.
>> И тако уз то пружа сада је прилика за п шест сет, који ће
поново укључити спровођење сопствене правописа, читање у 150.000
речи, како најбоље да сачувате није нужно очигледан.
И иако сам тежио да пронађе свети грал, не знам
тврде да је Трие.
У ствари, хеш табела може веома добро доказати да буде много ефикаснији.
Али, то су само -
то је само једна од одлуке о дизајну ћете морати да направите.
>> Али, хајде да затварање 50 или тако секунди да се завири у оно што лежи
напред следеће недеље и даље што смо транзицији из ове командне линије
света, ако Ц Програми веб ствари на језицима као што су и ПХП и
Јава и сама интернет, протоколи као што су ХТТП, који сте
узети здраво за готово годинама сада, а већина сваког откуцаног
дана, можда, или видео.
И ми ћемо почети да одлепите слојеви Шта је Интернет.
А шта је то код чини основу данашње алата.
Дакле 50 секунди овог тизер овде.
Ја вам Ратници Интернету.
>> [ВИДЕО РЕПРОДУКЦИЈА]
>> -Он је дошао са поруком.
Са протоколом све своје.
Он је дошао у свет сурове зидова, далеко унцаринг рутери, и опасности
горе од смрти.
Он је брз.
Он је јак.
Он је ТЦПИП.
И он има своју адресу.
Ратници у мрежи.
>> [ЕНД ВИДЕО РЕПРОДУКЦИЈА]
>> СПИКЕР 1: Тако интернету ће радити од наредне недеље.