[Музички] АНДИ Пенг: Добредојдовте на недела 6 на секција. Ние се отклонува од нашиот стандард време дел од вторник Попладнето на оваа прекрасна недела наутро. Ви благодариме за сите оние кои приклучи мене денес, но сериозно, аплауз. Тоа е прилично голем напор. Јас скоро и да не дури и го направи во тоа време, но тоа е во ред. Па знам дека сите од вас Само што го направи на квиз. Прво на сите, добредојде да На друга страна на тоа. Второ, ние ќе разговараме за тоа. Ќе зборуваме за квизот. Ние ќе зборуваме за тоа како што го правиш во класата. Ќе биде во ред. Имам вашето квизови за ви на крајот од тука, па ако момци сакаат да ги преземат погледне во него, сосема во ред. Толку брзо, пред да почне, агенда за денес е како што следува. Како што можете да видите, ние сме во основа брзо отпуштање преку целиот куп на структури на податоци навистина, навистина, навистина брзо. Па како таква, таа нема да биде супер интерактивни денес. Тоа само ќе биде мене вид на викање работи кои што, и ако ви се збуни, ако јас одам премногу брзо, да ме известите. Тие се само различни податоци структури, и како дел на вашиот pset за ова претстојната недела, ќе да се побара да се спроведе еден од нив, можеби две од them-- две од нив во вашиот pset. Добро, па јас сум само ќе започне со некои најави. Ние ќе одиме во текот Купишта и редици повеќе во длабочина од она што ние го сторивме пред квиз. Ние ќе одиме во текот поврзани листата повторно, уште еднаш, повеќе во длабочина од она што имавме пред квиз. А потоа ние ќе зборуваме за хаш маси, дрвја и неуспешни обиди, во која се прилично потребно за вашиот pset. И потоа ќе одиме во текот на некои корисни совети за pset5. Добро, па квиз 0. Просекот бил 58%. Тоа беше многу ниска, и така вие момци сите направи многу, многу добро во согласност со тоа. Прилично многу, непишано правило е ако сте во рок од една стандардна девијација на средната вредност особено бидејќи се наоѓаме во помалку удобни секција, ти си сосема во ред. Вие сте на вистинскиот пат. Животот е добар. Знам дека е страшно да се размислува дека Добив како 40% на овој квиз. Одам да пропадне оваа класа. Јас Ви ветувам, вие не сте ќе пропадне класата. Ти си сосема во ред. За оние од вас кои се здобија со текот средна вредност, импресивен, импресивен, како, сериозно добро направено. Јас ги имаат со мене. Се чувствуваат слободни да дојдат да ги добие на крајот на секција. Дозволете ми да знам ако имате било какви прашања, прашања со нив. Ако ние додадете вашиот резултат во ред, ги споделите со нас. Добро, па pset5, ова е навистина чудни недела за Јеил во смисла дека нашите pset се должи Среда на пладне вклучувајќи Кон крајот на денот, така што е, всушност, теоретски поради денеска на пладне. Веројатно никој не заврши во вторник на пладне. Тоа е сосема во ред. Ние ќе треба да се има на работното време Вечерва, како и во понеделникот вечерта. И сите делови на оваа недела ќе го всушност може да се претвори во работилници, па можете слободно да поп во секој дел што го сакате, и тие ќе бидат во вид на мини-pset работилници за помош на тоа. Така како што се, ова е само дел каде што ние сме наставен материјал. Сите други потези ќе се фокусира исклучиво на помош за pset. Да? ПУБЛИКАТА: Каде се работното време? АНДИ Пенг: Работно време tonight-- ох, добро прашање. Мислам дека работното време вечерва се во ТЕАЛ или на Ризницата. Ако ја изберете онлајн CS50 и да одите на работното време, треба да има распоред кој ви, каде што сите од нив се кажува. Знам или вечерва или утре е ТЕАЛ, и мислам дека може да има комонс за друга ноќ. Не сум сигурен. Добро прашање. Проверете на CS50. Кул, било какви прашања во врска со распоред за наредните три дена, како? Јас ветувам дека вие момци како Дејвид рече, ова е врвот на ридот. Вие момци се речиси таму. Само уште три дена. Одам таму, и тогаш сите ние ќе се сруши. Ќе имаме убав CS без пауза. Ќе се вратиме. Ние ќе се нурне во интернет програмирање и развој, работи кои се многу забавно споредба на некои од други psets. И тоа ќе биде студ, и ќе имаме многу забава. Ќе имаме повеќе бонбони. Жал ми е за слатки. Го заборавив бонбони. Тоа беше груба утро. Па вие сте речиси таму, и јас сум навистина горд на вас момци. Добро, па Купишта. Кој ги сака прашањето за Џек и неговата облека на квизот? Никој? Добро, тоа е во ред. Значи во суштина како што можете да слика Џек, овој човек овде, сака да ги преземе облека од врвот на магацинот, и тој го става назад кон магацинот откако тој е направено. Така на овој начин, тој никогаш не се чини дека се добива на дното на магацинот во неговата облека. Така овој вид на опишува основната структура на податоци за тоа како се спроведува оџак. Во суштина, се мисли на магацинот како и секоја магацинот на објекти каде што ќе се стави работите кон врвот, и потоа ќе ги поп надвор од врвот. Па LIFO е акроним што ни се допаѓа да use-- Последно, а прв. И така трае до врвот на Стек е првиот што излегува. И така на два мандата ние сакале да се дружат со кои се нарекуваат притисни и поп. Кога ќе се притисне нешто врз магацинот, и можете да го поп назад. И така претпоставувам дека ова е вид на апстрактен поим за оние од вас кои сакаат да видат како Крај на спроведувањето на оваа во реалниот свет. Колкумина од вас имаат напишано есеј можеби како еден час пред тоа се должи, и случајно избришиме огромен парче од него, како случајно? И тогаш што се направи контрола ние ги користиме за да го стави назад? Контрола-Зи, је? Контрола-Зи, така што износот на време кои го контролираат Зи го спаси животот, спасила мојот газ, во секое време кој е спроведен преку оџак. Во суштина сите информации што е на вашиот Word документ, таа добива се наметнува и појави по своја волја. И така во суштина секогаш кога ќе избришете нешто, можете да го поп назад. А потоа, ако е потребно, со што ви да извршат притисок, што е она што control-C е така. И светот функционира толку реално за тоа како едноставна структура на податоци може да помогне во вашиот секојдневен живот. Па struct е начинот на кој ние всушност го создаде оџак. Ние се дефинира тип struct, а потоа ние ја нарекуваме магацинот на дното. И во рамките на магацинот, имаме два параметри кои во суштина може да се манипулира, па ние имаме капацитет знак ѕвезда жици. Сето тоа го прави е создавање на низа дека ние може да се сместат што и да сакате која може да се утврди неговиот капацитет. Капацитет е само максималното количество на предмети што може да се стави во оваа низа. int големина е контра што ги држи пратите на колку предмети се во моментов во магацинот. Па тогаш можеме да ги пратите на тоа, А, и колку големи вистинските оџакот е, а, Б, колкав дел од тие магацинот ние исполнет бидејќи ние не сакаме до претекување поради, како што е нашиот капацитет. Така на пример, во оваа прекрасна прашање е на вашиот квиз. Во суштина како ние да им помогнам на кон врвот на магацинот. Прилично едноставна. Ако се погледне во него, ние ќе одиме преку ова. Ако [Беззвучен] size-- се сеќавам, секогаш кога ќе сакате да пристапите на некој параметар во рамките на struct, го прават името на struct.parameter. Во овој случај, s е името на нашиот оџак. Ние сакаме да се пристапи на големина од него, па правиме s.size. Така што додека големината не е еднаква на лице или како долг како што тоа е помалку од капацитет, или ќе работат тука. Сакате да пристапите на внатрешната на вашиот оџак, па s.strings, и ви се случува да се стави дека новиот број што сакате да го вметнете во таму. Да речеме ние ќе сакате да го внесете int n врз оџакот, можеме да направиме s.strings, загради, s.size еднаква на n. Поради големината е местото каде што ние во моментов се во магацинот ако ние се случува да им помогнам на тоа, ние само пристап каде големината е, тековната полнотата на магацинот, а ние им помогнам на int n врз него. А потоа ние сакаме да се осигураме дека ние сме, исто така, ја зголемува големината на n, за да можеме да ги пратите на тоа ние сме додаде екстра работа да магацинот. Сега имаме поголема големина. Дали ова тука имало смисла да се сите, како логично тоа функционира? Тоа беше вид на брз. ПУБЛИКАТА: Можете ли да одиме во текот на s.stringss.strings [s.size] повторно? АНДИ Пенг: Секако, така што она што го прави тоа s.size моментов ни ја даде? ПУБЛИКАТА: Тоа е моменталната големина. АНДИ Пенг: Точно, така што Тековниот индекс на нашите големина е во, и затоа сакаме да се стави нова цел број кои сакаме да ги вметнете во s.size. Дали тоа има смисла? Бидејќи s.strings, сето она што е е името на низата. Сето тоа е се што пристапуваат на низа во рамките на нашите struct, и така, ако сакаме да поставите n во тој индекс, ние само може да го пристап користење s.size загради. Кул. Добро, поп, го pseudocode надвор за вас момци, но сличен концепт. Дали тоа има смисла? Ако големината е поголема од нула, тогаш знаете дека сакате да се земе нешто надвор, бидејќи ако големината не е поголем од нула, тогаш немаш ништо во магацинот. Па вие само сакате да се изврши овој законик, тоа само може да pop ако има нешто од поп музиката. Па ако големината е поголема од 0, ние минус големина. Ние опаѓа големината и потоа да се вратат она што е во него, бидејќи со пукање, ние сакаме да пристап што и да се чуваат во индексот на врвот на магацинот. Сè што има смисла? Ако сум направил вие момци пишувам ова, би вие момци можат да се напише? Добро, вие момци можат да се позанимавам со неа. Не се грижи, ако не го добие. Ние немаме време да се код го ова денес, бидејќи ние сме доби многу на овие структури да се оди преку, но во суштина pseudocode, многу, многу слични да им помогнам. Само да го следат заедно логиката. Бидете сигурни дека ќе се пристапува на сите карактеристики на вашиот struct правилно. Да? ПУБЛИКАТА: Дали овие слајдови и целата оваа работа да биде до денес-носталгичната? АНДИ Пенг: Секогаш, Да. Одам да се обиде да го стави овој горе како еден час после. Јас ќе мејл Дејвид, Дејвид ќе се обиде да го стави како еден час по ова. Добро, па потоа да се движиме во оваа друга прекрасна податоци структура наречена редица. Како вие момци можат да се види тука, на дното, за Британците меѓу нас, сето тоа е една линија. Така спротивно на она што мислите дека магацинот е, задача е токму она што логично е што мислам дека е. Се одржува со правилата на FIFO, кој е прв, а прв. Ако сте прв еден во низата, ти си првиот што излегува на линијата. Значи она што сакаме да го нарекуваме овој е dequeueing и enqueueing. Ако сакаме да додадете нешто на нашата листа на чекање, ние Стави во ред. Ако сакаме да dequeue, или да нешто далеку, ние dequeue. Па истото чувство дека ние сме вид на создавање елементи фиксна големина кои ги може да се сместат одредени работи, но ние исто така може промени каде што ние сме поставување параметри внатре од нив врз основа на тоа каков тип на функционалност сакаме. Купишта така, сакавме последните еден, N за да биде првиот надвор. Ред е што сакаме првата работа во да биде првото нешто надвор. Па на struct тип се дефинира, како што можете да видите, тоа е малку поинаква од она што беше на оџакот затоа што не само што ќе мора да се задржи следи каде големината е моментално, ние, исто така, сакаат да ги пратите на главата како и тоа каде сме сега. Па мислам дека тоа е полесно ако јас се подготви ова. Значи, да се замисли ние го добивме на листа на чекање, па да речеме на главата е во право тука. Шефот на линија, ајде само да се каже дека е таму во моментов, и ние сакаме да внесете нешто во редот. Одам да се јавите големина суштина е истото што и опашка, на крајот од каде вашиот ред е. Да речеме големина е во право тука. Значи, како некој feasibly внесете нешто во ред? Што индекс сакаме да се одржи каде што сакате да го вметнете во. Ако ова е почетокот на Вашиот задача и ова е крајот на тоа или големината на тоа, каде што го правиме сакате да го додадете следниот објект? ПУБЛИКАТА: [Беззвучен] АНДИ Пенг: Токму така, сакате да го додадете во зависност од тоа сте го напишале. Или ова не е празно или дека не е празно. Па сакате да го додадете веројатно тука, бидејќи ако големината is-- доколку овие сите се полни, сакате за да го додадете во право тука, нели? И така тоа е, додека многу, многу едноставно, не баш секогаш точни бидејќи главната разлика помеѓу редот и магацинот е дека задача може всушност, да се манипулира така што промените на главата во зависност од каде што сакате на почетокот на вашиот знак, за почеток. И како резултат на тоа, вашиот опашка е исто така се случува да се промени. И така да ги разгледаме во овој код во моментов. Како вие момци исто така беа замолени да напише на квизот, Стави во ред. Можеби ќе се зборува низ зошто одговорот беше она што беше. Не можев сосема одговара на оваа линија на еден, но во суштина овој дел од кодот треба да биде во една линија. Трошат како 30 секунди. Погледнете, и да видиме зошто ова е начинот на кој таа е. Многу, многу слични struct, многу, многу слична структура како и претходните магацинот освен можеби една линија код. И дека една линија код одредува функционалност. И тоа навистина го издвојува редица од оџак. Секој сака да земе прободе да се објасни причините зошто го добив оваа комплицирана работа во оваа ситуација? Гледаме враќањето на нашите прекрасен модул пријател. Како вие момци наскоро ќе дојде да се препознае во програмирање, речиси во секое време ви треба нешто да се заврши околу било што, модул ќе биде начин да го направи тоа. Па знаејќи дека, дали некој сака да се обиде објаснувајќи дека линија код? Да, сите одговори се прифатени и добредојдени. ПУБЛИКАТА: Дали сте зборуваме за мене? АНДИ Пенг: Да. ПУБЛИКАТА: О, не ми е жал. АНДИ Пенг: Во ред, па ајде прошетка низ овој код. Па кога ќе се обидуваш да се додадете нешто кон дното, во прекрасната случај дека шефот случува да се биде тука, тоа е многу лесно за нас само да се оди до крај внесете нешто, нели? Но целата поента на ред е дека шефот всушност може динамички менува во зависност од каде што сакам самиот почеток на нашиот q за да биде, и како такво, на опашката е исто така се случува да се промени. И така се замисли дека ова не беше на дното, туку ова е листа на чекање. Да речеме, на главата е во право тука. Да речеме дека нашата задача изгледа вака. Ако сакаме да се префрлат во која на почетокот на линија, е, Да речеме дека ние се префрли главата На овој начин и големини тука. Сега сакаме да додадете нешто на оваа задача, но како што вие момци можат да се види, тоа не е толку едноставно како што е да се само додадете она што е по големина затоа што тогаш ќе ги потрошиме границите на нашите вистински низа. Каде би сакале да додадете навистина е тука. Тоа е убавината на редица е во тоа што за нас, визуелно го личи на линија оди вака, но кога се чуваат во податочна структура, тие го даде како што е како еден циклус. Тој вид на се обвива околу на предниот дел на ист начин која линија, исто така може да заврши околу зависност од каде и да сакате да го почетокот на линијата да биде. И така, ако ги погледне надолу тука, ајде велат дека сакавме да се создаде функција наречена Стави во ред. Сакавме да додадете int n во тоа н. Ако q.size q-- ние ќе го наречеме дека нашите податоци structure-- ако нашите queue.size не еднаква на капацитет или ако тоа е помалку од капацитет, q.strings е низа во рамките на нашите q. Ние ќе треба да се постави дека еднаква q.heads, кој е во право тука, плус q.size модул од страна на капацитет, што заврши ни назад околу тука. Така што во овој пример, индексот на главата е 1, нели? На индекс на големина е 0, 1, 2, 3, 4. За да можеме да се направи 1 плус 4 модул од страна на нашиот капацитет кој е на 5. Што ни даде? Што е индекс, кој ќе излезе од ова? ПУБЛИКАТА: 0. АНДИ Пенг: 0, што се случува да биде тука, и затоа сакаме да биде во можност да се вметне во право тука. И така оваа равенка тука вид од само работи со било кој број зависност од тоа каде вашиот главата и вашата големина се. Ако знаете што тие работите се, знаеш точно каде сакате да го вметнете што и да е, по својата задача. Дали тоа има смисла за секого? Знам вид на мозокот закачка особено бидејќи ова дојдоа во последиците на вашиот квиз. Но се надевам дека сите сега може да се разбере зошто ова решение или ова функција е начинот на кој таа е. Секој малку нејасни за тоа? ВО РЕД. И така сега, ако сакаше да dequeue, овој е местото каде нашата глава ќе биде менувањето затоа што ако ние требаше да dequeue, ние не ги тргнеме на крајот на q. Ние сакаме да ги тргнеме на главата, нели? Па како резултат на тоа, шефот ќе се промени, и тоа е причината зошто, кога ќе Стави во ред, вие мора да ги пратите на каде главата и вашата големина треба да биде во можност да се вметне во правилна позиција. И така, кога ќе dequeue, Јас, исто така го pseudocode надвор. Се чувствуваат слободни да ако сакате да се направи обид за кодирање ова. Сакате да се движат на главата, нели? Ако сакав да dequeue, јас ќе се движат на главата над. Ова ќе биде на чело. И нашите сегашни големина ќе одземе затоа што ние веќе не има четири елементи во низата. Имаме само три, а потоа ние сакаме да се врати она што беше се чуваат внатре на главата, бидејќи сакаме да ја искористам оваа вредност од толку многу слична на магацинот. Само сте преземање од некое друго место, и ќе мора повторно да го пренесе вашиот покажувач до друго место, како резултат. Логично, секој следат? Одлично. Добро, така што ние ќе треба да се зборува малку повеќе во длабочина за поврзани листи затоа што ќе биде многу, многу вредни за вас во текот на оваа недела psets. Поврзани листи, како вие момци да се сетам, сите тие се се јазли што се јазли на одредени вредности на двете вредност и покажувач кои се поврзани заедно од страна на оние покажувачи. И така на struct за тоа како ние создаваме јазол еве ние имаат int n, што е без оглед на вредноста во продавница или стринг n или што и да сакате да го го нарекуваат, знак ѕвезда о. Struct јазол ѕвезда, што е покажувачот што сакате да го имаат во секој јазол, сте ќе го имаат тоа покажувачот точка кон следниот. Ќе мора на шефот на која е поврзана листа ќе укажуваат на остатокот од вредностите така натаму и така натаму додека не се на крајот да стигне до крајот. И ова е само последен јазол случува да не имаат покажувач. Тоа се случува да се укаже на нула, а тоа е кога знаете дека сте го погоди крајот на вашиот поврзани листа е кога последен пат го покажувачот не укажуваат на ништо. Па ние ќе одиме малку повеќе во длабочина за тоа како еден би веројатно пребарување на поврзани листа. Се сеќавам што се некои од недостатоци на поврзани листи стихови низа однос пребарувања. Низа можеш бинарни пребарување, но Зошто не можете да го направат на поврзани листа? ПУБЛИКАТА: Поради тоа што сите тие се поврзани, но не сосема знаат каде [Беззвучен]. АНДИ Пенг: Да, токму така се сеќавам дека брилијантноста на низа е фактот дека имавме меморија за случаен пристап, каде што ако сакав вредност од индексот шест, јас само може да се каже индекс шест, ми даде таа вредност. И тоа е затоа низи се сортирани во соседни простор на меморија на едно место, додека вид на поврзани листи по случаен избор се прошарани сите околу себе, и единствениот начин на кој може да се најде еден е преку покажувач кој ви кажува на адресата на која што следниот јазол е. Па како резултат на тоа, единствениот начин за да пребарувате низ поврзани листа е линеарно пребарување. Бидејќи јас не знам каде точно 12-та вредност на поврзани листа е, Морам да напречни интегритет од кои една поврзана листа од страна на еден од главата во првиот јазол, на вториот јазол, на третиот јазол, сите патот надолу се додека конечно се за тоа каде тој јазол го барам е. И така, во таа смисла, барај на поврзани листа е секогаш n. Тоа секогаш е n. Тоа секогаш е во линеарно време. И така го кодот во кои ние спроведување на оваа, а оваа е нешто ново за вас, бидејќи вие момци момци имаат навистина не зборуваше за тоа или кога било види совети за тоа како да пребарување низ покажувачи, па ние ќе одиме преку ова е многу, многу бавно. Па пребарување bool, десно, ајде да замислиме што сакаме за да се создаде функција наречена пребарување кој враќа true ако најде вредност во внатрешноста на поврзани листа, и таа се враќа false поинаку. Листа со омилени јазол е во моментов само на покажувачот на првата ставка во вашата поврзани листа. int n е вредноста која сте бараат во таа листа. Па јазол ѕвезда покажувачот еднаква на листата. Тоа значи дека ние сме поставување и создавање на покажувачот за да се дека првиот јазол во внатрешноста на листата. Секој со мене? Значи, ако ние требаше да одат врати тука, ќе морам иницијализиран покажувач кој укажува на шефот на што и да е листа. А потоа, откако ќе се фаќате тука, додека покажувачот не еднакви нула, така што е јамка во која се наоѓаме ќе биде дополнително traversing остатокот од нашата листа затоа што се случува кога покажувачот е еднаква на нула? Ние знаеме дека ние have-- ПУБЛИКАТА: [Беззвучен] АНДИ Пенг: Точно, па знаеме дека ние сме стигнале до крајот на листата, нели? Ако се вратиме тука, секој јазол треба да се укажува на друг јазол и така натаму и така натаму додека не го погоди на крајот опашката на вашиот поврзани листа, која има покажувач дека само не укажуваат било каде, освен бр. И така треба да знаете дека во основа Вашата листа е сеуште таму нагоре додека покажувачот не е еднакво на нула затоа што еднаш тоа е еднакво на нула, знаеш дека нема повеќе нешта. Па тоа е циклус во кој ние сме ќе имаат вистински пребарување. А ако pointer-- гледате тој вид на стрелката функција таму? Па ако покажувачот поени на n, ако покажувачот на n еднаква еднаква n, па тоа значи дека ако покажувачот дека сте бараат на крајот на секоја јазол е всушност еднаков на вредноста што го барате, а потоа сакате да се вратите точно. Значи, во основа, ако сте на еден јазол кој има вредност која што го барате, знаете дека сте биле можност успешно пребарување. Во спротивно, ќе сакате да го поставите покажувачот на следното јазол. Тоа е она што таа линија, тука е тоа. Покажувачот еднаква на покажувачот следната. Секој се види како тоа е работат? И во суштина си оди за да се само напречни целината на листата, ресетирам вашиот покажувач секое време до ти на крајот хит на крајот на листата. И знаеш дека не постојат повеќе јазли за да пребарувате низ, а потоа можете да се вратите лажна затоа што знаете дека, добро де, ако јас сум бил во можност да пребарување преку севкупноста на листата. Ако во овој пример, ако сакав да се погледне за вредност од 10, и јас со почеток во главата, и Јас пребарување на целиот пат, и јас конечно стигнав до оваа, која покажувач кој укажува на нула, Знам дека, глупости, претпоставувам дека 10 не е во оваа листа, бидејќи не можев да го најдам. И јас сум на крајот на листата. И во кој случај ќе се знае Одам да се врати лажни. Дозволувајте тоа да се впие во за малку. Ова ќе биде убава важно за вашиот pset. Логиката на тоа е многу едноставно, можеби синтаксички само да го спроведат. Вие момци сакаат да направат сигурни дека ќе се разбере. Кул. Ok, па како ние би биле вметнување јазли, десно, во листата, бидејќи се сеќавам Кои се придобивките од она што на постоење на поврзани листа наспроти низа во однос на чување? ПУБЛИКАТА: Тоа е динамичен, така што е полесно to-- АНДИ Пенг: Токму така, така што е динамично што значи дека може да се прошири и да се намали во зависност од потребите на корисникот. И така, во таа смисла, ние не треба да губите непотребни меморија, бидејќи јас ако не знам колку вредности сакам до продавница, тоа не дава никаква смисла за мене да се создаде низа бидејќи ако сакам да се сместат 10 вредности и јас се создаде низа на 1.000, што е многу потроши меморија распределени. Тоа е причината зошто ние сакаме да се користи во врска листа за да бидат во можност да се динамички се менува или да се намали нашата големина. И така што го прави вметнување малку посложена. Бидејќи ние не може случајно да пристапите елементи начинот на кој ние би на низа. Ако сакам да се вметне елемент во седмата индекс, Јас само може да го вметнете во седмата индекс. На поврзани листа, тоа не го прави тоа доста работи како лесно, и така, ако сакавме да го вметнете Од една тука во поврзани листа, визуелно, тоа е многу лесно да се види. Ние само сакаме да го вметнете во право, таму, правото на почетокот на листата, веднаш по главата. Но начинот на кој ние треба да го распореди покажувачи е малку згрчена или, логично, тоа го прави смисла, но вие сакате да бидете сигурни дека можете да го имаат целосно надолу, бидејќи последно нешто што сакате е да го распореди на покажувачот начинот на кој што го правиме тука. Ако dereference на покажувачот од глава до 1, потоа одеднаш на остатокот од вашата поврзани листа е изгубена, бидејќи не сте, всушност, креира привремен ништо. Кој укажа на 2. Ако го преназначаване на покажувачот, тогаш остатокот од вашата листа е целосно изгубена. Значи сакате да бидете многу, многу внимателен тука прво да му ја додели на покажувачот од она што ќе го сакате да го вметнете во каде и што го сакате, а потоа ќе може dereference остатокот од вашата листа. Така ова се однесува за каде ќе се обидуваш да се вметне во. Ако сакате да го вметнете во главата, ако сакате да се одговори тука, ако сакате да ги внесете во На крајот, и, на крајот јас Претпоставувам дека би само Немате покажувач, но вие сакате да бидете сигурни дека ќе не направи изгуби остатокот од вашата листа. Вие секогаш сакате да бидете сигурни дека Вашиот нов јазол е да се покажува кон она што сакате да го вметнете во, а потоа можете да го додадете врзувањето на. Секој јасно? Ова се случува да биде еден од вистинските прашања. Еден од повеќето големи проблеми ви се случува да имате на вашиот pset е дека си оди за да се обиде да создаде на поврзани листа и вметнете работи но тогаш едноставно изгуби остатокот од вашата поврзани листа. И ви се случува да се биде како, јас не знам зошто ова се случува? И тоа е болката да се оди преку и пребарување на сите ваши покажувачи. И јас ви гарантирам на овој pset, пишување и цртање овие јазли надвор ќе биде многу, многу корисни. Па не може целосно да ги пратите од каде што сите ваши покажувачи се, она што се случува во ред, каде сите ваши јазли, она што треба да направите за да пристапите или вметнете или бришење или било кој од нив. Секој добар во тоа? Кул. Значи, ако сакаме да се погледне на кодот? О, јас не знам дали ние може да се види the-- ОК, значи на врвот на сите што е е во функција именуван вметнете каде сакаме за да вметнете int n во поврзаните листа. Ние ќе треба да се оди преку ова. Тоа е многу код, многу нови синтакса. Ќе биде во ред. Па на врвот, секогаш кога ние сакаме да се создаде ништо што ни е потребно да се направи, особено ако сакате тоа да не бидат зачувани на оџакот но во грамада? Одиме во Примерок, нели? Па ние ќе се создаде покажувачот. Јазол, покажувач, нови еднаквите Примерок од големината на еден јазол затоа што ние сакаме тој јазол да биде создадена. Ние сакаме на износот на меморија што еден јазол зазема што треба да се распределени за создавањето на новиот јазол. И тогаш ние ќе треба да се провери да се види дали новиот еднаквите еднакво на нула. Се сеќавам она што го кажавме? Што и да Примерок, она што мора секогаш да направам? Треба секогаш да се провери да се види дали или не тој е нула. На пример, ако вашиот оперативен системот е целосно полна, ако нема повеќе меморија на сите и ќе се обидат да Примерок, тоа ќе се врати нула за вас. И така, ако се обидете да го користите кога беше укажува на нула, вие нема да се во можност за пристап до тие информации. И така, како такви, сакавме да се направи Осигурајте се дека кога сте mallocing, ти си секогаш проверка за да види дали тој спомен на тебе е нула. И ако тоа не е, тогаш може да се движи на со остатокот од нашиот код. Па ние ќе треба да иницијализира на новиот јазол. Ние ќе треба да се направи нов n еднаква на n. И тогаш ние ќе треба да се направи постави нови покажувачот на нови на нула, бидејќи во моментов ние не сакам ништо за тоа да се насочува. Немаме поим каде тоа се случува да се стави, а потоа, ако сакаме да вметнете ја во главата, тогаш можеме да преназначаване покажувачот на главата. Дали секој следат логиката од каде што се случува? Сите ние сме прави е создавање на нов јазли, поставување на покажувачот на нула, а потоа и прераспределување тоа на главата ако ние Знаеме дека сакате да го вметнете во главата. А потоа на главата ќе точка кон тој нов јазол. Секој ред со тоа? Така, тоа е процес од два чекори. Имаш да се Прво доделете она што ќе го создаде. Во собата што покажувачот на повикување, а потоа ќе да вид на dereference првиот покажувач и насочете го кон нов јазол. Каде сакате да го вметнете, таа логика ќе се одржи точно. Тоа е вид на како доделување привремени променливи. Се сеќавам, имаш за да бидете сигурни дека ќе не се изгуби патеката на ако сте Замена. Вие сакате да бидете сигурни дека ќе имаат привремена променлива таква држи следи каде што нешто се чуваат, така што ќе не губат било која вредност во текот на како Месинг околу со него. Добро, така што кодот ќе биде тука. Вие момци ги разгледаме по дел. Тоа ќе биде таму. Па претпоставувам колку чини ова се разликуваат, ако сакавме да се вметне во средината или на крајот? Дали некој има идеја за она што е pseudocode како логична референца дека ќе ги преземе ако сакавме за да го внесеш во средината? Значи, ако сакаме да го вметнете во шеф, сите ние го правиме е да се создаде нов јазол. Ние го поставите покажувачот на таа нов јазол на она што на главата, а потоа во собата на главата на новиот јазол, нели? Ако сакавме да го внесеш во средината на листата, што ќе имаме да се направи? ПУБЛИКАТА: Тоа би уште биде сличен процес на, како и доделување на покажувачот тогаш назначување дека покажувач, но ќе треба да се лоцира таму. АНДИ Пенг: Точно, токму така истиот процес, освен тебе мора да се лоцира каде точно сакаат дека новите покажувачот да одат во, па ако сакам да го вметнете во средината на поврзани list-- ред, ајде да речеме дека е наша поврзани листа. Ако сакаме да го внесеш токму тука, ние ќе треба да се создаде нов јазол. Ние ќе треба да Примерок. Ние ќе треба да се создаде нов јазол. Ние ќе треба да му ја додели на покажувачот на овој јазол тука. Но, проблемот кој се разликува од каде што главата е е дека ние точно знаел која главата е. Дека тоа е правото на првото, нели? Но тука ние мора да ги пратите од каде што ние сме вметнување во. Ако ние се нашата вметнување јазол тука, ние го добивме за да бидете сигурни дека на една тема на овој јазол е онаа која reassigns покажувачот. Па тогаш мора да се вид на ги пратите на две работи. Ако ги пратите на тоа каде тоа јазол во моментов е вметнување во. Можете исто така треба да ги пратите на тоа каде претходниот јазол дека сте во потрага на исто така беше таму. Секој добар во тоа? ВО РЕД. Како за ставање во крајот? Ако сакав да го додадете here-- ако сакав за да додадете нов јазол до крајот на листата, како би можел да се обратите за тоа го прават? ПУБЛИКАТА: Значи, во моментов, Последната укажувале ништовни. АНДИ Пенг: Да. Точно, така што ова во моментов е насочен да се знае, и така претпоставувам, во оваа смисла, тоа е многу лесно да додадете до крајот на листата. Се што треба да направите е да го поставите еднакви на нула, а потоа бум. Право, таму, многу лесно. Многу едноставна. Многу сличен на главата, но логично вас сакате да бидете сигурни дека чекорите ве однесе кон правење било од тоа, ти си по должината. Тоа е многу лесно да се, во средината на вашиот код, да се фатат за, ох, имам толку многу покажувачи. Не знам каде нешто е да се покажува. Јас дури и не знаат кој јазол јас сум на. Што се случува? Релаксираат, се смири, земе длабок здив. Извлече вашата поврзани листа. Ако ти кажам, знам каде точно Јас треба да го вметнете ова во и знам точно како да го распореди на мојот покажувачи, многу, многу полесно да се слика out-- многу, многу полесно да не да се изгуби во грешки на вашиот код. Секој ред со тоа? ВО РЕД. Па претпоставувам концепт кој не сме навистина разговаравме за пред сега, и јас ќе се погоди веројатно не ќе се судрите со многу yet-- тоа е вид на напредна concept-- е дека ние, всушност, имаат податоци структура наречена двојно поврзана листата. Така што вие момци можат да се види, сите ние сме прави е создавање вистинска вредност, екстра покажувачот на секоја од нашите јазли што исто така укажува на претходниот јазол. Затоа, не само што имаме нашите јазли укажуваат на следниот. Тие, исто така, укажуваат на претходниот. Одам да ги игнорира овие две моментов. Па тогаш имате синџир кои можат да се движат во двете насоки, и тогаш тоа е малку полесно да логично следат заедно. Како тука, наместо следење на, ох, се Треба да знаете дека овој јазол е оној што морам да го распореди, Јас само може да оди тука и само се повлече претходната. Тогаш знам точно каде што е, а потоа ќе немора да напречни целината на поврзани листа. Тоа е малку полесно. Но, како што се, ќе мора двојно износот на покажувачи, што е двојно повеќе од количината на меморија. Тоа е многу совети како да ги пратите. Тоа е малку посложена, но тоа е малку повеќе корисник пријателски зависност на она што се обидуваат да се постигне. Значи овој тип на податоци структура сосема постои, и структурата за е многу, многу едноставна освен сите што си имаат е, наместо само покажувач на следниот, можете исто така имаат покажувач на претходната. Тоа е се што разликата беше. Секој добар во тоа? Кул. Добро, па сега сум навистина да поминат веројатно како и од 15 до 20 минути, или најголемиот дел на остатокот од времето во делот Станува збор за хаш маси. Колкумина од вас момци Ги прочитав pset5 спецификации? Добро, добро. Тоа е поголем од 50% од нормално. Во ред е. Така што вие момци ќе видиме, ти си предизвик во pset5 ќе биде да спроведе речникот каде што ќе се вчита над 140.000 зборови што ние ви даде или проверка на правопис тоа против сите на текстот. Ние ќе ви дадеме случаен парчиња на литературата. Ние ќе ви дадеме Одисеја. Ние ќе ви дадеме Илијада. Ние ќе ви дадеме Остин сили. И вашиот предизвик ќе биде да се проверка на правопис секој еден збор во сите на оние речници во суштина со нашите проверува правописот. И така има неколку делови на создавање на овој pset, прво што сакате да биде можност да всушност се вчита сите зборови во вашиот речникот, а потоа ќе сакаат да бидат во можност да проверка на правописот сите од нив. И така како што се, ви се случува да се бара структура на податоци што може да го направите ова брзо и ефикасно и динамично. Па претпоставувам најлесниот начин да го направите ова, најверојатно, ќе се создаде низа, нели? Најлесен начин на чување на вас е може да се создаде низа на 140.000 зборови и само да ги ставите сите таму и потоа да ги напречни преку бинарни пребарување или со селекции или not-- Жал ми е што го средат. Може да ги подредувате и потоа да ги напречни со бинарна пребарување или само линеарно пребарување и само во финалето на зборови, туку дека зема огромна сума на меморија, и тоа не е многу ефикасен. И така ние се случува да започне Станува збор за начини за правење нашето време работи поефикасно. И нашата цел е да се добие постојана време каде тоа е речиси како низи, каде имате моментален пристап. Ако сакав да барате ништо, Сакам да бидам во можност да само, бум, таа се најде точно, и извлечете ја. И така структура во која ние ќе се станува многу блиску за да биде во можност за пристап до постојана време, овој светиот грал во програмирање на постојана време се нарекува хаш табелата. И така Давид претходно рековме на [Беззвучен] малку во предавањето, но ние се случува да навистина нурне длабоко во оваа недела на парче што е во врска со како хаш табелата работи. Па начинот на кој хаш маса дела, на пример, ако сакав да ја запази еден куп на зборови, куп на зборови во англискиот јазик, Јас теоретски би можеле да се стави банана, јаболко, киви, манго, пар, и диња сите на само низа. Сите тие може да се вклопат во и да се најде. Тоа би било вид на болка да се пребарување и пристап, но на полесен начин да се направи ова е дека ние, всушност, може да се создаде структура вика хаш табелата, каде што хаш. Трчаме сите наши клучеви преку хеш функција, равенка, дека сите ги претвора во некој вид на вредност кој потоа ќе можеме да ги чувате со излез суштина низа на поврзани листа. И така тука, ако сакавме за чување на англиски зборови, ние потенцијално би можеле само, јас не Знаете, се претвори сите на првите букви во некој вид на број. И така, на пример, ако сакав А за да биде синоним за apple-- или со индекс на 0, и Б да биде синоним за 1, може да имаме 26 записи дека само може да се сместат сите букви од писмо дека ќе се започне со. И тогаш можеме да имаме јаболко на индексот на 0. Ние може да има банана на индексот на 1, диња во индексот на 2, и така натаму и така натаму. А со тоа и да сакав да го бара мојата хаш табелата и пристап јаболко, Знам дека Apple ќе почне со А, и знам точно дека мора да биде и на хаш маса во индекс 0, бидејќи на функцијата претходно доделени. Па не знам, ние сме програма во која корисникот ќе биде обвинет не arbitrarily-- произволно, со обидот да се смислено мислам на добар равенки за да може да се шири од сите на вашите вредности на некој начин тие можат лесно да пристапите тоа подоцна со како равенка кои ви се, себе си, знам. Па во таа смисла, ако сакав да се оди на манго, знам, ох, тоа започнува со м. Тоа мора да биде на листата на 12. Јас не мора да пребарувате низ ништо. Знам exactly-- јас само може да оди на индексот на 12 и повлечете тоа. Сите јасни за тоа како еден функција хаш табелата е работи? Тоа е вид на само една покомплексна низа. Тоа е се што и да е. ВО РЕД. Па претпоставувам дека трчаме во ова прашање на она што се случува ако имаш повеќе работи кои ви даде истиот индекс? Така велат нашите функција, сето тоа го направив беше да се земе дека првата буква и се претвори дека во соодветните 0 преку 25 индекс. Тоа е сосема во ред, ако имате само една на секој. Но, во втората ќе почнете има повеќе, ти си случува да имаат она што се нарекува судир. Значи, ако јас се обидувам да внесете го закопа во хаш маса која веќе има банана на неа, што ќе се случи кога ќе се обидат да се вметне тоа? Лоши работи затоа банана веќе постои во рамките на индексот што сакате да го складирате во. Бери вид е како, ах, она што можам да направам? Не знам каде да одат. Како можам да се реши тоа? И така ќе ви момци вид на види го правиме тоа слабо нешто секаде каде што можеме, всушност вид на создаде поврзани листа во нашата низи. И така најлесно да се размислува за тоа, сите хаш табелата е низа на поврзани листи. И така, во таа смисла, треба да оваа прекрасна низа од покажувачи, а потоа секој покажувачот во таа вредност, во тој индекс, всушност, може да укажуваат на други работи. И за да можете да ги имаат сите овие одделни Синџири излетаат на една голема низа. И така тука, ако можам сакаше да внесете Бери, Јас знам, во ред, јас ќе одам да го внесете тоа преку мојот хеш функција. Одам да се заокружи со индексот на 1, а потоа јас ќе одам да се биде во можност да имаат само еден помал подмножество на овој гигант 140.000 збор речникот. И јас тогаш може само да се погледне преку 1/26 од тоа. И така, тогаш јас само може да внесете Бери пред или по банана во овој случај? По, нели? И така ќе се случува да сакаат да вметнете овој јазол по банана, и така си оди за да се вметне на опашката на таа поврзани листа. Одам да се вратиш на оваа тема слајд, па вие момци можат да се види како хаш функција работи. Па хеш функција е оваа равенка дека сте водење вид на вашиот влез преку да добиете она што индекс што сакате да го доделите насока. И така, во овој пример, сите сакавме да направат е да се земе на првата буква, се претвори дека во индекс, тогаш ние кои може да се сместат во нашата хеш функција. Сите што го правиме тука е дека сме конвертирање на првата буква. Па keykey [0] е само првата буква на она што низа што ги имаме, ние сме поминува во. Ние сме конвертирање дека на горниот дел, и ние сме одземање од страна на голема буква А, така што сите тоа го прави ни дава голем број во кој можеме да хаш нашите вредности излез. И тогаш ние ќе треба да врати хаш модул големина. Да биде многу, многу внимателно затоа што, теоретски, тука Вашиот hash вредност може да биде бесконечна. Тоа може само да одат на и на и на. Тоа може да биде некои навистина, навистина голема вредност, но бидејќи вашиот хаш табелата што сте создадени има само 26 индекси, вие сакате да бидете сигурни дека вашата modulusing така што ќе не run-- тоа е истиот нешто како вашиот queue-- така што не ви се избега на долниот дел од хаш функција. Сакате да ја заврши назад околу на ист начин во [Беззвучен] кога сте имале како многу, многу големи букви, ќе не сакате тоа да се само избега на крајот. Истото се тука, вие сакате да бидете сигурни дека тоа не избега на крај со групирање околу на врвот на табелата. Значи ова е само еден многу едноставна хеш функција. Сето она што го направив беше да го направи првиот писмото на она што нашите влезни беше и се претвори дека во индекс кој ние би можеле да се стави во нашите хаш табелата. Да, и така како што реков претходно, начинот на кој се справи со судири во нашата хаш маси се имаат, она што ние го нарекуваме, врзувањето. Значи, ако се обидете да внесете повеќе зборови што почнуваат со истото, ви се случува да имаат еден hash вредност. Авокадо и јаболко, ако сте се пушта и преку нашите хеш функција, се случува да ви даде истиот број, бројот на 0. Така и на начинот на кој ние се реши што е дека ние всушност вид на може да ги врска заедно преку поврзани листи. И така, во таа смисла, вие момци можат да се види каков вид за тоа како структурата на податоците кои ние сме поставување на претходно како суво грозје поврзани листа вид на може да дојде заедно во една. А потоа можете да се создаде досега поефикасно структури на податоци што може да се справи со поголеми количини на податоци, кои динамично менување на големината во зависност од вашите потреби. Секој јасно? Секој вид на јасни на она што се случува овде? Ако сакав да insert-- она ​​што е овошје, која започнува со, не знам, Б, освен Бери, банана. ПУБЛИКАТА: Blackberry. АНДИ Пенг: Blackberry, капина. Каде што го прави BlackBerry оди тука? Па, ние, всушност, не се подредени ова сеуште, но теоретски ако сакаме да ја имаат оваа по азбучен ред, каде што треба да се оди на BlackBerry? ПУБЛИКАТА: [Беззвучен] АНДИ Пенг: Точно, откако тука, нели? Но, бидејќи тоа е многу тешко да се reorder-- Претпоставувам дека тоа е до вас момци. Вие момци можат целосно спроведување на она што сакате. На поефикасен начин да се направи ова, можеби ќе биде да се најде решение за вашата врска листа во азбучен ред, и така, кога ќе завршиш вметнување на нештата, сакате да бидат сигурни да ги внесете во азбучен ред така што тогаш кога сте обидувајќи се да ги пребарувате, вие не мора да се напречни сè. Да знаат точно каде што е, и тоа е полесно. Но, ако сте вид на мора работите прошарани по случаен избор, ти си уште се случува да имаат за да ја преминат и онака. И така, ако сакав да се само BlackBerry внесете тука и јас сакав да го бара за тоа, знам, ох, капина мора да се почне со индексот на 1, па јас знаеме моментално Само за пребарување на 1. А потоа можам да вид на напречни поврзани листа се додека не се дојде до BlackBerry, и then-- је? ПУБЛИКАТА: Ако се обидуваш да се create-- Претпоставувам како ова е многу едноставен хаш функција. А ако се сака да се направи повеќе слоеви на кој, како, Добро, ние сакаме да се одвои во како и сите азбучен писма а потоа повторно да се како друг сет од азбучен писма во рамките на таа, ние се стави како хаш табела во табела хаш, или како функција во рамките на функција? Или е that-- АНДИ Пенг: Значи вашиот хаш function-- вашиот хаш табелата може да биде голем како што сакате тоа да. Па во таа смисла, јас мислев тоа е многу лесно, многу едноставно за мене да се заснова само вид на букви од првиот збор. И така, има само 26 опции. Може да се добие само 26 опции од 0-25, бидејќи тие само може да почне од А до Ш, но ако сакаа за да додадете, можеби, повеќе комплексност или побрзо време да се кандидира на вашиот хаш табелата, можете апсолутно може да направи сите видови на нештата. Можете да направите свој равенка која ги дава повеќе дистрибуција во вашата зборови, а потоа, кога барате, тоа се случува да биде побрзо. Тоа е целосно зависи од вас момци како сакате да го спроведат тоа. Сфатете го тоа како само кофи. Ако сакав да се имаат 26 кофи, јас ќе одам да одат во оние кофи. Но јас ќе одам да се има еден куп на работи во секоја канта, па ако сакате да го направи тоа побрзо и поефикасно, дозволете ми да имаат сто кофи. Но тогаш ќе мора да дознаам начин да одат, за да бидат во соодветна кофа тие треба да бидат во. Но, тогаш вие всушност кога сакате да се погледне во тоа кофа, тоа е многу побрзо, бидејќи има помалку работи во секоја канта. И така, да, тоа е, всушност, трик за вас момци во pset5 е дека ќе биде соочат со предизвикот да само да се создаде што и е најефикасен функција, можете да замислите да се биде можност да ги чувате и да се провери овие вредности. Целосно зависи од вас момци сепак сакате да го направи тоа, но тоа е навистина добра поента. Кој вид на логика сакаат да почнат да размислуваат за е, добро, зошто да не се направи повеќе кофи. И тогаш јас треба да го бара помалку работи, а потоа можеби и јас имаат различни хаш функција. Да, има многу начини да го направите ова pset, некои се побрзо од другите. Јас сум целосно случува само види како брзо беше најбрз вие момци ќе да биде во можност да ја добиете вашата функции за работа. Добро, добро за секого врзувањето и хаш маси? Тоа е всушност како еден многу едноставен концепт, ако мислите дека за тоа. Сето тоа е она што е одвојување вашите податоци се во кофи, сортирање нив, а потоа да бараат на наведува дека е поврзано со. Кул. Во ред, сега имаме еден поинаков вид на податочна структура што се вика едно дрво. Ајде да одиме на и да разговараат за се обидува кои се многу различни, но во истата категорија. Во суштина, сите дрво е наместо за организирање на податоците во линеарен начин дека хаш табелата ви does-- Знаете, тоа е се здобија со врвот и дното а потоа ќе каков линк исклучување на it-- на Дрвото има на врвот кој го нарекувате корен, и тогаш тоа има лисја сите околу неа. И така сите го имаме тука е само врвот јазол што укажува на други јазли, дека поени на повеќе јазли, и така натаму и така натаму. И па вие само треба разделување гранки. Тоа е само еден поинаков начин на организирање на податоци, и затоа што ние го нарекуваме дрво, вие момци just-- тоа е само моделирани надвор за да изгледа како дрво. Тоа е причината зошто ние го нарекуваме дрвја. Хаш табелата изгледа како маса. Дрвото само изгледа како дрво. Сето тоа е посебна начин на организирање на јазли во зависност од она што вашите потреби се. За да можете да имате root и тогаш мора лисја. Начинот на кој што можеме особено мислам за тоа е бинарно дрво, бинарно дрво е само посебен вид на дрво каде што секој јазол само точки да, на Макс, две други јазли. И така тука треба посебна симетрија во дрво што го прави полесно да се вид на изгледаат во она што го цени сте затоа што тогаш мора секогаш лево или десно. Таму никогаш не е како трет од лево лево или четврта по лева страна. Тоа е само да имате лево и десно и можете да пребарувате било кој од овие две. И така зошто е ова корисно? Начинот на кој ова е корисно е ако сте во потрага да пребарувате низ вредности, нели? Наместо спроведување бинарни Барај во Array грешка, ако си сакал да биде во можност да го вметнете јазли и да однесе јазли по волја и, исто така, зачувување на пребарувањето капацитетите на бинарни пребарување. Така на овој начин, ние сме вид на tricking-- сеќавам кога ние изјави поврзани листи не може бинарни пребарување? Ние сме вид на создавањето на податоци структура кои трикови кои во работа. И така, бидејќи поврзани листи се линеарни, тие само се поврзат еден по друг. Ние може да се вид на мора различен вид на совети кои укажуваат на различни јазли што може да ни помогне со пребарување. И така тука, ако сакав да имаат бинарни пребарување дрво, Знам дека моето средината ако 55. Јас сум само ќе се создаде дека како мојата средина, како root ми, а потоа јас ќе одам да имаат вредности spin off на тоа. Па еве, ако јас одам да се бараат вредноста на 66, јас може да почне на 55. Тоа е 66 поголем од 55? Да тоа е, па знам дека Мус пребарување В о десно покажувачот од ова дрво. Одам на 77. Добро, што е помалку од 66 или поголем од 77? Тоа е помалку од, па да знаете, ох, што треба да биде оставен јазол. И така тука ние сме вид на зачувување на сите од големите нешта за низи, толку како динамична промена на големината на предмети, да се биде можност да се вметне и да го избришете по волја, без да мора да се грижите за фиксна износот на просторот. Ние се уште ги зачува сите оние прекрасни нешта а во исто време да биде во можност да се зачува се најавите и да пребарувате времето на бинарни пребарување дека сме биле само претходно можност да се добие фраза. Кул податочна структура, вид на комплекс да се спроведе, на јазол. Како што можете да видите, сите тоа е на struct на јазолот е тоа што имаш лево и право покажувач. Тоа е се што и да е. Па наместо само има x или претходна. Имаш лево или десно, а потоа можете да вид ги поврзат заедно сепак така одберете. ОК, ние сме всушност ќе само да потрае неколку минути. Па ние ќе треба да се вратиш тука. Како што реков претходно, Јас вид на објаснето логиката зад тоа како ние ќе го бара преку ова. Ние ќе треба да се обиде pseudocoding ова за да се види ако може да се вид на примени Истата логика на бинарни пребарување во друг тип на податоци структура. Ако вие момци сакате да се земе како неколку минути за да се само се размислува за тоа. ВО РЕД. Добро, јас ќе одам да всушност, само да ви даде нема the--, ние ќе зборуваме за pseudocode прво. Сака ли некој така да им даде прободе во тоа што Првото нешто што сакате да направите кога сте почнуваат да го бара тоа? Ако ние сме во потрага по вредноста на 66, што е првото нешто што сакате да направите, ако ние сакаме да се бинарни пребарување ова дрво? ПУБЛИКАТА: Сакате да изгледа добро и се погледне лево и да видиме [Беззвучен] поголем број. АНДИ Пенг: Да, точно. Па ви се случува да се погледне во вашиот корен. Има многу начини на кои можете да се јавите тоа, вашиот надреден јазол луѓе велат. Ми се допаѓа да се каже, бидејќи коренот тоа е како коренот од дрвото. Ви се случува да се погледне Вашиот коренот јазол, а ти си ќе го видите е 66 поголеми или помала од 55. И, ако е поголема од, добро, тоа е поголема од, каде ќе сакате да се погледне? Каде сакаме да го бара сега, нели? Ние сакаме да ги пребарувате на десната половина од ова дрво. Па ние имаме, погодно, односно покажувач кој покажува на десно. И така, тогаш може да се постави нашата нова root за да биде 77. Ние само може да оди каде и покажувачот е да се покажува. Добро, О, еве ние сме почнуваат на 77, а ние може да се само рекурзивно да го направите ова повторно и повторно. На овој начин, можете вид за да имаат некоја функција. Имате начин на пребарување кои ви може само да се повторува одново и одново и одново, зависност од тоа каде сакате да се погледне додека не се дојде до крајот на вредноста кои сте во потрага по. Има смисла? Јас сум за да ви покажеме вистинските код, и тоа е многу код. Нема потреба да навивач надвор. Ќе зборуваме низ него. Всушност, не. Тоа беше само pseudocode. Добро, тоа беше само pseudocode, што е малку комплекс, но тоа е сосема во ред. Секој следниве заедно во оваа ситуација? Ако коренот е ништовен, враќање лажно, бидејќи тоа значи Вие дури и не мора ништо таму. Ако n е корен на вредноста, па ако тоа се случува да биде оној што го барате, тогаш ви се случува да се врати точно бидејќи знаете дека ја најдов. Но, ако вредноста е помала од корен на n, ти си ќе пребарување на левата дете или лево лист, што и да сакате да го наречеме. И ако вредноста е поголема од корен, ви се случува да се бара право дрво, тогаш едноставно се кандидира на функцијата преку пребарување повторно. И ако коренот е ништовен, дека тој значи дека сте достигнавме крајот? Тоа значи дека може да има повеќе повеќе листови за пребарување, тогаш знаете, ох, се Претпоставувам дека тоа не е тука бидејќи јас откако разгледав целата работа и тоа не е тука, тоа само може да не е тука. Дали тоа има смисла за секого? Па тоа е како бинарни пребарување зачувување можностите на поврзани листи. Кул, така и на вториот тип на податоците што структурата момци Може да се обидете спроведување на вашиот pset, вие само треба да се избере еден метод. Но можеби и алтернативна метода за хаш табелата е она што ние го нарекуваме Trie. Сето Trie е е специфични тип на дрво и има вредности кои одат на други вредности. Значи наместо бинарен дрво во смисла на тоа дека само една нешто што може да укаже на две, може да имаат едно нешто точка за многу, многу работи. Вие во суштина имаат низи во внатрешноста на кој ќе ги чувате покажувачи кои упатуваат на други низи. Па јазол на тоа како ние да дефинира Trie ако сакаме да се имаат Логичка, в збор, нели? Па јазолот е Булова како вистински или лажни, пред сè на чело на таа низа, е овој збор? Второ, сакате да имате покажувачи на она што остатокот од нив се. Малку комплексен, малку апстрактен, но Јас ќе се објасни она што сите средства. Па еве, на врвот, ако имаат низа веќе објави, еден јазол каде што треба Булова вредност се чуваат во пред кој ви кажува дали е ова некој збор? Зарем ова не е зборот? И тогаш го имате остатокот од вашата низа која всушност зачувува сите можности за тоа што би можело да биде. Така, на пример, како на врвот имаш првото нешто што се вели дека е точно или лажни, да или не, ова е еден збор. А потоа ќе мора од 0 до 26 од буквите што можете да ги чувате. Ако сакав да ги барате за лилјак, одам на врвот и јас со нетрпение за B. најдам Б во мојата низа, и така знам, во ред, Б е зборот? Б не е збор, па на тој начин Јас мора да продолжи со барањето. Одам од Б, и гледам на покажувач, кој укажува на Б и јас не гледам друга низа на информации, истата структура кои ги имале претходно. Here-- и ох, следниот писмо во [Беззвучен] е А. Значи ние се погледне во таа низа. Ние се најде на осмото вредност, а потоа ние со нетрпение да се види, ох, еј, е во тоа што еден збор, е Б-А зборот? Тоа не е збор. Ние мора да ги бараме. И така, тогаш ние со нетрпение да каде покажувачот на A поени, и тоа укажува на уште еден начин на која ние имаме повеќе вредност се чуваат. И на крајот, ние се дојде до B-А-Т, која е збор. И така следниот пат ќе се погледне, си оди да го имаат тоа проверка, да, оваа Булова функција е точно. И така во таа смисла ние сме вид да има едно дрво со низи. Па тогаш може да се вид на пребарување надолу. Наместо хаш функција и Доделување вредности од страна на поврзани листа, вие само може да се спроведе Trie која бара downwords. Навистина, навистина комплицирани работи. Не е лесно да се размислува за, бидејќи јас сум како плукање толку многу структури на податоци од во тебе, но не секој вид на се разбере како функционира логиката на ова? Добро, кул. Па B-A-T, а потоа ви се случува да се бара. Следниот пат кога ќе си оди за да ја видите, ох, еј, тоа е точно, така знам дека ова мора да биде еден збор. Истото за зоолошката градина. Значи, тука е нешто во моментов, ако се сакаше да пребарувате за зоолошката градина, во моментов, моментално не е зоолошката градина збор во нашето речникот бидејќи, како што вие момци можат да се види, прво место дека имаме Булова врати вистина е на крајот на зумирање. Имаме Z-О-О-М. И така тука, не, всушност, имаат зборот, зоолошката градина, во нашето речникот затоа оваа опција не е обележана. Така што компјутер не го прави тоа знам дека зоолошката градина е збор бидејќи начинот на кој ние сме тоа се чуваат, само зум тука всушност има Булова вредност и тоа е се покажа точно. Значи, ако сакаме да го вметнете збор, зоолошката градина, во нашето речникот, како ќе се оди за тоа го прават? Што треба да направите за да се осигураме дека нашите компјутер знае дека Z-О-О е збор а не на првиот збор е Z-О-О-М? ПУБЛИКАТА: [Беззвучен] АНДИ Пенг: Точно, ние сакате да бидете сигурни дека овој тука, дека Булова вредност е штиклирани дека тоа е вистина. Z-О-О, тогаш ние ќе треба да проверите, па ние точно знаеме, еј, зоолошка градина е еден збор. Одам да кажам компјутер дека тоа е збор, така дека кога проверките на компјутерот, таа знае дека е зоолошката градина збор. Затоа што се сеќавам на сите овие податоци структури, тоа е многу лесно за нас да се каже дека, ох, лилјак е збор. Зоолошката градина е еден збор. Зум е збор. Но, кога ќе го гради, компјутерот нема идеја. Па мора да го кажам токму во кој момент е овој збор? На која точка не е тоа збор? И во кој момент да направам треба да се бараат работи, и во кој момент ми е потребно да одите понатаму? Секој јасно на што? Кул. И така тогаш доаѓа проблемот за тоа како би ние одат за вметнување на нешто кои, всушност, не е таму? Па да речеме ние сакаме да го внесете зборот, бања, во нашата Trie. Како вие момци можат да се види како во моментов сите го имаме сега е Б-А-Т, и оваа нова структура на податоци имаше едно пивце дека укажа null бидејќи претпоставуваме дека, ох, нема зборови по Б-А-Т, Зошто се потребни за да се задржи имајќи работите после тоа Т. Но, проблемот се појавува ако го правиш сакаат да имаат еден збор што доаѓа по Т е. Ако имате бања, ти си ќе сакаат правото H. Така и на начинот на кој ние се случува да се направи, што е ние ќе треба да се создаде посебна јазол. Ние не сме партиционираш без оглед на износот на меморија за оваа нова низа, и ние ќе го преназначаване покажувачи. Ние ќе треба да му ја додели на Н, Прво на сите, ова нула, ние ќе треба да се ослободи од. Ние ќе треба да имаат надолу Н точка. Ако можеме да видиме еден Н, ние го сакаме да одат на друго место. Овде, ние тогаш може да се провери надвор да. Ако ние го погоди часа по Т, ох, тогаш знаеме дека ова е еден збор. Булова се случува да се врати вистина. Сите јасни за тоа како што се случи? ВО РЕД. Значи во суштина, сето овие структури на податоци дека ние сме поминале повеќе од денес, јас сум качил над нив, навистина, навистина брзо а не да се многу детали, и тоа е во ред. Откако ќе почнете да Месинг со него, ќе биде следење на каде сите покажувачи се, она што се случува во вашата структури на податоци, итн. Тие ќе бидат многу корисни, и тоа е на вас останува момци да целосно да дознаам како сакате да се имплементираат работите. И така pset4, на 5-- ох, тоа е во ред. Pset5 е грешките во правописот. Како што реков претходно, си оди за да се, еднаш повторно, да го симнете изворниот код од нас. Таму се случува да биде три главни работи што ќе бидат симнување. Ќе преземете речници, КЕРС, и текстови. Сите тие работи се се или речници на зборови дека ние сакаме да се провери или тест на информации дека ние сакаме да се проверка на правопис. И така на речници даваме ви се случува да ви даде вистински зборови кои сакаме да ги чувате на некој начин, на начин што е поефикасно од низа. А потоа и текстовите се ќе биде она што ние сме ќе побара од вас да ги запишува проверете да бидете сигурни сите зборови се вистински зборови. И така на три блока на програми кои ќе ви даде се нарекуваат dictionary.c, dictionary.h, и speller.c. И така сите dictionary.c не е она што ќе ви биде побарано да ги спроведе. Се вчитува зборови. Го пишува чекови нив, и тоа го прави сигурни дека сè е правилно вметната. diction.h е само библиотека датотека изјавува дека сите оние функции. И speller.c, ние се случува да ви даде. Вие не треба да се промени ништо од тоа. Сите speller.c не е се земе дека, товари него, ја проверува брзината на тоа, тестови за репер за како тоа, како брзо сте во можност да се прават работите. Тоа е правопис. Само да не се плеткаш со него, но го направи Дали сте сигурни дека се разбере она што таа го прави. Ние ги користиме на функција наречена getrusage дека тестови на перформансите на вашиот правопис Проверка на. Сите тоа го прави е во основа се тестира време на се што е во вашиот речник, така погрижете се да го разбереш. Бидете внимателни да не се плеткаш со него или друго работите нема да се води уредно. И најголемиот дел од овој предизвик е за вие момци навистина да ги менувате dictionary.c. Ние ќе треба да ви даде 140.000 зборови во речник. Ние ќе треба да ви даде текст датотека која има овие зборови, и ние сакаме да биде во можност да организира нив во хаш табелата или Trie бидејќи кога бараме од вас да ги запишува check-- замислите ако сте правопис проверка како Одисеја на Хомер. Тоа е како овој огромен, огромен тест. Замислете ако секој зборот кој сте имале да се погледне преку низа на 140.000 вредности. Кои би се засекогаш за вашата машина да се кандидира. Тоа е причината зошто ние сакаме да го организираме нашето податоци во поефикасно структури на податоци како што се маса хаш или Trie. А потоа вие момци можат вид од кога барате пристап работите полесно и побрзо. И така да се биде внимателен да го реши судири. Си оди за да се добие еден куп на зборовите кои почнуваат со А. Си оди за да се добие еден куп зборови кои почнуваат со Б. До вас момци како сакате да го реши тоа. Можеби има уште ефикасен хеш функција од само првата буква од нешто, и така што е на вас момци да се вид на правите што сакате. Можеби сакате да го додадете сите букви заедно. Можеби сакате да се направи чудни работи се допаѓа на сметка на бројот на букви, како и да е. До вас момци како што сакате да направите. Ако сакате да се направи хаш табелата, ако сакате да се обидете со Trie, целосно зависи од вас. Јас ќе ве предупреди пред време дека Trie е обично малку потешко само затоа што има многу повеќе совети како да ги пратите. Но целосно зависи од вас момци. Тоа е далеку поефикасно во повеќето случаи. Сакате навистина да се биде во можност да го задржи пратите на сите ваши покажувачи. Како да го прават истото дека правам овде. Кога ќе се обидуваш да го вметнете вредности во хаш табелата или избришете, бидете сигурни дека сте навистина следење од каде што се е поради тоа е навистина лесен за да сум обидувајќи се да го вметнете како зборот, Енди. Да речеме дека тоа е вистински збор, зборот, Енди, во огромна листа на А зборови. Ако јас само да се случи да преназначаване покажувач погрешно, Упс, таму оди на интегритет на остатокот на мојот поврзани листа. Сега единствен збор јас имаме е Енди, а сега сите на други зборови во речникот да се изгуби. И така ќе сакате да бидете сигурни дека ќе ги пратите на сите ваши совети или на друго место ќе ја добиеме огромни проблеми во вашиот код. Цртаат работи надвор внимателно чекор по чекор. Тоа го прави многу полесно да се замисли. И на крај, вие сакате да бидете во можност да ги тестираат вашите перформанси на вашата програма на големата табла. Ако вие момци се земе погледне во CS50 токму сега, имаме она што се вика на големата табла. Тоа е резултат на состојба од најбрзите проверка на правопис пати во сите на CS50 во моментов, мислам дека на врвот како 10 Времето Мислам дека осум од нив се вработени. Ние навистина сакаме вие ​​момци да ни го победи. Сите од нас се обидуваат да се спроведе најбрзо кодот што е можно. Ние сакаме вие ​​момци да се обиде да го оспори нас и да се спроведе побрз од сите нас може. Па така ова е навистина прв пат, дека ние сме ќе побара од вас момци да се направи pset дека навистина може да се направи во кој било метод ти сакаш. Јас секогаш се каже, ова е повеќе слично до решение вистинскиот живот, нели? Велам, еј, јас треба да го направите тоа. Изгради една програма која го прави ова за мене. Направете го тоа како сакате. Јас само знам дека сакам да пости. Тоа е предизвик вашите за оваа недела. Вие момци, ние ќе да ви даде задача. Ние ќе треба да ви даде предизвик. И тогаш тоа е до вас момци целосно само дознаам што е најбрзиот и повеќето ефикасен начин за спроведување на оваа. Да? ПУБЛИКАТА: Дали смееме да ако Резултатите од ова истражување побрзо начини хаш маси да се направи на интернет, можеме да направиме дека и цитираат код на некој друг? АНДИ Пенг: Да, сосема во ред. Значи, ако вие момци го прочитате спецификации, има линија во спецификации кој се вели дека момците се целосно слободни да истражуваат хаш функции на она што се некои побрзото хаш функции да се кандидира работи преку како колку што ќе се цитираат овој код. Па некои луѓе веќе имаат сфатиле брзи начини на водење проверувачи за правопис, на брза начини на складирање на информации. Целосно зависи од вас момци ако сакам само да се земе тоа, нели? Бидете сигурни дека сте повикувајќи. Предизвикот тука навистина дека ние се обидуваме да се тестира е да се осигура дека знаете снајдете покажувачи. Колку што спроведување вистинските хеш функција и доаѓа со се допаѓа математика се прави тоа, вие момци може да истражување било методи онлајн вие момци сакате. Да? ПУБЛИКАТА: Можеме ли да се цитираат само со користење на [Беззвучен]? АНДИ Пенг: Да. Може да се само, со твојот коментар, можете да се цитираат како, о, земени од ала, ала, ала, хеш функција. Секој имате било какви прашања? Ние всушност breezed преку делот денес. Јас ќе бидам тука за да се одговори на прашањата, како и. Исто така, како што реков, канцеларија часа вечерва и утре. Спец оваа недела е, всушност, супер лесен и супер краток за да ја прочитате. Јас би навестиле преземање на ум, само Прошетајте низ целината на него. И Zamyla всушност ќе шета преку секоја од функциите што треба да се спроведе, и така тоа е многу, многу јасно како да се направи сè. Само за да бидете сигурни дека сте следење на покажувачи. Ова е многу предизвикувачки pset. Тоа не е предизвик, бидејќи како и, ох, концептите се толку многу повеќе тешко, па ќе мора да научат толку многу нови синтаксата на патот што сте направиле за последните pset. Pset ова е тешко, бидејќи има толку многу покажувачи, и тогаш тоа е многу, многу лесно да се еднаш имаш грешка во кодот не можат да се најде каде што вирусот е. И така комплетна и крајна вера во тебе момци да бидат во можност да се победи на нашите [Беззвучен] правопис. Јас всушност немаат никаква писмена рудник уште, но јас сум за да се напише рудникот. Па така додека сте пишување твое, јас ќе напишам мој. Одам да се обидат да се направи рудникот побрзо од твое. Ќе видиме кој има најбрзо еден. И да, јас ќе ги видиш сите од вие момци тука во вторникот. Јас ќе се кандидира еден вид како pset работилница. Сите делови на оваа недела се pset работилници, па вие момци имаат многу можности за помош, на работното време, како и секогаш, и јас навистина со нетрпение очекуваме да читањето на сите на вашиот код, момци '. Имам квизови се тука ако момци сакаат да дојдат да се оние. Тоа е се.