[Powered by Google Translate] [Седмица 6] [Дейвид Дж. Малан] [Харвардския университет] [Това е CS50. [CS50.TV] 

Това е CS50, и това е началото на Седмицата на 6, така няколко нови инструменти вече са на разположение, за да се възползват от първият от които се нарича CS50 Style. Коефициентите са, ако сте като мен или някоя от преподаването събратя, вие вероятно сте виждали програма, чийто стил изглежда малко нещо подобно. Може да започнете рязане някои ъгли, късно през нощта, или ще се справят с нея по-късно, и след това TF или Калифорния идва в работно време. След това за нас е трудно да се чете. Е, този код е синтактично правилно и ще се компилира и тя действително ще работи. Но това определено не е 5 за стил. 

Но сега, ако отидем в тази директория тук и забележите, че имам conditions2.c- и аз тичам тази нова команда, style50, този файл conditions2.c, Въведете, забележите, че той ме информира, че е стилизирана. Gedit забелязах, че файла е било променено на диск, и ако щракнете върху презареди, всичките си проблеми сега са автоматизирани. [Аплодисменти] Това е едно от нещата, които направихме през този уикенд. Осъзнайте, че е несъвършен, защото има някакъв код че тя просто не ще бъде в състояние да Stylize перфектно, но знайте, че сега това е инструмент, който можете да се възползвате от дори и само да спретнат на някои от най-errantly поставени фигурни скоби и други подобни. 

Но още по-убедителна в момента е CS50 Проверете. С CS50 Проверете, всъщност можете да изпълняват едни и същи тестове коректност на вашия собствен код, че преподавателските събратя са в състояние да. Това е помощна програма за команден ред, който идва сега в уреда веднага след като си направи update50 според pset 4 спецификации, както и да го използвате по същество по този начин. Изпълните командата check50. След това преминава в аргумент на командния ред, или по-известна като ключ или флаг. Като цяло, неща, които имат тирета се нарича ключ програма за команден ред, така че в уточнява проверките, които искате да изпълните. 

Тестове, които искате да изпълните, са идентифицирани по уникален начин чрез този низ, 2012/pset4/resize. С други думи, това е просто произволно, но уникален низ , които ние използваме, за да може еднозначно да идентифицира коректност pset 4 тестове. И тогава сте задали, разделени с интервал списък на файловете, които искате да качите CS50 Проверка за анализ. Например, ако отида в моето решение тук за resize.c- нека се отвори по-голям терминал прозореца и отивам напред и тичам да се каже check50 в 2012/pset4/resize, и тогава ще отида напред и да посочи имената на файловете, resize.c, и след това натиснете Enter, го компресира, Тя качени, той проверява, и аз просто не успя цял куп тестове. В червено горе в ляво казва, че съществуват resize.c и BMP. Това беше тест. Това е въпросът, който попита. И това е нещастен, защото отговорът е невярна. Бял текст под него казва, че очаква bmp.h да съществува, и това е просто моя вина. Забравих да го качите, така че аз трябва да качите и двата файла, resize.c и bmp.h. Но сега да забележите, всички от другите тестове са в жълто, защото те не са работи, и така усмивка на лицето е вертикална, защото той не е нито щастлив, нито тъжен, но ние трябва да се поправи този въпрос в червено преди тези проверки ще се проведе. 

Позволете ми да поправя това. Нека я увеличите и повторение на това, този път с bmp.h на командния ред, Enter, и сега, ако всичко върви добре, е да се провери и след това се върнете в резултат на задръжте дъха си всичко зелено, което означава, че правя наистина и на pset 4 досега. Можете да видите и да се направи извод от описателен текст точно това, което ние тествахме. Ние тествахме първия файлове съществуват? След това се изпитват прави resize.c компилация? Тогава ние тествахме не го преоразмерите 1x1 пиксела BMP, когато N, преоразмеряване фактор, е една. Сега, ако вие нямате представа какво е N, ще след като се потопите в pset 4, но това е просто здрав разум проверите, за да сте сигурни, че не сте преоразмеряване изображение на всички, ако преоразмеряване фактор е 1. Ако, от друга страна, преоразмерява 1x1 точки, за да 1x1 пиксела BMP 2x2 правилно Когато N е два, а след това по същия начин, мина формира съответно. 

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

Сега осъзнавам, тестовете не са непременно изчерпателни. Само защото можете да получите на екрана на зелено усмихнати лица не означава, кода си е перфектен, но това не означава, че той е преминал някои от изпитванията, предписани от спец.. Понякога ние не ще пусне проверки. Например, криминале, един от аспектите на pset 4, е вид разочароващо, ако ние ви даваме отговор на това, което е, и има редица начини, за да разкрие кой е човекът в тази червена шум. Спец. винаги ще определят в бъдеще за pset 5 напред какви проверки съществува за вас. Ще забележите, че има този бял URL на дъното. За сега, това е само диагностика изход. Ако посетите този адрес, вие ще получите един куп луди, шифрограми , което можете да търсите чрез, но това е най-вече за персонала , така че да могат да се диагностицират и отстраняване на грешки на грешки в check50 себе си. 

Без шум, нека продължим там, където бяхме. CS50 библиотека взехме за даденост, за няколко седмици, но след това миналата седмица, ние започнахме пилинг обратно един от слоевете от него. Ние започнахме да остави настрана низ в полза на това, което вместо? [Студенти] Чар. Чар *, което е знак * през цялото това време, но сега не е нужно да се преструвам, че това е действително тип данни низ. Напротив, той е бил синоним на видове за Чар * и низ е последователност от символи, така че защо има ли смисъл да представляват струни Чар * и? Какво означава Чар * в рамките на тази концепция на низ? Да. >> Студентски] Първият знак. Добре, първият знак, но не съвсем първия знак. Това е [Студенти] Адрес. Добре, адреса на първия знак. Всичко, което е необходимо, за да представлява низ в паметта на компютъра е само уникалния адрес на първия байт. Ти дори не трябва да се знае колко време е защото как може да ви разбера, че динамично? Студентски] Дължина на тетивата. Можете да се обадите низ дължина, отлично, но как работи низ дължина? Какво прави той? Да. [Student] Продължавайте, докато не получи нула характер. Да, точно така, той просто повтаря за цикъла, а линия, от * до края, а краят е представена от \ 0, така наречения нулев характер, NUL, да не се бърка с нула, което е указател, , която ще дойде отново в разговор днес. 

Отлепи назад слой на GetInt, и тогава ние се погледнете в GetString и припомни, че на тези функции, или наистина, GetString, е използване на определена функция действително разбор, че е четат или анализират, вход на потребителя. И каква е тази нова функция? Scanf или sscanf. То всъщност се предлага в няколко различни вкусове. Има scanf, има sscanf, има fscanf. За сега, обаче, нека се съсредоточим върху най-лесно е показано, и ме пусна напред и да се отворят в уреда файл, като това, scanf1.c. Това е супер проста програма, но това не нещо, което никога не съм правил без помощта на библиотеката CS50. Това стана Int от потребителя. Как действа тя? Е, в ред 16 има, забележите, че ние заявяваме INT нарича X, и в този момент в историята, каква е стойността на х? [Чува студент отговор] [David M.] Право, кой знае, някаква стойност боклук потенциално, така че в 17, ние просто кажете на потребителя дайте ми номер, моля, и 18 е мястото, където става интересно. Scanf изглежда да заеме една идея от ФОРМАТ в това, че използва тези формат кодове в кавички. % D, разбира се десетично число. Но защо съм преминава в и х а не само х? Първият от тях е правилен. Да. [Чува студент отговор] Точно така, ако целта на тази програма, като функцията GetInt, е да се получи едно цяло число от потребителя могат да преминат функции всички променливи, което искам, но ако не ги предаде чрез позоваване или по адрес или от показалеца, всички синоним за целите на днешните тогава тази функция няма възможност да променя съдържанието на тази променлива. Това ще премине в копие, точно като бъги версия на суап , че сме говорили за няколко пъти. 

Но вместо това, чрез правене & X, аз съм буквално минава в какво? [Student адрес. >> Адрес на х. Това е като изготвяне на карта за функцията, наречена scanf и казва тук, това са посоки парче на паметта в компютъра че можете да отидете съхранява някои цяло число. За sscanf сега правя, че какво оператор, какво парче на синтаксиса, ще трябва да използвате въпреки че ние не може да го види, защото някой друг е написал тази функция? С други думи - какво е това? [Student] X чете. Ще има някои четене, но само по отношение на х. Ако scanf се предава на адреса на х, синтактично, какво оператор е длъжен да съществуват някъде в рамките на изпълнението scanf, така че scanf всъщност може да напишете номер 2 на този адрес? Да, така *. Спомнете си, че * е сочен оператор, което по същество означава отида там. 

След като сте били предадени на един адрес, какъвто е случаят тук, scanf вероятно е, ако ние всъщност огледа изходния код прави * х или еквивалент, да отида на този адрес и да има някаква стойност. Сега, като за това как scanf получава вход от клавиатурата, ние ще размахва ръцете ни за днес. Просто се предположи, че операционната система позволява sscanf да говори клавиатурата на потребителя, но в този момент сега на ред 19, когато ние просто отпечатате X, тя изглежда да е случаят scanf е едно цяло число в х. Това е точно как scanf работи, и припомни миналата седмица това е точно как GetString и GetInt и другото си семейство от функции в крайна сметка работи, макар и с леко отклонението като sscanf което означава, сканирате низ вместо на клавиатурата. Но нека да разгледаме най-малко разсейването на това. В scanf2, че всъщност се е провалил. Какво не е наред и аз ще се скрия коментар, който обяснява като много по- какво не е наред с тази програма, версия 2? Бъдете като технически е възможно по това време. Изглежда доста добре. Това е добре разчленен, но Добре, какво ще кажеш да го режеш по-кратки въпроси? Линия 16. Какво е линия 16 правиш в прецизен, но технически английски език? Да се ​​малко неловко. Да, Майкъл. Студентски] Това сочи първата буква на низ. 

Добре, в близост. Нека ощипвам, че малко. Посочването на първата буква на низ, за ​​обявяване на променлива наречена буфер , който ще се отбележи първият адрес на низ или по-скоро, че ще посочи по-конкретно на знака. Забележете, че всъщност не е насочена навсякъде, защото няма оператор за присвояване. Не е знак за равенство, така че всичко, което правим е разпределяне на променлива наречена буфер. Това се случва на 32 бита, защото това е показалеца, и съдържанието на буфера вероятно в крайна сметка ще съдържа адреса на Чар, но за сега, какво буфер съдържа? Просто някои фалшив, кой знае, някои боклук стойност, защото не сме изрично го инициализира, така че ние не трябва да поеме нищо. Добре, сега линия 17-какво линия 17? Може би това ще се затопли всичко. Той отпечатва низ, нали? Той отпечатва String моля. 

Линия 18 е вид познат с това, че току-що видяхме вариацията на това но с различен код формат, така и в ред 18, ние казваме scanf тук е адреса на парче на паметта. Искам да звъни в низ, както се подразбира от% S, но проблемът е, че не сме направили няколко неща тук. Какво е един от проблемите? [Студентски] се опитва да сочен с нулев указател. Добри, NULL или просто в противен случай неизвестен указатели. Вие предаването scanf адрес, но току-що казахте преди малко че това е адресът е някакъв боклук стойност, защото ние не всъщност го възложи на нещо, и така казваш scanf ефективно сложи низ тук, но ние не знаем къде тук е, така че ние всъщност не са разпределени памет за буфер. Освен това, това, което сте и дори не казва scanf? Да предположим, че това е парче от паметта, и то не е боклук стойност, но все още не казваш scanf нещо важно. [Student] Къде всъщност е, амперсанд. Ampersand, така че в този случай, това е добре. Тъй като буфер се вече декларирани като показалка * парче на синтаксиса, ние не трябва да използвате амперсанд , защото това е вече един адрес, но мисля, че аз го чух тук. [Student] Колко голяма е тя? Добре, ние не казваш scanf колко голям е този буфер, което означава, че дори ако буфер указател, Казваш, scanf, сложи низ тук, но тук може да бъде два байта, може да е 10 байта, тя може да бъде един мегабайт. Scanf не е идея, а защото това е парче от паметта Предполага се, че това не е низ все още. Това е само низ, след като пишете символи и \ 0 до това парче на паметта. Сега е само някои парче на паметта. Scanf няма да знае кога да спре да пише на този адрес. 

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

Ето, казвам scanf тук е парче на паметта. Този път, това е всъщност парче от паметта, но защо е тази програма все още експлоатация? Какво се е случило все още? Казах да ми даде 16 байта, но- [Student] Какво ще стане, ако напишете в повече от 16? Точно така, какво ще стане, ако на потребителя видове в 17 знака или 1700 знака? В действителност, нека да видим, ако ние не можем пътуване през тази грешка сега. Това е по-добре, но не е съвършен. Нека вървим напред и тичам да scanf3 за съставяне на тази програма. Нека да scanf3, String моля: Здравейте, и ние като че ли се оправи. Нека се опитам малко по-дълъг, здравей там. Добре, нека да Здравейте как сте днес, Enter. Първи вид на щастлив тук, нека кажа здрасти как сте. Дявол да го вземе. Добре, така че ние сме късметлии. Нека видим дали не можем да поправя това. Не, това няма да ми позволи да копирате. Нека опитаме отново. Добре, да се изправя. Ще видим колко дълго мога да се преструвам да фокусира, докато все още се прави това. Дявол да го вземе. Това е доста подходящо, всъщност. Точно така. Точка. 

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

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

[Student] Как така не трябва да се сложи амперсанд до частта Добър въпрос. Как дойда не трябва да се сложи амперсанд до характера масив, както направих аз преди с повечето от нашите примери? Краткият отговор е масиви са малко по-специален. Почти можеш да мисля, че буфер за реално адрес, и то просто така се случва да бъде случай, че на площада нотация на конзолата е удобство, така че можем да отидем в конзола 0, скоба 1, скоба 2, без да се налага да се използва нотацията *. Това е малко на бяла лъжа, тъй като масиви и указатели , в действителност са малко по-различно, но те могат да често, но не винаги се използват взаимозаменяемо. Накратко, когато функцията се очаква указател към парче от паметта, можете да го давате адрес, който бе върнат от изчистване, и ще видим изчистване отново след дълго, или може да го предаде на името на масива. Не е нужно да правите амперсанд с масиви, тъй като те вече са по същество като адреси. Това е едно изключение. Квадратни скоби ги правят специален. 

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

GetString е идеален пример. GetString, написани от нас, няма представа колко символа да се очаква, така че фактът, че можем да разпределят парчета непрекъсната памет е добро. Масивите също решаване на проблема видяхме преди няколко седмици код започва да се прехвърли в нещо много лошо проектирани. Спомнете си, че съм създал студент структура, наречена Дейвид, и това всъщност е алтернатива, въпреки че, да има променлива наречена име и друга променлива, мисля, къща, и друга променлива ID, защото в тази история съм искал да въведе нещо друго като Роб в програмата, така че след това реших, чакай малко, Трябва да преименувате тези променливи. Нека наричаме мина NAME1, ID1, house1. Нека наречем Роб NAME2, house2, ID2. Но тогава чакай малко, какво да кажем за Томи? Тогава имахме още три променливи. Ние въведохме някой друг, четири набори от променливи. Светът започна да се разхвърлян много бързо, така че ние въведохме structs, и какво е завладяваща около една структура? Какво означава структура C ви позволи да направите? Това е наистина неловко днес. Какво? >> Чува студент отговор] Да, по-специално, typedef ви позволява да създадете нов тип данни, и структура, структура на ключова дума, ви позволява да капсулират концептуално свързани парчета на данните заедно и след това да ги наречем нещо като ученик. 

Това беше добре, защото сега ние можем да проектираме много повече вид на концептуално съответствие идеята на един студент в променлива , а не произволно като един низ, за ​​лична, и така нататък. Масивите са приятни, защото те ни позволяват да започне почистване на нашия код. Но това, което е недостатък на масив? Какво може нали? Да. Студентски Трябва да знаете, колко е голям. Трябва да знаете, колко е голям, така че това е вид болка. Тези от вас, с предварително програмиране опит знам, че в много езици, като Java, можете да поискате парче на паметта, по-специално масив, колко големи са, с дължина, имущество, така да се каже, и това е наистина удобно. В C, не може дори да се нарека strlen на родово масив защото strlen, като думата предполага, е само за струнни, и можете да разбера дължината на низ, защото на тази човешка конвенция \ 0, но масив, по-родово, е само парче от паметта. Ако това е масив от цели числа, не ще да има някакъв специален символ в края те чака. Трябва да се помни дължината на масива. Друг недостатък на масив надигна глава по себе си GetString. Какво е друг недостатък на масив? Господине, само ти и аз днес. [Чува студент отговор] >> Това е какво? Той е обявен на стека. Добре, декларирани в стека. Защо не ти харесва? [Student], защото той се използва повторно. То се използва повторно. Добре, ако използвате масив да бъде заделена памет, например, не можете да го върнете, защото това е в стека. Добре, това е недостатък. А какво ще кажеш за един друг с масив? След като го разпределят, вие сте някак прецакани, ако имате нужда от повече пространство от този масив. 

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

Сега, само за улов тук е, че почти се чувства като имам цял куп различни променливи. Това изглежда като пет различни променливи потенциално. Но какво, ако открадне идеята от струни , чрез който ние по някакъв начин връзка между тези неща заедно концептуално, и какво ако го направя това? Това ми е много зле съставен стрелка. Но да предположим, че всеки един от тези блокове памет посочи към другия, и този човек, който няма братя и сестри от дясната му страна, няма такава стрелка. Това е всъщност това, което се нарича свързан списък. Това е нова структура на данните, която ни позволява да се разпределят парче от паметта, после още една, после още една, после още една, по всяко време искаме по време на програмата, и ние си спомняме, че всички те са свързани по някакъв начин като буквално верижното заедно, и ние сме го направили картинки тук със стрелка. Но в кода, какво ще бъде механизмът, чрез които бихте могли по някакъв начин да се свърже, почти като Scratch, едно парче на друг парче? Бихме могли да се използва показалка, нали? Защото наистина стрелката, която става от горния ляв квадрат, този човек тук това биха могли да съдържат в рамките на този площад не само някои цели числа, а не само някои Чар, но какво ще стане, ако аз действително разпределени малко допълнително пространство, така че сега, всеки от моите парчета памет, въпреки че това ще ми струва, сега изглежда малко по-правоъгълна, когато едно от парчета на паметта се използва за брой, като номер 1, и след това, ако този човек съхранява номер 2, това друго парче от паметта се използва за стрела, или по-конкретно, показалка. И предполагам, че се съхранява под номер 3 тук, докато аз използвам това да се посочи, че човек, и сега този човек, нека предположим, Искам само три такива блокове памет. Ще начертаете линия през това, което показва нула. Няма допълнителна характер. 

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

Точно както с низ, вие трябва да знаете адреса на първо Чар. Същата сделка за свързани списъци. Трябва да знаете адреса на първото парче на паметта , тъй като от там можете да достигнете до всяка друга. Недостатъкът. Каква цена плащаме за тази гъвкавост на динамично доста голям структурата на данните, че ако някога се нуждаят от повече памет, добре, просто разпределят още едно парче и да показалец от старата към новата опашката на списъка? Да. [Student] Това отнема около два пъти по-голямо пространство. Това отнема два пъти повече пространство, така че определено е недостатък, а ние сме виждали това компромис преди между времето и пространството и гъвкавост където до сега, ние не трябва 32 бита за всеки един от тези номера. Ние наистина се нуждаят от 64, 32 за брой и 32 за показалеца. Но, хей, имам 2 гигабайта RAM. Добавянето на още 32 бита, тук и тук не изглежда, че голяма сделка. Но за големи масиви от данни, то определено добавя буквално два пъти повече. Какво е друг недостатък сега, или каква функция да даваме, ако ние представляваме списъци на неща със свързан списък, а не масив? Студентски] не могат да преминават назад. Вие не можете да преминават назад, така че вие ​​сте вид прецакани, ако сте пеша от ляво на дясно с помощта на линия или цикъл, докато и после си даваш сметка, "О, аз искам да се върна към началото на списъка." Вие не можете, защото тези насоки само от ляво на дясно, като стрелките показват. 

Сега, вие може да си спомни началото на списъка с друга променлива, но това е сложността да се има предвид. Масив, без значение колко далеч да отидете, вие винаги може да направи минус, минус, минус, минус и да се върнете, откъдето сте дошли. Какво е друг недостатък тук? Да. [Чува студент въпрос] , Така че Вие може да сте всъщност предложи данните структура, наречена двойно свързан списък, и наистина, ще се добавят още показалеца на всеки един от тези правоъгълници , които отиват в друга посока, нагоре, от които сега можете да преминават напред и назад, Недостатъкът на които сега сте с помощта на три пъти повече памет, както сме свикнали да , а също и добавяне на сложност в условията на Кодекса, Вие трябва да напишете, за да го направим. Но всички те са може би много разумни компромиси, ако възстановяването е по-важно. Да. Студентски] също не може да има 2D свързан списък. Добре, че не може наистина да има 2D свързан списък. Би могъл. Това не е толкова лесно, колкото масив. Както масив, нали отворена скоба, затворена скоба, отворена скоба, затворена скоба, и ще получите около 2 триизмерна структура. Може да се приложи 2-измерна свързан списък ако го направите добавка, както ти предложи 1/3 показалеца на всяка от тези неща, и ако си мислиш за друг списък идват при вас 3D стил от екрана на всички нас, което е просто друга верига от някакъв вид. Можем да го направим, но това не е толкова просто, колкото да пишете отворена скоба, квадратна скоба. Да. [Чува студент въпрос] Добър, така че това е истински кикър. 

Тези алгоритми, които сме pined, като о, двоично търсене, масив от числа можете да търсите на борда или телефонния указател, така много по-бързо, ако използвате разделяй и владей и двоичен алгоритъм на търсене, но търсене двоичен изисква две предположения. Едно, че данните са подредени. Сега, ние можем да се предполага това подредени, така че може би това не е причина за безпокойство, но двоично търсене също така се приема че сте имали произволен достъп до списъка с номера, и масив ви позволява да имате случаен достъп, както и от случаен достъп, Искам да кажа, ако вие сте даден масив, колко време ви отнема да се получи да скоба 0? Една операция, можете просто да използвате [0] и вие сте точно там. Колко стъпки се предприемат, за да стигнем до място 10? Една стъпка, просто отидете [10] и сте там. За разлика от това, как се стигна до 10-о число в свързан списък? Трябва да започнем от самото начало, защото си спомняш само началото на свързан списък, просто като низ се помни от адреса на първата Чар, и да откриете, че 10 вътр или, че 10-ия знак в низ, трябва да се търси цялото проклето нещо. 

Отново, ние не сме решаването на всичките ни проблеми. Ние сме за въвеждане на нови такива, но това наистина зависи от това, което се опитваме да проектираме. По отношение на прилагането на настоящия, ние може да заеме една идея от този студент структура. Синтаксис е много близък, с изключение на сега, идеята е малко по-абстрактно от къщата и името и ID. Но аз предлагам да имаме структура от данни в C , който се нарича възел, тъй като последната дума на слайд показва, вътрешността на възел и възел е само родово контейнер в областта на компютърните науки. Това обикновено се съставя като кръг или квадрат или правоъгълник, както сме правили. И в този структурата на данните, ние имаме едно цяло число, N, така че това е номер, който искате да съхраните. Но какъв е този втори ред, структура възел * следващия? Защо това е правилно, или каква роля играе това нещо игра, въпреки че е малко загадъчен на пръв поглед? Да. [Чува студент отговор] Точно така, така * нещо от плячката, че е показалеца на някакъв вид. Името на този указател е произволно следващия, но бихме могли да го нарича всичко, което искаме, но какво прави този указател точка за? [Student друг възел. >> Точно, посочва друг такъв възел. 

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

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

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

Добре, добре. Добре, отлично, така че нека да задам няколко въпроса тук. И всъщност, какво е вашето име? >> Анита. Анита, добре, хайде тук. Анита ще ни помогне някак се реши сравнително прост въпрос в първата, което е как да разберете дали има или няма стойност е в списъка? Сега, забележете, че първо, представени тук от Лукас, е малко по-различно, и така си на парче хартия е умишлено странично , защото тя не е толкова висока и не взема колкото се може повече битове, въпреки че технически той има същия размер на хартията, просто се завърта. Но той е малко по-различна в това, че той е само на 32 бита за указател, и всички тези момчета са 64 бита, половината от която е номер, половината от които е указател. Но не е изобразен показалеца, така че ако вие може донякъде неловко използва лявата си ръка, за да посочи на човека до вас. А ти си номер 34. Как ти е името? Ари. Ари, така че всъщност, задръжте хартия в дясната си ръка, а лявата ръка отива право надолу. Вие декларирате нула на ляво. 

Сега нашата човешка картината е много последователен. Това е всъщност как указатели. И ако можете да смачквам малко по този начин, така че не съм във вашия начин. Анита тук, ме намерите номера 22, но поема ограничение не хората листчета, но това е списък, а имате само Лукас да започнем с защото той е буквално първият показалеца. Да предположим, че вие ​​самите сте показалеца, и така вие също имате възможността да се насоча към нещо. Защо не започнеш като посочи какво точно Лукас се посочи? Добър, и нека да приемат това тук. Само в името на дискусията, остави ме да извадя празна страница тук. Как се пише името ти? >> Анита. Добре, Анита. Да кажем, възел * Анита = Лукас. Е, ние не трябва да ти се обадя Лукас. Трябва да ти се обадя първо. Защо е това в действителност в съответствие с реалността тук? Едно, първата вече съществува. Първо е била разпределена вероятно някъде тук. Node * първо, и е бил предоставен списък по някакъв начин. Не знам как е станало това. Това се случи преди клас започва. Това свързан списък на хората е бил създаден. И сега, в този момент в историята - това е всичко, става Facebook очевидно по-късно в този момент в историята, Анита е инициализирана да бъде равна на първата, което не означава,, че Анита точки Лукас. Вместо това, тя посочва това, което той посочва защото един и същ адрес, който е в рамките на 32 бита Лукас - 1, 2, 3 сега също е в рамките на 32 бита на Анита - 1, 2, 3. 

Сега намерете 22. Как ще го направите? Какво е това? >> Point какъвто и да е. Посочете какъвто и да е, така че давай напред и да действа възможно най-добре тук. Добре, добре, а сега сте посочите какво е вашето име с 22? Рамон. >> Рамон, така че Рамон се държи 22. Вече сте направили проверка. Ли Рамон == 22, и ако е така, например, ние може да се върне вярно. Нека, докато тези момчета стоя тук донякъде неловко позволете ми да направя нещо бързо като булев намери. Отивам да вървим напред и да кажем (възел * списък, вътр N). Аз ще се върна с вас. Аз просто трябва да напишете някакъв код. И сега отивам да вървим напред и да направите това, възел * Анита = списък. И аз ще отида напред и да се каже, докато (Анита! = NULL). 

Метафората тук става малко опъната, но докато (Анита! = NULL), какво искам да направя? Аз трябва по някакъв начин на съотнасяне цяло число, че Анита е насочена. В миналото, когато имахме структури, които възел е, използва нотация точка, и бихме казали нещо подобно anita.n, но проблемът тук е, че Анита не е структура на себе си. Какво е тя? Тя е показалеца, така че наистина, ако искаме да използваме тази точкова нотация и това ще изглежда умишлено малко загадъчен ние трябва да направим нещо като отидете на лявата ръка на каквото и Анита сочи към и след това получи областта н. Анита е указател, но какво е * Анита? Какво ли, че когато отидеш на това, което Анита е насочена? Структура, един възел, и възел, изземване, има поле, наречено н , защото, спомняте, тези две области, в непосредствена близост и N, , които видяхме преди малко тук. 

За да имитират това в кода, можем да направим това и казват, че ако ((* Анита) N ==), N, че гледам. Забележете, че функцията е приет в брой, което ме интересува. Тогава да вървим напред и да направим нещо подобно връщане вярно. Иначе, ако това не е така, какво искам да направя? Как мога да преведат код Какво Анита толкова интуитивно, като се разхождах из списъка? Какво трябва да направя тук, за да симулира Анита да предприемем тази стъпка на ляво, тази стъпка на ляво? [Чува студент отговор] >> Какво е това? [Чува студент отговор] Добър, не е лоша идея, но в миналото, когато сме направили това, ние сме направили Анита + + защото това щяло да добавите номера от 1 до Анита, които обикновено точка на следващото лице, като Рамон или лицето, до него или до него лице за установяване на ред. Но това не е съвсем добре тук, защото какво означава това нещо, което изглежда в паметта? Не е това. Ние трябва да изключите. Той изглежда така в паметта, и въпреки че съм 1 и 2 и 3 близо една до друга, ако наистина симулира това може момчета, докато все още сочи едни и същи хора, може някои от вас да вземе случаен стъпка назад, някои от вас случаен крачка напред? 

Тази бъркотия е все още свързан списък, но тези момчета може да е навсякъде в паметта, така Анита + + не се ходи на работа, защо? Какъв е място Анита + +? Кой знае. Това е някаква друга стойност, която просто така се случва да се намеси сред всички тези възли по случайност, защото ние не сме масив. Разпределят на всеки един от тези възли поотделно. Добре, ако вие сами можете да почистите обратно. Позволете ми предложи вместо на Анита + +, вместо това Анита стане добре, защо не отидем какъвто и да е Анита е насочена и след това направете следваща? С други думи, ние се връщаме към Рамон, който е номер 22, и след това следващата е като че Анита ще бъдат копиране лявата си ръка показалеца. Но тя не искаше отидат по-далеч от Рамон, защото открихме 22. Но това би било идеята. Сега, това е бог ужасна бъркотия. Честно казано, никой няма да си спомня този синтаксис и толкова щастие, това е всъщност малко съзнателно-о, не всъщност да видим какво съм написал. Това ще бъде по-убедителен, ако можеш. Voila! 

Зад кулисите бях решаване на проблема по този начин. Анита, да предприемат тази стъпка на ляво, първо място, ние трябва да излизат на адреса, който Анита сочи към и където ще намерите не само N, който току-що проверих за сравнение, но вие също ще намери следващото - в този случай, Лявата ръка на Рамон сочи към следващия възел в списъка. Но това е бог-ужасната бъркотия, в която по-горе споменах, но се оказва, C ни позволява да се опрости тази процедура. Вместо да пишете (* Анита), може вместо това просто напишете Анита-> и това е точно същото нещо функционално, но това е много по-интуитивен, и това е много повече в съответствие с картината, която ние сме били изготвяне през цялото това време с помощта на стрелките. 

И накрая, какво трябва да се направи в края на тази програма? Има един ред код останалите. Връщане какво? False, защото ако ние се през цялата линия, докато и Анита, в действителност, е нула, това означава, че тя отиде по целия път до края на списъка където тя е била посочите какво е вашето име? Лявата Ари. >> Ари ръка, което е нищожна. Анита е нула, и разбирам, че сте просто стоя тук неловко в състояние на неопределеност защото аз отивам на монолог тук, но ние ще ви включва отново само за миг. Анита е нищожна в този момент в историята, така линия, докато се прекратява, и ние трябва да върнем невярно, защото ако тя има целия път до нулев указател на Ари тогава не е имало номер, който търсеше в списъка. Да почистите прекалено, но това е доста добро изпълнение на функция прекосява, функция за свързан списък. Тя все още е линейна търсене, но това не е толкова просто, колкото + + указател или + + променлива и защото сега не можем да се досетите , където всеки един от тези възли са в паметта. Ние трябва буквално да се проследи пътя на галета или по-точно, указатели, за да получите от един възел към друг. 

Сега нека се опитаме друг. Анита, искам да се върна тук? Защо не отидем напред и да предостави още един човек от публиката? Изчистване какво е вашето име? >> Ребека. Ребека. Ребека е malloced от публиката, и тя се съхранява на номер 55. А целта на ръка в момента е Анита да вмъкнете Ребека в свързан списък в съответното място. Хайде тук за момент. Съм правил нещо подобно. Съм направил възел *. И какво е вашето име? Rebecca. >> Ребека, добре. Ребека получава изчистване (sizeof (възел)). Точно както се разпределят като студенти и какво ли още не неща в миналото, ние се нуждаем от размера на възела, така че сега Ребека сочи в какво? Ребека има две полета вътре в нея, единият от които е 55. Нека да направим това, което Ребека> = 55. Но тогава Ребека-> следващия трябва да бъде както сега, нейната ръка е нещо кой знае? Това сочи някои боклук стойност, така че защо да не направим за добра мярка ние поне правим това, така че лявата ръка е в нея. Сега Анита, вземете я от тук. Имате Ребека които са били разпределени. Давай напред и да откриете къде трябва да сложим Ребека. Добре, много добре. Добре, хубаво, а сега ние трябва да предостави малко на посоката, така че сте достигнали Ари. Лявата му ръка е нулев, но Ребека ясно принадлежи към правото, така че как ние трябва да се промени този свързан списък за да вмъкнете Ребека в подходящо място? Ако може буквално да се движи наляво ръцете на хората наоколо, ако е необходимо, ще отстраните проблема по този начин. Добре, добре, а междувременно, лявата ръка Ребека сега е до нея. 

Това е твърде лесно. Нека се опитаме разпределяне сме почти готови, 20. Добре, хайде нагоре. 20 са разпределени, така че нека да вървим напред и да кажа отново тук ние току-що направихте възел * Саад. Имаме изчистване (sizeof (възел)). След това направете същото точния синтаксис, както направихме преди 20, и аз ще направя следващия = NULL, и сега той е до Анита да поставите в свързан списък, ако бихте могли да играят точно същата роля. Execute. Добре, добре. Сега помислете внимателно, преди да започнете да се движите левите си ръце около. Далеч най-неловко роля днес. Чиято ръка трябва да се премести първо? Добре, чакай, аз чувам някои не. Ако някои хора учтиво искали да помогнат за решаването неловка ситуация тук. Първия може би трябва да се актуализира, чиято лява ръка? Да. Студентски] Саад. Добре, Саад, защо, нали? [Чува студент отговор] Добре, защото ако се движим какво е вашето име? >> Маршал. Маршал, ако се движим ръката си пръв до нула, сега сме буквално сираци четирима души в този списък защото той е единственото нещо, което сочи на Рамон и всеки наляво, така актуализиране че показалеца първият беше лошо. Да отмените че. Хубаво, а сега вървим напред и да се премести подходяща лявата ръка посочи Рамон. Това се чувства малко излишно. Сега вече има двама души, сочещи към Рамон, но това е добре защото сега как по друг начин да актуализира списъка? Каква друга страна, трябва да се движат? Отлично, сега имаме загуби на паметта? Не, по-добре, нека да видим дали не можем да се разбие още веднъж. 

Mallocing за последен път, номер 5. Начина, по гърба, хайде надолу. Това е много вълнуващо. [Аплодисменти] Как ти е името? >> Рон. Рон, добре, ти се malloced като номер 5. Ние току-що се извършват код, който е почти идентичен с тези само с различно име. Отлично. Сега, Анита, късмет вмъкване на номер пет в списъка. Добър, и? Отличен, така че това наистина е трета от три общия брой случаи. За първи път има някой, който в края, Ребека. След това имаше някой в ​​средата. Сега имаме някой в ​​началото, и в този пример, ние сега трябваше да актуализира Лукас за първи път защото първият елемент в списъка сега трябва да посочи нов възел, , които, от своя страна, е насочена на възела номер 9. 

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

Нека погледнем на нещата в по-сложна посока все още. Ние вече имаме понятието за свързан списък. Ние също имаме благодарение на предложение има двойно свързан списък, който изглежда почти същата, но сега имаме две указатели в рамките на структурата на вместо един, и ние вероятно биха могли да наречем тези указатели предишен и следващ или наляво или надясно, но ние, всъщност, се нуждаят от две от тях. Кодът ще бъде малко по-сложен. Анита би трябвало да свърши повече работа тук, на сцената. Но ние със сигурност може да изпълнява този вид структура. По отношение на времето за работа, обаче, какво ще бъде времето за работа за Анита за намиране на редица N в свързан списък? Все още голяма O N, така че не е по-добре, отколкото линейно търсене. Не можем да направим двоично търсене, обаче, отново. Защо бе, че делото? Вие не можете да скачат. Въпреки, че очевидно всички хора на сцената, и Анита да го eyeballed и каза: "Ето средата на списъка" тя няма да знаят, че ако тя беше компютърна програма защото единственото, което тя трябваше да засуче в началото на сценария Лукас, който е първият показалеца. Тя непременно ще трябва да се следват тези връзки, преброяване по пътя си, докато намери около средата, и дори тогава тя не ще да знае кога е достигнал средата освен ако тя отива по целия път до края, за да разбера колко са, след това backtracks, което също би било трудно, ако не беше двойно свързан списък от някакъв вид. 

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

Сега, всички сценарии идват на ум, когато като комин структурата на данните, където имате този имот на последния, първи излязъл, всъщност е убедителна? Че нещо добро? Че нещо лошо? Това определено е нещо лошо, ако тава не са идентични и всички те са били специални различни цветове или какво ли не, и желания от вас цвят е чак в дъното. Разбира се, не може да се получи, че без много усилия. Вие трябва да започнете от върха и да си проправите път надолу. Също така, какво ще стане, ако вие бяхте един от тези фен момчета , който чака цяла нощ, опитвайки се да се сдобиете с iPhone и линии до на място като това? Не би ли било хубаво, ако в магазина Apple структура стека данни? Yay? Най? Това е само добро за хората, които се показват в последната възможна минута и след това се изуваше на опашката. И всъщност, факта, че съм бил толкова склонен да кажа на опашката всъщност е в съответствие с това, което бихме могли да наречем този вид на структурата на данните, в действителност, когато заповедта е от значение, и искате първата, за да бъде първият ако само в името на човешката справедливост. Ще се обадя, че опашката структура на данните. 

Оказва се, че освен свързани списъци, да започнете да използвате тези едни и същи идеи и започнете да създавате нови и различни видове решения на проблемите. Например, в случай на комин, бихме могли да представляват комин с помощта на структурата на данните по този начин, бих предложила. В този случай, съм обявен за структура, и аз съм казал в рамките на тази структура е масив от числа и след това променлива наречена размер, и аз отивам да се обадя това нещо комин. Сега, защо това действително работят? В случай на комин, може да се направи това ефективно на екрана като масив. Тук е моят стак. Това са моите номера. И ще ги привлече, тъй като това, това, това, това, това. И тогава някой друг член на данни, който се нарича размер, така че това е размер, и това е номера, и колективно, цялата IPAD тук представлява една купчина структура. Сега, по подразбиране, размер вероятно трябва да се инициализира с 0, и това, което е вътре на масив от числа първоначално , когато за пръв път разпределят масив? Garbage. Кой знае? И това всъщност не е от значение. Няма значение дали това е 1, 2, 3, 4, 5, напълно случайно от лош късмет, съхранявани в моята структура, защото доколкото аз знам, че размера на стека е 0, тогава знам, програмно, не изглежда във всеки един от елементите в масива. Няма значение какво е там. Не гледайте на тях, тъй като ще бъде отражение на размера на 0. 

Но да предположим, сега отивам напред и поставете нещо в стека. Искам да въведете номера 5, така че сложих номер 5 тук, и после какво мога да остави тук? Сега всъщност ще милион за размера, и сега стека е с размер 1. Какво ще стане, ако отида напред и да въведете номера, нека кажем, 7 следващия? След това се обновява на 2, а след това ние ще направим 9, и след това получава актуализирана до 3. Но интересна особеност на тази стека е, че Аз трябва да премахнете елемент, ако искам да се появи нещо на комина, така да се каже? 9 ще бъде първото нещо, което трябва да отида. Как трябва картината се промени, ако искам да се появи елемент на разстояние от стека, много прилича на тавата в Mather? Да. >> Студентски] Set размер на 2. Точно така, всичко, което правя, е определен размер на 2, и какво да правя с масива? Не е нужно да правите нищо. Можех, само за да бъде анален, сложи 0 или -1 или нещо, което да покаже, че това не е легитимен стойност, но това няма значение, защото Може да записва извън самия масив, колко е дълго така че аз знам само погледнете първите два елемента в този масив. Сега, ако отида и добавете номер 8 до този масив, как картината се промени след това? Това става 8, и това става 3. Аз съм рязане на няколко ъгли. Сега имаме 5, 7, 8, и ние сме обратно в размер на 3. Това е доста лесно да се осъществи, но когато отиваме да съжалявам за това дизайнерско решение? Когато нещата започват да отиде много, много грешно? Да. [Чува студент отговор] Когато искате да се върнете и да получите първи елемент, който инча 

Оказва се, че тук, макар и комин е масив под капака, тези структури от данни, които сме започнали да говорим за известна като абстрактни структури от данни, как те се изпълняват е напълно освен точка. Структурата на данните като комин е трябвало да добави поддръжка операции, като тласък, който настоява поднос върху стека, и поп, която премахва елемент от стека, и това е всичко. Ако ви се налага да свалите някой друг код, който вече се прилага това нещо, наречено комин, че човек би написал само две функции за вас, натиснете и поп, чиято единствена цел в живота би било да се направи точно това. Вие или него или нея, които изпълняват тази програма би било напълно да се реши как да се прилагат семантиката на бутане и мак под капака или функционалността на бутане и мак. И аз съм малко недалновидно решение тук чрез прилагане на стака ми с тази проста структура на данните, защо? Кога този структурата на данните почивка? В кой момент трябва да върне грешка, когато потребителят изисква натискане, например? [Student] Ако няма повече място. Точно така, ако няма повече пространство, ако съм надвишаването на капацитета, , което е с главни букви, защото предполага, че това е някакъв вид на глобалната константа. Е, тогава аз просто ще трябва да го кажа: "Съжалявам, не мога да прокара друга стойност върху стека, "много искал в Mather. 

В един момент, те ще продължават да се удари в горната част на този малък кабинет. Няма повече пространство или капацитет в стека, при което има някаква грешка. Те трябва да сложите елемента някъде другаде, тавата някъде другаде, или никъде. Сега, с опашка, бихме могли да го приложи малко по-различно. Опашката е малко по-различна в това, че под предния капак, може да се прилага като масив, но защо, в този случай, аз предлага да има елемент, представляващ глава начело на списъка, предната част на списъка, първият човек, на опашка в магазина на Apple, в допълнение към размера? Защо ми е необходим допълнителен част от данните тук? Помислете за какви номера ако съм съставянето му, както следва. Да предположим, че това сега е опашката вместо комин, разликата е точно като Apple магазин опашката е честно. Първият човек, на опашка в началото на списъка, номер 5 в този случай, той или тя ще бъде пуснат в магазина първо. Нека го направим. Да предположим, че това е състоянието на опашката ми в този момент във времето, и сега в магазина на Apple се отваря и се води от първо лице, номер 5, в магазина. Как мога да променя картината сега, че съм-опашка от първо лице в предната част на линията? Какво е това? >> Студентски] Промяна на опашката. Промяна на главата, така че 5 изчезва. В действителност, това е като че най-добрия начин да направите това? В действителност, това е като че ли този човек изчезва. Какво би номер 7 в реален магазин? Те ще направят голяма крачка напред. 

Но това, което сме дошли да оценят, когато става въпрос за масиви и движещи се неща наоколо? Това е вид на загуба на време, нали? Защо трябва да бъде толкова анален, за да има първо лице в началото на линията на физически началото на парчето на паметта? Това е напълно ненужно. Защо? Какво би могло Помня само, а? >> Чува студент отговор] Точно така, аз просто не забравяйте главата с този допълнителен член данни че сега начело на списъка вече не е 0, което беше преди малко. Сега е всъщност номер 1. По този начин, аз се леко оптимизация. Само защото съм де-опашка някой от ред в началото на линията на Apple магазин не означава, че всеки трябва да се смени, които изземване е линейна операция. Вместо това мога да прекарат константно време само и да се постигне много по-бърз отговор. Но цената си плащам, какво да получат тази допълнителна производителност и не се налага да се прехвърлят на всички? Да. >> Чува студент отговор] Може да добавите още хора, добре, че проблемът е ортогонална на факта, че ние не измества хората около. Тя все още е масив, така че дали трябва или не прехвърли всички или не О, разбирам какво искаш да кажеш, добре. Всъщност, съгласен съм с това, което казваш, че това е почти като че сега ние никога няма да използват вече началото на този масив защото ако премахна 5, след това премахна 7. Но аз само поставят хората в дясно. 

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

И в действителност, гледайки напред, един от psets в този клас е почти винаги за изпълнение на проверка на правописа, с което ние ви даваме отново около 150 000 английски думи и целта е да се зареди в паметта и бързо да бъде в състояние да отговори на въпросите на формуляра е тази дума написани правилно? И това наистина ще суче, ако сте имали, за да превъртите през всички 150 000 думи, за да се отговори на този. Но, в действителност, ще видим, че можем да го направим в много, много бърз време. И това ще включва изпълнението на нещо, наречено хеш таблица, и въпреки, че на пръв поглед това нещо, наречено хеш таблица ще нека постигане на тези супер бързи времена за реакция, се оказва, че действително има проблем. Когато дойде време за изпълнение на това нещо, наречено - отново, аз го правя отново. Аз съм само един тук. Когато дойде време за изпълнение на това нещо, наречено хеш таблица, ние ще трябва да вземе решение. Колко голям трябва това нещо всъщност? И когато започнем вмъкване на номера в тази хеш таблица, как ще да ги съхранява по такъв начин, , че можем да ги получите обратно толкова бързо, колкото ги има в? Но ще видим след дълго, че този въпрос когато настана рожденият ден на всички в класа ще бъде доста уместен. Оказва се, че в тази зала, имаме няколко души, така че шансовете, че двама от нас имат същия рожден ден е вероятно доста висока. Какво става, ако имаше само 40 от нас в тази стая? Какви са шансовете на двама души, които имат същия рожден ден? [Студенти] Над 50%. Да, над 50%. Всъщност, аз дори донесе диаграма. Оказва се, че и това е наистина само една закрита прожекция ако има само 58 от нас в тази зала, вероятността от две от нас със същия рожден ден е изключително високо, почти 100%, и че ще предизвика цял куп боли за нас в сряда. 

С това каза, нека да отложи тук. Ще се видим в сряда. [Аплодисменти] [CS50.TV]