[Powered by Google Translate] [Недела 4]
[Дејвид Џ Malan] [Универзитетот Харвард]
[Ова е CS50.] [CS50.TV]
>> Добро, ова е CS50, а тоа е почеток на недела 4,
и ова е една од најспоро можно сортирање алгоритми.
Кој беше дека ние само одвиваа таму?
Тоа беше меур вид, со цел голема О (n ^ 2) + сума,
и навистина не сме единствените на овој свет да изгледа да знаете
што меур вид е или трчање време.
Всушност, ова е интервју со Ерик Шмит на Google
и поранешниот сенатор Барак Обама само неколку години.
>> Сега, сенаторот, ти си тука во Google,
и сакам да мислам на претседателството како интервјуто за работа.
Сега, тоа е тешко да се добие работа како претседател, а ти си минува низ строги мерки сега.
Тоа е исто така тешко да се добие работа во Google.
Имаме прашања, а ние бараме нашите кандидати прашања,
и овој е од Лари Швимер.
Вие момци мислам дека сум шегуваш? Тоа е право тука.
Што е најефикасен начин да се најде еден милион 32-битни броеви?
[Смеа]
Добро
Жал ми е. >> Не, не, не, не.
Мислам дека меурот вид ќе биде погрешен начин да се оди.
>> Ајде, кој му рекол ова?
Минатата недела се потсетиме ние зеде пауза од кодот, барем за еден ден,
и почна да се фокусира на некои повисоко ниво идеи и решавање на проблемот со поопшто
во контекст на пребарување и подредување,
и ќе воведе нешто што ние не го завршиме ова име на минатата недела,
но асимптотска нотација, Биг О, Биг Омега,
а понекогаш и Биг Тита нотација, и тие беа едноставно начини
на опишување трчање време на алгоритми,
колку време е потребно за алгоритам да се кандидира.
>> И може да се потсетиме дека зборуваше за трчање време во однос на големината
на влез, која ние обично повик n, без оглед на проблемот може да биде,
каде n е бројот на луѓе во собата,
бројот на страници во книгата на телефонот, и почнавме да се напише работи надвор
како О (n ^ 2) или О (n) или О (n најавите л),
па дури и кога математика не сосема работат надвор толку совршено
и тоа беше n ² - n / 2 или нешто слично
ние би наместо само фрлаат во некој од пониските цел термини,
и мотивација таму е дека ние навистина сакаат
вид на објективен начин на оценување
извршување на програми или извршување на алгоритми
дека на крајот на денот нема ништо да се направи, на пример,
со брзината на вашиот компјутер денес.
>> На пример, ако се спроведе меур вид,
или да спроведе спојат вид или селекција вид на компјутер денес,
2 GHz компјутер, и да се стартува,
и тоа трае некои бројот на секунди, следната година има 3 GHz
или 4 GHz компјутер, и тогаш може да тврдат дека "Леле, ми алгоритам
е сега два пати толку брзо ", кога во реалноста тоа не е очигледно случајот.
Тоа е само хардвер има добивано и побрзо, но вашиот компјутер
не, и така ние навистина сакаме да се фрлаат работи како
множители на 2 или мултипли од 3 кога станува збор за опишување
колку брзо или колку е бавно алгоритам е и навистина само се фокусираат
на n или некои фактор од него,
некаква моќ од него, како и во случај на сорти од минатата недела.
И се потсетиме дека со помош на спојат вид
ние бевме во можност да го стори тоа многу подобро отколку меур сортирање и селекција вид
па дури и вметнување вид.
>> Ние се спушти до n најавите n, и повторно,
потсетиме дека најавите n генерално се однесува на нешто што расте
побавно тогаш n, па n најавите n досега беше добар
бидејќи тоа е помалку од n ².
Но, за да се постигне n најавите n со спојување вид
она што беше основна зародишот на идејата дека моравме да потпора
дека ние, исто така, балон назад во недела 0?
Како ја решавање на сортирање проблем умно со спојување вид?
Што беше клучна увид, можеби?
Секој на сите.
Океј, ајде да направиме чекор назад.
Опишете се спојат вид со свои зборови.
Како таа функционира?
Океј, ние ќе ред назад кон недела 0.
Океј, да.
[Нечујни-студент]
Океј, добро, па ние поделени низа на броеви во 2 парчиња.
Ние подредени секоја од овие парчиња, а потоа ние ги спојуваат,
и видовме оваа идеја пред земање на проблем кој е овој голем
и сечкање до тоа во проблем што е тоа големи или овој голем.
>> Да се ​​потсетиме на телефонот книга пример.
Да се ​​потсетиме само-броење алгоритам од пред неколку недели,
па се спојат вид беше инволвиран со оваа pseudocode тука.
Кога си даде n елементи, прво тоа беше разумност провери.
Ако n <2 тогаш не прават ништо на сите
бидејќи ако n <2 тогаш n е очигледно 0 или 1,
и така, ако тоа е или 0 или 1 нема ништо да го решите.
Ќе завршиш.
Вашата листа е веќе тривијално подредени.
Но инаку ако имаш 2 или повеќе елементи оди напред и да ги делат
во 2 дела, лево и десно.
Сортирање секоја од тие дела, а потоа се логирате на подредени половини.
Но, проблемот овде е дека на прв поглед ова изгледа како ние сме punting.
Ова е кружен дефиниција дека ако сум те праша за сортирање овие n елементи
и ти ќе ми кажеш "Добро, добро, ние ќе средиме оние n / 2 и оние n / 2 елементи"
тогаш мојата следна прашање ќе биде "Добро, како да ги сортирате n / 2 елементи?"
>> Но, поради структурата на оваа програма,
бидејќи таму е оваа база случај, така да се каже,
овој посебен случај кој се вели дека ако n е <некои фиксна вредност како 2 врати веднаш.
Не одговори со истата кружни одговор.
Овој процес, овој cyclicity на крајот ќе заврши.
Ако те прашувам "Сортирај овие n елементи", и ќе речете: "Добро, сортирање овие n / 2"
тогаш велат: "Добро, сортирање овие n / 4, N / 8, n/16"
на крајот ќе се подели со доволно голем број
дека ќе имаат само 1 елемент лево, на која точка може да се каже,
"Еве, тука е сортирани поединечен елемент."
Потоа брилијантноста на овој алгоритам се тука е да се изведе од фактот
дека откако ќе ги имаат сите овие поединечно подредени списоци,
од кои сите се од 1 големина, која се чини дека е бескорисно,
штом еднаш ќе почнете спојување нив и спојување нив
ќе се изгради до крај како Роб не во видео на конечно подредени листа.
>> Но, оваа идеја се протега многу подалеку сортирање.
Постои оваа идеја вградени во оваа програма позната како рекурзија,
идејата која сте програмата,
и да се реши некој проблем ќе се наречеш,
или стави во контекст на програмските јазици што се во функција,
и со цел да се реши еден проблем, можете функцијата се наречеш
повторно и повторно и повторно, но функцијата
не може да се јавите бесконечно многу пати.
На крајот ќе мора да дното, така да се каже,
и имаат некоја хард-кодирани база состојба во која се вели
во овој момент престанат да повикуваат себе, така што целиот процес
конечно се всушност запре.
Што значи тоа навистина значи, да recurse?
>> Ајде да видиме, ако можеме да направиме едноставна, тривијални пример, да речеме,
3 луѓе со мене се тука на сцена, ако некој е удобно.
1, ајде нагоре, 2 и 3.
Ако 3 сакате да излезе тука.
Ако сакате да застанат веднаш до мене тука во линија, да претпоставиме дека проблемот на дофат на раката
е многу тривијално брои бројот на луѓе кои се тука.
Но, искрено, јас сум уморна од сите овие броење примери.
Ова ќе потрае некое време, 1, 2 и точка, точка, точка.
Тоа ќе потрае засекогаш.
Претпочитам само залог овој проблем целосно со помош на-Што е вашето име?
Sara. >> Сара, во ред.
Кели. >> Кели и?
>> Willy. >> Вили, Сара, Кели и Вили.
Токму сега јас се поставува прашањето од страна на некој
колку луѓе се горе на оваа фаза, и јас немам идеја.
Ова е навистина долга листа, и така наместо Одам да го направите овој трик.
Одам да побара од лицето до мене да го направи најголемиот дел од работата,
и откако таа се прави прави најголемиот дел од работата
Одам да се направи најмалку износот на работа е можно и само додадете 1
за она што нејзиниот одговор е, па тука ќе одиме.
Сум бил праша колку луѓе се на сцената.
Колку луѓе се на сцената лево од вас?
Лево од мене? >> Океј, но не измамник.
Тоа е добро, тоа е точно, но ако сакаме да продолжи оваа логика
ајде да се претпостави дека слично сакате да залог овој проблем лево од вас,
па наместо одговор директно оди напред и само ја префрлуваат одговорноста.
О, колку луѓе се лево од мене?
Колку луѓе се на лево?
1.
[Смеа]
Океј, па 0, па што сега Вили има направено
е сте се вратија вашиот одговор оваа насока велејќи 0.
Сега, она што треба да направам? >> 1.
Океј, па ти си на 1, па велат: "Добро, јас ќе одам да додадете 1
на она брои Вили беше ", така 1 + 0.
Ти си сега 1 па вашиот одговор на правото е сега
1. >> И рудникот ќе биде 2.
Добро, па ти си преземање на претходниот одговор од 1,
додавање на минимална количина на работа што сакате да направите, што е 1.
Вие сега имате 2, и тогаш предаде мене што вредност?
3, мислам, жалам, 2.
Добро.
>> Па, имавме 0 налево.
Потоа имавме 1, а потоа ние додадете 2,
и сега сте ме предавање на број 2,
и така сакам да кажам дека, во ред, 1, 3.
Има навистина 3 народот што стои до мене на оваа фаза,
па ние би можеле да имаат очигледно направиле тоа многу линеарно,
многу во очигледен начин, но што ние навистина?
Ние ја проблемот на големина 3 на почетокот.
Ние тогаш тоа урна во проблем на големината 2,
тогаш проблемот на големина 1, а потоа конечно база случај
беше навистина, о, нема никој таму,
на која точка Вили врати ефективно хард-кодирани одговор на неколку пати,
а вториот беше тогаш клобуркаше до, клобуркаше до, клобуркаше до,
а потоа со додавање на овој еден дополнителен 1
ние сме спроведува оваа Основната идеја на рекурзија.
>> Сега, во овој случај тоа навистина не се реши проблемот
било поефикасно потоа видовме досега.
Но, мислам за на алгоритми ние го направивме на сцената досега.
Имавме 8 парчиња хартија на таблата,
на видео, кога Шон беше во потрага по бројот 7, и она што тој го навистина?
Па, тој не направи било каков вид на поделба и освојување.
Тој не направи било каков вид на рекурзија.
Наместо тоа, тој само го направи ова линеарни алгоритам.
Но кога ќе се претстави идејата на подредени броеви на сцената живеат минатата недела
тогаш имавме овој инстинкт да одат на средината,
на која точка имавме помал листа на големина од 4 или друга листа на големина 4,
а потоа имавме исти проблем, па ние се повторува, повторува, повторува.
Со други зборови, ние recursed.
Ви благодарам многу за нашите 3 волонтери тука за демонстрирање на рекурзијата со нас.
>> Ајде да видиме ако не можеме да го направи тоа сега малку поконкретни,
решавање на проблем кој повторно би можеле да направите многу лесно,
но ние ќе го користат како отскочна штица за спроведување на оваа основна идеја.
Ако сакам да се пресмета збирот на еден куп на броеви,
На пример, ако помине во број 3,
Сакам да ви даде вредност на сигма 3,
па збирот на 3 + 2 + 1 + 0.
Сакам да се вратам одговорот 6,
па ние ќе ја имплементираат оваа сигма функција, овој збир функција
кои, пак, се во влез, а потоа се враќа на собирање
на тој број на целиот пат на 0.
Ние би можеле да го направите ова прилично едноставно, нели?
Ние би можеле да го направите ова со некаков вид на looping структура,
па дозволете ми да оди напред и да се добие овој отворени.
>> Вклучуваат stdio.h.
Дозволете ми да се влезе во главната да работат со овде.
Да зачувате ова како sigma.c.
Тогаш јас ќе одам да си тука, и јас одам да се изјаснат за int n,
и јас одам да го направите следново додека корисникот не соработуваат.
Додека корисникот не ми даде позитивен број
дозволете ми да оди напред и да ги поттикнуваат за n = GetInt,
и дозволете ми да им даде некои инструкции како да што да направам,
па printf ("позитивен цел број молам").
Само нешто релативно едноставен вака, така што со време ние хит линија 14
сега имаме позитивен цел број се претпоставува дека во n.
>> Сега ајде да направиме нешто со него.
Дозволете ми да оди напред и да се пресмета збирот, па int сума = сигма (л).
Сигма е само собирање, па јас сум само да го пишува во познавач начин.
Ние само ќе го наречеме сигма таму.
Тоа е сума, и сега ќе одам да се печати резултатот,
printf ("Сумата е% d \ n", сума).
А потоа ќе се врати 0 за добра мерка.
Ние го направивме она што оваа програма бара освен интересен дел,
која е всушност да се спроведе сигма функција.
>> Дозволете ми да одат надолу тука до дното, и дозволете ми да прогласи функција сигма.
Тоа е мора да се земе променлива која е од тип integer,
и она што тип на податок сакам да се вратат веројатно од сигма?
Int, бидејќи сакам да одговара на моите очекувања on-line 15.
Тука дозволете ми да оди напред и да ја имплементираат оваа
во прилично недвосмислен начин.
>> Ајде да одиме напред и да каже int сума = 0,
и сега јас ќе одам да си имаат малку за телефонска линија тука
што се случува да се каже нешто како ова,
за (int i = 0; јас <= број; i + +) збирот + = i.
И тогаш ќе одам да се вратат сума.
Јас би можеле да имаат имплементирано овој во секој број на начини.
Јас може да се користат додека јамка.
Можев да прескокнат користење на збирот променлива ако јас навистина сакаше да,
но на кратко, ние едноставно имаат функција која ако јас не глупак изјавува сума е 0.
Тогаш тоа iterates од 0 на до преку број,
и на секоја итерација се додава дека сегашната вредност на збирот а потоа се враќа сума.
>> Сега, има мало оптимизација овде.
Ова е веројатно потроши чекор, но толку било да е тоа. Тоа е во ред за сега.
Ние сме најмалку се темелно и ќе 0 целиот пат на до.
Не е многу тешко и прилично јасна,
но излегува дека со функцијата сигма имаме иста можност
како што направивме тука на сцена.
На сцената ние само смета како многу луѓе беа до мене,
но наместо тоа, ако сакаме да се брои бројот 3 + 2 + 1
за одредување на 0 би можеле слично залог на функција
дека јас наместо ќе се опише како рекурзивен.
Еве нека се брзо разумност провери и бидете сигурни дека јас не глупак.
>> Знам дека барем една работа во оваа програма јас го правам погрешно.
Кога ќе притиснете ентер одам да се добие било каков вид на вика на мене?
Што сум јас ќе биде викна на тоа?
Да, јас заборавив на прототип, па јас сум со користење на функција наречена сигма на линија 15,
но тоа не е прогласен додека линија 22, па најдобро проактивно одат нагоре тука
и прогласи прототип, и јас ќе кажам int сигма (int број), и тоа е тоа.
Тоа е имплементиран на дното.
>> Или на друг начин би можел да се реши овој,
Можев да ја преместите функцијата до таму, што не е лошо,
но барем кога вашите програми почне да се долго, искрено,
Мислам дека има некои вредност во секогаш има главниот на врвот
така што ќе во читателот да ја отворам датотеката, а потоа веднаш ја видите
она што го прави програмата без да пребарувате низ тоа
гледа дека главната функција.
Ајде да одиме надолу за да ми терминален прозорец тука, обидете се прави сигма направи сигма,
и јас зезнав тука.
Имплицитна изјава на функцијата GetInt значи дека си заборавил да го направи она што друго?
[Нечујни-студент]
Добро, па очигледно честа грешка, па ајде стави ова овде горе,
cs50.h, а сега да се вратиме на мојот терминален прозорец.
>> Јас ќе го исчистите екранот, а јас ќе повторување направи сигма.
Се чини да се состави. А сега допуштете ми се кандидира сигма.
Ќе внесете го бројот 3, а јас не добиваат 6, па не ригорозни чек,
но барем тоа изгледа да се работи на прв поглед, но сега ајде да го рипувате, освен,
и ајде да всушност поткрепа на идејата за рекурзија, повторно,
во еден многу едноставен контекст, така што по неколку недели време
кога ќе започнете истражуваат познавач структури на податоци од низи
имаме уште една алатка во алатка со која ќе се
манипулира со овие структури на податоци како што ќе видиме.
Ова е итеративен пристап, јамка-базирани на пристап.
>> Дозволете ми, наместо сега го направите тоа.
Дозволете ми, наместо да се каже дека збирот на бројот
за одредување на 0 е навистина истото како
број + сигма (број - 1).
Со други зборови, како на сцената јас punted на секој од луѓето до мене,
и тие за возврат чуваат punting додека ние конечно дно на Вили,
кој мораше да се врати на хард-кодирани одговор како 0.
Еве сега ние сме слично punting да сигма
истата функција како што беше првобитно наречено, но клучот увид тука
е дека ние не сме повикувајќи сигма идентично.
Ние не сме поминува во n.
Ние сме јасно што минува во број - 1,
па малку помал проблем, малку помал проблем.
>> За жал, ова не е сосема решение сепак, и пред да го поправи
она што може да се скока надвор како што очигледно на некои од вас
дозволете ми да оди напред и повторување направи.
Се чини да се компајлира во ред.
Дозволете ми повторување сигма со 6.
Whoops, дозволете ми повторување сигма со 6.
Видовме и пред, иако случајно последен пат, како и.
Зошто да се добие оваа криптичната сегментација грешка? Да.
[Нечујни-студент]
Нема база случај, и поконкретно, што најверојатно се случило?
Ова е симптом на она однесување?
Велат дека тоа малку погласно.
[Нечујни-студент]
Тоа е бесконечна јамка ефикасно, и на проблемот со бесконечна петелки
кога тие подразбираат рекурзија во овој случај, функција која себеси се нарекува,
она што се случува секој пат кога ќе се јавите на функција?
Па, се сетам на тоа како ние изложени на меморијата во компјутерот.
Рековме дека е ова парче од меморија се нарекува конзола која е на дното,
и секој пат кога ќе се јавите на функција малку повеќе меморија добива стави
на овој т.н. магацинот содржат локални променливи таа функција или параметри,
па ако сигма повици сигма повици сигма повици сигма
повици сигма каде е оваа приказна крајот?
>> Па, на крајот пречекорување на вкупната сума
на меморија што имате на располагање на вашиот компјутер.
Можете лизгањето на сегментот што си требал да остане во рамките на,
и ќе го добиете овој сегментација грешка, основни фрлени,
и она јадро фрлени значи дека јас сега имаат фајл наречен јадро
која е датотека која содржи нули и единици
кои, всушност, во иднина ќе биде дијагностички корисни.
Ако тоа не е очигледно за вас, каде што вашиот бубачка е
вие всушност може да направи малку форензички анализи, така да се каже,
на ова јадро депонија датотека, која, пак, е само еден куп на оние кои и нули
што во суштина претставува државата на вашата програма во меморијата
моментот кога се урна на овој начин.
>> На фикс е дека не можеме само слепо се врати сигма,
бројот + сигма на малку помал проблем.
Ние треба да имаат некој вид на база случај тука,
и што треба основата случај веројатно да биде?
[Нечујни-студент]
Океј, па додека бројот е позитивен ние всушност треба да се врати ова,
или стави на друг начин, ако бројот е, да речеме, <= на 0
знаеш што, јас ќе одам напред и да се врати 0,
слично Вили направив, и друго, јас ќе одам да се оди напред
и да се врати ова, па тоа не е толку многу пократок
од повторната верзија која ние шлаг до првиот со помош на за телефонска линија,
но забележите дека има овој вид на елеганција на него.
Наместо да се врати одреден број и вршење на сето ова математика
и додавање на работите со локални променливи
сте наместо велејќи: "Океј, ако тоа е супер лесен проблем,
како број е <0, дозволете ми да веднаш се врати 0. "
>> Ние нема да се мачат поддршка негативни броеви,
па ќе одам на хард код вредноста на 0.
Но во спротивно, за спроведување на оваа идеја за собирање
сите овие броеви заедно ќе можат ефикасно да земе мал залак
од проблемот, како и многу направивме тука на сцена,
тогаш залог остатокот на проблемот на следната лице,
но во овој случај следниот лице себе.
Тоа е идентично име функција.
Само помине тоа помали и помали и помали проблем секој пат,
и иако не сме сосема формализиран работи во кодот тука
тоа е токму она што се случува во недела 0 со телефонот книга.
Ова е токму она што се случува во изминатите недели со Sean
и со нашите демонстрации од пребарувањето за броеви.
Тоа е преземање на проблемот и делење тоа повторно и повторно.
>> Со други зборови, постои начин сега на преведување
овој реалниот свет конструкција, ова високо ниво конструкција
на поделба и освојување и прави нешто повторно и повторно
во кодот, па ова е нешто што ќе видиме повторно во текот на времето.
Сега, како настрана, ако сте нови на рекурзијата ви треба барем да се разбере сега
зошто ова е смешно.
Одам да одат во google.com,
и јас одам да пребарувате за некои совети и трикови за рекурзија, влезе.
Кажете му на лицето до вас, ако тие не се смееја само сега.
Дали мислевте рекурзија?
Дали мислевте-ах, таму ќе одиме.
Океј, сега тоа е остатокот од секого.
А малку велигденско јајце вградени таму некаде во Google.
Како настрана, еден од линковите ќе стави на веб страната на курсот
за денес е само оваа мрежа на различни алгоритми за сортирање,
од кои некои ќе гледаше во минатата недела, но она што е убаво за оваа визуелизација
како што се обиде да ја заврши вашиот ум околу различни работи поврзани со алгоритми
знаете дека можете многу лесно сега да почне со различни типови на влезови.
Влезови сите спротивен, влезови главно подредени, влезови случаен и така натаму.
Како што се обидуваат да, повторно, се разликуваат овие работи во твојот ум
сфатат дека овој URL на веб страната на курсот на предавања страница
може да ви помогне причина преку некои од нив.
>> Денес ние конечно да се реши овој проблем од време назад,
кој беше дека оваа swap функција едноставно не работат,
и она што е фундаментален проблем со оваа функција, swap,
чија цел беше, пак, да се разменат вредност тука и тука
како што тоа се случи?
Ова всушност не работат. Зошто?
Да.
[Нечујни-студент]
Точно, објаснувањето за ова bugginess
едноставно е затоа што кога ќе се јавите функции во C
и тие функции се аргументи, како и б тука,
се поминува во примероци од она што вредност сте обезбедување на таа функција.
Вие не сте обезбедување на оригинални вредности себе,
па ние го виде тоа во контекст на buggyc,
buggy3.c, која изгледаше малку нешто како ова.
>> Потсетиме дека имавме x и y иницијализиран на 1 и 2, соодветно.
Ние тогаш отпечатени она што беа.
Јас тогаш тврдеше дека сум бил ги менуваат со повик трампа на x, y.
Но, проблемот беше дека Замена работел,
но само во рамките на swap самата функција.
Веднаш штом ќе го погоди линија 40 оние заменети вредности
беа фрлени, и така ништо
во оригиналната функција главната всушност менуваат на сите,
па ако мислите дека тогаш за тоа што ова изгледа како во однос на нашата меморија
ако ова левата страна на одборот претставува-
и јас ќе дадам се од себе за сите да видат ова-ако ова левата страна на таблата
претставува, да речеме, вашата RAM меморија и магацинот се случува да расте на на овој начин,
и ние го нарекуваме функција како главна, а главната има 2 локални променливи, x и y,
ајде да се опише оние што x тука, и ајде да се опише овие како y тука,
и да се стави во вредностите 1 и 2, така што ова тука е главен,
и кога главната повикува на swap функција на оперативниот систем
дава на swap функција свој откос на меморија на магацинот,
сопствената рамка на магацинот, така да се каже.
Таа, исто така издвојува 32 бита за овие ints.
Тоа се случува да ги нарекуваме А и Б, но тоа е сосема произволна.
Тоа би можело да ги повика она што сака, но што се случува кога главните
повици swap е потребно овој 1, става копија таму, го става копија таму.
>> Постои 1 друга локална променлива во трампа, иако, наречен што? >> Tmp.
Tmp, па дозволете ми да се даде уште 32 бита тука,
и она што го правам во оваа функција?
Реков int мали добива, па има 1, па јас направив ова кога последен пат играше со овој пример.
Тогаш добива б, па б е 2, па сега ова станува 2,
и сега б добива Temp, па температура е 1,
па сега б станува ова.
Тоа е одлично. Тој работел.
Но, тогаш штом функција враќа
меморија swap ефективно исчезнува, така што тоа може да се користи
од страна на некои други функција во иднина, а главната е очигледно целосно непроменет.
Ние треба начин на фундаментално решавање на овој проблем,
а денес ние конечно ќе имаат начин на тоа каде
ние може да се воведе нешто што се нарекува покажувач.
Излегува дека ние може да го реши овој проблем
не со донесување на копии на x и y
но наместо со полагање во она, мислите, на swap функција?
Да, она што за адреса?
Не сме навистина разговаравме за адреси во многу детали,
но ако оваа табла претставува меморија на компјутерот ми е
ние сигурно може да почни нумерирање на бајти во мојата меморија
и велат дека ова е бајт # 1, ова е бајт # 2, бајт # 3,
бајт # 4, бајт # ... 2 милијарди ако имам 2 гигабајти RAM меморија,
па ние секако може да излезе со некои произволни броеви шема
за сите индивидуални бајти во меморијата на компјутерот ми е.
>> Што ако наместо кога ќе се јавам swap
наместо помине во копии на x и y
зошто не можам наместо да помине во адресата на x тука,
адресата на y тука, во суштина поштенска адреса
на x и y, бидејќи тогаш трампа, ако тој е информиран
на адреса во меморијата на x и y,
тогаш трампа, ако ние го научиле малку,
тој би можел да вози на таа адреса, така да се каже,
x, и го промените бројот таму, тогаш се вози на адресата на y,
го промените бројот таму, дури и додека не всушност добивање копии на тие вредности себе,
па иако ние разговаравме за тоа како меморија главните е
и тоа како swap меморијата на моќни и опасни дел на C
е дека секоја функција може да го допре меморија насекаде во компјутерот,
и ова е моќен во тоа што можете да направите многу фенси работи со компјутерски програми во C.
Ова е опасно затоа што, исто така, може да ја зафркнам многу лесно.
Всушност, една од најчестите начини за програми, овие денови да се експлоатираат
уште е не е програмер да се реализира
дека тој или таа е дозволувајќи им на податоци
да бидат напишани на локација во меморијата која не беше наменето.
>> На пример, тој или таа изјавува низа на големина 10
но потоа случајно се обидува да стави 11 бајти во таа низа од меморија,
и ќе почнете допирање делови на меморија, која веќе не се валидни.
Само да контекстуални ова, некои од вас можеби знаат дека
софтвер често ќе побара сериски броеви или регистрација клучеви,
Photoshop и Word и програми како оваа.
Постојат пукнатини, како што некои од вас знаат, интернет каде што може да работи малку програма,
и Voila, не повеќе барање за серискиот број.
Како е тоа работа?
Во многу случаи овие работи се едноставно наоѓање на компјутери
текст сегменти во вистински нули на компјутерот и оние
каде е тоа функција каде што серискиот број се бара,
и ќе ги избрише тој простор, или додека на програмата се извршува
можете да дознаам каде што клучот е, всушност, чуваат
користење на нешто што се нарекува дебагерот, и можете да попуштат софтвер кој начин.
Ова не е да се каже дека ова е нашата цел за наредните неколку дена,
но има многу реални последици.
Дека еден се случува да се вклучат кражба на софтвер,
но исто така има компромис на целиот машини.
>> Всушност, кога веб-сајтови овие денови се експлоатирани
и компромитирани и податоци се протекоа и лозинки се украдени
Ова често се однесува на лошото управување на една меморија,
или, во случај на бази на податоци, неуспехот да се предвиди
контрамерки влез, па повеќе за тоа во неделите што доаѓаат,
но сега за сега само еден подлец преглед на вид на штета што можете да направите
од страна не е сосема разбирање на тоа како работите работа под хауба.
Ајде да одиме за разбирање зошто ова е скршен
со алатка која ќе станува повеќе и повеќе корисни
како нашите програми се посложени.
Досега кога сте имале грешка во вашата програма
како си помина за дебагирање тоа?
Што вашиот техники биле досега, без разлика дали подучени од вашиот ТФ
или само самоук?
[Студентски] Printf.
Printf, па printf веројатно е вашиот пријател во дека ако сакате да ја видите
она што се случува во внатрешноста на вашата програма
можете само да се printf тука, printf тука, printf тука.
Потоа да се стартува, и ќе добиете еден куп на работи на екранот
кои можете да ги користите за да потоа се заклучи што всушност се случува не е во ред во вашата програма.
>> Printf има тенденција да биде многу моќна работа,
но тоа е многу рачен процес.
Мора да се стави printf тука, printf тука,
и ако го стави во внатрешноста на јамка може да добие 100 линии
на излез што потоа треба да кваси преку.
Тоа не е многу лесен или интерактивни механизам за дебагирање програми,
но за среќа постои алтернатива.
Има програма, на пример, наречен GDB, на ГНУ дебагерот,
што е малку таинствени во тоа како да го користам.
Тоа е малку комплексна, но искрено,
ова е една од оние работи каде што ако се стави во оваа недела и следната
екстра час да се разбере нешто како GDB
тоа ќе те спаси веројатно десетици часови на долг рок,
па со тоа, дозволете ми да ви даде краток вовед за тоа како ова нешто работи.
>> Јас сум во мојата терминален прозорец.
Дозволете ми да оди напред и да ги собере на оваа програма, buggy3.
Тоа е веќе во тек.
Дозволете ми да го стартувате како што направивме некое време назад, и навистина, тоа е прекината.
Но, зошто е ова? Можеби и јас зезнав на swap функција.
Можеби тоа е a и b. Јас не сум сосема ќе ги движите наоколу правилно.
Дозволете ми да оди напред и да го направите тоа.
Наместо само стартувајте buggy3 дозволете ми наместо да ја извршите оваа програма GDB,
и јас одам да го кажам да се кандидира buggy3,
и јас одам да се вклучат во командната линија аргумент,-TUI,
и ние ќе го стави ова во иднина проблеми на спец да ги потсети.
И сега оваа црна и бела интерфејс појави кои, пак,
е малку огромна На прво затоа што има сето ова
гаранција информации долу тука, но барем има нешто познато.
Во врвот на прозорецот е мојот вистински код,
и ако дојдете до тука дозволете ми да дојдете до самиот врв на мојата датотека,
и навистина, има buggy3.c и известување на дното на овој прозорец
Имам GDB прашува.
>> Ова не е иста како и моите нормални Џон Харвард прашува.
Ова е предупредувањето што се случува да ми дозволат да се контролира gdb.
GDB е дебагерот.
А дебагерот е програма која ви овозможува да одиме преку
извршување на вашата програма линија по линија по линија,
на патот прави нешто што сакате на програмата,
дури и функции за повикување, или бараат, уште поважно,
на вредности различни променливата.
Ајде да одиме напред и да го направите тоа.
Одам да се оди напред и да напишеш во рок од брза GDB е,
така забележите во долниот лев агол на екранот Сум напишани работи,
и јас сум притиснете ентер, и што тоа го стори?
Тоа буквално трчаше мојата програма, но јас всушност не гледам многу одат на тука
бидејќи јас не се всушност изјави дебагерот
за да го паузирате во одреден момент во времето.
Само напишете рок работи на програмата.
Јас всушност не гледам ништо. Не можам да го манипулира.
>> Наместо тоа дозволете ми да го направите тоа.
Во овој GDB брза дозволете ми наместо внесете пауза, влезе.
Тоа не е она што мислев да напишеш.
Ајде наместо напишете пауза главните.
Со други зборови, сакам да се постави нешто што се нарекува точка на прекин,
која е во потполност наречен поради тоа што ќе се скрши или да се откажеш
извршување на својата програма на тоа конкретно место.
Главните е името на мојата функција.
Забележете дека GDB е прилично паметни.
Го сфатиле дека главната случува да се започне околу на линијата 18
на buggy3.c, а потоа се забележи тука во горниот лев
б + е веднаш до линијата 18.
Тоа ме потсетува дека јас постави точки на прекин на линијата 18.
Овој пат кога ќе напишете рок, ќе одам да се кандидира ми програмата
се додека не хитови кои точки на прекин,
па на програмата ќе испуштам за мене на линијата 18.
Еве ќе одиме, да го стартуваш.
Ништо не чини да се случи, но известување на долниот лев агол
почнувајќи програма, buggy3, точки на прекин 1 во главните во buggy3.c линија 18.
Што можам да направам сега?
>> Забележите можам да почнете да пишувате работи како печати,
не printf, печатење х, а сега тоа е чудно.
$ 1 е само љубопитност, како што ќе видиме
секој пат кога ќе печати нешто ќе добие нов $ вредност.
Тоа е така што ќе може да се однесува назад кон претходниот вредности само во случај,
но сега за сега тоа што печати се ми кажуваше е дека вредноста на x во овој момент во приказната
очигледно е 134.514.032.
Што? Каде што дури и доаѓаат од?
[Нечујни-студент]
Всушност, тоа е она што ние ќе го нарекуваат ѓубре вредност, а ние не сме разговарале за ова, сепак,
но причината што иницијализира променливи
е очигледно дека тие имаат некоја вредност кои сакате да ги имаат.
Но, за улов се потсетиме дека можете да декларираат променливи
како што го направив пред еден момент во мојот сигма пример
без всушност да им даде вредност.
Потсетиме она што го направив овде во сигма.
Јас прогласи n, но она што вредност не можев да го даде?
Никој, бидејќи знаев дека во следните неколку линии
GetInt ќе се грижи за проблемот за поставување на вредноста во внатрешноста на n.
>> Но, во овој момент во приказната на линијата 11
и линија 12 и линија 13 и линија 14
во текот на тие неколку линии она што е вредноста на n?
Во C едноставно не го знаат.
Тоа е генерално некои ѓубре вредност, некои сосема случаен број
што е лево над суштина од некои претходни функција
откако е подигнат, па како програма трча
потсетиме дека функцијата добива функција, функција, функција.
Сите овие рамки се стави на меморијата, а потоа тие функции враќање,
и како само јас сугерираше со гума нивната меморија е на крајот повторно да се користи.
Па, тоа само така се случува, дека оваа променлива x во оваа програма
се чини дека се содржани некои ѓубре вредност како 134514032
од некои претходни функција, не оној што го напишав.
Тоа може да биде нешто што доаѓа ефикасно со оперативниот систем,
некоја функција под хауба.
>> Океј, тоа е во ред, но ајде сега преминете на следната линија.
Ако јас типот "следниот" во мојата GDB брзо и јас притиснете ентер,
забележите дека истакнување движи надолу за да линија 19,
но логично импликација е дека линијата 18
сега заврши извршување, па ако јас повторно внесете "печати x"
Јас сега треба да видите 1, и навистина, го правам.
Повторно, $ нешта е начин на GDB ви потсетувајќи
што историјата на отпечатоци се дека сте го направиле.
Сега дозволете ми да оди напред и да испечатите y, и навистина, y е некои луди вредност, како и,
но не е голема работа, бидејќи во линија 19 ние сме за да се додели
на вредност 2, па да ми напишете "Напред" повторно.
И сега ние сме на printf линија.
Дозволете ми да се печати х.
Дозволете ми да се печати y. Искрено, јас сум добивање малку уморни за печатење ова.
Дозволете ми наместо напишете "дисплеј x" и "дисплеј y"
и сега секој пат кога ќе напишете команда во иднина
Јас ќе се потсети на она што е x и y, што е x и y, што е x и y.
>> Можам исто така, како настрана, тип во "инфо локалното население."
Информации е посебна команда.
Локалните жители значи дека ми го покажува локални променливи.
Само во случај да заборавам или ова е лудо, комплицирани функција
дека јас или некој друг пишува инфо локалното население ќе ти кажам
она што се сите на локални променливи во оваа локална функција
дека може да се грижи за ако сакате да ѕиркаат наоколу.
Сега, printf е за да се изврши, па дозволете ми да одиме напред и само типот "Напред".
Бидејќи ние сме во оваа средина ние не сме всушност го гледате
изврши долу тука, но се забележи станува малку искривени тука.
Но забележите тоа е највисок екран таму,
така што не е добра програма тука, но тоа е во ред затоа што секогаш може да ѕиркаат наоколу
користење на печати ако сакам.
>> Дозволете ми да напишеш следниот повторно, и сега тука е интересен дел.
Во овој момент во приказната y е 2, а x е 1,
како што е предложено тука, и повторно,
Причината е ова автоматски прикажување сега е затоа што се користат командата
дисплеј x и приказ y, па моментов напишете следниот
во теорија x и y треба да стане заменети.
Сега, ние веќе знаете дека нема да биде случај,
но ќе видиме во еден момент како можеме да се нурне подлабоко да дознаам зошто тоа е вистина.
Следно, и, за жал, y е уште 2 и x се уште е 1, и можам да потврдам колку.
Верзија за x, печатење y.
Навистина, не Замена всушност се случило, па да почнеме овој свет.
Јасно трампа е скршен.
Ајде наместо напишете "Run" повторно.
Дозволете ми да кажам да, сакам да го рестартирате од почетокот, внесете.
>> Сега сум назад на линијата 18.
Сега забележите x и y се ѓубре вредности повторно.
Потоа, следниот, следната, следниот.
Ако добијам досадно јас исто така да само тип N за следната.
Можете да го скратите да најкус можен секвенца од карактери.
Swap сега е скршен.
Ајде да се нурне во, па наместо на пишување следната,
сега ќе одам да напишеш чекор, така што јас повлекува во внатрешноста на оваа функција
така што можам да одат преку него, па јас хит чекор и потоа внесете.
Забележете дека истакнување скокови долу пониски во мојата програма на линија 36.
Сега што се локални променливи?
Информации локалното население.
Ништо не само уште, бидејќи ние не сме добиле таа линија,
па ајде да одиме напред и да каже "Напред".
Сега ние се чини дека имаат мали, печатење мали.
Ѓубре вредност, нели? Јас мислам така.
Како за печати, печатење б, 1 и 2?
Во еден момент, штом ќе напишете следниот повторно
мали се случува да се земе на вредноста на 1, се надевам,
бидејќи мали се случува да биде доделен на вредноста на.
>> Сега ајде да ги испечатите, печатење б,
но сега печати мали, а тоа е навистина 1.
Дозволете ми да направам следно. Дозволете ми да направам следно.
Сум завршил на swap функција.
Сè уште сум во него во согласност 40, па дозволете ми да се печати,
печати б, и не ми е грижа што tmp е.
Тоа изгледа како трампа е точно кога станува збор за замена на a и b.
Но, ако јас сега напишеш следниот, јас скок назад на линија 25,
и, се разбира, ако јас типот во x и печатење y
тие се уште непроменета, па ние не се поправија проблемот.
Но, дијагностички сега можеби со ова GDB програма
ние сме најмалку добивано и еден чекор поблиску до разбирање
што се случува погрешно, без да раѓа нашиот код со ставање на printf тука,
printf тука, printf тука и тогаш тоа работи повторно и повторно
се обидувам да дознаам што се случува погрешно.
>> Одам да се оди напред и да се откажат од овој целосно со откажам.
Тоа се случува да потоа каже: "Излези и покрај тоа?" Да.
Сега сум назад во мојата нормална линија, и јас сум се направи со користење gdb.
Како настрана, вие не треба да ја користите-TUI знаме.
Всушност, ако го изостави добиете суштина долниот дел на екранот.
Ако јас потоа внесете пауза главни и потоа стартувајте
Јас се уште може да ја стартувате мојата програма, но она што ќе направите, е повеќе текстуално
само ми го покаже тековната линија едно по едно време.
На-TUI, текстуалните кориснички интерфејс,
само покажува дека повеќе од програмата одеднаш, што е веројатно малку концептуално полесно.
Но, навистина, јас само може да го направи следниот, следната, следната,
и јас одам да ја видите една линија во време, и ако навистина сакаат да видат што се случува
Можам да пишувам листа и да видиме еден куп на соседните линии.
>> Има еден видео дека ние сме праша што ќе се види за проблемот поставува 3
во која Нејт опфаќа некои од сложността на GDB,
и ова е една од оние работи, искрено, каде што некои не-тривијални процент од вас
никогаш не ќе се смести GDB, а тоа ќе биде лоша работа
затоа што буквално ќе заврши поминува повеќе време подоцна овој семестар
си поигруваше со одредување грешки тогаш ќе ако се стави во таа половина час / час
оваа недела и следната учење да се чувствуваме удобно со gdb.
Printf е вашиот пријател.
GDB сега треба да ти биде пријател.
>> Било какви прашања на GDB?
И тука е брз листа на некои од најмоќните и корисни команди.
Да. >> Можете да печатите низа?
Можете да печатите низа? Апсолутно.
Тоа не мора да биде само цели броеви.
Ако променливата е е стринг само напишете во печатените s.
Таа ќе ви покаже она што стринг променлива е.
[Нечујни-студент]
Тоа ќе ви даде адресата и низа себе.
Таа ќе ви покаже и двете.
И едно последно нешто, само затоа што тие се добри да се знае премногу.
Трагата и рамка, дозволете ми да се нурне во овој последен пат,
исто точно програма со gdb.
Дозволете ми да оди напред и да ја стартувате на текстуалната кориснички интерфејс верзија,
скрши главните.
Дозволете ми да оди напред и да се кандидира повторно. Тука сум.
Сега дозволете ми да одам наредната, следниот, следната, следниот, следната, чекор, внесете.
>> А сега да претпоставиме дека сум сега во размена намерно, но јас сум како "По ѓаволите, што е вредноста на x?"
Не можам х повеќе.
Не можам y бидејќи тие не се во опсегот.
Тие не се во контекст, но нема проблем.
Можам да пишувам трагата.
Тоа ми покажува сите функции кои се извршуваат до овој момент во времето.
Забележете дека еден на дното, главно, линии со главните
да биде на дното на нашата слика тука.
Фактот дека трампа е над неа линии со трампа биде над неа во меморијата тука,
и ако сакам да се вратам на главната привремено можам да кажам "рамка."
Што број? Главните е рамка # 1.
Одам да се оди напред и да каже "рамка 1."
>> Сега сум назад во главната, и можам да печати x, и можам да печати y,
но не можам да се печати или б.
Но, можам да ако кажам: "Океј, почекајте една минута. Каде беше на swap?"
Дозволете ми да оди напред и да каже "рамка 0."
Сега сум повторно таму каде што сакате да биде, и како настрана,
има други команди премногу, како ако сте навистина станува досадно пишување следниот, следната, следниот, следната,
генерално може да се каже нешто како "следните 10", и дека ќе ја засили преку следните 10 линии.
Исто така можете да напишете "продолжи" кога навистина се хранат со излегувајќи низ него.
Продолжи ќе се кандидира на вашиот програма, без прекин, додека таа хитови друга точка на прекин,
дали во јамка или спуштаат во вашата програма.
>> Во овој случај ние продолжи до крајот, а програмата излезено нормално.
Ова е фенси начин инфериорни процес.
Само вашата програма излезено нормално.
Повеќе за тоа во видеото и дебагирање сесии за да дојде.
Тоа беше многу.
Да го земеме нашите 5-минутна пауза тука, а ние ќе се вратат со structs и датотеки.
>> Ако имате нурна во pset оваа недела веќе
ќе знаеш дека ние ги користиме во дистрибуцијата код,
изворниот код што ги нудиме на вас, како појдовна точка, некои нови техники.
Конкретно, ние воведе оваа нова клучен збор наречен struct, за структурата,
така што можеме да креираш кориснички променливи на сорти.
Ние, исто така, воведе поимот на датотека I / O, датотеката влез и излез,
и ова е така што можеме да го спаси државата
на вашиот трка одбор на датотека на диск
така што наставата другарите и можам да ги разберам
она што се случува во внатрешноста на вашата програма, без рачно да играат
десетици пријателите трка.
Ние можеме да правиме ова повеќе automatedly.
>> Оваа идеја на struct решава прилично релевантни проблем.
Да претпоставиме дека сакаме да се имплементираат некои програмата
дека некако следи на информации за студентите,
и студентите би можеле да имаат, на пример, лична карта, име
и куќа во место како Харвард, па овие се 3 парчиња информации
ние сакаме да се задржи околу, па дозволете ми да оди напред и да почнете да пишувате малку програма тука,
вклучуваат stdio.h.
Дозволете ми да се направи вклучуваат cs50.h.
А потоа започнете мојата главна функција.
Јас нема да се мачат со било командната линија аргументи,
и тука сакам да имам еден студент, па ќе одам да се каже
студентот има име, па ќе одам да се каже "стринг име."
Потоа јас ќе одам да се каже студент, исто така, има лична карта, па int id,
и студентот има една куќа, па јас сум исто така, ќе кажат "стринг куќа."
Тогаш јас ќе нареди овие малку повеќе демонтирани се допаѓа ова.
Океј, сега имам 3 променливи со која треба да претставува еден студент, па "студент".
>> И сега сакам да се доверат овие вредности, па дозволете ми да оди напред и да кажете нешто како
"Id = 123."
Името ќе добие Давид.
Да речеме дека куќата се случува да се Mather,
а потоа јас ќе одам да направите нешто произволно како printf ("% s,
чиј број е% d, живее во% s.
И сега, она што сакам да го приклучиш во тука, едно по друго?
Име, ID, куќа, враќање 0.
Океј, ако јас зезнав тука некаде
Мислам дека имаме доста добра програма која ги зачувува еден студент.
Се разбира, ова не е за сите што интересно. Што ако сакам да имам 2 ученици?
Тоа не е голема работа. Јас може да го поддржи 2 луѓе.
Дозволете ми да оди напред и да ја нагласи ова и оди надолу тука,
и можам да кажам "id = 456" за некој како Роб кој живее во Киркланд.
>> Океј, чекај, но не можам да го нарекуваме овие истото,
и тоа изгледа како да сум ќе мора да ја копирате на оваа,
па дозволете ми да кажам дека тие ќе бидат променливи Давид,
и дозволете ми да се добијат некои копии од овие за заведување.
Ние ќе го нарекуваме овие на Rob но ова не е оди на работа сега
бидејќи имам-чекај, да ме промени да id1, name1 и house1.
Роб ќе биде 2, 2.
Морам да го промените ова тука, тука, тука, тука, тука, тука.
Чекај, што за Томи? Да го направите ова повторно.
Очигледно ако сеуште мислите дека ова е добар начин да се направи ова, не е,
па копирај / вметни лошо.
Но, ние се реши ова пред една недела.
>> Она што беше нашето решение кога сакавме да имаат повеќе инстанци од иста тип на податок?
[Студентите] низа.
Низа, па дозволете ми да се обиде да го исчисти ова.
Дозволете ми да се направи некои соба за себе на врвот, и дозволете ми наместо направите тоа тука.
Ние ќе го наречеме овие луѓе, и наместо тоа, ќе одам да се каже "int ИД"
и јас одам да го поддржи 3 од нас сега за сега.
Одам да се каже "стринг имиња", а јас ќе ја поддржам 3 од нас,
а потоа јас ќе одам да се каже "стринг куќи", а јас одам да го поддржи 3 од нас.
Сега тука, наместо на Дејвид добива својот локални променливи
можеме да се ослободиме од нив.
Дека се чувствува добро, дека ние сме чистење ова.
Јас тогаш може да се каже Дејвид ќе биде [0] и имиња [0]
и куќи [0].
А потоа Роб ние слично може да се спаси за ова.
Да се ​​стави ова овде долу, па тој се случува да произволно да биде ИД [1].
Тој ќе биде имиња [1],
а потоа на крај, куќи [1].
>> Уште малку досадни, и сега морам да дознаам ова,
па да речеме "имиња [0], проект [0], куќи [0],
и ајде да pluralize ова.
ИД, ИД, ИД.
И повторно, јас сум го прави тоа, па повторно, јас сум веќе прибегнување кон копирање / вметнување повторно,
па шансите се има друго решение овде.
Јас веројатно може да се исчисти овој горе понатаму со јамка или нешто слично,
Значи во кратки, тоа е малку подобро, но сеуште се чувствува како
Јас сум прибегнување кон copy / paste, но дури и тоа, тврдам,
навистина не е фундаментално право решение, бидејќи
што ако некогаш се одлучи знаеш што?
Ние навистина треба да се складирање на е-мејл адреси за Давид и Роб
и секој друг во оваа програма.
Ние, исто така, треба да ги чувате телефонски броеви.
Ние, исто така, треба да чува итни броеви за контакт.
Ние ги имаат сите овие делови на податоци што сакате да го зачувате,
Па, како да одите за тоа го прават?
>> Вие декларирате друга низа на врвот, а потоа можете рачно да додадете
е-маил адреса [0], е-мејл адреса [1]
за Давид и Роб и така натаму.
Но, има навистина само претпоставка основните овој дизајн
дека јас сум со користење на чест систем да се знае дека
[I] во секоја од неколку низи
само така се случува да се однесуваат на истото лице,
па [0] во IDS е бројот 123,
и јас одам да се претпостави дека имињата [0]
е иста личност име и куќи [0]
е куќата на истиот човек и така натаму за сите различни низи што ја создавам.
Но, забележуваат дека нема основни поврзување
меѓу оние 3 парчиња информации, ID, назив и куќа,
иако субјектот ние се обидуваме да модел во оваа програма не е низи.
Низи се само оваа програмска начин за тоа.
Што ние навистина сакаме да се моделира во нашата програма е личност
како Давид, едно лице како Роб внатрешноста на кој
или концизирајќи е име и идентификација и куќа.
>> Можеме некако изразат оваа идеја на херметичка
при што едно лице има лична карта, име и куќа
а не да се впуштат во навистина овој hack при што ние само
верувам дека заградата нешто
се однесува на ист човечки субјект во секоја од овие различни низи?
Ние всушност може да го направите тоа.
Дозволете ми да одат над главната сега за сега, и дозволете ми да се создаде мојата тип на податоци
за навистина прв пат.
Ние се користи оваа техника во трка,
но тука јас ќе одам да се оди напред и да се создаде тип на податоци,
и знаеш што, јас одам да го наречеме студент или лице,
и јас одам да се користи typedef за дефинирање на видот.
Одам да се каже дека ова е една структура,
а потоа оваа структура ќе биде од типот студент, ќе кажам,
иако тоа е малку датиран сега за мене.
Ние ќе каже "int id."
Ние ќе каже "стринг име."
Тогаш ние ќе каже "стринг куќа"
па сега до крајот на овие неколку линии на код
Имам само учи ѕвекот дека постои
податочен тип покрај ints, покрај жици, покрај двојки, покрај плови.
>> Од овој момент во времето линија 11, таму сега е нов тип на податоци се нарекува студенти,
и сега може да прогласи студент променлива насекаде сакам,
па дозволете ми да дојдете тука на луѓето.
Сега можам да се ослободи од ова, и јас да се вратиш до Дејвид тука,
и за Дејвид јас всушност може да се каже дека Давид,
ние буквално да го името на променливата по себе,
ќе биде од типот студент.
Ова може да изгледа малку чудно, но тоа не е сите што се разликува
од прогласување нешто како int или стринг или плови.
Тоа само така се случува да се нарекува студент сега,
и ако сакам да се стави нешто во внатрешноста на оваа структура
Јас сега треба да се користи нова фигура на синтаксата, но тоа е прилично јасна,
david.id = 123, david.name = "Давид" во главниот град D,
и david.house = "Mather"
и сега можам да се ослободи од овие работи тука.
ИЗВЕСТУВАЊЕ сега сме редизајнирана нашата програма во навистина многу подобар начин
во која сега нашата програма одразува реалниот свет.
>> Има реалниот свет идејата за човек или студент.
Тука имаме сега една верзија Ц на некое лице или поконкретно студент.
Внатрешноста на тоа лице се овие релевантни карактеристики,
Проект, име и куќа, па Роб суштина станува истото тука долу,
така студент ограбуваат, и сега rob.id = 456,
rob.name = "Роб".
Фактот дека променливата се вика Роб е вид на бесмислени.
Ние би можеле да се нарече x или y или z.
Ние само ја нарекол Роб да биде семантички конзистентно,
но, навистина името е внатре во тоа поле себе,
па сега имам ова.
Тоа исто така не се чувствува како најдобар дизајн во тоа дека јас сум хард кодирани Давид.
Сум хард кодирани Роб.
И јас се уште треба да се прибегне кон некои копирајте го и ставете секој пат кога ќе сакате нови променливи.
Покрај тоа, морам да очигледно им даде на секоја од овие променливи име,
иако јас многу повеќе би сакал да се опише овие променливи
повеќе генерички како студенти.
>> Сега можеме да се логирате на идеите кои се работат добро за нас
и наместо да се каже, "Знаете што, дај ми променлива наречена студенти,
и нека таа да биде со големина од 3 ", па сега можам да насочите ова понатаму,
се ослободи од рачно прогласи Давид,
и јас наместо да кажете нешто како студенти [0] тука.
Јас тогаш може да се каже студенти [0] тука,
студенти [0] тука, и така натаму, и јас да оди наоколу
и исчистете дека за заведување.
Јас, исто така може да се обратите за сега можеби додавајќи јамка
и користење на GetString и GetInt да всушност овие вредности од корисникот.
Јас би можеле да одат за додавање на постојана бидејќи ова е генерално лоша пракса
на хард код некои произволни број како 3 токму тука
а потоа само се сеќавам дека треба да се стави повеќе од 3 ученици во неа.
Тоа најверојатно ќе биде подобро да се користи # define на врвот на мојата датотека
и фактор кој надвор, па навистина, дозволете ми да оди напред и да се генерализира ова.
>> Дозволете ми да се отвори еден пример дека е меѓу денешните
примери во однапред, structs1.
Ова е повеќе комплетна програма која користи # define се тука
и вели дека ние ќе имаме 3 ученици од стандардните.
Еве јас сум прогласување класа во вредност од студентите,
па училницата на учениците, а сега сум со користење на јамка
само за да го кодот малку повеќе домот, се доверат на класа
со внесување на корисникот, така iterate на од i = 0 до студенти, што е 3.
И тогаш го извести корисникот во оваа верзија
она што е идентитетот на студентот, и јас го добиете со GetInt.
Што е името на студентот, а потоа да се добие со GetString.
Што е куќата на ученикот? Јас го добие со GetString.
А потоа на дното тука јас само одлучи да го промени
како јас сум печатење овие надвор и да всушност употреба на телефонска линија,
и кој сум јас печатење?
Според коментар сум печатење некој во Mather,
и тоа е тоа така Роб и Томи и така натаму-всушност Томи во Mather.
Томи и Дејвид ќе бидат испечатени во овој случај, но како е ова работа?
Не сме виделе оваа функција пред тоа, но се погоди тоа што ова го прави тоа.
Споредува жици.
>> Тоа е малку не-очигледно како тоа се споредува жици, бидејќи излегува
ако го враќа 0 тоа значи дека конците се еднакви.
Ако го враќа -1 што значи дека еден доаѓа по азбучен ред пред другите,
и ако го враќа 1 тоа значи дека друг збор доаѓа по азбучен ред
пред други, и може да се погледне на интернет или во човек страница
да се види точно кој начин е кој, но сето тоа сега го прават е тоа велејќи
ако [i]. куќа е еднаква на "Mather"
па ќе одиме напред и печатење, па и така е во Mather.
Но, тука е нешто што не сме виделе порано, а ние ќе се вратам на тоа.
Јас не се сеќавам воопшто да треба да го направите ова во било кој од моите програми.
Слободен е очигледно мислејќи на меморија, ослободувајќи меморија,
но она што меморијата сум јас очигледно ослободување во овој циклус на дното на оваа програма?
Изгледа како да сум ослободувајќи името на лицето
и куќата на една личност, но зошто е тоа така?
>> Излегува сите овие недели дека сте биле со GetString
ние сме вид на е воведување на бубачка во секој еден од вашите програми.
GetString од страна на дизајнот доделува меморија, така што тоа може да се врати да ви стринг,
како Давид, или Роб, и тогаш може да правите што сакате
со тоа стринг во вашата програма, бидејќи ние сме се задржани меморијата за вас.
Проблемот е сето ова време секој пат кога ќе се јавите GetString
ние, авторите на GetString, се бара од оперативниот систем
да ни даде малку RAM меморија за овој стринг.
Дајте ни малку RAM меморија за следниот стринг.
Ни даде некои повеќе RAM меморија за следниот стринг.
Што ви, програмер, никогаш не се прави
ни дава дека меморијата назад,
па за овие неколку недели на сите програми што сум напишал
имале она што се нарекува меморија скок при што тие ги користат
се повеќе и повеќе меморија секој пат кога ќе се јавите GetString, и тоа е добро.
Ние намерно го направи тоа во првите недели поради тоа што не е толку интересен
да мора да се грижите за тоа каде стринг е што доаѓаат од.
Сите што го сакате е зборот Роб да се врати кога корисникот ќе ја типови внатре
>> Но се движи напред ние сега треба да започне да добива повеќе софистицирани за ова.
Секое време ние алоцира меморија подобро на крајот ја предаде назад.
Инаку во реалниот свет на вашиот Mac или PC може да имате повремено искусни
симптоми каде што вашиот компјутер е мелење до застој конечно
или глупави предење плажа топката е само окупаторската на компјутерот
целата внимание и не можете да се прават работите.
Тоа може да се објасни со кој било број на грешки, но меѓу оние можни грешки
се работи вика меморија протекување при некој кој напиша дека парче софтвер
сте користење не заборавајте да ослободите меморија
дека тој или таа побара од оперативниот систем за,
не се користи GetString, бидејќи тоа е CS50 работа, но со користење на слични функции
кои бараат оперативниот систем за меморија.
Ако вие или тие ја зафркнам и всушност никогаш не се врати таа меморија
симптом на која може да биде дека програмата се забавува и го забавува и го успорува
освен ако не се сеќавам да се јавите бесплатно.
>> Ќе се врати кога и зошто ќе се јавите бесплатно,
но, ајде да одиме напред само за добра мерка и пробајте да ја отворите оваа конкретна програма.
Ова беше наречен structs1, внесете.
Дозволете ми да оди напред и да ја стартувате structs1, 123, Дејвид Mather,
456, Роб Киркланд, 789,
Томи Mather, и можеме да видиме на David во Mather, Томи во Mather.
Ова е само малку здрав разум Проверете дека е програмата е работа.
Сега, за жал, оваа програма е малку фрустрирачки во таа
Јас не сите кои работат, јас ја внеле во 9 различни жици, притиснете ентер,
беше кажано кој беше во Mather, но очигледно јас знаев кој беше во Mather веќе затоа што го напишавте.
Тоа би било барем убаво ако оваа програма е повеќе како база на податоци
а тоа всушност се сеќава на она што го внесе во
па јас никогаш не повторно треба да го внесете овие студент евиденција.
Можеби тоа е како registrarial систем.
>> Ние можеме да го направите тоа користејќи оваа техника позната како датотека I / O, датотеката влез и излез,
многу генерички начин на велејќи дека секој пат кога ќе сакате да го прочитате датотеки или да пишува датотеки
можете да го направите ова со одреден сет на функции.
Дозволете ми да оди напред и да се отвори овој пример structs2.c,
што е речиси идентични, но ајде да видиме што тоа сега го прави тоа.
На врвот на датотеката Изјавувам класа на студентите.
Јас тогаш се доверат на класа со внесување на корисникот,
па оние линии на код се исто како и пред тоа.
Потоа, ако дојдете тука јас печати секој кој е во Mather произволно како порано,
но ова е интересна нова функција.
Овие линии на код се нови, и тие се воведе нешто тука,
Датотека, сите капи, и има * во и тука.
Дозволете ми да се помести ова овде, a * овде, како и.
>> Оваа функција не сме виделе порано, fopen,
но тоа значи отварање датотека, па ајде обезмаслен преку нив,
и ова е нешто што ќе се врати во иднина psets,
но оваа линија тука суштина отвора фајл наречен база на податоци,
и тоа посебно се отвора во таков начин што тоа може да го направи она што со неа?
[Нечујни-студент]
Право, па "W" едноставно значи тоа кажува на оперативниот систем
ја отворите оваа датотека на таков начин што ќе можам да пишува на него.
Не сакам да го прочита. Не сакам само да се погледне во него.
Сакам да го промени и да додадете нешто потенцијално да го,
и датотеката ќе биде наречена база на податоци.
Ова би можело да се нарече нешто.
Ова може да биде database.txt. Ова би можело да биде. DB.
Ова би можело да биде еден збор, како foo, но јас произволно избра за името на датотеката база на податоци.
Ова е малку здрав разум проверка дека ќе се врати во големи детали текот на времето,
ако РП, за датотеката покажувач, не еднакви NULL тоа значи дека сите е добро.
>> Скратам приказната, функции како fopen понекогаш не успеваат.
Можеби датотеката не постои. Можеби сте надвор од диск простор.
Можеби немате дозвола да таа папка,
па ако fopen враќа null нешто лошо се случило.
Спротивно на тоа, ако fopen не врати null се е во ред
и јас да почнете со пишување на оваа датотека.
Еве еден нов трик.
Ова е за телефонска линија што е процесирањето над секој од моите студенти,
и тоа изгледа толку слична на она што ние го направивме досега,
но оваа функција е братучед на printf наречен fprintf за датотеката printf,
и ќе забележите тоа е различно во само 2 начини.
Еден, тоа почнува со f наместо p,
но тогаш неговата Првиот аргумент е очигледно што?
[Студентите] датотеката. >> Тоа е датотека.
Ова нешто што се нарекува РП, кои на крајот ќе разграничат каква датотека покажувачот е,
но сега за сега РП едноставно претставува датотека која се отвори,
па fprintf тука е велејќи печати број на овој корисник на датотека, не на екранот.
Печати името на корисникот на датотека, не на екранот,
куќата на датотека, не на екранот, а потоа тука долу, очигледно,
затвори датотека, а потоа надолу тука ослободи меморија.
>> Единствената разлика помеѓу оваа верзија 2 и верзија 1
е воведувањето на fopen и оваа датотека со *
и ова сфаќање на fprintf, па ајде да видиме што крајниот резултат е.
Дозволете ми да одам во мојата терминален прозорец.
Дозволете ми да се кандидира structs2, внесете.
Изгледа сите е добро. Да повторување structs2.
123, Дејвид Mather, 456, Роб Киркланд,
789, Томи Mather, внесете.
Изгледа дека се однесувал на ист, но ако јас сега прават ls
забележи она што датотеката е тука меѓу сите мојот код, база на податоци,
па ајде отвори таа, gedit на базата на податоци, и да бараат во тоа.
Тоа не е најсекси на формати на датотеки.
Тоа навистина е едно парче на податоци линија по линија по линија,
но оние од вас кои го користите Excel или CSV датотеки, одделени со запирки вредности,
Јас секако може да се користат fprintf да наместо можеби направи вакво нешто
така што јас всушност би можеле да се создаде еквивалент на Excel датотеката
со одвојување работи со запирки, а не само нови линии.
>> Во овој случај, ако имав наместо користи запирки наместо на нови линии
Јас буквално може да ја отворите оваа база на податоци датотека во Excel, ако наместо направи да изгледа вака.
На кратко, сега имаме моќ да пишуваат на датотеки
ние сега може да почне постојаниот податоци, имајќи го околу на диск
така што можеме да го задржи информации околу повторно и повторно.
Забележите неколку други работи кои се сега малку повеќе запознаени.
На врвот на оваа датотека C имаме typedef
затоа што сакавме да се создаде податочен тип кој претставува еден збор,
па овој вид е наречен збор, и во внатрешноста на оваа структура
тоа е малку познавач сега.
Зошто еден збор составен од очигледно низа?
Што е збор само интуитивно?
>> Тоа е низа од карактери.
Тоа е секвенца од знаци да се врати назад да се врати.
БУКВИ во сите настапи се случува да биде што произволно велат дека максималната должина
на било кој збор во речникот што се употребува за трка.
Зошто имам 1?
На нула карактер.
Сеќавам кога ние го сторивме на пример Bananagrams ни е потребно посебна вредност
на крајот на зборот, со цел да ги пратите
од каде зборови всушност заврши, а како проблем сет спецификација вели
тука сме асоцирањето со даден збор логичка вредност,
знаме, така да се каже, точно или неточно.
Го најде овој збор веќе, бидејќи сфаќаме
ние навистина треба начин на помнење не само што збор е во трка
но дали или не, на човекот, го најде
така што ако не го најдете зборот "на" не може само да напишете, внесете, на, внесете, на, внесете
и да добијат 3 поени, 3 поени, 3 поени, 3 поени.
Ние сакаме да бидеме во можност да црната листа на тој збор со поставување на bool
на true ако веќе сте го најде, и така тоа е причината зошто ние
врзуваат тоа во оваа структура.
>> Сега, тука долу во трка има оваа друга struct наречен речникот.
Отсутен тука е збор typedef затоа што во овој случај
ние потребни за да капсулирало идејата за речникот,
и речник содржи еден куп зборови,
како имплицирани од оваа низа, и колку од тие зборови се таму?
Па, она што оваа променлива наречена големина вели.
Но, ние само треба еден речник.
Ние не треба податочен тип се нарекува речникот.
Ние само треба еден од нив, па излегува во C
дека ако не се каже typedef, само велат struct, а потоа внатре во големи загради
ги ставаш променливи, тогаш стави името.
Ова се наведува една променлива наречена речник
што личи ова.
Спротивно на тоа, овие редови се создаде еднократно податоци структура наречена збор
дека можете да креирате повеќе копии на, како што ја создававме
повеќе копии на студентите.
>> Што значи тоа во крајна линија ни овозможи да се направи?
Дозволете ми да се вратам во, да речеме, еден поедноставен пример од поедноставни времиња,
и дозволете ми да се отвори, да речеме, compare1.c.
Проблемот тука при рака е всушност да лупам назад
слојот на низа и да започнете преземањето од овие обука тркала
бидејќи излегува дека низа сето ова време
е како што вети во неделата 1 навистина само прекар,
синоним од CS50 библиотека за нешто што изгледа малку повеќе криптичната,
char *, и видовме оваа ѕвезда порано.
Видовме во контекст на датотеки.
>> Ајде сега да видиме зошто ние се криел овој детал за некои Времето сега.
Тука е датотека наречена compare1.c,
и тоа очигледно го прашува корисникот за 2 жици, а и т,
а потоа се обидува да се споредат овие жици за еднаквост во линија 26,
и ако тие се еднакви тој вели: "Внесовте истото"
и ако тие не се еднакви тој вели: "Внесовте различни нешта."
Дозволете ми да оди напред и да ја извршите оваа програма.
Дозволете ми да одам во мојата изворниот директориум, направете compare1. Тоа Составувач ред.
Дозволете ми да се кандидира compare1.
Јас ќе зумирате, внесете.
Кажи нешто. ЗДРАВО.
Јас ќе кажам нешто повторно. ЗДРАВО.
Јас дефинитивно не внесете различни нешта.
>> Дозволете ми да се обиде повторно. Bye bye.
Дефинитивно не се разликува, па она што се случува тука?
Па, она што е навистина се спореди во линија 26?
[Нечујни-студент]
Да, па излегува дека стринг, тип на податоци, е вид на бела лага.
А низа е char *, но она што е char *?
А char *, како што велат, е покажувач,
и покажувач е, всушност, адреса,
сума локација во меморијата, а ако се случи да се внесе во еден збор како ЗДРАВО,
потсетиме од минатото дискусиите на стрингови
ова е како зборот Здраво.
Запомнете дека зборот како ЗДРАВО може да се претстави
како низа од карактери како оваа
а потоа со специјален карактер на крајот нарекува нулти карактер,
како \ означува.
Што е всушност низа?
Забележете дека ова е повеќе делови од меморијата,
и всушност, на крајот од него е познат само откако ќе се погледне преку цела низа
во потрага по специјални null карактер.
Но, ако ова е парче меморија од меморијата на компјутерот ми е,
ајде произволно да се каже дека овој стринг само што влегов среќа,
и тоа доби поставена на самиот почеток на RAM меморија на компјутерот ми е.
Ова е бајт 0, 1, 2, 3, 4, 5, 6 ...
>> Кога ќе се каже нешто како GetString и јас низа s = GetString
она што е навистина се врати?
За овие изминатите неколку недели, она што е навистина се чуваат во с
не е оваа низа по себе, но во овој случај она што се чуваат е
бројот 0, бидејќи она што GetString всушност не
е тоа не физички се врати стринг.
Тоа дури и не навистина да се направи концептуална смисла.
Што го прави тоа враќање е број.
Тој број е адресата на ЗДРАВО во меморијата,
и гудачки и тогаш, ако ние лупам назад овој слој, стринг не постои.
Тоа е само поедноставување на CS50 библиотека.
>> Ова навистина е нешто што се нарекува char *.
Char има смисла, бидејќи она што е збор, како Ало?
Па, тоа е серија на карактери, серија на карактери.
Char * значи адресата на карактер,
па што значи тоа да се врати стринг?
А убаво, едноставен начин за враќање низа
е наместо да се обидат да дознаам како ќе се вратам на 5 или 6 различни бајти
дозволете ми да се врати на адресата на која бајт?
Првиот.
Со други зборови, дозволете ми да ви даде адресата на некој лик во меморијата.
Тоа е она што char * претставува, адресата на еден единствен карактер во меморијата.
Повик таа променлива s.
Продавница во е дека одредена адреса, за што јас произволно рече дека е 0,
само да го задржи нешта едноставно, но во реалноста тоа е обично поголем број.
>> Почекајте една минута.
Ако сте само ми даде адресата на првиот карактер, како можам да знам што адресата е
на вториот лик, третата, четвртата и петтата?
[Нечујни-студент]
Вие само знам каде на крајот од стрингот е по пат на оваа корисна трик,
па кога ќе се користи нешто како printf, што printf буквално зема како своја аргумент,
потсетиме дека ние ги користиме случаеви оваа% s, а потоа ќе помине во
променлива која е складирање низа.
Што сте навистина поминува е адресата на првиот карактер на стрингот.
Printf потоа користи за јамка или додека јамка по приемот на таа адреса,
на пример, 0, па дозволете ми да го направите ова сега,
printf ("% s \ n" и);
Кога ќе се јавам printf ("% s \ n" и); она што јас сум навистина обезбедување printf со
е адресата на првиот карактер во с, која во оваа произволна случај е Х
>> Како се printf знаат што точно да се прикаже на екранот?
Лицето кое спроведува printf спроведува додека јамка или за телефонска линија
кој се вели дека е овој лик се изедначи со посебни null карактер?
Ако не, тоа печатите. Како за оваа?
Ако не го испечатите, да ја отпечати, печати, печати неа.
Ох, ова е посебен. Стоп за печатење и да се вратат на корисникот.
И тоа е буквално се што се случува под хауба,
и тоа е многу да се вари во првиот ден на класа,
но сега за сега тоа е навистина градење на блок на разбирање што
и тоа е се случува во внатрешноста на меморија нашиот компјутер,
и на крајот ќе закачам ова освен со мала помош
од една од нашите пријатели во Стенфорд.
>> Професорот Ник Parlante на Стенфорд има направено овој прекрасен видео инсерт
од сите видови на различни јазици кои воведе
оваа мала Claymation карактер Binky.
Гласот сте за да се слушне во само неколку секунди подлец преглед
е дека на Стенфорд професор, а ти си добивање
само 5 или 6 секунди на ова право сега,
но ова е забелешка на кој ќе се заклучи денес
и да започне в среда.
Јас ви даде Покажувач Забава со Binky, прегледот.
[♪ Музика ♪] [професор Parlante] Еј, Binky.
Разбудам. Тоа е време за покажувачот забава.
[Binky] Што е тоа? Учат за покажувачи?
О, стрина!
>> Ние ќе се видиме во среда.
[CS50.TV]