[Powered by Google Translate] [Недела 6, Продолжува] [Дејвид Џ Malan] [Универзитетот Харвард] [Ова е CS50.] [CS50.TV] Ова е CS50 и ова е крајот на недела 6. Значи CS50x, еден од првите курсеви Харвард вклучени во edx иницијатива навистина дебитираше минатата понеделникот. Ако сакате да се добие увид на она што другите на интернет сега се следниве заедно со, можете да се упатат кон x.cs50.net. Тоа ќе ви се пренасочува кон соодветното место на edx.org, која беше местото каде што овој и други предмети од МИТ и Беркли сега живеат. Ќе треба да се регистрирате за сметка, вие ќе најдете дека материјалот е во голема мера иста како сте имале овој семестар, иако неколку недели одложен, како што се се подготвени. Но, она што студентите во CS50x Сега ќе видите е интерфејс доста како оваа. Ова, на пример, е Zamyla водечки Walkthrough за проблемот сет 0. По влезете во edx.org, а CS50x студент гледа видови на нештата што би очекувале да видите во курсот: предавањето за понеделник, Предавање за среда, разни шорцеви, проблемот сетови, walkthroughs, PDF датотеки. Покрај тоа, како што гледате овде, машина преводи на англиски записници во кинески, јапонски, шпански, италијански, и целиот куп на други јазици кои сигурно ќе се несовршени како што ние ги промовираме програмски користење на нешто што се нарекува API-то, или апликација програмски интерфејс, од Google која ни овозможува да го конвертирате англиски на овие други јазици. Но, благодарение на прекрасните духот на некои сто-плус волонтери, случајни луѓе на интернет кои љубезно се нудат да се вклучат во овој проект, ние постепено ќе се подобри квалитетот на оние преводи со тоа што луѓето се поправи грешките што нашите компјутери ги направиле. 

Значи излегува имавме уште неколку студенти се појави во понеделникот отколку што првично се очекуваше. Всушност, сега CS50x има 100.000 луѓе следниве заедно дома. Па сфаќаш дека сите сме дел од овој прв класа за изработка на овој курс по компјутерски науки образование поопшто, пошироко, достапен. И реалноста е сега, со некои од овие масивна онлајн курсеви, сите тие почнуваат со овие многу голем број, како што се чини дека го направиле тука. Но целта, во крајна линија, за CS50x е навистина да се добие што поголем број луѓе до финишот што е можно. Од страна на дизајнот, CS50x се случува да бидат понудени од минатата понеделник на целиот пат низ 15 април 2013 година, така што луѓето кои имаат училиште обврски на друго место, работата, семејството, други конфликти и слично, имаат малку поголема флексибилност со која ќе се нурне во овој курс, кој, доволно е да се каже, е доста амбициозно направи ако само во текот на само три месеци во текот на вообичаениот семестар. Но овие ученици ќе биде справување со истиот проблем сетови, гледање на истата содржина, имаат пристап до истите шорцеви и слично. Значи сфатат дека сите ние сме навистина во ова заедно. И еден на крајот цели на CS50x не е само да добие што повеќе луѓе до финишот и да им даде оваа новооткриената разбирање на компјутерски науки и програмирање, но, исто така, да имаат нив имаат овој заедничкото искуство. Еден од дефинирање на карактеристиките на 50 на кампусот, се надеваме, е овој вид на комунални искуство, за подобро или за полошо, понекогаш, но имаат овие луѓе да се сврти кон лево и на десно, и работното време и hackathon и фер. Тоа е малку потешко да го стори тоа во лице со луѓе онлајн, но CS50x ќе заврши во април со првиот CS50 Експо, која ќе биде онлајн адаптација на нашата идеја на саемот каде што овие илјадници на сите студенти ќе бидат поканети да достават 1 - до 2-минутна видео, или снимањето на нивниот завршен проект или видео од нив мавтајќи здраво и зборуваме за нивниот проект и demoing тоа, многу сличен на вашите претходници го направиле тука на кампусот во фер, така што до крајот на семестарот, на надеж е да се има глобална изложба на конечните проекти CS50x учениците, многу сличен на она што ве очекува во декември тука на кампусот. Па повеќе за тоа во месеците што доаѓаат. 

Со 100.000 ученици, сепак, доаѓа потребата за уште неколку CAS. Со оглед дека вие момци пламнал на патеката тука и преземање CS50 неколку недели пред пуштањето на овој материјал за народот на edx, реализираат ние би сакале да се вклучат што поголем број од нашите сопствени студентите како е можно во оваа иницијатива, и во текот на семестарот, како и оваа зима и оваа следната пролет. Значи, ако би сакале да се вклучат во CS50x, особено се приклучи во на CS50x Дискутирај, верзијата edx на CS50 дискутираат, која многумина од вас биле користење на кампусот, онлајн огласна табла, Ве молиме главата на тоа рачно, нека знаат кој си, затоа што ние би сакале да се изгради тим на ученици и вработени и факултет слично на кампусот кои се само игра заедно и помагање. И кога ќе го видат прашање кое е запознаен со нив, ќе слушнете студент известување некои бубачки некаде таму во некоја земја на интернет, и што ѕвони на камбана затоа што премногу ја имале таа истото прашање во вашиот г-салата пред некое време, се надевам дека можеш да свири и да ги споделите вашите сопствени искуства. Затоа ве молиме да се причестуваат, ако би сакал. 

Компјутерски науки курсеви во Харвард имаат малку традиција, CS50 една од нив, имаат некои облека, некои алишта, кои можете да ги носите со гордост на крајот на семестарот, велејќи доста гордо дека ќе заврши CS50 и го зеде CS50 и слично, а ние секогаш се трудиме да се вклучат учениците во овој процес колку што е можно, при што ги покануваме, околу ова време на семестарот, студентите да ги достават дизајни користејќи Photoshop, или што и алатка за избор сакате да го користите ако сте дизајнер, да ги достават дизајни за маици и Суичери и чадори и малку bandanas за кучиња сега имаме и слично. И сè е тогаш - на победниците секоја година потоа се изложени на веб страната на курсот на store.cs50.net. Сè што се продава по цена таму, но веб-сајтот само по себе води и им овозможува на луѓето да се избере бои и дизајни, кои им се допаѓа. Па мислев дека ние само ќе споделам некои од дизајните минатата година кои беа на веб покрај ова тука, што е годишен традиција. "Секој ден јас сум СКГ Faultn" беше еден од поднесоци минатата година, кој се уште е на располагање таму за алумни. Имавме оваа "CS50, основана 1989 година." Еден од нашите Bowdens, Роб, беше многу популарна минатата година. "Тимот Бауден" е роден, овој дизајн е поднесено, меѓу врвот продавачи. Како што беше овој овде. Многу луѓе кои имале "Бауден треска" по продажбата на логови. Сфатат дека тоа сега може да биде вашиот дизајн таму, горе на интернет. Повеќе детали за ова во следниот проблем поставува за да дојде. 

Уште една алатка: сте имале некои изложеност и се надевам дека сега некои рацете на искуство со GDB, што е, се разбира, дебагер и ви овозможува да се манипулира вашата програма на прилично ниско ниво, го прават она што видови на нештата? Што значи GDB да го направите? Да? Дај ми нешто. [Студентски одговор, неразбирливо] Добро. Чекор во функција, така што не само што мора да напишеш работи и имаат програма удар преку целост, печатење работи на стандарден излез. Наместо тоа, можете да влезете низ таа линија по линија, или пишување следната да одат линија по линија по линија или чекор да се нурне во функција, обично оној што го напишал. Што друго не GDB да го направите? Да? [Студентски одговор, неразбирливо] Печати променливи. Значи, ако сакате да направите малку интроспекција во внатрешноста на вашата програма без да се впуштат во пишување printf изјави насекаде, можете само да се печати променлива или да прикаже променлива. Што друго можете да направите со дебагерот како GDB? [Студентски одговор, неразбирливо] Точно. Можете да го поставите точки на прекин, вие може да се каже пауза извршување во главната функција или функција foo. Може да се каже пауза извршување на линија 123. И точки на прекин се навистина моќна техника затоа што ако имаш општа смисла на тоа каде вашиот проблем веројатно е, вие не мора да губите време повлекува преку целост на програмата. Вие во суштина може да скокаат во право таму и тогаш проектот пишување - повлекува преку неа и со чекор или следната или слично. Но, се фати со нешто како GDB е тоа што ви помага, човекот, најдете проблеми и најдете грешки. Тоа не мора да ги најдете толку многу за вас. 

Значи ние воведе некој ден style50, која е краток командната линија алатка која се обидува да стилизирам вашиот код малку повеќе чисто од вас, човечки, би можеле да имаат направено. Но, тоа, исто така, е навистина само естетска работа. Но излегува дека е тоа друга алатка наречена Valgrind што е малку повеќе arcane да го користите. Своето производство е atrociously криптичната на прв поглед. Но, тоа е прекрасно корисни, особено сега кога сме во делот на терминот каде сте почнуваат да користат Примерок и динамична алокација на меморија. Работи може да тргне навистина, навистина лошо брзо. Затоа што ако заборавите да се ослободи вашата меморија, или можете Dereference некои NULL покажувач, или можете Dereference некои ѓубре покажувач, што е обично симптом дека резултатите? Секунда грешка. И ќе го добиете ова јадро датотека на одреден број на килобајти или мегабајти што претставува состојба на меморија вашата програма кога се урнал, но вашата програма крајот секунда грешки, сегментација на вина, што значи нешто лошо се случи скоро секогаш поврзана на мемориска поврзани грешка што сте го направиле некаде. Значи Valgrind ви помага да се најдат работи како оваа. Тоа е алатка која ви работи, како GDB, откако сте состави вашата програма, но наместо да се кандидира на вашиот програма директно, трчате Valgrind и ќе помине да го вашата програма, исто како што го правите со gdb. Сега, употреба, за да се добие најдобар вид на излез, е малку долго, па право таму на врвот од екранот ќе видите Valgrind-V. "-V" речиси универзално значи опширниот кога користите програми на Linux компјутер. Па тоа значи плукаат повеќе податоци отколку што може од стандардните. "- Протекуваат-проверка = полн." Ова е само велејќи проверка за сите можни меморија протекување, грешки што може да се направи. Ова, исто така, е честа парадигма со Линукс програми. Општо земено, ако имате командната линија аргумент дека е "прекинувач", дека би требало да се промени однесувањето на програмата, и тоа е една буква, тоа е-V, но ако тоа е вклучен, само со дизајн на програмерот, е целосна збор или серија на зборови, на командната линија аргумент почнува со -. Овие се само човечките конвенции, но ќе ги видиме повеќе. А потоа, конечно, "a.out" е произволно име за програмата во овој пример. И тука е некои претставник излез. 

Пред да погледнеме во она што би можело да значи, дозволете ми да одам во текот на Одрезок код овде. И дозволете ми да се помести ова од патот, доаѓа наскоро, и ајде да ги разгледаме во memory.c, што е овој краток пример тука. Значи во оваа програма, дозволете ми да зумирате на функции и прашања. Имаме функцијата главен која повикува функција, ѓ, и тогаш што ли ѓ продолжи да се направи, во малку технички англиски? Што значи ѓ продолжи да направам? Како за јас ќе започне со линија 20, а локацијата на ѕвездата не е важно, но јас само ќе бидат во согласност тука со минатата предавање. Што е линија 20 не за нас? На левата страна. Ние ќе го срушат понатаму. Int * x: што значи тоа направи? Во ред. Тоа е прогласување на покажувачот, а сега нека биде дури и повеќе од техничка природа. Што значи тоа, многу конкретно, да прогласи покажувачот? Некој друг? Да? [Студентски одговор, неразбирливо] предалеку. Значи ти ја читаш на десната страна на знак за еднаквост. Ајде да се фокусираат само на левата страна, само на int * x. Ова значи "прогласи" покажувач, но сега ајде да се нурне во подлабок на таа дефиниција. Што значи дека конкретно, технички значи? Да? [Студентски одговор, неразбирливо] Во ред. Тоа е се подготвува да го спаси адреса во меморијата. Добро. И ајде да ја искористам оваа чекор понатаму, тоа е прогласување на променлива, x, тоа е 32 бита. И знам дека тоа е 32 бита, бидејќи - Тоа не е затоа што тоа е цел број, бидејќи тоа е покажувачот во овој случај. Случајно тоа што тоа е една и иста со int, но факт е дека има ѕвездата има значи дека ова е покажувачот а во уредот, како и со многу компјутери, но не сите, показалки се 32 бити. На повеќе современи хардвер како на најновите Macs, најновите компјутери, може да имаат 64-битни покажувачи, но во апаратот, овие работи се 32 бити. Па ние ќе се стандардизираат на тоа. Поконкретно, приказната оди како што следува: Ние "прогласи" покажувач, што значи тоа? Ние го подготвуваме за чување на мемориската адреса. Што значи тоа? Ние создаваме променлива наречена x дека зазема 32 бита дека наскоро ќе ги чува адресата на цел број. И тоа е веројатно е за толку прецизна како може да се добие. Тоа е во ред движи напред за поедноставување на светот и само велат прогласи покажувач кој се нарекува x. Декларирате покажувач, но сфати и разбере она што всушност се случува дури и во само оние неколку ликови. 

Сега, ова е речиси малку полесно, иако тоа е повеќе израз. Па што е ова прави, тоа е истакнат сега: "Примерок (10 * sizeof (int));" Да? [Студентски одговор, неразбирливо] Добро. И јас ќе го однесе таму. Тоа е распределба на парче меморија за десет цели броеви. И сега ајде да се нурне во малку подлабоко, тоа е издвојување на дел од меморијата за десет цели броеви. Што Примерок потоа се враќа? Адресата на која дел, или, поконкретно, на адресата на првиот бајт од тоа парче. Како тогаш сум, програмер, да знаеме каде што дел од меморијата цели? Знам дека тоа е соседни. Примерок, по дефиниција, ќе ви даде соседни парче на меморија. Не празнини во неа. Вие имате пристап до секој бајт во тој дел, назад кон назад да се врати, но како да знам каде на крајот од овој дел на меморија е? Кога користите Примерок? [Студентски одговор, неразбирливо] Во ред. Не. Мора да се запамети. Морам да се сеќавам дека јас се користи на вредност 10, а јас дури и не изгледа да го направиле тоа тука. Но обврска е целосно на мене. Strlen, што станавме малку потпираат на за жици, работи само затоа што на оваа конвенција на постоење \ 0 или оваа специјална НУБ карактер, НУБ, на крајот од стрингот. Дека не поседува само произволни делови од меморијата. Тоа е до вас. Значи линија 20, а потоа, доделува парче меморија која може да собере десет цели броеви, а тоа продавници адресата на првиот бајт на тој дел од меморијата во променлива наречена х. Ерго, кој е покажувачот. Значи линија 21, за жал, беше грешка. Но, прво, она што го прави тоа? Тоа е велејќи продавница на 10 место, 0 индексирани, на дел од меморија се нарекува х вредност 0. 

Значи забележите неколку работи се случува. Иако x е покажувач, да се потсетиме од пред неколку недели дека сеуште можете да го користите низа стил квадратни загради нотација. Затоа што тоа е всушност краток рака нотација за повеќе криптичната изглед покажувачот аритметика. каде што ќе се направи нешто како ова: Земете адреса x, се движи 10 места над, потоа оди таму за да она адреса е зачувана на таа локација. Но, искрено, ова е само крволочен да чита и да се чувствуваме удобно со. Па во светот обично се користи во квадратни загради само затоа што е многу повеќе човечки пријателски да се прочита. Но, тоа е она што навистина се случува под хауба; x е на адреса не, низа, сама за себе. Значи ова е складирање 0 на локација 10 во х. Зошто е тоа лошо? Да? [Студентски одговор, неразбирливо] Токму така. Ние само распределени десет ints, но ние сметаме од 0 кога програмирање во C, па имате пристап до 0 1 2 3 4 5 6 7 8 9, но не 10. Значи, која било програма ќе секунда грешка или не е. Но, ние навистина не знам, ова е вид на nondeterministic однесување. Тоа навистина зависи од тоа дали ние ќе имаат среќа. Ако излезе дека оперативниот систем не му пречи ако јас го користам тоа екстра бајт, иако тоа не ја даде за мене, мојата програма не може да се сруши. Тоа е сурова, тоа е грешка, но вие не може да се види дека симптом, или можете да ја видите само еднаш во некое време. Но, реалноста е дека вирусот е, всушност, постојат. И тоа е навистина проблематично ако сум напишал една програма која сакате да биде точна, кои ќе се продаваат на програмата дека луѓето се користи секој еднаш во некое време се урна бидејќи, се разбира, ова не е добро. Всушност, ако имате телефон Андроид или iPhone и да преземете апликации овие денови, ако некогаш сте имале еден стан само да престанам, одеднаш исчезнува, тоа е речиси секогаш резултат на некои меморија поврзани со ова прашање, при што на програмерот зезнав и dereferenced покажувач дека тој или таа не треба да има, и како резултат на iOS или Андроид е само да го убие програма целосно наместо да ризикува недефиниран однесување или некој вид на безбедност компромис. 

Има една друга бубачка во оваа програма покрај оваа. Што друго би ја зезнав работата во оваа програма? Јас не сум практикува она што го проповеда. Да? [Студентски одговор, неразбирливо] Во ред. Јас не се ослободи меморија. Па правило сега мора да биде во секое време ви се јави Примерок, мора да се јавите бесплатно кога ќе се направи со користење дека меморијата. Сега, кога јас би сакал да се ослободи оваа меморија? Веројатно, под претпоставка дека оваа прва линија е точно, јас би сакал да го направите тука. Бидејќи не можев да, на пример, направете го тоа овде. Зошто? Само надвор од опсегот. Значи иако ние зборуваме за покажувачи, ова е една недела 2 или 3 прашањето, каде x е само во обем внатрешноста на тркалезните загради каде што било објавено. Така да дефинитивно не може да се ослободи таму. Мојата единствена шанса да се ослободи е приближно по линија 21. Ова е прилично едноставна програма, тоа беше прилично лесно еднаш вид на завиткани вашиот ум околу она што програмата го прави, каде грешките беа. Па дури и ако не го гледаа во прво време, се надевам дека тоа е малку очигледно сега дека овие грешки се прилично лесно да се реши и лесно да се направи. Но, кога на програмата е повеќе од 12 линии долго, тоа е 50 линии долги, 100 линии долги, одење преку вашиот кодот линија по линија, мислејќи низ него логично, е можно, но не е особено забавно да се направи, постојано во потрага по бубачки, и тоа е исто така тешко да се направи, а тоа е зошто алатка како Valgrind постои. Дозволете ми да оди напред и да го направите ова: дозволете ми да ми го отвори прозорецот на терминалот, и дозволете ми да не само стартувајте меморија, затоа што меморијата се чини дека е во ред. Јас сум добивање на среќа. Ќе дека дополнителни бајт на крајот на низата не чини да се биде премногу проблематично. Но, дозволете ми да, сепак, се направи здрав разум чек, кој едноставно значи да се провери дали или не ова е всушност точни. 

Па ајде да направиме valgrind-V - протекуваат-проверка = полн, а потоа името на програмата во овој случај е меморија не, a.out. Па дозволете ми да оди напред и да го направите тоа. Хит Enter. Драг Боже. Ова е нејзиниот излез, и тоа е она што се алудира погоре. Но, ако научат да читаат низ сите глупости овде, повеќето од ова е само дијагностички излез тоа не е интересно. Што окото навистина сака да се гледа за каква било споменување на грешка или не е валиден. Зборови кои укажуваат на проблеми. И навистина, ајде да видиме што се случува погрешно овде. Имам резиме на некој вид, "во употреба на излез:. 40 бајти во 1 блокови" Не сум баш сигурен што еден блок е сеуште, но 40 бајти всушност се чувствува како можев да дознаам каде што доаѓа од. 40 бајти. Зошто се 40 бајти во употреба на излез? И поконкретно, ако се движите надолу тука, зошто јас дефинитивно изгубени 40 бајти? Да? [Студентски одговор, неразбирливо] Совршен. Да, точно. Имаше десет цели броеви, а секој од нив е големината на 4 или 32 бита, па јас го заборавив точно 40 бајти бидејќи, како што предложи, не сум наречени слободни. Тоа е една бубачка, а сега нека се погледне надолу малку понатаму и да видиме до ова, "Невалидна пишуваат на големината 4." Сега што е ова? Оваа адреса на е изразена она база нотација, очигледно? Ова е хексадецимално, и секој пат кога ќе видите голем број почнувајќи со 0x, тоа значи хексадецимален, што ние го сторивме уште во, мислам, дел pset 0 на прашања, која беше само да се направи warmup вежба, конвертирање децимална да хексадецимален на бинарни и така натаму. Хексадецимално, само од човечка конвенција, обично се користат за да претставуваат совети или, поопшто, се однесува. Тоа е само конвенција, затоа што тоа е малку полесно да се чита, тоа е малку покомпактен отколку нешто како децимална, и бинарни е бескорисна за повеќето луѓе да го користите. Па сега што значи тоа? Па, тоа отприлика изгледа таму е невалиден пишуваат на големина од 4 на линија 21 од memory.c. Значи, да се вратиме на линија 21, и навистина, тука е дека неважечки пишувам. Значи Valgrind нема целосно да се одржи мојата рака и да ми кажете што фикс е, но тоа е откривање дека јас го правам погрешно пишувам. Јас сум допирање 4 бајти дека не треба да биде, и очигледно тоа е затоа што, како што посочи, го правам [10] наместо [9] максимално или [0] или нешто помеѓу. Со Valgrind, свесни секое време сте сега пишување програма кој користи совети и користи меморијата, и Примерок поконкретно, дефинитивно се влезе во навика на водење на овој долг но многу лесно копирани и атипичен команда на Valgrind да се види дали има некои грешки во таму. И тоа ќе биде огромно секој пат кога ќе видите излез, но само ја анализирам преку визуелно сите на излез и да видиме ако видите споменува на грешки или предупредувања или не е валиден или изгуби. Сите зборови кои звучат како сте ја зезнав некаде. Така сфаќаат дека е нова алатка во вашето раководство. 

Сега во понеделникот, имавме еден куп на луѓе доаѓаат тука и претставува поимот на поврзани листа. И воведовме поврзани листа како решение за она што проблемот? Да? [Студентски одговор, неразбирливо] Во ред. Низи не може да има меморија додадени на нив. Ако распредели низа на големина 10, тоа е сите ќе добиете. Можете да се јавите на функција како realloc ако првично наречен Примерок, и дека може да се обидете да расте низата ако постои простор кон крајот на тоа што никој друг не се користат, а ако не е, тоа само ќе те најдат поголем дел некаде на друго место. Но, тогаш ќе ги копирате сите оние бајти во новата низа. Ова звучи како многу точни решение. Зошто е ова непривлечна? Мислам тоа функционира, луѓето се реши овој проблем. Зошто ние треба да го решиме во понеделникот со поврзани листи? Да? [Студентски одговор, неразбирливо] Тоа би можело да трае долго време. Всушност, во секое време ви се повикуваат Примерок или realloc или calloc, што е уште еден еден, секој пат кога ќе, на програмата, се зборува за оперативниот систем, ќе имаат тенденција да го забават програмата надолу. И ако правиш овие видови на нештата во петелките, ти си навистина забавување на работите надолу. Вие нема да забележите ова за наједноставните на "Hello World" тип програми, но во многу поголеми програми, барајќи од оперативниот систем повторно и повторно за мемориски или давање го врати повторно и повторно не се стреми да биде добра работа. Плус, тоа е само вид на интелектуално - тоа е целосно губење на време. Зошто одвои повеќе и повеќе меморија, ризикот копирање сè во новата низа, ако имате алтернатива, која ви овозможува да издвојуваат само колку меморија, како вие всушност треба? Значи има предности и minuses тука. Еден од предности сега е дека имаме динамика. Не е важно каде делови од меморијата се дека се бесплатни, Јас само може да се најде на се создадат овие трошки од леб преку совети да стринг целиот мој поврзани листа заедно. Но, јас плати најмалку една цена. 

Што треба да се откажат во добивање поврзани листи? Да? [Студентски одговор, неразбирливо] Во ред. Ви треба повеќе меморија. Сега е потребно простор за овие покажувачи, и во случај на овој супер едноставен поврзани листа тоа е само се обидува да ја запази броеви, кои се 4 бајти, ние го задржи велејќи добро, покажувач е 4 бајти, па сега јас сум буквално двојно количината на меморија што ми треба само да ја запази оваа листа. Но, повторно, ова е константно Губитокот во компјутерски науки помеѓу времето и просторот и развој, напор и други ресурси. Што е уште недостатоци на користење на поврзани листа? Да? [Студентски одговор, неразбирливо] Добро. Не е толку лесно да пристапите. Веќе не можеме да потпора недела 0 принципи како поделба и освојување. И поконкретно, бинарни пребарување. Бидејќи иако ние, луѓето може да се види речиси каде средината на оваа листа е, на компјутерот само знае дека ова поврзани листа започнува адреса нарекува прв план. И тоа е 0x123 или нешто слично. И единствениот начин на програмата може да се најдат во средината елемент е всушност да пребарувате на целата листа. И дури и тогаш, таа буквално мора да пребарувате на целиот список, бидејќи дури откако ќе стигнат до средината елемент од следниве совети, вас, на програмата, немате поим колку долго оваа листа е, потенцијално, додека не го погоди крајот од неа, и како знаеш програмски дека сте на крајот на поврзани листа? Има посебна NULL покажувач, па уште еднаш, на конвенцијата. Наместо да го користите овој покажувач, ние дефинитивно не сакате тоа да бидат некои ѓубре вредност покажувајќи исклучи фаза некаде, ние сакаме да биде раката надолу, NULL, така што ние имаме оваа терминалот во овој податочна структура за да знаеме каде завршува. 

Што ако сакаме да се манипулира со ова? Ние направивме поголемиот дел од оваа визуелно и со луѓето, но што ако ние сакаме да се направи една вметнување? Значи оригиналот листа беше 9, 17, 20, 22, 29, 34. Што ако ние тогаш сакаа да Примерок простор за 55 број, еден јазол за тоа, и потоа сакате да го вметнете 55 во листата исто како што направивме во понеделникот? Како го правиме тоа? Па, Анита излезе и таа суштина одеше на листата. Таа започна првиот елемент, тогаш следниот, следната, следниот, следната, следниот. Конечно хит на левата страна на целиот пат и реализирани ох, ова е NULL. Значи она што покажувачот манипулација потребни за да се направи? Лицето кое беше на крајот, број 34, потребно левата рака подигната да се укаже на 55, 55 потребни левата рака укажува надолу за да биде новиот NULL терминатор. Готово. Прилично лесно да вметнете 55 во Подредена листа. И како тоа може да изгледа? 

Дозволете ми да оди напред и да се отворат некои кодот пример тука. Ќе се отвори gedit, и дозволете ми да отвори две датотеки во прв план. Една од нив е list1.h, и дозволете ми да ве потсетам дека ова е дел од код кои што се користат за да претставуваат јазол. А јазол има и int нарекува n и покажувач наречен следниот што само укажува на следното нешто во листата. Тоа е сега во. Ж датотека. Зошто? Има оваа конвенција, а ние не се преземаа предноста на оваа огромна сума себе, но лицето кое го напиша printf и други функции даде како подарок на светот на сите оние функции со пишување на фајл наречен stdio.h. А потоа, тука е string.h, а потоа има map.h, и има сите овие часот датотеки кои може да се види или да се користат за време на мандатот напишани од други луѓе. Обично во нив. Ж датотеки се само работи како typedefs или декларации на сопствени типови или декларации на константи. Вие не стави функции "имплементации во насловот датотеки. Да се ​​стави, наместо тоа, само нивните прототипови. Ќе се стави работите што сакате да го споделите со светот она што тие треба со цел да ги собере своите код. Па само да се влезе во оваа навика, решивме да го прават истото. Таму не е многу во list1.h, но ние сме се стави нешто што може да биде од интерес за луѓе во светот кои сакаат да ги користат нашите поврзани листа имплементација. Сега, во list1.c, јас не ќе оди преку целата оваа работа бидејќи тоа е малку долго, оваа програма, но, ајде да се кандидира тоа во реално брзо во конзолата. Дозволете ми да ги собере list1, дозволете ми да потоа изврши list1, и она што ќе видите е ние сме симулирани едноставна мала програма тука тоа ќе ми овозможи да додадете и отстранувате броеви на листата. Па дозволете ми да оди напред и тип 3 за опција од менито 3. Сакам да вметнете број - ајде да направиме првиот број, кој беше 9, и сега јас сум изјави на листата е сега 9. Дозволете ми да оди напред и да се направи уште еден вметнување, па јас хит опција од менито 3. Што број сакам да вметнете? 17. Enter. И јас ќе направам само уште еден. Дозволете ми да внесете го бројот 22. Значи имаме почетоците на поврзани листа што го имавме во слајд форма пред еден момент. Како е ова вметнување всушност се случува? Всушност, 22 е сега на крајот на листата. Значи приказната ни е кажано на сцената во понеделникот и ја резимираше само сега всушност треба да се случува во кодот. Ајде да ги разгледаме. Дозволете ми да дојдете во оваа датотека. Ние ќе притајуваат некои од функциите, но ние ќе одат надолу, да речеме, вметнете функција. 

Ајде да видиме како ќе одат за вметнување на нов јазол во овој поврзани листа. Каде е листата прогласена? Па, ајде да дојдете сите на патот до врвот, и ќе забележите дека мојот поврзани листа суштина е прогласен како еден показател дека е првично NULL. Затоа, јас сум со користење на глобалната променлива тука, што воопшто сме го проповедал против бидејќи тоа го прави кодот малку неуредна за одржување, тоа е вид на мрзливи, обично, но тоа не е мрзлив и не е во ред и тоа не е лоша ако единствена цел вашата програма во животот е да се симулираат еден поврзани листа. Која е токму она што го правиш. Така, наместо да пријават тоа во главната, а потоа мора да го помине секоја функција ние сме запишани во оваа програма, ние наместо да се реализира ох, ајде да се направи глобална затоа што целата Целта на оваа програма е да се покаже една и само една поврзани листа. Така што се чувствува добро. Тука се моите прототипови, и ние не ќе помине низ сите овие, но напишав избришете функција, на најдете функција, вметнете функција, како и функцијата напречни. Но, ајде сега одиме назад да вметнете функција и да видиме како тоа некој работи тука. Внеси е на линија - тука ќе одиме. Внесете. Значи тоа не презема никакви аргументи, бидејќи ние ќе прашам на корисникот во внатрешноста на оваа функција за бројот што сакате да го внесете. Но, прво, ние се подготват и да им даде некои простор. Ова е вид на копирате и залепите од другите пример. Во тој случај, бевме доделување на int, овој пат ние сме распределба на еден јазол. Јас навистина не се сеќавам колку бајти еден јазол е, но тоа е во ред. Sizeof може да сфати дека за мене. И зошто сум јас проверка за NULL во ред 120? Што би можело да тргне наопаку во согласност 119? Да? [Студентски одговор, неразбирливо] Добро. Само може да биде случај дека јас сум побара премногу меморија или нешто не е во ред и на оперативниот систем нема доволно бајти за да ми даде, па тоа сигнали како многу по враќањето NULL, и ако не се провери за што и јас само слепо да продолжи да го користи адреса вратено, тоа би можело да биде NULL. Тоа може да биде некоја непозната вредност; не е добра работа ако јас - всушност нема да биде непозната вредност. Тоа може да биде NULL, па не сакам да го злоупотреби и ризик dereferencing неа. Ако тоа се случи, јас само се врати и ќе се преправам како јас не се врати било меморија на сите. 

Инаку, јас му кажете на корисникот ми даде број да вметнете, јас го нарекувам нашиот стар пријател GetInt, и тогаш ова е нова синтакса воведовме во понеделникот. "Newptr-> n 'значи преземат адресата која сте биле дадени од страна Примерок која претставува првиот бајт од нов јазол објект, и потоа оди во областа наречена Н. А малку Trivia прашање: Ова е еквивалентно на она повеќе криптичната линија код? Како инаку би можеле да имам напишано ова? Сакате да земе прободе? [Студентски одговор, неразбирливо] Добро. Користење на. N, но тоа не е толку едноставно како ова. Што ми прво треба да се направи? [Студентски одговор, неразбирливо] Добро. Јас треба да направите * newptr.n. Значи ова е велејќи нови покажувачот е очигледно адреса. Зошто? Поради тоа што беше вратен од Примерок. На * newptr велејќи: "одам таму" а потоа еднаш сте таму, тогаш можете да го користите на повеќе познати. n, но тоа само изгледа малку грдо, особено ако луѓето се случува да подготви совети со стрелки цело време, во светот има стандардизирани на оваа стрелка нотација, што го прави токму истото. Така да само го користат -> нотација кога нешто лево е покажувач. Инаку, ако тоа е вистински struct, користете. Н. И тогаш ова: Зошто иницијализира newptr-> до NULL? Ние не сакаме висат левата рака исклучување на крајот на сцената. Ние сакаме тоа посочувајќи директно надолу, што значи на крајот од оваа листа потенцијално може да биде во овој јазол, и затоа е подобро бидете сигурни дека тоа е NULL. И, воопшто, иницијализацијата вашиот променливи или вашите податоци членови и structs до нешто е само добра пракса. Само допуштајќи ѓубре постојат и продолжи да постои генерално добива во неволја ако сте заборавиле да направите нешто подоцна. 

Еве неколку случаи. Оваа, пак, е вметнете функција, и првото нешто што го провери е ако променливата наречена прво, дека глобалната променлива е NULL, што значи дека не постои поврзани листа. Ние не се вметнати сите броеви, така што е тривијална да ја вметнете тековниот број во листата, бидејќи тоа само припаѓа на почетокот на листата. Значи ова беше кога Анита беше само стои до само овде, преправајќи никој друг не беше до тука на сцена додека не одвои еден јазол, тогаш таа може да се подигне својата рака за прв пат, ако сите други дојдени на сцената по неа во понеделникот. Сега тука, ова е малку проверка, каде што имаат да кажат дали новиот јазол вредноста на n е <вредноста на n во тековната прв јазол, тоа значи дека е поврзано листа која е започната. Има најмалку еден јазол во листата, но овој нов дечко припаѓа пред тоа, па ние треба да се движат работите околу себе. Со други зборови, ако листата започна со само, да речеме, само бројот 17, што е - всушност, може да се направи ова појасно. Ако ние започнуваме нашата приказна со покажувач тука се нарекува прво, и првично е NULL, а ние внесете го бројот 9, бројот 9 јасно припаѓа на почетокот на листата. Значи, да се преправаат дека ние само malloced адресата или бројот 9 и го ставив тука. Ако првиот е 9 по дифолт, првото сценарио зборувавме само значи точка ајде овој човек овде, остави го ова како NULL, а сега имаме бројот 9. Следниот бројот што сакате да го вметнете е 17. 17 припаѓа овде, па ние ќе треба да направите некои логички повлекува преку ова. Па ајде наместо тоа, пред да го направите тоа, ајде да се преправаме дека сакаме да внесете го бројот 8. 

Па само заради погодност, јас одам да се подготви тука. Но, се сеќавам, Примерок да го стави повеќето насекаде. Но заради цртање, јас ќе ја ставам тука. Па се преправам дека сум само распределуваат јазол за бројот 8, ова е NULL стандардно. Што сега треба да се случи? Неколку работи. Ние направивме оваа грешка на сцената во понеделникот, каде што обновено покажувач вака, потоа направи тоа, а потоа тврдеше дека - ние сираче сите други на сцената. Затоа што што не се - наредба на работењето овде е важно, бидејќи ние сега го заборавив овој јазол 9, тоа е само вид на лебдат во вселената. Значи ова не е вистинскиот пристап во понеделникот. Ние прво треба да се направи нешто друго. Состојбата на светот изгледа вака. Првично, 8 е наменет. Што ќе биде подобар начин за вметнување 8? Наместо на ажурирање на оваа покажувачот прво, само го ажурира ова овде, наместо. Значи ние треба една линија од код кој се случува да го вклучите оваа NULL карактер во вистински показател дека се укажува на јазол 9, и потоа можеме безбедно да се промени прво да се укаже на овој човек овде. Сега имаме листа, поврзани листа, од два елементи. И она што го прави ова всушност изгледа како овде? Ако ги погледнеме во кодот, забележите дека сум сторил токму тоа. Сум рече newptr, и во оваа приказна, newptr беше посочувајќи на овој човек. 

Значи, да ме привлече уште една работа, а јас треба да се остави малку повеќе простор за тоа. Па прости малечки цртеж. Овој човек е наречен newptr. Тоа е променлива донесовме неколку линии порано, во линија - над 25. И тоа укажува на 8. Значи, кога велам newptr-> следниот, тоа значи дека оди на struct тоа е се вперени во од newptr, па еве сме, одиме таму. Тогаш стрелките на е велејќи дека го добиете следниот поле, а потоа = кажува стави она вредност таму? Вредноста која беше во прв, што вредност е во првиот? Прво беше посочувајќи на овој јазол, па тоа значи дека ова сега треба да се истакне во овој јазол. Со други зборови, она што изгледа иако смешно неред со мојот ракопис, она што е едноставна идеја на само се движат овие стрели околу преведува на код со само овој еден лагер. Чување она што е во прв во следната поле и потоа обновете го она што прво всушност е. Ајде да одиме напред и брзо-нанапред преку некои од ова, и гледам само во оваа опашка вметнување за сега. Претпоставувам дека дојде до точка каде што сметам дека следната областа на некои јазол е NULL. И во овој момент во приказната, детаљ што сум glossing над е тоа дека јас сум воведе уште покажувачот се тука во 142 линија, претходник покажувач. Во суштина, во овој момент во приказната, откако на листата добива долго, Јас вид на треба да се оди со два прста, бидејќи ако одам предалеку, се сеќавам во една должина листата, не може да се врати назад. Значи оваа идеја на predptr е мојата лева прст, и newptr - не newptr. Друг показател дека е тука е мојот други прст, а јас сум само вид на одење на листата. Затоа што постои. Но, ајде да сметаат само еден од поедноставни случаи тука. Ако следната поле што покажувачот е NULL, што е логично импликација? Ако сте traversing оваа листа и го погоди NULL покажувачот? Ти си на крајот од листата, и така го кодот за да потоа додадете ова еден дополнителен елемент е вид на интуитивен ќе се земе дека јазол чиј следен покажувачот е NULL, па ова во моментов е NULL, и менуваат, сепак, да биде на адресата на новиот јазол. Значи ние сме само цртање во кодот на стрелката што привлече на сцената со зголемување на левата рака нечија. 

И случајот дека ќе бран моите раце, за сега, само затоа што мислам дека е лесно да се изгуби кога ќе го направи тоа во овој вид на животната средина, е проверка за вметнување на средината на листата. Но, само интуитивно, она што треба да се случи, ако сакате да дознаам каде што некои број припаѓа во средината е дека не треба да го изодиш со повеќе од еден прст, повеќе од еден покажувач, дознаам каде што припаѓа со проверка е елемент <тековната, > Тековната, и штом еднаш ќе се најде на тоа место, тогаш мора да се направи овој вид на школка игра каде што се движат на совети околу многу внимателно. И дека одговорот, ако сакате да се причина преку ова дома на свој, се сведува само на овие две линии на код, но редот на оние линии е супер важно. Затоа што ако ви падне страна на некој и да се подигне некој друг во погрешна цел, повторно, би можел да заврши orphaning листата. Да резимираме повеќе концептуално, вметнување на опашката е релативно јасна. Вметнување на главата е исто така релативно јасна, но треба да се ажурира дополнителни покажувачот ова време да се притисне број 5 во листата тука, а потоа вметнување во средината вклучува дури и повеќе напор, да многу внимателно внесете го бројот 20 во неговата точна локација, која е меѓу 17 и 22. Значи треба да се направи такво нешто има нов јазол 20 точка 22, а потоа, покажувач кој јазол треба да биде надграден последно? Тоа е 17, за да всушност го внесете. Значи, повторно, јас ќе го одложи вистинскиот код за што особено имплементација. 

На прв поглед, тоа е малку преголема, но тоа е навистина само бесконечна јамка која е looping, looping, looping, looping, и кршење штом ќе го погоди NULL покажувач, на која точка можете да го направите потребните вметнување. Ова, тогаш, е претставник поврзани листа вметнување код. Тоа беше вид на многу, и тоа се чувствува како ние сме решени еден проблем, но ние сме воведе целиот другиот. Искрено, ние помина сето ова време на големите O и Ω и трчање време, обидувајќи се да ги реши проблемите побрзо, и тука ние правиме голем чекор наназад, таа се чувствува. А сепак, ако целта е да се сместат податоци, се чувствува како Светиот Грал, како што рече во понеделникот, навистина ќе биде да ги чувате работите веднаш. 

Всушност, да претпоставиме дека ние не се стават настрана, поврзани листа за момент и ние наместо да воведе поимот на табелата. И ајде само мислам на маса за момент како низа. Оваа низа и овој случај тука има некои 26 елементи, од 0 до 25, и претпоставувам дека ви се потребни некои парче на багаж за имиња: Алис и Боб и Чарли и слично. И ви треба некои податоци структура за складирање на тие имиња. Па, можете да го користите нешто како поврзани листа и може да одиме на листата вметнување Алис пред Боб и Чарли по Боб и така натаму. И, всушност, ако сакате да се види кодот, како што Како настрана, знаеме дека во list2.h, тоа го правиме токму тоа. Ние не ќе одат преку овој код, но ова е варијанта на првиот пример која се воведува една друга struct видовме пред т.н. студент, а потоа она што всушност продавници во поврзаните листа е покажувач кон студентот структура наместо просто малку број, n. Па сфати дека е кодот таму што вклучува реалните жици, но ако целта при рака навистина сега е да се одговори на ефикасноста проблем, не би било убаво ако ние си даде објектот наречен Алис, сакаме да ја стави во вистинската локација, во податочна структура, се чувствува како тоа би било навистина убаво да се ставив Алис, чие име почнува со А, во првата локација. И Боб, чие име започнува со Б, во втората локација. Со низа, или да почнеме нарекувајќи маса, хаш табелата во тоа, можеме да направиме токму тоа. Ако ние се даде име како Алис, жиците како Алис, каде да се стави А-л-и-в-е? Ние треба hueristic. Ние треба во функција да се преземат некои влез како Alice и да се вратат одговор: "Стави Алиса во оваа локација." И оваа функција, оваа црна кутија, се случува да се нарече хаш функција. 

А хеш функција е нешто што е потребно влез, како "Алиса", и се враќа за вас, обично, нумерички локација во некои податоци структура, каде Алиса припаѓа. Во овој случај, нашите хаш функција треба да биде релативно едноставна. Нашите хаш функција треба да се каже, ако ви се даде "Алиса", кој карактер да се грижите за? Првиот. Па гледам [0], а потоа велам ако [0] лик е, се врати на број 0. Ако тоа е Б, врати 1. Ако тоа е C, вратете 2, и така натаму. Сите 0 индекс, и дека ќе ми дозволат да вметнете Алис а потоа Боб а потоа Чарли и така натаму во оваа податочна структура. Но има еден проблем. Што ако Анита доаѓа заедно повторно? Каде ќе стави Анита? Нејзиното име, исто така, почнува со буквата А, и тоа се чувствува како што е направен уште поголем хаос на овој проблем. Сега имаме непосредна вметнување, постојана време вметнување, во податочна структура наместо полошо случај линеарна, но она што можеме да направиме со Анита во овој случај? Кои се две опции, навистина? Да? [Студентски одговор, неразбирливо] Океј, па ние би можеле да имаат друга димензија. Тоа е добро. Значи можеме да се изгради работи во 3D како ние разговаравме за усно во понеделникот. Ние би можеле да додадете уште еден пристап тука, но претпоставувам дека не, јас се обидувам да ја задржите оваа едноставна. Целиот Целта тука е да имаат непосредна постојана време пристап, Значи тоа е додавање премногу комплексност. Кои се другите опции, кога се обидуваат да го вметнете Анита во оваа податочна структура? Да? [Студентски одговор, неразбирливо] Во ред. Значи, ние би можеле да се движат сите други надолу, како Чарли nudges надолу Боб и Алис, а потоа ќе стави Анита каде што таа навистина сака да биде. 

Се разбира, сега, има пропратен ефект на ова. Овие податоци структура е веројатно корисна не затоа што ние сакаме да го вметнете луѓе еднаш туку затоа што ние сакаме да се провери дали тие се таму подоцна ако сакаме да се печати од сите на имиња на податоци структура. Ние ќе направи нешто со овие податоци на крајот. Така, сега сме вид на зезнав над Алис, кој е веќе каде што би требало да биде. Ниту е Боб, ниту пак е Чарли. Па можеби и ова не е толку добра идеја. Но, навистина, ова е една опција. Ние би можеле да се префрлат сите надолу, или подлец, Анита дојде крајот на играта, зошто да не само да ги ставите на Anita не е тука, а не тука, не тука, ајде да ја стави малку подолу во листата. Но, тогаш овој проблем почнува да се префрлат повторно. Може да биде во можност да најдете Алис веднаш, врз основа на нејзиното име. И Боб веднаш, и Чарли. Но, тогаш барате Анита, и ќе видите, хм, Алис е во тек. Па, дозволете ми да провери подолу Алис. Боб не е Анита. Чарли не е Анита. О, таму е Анита. И ако продолжиш дека возот на логиката на тој пат, што е најлошото трчање време на наоѓање или вметнување Анита во оваа нова податочна структура? Тоа е О (n), нели? Затоа што во најлош случај, тука е Алис, Боб, Чарли. . . сите на патот надолу до некој наречен "Y", па постои само едно место лево. За среќа, имаме никој не вика "Z", па ќе стави Анита на самото дно. 

Не сме навистина реши тој проблем. Па можеби и ние треба да се воведе оваа трета димензија. И што излезе, ако ние се воведе оваа трета димензија, не можеме да го направите ова совршено, но Светиот Грал се случува да се добива постојано работно време вметнување и динамична инсерции, така што ние не треба да се хард-код низа на големина 26. Ние можеме да се вметне како многу имиња како што сакаме, но ајде да нашите 5-минутна пауза тука а потоа направи тоа правилно. Во ред. Јас во собата на приказна до прилично вештачки има со избирање на Алис и потоа Боб а потоа Чарли а потоа Анита, чие име беше очигледно ќе се судираат со Алис. Но, прашањето што заврши во понеделникот со е колку веројатно е тоа кои ќе добијат вакви судири? Со други зборови, ако почнеме да го користите овој табеларен структура, која е навистина само низа, во овој случај на 26 локации, Што ако нашите влезови се наместо рамномерно распределени? Тоа не е вештачки Алис и Боб и Чарли и Дејвид и така натаму по азбучен ред, тоа е рамномерно распределени во текот на еден преку З 

Можеби ние само ќе имаат среќа и ние нема да имаме две А или две Б со многу голема веројатност, но како некој посочи, ако ние генерализирана овој проблем и не 0-25 но, да речеме, од 0 до 364 или 65, често на бројот на денови во типична година, и го поставил прашањето: "Што е веројатноста дека две од нас во оваа просторија имаат ист роденден?" Го стави на друг начин, што е веројатноста дека две од нас има име почнува со А? Вид на прашање е иста, но оваа адреса простор, ова пребарување простор, е поголема во случај на родендени, бидејќи имаме толку многу повеќе денови во годината од букви во азбуката. Што е веројатноста за судир? Па, можеме да размислуваме за тоа од пронајдат математика во спротивна насока. Што е веројатноста нема судири? Па, овој израз тука вели дека она што е веројатноста ако има само една личност во оваа соба, дека тие имаат единствена роденден? Тоа е 100%. Затоа што ако има само едно лице во соба, неговиот или нејзиниот роденден може да биде било кој од 365 дена од годината. Значи 365/365 опции ми дава вредност 1. Па веројатноста во прашање во моментов е само 1. Но, ако има втор човек во собата, она што е веројатноста дека нивниот роденден е различен? Има само 364 можни денови, игнорирајќи престапна година, за нивниот роденден да не се судираат со други лица. Значи 364/365. Ако трето лице доаѓа во, тоа е 363/365, и така натаму. Па ние го задржи множење заедно овие фракции, кои се добива помала и помала, да дознаам што е веројатноста дека секој од нас има уникатен родендени? Но, тогаш може, се разбира, само да тој одговор и флип околу тоа и направи 1 минус сето тоа, израз ние на крајот ќе добиете ако се сеќавате на задната страна од вашите математика книги, изгледа малку нешто како ова, која е многу полесно толкува графички. И оваа графичка тука има на x оската на бројот на родендени, или бројот на луѓе со родендени, и на оската y е веројатноста на еден натпревар. И што тоа го кажува е дека ако имате, да речеме, дури, ајде да изберете нешто како 22, 23. Ако има 22 или 23 луѓе во собата, веројатноста дека две од оние многу малку луѓе се случува да имаат ист роденден е всушност супер висока, combinatorially. 50% шансите дека во класа на само 22 луѓе, семинар, практично, 2 од тие луѓе се случува да имаат ист роденден. Бидејќи има толку многу начини на кои може да имаат ист роденден. Дури и полошо, ако се погледне на десната страна на табелата, од кога ќе имаат класа со 58 ученици во него, веројатноста од 2 луѓе кои имаат роденден е супер, супер висока, речиси 100%. Сега, тоа е вид на забава факт во врска со реалниот живот. 

Но импликации, сега, за структури на податоци и складирање на информации значи дека само претпоставувајќи дека имате убав, чист, униформа дистрибуција на податоци и имаш доволно голема низа за да ги собере еден куп работи не значи дека си оди за да се добие на луѓето во уникатен локации. Ви се случува да имаат судири. Значи ова сфаќање на hashing, како што се вика, земајќи влез како "Алиса" и масажа тоа на некој начин а потоа добивам назад одговор како 0 или 1 или 2. Прв назад некои излез од таа функција е загрозена од овој веројатноста за судир. Па како можеме да се справи со овие судири? Па, за еден случај, може да се преземе идејата дека беше предложено. Ние само може да се префрлат сите надолу, или можеби малку повеќе, едноставно, наместо потег сите други, ајде да се движат Анита до дното на располагање самото место. Значи, ако Алис е во 0, Боб е во 1, Чарли е во 2, ние само ќе се стави Анита на локацијата 3. И ова е техника во податочни структури наречени линеарни љубопитство. Линеарна затоа што ти си само одење оваа линија, а ти си вид на љубопитство за достапни места во податочна структура. Се разбира, ова devolves во О (n). Ако податоците структура е навистина полна, има 25 лица во него веќе, а потоа Анита доаѓа заедно, таа завршува во она што ќе биде Локација Z, и тоа е добро. Таа се уште се вклопува, и можеме да ја најдат подоцна. 

Но, тоа беше спротивно на целта за забрзување работите. Па што ако ние наместо да воведе оваа трета димензија? Таа техника е генерално се нарекува посебно врзувањето, или имаат синџири. И што е хаш табелата сега е, овој табеларен структура, вашата маса е само низа од покажувачи. Но, она што тие совети укажуваат на се погоди што? А поврзани листа. Па што ако го земеме најдоброто од двата од овие светови? Ние ги користиме низи за почетна индекси во податочна структура, така што веднаш може да оди на [0] [1], [30] или така натаму, но така што ние имаме некои флексибилност и ние може да се вклопат Анита и Алис и Адам и сите други Име, ние наместо да ги споделите со другите оска расте произволно. И конечно, од понеделник, дека имаат експресивна способност со поврзаните листа. Ние може да се зголеми на податочна структура произволно. Алтернативно, ние едноставно може да направи голема 2-димензионална низа, но тоа ќе биде страшна ситуација ако еден од редовите во 2-димензионална низа не е доволно голем за дополнителни лице чие име се случува да се започне со А Не дај Боже ние треба да се реалоцираат огромна 2-димензионална структура само затоа што има толку многу луѓе именуван А, особено кога има толку малку луѓе наречена Z нешто. Тоа е само случува да биде многу редок податоци структура. Значи тоа не е совршена со какви било средства, но сега ние барем имаат способност за да веднаш се најде каде Алис или Анита припаѓа, барем во однос на вертикалната оска, и тогаш ние само треба да се одлучи каде да се стави Анита или Алиса во овој поврзани листа. Ако ние не се грижат за сортирање работи, колку брзо можеме да вметнете Алиса во структура, како тоа? Тоа е постојана време. Ние индекс во [0], а ако има никој, Alice оди на почетокот на таа врска листата. Но тоа не е голема работа. Бидејќи ако Анита тогаш доаѓа заедно одреден број на чекори подоцна, каде Анита припаѓаат? Па, [0]. OOP. Алис е веќе во кој поврзани листа. 

Но, ако ние не се грижат за сортирање овие имиња, ние само може да се движи Алис завршена, вметнете Анита, но дури и тоа е постојана време. Дури и ако има Алис и Адам и сите овие други А имиња, тоа не е навистина ги менува физички. Зошто? Бидејќи ние едноставно не тука со поврзани листа, кој знае се овие јазли се и покрај тоа? Се што треба да направите е да се преселат на трошки од леб. Се движат стрелките околу, вие не мора да се физички се движат сите податоци наоколу. Значи можеме да вметнете Анита, во тој случај, веднаш. Постојана време. Значи имаме постојана време збор, и постојано работно време вметнување на некој како Анита. Но вид на oversimplifying светот. Што ако подоцна сакате да го најдете Alice? Што ако подоцна сакате да го најдете Alice? Колку чекори се што се случува да се земе? [Студентски одговор, неразбирливо] Точно. Бројот на луѓето пред Алиса во земјата на поврзани листа. Значи тоа не е сосема совршена, бидејќи нашите податоци структура, пак, ја има оваа вертикална пристап и тогаш има овие поврзани листи виси - всушност, да не привлече тоа е низа. Тоа овие поврзани листи виси надвор од неа дека изгледа малку нешто како ова. Но, проблемот е ако Алис и Адам и сите овие други А имиња заврши повеќе и повеќе таму, наоѓање на некој би можел да заврши преземањето еден куп чекори, bcause мора да напречни поврзани листа, која е линеарна операција. Значи, навистина, тогаш, вметнување време конечно е О (n), каде n е бројот на елементи во листата. Поделено со, нека произволно го нарекуваат м, каде m е бројот на поврзани листи што ја имаме во оваа вертикална оска. Со други зборови, ако навистина се претпостави униформа дистрибуција на имиња, целосно нереално. Таму е очигледно повеќе од некои букви од другите. 

Но ако претпоставиме за момент униформа дистрибуција, и ние n вкупниот луѓе, и м вкупно синџири достапни за нас, тогаш должината на секоја од овие синџири прилично едноставно се случува да биде вкупно n поделен со бројот на синџири. Значи n / m. Но, тука е местото каде што ние можеме да бидеме сите математички умен. m е постојана, бидејќи има фиксен број од овие. Сте ќе прогласи својата низа на почетокот, и ние не сме промена на големината на вертикалната оска. По дефиниција, тоа останува фиксен. Тоа е само хоризонталната оска, така да се каже, тоа се менува. Значи технички, ова е константа. Па сега, вметнување време е доста О (n). Така што не се чувствуваат сите дека многу подобро. Но, она што е вистината овде? Па, сето ова време, за неколку недели, ние сме биле велејќи О (n ²). О (n), 2 x n ², - n, поделен со 2. . . ech. Тоа е само n ². Но сега, во овој дел на семестарот, можеме да почнам да зборувам за реалниот свет повторно. И n / m е апсолутно побрзо отколку само n сам. Ако имате илјада имиња, и да ги растури во неколку кофи така што ќе имаат само десет имиња во секоја од овие синџири, апсолутно бараат десет работи ќе биде побрзо од илјада работи. И така еден од претстојните проблем сетови ќе ви предизвик да се размислува за точно дека иако, да, асимптоматично и математички, ова е сепак само линеарна, што смрди во целина кога се обидуваат да се најдат работи. Во реалноста, тоа ќе биде побрзо отколку што затоа што на овој делител. И така таму повторно ќе биде оваа трампа и овој конфликт помеѓу теоријата и стварноста, и еден од копчиња ќе започне претворање во овој момент во семестар е повеќе од реалноста како што вид на подготовка за крајот semster е, како ќе се воведат во светот на веб програмирање, каде што, навистина, претставата ќе се смета затоа што вашите корисници ќе почнете да се чувствувате и да ја цениме сиромашните дизајн одлуки. 

Па, како да одите за спроведување на поврзани - хаш табелата со 31 елементи? И претходниот пример е произволно за родендени. Ако некој има роденден на 1 јануари или февруари 1, ние ќе ги стави во оваа кофа. Ако е 2 јануари, февруари 2, 2 март, ќе ги стави во оваа кофа. Тоа е зошто тоа беше 31. Како да се прогласи хаш табелата? Тоа може да биде прилично едноставна, јазол * маса ми е произволно име за неа, [31]. Ова ми дава 31 совети како да јазли, и дека ми дозволува да имаат 31 совети како да се поврзани листи дури и ако тие синџири се на почетокот NULL. Што сакам да се стави ако сакате да го зачувате "Алиса", "Боб", "Чарли"? Па, ние треба да се заврши овие работи во структурата затоа што ние треба Алис да се укаже на Боб, да се укаже на Чарли, и така натаму. Ние не само да имаат имиња сам, па можев да се создаде нова структура наречена јазол тука. 

Што е вистински јазол? Што е јазол во оваа нова поврзани листа? Првото нешто, наречен зборот, е името на лицето. ДОЛЖИНА, веројатно, се однесува на максимална должина од името на луѓето, што и да е, 20, 30, 40 карактери во луди агол случаи, и 1 е за што? Тоа е само екстра NULL карактер, \ 0. Значи ова јазол е завиткување "нешто" во внатрешноста на себе, но исто така изјавува покажувач повика следниот така што можеме да снабдување Алис да Боб да Чарли и така натаму. Може да биде NULL, но не мора нужно да биде. Било какви прашања во врска со овие хаш маси? Да? [Студентски прашува прашање, неразбирливо] Низа - добро прашање. Зошто е ова знак збор во низа, а не само char *? Во овој донекаде произволна пример, јас не сакам да мора да прибегне да Примерок за секоја од оригиналните имиња. Сакав да се изјасни за максималниот износ на меморијата за низа така што можев да го копирате во структурата Алис \ 0 и не треба да се занимаваат со Примерок и слободни и слично. Но, јас не можеше да стори дека ако сакав да бидам повеќе свесни за просторот употреба. Добро прашање. Значи, да се обидат да се генерализира далеку од оваа и да се фокусира на остатокот од денес на структури на податоци поопшто и други проблеми кои може да се реши со користење на истите основи иако структури на податоци се може да се разликуваат во нивните детали. 

Значи излегува по компјутерски науки, дрва се многу чести. И може да се мисли на дрво вид како семејство дрво, каде што има некои корени, некои матриарх или патријарх, баба или дедо или порано назад, под кои се мама и тато или различни браќа и сестри или слично. Значи дрво структура има јазли и има деца, обично 0 или повеќе деца за секој јазол. И некои од жаргон што го гледате во оваа слика овде е која било од мали деца или grandkids на рабовите кои немаат стрели кои произлегуваат од нив, тие се т.н. лисја, и секој од внатре е внатрешен јазол, вие може да го наречеме нешто заедно оние линии. Но, оваа структура е прилично честа. Оваа една е малку произволна. Имаме едно дете од левата страна, имаме три деца на десната страна, две деца на дното лево. Значи можеме да имаме различна големина дрва, но ако почнеме да се стандардизираат работи, и може да се сети на оваа од видео Патрик на бинарни пребарување од претходниот кратко интернет, бинарна пребарување не треба да бидат имплементирани со низа или парчиња хартија на табла. Да претпоставиме дека си сакал да ги чувате вашите броеви во повеќе софистицирани податоци структура. Можете да креирате дрво се допаѓа ова. Вие би можеле да имаат јазол прогласена во C, и тој јазол може да има најмалку два елементи во него. Една од нив е бројот што сакате да го зачувате, а другата е - добро, ние треба уште еден. Другите е неговата деца. Значи тука е уште податочна структура. Овој пат, еден јазол е дефинирана како складирање на голем број n а потоа две насоки; левата дете и право дете. И тие не се произволни. Она што е интересно за ова дрво? 

Што е шема во тоа како ние сме изложени ова или како Патрик го положи во својот видео? Тоа е вид на очигледно дека има некои сортирање случува тука, но она што е едноставно правило? Да? [Студентски одговор, неразбирливо] Совршена. Ако се загледувам во ова, можете да го видите мал број на левата страна, голем број на левата страна, но тоа е вистина за секој јазол. За секој јазол, нејзината лева дете помало од него, и неговото право дете поголем од него. Што ова значи сега е ако сакате да пребарувате овие податоци структура за, да речеме, бројот 44, Морам да започне во корен, затоа што со сите овие посложени структури на податоци сега, имаме само покажувач кон една работа, на почетокот. И во овој случај, на почетокот е коренот. Тоа не е крајниот лев, тоа е коренот на оваа структура. Па гледам тука е 55, и јас сум во потрага по 44. Која насока сакам да одам? Па, јас сакам да одам лево, бидејќи очигледно, на правото ќе биде премногу голема. Значи забележите тука, ти си вид на концептуално сечкање дрвото на половина затоа што никогаш не се случува долу на десната страна. Па сега одам од 55 до 33. Тоа е премногу мали на број. Јас сум во потрага по 44, но сега знам дали 44 е во ова дрво, можам да одам очигледно десно. Значи, повторно, јас сум градинарски дрвото на половина. Тоа е доста идентични концептуално на телефонот книга. Тоа е идентично со она што го правевме со документи на табла, но тоа е многу пософистициран структура која ни овозможува да всушност прават оваа поделба и освојување од страна на дизајнот на алгоритам, и всушност, traversing структура вака - Whoops. Traversing структура како оваа, каде што тоа е само "одат овој начин или да одат на тој начин" значи сето тоа код кој свиткани вашиот ум прво кога нејзиното спроведување во делот или одење низ него дома, за бинарни пребарување, со користење на рекурзијата или повторување, тоа е болка во вратот. Најди средината елемент, а потоа направи вашиот заокружување нагоре или надолу. 

Има убавина тоа затоа што ние сега може да користи рекурзија, повторно, туку многу повеќе чисто. Всушност, ако сте во бројот 55 и сакате да најдете 44, одите лево во овој случај, тогаш што правиш? Вие се излагате на истиот алгоритам. Можете провери вредноста на јазол, тогаш одете лево или десно. Потоа ќе се провери вредноста на јазол, одете лево или десно. Ова е совршено прилагоден за рекурзија. Значи, иако во минатото сме го направиле некои прилично произволно примери вклучуваат рекурзија дека не треба да биде рекурзивен, со податоци stuctures, особено дрвја, тоа е совршен примена на оваа идеја на земање на проблемот, намалува, а потоа решавање на истиот тип на, но помали, програмата. 

Па таму е друга податочна структура која може да се воведе. Оваа една е дизајниран на прв поглед да изгледа криптичната, но овој е неверојатен. Значи ова е податочна структура наречена Trie, Trie, која е наследена од зборот пронаоѓање, кој не му е изречена повторно пробајте-вредност, но тоа е она што светот го нарекува овие работи. Се обидува. Т-R-i-e. Тоа е дрво структура на некој вид, но секоја од јазли во Trie се чини дека е она? И тоа е малку погрешно, бидејќи тоа е вид на скратен. Но, изгледа дека секој јазол во оваа Trie е всушност низа. И иако авторот на овој дијаграм не ја покажа, во овој случај, оваа Trie е податочна структура чија цел во животот е да ја запази зборовите како А-л-и-в-е или Б-о-б. И начинот на кој овие податоци продавници Алис и Боб и Чарли и Анита и така натаму е тоа што користи низа при што за чување Алиса во земјата на Trie, ние започнуваме на root јазол кој изгледа како низа, и тоа е напишано во стенографија нотација. Авторот исфрлени abcdefg бидејќи немаше имињата со тоа. Тие само покажа М и P и T, но во овој случај, ајде да се движат подалеку од Алис и Боб и Чарли некои имиња кои се тука. Максвел е, всушност, во овој дијаграм. Па, како помина на авторот продавница М-на-x-w-е-л-л? Тој или таа започна на root јазол, и отиде во [М], па околу 13, 13 локација во низа. Потоа од таму, има покажувач. А покажувачот води кон друга низа. Од таму авторот индексирани во таа низа на локација А, како што е прикажано таму во горниот лев агол, и тогаш тој или таа следи дека покажувачот на друга низа, и отиде да го покажувачот на локација X. Потоа во наредните низа локација W, E, L, L, и така натаму, и конечно, да всушност се обидуваат да се стави слика на тоа. Што значи еден јазол изгледа во кодот? А јазол во Trie содржи низа на совети на повеќе јазли. Но, има, исто така, мора да биде некој вид на логичка вредност, барем во оваа институција. Јас се случи да го наречеме is_word. Зошто? Бидејќи кога сте вметнување Максвел, вие не сте вметнување ништо во овој податочна структура. Вие не сте пишување М Вие не сте пишување X. Сите што го правиш е по совети. Покажувачот кој претставува М, тогаш покажувачот што претставува, тогаш покажувачот кој претставува X, тогаш W, E, L, L, но она што треба да направите на крајот е вид на одат, чек, стигнав до ова место. Имаше еден збор кој завршува тука во податочна структура. 

Значи она што Trie е навистина исполнет со и авторот одбрал да претставуваат овие terminuses со малку триаголници. Ова само значи дека всушност овој триаголник е тука, оваа логичка вредност на точно значи ако одите наназад во дрво, што значи зборот име Максвел е во ова. Но зборот foo, на пример, не е во дрво, бидејќи ако почнам на root јазол се тука на врвот, Нема ѓ покажувач, без покажувачот o, без покажувачот о. Foo не е име во овој речник. Но, од друга страна, Тјуринг, т-у-р-и-н-г. Повторно, јас не чувајте т или u или r или јас или n или е. Но јас не продавница во оваа податочна структура вредност на вистинскиот пат овде во овој јазол - во дрво поставете ја оваа логичка вредност на is_word на true. Па Trie е вид на овој многу интересен мета структура, каде што не си навистина чување на самите зборови за овој вид на речник. Да биде јасно, ти си само чување Да или Не постои збор кој завршува тука. 

Сега она што е импликација? Ако имате 150.000 зборови во речник што ќе се обидуваш да ги чувате во меморијата користење на нешто како поврзани листа, ви се случува да имаат 150.000 јазли во вашиот поврзани листа. И наоѓање една од овие зборови по азбучен ред може да потрае О (n) време. Линеарна време. Но, во случај тука на Trie, што е трчање време на изнаоѓање на збор? Излегува убавината тука е дека дури и ако имате 149.999 зборови веќе во овој речник, како имплементирани со оваа структура на податоци, колку време е потребно да се најде или внесете уште една личност во тоа, како Алис, Алис? Па, тоа е само 5, можеби 6 чекори за коса карактер. Бидејќи presense на други имиња во структурата не се добие на начин на вметнување Алис. Покрај тоа, наоѓајќи Алис еднаш постојат 150.000 зборови во овој речник не се во вашиот начин на наоѓање на Alice на сите, бидејќи Алис е. . . . . тука, бидејќи најдов логичка вредност. И ако не постои рационален точно, тогаш Алис не е во оваа податочна структура на зборови. Со други зборови, трчање време за наоѓање на работите и вметнување работи во оваа нова податочна структура на Trie е O на - тоа не е n. Бидејќи presense од 150.000 луѓе нема ефект врз Алис, се чини. Значи, да го наречеме k, каде k е максималната должина на зборот на англиски јазик која е обично не повеќе од 20-нешто карактери. So k е константа. Значи Светиот Грал ни изгледа да се најде сега е дека на Trie, постојана време за инсерти, за пребарувања, за бришење. Бидејќи бројот на нештата веќе во структурата, кои не се дури и физички таму. Повторно, тие се само вид на штиклирани, да или не, нема влијание врз неговата иднина трчање време. 

Но има мора да биде фатат, инаку ние не би се потроши толку многу време на сите овие други структури на податоци само за да конечно се дојде до тајната што е неверојатно. Значи она што цена сме ние плаќаат за да се постигне оваа величина тука? Простор. Оваа работа е голем. И причината поради која авторот не го претстави тука, забележи дека сите овие нешта кои изгледаат како низи, тој не привлече остатокот од дрво, остатокот од Trie, бидејќи тие не само релевантни за приказната. Но, сите овие јазли се супер широк, и секој јазол во дрвото зазема 26 или, всушност, може да биде 27 карактери, бидејќи во овој случај јас бев вклучувајќи простор за апостроф така што ние би можеле да имаат apostrophized зборови. Во овој случај, овие се широко низи. Значи, иако тие не се picutured, ова зазема голем износ на RAM меморија. Што може да биде во ред, especilly во модерната хардвер, но тоа е Губитокот. Ние се помалку време со трошење повеќе простор. Значи каде е сето ова оди? Па, ајде да направиме - да видиме овде. Да се ​​направи скок за овој човек овде. 

Верувале или не, како што многу забавно како C е за некое време сега, ние сме постигнување на точка во семестар каде што тоа е време да транзиција кон нешто повеќе модерна. Работи на повисоко ниво. И иако во наредните неколку недели ние се уште ќе продолжиме да се потопи во светот на покажувачи и управување со меморијата да се добие таа удобност со кој потоа ќе можеме да се изгради на, на крајот од играта е конечно да се воведе, иронично не, овој јазик. Ние ќе потрошиме, како 10 минути од разговорот за HTML. Сите HTML е е јазик за Селектирај, и што е јазик за Селектирај е е овие серија на отворен загради и затворени загради кои велат дека 'го прават овој храбар " "Прават овој закосени букви 'го прават овој центарот". Тоа не е сето тоа интелектуално интересно, но тоа е супер корисни. А тоа е секако сеприсутно овие денови. Но, она што е моќен за светот на HTML и веб програмирање поопшто, е изградба на динамична работи, пишување на код во јазици како PHP или Пајтон или Руби или Java или C #. Навистина, без разлика на вашиот јазик на избор е, и генерирање на HTML динамично. Генерирање на нешто што се нарекува CSS динамично. Cascading Style Sheets, која е исто така за естетика. И така иако, денес, ако одам на некои веб-сајт како познатите Google.com, и јас одам да ја видите, инвеститорот, погледнете извор, кој можеби сте го направиле пред, но ќе видите извор, овој материјал веројатно изгледа прилично криптичната. Но, ова е основниот код кој имплементира Google.com. На предниот крај. А всушност сето ова е меки естетика нешта. Ова е CSS се тука. Ако јас се задржи лизгање надолу ќе добиете некои боја нешта. Ова е HTML. Кодот на Google личи на хаос, но ако јас всушност се отвори друг прозорец, можеме да видиме некои структура на ова. Ако го отворам ова горе, забележи, тоа е малку повеќе читлив. Ние ќе се види пред долго оваа ознака, [зборот] е ознака, HTML, главата, телото, div, скрипта, текстот област, распон, центриран, DIV. И ова е, исто така, се најде на криптичната изглед на прв поглед, но сето ова хаос следи одредени шаблони, и повторливи обрасци, така што еднаш ќе го добиете основите надолу, ќе бидете во можност да се напише кодот вака а потоа манипулира кодот вака користење на уште еден јазик, наречен вклучите Javascript-. И JavaScript е јазик кој работи во внатрешноста на прелистувачот денес дека ние ги користиме на Харвард курсеви, за текот шопинг алатка која мапи користи да ви даде еден куп на динамизам, Фејсбук ти дава да се покаже инстант ажурирање на статусот, Твитер го користи за да ви покаже твитови веднаш. Сето ова ќе почнеме да се миеше внатре Но, за да одам таму, ние треба да се разбере малку нешто во врска со Интернет. Овој клип е тука само една минута долго, и да претпоставиме сега за сега ова е, всушност, како Интернетот работи како закачка за она што е за да дојде. Јас ви даде "воини на Нет." 

[♫ бавна хор музика ♫] [Машки нараторот] Тој дојде со една порака. Со протоколот сите свои. [♫ Побрзо електронска музика ♫] Тој дојде во светот на кул firewalls, незасегнатата рутери, и опасностите далеку полошо од смртта. Тој е брз. Тој е силен. Тој е TCP / IP, и тој има вашата адреса. Воини на Нет. [Malan] Следната недела, тогаш. Интернет. Веб програмирање. Ова е CS50. [CS50.TV]