[За възпроизвеждане на музика]
SPEAKER 1: Добре.
Всеки добре дошли обратно към раздел.
Надявам се, че всички вие сте успешно възстановени от вашия тест
от миналата седмица.
Знам, че е малко луд в пъти.
Както казах и преди, ако сте в рамките на стандартното отклонение,
наистина не се тревожи за това, особено за по-малко удобни раздел.
Ето за това къде трябва да бъде.
>> Ако сте направили страхотно, след страхотно.
Слава на вас.
И ако се чувствате като теб трябва още малко помощ, моля
Чувствайте се свободни да се постигне от всяка от TFS.
Ние всички сме тук, за да помогнем.
>> Ето защо ние учим.
Ето защо аз съм тук, всеки понеделник за вас момчета и в офиса часа в четвъртък.
Така че, моля, чувствайте се свободни да ме уведомите Ако се притеснявате за нищо
или ако има нещо, за викторината че искате наистина искал да се обърна.
>> Така че в дневния ред за днес е всичко за структури от данни.
Някои от тях са просто щеше да бъде просто за да сте запознати с тях.
Вие не може някога изпълнение тях в този клас.
Някои от тях щете, като за правопис pset.
>> Вие ще имате избор между хеш таблици и опитва.
Така че ние със сигурност ще се случва през тези.
Това ще бъде определено по рода на участък с високо ниво днес, обаче,
защото има много от тях, и ако отидохме в подробностите по изпълнението
на всички от тях, ние не би дори да получите чрез свързани списъци
а може би и по-малко на хеш таблици.
>> Така че носят с мен.
Ние няма да правим колкото кодираща този момент.
Ако имате някакви въпроси относно това или искате да видите това на практика
или го изпробвате за себе си, Определено препоръчвам
ще study.cs50.net, които има примери за всяко от тях.
Ще имам PowerPoints с бележки, които ние
са склонни да използват, както и някои програмиране упражнения, особено за неща,
като свързани списъци и двоичен дървета стекове и знаци.
Така че малко по-високо ниво, което би било хубаво за вас, момчета.
>> Така че с това, ние ще се стартира.
И също така, yes-- викторини.
Мисля, че повечето от вас, които са в моята секция има си викторини,
но дойде някой или някаква причина не, те са точно тук, в предната част.
>> Така свързани списъци.
Знам, че този вид отива да архивирате преди викторина.
Това беше преди седмица че сме научили за това.
Но в този случай, ние просто ще отида малко по-задълбочено.
>> Така че, защо бихме могли да изберем свързан списък над масив?
Това, което ги отличава?
Да?
>> АУДИТОРИЯ: Може да разширите свързан изброят срещу фиксиран размер на масива.
SPEAKER 1: Точно така.
Масивът е фиксиран размер има предвид, че свързан списък е с различен размер.
Така че, ако ние не знаем как много искаме да се съхранява,
свързан списък ни дава голямо начин да се направи това, защото ние можем само
добавяне на нов възел и добавяне на друг възел и добавяне на друг възел.
Но това, което може да е компромис?
Дали някой си спомня компромис между масиви и свързани списъци?
Mmhmm?
>> АУДИТОРИЯ: Трябва да се мине през целия път
чрез свързан списък намиране на елемент в списък.
В масив, можете да намерите само един елемент.
>> SPEAKER 1: Точно така.
Така че с arrays--
>> АУДИТОРИЯ: [недоловим].
>> SPEAKER 1: С масиви, имаме това, което се нарича случаен достъп.
Това означава, че ако искаме това, което е някога петата точка на списък
или петата точка на нашата масив, можем просто да го вземете.
Ако това е свързан списък, ние имаме превъртите през, нали?
Така достъп до елемент в масив е константно време,
като има предвид, с свързания списък би най-вероятно ще бъде на линейното време, защото може би
нашата елемент е чак в края.
Ние трябва да се търси чрез всичко.
Така че с всички тези данни структури Отиваме
да се разходите малко повече време на, какви са плюсовете и минусите.
Когато може да искаме да използвате една върху друга?
И това е вид на голям нещо, за да отнемат.
>> Така че ние имаме тук определяне на възел.
Това е като един елемент в нашата свързан списък, нали?
Така че всички ние сме запознати с нашите typedef structs,
който отиде в прегледа за последен път.
Това е в общи линии просто създаване друг вид данни, които бихме могли да използваме.
>> И в този случай, това е някакъв възел че ще проведе някои число вътре.
И тогава това, което е втората част тук?
Някой?
>> АУДИТОРИЯ: [недоловим].
>> SPEAKER 1: Да.
Това е указател към следващия възел.
Така че това всъщност трябва да бъде тук.
Това е указател от тип възел към следващото нещо.
И това е, което те обхваща нашия възел.
Cool.
>> Добре, така че с търсене, тъй като бяхме просто казвам, преди ръка, ако сте
ще се търси чрез, Имате ли наистина да превъртите
чрез вашия свързан списък.
Така че, ако ние не търсим за броя 9, ние ще започне в главата ни
и това ни напомня в началото на нашия свързан списък, нали?
И ние казваме, добре, прави това възел съдържа номера 9?
Не?
>> Добре, да отидете на следващия.
Следвайте го.
Дали тя съдържа номера 9?
Не.
Следвайте следващия.
>> Така че ние трябва действително да превъртите чрез нашата свързан списък.
Не можем просто да отидете директно до мястото, където 9 е.
И ако вие действително искате да вижте някои псевдо-код там.
Ние имаме някои функция за търсене тук че отнема in-- какво го взема в?
Какво мислите вие?
Така лесна.
Какво е това?
АУДИТОРИЯ: [недоловим].
SPEAKER 1: Броят търсим.
Така ли е?
И какво би това съответства?
Това е указател към?
>> Аудитория: A възел.
>> SPEAKER 1: A възел към списъка че ние не търсим в, нали?
Така че ние имаме някои възли са показалецът тук.
Това е момент, който ще всъщност обхождане чрез нашия списък.
Ние го настроите равна на списък защото това е просто
създаване то равно на началото на нашия свързан списък.
>> И докато това не е NULL, докато ние все още имаме неща в нашия списък,
проверка, за да се види дали този възел има броя, което търсим.
Назад вярно.
В противен случай, той се актуализира, нали?
>> Ако е NULL, ние се оттегляме нашата линия, докато и връщане фалшиви
защото това означава, че не сме го намерили.
Всички ли се как се работи?
OK.
>> Така е и с вмъкване, можете има три различни начина.
Може да се добавя нищо, можете да добавите и можете да вмъкнете в асорти.
В този случай, ние сме ще направим сравнява първите.
Някой знае ли как тези три случая може да се различават?
>> Така сравнява първите означава, че сте поставили то в предната част на вашия списък.
Така че, това би означавало, че няма значение какъв е вашият възел е, без значение
каква стойност е, ти започваш да го пуснат тук отпред, OK?
Това ще бъде първият елемент във вашия списък.
>> Ако го добавите, че ще за да отидете на гърба на вашия списък.
И поставете в асорти означава, че сте ще сложи действително на мястото
където тя продължава да си свързан списък сортиран.
Отново, как да използвате тези и когато използвате
им ще варира в зависимост от вашия случай.
Ако това не е необходимо да да се сортира, сравнява първите клони
да бъде това, което повечето хора използвате, защото не правим
трябва да премине през целия списък да намерите в края, за да го добавите, нали?
Можете просто да го придържаме полето вътре.
>> Така че ние ще отидем през вмъкване 1 в момента.
Така че едно нещо, което аз отивам да Силно препоръчвам на този pset
е да се направи нещата, както винаги.
Това е много важно да се актуализира Вашите указатели в правилния ред
защото ако ги актуализира малко от ред,
ти започваш да се окажете загуба на части от вашия списък.
>> Така например, в този случай, ние сме казва главата само точка 1.
Ако ние просто направи това без да записвате това 1,
ние нямаме представа какво 1 трябва да се отбележи сега
защото сме загубили това, което главата посочи.
Така че едно нещо, което да се помни, когато правиш на прикрепяне
е да спаси това, което на главни точки на първата,
След това я прехвърли, и след това да актуализирате какво ново вашия възел трябва да посочат.
В този случай, това е един от начините да го направя.
>> Така че, ако бяхме го направили по този начин където ние просто преместени на главата,
ние губим основно ни Целият списък, нали?
Един от начините да го направите е да има по 1 точка На следващо място, и след това да има точка на главата до 1.
Или можете да направите нещо като временно съхранение, което говорихме.
>> Но пренасочване си указатели в правилния ред
ще бъде много, много важно за този pset.
В противен случай, вие ще трябва хеш маса или да опитате, че просто ще се
само част от думите, които ви искам и след това you're-- mmhmm?
АУДИТОРИЯ: Какво е временната нещо съхранение сте говориш?
SPEAKER 1: временно съхранение.
Така че основно друг начина, по който може да направи това
се съхранява главата на нещо като го съхранява временно променлива.
Присвояване на 1 и след това да актуализирате 1 до точка
какъвто и да е главата, използвана да посочи.
По този начин е очевидно по-елегантен, защото
не се нуждаят от временна стойност, но просто предлага друг начин да го направя.
И ние всъщност имаме някакъв код за това.
Така че за свързан списък, ние всъщност има някакъв код.
Така поставете тук, това се поставите символа.
Значи това влиза в главата.
>> Така че първото нещо, което трябва да създадете своя нов възел, разбира се,
и да се провери за NULL.
Винаги добра.
И тогава ще трябва да зададете стойностите.
Всеки път, когато се създаде нов възел, вие Не знам какво е, сочещи към следващия,
така че искам да го инициализира с NULL.
Ако все пак в крайна сметка посочи нещо друго, той се преотстъпва и това е добре.
Ако това е първото нещо, в списъка, тя се нуждае от
да сочи към NULL защото това е края на списъка.
>> Така че след това да я поставите, ние виждаме тук се възлагане на следващата стойност на нашата възел
да бъде каквото и да е главата, което е това, което имахме тук.
Това е, което ние просто го направих.
И тогава ние сме възлагане главата до точка в нашия нов възел, защото си спомням,
нов някои указател към възел, и това е точно това, което е на главата.
Това е точно защо ние имат тази стрелка Accessor.
Cool?
Mmhmm?
>> АУДИТОРИЯ: Трябва ли да инициализира нов до NULL първо,
или можем просто да го инициализира с глава?
>> SPEAKER 1: New следващия трябва да бъде NULL за да започнете
защото не знаете къде ще бъде.
Също така, това е един вид Точно като парадигма.
Можете да го настроите, равен на NULL, само за да направи сигурни, че всички ваши бази са покрити
преди да направите всяко пренасочване, така че сте винаги е гарантирано, че ще
да се посочи конкретна стойност спрямо като стойност за боклук.
Защото, да, ние присвоите Новият следващия автоматично,
но това е по-точно като Добра практика е да го инициализира
по този начин и след това пренасочване.
>> ОК, така че двойно свързан списък сега.
Какво мислите?
Какво е по-различно с двойно свързан списък?
>> Така че в нашите свързани списъци, ние можем се движи само в една посока, нали?
Ние имаме само следващия.
Можем само да се върви напред.
>> С двойно свързан списък, ние също може да се движи назад.
Така че ние имаме не само номер, който ние искаме да се съхранява,
имаме къде да сочи към следващия и къде точно идва.
Така че това дава възможност за някои по-добре прекосява.
>> Така двойно свързани възли, много подобно, нали?
Единствената разлика сега е, че ние има следващата и предишната.
Това е единствената разлика.
>> Така че, ако бяхме да се добавя нищо append-- ние не оказват код за това до here--
но ако ви се налага да се опита и поставете го, важното
е, че трябва да се направи уверете, че сте възлагане
както предишния си и си следващата показалеца правилно.
Така че в този случай, бихте не само се инициализира следващия,
нулирате предишния.
Ако ние сме в началото на списъка, ние не само ще направи главата равен нова,
но нашата нова предходната трябва точка на главата, нали?
>> Това е единствената разлика.
И, ако искате повече практика с тези със свързани списъци, с вмъкване,
с изтриване, с вложка в един разнообразен списък,
моля, проверете study.cs50.net.
Има един куп страхотни упражнения.
Аз силно ги препоръчвам.
Иска ми се да имах време да мине през тях но има много структури от данни
да се измъкне сам.
>> ОК, така че хеш таблици.
Това е може би най- полезна малко за вашия pset
тук, защото започваш да бъде изпълнението на една от тях, или да опитате.
Аз наистина харесвам хеш таблици.
Те са много готино.
>> Така че основно това, което се случва, е хеш таблица
е, когато ние наистина се нуждаят от бързо вмъкване, изтриване и търсене.
Това са неща, които ние сме приоритизиране в хеш таблица.
Те могат да получат доста големи, но както ще видим с опит
има неща, които са много по-големи.
>> Но общо взето, всички хеш маса е функция хашиш
който ви казва, който кофа да постави всеки на данните си, всеки един от вашите елементи вътре.
Един прост начин да се мисли за хеш таблица е, че тя е само на кофи с неща,
нали?
Така че, когато се сортиране неща от като първата буква от името си,
това е нещо като хеш таблица.
>> Така че, ако бях на мястото на група момчета е в групи от който започва името
с A тук, или който и да е рожден ден е през януари, февруари, март,
независимо, че е ефективно създаване на хеш таблица.
Това е просто създаване на кофи, че Вие сами си елементи в
така че можете да ги намерите по-лесно.
Така че по този начин, когато имам нужда да се намери един от вас,
Не е нужно да търсите през всяка от вашите имена.
I може да бъде като, о, аз знам, че Рожден ден на Даниел е in--
АУДИТОРИЯ: --April.
SPEAKER 1: Април.
Така че аз гледам в моята април кофа, и с малко късмет,
тя ще бъде само един там и времето ми е постоянно в този смисъл,
като има предвид, ако трябва да погледнем през един куп хора,
това ще отнеме много повече време.
Така хеш таблици са наистина само кофи.
Лесен начин да се мисли за тях.
>> Така че е много важно нещо за хеш таблица е хеш функция.
Така че нещата, аз просто говори, като Вашето първо писмо на първата си име
или вашия рожден ден месец Това са идеи, които
наистина корелира с хеш функция.
Това е просто начин на вземане на решение, което вие сте кофа елемент отива в, OK?
Така че за това pset, можете да погледнете нагоре почти всеки хеш функция, която желаете.
>> Не трябва да бъде себе си.
Има някои наистина готини хора от там, които правят всички видове луд математика.
А ако искате да направите вашия проверка на правописа супер бързо,
Определено бих гледам в един от тях.
>> Но има също така прости, като изчислителна
сумата на думите, като всяка буква има номер.
Изчислете сумата.
Това определя кофата.
Те също така имат лесни тези, които са точно като всички от A-те тук,
всички от B е тук.
Всеки един от тези.
>> По принцип, той просто ви казва, който индекс масив вашия елемент трябва да отидат в.
Просто решаването на bucket-- всичко е функция на хашиш е.
Така че тук имаме пример, който е само първата буква на низ
че аз просто се говори.
>> Така че имате някакъв хеш това е просто първата буква на низ минус A,
който ще ви даде някои число между 0 и 25 години.
И това, което искате да направите, е уверете се, че това представлява
размера на хеш table-- колко кофи са там.
С много от тях хеш функции, те са
ще се върне ценности, които биха могли е далеч над броя на кофи
че всъщност трябва в хеш таблица,
така че трябва да се направи сигурен и моден от тях.
В противен случай, той ще каже, О, тя трябва да бъде в кофа 5000
но имате само 30 кофи във вашия хеш таблица.
И разбира се, ние всички знаем, че е ще доведе до някои луди грешки.
Така че не забравяйте да мод от размер на вашия хеш таблица.
Cool.
Така сблъсъци.
Хубаво ли всички досега?
Mmhmm?
>> АУДИТОРИЯ: Защо би го се върне като масивна стойност?
>> SPEAKER 1: В зависимост от алгоритъма че си хеш функция използва.
Някои от тях ще направя луд умножение.
И това е всичко, за получаване на с равномерно разпределение,
така че те да се направят някои наистина луди неща понякога.
Това е всичко.
Нещо друго?
OK.
>> Така сблъсъци.
По принцип, както казах по-рано, в най-добрия случай,
всяка кофа гледам в е ще има едно нещо,
така че не е нужно да разгледаме всички, нали?
Аз нито знам, че е там, или това е Не, и това е, което наистина искаме.
Но ако имаме десетки хиляди точки на данни и по-малко от този брой
кофи, ние ще имаме сблъсъци, където в крайна сметка нещо
ще трябва да се окажете в кофа, която вече има елемент.
>> Така че въпросът е, какво правим в този случай?
Какво ще правим?
Ние вече имаме нещо там?
Да, ние просто го хвърли?
>> Не.
Ние трябва да поддържаме и двете от тях.
Така начина, по който обикновено се прави това е какво?
Каква е структурата на данните ние просто говорихме?
АУДИТОРИЯ: свързан списък.
SPEAKER 1: свързан списък.
Така че сега, вместо на всеки от тях кофи само с един елемент,
тя ще съдържа свързан списък на елементите, които са хеширани в нея.
OK, може всеки вид получите тази идея?
Защото не може да има масив защото ние не знаем колко много неща
ще бъде там.
A свързан списък ни позволява да Трябва просто точния брой, че
се сегментира в тази кофа, нали?
>> Така линейни сондиране е основно това idea--
това е един от начините за справяне с евентуален сблъсък.
Какво можете да направите, е, ако в този случай, Бери се сегментира в 1
и ние вече имаме нещо там, просто
продължавай, докато можете да намерите на празен слот.
Това е един от начините да се справя.
Другият начин да се справят с е с това, което току-що
called-- Свързаните списък се нарича извикване.
>> Така че тази идея работи, ако Вашата хеш таблица мислите
е много по-голям от определени вашите данни или ако
искате да опитате и да се минимизира верижното докато не е абсолютно необходимо.
Така че едно нещо е линейна сондиране очевидно означава
че си хеш функция не е чак толкова полезен
защото вие ще се окажете с помощта Вашата функция хашиш, Как да стигнем до точката,
можете линейни сонда до известно място, което е на разположение.
Но сега, разбира се, нищо друго, което завършва там,
вие ще трябва да търсите, дори още по-надолу.
>> И там е много по- Разходи за търсене,
отива в въвеждане елемент в хеш таблица, сега, нали?
И сега, когато отидете и се опитайте да намерите Бери отново, ти започваш да го хеш,
и то се случва да се каже, О, погледнете в кофа 1,
и това няма да бъде в кофа 1, така че вие ​​сте
ще трябва да преминават през останалата част от тях.
Така че понякога е полезно, но в повечето случаи,
ние ще кажем, че верижното е това, което искам да правя.
>> Така че ние говорихме за това по-рано.
Аз имам малко по-напред от себе си.
Но верижното е основно, че всяка кофа в хеш таблица
е просто свързан списък.
>> Така че по друг начин, или по-технически начин да се мисли за хеш таблица
е, че това е просто масив на свързани списъци, които
когато пишете си речник а вие се опитвате да го заредите,
мисля за него като за масив от свързани списъци
ще го направи много по-лесно за да можете да се инициализира.
>> АУДИТОРИЯ: Така хеш таблица има предварително определен размер,
като [недоловим] от кофи?
>> SPEAKER 1: Точно така.
Така че има определен брой кофи, че determine--
които вие трябва да Чувствайте се свободни да се играе с тях.
Тя може да бъде доста хладно да видим какво ще стане
като промените вашия номер на кофи.
Но да, той има номер на кофи.
Какво Ви дава възможност да се поберат като много елементи, от които се нуждаете
е този отделен верижното ви, където са свързани списъци във всяка кофа.
Това означава, че вашият хеш таблица ще бъде точно на размера
че имате нужда от него, за да бъде, нали?
Това е целият смисъл на свързани списъци.
Cool.
>> Така че всеки OK там?
Добре.
Ah.
Какво точно се случи?
Наистина сега.
Предполагам, някой ме убива.
>> ОК, ние ще отидем в опит, които са малко луди.
Обичам хеш таблици.
Мисля, че те са наистина страхотно.
Опитва са готини, също.
>> Така че няма кой да си спомня какво пробвам е?
Вие трябва да са преминали през то за кратко в лекция?
Спомняте ли си вид на това как тя работи?
АУДИТОРИЯ: Аз съм просто кимаше че мина над него.
SPEAKER 1: Ние трябва да излизат над него.
ОК, ние сме наистина ще отида над него сега е това, което казва.
>> АУДИТОРИЯ: Това е за извличане на дърво.
>> SPEAKER 1: Да.
Това е извличане на дърво.
Awesome.
Така че едно нещо, което трябва да отбележим е, че ние търсите в отделните герои
тук, нали?
>> Така че, преди с нашата хеш функция, ние Гледаха думите като цяло,
а сега ние търсим повече на героите, нали?
Така че ние имаме Maxwell тук и Мендел.
Така че основно try-- начин да се мисли за това е, че всяко ниво тук
е набор от букви.
Така че това е вашият корен възел тук, нали?
Това има всички символи на азбука за началото на всяка дума.
>> И това, което искате да направите, е да речем, ОК, ние имаме някои M дума.
Отиваме да търсим Максуел, така отиваме на М. И М пункта до цяло
друг масив, където всеки дума, докато има
е дума, която има като втората буква,
толкова дълго, тъй като има една дума, която има B като втората буква,
тя ще има указател става до известна следващия масив.
>> Вероятно не е дума, която MP нещо,
така че в позиция Р в този масив, тя просто ще бъде NULL.
Той би казал, OK, няма дума че е M последвано от P, OK?
Така че, ако ние мислим за това, всеки един от тези малки неща
всъщност е един от тях големи масиви от А до Z.
Така че това, което може да бъде едно от нещата, това е един вид недостатък на опит?
>> Аудитория: A много памет.
>> SPEAKER 1: Това е един тон на паметта, нали?
Всеки един от тези блокове тук представлява 26 места, 26 елемент масив.
Така че се опитва да получите невероятно пространство тежък.
>> Но те са много бързи.
Така невероятно бързо, но наистина пространство неефективна.
Нещо трябва да разбера кои точно искате.
Това са наистина страхотно за вашата pset, но те не заемат много памет,
така че да пласирам.
Така ли?
>> АУДИТОРИЯ: Би ли било възможно да се създаде пробвам и след това
след като имате всички данни в това, че вие ​​need--
Аз не знам дали това би имало смисъл.
Бях се отървем от всички NULL герои, но след това
вие не ще бъде в състояние да индексира them--
>> SPEAKER 1: Вие все още се нуждаят от тях.
>> АУДИТОРИЯ: - по същия начин всеки път.
SPEAKER 1: Да.
Вие се нуждаете от NULL герои, за да Знаете ли, че ако там не е една дума там.
Бен имахте ли нещо, което искате?
OK.
Добре, така че отиваме да отида малко по-
в техническа подробност зад пробвам и работи чрез един пример.
>> ОК, така че това е едно и също нещо.
Като има предвид, свързан списък, основната ни вид of-- каква е думата, която искате? -
като изграждане на блок беше възел.
В опит, ние също имаме един възел, но това е определено по различен начин.
>> Така че ние имаме някакъв булев че представлява дали дума всъщност
съществува на това място, и след това ние имаме някои масив here-- или по-скоро,
това е указател към масив от 27 символа.
И това е, в този случай, този 27-- Сигурен съм, че всички от вас са като, чакай,
има 26 букви в азбуката.
Защо имаме 27?
>> Така че в зависимост от начина, по който изпълнява тази,
това е от pset че разрешени за апострофи.
Така че това е защо допълнително един.
Вие също ще трябва по някакъв случаи нулевата Терминатор
е включен като един от знаци, че това е право да бъде,
и това е, как те проверете да видим дали това е краят на думата.
Ако сте заинтересувани, проверете Видео Кевин за study.cs50,
както и Wikipedia има някои добри ресурси там.
>> Но ние ще отидем през просто вид на начина, по който може да работи чрез пробвам
ако даден човек.
Така че ние имаме супер проста тук има думи "прилеп" и "увеличение" в тях.
И както виждаме тук, това малко пространство тук
представлява нашата булев че казва, да, това е думата.
И тогава това е нашата масиви от символи, нали?
>> Така че ние ще да мине през намиране на "прилепите" в този опит.
Така че започнете от върха, нали?
И ние знаем, че б съответства Вторият показател, вторият елемент
в този масив, защото и б.
Така приблизително втория.
>> И той казва, OK, хладно, следва, че в следващата масива, защото, ако си спомним,
това не е, че всеки от тях всъщност съдържа елемент.
Всеки един от тези масиви съдържа указател, нали?
Това е важно разграничение да се направи.
>> Знам, че това ще се be-- опита са Наистина е трудно да се кача на първия път,
така че дори и ако това е втори или трети път
и тя все още е вид на привидна трудно,
Обещавам, ако отидете часовник краткосрочен отново утре,
то най-вероятно ще направи много по-дълбок смисъл.
Това отнема много за храносмилане.
Аз все още понякога съм като, чакай, какво е опит?
Как мога да използвам това?
>> Така че ние сме Б, в този случай, която е втората ни индекс.
Ако имахме, да речем, в или г или друг писмо,
ние трябва да се набележат, че обратно към индекса на нашия масив, че съответства.
Така че ние ще вземе като rchar и ние просто изваждане на разстояние, за да го преобразувате от 0 до 25.
Всеки добър как Карта нашите герои?
OK.
>> Така че отиваме на втората и ние се види, че, да, това не е да NULL.
Ние можем да преминем към следващия набор.
Така че отиваме към следващия набор тук.
>> И ние казваме, добре, сега ние трябва да се види дали е тук.
Дали A нула или го прави всъщност се движи напред?
Така че в действителност се движи предаде в този масив.
И ние казваме, OK, т е последното ни писмо.
Така че отиваме в тона на индекса.
И тогава ние се движат напред защото има още един.
И това казва основно, че, да, се казва, че има една дума here--
че ако следвате този път сте пристигнали
в една дума, която знам, е "прилеп".
Да?
>> АУДИТОРИЯ: Дали е стандарт за това като индекс 0 и след това да има нещо в едно
или да има в края?
>> SPEAKER 1: No.
Така че, ако погледнем назад в нашия декларация тук, това е булев,
така че това е неговата собствена елемент във вашата възел.
Така че това не е част от масива.
Cool.
Така че, когато ние завършим нашата дума и ние сме в този масив, което искаме да направим
е да направи проверка за това нито дума.
И в този случай, тя ще се върне да.
>> Така че по тази бележка, ние знаем, че "зоопарк" - ние знаем, като хора, които "зоологическа градина" е дума,
нали?
Но се опитайте тук ще се каже, не, това не е така.
И бих казал, че тъй като ние не го е определила като дума тук.
Въпреки че можем да прекосяват чрез на този масив,
този опит ще кажа, че, не, зоологическа градина не е във вашия речник
защото ние не сме го е определила като такава.
>> Така че един от начините да направите that-- О, съжалявам, това.
Така че в този случай, "зоопарк" не е С една дума, но тя е в нашия опит.
Но в това, да кажем че го искат въведе думата "баня", какво се случва,
е, че ние следваме through-- б, в, т.
Ние сме в този масив, и отидем да търсите за час.
>> В този случай, когато ние погледнем показалеца на час,
това е, сочещи към NULL, OK?
Така че, освен ако не е изрично сочейки към друг масив,
приемем, че всички указатели в този масив са насочени към нула.
Така че в този случай, ч е насочена до нула, така че ние не можем да направим нищо,
така че също ще се върне невярно, "баня" не е тук.
Така че сега ние сме всъщност ще мине през
как ще можем действително да кажа че "зоологическа градина" се намира в нашия опит.
Как да вмъкнете "зоопарк" в нашия опит?
Така че в един и същи начин, че ние започнахме с нашата свързан списък, започваме в корена.
Когато се колебаете, започнете на основата на тези неща.
>> И ние ще кажем, OK, Z.
Z съществува в това, и го прави.
Значи да преминат към следващата си масив, OK?
И след това на следващия, ние казваме, OK, се о съществува?
Това е така.
Това отново.
>> И така, на следващата ни един, казахме, OK, "зоопарк" вече съществува тук.
Всичко, което трябва да направите е да зададете този равен да е вярно, че има една дума там.
Ако беше последвано всичко до преди този момент,
това е една дума, така че просто задайте равна на себе си.
Да?
>> АУДИТОРИЯ: Така че след това прави това означава, че "ба" е дума, също?
>> SPEAKER 1: No.
Така че в този случай, "ба", ние ще се тук, ние ще кажем, че е една дума,
и тя все още ще бъде не.
OK?
Mmhmm?
>> АУДИТОРИЯ: Така че, след като е го дума и ще ви кажа, да, то тогава
ще съдържа за да отидете на m?
>> SPEAKER 1: Така че това трябва да се направи with-- сте зареждането на тази вътре.
Вие казвате "зоологическа градина" е дума.
Когато отидете да check-- като, да речем, искате да кажете,
означава "зоопарк" съществува в този речник?
Вие само ще търсене за "зоопарк" и след това да проверите дали това е думата.
Вие никога няма да се движат чрез да m, защото това не е
това, което търсите.
>> Така че, ако ние наистина искахме да добави "баня" в този опит,
ние ще направим същото както направихме с "зоопарк"
освен ние ще видим, че когато ние се опита да стигне до час, то не съществува.
Така че може да се мисли за това като се опитва за да добавите нов възел в свързан списък,
така че ние ще трябва да се добавят още един от тези масиви, като така.
И след това, което правим е, че ние просто настройте ч елемент на този масив, сочещи към това.
>> И тогава какво ще искаме да направим тук?
Добавете го равно на истински защото това е една дума.
Cool.
Знам.
Опитва не са най-вълнуващите.
Повярвай ми, знам.
>> Така че едно е да се реализира с опит Аз казах, те са много ефективни.
Така че ние сме те виждали да отнеме до един тон на пространството.
Те са вид объркващо.
Така че, защо би някога сме ги използвате?
Ние използваме тези, защото те са невероятно ефективен.
>> Така че, ако някога търсите с една дума, вие сте единствената
ограничена от дължината на думата.
Така че, ако търсите за дума, която е с дължина пет,
сте само някога ще трябва да се направи най-много пет сравнения, OK?
Така че това го прави по същество постоянна.
Подобно на вмъкване и справка са основно константно време.
>> Така че, ако можете да си получите нещо константно време,
това е толкова добър, колкото го получава.
Вие не можете да получите по-добре, отколкото константно време за тези неща.
Така че това е един от най огромните плюсове на опита.
>> Но това е много място.
Така че някак си трябва да реши това, което е по-важно за вас.
И на днешните компютри, на пространство, което пробвам може да отнеме
може би не засяга ви, че е много, но може би
имаш работа с нещо че има много, много повече неща,
и опит просто не е разумно.
Да?
>> АУДИТОРИЯ: Чакай, така че трябва 26 писма във всеки един от тях?
>> SPEAKER 1: Mmhmm.
Да, имате 26.
Имате някои е дума маркер и след това имате 26 указатели във всеки един.
И те point--
>> АУДИТОРИЯ: И всеки 26 те всеки има 26?
>> SPEAKER 1: Да.
И ето защо, колкото можете виж, тя се разширява много бързо.
Добре.
Така че отиваме да влязат в дървета, които Аз се чувствам като е по-лесно и вероятно ще
е една хубава малка отсрочка от опита там.
Така че, надявам се повечето от вас съм виждал дърво преди.
Не харесвам доста хора отвън, които съм
не знам дали някой отиде на открито наскоро.
Отидох ябълка бране този уикенд, и о, Боже мой, че е красива.
Не знаех листа може да изглежда, че доста.
>> Така че това е само едно дърво, нали?
Това е просто някакъв възел, и сочи към куп други възли.
Както виждате тук, това е вид на повтаряща се тема.
Възли, насочен към възли е вид същността на много структури от данни.
Просто зависи от това как ние да ги насочи към всяка друга
и начина, по който преминават чрез тях и как можем
въведете неща, които определя техните различни характеристики.
>> Така че просто някои терминология, които аз съм използвал преди.
Така корен е всичко, което е на самия връх.
това е мястото, където ние винаги се започне.
Можете да мислите за него като за главата също.
Но за дървета, ние сме склонни да се отнасят към него като корен.
>> Всичко в долния here-- в много, много bottom--
са считани листа.
Така че върви заедно с цялата работа дърво, нали?
Листата са по краищата на вашето дърво.
>> И тогава ние също имаме няколко термини, за да говорят за възли във връзка
един към друг.
Така че ние имаме майка, деца, братя и сестри.
Така че в този случай 3 е майка на 5, 6 и 7.
Така родителят е такова, каквото е една стъпка по-горе каквото и да сте
отнасящи се до тях, така че просто като родословно дърво.
Надяваме се, че всичко това е малко по- малко по-интуитивен от опитите.
>> Братя и сестри са всички, които имат същата майка, нали?
Те са на същото ниво тук.
И тогава, както бях казвайки, децата са просто
каквото и да е с една стъпка по-долу възел в въпрос, нали?
Cool.
Така двоично дърво.
Може ли някой да отгатна на един от характеристиките на двоичен дърво?
>> АУДИТОРИЯ: Max два листа.
>> SPEAKER 1: Точно така.
Така максимум от два листа.
Така че в това и преди, ние имахме този че имаше три, но в двоичен дърво,
имате максимум от две деца на една майка, нали?
Има още интересна характеристика.
Някой знае ли, че?
Binary дърво.
>> Така двоично дърво ще има всичко на the-- това не е sorted--
но в сортирано двоично дърво, всичко на правото
е по-голяма от родител, и всичко в ляво
е по-малко, отколкото на родителя.
И това е тест въпрос преди, така че е добре да знаете.
Така че начина, по който ние определяме това, отново, ние имаме друг възел.
Това изглежда много подобно на това?
Двойно
>> АУДИТОРИЯ: свързани списъци
>> SPEAKER 1: двойно свързан списък, нали?
Така че, ако ние вместо това с предходната и следващата,
това ще бъде двойно свързан списък.
Но в този случай, ние всъщност има ляво и дясно и това е всичко.
В противен случай, това е точно същото.
Ние все още имаме елемент което търсите,
и просто да има две насоки Ще каквото е следващата.
Да, така двоично търсене дърво.
Ако забележите, всичко на точно тук е по-голяма than--
или всичко веднага надясно тук
е по-голяма от всичко тук е по-малко от.
>> Така че, ако трябва да се търси чрез това трябва да изглежда много близо до двоично търсене
тук, нали?
Освен, вместо да гледаш на половината от масив,
ние сме просто гледам или отляво страна или от дясната страна на дървото.
Така става малко по-просто, мисля.
>> Така че, ако си корен е NULL, Очевидно това е просто невярно.
И ако той е там, очевидно това е вярно.
Ако тя е по-малко, отколкото, да търсим наляво.
Ако тя е по-голяма от ние търсим правото.
Това е точно като двоично търсене, просто различна структура на данни
които ние използваме.
Вместо масив, това е просто двоично дърво.
>> OK, стекове.
И също така, тя изглежда като ние може да има по-малко време.
Ако го направим, аз съм щастлив да отида над нищо от това отново.
ОК, така че купища.
Дали някой си спомня какво stacks-- всички характеристики на комин?
>> ОК, така че повечето от нас, мисля, яде в трапезарията halls--
толкова, колкото ние не може да искате да.
Но очевидно, можеш да се сетиш на комин буквално като купчина тави
или купчина от неща.
И това, което е важно да осъзнаят е, че тя е
something-- характеристиката че ние го наричаме по-- е LIFO.
Някой знае ли какво означава?
Mmhmm?
>> АУДИТОРИЯ: Последно, първа изходяща.
>> SPEAKER 1: Точно така, да продължи, първа изходяща.
Така че, ако ние знаем, ако сме подреждане на нещата нагоре, най-лесното нещо да вземете off--
и може би единственото нещо, което може да вземете изключва, ако ни стак е голям enough--
е, че горния елемент.
Така че каквото и да се постави на last-- както виждаме тук,
каквото и да е бил бутнат на най-recently-- е
ще бъде първият нещо, което ние гърмя, OK?
>> Така че това, което имаме тук, е друг typedef структура.
Това е наистина просто искал интензивен курс по структура на данните,
така че има много хвърлени по вас, момчета.
Знам.
Така че още една структура.
Уау за структури.
>> И в този случай, това е някаква показалка на масив, който има някои капацитет.
Така че това представлява нашата стак тук, като реалното ни масив
че държи на нашите елементи.
И след това тук имаме някакъв размер.
>> И обикновено, което искате да запазите следите колко е голям вашият стак е
защото това, което се случва, за да се даде възможност можете да направите, е, ако знаете размера,
тя ви позволява да се каже, ОК, аз съм най-капацитет?
Мога ли да добавите още нещо?
И също така ви казва където горната част на вашия стак
е да знаете какво ви всъщност може да се свали.
И това всъщност ще да е малко по-ясно тук.
>> Така че, за да бута, едно нещо, ако сте някога да приложи натиск,
аз просто казвам, си стак има ограничен размер, нали?
Нашата гама имали някакъв капацитет.
Това е масив.
Това е с фиксиран размер, така че ние трябва да се уверете се, че ние не сме пускането повече
в нашия набор от нас всъщност има място за.
>> Така че, когато създавате тласък функция, първото нещо, което правя е да речем, OK,
имам място в моя стак?
Защото, ако не го направя, съжалявам, Аз не може да се съхранява вашата стихия.
Ако го направя, а след това искате да съхраните то в горната част на комина, нали?
>> И това е защо ние имаме да следите нашия размер.
Ако не следите на нашия размер, ние не знаем къде да го сложи.
Ние не знаем колко много неща са в нашата вече масив.
Както очевидно има начини че може би ще го направя.
Може да се инициализира всичко NULL и след това се проверява за най-новата NULL,
но много по-лесно нещо е просто да се каже, добре, следите от техния размер.
Като знам, че има четири елемента в моя набор, така че следващото нещо,
че ние поставяме, ние сме ще се съхранява в индекса 4.
И след това, разбира се, това означава, че успешно сте бутна нещо
на вашия стак, вие искате да увеличите размера
така че да знаете къде се намирате, така че че можете да натиснете повече неща.
>> Така че, ако ние се опитваме да се появи нещо извън стека,
какво може да е първото нещо, че искаме да се провери за?
Вие се опитвате да се вземат нещо от вашия стак.
Сигурни ли сте, че има нещо във вашия стак?
Не.
И така, какво може да искаме да се провери?
>> АУДИТОРИЯ: [недоловим].
SPEAKER 1: Проверка за размера?
Size.
Така че ние искаме да се провери, за да се види дали ни размер е по-голям от 0, OK?
И ако е така, тогава ние искаме да се намали ни размер от 0 и го върнете това.
Защо?
>> В първата бяхме бутане, ние го избута
върху размера и след това актуализиран размер.
В този случай, ние сме намаляващи размери и след това го свали, тя скубане
от нашия масив.
Защо бихме могли да направим това?
Така че, ако имам едно нещо на моя стак, какъв ще бъде размера си в този момент?
1.
>> И къде е елемент 1 се съхранява?
На какъв индекс?
АУДИТОРИЯ: 0.
SPEAKER 1: 0.
Така че в този случай, ние винаги трябва да се направи sure--
вместо да се завърне размер на минус 1, тъй като ние
знаем, че нашата елемент е ще се съхранява при по-малко 1
каквото е нашето, това просто се грижи за него.
Това е малко по-елегантен начин.
И ние просто намалите стъпково ни размер и след това се върнете размер.
Mmhmm?
>> АУДИТОРИЯ: Предполагам, че просто като цяло, защо би тази структура на данните
да бъде от полза?
>> SPEAKER 1: Това зависи от вашата връзка.
Така че за някои от теорията, ако работите with-- OK,
нека да видим дали има благоприятен един че е от полза за повече, отколкото навън
на CS.
С купчини, по всяко време имате нужда да следите на нещо, което
е най-наскоро добавя е, когато вие ще искате да използвате стак.
>> И не мога да се сетя за по добро пример за това точно сега.
Но когато най-новите нещо, което е най-важно за вас,
това е, когато купчина ще бъде полезно.
Опитвам се да мисля, че ако там е добра за това.
Ако мисля за добър пример в следващия 20 минути, аз определено ще ви кажа.
>> Но като цяло, ако има нещо, както казах, най-много, когато най-новите
Най-важното е, че е където стак влезе в игра.
Като има предвид, опашки са вид обратното.
И всички малки кучета.
Това не е ли страхотно, нали?
Имам чувството, че трябва да Просто трябва зайче видео
точно в средата на раздел за вас, момчета
защото това е силен раздел.
>> Така опашка.
Основно опашка е като линия.
Вие, момчета, аз съм сигурен, че тази употреба всеки ден, точно като в нашите зали за хранене.
Така че ние трябва да отидем в и да получите нашите тави, аз съм
Наистина ли трябва да чакат на опашка да плъзнете или да получите вашата храна.
>> Така че разликата тук е, че това е FIFO.
Така че, ако LIFO е на последно място в първо се, FIFO е първата, първа изходяща.
Така че това е мястото, където каквото и да постави на първата е най-важната.
Така че, ако сте били чака в line-- може да ви
представете си, че сте отишли ​​да иди новия iPhone
и имаше купчина където Последният човек в съответствие го на първо място,
хората ще се избиват един друг.
>> Така че, FIFO, всички ние сме много добре запознати с в реалния свят тук,
и всичко това е свързано с действително вид пресъздаване цялата тази линия
и опашка структура.
Така че, докато при стека, имаме тласък и поп.
С опашка, имаме Enqueue и dequeue.
Така Enqueue същество означава, го постави върху гърба,
и dequeue средства да се разстояние от предната.
Така че нашата структура от данни е малко по-сложно.
Имаме второ нещо, за да следите.
>> Така че без главата, това е точно комин, нали?
Това е същата структура като комин.
Единственото нещо различно сега е, че ние има тази глава, която ти какво мислиш
ще следите?
>> АУДИТОРИЯ: Първият.
>> SPEAKER 1: вдясно, Първото нещо, което ще се постави вътре.
Ръководителят на нашата опашка.
Който е първи по ред.
Добре, така че ако правим Enqueue.
Отново, с някоя от тези структури от данни,
тъй като си имаме работа с масив, ние трябва да се провери, ако имаме пространство.
>> Това е нещо като да ми кажеш вие, момчета, ако отворите даден файл,
трябва да се провери за нищожна.
С всяка от тези купчини и опашки, от които се нуждаете
за да види дали има място, защото ние сме справяне с фиксиран размер масив,
както виждаме here-- 0, 1, всички до 5.
Така че това, което правим в този случай е проверка за да видите дали все още има пространство.
Дали нашата размер по-малко от капацитета?
>> Ако е така, ние трябва да го съхранявате в опашката и ние актуализираме размер.
Така че това, което може да бъде на опашката в този случай?
Това не е изрично изписано.
Как бихме могли да го съхранявате?
Какво ще бъде на опашката?
>> Така че нека да преминете през този пример.
Така че това е масив с размер 6, нали?
И ние имаме в момента, нашият размер е 5.
И когато го поставите в, то се случва да отидат в петия индекса, нали?
Така се съхранява в опашка.
>> Друг начин да се напише опашка би просто да бъде наш масив на индекс на размер, нали?
Това е размер 5.
Следващото нещо е да отида в 5.
Cool?
OK.
Той получава малко по-сложно, когато започнем каша с главата.
Да?
>> АУДИТОРИЯ: Означава ли това, че ние ще са декларирали масив, който
беше дълга пет елемента и След това ние добавяме към него?
>> SPEAKER 1: No.
Така че в този случай, това е купчина.
Това ще бъде обявено като масив с размер 6.
И в този случай, ние Просто трябва един пространство вляво.
>> ОК, така че едно нещо, което е в тази случай, ако главата ни е на 0,
тогава ние просто да го добавите в размер.
Но това става малко по-сложни тъй като всъщност те
не разполагат с пързалка за това, така че аз ще
да се направи, защото това не е толкова просто, след като
започне да се отървете от неща.
Така че със стак имате само някога
да се притеснявате за това, което е с размерите когато добавяте нещо,
с опашка вие също трябва да се направи сигурен, че главата ви се отчита,
защото готино нещо за опашки е, че ако не сте на капацитет,
всъщност можете да го обгърне.
>> ОК, така че един thing-- о, това е ужасно тебешир.
Едно нещо е да се помисли по случая.
Ние просто ще направя пет.
ОК, така че ние ще казват, че главата е тук.
Това е 0, 1, 2, 3, 4.
>> Главата е там, и моля неща в тях.
И ние искаме да се добави нещо, нали?
Така че това, което ние трябва да се знам е, че главата е винаги
ще се движат по този начин и след това по принципа на обратната наоколо, OK?
>> Така че тази опашка има място, нали?
Той има място в самото начало, вид обратното на това.
Така че това, което трябва да направите, е, че ние трябва да се изчисли на опашката.
Ако знаете, че вашият глава не се е променила, опашката
е просто вашия масив в индексът на размера.
>> Но в действителност, ако сте с помощта на опашката, главата ти е вероятно да бъде актуализиран.
Така че това, което трябва да направите, е всъщност изчисли опашката.
Така че това, което правим, е тази формула тук, което аз отивам да ви разочарова
момчета мислят за и След това ние ще говорим за това.
Така че това е капацитет.
>> Така че това действително ще ви дам един начин да го направя.
Защото в този случай, какво?
Главата ни е на 1, нашия размер е 4.
Ако Министерството на отбраната, че до 5, ще получите 0, което е мястото, където ние трябва да го въведете.
>> Така че след това в следващия случай, ако трябва да направите това,
ние казваме, добре, нека dequeue нещо.
Ние dequeue това.
Ние приемаме този елемент, нали?
>> И сега главата ни се посочи тук, и ние искаме да се добави в друго нещо.
Това е в общи линии обратно на нашата линия, нали?
Опашките могат да увийте около масива.
Това е една от основните разлики.
Купища, не можете да направите това.
>> С опашки, можете да защото всичко, което има значение
е, че вие ​​знаете какво най-наскоро беше добавен.
Тъй като всичко ще бъде добавен в това наляво посока, в този случай,
и след това увийте около, можете да продължи въвеждането на нови елементи
в предната част на масива защото това не е наистина
предната част на масива вече.
Можете да мислите за началото на масив и когато главата ти в действителност.
>> Така че тази формула е как да се изчисли си опашка.
Ли, че има смисъл?
OK.
OK, dequeue, и след това вие имате 10 минути
да ми задавате уточняващи въпроси искате, защото знам, че е луд.
>> Добре, така че в същата way-- Аз не знам, ако вие забелязали,
но CS е за всички модели.
Нещата са доста по едни и същи, само с малки ощипвам.
Така че едно и също нещо тук.
Ние трябва да се провери, за да видите, ако ние всъщност има нещо в нашата опашка, нали?
Кажи, OK, е нашият размер по-голям от 0?
Cool.
>> Ако го направим, тогава ние се движи главата си, което е това, което току-що демонстрира тук.
Ние актуализира главата ни да бъде един повече.
И тогава ние намалите стъпково ни размер и да се върнете на елемента.
>> Има много неща, по-конкретно код на study.cs50.net,
и аз силно препоръчвам става чрез нея, ако имате време,
дори ако това е само псевдо-код.
И ако вие искате да говорите чрез че с мен един по един, моля ви кажете ми
знам.
Щях да бъда щастлив да.
Структури от данни, ако вземете CS 124, ще
Знам, че структури от данни стават много забавно и това е само началото.
>> Така че аз знам, че е трудно.
Това е ОК.
Ние се борим.
Аз все още го правя.
Така че не се тревожи твърде много за това.
>> Но това е в основата си катастрофата курс по структури от данни.
Знам, че е много.
Има ли нещо, което ние биха искали да отидете отново?
Всичко, което искаме да говорим чрез?
Да?
>> АУДИТОРИЯ: За този пример, така че новата опашката е 0 над това?
SPEAKER 1: Да.
АУДИТОРИЯ: OK.
Така че след това преминава през, ще имате един плюс 4 or--
>> SPEAKER 1: Така ли се казва, когато искаме да направим това отново?
АУДИТОРИЯ: Да.
Така че, ако сте били фигуриращ out-- където са ви изчисляване на опашката от това, че?
>> SPEAKER 1: Така опашката е in-- смених това.
Така че в този пример тук, това е масива гледаме, OK?
Така че ние имаме неща в 1, 2, 3 и 4.
Така че ние имаме нашата глава е равна на 1 в този момент, и нашия размер е равен на 4
в този момент, нали?
>> Вие всички ще се съгласим, че е така?
Така че правим главата плюс размера, който ни дава 5, а след това Министерството на отбраната с 5.
Ние получаваме 0, което ни казва, че 0 е където е нашата опашка, където имаме пространство.
>> АУДИТОРИЯ: Какво е шапка?
>> SPEAKER 1: Капацитетът.
Извинете.
Така че това е размера на масив.
Да?
>> АУДИТОРИЯ: [недоловим] преди ние върне елемент?
>> SPEAKER 1: Така че ние се премести на главата или да се върне в момента?
Така че, ако ние се движат един, намалите постъпково размера?
Дръж се.
Определено забравих друг.
Няма нищо.
Там не е друга формула.
Да, вие ще искате да се върнете на главата и след това се върнете обратно.
>> АУДИТОРИЯ: ОК, защото в този точка, ръководител е на 0,
и след това искате да се върнете индекс 0 и след това направи главата 1?
>> SPEAKER 1: Точно така.
Аз мисля, че има друг формула нещо като това.
Аз не разполагат с него на върха на главата ми, Аз не искам да ви даде грешен.
Но аз мисля, че е напълно валидна до да речем, OK, съхранявайте това element-- каквото
елемент главата на is-- намалите стъпково си размер, движи главата си над и връщане
каквото и да е елемент.
Това е напълно валиден.
OK.
Имам чувството, че това не е като most-- не сте
ще излезе от тук като, да, знам, че се опитва.
Аз го има всичко.
Това е ОК.
Обещавам.
Но структури от данни са нещо, което това отнема много време, за да свикнеш.
Вероятно една от най-трудните неща, мисля, че в курса.
>> Така че определено се повторение и търсите at-- I
наистина не знам свързани списъци докато аз го направих твърде много с тях,
по същия начин, че не го направих Наистина разбирам указатели
докато аз трябваше да го научи за двама години и да направят собствените си psets с него.
Това отнема много повторения и време.
И в крайна сметка, тя вид ще изберете.
>> Но в същото време, ако имате вид на разбиране на високо ниво, което
те правят, техните плюсове и cons-- което е това, което
ние наистина са склонни да се подчертае, особено в хода интро.
Например, защо да използваме пробвам над масив?
Например, какви са позитивите и негативи на всяка една от тези?
>> И разбирането на компромисите между всеки от тези структури
е това, което е много по-важно в момента.
Възможно е да има един луд или два въпроса, които е
Ще ви помоля да приложат натиск или изпълнява поп или Enqueue и dequeue.
Но за по-голямата част, като че висше разбиране ниво и по-
на интуитивно разбиране е по-важно, отколкото в действителност
е в състояние да го изпълни.
>> Ще бъде наистина страхотно, ако всички вие може да изляза и да се приложи пробвам,
но ние разбираме, че не е задължително най-разумното нещо, което точно сега.
Но можете в pset, ако искате да, и тогава вие ще получите практика,
и тогава може би ще наистина го разбирам.
Да?
>> АУДИТОРИЯ: ОК, така, кои от тях са ние трябваше да се използва в pset?
Трябва ли да се използва един от тях?
SPEAKER 1: Да.
Така че имате избор.
Предполагам, че в този случай, ние можем говорим за pset малко
защото аз се завтече през тях.
Така че във вашия pset, имате избор на опита или хеш таблици.
Някои хора ще се опитат и да използвате един цвят филтри,
но тези, които технически не са правилни.
Поради вероятностен характер, те дават неверни положителни резултати понякога.
Те са хладен поглед, все пак.
Силно препоръчваме да търсите в тях най-малко.
Но вие имате избор между хеш таблица и пробвам.
И това ще бъде мястото, където заредите във вашия речник.
>> И вие ще трябва да изберете Вашата хеш функция,
вие ще трябва да изберете колко Кофи имате, и тя ще варира.
Например, ако имате повече кофи, Може би тя ще работи по-бързо.
Но може би вие губите много пространство по този начин, все пак.
Трябва да го разбера.
Mmhmm?
>> АУДИТОРИЯ: Ти каза, че преди това ние може да се използват и други хеш функции,
че ние не трябва да се създаване на хеш функция?
>> SPEAKER 1: Да, точно така.
Така буквално за хеш функция, като Google "хеш функция"
и за някои готини хора изглежда.
Не се очаква да се изгради Вашите собствени хеш функции.
Хората прекарват дипломни работи по тези неща.
>> Така че не се тревожи за изграждането на вашия собствен.
Намери един онлайн, за да започнете.
Някои от тях ще трябва да манипулира малко
да се уверите, вида връщане съвпадат и какво ли не, така че в началото,
Бих препоръчваме да използвате нещо много лесно, че може би просто
хешове на първата буква.
И след това, след като сте, че работи, вграден охладител хеш функция.
Mmhmm?
>> АУДИТОРИЯ: Ще пробвам да бъде или ефективно, но просто по-трудно да, like--
>> SPEAKER 1: Значи пробвам, мисля, е интуитивно трудно да се приложат
но е много бърз.
Въпреки това, заема повече място.
Отново можете да оптимизирате и двете от тези в различни начини и има начини to--
АУДИТОРИЯ: Как сме класирани по този въпрос?
Има ли matter--
>> SPEAKER 1: Значи степен нормален начин.
Ти започваш да бъдат категоризирани по дизайн.
Накъдето и да правите, вие искате да уверете, че тя е толкова елегантен, колкото може да бъде
и толкова ефективно, колкото може да бъде.
Но ако решите да опитате или хашиш маса, докато тя работи,
ние сме щастливи с това.
И ако използвате нещо, което хешове на първата буква, това е добре,
като може би като дизайн-мъдър.
Ние сме също така достигането на точка в тази semester--
Аз не знам дали сте момчета noticed-- ако сте
pset класове намалеят малко защото на дизайн и какво ли не,
това е съвършено глоба.
Става все по-до точката, където си програми стават все по-сложни.
Има повече места можете да подобрите.
>> Така че това е напълно нормално.
Това не е, че сте прави лошо на вашия pset.
Това е просто ние сме в по-трудно за вас сега.
Така че всеки е това чувство.
Просто степен всичките си psets.
Знам, че всеки го чувстваш.
>> Така че не се тревожи за това.
И ако имате някакви въпроси относно преди psets или начини да се подобри,
Опитвам се и коментира спецификата места, но понякога това е края
и аз се уморяват.
Има ли някакви други неща около структури от данни?
Сигурен съм, че вие ​​наистина не искам да говоря за тях повече,
но ако има, аз съм щастлив да отида с тях, както и всичко,
от лекция миналия седмица или миналата седмица.
>> Знам, че миналата седмица беше преглед, така че ние може да прескочи някои преглед
от лекция.
Всякакви други въпроси мога да отговоря?
Добре, всичко е наред.
Е, вие се измъкнем 15 минути по-рано.
>> Надявам се, че това е полу-полезен най-малкото, и аз ще ви видя, момчета следващата седмица,
или четвъртък работно време.
Има ли искания за закуски за следващата седмица, това е нещо?
Защото аз забравих бонбони днес.
И донесе бонбони последно седмица, но това е Деня на Колумб,
така че там бяха като шест души, които имаше четири торби с бонбони за себе си.
Аз може да донесе Starbursts отново, ако искате.
Starbursts?
ОК, звучи добре.
Имате голям ден, момчета.