SPEAKER 1: Добре, така че това е CS50 Това е краят на пет седмици. И припомни, че за последен път сме Започнах да търся в красиви данните структури, които са започнали да се реши проблеми, които започнаха да се въведат нови проблеми, но ключът към това беше от резби, че ние Започнах да правя от възел до възел. Така че това, разбира се, с единична свързан списък. И от поединично свързани, Искам да кажа, че има само един резба между всеки от тези възли. Оказва се, можете да го направите по-красиви неща като двойно свързани списъци с което имате стрела ще и в двете посоки, което може да помогне с някои ефективност. Но това реши проблема? Какъв проблем е това реши? Защо ни е грижа в понеделник? Защо, на теория, е ни е грижа в понеделник? Какво прави? 

АУДИТОРИЯ: Ние динамично да го преоразмерите. 

SPEAKER 1: OK, за да можем да динамично преоразмеряване. Браво и на двама ви. Така че можете да промените размера на това динамично структура на данните, като има предвид, масив, Спомнете си, вие трябва да знаете априори колко място искате и ако имате нужда от малко по- космоса, вие сте вид на късмет. Трябва да се създаде изцяло нов масив. Трябва да се преместите всичките си данни от един на друг, в крайна сметка освободи стария масив ако можеш, и след това да продължи. Което просто се чувства много скъпо и много неефективно, а всъщност тя може да бъде. Но това не е всичко добро. Ние плащаме на цената, това, което беше едно от по-очевидните цени ние плащат с помощта на свързан списък? 

АУДИТОРИЯ: Трябва да използваме двойно пространство за всеки един. SPEAKER 1: Да, така че ние трябва най-малко два пъти по-голямо пространство. В действителност, аз осъзнах, тази картина е дори малко подвеждащо, защото на CS50 IDE в много модерна компютри, указател или адрес не е в действителност четири байта. Това е много често това осем дни байта, които означава най-долната правоъгълници там в реалност са вид два пъти по- голям, колкото това, което съм, изготвен, което означава, че използвате три пъти по- толкова място, колкото можем да имаме друго. Сега в същото време, ние сме още говорим байта, нали? Ние не говорим задължително мегабайта или гигабайта, освен ако тези данни структури получават големи. 

И така, днес ние започваме да се разгледа как можем да проучи данните по-ефективно, ако в Всъщност данните получава по-голяма. Но нека се опитаме да канонизира операциите първите което можете да направите за тях видове структури от данни. Така че нещо като свързани списък по принцип подкрепя операции искали да изтриете, вмъкнете, и търсене. И това, което мога да кажа от това? Това просто означава, че обикновено, ако хората използват свързан списък, те или някой друг е изпълнила функции като изтриване, вмъкване, и търсене, така че можете да всъщност направи нещо полезна със структурата на данните. Така че нека да хвърлим един бърз поглед как бихме могли да приложат някои код за свързан списък, както следва. 

Така че това е само част C код, дори не е пълна програма че аз наистина бързо разбита. Това не е онлайн в разпределението код, защото той всъщност няма да се изпълнява. Но забележете аз току-що с коментар каза, точка точка точка, има нещо там, точка, точка точка, нещо там. И нека просто погледнете какви са сочни части. Така на третия ред Припомняме, че това сега е Ние предложихме за обявяване на последния възел време, един от тези правоъгълни обекти. Той разполага с инт, че ние ще се обадя на N, но можем да го наречем нещо, и след това звезда структура на възел, наречен по-нататък. И само за да бъде ясно, че втората линия, по линия на шест, какво е това? Какво е да го прави за нас? Тъй като това със сигурност изглежда по- загадъчен, отколкото обичайните ни променливи. 

АУДИТОРИЯ: Това го прави движат над милион. 

SPEAKER 1: Това го прави движат над милион. И за да бъдем по-точни, тя ще се съхранява на адрес на възела, който е трябвало да бъде семантично до него, нали? Така че това няма да задължително се движи нищо. Това е просто ще съхраняване на стойност, която е ще бъде на адреса от друга възлова точка, и затова сме казвали структура на възел звезда, звездата, обозначаващ указател или адрес. ОК, така че сега, ако приемем, че имаме това N достъпна за нас, и нека Предполагам, че някой друг има Създава цял куп числа в свързан списък. И това е свързан списък , посочи от някакъв момент променлива, наречена списък, който е преминал тук като параметър, как мога да отида за съответствие 14 изпълнителните търсене? С други думи, ако аз съм прилагане функция, чиято цел в живота е да се вземе едно цяло число, а след това започваща на свързан списък, че е указател към свързан списък. Подобно на първия, който мисля, че David беше нашият доброволец в понеделник, Той сочеше целият свързан списък, това е така, сякаш сме минаваща David в нашия аргумент, както тук. Как да отида за преминаващи този списък? Е, оказва се, че въпреки че указатели са сравнително нови сега за нас, можем да направим това относително прямо. 

Отивам да вървим напред и да Декларирам временна променлива, която по условие е просто ще да се нарича указател, или PTR, но бихте могли да го наречем всичко, което искаш. И аз отивам да се инициализира да началото на списъка. Така че можете да вид мислите за това като мен учителят на другия ден, вид сочеше някого сред нашите хора като доброволци. Така че аз съм временна променлива, която е Просто посочи към едно и също нещо че нашата случайно име доброволец Давид също се посочва. Сега, докато показалеца е не нула, защото изземване че нищожна е някакъв специален часовой стойност разграничава на края на списъка така че, докато аз не съм сочейки земята като последната ни доброволец е, да вървим напред и направете следното. Ако pointer-- и сега аз искам вид да направи това, което направихме със студента structure-- ако показалеца точка до equals---скоро, ако показалеца точка N е равно на равно на променлива N, на аргумент, който е бил приет през, След това искам да отида напред и да кажа върнете вярно. Аз не съм намерил на номер N вътре един от възлите на моя свързан списък. Но точката вече не работи в този контекст, защото показалеца, PTR, е Наистина указател, на един адрес, ние всъщност може чудесно използвате най-накрая парче синтаксис този вид марки интуитивно усещане и действително използвате стрелка тук, което означава, отидете от този адрес до цяло число има вътре. Така че това е много подобен на дух на оператора на точка, но тъй като показалка не е указател а не самата структура на действителната, ние просто използвайте стрелката. 

Така че, ако текущия възел, че Аз, временна променлива, съм сочеше Не е N, какво искам да направя? Е, с моите хора доброволци че имахме тук онзи ден, ако първият ми от човека, не е тази, която искам, а може би и на втория човекът не е този, аз искам, а третият, I трябва да се запази физическо преместване. Подобно как мога да се оттегли през списък? Когато трябваше масив вас, Просто ми хареса I плюс плюс. Но в този случай е достатъчно да се направя показалеца, получава, показалеца, следващата. С други думи, в следващото поле е като всички останали ръцете на че нашите хора доброволци в понеделник използваше да отбележа в някакъв друг възел. Това бяха следващите техните съседи. 

Така че, ако искам да преминете през този списък, Не мога просто да направя аз, плюс плюс вече, Аз трябва да кажа, вместо I, показалеца, ще да се изравни каквото следващото поле е, следващото поле се, следващото поле е, след всички тези оставили ръцете че имахме на сцената посочващо някои следващите стойности. И ако аз се измъкне сам че цялата итерация, и накрая, аз удари нула не се налага намерено N все пак, аз просто се върнете фалшива. Така че отново, всичко, което правим тук, по картината преди малко, започва от сочейки началото на списъка се предполага. И тогава аз се провери, е стойността Търся равен на девет? Ако е така, аз се върнете вярно и аз съм свършен. Ако не, да актуализирам моята ръка, AKA показалеца, за да посоча на място при следващата стрелка, а След това на мястото на следващия стрелата, и на следващия. Аз съм просто се разхождах из този масив. 

Така че отново, на кого му пука? Подобно на това, което е тази съставка за? Е, Припомняме, че ние въведохме понятието за комин, който е тип абстрактен данни, доколкото това е не нещо C, това не е нещо CS50, това е една абстрактна идея, тази идея за подреждане неща на върха на един друг които могат да бъдат приложени в гроздове с различни начини. И един начин ние предложихме беше с масив, или с свързан списък. И се оказва, че е канонично, а стак поддържа най-малко две операции. И бръмча думи са бута, да бутнете нещо върху купчината, като нова тава в зала за хранене, или поп, което означава да се премахне най-горния тава от комина в трапезарията антре, а след това може би някои други операции, както добре. Е, как може да определим структурата че ние сме вече призова комин? 

Е, ние имаме всичко на изискваните синтаксис, с които разполагаме в C. казвам, ми даде определение тип една структура на вътрешната страна на комин, Отивам да се каже, е масив, на цял куп номера и след това размер. Така че, с други думи, ако искам да приложи това в кода, нека отида и просто вид изготвят какво казва. Така че това казва, дайте ми структура, която има масив, и аз не знам какво е капацитет, това е очевидно някои постоянно, че съм определено на друго място, и това е добре. Но предполагам, че това е само една, две, три, четири, пет. Така капацитет е 5. Този елемент вътре в моето структура ще се нарича номера. И тогава ми е такъв друга променлива очевидно нарича размер, който първоначално Отивам да се предвиди се инициализира на нула. Ако няма нищо в стека, размерът е нула, и това е боклук стойности в цифри. Нямам представа какво е там, просто все още. 

Така че, ако искам да бутнете нещо, върху купчината, Предполагам, че аз наричам функция тласък, и Казвам бутнете 50, като броят на 50 г. където бихте предложили Аз го привлече в този масив? Има пет различни възможни отговори. Къде искаш да прокара броя 50? Ако целта тук, отново, обадете се на функция да бута, да премине в спор на 50, къде мога да го сложите? Пет possible-- 20% шанс на познае правилно. Да? 

АУДИТОРИЯ: Far полето. 

SPEAKER 1: Far полето. Сега има 25% шанс на познае правилно. Така че всъщност ще се оправи. По конвенция, аз ще кажа с масив, ние обикновено ще започне в ляво, но ние със сигурност може да започне в правото. Така че спойлера тук би било съм Вероятно ще го привлече в ляво, точно като в нормален масив, където Започвам да отида наляво надясно. Но ако можете да флип аритметиката, глоба. Това просто не е конвенционална. OK, аз трябва да се направи една повече промяна все пак. Сега, когато съм бутна нещо върху комина, какво следва? 

Добре, аз трябва да увеличите размера. Така че нека да вървим напред и просто актуализира това, което е нула. И вместо сега, аз ще съм да се сложи в стойността една. И сега предполагам, че бутнете друг номер върху купчината, като 51. Е, аз трябва да се направи една по- промяна, която е до размера на две. И тогава аз предполагам, натиснете още един номер върху купчината като 61, Сега имам нужда да се актуализира размера още един време, и да получите стойността 3 като размера. И сега предполагам, аз наричам поп. Сега поп, по силата на споразумение, не взема един аргумент. С стак, той като цяло точка на тава метафората е, че не е нужно усмотрение да отиде получи, че тава, всичко, което може да направи се появи най-горната един от стека, само защото. Това е, което тази структура от данни прави. 

Така че по тази логика, ако аз казват поп, това, което идва на разстояние? Така 61. Така че това, което наистина е на компютъра ще направим в памет? Какво ми код трябва да направя? Какво бихте предложили сменяме на екрана? Какво трябва да се промени? Съжаляваме? Така че ние се отървете от 61. Така че определено мога да направя това. И мога да се отърва от 61. И тогава какво друго промяна трябва да се случи? Размер вероятно трябва да се върнем към две. И така, това е добре. Но почакайте, размер преди малко беше три. Нека просто да се направи бърза проверка здрав разум. Откъде знаем, че сме искаше да се отърве от 61? Тъй като ние сме се пръкват. И така, аз имам този втори размер собственост. 

Чакай малко, аз съм мисли обратно към две седмици когато ние започнахме да говорим за масиви, когато това е място нула, това е една локация, това е място две, това е място три, четири, Той прилича на връзка между размера и елемента, че искам да се премахне от масива изглежда да бъде само това, което? Размер минус едно. И така, това е начина, като хора ние знаем, 61 е на първо място. Как компютърът ще знаеш? Когато кода си, когато е най-вероятно искам да направя размер минус едно, така три минус един е две, и че означава, че ние искаме да се отървем от 61. И то наистина можем да актуализираме размера, така че размер предприятието отива от три до само две. И само за да бъде педантичен, аз отивам да предложи, че аз съм направил, нали? Можете предложен интуитивно правилно, че трябва да се отървете от 61. Но има не съм вид нещо се отървали от 61? Аз бях забравил ефективно че това е действително има. И мисля, обратно към PSET4, ако сте чели статията за съдебна медицина, в PDF че имахме момчета четат, или сте ще прочетете тази седмица за PSET4. Припомнете си, че това всъщност е уместен за цялата идея за компютърни лица. Какво компютър обикновено се прави, е тя просто забравя, когато нещо е, но тя не ида и като опитайте се да го задрасквам или пренебрегване тези битове с нули и единици или някакъв друг произволен модел освен ако не си го направи нарочно. Така че интуицията е Добре, да се отървете от 61. Но в действителност, ние не трябва да се притеснява. Ние просто трябва да забравяме, че тя е налице, като промените нашия размер. 

Сега има проблем с този стак. Ако аз държа бутане неща върху комина, какво е очевидно няма да се случи само за няколко минути път? Отиваме да свършат на пространството. И какво ще правим? Ние сме вид прецакани. Това изпълнение не позволявайте ни преоразмеряване на масива, тъй като се използва този синтаксис, ако мисля, обратно на две седмица, след като веднъж сте декларирани размера на масив, не сме виждали механизъм все още къде можете да промените размера на масива. И наистина C не разполага с този елемент. Ако кажете, дайте ми пет Nths, ги наричат ​​номера, това е всичко, ти започваш да го получи. Така че ние правим сега, считано от понеделник, имат способността да експресират разтвор все пак, ние просто трябва да се ощипвам определението на нашия купчина да не бъдат някои трудно кодирани масив, но само за да се съхранява на адрес. 

Сега защо е това? Сега ние просто трябва да се чувстват удобно, факта, че когато програмата ми изтече, Аз вероятно ще Трябва да попитам човека, колко числа искаш да съхранявате? Така че на входа трябва да дойде от някъде. Но след като знам, че номер, тогава мога само използвате това, което функционира до получаване на ми парче от паметта? Мога да използвам изчистване. И мога да кажа, всеки брой на байта Искам обратно за тези Nths. И всичко, което трябва да се съхранява в броя променлива тук вътре в тази структура на трябва да бъде това, което? Какво всъщност отива в номера в този сценарий? Да, указател към първия байт, че парче от паметта, или по-специално, на адреса на първото от тези байтове. Няма значение дали това е един байтове или един милиард байта, Просто трябва да се грижи за първото. Защото това, което изчистване гаранции и моите операционната система гаранции, е, че парчето памет I получите, то се случва да бъдат съседни. Там няма да бъде пропуски. Така че, ако съм поискал 50 байта или 1000 байта, те всички ще бъдат да се върна обратно към гърба. И доколкото си спомням колко е голям, колко много ми поиска, всичко, което трябва да знаете е първият такъв адрес. 

Така че сега ние имаме възможността в код. Макар, че това ще ни отведе повече време да напиша това нагоре, Сега можем да се преразпределят, че паметта от Просто съхраняване на друг адрес там ако искаме по-голяма или дори по-малко парче от паметта. Така че тук, за да пласирам. Сега ние се динамика. Все още имаме contiguousness съм претендира. Защото изчистване ще ни даде свързано парче от паметта. Но това ще бъде болка в врата за нас, програмист, действително да се кодират до. Това е просто повече работа. Трябва код близко до това, което бях чука навън само преди миг. Много изпълним, но добавя сложност. И така времето разработчик, програмист времето е още един ресурс че ние може да се наложи да прекарат известно време, за да получите нови функции. И след това, разбира се, има опашка. Ние няма да влезем в този един в много подробности. Но това е много подобен по дух. Можех да приложат на опашка, и съответните си операции, Enqueue или dequeue, като добавяте или премахвате, това е просто любител начин да го казвам, Enqueue или dequeue, както следва. Аз просто мога да се даде структура на че отново има масив редица му, който отново е с размер, но защо аз сега трябва да следите отпред на опашката? Аз не трябва да знаете предната част на моя стак. Е, ако аз отново за queue-- нека просто трудно го код като имащи като петте числа в потенциално тук. Така че това е нула, едно, две, три, четири. Това ще бъде наречени отново номера. И това ще се нарича размер. 

Защо това не е достатъчно, да има само размер? Ами, нека да прокара тези същите номера на. Така че аз съм pushed-- enqueued, или бутани. Сега ще Enqueue 50, и след това 51, и след това 61, и точка, точка точка. Така че това е Enqueue. I enqueued 50, после 51, после 61. И това изглежда идентично да стак до този момент, с изключение на I е нужно да се направи една промяна. Имам нужда да се актуализира този размер, така че аз отивам от нула до един до 02:58 сега. Как мога да dequeue? Какво се случва с dequeue? Кой трябва да влезе в този списък първи ако това е линията на Apple Store? Така 50. Така че това е вид сложни и този път. Като има предвид, за последен път, че е супер лесно просто да направите размер минус едно, Да стигна до края на моя масив ефективно където цифрите са, тя премахва 61. Но аз не искам да се премахне 61. Искам да се възползвам от 50, които беше там в 5:00 AM да се подредят за Новият iPhone или какво ли още не. И така, за да се отървете от 50, I Не може просто да направите това, нали? Мога да зачеркнете 50. Но ние просто си казахме не е нужно да бъде толкова анален че да задрасквам или скриване на данните. Ние можем просто да забравите къде е. 

Но ако си променя размера на предприятието, за да две, е това достатъчно информация да знаят какво се случва в моята опашка? Не съвсем. Както е моя размер две, но когато не започва опашката, особено ако аз все още имам Същите тези числа в паметта. 50, 51, 61. Така че аз трябва да се помни, Сега, когато отпред е. И така, както аз предложих нагоре там, ще сме просто нарича N-та отпред, чиято първоначална стойност трябва да е какво? Нула, само началото на списъка. Но сега, в допълнение към намаляващи размера, ние просто нарастване на фронта. Сега тук е друг проблем. Така че след като аз да тръгвам. Да предположим, че това е броят на като 121, 124, и след това, по дяволите, Аз съм на пространството. Но почакайте, аз не съм. Така че в този момент в историята, Предполагам, че размерът е едно, две, три, четири, така че предполагам, че размер е четири, отпред е един, 51 е така отпред. Искам да сложа друг номер тук, но, по дяволите, аз съм на пространството. Но аз не съм много, нали? Къде мога да се въведе някакъв допълнителна стойност, като 171? Да, можех просто вид се върна там, нали? И тогава зачеркнете 50, или Просто го презапишете с 171. И ако сте се чудех защо нашите номера дойдоха толкова произволни, те обикновено се вземат компютър научни курсове в Харвард след CS50. Но това беше една добра оптимизация, защото сега аз не губя пространство. Аз все още трябва да се помни колко е голяма тази нещо е общо. Това е пет общо. Защото аз не искам да се започнете презаписване 51. Така че сега аз съм все още на пространството, така същия проблем, както преди. Но можете да видите как сега в кода си, най-вероятно трябва да напиша малко по- сложност, за да се случи това. И всъщност, какво оператор в C-вероятно ви позволява можете да направите това по магически кръглостта? Да оператора на модул, знака за процент. Така че това, което е нещо готино за опашка, въпреки че ние продължаваме рисуване масиви тъй като тези като прави линии, ако вид мисля за това като извита наоколо като кръг, след това просто интуитивно го вид работи с умствени Мисля, че е малко по-чисто. Вие все още ще трябва да въведат че мисловен модел в код. Така че не е толкова трудно, в крайна сметка, да се приложат, но ние все още губи size-- по-скоро, способност да преоразмерите, освен ако не правим това. 

Ние трябва да се отървете от масива, ние да го замени с единен показалеца, и след това някъде в моя код Имам а това, което наричаме функционира действително да се създаде масива, наречени номера? Изчистване, или някаква подобна функция, точно. Всякакви въпроси за стекове или опашки. Да? Добър въпрос. Какво по модул ще можете да използвате тук. Така обикновено, когато се използва Министерството на отбраната, ще го направя с размера на Цялата структура на данните. Така че нещо като пет или капацитет, ако това е постоянен, вероятно е замесен. Но просто правиш по модул пет най-вероятно не е достатъчно, защото ние трябва да знаят, че ние правим обгърне тук или тук или тук. Значи вие сте най-вероятно също Ще искаме да включим размера на нещо, или предната променлива, както добре. Така че това е просто този сравнително прост аритметичен израз, но по модул ще бъде ключовата съставка. 

Така късометражен филм, ако щете. Една анимация, че някои хора в друг университет взети заедно, че ние сме адаптиран за тази дискусия. Тя включва изучаването на Джак факти за опашки и статистики. 

FILM: Имало едно време, имаше един човек на име Джак. Когато става дума за вземане на приятели, Джак не е имал цака. Така че Джак отиде да говори с Най-популярният човек знаеше. Той отиде до Лу и попита: Какво да правя? Лу видя, че приятелят му Беше наистина в затруднено положение. Е, той започна, просто вижте колко сте облечени. Не имате някакви дрехи с различен поглед? Да, каза Джак. Убеден съм, че правя. Ела в къщата ми и Аз ще ви ги покажа. И те отидоха на разстояние до Джак. И Джак показа Lou кутията където държеше всичките си ризи, и панталоните си и чорапите му. Лу каза, виждам че имате всичките си дрехи в купчина. Защо не носят някаква други веднъж в известно време? 

Джак каза, добре, когато съм премахване на дрехи и чорапи, Аз ги изпере и постави ги далеч в наказателното поле. След това идва следващият сутрин и до I-хоп. Отида на полето и да получите дрехите ми на разстояние от върха. Lou бързо осъзнах проблемът с Джак. Държеше дрехи, CD-та, и книги в стека. Когато той посегна нещо за четене или за носене, той ще избере най-горния книгата или бельото. Тогава, когато той е направил, той ще го постави обратно. Обратно, че ще отида, на върха на стека. Знам, че решението, каза триумфално Loud. Трябва да се научите да започнете да използвате опашка. Лу взе дрехите на Джак и ги затвори в килера. И когато той е изпразнен на наказателното поле, той просто го хвърли. 

Тогава той каза, сега Джак, в края на деня, сложи дрехите си в ляво когато ги направи. Тогава утре сутринта, когато виж на слънцето, да получите вашите дрехи отдясно, от края на линията. Не виждаш ли? каза Лу. Тя ще бъде толкова хубаво. Ще нося всичко наведнъж преди да носят нещо два пъти. И с всичко в опашки в неговата тоалетна и срок, Джак започна да се чувства съвсем сигурен в себе си. Всички благодарение на Лу и прекрасно си опашка. SPEAKER 1: Добре, това е възхитителен. Така че това, което е наистина се случва за под предния капак в момента? Това имаме указатели, че имаме изчистване, че имаме възможността да се създават парчета от паметта за себе си динамично. Така че това е една ние картина зърнал онзи ден. Ние наистина не спирам върху него, но тази снимка продължава вече под качулката от седмици. И така, това означава, просто правоъгълник, който установили сме, паметта на компютъра ви. И може би вашия компютър, или CS50 ID, има гигабайт памет или RAM или два гигабайта или четири. Това няма значение. Вашата операционна система Windows или Mac OS или Linux, същество дава възможност на програма да се мисли, че има достъп за целостта на паметта на компютъра, въпреки че може да се работи няколко програми наведнъж. Така че в действителност, че наистина не работи. Но това е вид илюзия дава на всичките си програми. Така че, ако има две участия на RAM, това е как компютърът може да мисли за това. 

Сега случайно, една от тях неща, един от тези сегменти на паметта, се нарича комин. И наистина всяко време до този момент в писмен код че сте се нарича функция, например основната. Припомнете си, че всеки път, когато съм памет, изготвен на компютъра, Аз винаги се направи нещо половината от правоъгълник тук и не се притеснява да говори за това, което е горе. Защото, когато основната се нарича, аз твърдя, че получавате това късче памет че слиза тук. И ако основната функция, наречена като суап, и суап отива тук. И се оказва, че е къде е завършил. На нещо, наречено комин вътре в паметта на компютъра ви. Сега в края на деня, това е просто обръщение. Това е като байт нула, байт, байт 2 млрд. Но ако си мислиш за него като този правоъгълен обект, всичко, което правим всеки време, което наричаме функция е наслояване ново парче от паметта. Ние даваме тази функция парче на собствената си памет, за да се работи. 

И припомни, че сега това е важно. Защото, ако ние нямаме нещо като суап и две локални променливи като А и Б и ние променяме тези ценности от едно и две до два и един, изземване че когато се връща за размяна, това е така, сякаш този отрязък от системната памет е просто изчезна. В действителност, тя все още е има forensically. И нещо още е действително има. Но концептуално, това е като Въпреки че е напълно изчезнала. И така основният не знае нито една от дейностите че се извършва в тази замяна функция, освен ако не е действително отражение в тези, аргументи от страна на показалеца или чрез препратка. Сега, основното решение на този проблем със суап преминава неща в по адрес. Но се оказва, също, което е продължава вече над тази част на правоъгълника през цялото това време е Все още има повече памет до там. И когато динамично достатъчно памет, независимо дали е вътре в GetString, които ние сме били прави за вас в CS50 библиотека, или, ако вие обадете изчистване и попитайте операционната система за парче памет, тя не идва от комина. Тя идва от друго място в паметта на компютъра си това се нарича купчината. И това не е по-различно. Това е същата RAM. Това е същата памет. Това е просто RAM, че е до там вместо тук. 

И така, какво означава това? Е, ако компютърът ви има ограничен размер на паметта и топчето се разраства, така че да се каже, и на куп, според до тази стрелка, расте надолу. С други думи, всеки време ти се обадя изчистване, което се дава на парче на памет от по-горе, тогава може би малко по-ниско, а след малко по-ниска, всеки път, когато ти се обадя изчистване, купчината, това е използване, е вид расте, разраства все по-близо до това, което? Купчината. Така че прави това да изглежда като добра идея? Искам да кажа, когато това не е много ясно какво друго можеш да направиш, ако само ти имат ограничен количество памет. Но това със сигурност е лошо. Тези две стрели са по катастрофата Разбира се един за друг. 

И се оказва, че лош човек, хора, които са особено добре с програмиране, и се опитва да проникна в компютрите, може да използва това реалност. Всъщност, нека да разгледаме малко фрагмент. Така че това е пример можете да прочетете за по-подробно на Wikipedia. Ние ще ви насочи в статия, ако любопитен. Но има една атака като цяло известен като препълване на буфера, че е съществувала толкова дълго, колкото хората да има способността да се манипулират памет на компютъра, особено в C. Така че това е един много произволна програма, но нека си го чете от дъното нагоре. Main в argC Чар звезда argV. Така че това е една програма, която отнема командния ред аргументи. И всичко се основна очевидно е разговор функция, тя се обади F за простота. И тя преминава в какво? ArgV на един. Така той преминава в каквото и F думата е, че потребителят напечатани в командния ред, след като на Име на програмата на всички. Толкова много, като Цезар или Vigenere, които можете да си спомните, правиш с argV. 

Така че това, което е F? F отнема в низ като единствен аргумент, AKA Чар звезда, същата нещо, като низ. И тя се нарича произволно бар в този пример. И след това слага в 12, само по отношение на лаик, това, което е Чар в скоба 12 прави за нас? Какво е това? Разпределяне на паметта, по-специално 12 байта за 12 символа. Точно. И тогава на последния ред, разбърква се и се копие, най-вероятно не сте виждали. Това е низ копие функция, чиято цел в живота е да копирате втория си довод в първия си аргумент, но само до определен брой байтове. Така трети аргумент казва, колко байта да копирате? Дължината на бар, независимо от потребителя написали инча И съдържанието на Бар, че низ, са копирани в паметта посочи в C. 

Така че това изглежда някак глупаво, и това е. Това е измислен пример, но това е представителна на клас вектори на атака, начин на атаката програма. Всичко е наред и добро, ако потребителят видове в една дума, която е 11 символа или по-малко, плюс наклонената черта нула. Какво става, ако потребителят в повече от 11 или 12 или 20 или 50 знака? Каква е тази програма ще направите? Потенциално сек вина. Това ще сляпо да копирате всичко в бара до към дължината си, което е буквално всичко в бар, в адреса посочи C. Но C е само изпреварващо да се прилага като 12 байта. Но няма допълнителна проверка. Няма никакъв случай условия. Няма никаква проверка за грешки тук. 

И така, какво тази програма е ще направя, е просто сляпо копират едно нещо към другия. И така, ако се направи това като картина, ето просто частица от пространството на паметта. Така забележи в долната част, ние има променлива бара местно. Така че показалеца, че ще ходи да store-- по-скоро, че местната аргумент, че това е ще съхранявате бара низ. И тогава просто забележите над него в комин, защото всеки път, когато поиска за паметта на стека, тя отива малко по- над него живописно, известие, че ние имаме 12 байта там. В горния ляв тях е C скоба нула и правилният дъното е C скоба 11. Това е само как компютрите ще го изложи. Така че просто интуитивно, ако бар има повече от 12 знака в общо, включително наклонената черта нула, където е най- 12 или скоба C 12 ще отиде? Или по-скоро, когато е 12-ти характера или 13-ти характер, стотен характер ще да се окажете на снимката? Над или под? 

Точно така, защото въпреки че самата стека расте нагоре, след като веднъж сте сложи неща в него, за конструктивни причини, поставя паметта от горе до долу. Така че, ако имаш повече от 12 байта, започваш да се започне да се презапише бар. Сега това е бъг, но е наистина не е голяма работа. Но това е голяма работа, защото има повече неща се случва в паметта. Така че тук е как можем да сложи здравей, за да бъде ясно. Ако аз напечатани в здравей в командния ред. H-E-L-L-O наклонена черта нула, се озовава в рамките на тези 12 байта, и ние сме супер безопасни. Всичко е наред. Но ако объркате нещо вече, това е потенциално Ще се вмъкват в бар пространство. Но още по-лошо, тя се превръща от цялото това време, въпреки че никога не сме говорили за това, топчето се използва за други неща. Това не е просто локални променливи. 

C е на много ниско ниво на езика. И това нещо тайно използва стека също да се помни, когато Функцията се нарича, това, което адресът е на предходната функция, така че може да скочи обратно към тази функция. Така че, когато основните разговори разменят, наред нещата избута върху купчината не са само суапове локални променливи, или неговите аргументи, също тайно избута върху купчината, представлявано от червено парче тук, е адресът на основната физически в паметта на компютъра, така че, когато се прави суап, компютърът знае, че аз трябва да се върна към основното и да завърши изпълнението на основната функция. Така че това е опасно сега, защото ако типовете потребителски добре в повече от здравей, така, че въвеждане на потребителя clobbers или презаписва, че червената точка, логично, ако на компютъра просто ще приемем, сляпо че байта в тази червено парче са адреса, на който тя трябва да се върне, какво ще стане ако противникът е достатъчно умен, или достатъчно късмет, за да се сложи последователност от байтове там, че прилича на един адрес, но това е адресът на код че той или тя иска компютъра да изпълни вместо главната? 

С други думи, ако това, което на потребител пише в командния ред, не е просто нещо безвреден като здравей, но всъщност е код, който е еквивалентен за да изтриете всички файлове на този потребител? Или пишете паролата си за мен? Или започнете да влезете им клавиши, нали? Има начин, нека да постанови днес, че те могат да напишете просто 'Здравей' не свят или тяхното име, те биха могли по същество премине в кодови, нули и такива, че компютърът грешки за код, така и на един адрес. Така че, макар и малко по-абстрактно, ако типове потребители в достатъчно състезателна код че ние ще обобщим тук A. A е атака или противници. Така че просто лоши неща. Ние не се грижим за номера или нули или такива днес, така че в крайна сметка презаписване, че червената точка, забележи, че последователност от байтове. O 835 C нула осем нула. И сега, както и статия в Уикипедия тук предложи, ако сега започнете действително етикетирането на байтове в компютъра ви памет, какво статията Wikipedia е предлагащата е, че това, което ако адресът на тази горния ляв байт е 80 C 0 3508. 

С други думи, ако лош човек е достатъчно умен, с неговия или нейния код действително да постави редица тук, че съответства на адреса на кода той или тя инжектира в компютъра, ви може да излъже компютъра в прави нищо. Сваляне на файлове, за електронна поща неща, смъркане на трафика, буквално всичко може да бъде инжектира в компютъра. И така, препълване на буфера атака в същността си е просто глупаво, глупаво императивно от масив, който не са имали своите граници проверени. И това е, което е супер опасна и едновременно супер мощен в C е, че ние наистина имаме достъп до всяка точка в паметта. Това е до нас, програмистите, които пишат оригиналния код да проверите дължината на всяка дяволски масиви, че ние сме манипулирали. Така че да е ясно, каква е уговорката? Ако ние се търкаля към тази код, аз не трябва просто промяна на дължината на бар, какво друго трябва да се провери? Какво друго трябва да се прави, за да предотвратяване на тази атака изцяло? Аз не искам да кажа, просто сляпо че трябва да се копира колкото се може повече байта както е дължината на бар. Искам да кажа, като копирате много байта като са в бар до отпуснатите памет, или 12 максимално. Така че аз трябва някакъв вид ако състоянието който прави проверка на дължината на бар, но ако тя надвишава 12, ние просто трудно код 12 като максималното възможно разстояние. В противен случай т.нар буфер препълване атака може да се случи. В долната част на тези слайдове, ако сте любопитни да научите повече е действителната оригиналната статия ако искате да погледнете. 

Но сега, сред цени платени тук е липсата на ефективност. Така че това е един бърз ниско ниво поглед към това, което могат да възникнат проблеми сега, че ние имат достъп до паметта на компютъра. Но друг проблем ние вече се препъна в понеделник беше просто неефективността на свързан списък. Ние сме обратно в линейното време. Ние вече нямаме съседна масив. Ние не разполагаме с произволен достъп. Ние не можем да използваме квадратна скоба нотация. Ние буквално трябва да се използва по време на цикъл като този, аз написах преди малко. Но в понеделник, ние твърдеше, че можем пълзене обратно в царството на ефективност постигане на нещо, което е логаритмична може би, или най-добре все пак, може би дори нещо, което е така наречените постоянно време. И така, как можем да направим, че с помощта на тези нови инструменти, тези адреси, тези указатели, и резби неща от нашата собствена? Е, предполагам, че тук, това са куп от числа, които искаме да се съхранява в структура и търсене на данни ефективно. Абсолютно Можем да се върнем назад до седмица две, хвърлят ги в масив, и да ги търсите с двоично търсене. Разделяй и владей. И всъщност ви е написал Търсене в двоичен в PSET3, където изпълнява програмата находка. Но знаете ли какво. Има вид на по- хитър начин за постигане на това. Това е малко по- сложна и може би ни позволява да видим защо двоичен търсене е толкова по-бързо. Първо, нека да въведат понятието за едно дърво. Което, въпреки че в риалити дървета вид растат по този начин, в света на компютъра науката те вид расте надолу като родословно дърво, където трябва баба си и дядо или баба и дядо велики или какво ли не най-отгоре, патриархът и матриарх на семейството, точно този, така наречените корен, възел, под които са си деца, по-долу, които са негови деца, или неговите потомци по-общо. И всеки, който виси дъното на семейството дърво, освен че е на най-младият в семейството, също може да бъде само най-общо нарича листата на дървото. 

Така че това е просто един куп от думи и определения за нещо, наречено дърво в компютъра наука, много прилича на родословно дърво. Но има и по-красиви превъплъщения дървета, един от които се нарича двоично търсене дърво. И можете вид закачка освен това, това нещо прави. Е, това е двоичен в какъв смисъл? Къде двоичен идват от тук? Съжаляваме? Това не е толкова много на едно или и. Това е още, че всеки от възли не повече от две деца, тъй като ние видите тук. Като цяло, tree-- и Вашите родители и прародители може да има колкото се може повече деца, или внуци, тъй като те всъщност искат, и така например там имаме три децата на разстояние, че дясната ръка на възел, но в двоично дърво, един възел има нула, една или две деца максимално. И това е хубаво собственост, защото, ако това е с таван от две, ние ще бъде в състояние да получи малко дневник база двама действия става тук в крайна сметка. Така че ние имаме нещо логаритмична. Но повече за това след малко. Търсене дърво означава, че числата са разположени така, че лявата детето стойност е по-голяма от корена. И правото си дете е по-голям от основата. С други думи, ако вземе всяка от възли, кръговете в тази картина, и поглежда към своя ляв дете и правото си дете, първият трябва да бъде по-малко от, Второто трябва да бъде по-голяма. Така че здравия разум провери 55. Той е оставил дете е 33. Това е по-малко от. 55, правото му дете е 77. Това е по-голям от. И това е рекурсивно определение. Бихме могли да проверява всеки един от тези, възли и същи модел би попречил. 

Така че това, което е хубаво в двоично търсене дърво, е че един, можем да го приложат с структура на, точно като тази. И въпреки, че сме хвърляне много структури на вашия, те са малко по- интуитивен сега се надяваме. Синтаксисът е все още тайнствена със сигурност, но съдържанието на възел в този context-- и пазим използване на думата възел, независимо дали това е правоъгълник на екрана или в кръг, това е просто някаква родово контейнер, в този случай на едно дърво, като този видяхме, имаме нужда от цяло число във всяка от възли и след това имам нужда от две указатели, сочещи към лявата и дясната детето детето, съответно. Така че това е как можем да приложат, че в една структура на. И как бих могъл да го приложи в кода? Е, нека хвърлим един бърз Посетете този малък пример. Това не е функционална, но аз съм копира и тази структура. И ако ми функция за двоичен Търсене в дърво се нарича търсене, и това отнема два аргумента, цяло число N и указател на една възлова точка, така указател към дървото или указател към корена на едно дърво, как да отида, за да търсите N? Ами, на първо място, защото аз съм занимаващи се с указатели, Отивам да се направи проверка на здравия разум. Ако дървесни равни равнява на нула, е N в това дърво или не в това дърво? Не може да бъде, нали? Ако аз съм минал нищожна, там няма нищо. Че може и просто сляпо кажа върне фалшиви. Ако ми дадеш нищо, аз със сигурност не може да намирам кой номер N. Така че какво друго бих могъл да проверите сега? Отивам да се каже и друго, ако N е по-малко от всичко, което е най-възела на дърво че съм бил предаден N стойност. С други думи, ако броят съм търси, N, е по-малко от възела че аз разглеждам. И възела Търся в се нарича дърво, и извикайте от предишния пример за да получите най-стойността в указател, Аз използвам наколонените стрелка. Така че, ако N е по-малко от дърво стрелка N, искам да отида концептуално лявата. Как мога да изразят търсите напусна? За да е ясно, дали това е на снимката въпросния и аз съм бил приет, че най-горната стрелка, която е насочена надолу. Това е моето дърво показалка. Аз съм като посочи в корена на дървото. И аз търся да речем, за 44 броя, произволно. Е 44 или по-малко от по-голяма от 55 очевидно? Така че това е по-малко от. И така, това изискване се прилага, ако. Така че концептуално, какво искам да търси следващия, ако аз съм гледам за 44? Да? 

Точно така, аз искам да Търсене по левия детето, или наляво под-дървото на тази снимка. И всъщност, нека чрез на снимката тук само за миг, тъй като Не мога да се почеше това. Ако започна тук, в 55, и Знам, че стойността 44 Търся да отляво, това е вид на подобно разкъсване телефонния указател в половината или разкъсване на дървото на половина. Аз вече не трябва да се грижим за Цялата тази половината от дървото. И все пак, любопитно от гледна точка на структура, това нещо тук, че започва с 33, че и самата е двоичен търсене дърво. Аз казах думата рекурсивни преди, защото Наистина това е структура от данни, че по дефиниция е рекурсивно. Може да се наложи едно дърво, което е това голяма, но всеки един от нейните деца представлява едно дърво малко по-малък. Вместо да е дядо или баба, сега това е просто мама or-- Не мога да не say-- майка или татко, че би било странно. Вместо двете деца там ще бъде като брат и сестра. Едно ново поколение на родословното дърво. Но структурно, това е една и съща идея. И се оказва, че имам функция с които мога да търсите двоично търсене дърво. Тя се нарича търсене. Търся N в дърво лява стрелка иначе, ако N е по-голяма от стойността Сигурен съм, че в момента в. 55 в историята преди малко. Имам функция, наречена търсене, което мога, просто мине N това и рекурсивно търсене под-дърво и просто връщане независимо, че отговор. Иначе аз имам някаква окончателна базов модел тук. 

Каква е крайната случая? Tree е или нула. Стойността съм или търсите е по-малко от това или по-голяма от или равна на нея. И мога да кажа, равна равен, но това е логично еквивалентен на просто казвам друго тук. Така че истинската е как да намеря нещо. Така че да се надяваме това е още по-наложителна например от функцията за глупав сигма ние направихме няколко лекции в гърба, където е било толкова лесно да се използва линия да брои до всички номера, от една Н. Тук със структурата на данните че се е рекурсивно дефинирани и рекурсивно изготвен, сега ние имат способността да се изразяваме в кода, който от своя страна е рекурсивно. Така че това е точно същия код тук. 

И така, какво друго можем да решим проблемите? Така бързо крачка от дървета за миг. Ето, да речем, на германското знаме. А има и ясно модел на този флаг. И има много флагове в света, които са толкова прости, колкото това от гледна точка на техните цветове и модели. Но предполагам, че това се съхранява като .GIF Или JPEG, или растерна графика, или за пинг, всеки графичен файлов формат с които сте запознати, някои от които сме играе с по PSET4. Това не изглежда полезно да се съхранява черен пиксел, черен пиксел, черен пиксел, точка, точка, точка, цял куп черни пиксели за първи scanline, или ред, а след това цял куп същата, тогава един куп на същото, и след това цял куп червени пиксела, червени пиксела, червени пиксела, след цяло куп жълти пиксела, жълто, нали? 

Има такава неефективност тук. Как бихте интуитивно компресирате германското знаме ако го изпълняват като файл? Подобно на това каква информация може да не притеснява съхраняване на диск, за да за да се намали размера на файла от нашия харесват мегабайт до килобайт, нещо, по-малки? Където се намира на съкращенията тук, за да бъде ясно? Какво може да направите? Да? Точно. Защо не, а не си спомня цвета на всеки пиксел кърпи точно като правиш в PSET4 с формата на растерна графика файл, защо просто не представляват лявата колона на пиксела, например куп черни пиксели, куп на червено, и куп жълти, и след това просто някак кодират Идеята за Повторете това 100 пъти или Повторете това 1000 пъти? Когато 100 или 1000 е само цяло число, така че може да се размине само с един номер вместо стотици или хиляди допълнителни пиксела. И наистина, това е начина, по който може да компресирате германското знаме. И Сега какво да кажем за френски флаг? И малко някаква умствено упражнение, което флаг могат да бъдат компресирани повече диск? Германското знаме или французите флаг, ако вземем този подход? Германското знаме, защото има по-хоризонтална съкращения. И като дизайн, графичен файл мнозина формати наистина работят линии като сканиране хоризонтално. Те биха могли да работят вертикално, просто човечеството Преди години решиха, че ние ще като цяло мисля за неща ред по ред, вместо колона по колона. Така че наистина, ако сте били да погледнете файла размер на немски флаг и френски флаг, докато резолюцията е същото, същата ширина и височина, този път тук ще бъде по-голяма, защото трябва да се повтаря себе си три пъти. Вие трябва да посочите, синьо, повторете себе си, бяла, повторете себе си, червено, повтаря себе си. Не може просто да отидете на всички Между другото в дясно. И като настрана, за да се изчистване на компресия е навсякъде, ако те са четири кадъра от една video-- ви да си спомните, че един филм или видео е по принцип като 29 или 30 кадъра в секунда. Това е като малко флип книга, където можете Просто вижте изображението, изображение, картинка, изображение, образ просто супер бързо, така че тя изглежда като актьорите на екрана се движат. Ето една пчела на Начало на букет цветя. И макар че може да е вид трудно да се види на пръв поглед, единственото нещо, което се движи в този филм е пчелата. 

Какво е тъпо за съхранение видео разархивиране? Това е вид на отпадъците, за да съхранявате видео като четири почти идентични изображения, които различават само дотолкова, доколкото когато пчелата е. Можете да изхвърлите най- на тази информация и не забравяйте само, например, първият кадър и последния кадър, ключови кадъра, ако сте Някога чували думата, и просто да се съхранява в средна когато пчелата е. И не е нужно да съхраните всички розово, и синьо, а зелени стойности, както добре. Така че това е да се каже само, че сгъстяване е навсякъде. Това е техника, ние често използват или приемаме за даденост, тези дни. 

Но как да компресирате текст? Как да отида за компресиране на текст? Е, всеки от героите в Ascii е един байт, или осем бита. И това е нещо тъпо, нали? Защото най-вероятно тип А и Е и I и O и U много по-често, отколкото като W или Q или Z, в зависимост от езика, на който пишеш със сигурност. И защо да се използва осем бита за всяка буква, включително най популярните писма, нали? Защо не се използва по-малко битове за супер популярни букви, като E, нещата, които предполагам на първо място в Колелото на късмета, и да използват повече битове за най-малко популярни букви? Защо? Защото ние просто ще ги използват по-рядко. 

Е, оказва се, че там има били направени опити да се направи това. И ако си спомняте от клас училище или гимназия, морзовата азбука. Морзовата азбука има точици и тирета, които могат да бъдат предава по жица като звуци или сигнали от някакъв вид. Но Морзовата азбука е супер чист. Това е вид на бинарна система че имате точки или тирета. Но, ако сте въвели, например, две точки. Или ако смятате, обратно към оператора който върви като по сигнал, звуков сигнал, звуков сигнал, звуков сигнал, удря малко спусъка който предава сигнал, ако получателят, получава две точки, какво послание сте получили? Напълно произволно. 

I? I? Или какво about-- иначе? Може би това е само два полето E е? Така че има този проблем на decodability с Морс код, при което освен ако човек, който да изпратите съобщението всъщност прави пауза за да можете да сортирате на видите или чуете пролуките между букви, това не е достатъчно просто да се изпрати поток от нули и единици, или точки и тирета, защото има неяснота. E е една точка, така че ако виж две точки или чуете две точки, може би това е два E или може би това е една I. Така че ние се нуждаем от система, която е малко по-умен от това. Така че един човек на име Huffman години Преди дойде с точно това. Така че ние просто ще да вземе един бърз поглед колко дървета са уместен за това. Да предположим, че това е известно глупаво съобщение, който искате да изпратите, съставен от само A, B, C е D'е и E е, но има много съкращения тук. Това не е писано да бъде на английски език. Това не е кодирано. Това е просто глупаво съобщение с много повторения. Така че, ако действително отписвайте всички На А, Б, С е, D'ите, и Е е, ето честотата. 20% от писмата са А на 45% от писмата, са E, а три други честоти. Преброихме там ръчно и що е математика. 

Така се оказва, че Хъфман, преди известно време, осъзнах, че, нали знаете какво, ако започна сграда дърво или гора от дървета, ако щете, както следва, което мога да направя следното. Отивам да дам един възел на всеки от писмата, че ме е грижа за и аз отивам да се съхранява вътрешността на този възел честотите като плаваща запетая стойност, или можете да го използвате като N, също, но ние просто ще се използва плувка тук. И алгоритъма, че той предлага, е, че вие възползвам от тази гора от един възел дървета, така че супер къси дървета, и да започнете да ги свързва с нови групи, нови родители, ако щете. И вие направите това, като изберете двете най-малки честоти в даден момент. Тогава взех 10% и 10%. Създам нов възел. И аз призовавам новия възел 20%. 

Кои две възли I съчетават следващия? Това е малко неясно. Така че има някои случаи ъгъл, за да помисли, но за да пазят нещата доста, Отивам да избере 20% - Аз вече не обръща внимание на децата. Отивам да изберете съответно 20% и 15% и изготвя два нови ръбове. И сега кои два възела мога логично комбинирате? Игнориране на всички деца, всички внуци, просто погледнете в корените сега. Кои две възли мога да връзвам заедно? Point два и 0.35. Така че нека да се направи две нови ръбове. И тогава аз имам само един ляв. Така че тук е едно дърво. И това е било умишлено, изготвен да изглеждат някак доста, но забележете, че ръбовете са също е маркиран нула и единица. Така че всички останали ръбове са равни на нула произволно, но последователно. Всички правилни ръбове са такива. 

И така, какво Хофман, предложен е, ако искате да представляват B, вместо представлява броят като 66 на Ascii което е осем цели бита, Знаете ли какво, просто магазина модела нула, нула, нула, нула, защото това е пътят от дървото ми, г-н дърво Хъфман е, на крилото от основата. Ако искате да съхраните E, за разлика от това, не го правят изпрати осем бита, които представляват Е. Вместо това, изпрати онова модел на бита? One. И това, което е хубаво за това е, E, че е най-популярният писмото, и сте с помощта на -кратък код за него. Следващата най-популярните писмо изглежда, че беше A. И така колко бита каза той предложи като употреби за това? Нула, едно. 

И тъй като това е изпълнена като това дърво, за сега нека да предвидят има не неяснота в Morse код, тъй като всички по- писма, които ви интересуват са в края на тези ръбове. Така че това е само един прилагане на едно дърво. Това is-- и ще помаха ръката ми по това как се може да приложи това като структура C. Ние просто трябва да се комбинират символ, като Чар, и честотата, в ляво и дясно. Но нека да разгледаме две крайни примери, които ще получи доста запознат с след викторина нула в проблем зададете пет. 

Така че има структурата на данните известен като хеш таблица. И хеш таблица е вид охлади това, че има кофи. И предполагам, че има четири кофи тук, само четири празни пространства. Ето едно тесте карти, а тук се клуб, лопата, клуб, диаманти, клуб, диаманти, клуб, диаманти, clubs-- така че това е произволно. Hearts, hearts-- така че аз съм bucketizing всички входове тук. И една нужди хеш таблици да разгледаме вашия вход, и след това го постави в определена поставят въз основа на това, което виждате. Това е един алгоритъм. И аз бях с помощта на супер проста визуална алгоритъм. Най-трудната част от които е спомняйки си какви са снимките. И след това има четири общи неща. 

Сега купчините растяха, които е нещо умишлено дизайн тук. Но какво друго да правя? Така че всъщност тук имаме куп стари училище изпит книги. Да предположим, че един куп студенти имена са тук. Ето по-голяма хеш-таблица. Вместо четири кофи, Аз, да речем 26. И ние не искахме да отидем назаем 26 неща от чужбина [? Annenberg?], Така че Ето и петте, които представляват А до Z. И ако аз виж студент, чието име започва с А, Отивам да си викторина сложил там. Ако някой започне с C, ей там, A-- всъщност, не исках да го направя. B отива тук. Така че аз имам A и B и C. И Сега тук е друг Един студент. Но ако това е хеш-таблица реализира с масив, Аз съм вид прецакани в този момент, нали? Някак трябва да се сложи някъде. 

Така че един начин да се реши този е, всичко, полето, A е зает, B е зает, C е зает. Отивам да го сложи в D. Така че най- на първо място, аз имам случаен незабавен достъп към всяка от кофите за учениците. Но сега това е вид децентрализиране в нещо линейно, защото, ако искам да потърсите някой, чието име започва с А, да проверя тук. Но ако това не е най-A Студент търся, Някак трябва да започнат проверка кофите, защото това, което направих Беше нещо линейно изследва структурата на данните. Глупава начин да се каже просто погледнете за първия наличен отвор, и постави като план Б, така да се каже, или план D в този случай, стойността в вместо това място. Това е просто, така че, ако сте получи 26 места и няма ученици с Q име или Z, или нещо подобно че, най-малко, че използвате пространството. 

Но ние вече сме виждали по- умни решения тук, нали? Какво бихте направили, вместо ако имате сблъсък? Ако двама души имат на името А, какво ще са били по-умен или по- интуитивно решение, отколкото просто извеждайки A, където D е трябвало да бъде? Защо не просто отидете извън [? Annenberg?], като изчистване, друг възел, да я тури тук, и след това пуснати, че един студент тук. Така че аз по същество имат някакъв вид масив, или може би по-елегантно, както сме започваме да виждаме свързан списък. 

И така хеш таблица е структура които биха могли да изглежда точно като този, но по-хитро, ти нещо, наречено отделна верижното, като хеш таблица съвсем просто е масив, всеки от чиито елементи не е число, от своя страна е свързан списък. Така че можете да получите супер бърз достъп да реши къде да си хеш стойност. Много прилича с примера на карти, Направих супер бързи решения. Hearts отива тук, диаманти отива тук. Same тук, A отива тук, D отива тук, B отива тук. Така че супер бързи поглед прозорци, и ако Случайно да тичам в случай когато имаш сблъсъци, две хора с едно и също име, и след това можете просто да започнете свързването им заедно. И може би да ги сортира по азбучен ред, може би не. Но поне сега имаме динамизма. Така че, от една страна имаме супер бързо константно време, и вид на линейното време участва, ако тези свързани списъци започнете да се получи малко дълго. 

Така че този вид е глупав, шантавите преди шега години. В CS50 хак-а-Thon, когато учениците се настанят, някои TF или Са всяка година мисли, че е смешно да се примири знак, подобен на този, когато тя просто означава, ако името ти започва с А, отидете по този начин. Ако започва вашето име с B, проверете this-- OK, това е смешно, може би по-късно през семестъра. Но има и друг начин за това, също. Върни се на това. 

Така че има тази структура. И това е нашият последен структура за днес, което е нещо, наречено синтактично дърво. T-R-I-E, които по някаква причина е кратък за извличане, но тя се нарича синтактично дърво. Така синтактично дърво е друга интересна амалгама от много от тези идеи. Това е едно дърво, което сме виждали преди. Това не е двоично търсене дърво. Това е дърво с произволен брой на децата, но всяко от децата в синтактично дърво е масив. Масив с размер на, да речем, 26 или може би 27 ако искате да подкрепите тирета имена или апострофи в имената на хората. 

И така, това е структура от данни. И ако се вгледате от горе до долу, като, ако Посетете най-горния възел там, M, е сочещи към най-лявата нещо там, който след това А, X, W, E, L, L. Това е само структурата на данните, които произволно е съхраняване на имена на хора. И Максуел се съхраняват само след пътека от масив масив масив. Но това, което е невероятно за синтактично дърво е че, като има предвид, свързан списък и дори масив, най-добрите, които някога сме придобили е линейното време или логаритмична време в търсене някого. В тази структура данни на Trie, ако моята структура на данните има едно име в него и аз съм гледам за Максуел, аз съм Ще го намерите доста бързо. Аз просто гледам за M-A-X-W-E-L-L. Ако тази структура от данни, от друга страна, ако N е един милион, ако има милион имена в тази структура данни, Максуел все още продължава да бъде откриваем след само M-A-X-W-E-L-L стъпки. И David-- D-A-V-I-D стъпки. С други думи, чрез изграждане структура, която е на данни Трябва всички тези масиви, в които се издържат с произволен достъп, Мога да започне да се оглежда до народната назове използват сума от време, който е пропорционална не броя на нещата в структурата на данните, като един милион съществуващи имена. Размерът на време ми отнема да се намери М-A-X-W-E-L-L в тази структура данни е пропорционална не на размер на структурата на данните, но на дължината на името. И реалистично имена, които търсим нагоре никога няма да бъде луд дълго. Може би някой има 10 герой назове, 20 име характер. Със сигурност това е крайно, нали? Има човек на земята, който има възможно най-дълго име, но това име е константа Дължина на стойност, нали? Той не се променя във всеки смисъл. Така че по този начин, ние сме постига структурата на данните че е константно време поглед нагоре. Той прави предприемат редица стъпки в зависимост от дължината на входа, но не и числото на името в структурата на данните. Така че, ако можем да удвои броя на имената следващата година от един милиард до два милиарда, констатация Maxwell ще отнеме точно същия брой седем стъпки за да го намери. И така, ние като че ли сме постигнали нашата Светия Граал на времето за работа. 

Така след няколко бързи съобщения. Quiz нула идва. Повече за това на интернет страницата на курса през следващите няколко дни. Понеделник lecture-- това е празник тук в Харвард в понеделник. Това не е в Ню Хейвън, така че ние сме като класа в Ню Хейвън за лекция в понеделник. Всичко ще бъде заснет и поточно както обикновено, но нека да приключи днес с 30 секунди клип наречени "Дълбоки мисли" от Daven Farnham, които е вдъхновен миналата година от събота "Дълбоки мисли" Night Live на от Джак Handy, които Сега трябва да има смисъл. 

FILM: И сега, "Deep Мисли "от Daven Farnham. Hash маса. 

SPEAKER 1: Добре, това е всичко за сега. Ще се видим следващата седмица. 

Дъг: За да го видим в действие. Така че нека да погледнем, че точно сега. Така че тук, имаме сортиран масив. 

Иън: Doug, може ли да отида напред и рестартиране това само за една секунда, моля. Добре, камери са подвижен, така че за действие, когато сте готови, Дъг, OK? Дъг: Добре, така че това, което ние имаме тук е сортиран масив. И аз съм оцветен всички елементи червено, за да покаже, че е в действителност, сортиран. Така се припомни, че първото нещо, което правим е ние сортирате лявата половина на масива. Тогава ние сортирате правото половината от масива. И ти-да, ти-да, ти-га, ние ги обедините заедно. И ние имаме един напълно сортиран масив. Така че това е начина, сортиране чрез сливане работи. 

Иън: Уау, чакай, чакай, нарязани, нарязани, нарязани, нарязани. Дъг, не може просто да ти-да, ти-га, Ya-га, вашия начин чрез сливане на сортиране. 

Дъг: Току-що го направих. Това е добре. Ние сме добре да тръгвам. Нека просто да се запази при търкаляне. Така или иначе, 

Иън: Трябва да се обясни по-пълно от това. Това просто не е достатъчно. Дъг: Ian, ние не правим трябва да се върнем към едно. Това е добре. Така или иначе, ако продължим с merge-- Ian, ние сме в средата на снимките. 

Иън: Знам. И ние не можем просто да ти-да, ти-га, Ya-га, през целия процес. Трябва да се обясни как двете страни се сливат заедно. 

Дъг: Но вече сме обясни как две sides-- 

Иън: Вие току-що е показано ги сливане масив. Дъг: Те знаят процеса. Те са добре. Минахме над нея десет пъти. 

Иън: Ти просто прескача право върху него. Връщаме до един, Не можеш ли да ти-да, ти-га върху него. Добре, обратно към едно. 

Дъг: Аз трябва да се върна през всички стъкла? Господи. Това е като шести път, Иън. Това е добре. 

Иън: Добре. Готов ли си? Страхотен. Action.