[Музика свири] DAVID Маланом: Ова е CS50. И ова е како на почетокот и end-- како literally-- речиси на крајот на шест неделно. 

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

ПУБЛИКАТА: [нечујни] DAVID Маланом: Навистина. И повеќе интересно, не дај Боже, ние се одржи едно предавање во петок на почетокот на семестарот, тоа е она што го гледаме се случи. Така, денес, ние се причестуваат во малку повеќе за структури на податоци. И да ви даде повеќе од солидна ментална модел за проблемите во пет, кој е сега надвор. Правописни грешки, при што, ние ќе ви рака текстуална датотека околу 100.000 плус Английский зборови, и ви се случува да имаат да дознаам како да умно ги вчитате во меморијата, во RAM меморија, користејќи некои податоци структурата на вашиот избор. 

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

ПУБЛИКАТА: вметнување. 

DAVID Маланом: вметнување. Што сакаш да кажеш со тоа? 

ПУБЛИКАТА: Насекаде заедно Листа [нечујни]. 

DAVID Маланом: Добро. Така можете да вметнете елемент секаде каде сакате во средината на листата без да се влага ништо, кои заклучивме, во нашата сортирање дискусии, не е секогаш добра работа, бидејќи е потребно време за да всушност се движат сите оние луѓе лево или десно. И така со поврзана листа, можете да само ги распредели со Примерок, нов јазол, а потоа и ажурирање на неколку pointers-- два, три операции max-- и ние сме во можност да слот некој во било каде во листа. 

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

ПУБЛИКАТА: [нечујни] DAVID Маланом: Совршена. Совршен. Тоа е навистина динамичен. И дека не сте извршиле, во однапред, за да некои фиксна големина на парче на меморија, како што ќе има до со низа, главата, од кои е тоа што ќе може да одвои јазли само на барање на тој начин со користење на само колку простор како што всушност треба. За разлика низа, може да случајно се доделат премалку. И тогаш тоа е само ќе за да биде болка во вратот да ги пренамени нови поголеми низа, копирајте сè што повеќе, ослободи стариот низа, а потоа се движи вашиот бизнис. Или уште полошо, може да се доделат начин повеќе меморија отколку што навистина треба, и така си оди за да имаат многу слабо населени низа, така да се каже. 

Така поврзана листа дава овие Предностите на динамичност и флексибилност со инсерции и бришење. Но сигурно мора да има цена платена. Всушност, една од темите проучени квиз нула беше неколку размени ние сме виделе досега. Значи она што е платена цена или Недостатоци на поврзани листа? Да. 

ПУБЛИКАТА: Не случаен пристап. 

DAVID Маланом: Не случаен пристап. Но кој се грижи? Случаен пристап не звучи релевантни. 

ПУБЛИКАТА: [нечујни] DAVID Маланом: Токму така. Ако сакате да имате одредени algorithm-- и дозволете ми да всушност предложи бинарен пребарување особено, кои е еден ние сме се користи доста bit-- ако немате случаен пристап, не можете да го направите тоа едноставни аритметички на изнаоѓање како средината елемент и скокање право на него. Вие наместо треба да почне во првата елемент и линеарно пребарување од лево кон десно, ако сакате да се најде средината или било кој друг елемент. 

ПУБЛИКАТА: Тоа веројатно е потребно повеќе меморија. 

DAVID Маланом: требаат повеќе меморија. Каде е дека дополнителни чини доаѓаат од во меморијата? 

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

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

Па, ако сте како мене, ти може да се види дека ова е m, па јас ќе одам да се вид на се стави ова во, ако ова е мојата маса или ми кат каде Јас сум ширење работи out-- или мојот низа really-- Јас би можеле да се стави сите на г-ѓа таму. Ох. Еве А. Па јас би можеле да стави Како овде. Ох. Еве уште еден А. Одам да се стави дека овде. Еве З. Еве уште еден М. И така Јас би можеле да почнат да прават купови вака. А потоа можеби и јас ќе одам во подоцнежните и вид на многу nitpicky-ly вид поединецот хемороиди. Но поентата е јас ќе изгледа на внесување на што сум раце и јас ќе го направи некои пресметува одлука врз основа на кој влез. Ако тоа започнува со, го стави таму. Ако тоа започнува со Z, го стави над таму, и сето она помеѓу. 

Па ова е техника која е општо позната како hashing-- H-A-S-Н- кои обично значи дека земајќи ја како влезни и користење на тоа влез за да се пресмета вредност, обично голем број, и дека број е индекс во складирање сад, како низа. Значи со други зборови, јас би можеле да имаат хеш функција, како што правам јас во мојата глава, дека ако видам некој е име кој започнува со, Одам да се мапираат дека на нула во мојата глава. И ако видам некој со Z, јас сум се случува да се на сајтот, кој до 25 во мојата глава а потоа се стави дека во последните повеќето куп. 

Сега, ако мислите дека за не мојот мозок но C програма, што броеви може да ви се потпрат за да се постигне тоа истиот резултат? Со други зборови, ако се имаше ASCII карактер, како да се утврди она кофа да го стави во? Најверојатно не сакаат да стави ја во кофа 65, која ќе биде како таму без добра причина. Каде сакате да се стави во однос на нејзината ASCII вредност? Каде сакате да направите за да нејзините ASCII вредност да излезе со попаметни кофа да го стави во? 

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

DAVID Маланом: Да. Па минус А или минус конкретно 65, ако тоа е капитал А. Или 98, ако тоа е со мали букви. И, така што ќе ни овозможи да се, многу едноставно и многу аритметички, стави нешто во кофа како тоа. Така што се испоставува, ние всушност го направите оваа, како и дури и со квизови. 

Па можеби ќе се сетат ли заокружено вашиот име настава колеги е на насловната страница. И беа организирани имиња ТФ во овие колумни по азбучен ред, и, верувале или не, кога сите 80 плус од нас здруживме друга ноќ да одделение, Последниот чекор во нашата оценување процес е да хаш на тестови во голем простор на подот на [нечујни] и да се постават квизови сите надвор во точно редоследот на нивната ТФ имиња на насловната страница, бидејќи тогаш тоа е многу полесно за нас да се бара преку дека за користење на линеарна пребарување или некој вид на мудрост за ТФ да се најдат неговите или квизови нејзините ученици. 

Па оваа идеја на hashing тоа ќе го видите е доста моќен е всушност прилично вообичаена и многу интуитивен, многу како можеби се делат и Conquer беше во недела нула. Јас брзо напред до Hackathon пред неколку години. Оваа беше Zamyla и неколку други вработени поздрав студенти како што дојде во. И имавме куп преклопен табели таму со имињата. И имавме имињата на организиран со слични Како што таму и З.Ш. таму. И така еден од TFS многу умно напиша на ова како на инструкции за тој ден. И во 12 недела од семестарот ова сите направени совршена смисла и сите знаеше што да прави. Но во секое време сте подредени во ист начин, сте за спроведување на истиот поим на хашиш. Така нека си го малку формализира. Тука е низа. Се подготвени да биде малку широк само да ги отслика, визуелно, дека ние може да се стави жици во нешто како ова. И оваа низа е јасно на вкупната големина 26. И нешто што се нарекува маса произволно. Но, ова е само препевот на уметникот на она што хаш табелата може да биде. 

Така хаш табелата сега се случува да биде на повисоко ниво на податоци структура. На крајот на денот ние сме за да се види дека може да се спроведе хаш табелата, која е многу сличен на проверка во линија на Hackathon многу вака маса се користат за подредување испит книги. Но хаш табелата е вид на ова високо ниво концепт кој би можел да користи низа под хаубата да ја спроведат, или пак може да се користи листата должина, или дури и можеби некои други структури на податоци. И сега тоа е theme-- преземање некои од овие основни состојки како низа и оваа зграда блокира сега на листа должина и види што друго можеме да изградиме на врвот на оние, како состојки во рецепт, со што се повеќе и повеќе интересни и корисни конечните резултати. 

Па со хаш табелата да ја спроведе во меморијата сликовито вака, но како може тоа всушност се кодира нагоре? Па, можеби едноставно како е ова. Ако капацитет во сите капи, е само некои constant-- на пример 26, за 26 писма на alphabet-- Јас би можеле да се јавам на моите променлива маса, и јас би можеле да тврдат дека јас ќе одам да стави знак ѕвезди во таму, или стринг. Така, тоа е толку едноставно како ова ако сакате да се спроведе хаш табелата. А сепак, ова е навистина само низа. Но, повторно, хаш маса е сега што ние ќе јавете се апстрактни тип на податоци, тоа е само вид на концептуална наслояване на врвот на нешто повеќе светски сега како низа. 

Сега, како да одиме за решавање на проблемите? Па, порано имав луксуз имаат доволно маса простор тука така што би можел да стави квизови насекаде сакав. Па како може да оди тука. ZS може да оди тука. Г-ѓа може да оди тука. А потоа имав некои екстра простор. Но, ова е малку измамник право сега, бидејќи оваа табела, ако јас навистина мислев на тоа како низа, е само ќе биде на некоја фиксна големина. 

Па технички, ако јас се повлече до квиз друг ученик и да видиме, ох, овој човек име започнува со премногу, Јас вид на сакаат да го стави таму. Но, штом го ставив таму, ако оваа табела навистина претставува низа, Одам да се императивни или затирания кој и квиз овој ученик е. Нели? Ако ова е низа, само едно нешто може да оди во секоја од овие клетки или елементи. И така јас вид на имаат да одбереш. 

Сега порано јас вид на измамени и го направи ова или јас само вид на рангирани им горе едни со други. Но, тоа не се случува да лета во кодот. Значи, каде што би можеле да го ставам втор студент чие име е ако сите морав е ова достапни маса простор? И јас сум користел три слота и тоа изгледа како таму е само уште неколку други. Она што можете да направите? ПУБЛИКАТА: [нечујни] DAVID Маланом: Да. Можеби ајде да го прости. Нели? Тоа не се вклопува каде што сакам да го стави. Па ќе одам да го стави технички каде Б ќе одат. Момент, се разбира, јас сум почнуваат да си ја наслика во еден агол. Ако стигнам до студент чие име е всушност Б, сега B се случува да бидат преместени малку напред, како што може да се случи, да, ако ова е Б, сега мора да оди тука. 

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

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

ПУБЛИКАТА: n. DAVID Маланом: Еднаш го слушнав голема О на n. Не е точно. Но ние ќе ги разграничат зошто во само еден миг. Што друго може да е? 

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

ПУБЛИКАТА: Тоа е една. DAVID Маланом: Тоа е една. Нели? Оваа е низа, која значи имаме случаен пристап. И ако мислиме на ова како нула и ова како 25, и сфаќаме дека, ох, тука е мојот влез С, Јас секако може да се конвертира S, ASCII карактер, до соодветен број помеѓу нула и 25 и потоа веднаш стави го таму каде што припаѓа. 

Но, се разбира, штом стигнам до вториот човек кој е име е А или Б или Ц на крајот, ако јас сум користел линеарни љубопитство како моето решение, трчање време на вметнување во најлош случај е всушност ќе се префрлат во што? И јас го чувам тука правилно рано. ПУБЛИКАТА: [нечујни] DAVID Маланом: Значи тоа е n навистина еднаш имате доволно голема група на податоци. Па, од една страна, ако Вашата низа е доволно голем и на вашите податоци е редок доволно, добие оваа прекрасна константно време. Но штом ќе почнете да добивање на повеќе и повеќе елементи, и само статистички ќе добиете повеќе луѓе со писмо Како и нивните име или писмо B, тоа може потенцијално префрлат во нешто повеќе линеарна. Па не е сосема совршена. Така би можеле да го направи подобро? 

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

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

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

DAVID Маланом: Да. Тоа изгледа како тоа е низа на поврзани листа. Значи, повторно, до оваа точка на сортирање на користење на овие структури на податоци сега како состојки за да се повеќе интересни решенија, сте апсолутно може да потрае основните, како и низа, а потоа се земе нешто повеќе Интересно како се поврзани листа па дури и да ги комбинирате во уште повеќе интересни податоци структура. И навистина, тоа исто така би да се нарекува hash табелата, при што низата е навистина хаш табелата, но дека хаш табелата има синџири, би се рекло, кои може да расте или се намалува врз основа на број на елементи што сакате да го внесете. 

Сега, според тоа, она што е трчање време сега? Ако сакам да вметнете некој чиј роденден е 31 октомври, каде што го прави тој или таа оди? Добре. На самото дно каде што вели 31. И кој е совршен. Тоа беше константно време. Но, што ако најдеме некој друг чиј роденден е, ајде да видиме, Октомври, Ноември, Декември 31? Каде е тој или таа се случува да се оди? Истото. Два чекора иако. Тоа е постојан, иако не е тоа? Добре. Во моментов тоа е. Но во општата случај, повеќе луѓе ќе се додаде, вероятностно, ние ќе за да добиете повеќе и повеќе судири. 

А ова е малку подобро, бидејќи технички сега ми синџири може да биде во најлош случај колку долго? Ако јас вметнете н луѓето во ова повеќе софистицирани податоци структура, н луѓе, во најлош случај тоа се случува да биде n. Зошто? 

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

Сега, ако има 31 дена во месецот, тоа значи дека мојата трчање време навистина е голем O на n над 31, што се чувствува подобро од линеарна. Но, она што беше една од нашите обврски за неколку недели назад секогаш кога станува збор за изразување трчање време на алгоритам? Само само погледнете на висока цел мандат. Нели? 31 е дефинитивно корисни. Но ова е сеуште голема O на n. Но една од темите на проблемот постави пет се случува да биде за да се се признае дека апсолутно, асимптотично, теоретски оваа структура на податоци не постои подобро отколку само еден масовен поврзана листа. И навистина, во краен случај, оваа хаш табелата може да се префрлат во тоа. 

Но, во реалниот свет, со нас луѓето дека сопствените Macs или компјутери или што и се работи реалниот свет софтвер на реалниот свет на податоци, кој алгоритам ви се случува да преферираш? На онаа што го крајот чекори или оној кој зема N поделено со 31 чекори да се најдат некои парче на податоци или да се погледне до некои информации? Мислам, апсолутно 31 марки разлика во реалниот свет. Тоа е 31 пати побрзо. И ние, луѓето се сигурно случува да го цениме тоа. 

Така сфаќаат дихотомијата таму помеѓу всушност зборуваме за нешта теоретски и асимптотично кои дефинитивно има вредност како што видовме, но во реалниот свет, ако се грижите за само правење человек среќен за основните податоци, вие многу добро може да сакате да ја прифатите на фактот дека, да, ова е линеарна, но тоа е 31 пати побрзо од линеарна може да биде. И уште подобро, ние не само што мора да направи нешто произволно како датум на раѓање, ние би можеле да поминат малку повеќе време и мудрост и мислам за она што може да направи, Даденото име на една личност, а можеби и нивниот датум на раѓање за да се комбинираат тие состојки за да дознаам нешто што е навистина повеќе подеднакво и помалку съдран, така да се каже од оваа слика моментално укажува дека може да биде. Како би можеле ние спроведување на оваа во код? Па, дозволете ми да предложи дека ние само позајмуваат некои синтакса ние сме користи неколку пати досега. И јас одам да се дефинираат еден јазол, кој повторно е генерички термин за само некои контејнер за некои податоци структура. Одам да се предложи низ се случува таму. Но, ние се случува да започнете преземањето оние обука тркала надвор сега. 

Нема повеќе CS50 библиотека навистина, освен ако не сакате за да го користите за вашиот конечниот Проектот, кој е во ред, но сега ние ќе треба да се повлечат завеса и велат дека тоа е само знак ѕвезда. Па зборот таму се случува да биде името на лицето во прашање. И сега имам врската тука за да следниот јазол така што овие претставуваат секоја од јазли во синџирот, потенцијално, на поврзани листа. 

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

Па еве, тогаш, е како да спроведување на хаш табелата дека спроведува посебна врзувањето. Сега можеме да направиме подобро? Сите права Обещах последен пат дека ние може да се постигне постојана време. И јас вид на ти дал константно време тука, но тогаш не рече навистина константно време, бидејќи тоа е уште зависни од вкупното број на елементи сте внесување во структурата на податоци. Но да претпоставиме дека ние го сторивме тоа. Дозволете ми да се вратиме на екранот овде. Дозволете ми исто така, проектот ова до тука, јасно екран, и да претпоставиме дека го направив тоа. Да претпоставиме дека јас сакав да го вметнете име Daven во во моите податоци структура. 

Па сакам да се вметне низ Daven во податоците структура. Што ако јас не го користат хаш табелата, но јас го користам нешто што е повеќе древовидная како семејство дрво, каде што имате некои корен на врвот, а потоа јазли и лисја кои одат надолу и нанадвор. Да претпоставиме дека тогаш, дека јас сакате да го вметнете Daven е во она што е во моментов празна листа. Одам да го направите следново: Јас сум случува да се создаде еден јазол во оваа фамилија дрво како структура на податоци, кој изгледа малку вака, од кои секоја правоаголници е, да речеме, за сега 26 елементи во неа. И секоја од клетките во оваа низа се случува да претставуваат писмо на писмото. 

Поточно, јас ќе одам да се третираат ова е A, тогаш B, тогаш C, а потоа D, ова овде. Така што ова се случува да се ефикасно претставуваат писмо Д. Но, за да вметнете сите Daven е името ми е потребно да се направи малку повеќе. Па јас сум првиот случува да хаш, така да се каже. Одам да се погледне на првата буква в Daven која е очигледно D, а јас ќе одам да се распределат еден јазол што изгледа како this-- голем правоаголник голема доволно за да ги собере целата азбука. 

Сега D е направено. Веднаш A. D-A-V-E-N е цел. Па сега она што јас ќе одам да направите е ова. Штом почнав Д известување нема покажувачот таму. Тоа е ѓубре вредности во моментот, или јас да ја иницијализирам на нула. Но, дозволете ми да продолжувам да одам со оваа идеја за изградба на дрво. Дозволете ми да се доделат уште еден од овие јазли, кој има 26 елементи во неа. 

И знаете што? Ако ова е само еден јазол во меморија, која I создадени со Примерок, со користење на структура како што наскоро ќе видиме, Одам да се направи this-- Одам да се подготви стрела нешто што претставена Д надолу на оваа нова јазол. И сега, прв од следниот писмо во име Daven е, V-- Д--V-- Одам да се оди напред и да подготви друг јазол како овој, при што, на V елементи тука, што ние ќе се подготви за instance-- Опа. Ние не ќе ги привлече таму. Тоа се случува да одат овде. 

Тогаш ние ќе треба да сметаат дека тоа е В. А потоа надолу тука ние ќе да индекс надолу од V во она што ние ќе се разгледа Е. А потоа од тука ние ќе го одат еден од овие јазли тука. И сега имаме едно прашање да се одговори. Ми треба некако да се покаже дека ние сме на крајот од стрингот Daven. Па јас само би можеле да го оставите нула. 

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

Значи она што може да направи наместо да е лекување на секој од овие елементи како можеби кој има две елементи во внатрешноста на нив. Еден е покажувач, всушност, како што јас го работам. Па секоја од овие кутии не е само една клетка. Но, што ако на врвот одно-- дното нечиј ќе биде нула, бидејќи не постои Davenport само уште. Што ако на врвот еден е некои посебни вредност? И тоа се случува да биде малку тешко да се оваа големина се подготви. Но претпоставувам дека тоа е само знак за проверка. Провери. D-A-V-E-N е низа во оваа структура на податоци. 

Во меѓувреме, ако имав повеќе простор тука, јас не можеше да стори П-О-Р-Т, и јас би можеле да се стави проверка во јазол кој има букви T на самиот крај. Па ова е масовно комплекс изглед податоци структура. И мојот ракопис сигурно не помага. Но, ако сакав да се вметне нешто друго, сметаат дека она што ние би го направил. Ако сакаме да се стави Давид, ние би следат истата логика, Д--V, но сега јас ќе се истакне во следниот елемент не од E, но од I до D. Па таму се случува да биде повеќе јазли во ова дрво. Ние се случува да имаат разговор Примерок повеќе. Но, јас не сакам да се направи комплетен хаос на оваа слика. Па ајде наместо да се погледне во едно тоа е се предформулиран вака со не точка, точка, точки, но само со кратенка низи. Но, секоја од јазли во ова дрво тука го претставува истиот thing-- низа Ray на големина 26. 

Или, ако сакаме да бидеме навистина соодветна сега, она што ако нечие име како апостроф, ајде да претпостави дека секој јазол всушност има како 27 индекси во него, а не само 26. Па ова сега ќе биде на податоци структура наречена trie-- T-R-I-E. Trie, која е наводно историски умен име за дрво дека е оптимизиран за пребарување, што се разбира, е напишано со I-Е па тоа е Trie. Но, тоа е историја на Trie. 

Па еден Trie е ова дрво-like податоци структура како семејно стебло дека во крајна линија се однесува како тоа. И тука е само уште еден пример на куп на имињата на другите луѓе. Но, прашањето сега при рака е она што имаат ние стекнато преку воведување веројатно повеќе сложен податоци структура, и еден, искрено, дека го користи многу меморија. 

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

Реално, никој нема бескрајно долго име, што би се рекло, на должината на име или должината на стрингот ние би можеле да имаат одредени состојбата на структура е веројатно она што? Тоа е константна. Нели? Тоа би можело да биде голем постојана како 40-нешто, но тоа е константа. И тоа нема никаква зависност од тоа колку други имиња се во оваа податочна структура. Со други зборови, ако I сакав да сега вметнете Колтон или Габриел или Роб или Zamyla или Alison или Белинда или било која друга називи од редот на вработените во овие податоци структура, е трчање време на вметнување други имиња нема да биде во сите под влијание од колку други елементи се во податоците структура веќе? Тоа не е. Нели? Бидејќи сме ефикасно користење овој мулти-слој hash табелата. И трчање време на било која од овие операции е зависна не од бројот на елементи кои се наоѓаат во податоците структура или кои се на крајот ќе за да биде во податоците структура, но од должината на што конкретно? 

Низ се вметнати, кој прави ова асимптотично постојана time-- голема O на еден. И искрено, само во реалниот свет, ова значи вметнување на името Daven зема како пет чекори, или Девенпорт девет чекори, или David пет чекори. Тоа е прилично ебам мали трчање пати. И, навистина, тоа е многу добра работа, особено кога тоа не е зависен од вкупното број на елементи во таму. Па како да се спроведе овој вид на структура во код? Тоа е малку повеќе комплекс, но сепак тоа е само примена на основните градежни блокови. Одам да се редефинира ни јазол како што следува: bool наречен word-- и ова може да се нарече ништо. Но bool претставува она што го изведов како знак за проверка. Да. Ова е крајот на низа во оваа структура на податоци. 

И, се разбира, на јазол звезда таму е се однесува на деца. И, навистина, само се допаѓа семејно стебло, ќе ја разгледа јазли кои се виси на дното на некои родител елемент да бидат деца. И така децата ќе се да се низа на 27, на 27-едно само да биде за апостроф. Ние си оди за да се најде решение на посебен случај тоа. Па можете да имате одредени имињата со апострофи. Можеби дури и цртичка треба одат во таму, но ќе види во п сет 5 ние само грижа за писма и апострофи. 

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

Сега Meanwhile-- О, прашање. 

ПУБЛИКАТА: Што е bool збор? 

DAVID Маланом: bool збор е само оваа C инкарнација на она што јас го опиша во ова поле тука, кога Почнав со расцепувањето на секој од елементи во две парчиња низа е. Еден е покажувач кон следниот јазол. На други треба да биде нешто како наога да се каже да, има Зборот Daven која завршува тука, затоа што не сакаме, во моментот, Дејв. 

И покрај тоа што Dave се случува да биде легитимни збор, тој не е во Trie уште. И D не е збор. И Г-не е збор или име. Така штиклирање укажува само еднаш сте погоди овој јазол е претходниот пат на карактери всушност низ кои сте поставена. Значи тоа е сите bool таму се прави за нас. 

Било какви други прашања на обиди? Да. 

ПУБЛИКАТА: Што е преклопување? Што ако имате Дејв и Daven? DAVID Маланом: Совршена. Што ако имате Дејв и Daven? Значи, ако ние се вметне, велат прекар, за David-- Dave-- D-A-V-E? Ова е всушност супер едноставен. Па ние сме само ќе ги преземе четирите чекори. D-A-V-E. И она што морам да направи еднаш ја удирам дека четвртата јазол? Само случува да се провери. Ние сме веќе добро да отидевме. Направи. Четири чекори. Константно време асимптотично. И сега ние сме посочи дека двете Дејв и Daven се стрингови во структурата. Па не е проблем. И ќе забележите како присуство на Daven не го направи земе повеќе време или помалку време за Дејв и обратно. 

Па што друго можеме сега направам? Ние сме се користи оваа метафора пред на пепелниците ги претставуваат нешто. Но излегува дека магацинот на пепелниците е, всушност, демонстративен на друга апстрактни податоци type-- повисоко ниво на податочна структура дека на крајот на денот е само како низа или поврзано листа или нешто повеќе светски. Но, тоа е повеќе интересно концептуална концепт. Магацинот, како овие Табли тука во Mather, обично се нарекува само that-- оџак. 

И во овој тип на податоци структура имате две операции- имате еден вика притисок за додавање на нешто до магацинот, како ставање друга тава назад на врвот на магацинот. А потоа поп, кој ви значи земе врвниот тава надвор. Но, она што е клучот за стек е дека тоа е се здобија овој љубопитни карактеристика. Како јадење салата персонал преуредување на коцки за следниот оброк, она што се случува да биде точно за тоа како студентите во интеракција со оваа структура на податоци? ПУБЛИКАТА: Тие се случува да pop еднократна. DAVID Маланом: Тие се случува да се поп еднократна, се надевам на врвот. Инаку тоа е само вид на глупави да одат по целиот пат до дното. Нели? Структура на податоци всушност не се овозможи можете да го дофати дното табла најмалку лесно. Па таму е овој љубопитен имот на оџакот дека последната точка во е случува да биде првиот надвор. И компјутерски научници се јавите оваа LIFO-- да трае во, прв надвор. А тоа всушност мора интересни апликации. Тоа не е нужно толку очигледни како што некои другите, но тоа може да се, всушност, да биде корисен, и тоа може, всушност, да се спроведува во неколку различни начини. 

Значи еден, а всушност, нека мене не да се нурне во тоа. Ајде да го направите ова, наместо. Ајде да погледнеме во еден кој е речиси истата идеја, но тоа е малку пофер. Нели? Ако сте еден од овие фан момчиња или девојки кои навистина сака Apple производи и ви се разбудив во 03:00 да се редат на некои продавница за да го добиете најновите iPhone, би можело да чекаат на ред се допаѓа ова. 

Сега ред е многу намерно име. Тоа е линија поради тоа што има некои правичноста на него. Нели? Тој вид на ќе вовлечени ако сте стигнавме таму прв на Apple продавница но вие сте ефикасно долното тава, бидејќи вработените Епл потоа поп последниот човек кој всушност доби по ред. Па купчињата и редици, иако функционално тие се вид на same-- тоа е само оваа збирка на ресурси кои е ќе расте и shrink-- има оваа праведност аспект на тоа, барем во реалниот свет, каде операции ќе се вежба се фундаментално различни. Stack-- опашка rather-- се вели дека имаат две операции: n опашка и г опашка. Или можете да ги нарекуваат било кој број на нештата. Но само сакате да го фати поимот дека еден е додавање и едно е во крајна линија со одземање. 

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

ПУБЛИКАТА: опашка. DAVID Маланом: Па, на опашката. Сигурен. Што друго? 

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

DAVID Маланом: поврзани листа можете да ги спроведе. И поврзана листа е убаво затоа што тогаш тоа може да расте произволно долго како што се противат да има некои фиксен број на луѓе во продавницата. Но, можеби и фиксен број на места е легитимна. Бидејќи ако тие имаат само како 20 iPhone-на првиот ден, можеби тие треба само низа од големината 20 до претставуваат дека на дното, која е само да се каже сега еднаш ние да почнам да зборувам за овие повисоко ниво проблеми, можете да го имплементира во било кој број на начини. И таму е веројатно само ќе се да се исклучи трговија во просторот и времето или само во свој код комплексност. 

Она што за оџакот? Па, говедо, видовме премногу само би можеле да бидат овие коцки. И можете да ја имплементираат оваа низа. Но во некоја точка, ако имате потреба при користење низа, што ќе се случи со тави сте се обидува да се спушти? Добре. Ти си само ќе да можат да одат толку висока. И мислам дека во Mather тие се всушност вдлабнати со тоа, што отворот. Па навистина, тоа е речиси како Mather е со користење на низа на фиксна големина, зашто можеш само одговара на толку многу пепелниците со тоа, што се отвора во ѕидот долу колена луѓето. И, така што може да биде вели дека е низа, но ние сигурно би можеле да спроведат дека поопшто со поврзана листа. 

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

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

Но она што е навистина уредни за овој исто така, само за да ви закачам со малку код, потсетиме рекурзијата од некое време назад, при што ти пишувам функција која се нарекува себеси. Ова е прекрасна можност за спроведување на нешто како рекурзија, бидејќи сметаат дека ова. 

Оваа е дрво. И јас сум бил малку анален со тоа како Го ставам на цели броеви на улица. Толку многу што тој има посебен name-- бинарни пребарување дрво. Сега сме слушнале од бинарни пребарување, но може да ви работат наназад од името оваа работа е? Што е шемата за тоа како I вметнале цели броеви во ова дрво? Тоа не е произволно. Там-то шема. Да. 

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

DAVID Маланом: Да. Помалите се на левата страна. Поголемите на прав. Таква што вистински изјава е родител е поголема од неговата лева дете, но помалку од неговите право дете. И само тоа е дури и рекурзивен вербална дефиниција бидејќи можете да го применат тоа истата логика на секој јазол и тоа само долен дел надвор, база случај ако ќе, кога ќе удри еден од листа, така да се каже, каде што еден отсуство нема деца понатаму. 

Сега како може да ви се најде бројот 44? Ќе започне во коренот и да кажам, хм. 55 не е 44 И така, да сакам да одам право или не сакам да оди лево? Па, очигледно сакате да одите лево. И така тоа е само како телефон книга пример во бинарна пребарување генерално. Но, ние сме нејзиното спроведување сега малку повеќе динамички од низа може да им овозможи на. И всушност, ако сакате да се погледне на кодот, на прв поглед сигурно. Тоа изгледа како куп линии. Но, тоа е убаво едноставна. Ако сакате да се имплементираат функција наречен пребарување чија цел во животот е да пребарување за вредност како n, цел број, а ти си поминале во еден pointer-- покажувач на јазол на корените, поточно, на тоа дрво, од кои можете да пристапите сè друго, се забележи како на вистината може да се спроведе логика. Ако дрвото е нула, Очигледно, тоа не е таму. Ајде само return false. Нели? Ако го предаде ништо, таму нема ништо. 

Друго, ако n е помал од дрво стрелка N-- сега стрелка н, потсетиме воведовме супер кратко пред некој ден, и тоа само значи de-референца покажувач и се погледне на областа наречена н. Па тоа значи одиме таму и погледнете во областа наречена н. Значи, ако н, вредноста сте дадено, е помалку од вредноста на дрво integer, Каде сакаш да одиме? Вляво. 

Така забележите рекурзијата. Јас сум returning-- не е точно. Не е неточно. Јас сум се враќа без оглед на одговорот е од повик за себе, минувајќи n пак, кој е вишок, но она што е малку различни сега? Како јас што го прави проблемот помали? Јас кој поминува во како втор аргумент, а не на коренот на дрвото, но на левата дете во овој случај. Па јас сум поминува во левата дете. 

Во меѓувреме, ако n е поголема од јазол Јас сум во моментов во потрага по, Јас пребарување на десната страна. Друго, ако на дрвото не е нула, и ако елементот не е од лево и тоа не е на правото, она што е прекрасно случај? Ние сме всушност се најде јазол во прашање, и така ние се врати вистина. 

Па ние само изгребани на површината сега некои од овие структури на податоци. Во проблем постави пет испишан истражуваат овие уште понатаму, и ќе ви биде дадена вашиот дизајн избор за тоа како да се обратите за ова. Што би сакал да се заклучи на е само 30 секунди закачка на она што го чека следната недела и пошироко. 

Како што ние begin-- за среќа можеби ќе think-- нашата транзиција бавно од светот на C и долните имплементација ниво детали, до свет во кој можеме да ги преземат за готово дека некој друг има конечно спроведува овие податоци структури за нас, и ние ќе почнеме да го разбираме реалниот свет средства за спроведување на web-базирани на програми и интернет на генерално и, исто така, многу сигурност импликации дека ние сме само почна да гребење на површината на. Овде е она што не чека во деновите што доаѓаат. 

[Видео репродукција] 

-Той Дојде со порака, со записник сите свои. Тој дојде во светот на суров firewalls, незасегнатата рутери, и опасностите далеку полошо од смртта. Тој е брз. Тој е силен. Тој е TCP / IP, и тој доби вашата адреса. "Воини на мрежата." [END видео репродукција] DAVID Маланом: следната недела пришествие. Ние ќе се видиме тогаш. [Видео репродукција] -И Сега, "длабоки мисли" од Daven Фарнхам. -Дэвид Секогаш започнува предавања со, "Сите во право." Зошто да не, "Еве решение на оваа недела проблем во собата " или "Ние даваме на сите вас?" [Се смее] [END видео репродукција]