[За възпроизвеждане на музика] DAVID J. Malan: Добре. Това е CS50. Това е пет седмици продължава, и ние има някои добри новини и лоши новини. Така че добрата новина е, че CS50 стартира този петък. Ако бихте искали да се присъединят към нас, отправят към обичайната URL адреса тук. Дори и по-добри новини, не лекция идния понеделник на 13-ти. Малко по-малко по-добри новини, викторина нула е следващата сряда. Повече подробности могат да бъдат намерено в този URL тук. И през следващите няколко дни ние ще се попълване на бланки по отношение на стаите че ще сме резервирани. По-добра новина е, че има Ще е преглед на курс-широк сесия този смешен Понеделник вечерта. Останете на линия за курса сайт за местоположение и подробности. Раздели, въпреки че е празник, ще се срещне също, както добре. Най-добрите новини, лекции следващия петък. Така че това е една традиция, ние трябва, съгласно учебната програма. Просто-- това ще бъде невероятно. Ще видите неща, като постоянен времеви структури от данни и хеш таблици и дървета и се опитва. И ние ще говорим за проблеми рожден ден. Цял куп неща очаква следващия петък. OK. Във всеки случай. Така си припомним, че ние сме били фокусиране върху тази картина на това, което е вътрешна памет нашия компютър. Така памет или RAM е мястото, където програми съществува, докато сте ги да работят. Ако щракнете двукратно върху иконата, за да стартирате някоя програма или щракнете двукратно върху иконата, за да отворите някой файл, тя зарежда от твърдия шофирате или твърдотелен диск в RAM, Random Access Memory, където той живее, докато захранването се изключва, капакът се затваря лаптопа, или спиране на програмата. 

Сега, памет, на които най-вероятно са 1 гигабайт тези дни, 2 гигабайта, или дори много повече, обикновено е изложена за дадена програма в този вид на правоъгълна концептуален модел което имаме стак на дъното и куп други неща, най-отгоре. Това, което в най-горната сме виждали на тази снимка преди, но никога не говореше за е така наречената текст сегмент. Текст сегмент е само един луксозен начин Споменаването на нули и единици, които композира действителните си съставила програма. 

Така че, когато щракнете двукратно върху Microsoft Word на вашия Mac или PC, или когато стартирате точка наклонена черта Mario на Linux компютър в терминален прозорец ви, от нули и единици, които съставят Word или Mario се съхранява временно в RAM на вашия компютър в така наречените текст сегмент за дадена програма. По-долу, че отива инициализира и неинициализирани данни. Това е нещо като глобални променливи, че не съм използвал много от, но от време на време сме имаше глобални променливи или статично дефинирана низове, които е трудно кодирани думи като "здравей" че не са взети в от потребителя , които са трудно кодирани във вашата програма. 

Сега, надолу към дъното сме има така наречената стека. И стека, до този момент, ние сме били използвате за какви цели? Какво стека били използвани за? Да? 

Публика: функции. 

DAVID J. Malan: За функции? В какъв смисъл за функции? 

АУДИТОРИЯ: Когато ти се обадя на функция, аргументи се копират върху стека. 

DAVID J. Malan: Точно така. Когато позвъните на функция, аргументи се копират върху стека. Така че всякакви X или Y или А или Б че сте преминаване във функция временно се постави на т.нар стека, само като един от Аненберг трапезария корита, както и неща като локални променливи. Ако вашият Foo функция или суап функция има локални променливи, като температура, тези две до края на стека. Сега, ние няма да говорим твърде много за тях, но тези променливи на обкръжението в долната част, което видяхме преди известно време, когато Бях futzing в клавиатурата един дни и аз започнах достъп неща като argv 100 или argv 1000, просто elements-- забравям на numbers-- но това не е трябвало да бъдат достъпни от мен. Ние започнахме да се срещаме някои фънки символи на екрана. Това са така наречените променливи на обкръжението като глобалните настройки за моя програма или за моя компютър, не несвързани с близкото бъг, който обсъждахме, Shellshock, който е бил изпаднал доста компютри. 

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

Но има вид проблем тук, тъй като картината предполага. Ние някак имат две кораби, за да се сблъскат. Тъй като се използват все повече и повече на стека, а както виждаме днес нататък, като се използват все повече и повече от грамада, непременно лоши неща могат да се случат. И наистина, ние може да принуди умишлено или неволно. Така Катерачът последно време е тази програма, който не служи за функционална друга цел, освен да покаже, как вие като лош човек може действително да Възползвайте се от грешки в програмата на някого и да поеме на програма или дори цялата компютърна система или сървъра. Така че просто да погледне за кратко, вие се отбележи, че основният в дъното отнема в командния ред аргументи, съгласно argv. И тя има покана към функция F, по същество една безименна функция, наречена Е, и това е преминаване в argv [1]. 

Така че каквото и дума видовете потребителски в най- подканата след името на тази програма е, и след това произволна функция на отгоре, е, отнема в низ, AKA Чар *, като сме започнали да обсъждаме, и то просто го нарича "бар". Но можем да го наречем нещо. И тогава тя декларира, вътре на е, за масив от знаци наречен c-- 12 такива знаци. 

Сега, от историята, която се разказва преди малко, когато в паметта е С, или са тези 12 овъгли ще свърши? Само за да бъде ясно. Да? 

АУДИТОРИЯ: On стека. 

DAVID J. Malan: On стека. Така в е локална променлива. Молим за 12 символа, или 12 байта. Тези, които са в крайна сметка ще на така наречената стека. Сега най-накрая е тази друга функция това всъщност е доста полезно, но ние не сме наистина използва то себе си, strncopy. Това означава низ копие, но само N писма, N знака. Така н символи ще бъдат копиран от бар в C. И колко? Дължината на бар. С други думи, че една линия, strncopy, се случва, за да копирате ефективно бар, за да в. 

Сега, само за да вид предвиждане Поуката от тази история, това, което е потенциално проблематични тук? Въпреки, че ние сме проверка на дължината на бар и да го прехвърлят в strncopy, какво е червата ви казва е все още разбити за тази програма? Да? 

АУДИТОРИЯ: Не включва стая за нищожна характер. DAVID J. Malan: Не включва стая за нищожна характер. Потенциално разлика досегашната практика ние не знаем дори има толкова много като плюс 1 до настанят че нищожна характер. Но това е дори по-лошо от това. Какво друго ни не е да направя? Да? 

АУДИТОРИЯ: [недоловим] DAVID J. Malan: Perfect. Ние трудно кодирани 12 доста произволно. Това не е толкова много на проблем, но фактът че ние не сме дори проверка дали дължината на бар е по-малко от 12, в такъв случай тя ще бъде безопасно да го сложи в паметта наречен в които сме разпределени. В действителност, ако е като бар Дълги от 20 знака, тази функция изглежда копиране 20 герои от бар в C, като по този начин като най-малко 8 байта че тя не трябва да бъде. Това е изводът тук. 

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

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

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

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

Но сега се опитват да превъртите напред. Какво предстои да се случи, ако ние минаваме в низ бар, който е по-дълъг от C? И ние няма да се извърши проверка дали това е наистина по-дълъг от 12. Коя част от тази картина ще се ще бъдат пренаписани от байтове 0, 1, 2, 3, точка точка точка 11, и след това лошо, 12, 13 до 19? Какво ще се случи тук, ако се направи извод от наредителя че в скоба 0 е на върха и в скоба 11 е нещо надолу надясно? Да? 

АУДИТОРИЯ: Е, това се случва да презапишете Чар * бара. 

DAVID J. Malan: Да, тя изглежда като ти започваш да презапишете Чар * бар. И по-лошо, ако изпратите в един наистина дълъг низ, вие дори може да презапишете какво? Адресът за връщане. Което отново е точно като трохи да каже на програмата, където да се върнем към когато е се прави се нарича. 

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

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

Така че, ако всеки от тях букви A точно представлява, концептуално, атака, атака, атака, атака, някои лоши код че някой друг е написал, но ако това лице е достатъчно умен, не само да се включат всички на тези RM-RFS, но също Трябва последните неговите или нейните няколко байта е номер, който съответства на адреса си или нейния собствен код атака че той или тя премина само като го предоставя в командния ред, можете ефективно да подвежда компютъра в забележи, когато F е направено изпълнение, О, това е време за мен да скочи обратно към червения връщане адрес. Но тъй като той или тя трябва по някакъв начин припокриват, че обратен адрес със своя номер, и те са достатъчно умни да са конфигурирани, че номер, за да се отнасят, както виж в супер върха ляв ъгъл там, действителното адреса в компютър паметта на някои от тяхната атака код, лош човек може да се излъже компютъра в изпълнение на неговата или нейната собствена код. 

И този код, отново, може да бъде всичко. Това обикновено се нарича черупка код, който е само начин да се каже, че това не е обикновено нещо толкова просто като RM-RF. Това всъщност е нещо като Bash, или действително програма, която му дава или програмна си контрол, за да се изпълни нещо друго, което те искат да. Така че, накратко, всичко това произтича от простия факт, че този бъг не участва проверка границите на масива. И тъй като начин компютри работа е, че те използвате стека от ефективно, концептуално, отдолу нагоре, но след това елементите натиснете върху стека расте отгоре надолу, това е изключително проблематично. Сега, има начини да се справите с това. И честно казано, има езици с които да се справите с това. Java е имунизиран, например, на този конкретен въпрос. Тъй като те не ви дават насоки. Те не ви дават директни адреси на паметта. Така че с тази сила, която имаме да пипа нищо в паметта Искаме идва, разбира се, голям риск. 

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

Добре. Така изчистване до този момент е била нашата нова приятел в които можем да разпредели памет че не е задължително да се знае предварително, че ние искаме, така че ние не трябва на твърдия код в нашия програмни номера като 12. След като потребителят не ни казва колко данни той или тя иска да въведе, можем да изчистване, че много памет. 

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

Но купчината е до тук. И това, което е хубаво за изчистване, е, че когато изчистване заделя памет до тук, това не е повлияло за голямата си част, от стека. И така всяка функция може да получите достъп до памет, която е malloc'd, дори с функция като getstring, дори след това се връща. 

Сега, обратното на изчистване е безплатна. И наистина, за да ви управлява Трябва да започнем да приеме е всеки, всеки, по всяко време можете да използвате изчистване трябва сам да използвате безплатно, в крайна сметка, на същата тази показалка. През цялото това време ние сме били писане бъги, бъги код, по много причини. Но един от които е използване на библиотеката CS50, който се е преднамерено бъги, тя изтича памет. Всеки път, когато се обадих getstring през последните няколко седмици ние питаш оперативните система, Linux, за паметта. И ти никога не веднъж го е дал обратно. И това не е в практикуват, е нещо добро. 

И Valgrind, един от най- инструменти, въведени в Pset 4, е всичко, за да ти помогне сега намерите бъгове като това. Но за щастие на Pset 4 не е нужно да използвате библиотеката CS50 или getstring. Така че каквито и да било грешки, свързани с паметта са в крайна сметка ще бъде вашата собствена. 

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

Така масив изглеждаше така. И това, което е от ключово значение за един масив е, че тя дава бек-ту-бек парчета памет, всеки от които ще бъде от същия тип, Int, INT, INT, INT, или Чар, Чар, Чар, Чар. Но има няколко недостатъци. Това например, е масив с размер шест. Да предположим, че се запълни тази масив с шест номера и след това, за каквито и да било причини, потребителското си иска да даде вие седми номер. Къде да го сложите? 

Какво е решението, ако имате създаден масив на стека, например, само с седмицата две нотация че ние въведохме, квадратни скоби с номер вътре? Е, имаш шест номера в тези кутии. Какви биха били вашите инстинкти? Къде бихте искали да го сложите? 

АУДИТОРИЯ: [недоловим] 

DAVID J. Malan: Моля? 

АУДИТОРИЯ: Сложете го на края. 

DAVID J. Malan: Сложете го на края. Така че малко повече на дясно, извън това поле. Което би било хубаво, но то Оказва се, че не може да направи това. Защото, ако не съм попитал за това парче от памет, тя може да бъде случайно, че това се използва от някои други променливи напълно. Спомни си една седмица или така, когато поставихме от Zamyla и Дейвин и Гейб имена в памет. Те бяха буквално обратно назад към гърба. Така че ние не винаги могат да Вярвам, че каквито и да е тук е на разположение за мен да се използва. 

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

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

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

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

И какво от това, ако вместо просто съхраняване на номерата, като 9, 17, 22, 26, 34, какво ще стане ако ние не се съхранява само няколко но указател в непосредствена близост до всеки такъв номер? Така че много като теб ще вдявам иглата през цял куп от плат, по някакъв начин на връзване неща заедно, по същия начин могат ние с указатели, като въплътен от стрели тук, вид тъкат заедно тези отделни правоъгълници чрез ефективно използване на показалеца до всеки номер, който посочва някои следващия брой, че посочва, от своя страна, някои следващия брой? Така че с други думи, това, което ако ние всъщност исках да приложи нещо подобно? Ами за съжаление, тези правоъгълници, най-малко един с 9, 17, 22, и така нататък, те вече не са приятни площади с единични номера. Долната, правоъгълника 9 по-долу, например, представлява това, което трябва бъде показалка, 32 бита. Сега, аз все още не съм наясно с всеки тип данни в C, която ви дава не само INT но указател напълно. 

И така, какво е решението, ако искаме да се измисли нашия собствен отговор на това? Да? 

АУДИТОРИЯ: [недоловим] 

DAVID J. Malan: Какво е това? 

АУДИТОРИЯ: New структура. 

DAVID J. Malan: Да, така че защо не ние създаваме нова структура, или в C, а структурата? Видяхме structs преди, ако за кратко, където се занимавахме със структура студент като този, който е имал име и къща. В Pset 3 пробив сте използвали целия куп structs-- GRect и GOvals че Stanford създаден, за да клъстер информация заедно. И какво от това, ако вземем същата тази идея за ключовите думи "typedef" и "структура" и след това някои студент специфични неща, и да се развива този в следното: typedef структура node-- и възел е просто много генерични компютърни науки термин за нещо в структурата на данните, контейнер в структурата на данните. Възел, аз твърдя, ще има едно цяло число N, напълно ясна, и след това малко по-загадъчно тази втора линия, структурата възел * следващия. Но в по-малко технически термини, това, което е, че на втора линия код вътре фигурните скоби? Да? 

АУДИТОРИЯ: [недоловим] DAVID J. Malan: A указател към друг възел. Така че, разбира се, синтаксис малко загадъчен. Но ако сте го прочели буквално, Следващата е името на променливата. Каква е неговата тип данни? Това е малко по-многословен, този път, но това е от тип структура възел *. Всеки път, когато съм виждал нещо звезда, че означава, че е указател към този тип данни. Така че следващия очевидно е указател към структура възел. 

Сега, това, което е структура на възел? Е, забележите, че виждате тези едни и същи думи в горния десен ъгъл. И наистина, можете да видите също и думата "Възел" тук в долния ляв ъгъл. И това всъщност е само за удобство. Забележете, че в нашата дефиниция студент там е думата "студент" само веднъж. И това е така, защото един студент обект не е самостоятелно референтна. Няма нищо вътре на студент , който трябва да сочи към друг ученик, persay. Това би било нещо като странно в реалния свят. 

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

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

Така че, ако сега ние искахме да започнем прилагането на този свързан списък, как бихме могли да преведем нещо като това да се кодира? Е, нека просто да видите пример за програма, която всъщност използва свързан списък. Сред днешния разпределение код е програма, наречена Списък Нула. И ако аз тичам това съм създал супер прост GUI, Графичен потребителски интерфейс, но това е наистина само ФОРМАТ. И сега съм си дал малко меню options-- Изтриване, Insert, издирване, и Traverse. И Quit. Това са само общи операции върху структура от данни, известна като списък връзка. 

Сега, Изтриване ще изтриване на номер от списъка. Insert ще добавите номер към списъка. Search ще изглежда за номер в списъка. И траверс е само един луксозен начин да се каже, разходка през списъка, да го отпечатате, но това е всичко. Не го променя по никакъв начин. 

Така че нека се опитаме това. Да вървим напред и тип 2. И тогава аз отивам да въведете номера, да речем 9. Enter. И сега моята програма е само програмирани да се каже, списък в момента е 9. Сега, ако отида напред и да вкарвайте отново, нека ми давай напред и отдалечаване и напишете 17. Сега в списъка ми е 9, а след това 17. Ако го направя поставете отново, нека да пропуснете един. Вместо това на 22, като на снимката сме търси в тук, позволете ми да скочи напред и вкарайте 26 следваща. Така че аз отивам да въведете 26. Списъкът е както очаквам. Но сега, само за да се види дали този код ще бъде гъвкав, нека сега тип 22, които най-малко концептуално, ако сме Имайки това подредени, което е наистина ще бъде още един гол точно сега, трябва да отиде в между 17 и 26. Така че аз хит Enter. В действителност, че работи. И така, нека сега да ме вкарва на последно място, на снимката, 34. 

Добре. Така че за сега нека да предвидят, че Изтрий и Traverse и Search направя, в действителност, да работят. В действителност, ако аз тичам Search, нека търсите номера 22, Enter. Той установява, 22. Така че това е, което тази програма Списък Нула прави. 

Но какво всъщност се случва върху който реализира това? Ами, първо, че може да има и наистина Аз нямам, файл, наречен list0.h. И някъде там е това линия, typedef, структура на възел, тогава аз имам фигурни скоби, INT N, и тогава struct-- какво е определението? Struct възел следващия. Така че ние се нуждаем от звездата. Сега технически влезем в навика на съставянето тук. Може да видите учебници и онлайн препратки го правят там. Това е функционално еквивалентна. В действителност, това е малко по-типично. Но ще бъде в съответствие с това, което което направихме миналия път и да направим това. И тогава накрая, аз отивам да правя това. 

Така че в заглавния файл някъде, в list0.h днес е това определение структура, а може би и някои други неща. Междувременно в list0c има ще бъде на няколко неща. Но ние просто ще начало и не завърши това. List0.h е файл, искам да се включат в моя C файл. И след това в някакъв момент, че съм Ще трябва ПНА, основната, анулира. И тогава аз отивам да има някои неща за вършене тук. Аз съм също ще има прототип, като нищожен, търсене, вътр, N, чиято цел в живота е за търсене на елемент. И след това тук аз твърдя в днешния код, нищожен, търсене, ПНА, п, не запетая, но отворени фигурни скоби. И сега искам по някакъв начин да търсите за един елемент в този списък. Но ние не разполагат с достатъчно информация на екрана, все още. Имам всъщност не представлява самия списък. Така че един начин бихме могли да приложат свързан списък в програма е някак си искам да направя нещо като декларира, свързан списък тук. За простота, аз отивам да се направи това глобално, въпреки че като цяло ние Не трябва да правим това твърде много. Но това ще опрости този пример. Така че аз искам да декларирам свързан списък тук. Сега, как бих могъл да направя това? 

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

АУДИТОРИЯ: Имаме нужда от указател към възел. DAVID J. Malan: A указател към възел. По-специално, който възел ще ви инстинкти са да се поддържа указател към? 

АУДИТОРИЯ: Първият възел. 

DAVID J. Malan: Да, вероятно само първия. И забележи, на първо възел е с различна форма. Това е само половината от размера на структурата, защото това е наистина само една показалка. Така че това, което наистина можете да направите, е да декларират свързан списък, за да бъде от тип възел *. И нека просто го наречем първия и го инициализира с нула. Така нула, отново, е, идващи в картината тук. Не само е нищожна използва като като специален върнатата стойност за неща като getstring и изчистване, нула също е нула показалка, липсата на показалеца, ако щете. Това просто означава, нищо не е все още тук. Сега на първо място, бих могъл да съм нарича това нещо. Бих могъл да го нарече "списък" или произволен брой други неща. Но аз съм го нарече "първия", така че ИТ линии с тази картина. Така че просто като низ може да бъде представена с адреса на първия байт, така че може един свързан списък. И ние ще видим други данни бъдат представени структури само с една показалка, 32-битов стрелка, сочеща при първия възел в структурата. 

Но сега нека да очакваме проблем. Ако аз съм само спомняйки в моята програма адреса на първата възлова точка, на първо правоъгълник в тази структура на данните, това, което е по-добре да бъде случаят да кажем за изпълнение на останалата част от моя списък? Какво е ключов детайл, който става да се гарантира това всъщност работи? И под "наистина работи" I да кажа, много прилича на низ, ни позволява да премине от първия знак в име Дейвин към втория, на трето, на на четвърто място, до самия край, как можем да знаем, когато сме в края на свързан списък, който изглежда по този начин? Когато това е нищожна. И аз съм представител на този вид, както е като електроинженер мощ, с малко заземяването символ на видове. Но това просто означава нула в този случай. Можете да го извади произволен брой начини, но този автор се случи да използват този символ тук. 

Толкова дълго, тъй като ние сме садене Всички тези възли заедно, само помня, когато първият е, толкова дълго като ще се постави специален символ в последния възел в списъка и ние ще използваме нищожна, защото това е това, което имаме на разположение за нас, този списък е пълен. И дори ако само ти давам указател към първият елемент, ти, програмист, със сигурност може да получите достъп до останалата част от него. Но нека да си умове скитат малко, ако те не са вече доста wandered-- какво е ще бъде времето за работа на намирането на нещо в този списък? Дявол да го вземе, това е голям O на N, което не е лошо, в справедливостта. Но е линейна. Ние сме се отказали от това, което функция на масиви, като се движат повече към тази картина на динамично изтъкани заедно или свързани възли? Ние сме се отказали от произволен достъп. Масивът е хубаво, защото математически всичко е да се върна обратно назад, за да върне. Въпреки, че тази картина изглежда доста, а дори и въпреки че изглежда като тези възли са добре раздалечени, в действителност те могат да бъдат навсякъде. ОХ1, ОХ50, Ox123, Ox99, те възли може да е навсякъде. Защото изчистване прави памет от купчината, но навсякъде в купчината. Не е задължително да се знае, че това е няма да се върне назад, за да върне. И така, тази картина в реалността Няма да бъде доста тази хубава. 

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

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

Ако показалка точка N, позволете ми да се върна към това, equals-- равнява на какво? Каква стойност търся? Действителната N, който е преминал инча Така че тук е друга функция, на C и много езици. Въпреки че структура, наречена възел има стойност н, напълно законен също има локален аргумент или променлива, наречена п. Защото дори и ние, с човешките очи, могат да се разграничат че п е вероятно различен от този вал. Защото синтаксисът е различен. Имаш една точка и показалеца, има предвид, че този човек няма такова нещо. Така че това е ОК. Това е ОК, за да им се обадя на едни и същи неща. 

Ако можете да откриете това, аз съм ще искате да направите нещо като обявим, че ние открихме, п. И ние ще си тръгнем, че като коментирате или pseudocode код. Иначе, и тук е интересна част, това, което искам да направя, ако текущия възел не се съдържа N, че ме е грижа за? Как да се постигне следното? Ако пръстът ми в момент е PTR, и това е сочейки към каквото и първо се сочеше, как мога да се движи пръста си към следващия възел в код? Е, какъв е трохи сме ще следват в този случай? АУДИТОРИЯ: [недоловим]. DAVID J. Malan: Да, така че следващия. Така че, ако се върнем към моя код тук, наистина, аз съм ще отида напред и да кажа, показалка, която е само временно променлива-- това е странно име, PTR, но Това е точно като temp-- Отивам да зададете на показалеца равна на каквото и показалеца е-- и отново, това ще бъде малко бъги за moment-- точка следващия. С други думи, аз отивам да си взема пръст, който е сочейки към този възел тук и аз ще кажа, нали знаеш какво, да погледнем в следващото поле и да се премести пръста си, за да каквото и да е сочеше. И това ще е Повтарям, повтарям, повторете. Но когато прави пръста ми спрем да правим каквото и да било? Веднага след като това ред код ритници в? АУДИТОРИЯ: [недоловим] DAVID J. Malan: Ако точка, докато показалка не е равна на нула. В един момент пръста ми ще се сочеше нула и аз отивам да се реализира това е краят на този списък. Сега, това е малко бяла лъжа за простота. Оказва се, че въпреки че Току-що научих тази точкова нотация за конструкции, показалеца не е структура. PTR е какво? Само за да бъде по-nitpicky. Това е указател към възел. Това не е само по себе си възел. Ако имах без звезди тук, показалеца absolutely-- това е един възел. Това е като една седмица декларация на променлива, въпреки че думата "възел" е нещо ново. 

Но веднага след като се въведе звезда, сега това е указател към възел. И за съжаление не можете да използвате дот нотация за показалеца. Вие трябва да използвате стрелката нотация, което поразително, е първият път, всяко парче синтаксис изглежда интуитивно. Това буквално изглежда като стрела. И така, това е нещо добро. И тук буквално изглежда като стрела. Така че аз мисля, че това е la-- аз не мисля, че съм по-извършване тук-- I мисля, че това е последното ново парче синтаксис, отиваме да се види. И слава Богу, че е наистина малко по-интуитивен. 

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

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

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

Добре. Да видим, какво е вашето име? 

АУДИТОРИЯ: Андрю. 

DAVID J. Malan: Andrew, сте номер 9. Приятно ми е да се запознаем. Заповядай. АУДИТОРИЯ: Джен. DAVID J. Malan: Джен. Дейвид. Номер 17. Да? 

АУДИТОРИЯ: Аз съм Джулия. 

DAVID J. Malan: Джулия, Дейвид. Номер 20. АУДИТОРИЯ: Christian. DAVID J. Malan: Christian, Дейвид. Номер 22. И? 

АУДИТОРИЯ: JP. DAVID J. Malan: JP. Номер 29. Така че продължавайте напред и да получите в-- Uh о. Uh о. Standby. 20. Дали някой има маркер? АУДИТОРИЯ: Имам Sharpie. DAVID J. Malan: Имаш Sharpie? OK. И не всеки има парче хартия? Запазване на лекцията. Хайде. АУДИТОРИЯ: Ние сме го. DAVID J. Malan: Ние го имаш? Добре, благодаря ви. Ето ни и нас. Дали това от вас? Вие току-що спаси деня. Така 29. Добре. I е неправилно изписана 29, но OK. Давай напред. Добре, аз ще ви дам писалката назад за миг. Така че ние имаме тези хора тук. Нека да има един друг. Габе, искаш ли да играем първият елемент тук? Ние ще трябва да се отбележи при тези хубави хора. Така 9, 17, 20, 22, сортиране от 29, и след това 34. Дали ще загубим някой? Имам 34. Къде did-- OK, който иска да бъде 34? Добре, хайде нагоре, 34. Добре, това ще бъде добре си струва кулминацията. Как ти е името? 

АУДИТОРИЯ: Peter. 

DAVID J. Malan: Peter, хайде нагоре. Добре, така че тук е цял куп възли. Всеки от вас, момчета представлява един от тези правоъгълници. И Габе, леко странно човек, представлява първият. Така показалеца си, е малко по-малък на екрана, отколкото всеки друг. И в този случай, всяка от ляво ръцете се случва или да сочи надолу, по този начин представляват нула, така само липсата на показалеца, или тя ще трябва да се посочи на възел в непосредствена близост до вас. 

Така че точно сега, ако ви красят себе си като на снимката тук, давай напред и точка един в друг, с Габе по-специално сочеше номер 9 представлява списък. OK, и номер 34, лявата ръка просто трябва да се посочи към пода. 

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

Е, номера, който се опитвате да вложка, която ние сега знаем, че е 55, но ако вие не знаете предварително, смея да кажа попада в най-малко три възможни ситуации. Къде може да е нов елемент? АУДИТОРИЯ: И в края или средата. DAVID J. Malan: В края на краищата, в центъра, или в началото. Така че аз твърдя, че има най-малко три проблема, които трябва да решим. Нека да изберете това, което е може би може би най-простият един, когато новият елемент принадлежи в началото. Така че аз отивам да имат код доста като търсене, което аз току-що е написал. И аз отивам да има PTR, които Ще представлявам тук с моя пръст, както обикновено. 

И не забравяйте, каква стойност сме се инициализира PTR да? Така че ние го инициализира с нула първоначално. Но тогава какво правим след като сме са вътре нашата функция за търсене? Ние го настроите равен на първия, което не означава, че правя това. Ако задам PTR равна на първо място, това, което трябва ръката ми наистина да сочи? Точно така. Така че, ако Гейб и аз ще да бъдат еднакви стойности тук, ние трябва да и двете точка номер 9. 

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

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

И сега какво, ако следващият сценарий идва заедно, и ние искаме да се вмъкне в началото или в главата на този списък? И какво е вашето име, номер 55? 

АУДИТОРИЯ: Jack. 

DAVID J. Malan: Джак? Добре, хубаво е да се запознаем. Добре дошли на борда. Така че сега ние ще вмъкнете, да речем, номер 5. Тук е вторият случай на три измислихме преди. Така че, ако 5 принадлежи в началото, нека да видим как ще открием, че навън. I инициализира ми PTR указател към номер 9 отново. И осъзнах, о, 5 е по-малко от 9. Така определи тази картина за нас. Чиито ръце, Гейб или Давид или-- какво е името на номер 9 е? 

АУДИТОРИЯ: Джен. 

DAVID J. Malan: hands-- Джен кои от нашите ръце, трябва да се промени? ОК, така че Гейб посочва в какво сега? В мен. Аз съм нов възел. Така че аз просто ще вид на ход тук, за да го видите визуално. А междувременно какво мога да посоча, че? И все пак, когато аз соча. Така че това е всичко. Така че просто наистина един ред код поправки този конкретен въпрос, то ще изглежда. Добре, така че това е добре. И някой може да бъде запазено за 5? Хайде нагоре. Ние ще ти донеса следващия път. 

Добре, така сега-- и Като настрана, имената Аз не съм на изрично споменаване на правото сега, Предвиждане показалка, предшественик на показалеца и нова показалка, че е само имената, дадени в примерен код за указатели или ръцете ми, че е вид, сочещи обратното. Как ти е името? 

АУДИТОРИЯ: Кристин. 

DAVID J. Malan: Кристин. Добре дошли на борда. Добре, така че нека да разгледаме сега малко по-досадно сценарий, с което искам да вмъкнете нещо като 26 в това. 20? Какво? Те are-- нещо добро имаме тази писалка. Добре, 20. Ако някой може да получи още едно парче хартия готов, само в case-- наред. О, интересно. Е е пример на лекция бъг. ОК, така това, което ти е името? АУДИТОРИЯ: Джулия. DAVID J. Malan: Джулия, може да ви поп навън и се преструвай, че никога не са били там? Добре, това не се е случило. Благодаря ви. Така че предполагам, че ние искаме вмъкнете Джулия в този свързан списък. Тя е номер 20. И разбира се, че е ще принадлежат в begin-- не посочи нищо все още. Така ръката ви може да бъде вид надолу нула или някаква стойност боклук. Нека кажа на бързо историята. Аз сочейки към номер 5 и този път. След това мога да проверя 9. След това мога да проверя 17. След това мога да проверя 22. И аз осъзнавам, ох, Джулия трябва да отида до 22. И така, какво трябва да се случи? Чиито ръце трябва да се промени? Джулия, мина, или-- какъв ти е името? 

АУДИТОРИЯ: Christian. 

DAVID J. Malan: Christian или? 

Публика: Анди. 

DAVID J. Malan: Andy. Christian или Анди? Анди трябва да посоча? Джулия. Добре. Така Анди, искаш ли да посочиш Джулия? Но почакайте. В историята до този момент, Аз съм нещо като един отговаря, в смисъл, че показалка е нещото, което е движещи се през списъка. Ние може да има име за Анди, но там не е променлива, наречена Анди. Единствената друга променлива, което имаме е първият, който е представляван от Гейб. 

Така че това е всъщност защо по този начин Дотук не съм необходим това. Но сега на екрана има споменем отново на Pred показалка. Така че нека да е по-ясно. Ако това е показалеца, имах по-добро да се получи малко по-интелигентни за моя итерация. Ако нямате нищо против, ще ми от тук отново, като посочи тук, сочейки тук. Но нека да има Pred показалка, предшественик показалка, че е вид сочейки елемент бях точно в. Така че, когато отидете тук, сега Лявата ми известия ръка. Когато отида тук лявата ми актуализации ръчно. И сега имам не само указател към елементът, който върви след Julia, Аз все още имам указател към Анди елемент преди. Така имате достъп, по същество, галета, ако щете, на всички необходими указатели. 

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

Сега, има определено друго операции, бихме могли да се приложи. И тези снимки тук просто изобразяват това, което ние просто направихме с хората. Какво ще кажете за отстраняване? Ако искам да, например, премахне номера 34 или 55, I може да има същия вид на код, но аз отивам да имат нужда от една или две стъпки. Защото какво е новото? Ако премахнете някой в ​​края на краищата, като номер 55 и след това 34, това, което също трябва да се промени, както аз правя това? Аз трябва да не evict-- какъв ти е името? 

АУДИТОРИЯ: Jack. 

DAVID J. Malan: Jack. Аз трябва да не само evict-- безплатно Jack, така буквално се обаждате безплатно Джак, или най-малко показалеца там, но сега какво трябва да се промени с Питър? Ръката му се по-добре да започне да сочи надолу. Защото веднага щом се обаждате безплатно на Джак, ако Петър все още сочеше Jack и затова аз продължавам преминаващи списъка и достъпа този указател, това е, когато нашият стар приятел сегментиране грешка може в действителност да риташ инча Защото ние сме като се има предвид памет обратно към Джак. 

Можеш да останеш там опасно само за миг. Защото ние имаме само няколко окончателните операции, за да разгледа. Сваляне на главата на списъка, или beginning-- и този е малко досадно. Защото ние трябва да знаем, че Гейб е вид специален в тази програма. Защото наистина, той има своя собствена показалка. Той не е просто да се посочи, както почти всеки друг тук. 

Така че, когато начело на списъка е отстранен, чиито ръце трябва да се промени сега? Какъв ти е името? 

АУДИТОРИЯ: Кристин. 

DAVID J. Malan: Аз съм ужасно на имена, очевидно. Така че Кристин и Гейб, чиито ръце трябва да се промени когато ние се опитваме да се отстранят Кристин, номер 5, от картинката? ОК, така че нека да направим Габе. Гейб ще посоча, Предполага се, че на номер 9. Но какво следва да се случи? АУДИТОРИЯ: Christine трябва е нищожен [недоловим]. DAVID J. Malan: Добре, ние трябва най-вероятно make-- чух "нула" някъде. АУДИТОРИЯ: Null и я освободи. DAVID J. Malan: Null какво? АУДИТОРИЯ: Null и я освободи. DAVID J. Malan: Null и я освободи. Така че това е много лесно. И това е съвършена, че вие ​​сте сега сортиране стоя там, които не принадлежат. Защото сте били отделена от списъка. Така в действителност е сираче от списъка. И така, ние бяхме по-добре се обаждате безплатно сега нататък Christine да дам, че паметта обратно. В противен случай всеки път, когато изтриване на възел от списъка ние може да се направи списък кратък, но не се намалява размера на паметта. И така, ако ние продължаваме да добавяте и добавяйки, добавяйки неща в списъка, моя компютър може да се забави и по-бавно и по-бавно, защото аз съм изчерпване на памет, дори ако не съм всъщност използване на байта на Кристин памет вече. 

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

[APPLAUSE] 

DAVID J. Malan: Добре. Така няколко аналитична въпроси тогава, ако можех. Видяхме тази нотация и преди, голям O и омега, горните граници и долни граници на времето за работа на някои алгоритъм. Така че нека да разгледаме само няколко въпроса. 

One, и ние го каза преди, какво е управлението време на търсене на списък по отношение на голям O? Какво е горна граница на протичане време на претърсване на свързан списък както се прилага от нашите доброволци тук? Това е голям O на N, линейна. Защото в най-лошия случай, елемент, като 55, ние може да се търси може да бъде там, където Джак беше, чак в края. За съжаление, за разлика от масив ние не можем да получите фантазия този път. Въпреки че всички от нашите хора бяха сортирани от малки елементи, 5, по целия път до по-голям елемент, 55, това е обикновено нещо добро. Но това, което прави това предположение вече не ни позволи да направим? АУДИТОРИЯ: [недоловим] DAVID J. Malan: отново Кажи? АУДИТОРИЯ: Random достъп. DAVID J. Malan: Random достъп. И на свой ред това означава, че можем да не вече се използва слаб нули, интуиция, и очевидност за използване на двоичен търсене и разделяй и владей. Защото, въпреки че ние хората биха могли очевидно се види, че Анди или Christian бяха приблизително в средата на списъка, ние само знаем, че като компютър чрез обиране списъка от самото начало. Така че ние сме се отказали, че произволен достъп. 

Толкова големи О п сега е на горната граница на нашето време за търсене. Какво ще кажете за омега на нашето търсене? Какво е по-ниската граница на търсенето за някакъв номер в този списък? АУДИТОРИЯ: [недоловим] DAVID J. Malan: отново Кажи? АУДИТОРИЯ: One. DAVID J. Malan: One. Така константно време. В най-добрия случай, Кристин е наистина в началото на списъка. И ние търсим номер 5, така че ние я намери. Така че не е голяма работа. Но тя трябва да е в началото на списъка в този случай. Какво ще кажете за нещо като Изтрий? Какво става, ако искате да изтриете елемент? Каква е горната граница и долната граница за изтриването на нещо от свързан списък? АУДИТОРИЯ: [недоловим] DAVID J. Malan: отново Кажи? АУДИТОРИЯ: п. DAVID J. Malan: н е наистина горната граница. Защото в най-лошия случай ние се опитваме за изтриване на Джак, като ние просто го направих. Той е чак в края. Ни отнема завинаги, или N стъпки, за да го намерят. Така че това е горна граница. Това е линейна, разбира се. И най-добрия случай времето за работа, или долните граници в най-добрия случай ще бъде постоянно време. Защото може би ние се опитваме да изтриете Кристин, и ние просто се късметлия тя е в началото. Сега чакай малко. Gabe също беше в началото, и ние също трябваше да актуализира Габе. Така че това не е просто една стъпка. Така че това е наистина постоянно време, в най-добрия случай, за отстраняване на най-малкия елемент? Това е, въпреки че може да бъде две, три, или дори 100 реда код, ако това е един и същ номер на линии, които не са в някакъв цикъл, и независимо от размера на списъка, абсолютно. Изтриване на елемент в началото на списъка дори ако трябва да се справят с Гейб, е все още времева константа. 

Така че това изглежда като масивна крачка назад. И това, което е загуба на време Ако в една седмица и седмица нула имахме не само pseudocode код, но действителното код да приложи нещо, което е дневник База N, или дневник, а по-скоро на N, база 2, от гледна точка на работа за времето си. Така че, защо, по дяволите, ще искаме да започнем с помощта на нещо като свързан списък? Да. 

АУДИТОРИЯ: Така че можете да добавите елементи в масива. DAVID J. Malan: Така че можете да добави елементи на масива. И това също е тематична. И ние ще продължим да се види това, този компромис, много като сме виждали компромис с сливат вид. Ние наистина може да се ускори търсене и сортиране, по-скоро, ако похарчите малко повече пространство и има допълнително парче на памет или масив за сливане вид. Но ние харчим повече пространство, но ние се спести време. В този случай, ние сме отказване от време, но ние сме набира гъвкавост, динамизъм, ако щете, което е може би една положителна черта. 

Ние сме също така харчат пространство. В какъв смисъл е свързан избройте по-скъпо по отношение на пространството от масив? Къде е допълнително пространство идва? Да? 

АУДИТОРИЯ: [недоловим] показалка. 

DAVID J. Malan: Да, ние Също така имате показалеца. Така че това е minorly досадно с това, че вече не съм I съхраняване само INT да представлява вътр. Аз съм съхраняване на едно цяло число и указател, който е 32 бита. Така че аз съм буквално удвояване размера на пространството, участващи. Така че това е компромис, но това е в случай на вътр. Да предположим, че вие ​​не сте съхраняване на ПНА, но предполагам, че всеки един от тези правоъгълници или всеки от тези хора представляваше една дума, на английски думата, която може да бъде пет знака, 10 герои, може би дори повече. После добави само 32 повече битове може да бъде по-малко от една голяма сделка. 

Какво става, ако всеки един от студентите в демонстрацията БУКВАЛНО студентски structs че имат имена и къщи, а може би телефонни номера и Twitter дръжки и други подобни. Така че всички полета започнахме Говорим за онзи ден, много по-малко на голяма сделка като нашите възли получите повече интересни и големи, за да харчат, а, допълнително показалка, само за да ги свърже заедно. Но наистина, това е компромис. И наистина, кодът е по-сложна, тъй като ще виж чрез обиране чрез че конкретен пример. Но какво, ако не са някои светия граал тук. Ами ако ние не направим крачка назад, но масивна стъпка напред и прилагане на данни структура, чрез която ние може да намерите елементи като Джак или Christine или други елементи в този масив в истинската константно време? Search е постоянна. Изтрий е постоянна. Insert е постоянна. Всички тези операции са постоянни. Това ще бъде нашата Светия Граал. И това е мястото, където ние ще вземем следващия път. Ще се видим тогава.