>> SPEAKER 1: Добре, така че ние сме назад.
Добре дошли в CS50.
Това е края на седмицата седем.
Така се припомни, че последния път, ние започнахме разглежда по-сложни леко
структурата на данните.
Тъй като до този момент, всичко, което трябваше наистина на наше разположение беше този, масив.
>> Но преди да се изхвърли масив като не всичко това интересно, което наистина го
всъщност е, какви са някои от плюсове на този прост данни
структура до този момент?
Какво е то добър в?
Доколкото сме виждали?
Какво имаш?
Нищо.
>> Студентът: [недоловим].
>> SPEAKER 1: Какво е това?
>> Студентът: [недоловим].
>> SPEAKER 1: Fixed размер.
ОК, така че защо е фиксиран размер добро все пак?
>> Студентът: [недоловим].
>> SPEAKER 1: Добре, така че това е ефективна в смисъл, че можете да се разпредели
фиксирана сума на пространството, което се надяваме, е точно толкова
пространство, както искате.
Така че може да бъде абсолютно плюс.
>> Какво е друг до страна на масив?
Да?
>> Студентът: [недоловим].
>> SPEAKER 1: Всички - Моля?
>> Студентът: [недоловим].
>> SPEAKER 1: Всички полета в паметта или един до друг.
А това е полезно - защо?
Това е съвсем вярно.
Но как можем да използват тази истина?
>> Студентът: [недоловим].
>> SPEAKER 1: Точно така, ние можем да следите където всичко е просто, знаейки
един адрес, а именно адреса на Първият байт на това парче на паметта.
Или в случай на низа, на адреса на първия
Чар в този низ.
И от там, можем да намерим края на низ.
Ние можем да намерим втория елемент, на Третият елемент, и така нататък.
>> И така, на фантазия може да се опише, че особеност е, че ни дават масиви
произволен достъп.
Само с помощта на квадратна скоба нотация и номер, можете да преминете към
специфичен елемент в масив в константно време, голяма O
на една, така да се каже.
>> Но е имало някои недостатъци.
Какво не масив направи много лесно?
Какво не е добър?
>> Студентът: [недоловим].
>> SPEAKER 1: Какво е това?
>> Студентът: [недоловим].
>> SPEAKER 1: Разширяване на размера.
Така че недостатъците на масива са точно обратното на това, което
квит сме.
Така че един от недостатъците е че е с фиксиран размер.
Така че наистина не може да го отглеждат.
Можете да преразпределят по-голяма буца памет, и след това се премести на старите елементи
в нов масив.
И тогава безплатно стария масив, за Например, с помощта на изчистване или подобна
функция, наречена презаделяне, които пренасочи памет.
>> Презаделяне, като отмени, се опитва да ви даде памет, която е в непосредствена близост до масива
, че вече имате.
Но това може да се движи нещата около напълно.
Но накратко, че е скъпо, нали?
Защото, ако има парче от паметта на този размер, но наистина искате една
с този размер, и искате да запазите оригиналните елементи, трябва
приблизително линеен процес, време за копиране която трябва да стане от
стария масив към новия.
А реалността иска от операционната система отново и отново, и
отново за големи блокове памет може да започне за да ви струва известно време, както добре.
Така че това е едновременно благословия и проклятие в прикрие фактът, че тези масиви
са с фиксиран размер.
Но ако се въведе вместо нещо подобен на този, който се обадихме на свързана
списък, ние да вземем няколко плюсове и няколко недостатъци тук.
>> Така че един свързан списък е просто данни конструкция на structs С в тази
случай, когато една структура, изземване, е само контейнер за един или повече специфични
видове променливи.
В този случай, това, което направи на типовете данни изглежда да е вътре в структурата, че
Последният път, когато нарича възел?
Всеки един от тези правоъгълници е възел.
И всяка една от по-малките правоъгълници във вътрешността му е тип данни.
Какви видове казахме те са били в понеделник?
Да?
>> Студентът: [недоловим].
>> SPEAKER 1: A променлива и показалеца, или По-специално, едно цяло число, за N,
и указател на дъното.
И двете от тези, които се случи да бъде 32 бита, в поне на компютър, подобен на този CS50
Техника, и така те са съставен по равно по размер.
>> Така че това, което използвате показалеца макар и за очевидно?
Защо добавите стрелка сега, когато бяха масиви толкова хубаво и чисто и просто?
Какво е показалеца правиш за ние в всеки един от тези възли?
>> Студентът: [недоловим].
>> SPEAKER 1: Точно така.
Той ти казва, когато следващата се.
Така че аз нещо като използваме аналогията на с помощта на конец, за да сортирате на
вденете тези възли заедно.
И това е точно това, което правим с указатели, тъй като всеки от тях
блокове памет може или не може да бъде тези, обратно към Насрещен
вътрешността на RAM, защото всеки път, когато обадете изчистване казвайки ми даде достатъчно
байта за нов възел, може да да е тук или че може да е тук.
Тя може да бъде тук.
Вие просто не знам.
>> Но използването на указатели в адресите на тези възли, можете да ги бод
заедно по начин, който изглежда визуално като списък, дори ако тези неща са
всички разпределени през целия си една или Вашите две или вашите четири гигабайта RAM
вътрешността на собствения си компютър.
>> Така посока надолу, а след това, на на свързан списък е какво?
Каква е цената, която ние сме очевидно плаща за това?
>> Студентът: [недоловим].
>> SPEAKER 1: Повече място, нали?
Ние, в този случай, два пъти сумата, на пространството, защото сме преминали
от 32 бита за всеки възел, за всеки Int, така че сега 64 бита, защото трябва да
запази около показалеца, както добре.
Можете да получите по-голяма ефективност, ако вашата структура е по-голямо от това просто нещо.
Ако действително има един студент в на които е няколко струни за
име и къща, може би идентификационен номер, може би някои други области като цяло.
>> Така че, ако имате достатъчно голяма структура, тогава може би цената на показалеца е
не е толкова голяма работа.
Това е малко на един ъгъл в случай, че ние сме съхраняване такъв прост примитивен
вътрешността на свързан списък.
Но въпросът е един и същ.
Определено си харчи повече памет, но сте се
гъвкавост.
Защото сега, ако искам да добавят елемент в началото на този списък,
Трябва да се разпредели нов възел.
И аз трябва да актуализирате само тези, стрелките някак си само с преместване
някои насоки наоколо.
>> Ако искате да вмъкнете нещо в средата на списъка, не трябва да
бутнете всеки настрана както направихме в седмици миналото с нашите доброволци, които
представени масив.
Мога да си разпределят нов възел и След това просто точка на стрелките в
различни посоки, тъй като не трябва да остане в действителната
памет истински ред, че съм съставен то тук на екрана.
>> И тогава на последно място, ако искате да вмъкнете нещо, което в края на списъка, че е
още по-лесно.
Това е нещо като произволна бройна система, но 34 на показалеца, да предположите.
Каква е стойността на показалеца си най- вероятно изготвен нещо като стар
училище антена там?
>> Студентът: [недоловим].
>> SPEAKER 1: Вероятно това е нищожна.
И наистина това е един автора представителство на нула.
И това е нищожна, защото сте абсолютно Трябва да знаем къде края на свързан
Списъкът е, за да не се съхранява след и след и след тези стрели
някои боклук стойност.
Така нула ще означава, че няма повече възли на правото на номер 34,
в този случай.
>> Така че предлагам да могат да се реализират този възел в кода.
И сме виждали този вид на синтаксиса преди.
Typedef просто определя нов тип за ни, ни дава синоним като
низ е за Чар *.
В този случай, това ще ни даде краткото записване, така че структурата на възел
може вместо просто да се запише като възловата точка, която е много по-чисти.
Това е много по-малко многословен.
>> Вътре възел е очевидно едно цяло число наречена N, а след това и структурата възел *
което означава точно това, което искахме стрелките, за да кажа, указател към друг
възел на точно същия тип данни.
И аз предлагам да може да приложи функция за търсене, подобен на този, който най-
пръв поглед може да изглежда малко комплекс.
Но нека да видим това в контекст.
>> Оставете ме да премина към уреда тук.
Нека да отворят файл, наречен списък нулева точка з.
И че само съдържа определението ние Току-що видях преди малко за тези данни
тип нарича възел.
Така че ние сме поставени, че в точка файл з.
>> И като настрана, въпреки че това програма, която сте на път да видите, е
Не всичко, което комплекс, това е наистина Конвенцията при писане на програма за
постави нещата като типове данни, за да дръпнете константи понякога, вътрешността на
заглавния файл, а не непременно в си C файл, със сигурност, когато
програми стават по-големи и по-големи, така че Вие знаете къде да търсите, както за
документация, в някои случаи, или за основните неща по този начин,
определяне на някакъв вид.
>> Ако сега се отвори списък нулева точка С забележите няколко неща.
Тя включва няколко заглавни файлове, повечето на което сме виждали преди.
Тя включва собствен заглавен файл.
>> И като настрана, защо това е двойно Цитати тук, за разлика от ъгъла
скоби на линията, която Аз бях подчерта там?
>> Студентът: [недоловим].
>> SPEAKER 1: Да, така че е локален файл.
Така че, ако това е локален файл на свой собствен тук по линия 15, например, да използвате
двойните кавички вместо от ъглови скоби.
>> Сега това е нещо интересно.
Забележете, че съм обявен за глобален променлива в тази програма по линия 18
нарича Първо, идеята е това е Ще бъде указател към първия
възел в свързания списъка ми, и съм инициализира го присвоява, защото съм
не са разпределени всяко действително възли, просто все още.
>> Така че това означава, картинно, това, което ние видях преди малко в картина като
че показалецът на далеч лявата страна.
Така че точно сега, че показалеца не оказва стрелка.
Вместо това е само нищожна.
Но той представлява това, което ще бъде адресът на първия действителното
възел в този списък.
Така че аз съм приложен е глобален защото, както ще видите, всичко това
Програмата се прилага в живота е на свързан списък за мен.
>> Сега имам няколко прототипа тук.
Реших да прилагат функции, като изтриване, вмъкване, търсене, и
прекосявам -
последната просто е разходка през списък, отпечатване на нейните елементи.
И сега тук е моят основната програма.
И ние няма да прекарват твърде много време в тях, тъй като това е нещо, надявам се
стара шапка от сега.
>> Отивам да направя следното, докато потребителят сътрудничи.
Така един, аз отивам да отпечатате от това меню.
И съм форматирал него като чисто, колкото можех.
Ако потребителят на едно, това означава, че те искат да изтриете нещо.
Ако потребителят на две, това означава, че те искат да вмъкнете нещо.
И така нататък.
Ще бъдете подканени След това за команда.
И тогава аз ще използвам GetInt.
>> Така че това е много проста menuing намесвам, когато просто трябва да въведете
редица картографиране на една на тези команди.
И сега имам хубава чиста ключ декларация, че ще се включите
независимо от потребителя написали инча
И ако те написали едно, аз ще обадете изтриете и почивка.
Ако те написали два, аз ще обадете вмъкнете и почивка.
>> И сега забелязвам сме поставени всеки от тях на една и съща линия.
Това е просто стилистични решения.
Обикновено сме виждали нещо по този начин.
Но аз просто реших, честно казано, моята програма изглеждаше по-разбираемо, защото
тя е само четири случая на просто го списъка по този начин.
Totally законното използване на стил.
И аз ще направя това, докато на Потребителят не е въвел нула, което аз
реши, ще означава, че те искат да се откажат.
>> Така че сега забележите това, което съм ще направим тук.
Отивам да освободи списък очевидно.
Но повече за, че в един момент.
Нека първо да стартирате тази програма.
Така че нека да се направи по-голям терминал прозорец, точка наклонена черта списък 0.
Отивам да се продължи напред и го поставете от пишете две, редица като 50, а сега
ще видите списък сега е 50.
И моят текст просто превъртат малко.
Така че сега забележите списъкът съдържа 50 броя.
>> Нека да направим още една вложка, като се вземат две.
Нека да изпишете номера като такъв.
Списък сега е един, последван от 50.
Така че това е просто текстово представяне на списъка.
И нека да вмъкнете още един номер като броят 42, което е се надяваме
ще свърши в средата, защото тази програма, по-специално видове него
елементи, тъй като им вложки.
Така че ние я имаме.
Super проста програма, която може да абсолютно са използвали масив, но аз
се случи да се използва свързан списък само за да мога да динамично
растат и да го свие.
>> Така че, нека да погледнем за търсене, ако Изпълнява КОМАНДА три, искам да търсите
за, да речем, на номер 43.
И нищо не е очевидно установено, защото се върнах никакъв отговор.
Така че нека да го направим отново.
Търсене.
Нека търсенето на 50, или по-скоро търсене за 42, което има хубав
малко коварен значение.
И открих смисъла на живота там.
Брой 42, ако не знаете препратка, то Google.
Добре.
И така, какво е тази програма направи за мен?
Това е просто ми позволи да вмъкнете този начин далеч и търсене на елементи.
>> Нека бързо напред, а след това, за да тази функция ние погледна
В понеделник като закачка.
Така че тази функция, аз твърдя, търси елемент в списъка, като първо
един, подканване на потребителя и след това призовава GetInt да получите действително Int
, която искате да търсите.
>> Тогава забележите това.
Отивам да се създаде временна променлива 188 в съответствие нарича показалеца -
PTR -
можеше да го нарече нещо.
И това е указател към възела защото казах възел * там.
И аз съм инициализиране тя да бъде равна на първо, за да мога ефективно да имам
пръст, така да се каже, на много Първият елемент от списъка.
Така че, ако дясната ми ръка тук е PTR съм сочи едно и също нещо, че първата
се посочи.
>> Така че сега отново в кода, какво се случва след това -
това е една обща парадигма при обработката на текста в продължение на структурата като
свързан списък.
Отивам да направите следното, докато показалеца не е равна на нула Така че, докато
пръста ми не е насочена към някои нула стойност, ако Стрелката п равнява п.
Ще забележите, че първо п е това, което потребителя напечатани в на GetInts наричат ​​тук.
>> Стрелката и п означава какво?
Ами ако се върнем на снимката тук, ако имам пръст сочеше
че първата точка, съдържаща девет, на стрелка по същество означава, отидете на тази
възел и вземете стойността на местоположението N, В този случай, данните поле, наречено п.
>> Като настрана - и ние видяхме това няколко Преди седмица, когато някой попита -
този синтаксис е нова, но тя не да ни даде сили, които ние
не вече имате.
Каква беше тази фраза едно да се използва точкова нотация и звезда двойка
Преди седмица, когато се отлепи назад този слой малко преждевременно?
>> Студентът: [недоловим].
>> SPEAKER 1: Точно така, това е звезда, и След това беше звездни точка N, с
скоби тук, които изглежда, честно казано, мисля, че много
по-загадъчен за четене.
Но звездата показалеца, както винаги, средства там.
И след като сте там, какви данни областта искаш да влезете?
Ами използвате точка нотация за достъп а structs полето за данни, и аз
специално искам п.
>> Честно казано, бих казал, това е просто по-трудно да се чете.
Това е трудно да си спомня къде се скобите отида, на
звезда и всичко това.
Така света приемат някои синтактични захар, така да се каже.
Само един секси начин да се каже, това е еквивалентно, и
може би по-интуитивен.
Ако показалецът е наистина показалеца, на средства със стрелки нотация отида там и да намерят
областта в този случай нарича п.
>> Така че, ако го намерите, обърнете внимание на това, което правя.
Аз просто разпечатате, открих аз процента, включване на стойност за този вътр.
Призовавам спя за една секунда, само за да вид на пауза неща на екрана, за да
дава на потребителя секунди да абсорбира какво стана.
И тогава аз се счупят.
В противен случай, какво да правя?
I актуализира показалеца на равно показалеца на стрелката.
>> Така че просто да е ясно, това означава, отидете там, използвайки моя старата школа нотация.
Така че това просто означава, за да отидете на каквото и , което сочи, които в много
Първият случай е, че аз съм сочеше на структура с девет в него.
Така че аз съм отишъл там.
И тогава точката нотация означава, получите стойността на следващото.
>> Но на стойност, въпреки че е изготвен като тесен, е просто число.
Това е цифров адрес.
Така че това един ред код, независимо дали написан по този начин, толкова по-загадъчен
начин, или по този начин, малко по- интуитивен начин, просто означава, премести ръката ми
от първия възел към следващия, и след това на следващия, и след това
следващата, и така нататък.
>> Така че ние няма да се спираме, от друга реализации на вмъквате и изтривате
и прекосявам, първите две от които са доста участват.
И мисля, че това е доста лесно да се получи загубят, когато го правят устно.
Но какво можем да направим тук, е се опитват да определят как
най-добре да направите това визуално.
Защото аз предлагам, че ако искате да вмъкнете елементи в тази
съществуващ списък, който има пет елемента -
9, 17, 22, 26, и 33 -
ако щяха да се приложи тази в код, аз трябва да се помисли как да стане
направят това.
>> И аз предлагам да приемате малки стъпки при което, в този случай искам да кажа, това, което са
възможните сценарии, които ние може да срещнете по принцип?
При прилагането на вложка за свързан списък, това просто се случва да бъде
Характерен пример за размера пет.
Е, ако искате да въведете цифра, като твърдят, че броят една страна, и
поддържане сортирани цел, когато е очевидно прави номер едно трябва да
отидете в този конкретен пример?
Както в началото.
>> Но това, което е интересно е, че ако желаете да вмъкнете едно в тази
списък, какви специални показалеца трябва да се актуализира очевидно?
Първо.
Така че бих казал, че това е първият случай че може да искате да разгледа, а
сценарий включва поставяне на началото на списъка.
>> Нека одират може би един толкова лесно, или дори по-лесно така, относително казано.
Да предположим, че искате да вкарате номер 35 в сортирани цел.
Тя очевидно принадлежи там.
И така, какво показалеца очевидно ще трябва да се актуализира в този сценарий?
34 на показалеца все не нула но на адреса на структурата
съдържащ броя 35.
Така че това е случай две.
Така вече, аз съм нещо като квантуване колко много работа трябва да направя тук.
>> И накрая, очевидно случая средата е Действително, в средата, ако искам да
вмъкнете нещо като думата 23, която отива между 23 и 26, но
Сега нещата стават малко по- участва, защото това, което
указатели трябва да се промени?
Така 22 очевидно трябва да се промени , тъй като не може да посочи 26 повече.
Той трябва да сочи към нова възлова точка, която Ще трябва да се разпределят, като се обадите
изчистване или някакъв еквивалент.
>> Но тогава аз също се нуждаят от този нов възел, 23 в този случай, да има своя показалеца
посочи кого?
26.
И там ще бъде цел на операциите тук.
Защото, ако върша това безумие и аз например започва от началото на
списъка, и моята цел е да поставите 23.
И да проверя, пък принадлежат тук, в близост до девет?
Не.
Има ли тук мястото, до 17?
Не.
Дали тя принадлежи тук до 22?
Да.
>> Сега, ако аз съм глупаво тук, а не мисля това през, може
разпредели новата ми възел за 23.
Аз може да актуализира показалеца от възела, наречен 22, сочейки
то на нов възел.
И след това какво трябва да се актуализира показалеца на нов възел да бъде?
>> Студентът: [недоловим].
>> SPEAKER 1: Точно така.
Посочването на 26.
Но дявол да го вземе, ако не бях вече актуализира Показалеца 22 по точка в този човек, и
сега имам сираци, останалите на списъка, така да се каже.
Така реда на операциите тук ще бъде важно.
>> За да направите това може ли да открадна, да речем, шест доброволци.
И нека да видим дали не можем да направим това визуално вместо код-мъдър.
И ние имаме някаква хубава стрес топчета за вас днес.
OK, какво ще кажеш за един, два, в обратно - в края там.
три, четири, и на двама ви момчетата в края.
И пет, шест.
Разбира се.
Пет и шест.
Добре ние ще дойдем с вас следващия път.
Добре, качвай се.
>> Добре, след като си тук, първо, бихте искали да бъде едно опасно
в Google Glass тук?
Добре, това е така, OK, стъкло, запишете видеоклип.
ОК, вие сте добре да тръгвам.
>> Добре, така че ако вие може да дойдеш тук, съм приготвил предварително
някои цифри.
Добре, ела тук.
И защо не отидеш малко допълнително по този начин.
И нека да видим, как ти е името, с Glass Google?
>> Студентът: Ben.
>> SPEAKER 1: Бен?
OK, Бен, ще бъдат първи, буквално.
Така че, ние ще Ви изпратим до края на етапа.
Добре, и вашето име?
>> Студентът: Джейсън.
>> SPEAKER 1: Jason, OK ти ще бъде номер девет.
Така че, ако искате да следвате Ben този начин.
>> Студентът: Jill.
>> SPEAKER 1: Jill, ти започваш да бъде 17, които, ако бях направил това по-
интелигентно, аз ще трябва започна в от другата страна.
Ти отиде по този начин.
22.
А вие сте?
>> Студентът: Mary.
>> SPEAKER 1: Mary, ще бъде 22.
И името ти е?
>> Студентът: Chris.
>> SPEAKER 1: Крис, ще бъде 26.
И тогава накрая.
>> Студентът: Diana.
>> SPEAKER 1: Diana, ще бъде 34.
Така че ела тук.
>> Добре, толкова съвършена, сортирано поръчате вече.
И да вървим напред и да направите това така че наистина можем да -
Ben ти си просто вид търсите навън в нищото там.
ОК, така че да вървим напред и да изобразяват тази използване на оръжие, подобно бях точно,,
какво става.
Така че продължавайте напред и Подарете си пеша или два между себе си.
И давай напред и посочи с ръка към всеки, който трябва да се посочи
въз основа на това.
И ако сте нула просто точка право надолу към пода.
ОК, така добре.
>> Така че сега ние имаме свързан списък, и ме пусна предложи, че ще играе ролята на
PTR, така че аз няма да се притеснява нося това наоколо.
И след това - някой глупав конвенция - можете да се обадите това всичко, което искате -
предшественик показалеца, Pred показалеца -
това е само псевдоним дадохме в нашия примерен код за лявата си ръка.
От друга страна, че ще бъде водене следите на кой кой е в
следните сценарии.
>> Така че предполагам, първо, искам да скубя че първият пример за вмъкване, да речем
20, в списъка.
Така че ми трябва някой, който да въплъщават номер 20 за нас.
Така че аз трябва да изчистване някой от публиката.
Хайде нагоре.
Как се казваш?
>> Студентът: Brian.
>> SPEAKER 1: Brian, добре, така че е възел, съдържащ 20.
Добре, ела тук.
И очевидно, когато се Brian принадлежат?
Така че, в средата на - всъщност, чакай малко.
Ние правим това от ред.
Правим това много по-трудно освен това трябва да бъде в началото.
OK, отиваме на свободно Brian и презаделяне Brian като пет.
>> ОК, така че сега искаме да вмъкнете Brian като пет.
Така че ела тук до Ben само за миг.
И вие може да се предполага кажа където тази история става.
Но нека да помислят внимателно реда на операциите.
И това е точно този визуален че това ще се подредят
с този примерен код.
Така че тук съм PTR сочи първоначално не на Бен, сам по себе си, но каквото и
ценим той съдържа, което в този случай е - това, което ти беше името?
>> Студентът: Джейсън.
>> SPEAKER 1: Jason, така Ben както и аз сме сочеше Jason в този момент.
Така че сега ще трябва да се определи, къде Brian принадлежат?
Така че единственото нещо, което има достъп до точно сега му е п показател за данни.
Така че аз ще да се провери, е Brian по-малко от Jason?
Отговорът е вярно.
>> И сега какво трябва да се случи, в правилния ред?
Трябва ли да актуализирам колко указатели общо в тази история?
Когато ръката ми все още сочеше Джейсън, и ръката си - ако искате да
сложи си ръка като, нещо, I не знам, въпросителен знак.
Добре, добре.
>> Добре, така че имате няколко кандидати.
Ben или I или Brian или Jason или всеки друг, който
указатели трябва да се промени?
Колко общо?
>> ОК, така че два.
Моята показалеца няма значение вече защото аз съм само временно.
Така че тези две момчета, вероятно, Бен и Брайън.
Така че позволете ми да предложа да актуализирате Бен, тъй като той е на първо място.
Първият елемент от този списък сега ще бъде Брайън.
Така Ben точка на Брайън.
ОК, сега какво?
>> Кой ще посочи към кого?
>> Студентът: [недоловим].
>> SPEAKER 1: ОК, така Brian има точка към Джейсън.
Но съм изгубили следите на показалеца, че?
Да знам къде е Джейсън?
>> Студентът: [недоловим].
>> SPEAKER едно: да направя, тъй като аз съм временното показалеца.
И се предполага, че не са се променили да посочи в нов възел.
Така че ние можем просто трябва Brian точка в който аз съм сочеше.
И сме готови.
Така единия случай вмъкване в началото на списъка.
Имаше две ключови стъпки.
One, трябва да актуализирате Бен, а след това ние също трябва да се актуализира Брайън.
И тогава не е нужно да се притеснява traipsing през останалата част от
списъка, тъй като вече е намерил своя място, защото той принадлежи на
отляво на първия елемент.
>> Добре, така че доста ясен.
В действителност, има усещането, че сме почти извършването на тази твърде сложна.
Така че нека сега одират края на списъка, и да видим къде
сложността започва.
Така че, ако сега, заделянето на памет от страна на публиката.
Всеки, който иска да играе 55?
Добре, видях ръката си пръв.
Хайде нагоре.
Да.
Как се казваш?
>> Студентът: [недоловим].
>> SPEAKER 1: Habata.
Добре, качвай се.
Ще се броят 55.
Така че, разбира се, принадлежат в края на списъка.
Така че нека да замествам симулацията с мен е на PTR само за миг.
Така че аз съм първият ще посоча независимо на Бен посочи.
И двамата сочи сега на Браян.
Така че 55 не е по-малко от пет.
Така че, аз отивам да се актуализира от сочещи към следващия показалеца на Брайън, който
Сега, разбира се, Джейсън.
55 не е по-малко от девет, така че Отивам да се актуализира PTR.
Отивам да се актуализира PTR Аз ще актуализира PTR.
И аз ще - Хм, какво е ти беше името?
>> Студентът: Diana.
>> SPEAKER 1: Diana сочи, разбира се, на нула с лявата си ръка.
Е, къде прави Habata всъщност принадлежат ясно?
В ляво, тук.
Е, как да знам, за да я сложи тук Мисля, че съм провалил.
Защото това, което е PTR изкуство настоящия момент?
Null.
Така че, въпреки че, визуално, ние можем очевидно виж всички от тях
момчета тук на сцената.
Аз не съм следял предходната лице в списъка.
Аз нямам пръст посочи, в този случай възловата точка номер 34.
>> Така че да започнете действително това свърши.
Така че сега аз действително е нужно втори локална променлива.
И това е, което ще видите в действителната проба C код, където, както и да отида,
когато се актуализира дясната ми ръка да се отбележи Джейсън, като по този начин остави зад Брайън, I
По-добре да използва лявата си ръка, за да актуализира, когато бях, така че като отида
чрез този списък -
по-опасно, отколкото възнамерявах Сега тук визуално -
Ще стигнем до края на списъка.
>> Тази страна все още е нула, което е доста безполезни, освен да покаже,
Аз съм ясно в края на списъка, но сега поне имам тази
предшественик показалеца сочи тук, така че Сега това, което ръцете и какво указатели трябва
за да се актуализира?
Чия ръка искаш да преконфигурирате първи?
>> Студентът: [недоловим].
>> SPEAKER 1: ОК, така че Даяна.
Къде искате да посоча Ляво Даяна показалеца на?
На 55, вероятно, така че ние сме добавя там.
А там, където трябва 55 показалеца отидете?
Down, представлява нищожна.
И ръцете ми, в този момент, не значение, защото те са само
временни променливи.
Така че сега сме готови.
>> Така че допълнителната сложност там - и това не е толкова трудно за изпълнение,
но ние се нуждаем от помощна променлива, за да се, че преди да се движи дясната си
страна, аз се актуализира стойността на лявата ми страна, Pred показалеца в този случай, така че
че имам зад гърба показалеца , за да следите къде се намирам.
Сега като настрана, ако си мислиш това чрез това се чувства като тя е
малко досадно да трябва да се запази проследяване на това лявата ръка.
>> Какво би друго решение на този проблем са?
Ако имаш да редизайн на данните структура говорим
чрез точно сега?
Ако това просто вид чувства малко досадно да трябва, като, две указатели
върви по списъка, кой друг може да са, в един идеален свят, поддържа
информация, която ни трябва?
Да?
>> Студентът: [недоловим].
>> SPEAKER 1: Точно така.
Точно така всъщност има интересен кълнове на една идея.
И тази идея на предишния показалеца, сочещи за предишния елемент.
Ами ако просто въплътена че вътре в себе си списък?
И това ще бъде трудно да се визуализира това, без цялата хартия
падане на пода.
Но да предположим, че тези момчета използват както на ръцете им да имат предишен
показалеца, и следващия показалеца, като по този начин прилагане на това, което ние ще се обадя на двойно
свързан списък.
Това ще ми позволи да сортирате назад, много по-лесно, без мен,
програмист, се налага да се запази проследявам ръчно -
наистина ръчно -
от мястото, където съм бил преди това в списъка.
Така че ние няма да направим това.
Ние ще продължаваме да го прости, защото това е ще дойде на цена, два пъти
много място за указатели, ако искате втори.
Но това е наистина обща данни структура, известна като
двойно свързан списък.
>> Нека да направим окончателния например тук и да тези момчета на тяхното нещастие.
Така изчистване 20.
Хайде нагоре от пътеката там.
Добре, как ти е името?
>> Студентът: [недоловим].
>> SPEAKER 1: Моля?
>> Студентът: [недоловим].
>> SPEAKER 1: Demeron?
OK качвай се.
Вие трябва да бъде 20.
Вие очевидно ще принадлежат между 17 и 22.
Така че позволете ми да научат урока си.
Аз ще започна показалеца сочеше Брайън.
И аз ще имам лявата ръка актуализирате само да Brian като се преместя в
Jason, проверка прави 20 по-малко от девет?
Не.
20 е по-малко от 17?
Не.
Е с 20 по-малко от 22?
Да.
И така, какво указатели или ръцете трябва да се промени където те насочваш сега?
>> Така че, можем да направим 17 сочеше 20.
Така че, това е добре.
Къде искаме да посоча показалеца сега?
В 22.
И ние знаем, където 22 е, отново благодаря да ми временно показалеца.
Така че ние сме ОК там.
Така че заради това временно складиране Аз съм следял, където всеки е.
И сега можете визуално да отидат в която ти е мястото, а сега ние трябва 1, 2, 3,
4, 5, 6, 7, 8, 9 стрес топки, и аплодисменти за
тези момчета, ако можехме.
Браво.
>> [APPLAUSE]
>> SPEAKER 1: Добре.
И вие може да задържи парчета на хартия като спомени.
>> Всички права, така, повярвай ми това е много по-лесно да преминете през този с
хора, отколкото е с застроена код.
Но това, което ще намерите в един момент сега, е, че една и съща - О, благодаря ви.
Благодаря ви -
е, че вие ​​ще откриете, че едни и същи данни структура, на свързан списък, всъщност може
да се използва като градивен елемент за още по- сложни структури от данни.
>> И осъзнават твърде темата тук е, че ние сме абсолютно въведени по-
сложността на изпълнението на този алгоритъм.
Insertion, и ако я преживяхме, заличаване и търсене, е малко
по-сложно, отколкото е е с множество.
Но ние получаваме някаква динамика.
Ние получите адаптивна структура на данните.
>> Но отново, плащаме цената на като някои допълнителна сложност, както в
прилагане него.
И ние сме се отказали от произволен достъп.
И за да бъда честен, не е някой хубав чисто предметно мога да ви дам, че
Тук пише защо свързан списък е по-добре от масив.
И да спрем дотук.
Тъй като темата отново появяване на предприятието, дори Още повече, че през следващите седмици, е
че там не е задължително един верен отговор.
>> Ето защо ние имаме отделна ос на дизайн за проблемните групи.
Той ще бъде много зависи от контекста дали искате да използвате тези данни
структура или че един, и то ще зависи от това, което има значение за вас по отношение
на ресурсите и сложност.
>> Но нека да предложи идеални данни структура, Светия Граал, ще бъде
нещо, което е константно време, независимо от това колко неща е
вътре в нея, не би ли било невероятно, ако структурата на данните върнати отговори в
константно време.
Да.
Тази дума е в огромния си речник.
Или Не, тази дума няма.
Или някой такъв проблем съществува.
Ами нека да видим, ако не можем поне предприеме стъпка към това.
>> Нека да предложи нова структура на данните, които може да се използва за различни неща,
В този случай нарича хеш таблица.
И така, ние всъщност сме обратно към фланга в масив, в този случай, и
донякъде произволно, съм нарисувал хеш таблица като масив с нещо като
двумерен масив -
или по-скоро това е изобразен тук като две двумерен масив - но това е само
масив с размер 26, така че ако обадете се на масив, маса скоба
нула е правоъгълник в горната част.
Таблица скоба 25 е правоъгълник в долната част.
А това е как бих могъл да нарисувате данни структура, в която искам да се съхранява
хората имена.
>> Така например, и аз няма да привлече всичко тук на режийни, ако
имаше този масив, който аз сега ще повикване на хеш таблица, и това е отново
Местоположение нула.
Това тук е мястото една страна, и така нататък.
Аз твърдя, че искам да използват тази информация, структура, в името на дискусията,
да съхранявате имената на хората, Alice и Bob и Charlie и други такива имена.
Така че мисля за това сега, като началото на, да речем, един речник
с много думи.
Те се случи да бъде имена В нашия пример тук.
А това е твърде уместен, може би, за да прилагане за проверка на правописа, тъй като ние
може за определен проблем шест.
>> Така че, ако имаме масив на обща площ 26 , така че това е 25-място
на дъното, и аз твърдя, че Алис е първата дума в речника на
имена, които искам да вмъкнете в RAM, в тази структура от данни, където са
инстинктите ви казвам, че на Алис Името трябва да отида в този масив?
>> Имаме 26 опции.
Когато искаме да я сложите?
Ние я искам в скобата нула, нали?
А за Алис, нека го наречем, че е нула.
И B ще бъде една и С ще бъдат две.
Така че ние ще напишем Алис име тук.
Ако след това поставете Bob, си Името ще отидете тук.
Charlie ще отидете тук.
И така нататък надолу през тези данни структура.
>> Това е една прекрасна структура на данните.
Защо?
Ами това, което е времето на работа поставите името на човека е в това
структура на данните в момента?
Като се има предвид, че тази таблица се прилага, наистина, като масив.
Ами това е константно време.
Това е състояние на някой.
Защо?
>> Е, как да се определи където Alice принадлежи?
Вие търсите в която буква от името си?
Първият.
И вие можете да отидете там, ако това е низ, от просто гледам на низ
скоба нула.
Така нулевия символ на низа.
Това е лесно.
Направихме го в крипто присвояване седмици.
И тогава след като знаете, че на Алис Писмото е столица, ние можем да се изважда
отстъпка 65 или капитал A себе си, която ни дава нула.
Така че ние вече знаем, че Alice принадлежи в населено място нула.
>> И тъй като указател към тези данни структура, от някакъв вид, колко време
ми отнеме да намерите място нула в масив?
Само една крачка, нали това е константно време поради произволен достъп се
планирана е функция на масив.
Така че, накратко, фигуриращ какво индекса от името на Алис е, което е, в
този случай, е А, или нека просто решаване че на нула, където В е един и С е
две, смятайки, че от е константно време.
Просто трябва да погледнем в първата си писмо, фигуриращ къде нула е
масив е константно време.
Така че технически това е като две стъпки сега.
Но това все още е постоянна.
Така че ние наричаме тази голяма O на една, така че ние сме добавя Алиса в тази таблица в
константно време.
>> Но, разбира се, аз съм като наивна тук, нали?
Какво става, ако има един Аарон в клас?
Или Алисия?
Или някакви други имена като се започне с A. Къде отиваме да
този човек, нали?
Искам да кажа, в момента има само три хората на масата, така че може би ние
следва да Aaron в населено място нула едно две три.
>> Добре, може да доведе до тук.
Но след това, ако се опитаме да вмъкнете David в този списък, къде David отидете?
Сега нашата система започва да се счупи надолу, нали?
Защото сега Дейвид завършва тук ако Aaron всъщност е тук.
И сега цялата тази идея да има чиста структура от данни, която ни дава
постоянни вмъквания време вече не е константно време, защото трябва да
проверите, о, по дяволите, някой вече е на мястото на Алис.
>> Нека сонда останалата част от тези данни структура, търси място да се сложи
някой като името на Аарон.
И така, това също започва да линейното време.
Освен това, ако сега искате да намерите Aaron в тази структура от данни, а вие
проверите, и името на Аарон не е тук.
В идеалния случай, просто ще кажа, Аарон не в структурата на данните.
Но ако го направите започнете да печелите място за Аарон, където би трябвало да има един D
или E, вие, най-лошия случай, трябва да се провери цялата структура на данните, по-
който случай тя преминава в нещо линейно в рамките на размера на таблицата.
>> Така че, добре, аз ще се определи това.
Проблемът тук е, че трябва 26 елементи в този масив.
Нека да го промените.
Опа.
Нека да го промените така, че вместо да е на на площ от 26 общо забележите дъното
Индексът ще се промени до п минус 1.
Ако 26 е ясно твърде малък, за хората " имена, защото има хиляди
имена на света, нека просто да на 100 или 1000 или 10000.
Нека просто се разпределят много повече пространство.
>> Добре, че не е задължително да намалява вероятността, че няма да има две
хора с имена започват с А, и така, че ще се опита да сложи A
имена на местоположението нула неподвижно.
Те все пак ще се сблъскат, които означава, че ние все още се нуждаят от решение да се сложи
Alice и Аарон и Алисия и други имена, започващи с A другаде.
Но колко голям проблем е това?
Каква е вероятността, че има сблъсъци в данните
структура като този?
>> Е, нека да - ще се върнем на този въпрос тук.
И вижте как да го реши пръв.
Позволете ми да спра това предложение тук.
Това, което току-що описах е един алгоритъм, евристичен нарича линейна
сондиране, при която, ако се опитате да вмъкнете нещо тук, в тези данни
структура, която се нарича хеш таблица, и няма място там,
наистина сонда за структура на данните проверка, е това на разположение?
Дали това разположение е това на разположение?
Това е на разположение?
И когато най-накрая е, поставите името, което първоначално предназначени
другаде на това място.
Но в най-лошия случай, единственото място може да бъде на дъното на данните
структура, в самия край на масива.
>> Така линейни сондиране, в най-лошия случай, преминава в линеен алгоритъм, където
Aaron, ако той се случва да се добавя последно в тази структура от данни, той може да
сблъскат с този първи място, но след края на лош късмет в самия край.
Така че това не е постоянна време Светия Граал за нас.
Този подход на вмъкването на елементи в данни структура, наречена хеш
Таблицата не изглежда да е константно време поне не в общия случай.
Той може да прехвърли в нещо линейна.
>> И какво, ако ние решаване сблъсъци малко по-различно?
Така че тук е по-сложен подход към това, което е все още
наречена хеш таблица.
И от хашиш, като настрана, това, което Искам да кажа, е индексът, че
I посочена рано.
За да хеш нещо може да бъде мисли като глагол.
>> Така че, ако хеш Alice е име, хеш функция, така да се каже,
трябва да се върне редица.
В този случай е равна на нула, ако тя принадлежи на местоположение нула, едно, ако тя принадлежи на
Местоположение една страна, и така нататък.
Така че моята хеш функция до този момент е било супер проста, само гледа към
Първата буква в името на някого.
Но хеш функция приема като въвеждане на някаква част от данните, с
низ, едно цяло число, независимо.
И го изплюва обикновено число.
И това е мястото, където броят на тези данни елемент принадлежи към структурата на данните
известен тук като хеш таблица.
>> Така че просто интуитивно, това е малко по-различен контекст.
Това всъщност се позовава на пример включващи рождени дни, когато е
може да има толкова, колкото Трийсет и един ден в месеца.
Но какво е това лице да вземе решение за правят в случай на катастрофа?
Context сега е, а не сблъсък на имена, но сблъсък на рождени дни,
Ако двама души имат същия рожден ден 2-ри Октомври, например.
>> Студентът: [недоловим].
>> SPEAKER 1: Да, така че тук имаме на деблокирането на свързани списъци.
Така че изглежда малко по-различно отколкото ние го привлече по-рано.
Но изглежда, че имат към масив на лявата страна.
Това е един форум, за не конкретна причина.
Но тя все още е масив.
Това е масив от указатели.
И всеки от тези елементи, всеки от тези кръгове или наклонени черти - наклонената черта
представлява нищожна - всяка една от тези указатели е очевидно, сочещи към
какви данни структура?
A свързан списък.
>> Така че сега ние сме в състояние да твърд код в нашата програма
размера на таблицата.
В този случай, знаем, че никога не е повече от 31 дни в месеца.
Толкова е трудно кодиране на стойност, като 31 е разумно в този контекст.
В контекста на имената трудно кодиране 26 не е неразумно хората
имената само начало, например, азбуката, включващи до Z.
>> Ние можем да се тъпча всички тях в тези данни структура, доколкото, когато получите
сблъсък, ние не поставяме имената тук, ние, вместо да мислят за тези клетки
не като низове самите, а като указатели към, например, Алис.
И тогава Алис може да има друг показалеца за друго име започва с
A. И Боб всъщност става тук.
>> И ако има друго име започва с B, той завършва тук.
И така, всеки от елементите на тази масата две, ако ние създадохме този на
малко по-хитро -
хайде -
ако ние създадохме това малко по- хитро, сега става адаптивен данни
структура, където няма твърда граница от това колко елементи можете да вмъкнете
в него, защото ако имате сблъсък, това е добре.
Просто върви напред и да го приложи към това, което видяхме преди малко беше
известен като свързан списък.
>> Ами нека да пауза за момент.
Каква е вероятността от сблъсък на първо място?
Добре, може би аз съм над мисли, може би Аз съм над инженеринг този проблем,
защото знаеш ли какво?
Да, мога да излезе с произволна примери разстояние от върха на главата ми като
Allison и Аарон, но в действителност, даден равномерно разпределение на
входове, тоест някои случайни вмъквания в структурата на данните, това, което наистина е
вероятността за сблъсък?
Ами оказва се, че всъщност супер висока.
Нека обобщим това Проблемът е в това.
>> Така в една стая на п CS50 учениците, какъв е вероятността, че най-малко
двама студенти в стаята имат същия рожден ден?
Така че има какво. няколко Hund -
200, 300 хора тук и няколко сто хора у дома днес.
Така че, ако искате да се питаме какво е вероятността от двама души
В тази стая има същия рожден ден, можем да разберем това.
И аз твърдя, всъщност има два хора със същия рожден ден.
>> Например, има ли някой има рожден ден днес?
Вчера?
Утре?
Добре, така че тя се чувства като аз ще да трябва да го правиш 363 или така по-
пъти, за да разбера всъщност ако имаме сблъсък.
Или можем да го направим математически а не досадно
прави това.
И предложа следното.
>> Така че аз предлагам да може да се моделира вероятността от двама души, имащи
същия рожден ден като вероятността от 1 минус вероятността от никой като
същия рожден ден.
Така че да се получи това, и това е само луксозен начин на писане на тази, за
първият човек в стаята, той или тя може да има всяка една от възможните
рождени дни поема 365 дни в годината, с извинения към хората с
на 29 февруари рожден ден.
>> Така че първият човек в тази зала е безплатно да има произволен брой рождени дни
от 365 възможности, така че ние ще го направя 365, разделена на 365,
който е един.
Следващият човек в стаята, ако целта е да се избегне сблъсък, може само
има свой рожден ден за това как много различни възможни дни?
364.
Така че втори мандат в този израз е по същество това, че математиката за нас
като се извади от един възможен ден.
И след това на следващия ден, на следващия ден следващия ден до общия брой
на хората в залата.
>> И ако след това помисли, какво тогава е вероятността не на всеки да има
уникални рождени дни, но отново един минус че, това, което получаваме, е израз
че може много fancifully изглежда така.
Но това е по-интересно да погледнете визуално.
Това е диаграма, където по оста х е на броя на хората в помещението,
броя на рождени дни.
На ординатата е вероятността от евентуален сблъсък, двама души
със същия рожден ден.
>> И на храна за вкъщи от тази крива е че веднага след като стигнете до искал 40
студенти, ти си на 90% вероятност combinatorically на две
или повече души имат същия рожден ден.
И след като стигна до 58 души като това е почти 100% от шанс на две
хората в залата ще имат същия рожден ден, макар няма
365 или 366 възможни кофи, и само 58 души в залата.
Просто статистически е по-вероятно да получите сблъсъци, които в краткосрочен
мотивира тази дискусия.
Че дори да получите фантазия тук, и започна като тези вериги, все още сме
ще има сблъсъци.
>> Така че това повдига въпроса, каква е разходите за правене на вмъквания и заличавания
в структурата на данните, подобен на този?
Ами нека да предложи -
и да се върна към екрана над тук - ако сме п елементи в
списък, така че ако се опитваме да вмъкнете п елементи, а ние имаме
Колко общо кофи?
Да речем, 31 общо кофи в случай на рождени дни.
Каква е максималната дължина на един на тези вериги потенциално?
>> Ако отново има 31 възможни Рождени дни в даден месец.
И ние просто бучки всички -
всъщност това е един глупав пример.
Да го направим 26 вместо.
Така че, ако действително има хора, чиито имена Започнете с по Z, като по този начин
26 възможности за нас.
И ние сме с помощта на структурата на данните като на един току-що видяхме, като имаме
масив от указатели, всеки от които точки в свързан списък, когато
Първият списък е всеки с името Alice.
Вторият списък е всеки с име, започващо с, като се започва
с В, и така нататък.
>> Какво е най-вероятно дължината на всеки от тези списъци, ако приемем, хубава чиста
разпределение на имена от А до Z в цялата структура на данните?
Има н хора в структурата на данните разделена на 26, ако са добре
разпределят в течение на целия структурата на данните.
Така дължината на всеки един от тези вериги е М, разделена на 26.
Но в голяма нотация O, какво е това?
Какво е това наистина?
Така че това е наистина само N, нали?
Защото казахме в миналото, уф, че сте се разделят с 26.
Да, в действителност то е по-бързо.
Но на теория, това не е фундаментално всичко, което по-бързо.
>> Така че ние не изглежда да е чак толкова много по-близо до тази Светия Граал.
В действителност, това е само линейно време.
По дяволите, в този момент, защо да не правим просто използвайте един огромен свързан списък?
Защо не просто използвайте един огромен масив за съхранение на имената на
всички в залата?
Е, има ли още нещо непреодолими за хеш-таблица?
Има ли все още нещо завладяващо за структурата на данните
който изглежда така?
Това.
>> Студентът: [недоловим].
>> SPEAKER 1: Да, и отново, ако това е просто линеен алгоритъм време, и
линейното време структурата на данните, защо да не правя просто съхранява името на всички в един голям
масив, или в голям свързан списък?
И престани да направи CS така много по-трудно , отколкото трябва да бъде?
Какво е убедителна за това, дори въпреки че аз го надраска?
>> Студентът: [недоловим].
>> SPEAKER 1: вмъквания, не са?
Expensive вече.
Така вмъквания потенциално биха могли все още бъде постоянна време, дори и ако вашите данни
структура изглежда така, множество указатели, всяка от които е насочена към
потенциално свързан списък.
Как може да се постигне постоянен време вмъкване на имена?
Придържайте се в предната част, нали?
>> Ако жертваме гол дизайн от по-рано, когато искаме да запазим
името на всички, например, подредени, или всички номера на сцената подредени,
Предполагам, че имаме несортиран свързан списък.
Тя само ни струва една или две стъпки, като в случай на Бен и Brian
по-рано, за да вмъкнете елемент в началото на списъка.
Така че, ако ние не се грижи за сортиране на всички на имена, започващи с А или всички
имената, започващи с B, все още можем да постигане на постоянно поставяне време.
Сега гледам Алис или Боб или всяко име по-общ план е все още какво?
Това е голям О п разделена на 26, в идеален случай, когато всички са еднакво
разпределени, където има най-много на А като има Z, която е вероятно
нереалистично.
Но това все още е линейна.
>> Но тук, ние се връщаме към точка от асимптотичната нотация е
теоретично вярно.
Но в реалния свят, ако се твърди, че моята програма може да направи нещо 26 пъти
по-бързо от твоя, чиято програма отиваш предпочиташе да използвате?
Yours или мина, която е 26 пъти по-бързо?
Реално, на лицето, чиято е 26 пъти по-бързо, дори ако теоретично
алгоритмите ни тече в една и съща асимптотичната времето за работа.
>> Нека да предложи различен разтвор напълно.
И ако това не ви оставят без дъх, Че ние сме извън структурите от данни.
Така че това е Trie -
Що за глупаво име.
Тя идва от извличането на данни, а думата е написан Trie, т-р-е-е, защото на
Разбира извличане звучи като Trie.
Но това е история на думата Trie.
>> Така Trie е наистина някаква дърво, и тя също е игра на тази дума.
И въпреки че не мога да си го видите с тази визуализация, а Trie е
дърво структурира, като родословно дърво с един прародител в горната и много
на внуци и правнуци като оставя на дъното.
Но всеки възел в Trie е масив.
И това е в масив - и нека свръхопростяването за момент - това е
масив, в този случай, с размер 26, когато всеки възел отново е масив от размера
26, когато нулевия елемент с това, че масив представлява, а последният
елемент за всяка такава масив представлява Z.
>> Така че аз предлагам, а след това, че тези данни структура, известна като Trie, може да бъде
използва и за съхраняване на думи.
Ние видяхме преди малко, как бихме могли да се съхранява думи, или в този случай имената и ние
видяхме по-рано как ние може да съхранява числа, но ако ние се фокусираме върху имената или низове
тук, забележете, което е интересно.
Аз твърдя, че името Максуел е вътрешността на структурата на данните.
Къде виждате Maxwell?
>> Студентът: [недоловим].
>> SPEAKER 1: От лявата.
Така че това, което е интересно с тези данни структура е по-скоро от магазин на
низ M-A-X-W-E-L-L наклонена черта нулеви, цялото Последователно, какво да го правим
следи.
Ако това е Trie като структура на данните, всеки един от които възли отново е масив,
и искате да съхранявате Maxwell, първо индекс и така основата на възела, така че
да се каже, най-горната възел, в населено място M, нали, така че
приблизително в средата.
И след това от там, следват показалеца на дете възли, така да се каже.
Така че, в смисъл, родословно дърво, го следват надолу.
И това да ви доведе до друг възел в ляво там, който е
просто друг масив.
>> И след това, ако искате да съхранявате Maxwell, ли, че показалецът, който представлява
A, който е този тук.
След това можете да преминете към следващото възел.
И забележете - това е защо на картината малко измамна -
този възел изглежда супер малка.
Но правото на това е Y и Z. Това е просто авторът е пресечен на
картината, така че всъщност виждаме нещата.
В противен случай тази снимка ще бъде изключително широк.
Така че сега вие индекс в населено място X, а след това W, E Тогава, след това L, тогава L. Тогава какъв е
това любопитство?
>> Е, ако ние използваме този вид на новия предприемат за съхранение на низ в
структурата на данните, все още трябва да същество отмятате в данните
структура, която дума свършва тук.
С други думи, всеки един от тези възли по някакъв начин трябва да се помни, че ние
всъщност след всички тези указатели и се оставя малко
троха хляб в долната тук на тази структура, за да покаже, M-A-X-W-E-L-L е
Всъщност в тази структура от данни.
>> Така че бихме могли да направите това, както следва.
Всеки от възлите в картината ние просто трион има един, масив с размер 27.
И това е вече 27, защото в БКП определени шест, ние всъщност ще ви дам един апостроф,
така че ние можем да имаме имена като O'Reilly и други с апострофи.
Но една и съща идея.
Всеки един от тези елементи в масиви сочи към структура
възел, така че само един възел.
Така че това е много напомня на нашата свързан списък.
>> И след това имам Boolean, която аз ще обадете дума, която е просто ще бъде
вярно, ако една дума завърши този възел в дървото.
Той ефективно представлява малко триъгълник видяхме преди малко.
Така че, ако думата завършва на този възел в дървото, така че областта думата ще бъде вярно,
която е концептуално отмятане, или ние рисувате този триъгълник, да има
е дума тук.
>> Така че това е Trie.
И сега въпросът е, какво е неговото време на работа?
Дали е голям O на п?
Може ли нещо друго?
Е, ако сте п имена в тези данни структура, Максуел е само един от
тях, какво е времето за работа на поставяте или намиране на Максуел?
Какво е времето за работа вмъкване на Максуел?
Ако има п други имена вече в таблицата?
Да?
>> Студентът: [недоловим].
>> SPEAKER 1: Да, това е дължината на име, нали?
Така M-а-х-w-е-л-л така тя се чувства като това алгоритъм е голяма O на седем.
Сега, разбира се, името ще варират по дължина.
Може би това е кратко име.
Може би това е по-дълго име.
Но това, което е ключът тук е, че това е постоянно число.
И може би това не е наистина константа, но Бог, ако реалистично, в
речник, вероятно има някаква граница от броя на буквите в
лице име в дадена страна.
>> И така, можем да предположим, че стойност е константа.
Аз не знам какво е то.
Това е може би по-голям от ние смятаме, че е така.
Защото винаги има някой ъгъл случай с един луд дълго име.
Така че, нека го наречем к, но тя все още е постоянна вероятно, защото всеки
име в света, най-малко в определена страна, е, че дължината или
по-кратък, така че това е постоянна.
Но когато съм казал нещо е голям O на постоянна стойност, какво е това
Наистина еквивалентни?
Това е наистина едно и също нещо както казва константно време.
>> Сега сме вид измама, нали?
Ние сме вид привличане някои теория тук, за да се каже, че добре, за да е на к
наистина просто порядъка на една, и това е константно време.
Но това наистина е така.
Тъй като ключовата поглед тук е, че ако сме п имена вече в тази
структурата на данните, и ние вложка Maxwell, е количеството време, което ни води до
вмъкнете Maxwell е засегнато от колко други хора
са в структурата на данните?
Не изглежда да бъде.
Ако имах един милиард повече елементи на настоящата Trie, а след това поставете Максуел, е
той е засегнато?
Не.
И това е, за разлика от някои от ден на данни структури, които сме виждали до този момент, когато
времето за работа на вашия алгоритъм е напълно независимо от това колко
неща е или не е вече с това, че структурата на данните.
>> И така с това дава сега е възможност за р набор шест, което ще
отново включва прилагане свой собствен проверка на правопис, четене в 150000
думи, как най-добре да се съхранява, че не е задължително очевидна.
И въпреки, че съм поставила за цел да намери Светия Граал, не искам
твърдят, че е Trie.
В действителност, хеш таблица може много добре да се окаже много по-ефективно.
Но това са само -
това е само една от дизайнерските решения ще трябва да се направи.
>> Но в затваряне нека вземем 50 или така секунди, за да вземе един поглед на това, което се намира
напред следващата седмица и след това ние прехода от този команден ред
свят, ако C програми за неща Мрежата основава и езици като PHP и
JavaScript и самият интернет, като протоколите HTTP, до която сте
приема за даденост за година сега, и печатен почти всеки
ден, може би, или наблюдавани.
И ние ще започнем да Обелете слоеве на това, което е в интернет.
И това, което е кодът, който лежи в основата на днешните средства.
Така 50 секунди на тази закачка тук.
Аз ви давам Warriors на мрежата.
>> [VIDEO PLAYBACK]
>> -Той дойде с послание.
С протокол всичките свои.
Той дойде в един свят на жестоки защитни стени, незаинтересовани рутери, и опасностите, далеч
по-лошо от смъртта.
Той е бърз.
Той е силен.
Той е TCPIP.
И той има адреса си.
Warriors на мрежата.
>> [END възпроизвеждане на видео]
>> SPEAKER 1: Това е начина, по интернет работят от следващата седмица.