[За възпроизвеждане на музика] 

АНДИ Пенг: Добре дошли в 6-та седмица на раздел. Ние се отклонява от нашия стандарт време участък от вторник следобед на тази прекрасна неделя сутринта. Благодаря ви за всички, че се присъедини към мен днес, но сериозно, аплодисменти. 

Това е доста голямо усилие. Аз почти дори не го направи с течение на времето, но беше ОК. Така че аз знам, че всички от вас, Току-що го е направил, за да викторината. Първо, добре дошли в обратната страна на това. 

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

Така бързо, преди да започнем, на дневен ред за днес е, както следва. Както можете да видите, че сме основно бърза стрелба през цял куп структури от данни наистина, наистина, наистина бързо. Така че като такава, тя няма да бъде супер интерактивна днес. Тя просто ще бъде ми вид крещи неща, които вие, и ако ви обърка, ако аз отивам твърде бързо, да ме уведомите. Те просто са различни данни структури, и като част на вашия pset за това предстоящата седмица, ще бъдете помолени да приложи една от тях, може би две от them-- две от тях във вашата pset. ОК, така че аз съм просто ще започнем с някои съобщения. Ние ще отидем стекове и опашки още в дълбочина, отколкото това, което направихме преди теста. Ние ще отидем свързана изброят отново, за пореден път, по-задълбочено, отколкото това, което имахме преди теста. И тогава ние ще говорим за хеш маси, дървета и опит, които всички са доста необходимо за вашата pset. И тогава ние ще отидем по някои полезни съвети за pset5. 

ОК, така викторина 0. Средната стойност е 58%. Това беше много ниска, и така вие всички Направих много, много добре в съответствие с това. 

Доста, правило е, ако сте в стандартно отклонение от средната стойност особено след като ние сме в по-малко удобна точка, вие сте напълно добре. Вие сте на път. Животът е добър. 

Знам, че е страшно да се мисли, че Имам като 40% от този тест. Отивам да се провали този клас. Обещавам ви, че не сте Ще успеят класа. Вие сте напълно добре. 

За тези от вас, които имам над средната стойност, впечатляваща, впечатляваща, като, сериозно направено както трябва. Аз ги нося със себе си. Чувствайте се свободни да дойдат да ги получите в края на раздел. Нека да знаят, ако имате някакво въпроси, въпроси с тях. Ако съберем резултата си погрешно, да ни уведомите. 

ОК, така pset5, това е наистина странно седмица за Йейл, в смисъл, че нашата pset се дължи Сряда по обяд включително покойния ден, така че това е всъщност теоретично поради вторник по обяд. Вероятно никой не завърши най вторник по обяд. Това е напълно наред. Отиваме да имат работно време тази вечер, както и в понеделник вечерта. И всички секции тази седмица ще действително да се превърне в работилници, да се чувстват свободни да поп в всеки раздел, което искате, и те ще бъдат нещо като мини-pset работилници за помощ за това. Така като такива, това е само частта накъде сме се преподава материал. Всички други секции ще бъдат фокусирани изключително на помощ за pset. Да? 

АУДИТОРИЯ: Къде са работно време? 

АНДИ Пенг: Работно време tonight-- о, добър въпрос. Мисля, че работното време тази вечер са в Teal или най Commons. Ако проверите онлайн CS50 и отидете на работното време, трябва да има график, вие, където всички от тях са казва. 

Знам, че нито тази вечер или утре е Тийл, и мисля, че може да има Комънс за онази вечер. Не съм сигурен. Добър въпрос. Проверка на CS50. 

Cool, всички въпроси по отношение на график за следващия като три дни? Обещавам ви, хора като Дейвид каза, че това е на върха на хълма. Вие, момчета, сте почти там. Само още три дни. Стигнете, а след това всички ние ще се понижат. Ще имаме хубав CS без прекъсване. Добре дошъл обратно. Ще се потопите в уеб програмиране и развитие, неща, които са много забавно сравнение до някои от другите psets. И това ще бъде чил и ще имаме много забавно. Ние ще имаме повече бонбони. Съжалявам за бонбони. Забравих бонбони. Това беше груб сутрин. Така че, момчета са почти там, и аз съм много горд с вас, момчета. 

ОК, така че купища. Кой обичан въпроса за Джак а облеклото му на теста? Никой? OK, това е добре. 

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

По същество, мисля, че на стека, както всеки комин на обекти където можете да постави нещата на върха, и След това можете да ги извадите от върха. Така LIFO е съкращение ни харесва да use-- Last In, First Out. И така продължи в в началото на стак е първата, която излиза. И така двата термина сме искали да се сдружават с които се наричат ​​тласък и поп. Когато натиснете върху нещо стека, и ти го поп обратно нагоре. 

И така, аз предполагам, че това е нещо като абстрактно понятие за тези от вас, които искат да видят като реалното изпълнение на този в реалния свят. Колко от вас са писали есе може би като един час преди това се дължеше, и случайно сте изтрили огромен парче от него, като случайно? И тогава какво правим контрол ние използваме, за да го пуснат обратно? Control-Z, така ли? Контрол, Z, така че количеството на пъти че Control-Z е спасил живота ми, е спасил задника ми, всеки път, която е осъществявана чрез комин. 

По същество цялата информация която е на вашия документ Word, той получава избута и изскочил на воля. И така, по същество, когато изтриете нещо, можете да го поп обратно нагоре. И тогава, ако имате нужда от него отново, вие го натиснете, което е това, което Control-C прави. И световната функция толкова реално на колко проста структура на данните може да помогне с вашето ежедневие. 

Така Struct е начинът, ние всъщност създаде стак. Ние написали определи структура на, и след това ние наричаме това поставете на дъното. И в рамките на пакета, имаме два параметъра че по същество ние можем да манипулираме, Така че ние имаме Чар капацитет звездни струни. 

Всичко, което го прави е създаване на масив че ние може да съхранява всичко, което искате което може да се определи капацитета си. Капацитетът е само на макс размер на елементи можем да пускат в този масив. Размер на инт е на тезгяха, която поддържа следите колко елемента са в момента в стека. Така че тогава ще можем да следим, A, както колко голям действителната стека е, и, В, колко от тази купчина напълнихме, защото ние не искаме да прелее над това, което е нашата способност. 

Така например, това прекрасно въпрос беше на вашия тест. По същество как ще бутнете върху купчината. Доста проста. Ако се вгледате в него, ние ще ходим през това. Ако [недоловим] size-- не забравяйте, когато искате да влезете параметър в рамките на една структура на, правиш името на struct.parameter. 

В този случай, а е Името на нашия стак. Искаме да получите достъп до размера от него, така че ние правим s.size. Така че, докато размерът не е равно на капацитета или толкова дълго, тъй като това е по-малко от капацитета, или ще работи тук. 

Вие искате да получите достъп до вътрешността на вашия стак, така s.strings, и ти започваш да се сложи това нов номер който искате да вмъкнете в там. Нека просто кажем, че ще искате да вмъкнете инт п върху купчината, бихме могли да направим s.strings, скоби, s.size равнява п. Тъй като размерът му е къде сме В момента са в стека ако ще да прокара това, ние просто достъп където размерът е, на текущата пълнота от стека, и ние натиснете инт п върху нея. И тогава ние искате да се уверите, че ние сме също така увеличаване размера на п, за да можем да следим ние сме добавя допълнително нещо, за да стека. Сега имаме по-голям размер. Означава ли това тук да има смисъл да всички, колко логично тя работи? Това е вид на бърз. АУДИТОРИЯ: Можете ли да разясни на s.stringss.strings [s.size] отново? АНДИ Пенг: Разбира се, така че какво прави s.size момента ни даде? АУДИТОРИЯ: Това е текущия размер. АНДИ Пенг: Точно така, така че текущия индекс, че нашата размер е най-, и така искаме да се сложи новото число че искаме да вмъкнете в s.size. Това прави ли смисъл? Защото s.strings, всичко, което е е името на масива. Всичко това е с достъп на масив в рамките на нашата структура на, и така, ако искаме да поставите п в този индекс, ние просто да го отворите използвайки скоби s.size. Готино. 

Добре, поп, аз го Псевдокод навън за вас, момчета, но подобна концепция. Това прави ли смисъл? Ако размерът е по-голяма от нула, а след това знаете, че искате да вземете нещо , защото ако размерът не е по-голяма от нула, а след това нямам нищо в стека. 

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

АУДИТОРИЯ: Ще тези слайдове и цялото това нещо се появи днес-Иш? АНДИ Пенг: Винаги, Аха. Отивам да се опита да сложи това нагоре като един час след това. Ще приятел Дейвид, Дейвид ще се опита да го направи като един час след това. 

ОК, така че след това се премести в тази друга прекрасна структура от данни, наречена опашка. Както вие може да видите тук, а опашка, за британците сред нас, всичко това е е една линия. Така че противно на това, смятате комин е, опашката е точно това, Логично ли, че е. Тя е проведена по правилата на FIFO, което е, пръв Out. Ако сте от първите, една в линията, вие сте първият, който излиза от линията. 

Така че това, което сме искали да наречем това е dequeueing и enqueueing. Ако искаме да добавите нещо в нашия опашка, ние Enqueue. Ако искаме да dequeue, или да вземат нещо далеч, ние dequeue. 

Така че същото усещане, че ние сме вид създаване на елементи с фиксиран размер, че ние може да съхранява определен неща, но ние можем също променя, когато ние сме пускането параметри в тях въз основа на какъв тип функционалност, което искаме. Така стекове, искахме последният един, N да бъде първата една навън. Queue е искаме първото нещо, за да бъде първото нещо навън. 

Така структура на типа определят, както можете да видите, това е малко по-различно от това, което беше стека защото не само, че трябва да се запази следите къде размера момента е, ние също искаме да следите на главата както и къде сме в момента са. Така че аз мисля, че е по-лесно ако се направи всичко. Така че нека да си представим, че имаме опашка, така че нека да кажем, главата е точно тук. Ръководителят на линията, нека само да кажа, че е там в момента, и ние искаме да вмъкнете нещо в опашката. Отивам да се обадя размер същество е същото нещо като опашка, В края на където и да си опашка е. Нека просто кажем размер е точно тук. 

И така, как един реално въведете нещо в режим на изчакване? Какво форум искаме да поставите където искате да вмъкнете в. Ако това е началото на вашето опашка и това е краят на това или размера на това, когато правим искате да добавите следващия обект? 

АУДИТОРИЯ: [недоловим] АНДИ Пенг: Точно така, искате да добавите то в зависимост от сте го написали. Или това е празно или че е празно. Значи вие искате да я добавите вероятно тук, защото, ако размерът is-- ако всички те са пълни, което искате да го добавите точно тук, нали? 

И така, това е, а много, много проста, не е съвсем правилно винаги тъй като основната разлика между опашка и стек е, че опашката да действително да бъде манипулиран така че промените в главата в зависимост от мястото, където искате началото на вашата реплика, за да започнете. И като резултат, опашката си също ще се промени. И така, да погледнем този код в момента. Както вие, момчета, също бяха помолени да напиша на теста, Enqueue. Може би ние ще говорим чрез защо отговорът е това, което беше. 

Не можех да отговарят съвсем точно тази линия на един, но по същество това парче код трябва да бъде на една линия. Прекарайте като 30 секунди. Обърнете внимание, и да видим защо това е начинът, по който тя е. 

Много, много подобна структура на много много подобна структура като предишния стека с изключение може би един ред код. И че един ред код определя функционалност. И той наистина отличава опашка от комин. 

Всеки, който иска да вземе хладно оръжие в която обяснява защо сте имам това сложно нещо тук? Ние виждаме завръщането на нашия прекрасен модул приятел. Както вие, момчета, скоро ще дойдат да признае на програмиране, почти по всяко време имате нужда от нещо да обгърне всичко, модул ще е начинът да го направя. Така че, знаейки, че, няма кой искате да се опита да обяснява, че ред код? Да, всички отговори са приети и добре дошли. АУДИТОРИЯ: Възможно ли е да ми говори? АНДИ Пенг: Да. АУДИТОРИЯ: О, не съжалявам. АНДИ Пенг: OK, така че нека преведе през този код. Така че, когато се опитвате да добави нещо към опашката, в чудесния случай, че главата се случва да бъде точно тук, това е много лесно за нас просто да отида до края вмъкнете нещо, нали? Но целият смисъл на опашка е че главата може действително динамично се променя в зависимост от това къде сме Искам началото на нашия р да бъде, и като такива, опашката също ще се промени. 

И така, представете си, че това не е на опашка, а по-скоро това е опашката. Да кажем, че главата е точно тук. Да кажем, че нашата опашка изглеждаше така. Ако искахме да се смени, когато началото на линията е, нека да кажем, че сме се размърда главата по този начин и размери тук. 

Сега искаме да добавите нещо към тази опашка, но тъй като вие може да видите, това не е толкова просто, колкото просто да добавете каквото е след размера защото тогава се изчерпи границите на реалното ни масив. Когато искаме наистина да добавите е тук. Това е красотата на опашка е, че за нас, то визуално Прилича на линия върви по този начин, но когато се съхранява в структура от данни, те го даде като като цикъл. Той вид увива към предната същия начин че една линия също може да увийте около зависимост от където и да сте Искам в началото на линията да бъде. И така, ако вземем една погледнете надолу тук, нека кажем ние искахме да се създаде функция, наречена Enqueue. Искахме да добавите инт п в която р. Ако q.size q-- ние ще се обадя, че нашите данни structure-- ако нашата queue.size не равно на капацитет, или ако това е по-малко от капацитета, q.strings е масива в рамките на нашата р. Отиваме да зададете че равен на q.heads, което е точно тук, плюс q.size модул с капацитет, който увийте ни върна тук. 

Така че в този пример, индекс на главата е едно, нали? Индексът на размер е 0, 1, 2, 3, 4. Така че ние можем да направим 1 плюс 4 модула от нашия капацитет, който е 5. Какво ни дава това? Какво е индексът, който излиза от това? 

АУДИТОРИЯ: 0. 

АНДИ Пенг: 0, което се случва да бъде точно тук, и така искаме да бъде в състояние да вмъкнете в точно тук. И така, това уравнение тук натура от просто работи с всякакви номера в зависимост от мястото си главата и вашия размер са. Ако знаете какво тези, нещата са, нали знаеш точно там, където искате да вмъкнете каквото и да е, след като си опашка. Това прави ли смисъл на всички? 

Знам вид мозъчен закачка особено след като тази дойде в резултат на вашия тест. Но се надяваме, че всеки, Сега можем да разберем защо това решение или това функция е начинът, по който тя е. Всеки, който е малко неясно за това? ДОБРЕ. 

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

И така, когато dequeue, Аз също го Псевдокод навън. Чувствайте се свободни да, ако искате да се направи опит за кодиране това. Искаш ли да се движи главата, нали? Ако исках да dequeue, I ще се движат главата над. Това би било в главата. 

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

ОК, така че ние ще поговорим малко по-задълбочено за свързани списъци защото те ще бъдат много, много ценно за вас в хода на тази седмица psets. Свързани списъци, като вас, момчета мога да си спомня, всички те са са възли, които са възли на определен стойности на двете стойност и указател които са свързани заедно от тези насоки. И така, за това как Struct ние създаваме една възлова точка тук е, че ние имат инт п, което е независимо от стойността в магазин или низ п или каквото и да искате да го наричат, Чар звезда п на. Struct възел звезда, която е на показалеца че искате да имате във всеки възел, започваш да има, че показалка точка към следващата. Ще имате на главата на свързан списък, който е Ще посоча с останалата част от стойностите така нататък и така нататък докато в крайна сметка да стигнат до края. И това е само последният възел Ще е нужно указател. Това ще посочим нищожна, и това е, когато знаеш, че си удари край на вашия свързан списък е, когато миналата показалеца не сочи към нищо. 

Така че ние ще отидем малко по-в дълбочина по отношение на това как всеки би евентуално търси свързан списък. Спомни си какво са някои от недостатъци на свързани списъци стихове масив отношение търсения. Масивът можете двоично търсене, но защо да не може да се направи, че в свързан списък? 

АУДИТОРИЯ: Защото всички те са свързани, но не съвсем знам къде [Недоловим]. 

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

И така, в резултат, единственият начин да се търси чрез свързан списък е линейно търсене. Защото аз не знам къде точно 12 стойност на свързания списък е, Аз трябва да премине през цялата от които свързан списък една от един от главата към първия възел, на втория възел, на третия възел, по целия път надолу, докато най-накрая да получите до мястото, където този възел Търся е. И така, в този смисъл, търсене на свързан списък винаги е п. Той винаги е п. Той винаги е в линейното време. 

И така кода, в която ние прилагаме това, и това е малко ново за вас, момчета, тъй като вие момчета наистина не са говорили за или някога видян указатели в това как да се търси чрез указатели, така че ние ще преминете през това много, много бавно. Така че търсенето булев, надясно, нека си представим, ние искаме да се създаде функция, наречена търсене, което се връща истина ако сте намерили стойност в рамките на свързано изброят, и го връща фалшиви друго. Списък звезда Node е В момента само на показалеца първа точка във вашия свързан списък. инт п е стойността, която сте търсите в този списък. 

Така възел звезда показалеца равнява списък. Това означава, че ние сме за създаване и създаване на показалец на първата възлова точка вътре в списъка. Всеки с мен? Така че, ако бяхме да отидете отново тук, щях да имам инициализира указател, който сочи към ръководителят на каквото и да е в списъка. 

И тогава, след като получите тук, докато курсорът не се равнява нищожна, така че е на линия, в която са ще бъде в последствие преминаващи останалата част от нашия списък, защото това, което се случва, когато показалеца равнява нула? Ние знаем, че сме have-- 

АУДИТОРИЯ: [недоловим] 

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

Така, че е на линия, в която сме Ще трябва реалното търсене. И ако pointer-- виждаш този вид на стрелка функция там? Така че, ако показалецът пункта до п, ако показалеца на п равнява равнява п, така че означава, че ако показалеца, че сте търсите в края на всеки възел всъщност е равна на стойността което търсите, а след това искате да се върнете вярно. Така че основно, ако сте в една възлова точка, която има стойност, която, което търсите, знаете ли, че сте били в състояние успешно да търсите. 

В противен случай, искате да зададете показалеца си към следващия възел. Това е, което тази линия тук се прави. Pointer равнява показалеца следващата. Всеки, който види как работи? 

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

Нека, който се накисва в за малко. Това ще бъде доста важно за вашия pset. Логиката на това е много проста, може би синтактично просто го изпълняват. Вие, момчета, искате да направите уверите, че сте разбрали. Готино. 

ОК, така че как ще бъде вмъкване възли, надясно, в списъка, защото не забравяйте, какви са това, което на обезщетенията на наличието на свързан списък сравнение масив от гледна точка на съхранение? 

АУДИТОРИЯ: Това е динамичен, така че е по-лесно to-- 

АНДИ Пенг: Точно така, така че е динамична, които означава, че той може да се разширява и свива в зависимост от нуждите на потребителя. И така, в този смисъл, ние не се нуждаят от да губите излишно памет, защото аз ако аз не знам колко стойности искам до магазина, то няма смисъл за мен да се създаде масив, защото ако искам да се съхранява 10 стойности и аз се създаде масив от 1000, това е много губи паметта, разпределени. Ето защо искаме да използваме свързан списък, за да бъде в състояние да динамично промяна или свие нашия размер. 

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

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

Така че това важи за навсякъде, където която се опитвате да вмъкнете в. Ако искате да се вмъкнете в главата, ако искате да отговорите тук, ако искате да се вмъкнете в края, добре, крайният I Предполагам, че просто ще нямам показалка, но вие искате да се уверите, че не правим губят останалата част от вашия списък. Вие винаги искате да се уверите Вашата нова възел сочи към каквото и да искате да вмъкнете в, и след това можете да добавите верижното нататък. Всеки ясно? 

Това ще бъде един от истинските проблеми. Един от най-важните въпроси започваш да има на вашия pset е, че ти започваш да се опитаме да създадем свързан списък и го поставете неща но след това просто се изплъзне от почивка на вашия свързан списък. И ти започваш да бъде като, I Не знам защо това се случва? И това е болка да премине през и търсене на всички ваши указатели. 

И аз ви гарантирам, по този pset, писане и рисуване тези възли от ще бъде много, много полезен. Така че можете да напълно да следите на мястото, където всички ваши указатели са, какво се случва погрешно, където всички ваши възли са, това, което трябва да направите, за да получите достъп или вмъкнете или изтриете или към някоя от тях. Всеки добър с това? Готино. 

Така че, ако искаме да разгледаме кода? О, аз не знам дали ние да разгледате the-- ОК, така че в горната всичко е е функция име посочете къде искаме да вмъкнете инт п в свързан списък. Отиваме да минеш през това. Това е много код, много нови синтаксис. Ще се оправи. 

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

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

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

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

Всичко, което правим, е създаването на нова възел, създаване на курсора нула, и след това пренасочване го в главата, ако ние знаят, че ние искаме да го вмъкнете в главата. И тогава в главата ще се сочи към този нов възел. Всеки OK с това? 

Така че това е процес на два етапа. Трябва да присвоите първа каквото и да създавате. Определете че указател към справки, а след това ви може вид сочен първата показалеца и го насочва към новия възел. Където и да искате да го поставите, тази логика няма да важи. 

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

ОК, така код ще бъде тук. Вие, момчета, да разгледаме след точка. Тя ще има. 

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

АУДИТОРИЯ: Би още е подобен процес на подобно възлагане на показалеца и След възлагане че показалеца, но ние ще трябва да се намери там. 

АНДИ Пенг: Точно така, точно така, същия процес с изключение на вас Трябва да се намери къде точно сте Искам тази нова показалка, за да отидат в, така че, ако искате да вмъкнете в средата на свързани list-- OK, нека да кажем, че това е нашата свързан списък. Ако искаме да го поставите точно тук, отиваме да създадете нов възел. Отиваме да изчистване. Отиваме да създадете нов възел. Отиваме да възложи показалеца на този възел тук. 

Но проблемът, който се различава от мястото, където главата е е, че ние знаехме точно когато главата е. Той е бил прав в началото, нали? Но тук ние трябва да следим на мястото, където ние сме го поставите в. Ако поставяте ни възел тук, ние имаме да се уверите, че една предишна към този възел е този, който преназначава на показалеца. Така че тогава ще трябва да вид следите на две неща. Ако следите, когато това възел в момента е в вкарате в. Вие също трябва да следите къде предишния възела, който вие търсите в също беше там. Всеки добър с това? ДОБРЕ. 

Какво ще кажете за вмъкване в края на краищата? Ако исках да го добавите here-- ако исках за добавяне на нов възел към края на списъка, как бих могъл да го направим това? АУДИТОРИЯ: Така че в момента, в Последният нечии посочи нищожна. АНДИ Пенг: Да. Точно така, така че това един В момента се посочи да се знае, и така че предполагам, в този смисъл, това е много лесно да добавите към края на списъка. Всичко, което трябва да направите е да го настроите равна на нула и след това бум. Точно там, много лесно. Много просто. 

Много подобен на глава, но логично искате да се уверите, че стъпките, ви отведе към правене на нищо от това, което след време. Това е много лесно да, в средата на кода си, хванат по, О, аз имам толкова много указатели. Аз не знам къде всичко сочи към. Аз дори не знам кой възел съм на. Какво става? 

Отпуснете се, успокой се, поемете дълбоко дъх. Налейте си свързан списък. Ако кажа, че знам къде точно Аз трябва да поставите този в и знам точно как да превъзложите ми указатели, много, много по-лесно да се картина out-- много, много по-лесно да не се губят в бъговете на кода си. Всеки OK с това? ДОБРЕ. 

Така че предполагам, концепция, която ние не сме Наистина говорихме досега, и аз предполагам, че вероятно няма да срещнете много yet-- това е вид напреднал concept-- е, че ние всъщност имаме данни структура, наречена двойно свързан списък. Така че, както вие може да видите, всичко, което правим, е създаването на действителна стойност, допълнително показалеца на всеки един от нашите възли че също така посочва предишния възел. Така че не само ние имаме възли сочат към следващата. Те посочват също с предишния. Отивам да се игнорират тези два момента. 

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

Но като такива, имат двойно вас сумата от указатели, това е в двоен размер на паметта. Това е много насоки, за да следите. Това е малко по-сложен, но това е малко по-удобни за ползване в зависимост от това, което се опитвате да постигнете. 

Така че този тип данни структура напълно съществува, и структурата е много, много проста, освен всичко, което има, е, вместо само указател към следващия, вие също трябва указател към предишния. Това е всичко, разликата е била. Всеки добър с това? Готино. 

Добре, така че сега аз съм наистина да прекарат вероятно като 15 до 20 минути или по-голямата част на останалата част от времето в раздел Говорим за хеш таблици. Колко от вас, момчета Прочетох pset5 спец? Добре, добре. Това е по-висока от 50% от обикновено. ОК е. 

Така че, както вие ще видите, ти си предизвикателство в pset5 ще бъде изпълнението на речника когато зареждате над 140,000 думи че ние ви даваме и правописа проверка то срещу целия текст. Ние ще ви дадем случайна литературни произведения. Ние ще ви дадем Одисеята. Ние ще ви дадем Илиада. Ние ще ви дадем Остин Пауърс. 

И си предизвикателство ще бъде да се проверка на правописа всяка дума във всички от тези речници същество с нашата проверка на правописа. И така, има няколко части на създаването на този pset, Първият искате да бъдете в състояние реално да се зареди всички думи във вашия речника, а след това ви Искам да бъда в състояние да проверка на правописа всички от тях. И така, като такива, ти започваш да се изисква структура на данните, които могат да направят това бързо и ефективно и динамично. 

Така че предполагам, че най-лесният начин да направите това, вие вероятно ще се създаде масив, нали? Най-лесният начин за съхранение ви е може да се създаде масив от 140,000 думи и просто да ги поставите там и след това да ги прекосяват от двоично търсене или чрез селекции или not-- Съжалявам, че е за сортиране. Можете да ги сортирате и след това да ги прекосяват от двоично търсене или просто линейно търсене и само крайните думите, но това отнема огромно количество памет, и това не е много ефективен. 

И така, ние ще започнем говорим за начини за печелене нашето време работи по-ефективно. А нашата цел е да се получи константно време, когато това е почти като масиви, където имате мигновен достъп. Ако исках да търсите за нищо, Искам да бъда в състояние само, бум, тя намери точно, и да го извадя. И така структура, в която ние ще се превръща в непосредствена близост да бъде в състояние да получите достъп до постоянно времето, това Свещения Граал в програмирането на постоянна време се нарича хеш таблица. И така, Давид вече бе споменато в [Недоловим] малко в лекция, но ние ще се вижда гмуркане в дълбока тази седмица на парче, което е във връзка с как хеш таблица работи. 

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

И така тук, ако искахме за съхранение на английски думи, бихме могли потенциално просто, аз не правя знам, включете всички първите букви в някаква редица. И така, например, ако исках А за да бъде синоним на apple-- или с индекса 0, и B да бъде синоним с 1, ние можем да имаме 26 вписвания че може просто да съхранявате всички от буквите на азбука, че ние ще започнем с. И тогава можем да имаме ябълка на индекса 0. Ние можем да имаме банани в индекса на 1, пъпеш в индекса на 2, и така нататък и така нататък. И по този начин, ако исках да търсите ми хеш маса и достъп ябълка, Знам ябълка започва с А, и аз знам точно че тя трябва да бъде и хашиш трапеза при индекс 0, защото на функцията предварително определен. 

Така че аз не знам, ние сме програма за употреба, където ще бъдете таксувани с Не arbitrarily-- произволно, с опита си да замислено мисля, че на добри уравнения за да може да се разпространи всички от вашите ценности по начин, те могат лесно достъп тя по-късно с подобно уравнение Ти ли си, себе си, знам. Така че, в смисъл, ако исках да отида, за да манго, знам, о, тя започва с m. Тя трябва да бъде в индекса от 12. Не е нужно да се търси чрез нищо. Знам exactly-- можех просто отидете на индексът на 12 и дръпнете, че навън. 

Всеки ясно как един хеш функция маса на работи? Това е вид на току-що по-сложен масив. Това е всичко, това е. ДОБРЕ. 

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

Така че, ако се опитам да вмъкнете погребат в хеш таблица, която вече има банан върху него, какво ще се случи, когато опитате да вмъкнете това? Лоши неща, защото бананите вече съществува в рамките на индекса че искате да го съхранявате инча Berry вид е като, ах, какво да правя? Аз не знам къде да отида. Как да разрешите този? 

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

И така тук, ако аз Исках да вмъкнете Бери, Знам, OK, аз отивам да вход то чрез моя хеш функция. Отивам да се окажете с индекса на 1, а след това аз ще бъда в състояние да имат само малка подгрупа от тази гигант 140000 дума речника. И тогава аз може просто да погледнете чрез 1/26 от това. 

И така, тогава аз може просто да вмъкнете Бери преди или след банан в такъв случай? След, нали? И така, вие ще искате да поставете този възел след банан, и така започваш да вмъкнете При опашката на тази свързан списък. Отивам да се върна към настоящия предишния слайд, така вие може да видите как хеш функция работи. 

Така че хеш функция е това уравнение че сте стартирали вид вашия вход чрез да получите каквото индекс Искате ли да го зададете към. И така, в този пример, всички искахме да направя, беше да вземе първата буква, превърнали това в един форум, тогава ние може да се съхранява, че в нашата хеш функция. Всичко, което правим тук, е, че сме превръщане на първата буква. Така keykey [0] е само първата буква на каквото и низ водим, ние сме минаваща инча Ние сме конвертиране, че до края на гимназиалната, и ние сме се извади от главни букви A, така че всичко това се прави ни дава редица по които можем да хеш нашите ценности върху. 

И тогава ние ще върнете хеш модул SIZE. Бъдете много, много внимателни защото теоретично тук Вашата хеш стойност може да бъде безкраен. Той може просто да отида и още и още. Тя може да бъде някои наистина, Наистина голяма стойност, а защото си хеш таблица, която сте създали има само 26-индекси, искате да се уверете, че modulusing, така че да не run-- това е същото нещо като вашата queue-- така че да не се налага да изключите дъното на вашия хеш функция. 

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

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

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

Ако исках да insert-- какво е плод, който започва с, аз не знам, Б, различни от зърна, банан. 

АУДИТОРИЯ: Blackberry. 

АНДИ Пенг: Blackberry, къпина. Къде къпина отидете тук? Е, ние всъщност не са сортирани това все още, но теоретично ако искаме да имаме тази по азбучен ред, където трябва BlackBerry отидете? 

АУДИТОРИЯ: [недоловим] 

АНДИ Пенг: Точно така, след като тук, нали? Но тъй като това е много трудно да се reorder-- Предполагам, това е до вас, момчета. Вие, момчета, може напълно приложи каквото си искате. Най-ефикасният начин за това може би ще бъде да сортирате свързана изброят в азбучен ред, и така, когато сте вмъкване на нещата, което искате да не забравяйте да ги вмъкнете в азбучен ред така че след това, когато сте опитвайки се да ги търсите, че не трябва да преминават всичко. Вие знаете точно къде тя е, и това е по-лесно. 

Но ако има нещо неща, разпръснати на случаен принцип, вие все още ще има да го прекосяват във всеки случай. И така, ако аз исках просто да си вмъкнете къпина тук и аз исках да търси за го, знам, о, къпина Трябва да се започне с индекса на 1, така че аз знаете мигновено просто търсене в едно. И тогава мога вид прекосяват свързан списък докато не стигнем до BlackBerry, и then-- така ли? 

АУДИТОРИЯ: Ако се опитвате да create-- Предполагам, че по този начин е много прост хеш функция. И ако ние искахме да направим няколко слоя, които харесват, OK, ние искаме да се раздели на като всички азбучен буквите и след това отново да се харесва друг комплект на азбучен писма в рамките на този, ние пускането като хеш маса в рамките на хеш таблица, или като функция в рамките на функция? Или е that-- 

АНДИ Пенг: Така си хеш function-- си хеш таблица може да бъде толкова голям, колкото искаш. Така че в този смисъл, аз мислех, това е много лесно, много просто за мен да се основава само на сортиране на писма от първата дума. И така, има само 26 възможности. Мога да получа само 26 възможности от От 0 до 25, тъй като те могат само започнете от А до Я. Но Ако искахте да се добави, може би, по-голяма сложност или по-бързо тече време, за да си хеш таблица, вие абсолютно може да направи най-различни неща. Можете да направите своя собствена уравнение, което дава по разпределение във вашия думи, а след това, когато търсите, това ще бъде по-бързо. 

Това е напълно до вас, момчета как искате да го привеждат в изпълнение. Мислете за това като само кофи. Ако исках да имам 26 кофи, аз отивам да подреди нещата в тези кофи. Но аз ще има куп неща във всяка кофа, така че, ако искате да го направите по-бързо и по-ефективно, нека да има сто кофи. 

Но тогава ще трябва да измислим начин да подреди нещата така, че те са в правилното кофата те трябва да бъдат в. Но тогава, когато действително искате да погледнете, че кофа, това е много по-бързо, защото има по-малко неща в всяка кофа. И така, да, това е всъщност трик за вас, момчета в pset5 е, че вие ​​ще бъдете изправени пред предизвикателството да създадат само каквото и да е най-ефективната функция може да се мисли за може да съхранява и да провери тези стойности. 

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

Да, има много начини да направите това pset, някои са по-бързо, отколкото други. Аз съм напълно просто ще видим как бързо беше най-бързите Вие, момчета, ще да бъде в състояние да си функции да работят. OK, всеки добре на веригите и хеш таблици? Това всъщност е като един много прост концепция, ако си мислиш за него. Всичко това е е отделяне на каквото и Вашите входове са в кофи, сортирането им, а след това и търсенето в изброява, че има, свързани с. 

Готино. Добре, сега имаме различен вид на структура от данни, която се нарича дърво. Нека да продължим и да се говори за опит които са видимо различен, но в същата категория. По същество, всички дърво е вместо за организиране на данните в линеен начин че хеш таблица можете does-- знам, тя има горна и долна и след това някак си създадете връзка на разстояние от един it-- дървото има горна които ти се обадя корена, и след това го има листа на всички около него. 

И така, всичко, което имаме тук е само най-горния възел който сочи към други възли, които точки за повече възли, и така нататък и така нататък. И така, вие просто трябва разделяне клонове. Това е просто един различен начин на организиране данни, и тъй като ние го наричаме дърво, вие just-- това е просто моделира, за да изглежда като дърво. Ето защо ние го наричаме дървета. 

Hash маса прилича на маса. Едно дърво просто изглежда като дърво. Всичко това е е отделен начин за организиране на възли в зависимост от това какви са вашите нужди. 

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

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

Така че тук, ако аз отивам да потърсите стойността на 66, аз може да започне на 55. Това е 66-голям от 55? Да, това е, така че аз знам, че Mus търсене аз п десния показалец на това дърво. Аз отивам до 77. Добре, е по-малко от 66 или по-голяма от 77? Това е по-малко от, така че да знаете, о, която трябва да бъде левия възел. 

И така, тук ние сме вид консервиране всички от големите неща за масиви, така като динамично преоразмеряване на обекти, като можете да добавяте и изтривате по желание, без да се налага да се притеснявате за фиксираната големи пространства. Ние все още се запазят всички тези прекрасни неща като в същото време е в състояние да се запази влезте и търсене време на двоично търсене че сме били само преди можете да получите една фраза. 

Cool данни структура, вид сложна за изпълнение, на възела. Както можете да видите, всичко е Struct на възела е, че имате ляв и право на показалеца. Това е всичко, това е. Така че вместо само имащ X или предишна. Имате лявата или право, и след това можете да вид ги свържем заедно обаче така решите. 

OK, ние всъщност ще Просто отделете няколко минути. Така че ние ще се върнем тук. Както казах по-рано, I вид обяснено логиката зад това как ние ще се търси чрез този. Ние ще се опитаме pseudocoding това, за да видите ако можем да вид прилагат същата логика на двоично търсене за различен тип структура на данните. Ако вие искате да вземете като двойка та просто да мислят за това. ДОБРЕ. Добре, аз отивам да всъщност просто ви даде не the--, ние ще говорим за Псевдокод първия. Така че няма кой да искате до получаване на хладно оръжие в това, което първото нещо, което искате да направите, когато вие започвате търсенето е? Ако ние не търсим стойността на 66, това, което е първото нещо, което искаме да направим, ако ние искаме да двоичен търсите това дърво? 

АУДИТОРИЯ: Вие искате да изглежда добре и погледнете наляво и виж [недоловим] по-голям брой. 

АНДИ Пенг: Да, точно така. Така че ти започваш да си погледнеш корен. Има много начини, можете да се обаждате то, ти майка възел хора казват. Обичам да казвам, защото корен това е като корените на дървото. Ще разгледаме Вашата корен възел, и вие сте ще видите, е 66-голям или от по-малко от 55. И ако това е по-голяма от, добре, това е по-голяма от, където искаме да изглежда? Къде искаме да търсите сега, нали? Искаме да търсите в дясната половина на това дърво. 

Така че ние имаме, удобно, а указател, който сочи към правото. И така, тогава ние можем да настроите новата ни корен да бъде 77. Ние можем само да отидете навсякъде, където показалецът сочи. Е, о, тук ние започваме на 77, и ние можем само направите това рекурсивно отново и отново. По този начин, вие вид на имат функция. Вие имате начин на търсене, които можете може просто да се повтаря отново и отново, и отново, в зависимост от това къде искате да изглеждате докато в крайна сметка стигна до стойност че можете да започнете да търсите. Има смисъл? 

Аз съм за да ви покажа действителната код, и това е много код. Няма нужда да се побърквам. Ще говорим през него. 

Всъщност, не. Това беше само Псевдокод. OK, това беше само Псевдокод, което е малко сложен, но това е напълно наред. Всеки следващ заедно тук? Ако коренът е нищожна, възвръщаемост невярно, защото това означава вие дори не са нищо там. 

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

И ако корен е нищожна, че това означава, че сте достигнали до края? Това означава, че вие ​​нямате още повече листа да търсите, тогава знаете, о, Предполагам, че не е тук защото след като съм погледна през цялото това нещо и то не е тук, тя просто не може да бъде тук. 

Това прави ли смисъл на всички? Така че това е като двоично търсене консервиране възможностите на свързани списъци. Охлажда се, така и на втория вид на данните, които структурата момчета може да се опита прилагането на вашия pset, вие само трябва да избере един метод. Но може би е алтернативен метод за хеш таблицата е, което ние наричаме синтактично дърво. 

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

Така възелът за това как ние ще определи синтактично дърво е, че ние искаме да имаме Булева, в дума, нали? Така възелът е Boolean като вярно или невярно, на първо място в главата на че масив, е тази дума? На второ място, искате да имате указатели да независимо от останалата част от тях са. Малко по-сложно, малко абстрактно, но Аз ще обясня какво, че всички средства. 

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

И тогава ще трябва от 0 до 26 на буквите, които можете да съхранявате. Ако исках да търсите тук за прилеп, отивам до върха и аз гледам за B. намеря B в моята масив, и така аз знам, OK, е B дума? B не е дума, така че по този начин Аз трябва да продължавам да търся. Отида от B, и аз гледам към указател, който сочи към B и виждам друг масив от информация, същата структура, че преди. 

И here-- о, на следващия писмо, в [недоловим] е A. Така че ние с нетърпение в тази гама. Намираме осмия стойност, и след това ние с нетърпение да видя, о, хей, е, че една дума, е B-A дума? Това не е дума. Ние трябва да продължим да търсим. 

И така, след това ние гледаме към мястото, където показалеца на A точки, и го насочва към друг начин в които ние имаме повече стойност, съхранявана. И в крайна сметка, ние се да B-A-T, която е дума. И така, следващият път погледнете, ти започваш да има, че проверка на, да, това Булева функция е вярно. И така, в смисъл, ние сме вид да има едно дърво с масиви. 

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

ОК готино. Така B-A-T, и след това започваш да търсите. Следващият път, когато започваш да се види, о, хей, това е вярно, Така знам, че това трябва да е една дума. 

Същото е и за зоопарк. Така че тук е нещо точно сега, ако ние Исках да търсите за зоологическа градина, точно сега, В момента не е зоологическа градина дума в нашия речник защото, както вие виждате, на първо място, че имаме Булева върнете вярно е в края на увеличение. Имаме Z-О-О-M. 

И така тук, ние не действително да има думата, зоологическата градина, в нашия речник защото това квадратче не се проверява. Така че компютърът не знаем, че зоологическа градина е дума защото начинът, по който ние сме го съхранява, само увеличение тук всъщност има Булева стойност който е бил включен вярно. Така че, ако искаме да вмъкнете Думата, зоологическа градина, в нашия речник, как ще го направим това? Какво трябва да направим, за да се уверете, че нашата компютър знае, че Z-О-О е дума и не първата дума е Z-O-O-M? 

АУДИТОРИЯ: [недоловим] 

АНДИ Пенг: Точно така, ние искате да се уверите, че това тук, че Булева стойност не е отметнали, че това е вярно. Z-О-О, тогава ние отиваме да се провери дали, така че ние знаем точно, хей, зоологическа градина е дума. Отивам да кажа на компютър, че това е една дума, така че когато проверките за компютърни, той знае, че зоологическа градина е дума. 

Защото не забравяйте, всички тези данни структури, това е много лесно за нас да се каже, о, прилеп е една дума. Zoo е една дума. Zoom е една дума. Но когато сте го построи, компютърът няма представа. 

Така че трябва да го кажа точно в кой момент е тази дума? В кой момент не е една дума? И в кой момент да направя Трябва да намерите неща, и в кой момент да трябва да отида по-нататък? Всеки ясно от това? Готино. 

И така, след това идва проблем за това как да го правим отида за вмъкване нещо че всъщност не е там? Така че нека просто кажем, че искате да вмъкнете думата, баня, в нашия синтактично дърво. Както вие може да видите като в момента всичко, което имаме сега е B-A-T, и тази нова структура на данните там имаше една пинта, че посочи към нула, защото ние приемаме че, о, там е без думи след B-A-T, Защо имаме нужда да се запази като взе нещата след това T. 

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

Отиваме да възложи H, На първо място, тази нищожна, отиваме да се отървете от. Отиваме да имат надолу на H момент. Ако ние виждаме H, ние го искаме за да отидете някъде другаде. 

В тук, тогава ще можем да отписвате да. Ако удари H след Т, о, След това ние знаем, че това е една дума. Булевият ще се върне вярно. Всеки ясно как е станало това? ДОБРЕ. 

Така че по същество всички от тези структури от данни че сме отишли ​​над днес, аз съм отишло над тях наистина, наистина бързо и не на много детайл, и това е ОК. След като започнете да бъркаш с него, вие ще бъдете следене на къде всички указатели, какво се случва във вашия структури от данни, и така нататък. Те ще бъдат много полезни, и това е до вас момчета тотално да разбера как искате да приложат неща. 

И така pset4, на 5-- о, което не е наред. Pset5 е правописни грешки. Както казах и преди, ти започваш да, веднъж отново, изтегляне изходния код от нас. Там ще бъде три основни неща, които ще се изтеглят. Ще изтеглите речници, KERS и текстове. 

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

И така трите блока на програми, които ще ви дадат се наричат ​​dictionary.c, dictionary.h и speller.c. И така всичко се прави dictionary.c това, което иска да се приложи. Тя зарежда думи. Той посочи проверки тях, и го прави сигурен че всичко е поставена правилно. 

diction.h е само една библиотека файл който обявява всички тези функции. И speller.c, ние ще ви дадем. Не е нужно да се променят от него. All speller.c се е да го вземеш, товар това, проверява скоростта на това, тества бенчмарка на като как бързо сте в състояние да направи неща. 

Това е правопис. Просто не се забъркваш с него, но се уверете, уверете, че разбирате това, което прави. Ние използваме функция, наречена getrusage че тества производителността на правописа пул. Всички го прави груб теста за време за всичко във вашия речник, така се уверете, че го разбирам. Бъдете внимателни, за да не се забъркваш с него или друг нещата няма да се показват правилно. 

И по-голямата част от това предизвикателство е за вие наистина да променят dictionary.c. Отиваме да ви дам 140,000 думи от речника. Отиваме да ви дам един текст файл, който има тези думи, и ние искаме да бъде в състояние да организира ги в хеш таблица или синтактично дърво защото, когато ние ви молим да обяснят check-- представете си, ако сте на правописа проверка като Odyssey Омир. Това е като този огромен, огромен тест. 

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

И така, бъдете внимателни, за да разрешите сблъсъци. Вие ще получите един куп от думи на които започват с А. Вие ще получите един куп думи които започват с B. До вас момчета как искате да го решат. Може би има и още ефикасно хеш функция отколкото само първата буква от нещо, и така, че е до вас момчета някак да правите каквото си искате. 

Може би искате да добавите всички букви заедно. Може би искате да направите харесва странни неща за отчитане на броя на буквите, както и да е. До вас, момчета, как искате да направите. Ако искате да направите хеш таблица, ако сте Искам да опитам синтактично дърво, напълно зависи от вас. Аз ще ви предупреди преди време, че Trie обикновено е малко по-трудно само защото има много Допълнителни съвети, за да следите. Но напълно до вас, момчета. Това е далеч по-ефективно в повечето случаи. Вие искате наистина да бъде в състояние да се запази следите на всички ваши указатели. Както направи същото нещо че правя тук. Когато се опитвате да вмъкнете стойности в хеш таблица или да изтриете, уверете се, че сте Наистина следенето от където всичко е така, защото тя наистина е много лесно, защото, ако аз съм опитвайки се да вмъкнете като думата, Анди. Нека просто кажем, че това е истинска дума, думата, Анди, в гигантски списък с A думи. 

Ако аз просто се случи да превъзложите указател погрешно, Опа, там отива целостта на останалата част от моите свързан списък. Сега единствената дума I имам е Анди, а сега всички други думи в речника са били загубени. И така, вие искате да сте сигурни, че да следите всичките си указатели или иначе ти започваш да се получи огромни проблеми в кода си. Начертайте нещата внимателно стъпка по стъпка. Това го прави много по-лесно да се сетиш. 

И накрая, вие искате да бъдете в състояние да тества производителността на вашата програма на големия борд. Ако вие отнеме Посетете CS50 точно сега, ние имаме това, което се нарича голяма дъска. Това е листа с резултатите от най-бързо правописа пъти проверка във всичките CS50 точно сега, мисля, че на върха като 10 Часовете Мисля, осем от тях са служители. Ние наистина искаме вие ​​да ни бият. 

Всички от нас се опитват да приложат най-бързият кодът е възможно. Искаме вие, момчета, за да се опита да оспори ни и приложат по-бързо от всички нас може. И така, това е наистина за първи път, че сме ви питам момчета да се направи, че pset наистина може да направи по какъвто и метод искаш. 

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

АУДИТОРИЯ: Дали сме се оставя да се, ако Исках да проучи бързи начини да се направи хеш таблици онлайн, можем да направим че и цитират код на някой друг? АНДИ Пенг: Да, напълно добре. Така че, ако вие прочетете спец, има ред в спецификацията, която казва, вие, момчета, са напълно безплатни за изследвания хеш функции в какви са някои на по-бързи хеш функции да тече нещата като стига да цитират този код. Така че някои хора вече имат измисли бързи начини за правене на правописа, на бързо начини за съхраняване на информация. Totally до вас, момчета, ако Искам просто да си вземе това, нали? Уверете се, че сте цитиране. Предизвикателството тук наистина че ние се опитваме да тествате е като се уверите, че знаете пътя си около Указатели. Що ли изпълнителните действителната разбъркваща функция и идва с харесват по математика, за да направи това, вие може да изследват независимо методи онлайн вас, момчета искат. Да? 

АУДИТОРИЯ: Можем ли да дам само с помощта на [недоловим]? 

АНДИ Пенг: Да. Можете просто, в коментар, можете да се цитират като, о, взета от бала, ала-, бала, хеш функция. Всеки, който има някакви въпроси? Ние всъщност breezed през секция днес. Аз ще бъда тук, за да отговори на въпросите, както добре. 

Също така, както вече казах, офис часа тази вечер и утре. Спецификацията тази седмица е всъщност супер лесно и супер кратък, за да се чете. Бих предложил да погледнете, само прочетете изцяло от него. 

И Zamyla всъщност ви разходки чрез всяка от функциите трябва да се прилагат, и затова е много, много ясно как да се направи всичко. Само за да се уверете, че сте следене на указатели. Това е много предизвикателна pset. 

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

И така, пълна и абсолютна вяра в себе си момчета, за да бъдат в състояние да победи нашата [недоловим] правопис. Аз всъщност има не всеки писмен мина все още, но аз съм на път да пиша моя. Така че, докато пишете твоя, аз ще се пишат мина. Отивам да се опита да направи мина по-бързо от твоя. Ще видим кой има най-бързия. 

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