ЗВУЧНИК 1: Сите во право, па ние сме назад. Добредојдовте на CS50. Ова е крај на недела седум. Па се потсетиме дека минатиот пат, почнавме во потрага на нешто пософистицирано структури на податоци. Бидејќи до сега, сите ние имавме навистина на располагање беше ова, низа. Но, пред да ги отфрлите низа како не сето тоа интересно, кој навистина тоа всушност е, она што се некои од предности на овој едноставен податоци структура досега? Што е тоа добар во? Досега како што видовме? Што имаш? Ништо. СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Што е тоа? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: фиксна големина. Добро, па зошто е фиксна големина добри иако? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Добро, така што е ефикасен во смисла на тоа дека може да се одвои фиксен износ на просторот, кои се надевам е токму колку простор, како сакате. Така што би можело да биде апсолутно плус. Што е уште една до страна на низа? Да? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Сите - Жал ми е? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Сите кутии во меморијата или до друг. И тоа е корисно - зошто? Тоа е сосема точно. Но, како може да се искористат дека вистината? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Точно, ние може да ги пратите на каде што сè е само со знаејќи една адреса, односно адресата на првиот бајт од таа парче на меморија. Или во случај на стрингот, на адресата на првиот знак во таа низа. И од таму, може да се најде на крајот од стрингот. Ние може да се најдат на вториот елемент, Третиот елемент, и така натаму. И така фенси начин на опишување на кој карактеристика е тоа што низи ни даде случаен пристап. Само со помош на плоштадот заградата нотација и број, можете да скокнете до специфичен елемент во низата во постојана време, големо O на еден, така да се каже. Но има некои недостатоци. Она што не низа направите многу лесно? Она што не е добро во? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Што е тоа? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Проширување во големина. Па downsides на низа се токму спротивното од она што квит сме. Па една од downsides е дека тоа е фиксна големина. Па ти навистина не може да расте. Можете да го пренамени поголем парче на меморија, а потоа се пресели на старите елементи во новата низа. А потоа бесплатно стариот низа, за пример, со користење Примерок или слична функција наречена realloc, која reallocates меморија. Realloc, како настрана, се обидува да ви даде меморија, која е веднаш до низа кои веќе ги имаш. Но тоа би можело да се движат работите околу заедно. Но, во краток, тоа е скапо, нели? Затоа што ако имате парче од меморијата на оваа големина, но навистина сакам една на оваа големина, и сакате да се зачува оригинални елементи, имате приближно една линеарна време процес на копирање што треба да се случи од стари низа на нови. И реалноста бара од оперативниот систем повторно и повторно и повторно за големи парчиња на меморија може да започне да ве чини извесно време како добро. Така, тоа е и благослов и проклетство во маскира, фактот дека овие низи се на фиксна големина. Но, ако ние се воведе наместо нешто вака, кој се нарекува поврзано листа, ќе го добиеме неколку квит и неколку downsides и тука. Па поврзана листа е едноставно податоци структура составена од Ц structs во овој случај, каде што структурата, се потсетиме, е само сад за една или повеќе специфични типови на променливи. Во овој случај, она што го стори типови на податоци се чини дека се во внатрешноста на struct дека Последниот пат што се нарекува еден јазол? Секој од овие правоаголници е еден јазол. И секоја од помали правоаголници во него е тип на податок. Какви видови Дали ние велиме тие беа во понеделник? Да? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: А променлива и покажувач, или поконкретно, со int, за n, и покажувач на дното. И на оние кои се случи да биде 32 бита, во најмалку на компјутер вака CS50 Апаратот, и така тие се подготвени подеднакво во големина. Па што се со користење на покажувачот иако за очигледно? Зошто го додадете ова стрелката сега кога низи беа па убаво и чисто и едноставно? Она што е на покажувачот прави за ни во секоја од овие јазли? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Токму така. Тоа е ти го кажувам каде На следната е. Па јас вид на користат аналогијата на користење на конец за сортирање на нишка овие јазли заедно. И тоа е токму она што го правиме со совети бидејќи секоја од овие делови од меморијата може или не може да биде соседни, назад да се врати да се врати во внатрешноста на RAM меморија, затоа што секој пат кога ќе јавете Примерок велејќи ми даде доволно бајти за нов јазол, тоа би можело да биде тука или тоа би можело да биде тука. Тоа би можело да биде тука. Тоа би можело да биде тука. Вие само не знам. Но со користење на покажувачи во адресите на оние јазли, може да бод нив заедно во начинот на кој изгледа визуелно како листа, дури и ако овие нешта се сите се шират во текот на вашата една или твоите два или вашиот четири гигабајти на RAM меморија во внатрешноста на вашиот сопствен компјутер. Значи во надолна линија, а потоа, на поврзана листа е она? Што е цена ние сме очигледно плаќаат? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Повеќе простор, нели? Ние сме, во овој случај, двојно се зголеми износот на просторот, бидејќи ние си отиде од 32 бита за секој јазол, за секоја int, па сега 64 бита, бидејќи ние треба да се задржи околу покажувач, како и. Можете да добиете повеќе ефикасност ако вашиот struct е поголема од ова едноставна работа. Ако навистина имаат еден студент во внатрешноста од кои е неколку стрингови за име и куќата, можеби ID број, можеби и некои други области заедно. Значи, ако имате доволно голема struct, тогаш можеби цената на покажувачот е не толку голем договор. Ова е малку агол случај во кој ние сме чување на таква едноставна примитивна внатрешноста на поврзана листа. Но поентата е иста. Ти си дефинитивно трошат повеќе меморија, но ти си добивање флексибилност. Бидејќи сега ако сакам да додадете елемент на почетокот на оваа листа, Морам да додели нов јазол. И морам да едноставно ажурирање оние стрели некако со само движат некои совети околу. Ако сакам да внесете нешто во средината од листата, јас не треба да се притисни секој настрана како што правевме во недели минатото со нашите волонтери кои претставен низа. Јас само може да одвои нов јазол и тогаш само точка на стрелки различни правци, бидејќи тоа не мора да остане во вистински меморија вистинска линија како јас сум подготвен тоа тука на екранот. А потоа на крај, ако сакате да вметнете нешто на крајот на листата, тоа е дури и полесно. Ова е вид на произволно нотација, но 34 е покажувач, ги погоди. Која е вредноста на покажувачот повеќето најверојатно привлечени вид на како старо училиште антена таму? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Тоа е веројатно нула. И навистина, токму тоа е една авторот застапеност на нула. И тоа е нула, бидејќи сте апсолутно треба да знаеш каде на крајот од поврзани Листата е, за да не се задржи следење и следење и следејќи ги овие стрели на некои ѓубре вредност. Така ништовни ќе значи дека нема повеќе лимфни јазли на правото на број 34, во овој случај. Па ние предлагаме дека ние може да се спроведе овој јазол во кодот. И видовме овој вид на синтаксата порано. Typedef само дефинира нов тип за нас, ни дава синоним како низа беше за char *. Во овој случај, тоа се случува да ни даде стенографија нотација, така што struct јазол може наместо само да се запише како јазол, што е многу почист. Тоа е многу помалку опширниот. Во внатрешноста на еден јазол е очигледно со int наречен n, а потоа struct јазол * што значи токму она што сакавме стрелките да значи, покажувач на друг јазол на исти тип на податок. И јас предложи дека би можеле да се имплементира функцијата за пребарување, како таков, кој во прв поглед може да изгледа малку комплекс. Но, да видиме тоа во контекст. Дозволете ми да одам во текот на апаратот тука. Дозволете ми да се отвори фајл наречен листа нулта точка ж. И што содржи само дефиницијата ние само видов пред еден миг за овој податоци тип се нарекува јазол. Па ние сме се стави дека во точка ж датотека. И како настрана, иако ова програма со која сте во врска да се види е не сето она што сложена, тоа е навистина конвенцијата кога пишувате програма за стави работите како типови на податоци, да се повлече константи, понекогаш, во внатрешноста на вашиот хедер датотека и не мора во вашиот C датотека, секако, кога вашиот програми се поголеми и поголеми, така што знаеш каде да се погледне и за документација во некои случаи, или за основите како ова, дефиниција на некој вид. Ако јас сега се отвори листа нулта точка в, забележите неколку работи. Тоа вклучува неколку насловот датотеки, повеќето од кои што сум го видел досега. Тоа вклучува свој хедер датотека. И како настрана, зошто тоа е двојно цитати тука, за разлика од агол загради на линија дека Сум Нагласени таму? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Да па тоа е локална датотека. Па ако е локална датотека на вашиот сопствен овде на линија 15, на пример, можете да користите на двојни наводници, наместо на аголни голема заграда. Сега ова е вид на интересни. Забележите дека сум прогласен за глобален променлива во оваа програма on-line 18 наречен прво, идејата е ова е ќе биде покажувач на првата јазол во мојот поврзаните листа, и јас сум иницијализира до нула, бидејќи јас сум не распределени било вистински јазли само уште. Па ова претставува, сликовито, она што ние видов пред еден миг на сликата како дека покажувачот на далеку левата страна. Па токму сега, дека покажувачот не мора стрела. Наместо тоа е само нула. Но тоа претставува она што ќе биде адресата на првиот вистински јазол во оваа листа. Па јас спроведува тоа е глобален бидејќи, како што ќе видиме, сето ова програма се во животот е спроведување на поврзана листа за мене. Сега имам неколку прототипови тука. Решив да се имплементираат карактеристики како бришење, вметнување, пребарување, и traversal - последните само да биде прошетка низ листа, печатење нејзините елементи. И сега тука е мојата главна рутина. И ние не ќе потроши премногу време за овие, бидејќи ова е вид на, се надевам стара шапка до сега. Одам да го направите следново, додека на корисникот соработува. Така што едно, јас ќе одам да се печати надвор ова мени. И јас сум форматирана тоа како демонтирани што можев. Ако корисникот видови во еден, тоа значи дека тие сакаат да избришете нешто. Ако корисникот видови во два, тоа значи дека тие сакаат да вметнете нешто. И така натаму. Одам да потоа го натера тогаш за некоја команда. А потоа јас ќе одам да се користи GetInt. Значи ова е навистина едноставно menuing интерфејс каде што едноставно мора да напишеш голем број мапирање на една на оние команди. И сега имам убав чист прекинувач изјава дека се случува да се префрлат на без оглед на корисник внесе внатре И ако тие ја внеле еден, јас ќе јавете се брише и се скрши. Ако тие ја внеле две, јас ќе јавете се вметне и се скрши. И сега забележиш јас сум се стави секој од овие на истата линија. Ова е само стилска решение. Обично ние сме виделе нешто вака. Но јас само одлучи, искрено, мојата програма изгледаше повеќе може да се чита затоа што тоа беше само во четири случаи на само да го наведете како оваа. Целосно легитимна употреба на стил. И јас одам да го направите ова се додека корисникот не внеле нула, за што јас одлучи ќе значи дека тие сакаат да се откажам. Па сега се забележи она што сум случува да го направите тука. Одам да се ослободи листата очигледно. Но повеќе за тоа во само еден миг. Ајде прво да ја извршите оваа програма. Па да ми направи поголема терминал прозорецот, точка црта листа 0. Одам да се оди напред и да ја вметнете на пишување два, голем број како 50, а сега ќе видите листа е сега 50. И мојот текст само scrolled се малку. Па сега забележите листата содржи бројот 50. Ајде да направиме уште вметнете со преземање на две. Ајде да внесете го бројот како еден. Листа сега е еден, проследено со 50. Па ова е само текстуална претстава на листата. И ајде да се вметне уште еден број како бројот 42, кој е се надевам дека случува да се заокружи во средината, бидејќи оваа програма во особено видови се елементи како што им инсерти. Па така ние го имаат. Супер едноставна програма со која може да апсолутно се користи низа, но јас се случи да биде со користење на поврзаните листа само така можам динамично расте и да се намали тоа. Па ајде да ги разгледаме за пребарување, ако јас стартува командата три, сакам да се бараат за, да речеме, бројот 43. И ништо не беше очигледно најде, затоа што влегов нема одговор. Па ајде да го направите ова повторно. Пребарување. Ајде да пребарување за 50, или подобро кажано пребарување 42, која има убав малку суптилни значење. И го најдов смислата на животот таму. Број 42, ако не знаеш на референца, го Google. Сите во право. Значи она што оваа програма направи за мене? Тоа е само ми дозволи да го вметнете на тој начин далеку и потрага по елементи. Ајде да брзо напред, а потоа, да се таа функција ние погледна во понеделникот, како закачка. Па оваа функција, тврдам, бара елемент во листата со првиот еден, се прашува корисникот, а потоа повик GetInt да се добие вистински int што сакате да го барате. Тогаш забележите ова. Одам да се создаде привремена променлива во согласност 188 нарече покажувачот - Кон меморија - би можеле да го нарекуваат ништо. И тоа е покажувач кон јазол затоа реков јазол * таму. И јас сум иницијализацијата тоа да биде еднаков на првиот, така што јас ефикасно имам прст, така да се каже, на самиот Првиот елемент на листата. Значи, ако мојата десна рака тука е кон меморија Јас сум покажувајќи кон истото што прв е насочена кон. Па сега повторно е во кодот, она што се случува следно - ова е заеднички парадигма кога процесирањето во текот на структура како поврзана листа. Одам да го направите следново додека покажувачот не е еднаква на нула Така, додека мојот прст не е насочена кон некои нула вредност, ако покажувачот стрелката n еднаква на n. Ние ќе забележите првиот што n е она што корисникот внесе во за GetInts нарекуваат тука. И покажувачот стрелката n значи што? И ако ние се вратиме на слика тука, ако имам прстот покажувајќи на дека првиот јазол кој содржи девет, стрелка суштина значи одат на таа јазол и го имате на вредноста на локација n, во овој случај, податоците областа наречена n. Како настрана - и видовме ова неколку на недели кога некој праша - оваа синтакса е нова, но тоа не го прави ни даде сили кои ние не веќе имаат. Она што беше оваа фраза еквивалентно на користење точка нотација и ѕвезда на неколку на недели кога ние излупени назад овој слој е малку прерано? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Точно, тоа беше ѕвезда, и тогаш тоа беше ѕвезда точка n, со загради тука, што изгледа, искрено, мислам дека многу повеќе криптичната да ја прочитате. Но ѕвезда покажувач, како и секогаш, средства одат таму. И еднаш сте таму, она што на податоци поле сакаш да пристапите? Па имате потреба при користење на dot нотација за пристап на structs податочното поле, и јас конкретно сакаш n. Искрено, јас би рекол ова е само потешко да се прочита. Тоа е потешко да се сети каде се заградите одат, ѕвезда и сето тоа. Така што светот усвоени некои синтаксички шеќер, така да се каже. Само секси начин да се каже, ова е еквивалент, и можеби и повеќе интуитивна. Ако покажувачот е навистина покажувач, стрелка нотација средства одат таму и да се најде на полето, во овој случај се нарекува n. Значи, ако јас го најдете, забележи она што го правам. Јас едноставно испечатите, го најдов проценти i, приклучување на вредност за кои Инт. Јас го нарекувам спие за една секунда само да се вид на пауза работи на екранот за да им даде на корисник една секунда за да се апсорбираат што едноставно се случи. И тогаш јас се скрши. Инаку, она што можам да направам? Јас обновете го покажувачот на еднаков покажувачот стрелката. Па само да биде јасно, ова значи одат таму, со користење на мојот старата школа нотација. Значи ова само значи да се оди на она што сте покажувајќи кон, кои во многу Првиот случај е јас сум покажувајќи кон на struct со девет во неа. Па јас сум качил таму. А потоа на dot нотација значи, добие на вредност на следниот. Но вредноста, иако тоа е составен како тесни, е само број. Тоа е нумерички адреса. Значи ова една линија код, без разлика дали напишана вака, толку повеќе криптичната начин, или вака, малку повеќе интуитивен начин, само значи се движат мојата рака од првиот јазол на следниот, и потоа на следниот една, а потоа следниот, и така натаму. Па ние не ќе живеат на други имплементации на вметнување и бришење на и traversal, првите две од кои се прилично кои се вклучени. И мислам дека тоа е сосема лесно да се добие изгубени кога го прави тоа вербално. Но, она што можеме да направиме тука е обидете се да се утврди како најдобро е да го направите тоа визуелно. Затоа што јас би им предложил дека ако ние сакате да го вметнете елементи во оваа постоечка листа, која има пет елементи - 9, 17, 22, 26, и 33 - ако јас се случува да се спроведе тоа во кодот, јас треба да се разгледа како да се обратите во врска со тоа. И јас би им предложил преземање на бебето чекори при што, во овој случај мислам, она што се можните сценарија кои ние да се судрите во воопшто? При спроведувањето на вметнете за поврзани листа, тоа само се случува да биде конкретен пример на големината пет. Па ако сакате да внесете број, како велат број еден, и одржување подредени цел, каде очигледно прави број еден треба да одат во овој конкретен пример? Како на почетокот. Но она што е интересно таму е дека ако сакате да вметнувате во овој листа, она што посебно покажувачот треба да се ажурираат очигледно? Во прв план. Па јас би рекол, ова е прв случај дека ние можеби ќе сакате да се разгледа, а сценарио вклучува вметнување на на почетокот на листата. Ајде да извади надвор можеби еден толку лесно, па дури и полесно случај, условно кажано. Да претпоставиме дека сакам да го вметнете број 35 во подредени цел. Тоа очигледно припаѓа таму. Па што покажувачот очигледно се случува да се треба да биде надграден во тоа сценарио? 34 е покажувачот станува не нула но на адреса на struct содржи бројот 35. Значи тоа е случај две. Тоа веќе, јас сум вид на quantizing колку работа имам да го направите тука. И конечно, очигледно средината случај е навистина, во средината, ако сакам да внесете нешто како 23 да речеме, што оди помеѓу 23 и 26, но сега нештата се малку повеќе вклучени затоа што она што совети треба да се менува? Па 22 очигледно треба да се промени затоа што тој не може да се укаже на 26 веќе. Тој треба да се укаже на нов јазол дека Јас ќе мора да одвои со повик Примерок или некој еквивалент. Но, тогаш јас, исто така, треба дека новиот јазол, 23 во овој случај, да има покажувач покажувајќи кон кого? 26. И таму се случува да биде редоследот на операциите тука. Затоа што ако го направам ова глупаво, и јас на пример старт на почетокот на листата, и мојата цел е да внесете 23. И јас се провери, дали тоа му припаѓаат тука, во близина девет? Бр. Дали тоа припаѓам овде, до 17? Бр. Дали тоа му припаѓа тука до 22? Да. Сега, ако јас сум глупаво тука, и не размислување ова преку, би можел да распредели мојот нов јазол за 23. Јас би можеле да ажурирање на покажувачот од јазол наречен 22, посочувајќи тоа во новиот јазол. И тогаш што имам да се ажурира покажувачот на новиот јазол да биде? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Токму така. Посочувајќи на 26. Но мајката ако јас не веќе обновете го Покажувач 22 да укаже на овој човек, и сега имам деца без родители, а остатокот на листата, така да се каже. Па редоследот на операциите овде се случува да биде важно. Да го направите тоа би можел да ги украде, да речеме, шест волонтери. И да видиме ако не можеме да го правиме ова визуелно, наместо на код-мудрец. И ние имаме некои убави стрес топки за вас денес. Добро, колку за еден, два, во назад - на крајот таму. три, четири, двете од вас момци на крајот. И пет, шест. Сигурно. Пет и шест. Сите во право, а ние ќе се да ви момци следниот пат. Добро, ајде нагоре. Сите во право, бидејќи вие сте тука прво, вие би сакале да биде еден чудно во Google Стакло тука? Добро, така, во ред, стакло, снимате видео. Добро, ти си добро да отидевме. Сите во право, па ако вие момци можат да дојдат преку овде, имам подготвени однапред некои броеви. Добро, ајде овде. И зошто не одиш малку понатаму на тој начин. И ајде да видиме, она што е вашето име, со Стакло Google? СТУДЕНТСКИ: Бен. ЗВУЧНИК 1: Бен? Во ред, Бен, ќе биде прв, буквално. Па ние ќе ви испратиме до крајот на сцената. Сите во право, и вашето име? СТУДЕНТСКИ: Џејсон. ЗВУЧНИК 1: Џејсон, ОК да ќе биде број девет. Значи, ако сакате да ги следите бен тој начин. СТУДЕНТСКИ: Џил. ЗВУЧНИК 1: Џил, си оди за да биде 17, кои ако би направиле ова повеќе интелигентно, ќе морам започна на другиот крај. Да одите тој пат. 22. И вие сте? СТУДЕНТСКИ: Марија. ЗВУЧНИК 1: Марија, ќе биде 22. И вашето име е? СТУДЕНТСКИ: Крис. ЗВУЧНИК 1: Крис, ќе биде 26. А потоа на крај. СТУДЕНТСКИ: Дијана. ЗВУЧНИК 1: Дијана, ќе биде 34. Така да дојдат на повеќе тука. Сите во право, толку совршен подредени нареди веќе. И ајде да одиме напред и да го направите тоа така што можеме да навистина - Бен ти си само вид на потрага надвор во никаде таму. ОК, па ајде да одиме напред и да го отслика ова користење на рацете, слично како бев она,, што се случува. Така одат напред и самите даваат нога или два помеѓу себе. И оди напред и да се укаже со една рака да кој и да треба да се укажува на врз основа на овој. И ако сте null само точка директно надолу кон подот. Добро, толку добро. Па сега имаме поврзана листа, и дозволете ми да предложи дека јас ќе ја играат улогата на Кон меморија, па јас нема да се мачат носат овој наоколу. А потоа - некој глупав конвенција - можете да се јавите ова нешто што сакате - претходник покажувач, pred покажувачот - тоа е само прекар дадовме во нашиот примерок кодот на мојата лева рака. Од друга страна дека ќе биде зачувана ги пратите на кој е кој во по сценарија. Па претпоставувам, прво, сакам да се извади надвор дека првиот пример на вметнување, велат 20, во листата. Па јас ќе одам да треба некој да отелотворуваат број 20 за нас. Значи ми треба да Примерок некој од публиката. Ајде горе. Што е вашето име? СТУДЕНТСКИ: Брајан. ЗВУЧНИК 1: Брајан, сите во право, така да ќе биде јазол кој содржи 20. Добро, ајде овде. И очигледно, каде се Брајан припаѓаат? Значи, во средината на - всушност, почекајте една минута. Го правиме ова на ред. Ние сме прави ова многу потешко отколку што треба да биде во прв план. Добро, ние ќе бесплатна Брајан и realloc Брајан како пет. Добро, па сега ние сакаме да го вметнете Брајан како пет. Па ајде овде до Бен за само еден миг. А вие веројатно може да се каже каде што оваа приказна се случува. Но, ајде да размислат за редоследот на операциите. И тоа е токму оваа визуелна што се случува да се редат со тоа примерок код. Па еве јас се кон меморија посочувајќи првично не на Бен, по себе, туку на она што цениме тој содржи, кој во овој случај е - што викаш повторно? СТУДЕНТСКИ: Џејсон. ЗВУЧНИК 1: Џејсон, па и двете Бен и јас се покажувајќи кон Џејсон во овој момент. Па сега јас треба да се утврди, каде што го прави Брајан припаѓаат? Па единственото нешто имам пристап до во моментов е негов n податоци елемент. Па ќе одам да се провери, е Брајан помалку од Џејсон? Одговорот е вистина. Значи она што сега треба да се случи, во правилен ред? Јас треба да се ажурира колку совети вкупно во оваа приказна? Каде што мојата рака се уште покажувајќи кон Џејсон, и вашата рака - ако сакате да стави својата рака како, на некој начин, јас не знам, знак прашалник. Добро, добро. Добро, па имате неколку кандидати. Или бен или јас или Брајан или Џејсон или секој друг, кој совети треба да се промени? Колку вкупно? ОК, значи два. Мојата покажувачот не е важно повеќе бидејќи јас сум само привремена. Така, тоа е овие две момчиња, веројатно, двете бен и Брајан. Значи, да ми предложи дека ние се ажурира Бен, бидејќи тој е во прв план. Првиот елемент на оваа листа сега ќе биде Брајан. Па бен точка на Брајан. Добро, сега што? Кој добива вперени во кого? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: OK, па Брајан има да се укаже на Џејсон. Но ми се губеше на таа покажувачот? Да знам каде Џејсон е? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Јас се направи, бидејќи јас сум привремената покажувач. И се претпоставува дека, јас не се променети да се укаже на нов јазол. Значи ние едноставно може да имаат Брајан точка на кој јас сум покажувајќи кон. И ние сме направиле. Така случај еден, вметнување на почнувајќи од листата. Имаше две клучни чекори. Еден, ние треба да се ажурира Бен, а потоа ние, исто така, мора да ги обноват Брајан. И тогаш јас не треба да се мачам traipsing низ остатокот на листа, бидејќи ние веќе се најде своето локација, бидејќи тој припаѓал на лево од првиот елемент. Сите во право, па прилично јасна. Всушност, се чувствува како ние сме речиси што ова е премногу комплицирано. Па ајде сега извади надвор од крајот на листата, и да видиме каде комплексноста започнува. Значи, ако сега, јас alloc од публиката. Секој сака да игра 55? Сите во право, ја видов твојата рака во прв план. Ајде горе. Да. Што е вашето име? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Habata. Добро, ајде нагоре. Вие ќе бидете во бројот 55. Така што, се разбира, му припаѓаат на крајот на листата. Па ајде да ги повторувате симулација со мене се кон меморија за само еден миг. Па јас сум прв ќе укаже на без оглед на Ben покажувајќи кон. Ние сме двете посочувајќи сега на Брајан. Па 55 не е помалку од пет. Па ќе одам да си се ажурира од страна на што укажува на следното покажувачот на Брајан, кој сега е, се разбира Џејсон. 55 не е помалку од девет, па Одам да се ажурира кон меморија. Одам да се ажурира кон меморија. Одам да се ажурира кон меморија Јас ќе се ажурира кон меморија. И јас ќе одам да - хм, она што е Вашето име повторно? СТУДЕНТСКИ: Дијана. ЗВУЧНИК 1: Дијана е да се покажува, се разбира, на нула со нејзината лева рака. Значи каде Habata всушност припаѓаат јасно? На левата страна, тука. Па како не знам да ја стави тука Мислам дека сум измамен. Затоа што она што е кон меморија уметност овој момент во времето? NULL. Па дури иако, визуелно, можеме да очигледно ги видиш сите од овие момци тука на сцената. Јас не сум водел сметка на претходната лице во списокот. Јас немам прст посочувајќи, во овој случај, на јазол број 34. Па ајде да всушност започнете овој завршена. Па сега јас всушност треба втор локална променлива. И тоа е она што ќе видите во вистински примерок C код, каде што како и да одам, кога ќе се ажурира мојата десна рака, за да укаже Џејсон, а со тоа оставајќи Брајан зад себе, јас подобро е да почнеме со користење мојата лева рака да ажурирање каде сум, така што кога одиш преку оваа листа - повеќе чудно отколку што се наменети сега тука визуелно - Одам да се дојде до крајот на листата. Оваа страна се уште е нула, што е прилично бескорисни, освен да се укаже Јас сум јасно на крајот на листата, но сега барем имам оваа претходник покажувачот посочувајќи тука, па сега што раце и она што совети треба да се ажурираат? Чија рака сакаш да ја ре првиот? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Добро, па Дијана. Каде сакате да укаже Левата страна на diana покажувачот во? На: 55, веројатно, така што ние сме вметнува таму. И каде што 55 покажувачот треба да одам? Надолу, што претставува нула. И моите раце, во овој момент, не важно, бидејќи тие беа само привремени променливи. Па сега ние сме направиле. Па на дополнителни комплексноста таму - и тоа не е толку тешко да се спроведе, но ние треба средно променлива да се направи сигурни дека пред да се движат моето право страна, јас обновете вредноста на мојата лева страна, pred покажувачот во овој случај, па дека имам заостанува покажувачот да ги пратите на тоа каде сум бил. Сега како настрана, ако си помислил на тоа преку, тоа се чувствува како тоа е малку досадно да мора да се задржи ги пратите на овој левата рака. Што би друго решение за овој проблем биле? Ако ли да редизајн на податоци структура зборуваме преку токму сега? Ако ова само вид на се чувствува малку досадни да имаат, како, два совети минува низ листата, кој друг би можел да се, во еден идеален свет, се одржува информации кои ни се потребни? Да? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Токму така. Право, па таму е всушност интересна микроб на една идеја. И оваа идеја на претходната покажувач, посочувајќи на претходните елемент. Што ако јас само отелотворени дека внатрешноста на листата по себе? И тоа се случува да биде тешко да се визуелизира тоа без сите хартија паѓа на подот. Но, да претпоставиме дека овие момци користи и на нивните раце да имаат претходно покажувач, и следната покажувач, а со тоа спроведување на она што ние ќе се јавите на двојно поврзана листа. Кои ќе ми дозволат да се најде на премотам касетата, многу повеќе лесно, без мене, програмер, да ги задржи ги пратите рачно - навистина рачно - на каде сум бил претходно во листата. Па ние нема да го стори тоа. Ќе го чувам едноставен, бидејќи тоа е ќе дојде со одредена цена, двапати многу простор за покажувачи, ако сакате втората. Но, тоа е навистина заеднички податочна структура позната како двојно поврзана листа. Ајде да го направите конечниот пример тука и го стави овие момци надвор од својата беда. Па Примерок 20. Ајде up од коридор таму. Сите во право, она што е вашето име? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Молам? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Demeron? Добро дојде на до. Вие ќе бидете во 20. Ти очигледно се случува да припаѓаат помеѓу 17 и 22. Така нека ме научи мојот лекција. Одам да се започне покажувачот покажувајќи кон Брајан. И јас одам да имаат мојата лева рака само надградба на Брајан како што јас се преселат во Џејсон, проверка прави 20 помалку од девет? Бр. Е 20 помалку од 17? Бр. Е 20 помалку од 22? Да. Па што совети или рацете треба да се промени каде што тие се покажувајќи сега? Така што можеме да направиме 17 посочувајќи на 20. Па тоа е добро. Каде што сакаме да укажеме го покажувачот сега? На 22. И знаеме каде 22 е, повторно благодарение на мојот привремено покажувач. Па ние сме во ред таму. Па поради тоа привремено чување Сум водел сметка каде што секој е. А сега можете визуелно да одат во, каде што ви припаѓаат, а сега ние треба 1, 2, 3, 4, 5, 6, 7, 8, 9 стрес топки, и аплауз за овие момци, кога би можеле. Убаво направено. [Аплауз] ЗВУЧНИК 1: Во ред. И може да се задржи на парчиња на хартија како спомени. Сите во право, па, верувајте ми тоа е многу полесно да поминувам низ тоа со луѓето отколку што е со реалните код. Но, она што ќе најдете во само еден миг сега, е дека истиот - ох, ви благодарам. Ви благодариме - е дека ќе најдете дека истите податоци структура, поврзана листа, може, всушност, да се користи како зграда блок на уште повеќе софистицирани структури на податоци. И да сфати премногу темата тука е дека ние сме апсолутно воведе повеќе комплексноста во спроведувањето на овој алгоритам. Вметнување, и ако отидовме низ него, бришење и пребарување, е малку покомплицирано од тоа беше со низа. Но, ние се здобијат со некои динамизам. Ние се добие адаптивни податоци структура. Но, повторно, ние ја плати цената на постоење на некои дополнителна комплексност, како во спроведување. И ние сме се откажале случаен пристап. И да бидам искрен, таму не е некои убави чистење слајд можам да ви даде дека вели тука е зошто поврзана листа е подобар од низа. И да ја оставите во тоа. Бидејќи темата reoccurring сега, дури и повеќе, па во следните неколку недели, е дека не е нужно точен одговор. Ова е причината зошто имаме посебна оска на дизајн за проблемот комплети. Тоа ќе биде многу контекст осетлива дали сакате да го користите овој податоци структура или оној, и тоа ќе зависи од она што е важно за вас во однос на ресурси и комплексност. Но, дозволете ми предложи дека идеален податоци структура, Светиот Грал, ќе биде нешто што е постојана време, без оглед на тоа колку материјал е во неа, не би било неверојатно ако податочна структура врати одговори во постојана време. Да. Овој збор е во вашата огромна речникот. Или не, овој збор не е. Или било кој таков проблем таму. Па ајде да видиме ако не можеме барем преземе чекор кон тоа. Дозволете ми да предложи нов податочна структура која може да се користи за различни нешта, во овој случај се нарекува хаш табелата. И така ние сме всушност назад кон обѕрне на низа, во овој случај, и нешто произволно, јас сум подготвен овој хаш табелата како низа со еден вид на две-димензионална низа - или подобро кажано, тоа е прикажан тука како две димензионална низа - но ова е само низа на големина 26, како што ако ние јавете се на низата маса, маса заградата нула е правоаголник на врвот. Табела заградата 25 е правоаголник на дното. И ова е како би можел да се повлече податоци структура во која сакам да ја запази на луѓето имиња. Така на пример, и јас не ќе ги привлече на целата работа тука на горе, ако јас имаа оваа низа, за што јас сум сега ќе да јавете се на хаш табелата, а тоа е повторно локација нула. Ова овде е локација еден, и така натаму. Тврдам дека сакам да го користите овој податоци структура, за доброто на дискусијата, за чување на луѓето имиња, Алис и Боб и Чарли и други такви имиња. Па мислам на ова сега како на почетоците на, да речеме, речник со многу зборови. Тие се случи да биде имиња во нашиот пример тука. И сево ова е премногу важен, можеби, да спроведување на Проверка на правопис, како што можеби за проблемот постави шест. Значи, ако имаме низа од вкупната големина 26 така што ова е 25-ти локација на дното, и тврдам дека Алис е првиот збор во речникот имиња што сакам да го вметнете во RAM меморија, во оваа податочна структура, каде што се инстинктите ти го кажувам дека на Alice Името треба да одат во оваа низа? Имаме 26 опции. Каде сакаме да ја стави? Ние ја сакате во заградата нула, нели? А за Алис, ајде да ги наречеме дека нула. И Б ќе биде еден, и C ќе биде два. Па ние ќе да се напише На alice име тука горе. Ако ние потоа вметнете Боб, неговиот името ќе одат овде. Чарли ќе одат овде. И така натаму надолу низ оваа податочна структура. Ова е прекрасен податочна структура. Зошто? Па она што е трчање време на вметнување на името на човекот е во оваа податочна структура во моментов? Со оглед дека оваа табела се спроведува, навистина, како низа. Добро, тоа е постојана време. Тоа е цел на еден. Зошто? И како да се утврди каде Алис му припаѓа? Ќе се погледне кои буква од нејзиното име? Првиот. И можете да одам таму, ако тоа е стринг, од само гледајќи во низа заградата нула. Па 0. карактер на стрингот. Тоа е лесно. Ние го направи тоа во крипто задача недели. А потоа штом ќе знам дека на Alice писмо е капитал А, ние може да одземе исклучување 65 или капиталот на себе, кој ни дава нула. Па ние сега знаеме дека Алис припаѓа на локација нула. И со оглед на покажувачот на овие податоци структура, на некој вид, колку долго тоа ме земе да се најде локација нула во низа? Само еден чекор, нели Тоа е постојана време бидејќи на случаен пристап ние предложениот беше карактеристика на низа. Значи на кратко, да пронајдат она што индексот на име на Alice е, што е, во овој случај, е, или ајде да се реши дека на нула, каде што B е еден и Ц е два, да пронајдат дека надвор е постојана време. Јас само треба да се погледне во неа првата буква, да пронајдат каде нула е низа е, исто така, постојана време. Толку технички тоа е како два чекори сега. Но, тоа е уште константа. Па ние го нарекуваме дека големите О на еден, па ние сме вметнува Алис во оваа табела во постојана време. Но, се разбира, јас сум се наивни тука, нели? Што ако има Арон во класата? Или Алиша? Или било која друга имиња почнувајќи со А Каде одиме да се стави тоа лице, нели? Мислам, токму сега има само три луѓе на масата, па можеби и ние треба да се стави на Aaron на локација нула еден два три. Право, би можел да се стави тука. Но, тогаш, ако се обидеме да го вметнете Давида во оваа листа, каде Дејвид одиме? Сега нашата систем ќе почне кршење долу, нели? Бидејќи сега Дејвид завршува тука ако Арон е всушност тука. Па сега целата оваа идеја да се има чиста податочна структура која ни дава постојана време инсерции не е веќе постојана време, бидејќи морам да провери, ох, damnit, некој е веќе на локација на Алис. Дозволете ми да ја испитаат можната го остатокот од овој податоци структура, во потрага по место да се стави некој како име на Aaron. И така дека премногу е почеток да се земе линеарно време. Покрај тоа, ако вие сега сакате да го најдете Aaron во оваа податочна структура, а вие провери, и името на Aaron не е овде. Идеално, вие само би рекол на Aaron не во податочна структура. Но ако не почнат да прават простор за Aaron таму каде што требаше да биде D или Е, ти, најлош случај, мора да се провери целата структура на податоци, во кој случај devolves во нешто линеарно на големината на табелата. Така што сите во право, јас ќе го надминете овој. Проблемот тука е тоа што морав 26 елементи во оваа низа. Дозволете ми да го промени. Whoops. Дозволете ми да ја промените, така што наместо да биде на големина 26 во вкупниот, забележуваат дното индекс ќе се промени до n минус 1. Ако 26 е јасно премногу мали за луѓето " имиња, бидејќи има илјадници Имињата на светот, ајде само да во 100 или 1000 или 10.000. Ајде да одвои многу повеќе простор. Па тоа не мора да се намали веројатноста дека нема да имаме два луѓето со имиња почнуваат со A, и така, ќе се обидат да се стави имињата на локација нула уште. Тие се уште се случува да се судираат, кои значи дека ние се уште треба решение да се стави Alice и Арон и Алиша и други имиња почнуваат со други места. Но, како голем дел од проблемот е ова? Што е веројатноста дека имаат судири во податоците структура, како тоа? Па, дозволете ми да - ние ќе се врати на тоа прашање тука. И гледам како ние би можеле реши тоа во прв план. Дозволете ми да се повлече до овој предлог тука. Она што ние само што е опишано е алгоритам, хеуристичен нарекува линеарно љубопитство при што, ако сте се обиделе да го вметнете нешто овде, во оваа податоци структура, која се нарекува хаш табелата, и нема простор таму, можете навистина истрагата на податочна структура проверка, дали е ова на располагање? Е ова Достапно е ова располагање? Дали е ова располагање? И кога конечно е, внесете го името, што што првично се наменети на друго место во таа локација. Но, во најлош случај, единственото место може да биде на самото дно на податоци структура, на самиот крај на низата. Толку линеарни љубопитство, во најлош случај, devolves во еден линеарен алгоритам каде Арон, ако тој се случува да се вметнат последен во оваа податочна структура, тој може да се судираат со оваа прва локација, но потоа заврши со лоша среќа на самиот крај. Па ова не е константа време светиот грал за нас. Овој пристап на вметнување на елементи во податочна структура се нарекува hash маса не чини да се биде константна време барем не во општата случај. Тоа може да се префрлат во нешто линеарна. Па што ако ние го реши судири малку поинаку? Па тука е многу пософистициран пристап кон она што е уште наречен хаш табелата. И со хаш, како настрана, она Сакам да кажам е индекс кој Јас од порано. На хаш нешто може да биде мисла на како глагол. Па ако хаш Алис е име, хаш функција, така да се каже, треба да се врати на број. Во овој случај е нула, ако таа им припаѓа на локација нула, еден, ако таа им припаѓа на локација една, и така натаму. Па ми хаш функција досега е супер едноставен, само гледајќи во првата буква во нечие име. Но на хеш функција зема како влез некои парче на податоци, стринг, на int, сеедно. И тоа плука типично број. И тој број е местото каде што податоци елемент припаѓа на податочна структура познат овде како хаш табелата. Па само интуитивно, ова е малку поинаков контекст. Ова всушност е се однесува на пример вклучувајќи родендени, каде може да има колку што 31 дена во месецот. Но, она што го направи ова лице да одлучи да направите во случај на судир? Контекст сега се не, судир на имиња, туку судир на родендени, ако двајца луѓе имаат ист роденден на на 2 октомври, на пример. СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Да, па тука имаме проширува на поврзани листи. Така што изгледа малку поинаку отколку што го привлече порано. Но, ние се чини дека треба да се низа на левата страна. Тоа е една индекс, за да нема посебна причина. Но тоа е уште една низа. Тоа е низа од покажувачи. И секоја од овие елементи, на секоја овие кругови или засеци - на коса црта претставуваат null - секој од овие совети очигледно укажува на она што на податоци структура? А поврзана листа. Па сега имаме можност да тешко кодот во нашата програма на големината на табелата. Во овој случај, знаеме дека има никогаш не е повеќе од 31 дена во месецот. Толку тешко кодирање вредност како 31 се разумни во тој контекст. Во контекст на имиња, тешко кодирање 26 не е неразумно тоа на луѓето имиња само почнете со, на пример, азбука вклучува преку З Можеме да ставам сите нив во таа податоци структура толку долго како што, кога ќе се добие судир, ние не се стави на имиња тука, ние наместо да мислам на овие клетки не како низи себе, туку како совети како да се, на пример, Алис. А потоа Алис може да имаат друга покажувачот на друго име почнувајќи со А и Боб всушност оди овде. И ако има друго име почнувајќи со Б, тој завршува овде. И така секој од елементите на оваа маса две, ако ние дизајниран ова малку повеќе умно - ајде - ако ние дизајниран ова малку повеќе умно, сега станува адаптивни податоци структура, каде што нема тешко граница од тоа колку многу елементи можете да вметнете во неа, бидејќи ако имате судир, тоа е во ред. Само напред и додаваат дека да она што го видовме малку пред беше познат како поврзана листа. Добро, ајде да пауза за само еден миг. Која е веројатноста за судир на прво место? Право, можеби и јас сум над размислување, можеби Јас сум над инженеринг овој проблем, бидејќи знаеш што? Да, можам да излезе со произволни примери од врвот на мојата глава како Алисон и Арон, но во реалноста, дадена униформа дистрибуција на влезови, тоа е некои случајни инсерции во податочна структура, она што навистина е веројатноста за судир? И излезе, тоа е всушност супер висока. Дозволете ми да се генерализира овој Проблемот е што е оваа. Значи во една соба од n CS50 студенти, она што е веројатноста дека барем двајца ученици во соба имаат ист роденден? Па таму е што. неколку hund - 200, 300 луѓе тука и неколку стотици луѓе дома денес. Па ако си сакал да се запрашаме што е веројатноста за две лица во оваа соба има истите роденден, можеме да дознаам ова. И тврдам всушност постојат два луѓе со исти роденден. На пример, дали некој имаат роденден денес? Вчера? Утре? Сите во право, па таа се чувствува како јас ќе одам мора да го направите тоа 363 или така повеќе пати за да всушност дознаам Ако имаме судир. Или ние може само да го направите ова математички наместо секојдневно да го прават тоа. И предложи следниве. Па јас предложи дека би можеле да се моделира веројатноста на две лица кои имаат ист роденден како веројатност од 1 минус веројатноста на никој не се има ист роденден. Па да се добие ова, и ова е само фенси начин на пишување на оваа, за Првиот човек во собата, тој или таа може да има било една од можните родендени претпоставувајќи 365 дена во годината, со извинување кон лица со на 29 февруари роденден. Па првиот човек во оваа просторија е слободен да има било кој број на родендени од 365 можности, така што ние ќе го направи тоа 365 поделено со 365, која е една. Следниот лице во собата, ако целта е да се избегне судир, може само имаат неговиот или нејзиниот роденден за тоа како многу различни можни дена? 364. Па вториот мандат во овој израз е во суштина прават тоа по математика за нас со одземање исклучи еден можен ден. И потоа на следниот ден, следниот ден, Следниот ден одредување на вкупниот број на луѓе во собата. И ако тогаш ние сметаат, тогаш што е веројатноста не на сите што имаат уникатен родендени, но повторно 1 минус дека, она што го добиваме е израз кои може многу fancifully изгледа вака. Но тоа е поинтересно да се погледне визуелно. Ова е шема каде што на x-оската е бројот на луѓе во собата, број на родендени. На y-оската е веројатноста на судир, две лица кои имаат ист роденден. И готова брза од оваа крива е дека веднаш штом ќе го засакаат 40 студенти, вие сте на 90% веројатност combinatorically на две луѓе, или повеќе има ист роденден. И штом еднаш ќе го засакаат 58 луѓе тоа е речиси 100% од шанса двете луѓе во собата се случува да имаат ист роденден, иако има 365 или 366 можни кофи, и само 58 луѓе во собата. Само статистички најверојатно ќе се добие судири, кој за кратко мотивира оваа дискусија. Дека дури и ако ние се фенси тука, и почнете да имаат овие синџири, ние сме се уште ќе мора судири. Така што се поставува прашањето, што е трошоците за водење инсерции и бришење во податочна структура, како тоа? Па нека ме предложи - и дозволете ми да се врати на екранот во текот тука - ако имаме n елементи во листа, па ако ние се обидуваме да го вметнете n елементи, и ние имаме колку вкупно кофи? Да речеме, 31 вкупно кофи во случај на родендени. Што е максималната должина на една на овие синџири потенцијално? Ако повторно има 31 можно родендени во дадениот месец. И ние сме само згрушувањето сите - всушност тоа е глупаво пример. Ајде да направиме 26 наместо тоа. Значи, ако навистина има луѓе чии имиња Започнете со преку Зи, со тоа давајќи им ни 26 можности. И ние сме со користење на податоци структура како оној кој го видоа, при што имаме низа на совети, од кои секоја укажува на поврзаните листа, каде што Првата листа е секој со името Алис. Втората листа е секој со името почнувајќи со А, со почеток со Б, и така натаму. Што е најверојатно должината на секоја од овие списоци ако претпоставиме убав чист дистрибуција на имиња A до Z низ целата структура на податоци? Има n луѓето во податочна структура поделено со 26, ако тие се убаво се шират во текот на целиот податочна структура. Па должината на секоја од овие синџири е n поделено со 26. Но во голема О нотација, што е тоа? Што е тоа навистина? Така, тоа е навистина само n, нели? Затоа што рековме во минатото, дека ugh сте подели со 26. Да, во реалноста тоа е побрзо. Но во теорија, тоа не е фундаментално сите што побрзо. Па ние не се чини дека се сите дека многу поблиску до оваа Светиот Грал. Всушност, ова е само линеарно време. Подлец, во овој момент, зошто да не само користење една огромна поврзана листа? Зошто да не само користење една огромна низа за чување на имињата на сите во собата? Па, има ли уште нешто релевантни за хаш табелата? Дали има уште нешто релевантни за податочна структура што личи ова? Ова. СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Право, и повторно, ако тоа е само еден линеарен пат алгоритам, и линеарно време податочна структура, зошто да не можам само запази името на сите во голема низа, или во голема поврзана листа? И да престане да прави CS толку многу потешко отколку што треба да биде? Она што е интересно во врска со ова, дури и иако јас го изгребани надвор? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: инсерции не се? Скапо повеќе. Па инсерции потенцијално би можеле уште да биде константна време, дури и ако вашите податоци структура изгледа вака, низа на совети, од кои секоја е насочена кон потенцијално поврзаните листа. Како може да се постигне постојана време вметнување на имиња? Се држи тоа на предната страна, нели? Ако ние жртвува дизајн цел од порано, каде што сакавме да го задржи името на секого, на пример, подредени, или на сите броеви на сцената подредени, да претпоставиме дека имаме несортиран поврзана листа. Тоа само ни се чини еден или два чекори, како и во случај на бен и Брајан порано, за да вметнете елемент во на почетокот на листата. Значи, ако ние не се грижат за сортирање сите на имиња почнуваат со A или сите имињата почнувајќи со Б, ние може да се уште постигне постојана време вметнување. Сега угледување Алис или Боб или било име поопшто се уште е она? Тоа е голема О од n поделено со 26, во идеален случај, каде што секој е подеднакво дистрибуира, каде што има толку многу А колку што има на Z, што е веројатно нереално. Но, тоа е уште линеарна. Но, овде, ќе се вратиме до точка на асимптотска нотација се теоретски вистина. Но, во реалниот свет, ако тврдам дека мојата програма може да стори нешто 26 пати побрзо од твоето, чија програма што ви се случува да преферираат користење? Твое или мое, кои е 26 пати побрзо? Реално, лицето чиј е 26 пати побрзо, дури и ако теоретски нашите алгоритми се извршуваат во истиот асимптотска трчање време. Дозволете ми да предложам поинаков решение заедно. И ако тоа не удар вашиот ум, ние сме надвор од структури на податоци. Значи ова е тоа Trie - вид глупаво име. Таа доаѓа од retrievals, а зборот е напишано Trie, Т-R-з-д, поради Се разбира пронаоѓање звучи како Trie. Но тоа е историја на зборот Trie. Па Trie е навистина некој вид на дрво, и тоа е, исто така, игра на тој збор. И иако не сосема може да ја види со оваа визуелизација, една Trie е дрво структурирана, како семејство дрво со еден предок на врвот и многу на внуци и правнуци како остава на дното. Но секој јазол во Trie е низа. И тоа е во низа - и ајде поедноставуваат за момент - тоа е низа, во овој случај, на големината 26, каде секој јазол повторно е низа од големината 26, каде што 0. елемент во таа низа претставува и последниот елемент во секоја таква низа претставува З Па јас предлагам, тогаш, дека овие податоци структура, познат како Trie, може да биде користи исто така за да ја запази зборовите. Видовме еден миг пред тоа како ние би можеле продавница зборови, или во овој случај имиња, а ние видов порано како ние може да се сместат броеви, но ако се фокусираме на имиња или жици тука, забележи она што е интересно. Тврдам дека името Максвел е внатрешноста на оваа податочна структура. Каде ја гледате Максвел? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: На лево. Значи она што е интересно со овој податоци структура е наместо продавница на низа М-А-Х-З-Е-Л-L обратна коса црта нула, сите contiguously, она што наместо направите ја следи. Ако ова е Trie како податочна структура, секој од чии јазли повторно е низа, и сакате да го зачувате Максвел, мора прво индекс и така на коренот на јазол, па да се каже, на врвниот јазол, на локација М, десно, па приближно во средината. А потоа од таму, можете следат покажувачот на дете јазли, така да се каже. Па во семејното стебло смисла, ќе го следат надолу. И дека ќе доведе до друг јазол на левата таму, кој е само уште една низа. А потоа, ако сакате да го зачувате Максвел, ќе најдете покажувачот, што претставува А, кој е овој овде. Потоа да одите кон следниот јазол. И информации - тоа е причината зошто на сликата малку залажувам - овој јазол изгледаат супер мал. Но на правото на оваа е Y и Z. Тоа е само авторот има скратени на слика, така што ќе всушност ги гледам работите. Во спротивно оваа слика ќе биде многу широк. Па сега вие индекс во локација X, тогаш W, Потоа Е, тогаш L, тогаш Л Тогаш што е овој љубопитност? Па, ако ние сме со користење на овој вид на нови преземе за тоа како да се складира низа во податочна структура, се уште треба да во суштина се провери надвор во податоците Структурата дека зборот завршува тука. Со други зборови, секој од овие јазли некако мора да се запамети дека ние всушност следат сите овие совети и се остава малку леб трошка на дното тука на овој структура за да се покаже М-А-Х-З-Е-Л-L е навистина во оваа податочна структура. Па ние би можеле да го направите тоа како што следува. Секоја од јазли во слика ние само видов има еден, низа на големина 27. И сега е 27, бидејќи во стр постави шест, ние, всушност, ќе ви даде апостроф, па може да имаме имиња како О'Рајли и други со апострофи. Но истата идеја. Секој од овие елементи во низа точки на struct јазол, па само еден јазол. Значи ова е многу потсетува на нашите поврзаните листа. И тогаш имам Булова, која Јас ќе повик збор, што е само ќе биде точно ако еден збор завршува на овој јазол во стеблото. Тоа ефикасно го претставува малку триаголник видовме пред еден миг. Па ако некој збор завршува на тој јазол во дрво, тој збор поле ќе биде вистина, кој е концептуално проверка исклучи, или ние сме цртање овој триаголник, да, постои е збор тука. Значи ова е Trie. И сега прашањето е, она што е неговата трчање време? Е тоа голема О од n? Тоа е нешто друго? Па, ако имаат N имиња во оваа податоци структура, Максвел да биде само една од нив, она што е трчање време на вметнување или изнаоѓање Максвел? Што е трчање време на вметнување Максвел? Ако има n други имиња веќе во табелата? Да? СТУДЕНТСКИ: [нечујни]. ЗВУЧНИК 1: Да, тоа е должина на името, нели? Па М-а-x-w-е-л-л, па таа се чувствува како оваа алгоритам е голема О од седум. Сега, се разбира, името ќе се разликуваат во должина. Можеби тоа е кратко име. Можеби тоа е веќе име. Но она што е Клучот тука е дека Тоа е постојан број. И можеби тоа не е навистина постојано, Но Бог, ако реално, во речник, таму е веројатно некои ограничување основа на бројот на букви во лицето име во одредена земја. И така ние може да се претпостави дека вредност е константа. Не знам што е тоа. Тоа е веројатно поголема од мислиме дека тоа е. Бидејќи секогаш има некој агол случај со луди долго име. Па ајде да го наречеме к, но тоа е уште една постојана веројатно, затоа што секој име во светот, барем во одредена земја, е дека должината или пократко, така што е константа. Но, кога ние рековме дека нешто не е голема О на константна вредност, што е тоа навистина еднакви на? Тоа е навистина истото како вели постојана време. Сега сме вид на мамење, нели? Ние сме вид на проширува некои теорија тука за да се каже дека добро, редослед на k е навистина само нареди на еден, и тоа е постојана време. Но тоа навистина е. Бидејќи клучот увид тука е дека ако имаме n имиња веќе во овој податочна структура, и ние вметнете Максвел, е износот на времето што ни е потребно да се вметнете Максвел на сите засегнати од тоа колку многу други луѓе се во податочна структура? Не чини да се биде. Ако имав една милијарда повеќе елементи на овој Trie, а потоа вметнете Максвел, е тој на сите засегнати? Бр. И тоа е за разлика од било кој од ден на податоци структури што сум го видел досега, каде трчање време на вашиот алгоритам е целосно независна од тоа колку работи е или не е веќе во таа податочна структура. И така со овој овозможува сега е можност за p сет шест, што ќе повторно вклучуваат спроведување на свој проверува правописот, читање во 150.000 зборови, како најдобро да ги чувате дека не е нужно очигледно. И иако сум се стремел да се најде Светиот Грал, јас не тврдат дека Trie е. Всушност, хаш табелата може многу добро се докаже да биде многу поефикасно. Но тие се само - тоа е само една од дизајн на одлуки ќе мора да се направи. Но, во затворање ајде да 50 или така секунди за да се погледнеме во она што лежи пред следната недела и пошироко ние транзиција од овој командната линија свет, ако C програми да работи веб- врз основа и јазици како PHP и Вклучите Javascript-и на интернет себе, протоколи како HTTP, кои сте земе здраво за готово со години сега, и внесе повеќето секој ден, можеби, или видел. И ќе почнеме да лупам назад слоеви на она што е на интернет. И она што е код кој денес во основата алатки. Така 50 секунди на овој закачка тука. Јас ви даде воини на Нет. [Видео репродукција] -Тој дојде со порака. Со записник сите свои. Тој дошол до еден свет на суров firewalls, незасегнатата рутери, и опасностите далеку полошо од смртта. Тој е брз. Тој е силен. Тој е TCPIP. И тој има вашата адреса. Воини на Нет. [Крај видео репродукција] ЗВУЧНИК 1: Тоа е како на интернет ќе работат како на следната недела.