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

Добре, това е CS50, и това е началото на 4-та седмица, и това е една от най-бавните възможни алгоритми за сортиране. Кой от тях е, че ние просто гледах там? Това е балон вид, за голяма O (N ^ 2) + сума, и ние наистина не са единствените, които в този свят, за да изглежда, че знае какво балон вид е или време на работа. В действителност, това е интервю с Ерик Шмид от Google и бивш сенатор Барак Обама само преди няколко години. 

Сега, сенатор, вие сте тук в Google Харесва ми да мисля на президентството като интервю за работа. Сега е трудно да си намеря работа като президент, и ти започваш сега тръпки. То също е трудно да си намеря работа в Google. Ние имаме въпроси, и ние искаме нашите кандидати въпроси, и това е от Лари Швимер. Вие, момчета, мисля, че се шегувам? Това е точно тук. Какво е най-ефективният начин да сортирате един милион 32-битови цели числа? [Смях] Е- Съжалявам. >> Не, не, не, не. Мисля, че нещо балон ще бъде погрешен начин да отида. 

Хайде, кой му е казал това? Миналата седмица спомняте, си взе почивка от кода, поне за един ден, и започна да се фокусира върху някои по-висши идеи и решаване на проблеми в по-общ план в контекста на търсене и сортиране, и ние въведохме нещо, което не е шамар това име на миналата седмица, но асимптотичната бройна система, Big O, Big Омега, и понякога Big Theta нотация, а те са просто начини да се опише времето за изпълнение на алгоритми, колко време е необходимо, за алгоритъм, за да се изпълнява. 

И може би си спомняте, че сте говорили за времето на работа по отношение на размера на вложените материали, което ние обикновено наричаме N, каквото може да има проблем, където N е броят на хората в стаята, броя на страници в телефонния указател, и ние започнахме да пишем за неща, като O (N ^ 2) или O (N) или O (N дневник н), и дори когато математиката не е съвсем работи толкова перфектно и това е н ² - N / 2 или нещо подобно ние вместо просто ще изхвърли някои от по-ниските условията ред, и мотивацията там е, че ние наистина искаме вид обективен начин за оценяване изпълнението на програми или изпълнение на алгоритми , че в края на деня няма нищо общо, например, със скоростта на вашия компютър днес. 

Така например, ако решите да реализирате вид балон, или да реализирате сливане вид или подбор вид на компютъра днес, 2 GHz компютър, и можете да го стартирате, и то под известен брой секунди, през следващата година има 3 GHz или 4 GHz компютър, и може да се твърди, че: "Уау, ми алгоритъм сега е два пъти по-бързо ", когато в действителност, че очевидно не е така. Това е просто хардуера е намерила по-бързо, но вашият компютър не, и така ние наистина искате да изхвърлите неща, като кратни на 2 или кратни на 3, когато става въпрос за описващ колко бързо или колко бавно алгоритъмът е и наистина просто се съсредоточи или някакъв фактор от него, някаква сила, тъй като в случай на видове от миналата седмица. И припомни, че с помощта на вид сливане ние бяхме в състояние да го направят много по-добре от балон сортиране и сортиране на избор и дори вмъкване вид. 

Трябва да влезете N N, и отново, припомни, че дневника н обикновено се отнася до нещо, което расте по-бавно N, така че N дневник N до този момент е добро защото тя е по-малко от N ². Но за постигането н влезете с вид сливане каква е била основната зародиша на идеята, че ние трябваше да се наберат че ние също отнесена обратно в седмици 0? Как се справим сортиране проблем умело с вид сливане? Какъв е ключът прозрение, може би? Всеки в всичко. Добре, нека да направи крачка назад. Опишете се слеят нещо в собствените си думи. Как работи? Добре, ние ще гребе обратно седмица 0. Добре, да. [Чува студент] Добре, добре, така че ние раздели масив от числа в две парчета. Сортирани всяка от тези парчета, а след това ги слива, и видяхме тази идея, преди да вземе този голям проблем, който е кълцане до в този голям или този голям проблем, това е. 

Спомнете си например телефонния указател. Спомнете си за самостоятелно отчитане алгоритъм от седмица преди, така се слеят вид са обобщени от този pseudocode тук. Когато сте н елементи, първо, че е здрав разум проверите. Ако N <2 не правят нищо защото ако N <2, тогава N очевидно е 0 или 1, и така, ако това е или 0 или 1, няма нищо да сортирате. Сте готови. Вашият списък вече е тривиално сортирани. Но в противен случай, ако имаш два или повече елемента отидете напред и да ги разделят в две половини, наляво и надясно. Подреди всяка от тези половини, а след това сливане на сортираните половинки. Но проблемът тук е, че на пръв поглед това се чувства като ние сме плоскодънни лодки. Това е кръгова дефиниция в това, ако съм ви помолих да сортирате н елементи и сте ми казваш "Добре, добре, ние ще сортирате тези N / 2 и тези N / 2 елементи" тогава следващият ми въпрос ще бъде "Добре, как да сортирате N / 2 елементи? 

Но поради структурата на тази програма, защото има случай тази база, така да се каже, този специален случай, който казва, че ако N <някаква фиксирана стойност, като две връщане веднага. Не отговаряйте със същия кръгъл отговор. Този процес, тази цикличност в крайна сметка ще приключи. Ако аз ви питам "Сортиране тези н елементи," и вие казвате: "Добре, сортирайте ги N / 2" тогава ще каже: "Добре, сортирате N / 4, N / 8, n/16," в крайна сметка ще се разделят с достатъчно голям брой , че ще имате само 1 ляво елемент, при което може да се каже, "Ето, тук е подредени един елемент." След блясъка на този алгоритъм тук е да произлиза от факта, че след като имате всички тези индивидуално сортирани списъци, всички от които са с размер 1, което изглежда да бъде безполезно, когато започнете да ги сливане и сливането им да изградят най-накрая като Роб във видеото накрая сортиран списък. 

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

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

Уили. >> Willy, Сара, Кели и Уили. Точно сега съм бил зададен въпрос от някой колко хора са на този етап, и аз нямам идея. Това е наистина дълъг списък, така че вместо това ще направя този трик. Отивам да попитам човек до мен, за да направим голямата част от работата, и веднъж тя върши по-голяма част от работата се извършва Отивам да се направи най-малко количество работа е възможно и просто добавете 1 независимо от нейния отговор, така че тук отиваме. Бях помолен колко хора са на сцената. Колко хора са на сцената в ляво от вас? Ляво от мен? >> Добре, но не мамят. Това е добре, това е вярно, но ако искаме да продължим тази логика нека приемем, че подобно искате да шута на този проблем в ляво от вас, така че вместо отговор директно да отидете напред и само да се отмятат. О, колко много хора са в ляво от мен? Колко хора са в ляво? 1. [Смях] Добре, така че 0, така че сега какво Уили е направил е сте върнали отговор на въпроса си тази посока, каза 0. Сега, какво трябва да направя? >> 1. Добре, така че вие ​​сте на 1, така че вие ​​казвате, "Добре, аз отивам да добавите 1 независимо от броя на Уили ", така че 1 + 0. Вече сте 1 така отговора си прави сега е 1. >> Мината ще бъде 2. Добре, така че сте като предишния отговор на една добавяне на минимално количество работа, което искате да направите, е един. Сега имате две, а след това на ръка ми коя стойност? 3, искам да кажа, съжалявам, 2. Добре. 

Е, ние имахме 0 наляво. Тогава имахме 1, а след това се прибавят 2, и сега ми подаде номер 2, и затова казвам, добре, 1, 3. Има наистина 3 души, застанали до мен на този етап, така че бихме могли очевидно са направили това много линейно, много очевидно, но какво сме наистина? Взехме проблем с размер 3 първоначално. След това го събори в проблема с размер 2 тогава проблема с размер 1, и накрая базов беше наистина, о, там няма никой, в който момент Уили се връща ефективно хард-кодиран отговор на няколко пъти, , а вторият беше с балончета, с балончета, с балончета, и след това чрез добавяне на този допълнителен 1 ние въведохме тази основна идея на рекурсия. 

Сега, в този случай не е наистина решаване на проблема по-ефективно тогава сме виждали до този момент. Но мисля, че за Алгоритмите, които съм правил на сцената до този момент. Имахме осем парчета хартия върху дъската, на видео, когато Шон е търсил за номер 7, и това, което е наистина? Е, той не е направил какъвто и да е вид на разделение и владей. Той не го направи какъвто и да е вид на рекурсия. Вместо това той просто направи това линеен алгоритъм. Но когато ние въведохме идеята на сортирани номера на сцената живеят миналата седмица Тогава ние имахме този инстинкт да ходят до средата, в този момент имахме по-малък списък с размер 4 или друг списък с размер 4, и след това имахме точно същия проблем, така че ние повтаря, повтаря, повтаря. С други думи, ние recursed. Благодаря ви много на нашите три доброволци тук за доказване на рекурсия с нас. 

Да видим, ако не можем да направи това сега малко по-конкретен, решаването на един проблем, който отново бихме могли да направим много лесно, но ние ще го използва като трамплин за прилагане на тази основна идея. Ако искам да се изчисли сумата от куп номера, Например, ако давате под номер 3, Искам да ви дам стойността на сигма 3, така че сумата от 3 + 2 + 1 + 0. Искам да се върна на отговор 6, така че ще изпълнява тази сигма функция, това сумиране функция , че отново се на входа и след това се връща на сумиране на този номер по целия път надолу до 0. Можем да го направим доста просто, нали? Можем да го направим с някакъв вид на примка структура, така че нека да вървим напред и да започваме. 

Включете stdio.h. Позволете ми да влязат в основната, за да работят тук. Да спасим като sigma.c. Тогава аз ще отида тук, и аз отивам да обявят INT N, и аз отивам да направите следното, докато потребителят не сътрудничи. Докато потребителят не ми е дал положително число позволете ми да отида напред и да ги пита за N = GetInt, и нека ми ги даде някои инструкции за това какво да правя, така ФОРМАТ ("положително число, моля"). Просто нещо сравнително просто като това, така че по времето когато удари линия 14 сега ние имаме положително число вероятно в N. 

Сега нека направим нещо с него. Нека вървим напред и изчисляване на сумиране, така вътр сума = сигма (N). Sigma е просто сумиране, така че аз съм просто го пише в красиви. Ние просто ще го нарека сигма там. Това е сумата, а сега аз отивам да изведе резултата, ФОРМАТ ("Сумата е% г \", сумата). И тогава ще върне 0 за добра мярка. Ние сме направили всичко, което тази програма изисква освен интересната част, което е действително прилагане на сигма функция. 

Нека отида до дъното, и нека да декларира функция сигма. Трябва да се вземат променлива, която е от тип цяло число, и какъв тип данни искам да се върна вероятно от сигма? Int, защото искам да съответстват на очакванията ми по линия 15. Тук нека вървим напред и да изпълнява настоящата в един доста директен начин. 

Да вървим напред и да каже INT сума = 0, и сега аз отивам да имат малко контур тук , че ще каже нещо подобно, (Int I = 0; I <= брой; + +) сумата + = I. И тогава аз отивам да се върне сумата. Би могла да осъществи това по всякакви начини. Бих могъл да използвам време контур. Можех да се отстраняват с помощта на сумата променлива, ако аз наистина исках да но по-кратко, ние просто трябва функция, която ако не съм глупак декларира сума е 0. След това повтаря от 0 нагоре чрез броя, и на всяка итерация добавя, че настоящата стойност на сумата и след това се връща сумата. 

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

Знам, че има поне едно нещо в тази програма, че аз съм направил погрешно. Когато удари влиза отивам да получите всякакъв вид да ми крещи? Какво съм аз ще се разкрещя за? Да, забравих прототип, така че аз съм с функция, наречена сигма по линия 15, но това не е обявен до ред 22, така че най-добре активно тук и да обявят прототип, и аз ще кажа INT сигма (INT номер) и това е всичко. Тя се осъществява в долната част. 

Или друг начин да се реши този, Мога да преместите функцията там, което не е лошо, но най-малко, когато вашите програми започват да се получи дълго, честно казано, Мисля, че има известна полза от това винаги като основната на върха така че да можете в четеца може да отворите файла и след това веднага да видите това, което програмата прави, без да се налага да се търси чрез търсите, че основната функция. Да вървим надолу, за да ми терминален прозорец тук, опитайте се прави сигма направи сигма, и аз прецаках тук. Implicit декларация на функцията GetInt означава, че съм забравил какво друго да направя? [Чува студент] Добре, така че очевидно е често срещана грешка, така че нека това тук, cs50.h, а сега нека се върнем на моя терминален прозорец. 

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

Нека вместо това сега правя това. Нека вместо да каже, че на сумиране на броя до 0 е наистина едно и също нещо като номер + сигма (брой - 1). С други думи, точно като на сцената punted на всеки един от хората, които са до мен, и те на свой ред плоскодънни лодки, докато най-накрая дъно от Willy, , които трябваше да се върне хард-кодиран отговор, като 0. Ето сега сме подобно плоскодънни лодки сигма същата функция като първоначално е бил наречен, но ключово прозрение тук е, че ние не се обаждате сигма идентично. Ние не сме преминаване в н. Ние сме ясно преминаване на брой - 1 така че малко по-малък проблем, малко по-малък проблем. 

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

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

Уговорката тук е, че не можем просто сляпо се върне сигма, номер + сигма на малко по-малък проблем. Ние трябва да имаме някаква база случай тук, и какво трябва базов вероятно ще бъде? [Чува студент] Добре, толкова дълго, колкото е положително всъщност трябва да се върне това, или казано по друг начин, ако номерът е, да речем, <= 0 знаеш ли какво, аз ще отида напред и да се върнете 0, много прилича на Уили, и друго, аз отивам да вървим напред и да се върне, така че не е, че много по-кратък от повтарящата се версия, че ние бита първо с помощта на примка, но забележите, че има този вид на елегантност към него. Вместо да върне някакъв номер и изпълнение на всичко това математика и добавяне на нещата с локални променливи ти вместо да казва: "Добре, ако това е супер лесен проблем, , като броят е <0, нека незабавно да върне 0. 

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

С други думи, сега има начин за превод на тази реална конструкция свят, това по-високо ниво конструкт на разделяй и владей и правиш нещо отново и отново в кода, така че това е нещо, което ще видя отново с течение на времето. Сега, като освен, ако сте нови за рекурсия, трябва най-малкото сега разбирам защо това е смешно. Отивам да отидете на google.com, и аз отивам да търсите за някои съвети и трикове за рекурсия, въведете. Кажете на човека до теб, ако те не се смееха точно сега. Може би имахте предвид рекурсия? Може би имахте предвид ах, там отиваме. Добре, сега това е останалата част от всеки. Малко великденско яйце, скрита някъде там в Google. Като настрана, една от връзките, пуснати на сайта на курса за днес е само тази мрежа на различни алгоритми за сортиране, някои от които разгледахме миналата седмица, но това, което е хубаво за тази визуализация като се опитате да увийте ума си около различни неща, свързани с алгоритми знаете, че можете много лесно да се започне с различни видове суровини. Входовете обърната, входове, които най-вече са подредени, входовете случаен принцип и така нататък. Като се опитате да, отново се разграничат тези неща в ума си осъзнаят, че това URL на интернет страницата на курса на лекциите страница може да ви помогне причина през някои от тези. 

Днес най-накрая да реши този проблем от известно време, което е, че тази функция суап просто не работи, и какъв е основният проблем с тази функция суап, целта на което, отново, да обменят стойност тук и тук такава, че това се случва? Това в действителност не работят. Защо? Да. [Чува студент] Точно така, обяснението за тази bugginess просто е така, защото когато ти се обадя функции в C и тези функции взимат аргументи, както и б тук, преминават в копия на независимо от стойността, която се предоставя на тази функция. Не са първоначалните стойности на себе си, така видяхме това в контекста на buggyc, buggy3.c, който изглеждаше малко нещо като това. 

Спомнете си, че имахме х и у инициализира с 1 и 2, съответно. Ние след това се отпечатва това, което бяха. Тогава твърдяха, че съм ги смяна, като се обадите на замяна на X, Y. Но проблемът е, че смяна работи, но само в обхвата на суапа самата функция. Веднага след като удари линия 40 тези стойности разменят изхвърлено, и така нищо в оригиналната функция главната всъщност е променила изобщо, така че ако мислите тогава как изглежда това от гледна точка на нашата памет ако това лявата страна на управителния съвет представлява и аз ще направя всичко по силите си, за да ги видят всички това, ако това лявата страна на борда представлява, да речем, RAM, и стека ще растат нагоре по този начин, и ние наричаме функция, като основния, и главните има две локални променливи, х и у, нека опише като х тук, и нека Опишете тези години тук, и нека сложим в стойностите 1 и 2, така че това тук е основният, и когато основният нарича суап функция на операционната система дава суап функция своя откос на паметта на стека, своя собствена рамка на стека, така да се каже. Той също така разпределя 32 бита за тези цели числа. Това се случва, да ги наречем А и Б, но това е напълно произволно. Той би могъл да ги нарече каквото иска, но какво се случва, когато основната повиквания суап е, че отнема този 1, поставя копие там, поставя копие. 

Има 1 локалната променлива във суап, макар, наречен какво? >> Tmp. ПТУ, така че нека си даде още 32 бита, и това, което съм направил в тази функция? Казах INT малки получава, така че има едно, така че направих това, когато за последен път се играе с този пример. Тогава получава б, така че Б е 2, така че сега това става 2, и сега б получава температура, така че темп е едно, така че сега б става това. Това е страхотно. Той е работил. Но след това, веднага след като функцията връща памет суап ефективно изчезва, така че да могат да бъдат използвани от някои други функции в бъдеще, и главните очевидно е напълно непроменена. Ние трябва начин фундаментално решаването на този проблем, и днес ние най-накрая ще има начин да направите това с което ние можем да представим нещо, наречено указател. Оказва се, че можем да решим този проблем не от преминаване в копия на х и у но вместо това от преминаване в какво ли мисли, за суап функция? Да, какво за адреса? Не сме говорили за адреси в много подробности, но ако това дъската представлява паметта на моя компютър ние със сигурност може да започне номерирането байта в моя RAM и да кажа това е байт # 1, това е байт # 2, байт # 3, байт # 4, байт # ... 2 милиарда, ако имам 2 гигабайта RAM, така че ние със сигурност може да излезе с някаква произволна схемата за номериране за всички индивидуални байта в паметта на моя компютър. 

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

Така например, той или тя декларира масив с размер 10 но след това случайно се опитва да постави 11 байта в този масив на паметта, и да започнете да докосвате части от паметта, които вече не са валидни. Само да контекстуален това, някои от вас може би знаят, че софтуер често ви подканва за серийни номера или регистрационни ключове, Photoshop и Word и програми като тази. Съществуват пукнатини, както някои от вас знаят, онлайн, където можете да стартирате малка програма, и готово, не по искане на един сериен номер. Как се работи? В много случаи тези неща са просто в компютрите текстови сегменти в действителните нули и тези на компютъра къде е тази функция, ако се иска сериен номер, и да презапишете пространство, или докато се изпълнява програмата можете да разберете, когато ключът е действително складираното използва нещо, наречено дебъгер, и вие може да се пропука софтуер по този начин. Това не е да се каже, че това е нашата цел за следващите няколко дни, но има много реалния свят последици. Това се случва, да се включат кражба на софтуер, но има и компромис на цели машини. 

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

ФОРМАТ има тенденция да бъде много мощно нещо, но това е много ръчен процес. Трябва да се сложи ФОРМАТ тук, ФОРМАТ тук, и ако го сложите в рамките на цикъла може да получите 100 линии на продукция, която след това трябва да се пресее през. Това не е много лесен за употреба или интерактивен механизъм за отстраняване на грешки на програми, но за щастие съществуват алтернативи. Има програма, например, GDB, GNU Debugger, , което е малко тайнствена в това как да го използвате. Това е малко сложно, но честно казано, това е едно от онези неща, които, ако ще ви постави в тази седмица и следващата допълнителен час, за да се разбере нещо подобно GDB то ще ви спести вероятно десетки часове в дългосрочен план, Така че с това, позволете ми да ви дам една закачка как работи това нещо. 

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

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

Вместо да ми позволи да направя това. На този GDB ред, нека вместо въведете почивка, въведете. Това не е това, което исках да въведете. Нека вместо въведете пауза главната. С други думи, искам да настроите нещо, наречено точка на прекъсване, , което е подходящо име, защото то ще се счупи или пауза изпълнение на програмата си в съответното място. Майн е името на моята функция. Забележете, че GDB е доста умен. Разбра, че основната случва да започне приблизително на ред 18 на buggy3.c и забележете тук, в горния ляв б + е в непосредствена близост до линията 18. Това ми напомня, че съм на прекъсване на ред 18. Този път, когато напиша план, аз отивам да стартирате програмата ми нагоре, докато го удари, че точка на прекъсване, така че програмата ще направи пауза за мен в ред 18. Ето ни, бягай. Не се появява нищо да се случи, но известие в долния ляв край започване на програмата, buggy3 преКъсване 1 в основната линия buggy3.c 18. Какво мога да направя сега? 

Забележете, мога да започнете да пишете неща като печат, не ФОРМАТ, печатни Х, и сега това е странно. $ 1 е просто любопитство, както ще видим всеки път, когато печатате нещо вие получавате нов $ стойност. Това е, така че да може да се отнася до предишните стойности само в случай, но за сега печат ми казва, е, че стойността на х в този момент в историята очевидно е 134514032. Какво? Къде е, че дори идват от? [Чува студент] Истината е, че това е, което ние ще се обадя на стойност боклук, и ние все още не сме говорили за това, но причината, поради която се инициализира променлива е очевидно, така че те имат някаква стойност, която искате те да имат. Но улов се припомни, че можете да декларират променливи както направих аз преди малко в сигма моя пример без всъщност да ги придават стойност. Спомнете си какво съм направил тук в сигма. Аз заявих N, но каква стойност съм го даде? Няма, защото знаех, че в следващите няколко реда GetInt ще се погрижи на проблема на стойност вътрешността на N. 

Но в този момент в историята на ред 11 и ред 12 и ред 13 и ред 14 през тези няколко реда каква е стойността на N? В C просто не знам. Това е някакъв боклук стойност, някои напълно произволен брой , което е останало основно от някои предишната функция се управлява, така че програмата работи припомним, че функцията получава функция, функция, функция. Всички тези рамки се на паметта, а след това тези функции връщат, и точно както аз предложих с гумичка, паметта им в крайна сметка се използват повторно. Е, просто така се случи, че тази променлива х в тази програма изглежда да съдържат стойност, като някои боклук 134514032 от някои предишната функция, а не, че съм написал. Тя може да бъде нещо, което идва ефективно с операционната система, някои функции под капака. 

Добре, това е добре, но нека сега да преминете към следващия ред. Ако напиша "Напред" в моя GDB ред и натиснете въведете, забележите, че подчертаване се движи надолу, за да линия 19, а логично следствие е, че линия 18 вече е приключил изпълнение, така че, ако отново въведете "печат х" Аз сега трябва да видим една и наистина правя. Отново $ неща е начин на GDB ви напомня историята на разпечатките, че сте направили. Сега нека да вървим напред и да отпечатате г., и наистина, Y е някаква луда стойност, както и, но не е голяма сделка, тъй като на ред 19 ние сме на път да го зададете на стойност 2, така че нека да въведете отново "Next". И сега сме на ФОРМАТ линия. Нека ми печат х. Нека се отпечатват г.. Честно казано, аз съм малко уморен от печата на тази. Нека вместо въведете "дисплей х" и "дисплей г., и сега всеки път, когато въведете командата в бъдеще Аз ще се напомни за това, което е х и у, какъв е х и у, какъв е х и у. 

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

Позволете ми да въведете следващия отново, а сега и тук е интересната част. В този момент в историята г. е 2, и х е 1, както е предложено тук, и отново, Причината за това е автоматично показване е така, защото аз използвах командата Показване на X и дисплей г., така че в момента пиша следващия на теория х и у, трябва да се превърне разменят. Сега, ние вече знаем, че това няма да се случи, но ще видим в момента как можем да се потопите дълбоко, за да разбера защо това е вярно. На следващо място, и за съжаление, Y е все още 2 и х е все още едно, и мога да потвърдя толкова. Печат X, печат Y. Наистина, няма смяна действително се е случило, така че нека започнем над. Ясно суап е счупен. Нека вместо да напишете "Run" отново. Позволете ми да кажа да, искам да го рестартирате от самото начало, въведете. 

Сега аз съм на ред 18. Сега забележите х и у са боклуци стойности отново. Следващо място, следващото, следващото, следващото. Ако аз се отегчават мога да просто да напишете N следващия. Можете да го съкрати възможно най-кратък последователност от символи. Swap сега е счупен. Да се ​​потопите в, така че вместо да пишете следващата сега отивам да въведете стъпка, така че аз съм засилване в рамките на тази функция така че мога да минеш през нея, така че удари стъпка и след това въведете. Забележете, че подчертавам скача по-надолу в моята програма до линията 36. Сега какви са локални променливи? Информация за местните жители. Нищо просто защото все още не сме стигнали до тази линия, така че нека да вървим напред и да каже "следващия". Сега изглежда, имаме малки, малки печат. Garbage стойност, нали? Мисля, че да. Какво ще кажете за Печат, печат б, 1 и 2? В един момент, веднага след като напиша следващия отново ПТУ ще отнеме на стойност от 1, да се надяваме, защото ПТУ е ще трябва да бъде назначен стойността на. 

Сега нека да се отпечатват, печат б, но сега да отпечатате малки, и това е наистина едно. Позволете ми да правя по-нататък. Позволете ми да правя по-нататък. Свърших суап функция. Аз все още съм вътре в него на ред 40, така че нека да отпечатате, печат б, и не ми пука какво ПТУ е. Тя изглежда като суап е правилна, когато става въпрос за смяна на А и Б. Но ако сега въведете следващия, скочи обратно на линия 25, и разбира се, ако пиша в х и печат у те все още са непроменени, така че не сте оправили проблема. Но диагностично сега може би с това GDB програма сме най-малко намерила една стъпка по-близо до разбирането какво не е наред, без да се налага да постеля нашия код чрез поставяне ФОРМАТ тук, ФОРМАТ тук, ФОРМАТ тук и след това да я пуснете отново и отново опитвайки се да разбера какво точно не е наред. 

Отивам да вървим напред и да се откажат от това общо с напусне. Това се случва след това да каже "Спри, така или иначе? Да. Сега съм в моя нормален ред, и аз съм направено с помощта GDB. Като настрана, не е нужно да използвате тази TUI флаг. В действителност, ако сте го пропуснете, можете да получите по същество долната половина на екрана. Ако след това въведете почивка основната и след това изпълнете Все още мога да тичам моята програма, но това, което ще направим, е по-дословно просто ми покаже един ред в даден момент. -Туи, текстова потребителски интерфейс, просто ви показва повече на програмата наведнъж, което е може би по-малко концептуално по-лесно. Но наистина, аз може просто да направи следващото, следващото, следващото, и аз отивам да видя една линия в даден момент, и ако наистина искате да видите какво се случва Да въведете списък и да видим един куп на съседните линии. 

Има едно видео, което сме помоли да свалите проблем определя 3 , в която Нейт обхваща някои от тънкостите на GDB, и това е едно от онези неща, честно казано, когато някои нетривиално процент от вас никога не ще докосне GDB, и това ще бъде лошо нещо защото буквално ще се окажете прекарват повече време по-късно този семестър преследва грешки, тогава бихте ако в този половин час / час тази седмица и следващата живот, за да свикнете с GDB. ФОРМАТ ти беше приятел. GDB сега трябва да бъда твой приятел. 

Всякакви въпроси за GDB? И тук е бърз списък на някои от най-мощните и полезни команди. Да. >> Може ли да отпечатате низ? Може да печатате низ? Разбира се. То не трябва да бъде само числа. Ако една променлива е низ тип и в печатните. Той ще ви покаже какво низ променлива. [Чува студент] Тя ще ви даде адреса и самия низ. Тя ще ви покажа. И едно последно нещо, само защото те са добре да се знае също. Обратно проследяване и рамката, позволете ми да се потопите в този последен път, точно същата програма с GDB. Позволете ми да отида напред и да стартирате текстова версия на потребителския интерфейс, прекъсне основната. Позволете ми да отида напред и да се кандидатира отново. Тук съм. Сега ме пусна следващото, следващото, следващото, следващото, следващото, стъпка, въведете. 

И сега Предполагам, че сега съм в суап умишлено, но аз съм като: "По дяволите, какво е стойността на х? Не мога да направя х повече. Не мога да направя г., защото те не са в обхвата. Те не са в контекст, но няма проблем. Мога да пиша обратно проследяване. Това ми показва всички функции, които са изпълнени до този момент. Забележете, че един на дъното, основно, се изравни с главния на дъното на нашата снимка тук. Фактът, че суап е над него линии с суап е над него в паметта, и ако искам да се върнем към основната временно може да се каже, "рамка". Какъв брой? Майн е рамка # 1. Отивам да вървим напред и да каже: "кадър 1". 

Сега съм обратно в главния и мога да отпечатате х и мога да отпечатате г., но не мога да отпечатам или б. Но аз мога, ако кажа "Добре, чакай малко. Къде беше суап? Нека вървим напред и да каже "рамка 0". Сега съм обратно там, където искам да бъда и като настрана, има и други команди, като ако сте наистина става досадно пишете следващото, следващото, следващото, следващото, като цяло могат да казват неща като "следващите 10", и че ще се оттегли през следващите 10 линии. Можете също да напишете "продължава", когато наистина се хранят със засилване чрез нея. Продължете ще продължи програмата си без прекъсване, докато не намери друг точка на прекъсване, независимо дали е в цикъл или по-надолу във вашата програма. 

В този случай ще продължи до края, и програмата излезе нормално. Това е един луксозен начин, ниско процес. Просто програмата си излезе нормално. Повече за това във видеото и за отстраняване на грешки на сесии, за да дойде. Това е много. Да ни вземат 5-минутна почивка тук, и ние ще се върне с structs и файлове. 

Ако вече сте се гмурна в pset тази седмица вие ще знаете, че ние използваме в разпределението код, изходен код, който ние предлагаме за вас като отправна точка, някои нови техники. По-специално, ние въведохме тази нова ключова дума, наречена структура, структура, , така че ние можем да създадем персонализирани променливи на видове. Ние също така въвежда понятието на файла I / O, файл входа и на изхода, и това е така, че ние можем да спасим държавата на вашия Scramble съвет във файл на диск че преподавателските събратя и мога да разбера какво става вътрешността на вашата програма, без да се налага ръчно да играе десетки игри Scramble. Ние можем да направим това по-automatedly. 

Тази идея на структурата решава доста непреодолими проблема. Да предположим, че искаме да се приложат някои програма , че по някакъв начин следи на информация за студенти, и студенти могат да имат, например, ID, име и къща на място, като Харвард, така че това са три парчета информация искаме да запазим около, така че нека да вървим напред и започнете да пишете малка програма, включва stdio.h. Остави ме да включва cs50.h. И тогава започна моята основна функция. Аз няма да се занимавам с никакви аргументи на командния ред, и тук искам да има студент, така че аз ще да кажа студент има име, така че аз ще кажа "име низ." Тогава аз ще кажа един студент има ID, така че INT номер, и един студент има къща, така че аз също щях да кажа "къща низ." Тогава ще поръчате тези малко по-чисто, по този начин. Добре, сега имам три променливи, с които да представляват един студент, така че "студент". 

А сега искам да се пренесат тези стойности, така че нека да вървим напред и да кажа нещо подобно "ID = 123". Име ще се получи, Дейвид. Да кажем, че къщата ще се получи Mather, и тогава аз ще направя нещо произволно като ФОРМАТ ("% S, чието ID е% г, живее в% S. И сега, какво искам да включите тук, един след друг? Име, номер, къща връщането на 0. Добре, освен ако не съм прецакал някъде тук Мисля, че имаме доста добра програма, която съхранява един студент. Разбира се, това не е толкова интересно. Какво ще стане, ако искам да имам 2 студенти? Това не е голяма работа. Мога да издържам 2 души. Нека вървим напред и да се подчертае това и слизат тук, и мога да кажа "ID = 456" за някой като Роб, който живее в Къркланд. 

Добре, чакай, но не мога да наричам едно и също нещо, и изглежда, че ще се наложи да копирате, така че нека да кажа, че те ще бъдат променливи Дейвид, и ме остави някои копия от тези за Роб. Ние ги наричам Роб, но това няма да работят сега защото съм чакайте, нека ме промени ID1, NAME1 и house1. Роб ще бъде 2, 2. Трябва да променим това тук, тук, тук, тук, тук, тук. Чакай, какво да кажем за Томи? Нека го направим отново. Очевидно, ако все още мисля, че това е добър начин да се направи това, не е, така да копирате / поставите лошо. Но ние решен преди седмица. 

Какво е нашето решение, когато искахме да имаме няколко копия на един и същ тип данни? [Студенти] масив. Масив, така че нека се опита да почисти нещата. Нека направят някои стая за себе си в горната част, и нека да го правим това тук. Ще наричаме тези хора, и вместо това ще кажа "INT идентификатори" и аз ще подкрепи три от нас за сега. Отивам да се каже "струнни имена", и аз ще подкрепя три от нас, и тогава аз ще да каже "струнни къщи", и аз ще подкрепи три от нас. Сега тук вместо на Дейвид свои локални променливи можем да се отървем от тези. , Че се чувства добре, че ние сме почистване. След това мога да кажа, Дейвид ще бъде [0] и имената [0] и къщи [0]. И тогава Роб ние можем по същия начин, освен по този. Нека сложим това тук, така че той ще произволно документи за самоличност [1]. Той ще бъде имена [1], и след това накрая, къщи [1]. 

Все пак е малко досадно, а сега аз трябва да разбера това, така че нека кажем "имената [0], ID [0], къщи [0], и да работя по съвместителство това. Документи за самоличност, документи за самоличност, документи за самоличност. И отново, аз го правя, така че отново, аз вече съм се прибягва да копирате / поставите отново, така че шансовете са има друго решение. Вероятно мога да почистите от по-нататъшно с примка или нещо подобно, толкова по-кратко, това е малко по-добре, но все още се чувства като Аз съм се прибягва да копирате / поставите, но дори и това, аз твърдя, наистина не е фундаментално правилното решение, защото какво ще стане, ако по някое време решим знаеш ли какво? Ние наистина трябва да са съхраняване на имейл адресите за Дейвид и Роб и всички останали в тази програма. Ние също трябва да съхранявате телефонни номера. Ние също трябва да се съхранява спешни номера за контакт. Ние имаме всички тези данни, които искате да съхранявате, И така, как да отида за това? 

Вие декларирате, друг масив в горната част, и след това можете ръчно да добавите имейл адрес [0], имейл адрес [1] за Дейвид и Роб и така нататък. Но има наистина само предположение, в основата на този дизайн че аз съм с честта система, за да се знае, че [I] във всяка от няколко масиви просто така се случва да се отнасят до едно и също лице, [0] идентификатори е номер 123, и аз отивам да се предположи, че имената [0] е името на едно и също лице и къщи [0] е едно и също лице къщата и така нататък за всички на различните масиви, които създавам. Но забележете, че няма фундаментална връзка сред тези три парчета от информация, номер, име и къща, въпреки че то ние се опитваме да модел в тази програма не е масиви. Масивите са само в този програмен начин за това. Това, което наистина искаме да моделираме в нашата програма е лице като Давид, човек като Роб вътрешността на която или капсулиране е име и документ за самоличност и къща. 

Може ли по някакъв начин да изрази тази идея за капсулиране което човек има идентификационен номер, наименование и къща и не прибягвайте до наистина тази рана, при която ние просто вярвам, че нещо скоба се отнася за една и съща човешка лице във всяка от тези различни масиви? Ние действително можем да направим това. Нека отида горе основни за сега, и ми позволи да създам мой собствен тип данни за наистина първи път. Ние използвахме тази техника Scramble но тук аз ще да вървим напред и да се създаде тип данни, и знаете ли какво, аз отивам да го наричат ​​студент или лице, и аз ще използвам typedef за определяне на вида. Отивам да се каже, че това е структура, и след това тази структура да бъде от тип студент, ние ще кажем, въпреки че това е малко от сега за мен. Ще кажа "INT номер." Ще каже: "име низ." Тогава ние ще кажем "низ къща, така че сега до края на тези няколко реда код Току-що научи ехтя, че съществува тип данни, освен интеджър, освен струни, освен удвоява, освен плувки. 

Към този момент във времето линия 11, сега е налице нов тип данни, наречен студенти, и сега мога да декларирате променлива студент навсякъде, което искам, така че нека превъртете надолу до хората. Сега мога да се отърве от този, и мога да се върна на Давида, и за Дейвид всъщност мога да кажа, че Дейвид, ние можем буквално името на променливата след себе си, ще бъде от тип студент. Това може да изглежда малко странно, но това не е всичко, различно от обявяването на нещо като едно цяло число или низ или число с плаваща запетая. Просто така се случи да се нарича студент сега, и ако искам да сложите нещо вътре в тази структура Сега трябва да се използва нов образец на синтаксиса, но това е доста ясен, david.id = 123, david.name = "Давид" в столицата D и david.house = "Mather" и сега мога да се отърве от тези неща тук. Забележете, а сега сме с нов дизайн нашата програма наистина много по-добър начин че сега нашата програма е огледален образ на реалния свят. 

Има реалния свят идеята за едно лице или студент. Ето сега имаме версия на C на лице, или по-точно един студент. Вътре на това лице са тези съответните характеристики, ID, име и къщата, така че Роб същество става едно и също нещо тук, така студент Роб, а сега rob.id = 456, rob.name = "Роб." Фактът, че променливата се нарича Роб е нещо безсмислено. Бихме могли да го наричат ​​Х или У или Z. Ние просто го наричат ​​Роб да бъде семантично съответствие, но наистина името е вътре в самата областта така че сега имам това. Това също не се чувствам като най-добър дизайн в това, че съм твърд кодирани Дейвид. Съм твърд кодирани Роб. И аз все още трябва да се прибегне до някои копие и поставете всеки път, когато искам нови променливи. Освен това, очевидно трябва да даде възможност на всяка от тези променливи име, въпреки че аз предпочитам да опише тези променливи  по-генерично като студенти. 

Сега можем да се слеят идеи, които са работили добре за нас и вместо да каже: "Знаеш ли какво, дай ми променлива наречена студенти, и нека да бъде с размер 3 ", така че сега мога да усъвършенства тази, да се отървете от ръчно обявена Дейвид, Вместо това мога да кажа нещо подобно студенти [0] тук. След това мога да кажа, студенти [0] тук студенти [0], и така нататък, и мога да отида, около и почистете, че за Роб. Аз също може да стане сега може би добавяне на линия и използване на GetString и GetInt да се получи в действителност тези стойности от потребителя. Мога да отида за добавяне на константа, защото по принцип е лоша практика на твърдия код някакъв произволен брой, като 3 тук и след това просто не забравяйте, че трябва да се поставят не повече от три студенти в него. Тя вероятно ще бъде по-добре да се използва # определят в горната част на файла ми и факторът, че навън, така че наистина ме пусна напред и обобщи това. 

Нека се отвори един пример, който е сред днешните примери предварително, structs1. Това е една по-пълна програма, която използва # определят тук и казва, че ще има три студенти по подразбиране. Тук съм за обявяване на класа струва на студентите, така че класната стая на учениците, а сега аз съм с една линия само за да направят кода малко по-елегантен, попълване на класа с въвеждане на потребителя, така че от I = 0 превъртите до студенти, което е с 3. И тогава аз да подтикне потребителя в тази версия  това, което е на студента ID, и аз го с GetInt. Какво е името на студента, а след това го получите с GetString. Какво е къщата на студента? Разбирам с GetString. И тогава в долната част тук просто реших да се промени как съм отпечатване на тези и за реално използване на една линия, и кой съм аз печат? Според коментара аз печат никого в Mather, и това е така Роб и Томи и т.н. - всъщност Томи Mather. Томи и Давид ще бъдат отпечатани в този случай, но как се работи? Не сме виждали тази функция преди, но да предположите какво прави това. Сравнява низове. 

Това е малко не-очевиден как се сравнява низове, защото се оказва, ако го връща 0, това означава, че конците са равни. Ако го връща -1, това означава, че идва по азбучен ред преди другия, и ако той се връща една, това означава, че другата дума идва по азбучен ред преди другия, и можете да търсите онлайн или в мъжа страница , за да видите кои точно начин е, но всичко това се прави, е да казва ако [I]. Къщата е равна на "Mather" след което продължете напред и да разпечатате така и така е в Mather. Но тук е нещо, което не сте виждали преди, и ние ще се върнем към това. Аз не си спомням някога да направите това в някоя от програмите ми. Безплатно е очевидно, отнасящи се до паметта, освобождава памет, но какво памет съм очевидно освобождаване в тази линия в долната част на тази програма? Тя изглежда сякаш съм освобождава името на лицето и къща, но защо е това? 

Оказва се, всички тези седмици, които сте използвали GetString сме на въвеждане на бъг във всеки един от вашите програми. GetString дизайн заделя памет, така че да може да се върне да ви низ, като Давид, Роб, и след това можете да правите каквото си искате с този символен низ във вашата програма, защото ние сме запазени памет за вас. Проблемът е цялото това време всеки път, когато ти се обадя GetString ние, авторите на GetString, са били питам операционната система да ни даде малко RAM за този низ. Дайте ни малко RAM за следващия низ. Дайте ни малко повече RAM за следващия низ. Какво, програмист, никога не са били прави ни дава, че паметта обратно, така че за тези няколко седмици всички програми, които сте написали са имали това, което се нарича памет скок, при който те продължите да използвате все повече и повече памет всеки път, когато ти се обадя GetString, и това е добре. Ние съзнателно направи, че в първите седмици, защото това не е толкова интересно да трябва да се притеснявате за това къде низ идва от. Всичко, което искам, е думата Роб да се върне когато потребителят го видове инча 

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

Ще се върнем, когато и защо бихте се обаждате безплатно, но нека вървим напред точно за добра мярка и опитайте да стартирате тази конкретна програма. Това се нарича structs1, въведете. Нека вървим напред и стартирайте structs1, 123, Дейвид Mather, 456, Роб Kirkland, 789, Томи Mather, и ние виждаме Давид в Mather, Томи в Mather. Това е само малка проверка на здрав разум, че програмата се работи. Сега, за съжаление, тази програма е малко разочароващо в Направих всичко, че работата, аз напечатани в 9 различни низове, натиснете въведете, Казаха, който е бил в Mather, но очевидно знаеше кой вече е в Mather, защото аз го въвели. Това ще бъде най-малко хубаво, ако тази програма е по-скоро като база данни и тя действително се помни това, което сте въвели в така че никога не съм отново за въвеждане на тези студентски записи. Може би това е като registrarial система. 

Ние можем да направим това, като използвате тази техника, известна като файл I / O, файл входа и на изхода, много общ смисъл, че всеки път, когато искате да прочетете файлове или запис на файлове можете да направите това с определен набор от функции. Позволете ми да отида напред и да отворите този structs2.c например, , което е почти идентичен, но нека видим това, което сега прави. В началото на файла Декларирам клас на учениците. След попълване на класа с вход на потребителя, така че тези редове код са точно както преди. Тогава, ако превъртете надолу тук печатам всеки, който е в Mather произволно както преди, но това е една интересна нова функция. Тези редове код са нови, и те въвеждат нещо, Файл, всички капачки, и тя е * в тук, както и. Нека ме премести тук, * тук, както и. 

Тази функция не сме виждали преди, fopen, но това означава файла отворен, така че нека обезмаслено чрез тях, и това е нещо, което ние ще се върнем в бъдещите psets но тази линия тук по същество отваря файл, наречен база данни, и конкретно се отваря по такъв начин, че той може да направи това, което да го? [Чува студент] Добре, така че "w" просто означава, че казва на операционната система отвори този файл по такъв начин, че могат да пишат. Не искам да го прочетете. Не искам просто да го погледнете. Искам да го променят и добавят неща, евентуално да го и файлът ще се нарича база данни. Това може да се нарече нищо. Това може да бъде database.txt. Това би могло да бъде. Db. Това може да бъде една дума като Foo, но аз произволно избра да даде име на файла на базата данни. Това е малко проверка на здрав разум, че ще се върне в големи подробности с течение на времето, ,, ако РП, файлов указател не е равно на NULL, това означава, че всичко е наред. 

Дълга история Накратко, функции като fopen понякога не успяват. Може би файла не съществува. Може би сте от дисково пространство. Може би не е нужно разрешение за тази папка, така че ако fopen връща NULL нещо лошо се е случило. И обратното, ако fopen не се връща нула всичко е наред и аз да започнете да пишете в този файл. Ето един нов трик. Това е за цикъл, който итерации над всеки един от моите ученици, и това изглежда толкова сходни с това, което съм правил преди, но тази функция е братовчед на ФОРМАТ нарича fprintf за файла ФОРМАТ и да забележите, че е различно само два начина. Първо, тя започва с F вместо стр. но тогава първият аргумент е очевидно какво? [Студенти] файл. >> Това е файл. Това нещо, наречено РП, която в крайна сметка ще дразни, освен това, което е файлов указател, но за сега FP просто представлява файл, който сте отворили, fprintf тук се казва Печат ID този потребител към файла, а не на екрана. Печат потребителското име на файла, а не на екрана, къщата файла, а не на екрана, а след това тук, очевидно, затваряне на файла и след това тук безплатно памет. 

Единствената разлика между тази версия 2 и версия 1 е въвеждането на fopen и този файл с * и това понятие на fprintf, така че нека видим какво крайният резултат е. Нека отидем в моята терминален прозорец. Нека да structs2, въведете. Изглежда, че всичко е наред. Нека повторение structs2. 123, Дейвид Mather, 456, Роб Къркланд, 789, Томи Mather, въведете. Изглежда, че се държи една и съща, но ако аз сега правя ли забележите файл е тук сред всички си код, база данни, така че нека отворим, че Gedit на база данни, и погледнете. Това не е най-секси файлови формати. Това наистина е една част от тази линия на ред на ред, но тези от вас, които използват Excel или CSV файлове, разделени със запетая стойности, Аз със сигурност може да използва fprintf вместо това може би се направи нещо подобно така, че в действителност може да създаде еквивалент на Excel файл чрез отделяне на нещата със запетаи, а не само за нови линии. 

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

Това е за масив от знаци. Това е поредица от символи гръб до гръб. ПИСМА във всички капачки се случва да бъде произволно казват максималната дължина на всяка дума в речника, който използваме за катеря. Защо имам едно? Нулевата характер. Спомнете си, когато ние направихме например Bananagrams имаме нужда от специална стойност в края на думата, за да следите спецификация проблем в стаята, където думите действително е приключила, и като казва тук ние се комбинират с дадена дума булева стойност, флаг, така да се каже, вярно или невярно. Забелязали ли сте, тази дума вече, защото осъзнаваме, ние наистина се нуждаят от начин на спомняне, не само това, което думата е в Scramble но дали сте или не сте човека, го е намерил така че ако намерите думата "" не може просто да въведете, въведете, въведете, въведете и да получите три точки, три точки, три точки, три точки. Ние искаме да бъдем в състояние да черния списък, че дума по определяне на булев да е истина, ако вече сте го намерили, и така това е защо ние капсулирани в тази структура. 

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

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

Нека сега да видим защо сме се укрива тази подробност за известно време сега. Ето файл, наречен compare1.c, и той очевидно пита потребителя за две струни, и т, и след това той се опитва да се сравняват тези струни за равенство в ред 26, и ако те са равни, казва той, "сте написали едно и също нещо", и ако те не са равни се казва, "сте въвели различни неща." Позволете ми да отида напред и да стартирате тази програма. Нека отидем в моя източник директория, compare1. Го е съставило добре. Нека да compare1. Ще я увеличите, въведете. Кажи нещо. Здравейте. Аз ще кажа нещо отново. Здравейте. Аз определено не въвеждате различни неща. 

Нека да опитаме отново. Чао. Определено не е различно, така че това, което става тук? Е, какво наистина се сравняват по линия 26? [Чува студент] Да, така се оказва, че низ тип данни, е вид на бяла лъжа. Низ е знак *, но това, което е знак *? Знак *, както се казва, е указател, и показалеца е ефективно адрес, сума място в паметта, и ако се случи да сте въвели в една дума като HELLO, припомнят от последните обсъждания на струните това е като думата HELLO. Не забравяйте, че може да бъде представена една дума като HELLO като масив от знаци като този и след това със специален знак за край нарича нулев характер, \ участвали. Какво всъщност е низ? Забележете, че това е няколко парчета от паметта, и в действителност, в края на това е известен само веднъж погледнете през целия низ търси за специалния характер на нула. Но ако това е парче на паметта от паметта на компютъра ми, нека произволно се каже, че този низ просто имам късмет, и го поставя в самото начало на моя компютър RAM. Това е байт 0, 1, 2, 3, 4, 5, 6 ... 

Когато кажа нещо като GetString и правя низ = GetString какво всъщност се връщат? За тези последните няколко седмици, какво наистина се съхраняват в S не е този низ по себе си, но в този случай това, което се съхранява номер 0, защото какво всъщност прави GetString е не физически връща низ. Това дори не наистина да направят концептуален смисъл. Какво го прави завръщане е номер. Този брой е адреса на HELLO в паметта, и струнен и след това, ако ние кори обратно този слой, низ не съществува в действителност. Това е само опростяване в библиотеката CS50. 

Това наистина е нещо, което се нарича Чар *. Чар има смисъл, защото това, което е една дума, като HELLO? Е, това е поредица от символи, поредица от знаци. Чар * означава адреса на герой, така че това, което означава да се върне низ? Известен и лесен начин за връщане низ е по-скоро, отколкото се опитват да разбера как да се върна до пет или шест различни байта нека се върнат на адреса, от които байт? Първия. С други думи, нека да ви дам адреса на герой в паметта. Това е, което Чар * представлява адреса на един-единствен герой в паметта. Обадете се на тази променлива и. Се съхранява в този конкретен адрес, който произволно каза е 0, само за да запазим нещата прости, но в действителност тя е като цяло по-голям брой. 

Изчакайте една минута. Ако сте само ми дава адреса на първия знак, как мога да разбера какъв е адреса на втория знак, трето, четвърто и пето? [Чува студент] Трябва само знам къде края на низа е чрез този удобен трик, така че, когато използва нещо като ФОРМАТ, какво ФОРМАТ буквално като аргумент, припомним, че ние използваме контейнер% S, и след това да премине в променлива че съхраняване низ. Какво сте наистина преминаване е адресът на първия знак на тази струна. ФОРМАТ използва за линия или цикъл, докато при получаване на този адрес, например, 0, така че нека да направим това сега, ФОРМАТ ("% S \ N"); Когато аз наричам ФОРМАТ ("% S \ N"); това, което аз съм наистина предоставяне ФОРМАТ с е адресът на първия знак, който в тази произволна случай е H. 

Как ФОРМАТ знам какво точно да се показва на екрана? Лице, което изпълнява ФОРМАТ реализира докато линия или за контур казва, че този герой е равна на специалния характер нула? Ако не, да го отпечатате. Какво ще кажете за това? Ако не го отпечатате, да го отпечатате, да го отпечатате, да го отпечатате. О, това е нещо специално. Спре да печата и да се върнете на потребителя. И това е буквално всичко, което се случва под капака, и това е много да се извари в първия ден на класа, но за сега това е наистина градивен елемент на разбиране всичко , който е бил вътре в памет на нашия компютър, и в крайна сметка ние ще дразни това, освен с малко помощ от един от нашите приятели в Станфорд. 

Проф. Ник Parlante в Станфорд е направил тази прекрасна поредица видео от всички видове на различни езици, които въведоха тази малка Binky глинената анимация характер. Гласът сте на път да чуе само няколко секунди закрита прожекция е, че на Станфорд професор, и сте се сега само 5 или 6 секунди от това право, но това е бележката, на която ще сключи днес и да започне в сряда. Аз ви давам Pointer Fun с Бинки, за предварителен преглед. ♪ Music ♪] [професор Parlante] Хей, Бинки. Събуди се. Това е време, за показалеца забавно. Бинки] Какво е това? Научете повече за указатели? О, лакомство! 

Ще се видим в сряда. [CS50.TV]