[Powered by Google Translate] [Седмица 6 Продължава] [Дейвид Дж. Малан] [Харвардския университет] [Това е CS50. [CS50.TV] Това е CS50 и това е края на седмица 6. Така CS50x, един от първите курсове в Харвард, участващи в инициативата EDX наистина дебютира миналия понеделник. Ако искате да получите един поглед на това, което другите в Интернет сега след заедно с, можете да се отправите на x.cs50.net. Това ще ви пренасочи към съответното място на edx.org което е, когато този и други курсове от Масачузетския технологичен институт и Бъркли сега живеят. Ще трябва да се запишете за една сметка, ще откриете, че материалът е до голяма степен същото както сте имали този семестър, макар и забавени няколко седмици, като вземем всичко готово. Но това, което студентите в CS50x Сега ще видите, е интерфейс, доста подобна на тази. Това, например, е Zamyla водещ на репетиция за проблем набор 0. При влезете в edx.org, CS50x студентът вижда различни неща бихте очаквали да видите в курс: на лекция за понеделник, лекция за сряда, различни шорти, проблемът комплекти, сваляне, PDF файлове. Освен това, както виждате тук, машинен превод на английски транскрипция на китайски, японски, испански, италиански, и цял куп други езици, които със сигурност ще бъде несъвършен , тъй като ние ги оваляйте програмно чрез нещо, наречено API, или интерфейс за програмиране на приложения от Google , която ни позволява да конвертирате от английски на други езици. Но благодарение на прекрасния дух на някои сто плюс доброволци, случайни хора в Интернет, които са любезно предложи да се включат в този проект, ние постепенно ще се подобрява качеството на тези преводи , като хората коригират грешки, които нашите компютри са направили. 

Така се оказва, че сме имали още няколко студенти показват в понеделник, отколкото първоначално се очакваше. Всъщност, сега CS50x има 100 000 души, след заедно у дома. Така че осъзнаваш, че са част от встъпителната класа на този курс по компютърни науки образование като цяло, по-широко достъпен. А реалността е сега, с някои от тези масивни онлайн курсове, всички те започват с тези на много голям брой, както изглежда вече сме направили тук. Но целта, в крайна сметка, за CS50x е наистина да получите най-много хора до финалната линия, е възможно. По проект, CS50x ще се предлага от миналия понеделник по целия път до 15 април, 2013, така че хора, които имат училищни ангажименти другаде, работата, семейството, други конфликти и други подобни, имат малко по-голяма гъвкавост с които да се потопите в този курс, който, достатъчно е да се каже, е доста амбициозно стане само ако в течение на само три месеца по време на обичайния семестър. Но тези ученици ще бъдат решаването на същите проблеми, смятайки, че едно и също съдържание, като достъп до същите шорти и други подобни. Така че осъзнават, че всички ние сме наистина заедно в това. И една от крайните цели на CS50x не е само за да получите колкото се може повече хора до финалната линия и да им даде тази нова разбиране на компютърните науки и програмиране, но също така и да ги имат този споделен опит. Една от определящите характеристики на 50 на територията на колежа, ние се надяваме, е този вид на комуналната опит, за добро или за лошо, а понякога и но се налага тези хора да се обърнат към наляво и надясно, и офис часа и hackathon и справедливата. Това е малко трудно да се направи, че в лице с хора онлайн, но CS50x ще приключи през април с първата по рода си CS50 Експо , което ще бъде онлайн адаптиране на нашата идея на панаира когато тези хиляди студенти ще бъдат поканени да представят 1 - 2-минутно видео, или Screencast на последния им проект или видео от тях размахваше Здравейте и говори за проекта си и го demoing, много прилича вашите предшественици са направили тук на територията на колежа в справедливата така че до края на семестъра, надеждата е да има глобален изложба на крайните проекти CS50x студенти, много подобен на този, който ви очаква декември тази година на територията на колежа. Така повече, че в идните месеци. 

С 100 000 студенти, обаче, идва нужда от още няколко компетентни. Като се има предвид, че вие ​​пламнал пътека тук и като CS50 няколко седмици преди освобождаването на този материал хора в EDX, осъзнаваме, че ще се радва да се включат колкото се може повече от нашите собствени ученици е възможно в тази инициатива, както по време на семестъра, както и тази зима и идната пролет. Така че, ако бихте искали да се включат в CS50x, особено присъединяването на CS50x обсъждане, EDX версия на CS50 Обсъждане която мнозина от вас са били на територията на колежа, онлайн бюлетин борд, моля, направете главата към този адрес, нека да знаят кой сте вие, защото ще се радваме да се изгради екип от студенти и преподаватели, така и факултета на територията на колежа, които просто играят заедно и да помагат. И когато те виждат един въпрос, който е запознат с тях, чуете студент отчитане на някои бъг някъде там в някои страни в Интернет, и че звъни звънец, защото вие също имаше същият проблем в г-зала преди известно време, надявам се след това можете да се намеся в разговора и да споделят собствения си опит. Така че моля не участва, ако искате. 

Курсове по компютърни науки в Харвард са малко на една традиция, CS50 сред тях, като някои дрехи, някои дрехи, които можете да носите гордо в края на семестъра, като каза доста гордо, че сте готови CS50 и взе CS50 и други подобни, и ние винаги се опитваме да се включат студенти в този процес, доколкото е възможно, чрез което покани, по това време на семестъра, студентите да представят проекти използвате Photoshop, или каквото и средство на избор, който искате да използвате ако сте дизайнер, да представят проекти за тениски и суитчъри и чадъри, както и малки КЪРПИ за кучета, сега ние имаме и други подобни. И всичко е след това - победителите всяка година са изложени на сайта на курса store.cs50.net. Всичко се продава по себестойност там, но там само по себе си работи и позволява на хората да избират цветове и дизайн, които те харесват. Така си мислех, ние просто щяхме да споделя някои от дизайни на миналата година , които са били на уебсайта, освен това тук, което е ежегодна традиция. "Всеки ден съм Seg Faultn" е един от представените миналата година, която все още е на разположение за възпитаници. Имахме ", CS50, създадена 1989 година." Един от нашите Bowdens, Роб, беше много популярна през миналата година. "Team Боудън" е роден, този дизайн е представена, сред най-продаваните. Както и този тук. Bowden Fever "Много хора според продажбите трупи. Осъзнайте, че вече може да бъде вашия проект там, в интернет. Повече подробности по този въпрос в следващия проблем, да дойде. 

Още един инструмент, сте имали някои експозиция, и да се надяваме сега някои практически опит с GDB, , което е, разбира се, дебъгер и ви позволява да манипулирате програмата си на доста ниско ниво, без да прави какви неща? Какво GDB ви позволи да направите? Да? Дай ми нещо. [Student отговор, неразбираем] Добре. Стъпка на функциите си, така че не само трябва да въведете работи и имат програма за удар през своята цялост, извеждаща неща на стандартния изход. , По-скоро може да се намеси чрез нея линия по ред, или да пишете следващата ред по ред по ред или стъпка, за да се потопите в една функция, обикновено този, който пише. Какво друго GDB ви позволи да направите? Да? [Student отговор, неразбираем] Печат променливи. Така че, ако искате да направите малко интроспекция, в рамките на програмата си , без да се налага да прибягват до писмено ФОРМАТ отчети навсякъде, може просто да отпечатате променлива или да покаже променлива. Какво друго мога да правя с дебъгер като GDB? [Student отговор, неразбираем] Точно така. Можете да задавате точки на прекъсване, може да се каже изпълнение почивка основната функция или функция на Foo. Може да се каже изпълнение на прекъсване на линията 123. И гранични точки са наистина мощна техника защото, ако имате най-общ смисъл от това, къде ти е проблема вероятно е, не е нужно да губите време се повишават през цялост на програмата. Можете същество скочи точно там и след това да започнете да пишете - засилване през него със стъпка или следващата или подобни. Но улов с нещо като GDB е, че тя ви помага, човека, проблемите си и да намерят вашите грешки. Не е задължително да ги намерите толкова много за вас. 

Така че ние въведохме друга style50 ден, който е на кратко командния ред инструмент която се опитва да Stylize кода си малко по-чисто от вас, човек, би могло да се направи. Но това също е наистина просто естетически нещо. Но се оказва, че този друг инструмент наречен Valgrind, че е малко по-тайнствена да използвате. Неговата продукция е отвратително загадъчен на пръв поглед. Но това е чудесно полезно, особено сега, когато сме част от срока , където можете да започнете да използвате изчистване и динамично разпределение на паметта. Нещата могат да тръгнат много, много погрешно бързо. Защото, ако сте пропуснали да освободите памет, или сочените от някои NULL показалеца, или сочените от някои боклук показалеца, това, което обикновено е симптом, че резултатите? Seg вина. И да получите този основен файл на известен брой килобайта или мегабайта , която представлява състоянието на паметта на вашата програма, когато тя се разби, но вашата програма в крайна сметка Seg грешки, сегментация вина, което означава, че нещо лошо се е случило почти винаги са свързани на паметта, свързана с грешка, която сте направили някъде. Така Valgrind ви помага да намерите неща като това. Това е инструмент, който ви тече, като GDB, след като компилирате вашата програма, но вместо да стартирате програмата директно, вие поемате Valgrind и преминава към вашата програма, точно както правите с GDB. Сега, използването, за да получите най-добрия вид на продукцията, е малко дълго, така че точно там на върха на екрана ще видите Valgrind-V. "V" почти навсякъде означава многословно, когато използвате програми на Linux компютър. А това означава, плюе повече данни, отколкото може да по подразбиране. "- Течове = пълно." Това е просто, че проверка за всички възможни течове на памет, грешки, които може да са направили. Това също е обща парадигма с Linux програми. По принцип, ако имате аргумент на командния ред, че е "ключ", , които е трябвало да промените поведението на програмата, и това е една буква, е-V, но ако това е включено, само с дизайна на програмиста, е пълна дума или поредица от думи, аргумент на командния ред започва с - Това са само човешки конвенции, но ще ги видите все по-често. И най-накрая, "a.out" е произволно име за програмата в този конкретен пример. И тук е някои представител изход. 

Преди да погледнем какво може да означава, нека преминем към фрагмент от кода тук. И нека ми се премести от пътя, идва скоро, и нека да погледнем в memory.c, който е този кратък пример тук. Така че в тази програма, позволете ми да се фокусирам върху функциите и въпроси. Имаме функция основната, която призовава функция, е, и после какво се е пристъпя да направя, леко технически английски език? Какво е пристъпя да направя? Какво ще кажеш аз ще започне с линия 20, както и местоположението на звездата не е от значение, но аз просто ще бъдат съвместими тук с последната лекция. Какво е линия 20, за нас? От лявата страна. Ние ще го съборят допълнително. Int * X: какво правим? Добре. Това е обявяване на показалеца, а сега нека да бъдем още по-технически. Какво означава това, много конкретно, да декларира указател? Някой друг? Да? [Student отговор, неразбираем] Твърде далеч. Така че четете на дясната страна на знака за равенство. Нека се съсредоточим само отляво, само на Int * х. Това означава "обяви" показалка, но сега нека се гмуркат по-дълбоко към това определение. Какво значи това конкретно, технически кажеш? Да? [Student отговор, неразбираем] Добре. Да запишете един адрес в паметта. Добре. И нека вземем тази една стъпка напред, то е за обявяване на променлива, х, това е 32 бита. И аз знам, че е 32 бита, защото - Това не е, защото това е ПНА, защото това е един показалеца в този случай. Съвпадение, че това е една и съща с вътр, но факта, че е звезда означава, че това е указател и в уреда, с много компютри, но не всички, указатели са 32 бита. На по-модерен хардуер като най-новите Mac-ове, най-новите персонални компютри, може да имате 64-битови указатели, но в уреда, тези неща са 32 бита. Така че ние ще стандартизира за това. По-конкретно, историята продължава, както следва: Ние "обявяват" показалеца, какво означава това? Ние се подготвяме да съхранявате адрес от паметта. Какво означава това? Ние създаваме променлива, наречена X, който заема 32 бита , които скоро ще се съхранява адреса на цяло число. И това е може би почти толкова точно, колкото можем да получим. Това е добре, движи напред, за да се опрости света и просто да кажа обяви показалеца нарича х. Обяви показалеца, но осъзнаят и да разберат какво всъщност се случва дори и само тези няколко знака. 

Сега, това е почти една малко по-лесно, въпреки че това е по-дълъг израз. И така, какво е това прави, че сега се откроява: "изчистване (10 * sizeof (INT));" Да? [Student отговор, неразбираем] Добре. И аз ще го отведе там. Разпределяне на парче на паметта в продължение на десет числа. А сега нека се потопите в малко по-дълбоко, то е за разпределяне на парче на паметта в продължение на десет цели числа. Какво е изчистване след това се връщат? Адрес на това парче, или, по-конкретно, на адреса на първия байт на това парче. Как тогава съм аз, програмист, за да знам къде е това парче на паметта краищата? Знам, че това е в съседство. Изчистване, по дефиниция, ще ви дам свързано парче от паметта. Без пропуски в него. Вие имате достъп до всеки байт в това парче, обратно към гръб до гръб, но как мога да знам къде е края на това парче на паметта? Когато използвате изчистване? [Student отговор, неразбираем] Добре. Не. Трябва да се помни. Трябва да се помни, че използва стойност 10, а аз дори не изглежда да са направили, че тук. Но тежестта е изцяло върху мен. Strlen, за които сме слабо зависима от струни, работи само, защото на тази конвенция на \ 0 или този специален нулев характер, NUL, в края на низ. Това не важи само за произволни блокове памет. Това е до вас. Така линия 20, а след това разпределя парче на паметта който може да съхранява десет числа, и го съхранява адреса на първия байт на това парче на паметта в променлива наречена х. Ergo, който е указател. Така линия 21, за съжаление, е било грешка. Но първо, какво е да го прави? Той казва магазин на място при 10, индексирани от 0, на парче памет, наречена X стойност 0. 

Така че забележите няколко неща ще. Въпреки че х е указател, припомнят от преди няколко седмици че все още можете да използвате масив стил нотация скоба площад. Защото това е всъщност ръка нотация за по-загадъчен изглеждащи показалеца аритметика. , където ние ще направим нещо като това: х адрес, преместване 10 места, след това да има какъвто и да е адрес се съхранява на това място. Но честно казано, това е просто отвратителен, да четат и да получите комфортно. Така светът обикновено използва квадратните скоби, само защото тя е много повече за човека да се чете. Но това е, което наистина се случва под предния капак; х е адрес, а не масив, сам по себе си. Така че това е съхраняване 0 на място при 10 в х. Защо това е лошо? Да? [Student отговор, неразбираем] Точно така. Ние само разпределят десет цели числа, но ние броим от 0 при програмирането на С, така че да имате достъп до 0 1 2 3 4 5 6 7 8 9, но не и 10. Така че или програмата ще сегмента вина или не е така. Но ние не наистина знаят; това е нещо на nondeterministic поведение. Това наистина зависи от това дали имаме късмет. Ако се окаже, че операционната система няма нищо против, ако използвам тази екстра байт, макар и да не го даде на мен, моята програма не може да се срине. Това е сурова, това е бъги, но може да не се види, че симптом, или може да го види само веднъж в последно време. Но реалността е, че грешката не е в действителност, има. И това е наистина проблем, ако сте написали програма, която искате да бъде вярна, , че сте продали на програмата, която хората използват, че всеки от време на време се срива защото, разбира се, това не е добре. В действителност, ако имате телефон с Android или iPhone и да изтеглите приложения тези дни, ако някога сте имали един апартамент, просто напуснете, изведнъж изчезва, това е почти винаги в резултат на някои въпроси, свързани с паметта, като програмист прецаках и dereferenced указател , че той или тя не трябва да има, и в резултат на IOS или Android е просто да убие изцяло програмата отколкото риск неопределено поведение или някакъв вид компромис за сигурност. 

Има една друга грешка в тази програма освен тази. Какво друго се издъних в тази програма? Аз не съм се практикува това, което съм проповядвал. Да? [Student отговор, неразбираем] Добре. Не съм освободен паметта. Така правилото сега трябва да бъде по всяко време ти се обадя изчистване, трябва да се обаждате безплатно, когато сте готови с тази памет. Сега, когато бих искал да се освободи тази памет? Вероятно, ако приемем, че тази първа линия е правилно, аз бих искал да го правя тук. Защото не можех, например, да го направя тук. Защо? Просто извън обхвата. Така че дори и ние не говорим за указатели, Това е една седмица два или три въпроса, където х е само в обхвата вътрешността на фигурни скоби, когато е декларирана. Така че определено не може да го освободи. Единственият ми шанс да го освободи е приблизително след линия 21. Това е доста проста програма, тя е доста лесно, след като вид увит ума си около това, което програмата прави, когато грешките са. А дори и да не го видим в първия, се надяваме, че е малко очевидно сега , че тези грешки са доста лесно се решава и лесно. Но когато програмата е повече от 12 реда, 50 линии, 100 линии, разхождах из вашия код линия по ред, мислейки, то логично, е възможно, но не е особено забавно да се направи, непрекъснато търси за грешки, и тя също е трудно да се направи, и това е защо съществува като инструмент Valgrind. Позволете ми да отида напред и да направите това: нека си отворя терминален прозорец, и нека не просто стартирате памет, защото паметта изглежда да се оправи. Аз съм късметлия. Отивате на този допълнителен байт в края на масива не изглежда да е твърде проблематично. Но нека, все пак, направи проверка на здрав разум, което просто означава, че за да се провери дали това всъщност е правилно. 

Така че нека да направим valgrind-V - изтичане на проверка = пълно, и след това името на програмата в този случай е паметта не a.out. Така че нека да вървим напред и да направите това. Хит Enter. Мили Боже. Това е изход, и това е, което споменах по-рано. Но, ако се научите да прочетете всички глупости тук, голямата част от това е просто диагностичен изход, който не е толкова интересен. Какво си око наистина иска да се търси, е всяко споменаване на грешка или невалиден. Думи, които предполагат проблеми. И наистина, нека да видим какво не е наред тук. Имам резюме от някакъв вид ", в употреба на излизане: 40 байта в 1 блокове" Аз наистина не съм сигурен какво блок все още, но 40 байта всъщност се чувства, че мога да разбера, когато това идва от. 40 байта. Защо 40 байта, които се използват при излизане? И по-специално, ако ние превъртете надолу, защо съм загубил окончателно 40 байта? Да? [Student отговор, неразбираем] Perfect. Да, точно така. Имаше десет числа, и всеки от тях е размер на 4, или 32 бита, така че съм загубил точно 40 байта, защото, както предложи, не са наречени свободни. Това е един бъг, а сега нека разгледаме малко по-нататък и да видим до това, "Невалиден пиша с размер 4". Сега какво е това? Този адрес се изразява каква база нотация, очевидно? Това е в шестнадесетичен вид, и всеки път, когато видите номер, започващ с 0x, това означава, шестнадесетичен, което ние направихме, мисля, раздел pset 0 от въпроси, което е просто да се направи упражнение за загрявка, Конвертиране на десетични шестнадесетичен двоичен и така нататък. Шестнадесетичен само от човешката конвенция, обикновено се използва за представяне на указатели или, по-общо, се занимава. Това е просто една конвенция, , защото това е малко по-лесно да се чете, това е малко по-компактен от нещо като знак след десетичната и бинарни е безполезен за повечето хора, които да се използват. Така че сега, какво означава това? Е, изглежда, че има невалиден запис на размер 4 по линия 21 на memory.c. Така че нека да се върнем към 21, и наистина, тук е, че невалиден запис. Така Valgrind няма да напълно да държи ръката ми и ми кажи какво е поправката, но това е откриване, че правя невалиден запис. Аз докосвате 4 байта, че не трябва да бъде, и очевидно това е така, защото, като посочи, правя [10] вместо [9] максимално или [0], или нещо по средата. С Valgrind, реализира всеки път, когато сте написването на програмата който използва указатели и използва памет и изчистване по-специално, определено ще получите в навик да работи толкова дълго , но много лесно се копира и командването на Valgrind да видим дали има някои грешки в там. И това ще бъде непоносимо всеки път, когато виждаш изхода, но просто разбор чрез визуално цялото производство и да видим, ако видите споменава на грешки или предупреждения или невалидна или изгубени. Която и да е от думите, които звучат като теб винтови някъде. Така че осъзнават, че е нов инструмент във вашата инструментариум. 

Сега в понеделник, имахме цял куп хора идват тук и представляват идеята на свързан списък. И ние въведохме свързан списък, като решение за какъв проблем? Да? [Student отговор, неразбираем] Добре. Масивите не могат да имат памет, добавени към тях. Ако разпределят масив с размер 10, това е всичко, което се. Можете да се обадите функция като презаделяне ако първоначално наречена изчистване, и които могат да се опитват да растат масива, ако има място към края на че никой друг не се използва, и ако няма, просто ще ви намери по-голямо парче някъде другаде. Но тогава ще го копира всички тези байта в нов масив. Това звучи като много правилно решение. Защо това е непривлекателна? Искам да кажа, че работи, хората са решили този проблем. Защо ние трябва да го решим в понеделник със свързани списъци? Да? [Отговор Student, неразбираем] може да отнеме дълго време. В действителност, всеки път, когато се обаждате изчистване или презаделяне или calloc, което е още една, всеки път, когато програмата се говори за операционната система, сте склонни да се забави програмата. И ако правиш тези неща в цикли, сте наистина забавят нещата. Ти няма да забележи този за най-простите на "Hello World" програми от типа, но в много по-големи програми, задаване на операционната система отново и отново за паметта или да го върнат отново и отново не е склонна да бъде нещо добро. Плюс това, тя е просто вид интелектуално - това е пълна загуба на време. Защо да отделят все повече и повече памет, всичко за копиране на риска в нов масив, ако имате алтернатива, която ви позволява да разпределят само толкова памет, колкото действително се нуждаят? Така че има плюсове и минуси тук. Един от плюсовете е, че имаме динамика. Не значение къде парчета на паметта, които са свободни, Мога само да сортирате за създаването на тези галета чрез указатели низ цялото ми свързан списък. Но аз плащат най-малко една цена. 

Какво трябва да се даде при получаването на свързани списъци? Да? [Student отговор, неразбираем] Добре. Имате нужда от повече памет. Сега имам нужда от пространство за тези насоки, и в случай на този супер прост свързан списък че само се опитва да съхранява числа, които са 4 байта, продължават да твърдят, добре, показалеца е 4 байта, така че сега съм буквално се удвои размера на паметта, трябва само да се съхранява този списък. Но отново, това е постоянен компромис по компютърни науки между времето и пространството и развитие, усилия и други ресурси. Какво е друг недостатък на използването на свързан списък? Да? [Student отговор, неразбираем] Добре. Не е толкова лесно за достъп. Вече не можем да ливъридж седмица 0 принципи като разделяй и владей. И по-конкретно, двоично търсене. Защото, въпреки че ние, хората, могат да видят около средата на този списък е, компютъра само се знае, че този свързан списък започва на адрес нарича първата. И това е 0x123 или нещо подобно. И единственият начин програмата може да намери средата елемент е действително да търсим в целия списък. И дори тогава, той буквално трябва да търсим в целия списък, защото дори и след като достигне средата елемент след указатели, , програмата, нямате представа колко е дълъг този списък е, потенциално докато не удари края на това, и как знаеш програмно че сте в края на свързан списък? Има специален NULL показалеца, така че отново конвенция. Вместо да използвате този указател, ние определено не искам тя да бъде някаква стойност боклук сочи етап някъде, ние искаме тя да бъде страна, NULL, , така че ние имаме това крайната точка в този структурата на данните, така че ние знаем къде свършва. 

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

Нека вървим напред и да се отворят някои например код. Ще отворя Gedit и нека се отворят два файла първото. Един от тях е list1.h, и нека само да напомня, че това е парче код че сме свикнали да представлява възел. Възел има както едно цяло число, наречено н и указател следва, че само точки към следващото нещо в списъка. Това вече е в файл з. Защо? Тази конвенция, и не сме се възползвали от тази огромна себе си сума, но човек, който пише ФОРМАТ и други функции даде като дар за света на тези функции чрез написването на файл, наречен stdio.h. И тогава там е string.h, и след това има map.h, и има всички тези ч файлове , че може да са видели или използвани по време на срока, написани от други хора. Обикновено в тези з файлове са единствените неща, като typedefs или декларации на потребителски типове или декларации на константи. Не слагайте реализации функции в заглавните файлове. , Вместо, само прототипи. Неща, които искате да споделите със света, това, което те имат нужда За да компилирате кода си. Така че просто трябва да влязат в този навик, ние решихме да направим едно и също нещо. Там не е много в list1.h, но ние сме поставени нещо, което може да представлява интерес за хората в света които искат да използват нашата свързан изпълнението списък. Сега в list1.c, аз няма да мине през цялото това нещо защото това е малко дълго, тази програма, но нека го изпълним реална бързо в командния ред. Нека ми съставят list1, нека след това пуснете list1, и това, което ще видите е сме симулирани просто малка програма тук че няма да ми позволи да добавяте и премахвате номера на списък. Така че нека да вървим напред и Тип 3 за 3 опция от менюто. Искам да въведете номера - нека да направим първото число, което е 9, и сега съм казал списъка сега е 9. Нека вървим напред и да направя друг вмъкване, така че удари опция от менюто 3. Какъв брой искам да вмъкнете? 17. Enter. И аз ще направя само още един. Позволете ми да въведете номера 22. Така че ние имаме начало на свързан списък, който имахме в слайд форма преди малко. Как става това вмъкване всъщност се случва? В действителност, 22 вече е в края на списъка. Така че историята, която разказа на сцената в понеделник и обобщи точно сега трябва действително да се случва в кода. Нека да разгледаме. Нека превъртете надолу в този файл. Ние ще замазват някои от функциите, но ние ще отидем да се каже, добавя функцията. 

Нека видим как можем отида за поставяне на нов възел в тази свързан списък. Когато се обявява списъка? Ами, нека да превъртите целия път до върха, и забележите, че ми свързан списък по същество е обявен като един указател, който първоначално е NULL. Така че аз съм с глобална променлива, която в общи линии сме проповядвал срещу защото го прави кода си малко разхвърлян да се поддържа, това е вид мързеливи, обикновено, но това не е мързелив и не е наред и не е зле ако единствената цел на програмата в живота е да се симулира един свързан списък. Което е точно това, което правим. Така че вместо да декларира това в основни и след това трябва да го предаде на всяка функция съм писал в тази програма, вместо да осъзнае, о, нека просто да я направите глобална защото целта на тази програма е да се демонстрира един и само един свързан списък. Така, че се чувства добре. Тук са моите прототипи, и ние няма да мине през всички тези, но аз написах функцията за изтриване, функция за търсене, добавя функция, както и функция, траверса. Но нека сега се връщаме надолу Вмъкване на функция и да видим как това работи тук. Вмъкни е на линия - да го направим. Поставете. Така че не предприемат никакви аргументи, защото отиваме да попитам потребителя вътрешността на тази функция за броя искат да вмъкнете. Но първо, ние подготвяме да им даде някои пространство. Това е нещо като копиране и поставяне от друг пример. В този случай, ние разпределяне на вътр, този път сме разпределяне на възел. Аз наистина не помня колко байта възел, но това е добре. Sizeof мога да разбера, че за мен. И защо съм проверка за NULL в линия 120? Какво може да се обърка в съответствие 119? Да? [Student отговор, неразбираем] Добре. Просто може да е случаят, че съм поискал прекалено много памет или нещо не е наред и операционната система не разполага с достатъчно байта да ми даде, така че сигнали, тъй като много от връщане NULL, и ако не се прави проверка за това и аз просто сляпо продължи да използвате адреса върна, тя може да бъде NULL. Тя може да бъде някаква неизвестна стойност, не е нещо добро, освен ако I - всъщност няма да е неизвестна стойност. Тя може да бъде NULL, така че аз не искам да злоупотребяват с нея и рискуват dereferencing. Ако това се случи, аз просто се върне и ние ще се преструвам, като аз не се върна на паметта на всички. 

В противен случай, аз съобщите на потребителя, да ми даде номер, за да вмъкнете, аз ви призовавам нашия стар приятел GetInt, и след това е новия синтаксис ние въведохме в понеделник. "Newptr-> N" означава адреса, който бяха дадени от изчистване която представлява първия байт на нов обект възел, и след това да отиде на полето, наречено н. Малко любопитни факти въпрос: Това е еквивалентно на това, което по-загадъчен линия на код? Как иначе може да съм написал това? Искате ли да хладно оръжие? [Student отговор, неразбираем] Добре. Използване на N, но това не е толкова проста, тъй като това. Какво първо трябва да направя? [Student отговор, неразбираем] Добре. Имам нужда от да направя * newptr.n. Така че това е, че новата показалеца очевидно адрес. Защо? Тъй като това бе върнат от изчистване. * Newptr каза: "отидем там" а след това веднъж сте там, а след това можете да използвате по-познато. н, но това просто изглежда малко грозно, особено ако ние, хората, ще изготвя указатели със стрелки през цялото време, в света има стандартизирани в тази стрелка нотация, което прави точно същото нещо. Така че можете да използвате само -> нотация, когато нещо в ляво е показалеца. В противен случай, ако това е действително структура. Н. И после това: Защо се инициализира newptr-> следващия NULL? Ние не искаме висящи лявата ръка разстояние от края на сцената. Ние искаме да го сочи право надолу, което означава края на този списък би могло да бъде в този възел, така че по-добре да се уверите, че е NULL. И като цяло, инициализиране на променливи или членове на вашите данни и structs нещо е просто добра практика. Просто отдаване под наем боклук съществуват и продължават да съществуват като цяло попадне в беда ако сте пропуснали да направим нещо по-късно. 

Ето няколко случая. Това отново е Вмъкване на функция, и първото нещо, което проверява за е, ако променлива наречена първата, , че глобалната променлива е NULL, това означава, че там не е свързан списък. Не сме написали номера, така че това е тривиално да поставите този номер в списъка, защото тя просто принадлежи в началото на списъка. Така че това беше, когато Анита е просто стои тук сам, преструвайки се, че никой друг не е тук на сцената, докато не разпределят възел, тогава тя може да вдигне ръка, за първи път, ако всички останали излезе на сцената след нея в понеделник. Сега тук, това е малко по проверка, където аз трябва да кажа, ако стойността на нов възел на н <стойността на N в първия възел, това означава, че е свързан списък, който е започнал. Има най-малко един възел в списъка, но този нов човек принадлежи преди това, така че ние трябва да се движат нещата около. С други думи, ако списъкът е започнал само с, да речем, само номер 17, това е - всъщност, ние можем да направим това по-ясно. Ако започнем нашата история с показалеца нарича първият, и първоначално е NULL, и въведете номера 9, номер 9 ясно принадлежи в началото на списъка. Така че нека се престорим, че ние просто malloced адреса или номера 9 и го сложи тук. Ако първото е 9 по подразбиране, първият сценарий, ние обсъдихме тук просто означава, точка нека този човек, оставите това NULL, сега имаме номер 9. Следващият брой искаме да вмъкнем е 17. 17 принадлежи тук, така че ние ще трябва да се направят някои логично засилване през това. Така че нека вместо това, преди да направим това, нека се престорим, че искаме да въведете номера 8. 

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

Така че нека да се направи още едно нещо, а аз трябваше да остави малко повече място за това. Така че прости малка рисунка. Този човек се нарича newptr. Това е променлива, ние декларирахме няколко реда по-рано, в съответствие - малко над 25. И сочи към 8. Така че, когато казвам newptr-> следващия, това означава, че отидете на структурата , което е насочено към от newptr, така че ние сме тук, отидете там. Тогава стрелката казва получите следващото поле, и след това = казва сложи каква стойност има? Стойност, която е в първо каква стойност е в първи? Първо сочеше този възел, така че това означава, че сега трябва да се насочи към този възел. С други думи, това, което изглежда макар и нелепо каша с моя почерк, какво е проста идея просто се движат тези стрелки около превежда код само с този лайнер. Съхранява това, което е на първо място в следващото поле и след това да се актуализира какво всъщност е първа. Нека вървим напред и бързо напред чрез някои от това, и гледам само в тази опашка на вмъкване за сега. Да предположим, че стигнем до точката, в която аз намирам, че следващото поле на някои възел е NULL. И в този момент в историята, една подробност, че аз съм специфичността е, че въведохме друг показалеца тук в линия 142, предшественик на показалеца. По същество, в този момент в историята, след като в списъка получава дълго, Някак си трябва да го извърви с два пръста, защото ако отида твърде далеч, помня в една единствена дължина, не можете да се върнете назад. Така че тази идея на predptr е лявата ми пръст, и newptr - не newptr. Друго основание е, че е тук е другият ми пръст, а аз съм просто вид на ходене на списъка. Ето защо, който съществува. Но нека разглеждаме само един от по-простите случаи тук. Ако е NULL, че следващото поле на показалеца, това, което е логично отражение? Ако се пресичат този списък и да ви удари с нулев указател? Ти си в края на списъка, така че код, за да добавите това един допълнителен елемент е нещо от интуитивен ще вземе този възел, чието следващия показалецът е NULL, така че това в момента е NULL, и да я промените, макар и да е адресът на новия възел. Така че ние просто привличане на код върху стрелката, която направихме на сцената чрез повишаване на лявата ръка на някого. 

И случай, че аз ще размахва ръцете ми за сега, просто защото мисля, че е лесно да се загубиш, когато ние го правим в този вид на околната среда, проверка за вмъкване в средата на списъка. Но просто интуитивно, какво трябва да се случи, ако искате да разберете когато известен брой принадлежи в средата е, че е нужно да се разхождате с повече от един пръст, повече от една показалка, разбера къде принадлежи чрез проверка е елемент <настоящата, > Една страна, и след като се намери това място, тогава ще трябва да направи този вид на черупката игра, когато се движите указатели около много внимателно. И този отговор, ако искате да причина през това у дома на собствения си, свежда само до тези два реда код, но от порядъка на тези линии е супер важно. Защото, ако пуснете ръката на някого и да се повиши някой друг е в грешен ред, отново, може да се окажете orphaning списъка. За да обобщим по-концептуално, вмъкване в опашката е сравнително лесно. Вмъкване в главата също е относително ясно, но трябва да се актуализират допълнително показалеца този път да изтръгне номер пет в списъка, и след това поставяне в средата включва още повече усилия, много внимателно поставете номер 20 на правилното му място, , която е между 17 и 22. Така че ще трябва да направя нещо подобно има нов възел 20, точка 22, и след това, показалецът които възел трябва да бъде актуализиран за последен път? Тя е на 17, за да я поставете. Така че отново, аз ще отложи действителният код за това конкретно изпълнение. 

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

В действителност, да предположим, че сме направили оставим настрана свързан списък за миг и ние вместо да въведе понятието за маса. И нека просто мисля, че на масата за миг като масив. Този масив и този случай тук има около 26 елемента, от 0 до 25, и предполагам, че ви е необходимо някакво парче за съхранение на имена: Алис и Боб и Чарли и подобни. И трябва някои данни структура за съхранение на тези имена. Е, можете да използвате нещо като свързан списък и може да ходи списъка вмъкване на Алис пред Боб и Чарли след Боб и така нататък. И в действителност, ако искате да видите код, като това настрана, знаете, че в list2.h, ние правим точно това. Ние няма да мине през този код, но това е вариант на първия пример , която въвежда една друга структура, сме виждали преди нар. студентски, и след това какво всъщност се съхранява в свързан списък е указател към структура студент а не просто малко цяло число, бр. Така разбирам, че е код, който включва действителните струни, но ако целта на ръка наистина сега е за решаване на проблема за ефективност, не би ли било хубаво, ако сме обект наречен Алис, искаме да я постави на мястото му в структурата на данните, тя се чувства като тя ще бъде наистина хубаво да съм сложил Алис, , чието име започва с А, в първото място. И Боб, чието име започва с Б, във второто място. С масив, или да започнете да го наричаш маса, хеш таблица в това, можем да направим точно това. Ако ни е дадено име като Алис, низ като Алиса, където се слага A-л-и-в-е? Имаме нужда от hueristic. Имаме нужда от функция да отнеме известно входа като Алиса и да се върне отговор "Поставете Алис на това място." И тази функция, тази черна кутия, ще се нарича хеш функция. 

А хеш функция е нещо, което се вход, като "Алиса", и се връща към вас, обикновено цифровата място в структурата някои данни, когато Алис принадлежи. В този случай, нашата хеш функция трябва да бъде сравнително проста. Нашата хеш функция трябва да кажа, че ако ви се предоставя "Алиса", чийто характер трябва да се грижи за? Първия. Така че гледам [0], и тогава аз бих казал, ако [0] герой е, върнете номер 0. Ако това е Б, върнете 1. Ако това е C, върнете два, и така нататък. Всички 0 индекс, и това ще ми позволи да вмъкнете Алис и след това Боб и след това Чарли и т.н. в тази структура на данните. Но има един проблем. Какво ще стане, ако Анита идва заедно отново? Къде да вложим Анита? Нейното име също започва с буквата А, и тя се чувства като ние сме направили още по-голяма бъркотия на този проблем. Сега имат незабавен вмъкване, постоянно вмъкване в структурата на данните отколкото по-лош случай линейни, но какво можем да направим с Анита в този случай? Какви са двата варианта, наистина ли? Да? [Student отговор, неразбираем Добре, така че бихме могли да имат друго измерение. Това е добре. Така че ние можем да изградим нещата в 3D, като говорихме за устно в понеделник. Бихме могли да добавите друг достъп тук, но предполагам, че не, аз се опитвам да се запази тази проста. Целта тук е да има непосредствена постоянна време достъп, така че добавянето на твърде много сложност. Какви са другите варианти, когато се опитват да вмъкнете Анита в тази структура на данните? Да? [Student отговор, неразбираем] Добре. Така че ние може да се движи всеки друг, като Чарли побутвания надолу Боб и Алис, и след това ще се постави Анита, когато тя наистина иска да бъде. 

Разбира се, сега, има един страничен ефект от това. Структурата на тези данни вероятно е полезна не защото искаме да вмъкнем хора веднъж , а защото искаме да се провери дали те са там по-късно ако искаме да изкарваме всички имена в структурата на данните. Отиваме да направим нещо с тези данни в крайна сметка. Така че сега ние сме вид прецака Алис, който вече не е, където тя е трябвало да бъде. Не е Боб, нито е Чарли. Така че може би това не е толкова добра идея. Но наистина, това е една опция. Ние може да прехвърли всички, или дяволите, Анита дойде късно в играта, защо не можем просто да Anita не е тук, а не тук, а не тук, нека просто я малко по-ниско в списъка. Но тогава този проблем започва да се прехвърлят отново. Може да бъде в състояние да намери Алис незабавно, въз основа на първото си име. И Боб незабавно, и Чарли. Но след това търсят Анита, и ще видите, хм, Алис е на пътя. Ами, нека да ме проверите по-долу Алис. Боб не е Анита. Чарли не е Анита. О, има Анита. И ако продължи този влак на логиката по целия път, това, което е най-лошия случай времето за работа на намирането или поставяне на Анита в тази нова структура на данните? Това е O (N), нали? Защото в най-лошия случай, е Алис, Боб, Чарли. . . по целия път до някой на име "Y", така че има само едно място наляво. За щастие, имаме не една, наречена "Z", така че ние Анита на самото дъно. 

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

Може би ще получите късмет и ние няма да имат две или две Б с много висока степен на вероятност, но както някой посочи, ако ние генерализирана този проблем и не 0-25 но, да речем, от 0 до 364 или 65, по-често броя на дните в една типична година, и зададе въпроса: "Каква е вероятността, че двама от нас в тази зала имат същия рожден ден?" Казано по друг начин, каква е вероятността, че двама от нас имат име започва с А? Въпросният вид е същата, но това адресно пространство, пространство, това търсене е по-голям в случай на рождени дни, защото имаме толкова много повече дни в годината, отколкото буквите в азбуката. Каква е вероятността от сблъсък? Е, можем да мислим за това, като разберете по математика по обратния начин. Каква е вероятността не сблъсъци? Е, този израз тук казва, че това е вероятността ако има само един човек в тази зала, че те имат уникален рожден ден? Това е 100%. Защото, ако има само един човек в стаята, неговия или нейния рожден ден може да бъде някоя от 365-те дни на годината. Така че 365/365 опции ми дава стойност на 1. Така че вероятността въпрос в момента е само един. Но ако има втори човек в стаята, каква е вероятността, че си рожден ден е различен? Има само 364 възможни дни, игнорирайки високосна година, за рождения си ден да не се сблъскат с други лица. Така че 364/365. Ако трето лице, е 363/365, и така нататък. Така че ние продължаваме умножаване на тези фракции, които са все по-малки и по-малки, да разбера каква е вероятността, че всички ние имаме уникални рождени дни? Но тогава можем да, разбира се, просто приемете този отговор и го обърнете наоколо и 1 минус всичко това, израз в крайна сметка ще се ако си спомняте, на гърба на математически книги, изглежда малко нещо като това, , което е много по-лесно тълкува графично. И този графичен тук има по оста х броя на рождени дни, или броят на хората с рождени дни, както и на оста Y е вероятността по време на мач. И това, което казва, е, че, ако имате, да речем, дори, да изберете нещо като 22, 23. Ако има 22 или 23 души в една стая, вероятността, че две от тези много малко хора ще имат същия рожден ден всъщност е супер висока, combinatorially. 50% относително, че в един клас от 22 души, семинар, на практика, 2 от тези хора ще имат същия рожден ден. Тъй като има толкова много начини, по които могат да имат същия рожден ден. Дори по-лошо, ако се вгледате в дясната страна на графиката, от времето, когато имат клас с 58 ученици в него, вероятността от два хора, които имат рожден ден е супер, супер високо, почти 100%. Сега, това е нещо забавно факта за реалния живот. 

Но последствията, сега, за структури от данни и съхранение на информация означава, че само ако приемем, че имат хубав, чист, равномерно разпределение на данни и имате достатъчно голям масив, за да се поберат на един куп неща не означава ли, че ще накараме хората в уникални места. Отиваш да има сблъсъци. Така че това понятие на хеширане, както се нарича, входен като "Алиса" и го масажирате по някакъв начин и след това да се върна отговор, като 0 или 1 или 2. Връщайки се някакъв изход от тази функция е измъчван от тази вероятност от сблъсък. И така, как можем да се справят с тези сблъсъци? Е, в единия случай, ние можем да се идеята, че беше предложено. Ние можем само да прехвърля всички, или може би малко по-просто, , а от движение всички останали, нека просто се движат Анита до дъното на достъпно място. Така че, ако Алис е 0, Боб е в една, Чарли е в 2, ние просто ще сложи Анита на място 3. И това е техника по структури от данни, наречена линейна сондиране. Linear защото сте просто ходене тази линия, и вие сте вид сондиране за наличните места в структурата на данните. Разбира се, това преминава в O (N). Ако структурата на данните е наистина пълен, има 25 души в него вече и след това Анита идва заедно, тя се озовава в какво ще бъде място Z, и това е добре. Тя все още се вписва, и ние можем да я намерим по-късно. 

Но това е в противоречие с целта за ускоряване на нещата. И какво, ако вместо това въведоха този третото измерение? Тази техника е обикновено се нарича отделна верижното, или с вериги. И какво е хеш таблица е, че това таблична структура, масата ви е само масив от указатели. Но какви са тези указатели сочат познайте какво? Свързан списък. И какво, ако вземем най-доброто от двете тези светове? Ние използваме масиви за първоначалните индекси в структурата на данните, така ние можем веднага да отидете на [0] [1], [30] или т.н., но така, че ние имаме известна гъвкавост и ние може да се побере Анита и Алис и Адам и всяко друго име, вместо това нека другата ос расте произволно. И най-накрая, в понеделник, че изразителни възможности с свързан списък. Структура на данните могат да растат произволно. Освен това, бихме могли просто да направи огромна 2-мерен масив, но това ще бъде ужасна ситуация, ако един от редовете в 2-мерен масив не е достатъчно голям, за допълнителен човек, чието име се случва да започне с А. Дай Боже, ние трябва да се преразпределят огромна 2-измерна структура просто защото има толкова много хора, обявен за особено когато има толкова малко хора, наречени Z нещо. Това е просто ще бъде много рядка структурата на данните. Така че това не е добра от какъвто и да е начин, но сега най-малкото имат способността веднага да намерите, когато Алис или Анита принадлежи, най-малко по отношение на вертикалната ос, и тогава ние просто трябва да решите къде да поставите Анита или Алиса в страната на този свързан списък. Ако не ни пука за сортиране на нещата, колко бързо можем да вмъкнете Алиса в структура като тази? Това е константно време. Ние индекс в [0], и ако никой не е там, Алис отива в началото на тази свързан списък. Но това не е огромна сделка. Защото, ако Анита след това идва заедно известен брой стъпки по-късно, когато Анита принадлежат? [0]. Обектно-ориентиран. Алис е вече в тази свързан списък. 

Но ако ние не им пука за сортиране на тези имена, можем просто да се движат Алис свърши, посочете Анита, но дори и това е константно време. Дори ако има Алис и Адам и всички тези други имена, това не е наистина пренасочването им към физически. Защо? Защото ние просто тук с свързан списък, кой знае тези възли са все пак? Всичко, което трябва да направите, е да преместите галета. Преместване на стрелките; не трябва физически да се местят данни около. Така че можем да вмъкнете Анита, в този случай незабавно. Константно време. Така че ние имаме постоянно търсене, и постоянно поставяне на някой като Анита. Но вид oversimplifying света. Какво ще стане, ако по-късно искате да намерите Алис? Какво ще стане, ако по-късно искате да намерите Алис? Колко стъпки е, че ще отнеме? [Student отговор, неразбираем] Точно така. Броят на хората, преди Алис в свързан списък. Така че това не е съвсем перфектна, защото нашата структурата на данните, отново, тази вертикална достъп и след това го има тези свързани списъци висящи - всъщност, да не се съставя един масив. Той има тези свързани списъци виси от това, че изглежда малко нещо подобно. Но проблемът е, че ако Алис и Адам и всички тези други имена в крайна сметка все повече и повече там, намиране на някой може да свърши куп стъпки, bcause имате да прекосяват свързан списък, което е линейна операция. Така че наистина, тогава времето, вмъкване в крайна сметка е O (N), където N е броят на елементите в списъка. Разделена, нека произволно го наричат ​​m, където m е броят на свързаните списъци , която имаме в тази вертикална ос. С други думи, ако наистина поеме равномерно разпределение на имена, напълно нереалистично. Има очевидно повече на някои писма от други. 

Но ако приемем за момента, в който равномерно разпределение, и ние сме N общия брой на хората, и м общо вериги достъпни за нас, тогава дължината на всяка една от тези вериги много просто ще бъде общо, N, разделен на броя на вериги. Така N / m. Но тук е мястото, където можем да бъдем всички математически умен. m е константа, защото има фиксиран брой от тях. Ти ще обяви своя масив в началото, и ние не сме преоразмеряване на вертикалната ос. По дефиниция, която остава фиксирана. Това е само хоризонталната ос, така да се каже, че се променя. Така че, технически погледнато, това е константа. Така че сега времето, вмъкване е почти O (N). Така че това не чувстват всички, че много по-добре. Но каква е истината? Е, през цялото това време, в продължение на седмици, ние сме били казват O (N ²). O (N), 2 х н ² - N, разделена на 2. . . ECH. Това е просто N ². Но сега, в тази част на семестъра, можем да започнем отново да говорим за реалния свят. И N / m е абсолютно по-бързо, отколкото просто N сам. Ако имате хиляди имена и да ги разделите на няколко кофи , така че имате само десет имена във всяка една от тези вериги, абсолютно търсене десет неща, ще бъде по-бързо, отколкото хиляда неща. И така, един от предстоящите проблемни комплекти ще ви предизвикателство да се мисли за точно това, въпреки че, да, асимптотично и математически, това е все още само линейно, което е гадно по принцип, когато се опитвате да намерите неща. В действителност, това ще бъде по-бързо, отколкото това защото на този делител. И така отново ще бъде този компромис и този конфликт между теория и реалност, и едно от копчетата ще почне да се върти в този момент в семестър е повече от една реалност, тъй като ние някак се подготвят за края semster , тъй като ще се въведе в света на уеб програмирането, където наистина, изпълнението ще се броят, защото вашите потребители ще започнете да се чувствате и да ги оценят лоши дизайнерски решения. 

Е, как да отида за изпълнението на свързания - хеш таблица с 31 елемента? И предишния пример е произволно за рождени дни. Ако някой има рожден ден от 1 януари или февруари 1, ние ще ги постави в тази кофа. Ако това е януари 2, 2 февруари, 2 март, ще ги поставя в тази кофа. Ето защо е било 31. Как се обяви хеш таблица? Тя може да бъде доста проста, възел * Таблицата е произволно име за него, [31]. Това ми дава 31 указатели към възли, и това ми позволява да имам 31 указатели към свързани списъци дори ако тези вериги са първоначално NULL. Какво искам да се сложи, ако искам да се запази "Alice", "Боб", "Чарли"? Е, ние трябва да приключи тези неща в структура защото имаме нужда от Алис да се отбележи Боб, да сочи към Чарли, и така нататък. Не можем просто да имат само имената, така че може да се създаде нова структура, наречена възел тук. 

Какво е действителното възел? Какво е възел в тази нова свързан списък? Първото нещо, наречено дума, е за името на лицето. Дължина, вероятно, се отнася до максималната дължина на името на човека, каквото и да е, 20, 30, 40 знака в луди случаи ъглови, и едно е за какво? Това е просто допълнително характер NULL, \ 0. Така че този възел опаковане "нещо" вътре в себе си, но също така декларира указател, наречен следващия така че можем верига Алис на Боб с Чарли и така нататък. Може да бъде нула, но не е задължително да бъде. Всички въпроси по тези хеш-таблици? Да? [Student питам въпрос, неразбираем] масив - добър въпрос. Защо това е Чар дума в масив, а не просто Чар *? В тази донякъде произволен пример, аз не искам да се налага да прибягват изчистване за всеки един от оригиналните имена. Исках да обяви максималното количество памет за низ така че мога да копирате в структурата Алис \ 0 и не трябва да се справят с изчистване и свободен и подобни. Но бих могъл да направя, че ако исках да бъда по-съзнателно използване на пространството. Добър въпрос. Така че нека се опитаме да обобщим далеч от това и се фокусира върху остатъка от днес на структури от данни, в по-общ план и други проблеми, които можем да решим, като се използват същите основи въпреки че самите структури от данни може да се различават в данните. 

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

Каква е модел как сме, това или как Патрик изложи в своето видео? Това е нещо очевидно, че има някакъв сортиране става тук, но това, което е просто правило? Да? [Student отговор, неразбираем] Perfect. Ако погледне, ще видите малък брой от ляво, големите цифри отляво, но това е вярно за всеки възел. За всеки възел, лявата му дете по-малко от него, и правото си дете по-голяма от него. Какво означава това сега е, ако искам да потърся тази структура на данните, да речем, брой 44, Трябва да започне в основата, защото, както с всички тези по-сложни структури от данни, имаме само указател към едно нещо, от самото начало. И в този случай, началото е коренът. Това не е в левия край, това е коренът на тази структура. Така че виждате тук, е 55, а аз търся 44. Коя посока да искате да отидете? Е, аз искам да отида на ляво, защото очевидно, в дясно ще бъде твърде голям. Така че забележите тук, ти си вид концептуално кълцане на дърво в 1/2 защото никога не отиваме към дясната страна. Така че сега отивам от 55 до 33. Това е твърде малко на брой. Търся 44, но сега знам, ако 44 е в това дърво, мога да отида очевидно надясно. Така че отново, аз съм подрязване на дървото наполовина. Това е почти идентичен концептуално до телефонния указател. Това е идентично с това, което направихме с документите на дъската, но това е по-сложна структура, която ни позволява да се прави това разделяй и владей по проект на алгоритъма, и в действителност, пресичащо структура като тази - ОПА. Присичайки структура като тази, където това е само "отиде по този начин или да отидете по този начин", означава, че кода, който се наведе ума си първи при реализирането му в раздел или пеша през него у дома, за двоично търсене, използване на рекурсия или итерация това е болка в областта на шията. Среда елемент, след това направете закръгляне нагоре или надолу. 

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

Така че има друга структура на данните, че можем да представим. Това е проектирана на пръв поглед да изглежда загадъчно, но това е невероятно. Така че това е структура, наречена Trie, Trie, който е наследил от думата извличане на данни, които не се произнася повторно опит-вал, но това е, което светът нарича тези неща. Опитва. T-R-и-д. Това е дървовидна структура от някакъв вид, но всеки един от възлите в Trie се появява за да бъде това? И това е малко подвеждащо, защото това е вид съкратено. Но изглежда, че всеки възел в тази Trie е всъщност масив. И въпреки че авторът на тази схема не е показано, в този случай, това Trie е структура от данни, чиято цел в живота е да съхранява думи като A-л-и-в-д или B-о-б. И начина, по който тези данни магазини Алис и Боб и Чарли и Анита и т.н. се използва масив за съхранение на Алиса в страната на Trie да започнем коренът, който изглежда като масив, и това е било написано в съкратена нотация. Авторът пропусне abcdefg, защото нямаше никакви имена с това. Те показват само М и P и Т, но в този случай, нека да се отдалечи от Алис и Боб и Чарли някои имена, които са тук. Максуел е действително в тази схема. Как автора магазин М-х-w-е-л-л? Той или тя започна в основата възел и отиде да [M], така че около 13, на 13-то място в масива. Тогава от там, има показалка. Показалеца, което води до друг масив. От там авторът индексират в този масив на място А, както е показано в горния ляв и тогава той или тя следва, че показалецът да друг масив, и отиде на показалеца на място при X. Тогава в следващото място масив W, E, L, L, и т.н., и накрая, нека се опитаме да сложите снимка на това. Какво прави един възел изглежда като код? Възел в Trie съдържа масив от указатели към повече възли. Но има и трябва да има някакъв вид на булева стойност, поне в това изпълнение. Аз се случи да го наричат ​​is_word. Защо? Защото, когато вие поставяте Максуел, вие не поставяте нищо в тази структура на данните. Вие не пишат М. не пишат X. Всичко, което правим, е след указатели. Указател, който представлява M, показалеца, която представлява, показалеца, който представлява X, W, E, L, L, но това, което трябва да направите, в края е нещо отидете, проверете, стигнах до това място. Имаше дума, която завършва тук, в структурата на данните. 

Така че това, което Trie е наистина изпълнен с автора избра да представлява тези terminuses с малки триъгълници. Това просто означава, че всъщност този триъгълник е тук, това булева стойност на истинската означава, че ако се върнете назад в дървото, това означава, че една дума, име Максуел е в това. Но думата Foo, например, не е в дървото, защото ако започна коренът тук най-отгоре, Има показалеца не е, няма показалеца о, не показалеца о. Foo не е име в този речник. Но за разлика от Тюринг, т-у-р-и-н-гр. Отново, аз не съхранявате тона или U или R или аз или н или г. Но аз направих магазин в структурата на данни стойността на верния път тук, в този възел - в дърво чрез създаването на тази булева стойност на is_word да е истина. Trie е вид на този много интересен мета структура, , където не сте наистина съхранение на думи за себе си този вид на речника. Да бъде ясно, просто съхранение "да" или "не", има дума, която свършва тук. 

Сега, какъв е изводът? Ако имате 150 000 думи в речника, че се опитвате да се съхранява в паметта използвате нещо като свързан списък, ще имат 150 000 възли в свързали списък. И намирането на една от тези думи по азбучен ред може да отнеме O (N) време. Линейно време. Но в случай на Trie, какво е времето на работа на намирането на думата? Оказва се, че красотата тук е, че дори и ако имате 149 999 думи, които вече са в този речник, , както се прилага с тази структура на данните, колко време отнема да се намери или да вмъкнете още един човек в това, като Алис, Алис? Е, това е само пет, може би шест стъпки за задния характер. Тъй като presense на други имена в структурата не в начина на поставяне на Алис. Освен това намирането на Алис, след като има 150 000 думи в този речник не получите във вашия начин за намиране на Алис, защото е Алис. . . . . тук, защото открих булева стойност. И ако няма булев вярно, тогава Алис не е в това структурата на данните на думи. С други думи, време за намиране на неща и да поставите нещата в тази нова структурата на данните на Trie O - това не е N. Тъй като presense на 150 000 души има никакъв ефект върху Алис, както изглежда. Така че нека да го наречем к, където к е максималната дължина на думата на английски език който обикновено е не повече от 20-тина символи. Така че к е константа. Така че Светия Граал изглежда вече сме в момента е, че на Trie, константно време за вложки за заявки, за изтриване. Тъй като броят на неща, които вече са в структурата, , които дори не са физически там. Отново, те просто някак отметка, "да" или "не", не оказва влияние на нейното бъдещо време на работа. 

Но там трябва да е уловка, защото в противен случай не би да губи толкова много време по всички тези други структури от данни най-накрая да стигнем до тайната, това е невероятно. Така че каква цена се плаща за да се постигне това величие тук? Space. Това нещо е огромно. И причината, че авторът не го представя тук, забележете, че всички тези неща, които приличат на масиви, той не изтегли останалата част от дървото, а останалата част на Trie защото те просто не са свързани с историята. Но всички тези възли са супер широк, и всеки възел в дървото заема 26 или всъщност, може да бъде 27 знака, защото в този случай, включително място за апостроф , така че бихме могли да има apostrophized думи. В този случай, те големи масиви. Така че, въпреки че те не са picutured, това отнема огромно количество RAM. Което може да се оправи, especilly в съвременния хардуер, но това е компромис. Ставаме по-малко време, като прекарат повече пространство. Е, къде е всичко това отиваш? Е, нека да направим - нека видим тук. Нека да направим скок на този човек тук. 

Вярвате или не, колкото и забавно като C е бил за известно време сега, ние сме достига точката на семестъра, когато е време за преход към по-модерни неща. Неща на по-високо ниво. И въпреки, че за следващите няколко седмици ние все пак ще продължи да се потопим в света на указатели и управление на паметта за да получите този утехата, с която може да се гради върху, края на играта е в крайна сметка да се въведе, по ирония на съдбата не, този език. Ние ще отделим, както и 10 включени минути за разговори за HTML. HTML е език за маркиране и какво е език за маркиране е е тези серии на отворени скоби и затворени скоби, които казват "това смело" - Това курсив "направи това в центъра на. Това не е всичко, което интелектуално интересно, но това е супер полезно. И със сигурност това е вездесъщ тези дни. Но това, което е мощен за света на HTML и уеб програмиране в по-общ план, изграждането на динамични неща, писане на код в езици като PHP или Python или Ruby или Java или C #. Наистина, независимо от езика си на избор, и генериране на HTML динамично. Генериране на нещо, наречено CSS динамично. На Cascading Style Sheets, което също е за естетиката. И така, въпреки че днес, ако отида на някои сайт като познатия Google.com и отивам да ги видите, разработчик, изглед източник, който може би не съм правил преди, но ще видите източник, тези неща вероятно изглежда доста загадъчно. Но това е основният код, който изпълнява Google.com. На предния край. И всъщност всичко това е пухкав естетика неща. Това е CSS тук. Ако продължавате да превъртате надолу ще получите някои оцветени неща. Това е HTML. Код на Google изглежда като каша, но ако действително се отвори друг прозорец, можем да видим някаква структура за това. Ако отворя тази на, забележете, тук, това е малко по-разбираеми. Отиваме да видите след дълго този етикет, [думата] е етикет, HTML, главата, тялото, DIV, скрипт, текстовото поле, педя, центриран, Div. И това също е някак загадъчен изглеждащи на пръв поглед, но цялата тази бъркотия следва определени модели, и повтарящи се модели, така че след като получите основите надолу, вие ще бъдете в състояние да напише код, като този и манипулира код, като се използва още един език, наречен JavaScript. И JavaScript е език, който се движи вътре в браузъра днес, че ние използваме на Харвард курсове, за търговски инструмент Разбира се, че Google Карти използва да ви дам един куп на динамика, Facebook ви дава мигновени актуализации за състоянието, Twitter се използва, за да ви покажа туитове незабавно. Всичко това ще започнем да се потопим. Но за да стигнем до там, ние трябва да разберем нещо за интернет. Този клип тук е само за една минута дълго, и нека да приемем, за сега това е, в действителност, как интернет работи като закачка за това, което е на път да дойде. Аз ви давам "Войни на мрежата". 

[♫ Slow музика хор ♫] [Мъж] Той дойде с послание. С протокол собствения си. [♫ бързо електронната музика ♫] Той дойде в един свят на готини защитни стени, незаинтересовани рутери, и опасностите далеч по-лоши от смъртта. Той е бърз. Той е силен. Той е TCP / IP, и той има адреса си. Войни на мрежата. [Малан] Следваща седмица, тогава. Интернет. Уеб програмиране. Това е CS50. [CS50.TV]