[За възпроизвеждане на музика] 

[Възпроизвеждане на видео] 

-Той Лъже. 

-За какво? 

-Не знам. 

-Значи Това, което знаем? 

-Това В 9:15, Ray Santoya беше на банкомат. -Да. Така че въпросът е, какво правеше той в 9:16? 

-Shooting На 9 милиметър в нещо. Може би е видял снайпериста. 

-Или Се работи с него. 

-Wait. Върнете се едно. 

-Какво виждаш? 

-Bring Лицето си до пълен екран. 

-His Очила. 

-Има Е отражение. 

-Това Е бейзболния отбор Nuevitas. Това е тяхното лого. 

-И Той говори за всеки, който носи, че якето. 

[END PLAYBACK] 

DAVID Malan: Добре. Това е CS50 и това е малко по- на [недоловим], с която сте рекламни кампании с проблем зададете четири. Днес ние започваме да изглежда малко по- дълбоко в тези неща, наречени указатели, която въпреки че е доста тайнствена тема, Оказва се, че това ще да бъде средство, чрез което ние може да започне изграждането и монтажа много по-сложни програми. Но го направихме на миналата сряда по пътя на някои claymation първия. Така че това, изземване, е Binky и ние го използва да погледнете в програма, която наистина не направи нищо интересно, но го е направил разкрие някои проблеми. Така че, за да започне днес, защо не ходим бързо през някои от тези стъпки, опитайте се да се дестилират в условия на човека точно това, което става тук и защо това е лошо, а след това преминете и действително да започне изграждането на нещо с тази техника? Така че това са първите, две линии в тази програма и от гледна точка на лаик, какво правят тези две линии? Някой, който е разумно комфортна с какво се е обявена на екрана? Какви са тези две линии правят? Това не е всичко, което различно от една седмица но има някои нови специален символ. Да? Обратно там. 

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

Така че това беше claymation въплъщение на това при която имате само две променливи, малки кръгли парчета от глина, който може да съхранява променливи, но като на увити стрелките показват, те не са действително сочи до всяка точка познат. Така че тогава имахме тази линия, а това е нов миналата седмица, изчистване на паметта разпределение, който е само на един луксозен начин за разказване на операционната система, Linux или Mac OS или Windows, хей, дайте ми малко памет, и всичко, което трябва да кажа, операционната система е това, когато той пита за памет. Това няма да е грижа какво започваш да правиш с него, но трябва да кажа, оперативната система за какво по пътя на изчистване. Да? 

АУДИТОРИЯ: Колко? DAVID Malan: Колко? Колко в байтове, и така, това, отново, скалъпена например, е просто казвам, дайте ми размера на инт. Сега, размерът на INT е четири байта или 32 бита. Така че това е просто начин на казвайки, хей, операционна система, ми даде четири байта памет че мога да използвам на мое разположение, и по-конкретно, какво прави изчистване възвръщаемост по отношение на това парче от четири байта? АУДИТОРИЯ: Адрес? DAVID Malan: Адресът. Адресът на това парче от четири байта. Точно. И така, това е, което се съхранява в крайна сметка в х и това е защо ние наистина не интересува какво броят на които адрес, е, дали това е OX1 или ОХ2 или някакъв загадъчен шестнадесетичен адрес. Ние просто се грижи картинно че тази променлива х сега е посочвайки, че парче от паметта. Така че стрелката представлява указател, или По-специално, адрес на паметта. Но отново, ние не обикновено се грижат какви са тези действителните адреси са. Сега, тази линия се казва това, което от гледна точка на лаик? Star х получава 42 запетая. Какво означава това? Искаш ли да отидеш? Не драскайте врата си. 

АУДИТОРИЯ: Адресът на х е в 42. 

DAVID Malan: Адресът на х е при 42. Не точно. Толкова близо, но не съвсем, защото има звездата, която е префикс тази х. Така че ние трябва да се ощипвам малко. Да? 

АУДИТОРИЯ: Стойността, че показалка х сочи е 42. DAVID Malan: OK. Стойността че показалеца х е посочвайки, да кажем, е 42, или казано по друг начин, звездата х казва, отидете на каквото и адрес е в х, независимо дали е 1 Oxford Улица или 33 Oxford Street или OX1 или ox33, каквото че цифров адрес, е, звезден х е dereferencing на х. Така че отивам на този адрес и след това пуснати на броя 42 там. Така че би било равностоен начин да се каже, че. Така че това е всичко наред и след това ние ще представлява картината както следва, където сме добавили 42-да, че парче от четири байтове на дясната ръка, но тази линия беше мястото, където нещата се объркват и главата Binky е изскочил разстояние в този момент, защото се случват лоши неща, когато можете сочен стойности за боклук или сте сочен за недействителна указатели, и аз казвам невалидни защото в този момент в история, това, което е вътре в у? Каква е стойността на у основава за последните няколко стъпки? Да? Какво е това? 

АУДИТОРИЯ: An адрес. DAVID Malan: An адрес. Тя трябва да бъде един адрес но аз го инициализира? Така че аз все още не съм. Така че това, което е известно, че там? Това е просто някаква стойност боклук. Тя може да бъде всеки адрес от нула до 2 милиарда, ако имате две участия на RAM, или нула до 4 милиарда, ако сте имам четири гигабайта RAM. Това е някаква ценност боклук, но проблемът е, че операционната система, ако това не ви е дал че парче от паметта конкретно че вие ​​се опитвате да отиде, това е като цяло ще причини това, което сме виждали като вина сегментация. Така че в действителност, всеки от вас, които имат бореше с проблеми на работното време или проблеми, които е по- обикновено с опитвам да разбера сегментация вина, че по принцип означава, можете да започнете да докосвате един сегмент от памет, която не трябва да бъде. Можете да започнете да докосвате памет, която операционната система не е да ви е позволено да се докоснат, независимо дали е като отидете твърде далеч в масив или като се започне сега, дали това е, защото сте докосвате памет, която току-що е някаква ценност боклук. 

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

И така картинно, ние сме представено с това две стрелки от х и у посочващо от на същото място. Така семантично, х е равно на х, защото и двете от тези, са еднакви съхранение адрес, ерго сочеше 42, и сега, когато ти казват звезда у, отидете на адрес в у, това е с интересен страничен ефект. Така адреса в Y е едно и също нещо като адрес в х. Така че, ако се каже, отидете на адрес в у и промяна на стойността до 13, кой друг е засегнат? X е, буква Г, така да се каже, следва да бъдат засегнати, както добре. 

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

Така че без по-нататъшно приказки, нека да разгледаме в случаите, когато това е в действителност се използва за известно време. Така че ние сме имали тази библиотека CS50 че има всички тези функции. Използвали сме GetInt много, GetString, Вероятно GetLongLong-рано в моя PSet една или така, но какво действително се случва? Е, нека хвърлим един бърз поглед под капака на една програма, която вдъхновява защо ние ви дам CS50 библиотека, и наистина като на миналата седмица, ние започнахме като тези, обучение колела изключен. Така че това вече е сортиран на аутопсия на това, продължава вече вътре в библиотеката CS50, въпреки че ние сега ще започнат да се движат далеч от него за повечето програми. 

Така че това е една програма, наречена scanf 0. Това е супер кратко. Тя просто има тези линии, но това въвежда функция, наречена scanf че ние всъщност ще видим в миг вътре в библиотеката CS50, макар и в малко по-различна форма. Така че тази програма по линия 16 е обявяване на променлива х. Така че ми даде четири байта за пад. Той е бил казвам за употреба, номер, моля, и след това това е интересен линия, която всъщност обвързва миналата седмица и този. Scanf, а след това забележите това отнема форматен, точно като ФОРМАТ, % и означава инт, а след това отнема втори аргумент, който изглежда малко фънки. Това е амперсанд х, и да се припомни, ние само видях тоя път миналата седмица. Какво означава амперсанд х представлява? Какво означава амперсанд направи в C? Да? 

АУДИТОРИЯ: Адресът на. DAVID Malan: Адресът на. Така че това е точно обратното на оператора на звезда, като има предвид, операторът на звездата казва, отидете на този адрес, на оператора амперсанд казва, разбера адрес на тази променлива, и така че това е ключов, защото целта scanf в живота е да се сканира на потребителя вход от клавиатурата, в зависимост от това, което той или тя видове, а после четат вход, който потребителя в променлива, но ние Видях в последните две седмици че този суап функция, която ние Опитах без усилие да приложат Просто разбито. Припомнете си, че с функцията за размяна, ако ние просто обявена А и Б, както цели числа, ние го успешно сменяте две променливи в тялото на суап Просто обичам с млякото и ОВ, но веднага след като се върна за размяна, това, което е резултат по отношение на х и у, оригиналните стойности? Нищо. Да. Нищо не се случи това време, защото суапове променят само своите локални копия, която е да се каже, всичко, този път, когато ние сме били минаваща през доводи до функции, ние сме просто преминаване копия на тези доводи. Можете да го направите с тази каквото си искате с тях, но те ще имат не осъществяване на първоначалните стойности. Така че това е проблем, ако можете искат да имат функция като scanf в живота, чиято цел е да сканирате въвеждане на потребителя от клавиатурата и след попълване на бланки, така да се се каже, че е, да се даде като променлива х на стойност, защото, ако бях на мястото да просто минават х да scanf, ако считате, логиката на последния седмица, scanf може да прави каквото иска с копие от х, но не можех постоянно се променят, освен ако х даваме scanf карта на съкровище, така да се каже, където х бележи място, при което минаваме в адреса на х, така че scanf може да отиде там и всъщност промяна стойността на х. И така наистина, всичко че тази програма прави ако правя scanf 0, в моя източник Указател 5м направи scanf 0, дот наклонена черта scanf, номер моля, 50, благодаря за 50. 

Така че това не е всичко, че интересно, но това, което се случва в действителност е, че веднага след като аз наричам scanf тук, стойността на х е постоянно променя. Сега, това изглежда хубаво и добро, а в действителност, това Изглежда, че ние наистина не се нуждаят на CS50 библиотеката вече всичко. Например, нека да тичам Това още веднъж тук. Позволете ми да го отвори за секунда. Нека се опитаме редица моля и вместо да каже 50 както преди, нека просто кажа не. OK, това е малко странно. ДОБРЕ. И само някои глупости тук. Така че това не изглежда да справят грешни ситуации. Така че ние трябва да минимално старт добавянето на някои за проверка на грешки за да се уверите, че потребителят има въвели в действителен брой като 50, защото очевидно пишете думи не се разпознава като проблематично, но вероятно трябва да бъде. 

Нека да погледнем тази версия сега това е моят опит да reimplement GetString. Ако scanf има всичко това функционалност вградена, защо са ни били рекламни кампании с тях обучение колела като GetString? Е, тук е може би моята собствена проста версия на GetString при който преди седмица, че може да съм казал, дайте ми низ и го наричат ​​буфер. Днес, аз отивам да се започне само казвайки Чар звезда, която, изземване, това е просто синоним. Тя изглежда страшно, но това е точно същото нещо. Така че ми даде променлива, наречена буфер че това ще се съхранява низ, кажете низа за употреба, моля, и след това, точно както и преди, нека се опитаме да заеме този урок scanf % и този път, а след това преминава в буфер. Сега, бърза проверка здрав разум. Защо ли не съм казвайки амперсанд буфер този път? Заключим от предишния пример. АУДИТОРИЯ: Char звезда е указател. DAVID Malan: Точно така, защото този път, Чар звезда вече е указател, на един адрес, по дефиниция на тази звезда е там. И ако scanf очаква един адрес, достатъчно е само да премине в буфер. Не е нужно да се каже амперсанд буфер. За любознателните, бихте могли направя нещо подобно. Тя ще има различно значение. Това ще ви даде по-показалка към указател, който всъщност валиден нещо в C, но за Сега, нека да го прости и да запази историята последователно. Аз съм просто ще премине в буфер и това е правилно. Проблемът обаче е, това. Нека да вървим напред и да стартирате тази програма след съставянето на този списък. Направи scanf 1. Дявол да го вземе, ми е съставител улов на моя грешка. Дай ми една секунда. Звън. Да речем, scanf-1.в. ДОБРЕ. Ето. Трябва ми. CS50 ID има разнообразен конфигурационни настройки че ви защити срещу себе си. Имах нужда да забраните тези от използвате трясък ръчно този път. Така че моля, низ. Отивам да вървим напред и да объркат в любимата ми свят здрасти. OK, за нищожна. Това не е това, което написах. Така че това е показателно за нещо е погрешно. Нека да вървим напред и да объркат в един наистина дълъг низ. Благодаря за нищожна и аз не знам ако аз отивам да бъде в състояние да го разбият. Нека се опитаме малко копие паста и да видим дали това ще помогне. Просто поставете много от това. Това определено е по-голяма низ от обичайното. Нека просто наистина го напиша. Не. Мамка му. Командата не е намерена. Така че това е свързано. Това е, защото аз поставили някои лоши герои, но това се оказва не се ходи на работа. 

Нека се опитаме още веднъж, защото това е по-забавно, ако ние всъщност го разбият. Нека да напишете това и сега, аз съм ще копирате един наистина дълъг низ а сега нека да видим дали можем може да се срине това нещо. Забележете, че пропуснахме пространства и нови линии и запетая и всички фънки герои. Enter. И сега мрежата е просто, че бавно. I задържан Command-V твърде дълго, ясно. Мамка му! Командата не е намерена. 

ДОБРЕ. Е, въпросът е, Въпреки това следното. И така, какво всъщност ще с тази декларация овъгляване звезда буфер по линия 16? Така че това, което съм аз все когато Декларирам указател? All аз съм се е четири байт стойност на наречен буфер, но това, което е вътре в него в момента? Това е просто някаква стойност боклук. Защото всеки път, когато се декларира променлива в C, това е просто някаква стойност боклук, и ние се започне да се спъне в тази реалност. Сега, когато аз кажа scanf, отидете на този адрес и сложи каквито и видовете потребителски в. Ако потребителят пише в здравей свят, добре, къде мога да го сложите? Buffer е на стойност един боклук. 

Така че това е нещо като стрела това е като посочи кой знае къде. Може би това е сочейки точно тук, в паметта ми. И така, когато потребителят видове в света Здравейте, програмата се опитва да постави на низ здравей свят наклонена черта 0 в това парче памет. Но с висока степен на вероятност, но очевидно не 100% вероятност, компютърът ще се срине след това програмата, защото това не е памет I следва да бъде позволено да се докоснат. Така накратко, тази програма е опорочено за точно поради тази причина. Аз принципно не правя това, което? Какви стъпки трябва да се пропусне, точно като ние пропуснахме с първи пример Binky си? Да? 

АУДИТОРИЯ: разпределение на паметта? 

DAVID Malan: разпределение на паметта. Аз не съм всъщност разпределя всеки спомен за този низ. Така че можем да се определи това в няколко начина. One, ние можем да го прости и в действителност, сега вие сте ще започне да видят замъгляване на границите между това, което масив е, какво низ е, какво е Чар звезда е, какво масив от символи е. Ето втори пример с участието на струнни инструменти и известие всичко, което съм правил на линия 16 е, вместо да каже че буфер ще бъде Чар звезда, указател към парче от паметта, Отивам да дам много активно себе буфер за 16 знака, и в действителност, ако сте запознати с термина буфериране Вероятно от света на видео, където видеоклип е буфериране, буфериране, буфериране. Е, каква е връзката тук? Е, Inside на YouTube и във вътрешността на видео плейъри обикновено е масив това е по-голям от 16. Тя може да бъде масив от размера на един мегабайта, може би 10 мегабайта, и в този масив прави за сваляне изтеглите цял куп от байтове, цял куп мегабайта видео и видео плейъра, YouTube или който и да е, започва четене на байтове, от които масив, и всеки път, когато видят Думата буфериране, буфериране, това означава, че играчът има Стигнахме до края на този масив. Мрежата е толкова бавно, че не разполага с презарежда масива с повече байта и така сте извън бита за да се покаже на потребителя. 

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

Хм, какво се е случило? String моля. Какво съм направил погрешно? Здравей, свят, буфер. Здравей Свят. Ах, аз знам това, което прави. ДОБРЕ. Така че това е четене до първото пространство. Така че нека да мамят само за миг и кажа аз просто исках да объркате нещо много дълго, като това е едно дълго изречение, това е едно, две, три, четири, пет, шест, седем, осем, девет, 10, 11, 12, 13, 14, 15, 16. ДОБРЕ. Това е наистина едно дълго изречение. Така че това изречение е по-дълъг от 16 символа и така, когато ударих Enter, какво ще се случи? Е, в този случай на история, бях обявен за буфер действително да е масив с 16 символа готови да отидете. Така един, два, три, четири, пет, шест, седем, осем, девет, 10, 11, 12, 13, 14, 15, 16. Така 16 знака, а сега, когато съм Прочети в нещо като това е дълъг изречение, какво ще се случи, е че аз отивам да прочетете в това е дълъг S-E-N-T-E-N-C-E, изр. 

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

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

Така че това изглежда проблематично. Аз бях подобри програмата, при която поне има някаква памет, но това би било да се ограничи на функцията за получаване GetString нанизи от някои крайни дължина 16. Така че, ако искате да подкрепи по-дълго изречения от 16 знака, С какво се занимаваш? Е, можете да увеличите Размер на този буфер до 32 или че изглежда вид кратко. Защо не можем просто да то 1000, но за бутане. Какъв е отговорът на интуитивно Просто се избягва този проблем, като прави ми буфер-голяма, като 1000 символа? С реализацията GetString този начин. Какво е добро или лошо тук? Да? АУДИТОРИЯ: Ако превърже много на пространството и да не я използват, тогава няма да може да преразпредели това пространство. DAVID Malan: Абсолютно. Това е разточителство, доколкото ако не го направите действително се нуждаят от тези 900 байта и все още сте с молба за 1000 общо, така или иначе, ти си просто отнема повече памет компютъра на потребителя, отколкото трябва да, и в крайна сметка, някои от които вече сте срещнали в живота, че когато сте използвате много програми и те изяжда много памет, Това всъщност може да повлияе на и работата на потребителя на компютъра. Така че това е нещо като мързелив разтвор, със сигурност, и обратно, това е не само разточителство, какъв проблем все още остава, дори ако аз направя моя буфер 1000? Да? 

АУДИТОРИЯ: The струна е с дължина 1001. DAVID Malan: Точно така. Ако си низ е с дължина 1001, имате точно същия проблем, и от моя аргумент, бих Просто след това да го направи 2000, но вие не знаете в напредне колко голям трябва да бъде, и все пак, аз трябва да компилирате програмата ми преди да позволите на хората да използват и изтегляне това. Така че това е точно типът неща, които библиотечните опитва CS50 за да ни помогне с и ние ще само поглед в някои от базовия изпълнението тук, но това е CS50 точка C. Това е файла, който е бил на CS50 IDE всички тези седмици, които сте използвали. Това е предварително компилирани и сте го използва автоматично от природата на наличието на непокрит L CS50 флаг с трясък, но ако аз превъртете надолу през всички тези функции, ето GetString, и само за да ви даде по- вкус на това, което се случва, нека хвърлим един бърз поглед към относителната сложност. Това не е супер дълги функция, но ние не го направи трябва да се мисли усилено за всички как да отида за получаване струни. 

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

Така че един бърз поглед, тук е просто една променлива с които аз отивам да следите от капацитета на моя буфер. Колко байта мога да се побере? Ето една променлива с п което аз отивам да се запази следи колко байта са всъщност в буфера или че потребителят е въвел. Ако не сте виждали това и преди, може да се определи, че дадена променлива като инт е грозен, който както подсказва и името, означава, че е не е отрицателен, и защо да го Аз някога искам да се занимавам уточняващи че едно цяло число не е просто едно цяло число, но това е неподписан инт? Това е неотрицателно инт. Какво означава [недоловим] означава? 

АУДИТОРИЯ: Тя е описващ сума памет, която може да бъде [недоловим]. 

DAVID Malan: Да. Така че, ако кажа, грозен, това всъщност е който ви дава един бит на допълнителна памет и изглежда някак глупаво, но ако има един бит на допълнителна памет, която означава, че имате два пъти повече стойности, които могат да представляват, тъй като тя може да бъде 0 или 1. Така че по подразбиране, едно цяло число може да бъде приблизително отрицателно 2 милиарда чак до положителен 2000000000. Това са големи диапазони, но тя все още е вид разточителство ако само се грижи за размери, които просто интуитивно трябва да бъде не-отрицателно или положително или 0, и след това, защо си губиш 2000000000 възможните стойности за отрицателни числа ако никога няма да ги използвам? Така че като кажа, грозен, сега ми инт може да бъде между 0 и грубо 4 милиарда. 

Така че тук е просто едно цяло число C по причини, ние няма да влязат в точно сега, както и защо това е вместо пад на Чар, но тук е същността на това, което се случва на, и някои от вас може да се използва, например, fgetc функция, дори и в PSet четири или по-късно, ние ще го видите отново в проблем зададете пет, fgetc е хубаво, защото, както е името вид, нещо като arcanely предполага, това е функция, която получава характер и това е така, това, което е коренно различна за това, което правим в GetString е, че ние не използвате scanf по същия начин. Ние просто пълзящи по стъпка-по-стъпка над каквото и потребителят е въвел, защото винаги можем да разпределите Чар и така можем винаги безопасно Посетете един Чар в даден момент, и магията започва да се случи тук. Отивам да превъртите надолу, за да средата на тази функция само накратко да Ви представим тази функция. Голяма като има изчистване функция, има функция презаделяне където презаделяне ви позволява да преразпредели парче памет и да я направи по-голяма или по-малка. Така дълга история кратко и с вълна от ръката ми за днес, знаем, че това, което GetString прави, е, че е нещо като на магически расте или свиване буфер като потребител видове в неговата или нейната низ. 

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

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

Уф. ДОБРЕ. Това беше една хапка но въпросът тук е, че причината ние имахме тези обучителни колела е така, защото най-ниското ниво, Има толкова много неща, които може да се обърка, че ние искахме да се справят с изпреварващо тези неща със сигурност в първите седмици от класа, но сега с PSet четири и пет и PSet отвъд ще видите, че това е по-до ви, но и вие сте по-способни за решаване на тези видове проблеми себе си. Всякакви въпроси относно GetString или GetInt? Да? 

АУДИТОРИЯ: Защо бихте се удвои капацитета на буфера а не само увеличаване на то с точната сума? 

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

Така че нека да разгледаме няколко на други странични ефекти на паметта, неща, които могат да се объркат и инструменти, които можете да използвате, за да се изравнят тези видове грешки. Оказва се, всички от вас, въпреки че check50 не Ви е казал толкова, са били писмено бъги код от една седмица дори и ако всички тестове са check50 преминали, и дори ако вие и вашият TF са супер уверена, че кода си работи както е предвидено. Вашият код е бъги или опорочено с това, че всички от вас, при използване на библиотека CS50, са изтичане памет. Вие сте били с молба операционната система за памет в повечето програми което сте написали, но сте всъщност никога не го върнат. Ти нарече GetString и GetInt и GetFloat, но с GetString, вие сте никога не нарича unGetString или Дай String Back или други подобни, но сме виждали че GetString прави достатъчно памет чрез изчистване или това функция презаделяне, който е само на много сходни по дух, и все пак, ние сме били молба на операционната система за памет и памет отново и отново но никога не ги дават обратно. 

Сега, като се отмени, се оказва, че когато програмата се затваря, всички на паметта се освобождава автоматично. Така че това не е било огромна сделка. Това няма да се прекъсне IDE или забави нещата, Но когато правят програми обикновено изтече памет и те са се кандидатира за дълъг период от време. Ако някога сте виждали глупавите плажна топка в Mac OS или пясъчния часовник на Windows, където това е вид забавя или мисли или мислене или просто наистина започва да се забави до пълзене, че е много вероятно би могло да бъде в резултат на теч с памет. Програмистите, които са написали софтуерът, който използвате попитайте на операционната система за памет на всеки няколко минути, всеки час. Но ако работите на софтуер, дори ако това е минимизиран в компютъра си за часове или дни наред, може да се кандидатства за повече и по- памет и всъщност никога не го използвате и така си код може да бъде, или програми може да има изтичане на памет, и ако започнете да протекат с памет, има по-малко памет за други програми, и ефектът е забави всичко надолу. 

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

Така че ето един пример от моята като бягане тази програма, като тече valgrind, на програма, наречена памет, и аз отивам да подчертаят линиите, които са в крайна сметка представлява интерес за нас. Така че има още повече отвличане на вниманието че съм изтрит от слайда. Но нека просто да видим какво това програма е в състояние да ни каже. Това е в състояние да ни казва неща като невалиден запис с размер 4. С други думи, ако докоснете памет, конкретно 4 байта памет че не трябва да има, valgrind мога да ви кажа, че. Невалиден запис с размер 4. Можете докосна четири байта че не трябва да има. Къде го направихте? Това е красотата. Дот Memory в ред 21 е мястото, където прецаках и затова е полезно. Много прилича GDB, тя може да помогне ви насочи към действителната грешка. 

Сега, това е малко по- многословно, ако не е объркващо. 40 байта в 1 полета са определено изгубени в рекордна загуба 1 от 1. Какво означава това? Е, това просто означава, че сте поискали 40 байта и никога не го е дал назад. Можете нарича изчистване или да ви нарича GetString и операционната система ти 40 байта, но никога не ви е дал освободил или освобождава памет, която, и да бъдем честни, ние никога не сме се покаже как да върне паметта. Оказва се, че там е супер проста функция, наречена безплатно. Взема един аргумент, нещото искате да освободите или да даде назад, но 40 байта, както изглежда, в тази програма са били изгубени в ред 20 от паметта Дот гр. 

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

АУДИТОРИЯ: [недоловим] пъти размера на инт което е 10 пъти, че [недоловим] DAVID Malan: Доброто и нека да обобщим. Така отпусне достатъчно място за 10 числа или 10, което е с размерите на инт, това е четири байта, така че 10 пъти 4 е 40, така че дясната страна, че аз съм Осветената е да ми даде 40 байта и съхраняване на адреса на първия байт в х. И сега на последно място и тук е мястото, където тази програма е бъгав, какво е лошо в ред 21 на базата на тази логика? Какво не е наред с линия 21? Да? АУДИТОРИЯ: Не можете да индекс в х [недоловим]. DAVID Malan: Да. Аз не трябва индекс в х подобно. Така синтактично, това е ОК. Какво е хубаво е, много като теб може да лекува името на масив като че ли това е указател, по подобен начин могат да се отнасят с теб показалец, сякаш това е масив, и така мога синтактично казват х конзола нещо, х скоба аз, но 10 е проблематично. Защо? 

АУДИТОРИЯ: Защото това не е вътре. 

DAVID Malan: Това не е вътре, че парче от паметта. Какво е най-голямата стойност I следва се поставя в тези квадратни скоби? 9, 0 до 9. Заради нула индексиране. Така 0 до 9 ще се оправи. Bracket 10 не е добро и но, припомни обаче, всеки път, Изглежда не мога да се опита да направи CS50 IDE катастрофа, като се въведе фалшиви ценности, тя не винаги да си сътрудничат, и наистина, често получите късмет, само защото операционната система не се забележите, че сте все така леко мине известно парче от паметта, защото ти остана в рамките на технически сегмента си, но повече за това в операционните системи клас, и така нещо подобно можеше много лесно остават неразкрити. Вашата програма никога няма да се блъсне последователно, но може би от време на време. 

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

Нека да превъртите до самия връх. Тук е мястото, където започнахме. Така че това не е чак толкова много продукция. Ето, че невалиден запис с размер 4 на ред 21. Е, това, което беше ред 21? Line 21 е точно това и че има смисъл че аз съм в валидно написването 4 байта, защото аз съм опитвайки се да сложи това число, който може да бъде всичко, то просто се случва да бъде нула, но аз се опитвам да го постави на място, който не принадлежи на мен. Освен това, тук долу, 40 байта в една блокове определено са загубили в рекордно 1. Това е, защото, когато аз наричам изчистване тук, аз всъщност никога не освободи паметта. 

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

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

Така че ние въведохме няколко седмици Преди понятието масив. Масивът е хубаво, защото това е трудно да се почисти нашия код защото ако исках да напиша програма с множество студенти или няколко имена и къщи и общежития и колежи и всичко това, бихме могли да съхранявате всичко по- чисто вътре в масив. Но предлагам един недостатък на масив досега. Дори и да не съм го страдал себе си в една програма, просто инстинктивно, това, което е лошо нещо около един масив, може би? Чух някои шумове. АУДИТОРИЯ: Това е трудно за промяна на размера. DAVID Malan: Това е трудно за промяна на размера. Вие не можете да променяте размера на масив, в действителност, само по себе в C. Можете да отпусне още масив, премести всичко от стария в новото, а сега има някои допълнително пространство, но това не е като едно език като Java или Python или произволен брой други езици, с които някои от вас може да е запознат, където можете може просто да поддържа добавянето неща втръсване до края на масив. Когато имате масив от размер 6, която е неговия размер, и толкова много харесвам идеята по-рано като буфер с определен размер, ще трябва да отгатне от портата какъв размер искаш да бъдеш? Ако Предполагам твърде голям, можете да започнете да губите пространство. Ако Предполагам твърде малък, можете Не може да съхранява тези данни, най-малко без много повече работа. 

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

АУДИТОРИЯ: A показалка. 

DAVID Malan: A показалка. Така че всеки един от тези стрели тук представлява указател или просто един адрес. Така че, с други думи, ако искам да съхранява списък с номера, Не мога просто да го съхранява, ако искам способността да расте и да се свие моята структура данни в масив. Така че аз трябва да има малко повече изтънченост, но забележете, че това снимка вид подсказва че ако сте просто имам малко теми свързващ всичко заедно, може би не е толкова трудно да се направи място между две от тези правоъгълници или две от тези възли, тъй като ние ще започнем наричайки ги, поставете нов възел, и след това с някаква нова тема, просто Отървете се от три възли заедно, първата, последната, и този, че просто поставя в средата. 

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

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

DAVID Malan: Така амперсанд ние ще използваме, за да получите на адреса на един възел потенциално. Но ние трябва друг черта на C за за да ми даде възможност за създаване на този обичай правоъгълник, този обичай променлива, ако щете, в паметта. АУДИТОРИЯ: A структура на. DAVID Malan: A структура на. Спомнете си от миналата седмица, ние въведохме структура на това сравнително проста дума че ни позволява да направим нещата по този начин. C не дойде с данни структура, наречена студент. Той идва с инт и плувка и Чар и такава, но тя не идва с ученик, но можем да създадем тип студент данни, студент структура, с този синтаксис тук. И вие ще видите това отново и отново. Така че не се притеснявайте за запаметяването на ключовите думи, но ключовата дума, която е важна е просто на факта, че ние казахме структура на и след това ние го нарече ученик и вътре на ученика е име и къща или общежитието или други подобни. 

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

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

Така че, ако приемем, сега можем да приложат това нещо в C, как правим в действителност започнете преминаващи този? Ами, всъщност, всичко, което трябва да направите, е обхождане от ляво на дясно и просто вид поставете възли или изтриване на възли или търсене на неща, където искаме, но да се направи това, да вървим напред и да направи нещата малко по-реално, защото това е било досега супер ниско ниво. Дали някой буквално искал да бъде на първо място? ДОБРЕ. Хайде нагоре. Как се казваш? 

DAVID: Дейвид. DAVID Malan: Дейвид. Приятно ми е. Аз също. Всичко е наред. И ние се нуждаем от номер 9. Не е толкова добър, колкото първия, може би. OK, номер 9. Редица 17, моля. Нека да се върнем малко по-нататък. Брой 22, моля, и Какво ще кажете за по-назад ако мога да видя никакви ръце с всичката светлина, или не. Някой се доброволец точно там. Искате ли да излезе? Вашият предмишницата е насилствено качвах. OK, 17. 22. 26 се слиза. Бихте някой друг искал да forcefully-- Хайде нагоре. Разрешава се действително доброволец. 

Така много бързо, ако вие може да подредите Просто обичам себе си възлите на екрана. Благодаря. И вие ще бъдете 26. Всички правилни и бързи запознанства. Така че аз съм Дейвид и вие също сте? DAVID: Дейвид. DAVID Malan: А вие сте? JAKE: Джейк. Сю: Сю. ALEX: Alex. RAPHAEL: Рафаел. TAYLOR: Taylor. DAVID Malan: Taylor. Отлично. Така че това са нашите доброволци за днес и да тръгнат напред и измести малко по този начин, и просто отидете напред и да запази държите вашите номера като сте или си Първият знак и с помощта на лявата си ръка, давай напред и просто изпълнение тези стрели, просто така, че лявата ръка е буквално сочейки към каквото и да трябва да посоча най-, и се даде някаква стая, така че визуално можем да видим ръцете си всъщност посочващо, а може просто да посоча вид на земята е добре. 

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

Сега, ако искам да всъщност вмъкнете някои нова стойност, да вървим напред и да направим това. Ние имаме възможност сега да избере друг възел. Кажете нека да започнем с mallocing 55. Някой би ли нещо против да бъде изчистване? OK, хайде нагоре. Как се казваш? RAINBOW: Rainbow. DAVID Malan: Rainbow? Всичко е наред. Изчистване Rainbow. Хайде нагоре. Така че сега ние трябва да се запитаме алгоритмично, където можем да сложим 55. Така че всички ние знаем, Очевидно, когато тя вероятно принадлежи, ако ние се опитваме да запази тази сортирани и ако вие може да отнеме една крачка назад, така че ние не падне на сцената, че ще бъде страхотно. Така че всъщност, Rainbow, започнем отначало тук с мен, защото ние като компютърът вече могат да само вижте една променлива в даден момент. Така че, ако това е първия възел. Забележете, че той не е един възел, той е просто една показалка, и затова той е съставен, за да бъде само размера на показалеца, не един от тези пълни правоъгълници. Така че ние ще се проверява по всяко итерация е 55 по-малко от 9? Не. Е 55 по-малко от 17? Не. По-малко от 22? По-малко от 26? По-малко от 34? И така, сега, очевидно Rainbow принадлежи към края. Така че да е ясно и какво е вашето име, Тейлър? 

TAYLOR: Taylor. DAVID Malan: Така сред Тейлър лява ръка и ръцете Rainbow е тук, чиято ръка трябва да се отбележи в това, което в За да въведете 55 в този списък? Какво трябва да направим? Да? 

АУДИТОРИЯ: ръка на Тейлър Необходимо е да се отбележи лявата. 

DAVID Malan: Точно така. Така вмъкване на възел в края на списъка е доста проста, защото просто Taylor трябва да се отбележи, вместо към земята или ние ще го наричаме нищожна, нищожна е нещо отсъствието указател или на специална нулев указател, вие сте Ще посоча с лявата си ръката на Rainbow и след Rainbow, Къде трябва да си ляв ръката вероятно посоча? Първа. Това не е добре, ако ръката й е нещо на сочеше тук или сортиране на всеки по какъв начин. Това щеше да се счита стойност на боклука, но ако тя сочи към някои известна стойност, ние ще го наричат ​​нула или нула, това е ОК защото имаме план в тази и ние знаем, списъкът е завършена. 

Така че това, което е още една сравнително прост случай? Можем ли изчистване 5? Хайде нагоре. Как се казваш? TIFFANY: Tiffany. DAVID Malan: Съжалявам? TIFFANY: Tiffany. DAVID Malan: Tiffany. Всичко е наред. Tiffany е malloced със стойността 5. Хайде нагоре. Това е един сравнително лесно също, но нека разгледаме цел на операциите сега. Това беше доста лесно с Тейлър в края. Номер 5, разбира се, по-малко от 9, и така имаме Дейвид, имаме Tiffany, и какво е вашето име? 

JAKE: Джейк. 

DAVID Malan: Джейк. Tiffany, Джейк, и Дейвид. Чия ръка следва да се актуализира на първо място? Какво искаш да правим тук? Има няколко възможни начина, но Има също така и един или повече погрешни начини. 

АУДИТОРИЯ: Започнете с лявата. 

DAVID Malan: Започнете с най-лявата. Кой е най-лявата тук тогава? АУДИТОРИЯ: Първо. 

DAVID Malan: OK. Така че започнете с първата и когато правиш искате да актуализирате ръцете на Давид да бъдат? АУДИТОРИЯ: към 5. DAVID Malan: OK. Така Давид, буква в пет или Tiffany тук и сега? 

АУДИТОРИЯ: Tiffany сочи към 9? DAVID Malan: Perfect, с изключение на Binky главата просто вид падна, нали? Защото това, което не е наред с тази снимка буквално? АУДИТОРИЯ: Нищо не сочи. DAVID Malan: Нищо не е сочейки към Джейк сега. Ние буквално сираче 9 и 17, и ние сме буквално изтече цялата памет, защото от актуализиране на ръката на Давид първо, това е глоба, доколкото това е правилно сочеше Tiffany сега, но ако никой не е имал далновидни, за да посоча Джейк, тогава сме загубили цялост на този списък. Така че нека да отмените. Така че това е нещо добро за спъне но нека да поправи сега. Какво трябва да направим първо, а? Да? 

АУДИТОРИЯ: Tiffany трябва да сочи към 9? DAVID Malan: Аз не мога се получи, че в близост до вас. Кой трябва да се отбележи в 9? 

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

DAVID Malan: Добре. Така че трябва да Tiffany първа точка в 9. Така че трябва да се Tiffany на същата стойност Давид, който изглежда съкратени за миг, но това е добре, защото сега, втора стъпка, можем да актуализираме ръката на Давид да посочи в Тифани, а след това, ако Именно това се чисти нещата като че това е вид като пролет, Сега това е правилното поставяне. Така отлична. Така че сега сме почти там. Нека да вмъкнете един последен стойност, като стойността 20. Ако можехме да изчистване един последен доброволец? Хайде нагоре. Така че това е малко по-сложно. Но наистина, кодът сме писмено, макар и устно, е просто като да имаш един куп ако условията на предприятието, нали? Имахме състояние проверка дали то принадлежи в края, може би началото. Ние трябва някаква линия да намери място в центъра. Така че нека да се направи, че с това, което ти е името? 

ERIC: Eric. 

DAVID Malan: Ерик? Ерик. Приятно ми е. Така че ние имаме 20. По-малко от пет? Не. По-малко от девет? Не. По-малко от 17? Не. ДОБРЕ. Той принадлежи тук и Вашите имена отново са? Сю: Сю. DAVID Malan: Сю. ALEX: Alex. DAVID Malan: Sue, Алекс, а? ERIC: Eric. DAVID Malan: Eric. Трябва да се актуализира първата чиито ръце? 

АУДИТОРИЯ: Eric. ДОБРЕ. Така че Ерик трябва да посочи къде? На 22. Good. И сега какво следва? Sue след това може да се отбележи най-Eric и сега, ако вие просто направи някои помещение, което е добре визуално, сега ние сме направили вкарването. Така че нека сега разгледаме един въпрос, но Благодаря ви много за нашите доброволци. Много добре направено. Можете да запазите тези, ако искате. И ние имаме един прекрасен подарък, ако раздяла всеки, който искате да вземете стрес топка. Нека само да мине този надолу. Така че какъв е храна за вкъщи от това? Това изглежда да е невероятно дотолкова, доколкото имаме сега въвежда алтернатива на решетка, която не е толкова ограничено за масив от някои фиксиран размер. Те могат да растат динамично. 

Но много като сме виждали от седмици минало, ние никога не се получи нищо безплатно, като със сигурност има компромис тук. Така че с главата на свързан списък, е тази динамика? Тази способност да растат и честно казано, можехме да направим за изтриване и може да се свие, когато е необходимо. Каква цена плащаме? Два пъти повече пространство, на първо място. Ако погледнете на снимката, вече не Аз съм съхраняване списък от цели числа. Аз съм съхраняване списък на числа плюс указатели. Така че аз съм удвояване на размера на пространството. Сега, може би това не е такава голяма работа 4 байта, 8 байта, но със сигурност може да се добавят за големи масиви от данни. Какво е друг недостатък? Да? 

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

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

Така че това е, което ние наричаме в компютърни науки структура данни LIFO. Последен вътре, първо се изважда. И ние ще видим след дълго защо които биха могли да бъдат полезни, но за сега, Просто помисли за имота. И това е нещо глупаво ако смятате за това как трапезарията го прави. Всеки път, когато чисти тави и сложи най-пресните тези на върха, бихте могли да имат по-рано чиста но в крайна сметка много мръсна и прашна табла на самото дъно ако никога всъщност стигнем до дъното на това стак, защото просто продължават да отправят новото и чистите тези на върха му. Същото нещо може да се случи в супермаркет също. Ако имате витрина на мляко и всеки път, CVS или който и да получава повече мляко, просто бутам млеката вече имате на гърба и сложите новите отпред, започваш да имат някои доста груба мляко в края на структурата на данните, защото тя винаги е на дъното, или еквивалентно тя винаги е на гърба. 

Но има и друг начин да се мисли за редят на опашка данни и например това. Ако вие сте един от тези хора, които харесва да се подредят извън магазина на Apple когато един нов продукт идва , вие вероятно сте не се използва данни стак структура, защото вие ще отблъсне всеки друг, който е редят на опашка, за да закупите някои нова играчка. По-скоро, вие сте вероятно използва каква структура от данни или каква система в реалния свят? Надяваме се, че това е линия, или по- правилно или повече British-подобни, опашка. И се оказва, опашката е и структура на данните по компютърни науки, но опашка има много различна собственост. Това не е LIFO. Последен вътре, първо се изважда. Пази Боже. Това е вместо FIFO. Първо, първа изходяща. И това е нещо добро за справедливост заради " Със сигурност, когато сте облицовка до супер рано сутринта. Ако отида там на първо място, вие искам да се махна първо, както добре. 

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

[За възпроизвеждане на музика]