ЗВУЧНИЦИ 1: Добро, така што ова е CS50 Ова е крајот на пет недела. И да се потсетиме дека последен пат се започнува да бара познавач на податоци структури, која започна да се реши проблеми, кои почнаа да се воведе нови проблеми, но клучот за ова е вид на нишките кои ги почна да се направи од јазол да јазол. Значи ова се разбира е на одделно поврзани листа. И со одделно поврзани, Мислам, има само еден нишка помеѓу секоја од тие јазли. Излегува можете да направите познавач работи како двојно поврзана листи при што ќе ги има стрелка оди во двете насоки, кои може да помогне со одредени ефикасност. Но, ова се реши проблемот? Што овој проблем се реши? Зошто ни е гајле во понеделник? Затоа, во теорија, не ни е гајле во понеделник? Што да направам? 

ПУБЛИКАТА: Ние динамички може да ја промените големината. 

ЗВУЧНИЦИ 1: Добро, така што можеме динамички да се менува големината. Добро направено и за вас. За да можете да ја промените големината на овој динамички податочна структура, додека низа, потсетиме, што треба да знаете приори колку простор ви треба и ако ви треба малку повеќе простор, ти си вид на надвор од среќа. Што треба да се создаде еден нов низа. Мора да се движат сите ваши податоци од еден до друг, на крајот се ослободи стариот низа ако можеш, а потоа продолжи. Кои само се чувствува многу скапа и многу неефикасен, и навистина може да биде. Но, тоа не е на сите добри. Ние ја плати цената, што беше еден од повеќе од очигледна цени ние плаќаат со помош на поврзани листа? 

ПУБЛИКАТА: Ние мора да ја користи двојно повеќе простор за секој од нив. ЗВУЧНИЦИ 1: Да, па ние треба најмалку двојно повеќе простор. Всушност, сфатив оваа слика е дури и малку погрешно, затоа што на CS50 ИРО во многу модерни компјутери, покажувач или адреса не е во фактот четири бајти. Тоа е многу често овие осум дена бајти, кој значи дното повеќето правоаголници постојат во реалноста се вид на двојно големи како што сум подготвен, што значи дека сте со користење на три пати многу простор како што ние би можеле да имаат поинаку. Сега, во исто време, ние сме уште се зборува бајти, нели? Ние не сме секогаш зборува мегабајти или гигабајти, освен ако овие структури на податоци се големи. 

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

Така што ова е само дел C код, дури и не заврши програмата дека јас навистина брзо шлаг. Тоа не е онлајн во дистрибуцијата код, бидејќи тоа нема да всушност работат. Но информации Тукушто со коментар, рече, точка точка точка, има по нешто таму, точка точка точка, нешто таму. И ајде да се погледне Кои се сочни делови. Така натаму линија три, потсетиме дека ова е сега ние предложи прогласување на јазол последните време, еден од оние кои се правоаголни предмети. Таа има int дека ние ќе го наречеме N, но ние би можеле да го наречеме ништо, а потоа ѕвезда struct јазол наречен следната. И само за да биде јасно, дека вториот линија, на линија шест, што е тоа? Она што го прави тоа за нас? Бидејќи тоа сигурно изгледа повеќе криптичната од нашето вообичаено променливи. 

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

ЗВУЧНИЦИ 1: Тоа го прави да се движат над еден. И за да бидеме попрецизни, тие ќе бидат зачувани адреса на јазол, кој е замислена да биде семантички веднаш до неа, нели? Па тоа не се случува да се мора да се движи нешто. Тоа е само ќе да складира вредност, која е ќе биде адреса на некои други јазли, и тоа е причината зошто сме го кажале struct јазол ѕвезда, ѕвезда означувајќи покажувач или адреса. Добро, па сега ако претпоставиме дека имаме оваа N достапни за нас, и нека е се претпостави дека некој друг има вметната целиот куп на цели броеви во поврзани листа. И дека е поврзана листа посочени од одреден момент променлива наречена листата што е донесен во тука како параметар, како можам да се обратите за линија 14 спроведување на пребарување? Со други зборови, ако сум спроведување функција чија цел во животот е да се земе int и тогаш почеток на поврзани листа, дека е покажувач кон поврзаните листа. Како прво, за кого мислам дека Дејвид беше нашите волонтери, во понеделникот, тој беше посочувајќи на целата поврзани листа, тоа е како да сме полагање Давид како наш аргумент тука. Како да одиме за напречни оваа листа? Па, излегува дека и покрај тоа што покажувачи се релативно нови, сега за нас, можеме да го направиме овој релативно на вистината. 

Одам да се оди напред и да прогласи привремена променлива која по конвенција е само ќе да се нарече покажувач, или кон меморија, но може да се нарече нешто што сакате. А јас ќе одам да се иницијализира тоа на почетокот на листата. За да можете да вид на мисли на ова како мене наставникот пред некој ден, вид посочувајќи на некој меѓу нашите луѓе како волонтери. Па јас сум привремена променлива која е само укажува на истото дека нашите случајно по име волонтер Дејвид беше исто така укажува. Сега додека покажувачот е не нула, затоа што се потсетиме дека е ништовен некои посебни стража вредност на демаркира на крајот на листата, Така, додека јас не сум укажува на земја како нашата последна волонтер беше, ајде да одиме напред и да го направите следново. Ако pointer-- и сега јас вид сакате да се направи она што го направивме со ученикот structure-- ако покажувачот точка до equals-- поточно, ако покажувачот точка N еднаква е еднаква на променлива N, на аргументи и тоа е се донесе во, тогаш сакам да се оди напред и да каже врати вистина. Најдов бројот N внатрешноста на еден од јазли се на мојот поврзани листа. Но точката веќе не работи во овој контекст, бидејќи покажувачот кон меморија, е навистина покажувач, адреса, ние всушност може прекрасно користете конечно парче синтакса тој вид на марки интуитивно чувство и всушност користат стрела тука, што значи да си одат од кои се однесуваат на цел број во истиот. Така што е многу слична во дух на операторот точка, туку затоа што покажувачот не е покажувач а не се вистинските struct, ние само користење на тастатурата. 

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

Па ако сакам да влезете низ оваа листа, Јас не може само да ми е плус плус повеќе, Јас наместо да кажам Јас, покажувач, се случува што и да се изедначи следниот поле не е, следниот поле е, следното поле не е, по сите оние лево раце што ги имавме на сцената за покажување некои последователни вредности. И ако јас се добие преку дека целата повторување, и на крај, јас хит null немање Пронајдени N уште, јас само return false. Значи, повторно, сето тоа што го правиме тука, како на слика пред еден миг, почнува со внесување на почетокот на листата се претпоставува. А потоа и да ја проверам, е вредноста Јас сум во потрага за еднакви на девет? Ако е така, јас се врати вистина и јас сум се направи. Ако не, јас се ажурираат мојата рака, АКА покажувач, до точка на локација на следната стрелки, и потоа локација следниот стрелката, и следниот. Јас сум едноставно одење преку оваа низа. 

Значи, повторно, кој се грижи? Како што е оваа состојка за? Па, да се потсетиме дека воведовме поимот на магацинот, кој е тип на апстрактен податоци доколку тоа е не нешто Ц, тоа не е нешто CS50, тоа е една апстрактна идеја, оваа идеја на редење работи на врвот на една друга кои можат да бидат имплементирани во гроздовете на различни начини. И еден начин ние предложи беше со низа, или со поврзана листа. И излегува дека канонски, односно магацинот поддржува најмалку две операции. И зуи зборови се бута, да им помогнам нешто врз оџакот, како нова лента во мензата, или поп, што значи да се отстрани врвниот фиоката од магацинот во јадење салата, а потоа можеби и некои други операции, како и. Па, како би можеле да се дефинира структурата дека ние сме сега повикуваат говедо? 

Па, ние сме сите од потребното синтаксата на располагање во C. велам, ми даде дефиниција на тип на на struct внатрешноста на оџакот, Јас ќе одам да се каже е низа, на куп на броеви и потоа големина. Значи со други зборови, ако сакам за спроведување на оваа во кодот, дозволете ми да оди и само вид на добие од тоа што ова е изјава. Значи ова е велејќи дека, дај ми структура која доби низа, и јас не знам што е капацитет, тоа е очигледно некои константа што сум дефиниран на друго место, и тоа е добро. Но, претпоставувам дека тоа е само еден, два, три, четири, пет. Па капацитет е 5. Овој елемент во внатрешноста на мојата структура ќе бидат повикани броеви. И тогаш ми е таков други променливи очигледно наречен големина, која првично ќе одам да се предвиди е иницијализиран на нула. Ако не постои ништо во магацинот, големината е нула, и тоа е вредности ѓубре во бројки. Јас немам идеја што е таму само уште. 

Значи, ако јас сакам да помогнам нешто врз оџакот, Претпоставувам дека се јавите на функцијата поттурнување и Велам помогнам 50, како и број 50, каде што ќе предложи Јас го привлече во оваа низа? Има пет различни можни одговори. Каде сакате да им помогнам на бројот 50? Ако цел овде, повторно, јавете се на притисни функција, да го положат во расправија 50, каде можам да го стави? Пет possible-- 20% шанса на погодување правилно. Да? 

ПУБЛИКАТА: екстремната десница. 

ЗВУЧНИЦИ 1: екстремната десница. Сега има 25% шанса на погодување правилно. Така што, всушност, ќе биде во ред. По договор, јас ќе кажам со низа, ние генерално ќе започне на левата страна, но секако може да со почеток во право. Па тука ќе биде спојлер сум веројатно нема да го вадам од левата страна, Исто како и во една нормална низа каде Јас тргнеш лево кон десно. Но, ако можете да флип аритметичка, парична казна. Тоа едноставно не е конвенционален. Добро, јас треба да се направи една повеќе промени, секако. Сега што сум ги турка нешто врз оџакот, што е следно? 

Добро, имам за зголемување на големината. Значи, дозволете ми да оди напред и само ажурира оваа, која беше нула. И наместо тоа сега, јас ќе одам да се стави во една вредност. И сега претпоставувам дека им помогнам на друг Бројот врз оџакот, како и 51. Па, јас треба да се направи уште еден промена, која е до големината на две. И тогаш претпоставувам дека помогнам уште еден Бројот врз оџакот како 61, сега јас треба да се ажурира на големината уште еден време, и да се добијат на вредност 3, како и големината. И сега да претпоставиме што јас го нарекувам поп. Сега се појавуваат, по конвенција, при што не се расправа. Со магацинот, целата точка на послужавник метафора е тоа што вие не мора да дискреција да одам да купам што послужавник, сите можете да направите се појавуваат на врвот на еден од магацинот, само затоа. Тоа е она што оваа податочна структура го прави тоа. 

Па од таа логика, ако јас велат поп, она што доаѓа надвор? Па 61. Значи она што навистина е компјутер случува да се направи во меморијата? Што значи на мојот код треба да направите? Што ќе ви предложат ние промена на екранот? Што треба да се промени? Жал ми е? За да можеме да се ослободи од 61. Па јас дефинитивно може да го направите тоа. И можам да се ослободи од 61. И тогаш што другите промена треба да се случи? Големината, веројатно е да се вратиш на две. И така тоа е во ред. Но чекајте, големина пред еден миг беше три. Ајде да се направи брза проверка разумност. Како да не знаеме дека ние сакаше да се ослободи од 61? Затоа што ние сме пукање. И така имам оваа втората големина имот. 

Чекај малку, јас сум Размислување назад кон две недела кога почнавме да зборуваме за низи, каде што ова е локација нула, ова е една локација, ова било локација две, ова е локацијата три, четири, тоа изгледа како врската меѓу големината и елементот што сакате да го отстраните од низата се појавува да биде само она што? Големина на минус еден. И така тоа е начинот како луѓето ние знаеме 61 се случи прво. Како е на компјутерот нема да знае? Кога вашиот код, каде што веројатно сакате да го направите големина минус еден, така три минус еден е два, и на тој значи дека ние сакаме да се ослободи од 61. И тогаш ние навистина може да се ажурира големината, така што сега големина оди од три на само две. И само за да бидат педантни, јас ќе одам да предложи дека јас сум се направи, нели? Ви предложи интуитивно точно дека треба да се ослободи од 61. Но не сум вид на вид на добиле ослободи од 61? Сум заборавил ефикасно дека тоа е всушност таму. И да се сетам на PSET4, ако сте ја прочитате написот за судска медицина, PDF дека сме имале вие ​​момци се прочита, или ќе ја прочитате оваа недела за PSET4. Потсетиме дека всушност ова е соодветен за Целата идеја на компјутерски криминолошки науки. Што компјутер генерално не е тоа само се заборави каде што нешто е, но тоа не оди во и како се обиде да го избрише или прескокнување оние битови со нули и единици или некои други случајни модел освен ако не се направи тоа намерно. Па вашата интуиција е Добро, ајде да се ослободи од 61. Но, во реалноста, ние не мора да се мачат. Ние само треба да се заборави дека тоа е таму со промена на нашата големина. 

Сега има еден проблем со овој магацинот. Ако јас се задржи туркање работи врз оџакот, што е очигледно нема да се случи во само неколку моменти на време? Ние ќе треба да работи надвор од просторот. И што ќе правиме? Ние сме вид на зезнав. Оваа институција не им дозволува ни ја промените големината на низата, поради користење оваа синтакса, ако сетам на недела две, откако ќе прогласи големината на низа, не сме виделе механизам сепак, каде што можете да ја смените големината на низата. И навистина Ц не дека имаат функција. Ако ти кажам да ми даде пет Nths, да ги наречеме броеви, тоа е се што ви се случува да го добие. Па правиме сега од понеделник имаат способноста за изразување на решение иако, ние само треба да го tweak дефинирањето на нашиот оџак да не бидат некои хард-кодирани низа, Но, само за да ја запази адреса. 

Сега, зошто е ова? Сега ние само треба да се биде удобно со на фактот дека кога моето програмата работи, Јас сум веројатно ќе Треба да се постави со луѓе, Колку броеви не сакате да ја зачувате? Па за внесување треба да дојде од некаде. Но штом јас знам дека број, а потоа јас само може да го користите она што функционира за да се даде ми парче меморија? Можам да го користам Примерок. И можам да кажам било кој број на бајти сакам назад за овие Nths. И сè што ми треба да се сместат на бројот променлива тука во внатрешноста на оваа struct треба да биде што? Што, всушност, оди во броеви во оваа ситуација? Да, покажувач на првата бајт од таа парче меморија, или поконкретно, на адресата на првиот од овие бајти. Не е важно дали тоа е една бајт или милијарда бајти, Јас само треба да се грижат за првиот. Затоа што она што Примерок гаранции и мојот оперативен систем гаранции, е тоа што на парче меморија јас добие, тоа се случува да биде соседни. Таму не се случува да биде празнини. Значи, ако сум го побарал 50 бајти или 1.000 бајти, сите тие се случува да биде да се врати назад кон назад. И толку долго колку што се сеќавам колку е голема, како многу ми побара, сите што треба да знаете е прв ваков адреса. 

Така, сега имаме можност во кодот. Иако, тоа се случува да ни потрае повеќе време да се напише овој горе, сега можеме да се реалоцираат дека меморијата со само чување на друга адреса таму ако сакаме поголема или дури помал парче на меморија. Па тука за да се пласирам. Сега ние се динамика. Ние се уште имаат contiguousness тврдам. Примерок бидејќи ќе ни даде соседни парче меморија. Но, тоа се случува да биде болка во вратот и за нас, програмер, за да всушност се кодира нагоре. Тоа е само повеќе работа. Ние треба код слично на она што беше удира од пред само еден миг. Многу doable, но додава комплексност. И толку време инвеститорот, програмер времето е уште еден ресурс кои би можеле да треба да се трошат извесно време за да добиете нови функции. А потоа се разбира, постои листа на чекање. Ние не би навлегувал во тоа еден во многу детали. Но тоа е многу слични во духот. Можев да се спроведе на дното, и што одговара на своето работење, Стави во ред или dequeue, како да додадете или отстраните, тоа е само познавач начин на велејќи: Стави во ред или dequeue, како што следи. Јас само може да си даде struct дека повторно има низа број е, дека повторно има големина, Но, зошто јас сега треба да ги пратите на предниот дел на дното? Јас не треба да знаете предниот дел на мојата оџак. Па, ако повторно за queue-- нека е само тешко се кодира како што имаат како пет цели броеви во потенцијално тука. Значи ова е нула, еден, два, три, четири. Ова се случува да биде повика повторно броеви. А со тоа ќе се нарече големина. 

Затоа не е доволно да се има само големината? Па, ајде да се поттикнат истите тие броеви. Па јас сум pushed-- enqueued, или се наметнува. Сега ќе Стави во ред 50, а потоа 51, а потоа 61, и точка точка точка. Значи тоа е Стави во ред. Јас enqueued 50, потоа 51, па 61. И кој изгледа идентично до магацинот досега, освен што треба да се направи една промена. Јас треба да се ажурира оваа големина, па одам од нула до еден до 2-3 сега. Како можам да dequeue? Што се случува со dequeue? Кој треба да падне оваа листа ако тоа е на линија на Apple продавница? Па 50. Така, тоа е вид на сложени да ја формира тоа време. Со оглед на тоа последен пат тоа беше супер лесно да се направи само големината минус еден, Стигнам до крајот на мојот низа ефикасно каде бројките се, тој ги отстранува 61. Но, јас не сакате да се отстрани 61. Сакам да се земе 50, кој беше таму во 05:00 да се редат за Новиот iPhone или какво ли не. И така да се ослободи од 50, јас не може само да го направите ова, нели? Јас може да премине од 50. Но, ние само што рековме не мора да биде толку анална како да го избрише или ги кријат податоците. Ние само може да заборави каде е тоа. 

Но, ако си ги променам моите големина сега да две, дали е тоа доволно информации да знаат што се случува во мојата листа на чекање? Не баш. Како што е мојата големина два, но каде започнува на листа на чекање, особено ако се 'уште имам истите тие броеви во меморијата. 50, 51, 61. Па јас треба да се запамети сега кога предниот дел е. И така како што јас предложи до таму, ние ќе имаат само наречен Енти фронт, чија почетна вредност треба да биде она што? Нула, само на почетокот на листата. Но сега во прилог на decrementing големината, ние само подигање на фронтот. Сега тука е уште еден проблем. Значи уште продолжувам да одам. Претпоставувам дека тоа е бројот на како 121, 124, и потоа, мајката, Јас сум надвор од простор. Но чекајте, јас не сум. Па во овој момент во приказната, Претпоставувам дека големината е еден, два, три, четири, па претпоставувам дека Големината е четири, предната е еден, па 51 е на фронтот. Сакам да се стави уште еден број тука, но, мајката, јас сум надвор од просторот. Но, јас не сум навистина, нели? Каде може да се стави некои дополнителна вредност, како 171? Да, би можел само вид на се врати таму, нели? А потоа премине од 50, или само да ја пребришете со 171. А ако се прашувате зошто нашите броеви доби толку случајно, Овие често се земени компјутер науката курсеви во Харвард по CS50. Но, тоа беше добра оптимизација, затоа што сега не сум губи простор. Јас се уште треба да се запамети колку е голема тоа нешто е вкупно. Тоа е пет вкупно. Затоа што не сакаат да пребрише почне 51. Па сега јас сум се уште надвор од просторот, па со истиот проблем како и досега. Но може да се види како сега во вашиот код, што веројатно мора да се напише малку повеќе комплексност да се направи што се случуваат. И всушност, она што операторот во C веројатно овозможува можете да го направите ова магично на кружност? Је оператор modulo, знак за процент. Значи она што е вид на ладно за редица, иако ние ги задржи цртање низи како што се овие, како прави линии, ако вид на се размислува за тоа како кривули наоколу како круг, а потоа само интуитивно тој вид на работи ментално Мислам дека малку повеќе чисто. Вие, сепак, ќе мора да се спроведе дека ментален модел во кодот. Па не е толку тешко, во крајна линија, да се спроведе, но ние се уште го изгуби size-- подобро, способноста за менување на големината, освен ако не го правиме тоа. 

Ние треба да се ослободи од низата, ние да го замени со еден покажувач, а потоа некаде во мојот код имам повик што функционира за да всушност се создаде низата наречена броеви? Примерок, или некои слични функција, точно. Било какви прашања во врска со Купишта или редици. Да? Добро прашање. Modulo што ќе се користи тука. Па, генерално, кога се користи МО, ќе го направи тоа со големина на Целата структура на податоци. Така нешто како пет или капацитет, ако тоа е постојана, веројатно е вмешан. Туку само прави modulo пет Веројатно не е доволен, затоа што треба да знаеме што правиме навиват тука или тука или тука. Па ти си најверојатно, исто така, ќе сакаат да се вклучат од големината на нешто, или на предната променлива, како и. Па тоа е само оваа релативно едноставни аритметички израз, но modulo ќе биде клучна состојка. 

Толку краток филм ако сакате. Анимација дека некои луѓе на друг универзитет стави заедно што имаме адаптирана за оваа дискусија. Тоа подразбира Џек учење на факти за редици и статистика. 

Филм: Еднаш, многу одамна, имаше еден дечко по име Џек. Кога станува збор за правење на пријатели, Џек не имаш талент. Значи Џек отиде да разговара со најпопуларниот човек што знае. Тој отиде во Лу и праша: Што да правам? Лу виде дека неговиот пријател беше навистина потресени. Па, тој почна, само изгледа како сте облечени. Не имате било какви облека со различен изглед? Да, рече Џек. Јас сигурно не. Доаѓаат во мојата куќа и Ќе им покажам на вас. Така тие отишле да се Џек. И Џек Лу покажа полето каде што се чуваат сите негови кошули, и неговите панталони, и чорапи. Лу рече, гледам имаш сите ваши облека во купот. Зошто не ви носат некои други еднаш во некое време? 

Џек рече, добро, кога јас извадете облека и чорапи, Јас ги мијат и се стави нив далеку во полето. Потоа доаѓа следниот наутро, а јас до хоп. Одам во кутија и да добијат мојата облека од врвот. Лу брзо сфатија проблемот со Џек. Тој се чува облека, CD-а, и книги во магацинот. Кога стигна за нешто да се прочита или да се носат, тој ќе го избере врвот книга или долна облека. Тогаш кога беше направено, тој што би рекол десен бек. Назад тоа ќе одам, на врвот на магацинот. Знам дека од решението, рече триумфален гласно. Што треба да научат да започнат со користење на редот. Лу зеде облеката на Џек и ги обесат во плакарот. И кога го празнат кутијата, тој само го фрлат. 

Тогаш тој рече: Сега Џек, на крајот на денот, стави вашата облека на левата кога ќе ги стави настрана. Тогаш утре наутро кога ќе се види блесокот на сонцето, се добие вашата облека на десната страна, од крајот на линијата. Не гледате ли? рече Лу. Тоа ќе биде толку убаво. Ќе носат се што некогаш пред да се носи нешто двапати. И со сè во редици во неговиот плакар и полица, Џек почна да се чувствува сосема сигурен во себе. Сите благодарение на Лу и неговата прекрасна задача. ЗВУЧНИЦИ 1: Во ред, тоа е симпатична. Значи она што е навистина се случува на под хаубата сега? Дека имаме покажувачи, дека имаме Примерок, дека имаме способноста да се создаде делови од меморијата за нас динамично. Значи ова е ние слика увид само пред некој ден. Ние навистина не живее за тоа, но оваа слика се случува под на хаубата за недели. И така ова претставува, само правоаголник дека ние сме подготвени, меморијата на вашиот компјутер. А можеби и на вашиот компјутер, или CS50 Проект, има GIGABYTE на меморија или RAM меморија или два гигабајти или четири. Тоа навистина не е важно. Вашиот оперативен систем Windows или Mac OS или Линукс, во суштина им овозможува на вашата програма да се мисли дека има пристап на целокупната меморијата на вашиот компјутер, и покрај тоа што може да се работи повеќе програми одеднаш. Така, во реалноста, тоа не функционира. Но, тоа е вид на илузија со оглед на сите ваши програми. Значи, ако сте имале две свирки на RAM меморија, овој е како на компјутерот може да се размислува за тоа. 

Сега случајно, еден од овие работи, една од овие сегменти на меморија, се нарекува оџак. И навистина во секое време досега во писмена форма код кои сте ги нарекува функција, на пример главни. Потсетиме дека секој пат сум меморија составен компјутерот, Јас секогаш се подготви вид на половина на правоаголник тука и не се мачи да зборува за тоа што е горе. Бидејќи кога главни се нарекува, тврдам дека ќе го добиете овој треска на меморија што оди надолу тука. И ако главниот нарекува функцијата како swap, и swap оди овде. И што излезе, тоа е каде се завршува. На нешто што се нарекува стек внатрешноста на меморијата на вашиот компјутер. Сега на крајот на денот, ова е само се обраќа. Тоа е како бајт нула, еден бајт, бајт 2 милијарди долари. Но, ако мислите дека за тоа како овој правоаголни објект, сите што го правиме секој време што ние го нарекуваме функција е дели нов парче од меморијата. Ние сме давање на таа функција парче на сопствената меморија за да се работи со. 

И да се потсетиме дека ова е важно. Затоа што ако ние немаме нешто како трампа и двајца локални променливи како А и Б и ние се променат овие вредности од еден и два до две и еден, да се потсетиме дека кога своп се враќа, тоа е како тоа парче меморија е само нема. Во реалноста, тоа е сепак постојат форензички. И нешто што, всушност, е уште таму. Но концептуално, тоа е како иако тоа е целосно исчезна. И така главната не знае некој од работа она што беше направено во таа swap функција, освен ако тоа е всушност помина во тие аргументи од страна на покажувачот или со повикување. Сега, основните решение за тој проблем со трампа поминува во работите од адресата. Но, се покажа, исто така, она што е се случува над тој дел на правоаголникот сето ова време е Сепак, има повеќе меморија до таму. И кога ќе се динамички алоцирам меморија, без разлика дали тоа е во внатрешноста на GetString, која ние сме прави за вас во CS50 библиотека, или ако вие момци јавете се и прашајте Примерок оперативниот систем за парче меморија, тоа не доаѓа од оџакот. Таа доаѓа од друго место во меморијата на вашиот компјутер што се вика на купот. И тоа не е било поинаку. Тоа е исто RAM меморија. Тоа е истата меморија. Тоа е само на RAM меморија која е до таму, наместо овде долу. 

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

И излегува дека лошо момче, луѓе кои се особено добри со програмирање, и се обидува да се пробие во компјутери, можат да ја искористат оваа реалност. Всушност, ајде да се разгледа малку програмка. Значи ова е пример можете да го прочитате за повеќе детали на Википедија. Ние ќе ви укаже на член, ако љубопитни. Но, има една напад генерално познат како buffer overflow дека постои се додека луѓето имале можност да манипулира компјутерска меморија, особено во В. Така што ова е многу произволна програма, но ајде да се чита од долу нагоре. Главната во argC знак ѕвезда argv. Така, тоа е програма со која се зема командната линија аргументи. И сите главни се очигледно е повик функција, да го наречеме F за едноставност. И поминува во што? Argv на еден. Така што се што се излачува во F зборот е дека корисникот ја внеле во конзолата по име на програмата е на сите. Толку многу како Цезар или Vigenere, која може да се сети прави со argv. 

Значи она што е F? F зема во низа како единствен аргумент, АКА знак ѕвезда, исто работа, како стринг. И се вика произволно бар во овој пример. А потоа знак C 12, само во однос на Едноставен, она што е знак в заградата 12 прави за нас? Што е тоа? Доделување меморија, конкретно 12 бајти за 12 карактери. Токму така. А потоа на последниот ред, се промешува и копија, што веројатно не сте виделе. Ова е стринг копија функција чија цел во животот е да го копирате својот втор аргумент во првиот аргумент, но само до одреден број на бајти. Па на третиот аргумент вели: колку бајти треба да ги копирате? Должината на лентата, без оглед на корисникот внесе во. И содржината на бар, таа низа, се копирани во меморијата вперен во В. 

Значи ова се чини глупаво, а тоа е. Тоа е смислена пример, но тоа е претставник од класата на нападот вектори, начин на напаѓање на програмата. Сите е добро и добро, ако на корисникот типови со еден збор, тоа е 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 бајти, и ние сме супер безбеден. Се е добро. Но, ако јас пишувате нешто подолго, потенцијално тоа е ќе се вовлече во лентата за статус. Но, уште полошо, тоа се покажува од сето ова време, иако никогаш не сме зборуваше за тоа, на магацинот се користи за други нешта. Тоа не е само локални променливи. 

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

Со други зборови, ако она што го пишува корисникот во конзолата, не е само нешто безопасни како здраво, но тоа е всушност кодот кој е еквивалентен за бришење на сите датотеки на корисникот? Или е-пошта на нивната лозинка за мене? Или започнете зачувување на нивните тастатурата, нели? Постои начин, да се пропише и денес, дека тие би можеле да напишете во не само здраво свет или нивното име, тие би можеле суштински помине во кодот, нули и оние, кои компјутерот грешки за кодот и адреса. Па иако малку апстрактно, ако корисникот видови доволно контрадикторна код дека ние ќе се генерализира и тука А. е удар или противници. Па само лошите работи. Ние не им е грижа за броеви или нули или оние Денес, како што ќе завршат пребрише дека црвено дел, забележи дека низа од бајти. О 835 С нула осум нула. И сега како Википедија видиш тука предложи, ако сега, всушност, да почне означување на бајти во вашиот компјутер меморија, што на Википедија е предлагачот е во тоа, што ако адреса од кои горниот лев бајт е 80 С 0 3508. 

Со други зборови, ако на негативецот е доволно паметни со неговите или нејзините код за да всушност се стави број тука одговара на адреса на кодот тој или таа се вбризгува во компјутерот, вие може да трик на компјутерот во ништо да преземе. Отстранување на датотеки, испраќање работите, кои душкаат вашиот сообраќај, буквално се може да биде инјектира во компјутер. И така на buffer overflow напад на неговото јадро е само глупав, глупав исклучително важна за низа што немаа неговите граници се провери. И тоа е она што е супер опасни и истовремено супер моќен во C е дека ние навистина имаат пристап до кое било место во меморијата. Тоа е до нас, програмери, кои пишуваат на оригиналниот код за да се провери на должината на која било ебам низи, дека ние сме манипулирање. Значи да биде јасно, она што е лек? Ако ние се тркалаат назад кон оваа код, што не треба само да промена на должината на лентата, што друго треба да биде проверка? Што друго треба да се прави за да се спречи овој напад целосно? Не сакам да кажам само слепо дека треба да ја копирате колку бајти како што е должината на бар. Сакам да кажам, копирајте како многу бајти што се во бар до распределени меморија, или 12 максимално. Па ми треба некој вид на услов ако која прави проверувате должината на лентата, но ако тоа е над 12, ние само тешко код 12 како максимално можно растојание. Инаку т.н. тампон overflow напад може да се случи. На дното на оние слајдови, Ако сте љубопитни за да прочитате повеќе е вистински оригиналниот напис ако сакате да ги погледне. 

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

Така што ова е само еден куп на зборови и дефиниции за нешто што се нарекува дрво во компјутер науката, многу сличен на семејно стебло. Но, има и познавач инкарнации на дрвја, од кои една се нарекува бинарни пребарување дрво. И може да се вид на шега освен што е ова нешто што го прави тоа. Па, тоа е бинарна во која смисла? Каде на бинарни дојде од тука? Жал ми е? Тоа не е толку многу на едниот или. Тоа е повеќе дека секој од јазлите нема повеќе од две деца, како што гледаме тука. Во принцип, tree-- и вашите родители и дедовци може да има колку деца или grandkids како тие всушност сакаат, и така на пример, ние имаме три деца исклучи дека десната рака јазол, но во бинарно дрво, на јазол има нула, еден, или две деца максимално. И тоа е убав имот, затоа што ако тоа се ограничени од страна на две, ние ќе треба да биде во можност да добие малку најавите база две акција се случува тука во крајна линија. Па ние имаме нешто логаритамски. Но повеќе за тоа во еден момент. Барај дрвото значи дека бројките се подесен така што левата дете вредноста е поголема од корен. И правото на децата е поголема од корен. Со други зборови, ако се земе било кој од јазли, кругови во овој филм, и гледа во неговата лева детето и неговото право на децата, прво треба да биде помала од, вториот треба да биде поголема. Па разумност провери 55. Тоа е лево дете е 33. Тоа е помалку од. 55, своето право на детето е 77. Е поголем од. А тоа е рекурзивен дефиниција. Ние би можеле да се провери секој еден од оние јазли и истата шема ќе се одржи. 

Значи она што е убаво во бинарни пребарување дрво, е оној, ние може да се имплементира со struct, само се допаѓа тоа. И иако ние сме фрлање многу структури, ви, тие се малку интуитивен сега се надевам. Синтаксата е уште таинствениот сигурно, но содржината на еден јазол во овој context-- а ние продолжуваме користење на зборот јазол, без разлика дали е правоаголник на екранот или на круг, тоа е само некои генерички контејнер, во овој случај, на едно дрво, како што е оној видовме, ни треба цел број во секоја од јазли и тогаш ќе треба два покажувачи за покажување од лево детето и правото на децата, соодветно. Значи тоа е како да имплементира дека во struct. И тоа како би можел да се имплементира во код? Па, ајде да се земе брз се погледне на овој мал пример. Тоа не е функционална, но јас сум копирани и атипичен таа структура. И ако мојата функција за бинарна пребарување дрво се нарекува пребарување, и ова е потребно два аргументи, цел број N и покажувач на јазол, па покажувач на дрвото или покажувач кон коренот на дрвото, како можам да одат во врска со пребарувањето за N? Па, прво, затоа што јас сум кои се занимаваат со стрелки, Одам да се направи проверка на разумност. Ако дрвото еднаквите еднакво на нула, е N во ова дрво или не во ова дрво? Тоа не може да биде, нели? Ако сум во минатото нула, таму нема ништо. Јас како и едноставно слепо велат return false. Ако ми даде ништо, јас сигурно не може да најдете било кој број Н. Па што друго би можел да проверете сега? Јас ќе одам да се каже и на друго место, ако n е помалку од она што е на јазол од дрвото дека јас сум бил предаден N вредност. Со други зборови, ако бројот Јас сум бараат, N, е помал од јазол дека јас сум во потрага на. И јазол јас барам при што се нарекува дрво, и да се потсетиме од претходниот пример да се добие на вредност во покажувач, Јас го користам нотација на стрелката. Па ако N е помала од дрво со стрелки Н, сакам да се концептуално одат лево. Како да го изразат во потрага лево? Да биде јасно, дали ова е сликата е во прашање, и јас сум бил донесен дека врвниот arrow кој покажуваше надолу. Тоа е мојот дрво покажувачот. Јас сум посочувајќи на коренот на дрвото. И јас барам да речеме, за бројот 44, произволно. 44 е помала или поголема од 55 очигледно? Така, тоа е помалку од. Па така ова ако состојбата се однесува. Концепциски така, она што сакам да го пребарување следната ако јас сум во потрага по 44? Да? 

Точно, сакам да пребарување левата дете, или на лево под-дрво на оваа слика. И всушност, дозволете ми преку сликата долу тука за само еден миг, бидејќи Не можам да ја изгребат ова. Ако почнам тука во 55, и Знам дека вредноста 44 Го барам е да по левата страна, тоа е вид на како кинење на телефонот книга во половина или кинење на дрво на половина. Јас веќе не мора да се грижат за целата оваа половина од дрво. А сепак, за чудо, во смисла на структура, тоа нешто над тука дека започнува со 33, кој се е бинарни пребарување дрво. Реков зборот рекурзивен порано, бидејќи навистина ова е податочна структура што по дефиниција е рекурзивен. Може да имаат дрво кое е ова? големи, но секој еден од нејзините деца претставува дрво само малку помали. Наместо тоа да се биде дедо или баба, сега тоа е само мајка or-- не можам да не say-- мајка или тато, тоа ќе биде чудно. Наместо тоа, има две деца ќе биде како брат и сестра. Нова генерација на семејното стебло. Но структурно, тоа е истата идеја. И излегува имам функција со која можам да пребарување бинарна пребарување дрво. Тоа се нарекува пребарување. Барам N во дрвото со стрелка налево друго ако n е поголема од вредноста дека јас сум во моментов во. 55 во приказната пред еден миг. Имам функција наречена пребарување дека јас само може да N помине ова и рекурзивно пребарување под-дрво и само враќање што и тој одговор. Друго Имам некои конечниот база случај тука. 

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

Значи она што други проблеми може да се реши? Толку брз чекор подалеку од дрва за само еден миг. Тука е, велат, германската знаме. И таму е јасно образец за ова знаме. И има многу знамиња во светот, која се толку едноставно како ова во смисла на нивните бои и дезени. Но, претпоставувам дека ова е зачуван како .gif, Или JPEG, или bitmap, или пинг, било графичка датотека формат со која сте запознаени, некои од нив сме играјќи си со во PSET4. Ова не чини вредно да се сместат црни точки, црна пиксели, црн пиксел, точка, точка, точка, целиот куп на црна пиксели за прв scanline, или ред, а потоа цел куп исти, тогаш целиот куп од истата, а потоа куп на црвени точки, црвени пиксели, црвени пиксели, а потоа во целина куп на жолта пиксели, жолта, нели? 

Има таков неефикасност тука. Како би ја интуитивно компресира германското знаме ако спроведувањето како датотека? Како и што информации може да не мачи чување на дискот со цел да се намали големината на датотеката од нашите како мегабајти на килобајт, нешто помали? Кој лежи на вишок тука за да се биде јасно? Што можете да направите? Да? Токму така. Зошто да не, а не се сеќавам бојата на секој пиксел ебам исто како што го правиш во PSET4 со форматот на bitmap датотека, зошто не се само претставуваат најлевата колона на пиксели, на пример еден куп црни точки, еден куп на црвено, и еден куп на жолта, а потоа само некако се кодираат Идејата за повторување на овој 100 пати или да ја повтори оваа 1000 пати? Каде 100 или 1000 е само цел број, па да може да се извлечеш со само еден број наместо на стотици или илјадници на дополнителни пиксели. И навистина, тоа е како ние би можеле да ги компресирате во германското знаме. И Сега што е со француското знаме? И малку некој вид на ментална вежба, која знаме може да биде компресирана повеќе на дискот? Германското знаме или на француски јазик знаме, ако се земе овој пристап? Германското знаме, затоа што има повеќе хоризонтална вишок. А од страна на дизајнот, многу графички фајлови формати се навистина работат линии како скенирање хоризонтално. Тие би можеле да работат вертикално, само човештвото Пред одлучи години дека ќе генерално мислам на работите ред по ред наместо колона по колона. Значи, навистина, ако сте биле да се погледне на датотека големина на германското знаме и француски знаме, па додека резолуцијата е исти, со иста ширина и висина, и оваа тука се случува да биде поголема, затоа што треба да се повторува себе три пати. Треба да ја наведете сина, повторете себе, бела, повторувам себе, црвена, повторувам себе. Вие не може само да си одат сите начинот на правото. И како настрана, да се направи чистење на компресија е насекаде, ако овие се четири рамки од video-- вас да не се помисли дека некој филм или видео е генерално како 29 или 30 фрејмови во секунда. Тоа е како малку флип книга, каде што само да се види на сликата, слика, слика, слика, слика само супер брзо така што изгледа како актерите на екранот се движат. Еве еден бумбари пчела на врвот на еден куп цвеќиња. И покрај тоа што би можело да биде вид на тешко да се види на прв поглед, единственото нешто што се движи во овој филм е на пчела. 

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

Но како да се компресира текст? Како да одите за компресирање на текстот? Па, секој од ликовите во ASCII е еден бајт, или осум бита. И тоа е вид на нем, нели? Затоа што најверојатно тип А и Е и јас и О и У многу почесто отколку како W или П или Z, во зависност од јазикот на кој сте пишување, секако. И така зошто сме користење осум битови за секоја буква, вклучувајќи најмалку популарни писма, нели? Зошто не ја користите помалку битови за супер популарни букви, како Е, работите кои ви се погоди прв во Тркало на среќата, и употребата на повеќе битови за помалку популарни букви? Зошто? Бидејќи ние сме само ќе ги користат поретко. 

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

Јас? Јас? Или она about-- или јас? Можеби тоа е само две право на E? Значи има овој проблем на Можност за декодираwе со Морс код, при што, освен ако личноста со испраќање на порака всушност паузи за да може да се најде решение на види или слушне празнините меѓу буквите, тоа не е доволно само да се испрати поток од нули и единици, или точки и цртички, бидејќи има двосмисленост. Е е една точка, па ако види две точки или слушнете две точки, можеби тоа е два на E или можеби е еден И. Па ние треба систем кој е малку повеќе умен од тоа. Па еден човек по име Хафман години Пред излезе со токму тоа. Значи ние сме само ќе да се земе брз поглед колку дрва се соодветен за ова. Да претпоставиме дека ова е некој глупави пораката што сакате да ја испратите, составен од само А, Б, Ц на D и E е, но има голем број на технолошки вишок тука. Тоа не е замислена да биде на англиски јазик. Тоа не е шифрирана. Тоа е само глупава порака со многу повторување. Значи, ако сте всушност избројам сите А, Б, Ц, на D и Е, тука е фреквенцијата. 20% од писмата се А, 45% од писмата се Е, а три други фреквенции. Ние бројат до таму рачно и само го направи математика. 

Значи излегува дека Хафман, пред некое време, сфати дека, знаете што, ако се започне изградба дрво, или шумски дрвја, ако сакате, како што следува, јас да го направите следново. Одам да се даде еден јазол на секое од писмата кои ми значат а јас ќе одам да ги чувате во внатрешноста на тој јазол фреквенциите како подвижна запирка вредност, или можете да го користите еден N, исто така, но ние само ќе ги користат плови тука. И алгоритам кој тој предложи е тоа што вие искористам оваа шума од еден јазол дрвја, па супер кратки дрвја, и ќе почнете да ги поврзе со нови групи, новите родители, ако сакате. И можете да го направите ова со избирање на две најмалиот фреквенции во исто време. Земав 10% и 10%. Јас создаде нов јазол. И ќе се јавам на новиот јазол 20%. 

Кои два јазли јас се комбинираат следно? Тоа е малку нејасен. Значи има некои случаи ќош, за да се разгледа, но да се задржи нешта убава, Одам да се изберат 20% - Јас сега се игнорира деца. Одам да се изберат 20% и 15% и да подготви два нови рабови. И сега што два јазли ми е логично да се комбинираат? Игнорираат сите деца, сите внуци, само погледнете во корените сега. Кои два јазли можам да врзува заедно? Точка два и 0,35. Па дозволете ми да се подготви две нови рабови. А потоа Имам само уште една лева. Значи тука е дрво. И тоа е составен намерно да се погледне вид на убава, но забележите дека рабовите имаат се означени како нула и еден. Така што сите од левата страна рабовите се нула арбитрарно, туку постојано. Сите правото рабовите се оние. 

И уште па што Хофман предложени се применува, ако сакате да го претставува Б, наместо претставува број 66, како е ASCII која е осум целиот битови, знаеш што, само продавница шемата на нула, нула, нула, нула, затоа што тоа е патот од мојот дрво, дрво г. Хафман е, на лист од коренот. Ако сакате да се складира Е, од друга страна, не се испрати осум битови кои претставуваат Е. Наместо тоа, пратете што шема на битови? Еден. И она што е убаво за ова е Е дека е најпопуларниот писмо, а ти си со користење на најкраткиот код за него. Следниот најпопуларниот писмо изгледа како тоа беше А. И така колку битови тој го предлага користење за тоа? Нула, еден. 

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

Па таму е податочна структура познат како хаш табелата. И хаш табелата е вид на се излади со тоа, што има кофи. И претпоставувам има четири кофи тука, само четири празни места. Еве еден шпил карти, и тука е клуб, лопата, клуб, дијаманти, клуб, дијаманти, клуб, дијаманти, clubs-- така што ова е случаен. Срца, hearts-- па јас сум bucketizing сите влезови тука. И потреби хаш табелата да се погледне во вашиот влез, а потоа го стави во одреден врши врз основа на она што го гледате. Тоа е алгоритам. И јас бев со користење на супер нагледни алгоритам. Најтешкиот дел од која е сеќавајќи се што се сликите. И тогаш има вкупно четири нешта. 

Сега Купишта растеа, која е нешто однапред испланирани тука. Но, што друго би можеле да направам? Така всушност, тука имаме куп на старата школа испит книги. Да претпоставиме дека еден куп на студентите имиња се овде. Еве еден поголем хаш табелата. Наместо четири кофи, Јас сум, да речеме 26. И ние не сакаме да одиме позајми 26 работите од надвор [? Annenberg?], Па Еве пет кои претставуваат A до Ш И ако јас види студент чие име започнува со, Одам да се неговите или нејзините квиз стави таму. Ако некој почне со C, таму, A-- всушност, не сакав да го направите тоа. Б оди овде. Па имам A и B и C. И Сега тука е уште еден студент. Но, ако ова хаш табелата е реализира со низа, Јас сум вид на зезнав во овој момент, нели? Јас вид на треба да се стави ова некаде. 

Значи еден начин може да се реши овој е, сите право, е зафатен, Б е зафатен, Ц е зафатен. Одам да го стави во Д. Значи во прв, јас имаат случаен брз пристап за секој од кофи за студентите. Но, сега тоа е вид на пренесените во нешто линеарна, зашто ако сакате да пребарувате за некој чие име започнува со, јас проверете тука. Но, ако тоа не е на А Студентот го барам, Јас вид на мора да започне проверката кофи, затоа што она што го направив беше вид на линеарно пикаат податоците структура. А глупав начин да се каже само да се погледне за првиот достапен отворањето, и да се стави како план Б, така да се каже, или план Д во овој случај, на вредноста наместо во таа локација. Ова е исто така што ако сте доби 26 локации, а не учениците со П име или Z, или нешто слично дека, барем сте со користење на просторот. 

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

И така хаш табелата е структура кои би можеле да изгледаат исто како овој, но повеќе умно, може нешто што се нарекува одделни врзувањето, при хаш табелата едноставно е низа, секој од чии елементи не е број, себе е поврзана листа. Така што ќе добие супер брз пристап одлучувањето за тоа каде да се хаш вашата вредност. Слично како со примерот на картички, Јас направив супер брзи одлуки. Хартс оди овде, дијаманти оди овде. Исто тука, оди овде, Д оди овде, Б оди овде. Така супер брз гледам-up прозорци, и ако да се случи да се кандидира во случај каде што имаш судири, две лица со исто име, и потоа само на проектот ги поврзува. А можеби и ќе продолжи да ги решат по азбучен ред, а можеби и не. Но барем сега имаме динамика. Значи, од една страна имаме супер брз постојана време, и вид на линеарна време вклучени ако овие поврзани листи да почне да се добие малку долго. 

Така овој вид на глупо, geeky пред шега години. На CS50 hack-а-thon, кога студентите се провери, некои ТФ или CA секоја година смета дека тоа е смешно да се стави знак како овој, каде што само значи ако вашето име започнува со А, одат на овој начин. Ако почне вашето име со Б, оди this-- ред, тоа е смешно, можеби и подоцна во текот на семестарот. Но, има уште еден начин за тоа, исто така. Се вратам на тоа. 

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

Па така ова е податочна структура. И ако се погледне од врвот до дното, како ако погледнете во горниот јазол таму, М, е што укажува на најлевата нешто таму, кој е тогаш А, X, W, E, L, L. Оваа е само податочна структура која произволно Дали земањето на имињата на луѓето. И Максвел се чуваат од само по патот на низа во низа во низа. Но, она што е неверојатно за Trie е дека, со оглед на поврзани листа, па дури и низа, најдобриот што некогаш сте добиле е линеарно време или логаритамски време во потрага некого. Во оваа податочна структура на Trie, ако моите податоци структура има едно име во неа и јас сум во потрага за Максвел, јас сум случува да го најдете прилично брзо. Јас само да се погледне за М-А-Х-W-Е-Л-L. Ако оваа податочна структура, пак, Ако n е еден милион, ако има милиони имиња во оваа податочна структура, Максвел се уште се случува да се биде видлив по само M-A-X-W-E-L-L чекори. И David-- Д-А-В-јас-Д чекори. Со други зборови, со изградба структура која е податоци сиве овие низи, од кои сите се издржуваат случаен пристап, Можам да почнете да барате до луѓето именува со користење на износот на време дека е пропорционален не бројот на работи во податочна структура, како милион постоечки имиња. На износот на време ми треба да се најде M-A-X-W-E-L-L во оваа структура на податоци е пропорционална не на големина на податочна структура, но за должината на името. И реално на имиња ние сме во потрага нагоре никогаш не се случува да се биде луд долго. Можеби некој има 10 карактер именува, 20 карактер име. Тоа е секако конечни, нели? Постои човек на Земјата, кои има најдолг можен име, но тоа име е постојана должина вредност, нели? Тоа не се разликуваат во секоја смисла на зборот. Така на овој начин, ние сме постигне структура на податоци тоа е постојана време погледнете-up. Тоа не се голем број на чекори во зависност од должината на внесување, но не и бројот на името во структурата на податоци. Значи, ако ние го удвои бројот на имиња следната година од една милијарда до две милијарди долари, наод Максвел се случува да се земе точно ист број на седум чекори да го најдам. И така ние се чини дека за да се постигне нашите светиот грал на водење на време. 

Па неколку брзи известувања. Квиз нула доаѓа. Повеќе за тоа на веб-страницата на курсот во текот на следните неколку дена. Понеделник lecture-- е празник тука на Харвард во понеделникот. Тоа не е во Њу Хевн, па ние сме преземање на класата до Њу Хевн за предавање во понеделникот. Се што ќе се снима и емитувана во живо, како и обично, но ајде да заврши денес со 30 вториот клип наречен "длабоки мисли" од страна на Daven Farnham, која бил инспириран од минатата година до сабота "Длабоки мисли" Night Live е Џек Практични, која сега треба да се направи смисла. 

Филм: И сега, "Длабоко Мисли "од Daven Farnham. Хаш табелата. 

ЗВУЧНИЦИ 1: Добро, тоа е тоа за сега. Ќе се видиме следната недела. 

Даг: За да го видите во акција. Па ајде да ги разгледаме во тоа токму сега. Па еве, имаме несортиран низа. 

Иан: Даг, ќе може да оди напред и да го рестартирате тоа за само една секунда, ве молам. Добро, камери се тркалаат, па акција секогаш кога ќе бидете подготвени, Даг, во ред? Даг: Добро, па она што го имаме тука е несортиран низа. И јас сум во боја од сите елементи црвено за да се покаже дека тоа е, всушност, несортиран. Така се потсетиме дека првото нешто што го направи е ги сортирате левата половина на низата. Тогаш ние се најде решение за правото половина на низата. И ти-да, Ya-де, Ya-да, ние ги спои заедно. И имаме целосно подредени низа. На тој начин се спојат вид работи. 

Иан: Леле, Леле, Леле, сече, се сече, се сече, се сече. Даг, вие не само да ти-да, ти-да, Ya-да, на вашиот пат низ спојување вид. 

Даг: Јас само го направи. Во ред е. Ние сме добро да отидевме. Ајде да ги задржи тркалање. Значи во секој случај, 

Иан: Треба да се објасни тоа уште повеќе од тоа. Тоа едноставно не е доволно. Даг: Иан, ние не треба да се врати во еден. Во ред е. Значи во секој случај, ако продолжиме со merge-- Иан, ние сме во средината на снимањето. 

Иан: Знам. И ние не може само ти-да, ти-да, Ya-да, во текот на целиот процес. Што треба да се објасни како Двете страни се спои заедно. 

Даг: Но, ние сме веќе објаснува како две sides-- 

Иан: Вие сте само што е прикажано им присоединување низа. Даг: Знаат процесот. Тие се во ред. Ние сме поминале повеќе од десет пати. 

Иан: Вие само прескокнаа право над неа. Се враќаме на еден, можете нели ти-да, Ya-da над неа. Добро, назад кон една. 

Даг: Морам да се вратам преку сите слајдови? Господе. Тоа е како шести пат, Јан. Во ред е. 

Иан: Во ред. Дали сте подготвени? Одлично. Акција.