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

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

Отново, pset6 е правописни грешки, PSET тази седмица. И тя също така ви съветва, и аз Насърчавам ви да използвате някои други ресурси, специално за тази PSET. По-специално, на три съм изброени на екрана - GDB, които ние сме били запознати с и е като за известно време сега, е ще бъде много полезна тази седмица. Така че сложих, че до тук. Но всеки път, когато работите с C, винаги трябва да се използва GDB да коригиране на грешки в програмите. Тази седмица също valgrind. Някой знае ли какво valgrind прави? 

ПУБЛИКАТА: Тя проверява за изтичане на памет? 

JASON Hirschhorn: Valgrind проверки за изтичане на памет. Така че, ако изчистване нещо в програма, питаш за памет. В края на вашата програма, вие имате да пишат свободно на всичко, което сте malloced да даде паметта обратно. Ако не пиша безплатно в края и вашата програма идва до заключение, Всичко ще автоматично бъдат освободени. И за малки програми, това е Не е кой знае какво. Но ако сте написването на дълго бягане програма, която не се откажат, задължително, след няколко минути или няколко секунди, след това изтичане на памет може да се превърне в огромна сделка. 

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

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

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

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

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

Има много неща се случват на екрана. Но всичко това трябва да бъде относително запознати с вас. На първия ред, ние обяви нов възел. И тогава вътре в тази нова възел, задам цяло число в този възел към едно. Ние виждаме на следващия ред Правя ФОРМАТ командване, но аз съм в сив цвят командата ФОРМАТ защото наистина Важна част е тази линия тук - new_node.n. Какво означава точката предвид? 

ПУБЛИКАТА: Отиди до възела и оценка п стойност за него. 

JASON Hirschhorn: Това е точно така. Dot означава достъп до п част на този нов възел. Това следващия ред какво прави? Майкъл. 

ПУБЛИКАТА: Той създава друг възел който ще сочи към новия възел. 

JASON Hirschhorn: Така че това не е така създаване на нов възел. Той създава какво? 

Аудитория: A показалка. 

JASON Hirschhorn: A показалеца на една възлова точка, както е посочено от този възел * тук. Така той създава указател към възел. И кой възел е тя сочеше да, Майкъл? 

ПУБЛИКАТА: New възел? 

JASON Hirschhorn: New възел. И това сочи там, защото сме го е дал адреса на нов възел. И сега, в този ред ние виждаме два различни начина на изразяване на едно и също нещо. И аз исках да подчертая, как тези две неща са еднакви. В първия ред, ние сочените показалеца. Така че отиваме към възела. Ето какво означава тази звезда. Виждали сме, че преди с указатели. Отиди на този възел. Това е в скоби. И тогава достъп чрез оператора точка н елемент на този възел. 

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

Но аз исках да посоча тези от преди да отиде по-нататък, така че да се разбере че наистина това нещо точно тук е синтактична захар за dereferencing показалеца и след това ще н част от тази структура. Всякакви въпроси за този кадър? OK. 

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

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

Да се ​​прекъсне, че надолу и отидете малко по-бавно. Отивам да сочи към дъската. Така че ние имаме нашия възел пет че ние сме създали в mallocs. Защо всички се смеят? Шегувам се. OK. Така че ние сме malloced пет. Ние създадохме този възел някъде другаде. Ние имаме готовност да отида. Започваме в предната част нашия списък с две. И ние искаме да вмъкнете в сортиран мода. 

Така че, ако ние виждаме две, а ние искаме да се сложи в пет, какво ще правим, когато видим нещо по-малко от нас? Какво? Искаме да вмъкнете пет в тази свързан списък, като ги сортират. Виждаме номер две. И така, какво ще правим? Marcus? 

ПУБЛИКАТА: Обадете се на показалеца на следващия възел. 

JASON Hirschhorn: И защо правим отиваме към следващия? 

ПУБЛИКАТА: Защото това е следващия възел в списъка. И ние знаем само, че на друго място. 

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

Пет е по-голям от четири. Така че ние продължаваме. И сега сме на шест. И какво виждаме в шест? Да, Карлос? 

ПУБЛИКАТА: Six е по-голям от пет. 

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

ПУБЛИКАТА: Two. 

JASON HIRSCHORN: Two. One, за да следите на тока един и една, за да следите на предишната. Това е само поединично свързан списък. Той отива само една посока. Ако имахме двойно свързан списък, където всичко сочеше към нещо след него и нещо пред нея, а след това ние няма да се наложи да го направя. Но в този случай, ние не искаме да загубим следите на това, което са били преди нас, в случай ние трябва да поставите пет някъде в средата. Кажете ни поставяте девет. Какво ще се случи, когато стигнахме до осем? 

ПУБЛИКАТА: Вие ще трябва да получи, че нулевата точка. Вместо да се налага нулевата точка ще трябва да добавят елемент и след това да го насочите към девет. 

JASON HIRSCHORN: Точно така. Така получаваме осем. Стигаме до края на списъка, защото това сочи към нула. И сега, вместо да се налага да го насочите към нищожна имаме го насочите към нашия нов възел. И ние настроите курсора в нашият нов възел към нула. Дали някой има някакви въпроси относно поставянето? Какво става, ако не се грижи за актуализирането на списъка подредени? 

ПУБЛИКАТА: тя Придържайте в началото или в края. 

JASON HIRSCHORN: тя Придържайте се към в началото или в края. Кой трябва да направим? Боби? Защо в края? 

ПУБЛИКАТА: Защото началото вече е запълнена. 

JASON HIRSCHORN: OK. Началото е вече запълнени. Кой иска да се спори срещу Боби. Marcus. 

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

JASON HIRSCHORN: Точно така. Така че, ако мислим по време на работа, на Времетраене на вмъкване в края ще бъде N, размерът на това. Каква е голямата O време на работа на вмъкване в началото? Constant време. Така че, ако не ви е грижа за запазване на нещо, подредени, много по-добре просто да си поставите в началото на този списък. И това може да бъде направено в константно време. 

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

ПУБЛИКАТА: Завръщане невярно? 

JASON HIRSCHORN: връщане фалшиви. Ние не го намери. Ако стигнете до края на списъка и не сте намерили номера, който сте търсите, не е там. Всякакви въпроси за намиране? Ако това е сортиран списък, какво би да бъде различен за нашия търсенето? Да. 

ПУБЛИКАТА: Би намерите първата стойност това е по-голям от този , което търсите и след това връщане фалшиви. 

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

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

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

ПУБЛИКАТА: Така че, ако ти започваш да се изтрие това, бихте ли просто да използвате безплатно, защото вероятно е malloced? 

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

OK. Така че, нека продължим да практикуват кодиране. Отиваме да се кодира три функции. Първият се нарича insert_node. Така че имате код, който аз ви емайл, и ако гледате това по-късно можете да получите достъп до кода в linked.c на интернет страницата на CS50. Но в linked.c, има някои скелет код, който вече е е написана за вас. И след това има няколко функции Вие трябва да напишете. 

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

Това е, което аз те моля да направиш сега. Отново, в linked.c, която ви Всички имаме, е кода на скелет. И вие трябва да видите към дъното Декларацията функция на пробата. Въпреки това, преди да отиде в това кодиране в C, аз силно ви препоръчваме да отидете през стъпките, ние сме били практикуване на всяка седмица. Ние вече сме преминали през снимка на това. Така че трябва да има някакво разбиране за това как работи това. Но бих искал да ви насърча да напишете някои pseudocode преди гмуркане инча И ние ще отидем pseudocode като група. И след това, след като сте написали pseudocode, и след като сме написали нашата pseudocode като група, можете да навлизам в кодиране в C. 

Както главите, функцията insert_node е може би най-трудните от тримата отиваме да пиша, защото аз добавя някои допълнителни ограничения за програмирането, по-специално, че вие няма да вмъкнете всеки дубликати и че списъкът трябва да остане сортирани. Така че това е не-тривиално програма че трябва да се кодира. И защо не си вземеш 5-7 минути само за да се работи по pseudocode и кода. И тогава ние ще започнем става като група. Отново, ако имате някакви въпроси, просто вдигнете ръката си и аз ще дойда на мача. . 

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

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

ПУБЛИКАТА: Така че първото нещо, което направих беше създадете нов указател към възела и I инициализира го насочите към една и съща нещо, че този списък е предната. 

JASON HIRSCHORN: OK. Значи вие създавате нов показалец в списъка не към възела. 

ПУБЛИКАТА: Точно така. Да. 

JASON HIRSCHORN: OK. И след това какво искаме да направим? Какво след това? Ами възел? Ние не разполагаме с един възел. Ние просто имат стойност. Ако искаме да вмъкнете възел, това, което правим трябва да направите първо, преди да можем дори мисля за да го поставите? 

ПУБЛИКАТА: О, съжалявам. ние трябва да се изчистване пространство за един възел. 

JASON HIRSCHORN: Отлично. Нека да направим - OK. Не може да се достигне до това високо. OK. Отиваме да слезем, и след това ние използваме две колони. Аз не мога да отида, че - OK. Създаване на нов възел. Можете да създадете друг показалеца да се изброят или можете просто да използвате списък, тъй като съществува. Вие наистина не трябва да правиш това. 

Така че ние създаваме нов възел. Чудесно. Това е, което правим на първо място. Каква е следващата? 

ПУБЛИКАТА: Изчакайте. Трябва ли да се създаде нов възел сега или трябва да чакаме, за да се уверите, че няма никакви дубликати на възела в списъка, преди да я създадете? 

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

ПУБЛИКАТА: то безплатно. 

JASON HIRSCHORN: Да. Вероятно го освободи. OK. Какво ще правим след като сме създаване на нов възел? Ани? 

ПУБЛИКАТА: Слагаме брой в възел? 

JASON HIRSCHORN: Точно така. Ние поставяме броя - ние изчистване пространство. Отивам да напуснат тази всичко като една линия. Но ти си прав. Ние изчистване пространство, а след това ние поставяме броя инча Ние дори да настроите курсора част от него нула. Това е точно така. И тогава какво да кажем след това? Ние извади тази снимка на дъската. И така, какво ще правим? 

ПУБЛИКАТА: Отиваме в списъка. 

JASON HIRSCHORN: Преминете през списъка. OK. И какво ще се проверява за най-всеки възел. Кърт, какво ще покажат в продължение на всеки възел? 

ПУБЛИКАТА: Виж дали стойността на п на този възел е по-голяма от стойността на п на нашия възел. 

JASON HIRSCHORN: OK. Отивам да се направи - Да, OK. Така че това е п - Отивам да се каже, ако стойността е по-голяма от този възел, тогава какво ще правим? 

ПУБЛИКАТА: Е, тогава ние вмъкнете нещото точно преди това. 

JASON HIRSCHORN: OK. Така че, ако това е по-голяма от тази, След това ние искаме да вмъкнете. Но ние искаме да го поставите точно преди защото ние също ще трябва да бъде следенето, а след това, от това, което беше преди. Така че, преди да вмъкнете. Така че ние вероятно пропуснал нещо по-рано. Ние вероятно трябва да се поддържа следите какво се случва. Но ние ще се върнем там. Така че каква стойност е по-малко от? Кърт, какво ще правим, ако стойност е по-малко от? 

ПУБЛИКАТА: Тогава просто продължавай освен ако това е последният. 

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

ПУБЛИКАТА: [недоловим]. 

JASON HIRSCHORN: Да. Като се има предвид това - Маркъс е прав. Бихме могли да са може би направил нещо по-различно. Но имайки предвид, че сме го създали, тук ние трябва да освободим и след това се върнете. О, момче. Така по-добре? Как е това? OK. Свободна и тогава какво правим се върне, [недоловим]? OK. Да не пропускаме нещо? И така, къде сме следенето на предварително възел? 

ПУБЛИКАТА: Мисля, че ще отида след създаване на нов възел. 

JASON HIRSCHORN: OK. Така че в началото ние ще вероятно - Да, ние можем да създадем указател към нов възел, като предишния показалеца възел и текущ показалка възел. Така че нека да вмъкнете, че тук. Създаване на текущата и предходната указатели към възли. Но кога ще коригира тези насоки? Когато правим това в кода? Джеф? 

ПУБЛИКАТА: - условия стойност? 

JASON HIRSCHORN: Кои един по-специално? 

ПУБЛИКАТА: Аз съм просто объркан. Ако е по-голяма от тази възлова точка, не искаш да кажеш, че искаш да отидеш на следващия възел? 

JASON Hirschhorn: Така че, ако нашата стойност е по-голяма от стойността на този възел. 

Публика: Да, тогава вие ще искате да отиде по-надолу по линията, нали? 

JASON Hirschhorn: Точно така. Така че ние не го поставете тук. Ако стойността е по-малко от този възел, тогава отиваме към следващия възел - или тогава ние вмъкнете преди. 

ПУБЛИКАТА: Изчакайте, който е тази възел и което е стойност? 

JASON Hirschhorn: Добър въпрос. Стойност на тази дефиниция на функция е това, което е дал. Така стойност е броят не ни дават. Така че, ако стойността е по-малка от тази възел, имаме нужда от време, за да вмъкнете. Ако е по-голяма от тази възлова точка, отиваме към следващия възел. И обратно към първоначалния въпрос, обаче, когато - 

ПУБЛИКАТА: Ако стойността е по-голяма от този възел. 

JASON Hirschhorn: И така, какво правим тук? Sweet. Това е правилно. Аз съм просто ще да пиша актуализиране указатели. Но да, с ток една бихте го актуализира до сочи към следващия. Нещо друго, което ти липсва? Така че аз отивам да въведете този код в Gedit. И докато аз правя това, можете да имате още няколко минути, за да работят на кодиране това в C. 

Така че аз имам принос за pseudocode. Един бърз бележка, преди да можем да започнем. Ние може да не е в състояние напълно да довърша това във всички три от тези функции. Има правилни решения за тях че аз ще имейл до вас момчета След раздел, и тя ще бъде публикуван на CS50.net. Така че аз не ви препоръчваме да отидете погледнете разделите. Препоръчвам ви да опитате тези на вашия притежавате, и след това да използвате практиката проблеми, за да проверите вашите отговори. Те всички са били предназначени за тясно се отнасят до и да се придържат към това, което което трябва да направите на снимачната проблем. Така че аз ви насърчавам да практикува тази на собствения си и след това да използвате кода за проверите вашите отговори. Защото аз не искам да се премине към хеш таблици в някакъв момент в секцията. Така че ние не може да получи през всичко това. Но ние ще направим колкото можем сега. 

OK. Нека да започнем. Asam, как да създадете нов възел? 

ПУБЛИКАТА: Нали STRUCT *. 

JASON Hirschhorn: Така че ние са, че до тук. О, съжалявам. Вие казвахте структура *. 

ПУБЛИКАТА: И тогава [? вид?] възел или в възел. 

JASON Hirschhorn: OK. Отивам да го наричат ​​new_node така че ние може да остане последователна. 

ПУБЛИКАТА: И вие искате да зададете, че с глава, на първия възел. 

JASON Hirschhorn: OK. Така че сега това, сочеща - така че това все още не е създаден нов възел. Това е просто сочещи към първи възел в списъка. Как да създадете нов възел? Ако имам нужда от пространство, за да създадете нов възел. Изчистване. И колко е голям? 

ПУБЛИКАТА: Размерът на структурата. 

JASON Hirschhorn: The размер на структурата. И това, което се нарича структура? 

ПУБЛИКАТА: Node? 

JASON Hirschhorn: Node. Така изчистване (sizeof (възел)); ни дава пространство. И е тази линия - едно нещо е неправилно в тази линия. Дали new_node указател към структура? Това е родово име. Какво е това - възел, точно така. Това е възел *. И какво ще правим веднага след ние изчистване нещо, Асан? Кое е първото нещо, което правим? Какво става, ако тя не работи? 

ПУБЛИКАТА: О, проверете дали точки на възловата точка? 

JASON Hirschhorn: Точно така. Така че, ако new_node равнява на равни нищожна, какво ще правим? Това връща булев, тази функция. Точно така. Изглежда добре. Нещо да добавите там? Ние ще добавим неща в края. Но това засега изглежда добре. Създаване на настоящите и предишните указатели. Майкъл, как мога да направя това? 

Публика: Ти нямаше да имаш да направим възел *. Вие ще трябва да не се направи една за new_node но за възли, които вече имат. 

JASON Hirschhorn: OK. Така текущия възел сме на. Ще се обадя, че Curr. Добре. Решихме, които искате да запазите два, защото ние трябва да знаем това, което е пред него. Какво те се инициализира с? 

ПУБЛИКАТА: стойността им в нашия списък. 

JASON Hirschhorn: Така че това, което е най- Първото нещо, което в нашия списък? Или как да знаем, когато началото на нашия списък е? 

ПУБЛИКАТА: Не е ли мина в функцията? 

JASON Hirschhorn: Точно така. Той е приет в точно тук. Така че, ако това е преминал на функцията, начало на списъка, какво трябва да настроите ток, равен на? 

ПУБЛИКАТА: List. 

JASON Hirschhorn: List. Това е точно така. Сега има адрес на началото на нашия списък. А какво да кажем за предишния? 

ПУБЛИКАТА: Списък минус едно? 

JASON Hirschhorn: Има нищо преди него. И така, какво можем да направим, за да означава нищо? 

ПУБЛИКАТА: Null. 

JASON Hirschhorn: Да. Това звучи като добра идея. Perfect. Благодаря. Преминете през списъка. Константин, колко време ще да мине през списъка? 

ПУБЛИКАТА: докато стигнем нищожна. 

JASON Hirschhorn: OK. Така че, ако, докато, за контур. Какво правим? 

ПУБЛИКАТА: Може би за цикъл? 

JASON Hirschhorn: Да го направим за линия. OK. 

ПУБЛИКАТА: И ние кажем - до текущата показалеца не е равно на нула. 

JASON Hirschhorn: Така че, ако ние знаем състояние, как да пишем една линия на базата на разстояние това условие. Какъв вид на една линия трябва да използвам? 

ПУБЛИКАТА: Докато. 

JASON Hirschhorn: Да. Това прави повече смисъл, базирани на разстояние от това, което каза. Ако просто искате да отидете в него ние ще Просто знам, че нещо, то ще направи смисъл да се направи, докато контур. Докато сегашната не е равно на нула, , ако стойността е по-малко от този възел. Akshar, дай ми тази линия. 

ПУБЛИКАТА: Ако текущата-> н п по-малко от стойността. Или обратно това. Превключете че скоба. 

JASON Hirschhorn: Съжалявам. 

ПУБЛИКАТА: Промяна на скобата. 

JASON Hirschhorn: Така че, ако това е по-голяма от стойността. Защото това е объркващо с коментар по-горе, аз ще го направя. Но да. Ако нашата стойност е по-малка от тази възел, какво ще правим? Oh. Аз го имам точно тук. Поставете преди. OK. Как правим това? 

ПУБЛИКАТА: Дали тя все още ме? 

JASON Hirschhorn: Да. 

ПУБЛИКАТА: You - new_node-> следващия. 

JASON Hirschhorn: Така че това, което е че ще е равно? 

ПУБЛИКАТА: Ще равен ток. 

JASON Hirschhorn: Точно така. И така, от друга - какво друго имаме нужда да се актуализира? 

ПУБЛИКАТА: Проверете дали покрай равнява нула. 

JASON Hirschhorn: Ако Предишна - така че ако предишна равнява нула. 

ПУБЛИКАТА: Това означава, че ще да се превърне в главата. 

JASON Hirschhorn: Това означава тя се превърна в главата. Тогава какво ще правим? 

ПУБЛИКАТА: Правим главата равнява new_node. 

JASON Hirschhorn: Head равнява new_node. И защо се отправят тук, не се изброят? 

ПУБЛИКАТА: Защото главата е глобална променлива, която е изходен място. 

JASON Hirschhorn: Sweet. OK. И - 

ПУБЛИКАТА: Тогава се друго предишна-> Следващата равнява new_node. И след това се върнете вярно. 

JASON Hirschhorn: Къде тръгнахме край new_node? 

ПУБЛИКАТА: Бих - Задам, че в началото. 

JASON Hirschhorn: Така че това, което линия? 

ПУБЛИКАТА: След ако изявление проверка, ако това е известно. 

JASON Hirschhorn: Точно тук? 

ПУБЛИКАТА: Бих направил new_node-> н се равнява на стойността. 

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

ПУБЛИКАТА: Ако стойността е по-голяма от Curr-> N - 

JASON Hirschhorn: Как да отиваме към следващия възел? 

ПУБЛИКАТА: Curr-> н е равна на new_node. 

JASON Hirschhorn: Значи п е каква част от структурата? Цялото число. И new_node е указател към възел. Така че това, което част от Curr трябва да актуализираме? Ако не п, тогава това, което е другата част? Ной, което е другата част. 

ПУБЛИКАТА: О, следващия. 

JASON Hirschhorn: Next, точно така. Точно така. В непосредствена близост е най-подходящия. И какво друго ни е нужно да се актуализира, Ноа? 

ПУБЛИКАТА: Указателите. 

JASON Hirschhorn: So ние актуализира ток. 

ПУБЛИКАТА: Пред-> следващия. 

JASON Hirschhorn: Да. ОК, ние ще пауза. Кой може да ни помогне тук? Manu, какво да правим? 

Публика: Трябва да зададете то равно на Curr-> следващия. Но направи това преди предишния ред. 

JASON Hirschhorn: OK. Нещо друго? Akshar. 

ПУБЛИКАТА: Аз не мисля, че ти си означаваше да се промени Curr-> следващия. Мисля, че трябваше да направя Curr равни Curr-> следващия да отидете на следващия възел. 

JASON Hirschhorn: Толкова съжалявам, къде? На каква линия? Тази линия? 

Публика: Да. Уверете се равнява Curr Curr-> следващия. 

JASON Hirschhorn: Така че това е правилното защото сегашната е указател към възел. И ние искаме тя да сочи към следващия възел на това, което в момента става все посочи. Самата Curr има следваща. Но ако трябва да се актуализира curr.next, ние ще се актуализира действителната бележката себе си не, когато този показалеца сочеше. Какво ще кажете за тази линия, все пак. Ави? 

ПУБЛИКАТА: Пред-> следващия равнява Curr. 

JASON Hirschhorn: Така че отново, ако предх е указател към възел, предишна ал-> След това е действителната указател в възел. Така че това ще се актуализира показалеца в възел Curr. Ние не искаме да се актуализира указател в възел. Искаме да актуализира предишна. Е, как да го направим? 

ПУБЛИКАТА: Той просто ще бъде предх. 

JASON Hirschhorn: Точно така. Предишна е указател към възел. Сега ние сме го сменят с по- нов показалец към възел. OK Нека се движи надолу. Накрая, последното условие. Джеф, какво правим тук? 

ПУБЛИКАТА: Ако стойността е равна Curr-> п. 

JASON Hirschhorn: Съжалявам. О, Боже мой. Какво? Стойност == Curr-> п. Какво ще правим? 

ПУБЛИКАТА: Ще освободим нашата new_node, и тогава ще се върне фалшиви. 

JASON Hirschhorn: Това е, което сме написали досега. Дали някой има нещо да добавите преди да направим? OK. Нека да опитаме. Контролът може да стигнат до края на не-нищожен функция. Ави, какво става? 

ПУБЛИКАТА: трябва ли да се сложи връщане Вярно извън примката, докато? 

JASON Hirschhorn: Не знам. Искаш ли да се? 

ПУБЛИКАТА: Няма значение. Не. 

JASON Hirschhorn: Akshar? 

ПУБЛИКАТА: Мисля, че трябваше да сложи връщане фалшиви в края на линия време. 

JASON Hirschhorn: Е, къде искаш да отидеш? 

ПУБЛИКАТА: Подобно извън контура време. Така че, ако излезете от примката, докато това означава, че че сте достигнали до края и нищо не се е случило. 

JASON Hirschhorn: OK. И така, какво ще правим тук? 

АУДИТОРИЯ: Връщате фалшива там. 

JASON Hirschhorn: О, ние го направи и на двете места? 

Публика: Да. 

JASON Hirschhorn: OK. Трябва ли да отида? О, Боже мой. Съжалявам. Извинявам се за екрана. Това е нещо откача върху нас. Така че изберете опция. Нула, на кода, се затваря програмата. Един вмъква нещо. Нека да вмъкнете три. Вложката не е била успешна. Отивам да разпечатате. Аз нямам нищо. OK. Може би това е просто случайност. Поставете единия. Не е успешна. OK. Нека да тече през GDB наистина бързо да провери какво се случва. 

Запомни GDB. / Името на вашия програмата ни попадне в GDB. Това да не е много, за да се справят? В мига? Вероятно. Затворете очи и поемете някакъв дълбок диша, ако ви омръзне на проблемите в него. Аз съм в GDB. Кое е първото нещо, което правя в GDB? Трябва да разбера какво става тук. Нека да видим. Ние имаме шест минути до фигура какво става. Пробив главната. И тогава какво да правя? Карлос? Изпълни. OK. Нека да изберете опция. И какво общо има N направя? Next. Да. 

ПУБЛИКАТА: Още не споменавате - не ми каза, че главата, че е инициализира с нула в началото. Но аз мислех, че каза, че е ОК. 

JASON Hirschhorn: Да вървим - нека да разгледаме в GDB, а след това ще се върнем. Но това звучи като вече имате някои идеи за това какво се случва. Така че ние искаме да вмъкнете нещо. OK. Ние сме вмъкнете. Моля въведете вътр. Ние ще вмъкнете три. И тогава аз съм по тази линия. Как мога да отида да започне отстраняване на грешки вложката известна функция? О, Боже мой. Това е много. Е, че откачам много? 

ПУБЛИКАТА: О, тя почина. 

JASON Hirschhorn: Току-що го извади. OK. 

ПУБЛИКАТА: Може би това е другия край на жицата. 

JASON Hirschhorn: Уау. Така че най-долния ред - това, което казахте? 

ПУБЛИКАТА: Казах иронията на техническата трудности в този клас. 

JASON Hirschhorn: Знам. Ако само имах контрол върху тази част. [Недоловим] Това звучи страхотно. Защо не започнеш да мислиш за момчета това, което би могъл да направи грешен, и ние ще се върнем в 90 секунди. 

Avica, аз отивам да ви попитам как да отида вътре insert_node да го развенчава. Така че това е мястото, където последно бяхме стигнали. Как мога да вляза вътре insert_node, Avica, да се проучи какво се случва? Какво GDB команда? Break не ще ме отведе вътре. Знае ли Marquise? 

ПУБЛИКАТА: Какво? 

JASON Hirschhorn: Какво команда GDB Да използвам за да влезем вътре тази функция? 

ПУБЛИКАТА: Стъпка? 

JASON Hirschhorn: Стъпка чрез S. Това ме отвежда вътре. OK. New_node mallocing малко пространство. Всичко това изглежда като това продължава. Нека да разгледаме new_node. Тя има някакъв адрес от паметта. Да проверим - това е всичко правилно. Така че тук всичко изглежда да се работи правилно. 

ПУБЛИКАТА: Каква е разликата между P и дисплей? 

JASON Hirschhorn: P щандове за печат. И така, вие ме питате какъв е разлика между това и това? В този случай, нищо. Но като цяло има някои различия. И вие трябва да погледнете в ръководството GDB. Но в този случай, нищо. Склонни сме да се използва за печат, все пак, защото ние не трябва да се направи много повече, отколкото отпечатате само една стойност. 

OK. Така че ние сме на линия 80 от нашия код, създаване възел * Curr равна на списък. Нека да разпечатате Curr. Това се равнява на списък. Sweet. Изчакайте. Това се равнява на нещо. Това не изглежда правилно. Ето. Това е така, защото в GDB, нали, ако това е линията, която си върху него все още не се изпълнява. Така че ще трябва наистина да въведете до изпълнение на линия преди да види резултатите от нея. Така че ние сме тук. Ние просто изпълнява този ред, предишния равнява на нула. Така че отново, ако ние отпечатате предишния няма да видим нищо странно. Но ако ние действително изпълнява тази линия, след това ще видим че тази линия е работил. 

Така че ние имаме Curr. Това са както добре. Нали така? Сега сме по тази линия тук. Докато Curr не прави равен нула. Е, какво прави Curr равен? Ние току-що видях, че се равнява на нула. Ние го отпечатва. Ще го разпечатате отново. Така е, че докато линия ще се изпълни? 

Публиката: Не. 

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

Първият включва, Curr, по подразбиране е равно на нула. И този цикъл тя изпълнява само ако Curr не е нищожна. И така, как мога да получа около това? Виждам три ръце. Аз ще чакам за повече от три. Маркъс, какво мислиш? 

ПУБЛИКАТА: Е, ако имате нужда от него, за да изпълнява повече от веднъж, просто го смените с по-Do-а линия. 

JASON Hirschhorn: OK. Това ще реши нашия проблем, все пак? 

ПУБЛИКАТА: В този случай не поради факта, че списъкът е празен. Така че, най-вероятно просто трябва да добавите изявление, че ако контур изходи тогава ще трябва да бъде в края на списъка, в който да ви насочи може просто да го вмъкнете. 

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

ПУБЛИКАТА: Ако вече имам възел malloced, бихте могли просто да се каже, new_node-> следващия равнява на нула, защото тя трябва да бъде в края. Или new_node-> следващия равнява на нула. 

JASON Hirschhorn: OK. Извинете. New_node-> следващия равнява на нула защото сме в края. Това не го инча Как да го сложи в списъка? Точно така. Това е просто да я оставяте равно на. Не как правим всъщност го постави в списъка? Какво сочи към край на списъка? 

ПУБЛИКАТА: Head. 

JASON Hirschhorn: Моля? 

ПУБЛИКАТА: Head сочи на края на списъка. 

JASON Hirschhorn: Ако няма нищо в списъка, главата е насочена към край на списъка. Така, че ще работи за първо вмъкване. Какво ще кажете, ако има няколко неща в списъка? Than ние не искаме да се създаде оглави равна на new_node. Какво искаме да правим там? Да? Вероятно предишния. Ще стане ли? Спомнете си, че предишната е просто указател към възел. И предишния е локална променлива. Така че тази линия ще създаде локална променлива, предишния, равна на или сочещи към този нов възел. Това всъщност няма да го сложи в нашия списък, все пак. Как да го сложи в нашия списък? Akchar? 

ПУБЛИКАТА: Мисля, че ти направи ток-> следващия. 

JASON Hirschhorn: OK. Curr-> следващия. Така че отново, че единствената причина, че сме надолу тук е, какво прави ток, равен? 

ПУБЛИКАТА: равно нула. 

JASON Hirschhorn: И какво от това ще стане, ако ние направим нула-> следващия? Какво ще получите? Ще получите грешка сегментация. 

ПУБЛИКАТА: Do Curr равнява нула. 

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

ПУБЛИКАТА: Previous-> следващия? 

JASON Hirschhorn: Previous-> следващия е това, което ние искаме да се актуализира, защото това действително ще го вмъкнете в на края на списъка. Имаме още един бъг, все пак, че ние ще тичам в. Какъв е този бъг? Да? 

ПУБЛИКАТА: Ще се върнете невярно в този случай? 

JASON Hirschhorn: О, се ще се върне фалшиви. Но има и друг бъг. Така че ние ще трябва да се сложи в замяна вярно. 

ПУБЛИКАТА: Има ли още предишния равен нищожна в горната част на списъка? 

JASON Hirschhorn: Значи предишния още е равно на нула в самото начало. Така че как можем да получим над това? Да? 

ПУБЛИКАТА: Мисля, че можете да направите проверка преди цикъла време, за да видим дали това е празен списък. 

JASON Hirschhorn: OK. Така че нека да отидете тук. Направете проверка. Ако - 

ПУБЛИКАТА: Така че, ако главата равнява се равнява на нула. 

JASON Hirschhorn: Ако главата равнява се равнява на нула - че ще ни каже дали е празен списък. 

ПУБЛИКАТА: И тогава вие направи главата равнява ново. 

JASON Hirschhorn: Head равнява new_node? И какво друго трябва да направим? 

ПУБЛИКАТА: И след това се върнете вярно. 

JASON Hirschhorn: Не съвсем. Ние пропускаме една стъпка. 

ПУБЛИКАТА: New_node следващия трябва да сочи към нула. 

JASON Hirschhorn: Точно така, Алдън. И тогава можем да се върнем вярно. OK. Но тя все още е добра идея да се правят неща, в края на списъка, нали? Добре. Ние все още може да се получи в действителност на края на списъка. Така е този код глоба, ако ние сме в края на списъка и там са някои неща в списъка? Нали така? Защото ние все още имаме идея Маркъс. Бихме могли да излезете от този цикъл, защото ние сме в края на списъка. Така че ние все още искаме това кодира тук? 

Публика: Да. 

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

Публиката: Не. 

JASON Hirschhorn: OK. Така че ние сме направили няколко промени. Ние сме направили тази проверка, преди да отиде в за празен списък. Така че ние сме се погрижили празен списък. И тук ние се грижи за вмъкване нещо в края на списъка. Така изглежда, че тази линия, докато поемането грижат за нещата между тях, някъде в списъка, ако има неща в списъка. 

OK. Нека да се кандидатира отново тази програма. Не е успешна. 

Публика: Ти не го направи. 

JASON Hirschhorn: О, Аз не го направи. Добър въпрос, Майкъл. Да добавим марка свързани. Line 87 има грешка. Линия 87. Алдън, това е линията, която ми даде. Какво не е наред? 

ПУБЛИКАТА: Тя трябва да бъде да се присвоява. 

JASON Hirschhorn: Отлично. Точно така. Тя трябва да бъде нула. Да направим отново. Compile. OK. Нека да вмъкнете три. Вложката е била успешна. Нека да го разпечатате. О, ако само можехме да се провери. Но ние не сме направили отпечатате функция все още. Нека да въведете нещо друго. Какво трябва да въведа? 

ПУБЛИКАТА: Seven. 

JASON Hirschhorn: Седем? 

Публика: Да. 

JASON Hirschhorn: Нямаме вина за сегмента. Така че ние имаме един, но ние ясно не могат да получат два. Това е 05:07. Така че бихме могли да развенчава тази в продължение на три минути. Но аз отивам да ни остави тук и преминете към хеш таблици. Но отново, отговорите за този код Аз ще го имейл до вас след малко. Ние сме много близо до него. Аз силно ви препоръчваме да разбера какво става тук и да я поправи. Така че аз ще ви изпратим имейл, този код като добре плюс решение - вероятно разтвора по-късно. Първо този код. 

Другото нещо, което искам да направя, преди да сме Финалът е, че не сме освободени нищо. Така че аз искам да ви покажа това, което valgrind изглежда. Ако бягаме valgrind граници на нашата програма,. / свързани. Пак според този слайд, ние би трябвало да работи valgrind с някакъв вид вариант, в този случай - Теч-проверка = пълна. Така че нека да напише valgrind - Теч-проверка = пълна. Така че това ще продължи valgrind на нашата програма. И сега програмата действително работи. Така че ние ще го изпълним точно като преди, сложи нещо инча Отивам да се постави в три. Това работи. Аз няма да се опита да сложи в нещо друг, защото ние ще получите SEG невярно в този случай. Така че аз съм просто ще се откажат. 

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

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

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

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

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

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

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

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

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

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

ПУБЛИКАТА: Тя може да намерите най- индекс в константно време? 

JASON Hirschhorn: Това Не е това, което означава. Но това е едно добро предположение. Някой друг да има предположение какво означава това? Това е добра хеш функция е детерминирана? Ани? 

ПУБЛИКАТА: Това е ключ може да се картографира само за едно място в хеш таблицата. 

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

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

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

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

ПУБЛИКАТА: Нула. 

JASON Hirschhorn: Защо нула? 

ПУБЛИКАТА: Защото три по модул три е равно на нула? 

JASON Hirschhorn: Three по модул три е равно на нула. Това е голямо предположение, и това е вярно. Така че в този случай той трябва да вероятно отидете на нула. Така че по-добър начин да се гарантира, че тази хеш Функцията връща само валидни индекси се да го по модул от размера на таблицата. Ако имате каквито и да е по модул тази възвръщаемост от три, вие винаги ще получите нещо средно между нула, едно, а две. И ако това винаги се връща седем, и винаги по модул от три, ти си Винаги ще получите едно и също нещо. 

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

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

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

Така че сложих в тиква. Тя връща нула. И сложих тиква тук. След това сложих в - това, което е още един Хелоуин-тематични нещо? 

ПУБЛИКАТА: Candy. 

JASON Hirschhorn: Candy! Това е страхотно. Сложих в бонбони и бонбони също ми дава нула. Какво да правя? Някакви идеи? Защото всички видове знам какво е отделен верижното. Така че някакви идеи какво да правя? Да. 

ПУБЛИКАТА: Поставянето на низ всъщност в хеш таблицата. 

JASON Hirschhorn: Така че ние ще привлече добра идея тук. OK. 

ПУБЛИКАТА: Нека Hashtable [Недоловим] показалеца, който сочи към началото на списъка. И след това са тиква бъде първата стойност в тази свързан списък и бонбони бъде втората стойност в този свързан списък. 

JASON Hirschhorn: OK. Marcus, това беше изключително. Отивам да се прекъсне, че надолу. Marcus казва не презапишете тиква. Това би било лошо. Не поставяйте бонбони някъде другаде. Отиваме, за да ги сложи както на нула. Но ние ще се справим с което ги излага на нула създаване на списък на нула. И ние отиваме да се създаде списък на всичко, което преобразува до нула. И най-добрият начин сме се научили да се създаде списък, който може да расте и да се намалят динамично не е в друг масив. Така че не е многомерен масив. Но просто да се създаде свързан списък. 

Така че това, което той предложи - Ще получите нова - е да се създаде масив с указатели, масив от указатели. OK. Някаква идея или намек какво вида на тази указатели трябва да бъде? Marcus? 

ПУБЛИКАТА: указатели към - 

JASON Hirschhorn: Защото каза свързан списък, така че - 

ПУБЛИКАТА: указатели на възлите? 

JASON Hirschhorn: указатели на възлите. Ако нещата в нашата обвързана списък са възли тогава те трябва да бъде възел указатели. И какво те се равнява първоначално? 

ПУБЛИКАТА: Null. 

JASON Hirschhorn: Null. Така че там е нашето празно нещо. Тиквени връща нула. Какво ще правим? Разходка с мен чрез него? Всъщност, Marcus вече ми даде. Някой друг ме минеш през нея. Какво правим, когато ние - това изглежда много подобен на това, което ние просто правим. Ави. 

ПУБЛИКАТА: Отивам да взема предположение. Така че, когато можете да получите бонбони. 

JASON Hirschhorn: Да. Е, имаме тиква. Нека да вземем първия милион. Имаме тиква. 

ПУБЛИКАТА: OK. Тиквени връща нула. Така че да го поставите в това. Или всъщност, да я поставите в свързан списък. 

JASON Hirschhorn: Как правим я оплете в свързан списък? 

ПУБЛИКАТА: О, действителната синтаксис? 

JASON Hirschhorn: Просто върви - да кажем нещо повече. Какво ще правим? 

Публика: Ти просто поставете че като първия възел. 

JASON Hirschhorn: OK. Така че ние имаме нашия възел, тиква. И сега как да го поставите? 

ПУБЛИКАТА: Вие определяте то към показалеца. 

JASON Hirschhorn: Кои показалка? 

ПУБЛИКАТА: Показалецът на нула. 

JASON Hirschhorn: Е, къде прави този момент? 

Публика: Да присвоява точно сега. 

JASON Hirschhorn: Е, тя посочи към нула. Но аз съм като в тиква. Така че, когато трябва да го насочите? 

Публика: Да тиква. 

JASON Hirschhorn: Да тиква. Точно така. Така че това говори за тиква. И къде е този указател в тиква точка? За 

ПУБЛИКАТА: Null. 

JASON Hirschhorn: За нула. Точно така. Така че ние просто добавя нещо в свързан списък. Ние току-що написах този код, за да направите това. Почти ние почти го напълно смахнат. Сега поставете бонбони. Нашата бонбони също отива към нула. И така, какво ще правим с бонбони? 

ПУБЛИКАТА: Това зависи от това дали Не се опитваме да го оправи. 

JASON Hirschhorn: Това е точно така. Тя зависи от това дали или не ние се опитваме да го оправи. Да предположим, че не сме ще го оправи. 

ПУБЛИКАТА: Ами тогава, както ние обсъдихме и преди, най-простата си, само за да го сложи още в самото начало, така че показалецът от нула точки за бонбони. 

JASON Hirschhorn: OK. Дръж се. Нека създадем бонбони точно тук. Така че този указател - 

Публика: Да, сега следва да се посочи бонбони. След това имате показалеца от бонбони точка за тиква. 

JASON Hirschhorn: Така ли? И казват, че имам още нещо за карта до нула? 

ПУБЛИКАТА: Ами, просто направи същото нещо? 

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

OK. Всякакви въпроси за отделни верижното? Как работи това? Моля, да ги питам сега. Аз наистина искам да се уверете, че всички разберем това, преди да се отправите. 

ПУБЛИКАТА: Защо ви постави тиква и бонбони в същото част от хеш таблицата? 

JASON Hirschhorn: Добър въпрос. Защо ние да ги постави в същата част от хеш таблицата? Е, в този случай нашата хеш функция връща нула за тях двамата. Така че те трябва да отидат в indice нула защото това е мястото, където отиваме да за да ги гледам, ако ние някога искам да ги гледам. Отново, с подход линейни сондиране ние няма да ги пуснат едновременно на нула. Но в подхода отделна верига, ние ще ги постави както на нула и след това да създадете списък на разстояние от нула. 

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

OK. Карлос. Linear сондиране ще включва - ако ние открихме сблъсък на нула, ние ще изглежда в следващата място, за да се види дали тя беше отворена и го сложи там. И тогава ние с нетърпение в следващия спорта и да видим дали това е била отворена и го сложи там. Така ние откриваме следващия наличен отворено място и го сложи там. Някакви други въпроси? Да, Ави. 

ПУБЛИКАТА: Като продължение на тази, какво искаш да кажеш с следващото място? В таблицата хашиш или в свързан списък. 

JASON Hirschhorn: За линеен програмиране, не са свързани списъци. Следващото място на хеш таблицата. 

ПУБЛИКАТА: OK. Така че хеш таблицата ще бъде инициализира с размера - като броят на низове че си поставяте? 

JASON Hirschhorn: Може би искам тя да бъде наистина голям. Да. Ето една снимка на това, което ние просто извади на дъската. Отново имаме сблъсък точно тук. на 152. И ще видите, ние създадохме свързан списък на разстояние от него. Отново, хеш таблица отделна навързването подход не е ли едно трябва да се вземат за определени проблеми шест но е, че много от студентите са склонни да се вземат. Така че на тази бележка, нека поговорим накратко преди да се отправите за проблем шест, и след това аз ще споделя една история с вас. Имаме три минути. 

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

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

След това е размер. Нека прескочим размер. Най-накрая сте се разтоварят. Разтоварете е едно ние не са изготвили върху дъската или още кодирани. Но аз ви насърчавам да се опита да го кодиране в нашата извадка свързан списък например. Но разтоварят интуитивно е подобен на свободно - или искам да кажа е подобна, за да проверите. С изключение на сега всеки път, когато започваш чрез, вие не просто проверка, за да виж, ако имате стойност там. Но вие приемате този възел и го освободят, по същество. Това е, което разтовари иска от вас да направите. Free всичко, което сте malloced. Така че ти започваш през целия списък отново, преминавайки през целия хеш маса отново. Този път не проверяват за да видите какво е там. Просто освободи това, което е там. 

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

И не опаковам още, Akchar. Нетърпелив бобър. Исках да кажа, благодаря ви момчета за идване в раздел. Имате Happy Halloween. Това е моят костюм. Ще бъде облечен тази в четвъртък ако те видя в работно време. И ако сте любопитни за някои по- фон като на този костюм, се чувстват безплатно да проверите 2011 раздел за една история за това, защо съм носенето на тиква костюм. И това е една тъжна история. Така че се уверете, че имате близките някои тъкани. Но по този въпрос, ако имате някакви въпроси, аз ще се придържаме около извън след раздел. Успех на проблема определя шест. И както винаги, ако имате някакви въпроси, да ме уведомите.