[Музички] Дејвид Џ MALAN: Во ред. Ова е CS50. Ова е недела пет продолжува, а ние има некои добри вести и некои лоши вести. Па Добрата вест е дека CS50 започна овој петок. Ако би сакале да ни се придружат, се упатат кон вообичаените рачно тука. Уште подобра вест, нема предавање ова доаѓа понеделник 13-ти. Малку помалку подобра вест, квиз нула е следната среда. Повеќе детали може да биде најдат на овој URL тука. И во текот на следните неколку дена ние ќе се пополнување на празни места во однос на соби дека ќе се задржани. Подобра вест е дека таму ќе биде разбира ширум преглед седница оваа доаѓаат Понеделник навечер. Stay tuned до на курсот веб-страница за локација и детали. Делови, иако тоа е празник, ќе се сретне и како и. Најдобрата вест, предавање следниот петок. Значи ова е традиција имаат, како на наставната програма. Just-- тоа се случува да биде неверојатно. Ќе видите работи како постојана време структури на податоци и хаш маси и дрва и се обидува. И ние ќе зборуваме за роденден проблеми. А целиот куп на работи чека следниот петок. Во ред. Во секој случај. Така се потсетиме дека ние сме фокусирајќи се на оваа слика на она што е во внатрешноста на меморија нашиот компјутер. Значи меморија или RAM меморија е местото каде што програми постојат додека си ги работи. Ако ќе кликнете двапати на иконата за да се кандидира на некои програма или со двоен клик на иконата за да го отворам во некои датотеки, тоа е натоварен од вашиот хард диск или цврста состојба диск во RAM меморија, Случаен Пристап меморија, каде тоа живее до моќта заминува, на лаптопот се затвора, или ќе ја завршите програмата. 

Сега дека меморија, кои најверојатно имаат 1 гигабајт овие денови, 2 гигабајти, или дури и многу повеќе, генерално се утврдени за одредена програма во овој вид на правоаголна концептуален модел при што имаме магацинот на дното и еден куп други нешта на врвот. Нешто во самиот врв видовме на оваа слика пред, но никогаш не зборуваше за е т.н. текст сегмент. Текстот сегмент е само стилизиран начин на велејќи дека нули и оние кои компонира вашиот вистински состави програма. 

Значи, кога ќе кликнете двапати на Microsoft Word на вашиот Mac или PC, или кога ќе ја стартувате точка намали Марио на Линукс компјутер во вашиот терминал, на нули и единици кои ја сочинуваат Збор или Марио се чуваат привремено во RAM меморија на вашиот компјутер во т.н. текстот сегмент за одредена програма. Под што оди иницијализира и Uninitialized податоци. Ова е нешто како глобални променливи, дека не сум користел многу од, но понекогаш ние сме имаше глобални променливи или статички дефинирани стрингови кои е хард кодирани зборови како "здраво" кои не се земени во од страна на корисникот кои се хард-кодирани во вашата програма. 

Сега, одредување на дното ние имаат т.н. оџак. И магацинот, досега, ние сме користење за какви цели? Што е оџакот се користи за? Да? 

ПУБЛИКАТА: Функции. 

Дејвид Џ MALAN: За функции? Во која смисла за функции? 

ПУБЛИКАТА: Кога ќе се јавите на функција, аргументи се копирани врз оџакот. 

Дејвид Џ MALAN: Токму така. Кога ќе се јавите на функција, нејзиниот аргументи се копирани врз оџакот. Така било на X или Y или А или Б дека сте поминува во функција привремено се стави на т.н. стек, како еден од Annenberg јадење салата сад, а исто така работи како локални променливи. Ако вашиот foo функција или вашиот swap функција има локални променливи, како Temp, овие две заврши на магацинот. Сега, ние нема да зборуваме премногу за нив, но овие животната средина променливи на дното видовме пред некое време кога Бев futzing на тастатурата еден ден и јас почнав да пристапуваат работи како argv 100 или argv 1000, само elements-- заборавам на numbers-- но тоа не требаше да се пристапи од страна на мене. Почнавме да гледате некои фанки симболи на екранот. Тоа беа таканаречените животната средина променливи како глобалните поставувања за мојата програмата или за мојот компјутер, не поврзани со последните грешка што зборувавме, Shellshock, тоа е се оптоваруваат неколку компјутери. 

Сега на крај, во денешниот фокус ние на крајот ќе биде на грамада. Ова е уште една парче од меморијата. И во основа сите овие меморија е истата работа. Тоа е истиот хардвер. Ние сме само вид на лекување на различни кластери на бајти за различни намени. Грамада е, исто така, ќе биде каде променливи и меморијата што ќе го побарате од оперативниот систем привремено се чуваат. 

Но, има еден вид на проблем тука, како на сликата подразбира. Ние вид на имаат два бродови за да се судираат. Бидејќи, како што имате потреба при користење се повеќе и повеќе на магацинот, и како што гледаме денес па натаму, како што се користи се повеќе и повеќе на грамада, сигурно лоши работи може да се случи. И навистина, што може да предизвика дека намерно или ненамерно. Па cliffhanger последен време беше оваа програма, кои не служат било функционална друга цел, освен да се демонстрира колку вас, како лошо момче всушност може да се Предноста на грешки во нечија програма и да се преземе на програмата, па дури и целиот компјутерски систем или серверот. Па само да се загледувам кратко, можете забележи дека главниот на дното зема во командната линија аргументи, како на argv. И има повик на функција f, суштина безимени функција наречена ѓ, а тоа е поминува во avg [1]. 

Значи она што зборот на корисникот видови во во брза по името на оваа програма, а потоа оваа произволна функција до врвот, ѓ, ги зема во низа, АКА char *, како што ние си почнал да разговараат, и тоа само го нарекува "бар". Но, ние би можеле да го наречеме нешто. А потоа се декларира, во внатрешноста на f, низа на карактери наречен c-- 12 такви карактери. 

Сега, според расказот бев кажувам пред една момент, што во меморијата е в, или оние 12 знаци ќе заврши? Само за да биде јасно. Да? 

ПУБЛИКАТА: На оџакот. 

Дејвид Џ MALAN: На оџакот. Па в е локална променлива. Бараме 12 карактери или 12 бајти. Тие се случува да се заокружи на т.н. оџак. Сега конечно е тоа друга функција тоа е всушност прилично корисна, но не сум навистина се користи тоа самите себеси, strncopy. Тоа значи низа копија, но само n писма, n карактери. Па n знаци ќе бидат копирани од бар во в. И колку? Должината на бар. Значи со други зборови, една линија, strncopy, се случува да го копирате ефикасно бар во в. 

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

ПУБЛИКАТА: Не вклучува простор за нула карактер. Дејвид Џ MALAN: не вклучува простор за нула карактер. Потенцијално, за разлика од досегашната практика ние дури и не имаат толку многу како плус 1 до го исполниме тоа null карактер. Но, тоа е уште полошо од тоа. Што друго што не успеаја да направам? Да? 

ПУБЛИКАТА: [Беззвучен] Дејвид Џ MALAN: Совршена. Ние сме хард кодирани 12 прилично произволно. Тоа не е толку проблем, но факт дека ние не сме дури и проверка дали должината на лентата е помалку од 12, во кој случај ќе биде безбедно да го стави во меморија наречен C дека ние сме распределени. Навистина, ако бар е како 20 карактери, оваа функција се чини дека копирање 20 ликови од бар во C, а со тоа земајќи најмалку 8 бајти дека тоа не треба да биде. Тоа е импликацијата тука. 

Значи во кратки, скршени програма. Не толку голем договор. Можеби ќе добие сегментација грешка. Ние сме сите имаа грешки во програми. Сите ние би можеле да имаат грешки во програмите од сега. Но она што е импликација? Па, тука е zoomed во верзија на таа слика на меморија мојот компјутер. Ова е дното на моето оџак. И навистина, на самото дно е она што е наречен родител рутински оџакот, фенси начин да се каже дека е главен. Така што секој кој се нарекува функцијата ѓ дека ние зборуваме за. Значи ова е на дното од оџакот. Врати адреса е нешто ново. Тоа е секогаш таму, секогаш биле во таа слика. Ние само никогаш не се јавиле внимание на тоа. Затоа што се покажува начинот на кој функционира е ц дека кога една функција повикува друга, не само што аргументи за таа функција се турка врз оџакот, не само локално на функцијата променливи се турка врз оџакот, нешто што се нарекува врати адреса исто така, добива се стави врз оџакот. Поточно, ако главната повици Foo, главниот на адреса во меморијата, волот нешто, ефикасно добива се стави врз оџакот така што кога f е направено негово извршување знае каде да скокнете назад во текстот сегмент со цел да се продолжи извршување. 

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

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

И само за нотни цели, забележите во горниот лев агол е она што ќе биде в заградата 0 и потоа малку надолу на правото е в заградата 11. Значи со други зборови, може да се замисли дека има мрежа на бајти таму, од кои првиот е горниот лев агол, долниот дел кој е последниот од тие 12 бајти. 

Но, сега се обидуваат да премотувате напред. Што ќе се случи ако се помине во низа бар што е повеќе од в? И ние не сме проверка дали тоа е навистина повеќе од 12. Кој дел од оваа слика се случува да се се препишани од страна на бајти 0, 1, 2, 3, точка точка точка, 11, и потоа лошо, 12, 13 до 19? Што ќе се случи тука, ако заклучиме од нарачување дека в заградата 0 е на врвот и в заградата 11 е вид на долу на правото? Да? 

ПУБЛИКАТА: Па, тоа се случува да ја пребришете char * бар. 

Дејвид Џ MALAN: Да, тоа изгледа како ви се случува да ја пребришете char * бар. И уште полошо, ако пратите во навистина долго стринг, вие може дури да ја пребришете што? Враќање адреса. Кои, повторно, е исто како Breadcrumb да ја каже програма, каде да се вратам на кога ѓ се прави се нарекува. 

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

Штом вашата програма се урна, тоа е неверојатно нешто. Затоа што тој мисли или таа откри она што е веројатно навистина е бубачка. А потоа тие можат да добијат повеќе умен и почна да се фокусира потесно за тоа како да ги искористат дека бубачка. Особено, она што тој или таа може да направите е да испратите, во најдобар случај, здраво. Нема ништо страшно. Тоа е стринг кој е доволно кратко. Но, што ако тој или таа праќа, и ние ќе го генерализира како, напад code-- така нули и оние кои ги прават работите како rm-rf, кој се отстрани сè од хард диск или испрати спам или некако го нападне машина? 

Значи, ако секој од овие писма А само претставува, Концептуално, напад, напад, напад, напад, некои лоши код дека некој друг напишал, но ако тоа лице е доволно паметни не само да ги вклучи сите на оние RM-Едукација, но, исто така, има неговата или нејзината последните неколку бајти има голем број што одговара на адресата на неговиот или нејзината сопствена напад кодот дека тој или таа помина во само преку обезбедување на тоа во конзолата, можете успешно да трик на компјутер во забележи кога ѓ се прави извршување, ох, тоа е време за мене да скокаат назад кон црвениот враќање адреса. Туку затоа што тој или таа има некако поклопуваа дека враќањето адреса со свои број, и тие се доволно паметни да ги конфигурирате што број да се однесуваат, како што види во супер врвот лев агол таму, вистинската адреса во компјутер меморија на некои од нивните напад код, лошо момче може да трик на компјутер во извршување на неговата или нејзината сопствена код. 

И тој код, пак, може да биде ништо. Тоа е обично се нарекува школка код, што е само начин да се каже дека тоа не е генерално нешто едноставно како rm-rf. Тоа е всушност нешто како баш, или вистински програма која му дава или нејзините програмски контрола да се изврши нешто друго што тие сакаат да. Значи во кратки, сето ова произлегува од едноставниот факт дека овој баг се вклучени не проверка границите на вашиот низа. И поради начинот на кој компјутери работа е тоа што тие користење на магацинот од ефикасно, концептуално, дното на нагоре, но потоа на елементи ве одвлече во магацинот расте врвот надолу, ова е неверојатно проблематична. Сега, постојат начини да се работи околу тоа. И искрено, постојат јазици со кој да работи околу ова. Јава е имун, на пример, да ова конкретно прашање. Бидејќи тие не ви даде совети. Тие не ви даде директни приклучоци за мемориски адреси. Значи со оваа моќ што ја имаме да се допре нешто во меморијата ние сакаме доаѓа, очигледно, голем ризик. 

Па да се внимава надвор. Ако, искрено, во месеците или годините што доаѓаат, во секое време ќе прочитате за некои експлоатација на програма или сервер, Ако некогаш сте се види навестување на нешто како на buffer overflow напади, или магацинот претекување е друг вид на напад, слични во духот, колку што инспирира на веб страницата име, ако го знаете, тоа е сите зборуваат за само преплавени со големина на некои карактер низа или низа некои поопшто. Било какви прашања, тогаш, за ова? Не се обиде ова дома. 

Во ред. Па Примерок досега е нашата нова пријател со тоа што може да се алоцира меморија дека ние не мора да знаете во однапред дека ние сакаме ние немаме на хард код во нашата програма броеви како 12. Еднаш на корисникот ни кажува колку податоци тој или таа сака да влез, можеме да Примерок дека многу меморија. 

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

Но, на грамада е тука. И она што е убаво за Примерок е дека кога Примерок доделува меморија до тука, тоа не е влијание, за најголем дел, од магацинот. И така било функција да пристапите меморија која е malloc'd, дури и од страна на функција како getstring, дури и откако ќе се враќа. 

Сега, обратно од Примерок е бесплатно. И навистина, правило треба да започне усвојување е било, било, во секое време да го користите Примерок можете сами да користат бесплатен, на крајот, на истиот покажувач. Сето ова време ние сме биле пишување кабриолет, кабриолет код, за многу причини. Но, еден од кои е со користење на CS50 библиотека, која сам по себе е намерно кабриолет, тоа протекување меморија. Секое време си се нарекува getstring во текот на изминатите неколку недели бараме оперативниот систем, Линукс, за меморија. А ти никогаш не еднаш го даде назад. И ова не е, пракса, добра работа. 

И Valgrind, еден од алатки воведе во Pset 4, е за сите да ви помогнеме, сега се најдат грешки како што. Но, за среќа за Pset 4 не треба да се користи CS50 библиотека или getstring. Така било грешки поврзани со меморијата се во крајна линија ќе биде своја. 

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

Па низа изгледаше вака. И она што беше клучен за околу еден низа е тоа што ви дава назад-до-назад делови од меморија, од кои секој ќе биде од ист тип, цел број, int, int, int, или знак, знак, знак, знак. Но, има неколку недостатоци. Ова на пример, е низа на големината шест. Да претпоставиме дека се пополни оваа низа со шест броеви и потоа, за било кои причини, Вашиот корисникот сака да даде ќе седми број. Каде ќе го стави? 

Она што е решението ако имате создаде низа на магацинот, на пример, само со недела две нотација дека ќе воведе, квадратни загради со голем број внатре? Па, имаш шест броеви во овие кутии. Што ќе биде вашиот инстинкт? Каде што ќе сакате да го стави? 

ПУБЛИКАТА: [Беззвучен] 

Дејвид Џ MALAN: Молам? 

ПУБЛИКАТА: Стави ја на крај. 

Дејвид Џ MALAN: Стави ја на крај. Па само во текот на правото, надвор од ова поле. Кој ќе биде убаво, но тоа испоставува дека не може да го стори тоа. Бидејќи ако не го праша за ова парче од меморијата, тоа би можело да биде случајно што ова се користи од страна на некои други променливи заедно. Сетам една недела или така кога ние положи надвор Zamyla и Davin и Габе имиња во меморијата. Тие беа буквално назад да се врати за да се врати. Па не можеме да мора да верувам дека она што го овде е на располагање за мене да го користите. 

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

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

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

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

Па што ако, наместо само чување на броеви, како 9, 17, 22, 26, 34, што ако ние не се чуваат само број, но покажувач до секој таков број? Така што многу како тебе би се нишка на игла низ целиот куп на ткаенина, некако врзување работи заедно, на сличен начин може да ние со покажувачи, како инкарниран со стрелка тука, вид на ткаат заедно овие индивидуални правоаголници од страна на ефикасно користење на покажувач до секој број кој укажува на некои следната број, односно укажува, пак, некои следниот број? Значи со други зборови, она што ако ние всушност сакаа да се спроведе вакво нешто? И за жал, овие правоаголници, барем на еден со 9, 17, 22, и така натаму, овие се веќе убав плоштади со еден броеви. На дното, правоаголник под 9, на пример, го претставува она што треба да биде покажувач, 32 бита. Сега, јас не сум свесен за било кој тип на податоци во C која ви дава не само int но покажувач заедно. 

Значи она што е решението ако сакаме да измисли свој одговор на ова? Да? 

ПУБЛИКАТА: [Беззвучен] 

Дејвид Џ MALAN: Што е тоа? 

ПУБЛИКАТА: Нова структура. 

Дејвид Џ MALAN: Да, па зошто да не се создаде нова структура, или во C, на struct? Видовме structs пред, ако на кратко, каде што се занимаваа со структурата на учениците вака, кој имаше име и куќа. Во Pset 3 Збег сте користеле целина куп на structs-- GRect и GOvals дека Стенфорд создаден за да се кластер информации заедно. Па што ако се земе истата идеја клучни зборови "typedef" и "struct" а потоа некои студент специфични нешта, и се развива ова на следниов начин: typedef struct node-- и јазол е само многу генерички компјутерски науки термин за нешто во податочна структура, контејнер во податоци структура. А јазол тврдам се случува да имаат на int n, сосема јасна, а потоа малку повеќе cryptically, оваа втора линија, struct јазол * следната. Но за помалку технички термини, што е тоа втора линија на код во внатрешноста на големи загради? Да? 

ПУБЛИКАТА: [Беззвучен] Дејвид Џ MALAN: А Покажувач на друг јазол. Значи, мора да признаеме, синтакса малку криптичната. Но, ако го чита буквално, следната е името на променливата. Каков е нејзиниот тип на податок? Тоа е малку опширниот тоа време, но тоа е од типот struct јазол *. Секое време видовме нешто ѕвезда, кој значи дека е покажувачот во тој тип на податок. Значи следниот е очигледно Покажувач на struct јазол. 

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

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

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

Значи, ако ние сега сака да започне спроведување на овој поврзана листа, како можеме да ги претвориме нешто како ова да кодот? Па, ајде да ја видите пример за програма со која всушност користи поврзана листа. Меѓу денешните дистрибуција код е програма наречена Листа на нула. И ако јас ја извршите оваа Јас создаде супер едноставен GUI, графички кориснички интерфејс, но тоа е навистина само printf. И сега сум дадени себе неколку мени options-- Избриши, Insert, пребарување, и Траверс. И да престанам. Ова се само заеднички операции на податоци структура позната како линк листа. 

Сега, Избриши се случува да се избришете некој број од листата. Вметнете се случува да додадете голем број на листата. Пребарување се случува да се погледне за бројот на листата. И напречни е само стилизиран начин каже, прошетка низ листата, печати ја надвор, но тоа е тоа. Не го менува во било кој начин. 

Па ајде да се обидеме ова. Ајде да одиме напред и тип 2. А потоа јас ќе одам да внесете го бројот, велат 9. Enter. И сега мојата програма е само програмирани да се каже, листата сега е 9. Сега, ако јас одам напред и ставајте повторно, да мене оди напред и одзумирате и тип во 17. Сега мојата листа е 9, тогаш 17. Ако го направам внесете повторно, да прескокнете едно. Наместо 22, како на сликата ние сме гледа во тука, дозволете ми скок напред и вметнете 26 следната. Па ќе одам да напишеш 26. Листата е како што се очекува. Но, сега, само за да се види дали овој код се случува да се биде флексибилен, дозволете ми сега тип 22, кои најмалку Концептуално, ако ние сме Задржување на оваа сортирани, што е навистина ќе биде уште еден гол токму сега, треба да одат во меѓу 17 и 26. Па јас хит Enter. Всушност, тоа функционира. И така сега дозволете ми да го вметнете последните, по сликата, 34. 

Во ред. Па за сега дозволете ми да пропише дека Бришење и Траверс и Барај направи, всушност, работат. Всушност, ако јас се кандидира Барај, да пребарување на број 22, Enter. Го најде 22. Значи тоа е она што ова Програмата Листа Нулта прави. 

Но, она што е, всушност, се случува на која спроведува ова? Па, прво јас би можеле да имаат, и навистина Јас немам, фајл наречен list0.h. И некаде таму е овој линија, typedef, struct јазол, тогаш имам големи загради, int n и тогаш struct-- она ​​што беше дефиниција? Struct јазол следната. Значи ние треба ѕвездата. Сега технички да се влезе во навика за цртање овде. Можете да видите учебници и онлајн референци го направи таму. Тоа е функционално еквивалентни. Всушност, ова е малку повеќе типични. Но, јас ќе биде во согласност со она што ние го сторивме последен пат и го направите тоа. А потоа на крај, јас ќе одам да го направите тоа. 

Значи во заглавието на датотеката некаде, во list0.h денес е ова struct дефиниција, а можеби и некои други работи. Во меѓувреме, во list0c има ќе биде неколку работи. Но, ние се случува да се само проектот и да не заврши ова. List0.h е датотека сакам да се вклучат во мојот Ц датотека. А потоа во некој момент јас сум ќе мора int, главно, неважечки. А потоа јас ќе одам да имаат некои to-do е овде. Јас сум исто така се случува да имаат прототип, како неважечки, пребарување, int, n, чија цел во животот е да пребарувате за елемент. И тогаш овде тврдам во денес код, празнина, пребарување, int, n, нема запирка, но отворена големи загради. И сега сакам да некако пребарување за елемент во листата. Но, ние немаме доволно информации на екранот сеуште. Не сум всушност претставен на листата себе. Значи еден начин ние би можеле да се имплементираат поврзана листа во програма е јас вид на сакаат да направат нешто како изјавувам поврзана листа тука. За едноставност, јас ќе одам да се направи оваа глобална, иако во принцип ние не треба да го направите тоа премногу. Но, тоа ќе се поедностави овој пример. Па сакам да се изјаснат поврзана листа тука. Сега, како би можел да го направам тоа? 

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

ПУБЛИКАТА: Ние треба покажувач на еден јазол. Дејвид Џ MALAN: покажувач на еден јазол. Особено, кој јазол би Вашиот инстинкти биде да се задржи покажувач? 

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

Дејвид Џ MALAN: Да, веројатно само првиот. И ќе забележите, првата јазол е поинаков облик. Тоа е само половина од големината на struct, затоа што тоа е навистина само покажувач. Значи она што навистина може да направите е да се изјасни поврзана листа да биде од типот јазол *. И ајде да го наречеме прв и да се иницијализира на нула. Значи нула, повторно, е што доаѓаат во сликата тука. Не само што е null користи како како посебен повратната вредност за нешта како getstring и Примерок, нула е исто така на нула покажувачот, недостатокот на покажувачот, ако сакате. Тоа само значи ништо не е уште тука. Сега прво, јас би можеле да го ова го нарече нешто. Можев да го нарече "листа" или било кој број на други работи. Но јас сум нарекувајќи го "прва", така што тоа линии со оваа слика. Па само како стринг може да се претстави со адреса на својот прв бајт, па може да биде поврзана листа. И ќе видиме други податоци структури да бидат претставени со само еден покажувач, 32-битен стрела, покажувајќи на самиот прв јазол во структурата. 

Но сега да се предвиди проблем. Ако јас сум само сеќавајќи во мојата програма на адресата на првиот јазол, првиот правоаголник во оваа податочна структура, што беше подобро да биде случај за имплементација на остатокот од мојот листа? Што е клучен детали што се случува за да се обезбеди ова всушност се работи? И од "всушност работи" Јас значи, слично како стринг, ни овозможува да одат од првиот карактер во името на Davin на втората, на третата, на Четврто, на самиот крај, како да знаеме кога сме на крајот на поврзани листа што личи ова? Кога тоа е нула. И јас сум претставен овој вид на како како електро инженер моќ, со малку заземјување симбол, на сорти. Но тоа само значи нула во овој случај. Можете да го нацрта било кој број начини, но овој автор се случи да го користите овој симбол тука. 

Толку долго како што ние сме stringing сите од овие јазли заедно, само сеќавајќи се, каде првиот е, се додека како што се стави посебен симбол на последен јазол во листата, и ние ќе го користите нула, затоа што тоа е она што го имаме на располагање, оваа листа е завршена. И дури и ако јас само ви даде покажувач првиот елемент, можете, на програмерот, секако, може да пристапите на остатокот од неа. Но, ајде да ги споделите вашите мисли талкаат малку, ако тие не се веќе доста wandered-- што е ќе биде во времетраење од наоѓање на нешто во оваа листа? По ѓаволите, тоа е голема О на n, што не е лошо, во праведноста. Но, тоа е линеарна. Сме се откажале што функција на низи со поместување повеќе кон оваа слика на динамички плетени заедно или се поврзани јазли? Ние сме се откажале случаен пристап. Низа е убаво, бидејќи математички што е назад да се врати за да се врати назад. Иако оваа слика изгледа убаво, па дури и и покрај тоа што изгледа како овие јазли се убаво распоредени покрај, во реалноста тие можат да бидат секаде. Ox1, Ox50, Ox123, Ox99, овие јазли можат да бидат секаде. Бидејќи Примерок прави алоцира меморија од грамада, но никаде во грамада. Вие не мора да знаете дека тоа е ќе биде да се врати назад кон назад. И така оваа слика во реалноста на нема да биде доста оваа убава. 

Па затоа се случува да се земе малку работат на спроведување на оваа функција. Значи, да се спроведе пребарување сега. И ќе видиме каков вид на паметен начин да се направи ова. Значи, ако јас сум за пребарување функција и Јас сум со оглед на променливата, број n да барате, треба да знаете нова синтакса за потрага во од структурата што е посочи, да се најде n. Значи, да го направите тоа. 

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

Ако покажувачот точка n, дозволете ми да се врати тоа, equals-- еднаква на што? Што вредност сум јас барате? Вистински n што беше донесен во. Значи тука е уште една карактеристика на C и многу јазици. Иако структура наречена јазол има вредност n, сосема легитимни исто така да имаат локална аргумент или променлива наречена n. Затоа што дури и ние, со човечки очи, може да се направи разлика дека n е веројатно различни од оваа n. Бидејќи синтаксата е различна. Имаш точка и покажувач, додека овој има такво нешто. Значи ова е во ред. Тоа е во ред да им се јавам на исти работи. 

Ако јас да ти се најде ова, јас сум ќе сакате да направите нешто како објавиме дека најдовме n. И ние ќе го оставиме тоа како коментира или pseudocode код. Друго, и тука е Интересните дел, што сакам да направам, ако тековната јазол не ги содржи n дека јас се грижат за? Како можам да го постигне следното? Ако мојот прст на момент е меморија, и тоа е покажувајќи кон она што Првиот е да се покажува во, како можам да се движи мојот прст кон следниот јазол во код? Па, она што е Breadcrumb сме ќе следат во овој случај? ПУБЛИКАТА: [Беззвучен]. Дејвид Џ MALAN: Да, па следната. Значи, ако јас се вратам во мојата код овде, навистина, јас сум ќе одиме напред и да се каже покажувач, што е само привремена variable-- тоа е чудно име, кон меморија, но тоа е исто како temp-- Одам да го поставите покажувачот еднакви на она што покажувачот is-- и повторно, тоа се случува да биде малку кабриолет за moment-- точка веднаш. Со други зборови, јас ќе одам да земам прст кој е покажувајќи кон овој јазол тука и јас одам да се каже, знаете што, погледнете во следното поле и да се движат вашиот прст за да што и да се покажува кон. И ова се случува да се повторувам, повторувам, повторете. Но, кога го прави мојот прст престане да прави ништо на сите? Штом она линија код клоци во? ПУБЛИКАТА: [Беззвучен] Дејвид Џ MALAN: Ако точка а покажувач не е еднаква на нула. Во одреден момент мојот прст на ќе биде покажувајќи кон нула и јас одам да се реализира тоа е крајот на оваа листа. Сега, ова е малку бела лага за едноставност. Излегува дека иако само научиле оваа точка нотација за структури, покажувачот не е struct. кон меморија е она? Само за да биде повеќе nitpicky. Тоа е покажувач кон јазол. Тоа не е еден јазол себе. Ако немав ѕвезда тука, покажувачот absolutely-- тоа е еден јазол. Ова е како една недела прогласување на променлива, иако зборот "јазол" е нова. 

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

Сега, за оние од вас кои би можеле да преферираат стариот начин, можете да го користите dot нотација. Но, како по понеделникот разговор, ние прво треба да се оди таму, одат за тоа адреса, а потоа пристап област. Значи, ова е, исто така, точно. И искрено, ова е малку повеќе педантниот. Ќе бидете буквално велејќи dereference на покажувачот и да си одат таму. А потоа го зграби .n, полето се нарекува n. Но, искрено, никој не сака за да напишете или да прочитате ова. И така светот измислени на стрелката нотација, кои е еквивалентно, идентични, тоа е само синтаксички шеќер. Така фенси начин да се каже ова изгледа подобро, или изгледа поедноставно. 

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

Значи, да го направите тоа. Ако ќе хумор мене тука, јас не донесе еден куп на стрес топки. Имам еден куп на броеви. И може да се добие само неколку волонтери да претставуваат 9, 17, 20, 22, 29, и 34? Значи во суштина сите кој е тука и денес. Тоа беше еден, два, три, четири, пет, шест лица. И јас сум бил побарано да go-- се види, нема еден во задниот крева рацете. Добро, еден, два, три, четири, five-- дозволете ми да се вчита balance-- шест. Добро, ќе дојде на шест до. Ќе треба други луѓе. Ние донесе екстра стрес топки. И ако може, на само еден миг, линија себе се само како оваа слика овде. 

Во ред. Ајде да видиме, како се викаш? 

ПУБЛИКАТА: Андреј. 

Дејвид Џ MALAN: Андреј, сте број 9. Убаво да ви се исполнат. Овде и да одите. ПУБЛИКАТА: Џен. Дејвид Џ MALAN: Џен. Давид. Број 17. Да? 

ПУБЛИКАТА: Јас сум Џулија. 

Дејвид Џ MALAN: Јулија, Дејвид. Број 20. ПУБЛИКАТА: христијанин. Дејвид Џ MALAN: Кристијан Давид. Број 22. И? 

ПУБЛИКАТА: ЈП. Дејвид Џ MALAN: ЈП. Број 29. Така одат напред и да добијат in-- Ух ох. Ух ох. Мирување. 20. Дали некој има маркер? ПУБЛИКАТА: Имам Sharpie. Дејвид Џ MALAN: Имаш Sharpie? Во ред. И дали некој има парче хартија? Спаси предавање. Ајде. ПУБЛИКАТА: Ние сме го добив. Дејвид Џ MALAN: Ние го зедов тоа? Добро, ви благодарам. Еве ќе одиме. Беше тоа од вас? Вие само спаси денот. Па 29. Во ред. Јас погрешно напишани 29, но во ред. Оди напред. Добро, јас ќе ви даде вашиот пенкало врати веднаш. Значи ние треба овие луѓе тука. Ајде да имаат еден друг. Габе, дали сакате да играте првиот елемент тука? Ќе треба да се истакне овие фини луѓе. Значи 9, 17, 20, 22, сортирање на 29, а потоа 34. Дали ја губиме некој? Имам 34. Каде did-- Добро, кој сака да биде 34? Добро, ајде нагоре, 34. Добро, ова ќе биде добро вреди кулминација. Што е вашето име? 

ПУБЛИКАТА: Петар. 

Дејвид Џ MALAN: Питер, ајде нагоре. Добро, па тука е целиот куп на јазли. Секој од вас момци претставува еден од овие правоаголници. И Габе, малку чудно човек, претставува прв план. Па неговата покажувачот е малку помал на екранот од сите други. И во овој случај, секој од лево рацете се случува да се укаже или надолу, со тоа што претставува нула, па само на отсуство на покажувач, или тоа ќе биде покажувајќи на еден јазол до тебе. 

Па сега ако украсуваат себе како на сликата тука, одиме напред и точка еден во друг, со Габе особено укажувањето на број 9 да претставуваат листа. Добро, и бројот 34, левата рака само треба да се укажува на подот. 

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

Па, бројот што се обидуваат да вметнете, кои знаеме сега треба да биде 55, но ако не сте знаеле однапред, јас daresay паѓа во најмалку три можни ситуации. Каде нов елемент може да биде? ПУБЛИКАТА: И на крајот или средината. Дејвид Џ MALAN: На крајот, во средината, или на почетокот. Така тврдам има најмалку три проблеми што треба да се реши. Ајде да се избере она што е можеби веројатно најпростиот еден, каде што новиот елемент припаѓа на почетокот. Па јас ќе одам да имаат код доста како пребарување, што јас само напишав. И јас одам да имаат кон меморија, која Ќе го претставуваме тука со мојот прст, како и обично. 

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

Значи ова беше на почетокот на нашата приказна. А сега ова е само јасна, иако синтаксата е нова. Концепциски, ова е само линеарно пребарување. Е 55 еднаков на 9? Или подобро кажано, да речеме помалку од 9. Затоа што јас се обидувам да дознаам каде да се стави 55. Помалку од 9, помалку од 17, помалку од 20, помалку од 22, помалку од 29, помалку од 34, бр. Па сега сме во случај еден од најмалку три. 

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

Па сега што ако следниот сценарио доаѓа заедно, и ние сакаме да се вметне на почетокот или на чело на оваа листа? И она што е вашето име, број 55? 

ПУБЛИКАТА: Џек. 

Дејвид Џ MALAN: Џек? Добро, убаво да ви се исполнат. Добредојдовте на бродот. Па сега ние ќе се вметнете, да речеме, бројот 5. Тука е втор случај на три дојдовме до пред. Значи, ако 5 припаѓа на почетокот, ајде да видиме како ќе најдеме тоа. Јас се иницијализира моите кон меморија покажувач на бројот 9 се повторно. И сфатив, о, 5 е помала од 9. Па се поправи оваа слика за нас. Чии раце, Габе или Давид or-- она ​​што е број 9 име? 

ПУБЛИКАТА: Џен. 

Дејвид Џ MALAN: hands-- на Jen кој од нашите раце треба да се промени? Добро, така Габе укажува на она што сега? Во мене. Јас сум нов јазол. Па јас ќе само вид на потег тука за да го видите визуелно. А во меѓувреме она што можам да истакнам дека? Сепак, каде што јас сум покажува. Значи тоа е тоа. Па само навистина една линија код поправки ова конкретно прашање, тоа ќе изгледа. Сите во право, па тоа е добро. И некој може да биде случаеви за 5? Ајде до. Ќе ти најдеме следниот пат. 

Добро, така now-- и Како настрана, имињата Јас не сум што експлицитно споменување на право сега, pred покажувач, претходник покажувачот и нови покажувачот, тоа е само имиња дадени во примерокот кодот на совети или моите раце и тоа е вид на покажувајќи наоколу. Што е вашето име? 

ПУБЛИКАТА: Кристин. 

Дејвид Џ MALAN: Кристин. Добредојдовте на бродот. Добро, па ајде да се разгледа сега малку повеќе досадни сценарио, при што сакам да го вметнете нешто како 26 во тоа. 20? Што? Овие are-- добра работа имаме ова пенкало. Добро, 20. Ако некој може да се добие уште еден дел од хартија подготвен, само во case-- ред. Ох, интересно. Па ова е пример на предавање бубачка. Добро па што е вашето име повторно? ПУБЛИКАТА: Јулија. Дејвид Џ MALAN: Јулија, може да ви се појави надвор и се преправам сте биле никогаш таму? Добро, тоа никогаш не се случило. Ви благодарам. Значи да претпоставиме што сакате да внесете Јулија во оваа поврзани листа. Таа е број 20. И, се разбира таа е ќе припаѓаат на begin-- не упатуваат на ништо сеуште. Па раката вид на може да биде надолу null или некои ѓубре вредност. Ајде да кажам на брз приказна. Јас сум покажувајќи кон број 5 на овој период. Тогаш јас се провери 9. Тогаш јас провери 17. Тогаш јас провери 22. И сфаќам, ooh, Јулија треба да се оди пред 22. Значи она што треба да се случи? Чии раце треба да се промени? Јулија, мојата, or-- она што е вашето име повторно? 

ПУБЛИКАТА: христијанин. 

Дејвид Џ MALAN: Кристијан или? 

ПУБЛИКАТА: Енди. 

Дејвид Џ MALAN: Енди. Христијанин или Енди? Енди треба да се укаже на? Јулија. Во ред. Па Енди, сакаш да се укаже на Јулија? Но, чекајте. Во приказната досега, Јас сум вид на еден одговорен, во смисла дека покажувачот е нешто што е се движат низ листата. Ние би можеле да имаат име за Енди, но нема променлива наречена Енди. Единствената друга променлива што го имаме е Првиот, кој е претставен од страна на Габе. 

Значи ова е всушност зошто тоа далеку не сме потребни ова. Но, сега на екранот постои споменам повторно на pred покажувач. Па да ми биде повеќе експлицитни. Ако ова е покажувач, имав подобро се добие малку поинтелигентен за мојот повторување. Ако не ти пречи мојата минува низ овде повторно, посочувајќи тука, покажувајќи тука. Но, дозволете ми да имаат pred покажувач, претходник покажувач, тоа е вид посочувајќи на елемент бев во. Па кога одам тука, сега мојата лева рака надградби. Кога одам тука мојата лева рака надградби. И сега имам само покажувач на елемент кој оди по Јулија, Јас се уште имаат покажувач Енди, елементот порано. Па имате пристап, во суштина, breadcrumbs, ако сакате, на сите потребните совети. 

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

Сега, секако дека постојат некои други операции што може да се спроведе. И овие слики тука само отслика она што го направија со луѓето. Што е со отстранување? Ако сакам да, на пример, отстрани број 34 или 55, Јас би можеле да имаат ист вид на код, но јас ќе одам да треба еден или два чекори. Бидејќи она што е ново? Ако јас отстраните некој на крајот, како број 55, а потоа 34, што, исто така, мора да се промени како што јас го правам тоа? Морам да го evict-- она што е вашето име повторно? 

ПУБЛИКАТА: Џек. 

Дејвид Џ MALAN: Џек. Морам да не само evict-- слободен Џек, па буквално повик ослободени Џек, или барем покажувачот таму, но сега што треба да се промени со Петар? Раката подобро е да почнеме покажува надолу. Затоа што веднаш штом ли повик ослободени од Џек, ако Петар уште покажувајќи кон Џек и јас тоа го задржи traversing листата и пристап до оваа покажувач, тоа е кога нашиот стар пријател сегментација грешка всушност би можеле да умирам. Затоа што сум со оглед на меморија назад Џек. 

Можете да остане таму чудно за само еден миг. Бидејќи имаме само неколку завршните операции за да се разгледа. Отстранување на чело на листата, или beginning-- и ова ми е малку досадни. Затоа што ние треба да знаат дека Габе е вид на специјални во оваа програма. Бидејќи навистина, тој има своја покажувач. Тој не е само вперени во, како што е речиси сите други овде. 

Па кога на чело на листата е отстранети, чии раце треба да се промени сега? Што е вашето име повторно? 

ПУБЛИКАТА: Кристин. 

Дејвид Џ MALAN: Јас сум ужасна на имиња, очигледно. Па Кристин и Габе, чии раце треба да се промени кога ќе се обидат да се отстрани Кристин, број 5 од сликата? Добро, така нека направи Габе. Габе ќе се укаже, веројатно, во број 9. Но, она што следната треба да се случи? ПУБЛИКАТА: Кристин треба бидат ништовни [Беззвучен]. Дејвид Џ MALAN: Добро, ние најверојатно треба make-- слушнав "нула" некаде. ПУБЛИКАТА: Нулев и слободни неа. Дејвид Џ MALAN: NULL што? ПУБЛИКАТА: Нулев и слободни неа. Дејвид Џ MALAN: Нулев и слободни неа. Значи ова е многу лесно. И тоа е совршена дека ти си сега вид на постојани таму, кои не припаѓаат. Бидејќи сте биле одделат од листата. Сте ефикасно се сираче од листата. И така имавме подобра повик ослободени сега Кристин да им даде дека меморијата назад. Инаку секој пат кога ние избришете еден јазол од листата ние би можеле да се прави листа пократок, но не и всушност се намалува големината на меморијата. И така, ако ние ги додавајќи и додавање, додавајќи работи на списокот, мојот компјутер може да се добие побавно и побавно и побавно, бидејќи јас сум истекува на меморија, дури и ако не сум всушност користење на бајти на Christine меморија повеќе. 

Па на крајот постојат и други сценарија, на course-- отстранување во средината, отстранување на крајот, како што видовме. Но поинтересно Предизвикот сега е ќе биде да се разгледа точно она трчање време е. Затоа, не само што може да ги задржи вашите парчиња хартија, ако Габе, не би ум даваат секој стрес топката. Ви благодарам многу за нашите поврзана листа на волонтери тука, ако може. 

[Аплауз] 

Дејвид Џ MALAN: Во ред. Па неколку аналитички прашања тогаш, ако можам. Видовме оваа нотација пред, голема О и омега, горната граница и долниот границите на трчање време на некои алгоритам. Па ајде да се разгледа само неколку прашања. 

Еден, и ние тоа го рече пред, што е водење време на потрагата по листа во однос на големите О? Што е горна граница на водење време на пребарувањето на поврзани листа а се имплементирани од нашите волонтери тука? Тоа е голема О на n, линеарна. Затоа што во најлош случај, на елемент, како 55, ние би можеле да се гледа за може да биде каде што Џек беше, сè на крајот. И, за жал, за разлика од низа не можеме да се фенси тоа време. Иако сите наши луѓе беа подредени од мали елементи, 5, сите на патот до поголем елемент, 55, тоа е обично е добра работа. Но, она што го прави таа претпоставка не ни дозволуваат да направам? ПУБЛИКАТА: [Беззвучен] Дејвид Џ MALAN: Кажи повторно? ПУБЛИКАТА: Случајни пристап. Дејвид Џ MALAN: Случајни пристап. И пак тоа значи дека ние не може не се користи слаби нули, интуиција, и очигледност на користење на бинарни пребарување и подели па владеј. Бидејќи иако ние луѓето би можеле очигледно види дека Енди или христијански беа приближно во средината на листата, ние знаеме само дека како компјутер со впивам листата од самиот почеток. Значи ние сме се откажале дека случаен пристап. 

Толку голема О од n сега е на горниот граница на нашите пребарување време. Што е со омега на нашите пребарување? Што е долната граница на пребарувањето за некои број во оваа листа? ПУБЛИКАТА: [Беззвучен] Дејвид Џ MALAN: Кажи повторно? ПУБЛИКАТА: Еден. Дејвид Џ MALAN: Еден. Па постојано време. Во најдобар случај, Кристин е навистина на почетокот на листата. И ние сме во потрага за број 5, па ние ја најде. Па нема ништо страшно. Но таа мора да биде во почетокот на списокот во овој случај. Она што за такво нешто избришете? Што ако сакате да ги избришете елемент? Што е горната граница и долната граница за бришење на нешто од поврзани Листа? ПУБЛИКАТА: [Беззвучен] Дејвид Џ MALAN: Кажи повторно? ПУБЛИКАТА: n. Дејвид Џ MALAN: n е навистина горната граница. Затоа што во најлош случај ќе се обидеме да ги избришете Џек, како што го направија. Тој е начинот на кој на крајот. Ни треба цела вечност, или n чекори за да го најде. Па тоа е горна граница. Тоа е линеарна, секако. И најдобар случај трчање време, или долниот границите во најдобар случај ќе биде постојана време. Затоа што можеби ќе се обидеме да ги избришете Кристин, а ние само ќе имаат среќа таа е на почетокот. Сега почекајте една минута. Габе беше, исто така, на почетокот, и ние, исто така, мораше да се ажурира Габе. Па тоа не е само еден чекор. Па тоа е навистина постојан време, во најдобар случај, за да се отстрани и најмалата елемент? Тоа е, иако тоа би можело да биде два, три, па дури и 100 линии на код, ако е ист број на линии, а не во некој циклус, и независно од големината на на листата, апсолутно. Бришење на елемент во на почетокот на листата, дури и ако ние треба да се занимаваат со Габе, се уште е постојана време. 

Значи ова се чини како масивни чекор наназад. И што е губење на време ако во една недела и недела нула имавме не само pseudocode код, но реалните код за спроведување на нешто што е дневник база n, или да се најавите, туку од n, база 2, во однос на своите работи време. Значи, зошто е грижам ние би сакале да започне користење на нешто како се поврзани листа? Да. 

ПУБЛИКАТА: Значи можете да додадете елементи на низата. Дејвид Џ MALAN: Значи можете да додадете елементи на низата. И тоа исто така е тематски. И ние ќе продолжиме да ја видите ова, оваа трампа, многу како видовме трампа со спојување вид. Ние навистина би можеле да го забрзаат пребарување или сортирање, поточно, ако ние трошиме малку повеќе простор и имаат дополнителен парче на меморија или низа за спојување вид. Но, ние трошиме повеќе простор, но заштедите време. Во овој случај, ние сме откажување време, но ние сме стекнување на флексибилност, динамика ако сакате, кој е веројатно позитивна карактеристика. 

Ние сме, исто така трошење простор. Во која смисла е поврзан листа поскапи во смисла на простор од низа? Каде е екстра простор доаѓаат од? Да? 

ПУБЛИКАТА: [Беззвучен] покажувач. 

Дејвид Џ MALAN: Да, ние исто така, имаат покажувач. Значи ова е minorly досадни во кој повеќе не сум Јас складирање само int да претставува цел број. Јас сум чување на int и покажувач, кој исто така е 32 бита. Па јас сум буквално удвојување износот на простор се вклучени. Па тоа е трампа, но тоа е во случај на int. Да претпоставиме дека не сте складирање int, но претпоставувам секој од овие правоаголници или од секоја од овие луѓе беше ги претставуваат еден збор, на англиски зборот што може да биде пет карактери, 10 карактери, можеби дури и повеќе. Потоа додавање на само 32 повеќе битови може да биде помалку од една голема зделка. 

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